基于局部密度聚类的包围体层次结构构建方法研究

发布时间：2021-08-30 18:49

　　随着计算机图形学与计算机硬件的飞速发展,基于间接光照渲染出的图像无法满足人们对真实感图片的追求,对基于全局光照的光线追踪的实时性要求越来越高。包围体层次结构是光线追踪中加速结构的一个重要研究方向,借助包围体层次结构能够有效减少光线求交时间,提高渲染速度。针对传统的包围体层次结构构建速度慢、质量低的问题,提出了一种基于局部密度聚类的包围体层次结构构建方法,该方法分为片元局部密度计算、横向迭代聚类和纵向优化三个步骤。片元密度计算过程中,利用莫顿码对场景片元进行空间排序,使用局部搜索策略近似计算得到片元密度;在横向迭代聚类的初次聚类过程中,选取密度大的片元作为聚类中心,通过聚类的方式在包围体层次结构的高层对独立分散的场景对象进行分割,尽可能减少高层包围盒之间的重叠区域,提高遍历效率,之后通过中间迭代聚类步骤构建出K叉结构树;在纵向优化部分,利用自底向上的凝聚聚类方法结合表面积启发式代价函数进一步优化质量,构造出K叉树的中间节点,得到最终的包围体层次结构。实验结果显示,基于局部密度聚类构建的包围体层次结构在保证构建速度的同时,提高了构建质量。在遍历速度上较已有方法提升了8%,重叠度降低11%,... 

【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校

【文章页数】：61 页

【学位级别】：硕士

【部分图文】：

真实感图片

13(a) Sponza 262K (b) Sibenik 752K (c) Fairy Forest 174K图 2.3 三种不同复杂度的片元密度图密度图中深色部分表示这片区域内的片元密度相对较小；亮色的部分则表示该区域片元密度相对较大。从图中可以看出建筑物场景中的大片元瓦片区域密度较小，而(a)中的花坛，(b)中的栏杆，(c)中的草丛片元密度较大，这些对象同时在场景中分布较为独立分散。综合 2.1 节所述，应当在 BVH 构建的上层就将这些区域从场景中分割开。本文使用基于片元密度聚类的BVH构建方法，该方法能够结合几何片元的密度分布信息，避免选取密度较小的片元作为聚类初始种子点，将聚类中心定位至片元紧密的模型中，通过聚类的方式在包围体层次结构的高层便将分散的场景对象分割，可以有效提高 BVH 质量。该方法首先需要计算场景中所有片元的密度，并从中选取密度最大的K 个候选片元作为初始聚类中心。

略需要使用局部密度来近似代替密度，为此过定义局部搜索半径 r，在上一节得到空间算片元的局部密度，同时该方法适合在 Gorton 码空间排序后的片元集合 C: 的片元，场景中的三角片元总量为 n，并且 ( ) ( ) 的 Morton 码。对于索引为 i 的片元 ，在半径，搜索滑动窗口大小为 2r，即在（ 如图 2.6 所示。

【参考文献】：
期刊论文
[1]基于动态任务调度的层次包围盒构建算法[J]. 张正昌,何发智,周毅.  计算机辅助设计与图形学学报. 2018(03)

博士论文
[1]面向高性能图形绘制的加速结构设计[D]. 杨鑫.浙江大学 2012



本文编号：3373310