Fast shadow silhouette generation.

[NicholasFrancis]

hi guys.

I've successfully gotten a mock-up stencil shadowing to work, and now I need to find a good algo for generating the shadow silhouettes. I wanted to discuss this with you before implementing it.

Anyways, my algo looks like this:

[quote]<pre>
foreach light {
foreach nearby object {
if (we have silhouette info from last frame) {
Foreach edge in silhouette {
if it is not an edge anymore, use a flood-fill principle to find the new edge.

}
} else {
Do a brute-force search for the edges

}
}
}


This involves the following steps:

make all silhouette edges potential silhoutte candidates
Each poly adjacent to the edge is either 'inside' or 'outside'
foreach candidate {
get face normal to light for faces on each side.
if (inside poly faces away from light) {
if (outside poly faces from light) {
mark edge as silhouette.
mark all other edges of both polys as candidates.
} else {
mark all other edges of inside poly as candidates.
}
}
if (inside poly faces light) {
if (outside poly faces away from light) {
candidate is an edge.
} else {
all other edges of outside poly are candidates.
}
}
}
[/CODE]

the principle is that I maintain the silhouette from last frame and the check if it is still valid. Where it isn't, I do a flood-fill style updating on the faces around to find the new silhouette.

Do you think this a good method, or is there something that's better?

Cheer,
Nicholas

[Lars]

Hi

I think using previous Frame Information is a good idea. But i am using a special structure for the creation of shadowvolumes. I precreate this structure on load-time.
This structure only contains edges. that could be a volume edge. For each edge both normals are stored (i do not allow models with edges shared by more then 2 triangles).
This way the volume generation gets fast cause you ignore edges between triangles, ontop of a cylinder for example.

But as you already know from your other thread my shadowing algorithm doesn't work yet. Still haven't implemented clipping and the volume generation has errors.

There i am looking into a technique from an Nvidia paper which uses infinite triangles.

Lars

[NicholasFrancis]

I'm thinking:

How about if we look at the edges instead of the faces, so that instead of looking at the normal for a two faces, we somehow just look at the edge?

Don't know 'bout the math, though...

[okapota]

i calculate the connectivity for each brush when it is created, i too, delete every edge that has the same normal on two sides, but actually it should be every edge that the angel between the two normals is <180 degrees. ant way, after that i create a long edge list for each light, composed by the egde lists of each brush inside the light, then i generate the volume, and update it when something moves. i should work it out, but i think it will work. i need to find a way of how to update only the volumes neccessery, because the volumes are stored in each light, not each brush. maybe i should change it. but i dont think.

[okapota]

actually, i have this idea of how to minimize the number of volumes generated, using a bsp. but i doubt i will have time to implement it, but ill try.
do you another way of determining if the eye is inside the volumes or not?

[NicholasFrancis]

Originally posted by okapota:
actually, i have this idea of how to minimize the number of volumes generated, using a bsp. but i doubt i will have time to implement it, but ill try.
do you another way of determining if the eye is inside the volumes or not?

Quick rejection:

If the light (including range) is outside view frustum, there i no shadow (there might ave been, but the light is cancelled out).

Detailed: get the bounding sphere of the object and project it away from the light. If another (visible) objects BS intersects it, there probably is a shadow.

[Kaycee]

You guys might be interested in this paper.
http://people.deas.harvard.edu/~pvs/research/silclip/

They have a method of finding the silhouette edges with minimal testing using a heirarchical tree.

KC

[NicholasFrancis]

Wov! Thanks - I'm downloading as I write this.

Guess theese papers pretty much have stopped any engine development on my part as I try to grasp their contents http://www.opengl.org/discussion_boards/ubb/wink.gif

cheers,
Nich