University of Nevada Reno

Sandstorm: A Dynamic Multi-contextual GPU-based Particle System

using Vector Fields for Particle Propagation

A thesis submitted in partial fulfillment of the requirements for the degree of Master of Science

in Computer Science

by

Michael John Smith

Dr. Frederick C. Harris, Jr., Thesis Advisor

May, 2008

Abstract

The use of Virtual Reality(VR) to visualize scientific phenomenon, is a quite command and useful occurrence. Virtual Reality can allow a scientists to immerse them selfs in the phenomenon that they are study. One such phenomenon currently under study is the dust could that is kicked up by a helicopter’s down-darft. In order to study such a phenomenon, an application will need to employ a Particle System to create such visual effects. A Particle System that create such effects would need to be able to handle the update and rendering of large amounts of particles. Particles will also need to follow a scientific model during the course of there life time. Also considering the Virtual Reality Environment in which it would be used in, the particle system would also need to be aware of multiple contexts. Sandstorm, A dynamic multi-contextual GPU-based particle system which uses vector fields for particle propagation is presented in this paper.

Acknowledgments

The work shown has been sponsored by the Department of the Army, Army Research Office; the contents of the information does not necessarily reflect the position or the policy of the federal government, and no official endorsement should be inffered. This work is funded by the CAVE Project (ARO# N61339-04-C-0072) at the Desert Research Institute.

Fisrt of all I would like to thank my committee for their help in getting my this far. I would like to personally thank my committee chair, Dr. Frederick C. Harris Jr., who has been a valued teacher and mentor throughout my entire college carrier. I would also like to thank my other committee members, Dr. Sergiu Dascalu and Dr. Scott Bassett, who have both been instramental throughout my graduate school experience. I extend my thanks to all the help that I have receive from my co-workers, especially Roger Hoang. Finally, many thanks go out to all of my family and friends, who’s undying support has help me threw the most difficult of times.

Contents

Abstract i

List of Figures iv

List of Tables v

1 Introduction 1

2 Background 4 2.1 Helicopter and Dust Simulation . . . . . . . . . . . . . . . . . . . . . 4 2.2 Virtual Reality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2.1 Depth Cues and Stereoscopic Displays . . . . . . . . . . . . . 5 2.2.2 Multiple Contexts . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.3 VRUI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.3 Wraith of Khan and the Genesis Effect . . . . . . . . . . . . . . . . . 8 2.3.1 Particle Generation . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3.2 Particle Attributes . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.3 Particle Dynamics . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.4 Particle Extinction . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3.5 Particle Rendering . . . . . . . . . . . . . . . . . . . . . . . . 12

2.4 GPU offloading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4.1 Vertex and Fragment Shaders . . . . . . . . . . . . . . . . . . 13 2.4.2 Geometry Shaders and Shader Model 4 . . . . . . . . . . . . . 13 2.4.3 Scientific Computation on the GPU . . . . . . . . . . . . . . . 14

2.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5.1 Uber Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5.2 Buidling a Million Particle System . . . . . . . . . . . . . . . 16 2.5.3 ParticleGS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Sandstorm the Idea 21

4 Sandstorm Software Specification and Design 23 4.1 Sandstorm Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 System Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3 Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.4 Use Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.5 Modeling and Design . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.5.1 Main Class Hierarchy . . . . . . . . . . . . . . . . . . . . . . . 26 4.5.2 Utility Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5 Sandstorm Prototype 34

5.1 GPU-Based . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.1.1 Creating and Destroying Particles . . . . . . . . . . . . . . . . 34 5.1.2 Updating Particles . . . . . . . . . . . . . . . . . . . . . . . . 38 5.1.3 Rendering Particles . . . . . . . . . . . . . . . . . . . . . . . . 38

5.2 Vector Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.3 Multi-contextual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.4 Dynamic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

6 Results 42

7 Conclusions and Future Work 44

List of Figures

2.1 A sample application written with VRUI. . . . . . . . . . . . . . . . . 7 2.2 Surface impact (a) Spearding across the surface (b). . . . . . . . . . . 9 4.1 Use cases for the Sandstorm prototype. . . . . . . . . . . . . . . . . . 27 4.2 The main system structure of the Sandstorm system. . . . . . . . . . 29

List of Tables

4.1 Functional requirements for the Sandstorm prototype application… 26 4.2 Non-functional requirements for the Sandstorm prototype application. 28 5.1 Table of dynamic attributes. . . . . . . . . . . . . . . . . . . . . . . . 41

Chapter 1

Introduction

In the following chapters you will find a discription of Sandstorm and all the issues surrounding its development. In the next chapter, Chapter 2, you find a background on the project, which includes all the information one would need to know about the issues surrounding the development of such a project. Chapter 3, will introduction what Sandstorm hopes to become. An overview of how Sandstorm was desgined will be presented in Chapter 4. In Chapter 5, you will find a discription of how Sandstorm was engineered. Result and A Consculsion and future work can be found in Chapters 6 and 7.

In the realm of Virtual Reality it is quite common for an application to implement a particle system to heighten the quality of immersion or to display scientific data. Such is the case in applications such as fluid dynamic applications, dust simulation, military training simulations, and fire simulation applications. Nonetheless, what ever application the particle system is used in, it needs to look realistic or at least behave realistically. Vector fields can be used to ’guide’ particles according to real scientific data, while also adding to realism. Vector fields will be discussed in more depth later on in the paper.

Virtual Reality applications and simulations require a multiple contextual environment in which to run [?] and [?]. A main context, which is in charge of updating simulations and communication, controls several rendering contexts. Each of these rendering contexts are responsible for rendering to one of the screens of a Virtual Reality environment. The rendering contexts will run independent of each other, and communication between them is usually only done when they are ready to draw. This design requirement can cause problems when using context sensitive graphics, such as particle systems. So special consideration has to be taken into account when dealing with particle systems in a multi-contextual environment. One such consideration is that most particle systems use random numbers to seed a particular particle’s initial speed and direction. Since the a copy of the particle system will be run pre-context, we need to make sure that each context gets the same random number every time one is needed. Also, the particles need to be updated consistently across all particle systems. Both of these considerations will be account for later in this paper.

Virtual Reality applications and simulations utilize a multiple context/thread environment to handle both complex data manipulation and intensive rendering. This complex data manipulation leaves little to no room for a particle system to run on a large scale, large enough to allow for rich data sets. GPU offloading techniques have been proven to allow applications and simulations to offload work, such as particle systems calculations on to the graphics hardware freeing up more resources on the CPU. Textures and Vertex Buffer Objects can be used to encode complex functions, or to really large data sets to the shaders. One has to be careful however, a GPU offloading algorithm has to be design such that data does not need to be constantly passed back and forth between the GPU and CPU. This can cause the bus to be overloaded and actually slow the rendering process down. Transform Feedback and Geometry Shader, both of which are part of Shading Model 4, can help elevate this data passing problem[cite].

Also, it is often the case that particle systems are written such that once the are set into motion there is every little to no changing of variables that are part of the particle simulation. Keeping that in mind, the following paper describes Sandstorm, a particle system that has the ability to be dynamic changed while being multicontextual and utilizing GPU offloading and vector fields for particle propagation.

The following chapters you will find a description of Sandstorm and all the issues surrounding its development. In the next chapter, Chapter 2, you find a background on the project, which includes all the information one would need to know about the issues surrounding the development of such a project. Chapter 3, will introduction what Sandstorm hopes to become. An overview of how Sandstorm was designed will be presented in Chapter 4. In Chapter 5, you will find a description of how Sandstorm was engineered. Result and A Conclusion and future work can be found in Chapters 6 and 7.

Chapter 2

Background

2.1 Helicopter and Dust Simulation

Before the question of ’what needs to be done’ is answered, the question of ’why’ needs to be answered. The Helicopter and Dust Simulation, Heli-Dust, is a scientific simulation in which the effect of a helicopter’s downdraft on the surrounding desert terrains, is studied. Heli-Dust, currently being developed at Desert Research Institute, is designed to run in a virtual reality environment and will need the uses 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.

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 that would be used has to be as efficient as possible, so GPU offloading was considered. The following sections will cover different aspects and issues one would encounter when developing such particle systems.

2.2 Virtual Reality

The ability to immerse one self in an application or simulations has interested both scientist 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 section is a description of the relevent constraints when developing a piece of software like Sandstorm in Virtual Reality.

2.2.1 Depth Cues and Stereoscopic Displays

First we must discuss visual depth cues. A depth cue is an indicator in which a human can perceive information regarding depth [?]. These depth cues come in many shapes and sizes and the 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 something is behind something else, size things in the distance appear smaller, and brightness, Figure 1 is an example of such cues. A Stereoscopic depth cues is one in which information from two eyes, this information is derived from the parallax between the different images received by each eye. Thus stereoscopic depth cues depended on the parallax between objects, which is the apparent displacement of objects viewed from different locations. Motion depth cues from a phenomenon known as motion parallax, which is cause 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, lets 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 were 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 see figure 2.2.1, Head mounted displays that afford some privacy see figure 2.2.3, To single walled displays.

There are two ways of accomplishing stereoscopic vision, and they are active and passive stereo. A active stereo system uses a combination of glasses with built in shutters, and a projector(s) 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 creating the illusion of depth. Active stereo has the benefit of allow for a very deep sense of depth [cite]. Passive stereo us two projectors for a single screen, one for the view coming from either 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 have the same polarization as one of the filters used on one of the projectors. Each eye only sees one of the images, also creating the the illusion of depth[3]. Most Cave Virtual Reality systems will use active stereo, because of its ability of allowing for a very deep sense of depth, giving the view the sense that they are walking into another world.

2.2.2 Multiple Contexts

A typical Virtual Reality application is split into multiple contexts, a main context and multiple rendering contexts, such as in figure 2.2.2. The main context usually handles things like input gathering 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 context, a Virtual Reality appilcation 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.

2.2.3 VRUI

Virtual Reality User Interface, or VRUI, is a virtual reality development toolkit that was developed by Oliver Kreylos at UC Davis[cite], figure 4 is an example of 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 misison by the abstraction of three main areas that are common to all Virtual Reality environments and systems; Display abstraction, Distribution abstraction, and Input abstraction.

Figure 2.1: A sample application written with VRUI.

The display abstraction provides a 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, or 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. Lastly split last, where the OpenGL API call stream is 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, toolkit needs to provide common mechanisms to access these input devices, and specify input requirements at a higher level.

One of the nicest 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 some what of a hassle however, 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. Also, sometimes the number of actions that one needs to be done might be to large for the user to remember all of them and might cause the user to forget what actions they can perform. Being able to choice actions form a menu of actions can elevate this problem.

VRUI was chosen as the development environment for Sandstorm, for its easy to program menus. The menus will allow Sandstorm to flex its ability change itself on the fly.

2.3 Wraith of Khan and the Genesis Effect

This paper has been talking about particle systems, but never talked about what particle systems are. The first particle system ever to be used was used in the movie Star Trek The Wrath of Khan, and was written about a paper by William T. Reeves[cite]. In the paper, Particle Systems - A Technique for Modeling a Class of Fuzzy Objects, Reeves describes a particle system that was used to create the Genesis Effect, which can be seen in figure 2.3.1 and 2.3.2.

a. b. Figure 2.2: Surface impact (a) Spearding across the surface (b).

The paper introduces particle systems as, modeling an object as a cloud of primitive particles that define its volume[cite]. During the course of the systems lifetime, particles are generated into the system, move and change form within the system, and then die and are removed from the system.

The paper categories 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 display these fuzzy object called particle systems is presented in this paper. There are three main difference between modeling regular objects and particle systems. First, the surfaces of the fuzzy object are not the smooth, well define, and made up of many primitive elements, instead they are defined as clouds of primitive particles that represents its volume. Second, a particle system is a dynamic object, one in which its elements are born, they die, and change shape. Lastly, the object that the particle system represents usually are non-deterministic, since the shapes of the represent object aren’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 past their prescribed lifetime are extinguished, (4) the remaining particles are moved and transformed according to their dynamic attributes, and finally (5) an image of the living particle is rendered in a frame buffer. Any number of instruction, 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 descripition of each of the steps listed above.

2.3.1 Particle Generation

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

Two methods are proposed for the controlling of 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

NP arts_{f} = MeanP arts_{f} + Rand()xV arP arts_{f},

where Rand is a procedure returning a uniformly distributed random number between -1.0 and +1.0, MeanP arts_{f} the mean number of particles, and V arP arts_{f} the variance.

The second method, the number of particles create at a time step can be control 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

NP arts_{f} = (MeanP arts_{saf} + Rand()xV arP arts_{saf})xScreenArea,

where MeanP arts_{saf} is the mean per screen area, V arP arts_{saf} its variance, and ScreenArea the particle system’s screen area. Reeves saw this a level of detail method for the particle system, the further away from the view the particle system was, the less particles it would create.

Another stochastic process for controlling the particle system, was to vary over time the mean number of particles created per frame. This would allow 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 used a simple linear function

MeanP arts_{f} = InitialMeanP arts + DeltaMeanP artsx(f − f_{0})

where f is the current frame, f_{0} the first frame during which the particle system was alive, InitialMeanP arts the mean number of particles at this first frame, and DeltaMeanP arts its rate of change.

2.3.2 Particle Attributes

Whenever a new particle was 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 the particles is determine 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 2.3.2 shows a typical spherical generation shape.

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 where allowed to deviate from the upward and away direction, of the circle and rectangle, by a small amount. The remain attributes such as shape, size, color, etc, cane be determined by built in control parameters.

2.3.3 Particle Dynamics

Each particle within a particle system move in a three-dimensional space and also have other attributes change 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. An particular particles 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 control with similar rate-of-change parameters.

2.3.4 Particle Extinction

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

Other methods where 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.

2.3.5 Particle Rendering

The rendering algorithm rendered the particles once their position and appearance parameters where determined. Reeves concluded that rendering fuzzy objects was just as difficult to render has regular surface based objects. Primitives of fuzzy objects could be obscure by other objects, they could be transparent and the could 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 point light source, 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.

2.4 GPU offloading

In recent years, graphics vendors have replace areas of fixed functionality with areas of programmability. Two such areas of programmability are the Vertex and Fragment Processors. These two processors handle a mangatude of fixed functionality functions, but also allow for custom programs to run on them. However if a custom program, shader, is run on the 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). 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 be concerned with.

