On computing the intersection of B-splines (extended abstract)

ABSTRACT

We consider the problem of computing a piecewise linear approximation to the intersection of a pair of tensor product B-spline surfaces in 3-space. The problem is rather central in solid modeling. We present a fast and robust divide-and-conquer algorithm for the problem, that is a generalization of the bisection algorithm for computing the roots of non-linear equations. The algorithm is guaranteed to solve a “nearby” problem, and our analysis proves that its expected run-time is linear in the worst-case size of the output. To our knowledge, this is the first such analysis, resulting in the first provably efficient algorithm for the problem.

REFERENCES

• 1: 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]
• 2: Robert E. Barnhill , Gerald Farin , M. Jordan , B. R. Piper, Surface/surface intersection, Computer Aided Geometric Design, v.4 n.1-2, p.3-16, July 1987 [doi>10.1016/0167-8396(87)90020-3]
• 3: 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
• 4: Cohen, E., Lyche, T., Riesenfeld, R., 1980. Discrete B-splines and subdivision techniques in computer-aided geometric design and computer graphics. Computer Graphics and Image Processing, 14, No 2, pp87-110.
• 5: Dokken, T., 1985. Finding intersections of B-spline represented geometric entities using recursive subdivision techniques. Computer Aided Geometric Design, 2, pp189-195.
• 6: 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]
• 7: Sheldon Katz , Thomas W. Sederberg, Genus of the intersection curve of two rational surface patches, Computer Aided Geometric Design, v.5 n.3, p.253-258, Sept. 1988 [doi>10.1016/0167-8396(88)90006-4]
• 8: Lane, J.M., and Riesenfeld, R., 1981. Bounds on a polynomial. BIT 21, pp112- 117.
• 9: Sehumaker, L., 1981. Spline functions, basic theory. Wiley-Interseience, New York.
• 10: Wang, G., 1984. The subdivision method of finding the intersection between two Bezier curves or surfaces. Zhejiang University Journal, Special Issue on Computational Geometry.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms