An efficient surface intersection algorithm based on lower-dimensional formulation

ABSTRACT

We present an efficient algorithm to compute the intersection of algebraic and NURBS surfaces. Our approach is based on combining the marching methods with the algbraic formulation. In particular, we propose and matrix computations. We present algorithms to compute a start point on each component of the intersection curve (both open and closed components), detect the presence of singularities, and find all the curve branches near the singularity. We also suggest methods to compute the step size during tracing to prevent component jumping. The algorithm runs an order of magnitude faster than previously published robust algorithms. The complexity of the algorithm is output sensitive.

REFERENCES

• 1: S. S. Abhyankar , C. L. Bajaj, Automatic parameterization of rational curves and surfaces III: algebraic plane curves, Computer Aided Geometric Design, v.5 n.4, p.309-321, Nov. 1988 [doi>10.1016/0167-8396(88)90011-8]
• 2: Dennis S. Arnon, Topologically reliable display of algebraic curves, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.219-227, July 1983
• 3: C. L. Bajaj , C. M. Hoffman , R. E. Lynch , J. E. H. Hopcroft, Tracing surface intersections, Computer Aided Geometric Design, v.5 n.4, p.285-307, Nov. 1988 [doi>10.1016/0167-8396(88)90010-6]
• 4: R. E. Barnhill , S. N. Kersey, A marching method for parametric surface/surface intersection, Computer Aided Geometric Design, v.7 n.1-4, p.257-280, Jun. 1990 [doi>10.1016/0167-8396(90)90035-P]
• 5: K.- P. Cheng, Using plane vector fields to obtain all the intersection curves of two general surfaces, Theory and practice of geometric modeling, Springer-Verlag New York, Inc., New York, NY, 1989
• 6: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 7: DIXON, A. L. 1908. The eliminant of three quantics in two independent variables. Proc. London Math. Soc. 6, 49-69, 209-236.
• 8: DOKKEN, T. 1985. Finding intersections of b-spline represented geometries using recursive subdivision techniques. Comput. Aided Geom. Des. 2, 189-195.
• 9: Tor Dokken , Vibeke Skytt , Anne-Marie Ytrehus, Recursive subdivision and iteration in intersections and related problems, Mathematical methods in computer aided geometric design, Academic Press Professional, Inc., San Diego, CA, 1989
• 10: R T Farouki, The characterization of parametric surface sections, Computer Vision, Graphics, and Image Processing, v.33 n.2, p.209-236, Feb. 1986 [doi>10.1016/0734-189X(86)90115-5]
• 11: 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]
• 12: FIELD, D. A., AND FIELD, R. 1992. A new family of curves for industrial applications. Tech. Rep. GMR-7571, General Motors Research Laboratories.
• 13: GEISOW, A. 1983. Surface interrogations. School of Computing Studies and Accountancy, University of East Anglia, Ph.D. thesis.
• 14: GOHBERG, I., LANCASTER, P., AND RODMAN, L. 1982. Matrix Polynomials. Academic Press, New York.
• 15: GOLUB, G. H., AND VAN LOAN, C. F. 1989. Matrix Computations. John Hopkins Press, Baltimore.
• 16: Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 17: C. M. Hoffmann, A dimensionality paradigm for surface interrogations, Computer Aided Geometric Design, v.7 n.6, p.517-532, Nov. 1990 [doi>10.1016/0167-8396(90)90013-H]
• 18: HOHMEYER, M. E. 1991. A surface intersection algorithm based on loop detection. Int. J. Comput. Geom. Appl. 1, 4, 473-490. Special issue on Solid Modeling.
• 19: Pradeep Sinha , Eric Klassen , K. K. Wang, Exploiting topological and geometric properties for selective subdivision, Proceedings of the first annual symposium on Computational geometry, p.39-45, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323239]
• 20: KRIEZIS, G. A., PATRIKALAKIS, N. M., AND WOLTER, F.E. 1990b. Topological and differential equation methods for surface intersections. Comput. Aided Des. 24, 1, 41-55.
• 21: G. A. Kriezis , P. V. Prakash , N. M. Patrikalakis, A method for intersecting algebraic surfaces with rational polynomial patches in presented, Computer-Aided Design, v.22 n.10, p.645-654, Dec. 1990 [doi>10.1016/0010-4485(90)90011-Z]
• 22: KRISHNAN, S., AND MANOCHA, D. 1996. Efficient representations and techniques for computing b-rep's of csg models with nurbs primitives. In Proceedings of CSG'96, Information Geometers, Ltd, 101-122.
• 23: LANE, g. M., AND RIESENFELD, R. F. 1980. A theoretical development for the computer generation and display of piecewise polynomial surfaces. IEEE Trans. Pattern Anal. Mach. Intell. 2, 1, 150-159.
• 24: Dieter Lasser, Intersection of parametric surfaces in the Bernstein—Be´zier representation, Computer-Aided Design, v.18 n.4, p.186-192, May 1986 [doi>10.1016/0010-4485(86)90130-2]
• 25: Dinesh Manocha, Algebraic and numeric techniques in modeling and robotics, University of California at Berkeley, Berkeley, CA, 1992
• 26: Dinesh Manocha, Computing selected solutions of polynomial equations, Proceedings of the international symposium on Symbolic and algebraic computation, p.1-8, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190349]
• 27: Dinesh Manocha, Solving Systems of Polynomial Equations, IEEE Computer Graphics and Applications, v.14 n.2, p.46-55, March 1994 [doi>10.1109/38.267470]
• 28: MANOCHA, D. AND CANNY, g.F. 1991. A new approach for surface intersection. Int. J. Comput. Geom. Appl. 1, 4, 491-516. Special issue on Solid Modeling.
• 29: Dinesh Manocha , Shankar Krishnan, Algebraic pruning: a fast technique for curve and surface intersection, Computer Aided Geometric Design, v.14 n.9, p.823-845, Dec. 1997 [doi>10.1016/S0167-8396(97)00008-3]
• 30: Nicholas M. Patrikalakis, Surface-to-Surface Intersections, IEEE Computer Graphics and Applications, v.13 n.1, p.89-95, January 1993 [doi>10.1109/38.180122]
• 31: L. Piegl, Geometric method of intersecting natural quadrics represented in trimmed surface form, Computer-Aided Design, v.21 n.4, p.201-212, May 1989 [doi>10.1016/0010-4485(89)90045-6]
• 32: PRATT, M.J. 1986. Surface/surface intersection problems. In The Mathematics of Surfaces II, J. A. Gregory, ed., Claredon Press, Oxford, 117-142.
• 33: Aristides A. G. Requicha , Jarek R. Rossignac, Solid Modeling and Beyond, IEEE Computer Graphics and Applications, v.12 n.5, p.31-44, September 1992 [doi>10.1109/38.156011]
• 34: Jaroslaw Rossignac , Aristides A. G. Requicha, Piecewise-circular curves for geometric modeling, IBM Journal of Research and Development, v.31 n.3, p.296-313, May 1, 1987
• 35: SARRAGA, R. F. 1983. Algebraic methods for intersection. Comput. Vis. Graph. Image Process. 22, 222-238.
• 36: Thomas Warren Sederberg, Implicit and parametric curves and surfaces for computer aided geometric design, 1983
• 37: 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]
• 38: Thomas W. Sederberg , Tomoyuki Nishita, Geometric Hermite approximation of surface patch intersection curves, Computer Aided Geometric Design, v.8 n.2, p.97-114, May 1991 [doi>10.1016/0167-8396(91)90036-B]
• 39: Raimund Seidel, Linear programming and convex hulls made easy, Proceedings of the sixth annual symposium on Computational geometry, p.211-215, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98570]
• 40: John M. Snyder, Interval analysis for computer graphics, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.121-130, July 1992
• 41: ZUNDEL, A. AND SEDERBERG, T. 1993. Using pyramidal surfaces to detect and isolate surface/ surface intersections. In SIAM Conference on Geometric Design (Tempe, AZ).

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:
  J. Computer Applications

General Terms:
Algorithms

Keywords:
algebraic curve, curve tracing, curve-surface intersection, eigenvalues, loop detection, matrices, singular points, surface-surface intersection