Hoping someone could help me understand the algorithm to finding edges. I've been reading and re-reading about shadow volumes and having a really tough go of it for some reason. Namely in the edge finding algorithm. The latest material I'm looking over comes from the book "Mathematics for 3D Game Programming and Computer Graphics" (3rd Edition) by Eric Lengyel. In it he displays the code behind a BuildEdges function. But he does what I've seen done so many other times with Shadow Volumes. He seems to base some stuff of the vertex-index of the points on a triangle and he furthers this even further by checking if the index number is greater than or less than the previous one. Um... what?. The index number, from my personal experience, is just a rudimentary number that correlates to a 3-float-value (x, y, z) in a vertex-table list that only lists vertex values once -- that is, a unique vertex list. But even if the actual vertex-list was not one of uniqueness of it's entries, what good would checking an index number's ordinal value be? From what I can tell, the indices (The order of the vertices in that list) has no rhyme or reason they're just in there in the order the 3D modeling program sees as it's looping through the geometry to export. I don't really understand how the index's number is helpful...If someone could shed some light on this, I'd really appreciate it; thanks!

P.S. I'd post the function, but I'm not sure if that's something the publisher would mind. I can't see why they wouldn't given it's only one function is a fairly thick book, but I'll defer that to the board mods.

-- StakFallT

You are trying to find silhouette edges. these are edges shared by triangles that face in opposite directions along the light direction. In 1 triangle, the vertices will be ABC, and in the other, DCB. BC and CB are both the same edge, but listed in different direction. In other words, each triangle will have a directed edge. After finding the silhouettes, the directed edges are used to create a consistently wound n-gon. Here is a paper from Eric on the subject that goes into it in better detail.

http://www.gamasutra.com/view/feature/131351/the_mechanics_of_robust_stencil_.php?print=1

Ok I think I follow that a little bit better, because even if you have two triangles that share an edge, if the normals to both faces are different, then it means you're at the edge of the model where it starts "wrapping" around toward the back; basically you're leveraging the property of normals being inverse of each other combined with the shared edge so as to determine which edges in the entire model are at that "wrap-around" part. Ok that makes sense, but what about the actual indices? In the function Eric basically checks the index numbers. Here's a short blurb of what I'm referring to... Hope this is ok...

for (long a = 0; a < triangleCount; a++)
{
long i1 = triangle->index[2];
for (long b =0; b < 3 b++)
{
long i2 = triangle->index[b];
if (i1 < i2)
{
...

If you simulate an example, let's say that triangle->index[2] = 103 and b = 0 (following it further -> long i2 = triangle->index[0] = 204)

What difference does it matter if i1 = 103 (for example) and i2 = 204 (again, for example)

103 and 204 only refer to entry numbers in a vertex list not the actual contents, how is checking 103 vs 204 really helpful? I could see if checking the vector at entry 103 vs the vector at entry 204 would be helpful, but the actual index numbers? Is this implicitly assuming that the order of vectors in the global-vector-list (that are referred to by the model's faces) are in some kind of special order? (NOTE: I'm not referring to the point order that make up a face, obviously that does matter, what I'm referring to are the actual index numbers themselves) If that's the case, then yeah I could see 103 and 204 actually having some sort of implicit yet significant meaning. Sorry if I'm being dense. I feel like this is something so simple, just I'm not there yet...Thanks so far btw!

P.S. Yeah that article is almost an exact copy out of his book, only main difference it seems is he left the function code and the GL shader code out of the article.

EDIT: Various edits in an attempt to articulate my point more clearly, also a couple of spelling mistakes

Read through the comment block in the first pass, and then the second. He is gathering directed edges where the i1 comes before i2. This is a shortcut for the second pass, notice the differences between the 2 loops.

hmm ok so if I understand this correctly, it's true that the actual index number has no real meaning;but it's also true that the function doesn't pretend it to be and that the only reason the function really actually works is because the index comparisons being made are the same set, only in opposite directions. If i'm understanding this correctly, it's like saying we're comparing A, B, and C -- we don't really care what A, B, and C are equal to or what vertex in the list A, B, and C's values are referring to, just as long as the two triangles are using AB, BC, or CA (and BA, CB, or AC). I guess maybe a better way of putting it would be to say, so long as Edge 1 and Edge 2 of Triangle 1 and Triangle 2 use the same solution set a comparison can be made, and whether one is less than or greater than has more to do with winding than actually caring about the value itself.

I think what I wasn't getting was that I kept thinking if Triangle 1 has indices: 100, 200, and 300 and Triangle 2 has indices: 50, 150 and 250 how does comparing the two sets of indices help? In that case, it doesn't. The indices of any edge comparisons made must be the same (Obviously in different directions -- hence > or < helps here for that, but the same nonetheless).

Something else that doesn't help is he's using "long a" to refer to the outer loop of all the triangles, yet just below he uses b to refer to the points of the triangle, making them seem related in purpose. He should've renamed a to something like TriangleNum or something, then when he does:

edge->faceIndex[0] = (unsigned short) a;

edge->faceIndex[1] = (unsigned short) a;

it would read:

edge->faceIndex[0] = (unsigned short) TriangleNum;

edge->faceIndex[1] = (unsigned short) TriangleNum;

and "long b" to something like "long PointNum"

much easier to understand and separates a's purpose from b. Which is obvious on the surface but when someone think's they're missing something and that's why they don't understand something, they start looking harder and trying to pull things out from the material.

Well I think what I've just experienced was a serious herp-derp moment. Furthering my previous reply: of course the "solution sets" MUST be the same! If you compared vertex index 100, 200, and 300 against vertex indices 50, 150, and 250 it wouldn't make sense because the vertices aren't even in the same position in space and if they were and they were just redundant vertex entries, technically it'd be a hole (despite overlapping) in the model! i.e. you don't check an edge shared by two triangles by checking two completely different sets of vertices otherwise it's no longer a shared edge lol! ::doh:: So the assumption made is the 3 points checked two of them must be in another triangle for the edge to be shared and it's quicker to check the index value rather than the float values. I kinda figured my brain was being dense lol

I think building the extra indices would actually cause a problem, because if vertex 1 is 0, 0, 0 (making it easy) and vertex (say) 53 is 0, 0, 0. Sure the values are the same, but the indexes are different. Sure you can check the value to see if they're the same, but not only is that slower, but you've introduced the implicit problem that the points aren't actually technically the same.They merely just overlap exactly. Like drawing a line on a piece of paper overtop of the same line, sure it looks like one line, but technically there are two lines there and I imagine that might cause some issues with the algorithm.

EDIT 1: (Rather than create a 2nd follow up post in a row, I figured I'd do this in the form of an edit) And what is the deal with Edge **edgeArray? The function definition is:

long BuildEdges(long vertexCount, long trianglecount, const Triangle *trianglearray, Edge **edgeArray)

and further in the function it does:

Edge *edge = &edgeArray[edgeCount;
edge->vertexIndex[0] = unsigned short) i1;
...

according to the book, edgeArray: "A pointer to a location in which a pointer to the edge array is returned (Lengyel; p.296).", the parameters, and the fact that edgeequal an element in edgeArray (Which appears to be already allocated), this variable is supposed to already be allocated, yet the book says "The return value is the number of edges written to the array edgeArray (Lengyel; p.296)." How can it write to memory without it already being allocated? How do I know it's not allocated yet? Because the function returns how many edges were written to it... If it's not allocated then the above code is going to create an access violation.

Woah. The man himself! :) Thanks!

I think building the extra indices would actually cause a problem, because if vertex 1 is 0, 0, 0 (making it easy) and vertex (say) 53 is 0, 0, 0. Sure the values are the same, but the indexes are different. Sure you can check the value to see if they're the same, but not only is that slower, but you've introduced the implicit problem that the points aren't actually technically the same.

they are not the same . but it is not a problem.

Most of the time in an indexed geometry, there are verticies with the same position but different rest of the attributes. Thus they are different verticies, they just have the position attribute equal- that's all. Do not confuse verticies with distinct points in 3d space. For example a cube with unsmooth normals has 8 distinct positions but also 24 distinct normals. Meaning it has 24 verticies in the end. If even every triangle of the cube was randomly texture cooordinte mapped, it would increase to 36 verticies- the maximum (amount of cube triangles times 3).

The main point in extending the triangles is in detecting a shared position edge - finding 4 indicies that points to position A then B, and then indices that points to B then A (in the manner of indexes ordering) . You then create between those 4 indexed vertices 2 triangles. In other words, you will create 2 triangles invisibly squeezed per every edge of mesh.

Alghorithm might be:

-get 3 indices

-cash all 3 indicies to array

- get next 3 indicies

-roll down the cashed indices array down, until any of the current triangle 3 edges is indexed in them for its position attribute

-build triangle current edge A, current edge B, found edge first

-build triangle found edge first, current edge B, found edge second

reconsider, though I might have been mistaken in some stuff of order though. This is slightly what I use though I have it optimized a little (I seek triangle "one up, two down", for often the seeked triangle is ahead, not down, so I do not scan so many times when seeking- thanks to adjency)

Remember, that the cases of geometry you have brought questioning in posts on are unable to shadow stencil- they are open meshes. Goemetry must ba an enclosed mesh - a mesh where every edge neighbours with an edge. Open meshes are highly metaphysical. Even a paper piece would be 4 triangles 4 positions, not 2 triangles 4 positions. Also, paper in real world has always 8 postions (a flat quad), if we are not quantuming the phenomena of real world.