在這篇論文裡，我們提出了一個有效率的演算法模擬沙雕和水之間的互動。近年來，流體模擬在電腦動畫和遊戲裡有舉足輕重的地位，然而沙雕和水的互動始終是個複雜的問題。
我們提供了一個以流體力學為基礎的方法，以粒子的觀點同時模擬沙子和水。由於沙子和水是由龐大數量的粒子所組成，本篇論文使用了適應取樣(Adaptive Sampling)演算法作為基礎做更有效率的模擬。除此之外，為了要模擬出水被沙子吸收的情況，在我們的系統裡面也考慮滲流(Porous Flow)的因素。如此一來，本篇論文可以完全結合沙子跟水的粒子。最後，本系統也會展示水和沙雕互動的效果。

In this thesis, we present an effective algorithm to simulate the interaction between sand sculptures and water. Recently, fluids simulation is an important topic in computer animation and games. However, the interaction between sand sculptures and water is still a complex problem.
We propose a unified Smoothed Particle Hydrodynamics framework for simulating both fluids and sand particles. Since the sand and water are sampled by a large number of particles, we use an adaptive sampling algorithm to simulate particles more effectively. Moreover, we also consider the water absorption of sand. We incorporate the porous flow simulation to our framework. As a result, we can combine sand and water completely. Our system will show how the water collapse sand sculptures during the simulation.

ABSTRACT (in Chinese)……....……………………………………………..............………..I
ABSTRACT (in English)……......………………………………….............…………………II
ACKNOWLEDGEMENTS………………………………………………….............……….III
CONTENTS..………………………………………………………………………................IV
LIST OF FIGURES....................................................................................................................V
CHAPTER 1 INTRODUCTION……………………………………………………................1
1.1 Motivation……………………………………………………………….............……1
1.2 System Overview…………………………………………………...….......................2
CHAPTER 2 RELATED WORKS.………………………………………….………...........…3
2.1 Fluid Simulation……………...……………………………………………….............3
2.2 Porous Flow Simulation…………...……………………………………….................3
2.3 Granular Simulation......................................................................................................4
CHAPTER 3 WATER AND SAND INTERACTIVE MODEL..……………………..............5
3.1 Smoothed Particle Hydrodynamics (SPH) Model...……………………….................5
3.2 Fluid Simulation.....................................................…………………………...............6
3.3 Granular Simulation.............……………………………………………….................7
3.4 Porous Flow Simulation……......……………………………………….…...............11
3.5 Combine Difference Particles.....................................................................................15
3.6 Adaptive Sampling Algorithm....................................................................................17
3.7 Summary of the Algorithm………………………………………………….............18
CHAPTER 4 IMPLEMENTATION AND RESULTS.……………………………..…..........20
CHAPTER 5 CONCLUSION AND FUTURE WORKS..……………..........…………….....72
REFERENCE………………………………………………………………….........…….......73

[1] Adams B., Pauly M., Keiser R., Guibas L. J.: Adaptively sampled particle fluids. In SIGGRAPH ’07: ACM SIGGRAPH 2007 papers (New York, NY, USA, 2007), ACM, p. 48.
[2] Baraff D.: An introduction to physically based modeling: Rigid body simulation 1 - unconstrained rigid body dynamics. SIGGRAPH Course Notes, 1997.
[3] Becker M., Teschner M.: Weakly compressible SPH for free surface flows. In SCA ’07: Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation (2007), pp. 209–217.
[4] Bell N., Yu Y., Mucha P. J.: Particle-based simulation of granular materials. In SCA ’05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation (New York, NY, USA, 2005), ACM Press, pp. 77–86.
[5] Carlson, M., Mucha, P. J., Turk, G. 2004. Rigid fluid: animating the interplay between rigid bodies and fluid. ACM Trans. Graph. (Proc. SIGGRAPH) 23, 377–384.
[6] Carlson, M., Mucha, P., Van Horn III, R., and Turk, G. 2002. Melting and flowing. In Proc. ACM SIGGRAPH/Eurographics Symp. Comp. Anim., 167-174.
[7] Clavet S., Beaudoin P., Poulin P.: Particle-based viscoelastic fluid simulation. In SCA ’05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation (New York, NY, USA, 2005), ACM Press, pp. 219–228.
[8] Cleary, P. W., Pyo, S. H., Prakash, M., and Koo, B. K. 2007. Bubbling and frothing liquids. ACM Trans. Graph. (SIGGRAPH Proc.) 26, 3, 971–976.
[9] Darcy, H. 1856. Les Fontaines Publiques de la Ville de Dijon, Dalmont, Paris.
[10] Desbrun, M., and Cani, M.-P. 1999. Space-time adaptive simulation of highly deformable substances. Tech. rep., INRIA Nr. 3829
[11] Foster N., Fedkiw R.: Practical animation of liquids. In SIGGRAPH ’01: Proceedings of the 28th annual conference on Computer graphics and interactive techniques (New York, NY, USA, 2001), ACM, pp. 23–30.
[12] Foster N., Metaxas D.: Controlling fluid animation. In CGI ’97: Proceedings of the 1997 Conference on Computer Graphics International (Washington, DC, USA, 1997), IEEE Computer Society, p. 178.
[13] Foster N., Metaxas D.: Realistic animation of liquids. Graph. Models Image Process. 58, 5 (1996), 471–483.
[14] G?聲evaux, O., Habibi, A., Dischler, J.-M. 2003. Simulating fluid-solid interaction. In Graphics Interface, 31–38.
[15] Hong J.-M., Lee H.-Y., Yoon J.-C., Kim C.-H.: Bubbles alive. In ACM SIGGRAPH (2008), pp. 1–4.
[16] Lenaerts T., Adams B., Dutre P.: Porous flow in particle-based fluid simulations. In SIGGRAPH 08: ACM SIGGRAPH 2008 Papers (New York, NY, USA, 2008), ACM, pp. 49:1–8.
[17] Lenaerts, T., and Dutr?? P. 2009. Mixing fluids and granular materials. Computer Graphics Forum 28, 2, 213–218.
[18] Miller G., Pearce A.: Globular dynamics: A connected particle system for animating viscous fluids. Computers and Graphics 13, 3 (1989), 305-309.
[19] M?刜ler M., Charypar D., Gross M.: Particle-based fluid simulation for interactive applications. In SCA ’03: Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation (Aire-la-Ville, Switzerland, Switzerland, 2003), Eurographics Association, pp. 154–159.
[20] M?刜ler M., Solenthaler B., Keiser R., Gross M.: Particle-based fluid-fluid interaction. In SCA ’05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation (New York, NY, USA, 2005), ACM Press, pp. 237–244.
[21] Monaghan J.: Smoothed particle hydrodynamics. Annual Revision on Astronomy and Astrophysics 30 (1992), 543–574.
[22] Monaghan J. J.: Smoothed particle hydrodynamics. Reports on Progress in Physics 68, 8 (August 2005), 1703–1759.
[23] POV-Ray, http://www.povray.org
[24] Stam J.: Stable fluids. In SIGGRAPH ’99: Proceedings of the 26th annual conference on Computer graphics and interactive techniques (New York, NY, USA, 1999), ACM Press/Addison-Wesley Publishing Co., pp. 121–128.
[25] Solenthaler B., Schlafli J., Pajarola R.: A unified particle model for fluid-solid interactions. Computer Animation and Virtual Worlds 18, 1 (2007), 69–82
[26] Zhu Y., Bridson R.: Animating sand as a fluid. In SIGGRAPH ’05: ACM SIGGRAPH 2005 Papers (New York, NY, USA, 2005), ACM Press, pp. 965–972.