# Bézier Curves

Aug 29 2019, 9:21 AM PST 15 min

Game development often requires using curves, such as drawing curvy shapes or travelling along a non-linear path. However, computers require a function in order to perform calculations. For lines, equations are quite simple (y = mx +b). Curves, on the other hand, tend to be a bit more complicated. A Bézier curve is an easier type of curve that is useful in a wide variety of places in game design. You’ll need to be somewhat comfortable with the following math topics in order to get started:

• Algebra
• Linear interpolation
• Vectors

A quadratic Bézier curve is a curve created using three points. The first and the third point define the start and the end of the curve. The intermediate point influences the curvature of the line, and is most of the time not on the curve.
Here’s what one quadratic Bézier looks like:

This may seem confusing at first, but it’s simpler than it appears: the function is lerping along the line between between p0 and p1 while simultaneously lerping along the line between p1 and p2. We’re then taking the two points created by those two lerp functions and then lerping along that value to get our point on the curve. This looks something like this:

We can write it in code form as such:

``````function lerp(a, b, c)
return a + (b - a) * c
end

local l1 = lerp(p0, p1, t)
local l2 = lerp(p1, p2, t)
local quad = lerp(l1, l2, t)
end
``````

This function is alright and there’s nothing wrong with it, but there’s a more formal equation that’s commonly used for quadratic Bézier curves.

To understand why this equation works we have to first think about how we would create a linear Bézier curve (not really a curve now is it?). If you’re up to date on the prerequisites of the article then you already know how to do this in the form of a linear interpolation between two points!

We already know how to do a quadratic Bezier using three linear interpolations like we did in the code above so let’s try writing that out with our linear B(t) function:

Sure enough we’re left with the formal quadratic Bézier curve equation!

``````function quadBezier(t, p0, p1, p2)
return (1 - t)^2 * p0 + 2 * (1 - t) * t * p1 + t^2 * p2
end
``````

## Cubic Bézier curves

A cubic Bézier curve is a curve that’s created with four points. The first and the fourth point define the start and the end of the curve. The intermediates point once again just like the quadratic curve influence the curvature of the line.

Here’s what a cubic Bézier might look like:

Once again, this might seem a little confusing to wrap your head around but it’s a very similar process to what we were doing with the quadratic Bézier curves. What we’re actually doing is lerping along the line between between p0 and p1 while simultaneously lerping along the line between p1 and p2 while also simultaneously lerping along the line between p2 and p3. We’re then taking the two points created by those the first and second lerp functions and then lerping along that value to get yet another point which we’ll call “a”. Then we’re taking two points created by the second and third lerp functions and lerping along the line created by those two points to get a point which we’ll call “b”. Finally, we lerp between “a” and “b” to get our point along the curve.

We can write this in function form:

``````function lerp(a, b, c)
return a + (b - a) * c
end

function cubicBezier(t, p0, p1, p2, p3)
local l1 = lerp(p0, p1, t)
local l2 = lerp(p1, p2, t)
local l3 = lerp(p2, p3, t)
local a = lerp(l1, l2, t)
local b = lerp(l2, l3, t)
local cubic = lerp(a, b, t)
return cubic
end
``````

Yet again, there’s a more formal equation for a cubic Bézier:

In a similar sense we can pull apart the code from above to find why this equation works:

Sure enough, we’re left with the cubic Bézier function!

``````function cubicBezier(t, p0, p1, p2, p3)
return (1 - t)^3*p0 + 3*(1 - t)^2*t*p1 + 3*(1 - t)*t^2*p2 + t^3*p3
end
``````

It is possible to have Bézier curves of higher degrees by following a similar pattern but for the purpose of this article we’ll stop here at cubic.

## Arc-length parameterization

So now that we know a bit about how to calculate points along Bézier curves let’s talk about some current issues we might face with them. To start, let’s see what happens when we try to interpolate along our curve at a fixed speed.

``````-- function for drawing a 2D line between two points
function drawLine(p1, p2)
local v = (p2 - p1)
local f = Instance.new("Frame")
f.Size = UDim2.new(0, v.magnitude + 1, 0, 2)
f.Position = UDim2.new(0,(p1.x + v.x/2) - f.Size.X.Offset * 0.5, 0, (p1.y + v.y/2) - f.Size.Y.Offset * 0.5)
f.Rotation = math.deg(math.atan2(v.y, v.x))
f.BorderSizePixel = 0
f.BackgroundColor3 = Color3.new()
return f
end

function update(p0, p1, p2, p3, canvas)
local last
canvas:ClearAllChildren() -- clear any previous drawings
for t = 0, 1, 0.01 do -- 0 <= t <= 1
local p = cubicBezier(t, p0, p1, p2, p3)
if last then drawLine(last, p).Parent = canvas end
last = p
end
end

function travelCurve(p0, p1, p2, p3, moving)
for t = 0, 1, 0.01 do -- 0 <= t <= 1
local p = cubicBezier(t, p0, p1, p2, p3)
moving.Position = UDim2.new(0, p.x - mp.AbsoluteSize.x/2, 0, p.y - mp.AbsoluteSize.y/2)
game:GetService("RunService").RenderStepped:wait()
end
end
``````

Hmm, that doesn’t look like it’s traveling at a linear rate does it? Turns out the reason for this is because by nature of a Bézier curve doesn’t produce points that are evenly distributed. To see this let’s just draw points along the curve.

