Some Constraint are ignored

[katastorm]

Hi 😄

I am working on a path-finding project for an Unity 2D Game. It has been 2 weeks since i've started using BurstTriangulator and this tool is amazing ! 🥇

For my use case i need to take the shapes of the walls from my rooms, exclude holes and area where enemies are not supposed to go. Actually, it works for 95% of my rooms. An example of the problem on the problematic :

In yellow the constraint Edges used in input

Here my result with holes seeds disabled :

Some edges are randomly ignored, causing sometimes an output result with 0 triangles. I tried to disable Burst, like said on some other asked issues, but it didn't work.

Any idea ? Thanks ! 👍

[andywiecko]

Hi @katastorm, Thank you very much for your contribution to the project!

Could you please provide me with some code that reproduces the bug (at least input data)? I will debug it over the weekend.

Best, Andrzej

[andywiecko]

I believe I need additional data from you since I've extracted points from picture which you attached but on my machine triangulation performs correctly (using v2.4.0) 😅 I've checked many settings refinement on/off, holes on/off. All passed without any bug.

Below reproduction:

[Test]
public void GithubIssue111Test()
{
    double2[] managedPositions =
    {
        new(3.897305171158049, -0.1048798252002916),
        new(3.878077203204662, 0.14498664724447607),
        new(1.6193736343772762, 0.14319009468317567),
        new(1.5950473415877644, 1.6360767176499147),
        new(-0.1667880553532411, 1.6168973051711584),
        new(-0.1963583394027677, 3.3597475115319257),
        new(1.5589220684632197, 3.358048069919884),
        new(1.525418790968682, 4.621704297159505),
        new(3.791114348142753, 4.623549405195436),
        new(3.7858703568827385, 4.8735129885894635),
        new(5.784996358339404, 4.915173585821801),
        new(5.790823015294976, 4.637436270939548),
        new(8.041951930080117, 4.666957999514445),
        new(8.081864530225785, 3.431124059237678),
        new(9.59213401310998, 3.4416120417577067),
        new(9.622286962855064, 1.670988103908714),
        new(8.125855790240351, 1.667540665210001),
        new(8.149890750182085, 0.18854090798737477),
        new(5.891624180626367, 0.16591405680990423),
        new(5.9178441369264405, -0.08390386016023399),
        new(3.5651857246904592, 3.3928137897547948),
        new(6.061471230881283, 3.4032046613255638),
        new(6.066715222141298, 4.153241077931536),
        new(3.563437727603788, 4.142801650886137),
        new(3.6231609613983977, 0.6293275066763773),
        new(6.132993445010926, 0.6606457878125749),
        new(6.1309541150764755, 1.4245205146880302),
        new(3.6212672978878375, 1.3862588006797765),
        new(2.3747997086671524, 1.1345472201990772),
        new(2.864530225782958, 1.124059237679048),
        new(2.8067006554989082, 3.880602087885409),
        new(2.3032774945375096, 3.877106093712066),
        new(6.863364894391843, 1.1796067006554982),
        new(7.387909686817189, 1.1763049283806732),
        new(7.330225782957029, 3.9259043457149785),
        new(6.819956300072835, 3.9154163631949492),
    };

    int[] managedConstraints =
    {
        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, 0,
        20, 21, 21, 22, 22, 23, 23, 20,
        24, 25, 25, 26, 26, 27, 27, 24,
        28, 29, 29, 30, 30, 31, 31, 28,
        32, 33, 33, 34, 34, 35, 35, 32,
    };

    float2[] managedHoles =
    {
        new(4.887982520029134f, 1.0061665452779804f),
        new(2.605098324836125f, 2.490313182811362f),
        new(4.844282592862346f, 3.7558630735615437f),
        new(7.109541150764749f, 2.7785384802136432f),
    };

    using var positions = new NativeArray<float2>(managedPositions.Select(i => (float2)i).ToArray(), Allocator.Persistent);
    using var constraints = new NativeArray<int>(managedConstraints, Allocator.Persistent);
    using var holes = new NativeArray<float2>(managedHoles, Allocator.Persistent);
    using var triangulator = new Triangulator(Allocator.Persistent)
    {
        Input =
        {
            Positions = positions,
            ConstraintEdges = constraints,
            HoleSeeds = holes,
        },
        Settings =
        {
            RefineMesh = true,
            RefinementThresholds = { Angle = math.radians(25f), Area = 0.1f },
            ConstrainEdges = true,
            RestoreBoundary = true,
            ValidateInput = true,
        }
    };

    triangulator.Run();
    triangulator.Draw();
}

[katastorm]

Hey !

(Triangulator.Run() : woah i didn't know that !)

Thanks for your quick answer. That's incredible, i've created an empty project and pass same values as in my game, and the bug persists. Here is my entire code :

using andywiecko.BurstTriangulator;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using Unity.Collections;
using Unity.Mathematics;
using UnityEngine;

public class Script : MonoBehaviour
{

    List<Vector2> positions;
    List<Vector2> holesSeeds;
    List<int> constraint;

    Triangulator tri;

    private void Awake()
    {

        positions = new List<Vector2>() {
            new Vector2(16.5f,1.5f),
            new Vector2(16.5f,2.5f),
            new Vector2(7.5f,2.5f),
            new Vector2(7.5f,8.5f),
            new Vector2(0.5f,8.5f),
            new Vector2(0.5f,15.5f),
            new Vector2(7.5f,15.5f),
            new Vector2(7.5f,20.5f),
            new Vector2(16.5f,20.5f),
            new Vector2(16.5f,21.5f),
            new Vector2(24.5f,21.5f),
            new Vector2(24.5f,20.5f),
            new Vector2(33.5f,20.5f),
            new Vector2(33.5f,15.5f),
            new Vector2(39.5f,15.5f),
            new Vector2(39.5f,8.5f),
            new Vector2(33.5f,8.5f),
            new Vector2(33.5f,2.5f),
            new Vector2(24.5f,2.5f),
            new Vector2(24.5f,1.5f),
            new Vector2(15.5f,15.5f),
            new Vector2(25.5f,15.5f),
            new Vector2(25.5f,18.5f),
            new Vector2(15.5f,18.5f),
            new Vector2(15.5f,4.5f),
            new Vector2(25.5f,4.5f),
            new Vector2(25.5f,7.5f),
            new Vector2(15.5f,7.5f),
            new Vector2(10.5f,6.5f),
            new Vector2(12.5f,6.5f),
            new Vector2(12.5f,17.5f),
            new Vector2(10.5f,17.5f),
            new Vector2(28.5f,6.5f),
            new Vector2(30.5f,6.5f),
            new Vector2(30.5f,17.5f),
            new Vector2(28.5f,17.5f),
            new Vector2(0.5f,11.5f),
            new Vector2(20.5f,21.5f),
            new Vector2(39.5f,11.5f),
            new Vector2(20.5f,1.44f)
        };

        constraint = new List<int>() {
            0,1,
            1,2,
            2,3,
            3,4,
            36,5,
            5,6,
            6,7,
            7,8,
            8,9,
            37,10,
            10,11,
            11,12,
            12,13,
            13,14,
            38,15,
            15,16,
            16,17,
            17,18,
            18,19,
            39,0,
            20,21,
            21,22,
            22,23,
            23,20,
            24,25,
            25,26,
            26,27,
            27,24,
            28,29,
            29,30,
            30,31,
            31,28,
            32,33,
            33,34,
            34,35,
            35,32,
            4,36,
            9,37,
            14,38,
            19,39
        };

        holesSeeds = new List<Vector2>() {
            new Vector2(16.5f,16.5f),
            new Vector2(16.5f,5.5f),
            new Vector2(11.5f,7.5f),
            new Vector2(29.5f,7.5f),
        };

        static float2[] castFloat2(IEnumerable<Vector2> vals)
        {
            return vals.Select(m => new float2(m.x, m.y)).ToArray();
        }

        using var constraintEdges = new NativeArray<int>(constraint.ToArray(), Allocator.Persistent);
        using var nativePositions = new NativeArray<float2>(castFloat2(positions), Allocator.Persistent);
        using var holes = new NativeArray<float2>(castFloat2(holesSeeds), Allocator.Persistent);

        tri = new Triangulator(Allocator.Persistent)
        {
            Settings =
            {
                ValidateInput = true,
                RestoreBoundary = true,
            },
            Input = {
                Positions = nativePositions,
                ConstraintEdges = constraintEdges,
                //HoleSeeds = holes,
                },
        };

        tri.Schedule().Complete();        
    }

    private void OnDrawGizmos()
    {
        if (!Application.isPlaying)
            return;

        float gizmoSize = 0.5f;

        Gizmos.color = Color.blue;
        foreach (var p in positions)
        {
            Gizmos.DrawSphere((Vector2)p, Gizmos.probeSize * gizmoSize); 
        }

        Gizmos.color = Color.red;
        foreach (var p in holesSeeds)
        {
            Gizmos.DrawSphere((Vector2)p, Gizmos.probeSize * gizmoSize);
        }

        Gizmos.color = Color.cyan;

        Vector2 p1;
        Vector2 p2;
        Vector2 p3;

        for (int i = 0; i < tri.Output.Triangles.Length/  3; i++)
        {
            p1 = positions[tri.Output.Triangles[i * 3 + 0]];
            p2 = positions[tri.Output.Triangles[i * 3 + 1]];
            p3 = positions[tri.Output.Triangles[i * 3 + 2]];

            Gizmos.DrawLine(p1, p2);
            Gizmos.DrawLine(p2, p3);
            Gizmos.DrawLine(p3, p1);
        }

        Gizmos.color = Color.yellow;
        for (int i = 0; i < constraint.Count / 2; i++)
            Gizmos.DrawLine(positions[constraint[i * 2]], positions[constraint[i * 2 + 1]]);
    }
}

I am using Unity 2021.3.34f1. Each time i add your package for the first time Unity yells errors at me and i have to modify some lines my myself. Maybe thats the cause of the problem ?

Thank you !

Entire project : EmptyProject_BurstTriangulator.zip

[andywiecko]

Hi @katastorm,

Great news! Thanks for your input. I've managed to find a bug. With commit 53c3f5c5453e52bb3b882ca7533f89d3d7116ed1, this should work perfectly. The commit just appends two lines in the resolving constraints algorithm:

                    pointToHalfedge[_q] = h0;
                    pointToHalfedge[_p] = h3;
                    pointToHalfedge[_i] = h4; //added
                    pointToHalfedge[_j] = h1; //added

I'm just wondering why this particular bug shows up just now! 😅 Many thanks for your contribution. This makes the package more stable. I hope that many users will benefit from that.

---

I am using Unity 2021.3.34f1. Each time i add your package for the first time Unity yells errors at me and i have to modify some lines my myself. Maybe thats the cause of the problem ?

Regarding your errors, I've checked packages-lock.json with the project you shared. You have to bump the Unity.Burst and Unity.Collections packages to resolve this. Please note that the package has the following dependencies defined in package.json:

 "dependencies": {
    "com.unity.burst": "1.8.7",
    "com.unity.collections": "2.2.0"
}

I strongly suggest updating these packages if you can. I also recommend using Unity Package Manager (UPM) to install BurstTriangulator (or OpenUPM to get the stable release). With UPM the appropriate dependencies will be install automatically. To fetch my commit with the fix, you can modify your project manifest as follows:

{
  "dependencies": {
    "com.andywiecko.burst.triangulator": "https://github.com/andywiecko/BurstTriangulator.git#53c3f5c5453e52bb3b882ca7533f89d3d7116ed1",

   ...

---

This fix will be included in the upcoming release v2.5.0, but before release we have to wait until #110 is merged.

PS Good luck with your game development :) I'm looking forward to the result!

[katastorm]

Thanks a lot! I will check your changes and send updates very quickly 😁

[katastorm]

Your fix work perfectly on my side. Thanks for all, I can't wait to see how this tool will evolve !

Here a simple prototype of path-finding using Burst triangulator (and triangle centroids) :

https://github.com/andywiecko/BurstTriangulator/assets/45739730/7d41e735-06c1-4cfe-ab8f-968b06df4298

[andywiecko]

Your fix work perfectly on my side. Thanks for all, I can't wait to see how this tool will evolve !

I'm glad I could help. Let me know if you need any further assistance with the package. Regarding upcoming features, in the near future, I plan to add support for auto holes detection and dynamic triangulation, which should be beneficial, for example, in RTS engines.

Here a simple prototype of path-finding using Burst triangulator (and triangle centroids) :

Wow, it looks very promising, congratulations! I'm also planning to develop an add-on package for BurstTriangulator specifically for pathfinding algorithms with trimeshes. However, this will take some time as I currently have limited availability for personal project development.

Best, Andrzej

[andywiecko]

@katastorm FYI, I've just released v2.5.0 (it is available on OpenUPM as well). This release contains a fix related to your issue.