Update Operations on 3D Simplicial Decompositions of Non-manifold Objects

G. Elber, N. Patrikalakis, P. Brunet (Editors)

Update operations on 3D simplicial decompositions of non-manifold objects

Leila De Floriani and Annie Hui

Department of Computer and Information Sciences, University of Genova, Via Dodecaneso, 35 - 16146 Genova (Italy).

Department of Computer Science, University of Maryland, College Park, MD 20742 (USA).

Email: [email protected], [email protected]

Abstract

We address the problem of updating non-manifold mixed-dimensional objects, described by three-dimensional simplicial com- plexes embedded in 3D Euclidean space. We consider two local update operations, edge collapse and vertex split, which are the most common operations performed for simplifying a simplicial complex. We examine the effect of such operations on a 3D simplicial complex, and we describe algorithms for edge collapse and vertex split on a compact representation of a 3D simplicial complex, that we call theNon-Manifold Indexed data structure with Adjacencies (NMIA). We also discuss how to encode the information needed for performing a vertex split and an edge collapse on a 3D simplicial complex. The encoding of such information together with the algorithms for updating the NMIA data structure form the basis for defining progressive as well as multi-resolution representations for objects described by 3D simplicial complexes and for extracting variable-resolution object descriptions.

Categories and Subject Descriptors(according to ACM CCS): I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling -Curve, surface, solid and object representations

1. Introduction

We consider the problem of locally updating a three-dimensional simplicial complex describing a non-manifold object by perform- ing edge collapses and vertex splits. Anedge collapseapplied to a simplicial complex contracts an edgeeof the complex into a new vertexv, or into one of the extreme vertices ofe.Vertex splitis the inverse of edge collapse: it replaces a vertexvof a complex with an edgee. Edge collapse and vertex split are common operations performed for coarsening or refining a complex in simplification algorithms [10,25].

The ultimate goal of our work is to develop a continuous multi- resolution representation for non-manifold objects described by three-dimensional simplicial decompositions, i.e., by combinations of tetrahedral meshes with lower dimensional entities described by chains of edges, or by triangle meshes. In order to develop a multi-resolution representation, we need a data structure for en- coding 3D simplicial complexes, that can be used to describe the variable-resolution complexes extracted from a multi-resolution model. Such a data structure must be compact, and must support efficient navigation within the complex through adjacencies, as re- quired by common geometric modeling operations. Since most ob- jects encountered in the applications contain a relatively small num- ber of non-manifold singularities, the data structure should scale to

the manifold case with a small overhead. Moreover, we need algo- rithms to perform edge collapse and vertex split on such represen- tation as well as a compact way of encoding vertex splits and edge collapses. This will be the basis for designing a data structure for representing the multi-resolution model.

In [5], we have defined a model for non-manifold objects de- scribed by simplicial complexes, called a Non-Manifold Multi- Tessellation (NMT), and we have described an implementation of the NMT for the case of two-dimensional complexes. Here, we plan to develop some basic tools for designing and implementing an NMT in the three-dimensional case.

In [4], we have defined a compact data structure, called aNon- Manifold Indexed data structure with Adjacencies (NMIA), for de- scribing three-dimensional simplicial complexes embedded in the 3D Euclidean space. The NMIA data structure encodes the vertices and the top simplexes of the complex plus a restricted subset of topological relations, and it supports retrieval of incidence and ad- jacency relations among the entities in the complex in time linear in the number of entities involved in the relations. Here, we briefly de- scribe the entities and relations defining the NMIA data structure, and an improved implementation of such structure, which exhibits an even better scalability to the manifold case, i.e., a very low over- head cost with respect to a similar data structure, the indexed data

c

The Eurographics Association 2004.

structure with adjacencies, commonly used to represent manifold simplicial meshes.

In [10], conditions are studied under which an edge collapse can be performed on a complex without changing its topological type, which have been applied in simplification algorithms for 3D sim- plicial complexes with a manifold domain to avoid creating non- manifold situations [2]. Here, we allow edge collapses and vertex splits to change the topological type of the domain of the simplicial complex as well as to create, or remove, lower-dimensional entities, such as wire edges and dangling faces.

In [25], Popovic and Hoppe describe the effect of applying a gen- eralization of edge collapse, called vertex-pair collapse, which con- sists of collapsing a pair of vertices (not necessarily connected by an edge), into a vertex, without imposing restrictions on topology changes. They sketch updating algorithms, which assume a ver- bose representation of the complex as an incidence graph, but they do not specify how topological relations in the incidence graph are affected. The storage cost of an incidence graph is three times the cost of the NMIA data structure. The restricted number of entities and relations encoded in the NMIA data structure makes updating algorithm considerably more complex.

Novel contributions of this paper are:

• a compact and scalable implementation of the NMIA data struc- ture;

• an analysis of the effect of edge collapse and of vertex split on a 3D simplicial complex;

• algorithms for performing edge collapse and vertex split on the NMIA data structure;

• an encoding of vertex split to be used as the basis for a pro- gressive volumetric representation of the object and for a data structure for encoding a 3D Non-Manifold Multi-Tessellation.

The remainder of this paper is organized as follows. In Section 2, we summarize some background notions. In Section3, we re- view some related work. In Section4, we describe the NMIA data structure, and we discuss our new implementation and its storage costs. In Section5, we analyze the effect of edge collapse and ver- tex split on a three-dimensional simplicial complex. In Section6, we describe an algorithm for performing edge collapse on a 3D simplicial complex encoded in the NMIA data structure. In Sec- tion7, we present an encoding for the vertex split operation, and we describe an algorithm for performing vertex split. In Section8, we present an instance of the NMT based on 3D simplicial com- plexes, generated through edge collapse. Finally, in Section9, we draw some conclusions and discuss future work.

2. Background

In this Section, we review some basic notions about Euclidean sim- plicial complexes in arbitrary dimensions, and the topological rela- tions among the cells of a complex.

Amanifoldobject is a subset of the Euclidean space for which the neighborhood of each internal point is homeomorphic to an open ball. Objects, that do not fulfill this property at one or more points, are callednon-manifoldobjects.

A Euclidean simplex of dimensiondis the convex hull ofd+1 linearly independent points in the 3-dimensional Euclidean space

E³, withd≤3. We simply call aEuclidean d-simplexad-simplex:

a 0-simplex is avertex; a 1-simplex anedge; a 2-simplex atrian- gle; a 3-simplex atetrahedron.dis called thedimensionofσand is denoted asdim(σ). Any Euclidean k-simplex, withk<d,σ⁰gen- erated by a setV_σ0⊆V_σof cardinalityk+1≤dis called ak-face ofσ.

A finite collectionΣof Euclidean simplexes is aEuclidean sim- plicial complexwhen (i) for each simplex σ∈Σ, all faces ofσ belong toΣ, and (ii) for each pair of simplexesσandσ⁰, either σ∩σ⁰=∅orσ∩σ⁰ is a face of bothσand σ⁰. Thedomain, or carrier, of a Euclidean simplicial complexΣembedded inE³, with d≤3, is the subset ofE³defined by the union, as point sets, of all the simplexes inΣ. We will consider in the paper three-dimensional simplicial complexes (3-complexes) embedded inE³.

Theboundary b(σ)of a simplexσis defined as the set of all faces ofσ. Similarly, theco-boundary, orstar, of a simplexσis defined as?σ={ξ∈Σ|σis a face ofξ}. Simplexesξin?σare calledco-facesofσ. In the following, we will callrestricted starof a simplexσ,?σ− {σ}, and we will denote it asst(σ). Thelinkof a simplexσ, denotedlink(σ), is the set of all faces of the co-faces ofσ, that are not incident atσ. Any simplexσsuch that?σ={σ}

is called atop simplexofΣ.

Two distinct simplexes are said to beincidentif one of them is a face of the other. Two simplexes are calledk-adjacentif they share ak-face. For example, a tetrahedron and a triangle are1-adjacentif they share an edge. Twop-simplexes, withp>0, are said to bead- jacentif they are(p−1)-adjacent. Two vertices (i.e., 0-simplexes) are calledadjacentif they are both incident at a common 1-simplex.

Anh-pathis a sequence of simplexes(σi)^k_i=0such that two suc- cessive simplexesσ_i−1,σiin the sequence areh-adjacent. Two sim- plexesσandσ⁰areh-connectedif and only if there exists anh-path (σi)^k_i=0such thatσis a face ofσ₀andσ⁰is a face ofσk. A subsetΣ⁰ of a complexΣis calledh-connectedif and only if every pair of its vertices areh-connected. Any maximalh-connected sub-complex of a complexΣis called anh-connected componentofΣ.

A complexΣ, where all top simplexes are maximal (i.e., of di- mensiond), is calledregular. A regular,(d−1)-connected com- plex in which each(d−1)-simplex is on the boundary of one or twod-simplexes is called apseudo-manifold. Note that every 3- complex embedded inE³is always a pseudo-manifold. A pseudo- manifold satisfying the additional property that all its vertices have a link combinatorially equivalent to the(d−1)-dimensional sphere is called a(combinatorial) manifold. The domain of a Euclidean simplicial complex, which is described by a combinatorial mani- fold, is a manifold inE³.

LetΣbe ad-complex and letσ∈Σbe ap-simplex, with 0≤p≤ d. For each integer valueq, 0≤q≤d, we define thetopological relation Rpq(σ)as a retrieval function that returns theq-simplexes ofΣthat are not disjoint fromσ. In particular:

• Forp<q,Rpq(σ)consists of the set of simplexes of orderqin the star ofσ.

• Forp>q,Rpq(σ)consists of the set of simplexes of orderqin the set of faces ofσ.

• Forp>0,Rpp(σ)is the set ofp-simplexes inΣthat are(p−1)- adjacent toσ.

• R₀₀(v), wherevis a vertex, consists of the set of verticeswsuch that{v,w}is a 1-simplex ofΣ.

Relation Rpq is called a boundary relation if p> q, a co- boundary relationif p<q, and anadjacency relationif p=q.

Boundary and co-boundary relations are calledincidence relations.

Boundary relations in a3-complexareR₃₀,R₃₁,R₃₂,R₂₀,R₂₁and R₁₀. Adjacency relations in a3-complexareR₃₃,R₂₂,R₁₁andR₀₀. Co-boundary relations areR₂₃,R₁₂,R₁₃,R₀₁,R₀₂andR₀₃.

3. Related Work

In this Section, we review related work on data structures for de- scribing three-dimensional simplicial and cell complexes, and on simplification algorithms for tetrahedral meshes (i.e., simplicial complexes with a manifold domain).

TheFacet-Edgedata structure [11] and theHandle-Facedata structure [23] have been proposed for three-dimensional cell com- plexes. Both describe 3-cells implicitly by encoding the 2-manifold complexes that form the boundary of such cells. The most common representation for three-dimensional simplicial complexes with a manifold domain is theIndexed data structure with Adjacencies (IA), which directly extends to arbitrary dimension, being called winged representation[24]. In ad-dimensional IA data structure, vertices and top simplexes are encoded together withR_d0andRdd

relations. The IA data structure can be extended by encoding only one incidentd-simplex for each vertexv, thus allowing efficient navigation around a vertex. In three dimensions, the storage cost of the indexed data structure with adjacencies is equal to 8nt+n integers, wherentis the number of tetrahedra andnis the number of vertices of the complex.

Dimension-independent data structures have been proposed for d-dimensional manifold complexes, which include theCell Tuple [1], and then-G-maps[22] for cellular complexes. When used to describe simplicial complexes, the storage cost of such data struc- tures is much higher than that of the IA data structure, for a fac- tor that grows combinatorially with the dimension of the complex (see [8]). The representation domain of all such data structures is larger than that of d-manifolds: the IA data structure can de- scribe Euclidean pseudo-manifolds embedded in the Euclideand- dimensional space, while the other two can describe a sub-class of pseudo-manifolds introduced in [22], and calledcellular quasi- manifolds. Selective Geometric Complexes (SGCs) [27] can de- scribe non-manifold and non-regular objects through cell com- plexes whose cells can be even open, or not simply connected. In SGCs, cells and their mutual adjacencies are encoded in an inci- dence graph [12].

An alternative approach to the design of non-manifold data struc- tures consists of decomposing a non-manifold object into simpler and more manageable parts [6,9,14,18,26]. Most proposals de- compose the two-dimensional boundaries of r-sets [9,14]. The al- gorithm presented in [26] tries to minimize the number of dupli- cations introduced by the decomposition process. In [18], the idea of cutting a two-dimensional non-manifold complex into manifold pieces is exploited to develop compression algorithms. In [6], a decomposition ford-dimensional non-manifold objects described through simplicial complexes is defined, which is unique and pro- duces a description of ad-complex (not necessarily embeddable in the Euclidean space) as a combination of nearly manifold compo- nents. A dimension-independent data structure for such decompo- sition is defined in [7], which describes the components and their connectivity in a two-level representation.

Data structures for non-manifold, non-regular, three- dimensional cell complexes have been proposed for modeling non-manifold solids [19,20,30]. Experimental evaluations re- ported in [21] show that these data structures do not scale well to the manifold case, since their storage cost is between 2.1 and 4.4 times higher than that of thewinged edgedata structure. The partial entity structure [21] has been shown to require half of the space of the radial-edge structure introduced in [20]. A data structure for encoding any two-dimensional simplicial complex, called thetriangle-segment data structure, has been proposed in [5], which extends the IA data structure to deal with non-regular (1-dimensional) parts and with non-manifold adjacencies of 2-simplexes at an edge. This data structure is compact, and scales very well to the manifold case, since it requires just one byte per vertex more than the IA data structure when applied to a manifold complex.

Mesh simplification has been extensively studied for triangle meshes (see, e.g., [16] for a survey). Some techniques have been extended to the case of tetrahedral meshes. In [15], Farias et al. pro- pose a non-incremental decimation method based on vertex clus- tering. The techniques proposed in [2,17,28] are all based on edge collapse and differ in the way they control the error for produc- ing a simplified mesh. Gross and Staadt [17] present a decimation technique based on collapsing an edge to an arbitrary interior point, and propose various cost functions to drive the collapsing process.

Cignoni et al. [2] propose an algorithm based on collapsing an edge to one of its extreme vertices (calledhalf-edge collapse), in which the simplification process is driven by a combination of the ge- ometric error introduced in simplifying the shape of the domain and of the error introduced in approximating the scalar field with fewer points. In [29], Véron and Léon describe how to perform sim- plification on a two-dimensional simplicial complex embedded in the three-dimensional Euclidean space. The complex is simplified through vertex removal as the primary operation, and then through edge collapse and face removal as secondary operations.

Popovic and Hoppe [25] consider general arbitrary-dimensional simplicial complexes, and describe how to perform vertex-pair col- lapse and its inverse by considering only how the entities in the complex are updated. In [10], a set of necessary and sufficient con- ditions to preserve the topological type of a simplicial complex when simplified through edge collapse are studied.

4. The NMIA Data Structure

The NMIA data structure describes 3D simplicial complexes con- taining one- and two-dimensional top simplexes, that we callwire edgesanddangling faces, respectively, (see Figure1(a)), in order to represent parts of different dimensionalities in the object. Also, it describes situations in which the restricted star of an edge, or of a vertex, consists of more than one connected component. At such edges and vertices, the manifold condition does not hold (see Figures1(b) and1(c)). Since we are dealing with 3-complexes em- bedded inE³, any 2-simplex, which is not a top simplex, must be on the boundary of either one or two tetrahedra.

We call each 2-connected component in the restricted star of an edge an edge-based cluster. Edge-based clusters can be ordered around the edge, for instance, in a counter-clockwise direction. An edge-based cluster consists either of a single dangling face, or of a

t2

t1

v4

v3

v1

v2

df

we t1

t2 v₂ v1

df e

v

t df

we

(a) (b) (c)

Figure 1:(a) a wire edge, we={v₁,v₂}, and a dangling face, d f= {v₁,v₃,v₄}, (b) e={v₁,v₂}, st(e)has two connected components, (c) st(v)has three connected components

2-connected set of tetrahedra sharing edgee(see Figure1b). Simi- larly, each 1-connected component of the restricted star of a vertex is called avertex-based cluster. If two simplexesσIandσjbelong to the same vertex-based cluster inst(v), then there exists a 1-path passing through only those simplexes which form the cluster.

To describe edge- and vertex-based clusters, we introduce three auxiliary relations, that represent the incidence of the edge-based clusters at an edge, and of the vertex-based clusters at a vertex:

• RelationR_0,clusters(v) is a retrieval function which associates, with vertexv, one representativek-simplex for each vertex-based cluster incident atv. If dangling faces and tetrahedra belong to the same cluster, a tetrahedron is chosen.

• RelationR_2,clusters(f)is a retrieval function which associates, with each edge ei of a dangling face f, the two edge-based clusters incident atei, and following and preceding face f in a counter-clockwise order aroundei.

• RelationR_3,clusters(t) is a retrieval function which associates, with each edgeei of a tetrahedront, at most two edge-based clusters incident atei, and following and preceding tetrahedront in a counter-clockwise order aroundei.

Note that each edge-based cluster at an edgeeis represented ei- ther by a dangling face incident at e, or by a tetrahedron, if the edge-based cluster consists of just one tetrahedron, or by two tetra- hedra, i.e., the two tetrahedra that do not have 2-adjacent neighbors along one of their two faces incident ate.

4.1. Entities and Relations

In the NMIA data structure,vertices,tetrahedra, wire edgesand dangling facesare encoded as entities. Edges bounding a face or a tetrahedron, or faces bounding a tetrahedron are not explicitly represented.

The following relations are stored:

• for each tetrahedront:

– relationR₃₀(t), which associates, with each tetrahedront, its four vertices ordered according to the orientation chosen for t.

– relationR₃₃(t), which associates, with each tetrahedront, the four tetrahedra adjacent tot through a 2-simplex, (thei-th tetrahedron inR₃₃(t)is the one that does not contain thei-th vertex oft).

– relationR_3,clusters(t), as defined above, for each of the six edges of tetrahedron t (considered in an order compatible with the orientation oft).

• for each dangling facef:

– relationR₂₀(f), which associates, with each dangling facef, its three vertices (ordered according to the orientation chosen forf).

– relationR_2,clusters(f), as defined above, for each of the three edges of dangling face f(considered in an order compatible with the orientation off).

• for each wire edgee, relationR₁₀(e), which associates, with edge e, its two extreme vertices.

• for each vertexv, relationR_0,clusters(v), as defined above.

4.2. Implementation

R₃₀(t),R₂₀(f)and R₁₀(e)relations are encoded as arrays of in- dexes for each tetrahedront, dangling face f and wire edgee, re- spectively.R₃₃(t)relation is encoded as a fix-sized arrayAof four elements. If a tetrahedronthas less than four adjacent neighbors, then the last element of arrayAstores a pointer to a variable-sized arrayBencodingR_3,clusters(t). A 1-bit flag f₁(t)is used to indicate whetherR_3,clusters(t)6=∅. In the first element of arrayB, we store three flags, namely:

• a 4-bit flag, f₂(t), which indicates which 2-adjacent neighbors are present inR₃₃(t),

• a variable-sized flag,f₃(t), which indicates on which edges tetra- hedronthas 1-adjacent neighbors related throughR_3,clustersre- lation,

• a variable-sized flag, f₄(t), which indicates whether 1-adjacent neighbors inR_3,clusters(t)are tetrahedra or dangling faces.

For each dangling face f, relationR_2,clustersis encoded in a simi- lar way. Two flags, f₅(f)and f₆(f), are used to encode the posi- tions and the values of 1-adjacent neighbors related to f through R_2,clustersrelation.

For each vertexv,R_0,clusters(v)is encoded as follows:

• a 1-bit flag f(v)is used to indicate whether the restricted star of v,st(v), consists of one cluster formed by a 2-connected set of tetrahedra

• a field which contains either the index of a tetrahedron inst(v), ifst(v)is a 2-connected set of tetrahedra, or a link to a list of rep- resentative elements (tetrahedra, dangling faces, or wire edges), one for each vertex-based cluster inst(v).

4.3. Storage Cost

Letnt,nd,nw,ndenote the number of tetrahedra, dangling faces, wire edges, and vertices in a simplicial complexΣ, respectively. Let cvdenote the sum of all vertex-based clusters over all non-manifold vertices ofΣ. Letcedenote the sum of all edge-based clusters over all non-manifold edges ofΣ. Letn_bbe the number of tetrahedrat such thatR_3,clusters(t)6=∅.

The storage cost of the NMIA data structure is equal to(8nt+ 5nd+2nw+nb+2ce+2(cv−n) +n)integers +(nt+n)bits, by assuming that pointers and indexes are stored as integers on 32 bits.

In the case of manifold complexes, the cost of the NMIA data structure reduces to(8nt+n)integers +(nt+n)bits, since such complexes do not contain dangling faces (nd =0), wire edges (nw=0), non-manifold edges (ce=0), or non-manifold vertices

(cv−n=0). For tetrahedral complexes used as the decomposion of the domain of a three-dimensional scalar field, it has been shown experimentally thatnt≈6n[3]. Thus the cost of the NMIA data structure becomes 49nintegers +nbytes.

The extended IA data structure exhibits the same performances as the NMIA in the manifold case. The extended IA data structure encodes, for each tetrahedront,R₃₀(t)andR₃₃(t)relations and, for each vertexv, a link to one tetrahedron incident atv. The storage cost is, thus, equal to 8nt+nintegers, which becomes 49nintegers under the assumption thatnt≈6n. Thus, the NMIA data structure exhibits an overhead of just one byte per vertex due to the repre- sentation of non-manifold singularities.

5. Edge Collapse and Vertex Split in a 3D Simplicial Complex In this Section, we discuss the effect of applying an edge collapse or a vertex split on a three-dimensional simplicial complexΣ.

5.1. Edge Collapse

Let e={v₁,v₂} be the edge to be collapsed in a 3D simplicial complexΣ. LetΣ⁰ be the complex resulting fromΣby collapsing edgeeinto a vertexv.

Anedge collapseapplied toe={v₁,v₂}inΣconsists of replac- ing edgeewith the new vertexvinΣ⁰, collapsing all dangling faces and tetrahedra in the restricted star ofe,st(e), to wire edges and faces incident atv, respectively, and in updating all the simplexes inst(v₁)∪st(v₂), i.e., all the simplexes incident at eitherv₁orv₂.

Given ak-simplex,σ, k=1,2,3, in Σ, such thatσ∈st(e)∪ st(v₁)∪st(v₂), eitherσis incident at edgee, orσis incident at v₁orv₂but not at both. In the former case,σmust be either a dan- gling face or a tetrahedron. In the latter case, there are two possible situations. Let us assume thatσis incident atv₁, then eitherσin- tersects some other simplexσincident at the other vertex,v₂, orσ has an empty intersection with all other simplexes incident atv₂.

Therefore, the following three cases may occur:

1. σ∈st(e): in this case,σ can either be a 2-simplex or a 3- simplex.

2. σ∈st(v₁),σ6∈st(v₂)and there existsσ∈st(v₂)such thatσ∩ σ6=∅: in this case,σis incident atv₁but not inv₂, and there exists a simplexσincident atv₂which intersectsσ. This case also includes the symmetric situation in whichσ∈st(v₂)and σ6∈st(v₁)and there existsσ∈st(v₁)such thatσ∩σ6=∅.

3. σ∈st(v₁),σ6∈st(v₂)andσ∩σ=∅, for everyσ∈st(v₂): in this case,σis incident atv₁and not inv₂and it does not have any intersection with simplexes incident atv₂. This case also includes the symmetric situation in whichσ∈st(v₂)andσ6∈

st(v₁)and∀σ∈st(v₁),σ∩σ=∅.

Figure2gives six examples of simplexes that are incident at edge e={v₁,v₂}to be collapsed as in case 1. In Figures2(a) to2(c), st(e)consists of tetrahedront₁, and of its two faces{u₁,v₁,v₂}and {u₂,v₁,v₂}which are incident ate. In Figures2(d) to2(f),st(e) consists of dangling faced f₁. In Figure3, six examples are given of simplexes that are incident at only one extreme vertex of the edge to be collapsed, and that intersect some simplexes that are incident at the other extreme vertex. As in Figure2,eis the edge to be collapsed. In Figures3(a) to3(c), the non-empty intersection

u₁

u₂ v₂

t₁ v₁ e u₁

u₂ v₂

t₂ t₁

v₁ e

t₃ u₁

u₂ v₂

t₂ t₁

v₁ e

(a) (b) (c)

v₂ v₁ df₁

u e

v₂ v₁ df₁ u

t1

e

v₂ v₁ df₁ u

t1

t2

e

(d) (e) (f)

Figure 2:Six examples of simplexes that are incident at the edge e={v₁,v₂}to be collapsed: in (a), (b) and (c), the simplexes in- cident at e are tetrahedron t₁and two of its faces,{u₁,v₁,v₂}and {u₂,v₁,v₂}, i.e., st(e) ={t₁,{u₁,v₁,v₂},{u₂,v₁,v₂}}. In (d), (e) and (f), the dangling face d f₁is incident at e, i.e., st(e) ={d f₁}.

(Case 1)

u₁

u₂ v₂

v₁

df3

df2

e u₁

u₂ v₂

t₂ v₁

df3

e

t₃ u₁

u₂ v₂

t₂ v₁ e

(a) (b) (c)

v₂ v₁ u

we₂ we₁

e

v₂ v₁ u

t1

we₂

e

v₂ v₁ u

t1

t2

e

(d) (e) (f)

Figure 3:Six examples of simplexes that are incident at one vertex of the edge e to be collapsed, and that have non-empty intersection with some other simplexes that are incident at the other vertex. In (a), dangling face d f₂ is incident at v₁ and dangling face d f₃ is incident at v₂. Their intersection is edge{u₁,u₂}. (b) and (c) are similar to (a), except that the simplex incident at either vertex may also be a tetrahedron. In (d), wire edges we₁and we₂are incident at v₁and v₂, respectively, and their intersection is vertex u. Similarly, in (e) and (f), the intersection is at vertex u. (Case 2)

of those simplexes incident atv₁and those incident atv₂is edge {u₁,u₂}. In the other three examples, the non-empty intersection is vertexu. Figure4(a) shows an example where a simplex incident at v₁does not intersect any simplex incident atv₂.

Letλ:st(e)→st(v)be a map such thatσ⁰=λ(σ)∈Σ⁰ is ob- tained fromσby replacing{v₁,v₂}withv. We call it adimension- reduction map. Letµ:st(v₁)∪st(v₂)−st(e)→st(v)be a map that, given a simplexσ∈st(v₁)∪st(v₂)−st(e), providesσ⁰=µ(σ)such thatσ⁰∈st(v)andσ⁰={v}∪{w| ∀w∈σ−{vi},v=1,2}. We call mapµasimplex transformation map.

When performing edge collapse, we apply:

173

t3

v2

v1

t2

e

⇔

t3

v t2

(a) (b)

Figure 4:An example in which a simplex, that is incident at one vertex of the edge e to be collapsed, has an empty intersection with all other simplexes that are incident at the other vertex. (a) Tetra- hedra t₂and t₃are incident at v₁and v₂, respectively, and they do not intersect each other. (Case 3) (b) When edge e is collapsed, the two tetrahedra become 0-adjacent.

• in case 1: a reduction mapλfor everyk-simplexσ∈st(e)into a (k−1)-simplexσ⁰,k=2,3.

• in cases 2 and 3: a transformation mapµ.

Figure5and Figure6show the effect of edge collapse on each of the examples in discussed in Figures 2and3. In each exam- ple, the drawing on top is a reproduction of that in Figures2and 3. The drawing at the bottom shows what happens after edgeeis collapsed. In Figures 5(a) to 5(c), tetrahedront₁ is incident ate.

After edge collapse,t₁may be become a dangling face, as in Fig- ure5(a), a boundary face, as in Figure5(b), or an internal face, as in Figure5(c). In Figures5(d) to5(f),d f₁ is incident ate. After edge collapse,d f₁may become a wire edge, as in Figure5(d), or a boundary edge, as in Figures5(e) and5(f). Figure6is similar. The result of edge collapse on the example of Figure4(a) is shown in Figure4(b). Note that, in all the cases, at most two simplexes are merged into one simplex as the effect of transformation mapµ.

5.2. Vertex Split

Vertex splitis the inverse operation with respect to edge collapse.

It consists of splitting a vertexvin a 3D simplicial complexΣinto an edgee={v₁,v₂}. Thek-simplexes inst(v)either expand into (k+1)-simplexes formingst(e), or become incident atv₁orv₂, or are duplicated.

Given ak-simplexσ⁰∈st(v), the following three cases may oc- cur:

1. σ⁰is expanded into a simplexσinst(e). In this case, we apply the inverseλ⁻¹of the dimension-reduction mapλwhich maps σ⁰∈st(v)intoσ∈st(e)such that λ(σ) =σ⁰. This is equiva- lent to replacingvinσ⁰with{v₁,v₂}. (Each of the examples of Figure5, when read from bottom to top, illustrates the effect of vertex split.)

2. σ⁰∈st(v)is mapped into twok-simplexesσaandσbsuch that σa∈st(v₁)andσb∈st(v₂)andσ⁰=µ(σa) =µ(σb). (See the examples of Figure6from bottom to top.)

3. σ⁰ is transformed into one simplexσincident atv₁or inv₂. In this case, we mapσ⁰∈st(v)intoσ∈st(v₁)∪st(v₂)such that σ⁰=µ(σ)by replacingvinσwithv₁orv₂. (See Figure4from right to left.)

6. Performing an Edge Collapse

Performing the collapse of an edge e={v₁,v₂} into a vertex v in a complex Σ requires specifying just edgee and vertex v.

u₁

u2 v2

t1

v1

e u₁

u2 v2

t2

t1

v1

e

t₃ u₁

u2 v2

t2

t1

v1

e

m m m

u1

u2df v u1

u2

t2

v f

u1

u2

t2

v t3 f’

(a) (b) (c)

v2

v1

df1

u e

v2

v1

df1

u t1

e

v2

v1

df1

u t1

t2

e

m m m

u we v

u v

t1

e’

u v

t1

t2

e’

(d) (e) (f)

Figure 5:Effect of edge collapse on the six examples shown in Fig- ure2. Edge e={v₁,v₂}is collapsed into vertex v. In (a), (b) and (c), tetrahedron t₁ becomes a new dangling face, d f , an external face, f , of tetrahedron t₂, or an internal face, f⁰, shared by tetra- hedra t₂and t₃, respectively. In (d), dangling face d f₁becomes a wire edge, we. In (e) and (f), d f₁becomes a boundary edge, e⁰, of simplexes incident at both u and the new vertex v.

R_k0relation is affected for allk-simplexes inst(v₁)∪st(v₂).R₃₃, R_3,clusters,R_2,clustersandR_0,clustersrelations are affected for all sim- plexes belonging to st(v₁)∪st(v₂), or adjacent to simplexes in st(v₁)∪st(v₂). In this Section, we discuss in detail the different situations which can arise and show how the entities and the rela- tions in the NMIA data structure have to be updated. Based on this analysis, we present an algorithm for performing edge collapse.

As discussed in Subsection5.1, case 1, in which ak-simplex is reduced to a(k−1)-simplex and case 2, in which twok-simplexes may be merged into a single one, require more attention. We enu- merate here the different situations which may arise in these two cases. This will also help us encoding the inverse of edge collapse, vertex split.

To this aim, we considerL=link(v₁)∩link(v₂).Lis a collection of vertices and edges which can be ordered clockwise or counter- clockwise around edgee={v₁,v₂}. Ifeis a manifold edge, then Lis homeomorphic to a circle or to a portion of a circle. Ifeis a non-manifold edge, thenLis composed of several connected com- ponents, one for each edge-based cluster incident ate. Each compo- nent may consist of an isolated vertex or of a chain of edges. Figure 7gives an example ofL=link(v₁)∩link(v₂). Edgee={v₁,v₂}is the edge to be collapsed.st(v₁)is composed of tetrahedrat₁,t₂,t₄ and of all their faces.link(v₁)consists of the simplexes inst(v₁)

u₁

u2 v2

v1

df3

df2

e u₁

u2 v2

t2 v1

df3

e

t₃ u₁

u2 v2

t2 v1

e

m m m

u1

u2df ₂ v u1

u2

t2

v df3

u1

u2 t3

t2

v f’

(a) (b) (c)

v2

v1

u we2

we1

e

v2

v1

u t1

we₂

e

v2

v1

u t1

t2

e

m m m

u we¹ v

u v

t1

we2

u v

t1

t2

e’

(d) (e) (f)

