在叢集電腦上平行彩繪多重解析度模型

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：103

、訪客IP：3.144.18.252

姓名

林明杰(Ming-Je Lin) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

在叢集電腦上平行彩繪多重解析度模型
(Parallel Rendering for Multiresolution Models on PC Cluster)

相關論文

★ 適用於大面積及場景轉換的視訊錯誤隱藏法	★ 虛擬觸覺系統中的力回饋修正與展現
★ 多頻譜衛星影像融合與紅外線影像合成	★ 腹腔鏡膽囊切除手術模擬系統
★ 飛行模擬系統中的動態載入式多重解析度地形模塑	★ 以凌波為基礎的多重解析度地形模塑與貼圖
★ 多重解析度光流分析與深度計算	★ 體積守恆的變形模塑應用於腹腔鏡手術模擬
★ 互動式多重解析度模型編輯技術	★ 以小波轉換為基礎的多重解析度邊線追蹤技術(Wavelet-based multiresolution edge tracking for edge detection)
★ 基於二次式誤差及屬性準則的多重解析度模塑	★ 以整數小波轉換及灰色理論為基礎的漸進式影像壓縮
★ 建立在動態載入多重解析度地形模塑的戰術模擬	★ 以多階分割的空間關係做人臉偵測與特徵擷取
★ 以小波轉換為基礎的影像浮水印與壓縮	★ 外觀守恆及視點相關的多重解析度模塑

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

本論文提出一個平行彩繪 (parallel rendering) 系統的架構，並利用此系統來完成多重解析度模型的彩繪工作，尤指資料量龐大或複雜度高的精細模型。該平行彩繪系統乃是採用分散式系統的網路架構，並在叢集電腦 (PC cluster) 上實作而成。
在該平行彩繪系統中，各電腦之間以100Mbps的乙太網路相連結，同時利用我們發展的通訊協定，透過Winsock來達到資訊的交換，以提供處理大量資料時所需的運算能力與記憶體空間。
我們的平行彩繪系統所採用的影像平行演算法是sort-last演算法，該演算法可以提供較佳的擴充性，以利後續的研究發展。同時我們也採用OpenGL來完成實際彩繪的工作。
我們的平行彩繪系統支援離散性多重解析度 (discrete multiresolution) 的模型彩繪，以更進一步提昇彩繪的效率。

摘要(英)

A parallel rendering system is presented to render multiresolution models on a PC cluster. The system provides great memory capacity and calculation power for real-time visualization on large-amounted data such as terrain models.
The rendering system is implemented on a distributed architecture; all PCs in the cluster is connected by a 100Mbps Ethernet network. The information are exchanged using the protocol that we developed through Winsock to achieve the cooperation.
The parallel rendering algorithm is adopted from the sort-last strategy due to its high scalability and the rendering algorithm is implemented by OpenGL library.
The parallel rendering system supports the parallel rendering for discrete multiresolution models to improve the rendering performance.

關鍵字(中)

★ 彩繪
★ 多重解析度
★ 平行
★ 叢集電腦

關鍵字(英)

★ Parallel Rendering
★ Multiresolution
★ PC Cluster

論文目次

Abstract ii
Contents iii
List of Figures vi
List of Tables ix
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 System overview 2
1.2.1 System architecture 2
1.2.2 System diagram 4
1.3 Thesis organization 5
Chapter 2 Related Work 6
2.1 Introduction to massive computing system 6
2.2 Massive computing systems for 3D computer graphics 8
2.2.1 The hardware of the massive computing system 8
2.2.2 The applications on 3D computer graphics 10
2.3 Two methods of parallel rendering 11
2.4 Parallel rendering on different hardware architectures 12
Chapter 3 Parallel Rendering 14
3.1 Parallelism in the rendering process 14
3.1.1 Functional parallelism 15
3.1.2 Data parallelism 16
3.1.3 Temporal parallelism 18
3.1.4 Hybrid approaches 19
3.2 Algorithmic concepts 20
3.2.1 Coherence 21
3.2.2 Task and data decomposition 22
3.2.3 Scalability 24
3.2.4 Load balancing 25
3.2.5 Object-space to image-space mapping 29
3.3 Design and implementation issues 31
3.3.1 Hardware versus software systems 32
3.3.2 Communication 34
3.3.3 Image assembly and display 38
Chapter 4 Basic Implementation 44
4.1 Network issues 44
4.1.1 Sockets 44
4.1.2 Network capacity 45
4.2 System initialization 45
4.3 Partitioning strategy 46
4.3.1 Sort-last implementation 46
4.3.2 Improvement for network load on image data 48
4.3.3 Improvement for network load on control message 49
4.4 Image composition 50
Chapter 5 Advanced Implementation 53
5.1 More RPCs 53
5.2 Multiresolution model 55
Chapter 6 Experiments 56
6.1 Models 56
6.2 Experimental results 57
6.2.1 Operations on RPC 57
6.2.2 Operations on CPC 59
6.2.3 Browsing displays 61
6.3 Performance evaluation 65
Chapter 7 Conclusions and Future Work 71
7.1 Powerful hardware 71
7.2 Other technology 71
7.3 Other model formats 73
7.4 Different system architecture 73
7.5 Different work amount of RPC 74
References 75

參考文獻

[1] Agranov, G. and C. Gotsman, A Parallel System for Rendering Realistic Terrain Image Sequences, Technical report of Computer Science Dep., Technion - Israel Institute of Technology, Haifa, Israel, July 1994.
[2] Akeley, K. “Realityengine graphics,” in Proc. SIGGRAPH 1993, Anaheim, CA, Aug.1-6, 1993, pp.109-116.
[3] Badouel, D., K. Bouatouch, and T. Priol, “Distributing data and control for ray tracing in parallel,” IEEE Computer Graphics and Applications, vol.14, no.4, pp.69-77, July 1994.
[4] Bar-Lev, A., A. Itzkovitz, A. Raviv, and A. Schuster, “Vertex-to-vertex parallel radiosity on clusters of PCs,” in Workshop on Algorithm Engineering, Venice, Italy, Sep. 1997, pp.177-187.
[5] Bar-Lev, A., A. Itzkovitz, A. Raviv, and A. Schuster, “Parallel vertex-to-vertex radiosity on a distributed shared memory system,” in Proc. the Fifth Int’’l Symposium on Solving Irregularly Structured Problems in Parallel (IRREGULAR ’’98), Berkeley, California, Aug. 9-11, 1998, pp.238-250.
[6] Chen, H., Y. Chen, A. Finkelstein, T. Funkhouser, K. Li, Z. Liu, R. Samanta, and G. Wallace, “Data distribution strategies for high-resolution displays,” Computers & Graphics, Special Issue on Mixed Realities - Beyond Conventions, vol.25, no.5, pp.811-818, Oct.2001.
[7] Clark, J., “A VLSI geometry processor for graphics,” Computer, vol.13, no.7, pp.59-68, July 1980.
[8] Clark, J., “The Geometry Engine: a VLSI geometry system for graphics,” Computer Graphics, vol.16, no.3, pp.127-133, July 1982.
[9] Convex Computer Corporation, Convex Exemplar System Overview Richardson, TX, 1994.
[10] Cox, M. and P. Hanrahan, “A distributed snooping algorithm for pixel merging,” IEEE Parallel and Distributed Technology, vol.2, no.2, pp.30-36, 1994.
[11] Cray Research, Inc., Cray Animation Theater, 1994.
[12] Crockett, T. W., Design Considerations for Parallel Graphics Libraries, ICASE Report no.94-49 (NASA CR 194935), Institute for Computer Applications in Science and Engineering, Hampton, Virginia, June 1994.
[13] Crockett, T. W. and T. Orloff, “Parallel polygon rendering for message-passing architectures,” IEEE Parallel and Distributed Technology, vol.2, no.2, pp.17-28, 1994.
[14] Crockett, T. W., Parallel Rendering, ICASE Report no.95-31 (NASA Contractor Report 195080), Apr. 1995.
[15] Dowd, K., "High performance computing," O’’Reilly & Associated Inc., Cambridge, MA, June 1993.
[16] Ellsworth, D., “A new algorithm for interactive graphics on multicomputers,” IEEE Computer Graphics and Applications, vol.14, no.4, pp.33-40, July 1994.
[17] El-Sana, J., “Multi-user view-dependent rendering,” in Proc. the Conf. IEEE Visualization 2000, Salt Lake City, Utah, Oct.8-13, 2000, pp.335-342.
[18] Evans and Sutherland Computer Corporation, Freedom Series Technical Report, Salt Lake City, Utah, 1992.
[19] Flynn, M. J., "Very high-speed computing systems," Proc. of the IEEE, vol.54, no.12, pp.1901-1909, Dec. 1966.
[20] Fountain, T. J. and M. J. Shute, Multiprocessor Computer Architectures, North-Holland Inc., 1990.
[21] Fuchs, H. and J. Poulton, “Pixel-Planes: a VLSI-oriented design for a raster graphics engine,” VLSI Design, vol.2, no.3, pp.20-28, 1981.
[22] Fuchs, H., J. Poulton, J. Eyles, T. Greer, J. Goldfeather, D. Ellsworth, S. Molnar, G. Turk, B. Tebbs, and L. Israel, “Pixel-Planes 5: a heterogeneous multiprocessor graphics system using processor-enhanced memories.” Computer Graphics, vol.23, no.3, pp.79-88, July 1989.
[23] Giertsen, C. and J. Petersen, “Parallel volume rendering on a network of workstations,” IEEE Computer Graphics and Applications, vol.13, no.6, pp.16-23, Nov. 1993.
[24] Hughes, J. P., “HIPPI,” in Proc. 17th Conf. on Local Computer Networks, Minneapolis, MN, Sep. 1992, pp.346-354.
[25] Jensen, D. W. and D. A. Reed, “A performance analysis exemplar: parallel ray tracing,” Concurrency: Practice and Experience, vol.4, no.2, pp.119-141, Apr. 1992.
[26] Kaba, J., J. Matey, G. Stoll, H. Taylor, and P. Hanrahan, “Interactive terrain rendering and volume visualization on the Princeton Engine,” in Proc. Visualization ‘92, Los Alamitos, CA, Oct. 1992, pp.349-355.
[27] Kessler, R. E. and J. L. Schwarzmeier, “Cray T3D: a new dimension for Cray Research,” in Proc. COMPCON Spring ‘93, San Francisco, CA, Feb. 1993, pp.176-182.
[28] Lee, T.-Y., C. S. Raghavendra, J. B. Nicholas, “Image composition schemes for sort-last polygon rendering on 2D mesh multicomputers”, IEEE Transactions on Visualization and Computer Graphics, vol.2, no.3, Sep. 1996.
[29] Lenoski, D., J. Laudon, K. Gharachorloo, W.-D. Weber, A. Gupta, J. Hennessy, M. Horowitz, and M. S. Lam, “The stanford dash multiprocessor,” Computer, vol.25, no.3, pp.63-79, Mar. 1992.
[30] Ma, K.-L., J. S. Painter, C. D. Hansen, and M. F. Krogh, “Parallel volume rendering using binary-swap compositing,” IEEE Computer Graphics and Applications, vol.14, no.4, pp.59-68, July 1994.
[31] Mackerras, P. and B. Corrie, “Exploiting data coherence to improve parallel volume rendering,” IEEE Parallel and Distributed Technology, vol.2, no.2, pp.8-16, Summer 1994.
[32] Molnar, S., J. Eyles, and J. Poulton, “PixelFlow: high-speed rendering using image composition,” Computer Graphics, vol.26, no.2, pp.231-240, July 1992.
[33] Molnar, S., M. Cox, D. Ellsworth, and H. Fuchs, “A sorting classification of parallel rendering,” IEEE Computer Graphics and Applications, vol.14, no.4, pp.23-32, July 1994.
[34] Neumann, U., “Communication costs for parallel volume-rendering algorithms,” IEEE Computer Graphics and Applications, vol.14, no.4, pp.49-58, July 1994.
[35] Nishimura, H., H. Ohno, T. Kawata, I. Shirakawa, and K. Omura, “LINKS-1: a parallel pipelined multicomputer system for image creation,” in Proc. 10th Annual Int. Sym. on Computer Architecture, Stockholm, Sweden, Jun. 1983, pp.387-394.
[36] Ortega, F. A., C. D. Hansen, and J. P. Ahrens, “Fast data parallel polygon rendering,” in Proc. Supercomputing ‘93, Portland, Oregon, Nov. 1993, pp.709-718.
[37] Pixar Animation Studios, PhotoRealistic RenderMan Toolkit v3.5 Reference Manual, Richmond, CA, 1994.
[38] Potmesil, M. and E. M. Hoffert, “The pixel machine: a parallel image computer,” Computer Graphics, vol.23, no.3, pp.69-78, July 1989.
[39] Puech, C., F. Sillion, and C. Vedel, “Improving interaction with radiosity-based lighting simulation programs,” Computer Graphics, vol.24, no.2, pp.51-57, Mar. 1990.
[40] Recker, R. J., D. W. George, and D. P. Greenberg, “Acceleration techniques for progressive refinement radiosity,” Computer Graphics, vol.24, no.2, pp.59-66, Mar. 1990.
[41] Ross, F. E., “An overview of FDDI: the fiber distributed data interface,” IEEE Journal on Selected Areas in Communications, vol.7, no.7, pp.1043-1051, Sep. 1989.
[42] Salmon, J. and J. Goldsmith, “A hypercube ray-tracer,” in Proc. of the Third Conf. on Hypercube Concurrent Computers and Applications, Pasadena, California, Jan. 19-20, 1988, vol.2, pp.1194-1206.
[43] Samanta, R. and T. A. Funkhouser, Dynamic Algorithms for Sorting Primitives Among Screen-Space Tiles in a Parallel Rendering System, Technical Report, Department of Computer Science, Princeton University, Oct. 1998.
[44] Samanta, R., T. Funkhouser, K. Li, and J. P. Singh, “Sort-first parallel rendering with a cluster of PCs,” Sketch at SIGGRAPH 2000, New Orleans, Louisiana, July 2000.
[45] Samanta, R., T. Funkhouser, K. Li, and J. P. Singh, “Hybrid sort-first and sort-last parallel rendering with a cluster of PCs,” in Proc. SIGGRAPH/Eurographics Workshop on Graphics Hardware, Interlaken, Switzerland, Aug.21-22, 2000, pp.99-108.
[46] Samanta, R., T. Funkhouser, and K. Li, “Parallel rendering with K-way replication,” in Proc. IEEE 2001 Symposium on Parallel and Large-Data Visualization and Graphics, San Diego, California, Oct. 2001.
[47] Shoch, J. F., Y. K. Dalal, and D. D. Redell, “Evolution of the ethernet local computer network,” Computer, vol.15, no.8, pp.10-27, Aug. 1982.
[48] Silva, C. T., and A. E. Kaufman, “Parallel performance measures for volume ray casting,” in Proc. Visualization ‘94, Washington, DC, Oct. 1994, pp.196-203.
[49] Sutherland, I. E., R. F. Sproull, and R. A. Schumacker, “A characterization of ten hidden-surface algorithms.” Computing Surveys, vol.6, no.1, pp.1-55, Mar. 1974.
[50] Teng, A., S. Whitman, and M. Lee, “STREN：a highly scalable parallel stereo terrain renderer for planetary mission simulations,” in Proc. SuperComputing ’’96, Pittsburgh, PA, Dec., 1996.
[51] Vetter, R. J., “ATM concepts, architectures, and protocols,” Communications of the ACM, vol.38, no.2, pp.30-38, Feb. 1995.
[52] Whelan, D. S. Animac: A Multiprocessor Architecture for Real-Time Computer Animation, Ph.D. dissertation, Computer Science Dept., California Institute of Technology, 1985.
[53] Whitman, S., Multiprocessor Methods for Computer Graphics Rendering. Jones and Bartlett Publishers, Boston, MA, 1992.
[54] Whitman, S., “Dynamic load balancing for parallel polygon rendering,” Computer Graphics and Applications, vol.14, no.4, pp.41-48, July 1994.
[55] Wittenbrink, C. M. and A. K. Somani, “Time and space optimal data parallel volume rendering using permutation warping,” Journal of Parallel and Distributed Computing, vol.46, no.6, pp.148-164, Nov. 1997.
[56] http://www.beowulf.org/
[57] http://www.linux.org.tw/CLDP/Beowulf-HOWTO-2.html
[58] http://www.se.ntou.edu.tw/~ylchang/

指導教授

曾定章(Din-Chang Tseng)

審核日期

2002-7-12

推文