如何开始研究？－－ 图形学相关的库介绍
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做视频实时渲染成水彩画的我想也属于这一类。

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