Published: 2016-05-30
ISBN: 978-91-7685-731-1
ISSN: 1650-3686 (print), 1650-3740 (online)
We show how a recent collision detection method, which is based on the familiar sweep and prune concept, can gain further performance for the special class of simulations that only involves axis-aligned bounding boxes of the same size. The proposed modifications lead to a worst-case optimal output-sensitive algorithm in 2D. Furthermore, the experimental result shows that our method gives generous speedups in practice and that dynamic scenes with one million objects can be processed at interactive rates even on a laptop.
[AGN*04] AGARWAL P., GUIBAS L., NGUYEN A., RUSSEL D., ZHANG L.: Collision detection for deforming necklaces. Computational Geometry: Theory and Applications 28, 2-3 (2004), 137–163. 5
[Bar92] BARAFF D.: Dynamic Simulation of Non-Penetrating Rigid Bodies. PhD thesis, Cornell University, 1992. 1, 2, 3
[CL16] CAPANNINI G., LARSSON T.: Efficient collision culling by a succinct bi-dimensional sweep and prune algorithm. In Proceedings of the 32nd Spring Conference on Computer Graphics (SCCG) (2016). 1, 2, 3, 4
[CLMP95] COHEN J. D., LIN M. C., MANOCHA D., PONAMGI M.: I-Collide: An interactive and exact collision detection system for large-scale environments. In Proceedings of the 1995 Symposium on Interactive 3D Graphics (1995), pp. 189–196. 1
[CR72] COOK S. A., RECKHOW R. A.: Time-bounded random access machines. In Proceedings of the fourth annual ACM symposium on Theory of computing (1972), pp. 73–80. 3
[CS06] COMING D. S., STAADT O. G.: Kinetic sweep and prune for multi-body continuous motion. Computers & Graphics 30, 3 (2006), 439–449. 2
[Eri04] ERICSON C.: Real-Time Collision Detection. Morgan Kaufmann, 2004. 1
[FLPR99] FRIGO M., LEISERSON C. E., PROKOP H., RAMACHANDRAN S.: Cache-oblivious algorithms. In 40th Annual Symposium on Foundations of Computer Science (1999), pp. 285–297. 4
[KMZ13] KETTNER L., MEYER A., ZOMORODIAN A.: Intersecting Sequences of dD Iso-oriented Boxes, 4.2 ed. CGal Editorial Board, 2013. 3
[Knu98] KNUTH D. E.: The art of computer programming, volume 3: sorting and searching (2nd Edition). Addison-Wesley, 1998. 2
[LHLK10] LIU F., HARADA T., LEE Y., KIM Y. J.: Real-time collision culling of a million bodies on graphics processing units. ACM Transactions on Graphics 29, 6 (2010), 154:1–154:8. 1, 2
[LM13] LI B., MUKUNDAN R.: A comparative analysis of spatial partitioning methods for large-scale, real-time crowd simulation. In 21st International Conference on Computer Graphics, Visualization and Computer Vision (2013), pp. 104–111. 5
[Ram10] RAMAN T. R. S.: Photograph of wildebeest herding and following a few leading zebra in the Masai Mara Kenya, 2010. CC BY 3.0 (http://creativecommons.org/licenses/by/3.0), via Wikimedia Commons. 5
[Sam05] SAMET H.: Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann, 2005. 1
[TBW09] TRACY D. J., BUSS S. R., WOODS B. M.: Efficient large-scale sweep and prune methods with AABB insertion and removal. In Proceedings of the IEEE Virtual Reality Conference (2009), pp. 191–198. 1, 2
[TKH*05] TESCHNER M., KIMMERLE S., HEIDELBERGER B., ZACHMANN G., RAGHUPATHI L., FUHRMANN A., CANI M.-
P., FAURE F., MAGNENAT-THALMANN N., STRASSER W., VOLINO P.: Collision detection for deformable objects. Computer Graphics Forum 24, 1 (2005), 61–81. 1
[Wel13] WELLER R.: New Geometric Data Structures for Collision Detection and Haptics. Springer, 2013. 1
