臺灣博碩士論文加值系統

在工程的領域當中,擴散方程式是廣泛被使用的,尤其是在熱力學上面,因此擴散方程式又叫作熱方程式,在電腦圖學的領域中,已經有發展出一些應用,譬如影像的去雜訊,網格的平滑化,或是填補一些缺少的資訊,都是很實用,且常見的.

在本篇論文當中,將會介紹其他的應用,利用擴散方程式的特性,來使問題的解決更簡單,執行起來更有效率,這就是本篇論文主要的貢獻.

In the field of engineering, the diffusion equation has been widely used. Especially in the field of thermodynamics, therefore the diffusion equation is also called heat equation. In the field of computer graphics, there are several applications developed. For instance, de-noise processing of image, mesh smoothing and fill holes in a certain data. Such applications are very useful and common.

In my thesis, I will introduce other applications which were solved using the property of diffusion equation. This will make the process of solving problem much easy and efficient. This is the major contribution of my thesis.

中文提要 I
Abstract II
誌謝 III
目錄 IV
表目錄 VIII
圖目錄 IX
第一章 導論 1
1.1研究動機與目的 1
1.2本論文中心思想 3
1.3本論文的貢獻 4
1.3.1 對流體控制的貢獻 4
1.3.2 在Imag warp的貢獻 5
第二章 相關研究 6
2.1 擴散方程式在電腦圖學的應用 6
2.2以物理為基礎的流體動畫模擬 7
2.2.1流體力學數值模擬: 7
2.3二維影像編輯 10
第三章 擴散方程式 11
3.1擴散方程式的偏微分型態 11
3.2 邊界條件 12
3.3 有限差分（finite difference） 13
3.3.1有限差分是一種微分的離散化表示法. 13
3.3.2有限差分依差分的類型 13
3.3.3有限差分對於向量分析的描述法 14
3.4 擴散方程式有離散化 15
3.4.1 擴散方程式顯示表示法（Explicit representation） 15
3.4.2 擴散方程式隱式表示法 20
3.4.3 顯式和隱式穩定度比較 22
3.4.4 迭代法求解 25
第四章 擴散方程在流體控制的應用 27
4.1 問題描述 27
4.2原理與流程 28
4.2.1那維爾-史托克斯方程式 (Navier Stoke`s Equation) 28
4.2.2歐拉運動方程式(Euler equations of motion) 30
4.2.3 控制流體的原理 31
4.2.4 系統流程概說 31
4.3 解流體偏微分方程 33
4.3.1資料結構 33
4.3.2 數值模擬的偏微分方程式概說 35
4.3.3 解方程式的步驟 37
4.3.4 投影的實作方法 38
4.3.5流體對流的實做方法 39
4.4 計算流體控制 44
4.4.1. 計算驅動力 45
4.4.2 邊界條件 47
4.4.3 終止條件 49
4.4.4.在流動的過程中對於密度場概說 50
4.4.5 密度場調整基本原理: 51
4.4.6 密度場調整開始的時機： 52
4.4.7 密度場調整的強度隨時間的變化 54
4.5 驅動力在物理上的合理性 55
4.5.1何謂物理上的合理 55
4.5.2數學推導 56
4.5.3結果視覺化 57
第五章 擴散方程式在二維圖片形狀編輯的應用 58
5.1 問題描述 58
5.2 演算法架構 59
5.3 邊界條件(Boundary Conditions) 62
5.3.1 控制點的邊界條件 62
5.3.2 形狀的邊界條件 63
5.4 把控制點移動的資訊擴散出去 67
5.4.1 卡氏式座標上的位移擴散 68
5.4.2 極座標上資訊擴散 72
5.4.3 結合旋轉和伸縮量的編輯方式 74
第六章實驗結果與討論 77
6.1擴散方程式在控制流體的應用 77
6.1.1 計算時間統計 83
6.1.2 驅動力的效能比較(With [Fattal and Lischinski ‘04]) 84
6.1.3 計算驅動力穩定度的比較(With [Fattal and Lischinski ‘04]) 85
6.2 擴散方程式在影像編輯的應用 88
6.2.1 運算時間統計 90
6.2.3 和[Igarashi et al ‘05]作比較 90
6.2.4 和[Schaefer et al ‘06]作比較 91
6.2.5 本演算法的限制 92
第七章 未來展望 93
參考文獻 94
中英文自述 99

[1]ABRAHAM, R., MARSDEN, J., AND RATIU, T. Manifolds, Tensor Analysis,
and Applications, Applied Mathematical Sciences. vol. 75. 1988.
[2]ALEXA, M., COHEN-OR, D., AND LEVIN, D. As rigid- as-possible shape interpolation. In Proceedings of ACM SIGGRAPH 2000, ACM Press/Addison-Wesley Publishing Co.,New York, NY, USA, 157–164.2000.
[3]BEIER, T., AND NEELY, S. Feature-based image metamorphosis. In SIGGRAPH : Proceedings of the 19th annual conference on Computer graphics and interactive techniques, ACM Press, New York, NY, USA, 35–42.1992.
[4]Bell, H. E. Gerschgorin's Theorem and the Zeros of Polynomials. Amer. Math. Monthly 72, 292-295, 1965.
[5]Bertalmio, M., Sapiro, G., Caselles, V., Ballester, C., Image Inpainting. Proc. SIGGRAPH, ACM, 2000.
[6]BOOKSTEIN, F. L.Principal. warps: Thin-plate splines and the decomposition of deformations. IEEE Trans. Pattern Anal. Mach. Intell. 11, 6, 567–585.1989.
[7]Byungmoon Kim, Yingjie Liu, Ignacio Llamas, Jarek Rossignac, Advections with Significantly Reduced Dissipation and Diffusion, IEEE Transactions on Visualization and Computer Graphics,to appear . 2006.
[8]David Kincaid And Ward Cheney,Numerical Analysis:Mathematics of Scientific Computing, Third Edition,Brooks/Cole.2002
[9]DUPONT T. F., LIU Y.: Back and forth error compensation and correction methods for removing errors induced by uneven gradients of the level set function. Journal of Computational Physics 190, 1 , 311–324.2003.
[10]ENRIGHT, D., MARSCHNER, S., AND FEDKIW, R. 2002. Animation and rendering of complex water surfaces. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH) 21,3 (July), 736–744.2002.
[11]FEDKIW, R., STAM, J., AND JENSEN, H. W. Visual simulation of smoke. Computer Graph. (Proceedings of ACM SIGGRAPH) 35, 15–22.2001.
[12]Fletcher, C.A.J.,Computational Techniques for Fluid Dynamics, Springer Verlag, Sydney,1990.
[13]FOSTER, N., AND FEDKIW, R.Practical animations of liquids. In Computer Graphics Proceedings, Annual Conference Series,E. Fiume, Ed., ACM SIGGRAPH, 23–30.2001.
[14]Harlow, F.H., andWelch, J.E.,Numerical Calculation of Time-Dependent Viscous Incompressible Flow, Phys. Fluids, 8, pp. 2182–2189.1965.
[15]HONG J.-M., KIM C.-H.: Controlling fluid animation with geometric potential. Computer Animation and Virtual Worlds 15, 3-4, 147–157. 3, 4, 6, 7.2004.
[16]IGARASHI, T., MOSCOVICH, T., AND HUGHES, J. F. As rigid-as-possible shape manipulation. ACM Trans. Graph. 24, 3,1134–1141.2005.
[17]James Davis, Stephen R. Marschner, Matt Garr, and Marc Levoy. Filling holes in complex surfaces using volumetric diffusion.First International Symposium on 3D Data Processing, Visualization, and Transmission Padua, Italy, June 19-21, 2002.
[18]Jian Sun, Jiaya Jia, Chi-Keung Tang and Heung-Yeung Shum. Poisson Matting. SIGGRAPH , ACM Transaction on Graphics, Vol 23, No. 3,315-321. April 2004.
[19]Jun Wang, Hongxin Zhang, Dong Xu, Hujun Bao. Sketch-based Poisson Mesh Editing. Journal of Computer-Aided Design & Computer Graphics (In Proceedings of ChinaGraph 2006),to appear.2006.
[20]KOBAYASHI, K. G., AND OOTSUBO, K.. t-ffd: free-form deformation by using triangular mesh. In SM ’03: Proceedings of the eighth ACM symposium on Solid modeling and applications, ACM Press, 226–234.2003.
[21]LAMORLETTE, A., AND FOSTER, N. Structural modeling of flames for a production environment. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2002) 21, 3 (July), 729–735.2002.
[22]Laurene V.Fausett ,Applied Numerical Analysis Using MATLAB ,Prentice Hall.1999.
[23]LEE, S.-Y., CHWA, K.-Y., AND SHIN, S. Y. Image metamorphosis using snakes and free-form deformations. In SIGGRAPH ’95: Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, ACMPress, New York, NY, USA, 439–448.1995.
[24]Liu ,S. S. Liaw, and P.K. Maini, Two-stage Turing model for generating pigment patterns on the leopard and the jaguar,Phys. Rev. E74,1-8,2006.
[25]M. Kazhdan, M. Bolitho, H. Hoppe. Poisson surface reconstruction. Eurographics Symposium on Geometry Processing, 61-70.2006.
[26]MACCRACKEN, R., AND JOY, K. I.Free-form deformations with lattices of arbitrary topology. In Proceedings of ACM SIGGRAPH 1996, ACM Press, 181–188.1996.
[27]Nature 442, 604-605(10 August 2006) | doi:10.1038/442604a; Published online 9 August 2006
[28]NGUYEN, D. Q., FEDKIW, R., AND JENSEN, H. W. Physically based modeling and animation of fire. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2002) 21, 3 (July), 721–728.2002.
[29]P. Blasi, B. Le Saec, and C. Schlick. A Rendering Algorithm for Discrete Volume Density Objects. Computer Graphics Forum (EUROGRAPHICS 93 Conference Proceedings), 12(3):201–210, 1993.
[30]P. Pérez, M. Gangnet, and A. Blake. Poisson image editing. ACM Transactions on Graphics (SIGGRAPH 2003), 2(3):313-318.2003.
[31]PERONA, P., AND MALIK., J. Scale space and edge detection using anisotropic diffusion. IEEE Trans. Pattern Anal. Machine Intell.12(7):629-639.1990.
[32]PRESS, W. H., TEUKOLSKY, S. A., VETTERLING, W. T., AND FLANNERY, B. P. Numerical Recipes in C: The Art of Scientific Computing, 2nd ed. Cambridge University Press.1992.
[33]Raanan Fattal, Dani Lischinski. Target-Driven Smoke Animation. ACM Transactions on Graphics, Vol. 23, No. 3, SIGGRAPH , pp. 441-448.2004.
[34]Schaefer S., McPhail T. and Warren J. Image Deformation Using Moving Least Squares In Proceedings of ACM SIGGRAPH 2006,533-540. 2006.
SEDERBERG, T. W., AND PARRY, S. R. . Free-form deformation of solid geometric models. In Proceedings of ACM SIGGRAPH 1986, ACM Press,151–160.1986.
[35]SHEPARD, D. . A two-dimensional interpolation function for irregularly-spaced data. In Proceedings of the 1968 23rd ACM national conference, ACM Press, 517–524.1968.
[36]STAM, J. Stable fluids. In Computer Graphics Proceedings, Annual Conference Series, A.Rockwood, Ed., ACMSIGGRAPH, 121–128.1999.
[37]T. Tasdizen, R. Whitaker, P. Burchard, and S. Osher. Geometric surface smoothing via anisotropic diffusion of normals. In Procceedings of IEEE Visualization '02, pages 125--132, 2002.
[38]TIDDEMAN, B., DUFFY, N., AND RABEY, G. A general method for overlap control in image warping. Computers and Graphics 25, 1, 59–66.2001.
[39]TREUILLE, A., MCNAMARA, A., POPOVIC, Z., AND STAM, J. Keyframe control of smoke simulations. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2003) 22, 3 (July), 716–723.2003.
[40]WITTING, P. Computational fluid dynamics in a traditional animation environment. In Computer Graphics Proceedings, Annual Conference Series, A. Rockwood, Ed., ACM SIGGRAPH, 129–136.1999.
[41]Xu, D., Zhang, H., Wang, Q., and Bao, H. Poisson shape interpolation. Graph. Models 68, 3 (May. 2006), 268-281.2006.
[42]Y. Tong, S. Lombeyda, A. Hirani, M. Desbrun.Discrete Multiscale Vector Field Decomposition.ACM transactions on Graphics, Vol 22, procedings of SIGGRAPH, July 2003, pp. 445-452.2003.
[43]Yanlin Weng, Weiwei Xu, Yanchen Wu, Kun Zhou, Baining Guo .2D Shape Deformation Using Nonlinear Least Squares Optimization.. To Appear in The Visual Computer Pacific Graphics ,2006.