Incremental algorithms for collision detection between solid models

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Incremental algorithms for collision detection between solid models

Full text

Pdf (1.24 MB)

Source

ACM Symposium on Solid and Physical Modeling archive
Proceedings of the third ACM symposium on Solid modeling and applications table of contents

Salt Lake City, Utah, United States

Pages: 293 - 304

Year of Publication: 1995

ISBN:0-89791-672-7

Authors

Madhav Ponamgi	Department of Computer Science, University of North Carolina, Chapel Hill, NC
Dinesh Manocha	Department of Computer Science, University of North Carolina, Chapel Hill, NC
Ming C. Lin	Department of Computer Science, University of North Carolina, Chapel Hill, NC

Sponsor

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 67, Citation Count: 20

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/218013.218076 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.

	AANJ94	Alejandro Garcia-Alonso , Nicolás Serrano , Juan Flaquer, Solving the Collision Detection Problem, IEEE Computer Graphics and Applications, v.14 n.3, p.36-43, May 1994 [doi>10.1109/38.279041]
	AP76	A.Appel and P.Will. Determining the three-dimensional convex hull of a polyhedron. IBM Journal of Research and Development, pages 590-600, 1976.
	Bor90	David Baraff, Curved surfaces and coherence for non-penetrating rigid body simulation, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.19-28, Aug. 1990
	Bar92	David Baraff, Dynamic simulation of nonpenetrating rigid bodies, Cornell University, Ithaca, NY, 1992
	BT92	Chanderjit L. Bajaj , Tamal K. Dey, Convex decomposition of polyhedra and robustness, SIAM Journal on Computing, v.21 n.2, p.339-364, April 1992 [doi>10.1137/0221025]
	Cam91	Stephen Cameron, Approximation hierarchies and S-bounds, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.129-137, June 05-07, 1991, Austin, Texas, United States [doi>10.1145/112515.112537]
	Can86	J Canny, Collision detection vkr moving polyhedra, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.2, p.200-209, March 1986 [doi>10.1109/TPAMI.1986.4767773]
	CC86	S. Cameron and R. K. Culley. Determining the minimum translational distance between two convex polyhedra. Proceedings of International Conference on Robotics and Automation, pages pp. 591-596, 1986.
	CD87	B. Chazelle , D. P. Dobkin, Intersection of convex objects in two and three dimensions, Journal of the ACM (JACM), v.34 n.1, p.1-27, Jan. 1987 [doi>10.1145/7531.24036]
	Cha84	Bernard Chazelle, Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm, SIAM Journal on Computing, v.13 n.3, p.488-507, August 1984 [doi>10.1137/0213031]
	Cha89	B. Chazelle. An optimal algorithm for intersecting threedimensional convex polyhedra. In Proc. 80th Anna. IEEE Sympos. Found. Comput. Sci., pages 586-591, 1989.
	CLMP95	Jonathan D. Cohen , Ming C. Lin , Dinesh Manocha , Madhav Ponamgi, I-COLLIDE: an interactive and exact collision detection system for large-scale environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.189-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199437]
	DF78	D.Muller and F.Preparata. Finding the intersection of two convex polyhedra. Theoretical Computer Science, 8(2):217-236, 1978.
	DK85	D.P. Dobkin and D. G. Kirkpatrick. A linear algorithm for determining the separation of convex pol yhedra. J. Algorithms, 6:381-392, 1985.
	Duf92	Tom Duff, Interval arithmetic recursive subdivision for implicit functions and constructive solid geometry, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.131-138, July 1992
	DZ93	P. Dworkin and D. Zeltzer. A new model for efficient dynamics simulation. Proceedings gurographics workshop on animation and simulation, pages 175-184, 1993.
	ea93	John M. Snyder , Adam R. Woodbury , Kurt Fleischer , Bena Currin , Alan H. Barr, Interval methods for multi-point collisions between time-dependent curved surfaces, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.321-334, September 1993 [doi>10.1145/166117.166158]
	FKN80	Henry Fuchs , Zvi M. Kedem , Bruce F. Naylor, On visible surface generation by a priori tree structures, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.124-133, July 14-18, 1980, Seattle, Washington, United States
	HBZ90	Brian Von Herzen , Alan H. Barr , Harold R. Zatz, Geometric collisions for time-dependent parametric surfaces, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.39-48, Aug. 1990
	HH87	C.M. Hoffmann and J. E. Hopcroft. Simulation of physical systems from geometric models. IEEE Journal on Robotics and Automation, 3(3):194-206, 1987.
	Hop88	J.E. Hopcroft. Electronic prototyping. IEEE Transactions on Aerospace and Electronic Systems, 24(2):663- 667, 1988.
	Hub93	P.M. Hubbard. Interactive collision detection. In Proceedings o.f IEEE Symposium on Research Frontiers in Virtual Reality, October 1993.
	LC91	M.C. Lin and John F. Canny. Efficient algorithms for incremental distance computation. In IEEE Con}erence on Robotics and Automation, 1991.
	Lin93	Ming Chieh Lin , John F. Canny, Efficient collision detection for animation and robotics, 1993
	LM95	M.C. Lin and Dinesh Manocha. Efficient contact determination between geometric models. International Journal of Computational Geometry and Applications, 1995. To appear.
	Lou66	P. Loutrel. Determination of hidden edges in polyhedral figures. Technical Report NYU-3-12-1966, Department of Computer Science, New York University, 1966.
	MW88	Matthew Moore , Jane Wilhelms, Collision detection and response for computer animationr3, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.289-298, Aug. 1988
	NAT90	Bruce Naylor , John Amanatides , William Thibault, Merging BSP trees yields polyhedral set operations, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.115-124, September 1990, Dallas, TX, USA
	Nay92	Bruce F. Naylor, Interactive solid geometry via partitioning trees, Proceedings of the conference on Graphics interface '92, p.11-18, September 1992, Vancouver, British Columbia, Canada
	O’R94	Joseph O'Rourke, Computational geometry in C, Cambridge University Press, New York, NY, 1994
	PML94	Madhav K. Ponamgi , Dinesh Manocha , Ming C. Lin, Incremental Algorithms for Collision Detection Between General Solid Models, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1994
	PS85	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	Tur89	G. Turk. Interactive collision detection for molecular graphics. Master's thesis, Computer Science Department, University of North Carolina at Chapel Hill, 1989.
	WG91	W.Bouma and G.Vanecek. Collision detection and analysis in a physically based simulation. Proceedings Eurographics workshop on animation and simulation, pages 191-203, 1991.
	WG93	William J. Bouma , George Vaněček, Jr., Modeling contacts in a physically based simulation, Proceedings on the second ACM symposium on Solid modeling and applications, p.409-418, May 19-21, 1993, Montreal, Quebec, Canada [doi>10.1145/164360.164496]

CITED BY 20

	David E. Johnson , Peter Willemsen , Elaine Cohen, Six Degree-of-Freedom Haptic Rendering Using Spatialized Normal Cone Search, IEEE Transactions on Visualization and Computer Graphics, v.11 n.6, p.661-670, November 2005
	Madhav K. Ponamgi , Dinesh Manocha , Ming C. Lin, Incremental Algorithms for Collision Detection Between Polygonal Models, IEEE Transactions on Visualization and Computer Graphics, v.3 n.1, p.51-64, January 1997
	Madhav Ponamgi , Ming C. Lin , Dinesh Manocha, Incremental collision detection for polygonal models, Proceedings of the eleventh annual symposium on Computational geometry, p.445-446, June 05-07, 1995, Vancouver, British Columbia, Canada
	SonOu Lee , JunHyeok Heo , KwangYun Wohn, An efficient collision detection algorithm using range data for walk-through systems, Proceedings of the ACM symposium on Virtual reality software and technology, p.119-123, September 1997, Lausanne, Switzerland
	Julien Basch , Jeff Erickson , Leonidas J. Guibas , John Hershberger , Li Zhang, Kinetic collision detection between two simple polygons, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.102-111, January 17-19, 1999, Baltimore, Maryland, United States
	John Hershberger, Kinetic collision detection with fast flight plan changes, Information Processing Letters, v.92 n.6, p.287-291, 31 December 2004
	Bedřich Beneš , Nestor Goméz Villanueva, GI-COLLIDE: collision detection with geometry images, Proceedings of the 21st spring conference on Computer graphics, May 12-14, 2005, Budmerice, Slovakia
	George Baciu , Wingo Sai-Keung Wong , Hanqiu Sun, Hardware-assisted virtual collisions, Proceedings of the ACM symposium on Virtual reality software and technology, p.145-151, November 02-05, 1998, Taipei, Taiwan
	Julien Basch , Jeff Erickson , Leonidas J. Guibas , John Hershberger , Li Zhang, Kinetic collision detection between two simple polygons, Computational Geometry: Theory and Applications, v.27 n.3, p.211-235, March 2004
	David M. Mount , Nathan S. Netanyahu , Christine D. Piatko , Ruth Silverman , Angela Y. Wu, A computational framework for incremental motion, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	George Baciu , Wingo Sai-Keung Wong, Image-based collision detection, Integrated image and graphics technologies, Kluwer Academic Publishers, Norwell, MA, 2004
	Ari Rappoport , Steven Spitz, Interactive Boolean operations for conceptual design of 3-D solids, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.269-278, August 1997
	S. Gottschalk , M. C. Lin , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996
	George Baciu , Wingo S. K. Wong, Image-Based Techniques in a Hybrid Collision Detector, IEEE Transactions on Visualization and Computer Graphics, v.9 n.2, p.254-271, April 2003
	Pankaj Agarwal , Leonidas Guibas , An Nguyen , Daniel Russel , Li Zhang, Collision detection for deforming necklaces, Computational Geometry: Theory and Applications, v.28 n.2-3, p.137-163, June 2004
	George Baciu , Wingo Sai-Keung Wong, Hardware-assisted self-collision for deformable surfaces, Proceedings of the ACM symposium on Virtual reality software and technology, November 11-13, 2002, Hong Kong, China
	Philip M. Hubbard, Approximating polyhedra with spheres for time-critical collision detection, ACM Transactions on Graphics (TOG), v.15 n.3, p.179-210, July 1996
	Eran Guendelman , Robert Bridson , Ronald Fedkiw, Nonconvex rigid bodies with stacking, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
	James T. Klosowski , Martin Held , Joseph S. B. Mitchell , Henry Sowizral , Karel Zikan, Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs, IEEE Transactions on Visualization and Computer Graphics, v.4 n.1, p.21-36, January 1998
	George Baciu , Wingo Sai-Keung Wong, Image-Based Collision Detection for Deformable Cloth Models, IEEE Transactions on Visualization and Computer Graphics, v.10 n.6, p.649-663, November 2004