Last time...
In my last post, I spoke about the awesome inspiration I got when I saw after watching this awesome video about Bézier Curves. It made me want to try and implement this algorithm for coding practice, and perhaps even use it for a small project or something.
I managed to create a test Unity project, and used the scene view UI to draw the Bézier curve:
Even though it looks a bit cool, it's just 3 points used to create a small curve. I want to see how I can go beyond this, and perhaps not limit myself to a fixed amount of points.
Enter the Cubic Bézier Curve!
Quick re-cap
The way that I'm drawing the current curve is by using a set of lerp functions across the 2 line segments between the 3 control points of the curve:
First code changes
Let's now start simple, and add a 4th control point to our curve and draw it:
public class BezierCurveDrawer : MonoBehaviour
{
public Vector3 m_point0 = new (-10f, 10f, 0f);
public Vector3 m_point1 = new (-10f, 20f, 0f);
public Vector3 m_point2 = new (10f, 20f, 0f);
public Vector3 m_point3 = new (10f, 10f, 0f);
...
private void DrawControlPoints()
{
Gizmos.DrawSphere(m_point0, k_controlPointRadius);
Gizmos.DrawSphere(m_point1, k_controlPointRadius);
Gizmos.DrawSphere(m_point2, k_controlPointRadius);
Gizmos.DrawSphere(m_point3, k_controlPointRadius);
}
private void DrawLineSegments()
{
Gizmos.DrawLine(m_point0, m_point1);
Gizmos.DrawLine(m_point1, m_point2);
Gizmos.DrawLine(m_point2, m_point3);
}
...
}
Of course, this won't do anything new, we're still using just the first 3 to generate the actual curve, but we're at least drawing all of the control points and line segments:
In Freya's video, she talks about the De Casteljau's algorithm, which is a series of iterations lerps, for every t value, in a range from 0.0 to 1.0. We see now 4 control points which result in 3 line segments:
I went ahead and tried simply that, adding that additional level of iteration of lerps, on the DrawBezierCurve() function, from the code created in the last post:
private void DrawBezierCurve()
{
Gizmos.color = Color.cyan;
var bezierCurvePoints = new List<Vector3>();
for (float t = 0f; t <= 1.001f; t += k_tValueStepIncrement)
{
// 1st iteration
var point0_iter1 = Vector3.Lerp(m_point0, m_point1, t);
var point1_iter1 = Vector3.Lerp(m_point1, m_point2, t);
var point2_iter1 = Vector3.Lerp(m_point2, m_point3, t);
// 2nd iteration
var point0_iter2 = Vector3.Lerp(point0_iter1, point1_iter1, t);
var point1_iter2 = Vector3.Lerp(point1_iter1, point2_iter1, t);
// 3rd iteration
var currentCurvePoint = Vector3.Lerp(point0_iter2, point1_iter2, t);
bezierCurvePoints.Add(currentCurvePoint);
}
...
}
And check it out! With this simple change, we now have our cubic Bézier curve:
If you think about it, it's an easy pattern to identify. When drawing our resulting curve, we iterate by creating a new smaller set of points, until we only have 2, which is the last iteration of just 1 lerp, and it gives us the point in the resulting curve.
Now with Recursion!
We can't continue by just manually adding control points(m_point4, m_point5, etc.) and then modify our code to add more iterations of lerps. We can definitely make a generic representation in our code.
Let's first add a list of control points that we'll use for our recursive implementation:
public class BezierCurveDrawer : MonoBehaviour
{
// OLD STUFF, will be deleted!
public Vector3 m_point0 = new (-10f, 10f, 0f);
public Vector3 m_point1 = new (-10f, 20f, 0f);
public Vector3 m_point2 = new (10f, 20f, 0f);
public Vector3 m_point3 = new (10f, 10f, 0f);
public List<Vector3> m_controlPoints = new List<Vector3>
{
new(-10f, 10f, 0f),
new (-10f, 20f, 0f),
new (10f, 20f, 0f),
new (10f, 10f, 0f)
};
...
}
Now you can dynamically add control points:
Next up, let's change the functions that draw the main control points, and their main line segments:
private void OnDrawGizmos()
{
DrawControlPoints();
DrawLineSegmentsOfControlPoints();
DrawBezierCurve();
}
private void DrawControlPoints()
{
foreach (var controlPoint in m_controlPoints)
{
Gizmos.DrawSphere(controlPoint, k_controlPointRadius);
}
}
private void DrawLineSegmentsOfControlPoints()
{
DrawLineSegmentsInBetweenPoints(m_controlPoints);
}
private void DrawLineSegmentsInBetweenPoints(List<Vector3> points)
{
for (int pointListIndex = 1; pointListIndex < points.Count; pointListIndex++)
{
Gizmos.DrawLine(
points[pointListIndex - 1],
points[pointListIndex]);
}
}
Note: Notice we added a new general function called
DrawLineSegmentsInBetweenPoints, which is used in theDrawLineSegmentsOfControlPointsfunction which used to beDrawLineSegments.
Now let's translate the series of lerps we talked about before in our DrawBezierCurve function, into a recursive version of the same logic:
private void DrawBezierCurve()
{
if (m_controlPoints.Count <= 1)
{
return;
}
Gizmos.color = Color.cyan;
var bezierCurvePoints = new List<Vector3>();
for (float t = 0f; t <= 1.001f; t += k_tValueStepIncrement)
{
CreateBezierCurveRecursively(m_controlPoints, t, ref bezierCurvePoints);
}
foreach(var curvePoint in bezierCurvePoints)
{
Gizmos.DrawSphere(curvePoint, 0.1f);
}
DrawLineSegmentsInBetweenPoints(bezierCurvePoints);
}
private void CreateBezierCurveRecursively(
List<Vector3> iterationOfControlPoints,
float t,
ref List<Vector3> resultCurve)
{
if(iterationOfControlPoints.Count == 2)
{
var resultCurvePoint =
Vector3.Lerp(
iterationOfControlPoints[0],
iterationOfControlPoints[1],
t);
resultCurve.Add(resultCurvePoint);
return;
}
var nextIterationOfPoints = GetNextIterationOfpoints(iterationOfControlPoints, t);
CreateBezierCurveRecursively(nextIterationOfPoints, t, ref resultCurve);
}
List<Vector3> GetNextIterationOfpoints(List<Vector3> currentIterationOfpoints, float t)
{
// reserve the memory beforehand, since we know how many points we'll end up with
List<Vector3> result = new(currentIterationOfpoints.Count - 1);
for (int i = 1; i < currentIterationOfpoints.Count; i++)
{
var segmentInterpolation =
Vector3.Lerp(
currentIterationOfpoints[i - 1],
currentIterationOfpoints[i],
t);
result.Add(segmentInterpolation);
}
return result;
}
And here we go! Now we have a nice curve that can be drawn with a dynamic amount of points:
Note: I've been showing this in
2Dview, for simplicity. But since we're usingVector3, this definitely works if you switch to3Dview, and can see the changes in theZaxis.
So, what's next?
I'm going to research some more about this, because I'd like to create something fun, maybe optimize this current code, or mix it up with some research I've done following the basic tutorials of Niantic's Lightship SDK.
One of the properties of Bézier Curves is that they are continuous. This means that one could join quadratic or cubic curves together to make more complex shapes, which is called a Composite Bézier Curve. The last control point of a curve would be the beginning of the next. This way, I don't necessarily need to recursively compute the entire curve when I decide to use 5 or more points.
Please let me know what you think!
- Any questions at all about my recursive implementation?
- What other flaws do you see with this implementation? (Hint: lots of allocations!)
- What optimizations would you apply to this code?
- Given this new update, how else would you use these kinds of curves?
🎉🎉🎉Happy coding!!🎉🎉🎉