Question about refinement

[ivan-trackman]

Hi,

I have a question regarding the refinement process, for some reason (and I think this is by design), the refinement process adds points to the constraint edge, but we want to preserve it as is. Is there any way to avoid doing that, and not split the constraint edges in refinement?

We apply catmullrom on the constraint edge later in compute shader and it will be not the same with new points.

P.S. thank you for this amazing project!

[andywiecko]

Hi @ivan-trackman,

Many thanks for reporting the issue!

---

Unfortunately, the current refinement algorithm, terminator, requires splitting the segment first before inserting points into triangles. This is essential to prevent adding points outside the mesh. To resolve your issue, I have thought of two solutions:

1. Run two passes of triangulation. First, schedule triangulation with mesh refinement, and in the second run, use the output positions from the first pass, filter out points that are inserted in constraints, and disable refinement. This solution may result in strange triangles for "very long" constraints, but overall the mesh should have similar triangle quality. Sketch:

using var positions = new NativeArray<float2>(..., Allocator.Persistent);
using var constraints = new NativeArray<int>(..., Allocator.Persistent);
using var holes = new NativeArray<float2>(..., Allocator.Persistent); // if required

using var triangulator = new Triangulator(Allocator.Persistent)
{
   Input = { Positions = positions, ConstraintEdges = constraints, HoleSeeds = holes },
   Settings = { RefineMesh = true, RefinementThresholds = { ... }, RestoreBoundary = true  
};


triangulator.Run();

using var filteredPositions = new NativeList<float2>(Allocator.Persistent);

// Filter out positions
filteredPositions.CopyFrom(positions);
for(int i = positions.Length; i < triangulator.Output.Positions.Length; i++)
{
   var p = triangulator.Output.Positions[i];
   if(i is not constraint)
   {
      filteredPositions.Add(p);
   }
}

triangulator.Settings.RefineMesh = false;
triangulator.Input.Positions = filteredPositions;

triangulator.Run();

Implementing the check "if(i is not constraint)" can be tricky but is doable. To make it easier, note that all points inserted during refinement have i >= positions.Length. The Triangulator internally has a buffer NativeList<bool> constrainedHalfedges which has a true element if a given halfedge is a constraint. This can be used to filter out which points should be removed.

2. Implement a different refinement algorithm and use Triangulator only for constraint triangulation.

---

In about two weeks, I will push development further. I'm going to merge some stuff, implement some enhancements, and probably release a new version. I could make this constrainedHalfedges public to make it easier and implement the full if(i is not constraint) part (output halfedges have already been opened here #131). I reported this issue on the project board: BurstTriangulator (view)

If you have any questions, let me know.

Best,
Andrzej Więckowski

[andywiecko]

PS
In the future, I plan to add a low-level API, NativeTriangulator, which will include many utilities to customize options for cases like this issue.

[ivan-trackman]

@andywiecko thanks a lot for this blazingly fast reply! We are currently trying the 2nd approach with ability to add some custom lists to store the information that will help us restore the original triangles (or so my teammate said)
We will post our findings here if you don't mind and maybe make a PR later

[andywiecko]

@ivan-trackman Interesting! I'm looking forward to hearing from you about your findings!
Contributions are always welcome 🙂

Best,
Andrzej

[andywiecko]

Hi @ivan-trackman,
I just wanted to inform you that I've recently released v3.1. You can find the full release notes here). It is already available on OpenUPM.

This release includes Output.ConstrainedHalfedges, which I mentioned in the thread, and supports native use cases that I believe may be beneficial for you.

Best,
Andrzej

[Artorias93]

Hi @andywiecko, I really appreciate your work on Triangulator!
I'm having some difficulties to understand how (and what) input to pass to be sure that AutoHolesAndBoundary feature work properly.
To be more specific, I need to pass in input a mesh (we can assume that it is flat/2D) without know nothing about it, just that it is a closed mesh.
We can't know if it is concave or convex, if it has holes or not (and where).
I just need to refine this mesh through your tool without know nothing about those things.

Do you think it is possible? Can you help me to solve my issue? I think it is a wrong input problem (I'm so sorry to share here a WallOfText fo Code).

public static Mesh ApplyDelaunay(Mesh mesh, float refinementAreaThreshold = 1f, float refinementAngleDegrees = 20f)
{
	// Extract vertices from the mesh
	Vector3[] inputVertices = mesh.vertices;
	int vertexCount = inputVertices.Length;

	Vector2[] inputUV = mesh.uv;
	Dictionary<double2, Vector2> uvMap = new Dictionary<double2, Vector2>();
	for (int i = 0; i < vertexCount; i++)
	{
		// Use X and Z coordinates as the key
		double2 posKey = new double2(inputVertices[i].x, inputVertices[i].z);
		if (!uvMap.ContainsKey(posKey))
			uvMap[posKey] = inputUV[i];
	}

	// Convert vertices to double2 using X and Z coordinates
	double2[] allPositions = new double2[vertexCount];
	for (int i = 0; i < vertexCount; i++)
	{
		allPositions[i] = new double2(inputVertices[i].x, inputVertices[i].z);
	}

	// Extract triangles from the mesh
	int[] triangles = mesh.triangles;
	int triangleCount = triangles.Length / 3;
	// Build a dictionary to count occurrences of each edge (order-independent)
	Dictionary<string, int> edgeCount = new Dictionary<string, int>();
	Dictionary<string, (int a, int b)> edgeMap = new Dictionary<string, (int, int)>();
	for (int i = 0; i < triangleCount; i++)
	{
		int a = triangles[3 * i];
		int b = triangles[3 * i + 1];
		int c = triangles[3 * i + 2];
		ProcessEdge(a, b, edgeCount, edgeMap);
		ProcessEdge(b, c, edgeCount, edgeMap);
		ProcessEdge(c, a, edgeCount, edgeMap);
	}

	// Boundary edges are those that appear only once
	List<int> unsortedBoundaryEdges = new List<int>();
	foreach (var kvp in edgeCount)
	{
		if (kvp.Value == 1)
		{
			var edge = edgeMap[kvp.Key];
			unsortedBoundaryEdges.Add(edge.a);
			unsortedBoundaryEdges.Add(edge.b);
		}
	}
	if (unsortedBoundaryEdges.Count == 0)
	{
		Debug.LogError("No boundary detected from triangles. Check the input.");
		return mesh;
	}

	// Reorder the boundary cycle using the BoundaryExtractor algorithm
	int[] unsortedEdgesArray = unsortedBoundaryEdges.ToArray();
	int[] orderedBoundaryCycle = BoundaryExtractor.ExtractBoundaryCycle(unsortedEdgesArray, allPositions);
	if (orderedBoundaryCycle == null)
	{
		Debug.LogError("Unable to reconstruct the contour from constraints.");
		return mesh;
	}

	// Build the flat array of constraints: each pair (i, i+1) defines a boundary edge
	int cycleCount = orderedBoundaryCycle.Length;
	int[] constraintEdgesArray = new int[(cycleCount - 1) * 2];
	for (int i = 0; i < cycleCount - 1; i++)
	{
		constraintEdgesArray[2 * i] = orderedBoundaryCycle[i];
		constraintEdgesArray[2 * i + 1] = orderedBoundaryCycle[i + 1];
	}

	// Prepare NativeArrays for BurstTriangulator
	NativeArray<double2> positionsNative = new NativeArray<double2>(allPositions, Allocator.Persistent);
	NativeArray<int> constraintsNative = new NativeArray<int>(constraintEdgesArray, Allocator.Persistent);

	// Perform triangulation with refinement and restore boundaries
	using (burstTri.Triangulator triangulator = new burstTri.Triangulator(Allocator.Persistent))
	{
		triangulator.Input.Positions = positionsNative;
		triangulator.Input.ConstraintEdges = constraintsNative;
		triangulator.Settings.RefineMesh = true;
		triangulator.Settings.RestoreBoundary = true;
		triangulator.Settings.AutoHolesAndBoundary = true;
		triangulator.Settings.ValidateInput = true;
		triangulator.Settings.RefinementThresholds.Area = refinementAreaThreshold;
		triangulator.Settings.RefinementThresholds.Angle = math.radians(refinementAngleDegrees);
		triangulator.Run();

		NativeArray<double2> refinedPositions = triangulator.Output.Positions.AsArray();
		NativeArray<int> refinedTriangles = triangulator.Output.Triangles.AsArray();

		// Convert results to Vector3 (using Y = 0, XZ plane)
		Vector3[] newVertices = new Vector3[refinedPositions.Length];
		for (int i = 0; i < refinedPositions.Length; i++)
		{
			newVertices[i] = new Vector3((float)refinedPositions[i].x, 0f, (float)refinedPositions[i].y);
		}
		int[] newTriangles = refinedTriangles.ToArray();

		mesh.vertices = newVertices;
		mesh.triangles = newTriangles;
		mesh.RecalculateNormals();
		mesh.RecalculateBounds();

		Vector2[] newUVs = new Vector2[newVertices.Length];
		float tolerance = 1e-4f; // Adjust tolerance as needed
		for (int i = 0; i < newVertices.Length; i++)
		{
			// Use X and Z coordinates to find the match
			double2 posKey = new double2(newVertices[i].x, newVertices[i].z);
			bool found = false;
			Vector2 bestUV = Vector2.zero;
			// Search in uvMap: if the new vertex is close enough to an original one, transfer the UV
			foreach (var kvp in uvMap)
			{
				if (math.distance(posKey, kvp.Key) < tolerance)
				{
					bestUV = kvp.Value;
					found = true;
					break;
				}
			}
			if (found)
			{
				newUVs[i] = bestUV;
			}
			else
			{
				// Fallback: use simple planar projection
				newUVs[i] = new Vector2(newVertices[i].x, newVertices[i].z);
			}
		}
		mesh.uv = newUVs;
	}

	positionsNative.Dispose();
	constraintsNative.Dispose();
	return mesh;
}

private static void ProcessEdge(int i, int j, Dictionary<string, int> edgeCount, Dictionary<string, (int a, int b)> edgeMap)
{
	int min = math.min(i, j);
	int max = math.max(i, j);
	string key = $"{min}_{max}";
	if (edgeCount.ContainsKey(key))
	{
		edgeCount[key]++;
	}
	else
	{
		edgeCount[key] = 1;
		edgeMap[key] = (min, max);
	}
}



public static class BoundaryExtractor
{
	public static int[] ExtractBoundaryCycle(int[] constraintEdges, double2[] vertices)
	{
		if (constraintEdges == null || constraintEdges.Length % 2 != 0)
		{
			Debug.LogError("The constraint vector is not valid.");
			return null;
		}

		// 1. Build the adjacency map
		Dictionary<int, List<int>> neighborMap = new Dictionary<int, List<int>>();
		int edgeCount = constraintEdges.Length / 2;
		for (int i = 0; i < edgeCount; i++)
		{
			int a = constraintEdges[2 * i];
			int b = constraintEdges[2 * i + 1];

			if (!neighborMap.ContainsKey(a))
				neighborMap[a] = new List<int>();
			if (!neighborMap.ContainsKey(b))
				neighborMap[b] = new List<int>();

			if (!neighborMap[a].Contains(b))
				neighborMap[a].Add(b);
			if (!neighborMap[b].Contains(a))
				neighborMap[b].Add(a);
		}

		// 2. For each vertex, sort neighbors clockwise
		foreach (var kvp in neighborMap)
		{
			int i = kvp.Key;
			kvp.Value.Sort((j, k) =>
			{
				double2 d1 = vertices[j] - vertices[i];
				double2 d2 = vertices[k] - vertices[i];
				double a1 = math.atan2(d1.y, d1.x);
				double a2 = math.atan2(d2.y, d2.x);
				a1 = (a1 < 0) ? a1 + 2 * math.PI : a1;
				a2 = (a2 < 0) ? a2 + 2 * math.PI : a2;
				double cw1 = 2 * math.PI - a1;
				double cw2 = 2 * math.PI - a2;
				return cw1.CompareTo(cw2);
			});
		}

		// 3. Choose the starting vertex: the one with the smallest x (if tied, smallest y)
		int start = 0;
		for (int i = 1; i < vertices.Length; i++)
		{
			if (vertices[i].x < vertices[start].x ||
			   (vertices[i].x == vertices[start].x && vertices[i].y < vertices[start].y))
				start = i;
		}

		// Select the initial edge: from start, choose the first neighbor (clockwise order)
		if (!neighborMap.ContainsKey(start) || neighborMap[start].Count == 0)
		{
			Debug.LogError("The starting vertex has no neighbors.");
			return null;
		}
		int initialNeighbor = neighborMap[start][0];

		// 4. Trace the boundary cycle
		List<int> cycle = new List<int>();
		cycle.Add(start);
		int previous = start;
		int current = initialNeighbor;
		cycle.Add(current);

		while (current != start)
		{
			List<int> currentNeighbors = neighborMap[current];
			int idx = currentNeighbors.IndexOf(previous);
			if (idx == -1)
			{
				Debug.LogError($"Error: vertex {current} does not have vertex {previous} among its neighbors.");
				return null;
			}
			int next = currentNeighbors[(idx + 1) % currentNeighbors.Count];

			if (cycle.Contains(next) && next != start)
			{
				Debug.LogError("Cycle interrupted: anomalous repetition of vertices detected.");
				return null;
			}
			cycle.Add(next);
			previous = current;
			current = next;
		}

		if (cycle[cycle.Count - 1] != start)
			cycle.Add(start);

		return cycle.ToArray();
	}
}

It doesn't work with this meshes:

1)
Triangles: 12, 2, 9, 7, 9, 2, 3, 1, 11, 10, 11, 1, 8, 11, 10, 9, 8, 10, 5, 8, 9, 6, 8, 5, 7, 6, 5, 4, 0, 3, 1, 3, 0, 2, 1, 0

Vertices: (112.32, 0.00, 748.93), (-184.74, 0.00, -940.07), (120.20, 0.00, 747.50), (-190.61, 0.00, -972.54), (-198.48, 0.00, -971.12), (102.25, 0.00, 468.24), (159.56, 0.00, 740.39), (151.69, 0.00, 741.81), (-151.24, 0.00, -979.66), (102.25, 0.00, 468.24), (-153.25, 0.00, -945.76), (-159.12, 0.00, -978.23), (70.76, 0.00, 473.93)

2)
Triangles: 3, 0, 1, 1, 2, 3, 4, 7, 6, 6, 5, 4, 8, 11, 10, 10, 9, 8, 12, 15, 14, 14, 13, 12, 16, 23, 22, 21, 20, 19, 17, 16, 22, 21, 19, 18, 18, 17, 22, 22, 21, 18, 24, 31, 30, 30, 29, 28, 27, 26, 25, 24, 30, 28, 27, 25, 24, 24, 28, 27, 39, 38, 37, 35, 34, 33, 39, 37, 36, 35, 33, 32, 32, 39, 36, 36, 35, 32, 40, 47, 46, 45, 44, 43, 41, 40, 46, 45, 43, 42, 42, 41, 46, 46, 45, 42, 48, 51, 50, 50, 49, 48, 52, 55, 54, 54, 53, 52, 56, 59, 58, 58, 57, 56, 60, 63, 62, 62, 61, 60, 71, 70, 69, 67, 66, 65, 65, 64, 71, 71, 69, 68, 67, 65, 71, 71, 68, 67, 72, 79, 78, 78, 77, 76, 76, 75, 74, 73, 72, 78, 78, 76, 74, 74, 73, 78, 80, 87, 86, 85, 84, 83, 81, 80, 86, 85, 83, 82, 82, 81, 86, 86, 85, 82, 95, 94, 93, 91, 90, 89, 95, 93, 92, 91, 89, 88, 88, 95, 92, 92, 91, 88

