1 Implicit curves

Remember conic sections from algebra class? Circles, ellipses, parabolas, and hyperbolas: the four types of curves you can get from an expression of the form $$Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0$$ We could generalize that (and depending on your algebra class you might have) into the form $$P(x,y) = 0$$ where $P$ is a polynomial function. Curves expressed as $f(x,y) = 0$ for some function $f$ are called implicit curves, and if $f$ is a polynomial they are called implicit polynomial curves.

A slight generalization of the formulation $$P(x,y) \ge 0$$ allows us to meaningfully define the implicit curve as the boundary between two regions: areas where $P$ is positive and areas where it is negative. As we’ll see, that generalization will simplify some of our algorithm design.

We can write algorithms that rasterize implicit polynomial curves directly in a very efficient way using two parts:

1. We want to evaluate the function $P$ at integer $x$ and $y$ coordinates (i.e., pixel centers) efficiently. In practice, efficiently means with just additions, no multiplications. We’ll achieve that using a little-taught discrete variant of a derivative called a finite difference.

2. We want to identify the border between the two regions with as few evaluations of $P$ as possible. We’ll achieve that by walking borders in a specific way.

The solutions we’ll find for these will turn out to encompass the Bresenham line-drawing algorithm as the special case when $P$ is linear.

2 Finite Differences

We have a larger writeup on finite differences; we present here a summary.

The first finite difference in $x$ of $f$ is defined to be $$f_x(x,y) \triangleq f(x+1,y) - f(x,y)$$ The finite difference in $y$, $f_y$ is defined similarly.

The finite difference of a polynomial is always 1 lower in degree than the original polynomial, so if $f$ is cubic in $x$ then $f_x$ is quadratic. We can continue this until we get a constant: a cubic $f$ means a linear $f_{xx}$ and constant $f_{xxx}$.

Mixed finite differences do not depend on differencing order. $$\begin{split} f_{xy}(x,y) &= \big(f(x+1,y+1) - f(x,y+1)\big) - \big(f(x+1,y) - f(x,y)\big) \\ &= f(x+1,y+1) - f(x,y+1) - f(x+1,y) + f(x,y) \\ &= f(x+1,y+1) - f(x+1,y) - f(x,y+1) + f(x,y) \\ &= \big(f(x+1,y+1) - f(x+1,y)\big) - \big(f(x,y+1) - f(x,y)\big) = f_{yx}(x,y) \end{split}$$

Rearranging the defining function shows us that we can use finite differences to evaluate a function at adjacent points using just a few additions: $$\begin{split} f(x+1,y) &= f(x,y) + f_x(x,y)\\ f(x-1.y) &= f(x,y) - f_x(x-1,y) \end{split}$$

Thus, we can evaluate a polynomial function at integer coordinates evaluating the full polynomial a few times up front and then doing just a few additions per additional value desired.

3 Drawing Curves

Suppose I am given an arbitrary implicit polynomial curve (of known degree) and asked to draw it.

First, we need some point on the edge of the polynomial. This might be explicitly derivable (e.g., we can find a point on the edge of a circle by adding its radius in $x$ to its center) or might be provided (e.g., we might be asked to draw a curve conencting two points); if neither of those is the case we’ll have to search for a starting point.

Given a point on the border, use finite differences to evaluate a 2×2 square of function values. Because it’s a border, some will be positive and some won’t. We then use finite differences to walk the 2×2 box along the border: if we step and get two new values with the same sign, we step in a perpendicular direction next; if we step and get two new values with different signs, we step in that same direction again next.

This process is not truly general: implicit polynomials curves could have several discontinuous regions (e.g. hyperbola) and if the curve has interesting details smaller than a pixel the curve following could get confused. However, for any given class of polynomial curves those cases can be analyzed in advance and work-around defined.