Search code examples
algorithmgraphic

How to compute the cyclic order for triangles' indices?

I am currently learning about computer graphics but the topic of cyclic ordering is something that I can't seem to grasp. I was told that software like blender export the indices of triangles making up a model in a cyclic order. This way, the normals are ensured to point outward from the model.

I am not so sure what cyclic order means and how does this kind of ordering applies to triangles indices? Also, if I want to procedurally generate a mesh, what would be the algorithm I should use to apply cyclic ordering so that my mesh has correct indices for calculating normals?

Solution

  • Cyclic ordering means that cyclic permutations of vertex indices in a certain direction give a outward pointing normal. To illustrate this, here is a diagram:

    enter image description here

    The cylindrical arrows show the outward pointing normal. On the left is the anti-clockwise ordering convention, and on the right clockwise. The circular arrows show the directions that you can shift ("permute") the indices in, for the normal to stay the same.

    For the anti-clockwise convention you would calculate the normal by (p2 - p1) x (p3 - p1), and for clockwise, (p3 - p1) x (p2 - p1). Note that the use of particular indices in these formulas is arbitrary as cyclic permutation would cover all possible ways of calculating the normal.

    I don't know if one convention is more commonly used than the other (in OpenGL, for example, you are free to set either); but if it is then I would guess the anti-clockwise (2 before 3). Again - it only matters that different programs using the same data also share the same convention.

    As an example, OpenGL uses the convention to determine how to calculate the outward normal, which it uses to do backface culling. It takes the dot product of the normal with a displacement vector from the camera to any point in the triangle's plane. If the result is negative then the triangle is facing the camera, and vice versa. (This is only useful for closed meshes though - you would see holes as transparent from certain angles. Again, OpenGL provides the option to disable backface culling entirely for this purpose.)

    If you procedurally generate a mesh, and want to compute the correct index ordering for all triangles, do the following:

    • Set the per-triangle indices in any order (as long as they belong to the correct triangle)

    • Calculate the normal using either convention that you choose (remember to be consistent)

    • Use the method in my previous answer to determine whether the computed normal is facing inwards

    • If it is, then swap any two indices for the triangle. This will switch to the correct ordering.