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).
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.
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.
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