Volume 28 (2009), Number 7 pp. 1–8

COMPUTER GRAPHICS forum

Chain Shape Matching for Simulating Complex Hairstyles
W. Rungjiratananon1 , Y. Kanamori2 and T. Nishita1
1 The University of Tokyo, Japan
2 University of Tsukuba, Japan

Abstract
Animations of hair dynamics greatly enrich the visual attractiveness of human characters. Traditional simulation
techniques handle hair as clumps or continuum for efficiency; however, the visual quality is limited because theycannot represent the fine-scale motion of individual hair strands. Although a recent mass-spring approach tackled
the problem of simulating the dynamics of every strand of hair, it required a complicated setting of springs andsuffered from high computational cost. In this paper, we base the animation of hair on such a fine-scale on Lattice
Shape Matching (LSM), which has been successfully used for simulating deformable objects. Our method regards
each strand of hair as a chain of particles, and computes geometrically-derived forces for the chain based onshape matching. Each chain of particles is simulated as an individual strand of hair. Our method can easily handle
complex hairstyles such as curly or afro styles in a numerically stable way. While our method is not physicallybased, our GPU-based simulator achieves visually-plausible animations consisting of several tens of thousandsof hair strands at interactive rates.
Categories and Subject Descriptors (according to ACM CCS): I.3.7 [Computer Graphics]: Three-Dimensional
Graphics and Realism—Animation

1. Introduction
Simulating the dynamics of a full head of hair (i.e., typically one hundred thousand hair strands) has, for a longtime, been a challenging task in computer graphics. The difficulty mainly stems from the computational cost and numerical stability, especially in the interactions between individual strands of hair, which are essential for animation. Other
important concerns for hair simulation include how to model
each strand to represent various hairstyles; many recent techniques handle hair as clumps or a continuum to avoid thecomputational issues and focus on specific hair styles suchas straight only [BNC03,Osh07,TB08] or straight plus curly
hairstyles [VMT06, BAC∗ 06]. Recently, an extended massspring model [SLF08] undertook to simulate the dynamics
of up to ten thousand individual hair strands. However, thisrequired a complicated configuration for the spring structureand suffered from high computational cost.
In this paper, we undertake fine-scale animation of alarge number of individual hair strands based on Lattice
Shape Matching (LSM) [RJ07]. LSM has been successfully
used for simulating deformable objects because it is simple,
fast and numerically stable. While LSM assumes that a dec 2010 The Author(s)Journal compilation c 2010 The Eurographics Association and Blackwell Publishing Ltd.
Published by Blackwell Publishing, 9600 Garsington Road, Oxford OX4 2DQ, UK and
350 Main Street, Malden, MA 02148, USA.

Figure 1: Animating 10k straight strands of hair (16 particles per strand, about 12 fps on the GPU), with the dynamics
of each strand of hair.

formable object can be approximated by a set of particlesaligned in a lattice, we represent a hair strand as a chain ofRungjiratananon et al. / Chain Shape Matching for Simulating Complex Hairstyles

Table 1: Advantages of our method against previous methods for hair strand dynamics.
Stability
HairstyleConstraint
Performance

Rigid chain [HMT01]
conditionalstraight only
trickyoff-line

Super helices [BAC∗ 06]
conditional
complex configurations
trickyoff-line

particles; therefore we call our method Chain Shape Matching (CSM). CSM is much simpler than LSM because it only
considers deformations along a single chain. We can immediately use the particles’ positions in the original shape tocreate a chain structure, which greatly benefits the design
process. While a hair strand should not be stretched, theoriginal LSM was not concerned with stretching because it
targeted deformation only. However, we successfully integrated a stretching constraint into the LSM framework.
Our proposed model is not physically-based, targetinginteractive applications including games. Our method canbe implemented entirely on the GPU and achieve interactive performance for up to several tens of thousands of hairstrands (Figure 1).
2. Previous WorkThe early research on hair simulation handled the dynamics of individual strands of hair using the mass-spring system [RCT91] and projective dynamics [AUK92]. However,these methods ignore hair-hair interactions, curliness andtorsion. Hadap and Magnenat [HMT01] use a rigid multibody serial chain to represent a hair strand which can capture the torsion effect, but still ignore curliness. Bertails etal. [BAC∗ 06] introduced a mechanical model called superhelixes based on Kirchhoff’s theory to represent a strand of
hair. The model can capture bending, torsion, non-stretching
and the curliness behavior of hair at high expense of computational cost.
For computational efficiency, several techniques regard
hair as disjoint groups [DTKT93, PCP02] or a continuum [HMT01, BNC03, VMT06], limiting the degrees of
freedom (DOFs) of the hair motion; although human hair has
a collective tendency, a high number of DOFs is required torepresent the fine-scale motion of hair blown about by thewind. Please refer to the survey [WBK∗ 07] for advances onhair modeling, styling, simulation and rendering.
Recently, mass-spring systems have commonly been used
for simulating hair dynamics. Integrations in mass-spring
systems are performed using explicit or implicit schemes.
Explicit schemes are often preferred due to the low computational cost and ease of implementation. However, for stable
simulation, the time step in an explicit scheme should be inversely proportional to the square root of the spring constant(the Courant condition). As a result, highly stiff hair is difficult to simulate at an interactive rate when using an explicit

Mass-spring [SLF08]
unconditional
complex configurations
easy
off-line

Our method
unconditional
easy
easy
interactive

scheme. Implicit schemes can solve the stability problem,with higher computational cost. Selle et al. [SLF08] proposed the use of additional altitude springs to simulate thecomplex behavior of human hair and semi-implicit springs
to solve the stability problem. However, this is not suitable
for stylized hair in interactive applications due to the expensive cost and complex configuration of the springs.
As for hair-hair interactions, most of the previous
methods only consider collisions occurring on guide hairstrands [CCK05, BAC∗ 06] and possibly miss collisions between interpolated hair strands when the guide strands do
not collide. There has been little research done that takes fullhair-hair interactions into consideration, except for the timeconsuming bounding box hierarchy used in [SLF08] and the
hybrid technique of Eulerian and Lagrangian methods introduced in [MSW∗ 09]. Tariq and Bavoil [TB08] introduceda fast technique for inter-hair collisions using a hair density
field. All the hair strands are voxelized into a grid then repulsive forces are applied to hair particles in high density areas.
However, their technique only affects volume preservationof hair. The same limitation can be seen in the continuum
methods [HMT01, BNC03, VMT06].
Unlike most of the previous works, our method is easy
to implement, can easily handle complex hairstyles, is interactive and numerically stable even if the hair is very stiff.
Also, our method handles collisions between individual hairstrands. This is accomplished by using particle-particle collision detection. The advantages of our method for simulating hair strand dynamics against those described in previous
works are summarized in Table 1.

3. Hair Simulation Method
Here we briefly explain Lattice Shape Matching(LSM) [RJ07] because it forms the basis of our method.
Then we describe how to model hair using our Chain ShapeMatching (CSM). While hair strands, in actual fact, do
not stretch, they are stretched in LSM. We also introduce
strain limiting for CSM. Finally, we describe the hair-hairinteraction algorithm in our model.

3.1. Lattice Shape Matching (LSM)
LSM is an extension of the shape matching
method [MHTG05]. The main advantages of the shapec 2010 The Author(s)Journal compilation c 2010 The Eurographics Association and Blackwell Publishing Ltd.

Rungjiratananon et al. / Chain Shape Matching for Simulating Complex Hairstyles

