What possibilies do I have to create a shadow volume for objects with “bad” geomtry, i.e. concave, maybe 2-sided, maybe not closed. I got a brute force method working that generates a shadow volume for each triangle and fail in my attemps to work on extruding the edges only. I think we can agree without too much discussion that the brute force way is not optimal performancewise.
Can you please outline alternatives?
Its very possible, just do it as you would normally. Match up polygon neighbors (polygons which share an edge), and when rendering, extrude from the front faces.
This will work just fine on models which arent “closed”… at least it works fine for me.
DopeFish: are you using Z-pass or Z-fail (Carmack’s reverse) ? Because from what i remember, Z-fail requires the geometry to be 2-manifold…
Y.
I think a need a little more detail here:
Which edges do you extrude (= which edges belong to the silhouette)? Regular edges that have exactly two adjacent faces where one is facing the light and one isn’t and (irregular) edges that belong only to one face - Is that what you’re proposing?
Just go ahead and combine the geometry with shared edges for those that are possible. When you later on create the shadow volume, you can generate a closed volume for any geometry. Just more or less edges.
I use the reverse carmack and can take any geometry and create shadows.
Use shadow buffers instead; they don’t care what you’re drawing as long as it renders 
I’ll do (and post my questions regarding perspective shadow mapping then 
) if (and only if) I’ve made those stencil shadows work perfectly.
Tooltech or DopeFish, could you elaborate on your approach a bit more? I’ve got a silhouette algorithm running, but it fails for objects that have holes. Or do you have any references to articles/papers about that?
In my scene graph I detect whenever a geometry is changed. If so, I send all the tris, tristrips, fans etc to an optimizer that basically uses hash maps to find edges between sindle triangles. I then build a connectivity structure that holds the info about what shared edges exist between triangles and their relative angle between them.
This conncetivity data is then used whenever the geometry matrix of the light position changes. I use it to build a surface out of the triangle soup that is front facing the light. All sides of the triangles in the soup that has not a shared edge with another front facing tri gets a “side” marker.
By rendering the front triangles, render the front triangles but transformed towards the direction of the shadow (back) reversed and adding “sides” from the marked triangles i always get a closed shadow volume.
Even if the traingles overlap the result of the stencil op is ok for sharp shadows.
The only problem I got with traingle soups is the when tris overlap, my soft shadow algo gets too dark for overlapping traingles because they get a too high stencil value.
You can download my shadow demo on my web page where you can load any kind of model and test with.
Stefan,
If I understand correctly you are currently using the “traditional” method of generating a silhouette by finding adjacent triangles where one is facing towards the light and the other one isn’t. You then extrude the edges to create your volume and use the edges facing the light to cap the end near the object and the away faces to cap the edges at “infinity”.
The problem is that not all of your meshes are properly closed? ie. There are triangles which do not necessarily have a neighbour (ie. Their neighbour may not use the same vertices because of texture coordinate differences)?
If this is the case then you could do what I do. I keep a separate mesh, untextured, in memory, which I use for both collision detection and for the generation of shadow volumes. If you do this you can have a mesh that is completely closed (ie. there isn’t any texture so the tex coords don’t affect the outcome) and you can also use simplified mesh as a type of optimization (in my case I have a sphere - the displayed mesh is quite detailed - the shadow/collision mesh is greatly simplified - when you look at the shadow, you can’t tell the difference).
Basically I just give make each triangle “aware” of its neighboring triangles, and when rendering, if the triangle is front-facing, i check its neighbors to see what theyre facing is. If theyre backfacing, I cast shadow from the shared edge.
Im using the depth-fail approach, and the shadowing is quite robust. I just create maps using the Q3radiant map editor, place some lights, and it automatically “just works” fine in each and every test map Ive done up.
For handling models which arent “closed”, and you come across the triangle which has an edge with no neighbor, just cast shadow for that edge.
http://mrg.telefragged.com/shadows/testmap2_4.jpg
[This message has been edited by DopeFish (edited 02-28-2003).]
For Tenebrae we had to generate volumes from arbitrary triangle soups.
We just find neighbours and render volume sides for the edges with invisible (or unexistent) neighbours.
The trick to capping your volumes is rendering the light facing faces again with extruded vertices and inverted windings.
One problem we had was when 3 triangles had the same shared edge (well it’s a triangle soup nothing is stopping this from happening)
you can read the discussion ont this here http://sourceforge.net/forum/forum.php?thread_id=810327&forum_id=209231
Charles
I found that, in cases where 3 triangles shared the same edge, that it wasnt hard to fix at all.
I may not have done it the best way, but the results come out perfect
I still don’t get it. Here are my test cases that I want to make work.
The first consist of a single quad that is tesselated into 2 triangles. The quad is 2-sided, i.e. it is always facing the light (and thus never culled). Clearly the four edges of the quad belong to the silhouette and the diagonal of the quad doesn’t.
The first question is whether I should duplicate all 2-sided triangles (after that every triangle is just 1-sided). If I did every edge had 2 faces with the exception of the diagonal which had 4 faces! The four edges would belong with a simple “one front facing face and one back facing face” rule to the silhouette. But I don’t see why the diagonal wouldn’t (the edge has four adjacent faces and one of them has a normal pointing in the opposite direction).
If I did not duplicate the triangles I would just add the edges with one face to the silhouette and the test would pass (but the next test won’t).
The next complicated case is an open “cylinder” that has only 3 quads as side faces and no caps. The three quads are 2-sided again. The isolated edges (with only one adjacent face) belong to the silhouette and (at least most of the cases) two of three edges where the quads join. The problem is how to determine which edges (especially if I just assume a triangle soup and don’t know that the normals are actually pointing outward). All faces are facing the light (by definition of 2-sided) thus the rule doesn’t work. If I duplicated all triangles such that I only had 1-sided triangles how would the one edge that does not belong to the silhouette and the diagonal of each quad differ from the other edges?
Thanks
Here’s an attempt to illustrate the latter test case with ASCII-Art:
Front view:
/
/__\Side view:
| |
|___|
(Edit: ASCII-Illustration, the side view should simply display a quad)
[This message has been edited by stefan (edited 03-03-2003).]
I think (could be wrong) that your best bet will be to duplicate all of your double sided polys as single sided ones. You can do this just for the shadow volume creation (rather than for sending to the GPU - although if you’re using 2 sided lighting then you may benefit from sending your split polys to the GPU).
The reason I say this is that if your polys are double sided then you could just use all edges to create your volume but you would end up using edges you don’t need (the edge across the diagonal of a quad for example).
It also gives you a nice way out of having an “open” mesh (ie edges which are not shared) because the “away” side will share the previously unshared edge with the “toward” side.
If I duplicated the double sided triangles I guess the resulting shadow volume is identical to the shadow volume per triangle technique.
How can I avoid including the unnecessary edges into the shadow volume (like the diagonal edge of a quad)?
I haven’t tried this myself, but I think this should do it. Basically, in addition to the silhouette edges, you extrude each open edge. By open edge I mean an edge that belongs to only one face. Then, if you cap your volume at infinity by mirroring the frontfaces (as seen from the light, again), this should generate closed volumes.
Unless, of course, I’m wrong 
-Ilkka
Originally posted by stefan:
How can I avoid including the unnecessary edges into the shadow volume (like the diagonal edge of a quad)?
The same as you normally would generate the volume… you check if the 2 triangles are front-facing, and if they are, you dont extrude that edge.
For the QUAD, it should be planar, else youd be better of treating them as seperate triangles.
JustHanging, Youre absolutely right with that. Its pretty much the general way to handle them when using the depth-fail approach.
Your biggest problem will be the fact that for EVERY triangle, there is going to be 3 edges that both face the light and face away from the light. At least in my code there would because when I add a vertice to a mesh it checks to see if the vertice already exists, if it does it doesn’t duplicate it, it just returns the existing index.
What you really need to do is be able to identify the edges which are not shared (eg. the ends of your “cylinder”) and only allow the sharing of verts in these cases. This way, when you duplicate the triangles, also duplicate the verts which are on a shared edge. The edges which are not shared will use the same verts.
Hope this makes sense…
I know this is an old thread, but I thought I’d add my late 2c.
this is mainly a reply to the post about tenebrae, where 3 face edges have shadows cast when there is only 1 lit face in the group…
anyway
Basically yesterday I managed to get my shadow volume generating code working for any geometry form whatsoever. And that makes me pretty happy
anyway. the way I went about it was pretty simple (the idea hit me in the middle of a software engineering lecture )…
basically, for volumes, treat each triangle as if it is casting a volume of it’s own, just a single volume, two triangles at each end, with 3 quads (or 6 tris). This would work fine but obviously has the issue that you are drawing insane numbers of triangles. (around 4x )
So…
assuming you have structures for edges and traingles, and that there are no duplicate edges (inculuding reversly wound edges), and that each triangle has a pointer to each edge, you can do the following…
Store, in the triangle, how the edge is wound realitive to the triangle.
ie, if the edge is between vertex 1 and 2 of the triangle, it is wound with the triangle, but if it’s between 2 and 1, it’s the opposite.
This would be an extra byte in the triangle structure. (bit flags).
In the edge, store a single char value, indicating how it should be drawn. (I’ll call it drawMethod here)
For each lit triangle, loop through the edges it is connected to, if the edge is the same winding as the triangle increment drawMethod, if it’s wound opposite, then decrement it.
What you find, is that you end up with the shiloette edges all with +1 or -1 drawMethod values, BUT for edges connected to 3 or more faces, you can get values of +2,+3,-2,-3, etc. This is where you extrude the edge twice, or 3 times, etc. So far I’ve found this works flawlessly (tested to situations where edges have 5 triangles connecting).
I don’t know if this is standard (I personally choose to try things myself before I resort to tutorials, etc). so if it is please smile and move on.