Chunked Bounding Volume Hierarchies for fast digital prototyping using volumetric meshes

Research output: Contribution to journalJournal articlepeer-review

Standard

Chunked Bounding Volume Hierarchies for fast digital prototyping using volumetric meshes. / Schmidtke, Robert; Erleben, Kenny.

In: IEEE Transactions on Visualization and Computer Graphics, Vol. 24, No. 12, 2018, p. 3044-3057.

Research output: Contribution to journalJournal articlepeer-review

Harvard

Schmidtke, R & Erleben, K 2018, 'Chunked Bounding Volume Hierarchies for fast digital prototyping using volumetric meshes', IEEE Transactions on Visualization and Computer Graphics, vol. 24, no. 12, pp. 3044-3057. https://doi.org/10.1109/TVCG.2017.2784441

APA

Schmidtke, R., & Erleben, K. (2018). Chunked Bounding Volume Hierarchies for fast digital prototyping using volumetric meshes. IEEE Transactions on Visualization and Computer Graphics, 24(12), 3044-3057. https://doi.org/10.1109/TVCG.2017.2784441

Vancouver

Schmidtke R, Erleben K. Chunked Bounding Volume Hierarchies for fast digital prototyping using volumetric meshes. IEEE Transactions on Visualization and Computer Graphics. 2018;24(12):3044-3057. https://doi.org/10.1109/TVCG.2017.2784441

Author

Schmidtke, Robert ; Erleben, Kenny. / Chunked Bounding Volume Hierarchies for fast digital prototyping using volumetric meshes. In: IEEE Transactions on Visualization and Computer Graphics. 2018 ; Vol. 24, No. 12. pp. 3044-3057.

Bibtex

@article{258cb37eec4f4bd18e8b03b6bedf6b35,
title = "Chunked Bounding Volume Hierarchies for fast digital prototyping using volumetric meshes",
abstract = "We present a novel approach to using Bounding Volume Hierarchies (BVHs) for collision detection of volumetric meshes for digital prototyping based on accurate simulation. In general, volumetric meshes contain more primitives than surface meshes, which in turn means larger BVHs. To manage these larger BVHs, we propose an algorithm for splitting meshes into smaller chunks with a limited-size BVH each. Limited-height BVHs make guided, all-pairs testing of two chunked meshes well-suited for GPU implementation. This is because the dynamically generated work during BVH traversal becomes bounded. Chunking is simple to implement compared to dynamic load balancing methods and can result in an overall two orders of magnitude speedup on GPUs. This indicates that dynamic load balancing may not be a well suited scheme for the GPU. The overall application timings showed that data transfers were not the bottleneck. Instead, the conversion to and from OpenCL friendly data structures was causing serious performance impediments. Still, a simple OpenMP acceleration of the conversion allowed the GPU solution to beat the CPU solution by 20 percent. We demonstrate our results using rigid and deformable body scenes of varying complexities on a variety of GPUs.",
keywords = "Collision detection, bounding volume hierarchies, parallel tandem traversal, scheduling algorithm",
author = "Robert Schmidtke and Kenny Erleben",
year = "2018",
doi = "10.1109/TVCG.2017.2784441",
language = "English",
volume = "24",
pages = "3044--3057",
journal = "I E E E Transactions on Visualization and Computer Graphics",
issn = "1077-2626",
publisher = "Institute of Electrical and Electronics Engineers",
number = "12",

}

RIS

TY - JOUR

T1 - Chunked Bounding Volume Hierarchies for fast digital prototyping using volumetric meshes

AU - Schmidtke, Robert

AU - Erleben, Kenny

PY - 2018

Y1 - 2018

N2 - We present a novel approach to using Bounding Volume Hierarchies (BVHs) for collision detection of volumetric meshes for digital prototyping based on accurate simulation. In general, volumetric meshes contain more primitives than surface meshes, which in turn means larger BVHs. To manage these larger BVHs, we propose an algorithm for splitting meshes into smaller chunks with a limited-size BVH each. Limited-height BVHs make guided, all-pairs testing of two chunked meshes well-suited for GPU implementation. This is because the dynamically generated work during BVH traversal becomes bounded. Chunking is simple to implement compared to dynamic load balancing methods and can result in an overall two orders of magnitude speedup on GPUs. This indicates that dynamic load balancing may not be a well suited scheme for the GPU. The overall application timings showed that data transfers were not the bottleneck. Instead, the conversion to and from OpenCL friendly data structures was causing serious performance impediments. Still, a simple OpenMP acceleration of the conversion allowed the GPU solution to beat the CPU solution by 20 percent. We demonstrate our results using rigid and deformable body scenes of varying complexities on a variety of GPUs.

AB - We present a novel approach to using Bounding Volume Hierarchies (BVHs) for collision detection of volumetric meshes for digital prototyping based on accurate simulation. In general, volumetric meshes contain more primitives than surface meshes, which in turn means larger BVHs. To manage these larger BVHs, we propose an algorithm for splitting meshes into smaller chunks with a limited-size BVH each. Limited-height BVHs make guided, all-pairs testing of two chunked meshes well-suited for GPU implementation. This is because the dynamically generated work during BVH traversal becomes bounded. Chunking is simple to implement compared to dynamic load balancing methods and can result in an overall two orders of magnitude speedup on GPUs. This indicates that dynamic load balancing may not be a well suited scheme for the GPU. The overall application timings showed that data transfers were not the bottleneck. Instead, the conversion to and from OpenCL friendly data structures was causing serious performance impediments. Still, a simple OpenMP acceleration of the conversion allowed the GPU solution to beat the CPU solution by 20 percent. We demonstrate our results using rigid and deformable body scenes of varying complexities on a variety of GPUs.

KW - Collision detection

KW - bounding volume hierarchies

KW - parallel tandem traversal

KW - scheduling algorithm

UR - http://www.scopus.com/inward/record.url?scp=85039761803&partnerID=8YFLogxK

U2 - 10.1109/TVCG.2017.2784441

DO - 10.1109/TVCG.2017.2784441

M3 - Journal article

C2 - 29990042

VL - 24

SP - 3044

EP - 3057

JO - I E E E Transactions on Visualization and Computer Graphics

JF - I E E E Transactions on Visualization and Computer Graphics

SN - 1077-2626

IS - 12

ER -

ID: 187584983