Announcement

Collapse
No announcement yet.

Get Distance at Location Along Spline.

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

    #16
    Originally posted by DanielKrakowiak View Post
    All above answers assume spline segments are straight lines which can lead to meters of error on curved splines. I suggest a binary search instead where any precision can be achieved depending on the number of iterations.
    Incorrect. 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.

    Comment


      #17
      Originally posted by Syed View Post
      Incorrect. 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.
      You haven't provided the details of your solution. So I commented on the provided code samples. Your solution should work for curved splines.

      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/spline-sampling 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 15-30% 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 segment-idx 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


        #18
        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/spline-sampling seemingly.
        I 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 1-2 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


          #19
          Originally posted by Syed View Post
          I 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 1-2 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.
          Depends on your case. I run it on hundreds of virtual cars, each sampling multiple long splines multiple times per second. All the code is running on multiple threads already, but is still far from free. Initially it was crazy expensive. I don't force anyone to optimize, but it's good to understand the cost.

          Comment


            #20
            Why is everyone writing so complicated? And many people write wrong, in fact, this need only one sentence of code.
            Last edited by 张良的狗链; 03-10-2020, 11:38 PM.

            Comment


              #21
              You have to upload an image to the internet, there's an upload option if you use the image button. We can't see a local file.

              Comment

              Working...
              X