From BlenderWiki
Design Overview and Roadmap for Hair Simulation
Proposal Summary
We propose to implement a new system for rendering, simulating and animating hair. The paramount requirement is stability and animator control.
The proposed hair structure works on 3 levels, each designed for one of the areas mentioned (animator tools/simulation/rendering). The amount of detail increases with each level, making animation feasible with as few keyframed points as possible, while giving enough data for simulation and greater detail in rendering.
The primary targeted renderer is Cycles. Generating of render data is largely handled inside the hair code and can be adopted later in Blender Internal or other renderers using the same consistent functions.
The basic simulation model is a mass-spring system, where each hair is represented by a chain of vertices, each connected to its neighbors by "springs" to control stretching and bending. Subdivision of (parts of) the time step allows stable simulation even with stiff springs for inelastic hair.
Collision detection between hairs and meshes should make use of optimized algorithms implemented by the Bullet physics engine. The more expensive hair-hair collision model could use either extensive pruning methods ([]) or a cheaper volume-based approach.
Grooming tools of the current particle-based hair system can be ported and extended when necessary. Simulation features may require some modifications to existing tools, which were designed for mostly static grooming.
Roadmap
Bullet API cleanup
Make sure the rigidbody API connecting Blender code to the Bullet engine works reliably for hair and supports non-object rigid bodies and collision objects.
Required time estimate: ? days
Force Fields Influence
Hair forces don't include external standard force fields yet.
Required time estimate: ? days
Point Caching
Extend the point cache format to support hair data.
Required time estimate: ? days
Hair-Hair Collision
As a usable alternative to the much more complicated and costly hair pruning algorithm, a volume-based voxel method would be preferable at first. It could be replaced or complemented at some later point.
Required time estimate: ? days
Child Hair Tweaks
Add features for distributing and shaping render hairs on top of the simulation hairs. A lot of different features can be implemented here, but existing particle hair options would have priority. Hair curling could work well on this level, as well as clumping, braids, dreadlocks, ...
Omitting the interpolation method for child hairs could speed up the process, and is probably not needed at this stage.
Required time estimate: ? days
Guide Hair Interpolation
To implement the first of the three mentioned hair levels (guide/simulation/render) we need to specify certain hairs as guide hairs. In edit mode only these hairs would be editable and/or displayed (much like current parent/child hair dichotomy). Editing guide hairs affects only their rest positions. Rest positions of all other simulation hairs are then interpolated like child hairs in the current particle hair.
Guide hairs could be enabled/disabled quite freely among existing simulation hairs (although sudden jumps in rest positions could be the result).
Required time estimate: ? days
Hair Edit Operators
The current operators for grooming work quite nicely and should be adapted to support the new hair data.
Additional operators may be invented for different kinds of data (e.g. per-hair curl settings). However, this should be decided on a per case basis when the need arises.
Required time estimate: ? days
Cycles Shader Attributes
A few attributes for Cycles shaders are still missing in the hair data conversion, in particular UV mapping of root locations and vertex color maps.
Required time estimate: ? days
Effectors Optimization
Implement an efficient way of evaluating force fields for many points. The current "effectors" implementation is terribly slow, due to using linked lists of effectors and inefficient copying of simulation data. Much more optimized implementations are possible here.
Required time estimate: ? days
Design
Hair Levels
Comparison
The current hair system works basically on 2 levels: Guide hairs and Child hairs. Few guide hairs is nice for grooming a character, but simulation is hardly usable then because most visible hairs are simply interpolated. More guide/simulated hairs on the other hand make accurate grooming much more tedious. For an example see the "Koro" character by Pablo Vasquez.
|
To alleviate this problem the hair structure should use animated guide hairs only to define the rest position of hairs. This rest position is the shape and orientation of a hair in which it would remain perfectly still (as long as no external forces like gravity are present).
More hairs can be interpolated between these primary guide hairs to improve simulation results. This would use the same interpolation method as the current child hairs, but only define the rest positions, while the actual deformation is defined by the simulation.
Data Structure
A mass-spring based model appears to be the most suitable for the purposes of 3D animation. Other mathematical models have been examined, but have limitations that outweigh their advantages:
- "Super-Helices" offer a lot of visual detail for little memory, but are computationally expensive [1]
- "Oriented Strands" are more stable, but prevent all stretching and are more difficult to implement [2] (section 1.3)
Our approach instead follows the method outlined in [3]. Parts of the original method may be omitted or replaced, but the basic principle has been proven to work in production and is comparatively easy to implement.
A hair system is a collection of individual hairs. These hairs in turn consist of a sequence of points (a hair curve), each of which has a number of settings and a motion state (location, velocity). Each hair point also has a rest position that defines an animatable target for the simulation.
Every hair curve has an assigned root mesh point that indirectly connects it to a mesh object. Such mesh points can be evaluated on deforming meshes to yield an animated location, normal and tangent on the mesh surface, which defines the changing orientation of the hair.
Mesh Point Sampling
The mesh sampling system defines a consistent way of maintaining a stable point on animated and deforming meshes. It is separate from the hair system so that it can be used in other contexts, such as particle systems (which currently have a lot of issues with emitter locations). Tools can be created to enabled user-defined hair distributions easily without having to create extra texture mapping and the like (unless desired).
|
Rendering
The amount of data in animated and simulated hairs is comparatively low (it is technically not feasible to simulate each hair on a typical human head or animal fur coat, let alone multiple characters). The full detail of hair is generated only for rendering and display purposes. To render a plausible amount of hair, additional child hairs have to be generated from simulation data. Child data is generated on-the-fly by the hair system on request from a renderer. This allows the logic for child hair distribution and shaping to remain inside the hair system instead of having to be implemented by all renderers.
The display system can use the same data as renderers for consistency. Since the amount of child hairs can be difficult to display in realtime the render data can be simplified by reducing child hair counts and interpolation steps for realtime display.
Additional detail such as curling and clumping can be added to the child hairs. This simulates the natural tendency of hairs to stick together in wisps, particularly in curly hair which tends to form self-supporting strands.
Two distribution methods for child hairs have already been implemented in the current particle hair system, namely children grouped around the parent ("simple") and children interpolated between multiple parents ("interpolated"). The latter approach can potentially add unwanted artifacts when two or more unrelated simulation hairs are interpolated, so for child hairs the grouping approach would be preferable. Interpolation could instead be more useful when expanding from the guide hair level to simulation hairs (see Hair Levels).
Solver
The hair simulation uses a semi-implicit Euler solver [4]. This solver has the very desirable property of good energy conservation, making spring systems such as our hair model much more stable than e.g. the basic Euler method.
In addition to the main integration step a viscous damping step is performed on the point velocities. This is an important feature to stabilize the simulation further, in particular in the case of stiff stretching springs that are needed for realistic hair simulation.
The overall timestep is divided into a number of sub-loops to increase stability further. Velocities and locations are updated in multiple small increments per collision detection step ([3] mentions a typical amount of 30 or 60 force substeps depending on complexity). Damping happens in yet another sub-loop due to its tendency to destabilize stiff springs (typically another factor of 10). All these steps are relatively cheap compared to collision detection, so adding sub-steps is not the main influence on performance.
Collision
Collision for hair systems can be divided into two main categories:
- Hair-Object collision
- Hair-Hair collision
Detecting collisions can also be somewhat separated from dynamic response of the colliding objects. This allows us to calculate collision pairs once at the beginning of the time step and then use these pairs in the more fine-grained integration steps that follow.
Hair-Object collision
The collision model described in [3] calls for representing hair points by spheres. The radius of each sphere models the width of a hair strand or wisp at that point (a property that should be directly reflected in child hair distribution during rendering).
For detecting collisions the Bullet physics engine provides a wealth of optimized methods and good performance. Bullets second mainstay is the dynamic response between colliding rigid bodies, but this part is not very helpful for hair simulation. One possible approach (already implemented) to detect hair-object collisions is to create a "Ghost Object" for the hair system and then check for potential collisions with each of the hair point spheres. Another option could be to use the relatively new softbody system in Bullet.
Response to collisions is based on a penalty force formulation. A comprehensive description of a stable response system can be found in [5]. The main idea is to stop a penetrating motion quickly in a single integration step, and then put the colliding objects into a "contacting" state that does not increase vertical velocity. This promises to avoid many stability issues caused by oscillating impact and restitution forces.
Hair-Hair collision
Collisions between hairs are the more challenging collision type, due to the sheer amount of potential contacts.
The approach taken by [3] is to aggressively prune the number of potential contacts prior to actual simulation. This approach also allows threading optimization, since handling collisions requires shared access to data. Pruning collisions allows grouping of hairs into independent groups of hairs that never collide, and so reduces the need for processors to exchange data at synchronization points.
There are other approaches to handle hair-hair collision which may be easier to implement and can handle larger amounts of hairs reasonably well. [6] describes a volumetric approach to summarize the influence of many hairs in a voxel description. A gradient calculated from the scalar density field of hairs provides a way of keeping a hair volume from collapsing without actually calculating large numbers of collision pairs. The price is reduced detail and potential intersection artifacts that may require manual fixing by animators.
Caching
Caching is a necessity for many reasons:
- Realtime playback, while approximatable with reduced data, is not feasible on full simulation settings ([3] gives an example of 20 to 30 seconds calculation per frame for complex characters)
- Exporting scene data and other processes that utilize the full frame range work much better
- Motion blur usually samples an interval (-0.5, 0.5) around the current frame, which requires cached simulation data
- Layered physics simulations (not yet implemented) can treat cached data like keyframe-animated data (e.g.: rain drop particles on hair)
The current point cache implementation, while lacking in many respects, should be sufficient for now and easily extendable to hair. At some point we may want to consider a point cache solution based on Alembic, but this is not a high priority.
[1] http://www-evasion.imag.fr/Publications/2006/BACQLL06/sigFinalHair06.pdf
[2] http://hal.archives-ouvertes.fr/docs/00/52/02/70/PDF/finalcoursenotes2008.pdf
[3] http://graphics.pixar.com/library/CurlyHairA/paper.pdf
[4] http://en.wikipedia.org/wiki/Semi-implicit_Euler_method
[5] http://graphics.snu.ac.kr/publications/2005-choe-HairSim/Choe_2005_SCA.pdf
[6] http://graphics.pixar.com/library/Hair/paper.pdf
