Build Kd-Tree for Virtual Scenes in a Fast and Optimal Way

GUO Jie; XU Xiao-yang; PAN Jin-gui

您当前的位置：

首页 >

文章列表页 >

Build Kd-Tree for Virtual Scenes in a Fast and Optimal Way

更新时间：2025-07-16

- Build Kd-Tree for Virtual Scenes in a Fast and Optimal Way
- Acta Electronica Sinica Vol. 39, Issue 8, Pages: 1811-1817(2011)
- 作者机构：
  
  南京大学计算机软件新技术国家重点实验室,江苏,南京,210093
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP391
- Published：2011
- 稿件说明：
移动端阅览
GUO Jie, XU Xiao-yang, PAN Jin-gui. Build Kd-Tree for Virtual Scenes in a Fast and Optimal Way[J]. Acta Electronica Sinica, 2011, 39(8): 1811-1817.
DOI：

GUO Jie, XU Xiao-yang, PAN Jin-gui. Build Kd-Tree for Virtual Scenes in a Fast and Optimal Way[J]. Acta Electronica Sinica, 2011, 39(8): 1811-1817. DOI：

摘要

Kd-tree因其具有场景自适应划分、低存储消耗和快速遍历等优势成为使用最为广泛的加速结构.本文提出一种快速优化的kd-tree构造方法

该方法通过分析场景的SAH函数

将模拟退火技术使用到最优分割平面搜索过程中加快搜索过程

从而加速kd-tree的构造过程.实验表明

通过本文的方法可以在保证构造的kd-tree的质量情况下有效加快构造速度.同时

本文实现了该方法的一个多核并行扩展

利用多核CPU的并行处理能力

进一步加快了kd-tree的构造过程.

Abstract

Kd-tree

due to its adaptive division

low memory consumption and fast traversal

has become the most widely used accelerating structure of the virtual scenes.A fast and optimal kd-tree construction method for virtual scenes is proposed in this paper.By analyzing the SAH function of the scene

simulated annealing is used in the optimal split plane search procedure so as to speed up this procedure.In this way

the kd-tree construction is finally accelerated.Experimental results show that the construction of kd-tree is efficiently accelerated with no loss of kd-tree quality.Furthermore

a multi-core parallel computing extension is implemented in this paper

and with the use of multi-core CPU's parallel processing capabilities

the kd-tree construction is further accelerated.

关键词

Keywords

references

Views

1873

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Review on Technology of Placement and Routing for the FPGA

A Salp Swarm Algorithm Based on Stepped Tent Chaos and Simulated Annealing

DReAC:A Novel Dynamically Reconfigurable Co-Processor

Hybrid Artificial Fish Swarm Optimization Algorithm Based on Mutation Operator and Simulated Annealing

Related Author

CHEN Lei

WANG Shuo

ZHOU Jing

ZHANG Yao-wei

PANG Yong-jing

ZHOU Chong

MA Xiao-jing

DU Zhong

Related Institution

Beijing Microelectronics Technology Institute

Department of Micro/nanoelectronics, School of Electronics Engineering and Computer Science, Peking University

Inner Mongolia Electromechanical Control Laboratory

Inner Mongolia University of Technology

北京应用物理与计算数学研究所第一研究室北京

⁰