Sign in to follow this  
Alex Red

Triangles Winding...

Recommended Posts

Alex Red    136
I am converting an Models Database... Found that some models got some Triangles with no CCW vertex order, so, I have to fix them... is there a way ( knowing the plane Equation of the Triangle ) to figure out if the vertices are CW or CCW winding ordered...? tnx [R]ed

Share this post


Link to post
Share on other sites
ajas95    767
A mesh that has consistent winding satisfies the property that each edge is used by 2 triangles and each triangle refers to the edge in the opposite direction (p0p1 in triangle T0 and p1p0 in triangle T1, for example). So you could start with one triangle that is wound correctly and use a floodfill algorithm to go around all triangles that share an edge with the current one, ensure that they wind correctly (correcting any edges that don't), and then visit all their neighbors.

Christer Ericson had an article about this in Real-Time Collision Detection I think. The important part was first generating connectivity info so that you can quickly identify the other triangle that shares an edge with the current one.

Share this post


Link to post
Share on other sites
Alex Red    136
Tnx... but not what I am looking for...
I have no meshes... I have some triangles having no collision matter...
I have to reverse them if ( badly ) CW winded...

nothing else...

tnx the sane
[R]ed

Share this post


Link to post
Share on other sites
ajas95    767
Oh, you know the plane equation! Yeah, just take the cross product: (p1-p0)X(p2-p0) and dot that with the plane normal. the positive or negative result will consistently indicate CW or CCW winding.

Share this post


Link to post
Share on other sites
If i understand the question correctly, you've got a bunch of triangles specified as three verticies and the plane equation (including normal direction). Different triangles may have different windings. Triangles do not necissarily form a manifold mesh.

If this is the case, for each tri call the verticies v0, v1 and v2 (in the order they are specified in the source data). Calculate M = (v2-v0) X (v1-v0), this gives you the normal direction of the tri, if it has CW winding. Let N be the normal from the tri's plane equation.

M.N > 0 => CW winding
M.N < 0 => CCW winding

Does this answer the original question?

Share this post


Link to post
Share on other sites
Alex Red    136
K... I already tried this...

Vertices V0, V1, V2

// get vectors
x1=V1.x-V0.x
y1=V1.y-V0.y
z1=V1.z-V0.z

x2=V2.x-V0.x
y2=V2.y-V0.y
z2=V2.z-V0.z

// The normal by cross product
nx=y1*z2-z1*y2
ny=x1*z2-z1*x2
nz=x1*y2-y1*x2

// Normalize it
r=sqrt(nx*nx+ny*ny+nz*nz)
nx/=r;
ny/=r;
nz/=r;

// Dot product with plane A, B, C
r=nx*A+ny*B+nz*C // tried also adding D

then check CCW or CW based on 'r'

this have already done but seems not to work... is it the right procedure...?
if yes I suppose the DB got some more problems...

tnx

[R]ed

Share this post


Link to post
Share on other sites
Bug in calculating cross product, should be
ny=z1*x2-x1*z2

Also there is no need to normalise it as all you care about is the sign of r, not it's magnitude.

If r > 0 the winding is CCW otherwise it's CW.

Share this post


Link to post
Share on other sites
Alex Red    136
Tnx Luke...u r right...
however... seems not to work....
I will check better... if u confirm me this is the right procedure...
not sure then about some equations in the DB, and if it's sure this is the right procedure, I will ask DB creators...

tnx again

[R]ed

Share this post


Link to post
Share on other sites
ketek    132
Basically , you can't , i've tried some time ago too, i tried every plane equation and type of cw or ccw identification scheme, unless you pick the correct winded triangle and start from that, there is no way to tell the pc
if the modeller who did the mesh wanted that triangle to be cw or ccw, forget about the normal, it works only if your mesh is totally enclosed with no concavities ( just a bubble or a sphere ).
Of course i could be wrong , but i did try *everything*

Share this post


Link to post
Share on other sites
oliii    2196
How do you know they have no CCW order? Because they lit wrong? because they don't get stripped properly?

surely the mesh must have some sort of hints on how the faces are oriented. Like vertex normals, or lighting.

Also, as said before, you cannot have two triangles sharing the same edge, also sharing the same vertex ordering. On one triangle, the edge from the winding order maybe point A and B in that order. On the other triangle, it's got to be from B to A.

But artists messing up with winding orders unconsistent meshes (T-junctions, bad welding, ect...), ought to get a slap between the ears.

Share this post


Link to post
Share on other sites
Alex Red    136
Well...
Basically still I dunno if it works... math speaking and looking at model for me it should... as the old Engine ( BSP ) was using plane normals to find the culling of a triangle...
However... I found why id does not work at present... speaking with Artits found that the triangles giving problems seems to be transformed on the fly while drawing model...
and guess a transformation...? Mirroring along an axis ( what an idea... )...
that makes same vertices of the mirrored triangle winded from CCW to CW...
and I could not see before as my test procedure is applied converting the model, and it's done at DB level, and not when it's drawn...

so... tnx to any1 for help anyway

I'll fix this too and then try the procedure

[R]ed

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this