PDA

View Full Version : Silhouette Edges



Riskz
04-10-2009, 01:25 PM
It's me again, hehe.
I'd like to know which may be the best algorithm to calculate the silhouette edges.
My object data is stored something like this:

Object:
...
Array of faces-> a,b,c (vertexes)
ta,tb,tc (texture coordinates for each vertex)
Array of vertexes-> x,y,z (position)
nx,ny,nz (normal)
...

Which could be the best way to know the silhouette edge?
May I add a index of neighbour faces to each face?

I couldn't find a tutorial on the web which I can really understand.

thanks

Ilian Dinev
04-10-2009, 05:25 PM
Edges, that are shared between two triangles, and one triangle is a front-face while the other is a backface, are part of the silhouette.

MaxH
04-10-2009, 06:04 PM
An overview of one approach ... Compute angle between each polygon normal and a vector from one of the poly vertices to the eyepoint. If angle > 180 degs (i.e. negative dot product), processing of that poly is complete. If angle < 180, add each edge of poly selectively to an edge list. By 'selectively' I mean only add it to the list if it isn't already in the list. If it is already there, remove it. You will be left with a list of silhouette edges only.

Riskz
04-10-2009, 06:44 PM
Thank to both. I'm now getting an idea of how to idea, but I'd appreciate some help with the code.
Something like:

for(each polygon)
angle= ...
if(angle<180)
for(each edge on the list)
if(edge1 is on the list) remove it
else add it
if(edge2 is on the list) remove it
else add it
if(edge3 is on the list) remove it
else add it
I'd like help with the angle calculation, I'm not very good at 3d math :P

Thanks

todayman
04-10-2009, 07:14 PM
You're not going to actually compute the angle, that's not worth it. Instead, as MaxH says, use the dot product of the normal and the vector from the vertices to the eye point. The dot product of two vectors, a and b, is a_x*b_x+a_y*b_y+a_z*b_z (multiply corresponding components and add them all up). Through some nifty math, this is equal to the product of the magnitudes of the vectors times the cosine of the angle between them. Since the cosine of angles between 90 and 270 (angles facing away from the camera) is negative, any negative dot product means that the poly is facing away from the camera.

Riskz
04-11-2009, 11:34 AM
...use the dot product of the normal and the vector from the vertices to the eye point.
3 questions:
- But if there are three vertices, I will have three separated vectors (from each vertex to the eyepoint).
- The eye point means the position of the camera?
- Do I have to normalize the vectors?

Thanks

Mike Werner
04-11-2009, 06:15 PM
- But if there are three vertices, I will have three separated vectors (from each vertex to the eyepoint). Doesn't matter which one you use.

- The eye point means the position of the camera? Correct.

- Do I have to normalize the vectors? No.

Riskz
04-11-2009, 10:36 PM
Thanks, I'll try to make some time and start coding

Mike Werner
04-11-2009, 11:19 PM
A word of warning - the MaxH algorithm works for convex polyhedra. You may find it unsatisfactory for concave objects. But it's a start.

Riskz
04-12-2009, 12:24 PM
Thanks Mike. At the moment the objects in my game which cast shadows are all convex =). What a stroke of luck.

Riskz
04-13-2009, 03:57 PM
I think tomorrow and the day after tomorrow I'll have some free time to spend on the code.
I've been thinking which could be the best way to organize the edge list.
Are linked lists the best option? It's the only way I can think about which is easy to "remove" and "add" edges easy and fast during runtime

thanks