BurstTriangulator
BurstTriangulator copied to clipboard
Published
20 hours ago •
andywiecko
andywiecko
Triangulation freezes when submitting a particular polygon
Hi,
The following polygon geometry + code causes a freeze:
float2 points[] = {
new float2(14225.59f, -2335.27f), new float2(13380.24f, -2344.72f), new float2(13197.35f, -2119.65f),
new float2(11750.51f, -2122.18f), new float2(11670.1f, -2186.25f), new float2(11424.88f, -2178.53f),
new float2(11193.54f, -2025.36f), new float2(11159.36f, -1812.22f), new float2(10956.29f, -1731.62f),
new float2(10949.03f, -1524.29f), new float2(10727.71f, -1379.53f), new float2(10532.48f, -1145.83f),
new float2(10525.18f, -906.69f), new float2(10410.57f, -750.73f), new float2(10629.48f, -657.33f),
new float2(10622f, -625.7f), new float2(10467.05f, -552.15f), new float2(10415.75f, -423.21f),
new float2(10037.01f, -427.11f), new float2(9997.4f, -487.33f), new float2(9788.02f, -539.44f),
new float2(9130.03f, -533.95f), new float2(8905.69f, -490.95f), new float2(8842.1f, -396.11f),
new float2(8410.81f, -407.12f), new float2(8211.88f, -583.32f), new float2(7985.37f, -588.47f),
new float2(7880.46f, -574.94f), new float2(7200.87f, -574.14f), new float2(6664.29f, -637.89f),
new float2(6351.84f, -483.61f), new float2(6324.37f, -143.48f), new float2(6093.94f, -152.8f),
new float2(5743.03f, 213.65f), new float2(5725.63f, 624.21f), new float2(5562.64f, 815.17f),
new float2(5564.65f, 1145.66f), new float2(4846.4f, 1325.89f), new float2(4362.98f, 1327.97f),
new float2(5265.89f, 267.31f), new float2(5266.32f, -791.39f), new float2(3806f, -817.38f),
new float2(3385.84f, -501.25f), new float2(3374.35f, -372.48f), new float2(3555.98f, -321.11f),
new float2(3549.9f, -272.35f), new float2(3356.27f, -221.45f), new float2(3352.42f, 13.16f),
new float2(1371.39f, 5.41f), new float2(1362.47f, -191.23f), new float2(1188.9f, -235.72f),
new float2(1180.86f, -709.59f), new float2(132.26f, -720.07f), new float2(1.94f, -788.66f),
new float2(-1240.12f, -779.03f), new float2(-1352.26f, -973.64f), new float2(-1665.17f, -973.84f),
new float2(-1811.91f, -932.75f), new float2(-1919.98f, -772.61f), new float2(-2623.09f, -782.31f),
new float2(-3030.54f, -634.38f), new float2(-3045.53f, -52.71f), new float2(-3969.83f, -61.28f),
new float2(-6676.96f, 102.16f), new float2(-7209.27f, 100.12f), new float2(-7729.39f, 178.02f),
new float2(-8228.73f, 126.39f), new float2(-8409.52f, 164.47f), new float2(-9432.81f, 168.43f),
new float2(-9586.02f, 116.14f), new float2(-10758.65f, 110.23f), new float2(-10894.94f, 63.53f),
new float2(-11737.45f, 60.54f), new float2(-11935.7f, 1.79f), new float2(-12437.14f, -4.33f),
new float2(-12832.19f, 41.15f), new float2(-13271.23f, 30.64f), new float2(-13478.52f, 65.91f),
new float2(-13729f, 65.71f), new float2(-13846.23f, 21.68f), new float2(-14000.3f, 62.86f),
new float2(-15224.52f, 58.78f), new float2(-15232.59f, -142.28f), new float2(-4326.12f, -232.09f),
new float2(-4083.7f, -441.37f), new float2(-3467.35f, -478.48f), new float2(-3040.92f, -1160.16f),
new float2(7192.14f, -1332.7f), new float2(7249.66f, -939.11f), new float2(8399.41f, -932.84f),
new float2(8816.72f, -830.49f), new float2(9861.58f, -835.71f), new float2(10065.59f, -1110.57f),
new float2(10052.32f, -2118.14f), new float2(9006.64f, -2125.78f), new float2(8818.37f, -2203.58f),
new float2(8846.09f, -2620.2f), new float2(14244.65f, -2650.96f)
};
int[] constraintIndices[] = {
97, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18,
18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30, 30, 31, 31, 32, 32, 33,
33, 34, 34, 35, 35, 36, 36, 37, 37, 38, 38, 39, 39, 40, 40, 41, 41, 42, 42, 43, 43, 44, 44, 45, 45, 46, 46, 47, 47, 48,
48, 49, 49, 50, 50, 51, 51, 52, 52, 53, 53, 54, 54, 55, 55, 56, 56, 57, 57, 58, 58, 59, 59, 60, 60, 61, 61, 62, 62, 63,
63, 64, 64, 65, 65, 66, 66, 67, 67, 68, 68, 69, 69, 70, 70, 71, 71, 72, 72, 73, 73, 74, 74, 75, 75, 76, 76, 77, 77, 78,
78, 79, 79, 80, 80, 81, 81, 82, 82, 83, 83, 84, 84, 85, 85, 86, 86, 87, 87, 88, 88, 89, 89, 90, 90, 91, 91, 92, 92, 93,
93, 94, 94, 95, 95, 96, 96, 97
};
using var triangulator = new Triangulator(capacity: 1024, Allocator.Persistent);
using var inputPositions = new NativeArray<float2>(points, Allocator.Persistent);
using var constraintEdges = new NativeArray<int>(constraintIndices, Allocator.Persistent);
triangulator.Settings.RefineMesh = false;
triangulator.Settings.ConstrainEdges = true;
triangulator.Settings.RestoreBoundary = true;
triangulator.Input.Positions = inputPositions;
triangulator.Input.ConstraintEdges = constraintEdges;
triangulator.Run();
(Tested using Unity 2021.3.6f1)
Do you have an explanation (and hopefully a fix)?
Best regards,
Martin
Hi @mduvergey, thanks for the feedback. Your data scale seems large at first glance.
Have you tried Settings.UseLocalTransformation = true option?
Tomorrow I will find some time to investigate this. I will let you know in the next message.
Best, Andrzej
Hi Andrzej,
Yes, tried that but without success. Thank you for investigating.
Best regards, Martin
Hi @mduvergey, I've investigated your issue today. I really appreciate your contribution to the project with that reported issue.
Your test specimen is quite specific and my guess is that float precision is not enough to resolve the constraint triangulation properly.
Additionally, constraint edge length is quite non-uniform.
There are very long constraints that produce triangles with very acute triangles.
"Triangulations" do not like such objects, and the Sloan algorithm gets stuck at some point.
Please note that your data aspect ratio is large. Width is more or less 10 times larger than height.
Your input data (white) and the result triangulation (blue) with ConstrainEdges and RestoreBoundary options disabled:
There are a few solutions to the problem:
- In your case probably the simplest solution is to rescale the data points in
xandyseparately, however, this is not a universal solution, since your data could be rotated for example by 33 degrees. - Add an additional option to the triangulator to rescale the points using some minimal OBB (generalized option 1.)
- Refine input constraints by splitting too-large edges.
I implemented a prototype solution for 3 and it seems to work.
In the following image you can see the result for refined input (note additional points) with ConstrainEdges and RestoreBoundary options enabled:
Below you can find (very dirty) prototype code:
private void OnDrawGizmos()
{
float2[] points = {
new float2(14225.59f, -2335.27f), new float2(13380.24f, -2344.72f), new float2(13197.35f, -2119.65f),
new float2(11750.51f, -2122.18f), new float2(11670.1f, -2186.25f), new float2(11424.88f, -2178.53f),
new float2(11193.54f, -2025.36f), new float2(11159.36f, -1812.22f), new float2(10956.29f, -1731.62f),
new float2(10949.03f, -1524.29f), new float2(10727.71f, -1379.53f), new float2(10532.48f, -1145.83f),
new float2(10525.18f, -906.69f), new float2(10410.57f, -750.73f), new float2(10629.48f, -657.33f),
new float2(10622f, -625.7f), new float2(10467.05f, -552.15f), new float2(10415.75f, -423.21f),
new float2(10037.01f, -427.11f), new float2(9997.4f, -487.33f), new float2(9788.02f, -539.44f),
new float2(9130.03f, -533.95f), new float2(8905.69f, -490.95f), new float2(8842.1f, -396.11f),
new float2(8410.81f, -407.12f), new float2(8211.88f, -583.32f), new float2(7985.37f, -588.47f),
new float2(7880.46f, -574.94f), new float2(7200.87f, -574.14f), new float2(6664.29f, -637.89f),
new float2(6351.84f, -483.61f), new float2(6324.37f, -143.48f), new float2(6093.94f, -152.8f),
new float2(5743.03f, 213.65f), new float2(5725.63f, 624.21f), new float2(5562.64f, 815.17f),
new float2(5564.65f, 1145.66f), new float2(4846.4f, 1325.89f), new float2(4362.98f, 1327.97f),
new float2(5265.89f, 267.31f), new float2(5266.32f, -791.39f), new float2(3806f, -817.38f),
new float2(3385.84f, -501.25f), new float2(3374.35f, -372.48f), new float2(3555.98f, -321.11f),
new float2(3549.9f, -272.35f), new float2(3356.27f, -221.45f), new float2(3352.42f, 13.16f),
new float2(1371.39f, 5.41f), new float2(1362.47f, -191.23f), new float2(1188.9f, -235.72f),
new float2(1180.86f, -709.59f), new float2(132.26f, -720.07f), new float2(1.94f, -788.66f),
new float2(-1240.12f, -779.03f), new float2(-1352.26f, -973.64f), new float2(-1665.17f, -973.84f),
new float2(-1811.91f, -932.75f), new float2(-1919.98f, -772.61f), new float2(-2623.09f, -782.31f),
new float2(-3030.54f, -634.38f), new float2(-3045.53f, -52.71f), new float2(-3969.83f, -61.28f),
new float2(-6676.96f, 102.16f), new float2(-7209.27f, 100.12f), new float2(-7729.39f, 178.02f),
new float2(-8228.73f, 126.39f), new float2(-8409.52f, 164.47f), new float2(-9432.81f, 168.43f),
new float2(-9586.02f, 116.14f), new float2(-10758.65f, 110.23f), new float2(-10894.94f, 63.53f),
new float2(-11737.45f, 60.54f), new float2(-11935.7f, 1.79f), new float2(-12437.14f, -4.33f),
new float2(-12832.19f, 41.15f), new float2(-13271.23f, 30.64f), new float2(-13478.52f, 65.91f),
new float2(-13729f, 65.71f), new float2(-13846.23f, 21.68f), new float2(-14000.3f, 62.86f),
new float2(-15224.52f, 58.78f), new float2(-15232.59f, -142.28f), new float2(-4326.12f, -232.09f),
new float2(-4083.7f, -441.37f), new float2(-3467.35f, -478.48f), new float2(-3040.92f, -1160.16f),
new float2(7192.14f, -1332.7f), new float2(7249.66f, -939.11f), new float2(8399.41f, -932.84f),
new float2(8816.72f, -830.49f), new float2(9861.58f, -835.71f), new float2(10065.59f, -1110.57f),
new float2(10052.32f, -2118.14f), new float2(9006.64f, -2125.78f), new float2(8818.37f, -2203.58f),
new float2(8846.09f, -2620.2f), new float2(14244.65f, -2650.96f)
};
points = points.Select(p => p / 1000).ToArray();
int[] constraintIndices = {
97, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18,
18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30, 30, 31, 31, 32, 32, 33,
33, 34, 34, 35, 35, 36, 36, 37, 37, 38, 38, 39, 39, 40, 40, 41, 41, 42, 42, 43, 43, 44, 44, 45, 45, 46, 46, 47, 47, 48,
48, 49, 49, 50, 50, 51, 51, 52, 52, 53, 53, 54, 54, 55, 55, 56, 56, 57, 57, 58, 58, 59, 59, 60, 60, 61, 61, 62, 62, 63,
63, 64, 64, 65, 65, 66, 66, 67, 67, 68, 68, 69, 69, 70, 70, 71, 71, 72, 72, 73, 73, 74, 74, 75, 75, 76, 76, 77, 77, 78,
78, 79, 79, 80, 80, 81, 81, 82, 82, 83, 83, 84, 84, 85, 85, 86, 86, 87, 87, 88, 88, 89, 89, 90, 90, 91, 91, 92, 92, 93,
93, 94, 94, 95, 95, 96, 96, 97
};
void Refine()
{
var tmp_ids = new List<int>();
var tmp_points = new List<float2>(points);
const float minDistanceSq = 2;
for (int i = 0; i < constraintIndices.Length / 2; i++)
{
var id0 = constraintIndices[2 * i + 0];
var id1 = constraintIndices[2 * i + 1];
var p0 = points[id0];
var p1 = points[id1];
if (math.distancesq(p0, p1) > minDistanceSq)
{
var id = tmp_points.Count;
tmp_points.Add(0.5f * (p0 + p1));
tmp_ids.Add(id0);
tmp_ids.Add(id);
tmp_ids.Add(id);
tmp_ids.Add(id1);
}
else
{
tmp_ids.Add(id0);
tmp_ids.Add(id1);
}
}
points = tmp_points.ToArray();
constraintIndices = tmp_ids.ToArray();
}
for (int i = 0; i < 10; i++)
{
Refine();
}
using var triangulator = new Triangulator(capacity: 1024, Allocator.Persistent);
using var inputPositions = new NativeArray<float2>(points, Allocator.Persistent);
using var constraintEdges = new NativeArray<int>(constraintIndices, Allocator.Persistent);
triangulator.Settings.ValidateInput = true;
triangulator.Settings.RefineMesh = false;
triangulator.Settings.ConstrainEdges = true;
triangulator.Settings.RestoreBoundary = true;
triangulator.Input.Positions = inputPositions;
triangulator.Input.ConstraintEdges = constraintEdges;
triangulator.Run();
Gizmos.color = Color.blue;
var triangles = triangulator.Output.Triangles;
for (int i = 0; i < triangles.Length / 3; i++)
{
var id0 = triangles[3 * i + 0];
var id1 = triangles[3 * i + 1];
var id2 = triangles[3 * i + 2];
var p0 = math.float3(points[id0], 0);
var p1 = math.float3(points[id1], 0);
var p2 = math.float3(points[id2], 0);
Gizmos.DrawLine(p0, p1);
Gizmos.DrawLine(p0, p2);
Gizmos.DrawLine(p1, p2);
}
Gizmos.color = Color.white;
foreach (var p in points)
{
Gizmos.DrawSphere(math.float3(p, 0), 0.1f);
}
for (int i = 0; i < constraintIndices.Length / 2; i++)
{
var id0 = constraintIndices[2 * i + 0];
var id1 = constraintIndices[2 * i + 1];
var c0 = math.float3(points[id0], 0);
var c1 = math.float3(points[id1], 0);
Gizmos.DrawLine(c0, c1);
}
}
I will think about some proper solution for that matter and I hope to release v1.5.0 in the next month which will fix this.
My favorite solution is 2. (with OBB), but editor freezing should be handled as well, even if one does not enable the option to OBB rescaling.
Best, Andrzej
Hi again @mduvergey, I managed also to implement solution no. 2 and it seems to work!
I made up the following algorithm:
- Calculate average point $\mu = \frac 1n \displaystyle\sum_{i=1}^n x_i $;
- Transform points: $x_i \to x_i - \mu$;
- Build covariance matrix: $\text{cov} = \frac 1n\displaystyle\sum_i x_i x_i^\mathsf T$;
- Solve eigen equation: $\text{cov} v_i = \lambda_i v_i$;
- Rotate points using $U = [v_i]$ matrix : $x_i \to U^{\mathsf T} x_i$;
- Find min and max point from transformed points and calculate $c = \frac12 (\text{min}+\text{max})$ and $s = \text{max} - \text{min}$;
- Transform points: $x_i \to 2 (x_i - c) / s$;
- Use the points as input for triangulation.
I tested this with your data but rotated by some angle. Here you have rotated data with eigen vectors from the covariant matrix (marked with green and red lines)
Here are data after applying $U$ and with corresponding bounding box (marked with yellow) and data after rescaling (point 7. in algorithm) marked with green.
Finally the proper solution with ConstrainEdges and RestoreBoundary enabled (without any additional constraint refinement).
Here is the dirty prototype solution
private void OnDrawGizmos()
{
float2[] points = {
new float2(14225.59f, -2335.27f), new float2(13380.24f, -2344.72f), new float2(13197.35f, -2119.65f),
new float2(11750.51f, -2122.18f), new float2(11670.1f, -2186.25f), new float2(11424.88f, -2178.53f),
new float2(11193.54f, -2025.36f), new float2(11159.36f, -1812.22f), new float2(10956.29f, -1731.62f),
new float2(10949.03f, -1524.29f), new float2(10727.71f, -1379.53f), new float2(10532.48f, -1145.83f),
new float2(10525.18f, -906.69f), new float2(10410.57f, -750.73f), new float2(10629.48f, -657.33f),
new float2(10622f, -625.7f), new float2(10467.05f, -552.15f), new float2(10415.75f, -423.21f),
new float2(10037.01f, -427.11f), new float2(9997.4f, -487.33f), new float2(9788.02f, -539.44f),
new float2(9130.03f, -533.95f), new float2(8905.69f, -490.95f), new float2(8842.1f, -396.11f),
new float2(8410.81f, -407.12f), new float2(8211.88f, -583.32f), new float2(7985.37f, -588.47f),
new float2(7880.46f, -574.94f), new float2(7200.87f, -574.14f), new float2(6664.29f, -637.89f),
new float2(6351.84f, -483.61f), new float2(6324.37f, -143.48f), new float2(6093.94f, -152.8f),
new float2(5743.03f, 213.65f), new float2(5725.63f, 624.21f), new float2(5562.64f, 815.17f),
new float2(5564.65f, 1145.66f), new float2(4846.4f, 1325.89f), new float2(4362.98f, 1327.97f),
new float2(5265.89f, 267.31f), new float2(5266.32f, -791.39f), new float2(3806f, -817.38f),
new float2(3385.84f, -501.25f), new float2(3374.35f, -372.48f), new float2(3555.98f, -321.11f),
new float2(3549.9f, -272.35f), new float2(3356.27f, -221.45f), new float2(3352.42f, 13.16f),
new float2(1371.39f, 5.41f), new float2(1362.47f, -191.23f), new float2(1188.9f, -235.72f),
new float2(1180.86f, -709.59f), new float2(132.26f, -720.07f), new float2(1.94f, -788.66f),
new float2(-1240.12f, -779.03f), new float2(-1352.26f, -973.64f), new float2(-1665.17f, -973.84f),
new float2(-1811.91f, -932.75f), new float2(-1919.98f, -772.61f), new float2(-2623.09f, -782.31f),
new float2(-3030.54f, -634.38f), new float2(-3045.53f, -52.71f), new float2(-3969.83f, -61.28f),
new float2(-6676.96f, 102.16f), new float2(-7209.27f, 100.12f), new float2(-7729.39f, 178.02f),
new float2(-8228.73f, 126.39f), new float2(-8409.52f, 164.47f), new float2(-9432.81f, 168.43f),
new float2(-9586.02f, 116.14f), new float2(-10758.65f, 110.23f), new float2(-10894.94f, 63.53f),
new float2(-11737.45f, 60.54f), new float2(-11935.7f, 1.79f), new float2(-12437.14f, -4.33f),
new float2(-12832.19f, 41.15f), new float2(-13271.23f, 30.64f), new float2(-13478.52f, 65.91f),
new float2(-13729f, 65.71f), new float2(-13846.23f, 21.68f), new float2(-14000.3f, 62.86f),
new float2(-15224.52f, 58.78f), new float2(-15232.59f, -142.28f), new float2(-4326.12f, -232.09f),
new float2(-4083.7f, -441.37f), new float2(-3467.35f, -478.48f), new float2(-3040.92f, -1160.16f),
new float2(7192.14f, -1332.7f), new float2(7249.66f, -939.11f), new float2(8399.41f, -932.84f),
new float2(8816.72f, -830.49f), new float2(9861.58f, -835.71f), new float2(10065.59f, -1110.57f),
new float2(10052.32f, -2118.14f), new float2(9006.64f, -2125.78f), new float2(8818.37f, -2203.58f),
new float2(8846.09f, -2620.2f), new float2(14244.65f, -2650.96f)
};
int[] constraintIndices = {
97, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18,
18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30, 30, 31, 31, 32, 32, 33,
33, 34, 34, 35, 35, 36, 36, 37, 37, 38, 38, 39, 39, 40, 40, 41, 41, 42, 42, 43, 43, 44, 44, 45, 45, 46, 46, 47, 47, 48,
48, 49, 49, 50, 50, 51, 51, 52, 52, 53, 53, 54, 54, 55, 55, 56, 56, 57, 57, 58, 58, 59, 59, 60, 60, 61, 61, 62, 62, 63,
63, 64, 64, 65, 65, 66, 66, 67, 67, 68, 68, 69, 69, 70, 70, 71, 71, 72, 72, 73, 73, 74, 74, 75, 75, 76, 76, 77, 77, 78,
78, 79, 79, 80, 80, 81, 81, 82, 82, 83, 83, 84, 84, 85, 85, 86, 86, 87, 87, 88, 88, 89, 89, 90, 90, 91, 91, 92, 92, 93,
93, 94, 94, 95, 95, 96, 96, 97
};
var phi = math.PI / 4;
var R = math.float2x2(math.cos(phi), math.sin(phi), -math.sin(phi), math.cos(phi));
points = points.Select(p => math.mul(R, p / 1000)).ToArray();
var mu = float2.zero;
foreach (var p in points)
{
mu += p;
}
mu /= points.Length;
var points_mu = points.Select(p => p - mu).ToArray();
static float2x2 Kron(float2 a, float2 b) => math.float2x2(a * b[0], a * b[1]);
var cov = float2x2.zero;
foreach (var p in points_mu)
{
cov += Kron(p, p);
}
cov /= points_mu.Length;
Eigen(cov, out _, out var eigvec);
Gizmos.color = Color.red;
Gizmos.DrawRay(math.float3(mu, 0), math.float3(eigvec[0], 0));
Gizmos.color = Color.green;
Gizmos.DrawRay(math.float3(mu, 0), math.float3(eigvec[1], 0));
Gizmos.color = Color.white;
foreach (var p in points)
{
Gizmos.DrawSphere(math.float3(p, 0), 0.1f);
}
var points_rot = points.Select(p => math.mul(math.transpose(eigvec), p)).ToArray();
Gizmos.color = Color.yellow;
foreach (var p in points_rot)
{
Gizmos.DrawSphere(math.float3(p, 0), 0.1f);
}
float2 min = float.MaxValue;
float2 max = float.MinValue;
foreach (var p in points_rot)
{
min = math.min(p, min);
max = math.max(p, max);
}
var c = 0.5f * (min + max);
var s = max - min;
Gizmos.color = Color.yellow;
Gizmos.DrawWireCube(math.float3(c, 0), math.float3(s, 0));
var points_norm = points_rot.Select(p => 2 * (p - c) / s).ToArray();
Gizmos.color = Color.green;
foreach (var p in points_norm)
{
Gizmos.DrawSphere(math.float3(p, 0), 0.1f);
}
Gizmos.DrawWireCube(math.float3(0, 0, 0), math.float3(2, 2, 0));
using var triangulator = new Triangulator(capacity: 1024, Allocator.Persistent);
using var inputPositions = new NativeArray<float2>(points_norm, Allocator.Persistent);
using var constraintEdges = new NativeArray<int>(constraintIndices, Allocator.Persistent);
triangulator.Settings.ValidateInput = true;
triangulator.Settings.RefineMesh = false;
triangulator.Settings.ConstrainEdges = true;
triangulator.Settings.RestoreBoundary = true;
triangulator.Input.Positions = inputPositions;
triangulator.Input.ConstraintEdges = constraintEdges;
triangulator.Run();
Gizmos.color = Color.blue;
var triangles = triangulator.Output.Triangles;
for (int i = 0; i < triangles.Length / 3; i++)
{
var id0 = triangles[3 * i + 0];
var id1 = triangles[3 * i + 1];
var id2 = triangles[3 * i + 2];
var p0 = math.float3(points[id0], 0);
var p1 = math.float3(points[id1], 0);
var p2 = math.float3(points[id2], 0);
Gizmos.DrawLine(p0, p1);
Gizmos.DrawLine(p0, p2);
Gizmos.DrawLine(p1, p2);
}
}
static void Eigen(float2x2 matrix, out float2 eigval, out float2x2 eigvec)
{
var a00 = matrix[0][0];
var a11 = matrix[1][1];
var a01 = matrix[0][1];
var a00a11 = a00 - a11;
var p1 = a00 + a11;
var p2 = (a00a11 >= 0 ? 1 : -1) * math.sqrt(a00a11 * a00a11 + 4 * a01 * a01);
var lambda1 = p1 + p2;
var lambda2 = p1 - p2;
eigval = 0.5f * math.float2(lambda1, lambda2);
var phi = 0.5f * math.atan2(2 * a01, a00a11);
eigvec = math.float2x2
(
m00: math.cos(phi), m01: -math.sin(phi),
m10: math.sin(phi), m11: math.cos(phi)
);
}
As I said before I'm going to implement this feature properly and release it in the future v1.5.0 (I plan to do it next month).
I hope that my answers resolve your issues.
If you have any additional questions let me know.
Best, Andrzej
Hi Andrzej,
Thank you very much for taking the time to investigate the matter, I appreciate that.
I think I will be able to implement a reliable fix with all the information you provided. Should any other problem arise, I will let you know. I am also looking forward the next version of the library :)
Best regards,
Martin
Hey @mduvergey,
I've just released v1.5.0, which resolves the editor hang during triangulation.
I have also introduced PCA transformation, which can be enabled with settings.UsePCATransformation = true;.
This transformation should address any issues with the triangulation input data that were mentioned in issues #30 and #31.
I hope that these changes will resolve all of the problems with the project.
I think that this will be the last major version (excluding any necessary bug fixes), and over the next 2-3 months, I plan to prepare version 2.0.0. In this version, I plan to refactor the codebase, remove deprecated features, update packages, and standardize the settings and input format.
If you have any suggestions or feature requests, please let me know so that I can consider additional updates before the release.
Best regards, Andrzej
PS The 1.5.0 is already available on OpenUPM.
Hi @andywiecko,
Thank you for the follow-up. I'll try the new version and let you know if I have any suggestions.
Best regards,
Martin