On converting sets of tetrahedra to combinatorial and PL manifolds. (English) Zbl 1205.65065
Summary: We investigate the problem of removing singularities from a non-manifold tetrahedral mesh so as to convert it to a more exploitable manifold representation. Given the twofold combinatorial and geometrical nature of a 3D simplicial complex, we propose two conversion algorithms that, depending on the targeted application, modify either its connectivity only or both its connectivity and its geometry. In the first case, the tetrahedral mesh is converted to a combinatorial 3-manifold, whereas in the second case it becomes a piecewise linear (PL) 3-manifold. For both the approaches, the conversion takes place while using only local modifications around the singularities. We outline sufficient conditions on the mesh to guarantee the feasibility of the approaches and we show how singularities can be both identified and removed according to the configuration of their neighborhoods. Furthermore, besides adapting and extending surface-based approaches to a specific class of full-dimensional simplicial complexes in 3D, we show that our algorithms can be implemented using a flexible data structure for manifold tetrahedral meshes which is suitable for general applications. In order to exclude pathological configurations while providing sound guarantees, the input mesh is required to be a sub-complex of a combinatorial ball; this makes it possible to assume that all the singularities are part of the mesh boundary.
Software:
ReMESHReferences:
| [1] | Alliez, P.; Cohen-Steiner, D.; Yvinec, M.; Desbrun, M., Variational tetrahedral meshing, ACM Transactions on Graphics, 24, 3, 617-625 (2005) |
| [2] | Attene, M., 2004. Surface remeshing and applications. PhD thesis, Genoa University; Attene, M., 2004. Surface remeshing and applications. PhD thesis, Genoa University |
| [3] | Attene, M.; Falcidieno, B., ReMESH: An interactive environment to edit and repair triangle meshes, (Proc. of Shape Modelling International (SMI’06) (2006), IEEE Computer Society Press), 271-276 |
| [4] | Attene, M., Robbiano, F., Spagnuolo, M., Falcidieno, B., 2007a. Semantic annotation of 3D surface meshes based on feature characterization. In: SAMT’07 Procs. In: Lecture Notes in Computer Science, vol. 4816, pp. 126-139; Attene, M., Robbiano, F., Spagnuolo, M., Falcidieno, B., 2007a. Semantic annotation of 3D surface meshes based on feature characterization. In: SAMT’07 Procs. In: Lecture Notes in Computer Science, vol. 4816, pp. 126-139 |
| [5] | Attene, M.; Ferri, M.; Giorgi, D., Combinatorial 3-manifolds from sets of tetrahedra, (Cyberworlds ’07 Proceedings, Spec. Sess. on NASAGEM Workshop (2007), IEEE Computer Society Press), 367-375 |
| [6] | Battiato, S., Bosco, C., Farinella, G., Impoco, G., 2006. 3D CT segmentation for clinical evaluation of knee prosthesis operations. In: Proc. of 4th Eurographics Conference - Italian Chapter, February 2006; Battiato, S., Bosco, C., Farinella, G., Impoco, G., 2006. 3D CT segmentation for clinical evaluation of knee prosthesis operations. In: Proc. of 4th Eurographics Conference - Italian Chapter, February 2006 |
| [7] | Baumgart, B.G., 1975, A polyhedron representation for computer vision. In: Proc. of National Computer Conference, pp. 589-596; Baumgart, B.G., 1975, A polyhedron representation for computer vision. In: Proc. of National Computer Conference, pp. 589-596 |
| [8] | Botsch, M., Kobbelt, L., 2001. A robust procedure to eliminate degenerate faces from triangle meshes. In: Proc. of Vision, Modeling and Visualization, pp. 283-290; Botsch, M., Kobbelt, L., 2001. A robust procedure to eliminate degenerate faces from triangle meshes. In: Proc. of Vision, Modeling and Visualization, pp. 283-290 |
| [9] | Botsch, M., Pauly, M., Kobbelt, L., Alliez, P., Levy, B., Bischoff, S., Rossl, C., 2007. Geometric modeling based on polygonal meshes. In: SIGGRAPH Course Notes; Botsch, M., Pauly, M., Kobbelt, L., Alliez, P., Levy, B., Bischoff, S., Rossl, C., 2007. Geometric modeling based on polygonal meshes. In: SIGGRAPH Course Notes |
| [10] | Brisson, E., Representing geometric structures in \(d\) dimensions: Topology and order, (Proc. of 5th ACM Symp. on Computational Geometry. Proc. of 5th ACM Symp. on Computational Geometry, New York, June 1989 (1989), ACM Press), 218-227 |
| [11] | Bruzzone, E.; Floriani, L. D., Two data structures for building tetrahedralizations, The Visual Computer, 6, 5, 266-283 (1990) |
| [12] | Campagna, S.; Kobbelt, L.; Seidel, H. P., Directed edges – a scalable representation for triangle meshes, ACM Journal of Graphics Tools, 3, 4 (1998) · Zbl 0959.65043 |
| [13] | Catalano, C. E.; Camossi, E.; Ferrandes, R.; Cheutet, V.; Sevilmis, N., A product design ontology for enhancing shape processing in design workflows, Journal of Intelligent Manufacturing (2008), Special issue on Knowledge Discovery and Management in Engineering Design |
| [14] | (De Floriani, L.; Spagnuolo, M., Shape Analysis and Structuring. Shape Analysis and Structuring, Mathematics and Visualization Series (2008), Springer) · Zbl 1125.68126 |
| [15] | Dobkin, D.; Laszlo, M., Primitives for the manipulation of three-dimensional subdivisions, Algorithmica, 5, 4, 3-32 (1989) · Zbl 0664.68023 |
| [16] | Falcidieno, B.; Ratto, O., 2-manifold cell decomposition of r-sets, Computer Graphics Forum, 11, 3, 391-404 (1992) |
| [17] | Floriani, L. D.; Hui, A., Data structures for simplicial complexes: An analysis and a comparison, (Third Eurographics Symposium on Geometry Processing. Third Eurographics Symposium on Geometry Processing, July 2005 (2005), Eurographics Association) |
| [18] | Floriani, L. D.; Mesmoudi, M. M.; Morando, F.; Puppo, E., Decomposing non-manifold objects in arbitrary dimensions, Graphical Models, 65, 2-22 (2003) · Zbl 1039.68150 |
| [19] | Forest, C.; Delingette, H.; Ayache, N., Removing tetrahedra from manifold tetrahedralisation: Application to real-time surgical simulation, Medical Image Analysis, 9, 113-122 (2005) |
| [20] | Glaser, L. C., Geometrical Combinatorial Topology, vol. 1 (1970), Van Nostrand Reinhold: Van Nostrand Reinhold New York · Zbl 0212.55603 |
| [21] | Glaser, L. C., A proof of the most general polyhedral Schoenflies conjecture possible, Pacific Journal of Mathematics, 38, 2, 401-417 (1971) · Zbl 0194.55604 |
| [22] | Gueziec, A.; Taubin, G.; Lazarus, F.; Horn, B., Cutting stitching: Converting sets of polygons to manifold surfaces, IEEE Trans. on Visualization and Computer Graphics, 7, 2, 136-151 (2001) |
| [23] | Guibas, L.; Stolfi, J., Primitives for the manipulation of general subdivisions and computation of Voronoi diagrams, ACM Transactions on Graphics, 4, 2, 74-123 (1985) · Zbl 0586.68059 |
| [24] | Gursoz, E.; Choi, Y.; Prinz, F., Vertex-based representation of non-manifold boundaries, (Wozny, M. J.; Turner, J.; Preiss, K., Geometric Modeling for Product Engineering (1990), Elsevier: Elsevier North Holland), 107-130 |
| [25] | Hartmann, U., Kruggel, F., 1998. A fast algorithm for generating large tetrahedral 3D finite element meshes from magnetic resonance tomograms. In: Proc. of the IEEE Workshop on Biomedical Image Analysis, p. 184; Hartmann, U., Kruggel, F., 1998. A fast algorithm for generating large tetrahedral 3D finite element meshes from magnetic resonance tomograms. In: Proc. of the IEEE Workshop on Biomedical Image Analysis, p. 184 |
| [26] | Hui, A.; Vaclavik, L.; Floriani, L. D., A decomposition-based representation for 3D simplicial complexes, (Fourth Eurographics Symposium on Geometry Processing. Fourth Eurographics Symposium on Geometry Processing, June 2006 (2006), Eurographics Association) |
| [27] | Lee, S.; Lee, K., Partial entity structure: A fast and compact non-manifold boundary representation based on partial topological entities, (Proc. of 6th ACM Symp. on Solid Modeling and Applications (2001), ACM: ACM New York), 159-170 |
| [28] | Loop, C., 1987. Smooth subdivision surfaces based on triangles. MsC Thesis, University of Utah, USA; Loop, C., 1987. Smooth subdivision surfaces based on triangles. MsC Thesis, University of Utah, USA |
| [29] | Lopes, H.; Tavares, G., Structural operators for modeling 3-manifolds, (Proc. of 4th ACM Symp. on Solid Modeling and Applications. Proc. of 4th ACM Symp. on Solid Modeling and Applications, New York, May 1997 (1997), ACM), 45-60 |
| [30] | Luo, Y.; Lukacs, G., A boundary representation of form features and non-manifold solid objects, (Proc. of 1st ACM Symp. on Solid Modeling and Applications. Proc. of 1st ACM Symp. on Solid Modeling and Applications, New York, June 1991 (1991), ACM), 45-60 |
| [31] | Mäntylä, M., Introduction to Solid Modeling (1988), Computer Science Press: Computer Science Press Rockville, Maryland, USA |
| [32] | Paoluzzi, A.; Bernardini, F.; Cattani, C.; Ferrucci, V., Dimension-independent modeling with simplicial complexes, ACM Transactions on Graphics, 12, 1, 56-102 (1993) · Zbl 0770.68114 |
| [33] | Rossignac, J., 1997. Structured topological complexes: A feature-based API for non-manifold topologies. In: Proc. of the ACM Symposium on Solid Modeling, pp. 1-9; Rossignac, J., 1997. Structured topological complexes: A feature-based API for non-manifold topologies. In: Proc. of the ACM Symposium on Solid Modeling, pp. 1-9 |
| [34] | Rossignac, J.; Cardoze, D., Matchmaker: Manifold breps for non-manifold r-sets, (Proc. of 5th ACM Symposium on Solid Modeling and Applications. Proc. of 5th ACM Symposium on Solid Modeling and Applications, New York (1999), ACM Press), 31-41 |
| [35] | Rossignac, J., O’Connor, M., 1989. SGC: A dimension-independent model for pointsets with internal structures and incomplete boundaries. In: Proc. of the IFIP Workshop on CAD/CAM, pp. 145-180; Rossignac, J., O’Connor, M., 1989. SGC: A dimension-independent model for pointsets with internal structures and incomplete boundaries. In: Proc. of the IFIP Workshop on CAD/CAM, pp. 145-180 |
| [36] | Rourke, C. P.; Sanderson, B. J., Introduction to Piecewise Linear Topology, vol. 1 (1972), Springer-Verlag: Springer-Verlag Berlin, Heidelberg, New York · Zbl 0254.57010 |
| [37] | Schönhardt, E., Über die Zerlegung von Dreieckspolyedern in Tetraeder, Math. Annalen, 89, 309-312 (1927) · JFM 53.0576.01 |
| [38] | Si, H., Gaertner, K., 2005. Meshing piecewise linear complexes by constrained Delaunay tetrahedralizations. In: Proceedings of the 14th International Meshing Roundtable, pp. 147-163; Si, H., Gaertner, K., 2005. Meshing piecewise linear complexes by constrained Delaunay tetrahedralizations. In: Proceedings of the 14th International Meshing Roundtable, pp. 147-163 |
| [39] | Zhuang, Y.; Canny, J., Real-time physically realistic simulation of global deformation, (SIGGRAPH99 Sketches and Applications. SIGGRAPH99 Sketches and Applications, New York, August 1999 (1999), ACM Press) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
