On the face of it, it might just sound like the inverse of the Get Location at Distance Along Spline node, but it requires some pretty complex math (and from what i gather can only give an approximation). But this node is something that would be incredibly helpful when dealing with splines.
You can get fairly accurate distance by dividing spline segments into lots of very small straight lines and therefore, the distance = number of lines * single line length.
lol - I was totally looking for this today as well!
Upvote++
I agree that this would be very useful.
I believe I was able to write a function(a pure one even) in blueprint to achieve this. I have included a screenshot of my graph. I have tested this a few times and it seems to work. If anyone finds that this doesn’t work please say so.
6 Likes
Thanks !! Exactly what I needed and it work great !
1 Like
Oh seem like that function don’t work at all as expected cause of this Unreal Engine Issues and Bug Tracker (UE-27979)
According to the issue this has been only affecting 4.10 and 4.11. Also its closed now due to not being able to reproduce.
Here’s the same thing (more or less) in C++ with a consideration for having the location at the end point.
UFUNCTION(BlueprintCallable, BlueprintPure, Category = "Spline")
static float UUtilities::FindDistanceAlongSplineClosestToLocation(const USplineComponent* Spline, const FVector& Location)
{
float InputKey = Spline->FindInputKeyClosestToWorldLocation(Location);
int32 SplinePoint = FMath::TruncToInt(InputKey);
float SplinePointDistance = Spline->GetDistanceAlongSplineAtSplinePoint(SplinePoint);
if (SplinePoint < Spline->GetNumberOfSplinePoints())
{
float NextPointDistance = Spline->GetDistanceAlongSplineAtSplinePoint(SplinePoint + 1);
return FMath::Lerp(SplinePointDistance, NextPointDistance, InputKey - SplinePoint);
}
else
{
float PrevPointDistance = Spline->GetDistanceAlongSplineAtSplinePoint(SplinePoint - 1);
return FMath::Lerp(PrevPointDistance, SplinePointDistance, SplinePoint - InputKey);
}
}
2 Likes
Aakrasia solution is more accurate than roushenzo. Sadly still not perfect due to the tangents (distance is not linear), but it is a good approach. Maybe someone who knows mathematics could perfectionate it :-/. Are splines a bezier curve? Maybe I could investigate it. If I can make one perfect I will post it here.
bump?..
I’m using this one:
float ASomething::GetDistanceAlongSplineAtWorldLocation(const USplineComponent* InSpline, const FVector InWorldLocation)
{
if (!InSpline)
return 0.f;
auto InputKeyFloat = InSpline->FindInputKeyClosestToWorldLocation(InWorldLocation);
auto InputKey = FMath::TruncToInt(InputKeyFloat);
auto A = InSpline->GetDistanceAlongSplineAtSplinePoint(InputKey);
auto B = InSpline->GetDistanceAlongSplineAtSplinePoint(InputKey + 1);
return A + ((B - A) * (InputKeyFloat - InputKey));
}
Seems to work pretty well.
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.
float SplineUtils::GetApproxDistanceClosestToWorldLocation(FVector Pos_WS, const USplineComponent& Spline)
{
const auto TargetInputKey = Spline.FindInputKeyClosestToWorldLocation(Pos_WS);
const auto PointIdx = static_cast<int32>(TargetInputKey);
auto LowDistBound_cm = Spline.GetDistanceAlongSplineAtSplinePoint(PointIdx);
auto HighDistBound_cm = Spline.GetDistanceAlongSplineAtSplinePoint(PointIdx + 1);
auto MiddleDistEstimate_cm = (LowDistBound_cm + HighDistBound_cm) * 0.5f;
const auto& DistanceToInputMapping = Spline.SplineCurves.ReparamTable;
for (auto IterCount = 0; IterCount < 10; ++IterCount)
{
const auto MiddleInputKey = DistanceToInputMapping.Eval(MiddleDistEstimate_cm);
if (TargetInputKey < MiddleInputKey) {
HighDistBound_cm = MiddleDistEstimate_cm;
} else {
LowDistBound_cm = MiddleDistEstimate_cm;
}
MiddleDistEstimate_cm = (LowDistBound_cm + HighDistBound_cm) * 0.5f;
}
return MiddleDistEstimate_cm;
}
1 Like
I’ve created a pull request for this feature:
https://github.com/EpicGames/UnrealEngine/pull/6646
It adds a GetDistanceAtSplineInputKey GetDistanceAlongSplineAtSplineInputKey method to USplineComponent.
The change relies on the ReparamTable assuming a linear relationship between the distance and the input key between consecutive entries. Meaning if distance is 5 at input key 0.1, and distance is 25 at input key 0.2, then distance at input key 0.15 is 15.
So this should be as accurate as the inverse operation(s) (e.g. GetInputKeyAtDistanceAlongSpline, GetLocationAtDistanceAlongSpline), without the need to iterate.
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).
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.
Why is everyone writing so complicated? And many people write wrong, in fact, this need only one sentence of code.