Figure 6: Effect of edge collapse on the six examples shown in Figure 3. Edge e={v₁,v₂}is collapsed into a new vertex v. In (a), dangling faces d f₂and d f₃, which originally intersect at edge {u₁,u₂}, become one face d f₂. In (b), d f₃becomes an external face of tetrahedron t₂. In (c), the two tetrahedra t₂and t₃become face- adjacent at f⁰. In (d), wire edges we₁and we₂become a single wire edge, we₁. In (e), we₂becomes a boundary edge of simplexes inci- dent at both u and the new vertex v. In (f), the two set of simplexes that are incident at v₁and v₂, respectively, become edge-adjacent at edge e⁰after edge collapse.

that are not incident at v₁, namely faces f₁ and f₃ with all their boundaries.st(v₂)is composed of tetrahedrat₁,t₃,t₅and of all their faces.link(v₂)is defined similarly tolink(v₁), and consists of faces f₂ and f₄with all their boundaries. ThusLconsists of one edge, namely, edge{u₁,u₂}.

t4

t2

v1

v2

t3 t5

u1

u₂ f1

f3

f4

f2

t1 e L

Figure 7:An illustration for L=link(v₁)∩link(v₂): link(v₁)is composed of faces f₁, f₃ and of all their boundaries. Similarly, link(v₂) is composed of faces f₂, f₄, and of their boundaries.

Therefore, L is composed of edge{u₁,u₂}. Letω0={t₂,t₃}. Then, l(ω₀) ={t₂,t₃}, and c(ω₀) ={t₁}.

Let us considerωi∈L:ωican be a vertex,u, or an edge{u₁,u₂}.

We denote with l(ωi)the set of simplexes incident at ωi, i.e. in st(ωi), and incident at eitherv₁orv₂but not in both. In the exam- ple of Figure7,Lhas only one component, namely edge{u₁,u₂}, which we callω0. Thus,l(ω0) ={t₂,t₃}. We denote withc(ωi)the set of simplexes incident atωi, i.e., inst(ωi), and in bothv₁andv₂. In the example of Figure7,c(ω₀) ={t₁}.

We consider a simplexσ∈c(ωi), which can be either a tetrahe- dron, or a dangling face, and two simplexesσ1andσ2, incident at v₁andv₂, respectively, and belonging tol(ωi). Note thatσ₁andσ₂ can be tetrahedra, dangling faces or wire edges. This latter case is possible only whenωiis a vertex.

The possible combinations ofσ1,σandσ2are reported in Table 1. The first eight cases apply whenωiis an edge. The other eight cases apply whenωiis a vertex. In the columns corresponding to σ₁,σandσ₂, the symbol T, F, E or∅, means that the corresponding simplex is a tetrahedron, a dangling face, a wire edge or is non- existent, respectively. Whenωi is an edge, σis always bounded by four vertices{v₁,v₂,ωi}and can be either a tetrahedron or a hole. In both cases, it shares face{v₁,ωi}withσ1and face{v₂,ωi} withσ2. Ifσis a tetrahedron, it undergoes a dimension-reduction transformation into face{v,ωi}. In all cases, simplexes{v₁,ωi} and{v₂,ωi}are merged into simplex{v,ωi}. In the NMIA data structure, we are only interested in the case in which{v,ωi}is a dangling face, since we do not encode the faces bounding a tetra- hedron explicitly.

Whenωiis a vertex,σcan be either a dangling face or a hole, but, in both cases, it is bounded by three vertices{v₁,v₂,ωi}. Simplexes σ1andσ2share edges{v₁,ωi}and{v₂,ωi}withσ, respectively.

Note that, in general, there are severalσ1 andσ2 inl(ωi), except whenσ₁ orσ₂ are wire edges: in this case, they are completely defined by{v₁,ωi}or{v₂,ωi}. Moreover, eitherσ1orσ2can be a wire edge only ifσis empty.

ωiis an edge{u₁,u₂} ωiis a vertexu

Case σ1 σ σ2 Case σ1 σ σ2

1 ∅ T ∅ 9 ∅ F ∅

2 T T ∅ 10 T/F F ∅

3 ∅ T T 11 ∅ F T/F

4 T T T 12 T/F F T/F

5 F ∅ F 13 E ∅ E

6 T ∅ F 14 T/F ∅ E

7 F ∅ T 15 E ∅ T/F

8 T ∅ T 16 T/F ∅ T/F

Table 1:Cases for simplexσin c(ωi)and simplexesσ₁andσ₂in l(ωi).T= tetrahedron,F= dangling face,E= wire edge,∅stands for the absence of a simplex.

Examples of cases 1, 2, 4, 9, 10 and 12 in Table1are shown in Figures2(a) to2(f). The examples in Figures3(a) to 3(f) are instances of cases 5, 6, 8, 13, 14 and 16, respectively. Cases 3, 7, 11 and 15 are symmetric to cases 2, 6, 10 and 14 respectively.

In what follows, we examine how the entities and the relations are affected in the sixteen cases shown in Table1. We considerL as an ordered sequence of elementsωi, whereωiis either a vertex or an edge. We denote asωi−1 andωi+1, respectively, the prede- cessor and the successor ofωialongL. Note thatωidoes not need

to be connected to eitherω_i−1orωi+1. Also,ωican be an isolated vertex, or a vertex which is common to the two edgesωi−1 and ωi+1, or an extreme vertex of eitherωi−1orωi+1. These two latter cases occur whenσis a dangling face{u,v₁,v₂}and{ωi−1,v₁,v₂} or{ωi+1,v₁,v₂}, or both, define an empty tetrahedral hole. Thus, similarly to isolated vertices, we consider such a vertex as a sepa- rate element ofLand not as an extreme vertex of an edge.

df2

df1

u2

u₁ t4

t₃ t₁

v₂ v₁

t₂ e

⇔ df2

df1

u2

u₁ t4

t₃ t₂ v

df

(a) t₁

df2

df1

u₂ u1

t₄ t₂ t₃ v2

v₁ e

⇔

t₁

df2

df1

u₂ u1

t₄ v t₃

(b) t₁

u₂ u₁

t₄ t₃

t₂ v₂

v₁ df1

df2

e

⇔

t₁ u₂ u₁

t₄ t₃

t₂ v df¹

(c)

Figure 8:Examples of the updates needed at edge{u₁,u₂}after the collapse of edge e: In (a), tetrahedron t₁becomes a dangling face d f . R_2,cluster(d f)at edge{u₁,u₂}consists of dangling face d f₂ and tetrahedron t₂. The adjacency relations of the original neighbors of t₁ at edge{u₁,u₂}, namely d f₂ and t₂, need to be updated. d f replaces t₁in R_2,cluster(d f₂)and R_3,cluster(t₂). In (b), after edge e is collapsed, tetrahedron t₂becomes a boundary face of tetrahedron t₃, and tetrahedra t₁and t₃become immediate neigh- bors of each other at edge{u₁,u₂}. Therefore, t₂is removed from R₃₃(t₃)relation and t₁ is added to R_3,cluster(t₃). t₃ replaces t₂ in R_3,cluster(t₁). In (c), dangling face d f₂is merged into dangling face d f₁. d f₁and tetrahedron t₄become immediate neighbors of each other. So t₄replaces d f₂in R_2,cluster(d f₁), and d f₁replaces d f₂in R_3,cluster(t₄).

Whenωi={u₁,u₂}is an edge, (which holds for cases 1 to 8 in Table1,) the collapse of edgee={v₁,v₂}may cause the 1- and 2-adjacency (i.e.,R_2,clusters,R_3,clustersandR₃₃) relations to change for simplexes incident at edge{u₁,u₂}. These relations need to be updated. The three examples in Figure8illustrate how the update is done at {u₁,u₂}. In each example, the left part illustrates the situation before edge collapse, and the right part after. After edge

collapse, adjacency relations (R_3,clustersor R_2,clusters) at the new edges{u₁,v}and{u₂,v} are updated in a similar fashion. Spe- cial attention has to be given, however, whenωi={u₁,u₂}is con- nected toωi−1or toωi+1because neighboring simplexes may also be merged due to the collapse of edgee. Figure9(a) illustrates a situation in whichωi is not connected to its predessesor or suc- cessor, and Figure9(b), a situation in whichωiis connected to its predessesor. In Figure9(a), tetrahedront₁ is incident at the edge e={v₁,v₂}to be collapsed. Letω0 be edge{u₁,u₂}.ω0 is not connected to any other components ofLsince it is the only compo- nent ofL. Dangling faced f₁is the immediate neighbor oft₁at edge {u₁,v₁}, and dangling faced f₂is the immediate neighbor oft₁at edge{u₁,v₂}. After edge collapse,d f₁andd f₂become 1-adjacent at the new edge,{u₁,v}. In Figure9(b), the edge to be collapsed is e={v₁,v₂}.Lhas two components, namely{u₃,u₁}and{u₁,u₂}, which we callω0andω1. Similar to the example of9(a), before edge collapse, dangling facesd f₁ andd f₂are neighbors oft₁ at edges{u₁,v₁}and{u₁,v₂}, respectively. After edge collapse,d f₂ is merged tod f₁.

df2

v₂ u₁

u₂ t₁ v₁ df1

ω₀

e ⇔ v

u₁ df3

df2

df1

ωu₀₂ (a)

t₁ u₂ u₁ v₂

df2

v₁

u₃ ω₀ ω₁ df1

e ⇔

u₂ u₁ df1

df3

v

u₃ ω₀ ω₁

(b)

Figure 9: Two examples to show the update of the edge-based clusters at edge{u₁,v}after an edge collapse operation. In (a), tetrahedron t₁becomes a dangling face d f₃. Dangling faces d f₁ and d f₂, which are neighbors of t₁ at edge {u₁,v₁} and edge {u₁,v₂}, respectively, become neighbors of each other at the new edge{u₁,v}Therefore, R_2,clusters(d f₃)consists of d f₁and d f₂. d f₃ replaces t₁in both R_2,clusters(d f₁)and R_2,clusters(d f₂). In (b), after edge collapse, tetrahedron t₁becomes dangling face d f₃, and dan- gling face d f₁is merged into dangling face d f₂. So R_2,clusters(d f₃) consists of only d f₁and R_2,clusters(d f₁)consists of only d f₃.

Whenωi=uis a vertex, (cases 9 to 16 in Table1,) the collapse of edgee={v₁,v₂}causes two 1-connect clusters to merge into one.R_0,clustersat the new vertexvneeds to be defined. We need to updateR_3,clustersorR_2,clustersrelations at edge{u,v}. These up- dates are completely similar to those done for simplexes incident at edge{u₁,v}and{u₂,v}for the case whereωiis an edge.

We summarize now the various cases in an edge collapse algo- rithm. LetΣbe the given complex. Lete={v₁,v₂}be the edge to be collapsed into a vertexv. Recall thatL=link(v₁)∩link(v₂).

We denote withΩ_L1the set of top simplexes (tetrahedra, dangling faces and wire edge)σsuch thatσis incident atv₁ and in some entity oflink(v₁)−L, and withΩL2the set of simplexes incident at v₂and in some entity oflink(v₂)−L.

TheEdge Collapse algorithmperforms the following steps: