View Full Version : Silhouette edge detection

09-12-2002, 06:18 AM
Hi, I'm currently trying to figure out a good way to reppresent 3D objects. What I have so far is the following:
A vertex consist of four coordinates (x,y,z,w)

An edge contains two vertices, the end points, and pointers to the two triangles, that share that edge.

A triangle contains three edges

An object class contains a list of vertices and a list of triangles

In my application, I need to find the outline of an object, i.e. the edges that contribute to the silhouette of the object. The way I would do this is to go through all the trinagles edges and ask if the two triangles that share it are front-facing and back-facing respectively. If so, the edges is part of the outline.
The problem is, that using the above structure will result in edges being reported as part of the silhouette twice. That is, two edges consisting of the two vertices P1 and P2, the will both be detected as silhoutte edge, when in fact only one of them is needed. Once when going from P1 to P2 and again when going from P2 to P1.
Does anyone have any suggestions how to avoid this?

Regards Anders

P.S. I realize this explanation may be a little cryptic, so if anything needs clarification, please say so http://www.opengl.org/discussion_boards/ubb/smile.gif

[This message has been edited by Anders (edited 09-12-2002).]

09-12-2002, 06:31 AM
In your class 'triangle' you have three edges. But you could add 3 booleans that know if an edge of this triangle has been tested. At the beginning all booleans of all triangles are false.
Then when you pick a triangle :
for each edge of the triangle
if the edge has been tested (ie if the corresonding boolean is false) then ignore it
else test the edge and tell that the edge has been tested (ie set the corresponding boolean to true) and tell that the same edge of the neighbour triangle has been tested too (ie set the corresponding boolean of the same edge of the neightbour triangle to true)

Though, this method adds 3 booleans (an overhead of 3bits or 3bytes) in each triangle and needs to flush all booleans whenever you want to compute a new silhouette (that is, you can't compute more than one silhouette simultaneously on the same object)

[This message has been edited by vincoof (edited 09-12-2002).]

09-12-2002, 02:01 PM
if i read u right- the edges are members of the triangles, yes?
or am i wrong?

why not have edges as separate entities, a list of them, and each triangle has a pointer to its three edges. the edges have pointers back to their triangles.

then just walk the edge list, doing the test based on the triangle pointers that are stored in the edges.

so when you get to the end of the edge list, all edges have been tested only once ( http://www.opengl.org/discussion_boards/ubb/smile.gif )

09-13-2002, 01:59 AM
Thanks for your replies.
Vshader, I thought of something similar, i.e. to have a list of edges and then construct the triangles as pointers into that list. But wouldn't that solution give me a problem when I need to draw the triangles.
I mean, I have to ensure drawing in a counter-clockwise order. What I mean is, when two triangles share the same edge, that has the vertices P1 and P2, the order in which to draw the edge vertices is not always the same. It is possible that when I draw triangle number one, I need to draw vertex P1 first and then P2, but when drawing triangle number two, the order is reversed to ensure a counter-clockwise drawing. So when drawing a triangle, it is not as simple as drawing all the edges, or am I wrong?
How do I account for that?

Regards Anders

09-15-2002, 07:55 AM
store the vertex indices in counter-clockwise order in the triangles.
you don't need the edge list for rendering the triangles, only for edge detection

09-15-2002, 04:49 PM
If each vertex has a number, then you only need to consider edges that go from lower numbered vertices to higher numbered vertices; not the other way around.

Alternately, you can consider only edges that belong to triangles whose face normals are facing the light.