Tetrahedral mesh generation by Delaunay refinement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Tetrahedral mesh generation by Delaunay refinement

Full text

Pdf (1.50 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the fourteenth annual symposium on Computational geometry table of contents

Minneapolis, Minnesota, United States

Pages: 86 - 95

Year of Publication: 1998

ISBN:0-89791-973-4

Author

Jonathan Richard Shewchuk

School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 120, Citation Count: 51

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/276884.276894 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Adrian Bowyer, Computing Dirichlet Tessellations. Computer l'ouma124(2):162-166, 1981.
	2	L. Paul Chew. Guaranteed-Quality Triangular Meshes. Technical Report TR-89-983, Department of Computer Science, Comell University, 1989.
	3	L. Paul Chew, Guaranteed-quality mesh generation for curved surfaces, Proceedings of the ninth annual symposium on Computational geometry, p.274-280, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161150]
	4	L. Paul Chew, Guaranteed-quality Delaunay meshing in 3D (short version), Proceedings of the thirteenth annual symposium on Computational geometry, p.391-393, June 04-06, 1997, Nice, France [doi>10.1145/262839.263018]
	5	Tarnal Krishna Dey, Chanderjit L. Bajaj, and Kokichi Sugiham. On Good Triangulations in Three Dimensions. International Journal of Computational Geometry & Applications 2(1):75-95, 1992.
	6	Lori A. Freitag and Carl Ollivier-Gooeh. A Comparison of Tetrahedral Mesh Improvement Techniques. Fifth Intema. tional Meshing Roundtable (Pittsburgh, Pennsylvania), pages 87-100. Sandia National Laboratories, October 1996.
	7	William H. Prey. Selective Refinement: A New Strate.# for Automatic Node Placement in Graded Triangular Meshes. International Journal for Numerical Methods in Engineedng 24( 11):2183-2200, November 1987.
	8	Charles L. Lawson. Sofm'are for Cz Surface Interpolation. Mathematical Software III (John R. Rice, editor), pages 161- 194. Acadernie Press, New York, 1977.
	9	Gary L. Miller , Dafna Talmor , Shang-Hua Teng , Noel Walkington, A Delaunay based numerical method for three dimensions: generation, formulation, and partition, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.683-692, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225286]
	10	Gary L. Miller, Dafna Talmor, Shang-Hua Teng, Noel Walk. ington, and Han Wang. Control Volume Meshes using Sphere Pacldng: Generation, Refinement and Coarsening. Fifth International Meshing Roundtable, pages 47--61, October 1996.
	11	Scott A. Mitchell , Stephen A. Vavasis, Quality mesh generation in three dimensions, Proceedings of the eighth annual symposium on Computational geometry, p.212-221, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142720]
	12	Scott A. Mitchell , Stephen A. Vavasis, Quality Mesh Generation in Higher Dimensions, SIAM Journal on Computing, v.29 n.4, p.1334-1370, Feb. 2000 to March 2000 [doi>10.1137/S0097539796314124]
	13	Jim Ruppert, A Delaunay refinement algorithm for quality 2-dimensional mesh generation, Journal of Algorithms, v.18 n.3, p.548-585, May 1995
	14	Jonathan Richard Shewehuk. Delaunay Refinement Mesh Generation. Ph.D. thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, May 1997. Available as Teehnieal Report CMU-CS-97-137.
	15	Jonathan Richard Shewchuk, A condition guaranteeing the existence of higher-dimensional constrained Delaunay triangulations, Proceedings of the fourteenth annual symposium on Computational geometry, p.76-85, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276893]
	16	David E Watson. Computing the n-dimensional Delaunay Tessellation with Application to Voronoi Polytopes. Computer Journal 24(2):167-172, 1981.
	17	Nigel P. Weatherill. Delaunay Triangulation in Computa. tional Fluid Dynamics. Computers and Mathematics with Applications 24(5/6):129-150, September 1992.

