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
Adaptive Bounding Volume Hierarchies for Efficient Collision Queries
Mälardalen University, School of Innovation, Design and Engineering.ORCID iD: 0000-0002-1550-0994
2009 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The need for efficient interference detection frequently arises in computer graphics, robotics, virtual prototyping, surgery simulation, computer games, and visualization. To prevent bodies passing directly through each other, the simulation system must be able to track touching or intersecting geometric primitives. In interactive simulations, in which millions of geometric primitives may be involved, highly efficient collision detection algorithms are necessary. For these reasons, new adaptive collision detection algorithms for rigid and different types of deformable polygon meshes are proposed in this thesis. The solutions are based on adaptive bounding volume hierarchies.

For deformable body simulation, different refit and reconstruction schemes to efficiently update the hierarchies as the models deform are presented. These methods permit the models to change their entire shape at every time step of the simulation. The types of deformable models considered are (i) polygon meshes that are deformed by arbitrary vertex repositioning, but with the mesh topology preserved, (ii) models deformed by linear morphing of a fixed number of reference meshes, and (iii) models undergoing completely unstructured relative motion among the geometric primitives. For rigid body simulation, a novel type of bounding volume, the slab cut ball, is introduced, which improves the culling efficiency of the data structure significantly at a low storage cost. Furthermore, a solution for even tighter fitting heterogeneous hierarchies is outlined, including novel intersection tests between spheres and boxes as well as ellipsoids and boxes. The results from the practical experiments indicate that significant speedups can be achieved by using these new methods for collision queries as well as for ray shooting in complex deforming scenes.

 

Place, publisher, year, edition, pages
Västerås: Mälardalen University , 2009. , p. 250
Series
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 71
Keywords [en]
Bounding volume hierarchies, Collision detection, Rigid bodies, Deformable models, Data structures, Simulation, Animation, Three-dimensional graphics and realism
National Category
Computer Sciences
Research subject
Datavetenskap
Identifiers
URN: urn:nbn:se:mdh:diva-4665ISBN: 978-91-86135-18-8 (print)OAI: oai:DiVA.org:mdh-4665DiVA, id: diva2:133780
Public defence
2009-03-05, Alfa, Hus U, Mälardalens högskola, Högskoleplan 1, Västerås, 14:00 (English)
Opponent
Supervisors
Available from: 2009-03-10 Created: 2009-01-14 Last updated: 2018-01-13Bibliographically approved

Open Access in DiVA

fulltext(1748 kB)750 downloads
File information
File name FULLTEXT01.pdfFile size 1748 kBChecksum SHA-512
c9915798c53e7c9bb63c90fd2f95adedc834b89428edc20c066062ce6755c8d177d6db66dab95198d9ef66191e5a20d111b8d65ece0d5df47107fd79f46aee7a
Type fulltextMimetype application/pdf

Authority records BETA

Larsson, Thomas

Search in DiVA

By author/editor
Larsson, Thomas
By organisation
School of Innovation, Design and Engineering
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 750 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 332 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