| 订阅 | 在线投稿
分享
 
 
 

详细介绍四叉树Quadtrees(上)

来源:互联网  宽屏版  评论
2008-05-19 00:44:09

原理:什么是Quadtrees?

由于3D图形卡消费市场的变革,现在3D游戏越来越流行了,他们中大部分是第一人称射击游戏,这 是一个很好的理由,这个理由是室内环境,当和室外环境相比它非常简单。对于室外环境,它没有方便 的通往下一关的楼梯,门,或墙来阻挡你的视线。室外环境都是连续的。对于传统的几何学来说这是非 常棘手的,请打入quadtrees来学习下面的知识。

注意:下面的图示都是从上到下看一个3D地形,方格显示了在X和Y轴上的地形,并看不见现 实中的物体高度,因为我们是顺着Y轴看的。

Figure 1

设想你的地形是一个非常大的方格,在一个X和Z的面上扩展,如图1。我们有一个摄象机在地形的右 下角,它的可视截面(蓝三角)扩展为在相同方向上的小单元,这样在优化前,绘制地形的程序代码看 起来象这样:

for(int ctr=0; ctr

{

DrawCell();

}

注意:一个小单元就是一个包含一些三角形的正方形,它是地形的一部分),看起来非常好,但是本 来我们只是占用了16个单元,可是画了256个。这是非常大的浪费,在我们的可视截面里只有5个单元。 现在第一个优化:我们要测试所有的单元是否在可视截面里,如果在就画他,现在的代码如下:

