xosen

翻译：宋晓宇    write by Henri Haki

介绍：
　　传统计算机图形应用--特别是的应用的需要一个实时，交互的方法来现实--通过处理一个发送到显卡的数据的最有效的图形数据子集的方法来决定图形数据的显示，而不是传送全部的数据，四叉树，八叉树，Bsp树，背面剔出，pvs集合很多其他方法都是针对这个目的而提出的。

　　流行的计算机图形卡近些年在处理能力和处理方法上程指数增长，当前的状态揭示出很多时候应该更好的和快速的找到一个好的数据集把它们送到显卡里，而不是把精力放在努力的找到一个最好的数据集。这样的数据集是一个近似的最好的数据集并且能经常发现它都有十分有效的算法，因此手头上的任务因此就变成了回顾已经存在的技术和算法并且尝试找到最快的选择，这对于找到最好的解决问题的方法并不是什么负担。

一、四叉树：
　　四叉树作为数据处理表达技术的一个好方法已经有很多年了，特别是地形渲染引擎都能利用他很有效的作为剔出机制，剩余的这个章节将会给出一个小数量的说明四叉树并且传统的，高层的方法使用四叉树，在描述一个快速的方法之前。

四叉树数据结构：

　　四叉树被描述通过对应每个父节点传递四个子节点，在一个地形渲染上下文里，根节点将会表达为这个围绕地形的正方形区域集，自节点表示为“左上”，“右上”，“左下”和“右下”象限，这些象限由根节点组成并且每一个都是由四个字节点递归的定义下面的描述将会说明这些概念一个四元数的数据结构并不负责,下面的伪码演示了这个四叉树的节点：

TPosition = record
  x,y : float;
end;

PQuad = pointer to TQuadNode;
TQuad = record
  p1,p2,p3,p4 : TPosition;    // corners
  c1,c2,c3,c4 : PQuadNode;    // children
end;

一个简单的递归初始化一个深度为max_depth的四叉树如下：

function InitQuad(x,y,w : float; lev : int) : PQuad;
var
  tmp : PQuad;
begin
  inc(lev);
  if lev > max_depth then return(nil);
  new(tmp);
  ...initialize tmp node with corner data
  w := w / 2;
  tmp^.c1 := InitQuad(x - w, y - w, w, lev);
  tmp^.c2 := InitQuad(x - w, y + w, w, lev);
  tmp^.c3 := InitQuad(x + w, y + w, w, lev);
  tmp^.c4 := InitQuad(x + w, y - w, w, lev);

  return(tmp);
end;

基于四叉树的背面剔除

　　在很多应用里主要的四叉树函数是提供一个有效的的视截体数据剔除,下面的基于视点的高层视截体剔除已经够了：

procedure CullQuad(q : PQuad);
begin
  case Clip_Quad_against_View(q) of
    inside  : DrawQuad(q);
    outside : ; // ignore quad
    else begin
      ...CullQuad children of q
    end;
  end;
end;

Clip_Quad_against_View 是cullquad的关键函数，并且当然运行的函数和方法来解决这个问题是否是一个四元（或者多边形）交叉于这个视见体，通过交叉视见体金字塔作为平面集合检测平面作为一套光线，然后连续测试几何体的光线怎么和可视体平面相交的，光线相交测试的方程在很多３ｄ几何的书上都可以找到，这里不做重复。

二、选择基于四叉树的视点剔除：

　　上面描述的方法一般情况下会得出正确的结果，但是他没有给这个简单的静态的四叉树提供任何东西，好多的优化可以应用到四叉树的剔除过程，下面的两个阶段产生了一个很快的和很有效的基于四元数的剔除：

　　*基于点的剔除：一个完全的剔除计算，他通过记录相关的四个角的可视点。

　　很多这样的情况可以被考虑，例如：如果一个单独的点在视见体内发现，那么这个块就在视见体内，如果所有的点都在视见体的一面，那么这个块就不在视见体内．一个数量的可能性就存在，并且需要通过一个完全的计算，但是上面给出的两种情况得出了一个充足的启发性来接受，丢弃或者将来重新定义一个潜在的块。

　　*Ｍｏｍｏｉｚａｔｉｏｎ：是一种储存计算结果的技术并且还需要相同的计算时查找储存的结果。

