COMPUTER GRAPHICS forum

DOI: 10.1111/j.1467-8659.2010.01755.x

Volume 00 (2010), number 0 pp. 1–9

Chain Shape Matching for Simulating Complex Hairstyles
W. Rungjiratananon1 , Y. Kanamori2 and T. Nishita1

1 The University of Tokyo, Japan{witawat, nis}@nis-lab.is.s.u-tokyo.ac.jp
2 University of Tsukuba, Japankanamori@cs.tsukuba.ac.jp

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 physically
based, our GPU-based simulator achieves visually plausible animations consisting of several tens of thousands ofhair strands at interactive rates.
Keywords: hair simulation, shape matching, GPU, individual hair strand, interactive
ACM CCS: I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism—Animation

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 issimple, fast and numerically stable. While LSM assumes
that a deformable object can be approximated by a set ofparticles aligned in a lattice, we represent a hair strand asa chain of 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 to create a chain structure, which greatly benefits the design process. While a hair strand should not be
stretched, the original LSM was not concerned with stretching because it targeted deformation only. However, we successfully integrated a stretching constraint into the LSM
framework.

1. Introduction
Simulating the dynamics of a full head of hair (i.e. typically one hundred thousand hair strands) has, for a long time,
been a challenging task in computer graphics. The difficulty
mainly stems from the computational cost and numericalstability, 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 10 000 individual hair strands. However, this required a complicated configuration for the spring structureand suffered from high computational cost.
c 2010 The Authors
c 2010 The Eurographics Association and
Journal compilation Blackwell Publishing Ltd. Published by Blackwell Publishing,
9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main
Street, Malden, MA 02148, USA.

1

2

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

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 modelling, styling, simulation and rendering.

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.

Our proposed model is not physically based, targeting interactive applications including games. Our method can be
implemented entirely on the GPU and achieve interactive performance for up to several tens of thousands of hair strands(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, thesemethods ignore hair–hair interactions, curliness and torsion.
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 et al. [BAC∗ 06]
introduced a mechanical model called super-helixes basedon Kirchhoff’s theory to represent a strand of hair. The model
can capture bending, torsion, non-stretching and the curlinessbehaviour 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

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
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 behaviour of human hair and semi-implicit springs
to solve the stability problem. However, this is not suitable forstylized 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 hair strands[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 full hair–hair interactions into consideration, except for the time-consuming
bounding box hierarchy used in [SLF08] and the hybrid
technique of Eulerian and Lagrangian methods introducedin [MSW∗ 09]. Tariq and Bavoil [TB08] introduced a 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 methods, 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.

Table 1: Advantages of our method against the previous methods for hair strand dynamics

Stability
HairstyleConstraint
Performance

Rigid chain [HMT01]

Super helices [BAC∗ 06]

Mass-spring [SLF08]

Our method

Conditional
Straight only
TrickyOff-line

Conditional
Complex configurations
TrickyOff-line

Unconditional
Complex configurations
Easy
Off-line

Unconditional
Easy
Easy
Interactivec 2010 The Authors
c 2010 The Eurographics Association and Blackwell Publishing Ltd.
Journal compilation 3

W. Rungjiratananon et al. / Chain Shape Matching for Simulating Complex Hairstyles
Deformable object LatticeRegionsx0

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

Hair particles
Chain regions

g0
g1

Optimal translation
and rotation
0

x30

x2

Original chain shape
x00
x01

x0
x1

x40

(c) LSM for a hair strand(d) CSM for a hair strand

Figure 2: Illustrations for Lattice Shape Matching (LSM)
and Chain Shape Matching (CSM).

gi = N1r

Here we briefly explain LSM [RJ07] because it forms the basis of our method. Then we describe how to model hair using
our 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–hair interaction
algorithm in our model.

g0

Optimal translation
and rotation

g3 g4

g1
g2

x4
x3

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

3. Hair Simulation Method

g2

x2

x20
x30

x1

x3 g3






Rr x0i − x0cm,r + xcm,r ,

(1)

r∈Ri

where Ri is a set of regions that particle i belongs to, x0i
is the original position, x0cm,r is the centre of mass of theoriginal shape of the region, xcm,r and Rr are the optimaltranslation and rotation for region r. Finally, for each particle,
the velocity is computed toward the goal position.
gi (t) − xi (t)fi,ext (xi , t)
,
+ dt
(2)
dt
mi
xi (t + dt) = xi (t) + dtvi (t + dt),vi (t + dt) = vi (t) +3.1. Lattice shape matching
LSM is an extension of the shape matching method[MHTG05]. The main advantages of the shape matching
method are unconditional stability and high controllability
due to its geometrically motivated computation. Optimallytransformed positions are computed first, and then particles
are moved towards those positions. Since it guarantees thatall particles are updated towards the appropriate 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 2 b). The region halfwidth value w (w = 1, 2, 3, . . .) corresponds to the stiffnessof the object. The positions of particles are updated as follows. First, they are moved independently according to theexternal forces. Next, for each region, LSM computes an optimal rigid transformation (i.e. rotation and translation) basedon shape 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
by particle per-region mass m
i = Nmri , where mi is the mass ofparticle i and Nr is the total number of regions that the particle i belongs to. The goal position of particle i is computed

where dt is a time step, vi is the velocity and fi,ext the external
force.
3.2. Hair simulation using Chain Shape Matching
In our method, a hair strand is represented by a chain ofparticles grouped into multiple overlapping chain regions(Figure 2d). Each particle i is associated with a chain region
Ri ∈ Ri that centres the particle i and contains adjacent particles 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 CSM. Algorithm 2 describes
the pseudocode of our algorithm.
Note that the rotation matrix R can be inverted, that is, 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 influencein 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 defined by
the original particle positions, since these original positions

c 2010 The Authors
c 2010 The Eurographics Association and Blackwell Publishing Ltd.
Journal compilation 4

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

Algorithm 1: Pseudocode of CSM algorithm.

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

for all particles i do
initialize original position x0i , xi ← x0i
end forloop
BucketGeneration() // Sections 3.4 and 4.1
for all particles i dofi,ext ← ComputeCollisionForce() + fgravity
end forfor all particles i dofvi ← vi + dt i,ext
mixi ← xi + dtvi
end forfor all chain regions Ri do
xcm ← ComputeOptimalTranslation()R ← ComputeOptimalRotation()end forfor all particles i dogi ← ComputeGoalPosition() // Eq.1
end forfor all particles i dogi ← StrainLimiting() // Section 3.3
xi ← gi−xi
vi ← vi + gi dt
end forend loop

Figure 4: The original particle positions define the shapesof the hair strands. Green particles show the original particle
positions.
define the shape of the strand at rest (Figure 4 ). The root of
each strand is fixed by several particles which are constrainedon the head. The number and direction of the constrained
particles partially determine the behaviour of the strand. The
stiffness of the strand is defined by the chain region halfwidth w (Figure 5), which can be partially modified togenerate complex hairstyles; for example, 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 rigidly
transformed positions, and β allows goal positions to undergoa linear transformation (see [MHTG05] for more details).

Figure 5: A bunch of 1k strands is dragged over a cylinder,
with different chain region half-width w. Small w makes thestrands softer while large w stiffer.
While α and β can control the stiffness independently ofw, 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 length ofstretched 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 are computed 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,c 2010 The Authors
c 2010 The Eurographics Association and Blackwell Publishing Ltd.
Journal compilation 5

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

strand index = 1
Near-root particle
Non-stretched
Stretched
Near-tip particle

strand index = 2

Hair tip

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

Figure 6: Comparison of stretched particles adjustment.

we move each near-tip particle along the direction of theprevious segment that is already adjusted (Figure 6c). As aresult, each hair strand becomes a smooth curve from theroot to the tip (Figure 6d). Note that just moving particles
to the non-stretched positions leads to the loss of linear andangular momenta. To conserve the momenta, our method
modifies velocity, similarly to [MHHR07].

2D textures

strand index = 3
R G B

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 colours in this figure.

for nearest-neighbour searches in the collision detection process.

4.1. Simulation step
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 aredetected using a uniform grid of voxels that store the indicesof particles. The pair particles colliding are found from theneighbouring 3 × 3 × 3 voxels, and the penalty forces areadded to them. For hair–head interactions, the head modelis represented by a set of large spheres, and collisions witheach 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, that is, two position textures, two velocity textures,
one property texture (region half-width w, particle index,
strand index and non-stretched length), one original position
texture, one texture for optimal translation and three textures
for optimal rotation (3 × 3 matrix, nine 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

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 nearestneighbour 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.
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 ofthe texture layout. Particle a has a half-width size w = 3.
Particles contained in the region can be found in three texels
to the left and right hand sides. In the case of particle b witha half-width size w = 5, five adjacent particles can be foundon the right hand side, while the last two particles are foundin 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 does not have to containa maximal number of particles (11 in case of w = 5).
Pass 4 : Goal position computation (lines 17–19) Afterthe 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c 2010 The Authors
c 2010 The Eurographics Association and Blackwell Publishing Ltd.
Journal compilation 6

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

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

Pass 2 : Position Update
and Collision Detection

BucketPosition (B) Velocity (B)Property

Pass 3 :Chain Shape Matching

Original
Position

w=5

OptimalTranslation

w=3

(b)
(a)

(c)
Figure 9: Layout of hair particles on a texture memory. (a)The region half-width w = 3. The particles in the region canbe 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 non-stretched position
is computed by tracing the length of each segment from theroot particle.

OptimalRotation

Pass 4 : Goal Position
Computation
Position (B)Pass 5 : Strain Limiting
Position (A) Velocity (A)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.

can be 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
can also be read from the adjacent texels.

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

Pass 5 : Strain Limiting (lines 20–24) The final pass isthe strain liming process (Section 3.3). The non-stretchedposition of each particle can be computed from the length
starting from the root particle of the strand to the particle(see particle c in Figure 9). After updating particle positions,the velocities are also updated in this pass.
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.

5. Results
The prototype implementation was written in C++, using
OpenGL and GLSL. All experiments were conducted on a
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
the result 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 12 shows animation sequences of straight, curlyand complex hairstyles flowing in the wind. Each strand ofc 2010 The Authors
c 2010 The Eurographics Association and Blackwell Publishing Ltd.
Journal compilation 

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

7

Figure 12: 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 5. Each strand of the complex hairstyle is straight near
the roots and curly near the tips with chain region half-widths of w = 2 and 6, respectively.
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 is shownin Figure 13 . The simulation and rendering speeds of eachsequence are 12, 7 and 4 fps, respectively.

6. Conclusions
We have presented a simple model for simulating hair basedon shape matching. Our method can achieve visually plausible animations with complex hairstyles in a numericallystable way, even for highly stiff and curly hair like an afro.
We have also demonstrated that a GPU-based simulator canachieve 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 isthe use of the torsion spring presented in a rigid multibody
serial chain [HMT01] which represents a hair strand as achain of rigid segments could be adapted. Because the hairstrand in our model is also represented by a chain of particles,c 2010 The Authors
c 2010 The Eurographics Association and Blackwell Publishing Ltd.
Journal compilation 8

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

ms
150
140

~
~

31.4%

~
~

90

[BNC03] BANDO Y., NISHITA T., CHEN B.-Y.: Animatinghair with loosely connected particles. Computer Graphics Forum (Proceedings of EUROGRAPHICS 2003), 22,
3 (2003), 411–418.

80

20
10

2.4%
2.8%
2.4%

30

[BS05] BOUBEKEUR T., SCHLICK C.: Generic mesh refinement
on GPU. In ACM SIGGRAPH/Eurographics Graphics
Hardware (Los Angeles, CA, USA, 2005), Eurographics
Association, pp. 99–104.

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

(10k, 160k)(10k, 580k)(23k, 764k)

New pos. + Coll.
Goal Comp.

Bucket Gen.

CSM
Rendering

Figure 13: 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).
torsion springs between particles could be added to capture
the torsion effect. In addition, collisions between hair segments cannot be detected in our model due to the use of
sphere–sphere collision detection. We would like to employ
a fast and 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 accountto generate more realistic results.
Although our method simulates each strand of hair individually, an interpolation technique such as [CJY02] and[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.

[CCK05] CHOE B., CHOI 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 (Los Angeles, CA,
USA, 2005), ACM Press, pp. 153–160.
[CJY02] CHANG J. T., JIN J., YU Y.: A practical model for hairmutual interactions. In SCA ’02: Proceedings of the 2002
ACM SIGGRAPH/Eurographics symposium on Computer
animation (San Antonio, TX, USA, 2002), ACM Press,
pp. 73–80.
[DTKT93] DALDEGAN A., THALMANN N. M., KURIHARA T.,
THALMANN D.: An integrated system for modeling, animating and rendering hair. Computer Graphics Forum,
12, 3 (1993), 211–221.
[Har07] HARADA T.: Real-time rigid body simulation on
GPUs. GPU Gems 3, Chapter 29 (2007), 123–148.
[HMT01] HADAP S., MAGNENAT-THALMANN N.: Modeling dynamic hair as a continuum. Computer Graphics Forum, 20,
3 (2001), 329–338.
[MHHR07] MÜLLER M., HEIDELBERGER B., HENNIX M.,
RATCLIFF J.: Position based dynamics. J. Vis. Comun. Image Represent., 18, 2 (2007), 109–118.
[MHTG05] MÜLLER M., HEIDELBERGER B., TESCHNER M.,
GROSS M.: Meshless deformations based on shape matching. In SIGGRAPH ’05: ACM SIGGRAPH 2005 Papers(Los Angeles, CA, USA, 2005), ACM Press, pp. 471–478.

References[AUK92] ANJYO K., USAMI Y., KURIHARA T.: A simple
method for extracting the natural beauty of hair. In SIGGRAPH ’92: ACM SIGGRAPH 1992 Papers (Chicago,
IL, USA, 1992), ACM Press, pp. 111–120.

[MSW*09] MCADAMS A., SELLE A., WARD K., SIFAKIS E.,TERAN J.: Detail preserving continuum simulation ofstraight hair. In SIGGRAPH ’09: ACM SIGGRAPH 2009
Papers (New Orleans, LA, USA, 2009), ACM Press,
pp. 1–6.

[BAC*06] BERTAILS F., AUDOLY B., CANI M.-P., QUERLEUX B.,
LEROY F., LÉVÊQUE J.-L.: Super-helices for predicting the
dynamics of natural hair. In SIGGRAPH ’06: ACM SIGGRAPH 2006 Papers (Boston, MA, USA, 2006), ACM
Press, pp. 1180–1187.

[OKN09] OHTA M., KANAMORI Y., NISHITA T.: Deformation and fracturing using adaptive shape matching withstiffness adjustment. In Comput. Animat. Virtual Worlds(2009), vol. 20, John Wiley & Sons, Ltd., Het Trippenhuis,
Amsterdam, The Netherlands, pp. 365–373.

[BFA02] BRIDSON R., FEDKIW R., ANDERSON J.: Robust treatment of collisions, contact and friction for cloth animation.
In SIGGRAPH ’02: ACM SIGGRAPH 2002 Papers (San
Antonio, TX, USA, 2002), ACM Press, pp. 594–603.

[Osh07] OSHITA M.: Real-time hair simulation on GPU witha dynamic wisp model. In Comput. Animat. Virtual Worlds(2007), vol. 18, John Wiley & Sons, Ltd., Hasselt, Belgium, pp. 583–593.


c 2010 The Authors
c 2010 The Eurographics Association and Blackwell Publishing Ltd.
Journal compilation 

W. Rungjiratananon et al. / Chain Shape Matching for Simulating Complex Hairstyles[PCP02] PLANTE E., CANI M.-P., POULIN P.: Capturing thecomplexity of hair motion. Graphical Models (GMOD),64, 1 (2002), 40–58.
[Pro95] PROVOT X.: Deformation constraints in a massspring model to describe rigid cloth behavior. In Graphics Interface ’95. W. A. Davis and P. Prusinkiewicz(Eds). Canadian Human-Computer Communications Society, Quebec, Quebec, Canada (1995), pp. 147–154.
[RCT91] ROSENBLUM R. E., CARLSON W. E., TRIPP 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] RIVERS A. R., JAMES D. L.: FastLSM: fast lattice
shape matching for robust real-time deformation. In SIGGRAPH ’07: ACM SIGGRAPH 2007 papers (San Diego,
CA, USA, 2007), ACM Press, pp. 82–87.
[SLF08] SELLE A., LENTINE M., FEDKIW R.: A mass springmodel for hair simulation. In SIGGRAPH ’08: ACM SIG-

9

GRAPH 2008 papers (San Diego, CA, USA, 2008), ACM
Press, pp. 1–11.
[TB08] TARIQ S., BAVOIL L.: Real time hair simulation andrendering on the GPU. In SIGGRAPH ’08: ACM SIGGRAPH 2008 talks (San Diego, CA, USA, 2008), ACM
Press, p. 1.
[VMT06] VOLINO P., MAGNENAT-THALMANN N.: Real-timeanimation of complex hairstyles. IEEE Transactions on
Visualization and Computer Graphics, 12, 2 (2006), 131–
142.
[WBK*07] WARD K., BERTAILS F., KIM T.-Y., MARSCHNER S.
R., CANI M.-P., LIN M.: A survey on hair modeling: styling,simulation, and rendering. IEEE Transactions on Visualization and Computer Graphics (TVCG), 13, 2 (2007),
213–234.
[YK08] YUKSEL C., KEYSER J.: Deep opacity maps. Computer Graphics Forum (Proceedings of EUROGRAPHICS
2008), 27, 2 (2008), 675–680.


c 2010 The Authors
c 2010 The Eurographics Association and Blackwell Publishing Ltd.
Journal compilation 