空间划分技术对比简表

典型空间划分结构技术比较

Comparison of spatial data structure

名称 适用情况 空间需求 时间需求 能够满足动态场景多的三维系统 优点 缺点
BVH 所有场景 在进行视锥裁剪以及光线相交测试的时候,可以简化操作,父节点不可见或者不相交,就可以抛弃剩下的子节点。在物体移动时,简单检查物体是否还在父节点内就可以判断是否需要更新整个BVH。 如果确定父节点需要进行光线相交测试或者可见性测试,就必须遍历所有的节点。随着动态物体的移动,整棵BVH树会越来越不平衡,性能会有所下降。
BSP 大规模数据的复杂室内场景 能够了解场景中物体渲染的前后排序情况。在进行遮挡剔除和光线跟踪 以及透明物体绘制的时候有着很大的优势。 需要更多的空间用于存储分割平面的相关信息。
Octree 大规模资料的广阔室外场景 八叉树算法的算法实现简单,遍历过程十分的方便,并且占用的存储空间较小。即效率较高。 划分最小粒度较难确定,粒度过大,有些叶子结点的数据量可能较大,粒度过小,八叉树深度过深。并且存储空间的冗余较多。动态场景中对树结构修改的开销较大。
Quadtree 大规模资料的广阔室外场景,主要针对地形 算法简单易于实现,查询效率非常高。 随着地理空间对象的不断插入,四叉树的层次会不断地加深,将形成一棵严重不平衡的四叉树,那么每次查询的深度将大大的增多,从而导致查询效率的急剧下降。

发表评论

电子邮件地址不会被公开。 必填项已用*标注