People
Research
Publications
Meshing
Home
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.
Recently we have extended PSC meshing to a localization framework which works on the principle of divide-and-conquer as a result of which the algorithm and the software LocPSC runs much faster and can handle large meshes. See the end of this page for details.
1. T. K. Dey, and J. A. Levine. Delaunay meshing of piecewise smooth complexes without expensive predicates. Algorithms, vol. 2, issue 4 (2009), 1327--1349. doi:10.3390/a2041327. Technical report OSU-CISRC-7108-TR40, July, 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.
S.-W. Cheng, T. K. Dey, and J. R. Shewchuk. Delaunay Mesh Generation. CRC Press, 2012. (Chapter 13)
The above chapter grew out of:
T. K. Dey, and J. A. Levine. Delaunay meshing of piecewise smooth complexes without expensive predicates. Manuscript, 2008.
The algorithm described in our Delaunay Mesh Generation book has been extended to work under a localization framework. It works by splitting the space into octree nodes and meshing the input piece by piece within each node. The algorithm automatically makes sure that a coherent mesh is generated by the process while preserving all features. See the paper below for details. Our latest software LocPSC is based on this work.
T. K. Dey and A. Slatton. Localized Delaunay refinement for piecewise-smooth complexes. Proc. 29th Annu. Sympos. Comput. Geom. (2013).
This project work is supported by NSF grants CCF-0430735 and CCF-0635008