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.

THE NAVIER STOKES EQUATIONSFIGURE 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.

GRID WITH BOUNDARY CELLSFIGURE 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.

RESULTS FROM SOLVER INPLEMENTED IN [ STAM03 ]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

  1. A system which calculates dynamic forces and moves the particles according to these.
  2. 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.

ANIMATED LAVA FLOW

FIGURE 5 – ANIMATED LAVA FLOW [ PERLIN01 ]

BASIC SHAPE (LEFT) USED TO CREATE FIRE EFFECT (RIGHT) [ TATARINOV07 ]

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:

  1. Visual Effect – Qualitative
  2. 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.

MONTHLY PROJECT DELIVERABLES OVERVIEWMONTHLY PROJECT DELIVERABLES OVERVIEW

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.

VN:F [1.8.8_1072]
Rating: 0.0/10 (0 votes cast)
VN:F [1.8.8_1072]
Rating: 0 (from 0 votes)

The following animation was created in Maya 3D. It consists of 2 meshes and was successfully exported to DirectX. Being my first animated model, it is extremely basic…It can be downloaded below.

Maya Gun Animation

Maya Gun Animation 2

DirectX Gun Animation

DirectX Gun Animation 2

The files for the Gun and Bullet can be downloaded here.

VN:F [1.8.8_1072]
Rating: 0.0/10 (0 votes cast)
VN:F [1.8.8_1072]
Rating: 0 (from 0 votes)

Overview

This document covers the notes and discussions during the meetings of the project team.

Jan 18th 2008

Participants: Programmers team full participation

Duration: 4 hrs

- Discussion of two different game ideas:

o Alley Katz(Sameer KUMAR)

o A survival game(Gorkem PACACI)

- For both of the ideas, members are going to write one-page descriptions and post them on assembla.

- Decided to use google groups for in-group communication.

Jan 25th 2008

Participants: Programmers team full participation, and GPM students also joined.

Duration: 6 hrs

- Decided to use assembla.com’s internal messaging service for in-group communication.

- One more week will be allowed for the ideas to get mature.

- Discussing about the coding conventions.

- Discussing about the current game ideas with GPM members.

- Coding conventions will be written to assembla wiki page, and will be opened for discussion.

- Discussed the heartbeat function in the game. Kenneth and Rushi are going to have a meeing with Andy Sapeluk to get help on hardware side.

Feb 1st 2008

Participants: Programmers team full participation

Duration: 2 hrs

- Discussed to change the meeting date of the week

- One of the GPM members work on Tuesday, and the other works on Wednesday, so it’s the best choice to keep meeting on Fridays.

- Sameer has a flatmate who is an artist, he is going to ask for his help.

Feb 8th 2008

Participants: Programmers team.

Duration: 6 hrs

- Voted for the game ideas, and the Alley Katz idea has been picked.

Discussed:

- The writing of the Game Design Document (GDD), Technical Design Document (TDD), and the Creative Design Document (CDD aka Art Production plan/APP)

- Discussed the need for artists and sound engineers.

- The structure of the level.

- The scoring system for the game.

- The heartbeat monitor.

Decided:

- The completed game should have 5 levels with five puzzles in each. Each level being a different city.

- Types of music that would suit the game. We are using techno remix songs during the riding scene.

- How the race should be started. (girl with bra)

- What sort of obstacles the racer would face. E.g. pedestrians, cars, dogs.
Gameplay.

Feb 15th 2008

Participants: Programmers team, GPM students

Duration: 6 hrs

- Andrew attended to the meeting as the artist of the game content.

Discussed:

- The art style. Wind, hills etc.

- Which part of Dundee the game should be held in.

- Tone, Genre, Theme, Story of the game.

- The structure of the level.

- List of animations.

- How many characters.

- Racing blur.

Feb 29th 2008

Participants: Programmers team, GPM, Artist

Duration: 4 hrs

Decisions about the content of the game:

- Checkpoints would be used

- A heartbeat monitor to determine how fast the user’s heart is racing. This will allow the game to reward or penalise the player for getting excited or staying calm.

- Heartbeats count down until zero.

- Completing a puzzle rewards the player with more heartbeats.

- At the start of the level the player will be asked to select their route.

- Which location the puzzles are attached to will be randomised.

- No competitors will be visible on screen, although there will be a constant reminder of how well they are doing.

Mar 14th 2008

The meeting notes for this date has been lost.

Note: We gave a break to meetings after easter holiday, but we kept email discussions going.

Apr 25th 2008

Participants: Programmers team full participation

Duration: 5 hrs

- Discussed the Puzzles

- Three puzzles are going to be incorporated into the game.

o A pong implementation

o A three dimensional snake implementation

o An implementation of Picross puzzle

- Discussed the last situation about the heartbeat monitor.

- As it turns out, we won’t be able to support heartbeat system in the game. Instead, we are going to use a points system. Player is going to collect points from the puzzles, and at the end of the game. Total points are going to define the total success of the player.

May 6th 2008

Participants: Programmers full team participation

- As it turns out, we won’t be able to get any input from the art side. So procedural generation of the game contents.

A task list for the last week has been stated:

- Menu
- Add bitmap graphic for title and credits

- Game
- Generate buildings (10 blocks with textures)
- Complete the 3 puzzles
- Collect points from puzzles and show them at the end.
- Disable sounds during the puzzles.
- Re-design pedestrian waypoints
- Fix the initial state of the directional light.
- Add puzzle destination positions to the mini map.

- Bicycle
- Replace the box with bike mesh
- Limit speed of the vehicle by a constant
- Fix reverse speed constant
- Fix brake torque constant
- The vehicle sometimes keeps going while the player is playing the puzzle.

- Camera
- Fix initial position of the camera

- Misc
- Game design document last changes

VN:F [1.8.8_1072]
Rating: 0.0/10 (0 votes cast)
VN:F [1.8.8_1072]
Rating: 0 (from 0 votes)