http:^^www.tc.cornell.edu^visualization^education^cs718^fall1995^mccune^final^report.html

来自「This data set contains WWW-pages collect」· HTML 代码 · 共 371 行 · 第 1/2 页

particles' states will not have any specific particle with which to interact.
Therefore, some means of communicating the change of state is necessary. 
For example, consider a water particle moving into a bin full of fire-particles.With all the surrounding fire particles, the water particle(s) should
transform to steam.  But the fire particles should have their temperatures
altered as well, or should have some proportion of fire particles die to
account for the energy exchanged.<P>

The bins therefore must be utilized to pass messages to particles that should
die or undergo a loss in energy.  One set of particles is choosen to perform
the transition and issue the appropriate message, the other is choosen to 
listen for the message and take the appropriate action.  In the fire and
water example, the water is the one which performs the tansition to steam
and passes the message, while the fire particles are the system that reacts
to the passed messages. <P>

One possible means of message passing and the one utilized in this research
is to use the number of particles per bin as the means of message passing.
Temperature of given particles and motion vectors can be calculated based
on these figures.  To differentiate water from fire, water is given a 
negative count.  Where it is obvious that two types of particles are 
present in a certain bin, it is assumed that fire extinguishes water with
a certain ratio of fire particles to water particles.  If the water particles
transform, they decrement the number of particle bins by the number of
fire particles extinguished.  Before the fire-particles move again they
note the change and that percentage of particles will on average die. <P>

For example, take particle X.  It moves into a bin and after all other
<I>fire</I> particles have moved it notes that there are 15 particles
including itself in the bin.  During the <I>water</I> movement portion of the frame,
3 water particles move into the same bin and are considered to exchange heat
and vaporize with the fire particles.  Say that it takes two fire particles
to vaporize one water particle, then 6 fire particles are extinguished, while
3 new steam particles are created.  The final bin count is 9-- steam is counted
as a neutral particle.  The final position of all particles in the frame
is output and processing for the next frame begins.  Each fire-particle is
searched for those particles that should have died.  When particle X is
reached (or any of the fire particles in the bin) it notes that there are
now 9 particles in the bin when their used to be 15.  Thus, 6 out of the 15
particles must have died.  The particle picks a random number between 0 and 1
and if it's number is less than 6/15ths, it's number is up and 
the particle "dies."
<P>
It can happen the opposite way as well, that a fire-particle moves into a bin
populated by water particles and should extinguish itself as well.  The water
particles also need to know their state after all water particles have moved,
so that they will also be killed off in the appropriate situtation.
<P>
A byproduct of the fact that probabilities are used to kill of particles, is
that the bin counts are accurate only on the average.  As time passes however,
local error and changes in the system based on the error could accumulate.
Therefore it is necessary to recount the number of particles of any type at
the end of each movement phase.  This in some ways doubles the time required
to animate any interacting particle system, but is still linear in time and
better than N squared.

Thus, the steps required to interact 2 particle systems with message passing
can be generalized as follows:

<UL>
<LI>	Remove "dead" particles of type 1 from the particle system
<LI>	Move the type 1 particles
<LI>	After all type 1 particles have moved, each type 1 particle notes final state
<LI>	Remove "dead" particles of type 2 from the particle system
<LI>    Move the type 2 particles
<LI>	After all type 2 particles have moved, each type 2 particle notes final state
</UL>

<H3> 4.0 Results </H3>

	Though the above presented method solves many problems, there are
a few that are more difficult to side-step.  In particular, conservation of
momentum is difficult to maintain- simulating a collision is easily done 
using a probabilistic method and in closely approximating reality  should
be done through every bin which the particle moves.  However, when a collision
occurs the only particle that can be affected (unless message passing is
again used) is the source particle.  <P>
	This problem encountered during the research can either be side-stepped
by ignoring interim bins completely (as is done in this research) or perhaps
can have a damping factor applied proportionate to the number of collisions
that might have occurred.  

	Another difficulty is that there are even more parameters that must
be tweaked into place to produce an image that approximates the reality and
doesn't approximate some alterante reality-- where flames progress upwards
in very defined bands for instance. <P>

	An implementation of an interdependent fire system was investigated
and can be seen by the results below.  The fire particle system image 
was originally created with a 200,000 particle-system. 
attempted to use 150,000 particles in the provided MPEG.
The particles are created during frames 1-30 and
after that are created from the particles that have already died. 
The image was rendered using <!WA1><!WA1><!WA1><!WA1><a href="http://www.tc.cornell.edu/Visualization/tools/dx.html"> 
DX </A> with a color map and an opacity map. The animation took approximately
11 minutes to create running on a RISC 6000 processor with 128 MB of memory. 
However, it has been noticed that due to the bin
limitations many of the particles go unused and essentially only slightly
more than 50,000 particles are being used.  Using only 50,000 particles 
(due to the current initialization sequence of the program) a slightly
less full animation is produced, but is comparable to the original and
only takes 5.4 minutes to create.  <P>

In the provided animation,
a particle's temperature is based on the number of particles
within the same region of space, while it's motion vector is determined
based upon the density of particles immediately within its own space as
well as those bins that immediately neighbor the space.  A damping factor
is applied to the motion in the plane that produces a circular cross-section
when no particles are collided, whereas in the vertical direction changes
in motion are based on temperature.  Overall, there are 21 parameters including
bin sizes that may be modified. It is also important to note, 
that if the bin size is selected to be too large, visible artifacts will
be generated.
<CENTER>
<!WA2><!WA2><!WA2><!WA2><A HREF="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/mccune/final/Images/FlamePic0.jpg"> <!WA3><!WA3><!WA3><!WA3><IMG ALIGN=CENTER  SRC="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/mccune/final/Images/FlamePic0.jpg">   </A>
</CENTER> <P>
The animation is also present as an <!WA4><!WA4><!WA4><!WA4><A HREF="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/mccune/final/flame.mpg"> MPEG. </A> <P>

There are some artifacts present in the animation of the flame that I am
not quite yet sure why they are there.  In the first frame of the animation
provided, a top view is provided.  It is possible to see from this top view
a criss-cross pattern that is an obvious artifact from using the bins and/or
some combination of the motion mechanism, although I am unsure as to why
this is the case.  Also, the flame tends to pulse from one frame to the next
which is something that would preferably not occur- I am unsure
what is causing the oscillatory motion. <P>


There is another benefit to using bins with an interdependent particle systems,
parallelization.  As opposed to passing particles and all their associated 
information across bin boundaries, only the information contained by the
bins need be passed.  This can save (given the amount of information each
particle must pass as well as the fact that there can be a good number
of particles per bin) up to more than 100 times the amount of message passing
that needs to be done.  Thus, it should be possible to parallelize the
application. <P>

One other effect should be noted.  In independent particle systems, groups
of particle systems can be lessened or local processing abandoned altogether
once sufficient information for a given area of the output area has been 
determined
(e.g. there is no reason to use a thousand particles to represent a section
of the screen only 10 pixels by 10 pixels wide).  In an interdependent particle
systems, this is not the case.  The entire process of the particle system is
dependent upon the presence and number of its nearest neighbors-- stopping
part of the particle system will eventually translate its effects to neighboring
parts of the particle system that are still moving, with <I>unknown</I> consequences.
Thus, some of the optimizations that are possible for independent systems,
are <I>not necessarily</I> possible with interdependent particle systems.  

<H3> 5.0 Conclusions	</H3>

	This work has demonstrated that an interdependent particle system 
approach is feasible and that it is possible to use some of the attributes
of the particle system itself to model "fuzzy" objects.  A model has been
proposed to allow the interaction of two particle systems and could possibly
be extended to more.  Many aspects of this work remain unexplored. Future work 
will finish the investigation of the proposed model
to interact two particle systems to result in a third.   <P>

	There are many aspects of interdependent particle systems where
	research could still be done.  For instance, 
investigating the interactions used on independent systems to achieve the
flickering of a flame by adding spirals or clustering particles.  Or trying
to simulate these effects by adding an air particle system to
the field to simulate the convection of air.  Starting
configurations that change over time and are not based on some random 
distribution of some preset starting configuration, but perhaps based on
preset data volumes.   It would also be interesting to see the results
of a wall of fire, or some other configuration of flames modeled on a
parallel processor.

<H3> 6.0 References </H3>

<P>
	"Particle Systems-- A Technique for Modeling a Class of Fuzzy Objects",
	William T. Reeves, ACM Transactions on Graphics, Vol 2, No 2, pp 91-108
<P>
	"Particle Animation and Rendering Using Data Parallel Computation",
	Karl Sims, Computer Graphics, Vol 24, No 4, pp 405-413

</body>

</HTML>