我的关于quadTree中LOST OF DETAIL的意识流思考，写出来欢迎

kingsom

首先的问题是：

什么时候ＬＯＳＴ？

足够远。

怎么体现ＬＯＳＴ？

渲染更少的定点。

意识流出来了：

begin

ｆｏｒ　ｅａｃｈ　ｐａｔｃｈ

ｉｆ（足够远）

渲染更少的定点；

end；

如何定义这个patch呢？


不好说。。。。（geomipmapping用的是这种结构）



但是现在，，


quadTree算法反其道而行之：


意识流如下：：


//begin：

if(足够近并且变长大于或者等于2)

{

    分解它为四个小正方形。

}else

{

//这里只是放一个渲染标记它要被渲染哈哈。。并不渲染的。
      渲染它！

}

//end


看上去很简单！！！


在这样的简单实现过程出现了CRACK怎么办呢？？？


如下图：









画圈圈的地方都是出现Crack的地方啊。。


如何处理呢？？？



所以要从本质上判断啊！！！



应该像这样：



if(这个顶点不是它邻居的顶点){

不渲染它。。

}

else

{

渲染它..

}



那么。。。现在的焦点就在于如何判断这个顶点不是它邻居的顶点了！！！！



这个怎么去想呢？？？？？？？？？？


先丢一边吧！

我是一下子没有想出来啊！！！！不过，我再想下面这个问题：：

那么大一个地图。。我们总得遍历吧！！！！

那么我们遍历的最小单位是什么！！！！

例如：


foreach

renderEach；


我们的each 是什么！！！！


Each 顶点  么！！！


不！！！坚决不能，为什么？


因为CRack的存在！！！我们必须得调整这些定点。


那么三角型如何！！！


（呵呵没有试验过！！不过有Ｒｏａｍ算法好像就是三角型的！！！）

（
ｑｕａｄＴｒｅｅ用的是什么呢！！！

当然是quad了！！

｝
好了！！

发明这个ｑｕａｄＴｒｅｅ算法的人


是先有ｑｕａｄＴｒｅｅ再想到ｑｕａｄ呢


还是从quad的想法诞生了一个ｑｕａｄＴｒｅｅ算法出来呢？


不管了！！现在就从那么个最小单位说其吧：


如下图：


1      2
   
   5
   
3      4




四个三角形拼接起来的（假）正方形！说它假，是因为不在一个平面上。

一句话：


　　一个不能再分成四份方块的方块？？？？



一个不能再分的方块是什么呢，不能被分成四份！！！！！！！！！！！！





它是什么呢？？？？？？？？？





在Tree里面！！！！





叶子!!!!!!!!!!!!!!!!



所以！


我们的渲染代码应该像这样：



//遍历所有的叶子！！



Render(TreeNode* tree)

{

     

     if 是叶子节点，

       render(Tree->data)；

     else

        Render（tree->leftupTreeNode）;

        Render(Tree->leftdownTreeNode);

        Render(Tree->rightupTreeNode);

         Render(Tree->rightdownTreeNode);

}



那么现在集中的问题是再哪里呢？





render（Tree->data）；



在这句了；



所有的代码都集中这个地方。。因为我们的递归遍历，最终的落脚点！！！！





问题很明朗了！！！

下面是如何实现render（ｔｈｅＥｌｅｍｅｎｔＱｕａｄ）；


就是在这个地方，这个函数，我们要判断裂缝的存在性！！


这当然需要数据！！参数不能只有一个theElementQuad咯！！

或者这个theElementQuad要有所有能判断它是否：


像以前所说的！！


if(这个顶点不是它邻居的顶点){

不渲染它。。

}

else

{

渲染它..

}

好了。。到此为至。。后面的理论是为每一个中心点保留一个表明叶子层级的东西！！

用了两个二维数组表。。。

一个表明这个quad的Tree层级，一个表明这个quad的大小，也就是边长！！


然后联合起来，就判断除了，这个顶点是不是相邻quad的顶点！！



我还没想清楚怎么算的。不过认为到此离成功不远了！！

kingsom

补充一下吧：算是更详细的解释。


首先说明ＬＯＳＥ　ＯＦ　ＤＥＴＡＩＬ　代码在整个地形网格渲染过程中的位置，

它是再所有的纹理，法线，高度都给了之后剔除顶点的。

它也就是

ｄｒａｗＥｌｅｍｅｎｔｓ的最后一道工序。。


一个ｎ＊ｎ大的网格中，剔除其中的一部分定点来模拟模糊的远景的。

高度有了？？

（ｘ，ｙ，ｚ）？

看到没有！有个！！！ｙ！！！


也就是说地图是三维的，


哪么一个三维中的假正方形？？？？


它的中心？


如果我们的ｑｕａｄ是　


１　　２


３　　４

这就依赖于我们绘制的顺序咯！！


例如　１　３　４　２　哪么中心就是　　

（（ｘ１＋ｘ４／２），（ｙ１＋ｙ４）／２，（ｚ１＋ｚ４）／２）；


也就是说：中心依赖于我们的绘制顺序！！！！比如


