Rendering Curves and Surfaces with Hybrid Subdivision and Forward Differencing

Ari Rappoport

We present a hybrid rendering algorithm for rendering parametric curves and surfaces. The algorithm uses a series of Direct Rendering Criteria (DRC) for determining whether the curve/surface can be directly rendered by forward differencing with a constant step size. The DRCs test the geometric flatness of the curve/surface, its parametric uniformity, and the ability to use only integer arithmetic in the forward differencing algorithm. If any of the DRCs is not fulfilled, the curve/surface is subdivided. The location of the subdivision in parameter space is chosen to increase the chances that the new segments will satisfy the DRCs. For the integer arithmetic DRC we introduce a general method for determining an alignment of the forward differences. We show that for cubic (quartic) curves this alignment enables up to 2^13 (2^11) forward steps for curves lying in a 128K X 128K space. The method is applicable to curves of any order.

ACM Transactions on Graphics, 10(4):323-341, October 1991.