A scalable data structure for three-dimensional non-manifold objects

(1)

L. Kobbelt, P. Schröder, H. Hoppe (Editors)

A scalable data structure

for three-dimensional 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)

Abstract

In this paper, we address the problem of representing and manipulating non-manifold, mixed-dimensional objects described by three-dimensional simplicial complexes embedded in the 3D Euclidean space. We describe the de- sign and the implementation of a new data structure, that we call thenon-manifold indexed data structure with adjacencies (NMIA), which can represent any three-dimensional Euclidean simplicial complex compactly, since it encodes only the vertices and the top simplexes of the complex plus a restricted subset of topological relations among simplexes. The NMIA structure supports efficient traversal algorithms which retrieve topological relations in optimal time, and it scales very well to the manifold case. Here, we sketch traversal algorithms, and we compare the NMIA structure with data structures for manifold and regular 3D simplicial complexes.

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

Non-manifold objects are subsets of the Euclidean space which can be regarded as combinations of wire-frame, surface, solid and cellular decompositions. Informally, amani- foldobject is a subset of the Euclidean space for which the neighborhood of each internal point is locally equivalent to an open ball. Objects that do not fulfill this property at one or more points are callednon-manifoldobjects.

As pointed out by several authors⁵^,¹⁶^,²⁷^,²²^,²⁹, in a modeling system we need to represent non-manifold objects since Boolean operators are closed in the non-manifold domain, sweeping or offset operations may generate parts of different dimensionalities, non-manifold topologies are required in different product development phases, such as concep- tual design, analysis and manufacturing. Furthermore, most objects encountered in the applications contain a relatively small number of non-manifoldsingularities.Thus, it is im- portant to develop representations that scale well with the degree of "non-manifoldness" of the object.

Non-manifold objects can be effectively described through simplicial or cell complexes with a non-manifold and non-regular (i.e., with parts of different dimensional-

ities) domain. The contribution of this work is in designing and implementing a data structure for describing three- dimensional simplicial complexes embedded in the 3D Eu- clidean space, i.e., combinations of tetrahedral meshes with lower dimensional entities described by a chain of edges, or by a triangle mesh.

The trade-off when designing a data structure for a simplicial, or cell complex is among its expressive power, its storage cost and the efficiency of the algorithms for travers- ing the complex (which are based on primitives for retrieving incident and adjacent entities to a given one). To this aim, we have developed a data structure that satisfies the following requirements: (i) to be as compact as possible, (ii) to support retrieval of incidence and adjacency relations among the entities in the complex in optimal time, (iii) to be able to describe all kinds of non-manifold objects in 3D space parti- tioned into a 3D simplicial complex, and (iv) to be scalable, i.e., to exhibit just a low overhead cost due to the representation of non-manifold singularities.

Our data structure, that we call thenon-manifold indexed data structure with adjacencies (NMIA), encodes only the vertices and the top simplexes of the complex, plus a restricted subset of topological relations among simplexes.

(2)

For comparison purposes, we also specialize a general data structure for cell complexes, theincidence graph¹², to describe a certain class of simplicial complexes, and we call the resulting data structure thesimplified incidence graph.

We compare our data structure with both the simplified incidence graph and with a well-known data structure for a class of simplicial complexes, theindexed data structure with ad- jacencies.

The remainder of this paper is organized as follows. In Section 2, we summarize some background notions, which are necessary for understanding the related materials in this work. In Section 3, we review some related work. In Sec- tion 4, we describe the NMIA data structure. In Section 5, we present an implementation of this data structure and discuss its storage cost. In Section 6, we present the algorithms for retrieving topological relations for a simplicial complex described by the NMIA data structure. In Section 7, we describe the simplified incidence graph, and we present a comparison of the NMIA structure with such data structure and with the indexed data structure with adjacencies. Finally, in Section 8, we draw some conclusions and discuss future work.

2. Background

In this Section, we review some basic combinatorial notions about simplicial complexes in arbitrary dimensions, and we introduce the topological relations among the cells of a complex. We useabstract simplicial complexesas basic tools to capture the combinatorial structure of Euclidean simplicial complexes.

2.1. Simplicial Complexes

LetV be a finite set of points that we callvertices. Anab- stract simplicial complexonV is a subsetΣof the set of (non-empty) parts ofV such that{v} ∈Σfor every point v∈V, and ifs⊂V is an element ofΣ, then every subset of sis also an element ofΣ¹⁸. Each element ofΣis called an abstract simplex.

Thedimensionof a simplexs∈Σ, denoteddim(s), is defined bydim(s) =|s| −1, where|s|is the number of vertices ins. A simplex of dimensionkis called ak-simplex.

A complex Σ is calledd-dimensional, or a d-complex, if max_s∈Σ(dim(s)) =d. Eachd-simplex of ad-complexΣis called amaximal simplexofΣ.

Theboundary b(s)of a simplexsis defined as the set of all proper parts ofs. Simplexesξinb(s)are calledfacesofs.

Similarly, theco-boundary, orstar, of a simplexsis defined as?s={ξ∈Σ|s⊂ξ}. Simplexesξin?sare calledco-faces ofs. Thelinkof a simplexsis the set of all faces of co-faces ofs, that are not incident ats. Any simplexssuch that?s=s is called atop simplexofΣ. In the following, we will call restricted starof a simplexs,?s− {s}, and we will denote it asst(s).

Two distinct simplexes are said to beincident if one of them is a face of the other. Two simplexes are called k- adjacentif they share ak-face. Twop-simplexes, withp>0, are said to beadjacentif they are(p−1)-adjacent. Two vertices (i.e., 0-simplexes) are calledadjacentif they are both incident at a common 1-simplex. Two simplexes that are nei- ther incident nor adjacent are said to bedisjoint.

