In an example code of the book "introduction to 3d game programming with directx 11"

Question

void GeometryGenerator::Subdivide(MeshData& meshData)
{
    // Save a copy of the input geometry.
    MeshData inputCopy = meshData;


    meshData.Vertices.resize(0);
    meshData.Indices.resize(0);

    //       v1
    //       *
    //      / \
    //     /   \
    //  m0*-----*m1
    //   / \   / \
    //  /   \ /   \
    // *-----*-----*
    // v0    m2     v2

    UINT numTris = inputCopy.Indices.size()/3;
    for(UINT i = 0; i < numTris; ++i)
    {
        Vertex v0 = inputCopy.Vertices[ inputCopy.Indices[i*3+0] ];
        Vertex v1 = inputCopy.Vertices[ inputCopy.Indices[i*3+1] ];
        Vertex v2 = inputCopy.Vertices[ inputCopy.Indices[i*3+2] ];

        //
        // Generate the midpoints.
        //

        Vertex m0, m1, m2;

        // For subdivision, we just care about the position component.  We 
        // derive the other
        // vertex components in CreateGeosphere.

        m0.Position = XMFLOAT3(
            0.5f*(v0.Position.x + v1.Position.x),
            0.5f*(v0.Position.y + v1.Position.y),
            0.5f*(v0.Position.z + v1.Position.z));

        m1.Position = XMFLOAT3(
            0.5f*(v1.Position.x + v2.Position.x),
            0.5f*(v1.Position.y + v2.Position.y),
            0.5f*(v1.Position.z + v2.Position.z));

        m2.Position = XMFLOAT3(
            0.5f*(v0.Position.x + v2.Position.x),
            0.5f*(v0.Position.y + v2.Position.y),
            0.5f*(v0.Position.z + v2.Position.z));

        //
        // Add new geometry.
        //

        meshData.Vertices.push_back(v0); // 0
        meshData.Vertices.push_back(v1); // 1
        meshData.Vertices.push_back(v2); // 2
        meshData.Vertices.push_back(m0); // 3
        meshData.Vertices.push_back(m1); // 4
        meshData.Vertices.push_back(m2); // 5

        meshData.Indices.push_back(i*6+0);
        meshData.Indices.push_back(i*6+3);
        meshData.Indices.push_back(i*6+5);

        meshData.Indices.push_back(i*6+3);
        meshData.Indices.push_back(i*6+4);
        meshData.Indices.push_back(i*6+5);

        meshData.Indices.push_back(i*6+5);
        meshData.Indices.push_back(i*6+4);
        meshData.Indices.push_back(i*6+2);

        meshData.Indices.push_back(i*6+3);
        meshData.Indices.push_back(i*6+1);
        meshData.Indices.push_back(i*6+4);
    }
}

---

This function is in 'GeometryGenerator.cpp' file and does subdivide a mesh. Before this fuction is called, a icosahedron is created and transmitted as the parameter meshData. The members of MeshData, Vertices and Indices, are vectors of STL.

In my opinion, after this function calls those series of functions, meshData.Vertices.push_back, in the next iteration of the loop some of vertices may be repeatedly stored.

Anyone could answer

• whether I am wrong,
• why the author make the codes like this,
• or whether there is more efficient way if my thought is right.

Thank you all who read my poor English.

Answer 1

whether I am wrong

I am pretty sure you are right, especially about the duplicated vertices!

why the author make the codes like this

No one can answer this except the author himself. I would guess that he/she simply oversaw the duplication problem...

or whether there is more efficient way if my thought is right.

I would not care for efficency as long as the algorithm is not correct!

First, we need to avoid vertex duplication. I simply would leave the existing vertices as are (thus only clear the indices) and append the new ones at the end. For this purpose, I would store the edges in a temporary std::map, mapping a pair of indices (the edge) to the newly created index (always smaller index first to avoid problems with (10,12) vs. (12,10), which identify the same edge...).

Then for v0, v1, v2, I'd use the indices, not the vertices themselves. m0, m1, m2 are looked up in the map first, if found, use, otherwise, create a new vertex, add it to the vertices vector and add an entry in our map.

UINT v0 = copiedIndices[i*3+0];
// ...

UINT m0;
auto key = std::make_pair(v0, v1); // TODO: order indices!!!
auto entry = myMap.find(key); 
if(entry != myMap.end())
{
    m0 = entry->second;
}
else
{
    meshData.Vertices.push_back(newVertex);
    m0 = meshData.Vertices.size() - 1;
    myMap.insert(key, m0);
}

Then you will add your new triangles, just take the indices as are:

meshdata.indices.pushback(v0); // one of the original indices
meshdata.indices.pushback(m0); // one of the new ones
meshdata.indices.pushback(m2);

// ...

Answer 2

• If there is another triangle adjacent to v1 - v2 side then v1, v2 and m1 will be added twice and so on.
• Who knows? Maybe there is an extra deduplication pass after this.
• It is possible to perform this on GPU using either geometry shader or straight tessellation. See this example.