(3.236.118.225) 您好!臺灣時間:2021/05/16 14:56
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳利琮
研究生(外文):Lih-Tsrong Chen
論文名稱:有效的全域照度成圖演算法之研究
論文名稱(外文):A Study of Efficient Rendering Algorithms for Globall Illumination
指導教授:王宗銘王宗銘引用關係
指導教授(外文):Chung-Ming Wang
學位類別:碩士
校院名稱:國立中興大學
系所名稱:資訊科學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:中文
論文頁數:151
中文關鍵詞:成圖蒙地卡羅法全域照度分散式計算需求導向加速效能負載平衡啟發式
外文關鍵詞:RenderingMonte Carlo MethodGlobal IlluminationDistributed ComputingDemand-DrivenSpeed-UpLoad BalanceHeuristic
相關次數:
  • 被引用被引用:1
  • 點閱點閱:110
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
  成圖是產生真實且符合光物理特性影像的技術,成圖方程式考慮到光源對物體的直接影響與其它物體間的間接影響,全域照度成圖演算法不僅計算光源對物體的照度貢獻,更考慮在光源照射下,場景中物體間的相互反射效果,更能真實的表現出環境中物體間受到光線照明後所產生的影響,產生具有陰影、色彩漸層、反射等效果的複雜場景,故能更正確、更真實的模擬三度空間場景,產生高解析度、高真實感的影像。
  在本篇論文中,我們將探討如何有效的減少全域照度成圖影像的雜訊,增加影像品質,因我們是利用成圖方程式計算場景中光源對物體表面上點的照度,此方程式是由複雜的積分算式所組成,需透過蒙地卡羅法求得此積分算式的近似解,而蒙地卡羅法的做法需在光源上的取正確且足夠的樣本點,才能解出較精確誤差較小的積分解,若光源上取的點越多或正確,則我們的成圖品質相對的會有較少的雜訊,影像看起來會更真實,因此在本文中將探討數種在光源上有效且精確的取樣方法。
  然而若要獲得更逼真的成圖影像,除了可用較多物件描述複雜的場景外,亦需對物體表面上的點精確的計算光源對此點的直接照度值或其它物體對此點的間接照度值,所以需在光源或像素點上取足夠的有效樣本,才能精確的計算照度值,一旦樣本數或場景物件數增加,其成圖時間常以指數比值增加成長,因此有效的降低成圖時間是迫切需要的,除了可尋求複雜度較低的演算法或對程式碼做最佳化,另外亦可使用分散式計算大幅降低成圖時間,因此在本文中亦將探討如何加強分散式的成圖計算效能與降低成圖時間。在分散式計算中有許多值得研究與探討的議題,諸如「需求導向」工作分配機制、「加速效能」、「負載平衡」等,然而「需求導向」的工作分配機制在系統開始做分散式計算後,工作的切割大小隨即固定不能更改,對於每個工作的複雜度我們並無法事先預知,在「非同質」或是計算能力相差懸殊的分散式成圖計算環境下,倘若套用複雜的場景模型或較多的取樣數,當工作切割的尺寸較大時,負載不平衡的現象會十分的明顯,同時間接的影響系統的加速效能。
  基於上述的動機與理由,我們發展一套進階的工作分配的評估機制,針對在分散式計算環境中,若有部分計算資源的工作量相當大而同一期間其餘計算資源卻有閒置的狀況下,設計一個智慧型的動態負載平衡演算法,當負載不平衡狀態發生時,系統能夠動態的將工作做適當的切割與分配,使得負載不平衡的狀態能有所改善。
  為了能夠在分散式環境中正確、客觀的定義出各個機器之負載狀態,我們在工作的排程分配方面,定義了「啟發式」的需求導向工作分配機制,系統對於索求工作的計算資源具備了「啟發式」的決策能力,不在是無條件的給予工作,而是會針對計算資源之前的計算效能紀錄、分析現階段系統的負載狀態與工作的複雜度等幾項因素評估,由一評估公式判斷工作的適合度,若不適合則給予較小或複雜度較低的工作,讓每台計算資源能充分的發揮與利用本身的計算能力,同時分配到適合自己的工作大小,有效的利用閒置的計算資源,間接的提昇系統負載平衡效能。
  經由實驗證實,「啟發式」的需求導向工作分配機制,可彌補經驗法則切割的缺失,在大型的異質分散式計算環境中,縱使以不同大小的工作切割,均能將系統的加速效能與負載平衡維持在理想的水準之上,同時可有效的提昇系統的負載平衡,間接的提升分散式計算的加速效能、加快系統成圖的完成時間。
綜觀本論文,我們分別對圓柱光源提出有效的取樣方法,使得圖像的品質更接近真實,同時亦提出「啟發式」的需求導向工作分配機制,有效的利用閒置的計算資源,提昇系統的負載平衡效能,間接的加快成圖時間,使得圖像的產生於時間上更有效率。

Rendering is a technique to generate images with a sense of reality. The rendering equation considers the influence of direct and indirect lighting. The global illumination rendering algorithms not only calculates the direct lighting but also considers the inter-reflection of objects. They can actually represent the effect of objects illuminated by luminaire, such as shadows, color bleeding, reflection and so on. Therefore, the global illumination rendering can generate more accurate and realistic 3D scenes with high resolution and realistic synthetic image.
In this thesis, we investigate how to efficiently reduce the noise and improve quality of global illumination rendering images. We consider the rendering equation to calculate the illumination of the surface. We used Monte Carlo methods to solve the rendering equation. To obtain less error solution and generate images with better qualities, sampling must be efficient for luminaries. We present several accurate and efficient sampling methods on cylindrical luminaires.
Distributed computing is a popular approach to improving the computing efficiency. The demand-driven scheme is a well-known scheme for distributed computing. However, the demand-driven task scheduling has a severe drawback: the task size can never be changed in the computing process and it is impossible to foresee the complexity of a task. In a heterogeneous environment, the speed up and load balancing will be even poor as we rendering complex scene model, task more samples or larger task size.
To cope with these problems, we design and develop an advanced demand-driven scheme called “heuristic demand-driven mechanism”. During the distributed computing. As the load imbalance occurring, it aimed at the idle and others computing resources analyzes theirs computing performance in the past, current loading and the complexity of task. This scheme can appropriately decompose and dynamically dispatch tasks, and encourage each computing resource to make full use of its computing power.
Experimental results demonstrate that the proposed “heuristic demand-driven mechanism” is able to improve the speed-up and load balancing efficiency. For example, the Office scene model with 16*16 task size achieves nearly 93% of ideal speed-up in a PC cluster environment. The load balance for 64*64 task size has 43% of improvement. Our scheme demonstrates its advantages in a large heterogeneous computing environment with large task sizes. The speed-up is toward to be optimal regardless of various task sizes.

第一章 緒論
1.1 研究動機與目的……..……..………………………………………………1
1.2 論文架構………………..……..……………………………………………5
第二章 相關研究
2.1 全域照度……………………………………………………………………7
2.2 成圖方程式……………..…………………………………………..………8
2.3 全域照度成圖演算法.………………………………………………..…….10
2.3.1 光線追蹤...……………………………………………………….....10
2.3.2 蒙地卡羅直接照明成圖演算法………………………………..…..11
2.3.3 蒙地卡羅路徑追蹤成圖演算法……...…………………………….13
2.4 蒙地卡羅法…………………………………………………………..……14
2.5 隨機變數產生法…………………………………………………………..17
2.6 混和密度法…………………………………………………………….….19
2.7 包含平面上點集合的最小凸多邊形……………………………………..20
2.8 平行分散式計算環境…………………………………………..……..…..22
2.8.1 軟體計算環境的選擇……………………………………….……….27
2.8.2 MPI通訊機制介紹……………….………………….……………...28
2.8.3 MPI之點對點通訊機制………………………………..…………..33
第三章 演算法設計與實做
3.1 圓柱光源取樣法…………………………………………………………..35
3.1.1 均勻密度取樣法…………………..………………………………..35
3.1.2 可視面取樣法……………………..……………………………..…36
一般可視面取樣法……………….……...………………………..36
權重可視面取樣法………………………….…...………………..37
3.1.3 實體角取樣法……………………………………………..………..39
切線法………………………………………………………….....40
界線多面體………..………...……………………………………43
3.2平行分散式計算….………………………………………………………….51
3.2.1 線上成圖進度顯示………………..………………………………..54
3.2.2 可中斷式的分散式成圖系統……..………………………………..57
3.2.3 啟發式的需求導向工作分配機制..………………………………..58
第四章 實驗結果與效能分析
4.1 測試環境…..……………………………………………………….……..69
4.2 測試模型……..………………………………………….………………..71
4.3 蒙地卡羅直接照明成圖演算法.…………………………….…………….72
4.3.1 Stratified與Non-stratified取樣法…………….………….….…….73
4.3.2 圓柱光源上不同的取樣法……………………..………….………...76
4.3.3 實體角中三種不同的取樣法………………….....………….…….82
4.4 分散式時間測試與效能分析.……………………………………….…...86
4.4.1 系統的加速……..…..………………………………..…………….87
4.4.2 不同工做分配機制之結果.…………………………..……………92
4.4.3 更小的工作切割尺寸……..…………………………..……….…..99
第五章 結論與未來工作
5.1 結論………………………………………..….…………………………109
5.2 未來工作…………………………………………………………………113
附錄
附錄A MPI平行程式設計
A.1 MPI(Message Passing Interface)簡介……………………….….…...117
A.2系統發展與環境設定…………………….………………………….119
A.3 MPI基本指令…….………………………………………………....122
附錄B實驗數據
B.1 Cornell box場景模型………...…………………………….………125
B.2 Office場景模型……...…………………………….………………129
B.3 Balls場景模型……………………………………………………..131
參考文獻……………………………………………………………………………138
詞彙索引
英中對照表…………...………………………………...……...….…………143
中英對照表…………...……………………………..…………………….…147

[Arvo86]J. Arvo, "Backward Ray Tracing", Developments in Ray Tracing, SIGGRAPH ’86 Course Notes, Vol. 12, August 1986.
[Arvo95]J. Arvo, “Stratified Sampling of Spherical Triangles,” In ACM SIGGRAPH ’95 Computer Graphics Proceedings, pp. 437-438, 1995.
[Bado94]D. Badouel, K. Bouatouch, and T. Priol, “Distributed Data and Control for Ray Tracing in Parallel,” IEEE Computer Graphics and Applications, Vol. 14, No.4, pp. 69—77, 1998.
[Bart99]D. Bartz, B. Schneider, and C. Silva, “Rendering and Visualization in Parallel Environments,” Tutorial of Eurographics ’99, 1999.
[Bria01]B. Wylie, C. Pavlako, V. Lewis, and K. Moreland, “Scalable Rendering on PC Clusters,” IEEE Computer Graphics and Applications, pp. 69—77, July/August 2001.
[Chal98]A. Chalmers and E. Reinhard, “Parallel and Distributed Photo-Realistic Rendering,” ACM SIGGRAPH ’98 Conference Proceeding, Course Notes 3, 1998.
[Croc97]W. Crockett, F. Thomas, “An Introduction to Parallel Rendering,” Parallel Computing, Vol. 23, No. 7, pp. 819-843, July 1997.
[Dutr93]P. Dutré , E. P. Lafortune, and Y. D. Willems, “Monte Carlo Light Tracing with Direct Computation of Pixel Intensities,” Proceedings of Compugraphics '93, Alvor, Portugal, pp.128-137, December 1993.
[Dutr96]P. Dutr´ e, Mathematical Frameworks and Monte Carlo Algorithms for Global Illumination in Computer Graphics, PhD thesis, Katholieke Universiteit Leuven, Belgium, September 1996.
[Grah72]R. L. Graham. An Efficient Algorithms for Determining the Convex Hull of a Finite Planar Set, Information Processing Letters, Vol. 1, pp. 132-133, 1972
[Hamm64]J. Hammersley and D. Handscomb, Monte Carlo Methods, Wiley, New York, NY, 1964.
[Heck92]P. S. Heckbert, “Introduction to Global Illumination,” ACM SIGGRAPH '92, Global Illumination Course, 1992.
[Heri97]A. Heirich and J. Arvo, “Scalable Monte Carlo Image Synthesis,” Parallel Computing, Vol. 23, No. 7, pp. 845-859, July 1997.
[Heri98a]A. Heirich and J. Arvo, “A Competitive Analysis of Load Balancing Strategies for Parallel Ray Tracing,” Journal of Supercomputing, Vol. 12, No. 1, pp. 57-68, 1998.
[Heri98b]A. Heirich, Analysis of Acalable Algorithms for Dynamic Load Balancing and Mapping with Application to Photo-realistic Rendering, PhD thesis, California Institute of Technology, Pasadena, California, 1998.
[Hyeo97]S. E. Hyeon-Ju Yoon and J. W. Cho, “Image Parallel Ray Tracing using Static Load Balancing and Data Prefetching,” Parallel Computing, Vol. 23, No.7, pp. 861—872, 1998.
[Iked98]T. Ikedo and J. Ma, “A Scalable Rendering Processor,” IEEE Computer Graphics and Applications, Vol. 18, No. 2, March/April 1998.
[Jane97]E. Jansen and W. Frederik, “Rendering Large Scenes Using Parallel Ray,” Parallel Computing, Vol. 23, No. 7, pp. 873-885, July 1997.
[Kaji86]J. T. Kajiya, “The Rendering Equation,” Computer Graphics, ACM SIGGRAPH ’86 Conference Proceeding, Vol. 20, pp. 143-150, 1998.
[Keat98]M. J. Keates and R. J. Hubbold, “Interactive Ray Tracing on A Virtual Shared-Memory Parallel Computer,” Computer Graphics Forum, Vol. 14, No. 4, pp. 189-202, 1998.
[Lafo96]E. P. Lafortune, Mathematical Models and Monte Carlo Algorithms for Physically Based Rendering, PhD dissertation, Katholieke Universiteit Leuven, February 1996.
[Lafo96]E. Lafortune, Mathematical Model and Monte Carlo Algorithm for Physically Based Rendering, Ph.D. Dissertation, Department of Computer Science, Katholieke Universiteit Leuven, Belgium, 1996.
[Mess94]Message Passing Interface Forum, “MPI: A Message Passing Interface Standard,” International Journal of Supercomputing Applications and High Performance Computing, Vol. 8, No.3, 1994.
[Mood74]A. M. Mood, F. A. Graybill, and D. C. Boes, Introduction to the Theory of Statistics, McGraw-Hill, Singapore, pp. 122-123, 1974.
[Orcu98]D. E. Orcutt, “Implementation of Ray Tracing on the Hypercube,” Third Conference on Hypercube Concurrent Computers and Applications, Vol. 2, pp. 1207—1210, 1998.
[Patt92]S. Pattaniak and S. Madur, “Computation of Global Illumination by Monte Carlo Simulation of the Particle Model of Light,” Third Eurographics Workshop on Rendering, pp.71-83, May 1992.
[Patt93]S. N Pattanaik and S.P. Mudur, “Computation of Global Illumination in a Participating Medium by Monte Carlo Simulation,” The Journal of Visualization and Computer Animation, Vol. 4, No. 3, pp. 133-152, 1993.
[Phil98]P. Slusallek, M. Stamminger, W. Heidrich, J. Popp, and H. Seidel, “Composite Lighting Simulations with Lighting Networks,” IEEE Computer Graphics and Applications, pp. 22—31, March 1998.
[Reis00]A. Reisman, C. Gotsman, and A. Schuster, “Interactive-Rate Animation Generation by Parallel Progressive Ray-Tracing on Distributed-Memory Machines,” Journal of Parallel and Distributed Computing, Vol. 60, No. 9, pp. 1074-1102, September 2000.
[Sama99]R. Samanta, J. Zheng, T. Funkhouser, K. Li, and J. P. Singh, “Load Balancing for Multi-Projector Rendering Systems,” Eurographics Workshop on Graphics Hardware, August 1999.
[Schn98]B. Schneider. “Parallel Rendering on PC Workstations,” Proceedings of 1998 International Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas, July 1998.
[Scot99]T. D. Scott, V. F. Fusco, and R. S. Ferguson, “3D Ray-Tracing on PC Networks using TCP/IP,” Proceedings of the 1999 International Conference on Information Visualization.
[Shir91]P. Shirley and C. Wang, “Direct Lighting Calculation by Monte Carlo Integration,” Proceedings of the Second Eurographics Workshop on Rendering, 1991.
[Shir96]P. Shirley, C. Wang, and K. Zimmerman, “Monte Carlo Technique for Direct Lighting Calculations,” ACM Transactions on Graphics, Vol. 15, No. 1, pp. 1-36, 1996.
[Shir98]P. Shirley, “Monte Carlo Methods in Rendering,” ACM SIGGRAPH ’98 Conference Proceeding, Course Notes 5, pp.9—1, 1998.
[Shre66]Y. Shreider, The Monte Carlo Method, Pergamon Press, New York, NY, 1966.
[Sing94]J. S. Sing, A. Gupta, and M. Levoy, “Parallel Visualization Algorithms: Performance and Architectural Implications,” IEEE Computer, Vol.27, No.7, pp. 45—55, 1998.
[Snel97]Q. O. Snell, Parallel Hierarchical Global Illumination, PhD thesis, Computer Science, Iowa State University, 1997.
[Sobo94]I. Sobol, A Primer for the Monte Carlo Method, CRC Press, Boca Raton, Florida, 1994.
[Tahs98]K. Tahsin; M. Aykanat, Cevdetb; Özgüç, and Bülentb, “Object-Space Parallel Polygon Rendering on Hypercubes,” Computers & Graphics, Vol. 22, No. 4, pp. 487-503, August 1998.
[Taka90]A. Takage, H.Takaora, T. Oshima, and Y. Ogota, “Accurate Rendering Technique Based on Colorimetric Conception”, Proceeding of SIGGRAPH 1990, pp.263-272, 1990.
[Wang94]C. Wang., The Direct Lighting Computation in Global Illumination Methods, Ph. D Dissertation, Department of Computer Science, University of Indiana, Indiana, 1994.
[Whit80]T. Whitted. “An Improved Illumination Model for Shaded Display,” Communications of the ACM, Vol. 23, No. 6, pp. 343-349, June 1980.
[Zare95]D. Zareski, “Efficient Parallel Global Illumination Using Density Estimation,” Proceedings of the 1995 Parallel Rendering Symposium, pp. 47-54, 1995.
[Zimm98]K. Zimmerman, Density Prediction for Importance Sampling in Realistic Image Synthesis, Ph.D. Dissertation, Department of Computer Science, University of Indiana, Indiana, 1998.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