Anh-path is a sequence of simplexes(si)^k_i=0 such that two successive simplexessi−1,siareh-adjacent. Two sim- plexessands⁰areh-connected, if and only if there exists an h-path(si)^k_i=0such thatsis a face ofs₀ ands⁰is a face of sk. A subsetΣ⁰of a complexΣis calledh-connectedif and only if every pair of its vertices areh-connected. Any max- imalh-connected sub-complex of a complexΣis called an h-connected componentofΣ. The termconnectedis used as a shortcut for 0-connected.

A d-complex Σ where all top simplexes are maximal (i.e., of dimension d) is called regular, or uniformly d- dimensional. A(d−1)-simplexsin ad-complexΣis aman- ifold(d−1)-simplexif and only if there are at most twod- simplexes incident ats. Otherwise,sis called anon-manifold (d−1)-simplex. A regular(d−1)-connectedd-complex in which all(d−1)-simplexes are manifold is called a(com- binatorial) pseudo-manifold (possibly with boundary). A pseudo-manifold satisfying the additional property that all its vertices have a link combinatorially equivalent either to the(d−1)-dimensional sphere or to the(d−1)-dimensional ball is called a(combinatorial) manifold.

A Euclidean simplex of dimensiondis the convex hull of d+1 linearly independent points in then-dimensional Eu- clidean spaceEⁿ, withd≤n. We simply call aEuclidean d-simplexad-simplexwhen the context is understood: a 0- simplex is avertex; a 1-simplex anedge; a 2-simplex atri- angle; a 3-simplex atetrahedron. Any Euclidean k-simplex tgenerated by a setVt⊆Vsof cardinalityk+1≤dis called ak-faceofs.

A finite collection Σ of Euclidean simplexes is a Eu- clidean simplicial complexwhen both (i) for each simplex s∈Σ, all faces ofsbelong toΣ, and (ii) for each pair of sim- plexessands⁰, eithers∩s⁰=∅ors∩s⁰is a face of boths ands⁰.

The domain, or carrier, of a d-dimensional Euclidean simplicial complexΣembedded inEⁿ, withd≤n, is the sub- set ofEⁿdefined by the union, as point sets, of all the simplexes inΣ. The combinatorial structure of a Euclidean simplicial complex is an abstract simplicial complex. The domain of a Euclidean simplicial complex which is described by a combinatorial manifold is a manifold inEⁿ. Whenever no ambiguity arises, we will use the termsimplexto denote an abstract, or a Euclidean, simplex. We will also use the termcomplexto denote an abstract, or a Euclidean, simplicial complex.

(3)

2.2. Topological Relations

Let Σ be a d-complex. Let s ∈Σ be a p-simplex, with 0≤p≤d. For each integer valueq, 0≤q≤d, we define the topological relationRpq(s)as a retrieval function that re- turns theq-simplexes ofΣthat are not disjoint from s. In particular:

• Forp<q,Rpq(s)consists of the set of simplexes of order qin the star ofs.

• Forp>q,Rpq(s)consists of the set of simplexes of order qin the set of faces ofs.

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

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

RelationRpqis called aboundary relationifp>q, aco- boundary relationifp<qand anadjacency relationifp= q. Boundary and co-boundary relations together are called incidence relations.

3. Related Work

Most of the existing work in the literature focuses on the two-dimensional boundary representation of three- dimensional objects, and on the manifold domain. In the manifold domain, several data structures have been proposed for representing the decomposition of the boundary of a three-dimensional manifold into a simplicial complex

1^,11^,15^,17^,21^,23^,28. The approach proposed in¹⁵has been generalized to manifold complexes in three and higher dimensions¹¹^,², while the half-edge data structure has been extended to the three dimensional case in²¹. The compact corner table data structure²⁸has been generalized to arbitrary non-manifold meshes.

Most work in the context ofnon-manifoldmodeling has been done in two dimensions for representing the boundary of non-manifold, non-regular objects. The first proposal for a topological data structure for boundary representation of non-manifold objects is theradial-edge structure²⁹. In¹⁶, Gursoz et al. describe a vertex-based data structure, called thetri-cyclic cuspstructure, which extends the radial-edge structure by maintaining also inclusion relations between the local neighborhoods of a vertex. A similar structure has been introduced by Yagamuchi and Kimura³⁰. A more compact data structure, called thepartial entity structure¹⁹has been more recently proposed: it has been shown to require half of the space of the radial-edge structure. The storage costs of all such data structures do not scale with the number of non- manifold singularities, since they have been developed under the assumption that objects contain several non-manifold joints. The radial-edge data structure has been specialized in

24to the case of two-dimensional simplicial meshes.

In⁸, a compact data structure for non-manifold and non- regular two-dimensional simplicial complexes has been pre-

sented, which encodes both connectivity and adjacency information with a small memory overhead, and scales very well to the manifold case. A compact scalable edge-based data structure for non-manifold two-dimensional simplicial complexes has been proposed by Campagna et al.⁴, which also scales well to manifold meshes, but it is restricted to regular complexes. A few proposals exist for modeling shapes in arbitrary dimensions through cell complexes. Se- lective Geometric Complexes (SGCs) ²⁷ can describe objects through cell complexes whose cells can be either open, or not simply connected. In SGCs, cells and their mutual adjacencies are encoded in an incidence graph ¹², which is a complete, but a verbose data structure. N-G-maps ²⁰ are an implicit representation for a sub-class of pseudo- manifolds, called quasi-manifolds, but they are also quite space-consuming. The winged representation²⁵can describe d-dimensional pseudo-manifold simplicial complexes, i.e., just regular ones. It generalizes to arbitrary dimensions the so-called incidence data structure with adjacency commonly used for triangle and tetrahedral meshes³.

An alternative approach to the design of non-manifold data structures consists of decomposing a non-manifold object into simpler and more manageable parts ⁷^,¹⁰^,¹³^,¹⁴. The proposals in ¹⁰^,¹³^,¹⁴ are restricted to modeling two- dimensional regular complexes, which describe the boundary of a solid object. In⁷, a sound decomposition for d- dimensional non-manifold objects described through simplicial complexes is defined, which is unique and produces a description of an abstractd-complex (not necessarily em- beddable in the Euclidean space) as a combination of nearly manifold components. A data dimension-independent data structure for such decomposition is defined in⁹, which de- scribes the components and their connectivity in a two-level representation.

4. Design of the Data Structure

In this Section, we introduce the design choices performed and the elements (entities and topological relations) of a data structure for describing three-dimensional simplicial complexes embedded in the three-dimensional Euclidean space.

4.1. Design Issues

In our data structure, we want to be able to describe 3D simplicial complexes containing also one- and two-dimensional top simplexes, that we callwire-edgesanddangling faces, respectively, in order to represent parts of different dimensionalities in the object. Moreover, we need to describe situations in which the restricted star of an edge, or of a vertex.

consists of more than one connected component, in order to represent edges and vertices in the object for which the manifold condition does not hold. Note that, since we are dealing with are 3-complexes embedded inE³, any 2-simplex, which is not a top simplex, must be on the boundary of either one or two simplexes.

(4)

The above singularities can be summarized as the presence of:

1. several connected components in the restricted star of some vertex (called anm-vertex) (see Figure 1);

2. 1-dimensional top simplexes (wire-edges) (see Figure 2);

3. several connected components in the restricted star of some edge ( called anm-edge) (see Figure 3);

4. 2-dimensional top simplexes (dangling faces) (see Figure 4).

In all the figures, tetrahedra are in solid grey of two intensi- ties; dangling faces are shaded; edges and vertices of interest are highlighted in bold.

v we

df

0

t0

t

1

df

df ²

t₂ t₃

Figure 1: st(v) has four connected components

t

₁

we t

₀

Figure 2:a wire-edge, we, connecting two tetrahedra

e

3

df t

df

0 1

1 0

t

₂

t t

Figure 3: st(e) has four connected components

df

t

₁

t

₀

Figure 4:a dangling face, d f , connecting two tetrahe- dra

Thus, the data structure must describe correctly the pre- vious four cases. Cases 1 and 3 involve connectivity issues, and are discussed below.

4.2. Singularities at a non-manifold vertex

To take care of the connectivity information at an nm-vertex, we observe that the restricted star of a nm-vertexvconsists of several connected components. We call each such component avertex-based cluster. If two simplexessi,sjbelong to the same vertex-based cluster inst(v), then there exists a 1- connected path passing through only those simplexes which form the cluster. These clusters cannot be ordered aroundv.

As no ordering is possible, the basic strategy of moving around a non-manifold vertex is to perform a breadth-first

search and visit all simplexes that are related through rela- tionsR₃₃,R₂₃, orR₃₂in the same cluster (to be described in Section 6).

4.3. Singularities at a non-manifold edge

The restricted start of an nm-edge consists of several connected components. We call each such component anedge- based cluster. Edge-based clusters can be ordered around the edge, for instance, in counter-clockwise direction. Also, if simplexessi,sjbelong to the same connected component in st(e), then there exists a 2-connected path fromsitosjthat traverses through only those simplexes that are incident at e. This implies that a cluster consists either of a single dan- gling face, or of a collection of tetrahedra fanning out from the nm-edge. This is an interesting property for navigation:

when we want to find all the elements within an edge-based cluster, we simply move from one tetrahedron to the next one by using relationR₃₃. When we finish examining a cluster, we need to find the next cluster. To this aim, for each simplexsiof dimension 2 or higher, we keep track of its left and right neighbors around each of its edges when necessary.

This condition is described as follows:

• If a simplexsiis the only element of a cluster, then both its left and right neighbors (which may be identical) would belong to some other clusters arounde. These two simplexes are the left and right neighbors ofsiwith respect to edgee.

• If the simplex on the left ofsibelongs to the same cluster assi, then we saysihas no left neighbor with respect to edgee.

• A symmetric case holds for the right neighbor.

For example, consider the object in Figure 3. In Figure 5, we show on the right a cross-section of the star of edgee, The table in Figure 5 shows the edge-based clusters associated with the nm-edgeeby considering the clusters in a counter- clockwise order.

4.4. Entities and Topological Relations 4.4.1. Entities

Given a simplicial complex Σ, the non-manifold indexed data structure with adjacencies (NMIA)encodes all vertices (0-simplexes), wire-edges (top 1-simplexes), dangling faces (top 2-simplexes), and tetrahedra (3-simplexes) ofΣ. Other 1- and 2-simplexes are not explicitly represented.

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

• RelationR_0,clusters(v)is a retrieval function which associates, with vertexv, one representativek-simplex for each vertex-based cluster incident atv. Let us consider the object in Figure 1 as an example. The object is reproduced in

(5)

0 0

1

2

t

3

t t t df

df

e

3

df t

df

0 1

1 0

t

₂

t t

e

Entity left neighbor ate right neighbor ate

d f₀ t₀ d f₁

d f₁ d f₀ t₃

t₃ d f₁ t₂

t₂ t₃ empty

t₁ empty empty

t₀ empty d f₀

Figure 5:Clusters around a nm-edge e and their neighbor- ing relations.

Figure 6. There are four clusters incident at vertexv. We take one representative from each of these clusters. One possible way is shown on the bottom of Figure 6.

• RelationR_2,clusters(f)is a retrieval function which associates, with each edgeeiof a dangling face f, the edge- based clusters incident atei, in a counter-clockwise ordered sequence.

• RelationR_3,clusters(s)is a retrieval function which associates, with each edgeeiof a 3-simplexs, the edge-based clusters incident atei, in a counter-clockwise ordered sequence.

v we

df

0

t0

t

1

df

df ²

t2

t₃

we₀

v df0

t2

df1

cluster: 1 2 3 4

representative chosen: we₀ d f₁ d f₀ t₂ Figure 6:Vertex-based clusters at the vertex shown in bold, and choice of representatives for each cluster shown in the table

Thus, for each tetrahedront, we encode the following relations:

• RelationR₃₀(t), which associates, with each tetrahedront,

its four vertices ordered according to the orientation chosen fort.

• RelationR₃₃(t), which associates, with each tetrahedront, the four tetrahedra adjacent totthrough a 2-simplex, (the i-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 tetrahedront(considered in an order compatible with the orientation oft).

For each dangling face f, we encode the following rela- tions:

• Relation R₂₀(f), which associates, with each dangling face f, its three vertices (ordered according to the orien- tation chosen for f).

• 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 of f).

For each wire-edgee, we encode relationR₁₀(e), which associates, with edgee, its two extreme vertices. Note that there cannot exist edge-based clusters incident at a wire-edge e. Finally, for each vertexv, we encode relationR_0,clusters(v), as defined above. Note that only one representative for each vertex-based cluster is maintained.

5. Implementation of the NMIA Data Structure In this Section, we describe our implementation of the NMIA data structure, and we evaluate its storage cost. Al- though the space needed to index one entity is justlog₂m bits, wheremdenotes the total number of such entities in the data structure, in our implementation, for simplicity, we use one integer (represented on 32 bits) to index an entity.

We consider references and indexes as integers also in the comparison presented in Section 7.

Our present design aims at supporting both efficient traversal and mesh modifications. Short dynamic arrays are used to store relations to make local modifications on connectivity simpler.

For each entity (vertex, wire-edge, dangling face and tetrahedron), we store a one-bit flag for temporarily mark- ing a simplex as having been visited. These flags have to be reset after each query. We encode theR₃₀(t),R₂₀(f)and R₁₀(e)relations as arrays of indexes to the four, three and two vertices of a tetrahedront, of a dangling face f, and of a wire-edgee, respectively.

For each tetrahedron t, relationR₃₃(t)is encoded as a 2-bit flag f₃₃, a (possibly empty) array containing the 2- adjacent neighbors oftand a reference to this latter array.

A null reference means thatthas no 2-adjacent neighbors.

Otherwise,f₃₃+1 is equal to the number of 2-adjacent tetrahedra.

RelationR_3,clusters(t)stores the edge-based cluster infor-

(6)

mation for each of the six edges oft. For each edgeeoft, it encodes:

• a 4-bit flagf_3cto indicate the types of left and right neighbors thatthas ate. The meanings of the flag are reported in Table 1. Note that, iff_3cis equal to 1, 2, 3, or 6, thent has one neighboring cluster ate; iff_3cis equal to 4, 5, 7, or 8, thenthas two neighboring clusters ate. Otherwise, it has no neighbor. Sincethas six edges, six flags and up to twelve neighbors have to be stored, and thus a total of 24 bits for each tetrahedron.

• an integer array of cluster entities containing the indexes either to a tetrahedron or to a dangling face. The size of this array is exactly equal to the number of cluster entities to be stored.

• a reference to the cluster entity array.

flag left neighbor type right neighbor type

0 empty empty

1 empty dangling face

2 empty tetrahedron

3 dangling face empty

4 dangling face dangling face 5 dangling face tetrahedron

6 tetrahedron empty

7 tetrahedron dangling face

8 tetrahedron tetrahedron

Table 1:Meanings of the values of the f_3cflag

!"!"!"!"!"!

#"#"#"#"#"#

$"$"$"$"$

%"%"%"%"%

e

3

df t

df

0 1

1 0

t

₂

t t

e

4

e

₃

e

₀

e

₅

e

₂

t

₃

e

₁

e=

this

Edge: e₀ e₁ e₂ e₃ e₄ e₅

Flag value: 0 5 0 0 0 0

Values of array: 1 2

Figure 7:Encoding of the neighboring clusters of tetrahe- dron t₃with respect to its six edges

As an example, let us consider the complex in Figure 7.

Consider tetrahedront₃. We label withe₀,..,e₅the six edges oft₃, as shown in Figure 7 on the right. The neighboring cluster information at the six edges are encoded with the flags shown in the table in Figure 7. Edgee₁has flag value 5 because the left neighbor oft₃ at edgee₁ is a dangling

face (d f₁), and the right neighbor is a tetrahedron (t₂). At all other edges,t₃appears as a cluster by itself, i.e., it has no left nor right neighbors at other edges. Thus, all flag values are 0. From the values of the six flags, we can tell that there are only two entities related tot₃inR_3,cluster(t₃), whose indexes are stored in the cluster entity array. We do not need to store their types since such information are already encoded by the flags.

For each dangling face f, relation R_2,clusters(f) is encoded in a completely similar way asR_3,clusters for tetrahedra. Since a dangling face has three edges,R_2,clustersis scaled accordingly.

Finally, relationR_0,clusters(v)for a vertexvis encoded by using an array of 2-bit flags and an integer array of indexes, each being an index to one representative (a wire-edge, a dangling face, or a tetrahedron) of a cluster atv. The flag indicates whether the representative is a wire-edge, a dangling face, or a tetrahedron. As an example, let us consider the complex depicted in Figure 6. The particular choice we have made is encoded in theR_0,clusters(v)relation as shown in Table 2.

representative chosen: we₀ d f₁ d f₀ t₂

flag: 0 1 1 2

index of entity: 0 1 0 2

Table 2:Encoding of R_0,clusters(v)for the non-manifold ver- tex v of Figure 6

We have designed and implemented an algorithm for building the NMIA data structure by starting from the collection of all the top simplexes in the complex. The input consists of all vertex coordinates plus the list of the top simplexes, where each top simplex is expressed through the indexes of its vertices. The algorithm reconstructs the adjacency information and detects the non-manifold situations around vertices and edges. The current version is intended to build the data structure statically to work off-line. In this case, a preprocessing step is taken to make the connectivity information at each simplex available.

5.1. Storage costs

Let nt,d,w,nv denote the number of tetrahedra, dangling

