Exact integer hybrid subdivision and forward differencing of cubics

ABSTRACT

Forward differencing is widely used to generate rapidly large numbers of points at equally space parameter values along a curve. A failing of forward differencing is the tendency to generate many extraneous points for curves with highly nonuniform parameterizations. A key result is presented and proven, namely, that a few levels of subdivision, prior to initialization for forward differencing, can improve substantially the quality of the step size estimate, resulting in very few extra points. The initial subdivisions can be done without loss of the exact integer precision available in forward differencing. For small numbers of points—a common occurrence in fonts—exact subdivision is even faster than exact forward differencing. When exact subdivision is used in conjunction with a previously presented exact forward-differencing algorithm, arbitrary cubic curves may be rendered with 32-bit arithmetic and guaranteed single-pixel accuracy, in a grid with an address space as large as 0…7281, with no two generated points greater than one pixel apart. This is more steps than previously possible. Previous discussions of rendering using subdivision have concentrated not on distance but on straightness estimates, whereby subdivision can be stopped once a subcurve can be drawn safely using its polygonal approximation. In this article, bounds are also derived on the size of the control polygon after multiple levels of subdivision: these are used to determine bounds on the number of steps required for differencing. It is shown that any curve whose rasterization fits in a space of &ohgr; pixels requires no more than 9&ohgr; steps.

REFERENCES

• 1: Narayanan Anantakrishnan , Les A. Piegl, Integer subdivision algorithm for rendering NURBS curves, The Visual Computer: International Journal of Computer Graphics, v.8 n.3, p.149-161, March 1992 [doi>10.1007/BF01902135]
• 2: Edwin Earl Catmull, A subdivision algorithm for computer display of curved surfaces., 1974
• 3: CHAR, B. W., GEDDE$, K. O., GONNETr, G. H., AND WATT, S. M. 1985. Maple User's Guide. WATCOM Publications, Waterloo, Ontario, Canada.
• 4: I~: CAS'r~:I,JA/T, P. 1959. Courbes et surfaces h p61es. Tech. Rep., Citroi~n, Paris.
• 5: Gerald Farin, Curves and surfaces for computer aided geometric design: a practical guide, Academic Press Professional, Inc., San Diego, CA, 1988
• 6: D. R. Forsey , R. V. Klassen, An adaptive subdivision algorithm for crack prevention in the display of parametric surfaces, Proceedings on Graphics interface '90, p.1-8, June 1990, Halifax, Nova Scotia
• 7: Daniel Filip , Robert Magedson , Robert Markot, Surface algorithms using bounds on derivatives, Computer Aided Geometric Design, v.3 n.4, p.295-311, 1987 [doi>10.1016/0167-8396(86)90005-1]
• 8: GONI'Z^R()WSKI, J. 1989. Fast generation of unfilled and filled outline characters. In Proceedilzgs ofR1DT'89, J. Andr6 and R. Hersch, Eds. Cambridge University Press, Cambridge, Mass., 97 110.
• 9: R. Victor Klassen, Drawing antialiased cubic spline curves, ACM Transactions on Graphics (TOG), v.10 n.1, p.92-108, Jan. 1991 [doi>10.1145/99902.99906]
• 10: R. Victor Klassen, Integer forward differencing of cubic polynomials: analysis and algorithms, ACM Transactions on Graphics (TOG), v.10 n.2, p.152-181, April 1991 [doi>10.1145/108360.108364]
• 11: KL,.xss~:x. R. V. 1993. A note on integer subdivision of NURBS. Vis. Cornput. 9, 5 /Mar.), 289 291.
• 12: Sheue-Ling Lien , Michael Shantz , Vaughan Pratt, Adaptive forward differencing for rendering curves and surfaces, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.111-118, July 1987
• 13: Ari Rappoport, Rendering curves and surfaces with hybrid subdivision and forward differencing, ACM Transactions on Graphics (TOG), v.10 n.4, p.323-341, Oct. 1991 [doi>10.1145/116913.116914]
• 14: Alyn P. Rockwood, Generalized scanning technique for display of parametrically defined surfaces, IEEE Computer Graphics and Applications, v.7 n.9, p.15-26, Aug. 1987
• 15: W^xt;. G. 1984. The subdivision method for finding the intersection between two Bdzier curv(~s or surfaces. Zb,:fiong Univ. d. Special issue on Computational Geometry. In Chinese.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Splines

General Terms:
Algorithms, Reliability

Keywords:
Be´zier polynomials, parameterization, spline curves