Personal tools
You are here: Home Projects Internal Projects Controlled Perturbation of Polyhedral Surfaces
« May 2017 »
May
SuMoTuWeThFrSa
123456
78910111213
14151617181920
21222324252627
28293031
Log in


Forgot your password?
 

Controlled Perturbation of Polyhedral Surfaces

[Polyhedral Surfaces]

Abstract

We describe a perturbation scheme to overcome degeneracies and precision problems for algorithms that manipulate polyhedral surfaces using floating point arithmetic. The perturbation algorithm is simple, easy to program and completely removes all degeneracies. We describe a software package that implements it, and report experimental results. The perturbation requires O(n log^3 n +nDK^2) expected time and O(n log^3 n + nDK^2) working storage, and has O(n) output size, where n is the total number of facets in the surfaces, K is a small constant in the input instances that we have examined, D is a constant greater than K but still small in most inputs, and both might be as large as n in `pathological' inputs. A tradeoff exists between the magnitude of the perturbation and the efficiency of the computation. Our perturbation package can be used by any application that manipulates polyhedral surfaces and needs robust input, such as solid modeling, manufacturing and robotics. We describe an application for the computation of swept volumes, which uses our perturbation package and is therefore robust and does not need to handle degeneracies. Our work is based on the reference below, which handles the case of spheres, extending the scheme to the more difficult case of polyhedral surfaces perturbation.

Links

  • Dan Halperin and Sigal Raab
    Controlled perturbation for arrangements of polyhedral surfaces
    Full version [pdf]
  • Sigal Raab
    Controlled perturbation for arrangements of polyhedral surfaces with application to swept volumes
    In Proceedings of the 15th ACM Symposium on Computational Geometry (SoCG), 163-172, Miami, 1999 [link] [bibtex]
  • Sigal Raab
    Controlled Pertubation for Arrangements of Polyhedral Surfaces with Application to Swept Volumes
    M.Sc. thesis [pdf] [bibtex]
    Carried out at the Bar Ilan university, Ramat-Gan, Israel and the Tel Aviv university.
  • Controlled Perturbation (of Spheres) project

Contact

Sigal Raab http://www.math.tau.ac.il/~raab raab@post.tau.ac.il
Dan Halperin http://acg.cs.tau.ac.il/danhalperin halperin@post.tau.ac.il
Document Actions