臺灣博碩士論文加值系統

3D繪圖系統已經在桌上型電腦平台發展一段時日，所顯示出來的3D效果也相當的驚人。但由於需要大面積矽晶片以放置大量的運算元件，且擁有高溫、耗電等特性，使其無法被順利的整合在攜帶型電子產品之中。然而，隨著嵌入式系統的快速發展、硬體製程的進步、和消費性及攜帶性產品上對於3D繪圖的應用需求的大量增加，如何在這樣的產品中設計一個低成本的3D繪圖加速硬體已成為一項重要的課題。
一般的3D繪圖硬體中，依處理階段的不同，可分為前半部的Geometry engine跟後半部的Rasterization engine。本論文根據砌塊式繪圖架構為基礎，設計出一高效率之Rasterization engine。此引擎擁有以下幾點特點：使用tile-boundary skip traversal進行三角形掃描、使用barycentric coordinate轉換三角形座標進行內插、使用multi Z test和6D block texture cache等功能。這些特點使得RE硬體可以在維持一定繪圖品質的前提下，同時減少硬體設計面積跟提高硬體效能。本論文最後所完成之合成後RTL模型，可在QEMU全系統驗證平台下，以時脈200MHz和OpenGL ES應用程式軟體、Linux作業系統、geometry engine進行軟硬體協同模擬驗證，成功完成一可適用於嵌入式系統之3D繪圖引擎。

3D graphic rendering system for desktop has been developed for a long time and has the capability to show amazing 3D effect. However, this system is hard to be integrated with mobile electronic products because of its large-area requirement, high temperature, and high-power consumption. Due to the rapid development of embedded system and hardware technology, and increasing demand of 3D graphic applications for consumer electronic, how to design a low-cost 3D graphic accelerator has become an important issue.
A typical 3D graphic accelerator can be divided into a geometry engine and a rasterization engine by the different processing stages. In this thesis, a highly efficient rasterization engine based on tile-based architecture is proposed. This engine has incorporated the following architecture techniques: tile-boundary skip traversal, barycentric coordinate, multi Z test, and 6D block texture cache. With these features, we reduce the area cost and improve the performance of the rasterization engine we design. The rasterization engine when synthesized with TSMC 0.18um technology can run up to 200MHz. We also verify the entire 3D graphic accelerator net-list with OpenGL ES application in Linux OS under a full system simulation platform constructed with CoWare and QEMU.

摘要 I
Abstract II
誌謝 III
目錄 IV
圖目錄 VII
表目錄 X
第1章 Introduction 1
1.1 Motivation 1
1.2 Contribution 1
1.3 Organization 2
第2章 Background and related work 3
2.1 3D Computer Graphic 3
2.2 Graphic application programming interface 4
2.2.1 OpenGL API 5
2.2.2 OpenGL ES 6
2.3 Conventional OpenGL pipeline 6
2.3.1 Geometry Stage 7
2.3.2 Rasterization Stage 9
2.4 Tile-Based rendering pipeline 14
2.5 Related work 15
2.5.1 Tile-based architecture 15
2.5.2 Conventional immediate mode architecture 16
第3章 Rasterization algorithm exploration 18
3.1 Edge function and Traversal 18
3.1.1 Edge function test 18
3.1.2 Traversal algorithm 20
3.1.3 Traversal method for tile-based architecture 22
3.1.4 A defect of tile-bounding skip traversal we proposed 24
3.1.5 Performance of tile bounding skip traversal 26
3.2 Interpolation 27
3.2.1 Plane equation 28
3.2.2 Plane equation with fixed-point calculation 29
3.2.3 Interpolation using barycentric coordinates 31
3.3 Anti-Aliasing(AA) 33
3.4 Texture mapping 38
3.5 Per-fragment operation 39
第4章 Architecture development 41
4.1 Texture cache 42
4.1.1 6D block texture cache 42
4.1.2 Simulation of texture cache 43
4.1.3 Summary of texture cache 45
4.2 Early depth test 46
4.2.1 Alpha test with early depth test 46
4.2.2 Data hazard in separated early depth test 49
4.2.3 Multi Z test 50
4.2.4 Simulation and summery of early depth test 52
4.3 RM Architecture summery 53
第5章 RTL implementation 54
5.1 Triangle setup 55
5.2 Rasterizer 56
5.3 Per-fragment operation 59
5.4 Summery of RTL implementation 60
第6章 Simulation and verification 61
6.1 Simulation platform 61
6.1.1 Simulation model 62
6.1.2 Full system simulation platform for RTL model 63
6.2 Verification methodology 66
6.3 Simulation and verification result 67
6.3.1 Simulation result 67
6.3.2 Verification result 70
第7章 Conclusion and future work 73
7.1 Conclusion 73
7.2 Future work 74
Reference 75

[1]Jen-Kai Cho, “Multi-view Image Generation Using Compensated Depth-Image-Based Rendering for 3D Displays,” Master’s Thesis, Institute of Computer and Communication Engineering, National Cheng Kung University, 2007.
[2]Vincent Mobile 3D Rendering Library. Available:
http://sourceforge.net/projects/ogl-es/
[3]M. Segal and K. Akeley, “The OpenGL Graphics System: A Specification Version 2.1,” Silicon Graphics, Inc,
http://www.opengl.org/registry/doc/glspec21.20061201.pdf
[4]R. S. Wright, Jr., and B. Lipchark, OpenGL SuperBible, 3rd edition. Sams Publishing, 2005.
[5]Microsoft Corp., DirectX Resource Center,
http://msdn2.microsoft.com/zh-tw/xna/aa937781.aspx
[6]D. Blythe and A. Munshi, “OpenGL ES Common/Common-Lite Profile Specification Version 1.1.10,” Khronos Group, Inc. Available: http://www.khronos.org/registry/gles/specs/1.1/es_full_spec.1.1.10.pdf
[7]K. Pulli et al., Mobile 3D Graphic, MK publishing, 2008.
[8]G. Humphreys et al., “Chromium: A Stream Processing Framework for Interactive Rendering on Clusters,” In Proc. 29th Annual Conf. on Computer Graphics and Interactive Techniques (SIGGRAPH 2002), pp. 693–702, 2002.
[9]S. Molnar, M. Cox, D. Ellsworth, and H. Fuchs, “A Sorting Classification of Parallel Rendering,” In IEEE Comput. Graph. Appl., vol 14(4), pp. 23–32, 1994.
[10]H. Fuchs, et al., "Pixel-planes 5: A Heterogeneous Multiprocessor Graphics System Using Processor-Enhanced Memories," In Proc. ACM SIGGRAPH, pp. 79-88, 1989.
[11]Image Technologies Ltd, STMicroelectronics KYRO™ and KYRO II™ PowerVR 3D Graphics Accelerator,
http://www.imgtec.com/corporate/newsdetail.asp?NewsID=252
[12]T. Akenine-Moller and E. Haines, Real-time rendering, 2nd edition. A. K. Peters, Ltd, Natick, MA, 2002.
[13]A. Stevens, White paper: ARM Mali 3D Graphics System Solution, December 2006, http://www.arm.com/miscPDFs/16514.pdf
[14]Imagination Technologies Ltd., PowerVR MBX 2D/3D Graphics, http://www.imgtec.com/Downloads/index.asp?download=true&f=PowerVRMBX.pdf&t=PowerVR%20PDP%20Documents
[15]AMD&ATI Ltd, Xenos: XBOX360 GPU,
http://ati.amd.com/developer/eg05-xenos-doggett-final.pdf
[16]L. Seiler et al., “Larrabee: a many-core x86 architecture for visual computing.” ACM Trans. Graphics (Proc. SIGGRAPH ‘08), vol.27, no. 3, Aug. 2008.
[17]D. Kim et al., “An SoC with 1.3Gtexels/s 3D Graphics Full Pipeline Engine for Consumer Applications,” In IEEE J. Solid-State Circuits, vol. 41, pp. 71, Jan. 2006.
[18]J. Pineda, “A parallel algorithm for polygon rasterization,” In Proc. 15th annual conference on Computer graphics and interactive techniques, p.17-20, June 1988, http://portal.acm.org/citation.cfm?id=378457&dl=GUIDE&coll=GUIDE&CFID=43594580&CFTOKEN=14674529
[19]P. Shirley, “Physically Based Lighting Calculations for Computer Graphics,” PhD thesis, University of Illinois at Urbana Champaign, 1990.
[20]M. Cox, N. Bhandari, and M. Shantz, "Multi-level caching for 3D graphics hardware,” In Proc. 25th Annual International Symposium on Computer Architecture (ISCA'98), pp 86-97, 1998.


[21]Z. S. Hakura and A. Gupta. “The design and analysis of a cache architecture for texture mapping,” In Proc. 24th annual international symposium on Computer architecture (ISCA '97), pp108-120, 1997.
[22]C. J. Choi et al., "Performance comparison of various cache systems for texture mapping," High Performance Computing in the Asia-Pacific Region, 2000. Proceedings. The Fourth International Conference/Exhibition on, vol.1, no., pp.374-379 vol.1, 2000.
[23]H. Igehy et al, “Prefetching in a texture cache architecture,” In Proc. ACM SIGGRAPH / EUROGRAPHICS conference on Graphics Hardware, pp. 133-142, 1998.
[24]S. Morein, “ATI Radeon - HyperZ Technology,” Hot3D Session 2000 Eurographics Workshop Computer Graphics Hardware, 2000,
http://www.graphicshardware.org/previous/www_2000/presentations/ATIHot3D.pdf
[25]NVidia, “Technical Briefs: An In-Depth Look at Geforce3 Features,” http://www.nvidia.com/Products/GeForce3.nsf /technical.html
[26]W.-C. Park et al., "An effective pixel rasterization pipeline architecture for 3D rendering processors," In Proc. IEEE Transactions on Computers, vol.52, no.11, pp. 1501-1508, Nov. 2003
[27]D. A. Patterson and J. L. Hennessy, Computer Organization and Design, 3rd edition, MK publishing, 2005.
[28]Synopsys, DesignWare IP Family Reference Guide,
https://www.synopsys.com/dw/doc.php/doc/dwf/datasheets/dw_div_pipe.pdf
[29]Design Compiler, http://www.synopsys.com/home.aspx
[30]CoWare Platform Architecture,
http://www.coware.com/products/platformarchitect.php
[31]QEMU Processor Emulator, official site : http://bellard.org/qemu/