Complete subdivision algorithms, I: intersection of Bezier curves

ABSTRACT

We give the first complete subdivision algorithm for the intersection of two Bezier curves F, G, possibly with tangential intersections. Our approach to robust subdivision algorithms is based on geometric separation bounds, and using a criterion for detecting non-crossing intersection of curves. Our algorithm is adaptive, being based only on exact bigfloat computations. In particular, we avoid manipulation of algebraic numbers and resultant computations. It is designed to be competitive with current algorithms on "nice" inputs. All standard algorithms assume F,G to be relatively prime—our algorithm needs a generalization of this.

REFERENCES

• 1: Dennis S. Arnon , Scott McCallum, A polynomical-time algorithm for the topological type of a real algebraic curve, Journal of Symbolic Computation, v.5 n.1-2, p.213-236, February/April 1988 [doi>10.1016/S0747-7171(88)80013-0]
• 2: Chandrajit L. Bajaj , Myung-Soo Kim, Algorithms for Planar Geometric Models, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.67-81, July 11-15, 1988
• 3: S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Springer, 2003.
• 4: Eric Berberich , Arno Eigenwillig , Michael Hemmer , Susan Hert , Kurt Mehlhorn , Elmar Schömer, A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons, Proceedings of the 10th Annual European Symposium on Algorithms, p.174-186, September 17-21, 2002
• 5: Hervé Brönnimann , Christoph Burnikel , Sylvain Pion, Interval arithmetic yields efficient dynamic filters for computational geometry, Discrete Applied Mathematics, v.109 n.1-2, p.25-47, April 15, 2001 [doi>10.1016/S0166-218X(00)00231-6]
• 6: Geometric modeling with splines: an introduction, A. K. Peters, Ltd., Natick, MA, 2001
• 7: Gershon Elber , Myung-Soo Kim, Geometric constraint solver using multivariate rational spline functions, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.1-10, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376958]
• 8: Gerald Farin, Curves and surfaces for computer aided geometric design (3rd ed.): a practical guide, Academic Press Professional, Inc., San Diego, CA, 1993
• 9: Rida T. Farouki, Numerical Stability in Geometric Algorithms and Representations, Proceedings of the 3rd IMA Conference on the Mathematics of Surfaces, p.83-113, September 19-21, 1988
• 10: Nicola Geismann , Michael Hemmer , Elmar Schömer, Computing a 3-dimensional cell in an arrangement of quadrics: exactly and actually!, Proceedings of the seventeenth annual symposium on Computational geometry, p.264-273, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378689]
• 11: Laureano González-Vega , M'Hammed El Kahoui, An improved upper complexity bound for the topology computation of a real algebraic plane curve, Journal of Complexity, v.12 n.4, p.527-544, Dec. 1996 [doi>10.1006/jcom.1996.0032]
• 12: Laureano Gonzalez-Vega , Ioana Necula, Efficient topology determination of implicitly defined algebraic plane curves, Computer Aided Geometric Design, v.19 n.9, p.719-743, December 2002 [doi>10.1016/S0167-8396(02)00167-X]
• 13: Hoon Hong, An efficient method for analyzing the topology of plane real algebraic curves, Mathematics and Computers in Simulation, v.42 n.4-6, p.571-582, Nov. 1996
• 14: M.-S. Kim and I.-K. Lee. Gaussian approximations of objects bounded by algebraic curves. In Proc. 1990 IEEE Int'l, Conf. on Robotics and Automation, pages 322--326, 1990. May 13--18, Cincinnati, U.S.A.
• 15: B. Mourrain and J.-P. Pavone. Subdivision methods for solving polynomial equations. Technical Report 5658, INRIA, 2005.
• 16: N.M. M. Patrikalakis , Nicholas M. Patrikalakis, Shape Interrogation for Computer Aided Design and Manufacturing, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 17: Simon Plantinga , Gert Vegter, Isotopic approximation of implicit curves and surfaces, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057465]
• 18: T. Sakkalis. The topological configuration of a real algebraic curve. Bulletin of the Australian Math. Soc., 43:37--50, 1991.
• 19: Thomas W. Sederberg , Ray J. Meyers, Loop detection in surface patch intersections, Computer Aided Geometric Design, v.5 n.2, p.161-171, July 1988 [doi>10.1016/0167-8396(88)90029-5]
• 20: Raimund Seidel , Nicola Wolpert, On the exact computation of the topology of real algebraic curves, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064111]
• 21: Ron Wein, High-Level Filtering for Arrangements of Conic Arcs, Proceedings of the 10th Annual European Symposium on Algorithms, p.884-895, September 17-21, 2002
• 22: N. Wolpert. An Exact and Efficient Approach for Computing a Cell in an Arrangement of Quadrics. PhD thesis, University of Saarland, Saarbruecken, Germany, Oct. 2002.
• 23: N. Wolpert. Jacobi curves: Computing the exact topology of arrangements of non-singular algebraic curves. In 11th European Symposium on Algorithms (ESA), pages 532--543, 2003. Budapest, 15-20 September.
• 24: Chee Keng Yap, Fundamental problems of algorithmic algebra, Oxford University Press, Inc., New York, NY, 1999

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Additional Classification:
  D. Software
  D.m MISCELLANEOUS

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations

General Terms:
Algorithms, Performance, Reliability

Keywords:
Bezier curves, computational geometry, curve intersection, exact geometric computation, geometric algorithms, methods for polynomials, robust geometric computation, robust numerical algorithms, subdivision method