Technique for simulating the dynamics of hair

A simulation engine is configured to generate a physical simulation of a chain of particles by implementing a physics-based algorithm. The simulation engine is configured to generate a predicted position for each particle and to then adjust the predicted position of each particle based on a set of constraints associated with the physics-based algorithm. The simulation engine may then generate a predicted velocity for a given particle based on the adjusted, predicted position of that particle and based on the adjusted, predicted position of an adjacent particle.

BACKGROUND OF THE INVENTION

Field of the Invention

The present invention generally relates to physical simulations and, more specifically, to a technique for simulating the dynamics of hair.

Description of the Related Art

Conventional simulation engines are capable of simulating the dynamics of of a wide variety of physical objects, including polygons, particles, and hair. In order to simulate the dynamics of hair, a conventional simulation engine typically models each strand of hair as a chain of particles. The simulation engine may apply a physics-based algorithm to each particle in a chain of particles in order to update the position of each such particle at a given time step in the simulation. The physics-based algorithm may incorporate various laws of motion, as well as different physical constraints, when updating the positions of particles in the chain of particles.

When simulating hair via the approach described above, the simulation engine typically imposes a distance constraint between particles in the chain of particles in order to ensure that neighboring particles reside a fixed distance from one another. Enforcing distance constraints in this fashion may cause the chain of particles to appear inextensible and therefore more similar to a natural strand of hair.

However, enforcing multiple different sets of constraints can be difficult because updating the position of one particle to meet one set of constraints may end up causing the position of that particle to violate a different set of constraints. Conventional simulation engines work around this problem by iteratively adjusting the position of each particle many times during a given time step until all constraints are met.

The problem with this approach is that applying a physics-based algorithm and associated physical constraints iteratively at every time step of the simulation for every particle in the simulation in order to prevent the hair from appearing stretchy is often computationally intensive, and may result in a very slow physics simulation. Reducing the number of iterations per time step can speed up the simulation but this results in unrealistic looking stretchy hair. Consequently, the simulation of inextensible hair could not be implemented within a real-time physics simulation such as a video game.

Accordingly, what is needed in the art is a more efficient technique for simulating hair in real-time.

SUMMARY OF THE INVENTION

One embodiment of the present invention sets forth a computer-implemented method for generating a physical simulation of a chain of particles, including generating a position prediction for a particle in the chain of particles based on a set of physical rules associated with the physical simulation, generating an adjusted position prediction for the particle based on the position prediction and a set of physical constraints associated with the chain of particles, generating a velocity prediction for the particle based on a first velocity prediction factor associated with the particle and based on a second velocity prediction factor associated with a first neighbor particle residing adjacent to the particle in the chain of particles, updating a current position of the particle on a display device to reflect the adjusted position prediction associated with the particle, and updating a current velocity of the particle to reflect the velocity prediction associated with the particle.

One advantage of the disclosed algorithm is that the position of each particle within the physical simulation may only need to be updated with just one iteration of the algorithm to satisfy constraints associated with each such particle. Accordingly, chains of particles may appear to have zero stretching. The disclosed algorithm may thus be implemented in real-time simulations such as video games.

DETAILED DESCRIPTION

System Overview

FIG. 1is a block diagram illustrating a computer system100configured to implement one or more aspects of the present invention. Computer system100includes a central processing unit (CPU)102and a system memory104communicating via an interconnection path that may include a memory bridge105. Memory bridge105, which may be, e.g., a Northbridge chip, is connected via a bus or other communication path106(e.g., a HyperTransport link) to an input/output (I/O) bridge107. I/O bridge107, which may be, e.g., a Southbridge chip, receives user input from one or more user input devices108(e.g., keyboard, mouse) and forwards the input to CPU102via communication path106and memory bridge105. A parallel processing subsystem112is coupled to memory bridge105via a bus or second communication path113(e.g., a Peripheral Component Interconnect (PCI) Express, Accelerated Graphics Port (AGP), or HyperTransport link); in one embodiment parallel processing subsystem112is a graphics subsystem that delivers pixels to a display device110that may be any conventional cathode ray tube, liquid crystal display, light-emitting diode display, or the like. A system disk114is also connected to I/O bridge107and may be configured to store content and applications and data for use by CPU102and parallel processing subsystem112. System disk114provides non-volatile storage for applications and data and may include fixed or removable hard disk drives, flash memory devices, and compact disc (CD) read-only-memory (ROM), digital versatile disc (DVD) ROM, Blu-ray, high-definition (HD) DVD, or other magnetic, optical, or solid state storage devices.

A switch116provides connections between I/O bridge107and other components such as a network adapter118and various add-in cards120and121. Other components (not explicitly shown), including universal serial bus (USB) or other port connections, CD drives, DVD drives, film recording devices, and the like, may also be connected to I/O bridge107. The various communication paths shown inFIG. 1, including the specifically named communication paths106and113may be implemented using any suitable protocols, such as PCI Express (PCI-e), AGP, HyperTransport, or any other bus or point-to-point communication protocol(s), and connections between different devices may use different protocols as is known in the art.

In one embodiment, the parallel processing subsystem112incorporates circuitry optimized for graphics and video processing, including, for example, video output circuitry, and constitutes a graphics processing unit (GPU). In another embodiment, the parallel processing subsystem112incorporates circuitry optimized for general purpose processing, while preserving the underlying computational architecture, described in greater detail herein. In yet another embodiment, the parallel processing subsystem112may be integrated with one or more other system elements in a single subsystem, such as joining the memory bridge105, CPU102, and I/O bridge107to form a system on chip (SoC).

Parallel processing subsystem112includes one or more parallel processing units (PPUs) each configured to perform multiple processing operations simultaneously. In one embodiment, each PPU within parallel processing subsystem112is a graphics processing unit (GPU) or a general-purpose GPU. A given PPU may include any amount of local memory and may also be coupled to a global memory also accessible by any of the other PPUs within parallel processing subsystem112. Each PPU may include any number of different processing cores, each such core capable of executing multiple different execution threads simultaneously. A given execution thread may perform graphics-related operations or generic processing operations.

Each PPU within parallel processing subsystem112may also execute a simulation application150that resides in system memory103. When executing simulation application150, a given PPU is configured to generate a physical simulation of one or more chains of particles and to output pixels that represent that physical simulation to a display device. A given chain of particles within the physical simulation could represent, for example, a strand of hair or fur. In one embodiment, simulation engine150may reside within a video game that executes on both CPU102and parallel processing subsystem112, and each chain of particles simulated by a PPU within parallel processing subsystem112may represent a strand of hair or fur attached to a character within that video game.

At each time step in the physical simulation, simulation engine150is configured to update the position and velocity of each particle in a chain of particles within the physical simulation by implementing a physics-based algorithm described below in conjunction withFIG. 2.

Simulating the Dynamics of Hair

FIG. 2is a flow diagram of method steps for simulating a chain of particles, according to one embodiment of the present invention. Although the method steps are described in conjunction with the system ofFIG. 1, persons of ordinary skill in the art will understand that any system configured to perform the method steps, in any order, is within the scope of the inventions. The method steps described below represent the physics-based algorithm implemented by simulation engine150, as mentioned above in conjunction withFIG. 1.

As shown, a method200begins at step202, where simulation engine150generates a position prediction for a particle in a chain of particles. Simulation engine150is configured to generate the position prediction for the particle based on the current position and velocity of the particle at the current time step, a set of forces applied to the particle at the current time step, as well as the length of the time step implemented by simulation engine150for the physical simulation. Simulation engine150may perform step202by applying a set of physical rules to the particle that represent a physical law of motion, such as, e.g., Newton's second law of motion and a time integration scheme such as, e.g., the explicit Euler method. In one embodiment, the chain of particles is attached to another object within the physical simulation by an “anchor” particle residing at one end of the chain of particles. The object to which the chain is attached could be, e.g., a character within a video game configured to implement simulation engine150.

At step204, simulation engine150adjusts the position prediction of the particle by enforcing a set of constraints between the particle and a “previous” particle in the chain of particles. As referred to herein, a “previous” particle is a particle residing adjacent to the particle towards the anchor particle. In one embodiment, simulation engine150adjusts the position prediction of the particle by “moving” that particle towards the previous particle along a line that connects the particle to the previous particle. In this fashion, simulation engine150could “move” the particle until the distance constraint is met.

At step206, simulation engine150generates a velocity prediction for the particle based on the adjusted position prediction generated at step204, the adjusted position prediction of a “subsequent” particle in the chain of particles, a damping factor, and the length of the time step implemented by simulation engine150for the physical simulation. As referred to herein, a “subsequent” particle is a particle residing adjacent to the particle opposite the anchor particle. Simulation engine150may generate the adjusted position prediction of the subsequent particle in the chain of particles by performing steps202and204of the method200with the subsequent particle.

At step208, simulation engine150updates the position of the particle to reflect the position prediction generated for the particle at step202. At step210, simulation engine150updates the velocity of the particle to reflect the velocity prediction generated for the particle at step206. The method200then ends.

Simulation engine150may implement the method200for each particle in a chain of particles in parallel, e.g. on each processing core of a PPU within parallel processing subsystem112, thereby performing each step of the method200for each particle simultaneously. With this approach, the adjusted position predictions for particles could be made available to simulation engine150when computing the velocity predictions of neighboring particles. In general, simulation engine150need only implement the method200once for each particle during a given time step, thereby conferring a significant advantage over conventional techniques that require multiple iterations of physics-based algorithms in order to update the positions of particles.

The approach described above is discussed in greater detail by way of example in conjunction withFIGS. 3A-3D.

FIG. 3Ais a conceptual diagram that represents a chain300of modeled particles, according to one embodiment of the present invention. As shown, chain300includes particles302,304,306, and308that reside at positions312,314,316, and318, respectively. Particle302could be the “anchor” particle, as described above in conjunction withFIG. 2, and as such, may have a fixed position relative to an object within the physical simulation.

At each time step of the physical simulation, simulation engine150computes a position prediction for a given particle based on the position, velocity, and forces applied to that particle during a previous time step, in like fashion as described in conjunction with step202of the method200shown inFIG. 2. InFIG. 3A, particles302,304,306, and308are disposed at position prediction312,314,316, and318, respectively, according to the position prediction generated for each of those particles by simulation engine150. As also shown, particles302and304reside at a distance L1 from one another, particles304and306reside at a distance L2 from one another, and particles306and308reside at a distance L3 from one another. Simulation engine150is configured to adjust the position prediction for each particle in order to meet a set of physical constraints, as discussed in greater detail below in conjunction withFIG. 3B.

FIG. 3Bis a conceptual diagram that represents the chain300of modeled particles, according to one embodiment of the present invention. As shown, particle304now resides at position324, particle306now resides at position326, and particle308now resides at position328. Furthermore, particle304now resides at a distance L0 from particle302, particle306now resides at the same distance L0 from particle304, and particle308also resides at that distance L0 from particle306. As mentioned above in conjunction withFIG. 3A, simulation engine is configured to adjust the position predictions for each particle to meet a set of physical constraints. InFIG. 3B, simulation engine150has adjusted the position predictions shown inFIG. 3Ato meet the physical constraint that each of particles302,304,306, and308reside at a fixed distance L0 from one another, similar to step204of the method200described above in conjunction withFIG. 2.

In one embodiment, simulation engine150processes constraints associated with the chain300of particles in a “top-down” fashion starting with the anchor particle. A given particle is moved on a straight line towards a previous particle in order to satisfy a distance constraint between the particle and the previous particle. This process is performed for each particle in succession, starting from the anchor particle, so that each distance constraint associated with the chain300of particles may be satisfied. Simulation engine150may then generate a velocity prediction for each particle, as described in greater detail below in conjunction withFIG. 3C.

FIG. 3Cis a conceptual diagram that represents the chain300of modeled particles, according to one embodiment of the present invention. As shown, chain300includes particles302,304,306, and308residing at positions312,324,326, and328. Once simulation engine150has adjusted the position prediction of each particle to meet the set of physical constraints, as discussed above in conjunction withFIG. 3B, simulation engine150may then generate a velocity prediction for each particle based on two separate factors.

