In our representation, an object is a collection of surface components.
struct Obj{
Container<Surface*> surfaces;
}
The surface is structured as S= (V, E, F, B) where V, E, F, B are the collections of vertices, edges, faces and boundary curves respectivelly.
These sets are stored in containers of pointers to the correspondent topological data structures. The boundary container simply stores pointers to one of the edges of each boundary curve and it is the topological core of our data structure. Indeed it deals effectivelly with all topological changes, i.e., the increase or decrease in the number of boundary curves. Note that a compact surface will have an empty set as its boundary.
struct Surface {
Container<Face*> faces;
Container<Edge*> edges;
Container<Vertex*> vertices;
Container<Edge*> bndries;
}
The face structure stores a pointer to the first half-edge of its outer loop. Here, we assume triangular faces and thus, the face loop contains exactly three edges.
struct Face {
Half_Edge* he_ref;
}
An edge is formed by two half-edges. In the case it is representing a boundary edge one of these half-edges points to a null face.
struct Edge {
Half_Edge he[2];
}
The half-edge is the central topological element of the data structure. It stores a pointer to its initial vertex, a pointer to the next half-edge in the face loop, and pointers to the edge and face it belongs. Note that the mate half-edge can be accessed through the pointer to its parent edge.
struct Half_Edge {
Vertex* org_ref;
Half_Edge* nxt_ref;
Face* f_ref;
Edge* e_ref;
}
The vertex structure stores one pointer to an incident half-edge. In the case of a boundary vertex, this half-edge is part of the boundary curve. This representation makes it trivial to identify if a vertex is on the boundary or is in the interior of the surface. Also, it is instrumental not only for the implementation of the vertex star iterator, but also for the boundary curve iterator. The vertex structure can also hold additional data, such as geometry (e.g. position, normals), texture and parametric coordinates.
struct Vertex { Half_Edge* star_ref; int level; }
The point data structure described below stores a pointer to the vertex. It represents a "bridge" between geometry and topology. It also stores geometric data of the vertex. Note that if the reference to the vertex is null then the point does not belong to the mesh.
struc Point{ Vertex* v; Data* d; }
Surfaces reconstructions are typical examples where this structure is very usefull. Indeed their geometric operations acts on points (some may belong to the boundary or not) whereas mesh vertices attach then by handle operations whenever new thiangles are created.