Debian Codegraph @

texmf-dist/doc/latex/lapdf/bezinfo.tex

raw
1 \documentclass[titlepage,a4paper,11pt]{report}
2 \usepackage{shortvrb}
3 \usepackage{array}
4 \usepackage[color]{lapdf}
5
6 \textheight24.92cm
7 \textwidth15.92cm
8 \oddsidemargin0cm
9 \evensidemargin0cm
10 \topmargin-0.3cm
11 \headheight0cm
12 \topskip0cm
13 \headsep0cm
14 \unitlength1cm
15
16 \MakeShortVerb{\|}
17
18 \def\it{\textit}
19 \def\tt{\texttt}
20 \def\sf{\textsf}
21 \def\bf{\textbf}
22 \def\em{\textit}
23 \def\mr{\mathrm}
24 \def\mb{\mathbf}
25 \def\fr{\frac}
26 \def\qq{\qquad}
27
28 \def\syn{\item[Syntax]}
29 \def\fun{\item[Function]}
30 \def\exa{\item[Example]}
31 \def\see{\item[See Also]}
32
33 % -------------------------------------------
34 \title{
35 \bf{\Huge Bezier Curves} \\ \vspace{0.6cm}
36 \bf{An Introduction}}
37 \author{ \\
38 Detlef Reimers\\
39 [email protected]\\
40 http://detlefreimers.de}
41 \date{\today}
42
43 % -------------------------------------------------------------------------
44 \begin{document}
45
46 \parindent0cm
47 \maketitle
48
49 % -------------------------------------------------------------------------
50 \chapter{Bezier Curve Basics}
51 \section{Linear Interpolation}
52 This section will give you a basic introduction to bezier curves. We begin
53 with the simplest curve form, a straight line. We can express any point
54 $\mb{x}$ on this straight line by the two given points and the parameter $t$:
55 \begin{equation}
56 \mb{x}=\mb{x}(t)=(t-1)\mb{a}+t\mb{b}.
57 \end{equation}
58 For $t=0$ the straight line passes through $\mb{a}$, and for $t=1$
59 it passes through $\mb{b}$. For $0\le t\le 1$ the point $\mb{x}$
60 is between $\mb{a}$ and $\mb{b}$, while for all other values of $t$
61 it is outside (see Figure 1).
62 \begin{center}
63 \begin{lapdf}(6,3.6)(0,-0.3)
64 \Dash(0)
65 \Red
66 \Line(0,0)(6,3) \Stroke
67 \Point(1)(1,0.5)
68 \Point(0)(2.5,1.25)
69 \Point(1)(5,2.5)
70 \Text(1,0.7,bc){$\mb{a}$}
71 \Text(2.5,1.45,bc){$\mb{x}$}
72 \Text(5,2.7,bc){$\mb{b}$}
73 \Text(1.8,0.5,bc){$t$}
74 \Text(2.5,0.7,bc){:}
75 \Text(4.1,1.5,bc){$1-t$}
76 \end{lapdf}
77
78 \it{\bf{Figure 1}: Line interpolation on a straight line}
79 \end{center}
80 The point $\mb{x}$ divides the straight line segment between $\mb{a}$
81 and $\mb{b}$ in the ratio $t:1-t$ and any point on the straight line can be
82 calculated by changing this parameter. If t lies between $\mb{a}$ and
83 $\mb{b}$, then $t\in [0,1]$. We can remove this restriction for $t$, if
84 we define $t=(u-a)/(b-a)$ with $u\in [a,b]$, we get:
85 \begin{equation}
86 \mb{x}=\mb{x}(t)=\fr{b-u}{b-a}\mb{a}+\fr{u-a}{b-a}\mb{b}.
87 \end{equation}
88 For $u=a$ the point is $\mb{x}=\mb{a}$ and for $u=b$ it is $\mb{x}=\mb{b}$
89 accordingly. Notice, that the value of the ratio $t:1-t$ did not change
90 after this reparametrisation.
91 \begin{equation}
92 ratio(\mb{a,x,b}):=\fr{t}{1-t}=\fr{u-a}{b-u}.
93 \end{equation}
94 One of the most fundamental properties of the linear interpolation is its
95 \it{affine invariance}. This means, if you apply any affine map like
96 translation, scaling, rotation, shearing or parallel projection to the
97 points and then calculate $\mb{x}$, the result will the same as if you first
98 calculated the point and then applied the affine map to the three points.
99
100 It should also be mentioned, that from a numerical point of view the linear
101 interpolation is a stable mathematical operation. This means that small changes
102 in the supplied values never lead to sudden great changes in the result. The well
103 known Horner's schema for instance, which can be used to evaluate polynomials,
104 is a bad example in this area.
105
106 \section{Quadratic Bezier Curves}
107 We now want to use the results from the linear case to develop the
108 most elementary nonlinear curve form, the \it{parabola}. The main idea
109 is very simple: we use repeated linear interpolations to compute a point
110 on a parabola (a quadratic curve). Let $\mb{p}_0,\mb{p}_1,\mb{p}_2$ be
111 three given points and let $t\in \mb{\Re}$. Now we build:
112 \begin{eqnarray*}
113 \mb{p}_0^1(t) & = & (1-t)\mb{p}_0+t\mb{p}_1 \\
114 \mb{p}_1^1(t) & = & (1-t)\mb{p}_1+t\mb{p}_2 \\
115 \mb{p}_0^2(t) & = & (1-t)\mb{p}_0^1(t)+t\mb{p}_1^1(t).
116 \end{eqnarray*}
117 Inserting the first two equations into the third one, we get:
118 \begin{eqnarray}
119 \mb{p}_0^2(t) & = & (1-t)^2\mb{p}_0+2(1-t)t\mb{p}_1+t^2\mb{p}_2.
120 \end{eqnarray}
121 This formula represents a quadratic expression in $t$. We use the
122 superscript here to denote the curve degree. So, we can say that
123 $\mb{p}_0^2$ traces out a parabolic curve, if $t$ varies from $-\infty$
124 to $+\infty$. The first three expressions clearly show that we only used
125 repeated linear interpolation to compute a curve point and we can state,
126 that this curve construction is \it{affine invariant}. Look at Figure 2
127 for the geometric construction of the curve point $\mb{p}_0^2$ for $t=1/3$.
128 \begin{center}
129 \begin{lapdf}(10,7.6)(0,0.2)
130 \Setwidth(0.01)
131 \Black
132 \Polygon(1,2)(7,7)(9,1) \Stroke
133 \Dash(1)
134 \Line(3,3.667)(7.667,5) \Stroke
135 \Dash(0)
136 \Setwidth(0.02)
137 \Red
138 \Curve(64)(1,2)(7,7)(9,1) \Stroke
139 \Point(1)(1,2)
140 \Point(1)(7,7)
141 \Point(1)(9,1)
142 \Point(1)(3,3.667)
143 \Point(1)(7.667,5)
144 \Point(0)(4.556,4.111)
145 \Text(1,1.6,bc){$\mb{p}_0$}
146 \Text(7,7.2,bc){$\mb{p}_1$}
147 \Text(9,0.6,bc){$\mb{p}_2$}
148 \Text(2.7,3.7,bc){$\mb{p}_0^1$}
149 \Text(8,4.9,bc){$\mb{p}_1^1$}
150 \Text(4.556,3.62,bc){$\mb{p}_0^2$}
151 \end{lapdf}
152
153 \it{\bf{Figure 2}: Repeated Line interpolation on a parabola}
154 \end{center}
155 For $t\in [0,1]$ the curve lies in the triangle formed by
156 $\mb{p}_0,\mb{p}_1,\mb{p}_2$. This is called the \it{convex hull property}.
157 As special points we have $\mb{p}^2(0)=\mb{p}_0$ and $\mb{p}^2(1)=\mb{p}_2$.
158 If the point $\mb{p}_1$ only lies on the curve, it must be a straight line.
159 The construction also shows the following property:
160 \begin{equation}
161 ratio(\mb{p}_0,\mb{p}_0^1,\mb{p}_1)=ratio(\mb{p}_1,\mb{p}_1^1,\mb{p}_2)
162 =ratio(\mb{p}_0^1,\mb{p}_0^2,\mb{p}_1^1)=\fr{t}{1-t}.
163 \end{equation}
164 All ratios are equal, this proves the affine invariance of the curve
165 construction. If you look at the generated curve, you see that for $t=0$
166 the curve is tangent to the line $\mb{p}_0\mb{p}_1$ and for $t=1$ it is
167 tangent to the line $\mb{p}_1\mb{p}_2$. We come back to this fact later.
168
169 The geometric construction is based on the principle of repeated linear
170 interpolation and the curve point is obtained by the last interpolation.
171 This principle is the underlying concept for the construction of all
172 \it{bezier curves} of any degree $n$. If we want to construct an $n$
173 degree curve, we need $n+1$ \it{control points}. The number of linear
174 interpolations, needed to compute a point on a curve of degree $n$, is:
175 \begin{equation}
176 N=\fr{n(n+1)}{2}
177 \end{equation}
178
179 \section{Cubic Bezier Curves}
180 Parabolas cannot form real space curves, because the three control points
181 always build a plane. This leads us to the next class of curves, the cubic
182 curves.
183
184 Here we have four control points $\mb{p}_0,\mb{p}_1,\mb{p}_2,,\mb{p}_3$
185 and let $t\in \mb{\Re}$. We compute a curve point with the following
186 construction:
187 \begin{eqnarray*}
188 \mb{p}_0^1(t) & = & (1-t)\mb{p}_0+t\mb{p}_1 \\
189 \mb{p}_1^1(t) & = & (1-t)\mb{p}_1+t\mb{p}_2 \\
190 \mb{p}_2^1(t) & = & (1-t)\mb{p}_2+t\mb{p}_3 \\
191 \mb{p}_0^2(t) & = & (1-t)\mb{p}_0^1(t)+t\mb{p}_1^1(t) \\
192 \mb{p}_1^2(t) & = & (1-t)\mb{p}_1^1(t)+t\mb{p}_2^1(t) \\
193 \mb{p}_0^3(t) & = & (1-t)\mb{p}_0^2(t)+t\mb{p}_1^2(t).
194 \end{eqnarray*}
195 Inserting the first three equations into the next two, we obtain:
196 \begin{eqnarray*}
197 \mb{p}_0^2(t) & = & (1-t)^2\mb{p}_0+2(1-t)t\mb{p}_1+t^2\mb{p}_2 \\
198 \mb{p}_1^2(t) & = & (1-t)^2\mb{p}_1+2(1-t)t\mb{p}_2+t^2\mb{p}_3.
199 \end{eqnarray*}
200 Again, we insert these two equations into the last one, and get this:
201 \begin{eqnarray*}
202 \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
203 +(1-t)^2t\mb{p}_1+2(1-t)t^2\mb{p}_2+t^3\mb{p}_3.
204 \end{eqnarray*}
205 After some simplifications, we obtain this result:
206 \begin{eqnarray}
207 \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
208 +t^3\mb{p}_3.
209 \end{eqnarray}
210 Now, $\mb{p}_0^3$ is our point on the curve at parameter value $t$ and
211 we see that the construction is principally the same as in the quadratic
212 case. In Figure 3 you see the geometric construction for $t=1/2$:
213 \begin{center}
214 \begin{lapdf}(10,7.4)(0,0.3)
215 \Setwidth(0.01)
216 \Black
217 \Polygon(1,2)(4,7)(8,6)(9,1) \Stroke
218 \Dash(1)
219 \Polygon(2.5,4.5)(6,6.5)(8.5,3.5) \Stroke
220 \Line(4.25,5.5)(7.25,5) \Stroke
221 \Dash(0)
222 \Setwidth(0.02)
223 \Red
224 \Curve(64)(1,2)(4,7)(8,6)(9,1) \Stroke
225 \Point(1)(1,2)
226 \Point(1)(4,7)
227 \Point(1)(8,6)
228 \Point(1)(9,1)
229 \Point(1)(2.5,4.5)
230 \Point(1)(6,6.5)
231 \Point(1)(8.5,3.5)
232 \Point(1)(4.25,5.5)
233 \Point(1)(7.25,5)
234 \Point(0)(5.75,5.25)
235 \Text(1,1.6,bc){$\mb{p}_0$}
236 \Text(4,7.2,bc){$\mb{p}_1$}
237 \Text(8,6.2,bc){$\mb{p}_2$}
238 \Text(9,0.6,bc){$\mb{p}_3$}
239 \Text(2.2,4.5,bc){$\mb{p}_0^1$}
240 \Text(6,6.7,bc){$\mb{p}_1^1$}
241 \Text(8.8,3.5,bc){$\mb{p}_2^1$}
242 \Text(4.0,5.6,bc){$\mb{p}_0^2$}
243 \Text(7.5,5.1,bc){$\mb{p}_1^2$}
244 \Text(5.75,4.7,bc){$\mb{p}_0^3$}
245 \end{lapdf}
246
247 \it{\bf{Figure 3}: Repeated Line interpolation on a cubic}
248 \end{center}
249 From equation (7) we see, that this is a cubic expression in $t$, so
250 the obtained curve is a cubic curve. This is the first curve form that
251 can build space curves, because four control points can live in space
252 and not only in a plane.
253
254 This curve is also affine invariant and we need 6 linear interpolations,
255 to compute a point $\mb{p}_0^3$ on the curve. If we look at the curve
256 form, we see that for $t=0$ the curve is tangent to the line
257 $\mb{p}_0\mb{p}_1$ and for $t=1$ it is tangent to the line
258 $\mb{p}_1\mb{p}_2$. We already mentioned this fact for the parabola.
259 Cubic curve are always inside the convex hull of the four control points.
260
261 Parametric cubic curves have much more form variations than parabolas,
262 they can have inflection points, nodes (points of self intersection)
263 or even a cusp (point, in which the curve has two tangents). Therefore
264 these cubic curves are used as the major curve forms in Postscript, PDF
265 or in vector drawing and CAD programs.
266
267 \section{Rational Quadratic Bezier Curves}
268 As last curve form I want to introduce rational quadratic bezier curves.
269 They are very important, because they can exactly produce conic curves like
270 parabolas, hyperbolas, ellipses and circles.
271
272 These curves are a generalisation of their so called integral counterparts,
273 because they include them but they have even more form variations than
274 the integral bezier curves.
275
276 Generally spoken, rational curves lie in another space as integral curves.
277 If you draw a circle on a piece of paper and rotate the paper in front of
278 your eyes, you'll see an ellipse. It's a so called projection of the circle.
279 If you repeat this experiment with a parabola, you might see a hyperbola.
280 If we look at this subject backwards, we can state that every rational
281 quadratic bezier curve in 3D-space can be seen as a projection of an
282 integral quadratic bezier curve in the plane. This is fundamental for the
283 understanding of rational bezier curves.
284
285 We can deal with rational curves just the way we did with integral curves,
286 but we have to put them first in a so called homogeneous space. This has
287 one more coordinate, the weight of a point. In the rational case, every
288 bezier point has an $x$-value, an $y$-value and a weight $w$. In normal
289 space, each point of a bezier curve has the weight $w=1$. This weight can
290 be interpreted as the $z$-coordinate of a point.
291
292 Here is the mathematical description of a rational quadratic bezier curve:
293 \begin{eqnarray}
294 \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}
295 {(1-t)^2w_0+2(1-t)tw_1+t^2w_2}.
296 \end{eqnarray}
297 As you can see, every point is associated with it's own weight. This is the
298 general form of a rational quadratic bezier curve. With some more involved
299 math it can be translated into a simpler form, which is called the
300 \it{standard form} and it looks like this:
301 \begin{eqnarray}
302 \mb{p}(t) & = & \fr{(1-t)^2\mb{p}_0+2(1-t)tw\mb{p}_1+t^2\mb{p}_2}
303 {(1-t)^2+2(1-t)tw+t^2}.
304 \end{eqnarray}
305 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.
306
307 But now comes the magic of homogeneous coordinates. If we do the following
308 transformation at the very beginning of our curve calculation:
309 \begin{eqnarray}
310 x \rightarrow x \cdot w & y \rightarrow y \cdot w & z \rightarrow w,
311 \end{eqnarray}
312 we can compute the curve points without any fractional math in the same way
313 as we did in the integral case. But before we draw the point, we have to
314 transform it back to the so called affine space (here: our normal 2D-space)
315 with the following caculations:
316 \begin{eqnarray}
317 x \rightarrow x / w & y \rightarrow y / w & z \rightarrow 1,
318 \end{eqnarray}
319 I'm not going to explain the mathematical background, but I want to mention
320 that this is the reason, why homogeneous coordinates are used in so many
321 advanced graphic algorithms. If we go back to our paper example, we can say
322 that changing from affine space to homogeneous space is like the projective
323 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
324 implemented in \TeX. \it{Figure 4} shows several conic curves, which all share the same bezier points, only the inner weight $w$ changes.
325 \begin{center}
326 \begin{lapdf}(11,9.5)(-5.5,-3.3)
327 \Setwidth(0.01)
328 \Black
329 \Polygon(-5,0.5)(2,6)(5,-0.5) \Stroke
330 \Dash(1)
331 \Line(-1,-3)(2,6) \Stroke
332 \Dash(0)
333 \Setwidth(0.02)
334 \Red
335 \Rcurve(64)(-5,0.5,1)(2,6,3)(5,-0.5,1) \Stroke
336 \Green
337 \Rcurve(64)(-5,0.5,1)(2,6,1)(5,-0.5,1) \Stroke
338 \Blue
339 \Rcurve(64)(-5,0.5,3)(2,6,1)(5,-0.5,3) \Stroke
340 \Cyan
341 \Rcurve(64)(-5,0.5,3)(2,6,0)(5,-0.5,1) \Stroke
342 \Magenta
343 \Rcurve(96)(-5,0.5,3)(2,6,-1)(5,-0.5,3) \Stroke
344 \Point(1)(-5,0.5)
345 \Point(1)(2,6)
346 \Point(1)(5,-0.5)
347 \Point(1)(1.5,4.5)
348 \Point(1)(1,3)
349 \Point(1)(0.5,1.5)
350 \Point(1)(0,0)
351 \Point(1)(-1,-3)
352 \Text(-5.1,0.55,br){$P_0$}
353 \Text(2,6.2,bc){$P_1$}
354 \Text(5.1,-0.5,bl){$P_2$}
355 \Text(-0.9,-3,bl){$-1/3$}
356 \Text(0.15,0.05,bl){$w=0$}
357 \Text(0.65,1.5,bl){$1/3$}
358 \Text(1.15,3.05,bl){$1$}
359 \Text(1.62,4.55,bl){$3$}
360 \Text(-5.6,5.5,tl){$w^2>1$: Hyperbola}
361 \Text(-5.6,4.9,tl){$w^2=1$: Parabola}
362 \Text(-5.6,4.3,tl){$w^2<1$: Ellipse}
363 \Text(-5.6,3.7,tl){$w^2=0$: Line}
364 \end{lapdf}
365
366 \it{\bf{Figure 4}: Various conic arcs defined by $w=(3,1,1/3,0,-1/3)$}.
367 \end{center}
368 To the left of the picture is the curve form classification corresponding to
369 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:
370 \begin{eqnarray}
371 w & = & \cos(a).
372 \end{eqnarray}
373 Here is an example of a circle, build with two rational quadratic bezier curves:
374 \begin{center}
375 \begin{lapdf}(6,8)(-3,-2.6)
376 \Setwidth(0.01)
377 \Black
378 \Polygon(+2.167,+1.25)(+0.00,+5.0)(-2.167,+1.25) \Stroke
379 \Setwidth(0.02)
380 \Red
381 \Rmoveto(+2.167,+1.25,2)
382 \Rcurveto(64)(+0.00,+5.0,1)(-2.167,+1.25,2)
383 \Rcurveto(96)(+0.00,+5.0,-1)(+2.167,+1.25,2) \Stroke
384 \Point(1)(+2.167,+1.25)
385 \Point(1)(+0.00,+5.0)
386 \Point(1)(-2.167,+1.25)
387 \Text(0,4.6,tc){$a$}
388 \Text(1,4.73,tl){$w=\cos 60^\circ=0.5$}
389 \Text(0,2.2,tc){$w=0.5$}
390 \Text(0,-2.2,bc){$w=-0.5$}
391 \Text(-2.24,+1.29,br){$P_0$}
392 \Text(+0.05,+5.13,bc){$P_1$}
393 \Text(+2.22,+1.28,bl){$P_2$}
394 \end{lapdf}
395
396 \it{\bf{Figure 5}: A full circle with two rational quadratic bezier curves.}
397 \end{center}
398 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.
399
400 Now it's up to you. I hope, this short introduction into the world of bezier
401 curves has risen your appetite. There are many good books around, which deal
402 with this subject. Look at the end of this paper for some suggestions.
403
404 \section{Additional Readings}
405 Depending on the levels of insight you want to achieve, there are lots of
406 good books and free literature on the market and on the internet. I want
407 to give you some suggestions for literature, that will help you to learn
408 more about graphics programming.
409
410 \begin{thebibliography}{0}
411 \bibitem{1} MORTENSON M.E.: \textsl{Mathematics for Computer Graphics
412 Applications},
413 Industrial Press, Inc., 2 ed. 1999.
414
415 \bibitem{2} FOLEY, VAN DAM.: \textsl{Computer Graphics -- Principles
416 and Practice}, Addison-Wesley, 2 ed. 1996.
417
418 \bibitem{3} PAETH, ALAN W.: \textsl{Graphics GEMS I-V},
419 AP Professional, 1995.
420
421 \bibitem{4} ABRASH, MICHAEL.: \textsl{Graphics Programming Black Book},
422 Coriolis Group Books, 1997.
423
424 \bibitem{5} FARIN G.: \it{Curves and Surfaces For Computer Aided
425 Geometric Design -- A Practical Guide}, Academic Press, 2 ed. 1999.
426
427 \bibitem{6} FARIN G.: \it{NURBS -- from Projective Geometry to
428 Practical Use}, A K Peters Ltd., Natick, MA, 2 ed. 1990.
429
430 \bibitem{7} PIEGL L. \& TILLER W.: \it{The NURBS Book}, Springer, 2 ed. 1997.
431 \end{thebibliography}
432
433 \end{document}