英文原文出處：
http://www.gamedev.net/reference/articles/article1485.asp翻譯:宋曉宇
介紹： 傳統(tǒng)計算機圖形應(yīng)用--特別是的應(yīng)用的需要一個實時，交互的方法來現(xiàn)實--通過處理一個發(fā)送到顯卡的數(shù)據(jù)的最有效的圖形數(shù)據(jù)子集的方法來決定圖形數(shù)據(jù)的顯示，而不是傳送全部的數(shù)據(jù)，四叉樹，八叉樹，Bsp樹，背面剔出，pvs集合很多其他方法都是針對這個目的而提出的。
流行的計算機圖形卡近些年在處理能力和處理方法上程指數(shù)增長，當前的狀態(tài)揭示出很多時候應(yīng)該更好的和快速的找到一個好的數(shù)據(jù)集把它們送到顯卡里，而不是把精力放在努力的找到一個最好的數(shù)據(jù)集。這樣的數(shù)據(jù)集是一個近似的最好的數(shù)據(jù)集并且能經(jīng)常發(fā)現(xiàn)它都有十分有效的算法，因此手頭上的任務(wù)因此就變成了回顧已經(jīng)存在的技術(shù)和算法并且嘗試找到最快的選擇，這對于找到最好的解決問題的方法并不是什么負擔。
一、四叉樹： 四叉樹作為數(shù)據(jù)處理表達技術(shù)的一個好方法已經(jīng)有很多年了，特別是地形渲染引擎都能利用他很有效的作為剔出機制，剩余的這個章節(jié)將會給出一個小數(shù)量的說明四叉樹并且傳統(tǒng)的，高層的方法使用四叉樹，在描述一個快速的方法之前。
四叉樹數(shù)據(jù)結(jié)構(gòu)：四叉樹被描述通過對應(yīng)每個父節(jié)點傳遞四個子節(jié)點，在一個地形渲染上下文里，根節(jié)點將會表達為這個圍繞地形的正方形區(qū)域集，自節(jié)點表示為“左上”，“右上”，“左下”和“右下”象限，這些象限由根節(jié)點組成并且每一個都是由四個字節(jié)點遞歸的定義下面的描述將會說明這些概念一個四元數(shù)的數(shù)據(jù)結(jié)構(gòu)并不負責,下面的偽碼演示了這個四叉樹的節(jié)點：
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;
基于四叉樹的背面剔除 在很多應(yīng)用里主要的四叉樹函數(shù)是提供一個有效的的視截體數(shù)據(jù)剔除,下面的基于視點的高層視截體剔除已經(jīng)夠了：
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的關(guān)鍵函數(shù)，并且當然運行的函數(shù)和方法來解決這個問題是否是一個四元（或者多邊形）交叉于這個視見體，通過交叉視見體金字塔作為平面集合檢測平面作為一套光線，然后連續(xù)測試幾何體的光線怎么和可視體平面相交的，光線相交測試的方程在很多３ｄ幾何的書上都可以找到，這里不做重復(fù)。
二、選擇基于四叉樹的視點剔除：上面描述的方法一般情況下會得出正確的結(jié)果，但是他沒有給這個簡單的靜態(tài)的四叉樹提供任何東西，好多的優(yōu)化可以應(yīng)用到四叉樹的剔除過程，下面的兩個階段產(chǎn)生了一個很快的和很有效的基于四元數(shù)的剔除：
*基于點的剔除：一個完全的剔除計算，他通過記錄相關(guān)的四個角的可視點。
很多這樣的情況可以被考慮，例如：如果一個單獨的點在視見體內(nèi)發(fā)現(xiàn)，那么這個塊就在視見體內(nèi)，如果所有的點都在視見體的一面，那么這個塊就不在視見體內(nèi)．一個數(shù)量的可能性就存在，并且需要通過一個完全的計算，但是上面給出的兩種情況得出了一個充足的啟發(fā)性來接受，丟棄或者將來重新定義一個潛在的塊。
*Ｍｏｍｏｉｚａｔｉｏｎ：是一種儲存計算結(jié)果的技術(shù)并且還需要相同的計算時查找儲存的結(jié)果。
四元數(shù)作為一個靜態(tài)結(jié)構(gòu)，這種特殊角的點經(jīng)常都是相同的，另外，很多塊的角是四個塊共享的，并且在循環(huán)傳遞四元數(shù)的角一遍又一遍的，通過決定一個角的相關(guān)位置關(guān)聯(lián)這個可視體和方便的儲存這個四元數(shù)的的計算結(jié)果。
下面的偽代碼聲明了這個算法，對于一個四元數(shù)橫跨的區(qū)域是(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;
上面的函數(shù)應(yīng)該被清除并且及早的需要整數(shù)的的四元塊程序
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;
三、另外需要考慮的：很多在代碼里和一般的算法里都需要被考慮的是：
*四叉樹算法的版本里表現(xiàn)出的只剔除左/右，不是近裁剪面，不是遠裁減面或者上下都沒有考慮，另外只有平面視角。因此這個算法只覆蓋了四叉樹的的高度剔除和視見面沿著這個四叉樹的面。
我們擴展這些代碼沿著3d的四叉樹，增加如：應(yīng)用四叉樹的移出算法-任何可視的位置和方向?qū)_的進行的東西。
*另外很多附加的點，視見體需要考慮執(zhí)行的比如：如果兩個點在視見體的前面并且對這FOV的一個面，這個塊部分在這個視見體里，對于很多的算法，這樣的關(guān)卡滿足這個結(jié)果。
*主要關(guān)心這個算法的需要是在記憶需求里，盡管一般的沉浸記憶對于每個可能的塊某些點需要一個附加的字節(jié)。因此如果正方形的區(qū)域有n個間隔，每個面都都需要n個字節(jié)來儲存，通過典型的只有一個碎片的內(nèi)存被一個給定的遍歷訪問，這一部分就被訪問了很多次。
這篇文章總結(jié)了算法的表達，我發(fā)現(xiàn)這是一個有用積極的算法，如果你查詢了相關(guān)的算法并且有感觸可以寫信給我咨詢。