跳到主要內容

臺灣博碩士論文加值系統

(44.192.22.242) 您好!臺灣時間:2021/08/05 13:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:王唯任
研究生(外文):Wei-RenWang
論文名稱:低複雜度適應性曲線細分之超大型積體電路設計
論文名稱(外文):Low-Complexity VLSI Design of Adaptive Tessellation
指導教授:謝明得謝明得引用關係
指導教授(外文):Ming-Der Shieh
學位類別:碩士
校院名稱:國立成功大學
系所名稱:電機工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:64
中文關鍵詞:向量繪圖步進式降階貝茲曲線曲線細分
外文關鍵詞:Vector graphicsStepwise degree reductionBezier curveTessellation
相關次數:
  • 被引用被引用:0
  • 點閱點閱:161
  • 評分評分:
  • 下載下載:7
  • 收藏至我的研究室書目清單書目收藏:0
現今向量繪圖在嵌入式系統的應用下越趨重要,在二維向量繪圖中,貝茲曲線已被廣泛的應用為繪圖物件的成員,而曲線的繪製需要用分段且連續的直線來近似,稱作曲線細分(tessellation),之後再執行點陣化(rasterization)的運算;若使用均勻取樣的方式來進行曲線細分,往往會造成過多的邊緣資訊,而增加了邊緣記憶體大小及記憶體存取次數。相較而言,適應性的曲線細分方式則能有效的根據曲線局部的曲率調整近似線段的數量,如何開發適合硬體實現的適應性演算法即為一重要課題。
本論文主要是探討基於貝茲曲線的步進式降階演算法,著重於將三次曲線降階成許多二次曲線後,再對每條二次曲線使用點偏移(point offsetting)的近似方法降低曲線近似的誤差,並減少近似線段的數量,在相近的圖形品質下,所提出的方法可明顯減少邊緣數量。步進式降階通常使用遞迴式切割(recursive subdivision)的方式實現,然而在硬體實現上,切割演算法將導致輸出率不固定且需要額外的記憶體堆疊(memory stack)。針對此問題,本篇論文探討以正向差分為基礎的方式來進行計算,以得到低複雜度且輸出率較固定的曲線細分單元。相較於固定點數的正向差分,本論文所提出的方法可以減少所需的近似線段數目並適合硬體的實現;對於使用大量貝茲曲線的圖形而言,將可大幅減少邊緣記憶體的存取次數,並降低總運算時間。所提出之架構已經在以ARM926EJ為核心及Xilinx Vertex-5 FPGA之虹晶SCDK平台上完成驗證。

Nowadays vector graphics have become important in embedded systems. In two-dimensional vector graphics, Bézier curves are widely used as one member of graphic objects. Curve rendering requires continuously piecewise linear approximation called tessellation, and rasterization follows afterward. If the tessellation uses a uniformly-sampled method, it normally results in excessive edge data, thus increasing the edge memory size and memory access times. Comparatively, adaptive tessellation may effectively configure and approximate line segments by the local curvature of curves. Therefore, exploring a hardware-friendly adaptive tessellation algorithm is a significant topic in graphics-related applications.
This study transforms a cubic curve to a set of quadratic ones based on the stepwise degree reduction algorithm for Bézier curves. A point offsetting method is then applied for linear approximation of each quadratic curve which contributes to the error reduction and approximated segment number. The proposed method can decrease the number of edges under the constraint of similar image qualities. The stepwise degree reduction algorithm is generally implemented using the recursive subdivision algorithm which results in an unstable throughput and induces memory stack in hardware implementation. This thesis derives an efficient computation method based on the forward differencing in order to reach a tessellation design with low complexity and stable throughput. Compared to the conventional forward difference method with a fixed segment count, the proposed one can reduce the number of approximated segments and is suitable for hardware implementation. For an image containing many bézier curves, the proposed method will decrease the edge memory access times as well as the computation time. The associated design has been verified on the Socle SCDK platform with an ARM926EJ core and Xilinx Vertex-5 series FPGA.

摘   要 iii
ABSTRACT v
誌  謝 vii
目  錄 viii
表 目 錄 x
圖 目 錄 xi
第一章 緒論 1
1.1 研究動機 1
1.2 論文架構 2
第二章 背景知識介紹 3
2.1向量繪圖介紹 3
2.1.1 二維向量繪圖基本概念 3
2.1.2 OpenVG標準 4
2.1.3 曲線細分單元功能 4
2.2貝茲曲線 6
2.2.1 定義 6
2.2.2 De Casteljau演算法 7
2.2.3 貝茲曲線的升階 8
2.3 貝茲曲線細分演算法 9
2.3.1 正向差分演算法 9
2.3.2 適應性正向差分運算 10
2.3.3 遞迴式分割演算法 11
2.3.4 迭代式分割演算法 13
2.4 貝茲曲線降階演算法 15
2.4.1 貝茲曲線的降階 16
2.4.2 步進式降階演算法 18
第三章 基於正向差分及點偏移方法 之步進式降階演算法 20
3.1 步進式降階演算法實現問題 20
3.2 三次曲線降階之正向差分運算 20
3.2.1 三次曲線控制點之正向差分運算 21
3.2.2 降為二階曲線後之正向差分運算 22
3.3 二階曲線之點偏移演算法 24
3.3.1 誤差模型之分析 24
3.3.2 點偏移的概念 26
3.3.3 第一型點偏移探討及其正向差分運算 29
3.3.4 第二型點偏移探討及其正向差分運算 33
3.3.5 整體細分演算法 37
第四章 實驗結果比較與硬體實現 40
4.1 演算法的分析比較 40
4.1.1 降階演算法的比較 40
4.1.2 曲線細分演算法的比較 45
4.2 硬體架構設計與實現 50
4.2.1 整體架構說明 50
4.2.2 降階參數運算 53
4.2.3 正向差分運算 55
4.3實現結果與分析比較 57
第五章 結論與未來展望 61
5.1 結論 61
5.2 未來展望 61
參考文獻 62


[1]OpenVG 1.1 specification, Khronos Group Inc., Dec. 3, 2008.
[2]J. H. Park, K. Y. Lee, and J. C. Kwak, “A design of OpenVG 2D vector graphics accelerator for a mobile device, in Proc. Int. Tec. Conf. Circuts/Sys. Comput. Commun., 2008, pp. 1633-1636.
[3]R. Huang and S. Chae, “Implementation of an OpenVG rasterizer with configurable anti-aliasing and multi-window scissoring, in Proc. IEEE Int. Conf. Comput. Inf. Tech., Sep. 2006, pp. 179-184.
[4]D. Kim, K. Cha, and S. Chae, “A high-performance OpenVG accelerator with dual-scanline filling rendering, IEEE Trans. Consum. Electro., vol. 54, no. 3, pp. 1303-1311, Aug. 2008.
[5]K. Cha, D. Kim, and S. Chae, “An optimized rendering algorithm for hardware implementation of openVG 2D vector graphics, in Proc. IEEE SoC Design Conf., vol. 1, 2008, pp. 338-341.
[6]S. H. Kim, Y. Oh, K. Park, and W. W. Ro, “Hardware implementation of a tessellation accelerator for the OpenVG standard, IEICE Electron. Express, vol. 7, no. 6, pp. 440-446, Mar. 2010.
[7]S. W. Seo, Y. L. Shen, K. Y. Kim, and H. C. Oh, “Scanline–based rendering of 2D vector graphics, IEICE Electron. Express, vol. 8, no. 11, pp. 788-794, Mar. 2011.
[8]Y. L. Shen, S. W. Seo, Y. Zhang, and et al, “A low hardware cost 2D vector graphic rendering algorithm for supersampling antialiasing, in Proc. IEEE Int. Workshop Edu. Tech. Comput. Sci., 2010, pp. 141-144.
[9]E. Angel, Interactive Computer Graphics: A Top-Down Approach Using OpenGL, 5th ed.Boston: Addison-Wesley, 2009.
[10]S. L. Lien, M. Shantz, and V. Pratt, “Adaptive forward differencing for rendering curves and surfaces, in Proc. ACM 14th Annual Conf. Comput. Graph. and Interactive Tech., vol. 21, no. 4, July 1987, pp. 111-118.
[11]S. L. Chang, M. Shantz, and R. Rocchetti, “Rendering cubic curves and surfaces with integer adaptive forward difference, in Proc. ACM 16th Annual Conf. Comput. Graph. and Interactive Tech., vol. 23, no. 3, 1989, pp. 157-166.
[12]R. Ari, “Rendering curves and surfaces with hybrid subdivision and forward differencing, ACM Trans. Graph., vol. 10, no. 4, pp. 323-341, Oct. 1987.
[13]T. F. Hain, A. Ahmad, and D. D. Langan, “Precise flattening of cubic Bézier segments, in Proc. of Canadian Conf. Computational Geom., Montreal, Canada, Aug 2004.
[14]J. Zheng, T. W. Sederberg, “Estimating tessellation parameter intervals for rational curves and surfaces, ACM Trans. Graph., vol 19, no. 1, pp. 56-77, Jan. 2000.
[15]D. Filip, R. Magedson, and R. Markot, “Surface algorithms using bounds on derivatives, Comput.-Aided Geom. Des., vol. 3, no. 4, pp. 295-311, Dec. 1986.
[16]M. Eck, “Degree reduction of Bézier curves, Comput.-Aided Geom. Des., vol. 10, no. 3-4, pp. 237-251, Aug. 1993.
[17]M. Eck, “Least squares degree reduction of Bézier curves, Comput.-Aided. Des., vol. 27, no. 11, pp. 845-851, Nov. 1995.
[18]M. Eck, “The geometry of optimal degree reduction of Bézier curves, Comput.-Aided. Geom. Des., vol. 13, no. 8, pp. 773-788, Nov. 1996.
[19]R. J. Zhang and W. Y. Ma, “Consolidated sharp bounds for Bezier curve approximation with cutdown polygon and corner cutting polygon, Comput. Aided Geom. Des., vol. 27, no. 5, pp. 382-394, June 2010.
[20]Y.N. Chang, “A fast spline curve rendering accelerator architecture, IEEE Trans. Circuits and Sys. II: Express Briefs, vol.56, no.11, pp.870-874, Nov. 2009.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top