Distance approximations for rasterizing implicit curves

ABSTRACT

In this article we present new algorithms for rasterizing implicit curves, i.e., curves represented as level sets of functions of two variables. Considering the pixels as square regions of the plane, a “correct” algorithm should paint those pixels whose centers lie at less than half the desired line width from the curve. A straightforward implementation, scanning the display array evaluating the Euclidean distance from the center of each pixel to the curve, is impractical, and a standard quad-tree-like recursive subdivision scheme is used instead. Then we attack the problem of testing whether or not the Euclidean distance from a point to an implicit curve is less than a given threshold. For the most general case, when the implicit function is only required to have continuous first-order derivatives, we show how to reformulate the test as an unconstrained global root-finding problem in a circular domain. For implicit functions with continuous derivatives up to order k we introduce an approximate distance of order k. The approximate distance of order k from a point to an implicit curve is asymptotically equivalent to the Euclidean distance and provides a sufficient test for a polynomial of degree k not to have roots inside a circle. This is the main contribution of the article. By replacing the Euclidean distance test with one of these approximate distance tests, we obtain a practical rendering algorithm, proven to be correct for algebraic curves. To speed up the computation we also introduce heuristics, which used in conjunction with low-order approximate distances almost always produce equivalent results. The behavior of the algorithms is analyzed, both near regular and singular points, and several possible extensions and applications are discussed.

REFERENCES

