godot: Curve3D get_closest_point broken

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

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

@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 https://github.com/godotengine/godot/pull/64212

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.

@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.

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.

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?

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?

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.