Stencil Shadow Volume winding determination

F

FoxMcCloud

Newcomer
I'm trying to implement stencil shadowing and I'm running into a problem with shadow volume generation - I get the edge list and determine the shadow edges correctly, at least according to my visualizations (highlighting shadow edges / drawing shadow volumes to color buffer), however I can't seem to get the winding order right, messing up front / back facing - here's what it looks like right now:

http://www.flickr.com/photos/59098813@N06/5628070669/lightbox/

Here's my edge generation / shadow edge detection code:

Code: 
struct edge
{
    unsigned int vertex_index[2];
    unsigned int triangle_index[2];
};

#pragma pack(push)
#pragma pack(1)
struct triangle
{
    ext::uint16 index[3];
};
#pragma pack(pop)


unsigned int BuildEdges(unsigned int VertexCount, unsigned int TriangleCount, const triangle* TriangleArray, edge* EdgeArray)
{
    assert(sizeof(triangle) == (sizeof(ext::uint16) * 3));
    long MaxEdgeCount = TriangleCount * 3;
    unsigned short* FirstEdge = new unsigned short[VertexCount + MaxEdgeCount];
    unsigned short* NextEdge = FirstEdge + VertexCount;
    
    for(unsigned int a = 0; a < VertexCount; a++)
    {
        FirstEdge[a] = 0xFFFF;
    }
    
    // First pass over all triangles. This finds all the edges satisfying the
    // condition that the first vertex index is less than the second vertex index
    // when the direction from the first vertex to the second vertex represents
    // a counterclockwise winding around the triangle to which the edge belongs.
    // For each edge found, the edge index is stored in a linked list of edges
    // belonging to the lower-numbered vertex index i. This allows us to quickly
    // find an edge in the second pass whose higher-numbered vertex index is i.
    
    unsigned int EdgeCount = 0;
    const triangle* Triangle = TriangleArray;
    for(unsigned int a = 0; a < TriangleCount; a++)
    {
        unsigned int i1 = Triangle->index[2];
        for(unsigned int b = 0; b < 3; b++)
        {
            unsigned int i2 = Triangle->index[b];
            if (i1 < i2)
            {
                edge* Edge = &EdgeArray[EdgeCount];
                
                Edge->vertex_index[0] = (ext::uint16) i1;
                Edge->vertex_index[1] = (ext::uint16) i2;
                Edge->triangle_index[0] = (ext::uint16) a;
                Edge->triangle_index[1] = (ext::uint16) a;
                
                unsigned int EdgeIndex = FirstEdge[i1];
                if (EdgeIndex == 0xFFFF)
                {
                    FirstEdge[i1] = EdgeCount;
                }
                else
                {
                    for (;;)
                    {
                        unsigned int Index = NextEdge[EdgeIndex];
                        if (Index == 0xFFFF)
                        {
                            NextEdge[EdgeIndex] = EdgeCount;
                            break;
                        }
                        
                        EdgeIndex = Index;
                    }
                }
                
                NextEdge[EdgeCount] = 0xFFFF;
                EdgeCount++;
            }
            
            i1 = i2;
        }
        
        Triangle++;
    }
    
    // Second pass over all triangles. This finds all the edges satisfying the
    // condition that the first vertex index is greater than the second vertex index
    // when the direction from the first vertex to the second vertex represents
    // a counterclockwise winding around the triangle to which the edge belongs.
    // For each of these edges, the same edge should have already been found in
    // the first pass for a different triangle. So we search the list of edges
    // for the higher-numbered vertex index for the matching edge and fill in the
    // second triangle index. The maximum number of comparisons in this search for
    // any vertex is the number of edges having that vertex as an endpoint.
    
    Triangle = TriangleArray;
    for(unsigned int a = 0; a < TriangleCount; a++)
    {
        unsigned int i1 = Triangle->index[2];
        for(unsigned int b = 0; b < 3; b++)
        {
            unsigned int i2 = Triangle->index[b];
            if(i1 > i2)
            {
                for(unsigned int EdgeIndex = FirstEdge[i2]; EdgeIndex != 0xFFFF; EdgeIndex = NextEdge[EdgeIndex])
                {
                    edge* Edge = &EdgeArray[EdgeIndex];
                    if ((Edge->vertex_index[1] == i1) && (Edge->triangle_index[0] == Edge->triangle_index[1]))
                    {
                        Edge->triangle_index[1] = (unsigned short) a;
                        break;
                    }
                }
            }
            i1 = i2;
        }
        
        Triangle++;
    }
    
    delete[] FirstEdge;
    return EdgeCount;
}

vector<bool> CalculateShadowEdges(const float3 LightPosition, const vector<float3>& Vertices, const std::vector<float3>& Normals, unsigned int TriangleCount, const triangle* Triangles, vector<edge>& Edges)
{
    vector<bool> Result;
    Result.resize(Edges.size(), false);
    vector<float3> TriCenters(TriangleCount);
    vector<float3> TriNormals(TriangleCount);
    vector<float3> LightVectors(TriangleCount);
    for(unsigned int i = 0; i < TriangleCount; ++i)
    {
        float3 A = Vertices[Triangles[i].index[0]];
        float3 B = Vertices[Triangles[i].index[1]];
        float3 C = Vertices[Triangles[i].index[2]];
        float3 Center = (A + B + C) * (1.0/3.0);
        TriCenters[i] = Center;
        float3 NormalA = Normals[Triangles[i].index[0]];
        float3 NormalB = Normals[Triangles[i].index[1]];
        float3 NormalC = Normals[Triangles[i].index[2]];
        float3 Normal = normalize(NormalA + NormalB + NormalC);
        TriNormals[i] = Normal;
        float3 LightVector = Center - LightPosition;
        LightVectors[i] = normalize(LightVector);
    }
    for(unsigned int i = 0; i < Edges.size(); ++i)
    {
        float CosA = dot(TriNormals[Edges[i].triangle_index[0]], LightVectors[Edges[i].triangle_index[0]]);
        float CosB = dot(TriNormals[Edges[i].triangle_index[1]], LightVectors[Edges[i].triangle_index[1]]);
        if(((CosA > 0) && (CosB < 0)) || ((CosA < 0) && (CosB > 0)))
        {
            Result[i] = true;
        }
    }
    return Result;
}

And here's my shadow volume rendering code:
Code: 
void mesh::DrawStencilVolumes(const float3 LightPosition)
{
    vector<edge> Edges(Indices.size());
    unsigned int EdgeCount = BuildEdges(Vertices.size(), Indices.size() / 3, (const triangle*)&Indices[0], &Edges[0]);
    Edges.resize(EdgeCount);
    //Triangles is just a different view of Indices.
    const triangle* Triangles = (const triangle*)&Indices[0];
    //ShadowEdges[i] is true if Edges[i] is a shadow edge
    vector<bool> ShadowEdges = CalculateShadowEdges(LightPosition, Vertices, Normals, Indices.size() / 3, (const triangle*)&Indices[0], Edges);
    //
    unsigned int TriangleCount = Indices.size() / 3;
    vector<float3> TriCenters(TriangleCount);
    vector<float3> TriNormals(TriangleCount);
    //Vector from the light to TriCenters[i]
    vector<float3> LightVectors(TriangleCount);
    for(unsigned int i = 0; i < TriangleCount; ++i)
    {
        float3 A = Vertices[Triangles[i].index[0]];
        float3 B = Vertices[Triangles[i].index[1]];
        float3 C = Vertices[Triangles[i].index[2]];
        float3 Center = (A + B + C) * (1.0/3.0);
        TriCenters[i] = Center;
        float3 NormalA = Normals[Triangles[i].index[0]];
        float3 NormalB = Normals[Triangles[i].index[1]];
        float3 NormalC = Normals[Triangles[i].index[2]];
        float3 Normal = normalize(NormalA + NormalB + NormalC);
        TriNormals[i] = Normal;
        float3 LightVector = Center - LightPosition;
        LightVectors[i] = normalize(LightVector);
    }
    //
    using namespace application;
    using namespace programs;
    cgGLBindProgram(SimpleVertexProgram);
    cgGLBindProgram(StencilShadowVolumesDebugFragmentProgram);
    float Color[] = { 1, 0, 1, 1 };
    cgSetParameter4fv(cgGetNamedParameter(SimpleFragmentProgram, "Color"), Color);
    update_matrices();
    glPointSize(4.0);
    glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
    glDisable(GL_CULL_FACE);
    glBegin(GL_QUADS);
    for(unsigned int i = 0; i < Edges.size(); ++i)
    {
        if(ShadowEdges[i])
        {
            unsigned int FirstVertexIndex = Edges[i].vertex_index[0];
            unsigned int SecondVertexIndex = Edges[i].vertex_index[1];
            float3 StartPoint = Vertices[Edges[i].vertex_index[0]];
            float3 EndPoint = Vertices[Edges[i].vertex_index[1]];
            triangle FirstTriangle = Triangles[Edges[i].triangle_index[0]];
            triangle SecondTriangle = Triangles[Edges[i].triangle_index[1]];
            float3 FirstNormal = TriNormals[Edges[i].triangle_index[0]];
            float3 SecondNormal = TriNormals[Edges[i].triangle_index[1]];
            float3 FirstLightVector = LightVectors[Edges[i].triangle_index[0]];
            float3 SecondLightVector = LightVectors[Edges[i].triangle_index[1]];
            unsigned int FirstIndex = Edges[i].vertex_index[0];
            unsigned int SecondIndex = Edges[i].vertex_index[1];
            //Begin experimental block
            //This block tests to see if the second triangle comes before the first
            //(based on winding order) and if so swaps the edge points.
            bool Swap = false;
            for(unsigned int i = 0; i < 3; ++i)
            {
                if(FirstTriangle.index[i] == FirstIndex)
                {
                    if(FirstTriangle.index[(i+1)%3] == SecondIndex)
                    {
                        Swap = true;
                    }
                }
            }
            //
            if(Swap)
            {
                swap(StartPoint, EndPoint);
            }
            //End experimental block
            float CosA = dot(FirstNormal, FirstLightVector);
            float CosB = dot(SecondNormal, SecondLightVector);
            //If the first triangle faces towards the light and the second away from the light
            //Then swap the start / end points to swap winding for the extruded polygon.
            if(((CosA > 0) && (CosB < 0)))
            {
                swap(StartPoint, EndPoint);
            }
            //This is a fudge factor, extrusion should be to infinity.
            const float Scale = 1000.0f;
            float3 StartExtruded = StartPoint + (normalize(StartPoint - LightPosition) * Scale);
            float3 EndExtruded = EndPoint + (normalize(EndPoint - LightPosition) * Scale);
            const float W = 1.0f;
            glVertexAttrib4f(0, StartPoint.x, StartPoint.y, StartPoint.z, 1);
            glVertexAttrib4f(0, EndPoint.x, EndPoint.y, EndPoint.z, 1);
            glVertexAttrib4f(0, EndExtruded.x, EndExtruded.y, EndExtruded.z, W);
            glVertexAttrib4f(0, StartExtruded.x, StartExtruded.y, StartExtruded.z, W);
        }
    }
    glEnd();
    ///
    glDisable(GL_CULL_FACE);
}

Any idea where I'm going wrong? I'm basing my work on this: http://www.gamasutra.com/view/feature/2942/the_mechanics_of_robust_stencil_.php?print=1 . Any help would be appreciated.
 
It's been years since I did work with shadow volumes and I could easily be mistaken (as I didn't spend too long looking at the code), but it appears you are using the stored vertex normals to determine front/back facing WRT the light. AFAICS you can't do that - you need a normal that is genuinely perpendicular for the entire triangle. Either precompute and store it (somewhere) or generate it on the fly from your vertex positions (i.e. the cross product of two edges).

Actually, since you then want to dot it with the light direction, perhaps you can combine the normal calc with the dot product (i.e. a vector triple product). That might be cheaper. <shrug>
 
Thanks. Just tried that, it resulted in a minor improvement, but the scene still looks the way it did, for the most part. How do you determine winding for front / back facing?
 
Alright, I'm almost certain the problem is in this part:

Code: 
glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
    glDisable(GL_CULL_FACE);
    glBegin(GL_QUADS);
    //Loop over all edges
    for(unsigned int i = 0; i < Edges.size(); ++i)
    {
        //if Edge i is a shadow edge
        if(ShadowEdges[i])
        {
            unsigned int FirstVertexIndex = Edges[i].vertex_index[0];
            unsigned int SecondVertexIndex = Edges[i].vertex_index[1];
            float3 StartPoint = Vertices[Edges[i].vertex_index[0]];
            float3 EndPoint = Vertices[Edges[i].vertex_index[1]];
            triangle FirstTriangle = Triangles[Edges[i].triangle_index[0]];
            triangle SecondTriangle = Triangles[Edges[i].triangle_index[1]];
            float3 FirstNormal = TriNormals[Edges[i].triangle_index[0]];
            float3 SecondNormal = TriNormals[Edges[i].triangle_index[1]];
            float3 FirstLightVector = LightVectors[Edges[i].triangle_index[0]];
            float3 SecondLightVector = LightVectors[Edges[i].triangle_index[1]];
            unsigned int FirstIndex = Edges[i].vertex_index[0];
            unsigned int SecondIndex = Edges[i].vertex_index[1];
            //Begin experimental block
            //This block tests to see if the second triangle comes before the first
            //(based on winding order) and if so swaps the edge points.
            bool Swap = false;
            bool FirstIsFirst = false;
            for(unsigned int i = 0; i < 3; ++i)
            {
                if(FirstTriangle.index[i] == FirstIndex)
                {
                    if(FirstTriangle.index[(i+1)%3] == SecondIndex)
                    {
                        Swap = true;
                        FirstIsFirst = true;
                    }
                }
            }
            //If the second triangle comes first, swap normal / light vector
            if(!FirstIsFirst)
            {
                swap(FirstNormal, SecondNormal);
                swap(FirstLightVector, SecondLightVector);
            }
            //End experimental block
            float CosA = dot(FirstNormal, FirstLightVector);
            float CosB = dot(SecondNormal, SecondLightVector);
            //If the first triangle faces towards the light and the second away from the light
            //Then swap the start / end points to swap winding for the extruded polygon.
            if(((CosA > 0) && (CosB < 0)))
            {
                swap(StartPoint, EndPoint);
            }
            //This is a fudge factor, extrusion should be to infinity.
            const float Scale = 1000.0f;
            float3 StartExtruded = StartPoint + (normalize(StartPoint - LightPosition) * Scale);
            float3 EndExtruded = EndPoint + (normalize(EndPoint - LightPosition) * Scale);
            const float W = 1.0f;
            glVertexAttrib4f(0, StartPoint.x, StartPoint.y, StartPoint.z, 1);
            glVertexAttrib4f(0, EndPoint.x, EndPoint.y, EndPoint.z, 1);
            glVertexAttrib4f(0, EndExtruded.x, EndExtruded.y, EndExtruded.z, W);
            glVertexAttrib4f(0, StartExtruded.x, StartExtruded.y, StartExtruded.z, W);
        }
    }
    glEnd();

Now what's wrong with my First / Second triangle determination and winding determination? It looks proper to me, but obviously it's not, so I could use another pair of eyes. Any ideas?
 
FoxMcCloud said:
Thanks. Just tried that, it resulted in a minor improvement, but the scene still looks the way it did, for the most part. How do you determine winding for front / back facing?
Click to expand...
One would hope that your model data is already consistent in that all "front facing" triangles are, say, "clockwise". You then should get a sensible result when you compute the front/back relationship relative to the light direction.

If it turns out that your model is not consistent (but that would seem unlikely as you'd probably get holes appearing in it assuming culling is enabled in the normal render) then you either have to fix it, or adapt your algorithm so that it casts shadows from both front and back triangles (though that is somewhat inefficient).

I'll try to look at your code if I get a chance later today but I'm a bit busy ATM.
 
Ok nevermind, I misread the first part.
Can you explain what you're trying to do with the testing of triangle index order? I'm a bit puzzled by that one.
 
The index value of a vertex should be regarded as arbitrary - only the XYZ positions of the vertices matter and that is what you should use to compute the winding order relative to the lights.
 
What Simon said - the only thing that matters is the facing "order" of the two triangle normals (which is the second swap you're already doing).

Get rid of the index-based swap, and from what I can tell, things should work (I didn't see any other visible issue in the code).
 
Alright, I removed the swaps except for the dot-product based one, and it's still messed up.

Pretty much, I want to *understand* the logic, not just patch my code, so here's my question:

given a vertex list V[] (x, y, z), A triangle list T[] (each triangle is 3 indices w/ front facing CCW), and a shadow edge E which consists of 2 edge indices (FirstIndex, SecondIndex), 2 triangles (FirstTriangle, SecondTriangle), and a light position L in world space: How do I determine the extrusion order for the stencil shadow quad: is it { V[FirstIndex], V[SecondIndex], extrude(V[SecondIndex]), extrude(V[FirstIndex]) } or {V[SecondIndex, V[FirstIndex], extrude(V[FirstIndex]), extrude(V[SecondIndex]) } ? How do I select between those two?
 
With your framework, you'll have to examine the triangle indices.

First figure out which triangle faces the light:
Code: 
i = FirstTriangle; 
if (dot(cross(V[T[3*i+2]]-V[T[3*i+1]], V[T[3*i+0]]-V[T[3*i+1]]), L-V[T[3*i+1]]) < 0) i = SecondTriangle;

If the pair (FirstIndex, SecondIndex) matches (T[3*i+0], T[3*i+1]) or (T[3*i+1], T[3*i+2]) or (T[3*i+2], T[3*i+0]), then the quad should be ordered {V[SecondIndex, V[FirstIndex], extrude(V[FirstIndex]), extrude(V[SecondIndex]) }. If it matches (1,0), (2,1), or (0,2) then the quad should be the other way.

The cleaner way to avoid this is to have a boolean corresponding to each element of T[] (or a list of indices), and i'th flag to true if the triangle is facing the light and the edge from V[T] to V[T[j]] (where j = i + (i%3==2) ? -2 : 1) is a shadow edge. Then the quad will always be {V[T[j]], V[T], extrude(V[T]), extrude(V[T[j]])}. There's no need to work with a separate edge list, as your triangle list is an edge list, and it also contains the winding information.

I'd suggest a simpler algorithm, though: Insert points and triangles when finding silhouette edges, and flag points to be extruded instead of edges. This takes care of caps, also. I'm assuming you don't want to rewrite what you have, though, so it's a moot point.
 
Last edited by a moderator:
I did that and it doesn't seem to be working. Here's my code in case that helps - I don't think I made a mistake but a second pair of eyes won't hurt:

Code: 
glBegin(GL_QUADS);
    for(unsigned int i = 0; i < Edges.size(); ++i)
    {
        if(ShadowEdges[i])
        {
            unsigned int FirstVertexIndex = Edges[i].vertex_index[0];
            unsigned int SecondVertexIndex = Edges[i].vertex_index[1];
            float3 StartPoint = Vertices[Edges[i].vertex_index[0]];
            float3 EndPoint = Vertices[Edges[i].vertex_index[1]];
            triangle FirstTriangle = Triangles[Edges[i].triangle_index[0]];
            triangle SecondTriangle = Triangles[Edges[i].triangle_index[1]];
            float3 FirstNormal = TriNormals[Edges[i].triangle_index[0]];
            float3 SecondNormal = TriNormals[Edges[i].triangle_index[1]];
            float3 FirstLightVector = LightVectors[Edges[i].triangle_index[0]];
            float3 SecondLightVector = LightVectors[Edges[i].triangle_index[1]];
            unsigned int FirstIndex = Edges[i].vertex_index[0];
            unsigned int SecondIndex = Edges[i].vertex_index[1];
            //Begin experimental block
            //This block tests to see if the second triangle comes before the first
            //(based on winding order) and if so swaps the edge points.
            bool Swap = false;
            bool FirstIsFirst = false;
            for(unsigned int i = 0; i < 3; ++i)
            {
                if(FirstTriangle.index[i] == FirstIndex)
                {
                    if(FirstTriangle.index[(i+1)%3] == SecondIndex)
                    {
                        Swap = true;
                        FirstIsFirst = true;
                    }
                }
            }
            //
            if(Swap)
            {
                swap(StartPoint, EndPoint);
            }
            //This is a fudge factor, extrusion should be to infinity.
            const float Scale = 1000.0f;
            float3 StartExtruded = StartPoint + (normalize(StartPoint - LightPosition) * Scale);
            float3 EndExtruded = EndPoint + (normalize(EndPoint - LightPosition) * Scale);
            const float W = 1.0f;
            glVertexAttrib4f(0, StartPoint.x, StartPoint.y, StartPoint.z, 1);
            glVertexAttrib4f(0, EndPoint.x, EndPoint.y, EndPoint.z, 1);
            glVertexAttrib4f(0, EndExtruded.x, EndExtruded.y, EndExtruded.z, W);
            glVertexAttrib4f(0, StartExtruded.x, StartExtruded.y, StartExtruded.z, W);
        }
    }
    glEnd();
 
You cannot use vertex indices* to identify front/back facing - you have use the XYZ positions of the vertices.

*Consider what happens if you had a model with a single triangle.
 
Simon F said:
You cannot use vertex indices* to identify front/back facing - you have use the XYZ positions of the vertices.

*Consider what happens if you had a model with a single triangle.
Click to expand...

Could you elaborate? I don't think I completely understand what you're trying to say.
 
FoxMcCloud said:
Could you elaborate? I don't think I completely understand what you're trying to say.
Click to expand...

I could be wrong but I think I can come up with a simple example.

Supposed that you use clockwise for "front facing." So you have a triangle:

<0, 0, 0>-<0, 1, 0>-<1, 0, 0>

Now if you turn this triangle 180 degrees along the Y axis, it becomes "back facing":

<0, 0, 0>-<0, 1, 0>-<-1, 0, 0>

because the vertices are now counter-clockwise. However, the vertex indices are completely the same. So you can't tell whether a triangle is front facing or back facing only from vertex indices.
 
FoxMcCloud said:
What am I trying to determine facing with respect to? The light or the viewer?
Click to expand...
Whatever you want. You cannot use the indices as they cannot contain enough information. You must either dynamically compute the orientation of the triangle with respect to the light direction using the positions of the 3 vertices or precompute the triangle's normal (and not use the averaged vertex normals) and use that for orientation calculations.
 
I already do that - I use the triangle's planar normal to determine facing towards the light, and it seems to be working correctly when I visualize shadow edges. I don't see how this could solve the problem of determining the winding order however - I know the edge (a, b) is a shadow edge, but winding its extruded quad properly is my problem.
 
FoxMcCloud said:
I did that and it doesn't seem to be working. Here's my code in case that helps - I don't think I made a mistake but a second pair of eyes won't hurt:
Click to expand...
I don't see where you're determining which of the two triangles is facing the light, i.e. determining i in my post (sorry, I should have used a different letter, as it's not the same i as in your code).

Before "//Begin experimental block", insert the following code:
Code: 
triangle LitTriangle = (dot(FirstLightVector, FirstNormal) > 0) ? FirstTriangle : SecondTriangle;
You may have to reverse the inequality depending on how you calculated your light vectors. Then, in your if blocks below, replace FirstTriangle with LitTriangle.
 
You must log in or register to reply here.

Similar threads

S
Modern textureless deferred rendering techniques
2
Replies
27
Views
62K
upnorthsox
U
N
ID Tech 4 Coding puzzle
Replies
6
Views
4K
nbohr1more
N
W
Problems with Deferred Shading
Replies
9
Views
8K
IronNick
I
M
Tangent space – bump mapping HELP!
Replies
8
Views
3K
Mr.Pink
M
M
Vertex Buffer Object - usage HELP!
Replies
4
Views
5K
Mr.Pink
M
Back
Top