This document is intended to give an overview of the SDLib subdivision surface library. It is aimed at the developer who is building an application around SDLib. This paper first gives an overview of subdivision surface. It then explains implementation details of SDLib, and provides details of the assumptions underlying the SDLib library. It is expected that the reader also has access to the more formal documentation supplied with the SDLib release, and also to the SDLib source code. While those are the most precise description of what goes on in SDLib, this document is intended to give a gentler high-level explanation.
Subdivision surfaces are a powerful way of modeling smooth surfaces of arbitrary topology. As a motivating, example, consider the 3-way join shape that is depicted in Figure 1. The complex topology around the join would require complex modeling or careful blend operations if it were created using NURBS surfaces. However, subdivision surfaces make this and other topologically complex shapes very easy to build.
Figure 1. Subdivision surface motivation. This smoothly joining 3-way pipe is difficult to build with NURBS patches, but quite simple to model using subdivision surfaces.
SDLib implements a particular kind of subdivision surface known as a Catmull-Clark subdivision surface. A Catmull-Clark subdivision surface is designed to exactly reproduce uniform bicubic B-spline surfaces in most places. This makes it especially useful for interaction with B-spline surfaces.
Mathematically, all subdivision surface work by beginning with a base polygonal mesh, and repeatedly subdividing the mesh by adding new vertices and faces.
The progress of Catmull-Clark subdivision is depicted in Figure 2. The left side of the figure shows an octahedron mesh made of 8 triangles, connected between vertices of valence 4 (the valence of a vertex measures the number of edges connected to that vertex). This octahedron will be used as the base mesh for this particular example. The right side of Figure 2 shows the result of one level of subdivision on the octahedron base mesh. Note that each original triangle in the base mesh has been subdivided into 3 quad faces by adding a new vertex on the middle of each edge and at the center of each face. This new mesh is known as the level 1 mesh, just as the octahedron base mesh itself is called the level 0 mesh. Although the base mesh can have faces with any number of edges, meshes at level 1 and later levels will only be composed of faces that are quads.
Figure 2. Subdividing an octahedron mesh. The octahedron on the left will be used as the base mesh for further subdivision. The mesh on the right shows the result of a single Catmull-Clark subdivision of the octahedron mesh.
We can continue the subdivision by subdividing the level 1 mesh in Figure 2 into the mesh shown in Figure 3. The level 2 mesh has 4 times the number of faces of the level 1 mesh. In general, a level n mesh will have 4n times the faces, edges, and vertices of the original base mesh. Keep this in mind, since it implies an exponential blowup in the memory and processing time for increasing levels of n. In general, level 4 is quite detailed for most purposes, and it is usually possible to do plenty of detailed surface modeling without going any deeper than level 2 or 3. Although SDLib supports deeper levels, they should be used with caution, because the extra memory and processing required can slow things down a lot.
Figure 3. Further subdivision of the octahedron. The mesh on the left shows the octahedron after 2 levels of subdivision. The surface on the right is the Catmull-Clark subdivision surface that results in the limit of the subdivision process.
If the subdivision of the octahedron is repeated an infinite number of times, it yields the surface on the right side of Figure 3. This surface, known as the limit surface, is the Catmull-Clark subdivision surface that arises from infinitely subdividing the octahedron base mesh. Fortunately, it is not necessary to subdivide an infinite number of times – the points on the limit surface that are rendered in Figure 3 can be computed from previous mesh levels using known formulas.
Recall that the Catmull-Clark surface is exactly a B-spline surface in most places. It turns out that the mesh vertices at levels 0, 1, 2, and so on are the analog of NURBS control vertices in how they affect the underlying subdivision surfaces. That means that if the vertices are moved, they have an effect on the surface that feels much like control vertices do on NURBS surfaces. For example, Figure 4 shows the level 1 vertices in relation to the limit surface. However, the range of their effect depends on the level. A level 0 control vertex has a large, coarse effect on the surface, whereas a level 2 control vertex has a tighter, finer effect on the surface. This means that editing is available at a variety of levels of detail.
Figure 4. Control vertices. The yellow vertices can be used to edit the underlying limit surface in a manner exactly like B-spline control vertices can edit a NURBS surface.
Although a subdivision surface is very close to a NURBS surface, it is not identical. In regions where all the mesh faces are quads that are composed entirely of valence 4 vertices, the resulting surface is exactly a uniform bicubic B-spline surface whose control vertices are given by the same mesh vertices. However, in regions where there are irregular vertices (vertices of valence other than 4), such as the new level 1 vertices built in the center of the level 0 triangles, the surface immediately near those vertices is not equivalent to a B-spline. At finer levels of detail, as the subdivision level increases, the irregular vertices become relatively rare, and the control vertices act on the surface nearly everywhere identically to bicubic uniform B-spline control vertices.
The above description of a subdivision surface begins with a polygonal base mesh that yields a smooth surface in the limit. Given an input base mesh, one can edit the resulting surface by editing the control points at
the level 0, or base level, of the surface.
However, control vertices at other levels can also have an effect on the surface. One can change the surface by editing a control vertex at level 1, or 2, or finer. The finer the level, the finer the effect on the underlying surface.
Finer-level editing can be used to add detail to a shape. For example, a head modeled mostly at the base shape can be edited at finer levels to add detail such as a wart or dimple.
However, there is a price to be paid in additional memory. Finer-level control vertices are available when desired, but each additional level of the surface multiplies the amount of memory allocated by roughly 4. This means that editing at level 5 requires roughly 4*4*4 = 256 times the amount of memory used for editing at level 2.
The finer-level details may be defined as offsets from their coarser-level parent control vertices. This means that once you have set up the fine-level edit information, re-editing the coarser-level data will not lose the fine-level detail. Instead, the finer-level data will move along in sync with the coarser-level edits. . Figure 5 shows an example of this, with a coarse-level and fine-level edit on the same shape.
Figure 5. Hierarchical editing. The mesh on the left shows a level 0 edit applied to the shape of Figure 1. The mesh in the middle shows a level-3 edit. The two edits may be combined in a single edited shape, as shown on the right.
Usually, a subdivision surface is smooth everywhere. However, it is possible to selectively set edges in the surface to be non-smooth, or crease edges. A crease edge can be set to be sharp, in which case a sharp corner will appear in the place corresponding to that edge in the limit surface. A vertex can also be set to be sharp on its own, in which case it will have the appearance of the tip of a cone.
A vertex has different effects depending on how many crease edges come from it:
- 0 crease edges: The vertex is the usual smooth vertex, and has no crease effects.
- 2 crease edges: The vertex is in the middle of a crease. Its position will be computed using uniform cubic B-spline curve rules.
- 1 cre
ase edge: The vertex is at the end of a crease. It is surrounded by smooth surface, except for a single sharp crease coming from it. This is called a dart, and is shown in the center of Figure 6.
- 3 or more sharp creases: The vertex is considered a sharp corner vertex, such as arises at the corner of a cube with 3 sharp edges coming from it.
Figure 6. Examples of creases. The left image shows a crease made by setting the top 4 edges of the cube control mesh to a sharp crease. The center image shows a dart, or disappearing crease. The right image shows a single edge of the cube set to a pinch, or partial crease.
As Figure 6 also shows, it is possible to make a pinch in the surface – the surface will still be smooth at that area, but the region corresponding to the edge will be pulled closer to looking crease-like than occurs without setting the pinch.
Just as with control vertices, SDLib allows creases and pinches to be edited at any level in the hierarchy.
In this section, we delve into the specifics of modeling subdivision surfaces with SDLib.
To edit a surface from scratch in SDLib, it is first necessary to build the base polygonal mesh. This input polygonal mesh is passed off to SDLib’s SubdSurface constructor, which then builds a subdivision surface from it. The polygonal mesh is supplied as an SDLib PolygonCollection object. It may be built in a polygonal mesh editor, and then read into a PolygonCollection. For at least version 1.0 of SDLib, the mesh read in must follow these requirements:
- Connectivity must be specified. Regions that are intended to be connected in the subdivision surface must also be connected in the input mesh. For example, if the input mesh is a cube, and the resulting surface is intended to be one seamless surface, the input mesh topology must likewise specify that each of the 6 cube faces must be connected to its neighbors. It is possible to use as input a single mesh that breaks into multiple disconnected components – such a mesh will result in a surface that is similarly disconnected. For example, two separated cubes may be used as input to define a subdivision surface made of two disconnected blobs.
- The mesh must be manifold. This means in practice that along a single edge in the input mesh, there can be at most 2 faces connected to the 2 sides of the edge. Additionally, both faces meeting along the same edge must be oriented the same way. (This disallows, for example, a mesh description of a Möbius strip.)
The following words have special meaning within SDLib:
- base level : Level 0 of the surface. The base level connectivity corresponds exactly to that of the input polygonal mesh.
- base face : A face at level 0 of the surface.
- base vertex : A vertex at level 0 of the surface.
- boundary edge : The outside edge of the surface is computed as if it were a crease..
- coarser level : A level with coarser features with respect to the current level. For level 1, level 0 is a coarser level. Level 0 is the coarsest possible level, and has no coarser level
- CV : Abbreviation for “control vertex.”
- dart : A vertex at the middle of the surface with exactly 1 crease edge coming from it..
- feature : A face, edge, or vertex. Features are used on a polygonal mesh, or on a subdivision surface at any level.
- finer level : A level with finer features with respect to the current level. For level 1, level 2 is a finer level.
- parent feature : The feature at the coarser level of the surface that is “above” this feature in the surface hierarchy. It corresponds to the same part of the surface, but in the case of a parent face or parent edge, it is over a larger region.
- reference face : A face at level 1. Reference faces are used to organize the structure of the subdivision surface because, unlike base level faces, they are guaranteed to always be 4-sided.
- vertex influence : The influence on a vertex position due to certain coarser-level vertices. This is explained in more detail below
The rest of this section will explain some of the operations supplied by various methods in SDLib. In this subsection, we will examine some of the rules of thumb that are used consistently within SDLib. Some of these terms may not make complete sense before reading the rest of the document, but they are provided here as a central glossary.
- Counter-clockwise index ordering. The ordering of adjacent features always follows the right-hand rule and moves counter-clockwise. For example, on a face, vertex 0 is followed by vertex 1, and then vertex 2, going counter-clockwise around the face. For a vertex, adjacent face 0 is followed immediately clockwise by face 1.
- Counting. Counting always begins at 0. Thus, a face with n vertices has vertices (0, 1, …, n-1), in counter-clockwise order around the face. A valid index is ordinarily between 0 and n-1.
- “Safe” adjacency. For all adjacency methods, an accompanying “Safe” method exists. A “Safe” method has the same name, but with the “Safe” prefix. This allows queries for indices that may be out of the usual allowed [0..(n-1)] range by moving around and getting the vertex in a modulo fashion. For example, asking a face for its Vertex(-1) is an illegal operation that fails a debug assertion. However, it is legal to ask a face for its SafeVertex(-1), which returns the vertex (n-1) for that face. Safe methods have slightly extra overhead over the usual operations, but allow convenient indexing within loops for the (i+1) or (i-1) adjacency features.
- Edges relating to vertices. Edge i always goes between vertex i and vertex (i+1) when indexed from a face.
- Faces relating to vertices. As seen from a face, face i is the face across edge i. Hence, it is also adjacent between vertex i and vertex (i+1).
- Faces relating to edges on a vertex. Face i from a vertex is between edge iand edge i+1.
- Boundary edges. If a face in the input mesh is not connected to any other face along edge i, then that edge is considered a boundary. Additionally, the edge is a boundary edge, then any vertices on that edge are also considered boundary vertices.
- NULL index references. If an adjacent face or edge for a valid index does not exist because it is being queried across a boundary then NULLIndex is returned.
- Face size. All faces must have at least 3 vertices – faces of fewer vertices are not allowed. There is also an upper limit for the maximum number of vertices on a face. This constant is currently set in SQPoly::MaxVertexCount .
- Indexing and coordinates. When evaluating a position on the subdivision surface, the parameters may be thought of as being taken with respect to a reference face, where the origin is at that reference face’s vertex 0.
- Feature data. For memory reasons, explicit adjacency information is not stored at finer levels of the surface. However, some data, such as positions for each vertex, and sharpness for each edge, is stored at every level.
- SubVertex. Each feature at every level has a corresponding finer-level vertex. The SubVertex for a face is the finer-level vertex that is created by subdivision at the middle of the face. A similar thing goes for an edge.
- Debug assertions. When the SQDEBUG compile flag is turned on, it activates numerous assertion tests that are sprinkled throughout the SDLib code. If any of these assertions fails, a warning message is printed, and an exception is thrown. This can be useful for debugging a program that does not work, but it adds additional overhead. The SQDEBUG flag is turned on automatically in SDLib’s Debug configuration under Visual Studio. Under Linux, it may be turned on as a flag to gcc.
- ID. Reference and base features have unique IDs that persist across save and restore.
Adjacency principles for an example face are illustrated in Figure 7:
Figure 7. Face indexing. This shows indexing of adjacent vertices vi, edges ei, and faces fi around face f
Position information is supported at every vertex of the subdivision surface, at every level. Texture (R,G,B, and opacity) information can be set as well, but differs in some respects:
- Each vertex has exactly one position. A vertex along a texture boundary can have different texture depending on which face the vertex is being referenced from.
- For memory reasons, SDLib only supports editing texture information at base level vertices. Texture information can be queried at finer level vertices, but unlike position, there is no capability for editing texture at finer levels.
Although the PolygonMesh class is sufficient to represent a basic polygon mesh, it is insufficient on its own to completely support a subdivision surface. Hence, SDLib includes supporting classes to represent base faces, edges, and vertices.
BaseFace: A base face exactly corresponds to a face in the input mesh. It contains the full connectivity information from its corresponding face in the input mesh, and also knows about the reference faces at level 1.
BaseVertex: A base vertex also exactly corresponds to a vertex in the input mesh, and contains full connectivity for its neighbors.
BaseEdge: A base edge is stored as a half-edge going in a particular direction between two vertices.
References faces are faces at level 1. They are treated specially, since they are the coarsest level faces that are guaranteed to be 4-sided. This makes them convenient for dividing the subdivision surface into 4-sided regions. Hence, a subdivision feature at finer levels is defined relative to its reference face. When there is a possibility of several reference faces for a feature (such as occurs along borders of reference faces), a single reference face is uniquely chosen.
A base face of n vertices has n reference faces as its children. ReferenceFace i always has as its own vertex 0 a base vertex. This is illustrated in Figure 8.
A ReferenceVertex is simply a vertex on a ReferenceFace. Unlike more general SubdFeature classes, a ReferenceFace or ReferenceVertex has full adjacency pointer information to its immediate neighbors.
Figure 8. Indexing in a 5-sided base face. An n-sided base face with base vertices bv0..bvn-1 is split into n reference faces rf0…rfn-1. Each reference face rfi roots its vertex 0 at the corresponding base vertex bvi of the surface. For reference face rf1 in the figure, its 4 vertices are ReferenceVertices rv0…rv3. Also note that bv1 and rv0 refer to the same place on the surface, except that rv0 is a vertex at level 1 and bv1 is its parent vertex at level 0.
When a vertex v at level l is computed, its position is calculated as an affine combination of vertex positions at level l-1. This combination remains the same as long as the local crease information and connectivity remains the same. In SDLib, this information is stored on the vertex and is used to compute the vertex position when a coarser-level vertex is edited. A VertexInfluenceList is simply a list of (vertex, influence amount) pairs, giving the influence of coarser-level vertices on a particular vertex.
A subdivision surface in SDLib is composed of faces, vertices, and edges at every level of the surface. Together, faces, edges, and vertices are called surface features. This is done by deriving classes SubdFace, SubdEdge, and SubdVertex from a common parent class SubdFeature. In this section, some of the methods common to all features are described; later we will examine methods specific to certain features.
In order to save memory, a SubdFeature itself is not actually stored within a SUbdSurface. Instead, an object of a SubdFeature derived class knows enough information about where it refers to on the surface, and from this, the adjacency information can be inferred. This makes many of the adjacency operations somewhat complicated, but it makes memory storage far more compact, especially as the subdivision levels increase.
Each SubdFeature has a common set of information:
- The SubdSurface that the feature lives on.
- A ReferenceFace denoting the part of the surface that the feature is on. For a SubdFace, there can be only one possibility. For a SubdEdge or SubdVertex, a unique ReferenceFace is chosen to avoid ambiguity.
- The level that the feature is found on.
- A pair (i, j) of indices representing a location within the grid of possibilities for the level. The grid is rooted at the 0 vertex for the ReferenceFace, and moves with i increasing as one moves towards the ReferenceFace’s vertex 1, and j increasing as one moves towards the ReferenceFace’s vertex 3. An example showing the index possibilities within a ReferenceFace at level 2 is shown in Figure 9
Figure 9. SubdFace and SubdVertex indexing. This shows (i, j) indexing for SubdVertices and SubdFaces over a level 2 ReferenceFace. Level 1 reference vertices at the corners of the reference face are denoted by rvi
A SubdFace object can be used to represent a fac
e at any level of the surface. A SubdFace is defined by the usual SubdFeature data. Some SubdFace methods that require further explanation include:
- int IndexWithinParent() : returns the index that the parent face has to get to this SubdFace. If f.IndexWithinParent() == i then f.ParentFace().SubFace(i) == f.
- FaceClassification Classification() : returns the kind of face that this is. Possibilities include:
- BaseLevelFace : The SubdFace represents a base face. In this special case, the ReferenceFace index really gives the index of the corresponding BaseFace, and the other fields are ignored.
- InteriorFace : The SubdFace represents a face in the middle of the ReferenceFace, with no neighbors on any other ReferenceFace. This is the simplest case, since all neighbors are guaranteed to be easy to find.
- CornerFace : The SubdFace represents a face at the corner of the ReferenceFace.
- SideFace : The SubdFace represents a face along the side of the ReferenceFace, but it is not a CornerFace.
There are different classes to handle adjacency for each of these possibilities.
- int IndexFromVertex(SubdVertex v) : returns the index that vertex v has to get to this SubdFace. If f.IndexFromVertex(v) == i then v.Face(i) == f.
A SubdVertex object can be used to represent a vertex at any level of the surface. A SubdVertex is defined by the usual SubdFeature data. Some SubdVertex methods that require further explanation include:
- Vector3 EditVector() : returns a vector representing how much this vertex has been edited from the position it would have if it were merely the result of subdividing its coarser-level influence vertices.
- VertexClassification Classification() : returns the kind of vertex that this is. Possibilities include
- BaseLevelVertex : The SubdVertex represents a base vertex. In this special case, the ReferenceFace index really gives the index of the corresponding BaseVertex, and the other fields are ignored.
- InteriorVertex : The SubdVertex represents a vertex in the middle of the ReferenceFace, with no neighbors on any other ReferenceFace. This is the simplest case, since all neighbors are guaranteed to be easy to find.
- CornerVertex : The SubdVertex represents a face at the corner of the ReferenceFace.
- SideVertex : The SubdVertex represents a face along the side of the ReferenceFace, but it is not a CornerVertex.
There are different classes to handle adjacency for each of these possibilities.
- int CreaseEdgeCount() : returns the number of crease edges radiating from this vertex. An ordinary smooth vertex has 0 crease edges. If the vertex is in the middle of a normal crease edge, there are exactly 2 crease edges. If it is at the end of a dart, there is exactly 1. If there are 3 or greater crease edges, then the vertex is considered to be a sharp corner.
SDLib provides iterators for features in the SubdSurface. SubdFaceIterator, SubdEdgeIterator, and SubdVertexIterator are used to iterate over their respective features at a particular level of the surface. Each of these iterators is built from a SubdLevel object that specifies a subdivision surface and the level on that surface to iterate over. Examples of the iterators are given in the code base, such as in the SubdLimitVertexTessellator::Tessellate() method.
SDLib provides two kinds of tessellators to produce a connected polygonal mesh from the subdivision surface:
- SubdCVTessellator: This tessellates the subdivision surface into a polygonal mesh built from the control vertices at a particular level. This can be useful for simply examining the CVs. It is also a back-door way to simulate changes of topology at finer levels, since a finer-level mesh can be edited, and then reused as a base mesh for a new subdivision surface.
- SubdLimitVertexTessellator. This is useful for providing a good approximation of the limit surface. The vertices output here are taken from the limit surface itself, not just from the CVs. The level that is used as the tessellation parameter in the SubdLevel object does not change the positions of the vertices generated, only their density over the limit surface.
The TestSubdLib directory in the SDLib release has hundreds of unit tests for testing SDLib in Windows. It also contains many examples of code that sets up SDLib classes and calls methods in those classes. This provides examples of how much of the SDLib code can be used.
Please send suggestions and additions for improving this document to Michael Lounsbery at email@example.com .
Copyright © 1998-2010 Solid Modeling Solutions
All rights reserved.
Information in this document is subject to change without notice.