By: Shyam Guthikonda and Jason Bixler



Project Goals

Our goal with this project is to effectively implement a particle engine in a 3 dimensional environment. By a particle engine, we mean a system which will effectively implement realistic weather-type effects through the use of small, continuously moving particles throughout our scene. A system like this takes a lot of "background" programming in order to both manage and manipulate the several different systems we plan to create. More importantly, memory management is a very real issue here as we will be creating hundreds, if not thousands, of particles accross all of the different systems should they all be turned on at the same time. Thus we will start with a basic 3 dimensional environment with the user having camera control of moving fowards, backwards, left, right, rotate left, and rotate right. Once we have this basic "arena" set up, we will texture the environment to make it a more realistic-looking area with a grassland base and appropriately stitched skybox for the atmosphere.

As for the details regarding the actual particle engine, we will start with a top down design, having a particle manager at the top of the hierarchy to create, destroy, and manipulate all of the different systems we will be implementing. This particle manager will have methods for adding and removing systems from the scene as well. In addition, we will be creating a base class with virtual initialization and update functions to be overridden in the classes we define for each specific type of system.

On the smaller scale of particle management, our particle system objects will hold a livelist and deadlist for managing our particles. Whenever a particle moves out of the range of the scene, or where we want the system's particles to exist in the scene, they will be moved to the deadlist to be re-initialized and used again, versus destroying and re-creating each particle to simulate continual motion, which would be rather memory intensive and slow. Our actual particle object, to be created and re-initialized within each system, will be rather small in the amount of data it will hold, but items such as it's texture, current location, lifetime of the particle, and x,y,and z velocities to control its motion will be among them.

As for the differing aspects of each individual system, there aren't many variations other than the "origin" from which each system's particles will emanate from and the boundaries of each system.

Planned Effects

  • Rain
  • Snow
  • Fire
  • Smoke
  • Water (Fountain)
  • Other

Who Did What

  • We each discussed several of the algorithms used in this project, other than the ones Shyam implemented from his past OpenGL Labs.
  • Shyam did most of the coding since we ran into problems regarding .dll files and getting the code to run on my system or lab computers and figure we'd be more efficient if we didn't waste time on that aspect.
  • Jason located the algorithm that we used for the fire and coded a good portion of it during one of our meetings
  • Jason started the website and did a good portion of it, having the images and algorithms done by Shyam

'Utilized' Reference List

Texture 'Masks'

The following images are the final textures (billboards) decided upon to use for the snow and smoke, respectively. The black background becomes totally transparent. Completely white areas are totally opaque. Gray areas are linearly blended accordingly.
      

Project Progress

=> Sunday, April 3, 2005

Before we met for the first time, Shyam implemented his past camera movement from prior labs into a 3-D environment we could use for the project.



=> Tuesday, April 5, 2005

At our first meeting, we referenced one of the websites Shyam had found prior to turning in our proposal (http://www.mysticgd.com/misc/AdvancedParticleSystems.pdf) to help us in our discussion of the data structures we needed for the project. This resource was a generalized discussion of the different data structures needed for a particle system. From this document we discovered the need for a particle manager to keep track of all the particles we created for each respective system. We also discussed the different attributes that each particle should have in it's own data structure. Memory management was also brought up in our discussion. We wanted to make sure not to have memory leaks and make the system crawl to a halt through the constant creation and deletion of particles in our application, but rather to re-initialize particles once they had left the area in which we wanted to implement our effect. In order to evaluate our effective use of memory management, as this document suggested, we kept track of how many frames per second our application was drawing as a good benchmark to compare the addition of each new system to our scene.

We eventually settled on the notion of a live list and a dead list, both having the implementation of the STL linked list (as opposed to using a vector which would be slow due to the constant inserting/removing of elements). All particles would be initially contained in the live list. As they went out of range of a given region (bounding box) or their maximum allowed lifetime was exceeded, they would be added to the dead list. Then, once per frame, the dead list would be cycled through. All particles contained in it would be assigned new parameters and added to the live list. Now we can re-use memory instead of (de)allocating and reinitializing constantly.

This system also made rendering much more efficient. Instead of looping through MAX_PARTICLE particles and rendering only the live ones, we now only have to loop through every particle in the live list and render those. The dead list and it's particles can be ignored.

We decided to use a inheritance-type system to allow us to better and more easily split up the duties. The manager class would maintain an array of base effects. All effects, then (snow, rain, etc), would be derived directly from this base effect class. The base class would provide us a model to base all our other effects on. We decided, then, at the conclusion of our meeting that Shyam would create the manager and base class structures, and then send me the appropriate files so I could begin to implement the rain effect.

Following this meeting and preceeding our next class, Shyam added in texturing for a grassland upon which the camera would move, and found 6 images to use as a sky box for added realism.



=> Wednesday, April 6, 2005

Shyam also said he had some extra time and was getting anxious about starting the effects so he began to implement the rain effect. The first implementation of this rain effect initialized 1000 rain particles that were just small GL_QUADS textured with a blue texture. These all were created simultaneously and fell at the same rate, and Shyam had not yet implemented the effect of having the particles re-initialized, so they ultimately all stopped falling at the same time as well.



=> Thursday, April 7, 2005

The next problems that needed to be tackled regarding the rain effect was to obviously have the particles "regenerate" by re-initializing them, but more importantly to have the particles face the camera. Creating and transforming 3-D particles would ultimately be desired, but due to the physical constraints of graphics cards and their GPU's, we figured we should stick with 2-D paricles for processing efficiency. Thus, it was clearly obvious in moving around the scene that the particles were flat, so the next goal was to make the particles face the camera at all times.



=> Sunday, April 10, 2005

Shyam effectively got the particles to face the camera, after much agony, and thus look more realistic as they didn't look flat while moving throughout the 3-D scene. He eventually solved this problem by manually subtracting the position of the camera from the position of each particle, and then pre-multiplying the camera rotation each of these newly transformed particle positions. The modelview matrix is set to the identity matrix, so it has no effect on the particles during their rendering routines.

During this time however, I was trying to get started on the project by focusing on the fire effect. Yet, once I had Shyam's files, I couldn't run his executable on my computer or any of the computers in the lab. I then tried to re-compile the program, noticing I didn't have all of the files, mostly relating to GLUI. After much frustration, we both just decided that we would meet together and code together from this point forth to be more productive and avoid this problem overall.



=> Monday, April 11, 2005

In the meantime, Shyam decided to make the rain particles with GL_LINES instead of GL_QUADS and gave them a gray/white color and a slight alpha, effectively making the rain look much more realistic.



Shyam also, fairly easily, implemented snow as it has the same basic effects as rain except with a different velocity and different appearance. Shyam, altered the appearance by taking two different textures (one - the image - a drawing of a snowflake. The other - the mask - a black and white (1 bit) inverted image of the snowflake), and performing some blending operations on them. The basic algorithm (taken from NeHe) is as follows:
  • Enable blending, enable texture mapping, disable depth testing.
  • For each particle:
    • Set the screen to black if the section of the mask that is being copied to the screen is black. Don't change anything covered by the white mask. i.e. glBlendFunc( GL_DST_COLOR, GL_ZERO )
    • Bind your mask texture. Draw the quad.
    • Copy any part of the image texture that is not black to the screen. The only parts of the texture that get drawn to the screen are parts that land on top of the black portion of the mask. Because the mask is black, nothing from the screen will shine through our texture. i.e. glBlendFunc( GL_ONE, GL_ONE )
    • Bind your image texture. Draw the quad to the same exact vertices.
  • Disable blending, disable texture mapping, enable depth testing.
The depth testing disable seems a little odd. This is done because we are effectively drawing 2 quads on top of each other. If depth testing is enabled, only 1 of those quads would actually be drawn, giving us a bunch of black squares.

Below is the finished result: Round snowflakes ! (Textures with a separate alpha channel would have been the ideal choice. However, at the time of implementing this, bmp were our only option).



=> Tuesday, April 12, 2005

Shyam next added a new effect, Spell01, by altering x, y, and z velocities to simulate horizontally spouting particles, possibly useful to later simulate spouting water. This was also the first effect to utilize an origin. All particles are created at a given point. Then, they emanate outwards based on their velocity vectors.

One thing that was discovered while implementing this effect (which would come handy later for the fire effect) was the use of HSL colors: Hue, Saturation, and Light. By using this color scheme instead of RGB, we could use a paint program like Paint Shop Pro, and find a given range of color we wanted. For this spell, we used a range of green. With HSL, we effectively just compute a random number in our given range (for each H, S, L), then add x to this random number, giving us a number from x - rangeMax.

To convert these HSL vector values to RGB, the following algorithm was found and implemented (taken from w3.org). 

    HOW TO RETURN hsl.to.rgb(h, s, l): 
       SELECT: 
	  l<=0.5: PUT l*(s+1) IN m2
	  ELSE: PUT l+s-l*s IN m2
       PUT l*2-m2 IN m1
       PUT hue.to.rgb(m1, m2, h+1/3) IN r
       PUT hue.to.rgb(m1, m2, h    ) IN g
       PUT hue.to.rgb(m1, m2, h-1/3) IN b
       RETURN (r, g, b)

    HOW TO RETURN hue.to.rgb(m1, m2, h): 
       IF h<0: PUT h+1 IN h
       IF h>1: PUT h-1 IN h
       IF h*6<1: RETURN m1+(m2-m1)*h*6
       IF h*2<1: RETURN m2
       IF h*3<2: RETURN m1+(m2-m1)*(2/3-h)*6
       RETURN m1








=> Sunday, April 17, 2005

We met again today to start work on the fire effect since I couldn't very efficiently work on this effect without just doing it on Shyam's version of code on his laptop. Jason came to the meeting having found an algorithm, from gamedev.net, that would get us started on a basic way to simulate fire.

In order to implement this algorithm, we first got rid of the two buffer example used in this algorithm. Also, we had to bypass some of our base-class functionality. Specifically, we did not want to make use of the live-list and dead-list system that we had used in all the other particle systems. This was due to the method in which this algorithm describes the color interpolation. Thus we defined a DIM x DIM matrix of particles so that we could implement the color scheme described. The basic algorithm is as follows:

  • For each particle in the 2-d array:
    • Add together the 4 color vectors of its 4 neighboring entries in the array (right, left, top, bottom), accounting for particles on the 'edge' of the boundary. This could be carried to 3-d as well, and even diagonal neighbors, but we did not choose to do that.
    • Take this color sum, and divide by the number of neighbors we sampled. This gives you an average color. Use this as the color of the particle.
Initially, we got the fire to "rise" except we used the previous velocity calculations from the spouting particle effect (Spell01), so the fire was moving parallel to the ground in a DIM x DIM area. Also, and more importantly, its obvious that the color interpolation wasn't working correctly as most of the particles were black (as shown below). We adjourned at this time, and figured the velocity and fire placement was easily fixable and that the only real problem would be figuring out the color interpolation. We also had to decide how to fix the large gaps in the fire, so that you cannot see through it as shown below.



=> Monday, April 18, 2005

Looking over the code after the previous days meeting, Shyam noticed the small bug that was creating the black particles. During our averaging of neighboring colors, we were not re-initializing the color sum, or the number of neighbors to 0.0 after each average. This was essentially giving us vectors such as: (0.0001, 0.0001, 0.0001), or, very close to black. By re-initializing these two variables after each particle, the problem was solved.

Next, Shyam adjusted the colors (using HSL) the same way as with the Spell01 effect, but using a range of reds this time. He also increased the particle size, tweaked with the number of particles, and changed their velocities. The fire was essentially complete.

The first screenshot below is to show what the fire looks like without using the averaging algorithm. The second screenshot shows the improvement with the algorithm.







Jason puts up the first version of our webpage.

=> Tuesday, April 19, 2005

We had another meeting today after class. We worked on the smoke today, for about a hour. We spent some time looking at various demos with smoke effects, to see how they implemented it. We decided that instead of using thousands of tiny particles, we would have to use textures. We tried to implement the smoke in the same fashion as the snow (using a texture mask). This did not work, however. Smoke, unlike snow, needs to be very transparent. Using the masking technique, we were unable to blend the entire image.

To get around this, it was decided that we needed to use billboarding. We needed our textures to maintain their own alpha information in a separate alpha channel. We turned to tga images. We quickly tried to implement some tga loading code, but without an active internet connection, it was proving best just to hold off on this. We ended the meeting, and said we would think about which format would be best/easiest to incorporate into our already existing project.

Later that day, Shyam sat down and tried to add tga loading routines to the existing texture manager class. This proved to be an extreme b*tch, however, as after 4 hours of work, he had nothing to show except a sore fist (from hitting the nearby wall) and a headache. He was close, however, to solving the problem. Towards the end of the session, Shyam realized why his tga loading code would work on some images and not others: some were compressed (as created by Paint Shop Pro) and some were uncompressed. After noticing this, Shyam had a good idea of what he had to do, and he vowed to complete the task at a later date - since now he needed a break and a Mountain Dew.

***Breaking News*** Shyam has just gone to take a screenshot of the 'broken' smoke in order to post it below, and the smoke is now working perfectly. This must truly be a miracle, possibly the cause of the new pope, Pope Benedict XVI? Shyam is truly in a state of bewilderment and is now going to bed. He will post the screenshot of the current working state of the smoke now, as-is, and tweak with it tomorrow.



=> Wednesday, April 20, 2005

By accident, Shyam figured out a new masking technique, better and much more efficient than the previously described algorithm taken from NeHe. A .bmp image can be used. During the rendering loop for a given particle, a couple OpenGL functions are utilized.
  • Enable blending
  • Call glBlendColor( r, g, b, a ). This specifies a constant rgba value that can be used to tint your final image (although the alpha value is essentially ignored since you can't technically blend a texture like this with a constant color).
  • Call glBlendFuncSeparate( GL_CONSTANT_COLOR, GL_ONE, GL_CONSTANT_ALPHA, GL_ONE ). This will blend your constant color set on the previous line. Also, this will make colors other than ZERO (0x000000 = black), be drawn. So, draw any image on a black background, then render it this way, and the black parts will not be drawn.
  • Bind your image texture.
  • Draw your quad with the appropriate texture coordinates!
Using this technique, we eliminated the need to draw DOUBLE the particles that we want (one for the mask, one for the actual image). This greatly improves our performance rate, as well as increases the quality of our images (and makes it easier to create images as we don't have to worry about drawing a mask to line up perfectly). Below are the finished smoke effects, and the re-vamped snow effect with a much more realistic texture than previously shown.

Also, using this billboarding technique, we were able to SIGNIFICANTLY reduce the number of quads we had to draw. Compared to our fire system, which uses one quad per particle (4900 particles), our smoke system only uses 40 particles.

Lastly, we implemented a color "change" factor for the smoke system. We take a start color for our particles, and an end color. Then, based on the total lifetime that the particle will exist, we calculate a color change value that will linearly bring us from the start color to the end color. Then, each second, we subtract this value from the current color value of the particle. Using this, the smoke particles start out strong and slowly fade away, until they become totally transparent, at which time their life has expired and they are recycled.







=> Monday, May 2, 2005

We had our final meeting today. The presentation was discussed and worked on, and the webpage was finalized by Jason - adding all the rest of the required information.

Shyam added a textured crate for the fire to burn.








Last Updated: 05.2.2005 @ 7:21 pm