Algorithms for intersecting parametric and algebraic curves I: simple intersections

ABSTRACT

The problem of computing the intersection of parametric and algebraic curves arises in many applications of computer graphics and geometric and solid modeling. Previous algorithms are based on techniques from elimination theory or subdivision and iteration. The former is, however, restricted to low-degree curves. This is mainly due to issues of efficiency and numerical stability. In this article we use elimination theory and express the resultant of the equations of intersection as matrix determinant. The matrix itself rather than its symbolic determinant, a polynomial, is used as the representation. The problem of intersection is reduced to that of computing the eigenvalues and eigenvectors of a numeric matrix. The main advantage of this approach lies in its efficency and robustness. Moreover, the numerical accuracy of these operations is well understood. For almost all cases we are able to compute accurate answers in 64-bit IEEE floating-point arithmetic.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 2: Richard H. Bartels , John C. Beatty , Brian A. Barsky, An introduction to splines for use in computer graphics & geometric modeling, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 3: Zhaojun Bai , James W. Demmel, Design of a Parallel Nonsymmetric Eigenroutine Toolbox, Part I, University of California at Berkeley, Berkeley, CA, 1992
• 4: Z. Bai , James Demmel , A. McKenney, On computing condition numbers for the nonsymmetric eigenproblem, ACM Transactions on Mathematical Software (TOMS), v.19 n.2, p.202-223, June 1993 [doi>10.1145/152613.152617]
• 5: George E. Collins , Werner Krandick, An efficient algorithm for infallible polynomial complex root isolation, Papers from the international symposium on Symbolic and algebraic computation, p.189-194, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143308]
• 6: DEMMEL, J. 1989. LAPACK: A portable linear algebra library for supercomputers. In Proceedings of the 1989 IEEE Control Systems Society Workshop on Computer-Aided Control System Design. IEEE, New York
• 7: Gershon Elber , Elaine Cohen, Hidden curve removal for free form surfaces, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.95-104, Aug. 1990
• 8: R. T. Farouki , V. T. Rajan, On the numerical condition of polynomials in Berstein form, Computer Aided Geometric Design, v.4 n.3, p.191-216, Nov., 1987 [doi>10.1016/0167-8396(87)90012-4]
• 9: GARROW, B. S., BoYLE, J. M., Dent;ann.,\, J., ^ND MOLE~, C. B. 1977. Matrix Eigen.~ystem Routines EINPACK (;uide Extension. Lecture Notes in Computer Science, vol. 51. Springer- Verlag, Berlin.
• 10: GOLUB, G. H. AND VAN LOAN, C F. 1989. Matrix Computations. ,John Hopkins Press, Baltimore, Md.
• 11: GOBBERG, I., LANCASTER P. AND R()I)MAN, L. 1982 Matrix Pol.vnomials. Academic Press, New York
• 12: GOLDMAN, R., SEI)ERBERC,, T. W.. ANI) ANDERSON, D. C. 1984. Vector elimination: A technique for the imphcitization, inversion and intersection of planar parametric rational polynomial curves. ('omput. Aided Gee. Des. I, 4, 327 356.
• 13: John D. Hobby, Numerically stable implicitization of cubic curves, ACM Transactions on Graphics (TOG), v.10 n.3, p.255-296, July 1991 [doi>10.1145/108541.108546]
• 14: Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 15: KOPPAKAR, P. A. ANI) Mt~laq~, S. P. 1983. A new class of algorithms fi)r the processing of parametric curves. (!omput. Aided Des. 1,5, 1, 41 45.
• 16: LANE, ,1 M. ANII RIESFNFEIA), R F. 1980. A theoretical development fi)r the computer generation and display of piecewise polynmnial surfaces. IEEE Trans. Patt. Anal. Mach. Intell. 2, I, 150 159.
• 17: MACUALAY,'. F. ,'q. 1902. ()n some formula in elimination. Proceedings of London Mathematical Nociety, pages 3 27, May.
• 18: D. Manocha, Regular curves and proper parametrizations, Proceedings of the international symposium on Symbolic and algebraic computation, p.271-276, August 20-24, 1990, Tokyo, Japan [doi>10.1145/96877.96947]
• 19: Dinesh Manocha, Algebraic and numeric techniques in modeling and robotics, University of California at Berkeley, Berkeley, CA, 1992
• 20: Dinesh Manocha , John F. Canny, Detecting cusps and inflection points in curves, Computer Aided Geometric Design, v.9 n.1, p.1-24, May 1992 [doi>10.1016/0167-8396(92)90050-Y]
• 21: Dinesh Manocha , James W. Demmel, Algorithms for Intersecting Parametric and Algebraic Curves, University of California at Berkeley, Berkeley, CA, 1992
• 22: R. P. Markot , R. L. Magedson, Solutions of tangential surface and curve intersections, Computer-Aided Design, v.21 n.7, p.421-429, Sep. 1989 [doi>10.1016/0010-4485(89)90126-7]
• 23: SALMON, G. 1885. Lessons Introductory to the Modern Higher Algebra. G. E. Stechert and Co., New York.
• 24: T. W. Sederberg, Algorithm for algebraic curve intersection, Computer-Aided Design, v.21 n.9, p.547-554, Nov. 1989 [doi>10.1016/0010-4485(89)90015-8]
• 25: T W Sederberg, Improperly parametrized rational curves, Computer Aided Geometric Design, v.3 n.1, p.67-75, May 1986 [doi>10.1016/0167-8396(86)90025-7]
• 26: Thomas Warren Sederberg, Implicit and parametric curves and surfaces for computer aided geometric design, 1983
• 27: Thomas W Sederberg , Scott R Parry, Comparison of three curve intersection algorithms, Computer-Aided Design, v.18 n.1, p.58-64, Jan/Feb. 1986 [doi>10.1016/S0010-4485(86)80013-6]
• 28: T. W. Sederberg , S. C. White , A. K. Zundel, Fat arcs: a bounding region with cubic convergence, Computer Aided Geometric Design, v.6 n.3, p.205-218, Aug. 1989 [doi>10.1016/0167-8396(89)90024-1]
• 29: STURMFELS, B. 1991. Sparse elimination theory. In D. Eisenbud and L. Robbiano, editors, Computational Algebraic Geometry and Commutative Algebra. Cambridge University Press.
• 30: WALKER, R. J. 1950. Algebraic Curves. Princeton University Press, New Jersey.
• 31: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• 32: WILKINSON, J. H. 1959. The evaluation of the zeros of ill-conditioned polynomials. Parts i and ii. Num. Math. 1, 150-166 and 167-180.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Performance

Keywords:
algebraic, curves, eigenvalues, intersection, parametric, resultants, robustness