ecurtiss / CatRom

Creates Catmull-Rom splines for Roblox
https://ecurtiss.github.io/CatRom/
Mozilla Public License 2.0
45 stars 11 forks source link

Add method to query for nearest point on spline to a point #14

Open ecurtiss opened 2 months ago

ecurtiss commented 2 months ago

This ends up being a minimization problem on a 6th-degree polynomial. If the user is tracking the nearest point over time, then starting the minimization from a nearby reference point could give quick convergence with a basic algorithm. Otherwise, we could find all roots of the derivative in [0, 1] using http://www.cemyuksel.com/research/polynomials/.

ecurtiss commented 2 months ago

On second thought, the distance function is actually discontinuous when you take the query point as a parameter. Hence, trying a root-find at the previous time could give you the next closest point, but it is not guaranteed.

Here's an idea for doing a nearest point query that considers all segments:

  1. Broad phase: For each segment, compute the smallest distance and largest distance from the segment's bounding box to the query point. This gives an upper bound and a lower bound on the distance from the segment to the query point. Discard any segments whose lower bound is greater than the smallest upper bound. Lastly, cache the bounding boxes.
  2. Narrow phase: For every segment that survives the broad phase, do the root find.

Thoughts: