Ordering vertices of a face for correct triangle definition

Question

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.

Answer 1

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>> {
        readonly public T value;
        readonly public float key;

        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.
            _toSort.Add(new Sortable<Vector3>(vertex, angle));
        }

        // 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;
    }
}