Converting a Spline InputKey to a Distance efficiently?

Development Programming & Scripting
1

So, the situation I’m in is that I need to figure out how far apart two points on a spline are. (As in, following the spline.)

The obvious way is to get the distances each point are from the spline’s start, and subtract one from the other.

However, I don’t see an obvious way to pull this data from the SplineComponent. I can:

  • Use a Distance to get an InputKey (GetInputKeyAtDistanceAlongSpline)

  • Use a Distance to get a Location (GetLocationAtDistanceAlongSpline)

  • Use an InputKey to get a Location (GetLocationAtSplineInputKey)

  • Use a Location to get an InputKey (FindInputKeyClosestToWorldLocation)

But there doesn’t seem to be any way to convert an InputKey back into a Distance. If there was, I could take the two locations, get their input keys, use the input keys to get two distances, and then subtract one distance from the other, but that key step of converting an InputKey to a distance is missing… which is weird, since it seems to me that InputKeys and Distances do essentially the same thing, so there ought to be a simple conversion between the two.

Does anyone know how to perform this conversion (in a non brute-forcey, accurate) way?

2

As far as I know, there is no out-of-box function performing that.

Fortunately, both InputKey and Distance of USplineComponent’s ReparamTable are sorted ascending.

By utilizing this we can provide a function that converts input key to distance.

Snippet is following:

template <class TElement, class TAllocator, class TPredicate>
static int UpperBound(const TArray<TElement, TAllocator>& arr, TPredicate pred)
{
	// http://en.cppreference.com/w/cpp/algorithm/upper_bound

	int32 first = 0;
	auto count = arr.Num();
	while (count > 0)
	{
		auto step = count / 2;
		auto it = first + step;
		if (!pred(arr[it]))
		{
			first = ++it;
			count -= step + 1;
		}
		else count = step;
	}

	return first;
}

float SplineConvertInputKeyToDistance(USplineComponent* spline, float inputKey)
{
	// ReparamTable maps distance (InVal) to inputKey (OutVal)
	// Fortunately, InVal and OutVal are already guaranteed to be sorted in ascending order.
    // So we can do binary search ('upper_bound' to be precise) to find 
    // nearest smallest entry by OutVal (input-key) that is next to the input key we want.
    // When we lerp it's InVal (distance) with previous entry's one
    // it would be meaningful approximation of distance we are looking to find.

	auto& pts = spline->SplineCurves.ReparamTable.Points;

	int upperBound = UpperBound(pts, [inputKey](const FInterpCurvePointFloat& p)
	{
		return inputKey < p.OutVal;
	});

	if (upperBound == pts.Num())
		return pts.Last().InVal;

	if (upperBound == 0)
		return pts[0].InVal;

	auto& p0 = pts[upperBound - 1];
	auto& p1 = pts[upperBound];

	float k0 = p0.OutVal;
	float k1 = p1.OutVal;

	float d0 = p0.InVal;
	float d1 = p1.InVal;

	float kt = (inputKey - k0) / (k1 - k0);
	float d = FMath::Lerp(d0, d1, kt);

	return d;
}

This code’s complexity is n*log(n) so it would be quite effecient. And accuracy would be also acceptable for most cases. (Distance to InputKey was interpolated at the first time so it would not be a problem)

3

How would this be translated to BPs?

4

(http://i.imgur.com/CDCUUxR.png)

not shure if this is the same (performancewise)… but it kinda does the same.

5

上面解决方法是不太正确的，我已经完美解决了，只要读懂底层，就很简单。

6

Here is my implementation, you can get a fairly accurate result, but I must say “it’s not that efficiency”, because the FSplineCurves::GetSegmentLength method used “Legendre-Gauss quadrature” for solving the integral equation. If you seek the lowest time complexity, the simplest way is "pre-bake“ the distance into a “param to distance” array, then sample it using linear lerp.

float GetDistanceAlongSpline(float InputKey, USplineComponent* InSplineComponent)
{
	float Frac, Int;
	Frac = FMath::Modf(InputKey, &Int);
	int Index = (int32)Int;

	int MaxExclusiveInputKey = (float)(InSplineComponent->IsClosedLoop() ? InSplineComponent->GetNumberOfSplinePoints() : InSplineComponent->GetNumberOfSplinePoints() - 1);
	check(Index <= MaxExclusiveInputKey);
	if(Index == MaxExclusiveInputKey)
	{
		check(Frac < 0.0001f);
		Index = MaxExclusiveInputKey - 1;
		Frac = 1.0f;
	}

	return InSplineComponent->GetDistanceAlongSplineAtSplinePoint(Index)
		+ InSplineComponent->SplineCurves.GetSegmentLength(Index, Frac, InSplineComponent->IsClosedLoop(), InSplineComponent->GetComponentTransform().GetScale3D());
}