0
\$\begingroup\$

I'm doing some topological operations on my mesh and I need to know the winding order for my mesh.

Since I will be importing models from different sources I will need to know whether the winding order is clockwise and anti-clockwise so I can get normals and things like that.

Question : Is there a way that I can determine the winding order of a list of vertices.

Edit 1: I am using a 3D mesh

\$\endgroup\$
  • \$\begingroup\$ Safe to assume this is in 3D? In 2D, we can assume that the side facing out of the screen is the front, and compute the winding order that way. In 3D, we need some additional information to know which side of the polygon is supposed to be the front (since a polygon that's wound clockwise when you look at it in one direction is wound counter-clockwise if you look at it from the opposite side). What's your source of ground truth for determining which side is "out"? \$\endgroup\$ – DMGregory Jun 2 '18 at 17:43
  • \$\begingroup\$ You don't need to know the winding order to get the normal. A simple cross product of the vertices already takes that into account. \$\endgroup\$ – Bálint Jun 3 '18 at 0:09
  • 1
    \$\begingroup\$ @Bálint true, but there are two normals to a polygon in 3D: one pointing "out" and one pointing "in" — we usually use knowledge of the winding order to compute the outward-pointing normal. If the mesh might be wound either way then we'll need some other piece of information to tell us which side faces out. \$\endgroup\$ – DMGregory Jun 3 '18 at 11:59
  • \$\begingroup\$ @DMGregory is there anything else i need to add to ensure I get an answer \$\endgroup\$ – user116458 Jun 3 '18 at 14:02
  • \$\begingroup\$ I asked above what information you have to distinguish the front/outside face of a polygon from the back/inside face, if you don't know its winding order in advance. Meshes can, in the most general/worst case, be a disorganized polygon soup without an interior volume, so we'll need some clues to work from to figure out which side is supposed to be the front. If you have any information at all about what kinds of meshes and shapes you're working with, that helps narrow the uncertainty. \$\endgroup\$ – DMGregory Jun 3 '18 at 14:05
0
\$\begingroup\$

There is no way to automatically infer the winding order of a 3D mesh that will work for every possible input.

For instance, if I give you the triangle (0, 0, 0), (1, 0, 0), (0, 1, 0) alone with no other context, you don't know whether it's meant to be wound counter-clockwise (so its front faces out along the z- axis) or clockwise (so its front faces out along the z+ axis). (Assuming a left-handed coordinate system, but the coordinate system could just as well be right-handed, flipping the whole thing)

Both of these would be valid interpretations, and you'd need to ask the creator or use some knowledge about the mesh's format or what it's meant to represent to sort out which version is intended.

But there is a common special case where we can infer the correct facing with higher confidence: if your meshes represent solid objects and you have watertight manifold geometry. (This means that the mesh makes a continuous surface with no holes, gaps, loose edges, or single-sided fins)

If you have such a mesh, you can guess at its winding, then check whether that guess makes sense by seeing if it puts the front face of each polygon facing "out" of the solid rather than inside. (But note: there are rare cases where we make meshes that have been deliberately turned inside-out for various effects, so even this test isn't foolproof!)

It proceeds like this:

  1. Pick a triangle/polygon arbitrarily

  2. Construct that polygon's normal according to your guessed winding

  3. Cast a ray through a point in that polygon, in the direction opposite its normal. Test this ray against every other polygon in the mesh (this can get expensive)

    • If you get an odd number of hits (hitting the back of another polygon, then possibly the front of another then the back of another, or any number of front-back pairs), then your winding guess looks correct. This is the pattern we'd expect to see when firing into a solid shape.

    • If you get an even number of hits, then your winding guess was probably incorrect, and you should use the opposite winding instead.

You can run this test for several different sample polygons in your mesh to build up consensus, and try to weed-out outliers due to non-manifold geometry like single-sided leaf fins.

As you can see though, it's a lot more work, and has fewer guarantees, than just inspecting your geometry source format to determine what winding is standard for that type, or asking whoever made the mesh.


(I originally skipped this case because you said you wanted to generate normals, and didn't mention that you had them available as input. But for completeness...)

If your mesh has normal vectors, then you can use these as the ground truth for the intended front facing direction (provided the creator of the model isn't doing anything too weird with manually-adjusted normals...)

Say you have a triangle with points (in order) a, b, c

Compute the expected normal of your triangle by taking the cross product:

 expectedNormal = Vector3.Cross(b - a, c - b);

Now compare that against the normals that came with your mesh (if your mesh has normals defined per vertex, you can average the three vertex normals for a triangle to get a triangle normal. Or you can average all the expectedNormal values for triangles bordering a given vertex to get a vertex normal instead)

agreement = Vector3.Dot(expectedNormal, sourceMeshNormal);

If agreement > 0 then your mesh is wound counter-clockwise when looking at it against its normal in a right-handed coordinate system, or clockwise if you're in a left-handed coordinate system. If agreement < 0 then your mesh is wound clockwise in a right-handed coordinate system, or counter-clockwise if you're in a left-handed coordinate system. If agreement is zero then the test is inconclusive for this triangle (someone's cranked the input normals to be near-zero or near-parallel to the surface for some reason), and you can try again with a different part of the mesh.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy