lapdf is back (2sep11)

git-svn-id: svn://tug.org/texlive/trunk@23806 c570f23f-e606-0410-a88d-b1316a301751

1 files changed, 433 insertions, 0 deletions

diff --git a/Master/texmf-dist/doc/latex/lapdf/bezinfo.tex b/Master/texmf-dist/doc/latex/lapdf/bezinfo.tex
new file mode 100644
index 00000000000..9cee401ee4f
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/lapdf/bezinfo.tex
@@ -0,0 +1,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}