Advanced

Bounding Volume Hierarchies of Slab Cut Balls

Larsson, T. and Akenine-Möller, Tomas LU (2009) In Computer Graphics Forum 28(8). p.2379-2395
Abstract
We introduce a bounding volume hierarchy based on the Slab Cut Ball. This novel type of enclosing shape provides an attractive balance between tightness of fit, cost of overlap testing, and memory requirement. The hierarchy construction algorithm includes a new method for the construction of tight bounding volumes in worst case O(n) time, which means our tree data structure is constructed in O(n log n) time using traditional top-down building methods. A fast overlap test method between two slab cut balls is also proposed, requiring as few as 28-99 arithmetic operations, including the transformation cost. Practical collision detection experiments confirm that our tree data structure is amenable for high performance collision queries. In all... (More)
We introduce a bounding volume hierarchy based on the Slab Cut Ball. This novel type of enclosing shape provides an attractive balance between tightness of fit, cost of overlap testing, and memory requirement. The hierarchy construction algorithm includes a new method for the construction of tight bounding volumes in worst case O(n) time, which means our tree data structure is constructed in O(n log n) time using traditional top-down building methods. A fast overlap test method between two slab cut balls is also proposed, requiring as few as 28-99 arithmetic operations, including the transformation cost. Practical collision detection experiments confirm that our tree data structure is amenable for high performance collision queries. In all the tested benchmarks, our bounding volume hierarchy consistently gives performance improvements over the sphere tree, and it is also faster than the OBB tree in five out of six scenes. In particular, our method is asymptotically faster than the sphere tree, and it also outperforms the OBB tree, in close proximity situations. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
animation, rigid body simulation, collision detection, bounding volumes, hierarchical data structures
in
Computer Graphics Forum
volume
28
issue
8
pages
2379 - 2395
publisher
Wiley-Blackwell
external identifiers
  • wos:000272569400029
  • scopus:72249083065
ISSN
1467-8659
DOI
10.1111/j.1467-8659.2009.01548.x
language
English
LU publication?
yes
id
443ace29-07b4-40ce-bfe1-fea89a7c55bd (old id 1532735)
date added to LUP
2010-01-28 17:10:43
date last changed
2017-01-01 04:26:58
@article{443ace29-07b4-40ce-bfe1-fea89a7c55bd,
  abstract     = {We introduce a bounding volume hierarchy based on the Slab Cut Ball. This novel type of enclosing shape provides an attractive balance between tightness of fit, cost of overlap testing, and memory requirement. The hierarchy construction algorithm includes a new method for the construction of tight bounding volumes in worst case O(n) time, which means our tree data structure is constructed in O(n log n) time using traditional top-down building methods. A fast overlap test method between two slab cut balls is also proposed, requiring as few as 28-99 arithmetic operations, including the transformation cost. Practical collision detection experiments confirm that our tree data structure is amenable for high performance collision queries. In all the tested benchmarks, our bounding volume hierarchy consistently gives performance improvements over the sphere tree, and it is also faster than the OBB tree in five out of six scenes. In particular, our method is asymptotically faster than the sphere tree, and it also outperforms the OBB tree, in close proximity situations.},
  author       = {Larsson, T. and Akenine-Möller, Tomas},
  issn         = {1467-8659},
  keyword      = {animation,rigid body simulation,collision detection,bounding volumes,hierarchical data structures},
  language     = {eng},
  number       = {8},
  pages        = {2379--2395},
  publisher    = {Wiley-Blackwell},
  series       = {Computer Graphics Forum},
  title        = {Bounding Volume Hierarchies of Slab Cut Balls},
  url          = {http://dx.doi.org/10.1111/j.1467-8659.2009.01548.x},
  volume       = {28},
  year         = {2009},
}