GDScript::Geometry2D.segment_intersects_segment() returns null on valid intersection point

[just-like-that]

Tested versions

v4.3.dev1.official [9d1cbab]

System information

Godot v4.3.dev1 - Windows 10.0.19045 - GLES3 (Compatibility) - Quadro K1000M () - Intel(R) Core(TM) i7-3740QM CPU @ 2.70GHz (8 Threads)

Issue description

Geometry2D.segment_intersects_segment() returns null as a result although a valid intersection point exists.

1st segment has a starting point exactly residing on 2nd segment.
2nd segment is vertical.

Swapping from with to hence exchanging the start point with the end point leads to correct result.

I expect Geometry2D.segment_intersects_segment() to always return the same result regardless of the order of start and end points of segments given.

Steps to reproduce

Geometry2D.segment_intersects_segment(from_a, to_a, from_b, to_b) returns null for
var from_a := Vector2(585, 95)
var to_a := Vector2(581, 98)
var from_b := Vector2(585, 105)
var to_b := Vector2(585, 45)

Correct result is (585, 95).

Proof via swapping from_b with to_b:
Geometry2D.segment_intersects_segment(from_a, to_a, to_b, from_b) returns (585, 95).

Minimal reproduction project (MRP)

segment_bug.zip

[just-like-that]

# A candidate to produce an error is the calculation of ABpos in the function Geometry2D.segment_intersects_segment().
# Maybe this produces a very little negative number in the original source code.
# In my tests with the source found from github translated to GDScript it is working.
# For me it looks like a floating point error, which comes to life in C and not in gdscript.

[AThousandShips]

Sounds like a precision error, see:

• Geometry2D.is_point_in_polygon() give inconsistent result on exactly boundary points #81042

[just-like-that]

Sounds like a precision error, see:

* [Geometry2D.is_point_in_polygon() give inconsistent result on exactly boundary points #81042](https://github.com/godotengine/godot/issues/81042)

Good to kill two birds with one stone! ;)

Are there any plans to fix this?
Or do we have to wait before double precision is being used in the engine?

[AThousandShips]

Double precision is something you can enable, this isn't solved yet and it was just a guess that this is because of precision, my suspicion is that this should be a documentation thing unless something is wrong in the code, I suspect it's not though and it's just a reality of the code

Can you check if line_intersects_line works correctly? And what it yields?

[just-like-that]

From my past experience line_intersects_line() used to work!

Here are the results:
xp-1::from_a= (585, 95) to_a= (581, 98) from_b= (585, 105) to_b= (585, 45) xp= (585, 95)
xp-2::from_a= (585, 95) to_a= (581, 98) from_b= (585, 45) to_b= (585, 105) xp= (585, 95)
xp-3::from_a= (581, 98) to_a= (585, 95) from_b= (585, 105) to_b= (585, 45) xp= (585, 95)
xp-4::from_a= (581, 98) to_a= (585, 95) from_b= (585, 45) to_b= (585, 105) xp= (585, 95)

Code used:

func test_line_intersects_line(from_a: Vector2, to_a: Vector2, from_b: Vector2, to_b: Vector2) -> void:
	print_debug()
	prints("xp-1::from_a= %s  to_a= %s  from_b= %s  to_b= %s  xp= %s"
			% [from_a, to_a, from_b, to_b, Geometry2D.line_intersects_line(from_a, from_a.direction_to(to_a), from_b, from_b.direction_to(to_b))])
	prints("xp-2::from_a= %s  to_a= %s  from_b= %s  to_b= %s  xp= %s"
			% [from_a, to_a, to_b, from_b, Geometry2D.line_intersects_line(from_a, from_a.direction_to(to_a), to_b, to_b.direction_to(from_b))])

	prints("xp-3::from_a= %s  to_a= %s  from_b= %s  to_b= %s  xp= %s"
			% [to_a, from_a, from_b, to_b, Geometry2D.line_intersects_line(to_a, to_a.direction_to(from_a), from_b, from_b.direction_to(to_b))])
	prints("xp-4::from_a= %s  to_a= %s  from_b= %s  to_b= %s  xp= %s"
			% [to_a, from_a, to_b, from_b, Geometry2D.line_intersects_line(to_a, to_a.direction_to(from_a), to_b, to_b.direction_to(from_b))])

	print()
###

[just-like-that]

I rely on Geometry2D.segment_intersects_segment(from_a, to_a, from_b, to_b) and can't use line_intersects_line() in my project.
So a fix is highly welcome!

[AThousandShips]

This is likely the code that fails in this case:

real_t ABpos = D.x + (C.x - D.x) * D.y / (D.y - C.y);

// Fail if segment C-D crosses line A-B outside of segment A-B.
if ((ABpos < 0) || (ABpos > 1)) {
	return false;
}

Due to precision errors, but unsure, it's possible that a fix can be made, but unable to test or verify any code right now

[just-like-that]

Double precision is something you can enable

Is there another way then compiling the source?

Are there some official builds provided which have this activated already?

[AThousandShips]

No, not currently, see:

• Default float=64 to be on (double precision emulation) godot-proposals#5610

[just-like-that]

Another combination:
from_a = Vector2(605, 371)
to_a = Vector2(601, 368)
from_b = Vector2(605, 345)
to_b = Vector2(605, 605)

leads to:
xp-1::from_a= (605, 371) to_a= (601, 368) from_b= (605, 345) to_b= (605, 605) xp= (605, 371)
xp-2::from_a= (605, 371) to_a= (601, 368) from_b= (605, 605) to_b= (605, 345) xp= (605, 371)
xp-3::from_a= (601, 368) to_a= (605, 371) from_b= (605, 345) to_b= (605, 605) xp= < null >
xp-4::from_a= (601, 368) to_a= (605, 371) from_b= (605, 605) to_b= (605, 345) xp= (605, 371)

And the translated GDScript code results in:

ABpos= -0.00000009536743
xp-1::from_a= (605, 371) to_a= (601, 368) from_b= (605, 345) to_b= (605, 605) xp= false result= [(0, 0)]
ABpos= -0.00000009536743
xp-2::from_a= (605, 371) to_a= (601, 368) from_b= (605, 605) to_b= (605, 345) xp= false result= [(0, 0)]
ABpos= 1.00000009536743
xp-3::from_a= (601, 368) to_a= (605, 371) from_b= (605, 345) to_b= (605, 605) xp= false result= [(0, 0)]
ABpos= 1.00000009536743
xp-4::from_a= (601, 368) to_a= (605, 371) from_b= (605, 605) to_b= (605, 345) xp= false result= [(0, 0)]

[just-like-that]

As it looks like - see above comment - field ABpos caries values which are close to the bounds check.
In this case a possible fix would look like this:

		// Fail if segment C-D crosses line A-B outside of segment A-B.
		if ((ABpos < (real_t)-CMP_EPSILON) || (ABpos > 1 + (real_t)CMP_EPSILON)) {
			return false;
		}

[AThousandShips]

This would introduce some errors in the other direction, which would need to be weighed against this case

[just-like-that]

I understood that's what this proposal is all about?!
godotengine/godot-proposals#3565

[AThousandShips]

That's unrelated, just about exposing it to GDScript, this wouldn't affect the c++ code

[just-like-that]

That's unrelated, just about exposing it to GDScript, this wouldn't affect the c++ code

I know. What I mean is do not compare floats with == or != and comparison operators like < or > also need precision tolerance ...