``````-- function for drawing a 2D point
function drawPoint(p1)
local f = Instance.new("Frame")
f.Size = UDim2.new(0, 2, 0, 2)
f.Position = UDim2.new(0, p1.x - f.Size.X.Offset * 0.5, 0, p1.y - f.Size.Y.Offset * 0.5)
f.BorderSizePixel = 0
f.BackgroundColor3 = Color3.new()
return f
end

function update(p0, p1, p2, p3, canvas)
local last
canvas:ClearAllChildren() -- clear any previous drawings
for t = 0, 1, 0.01 do -- 0 <= t <= 1
local p = cubicBezier(t, p0, p1, p2, p3)
drawPoint(p).Parent = world
last = p
end
end
``````

As shown in the gif above, the points near the middle are more tightly packed together and the points closer to the start and end of the curve are further apart. This creates an effect of slowing down in the middle and getting faster near the start and end. So what can we do to fix this problem? In other words, how can we make it so that t = 0.25 is guaranteed to be 25% along the curve’s distance?

Turns out the simplest way to do this is a best guess method which isn’t perfect, but it’s so close that unless you’re working for NASA you won’t even notice it. To be clear, there are other ways to do this that are more accurate, but they require calculus which is out of the scope of this article.

Here’s how the process works:

``````-- n is the number of points
-- func is the bezier curve function
-- ... are the points used in the bezier curve function
function length(n, func, ...)
local sum, ranges, sums = 0, {}, {}
for i = 0, n-1 do
-- calculate the current point and the next point
local p1, p2 = func(i/n, ...), func((i+1)/n, ...)
-- get the distance between them
local dist = (p2 - p1).magnitude
-- store the information we gathered in a table that's indexed by the current distance
ranges[sum] = {dist, p1, p2}
-- store the current sum so we can easily sort through it later
table.insert(sums, sum)
-- update the sum
sum = sum + dist
end
-- return values
return sum, ranges, sums
end
``````

With that in mind we can use that function in tandem with another to get a pretty good guess of the actual linear position t would represent along the Bezier curve:

``````function fixedBezier(n, t, func, ...)
-- gather values from length function
local length, ranges, sums = length(n, func, ...)
-- find how far along the length we should be
local T, near = t * length, 0
-- get the nearest point we calculated
for _, n in next, sums do
if (T - n) < 0 then break end
near = n
end
local set = ranges[near]
-- linearly interpolate between that point and its neighbor
local percent = (T - near)/set[1]
return set[2] + (set[3] - set[2]) * percent
end
``````

Here’s the problem, when our current function is used consecutively this causes a lot of lag! We’re using the length function which has to do a ton of point calculations every time for just one single point! Here’s the good news though, if we use a bit of object oriented programming we can store the values the length function and make sure to update it only when the points that create the Bézier change!

Here’s a nice little Bézier module that should work with any degree of Bézier function:

``````local bezier = {}

function length(n, func, ...)
local sum, ranges, sums = 0, {}, {}
for i = 0, n-1 do
local p1, p2 = func(i/n, ...), func((i+1)/n, ...)
local dist = (p2 - p1).magnitude
ranges[sum] = {dist, p1, p2}
table.insert(sums, sum)
sum = sum + dist
end
return sum, ranges, sums
end

function bezier.new(func, n, ...)
local self = setmetatable({}, {__index = bezier})
local sum, ranges, sums = length(n, func, ...)
self.func = func
self.n = n
self.points = {...}
self.length = sum
self.ranges = ranges
self.sums = sums
return self
end

function bezier:setPoints(...)
-- only update the length when the control points are changed
local sum, ranges, sums = length(self.n, self.func, ...)
self.points = {...}
self.length = sum
self.ranges = ranges
self.sums = sums
end

function bezier:calc(t)
-- if you don't need t to be a percentage of distance
return self.func(t, unpack(self.points))
end

function bezier:calcFixed(t)
local T, near = t * self.length, 0
for _, n in next, self.sums do
if (T - n) < 0 then break end
near = n
end
local set = self.ranges[near]
local percent = (T - near)/set[1]
return set[2], set[3], percent
end

return bezier
``````

## Bézier paths

The last thing this article will cover is the idea of connecting multiple Bézier curves together. For visual purposes the concept is easy. Just make sure that the start point of your next Bézier curve is the same as the last point on the previous Bézier curve. What becomes more difficult is making these curves into a single interpolation function. Luckily for us, it’s a similar process to Arc-length parameterization except we already have all the values we need!

For example let’s assume we’re using the module from above:

``````-- bzs is table with bezier urves in it in order traveled
function travelPath(t, bzs)
local totalLength, sums = 0, {}
-- get total length of all curves, also order sums for sorting
for _, bz in next, bzs do
table.insert(sums, totalLength)
totalLength = totalLength + bz.length
end
-- get percentage of total distance and find the bezier curve we're on
local T, near, bz = t * totalLength, 0, bzs[1]
for i, n in ipairs(sums) do
if (T - n) < 0 then break end
near, bz = n, bzs[i]
end
-- get relative percentage traveled on given bezier curve
local percent = (T - near)/bz.length
-- lerp across curve by percentage
local a, b, c = bz:calcFixed(percent)
return a + (b - a) * c
end
``````

That’s all there is to it! We can also use Bézier curves in 3D since lerping with 3D and 2D vectors is the same.

Tags:
• math
• movement