# Chapter 1 – Introduction

## 1.1 High Concept

The aim of this project is to incorporate fluid dynamics and particles systems to model natural phenomena in real time. Using the Navier-Stokes equations as a basis for modelling fluid flow, the resultant output will be feed into the particle system. All of the calculations will be performed using the GPU, displaying the robustness and benefits of designing such an application.

## 1.2 Project Overview

The animation of gases and fluids such as smoke, water and fire provide some of the most stunning visuals in computer games today. These can be achieved with a variety of methods and currently many projects are looking to expand on previous techniques. Particle systems are used in all modern action / shooter games to model a variety of phenomena such as explosions, smoke and clouds.

Volcanic activity is chosen as it represents a combination of gas, fluid and combustion. When these phenomena interact, the results should model the real world. Common particle systems use simple static forces to update individual pieces. Modelling these interactions is CPU intensive due to the sheer number of calculations involved. When utilising particles for achieving a realistic visualisation of any phenomena, the main factor that determines the quality is the number of particles used to represent the system. Increasing this number automatically increases the overhead on the system. Data transfer between the CPU and the GPU is limited and so a bottleneck will occur if systems containing tens of thousands of particles are rendered. Performing all of these calculations on the GPU erases this issue. It can also update particle positions freeing up more CPU power. The GPU can also calculate other environmental forces and apply those to the particle system as will be demonstrated by this project.

This project will focus on

- Techniques for modelling interactions between natural phenomena

- Performing these interactions on the GPU in real-time

## 1.3 Project Scope

This paper aims to investigate research and current techniques across the fields of fluid dynamics, particle systems and GPU programming. The following chapter summarises these technologies.

After considering the literature, a suitable method for designing the application is derived. The chosen method will be compatible for designing other types of similar phenomena.

# Chapter 2 – Background and Literature Review

This chapter deals with the methodologies required to complete this project.

## 2.1 Fluid Dynamics

## 2.1.1 Fluid Physics

The field of fluid dynamics deals with the study of the motion of fluids and gases. The Navier-Stokes equations can be used to describe this motion. A fluid with constant density and temperature is described by a velocity and pressure field. The equations model the relationship between the velocity and the rates of change of the pressure in a given fluid.

**FIGURE 1 – THE NAVIER STOKES EQUATIONS [ STAM03 ]**

**Equation 2.1 shows the velocity in a compact vector notation and 2.2 shows a density moving through the velocity field.**

From this, the main properties are:

#### Advection:

The velocity of a fluid causes the fluid to transport objects, densities and other quantities along with the flow.

#### Pressure:

When force is applied to a fluid, it does not instantly affect the entire volume. Instead the pressure builds up, and any pressure leads to an increase in acceleration.

#### Diffusion:

Thick fluids such as lava have a high viscosity. Viscosity is a measure of how resistive a fluid is to flow. This resistance results in diffusion of the momentum.

#### External Forces:

These forces may be either local forces or body forces. Local forces may be applied to a specific region of the fluid whilst body forces are applied equally to the entire fluid.

## 2.1.2 Fluid Dynamics in Computer Games

There are different methods available to model fluid dynamics. The primary concern is the final aesthetic effect and the ability to run in real time so accuracy is off a lesser value. Modelling fluids with accuracy in mind would result in a computationally expensive system.

To use the Navier-Stokes equations, the space must be converted into a grid. The density of the object, velocity and pressure at the centre of each grid cell must be defined. At each time step, the equations are used to determine the new values of the fields. An extra layer of cells is provided to account for the boundary conditions.

**FIGURE 2 – GRID WITH BOUNDARY CELLS [ STAM 03 ]**

Many systems have been created which can model accurate and realistic simulations. However, these are not designed to run in real-time. [ Fedkiw01 ] assumes that the fluid flow is of constant density and uses Euler equations. It uses an implicit semi-Lagrangian scheme which ensures stability over the time step. This algorithm builds a new grid of velocities from the ones already computed by tracing the midpoints of each voxel face through the velocity field. New velocities are then interpolated at these points and the values are transferred to the cell they originated from.

[ Stam03 ] describes a system which utilises an Eulerian grid approach. This uses a coarser resolution than that required for accurate simulations reducing the overhead. The simulation space is divided in a 3D voxel grid. The Navier-Stokes equations for the gas volume in each cell are calculated by applying numerical methods. It provides an implicit integration scheme, allowing the system to run at any time step. This is based on equation 2.2. The solver is used to evolve the smoke density over time in each cell given the rate of diffusion and a static velocity field. This moves the smoke and allows changing forces caused by the environment.

**FIGURE 3 – RESULTS FROM SOLVER INPLEMENTED IN [ STAM03 ]**

## 2.1.3 Rendering Fluid

Rendering fluids or gases is known as volume rendering. Mentioned in the previous section, the space must be divided into a 3D grid containing the gas densities of each cell. [ Stam03 ] uses a particle based approach which moves the particles through the generated velocity field instead of the gas densities. The densities can be modelled as particles at the centre of each cell.

## 2.2 Particle Systems

## 2.2.1 General Particle Systems

A particle is a very small object that is usually modelled as a point mathematically. Point sprites can have textures mapped to them and the sizes can vary. The conventional particle system contains an emitter which creates the particles. This also controls their life-span and applies initial forces to them. When the particle is instantiated, it moves to a random 3D point

within a specified area and constantly moves under the force applied to it.

Traditionally the particles were stored in a vertex buffer in the main system memory and these points were sent to the GPU. This method can handle up to 10000 particles before bottlenecks begin to occur. This is computationally expensive for large particle systems and so the current trend is to compute all the required information on the GPU.

## 2.2.2 GPU – Based Particle Systems

Parallel processing capabilities of computers today allow systems to perform calculations simultaneously. All updating and rendering is performed on the GPU. The programmable graphics pipeline and recent hardware advances affords this flexibility. The previous technique of streaming the vertices of the particles is eliminated freeing the CPU for other computational work.

[ Latta04 ] utilises the above implementation creating up to a million particles on the GPU. The velocities and positions of all particles are stored in textures. [ Kolb04 ] describes a system for collision detection using depth maps that represent the outer shape of an object. These store distance values and normal vectors. Additional textures can store other collision data allowing the pixel shader to bounce or merge objects. [ Kruger05 ] implements system which utilises fluid dynamics techniques. For 2D, it uses pre-computed effect templates to update the particle positions which are stored in textures. By using volumetric extrusion, the techniques are extended to work in 3D, but are only suitable for symmetric effects.

## 2.2.3 Verlet Integration

In order to update the positions of particles over time, Verlet integration will be used. This states that the velocity of the particle is deduced by comparing the previous position to the one before. [ Latta04 ]

x ‘= 2x – x* + a . Δt^2

x* = x

x* = previous position

# Chapter 3 – Method

## 3.1 Overview

The following section details the intended method to produce the final result. The high level outcomes of this project are

- A system which calculates dynamic forces and moves the particles according to these.
- Implement a GPU based system on the above factors which controls the entire scene.

## 3.2 CPU System

## 3.2.1 Particle Generation

Particles are required for four types of phenomena:

- Fire
- Smoke
- Explosions
- Lava Flow

The emitter system which creates the particles will store them as texels in two procedural textures. The textures will store their previous and current positions. Another texture stores other static data for each particle as shown in Figure 4. The rate of particles emitted will depend on the type of phenomena. Created particles are assigned a random point and velocity. As the Verlet integration generates a previous and current position, the origin, of the particle, the GPU can manipulate it using this data. Once a particle dies, its texel must be freed for the use of new particles.

**FIGURE 4 – PARTICLE DATA STORAGE IN MULTIPLE TEXTURES [ LATTA04 ]**

## 3.2.2 Phenomena Velocities

Each of the phenomena shall have different forces acting on them. Lava will contain higher viscosity and advection values. Viscosity will increase over time changing the texture. Each one will be contained in a 3D grid. Each cell of the grid will have a velocity assigned representing the air flow of that particular cell. The solvers utilised in [ Stam03 ] will form a basis to calculate the velocities which will then be stored in a procedural texture for GPU access. An extra layer of cells will be created to represent the boundary conditions. This will allow realistic interactions between the different phenomena. The procedural texture generated will represent the entire velocity grid.

## 3.3 GPU System

The shader will determine the new positions of the particles depending on the velocity of the cell in question, current position and the previous position of the particle itself. The outer cells will be affected by the cells from other grids. The new position is stored in a particle position buffer and the vertex shader positions this in the game world. After particles have been translated, they have to be depth sorted into a suitable render order. They will also undergo alpha blending as all phenomena will be inter connected. Point sprites are used to render the particle which is rotated according to the stored value.

## 3.4 Alternative Method

#### Perlin Noise

The entire system could be designed with the use of Perlin noise. [ Perlin01 ] utilises a method to create lava flow and fire with smoke. Perlin Noise is extended to incorporate advection. [Tatarinov07 ] creates fire using Perlin Noise to perturb a basic fire shape. This could be extended to the other intended features.

**FIGURE 5 – ANIMATED LAVA FLOW [ PERLIN01 ]**

**FIGURE 6 – BASIC SHAPE (LEFT) USED TO CREATE FIRE EFFECT (RIGHT) [ TATARINOV07 ]**

## 3.5 Evaluation Criteria

The final application will be accessed according to two factors:

- Visual Effect – Qualitative
- Application Performance – Quantitative

## 3.5.1 Qualitative

The main aim of this project is to create an aesthetically pleasing and display the realistic interactions between the different types of phenomena which can then be transferred to a game situation. Comparisons shall be made against projects using similar technology.

## 3.5.2 Quantitative

The application must run at a minimum of 30 fps. There may be trade-off with the qualitative criteria to achieve this. Code optimisations may have to be performed. This would entail modifications to the algorithms or to the data structures. Tests against running the system only on the CPU will also be performed.

# Chapter 4 – Project Plan

Figure 7 gives an overview of the monthly project deliverables. Appendix I contains a detailed Gantt chart.

**FIGURE 7 – MONTHLY PROJECT DELIVERABLES OVERVIEW**

# Chapter 5

## 5.1 References

Latta, L. 2004. **Building a Million Particle System**, http://www.gdconf.com/conference/archives/2004/latta_lutz_01.pdf (Date Accessed: 08/05/08)

Kolb, A., Latta, L., Rezk-Salama, C. 2004. **Hardware-Based Simulation and Collision Detection for Large Particle Systems**, http://www.2ld.de/gh2004/HWSimCollisionPS.pdf (Date Accessed: 08/05/08)

Kruger, J., Westermann, R. 2005. **GPU Simulation and Rendering of Volumetric Effects for Computer Games and Virtual Environments**. http://wwwcg.in.tum.de/Research/data/Publications/eg05.pdf (Date Accessed: 08/05/08)

Stam, J. 2003. **Real-Time Fluid Dynamics for Games**. http://www.dgp.toronto.edu/people/stam/reality/Research/pdf/GDC03.pdf (Date Accessed: 08/05/08)

Petersson, S. 2007. **Particle System Rendering – The effect on rendering speed when using Geometry Shaders**. http://www.bth.se/fou/cuppsats.nsf/all/10165efe6d0ac508c12573470032c16a/$file/070518_DVC001_Stefan_Petersson_850417_Rapport.pdf (Date Accessed: 08/05/08)

Anderson, L. 2005. **Real-Time Fluid Dynamics for Virtual Surgery**. http://www.ce.chalmers.se/~uffe/xjobb/blood.pdf (Date Accessed: 08/05/08)

Fedkiw, R., Stam, J., Jensen, H.W. 2001. **Visual Simulation of Smoke**. http://physbam.stanford.edu/~fedkiw/papers/stanford2001-01.pdf (Date Accessed: 08/05/08)

Stora, D., Agliati, P.-O., Cani, M.-P., Neyret, F., Gascuel, J.-D. 1999. **Animating Lava Flows**. http://www-evasion.imag.fr/Publications/1999/SACNG99/gi99.pdf (Date Accessed: 08/05/08)

Tatarinov, A. 2007. **Perlin Fire**. http://developer.download.nvidia.com/whitepapers/2007/SDK10/PerlinFire.pdf (Date Accessed: 09/05/08)

Perlin, K. 2001. **Flow Noise**. ., http://chihara.aist-nara.ac.jp/people/2003/takasi-a/research/short_paper.pdf (Date Accessed: 09/05/08)

Amada, T., Imura, M., Yasumuro, Y., Manabe, Y., Chihara, K., **Particle-Based Fluid Simulation on GPU**, http://chihara.aist-nara.ac.jp/people/2003/takasi-a/research/short_paper.pdf (Date Accessed: 09/05/08)

Mizuno, R., Dobashi, Y., Nishita, T. 2002. **Volcanic Smoke Animation using CML**, http://nis-lab.is.s.u-tokyo.ac.jp/nis/cdrom/cgi/ics2002-crf5.pdf (Date Accessed: 09/05/08)

Miyazaki, R., Yosida, S., Dobashi, Y., Nishita, T. 2001. **A Method for Modeling Clouds based on Atmospheric Fluid Dynamics**, http://nis-ei.eng.hokudai.ac.jp/~doba/papers/ PG2001_CML.pdf (Date Accessed: 09/05/08)

**Nvidia Developer**, http://developer.nvidia.com/page/home.html, (Date Accessed: 01/05/08)

**ATI Developer**, http://ati.amd.com/developer/, (Date Accessed: 01/05/08)

## 5.2 Bibliography

Cartwright, C. 2008, **SA1100A Masters Proposal Course Notes**, University of Abertay, Dundee, https://portal.abertay.ac.uk/learning/module/co/sa/SA1100A07/

Fernando, R. 2004, **GPU Gems**, Nvidia Developer Zone, http://developer.nvidia.com/object/gpu_gems_home.html

Dickheiser, M. 2006, **Game Programming Gems 6**, Charles River Media, Boston.

Nyguyen, H. 2007, **GPU Gems 3**, Addison Wesley Professional, Boston.

Luna, F. D. 2006, **Introduction to 3D Game Programming with DirectX 9.0c : A Shader Approach**, Wordware Publishing, Texas.

The .pdf version of this report can be viewed here.