koobas.hobune.stream
Triangulating a 2D polygon with only hull vertices.
I'm building a random road network where each node is an intersection that connects to some roads. Each road is a straight line between two intersections. Each road builds its mesh by creating 4 vertices then extruding them in the y direction using Unity's Procedural Examples project (MeshExtrusion.cs).
I want to generate my intersections in a similar manner. For each road that's built, it gives 2 of those vertices to each connecting intersection for it to store in an internal vertex list. That builds my vertex list for the intersection. All that's left is to triangulate and extrude it. However, none of my triangulation methods have worked. I've tried using the oft recommended Triangulator.cs script, which doesn't produce correct triangles for even a simple case of 4 vertices placed at each corner.
So I figured this wasn't too big a deal, since my roads are all connecting to the outside of the intersection, I really just needed a convex hull triangulation algorithm, so I came up with one:
-Initialize a list T to hold triangle indices
-Pick a random vertex V (or use some heuristic, I'm using the vertex with the smallest x+y term)
-Sort the rest of the vertices based on the angle between Vector3.right and the line segment V->vertex, put this sorted list into a stack S, pushing the largest angled vertex first.
-Let P be the first popped vertex from S.
-While S is not empty:
append V to T,
append P to T,
append S.Peek() to T
pop the next vertex from S and set P to it.
Since my vertices are actually structs that hold the vertex position as well as the index, I can just iterate over T and collect the triangle indices to set for the triangle. The problem is, I'm getting weird results. Here are the top and bottom views of using this algorithm with one vertex on each corner and an extra one at (0.2, 0, 1.1)
I can't seem to get the triangulation correct for an arbitrary polygon.
Here is what I came up with:
[RequireComponent(typeof(MeshFilter))]
public class PolygonTriangulator : MonoBehaviour {
private void Start()
{
Vector3[] verts = new Vector3[] {
new Vector3(0.2f, 0, 1.1f),
new Vector3(-1, 0, -1),
new Vector3(-1, 0, 1),
new Vector3(1, 0, -1),
new Vector3(1, 0, 1),
};
Build(verts);
}
public void Build(Vector3[] vertices) {
Vector2[] vs = vertices.Select(v=>new Vector2(v.x, v.z)).ToArray();
vs.SortBy(v=>Vector2.right.AngleTo(v));
Mesh m = new Mesh();
m.Clear();
m.vertices = vertices;
m.triangles = SimpleTriangulator.Triangulate(vs);
//m.triangles = new Triangulator(vs).Triangulate();
m.RecalculateNormals();
m.RecalculateBounds();
GetComponent<MeshFilter>().mesh = m;
}
public static float AngleTo(this Vector2 this_, Vector2 to) {
Vector2 direction = to - this_;
float angle = Mathf.Atan2(direction.y, direction.x) * Mathf.Rad2Deg;
if (angle < 0f) angle += 360f;
return angle;
}
}
And here's the triangulation code:
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
public struct VertexWithIndex {
public Vector2 vertex;
public int index;
public VertexWithIndex(Vector2 vertex, int index) {
this.vertex = vertex;
this.index = index;
}
public bool Is(VertexWithIndex other) {
if (other.vertex == this.vertex && other.index == this.index) {
return true;
}
return false;
}
}
public static class SimpleTriangulator {
public static int[] Triangulate(Vector2[] inputVerts)
{
if (inputVerts.Length < 3) {
if (inputVerts.Length == 2) {
return new int[] { 0, 1, };
}
return null;
}
List<VertexWithIndex> vertices = new List<VertexWithIndex>();
for (int i = 0; i < inputVerts.Length; i++)
{
vertices.Add(new VertexWithIndex(inputVerts[i], i));
}
List<int> tris = new List<int>();
// Get the vertex closest to the 4th quadrant
VertexWithIndex randomSelected = vertices.OrderBy(a=>a.vertex.x + a.vertex.y).First();
List<VertexWithIndex> restOfVertices = vertices.Where(v=>!v.Is(randomSelected)).ToList();
Stack<VertexWithIndex> V = new Stack<VertexWithIndex>(restOfVertices);
VertexWithIndex secondVertexInTriangle = V.Pop();
while (V.Count > 0) {
int[] newTriangle = EnsureCorrectOrdering(randomSelected, secondVertexInTriangle, V.Peek());
/*new int[3];
newTriangle[0] = randomSelected.index;
newTriangle[1] = secondVertexInTriangle.index;
newTriangle[2] = V.Peek().index;*/
tris.AddRange(newTriangle);
secondVertexInTriangle = V.Pop();
}
return tris.ToArray();
}
// Given three vertices, return their indices in clockwise order
static int[] EnsureCorrectOrdering(VertexWithIndex[] triangle) {
return EnsureCorrectOrdering(triangle[0], triangle[1], triangle[2]);
}
static int[] EnsureCorrectOrdering(VertexWithIndex a, VertexWithIndex b, VertexWithIndex c) {
int[] indices = new int[3];
Vector3 AC = c.vertex - a.vertex;
AC = new Vector3(AC.x, AC.z, AC.y);
Vector3 AB = b.vertex - a.vertex;
AB = new Vector3(AB.x, AB.z, AB.y);
if (Vector3.Cross(AC, AB).sqrMagnitude > 0) {
indices[0] = a.index;
indices[1] = b.index;
indices[2] = c.index;
} else {
indices[0] = a.index;
indices[1] = c.index;
indices[2] = b.index;
}
return indices;
}
}
I know I'm missing something here, since the Triangulation.cs script didn't work I think there's something wrong with my logic, code, or both. But I've been unable to fix this.
What is "SortBy" ? It's not a known linq extension nor a default method of a native array. Are you sure that that method does sort your array correctly? Also "AngleTo" doesn't take a reference vector but a relative position. So it would make more sense to use Vector2.zero than "right".
Try this ins$$anonymous$$d:
Vector2[] vs = vertices.Select( v=>new Vector2(v.x, v.z) ).OrderBy( v=>Vector2.zero.AngleTo(v) ).ToArray();
The SortBy was a mistyped edit, oops! So following your advice, and to make it more robust, I tried sorting inside the triangulation method right before needing it sorted, using:
VertexWithIndex randomSelected = vertices.OrderBy(a=>a.vertex.x + a.vertex.y).First();
List<VertexWithIndex> restOfVertices = vertices.Where(v=>!v.Is(randomSelected)).ToList();
Stack<VertexWithIndex> V = new Stack<VertexWithIndex>(restOfVertices);
V.OrderBy(x=>Vector2.zero.AngleTo(x.vertex));
But it produced the exact same results.
So I've fixed the issues, it had everything to do with using the OrderBy method in the wrong place, which is what I seem to have missed from @Bunny83's comment. Here is my finished script, you can use it to build a 2d mesh from the hull (outside) vertices of a convex polygon.
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
public struct VertexWithIndex {
public Vector2 vertex;
public int index;
public VertexWithIndex(Vector2 vertex, int index) {
this.vertex = vertex;
this.index = index;
}
public bool Is(VertexWithIndex other) {
if (other.vertex == this.vertex && other.index == this.index) {
return true;
}
return false;
}
}
public static class HullMesher {
/// <summary>
/// Builds a 2d polygon in the xz plane.
/// </summary>
/// <param name="vertices"></param>
/// <returns></returns>
public static Mesh BuildPolygon(Vector3[] vertices) {
Vector2[] vs = vertices.Select(v=>new Vector2(v.x, v.z)).ToArray();
Mesh m = new Mesh();
m.Clear();
m.vertices = vertices;
m.triangles = TriangulateHull(vs);
m.RecalculateNormals();
m.RecalculateBounds(); //calculate the bounds before calculating UV's
Vector2[] uvs = new Vector2[vertices.Length];
float rightX = (vertices.Max(a=>a.x) - vertices.Min(a=>a.x)) / (vertices.Max(a=>a.y) - vertices.Min(a=>a.y));
float l_width = m.bounds.size.x;
float l_height = m.bounds.size.z;
for(int i = 0; i < uvs.Length; i++) {
float distFromMinX = vertices[i].x - m.bounds.min.x;
float distFromMinY = vertices[i].y - m.bounds.min.y;
uvs[i] = new Vector2(distFromMinX / l_width, distFromMinY / l_height);
}
m.uv = uvs;
/*if (texture != null) { // How to set textures
Material mat = GetComponent<MeshRenderer>().material;
mat.mainTexture = texture;
mat.mainTextureScale = new UnityEngine.Vector2(1f/ rightX, 1);
}*/
return m;
}
public static int[] TriangulateHull(Vector2[] inputVerts)
{
if (inputVerts.Length < 3) {
if (inputVerts.Length == 2) {
return new int[] { 0, 1, };
}
return null;
}
List<VertexWithIndex> vertices = new List<VertexWithIndex>();
for (int i = 0; i < inputVerts.Length; i++)
{
vertices.Add(new VertexWithIndex(inputVerts[i], i));
}
List<int> tris = new List<int>();
VertexWithIndex randomSelected = vertices.OrderBy(a=>a.vertex.y+a.vertex.x).First(); // Heuristic to pick the lowest x+y value results in all angles being in [0, 90]
List<VertexWithIndex> restOfVertices = vertices.Where(v=>!v.Is(randomSelected)).ToList();
Stack<VertexWithIndex> V = new Stack<VertexWithIndex>(restOfVertices.OrderBy(x=>x.vertex.PositiveAngleTo(randomSelected.vertex))); //The issue is here, it isn't ordering them correctly use the debugger for this method
VertexWithIndex secondVertexInTriangle = V.Pop();
//So what this algorithm does is triangulates by connecting a vertex with all other vertices.
//Then
//It only works for convex hulls.
while (V.Count > 0) {
int[] newTriangle = new int[3]; //EnsureCorrectOrdering(randomSelected, secondVertexInTriangle, V.Peek());
tris.Add(randomSelected.index);
tris.Add(secondVertexInTriangle.index);
tris.Add(V.Peek().index);
secondVertexInTriangle = V.Pop();
}
return tris.ToArray();
}
// Given three vertices, return their indices in clockwise order
static int[] EnsureCorrectOrdering(VertexWithIndex[] triangle) {
return EnsureCorrectOrdering(triangle[0], triangle[1], triangle[2]);
}
static int[] EnsureCorrectOrdering(VertexWithIndex a, VertexWithIndex b, VertexWithIndex c) {
int[] indices = new int[3];
Vector3 AC = c.vertex - a.vertex;
AC = new Vector3(AC.x, AC.z, AC.y);
Vector3 AB = b.vertex - a.vertex;
AB = new Vector3(AB.x, AB.z, AB.y);
if (Vector3.Cross(AC, AB).sqrMagnitude > 0) {
indices[0] = a.index;
indices[1] = b.index;
indices[2] = c.index;
} else {
indices[0] = a.index;
indices[1] = c.index;
indices[2] = b.index;
}
return indices;
}
public static float PositiveAngleTo(this Vector2 this_, Vector2 to) {
Vector2 direction = to - this_;
float angle = Mathf.Atan2(direction.y, direction.x) * Mathf.Rad2Deg;
if (angle < 0f) angle += 360f;
return angle;
}
}
Here's an example script:
using System;
using UnityEngine;
[RequireComponent(typeof(MeshFilter))]
public class RandomPolygonMesher : MonoBehaviour {
Vector3[] vertices;
// Use this for initialization
void Start () {
Func<float> r = () => UnityEngine.Random.Range(-1f, 1f);
vertices = new Vector3[] {
new Vector3(r(), 0, r()),
new Vector3(r(), 0, r()),
new Vector3(r(), 0, r()),
new Vector3(r(), 0, r()),
new Vector3(r(), 0, r()),
};
GetComponent<MeshFilter>().mesh = HullMesher.BuildPolygon(vertices);
}
// Update is called once per frame
void Update () {
if (Input.GetKeyDown(KeyCode.Space)) Start();
}
}
As you click space you can see how sometimes it creates a non convex polygon, just ensure all of your vertices form a convex shape and it works fine.
To use this with the above mesh extruder you can create 3d convex shapes from 2d convex polygons. Just import the MeshExtrusion.cs script from the link in the original question. Then in start create the extrusion matrices:
void Start () {
Func<float> rdm = () => UnityEngine.Random.Range(-1f, 1f);
vertices = new Vector3[] {
new Vector3(rdm(), 0, rdm()),
new Vector3(rdm(), 0, rdm()),
new Vector3(rdm(), 0, rdm()),
new Vector3(rdm(), 0, rdm()),
new Vector3(rdm(), 0, rdm()),
};
Mesh m = HullMesher.BuildPolygon(vertices);
//Local translation
Vector3 t = Vector3.zero;
//Local rotation
Quaternion r = Quaternion.identity;
//Local scaling
Vector3 s = Vector3.one;
//Transform before extrusion
Matrix4x4 op0 = Matrix4x4.TRS(t, r, s);
//Transform after extrusion
Matrix4x4 op1 = Matrix4x4.TRS(transform.up * extrusionHeight, r, s);
//Extrusion operations
Matrix4x4[] ops = new Matrix4x4[] { op0, op1, };
//Perform all extrusion operations on the mesh, the bool is whether or not to flip the resulting triangle faces
MeshExtrusion.ExtrudeMesh(m, GetComponent<MeshFilter>().mesh, ops, true);
m.RecalculateNormals();
m.RecalculateBounds();
if (texture != null) {
GetComponent<MeshRenderer>().material.mainTexture = texture;
}
}
