A02: raytracing
# A02: raytracing
預先準備動作
- 參照 phonebook 的指示,在實體機器安裝 GNU/Linux 和相關的開發套件
- 注意: 不得透過虛擬機器,因為我們在意實際機器上的效能
- 安裝以下開發工具
$ sudo apt-get update $ sudo apt-get install graphviz $ sudo apt-get install imagemagick
光影追蹤程式
- 光線追蹤 (Ray tracing) 是三維電腦圖形學中的描繪演算法 (rendering algorithm),跟蹤從眼睛發出的光線,而非是光源發出的光線,藉由預先編排好的場景,以數學模型顯現出來,可得到類似於光線投射與掃描線描繪方法的結果,對於反射與折射,可有更準確的模擬效果,效率非常高,所以當追求高品質的效果時,經常使用這種方法
- 在物理學中,光線追跡可以用來計算光束在介質中傳播的情況。在介質中傳播時,光束可能會被介質吸收,改變傳播方向或者射出介質表面等。我們通過計算理想化的窄光束(光線)通過介質中的情形來解決這種複雜的情況
- 在實際應用中,可將各種電磁波或者微小粒子看成理想化的窄波束(即光線),基於這種假設,人們利用光線追跡來計算光線在介質中傳播的情況。光線追跡方法首先計算一條光線在被介質吸收,或者改變方向前,光線在介質中傳播的距離,方向以及到達的新位置,然後從這個新的位置產生出一條新的光線,使用同樣的處理方法,最終計算出一個完整的光線在介質中傳播的路徑
- 成大資訊系師生合作開發原始程式碼僅 650 行的光線追蹤 C 語言程式: raytracing
取得原始程式碼、編譯和測試:
$ git clone https://github.com/sysprog21/raytracing $ cd raytracing $ make $ ./raytracing
出現
# Rendering scene
字樣後,請保持耐心,等待程式輸出Done!
字樣,參考輸出:Execution time of raytracing() : 2.994175 sec
raytracing 程式執行完畢,將輸出名為
out.ppm
的檔案,可透過eog
或在圖形界面點擊開啟。參考輸出:操作提示:
- 透過
convert
這個工具可將 PPM 轉為 PNG 或其他格式,如:$ convert out.ppm out.png
- 透過
make check
會檢驗程式碼輸出的圖片是否符合預期,符合的話會得到 “Verified OK!” 字樣
作業要求
- 在 GitHub 上 fork raytracing,並思考如何改善程式效能
- 以
make PROFILE=1
重新編譯程式碼,並且學習 gprof - 以 gprof 指出效能瓶頸,並且著手改寫檔案
math-toolkit.h
在內的函式實做,充分紀錄效能差異在共筆- 注意: 請勿更動編譯器最佳化選項
-O0
(關閉最佳化) - 檔案
math-toolkit.h
定義的若干數學操作函式很重要,可參考 Investigating SSE cross product performance、MathFu 原始程式碼,以及 2015q3 Homework #1 Ext
- 注意: 請勿更動編譯器最佳化選項
- 可善用 POSIX Thread, OpenMP, software pipelining, 以及 loop unrolling 一類的技巧來加速程式運作
- 將你的觀察、分析,以及各式效能改善過程,並善用 gnuplot 製圖,紀錄於「作業區」
截止日期
- Sep 29, 2016 (含) 之前
- 越早在 GitHub 上有動態、越早接受 code review,評分越高