\chapter{Sandstorm Prototype}\label{ch5}

In this chapter you will find a description of the inner workings of the Sandstorm Prototype.
First, a description of the GPU-Based particle system will be described, then the steps to combat the multi-contextual environment.
Next the use of vector fields will be discussed both on how they are used to update the particles and how the vector fields are updated themselves.
Finally, a description of the dynamic nature of Sandstorm and a listing of all the attributes that are able to be dynamically changed is presented.

\section{GPU-Based}\label{sec:GPUBased}

This thesis has looked at a hand full of particle systems, some of which are GPU-based particle systems.
This section describes the GPU-based particle system of Sandstorm.
Like most particle systems, Sandstorm's particle system has three main phases: (1) Creation and Destruction phase, (2) Update phase, and (3) Rendering phase.
The following sections describe these three main phases.

\subsection{Creating and Destroying Particles}\label{sec:Create}

The most important part of a particle system is its ability to introduce new particles into the system.
Without it the user would be staring at a blank screen.
On the other hand, destroying particles is also an important part of a particle system. 
Without this ability the particle system would not be able to introduce new particles when the system has reached its maximum.
Considering that the creation and destruction of particles is handled on the GPU the problem has to be revisited.
According to Reeves~\cite{reeves}, and others~\cite{kipfer04:uber,latta}, there are three steps: (1) particles are born, (2) each new particle is assigned individual attributes, and (3) particles that are too old are destroyed.

Traditional particle systems would create particles and store them into a dynamically growing data structure, such as a linked list or an array.
But with GPU-based particle systems particles can't be stored in such data structures, as is the case with Uber Flow~\cite{kipfer04:uber} and Latta's Million Particle System~\cite{latta}.
In both cases textures were used to store particles and their associated data, this allowed the isolation of particles and particle data to the GPU, freeing space on the CPU.
However, textures aren't the most efficient mechanism for relaying information to the GPU. 
Now VBOs can be used to relay information to the GPU more efficiently.
Like previously stated, a VBO stores data on the high-performance graphics memory of the GPU~\cite{nvidia:vbo}.
Also VBOs can be resized to fit the exact amount of data that is used, whereas, a texture needs to describe a rectangular area that encompasses the entire area of the amount of data.
For example if a data set had 19 members then a texture would have to cover an area of 20, wasting more memory than is actually needed.
This is not the case with a VBO, which would just need to be of size 19.
This property can allow the VBO to dynamically increase and decrease in size to accommodate large amounts of particle information.
Because of VBOs' memory efficiency, Sandstorm uses them to store particle information on the GPU.



Considering that the GPU is a set streaming processors, a second look needs to be taken at how the particle information is stored.
Since we never know just how many processors are reading and/or writing to a particular location in the VBO, a double buffered approach needs to be adopated.
Like Latta's Million Particle System~\cite{latta}, Sandstorm uses a double buffered approach to store particle information on the GPU. 
One of the buffers is used as a read buffer and the other buffer is used as the write buffer.
At the end of every cycle these buffers are swapped.
Also like Latta's Million Particle System~\cite{latta} and Uber Flow~\cite{kipfer04:uber}, each of the buffers hold two VBOs.
One VBO holds the particle's position in 3D space, which is stored in the first 3 members of the vertex, the fourth member of the vertex contains the lifetime of the particle.
The other VBO holds the particle's velocity components, which are also stored in the first 3 members of the vertex leaving the fourth member free for use elsewhere, see Figure~\ref{fig:sandvbo}.

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=10cm]{images/SandstormVBO.png}
	\end{center}
	\caption{An example how Sandstorm store particle information.}
	\label{fig:sandvbo}
\end{figure}

Most modern particle systems have two entities associated to them, one is the particle and the other is the emitter.
Considering we know what a particle is, its time to describe what a emitter is and what it is used for.
An emitter is an entity that is responsible for the emission of particles, which usually has a position in space or an area for which it is responsible for emitting particles to.
Emitters are entities that are not usually rendered, they are merely abstract objects responsible for the introduction of new particles into the system.
On that note, in Sandstorm an emitter is stored in the same buffer as the particles.
In the case of an emitter, the members of position vertex buffer holds random numbers to aid in the seeding of initial values.
The case is the same for the velocity vertex buffer, but instead the fourth member is set to one to denote that the emitter is indeed an emitter.
Therefore, the fourth member of the particle's velocity vertex buffer is set to zero to denote a particle.

Now that we know how the particle information is store on the card, it's time to take a look at how the particles are created.
In Shader Model 4, the geometry shader can emit one or more vertices up to a maximum amount that is hardware dependent.
Keeping that in mind, geometry shaders are a logical choice for the creation and destruction of the particles.

At the beginning of the Creation and Destruction phase, the particle information is passed to the shader that is responsible for the creation and destruction of the particles, the particle shader.
Once the particle shader has the particle information, it determines if the object that it receives is a particle or an emitter, by looking at the 4th value of the velocity vertex.
Once the shader has determined if it is dealing with an emitter, it begins to emit particles.
The first thing to determine is how many particles are to be emitted, which is done by determining how many particles have already been emitted and subtracting that from the number of particle per second.
Once the difference is found, it's divided by the amount left in that cycle, each cycle is a second.
This method won't always give the exact amount of particles per second, but it gives the system another measure of diversity, making the system seem more realistic.

Once the number of particles to be emitted has been determined, the particles are created but not yet emitted.
Inside the aforementioned while loop, each particle is seeded with initial information that conforms to certain ranges.
In order to give the particle system a more realistic feel to it this initial information is random.
But creating random numbers on the GPU is currently not supported; therefore, a perturbation texture was used.
This will be described in more detail later in the mutli-contextual section.
Once the particle has its initial information, the emitter emits the position and velocity vertex of all the particles into the write buffer.
Finally, the emitter emits itself back into the write buffer.

If the object that the particle shader is passed is a particle, then something different happens.
First, if the particle is determined to be dead the shader emits nothing freeing up its spot in the vertex buffer.
If the particle is not dead, then the particle is updated which is describe in the following subsection.

\subsection{Updating Particles}\label{sec:Update}

The next step in a particle system, once new particles are created and old particles are destroyed, is to update a particles' information.
This section describes the Update phase.

The first thing that is done is to perform a lookup into the vector field and get the acceleration information at the position of the particle.
This lookup is done by interpolating the position of the particle and dividing the members by the width, height, and depth of the vector field.
Once the acceleration information is obtained the velocity of the particle is updated, then the position and the total time lived are also updated.
Once the particle's information is updated it is emitted into the write buffer.

This is where Transform Feedback steps in.
As previously stated, Transform Feedback allows one shader to specify an output vertex buffer object, so that another shader can use that same vertex buffer object as an input buffer.
Once all of the particles have been updated and have been emitted into the write buffer, the read and write buffers are swapped and Transform Feedback feeds the read buffer to the render shader.

\subsection{Rendering Particles}\label{sec:Render}

Finally, the last thing to do in the particle system is to render the particles.
As previously stated, geometry shaders can emit one or more vertices to a render target.
This ability can aid in the rendering of particles.
When rendering particles, most particle systems render the particles as textured billboards, this gives the illusion of a volumetric cloud of dust.
However, some particle systems, mostly scientific visualization systems, render particles as points in order to study the behavior of particles.
Therefore, Sandstorm has the ability to render the particles as either blended textured spherical billboards or points.

When rendering particles as textured billboards, two pieces of information must be determined by the render shader.
The first and easiest is the position of the particle, which is passed to the render shader by the the particle shader through the Transform Feedback model.
The second piece of information that needs to be determined is the eye coordinates, which can be obtained through the built-in variables of the shader.
Once the need information is obtained, a normal centered at the particles position and points to the eye can be calculated.
This normal can be found by the following equation:
\[
	normal = gl\_ModelViewMatrixInverse * Up\_Vector
\]
where $gl\_ModelViewMatrixInverse$, is the built-in variable that describes the Inverse of the Model View Matrix, and $Up\_Vector$ is the up vector that you are using for your world, such as y-up or z-up.
When that normal has been calculated the four points that make up the corners of the billboard can be calculated and the points for the billboard can be emitted to the framebuffer for rendering.
However, considering that geometry shaders can not currently emit quads, two triangles that form a quad have to be emitted.

Once the billboards have been emitted they are then rendered to an off-screen buffer so that they can be run within a deferred shading shader.

Currently, Sandstorm uses a deferred shading method to blend the particles together so that the more particles there are in a scene the more dense the particle field looks.
The first step is to accumulate the particles, per pixel, so that the more particles that are behind that particular pixel the denser it looks.
This is done by premultiplying the particles RGB in a shader, then blend using: 
\[ 
glBlend(GL\_ONE, GL\_ONE\_MINUS\_SRC\_ALPHA)
\]
which gives:
\[
	RGB = Src.rgb * Src.a + Dst.rgb * (1 - Src.a) 
\]
\[
	  A = Src.a * ONE + Dst.rgb * (1 - Src.a)
\]
Once this is done the particles are ready to be lit, this is done by taking the surface normals and doting them with the light direction.
After the light is done this result can be rendered to a full screen quad with the result textured onto it~\cite{deferred}.
One thing extra that needs to be handled because of this method is that the deferred shading shader needs to know the depth buffer of the scene you use to draw the particles onto.
This would require the user of Sandstorm to render the scene to an offscreen buffer, making sure to attach a depth buffer and passing the depth buffer to the deferred shading shader.

When rendering particles as points, Sandstorm does something similar to the textured spherical billboards.
Instead of rendering a particle as a small point or a small cube, a non-blended non-textured spherical billboard is rendered.
This is done because it is currently computationally cheaper to calculate the normals and points and emit six vertices than it is to emit 36 vertices to make up a cube.
This is done because of code reuse and code size.
Simply leave out the render fragment shader and the deferred shader leads to smaller code size, rather than making a separate branch for point rendering.
Therefore, the same render shader is used, except that the texturing and the blending of the billboards is replaced with a simple coloring method.

\section{Vector Fields}\label{sec:Vector}

The using of vector fields in Sandstorm was necessary so that the behavior particles could be controlled by gathered scientific data.
This section describes how the vector fields are implemented and updated.
The use of vector fields was described in the Updating Particles subsection GPU-based section of this chapter.

The vector fields that are used in Sandstorm are represented as 3D textures.
Textures were used instead of VBOs, because of the existing internal methods for dealing with 3D textures, such as wrapping and indexing the texture as a 3D space.
Also considering that, currently, a vector field describes a 3D rectangular area of space, the whole texture will be used, unlike the particle information textures used in Latta's Million Particle system~\cite{latta} and other particle systems.
A copy of the vector field is represented as a 3D array on the CPU to conform to the split first method.
Doing this allows a main object to maintain the vector field, by updating the vector field according to a simulation, such as a helicopter-desert terrain interaction model.

\section{Multi-contextual}\label{sec:Multicontext}

As previously stated, when dealing in a multi-contextual environment there are several methods that can be used, three of which are: (1) split first where the simulation is replicated on all contexts, (2) split middle where a shared data structure is transmit to all contexts, and (3) split last where the rendering calls are transmitted to all contexts.
Sandstorm uses a split first method to combat the multi-contextual environmental constraints of a 3D Virtual Reality environment.
This method is used for three main reasons:
\begin{itemize}\item The use of Vector Fields to guide particles allows for the predictability of the behavior of particles once created.\end{itemize}
\begin{itemize}\item The use of a perturbation texture for creation of particles allows one perturbation texture to be created and passed to all simulations at initialization.\end{itemize}
\begin{itemize}\item Finally, the use of a GPU-based particle system, allowing the simulation to be distributed across multiple graphics hardware and eliminating the need for communication between GPUs.\end{itemize}
Considering these three reasons, Sandstorm can safely use a split first method for the distribution of the simulation across multiple contexts.

\begin{figure}
	\centerline{\epsfig{file=images/MainClass.png, width=14cm}}
	\caption{The main system structure of the Sandstorm system.}
	\label{fig:mainclass1}
\end{figure}

Figure~\ref{fig:mainclass1}, shows how Sandstorm is designed to utilize the split first method.
At the top of the architecture sits a main object that coordinates the initialization of all the simulation objects and controls the updating and rendering of the simulation objects.
This main object is in turn controlled by the main context of the 3D virtual reality environment.
Each of these simulation objects contain a particle system and the same set of data, data that is given to the simulation object by the main object.
The data that is given to each simulation includes the following: (1) the time lapsed between frames, (2) an updated vector field if one exists, (3) any random numbers that need to be generated, and (4) particle attributes.

\section{Dynamic}\label{sec:Dynamic}

In order to allow for a more diverse and realistic behaving particle system, certain attributes are given the ability to be changed by the user of Sandstorm.
The split first method that Sandstorm's architecture is modeled after, aids in the controlling of the dynamic attributes of the particle system.
The main object passes down any changes to the attributes to the simulation objects and in turn down to the GPUs that the simulation are running on.
A list of Dynamic attributes can be found in Table~\ref{tab:dynamic} .
\begin{table}[h]
\begin{center}
\begin{tabular}{|ll|} \hline
    Size 	   & This attribute determines the size of the particles when they are rendered. \\
	Lifetime   & This attribute determines how long a particle can live. \\
	AreaWidth  & This attribute determines how wide the emission area is. \\
	AreaDepth  & This attribute determines how deep the emission area is. \\
	Maximum	   & This attribute determines maximum amount of particles allowed to be \\
			   & emitted into the system. Keep in mind that this is a soft max \\
			   & and that there is a predetermined maximum amount of particles. \\ 
	Position	& This attribute determines the positions of the emission area. \\ \hline
\end{tabular}
\end{center}
\caption{Table of dynamic attributes.}
\label{tab:dynamic}
\end{table}

