CGCAP

Applied Computational Geometry

The most widespread approach to rasterization is scan conversion but even for simple concave polygons known scan conversion algorithms require a computationally expensive presorting and marking phase before they can compute the actual intervals of points contained in the region. The latter phase -- specially for curved boundaries -- requires careful attention to both geometric and numeric detail in order to provide robust algorithms. Conventional filling and stroking of curved regions is based on algorithms for scan conversion of polygons where the end points of spans are incrementally updated and pixels in between are filled. At some stage the intersection formula derived in the continuous plane and usually computed using real arithmetic has to be mapped to the discrete plane. This mapping necessitates an implicit or explicit epsilon-test that may cause incorret results.

On the other hand, the Point Containment paradigm is a natural way to perform raster graphics operations such as filling and stroking. In a presentation at the Panel Session on Fundamental Algorithms at the 1985 ACM SIGGRAPH Conference, Forrest expressed the need for an efficient and robust algorithm to decide if a given point is part of a mathematically defined shape. Such an algorithm was later developed by Corthout et al. and implemented in dedicated silicon, the Pharos chip fabricated by Philips, on support of the PostScript page description language.

Following Corthout, Pol and Jonkers strategy we aim to provide robust and efficient geometric algorithms where the problems of discretisation are acknowledged and tackled by casting the problem to be solved as a discrete integer problem from the outset rather than attempting to accommodate all the problems of numerical accuracy which follow from floating point discretisation, geometric approximation, or a less rigorous approach to discretisation later in the rendering process.