臺灣博碩士論文加值系統

虛擬模型廣泛地出現在手機遊戲或者電影動畫製作中，其中以使用高畫質貼圖成像對於使用者的感受尤其重要。然而，三維遊戲引擎往往需要較高的資訊儲存量，但是，在網路傳輸上又需要低檔案大小才能節省成本。因此，本研究使用向量圖(Vector Image) ，一種有別於傳統點陣圖(Raster Image)，以點、直線或者是多邊形等數學方程的幾何圖形來表達圖像，任意放大向量圖仍然不會遺失細節或影響清晰度，以克服使用高解析度點陣圖需要更高記憶體空間的問題。本研究提出了全域優化(Global Optimization)，優化了原始的網格結構以降低網格重構法的限制(Constraints)、修正流場計算使其能產生平順的流場線，並且大幅減少重構後網格的面數，以達到精簡網格但保有品質的結果。同時，整合了賀麥片塊(Hermite Patch) 與拓樸渲染器(Tessellation Shader)，將圖像與三維模型的幾何特徵(Geometrical Features)轉換成賀麥片塊(Hermite Patch) 資料型態用以儲存，在渲染階段時，根據視角自動決定了渲染時取樣點(Sample Points)的密度，藉由簡單的矩陣計算決定取樣點的位置與顏色，達成即時渲染的結果。本研究與最先進技術(State-of-The-Art) 以檔案大小、渲染幀率(Frame per Second，FPS)、均方差(Mean squared error，MSE)與網格品質(Mesh Quality)做比較驗證。結果在渲染幀率(FPS)與均方差(MSE)的比較上，本研究與其他皆無太大的落差甚或有領先，但是檔案大小卻減少了將近一半且網格品質分數皆比其他高。因此，本研究可以達成商業遊戲的要求，不僅可以完成即時且無失真之渲染，還可以大量降低啟動應用所需的資料量。

3D models are widely found in mobile games and animation films, where the quality of textures impacts hugely on the audience's perception of a work's aesthetic quality. However, 3D game engines require high storage capacity, resulting in huge cost for data transferring over the internet. Therefore, this study exploits vector images, which is another image format for representing an image. With geometry primitives such as points, straight lines and polygons, vector images are able to represent pictures while enabling arbitrary amplification without lose of detail or blurring the picture, and thus, overcoming the problems of using high-resolution raster images that require higher memory space.

This study proposes a global optimization method, which optimizes the original mesh structure to reduce the constraints of the mesh reconstruction method. The method then corrects the flow field calculations to produce smooth flow field lines, and significantly reduces the size of the grid number of the mesh to achieve a compact mesh but keep the quality of the results.At the same time, integrating the Hermite patch and tessellation shader, converting the image and geometrical features of 3D model into Hermite patch structure for storage.In the rendering stage, according to the perspective of the rendering time to automatically determine the sampling density, and then determine the location and color of the sample points with a simple matrix calculation to achieve the results of real-time rendering.

This study considers file size, frame per second, mean squared error and mesh quality while comparing the results with other the-state-of-the-art methods. The differences in FPS and MSE of our results to other compared methods' results show there is no significant difference between ours and the other, while the size of the file is reduced by almost half and the mesh quality score is higher than others' results. Therefore, the results of proposed method can comply with the industry standards of mobile games, meaning our results can be rendered in real-time without lose of details and drastically accelerates the start-up process of game applications.

中文摘要 - i
Abstract - ii
目錄 - iv
表目錄 - vi
圖目錄 - vii
符號標記使用說明 - ix
1 介紹 - 1
1.1 問題定義 - 2
1.2 主要貢獻 - 3
1.3 論文架構 - 4
2 相關研究 - 5
2.1 向量圖渲染與圖形處理器加速 - 5
2.2 基於向量化的貼圖 - 6
2.3 嵌於模型中之基於向量化的貼圖 - 7
2.4 網格重構法 - 8
3 方法總覽 - 10
4 顏色片塊結構建立 - 12
4.1 顏色單元(Color Unit) - 12
4.2 顏色片塊(Color Patch) - 15
5 基於流場之網格重構法 - 19
5.1 顏色片塊之流場計算 - 19
5.1.1 標號設定 - 19
5.1.2 流場限制(Constraints)與解流場(Solving) - 23
5.2 等間距流場線之建立 - 24
5.2.1 控制流場線追蹤間距(Control of Separating Distance of Streamlines) - 24
5.2.2 種子點之選擇(Seed Points Selection) - 26
5.3 流場線限制之網格重構法 - 28
6 重構資訊嵌入網格後即時渲染 - 30
6.1 賀麥片塊(Hermite Patch)結構 - 30
6.2 資訊嵌入重構網格 - 31
6.3 拓樸渲染器(Tessellation Shader)之即時渲染 - 35
7 實驗結果與討論 - 40
8 結論與未來工作 - 51
參考文獻 - 53

[1] K. Kerr, "Introducing direct2d," 2009.
[2] G. Ramanarayanan, K. Bala, B. Walter, "Feature-based textures," in Proceedings of the 15th Eurographics Conference on Rendering Techniques, EGSR'04, pp. 265-274, 2004.
[3] Freescale, Multimedia Application Division, "i.mx35 accelerated 2d graphics: Optimizing 2d graphics with openvg and i.mx35," 2010.
[4] R. Huang, S. Chae, "Implementation of an openvg rasterizer with cofigurable anti-aliasing and multi-window scissoring," in Proceedings of the 6th IEEE International Conference on Computer and Information Technology, CIT '06, pp. 179-179, 2006.
[5] D. Kim, K. Cha, S. Chae, "A high-performance openvg accelerator with dual-scanline filling rendering," IEEE Transactions on Consumer Electronics, vol. 54, no. 3, pp. 1303-1311, 2008.
[6] Y. Kokojima, K. Sugita, T. Saito, T. Takemoto, "Resolution independent rendering of deformable vector objects using graphics hardware," in ACM SIGGRAPH 2006 Sketches, SIGGRAPH '06, p. 108, 2006.
[7] A. J. Rued, J. Ruiz de Miras, F. R. Feito, "Gpu-based rendering of curved polygons using simplicial coverings," Computers & Graphics, vol. 32, no. 5, pp. 581-588, 2008.
[8] M. Kilgard, J. Bolz, "Gpu-accelerated path rendering," ACM Transactions on Graphics (TOG), vol. 31, no. 6, pp. 172:1-172:10, 2012.
[9] P. Sen, M. Cammarano, P. Hanrahan, "Shadow silhouette maps," ACM Transactions on Graphics (TOG), vol. 22, no. 3, pp. 521-526, 2003.
[10] P. Sen, "Silhouette maps for improved texture magnification," in Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware, HWWS '04, pp. 65-73, 2004.
[11] J. Tumblin, P. Choudhury, "Bixels: Picture samples with sharp embedded boundaries," in Proceedings of the Fifteenth Eurographics Conference on Rendering Techniques, EGSR'04, pp. 255-264, 2004.
[12] S. Lefebvre, H. Hoppe, "Perfect spatial hashing," ACM Trans. Graph., vol. 25, no. 3, pp. 579-588, 2006.
[13] S. Lefebvre, H. Hoppe, "Compressed random-access trees for spatially coherent data," in Proceedings of the 18th Eurographics Conference on Rendering Techniques, EGSR'07, pp. 339-349, 2007.
[14] M. Tarini, P. Cignoni, "Pinchmaps: Textures with customizable discontinuities, "Computer Graphics Forum, vol. 24, no. 3, pp. 557-568, 2005.
[15] J. Loviscach, "Efficient magnification of bi-level textures," ACM SIGGRAPH 2005 Sketches, p. 131, 2005.
[16] N. Ray, T. Neiger, B. Levy, X. Cavin, "Vector texture maps on the gpu," tech. rep.
[17] Z. Qin, M. D. Mccool, C. S. Kaplan, "Real-time texture-mapped vector glyphs," in Proceedings of the 2006 Symposium on Interactive 3D Graphics and Games, I3D '06, pp. 125-132, 2006.
[18] S. Jeschke, D. Cline, P. Wonka, "Rendering surface details with diffusion curves," ACM Transactions on Graphics (TOG), vol. 28, no. 8, pp. 117:1-117:8, 2009.
[19] D. Nehab, H. Hoppe, "Random-access rendering of general vector graphics," ACM Transactions on Graphics (TOG), vol. 27, no. 5, pp. 135:1-135:10, 2008.
[20] Z. Qin, M. D. McCool, C. Kaplan, "Precise vector textures for real-time 3d rendering," in Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games, I3D '08, pp. 199-206, 2008.
[21] C. Loop, J. Blinn, "Resolution independent curve rendering using programmable graphics hardware," ACM Transactions on Graphics (TOG), vol. 24, no. 3, pp. 1000-1009, 2005.
[22] R. Santina, "Resolution independent nurbs curves rendering using programmable graphics pipeline," vol. PP, pp. 70-73, 2011.
[23] S. Boye, P. Barla, G. Guennebaud, "A vectorial solver for free-form vector gradients," ACM Transactions on Graphics (TOG), vol. 31, no. 6, pp. 173:1-173:9, 2012.
[24] C. Y. Yao, K. Y. Chen, H. N. Guo, J. C. Li, Y. C. Lai, "Resolution independent real-time vector embedded mesh for animation," IEEE Transactions on Circuits and Systems for Video Technology, vol. PP, no. 99, pp. 1-1, 2016.
[25] T. K. Dey, G. Li, T. Ray, "Polygonal surface remeshing with delaunay refinement," Engineering with Computers, vol. 26, no. 3, pp. 289-301, 2005.
[26] S. Dong, S. Kircher, M. Garland, "Harmonic functions for quadrilateral remeshing of arbitrary manifolds," Computer Aided Geometric Design, vol. 22, no. 5, pp. 392-423, 2005.
[27] M. Attene, B. Falcidieno, J. Rossignac, M. Spagnuolo, "Edge-sharpener: Recovering sharp features in triangulations of non-adaptively remeshed surfaces," SGP '03, pp. 62-69, 2003.
[28] P. Alliez, D. Cohen-Steiner, O. Devillers, B. Levy, M. Desbrun, "Anisotropic polygonal remeshing," ACM Transactions on Graphics (TOG), vol. 22, no. 3, pp. 485-493, 2003.
[29] R. Maharik, M. Bessmeltsev, A. Sheffer, A. Shamir, N. Carr, "Digital micrography," ACM Transactions on Graphics (TOG), vol. 30, no. 4, pp. 100:1-100:12, 2011.
[30] B. Jobard, W. Lefer, M. Grave, Creating Evenly-Spaced Streamlines of Arbitrary Density. Vienna: Springer Vienna, 1997.
[31] Y. Avrithis, Y. Kalantidis, G. Tolias, E. Spyrou, "Retrieving landmark and non-landmark images from community photo collections," in Proceedings of the 18th ACM International Conference on Multimedia, MM '10, pp. 153-162, 2010.
[32] C. Chen, M. You, S. Chiou, "Psycho-pleasurability of maps for wayFinding," in 6th Asian Design International Conference, Tsukuba, Japan, 2003.
[33] W. Chen, A. Battestini, N. Gelfand, V. Setlur, "Visual summaries of popular landmarks from community photo collections," in Proceedings of the 17th ACM International Conference on Multimedia, MM '09, pp. 789-792, 2009.
[34] F. Feito, J. C. Torres and A. Urena, "Orientation, simplicity, and inclusion test for planar polygons," Computers & Graphics, vol. 19, no. 4, pp. 595-600, 1995.
[35] S. F. Frisken, R. N. Perry, A. P. Rockwood, T. R. Jones, "Adaptively sampled distance Fields: A general representation of shape for computer graphics," in Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH '00, pp. 249-254, 2000.
[36] C. Green, "Improved alpha-tested magnification for vector textures and special effects," in ACM SIGGRAPH 2007 Courses, SIGGRAPH '07, pp. 9-18, 2007.
[37] S. Hickey, M. Pakanen, L. Arhippainen, "A 3d ui for service multitasking in a 3d city map," in Proceedings of the 24th Australian Computer-Human Interaction Conference, OzCHI '12, pp. 208-211, 2012.
[38] D. E. Johnson, E. Cohen, "Distance extrema for spline models using tangent cones," in Proceedings of Graphics Interface 2005, GI '05, pp. 169-175, 2005.
[39] M. Kraus, T. Ertl, "Adaptive texture maps," in Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware, HWWS '02, pp. 7-15, 2002.
[40] J. Li, E. Sharlin, S. Greenberg, M. Rounding, "Designing the car iwindow: Exploring interaction through vehicle side windows," in CHI'13 Extended Abstracts on Human Factors in Computing Systems, CHI EA '13, pp. 1665-1670, 2013.
[41] J. Ruiz De Miras, F.R. Feito, "Inclusion test for curved-edge polygons," Computers & Graphics, vol. 21, no. 6, pp. 815-824, 1997.
[42] P. Nilsson, D. Reveman, "Glitz: Hardware accelerated image compositing using opengl," in Proceedings of the Annual Conference on USENIX Annual Technical Conference, ATEC '04, pp. 28-28, 2004.
[43] K. Packard, "Design and implementation of the x rendering extension," in Proceedings of the FREENIX Track: 2001 USENIX Annual Technical Conference, pp. 213-224, 2001.
[44] E. Parilov, D. Zorin, "Real-time rendering of textures with feature curves, "ACM Transactions on Graphics (TOG), vol. 27, no. 1, pp. 3:1-3:15, 2008.
[45] M. Plass, M. Stone, "Curve-Fitting with piecewise parametric cubics," Proceedings of the 10th Annual Conference on Computer Graphics and Interactive Techniques, vol. 17, no. 3, pp. 229-239, 1983.
[46] D. Reilly, K. Inkpen, "Map morphing: Making sense of incongruent maps," in Proceedings of Graphics Interface 2004, GI '04, pp. 231-238, 2004.
[47] E. Ruf, "An inexpensive bounding representation for offsets of quadratic curves," in Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics, HPG '11, pp. 143-150, 2011.
[48] B. C. Russell, R. Martin-Brualla, D. J. Butler, S. M. Seitz, L. Zettlemoyer, "3d wikipedia: Using online text to automatically label and navigate reconstructed geometry," ACM Transactions on Graphics (TOG), vol. 32, no. 6, p. 193, 2013.
[49] A. Secord, J. Lu, A. Finkelstein, M. Singh, A. Nealen, "Perceptual models of viewpoint preference," ACM Transactions on Graphics (TOG), vol. 30, no. 5, pp. 109:1-109:12, 2011.
[50] T. W. Sederberg, T. Nishita, "Curve intersection using bezier clipping," Computer-Aided Design, vol. 22, no. 9, pp. 538-549, 1990.
[51] P. Selinger, "A realistic 2d drawing system," 2003.
[52] N. Snavely, S. Seitz, R. Szeliski, "Modeling the world from internet photo collections," International Journal of Computer Vision, vol. 80, no. 2, pp. 189-210, 2008.
[53] N. Snavely, S. Seitz, R. Szeliski, "Photo tourism: Exploring photo collections in 3d," ACM Transactions on Graphics (TOG), vol. 25, no. 3, pp. 835-846, 2006.
[54] S. Stannus, D. Rolf, A. Lucieer, W. Chinthammit, "Gestural navigation in google earth," in Proceedings of the 23rd Australian Computer-Human Interaction Conference, OzCHI '11, pp. 269-272, 2011.
[55] H. Wang, J. Kearney, K. Atkinson, "Robust and effficient computation of the closest point on a spline curve," in Proceedings of the 5th International Conference on Curves and Surfaces, pp. 397-406, 2002.
[56] Y. Yoshimoto, T. Dang, A. Kimura, F. Shibata, H Tamura, "Interaction design of 2d/3d map navigation on wall and tabletop displays," in Proceedings of the ACM International Conference on Interactive Tabletopsand Surfaces, ITS '11, pp. 254-255, 2011.
[57] Y. Zheng, M. Zhao, Y. Song, H. Adam, U. Buddemeier, A. Bissacco, F. Brucher, T. Chua, H. Neven, "Tour the world: Building a web-scale landmark recognition engine," in 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1085-1092, 2009.