最近开始抽空在看GPU Gems 3了。本来想挑几篇全文翻译，但是无奈自己英语水平薄弱，同时最近老板逼得紧，也没有那么多时间，于是便准备以导读的形式，将文章的主干部分翻译出来,帮助英文不好的筒子们。
导读也是我自己读书的总结。文章的核心内容一定会提及.图和源码，通常我会标注上对应的图书上的figure和list，各位自行参考。基本维持原文的篇章段落，但是一般不会逐字句的考究。
至于能有多少篇，我倒是不能保证。不过我所用的电子版是那个26M的chm，我读的时候会把它翻成PDF并加注，如果有筒子需要我注释后的pdf，可以与我联系：
mail： wuye9036 _AAAAATTTTT_ google _dotdotdotdotdot_com
--------------------------------------------------------------------------------
Chapter I 运用GPU构造复杂的过程化地形
1.1 Introduction
过程化地形的应用已经有不少的历史了，Game Programming Gems 2上就已经有了不少成熟的过程化地形的方法，比方说随机断层、基于噪声的、基于分形理论的、中点分割加扰动的。
不过这些算法在现代硬件上都时有缺陷的，特别是针对规模很大的地形，要么只能在CPU上实时生成，要么就得预存储起来，但是不管怎么说都面临着很大的资源开销；其次这些算法都是只能生成有些起伏的平面，没办法表现山洞、岩石凸角一类的3D特征。本文运用DX10的Geometry Shader与Stream Output，弥补了上述两个缺陷。
1.2 移动立方体与密度函数
要解决3D的地形特征，首先要解决3D地形特征的表达问题。文中将空间划分为多个Blocks，每个Block代表了世界坐标系中1*1*1大小的空间。每个Block由一个3D纹理来表达。由于使用了过程化的方法，每个Block可以在运行的时候动态生成，这样只需要保留那些能看得见的blocks，从而解决了存储问题。
概念上，一个3D的地形可以由一个密度函数来表达。对于每个空间中的点(x, y, z)，都有唯一对应的密度值。我们假设，对于任意一个空间中的点，如果点在地形内部/岩石内部当且仅当点上的密度值大于0。那么小于0的点，自然就在地形之外，如在空气中，水中等等。而岩石表面上的点密度刚好等于0。
那么自然，这些岩石表面上密度值等于0的点，就是我们要绘制的“表面”。
在将空间划分为Block后，还要将每个block进一步细分为多个voxel（体素）。我们假定体素内密度变化时连续的。那么很显然，如果一个体素的顶点上密度有正有负，那么必然里面会有一个（也有可能是多个）0值面。问题就转化为，如何根据体素各个顶点的密度值，求出这个体素内的0值面。如果再把这个假设限定的严格一点，如果体素内密度变化是线性的，那么这些面可以由0-5个三角形来表示；求得这些三角形的方法，被称为Marching Cube算法。
很显然，有多少个三角形，每个三角形的顶点落在哪条边上，是由八个顶点的密度的正负值所决定的，而值的相对大小则决定了三角形的顶点在边上靠近那个顶点。那么也就是说，一个体素内0值面的分布共有2^8中情况。如果顶点密度为负，那么标记为0，顶点密度为正则标记为1，则八个顶点的情况可以由一个Byte来表示。
图1-3
如果这个字节的值为0或者为255，那么说明所有的顶点都为正或为负，那么说明体素中并没有地表面。Martin Frank为剩下的254中情况建立了一个查找表。其中基本的情形有14种，其余的均可由这些基本情况的对称或旋转求得。
图1-4
当确定了三角形的三个顶点分布于哪些边上后，便可用插值的方法求出所在位置。顶点将位于0值点处。例如，一条边AB上有一个0值点P，如果A的密度0.3，B的密度-0.1，那么PB的长度是PA长度的三倍。
1.2.2 查找表
上文已经提到了如何通过体素角点的密度值，就会知道会生成哪些多边形；这些多边形的顶点落在哪些边上。
接下来，我们将用讨论这些理论如何在GPU上实现。
首先我们建立一张查找表
int case_to_numpolys[256];
其中每种情况能产生多少个三角形。
第二张查找表，
int3 edge_connect_list[256][5];
这张表保存了每种情况对应的5个三角形。并且我们将一个体素中的12条边按照0-11编号（图 1-5），则查找返回的返回的int3指出了，每个三角形的三个顶点分别落在哪条边上。
图 1-5 Case 193 的0值多边形情况
下面的例子很好的说明了这一点。
我们以case 193为例。193总共有3个三角形，那么case_to_numploys[193] = 3，其次，edge_connect_list[193][]返回这样的结果：
int3 edge_connect_list[193][0]: 11 5 10
int3 edge_connect_list[193][1]: 11 7 5
int3 edge_connect_list[193][2]: 8 3 0
int3 edge_connect_list[193][3]: -1 -1 -1
int3 edge_connect_list[193][4]: -1 -1 -1
Geometry Shader在查找了这两张表的信息之后，并计算出顶点在边上的具体位置，便会返回3个多边形列表所需要的9个顶点。由于创建Marching Cubes查找表需要很多的计算量，因此建议预先计算好并在运行前载入。该表在光盘上可以找到。