Meshing of Piecewise Smooth Complexes (Surfaces and Volumes, Non-manifolds)





A piecewise smooth complex (PSC) is a collection of smooth patches which meet at nonsmooth or nonsmooth interfaces. We have recently built software which meshes PSCs in three dimensions using Delaunay simplices. The following abstract and video describes the implementation of this algorithm and gives examples to illustrate some of its features.

T. K. Dey, and J. A. Levine. DelPSC: A Delaunay mesher for piecewise smooth complexes Proc. 24th Annu. ACM Sympos. on Computational Geometry (2008) (Multimedia Submission).

  768x576   384x288
High Quality: AVI (72Mb)   AVI (19Mb)
Medium Quality: AVI (50Mb)   AVI (14Mb)

We have DelPSC software  which is based on the following  work (1). This work is a culmination of a series of works (2 and 3) that we describe below.

1. T. K. Dey, and J. A. Levine. Delaunay meshing of piecewise smooth complexes without expensive predicates. Manuscript, 2008.

PSCs can model a large class of geometric domains including polyhedra, smooth and piecewise smooth surfaces, and non-manifolds. In our first algorithm we devised a provable Delaunay refinement where we protect these regions with weighted points such that the weights mimic the local feature size in a Lipschitz-like manner. We then perform Delaunay refinement using the weighted Voronoi diagram. This work provides a new notion of local feature size and a proof for a generalized topological ball property.

2. S.-W. Cheng, T. K. Dey, and E. A. Ramos. Delaunay refinement for piecewise smooth complexes Proc. 18th Annu. ACM-SIAM Sympos. Discrete Algorithms (2007), 1096--1105.

Protecting a feature curve.

Extending the concepts above, a more practical version of this algorithm was designed and implemented. By applying a novel simplification, the number of topological tests was reduced from four to one. Moreover, the algorithm was extended to mesh both PSCs and the volumes contained within them. The following sources describe this work.

3. S.-W. Cheng, T. K. Dey, and J. A. Levine A Practical Delaunay Meshing Algorithm for a Large Class of Domains Proc. 6th Intl. Meshing Roundtable, 2007.

Two meshed PSCs, the Anchor (top) and Swirl (bottom). These models are meshed by identifying and protecting feature curves, performing a surface mesh, and then (if possible) performing a volume mesh

In our latest version of the algorithm we eliminated the need to compute feature size during the protection step. Instead, we adjust the weights of protecting balls on-the-fly to satisfy constraints during Delaunay refinement. Using this scheme, we prove that the Delaunay refinement terminates while reducing expensive computations in both phases of refinement.

T. K. Dey, and J. A. Levine Reducing expensive computations in Delaunay meshing of piecewise smooth complexes Manuscript, 2008. 

This project work is supported by NSF grants CCF-0430735 and CCF-0635008