http:^^www.tc.cornell.edu^visualization^education^cs718^fall1995^mccune^final^report.html
来自「This data set contains WWW-pages collect」· HTML 代码 · 共 371 行 · 第 1/2 页
HTML
371 行
Date: Mon, 16 Dec 1996 22:14:49 GMTServer: NCSA/1.5Content-type: text/htmlLast-modified: Fri, 15 Dec 1995 19:12:13 GMTContent-length: 20114<HTML><TITLE> CS718 Project- Interdependent Particle Systems </TITLE> <BODY BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#000077"> <H2> Interdependent Particle Systems </H2><H3> by Justin A. McCune </H3><!WA0><!WA0><!WA0><!WA0><IMG SRC="http://www.tc.cornell.edu/Visualization/Education/cs718/fall1995/mccune/final/Images/hline.gif"><P><H3> 1.0 Introduction </H3> <P>Particle systems have been used to model a variety of "fuzzy" objectssuch as water, fire, grass, fireworks, clouds, smoke, and others. Inno work that I am aware of do the particles within the system interactwith each other. Instead to simulate the realities which they model,the designers of the particle-system use specific starting configurations,groups of particle systems, and introduce torques, spirals, and othereffects to the particle system(s). Sometimes to simulate waterfalls andother fuzzy objects where collisions are necessary, the particles arechecked for collision against a small number of external objects andare bounced off of the objects with which they collide. Independentparticle systems therefore, do not experience pressure gradients, donot collide with particles within their own system, and only approximatethe reality which they represent.The resultsreported within this paper report on particle-systems that do interactwith their neighboring particles. The motivation behind this researchis an attempt to allow the interactionof two or more particle systems and to more produce a more realisticmodel of particle systems.<P> Section 2 reviews the principles of independent particle systems,section 3 presents the problems and methods used in this research, section4 discusses the results, section 5 presents the conclusion and possibleextensions, while section 6 presents the references. <P><H3> 2.0 A Review of Independent Particle Systems </H3> Particle systems can usually be characterized by the followingproperties:<OL><LI> A lifetime<LI> A velocity<LI> A color <LI> A transparency<LI> A size<LI> A shape</OL> Almost all particles have a lifetime,velocity, and color wherethe remaining properties are decided upon by the modeller. Over the lifetime ofthe particle, the particle will change some or all of its attributes- thecolor might fade from white to red before it "dies". Velocities ofparticles can increase, decrease, or alter directions due to gravity or a collision with some object. <P> The other characteristic of particle systems is that there are a large number of particles. Water is technically comprised of billions andbillions of H2O molecules, and a particle system likewise represents whatit models with many many particles, though not billions and billions. The typical particle system is comprised of thousands of particles wherethis could range from a few thousand to hundreds of thousands dependingupon the resolution needed and the size of the desired image. <P>Particle systems are used to model "fuzzy" objects, such as fire, water,and other dynamic systems that are difficult to model with conventionalmethods, mainly due to the wide variations in color and shape even forjust one moment in time. To provide a well known example of a particlesystem take a look at the "Genesis Effect" in Star Trek II: The Wrath of Kahn. A particle system is used to model first an explosion and then the spreadingof a fire around a planet. The Genesis Effect used 25-750+ thousand particles throughout the course of the animation.<H3> 3.0 Interdependent Particle Systems </H3>In an interdependent particle system, particles can change based onthe presence, number, and/or proximity of neighboring particles. Inreal systems comprised of molecules, large densities tend to disperseuntil equilibrium is reached. Molecules also exchange energy, and thatenergy can directly affect the color of the light that the moleculeemits or reflects. With an interdependent particle system, it becomespossible to simulate these effects. For instance, take a fire particlesystem and a water particle system and mix parts of the systems together-the result is steam. An interdependent system of fire and water interactingto produce steam was the goal and motivation of this research. <P>The obvious and most difficult problem when dealing with an interactive particle system is the large number of particles.To determine collision, engergy exchange, or other interactive effectson any particle X, the particle either must search or sum the effectsof all its neihgboring N-1 particles. The problem as most simplyand correctly formulated is N squared in complexity.With a hundred thousand particles, however, moving and changing Nsquared particles per frame of an animation will take too long.A simplificationis needed to make the system develop more quickly and is easily justifiedand arrived at when examining real systems. <P>In all systems we are concerned with, a particle's dependency on its neighbors is usuallyproportional to or less than the inverse square of the distance betweenit and the neighbor. With thousands of particles within asystem, it is likely that much less than a hundred particleswill actually contribute significantly to the motion or energy levelof any particle. Thus, there is but to determine what a "significant"contribution is, the distance where the average particle's contributionwill be less than significant, and which particles are within that distance.<P>The problem is simplified, but to determine which particles are withinthe distance without any other information than given by the particlesthemselves would still be an N squared operation. Therefore, it is logical to introduce into the model, the concept of bins. Space isdivided into regularly spaced equal volume bins. Each particle is put into the bin corresponding to its location in space. Thus, thereare two large lists - one a list of all the particles, and the other an arranged set of bins containing pointers to the appropriate particle.<P>Ideally each bin would in any dimension be at least the size of thedistance whereby a particle is judged to possibly have a significantcontribution. To determine the contributions of the neighbors to particle X,the program would need to search only the other particles within the bin that particle X is in and all the particles within the immediately neighboring bins --to deal with particles located near the boundaries of a bin.Since all particles within the threshold distance are guaranteed to be withinthe space searched, particle X is guaranteed to be modified by all significantcontributors.<P>Though this would work, it is impractical to implement due to memorylimitations. The ideal bin size would generally be only three to fourtimes the size of a particle. However to account for all the places aparticle might move to during the progression of its life, there will be a largepercentage of bins that most of the time are empty.Given this and the fact that there are 3 dimensions which must have binsallocated, result in very large numbers of bins. For instance,taking a hundred bins per each dimension, results in the need for a millionbins- more bins than particles. A hundred bins, would also be inefficientfor many parts of the particle system where there were large densities ofparticles-- again the lists to be searched would be in the hundreds perparticle negating the effectiveness of using bins. Therefore, a larger number of bins is necessary, but using more bins wouldquickly exhaust the resources of almost any computer. <P>To solve this problem we must simplify the model even further losing muchof the accuracy that could be obtained with the previous methods. Each binis now allowed to hold only a number of particles, a temperature,or some othermost important data element. Insteadof containing a variable size list of particles within the bin, it contains a set small number of informational elements. This results in the loss of alot of useful information and willresult in rough approximations thatlose the accuracy of earlier models. However, interdependent reactionsare still possible, because there is some information available about any particle's localregion of space and its immediately neighboring areas of space. <P>The problem is transformed from one of searching through thousands of particlesto one of communication and/or accuracy. By containing only such simple information, spatialrelation is lost, as well as specific data, and most importantly identity.Simulation of collisions, movement, and temperature exchange is now possibleonly as probabilities and is no longer deterministic. <P>For example, to determine the collision of a particle X moving through spacewith another particle, we must bound the maximum number of particles in anygiven region of space. If particle X is attempting to move through a bin,then collision occurs with a probablility equal to the number of particles within the bindivided by the maximum number of particles allowed in the bin. For example,if the maximum number of particles per bin is 30, and there are 19 particlesin the bin that particle X is attempting to move through, then there is a 2/3rds chance that particle X will collide. <P>The communication issue is also a problem that must be resolved. In the efforts to research fire and water combining to form steam, the appropriatephysical model is each particle exchanges temperatures and sometimes steamis created and/or sometimes the fire is extinguished. Since the identityof any particle within a bin is lost, a particle that moves from a bin toanother bin where it should change state and likewise decrement the opposing⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?