八叉树

f(x) · 发表于 2009-9-22 21:47:59

本帖最后由 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:22

很好的理论啊。。回头看看能不能放到脚本里去。。谢谢LZ

hadid · 发表于 2009-11-11 22:30:02

为什么没图啊

hadid · 发表于 2009-11-11 22:32:20

应该是很实用的算法，不过还没想好和建筑怎么碰

dizon · 发表于 2009-11-22 15:26:09

提示: 作者被禁止或删除内容自动屏蔽

arkuo · 发表于 2009-11-22 20:52:42

這個理論很有意思可以拿來做碰撞模擬...

onobob · 发表于 2009-11-25 17:07:16

不是很懂哦

hbnx188 · 发表于 2010-2-11 11:30:43

好理论！！

麓山小农 · 发表于 2010-3-22 19:20:35

原来八叉树算是笛卡尔坐标的衍生物数学家太伟大了

ssean · 发表于 2010-3-24 22:13:39

学习了啊啊啊·

zhouningyi1 · 发表于 2010-5-28 23:00:42

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

lucas · 发表于 2010-11-22 16:31:13

········学习中

fxgytulxl · 发表于 2010-12-20 00:35:45

有图有真相

langdezhuren · 发表于 2011-3-12 23:45:25

········学习中

minfish2005 · 发表于 2011-3-14 16:25:52

嗯不错，有点意思

sunjianan · 发表于 2011-3-15 20:20:11

在计算几何中看过、。。。。。。。。

3582076094 · 发表于 2011-4-2 00:18:21

八杈树原来是这么回事啊~

baroque2011 · 发表于 2011-4-3 11:50:05

I LCVE 八叉树。

1236542020 · 发表于 2011-8-15 13:35:23

学习学习……

bensonzz · 发表于 2011-12-1 13:10:28

学习中。。。。

帐号		自动登录	找回密码
密码			注册

dizon dizon 当前离线积分 769 头像被屏蔽	5^m 发表于 2009-11-22 15:26:09 \| 只看该作者提示: 作者被禁止或删除内容自动屏蔽
dizon dizon 当前离线积分 769 头像被屏蔽
	回复支持反对举报

[中文资源] 八叉树

评分