Develop Your 3D Engine
背景：
这是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）。