2.4.1 Vertex and Fragment Shaders

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.

****need more info on this section****

2.4.2 Geometry Shaders and Shader Model 4

With the introduction of Shader Model 4, considering with the release of the 8800 series graphics cards from Nvidia, certain enhancements where added to GLSL and OpenGL, to increase the performance of GPU based computer. Two such enhancements where 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 can 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 enhancement to GLSL and OpenGL that we are interested in is Transform Feedback. This nice little addon, 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.

2.4.3 Scientific Computation on the GPU

In the days before shaders, the GPU was used just for rendering. But with the advent these areas of programmability, shaders can now allow the GPU 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,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 so much more[cite]. With the programmability introduced with the OpenGL Shading Language, texture mapping has gotten 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 define 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, VBOs, can also be used to store values for complex functions, or actually encode thus complex functions themselves. But unlike textures, vertex buffer objects allow data to be cached into high-performance graphics memory on the GPU[cite].

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

2.5 Related Work

In the following section you will find three particle system that Sandstorm takes some inspiration from, other can Reeve’s particle system. They mostly describe different accepts of creating GPU based particle system, but also disribe general issue when developing modern particle systems.

2.5.1 Uber Flow

UberFlow is a system for real-time animation and rendering or large particle sets using GPU computation and memory objects in OpenGL[1]. 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 to the geometry units to render images in the frame buffer These intermediate results are stored in a texture, in which particles position, lifetime, and velocities are store. 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, 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 done, each particle’s displacement is updated according to the time interval from last time. The particles are then sorted either by; resolving inter-particle collisions and renders particles as opaque primitives or it sorts particles according to their distance to the viewer and renders the particles as semi-transparent[1]. After that the position texture is scan for any collisions, and the output of this pass is feed into the collision response pass, where the colliding particles positions’ are updated accordingly. After particle-particle collision 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 10 frames per second. Keep in mind that this paper was write in 2004, and since then graphics hardware has made leeps 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 3.

