現今向量繪圖在嵌入式系統的應用下越趨重要，在二維向量繪圖中，貝茲曲線已被廣泛的應用為繪圖物件的成員，而曲線的繪製需要用分段且連續的直線來近似，稱作曲線細分(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.

[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.