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.