　　四元数作为一个静态结构，这种特殊角的点经常都是相同的，另外，很多块的角是四个块共享的，并且在循环传递四元数的角一遍又一遍的，通过决定一个角的相关位置关联这个可视体和方便的储存这个四元数的的计算结果。

　　下面的伪代码声明了这个算法，对于一个四元数横跨的区域是(0,0)到(256,256);

(globals:)
Memoized : array[0..256,0..256] of byte;
posx,posy : float;  // origin of FOW
Lx,Ly,Lz : float;   // normal of left FOV plane
Rx,Ry,Rz : float;   // normal of right FOV plane

function CheckPos(x, y : int) : int;
// checks position x,y against FOV planes, memoize
// Results: bit 1 (inside), bit 2 (left), bit 3 (right)
var
  res : int;
begin
  res := 0;
  if (x-posx)*Lx + (y-posy)*Ly > 0 then res := 2;
  if (x-posx)*Rx + (y-posy)*Ry > 0 then res := res or 4;
  if res = 0 then res := 1;
  Memoized[x,y] := res;
  return res;
end;

function TestQuad(x, y, w : int) : int;
// quad-midpoint: (x,y)
// quad-width: 2w
// test quad against FOV
// Results: 0 (out), 1 (partially in), 2 (completely in), -1 (unknown)
var
  m1,m2,m3,m4 : int;
  tmp : int;
begin
  m1 := Memoized[x - w, y + w];
  if m1 = 0 then CheckPos(x - w, y + w);
  m2 := Memoized[x + w, y + w];
  if m2 = 0 then CheckPos(x + w, y + w);
  m3 := Memoized[x + w, y - w];
  if m3 = 0 then CheckPos(x + w, y - w);
  m4 := Memoized[x - w, y - w];
  if m4 = 0 then CheckPos(x - w, y - w);

  tmp := m1 and m2 and m3 and m4;
  if tmp = 1 then
    return 2;        // quad completely inside FOV

  if m1 or m2 or m3 or m4 = 1 then
    return 1;        // quad partially inside FOV

  if tmp => 0 then
    return 0;        // quad completely outside FOV

  return -1;         // else quad state undetermined
end;

上面的函数应该被清除并且及早的需要整数的的四元块程序

procedure CullQuadtree;
begin
  Clear_Memoized_Array_to_Zero;
  CullQuad(Quadtree_Root);
end;

procedure CullQuad(q : PQuad);
begin
  case Test(quadmidpoints and half-width) of
    2 : ...handle complete quad
    1 : ...handle partial quad
    0 : ;  // ignore quad
    else begin
      ...CullQuad children of q
    end;
  end;
end;

三、另外需要考虑的：

很多在代码里和一般的算法里都需要被考虑的是：

　　*四叉树算法的版本里表现出的只剔除左/右，不是近裁剪面，不是远裁减面或者上下都没有考虑，另外只有平面视角。因此这个算法只覆盖了四叉树的的高度剔除和视见面沿着这个四叉树的面。

　　我们扩展这些代码沿着3d的四叉树，增加如：应用四叉树的移出算法-任何可视的位置和方向将会正确的进行的东西。

　　*另外很多附加的点，视见体需要考虑执行的比如：如果两个点在视见体的前面并且对这FOV的一个面，这个块部分在这个视见体里，对于很多的算法，这样的关卡满足这个结果。

　　*主要关心这个算法的需要是在记忆需求里，尽管一般的沉浸记忆对于每个可能的块某些点需要一个附加的字节。因此如果正方形的区域有n个间隔，每个面都都需要n个字节来储存，通过典型的只有一个碎片的内存被一个给定的遍历访问，这一部分就被访问了很多次。

　　这篇文章总结了算法的表达，我发现这是一个有用积极的算法，如果你查询了相关的算法并且有感触可以写信给我咨询。

英文原文出处：http://www.gamedev.net/reference/articles/article1485.asp

　　第一次翻译文章贴出，错误很多，尚未修改，希望大家谅解和支持。原来一直喜欢看别人翻译后的文章，今天早上实在找不到汉语的来看，索性翻译一篇好了，心想也报了12月份的英语6级考试从没复习过，就当仔细复习下英语好了。也改一改看英文文档不仔细的毛病。谁知道遇到了太多的困能。唉！看来以后要体谅一下那些翻译专业英文的人了。而且本来想要发表到技术文档区的，可实在怕丢人就算了，发这里大家先给意见再说了。谢谢各位了。