如何开始研究？－－ 图形学相关的库介绍
jingwenlai 2010-4-29

以下列出一些我在学习过程中碰到过的库及其相应的介绍，希望对刚入门的师弟师妹有一个大体的印象。 如果你觉得我有些说得不准确的地方，请及时帮忙指正，谢谢。

图形学大体上可以分为两类：一类是建模，一类是渲染

* 建模
现在我们所做的数字几何处理(Digital Signal Processing)大体上都是在做建模这一类，不管是做模型分析还是模型编辑。对于模型，我们首先需要了解它的数据结构。
** 数据结构：
我们所处理的模型大部分情况下是大家通常所说的mesh，实际上其是由点、线、面所组成的一个物体（如果大家有用过maya/3dsmax之类的软件的话，在framewire渲染模式下，可以看得比较清楚）。如何对这些元素进行组织，就得需要底层的数据结构的支持，而这些数据结构有很多种，现在大家最常用的是一个叫做“半边结构”（Halfedge）的数据结构，在这里有关于它的最初始的介绍http://www.holmes3d.net/graphics/dcel/， 在CGAL库中实现的Mesh结构也是半边结构，大家可以看它的Manual中的Polyhedral那一章。OpenMesh中实现的Mesh数据结构同样也是半边结构。 CGAL或OpenMesh对于Mesh部分提供的功能都差不多，所不同的只是其API的使用方式。 还有一些比较小众的库，如trimesh2

有了数据结构，就可以在上面做很多分析或者操作，比如简化，细分，分析模型的特征等。在这里，我们需要对数据处理的结构或模型用可视化的方式直观地显示出来，所以，也就引出了我们需要使用的图形API： OpenGL/DirectX
**图形API: OpenGL/DirectX
我们需要图形API的原因是想把我们对模型的处理结构及模型用可视化的方式直观显示出来，这就需要我们学习OpenGL或DirectX的使用，现在我们组使用的大部分是OpenGL,好处是可以跨平台，而且学习资源丰富。当然，现在有一些库对两者进行封装，提供统一的接口以供使用，其中最出名的算是OGRE. 但是我们所需要的大部分是对点线面的原子操作，大高层的库反倒不好用，所以大部分情况下还是用底层的API

好了，有了API，但是API只是接口，我们需要一些东西来承载它，因此也就需要界面库，因为整个OpenGL/DirectX其需要Context(上下文)来对它进行初始化。
** GUI
这里的界面库包括以下几类：一类是大部分介绍OpenGL编程的时候都会介绍的GLUT,一类是更丰富一点的MFC, Qt之类。CGAL官方出的subdivision tutorial中使用的界面是MFC, 熊老师在它的基础上扩展了很多，已经加入了很多他的算法。另外，Kobbelt那一组的Mario等人在SIGGRAPH 2007/2008, Eurographics 2007都出过course notes,包含十多章的PDF（基本上每一章是一个算法）以及一个源代码的打包文件，它里面使用的是GLUT，灿江当时做的时候是从那个上面开始扩展的。而我挑的是一个比较偏的叫FLTK的GUI库，上手会比较快，但当程序大了之后，比较难维护，现在开始往Qt那边转了。
我个人觉得比较好的学习方法是挑一个自己喜欢的不算太大的程序（如CGAL的subdivision tutorial或OpenMesh的SIGGRAPH 2007/2008 course notes中附带的程序）， 先把它整个程序流程弄懂，然后再在那个基础上慢慢扩展自己的算法。

