quadTree 论文Real-Time Generation of Continuous吃透了

Real-Time Generation of Continuous Levels of Detail for Height Fields

下面总结一下：

 

 

首先说明quadTree里面的最小单位：

 

 

最小的叶子：

 

 

它有9个点哦！！！！！！！

 

 

1   2    3

 

4   5    6

 

7   8    9

 

也就是说边长为2.。。。。。。。。。

 

好不容易想清楚。。。。。。

 

也就是最小的叶子：

1.关于quadTree 如何保存的问题，用个二维表就可以了。

2.通过调整d2的值，来保证一个相临的节点之间的深度只差1或者0；

先找到最大可能深度。。为MaxDepth

? ? ? ? ? ? ? ? ?
? ? ? ? ? 0 ? 0 ?
? ? 0 ? ? ? 1 ? ?
? ? ? ? ? 0 ? 0 ?
? ? ? ? 1 ? ? ? ?
? 0 ? 0 ? 0 ? 1 ?
? ? 1 ? ? ? 1 ? ?
? 0 ? 0 ? 0 ? 1 ?
? ? ? ? ? ? ? ???

 

注意最小的单位为9个点：

 

 

1   2   3

 

4   5   6

 

7   8   9

 

可以设置一个最深的深度阀值。其实也可以不设。

深度=Max；

while（深度=0）

{

  求得所有深度为此，深度的中心；

 

 计算d2

    

 这时候父节点就得到了4个d2值乘以K，找到自己的d2，然后有,从中选出最大的那一个进行保留。

 

 把4个d2传给下一层。

 

 深度减去1，

  

 重复上面的过程。直到d2为0；

}

 

   方法是再次从底层向高层，往上遍历D2参数，如果有一个值比这个的K倍，也就是 2C/(C-1) 小，那么我们该怎么办呢！找出最大的一个。max（K*lowerADJd2,TheCurrentD2）;并设为这个值。

3.因为d2有了，根据条件f<1,就可以保证相邻节点之间的深度只差1.

 

4.

有很多逻辑问题在这里面！！！！！！！！！！

 

然后渲染叶子！！！！！

 

去除那些不必要渲染的点的时候，这样做：

 

根据方位，具体问题具体分析！！！！！！！！

 

而且Morphing也就是地貌化，

 

叶子的渲染。根据方位，，判断Crack。。插值高度！！

 

等等。。。

 

在渲染过程中我们保存一个 d=2（1-f）在节点的中心！！！！！！

 

 

然后用公式

 

 

d×（实际高度）+（1-d）×（对角线两点的平均高度）

 

 

总共有5个点需要插值！！包括中间的点！！

必须搞清楚咯！！！！！！！！！！！！！！！！！！！！！！！！！

 

每一个叶子一共渲染9个点。。。

 

 

如果叶子的角点被标记为 “不需要渲染”

 

 

哪么可以根据具体位置。。选择要渲染的点。。

 

 

叶子的边点是必须要渲染德。。

 

 

叶子的角点则根据具体情况具体分析。。

 

也就是说D>=2;

 

也就是说只有下面情况需要考虑：

 

 

1           2          5                              11

 

 

3           4           6           

 

 

7           8           9                                12

 

 

渲染右边的时候。对于6 这个点，我们用混合因子。

 

而渲染左边的时候。我们只需要考虑。。是否渲染6 这个点。

 

 

而上边，如果是个同样的叶子，则不用考虑，因为没有突变！！

 

 

如果是半个叶子。。那么。。

 

 

则在边上渲染4个扇形。。不用渲染叶子。。

 

 

 

算法：

 

if( 节点是叶子)

{

    find父节点；

    find 父节点相关的两个邻节点；

    if（深度与2相同或者大于2）

   {

        找到此叶子节点父节点的对应邻边的子节点。

        比较深度。

       if（深度相同叶子）直接渲染

       if（深度大于1（节点））说明了丢失了部分细节，用混合因子插边值进行渲染。

             相当于多渲染了一个点。（这个点可以保证不被邻边渲染。）

    }

 else if

{

小于2.也就是叶子。

 

根据方位，渲染3个点或者不渲染。 

 说明地貌化已经做过了。

 

 

 

}

 

}

 

好了！！！！！！！！！！！！！！！！！！！！！！！！！！！！！完了。。。。。。。。。。。