Two data structures for building tetrahedralizations


A polyhedral decomposition can be unambiguously described as the collection of four primitive elements (i.e., polyhedra, facets, edges, and vertices) plus their mutual adjacency relations. We consider here the problem of representing a specific kind of polyhedral decomposition, i.e., a tetrahedralization. We describe two different representations for a tetrahedralization. The first one can only model polyhedral decompositions with tetrahedral cells, while the second one is suitable for describing any partition of a volume into polyhedral cells with triangular facets. We present two sets of primitive Euler operators, which build and manipulate such representations while maintaining their topological integrity. The use of such operators is demonstrated in connection with two algorithms for building a Delaunay tetrahedralization, which show the different hedralization, which show the different uses of the two representations.

The Visual Computer