[翻译] 4叉树和 8叉树的剔出选择

翻译:宋晓宇writebyHenriHaki

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

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

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

4叉树数据结构:

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

TPosition=record
x,y:float;
end;

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

个简单递归化个深度为max_depth 4叉树如下:

functionInitQuad(x,y,w:float;lev:):PQuad;
var
tmp:PQuad;
begin
inc(lev);
lev>max_depththen(nil);
(tmp);
...initializetmpnodewithcornerdata
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);

(tmp);
end;

基于 4叉树背面剔除

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

procedureCullQuad(q:PQuad);
begin
Clip_Quad_against_View(q)of
inside:DrawQuad(q);
outside:;//ignorequad
begin
...CullQuadchildrenofq
end;
end;
end;

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

2、选择基于 4叉树视点剔除:

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

　　*基于点剔除:个完全剔除计算他通过记录相关 4个角可视点

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

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

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

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

(globals:)
Memoized:.gif' />[0..256,0..256]of;
posx,posy:float;//originofFOW
Lx,Ly,Lz:float;//normalofleftFOVplane
Rx,Ry,Rz:float;//normalofrightFOVplane

functionCheckPos(x,y:):;
//checkspositionx,yagainstFOVplanes,memoize
//Results:bit1(inside),bit2(left),bit3(right)


var
res:;
begin
res:=0;
(x-posx)*Lx+(y-posy)*Ly>0thenres:=2;
(x-posx)*Rx+(y-posy)*Ry>0thenres:=resor4;
res=0thenres:=1;
Memoized[x,y]:=res;
res;
end;

functionTestQuad(x,y,w:):;
//quad-midpo:(x,y)
//quad-width:2w
//testquadagainstFOV
//Results:0(out),1(partiallyin),2(completelyin),-1(unknown)
var
m1,m2,m3,m4:;
tmp:;
begin
m1:=Memoized[x-w,y+w];
m1=0thenCheckPos(x-w,y+w);
m2:=Memoized[x+w,y+w];
m2=0thenCheckPos(x+w,y+w);
m3:=Memoized[x+w,y-w];
m3=0thenCheckPos(x+w,y-w);
m4:=Memoized[x-w,y-w];
m4=0thenCheckPos(x-w,y-w);

tmp:=m1andm2andm3andm4;
tmp=1then
2;//quadcompletelyinsideFOV

m1orm2orm3orm4=1then
1;//quadpartiallyinsideFOV

tmp=>0then
0;//quadcompletelyoutsideFOV

-1;//quadstateundetermined
end;

上面应该被清除并且及早需要整数 4元块

procedureCullQuadtree;
begin
Clear_Memoized_Array_to_Zero;
CullQuad(Quadtree_Root);
end;

procedureCullQuad(q:PQuad);
begin
Test(quadmidposandhalf-width)of
2:...handlecompletequad
1:...handlepartialquad
0:; //ignorequad
begin
...CullQuadchildrenofq
end;
end;
end;

3、另外需要考虑:

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

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

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

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

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

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

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

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

延伸阅读