Curve3D get_closest_point broken

[Skwint]

Godot version

4.0.dev commit f9fa182

System information

windows 7 and windows 11

Issue description

The Curve3D.get_closest_point function now returns weirdly discrete answers, instead of the closest points.

Steps to reproduce

Make a node with a script and put this in the ready function.

func _ready():
	var frog : Curve3D = Curve3D.new()
	frog.add_point(Vector3(0.0, 0.0, 0.0), Vector3(0.0, -10.0, 0.0), Vector3(0.0, 10.0, 0.0))
	frog.add_point(Vector3(0.0, 100.0, 0.0), Vector3(0.0, -10.0, 0.0), Vector3(0.0, 10.0, 0.0))
	
	var pos = Vector3(0.2, 0.0, 0.0)
	
	for y in range(0.0, 100.0):
		pos.y = y
		var found = frog.get_closest_point(pos)
		print("at ", y, " => ", found)

The curve is just a straight line so it should return points with a Y value matching the Y value of the query.
Instead what you get is:

at 0 => (0, 0, 0)
at 1 => (0, 50, 0)
at 2 => (0, 50, 0)
at 3 => (0, 50, 0)
at 4 => (0, 50, 0)
at 5 => (0, 50, 0)
.
.
.
at 74 => (0, 50, 0)
at 75 => (0, 50, 0)
at 76 => (0, 100, 0)
at 77 => (0, 100, 0)
.
.
.

I'm 99% sure the commit f9fa182 introduced this one.

Minimal reproduction project

N/A

[kleonc]

Can confirm it works properly in v4.0.beta6.official [7f8ecff] and incorrectly in [68e3f49].

cc @xiongyaohua who made #69043.

[xiongyaohua]

My bad. Should be fixed by #69239

[Skwint]

I'm sorry, this fix is definitely an improvement, but the results are still weirdly discrete. If I change my test case to this:

	var toad : Curve3D = Curve3D.new()
	toad.add_point(Vector3(0.0, 0.0, 0.0), Vector3(0.0, -10.0, 0.0), Vector3(0.0, 10.0, 0.0))
	toad.add_point(Vector3(0.0, 100.0, 0.0), Vector3(0.0, -10.0, 0.0), Vector3(0.0, 10.0, 0.0))
	
	var rad = Vector3(0.2, 0.0, 0.0)
	
	for y in Vector3(49.0, 51.0, 0.1):
		rad.y = y
		var found = toad.get_closest_point(rad)
		print("at ", rad, " => ", found)

then the output looks like:

at (0.2, 49.5, 0) => (0, 49.47266, 0)
at (0.2, 49.6, 0) => (0, 49.47266, 0)
at (0.2, 49.7, 0) => (0, 49.47266, 0)
at (0.2, 49.8, 0) => (0, 50, 0)
at (0.2, 49.9, 0) => (0, 50, 0)
at (0.2, 50, 0) => (0, 50, 0)
at (0.2, 50.1, 0) => (0, 50, 0)
at (0.2, 50.2, 0) => (0, 50, 0)
at (0.2, 50.3, 0) => (0, 50.52734, 0)
at (0.2, 50.4, 0) => (0, 50.52734, 0)
at (0.2, 50.5, 0) => (0, 50.52734, 0)

Internally it is interpolating a dot product along the length of a straight line segment and while I expect to see floating point rounding errors I don't expect it to "step" in chunks of over 0.5. There's something weird going on.

[Skwint]

Increasing the bake interval from the default 0.2 to 1.0 improves the results a bit, although they still have repeating results at the 0,50,0 point, but it shows something else weird as well - I don't know if this helps:

at (0.2, 49.6, 0) => (0, 49.67346, 0)
at (0.2, 49.7, 0) => (0, 49.78468, 0)

The result for y=49.6 is closer to 49.7 than the result found for 49.7. That can't be right. Infact, I'm pretty sure I should be getting almost exactly equal Y values for both of these.

[kleonc]

According to the docs Curve3D.get_closest_point is supposed to return the closest baked point. If that's indeed the intended behavior then the "weirdly discrete" nature of the results is correct (as the baked points are discrete). However, even in such case this:

at (0.2, 49.6, 0) => (0, 49.67346, 0)
at (0.2, 49.7, 0) => (0, 49.78468, 0)

seems to be a bug as (0, 49.67346, 0) is indeed closer to (0.2, 49.7, 0) than (0, 49.78468, 0) is. Approximately:

|(0.2, 49.7, 0) - (0, 49.67346, 0)| = 0.201753
|(0.2, 49.7, 0) - (0, 49.78468, 0)| = 0.217188

[Skwint]

hmmm ... well, the code definitely tries to interpolate between the baked points, and I'm pretty sure it used to succeed because I used to get smoother surfaces, but fair enough.
I think I'm going to end up writing my own version instead, but since these curves are followed by path finders (I think?) doesn't this make them stutter?

[CousCous4]

@kleonc - I think throughout 3.x get_closest_point() found the closest point by using interpolation between baked points which seems like intended behaviour?

I agree with @Skwint that using it resulted in a smooth output in 3.x (and possibly early 4.0 betas).

On a similar vein I think sample_baked() used to be called interpolate_baked() in 3.x, and the naming has changed for 4.0. In my opinion the name interpolate_baked() more closely represented the documentation description, although I'm sure this was changed for a reason!

Maybe there could be a sample_baked() and an interpolate_baked() function with outputs for baked points and interpolations respectively?

Related to this, in Beta 7 I also came across a bug with get_closest_offset() that seems to have just been introduced where the offset it is returning seems wrong. Steps to reproduce in a _ready():

var curve = Curve3D.new()
curve.add_point(Vector3(0,0,0))
curve.add_point(Vector3(4,0,0))
print(curve.get_closest_offset(Vector3(2,0,0)))
#Prints 0.20000000298023 when I think it should print 2.0 exactly

Not sure if I should open another bug report for this? (Apologies it's my first post).

@xiongyaohua Thanks for your work on Curves/Paths, I have been following along eagerly awaiting the changes!

[Skwint]

I think the offset is the fractional distance along the curve, starting at 0.0 and ending at 1.0, rather than the absolute distance in space, but in that case it should print 0.5 in your case. That could be the same bug as this.

[CousCous4]

Ah good point! The docs aren't too clear on it, but I think that in 3.x it was the equivalent of the PathFollow offset not the unit_offset (which is now called progress and unit_progress in 4.x). Given something doesn't seem right with get_closest_offset(), do you think it needs its own issue report added?

[Skwint]

I'd hold off until this one is merged and then see, but it doesn't really hurt. If you do raise it, link this one to make the devs life a bit easier.

[xiongyaohua]

@Skwint I don't expect it to "step" in chunks of over 0.5. There's something weird going on

@CousCous4 Prints 0.20000000298023 when I think it should print 2.0 exactly

Hi, I think these two problems are caused by my PR which introduce a new baking method. There is an subtile behaviour change. Bake interval "0.2" no longer produce points exactly "0.2" apart, but more or less "0.2" apart. This change is for simpler code and better baking performance. I am also quite new to godot code so I don't realize it create problems for other parts. Sorry.

I think the proper fix is instead of finding the closest baked point, these two find_closest_* functions should find the geometrically closest point on the baked line segments. Then the result will be baking method independent(at least for straight lines). I am a bit occupied recently, so I am going to do that on this weekend.

Thanks for your work on Curves/Paths, I have been following along eagerly awaiting the changes

Thanks for your appreciation 😄.

@kleonc seems to be a bug as (0, 49.67346, 0) is indeed closer to (0.2, 49.7, 0) than (0, 49.78468, 0) is

That is strange. I suspect it is an old bug in the get_closest_point, as the code is not touched by my PR. I will investigate on weekend.

[xiongyaohua]

Found some time, and fix the problem(again). Hope I get it right this time.

Turns out the original get_closest_* assumes the distance between the baked points are always the same, which is no longer true.

After this fix, the test code

func _ready():
	var frog : Curve3D = Curve3D.new()
	frog.add_point(Vector3(0.0, 0.0, 0.0), Vector3(0.0, -10.0, 0.0), Vector3(0.0, 10.0, 0.0))
	frog.add_point(Vector3(0.0, 100.0, 0.0), Vector3(0.0, -10.0, 0.0), Vector3(0.0, 10.0, 0.0))
	
	var pos = Vector3(0.2, 0.0, 0.0)
	
	for y in range(0.0, 100.0):
		pos.y = y
		var found = frog.get_closest_point(pos)
		print("at ", y, " => ", found)
	
	print("-------")
	var curve = Curve3D.new()
	curve.add_point(Vector3(0,0,0))
	curve.add_point(Vector3(4,0,0))
	for y in range(0.0, 4.0):
		print("at ", y, " => ", curve.get_closest_offset(Vector3(y,0,0)))

produces this result

at 96 => (0, 96, 0)
at 97 => (0, 97, 0)
at 98 => (0, 98, 0)
at 99 => (0, 99, 0)
-------
at 0 => 0
at 1 => 1
at 2 => 2
at 3 => 3

[kleonc]

hmmm ... well, the code definitely tries to interpolate between the baked points, and I'm pretty sure it used to succeed because I used to get smoother surfaces, but fair enough.

@kleonc - I think throughout 3.x get_closest_point() found the closest point by using interpolation between baked points which seems like intended behaviour?

@Skwint @CousCous4 Actually after rethinking I guess it's probably get_closest_point()'s docs which are simply unclear/misleading. I suspect by "the closest baked point" the author meant any point on the baked polyline (polyline composed from the baked points), not only the actual baked points.
That's just a guess but I don't think it'd actually make any sense for get_closest_point() to return baked points only, I don't see how having just the position of the closest baked point could be useful. If anything, one would rather want to get the index of such closest baked point instead as it would allow to obtain neighbor baked points, or in/out control points. Moreover, if it were meant to return baked points then it should rather be called get_closest_baked_point() instead.

I think the proper fix is instead of finding the closest baked point, these two find_closest_* functions should find the geometrically closest point on the baked line segments.

@xiongyaohua So I agree with that. The docs needs to be clarified of course (it's fine in your PR).
Have you been backporting your changes/PRs to 3.x? Cause if not then it would probably be a good idea to potentially just clarify the docs in there as well in a dedicated PR.

On a similar vein I think sample_baked() used to be called interpolate_baked() in 3.x, and the naming has changed for 4.0. In my opinion the name interpolate_baked() more closely represented the documentation description, although I'm sure this was changed for a reason!

For reference it was changed in #63394.

[CousCous4]

Completely agree with your points @kleonc and @xiongyaohua !

While we are on the subject - I think another really useful function for a curve would be something like "get_tangent_at_offset", or equivalently "get_direction_at_offset", which returns the mathematical tangent of the curve at a given offset (or an approximation of it if that's not possible). I imagine that this is already calculated somewhere as the PathFollow inherits the rotation of the curve, and I think when we have both the position and tangent (i.e. direction) of the path at a given offset I think using the curve on its own without a PathFollow becomes quite powerful.

[xiongyaohua]

@kleonc Actually after rethinking I guess it's probably get_closest_point()'s docs which are simply unclear/misleading. I suspect by "the closest baked point" the author meant any point on the baked polyline (polyline composed from the baked points), not only the actual baked points.

Yes, the old doc was misleading. These methods actually find point on baked polyline. So I updated the doc in my PR.

@kleonc Have you been backporting your changes/PRs to 3.x? Cause if not then it would probably be a good idea to potentially just clarify the docs in there as well in a dedicated PR.

Not yet. I think the backporting needs to wait for now, because the Curve refactoring is still in progress. After the release of 4.0 I'll look into backport if there is enough demand.

@CousCous4 I think another really useful function for a curve would be something like "get_tangent_at_offset", or equivalently "get_direction_at_offset", which returns the mathematical tangent of the curve at a given offset (or an approximation of it if that's not possible). I imagine that this is already calculated somewhere as the PathFollow inherits the rotation of the curve, and I think when we have both the position and tangent (i.e. direction) of the path at a given offset I think using the curve on its own without a PathFollow becomes quite powerful.

That is exactly why I started the whole refactoring effort. Now there is a method called sample_backed_with_rotation() on both Curve2D and Curve3D. Give it an offset alone the curve, it returns the local transform frame at that point, including position, tangent vector, up vector, side vector. See #64212

[Zireael07]

I think backporting should wait until the refactor is finished