Gabriel-constrained Parametric Surface Triangulation

Authors: Oscar E. Ruiz, Carlos Cadavid, Juan G. Lalinde, Ricardo Serrano, Guillermo Peris-Fajarnes

Abstract:

The Boundary Representation of a 3D manifold contains FACES (connected subsets of a parametric surface S : R2 -! R3). In many science and engineering applications it is cumbersome and algebraically difficult to deal with the polynomial set and constraints (LOOPs) representing the FACE. Because of this reason, a Piecewise Linear (PL) approximation of the FACE is needed, which is usually represented in terms of triangles (i.e. 2-simplices). Solving the problem of FACE triangulation requires producing quality triangles which are: (i) independent of the arguments of S, (ii) sensitive to the local curvatures, and (iii) compliant with the boundaries of the FACE and (iv) topologically compatible with the triangles of the neighboring FACEs. In the existing literature there are no guarantees for the point (iii). This article contributes to the topic of triangulations conforming to the boundaries of the FACE by applying the concept of parameterindependent Gabriel complex, which improves the correctness of the triangulation regarding aspects (iii) and (iv). In addition, the article applies the geometric concept of tangent ball to a surface at a point to address points (i) and (ii). Additional research is needed in algorithms that (i) take advantage of the concepts presented in the heuristic algorithm proposed and (ii) can be proved correct.

Keywords: surface triangulation, conforming triangulation, surfacesampling, Gabriel complex.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1056488

References:

[1] K. Abe, J. Bisceglio, T. J. Peters, A. C. Russell, and T. Sakkalis. Computational topology for reconstruction of surfaces with boundary: Integrating experiments and theory. In SMI -05: Proceedings of the International Conference on Shape Modeling and Applications 2005, pages 290-299, Washington, DC, USA, 2005. IEEE Computer Society.
[2] Udo Adamy, Joachim Giesen, and Matthias John. New techniques for topologically correct surface reconstruction. In VIS -00: Proceedings of the conference on Visualization -00, pages 373-380, Los Alamitos, CA, USA, 2000. IEEE Computer Society Press.
[3] N. Amenta, M. Bern, and D. Eppstein. The crust and the betaskeleton: Combinatorial curve reconstruction. Graphical models and image processing: GMIP, 60(2):125-, 1998.
[4] Nina Amenta and Marshall Bern. Surface reconstruction by voronoi filtering. In SCG -98: Proceedings of the fourteenth annual symposium on Computational geometry, pages 39-48, New York, NY, USA, 1998. ACM.
[5] Dominique Attali, Jean-Daniel Boissonnat, and Andr'e Lieutier. Complexity of the delaunay triangulation of points on surfaces the smooth case. In SCG -03: Proceedings of the nineteenth annual symposium on Computational geometry, pages 201-210, New York, NY, USA, 2003. ACM.
[6] J-D Boissonnat and S. Oudot. An effective condition for sampling surfaces with guarantees. In SM -04: Proceedings of the ninth ACM symposium on Solid modeling and applications, pages 101-112, Airela- Ville, Switzerland, Switzerland, 2004. Eurographics Association.
[7] Jean-Daniel Boissonnat and Steve Oudot. Provably good sampling and meshing of lipschitz surfaces. In SCG -06: Proceedings of the twentysecond annual symposium on Computational geometry, pages 337-346, New York, NY, USA, 2006. ACM.
[8] Manfredo Do Carmo. Differential geometry of curves and surfaces, pages 1-168. Prentice Hall, 1976. ISBN: 0-13-212589-7.
[9] Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos, and Tathagata Ray. Sampling and meshing a surface with guaranteed topology and geometry. In SCG -04: Proceedings of the twentieth annual symposium on Computational geometry, pages 280-289, New York, NY, USA, 2004. ACM.
[10] L. Paul Chew. Guaranteed-quality mesh generation for curved surfaces. In SCG -93: Proceedings of the ninth annual symposium on Computational geometry, pages 274-280, New York, NY, USA, 1993. ACM.
[11] Museo del Oro Bogot'a DC. Pre-columbian fish. http://www.banrep.org/museo/eng/home4.htm.
[12] Herbert Edelsbrunner and Nimish R. Shah. Triangulating topological spaces. In SCG -94: Proceedings of the tenth annual symposium on Computational geometry, pages 285-292, New York, NY, USA, 1994. ACM.
[13] Rosalinda Ferrandes. Pump carter. http://shapes.aimatshape.net/viewgroup.php?id=919.
[14] Rosalinda Ferrandes. Stub axle. http://shapes.aimatshape.net/viewgroup.php?id=917.
[15] Greg Leibon and David Letscher. Delaunay triangulations and voronoi diagrams for riemannian manifolds. In SCG -00: Proceedings of the sixteenth annual symposium on Computational geometry, pages 341- 349, New York, NY, USA, 2000. ACM.
[16] A' ngel Montesdeoca. Apuntes de geometr'─▒a diferencial de curvas y superficies. Santa Cruz de Tenerife, 1996. ISBN: 84-8309-026-0.
[17] Oscar E. Ruiz, John Congote, Carlos Cadavid, Juan G. Lalinde, and Guillermo Peris. Parameter-independent, curvature-sensitive sprinkle and star algorithms for surface triangulation. Submitted to the Computer- Aided Design Journal at Elsevier editorial.
[18] Oscar E. Ruiz and Sebastian Pe˜na. Aspect ratio- and size-controlled patterned triangulations of parametric surfaces. In Ninth IASTED Intl. Conf. Computer Graphics and Imaging, February 13-15 2007.