“An algorithm and data structure for 3D object synthesis using surface patch intersections” by Carlson

There are several successful systems that provide algorithms that allow for the intersection of polygonal objects or other primitive shapes to create more complex objects. Our intent is to provide similar algorithms for intersecting surface patches. There have been contributions to this concept at the display algorithm level, that is, computing the intersection at the time the frame is generated. In an animation environment, however, it becomes important to incorporate the intersection in the data generation routines, in order that those parts of the intersected object that never contribute to an image are not processed by the display algorithm. This only increases the complexity of the object unnecessarily, and subsequently puts an additional burden on the display algorithms. An algorithm is described which uses a modified Catmull recursive subdivision scheme to find the space curve which is the intersection of two bicubic patches. An associated data structure is discussed which incorporates this curve of intersection in the patch description in a way suitable for efficient display of the intersected object. Sample output of these intersections are shown which serve to illustrate the capabilities and limitations of the described procedures.

1. Baumgart, B.G., “Geometric Modeling for Computer Vision,” AIM-249, STAN-CS-74-463, Stanford U. Computer Sci. Dept. (October 1974).
2. Blinn, James F., “Computer Display of Curved Surfaces,” PhD Thesis , University of Utah (December 1978).
3. Braid, Ian C., “The Synthesis of Solids Bounded by Many Faces,” Comm. ACM Vol. 18(4) pp. 209-216 (April 1975).
4. Brown, C. M., “PADL-2: A Technical Summary,” IEEE Computer Graphics and Applications Vol. 2(2) pp. 69-84 (March 1982).
5. Catmull, Edwin E., “A Subdivision Algorithm for Computer Display of Curved Surfaces,” UTEC-CSc-74-133, Salt Lake City, Utah (December 1974). University of Utah Dept of Comp Science.
6. Clark, James H., “A Fast Scan-Line Algorithm for Rendering Parametric Surfaces,” Computer Graphics (SIGGRAPH 79 supplement) Vol. 13(3)(August 1979 ).
7. Cohen, Elaine, Lyche, Tom, and Riesenfeld, Richard F., “Discrete B-Splines and Subdivision Techniques in Computer-Aided Geometric Design and Computer Graphics,” Computer Graphics and Image Processing Vol. 14(2) pp. 87-111 (October 1980).
8. Forrest, A. R., “Computational Geometry -Achievements and Problems,” in Computer Aided Geometric Design, ed. Richard F. Riesenfeld, Academic Press, New York (1974).
9. Hunter, G.M., Efficient Computation and Data Structures for Graphics, Princeton U., Dept. of EE and CSc (1978). Ph.D. Dissertation.
10. Lane, Jeffrey M. and Carpenter, Loren C., “Scan Line Methods for Displaying Parametrically Defined Surfaces,” Comm. ACM Vol. 23(1) pp. 23-34 (January 1980).
11. Lane, Jeffrey M. and Riesenfeld, Richard F., “A Theoretical Development for the Computer Generation of Piecewise Polynomial Surfaces,” IEEE Trans. Pattern Analysis and Machine Intelligence Vol. PAMI-2(1) pp. 35-46 (January 1980).
12. Levin, Joshua Z., “A Parametric Algorithm for Drawing Pictures of Solid Objects Composed of Quadric Surfaces,” Comm. ACM Vol. 19(10) pp. 555-563 (October 1976).
13. Parent, Richard E., “A System for Sculpting 3-D Data,” Computer Graphics Vol. 11(2) pp. 138-147 Proc. Siggraph ’77, (Summer 1977).
14. Tilove, R. B., “Set Membership Classification: A Unified Approach to Geometric Intersection Problems,” IEEE Trans. Computers Vol. C-29(10) pp. 874-883 (Oct. 1980).
15. Whitted, J. Turner, “A Scan Line Algorithm for Computer Display of Curved Surfaces,” Computer Graphics (SIGGRAPH 78 supplement) Vol. 13(3)(August 1978 ).