Parallel SAH Based KD Tree Construction Algorithm

Cheng Ma

doi:10.4028/www.scientific.net/AMR.433-440.3543

Paper Titles

User-Defined Report Design and Implementation
p.3521

A Spread-Out Design for Dual-Band GPS Microstrip Antenna
p.3525

Design of Control System for Pavement Accelerated Loading Testing Equipment Based on Bus Technology
p.3531

The Application of Fuzzy C Mean Clustering Algorithm on Image Processing Based on .NET Component
p.3536

Parallel SAH Based KD Tree Construction Algorithm
p.3543

Research of E-Commerce Security Technology
p.3548

Research on the Switch Scheduling Algorithm of Networked Control System
p.3553

Application Study of Symbolism
p.3560

Segmenting Lung Fields in CT Image Using Legendre Moments and Active Contour
p.3564

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 433-440Parallel SAH Based KD Tree Construction Algorithm

Parallel SAH Based KD Tree Construction Algorithm

Abstract:

The best method to construct a high quality KD tree is by using Surface Area Heuristic[1][4] (SAH). However, the computation involved in SAH is expensive. Wald and Havran[2] introduced a sequential algorithm of O(NlogN) complexity, which reached the lower bound of constructing a binary tree. In this paper, we will introduce a parallel SAH KD tree construction algorithm based on the O(NlogN) sequential algorithm. We proposed data structure for parallel constructing process which can minimize the communication among working threads, and a load balance strategy for evenly distributing work load. Our algorithm can achieve 4x speed up on 8-core CPUs architecture.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 433-440)

Pages:

3543-3547

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.433-440.3543

Citation:

Cite this paper

Online since:

January 2012

Authors:

Cheng Ma

Keywords:

Graphic Processing Unit (GPU), KD Tree, Multi-Core, Parallel, SAH

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] J. D. MacDonald and K. S. Booth. Heuristics for ray tracing using space subdivision. In Graphics Interface Proceedings 1989, pages 152-163, Wellesley, MA, USA, June 1989. A.K. Peters, Ltd.

Google Scholar

[2] I. Wald and V. Havran. On building fast kd-trees for ray tracing, and on doing that in o(nlogn). In Proc. IEEE Symp. Interactive Ray Tracing, pages 61-69, (2006).

DOI: 10.1109/rt.2006.280216

Google Scholar

[3] Vlastimil Havran. Heuristic Ray Shooting Algorithms. Ph.D. Thesis. Department of Computer Science and Engineering Faculty of Electrical Engineering, Czech Technical University in Prague, November (2000).

Google Scholar

[4] J. D. MacDonald and K. S. Booth. Heuristics for ray tracing using space subdivision. Visual Computer, 6(6): 153–65, (1990).

DOI: 10.1007/bf01911006

Google Scholar

[5] Stefan Popov, Johannes Günther, Hans-Peter Seidel and Philipp Slusallek. Experiences with Streaming Construction of SAH KD-Trees. Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing, pages 89-94. (2006).

DOI: 10.1109/rt.2006.280219

Google Scholar