Linear Subdivision - cmu462/Scotty3D GitHub Wiki

Unlike most other global remeshing operations, linear (and Catmull-Clark) subdivision will proceed by completely replacing the original halfedge mesh with a new one. The high-level procedure is:

1. Generate a list of vertex positions for the new mesh.
2. Generate a list of polygons for the new mesh, as a list of indices into the new vertex list (a la "polygon soup").
3. Hand these two lists to the method HalfedgeMesh::rebuild, which rebuilds the halfedge connectivity from scratch.

Given these lists, rebuild will take care of allocating halfedges, setting up next and twin pointers, etc., based on the list of polygons generated in step 2---this routine is already implemented in the Scotty3D skeleton code.

Both linear and Catmull-Clark subdivision schemes will handle general n-gons (i.e., polygons with n sides) rather than, say, quads only or triangles only. Each n-gon (including but not limited to quadrilaterals) will be split into n quadrilaterals according to the following template:

The high-level procedure is outlined in greater detail in HalfedgeMesh::subdivideQuad.

For global linear or Catmull-Clark subdivision, the strategy for assigning new vertex positions may at first appear a bit strange: in addition to updating positions at vertices, we will also calculate vertex positions associated with the edges and faces of the original mesh. Storing new vertex positions on edges and faces will make it extremely convenient to generate the polygons in our new mesh, since we can still use the halfedge data structure to decide which four positions get connected up to form a quadrilateral. In particular, each quad in the new mesh will consist of:

• one new vertex associated with a face from the original mesh,
• two new vertices associated with edges from the original mesh, and
• one vertex from the original mesh.

For linear subdivision, the rules for computing new vertex positions are very simple:

• New vertices at original faces are assigned the average coordinates of all corners of that face (i.e., the arithmetic mean).
• New vertices at original edges are assigned the average coordinates of the two edge endpoints.
• New vertices at original vertices are assigned the same coordinates as in the original mesh.

These values should be assigned to the members Face::newPosition, Edge::newPosition, and Vertex::newPosition, respectively. For instance, f->newPosition = Vector3D( x, y, z ); will assign the coordinates (x,y,z) to the new vertex associated with face f. The general strategy for assigning these new positions is to iterate over all vertices, then all edges, then all faces, assigning appropriate values to newPosition. Note: you must copy the original vertex position Vertex::position to the new vertex position Vertex::newPosition; these values will not be used automatically.

This step should be implemented in the method HalfedgeMesh::computeLinearSubdivisionPositions in meshEdit.cpp.

Once the new vertex positions have been assigned to elements of the halfedge mesh, they need to be accumulated into a single list of all vertex positions in the new mesh, which will be handed to HalfedgeMesh::rebuild. It is important that vertex coordinates in this list appear in the same order they were indexed! For instance, if you index vertices, then edges, then faces, then the final vertex coordinate list should likewise contain coordinates from vertices, then coordinates from edges, then coordinates from faces. These vertex coordinates can be accumuluated using an object of type vector<Vector3D>, i.e., a dynamically-sized array of vertex positions. The basic strategy is to loop over all vertices, then all edges, then all faces, calling push_back to append each new vertex coordinate to the list. (See the next section for further discussion of the vector class.) Further details are provided in the in-line comments.

This last step should be implemented in the method HalfedgeMesh::buildSubdivisionVertexList in meshEdit.cpp.

In addition to new (x,y,z) coordinates, we also need to assign a unique index to each vertex in the new mesh---including those that are associated with edges and faces. In other words, every vertex, edge, and face in the mesh will be assigned an integer between 0 and N-1, where N is the total number of vertices plus edges plus faces in the original mesh. A simple strategy for assigning these indices is:

1. Initialize a counter to zero.
2. Iterate over vertices, assigning the index of the current vertex to the counter value, and incrementing the counter.
3. Iterate over edges, assigning the index of the current edge to the counter value, and incrementing the counter.
4. Iterate over faces, assigning the index of the current face to the counter value, and incrementing the counter.

Note that the particular choice of indices does not matter---the only things you must guarantee are that (i) every mesh element is assigned a valid index, and (ii) no two mesh elements share the same index.

Recall that in linear and Catmull-Clark subdivision all polygons are subdivided simultaneously. In other words, if we focus on the whole mesh (rather than a single polygon), then we are globally

• creating one new vertex for each edge,
• creating one new vertex for each face, and
• keeping all the vertices of the original mesh.

These vertices are then connected up to form quadrilaterals (n quadrilaterals for each n-gon in the input mesh). Rather than directly modifying the halfedge connectivity, these new quads will be collected in a much simpler mesh data structure: a list of polygons. Note that with this subdivision scheme, every polygon in the output mesh will be a quadrilateral, even if the input contains triangles, pentagons, etc.

In Scotty3D, a list of polygons can be declared as

vector< vector<Index> > quads;

where vector is a class from the C++ standard template library, representing a dynamically-sized array. An Index is just another name for a size_t, which is the standard C++ type for integers that specify an element of an array. Polygons can be created by allocating a list of appropriate size, then specifying the indices of each vertex in the polygon. For example:

vector<Index> quad( 4 ); // allocate an array with four elements
// Build a quad with vertices specified by integers (a,b,c,d), starting at zero.
// These indices should correspond to the indices computing when assigning vertex
// positions, as described above.
quad[0] = a;
quad[1] = b;
quad[2] = c;
quad[3] = d;

Once a quad has been created, it can be added to the list of quads by using the method vector::push_back, which appends an item to a vector:

vector< vector<Index> > newPolygons;
newPolygons.push_back( quad );

The full array of new polygons will then be passed to the method HalfedgeMesh::rebuild, together with the new vertex positions.

This step should be implemented in the method HalfedgeMesh::buildSubdivisionFaceList in meshEdit.cpp.