程序设计

2ae8af3cdeb4.png

Hermite Curve 在绘制轨迹中的应用

0
2 years ago
by windam in

 

在3D游戏的粒子系统中，往往可能有这样一类需求——伴随着人的动作，一条光带划过，或者伴随着武器的劈砍动作，一条刀光划过。

如果我们简单的在每次Tick的时候采样当前的位置朝向，并创建一截新的面片，往往会形成类似于如下图的粗陋效果：

不连续轨迹

之所以会产生一截一截的感觉，是由于在每次进行采样的时候，我们只能得到当前时刻的位置信息。因此尽管在从上一次到本次采样的过程中，轨迹实际经过的路程是一条平滑的曲线，可由于每一帧之间的时间不可能小到足够提供平滑曲线的采样精度，我们所能获得的总是一截截的折线。

怎样才能够通过为数不多的关键点，创造出一条平滑的曲线来呢？

Charles Hermite 提出的Hermite Curve解决了上面的问题。通过一系列的三维空间关键点，可以得到每个点处的切线，再经过Hermite Base Function的多项式计算，则可以得到插值点。

如图：

HermiteCurve示意

设P1，P2为平面上的两个点，T1，T2为两点处的切线，由点及点的切线，Hermite Spline就可以给出一个平滑过渡的曲线。

Hermite Base 多项式的参数如下表，其中t是从上一个点到当前点的插值系数。上一个点处为0，当前点为1。

Ogre在其Ogre::SimpleSpline类中实现了HermiteCurve。感兴趣的同学可以做以参考。

 

  expanded factorized
h00(t) t3 − 3t2 + 1 1 + 2t)(1 − t)2
h10(t) t3 − 2t2 + t t(1 − t)2
h01(t) − 2t3 + 3t2 t2(3 − 2t)
h11(t) t3 − t2 t2(t − 1)

事实上，上述做法也不过就是对Hermite Curve类型的样条曲线的利用而已。样条曲线实际上并不陌生，贝塞尔曲线就是一种我们关注最多的样条曲线。尽管其不适用于我们前述的场合——原因是贝塞尔曲线通过控制点计算出的曲线并非一条依次经过控制点的曲线。如下图所示（图片来源于:http://escience.anu.edu.au/lecture/cg/Spline/printCG.en.html）：

bezier_spline 

参考资料：

1. Hermite Curve Interpolation. Hamburg (Germany), the 30th March 1998

2. Cubic Hermite spline

THREADINFO.jpg

windows的消息队列与消息循环#1

9
2 years ago
by windam in ,

在Windows操作系统中，窗口是一种User Object，隶属于创建它的线程。如果创建窗口的线程结束，则操作系统会自动删除窗口。建立窗口的线程，必须是为窗口处理所有消息的线程，如果你创建了一个后台线程，希望更新界面，那么只能通过消息的形式去通知窗口，并由拥有窗口的线程在窗口的消息处理函数中做出处理。

1、Windows的消息队列与消息循环

所有创建了窗口的Windows程序，都需要运行一个消息循环，我们在无数的Windows编程书籍中都可以看到这样的经典代码：

1:  while (GetMessage(&msg, hWnd, 0, 0) > 0)
2:  {
3:      TranslateMessage(&msg);
4:      DispatchMessage(&msg);
5:  }

这里的hWnd就是创建的窗口句柄，上述循环会不断的把该窗口(hWnd)相关的消息取出来，并分发到消息处理函数当中。

GetMessage函数是用来获取当前线程消息队列当中的消息的，其中的第二个参数如果传递一个窗口句柄，那么就会获取该窗口相关的消息，如果传NULL，那么会将线程消息队列中所有的消息都取出来。如果创建了多个窗口，而只对其中一个窗口句柄调用GetMessage形成消息循环，那么别的窗口都会毫无响应。

