Index out of Range in FindTriangleNode()

[happy-turtle]

Hi, really cool work! I am sometimes getting an Index out of Range exception in the FindTriangleNode function. I debugged a bit: t.C2 is chosen in these cases, but C2 has the value -1. With curr == C2 == -1, triangles[-1] is out of range. This happens with polygons with a size of about 200 vertices. Do you maybe have an idea how to fix this issue?

int FindTriangleNode(int pi) {
    var curr = 0;

    while (!triangles[curr].IsLeaf)
    {
        var t = triangles[curr];

        if (t.C0 >= 0 && PointInTriangle(pi, t.C0)) {
            curr = t.C0;
        } else if (t.C1 >= 0 && PointInTriangle(pi, t.C1)) {
            curr = t.C1;
        } else {
            curr = t.C2;
        }
    }
    return curr;
}

Do you think it would be possible for me to extend this library to build constrained conforming or conforming triangulations? Or are these based on completely different algorithms. Maybe you looked into these topics.

I am working on generating meshes out of outlines in a video stream. With OpenCV I'm getting the outlines in the image as polygons and then I want to build meshes out of these polygons via Delaunay Triangulation. Your library is well structured and good to read, thanks a lot.

[OskarSigvardsson]

Hi! Thanks for the nice words!

I can't say that I've seen this particular issue, and it's not immediately clear to me what's going on. My guess is it's some sort of corner case I haven't considered (points falling exactly on other points or on some shared edge or something). Can you provide a set of points which causes this? It's going to be hard to debug otherwise. Just post the list as CSV or something (make sure the coordinates aren't rounded off, if you just print Unity's Vector3's, they round the coordinates off to uselessly few digits. Printing the x/y/z coordinates directly or converting them directly to strings usually does the job. ).

I am working on generating meshes out of outlines in a video stream. With OpenCV I'm getting the outlines in the image as polygons and then I want to build meshes out of these polygons via Delaunay Triangulation. Your library is well structured and good to read, thanks a lot.

I'm happy that you like my library, but if your polygons are convex, doing Delaunay triangulations seems a little overkill, you can just triangulate your polygons by drawing a line from one vertex to all the other ones. And if your polygons aren't convex, don't you need to make them convex before calling my library? Otherwise, doesn't the library triangulate the things outside the polygons (i.e. it triangulates the convex hull of the points in the polygon)? Anyway, just curious 🙂

I'd love to get the set of points that causes the issue so i can debug it. People seem to like this library and I want to ensure it's high-quality. No promises on when I'll be able to get to fixing it, though, but I will try and investigate this when I can.

[happy-turtle]

Thanks for the quick response. I attached a zip file with all the polygons that throw this error in seperate csv files, I hope you can work with these.

polygons.zip

I'm happy that you like my library, but if your polygons are convex, doing Delaunay triangulations seems a little overkill, you can just triangulate your polygons by drawing a line from one vertex to all the other ones. And if your polygons aren't convex, don't you need to make them convex before calling my library? Otherwise, doesn't the library triangulate the things outside the polygons (i.e. it triangulates the convex hull of the points in the polygon)? Anyway, just curious 🙂

Yes, you are completely right, I might be on the wrong track. 😄 I am trying to wrap my head around all the different algorithms and what I actually need in the end. My polygons are not convex, yes. And when I currently triangulate with your library I get the outsides triangulated as well, which I ultimately do not need. That is the point where I am not sure how to proceed. For example in this library by mattatz he does a triangulation first, like you do. And then he further refines the triangulation by adding Steiner points. His library is a lot slower though, and the ultimate goal for me is to do all this in realtime. So my current understanding is, I could use your library for the first triangulation and then build on top of this triangulation to do further refinements to delete the unneeded outsides and maybe add Steiner points. Would you say this is alway done before triangulation? Or as an inclusive part of the algorithm itself?

Edit: This seems to be my optimal outcome.

[OskarSigvardsson]

It sounds what you're looking for is a polygon triangulation algorithm. You can do this with Delaunay libraries that support "constrained Delaunay triangulations" where you say "these edges HAVE to be in the final triangulation, even if it violates the Delaunay condition", and then you remove all the edges that are outside the polygon. With a regular Delaunay triangulations, there's no guarantee that the edges of the polygons are part of the final triangulation (in fact, they probably wont be). Unfortunately, my library doesn't support these kinds of constraints.

It's also a little overkill to use Delaunay for polygon triangulations. There's a technique called "ear clipping" which is pretty easy to implement if you wanna give it a go yourself (look it up on wikipedia). It's O(n^2), but for polygons with ~200 points, that should be easily doable in real time. It gets trickier if your polygon has holes, though. I'm sure there's some Unity library for this somewhere, though, it's such a basic thing. If there's not, I should make one I guess :) I have a vague memory of implementing the sweepline algorithm for Unity years back, but I have no idea where that code is.

Anyway, thanks for the data, I'll be looking into it!

[happy-turtle]

Ear clipping might be a good suggestion. I will try it out. My best outcome until now was with Triangle.Net, a C# port of Triangle. It uses the constrained Delaunay algorithm that you mentioned. The advantage of that library is that I can control the triangle quality. I later extrude the vertices with height maps and tesselation shaders. More evenly distributed vertices and triangles with nice angles result in a smoother lighting of the extruded mesh. But Triangle.Net is not really made for realtime purposes, it produces a lot of garbage and I am barely reaching 30 fps. That was what made your library so much more attractive. :smile: I will see if ear clipping gives me reasonably good results for further extrusion. Thanks a lot for the conversation, your interest and your time, it helped a lot!