Shadow Volumes and non-closed meshes

Today I implemented an algorithm that produces correct shadow volumes for non-closed meshes, aka meshes with open edges. I couldn't find it anywhere on the Internet so I decided to publish it here. It's from Game Programming Gems 4. The gist of the algorithm is to add inverted face normals and point edges with missing neighboring face to them. To use it, call generateOpenEdgeTriangles() after generateEdges().

#define NO_NEIGHBOR 65535


// Indices of two vertices that belong to the same triangle. Used to construct shadow volume sides.
struct TriangleEdge
{
    TriangleEdge() : v1(0), v2(0), f1(NO_NEIGHBOR), f2(NO_NEIGHBOR) {}
    TriangleEdge( unsigned short a_v1, unsigned short a_v2 ) : v1(a_v1), v2(a_v2) {}

    unsigned short v1;
    unsigned short v2;
    unsigned short f1;
    unsigned short f2;
};

bool ShadowVolume::doesEdgeBelongToFace( TriangleEdge& edge, int aFaceIndex ) const

{

    // A and B.

    if ((almostEquals( meshVertices[ meshFaces[ aFaceIndex ].x ], meshVertices[ edge.v1 ] ) &&

         almostEquals( meshVertices[ meshFaces[ aFaceIndex ].y ], meshVertices[ edge.v2 ] )) ||

        (almostEquals( meshVertices[ meshFaces[ aFaceIndex ].x ], meshVertices[ edge.v2 ] ) &&

         almostEquals( meshVertices[ meshFaces[ aFaceIndex ].y ], meshVertices[ edge.v1 ] )))

    {

        return true;

    }

    

    // B and C.

    if ((almostEquals( meshVertices[ meshFaces[ aFaceIndex ].y ], meshVertices[ edge.v1 ] ) &&

         almostEquals( meshVertices[ meshFaces[ aFaceIndex ].z ], meshVertices[ edge.v2 ] )) ||

        (almostEquals( meshVertices[ meshFaces[ aFaceIndex ].y ], meshVertices[ edge.v2 ] ) &&

         almostEquals( meshVertices[ meshFaces[ aFaceIndex ].z ], meshVertices[ edge.v1 ] )))

    {

        return true;

    }

    

    // C and A.

    if ((almostEquals( meshVertices[ meshFaces[ aFaceIndex ].z ], meshVertices[ edge.v1 ] ) &&

         almostEquals( meshVertices[ meshFaces[ aFaceIndex ].x ], meshVertices[ edge.v2 ] )) ||

        (almostEquals( meshVertices[ meshFaces[ aFaceIndex ].z ], meshVertices[ edge.v2 ] ) &&

         almostEquals( meshVertices[ meshFaces[ aFaceIndex ].x ], meshVertices[ edge.v1 ] )))

    {

        return true;

    }

    return false;

}



void ShadowVolume::generateEdges()
{
    TriangleEdge edge;
    
    for (unsigned int f = 0; f < meshFaces.getSize(); ++f)
    {        
        edge.v1 = meshFaces[ f ].x;
        edge.v2 = meshFaces[ f ].y;
        edge.f1 = f;
        edge.f2 = NO_NEIGHBOR;
        
        // Finds the other face that's touching vertices v1 and v2.
        for (unsigned int f2 = 0; f2 < meshFaces.getSize(); ++f2)
        {
            if (f2 == f)
            {
                continue;
            }
            if (doesEdgeBelongToFace( edge, f2 ))
            {
                edge.f2 = f2;
                break;
            }
        }
        edges[ f * 3 + 0 ] = edge;
        
        edge.v1 = meshFaces[ f ].y;
        edge.v2 = meshFaces[ f ].z;
        edge.f1 = f;
        edge.f2 = NO_NEIGHBOR;
        
        // Finds the other face that's touching vertices v1 and v2.
        for (unsigned int f2 = 0; f2 < meshFaces.getSize(); ++f2)
        {
            if (f2 == f)
            {
                continue;
            }
            if (doesEdgeBelongToFace( edge, f2 ))
            {
                edge.f2 = f2;
                break;
            }
        }
        edges[ f * 3 + 1 ] = edge;
        
        edge.v1 = meshFaces[ f ].z;
        edge.v2 = meshFaces[ f ].x;
        edge.f1 = f;
        edge.f2 = NO_NEIGHBOR;
        
        // Finds the other face that's touching vertices v1 and v2.
        for (unsigned int f2 = 0; f2 < meshFaces.getSize(); ++f2)
        {
            if (f2 == f)
            {
                continue;
            }
            if (doesEdgeBelongToFace( edge, f2 ))
            {
                edge.f2 = f2;
                break;
            }
        }
        edges[ f * 3 + 2 ] = edge;
    }
}

void ShadowVolume::generateOpenEdgeTriangles()
{
    int degenFacesSize = 0;


    // Finds out the # of open edges.
    for (unsigned int e = 0; e < edges.getSize(); ++e)
    {
        if (edges[ e ].f2 == NO_NEIGHBOR)
        {
            ++degenFacesSize;
        }
    }
    int offs = meshFaces.getSize();
    meshFaceNormals.resize( offs + degenFacesSize );
    backFaces.resize( offs + degenFacesSize );    


    for (unsigned int e = 0; e < edges.getSize(); ++e)
    {
        if (edges[ e ].f2 == NO_NEIGHBOR)
        {
            meshFaceNormals[ offs ] = -meshFaceNormals[ edges[e].f1 ];


            edges[ e ].f2 = offs;


            ++offs;
        }
    }
}