Numerical instability issues with bezier curves

[velipso]

I've included a failure test case in the demo, here:

polybool/demo/demo.html

Line 117 in 3ee7c44

// this one fails due to numerical instability... it will detect an intersection between line

This will fail due to numerical instability.

I'm not sure exactly how to fix it... the solveCubic function is returning a T value very close to 1, but not exactly 1 (and not within striking distance of the epsilon value), so it ends up thinking there is an intersection between a curve and a line, but in reality they just share an endpoint.

I think the solveCubic function needs to take the epsilon value into account in a smarter way, or perhaps rewritten entirely.

[velipso]

I've changed things, but now there is some silliness here:

polybool/src/Segment.ts

Lines 464 to 476 in 80bfb19

	if (force) {
	// TODO: what?!?! lol this is so wrong
	for (const t of [
	...this.geo.solveCubic(0, B, C, D),
	...this.geo.solveCubic(0, 0, C, D),
	0,
	]) {
	const ts = this.geo.snap01(t);
	if (ts >= 0 && ts <= 1) {
	return this.point(t)[1];
	}
	}
	}

[velipso]

I fixed some of this, but now the only issue I notice is when two curves intersection point just barely touches

[Fribur]

I noticed you use absolute epsilon equality test throughout polybool if (Abs(x – y) <= EPSILON). That’s fine when numbers are between -1 and 1 and epsilon not much smaller than 1*10^-6 for 32bit float, but will fail once coordinates get larger, and thereby the delta to the next/previous representable number gets larger than epsilon. Polybool could more robustly deal simultaneously with small and large coordinates by implementing the combination of an absolute and relative test (where epsilon is scaled by largest coordinate): if (Abs(x - y) <= absTol * Max(1.0f, relTol/absTol * Max(Abs(x), Abs(y)))) . More details here https://realtimecollisiondetection.net/blog/?p=89 This might also resolve this bezier bug, but have to look into this in a bit more detail.

[Fribur]

As for the specific problem of solving the cubic equation: freetype (de-facto standard for rendering fonts) is using Newton approximation as the numerical approach to find the roots suffers from overflow/under flow issues. https://github.com/freetype/freetype/blob/6d4977d66033e7841219bdc2b686a97552091ade/src/sdf/ftsdf.c#L1586 In fact they ditched rendering from Beziers entirely, as splitting the Beziers into lines (with a definable max deviation from the curve) turned out to be much faster overall and avoids all of this complicated error prone Bezier math. In case you find C# easier to read, here my implementation for finding the minimum distance to a cubic Beziers using Newton iteration FYI https://github.com/Fribur/TextMeshDOTS/blob/54a3c2ed79210b975b8a68030c09d9f0ae4a571a/Internal/Harfbuzz/Bitmap/SDF.cs#L465

[velipso]

Very interesting, thanks for sharing!

It's been surprising that most of the complexity I've run into with this project is around floating point -- the core algorithm works great and is simple in essence, but detecting the conditions using inexact numbers is the difficult part that I still struggle with.