tessMeshRefineDelaunay issues

[chris0e3]

Hello.

I’m encountering a few anomalies with tessMeshRefineDelaunay in libtess2-1.0.2.

I’ve written a very simple example/test program that creates 1 or more, non-overlapping, circle or annulus like shapes, each with a user specified number of steps/points. These are all added to a TESStesselator using tessAddContour, CONSTRAINED_DELAUNAY_TRIANGULATION (CDT) is enabled (optionally) and then a single call to tessTesselate is made. The results are then output as EPS (which is easily viewed on macOS using Preview.app). Some timing stats are also reported.

This can create outputs from ~500 bytes (8 points, 1 contour → 6 triangles) to >500 MB (10,240,000 points, 400 contours → 10,240,000 triangles).

[The full program is only ~100 lines. I can post it here if requested.]

For example with 3 circles of 8 points each & CDT on; the output is:

But, with the same inputs but CDT off all 3 'circles' look like the rightmost one.
Is this expected behaviour? If I space out the shapes then the 2nd & 3rd look the same (but different from any of the above).

While experimenting with this I noticed that tessMeshRefineDelaunay does:

libtess2/Source/tess.c

Line 481 in fc52516

maxIter = maxFaces * maxFaces;

(where maxIter & maxFaces are ints) to limit the iteration count.
When maxFaces > 46,340 maxIter becomes negative (or undefined) resulting in no or a random amount of refinement.

This can be fixed with this change:

463:	long maxFaces = 0, maxIter = 0, iter = 0;

to:

libtess2/Source/tess.c

Line 463 in fc52516

int maxFaces = 0, maxIter = 0, iter = 0;

However, this does not fix the original problem. But it can cause tessMeshRefineDelaunay to dominate the run time. (I’ve seen billions of iterations in its while loop.) Further, if I run the program with (for instance):
        shape=annulus, steps=256, repeats=5, CDT=on it takes ~186 ms.
But with:
        shape=annulus, steps=257, repeats=5, CDT=on it takes ~3 ms.
And with CDT=off they both take ~2 ms.

So, in summary, I’m not convinced tessMeshRefineDelaunay is behaving correctly.

… a short while later …

I found this paper http://www.math.uha.fr/chevallier/publication/2009_07_09_article_cgta.pdf.
And, based on a cursory glance, I replaced the stack in tessMeshRefineDelaunay with a queue.
This appears to give better output results and can be as much as 100 (or even 300) times as fast when dealing with large numbers (>10,000) of triangles.

Here’s the minimal patch:

--- Source/tess.c~orig	2019-04-22 20:05:13.000000000 +0100
+++ Source/tess.c	2023-09-12 16:58:57.000000000 +0100
@@ -406,0 +407 @@
+	EdgeStackNode *end;
@@ -412 +413 @@
-	stack->top = NULL;
+	stack->top = stack->end = NULL;
@@ -432,2 +433,4 @@
-	node->next = stack->top;
-	stack->top = node;
+	node->next = NULL;
+	if (stack->end) stack->end->next = node;
+	else if (!stack->top) stack->top = node;
+	stack->end = node;
@@ -463 +466 @@
-	int maxFaces = 0, maxIter = 0, iter = 0;
+	long maxFaces = 0, maxIter = 0, iter = 0;

[chris0e3]

PING!

[sfreilich]

@chris0e3 I added some CI and tests just the other day, want to submit a PR with tests? It does seem like a big improvement, performance-wise. I can also do some downstream testing on projects on my end if I have a patch to test.