Digital Geometry Processing / Core Mesh Data Structures

Core Mesh Data Structures in C++

In our experience the small number of data structures described here are sufficient to implement the vast majority of basic digital geometry processing operations.

A simple data structure to represent a polygon mesh is composed of two arrays; one array of floating point variables, which we name coord represents the 3D vertex coordinates of the mesh, and one array of integers, which we name coordIndex, represents the faces of the mesh. This representation roughly corresponds to a VRML'97 IndexedFaceSet node with no properties, such as the tetrahedron shown in the following figure.

 #VRML V2.0 utf8
 Shape {
   geometry IndexedFaceSet {
     coord Coordinate {
       point [
          1.633 -0.943 -0.667 # V0
          0.000  0.000  2.000 # V1
         -1.633 -0.943 -0.667 # V2
          0.000  1.886 -0.667 # V3
       ]
     }
     coordIndex [
       0 1 2 -1 # F0
       3 1 0 -1 # F1
       2 1 3 -1 # F2
       2 3 0 -1 # F3
     ]
   }
 }

The Virtual Reality Modeling Language (VRML’97) is the International Standard ISO/IEC 14772-1:1997. The VRML2 Cheat Sheet is a summary of all the VRML'97 nodes. Formally, in VRML'97 an IndexedFaceSet node has a variable named coord which must have as value a node of type Coordinate, and a Coordinate node has a single variable named point, which is an array of floating point numbers. In this page, when we refer to the array coord we mean the array point of the Coordinate node.

If the mesh has V vertices, the size of the coord array should be 3V. Vertex indices are assigned consecutive indices from 0 to V-1. If j is a vertex index in the range 0≤j<V, then the three coordinates of the vertex are x=coord[3j], y=coord[3j+1], and z=coord[3j+2].

Each face is a cycle three or more of vertex indices without repetition. Faces with holes cannot be represented. These cycles are stored in consecutive order in the coordIndex, with each face terminated by the value -1. In particular, the last value of the coordIndex array should be equal to -1.

The tetrahedron shown above has 4 vertices and 4 triangular faces. face 0 is (0,1,2), face 1 is (3,1,0), face 2 is (2,1,3), and face 3 is (2,3,0).

Arrays

It is often the case that the sizes of the arrays are not known in advanced, and that the arrays need to change in size as a result of operations. As a result, the most fundamental data structures used to represent polygon meshes are the variable size arrays of integers and floating point numbers. In C++ these data structures correspond to the STL templated classes vector<int> and vector<float>.

Next : Faces

Brown University School of Engineering

ENGN 2501 Digital Geometry Processing

Spring 2023

Core Mesh Data Structures in C++

Arrays

Next : Faces