Replacing edges with degenerate quads (for shadow volumes)

Member
Posts: 35
Joined: 2009.10
Post: #1
I intend to implement vertex shader driven shadow volumes, where in a model there are degenerate quads (or two triangles) between each triangle "edge" that can stretch when the back-facing triangles are transformed away from the light via the vertex shader. To that end, I've been working on an OBJ loader that can construct vertex, normal, and index arrays for a model that includes these edge quads. The problem is that trying to include the edge quads turns my model into a crumpled mess.

In my algorithm, for each face (I assume only triangles) I create three new vertices and three new vertex indices. Each vertex is assigned the triangle's normal. I assume a counter-clockwise winding. This data is put into arrays that can be moved to VBOs. That looks fine so far.

I get problems when I try to add the edge quads. When I see a new edge (represented by a pair of vertex indices) from the OBJ, I add it to an edge list along with their respective "real" vertex indices (since I'm duplicating vertices and vertex indices). If I encounter a pair of indices that represent an old edge, I get the original edge and use the information stored in it to construct the indices for two triangles that form the edge quad. Doing this, however, breaks my model.

My convenience class for keeping track of edges:
Code:
@interface ModelEdge : NSObject
{
    int start, end; // From OBJ file
    int realStart, realEnd; // Derived at runtime
}

@property (readonly) int start, end, realStart, realEnd;

+ (void)addEdgeToArray:(NSMutableArray *)array withStart:(int)start
   withEnd:(int)end withRealStart:(int)realStart
   withRealEnd:(int)realEnd;

+ (int)indexOfEdgeInArray:(NSArray *)array withStart:(int)start
   withEnd:(int)end;

- (id)initWithStart:(int)s withEnd:(int)e withRealStart:(int)rs
   withRealEnd:(int)re;

@end

@implementation ModelEdge

@synthesize start, end, realStart, realEnd;

+ (void)addEdgeToArray:(NSMutableArray *)array withStart:(int)start
   withEnd:(int)end withRealStart:(int)realStart
   withRealEnd:(int)realEnd
{
    ModelEdge *edge = [[ModelEdge alloc] initWithStart:start
      withEnd:end withRealStart:realStart withRealEnd:realEnd];
    [array addObject:edge];
    //[edge release];
}

+ (int)indexOfEdgeInArray:(NSArray *)array withStart:(int)start
   withEnd:(int)end
{
    int result = -1;

    int size = (int)[array count];
    ModelEdge *e;
    for (int i = 0; i < size; ++i)
    {
        e = [array objectAtIndex:i];
        if ((e.start == end) && (e.end == start))
        {
            result = i;
            break;
        }
    }

    return result;
}

- (id)initWithStart:(int)s withEnd:(int)e withRealStart:(int)rs
   withRealEnd:(int)re
{
    self = [super init];
    if (self)
    {
        start = s;
        end = e;
        realStart = rs;
        realEnd = re;
    }
    return self;
}

@end

Functions for dealing with OBJ files
Code:
void calculateTriangleNormal(NSArray *va, NSArray *vb, NSArray *vc,
  double *nx, double *ny, double *nz)
{
    double x1 = [[vb objectAtIndex:0] doubleValue]
    - [[va objectAtIndex:0] doubleValue];
    double y1 = [[vb objectAtIndex:1] doubleValue]
    - [[va objectAtIndex:1] doubleValue];
    double z1 = [[vb objectAtIndex:2] doubleValue]
    - [[va objectAtIndex:2] doubleValue];
    
    double x2 = [[vc objectAtIndex:0] doubleValue]
    - [[va objectAtIndex:0] doubleValue];
    double y2 = [[vc objectAtIndex:1] doubleValue]
    - [[va objectAtIndex:1] doubleValue];
    double z2 = [[vc objectAtIndex:2] doubleValue]
    - [[va objectAtIndex:2] doubleValue];
    
    *nx = (y1 * z2) - (z1 * y2);
    *ny = (z1 * x2) - (x1 * z2);
    *nz = (x1 * y2) - (y1 * x2);
    
    // Normalize normal
    
    double length = sqrt((*nx * *nx) + (*ny * *ny) + (*nz * *nz));
    *nx /= length;
    *ny /= length;
    *nz /= length;
}


BOOL obj_isNotComment(NSString *line)
{
    return ([line length] > 0) && ([line characterAtIndex:0] != '#');
}

BOOL obj_isVertex(NSString *line)
{
    NSRange substringLoc = [line rangeOfString:VERTEX];
    return substringLoc.location == 0;
}

void obj_loadVertices(NSString *line, NSMutableArray *destination)
{
    NSScanner *numberScanner = [NSScanner scannerWithString:line];

    double x, y, z;

    [numberScanner scanString:VERTEX intoString:NULL];
    [numberScanner scanDouble:&x];
    [numberScanner scanDouble:&y];
    [numberScanner scanDouble:&z];

    [destination addObject:[NSArray arrayWithObjects:
      [NSNumber numberWithDouble:x],
      [NSNumber numberWithDouble:y],
      [NSNumber numberWithDouble:z],
      nil]
    ];
}

BOOL obj_isFace(NSString *line)
{
    NSRange substringLoc = [line rangeOfString:FACE];
    return substringLoc.location == 0;
}

void obj_loadFaceIndices(NSString *line, int *a, int *b, int *c)
{
    NSScanner *numberScanner = [NSScanner scannerWithString:line];

    [numberScanner scanString:FACE intoString:NULL];

    // Assumes model is triangulated

    [numberScanner scanInt:a];
    [numberScanner scanString:@"//" intoString:NULL];
    --(*a);

    [numberScanner scanInt:b];
    [numberScanner scanString:@"//" intoString:NULL];
    --(*b);

    [numberScanner scanInt:c];
    [numberScanner scanString:@"//" intoString:NULL];
    --(*c);
}

void obj_findTriangleNormal(const NSArray *vertices,
  const int via, const int vib, const int vic,
  GLdouble *nx, GLdouble *ny, GLdouble *nz)
{
    NSArray *vertA = [vertices objectAtIndex:via];
    NSArray *vertB = [vertices objectAtIndex:vib];
    NSArray *vertC = [vertices objectAtIndex:vic];

    calculateTriangleNormal(vertA, vertB, vertC, nx, ny, nz);
}

The core OBJ loading code:
Code:
// Either keep track of a new edge or create a new edge quad
static void handleEdge(NSMutableArray *indices, NSMutableArray *edges,
  int indA, int indB, unsigned short realIA, unsigned short realIB)
{
    int edgeIndex = [ModelEdge indexOfEdgeInArray:edges withStart:indA
      withEnd:indB];

    if (edgeIndex < 0)
    {
        [ModelEdge addEdgeToArray:edges withStart:indA withEnd:indB
          withRealStart:realIA withRealEnd:realIB];
    }
    else
    {
        ModelEdge *e = [edges objectAtIndex:edgeIndex];
        [edges removeObjectAtIndex:edgeIndex];

        // Add two triangles to make a (degenerate)
        // quad

        [indices addObject:[NSNumber numberWithUnsignedShort:realIB]];
        [indices addObject:[NSNumber numberWithUnsignedShort:realIA]];
        [indices addObject:[NSNumber
          numberWithUnsignedShort:e.realStart]];

        [indices addObject:[NSNumber
          numberWithUnsignedShort:e.realEnd]];
        [indices addObject:[NSNumber
          numberWithUnsignedShort:e.realStart]];
        [indices addObject:[NSNumber numberWithUnsignedShort:realIA]];
    }
}

// Populate arrays with model data that can be transferred into VBOs
void getMeshData(NSString *objPath, NSMutableArray *vertices,
  NSMutableArray *normals, NSMutableArray *indices)
{
    NSMutableArray *baseVertices = [NSMutableArray array];
    NSMutableArray *edges = [NSMutableArray array];

    NSArray *fileLines = linesFromFile(objPath);

    NSString *currentColour = @"";

    for (NSString *line in fileLines)
    {
        if (obj_isNotComment(line))
        {
            if (obj_isVertex(line))
            {
                obj_loadVertices(line, baseVertices);
            }
            else if (obj_isFace(line))
            {
                int ia, ib, ic;
                obj_loadFaceIndices(line, &ia, &ib, &ic);

                // Indices

                unsigned short realIA = [indices count];
                unsigned short realIB = realIA + 1;
                unsigned short realIC = realIB + 1;

                [indices addObject:[NSNumber
                  numberWithUnsignedShort:realIA]];
                [indices addObject:[NSNumber
                  numberWithUnsignedShort:realIB]];
                [indices addObject:[NSNumber
                  numberWithUnsignedShort:realIC]];

                // Edges

                handleEdge(indices, edges, ia, ib, realIA,
                  realIB);
                handleEdge(indices, edges, ib, ic, realIB,
                  realIC);
                handleEdge(indices, edges, ic, ia, realIC,
                  realIA);

                // Vertices

                NSArray *va = [baseVertices objectAtIndex:ia];
                NSArray *vb = [baseVertices objectAtIndex:ib];
                NSArray *vc = [baseVertices objectAtIndex:ic];

                // Calculate face normal

                double nx, ny, nz;
                obj_findTriangleNormal(baseVertices, ia, ib, ic,
                  &nx, &ny, &nz);

                // Get final vertex data

                // Vertex A
                for (NSNumber *v in va)
                {
                    [vertices addObject:v];
                }

                // Vertex B
                for (NSNumber *v in vb)
                {
                    [vertices addObject:v];
                }

                // Vertex C
                for (NSNumber *v in vc)
                {
                    [vertices addObject:v];
                }

                // Normals
                for (int i = 0; i < 3; ++i)
                {
                    [normals addObject:
                     [NSNumber numberWithDouble:nx]];
                    [normals addObject:
                     [NSNumber numberWithDouble:ny]];
                    [normals addObject:
                     [NSNumber numberWithDouble:nz]];
                }
            }
        }
    }

    if ([edges count] > 0)
    {
        NSLog(@"Warning: Model '%@' has holes in it", objPath);
    }
}

Anyone notice any mistakes here? Huh
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #2
I'll be honest, that's a heap of code to look over. But that being said, I implemented GPU shadow volume extrusion a few years ago ( before I gave up on stencil shadows and went for shadow mapping, whole hog ).

In my approach, I left the geometry as loaded from disk ( or procedurally generated ) alone for general-purpose rendering. After all, degenerate quads are degenerate quads. Instead, I generated a separate vbo where each triangle edge was doubled into a quad. The vertex shader left the quads for caps degenerate, and extruded the degenerates to infinity for the silhouette. The performance was actually pretty decent. If you're interested, I should still have that code deep deep deep in my SVN history.

That being said, shadow maps are the way to go. I put it off until I had a GPU I could write GLSL for and I got over my fear of the maths. If I could figure it out (I was an art major...) then probably you can too.

EDIT: Originally I forgot how my volume extruder worked Rasp
Quote this message in a reply
Member
Posts: 35
Joined: 2009.10
Post: #3
TomorrowPlusX Wrote:I'll be honest, that's a heap of code to look over. But that being said, I implemented GPU shadow volume extrusion a few years ago ( before I gave up on stencil shadows and went for shadow mapping, whole hog ).
Yeah. Sorry about that, but I honestly didn't know where to cut it off. If I had shown code like something; somefunction(); something else; ..., someone is going to ask what somefunction() does.

Quote:In my approach, I left the geometry as loaded from disk ( or procedurally generated ) alone for general-purpose rendering. After all, degenerate quads are degenerate quads. Instead, I generated a separate vbo where each triangle edge was doubled into a quad. The vertex shader left the quads for caps degenerate, and extruded the degenerates to infinity for the silhouette. The performance was actually pretty decent. If you're interested, I should still have that code deep deep deep in my SVN history.
That's basically what I've been trying to do, except I was going to use one VBO for both rendering and shadows. Probably not something to do in general, but for various reasons I feel it would work for my project.

I figure, if I render the model using triangles, then to add the quad for each edge I'd add two triangles. And since I'm using an indexed triangle array all I'd have to do is create unique vertices for each face (which I'm doing) and add extra indices to represent the quad triangles. The VBO, with duplicated vertices and index array, renders perfectly when I don't add indices to represent the quad triangles, but becomes crumpled otherwise.

Quote:That being said, shadow maps are the way to go.
I've been ambivalent about this and wanted to know what made you switch to shadow mapping. It sounded easier to me at first but as I read about how the perspective and aliasing artifacts have to be compensated for it started to sound no easier than shadow volumes. Plus I have a requirement for very precise hard shadows, so shadow volume ended up sounding more appropriate anyway.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #4
Coyote Wrote:Yeah. Sorry about that, but I honestly didn't know where to cut it off. If I had shown code like something; somefunction(); something else; ..., someone is going to ask what somefunction() does.

Hey, better safe than sorry.


Quote:That's basically what I've been trying to do, except I was going to use one VBO for both rendering and shadows. Probably not something to do in general, but for various reasons I feel it would work for my project.

Personally, I don't think you should be submitting degenerate geometry in your normal draw calls. However, if your doubled indices are at the end of your storage ( say, valid mesh triangles at the front, doubled edges at the end ) then you could draw only the valid geometry for your normal rendering, and you could submit the whole shebang for shadows, and you only need one VBO.

BTW, which part of rendering is failing? Normal rendering? Or shadow volume rendering?

Quote:I figure, if I render the model using triangles, then to add the quad for each edge I'd add two triangles. And since I'm using an indexed triangle array all I'd have to do is create unique vertices for each face (which I'm doing) and add extra indices to represent the quad triangles. The VBO, with duplicated vertices and index array, renders perfectly when I don't add indices to represent the quad triangles, but becomes crumpled otherwise.

