37-Issue 2

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/2632120

Browse

Browsing 37-Issue 2 by Subject "Collision detection"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Efficient BVH-based Collision Detection Scheme with Ordering and Restructuring
    (The Eurographics Association and John Wiley & Sons Ltd., 2018) Wang, Xinlei; Tang, Min; Manocha, Dinesh; Tong, Ruofeng; Gutierrez, Diego and Sheffer, Alla
    Bounding volume hierarchy (BVH) has been widely adopted as the acceleration structure in broad-phase collision detection. Previous state-of-the-art BVH-based collision detection approaches exploited the spatio-temporal coherence of simulations by maintaining a bounding volume test tree (BVTT) front. A major drawback of these algorithms is that large deformations in the scenes decrease culling efficiency and slow down collision queries. Moreover, for front-based methods, the inefficient caching on GPU caused by the arbitrary layout of BVH and BVTT front nodes becomes a critical performance issue. We present a fast and robust BVH-based collision detection scheme on GPU that addresses the above problems by ordering and restructuring BVHs and BVTT fronts. Our techniques are based on the use of histogram sort and an auxiliary structure BVTT front log, through which we analyze the dynamic status of BVTT front and BVH quality. Our approach efficiently handles inter- and intra-object collisions and performs especially well in simulations where there is considerable spatio-temporal coherence. The benchmark results demonstrate that our approach is significantly faster than the previous BVH-based method, and also outperforms other state-of-the-art spatial subdivision schemes in terms of speed.
  • No Thumbnail Available
    Item
    Fast Penetration Volume for Rigid Bodies
    (The Eurographics Association and John Wiley & Sons Ltd., 2018) Nirel, Dan; Lischinski, Dani; Gutierrez, Diego and Sheffer, Alla
    Handling collisions among a large number of bodies can be a performance bottleneck in video games and many other real-time applications. We present a new framework for detecting and resolving collisions using the penetration volume as an interpenetration measure. Given two non-convex polyhedral bodies, a new sampling paradigm locates their near-contact configurations in advance, and stores associated contact information in a compact database. At runtime, we retrieve a given configuration's nearest neighbors. By taking advantage of the penetration volume's continuity, cheap geometric methods can use the neighbors to estimate contact information as well as a translational gradient. This results in an extremely fast, geometry-independent, and trivially parallelizable computation, which constitutes the first global volume-based collision resolution. When processing multiple collisions simultaneously on a 4-core processor, the average running cost is as low as 5 μs. Furthermore, no additional proximity or contact-regions queries are required. These results are orders of magnitude faster than previous penetration volume approaches.