\chapter{Background}\label{ch2}

\section{Helicopter and Dust Simulation}\label{sec:heldust}
Before the question of `what needs to be done' is answered, the question of `why' needs to be addressed.
The Helicopter and Dust Simulation, Heli-Dust, is a scientific simulation in which the effect of a helicopter's downdraft on the surrounding desert terrain is studied.
Heli-Dust, currently being developed at the Desert Research Institute, is designed to run in a virtual reality environment and will need the use of a particle system to display the dust cloud generated by a helicopter.
Heli-Dust was written using the Dust Framework, a framework which allows the developer to setup a scene using an XML file.
A current illustration of Heli-Dust is shown in Figure~\ref{fig:dustframe}.
 
Early prototypes for Heli-Dust implemented a very simple particle system in which particles where emitted and accelerated upwards.
However, it was quickly determined that Heli-Dust would need a much more in-depth particle system, one in which gathered scientific data could be used to `guide' the particles' motion.
It was also determined that the particle system used would have be as efficient as possible, so GPU offloading was considered.
The following sections cover different aspects and issues one would encounter when developing such particle systems.

\begin{figure}
    \centerline{\epsfig{file=images/DustFramework.png, width=12cm}}
    \caption{Screenshot from the Dust Framework project.}
    \label{fig:dustframe}
\end{figure}

\section{Virtual Reality}\label{sec:VR}
The ability to immerse oneself in an application or simulation has interested both scientists and engineers alike.
Such applications and simulations require knowledge about how virtual reality works and what constraints you will be facing.
In the following section you will find a description of the basics of a virtual reality environment like the one that will be used with Sandstorm, such as depth cues and stereoscopic displays. 
Also in the following subsections there is a description of the relevant constraints when developing a piece of software such as Sandstorm in a virtual reality environment.

\subsection{Depth Cues and Stereoscopic Displays}\label{sec:Depth}

First we must discuss visual depth cues.
A depth cue is an indicator in which a human can perceive information regarding depth ~\cite{sherman03:understanding}.
These depth cues come in many shapes and sizes and include monoscopic, stereoscopic, and motion depth cues. 
A monoscopic depth cue is one in which only information from a single eye, or information for a single image is available. 
This information can include: position, if an object is behind something else; size, things in the distance appear smaller; and brightness.
A stereoscopic depth cue is one in which information is obtained from two eyes; this information is derived from the parallax between the different images received by each eye.
Thus, stereoscopic depth cues depend on the parallax between objects, which is the apparent displacement of objects viewed from different locations.
Motion depth cues come from a phenomenon known as motion parallax, which is caused by the changing relative position between the head and the object being observed.
Depth information is observed by noticing that objects in the distance move less than objects closer to the viewer.

Now that we have looked at what a depth cue is, let's look at how virtual reality uses these depth cues to fool our eyes into believing that a 2D image is a 3D image.
Rendering a particular viewport of each eye on a stereoscopic display allows the user to view stereoscopic depths where otherwise they would not be able to.
Stereoscopic displays come in all shapes and sizes including but not limited to: CAVE systems that allow the user to ``step" in the world(Figure~\ref{fig:cave}), head mounted displays that afford some privacy(Figure~\ref{fig:hmd}), and single walled displays.

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=12cm]{images/cave.jpg}
    \end{center}
    \caption{An example of a CAVE system.}
    \label{fig:cave}
\end{figure}

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=10cm]{images/hmd.png}
    \end{center}
    \caption{A example of a Head mounted display.}
    \label{fig:hmd}
\end{figure}


There are two ways of accomplishing stereoscopic vision, and they are active and passive stereo.
An active stereo system uses a combination of glasses with built-in shutters, and a projector or projectors that rapidly switch back and forth between the left and right eye image. 
The shutters in the glasses allow the user to only see one image at a time, thus creating the illusion of depth. 
Active stereo has the benefit of allowing for a very deep sense of depth ~\cite{sherman03:understanding}.
Passive stereo uses two projectors for a single screen, one view for each eye. 
A polarized filter is used on each projector, giving the light coming out of the projector a predetermined polarization. 
The user then wears a set of polarized glasses, each eye has the same polarization as one of the filters used on one of the projectors.
 Each eye only sees one of the images creating the the illusion of depth ~\cite{sherman03:understanding}. 
Most CAVE virtual reality systems will use active stereo because it gives a very deep sense of depth, giving the viewers the sense that they are walking into another world. 

\subsection{Multiple Contexts}\label{sec:MultiContext}

A typical virtual reality application is split into multiple contexts: a main context and multiple rendering contexts.
The main context usually handles things like input abstraction and simulation gathering, while the multiple rendering contexts handle the rendering of the scene according to the view that its screen is suppose to have.
Because of these multiple contexts, a virtual reality application developer needs to make sure that all context sensitive information and algorithms are multiple context safe.
Things like random number generation need to be generated in the main context and passed down to the render contexts.
Also a major consideration, especially for particle systems, is that if billboards are drawn each rendering context needs to get the correct coordinates of the camera.

\subsection{Virtual Reality Toolkits}\label{sec:Virtual Reality Toolkits}

There are many virtual reality toolkits and libraries that are currently available for use in a virtual reality applications.
Such toolkits and libraries usually handle things like creating stereosopic images, setting up the virtual reality environment, and handling distribution methods.
This section describes two such toolkits/libraries: VRUI and FreeVR.

Virtual Reality User Interface, or VRUI, is a virtual reality development toolkit that was developed by Oliver Kreylos at UC Davis ~\cite{kreylos07:vrui}. Figure~\ref{fig:vrui} is an example of an application written with VRUI.
VRUI's main mission is to shield the developer from a particular configuration of a virtual reality environment.
This will allow developers to develop quickly and in a portable and scalable fashion.
VRUI accomplishes this mission by the abstraction of three main areas that are common to all virtual reality environments and systems: display abstraction, distribution abstraction, and input abstraction.

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=12cm]{images/Vrui-1.png}
	\end{center}
	\caption{A sample application written with VRUI.}
	\label{fig:vrui}
\end{figure}


The display abstraction provides OpenGL rendering contexts that are set up in such a fashion that rendering a scene will display that scene on all rendering surfaces.
These rendering surfaces run the gambit from monitors to screens to head-mounted displays.
This display abstraction is also in charge of rendering the scene in the correct stereographic mode.

The distribution abstraction provides the developer with a transparent environment in which the distribution method is hidden from the developer.
There are three types of distribution as defined by VRUI: split first, split middle, and split last. 
Split first is where an application is replicated on all the computers in the environment, and data is synchronized by hardware.
Split middle is a method in which a shared data structure, such as a scene graph, is used to transmit data from a main application/computer (or cluster) to all the rendering applications/computers.
Finally split last, consists of an OpenGL API calls are broadcast from a main application/computer to all rendering applications/computers.

According to VRUI, a toolkit must hide the differences in input hardware and provide a uniform view of the set of connected input devices. 
Also, the toolkit needs to provide common mechanisms to access these input devices and specify input requirements at a higher level.

One of the best features of VRUI is its easy to program menu system. 
This system allows a developer to program menus for use in a 3D virtual reality environment. 
When programming for a virtual reality environment, one is usually forced to map actions to
buttons. 
This can be somewhat of a hassle because certain actions don't always map well to a single button. Some actions map better to a slider or an interactive graph where points can be dragged to modify the state of the program. 
Sometimes the number of actions that need to be done might be too large for the user to remember all of them and might cause the user to forget what actions they can perform. 
Being able to choose actions from a menu of actions can alleviate this problem.

VRUI was chosen as the development environment for Sandstorm, due to its to program menus.
The menus allow Sandstorm the flexibility to change itself on the fly.

Developed and maintain by William Sherman, FreeVR is an open source virtual reality interface/integration library~\cite{sherman:freevr}.
FreeVR was designed to work on a diverse range of input and output hardware and also to work on existing as well as newly established VR systems.
However, FreeVR is not a content engine; it does not contain a scenegraph or other content organizational features.
In this regard FreeVR is a lot like VRUI; however, there are some major differences between FreeVR and VRUI.
The first difference is that FreeVR has no menu system; it leaves that up to the user.
Also unlike VRUI, FreeVR is currently designed to work on shared memory systems, whereas VRUI focuses on clusters.

\section{Wrath of Khan and the Genesis Effect}\label{sec:WOK}
The first particle system ever used was implemented for use in the movie Star Trek: The Wrath of Khan and was outlined in a paper by William T. Reeves~\cite{reeves}.
In the paper, {\it Particle Systems - A Technique for Modeling a Class of Fuzzy Objects}, Reeves describes the particle system that was used to create the Genesis Effect, which can be seen in Figure~\ref{fig:gensis1} and Figure~\ref{fig:gensis2}.

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=12cm]{images/GenesisEffect1.png}
	\end{center}
	\caption{Surface impact.}
	\label{fig:gensis1}
\end{figure}
\begin{figure}[h]
	\begin{center}
		\includegraphics[width=12cm]{images/GenesisEffect2.png}
	\end{center}
	\caption{Spearding across the surface.}
	\label{fig:gensis2}
\end{figure}

The paper introduces particle systems as the modeling of an object as a cloud of primitive particles that define its volume ~\cite{reeves}.
During the course of the system's lifetime; particles are generated into the system, particles move and change form within the system, and then they die and are removed from the system.

The paper categorizes particle systems as a ``fuzzy" object in which they do not have smooth, well-defined, and shiny surfaces; instead their surfaces are irregular, complex, and ill-defined.
A method for modeling and displaying these fuzzy objects called particle systems is presented in this paper.
There are three main differences between modeling regular objects and particle systems. 
First, the surfaces of the fuzzy object are not smooth, well defined, and made up of many primitive elements. 
Instead they are defined as clouds of primitive particles that represent its volume.
Second, a particle system is a dynamic object, one in which its elements are born, die, and change shape.
Lastly, the object that the particle system represents usually is non deterministic, since the shape of the object isn't always well known, such as fire.

Reeves determined that during each frame five steps need to be performed: (1) particles are born, (2) each new particle is assigned individual attributes, (3) any particles that have existed within the system and have passed their prescribed lifetime are extinguished, (4) the remaining particles are moved and transformed according to their dynamic attributes, and (5) an image of the living particle is rendered in a framebuffer.
Any number of instructions that make sense can be used in the above set.
For example the updating of the particles positions can be described by a series of partial differential equations, or even a vector field.
In the following sections you will find a description of each of the steps listed above.

\subsection{Particle Generation}\label{ParticleGen}

By means of controlled stochastic processes, particles are generated into the particle system.
One such process determines the number of particles that are created during each interval of time.
The number of particles created strongly influences the density of the particle system, thus it must be controlled carefully.

Two methods are proposed for controlling the number of particles being created.
First the designer can control the mean number of particles created at a frame and also a variance.
The actual number of particles created per frame is
\[
NParts_{f} = MeanParts_{f} + Rand() * VarParts_{f},
\]
where $Rand$ is a procedure returning a uniformly distributed random number between $-1.0$ and $+1.0$, $MeanParts_{f}$ the mean number of particles, and $VarParts_{f}$ the variance.

The second method, the number of particles created during a time step can be controlled by the amount of screen area the particle system takes up.
The mean number of particles created per unit of screen area and its variance can be controlled by the designer.
The particle system can determine the view parameters at a particular frame and calculate the approximate screen area it covers.
The equation for such a control method is
\[
	NParts_{f} = (MeanParts_{saf} + Rand() * VarParts_{saf}) * ScreenArea,
\]
where $MeanParts_{saf}$ is the mean per screen area, $VarParts_{saf}$ its variance, and $ScreenArea$ the particle system's screen area.
Reeves described this as a level of detail method for the particle system, the further away from the view the particle system was the less particles it created.

Another stochastic process for controlling the particle system, is to vary over time the mean number of particles created per frame.
This allows the particle system to increase and decrease in intensity over time, just like fire and clouds would increase and decrease in their intensity over time.
To do this the particle system uses a simple linear function
\[
MeanParts_{f} = InitialMeanParts + DeltaMeanParts x (f - f_{0})
\]
where $f$ is the current frame, $f_{0}$ the first frame during which the particle system is alive, $InitialMeanParts$ the mean number of particles at this first frame, and $DeltaMeanParts$ its rate of change.

\subsection{Particle Attributes}\label{ParticleAttrib}

Whenever a new particle is created, the particle system has to determine values for the following attributes; (1) initial position, (2) initial velocity (speed and direction), (3) initial size, (4) initial color, (5) initial transparency, (6) shape, and (7) lifetime.
The initial position of each particle is determined by a $generation \ shape$, in which particles are emitted from a region of space around the origin of the particle system.
Reeves implemented several different generation shapes, a sphere of radius $r$, a circle of radius $r$, and rectangle of length $l$ and width $w$.
Figure~\ref{fig:reeves} shows a typical spherical generation shape.

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=12cm]{images/reeves.png}
	\end{center}
	\caption{Typical spherical generation shape ~\cite{reeves}.}
	\label{fig:reeves}
\end{figure}

The generation shape also determined the initial direction of a particle, sphere being outward from the origin, and for the circle and rectangle the direction would be upward and away from the surface of the generation shape.
Particles were allowed to deviate from the upward and away direction of the circle and rectangle by a small amount.
The remaining attributes such as shape, size, color, etc, can be determined by built in control parameters.

\subsection{Particle Dynamics}\label{ParticleDyn}

Each particle within a particle system moves in a three-dimensional space and has other attributes changing over time.
To update the particles' position the particle system simply adds the velocity vector to the position vector, obtaining the new position of the particle.
An acceleration factor to modify the particles' velocity can be added to add a bit more realism and complexity to the particle system.
A particular particle's color can change over time and changes according to a rate-of-color-change parameter.
Other attributes such as transparency and size of particles could also be controlled with similar rate-of-change parameters.

\subsection{Particle Extinction}\label{ParticleExt}

When a particle is created it is given a maximum lifetime, measured in frames, in which it is allowed to exist.
During each frame computation, the lifetime is decremented and once the lifetime reaches zero the particle dies.

Other methods were available to kill particles when they no longer contribute anything to the image.
One method was if the intensity of a particular particle drops below a threshold the particle was killed.
The other methods being that if a particle that moves more than a certain distance in a given direction from the particle system's origin of its parent the particle was also considered for termination.

\subsection{Particle Rendering}\label{ParticleRender}

The rendering algorithm renders the particles once their position and appearance parameters are determined.
Reeves concluded that rendering fuzzy objects was just as difficult to render as regular surface based objects.
Primitives of fuzzy objects could be obscured by other objects, could be transparent, and they can cast shadows on other objects, not to mention that they can coexist in a scene with regular objects.

Two assumptions where made to allow for the simplification of the rendering of the particles.
The first assumption was that particles do not intersect with other surface-based objects, thus the rendering algorithm need only handle particles. 
The other assumption was that particles where considered to be point light sources; therefore, determining hidden surfaces was no longer a problem, each particle adds a bit of light to the pixels that it covers.
With this algorithm and assumption, no visibility sorting of the particles was needed.

\section{GPU offloading}\label{GPUoff}

In recent years, graphics vendors have replaced areas of fixed functionality with areas of programmability.
Two such areas of programmability are the vertex and fragment processors.
These two processors handle a magnitude of fixed functionality functions, but also allow for custom programs to run on them.
However, if a custom program (shader) is run on one of the two processors, the fixed functionality of each processor is disabled.
Several programming languages where created to aid in the development of shaders, one such language is the OpenGL Shading Language(GLSL)~\cite{glsl}.
GLSL is a C/C++ like programming language that was developed by the OpenGL development team, and will be the only shading language that we will consider.

\subsection{Vertex and Fragment Shaders}\label{sec:VertFrag}

The vertex processor is a programmable unit that operates on incoming vertex values and their associated data.
Some of the duties of the vertex processor are: vertex transformation, normal transformation and normalization, texture coordinate generation and transformation, and lighting.
Data enters the vertex shader through special variables or textures and exits through special output variables.

The fragment processor is a programmable unit that operates on fragment values and their associated data. 
Some of the duties of the fragment processor are: operations on interpolated values, texture access, texture application, fog, and color sum.
As with vertex shaders, data enters the fragment shader through special variables and/or textures but exits as rendering results.

Together, both the vertex processor and the fragment processor are part of the OpenGL programmable pipeline.
In Figure~\ref{fig:reeves1} you can find a diagram of how the OpenGL programmable pipeline is laid out.

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=12cm]{images/pipeline.png}
	\end{center}
	\caption{OpenGL Programmable pipeline ~\cite{pipeline}.}
	\label{fig:reeves1}
\end{figure}

\subsection{Geometry Shaders and Shader Model 4}\label{sec:Shader4}

With the introduction of Shader Model 4, considering with the release of the 8800 series graphics cards from Nvidia certain enhancements were added to GLSL and OpenGL to increase the performance of GPU based program.
Two such enhancements were geometry shaders and transform feedback.

Unlike its counter parts, the geometry shader has some unique features. The most important feature being the ability to create vertices on the fly.
Both the vertex and fragment shader could not create vertices, all they could do is transform them.
But the geometry shader has ability to create vertices, thus allowing the geometry shader to create new geometry without having to access the CPU at all.

Other enhancements to GLSL and OpenGL of interested in is transform feedback.
This nice little add-on allows a shader to specify an output vertex buffer object, so that another shader can use that same vertex buffer object as an input buffer.
Thus a developer can create multi-pass shaders that do not need to relay information back to the CPU for the other passes.

\subsection{Scientific Computation on the GPU}\label{sec:GPUcomp}

In the days before shaders, the GPU was used just for rendering.
But with the advent programmable shaders, the GPUcan now be to aid in scientific computation.
One can `trick' the GPU into thinking that it is working on rendering information.
Two methods for `tricking' the GPU are to encode data into textures or into vertex buffer objects, or VBOs.

Texture mapping is a powerful mechanism built into OpenGL. At the time of OpenGL's birth it was nothing more than a way to paste an image on a surface; now it can be used for much more~\cite{rost06:glsl}.
With the programmability introduced with the OpenGL Shading Language, texture mapping has become a much broader definition.
Programs can now use shaders to read values from any number of textures and use them in any way that makes sense.
This can run the gambit of sophisticated algorithms that use the result of one texture access, to defining parameters of another, to storing intermediate rendering results.
Textures can also be used to store values for complex functions or actually encode those complex functions themselves.

Vertex buffer objects can also be used to store values for complex functions or actually encode the complex functions themselves.
But unlike textures, vertex buffer objects allow data to be cached into high-performance graphics memory on the GPU~\cite{nvidia:vbo}.

Using the GPU for scientific computation can provide added realism to scientific visualization applications.
This added realism can be accomplished by freeing up cycles on the CPU, thus letting more calculations to occur per time interval or increase the number of frames per second.

\section{Related Work}\label{Related}
In the following subsections you will find three particle systems that Sandstorm takes some inspiration from.
They mostly describe different aspects of creating GPU based particle system, but also describe the general issues when developing modern particle systems.
\subsection{Uber Flow}\label{Uber}
UberFlow is a system for real-time animation and rendering of large particle sets using GPU computation and memory objects in OpenGL~\cite{kipfer04:uber}. 
The authors of Uberflow considered the use of the GPU because of the ability to offload the computation from the CPU and inherent parallelism and communication on the GPU.
UberFlow's method relies on computing intermediate results on the GPU, saving these results in graphics memory, and then using them again as input into the geometry units to render images in the frame buffer.
These intermediate results are stored in a texture, in which particle position, lifetime, and velocities are stored.
During each time step UberFlow conducts the following events: emission, collisionless motion of particles, sorting particles, pairing of collision partners, collision response, enforcement of boundary conditions and particle rendering.

During emission, a 2D RGBA texture map containing the particles position and lifetime along with a second texture containing velocities are compared and updated.
These textures are passed on to the next pass of the particle system.
In this next pass, collisionless particle motion is performed with each particle's displacement updated according to the time interval from the last time.
The particles are then sorted either by resolving inter-particle collisions and rendering particles as opaque primitives or it sorts particles according to their distance to the viewer and renders the particles as semi-transparent~\cite{kipfer04:uber}.
After that, the position texture is scanned for any collisions, and the output of this pass is fed into the collision response pass, where the colliding particles positions' are updated accordingly.
After particle-particle collisions are calculated, the shader collides with static parts of the scene by creating a 3D texture map of the scene and comparing it with the position texture map of the particles.
Once all of this is done the particles are then rendered by looking up their position in the position texture and using those positions as input to a typical rendering process.

With these techniques UberFlow was capable of rendering a quarter of a million particles with about ten frames per second.
Keep in mind that this paper was written in 2004.
Since then graphics hardware have made leaps and bounds, and the techniques used in UberFlow can be adapted for use in Sandstorm.
An example of UberFlow's capability is shown in Figure~\ref{fig:uber}.

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=12cm]{images/Uber-1.png}
    \end{center}
    \caption{An example of UberFlow's capability.}
    \label{fig:uber}
\end{figure}

\subsection{Building a Million Particle System}\label{Million}

In 2004, Lutz Latta wrote a paper entitled ``Building a Million Particle System", in which Latta describes an implementation of a particle system on the GPU ~\cite{latta}.
Latta believed that such a particle system would be capable of rendering up to 1 million particles.

Real-time particle systems are often limited by two factors, the fill rate of the particular GPU they run on, and the CPU to GPU communication.
The number of pixels a GPU can draw each frame, or the fill rate, is a limiting factor when the size of the particles is large.
Considering that realism of a particle system increases when small particles are used, the fill rate limitation loses importance~\cite{latta}.
The second limitation, CPU to GPU data transfer bandwidth, now dominates many particle systems.
Because the particle system has to share the graphics bus with many other rendering tasks, most CPU based particle systems can only achieve up to 10,000 particles per frame~\cite{latta}.
Therefore, Latta believed that it was necessary to minimize the amount of communication of particle data across the graphics bus.

In a particle system, the most important attributes of a particle are its position and velocity.
In order to create a particle system that uses the GPU, these attributes have to be stored somewhere where a shader will be able to access them.
Textures were used to accomplish this goal in this particular particle system.
Two pairs of textures, each pair containing one texture holding the position and the other holding the velocity of each particle, were used to allow shader access to the position and velocity information.
Two pairs were used due to the fact that a texture cannot be used as both an output and input at the same time, thus creating a double buffering technique to compute new data, see Figure~\ref{fig:latta}.

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=12cm]{images/lattabuffer.png}
    \end{center}
    \caption{An example of how Latta stores particle information.}
    \label{fig:latta}
\end{figure}
 

The simulation and rendering of the particles in the particle system were split into 6 basic steps: (1) Process birth and death, (2) Update velocities, (3) Update positions, (4) Sort for alpha blending(optional), (5) Transfer texture data to vertex data, and (6) Render particles~\cite{latta}.

In this particular particle system, particles could either exist forever or were given a limited time to live.
The creation of new particles in the system requires the association of new data in an available index in the two information textures.
Being serial by nature, allocation could not be done efficiently on a massively parallel device such as the GPU.
Therefore, the allocation of a new particle was handled on the CPU, where an available index to the textures was determined and passed to the GPU.
Particle death was handled both on the GPU and the CPU, when a particle dies the GPU would stop updating and rendering, and the CPU would add the index of the dead particle back to the group of indices available for allocation.

The next step was to update the velocities of the particles. 
A fragment shader was used for this step.
The shader was given access to the velocity texture by rendering that texture to a screen-sized quad.
The texture used would be one of the double-buffered velocity textures, while the other texture was set as the render target for the shader and would hold the new velocities.
The shader would update the velocities by first applying any global forces, such as gravity and wind to the particles' velocities.
Once that was done any local forces were applied to the velocities.
Such forces include magnet attraction and repulsion.
Then collision detection was perform, and the shader would determine the next position of the particle and correct its velocity accordingly.

Once the particles' velocities were updated, it was time for the particles' position.
A similar method was used to bind the texture for use in the shader as was used in the updating of the velocities.
A simple Euler integration was used to update the particles' positions.
That Euler integration was,
\[
p = p' + v * delta_t
\]
where $p$ is current position and $p'$ is the previous position, $v$ is the current velocity, and $delta_t$ is the time between frames.

Sorting for alpha blending (optional) was used to sort particles based on distance so that the particles in the front would be blended correctly.
A simple ``odd-even merge sort" algorithm was used by the GPU to allow for the exploitation of the GPU's parallelism.
Also the sort had a constant number of iterations for a data set of a given size. 

After the positions of the particles were determined it was time to transfer the texture data to vertex data to allow for the rendering of the particles.
``Uber-buffers", also called super buffers, which basically are a data-agnostic storage of vertex or fragment data in a buffer, were used ~\cite{latta}.
These uber-buffers allow for the accelerated asynchronous copying of data inside the GPU memory.
Considering that particles can be rendered as either point sprites, triangles, or quads, the uber-buffers had to replicate the corresponding number of vertices.
To avoid this overhead, the particle system used point sprites ~\cite{latta}.

Once the particles were transformed from texture memory to vertex memory they were ready for rendering to the frame buffer.
During rendering other attributes, such as color and size, were computed inside the vertex shader.
As mentioned before, the particles were rendered as point sprites to reduce the workload on the vertex shader.

\subsection{Particles}\label{ParticleGS}

This next particle system is a bit unusual since it does not have a paper associated to it and instead may be found online ~\cite{ParticleGS}.
This particle system, found on Microsoft's MSDN2 website, uses the latest and greatest in graphics technology to out perform its older counter parts.
Also this particle system was written in DirectX10, rather than a free shading language like GLSL or Cg.

With the advent of geometry shaders, the ability to output arbitrary amounts of vertices has allowed GPU particle systems to go one step further in becoming CPU independent.
Instead of visualizing particles as point sprites, the geometry shader can now be used to create a textured billboard to be used as particles, and this particle system does just that.

Also, this sample particle system uses the stream out capabilities of the geometry shaders to store results of particle calculations into an output buffer.
The output buffer is then used in a second pass and fed into the rendering shader, where the position of the particles are used to render the appropriate particle.

This particle system was studied because it described a more efficient method for the creation of particles as compared with the two previous particle systems.
In this particle system, a geometry shader controls the creation and destruction of particles by either outputting new geometry, which is encoded with a particles position and velocity, or avoiding writing existing geometry.
This method allows the geometry shader to allocate particle's to a vertex buffer object, which in turn can increase and decrease in size according to the amount of particles that are alive.
This eliminates the need for a CPU based algorithm for the allocation of particles to a fixed size texture.
