網格簡化
實驗目的
實現邊坍塌的網格簡化方法。
實驗內容
我實現了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以提升效率。
