## GPU shadow volume extrusion with GLSL

Sage
Posts: 1,199
Joined: 2004.10
Post: #1
This is branch from an earlier thread which I started, and then derailed http://idevgames.com/forum/showthread.php?t=13373

So, I'm about to transition from CPU to GPU shadow volume extrusion. This being said, I understand the CPU approach ( I wrote it! ) but being a novice shader programmer, I hope people can help me a little with the math, since shaders live in a slightly different space.

First, I believe I understand the principle for GPU shadow volume extrusion. I have three VBOs -- one for the triangle geometry which makes up the light facing caps and the extruded caps. One for per-vertex normals so I know I'm getting the triangle's normal for each vertex ( I know this means vertex duplication ). And finally, one VBO which contains doubled-up edges as quads for silhouette extrusion. My understanding is that I can use the same shader for silhouette extrusion as for volume caps.

Now, in my CPU implementation the approach I take is this:

1) I use the inverse of the modelview matrix for the model to transform the light position to the untransformed space of the model.

2) I do the extrusion to infinity more or less like so ( leaving out silhouette math. Also, the code below is for positional light, not directional )
Code:
```vec4 p = points[...]; pInfinity = vec4( p.x * lightPosition.w - lightPosition.x,                           p.y * lightPosition.w - lightPosition.y,                           p.z * lightPosition.w - lightPosition.z,                           0.0f );```

3) When I render the volume, leaving out the stencil code, I just multmatrix the model's transformation matrix and display the vertex arrays I calculated in step 2.

So, here's what I'm wondering with regards to doing this on the GPU.

1) When rendering the volume, I assume I'll multmatrix by the model's transformation before rendering the volume. In my GLSL code I can get the vertex relative light direction via something like:

Code:
```vec4 ecPos = gl_ModelViewMatrix * gl_Vertex; vec3 localLightDirection = normalize( gl_LightSource[0].position.xyz - ecPos.xyz );```

This is what I do for lighting, and it seems relevant. Further, after testing for facing light, can this ( inverted ) be used for my extrusion direction?

2) To project to infinity... well, I'm just guessing here, but can similar math as used above work? Can I just do something like:
Code:
```if ( dot( gl_Normal, localLightDirection ) < 0 ) {     vec3 dir( -localLightDirection );     vec3 pos = ftransform();     gl_Position = vec4( pos.x * gl_LightSource[0].position.w - localLightDirection.x,                                   pos.y * gl_LightSource[0].position.w - localLightDirection.y,                                   pos.z * gl_LightSource[0].position.w - localLightDirection.z,                                   0.0 ); // zero for infinity } else {     // leave it alone     gl_Position = ftransform(); }```

I'm just guessing, and I hope somebody can help. akb825... paging akb825
Moderator
Posts: 1,140
Joined: 2005.07
Post: #2
It looks like it will work, but I think you're thinking a bit too much about the extrusion direction. What I did was transform the normal as you normally would, then do the dot product with the light as you did. If it's negative, I would extrude not the point, but the transformation matrix itself. In this case, I took took the light direction scaled by my extrusion amount, and subtracted the modelview[0].w, modelview[1].w, and modelview[2].w by the extrusion amount's x, y, and z respectively. I then transformed the position as I normally would. This way I get around the orientation by feeding the transformation directly into the matrix.
Moderator
Posts: 1,140
Joined: 2005.07
Post: #3
I know that you've decided to stick with stencil shadows for now, but I've just came across a new shadow mapping method: trapezoidal shadow mapping. It seems to take only a little more work to calculate the matrix for the light, and a shader to correctly offset the depth values, (a good approximation can be done solely with vertex shaders) while it gives probably the best shadow quality presently available on current graphics cards. You should take a look at it, since I'm sure you'll eventually go to shadow maps. http://www.comp.nus.edu.sg/~tants/tsm/TSM_recipe.html
Sage
Posts: 1,199
Joined: 2004.10
Post: #4
That's really quite interesting. The whole reason I've avoided shadow maps is due to the trickery required to get decent precision. That being said, while I will read the article a few times and try to understand, I fear the math's over my head.

So, anyway, I've got GPU extrusion sort of working for directional and positional light sources. Or, to clarify:

Point projection based on facedness seems to work. The points go to infinity just like they do for my CPU based version ( using a debug rendering routine that draws the volume ).

On the other hand, I seem to have winding problems.

But I think I can tackle it. When I've got it all working, I'll post source in case anybody wants to see how to do it.
Moderator
Posts: 1,140
Joined: 2005.07
Post: #5
I'll attempt to get the trapezoidal implementation working and post some sample code if I do get it right.

When I made my shadow meshes, I had some winding problems when I tried to correct them, but I found out that if I simply go in the direction the indices take me, the problem never surfaces.
Sage
Posts: 1,199
Joined: 2004.10
Post: #6
Actually, it wasn't a winding issue at all -- I was passing the wrong normal array when rendering the edge quads. Whoops.

That being said, my extrusion shaders work ( both directional and positional ) -- YAY! Sort of. I'm getting weird rendering side effects. I'm working on it now, but I'm likely to post a plea for help with screenshots and example code soon...
Sage
Posts: 1,199
Joined: 2004.10
Post: #7
Well, I've got GPU shadows working, and they look great! The screenshots below are of a scene with 3 lights, 1 directional, two positional.

The trouble is, my extrusion shaders are running in software, not GPU. So, technically, it's not really a GPU shader

Here's my positional extruder:
Code:
```uniform vec4 localLightPosition; void main() {     /*         Direction in untransformed space from the vertex to the light     */     vec3 localLightDirection = normalize( localLightPosition.xyz - gl_Vertex.xyz );     vec4 result;     float ndl = dot( gl_Normal, localLightDirection.xyz );     if ( ndl < 0.0 )     {         vec4 pos = vec4( -localLightDirection, 0.0 );         result = gl_ModelViewProjectionMatrix * pos;     }     else     {         // leave it alone         result = ftransform();     }          gl_Position = result; }```

Here's my directional extruder:
Code:
```uniform vec4 localLightDirection; uniform vec4 infinity; void main() {     /*         We're operating on untransformed model coordinates, so use vanilla gl_Normal     */     float ndl = dot( gl_Normal, localLightDirection.xyz );     vec4 result;          if ( ndl < 0.0 )     {         result = gl_ModelViewProjectionMatrix * infinity;     }     else     {         // leave it alone         result = ftransform();     }          gl_Position = result; }```

And here's the common fragment shader:
Code:
```void main() {     /*         Just write the fragment.     */     gl_FragColor = vec4( 1.0, 0.0, 1.0, 0.5 ); }```

Note, the fragment is non-opaque so I can visualize the volume for debugging.

I have NO idea why the GLSL is running on the CPU.
Sage
Posts: 1,199
Joined: 2004.10
Post: #8
SOLVED: Thanks to a kind answer on mac-opengl.

The answer is GLSL can't unroll a conditional if you do matrix math in it. So, for reference if anybody stumbles on this, here's my corrected shaders.

Directional extrusion:
Code:
```uniform vec4 localLightDirection; uniform vec4 infinity; void main() {     vec4 p, q;     float ndl = dot( gl_Normal, localLightDirection.xyz );     p = gl_ModelViewProjectionMatrix * infinity;     q = ftransform();     if ( ndl >= 0.0 ) p = q;     gl_Position = p; }```

And positional extrusion:
Code:
```uniform vec4 localLightPosition; uniform vec4 infinity; void main() {     /*         Direction in untransformed space from the vertex to the light     */     vec3 localLightDirection = normalize( localLightPosition.xyz - gl_Vertex.xyz );     vec4 p,q;     p = gl_ModelViewProjectionMatrix * vec4( -localLightDirection, 0.0 );     q = ftransform();     float ndl = dot( gl_Normal, localLightDirection.xyz );     if ( ndl >= 0.0 ) p = q;     gl_Position = p; }```

Now, in the demo I used with three light sources I get 60fps, instead of 30, with very little CPU hit outside of visibility determination.

In my stress test, however, I get the same FPS as with the CPU implementation ( about 20fps). But that's great, since my CPU is barely being touched, and thus has more cycles to dedicate to physics and AI. Also my stress test really is a "stress test", and unrepresentative of my intended usage.
Moderator
Posts: 869
Joined: 2003.01
Post: #9
It looks nice. Do the shadows only work for convex objects, or all kinds?
Sage
Posts: 1,199
Joined: 2004.10
Post: #10
Only convex. Supposedly there are tricks/hacks to make stencil shadows work with non-convex objects, but I haven't read into it.

Obviously, shadow maps are the future. But I can't wrap my brain around the math required to make them work robustly.
Luminary
Posts: 5,143
Joined: 2002.04
Post: #11
Stencil shadows "just work" for nonconvex objects, surely...
Sage
Posts: 1,199
Joined: 2004.10
Post: #12
Sorry, the terminology was wrong. What I meant was "closed". Non-Convex is fine!
JoNo21
Unregistered

Post: #13
Hey sounds like a pretty cool technique, I think I get the majority of how its done. Is there any chance I could take a peek at your source?

Thanks!