for(int ctr=0; ctr

{

if(cell is in frustum) DrawCell();

}

如果单元在我们的可视截面中,就画他,非常正确。现在我们只画了5个单元,而不是256个,我们只 是更改很少的代码。在上面,我们保存了我们没有绘出的251个单元,每次都是,这是非常的浪费,如下图:

Figure 2

我将一些单元变成了兰色,这样我们可以建立一个包围盒,如果兰色的单元不在截面内,我们可以安全 的说这个单元在区域A中,如果我们知道兰色的单元不在截面内,我们如何去测试区域A中的其他144个单元 呢,这由quadtrees 来工作

quadtrees 是从地形中获得的,把它分割成四个较小的部分,每一个部分继续分下去,直到一个分到 一个设定的大小,这看起来有点乱,让我结合图片解释一下,首先,从我们的网格出发,现在将他分为四份。

Figure 3

如图三,我们现在有四个子地形,继续分下去,知道一个部分只有一个单元,,在下图中,我们把第一个 小部分分成了四个更小的部分。

Figure 4

然后继续:

Figure 5

然后继续:

Figure 6

好了,现在第一个部件只有一个单元大小,我们告诉树停止分割第一个部件,分割下一个,直到 全部分割完毕。当然你也可以将树分割到合适的三角形数目停止,在我们的例子中为16个三角形,第 一,这个树是父子关系,每个子节点有一个父节点,每个父节点有四个子节点,叶节点例外,他只有 一个父节点没有子节点。叶节点是我们允许的最小的子节点,第二,每个树都有一个根节点,它没有 父节点,但有四个子节点。

再看一下图,暗红的边界就是根节点,在图3中,我们分割根节点,分配给他的子节点。蓝线描绘 的正方形是根节点的四个子。称为节点2,3,4,5。在图4 ,我们把节点2分为四份,这些正方形是 节点的子,称为节点6,7,8,9。继续由节点6分割出10,11,12,13,由节点10分割为14,15, 16,17。这是他们的叶节点。停止分割。分割节点11,分完后是12和13,然后是7,8,和9。然后是 3,4,5。完成。

quadtrees 使用一个节点的包围坐标工作,我们说我们的图形0-16在X轴上,0-16在Z轴上。由于 这个原因,我们整个地图的包围坐标为左上为(0,0,0)右上(16,0,0)左下(0,0,16)右下 (16,0,16)当我们分割父节点时,我们就分割他的包围坐标,于是节点2的包围坐标为:左上 (0,0,0)右上(8,0,0)左下(0,0,8)右下(8,0,8)如图7.

Figure 7

Test 1

方法如下:我们从根节点开始问“摄象机是否在根节点的包围坐标内?”我们说是。我们知道摄 象机在根节点的一个子节点内,于是测试他们,“摄象机在节点2的包围坐标内吗?”这里回答不, 于是我们离开节点2和它的子节点。这样我们就可以不用测试节点2的64个单元了,不坏,不坏。

Figure 8

Test 2

你可以看图8,我移出了节点2和它的子节点。继续测试,“摄象机在节点3的包围坐标内吗?” ,回答不,于是我们可以安全的离开节点3和它的子节点。

Figure 9

Test 3

继续“摄象机在节点4的包围坐标内吗?”回答不测试节点5。

Figure 10

Test 4

这时,摄象机在节点5的包围坐标内,我们测试它的子节点,我们给他的子节点命名为A,B,C,D, 测试第一个子节点“摄象机在节点A的包围坐标内吗?”如图10,不在,于是我们离开节点A和它的子节 点。

Figure 11

Test 5

现在测试节点5的第二个子节点,“摄象机在节点B的包围坐标内吗?”如图11。不在

Figure 12

Test 6

现在测试节点5的第三个子节点,“摄象机在节点C的包围坐标内吗?”如图12。不在

Figure 13

Test 7

OK,他一定在节点D中,“摄象机在节点D的包围坐标内吗?”,是的,太好了,我们将在这里停止。 考虑一下上面的测试,共有16次测试(节点D内),结果是有5个单元被看见,测试总数是7+16为23。 我们从256减少为23次。

A quadtree is used to dismiss large chunks of terrain at a time. If an apple is on a tree's leaf, chopping off the branches the apple is nowhere near saves you looking on every leaf.

编码

Before we go any further, I advise those who are unsure about Indexed Lists to read through my tutorial here.

我们需要:

一个保存我们QUADTREE数据的结构

一个建立树的函数

一个保存三角形数据的结构

typedef struct node

{

int bType;

VERTEX vBoundingCoordinates[4];

unsigned int uiBranches[4];

unsigned int uiVertexStrip1[8];

unsigned int uiVertexStrip2[8];

unsigned int uiVertexStrip3[8];

unsigned int uiVertexStrip4[8];

unsigned int uiID;

unsigned int uiParentID;

}NODE;

变量bType告诉我们节点的类型,可以为NODE_TYPE or LEAF_TYPE,如果我们画树的话,他用 来作为一个标志告诉程序停止或画一些三角形(LEAF_TYPE),或继续向下解析树(NODE_TYPE)。 下一个变量是一个包含4个顶点的数组,他用来保存节点的包围坐标,VERTEX定义如下

typedef struct vertex

{

float x,y,z;

}VERTEX;

我们还有一个叫做uiBranches的数组,他保存了四个索引值,代表了节点的四个子节点,如果本 节点类型是LEAF_TYPE,就不使用。

由于我们说每个叶节点保存16个多边形,这里有四个数组,名为uiVertexStrip1到uiVertexStrip4, 每个数组保存四个三角形。在本向导中,他们没被使用

变量uiID保存了QUADTREE的节点ID,在我解释他以前,QUADTREE就如同一个节点的数组,这个ID就是 数组的索引

T让我们看看最后一个变量,uiParentID,它是父节点的索引,让我们用自己的方法来遍历这棵树,对 于给定的节点,我们可以从它的父节点遍历到它的子节点,对于下面给定一个树,我们如何遍历他呢,

NODE *pNodeList;

这是一个pNodeList的指针,它是一个QUADTREE,注意:我们使用数组pNodeList[0] 作为根节点。

Formula 1.

上面的公式给出了叶节点的数目,叶宽指的是每个叶的三角形数目,这里我们称叶节点为单元,也可以说每 个单元包含16个三角形,那么这里的叶宽为4个三角形,Grid Width 指的是格子的宽度,由于每个单元有4个 三角形,Grid Width 为16个单元乘以4是64,为了求出树中的节点数,使用下面的函数:

un

  原理:什么是Quadtrees?   由于3D图形卡消费市场的变革,现在3D游戏越来越流行了,他们中大部分是第一人称射击游戏,这 是一个很好的理由,这个理由是室内环境,当和室外环境相比它非常简单。对于室外环境,它没有方便 的通往下一关的楼梯,门,或墙来阻挡你的视线。室外环境都是连续的。对于传统的几何学来说这是非 常棘手的,请打入quadtrees来学习下面的知识。   注意:下面的图示都是从上到下看一个3D地形,方格显示了在X和Y轴上的地形,并看不见现 实中的物体高度,因为我们是顺着Y轴看的。         Figure 1   设想你的地形是一个非常大的方格,在一个X和Z的面上扩展,如图1。我们有一个摄象机在地形的右 下角,它的可视截面(蓝三角)扩展为在相同方向上的小单元,这样在优化前,绘制地形的程序代码看 起来象这样:   for(int ctr=0; ctr   {   DrawCell();   }   注意:一个小单元就是一个包含一些三角形的正方形,它是地形的一部分),看起来非常好,但是本 来我们只是占用了16个单元,可是画了256个。这是非常大的浪费,在我们的可视截面里只有5个单元。 现在第一个优化:我们要测试所有的单元是否在可视截面里,如果在就画他,现在的代码如下:   for(int ctr=0; ctr   {   if(cell is in frustum) DrawCell();   }   如果单元在我们的可视截面中,就画他,非常正确。现在我们只画了5个单元,而不是256个,我们只 是更改很少的代码。在上面,我们保存了我们没有绘出的251个单元,每次都是,这是非常的浪费,如下图:         Figure 2   我将一些单元变成了兰色,这样我们可以建立一个包围盒,如果兰色的单元不在截面内,我们可以安全 的说这个单元在区域A中,如果我们知道兰色的单元不在截面内,我们如何去测试区域A中的其他144个单元 呢,这由quadtrees 来工作   quadtrees 是从地形中获得的,把它分割成四个较小的部分,每一个部分继续分下去,直到一个分到 一个设定的大小,这看起来有点乱,让我结合图片解释一下,首先,从我们的网格出发,现在将他分为四份。         Figure 3   如图三,我们现在有四个子地形,继续分下去,知道一个部分只有一个单元,,在下图中,我们把第一个 小部分分成了四个更小的部分。         Figure 4   然后继续:         Figure 5   然后继续:         Figure 6   好了,现在第一个部件只有一个单元大小,我们告诉树停止分割第一个部件,分割下一个,直到 全部分割完毕。当然你也可以将树分割到合适的三角形数目停止,在我们的例子中为16个三角形,第 一,这个树是父子关系,每个子节点有一个父节点,每个父节点有四个子节点,叶节点例外,他只有 一个父节点没有子节点。叶节点是我们允许的最小的子节点,第二,每个树都有一个根节点,它没有 父节点,但有四个子节点。   再看一下图,暗红的边界就是根节点,在图3中,我们分割根节点,分配给他的子节点。蓝线描绘 的正方形是根节点的四个子。称为节点2,3,4,5。在图4 ,我们把节点2分为四份,这些正方形是 节点的子,称为节点6,7,8,9。继续由节点6分割出10,11,12,13,由节点10分割为14,15, 16,17。这是他们的叶节点。停止分割。分割节点11,分完后是12和13,然后是7,8,和9。然后是 3,4,5。完成。   quadtrees 使用一个节点的包围坐标工作,我们说我们的图形0-16在X轴上,0-16在Z轴上。由于 这个原因,我们整个地图的包围坐标为左上为(0,0,0)右上(16,0,0)左下(0,0,16)右下 (16,0,16)当我们分割父节点时,我们就分割他的包围坐标,于是节点2的包围坐标为:左上 (0,0,0)右上(8,0,0)左下(0,0,8)右下(8,0,8)如图7.         Figure 7   Test 1   方法如下:我们从根节点开始问“摄象机是否在根节点的包围坐标内?”我们说是。我们知道摄 象机在根节点的一个子节点内,于是测试他们,“摄象机在节点2的包围坐标内吗?”这里回答不, 于是我们离开节点2和它的子节点。这样我们就可以不用测试节点2的64个单元了,不坏,不坏。         Figure 8   Test 2   你可以看图8,我移出了节点2和它的子节点。继续测试,“摄象机在节点3的包围坐标内吗?” ,回答不,于是我们可以安全的离开节点3和它的子节点。         Figure 9   Test 3   继续“摄象机在节点4的包围坐标内吗?”回答不测试节点5。         Figure 10   Test 4   这时,摄象机在节点5的包围坐标内,我们测试它的子节点,我们给他的子节点命名为A,B,C,D, 测试第一个子节点“摄象机在节点A的包围坐标内吗?”如图10,不在,于是我们离开节点A和它的子节 点。         Figure 11   Test 5   现在测试节点5的第二个子节点,“摄象机在节点B的包围坐标内吗?”如图11。不在         Figure 12   Test 6   现在测试节点5的第三个子节点,“摄象机在节点C的包围坐标内吗?”如图12。不在         Figure 13   Test 7   OK,他一定在节点D中,“摄象机在节点D的包围坐标内吗?”,是的,太好了,我们将在这里停止。 考虑一下上面的测试,共有16次测试(节点D内),结果是有5个单元被看见,测试总数是7+16为23。 我们从256减少为23次。   A quadtree is used to dismiss large chunks of terrain at a time. If an apple is on a tree's leaf, chopping off the branches the apple is nowhere near saves you looking on every leaf.   编码   Before we go any further, I advise those who are unsure about Indexed Lists to read through my tutorial here.   我们需要:   一个保存我们QUADTREE数据的结构   一个建立树的函数   一个保存三角形数据的结构   typedef struct node   {   int bType;   VERTEX vBoundingCoordinates[4];   unsigned int uiBranches[4];   unsigned int uiVertexStrip1[8];   unsigned int uiVertexStrip2[8];   unsigned int uiVertexStrip3[8];   unsigned int uiVertexStrip4[8];   unsigned int uiID;   unsigned int uiParentID;   }NODE;   变量bType告诉我们节点的类型,可以为NODE_TYPE or LEAF_TYPE,如果我们画树的话,他用 来作为一个标志告诉程序停止或画一些三角形(LEAF_TYPE),或继续向下解析树(NODE_TYPE)。 下一个变量是一个包含4个顶点的数组,他用来保存节点的包围坐标,VERTEX定义如下   typedef struct vertex   {   float x,y,z;   }VERTEX;   我们还有一个叫做uiBranches的数组,他保存了四个索引值,代表了节点的四个子节点,如果本 节点类型是LEAF_TYPE,就不使用。   由于我们说每个叶节点保存16个多边形,这里有四个数组,名为uiVertexStrip1到uiVertexStrip4, 每个数组保存四个三角形。在本向导中,他们没被使用   变量uiID保存了QUADTREE的节点ID,在我解释他以前,QUADTREE就如同一个节点的数组,这个ID就是 数组的索引   T让我们看看最后一个变量,uiParentID,它是父节点的索引,让我们用自己的方法来遍历这棵树,对 于给定的节点,我们可以从它的父节点遍历到它的子节点,对于下面给定一个树,我们如何遍历他呢,   NODE *pNodeList;   这是一个pNodeList的指针,它是一个QUADTREE,注意:我们使用数组pNodeList[0] 作为根节点。      Formula 1.   上面的公式给出了叶节点的数目,叶宽指的是每个叶的三角形数目,这里我们称叶节点为单元,也可以说每 个单元包含16个三角形,那么这里的叶宽为4个三角形,Grid Width 指的是格子的宽度,由于每个单元有4个 三角形,Grid Width 为16个单元乘以4是64,为了求出树中的节点数,使用下面的函数:   un
󰈣󰈤
 
 
 
>>返回首页<<
 
 热帖排行
 
 
 
静静地坐在废墟上,四周的荒凉一望无际,忽然觉得,凄凉也很美
©2005- 王朝网络 版权所有