Repairing and meshing imperfect shapes with delaunay refinement

Oleksiy Busaryev, Tamal K. Dey, Joshua A. Levine

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

As a direct consequence of software quirks, designer errors, and representation flaws, often three-dimensional shapes are stored in formats that introduce inconsistencies such as small gaps and overlaps between surface patches. We present a new algorithm that simultaneously repairs imperfect geometry and topology while generating Delaunay meshes of these shapes. At the core of this approach is a meshing algorithm for input shapes that are piecewise smooth complexes (PSCs), a collection of smooth surface patches meeting at curves non-smoothly or in non-manifold configurations. Guided by a user tolerance parameter, we automatically merge nearby components while building a Delaunay mesh that has many of these errors fixed. Experimental evidence is provided to show the results of our algorithm on common computer-aided design (CAD) formats. Our algorithm may also be used to simplify shapes by removing small features which would require an excessive number of elements to preserve them in the output mesh.

Original languageEnglish (US)
Title of host publicationProceedings - SPM 2009
Subtitle of host publicationSIAM/ACM Joint Conference on Geometric and Physical Modeling
Pages25-33
Number of pages9
DOIs
StatePublished - 2009
Externally publishedYes
EventSPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling - San Francisco, CA, United States
Duration: Oct 5 2009Oct 8 2009

Publication series

NameProceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling

Other

OtherSPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling
Country/TerritoryUnited States
CitySan Francisco, CA
Period10/5/0910/8/09

Keywords

  • Delaunay mesh generation
  • Piecewise-smooth complexes
  • Shape repair
  • Topology

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Science Applications
  • Computer Vision and Pattern Recognition
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Repairing and meshing imperfect shapes with delaunay refinement'. Together they form a unique fingerprint.

Cite this