\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#168: Cubic Bezier Curves on the Canvas}
\date{January 25, 2004}
\author{Lars Hellström}
\urlstyle{sf}
\setlength{\parskip}{1ex}
\setlength{\parindent}{0pt}
\def\tipversion$#1${\texttt{\$#1\$}}
\def\tiplangle#1{\ensuremath{<}}
\def\tiprangle#1{\ensuremath{>}}
\def\tipbar#1{\ensuremath{|}}
\def\tipmail#1#2{\(\langle\){\small\expandafter\url{#1@#2}}\(\rangle\)}
\ifx\pdfoutput\undefined
\newcommand{\tipimage}[2]{\typeout{Make sure you download #1.eps}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.eps}}{\includegraphics[width=0.8\textwidth]{#1.eps}}}
\newcommand{\tipxref}[1]{}
\newcommand{\tipxrefend}{}
\else
\newcommand{\tipimage}[2]{\typeout{Make sure you create #1.pdf}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.pdf}}{\includegraphics[width=0.8\textwidth]{#1.pdf}}}
\pdfcatalog{/PageMode /UseOutlines}
\newcommand{\tipxref}[1]{\pdfannotlink attr {/C [0.5 0.5 1.0] /Border [0 0 1]} goto name {#1}}
\newcommand{\tipxrefend}{\pdfendlink}
\fi
\newenvironment{tipabstract}{\begin{abstract}}{\end{abstract}}
\begin{document}\maketitle
\begin{center}\begin{tabularx}{\linewidth}{|r@{: }X|}\hline
\textbf{TIP \#168}&\textbf{Cubic Bezier Curves on the Canvas}\\\hline
Author&

Lars Hellström \tipmail{Lars.Hellstrom}{math.umu.se}
\\
Created&Sunday, \(\text{25}^{\text{th}}\) January 2004\\
Type&Project\\
Tcl Version&\(8.5\)\\
State&Final\\
Vote&Done\\
Version&\tipversion$Revision: 1.10 $\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This document proposes a new \textbf{-smooth} method for \textbf{line} and \textbf{polygon} canvas items that supports cubic Bezier curves and clarifies some of the existing terminology in that area.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Proposal}

A new method for the \textbf{-smooth} canvas item option will be defined. Under this method, the points defining the item will be interpreted as a sequence \textit{knot-point} \textit{control-point} \textit{control-point} \textit{knot-point} \textit{control-point} \textit{control-point} ... of a curve composed of cubic Bezier segments. More precisely, if the list of coordinates is

\begin{figure}[htbp]\begin{center}\leavevmode
\tipimage{168ab}{223pt}
\caption{List of coordinates}
\end{center}\end{figure}

then the \textit{N}th (counting from zero) segment of the curve consists of points whose coordinates \textit{(x,y)} satisfies

\begin{figure}[htbp]\begin{center}\leavevmode
\tipimage{168xy}{506pt}
\caption{Parametric equations for x and y}
\end{center}\end{figure}

for some value of \textit{t} between 0 and 1, inclusive. If there are \textit{3N+1} points then the above defines an \textit{N} segment curve. In the case that the number of points is \textit{3N} or \textit{3N-1} then they shall still define an \textit{N} segment curve, where in the first case the first knot of the first segment is reused as the last knot in the last segment, and in the second case the first knot and control point in the first segment are reused as the last control point and knot in the last segment respectively.

Straight line segments in the curve can be encoded as a segment where the control points are equal to the neighbouring knot points. While this is not the only way to encode a straight line, it is a case that is recognised and handled more efficiently by code that renders the canvas item.

The name of this new method should be ``\textbf{raw}''.

The name of the existing \textbf{-smooth} method (as returned by the itemcget widget command) should be changed from ``\textbf{bezier}'' to ``\textbf{true}'', and the name ``\textbf{bezier}'', while at least in Tcl 8.5 still supported, should be deprecated.

\section{Rationale}

Cubic Bezier curves, being for example the native curve format in Postscript and its descendants, is probably the most common format for smooth curves in computing today. It is even used internally in Tk; for each segment of a \textbf{-smooth 1} curve, rendering starts with the calculation of a cubic Bezier representation of that curve and continues to use only this representation when approximating the smooth curve with straight line segments. Hence it might be claimed that the cubic Bezier curve is the ``raw'' format of a smooth curve in Tk. No new calculations need to be implemented in the core to implement this TIP, it is merely a matter of combining existing functions in a suitable way and move data around. Therefore it seems a waste to not provide cubic Bezier curves, when they are anyway already half implemented.

The reason for the interpretation of a curve with \textit{3N} points given is that this will cause the curve to be closed. Conversely, omitting the final knot point is sometimes used as a way of encoding the fact that the curve should be closed. This rule will therefore facilitate the use of data where then omitted endpoint convention has been employed. The only reason for the \textit{3N-1} point rule is that it fits a simple scheme (when at the end of the list of coordinates, continue from the start) that supports the \textit{3N} and \textit{3N+1} cases.

The reason for deprecating the name ``\textbf{bezier}'' for the traditional smoothing method is that it is at best confusing, and according to many authorities simply wrong. The term ``Bezier curve'' is very often used as a synonym of ``cubic Bezier curve'', whence the majority of programmers new to this feature of the canvas widget would probably expect ``\textbf{-smooth bezier}'' to imply the effect of the smoothing option proposed in this document rather than the smoothing via quadratic splines that it currently is. The amount of disappointment that could result from the unpleasant discovery that what one thought was the former is really the latter should not be underestimated.

The reason for changing the official name of the traditional smoothing method to ``\textbf{true}'' are (i) that it is backwards compatible in the sense that this name works for specifying that smoothing method in all Tk versions and (ii) that it is somewhat mnemonic, because it happens to coincide with the format used for curves in \textit{True}Type fonts.

\section{Background}

The question of what may rightfully be called ``\textbf{bezier}'' is somewhat complicated and deserves expounding upon. It really begins with Bernstein; the \textit{Bernstein degree n form} of a polynomial f is

\begin{figure}[htbp]\begin{center}\leavevmode
\tipimage{168f}{267pt}
\caption{Bernstein degree n form polynomial}
\end{center}\end{figure}

One advantage this form has over the standard form is that the coefficients \textit{a\_0, ..., a\_n} are directly comparable to the function values \textit{f(0), f(1/n), f(2/n), ..., f(1)}; the two are generally not equal (with the exception for the endpoints of the \textit{[0,1]} interval), but the function values approximates the sequence of coefficients in various useful ways. (Bernstein used it to give an elegant proof of the Weierstrass Approximation Theorem.)

A \textit{Bezier curve} (or Bernstein-Bezier curve, as it is sometimes called) of degree \textit{n} is a parametric curve \textit{P} defined by a sequence of \textit{n+1} points \textit{P\_0, ..., P\_n} (known as the \textit{control points} of the curve) where each coordinate function is the Bernstein polynomial one gets by taking as \textit{a\_k} the corresponding coordinate of the point \textit{P\_k} and parametric time goes from \textit{0} to \textit{1}; formally

\begin{figure}[htbp]\begin{center}\leavevmode
\tipimage{168P}{265pt}
\caption{Bernstein polynomial for points}
\end{center}\end{figure}

for \textit{t} between \textit{0} and \textit{1} inclusive. Higher degree Bezier curves are not used much in computer graphics (probably because the effect on the curve of moving an single control point is often not intuitively clear) but they do exist and it is not illogical to expect that a
\begingroup\small\begin{verbatim}
  $canvas create line $points -smooth bezier
\end{verbatim}
\endgroup

should be the degree-[expr \{[llength \$points]/2 --- 1\}] Bezier curve defined by the given points.

Another term which often occurs when discussing computer graphic curves is ``spline''. A \textit{spline} is a curve that passes through a set of given points (the \textit{knots} of the curve) in a given order, satisfies some smoothness condition, and in some sense is best possible under these conditions. The most common optimality condition is that the curve should be composed from segments that can be parameterized by polynomials of given degree, but there are implicit conditions (minimizing some suitable measure of curve deformation) which leads to the same family of curves.

The \textbf{-smooth 1} curves of the Tk canvas are splines (of degree \textit{2}) in this sense, even though the points used for defining them are (with the exception for endpoints) not the knots of the spline. (Rather, the internal knots are the midpoints of the line segments joining two adjacent control point.) The \textbf{raw} curves proposed here are in general \textit{not} splines (because they admit discontinuous changes in tangent direction, thus violating the smoothness condition), but they often serve as an encoding for pre-computed degree 3 splines and this use has lead to a confusion in terminology in this area. It is not uncommon that piecewise cubic Bezier curves in general are referred to as ``cubic splines'', even though that is a more special concept. It may also be observed that the endpoints of the Bezier segments are usually referred to as \textit{knots} of the curve, whereas the term ``control points'' is often reserved for the non-knot control points. This rather harmless convention is for example used above. Incorrect use of the word ``spline'' should however be avoided.

\section{Alternatives}

It would be possible to provide the suggested functionality using a compiled extension instead, but that seems a waste since almost all of the functionality is present in the core anyway.

It would also be possible to use the semantics of the Tkspline package [\url{http://www.graphviz.org/cgi-bin/man?tkspline}] \textbf{-smooth} method providing cubic Bezier curves, but that package reverts to using the \textbf{-smooth true} method of smoothing if the number of points is not \textit{3N+1}, which doesn't seem useful and may cause bugs to be less visible. Using the Tkspline syntax (calling the \textbf{-smooth} method ``spline'') should probably be avoided even if the two methods were compatible, since the curves produced in general aren't splines.

\section{Implementation}

A sample implementation of this proposal (minus the part about changing the name of the existing \textbf{-smooth} method) exists [\url{http://sf.net/tracker/?func=detail&aid=886240&group_id=12997&atid=312997}].

\section{Copyright}

This document has been placed in the public domain.

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\end{document}
