chapters/Background_Bezier.tex

   1 A Bezier Curve of degree $n$ is defined by $n$ ``control points'' $\left\{P_0, ... P_n\right\}$.
   2 Points $P(t)$ along the curve are defined by:
   3 \begin{align}
   4         P(t) &= \displaystyle\sum_{j=0}^{n} B_j^n(t) P_j
   5 \end{align}
   6
   7 From this definition it should be apparent $P(t)$ for a Bezier Curve of degree $0$ maps to a single point, whilst $P(t)$ for a Bezier of degree $1$ is a straight line between $P_0$ and $P_1$. $P(t)$ always begins at $P_0$ for $t = 0$ and ends at $P_n$ when $t = 1$.
   8
   9 Figure \ref{bezier_3} shows a Bezier Curve defined by the points $\left\{(0,0), (1,0), (1,1)\right\}$.
  10
  11 A straightforward algorithm for rendering Bezier's is to simply sample $P(t)$ for some number of values of $t$ and connect the resulting points with straight lines using Bresenham or Wu's algorithm (See Section \ref{Straight Lines}). Whilst the performance of this algorithm is linear, in ???? De Casteljau derived a more efficient means of sub dividing beziers into line segments.
  12
  13 Recently, Goldman presented an argument that Bezier's could be considered as fractal in nature, a fractal being the fixed point of an iterated function system\cite{goldman_thefractal}. Goldman's proof depends upon a modification to the De Casteljau Subdivision algorithm which expresses the subdivisions as an iterated function system. The cost of this modification is that the algorithm is no longer $O(n)$ but $O(n^2)$; although it is not explicitly stated by Goldman it seems clear that the modified algorithm is mainly of theoretical interest.
  14