prtdslham

Parallelized Real-TimeDynamic Simulation of Long Hair over Arbitrary Meshes: 

Parallelized Real-Time Dynamic Simulation of Long Hair over Arbitrary Meshes Stuart Golodetz

What is hair simulation?: 

What is hair simulation? Hair simulation is about physically modelling hair and seeing what happens when it is perturbed (by wind, for example). It involves three distinct activities – hair shape modelling, hair rendering and hair dynamics. Hair shape modelling is concerned with how to model hair so that it has the right shape (e.g. short vs. long, straight vs. curly). The other two are self-explanatory.

Why model hair?: 

Why model hair? Two separate questions: we want to model hair both because it’s inherently interesting and because it has similarities to strings, ropes and fibres. We want to model hair because without an appropriate underlying physical representation, rendered hair looks good but can’t do anything interesting.

State Of The Art (1): 

State Of The Art (1) Modelling (particularly rendering) of short hair and fur is getting better all the time (see right). Modelling of longer hair remains a research problem.

State Of The Art (2): 

State Of The Art (2) Current research tends to produce impressive results in specific areas whilst avoiding dealing with others. There are documented approaches based on level-of-detail (LOD) ideas, computational fluid dynamics (CFD) and thin shell volumes (TSVs). Each method has different strengths and weaknesses.

Aims: 

Aims Blue-skies research! The aim is to simulate as much hair as possible, with the greatest possible accuracy and speed. We want to see what happens when the hair is perturbed (e.g. by wind). We want to be able to specify properties of the hair, e.g. length, number density, etc. We want our implementation to be generic and flexible.

Basic Design – Physics: 

Basic Design – Physics We start with the physics kernel. Its purpose is to simulate a number of objects by applying type-specific numerical schemes to update their properties (e.g. position, velocity) from one time-step to the next. The physics kernel does not (and should not) worry about collision detection and response (CDR), which is application-specific and must be dealt with at a higher level.

Basic Design – Physics: 

Basic Design – Physics Each object in our system has a number of key points to which forces (which may vary with the system state) can be applied. The numerical schemes use these forces when calculating how to update the objects. In this design, springs are considered to be force appliers, that is, things which add forces to objects. (Disconnecting a spring would mean removing forces in this context.)

Basic Design – Hair Representation: 

Basic Design – Hair Representation The hairs in our simulation are represented as chains of point masses, connected using linear and angular springs as shown. Linear springs apply a force (along their line of action) to each of the two objects they connect, calculated using Hooke’s Law.

Basic Design – Hair Representation: 

Basic Design – Hair Representation Angular springs are used to prevent the hairs bending too much. They exert forces on points i-1 and i+1 which have a restoring effect on the angle at point i.

Basic Design – Forces: 

Basic Design – Forces We model gravity, wind and (velocity-dependent) air resistance in the obvious way, by applying the relevant forces to each of the point masses which make up the hairs. The air resistance constant was determined empirically. There are (at most) seven forces acting on any one point mass: gravity, wind, air resistance, two linear spring forces and two angular spring forces.

Basic Design – Hair Bases: 

Basic Design – Hair Bases We introduce the concept of a hair base, which generalises heads, meshes, etc. The roots of the hairs are represented as key points on the hair base. A hair is connected to the hair base by connecting the closest point mass to the hair root with a linear spring.

In Detail – The Head Hair BaseRepresentation and Coordinate Systems (1): 

In Detail – The Head Hair Base Representation and Coordinate Systems (1) The head is represented as an ellipsoid. In turn, we represent an ellipsoid as an orthogonal coordinate system, with its centre being the origin of that system. In the case of the head hair base, we call that system the head’s local coordinate system.

In Detail – The Head Hair BaseRepresentation and Coordinate Systems (2): 

In Detail – The Head Hair Base Representation and Coordinate Systems (2) We also define a polar coordinate system (φ, θ) for distributing hair roots. This goes from φ = 0 at the top of the head, to φ = π at the bottom, and from θ = 0 at the right of the head to θ = π at the left. The point (φ, θ) in polar coordinates corresponds to the local coordinate system point (cos θ sin φ, sin θ sin φ, cos φ).

In Detail – The Head Hair BaseHair Root Distribution: 

In Detail – The Head Hair Base Hair Root Distribution To distribute the hair roots over the head, users specify intervals [φlow, φhigh] and [θlow, θhigh] over which hair should be distributed (this allows us to cover the back but not the front of the head, for instance). A uniform grid is generated and then random points are chosen in each grid square according to a user-specified number density function ρ(φ, θ).

In Detail – The Head Hair BaseHair Properties: 

In Detail – The Head Hair Base Hair Properties Hair properties such as length, colour, etc. can be specified as functions of the hair root position (φ, θ). In practice, we tend to borrow an idea from the literature and interpolate user-specified values at the top, bottom, left, right, front and back of the head.

In Detail – The Head Hair BaseCollision Detection: 

In Detail – The Head Hair Base Collision Detection Since we have to simulate large numbers of hairs in real-time, collision detection and response needs to be cheap. We can get acceptable results by simply testing the individual point masses against a slightly expanded head. By keeping the points outside of this, we generally manage to avoid the hairs penetrating the actual head. Using more points provides better accuracy but carries a computational cost.

In Detail – The Head Hair BaseCollision Response: 

In Detail – The Head Hair Base Collision Response When a collision is detected, we simply move the point away from the centre of the head until it’s outside the expanded head. This is unsophisticated, but fast. Our CDR approach provides reasonable results for a stationary head, but if the head can move then a better scheme is required.

In Detail – The Mesh Hair Base: 

In Detail – The Mesh Hair Base Many of our ideas generalise to arbitrary meshes. In particular, I have been simulating a long-haired penguin as a proof-of-concept. Collision detection and response requires additional work, as will be described shortly.

In Detail – The Mesh Hair BaseHair Root Distribution and Properties: 

In Detail – The Mesh Hair Base Hair Root Distribution and Properties The mesh for the penguin was constructed using Blender. The hair root distribution is specified by applying a special material to parts of the mesh which should have hair attached. Hair properties are specified by varying which material is applied.

In Detail – The Mesh Hair BaseCollision Detection: 

In Detail – The Mesh Hair Base Collision Detection We expand the penguin mesh using Blender to form a collision mesh (this can be less detailed). This mesh is then used to construct a BSP tree which we use for collision detection.

In Detail – The Mesh Hair BaseCollision Detection: 

In Detail – The Mesh Hair Base Collision Detection BSP trees (binary space partitioning trees) recursively divide space in two:

In Detail – The Mesh Hair BaseCollision Detection: 

In Detail – The Mesh Hair Base Collision Detection We do our collision detection by recursively testing each hair point object against the BSP tree. Those objects that end up in a solid leaf of the tree (and are therefore inside the penguin) are then subjected to collision response.

In Detail – The Mesh Hair BaseCollision Response: 

In Detail – The Mesh Hair Base Collision Response There is a BSP raycasting algorithm that allows us to find the point at which we first transition from solid to empty space (or vice-versa). We use this to move our penetrating point outside the mesh again. What ray direction to use is non-obvious. The negation of the object’s velocity doesn’t work well. In practice, we try several directions and pick the one which induces the smallest change in position.

In Detail – The Mesh Hair BaseCollision Response: 

In Detail – The Mesh Hair Base Collision Response We don’t want our collision response to change the length of the hair. That would change the sizes of the spring forces being applied and cause instability. We thus apply length constraints to maintain the hair length over collision response.

Rendering Details: 

Rendering Details We render the hairs as cubic splines. To do this, we have to interpolate the point objects at each frame. The interpolation process involves a matrix inversion, but we can cache the inverted matrix for each hair to speed things up. We use OpenGL Shading Language (GLSL) vertex and fragment shaders to get our Phong lighting effects.

HairPen BendCoding for the Cell BE: 

HairPen Bend Coding for the Cell BE IBM are running a student competition to write code for the new Cell BE architecture, which is finding use in Sony’s PS3. It has 1 primary and 8 secondary processors running in parallel. This makes it good for parallelizing simulation code. I am currently in the process of porting the Java code to C++ for my competition entry.

Future Work: 

Future Work The collision detection and response could do with more work. Accommodating hair base movement remains a challenge with this approach. In practice, I’m planning to spend the rest of my DPhil on kidney cancer work, but hair modelling has been really interesting.