You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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/.
The text was updated successfully, but these errors were encountered:
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:
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.
Narrow phase: For every segment that survives the broad phase, do the root find.
Thoughts:
Since we can cache the bounding boxes, it is probably worth our time to write a tighter bounding box algorithm.
We could still start with a root-find at the previous closest time, as this would give an upper bound on the distance. We could use this for the broad phase if it's smaller than the smallest upper bound from the bounding boxes.
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/.
The text was updated successfully, but these errors were encountered: