Try   HackMD

B02: raytracing

tags: sysprog2017

主講人: jserv / 課程討論區: 2017 年系統軟體課程

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
返回「嵌入式作業系統設計與實作」課程進度表

  • 作業解說 video，請對照觀看，只要看 "Homework 2" 的部份
  • 參考實做程式的解說 video，對應的共筆

預先準備動作

  • 參照 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 或在圖形界面點擊開啟。參考輸出:
    Image Not Showing Possible Reasons
    • The image was uploaded to a note which you don't have access to
    • The note which the image was originally uploaded to has been deleted
    Learn More →
  • 操作提示：
    • 透過 convert 這個工具可將 PPM 轉為 PNG 或其他格式，如:
    ​​​​$ convert out.ppm out.png
  • make check 會檢驗程式碼輸出的圖片是否符合預期，符合的話會得到 “Verified OK!” 字樣

作業要求

  • 在 GitHub 上 fork raytracing，並思考如何改善程式效能
  • 以 make PROFILE=1 重新編譯程式碼，並且學習 gprof
  • 以 gprof 指出效能瓶頸，並且著手改寫檔案 math-toolkit.h 在內的函式實做，充分紀錄效能差異在共筆
  • 可善用 POSIX Thread, OpenMP, software pipelining, 以及 loop unrolling 一類的技巧來加速程式運作
  • 將你的觀察、分析，以及各式效能改善過程，並善用 gnuplot 製圖，紀錄於「作業區」

截止日期

  • Mar 4, 2017 (含) 之前
  • 越早在 GitHub 上有動態、越早接受 code review，評分越高

挑戰題

見賢思齊：共筆選讀

  • hugikun999: 共筆
    • 利用 gprof2dot 工具，將最耗時的函式與呼叫的路徑視覺化，隨後他做了頗多 OpenMP 的實驗
  • LanKuDot: 共筆
    • 解讀了光線追蹤程式。以函式 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 只取其中一個值會太浪費;

參考資料

引用過往作業成果時，務必標註出處 (包含 GitHub 帳號或人名)，連帶相關的超連結

Last changed by 
 
sysprog
System Software Programming
0
3355
Published on HackMD