Article | Proceedings of SIGRAD 2016, May 23rd and 24th, Visby, Sweden | Output Sensitive Collision Detection for Unisize Boxes
Göm menyn

Title:
Output Sensitive Collision Detection for Unisize Boxes
Author:
Gabriele Capannini: Mälardalen University, Sweden Thomas Larsson: Mälardalen University, Sweden
Download:
Full text (pdf)
Year:
2016
Conference:
Proceedings of SIGRAD 2016, May 23rd and 24th, Visby, Sweden
Issue:
127
Article no.:
004
Pages:
22-27
No. of pages:
6
Publication type:
Abstract and Fulltext
Published:
2016-05-30
ISBN:
978-91-7685-731-1
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Publisher:
Linköping University Electronic Press, Linköpings universitet


Export in BibTex, RIS or text

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.

Keywords: Collision Detection Simulation Algorithms

Proceedings of SIGRAD 2016, May 23rd and 24th, Visby, Sweden

Author:
Gabriele Capannini, Thomas Larsson
Title:
Output Sensitive Collision Detection for Unisize Boxes
References:

[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

Proceedings of SIGRAD 2016, May 23rd and 24th, Visby, Sweden

Author:
Gabriele Capannini, Thomas Larsson
Title:
Output Sensitive Collision Detection for Unisize Boxes
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment


Responsible for this page: Peter Berkesand
Last updated: 2017-02-21