CITED BY 51

	Herbert Edelsbrunner , Xiang-Yang Li , Gary Miller , Andreas Stathopoulos , Dafna Talmor , Shang-Hua Teng , Alper Üngör , Noel Walkington, Smoothing and cleaning up slivers, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.273-277, May 21-23, 2000, Portland, Oregon, United States
	Démian Nave , Nikos Chrisochoides , L. Paul Chew, Guaranteed: quality parallel delaunay refinement for restricted polyhedral domains, Proceedings of the eighteenth annual symposium on Computational geometry, p.135-144, June 05-07, 2002, Barcelona, Spain
	Xiang-Yang Li , Shang-Hua Teng, Generating well-shaped Delaunay meshed in 3D, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.28-37, January 07-09, 2001, Washington, D.C., United States
	David Cohen-Steiner , Éric Colin de Verdière , Mariette Yvinec, Conforming Delaunay triangulations in 3D, Proceedings of the eighteenth annual symposium on Computational geometry, p.199-208, June 05-07, 2002, Barcelona, Spain
	Jeff Erickson, Nice point sets can have nasty Delaunay triangulations, Proceedings of the seventeenth annual symposium on Computational geometry, p.96-105, June 2001, Medford, Massachusetts, United States
	Siu-Wing Cheng , Tamal K. Dey, Quality meshing with weighted Delaunay refinement, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.137-146, January 06-08, 2002, San Francisco, California
	Herbert Edelsbrunner , Damrong Guoy, Sink-insertion for mesh improvement, Proceedings of the seventeenth annual symposium on Computational geometry, p.115-123, June 2001, Medford, Massachusetts, United States
	Jeff Erickson, Dense point sets have sparse Delaunay triangulations: or "…but not too nasty", Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.125-134, January 06-08, 2002, San Francisco, California
	Jonathan Richard Shewchuk, Mesh generation for domains with small angles, Proceedings of the sixteenth annual symposium on Computational geometry, p.1-10, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Barbara Cutler , Julie Dorsey , Leonard McMillan , Matthias Müller , Robert Jagnow, A procedural approach to authoring solid models, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
	Siu-Wing Cheng , Tamal K. Dey , Herbert Edelsbrunner , Michael A. Facello , Shang-Hua Teng, Silver exudation, Journal of the ACM (JACM), v.47 n.5, p.883-904, Sept. 2000
	Michael Murphy , David M. Mount , Carl W. Gable, A point-placement strategy for conforming Delaunay tetrahedralization, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.67-74, January 09-11, 2000, San Francisco, California, United States
	Lusine Yepremyan , James E. Falk, Delaunay partitions in Rⁿ applied to non-convex programs and vertex/facet enumeration problems, Computers and Operations Research, v.32 n.4, p.793-812, April 2005
	Siu-Wing Cheng , Sheung-Hung Poon, Graded conforming Delaunay tetrahedralization with bounded radius-edge ratio, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Xiang-Yang Li, Generating well-shaped d-dimensional Delaunay meshes, Theoretical Computer Science, v.296 n.1, p.145-165, 4 March 2003
	Pierre Alliez , David Cohen-Steiner , Mariette Yvinec , Mathieu Desbrun, Variational tetrahedral meshing, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
	Qiang Wu , Hua Xu, An approach to computer modeling and visualization of geological faults in 3D, Computers & Geosciences, v.29 n.4, p.503-509, May 2003
	Siu-Wing Cheng , Tamal K. Dey , Herbert Edelsbrunner , Michael A. Facello , Shang-Hua Teng, Sliver exudation, Proceedings of the fifteenth annual symposium on Computational geometry, p.1-13, June 13-16, 1999, Miami Beach, Florida, United States
	Danny Z. Chen , Xiaobo Hu , Yingping Huang , Yifan Li , Jinhui Xu, Algorithms for congruent sphere packing and applications, Proceedings of the seventeenth annual symposium on Computational geometry, p.212-221, June 2001, Medford, Massachusetts, United States
	Jeff Erickson, Local polyhedra and geometric graphs, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Boting Yang , Cao An Wang, Detecting tetrahedralizations of a set of line segments, Journal of Algorithms, v.53 n.1, p.1-35, October 2004
	Siu-Wing Cheng , Tamal K. Dey , Edgar A. Ramos , Tathagata Ray, Sampling and meshing a surface with guaranteed topology and geometry, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Siu-Wing Cheng , Tamal K. Dey , Edgar A. Ramos , Tathagata Ray, Quality meshing for polyhedra with small angles, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	David Cohen-Steiner , Éric Colin de Verdière , Mariette Yvinec, Conforming delaunay triangulations in 3D, Computational Geometry: Theory and Applications, v.28 n.2-3, p.217-233, June 2004
	Démian Nave , Nikos Chrisochoides , L. Paul Chew, Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains, Computational Geometry: Theory and Applications, v.28 n.2-3, p.191-215, June 2004
	Richard Shewchuk, Star splaying: an algorithm for repairing delaunay triangulations and convex hulls, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Emanuele Danovaro , Leila De Floriani , Paola Magillo , Enrico Puppo, Representing vertex-based simplicial multi-complexes, Digital and image geometry: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2001
	Jeff Erickson, Local polyhedra and geometric graphs, Computational Geometry: Theory and Applications, v.31 n.1-2, p.101-125, May 2005
	Kun Zhou , Jin Huang , John Snyder , Xinguo Liu , Hujun Bao , Baining Guo , Heung-Yeung Shum, Large mesh deformation using the volumetric graph Laplacian, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
	Francois Labelle , Jonathan Richard Shewchuk, Anisotropic voronoi diagrams and guaranteed-quality anisotropic mesh generation, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	François Labelle, Sliver removal by lattice refinement, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Siu-Wing Cheng, On the sizes of Delaunay meshes, Computational Geometry: Theory and Applications, v.33 n.3, p.130-138, February 2006
	Siu-Wing Cheng , Tamal K. Dey , Edgar A. Ramos, Delaunay refinement for piecewise smooth complexes, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1096-1105, January 07-09, 2007, New Orleans, Louisiana
	Pierre Alliez , David Cohen-Steiner , Mariette Yvinec , Mathieu Desbrun, Variational tetrahedral meshing, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California
	Qiang Du , Desheng Wang, Recent progress in robust and quality Delaunay mesh generation, Journal of Computational and Applied Mathematics, v.195 n.1, p.8-23, 15 October 2006
	Martin Isenburg , Yuanxin Liu , Jonathan Shewchuk , Jack Snoeyink, Streaming computation of Delaunay triangulations, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
	Kokichi Sugihara, Sliver-free perturbation for the Delaunay tetrahedrization, Computer-Aided Design, v.39 n.2, p.87-94, February, 2007
	Joshua Podolak , Szymon Rusinkiewicz, Atomic volumes for mesh completion, Proceedings of the third Eurographics symposium on Geometry processing, July 04-06, 2005, Vienna, Austria
	Stratos Papadomanolakis , Anastassia Ailamaki , Julio C. Lopez , Tiankai Tu , David R. O'Hallaron , Gerd Heber, Efficient query processing on unstructured tetrahedral meshes, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	Andrey N. Chernikov , Nikos P. Chrisochoides, Three-dimensional delaunay refinement for multi-core processors, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece
	Tamal K. Dey , Joshua A. Levine, Delpsc: a delaunay mesher for piecewise smooth complexes, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Jean-Daniel Boissonnat , Camille Wormser , Mariette Yvinec, Locally uniform anisotropic meshing, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Sheng-Hui Liao , Ruo-Feng Tong , Jin-Xiang Dong, Anisotropic finite element modeling for patient-specific mandible, Computer Methods and Programs in Biomedicine, v.88 n.3, p.197-209, December, 2007
	Costin-Anton Boiangiu , Dan-Cristian Cananau , Andrei-Cristian Spataru, Modern approaches in detection of page separators for image clustering, WSEAS Transactions on Computers, v.7 n.7, p.1071-1080, July 2008
	Costin-Anton Boiangiu , Dan-Cristian Cananau , Spataru Andrei, Detection of arbitrary-form separators based on filtered delaunay triangulation, Proceedings of the 9th WSEAS International Conference on International Conference on Automation and Information, p.442-445, June 24-26, 2008, Bucharest, Romania
	Jaeil Choi , Andrzej Szymczak, Fitting solid meshes to animated surfaces using linear elasticity, ACM Transactions on Graphics (TOG), v.28 n.1, p.1-10, January 2009
	Benoît Hudson , Gary L. Miller , Todd Phillips , Don Sheehy, Size complexity of volume meshes vs. surface meshes, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1041-1047, January 04-06, 2009, New York, New York
	Vicente H.F. Batista , David L. Millman , Sylvain Pion , Johannes Singler, Parallel geometric algorithms for multi-core computers, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Celine Paloc , Alessandro Faraci , Fernando Bello, Online Remeshing for Soft Tissue Simulation in Surgical Training, IEEE Computer Graphics and Applications, v.26 n.6, p.24-34, November 2006
	Laurent Rineau , Mariette Yvinec, A generic software design for Delaunay refinement meshing, Computational Geometry: Theory and Applications, v.38 n.1-2, p.100-110, September, 2007
	Chuan-Chu Kuo , Hong-Tzong Yau, A New Combinatorial Approach to Surface Reconstruction with Sharp Features, IEEE Transactions on Visualization and Computer Graphics, v.12 n.1, p.73-82, January 2006