matching method are unconditional stability and high controllability due to its geometrically-motivated computation.
Optimally-transformed positions are computed first, andthen particles are moved towards those positions. Since
it guarantees that all particles are updated towards theappropriate positions, the overshooting problem that occurs
in explicit integration schemes is eliminated. This technique
is later generalized as position based dynamics [MHHR07],
which can be applied to general simulation systems.
In LSM, the particles are grouped into multipleoverlapping cubical regions (Figure 2b). The region halfwidth value w (w = 1, 2, 3, · · · ) corresponds to the stiffness ofthe object. The positions of particles are updated as follows.
First, they are moved independently according to the external forces. Next, for each region, LSM computes an optimal
rigid transformation (i.e., rotation and translation) based onshape matching [MHTG05]. The rigidly-transformed positions of the particles are called goal positions. The goal position gi of particle i is weighed in the overlapping regions
miei = N, where mi is the mass ofby particle per-region mass mrparticle i and Nr is the total number of regions that the particle i belongs to. The goal position of particle i is computed
as follows.
gi =1∑ (Rr (x0i − x0cm,r ) + xcm,r ),Nr r∈Ri(1)where Ri is a set of regions that particle i belongs to, x0i is
the original position, x0cm,r is the center of mass of the original shape of the region, xcm,r and Rr are the optimal translation and rotation for region r. Finally, for each particle, thevelocity is computed toward the goal position.
fi,ext (xi ,t)gi (t) − xi (t)
+ dt
, (2)
dt
mi
xi (t + dt) = xi (t) + dtvi (t + dt),
(3)vi (t + dt) = vi (t) +where dt is a time step, vi is the velocity and fi,ext the external force.
3.2. Hair Simulation Using Chain Shape Matching(CSM)
In our method, a hair strand is represented by a chain of particles grouped into multiple overlapping chain regions (Figure 2d). Each particle i is associated with a chain region
Ri ∈ Ri that centers the particle i and contains adjacentparticles within the region half-width w. Each chain region
uses the same shape matching method as used in LSM (Figure 3). Therefore we call our algorithm Chain Shape Matching (CSM). Algorithm 1 describes the pseudocode of ouralgorithm.
Note that the rotation matrix R can be inverted, i.e., it
can involve reflection. Reflection causes flipping of the input
shape, and therefore should be avoided for ordinary shape
matching [MHTG05, RJ07]; however, it has little influencec 2010 The Author(s)Journal compilation c 2010 The Eurographics Association and Blackwell Publishing Ltd.

Deformable object LatticeRegions

Lattice particles(a) LSM for a deformable object (b) LSM for a deformable object(A lattice and regions)(An object and a lattice)Hair strand
Lattice(c) LSM for a hair strand

Hair particles
Chain regions(d) CSM for a hair strand

Figure 2: Illustrations for Lattice Shape Matching (LSM)
and Chain Shape Matching (CSM).
Algorithm 1 Pseudocode of CSM algorithm.
1: for all particles i do
2:
initialize original position x0i , xi ← x0i
3: end for
4: loop5:
BucketGeneration() // Sections 3.4 and 4.1
6:
for all particles i do
7:fi,ext ← ComputeCollisionForce() + fgravity
8:
end for9:
for all particles i dofi,ext10:vi ← vi + dt mi
11:xi ← xi + dtvi
12:
end for13:
for all chain regions Ri do
14:
xcm ← ComputeOptimalTranslation()
15:
R ← ComputeOptimalRotation()16:
end for17:
for all particles i do
18:
gi ← ComputeGoalPosition() // Eq.1
19:
end for20:
for all particles i do
21:
gi ← StrainLimiting() // Section 3.3
22:xi ← gii
23:
vi ← vi + gi −x
dt
24:
end for
25: end loop

in our case because we employ one-dimensional shapes, andthus can be ignored.
In CSM, we can design complex hairstyles at the strandlevel as follows. The shape of the strand can be definedby the original particle positions, since these original positions define the shape of the strand at rest (Figure 4). The
root of each strand is fixed by several particles which areRungjiratananon et al. / Chain Shape Matching for Simulating Complex Hairstyles
x0
Original lattice shape
x01
x00

x30

x20

Optimal translation
and rotation

Original chain shape
x00
x01
x20

g0
g1
x1
x3 g3

x0

x40

Optimal translation
and rotation

Figure 5: A bunch of 1,000 strands is dragged over a cylinder, with different chain region half-width w. Small w makes
the strands softer while large w stiffer.

g0
x2

x1
x30

g2

g3 g4

g1

x4

g2
x3

Figure 3: x0i is the original position, xi is the position updated by external forces and gi is the goal position of particlei.

Figure 4: The original particle positions define the shapesof the hair strands.

constrained on the head. The number and direction of theconstrained particles partially determine the behavior of thestrand. The stiffness of the strand is defined by the chain
region half-width w (Figure 5), which can be partially modified to generate complex hairstyles; e.g., soft straight hairnear the root and stiff curly hair near the tip of the hair strand.
Regarding the stiffness control of hair strands, one might
consider the use of parameters α, β ∈ [0, 1], as presented in
the original shape matching paper [MHTG05]; α controls
the tendency that goal positions are moved towards rigidlytransformed positions, and β allows goal positions to undergo a linear transformation (see [MHTG05] for more details). While α and β can control the stiffness independentlyof w, we simply fix α = 1 and β = 0 according to the LSM
paper [RJ07], taking into account that α and β can make aregion softer but not stiffer. Although reducing the numberof particles makes a region stiffer, it also reduces the hairstrand’s DOFs required especially for complex hairstyles.
Nevertheless, the use of α and β in conjunction with w might
benefit to advanced stiffness control, which is left as future
work; a study on the relationship between β and w can befound in [OKN09].

3.3. Strain Limiting
In this subsection, we describe how to limit the stretching of
hair. Techniques for constraining stretching were originallyproposed in research on cloth simulation, known as strain
limiting. Most of the cloth simulations use an elastic system
to model cloth such as popular mass-spring systems. As adrawback, the cloth becomes very elastic and looks unnatural. Provot et al. [Pro95] therefore modified positions bychecking the length of each segment (a spring in the massspring systems) in the cloth and then adjusting the lengthof stretched segments. However, modifying one segment
causes stretching of other connected segments. Although iterative modification can be applied, convergence is not guaranteed. Bridson et al. [BFA02] and Selle et al. [SLF08] modified velocity instead of position. In our framework, however,goal positions are computed first and then the velocities arecomputed so that particles are moved towards the goal positions (Section 3.1). Therefore, modifying velocity is not
appropriate for our CSM framework (position based framework).
To constrain stretching, we modify the positions ofstretched segments in hair strands after the shape matchingprocess (Figure 6a). Since the root of a hair strand is always
attached to the head, we adjust only the near-tip particle (theendpoint near the tip of the strand) of a stretched segmentto the non-stretched position. This adjustment process takes
place from the root to the tip of the strand, therefore an iterative adjustment is not required.
A simple option for strain limiting is to shrink segments
individually and then connect them together (Figure 6b);
however, our experiments yield unnatural results. Instead,
we move each near-tip particle along the direction of the previous segment that is already adjusted (Figure 6c). As a result, each hair strand becomes a smooth curve from the rootto the tip (Figure 6d). Note that just moving particles to thenon-stretched positions leads to the loss of linear and angularmomenta. To conserve the momenta, our method modifies
velocity, similarly to [MHHR07].
c 2010 The Author(s)Journal compilation c 2010 The Eurographics Association and Blackwell Publishing Ltd.

Rungjiratananon et al. / Chain Shape Matching for Simulating Complex Hairstyles
Hair root

Near-root particle
Non-stretched
Stretched
Near-tip particle

Position (A) Velocity (A)Pass 1 : Bucket
Generation

Pass 2 : Position Update
and Collision Detection

BucketPosition (B) Velocity (B)Property

(a)
(c)
(b)
(d)
The stretched strand Shrinking each Adjusting near-tip The comparison
after shape matching. stretched segment. particle in theof (b) and (c).
propagating direction.

Pass 3 :Chain Shape Matching

Original
Position

Figure 6: Comparison of stretched particles adjustment.

OptimalTranslation

Hair tip

OptimalRotation

Pass 4 : Goal Position
Computation

strand index = 1
strand index = 2

Position (B)Pass 5 : Strain Limiting

2D textures

strand index = 3
R G B

Position (A) Velocity (A)A

A texel with 4 color channels

Figure 7: Physical values of particles are stored in textures(up to four values per texel). Particles of each hair strand
are distinguished by the strand index. These are shown bydifferent colors in this figure.

3.4. Collision Detection and Response
For hair-hair and hair-head interactions, we employ simple
sphere-sphere collision detection that can be easily implemented on the GPU. Particles of hair strands required in
CSM are used for collision detection. Note that, to handle collisions more accurately, we can increase the number of particles independently of those used in CSM, while
our implementation uses identical particles. Particle-particle
collisions are detected using a uniform grid of voxels that
store the indices of particles. The pair particles colliding arefound from the neighboring 3×3×3 voxels, and the penalty
forces are added to them. For hair-head interactions, the headmodel is represented by a set of large spheres, and collisions
with each particle are calculated.
4. GPU Implementation
For the GPU computation, the physical values of particles
are stored in 2D textures in the GPU memory. We use 32bit
floating-point RGBA textures, and thus each texel can store
up to four values for a particle. Our implementation uses ten
textures, i.e., two position textures, two velocity textures,
one property texture (region half-width w, particle index,
c 2010 The Author(s)Journal compilation c 2010 The Eurographics Association and Blackwell Publishing Ltd.

Figure 8: Simulation flow of a single step on the GPU. Blue
rectangles represent the texture data, black rounded rectangles represent operations and green directed line segments
represent the flow of data.

strand index and limiting length), one original position texture, one texture for optimal translation and three textures
for optimal rotation (3×3 matrix, 9 components). Strand indices (see Figure 7) are required to distinguish strands because values for all particles are stored in the same textures,and each strand can contain a different number of particles.
In addition, our implementation requires one bucket texture,
where each texel represents a voxel that stores particle indices for nearest-neighbor searches in the collision detection
process.
4.1. Simulation Step
In each simulation time step, five passes of the GPU computation are assigned (see the black rounded rectangles in
Figure 8). The detail of each GPU pass is explained together
with corresponding line numbers of Algorithm 1 as follows:
Passes 1 and 2 : Position update and collision detection(lines 5-12) First, the bucket texture is generated for nearestneighbor searches using a GPGPU technique [Har07]. The
velocity of each particle is updated according to external
forces such as gravity and penalty forces calculated in thecollision detection process (Section 3.4). Then, the positionof each particle is updated according to the updated velocity
and the time step.

