No Access

COLLISION DETECTION OPTIMIZATION IN A MULTI-PARTICLE SYSTEM

Department of Computer Science, University of Calgary, Calgary, AB, Canada, T2N1N4, Canada

Address for Correspondence: Department of Computer Science, University of Calgary, 2500 University Drive N.W. Calgary AB Canada T2N1N4.

Search for more papers by this author

and

JON ROKNE

Department of Computer Science, University of Calgary, Calgary, AB, Canada, T2N1N4, Canada

Search for more papers by this author

https://doi.org/10.1142/S0218195903001189Cited by:11 (Source: Crossref)

Abstract

Collision detection optimization in an event-driven simulation of a multi-particle system is one of the crucial tasks, determining the efficiency of the simulation. We present the event-driven simulation algorithm that employs dynamic computational geometry data structures as a tool for collision detection optimization (CDO). The first successful application of the dynamic generalized Voronoi diagram method for collision detection optimization in a system of moving particles is discussed. A comprehensive comparision of four kinetic data structures in d-dimensional space, performed in a framework of an event-driven simulation of a granular-type materials system, is supported by the experimental results.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

P. Agarwalet al., Cylindrical static and kinetic binary space partitions, Proceedings of the 13th Annual Symposium on Computational Geometry (1997) pp. 39–48. Google Scholar
Amir-Moez, Khayyam and al-Biruni, Texas J. Science 46(3), 241 (1994). Web of Science, Google Scholar
B. J. Gellatly and J. L. Finney, Journal of Non-Crystal. Solids 50, 313 (1982), DOI: 10.1016/0022-3093(82)90093-X. Crossref, Web of Science, Google Scholar
J. Basch, L. Guibas and L. Zhang, Proximity problems on moving spheres, Proc. of 13th Annual Symposium on Computational Geometry (1997) pp. 344–351. Google Scholar
W. Fisher and E. Koch, Z. Kristallogr. 150, 248 (1979). Google Scholar
D. Gavrilov, O. Vinogradov and W. J. D. Shaw, Powder Technology 101(1), 63 (1999), DOI: 10.1016/S0032-5910(98)00149-1. Crossref, Web of Science, Google Scholar
M. Gavrilova, LNCS 2073 (Springer-Verlag, 2001) pp. 663–672. Google Scholar
M. Gavrilova and J. Rokne, Computer-Aided Geom. Design 6, 89 (1999). Web of Science, Google Scholar
Gavrilova, M. Proximity and Applications in General Metrics, Ph. D. Thesis, The University of Calgary, Dept. of Computer Science, Calgary, AB, Canada (1999) . Google Scholar
M. Gavrilova, J. Rokne and D. Gavrilov, Dynamic collision detection algorithms in computational geometry, 12th European Workshop on CG (1996) pp. 103–106. Google Scholar
L. Guibas and L. Zhang , Euclidean proximity and power diagrams , Proceedngs of the 10th Canadian Conference on Comp. Geometry ( 1998 ) . Google Scholar
L. Guibas , F. Xie and L. Zhang , Kinetic collision detection: algorithms and experiments , Proceedings of the 2001 IEEE Int. Conf. on Robotics and Automation ( 2001 ) . Google Scholar
S. Gottschalk, M. Lin and D. Manocha, OBBtree: A hierarchical data structure for rapid interference detection, Computer Graphics Proc. (1996) pp. 171–180. Google Scholar
M. Held, J. Klosowski and J. Mitchell, Collision detection for fly-throughs in virtual environments, 12th Annual ACM Symp. on Comp. Geometry (1996) pp. V13–V14. Google Scholar
P. Hubbard, ACM Transaction on Graphics 15(3), 179 (1996), DOI: 10.1145/231731.231732. Crossref, Web of Science, Google Scholar
D.-J. Kim, L. Guibas and S.-Y. Shin, IEEE Transactions on Visualization and Computer Graphics 4(3), (1998). Google Scholar
J. T. Klosowskiet al., IEEE Trans. Visualizat. Comput. Graph. 4(1), 21 (1998), DOI: 10.1109/2945.675649. Crossref, Web of Science, Google Scholar
A. Krantz, ACM Transaction on Modeling and Computer Simulation 6(3), 185 (1996), DOI: 10.1145/235025.235030. Crossref, Google Scholar
D. T. Lee , C. D. Yang and C. K. Wong , Rectilinear Paths among Rectilinear Obstacles , ISAAC: 3rd International Symposium on Algorithms and Computation (formerly SIGAL International Symposium on Algorithms) ( 1996 ) . Google Scholar
Medvedev, N. N. Voronoi-Delaunay method for non-crystalline structures, SB Russian Academy of Science, Novosibirsk (2000) . Google Scholar
V. A. Luchnikovet al., Phys. Rev. E 59(6), 7205 (1999), DOI: 10.1103/PhysRevE.59.7205. Crossref, Web of Science, Google Scholar
V. Milenkovic, Position-based physics: Simulating a motion of many highly interactive spheres and polyhedra, Comp. Graph., Ann. Conf. Series (1996) pp. 129–136. Google Scholar
B. Mirtich and J. Canny, Impulse-based simulation of rigid bodies, Symposium on Interactive 3D Graphics (1995) pp. 181–188. Google Scholar
A. Okabe , B. Boots and K. Sugihara , Spatial Tessellations: Concepts and Applications of Voronoi Diagrams ( John Wiley & Sons , England , 1992 ) . Google Scholar
J. Park and D. Fussell, Computers and Graphics 21(4), 483 (1997). Crossref, Web of Science, Google Scholar
T. Roos and H. Noltemeier, Lecture Notes in Control and Information Science 180 (1992) pp. 102–111. Google Scholar
O. Vinogradov, Recent Advances in Structural Mechanics 248, 111 (1992). Google Scholar
E. Wegert, J. of Computational Applied Mathematics 29(3), 311 (1990), DOI: 10.1016/0377-0427(90)90014-Q. Crossref, Web of Science, Google Scholar