欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

空间八叉树剖分

发布时间:2024/5/15 编程问答 4 豆豆
如意编程网 收集整理的这篇文章主要介绍了 空间八叉树剖分 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

空间八叉树剖分

转载自:http://hi.baidu.com/j_factory/blog/item/8bc1ca182d7f45f6af5133c3.html

 

空间八叉树算法是一个空间非均匀网格剖分算法,该算法将含有整个场景的空间立方体按三个方向分割成八个子立方体网格,组织成一棵八叉树。若某 一子立方体网格中所含景物面片数大于给定的阈值,则为该子立方体作进一步的剖分。上述剖分过程直至八叉树每一个叶子节点所含面片数均小于给定的阈值为止。 这个算法也是利用了空间连贯性。

    八叉树的最大深度表示空间分割所达到的层次,称为空间分辨率,而八叉树的终结节点对应分割后的空间网格单元。设八叉树的深度为N,任 一个八叉树终结节点的编码为

 

 

 

    由上述八叉树结点的编码方式很容易找到空间任一点所在的空间网格单元。设P(x,y,z) 为一空间点,x,y,z取整数,其相应的二进制表

 

1  P所在单位立方体网格编码为q1q2...qN

 

面上),则该空间网格的前左下角坐标为

 

 

    上述性质在下面介绍的光线跟踪八叉树算法中起了很重要的作用。

 

    下面来看如何进行光线跟踪。设光线起始点为P0,方向为R,先求P0所在单位立方体网格的八叉树编码Q。这 只需先对P0各坐标分量取整得到单位立方体网格的前左下 角坐标P,然后即可用式(5)计算编码Q。若计算出的P点位于 世界立方体的边界上,则需根据光线前进方向判别光线是否已射出场景。若光线已射出场景,则算法结束。否则,在空间线性八叉树结点表中查找Q。查 找的结果用两个量表示。一个是表明查找是否成功的布尔量T,另一是未获匹时,T取真值。这是因为该结点对应的空间网格包含了P0所在的最小网格单元。注意这一结点为非空的终结点,它表明P0点位于一含有三角形面片且边长为2N-i的空间网格内部或边界上。未获匹配位数B定义为八叉树终结点表中与Q获得 最大程度匹配结点,其编码尾部不匹配的位数。若该结点的编码为 通过QB则可确定当前立方体的空间位置和大小。对线性八叉树采用二分查找可以加快查询速度。

http://blog.csdn.net/wsh6759/article/details/7424993

总结

以上是如意编程网为你收集整理的空间八叉树剖分的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。