2.5.2 Buidling a Million Particle System

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 believed that such particle system would be capable of render up to 1 million particles.

Real-time particle systems are often limited by two factors the fill rate of the particulur GPU they are run on, and by 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 increase when small particles are used, the fill rate limitation loses importance[cit]. The second limitation, CPU to GPU data transfer bandwidth, now dominates many particle system. Becuase the particle system has to share the graphics bus with many other rendering tasks, most CPU based particle system can only achieve up to 10,000 particles per frame[cite]. 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 where used so 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 where used because considering 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.

The simulation and rendering of the particles in the particle system was 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].

In this particular particle system, particles could either exist forever or where given a limited time to live. The creation of new particle in the system requires the association of new data in an available index in the two information textures. th these techniques UberFlow was capable of rendering a quarter of a million particles with about 10 frames per second. Keep in mind that this paper was write in 2004, and since then graphics hardware has made leeps 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 3. Since, 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 handle on the CPU, where an available index to the textures was determined and passed to the GPU. Particle death was handle both on the GPU and the CPU, when a particle died GPU would stop updating and rendering and the CPU would add the index of the dead particle back to the group of indecies 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 where applied to the velocities, such forces include magnet attraction or repulsion. Then collision detection was perform, the shader would determine the next position of the particle and correct it velocity accordingly Then collision detection was perform, the shader would determine the next position of the particle and correct it velocity accordingly.

