Exploiting topological and geometric properties for selective subdivision

ABSTRACT

This paper presents a theorem relating the geometry of two smooth surfaces with the topology of their intersection. Algorithms for computing intersections of surfaces are very basic to those solid-modeling systems that allow Boolean operations such as Union, Intersection, and Subtraction on solids. Recently, such an algorithm based on recursive subdivision of the surfaces has attracted a lot of attention because of its simplicity and wide applicability. However, this algorithm for intersection of surfaces fails to find all intersections for certain relative orientations of surfaces. Finer subdivision of the surfaces may result in the correct intersections but also results in many unnecessary computations. The mathematical result established in this paper is significant in that it provides a check to determine when finer subdivision will yield no new topological information for an intersection. It is shown how the check may be incorporated into the existing subdivision algorithm to compute intersections reliably and efficiently.

REFERENCES

• 1: [1] Carl De Boor, On Calculating with B-splines, Journal of Approximation Theory, 6. 50-62 (1972).
• 2: [2] Elaine Cohen, Tom Lyche, Richard Riesenfeld, Discrete B-splines and Subdivision Techniques in Computer-Aided Geometric Design and Computer Graphics, Computer Graphics and Image Processing, 14, 87-111 (1980).
• 3: [3] Jeffrey M. Lane and Richard R. Riesenfeld, A Theoretical Development for the computer Generation and Dispay of Picewise Polynomial Surfaces, Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-2, no. 1, January 1980.
• 4: [4] S. P. Madur, P. A. Koparkar, Interval Methods far Processing Geometric Objects, IEEE CG&A, Feb. 1984.
• 5: [5] Q. S. Peng, An Algorithm for finding Intersection lines between two B-Spline Surfaces, CAD, v. 16 n. 4, July 1984.
• 6: [6] Victor Guillemin, Alan Pollack, Differential Topology, 1974, Prentice Hall, Inc., Englewood Cliffs, New Jersey.
• 7: Joshua Levin, A parametric algorithm for drawing pictures of solid objects composed of quadric surfaces, Communications of the ACM, v.19 n.10, p.555-563, Oct. 1976 [doi>10.1145/360349.360355]
• 8: [8] T. Varady, Surface-surface Intersections for Double-quadratic Parametric Patches in a Solid Modeller, Computer and Automation Research Institute, Hungarian Academy of Sciences.
• 9: [9] Shape Data Ltd., Romulus Programmers Manual-Version 4, Cambridge, United Kingdom, 1982.
• 10: [10] TIPS Working Group, TIPS-I, Hokkaido Univ., Institute of Precision Engg., Sapporo, Japan, 1978.
• 11: [11] Gene H. Golub, Charles F. Van Loan, Matrix Camputations, The Johns Hopkins Univ. Press, Baltimore, Maryland, 1983.
• 12: [12] James U. Korien, Solid Modelling Requirements for Robotic Applications, IBM T. J. Watson Research Center, Yorktown Heights, NY 10598.
• 13: [13] E. Catmull, A Subdivision Algorithm for Computer Display of Curved Surfaces, Univ. of Utah Comp. Sci. Dept. UTEC-CSC- 74-133, 1974.

INDEX TERMS

Primary 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

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

General Terms:
Algorithms, Design, Measurement, Theory, Verification