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

Weller, René; Klein, Jan; Zachmann, Gabriel

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

Files

011-017.pdf (290.18 KB)

Date

2006

Authors

Weller, René
Klein, Jan
Zachmann, Gabriel

Publisher

The Eurographics Association

Abstract

In 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.

        @inproceedings{:10.2312/EGVE/EGVE06/011-017
,
booktitle = {Eurographics Symposium on Virtual Environments
},
editor = {Ming Lin and Roger Hubbold
},
title = {{A Model for the Expected Running Time of Collision Detection using AABB Trees
}},
author = {Weller, René and 
Klein, Jan and 
Zachmann, Gabriel
},
year = {2006
},
publisher = {The Eurographics Association
},
ISSN = {1727-530X
},
ISBN = {3-905673-33-9
},
DOI = {/10.2312/EGVE/EGVE06/011-017
}
}