Shadow Volumes via Vertex Shader

[MrFloopy]

Hi all,

Am using a vertex shader for shadow volume extrusion and have hit a snag. When two vertices share a common position but not normal or texture coord, I create degenerate faces between them an this works fin for mist cases.

the problem is that the vertex shader calculates whether to extrude the vertex or not based on the vertex normal and not the face normal, this can create areas where a vertex should be extruded away but is not since it's shared vertex normal is not pointing away from the light.

Short of creating unique vertices for each face I cannot think od a solution to this.

Any ideas?

 

[Hyp-X]

the problem is that the vertex shader calculates whether to extrude the vertex or not based on the vertex normal and not the face normal, this can create areas where a vertex should be extruded away but is not since it's shared vertex normal is not pointing away from the light.

Actually it's worse when the vertex is not shared as you'd get gaps in the shadow volume which can cause surprising light leaking effects.

Maybe you should tell why you want to calculate the volume with VS so you cat get an advice in the right direction.

 

[MrFloopy]

Actually it's worse when the vertex is not shared as you'd get gaps in the shadow volume which can cause surprising light leaking effects.

Not if you place degenerate tri's between shared edges with non-unique verts.

Maybe you should tell why you want to calculate the volume with VS so you cat get an advice in the right direction

Because of the CPU saving. Am running lot's of physics at same time so any CPU time saved is very important (Yes, even to detriment to exact shadow volumes although the less artifacts present the better obviously). And lights in scene can be arbitrarily dynamic so calculating silouettes are to be avoided if possible.

It is quite robust if degenerate tri's are placed between every edge, however this should not be required in all cases. I am thinking that only certain edges that share non-unique verts need these degenerate tris between them. I guess it's a matter of what metric is required to determine which do and which don't

 

[Hyp-X]

Not if you place degenerate tri's between shared edges with non-unique verts.

Oops missed that.

Well, the correct shadow volumes needs the side triangles, so this is only achievable the way you described it (creating unique vertices for each face).

On the other hand the other solution might not be that bad - worth a try. It might depend on the surface complexity of the object.

 

[MrFloopy]

Will give it a go. Will try based on a face to face angle factor. Probably worth a bit of extra shadow geometry.

 

[Hyp-X]

My guess is that the most visible artifact would be "shadow popping", when a vertex turns from lit to non-lit the shape of the shadow casted on another surface might have a sudden change. Might be small if the angle between the neighbour faces is small.

This is the only way to do it when N-patches are enabled, but since N-patches make the mesh more smooth, it should lessen the popping effect.

 

[MrFloopy]

My guess is that the most visible artifact would be "shadow popping"

Yes it is, but by using a self shadowing term in the diffuse and specular pixel shader this is reduced somewhat.

Still biggest problem is as I described which can cause quite a few holes in the shadow (If you can have a hole in the absence of light )

I think a completely robust solution is probably not likely but considering the alternatives it still looks pretty impressive.

 

[pcchen]

I did some experiments a while ago to use vertex shader to mimic my CPU implementation of shadow volumes (which is quite robust). However, its overhead is too large (a quad for each edge). There are also some problems with vertex blending (it is quite troublesome to recompute the true normal of a triangle). I decided to keep using CPU to do everything including vertex blending and shadow volumes.

 

[ector]

I am using an approach, based on the Robust Shadow Volumes doc, where I find silhouettes in software using a somewhat fast algorithm with no need for an edge structure, and then do the final extrusion calculation in hardware by for each vertex passing in a number, 0 or 1, telling whether or not this vertex should be extruded to infinity or not. I've been thinking about how to move more calculations to the shader but so far I've not been successful. I have no idea if this algorithm is fast since I've only used it on fairly simple test scenes, but making, extruding and drawing shadow volumes from a 10000-poly object in realtime is no problem on my athlon 1800.. maybe doesn't say very much..

Anyway, here's my optimized shader (not as readable as it used to be anymore ) if anybody is interested:

; v0     = position
; v1     = extrudeAmount <- {0,1} (NOTE this is reversed, vertices you 
;                                   want to extrude should use 0, others 1)
;
; c0-3   = Transposed matrix
; c4     = Homogenous light position


;(Ax*Lw - Lx*Aw, Ay*Lw - Ly*Aw, Az*Lw-Lz*Aw, 0);
mul r1, v0, c4.wwww
mad r1, c4, -v0.wwww, r1

; lerp between v0,r1
add r2, v0, -r1
mad r0, r2, v1.xxxx, r1

; Transform position
m4x4 oPos, r0, c0

 

[3dcgi]

ector. I'm curious how your silhouette extraction is done. I've read about some methods before, but many needed a special data structure. Do you have a link to the algorithm or did you develop it yourself?

Thanks.

 

[ector]

well, i'm actually using a completely rewritten version of the not very efficiently written algorithm Microsoft uses in the ShadowVolume sample in DX8SDK.. check out that sample for the algorithm.

Anyway it's basically:
maintain a list of edges.
go through all your triangles (since you need to do it anyway for capping).
for each front-facing triangle, apart from adding it to your list of cap polys, call AddEdge(v0,v1); AddEdge(v1,v2); AddEdge(v2,v0);

AddEdge is a function that takes an edge, and adds it to the edge list if it's not already there, OR REMOVES it from the list if it is! this will leave you with a list only containing silhouette edges.
To remove an item from this list, take the last one in the list and put it where the old one was so you won't have to shift around so much data.

I have made the observation that when you add a new edge, you only need to test for edges in the list going in the "opposite direction", if your mesh is correct.

Maybe an algorithm with connectivity information would be slightly faster, but I really like the simplicity of this and not having to keep track of an edge structure for each mesh.

 

[3dcgi]

Thanks for the explaination.

 

[Hyp-X]

Well, that algorithm can screw up on some meshes (you can count on artist to be innovative, and create such meshes! )

Also I don't think that "removing from the list" is a particularly fast operation, as it involves searching.

Keeping an edge buffer is actually moving this searching out of real time code.

 

[arjan de lumens]

To avoid searching through the entire edge list for every time an edge needs to be added/removed, you could use a hash table to store the edges. Which should give you a rather dramatic speedup for large-polycount models. Although you will have to experiment a little to find a good (fast and sufficiently random) hash function.

 

[MfA]

If you go to that much trouble not taking connectivity into acount becomes a bit silly ... can't beat O(1).

 

[ector]

>Also I don't think that "removing from the list" is a particularly fast
>operation, as it involves searching.
uhms.. see the note how I do it. it's very fast (I just move the last item in the list to where the hole is, since order doesn't matter)

>To avoid searching through the entire edge list for every time an edge >needs to be added/removed, you could use a hash table to store the >edges. Which should give you a rather dramatic speedup for large->polycount models. Although you will have to experiment a little to find a >good (fast and sufficiently random) hash function.

yeah, I've thought of this to and I'll do some research into it once this edge search becomes the bottleneck.. and for various reasons, I don't think it's the bottleneck right now. Besides, i'm shadowing a morphing 10 000 poly object in 60fps (on athlon 1800+ / GF2MX!).. so it's not THAT horribly slow
I know that with more advanced scenes this is still not going to be fast enough, but i'll worry about that when that time comes...