Method and apparatus for approximating hair and similar objects during animation
View Patent ↗Simulating dynamics (e.g., physical effects of inertia, forces, wind) on strands (e.g., hair) during computer based animation requires quick and accurate approximations of mathematical curves. Each strand is initially represented as a B-spline curve. Line segments approximating the curve are created by using affine combinations based on the curve's control vertices. Dynamics simulation is performed on the line segment approximation. Once an approximated strand is simulated, it is converted back into a B-spine curve representation for downstream processes, such as rendering. The rendering process displays the simulated strand to the animator.
1. A computer-implemented method for depicting freeform curves comprising the acts of:
receiving a plurality of data structures associated with a first curve, wherein the first curve is a freeform curve;
computing, using a processor, a first plurality of line segments to approximate the first curve by evaluating an affine combination, wherein a plurality of the computed first line segments are approximately equal in length to their respective portions of the first curve;
providing the computed first line segments to an animation process, wherein the computed first line segments are to be animated by the animation process;
receiving a second plurality of line segments from the animation process, wherein the second plurality of line segments is based on the computed first line segment and the animation process;
computing, using the processor, a second curve to approximate the second plurality of line segments by solving a linear system of equations,
wherein the second curve is a freeform curve,
wherein a plurality of segments of the computed second curve are approximately equal in length to their respective line segments, and
wherein the linear system of equations comprises a tridiagonal matrix defined by the affine combination; and
causing a display of the computed second curve.
2. The method of claim 1 , wherein the plurality of data structures corresponds to a first plurality of control vertices associated with the first curve.
3. The method of claim 2 , wherein each control vertex is defined as a plurality of points in affine space.
4. The method of claim 2 , wherein each control vertex is defined as a plurality of vectors.
5. The method of claim 1 , wherein the first curve is an uniform B-spline curve.
6. The method of claim 1 , wherein the animation process involves dynamics simulation of the computed first line segments.
7. The method of claim 1 , wherein the computed second curve is an uniform B-spline curve.
8. The method of claim 7 , wherein the computed second curve is associated with a second plurality of control vertices.
9. The method of claim 8 , wherein each control vertex is defined as a plurality of vectors.
10. The method of claim 8 , wherein each control vertex is defined as a plurality of points in an affine space.
11. The method of claim 1 ,
wherein the first curve is an uniform B-spline curve,
wherein the plurality of data structures corresponds to a first plurality of control vertices associated with the first curve,
wherein the computing of the first plurality of line segments comprises evaluating the affine combination based on the first plurality of control vertices, and
wherein the total number of line segments in the first plurality of line segments is based on the total number of data structures in the plurality of data structures.
12. The computer-implemented method of claim 11 , wherein the first curve is associated with a strand of hair of a computer-animated character.
13. A non-transitory computer-readable storage medium comprising instructions configured to be executed at a computer and to cause the computer to depict freeform curves, the instructions comprising:
receiving a plurality of data structures associated with a first curve, wherein the first curve is a freeform curve;
computing a first plurality of line segments to approximate the first curve by evaluating an affine combination, wherein a plurality of the computed first line segments are approximately equal in length to their respective portions of the first curve;
providing the computed first line segments to an animation process, wherein the computed first line segments is to be animated by the animation process;
receiving a second plurality of line segments from the animation process, wherein the second plurality of line segments is based on the computed first line segment and the animation process;
computing a second curve to approximate the second plurality of line segments by solving a linear system of equations,
wherein the second curve is a freeform curve,
wherein a plurality of segments of the computed second curve are approximately equal in length to their respective line segments, and
wherein the linear system of equations comprises a tridiagonal matrix defined by the affine combination; and
causing a display of the computed second curve.
14. The computer-readable storage medium of claim 13 ,
wherein the first curve is an uniform B-spline curve,
wherein the plurality of data structures corresponds to a first plurality of control vertices associated with the first curve,
wherein the computing of the first plurality of line segments comprises evaluating the affine combination based on the first plurality of control vertices, and
wherein the total number of line segments in the first plurality of line segments is based on the total number of data structures in the plurality of data structures.
15. The computer-readable storage medium of claim 14 , wherein the first curve is associated with a strand of hair of a computer-animated character.
16. An animation system for depicting freeform curves, comprising:
a memory for storing a plurality of data structures, wherein at least a subset of the plurality of data structures is associated with a freeform curve;
an input processor coupled to the memory, and which calculates a first B-spline curve from the freeform curve;
an affine coefficient calculator connected to the memory and the input processor, and which calculates a plurality of affine coefficients for approximating the first B-spline curve;
a strand approximator coupled to the memory and the affine coefficient calculator, and which computes a first plurality of line segments to approximate the first B-spline curve,
wherein the first plurality of line segments are approximately equal in length to their respective portions of the first B-spline curve,
wherein the computing a first plurality of line segments comprises evaluating the plurality of affine coefficients;
a dynamics simulator coupled to the memory and the strand approximator, and which changes each first plurality of line segments each into a second plurality of line segments;
a B-spline converter coupled to the memory and the dynamics simulator, and which computes a second B-spline curve to approximate the second plurality of line segments by solving a linear system of equations,
wherein the linear system of equations comprises a tridiagonal matrix defined by the plurality of affine coefficients; and
a rendering component coupled to the memory, the B-spline converter, and which depicts the computed second B-spline curve.
17. The system of claim 16 , wherein:
the first curve is an uniform B-spline curve,
the subset of data structures corresponds to a first plurality of control vertices associated with the first curve,
wherein the computing of the first plurality of line segments comprises evaluating the affine combination based on the first plurality of control vertices, and
wherein the total number of line segments in the first plurality of line segments is based on the total number of data structures in the plurality of data structures.
18. The system of claim 17 , wherein the first B-spline curve is associated with a strand of hair of a computer-animated character.