热门问题
时间线
聊天
视角

八叉树

来自维基百科,自由的百科全书

八叉树
Remove ads

八叉树(英語:Octree)是一种树形数据结构,每个内部节点都正好有八个子节点。八叉树常用于分割三维空间,将其递归细分为八个卦限。八叉树是四叉树在三维空间中的对应,在三维图形、三维游戏引擎等领域有很多应用。

事实速览 八叉树, 类型 ...
Thumb
左:遞迴子切分一個立方體為多個卦限。右:對應的八叉樹

表示空间

八叉树的每个节点都可以代表一个空间,对应的八个子节点则将这个空间细分为八个卦限。点域(point region,简称PR)八叉树的节点中都存储着一个三维,即该节点对应区域的「中心」,也是八个子节点对应区域中的一个角落。矩阵(matrix based,简称MX)八叉树中,节点只记录区域范围,对应的中心点坐标需要从区域范围推算。因此,PR八叉树的根节点可以表示无限大的空间;而MX八叉树的根节点只能表示有限空间,这样才可以得到隐含的中心点。

历史

八叉树在三维计算机图形领域的应用可以追溯到1980年伦斯勒理工学院唐纳德·马尔(Donald Meagher)的报告《八叉树编码:使用计算机表示、操作、显示任意三维对象的新技术》(Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer[1]

主要用途

另见

参考资料

外部連結

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads