Parallel BVH construction using k-means clustering

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00300076" target="_blank" >RIV/68407700:21230/16:00300076 - isvavai.cz</a>

Result on the web

<a href="http://link.springer.com/article/10.1007/s00371-016-1241-0" target="_blank" >http://link.springer.com/article/10.1007/s00371-016-1241-0</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00371-016-1241-0" target="_blank" >10.1007/s00371-016-1241-0</a>

Result language

angličtina

Original language name

Parallel BVH construction using k-means clustering

Original language description

We propose a novel method for fast parallel construction of bounding volume hierarchies (BVH) on the GPU. Our method is based on a combination of divisible and agglomerative clustering. We use the k-means algorithm to subdivide scene primitives into clusters. From these clusters, we construct treelets using the agglomerative clustering algorithm. Applying this procedure recursively, we construct the entire bounding volume hierarchy. We implemented the method using parallel programming concepts on the GPU. The results show the versatility of the method: it can be used to construct medium-quality hierarchies very quickly, but also it can be used to construct high-quality hierarchies given a slightly longer computational time. We evaluate the method in the context of GPU ray tracing and show that it provides results comparable with other state-of-the-art GPU techniques for BVH construction. We also believe that our approach based on the k-means algorithm gives a new insight into how bounding volume hierarchies can be constructed.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/GAP202%2F12%2F2413" target="_blank" >GAP202/12/2413: Optimal Algorithms for Image Synthesis</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2016

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

The Visual Computer

ISSN

0178-2789

e-ISSN

—

Volume of the periodical

32

Issue of the periodical within the volume

6

Country of publishing house

DE - GERMANY

Number of pages

11

Pages from-to

977-987

UT code for WoS article

000378731600029

EID of the result in the Scopus database

2-s2.0-84966430759