A surface intersection algorithm based on loop detection

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A surface intersection algorithm based on loop detection

Full text

Pdf (1.02 MB)

Source

ACM Symposium on Solid and Physical Modeling archive
Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications table of contents

Austin, Texas, United States

Pages: 197 - 207

Year of Publication: 1991

ISBN:0-89791-427-9

Author

Michael E. Hohmeyer

Computer Science Division, Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, California

Sponsor

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 47, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/112515.112543 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P. R. Arner. Another Look at Surface/Surface Intersection. PhD thesis, University of Utah, Salt Lake City, 1987.
	2	Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition I: the basic algorithm, SIAM Journal on Computing, v.13 n.4, p.865-877, Nov. 1984 [doi>10.1137/0213054]
	3	C. Asteasu, Intersection of arbitrary surfaces, Computer-Aided Design, v.20 n.9, p.533-538, Nov. 1988 [doi>10.1016/0010-4485(88)90043-7 ]
	4	D. Ayala, Boolean operations between solids and surfaces by octrees: models and algorithms, Computer-Aided Design, v.20 n.10, p.452-465, Oct. 1988
	5	Chanderjit Bajaj, Thomas Garrity, and Joe Warren. On the applications of multi-equational resultants. Technical Report TR88-83, Rice University,, Houston, Texas, November 1988.
	6	Chanderjit L. Bajaj, Christoph M. Hoffmann, and John E. Hopcroft. Tracing planar algebraic curves. Technical Report CSD-TR-637, Department of Computer Science, Purdue University, West Lafayette, indiana 47907, September 1987.
	7	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 ]
	8	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 ]
	9	Wayne E. Carlson, An algorithm and data structure for 3D object synthesis using surface patch intersections, Proceedings of the 9th annual conference on Computer graphics and interactive techniques, p.255-263, July 26-30, 1982, Boston, Massachusetts, United States
	10	M. S. Casale , J. E. Bobrow, A set operation algorithm for sculptured solids modeled with trimmed patches, Computer Aided Geometric Design, v.6 n.3, p.235-247, Aug. 1989 [doi>10.1016/0167-8396(89)90026-5 ]
	11	Malcolm S. CasMe. Free-form solid modeling with trimmed surface patches. IEEE Computer Graphics and Applications, 7(1):33-43, January 1987.
	12	Vijay Chandru and Bipin S. Kochar. Analytic techniques for geometric intersection problems. In Gerald E. Farin, editor, Geometric Modeling: Algorithms and New Trends, pages 305-318. SIAM, Philadelphia, 1987.
	13	J. J. Chen and T. M. Ozsoy. An intersection algorithm for C2 parametric surfaces. In Knowledge Engineering and Computer Modelling, pages 69- 77. 1986.
	14	J. J. Chen , T. M. Ozsoy, Predictor-corrector type of intersection algorithm for C2 parametric surfaces, Computer-Aided Design, v.20 n.6, p.347-352, July/Aug. 1988 [doi>10.1016/0010-4485(88)90117-0]
	15	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
	16	T. Dokken. Finding intersections of B-spline representations using recursive subdivision. Computer Aided Geometric Design, 2:189-196, 1985.
	17	Rida T. Farouki, Trimmed-surface algorithms for the evaluation and interrogation of solid boundary representations, IBM Journal of Research and Development, v.31 n.3, p.314-334, May 1, 1987
	18	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]
	19	Rida T. Farouki. Direct surface section evaluation. In Gerald Farin, editor, Geometric Modeling: Algorithms and New Trends, pages 319-334. SIAM, Philadelphia, 1987.
	20	Daniel Filip, Robert Markot, and Robert Madgedson. Using bounds on derivatives in computer aided geometric design. Submitted for publication.
	21	S. L. Hanna, J. F. Abel, and D. P. Greenberg. Intersection of parametric surfaces by means of lookup tables. IEEE Computer Graphics and Applications, 3(3), October 1983.
	22	Robin Hartshorne. Algebraic Geoemtry. Springer- Verlag, New York, 1977.
	23	Christoff M. Hoffmann. A dimensionality paradigm for surface interrogations. Technical Report CER-87-45, Department of Computer Science, Purdue University, December 1988.
	24	Christoph M. Hoffmann. Algebraic curves. Technical Report Technical Report, Computer Science Department, Purdue University, West Lafayette, Indiana 47907, May 1987.
	25	Christoph M. Hoffmann. Applying algebraic geometry to surface intersection evaluation. Technical Report CSD-TR-772, Computer Science Department, Purdue University, West Lafayette, Indiana 47907, April 1988.
	26	Christoph M. Hoffmann and Robert E. Lynch. Following space curves numerically. Technical Report CSD-TR-684, Computer Science Department, Purdue University, West Lafayette, Indiana 47907, May 1987.
	27	E. G. Houghton, R. F. Emnet, J. D. Factor, and C. L. Sabharwal. Implementation of divide-andconquer method for intersection of parametric sirfaces. Computer Aided Geometric Design, pages 173-183, 1985.
	28	John Keith Johnstone, The sorting of points along an algebraic curve, 1987
	29	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 ]
	30	Joshua Z. Levin. Mathematical models for determining the intersections of quadric surfaces. Computer Graphics and Image Processing, 11:73-87, September 1979.
	31	R. P. Markot , R. L. Magedson, Solutions of tangential surface and curve intersections, Computer-Aided Design, v.21 n.7, p.421-429, Sep. 1989 [doi>10.1016/0010-4485(89)90126-7 ]
	32	James R. Miller, Geometric approaches to nonplanar quadric surface intersection curves, ACM Transactions on Graphics (TOG), v.6 n.4, p.274-307, Oct. 1987 [doi>10.1145/35039.35041]
	33	James R. Miller. Sculptured surfaces in solid models: Issues and alternative approaches. IEEE Computer Graphics and Applications, 6(12):33-43, 1987.
	34	James R. Miller, Analysis of Quadric-Surface-Based Solid Models, IEEE Computer Graphics and Applications, v.8 n.1, p.28-42, January 1988 [doi>10.1109/38.488 ]
	35	B. K. Natarajan, On computing the intersection of B-splines (extended abstract), Proceedings of the sixth annual symposium on Computational geometry, p.157-167, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98559]
	36	J. Owen and A. Rockwood. intersection of general implicit surfaces. In Gerald Farin, editor, Geometric Modeling: Algorithms and Trends. SIAM Publications, Philadelphia, 1987.
	37	Qun Sheng Peng. An algorithm for finding the intersection lines between two B-spline surfaces. Computer-Aided Design, 16(4), July 1984.
	38	H. U. Pfeifer. Methods for intersecting geometrical entities in the gpm module for volume geometry. Computer-Aided Design, 17(7):311-318, September 1985.
	39	M. B. Phillips and G. M. Odell. An algorithm for locating and displaying the intersection of two arbitrary surfaces. IEEE Computer Graphics and Applications, 4(9):48-58, 1984.
	40	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 ]
	41	M. J. Pratt and A. D. Geisow. Surface/surface intersection problems. In Gregory J. A., editor, The Mathematics of Surfaces, pages 117-142. Claredon Press, Oxford, 1986.
	42	Malcolm A. Sabin. Interrogation Techniques .for Parametric Surfaces, pages 1095-1118. Plenum Press, London and New York, 1971.
	43	Malcolm A. Sabin. A method for displaying the intersection curve of two quadric surfaces. The Computer Journal, 19:336-338, November 1976.
	44	Ramon F. Sarraga. Algebraic methods for intersections of quadric surfaces in gmsolid. Computer Vision, Graphics and Image Processing, 22(2):222-238, May 1983.
	45	T. W. Sederberg , H. N. Christiansen , S. Katz, Improved test for closed loops in surface intersections, Computer-Aided Design, v.21 n.10, p.505-508, Oct. 1989
	46	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 ]
	47	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]
	48	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]
	49	Jack Scott Snoeyink. Intersecting trimmed quadric surface patches: a geometric method using parametric functions. Submitted for publication, 1990.
	50	Spencer Woodlief Thomas, Modelling volumes bounded by b-spline surfaces, 1984

CITED BY 6

	Ioana Boier-Martin , Denis Zorin, Differentiable parameterization of Catmull-Clark subdivision surfaces, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France
	A. Galligo , M. Stillman, On the geometry of parametrized bicubic surfaces, Journal of Symbolic Computation, v.42 n.1-2, p.136-158, January, 2007
	Nicholas M. Patrikalakis, Surface-to-Surface Intersections, IEEE Computer Graphics and Applications, v.13 n.1, p.89-95, January 1993
	Gershon Elber , Elaine Cohen, Arbitrarily precise computation of Gauss maps and visibility sets for freeform surfaces, Proceedings of the third ACM symposium on Solid modeling and applications, p.271-279, May 17-19, 1995, Salt Lake City, Utah, United States
	Xianming Chen , Richard F. Riesenfeld , Elaine Cohen , James Damon, Theoretically-based algorithms for robustly tracking intersection curves of deforming surfaces, Computer-Aided Design, v.39 n.5, p.389-397, May, 2007
	André Galligo , Jean Pascal Pavone, Selfintersections of a bézier bicubic surface, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.148-155, July 24-27, 2005, Beijing, China