Fast and simple 2D geometric proximity queries using graphics hardware

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Fast and simple 2D geometric proximity queries using graphics hardware

Full text

Pdf (1.78 MB)

Source

Symposium on Interactive 3D Graphics archive
Proceedings of the 2001 symposium on Interactive 3D graphics table of contents

Pages: 145 - 148

Year of Publication: 2001

ISBN:1-58113-292-1

Authors

Kenneth E. Hoff, III	Univ. of North Carolina, Chapel Hill
Andrew Zaferakis	Univ. of North Carolina, Chapel Hill
Ming Lin	Univ. of North Carolina, Chapel Hill
Dinesh Manocha	Univ. of North Carolina, Chapel Hill

Sponsor

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 58, Citation Count: 38

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/364338.364383 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	David Baraff, Dynamic simulation of nonpenetrating rigid bodies, Cornell University, Ithaca, NY, 1992
	2	S. Cameron, Enhancing GJK: Computing Minimum and Penetration Distance between Convex Polyhedra. International Conference on Robotics and Automation, 3112-3117, 1997
	3	D. Dobkin, J. Hershberger, D. Kirkpatrick, S. Suri, Computing the Intersection Depth of Polyhedra. Algorithmica, 9(6), 518-533, 1993
	4	S. Ehmann and M. Lin. Accelerated Proximity Queries Between Convex Polyhedra By Multi-Level Voronoi Marching. Proc. International Conf. on Intelligent Robots and Systems, 2000
	5	Sarah F. Frisken , Ronald N. Perry , Alyn P. Rockwood , Thouis R. Jones, Adaptively sampled distance fields: a general representation of shape for computer graphics, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.249-254, July 2000 [doi>10.1145/344779.344899]
	6	E. G. Gilbert, D. W. Johnson, S.S. Keerthi. A Fast Procedure for Computing the Distance Between Objects in Three-Dimensional Space. IEEE J. Robotics and Automation, RA(4): 193-203, 1988
	7	Jack Goldfeather , Steven Monar , Greg Turk , Henry Fuchs, Near Real-Time CSG Rendering Using Tree Normalization and Geometric Pruning, IEEE Computer Graphics and Applications, v.9 n.3, p.20-28, May 1989 [doi>10.1109/38.28107]
	8	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 [doi>10.1145/237170.237244]
	9	Gentaro Hirota , Susan Fisher , Ming Lin, Simulation of Non-penetrating Elastic Bodies Using Distance Fields, University of North Carolina at Chapel Hill, Chapel Hill, NC, 2000
	10	Kenneth E. Hoff, III , John Keyser , Ming Lin , Dinesh Manocha , Tim Culver, Fast computation of generalized Voronoi diagrams using graphics hardware, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.277-286, July 1999 [doi>10.1145/311535.311567]
	11	K. Hoff, T. Culver, J. Keyser, M. Lin, and D. Manocha. Interactive Motion Planning Using Hardware-Accelerated Computation of Generalized Voronoi Diagrams. Proc. of IEEE International Conf. on Robotics and Automation, 2000
	12	P. M. Hubbard, Interactive Collision Detection. IEEE Symposium on Research Frontiers in Virtual Reality. 24-31, 1993
	13	R. Kimmel, N. Kiryati, A. Bruckstein, Multi-Valued Distance Maps for Motion Planning on Surfaces with Moving Obstacles. IEEE Transactions on Robotics and Automation, vol 14: 427-438, 1998
	14	D. Johnson, E. Cohen, A Framework for Efficient Minimum Distance Computation, IEEE Conf. On Robotics and Animation, 3678-3683, 1998
	15	Jed Lengyel , Mark Reichert , Bruce R. Donald , Donald P. Greenberg, Real-time robot motion planning using rasterizing computer graphics hardware, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.327-335, September 1990, Dallas, TX, USA
	16	M. Lin, J. Canny. Efficient Algorithms for Incremental Distance Computation. IEEE Transactions on Robotics and Automation, 1991
	17	Brian Vincent Mirtich, Impulse-based dynamic simulation of rigid body systems, 1996
	18	C. Pisula, K. Hoff, M. Lin, and D. Manocha. Randomized Path Planning for a Rigid Body Based on Hardware Accelerated Voronoi Sampling. Proc. of Workshop on Algorithmic Foundations of Robotics, 2000
	19	S. Quinlan, Efficient Distance Computation between Non-Convex Objects. International Conf. on Robotica and Automation, 3324-3329, 1994
	20	Jarek Rossignac , Abe Megahed , Bengt-Olaf Schneider, Interactive inspection of solids: cross-sections and interferences, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.353-360, July 1992
	21	J. Sethian, Level Set Methods, Cambridge University Press, 1996
	22	J. Snyder, A. Woodbury, K. Fleischer, B. Currin, A. Barr, Interval Methods for Multi-Point Collisions Between Time Dependent Curved Surfaces. ACM Computer Graphics, 321-334, 1993

