Support for Steiner points to refine Constrained Delaunay Triangulation?

[adrian-maggio]

Is there support in Tinfour for Constrained Delaunay Triangulation refinement via Steiner points? I am using Tinfour to triangulate perlin-noise generated 2D terrain paths. The constraints are causing many skinny triangles. Briefly read that Steiner points can be generated using the circumcircle centers of "bad triangles". Not sure if that is a valid approach, or how to achieve that.

[gwlucastrig]

The answer to that question is "yes and no".

In the near term, it is possible to put together a partial solution doing exactly what you described. It will be a little slow if your triangulation contains more than a few hundred thousand sample points. And it won't be as close to optimal as one might prefer. But it should help. I will post the broad outlines a a procedure below.

In the longer term, Delaunay refinement would be an important enhancement to the Tinfour library that I would very much like to see happen. I've researched both Ruppert's algorithm and Chew's second algorithm, and think I have an idea of how to proceed. I have wanted to do it for a few years now, but the level of effort is large... and, until you posted here, nobody has ever asked for it. It would take me a coupe of months to do the implementation (since Tinfour is not part of my "day job" and I can only work on it nights and weekends, work tends to go rather slow). So the question of whether I took on the project would depend on how much use you think you would have for Delaunay refinement and whether your own time requirements would be compatible with my limited work schedule.

Before I get started on my proposed approach, I have to ask if you are concerned about the assignment of z values to your Steiner points or if you only care about the horizontal geometry of the triangulation?

Also, if you could put some test data someplace where I could download it, I could see if I can implement some example code to test the ideas described below.

Okay, here's a broad outline of the quick and dirty solution:

1. Tinfour has a limitation in that once constraints are added to a triangulation, new points can no longer be added. This is a shortcoming that I hope to improve in the future. But for now, we have to deal with it. So as we add Steiner points to our collection, we have to rebuild the triangulation from scratch in order to incorporate them into the mesh.
2. Identify a list of skinny triangles. For a small subset of the worst cases, compute their circumcenters and use that to generate some new Steiner points.
3. Rebuild the triangulation, adding the Steiner points to input vertex set.
4. Repeat from step 2 until the number of skinny triangles declines sufficiently.

Ruppert's algorithm has a special rule for handling cases when the circumcenters fall outside the convex hull of the triangulation. I will look up the details tomorrow and post some more information.

As you can see, the method described above is slow because it involves rebuilding the Delaunay multiple times and also making a pass through the triangulation to identify skinny triangles each time a new Delaunay is built. Tinfour's pretty fast, repeating that process multiple time does take some processing time.

[micycle1]

I've been after this feature too (for the geometry projects of mine you've already seen). In the meantime I settled for a more simple approach of inserting triangle centroids as steiner points, but a "proper" solution would be awesome.

[adrian-maggio]

Thanks for the in-depth reply. I am indeed trying out the approach you outlined. Will have more time to work on it tonight probably. I am doing a lot of work on 2D procedural terrain generation for games, and having this refinement feature as a built in feature of Tinfour, hopefully with better performance than the workaround, would be awesome. Tinfour is already a lifesaver though, so thanks for that.

I put some test data here: https://github.com/adrian-maggio/delaunay-test-data

The raw perlin noise data:
test-noise-data-x161-y141.txt

The vertices for two iso paths generated by using marching-squares with a single threshold of 200. The smaller path is a hole.
test-path-0-data-x161-y141.txt
test-path-1-data-x161-y141.txt

The constraints I fed in to Tinfour:
test-outer-constraints-0-x161-y141.txt
test-hole-constraints-0-x161-y141.txt

test-outer-constraints-1-x161-y141.txt - I think this one is an anomaly, which I only noticed while adding debug statements to get this test data. The values are too huge to be used in my render code. I will investigate.

The triangle data output from Tinfour.
test-triangles-0-x161-y141.txt
test-triangles-1-x161-y141.txt

NOTE on the triangle data:
This is probably something wrong in my code, but I had to rotate each by -90 degrees and flip on the X-axis in order to get the triangle vertices to render correctly:

    AffineTransform at = new AffineTransform();
    at.rotate(-1.57079633);
    at.scale(-1, 1);
    Path2D path = tri.getPath2D(at);

[adrian-maggio]

I'll post some screenshots later.

[adrian-maggio]

[adrian-maggio]

Note: this is the without refinement. Notice the skinny triangles.

[gwlucastrig]

The geometry in you pictures looks like an excellent opportunity for refinement. I'm afraid I am not making much progress on my side. Do you have an easy way to send me that data to look at?

…

On Sun, Sep 11, 2022, 4:15 PM Adrian Maggio ***@***.***> wrote: Note: this is the without refinement. Notice the skinny triangles. — Reply to this email directly, view it on GitHub <#88 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AEWJDYN7IQIML6AV5MIAEMLV5Y4VBANCNFSM6AAAAAAQIJFEKA> . You are receiving this because you commented.Message ID: ***@***.***>

[adrian-maggio]

The data that went in to generating that picture, is in this github repo: https://github.com/adrian-maggio/delaunay-test-data. Descriptions of the files are outlined above.
If you can't get the files, I can email you a zip file of them.

My progress:

I've been trying out the procedure you outlined of determining skinny triangles, computing the circumcircle, adding the steiner points and re-running the triangulation, and I am getting some success, but am also running into some problems.

I am not sure if I am identifying skinny triangles correctly. Im just looking for if any angle is below a certain number of degrees, and if it is, calling it skinny.

This works in certain situations. Firstly, there is some problem when my geometry contains a hole, as in the picture above. If there is a hole, (I assume), steiner points appear to be placed outside of my iso paths, (inside the hole, and above my terrain constraint line), and I get triangles everywhere.

Ignoring the hole problem for now, I am currently testing with geometry without holes. In this case, If I set my "skinny" triangle threshold to 3 degrees (or something very small like that), and iterate the whole refinement process until either:

1. There are fewer than 20 skinny triangles
2. or the previous number of skinny triangles == the current number of skinny triangles
3. or the current number of skinny triangles > the previous number of skinny triangles

it somewhat works, (though i still have many relatively skinny triangles).
The reason for case item 3, is that sometimes, after falling, the number of skinny triangles will begin to rise again.

Also, if I set the skinny triangle threshold to anything higher than 3, I get more and more skinny triangles every iteration, until the whole process blows up.

[adrian-maggio]

I sent you email with the test data in a zip, and a link to a screen capture video.

I'm attempting to remedy the "hole" problem by ensuring that Steiner points are both within the main path, and NOT within any hole subpaths. Lots of Steiner points that would fall outside my main path constraint, are properly discarded with no ill effect.

However, if any Steiner points that would fall within a hole are discarded (simply not added to the tin during the next iteration), then things blow up with this error while trying to add my constraints:

Exception in thread "AWT-EventQueue-0" java.lang.IllegalStateException: Internal failure, constraint not added
at org.tinfour.standard.IncrementalTin.processConstraint(IncrementalTin.java:2201)
at org.tinfour.standard.IncrementalTin.addConstraints(IncrementalTin.java:1893)

[adrian-maggio]

I do not know why the omission of a few Steiner points would cause the constraints (that I used in previous iterations) to be invalid?

[adrian-maggio]

Update: The above error is what I get if I call this:
tin.addConstraints(constraintList, false);

If I call this:
tin.addConstraints(constraintList, true);

I get this error:

Exception in thread "AWT-EventQueue-0" java.lang.StackOverflowError
at java.base/java.util.HashMap.getNode(HashMap.java:567)
at java.base/java.util.HashMap.get(HashMap.java:552)
at org.tinfour.edge.EdgePool.splitEdge(EdgePool.java:562)
at org.tinfour.standard.IncrementalTin.restoreConformity(IncrementalTin.java:2543)
at org.tinfour.standard.IncrementalTin.restoreConformity(IncrementalTin.java:2569)
at org.tinfour.standard.IncrementalTin.restoreConformity(IncrementalTin.java:2569)
at org.tinfour.standard.IncrementalTin.restoreConformity(IncrementalTin.java:2569)
at org.tinfour.standard.IncrementalTin.restoreConformity(IncrementalTin.java:2569)
at org.tinfour.standard.IncrementalTin.restoreConformity(IncrementalTin.java:2569)
at org.tinfour.standard.IncrementalTin.restoreConformity(IncrementalTin.java:2569)
at org.tinfour.standard.IncrementalTin.restoreConformity(IncrementalTin.java:2569)
at org.tinfour.standard.IncrementalTin.restoreConformity(IncrementalTin.java:2569)
at org.tinfour.standard.IncrementalTin.restoreConformity(IncrementalTin.java:2569)
at org.tinfour.standard.IncrementalTin.restoreConformity(IncrementalTin.java:2569)
at org.tinfour.standard.IncrementalTin.restoreConformity(IncrementalTin.java:2569)

... this line repeats forever

[adrian-maggio]

Ok, found a bug in my code related to a scaling factor I use to condition point values. The scaling was being applied every time the refinement was run, so it was accumulating where it should not, causing vertex data to increase rapidly.

So, in other words, the refinement procedure you outlined is working for me. I still have the issue of the number of skinny triangles sometime increasing after refinement, and the issue of not being able to set my skinny triangle angle threshold above 3 degrees. Any idea on how to fix those?

[adrian-maggio]

Here is some test results:

[gwlucastrig]

First off, i think you've made petty good progress. I don't have any ideas right now. But I am going to reread Ruppert's paper tonight and see if I can come up with anything more.

…

