岁月流转,往昔空明

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 3 Stories :: 413 Comments :: 0 Trackbacks
最近开始抽空在看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查找表需要很多的计算量,因此建议预先计算好并在运行前载入。该表在光盘上可以找到。

posted on 2008-05-20 20:38 空明流转 阅读(2095) 评论(2)  编辑 收藏 引用

评论

# re: 开个新的系列:GPU Gems 3 导读 + Chapter I 运用GPU构造复杂的过程化地形 导读(上) 2008-05-21 12:39 亨德列克
老吴,你太牛了  回复  更多评论
  

# re: 开个新的系列:GPU Gems 3 导读 + Chapter I 运用GPU构造复杂的过程化地形 导读(上) 2008-05-21 14:41 空明流转
@亨德列克
日。。。你他喵的又来风凉了。。。  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理