CITED BY 38

	Young J. Kim , Gokul Varadhan , Ming C. Lin , Dinesh Manocha, Fast swept volume approximation of complex polyhedral models, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA
	Young J. Kim , Miguel A. Otaduy , Ming C. Lin , Dinesh Manocha, Fast penetration depth computation for physically-based animation, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas
	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
	Naga K. Govindaraju , Ming C. Lin , Dinesh Manocha, Fast and Reliable Collision Culling Using Graphics Hardware, IEEE Transactions on Visualization and Computer Graphics, v.12 n.2, p.143-154, March 2006
	Miguel A. Otaduy , Ming C. Lin, Sensation preserving simplification for haptic rendering, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
	Michael Wainer, Interactive computation and visualization of fetch using standard computer graphics hardware, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
	Susan Fisher , Ming C. Lin, Deformed distance fields for simulation of non-penetrating flexible bodies, Proceedings of the Eurographic workshop on Computer animation and simulation, p.99-111, September 02-03, 2001, Manchester, UK
	Young J. Kim , Miguel A. Otaduy , Ming C. Lin , Dinesh Manocha, Six-degree-of-freedom haptic rendering using incremental and localized computations, Presence: Teleoperators and Virtual Environments, v.12 n.3, p.277-295, 1 June 2003
	Sarah F. Frisken , Ronald N. Perry, Efficient estimation of 3D Euclidean distance fields from 2D range images, Proceedings of the 2002 IEEE symposium on Volume visualization and graphics, October 28-29, 2002, Boston, Massachusetts
	Chengyu Sun , Divyakant Agrawal , Amr El Abbadi, Hardware acceleration for spatial selections and joins, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	Miguel A. Otaduy , Ming C. Lin, CLODs: dual hierarchies for multiresolution collision detection, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
	Naga K. Govindaraju , Stephane Redon , Ming C. Lin , Dinesh Manocha, CULLIDE: interactive collision detection between complex models in large environments using graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
	Young J. Kim , Ming C. Lin , Dinesh Manocha, Incremental Penetration Depth Estimation between Convex Polytopes Using Dual-Space Expansion, IEEE Transactions on Visualization and Computer Graphics, v.10 n.2, p.152-163, March 2004
	Kaoru Sugita , Takeshi Naemura , Hiroshi Harashima, Performance evaluation of programmable graphics hardware for image filtering and stereo matching, Proceedings of the ACM symposium on Virtual reality software and technology, October 01-03, 2003, Osaka, Japan
	Benjamin Lok , Samir Naik , Mary Whitton , Frederick P. Brooks, Jr., Incorporating dynamic real objects into immersive virtual environments, Proceedings of the 2003 symposium on Interactive 3D graphics, April 27-30, 2003, Monterey, California
	Zhaowei Fan , Huagen Wan , Shuming Gao, Simple and rapid collision detection using multiple viewing volumes, Proceedings of the 2004 ACM SIGGRAPH international conference on Virtual Reality continuum and its applications in industry, June 16-18, 2004, Singapore
	Avneesh Sud , Naga Govindaraju , Russell Gayle , Dinesh Manocha, Interactive 3D distance field computation using linear factorization, Proceedings of the 2006 symposium on Interactive 3D graphics and games, March 14-17, 2006, Redwood City, California
	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
	Wei Chen , Huagen Wan , Hongxin Zhang , Hujun Bao , Qunsheng Peng, Interactive collision detection for complex and deformable models using programmable graphics hardware, Proceedings of the ACM symposium on Virtual reality software and technology, November 10-12, 2004, Hong Kong
	Naga K. Govindaraju , Ming C. Lin , Dinesh Manocha, Fast and reliable collision culling using graphics hardware, Proceedings of the ACM symposium on Virtual reality software and technology, November 10-12, 2004, Hong Kong
	Naga K. Govindaraju , Ming C. Lin , Dinesh Manocha, Efficient collision culling among deformable objects using graphics processors, Presence: Teleoperators and Virtual Environments, v.15 n.1, p.62-76, February 2006
	Stephane Redon , Young J. Kim , Ming C. Lin , Dinesh Manocha, Fast continuous collision detection for articulated models, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	Sarah F. Frisken , Ronald N. Perry, Designing with distance fields, ACM SIGGRAPH 2006 Courses, July 30-August 03, 2006, Boston, Massachusetts
	Mashhuda Glencross , Alan G. Chalmers , Ming C. Lin , Miguel A. Otaduy , Diego Gutierrez, Exploiting perception in high-fidelity virtual environments Additional presentations from the 24th course are available on the citation page , ACM SIGGRAPH 2006 Courses, July 30-August 03, 2006, Boston, Massachusetts
	Yiyu Cai , Zhaowei Fan , Huagen Wan , Shuming Gao , Baifang Lu , Kian Teck Lim, Hardware-accelerated collision detection for 3D virtual reality gaming, Simulation and Gaming, v.37 n.4, p.476-490, December 2006
	Miguel A. Otaduy , Ming C. Lin, Sensation preserving simplification for haptic rendering, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California
	Miguel A. Otaduy , Ming C. Lin, Introduction to haptic rendering, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California
	Naga K. Govindaraju , Ilknur Kabul , Ming C. Lin , Dinesh Manocha, Fast continuous collision detection among deformable models using graphics processors, Computers and Graphics, v.31 n.1, p.5-14, January, 2007
	Nagender Bandi , Chengyu Sun , Divyakant Agrawal , Amr El Abbadi, Hardware acceleration in commercial databases: a case study of spatial operations, Proceedings of the Thirtieth international conference on Very large data bases, p.1021-1032, August 31-September 03, 2004, Toronto, Canada
	Wingo Sai-Keung Wong , George Baciu, Hardware-Based Collision and Self-Collision for Rigid and Deformable Surfaces, Presence: Teleoperators and Virtual Environments, v.13 n.6, p.681-691, December 2004
	Young J. Kim , Stephane Redon , Ming C. Lin , Dinesh Manocha , Jim Templeman, Interactive Continuous Collision Detection Using Swept Volume for Avatars, Presence: Teleoperators and Virtual Environments, v.16 n.2, p.206-223, April 2007
	L. Pomante , P. Di felice, Ad-hoc HW/SW architectures for DBMSs: a co-design approach, Proceedings of the 6th Conference on 6th WSEAS Int. Conf. on Artificial Intelligence, Knowledge Engineering and Data Bases, p.153-158, February 16-19, 2007, Corfu Island, Greece
	Nagender Bandi , Chengyu Sun , Divyakant Agrawal , Amr El Abbadi, Fast computation of spatial selections and joins using graphics hardware, Information Systems, v.32 n.8, p.1073-1100, December, 2007
	Avneesh Sud , Erik Andersen , Sean Curtis , Ming Lin , Dinesh Manocha, Real-time path planning for virtual agents in dynamic environments, ACM SIGGRAPH 2008 classes, August 11-15, 2008, Los Angeles, California
	Dror Aiger , Klara Kedem, Applying graphics hardware to achieve extremely fast geometric pattern matching in two and three dimensional transformation space, Information Processing Letters, v.105 n.6, p.224-230, March, 2008
	Xinyu Zhang , Young J. Kim, Interactive Collision Detection for Deformable Models Using Streaming AABBs, IEEE Transactions on Visualization and Computer Graphics, v.13 n.2, p.318-329, March 2007
	Anderson Maciel , Ronan Boulic , Daniel Thalmann, Efficient Collision Detection within Deforming Spherical Sliding Contact, IEEE Transactions on Visualization and Computer Graphics, v.13 n.3, p.518-529, May 2007
	Adarsh Krishnamurthy , Sara McMains , Kirk Halle, Accelerating geometric queries using the GPU, 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling, October 05-08, 2009, San Francisco, California