mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Bounding Volume Hierarchies of Slab Cut Balls
Mälardalen University, School of Innovation, Design and Engineering.ORCID iD: 0000-0002-1550-0994
Lund University.
2009 (English)In: Computer graphics forum (Print), ISSN 0167-7055, E-ISSN 1467-8659, Vol. 28, no 8, p. 2379-2395Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2009. Vol. 28, no 8, p. 2379-2395
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:mdh:diva-9129DOI: 10.1111/j.1467-8659.2009.01548.xISI: 000272569400029Scopus ID: 2-s2.0-72249083065OAI: oai:DiVA.org:mdh-9129DiVA, id: diva2:301702
Available from: 2010-03-03 Created: 2010-03-03 Last updated: 2017-12-12Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Larsson, Thomas

Search in DiVA

By author/editor
Larsson, Thomas
By organisation
School of Innovation, Design and Engineering
In the same journal
Computer graphics forum (Print)
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 63 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf