Transcript Introduction to Procedural Methods, Particles

Introduction to
Procedural Methods, Particles
Glenn G. Chappell
[email protected]
U. of Alaska Fairbanks
CS 481/681 Lecture Notes
Monday, March 22, 2004
Where Are We? [1/2]

So far, we have covered:

Organizing a 3-D Scene
• Drawable objects
• Tree representations

Advanced HSR
• Image-space methods
• Object-space methods

Buffer-Based Effects
• Accumulation, including jittering
• Stenciling

Virtual Reality
• Representing transformations
• VR Juggler programming
• User-interface issues

Describing Objects
•
•
•
•
Explicit vs. implicit
Splines
Implicit representations & marching cubes
Rapid prototyping & file formats
22 Mar 2004
CS 481/681
2
Where Are We? [2/2]

Next:

Procedural Methods
• Modeling particles
• Particle systems
• Fractals

Non-Pipeline-Based Rendering
• Ray tracing, etc.


As well as whatever VR-related topics can be made to work …
Also, the take-home midterm exam is due on Wednesday
(3/24) at the start of class.



Do not turn it in via e-mail. Give me stapled sheets of paper.
The midterm is available on the web page.
Complete instructions are on the exam.
22 Mar 2004
CS 481/681
3
Procedural Methods:
Introduction [1/2]



We have considered various ways to represent a
scene and objects within a scene.
Sometimes objects are complex enough (in
appearance or behavior) that we think primarily
about the algorithm that generates the object,
rather than any static representation.
Such algorithms are generally known as
procedural methods.

Perlin’s noise-based texture generation technique (from
CS 381, fall 2003) is a good example of a procedural
method.
22 Mar 2004
CS 481/681
4
Procedural Methods:
Introduction [2/2]

We will consider two main categories of procedural methods:

Particle systems
• Independently moving particles, obeying some set of laws.
• Used for:
•
•
•
•
•
•
•
•

Smoke.
Sparks (from welding or whatever).
Explosions (not too different from sparks).
Semi-rigid solids (particles connected by stiff springs).
Cloth (particles connected by things that act like fibers).
Crowd scenes (each particle is a person).
Flocks of birds & schools of fish.
Etc.
Fractals
• Definitions later …
• Used for:
•
•
•
•
22 Mar 2004
Clouds.
Terrain.
Tree bark.
Pretty pictures. 
CS 481/681
5
Particles:
Definition

A particle is an object that has a time-dependent
position.



In CG, particles are used in many types of
modeling.



That’s essentially all it has.
So it can be somewhere, and it can move.
Particles may interact with each other in complex ways.
We can render a particle however we want.
Particles are most interesting when they form
groups in which each particle moves (somewhat)
independently.

This is called a particle system.
22 Mar 2004
CS 481/681
6
Particles:
Position & Motion [1/2]


We look at how to model a single particle.
Suppose our particle obeys Newton’s Laws of Motion.




Newton’s First Law says that a particle’s velocity stays
constant unless it is subjected to an external force.
So the state of a very simple particle can be stored as a
position and a velocity.
In TRANSF, this might be a pos and a vec.
So a simple particle can be represented by a two-element
struct:
struct Particle {
pos position;
vec velocity;
};
22 Mar 2004
CS 481/681
7
Particles:
Position & Motion [2/2]

Code for a particle, with no force acting on it, might look like this:

Global:
Particle p;

In the idle function:
static double previous_time = get_the_time();
double current_time = get_the_time();
double elapsed_time = current_time – previous_time;
p.position += p.velocity * elapsed_time;
glutPostRedisplay();
previous_time = current_time;

In the display function:
render(p);
22 Mar 2004
CS 481/681
8
Particles:
Force

Newton’s Second Law says that when a force acts on a particle,
the resulting acceleration is proportional to the force and
inversely proportional to the mass of the particle:
f
a
m



So when we deal with forces, we might want to store a mass for our
particle as well.
The simplest force is gravity, which, at human scales, can be
considered as giving a constant acceleration in the downward
direction.
How do we find the position of a moving particle whose velocity
is changing?

This question leads to the very deep topic of differential equations
and their solutions. We will not cover this in detail here, but we can
say a little bit …
22 Mar 2004
CS 481/681
9
Particles:
Simple Approximation

Suppose the force on a particle is small.


Then its velocity will not change much between two frames.
And we can approximate its changing velocity by its current velocity.
vec force = compute_force(p.position);
p.position += p.velocity * elapsed_time;
p.velocity += force / p.mass * elapsed_time;


This is based on a simple method for solving differential
equations, called Euler’s Method.
This method has two problems:

Accuracy
• The velocity is not constant, after all.

Stability
• Small initial errors in position can quickly turn into large errors.
22 Mar 2004
CS 481/681
10
Particles:
Better Approximation

We can do better if, instead of using the current velocity of the particle to
update its position, we use the average of its current velocity and its
next velocity.


Except we do not necessarily know what the latter is. 
So, we approximate it, the same way we have been:
vec force = compute_force(p.position);
vec next_velocity = p.velocity + force / p.mass * elapsed_time;
p.position += (p.velocity + next_velocity) / 2. * elapsed_time;
p.velocity = next_velocity;

This is based on a method for solving differential equations, called the
Order 2 Runge-Kutta Method.


It has both better accuracy and stability.
When the acceleration is constant (e.g., gravity), it is exactly right.
• I mean mathematically, of course. Floating-point computations are always wrong.

When the acceleration is not constant, we should do better than the above
code.
22 Mar 2004
CS 481/681
11
Particles:
Other Forces

Other common forces:

Planetary-Scale Gravity
• Attractive force between two particles.
• Proportional to the product of their masses.
• Inversely proportional to the distance between them.

Drag/Friction/Air Resistance
• Force is opposite to the direction of motion.
• Speed and mass may have effects.

Spring Forces
•
•
•
•

Pulls an object toward the at-rest point of the spring.
Force is proportional to the distance of the object from this point.
Usually combined with drag to give a realistic simulation.
Can be used in a “grid” to simulate a semi-rigid object.
Buoyancy
• In air (for smoke!) or water.

Elastic (or Inelastic) Collisions
22 Mar 2004
CS 481/681
12