X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fsam.git;a=blobdiff_plain;f=chapters%2FBackground_Spline.tex;fp=chapters%2FBackground_Spline.tex;h=91244e4a8b3dce7cd1ae090cb44a48b1f0618cce;hp=0000000000000000000000000000000000000000;hb=3b509bbb92dc136e78e681973ca9ba364fa7be20;hpb=38a856db801fa59c8959d85dd3f8f83437710681

diff --git a/chapters/Background_Spline.tex b/chapters/Background_Spline.tex
new file mode 100644
index 0000000..91244e4
--- /dev/null
+++ b/chapters/Background_Spline.tex
@@ -0,0 +1,69 @@
+
+Splines are continuous curves formed from piecewise polynomial segments. A polynomial of $n$th degree is defined by $n$ constants $\{a_0, a_1, ... a_n\}$ and:
+\begin{align}
+	y(x) &= \displaystyle\sum_{k=0}^n a_k x^k
+\end{align}
+
+ \begin{comment}
+Splines may be rasterised by sampling of $y(x)$ at a number of points $x_i$ and drawing straight lines between  $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ as discussed in Section \ref{Straight Lines}.
+
+There are many different ways to define a spline.One approach is to specify ``knots'' on the curve and choosing a fixed $n$ ($n = 3$ for ``cubic'' splines) solve for the cooefficients to generate polynomials passing through the points. Alternatively, special polynomials may be defined using ``control'' points which themselves are not part of the curve; these are convenient for graphical based editors.\end{co B{\'e}zier splines are the most straight forward way to define a curve in the standards considered in Section \ref{Document Representations}. A spline defined from two cubic B{\'e}ziers is shown in Figure \ref{spline.pdf}
+\end{comment}
+
+Cubic and Quadratic B{\'e}zier Splines are used to define curved paths in the PostScript\cite{plrm}, PDF\cite{pdfref17} and SVG\cite{svg2011-1.1} standards which we will discuss in Section \ref{Document Representations}.  Cubic B{\'e}ziers are also used to define vector fonts for rendering text in these standards and the \TeX typesetting language \cite{knuth1983metafont, knuth1984texbook}. The usefulness of B{\'e}zier curves was realised by Pierre B{\'e}zier who used them in the 1960s for the computer aided design of automobile bodies\cite{bezier1986apersonal}. 
+
+A B{\'e}zier Curve of degree $n$ is defined by $n$ ``control points'' $\left\{P_0, ... P_n\right\}$. 
+Points $P(t) = (x(t), y(t))$ along the curve are defined by:
+\begin{align}
+	P(t) &= \displaystyle\sum_{j=0}^{n} B_j^n(t) P_j
+\end{align}
+Where $t \epsilon [0,1]$ is a control parameter. The polynomials $B_j^n(t)$ are Bernstein Basis Polynomials which are defined as:
+\begin{align}
+	B_j^n(t) &=  \left(^n_j\right) t^j\left(1-t\right)^{n-j} \quad \quad j=0,1,...,n \\
+	\text{Where } \left(^n_j\right) &= \frac{n!}{n!(n-j)!} \quad \text{ (The Binomial Coefficients)}
+\end{align}
+From these definitions it should be apparent that in all cases, $P(0) = P_0$ and $P(1) = P_n$. An $n = 1$ B{\'e}zier Curve is a straight line.
+
+Algorithms for rendering B{\'e}zier's may simply sample $P(t)$ for suffiently many values of $t$ --- enough so that the spacing between successive points is always less than one pixel distance. Alternately, a smaller number of points may be sampled with the resulting points connected by straight lines using one of the algorithms discussed in Section \ref{Straight Lines}.
+
+De Casteljau's algorithm of 1959 is often used for approximating B{\'e}ziers\cite{computergraphics2, knuth1983metafont}. This algorithm subdivides the original $n$ control points $\left\{P_0, ... P_n\right\}$ into $2n$ points $\left\{Q_0, ... Q_n\right\}$ and $\left\{R_0, ... R_n\right\}$; when iterated, the produced points will converge to $P(t)$. As a tensor equation this subdivision can be expressed as:
+\begin{align}
+	Q_i = \left(\frac{\left(^n_j\right)}{2^j}\right) P_i &\text{ and }	R_i = \left(\frac{\left(^{n-j}_{n-k}\right)}{2^{n-j}}\right) P_i
+\end{align}
+
+
+In much of the literature it is taken as trivial that it is only necessary to specify the control points of a B{\'e}zier in order to be able to render it at any level of detail\cite{knuth1983metafont, computergraphics2}. Recently, Goldman presented an argument that B{\'e}zier's could be considered as fractal in nature, because the De Casteljau algorithm may be modified to be expressed the polynomial $P(t)$ as the result of iterated function system\cite{goldman_thefractal}. If this argument is correct, any primitive that can be described soley in terms of B{\'e}zier Curves may also be considered as fractal in nature. Ideally all these primitives may be rendered at any level of detail or ``zoom'' desired; however, computation of the pixel locations of the curve will be subject to the precision limits of the numerical representation which is used; we discuss these issues in Section \ref{}.
+
+
+\begin{figure}[H]
+\centering
+\begin{minipage}[t]{0.3\textwidth}
+\begin{figure}[H]
+	\centering
+	\includegraphics[width=0.7\textwidth]{figures/spline_labelled.pdf}
+\end{figure}
+\end{minipage}
+\begin{minipage}[t]{0.3\textwidth}
+\begin{minted}{xml}
+<!-- DOM element in SVG used to construct the spline -->
+<path d="M 0,300 
+	C 0,300 200,210 90,140 
+	-20,70 200,0 200,0"
+	style="stroke:#000000; stroke-width:1px; 
+	fill:none;"/>
+\end{minted}
+\begin{minted}{postscript}
+% PostScript commands for a similar spline
+0 300 moveto 
+0 300 200 210 90 140 curveto 
+-20 70 200 0 200 0 curveto stroke 
+\end{minted}
+\end{minipage}
+\begin{minipage}[t]{0.3\textwidth}
+\begin{figure}[H]
+	\centering
+	\includegraphics[width=0.7\textwidth]{figures/spline.pdf}
+\end{figure}
+\end{minipage}
+	\caption{Constructing a Spline from two cubic B{\'e}ziers \\ (a) Showing the Control Points (b) Representations in SVG and PostScript (c) Rendered Spline}\label{spline.pdf}
+\end{figure}