Rungjiratananon et al. / Chain Shape Matching for Simulating Complex Hairstyles

4

b w=5

5

3

2

2

1

1

a 1

1
w=3

2

2

3

3

c

Figure 10: Moving bunch of hair strands with (left) andwithout (right) strain limiting.

Figure 9: Connectivity information of hair particles on a
texture. (a) The region half-width w = 3. The particles in theregion can be found in the adjacent texels. (b) The region
half-width w = 5. All five adjacent particles in the right half
can be found. The left half has only two adjacent particles
in a strand. (c) Access pattern for strain limiting. The nonstretched position is computed by tracing the length of eachsegment from the root particle.

Pass 3 : Chain shape matching (lines 13-16) The optimal
rigid transformation of each chain region is computed fromthe particle positions in the region. Hair particles are stored
sequentially in a texture. See Figure 9 for an example of the
texture layout. Particle a has a half-width size w = 3. Particles contained in the region can be found in three texels tothe left and right hand sides. In the case of particle b with ahalf-width size w = 5, five adjacent particles can be found on
the right hand side, while the last two particles are found in
the next row by computing their addresses with the texture
width. However, the last three particles on the left hand side
have a different strand index. Therefore, only two adjacentparticles can be found. The region doesn’t have to contain amaximal number of particles (eleven in case of w = 5).
Pass 4 : Goal position computation (lines 17-19) After the
optimal translation and rotation computation, the goal position of each particle is computed by averaging the goal positions of overlapping regions (Equation 1). This process canbe computed in a similar way to the chain shape matching
pass (Pass 3). Instead of particle positions, the computed optimal translation and rotation of the overlapping regions canalso be read from the adjacent texels.
Pass 5 : Strain Limiting (lines 20-24) The final pass is thestrain liming process (Section 3.3). The non-stretched position of each particle can be computed from the length starting from the root particle of the strand to the particle (seeparticle c in Figure 9). After updating particle positions, thevelocities are also updated in this pass.
5. Results
The prototype implementation was written in C++, using
OpenGL and GLSL. All experiments were conducted on a

Figure 11: Increasing hair strands greatly improves the visual quality. From left to right, there are 1.25k, 5k and 10k
hair strands on the head.

PC with an Intel Core 2 Quad 3.00GHz, 2GB RAM and an
NVIDIA GeForce GTX 280 graphics card. The structure ofhair is rendered as connected line segments between particles, and the visual quality is enhanced by Catmull-Rom
splines on the GPU using the instanced tessellation technique [BS05]. As for the shading and self shadowing of
hair, we used the Kajiya-Kay shading model and Deep Opacity Maps [YK08], respectively. All simulation and rendering
were entirely conducted on the GPU. The frame rates in thispaper include both simulation and rendering. We perform
only a single simulation step per frame. Figure 10 shows theresult of hair simulation with and without strain limiting described in Section 3.3. The hair strands are stretched due tothe external forces without strain limiting. Figure 11 shows
the result with different numbers of strands on the head. With
more strands the visual quality is increased.
Figure 13 shows animation sequences of straight, curlyand complex hairstyles flowing in the wind. Each strand of
the complex hairstyle is straight around the top and curlyaround the bottom. Each scene consists of 10k strands (160k
particles), 10k strands (580k particles) and 17k strands (764k
particles), respectively. The breakdown computational timeused in each GPU pass and rendering for each result isshown in Figure 12. The simulation and rendering speedsof each sequence are 12, 7 and 4 fps, respectively.
c 2010 The Author(s)Journal compilation c 2010 The Eurographics Association and Blackwell Publishing Ltd.

Rungjiratananon et al. / Chain Shape Matching for Simulating Complex Hairstyles
51.8%

ms
150
140

~
~

31.4%

~
~

90
80

20
10

2.4%
2.8%
2.4%

30

References
9.2%

40

38.4%
19.2%
2.2%
1.9%
2.2%
36.1%

50

11.1%
1.9%
2.1%
3.1%

60

35.2%

46.6%

70

0

Figure 14 (top)(10k, 160k)
New pos. + Coll.
Goal Comp.

Figure 14 (middle) Figure 14 (bo"om)(10k, 580k)(23k, 764k)
Bucket Gen.
Strain Limi!ng[BAC∗ 06] can be applied for an application which prefers abetter performance to finer detail. For example, in the caseof one thousand hair strands with 30k particles (Figure 5),
our model can run at 61 fps, which is sufficiently fast forinteractive applications such as games.

CSM
Rendering

Figure 12: The computational time in milliseconds used ineach GPU pass and rendering. The detail of each GPU passis described in Section 4.1. The numbers of hair strands andparticles used in each result are shown as (no. of strands,
no. of particles).

6. Conclusions
We have presented a simple model for simulating hairbased on shape matching. Our method can achieve visuallyplausible animations with complex hairstyles in a numerically stable way, even for highly stiff and curly hair like anafro. We have also demonstrated that a GPU-based simulator
can achieve interactive performance up to several ten thousand hair strands.
There are some limitations in our method. Our model is
non-physically based, thus to specify the physical properties of hair strands such as elastic properties is impractical.
We used trial and error to get the desired result. We do notconsider the torsion of hair in our model. Torsion has lesssignificant effects for straight hair in common animations,because the external forces that twist straight hair are rare.
However, it does occur in curly hair. We would like to improve our model to capture the torsion of hair. One idea is theuse of the torsion spring presented in a rigid multibody serial chain [HMT01] which represents a hair strand as a chainof rigid segments could be adapted. Because the hair strand
in our model is also represented by a chain of particles, torsion springs between particles could be added to capture thetorsion effect. In addition, collisions between hair segments
cannot be detected in our model due to the use of spheresphere collision detection. We would like to employ a fastand robust collision detection that could find the intersections between lines as well. The stiction force influenced by
the electrostatic pull-in also has to be taken into account togenerate more realistic results.
Although our method simulates each strand of hair individually, an interpolation technique such as [CJY02] andc 2010 The Author(s)Journal compilation c 2010 The Eurographics Association and Blackwell Publishing Ltd.

[AUK92] A NJYO K., U SAMI Y., K URIHARA T.: A simple
method for extracting the natural beauty of hair. In SIGGRAPH’92: Proceedings of the 19th annual conference on Computer
graphics and interactive techniques (1992), pp. 111–120.
[BAC∗ 06] B ERTAILS F., AUDOLY B., C ANI M.-P., Q UERLEUX
B., L EROY F., L ÉVÊQUE J.-L.: Super-helices for predicting the
dynamics of natural hair. In SIGGRAPH ’06: ACM SIGGRAPH
2006 Papers (2006), pp. 1180–1187.
[BFA02] B RIDSON R., F EDKIW R., A NDERSON J.: Robust treatment of collisions, contact and friction for cloth animation. In
SIGGRAPH ’02: Proceedings of the 29th annual conference on
Computer graphics and interactive techniques (2002), pp. 594–
603.
[BNC03] BANDO Y., N ISHITA T., C HEN B.-Y.: Animating hairwith loosely connected particles. Comput. Graph. Forum 22, 3(2003), 411–418.
[BS05] BOUBEKEUR T., SCHLICK C.: Generic mesh refinement on GPU. In ACM SIGGRAPH/Eurographics Graphics
Hardware (2005), pp. 99–104.
[CCK05] C HOE B., C HOI M. G., KO H.-S.: Simulating complex hair with robust collision handling. In SCA ’05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on
Computer animation (2005), pp. 153–160.
[CJY02] C HANG J. T., J IN J., Y U Y.: A practical model forhair mutual interactions. In SCA ’02: Proceedings of the 2002
ACM SIGGRAPH/Eurographics symposium on Computer animation (2002), pp. 73–80.
[DTKT93] DALDEGAN A., T HALMANN N. M., K URIHARA T.,
T HALMANN D.: An integrated system for modeling, animating and rendering hair. In Computer Graphics Forum (1993),
pp. 211–221.
[Har07] H ARADA T.: Real-time rigid body simulation on GPUs.
GPU Gems 3, Chapter 29 (2007), 123–148.
[HMT01] H ADAP S., M AGNENAT-T HALMANN N.: Modelingdynamic hair as a continuum. Comput. Graph. Forum 20, 3(2001), 329–338.
[MHHR07] M ÜLLER M., H EIDELBERGER B., H ENNIX M.,
R ATCLIFF J.: Position based dynamics. J. Vis. Comun. Image
Represent. 18, 2 (2007), 109–118.
[MHTG05] M ÜLLER M., H EIDELBERGER B., T ESCHNER M.,
G ROSS M.: Meshless deformations based on shape matching. In
SIGGRAPH ’05: ACM SIGGRAPH 2005 Papers (2005), pp. 471–
478.
[MSW∗ 09] M C A DAMS A., S ELLE A., WARD K., S IFAKIS E.,
T ERAN J.: Detail preserving continuum simulation of straight
hair. In SIGGRAPH ’09: ACM SIGGRAPH 2009 Papers (2009),
pp. 1–6.
[OKN09] O HTA M., K ANAMORI Y., N ISHITA T.: Deformationand fracturing using adaptive shape matching with stiffness adjustment. Comput. Animat. Virtual Worlds 20, 2-3 (2009), 365–373.
[Osh07] O SHITA M.: Real-time hair simulation on GPU with adynamic wisp model. Comput. Animat. Virtual Worlds 18, 4-5(2007), 583–593.

Rungjiratananon et al. / Chain Shape Matching for Simulating Complex Hairstyles

Figure 13: Animation sequences of straight (top row, 12 fps), curly (middle row, 7 fps) and complex hairstyles (bottom row, 4 fps)
in the wind. There are 10k strands (160k particles), 10k strands (580k particles) and 23k strands (764k particles), respectively.
The stiffness configurations of the straight and curly hair are w = 2 and w = 5. Each strand of the complex hairstyle is straightnear the roots and curly near the tips with chain region half-widths of w = 2 and w = 6, respectively.

[PCP02] P LANTE E., C ANI M.-P., P OULIN P.: Capturing thecomplexity of hair motion. Graphical Models (GMOD) 64, 1(january 2002), 40–58.

[TB08] TARIQ S., BAVOIL L.: Real time hair simulation and rendering on the GPU. In SIGGRAPH ’08: ACM SIGGRAPH 2008
talks (2008), pp. 1–1.

[Pro95] P ROVOT X.: Deformation constraints in a mass-springmodel to describe rigid cloth behavior. In Graphics Interface ’95(1995), Davis W. A., Prusinkiewicz P., (Eds.), Canadian HumanComputer Communications Society, pp. 147–154.

[VMT06] VOLINO P., M AGNENAT-T HALMANN N.: Real-timeanimation of complex hairstyles. IEEE Transactions on Visualization and Computer Graphics 12, 2 (2006), 131–142.

[RCT91] ROSENBLUM R. E., C ARLSON W. E., T RIPP E.: Simulating the structure and dynamics of human hair: Modelling, rendering and animation. The Journal of Visualization and Computer Animation 2, 4 (1991), 141–148.
[RJ07] R IVERS A. R., JAMES D. L.: FastLSM: fast lattice shape
matching for robust real-time deformation. In SIGGRAPH ’07:
ACM SIGGRAPH 2007 papers (2007), p. 82.

[WBK∗ 07] WARD K., B ERTAILS F., K IM T.-Y., M ARSCHNER
S. R., C ANI M.-P., L IN M.: A survey on hair modeling: Styling,simulation, and rendering. IEEE Transactions on Visualization
and Computer Graphics (TVCG) 13, 2 (2007), 213–34.
[YK08] Y UKSEL C., K EYSER J.: Deep opacity maps. Computer
Graphics Forum (Proceedings of EUROGRAPHICS 2008) 27, 2(2008), 675–680.

[SLF08] S ELLE A., L ENTINE M., F EDKIW R.: A mass springmodel for hair simulation. In SIGGRAPH ’08: ACM SIGGRAPH
2008 papers (2008), pp. 1–11.
c 2010 The Author(s)Journal compilation c 2010 The Eurographics Association and Blackwell Publishing Ltd.