　　３　４　２　１　　那么中心就是另外一种情形：
（（ｘ２＋ｘ３／２），（ｙ２＋ｙ３）／２，（ｚ２＋ｚ３）／２）；


现在把它反过来说：

　　如果给了一个中心坐标！！而且还知道它再两个对角线的哪条对角线上！那么这个（假）四变形必须按照某种顺序来绘制！！


因为这是ｑｕａｄＴｒｅｅ算法的第一步，所以必须搞清楚！！

下面看一看ｑｕａｄＴｒｅｅ是大概如何确定它的
子方块的中心：

假设说一个ｑｕａｄ仅仅如此：

ｃｌａｓｓ　ｑｕａｄ｛
　　　ｇｌＩｎｔ３ｖ　ｃｅｎｔｅｒ；
　　　ｇｌＩｎｔ　　ｓｉｚｅ；
｝
／／左上角

ｌｅｆｔＵｐＱｕａｄｅ．ｃｅｎｔｅｒ＝。。。；

ｌｅｆｔＵｐＱｕａｄ．ｓｉｚｅ＝ｓｉｚｅ／２；
／／左下角
ｌｅｆｔＤｏｗｎＱｕａｄｅ．ｃｅｎｔｅｒ＝。。。；

ｌｅｆｔＤｏｗｎＱｕａｄ．ｓｉｚｅ＝ｓｉｚｅ／２；
／／右上角
。。。。
／／右下角
。。。。

现在的问题是：

如果一个ｌｅｆｔＵｐＱｕａｄ也仅仅提供了这样一些信息：

一个中心坐标：　ｘ，ｙ，ｚ
一个边长：ｓｉｚｅ（确切的说是边长在ｘ，ｚ平面上的投影）

如何确定中心在哪条对角线上！！！

最简单的方法是让它的子节点保持一个父节点的指针：（如下所示）

可以直接根据子和父中心的相对位置来判断具体的位置关系。

ｃｌａｓｓ　Ｑｕａｄ｛
　　　ｇｌＩｎｔ３ｖ　ｃｅｎｔｅｒ；
　　　ｇｌＩｎｔ　　ｓｉｚｅ；
　　　ｑｕａｄ＊　ｐＰａｒｅｎｔ；
｝

根据不同的ｄｉｒｅｃｔ选择不同的绘制方法！！（我是这样想的！）

那么ＱｕａｄＮｏｄｅ呢？

这样写：

ｃｌａｓｓ　ＱｕａｄＮｏｄｅ｛
　Ｑｕａｄ　　Ｄａｔａ；／／
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＵｐＬｅｆｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＵｐＲｉｇｈｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＤｏｗｎＬｅｆｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＤｏｗｎＲｉｇｈｔ；
｝
好了！！现在添加方法，什么方法呢！！！！！！！！！！

不用猜也知道！！！为什么，因为说过啦，它仅仅需要的是如何render一个叶子！！！

那么什么叫做叶子呢？？？

当然是四个子节点都是NULL了。先不管这个，先写个RenderLeaf吧，然后呢加一个Render方法！

好了  看一看现在我的quadNode的样子吧：
ｃｌａｓｓ　ＱｕａｄＮｏｄｅ｛
  Ｒｅｎｄｅｒ（）；
　ＲｅｎｄｅｒＬｅａｆ（）；
　Ｑｕａｄ　　Ｄａｔａ；／／
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＵｐＬｅｆｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＵｐＲｉｇｈｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＤｏｗｎＬｅｆｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＤｏｗｎＲｉｇｈｔ；
｝
很简单吧！！！！！！其实真的很简单哦。。

Ｒｅｎｄｅｒ（）最终的落脚点在ＲｅｄｅｒＬｅａｆ上

ＲｅｎｄｅｒＬｅａｆ需要怎么避免Ｈｏｌｅ的出现！！

再看看新鲜出炉的ＲｅｎｄｅｒＬｅａｆ方法吧：

ＲｅｎｄｅｒＬｅａｆ（）
｛
ｉｆ（顶点不是矩形的顶点）
　｛
　去除这个顶点
　｝ｅｌｓｅ
　｛
　不去除
　｝；
　渲染它；
｝
好了！！很简单吧！！现在根据由接口再到数据ＯＯＰ思想：

看看我们实现这个东西需要什么样的基本数据吧：

在ＯｐｅｎＧＬ中，渲染一个东西最通用的方法是，给出顶点的索引；好了，我们的ＲｅｎｄｅｒＬｅａｆ得到了更进一步的质量提升：：


ＲｅｎｄｅｒＬｅａｆ（）
｛
ｉｆ（顶点不是相邻矩形的顶点）
　｛
　去除这个顶点
　｝ｅｌｓｅ
　｛
　不去除
　｝；
　ＤｒａｗＩｎｄｅｘ（ｇｌＩｎｔ　ｉｎｄｅｘes, unsigned byte size);
｝
好了，看到没，我们需要一个Index[] unsigned byte 这些数据！！！！！一个整形数组和它的大小！！！！

好，我们把它添上吧！！现在的QuadNode应该是这样:


ｃｌａｓｓ　ＱｕａｄＮｏｄｅ｛
  Ｒｅｎｄｅｒ（）；
　ＲｅｎｄｅｒＬｅａｆ（）；
//////////////////////////
  glInt[] Indexes;
  glUnChar Size;
//////////////////////////
　Ｑｕａｄ　　Ｄａｔａ；／／
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＵｐＬｅｆｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＵｐＲｉｇｈｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＤｏｗｎＬｅｆｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＤｏｗｎＲｉｇｈｔ；
｝
斜杠中间是新添加的。注意了。。

一个方块有四个顶点，

假设为， 1，2，3 ，4

去除了一个剩一个，如何去除呢！！！

我没有去想，但是我知道我需要有一个方法来做这件事情！！！

好！！可是，现在我们需要一个void GetIndexOut(int Indexes[],int &size,int theIndex).

好了现在的节点应该像这么个样子：

ｃｌａｓｓ　ＱｕａｄＮｏｄｅ｛
  //-------- 新添加的数据--------//
  void GetIndexOut(int theIndex);
  //---------************-----------//
  Ｒｅｎｄｅｒ（）；
　ＲｅｎｄｅｒＬｅａｆ（）；
//////////////////////////
  glInt[] Indexes;
  glUnChar Size;
//////////////////////////
　Ｑｕａｄ　　Ｄａｔａ；／／
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＵｐＬｅｆｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＵｐＲｉｇｈｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＤｏｗｎＬｅｆｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＤｏｗｎＲｉｇｈｔ；
｝

我仔细想想，其实我要的应该是个链表！！

链表的删除操作要容易的多！！！

可是，人家OpenGL就只认数组！

好，那现在加个链表！！！

ｃｌａｓｓ　ＱｕａｄＮｏｄｅ｛
  //
  List list;
  //
  //-------- 新添加的数据--------//
  void GetIndexOut(int theIndex);
  //---------************-----------//
  Ｒｅｎｄｅｒ（）；
　ＲｅｎｄｅｒＬｅａｆ（）；
//////////////////////////
  glInt[] Indexes;
  glUnChar Size;
//////////////////////////
　Ｑｕａｄ　　Ｄａｔａ；／／
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＵｐＬｅｆｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＵｐＲｉｇｈｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＤｏｗｎＬｅｆｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＤｏｗｎＲｉｇｈｔ；
｝

有了链表，我们的数组就可以拜拜了

ｃｌａｓｓ　ＱｕａｄＮｏｄｅ｛
  //
  List list;
  //
  //-------- 新添加的数据--------//
  void GetIndexOut(int theIndex);
  //---------************-----------//
  Ｒｅｎｄｅｒ（）；
　ＲｅｎｄｅｒＬｅａｆ（）；
///////////这部分删除///////////////
  glInt[] Indexes;
  glUnChar Size;
//////////////////////////
　Ｑｕａｄ　　Ｄａｔａ；／／
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＵｐＬｅｆｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＵｐＲｉｇｈｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＤｏｗｎＬｅｆｔ；
　ＱｕａｄＮｏｄｅ＊　ｐ＿ＤｏｗｎＲｉｇｈｔ；
｝

但是，需要在以下地方加代码：

ＲｅｎｄｅｒＬｅａｆ（）
｛
ｉｆ（顶点不是相邻矩形的顶点）
　｛
、、、、、、添加的代码、、、、、、、、、、
　List.remove()
、、、、、、、、、、、、、、
　｝
////////////添加的代码///////////////
indexes= List.copy();
  size=list.sie();
//////////////////
　ＤｒａｗＩｎｄｅｘ（ｇｌＩｎｔ　ｉｎｄｅｘes, unsigned byte size);
｝

好了。。。一切OK!!!!!现在就只有一个问题，就是那一句：：：

所有的问题现在集中在这一句上！！！！！

、、、、、、、、、、、、、
顶点不是相邻矩形的顶点
、、、、、、、、、、、、、、

好，现在讨论它可能需要的数据。。


相邻的矩形是什么呢！！！其实还是叶子，，，


所有的  大大小小的

1         2


3         4

现在以一种树方式组织了起来，现在我们缺要在位置上找邻居？？？？

很混乱吧。。。。。。。。。。


其实即使邻居找到之后，去除顶点，顶点的去除必然引发新的邻居结构！好。。。问题就在这里！！！！！

看看我的逻辑多么的可笑，这是一个Tree的自我判断，又自我拆卸的过程啊！

拆卸的过来又反过来影响自我判断的结果！

这个是什么破逻辑啊！

不过它确实可行，只是每次遍历方法（前序，中序，后序），产生的结果不一样！！！！！！！！

好了！于是很牛逼的人。。。。写了一些很牛逼的算法。。。。。例如：

如果保证相邻的大小仅仅相差1，，，那么。。。产生的结果就会相同啦。


这个我还没弄懂为什么以及怎么保证的，

那篇论文中用了很复杂的数学公式套公式，爷爷的，真够狠的！！

好了到此为止。。。。。。

♂樱♀

高