Vertices: (-131.40, 0.00, -644.85), (-122.33, 0.00, -594.66), (-110.52, 0.00, -596.80), (-119.59, 0.00, -646.98), (-99.91, 0.00, -650.54), (-90.84, 0.00, -600.35), (-102.65, 0.00, -598.22), (-111.71, 0.00, -648.41), (-154.41, 0.00, -862.22), (-161.79, 0.00, -860.89), (-165.17, 0.00, -879.58), (-157.79, 0.00, -880.92), (-147.03, 0.00, -863.55), (-154.41, 0.00, -862.22), (-157.79, 0.00, -880.92), (-150.41, 0.00, -882.25), (-157.79, 0.00, -880.92), (-165.17, 0.00, -879.58), (-161.79, 0.00, -860.89), (-154.41, 0.00, -862.22), (-148.19, 0.00, -827.78), (-163.94, 0.00, -824.93), (-184.74, 0.00, -940.07), (-168.99, 0.00, -942.91), (-132.45, 0.00, -830.62), (-148.19, 0.00, -827.78), (-154.41, 0.00, -862.22), (-147.03, 0.00, -863.55), (-150.41, 0.00, -882.25), (-157.79, 0.00, -880.92), (-168.99, 0.00, -942.91), (-153.25, 0.00, -945.76), (-41.24, 0.00, -235.91), (-56.99, 0.00, -233.07), (-122.33, 0.00, -594.66), (-110.52, 0.00, -596.80), (-119.59, 0.00, -646.98), (-131.40, 0.00, -644.85), (-163.94, 0.00, -824.93), (-148.19, 0.00, -827.78), (-99.91, 0.00, -650.54), (-111.71, 0.00, -648.41), (-102.65, 0.00, -598.22), (-90.84, 0.00, -600.35), (-25.50, 0.00, -238.76), (-41.24, 0.00, -235.91), (-148.19, 0.00, -827.78), (-132.45, 0.00, -830.62), (48.91, 0.00, 173.03), (37.10, 0.00, 175.16), (28.03, 0.00, 124.97), (39.84, 0.00, 122.84), (29.23, 0.00, 176.58), (17.42, 0.00, 178.72), (8.35, 0.00, 128.53), (20.16, 0.00, 126.39), (82.69, 0.00, 407.76), (75.31, 0.00, 409.09), (71.93, 0.00, 390.40), (79.31, 0.00, 389.06), (75.31, 0.00, 409.09), (67.93, 0.00, 410.43), (64.55, 0.00, 391.73), (71.93, 0.00, 390.40), (102.25, 0.00, 468.24), (86.51, 0.00, 471.09), (75.31, 0.00, 409.09), (82.69, 0.00, 407.76), (79.31, 0.00, 389.06), (71.93, 0.00, 390.40), (65.70, 0.00, 355.95), (81.45, 0.00, 353.11), (71.93, 0.00, 390.40), (64.55, 0.00, 391.73), (67.93, 0.00, 410.43), (75.31, 0.00, 409.09), (86.51, 0.00, 471.09), (70.76, 0.00, 473.93), (49.96, 0.00, 358.80), (65.70, 0.00, 355.95), (39.84, 0.00, 122.84), (28.03, 0.00, 124.97), (37.10, 0.00, 175.16), (48.91, 0.00, 173.03), (81.45, 0.00, 353.11), (65.70, 0.00, 355.95), (-41.24, 0.00, -235.91), (-25.50, 0.00, -238.76), (65.70, 0.00, 355.95), (49.96, 0.00, 358.80), (17.42, 0.00, 178.72), (29.23, 0.00, 176.58), (20.16, 0.00, 126.39), (8.35, 0.00, 128.53), (-56.99, 0.00, -233.07), (-41.24, 0.00, -235.91)

Again, so sorry to share this amount of text with you, but I'm going crazy... Really appreciate your help...

[andywiecko]

Hi @Artorias93,
I'm working on the demo for your problem, and it's almost done. However, I encountered some difficulties.

The examples you provided contain degenerate meshes—that is, they include duplicate vertices. Was this intentional, or did you lose precision while copying and pasting the data?

For example, in case 1, vertices [5] and [9] are identical: (102.25, 0.00, 468.24) and (102.25, 0.00, 468.24), respectively.

I attempted to work around this by triangulating and constraining the mesh, but it seems like there is a precision issue. Below, you can see a screenshot of the input mesh (case 1), where some triangles appear to intersect with each other.

I have also utility in test namespace for that and this give me the following info for case 1) (triangle with id 6 is degenerated)

---
Triangulation is invalid!
  - Some triangles are intersecting: [(0, 6),(0, 7),(0, 8),(0, 11),(1, 6),(1, 7),(1, 8),(5, 6),(5, 7),(5, 8),(6, 7),(6, 8)].
---

Let me know what you think, and in a case of precision issue please upload data for case 1 with higher precision.

Best,
Andrzej

[Artorias93]

Hi @andywiecko!
Thank you for your interest :)

I'm just ask for mesh.vertices in Unity and it gave me:
Vertices: (112.32, 0.00, 748.93), (-184.74, 0.00, -940.07), (120.20, 0.00, 747.50), (-190.61, 0.00, -972.54), (-198.48, 0.00, -971.12), (102.25, 0.00, 468.24), (159.56, 0.00, 740.39), (151.69, 0.00, 741.81), (-151.24, 0.00, -979.66), (102.25, 0.00, 468.24), (-153.25, 0.00, -945.76), (-159.12, 0.00, -978.23), (70.76, 0.00, 473.93)

