Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Bounding Volume Hierarchies of Slab Cut Balls

In English

Författare

Summary, in English

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.

Publiceringsår

2009

Språk

Engelska

Sidor

2379-2395

Publikation/Tidskrift/Serie

Computer Graphics Forum

Volym

28

Issue

8

Dokumenttyp

Artikel i tidskrift

Förlag

Wiley-Blackwell

Ämne

  • Computer Science

Nyckelord

  • animation
  • rigid body simulation
  • collision detection
  • bounding volumes
  • hierarchical data structures

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 1467-8659