faces, wire-edges, and vertices in a simplicial complex, respectively. Let bbe the number of boundary faces in the complex (i.e., those triangles that belong to exactly one tetrahedron). Letceandcvbe the total number of clusters over all the nm-edges and nm-vertices, respectively.

For the purpose of comparison with other data structures, we also define the following quantities. Letnf be the total

(7)

number of faces (including dangling faces). Letne be the total number of edges (including wire-edges).

Letktbe the total number of neighboring edge-based clusters stored over all tetrahedra, andk_dbe the total number of neighboring edge-based clusters stored over all the dangling faces. Thus, we have that 2ce=kt+k_d, because every edge- based cluster appears twice, once as a left and once as a right neighbor.

We need 3nvdoubles for vertex coordinates,nt+d+w+

nvbits for the one-bit navigation flag. In the following, we report the space requirements for each encoded relation:

• R₃₀: 4ntintegers

• R₂₀: 3dintegers

• R₁₀: 2wintegers

• R₃₃: 2ntbits for flags +(4nt−b)integers for theR₃₃array +ntintegers for references to theR₃₃array

• R_3,clusters: 24ntbits for flags (of which each tetrahedron has 6) +ktintegers for the cluster arrays +nt references to the cluster arrays

• R_2,clusters: 12dbits for flags (of which each dangling face has 3) +k_d integers for the cluster arrays +dreferences to the cluster arrays

• R_0,clusters: 2cvbits for flags +cvintegers for the cluster arrays storing cluster representatives +nvintegers keeping tracking of the length of each cluster array +nvreferences to the array.

Now, we evaluate and compare the space requirements of the NMIA structure in the general case, in the case of pseudo-manifold complexes and in the case of manifold complexes. We assume that reference and indexes are stored as 32 bits integers.

• General non-manifolds:

geometric information:3nvdoubles topological entities:(nt+d+w+nv)bits

topological relations:(10nt−b+4d+2w+2nv+2ce+ cv)integers +(26nt+12d+2cv)bits.

• Pseudo-manifolds:

Pseudo-manifold complexes do not have dangling faces and wire-edges (thus,d=w=0), but they may have non- manifold edges and non-manifold vertices. The space requirements thus become:

geometric information:3nvdoubles topological entities:(nt+nv)bits

topological relations:(10nt−b+2nv+2ce+cv)integers +(26nt+2cv)bits

• Manifolds:

Manifold complexes do not have dangling faces, wire- edges and non-manifold edges. Each vertex has exactly one cluster. Sod=w=ce=0 andcv=nv. The storage requirements thus become:

geometric information:3nvdoubles

topological entities:(nt+nv)bits

topological relations: (10nt −b+3nv) integers + (26nt+2nv)bits

In practical applications, it has been shown thatnt ≈6nv 6. Thus, the space requirements for a manifold are approximately equal to 73nvintegers + 3nvdoubles.

6. Retrieving Topological Relations

In this Section, we discuss how topological relations can be retrieved in optimal, or almost optimal, time from the NMIA data structure. This means that all non-stored relations can be retrieved in time linear in the number of entities involved in the specific relation, that is, for instance, the edges incident at a given vertexv(theR₀₁ relation) can be extracted in time linear in the number of edges incident at v. Such retrieval algorithms are the basis for developing effi- cient traversal algorithms through the complex described by the data structure.

Retrieving those relations which are explicitly stored in the data structure, i.e.,R₃₀ andR₃₃, for tetrahedra,R₂₀, for dangling faces,R₁₀, for wire-edges, takes constant time.

Retrieving boundary relationsR₃₂(t)andR₃₁(t)provides as results the faces of tetrahedront, specified as triplets of vertices, and the edges of tetrahedront, specified as pairs of vertices, respectively, and can be performed in constant time.

To retrieve boundary relationR₂₁(f), we need to specify facefin casefis not a dangling face. Thus, iffis a boundary face of a tetrahedront, then we specify f asface(t, i), that is thei-th face oft, wherei=0, ..,3. The 1-simplexes involved inR₂₁(f)are again specified as pairs of vertices.

Thus, relationR₂₁(f)is retrieved in constant time.

RelationR₂₃(f)can be extracted only for boundary faces of tetrahedra. Face f is specified asface(t, i). The retrieval algorithm makes use of relationR₃₃(t)to find the other tetrahedron sharingf, if it exists. This takes constant time.

Retrieving relationsR₁₂(e)andR₁₃(e)involves navigating around an edgee. The corresponding retrieval algorithms are implemented in a very similar fashion. The edge being queried can be a boundary edge of a dangling face or of a tetrahedron, but not a wire-edge. An edge of a dangling face f is addressed asedge(f, i)fori=0, ...,2 and an edge of a tetrahedront isedge(t, j)for j=0, ...,5. We use relations R_3,clustersorR_2,clustersdepending on whethereis an edge of a tetrahedron, or of a dangling face. If a cluster is a collection of tetrahedra that fan out from edgee, we use theR₃₃ relation to move from one tetrahedron to the next in the same cluster, andR₃₀to make sure that both of them are incident ate.

We illustrate through the example in Figure 8 how to retrieve bothR₁₂(e)andR₁₃(e)relations, i.e., how to navigate around an edgeein counter-clockwise direction. To this aim, we perform the following steps:

(8)

1

t3

df

df₀ t₂

t₁ t₀ e

2

6

5 1

4 3

7

start