这里需要补充说明一个概念：消息队列是操作系统为每个需要处理消息的线程创建的，任何线程只要调用过与消息有关的函数（如，GetMessage，PeekMessage），操作系统就会为该线程创建消息队列。可能有人会问，那没有窗口的线程，操作系统也有必要为其创建消息队列么？这是有可能的，因为我们可以通过诸如PostThreadMessage的Api向别的线程或者本线程发送消息，如果目标线程没有消息队列，会导致这个函数返回失败。 (more…)

Win32平台下编译SVN源码全过程

5
2 years ago
by windam in , ,

前段时间曾经总结过一些在win32平台下基于SVN开发的一些注意事项，主要是在利用svn官方发布的二进制库进行开发过程中使用的方法和一些值得注意的问题。

 

由于svn官方发布的win32平台下的二进制文件是基于vc6编译的，在使用vc2005进行开发时，会遇到因CRT冲突而引起的link错误。因此，如果是使用vc2005（我推测使用VC2003也会遇到同样的问题，尚未验证）附带的CRT库与svn官方发布的binary进行link，那么无论如何都会出现crash的问题。最为彻底的解决方案，还是自行编译svn源码。

 

在win32下编译svn源码说明：

 首先需要从官方下载一份SVN源码，版本可以根据需要选取，比如最新的Release 1.6.3(目前已经更新到1.6.6)可以在这个地址下载到：

http://subversion.tigris.org/downloads/subversion-1.6.3.zip

以及svn所需的依赖包：

http://subversion.tigris.org/downloads/subversion-deps-1.6.3.zip

如果需要支持ssl的话，还需要下载openssl（根据实际需要选择相应版本）：

http://www.openssl.org/source/

如果需要BerkeleyDB的话，需要下载WindowsBDB(BDB是可选的，如果不使用BDB，则默认使用FSFS)：

http://subversion.tigris.org/servlets/ProjectDocumentList?folderID=688&expandFolder=688&folderID=2627

此外还有Windows libintl：

http://subversion.tigris.org/servlets/ProjectDocumentList?folderID=2627&expandFolder=2627&folderID=8100

 

 

解压svn源码包，可以在subversion-1.6.3目录中找到这么一个官方发布的说明文件INSTALL。该文件详述了安装通过源码编译SVN所需依赖的工具及第三方库，并且给出了详细的步骤。

网上同样有一个INSTALL的说明，可以在这里访问到:

http://svn.collab.net/repos/svn/trunk/INSTALL

 

编译开源项目的话，其附带的INSTALL说明都是最重要也是最全面的参考。网上搜索的其他资料，也会有相应的参考价值，但无论如何，其信息的来源也是INSTALL。因此编译开源项目时，认真阅读INSTALL是最重要且效率最高的。

 

从Google上进行一下简单的搜索的话，可以找到一篇介绍svn源码编译的文章，在这里：http://rocksun.cn/?p=103

 

为了后续的步骤方便，我们需要先准备编译所必须的一些东西：

包括Perl：http://www.activestate.com/activeperl/

Python：http://www.python.org/download/

 

 

安装Python以及Perl，比如分别安装到D:\Python26以及D:\Perl。安装好之后，将python以及perl的bin目录设为系统目录并重新启动使之生效。

 

编译svn源码第一步，将下载的svn源码包解压到X:\SVN\svn—trunk下。X可以是任意一个盘符。在我的机器上，我使用了F盘，下文中皆以F盘举例。

 

在F:\SVN\svn-trunk中解压了刚才下载的svn源码包以及依赖之后，可以在目录

F:\SVN\src-trunk\subversion-1.6.3中看到以下文件及目录：

以及文件：

Svn的编译需要依赖libapr以及libapr-util，SQLite，zlib，libintl可选，libneon/libserf二则择一，openssl可选，BerkeleyDB可选，libsasl可选，对Python,Perl,Java,Ruby支持的模块可选，以及KDELibs,GNOME Keyring可选。

 

我们依次先编译依赖项：首先进入到subversion-1.6.3\apr目录中。可以看到存在apr.dsw以及apr.dsp文件，这是VC6的工程文件。我们如果想在2005下编译的话，需要将其转换成sln及vcproj文件，简单的用vc2005打开该文件并保存即可。该目录下还有Makefile.win文件，是win下的makefile，我们打开makefile.win文件查看一下说明：可以得知如果需要编译.sln文件的话，需要置USESLN=1。

 

