sphere trees for speedy BSPs--game programming gems5

2012/03/09 14:09
阅读数 55

BSP虽然在现代游戏开发中出场机会越来越少,但是在visibility preprocessing, collision detection, polygon sorting中仍旧有良好的应用;

bsp把场景用多个splitter划分为多个区域,并存在树结构中,它有两个重要标准:

1,划分粒度:最好能够划分到polygon级别--精确剔除;

2,平衡数:splitter划分出来的树左右尽可能平衡--搜索时间最小且稳定;

bsp牛x之处在于其明确的划分机制和树状存储方式。

这篇文章中所要优化的就是其构建过程,使用bounding volume tree来使得划分过程变得更加迅速;

bounding volume tree以树的层次方式,以bounding volume为标准来组织场景,这样可以在合适的粒度上对model进行判别操作;

比如在构造bsp的时候,可以判别一个bounding sphere在splitter前边,那么可知其中所有polygon都在前边,如果相交,就顺着bouding sphere tree继续向下找;

听起来很想二分搜索,当然它们是一个东西,树状结构都会带来这种优势--树枝剔除带来的加速和编码便利;

树真的是牛x的数据结构,it's great;


原文链接: http://blog.csdn.net/ccanan/article/details/1566355
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部