Материал: [2.1] 3D Imaging, Analysis and Applications-Springer-Verlag London (2012)

Table 4.2 Space and time complexity of mesh data structures for a mesh of M faces and N vertices

Winged-edge. The best known boundary representation (B-rep). Each edge stores pointers to the two vertices at their ends, the two faces bordering them, and pointers to four of the edges connected to the end points. This structure allows edge-vertex and edge-face queries to be answered in constant time, though other adjacency queries can require more processing.

Halfedge. Also known as the FE-structure [78] or as a doubly-connected edge list (DCEL) [4], although note that the originally proposed DCEL [43] described a different data structure. The halfedge is a B-rep structure which makes explicit the notion that an edge is shared by two faces by splitting an edge into two entities. It is restricted to representing manifold surfaces. Further implementation details are given below.

Adjacency matrix. A symmetric matrix of size N × N , which contains 1 if there is an edge between the corresponding vertices. Highly space inefficient for meshes but allows some operations to be performed by applying linear algebra to the adjacency matrix. This forms the basis of algebraic graph theory [5].

We provide a summary of the time and space complexity of a representative sample of mesh data structures in Table 4.2. Note that different structures that support operations with the same asymptotic complexity, may not be equally efficient in practice. For example, finding all vertices of a face using a winged-edge structure requires traversal from the face list to the edge list to the vertex list, whereas the vertex-face list structure can traverse directly from faces to vertices. Also note that, where we specify constant time, we refer to constant time per piece of information. So, for example, using a halfedge all of the edges incident on a vertex can be computed in a time which is linear in the number of edges incident on the vertex.

The halfedge structure allows all adjacency queries to be computed in constant time, while requiring only a modest overhead in storage requirements. For this reason, it is a good choice as a general purpose data structure for mesh processing. We describe the halfedge data structure in more detail in the following sections.

4.3.2.1 Halfedge Structure

The halfedge data structure comprises vertices, faces and “halfedges”. Each edge in the mesh is represented by two halfedges. Conceptually, a halfedge is obtained by dividing an edge down its length. Figure 4.11 shows a small section of a mesh represented using the halfedge structure. Halfedges store pointers to the following:

Fig. 4.11 Halfedge structure

1.The next halfedge in the facet (and so they form a circularly linked list around the face).

2.Its companion “opposite” halfedge.

3.The vertex at the end of the halfedge.

4.The face that the halfedge borders.

Note that halfedges can be linked in clockwise or counterclockwise direction about a face, but this must be consistent over the mesh.

Concretely, in the C programming language, a minimal halfedge structure would be implemented as follows:

s t r u c t h a l f e d g e

{

h a l f e d g e n e x t ;

h a l f e d g e o p p o s i t e ;

v e r t e x i n c i d e n t v e r t e x ; f a c e i n c i d e n t f a c e t ;

} ;

In the halfedge data structure, a vertex stores 3D position (as well as any other pervertex information) and a pointer to one of the halfedges that uses the vertex as a starting point:

s t r u c t v e r t e x

/ / A d d i t i o n a l per−v e r t e x d a t a h e r e h a l f e d g e o u t g o i n g e d g e ;

}

Finally, a facet stores any per-facet information (for example, face normals) and a pointer to one of the halfedges bordering the face:

s t r u c t f a c e

{

/ / A d d i t i o n a l per− f a c e t d a t a h e r e h a l f e d g e b o r d e r e d g e ;

}

With the halfedge structure to hand, traversals are achieved by simply following the appropriate pointers. In the simplest case, the vertices adjacent to an edge can be found as follows:

A similar approach can be applied for adjacent faces. Traversing the perimeter of a face is simply a case of following a circularly linked list:

h a l f e d g e e d g e = f a c e −>b o r d e r e d g e ;

Another useful operation is iterating over all the edges adjacent to a vertex (this is important for range searching and also for vertex deletion resulting from an edge collapse, where pointers to this vertex must be changed to point to the vertex at the other end of the deleted edge). This is implemented as follows:

h a l f e d g e e d g e = v e r t −>o u t g o i n g e d g e ;

Many other traversal operations can be implemented in a similar manner. In the context of range searching, edge lengths need to be considered (i.e. the Euclidean distance between adjacent vertices). Dijkstra’s shortest path algorithm can be applied in this context for range searching using approximate geodesic distances or for exact geodesic distances the Fast Marching Method can be used [30]. Exercise 7 asks you to implement Dijkstra’s shortest path algorithm on a halfedge structure.

Fig. 4.12 Creation of (a) F-face, (b) E-face and (c) V-face in the Doo-Sabin subdivision scheme

1.Every vertex vi , where {i} KN , yields a new vertex, vi,f , for every face f = {i, j, k, . . . } KN that has vi as a vertex. This is known as the image of vi in f .

2.The position of vi,f can be computed using a number of different rules. A simple scheme sets vi,f to the midpoint of the centroid of f and the vertex position vi , i.e.

3.Image vertices are connected to form three kinds of new face, the first of which is an F-face. An F-face is a smaller version of an original face, f =

{i, j, k, . . . } KN , formed by connecting the image vertices of the vertices of f , i.e. vi,f , vj,f , vk,f , . . . . If f is an n-sided face then so is the resulting F-face. This process is shown in Fig. 4.12(a).

4.The second type of new face is an E-face. For every edge {i, j } KN shared by two vertices f1 and f2, a new rectangular face is formed from the four image

vertices created from the endpoints of the edge, i.e. vi,f1 , vi,f2 , vj,f1 and vj,f2 . This process is shown in Fig. 4.12(b).

5.The final type of new face is a V-face. For every vertex {i} KN , a new face is created by connecting the image vertices of vi in all faces to which vi is adjacent. If vi has degree n then the new V-face is n-sided. This process is shown in Fig. 4.12(c).

To summarize, the subdivided mesh will comprise a quadrilateral for each edge in the original mesh, an n-sided polygon for each n-sided polygon in the original mesh and an n-sided polygon for each degree-n vertex in the original mesh. An example of applying the Doo-Sabin scheme to a quadrilateral mesh is shown in Fig. 4.13. After one round of subdivision, all vertices have degree four. Hence subsequent divisions