05计算机图形学双语课程systems

1、Particle Systems1Angel: Interactive Computer Graphics 5E Addison-Wesley 2009原著Ed AngelProfessor of Computer Science, Electrical and Computer Engineering, and Media ArtsUniversity of New Mexico编辑 武汉大学计算机学院图形学课程组2Angel: Interactive Computer Graphics 5E Addison-Wesley 2009IntroductionMost important of

2、procedural methodsUsed to modelNatural phenomenaCloudsTerrainPlantsCrowd ScenesReal physical processes3Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Newtonian ParticleParticle system is a set of particlesEach particle is an ideal point massSix degrees of freedomPositionVelocityEach part

3、icle obeys Newtons law f = ma4Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Particle Equationspi = (xi, yi, zi)vi = dpi/dt = pi = (dxi/dt, dyi/dt, zi/dt)m vi = fiHard part is defining force vector5Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Force VectorIndependent Particl

4、es O(n)GravityWind forcesCoupled Particles O(n)MeshesSpring-Mass SystemsCoupled Particles O(n2)Attractive and repulsive forces6Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Solution of Particle Systemsfloat time, delta state6n, force3n;state = initial_state();for(time = t0; timefinal_ti

5、me, time+=delta) force = force_function(state, time);state = ode(force, state, time, delta);render(state, time)7Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Simple ForcesConsider force on particle i fi = fi(pi, vi)Gravity fi = g gi = (0, -g, 0)Wind forcesDragpi(t0), vi(t0)8Angel: Inter

6、active Computer Graphics 5E Addison-Wesley 2009MeshesConnect each particle to its closest neighborsO(n) force calculationUse spring-mass system9Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Spring ForcesAssume each particle has unit mass and is connected to its neighbor(s) by a springHo

7、okes law: force proportional to distance (d = |p q|) between the points10Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Hookes LawLet s be the distance when there is no force f = -ks(|d| - s) d/|d|ks is the spring constantd/|d| is a unit vector pointed from p to qEach interior point in m

8、esh has four forces applied to it11Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Spring DampingA pure spring-mass will oscillate foreverMust add a damping termf = -(ks(|d| - s) + kd dd/|d|)d/|d|Must project velocity12Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Attraction

9、and RepulsionInverse square law f = -krd/|d|3General case requires O(n2) calculationIn most problems, the drop off is such that not many particles contribute to the forces on any given particleSorting problem: is O(n log n)13Angel: Interactive Computer Graphics 5E Addison-Wesley 2009BoxesSpatial sub

10、division techniqueDivide space into boxesParticle can only interact with particles in its box or the neighboring boxesMust update which box a particle belongs to after each time step14Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Linked ListsEach particle maintains a linked list of its

11、neighborsUpdate data structure at each time stepMust amortize (分期偿还) cost of building the data structures initially15Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Particle Field CalculationsConsider simple gravityWe dont compute forces due to sun, moon, and other large bodiesRather we u

12、se the gravitational fieldUsually we can group particles into equivalent point masses16Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Solution of ODEsParticle system has 6n ordinary differential equationsWrite set as du/dt = g(u,t)Solve by approximations using Taylors Thm17Angel: Interac

13、tive Computer Graphics 5E Addison-Wesley 2009Eulers Methodu(t + h) u(t) + h du/dt = u(t) + hg(u, t)Per step error is O(h2)Require one force evaluation per time stepProblem is numerical instability depends on step size18Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Improved Euleru(t + h)

14、 u(t) + h/2(g(u, t) + g(u, t+h) Per step error is O(h3)Also allows for larger step sizesBut requires two function evaluations per stepAlso known as Runge-Kutta method of order 219Angel: Interactive Computer Graphics 5E Addison-Wesley 2009ContraintsEasy in computer graphics to ignore physical realitySurfaces are virtualMust detect collisions separately if we want exact solutionCan approximate with repulsive forces20Angel: Interactive Computer Graphics 5E Addison-Wesley 20