But I can't see that intersection with my eyes o.O
I don't know if this could be helpful, but the inner part is a hole.

[andywiecko]

How do you collect the data, are you using UnityEngine.Debug.Log(x);?

[Artorias93]

How do you collect the data, are you using UnityEngine.Debug.Log(x);?

Yes, Debug.Log("Vertices: " + string.Join(", ", mesh.vertices));
Unfortunatly, this and other meshes are auto-generated, so sometimes they can be not-perfect... In my Unity, I can see this... So it seems imperfect, but with no intersections (but maybe it is a graphic approximation)

[andywiecko]

Okay, so this may be the issue. Note, that Unity.Debug.Log will cause lose of precision and this is very significant cutoff:

Consider this code:

var x = new Vector3(math.PI, 0, 0);
UnityEngine.Debug.Log(x);
UnityEngine.Debug.Log($"{x.x} {x.y} {x.z}");

This will output in the console:

Try this instead, this should do the trick:

UnityEngine.Debug.Log(string.Join(",", a.Select(i => $"({i.x}, {i.y}, {i.z})")));

[Artorias93]

Thank you for the tip, here the new result:
Vertices: (112.323, 0, 748.927),(-184.739, 0, -940.068),(120.195, 0, 747.504),(-190.607, 0, -972.542),(-198.479, 0, -971.12),(102.253, 0, 468.244),(159.558, 0, 740.391),(151.685, 0, 741.814),(-151.244, 0, -979.655),(102.2526, 0, 468.2441),(-153.249, 0, -945.758),(-159.117, 0, -978.232),(70.763, 0, 473.934)

[andywiecko]

Great, thanks! As you can see [5] and [9] are different now. I will share with you the demo shortly, but probably tomorrow.

Best,
Andrzej

[Artorias93]

Thank you so much :)
I can't wait for the Dummy Method, it will be a total boost in terms of input preparation 💃
(I'm not a great expert in meshes, so It is easy than I've done bad and crazy things preparing the input for Triangulator) :(