BIT-101
Bill Gates touched my MacBook Pro
This is something I need to solve every now and then - the need to interpolate smoothly along a Bézier curve. This can manifest in a few ways.
One, you want to evenly place points along the curve.
Two, you want to smoothly move an object along the curve.
Three, you want to find a point that is some percentage of the way along the curve.
I should note that as far as I know there is no mathematical way to perfectly accomplish this. Or at least not one that’s feasible to implement in code. So we have to resort to other usable methods.
Well, you might think, the formula for a Bézier curve has a t value in it, where if t is 0.0 it’s the start of the curve, and at t = 1.0, it’s the end of the curve. So just interpolate t from 0 to 1 and create a point on each returned location.
For this post, I’m going to show you some of the code in my own personal geometry library. It’s written in Go and has a lot of dependencies on other code in the library, but I think you’ll be able to understand what’s going on.
I have a function called geom.BezierPoint which looks like this:
func BezierPoint(t float64, p0 *Point, p1 *Point, p2 *Point, p3 *Point) *Point {
oneMinusT := 1.0 - t
m0 := oneMinusT * oneMinusT * oneMinusT
m1 := 3.0 * oneMinusT * oneMinusT * t
m2 := 3.0 * oneMinusT * t * t
m3 := t * t * t
return &Point{
m0*p0.X + m1*p1.X + m2*p2.X + m3*p3.X,
m0*p0.Y + m1*p1.Y + m2*p2.Y + m3*p3.Y,
}
}
Give it your four control points and a t value and it gives you back a point for that location along the curve.
So I’ll create some control points on an 800x800 surface and stroke a Bézier curve, then loop through 100 t values and draw a point at each location.
OK, so we do indeed have 100 points along the curve, but they are not evenly spaced. At the start and at the end they are further apart, while in the center, they’re very cramped. Not what was specified at all.
I’ve solved this in the past. And when I wanted to add this solution to my library, I attempted the same solution. And it works. Kind of.
You start by figuring out how much space you want between each point. Say it’s 20 pixels.
You get the first point on the curve, the p0 control point.
Now you get additional points by increasing t in very small increments until the distance from p0 to the point you get is very close to 20 pixels.
Then you make this new point the starting point and continuing to increase t in tiny increments until you get another point that’s about 20 pixels from that.
The first problem is that if you don’t increase t in small enough increments, you may not get very close to the target distance. So you have to check if you’ve gone beyond that distance. Then your points just aren’t super accurate. They’re kind of evenly spaced, but there’s still an occasional glitch where they are a bit further apart of closer together.
The solution to the first problem is to use very tiny increments for t so that you are always getting very close to the target distance. This solution introduces the second problem. I found I sometimes had to use increments as low as 0.0001 to get the errors down to a sub-pixel level. That’s 10,000 iterations to create a set of just 100 evenly placed points. This can get SLOW.
One thought is that for a low number of points you can get away with a higher increment and for a higher number of points, you need a much lower increment. I spent some time trying to figure out a formula that would account for that, without much luck.
The third problem is that even when you use low increments, the last point may be very close to the end of the path, less than the target distance. So you still get some glitchiness there.
Yet another problem is that this relies on knowing how much space you want between points. But say you just know that you want 100 points along the curve. Now you need to know the length of the curve. And that comes back to the same performance problem. The simplest way to get the length is to generate a bunch of Bézier points and add up the distances between each of them. But the more points you create, the more accurate the length. You may have to add a few thousand points to get a decently accurate length. This adds to the low performance problem.
I spent a lot of time trying to add error correction/propagation and other strategies to make this more performant and still look good. No real joy there.
So I went back to the drawing board.
Rethinking this, I realized I could break the Bézier curve down into a segmented path and then interpolate along that path.
Before I even thought of this in terms of Bézier paths though, I needed a function that can interpolate along such a path. A path is simply a list of points. And in my library I have such an object, called PointList. This function should take a t value from 0 to 1 and return a point somewhere along this path, where 0 would be the first point, 1 would be the last point, anything else, somewhere in between, along one of the segments of that path.
Here’s the Go code I came up with. Again, you might not understand all of what’s going on here if you’re not familiar with the language, but you should be able to suss out the basics.
func (p PointList) Interpolate(t float64) (*Point, error) {
if t < 0 || t > 1 {
return nil, errors.New("t should be from 0.0 to 1.0")
}
if t == 0 {
return p.First(), nil
}
if t == 1 {
return p.Last(), nil
}
length := p.Length()
accumulated := 0.0
for i := range len(p) - 1 {
p0 := p[i]
p1 := p[i+1]
l := p0.Distance(p1)
if (accumulated+l)/length > t {
tmin := accumulated / length
tmax := (accumulated + l) / length
t = blmath.Norm(t, tmin, tmax)
return LerpPoint(t, p0, p1), nil
}
accumulated += l
}
return nil, errors.New("unable to interpolate")
}
In short, the whole path has a length, which is the sum of all the segments between each of its points. First, I look for the segment that contains t - where the percentage of the length so far is less than t, but after this segment it’s greater than t. Then I interpolate between the two points that make up that segment and return that point.
In this animation, I create a path of completely random points and then interpolate t from 0 to 1, drawing a point for that t on each frame. You can see it smoothly moves along the path.
Alternately, I can just increase t by 0.01 to create 100 evenly placed points.
Now we just need to create a segmented path like this for a Bézier curve. That’s easy enough. Just go back to our naive approach from the start of this post and create a bunch of points with the BezierPoint function. For demonstration purposes, first I’ll do it in a lower resolution so you can see the segment’s clearly.
Here, I just increased t by 0.1 each iteration, creating 10 segments.
Now this is a PointList - a path made by discrete points - that I can interpolate over with my PointList.Interpolate function. This time I’ll draw the actual Bézier curve, and then 100 interpolated points.
Not great. The points are spaced nicely, but they don’t follow the curve too well. Because the path I created was too low res. Let’s try making that path with 100 segments instead of just 10.
Let’s see what this segmented path looks like with 100 segments.
That’s pretty smooth. You can’t really tell this is made from straight lines. It just looks like a curve.
Now let’s see what happens when we evenly interpolate 100 points along this path. This time with the actual smooth curve drawn in the background.
Woohoo! That’s pretty much perfect. The points follow the curve. They are evenly spaced. Start and end points are all good.
But one question remains:
How many segments to create for a given curve and number of points? Well, as you can see above, for 100 interpolated points, 100 segments worked out pretty well. In my final function, I just doubled that to be sure. That’s still only 200 segments, as compared to up to 10,000 iterations in my earlier attempt, and with even better results.
Here’s the function I came up with:
func LinearBezierPoints(count float64, p0, p1, p2, p3 *Point) PointList {
path := NewPointList()
for i := 0.0; i <= count*2; i++ {
t := i / (count * 2)
p := BezierPoint(t, p0, p1, p2, p3)
path.Add(p)
}
points := NewPointList()
for i := 0.0; i <= count; i++ {
t := i / count
p, _ := path.Interpolate(t)
points.Add(p)
}
return points
}
Pretty simple actually, with the Interpolate function doing a lot of the heavy lifting.
Note that these points technically still aren’t perfect, Most of them will not perfectly lie on the curve. But by segmenting that curve enough, they’re close enough for anyone’s eye. And if that isn’t close enough, segment the curve some more.
Earlier I said that one application of this would be smoothly moving an object along a Bézier curve.
In this final animation, I have a Bézier curve. The red dot is moving along the curve using the normal Bézier curve formula. Note that it does not move at a constant speed. It starts out fast, slows in the middle and speeds up again at the end. The green dot moves at a constant speed along the curve. Also note that they both finish together. I guess you could use this kind of thing for a custom easing function if the existing ones aren’t enough for you.
Hopefully this helps someone somewhere down the line. I’ll probably continue to improve this code myself. So the code you see here may look a bit different than what you see in my library. I’ll probably create an separate BezierCurve object with methods that do these things. And a function to create a segmented path from a set of Bézier control points. And… who knows what else.
[Update] I did end up creating that BezierCurve object. You can see it here: https://github.com/bit101/bitlib/blob/main/geom/bezier.go
Comments? Best way to shout at me is on Mastodon