Game Engine Gems 2



2

G

P

G

L

Ma

r

Tait

u

22.1Int

Thi

s

gen

e

tech

n

that

inde

of e

a

Fi

gu

sphe

r

p

arti

c

2

2

P

GPUC

l

L

SL,Op

e

r

co Fratarc

a

u

s Software

It

roductio

n

s

chapter pro

v

e

ric program

m

n

ologies are

simulates a

p

rs, and plane

s

a

ch different

t

u

re 22.1. A pi

e

r

e at interacti

v

c

les.

l

othSi

m

e

nCL,a

a

ngeli

It

alia

n



v

ides a com

p

m

ing on the

G

used for im

p

p

iece of clot

h

s

(see Figure

t

echnology i

n

e

ce of cloth fa

l

v

e rates. The c

m

ulati

o

ndCU

D

p

arison stud

y

G

PU, namel

y

p

lementing a

n

h

colliding w

i

22.1). We as

s

n

terms of us

a

l

ls under the i

n

loth is compo

s

o

nUsin

g

D

A

y

between th

r

y

, GLSL, CU

n

interactive

i

th simple pr

i

s

ess the adva

n

a

bility and pe

r

n

fluence of gr

a

s

ed of 780,00

0

g



r

ee popular

p

U

DA, and Op

e

physically-

ba

i

mitives like

s

n

tages and t

h

r

formance.

avity while c

o

0

springs con

n

p

latforms for

e

nCL. These

a

sed method

s

pheres, cyl-

h

e drawbacks

o

lliding with a

n

ecting 65,000

365

366 22.GPGPUClothSimulationUsing GLSL,OpenCL,andCUDA

Figure 22.2. A

4

4 grid of particle vertices and the springs for one of the particles.

22.2NumericalAlgorithm

This section provides a brief overview of the theory behind the algorithm used in

computing the cloth simulation. A straightforward way to implement elastic net-

works of particles is by using a mass-spring system. Given a set of evenly spaced

particles on a grid, each particle is connected to its neighbors through simulated

springs, as depicted in Figure 22.2. Each spring applies to the connected particles

a force

spring

F

:





spring

kb





0

F

ll x



,

where l represents the current length of the spring (i.e., its magnitude is the dis-

tance between the connected particles),

0

l

represents the rest length of the spring

at the beginning of the simulation, k is the stiffness constant,

x



is the velocity of

the particle, and b is the damping constant. This equation means that a spring

always applies a force that brings the distance between the connected particles

back to its initial rest length. The more the current distance diverges from the rest

length, then the larger is the applied force. This force is damped proportionally to

the current velocity of the particles by the last term in the equation. The blue

springs in Figure 22.2 simulate the stretch stress of the cloth, while the longer red

ones simulate the shear and bend stresses.

For each particle, the numerical algorithm that computes its dynamics is

schematically illustrated in Figure 22.3. For each step of the dynamic simulation,

(i, j)

(i, j + 1)

(i + 1, j − 1)

(i − 2, j − 2)

22.2NumericalAlgorithm 367

Figure 22.3. Numerical algorithm for computing the cloth simulation.

the spring forces and other external forces (e.g., gravity) are applied to the parti-

cles, and then their dynamics are computed according to the Verlet method [Mül-

ler 2008] applied to each particle in the system through the following steps:

1.

   



ΔΔtttttxxx



.

2.

  

,tttmxFxx

 

.

3.

















2

Δ 2 ΔΔtt t tt tt xxxx



.

Here,





t

F

is the current total force applied to the particle, m is the particle mass,





tx



is its acceleration,





tx



is the velocity,





tx

is the current position, and

Δ

t

is

the time step of the simulation (i.e., how much time the simulation is advanced

for each iteration of the algorithm).

The Verlet method is very popular in real-time applications because it is

simple and fourth-order accurate, meaning that the error for the position compu-

tation is



4

ΔOt

. This makes the Verlet method two orders of magnitude more

precise than the explicit Euler method, and at the same time, it avoids the compu-

Initial state

Compute forces F(t):

springs and gravity

Compute acceleration

Compute new state

Update state

Handle collisions

 

ttmxF



 

00

,ttxx





Δ , Δtt ttxx



  

, Δ , Δt t tt tt← xx x x