Figure 8:Navigating through the entities incident at a non- manifold edge e (here we show a view perpendicular to edge e, as shown in Figure 6

1. We start withebeing an edge oft₃.

2. UsingR_3,clusters(t₃), we retrieve the left and right neighbors oft₃with respect toe. These ared f₁andt₂, respectively. Then, we move tot₂.

3. FromR_3,clusters(t₂)we see thatt₂has no right neighbor.

Thus, relationR₃₃(t₂)allows us to extract all the tetrahedra which are face-adjacent tot₂. By usingR₃₀(t₂), we can selectt₁as the only tetrahedron that is also incident ate. Then, we move tot₁.

4. FromR_3,clusters(t₁)we see thatt₁has no right neighbor.

Thus, again we use theR₃₃(t₁)to retrieve the tetrahedra which are face-adjacent tot₁andR₃₀(t₁)to select those incident ate. This givest₀andt₂, and thus we move tot₀. 5. FromR_3,clusters(t₀)we see that the right neighbor oft₀is

d f₀. Thus, we move tod f₀.

6. FromR_2,clusters(d f₀)we see that the right neighbor of d f₀isd f₁. Thus, we move tod f₁.

7. FromR_2,clusters(d f₁)we see that the right neighbor of d f₁ist₃. Thus, we are done, since we started witht₃. It can be easily seen that retrieving relationR₁₂(e)takes a time linear in the number of faces incident at e, i.e., it can be performed in optimal time. Retrieving relationR₁₃(e) takesO(|R₁₂(e)|)time, where|R₁₂(e)|denotes the number of faces incident ate, because of the possible presence of dangling faces.

RelationR₂₂(f)is basically retrieved in the same way as relationR₁₂(e), one for each edge of face f. Therefore, it takesO(|R₂₂(f)|)time, which is optimal.

Retrieving relationsR₀₀(v),R₀₁(v),R₀₂(v), andR₀₃(v)re- quires a breadth-first search over all the clusters incident at vertexv. Within each cluster, entities that are incident atv are traversed by usingR₃₃,R₃₀,R_3,clusters, andR_2,clustersre- lations.

Again we illustrate, through an example, how to retrieve all tetrahedra, dangling faces and wire-edges incident at a given non-manifold vertexv(see Figures 9 and 10). In the same way, we can retrieve allR_0i(v)relations, wherei= 0,1,2,3. Note that we use a queue to guide the breadth-first

&'&'&'&

('('('(

)')')') )')')') )')')') )')')') )')')') )')')') )')')')

*'*'*'*

+'+'+'+'+

,',',', ,',',', ,',',', ,',',', ,',',',

t₂ we

df

0

t0

t

1

1 3

df v df

2

representative

Figure 9:The cluster selected for navigation

t2

start v

t₂ df

t₁ v 2

t₂ df

t₁ v 2

t₂

-.-.-.-.- -.-.-.-.- -.-.-.-.- -.-.-.-.-

/././././

df t0

t₁ v 2

t₂

0.0.0.0.0 0.0.0.0.0 0.0.0.0.0 0.0.0.0.0

1.1.1.1 1.1.1.1 1.1.1.1 1.1.1.1

df t0

t₁ v 2

t₂

2.2.2.2.2 2.2.2.2.2 2.2.2.2.2 2.2.2.2.2

3.3.3.3.3 3.3.3.3.3 3.3.3.3.3 3.3.3.3.3

df t0

t₁ v 2

Figure 10:Navigation of the circled cluster

traversal of the star ofvand that we mark a simplex as visited when we insert it into the queue. We perform the following steps:

1. We start with onlyt₂ in the queue, which we have ob- tained fromR_0,clusters(v).

2. Using R₃₃(t₂), we find that t₁ is incident at v. Using R_3,clusters(t₂), we find thatd f₂is also incident atv. Thus, t₁andd f₂are inserted into the queue.

3. Now, we dequeue t₁ and examine R₃₃(t₁) and R_3,clusters(t₁). This gives t₂ and d f₂, that are already marked as visited.

4. Then, we dequeue d f₂. and we examine relation R_2,clusters(d f₂). This givest₀, t₁ andt₂, among which onlyt₀is not visited. Thus, we insertt₀into the queue.

5. We dequeue t₀ and we examine the R₃₃(t₀) and R_3,clusters(d f₂)relations. This givesd f₂, which has already been visited.

6. The traversal is finished, since the queue is empty. Reset the flags of all the simplexes retrieved.

Retrieving relationsR₀₀(v)andR₀₁(v)takes optimal time.

As in the case ofR₁₃, bothR₀₂(v)andR₀₃(v)relations can be retrieved inO(|R₀₀(v)|)time due to the possible presence of tetrahedra, forR₀₂(v), or of dangling faces, forR₀₃(v).

(9)

Finally, by usingR₀₁ andR₁₀ relations, we can retrieve theR₁₁(e)relation, i.e., all the edges incident at the extreme vertices of edgee, in optimal time.

Note that in our design, we specify a face or an edge, which is not a top simplex, implicitly in terms of one the top simplexes (such as tetrahedra, dangling faces) containing it.

We use top simplexes as entities because the retrieval primitives are usually used in the context of algorithms which traverse the complex by moving from one top simplex to another.

In case ak-simplexσis specified explicitly through the indexes of its(k+1)vertices, and we need to retrieve the index of the simplex, ifσis a top simplex, relationR₀₀(vi) must be retrieved for each vertexvi ofσ. In the manifold case the same strategy is commonly used, since a manifold simplicial complex is usually encoded with the indexed data structure with adjacencies.

7. Comparisons

In this Section, we present another data structure, that we call thesimplified incidence graph, which is a simplified version of the incidence graph ¹² for simplicial pseudo- manifolds, we review the indexed data structure with ad- jacenciesfor simplicial pseudo-manifolds, and we compare the NMIA data structure with the former two.

7.1. Simplified Incidence Graph

The incidence graph¹²is a data structure ford-dimensional cell complexes, in which everyi-cell is stored as an entity, and boundary topological relationsRi,i−1fori=1, ...,das well as co-boundary relationsR_i,i+1fori=0, ...,d−1 are encoded. For simplicial complexes, boundary relations are constant.

In the case of three-dimensional simplicial pseudo- manifolds, co-boundary relationsR₁₂(e)andR₀₁(v)can be retrieved in optimal time (i.e., linear in the number of simplexes inR₁₂(e) and R₀₁(v), respectively), by storing, for R₁₂(e), one representative 2-simplex for each edge-based cluster incident at edgee, and, forR₀₁(v), one representative edge for each vertex-based cluster incident atv. In the manifold case, each edge and each vertex has only one cluster. We call the incidence graph in which we store just one representative forR₀₁(v)andR₁₂(e)relations thesimplified incidence graph.

The simplified incidence graph stores all 0-, 1-, 2- and 3-simplexes. It encodes the coordinates of each vertex (3nv

doubles for the 3D coordinates) and the following relations:

• relationR₃₂(t): the four faces on the boundary of tetrahedront(4ntintegers).

• relationR₂₁(f): the three edges on the boundary of facef (3nf integers).

• relationR₁₀(e): the two vertices on the boundary of edge e(2neintegers).

• relationR₂₃(f): the one, or two tetrahedra that are incident atf(4ntintegers).

• relationR^∗₁₂(e): only one representative edge from each edge-based cluster that is incident ate(ce+ne−kinte- gers, wherekis the number of nm-edges).

• relationR^∗₀₁(v): only one representative edge from each vertex-based cluster that is incident at vertexv(cvintegers).

We can evaluate the storage requirements of the data structure in the case of pseudo-manifolds and manifolds:

• Pseudo-manifolds:

topological relations:(8nt+3nf+3ne+ce+cv−k)integers

• Manifolds:ce=k=0 andcv=nv

topological relations:8nt+3nf+3ne+nvintegers If we assume thatnt ≈6nv, the space requirements are about 131nvintegers + 3nvdoubles.

It can be shown that all topological relations can be extracted in optimal time from the simplified incidence graph.

7.2. Indexed Data Structure with Adjacencies

The indexed data structure with adjacencies is a compact data structure for simplicial pseudo-manifolds in arbitrary dimensions, which encodes only 0- andd-simplexes and their connectivity. We describe here the three-dimensional instance of this data structure.

The indexed data structure encodes the vertex coordinates (3nvdoubles), all 0- and 3-simplexes plus the following relations:

• relationR₃₀(t): the four vertices on the boundary oft(4nt

integers).

• relation R₃₃(t): the four tetrahedra that are adjacent to tetrahedront(4nt−bintegers).

For both pseudo-manifold and manifold complexes, its space requirements are:

geometric information:3nvdoubles topological relations:8nt−bintegers

If we assume in the manifold case thatnt≈6nv, then the storage cost is approximately equal to 48nvintegers + 3nv

doubles.

Also, it can be easily seen that only boundary relations can be retrieved in optimal time from the indexed data structure with adjacencies. This data structure cannot support navigation through vertices and edges in optimal time.

(10)

7.3. Comparison

For a manifold or a reasonably regular object such thatce

andcvare small, we can see that the space used by NMIA data structure is about halfof that used by the simplified incidence graph.

The space requirements are about 1.5 times with respect to those of the indexed data structure with adjacencies, which, however, cannot support navigation through vertices and edges, since only the encoded relations plus boundary relations for tetrahedra can be retrieved efficiently.

8. Concluding Remarks

We have described the design and the implementation of a new data structure, that we called thenon-manifold indexed data structure with adjacencies (NMIA), which can repre- sent any three-dimensional abstract simplicial complex in which any 2-simplex is on the boundary of at most two 3- simplexes. The NMIA structure is compact, since it encodes only the vertices and the top simplexes of the complex plus a restricted subset of topological relations among simplexes. It supports efficient navigation algorithms to retrieve topological relations, and it scales very well to the pseudo-manifold and manifold cases.

For comparison purposes, we have described a simplified version of the incidence graph for simplicial complexes, the simplified incidence graph, which, however, can only repre- sent pseudo-manifolds. While it can be shown that this latter data structure also supports navigation in optimal time, its storage cost is almost twice that of the NMIA structure.

In order to accommodate non-manifold singularities and fast navigation, the storage cost of the NMIA structure is about 1.5 times that of the simpleindexed data structure with adjacencies, which supports efficient retrieval only of theR_3i relations, withi=0,1,2,3.

In our future work, we plan to investigate extensions of the NMIA data structure to higher dimensions, to develop algorithms for updating the NMIA structure for simplifica- tion purposes. Our aim is to design and develop a multi- resolution volumetric model for non-manifold, and non- regular 3D objects, which extends the model proposed in⁸ to the three dimensional case. In this context, we plan to use the NMIA data structure to represent the adaptive meshes extracted from the multi-resolution model through selective refinement queries.

9. Acknowledgments

This work has been partially supported by the project MACROGeo (funded by the Italian Ministry of Edu- cation, University and Research under contract number RBAU01MZJ5).

References

1. B. G. Baumgart. Winged edge polyhedron representation. Technical Report CS-TR-72-320, Stanford University, Department of Computer Science, October 1972.

2. E. Brisson. Representing geometric structures inddi- mensions: Topology and order. InProceedings 5th ACM Symposium on Computational Geometry, pages 218–227. ACM Press, June 1989.

3. E. Bruzzone, and L. De Floriani. Two data structures for building tetrahedralizations. The Visual Computer, 6(5): 266–283, 1990.

4. S. Campagna, L. Kobbelt, and H.-P. Seidel. Directed edges - a scalable representation for triangle meshes.

Journal of Graphics Tools, 4(3), 1999.

5. W. Charlesworth and D. C. Anderson. Applications of non-manifold topology. InProceedings Computers in Engineering Conference and Engineering Database Symposium, pages 103–112. ASME, 1995.

6. P. Cignoni, L. De Floriani, P. Magillo, E. Puppo, and R. Scopigno. Selective refinement queries for volume visualization of unstructured tetrahedral meshes IEEE Transactions on Visualization and Computer Graph- ics,to appear, 2003.

7. L. De Floriani, M. M. Mesmoudi, F. Morando, and E. Puppo. Non-manifold decomposition in arbitrary dimensions. In A. Braquelaire, J.-O. Lachaud, and A. Vialard, editors,Discrete Geometry for Computer Imagery, Lecture Notes in Computer Science, volume 2301, pages 69–80. Springer-Verlag, 2002. Extended version to appear inGraphical Models, 2003

8. L. De Floriani, P. Magillo, E. Puppo, and D. Sobrero.

A multi-resolution topological representation for non- manifold meshes. InProceedings 7th ACM Symposium on Solid Modeling and Applications (SM02), 2002.

Saarbrucken, Germany, June 17-21. Extended version to appear inComputer-Aided Design, 2003.

9. L. De Floriani, F. Morando and E. Puppo. Represen- tation of Non-manifold Objects Through Decomposi- tion into Nearly Manifold Parts. InProceedings 8th ACM Symposium on Solid Modeling and Applications (SM03), 2003. Seattle, USA, June 16-20, 2003.

10. H. Desaulnier and N. Stewart. An extension of manifold boundary representation to r-sets. ACM Trans. on Graphics, 11(1):40–60, 1992.

11. D. Dobkin and M. Laszlo. Primitives for the manipulation of three-dimensional subdivisions.Algorithmica, 5(4):3–32, 1989.

12. H. Edelsbrunner. Algorithms in Combinatorial Geom- etry. Springer-Verlag, 1987.

(11)

13. B. Falcidieno and O. Ratto. Two-manifold cell decomposition of r-sets. In A. Kilgour and L. Kjelldahl, editors,Proceedings EUROGRAPHICS ’92, volume 11, pages 391–404, September 1992.

14. A. Gueziec, G. Taubin, F. Lazarus, and William Horn.

Converting sets of polygons to manifold surfaces by cutting and stitching. In Scott Grisson, Janet McAnd- less, Omar Ahmad, Christopher Stapleton, Adele New- ton, Celia Pearce, Ryan Ulyate, and Rick Parent, editors, Conference abstracts and applications: SIG- GRAPH 98, July 14–21, 1998, Orlando, FL, Computer Graphics, pages 245–245, New York, NY 10036, USA, 1998. ACM Press.

15. L. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and computation of Voronoi di- agrams. ACM Trans. on Graphics, 4(2):74–123, April 1985.

16. E. L. Gursoz, Y. Choi, and F. B. Prinz. Vertex-based representation of non-manifold boundaries. In M. J.

Wozny, J. U. Turner, and K. Preiss, editors,Geometric Modeling for Product Engineering, pages 107–130. El- sevier Science Publishers B.V., North Holland, 1990.

17. K. I. Joy, J. Legakis, R. MacCracken. Data Struc- tures for Multiresolution Representation of Unstruc- tured Meshes In G.Farin, H. Hagen, B. Hamann, editors,Hierarchical Approximation and Geometric Meth- ods for Scientific Visualization, Springer Verlag, Hei- delberg, 2002.

18. V. A. Kovalevsky. Finite topology as applied to image analysis. Computer Vision, Graphics, and Image Pro- cessing, 46(2):141–161, May 1989.

19. S.H. Lee and K. Lee. Partial Entity structure: a fast and compact non-manifold boundary representation based on partial topological entities. InProceedings of the Sixth ACM Symposium on Solid Modeling and Appli- cations, pp.159-170. ACM, June 2001. Ann Arbor, Michigan.

20. P. Lienhardt. N-dimensional generalized combinatorial maps and cellular quasi-manifolds. Int. Journal of Comp. Geom. and Appl., 4(3):275–324, 1994.

21. H. Lopes and G. Tavares. Structural operators for modeling 3-manifolds. InProceedings of the Fourth ACM Symposium on Solid Modeling and Applications, pages 10–18. ACM, May 1997. Atlanta, Georgia, May 14-16.

22. Y. Luo and G. Lukács. A boundary representation of form features and non-manifold solid objects. InProc.

First ACM Symposium on Solid Modeling and Applica- tions, Austin, TX, June 1991.

23. M. Mantyla.An Introduction to Solid Modeling. Com- puter Science Press, 1983.

24. S. McMains and C. S. J. Hellerstein, Out-of-core building of a topological data structure from a polygon soup InProceedings Sixth ACM Symposium on Solid Mod- eling and Applications, Ann Arbor, Michigan, 2001, pages 171–182.

25. A. Paoluzzi, F. Bernardini, C. Cattani, and V. Ferrucci.

Dimension-independent modeling with simplicial complexes.ACM Transactions on Graphics, 12(1):56–102, January 1993.

26. J. Rossignac and D. Cardoze. Matchmaker: Mani- fold BReps for non-manifold r-sets. In Willem F.

Bronsvoort and David C. Anderson, editors,Proceed- ings of the Fifth ACM Symposium on Solid Modeling and Applications, pages 31–41. ACM, June 1999.

27. J.R. Rossignac and M.A. O’Connor. SGC: A dimension-independent model for point sets with internal structures and incomplete boundaries. In J.U. Turner M. J. Wozny and K. Preiss, editors,Geo- metric Modeling for Product Engineering, pages 145–

180. Elsevier Science Publishers B.V. (North–Holland), Amsterdam, 1990.

28. J. Rossignac, A. Safonova, A. Szymczak. 3D compres- sion Made Simple: Edgebreaker on a Corner Table. In Proceedings Shape Modeling International 2001, Gen- ova, Italy, May 2001

29. K. Weiler. The Radial Edge data structure: A topological representation for non-manifold geometric boundary modeling. In J.L. Encarnacao, M.J. Wozny, H.W.

McLaughlin, editors, Geometric Modeling for CAD Applications, pages 3–36. Elsevier Science Publishers B.V. (North–Holland), Amsterdam, 1988.

30. Y. Yamaguchi and F. Kimura. Non-manifold topology based on coupling entities. IEEE Computer Graphics and Applications, 15(1):42–50, January 1995.