Abstract
We consider the problem of approximating nonsingular surfaces which are implicitly represented by equations of the form f(x,y,z)=0. Our correctness criterion is an isotopy of the approximate surface to the exact surface. We focus on methods based on domain subdivision using numerical primitives. Such methods are practical and have adaptive and local complexity. Previously, Snyder (1992) [3] and Plantinga-Vegter (2004) [4] have introduced techniques based on parameterizability and non-local isotopy, respectively. In our previous work (SoCG 2009), we synthesized these two techniques into an efficient and practical algorithm for curves. This paper extends our approach to surfaces. The extension is by no means routine: the correctness argument is much more intricate. Unlike the 2-D case, a new phenomenon arises in which local rules for constructing surfaces are no longer sufficient. We treat an important extension to exploit anisotropic subdivision. Anisotropy means that we allow boxes to be split into 2, 4 or 8 subboxes with arbitrary but bounded aspect ratio. This could greatly improve the adaptivity of the algorithm. Our algorithms are relatively easy to implement, as the underlying primitives are based on interval arithmetic and exact BigFloat numbers. We report on encouraging preliminary experimental results.
Original language | English (US) |
---|---|
Pages (from-to) | 451-462 |
Number of pages | 12 |
Journal | CAD Computer Aided Design |
Volume | 45 |
Issue number | 2 |
DOIs | |
State | Published - Feb 2013 |
Keywords
- Exact numerical algorithms
- Interval methods
- Isotopy
- Mesh generation
- Parameterizability
- Subdivision algorithms
- Surface approximation
- Topological correctness
ASJC Scopus subject areas
- Computer Science Applications
- Computer Graphics and Computer-Aided Design
- Industrial and Manufacturing Engineering