revarbat / BOSL

The Belfry OpenScad Library - A library of tools, shapes, and helpers to make OpenScad easier to use.
https://github.com/revarbat/BOSL/wiki
BSD 2-Clause "Simplified" License
557 stars 62 forks source link

[BUG] bezier_segment_closest_point() fails #50

Closed RonaldoCMP closed 5 years ago

RonaldoCMP commented 5 years ago

Consider the 2D Bézier curve with the control points:

p = [[3.98743, 5.29979], [-8.21663, -2.76544], [-5.4184, -5.00586], [8.26971, -0.0435725]];

Evaluating its closest point to the origin with function bezier_segment_closest_point() from beziers.scad, we find:

umin = bezier_segment_closest_point(p, [0,0], max_err=0.01); distmin = norm(bez_point(p, umin)); echo(umin=umin); echo(distmin=distmin); // ECHO: umin = 0.765625 // ECHO: distmin = 2.41428

However, if we evaluate the point at u = 0.183874 of the same curve and compute its distance to the origin, we find:

dist2 = norm(bez_point(p, 0.183874)); echo(dist2=dist2); // ECHO: dist2 = 1.91359

a distance value 80% of the computed by function bezier_segment_closest_point(). Reducing max_err to 1e-6 doesn't change the results significantly.

I confess that I have not understood the ideas behind that function code. My own version of that function uses Bézier subdivision to recursively find the closest point. It calls the Bézier subdivision function once for each call. Bézier subdivision has a small overhead over a Bézier point evaluation but it may be faster than the three point evaluations the function bezier_segment_closest_point() requires. So, besides, I would expect a faster method using subdivision.

revarbat commented 5 years ago

Rewrote algorithm to search all possible minima. Fixed in 5bbbbd4a76ba3080746d93c8b7de32dbab703461