在VC2005的命令行中输入nmake -f makefile.win buildall checkall USESLN=1便可以开始编译apr了。Checkall表示编译完成后会去运行所有的测试用例。

 

编译完成后，当前目录下会多出2个文件夹，分别是LibR – StaticRelease，Release – DllRelease。如果选择Debug编译，则会生成LibD – StaticDebug， Debug – DllDebug。

 

类似的，我们将apr-util以及apr-iconv也编译好。

 

编译zlib：

进入zlib目录后，使用以下命令编译zlib库

nmake -f win32/Makefile.msc

 

编译openssl：

将此前下载的openssl解压到F:\SVN\openssl

阅读其INSTALL文档（INSTALL.W32）

使用VC编译openssl首先需要运行configure：

perl Configure VC-WIN32

接着运行

ms\do_masm

这里的do_masm是一个bat脚本，该脚本会生成nt.mak以及ntdll.mak分别是Release版本的静态和动态的库的make文件。如果想生成debug版本的make文件，可以通过修改do_masm.bat中的调用mk1mf.pl脚本处的参数实现，具体参数可以参考mk1mf.pl文件自身的说明。

接下来，创建动态链接库版本的ssl库用nmake -f ms\ntdll.mak，以及静态版本使用：nmake -f ms\nt.mak

生成的结果文件位于out32dll文件夹，以及out32文件夹中。

 

编译neon

进入F:\SVN\src-trunk\subversion-1.6.3\neon目录

nmake –f neon.mak

默认生成的是release版的libneon.lib (debug版为libneonD.lib)

可以用nmake –f neon.mak DEBUG_BUILD=1生成debug版的lib。

 

回到F:\SVN\src-trunk\subversion-1.6.3

运行python gen-make.py –help可以了解如何使用gen-make.py生成我们所需的svn编译文件。

由于在此，我打算选用neon, libintl, openssl(本例中并不打算使用BDB，如果需要BDB则需要增加—with-berkeley-db=DIR参数)进行编译，目前需要关注的几个重要参数如下：

–with-apr=DIR

–with-apr-util=DIR

–with-apr-iconv=DIR

–with-neon=DIR

–with-libintl=DIR

–with-openssl=DIR

–with-zlib=DIR

–vsnet-version=VER

 

运行

F:\SVN\src-trunk\subversion-1.6.3>python gen-make.py -t vcproj

–with-apr=apr –with-apr-iconv=apr-iconv –with-apr-util=apr-util –with-libintl=svn-win32-libintl –with-openssl=..\..\openssl –with-zlib=zlib –vsnet-version=2005

 

(其中的libintl需要解压到当前文件夹中)

即可生成vc2005的sln(subversion_vcnet.sln)文件了。

 

打开vc2005，选择Debug编译选项，对项目ALL进行编译。如果一切顺利，则会生成一个F:\SVN\src-trunk\subversion-1.6.3\Debug目录。内容包括svn的所有的lib及可执行文件。

将svn\svn.exe以及所有目录下的.dll文件拷贝到一个新建的bin目录下。将openssl的dll，apr, apr-util, apr-iconv的dll拷贝到同样的bin目录下，如下图：

运行svn –version看看结果吧～

 

最后，当我们有了自行编译的svn可以做什么？你可以做任何你想做的事——比如自己基于svn的接口进行开发（可以参考开源项目rapidsvn以及TortoiseSVN的源码）

编写一个DLL时应当注意什么#1

6
2 years ago
by windam in ,

库与代码重用

1、静态库vs动态库

静态库的优势和劣势

动态库的优势与问题

2、静态C/C++运行库 vs 动态C/C++运行库 & manifest

3、关于动态库接口设计

库与代码重用

