Core Mesh Data Structures in C++

Faces

Many algorithms require efficient random access to the mesh faces, and the coordIndex array does not provide this functionality. In the coordIndex array face 0 starts at the beginning of the array, face 1 immediately after the first -1, face 2 immediately after the second -1, and in general, to find the beginning of face k requires a linear traversal of the coordIndex array during which the number of -1's encountered must be counted. We define the Faces data structure to solve this problem. 

 class Faces {
   public:
             Faces(const int nV, const vector<int>& coordIndex);
     int     getNumberOfVertices()                    const;
     int     getNumberOfFaces()                       const;
     int     getNumberOfCorners()                     const;
     int     getFaceSize(int iF)                      const;
     int     getFaceFirstCorner(const int iF)         const;
     int     getFaceVertex(const int iF, const int j) const;
     int     getCornerFace(const int iC)              const;
     int     getNextCorner(const int iC)              const;
 }

The constructor Faces(int V, vector<int>& coordIndex) creates an instance of the data structure for a mesh with V vertices, and faces defined by the coordIndex array. Providing as arguments a value of V≤0 or a coordIndex array with a non-zero element value iV outside of the range 0≤iV<V, faces with less than three elements, or faces with repeated vertex indices, are errors. The methods getNumberOfVertices() provides the total number of vertex of the mesh, i.e., the value of the parameter V provided to the constructor. The method getNumberOfFaces() returns the total number of faces of the mesh, i.e., the number of -1's in the coordIndex array.

We define the corners of the mesh as all the pairs (iF,iV), where iF is a face index, and iV is a vertex index contained in face iF. For example, in the case of the tetrahedron shown above, the corners are 

  (0,0),(0,1),(0,2),
  (1.3),(1.1),(1,0),
  (2,2),(1,2),(3,2),
  (2,3),(3,3),(0,3)

Since there is a 1-1 correspondence between mesh corners and non-negative elements of the coordIndex array, we define the index of a corner as the location of the corresponding non-negative element in the coordIndex array. The locations of negative elements of the coordIndex array are invalid corner indices. For example, in the case of the tetrahedron, the association between corner indices and corners is 

  0→(0,0),1→(0,1),2→(0,2),
  4→(1.3),5→(1.1),6→(1,0),
  8→(2,2),9→(1,2),10→(3,2),
  12→(2,3),13→(3,3),14→(0,3)
and the corner indices 3,7,11, and 15 are invalid.

Using these indexing scheme there is no need to allocate additional memory to to store the mesh corners. Enumerating the corners consecutively would have required additional memory to represent the mapping from corner indices to coordIndex array locations and the inverse of this mapping, which double or triple the amount of memory needed to represent the faces and corners.

The method getNumberOfCorners() returns the size of the coordIndex array, including the -1 face separators, not the number of non-negative elements of the coordIndex array. As described above, including the -1 face separators as (invalid) corners simplify many of the algorithms. The method getFaceSize(iF) returns the number of corners in face iF. The method getFaceFirstCorner(iF) returns the index of the first corner of face iF. The method getFaceVertex(iF,j) returns the vertex index of the j-th corner of face iF. Calling the last three methods with a value of iF outside of the range 0≤iF<getNumberOfFaces(), or the last method with a value of j outside of the range 0≤j<getNumberOfCorners(iF), is an error.

The method getCornerFace(iC) returns the face index of the face which contains the corner associated with the corner index iC, if corner index iC is valid. Otherwise, getCornerFace(iC) returns the value -1. In particular, if the index iC corresponds to a -1 face separator, getCornerFace(iC) returns the value -1. For example, in the case of the tetrahedron, getCornerFace(2)==0 and getCornerFace(9)==3.

Finally, the method getNextCorner(iC) returns the index of the corner which follows the corner associated with the corner index iC within the face which contains the corner associated with the corner index iC. For example, in the case of the tetrahedron, we have getNextCorner(9)==10 and getNextCorner(10)==8.

Next : Edges

Core Mesh | Faces | Edges | Graph | HalfEdges | Partition | PolygonMesh | Queue