熟悉了上面这三种类型的库之后，基本上就可以开始做事了，你可以针对你自己所想要实现的算法查找相应的资料，这里我主要给出我接触过的有关数值求解那部分的库。
** 数值求解
需要数值求解的原因大部分是因为近年来有关模型编辑（mesh editing）方面的内容，都会涉及到大的稀疏矩阵的求解，它底层的主要是一些向量与向量，向量与矩阵，矩阵与矩阵之间的操作
＊＊＊CPU方面：
最早的这方面的库是BLAS,LINPACK这一类库。这一类型的库比较底层，所以后面有许多人给出类似的实现，但是更高层一些（即面向程序员更易用）：
1.Intel 的MKL: 这个库在浙大有人用（08年大连开会认识的浙大的赵勇用得是这个）， AMD也有相应的实现叫acml，但是好像使用的人不多。
2.另一阵营则是学术界自行实现的了，其中一个是现在在论文中引用数较多的taucs, 另一个是http://www.cise.ufl.edu/research/sparse/ 介绍的其它库，包括UMFPACK, CHOLMOD
其性能的对比可参见《Experiences of Sparse Direct Symmetric Solvers》，《A Fast Multigrid Algorithm for Mesh Deformation》，这类型的数值求解库比较多，但是只需要选一个就可以了。
3.还有一种方法我值得可以推荐的是借用matlab, matlab可以用于难证上述的库求解的正确性，或者如李琳那样使用matlab提供的api, 直接把需要求解的过程交给matlab,然后把matlab求解出来的结果再在自己的程序中使用。熊老师在这方面做得工作更多，有一次听他说他后续的有关数值求解（如特征值特征向量等）的求解全部交由matlab处理，这种方式的优点是使原型开发更快，而且专注于更关心的内容，缺点可能是性能方面。这种方式我个人现在比较推荐，可以等算法实现稳定后，再考虑性能优化的问题。

***GPU方面:
现在随着CUDA的流行，CUDA中提供了cuBlas,提供一些基本的与BLAS相对应的操作，现在后续地基于它的数值求解算法也有人在做，速度会比CPU的快。
这部分目前了解不多

* 渲染
渲染这一部分，我看得不多，一般来说我觉得分为两派，一派是追求尽可能的真实还原真实世界的场景，这一部分包含的算法包括Raytracing, radiosity等，另一部分则追求non-photorealistic（非真实）, 其中有一些是希望利用算法判断模型特征然后勾勒出一些轮廓，有一些是希望做出漫画效果，上一次灿江发的2010做视频实时渲染成水彩画的我想也属于这一类。

学习的过程中走过一些弯路，希望本文对你有所帮助。

  一些开源人士真的为图形学或者3d游戏发展做了很多无私的贡献，OGRE，IRRLicht，CEGUI一系列3d图形渲染引擎和游戏引擎，还有Opengl,VTK，CGAL这些工具库。由于兴趣和工作的缘故要安装上面一些，可是悲剧的是上面不少光是安装就让我晕了一两天。发现写了几年程序，连vs中基本设置都不懂。决心弄清楚vs中一些常用选项，网上找了下发现相关资料很少，估计我这种菜鸟才会去问这种问题。不管了，请教了子豪和李闻师兄后终于弄清了几个选项。

（1）Output directory:输出文件的路径，也就是我们要生成的exe所在的文件夹，vs中默认是$(SolutionDir)\$(ConfigurationName)。其中SolutionDir路径一般为与sln同名的文件夹中，或者说是vcproj所在的文件夹。至于$(ConfigurationName)即为当前configuration的模式，debug或release。
（2）Output file:即是要输出的文件比如exe，一般默认为：$(OutDir)\$(ProjectName).exe，其中OutDir即为上面定义的Output directory（vs默认$(SolutionDir)\$(ConfigurationName)）。
（3）Intermediate directory:中间文件夹，我对它唯一了解是系统（编译器，连接器？）会在这个文件夹寻找执行exe所需的额外dll。
（4）work directory:作用和Intermediate directory有点像，系统（编译器，连接器？）会在这个文件夹寻找执行exe所需的额外dll。它还决定了我们exe调用一些文件的当前路径。比如我们代码中要读入一个数据txt文本或一些模型，例如 smgr->getTxt(“sydney.txt”)，那么系统就会默认syney.txt在work directory中并去寻找。
（5）c++->general->additional include directories:这个不说很多人也知道了，相当常用的选项，包含头文件。编译使用一些开源软件时，使用其关键一步就是在这个选项中把开源软件那些include包含进来。
（6）linker->general->additional library directories：和上面差不多，相当常用的选项，编译使用一些开源软件时，把它们的静态库包含进来。
  上面不少选项都是vs中默认，对于一些开源软件的路径配置具体要看makefile。但是我对makefile不熟悉。学习学习再来分享。
  所以一般的开源软件安装虽然需要下载相应的依赖库放到相应的位置，或者需要cmake之类的，但是最后使用的时候无非把动态库，头文件，静态库各归其位就好了。

1. shape editting

http://www.dgp.toronto.edu/~rms/#Publications

2. premultiplied alpha.

http://keithp.com/~keithp/porterduff/p253-porter.pdf

CEGUI是OGRE推荐的UI，很适合在三维游戏中使用的一个不错的UI。其安装应该是比较简单的，但是我比较菜鸟，按照其准官方的安装方式还是出了一点问题，特拿来分享下，如果大家遇到类似问题可以解决。

先是准官方的安装过程。

1. cegui 0.7.1的下载地址：http://prdownloads.sourceforge.net/crayzedsgui/CEGUI-0.7.1.zip?download
2. cegui 0.7.1依赖库的下载地址：http://prdownloads.sourceforge.net/crayzedsgui/CEGUI-DEPS-0.7.x-r1-vc9.zip?download
3. 将cegui解压，建议将解压后生成的cegui目录改名为对应的版本号，例如：F:\SDK\cegui-v0-7-1，以区分各个版本
4. 将依赖库解压到cegui的目录中，例如：F:\SDK\cegui-v0-7-1\Dependencies
5. 进入目录F:\SDK\cegui-v0-7-1\projects\premake
6. 用记事本打开目录下的config.lua，找到两个变量：OGRE_PATHS和OIS_PATHS
7. 将其修改成对应的ogre和ois的路径，例如：

OGRE_PATHS = { “F:\SDK\ogre-v1-7-0″, “OgreMain/include”, “lib” }
OIS_PATHS = { “F:\SDK\ogre-v1-7-0/Dependencies/include/OIS/”, “”, “lib” }

8. 找到CEGUI_OLD_OIS_API变量，设置为false
9. 找到OGRE_RENDERER变量，设置为true
10. 找到SAMPLES_OGRE变量，设置为true
11. 进入目录F:\SDK\cegui-v0-7-1\projects\premake，运行build_vs2008.bat（或对应的其他版本），你将看到CEGUI.sln
12. 继续运行build_samples_vs2008.bat（或对应的其他版本），你将看到CEGUISamples.sln
13. 在编译CEGUI.sln和CEGUISamples.sln时，如果依然存在找不到h或是link错误，请打开工程属性，修改Additional Include Directories和Additional Library Directories中对应的ogre和ois相关的路径
14. 请注意ogre 1.7.0的lib是生成在debug和release子目录中，记得修改为正确的link路径
15. 运行sample前，记得先复制F:\SDK\cegui-v0-7-1\dependencies\bin下的所有dll到F:\SDK\cegui-v0-7-1\bin下面，这样就不会报错提示缺少dll了

下面是我自己针对上面13步以后的的补充。。由于分几个阶段安装和写，又懒得再去编辑，所以中英文搭配。

1:First run cegui.sln.I guess because I seperate cegui from ogre,then the compiler said it can’t find
ogreblendmode.h,I add it from ogre_source_1.7.0/ogreMain/include to cegui.sln through properties->configuration properties->c/c++/general->Additional Include Directoriesdirectories->include files.

有几点要注意的。
第一点：要注意的是先编译CEGUI.sln再编译CEGUISample.sln，而且都要在同一模式下，或者至少CEGUI.sln有生成过该模式的库。
比如CEGUISample.sln要在debug模式下编译，那么CEGUI.sln要至少在debug模式下编译过，以生成相应的库。
第二点：是在给项目增加所依赖的include和library文件时，注意相对路径和绝对路径。比如要给CEGUISampler.sln增加OgreMain\include,注意如果前面出现\……\……，表示在当前文件下的相对路径，是不行的。

2:Then I run ceguisamples.sln,I complile the project of CEGUISampleHelper first！
下面的都是针对项目CEGUISampleHelper。
the things happened nearly the same.So this time I add something to the project too.
(1)
The compiler can’t find ogreblendmode.h
I add ogre_source_1.7.0/ogreMain/include to the project of CEGUISampleHelper through properties->configuration properties->c/c++/general->Additional Include Directoriesdirectories->include files
(2)
The compiler can’t find ogresettings.h.
I add ogre1.7.0_build/include to the project of CEGUISampleHelper throughproperties->configuration properties->c/c++/general->Additional Include Directoriesdirectories->include files
(3)
The complier can’t find ois.h
Add ogre_source_1.7.0/Dependencies/include/ois.h the same above.
(4)
The compiler can’t find ceguiOgreRender_d.lib
Add ogre_source_1.7.0/Dependencies/lib/debug to the project of CEGUISampleHelper: properties->configuration properties->liner->general->Additional Library Directories
Add F:\ogreAll\ogre1.7.0\ogre1.7.0_build\lib\Debug to the project of CEGUISampleHelper :properties->configuration properties->liner->general->Additional Library Directories
下面针对各个具体的Sample
（下面的1，2步貌似加不加都可以）
（1）：对每个需要运行的Sample在事先包括的头文件里加上
F:\ogreAll\ogre1.7.0\ogre_source_1.7.0\OgreMain\include
在事先包括的静态库里加上
（2）：F:\ogreAll\ogre1.7.0\ogre1.7.0_build\lib\Debug
（3）：如果运行后说找不到OgreMain_d.dll，可以把sample的工作目录（properties->configuration properties->debugging->working directories）改成OgreMain_d.dll所在的目录，比如我的：
F:\ogreAll\ogre1.7.0\ogre1.7.0_build\bin\debug

有几点要注意的。
一：
（下面的一步是我在一关于sdk的装配博客里看到的，所列出的头文件和库文件貌似在我下载的源码版里面已经事先加上了,也就是至少在源码的环境里是不需要的。如果sdk是需要的话大家可以加上）
配置vs环境。打开CEGUISamples VS2005，工具–>选项–>项目和解决方案–>VC++目录–>包含文件,在这里添加路径：（注：各个版本之间路径会有不同，但有一共性，都是include文件夹）

D:\CEGUISDK\Samples\common\include

D:\CEGUISDK\dependencies\include

D:\CEGUISDK\cegui\include

库文件，

D:\CEGUISDK\lib

D:\CEGUISDK\dependencies\lib\dynamic

D:\CEGUISDK\dependencies\lib\static（以往版本是不分dynamic和static的）

二：
  如果自己系统是xp不是Vista，不需要运行D3d10，所以可以在CEGUISamplerHelper项目里把带有d3d10字样的h文件和cpp文件移除，然后再去[CEGUI-SDK-0.7.1-vc9\cegui\include]文件夹下找到config.h文件，打开，把“#define CEGUI_SAMPLES_USE_D3D10”
的去掉。否则会说什么D3d10××.dll不可用之类的。

三：
  有些人说那个dataFiles（一些sample用的多媒体照片等）要放在相应的项目下面，但是我试了下貌似不行（其实应该可以的，只是我相对路径弄混了），所以我干脆在CEGuiBaseApplication.cpp里将datafiles的所在路径改成绝对路径
// setup default-default path
#ifndef CEGUI_SAMPLE_DATAPATH
// #define CEGUI_SAMPLE_DATAPATH “../datafiles”
#define CEGUI_SAMPLE_DATAPATH “f:/open Source Programe/cegui/cegui-0.7.1/datafiles”
#endif