• 1: ABHYANKAR, S. S. AND BAJAJ, C. 1988. Automatic parameterization of rational curves and surfaces IV: Algebraic space curves. Tech. Rep. CSD-TR-703, Purdue Univ., Computer Sciences Dept., West Lafayette, Ind.
• 2: S. S. Abhyankar , C. Bajaj, Automatic parameterization of rational curves and surfaces 1: conics and conicoids, Computer-Aided Design, v.19 n.1, p.11-14, Jan./Feb. 1987 [doi>10.1016/0010-4485(87)90147-3]
• 3: S. S. Abhyanker , C. Bajaj, Automatic parametrization of rational curves and surfaces II: cubics and cubicoids, Computer-Aided Design, v.19 n.9, p.499-502, Nov. 1987 [doi>10.1016/0010-4485(87)90235-1]
• 4: ABHYANKAR, S. S. AND BAJAJ, C. 1987c. Automatic parameterixation of rational curves and surfaces III: Algebraic plane curves. Tech. Rep. CSD-TR-619, Purdue Univ., Computer Sciences Dept., West Lafayette, Ind.
• 5: ALLGOWER, E. AND GEORG, K. 1980. Simpliciai and continuation methods for approximating fixed points and solutions to systems of equations. SIAM Rev. 22, 1 (Jan.), 28-85.
• 6: ALLGOWEH, E. L. AND SCttMtDT, P.H. 1985. An algorithm for piecewise-linear approximation of an implicitly defined manifold. SIAM J. Num. Anal. 22, 2 (Apr.), 322-346.
• 7: Dennis S. Arnon, Topologically reliable display of algebraic curves, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.219-227, July 1983
• 8: BAJAJ, C. L., HOFFMANN, C. M., HOPCHOFr, J. E., AND LYNCH, R. E. 1987. Tracing surface intersections. Tech. Rep. CSD-TR-728, Dept. of Computer Science, Purdue Univ., West Lafayette, Ind.
• 9: R. Baker Kearfott, Some tests of generalized bisection, ACM Transactions on Mathematical Software (TOMS), v.13 n.3, p.197-220, Sept. 1987 [doi>10.1145/29380.29862]
• 10: J. Bloomenthal, Polygonization of implicit surfaces, Computer Aided Geometric Design, v.5 n.4, p.341-355, Nov. 1988 [doi>10.1016/0167-8396(88)90013-1]
• 11: BOCltNAK, J., COSTE, M., AND RoY, M.-F. 1987. G~m~trie' alg~brique r~elle. In Ergebnisse der Mathematik un ihrer Grenzgebiete. Vol. 12. Springer-Verlag, Berlin.
• 12: BORODIN, A. AND MUNGO, I. 1975. The Computational Complexity of Algebraic and Numeric Problems. American Elsevier, New York.
• 13: John F. Canny, The complexity of robot motion planning, MIT Press, Cambridge, MA, 1988
• 14: DE MOUNTAUDOUIN, Y. 1991. Resolution of p(x, y) = O. Comput. Aided Des. 23, 9 (Nov.), 653 -654.
• 15: J. E. Dennis, Jr. , Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Classics in Applied Mathematics, 16), Soc for Industrial & Applied Math, 1996
• 16: David P. Dobkin , Allan R. Wilks , Silvio V. F. Levy , William P. Thurston, Contour tracing by piecewise linear approximations, ACM Transactions on Graphics (TOG), v.9 n.4, p.389-423, Oct. 1990 [doi>10.1145/88560.88575]
• 17: Michael L. Dowling, A fast parallel Horner algorithm, SIAM Journal on Computing, v.19 n.1, p.133-142, Feb. 1990 [doi>10.1137/0219008]
• 18: A. Eiger , K. Sikorski , F. Stenger, A bisection method for systems of nonlinear equations, ACM Transactions on Mathematical Software (TOMS), v.10 n.4, p.367-377, Dec. 1984 [doi>10.1145/2701.2705]
• 19: GEIsow, A. 1983. Surface interrogations. Ph.D. thesis, Univ. of East Anglia, School of Computing Studies, U.K
• 20: John D. Hobby, Rasterization of nonparametric curves, ACM Transactions on Graphics (TOG), v.9 n.3, p.262-277, July 1990 [doi>10.1145/78964.78966]
• 21: JORDAN, 11. W., ,JR., LENNON, W. J., ANI) Hal.M, B. D. 1973. An improved algorithm for the generation of nanparametrie curves. IEEE Trans. Comput. C-22, 12 (Dec.), 1052 1060.
• 22: D. J. Kriegman , Jean Ponce, On Recognizing and Positioning Curved 3-D Objects from Image Contours, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.12, p.1127-1137, December 1990 [doi>10.1109/34.62602]
• 23: Dinesh Manocha, Algebraic and numeric techniques in modeling and robotics, University of California at Berkeley, Berkeley, CA, 1992
• 24: Dinesh Manocha, MultiPolynomial Resultant Algorithms, University of California at Berkeley, Berkeley, CA, 1991
• 25: MILNE, P. 1990. On the solution of a set of.polynomial equations. Tech. Rep., Bath Univ., Bath, U.K.
• 26: MoRE, J. J., GARBOW, B. S., ANb HILI~STROM, K.E. 1980. User guide for minpack-l. Tech. Rep. ANL-80-74, Argone National Laboratories.
• 27: Alexander Morgan , Vadim Shapiro, Box-bisection for solving second-degree systems and the problem of clustering, ACM Transactions on Mathematical Software (TOMS), v.13 n.2, p.152-167, June 1987 [doi>10.1145/328512.328521]
• 28: OVERMARS, m. H. 1988. Geometric data structures for computer graphics: an overview. In Theoretical Foundations of Computer Graphics and CAD. NAT() ASI Series, vol. F40, Springer-Verlag, 21- 49.
• 29: Paul Christian Pedersen , Bud Mishra, Counting real zeros, 1991
• 30: Paul Pedersen, Multivariate Sturm Theory, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.318-332, October 07-11, 1991
• 31: Jean Ponce , Anthony Hoogs , David J. Kriegman, On using CAD models to compute the pose of curved 3D objects, CVGIP: Image Understanding, v.55 n.2, p.184-197, March 1992 [doi>10.1016/1049-9660(92)90016-V]
• 32: Vaughan Pratt, Direct least-squares fitting of algebraic surfaces, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.145-152, July 1987
• 33: SAMET, H. 1988. An overview ofquadtrees, octrees, and related hierachical data structures. In Theoretical Foundations of Computer Graphics and CAD. NATO ASI Series, vol. F40. Springer-Verlag, Berlin, 51-68.
• 34: SAMPSON, P.D. 1982. Fitting conic sections to very scattered data: An iterative refinement of the bookstein algorithm. Comput. Vis. Graph. Image Pro{'. 18, 97 108.
• 35: SEDERBERG, T. W., ANDERSON, D. C., AND GaLl)MAN, R. N. 1984. Implicit representation of parametric curves and surfaces. Comput. Vis. Graph. Image Prec. 28, 1, 72 84.
• 36: SEDERBERG, T. W., ANI)EaSON, D. C., A.~D GOLDMAN, R.N. 1985. Implicitization, inversion, and intersection of planar rational cubic curves. Comput. Vis. Graph. Image Pro{.. 31, 1 (July), 89- 102.
• 37: Jean Serra, Image Analysis and Mathematical Morphology, Academic Press, Inc., Orlando, FL, 1983
• 38: TAUBIN, G. 1988. Nonplanar curve and surface estimation in 3-space. In Proceedings of the IEEE Conference on Robotics and Automation. IEEE, New York.
• 39: Gabriel Taubin, Estimation of Planar Curves, Surfaces, and Nonplanar Space Curves Defined by Implicit Equations with Applications to Edge and Range Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.11, p.1115-1138, November 1991 [doi>10.1109/34.103273]
• 40: Gabriel Taubin, An accurate algorithm for rasterizing algebraic curves, Proceedings on the second ACM symposium on Solid modeling and applications, p.221-230, May 19-21, 1993, Montreal, Quebec, Canada [doi>10.1145/164360.164427]
• 41: G. Taubin , F. Cukierman , S. Sullivan , J. Ponce , D. J. Kriegman, Parameterized Families of Polynomials for Bounded Algebraic Curve and Surface Fitting, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.3, p.287-303, March 1994 [doi>10.1109/34.276128]
• 42: TAUBIN, G., CUKIERMAN, F., SULLIVAN, S., PONCE, J., AND KRIEGMAN, D.J. 1992. Parameterizing and fitting bounded algebraic curves and surfaces. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. IEEE, New York, 103-108.
• 43: THORPE, J.A. 1979. Elementary Topics in Differential Geometry. Springer-Verlag, New York.
• 44: Jerry Van Aken , Mark Novak, Curve-drawing algorithms for Raster displays, ACM Transactions on Graphics (TOG), v.4 n.2, p.147-169, April 1985 [doi>10.1145/282918.282943]
• 45: WALKER, R 1950. Algebraic Curves. Princeton University Press, Princeton, N.J.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Theory

Keywords:
algebraic curve, approximate distance, implicit curve, rendering