营员交流长郡中学

1、3D图像引擎初探长郡中学 梁盾 沈业基前言半个世纪多以来，计算机硬件发展速度极快想必大家应该都认识这位计算机界的“老爷爷”Eniac前言还记得小时候第一次买电脑，玩了好久的游戏就是这个前言现在很多大型3d游戏，画面十分惊艳前言以假乱真的电影画面硬件在进步CpuGpuMx400/440算法也在进步几个大名鼎鼎的图像引擎：Frostbite 2.0（寒霜）Unreal Engine 3（虚幻）CryENGINE 3.思考我们作为对“算法”和“数据结构”相当熟悉的OIer，虽然做题比较行，但我们似乎并不太熟悉这些与生活联系相当紧密的东西。刚才展示一些3D电影中出现的图片中那些以假乱真的渲染效果到底是

2、怎么做出来的呢？那些高效而又逼真的3D图像引擎到底是怎么实现的呢？解惑我向对3D引擎方面比较有研究的刘汝佳老师问了这个问题，得到了如下答复：3D电影可以用大量时间使用离线算法得到最好的效果，例如光线追踪、光子映射等算法；而3D引擎由于对效率要求很高，所以一般会退而求其次地采用一些虽然不尽符合物理规律，但实际效果还不错的算法，如法线贴图、Z-Buffer等算法。解惑可以看出离线渲染和在线渲染各有侧重，各有千秋下面我将分离线渲染和在线渲染两方面与大家交流交流离线渲染光线追踪由于光路可逆原理，我们可以从眼睛发射出若干条射线来反着寻找我们看到的物体。具体而言，就是对于屏幕上的每一个像素，我们引一条从眼

3、睛射向这个点的射线，模拟这条射线的运动轨迹直到得到这个像素最后是什么样子。光线追踪在简单情况下，所有物体既不反射光也不透明，则每当射线碰到一个物体时，我们可以直接计算这个物体的颜色。而光线追踪最nb的地方在于可以处理反射与折射的情况如果射线碰到了一个反射性物体，我们发出一条新的反射光线，从碰撞点射出，指向 碰撞表面的外部。同理，如果射线碰到了一个透明物体，我们派生出一条新的折射光线，从碰撞点射出，指向碰撞表面的内部。如果 碰撞面两侧的物体的折射系数不同，则光线的方向将发生改变。光线追踪处理每条射线的过程伪代码如下：(LRJ老师提供)光线追踪优势：对于镜面、玻璃和水面，光线追踪可以渲染出相当华丽

4、的效果劣势：速度比较慢，随着场景中的物体个数增加，算法消耗的时间会急速增长初步成果实现其实说白了这就是一道很普通的计算几何题，计算几何题往往实现才是其关键LRJ老师的那道题就是UVa12313，大家可以考虑没事的时候自己去做一做下面我讲讲我自己的实现方法，如果大家有更好的实现方法就上来一起交流交流吧。实现创建三维向量类：struct pointdouble x,y,z;P operator +(P a,P b) return P(a.x+b.x,a.y+b.y,a.z+b.z); /向量加法P operator -(P a,P b) return P(a.x-b.x,a.y-b.y,a.z-b

5、.z); /向量减法P operator *(P a,double b) return P(a.x*b,a.y*b,a.z*b); /数乘P operator /(P a,double b) return a*(1/b); /还是数乘P operator *(P a,P b) return P(a.y*b.z-a.z*b.y,a.z*b.x-b.z*a.x,a.x*b.y-a.y*b.x);/三维叉积double operator /(P a,P b) return a.x*b.x+a.y*b.y+a.z*b.z; /点积double mo(P a) return sqrt(a.x*a.x+a

6、.y*a.y+a.z*a.z); /模其中比较关键的是三维叉积，他可以返回和这两个向量垂直的另一个向量。实现创建三维面类：struct P f,double s表示的就是(x*f.x + y*f.y + z*f.z = s)这样子的一个面，f的实际意义就是这个面的法向量，为了使得下面的计算变得简便，我们把f的模变成一。假设我们要求点a到面b的距离，直接a/b.f-b.s即可，其中“/”为向量点积有了以上这些过程以后，写起来就方便多了。实现色彩的合成与明暗：Lambertian着色法（也叫余弦着色法）： 即根据碰撞表面的法线和从碰撞点到光源的向量的点积计算亮度。当夹角增大时，亮度按照余弦函数减小

7、。这么做的目的是为了让模型更加有立体感。实现实现很难吗？不，代码量比杀菌计划还要小一点！最麻烦的地方：1.求射线与面的交点；2.处理射线反射与折射；不担心常数的话可以使用高斯消元，担心常数的话拿出你的笔和纸用力算吧如果大家有兴趣实现的话建议先完成杀菌计划。遗留的一个问题代码实现出来了，但是我们怎么样将图片输出出来呢？会python的同学可以直接使用PIL来处理，只用c+的话这里我们可以观摩一下范浩强神牛曾经写过的光线追踪算法。BMP或者PNG都是位图文件，我们可以直接把他当做二进制文件读取并且修改。详细资料： 具体实现： 优化观察这个图，我们会发现几个问题：锯齿严重无法处理光的辉映、焦散的情况

8、优化怎样抗锯齿呢？最朴素的方法就是直接把原来的一个像素分成n*n个像素，最后这个点的颜色就是n*n个像素颜色的平均值，如下对比图：N越大，效果就越好，但渲染时间也越长。一般游戏里设置的几级抗锯齿，我猜大概就是N有多大的意思吧。优化解决光的辉映、焦散的情况。实际上这个问题难以解决，需要用到另外一个算法：光子映射。介于本人水平。研究这个算法的任务就交给大家吧！有兴趣的同学请自行wiki或者百度。几张高清成品图花费了大量时间进行参数修改，最终完成了几张自己觉得还行的作品，诚邀大家围观 _ 在线渲染虽然光线追踪渲染出来的画面挺不错的，但是花费的时间相当长，比如前几页的图片，每张图片差不多要两分钟才能运

9、算完成，当然，我写丑了也是很大的原因= =即使是写得相当优异的光线追踪算法，也达不到在线渲染的要求，顶多在部分场景的关键部位使用少量的光线追踪算法。在线渲染这里我们可以大致的计算一下在线渲染的复杂度要求：每秒30帧，分辨率1440*900，因此每秒需要计算的像素个数为38880000，每个像素差不多需要O(1)出解！这似乎非常困难在线渲染这里我向大家介绍一下z-buffer算法，中文叫做“深度缓冲”，实际上伪代码相当简单：For 场景中的每一个物体 For 这个物体在屏幕上可能显示的每一个像素 if 从这个像素看到的这个物体不会被别的物体挡住 then 计算这个点的颜色可以发现，这个算法的复杂

10、度是O(n+sigma(每个物体在屏幕上显示的 像素个数)虽然在某些情况下这个算法甚至会比光线追踪还要慢，但是真实场景都是相当迅速的在线渲染观察z-buffer算法的伪代码可以发现他的优缺点。优点：速度快缺点：无法处理阴影，折射和反射在线渲染由于需要体现出在线的速度，我仿照现在的第一人称射击类游戏，使得摄像机可以通过WASD和鼠标来控制摄像机在场景内部移动。为了实现这些交互式功能，我使用的开发平台是QT在线渲染Z-buffer算法不负众望，在进过了一些常数优化以后，对于一个有30个三角形的场景可以轻易的达到50fps！虽然画面稍逊，并且但是我们可以在场景内部移动了！在线渲染但是，刘汝佳老师给了

11、我一个场景内有70000个三角形的兔子高模！70000多个三角形的计算已经让我的小程序跑得气喘吁吁，帧数直接降到15，严重影响动画的流畅性优化这是一个艰巨的任务，我不断的更新程序，将常数优化加到山穷水尽，帧数也仅仅提升到了20帧，而人眼至少需要30帧才不会感觉到卡顿继续优化的空间在哪里？看了看自己笔记本上的intel core标志，反映了过来：多线程优化！优化想必大家平时都发现到：自己的程序cpu占用量总是只有1/芯片线程数，怎样才可以利用到cpu的全部力量呢？答案就是多线程。C/C+可以使用fork()来使得自己的程序变成多进程，所以在noi等比赛中都是严令禁止使用fork。这里我直接使用了qt中的qthread类，方便多线程管理优化考虑到现在大部分电脑的芯片线程个数没有超过8，所以我创建了8个线程来运算。多线程优化的大致思路就是把这n个三角形的运算平均分给8个进程来进行运算，最后在使用主进程来整合8个进程的运算结果。优化结果相当可喜可贺，下表是添加了多线程优化的效果，大家观察这个表格，可以发现多线程优化是相当给力的！之所以fps不随线程数线性增长，是因为主进程整合所有线程的运算结果也是瓶颈之一使用线程数1248平均fps25