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