Article

A voxel-based parallel collision detection algorithm

Authors:

Orion Sky Lawlor,

Laxmikant V. KaléeAuthors Info & Claims

ICS '02: Proceedings of the 16th international conference on Supercomputing

Pages 285 - 293

https://doi.org/10.1145/514191.514231

Published: 22 June 2002 Publication History

Abstract

Two physical objects cannot occupy the same space at the same time. Simulated physical objects do not naturally obey this constraint. Instead, we must detect when two objects have collided---we must perform collision detection. This work presents a simple voxel-based collision detection algorithm, an efficient parallel implementation of the algorithm, and performance results.

References

[1]

S. Bandi and D. Thalmann. An adaptive spatial subdivision of the object space for fast collision of animated rigid bodies. In Proceedings of Eurographics '95, pages 259--270, August 1995. http://ligwww.epfl.ch/~thalmann/

[2]

S. Brown, S. Attaway, S. Plimpton, and B. Hendrickson. Parallel strategies for crash and impact simulations. Computer Methods in Applied Mechanics and Engineering, 184:375--390, 2000

[3]

R. Brunner and L. Kalée. Adapting to load on workstation clusters. In The Seventh Symposium on the Frontiers of Massively Parallel Computation, pages 106--112, February 1999

Digital Library

[4]

S. Cameron. Approximation hierarchies and s-bounds. In Proceedings of Symposium on Solid Modeling Foundations and CAD/CAM Applications, pages 129--137, 1991

Digital Library

[5]

B. Curless and M. Levoy. A volumetric method for building complex models from range images. In Proceedings of ACM Siggraph '96, pages 303--312, 1996

Digital Library

[6]

R. Farouki, C Neff, and M. O'Connor. Automatic parsing of degnerate quadric-surface intersections. ACM Transactions on Graphics, 8:174--203, 1989

Digital Library

[7]

H. Fuchs, Z. Kedem, and B. Naylor. On visible surface generation by a priori tree structures. Proceedings of ACM Siggraph, pages 124--133, 1980

Digital Library

[8]

V. Gaede and O. Günther. Multidimensional access methods. ACM Computing Surveys, 30(2):170--231, June 1998

Digital Library

[9]

E. Gilbert, D. Johnson, and S. Keerthi. A fast procedure for computing the distance between objects in three-dimensional space. IEEE Journal of Robotics and Automation, RA-4:193--203, 1988

[10]

S. Gottschalk, M. Lin, and D. Manocha. Obb-tree: A heirarchical structure for rapid interference detection. In Proceedings of ACM Siggraph '96, pages 171--180, 1996

Digital Library

[11]

Chris Hecker. Let's get to the (floating) point. Game Developer Magazine, Feb/Mar, 1996

[12]

P. Hubbard. Efficient Collision Detection for Animation and Robotics. PhD thesis, Brown University, 1994

[13]

P. Jiménez, F. Thomas, and C. Torras. 3d collision detection: A survey. Computers and Graphics, 25(2):269--285, 2001

[14]

L. Kale and S. Krishnan. Charm++: Parallel Programming with Message-Driven Objects. In Parallel Programming using C++, pages 175--213. 1996. http://charm.cs.uiuc.edu/

[15]

L. Kalée, R. Skeel, M. Bhandarkar, R. Brunner, A. Gursoy, N. Krawetz, J. Phillips, A. Shinozaki, K. Varadarajan, and K. Schulten. NAMD2: Greater scalability for parallel molecular dynamics. Journal of Computational Physics, 151:283--312, 1999

Digital Library

[16]

K. Kawachi and H. Suzuki. Distance computation between non-convex polyhedra at short range based on discrete voronoi regions. In Proceedings of Geometric Modeling and Procesing, pages 123--128, Hong Kong, 2000. IEEE

Digital Library

[17]

J. Klosowski, M. Held, J. Mitchell, H. Sowizral, and K. Zikan. Efficient collision detection using bounding volumes of k-dops. In Siggraph '96 Visual Proceedings, page 151, 1996

[18]

S. Krishnan, A. Pattekar, M. Lin, and D. Manocha. A higher order bounding volume for fast proximity queries. In Proceedings of Third International Workshop on Algorithmic Foundations of Robotics, 1998

Digital Library

[19]

O. Lawlor. A grid-based parallel collision detection algorithm. Master's thesis, University of Illinois at Urbana-Champaign, March 2001. http://charm.cs.uiuc.edu/papers/

[20]

O. Lawlor and L. Kalée. Supporting dynamic parallel object arrays. In Proceedings of International Symposium on Computing in Object-oriented Parallel Environments, Stanford, CA, Jun 2001. http://charm.cs.uiuc.edu/papers/

Digital Library

[21]

M. Lin. Efficient Collision Detection for Animation and Robotics. PhD thesis, University of California, Berkeley, 1993

Digital Library

[22]

M. Lin and J. Canny. Efficient algorithms for incremental distance computation. IEEE Conference on Robotics and Automation, pages 1008--1014, 1991

[23]

M. Lin and S. Gottschalk. Collision detection between geometric models: A survey. In Proceedings of IMA Conference on Mathematics of Surfaces, 1998. http://www.cs.unc.edu/~dm/collision.html

[24]

S. Suri, P. Hubbard, and J. Hughes. Analyzing bounding boxes for object intersections. ACM Transactions on Graphics, 18 no. 3:257--277, July 1999

Digital Library

[25]

G. Turk. Interactive collision detection for molecular graphics. Master's thesis, University of North Carolina at Chapel Hill, 1989

[26]

Y. Zhou and S. Suri. Analysis of a bounding box heuristic for object intersection. Journal of the ACM, 46 no. 6:833--857, November 1999

Digital Library

[27]

M. Zyda, W. Osborne, J. Monahan, and D. Pratt. Npsnet: Real-time collision detection and response. Journal of Visualization and Computer Animation, 4, number 1:13--24, 1993

Cited By

Delgado Díez SCerrada Somolinos CGómez Palomo S(2024)Optimizing Surface Voxelization for Triangular Meshes with Equidistant Scanlines and Gap DetectionComputer Graphics Forum10.1111/cgf.1519543:6Online publication date: 4-Sep-2024
https://doi.org/10.1111/cgf.15195
Song MKim YKim MPark D(2024)Graph-based 3D Collision-distance Estimation Network with Probabilistic Graph Rewiring2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10611465(10939-10945)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10611465
Ghafarian Tamizi MHonari HNozdryn-Plotnicki ANajjaran H(2024)End-to-end deep learning-based framework for path planning and collision checking: bin-picking applicationRobotica10.1017/S0263574724000109(1-19)Online publication date: 13-Feb-2024
https://doi.org/10.1017/S0263574724000109
Show More Cited By

Index Terms

A voxel-based parallel collision detection algorithm
1. Computing methodologies
  1. Modeling and simulation

Recommendations

A Real-time Robot Arm Collision Detection Algorithm
MACE '12: Proceedings of the 2012 Third International Conference on Mechanic Automation and Control Engineering

Collision detection is a important issue in the field of industrial robot path planning and virtual reality. In this paper the author on the basis of existing research, put forward a real-time collision detection algorithm for industrial robot arm. The ...
Efficient Collision Detection for Industrial Robot Simulation System
ICIRA 2015: Proceedings of the 8th International Conference on Intelligent Robotics and Applications - Volume 9246

As the result of an increasing number of industrial robots, the simulation of industrial robot has become a very active research field. Collision detection for industrial robot simulation system is an essential part. In this paper, we present two kinds ...
Collision detection algorithm in virtual environment of robot workcell
AICI'10: Proceedings of the 2010 international conference on Artificial intelligence and computational intelligence: Part I

Rapid and accurate collision detection is necessary to robot programming and simulation system based on virtual reality. A collision detection algorithm based on the data structure of the pre-built scene graph is proposed. It is the hierarchical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICS '02: Proceedings of the 16th international conference on Supercomputing

June 2002

338 pages

ISBN:1581134835

DOI:10.1145/514191

General Chair:
Kemal Ebcioglu
IBM T.J. Watson Research Center
,
Program Chairs:
Keshav Pingali
Cornell University
,
Alex Nicolau
University of California

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ICS02

Sponsor:

SIGARCH

ICS02: International Conference on Supercomputing

June 22 - 26, 2002

New York, New York, USA

Acceptance Rates

ICS '02 Paper Acceptance Rate 31 of 144 submissions, 22%;

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
1,370
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Delgado Díez SCerrada Somolinos CGómez Palomo S(2024)Optimizing Surface Voxelization for Triangular Meshes with Equidistant Scanlines and Gap DetectionComputer Graphics Forum10.1111/cgf.1519543:6Online publication date: 4-Sep-2024
https://doi.org/10.1111/cgf.15195
Song MKim YKim MPark D(2024)Graph-based 3D Collision-distance Estimation Network with Probabilistic Graph Rewiring2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10611465(10939-10945)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10611465
Ghafarian Tamizi MHonari HNozdryn-Plotnicki ANajjaran H(2024)End-to-end deep learning-based framework for path planning and collision checking: bin-picking applicationRobotica10.1017/S0263574724000109(1-19)Online publication date: 13-Feb-2024
https://doi.org/10.1017/S0263574724000109
Gonnermann CKurscheid SSchmucker BDaub R(2024)Simulation-based validation of process monitoring tasks in assemblyProduction Engineering10.1007/s11740-024-01269-zOnline publication date: 11-Mar-2024
https://doi.org/10.1007/s11740-024-01269-z
Das HKumar SKumar S(2022)Precise Parallel FEM-based Interactive Cutting Simulation of Deformable Bodies2022 IEEE 29th International Conference on High Performance Computing, Data, and Analytics (HiPC)10.1109/HiPC56025.2022.00036(198-203)Online publication date: Dec-2022
https://doi.org/10.1109/HiPC56025.2022.00036
Chen XKonobrytskyi DTucker TKurfess TVuduc R(2019)Faster parallel collision detection at high resolution for CNC milling applicationsProceedings of the 48th International Conference on Parallel Processing10.1145/3337821.3337838(1-10)Online publication date: 5-Aug-2019
https://dl.acm.org/doi/10.1145/3337821.3337838
Du PLiu ESuzumura TBargteil AMitchell K(2017)Parallel continuous collision detection for high-performance GPU clusterProceedings of the 21st ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games10.1145/3023368.3023384(1-7)Online publication date: 25-Feb-2017
https://dl.acm.org/doi/10.1145/3023368.3023384
Hwang SKim HJang TYoo JKim SPaeng KKim S(2017)Image-based object reconstruction using run-length representationImage Communication10.1016/j.image.2016.11.00251:C(1-12)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1016/j.image.2016.11.002
Du PZhao JCao WWang Y(2017)DCCD: Distributed N-Body Rigid Continuous Collision Detection for Large-Scale Virtual EnvironmentsArabian Journal for Science and Engineering10.1007/s13369-016-2411-042:8(3141-3147)Online publication date: 28-Jan-2017
https://doi.org/10.1007/s13369-016-2411-0
Nita CStroia IItu LSuciu CMihalef VDatar MRapaka SSharma P(2016)GPU accelerated, robust method for voxelization of solid objects2016 IEEE High Performance Extreme Computing Conference (HPEC)10.1109/HPEC.2016.7761582(1-5)Online publication date: Sep-2016
https://doi.org/10.1109/HPEC.2016.7761582
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents