# B02: raytracing ###### tags: `sysprog2017` :::info 主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2017 年系統軟體課程](https://www.facebook.com/groups/system.software2017/) :mega: 返回「[嵌入式作業系統設計與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程進度表 ::: * ==作業解說 [video](https://www.youtube.com/watch?v=m1RmfOfSwno)==,請對照觀看,只要看 "Homework 2" 的部份 * ==參考實做程式的解說 [video](https://www.youtube.com/watch?v=V_rLyzecuaE)==,[對應的共筆](https://embedded2016.hackpad.com/ep/pad/static/f5CCUGMQ4Kp) ## 預先準備動作 * 參照 [phonebook](https://hackmd.io/s/rJYD4UPKe) 的指示,在實體機器安裝 GNU/Linux 和相關的開發套件 * 注意: 不得透過虛擬機器,因為我們在意實際機器上的效能 * 安裝以下開發工具 ``` $ sudo apt-get update $ sudo apt-get install graphviz $ sudo apt-get install imagemagick ``` ## 光影追蹤程式 * 光線追蹤 (Ray tracing) 是三維電腦圖形學中的算繪演算法 (rendering algorithm),跟蹤從眼睛發出的光線,而非是光源發出的光線,藉由預先編排好的場景,以數學模型顯現出來,可得到類似於光線投射與掃描線描繪方法的結果,對於反射與折射,可有更準確的模擬效果,效率非常高,所以當追求高品質的效果時,經常使用這種方法 * 在物理學中,光線追跡可以用來計算光束在介質中傳播的情況。在介質中傳播時,光束可能會被介質吸收,改變傳播方向或者射出介質表面等。我們通過計算理想化的窄光束(光線)通過介質中的情形來解決這種複雜的情況 * 在實際應用中,可將各種電磁波或者微小粒子看成理想化的窄波束(即光線),基於這種假設,人們利用光線追跡來計算光線在介質中傳播的情況。光線追跡方法首先計算一條光線在被介質吸收,或者改變方向前,光線在介質中傳播的距離,方向以及到達的新位置,然後從這個新的位置產生出一條新的光線,使用同樣的處理方法,最終計算出一個完整的光線在介質中傳播的路徑 * 成大資訊系師生合作開發原始程式碼僅 650 行的光線追蹤 C 語言程式: [raytracing](https://github.com/sysprog21/raytracing) * 取得原始程式碼、編譯和測試: ```shell $ git clone https://github.com/sysprog21/raytracing $ cd raytracing $ make $ ./raytracing ``` * 出現 `# Rendering scene` 字樣後,請保持耐心,等待程式輸出 `Done!` 字樣,參考輸出: ``` Execution time of raytracing() : 2.994175 sec ``` * [raytracing](https://github.com/sysprog21/raytracing) 程式執行完畢,將輸出名為 `out.ppm` 的檔案,可透過 `eog` 或在圖形界面點擊開啟。參考輸出: ![ray-tracing](https://hackmd.io/_uploads/Sk-5kLYoY.png) * 操作提示: * 透過 `convert` 這個工具可將 PPM 轉為 PNG 或其他格式,如: ```shell $ convert out.ppm out.png ``` * `make check` 會檢驗程式碼輸出的圖片是否符合預期,符合的話會得到 “Verified OK!” 字樣 ## 作業要求 * 在 GitHub 上 fork [raytracing](https://github.com/sysprog21/raytracing),並思考如何改善程式效能 * 以 `make PROFILE=1` 重新編譯程式碼,並且學習 [gprof](https://sourceware.org/binutils/docs/gprof/) * 參考 [使用 GNU gprof 進行 Linux 平台的程式分析](http://os.51cto.com/art/200703/41426.htm) * 以 [gprof](https://sourceware.org/binutils/docs/gprof/) 指出效能瓶頸,並且著手改寫檔案 `math-toolkit.h` 在內的函式實做,充分紀錄效能差異在共筆 * 注意: 請勿更動編譯器最佳化選項 `-O0` (關閉最佳化) * 檔案 `math-toolkit.h` 定義的若干數學操作函式很重要,可參考 [Investigating SSE cross product performance](http://threadlocalmutex.com/?p=8)、[MathFu](https://google.github.io/mathfu/) 原始程式碼,以及 [2015q3 Homework #1 Ext](http://wiki.csie.ncku.edu.tw/embedded/2015q3h1ext) * 可善用 POSIX Thread, OpenMP, software pipelining, 以及 loop unrolling 一類的技巧來加速程式運作 * 將你的觀察、分析,以及各式效能改善過程,並善用 gnuplot 製圖,紀錄於「[作業區](https://hackmd.io/s/Hy2rieDYe)」 ## 截止日期 * Mar 4, 2017 (含) 之前 * 越早在 GitHub 上有動態、越早接受 code review,評分越高 ## 挑戰題 * 透過 SIMD 指令或 OpenCL 改寫 raytracing 內部實作 * 參考: * [你也可以寫 SIMD 比寫網頁還快 - I](https://champyen.blogspot.com/2017/01/simd-i.html) * [你也可以寫 SIMD 比寫網頁還快 - II](https://champyen.blogspot.com/2017/01/simd-ii.html) * [你也可以寫 SIMD 比寫網頁還快 - III](https://champyen.blogspot.com/2017/01/simd-iii.html) * 改寫 raytracing,引入更複雜、更華麗的模型 (model) ## 見賢思齊:共筆選讀 * [hugikun999](https://github.com/hugikun999/raytracing): [共筆](https://hackmd.io/s/HyHhgcv6) * 利用 gprof2dot 工具,將最耗時的函式與呼叫的路徑視覺化,隨後他做了頗多 OpenMP 的實驗 * LanKuDot: [共筆](https://hackmd.io/s/rkggUeKa) * 解讀了光線追蹤程式。以函式 raytracing 來說,傳入場景必要的物件:長方面 (牆)、球體、光源、背景色、攝影機位置及視角、攝影機畫面 (輸出圖片) 的長寬。 * 先計算以攝影機平面為基準的 vector space 的 basis vector,將結果存在 vector u, v, w。SAMPLES:為了反鋸齒 (MSAA,多重採樣反鋸齒法),設定成取樣四個 pixel 作為該 pixel 的顏色。 * 觀察 raytracing 後,提出 raytracing 程式可進行平行化之處: * 整張圖的運算切割:row 分, column 分或 block 分。缺點是每一個 pixel 的呼叫熱度不一樣,所以如果切出來熱度過於集中在某個 block,平行化的效果不高; * 模糊化處理:每個 sample 做完運算後,再取平均; * RGB:RGB 的計算結果是不互相干擾的,可以個別平行加。缺點 ray_color 計算完顏色一次輸出 RGB,如果每個 thread 只取其中一個值會太浪費; ## 參考資料 :::warning 引用過往作業成果時,務必標註出處 (包含 GitHub 帳號或人名),連帶相關的超連結 ::: * [Ray tracing](https://en.wikipedia.org/wiki/Ray_tracing_(graphics)) * [認識與學習 Bash](http://linux.vbird.org/linux_basic/0320bash.php) * [學習 Shell Scripts](http://linux.vbird.org/linux_basic/0340bashshell-scripts.php) * [2016 年秋季班課程作業區](https://hackmd.io/s/H1B7-hGp): 提供錄影解說 * [2016 年春季班課程作業區](https://embedded2016.hackpad.com/2016q1-Homework-2-v37rXPJjRlW)