Ordering vertices of a face for correct triangle definition

I'm trying to ascertain the appropriate order of vertices for the face of a mesh that is programmatically created. Currently the face is always a quadrangle, but eventually a face can consist of any number of vertices ≥3. What I have are the Vector3 of the vertices, the Vector3 of the normal, and the Vector3 of both up and left. Because these faces can have any rotation, they are not guaranteed to be (and will rarely be) completely perpendicular to any of the three primary axes.

I've looked at using dot products and matrices to try to remap them to a 2D coordinate system, but I could not quite get it right, and that rotation could also be problematic for faces on the "top" and "bottom" of a mesh.

As it is, I'm trying to find a formula that would use the vertices, the normal, up, and left to (in the case of a quadrangle) start with the upper-leftmost vertex if facing it from the normal direction and work clockwise from there. I could use the ordered vertices to properly build triangles that would suit the normal and display properly.

I'm not bad with math, per se, but vector mathematics are outside of my comfort zone, which is in part why I'm going through this exercise.

TL;DR, I have a cube which is transformed and rotated randomly in 3D world space. I've captured each face into an object that contains the vertices, normal, up, and left direction (normal for the face, up and left as far as the GameObject itself is concerned) and want to order the vertices for triangle mapping for the mesh.

• Can you make any guarantees about the shape of the faces? eg. are they convex? – DMGregory May 28 '20 at 20:38
• Ah, good question. The individual faces will always be planar, e.g. will always consist of coplanar triangles. They will be Unity mesh faces, with no submeshes or deformation. – Jesse Williams May 28 '20 at 20:41
• So, are they convex? That part is actually kind of crucial. For a convex polygon, we can infer/invent an ordering of the vertices. If the polygon is non-convex, or possibly self-intersecting, we may need an order as an input to make sure we're producing the same polygon that was intended. The ordering can be clockwise, counterclockwise, or an unknown coin-toss whether it's one or the other (and we'll figure that out), but we can't work from an unordered collection of points if we lack a convexity guarantee (or a weaker guarantee like being star-shaped). – DMGregory May 28 '20 at 20:43
• Ah, I see what you're asking. For now the polygons will always be convex. I may tackle non-convex at some point, but not now for sure. In fact, the entire 3D mesh will currently always be convex and manifold. – Jesse Williams May 28 '20 at 20:48
• (Note that it's possible to form a convex manifold mesh out of non-convex polygons) – DMGregory May 28 '20 at 20:52

Normally this would be something you handle earlier in your generator function - generating vertices in a known winding by construction, rather than sorting them after the fact.

That said, you can make a function to put the vertices in a winding of your choice like so:

using System.Collections.Generic;
using UnityEngine;

public class ProcMesh : MonoBehaviour
{
struct Sortable<T> : System.IComparable<Sortable<T>> {

public Sortable(T value, float key) {
this.value = value;
this.key = key;
}

public int CompareTo(Sortable<T> other) {
return key.CompareTo(other.key);
}
}

// Cached temporary list we can re-use for each sort, rather than re-allocating.
List<Sortable<Vector3>> _toSort = new List<Sortable<Vector3>>();

void SortFaceVertices(List<Vector3> vertices, Vector3 normal) {
// Find the rough center point of the face.
Vector3 centroid = Vector3.zero;
foreach (var vertex in vertices)
centroid += vertex;
centroid *= 1f / vertices.Count;

// Form an orientation that points the z+ axis along the normal.
Quaternion orientation = Quaternion.LookRotation(normal);
// Its inverse maps the face into the XY plane.
Quaternion toXY = Quaternion.Inverse(orientation);

// Fill our sortable collection with entries for each vertex.
_toSort.Clear();
foreach (var vertex in vertices) {
// Map the vertex into the XYplane, with the face at the origin.
Vector2 inPlane = toXY * (vertex - centroid);

// Compute its angle counter-clockwise from the x+ axis.
float angle = Mathf.Atan2(inPlane.y, inPlane.x);

// To sort clockwise, multiply the angle by -1.
}

// Do the actual sorting!
_toSort.Sort();

// Fill the list we were provided with vertices in our sorted order.
for (int i = 0; i < vertices.Count; i++)
vertices[i] = _toSort[i].value;
}
}

• Thank you - I added the Sortable<T> struct on it's own and used SortFaceVertices() with my Face class as a param (which has properties for Vectors and Normal). It works great, except the back face of the test cube is ordered the same as the front face, so the mesh is visible from +x rather than -x. I'll play around a bit with different orientations and see if it's always +/-x local x or +/- world x. Maybe I'll add a field that contains the centroid of the entire mesh to ensure that the face is ordered to always face away. This is a huge help - seriously, thank you! – Jesse Williams May 29 '20 at 2:37
• It sounds like you've passed the wrong normal for your back face. The winding is chosen based on the normal. – DMGregory May 29 '20 at 2:38
• Ah yes, I see where that might be happening. Actually the normals, I think, are fine, but the GO the face is attached to appears to be facing incorrectly. Oops! – Jesse Williams May 29 '20 at 12:23
• There's a slightly easier way to do this: gamedev.stackexchange.com/questions/26974/… Basically, leave the vertices alone and manipulate the index buffer. – 3Dave May 29 '20 at 18:11
• Good point @3Dave. I assumed OP might also need the sorting in order to do the triangulation, but if they already have the faces triangulated then it's absolutely faster to just check the winding of each triangle vs the normal and flip two indices if dot(cross(v[i3] - v[i1], v[i2] - v[i1]), n) < 0 – DMGregory May 29 '20 at 18:37