INTRODUCTION

Since the late 1970’s, a number of film and animation productions have achieved a new level of realism by using physically based modeling and simulation for secondary motions and special effects.  Examples include explosions in The Wrath of Khan and the movement of water and generation of smoke in Titanic.  The subtle effect of the motion of the waves in Titanic would be difficult to generate using traditional keyframed animation.  Despite the realism simulation can lend to a scene, animators are often hesitant to use simulation methods for more complex scenarios due to the painstakingly long rendering time of each frame.  A single sequence may take hours to generate, making it virtually impossible to tweak a scene to an animator’s idea of perfection.

This lengthy rendering time also prevents the use of simulation in real-time scenarios, such as in virtual environments.  The subtle effects of secondary motions, whether it be movement of clothing, smoke streams, or the gentle shaking of leaves as the wind blows through the trees, can bring an animated scene or virtual environment to life.

A great deal of work has been performed in improving rendering times of large scale models through the generation of levels of detail.  We look to extend this concept to the field of physically based simulation.
 

PROBLEM DEFINITION – GOALS

The main goals of this project were to

1. create a framework for switching between levels of detail in physically-based simulations
2. automatically construct, and smoothly blend between the different LOD’s
 

ACCOMPLISHMENTS

• Several major changes were made to the project plan as the semester progressed.  Namely, I abandoned the idea of using a strict particle system to model the tree.  Particle systems are useful for rendering trees at large distances, however I wished to zoom in and out on a tree blowing in the wind.  Zooming in would require that the leaves be attached to the branches.

Therefore, the resulting system is a hybrid of simulation types.  The trunk and branch structure are modelled with a spring mass system, and the leaves are modelled as articulated bodies.
 

• Creating the tree was a feat in itself.  A l-system program from Lauren Lepre was greatly modified to construct a hierarchical data structure instead of simply writing out dxf files.  Maintaining the hierarchy of the model as opposed to just writing out the faces of the model in random order was a difficult problem.  Originally I wrote a DXF Reader but again was unable to recapture the hierarchy inherent in the model; the hierarchy had to be captured at the time of generation.

The following image shows how the hierarchy of the data structure biological tree match.  All nodes on the same levels of the data structure are rendered in the same color.
 
 









The following two are examples of changing a few parameters on our .ls tree definition file:










• An unexpected time consuming task was assigning spring constants to the various branches of the tree.  This took time and effort to achieve realistic results.  Further research may provide better insight for setting these constants.

 
• LOD switch mechanisms - Simulation can be cut off at any level of the tree.  For example, we could just move the main branches, or the first two levels of branches.  The motions generated by these levels is always inherited by the children.  Furthermore, the leaves are considered independently of the levels of hierarchy.  The leaves can easily be toggled on or off.  A future extension would be to determine when we are at a sufficient distance where a particle system can be used in place of the articulated body simulation for the motion of the leaves.

 
• LOD measures:
• L1,L2,Linfinity norms did not provide useful numbers
• Currently using RMS of the motion of the particles.  Each level is computed independently, such that we can identify which levels are the main contributors to the motion of the scene.  Each time a particle is moved, the square of the change in distance is added to the tally for its level.  Then after 15 frames, the square root of the mean of the squares is taken to give an indication of the amount of motion being generated at each level.  The choice of 15 frames is approximately every second.  This could be a user-controlled parameter.

The goal of this metric is to compare the average distance traveled by a particle to the user's distance for the scene.  If the user distance is great enough, the motion will be indistinguishable and can be eliminated.
 

• How the LODs work...

From the main level, ps->updateTree() is called.  This function calls both the LOD object methods and asks the tree to recursively update through a helper function.  The LOD object gathers data until a limit of frames is generated.  Currently this is set to 15, but this will eventually be a user-defined option (too much LOD checking might generate too much overhead).
 
int ParticleSystem::updateTree(int eulers)
{
     static double motion[8];

     if (frameNum % 15 == 0)
     {
          for (int i=1; i<=tree_depth; i++)
          {
               //find rms error for each level
               motion[i] = lod.RMSmotion[i]/lod.numParticles[i];
               motion[i] = sqrt(motion[i]);
          }

          //reset every 15 frames
          for (i=0; i<25; i++)
            lod.RMSmotion[i] = 0;
     }

     //reset every time
     for (int j=0; j< 25; j++)
          lod.numParticles[j] = 0;
     frameNum++;

     //LOD switch check would be here
     lod.check(motion,userDistance);

     //leaf toggle and depth parameter would be set
     //according to results of lod.check
     int leaves = 0;
     int depth = treeDepth;
     totaltime +=timeStep;
     updateRoot(particles[0], depth, eulers, leaves);
     return 1;
}

STILL ON THE TO-DO LIST

• Due to the unexpected difficulty encountered in pulling the entire simulation together, I was unable to actually implement the LOD switching.  The mechanism is there; it is just not complete.  Part of the problem is with the current projection matrix.  I honestly need help getting the zoom right for a perspective projection and with course projects looming, I was unable to find assistance.

 
• MORE ideas for the LOD switch function need to be checked.  Currently, by analyzing the amount of motion on each level, we do have some idea of the simulation fidelity lost by simplification.  But a lot of time needs to be spent evaluating all possible heuristics, and obtaining statistical data for analysis.

 
• Pruning of motion calculations for objects outside the region of interest needs to be implemented.  This idea will be SIGNIFICANTLY easier when the switch to using spatial partitioning algorithms is made.

 
• The idea of spatial partitioning had to be abandoned; another student encountered difficulties in this work as well leaving insufficient time for implementation.  The current project looks mainly at articulated bodies; using spatial partitioning would allow analysis of a completely different category of simulation.

 
• Bug fix (texture mapping):  I worked with Gentaro for more than six hours at one point trying to debug texture mapping to no avail.  While moving to the SGI at some point is inevitable, I prefer to keep it on my laptop so I can work from home when sick, which we all know happens too darn often lately.

 
• Spring constants - I would like to see more motion of the upper branches and need to research how to set the constants appropriately.

 
• File Parsing - currently the user must enter the "branching" factors for the tree to be generated.  Ideally this would be automatic.

 

The following files are quicktime movie files to show an example of what the system can currently do.

Movie One
Movie Two
Movie Three