网格简化
实验目的
实现边坍塌的网格简化方法。
实验内容
我实现了Surface Simplification Using Quadric Error
Metrics(下面称为Quadric)及A Simple, Fast, and Effective Polygon
Reduction
Algorithm(下面称为Simple)及中的网格简化算法。程序中使用了堆优化。对于fixed.perfect.dragon.100K.0.07.obj，简化到1%时，我的机器上Simple需要4.423秒，Quadric需要7.403秒。
A Simple, Fast, and Effective Polygon Reduction Algorithm
Buddha
下面是Buddha.obj的原图： 
下面是网格简化后的效果图：
Fixed Perfect Dragon
下面是fixed.perfect.dragon.100K.0.07.obj的原图： 
下面是网格简化后的效果图： 
Surface Simplification Using Quadric Error Metrics
下面是5%面片时两个算法生成的模型： 
下面是1%面片时两个算法生成的模型： 
个人主观感觉Quadric的效果比Simple好。
目录结构
src/simple.cc：Simple的实现。
src/quadric.cc：Quadric的实现。
均使用C++ 11编写。
光线追踪
实验目的
实现光线追踪算法，产生具有真实感的图像。
几何图形
程序中实现了球、平面、三角形、网格等图形。
三角形
光线与三角形的相交采用了一个较快的方法：Möbius发明的barycentric coordinates，同时可以用作后面纹理用的UV mapping。
物体表示
include/Geometry.hh及include/geometry/*.hh表示各个抽象的几何图形，Geometry类定义了finite变量表示图形是否为有限的，另外还定义了表示与光线相交的抽象接口getTrace。
getTrace以Ray为参数，返回表示与光线相交结果的Trace类的实例，Trace类定义了交点位置、与光线原点距离、交点处图形的法向量、交点处的材质等信息。
Material类表示材质，带有漫反射、折射，及其他各个Phong模型需要用到的参数。
表示物体的纹理，可以用uv-mapping得到具体的材质信息。
Prim表示物体，是Geometry及Texture两个类的简单组合，它也定义了getTrace方法，实现方法为调用下层的Geometry的同名方法，设置得到的Trace实例的prim变量，使其指向自己。
物理模型
Phong反射模型
采用了裴祥风提出的Phong反射模型。
折射
0.45 
0.45 
0.45 
0.45 
0.45 
光线能量衰减
光线初始能量为1.0，在传播过程中能量会衰减。下图是没有光线能量衰减的：
根据Beer-Lambert law的简化公式：
视觉效果有一定提升：
纹理
所有表示几何图形的类(Geometry)都具有uv方法，用于把改图形上的一个顶点映射到Texture具有getMaterial方法，根据uv座标获得相应位置的材质信息。
加速算法
包围盒
对于每根光线，计算和它相交的物体的朴素算法是枚举场景中所有物体，依次和光线计算交点。这可以用包围盒及Kd-tree对空间剖分进行优化。
包围盒的主要思想是场景中所有物体都有一个包围盒，物体与光线相交仅当包围盒与光线相交。如果把若干物体放在同一包围盒里，而这个大包围盒不与光线相交，那么这个大包围盒里的所有物体都不用判断是否会与光线相交了。
Kd-tree
Kd-tree则对这些包围盒做了层次化的划分，每个内部节点都有一个划分平面，把节点表示的空间划分为两半。如果检测到光线与左半空间相交且距离小于光线与右半空间交点距离，那么右半空间就无需考虑了。
Kd-tree的空间划分方式可以根据两边的物体数目差，也可以用surface area
heuristic，实现中我采用了如下公式作为划分平面的估价函数：
选择使这个股价函数的最优划分平面。
渲染下面的121个球，对于每根光线枚举所有物体求交点的朴素实现需要5.375秒，使用Kd-tree后仅需0.28秒。
实现中所有场景中的物体我用一棵Kd-tree管理，对于较大的面片会用一棵局部的Kd-tree管理。
OpenMP
程序的主循环枚举了屏幕的各个像素进行光线追踪，注意到不同像素之间互补干扰，可以轻松地在for循环前加上OpenMP的指示符获得多线程优化。
其他
Gamma校正
Gamma校正(Gamma
correction)用来光线的辉度或三色刺激值进行非线性的运算，程序提供了几个选项用于控制RGB三个分量的gamma值，通过如下公式计算实际显示的R值(G值、B值类似):
反锯齿
反锯齿(anti-aliasing)是一种消除显示器输出的画面中图物边缘出现凹凸锯齿的技术。常规的方法是supersampling，即在像素点附近提高采样密度，差值获得颜色值。实现中采用了stochastic sampling，在像素点附近随机选择一些点，差值获得颜色值。
另外可以使用adaptive sampling的方法，当像素点的颜色值和周围相差较大时再采用supersampling以提升效率。