对于像C，C++这样的语言来说，库是扩展语言功能的重要手段，对于项目来说，代码库是节约开发时间，缩减成本，划分项目模块以利于多人合作，并通过重用已有代码而避免重复劳动的必要工具。开发一个稍具规模的项目，总免不了设计和划分模块，如何设计和划分，采取什么方案解决问题，总要面临诸多取舍。

最近跟动态库/静态库/动态静态CRT/MFC打了诸多交道。本文是对这段时间遇到的问题与思考的总结。

1. 静态库 vs. 动态库

静态库本质上就是编译好的目标代码(使用vc的话，编译.cpp文件或者.c文件之后会得到目标文件.obj，编译结束后，link程序会按照指定的要求将目标文件链接成最终的输出文件——常见的有.lib/.dll/.exe)的一份合集。

相比于动态库，静态库没有入口函数，不能独立执行，不能动态链接，一旦被链接到目标文件中，静态库的代码段/数据段都会被合并到目标文件当中去。这是静态库与动态库的本质区别。

由于上述差别，那么我们就很容易理解下面的情况：如果你在静态库中定义一个静态或全局对象，最终该对象会被链接到目标文件的数据段中（目标文件可能是某个dll也可能是exe）。

静态库的优势在于，简单易用，你无需考虑内存的申请与释放问题，因为静态库的代码段作为目标模块的一部分（EXE或DLL），在其中所调用的new/delete在链接阶段会被重定位到该目标模块的CRT函数地址。

对应的，如果你使用DLL，由于DLL中会自行初始化一份CRT堆，因此它的内存申请与释放是在有别于在EXE的CRT堆中进行的（两个不同的CRT堆），如果你从DLL中申请一块内存出来使用，最后也必须交还给DLL模块内部去释放。否则会产生Heap Collision，在Debug模式下，你会收到一个系统位于malloc中的断言，并了解到发生了什么。*

此处的叙述存在错误，更正如下：

一个DLL或许会，或许不会拥有一份自行初始化的CRT堆，这取决于DLL是通过动态链接MSVCRT还是静态链接LIBCMT。由于CRT是通过一个全局变量_crtheap维护着一个Heap（Windows环境下），并且会在CRT初始化的时候初始化CRT堆，因此，如果整个应用程序都是通过链接动态的msvcrt，使用同一份crt，则不会有问题。但是如果有任一二进制模块链接了静态crt，则会拥有一份自己的crt堆。严格来说，你应当小心的保证来自于某个CRT的堆内存最后也被交还给该CRT堆，否则会发生错误，在Debug模式下，当你调用free函数释放来自于另一个CRT堆的内存时，会有一个_ASSERTE(_CrtIsValidHeapPointer(pUserData));断言失败，提醒你用错了堆。

如果我们的DLL是链接了一个静态的CRT并且发布出去了，那么我们还是应当保证所有来自于该DLL的内存都由该DLL回收。其原因如上述分析所言，是由于该DLL拥有一份自己的CRT堆。

 

再有，如果你的静态库A依赖于静态库B的头文件，而目标应用程序EXE依赖了静态库A，那么你在链接静态库A的时候，也必须链接静态库B。否则会有静态库A中的某些符号无法被找到，从而导致链接失败。而动态库A如果依赖于一个静态库B，那么你无需在依赖该动态库的EXE中再次包含该静态库，因为该动态库A已经将该静态库B链接到A模块当中了，在DLL A中已经有了一份，如果EXE模块没有直接依赖于静态库B的话，那么就无需在EXE中再次link该静态库了。

上述问题也通常是混用静态库和动态库时可能遇到的一个问题：如果有一个静态库A，被动态库B和EXE C都用到了，而EXE C又需要使用动态库B，那么这份A的代码和全局数据就在动态库B和EXE C中存在了两份。第一，这是一种对空间的浪费；其次，这可能会引发问题，比如，当我在EXE C中new一份A中的某对象X的指针，并将该指针传入到动态库B中使用，表面上看似乎没有问题，但是如果这个对象X引用了A库中的全局/静态数据，就可能会引发问题，因为此时动态库B中存在有一份A库中的全局/静态数据，而EXE C中有另一份，如果这个全局/静态数据被X使用的话，那么就会得到前后不一致的上下文环境。具体可能产生什么问题要看具体的逻辑是如何组织的。在这种情况下，最好能将静态库A重新组织成一个动态库，这样就不存在多份代码以及多套全局数据的问题了；如果不能这么做，你可以根据具体的应用程序组织的形式，采取DLL导出A库接口，EXE使用DLL导出接口去访问A库而不直接链接A库本身的方法来变通，但通常这不是根本的解决方案。

另一方面，在DLL中可以包含自己的资源文件，而LIB中不能。因为DLL是一份完整的PE文件，而LIB只是若干个OBJ打包。这并不是说，使用LIB的时候不能使用资源(RC)，你可以将LIB中使用的RC文件，resource.h都include到目标应用程序当中，只要没有资源ID冲突就可以正常使用，就像是你在目标应用程序的资源当中定义了这些资源一样。而DLL中的资源则隶属于DLL自身，不会与EXE中的资源在ID号上产生冲突，只是在使用的时候还需要针对Resource做一些Handle上的设置（参考AfxSetResourceHandle），才能使得API访问DLL中的资源而非EXE中的。如果要编写一个带有资源的库模块，DLL确实是不二选择。

2. 静态&动态C/C++ runtime 以及 manifest

静态的C-runtime库叫做LIBC.lib，我们通常使用多线程的版本叫LIBCMT.lib，debug下的版本叫LIBCMTD.lib。而动态的C-runtime，在VC的环境下，我们使用的是MSVCRT.lib，以及debug下的MSVCRTD.lib（这两个lib实际是两个导出符号文件，实际的运行库位于msvcrt.dll/msvcrtd.dll中(VC6)，如果是VC2005的版本则是msvcr80.dll/msvcr80d.dll）

C++的runtime库，静态版的是LIBCPMT.lib/LIBCPMTD.lib。动态版的是MSVCPRT.lib以及MSVCPRTD.lib。（类似的，实际的运行库位于<VC2005中>msvcp80.dll/msvcp80d.dll）

在第一点的对比中已经提到过，如果同时又DLL模块依赖一个静态库，而又有一个依赖该DLL模块的EXE还依赖这个静态库，那么最终的内存中就会存在两份该静态库的代码以及全局数据。这一点对于C/C++运行库也是一样的。所需要注意的是，只要是基于C语言以及C++语言的程序，几乎所有的都会用到C/C++运行库，因此如果在规划一个项目的时候，发现有多个dll模块，那么最好是使用动态版的运行库，以避免最终的内存中出现多份不必要的运行库代码。

再有一点是关于XP之后的系统中，以及在VC2005之后的编译环境中，微软添加的manifest机制。该机制是为了解决同名但版本错误的DLL加载问题而提出的。比如，我们手上有两份VC编译器，分别是不同的版本，其中携带的MSVCR80.dll也是不同的版本，但是都叫MSVCR80.dll，如果我们在应用程序安装时，简单粗暴的将系统目录下替换成我们应用程序所依赖的MSVCR80.dll，那么可能会造成以往的应用程序无法正确运行的问题，因为他们可能依赖的是其他版本的MSVCR80.dll。

解决这个问题的途径是将一个dll的运行环境，版本，以及校验值等信息编码到一个目录名当中，而在安装应用程序时，将该版本的dll放置到对应名字的目录下，这样尽管dll名称一致，我们也可以找到所需要正确版本的dll。但是应用程序怎么知道需要依赖哪个版本的dll呢？如果应用程序不知道，即使系统中有正确版本的dll，操作系统也不知道应该去加载哪一个dll。

因此manifest文件就把该模块所依赖的模块都标明了，通过名称，校验码，版本等等信息以确保所指明的模块不会有歧义（用记事本打开一个manifest文件，你就可以看到上述信息），当该应用程序EXE或者DLL被操作系统加载时，系统就会根据该信息去查找对应模块，首先会在C:\Windows\WinSxS目录下找（打开这个目录，你就能看到大量不同版本的CRT/CPRT/MFC/ATL等等运行库），如果没有找到那么也会应用程序当前目录下找。

这就是为什么使用VC2005编译一个dll也好，一个exe也好，总会多生成一个manifest的文件的原因。所以如果使用了动态版本的CRT运行库，或者其他任何DLL，那么最好就不要关闭manifest生成的编译选项。

3. 关于动态库接口设计

如果动态库可能经常会更新版本，提供新的功能接口，那么如果使得动态库的升级无需改动依赖于他的可执行模块就是一个值得思考的问题。

具体要达到上述目标，需要保证的有以下几点：

a. 动态库中的类的内存布局不暴露给外界，也就是说动态库提供给用户的.h中，不应当有类的成员信息。这是因为，如果类的内部数据修改了，增加了一个变量或者减少了，那么这个类所占用的内存大小也就修改了，倘若有exe使用上一版本的类定义，new了一个类对象，那么一旦发生类定义修改的情况，这部分代码就必须要重新编译链接了。比较标准的做法是dll只向外界提供接口定义，而不提供实现定义，即提供的是一个类，但是类中只包含纯虚函数，而没有数据<这种做法有点类似于COM的思路>；或者是只提供一系列普通函数以及一个实现类的指针，这种做法有一个好处，如果添加新的函数接口，也无需重新更新外部程序，但是如果使用虚函数接口则不然。

b. 动态库中的类应当不给外界提供构造析构的能力，同样是基于上述原因，如果外界可以new/delete该类，那么当类的定义修改时就会出现不得不重新编译使用该库的应用程序的情况。倘若只通过dll中定义好的借口进行交互，则不存在这个问题。比如外部不能直接new一个对象，而是必须从一个dll导出函数中获取一个对象的指针，外部同样不能delete这个对象，而是必须将之送入另一个导出函数交给dll去删除。这样只要dll保持着两个接口不变，更新dll时是无需更新依赖该dll的应用程序的。（一个比较好的做法是将dll提供外界的接口类的构造析构函数设置为private）

c. Dll应当尽可能使用动态crt，如果用到了mfc应当尽可能使用动态mfc。这是为了避免dll与外部模块中存在多份重复代码的情况。同时如果有dll需要依赖的其他静态库，也应当尽可能使用该库的动态版本。

p.s. 如果想了解更多的关于静态库，动态库，C运行库方面的知识，可以参考《程序员的自我修养——链接装载与库》一书。

p.s.2 果然如pongba老大所言，将自己认为没有问题的知识写下来是一次很好的学习过程，写下本篇文章的过程中，我将原先认为明白的，但是实际并不见得就真的明白的问题，梳理清楚了很多。写的过程有助于把原先大脑中下意识存在的假设显现出来，在思维中再次加工，将原先不明确的概念搞清楚。

 

#1 更正了关于DLL与CRT堆内存的一处错误，感谢coldfall热心指正

3D地形学习笔记1–地形生成

0
2 years ago
by windam in

地形生成是一个很有意思的话题，通过简单的函数以及一些参数配置，就可以轻松的生成接近于自然地貌的地形。

 

两种众所周知的地形生成算法分别是

1、  Fault Formation

2、  Midponit displacement (又名diamond square)

 

Fault Formation 算法

这个算法的本质其实很简单。想象一个方块，在这个方块中随机取一个点为起始点，再随机选择一个方向，形成一条射线，然后将高度图中这个射线左侧（或者右侧）的部分全部添加一个Delta。重复上述步骤若干次，每次将添加的Delta减小一些，一个简单的高度图就可以生成出来了。

Delta应当与当前迭代次数与总迭代次数的比值成线性关系。

Delta = MaxHeight – (MaxHeight – MinHeight) * CurrentItr / TotalItr;

这样第一次迭代所产生的影响最大，而后的迭代中对整个高度图的影响依次递减，在之前的高度基础上继续增加高度图中的细节。通常来说，迭代次数越多，效果会越好。

 

