关于三维场景八叉树的初步想法

今天建冰跟我提起了一个很有意思的东西:八叉树

把一个立方体切三刀,横一刀,竖两刀(按坐标轴的方向切),就变成8个边长为一半的立方体。再切一次小立方体,在分成8块。。。
一直往下递归,这就可以使用一个八叉树储存。

八叉树储存的好处:
1.在没有东西的立方体,就不用再往下切,能节省储存空间,运算资源
2.管理方便,搜索某一个小方块的时候,能很方便的使用二分法查找
3.深度到一定层次以后,基本可以拟合所有的三维模型。

对八叉树的使用的初步想法:
        首先,对一个三维游戏的空间来说,z维的使用远比x、y维少。若x、y维使用范围是0-1024,z维用到128就足够了(当然这是在地面游戏的基础上,不包括空战)。
        所以,为了减少八叉树的层次,我们可以对八叉树做一点点扩充:第一层不作为八叉树的分叉储存,储存一个平面。这是一个由立方体拼成的平面。大家可以想象一下平面拼起来的麻将。从第二层开始,就是真正意义上的八叉树,第一层平面上的每一个立方体,都是八叉树的根节点,然后往下细分。假如场景需要为1024*1024*128,这只需要第一层4*4的立方体,然后每个立方体对应7层的八叉树即可。对比起全八叉树,只能形成1024*1024*1024的空间,需要10层的八叉树,节约了3层。

         其次,对于场景里面的物体操作。
         物体可以用一个小八叉树储存(八叉树again),当然这个八叉树的层次会少很多,最多不过5层。在场景中,以某一个元点(譬如八叉树的最左叶节点)作为场景的定位,然后判断与场景相交,只需要一个矩阵的乘法运算即可。效率很高
        
         当然,八叉树的相交会存在一定问题。在我暂时能想到的范围里,由于八叉树的储存不完全是以元点为单位的,会有很多节点没有延伸到最底层(当然这个最底层是必须为定义好的有限层),取相交矩阵的时候,必须把其延伸到最底层,才能取出这个矩阵(或者用一些特殊算法取)。这还是在一个物体的情况下。当有多个物体的时候,两种解决方法:其一,把物体的占用空间存进场景八叉树,这样每个物体的占用空间场景都知道,只要在场景空间里面判断是否有交集即可。其二,以相对坐标的形式,遍历两个物体相交的元点是否有重叠占用。



posted on 2009-05-07 13:51 whitech 阅读(1636) 评论(1)  编辑 收藏 引用

评论

# re: 关于三维场景八叉树的初步想法 2010-01-27 11:36 刘义勤

你可以考虑R树  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年5月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