1. Parallel BVH Construction Using Locally Density Clustering
- Author
-
Wang Weijian, Yunfei Hu, Dan Li, Yingsong Hu, and Qingzhi Zeng
- Subjects
General Computer Science ,Computer science ,local search ,010103 numerical & computational mathematics ,02 engineering and technology ,Bounding volume hierarchy ,01 natural sciences ,Rendering (computer graphics) ,parallel Construction ,0202 electrical engineering, electronic engineering, information engineering ,General Materials Science ,Local search (optimization) ,Primitive density ,0101 mathematics ,Cluster analysis ,ComputingMethodologies_COMPUTERGRAPHICS ,business.industry ,Heuristic ,General Engineering ,020207 software engineering ,Hierarchical clustering ,Tree traversal ,Morton code ,Ray tracing (graphics) ,lcsh:Electrical engineering. Electronics. Nuclear engineering ,business ,Algorithm ,lcsh:TK1-9971 - Abstract
A novel bounding volume hierarchy (BVH) construction method based on locally dense clustering (LDC) was proposed for the low quality of BVH constructed in a complex scene with uneven distribution of primitives. The quality of the BVH was effectively improved by defining primitive density, analyzing the relation between density and traversal efficiency, selecting primitives with high density as the clustering center at the early stages of construction, and combining with top-down iterative clustering and bottom-up agglomerative clustering (AC). In order to effectively calculate primitive density, a local search strategy based on Morton coding was adopted. This strategy can quickly get approximate primitive density information through GPU. We evaluate the method and show that, in the complex building scene with uneven distribution of primitives, our method is 13% higher in traversal speed and 11% lower in surface area heuristic (SAH) cost. That means our method can improve the rendering speed of ray tracing effectively.
- Published
- 2019