实现FaultFormation的伪码如下:

 

Do_Formation(float* pfBuffer, int iLen, Point ptStart, Point ptEnd, float fDelta)

{

         Point ptDir = ptEnd – ptStart;

 

         For (int z = 0; z < iLen; ++z)

                   For (int x = 0; x < iLen; ++x)

                   {

                            Point ptDirCur = Point(x – ptStart.x, z – ptStart.z);

                            // 直线方程，判断一个点位于直线的上方或下方

                            If (ptDirCur.x * ptDir.x – ptCurDir.z * ptDir.z > 0)

                                     pfBuffer[z * iLen + x] += fDelta;

}

}

 

Proc_Fault_Formation(float* pfBuffer, int iLen, int iMinDelta, int iMaxDelta, int iIterationTimes)

{

         for (int iCurIteration; iCurIteration < iIterationTimes; ++iCurIteration)

         {

                   float fDelta = iMaxDelta – (iMaxDelta – iMinDelta) * iCurIteration / iIterationTimes;

                   Point ptStart = randomPoint();

                   Point ptEnd;

Do

ptEnd = randomPoint();

                   While (ptEnd == ptStart);

                   Do_Formation(pfBuffer, iLen, ptStart, ptEnd, fDelta);

}

}

 

按照上述思路实现的高度图生成算法，产生的图片如下：

迭代1次及32次时的效果：(为了区别背景色，我给图片增加了1像素的边框)

 

 

 

 

 

 

 

 

 

但是如果我们直接用这张图做地形的话，会遇到一个问题。地形的高度变化的边缘部分太过突兀了。我们需要增加一个模糊的步骤用以平滑高度突变(模糊可以采用任何一种模糊算法，比如常见的高斯模糊-有关高斯模糊的内容参考本文的附录)。

 

下图为增加了模糊处理，迭代32次的高度图。

 

使用Fault Formation算法生成地形的一个好处是分辨率不受限制，我们可以设置任意宽高的高度图。但是缺点是生成的地形细节往往不够丰富，不足以模拟大规模的地形场景。

 

Mid-point displacement算法是一种过程生成机制，特别适合用于生成较大规模的地形场景。

一篇很全面的介绍Mid-point displacement的文章可以参考 这里

关于Mid-point displacement的原理也可以参考 这里

 

单纯从算法上来看，Mid-point displacement所做的事情是很简单的：

该算法只能生成边长（一条边上的顶点数目）为2^n + 1的高度图。为什么有这个限制？原因是这个算法必须要以一个正方形为一个递归单元，每次处理完一个正方形后，都必须将其划分为4个更小的正方形加以处理。只有2^n + 1边长的正方形才能满足此切分条件。(2 = 2^0 + 1, 3 = 2 ^ 1 + 1, 5 = 2 ^ 2 + 1, 33 = 2 ^5 + 1, 1025 = 2 ^ 10 + 1 以此类推)

Midpoint displacement算法又名Diamond-square算法。该算法分为两个步骤：Diamond-step及Square-step。

 

算法的初始，我们需要给地形的四个角的顶点赋初值。这个值可以指定，或者随机产生。

如上图，四个角的值已有，为0, 2, 4, 8。而后，我们需要计算中点的值，图示中的3.5点的位置即为该图的中点。

中点值通过将四个角做算术平均，并增加一个小的随机值得到，随机值可以为正也可以为负。

上述步骤被称为Diamond-step。

接下来，我们只需要根据已有的四个顶点处的值，计算四条边的中点的算术平均值即可。

这一步被称为Square-step。

完成上述步骤之后，我们得到了四个更小一级的方块，分别对这四个方块重复上述步骤，直到当前块的边长为2时即可结束。

 

实际实现中，我们需要对所做的Displacement操作（即给中点附加一个随机值的操作），在每次迭代中，将随机的范围跟随当前边长逐步缩小。这样可以保障最终的高度图是逐步收敛并趋于稳定的。

 

该算法的实现伪码如下：

 

Displace(float cur_len, float total_len)

         Return (rand(0.0f, 1.0f) – 0.5f) * cur_len / total_len * 1.5f;

MidpointDisplacement(float* pfBuffer

, int x

, int y

, int len

, int pitch

, float top_left

, float top_right

, float bottom_left

, float bottom_right)

{

         Float mid_top, mid_left, mid_right, mid_bottom;

         Float middle;

         Int new_len = len / 2;

         If (len == 2)

         {

                   pfBuffer[y * pitch + x] = top_left;

                   pfBuffer[y * pitch + x + 1] = top_right;

                   pfBuffer[(y + 1) * pitch + x] = bottom_left;

                   pfBuffer[(y + 1) * pitch + x + 1] = bottom_right;

                   return;

}

 

Middle = (top_left + top_right + bottom_left + bottom_right) / 4 + Displacement(len, pitch);

Mid_top = (top_left + top_right) / 2;

Mid_left = (top_left + bottom_left) / 2;

Mid_bottom = (bottom_left + bottom_right) / 2;

Mid_right = (top_right + bottom_right) / 2;

 

         Clamp(middle, 0.f, 1.f);

         MidpointDisplacement(pfBuffer, x, y, new_len, pitch, top_left, mid_top, mid_left, middle);

         MidpointDisplacement(pfBuffer, x + new_len, y, new_len, pitch, mid_top, right_top, middle, mid_right);

         MidpointDisplacement(pfBuffer, x, y + new_len, new_len, pitch, mid_left, middle, bottom_left, mid_bottom);

         MidpointDisplacement(pfBuffer, x + new_len, y + new_len, new_len, pitch, middle, mid_right, mid_bottom, bottom_right);

 

}

 

使用上述算法所得的高度图如下：

 

左图是未经过模糊的版本，颗粒状比较明显，如果在实际的地形中，会导致凹凸感较强的失真情况，右图是经过模糊的版本。

 

参考文章：

Focus on 3D Terrain Programming (Trend Polack)

http://gameprogrammer.com/fractal.html

 

附录：关于高斯模糊

http://en.wikipedia.org/wiki/Gaussian_blur

 

二维高斯模糊的方程如下：

上述方程，用于通过制定的参数构造一个高斯滤波器（高斯滤波器是一个低通滤波器，会滤除信号中的高频部分–通俗的说就是突变较大的部分），该滤波器本质上就是一个R*R的矩阵，以该矩阵的中心点为原点，对矩阵中的每一个点(x,y)，将其值赋为G(x,y) ，则在该矩阵即被构造完成。

 

理论上说，高斯矩阵的所有项之和应当为1。

Wiki中给了一个当(with σ = 0.84089642)，R为7时的参考高斯矩阵：

 

0.00000067 0.00002292 0.00019117 0.00038771 0.00019117 0.00002292 0.00000067
0.00002292 0.00078633 0.00655965 0.01330373 0.00655965 0.00078633 0.00002292
0.00019117 0.00655965 0.05472157 0.11098164 0.05472157 0.00655965 0.00019117
0.00038771 0.01330373 0.11098164 0.22508352 0.11098164 0.01330373 0.00038771
0.00019117 0.00655965 0.05472157 0.11098164 0.05472157 0.00655965 0.00019117
0.00002292 0.00078633 0.00655965 0.01330373 0.00655965 0.00078633 0.00002292
0.00000067 0.00002292 0.00019117 0.00038771 0.00019117 0.00002292 0.00000067

 

 

高斯模糊的过程就是对原图像的每一个像素点，将上述矩阵的中心点对准该像素点，并以矩阵中的值为系数，将原图像上的位于当前矩阵范围内的像素点的值，乘以对应矩阵项的系数，并求和，而后重新赋予当前像素的过程。

 

模糊的过程较为简单，但是需要注意的是边界情况处理，当处理高斯矩阵的部分项超出原图像边界时，需要做一些特殊处理，以保障边界处的模糊是平滑的即可。

 

p.s.接下来的目标是整理一下地形渲染中纹理，光照，以及LOD的内容。

Go to Top