summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/lapdf/bezinfo.tex
blob: 9cee401ee4f260fff2adfecc4fc3415c2449fb23 (plain)
1
2
3
4
5
6
7
8
9
10
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
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
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
\documentclass[titlepage,a4paper,11pt]{report}
\usepackage{shortvrb}
\usepackage{array}
\usepackage[color]{lapdf}

\textheight24.92cm
\textwidth15.92cm
\oddsidemargin0cm
\evensidemargin0cm
\topmargin-0.3cm
\headheight0cm
\topskip0cm
\headsep0cm
\unitlength1cm

\MakeShortVerb{\|}

\def\it{\textit}
\def\tt{\texttt}
\def\sf{\textsf}
\def\bf{\textbf}
\def\em{\textit}
\def\mr{\mathrm}
\def\mb{\mathbf}
\def\fr{\frac}
\def\qq{\qquad}

\def\syn{\item[Syntax]}
\def\fun{\item[Function]}
\def\exa{\item[Example]}
\def\see{\item[See Also]}

% -------------------------------------------
\title{
 \bf{\Huge Bezier Curves} \\ \vspace{0.6cm}
 \bf{An Introduction}}
\author{ \\
 Detlef Reimers\\
 detlefreimers@gmx.de\\
 http://detlefreimers.de}
\date{\today}

% -------------------------------------------------------------------------
\begin{document}

\parindent0cm
\maketitle

% -------------------------------------------------------------------------
\chapter{Bezier Curve Basics}
\section{Linear Interpolation}
This section will give you a basic introduction to bezier curves. We begin
with the simplest curve form, a straight line. We can express any point
$\mb{x}$ on this straight line by the two given points and the parameter $t$:
\begin{equation}
  \mb{x}=\mb{x}(t)=(t-1)\mb{a}+t\mb{b}.
\end{equation}
For $t=0$ the straight line passes through $\mb{a}$, and for $t=1$
it passes through $\mb{b}$. For $0\le t\le 1$ the point $\mb{x}$
is between $\mb{a}$ and $\mb{b}$, while for all other values of $t$
it is outside (see Figure 1).
\begin{center}
\begin{lapdf}(6,3.6)(0,-0.3)
  \Dash(0)
  \Red
  \Line(0,0)(6,3) \Stroke
  \Point(1)(1,0.5)
  \Point(0)(2.5,1.25)
  \Point(1)(5,2.5)
  \Text(1,0.7,bc){$\mb{a}$}
  \Text(2.5,1.45,bc){$\mb{x}$}
  \Text(5,2.7,bc){$\mb{b}$}
  \Text(1.8,0.5,bc){$t$}
  \Text(2.5,0.7,bc){:}
  \Text(4.1,1.5,bc){$1-t$}
\end{lapdf}

\it{\bf{Figure 1}: Line interpolation on a straight line}
\end{center}
The point $\mb{x}$ divides the straight line segment between $\mb{a}$
and $\mb{b}$ in the ratio $t:1-t$ and any point on the straight line can be
calculated by changing this parameter. If t lies between $\mb{a}$ and
$\mb{b}$, then $t\in [0,1]$. We can remove this restriction for $t$, if
we define $t=(u-a)/(b-a)$ with $u\in [a,b]$, we get:
\begin{equation}
  \mb{x}=\mb{x}(t)=\fr{b-u}{b-a}\mb{a}+\fr{u-a}{b-a}\mb{b}.
\end{equation}
For $u=a$ the point is $\mb{x}=\mb{a}$ and for $u=b$ it is $\mb{x}=\mb{b}$
accordingly. Notice, that the value of the ratio $t:1-t$ did not change
after this reparametrisation.
\begin{equation}
  ratio(\mb{a,x,b}):=\fr{t}{1-t}=\fr{u-a}{b-u}.
\end{equation}
One of the most fundamental properties of the linear interpolation is its
\it{affine invariance}. This means, if you apply any affine map like
translation, scaling, rotation, shearing or parallel projection to the
points and then calculate $\mb{x}$, the result will the same as if you first
calculated the point and then applied the affine map to the three points.

It should also be mentioned, that from a numerical point of view the linear
interpolation is a stable mathematical operation. This means that small changes
in the supplied values never lead to sudden great changes in the result. The well
known Horner's schema for instance, which can be used to evaluate polynomials,
is a bad example in this area.

\section{Quadratic Bezier Curves}
We now want to use the results from the linear case to develop the
most elementary nonlinear curve form, the \it{parabola}. The main idea
is very simple: we use repeated linear interpolations to compute a point
on a parabola (a quadratic curve). Let $\mb{p}_0,\mb{p}_1,\mb{p}_2$ be
three given points and let $t\in \mb{\Re}$. Now we build:
\begin{eqnarray*}
  \mb{p}_0^1(t) & = & (1-t)\mb{p}_0+t\mb{p}_1 \\
  \mb{p}_1^1(t) & = & (1-t)\mb{p}_1+t\mb{p}_2 \\
  \mb{p}_0^2(t) & = & (1-t)\mb{p}_0^1(t)+t\mb{p}_1^1(t).
\end{eqnarray*}
Inserting the first two equations into the third one, we get:
\begin{eqnarray}
  \mb{p}_0^2(t) & = & (1-t)^2\mb{p}_0+2(1-t)t\mb{p}_1+t^2\mb{p}_2.
\end{eqnarray}
This formula represents a quadratic expression in $t$. We use the
superscript here to denote the curve degree. So, we can say that
$\mb{p}_0^2$ traces out a parabolic curve, if $t$ varies from $-\infty$
to $+\infty$. The first three expressions clearly show that we only used
repeated linear interpolation to compute a curve point and we can state,
that this curve construction is \it{affine invariant}. Look at Figure 2
for the geometric construction of the curve point $\mb{p}_0^2$ for $t=1/3$.
\begin{center}
\begin{lapdf}(10,7.6)(0,0.2)
  \Setwidth(0.01)
  \Black
  \Polygon(1,2)(7,7)(9,1) \Stroke
  \Dash(1)
  \Line(3,3.667)(7.667,5) \Stroke
  \Dash(0)
  \Setwidth(0.02)
  \Red
  \Curve(64)(1,2)(7,7)(9,1) \Stroke
  \Point(1)(1,2)
  \Point(1)(7,7)
  \Point(1)(9,1)
  \Point(1)(3,3.667)
  \Point(1)(7.667,5)
  \Point(0)(4.556,4.111)
  \Text(1,1.6,bc){$\mb{p}_0$}
  \Text(7,7.2,bc){$\mb{p}_1$}
  \Text(9,0.6,bc){$\mb{p}_2$}
  \Text(2.7,3.7,bc){$\mb{p}_0^1$}
  \Text(8,4.9,bc){$\mb{p}_1^1$}
  \Text(4.556,3.62,bc){$\mb{p}_0^2$}
\end{lapdf}

\it{\bf{Figure 2}: Repeated Line interpolation on a parabola}
\end{center}
For $t\in [0,1]$ the curve lies in the triangle formed by
$\mb{p}_0,\mb{p}_1,\mb{p}_2$. This is called the \it{convex hull property}.
As special points we have $\mb{p}^2(0)=\mb{p}_0$ and $\mb{p}^2(1)=\mb{p}_2$.
If the point $\mb{p}_1$ only lies on the curve, it must be a straight line.
The construction also shows the following property:
\begin{equation}
  ratio(\mb{p}_0,\mb{p}_0^1,\mb{p}_1)=ratio(\mb{p}_1,\mb{p}_1^1,\mb{p}_2)
  =ratio(\mb{p}_0^1,\mb{p}_0^2,\mb{p}_1^1)=\fr{t}{1-t}.
\end{equation}
All ratios are equal, this proves the affine invariance of the curve
construction. If you look at the generated curve, you see that for $t=0$
the curve is tangent to the line $\mb{p}_0\mb{p}_1$ and for $t=1$ it is
tangent to the line $\mb{p}_1\mb{p}_2$. We come back to this fact later.

The geometric construction is based on the principle of repeated linear
interpolation and the curve point is obtained by the last interpolation.
This principle is the underlying concept for the construction of all
\it{bezier curves} of any degree $n$. If we want to construct an $n$
degree curve, we need $n+1$ \it{control points}. The number of linear
interpolations, needed to compute a point on a curve of degree $n$, is:
\begin{equation}
  N=\fr{n(n+1)}{2}
\end{equation}

\section{Cubic Bezier Curves}
Parabolas cannot form real space curves, because the three control points
always build a plane. This leads us to the next class of curves, the cubic
curves.

Here we have four control points $\mb{p}_0,\mb{p}_1,\mb{p}_2,,\mb{p}_3$
and let $t\in \mb{\Re}$. We compute a curve point with the following
construction:
\begin{eqnarray*}
  \mb{p}_0^1(t) & = & (1-t)\mb{p}_0+t\mb{p}_1 \\
  \mb{p}_1^1(t) & = & (1-t)\mb{p}_1+t\mb{p}_2 \\
  \mb{p}_2^1(t) & = & (1-t)\mb{p}_2+t\mb{p}_3 \\
  \mb{p}_0^2(t) & = & (1-t)\mb{p}_0^1(t)+t\mb{p}_1^1(t) \\
  \mb{p}_1^2(t) & = & (1-t)\mb{p}_1^1(t)+t\mb{p}_2^1(t) \\
  \mb{p}_0^3(t) & = & (1-t)\mb{p}_0^2(t)+t\mb{p}_1^2(t).
\end{eqnarray*}
Inserting the first three equations into the next two, we obtain:
\begin{eqnarray*}
  \mb{p}_0^2(t) & = & (1-t)^2\mb{p}_0+2(1-t)t\mb{p}_1+t^2\mb{p}_2 \\
  \mb{p}_1^2(t) & = & (1-t)^2\mb{p}_1+2(1-t)t\mb{p}_2+t^2\mb{p}_3.
\end{eqnarray*}
Again, we insert these two equations into the last one, and get this:
\begin{eqnarray*}
  \mb{p}_0^3(t) & = & (1-t)^3\mb{p}_0+2(1-t)^2t\mb{p}_1+(1-t)t^2\mb{p}_2
  +(1-t)^2t\mb{p}_1+2(1-t)t^2\mb{p}_2+t^3\mb{p}_3.
\end{eqnarray*}
After some simplifications, we obtain this result:
\begin{eqnarray}
  \mb{p}_0^3(t)=(1-t)^3\mb{p}_0+3(1-t)^2t\mb{p}_1+3(1-t)t^2\mb{p}_2
  +t^3\mb{p}_3.
\end{eqnarray}
Now, $\mb{p}_0^3$ is our point on the curve at parameter value $t$ and
we see that the construction is principally the same as in the quadratic
case. In Figure 3 you see the geometric construction for $t=1/2$:
\begin{center}
\begin{lapdf}(10,7.4)(0,0.3)
  \Setwidth(0.01)
  \Black
  \Polygon(1,2)(4,7)(8,6)(9,1) \Stroke
  \Dash(1)
  \Polygon(2.5,4.5)(6,6.5)(8.5,3.5) \Stroke
  \Line(4.25,5.5)(7.25,5) \Stroke
  \Dash(0)
  \Setwidth(0.02)
  \Red
  \Curve(64)(1,2)(4,7)(8,6)(9,1) \Stroke
  \Point(1)(1,2)
  \Point(1)(4,7)
  \Point(1)(8,6)
  \Point(1)(9,1)
  \Point(1)(2.5,4.5)
  \Point(1)(6,6.5)
  \Point(1)(8.5,3.5)
  \Point(1)(4.25,5.5)
  \Point(1)(7.25,5)
  \Point(0)(5.75,5.25)
  \Text(1,1.6,bc){$\mb{p}_0$}
  \Text(4,7.2,bc){$\mb{p}_1$}
  \Text(8,6.2,bc){$\mb{p}_2$}
  \Text(9,0.6,bc){$\mb{p}_3$}
  \Text(2.2,4.5,bc){$\mb{p}_0^1$}
  \Text(6,6.7,bc){$\mb{p}_1^1$}
  \Text(8.8,3.5,bc){$\mb{p}_2^1$}
  \Text(4.0,5.6,bc){$\mb{p}_0^2$}
  \Text(7.5,5.1,bc){$\mb{p}_1^2$}
  \Text(5.75,4.7,bc){$\mb{p}_0^3$}
\end{lapdf}

\it{\bf{Figure 3}: Repeated Line interpolation on a cubic}
\end{center}
From equation (7) we see, that this is a cubic expression in $t$, so
the obtained curve is a cubic curve. This is the first curve form that
can build space curves, because four control points can live in space
and not only in a plane.

This curve is also affine invariant and we need 6 linear interpolations,
to compute a point $\mb{p}_0^3$ on the curve. If we look at the curve
form, we see that for $t=0$ the curve is tangent to the line
$\mb{p}_0\mb{p}_1$ and for $t=1$ it is tangent to the line
$\mb{p}_1\mb{p}_2$. We already mentioned this fact for the parabola.
Cubic curve are always inside the convex hull of the four control points.

Parametric cubic curves have much more form variations than parabolas,
they can have inflection points, nodes (points of self intersection)
or even a cusp (point, in which the curve has two tangents). Therefore
these cubic curves are used as the major curve forms in Postscript, PDF
or in vector drawing and CAD programs.

\section{Rational Quadratic Bezier Curves}
As last curve form I want to introduce rational quadratic bezier curves.
They are very important, because they can exactly produce conic curves like
parabolas, hyperbolas, ellipses and circles.

These curves are a generalisation of their so called integral counterparts,
because they include them but they have even more form variations than
the integral bezier curves.

Generally spoken, rational curves lie in another space as integral curves.
If you draw a circle on a piece of paper and rotate the paper in front of
your eyes, you'll see an ellipse. It's a so called projection of the circle.
If you repeat this experiment with a parabola, you might see a hyperbola.
If we look at this subject backwards, we can state that every rational
quadratic bezier curve in 3D-space can be seen as a projection of an
integral quadratic bezier curve in the plane. This is fundamental for the
understanding of rational bezier curves.

We can deal with rational curves just the way we did with integral curves,
but we have to put them first in a so called homogeneous space. This has
one more coordinate, the weight of a point. In the rational case, every
bezier point has an $x$-value, an $y$-value and a weight $w$. In normal
space, each point of a bezier curve has the weight $w=1$. This weight can
be interpreted as the $z$-coordinate of a point.

Here is the mathematical description of a rational quadratic bezier curve:
\begin{eqnarray}
  \mb{p}(t) & = & \fr{(1-t)^2w_0\mb{p}_0+2(1-t)tw_1\mb{p}_1+t^2w_2\mb{p}_2}
     {(1-t)^2w_0+2(1-t)tw_1+t^2w_2}.
\end{eqnarray}
As you can see, every point is associated with it's own weight. This is the
general form of a rational quadratic bezier curve. With some more involved
math it can be translated into a simpler form, which is called the
\it{standard form} and it looks like this:
\begin{eqnarray}
  \mb{p}(t) & = & \fr{(1-t)^2\mb{p}_0+2(1-t)tw\mb{p}_1+t^2\mb{p}_2}
     {(1-t)^2+2(1-t)tw+t^2}.
\end{eqnarray}
The outer weights $w_0$ and $w_2$ are gone (their value is 1) and the central inner weight is transformed to $w$. The term \it{rational} simply reflects the fact, that every rational bezier curve is build from a rational expression, which is much more complicated then the expression for integral curves.

But now comes the magic of homogeneous coordinates. If we do the following
transformation at the very beginning of our curve calculation:
\begin{eqnarray}
  x \rightarrow x \cdot w & y \rightarrow y \cdot w & z \rightarrow w,
\end{eqnarray}
we can compute the curve points without any fractional math in the same way
as we did in the integral case. But before we draw the point, we have to
transform it back to the so called affine space (here: our normal 2D-space)
with the following caculations:
\begin{eqnarray}
  x \rightarrow x / w & y \rightarrow y / w & z \rightarrow 1,
\end{eqnarray}
I'm not going to explain the mathematical background, but I want to mention
that this is the reason, why homogeneous coordinates are used in so many
advanced graphic algorithms. If we go back to our paper example, we can say
that changing from affine space to homogeneous space is like the projective
view of the original shape and changing it back gives us the original. In the style file you can look up the |Rcurve| macro to see how this is
implemented in \TeX. \it{Figure 4} shows several conic curves, which all share the same bezier points, only the inner weight $w$ changes.
\begin{center}
\begin{lapdf}(11,9.5)(-5.5,-3.3)
  \Setwidth(0.01)
  \Black
  \Polygon(-5,0.5)(2,6)(5,-0.5) \Stroke
  \Dash(1)
  \Line(-1,-3)(2,6) \Stroke
  \Dash(0)
  \Setwidth(0.02)
  \Red
  \Rcurve(64)(-5,0.5,1)(2,6,3)(5,-0.5,1) \Stroke
  \Green
  \Rcurve(64)(-5,0.5,1)(2,6,1)(5,-0.5,1) \Stroke
  \Blue
  \Rcurve(64)(-5,0.5,3)(2,6,1)(5,-0.5,3) \Stroke
  \Cyan
  \Rcurve(64)(-5,0.5,3)(2,6,0)(5,-0.5,1) \Stroke
  \Magenta
  \Rcurve(96)(-5,0.5,3)(2,6,-1)(5,-0.5,3) \Stroke
  \Point(1)(-5,0.5)
  \Point(1)(2,6)
  \Point(1)(5,-0.5)
  \Point(1)(1.5,4.5)
  \Point(1)(1,3)
  \Point(1)(0.5,1.5)
  \Point(1)(0,0)
  \Point(1)(-1,-3)
  \Text(-5.1,0.55,br){$P_0$}
  \Text(2,6.2,bc){$P_1$}
  \Text(5.1,-0.5,bl){$P_2$}
  \Text(-0.9,-3,bl){$-1/3$}
  \Text(0.15,0.05,bl){$w=0$}
  \Text(0.65,1.5,bl){$1/3$}
  \Text(1.15,3.05,bl){$1$}
  \Text(1.62,4.55,bl){$3$}
  \Text(-5.6,5.5,tl){$w^2>1$: Hyperbola}
  \Text(-5.6,4.9,tl){$w^2=1$: Parabola}
  \Text(-5.6,4.3,tl){$w^2<1$: Ellipse}
  \Text(-5.6,3.7,tl){$w^2=0$: Line}
\end{lapdf}

\it{\bf{Figure 4}: Various conic arcs defined by $w=(3,1,1/3,0,-1/3)$}.
\end{center}
To the left of the picture is the curve form classification corresponding to
different values of $w$. You may ask now: ``\it{Where is the circle?}''. Well, that's no real problem. Without any proof here follows the answer. Let's first name the angle, formed by the bezier polygon. We call it $a$. As we saw before, the circle is simply a special case of an ellipse. The ellipse is actually a circle, if the following condition holds:
\begin{eqnarray}
  w & = & \cos(a).
\end{eqnarray}
Here is an example of a circle, build with two rational quadratic bezier curves:
\begin{center}
\begin{lapdf}(6,8)(-3,-2.6)
  \Setwidth(0.01)
  \Black
  \Polygon(+2.167,+1.25)(+0.00,+5.0)(-2.167,+1.25) \Stroke
  \Setwidth(0.02)
  \Red
  \Rmoveto(+2.167,+1.25,2)
  \Rcurveto(64)(+0.00,+5.0,1)(-2.167,+1.25,2)
  \Rcurveto(96)(+0.00,+5.0,-1)(+2.167,+1.25,2) \Stroke
  \Point(1)(+2.167,+1.25)
  \Point(1)(+0.00,+5.0)
  \Point(1)(-2.167,+1.25)
  \Text(0,4.6,tc){$a$}
  \Text(1,4.73,tl){$w=\cos 60^\circ=0.5$}
  \Text(0,2.2,tc){$w=0.5$}
  \Text(0,-2.2,bc){$w=-0.5$}
  \Text(-2.24,+1.29,br){$P_0$}
  \Text(+0.05,+5.13,bc){$P_1$}
  \Text(+2.22,+1.28,bl){$P_2$}
\end{lapdf}

\it{\bf{Figure 5}: A full circle with two rational quadratic bezier curves.}
\end{center}
Both curves share the same bezier points, but the lower one (the complementary curve) has negative weight $-w$. Everytime you want to draw the complementary rational curve, you only have to negate the weight value.

Now it's up to you. I hope, this short introduction into the world of bezier
curves has risen your appetite. There are many good books around, which deal
with this subject. Look at the end of this paper for some suggestions.

\section{Additional Readings}
Depending on the levels of insight you want to achieve, there are lots of
good books and free literature on the market and on the internet. I want
to give you some suggestions for literature, that will help you to learn
more about graphics programming.

\begin{thebibliography}{0}
  \bibitem{1} MORTENSON M.E.: \textsl{Mathematics for Computer Graphics
  Applications},
  Industrial Press, Inc., 2 ed. 1999.

  \bibitem{2} FOLEY, VAN DAM.: \textsl{Computer Graphics -- Principles
   and Practice}, Addison-Wesley, 2 ed. 1996.

  \bibitem{3} PAETH, ALAN W.: \textsl{Graphics GEMS I-V},
  AP Professional, 1995.

  \bibitem{4} ABRASH, MICHAEL.: \textsl{Graphics Programming Black Book},
  Coriolis Group Books, 1997.

  \bibitem{5} FARIN G.: \it{Curves and Surfaces For Computer Aided
   Geometric Design -- A Practical Guide}, Academic Press, 2 ed. 1999.

  \bibitem{6} FARIN G.: \it{NURBS -- from Projective Geometry to
   Practical Use}, A K Peters Ltd., Natick, MA, 2 ed. 1990.

  \bibitem{7} PIEGL L. \& TILLER W.: \it{The NURBS Book}, Springer, 2 ed. 1997.
\end{thebibliography}

\end{document}