Non-local isotopic approximation of nonsingular surfaces

Long Lin, Chee Yap, Jihun Yu

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)451-462
Number of pages12
JournalCAD Computer Aided Design
Issue number2
StatePublished - Feb 2013


  • 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


Dive into the research topics of 'Non-local isotopic approximation of nonsingular surfaces'. Together they form a unique fingerprint.

Cite this