Once the particles’ velocities where updated, it was the time particles’ positions. 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′ the previous position, v being the current velocity, and delta_{t} being the time between frames.

Sorting for alpha blending, optional, was used to sort particles based on distance so that the particles in the from would be blended correctly. A simple ”odd-even merge sort” algorithm was used on the GPU to allow for the exploitation of the GPU’s parallelness. Also the sort had a constant number of iterations for a data set of a given size.

After the positions of the particles where determine 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, where used[cite]. 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 replicated the corresponding number of vertices. To avoid this overhead, the particle system used point sprites[cite].

Once the particles where 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 inside the vertex shader. As mention before the particles were rendered has point sprites to reduce the workload on the vertex shader.

2.5.3 ParticleGS

This next particle system is a bit unusual, it does not have a paper associated to it, instead it can be found online[cite]. This particle system that can be found on Microsoft’s msdn2 website uses the latests 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 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 feed into the rendering shader, where the position of the particles are used to render the apporitate particle.

This particle system was study because it describe a more efficient method for the creation of particles, than the two previous particle system. 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 particles 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.

Chapter 3

Sandstorm the Idea

In this section you will find a brief descripition of what Sandstorm hopes to accomplish, along with issue with developing such an endeavor. Sandstorm is a Dynamic Multi-contextual GPU-based Particle System that uses vector fields for particle propagation. Sandstorm is designed to use gather scientific data, vector fields, and use it to ’guide’ the motion of the particles according to this observed data. Also Sandstorm is designed to run in a 3D Virtual Reality environment with the presence of other applications and simulations. Therefore the performance of Sandstorm was an issue, thus a GPU-based approach was used to tire and free the CPU for use elsewhere.

First off, lets take a look at what is meant by Sandstorm by Dynamic. Sandstorm is design to have the ability to change certain of its attributes on the fly. Some of this attributes include, the rate at which particles are emitted, the size of the particles, the area of which the particles are emitted out of, the vector field that propagates the particles, and the lifetime of the particles. This ability was added to aid in the real-time scalability of Sandstorm, as less and less resources become available to the system, Sandstorm can be scaled back to allow more resources for more important tasks. This ability also brings with it an inherited level of detail, allowing Sandstorm to decrease the number of particles being emitted when the viewer is far away from the particle system.

Next, lets take a look at why Sandstorm is a Multi-contextual particle system. As previously stated in Chapter 2, the typical architecture for a 3D Virtual Reality application/simulation is that there is a main context that handles such task as input gathering and updating simulations, and multiple rendering contexts that handle the rendering of a scene. Considering that there are several rendering contexts, the generation of such information such as random numbers, for use in rendering algorithms, needs to be context safe. Therefore a split first, described in Chapter 2, approach was adopted for use in Sandstorm. What is meant by this is that each context is given a copy of the entire simulation to run on it, but not every thing was given to all contexts. The main context still handles context safe calculations such as random numbers and passes them out the all the rendering contexts. This split first approach was adopted to try and take advantage of the massively parallel streaming model that are today’s GPUs.

Sandstorm is designed to leverage the use of todays powerful and advanced GPUs. To take full advantage of todays GPUs, Sandstorm is designed to use Shader Model 4, in particular Geometry Shaders and Transform Feedback. By uses this two aspects of Shader Model 4, Sandstorm is capable of isolating all of the particle simulation and render step to the GPU. In fact only two aspects of the particle system remain on the CPU, the passing of per frame data(such as delta time) and the updating of the vector fields. The Updating of the vector fields was left on the CPU, because the vector fields are implemented in 3D textures, and to update an entire 3D texture on the GPU would put to much work on the GPU.

