背景：
这是Delphi 3D 的3D Engine Dev.系列tutorial。（www.delphi3d.net）
This site is written and maintained by Tom Nuydens.
从基本的view system到高级的PVS(Possible Visible Set)，LOD(Level of Detail)都有介绍，难能可贵的是写的深入浅出，别以为Tom Nuydens是某个传奇人物，他22岁，也是刚刚大学毕业，真是不尽牛人滚滚滚来啊！
我的翻译：
我最近在看Computer Graphics ，搜到这个站，发现很有用，所以本着learning by doing && share && just for fun的态度翻译(欢迎指正)，并加上了一些我的理解和一些Expand（Maths ,some new figures etc.）。So，The Original Delphi 3D Engine Dev. Tutorial Series copyright by Tom Nuyden and this Translation and The Expanded Part copyright by John_Cash：）.(底下没标fig 的图都是我用画板画的，苦吧？：（，so, all rights reserved )
这是一个长达24篇的教程...长啊...
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
Issue 2 : Visibility determination algorithms（可见性判别算法）
可见性判别－－－3D Engine 的核心
什么是可见性判别？
3D绘制时要尽量避免重绘，如上图中六面体只有三个面可见，所以其余三个面绘制前应当删除（back face culling）。这只是简单的例子，想象一下，Quake中一关有多少面，要不用VD的话，即使是用硬件绘制也受不了，就能理解可见性判别的重要性了。
VD的策略选择会极大的影响Engine的效率。很明显，要是每一点都重绘的话，你的Engine就会花大量的时间画看不见的面，从而导致效率的损失；另一方面，要是你追求完美，连一点也不愿意重绘的话（software rendering 时这点的确很重要），你就要权衡VD算法和部分重绘的代价了。不仅仅是绘制需要考虑VD，在绘制前的视变换（viewing transformation，指从世界坐标系变换到用户坐标系）也很费时，就要尽量减少需要变换的面，当然我们并不需要变换那些看不见的面。
又很多种删除不可见多边形的方法。下面从最基本的开始讨论，后面会涉及到一些高级技术
Basic algorithms
剔除不可见多边形最直接，最简单的方法就是背面删除（back face culling）了。背面删除基于下面的假设：“多边形是封闭多面体的一个面，并且只有一面可见”。想象一下六面体的面，不可见的面有什么特点呢？――――该面的法线和用户视线夹角大于90度。可以用点积表示如图，当点积结果<0时，表示该面不可见。
下一步要做的就是，把你背后的那些面删掉。怎么删？在用户坐标下所有顶点Z<0的那些面。
还有要做的吗？当然。最后一步就是视见体（view frustum）删除了。
图中浅灰色的即为View Frustum，老外有时管这叫view pyramid，由六个四边形围成。其中深灰色三角形1，在view Frustum 中，不被删除，而2就需要被删了。具体判断使用平面方程：
S(x,y,z)=Ax+By+Cz-D
要是你线性代数还没忘的话，就应当能理解，（A,B,C）给出了平面法线，S（x,y,z）结果就是(x,y,z)点到平面的距离。OK，把待判断的多边形的所有顶点带入S(x,y,z)，根据正，负，0值，就可以判断其在平面外，内，上（这与多边形法线的定义有关），从而决定多边形是否被剔除。
注:要是你真忘了的话，我来推一下：
向量形式的平面可以记做：N*(X - P)=0 N为法线，P为平面任一点。
将X（x,y,z），N（A，B，C）带入，得：Ax+By+Cz=N*P。
其中*为点乘。
Octrees(八叉树)
上面的删除算法，效率还是不高的话，就要用到高级点的技术了。八叉树，本身是二叉树的3D版本。用来将空间递归的划分成立方体子空间（和BSP（Binary Space Partition）类似）。例如：（从z轴向下看）
如果可以确定一个子空间不可见的话，那该空间内的所有多边形就可以删除了。麻烦的是，对于可见的子空间内的多边形，Octree并没有提供可见性判别的方法（当然要是划分的太细的话，很可能得不偿失，递归，递规，…..，还想调试吗？）。另外，octree的划分方法很明显适合于直角坐标，你要是用几何坐标的话，可能没那么easy。：）
Portal rendering（入口）
什么是portal?
空间分割成凸多面体时，一个面切下去，有可能切空了。也就是说，这个面将原来的子空间一分为二时，没有切到多边形，这个面就成为一个portal。
图中，左右两个子空间就通过一个portal连起来了（和门的作用差不多）。右图说明，portal是一个不需要绘制的多边形，不阻挡视线。
Portal Rendering 比基本算法多做的就是view frustum 中多边形的删除。由于划分得到的子空间都是凸多面体，所以不存在多边形的排序问题（想象一下，站在一个凸多面体内，当然所有面的绘制顺序没有关系，因为所有面都可见）。算法从观察者所在的区域开始，绘制所有多边形，该区域若存在portal，将这个portal剪裁到视见体内，接着绘制该portal连接的区域。当两个portal相遇时，就需要将后一个剪裁到前一个portal中。如图：
当然，如果一个portal最终不可见，那么它连接的区域也就不可见了。
Dynamic LOD
地形绘制的Engine中常常用到Dynamic LOD(动态 Level of Detail)，用来简化远处的几何体的绘制。比如三角洲里边，远处的地形就会绘制的粗一些，随者你走近，地形就会越来越细致（三角形越来越多）。通常可以用octree来实现，如图：
(这张图来自：www.gametutorials.com)
另一种类似的技术叫：real-time tessellation 是指模型使用不同的精细度以适应不同的要求。
实际上，这两种技术都用于减少要显示的多边形数量（/质量），而非可见性判别。
Conclusion
这就是几种常用的算法，需要更详细的内容，可以去flipcode.com gamedev.net gamasutra.com gametutorials.com 看看。当然一个Engine 可以混用多种技术，比如BSP和octree的混合，octree和 portal 的混合，etc.。
下一次：Portal Rendering。（著名的《Duke Nukem Forever》永远的毁灭公爵 就用的是 portal Engine）。