On Tue, Sep 13, 2022, 4:00 PM Adrian Maggio ***@***.***> wrote: Here is some test results: [image: Screen Shot 2022-09-13 at 3 58 27 PM] <https://user-images.githubusercontent.com/22044272/189997701-45f330b7-738b-4ed4-909c-e7701328c44d.png> [image: Screen Shot 2022-09-13 at 3 58 46 PM] <https://user-images.githubusercontent.com/22044272/189997730-d33e1bef-4ad6-45c7-b5da-58161715bb23.png> [image: Screen Shot 2022-09-13 at 3 59 20 PM] <https://user-images.githubusercontent.com/22044272/189997745-d01a42a3-5284-41f9-b7bb-779599d46e70.png> [image: Screen Shot 2022-09-13 at 3 59 33 PM] <https://user-images.githubusercontent.com/22044272/189997754-49e27b4f-eb5a-4bfb-b6a3-b35f923c2a9a.png> — Reply to this email directly, view it on GitHub <#88 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AEWJDYKMTANLZ4DLBFY66ZTV6DMPHANCNFSM6AAAAAAQIJFEKA> . You are receiving this because you commented.Message ID: ***@***.***>

[gwlucastrig]

Looking at your results, they're really impressive. I especially like to animation you presented. I am pleased that Tinfour could be part of that.

I dug up my old notes on algorithms for Delaunay refinement and had started working on some test code. It's going to be a long and challenging process. So I won't be able to provide much of use to you in the near term.

One thing I wanted to mention. Two well known investigators into the Delaunay, Ruppert and Shewchuk, both caution about cases where the constraint geometries include sharp angles. Because they are constraints, they can't be adjusted, and no matter how many points an algorithm inserts, they will still maintain the original angles. Ruppert and Shewchuk both offer solutions involving "guard edges", but neither of them really appeal to me. I didn't see any features like that in your source data, but it is something that could present a problem in the future.

[adrian-maggio]

Thanks. I think the iterative approach to re-triangulating after adding Steiner points, until the number of bad triangles reaches a threshold minimum number, (or we detect an increase, or the number reaches equilibrium), is enough for me for now. It might be a bit slow, but with the relatively small number of triangles, it may be enough.

I will know more once I can port my test code back in to my main codebase, (moving from swing/awt code to libGdx mobile code). This brings me to another point. Since mobile dev does not like awt classes, I think I am going to undertake making a version of Tinfour that does not use any awt classes. Will let you know how that goes. Perhaps it is something you might want to keep? If anyone else has a need for Tinfour's functionality for use in mobile development, it might be worth keeping.

[adrian-maggio]

I will keep that in mind, regarding sharp angles. Perhaps I can tailor my scalar field data to prevent that.

[gwlucastrig]

I am kicking myself fir using the java.awt in the Tinfour core module. What a dumb move!

The way the code is organized, it uses Rectangle2D in a lot of places as a way of getting the domain or bounds of a data set. As a start I would think of replacing them with a simple Java object that does the same thing. Is there anything else in the standard Java API that would be suitable?

Tee core module also includes quite a few utility classes I wrote to support graphics operations. They could probably migrate to a separate module, perhaps something like TinfourGraphics.jar or TinfourAwt.jar. Then anyone who wanted to use Tinfour on an Android could simply ignore them. A couple of the constraint-related classes have methods that produce a Path2D, and these would have to move.

The demo module would probably continue to use java.awt. I am not sure about TinfourGIS, but I would try to make it independent of Swing/AWT.

The changes would definitely break compatibility with existing code. Perhaps I could do something like the Apache folks do and define a new revision using org,tinfour2.* instead of org.tinfour.*

I can envision a new github named something like TinfourGdx to support libGdx. If you decide you (or anyone else) would like to do something like that, let me know and I'll link to it from the main project page. I think that, ideally, there would be just one TinfourCore built in the main repository, but other projects could pursue non-Swing/AWT solutions.

[gwlucastrig]

Well I'll be... You already forked off a project called Tinfour-nonAWT. It will be interesting to see where you take things.

[adrian-maggio]

Check this out:
https://drive.google.com/file/d/1nG8ePtcnbGmhGsDByUo8uihV1F8qBYql/view?usp=sharing

That is running on my phone. A libGDX project I am working on, perlin-noise, procedurally generated terrain data, iso-lines created by marching squares, using the non-awt Tinfour (using my mobile-awt hacks) to refine the triangles, and producing 2d voxel chunks as terrain tiles. It's not pretty, but it is doing a rough job of what I want with the first try.

Made a very small subset of the awt stuff used by Tinfour core, without actual awt dependencies, in my project:
https://github.com/cyborg-interactive-llc/mobile-awt
At the same time, made a version of Tinfour (pardon the stuff that was ripped out for this experiment), which uses mobile-awt, here:
https://github.com/cyborg-interactive-llc/Tinfour-nonAWT
The branch I am working on is "remove-awt-deps", if you want to see the mess I am making.