NCF参数化建筑论坛

标题: 八叉树 [打印本页]

作者: f(x) 时间: 2009-9-22 21:47
标题: 八叉树
本帖最后由 f(x) 于 2009-11-16 10:16 编辑 Octree（八叉树）的定义是：若不为空树的话，树中任一节点的子节点恰好只会有八个，或零个，也就是子节点不会有0与8以外的数目。那么，这要用来做什么？想象一个立方体，我们最少可以切成多少个相同等分的小立方体？答案就是8个。再想象我们有一个房间，房间里某个角落藏着一枚金币，我们想很快的把金币找出来，聪明的你会怎么做？我们可以把房间当成一个立方体，先切成八个小立方体，然后排除掉没有放任何东西的小立方体，再把有可能藏金币的小立方体继续切八等份….如此下去，平均在Log8(房间内的所有物品数)的时间内就可找到金币。因此，Octree就是用在3D空间中的场景管理，可以很快地知道物体在3D场景中的位置，或侦测与其它物体是否有碰撞以及是否在可视范围内。 2、实现Octree的原理 (1). 设定最大递归深度 (2). 找出场景的最大尺寸，并以此尺寸建立第一个立方体 (3). 依序将单位元元素丢入能被包含且没有子节点的立方体 (4). 若没有达到最大递归深度，就进行细分八等份，再将该立方体所装的单位元元素全部分担给八个子立方体 (5). 若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的，则该子立方体停止细分，因为跟据空间分割理论，细分的空间所得到的分配必定较少，若是一样数目，则再怎么切数目还是一样，会造成无穷切割的情形。 (6). 重复3，直到达到最大递归深度。

作者: ffnforever 时间: 2009-10-19 15:43
很好的理论啊。。回头看看能不能放到脚本里去。。谢谢LZ

作者: hadid 时间: 2009-11-11 22:30
为什么没图啊

作者: hadid 时间: 2009-11-11 22:32
应该是很实用的算法，不过还没想好和建筑怎么碰

作者: dizon 时间: 2009-11-22 15:26
为什么是8啊

作者: arkuo 时间: 2009-11-22 20:52
這個理論很有意思可以拿來做碰撞模擬...

作者: onobob 时间: 2009-11-25 17:07
不是很懂哦

作者: hbnx188 时间: 2010-2-11 11:30
好理论！！

作者: 麓山小农 时间: 2010-3-22 19:20
原来八叉树算是笛卡尔坐标的衍生物数学家太伟大了

作者: ssean 时间: 2010-3-24 22:13
学习了啊啊啊·

作者: zhouningyi1 时间: 2010-5-28 23:00
看了楼主的阐述觉得挺有理 8x树应该是做切掉无用的空间之用吧? 但是不是最有效的持怀疑，因为切分线段最快速的是黄金分割法吧，同理的话切分立方体(三维线段)，也许也是找黄金分割点的

作者: lucas 时间: 2010-11-22 16:31
········学习中

作者: fxgytulxl 时间: 2010-12-20 00:35
有图有真相

作者: langdezhuren 时间: 2011-3-12 23:45
········学习中

作者: minfish2005 时间: 2011-3-14 16:25
嗯不错，有点意思

作者: sunjianan 时间: 2011-3-15 20:20
在计算几何中看过、。。。。。。。。

作者: 3582076094 时间: 2011-4-2 00:18
八杈树原来是这么回事啊~

作者: baroque2011 时间: 2011-4-3 11:50
I LCVE 八叉树。

作者: 1236542020 时间: 2011-8-15 13:35
学习学习……

作者: bensonzz 时间: 2011-12-1 13:10
学习中。。。。

作者: liqianno1 时间: 2012-12-28 18:44
学习了，亲

作者: 燕然居士 时间: 2014-3-10 15:46
太高深了。看不懂。。

欢迎光临 NCF参数化建筑论坛 (http://ncf-china.com/)