Application: SubDiv
The SubDiv application implements the modified butterfly subdivision
scheme we just discussed. It loads an .o3d file and displays it interactively,
giving the users the option of subdividing the model whenever they wish.
Chapter 8: Advanced 3D Techniques n 387
Figure 8.30:
A subdivided
octagon model
Figure 8.31: The SubDiv sample
The model data is represented with an adjacency graph. Each triangle
structure holds pointers to the three vertices it is composed of. Each vertex
structure has STL vectors that contain pointers to edge structures (one
edge for each vertex it’s connected to) and triangle structures. The lists are
unsorted (which requires linear searching; fixing this to order the edges in
clockwise winding order, for example, is left as an exercise for the reader).
The following code gives the header definitions (and many of the func-
tions) for the vertex, edge, and triangle structures. These classes are all
defined inside the subdivision surface class (cSubDivSurf).
/**
* Subdivision Surface vertex
*/
struct sVert
{
/**
* These two arrays describe the adjacency information
* for a vertex. Each vertex knows who all of its neighboring
* edges and triangles are. An important note is that these
* lists aren't sorted. We need to search through the list
* when we need to get a specific adjacent triangle.
* This is, of course, inefficient. Consider sorted insertion
* an exercise to the reader.
*/
std::vector< sTriangle* > m_triList;
std::vector< sEdge* > m_edgeList;
/**
* position/normal information for the vertex
*/
388 n Chapter 8: Advanced 3D Techniques
Figure 8.32: The SubDiv sample after division
cGraphicsLayer::cDefaultVertex m_vert;
/**
* Each vertex knows its position in the array it lies in.
* This helps when we're constructing the arrays of subdivided data.
*/
int m_index;
void AddEdge( sEdge *pEdge )
{
assert( 0 == std::count(
m_edgeList.begin(),
m_edgeList.end(),
pEdge ) );
m_edgeList.push_back( pEdge );
}
void AddTri( sTriangle *pTri )
{
assert( 0 == std::count(
m_triList.begin(),
m_triList.end(),
pTri ) );
m_triList.push_back( pTri );
}
/**
* Valence == How many other vertices are connected to this one
* which said another way is how many edges the vert has.
*/
int Valence()
{
return m_edgeList.size();
}
sVert() :
m_triList( 0 ),
m_edgeList( 0 )
{
}
/**
* Given a vertex that we know we are attached to, this function
* searches the list of adjacent edges looking for the one that
* contains the input vertex. Asserts if there is no edge for
* that vertex.
*/
sEdge *GetEdge( sVert *pOther )
{
for( int i=0; i<m_edgeList.size(); i++ )
{
if( m_edgeList[i]->Contains( pOther ) )
return m_edgeList[i];
}
assert(false); // didn't have it!
Chapter 8: Advanced 3D Techniques n 389
return NULL;
}
};
/**
* Edge structure that connects two vertices in a SubSurf
*/
struct sEdge
{
sVert *m_v[2];
/**
* When we perform the subdivision calculations on all the edges
* the result is held in this newVLoc structure. Never has any
* connectivity information, just location and color.
*/
sVert m_newVLoc;
/**
* true == one of the edges' vertices is the input vertex
*/
bool Contains( sVert *pVert )
{
return (m_v[0] == pVert) || m_v[1] == pVert;
}
/**
* retval = the other vertex than the input one
*/
sVert *Other( sVert *pVert )
{
return (m_v[0] == pVert) ? m_v[1] : m_v[0];
}
void Init( sVert *v0, sVert *v1 )
{
m_v[0] = v0;
m_v[1] = v1;
/**
* Note that the edge notifies both of its vertices that it's
* connected to them.
*/
m_v[0]->AddEdge( this );
m_v[1]->AddEdge( this );
}
/**
* This function takes into consideration the two triangles that
* share this edge. It returns the third vertex of the first
* triangle it finds that is not equal to 'notThisOne'. So if we
* want one, notThisOne is passed as NULL. If we want the other
* one, we pass the result of the first execution.
*/
sVert *GetOtherVert( sVert *v0, sVert *v1, sVert *notThisOne )
{
390 n Chapter 8: Advanced 3D Techniques
sTriangle *pTri;
for( int i=0; i<v0->m_triList.size(); i++ )
{
pTri = v0->m_triList[i];
if( pTri->Contains( v0 ) && pTri->Contains( v1 ) )
{
if( pTri->Other( v0, v1 ) != notThisOne )
return pTri->Other( v0, v1 );
}
}
// when we support boundary edges, we shouldn't assert
assert(false);
return NULL;
}
/**
* Calculate the K-Vertex location of 'prim' vertex. For triangles
* of valence !=6
*/
point3 CalcKVert( int prim, int sec );
/**
* Calculate the location of the subdivided point using the
* butterfly method.
* for edges with both vertices of valence == 6
*/
point3 CalcButterfly();
};
/**
* Subdivision surface triangle
*/
struct sTriangle
{
/**
* The three vertices of this triangle
*/
sVert *m_v[3];
point3 m_normal;
void Init( sVert *v0, sVert *v1, sVert *v2 )
{
m_v[0] = v0;
m_v[1] = v1;
m_v[2] = v2;
/**
* Note that the triangle notifies all 3 of its vertices
* that it's connected to them.
*/
m_v[0]->AddTri( this );
m_v[1]->AddTri( this );
m_v[2]->AddTri( this );
}
/**
* true == the triangle contains the input vertex
Chapter 8: Advanced 3D Techniques n 391

Get Advanced 3D Game Programming with DirectX 10.0 now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.