CGAL: the computational geometry algorithms library

ABSTRACT

This course provides an overview of CGAL geometric algorithms and data structures. We start with a presentation the objectives and scope of the CGAL open source project. The three next parts cover SIGGRAPH topics: (1) CGAL for point set processing, including denoising, outlier removal, smoothing, resampling, curvature estimation, shape detection and surface reconstruction, (2) CGAL for polygon mesh processing, including Boolean operations, deformation, skeletonization, segmentation, hole filling, isotropic remeshing, simplification, and (3) CGAL for mesh generation, including surface and volume mesh generation, from either 3D images, implicit functions or surface meshes.

References

1. http://www.cgal.org/
2. Ruwen Schnabel, Roland Wahl, and Reinhard Klein. Efficient ransac for point-cloud shape detection. In Computer graphics forum, volume 26, pages 214--226. Wiley Online Library, 2007.
3. David Cohen-Steiner and Tran Kai Frank Da. A greedy Delaunay-based surface reconstruction algorithm. The Visual Computer, 20:4--16, 2004.
4. Olga Sorkine and Marc Alexa. As-rigid-as-possible surface modeling. In ACM International Conference Proceeding Series, volume 257, pages 109--116. Citeseer, 2007.
5. Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schröder. A simple geometric model for elastic deformations. In ACM SIGGRAPH 2010 papers, SIGGRAPH '10, pages 38:1--38:6. ACM, 2010.
6. Andrea Tagliasacchi, Ibraheem Alhashim, Matt Olson, and Hao Zhang. Mean curvature skeletons. Computer Graphics Forum (Proceedings of the Symposium on Geometry Processing), 31(5):1735--1744, 2012.
7. L. Shapira, A. Shamir, and D. Cohen-Or. Consistent mesh partitioning and skeletonisation using the shape diameter function. The Visual Computer, 24(4):249--259, 2008.
8. M. Botsch and L. Kobbelt. A remeshing approach to multiresolution modeling. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, pages 185--192. ACM, 2004.
9. Shi-Qing Xin and Guo-Jin Wang. Improving chen and han's algorithm on the discrete geodesic problem. ACM Trans. Graph., 28(4):104:1--104:8, September 2009.
10. J. Chen and Y. Han. Shortest paths on a polyhedron. Internat. J. Comput. Geom. Appl., 6:127--144, 1996.
11. Joseph S. B. Mitchell, D. M. Mount, and C. H. Papadimitriou. The discrete geodesic problem. SIAM J. Comput., 16:647--668, 1987.
12. Jonathan R. Shewchuk. Tetrahedral mesh generation by Delaunay refinement. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 86--95, 1998.
13. Pierre Alliez, David Cohen-Steiner, Mariette Yvinec, and Mathieu Desbrun. Variational tetrahedral meshing. ACM Transactions on Graphics, 24:617--625, 2005. SIGGRAPH '2005 Conference Proceedings.
14. Julie Digne, Jean-Michel Morel, Charyar-Mehdi Souzani, and Claire Lartigue. Scale space meshing of raw data point sets. Computer Graphics Forum, 30(6):1630--1642, 2011.
15. Michael Kazhdan, M. Bolitho, and Hugues Hoppe. Poisson Surface Reconstruction. In Symp. on Geometry Processing, pages 61--70, 2006.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling