Originally posted by DanielKrakowiak
View Post
Announcement
Collapse
No announcement yet.
Get Distance at Location Along Spline.
Collapse
X

Originally posted by Syed View PostIncorrect. I have used my code in production and it works fine in all cases. And it is not complex either, just divide you spline small enough and then you can 'merge' it for distance that you wanted.
However, dividing the whole segment upfront into n straight pieces seems unnecessary, as that gives you linear complexity where logarithmic is possible. To explain: if your segment has 10 m and you want 1 m pieces for your approximation  you divide it into 10 pieces. But if you want to double the precision of your approximation by using 0.5 m piece, you need to divide into 20 pieces. Twice the amount of calculations/splinesampling seemingly.
Binary search achieves the same, also diving the segment into straight pieces. But doubling the precision requires only one more iteration, thus logarithmic complexity. That is especially important for long splines with long segments.
There is a problem I found however  you can't use a strict binary search  dividing a segment into halves each time. You have to divide with some extra margin  to account for the curvature of the segment. Otherwise the searched position may end up just next to your division point, but on the wrong side. And then you are running other iterations on the wrong piece of the segment. Adding something like 1530% of margin (inflating the half you want to keep processing) solves the problem for most splines. And this really requires maybe an extra one or two iterations, so the performance is still great and complexity stays logarithmic.
There is also another source of slow down when sampling splines  finding the segmentidx to further analyze (FindInputKeyClosestToWorldLocation). UE does that using a linear search from the beginning of the spline. I also advise to replace that with binary search where possible (for slightly curved splines).
Comment

Originally posted by DanielKrakowiak View Post
However, dividing the whole segment upfront into n straight pieces seems unnecessary, as that gives you linear complexity where logarithmic is possible. To explain: if your segment has 10 m and you want 1 m pieces for your approximation  you divide it into 10 pieces. But if you want to double the precision of your approximation by using 0.5 m piece, you need to divide into 20 pieces. Twice the amount of calculations/splinesampling seemingly.
Comment

Originally posted by Syed View PostI agree that the code I used may not be very fast, but the execution time is almost negligible. Plus if the calculation does take too long to finish, then just do it in separate thread and signal the main thread when it finished (and it will never exceed 12 seconds so far in my case). For a curve that is 2km length. dividing it into 1cm is still not taking long to finish. And also, do it once and cache for subsequent uses. Better yet, save them into external files and the curve will not be needed to calculate unless there are changes.
Comment
Comment