13 replies to this topic

[elijah]

I tried using this formula

normal = cross( (b - a),(c - a) );
sign( dot( cross( normal, (b - a) ), (c - a) ) );

but I'm always getting a positive number. It should return either positive or negative value based on the winding rule.

Can anybody help me on this.

[Mihail121]

Yes, sure it is not working, because:

// cross(normal, (b-a)) is, in fact, (c-a) !!!!

sign(  dot( cross(normal, b-a), c-a )  ) =
sign(  dot( c-a,c-a )  ) =
sign(  cos(0)  )  = 1

You just need a target vector to compare the plane's normal you already have.

edit: nonsense

[poita]

What are you trying to do?

If you do some algebra, then you'll see why you always get a positive number:

Let B = b-a
Let C = c-a

N = B x C

(N x B) . C
=((B x C) x B) . C

Now use this (from wiki)

to simplify the (B x C) x B bit

= ( (B.B)C - (C.B)B ).C
= ( (B.B)(C.C) - (C.B)(B.C) )
= ( |B|²|C|² - (C.B)² )

And since


= ( |B|²|C|² - (|C||B|cosθ)² )
= ( |B|²|C|² - |B|²|C|²cos²θ )
= |B|²|C|² ( 1 - cos²θ )

and since cos²θ ≤ 1, the whole expression will always be positive.

Quote

// cross(normal, (b-a)) is, in fact, (c-a) !!!!

No it isn't :P

[Mihail121]

poita said:

No it isn't :P

Yes, it is.

[poita]

Mihail121 said:

Yes, it is.

You do realize I just proved you wrong with some relatively easy to follow algebra.

(B x C) x B does not necessarily equal C.

A simple counter example:

B = (1, 1, 0)
C = (1, 0, 0)

B x C = (0, 0, -1)

(B x C) x B = (1, -1, 0)

[Reedbeta]

To return to the original topic, detecting/regularizing winding is difficult in general.

If you have a convex shape, you can do it by having the user provide a single point inside the object. Then for each polygon, you can work out the winding according to whether the picked point falls in front of or behind it.

If you have a connected, orientable, 2-manifold mesh you can do it by having the user choose the correct winding on a single polygon and propagating that to neighboring polys until the whole mesh is covered.

Can you tell us more about what you're trying to do? With more context, we might be able to recommend a better approach.

[SyntaxError]

I'm not sure what you are trying to do here. A winding rule is something that you or someone else has to determine in advance. It's typically not something that you detect.

For instance if you have a box you can think of it as solid on the inside and having it's surface on the outside. Alternatively you can also think of it as a space that you can stand inside such that everything outside of it is solid and the surface is on the inside. Granted the first case is much more common but the second one is just as valid. A winding rule is a convention. Someone correct me if I'm wrong but I don't think you can auto-detect it.

Just pick one and construct your geometry to conform to it.

[poita]

Well yeah, you can define it to be inside or outside if you want, but assuming you want it to be on the inside (which is the general assumption) you can calculate it.

[elijah]

Thank for all your help. I'm very rusty on my maths. My previous job is embedded design engineer. We just used tools & libraries. I will go digest all your explanation tomorrow.

What I'm trying to do is to check whether the shape that has being created by my staff through programming sequence conforms to the winding rule. Its difficult to visualize in details to check their work. So I decided to write a program to examine every triangles that froms the object. Previously I have being clicking each triangle to check visually.

To keep it simple, I will know the center point of the shape at point ( 0, 0, 0 ). I will also know any points that are inside the shape. The shape could be any form like sphere, cylinder, torus and etc.

Can anybody help me on this ? Once again thank you for all your help. I hope my standard can come to par with you guys one day.

[SyntaxError]

poita said:

Well yeah, you can define it to be inside or outside if you want, but assuming you want it to be on the inside (which is the general assumption) you can calculate it.

That may be, but that doesn't explain why he needs to auto-detect winding which certainly can't be done from a single triangle.

[Mihail121]

elijah said:

To keep it simple, I will know the center point of the shape at point ( 0, 0, 0 ). I will also know any points that are inside the shape. The shape could be any form like sphere, cylinder, torus and etc.

Can anybody help me on this ? Once again thank you for all your help. I hope my standard can come to par with you guys one day.

If the center point is known to be at (0,0,0) and we are talking about spheres and cylinders here (tori won't work), you can follow Reed's advice. Calculate for each triangle the plane's normal, and check which side of the triangle's plane the point (0,0,0) is at. It's as simple as that. By the way, why even bother if these objects could be modeled in 30 seconds using every 3D software out there with a known winding rule.

[elijah]

I think I solved the problem

Vector3f p = new Vector3f(p1);
Normal.dot( p )
it returns either 1 or -1

Is this correct ? The reason I need to check because of the modelling software library A U B , A - B , B - A will result in a hole when it should not be

[SyntaxError]

elijah said:

Thank for all your help. I'm very rusty on my maths. My previous job is embedded design engineer. We just used tools & libraries. I will go digest all your explanation tomorrow.

What I'm trying to do is to check whether the shape that has being created by my staff through programming sequence conforms to the winding rule. Its difficult to visualize in details to check their work. So I decided to write a program to examine every triangles that froms the object. Previously I have being clicking each triangle to check visually.

To keep it simple, I will know the center point of the shape at point ( 0, 0, 0 ). I will also know any points that are inside the shape. The shape could be any form like sphere, cylinder, torus and etc.

Can anybody help me on this ? Once again thank you for all your help. I hope my standard can come to par with you guys one day.

I think you need to do something like this. Start at your point (0,0,0) and draw a vector from it extending in though the middle of any triangle. Now you have to count all the intersections with the object (i.e. all other triangles including the one you stated with). If there is an odd number you stated inside the object. If there is an even number you started outside. You can also determine if for the triangle you picked, you are entering or leaving the object. You probably need some special cases to make this work perfectly. For instance if you pass directly though an edge you might end up counting intersections for both polygons on either side of it, however you really only want one intersection. Passing though a point is likewise situation. For each triangle I would check points first, then edges and then the face. That way you can branch off into your special case code properly.

In any case now you have all the information to determine if your winding is correct by taking the dot product of the vector and the normal of the triangle. If your object has adjacency information you can then walk from your triangle and visit all triangles in the object to check their winding. Alternatively you can test each polygon separately with the above method.

[elijah]

Thank You very much for helping me. I have solved the problem by following your suggestion.