For a given particle, simulation engine150determines the first velocity prediction factor for that particle based on the distance between the position prediction for the particle (such as that generated by step202of the method200), the adjusted position prediction for the particle (such as that generated at step204of the method200), and the length of the time step implemented by simulation engine150for the physical simulation. The first velocity prediction factor represents the predicted velocity of the particle after traversing the distance between the position prediction and the adjusted position prediction during the time step.

For example, when simulation engine150adjusts position prediction314of particle304, thereby moving particle304to position324, simulation engine150could then compute the first velocity prediction factor for particle304as velocity334. Likewise, when simulation engine150adjusts position prediction316of particle306, thereby moving particle306to position326, simulation engine150could then compute the first velocity prediction factor for particle306as velocity336. Further, when simulation engine150adjusts position prediction318of particle308, thereby moving particle308to position328, simulation engine150could then compute the first velocity prediction factor for particle308as velocity338.

For a given particle, simulation engine150may then compute the second velocity prediction factor for that particle based on the first velocity prediction factor associated with the subsequent particle in the chain of particles as well as a damping factor. For example, simulation engine150may compute the second velocity prediction factor for particle304as the inverse of velocity336(associated with particle306) multiplied by the damping factor, shown inFIG. 3Cas velocity344. Likewise, simulation engine150may compute the second velocity prediction factor for particle306as the inverse of velocity338(associated with particle308) multiplied by the damping factor, shown inFIG. 3Cas velocity346. In one embodiment, the damping factor is a decimal between 0 and 1. For a particle residing at the end of chain300, such as particle308, simulation engine150may not compute the second velocity prediction factor since that particle does not have a subsequent particle.

For a given particle, simulation engine150is configured to compute the velocity prediction for that particle based on the first and second velocity prediction factors described above. In one embodiment, simulation engine150adds the two velocity prediction factors together to generate the overall velocity prediction for a given particle. For example, simulation engine150could compute the velocity prediction354for particle304based on velocities334and344. Likewise, simulation engine150could compute the velocity prediction356for particle306based on velocity336and346. Step206of the method200discussed above in conjunction withFIG. 2describes a general approach for computing the velocity prediction for a given particle.

Once simulation engine150has generated an adjusted position prediction and a velocity prediction for each particle in chain300, simulation engine150may update the position and velocity of each particle in chain300to reflect those adjusted position predictions and velocity predictions, as described in greater detail below in conjunction withFIG. 3D.

FIG. 3Dis a conceptual diagram that represents the chain300of modeled particles, according to one embodiment of the present invention. As shown, particles302,304,306, and308reside at positions312,324,326, and328, respectively. Particles304,306, and308have velocities354,356, and338, respectively. Simulation engine150may update the positions and velocities of particles302,304,306, and308in like fashion as described above in conjunction with steps208and210of the method200shown inFIG. 2. Once simulation engine150has updated the position of each particle in the physical simulation according to the techniques described above, simulation engine150may then generate a set of pixels that represent those particles. Simulation engine150may then output those pixels to a display device, e.g. for display to an end-user.

Those skilled in the art will understand that the example discussed in conjunction withFIGS. 3A-3Drepresents just one possible implementation of the techniques described herein, and that other implementations are also possible.

In sum, a simulation engine is configured to generate a physical simulation of a chain of particles by implementing a physics-based algorithm. The simulation engine is configured to generate a predicted position for each particle and to then adjust the predicted position of each particle based on a set of constraints associated with the physics-based algorithm. The simulation engine may then generate a predicted velocity for a given particle based on the adjusted, predicted position of that particle and based on the adjusted, predicted position of an adjacent particle.

Advantageously, the simulation engine is capable of updating the position of each particle within the physical simulation with just one iteration of the physics-based algorithm, thereby allowing that algorithm to be implemented in real-time simulations such as video games.

The invention has been described above with reference to specific embodiments. Persons of ordinary skill in the art, however, will understand that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention as set forth in the appended claims. The foregoing description and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.

Therefore, the scope of embodiments of the present invention is set forth in the claims that follow.