Curve2D.tessellate() duplicates each redundant point 60 times.

DinoMC commented 4 months ago

Tested versions

Reproducible in: 4.3.beta2.official [b75f0485b]

System information

Godot v4.3.beta2 - Windows 10.0.22631 - Vulkan (Forward+) - dedicated NVIDIA GeForce RTX 4070 (NVIDIA; 32.0.15.5585) - Intel(R) Core(TM) i7-9700K CPU @ 3.60GHz (8 Threads)

Issue description

If you tessellate a 5 points square (5th point is to close the curve), you end up with an array of 5 points (normal behavior).

If for some reason, one of that point is repeated in your curve, the curve still form the exact same square, with a 6th useless point. But if you tessellate it, you end up with an array of 66 points, with the redundant point repeated 61 times in a row. If every point is duplicated (still the same curve), you end up with 325 points.

This doesn't seem to serve any purpose so I assume this is a bug.

(PS. Explanation of why I have redundant points and why this might be an issue in practice :

I'm clipping polygons for a freeform digging system, which is how I ended up with duplicate points in my array - might be because of an error in my code tho.

Then my script started throwing "convex decomposing failed" errors, and while looking for the issue in the debugger, I realized that my polygons had WAY more points than they should.

Eventually tracked it down to the tessellate() function that would multiply the points, then I throw back the new shape into it when digging again, multiplying those 60 times again exponentially.

Now after generating my new terrain polygons, I use a function to remove all points that are less than 1.0 distance to the previous one and I don't have any error anymore)

Steps to reproduce

Create a Curve2D, tessellate it, check the amount of points.
Duplicate a point in the curve.
Tesselate it again, check the amount of points. It will have gone up by 61.

Example : Starting curve is (0,0) , (0,1) , (1,1) . Tessellate point count is 3. Second curve is (0,0) , (0,1) , (0,1) , (1,1) . Tesselate point count is 64.

Minimal reproduction project (MRP)

tessellate-bug-mrp.zip

This create a curve in the form of a square, tessellate it, print the points count. Then duplicates every points and repeat, 10 times. The amount of points grows very fast (5 -> 325 -> 645 -> ...)

Second test is tessellating, then creating a new curve with the result and tessellating again. The amount of points grows exponentially (5 -> 325 -> 20485) then fail on the third loop (tessellate() returns \ with no error)

djtech-dev commented 4 months ago

I know this isn't releted to the bug, but a good idea to implement a freeform digging system should be to use a voxel-based environment (add-on for Godot 4.x)

jmattspartacus commented 3 months ago

For the second test, can you describe the behavior you expect? I have the first test fixed, but I want to make sure I put this to bed before I open the PR.

jmattspartacus commented 3 months ago

Additional question for you, if you cull the points that are the same, was it giving you the desired effect in your project? These points also don't have in/out specified. Without specifying in/out for each point, interpolating the bezier curves doesn't really give a meaningful output. Consider this additional test that I've added to make sure I'm not losing other desired behavior.


func sq(x, a, b):
    return a*x*x + b
print("test3: simple a x^2 + b curve ")
var testcurve3 = Curve2D.new()

for i in range(0, 20, 2):
    var pos = Vector2(i, sq(i, -.1, 10))
    # if we set these to (0,0) as they are by default
    # the tesselated point will always be (0,0)
    var in_point = Vector2(i - 1, sq(i - 1, -.1, 10))
    var out_point = Vector2(i + 1, sq(i + 1, -.1, 10))
    testcurve3.add_point(pos,in_point,out_point)
var tessel3 = testcurve3.tessellate()
# we expect this to be larger than the number of iterations since it's
# swinging through an arc
print(tessel3.size())

DinoMC commented 3 months ago

Second test was to illustrate how the same issue could cause to crash very fast even if starting with only 5 points, so fixing the first one should fix the second too. Expected result would be, if I start with a simple shape like the example square, I should be able to run the second test and end up with a low amount of point even after all 10 iterations. But if you start with a very complex shape, it would make sense for it to fail even with the fix.

In my project : I assume bezier curves don't do anything if applied to a line of length 0 (correct?). If I had eg. a Polygon with points P1 P2 P3 P4 that turned into P1 P2 P2 .... P2 P2 P3 P4 after tessellate(), I'd keep the first and last instances of P2, the ones that actually drew lines to P1 and P3 (and where the bezier curves might be useful) and it seemed to work correctly.

I agree that it makes sense for the number of points to be high in the additional test you posted. I think you should check if the print returns the same number with and without the PR, if it's less we should make sure that it's not discarding useful points.

Interestingly I tried a new test after reading this and the result shows tessellate() really doesn't work as expected currently. Consider this variant of the first test :

    for i in range(1, 11):
        var testcurve = Curve2D.new()
        testcurve.add_point(Vector2(0,0))
        testcurve.add_point(Vector2(40,0))
        for j in range(0, i):
            testcurve.add_point(Vector2(40,40))
        testcurve.add_point(Vector2(0,40))
        var tessel = testcurve.tessellate()
        print(tessel.size())

Makes a simple square shape (not closed), should be easy to tessellate without losing accuracy, even with the duplicate points. Print result grows rapidly, up to 580. Now, if I edit it like this :

    for i in range(1, 11):
        var testcurve = Curve2D.new()
        testcurve.add_point(Vector2(0,0))
        testcurve.add_point(Vector2(40,0))
        var in_point = Vector2(i*3, i*3)
        var out_point = Vector2(i*-3, i*-3)
        for j in range(0, i):
            testcurve.add_point(Vector2(40,40), in_point, out_point)
        testcurve.add_point(Vector2(0,40))
        var tessel = testcurve.tessellate()
        print(tessel.size())

It now create curves that are more complex and should require more points to tessellate accurately, but still with the same number of duplicate points. In this case, the first print starts higher (expected, curve is more complex), but grows WAY slower, only ~10 points per iteration rather than 60 in the previous one, ending up at only 116. It seems the bug that duplicates identical points 60 times actually doesn't apply if the point has a bezier curve for some reason, even if it's not used.

You should try this with the PR to check if the result is more expected (second test creates more complex curves so it should return more points)

godotengine / godot