英文原文出處：
http://www.gamedev.net/reference/articles/article1485.asp翻譯:宋曉宇
介紹： 傳統計算機圖形應用--特別是的應用的需要一個實時，交互的方法來現實--通過處理一個發送到顯卡的數據的最有效的圖形數據子集的方法來決定圖形數據的顯示，而不是傳送全部的數據，四叉樹，八叉樹，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個字節來儲存，通過典型的只有一個碎片的內存被一個給定的遍歷訪問，這一部分就被訪問了很多次。
這篇文章總結了算法的表達，我發現這是一個有用積極的算法，如果你查詢了相關的算法并且有感觸可以寫信給我咨詢。