Finally, Sandstorm is designed to use vector fields, filled with gather and observed scientific data, to propagate the particles. This was done so that Sandstorm can mimic such scientific phenomenon has the dust cloud that is kicked up by a helicopter’s downdraft.

The actual implementation for all of these attributes of Sandstorm, we be described in the sections to follow.

Chapter 4

Sandstorm Software Specification and Design

Chapter 2 presented the background and problems with creating such a particle system as Sandstorm. Also chapter 3 presented what Sandstorm is trying to accomplish. This chapter presents a formal description of the goals, requirements and use cases, of Sandstorm. The goals will describe four major attributes that the Sandstorm prototype shall have. The requirements are presented in two categories functional and non-functional requirements, and describe the basics features of the Sandstorm prototype. The use cases describe the use and basic functionality of the Sandstorm. Later in the chapter, you’ll find a more detailed discussion of the overall system and subsystems of Sandstorm. The software engineering practices and principles used to develop Sandstorm can be found in [cite] and [cite]. Providing the reader with an understanding of the structure and methodology behind Sandstorm, is the aim of this chapter.

4.1 Sandstorm Goals

First off, Sandstorm is meant to be a tool for the visualization of atmospheric phenomenon for scientific study, such as dust clouds and smoke. Thus, Sandstorm must allow for the input of observed scientific data to fuel the visualization of these phenomenon. For instance, the use of vector fields to guild the trajectory of the particles in a atmospheric phenomenon visualization, is one example of allowing for the input of observed scientific data. Therefore, Sandstorm uses vector fields to allow for the input of observed scientific data to file the visualization of atmospheric phenomenon.

According to other particle systems[cite million] and [cite uberflow], the higher amount and smaller size of particles add to the realism of a particle system. Traditional CPU-based particle systems are stuck at around a 100,000 particles[lata], limited by the transfer of particle rendering information across the graphics bus. While newer GPU-based particle systems [cite million], [cite uberflow], [cite particleGS], allow for a much higher amount of particles to be displayed, around 500,000. Therefore, Sandstorm uses a GPU-based approach to allow for a high amount of smaller sized particles, to add to a higher degree of realism.

Allowing the user to immerse themselves into the scientific phenomenon that they are studying, may allow for a better understanding of the phenomenon. Using a 3D Virtual Reality environment, will allow a user to immerse themselves into a particular application. Therefore, Sandstorm will utilize a 3D Virtual Reality environment to allow for the immersion of the user in a scientific phenomenon.

Like previously stated, Sandstorm is meant to be a tool for the visualization of atmospheric phenomenon for scientific study, such as dust clouds and smoke. Thus, Sandstorm must have the ability to allow the application programmer to customize the particle system. Such customization could include, whether or not to display the particles as points or textured billboards, the size of particles, and maximum life time of the particles. Therefore, Sandstorm allows for a horde of attributes to be changed both programmatically and during run-time, for a complete list see table [table in 5.4].

4.2 System Requirements

Like all software systems, Sandstorm has minimum system requirements that must be met in order for the system to perform properly. This section will describe the minimum system requirements of Sandstorm and describe some of the system specs of the system that Sandstorm was tested and developed on.

The first requirement is the most apparent, and that is the Virtual Reality environment. Sandstorm was developed for the express use in an active stereo cave system, the cave system that Sandstorm was tested on was the one at Desert Research Institute. This cave system was an active stereo, four-walled flexed cave system, the cave was designed by FakeSpace[cite?]. The system utilizes a multi-cored machine and an Nvidia quadroplex to power it[cite?].

Like perviously stated throughout this paper, Sandstorm utilizes a GPU-based approach. However, this GPU-based approach is not your run-of-the-mill approach, it utilizes Shader Model 4, more specifically geometry shaders and transform feedback. The system that Sandstorm was developed on and for uses a Nvidia quadroplex with a G80 chipset in it, thus an system that is going to run Sandstorm will also have to have a G80 chipset.

**Up to Harris: Insert paragraph describe giotto?

section under construction.

4.3 Requirements

Before the use cases and class diagrams can be presented, the requirements of Sandstorm must first be outlined (Table 4.1). These requirements were distilled through domain knowledge and the requirements of the Helicopter and Dust Simulation application described in Chapter 2.

Next the non-functional requirements (Table 4.2) show what technologies are used in Sandstorm and software features. These non-functional requirement largely control the software engineering of Sandstorm and its subsystems.

4.4 Use Cases

The use case (Figure 4.1), denotes the functionality provided to the end user. These use cases are developing using the functional requirements presented above. There are two actors that directly influence the Sandstorm particle system. The user manip-

F01 Sandstorm shall display a visual representation of phenomenon

such as; dust clouds, i.e. particle system.

F02 Sandstorm shall use vector fields to guide particles.
F03 Sandstorm shall utilize GPU-offloading.
F04 Sandstorm shall be written to work in a 3D Virtual Reality

environment.

F05 Sandstorm shall allow users to change the maximum lifetime of

the particles.

F06 Sandstorm shall allow users to change the size of the particles.
F07 Sandstorm shall allow users to change the area in which the

paritcles are emitted.

F08 Sandstorm shall allow users to change the rate at which particles

are emitted.

F09 Sandstorm shall allow users to change the maximun number of

particles that are allowed to be emitted.

F09 Sandstorm shall allow users to start/stop and pause the

particle simulation.

F10 Sandstorm shall allow users to change the attributes both

programmaticlly and during run time.

F11 Sandstorm shall allow for a large number of particles to be

display, above 100,000.

Table 4.1: Functional requirements for the Sandstorm prototype application.

ulates Sandstorm, by changing the dynamic attributes of the systems. Time is also a major actor on Sandstorm, it controls the update of the simulation, and animates the particles.

4.5 Modeling and Design

This section describes the structure and design of the Sandstorm particle system. This includes a Main Class Hierarchy diagram, which includes a describe of the classes, and a description of the Utility Classes that were used. section under construction.

4.5.1 Main Class Hierarchy

In Figure 4.2, you can find the main class heirarchy of the Sandstorm particle system. This is not an inheritance hierarchy, rather a flow of control between the classes. Also

27

Figure 4.1: Use cases for the Sandstorm prototype.

N01 Sandstorm’s CPU based portion shall be written in C++.
N02 Sandstorm’s GPU based portion shall be written in GLSL.
N03 Sandstorm shall be implemented in a modular fashion allowing for the

replacement of components when more efficient methods are discovered.

N04 Sandstorm shall maintain independence from windowing/VR toolkit.
N05 Sandstorm shall use the VRUI library for prototype application.
N06 Sandstorm shall maintain interactive levels of temporal fidelity,

above 15 FPS.

N07 Sandstorm shall use Geometry Shaders for the creation and updating

of particles.

N08 Sandstorm shall use Geometry Shaders for the rendering of particles.
N09 Sandstorm shall use Transform Feedback to transmit the particle

data to the update/creation shader(s) to the render shader(s).

Table 4.2: Non-functional requirements for the Sandstorm prototype application.

there are other classes that were used in the creation of Sandstorm and they will be covered in the following section. Multicontextual ParticleSystem

This class is the main control mechanism for the entire particle systems, from controlling the flow of the simulation to the flow of data. This class contains a list of ParticleSystem classes, each ParticleSystem classes is responsible for a context. The list containing ParticleSystem is updated with data such as time between frames and changes in dynamic attributes.

In a multicontextual environment the generation of random numbers needs to be done on a single context, to ensure that all contexts get the same random numbers. During initialization, the Multicontextual Particle is responsible for generating any random numbers that are needed for the per context simulations. ParticleSystem

Each context contains a ParticleSystem class, which is responsible for the creation and coordination the Shader objects. During creation, the ParticleSystem class creates and initializes the shader objects with data that they need, such as pointers to render buffers and particle information buffers. First the ParticleSystem class creates and initializes the ParticleGeoUpdate shader, which is responsible for the particle

29

Figure 4.2: The main system structure of the Sandstorm system. information buffers. Once the ParticleGeoUpdate shader object is initialized, the ParticleSystem initializes the ParticleRender shader object, with a pointer to the particle position buffer, initialized by the ParticleGeoUpdate. Finally, when the ParticleRender shader object is initialized the ParticlePost shader object is initialized with the output buffer of the ParticleRender shader object.

During the simulation the ParticleSystem class will, when called, call the ParticleGeoUpdate class to update the particle information. Once the particles have been updated, the ParticleSystem class, when called, will first call the ParticleRender shader to render the particles into an off screen buffer. After the ParticleRender shader object is called, the ParticlePost shader object is called to render the result of the deferred shading. Also while the simulation is running the ParticleSystem class directs the flow of the data to the correct shader objects, such as change in the size of the particles or the maximum life time of the particles. ParticleGeoUpdate

In every context there is a ParticleGeoUpdate class, which is responible for updating and creation of the particles. During initialization the ParticleGeoUpdate class creates and initializes all of the paritcle information buffers, such as the particle positions and particle velocity buffers. The ParticleGeoUpdate class will create two sets of these buffers, so that the data is double buffered.

During the simulation the ParticleGeoUpdate updates the particle informations, which includes the particle positions, velocities, and time lived. This is done by storing the particle information into vertex-buffer objects(VBOs), and feeding those VBOs into a shader that will update and create the particles. Once the shader has updated and created the particles, the ParticleGeoUpdate class gets the result, using Transform Feedback, and swaps the two set of buffers. ParticleRender

Once the ParticleGeoUpdate class is done updating and creating the particles, the ParticleSystem class calls the ParticleRender class. The ParticleRender class is responsible for the rendering of the particles into a off screen buffer for use in the ParticlePost class. During initialization the ParticleRender class receives from the ParticleSystem class, a pointer to the two particle positions buffers. Also, the ParticleRender class receives from the ParticleSystem class, a pointer to the off screen buffer that it is to render to.

During the simulation the ParticleRender class uses the particle position buffer pointer to feed the render shader the particle position information. But before the ParticleRender tells the render shader to render the particles, it redirects the output of the render shader, into the off screen buffer. Once the render shader has rendered the particles, the ParticleRender class swaps the pointer of the particle position buffer, so that it matches the correct one that the ParticleGeoUpdate will use next round. ParticlePost

Once the ParticleRender class is done rendering the particles into a off screen buffer, the ParticleSystem class calls the ParticlePost class. The ParticlePost class is responable for the deferred shading affect described in chapter 5. During initialization the ParticlePost class receive form the ParticleSystem class, a pointer to a off screen buffer, which holds the results of the ParticleRender class. During the simulation the ParticlePost class uses the off screen buffer to feed the deferred shading shader. Shader

The Shader class is a small utility class that handles the creation, compilation, and linking of all shader code. Each of the three shader object classes (Particle-GeoUpdate, ParticlRender, and ParticlePost), inherit from this class. During the initialization of this class, the shader source code is located and load, if the shader source code cannot be located or loaded an error is returned. Once the shader source code is load, it is then complied and linked, if any errors occurred in the compiling or linking of the code those errors are printed. Once the shader source has been compiled and linked succesnheritsfully, an identification number is stored into the Shader class. It is up the class that inherits from the Shader class, to implementation the two virtual functions that are present in this class. The first virtual function that needs to be implemented is the initialize uniforms function, this functions finds and stores the location of any input variable to the shader. The second virtual function that needs to be implemented is the draw function, which is responsible for setup up the proper openGL state and activating the shader. Each of the Shader object classes (ParticleGeoUpdate, ParticleRender, and ParticlePost), all implement these two functions, and store the location of the shader input variables.

4.5.2 Utility Classes

The class/objects/functions listed in the previous section where not the only ones used in this project, below is a breif description of some of the other piece of Sandstorm. First the GFX Utility Library, created by Roger Hoang[cite], is a small multicontextual graphics library. And second, Vector Field File Loader, is a small object orientation system that loads vector data from a file for use in Sandstorm. GFX Utility Library

GFX Utility Library, created by Roger Hoang[cite], is a small multi-contextual graphics library, that handles such things as multi-contextual textures and framebuffers, and openGL state saving and restoring code.

The GFX texture and framebuffer classes are multi-contextual texture and framebufer classes that is used in Sandstorm for ensuring that any texture/framebuffer data is multi-context safe. This is done by taking the same approach that Sandstorm does to multi-contextualism, and that is to create a copy of the data for each context. The multi-contextual class each contain a list that hold these context copy’s. When a new context is added a object(texture/framebuffer) is create and initialized with the proper data, then it is added to the context list of the class.

Other functions of the GFX Library that are used in Sandstorm are the popAll and pushAll functions, which are nothing more than wrappers for openGL state saving and restoring code. Vector Feild File Loader

The Vector Field File Loader(VFFL), is a simple class that handles the loading of vector field data and translates the data into a form that can be used by Sandstorm.

First off, the VFFL loads the file data into a 3 dimensional array, for simplicity of loading different file formats. Sandstorm uses 3D-textures to transmit the vector field data to the GPU, so in order to use the vector field data along with any texture the data needs to be in a single dimensional array. Once, the data is loading from the file into the 3 dimensional array, the VFFL translates that data into a single dimensional array, so that it can be used in the vector field texture.

Chapter 5

Sandstorm Prototype

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

5.1 GPU-Based

This paper 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 man phases.

5.1.1 Creating and Destroying Particles

The most important part of a particle systems 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 as reached its maximum. Considering that the creation and destruction of particles is handle on the GPU, the problem has to be revisited. According to Reeves[cite], and others[cite], 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 a particles and store them into a dynamically growing data structure, such as a linked list or an array. But, with GPUbased particle systems particles can’t be stored in such data structures, as is the case with Uber Flow and Latta’s Million Particle System. In both cases textures where 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(Vertex Buffer Objects) can be used to relay information to the GPU more efficient. Like previously stated, a VBO stores data on the high-performance graphics memory of the GPU[cite]. Also VBOs can be resized to fit the exact amount of data that is used, where as 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 actually need. 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 store. Since we never know just how many processors are read and/or writing to a particular location in the VBO, a double buffered approach needs to be adopated. Like Latta’s Million Particle System, 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 and Uber Flow, each of the buffers hold two VBOs. One VBO holds the particle’s position in 3D space, which are store in the first 3 members of the vertex, and in the fourth member of the vertex is 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 else where.

Most modren 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 responable 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 store in the same buffer as the particles. In the case of an emitter, in the members of position vertex buffer hold 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 a emitter. Therefore the fourth member of the particle’s velocity vertex buffer is set to zero to denote that is a particle.

Now that we know how the particle information is store on the card, its time to take a look at how the particles are created. In Shader Model 4, 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 logic 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 receive is a particle or an emitter, by looking at the 4 value of the velocity vertex. Once the shader has determined if it is dealing with a emitter, it begins to emit particles. First thing to determine is how many particles are to be emitted, that is done by determining how many particles have already emitted and subtracting that from the number of particle per second. Once that is the difference is found, its divided by the amount left in that cycle, each cycle is a second. This method won’t always give the exact amount of particle per second that prescribe by the rate, but it gives the system another measure diversity, making the system seem more realistically.

At this point we need to discuss a limitation of current shaders. When a shader is compiled all loops are unrolled, no matter if they can or can not be unrolled. This has the ability of optimizing the shader code, but can however cause a headache when creating a loop of indeterminate compile-time size. Considering that the compiler cannot unroll a loop of indeterminate size these loops cannot be used. This was a problem, because an emitter has to be able to emit more than one particle at a time. In order to get around this, the shader had to be tricked, a while loop with an internal condition was used, see figure blah.

**Insert figure that has the psuedo-code for the loop**.

Once the number of particles to be emitted has been determined, the particles are created but not yet created. Inside the aformentioned while loop, each particle is seeded with initial information, that conforms 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 support, therefore a perturbation texture was used. This will describe 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 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 following section.

5.1.2 Updating Particles

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

First thing that is done is to do 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.

5.1.3 Rendering Particles

Finally, the last thing to do in the particle system, is to render the particles. Like 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 could of dust. However, some particle systems, mostly scientific visualization system, 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 the 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 that is centered at the particles position and points to the eye can be calculated. This normal can be found by the following equation:

normal = gl_{M}odelV iewMatrixInverse ∗ Up_{v}ector

where gl_{M}odelV iewMatrixInverse, is the built-in variable that describes the Inverse of the Model View Matrix, and Up_{v}ector 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 a off screen buffer, so that the can be run a deferred shading shader.

**Insert describition about deferred shading.**

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 the 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 lead to smaller code size, than making a seperate branch for point rendering. Therefore the same render shader is used, expect that the texturing and the blending of the billboards replace with a simple coloring method.

5.2 Vector Fields

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 where used instead of VBOs, because of the existing internal methods for dealing with 3D textures, such as wraping 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 and other particle systems. A copy of the vector fields, 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.

5.3 Multi-contextual

Like 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: - The use of Vector Fields to guide particles allows for the predictability of the behavior of particles once created. - The use of a perturbation texture for creation of particles, allows one perturbation texture to be created and passed to all simulations at initialization. - And 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. Considering these three reasons, Sandstorm can safely use a split first method for the distribution of the simulation across multiple contexts.

The above figure shows how Sandstorm is designed to utilize the split first method. At the top of the architecture sets 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 contains a particle system and the same set of data, data that is given to the simulation object by the main object. The data is 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.

5.4 Dynamic

In order to allow for a more diverse and realistic behaving particle system, certain attributes are giving the ability to be changed by the user of Sandstorm. The split first method that Sandstorm’s architecture is model 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 5.1 .

size  This attribute determines the size of the particles when they are renderd.
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.

Table 5.1: Table of dynamic attributes.

Chapter 6

Results

In order to test the Sandstorm particle system, a sample application was created. The sample application was created using the Dust Framework for the creation of a scene too work with. The terrain that was used in the scene was of an area of desert outside of Yuma, Arizona. The object that was used in the scene was a Blackhawk Helicopter, that was not accurate to real world specifications. A simple control scheme for the helicopter was used, where the wand could be tilted toward the user to increase the throttle and away from the user to decrease the throttle of the helicopter.

A Basic vector field was used in this sample application, see figure 6.1 for more details. Considering that Sandstorm is not a vector field interaction model, where vector fields are calculated according to scientific models, a single vector field was used. In order to create a dynamic test of the Sandstorm particle system, a simple helicopter-vector field interaction model was created. This interaction model was nothing more than as the throttle of the helicopter was increased, the amount, life time, and rate of the particles increased. On the other side, as the throttle of the helicopter was decreased the amount, life time, and rate of the particles was decreased. Also as the distance of the helicopter and the ground increase passed a predetermined point the amount, life time, and rate of the particles, was also decreased.

This test was designed to test several aspects of Sandstorm, the dynamic attributes, the ability of the particles to follow a vector field, and the ability to be run in a multi-contextual environment.

***Insert results of the test, along with pictures***.

43

*** Section under construction. ***

Chapter 7

Conclusions and Future Work

We have seen that Sandstorm has meat all of its design goals list in chapter 4. Sandstorm is a particle system that has the ability to create a visual representation of phenomenon such as dust clouds. Sandstorm has the ability change attributes such as emission area, rate, life time, and maximum number of particles. Sandstorm utilizes GPU-offloading to updated and render particles. Vector Fields where used in Sandstorm to ’guide’ the motion of particles. **Sandstorm has the ability to run in a multi-contextual environment and can update and render above 100,000 particles in such an environment.**

Considering that Sandstorm is currently just a prototype there are many things that can be done to increase the quality of the system.

First thing to address is that the current Sandstorm has areas that can use a bit of optimization. Currently both emitters and particles reside in the same buffer objects, this causes the shaders that use these buffers to contain branching. Branching in a shader can be computationally expensive, therefore it might be better to split emitters and particles up into different buffers. Another thing about the current Sandstorm, is that the size of the buffers are currently of static size, and do not dynamically increase or decrease in size. Instead of using a soft maximum amount of particles create a pseudo-dynamic size, it might be beneficial to create a dynamic sized buffer. These dynamic sized buffers will deffentaly increase speed when the amount of particle is small, but they might not help at all as the size of the buffers reach large numbers.

Other features that can be added to Sandstorm to increase the quality of the system are as follows. Collisions between particles and static objects can implemented, such static object would be the terrain in the sample application, a method can be found in[cite]. Collisions between dynamic objects, such as the helicopter, could be added to Sandstorm. Soft particles could be added to Sandstorm to allow for more realistic looking particles[cite]. Motion Blur is another effect that could be added to make the particles look more verisimilar[cite]. And finally, a shader based physics model could be implemented to allow users of the system to change the behavior of the particles without having to recompile.

***section under construction.****