This sounds fine to me, honestly. I'll look over your code but I can't promise anything Sneaky


Quote:I've been ambivalent about this and wanted to know what made you switch to shadow mapping. It sounded easier to me at first but as I read about how the perspective and aliasing artifacts have to be compensated for it started to sound no easier than shadow volumes. Plus I have a requirement for very precise hard shadows, so shadow volume ended up sounding more appropriate anyway.

Honestly, once you get the maths figured out, it's easier. I've been able to drop so much code it's not funny. Performance went up, code size & complexity went down.

The factors that got me to switch were:

1) I couldn't render shadows into an FBO without a stencil attachment ( which may be available now, but wasn't a few years ago ).

2) I wanted dynamic shadows for my terrain, something which simply wasn't feasible with stencil owing to vertex throughput and the need for a "watertight" volume.

I've implemented 3 shadow mapping techniques, spot, directional and point ( I bit the bullet and got omnidirectional point shadows working just a few weeks ago ). Using "cascading shadow maps" for directional lighting produces fairly sharp shadows, but honestly, nothing beats stencil for hard shadows.

I did a demo a while back of CSM ( the only hard technique ). If you search this forum you should be able to find it ( and the code )
Quote this message in a reply
Member
Posts: 35
Joined: 2009.10
Post: #5
TomorrowPlusX Wrote:Personally, I don't think you should be submitting degenerate geometry in your normal draw calls. However, if your doubled indices are at the end of your storage ( say, valid mesh triangles at the front, doubled edges at the end ) then you could draw only the valid geometry for your normal rendering, and you could submit the whole shebang for shadows, and you only need one VBO.
Good point. I'll probably implement that afterwards if I ever get this bug fixed.

Quote:BTW, which part of rendering is failing? Normal rendering? Or shadow volume rendering?
The rendering part. I haven't done anything with the shadow volume part yet.

This is what my model looks like if I don't try adding the edge quad triangles:
[Image: shipw.png]
[Image: ship2.png]

And this is what happens when I try to add the edge quad triangles:
[Image: shipcrumpled.png]
[Image: shipcrumpled2.png]

Quote:I wanted dynamic shadows for my terrain, something which simply wasn't feasible with stencil owing to vertex throughput and the need for a "watertight" volume.
You mean terrain self-shadowing, right? Now, I was going to have terrain be a mesh generated by a heightmap. The terrain would be relatively low poly (I'm going for a retro look) so I wasn't terribly worried about vertex throughput. I also figured the mesh could be made watertight by capping the bottom.

Quote:I've implemented 3 shadow mapping techniques, spot, directional and point ( I bit the bullet and got omnidirectional point shadows working just a few weeks ago ). Using "cascading shadow maps" for directional lighting produces fairly sharp shadows, but honestly, nothing beats stencil for hard shadows.
I only need directional lighting. I'm curious about what you meant by "nothing beats stencil for hard shadows". Are you saying there's some kind of "stencil shadow mapping" technique, or were you talking about something else?
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #6
Stenciled shadows are done all in eye space so your shadows are pixel perfect (though aliased).

Shaddow mapping uses textures to buffer the depth of the light from the light's point of view and so you will always be able to see the resolution of the shadow map you are using unless it's ridiculously high.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Sage
Posts: 1,199
Joined: 2004.10
Post: #7
It looks to me like you're borking your core geometry when adding edge quads. There's really nothing "bad" about submitting degenerate geometry, other than that your vertex processing will be working overtime. Those edge quads shouldn't ruin your geometry, so, really you have a code bug here ( not a conceptual one ). This might come down to painful, classical printf debugging. Find out how adding edge quads modifies your triangles.


Coyote Wrote:You mean terrain self-shadowing, right? Now, I was going to have terrain be a mesh generated by a heightmap. The terrain would be relatively low poly (I'm going for a retro look) so I wasn't terribly worried about vertex throughput. I also figured the mesh could be made watertight by capping the bottom.

If you're going old-school, then capping your terrain and treating it as one big mesh should be fine. My terrains have ~500,000 triangles and I'll be going much higher, and accordingly they're partitioned and aren't watertight. With shadow maps they can cast shadows trivially, it's awesome.

Coyote Wrote:I only need directional lighting. I'm curious about what you meant by "nothing beats stencil for hard shadows". Are you saying there's some kind of "stencil shadow mapping" technique, or were you talking about something else?

Skorche said it better than me. But if I were doing a space combat game I'd go with stencil shadows. Anything else I'll stick with shadow maps.
Quote this message in a reply
Member
Posts: 35
Joined: 2009.10
Post: #8
Well, I fixed my bug. Now I add the edge triangle indices after I've added the indices for all the other triangles. Now I think I have some nice shadow volumes, though the depth testing seems to be messed up when I draw it graphically:

[Image: shadowvolume.png]

Also, if I make the camera follow the ship the volume gets clipped at certain angles.

Before clip:

[Image: beforeclip.png]

After clip:

[Image: afterclip.png]

I don't think it's my view frustum, since I tried zooming out but still got the clipping. This is my camera set-up code:
Code:
double radians = shipAngle * (3.14 / 180.0);
gluLookAt(shipX - (2.0 * sin(radians)), 1.0,
  shipZ - (2.0 * cos(radians)), shipX, 0.333, shipZ,
  0.0, 1.0, 0.0);

And this is the vertex shader that does the volume extrusion:
Code:
uniform vec3 lightDir; // Parallel light

void main()
{
    vec3 eyeNormal = normalize(gl_NormalMatrix * gl_Normal);
    vec3 realLightDir = normalize(lightDir);

    float dotprod = dot(eyeNormal, realLightDir);

    gl_Position = ftransform();

    if (dotprod <= 0.0)
    {
        gl_Position += vec4(-realLightDir, 0.0);
        gl_FrontColor = vec4(1.0, 0.0, 0.0, 1.0);
    }
    else
    {
        gl_FrontColor = gl_Color;
    }
}
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #9
M_PI ftw....
Quote this message in a reply
Member
Posts: 35
Joined: 2009.10
Post: #10
Not to mention that I'll need to implement an actual camera class eventually...Sneaky

Update: Also, I think I got my shadow volume extrusion shader working now:
Code:
uniform vec3 lightDir;

void main()
{
    vec3 eyeNormal = normalize(gl_NormalMatrix * gl_Normal);
    vec3 realLightDir = normalize(lightDir);

    float dotprod = dot(eyeNormal, realLightDir);

    vec4 finalTransform = ftransform();
    vec4 shadowTransform = gl_ProjectionMatrix * vec4(-realLightDir, 0.0);

    if (dotprod <= 0.0)
    {
        finalTransform = shadowTransform;
    }

    gl_Position = finalTransform;
}

Update 2: Actually, I'm wrong again. While the shadow volume extends roughly in the right direction, it shifts as I move the ship instead of staying fixed (remember I'm using a directional light source).
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Preventing texture from creating transparent gaps on edges ardowz 3 1,718 Jan 21, 2014 11:28 AM
Last Post: SethWillits
  Create Aquaria-like terrain- texturing edges AndyKorth 3 6,479 Jul 31, 2011 08:13 PM
Last Post: FlamingHairball
  2d shadow blending problems tesil 1 5,837 Mar 17, 2011 10:12 AM
Last Post: Skorche
  [SOLVED]OpenGL edges of textures mk12 2 4,542 Sep 2, 2010 08:07 PM
Last Post: mk12
  Shadow Mapping - Self-Shadowing Z-Fighting Artifacts Bachus 16 22,472 Feb 11, 2009 12:24 PM
Last Post: arekkusu