NordFenris

01-04-2003, 03:25 PM

I'm trying to speed up our shadow volume code, and as such, we need to find the mesh silhuette (sp?). We were thinking of taking the culled-neighbour approach (any edge having one culled and one unculled triangle is considered part of the silhuette)

So, we set out to build an adjacency graph, to see which polygons neighbour which. I tried the brute force approach, by looking at each polygon, and then sifting through the poly buffer, and see which polygons share more than two vertices with that polygon. After that, there'll be some sorting, but already here I've stumbled upon a problem. When trying to build the graph for a 2000 poly model, I quickly end up in 36.000.000 vertices that have to be checked (n^2 * v^2, where n is numOfPolys, and v is numOfVertices).

Is there a better way to build a graph like this, or is this headbangingagainstthewalluntileithergivesin method the only known way?

Of course, I need to ask - is this how the shadow silhouette is usually calculated? Or have I made a huge mistake?

Thanks for any input!

So, we set out to build an adjacency graph, to see which polygons neighbour which. I tried the brute force approach, by looking at each polygon, and then sifting through the poly buffer, and see which polygons share more than two vertices with that polygon. After that, there'll be some sorting, but already here I've stumbled upon a problem. When trying to build the graph for a 2000 poly model, I quickly end up in 36.000.000 vertices that have to be checked (n^2 * v^2, where n is numOfPolys, and v is numOfVertices).

Is there a better way to build a graph like this, or is this headbangingagainstthewalluntileithergivesin method the only known way?

Of course, I need to ask - is this how the shadow silhouette is usually calculated? Or have I made a huge mistake?

Thanks for any input!