Orion Sky Lawlor
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.
- 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/Google Scholar
- 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, 2000Google ScholarCross Ref
- 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 Google ScholarDigital Library
- S. Cameron. Approximation hierarchies and s-bounds. In Proceedings of Symposium on Solid Modeling Foundations and CAD/CAM Applications, pages 129--137, 1991 Google ScholarDigital Library
- 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 Google ScholarDigital Library
- R. Farouki, C Neff, and M. O'Connor. Automatic parsing of degnerate quadric-surface intersections. ACM Transactions on Graphics, 8:174--203, 1989 Google ScholarDigital Library
- H. Fuchs, Z. Kedem, and B. Naylor. On visible surface generation by a priori tree structures. Proceedings of ACM Siggraph, pages 124--133, 1980 Google ScholarDigital Library
- V. Gaede and O. Günther. Multidimensional access methods. ACM Computing Surveys, 30(2):170--231, June 1998 Google ScholarDigital Library
- 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, 1988Google ScholarCross Ref
- 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 Google ScholarDigital Library
- Chris Hecker. Let's get to the (floating) point. Game Developer Magazine, Feb/Mar, 1996Google Scholar
- P. Hubbard. Efficient Collision Detection for Animation and Robotics. PhD thesis, Brown University, 1994Google Scholar
- P. Jiménez, F. Thomas, and C. Torras. 3d collision detection: A survey. Computers and Graphics, 25(2):269--285, 2001Google ScholarCross Ref
- 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/Google Scholar
- 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 Google ScholarDigital Library
- 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 Google ScholarDigital Library
- 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, 1996Google Scholar
- 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 Google ScholarDigital Library
- 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/Google Scholar
- 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/ Google ScholarDigital Library
- M. Lin. Efficient Collision Detection for Animation and Robotics. PhD thesis, University of California, Berkeley, 1993 Google ScholarDigital Library
- M. Lin and J. Canny. Efficient algorithms for incremental distance computation. IEEE Conference on Robotics and Automation, pages 1008--1014, 1991Google Scholar
- 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.htmlGoogle Scholar
- S. Suri, P. Hubbard, and J. Hughes. Analyzing bounding boxes for object intersections. ACM Transactions on Graphics, 18 no. 3:257--277, July 1999 Google ScholarDigital Library
- G. Turk. Interactive collision detection for molecular graphics. Master's thesis, University of North Carolina at Chapel Hill, 1989Google Scholar
- 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 Google ScholarDigital Library
- 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, 1993Google Scholar
Index Terms
- A voxel-based parallel collision detection algorithm
Recommendations
A Real-time Robot Arm Collision Detection Algorithm
MACE '12: Proceedings of the 2012 Third International Conference on Mechanic Automation and Control EngineeringCollision 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 9246As 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 IRapid 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