# Getting a point on a bezier curve given distance

I’m working on a ledge-hanging system that uses bezier curves to define the edge that can be hung from/shimmied along.

I discovered that one cannot simply get the next point on the edge by increasing the parameter “time” as you’ll get points that are spaced unevenly.

I found this primer on Bezier curves that told me I would have to compile a Look Up Table of time-for-distance values in order to move along the curve by a specific amount.

I do that by looping through the curve by time and adding up the distance between the current and previous points to get the distance of each point in the table.

Like So

``````private BezierTableData[] _LUT;
public BezierTableData[] LookUpTable
{
get
{
if(dirty || _LUT == null)
{
int segResolution = 50;
int tableSize = close ? segResolution * points.Length : segResolution * points.Length - 1;
_LUT = new BezierTableData[tableSize + 1]; //wipe the array
float totalDist = 0f;
float totalTime = 0f;
int luP = 0;

for(; totalTime < 1.0f; totalTime += 1.0f/tableSize) //loop through the entire curve in equal steps of time
{
Vector3 point = this.GetPointAt(totalTime); // get point at this time

if(totalTime != 0) //if this is not the first loop
{
totalDist += Vector3.Distance(point, _LUT[luP - 1].pos); //add the distance between this and the last point.
}

_LUT[luP] = new BezierTableData(point, totalTime, totalDist); //set the look up point.
luP++; //increment total look up point index
}
dirty = false;
}
return (BezierTableData[])_LUT.Clone(); // return a clone of the table so that we can't mess with it.
}
}
``````

So I figure now to find a point by distance, I can just find the two Look Up Points that have a greater and smaller distance, respectively, and return a point on the vector between those two points and it would be close enough.

Like this I thought.

``````public Vector3 GetPointByDist(BezierCurve ledge, float dist)
{
BezierTableData[] table = ledge.LookUpTable;
Vector3 point = Vector3.zero;

if (dist > ledge.length) //handle closed loops
{
if (ledge.close)
{
dist -= ledge.length;
}
else
{
dist = ledge.length;
}
}

for (int i = 0; i < table.Length - 1; i++)
{
if (table[i + 1].d >= dist && table[i].d <= dist) //find what two points we are between
{
dist -= table[i].d; //get just the distance from the next point.
Vector3 btween = table[i + 1].pos - table[i].pos;
point = table[i + 1].pos + (btween * dist);
}
}

return point;
}
``````

To move along the curve, I thought I would simply find the distance of the current position on the curve, and then add the amount of distance I wish to move, get that point by the distance, and move to it.

Current distance on the curve

`````` public float GetDistByPoint(BezierCurve ledge, Vector3 origin) // get the distance of a point on the curve
{
BezierTableData[] table = ledge.LookUpTable;

float dist = 0f; //how far this point is on the curve in units.
float closestDist = 999f;
float bcTime = 0;

//look through our LUT to find the points we are between
for (int i = 0; i < table.Length; i++)
{
float pointDist = Vector3.Distance(origin, table[i].pos); //distance between the origin and this table point

if (pointDist < closestDist) //if this table point is closest.
{
bcTime = table[i].t; //grab the time of the nearest table point
closestDist = pointDist; // set the closest distance
dist = table[i].d; // grab the closest table point
//tablePointDist = table[i].d;
}
}

float interval = (1.0f / table.Length);

//do a binary search to find a more exact point
for (int i = 0; i < 10; i++) // max of 10 loops cause aint nobody got the time for that!
{
Vector3 p1 = ledge.GetPointAt(bcTime + (interval / 2.0f)); //grab a point on either side of the table point and get the distance to the origin
Vector3 p2 = ledge.GetPointAt(bcTime - (interval / 2.0f));
float p1Dist = Vector3.Distance(origin, p1);
float p2Dist = Vector3.Distance(origin, p2);

if (p1Dist < closestDist) //if we have found a point that is closer to the origin, we keep it.
{
bcTime += (interval / 2.0f); //adjust the time of the point we are getting.
closestDist = p1Dist; // set the distance to beat.
dist += p1Dist; // add the distance to this new point
//Debug.Log("Getting closer");
}
else if (p2Dist < closestDist)
{
bcTime -= (interval / 2.0f);
closestDist = p2Dist;
dist += p2Dist;
//Debug.Log("Getting closer");
}

if (p1Dist > closestDist || p2Dist > closestDist) // if either point has overshot the origin, we need to shrink our interval.
{
if (interval > .0001f) //if our interval isn't small enough
{
interval = (interval / 2.0f);
}
else //interval is really really small.
{
//there's our point!
//Debug.Log("Got Point from binary search");
break; // break out of the loop because we are done
}
}
}

return dist;
}
``````

``````cur_dist = GetDistByPoint(bc, closestPoint);

float moveDist = (moveSpeed * inpX) * Time.deltaTime/10; //how far we should move in distance
Vector3 nextPoint = GetPointByDist(bc, cur_dist + moveDist);

transform.position = nextPoint;
``````
``````cur_dist = GetDistByPoint(bc, closestPoint);

float moveDist = (moveSpeed * inpX) * Time.deltaTime/10; //how far we should move in distance
Vector3 nextPoint = GetPointByDist(bc, cur_dist + moveDist);

transform.position = nextPoint;
``````

But when I try to move a Transform around the curve this way, I still get a big slowdown in movement around the control points of the Bezier curve, similar to when I was using Time to find points.

I’ve got that feeling like the issue is something dumb, but I’d really appreciate another pair of eyes on this. Thanks for your time!

Is the problem perhaps because you’re table-ifying on a per-segment basis rather than taking the entire bezier curve (all control points in a row) and accumulating the distance like that so you can move along it linearly?

But I already dealt with this problem when I was writing my Waypoint system. I created several spline types, Catmull, Bezier, BezierChain (multiple beziers chained with one another), and Linear.

All but the Linear have this problem. And you do need to create a time table for them. This was my general implementation (all of them do it generally the same way):

``````using UnityEngine;
using System.Collections.Generic;

namespace com.spacepuppy.Waypoints
{
internal class CurveConstantSpeedTable
{

#region Fields

private float _totalArcLength = float.NaN;
private float[] _timesTable;
private float[] _lengthsTable;

#endregion

#region CONSTRUCTOR

#endregion

#region Properties

public float TotalArcLength
{
get { return _totalArcLength; }
}

public bool IsDirty
{
get { return float.IsNaN(_totalArcLength); }
}

public int SubdivisionCount
{
get { return (_timesTable != null) ? _timesTable.Length : 0; }
}

#endregion

#region Methods

public void Clean(int subdivisions, System.Func<float, Vector3> getRealPositionAt)
{
_totalArcLength = 0f;
float incr = 1f / subdivisions;
_timesTable = new float[subdivisions];
_lengthsTable = new float[subdivisions];

var prevP = getRealPositionAt(0);
float perc;
Vector3 currP;
for (int i = 1; i <= subdivisions; ++i)
{
perc = incr * i;
currP = getRealPositionAt(perc);
_totalArcLength += Vector3.Distance(currP, prevP);
prevP = currP;
_timesTable[i - 1] = perc;
_lengthsTable[i - 1] = _totalArcLength;
}
}

public void SetDirty()
{
_totalArcLength = float.NaN;
_timesTable = null;
_lengthsTable = null;
}

public void SetZero()
{
_totalArcLength = 0f;
_timesTable = null;
_lengthsTable = null;
}

public float GetConstPathPercFromTimePerc(float t)
{
if (float.IsNaN(_totalArcLength) || _totalArcLength == 0f) return t;

//Apply constant speed
if (t > 0f && t < 1f)
{
float tLen = _totalArcLength * t;
float t0 = 0f, l0 = 0f, t1 = 0f, l1 = 0f;
int alen = _lengthsTable.Length;
for (int i = 0; i < alen; ++i)
{
if (_lengthsTable[i] > tLen)
{
t1 = _timesTable[i];
l1 = _lengthsTable[i];
if (i > 0) l0 = _lengthsTable[i - 1];
break;
}
t0 = _timesTable[i];
}
t = t0 + ((tLen - l0) / (l1 - l0)) * (t1 - t0);
}

if (t > 1f) t = 1f;
else if (t < 0f) t = 0f;
return t;
}

public float GetTimeAtSubdivision(int index)
{
if (_timesTable == null) return 0f;
return _timesTable[index];
}

#endregion

}
}
``````

In it you call clean to calculate the table, passing in how many subdivisions (level of detail) as well as a delegate to calculate the non-normalized position.

Here you can see me using it on my BezierSpline class:

``````using UnityEngine;
using System.Collections.Generic;

namespace com.spacepuppy.Waypoints
{

public class BezierSplinePath : IConfigurableIndexedWaypointPath
{

#region Fields

private bool _isClosed;
private List<IWaypoint> _waypoints = new List<IWaypoint>();

private Vector3[] _points;
private CurveConstantSpeedTable _speedTable = new CurveConstantSpeedTable();

#endregion

#region CONSTRUCTOR

public BezierSplinePath()
{

}

public BezierSplinePath(IEnumerable<IWaypoint> waypoints)
{
this.Clean_Imp();
}

#endregion

#region Properties

#endregion

#region Methods

private void Clean_Imp()
{
if (_waypoints.Count == 0)
{
_speedTable.SetZero();
}
else if (_waypoints.Count == 1)
{
_speedTable.SetZero();
}
else
{
var arr = this.GetPointArray();
float estimatedLength = 0f;
for(int i = 1; i < arr.Length; i++)
{
estimatedLength += (arr[i] - arr[i - 1]).magnitude;
}
int detail = Mathf.RoundToInt(estimatedLength / 0.1f);

_speedTable.Clean(detail, this.GetRealPositionAt);
}
}

private Vector3[] GetPointArray()
{
int l = _waypoints.Count;
int cnt = l;
if (_isClosed) cnt++;
if (_points == null)
_points = new Vector3[cnt];
else if(_points.Length != cnt)
System.Array.Resize(ref _points, cnt);

for (int i = 0; i < l; i++ )
{
_points[i] = _waypoints[i].Position;
}
if(_isClosed)
{
_points[cnt - 1] = _waypoints[0].Position;
}

return _points;
}

private Vector3 GetRealPositionAt(float t)
{
var arr = this.GetPointArray();
var c = arr.Length;
while (c > 1)
{
for (int i = 1; i < c; i++)
{
arr[i - 1] = Vector3.Lerp(arr[i - 1], arr[i], t);
}

c--;
}
return arr[0];
}

#endregion

#region IWaypointPath Interface

public bool IsClosed
{
get { return _isClosed; }
set
{
if (_isClosed == value) return;
_isClosed = value;
_speedTable.SetDirty();
}
}

public float GetArcLength()
{
if (_speedTable.IsDirty) this.Clean_Imp();
return _speedTable.TotalArcLength;
}

public Vector3 GetPositionAt(float t)
{
if (_waypoints.Count == 0) return Vector3.zero;
if (_waypoints.Count == 1) return _waypoints[0].Position;

if (_speedTable.IsDirty) this.Clean_Imp();
return this.GetRealPositionAt(_speedTable.GetConstPathPercFromTimePerc(t));
}

public Waypoint GetWaypointAt(float t)
{
if (_waypoints.Count == 0) return Waypoint.Invalid;
if (_waypoints.Count == 1) return new Waypoint(_waypoints[0]);

t = _speedTable.GetConstPathPercFromTimePerc(t);
var p1 = this.GetRealPositionAt(t);
var p2 = this.GetRealPositionAt(t + 0.01f);
return new Waypoint(p1, (p2 - p1));
}

public Vector3[] GetDetailedPositions(float segmentLength)
{
int detail = Mathf.FloorToInt(this.GetArcLength() / segmentLength) + 1;
Vector3[] arr = new Vector3[detail + 1];
for (int i = 0; i <= detail; i++)
{
arr[i] = this.GetPositionAt((float)i / (float)detail);
}
return arr;
}

#endregion

//... REDACTED LARGE PORTION OF CLASS USED FOR CONFIGURATION, UNNECESSARY FOR EXAMPLE USAGE

}

}
``````
2 Likes

That did it for sure! My hat is off to you sir, that was just what i needed to put me on the right path. Thanks for the code!

No prob man, hope it all goes well.

I’ve just come across this and I’m trying to implement some of these methods in my own code.

I’m using your methods to generate the two float[ ]'s, however I’m having trouble implementing these values when it comes to actually creating the curve.

``````private Vector3 GetBezierPoint(float t, Vector3 start, Vector3 control, Vector3 end, float totalCurveLength)
{
float x = (((1 - t) * (1 - t)) * start.x) + (2 * t * (1 - t) * control.x) + ((t * t) * end.x);
float y = (((1 - t) * (1 - t)) * start.y) + (2 * t * (1 - t) * control.y) + ((t * t) * end.y);
float z = (((1 - t) * (1 - t)) * start.z) + (2 * t * (1 - t) * control.z) + ((t * t) * end.z);
return new Vector3(x, y, z);
}
``````

That’s the code I’m using the generate a point on the dynamically generated curve, it’s a quadrilateral bezier curve, so it only has three points. I’m just not sure which lerp’s I should be replacing with the values from the length arrays.

If you’ve got a couple of minutes spare I’d love to discuss this. Thanks

I seem to remember using a free unity store package for making my curves, and they weren’t dynamically generated.

If you’re talking about the lengths in CurveConstantSpeedTable, you will note that this all hinges on the control points being predefined.

Your function is sort of an on demand method, as opposed to a stored reference.

You don’t want to be calculating CurveConstantSpeedTable every step of t, but rather only when it’s considered dirty.

Anyways… here’s the library from which my previous code comes from, you can read through it if you want:
https://github.com/lordofduct/spacepuppy-unity-framework/tree/master/SpacepuppyWaypoints/Waypoints

And inspector/editor code:
https://github.com/lordofduct/spacepuppy-unity-framework/tree/master/SpacepuppyWaypointsEditor/Waypoints

In it, BezierSplinePath With only 3 control points added with result in a qudratic bezier, which is what you desire.

Well after looking through your code I’ve managed to create my own arc-parameterization method. It works, but for some reason it sometimes creates a gap at the start of the curve if the distance between the start and the control point is somewhat long.