EdgeListBuilder done, pondering

· by Steve · Read in about 3 min · (595 Words)

I wrote an edge list builder over the weekend as preparation for stencil shadow support. One thing I noticed is that all the stencil shadow demos around make large simplifying assumptions about the geometry they have to process - they assume meshes are made out of a single set of triangles, which reference only one vertex buffer. Meshes have to be ‘closed’ within these limitations (ie every edge has to be attached to exactly 2 triangles). They also can’t deal with duplicated vertices, where vertices in the same position are duplicated in order to allow discontinuities in other vertex components, like normals and texture coordinates. Therefore the edge building methods I’ve seen around the Internet only handle a very small subset of kinds of meshes OGRE supports (which I guess is why they all seem to use Quake models i ntheir demos).

Well, this isn’t good enough in the ‘real world’ that OGRE lives in - in practice it’s extremely common to use duplicated vertices (‘sharp’ lighting edges for example), and many people use meshes which are composed of multiple submeshes (so they can assign different materials), and sometimes these submeshes can use different vertex buffers (they may have different vertex formats). Therefore I’ve had to be a lot smarter with my edge builder. It can take multiple index sets and multiple vertex buffers, and when you invoke the build it rationalises the mesh, identifying duplicate vertices from all the vertex buffers involved and building an edge list which spans the entire set. This means it will happily detect edges between submeshes, where other techniques would throw a wobbler because they’d consider the mesh to be ‘not closed’. It also makes sure that the 2 ends of an edge are always located within the same vertex buffer, so that you can realistically use them to build shadow volumes.

The dark cap is slightly more problematic - when you have multiple submeshes you can’t use the optimisation where you draw a triangle fan from a single point around all the silhoutte edges of the dark cap, because the edges may be in different vertex buffers. I’m going to have to consider this one; it is certainly easier when multiple submeshes used shared geometry because although their indexes are separate, the vertices are in the same buffer so a unified dark cap (and shadow volume) can be built as a single render operation. The light cap is never a problem, because you always render it as the original light-facing polys which can be don ein fragments if need be. The dark cap could be done that way too (rendering the unlit faces) but that’s not as fast as the other method.

Incase you hadn’t grasped from that discussion, my plan for stencils is to use the Lengyel method of choosing the zpass or zfail stencil approach depending on whether the shadow volume intersects the view near plane. The zpass method is faster because it only requires rendering of the shadow volume (not the caps) but does not work when the view is inside the shadow volume. When we detect that case, we fall back on the zfail method (also known as the Carmack approach) which is not as fast because it needs light and / or dark caps, but renders correctly when you’re inside the shadow.

I’ve also added scissor rectangle support to the rendersystems that support it (Dx9 and GL) which I’ll use to limit shadow volume / colour rendering to the attenuation region of the light; this can help eliminate overhead for are distant lights.