Newer
Older
.. include:: ../../abbreviation.txt
.. _bezier-geometry-ressources-page:
===============
Bézier Curves
===============
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
Definitions
-----------
A Bézier curve is defined by a set of control points :math:`\mathbf{P}_0` through
:math:`\mathbf{P}_n`, where :math:`n` is called its order (:math:`n = 1` for linear, 2 for
quadratic, 3 for cubic etc.). The first and last control points are always the end points of the
curve;
In the following :math:`0 \le t \le 1`.
Linear Bézier Curves
---------------------
Given distinct points :math:`\mathbf{P}_0` and :math:`\mathbf{P}_1`, a linear Bézier curve is simply
a straight line between those two points. The curve is given by
.. math::
\begin{align}
\mathbf{B}(t) &= \mathbf{P}_0 + t (\mathbf{P}_1 - \mathbf{P}_0) \\
&= (1-t) \mathbf{P}_0 + t \mathbf{P}_1
\end{align}
and is equivalent to linear interpolation.
Quadratic Bézier Curves
-----------------------
A quadratic Bézier curve is the path traced by the function :math:`\mathbf{B}(t)`, given points
:math:`\mathbf{P}_0`, :math:`\mathbf{P}_1`, and :math:`\mathbf{P}_2`,
.. math::
\mathbf{B}(t) = (1 - t)[(1 - t) \mathbf{P}_0 + t \mathbf{P}_1] + t [(1 - t) \mathbf{P}_1 + t \mathbf{P}_2]
which can be interpreted as the linear interpolant of corresponding points on the linear Bézier
curves from :math:`\mathbf{P}_0` to :math:`\mathbf{P}_1` and from :math:`\mathbf{P}_1` to
:math:`\mathbf{P}_2` respectively.
Rearranging the preceding equation yields:
.. math::
\begin{align}
\mathbf{B}(t) &= (1 - t)^{2} \mathbf{P}_0 + 2(1 - t)t \mathbf{P}_1 + t^{2} \mathbf{P}_2 \\
&= (\mathbf{P}_0 - 2\mathbf{P}_1 + \mathbf{P}_2) t^2 +
(-2\mathbf{P}_0 + 2\mathbf{P}_1) t +
\mathbf{P}_0
\end{align}
This can be written in a way that highlights the symmetry with respect to :math:`\mathbf{P}_1`:
.. math::
\mathbf{B}(t) = \mathbf{P}_1 + (1 - t)^{2} ( \mathbf{P}_0 - \mathbf{P}_1) + t^{2} (\mathbf{P}_2 - \mathbf{P}_1)
Which immediately gives the derivative of the Bézier curve with respect to `t`:
.. math::
\mathbf{B}'(t) = 2(1 - t) (\mathbf{P}_1 - \mathbf{P}_0) + 2t (\mathbf{P}_2 - \mathbf{P}_1)
from which it can be concluded that the tangents to the curve at :math:`\mathbf{P}_0` and
:math:`\mathbf{P}_2` intersect at :math:`\mathbf{P}_1`. As :math:`t` increases from 0 to 1, the
curve departs from :math:`\mathbf{P}_0` in the direction of :math:`\mathbf{P}_1`, then bends to
arrive at :math:`\mathbf{P}_2` from the direction of :math:`\mathbf{P}_1`.
The second derivative of the Bézier curve with respect to :math:`t` is
.. math::
\mathbf{B}''(t) = 2 (\mathbf{P}_2 - 2 \mathbf{P}_1 + \mathbf{P}_0)
Cubic Bézier Curves
-------------------
Four points :math:`\mathbf{P}_0`, :math:`\mathbf{P}_1`, :math:`\mathbf{P}_2` and
:math:`\mathbf{P}_3` in the plane or in higher-dimensional space define a cubic Bézier curve. The
curve starts at :math:`\mathbf{P}_0` going toward :math:`\mathbf{P}_1` and arrives at
:math:`\mathbf{P}_3` coming from the direction of :math:`\mathbf{P}_2`. Usually, it will not pass
through :math:`\mathbf{P}_1` or :math:`\mathbf{P}_2`; these points are only there to provide
directional information. The distance between :math:`\mathbf{P}_1` and :math:`\mathbf{P}_2`
determines "how far" and "how fast" the curve moves towards :math:`\mathbf{P}_1` before turning
towards :math:`\mathbf{P}_2`.
Writing :math:`\mathbf{B}_{\mathbf P_i,\mathbf P_j,\mathbf P_k}(t)` for the quadratic Bézier curve
defined by points :math:`\mathbf{P}_i`, :math:`\mathbf{P}_j`, and :math:`\mathbf{P}_k`, the cubic
Bézier curve can be defined as an affine combination of two quadratic Bézier curves:
.. math::
\mathbf{B}(t) = (1-t) \mathbf{B}_{\mathbf P_0,\mathbf P_1,\mathbf P_2}(t) +
t \mathbf{B}_{\mathbf P_1,\mathbf P_2,\mathbf P_3}(t)
The explicit form of the curve is:
.. math::
\begin{align}
\mathbf{B}(t) &= (1-t)^3 \mathbf{P}_0 + 3(1-t)^2t \mathbf{P}_1 + 3(1-t)t^2 \mathbf{P}_2 + t^3\mathbf{P}_3 \\
&= (\mathbf{P}_3 - 3\mathbf{P}_2 + 3\mathbf{P}_1 - \mathbf{P}_0) t^3 +
3(\mathbf{P}_2 - 2\mathbf{P}_1 + \mathbf{P}_0) t^2 +
3(\mathbf{P}_1 - \mathbf{P}_0) t +
\mathbf{P}_0
\end{align}
For some choices of :math:`\mathbf{P}_1` and :math:`\mathbf{P}_2` the curve may intersect itself, or
contain a cusp.
The derivative of the cubic Bézier curve with respect to :math:`t` is
.. math::
\mathbf{B}'(t) = 3(1-t)^2 (\mathbf{P}_1 - \mathbf{P}_0) + 6(1-t)t (\mathbf{P}_2 - \mathbf{P}_1) + 3t^2 (\mathbf{P}_3 - \mathbf{P}_2)
The second derivative of the Bézier curve with respect to :math:`t` is
.. math::
\mathbf{B}''(t) = 6(1-t) (\mathbf{P}_2 - 2 \mathbf{P}_1 + \mathbf{P}_0) + 6t (\mathbf{P}_3 - 2 \mathbf{P}_2 + \mathbf{P}_1)
Recursive definition
--------------------
A recursive definition for the Bézier curve of degree :math:`n` expresses it as a point-to-point
linear combination of a pair of corresponding points in two Bézier curves of degree :math:`n-1`.
Let :math:`\mathbf{B}_{\mathbf{P}_0\mathbf{P}_1\ldots\mathbf{P}_n}` denote the Bézier curve
determined by any selection of points :math:`\mathbf{P}_0`, :math:`\mathbf{P}_1`, :math:`\ldots`,
:math:`\mathbf{P}_{n-1}`.
The recursive definition is
.. math::
\begin{align}
\mathbf{B}_{\mathbf{P}_0}(t) &= \mathbf{P}_0 \\[1em]
\mathbf{B}(t) &= \mathbf{B}_{\mathbf{P}_0\mathbf{P}_1\ldots\mathbf{P}_n}(t) \\
&= (1-t) \mathbf{B}_{\mathbf{P}_0\mathbf{P}_1\ldots\mathbf{P}_{n-1}}(t) +
t \mathbf{B}_{\mathbf{P}_1\mathbf{P}_2\ldots\mathbf{P}_n}(t)
\end{align}
The formula can be expressed explicitly as follows:
.. math::
\begin{align}
\mathbf{B}(t) &= \sum_{i=0}^n b_{i,n}(t) \mathbf{P}_i \\
&= \sum_{i=0}^n {n\choose i}(1 - t)^{n - i}t^i \mathbf{P}_i \\
&= (1 - t)^n \mathbf{P}_0 +
{n\choose 1}(1 - t)^{n - 1}t \mathbf{P}_1 +
\cdots +
{n\choose n - 1}(1 - t)t^{n - 1} \mathbf{P}_{n - 1} +
t^n \mathbf{P}_n
\end{align}
where :math:`b_{i,n}(t)` are the Bernstein basis polynomials of degree :math:`n` and :math:`n
\choose i` are the binomial coefficients.
Degree elevation
----------------
A Bézier curve of degree :math:`n` can be converted into a Bézier curve of degree :math:`n + 1` with
the same shape.
To do degree elevation, we use the equality
.. math::
\mathbf{B}(t) = (1-t) \mathbf{B}(t) + t \mathbf{B}(t)
Each component :math:`\mathbf{b}_{i,n}(t) \mathbf{P}_i` is multiplied by :math:`(1-t)` and
:math:`t`, thus increasing a degree by one, without changing the value.
For arbitrary :math:`n`, we have
.. math::
\begin{align}
\mathbf{B}(t) &= (1 - t) \sum_{i=0}^n \mathbf{b}_{i,n}(t) \mathbf{P}_i +
t \sum_{i=0}^n \mathbf{b}_{i,n}(t) \mathbf{P}_i \\
&= \sum_{i=0}^n \frac{n + 1 - i}{n + 1} \mathbf{b}_{i, n + 1}(t) \mathbf{P}_i +
\sum_{i=0}^n \frac{i + 1}{n + 1} \mathbf{b}_{i + 1, n + 1}(t) \mathbf{P}_i \\
&= \sum_{i=0}^{n + 1} \mathbf{b}_{i, n + 1}(t)
\left(\frac{i}{n + 1} \mathbf{P}_{i - 1} +
\frac{n + 1 - i}{n + 1} \mathbf{P}_i\right) \\
&= \sum_{i=0}^{n + 1} \mathbf{b}_{i, n + 1}(t) \mathbf{P'}_i
\end{align}
Therefore the new control points are
.. math::
\mathbf{P'}_i = \frac{i}{n + 1} \mathbf{P}_{i - 1} + \frac{n + 1 - i}{n + 1} \mathbf{P}_i
It introduces two arbitrary points :math:`\mathbf{P}_{-1}` and :math:`\mathbf{P}_{n+1}` which are
cancelled in :math:`\mathbf{P'}_i`.
Matrix Forms
------------
.. math::
\mathbf{B}(t) = \mathbf{Transformation} \; \mathbf{Control} \; \mathbf{Basis} \; \mathbf{T}(t)
.. math::
\begin{align}
\mathbf{B^2}(t) &= \mathbf{Tr}
\begin{pmatrix}
P_{1x} & P_{2x} & P_{3x} \\
P_{1y} & P_{2x} & P_{3x} \\
1 & 1 & 1
\end{pmatrix}
\begin{pmatrix}
1 & -2 & 1 \\
0 & 2 & -2 \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
1 \\
t \\
t^2
\end{pmatrix} \\[1em]
\mathbf{B^3}(t) &= \mathbf{Tr}
\begin{pmatrix}
P_{1x} & P_{2x} & P_{3x} & P_{4x} \\
P_{1y} & P_{2x} & P_{3x} & P_{4x} \\
0 & 0 & 0 & 0 \\
1 & 1 & 1 & 1
\end{pmatrix}
\begin{pmatrix}
1 & -3 & 3 & -1 \\
0 & 3 & -6 & 3 \\
0 & 0 & 3 & -3 \\
0 & 0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
1 \\
t \\
t^2 \\
t^3
\end{pmatrix}
\end{align}
.. B(t) = P0 (1 - 2t + t^2) +
P1 ( 2t - t^2) +
P2 t^2
Symbolic Calculation
--------------------
.. code-block:: py3
>>> from sympy import *
>>> P0, P1, P2, P3, P, t = symbols('P0 P1 P2 P3 P t')
>>> B2 = (1-t)*((1-t)*P0 + t*P1) + t*((1-t)*P1 + t*P2)
>>> collect(expand(B2), t)
P0 + t**2*(P0 - 2*P1 + P2) + t*(-2*P0 + 2*P1)
>>> B2_012 = (1-t)*((1-t)*P0 + t*P1) + t*((1-t)*P1 + t*P2)
>>> B2_123 = (1-t)*((1-t)*P1 + t*P2) + t*((1-t)*P2 + t*P3)
>>> B3 = (1-t)*B2_012 + t*B2_123
>>> collect(expand(B2), t)
P0 + t**3*(-P0 + 3*P1 - 3*P2 + P3) + t**2*(3*P0 - 6*P1 + 3*P2) + t*(-3*P0 + 3*P1)
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
.. _bezier-curve-length-section:
Curve Length
------------
Reference
* http://www.gamedev.net/topic/551455-length-of-a-generalized-quadratic-bezier-curve-in-3d
* Dave Eberly Posted October 25, 2009
The quadratic Bézier is
.. math::
\mathbf{B}(t) = (1-t)^2 \mathbf{P}_0 + 2t(1-t) \mathbf{P}_1 + t^2 \mathbf{P}_2
The derivative is
.. math::
\mathbf{B'}(t) = -2(1-t) \mathbf{P}_0 + (2-4t) \mathbf{P}_1 + 2t \mathbf{P}_2
The length of the curve for :math:`0 <= t <= 1` is
.. math::
\int_0^1 \sqrt{(x'(t))^2 + (y'(t))^2} dt
The integrand is of the form :math:`\sqrt{c t^2 + b t + a}`
You have three separate cases: :math:`c = 0`, :math:`c > 0`, or :math:`c < 0`.
The case :math:`c = 0` is easy.
For the case :math:`c > 0`, an antiderivative is
.. math::
\frac{2ct + b}{4c} \sqrt{ct^2 + bt + a} + \frac{k}{2\sqrt{c}} \ln{\left(2\sqrt{c(ct^2 + bt + a)} + 2ct + b\right)}
For the case :math:`c < 0`, an antiderivative is
.. math::
\frac{2ct + b}{4c} \sqrt{ct^2 + bt + a} - \frac{k}{2\sqrt{-c}} \arcsin{\frac{2ct + b}{\sqrt{-q}}}
where :math:`k = \frac{4c}{q}` with :math:`q = 4ac - b^2`.
.. _bezier-curve-flatness-section:
Determine the curve flatness
----------------------------
Reference
* Kaspar Fischer and Roger Willcocks http://hcklbrrfnn.files.wordpress.com/2012/08/bez.pdf
* PostScript Language Reference. Addison- Wesley, third edition, 1999
*flatness* is the maximum error allowed for the straight line to deviate from the curve.
Algorithm
We define the flatness of the curve as the argmax of the distance from the curve to the
line passing by the start and stop point.
:math:`\mathrm{flatness} = argmax(d(t))` for :math:`t \in [0, 1]` where :math:`d(t) = \vert B(t) - L(t) \vert`
The line equation is
.. math::
L = (1-t) \mathbf{P}_0 + t \mathbf{P}_1
Let
.. math::
\begin{align}
u &= 3\mathbf{P}_1 - 2\mathbf{P}_0 - \mathbf{P}_3 \\
v &= 3\mathbf{P}_2 - \mathbf{P}_0 - 2\mathbf{P}_3
\end{align}
The distance is
.. math::
\begin{align}
d(t) &= (1-t)^2 t \left(3\mathbf{P}_1 - 2\mathbf{P}_0 - \mathbf{P}_3\right) + (1-t) t^2 (3\mathbf{P}_2 - \mathbf{P}_0 - 2\mathbf{P}_3) \\
&= (1-t)^2 t u + (1-t) t^2 v
\end{align}
The square of the distance is
.. math::
d(t)^2 = (1 - t)^2 t^2 (((1 - t) ux + t vx)^2 + ((1 - t) uy + t vy)^2
From
.. math::
\begin{align}
argmax((1 - t)^2 t^2) &= \frac{1}{16} \\
argmax((1 - t) a + t b) &= argmax(a, b)
\end{align}
we can express a bound on the flatness
.. math::
\mathrm{flatness}^2 = argmax(d(t)^2) \leq \frac{1}{16} (argmax(ux^2, vx^2) + argmax(uy^2, vy^2))
Thus an upper bound of :math:`16\,\mathrm{flatness}^2` is
.. math::
argmax(ux^2, vx^2) + argmax(uy^2, vy^2)