Non-parametric digitization algorithms.

We examine a class of algorithms for digitizing spline curves by deriving an implicit form F(x,y) = 0, where F can be evaluated cheaply in integer arithmetic using finite differences. These algorithms run very fast and produce what can be regarded as the optimal digital output, but previously known algorithms have had serious limitations. We extend previous work on conic sections to the cubic and higher order curves used in many graphics applications, and we solve an important undersampling problem that has plagued previous work. We also give efficient, numerically stable techniques for converting from commonly used parametric forms to suitable implicit forms, and we show how linear transformations can be used to improve the speed and accuracy of digitization algorithms.