A Model for the Expected Running Time of Collision Detection using AABB Trees

Simple item page
dc.contributor.authorWeller, Renéen_US
dc.contributor.authorKlein, Janen_US
dc.contributor.authorZachmann, Gabrielen_US
dc.contributor.editorMing Lin and Roger Hubbolden_US
dc.date.accessioned2014-01-27T10:47:21Z
dc.date.available2014-01-27T10:47:21Z
dc.date.issued2006en_US
dc.description.abstractIn this paper, we propose a model to estimate the expected running time of hierarchical collision detection that utilizes AABB trees, which are a frequently used type of bounding volume (BV). We show that the average running time for the simultaneous traversal of two binary AABB trees depends on two characteristic parameters: the overlap of the root BVs and the BV diminishing factor within the hierarchies. With this model, we show that the average running time is in O(n) or even in O(logn) for realistic cases. Finally, we present some experiments that confirm our theoretical considerations. We believe that our results are interesting not only from a theoretical point of view, but also for practical applications, e. g., in time-critical collision detection scenarios where our running time prediction could help to make the best use of CPU time available.en_US
dc.description.seriesinformationEurographics Symposium on Virtual Environmentsen_US
dc.identifier.isbn3-905673-33-9en_US
dc.identifier.issn1727-530Xen_US
dc.identifier.urihttps://doi.org/10.2312/EGVE/EGVE06/011-017en_US
dc.publisherThe Eurographics Associationen_US
dc.titleA Model for the Expected Running Time of Collision Detection using AABB Treesen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
011-017.pdf
Size:
290.18 KB
Format:
Adobe Portable Document Format
Download
Collections
EGVE06: 12th Eurographics Symposium on Virtual Environments