A COMPLETE ALGORITHM FOR REAL-TIME SPLINE-BASED
Martin D. Hash
The quest for visual realism in real-time includes both shape and movement. Model scalability has received much attention but with relatively little consideration given for animating surfaces. Personal computer hardware will soon reach the performance levels where real-time, visually attractive character animation is possible on the Internet. First instituted in a commercial product in 1987, this paper presents an entire technology for real-time, photorealistic simulation which includes a method of subdividing Bezier spline models that maintain their connectivity information during animation, and a method of applying and reusing motion on those models.
Keywords: Spline mesh, real-time patch subdivision, flatness testing, reusable motion.
Surface representation technology and animation are tightly integrated. In this example, a Bezier spline mesh represents a surface that is composed of perimeter-only spline patches, but these are not Bezier patches since there are no traditional "twist" vectors, nor basis matrix [Farin88]. Instead, solving the patch uses a geometric rather than analytic solution. The patches recursively subdivide into halves, linearly interpolating to obtain interior control points.
Closeup showing p1-p16 identification
Adjoining patches with different levels of subdivision will exhibit cracking unless a heuristic is used which uses a "flat enough" criteria to determine when a cubic spline can be approximated by a line. For real-time operation, the speed of both the flatness check and resulting line substitution is critical.
The cubic is assumed to be parameterized in t:
(1-t)^3 * p0 + 3 * (1-t)^2*t * p1 + 3 * (1-t)*t^2 * p2 + t^3 * p3.
Since the 2nd derivative of an equation determines its instantaneous flatness, for "s" curves, two 2nd derivative evaluations occur at t = 1/3 and t = 2/3.
2nd derivative of bezier formula:
(-6t+6)*p0 + (18t-12)*p1 +(-18t+6)*p2 + 6t*p3
1/3: 4 * p0 - 6 * p1 + 2 * p3
2/3: 2 * p0 - 6 * p2 + 4 * p3
(t is chosen to be 1/3 and 2/3 because at these special values there are only three vector multiplies, and their simple addition is close to a t = 1/2 evaluation).
The norm of the result of 1/3 is then checked against a constant "straight enough" term. If it exceeds this value, the check returns "TRUE" - there should be a split. Otherwise, the 2/3 value is evaluated and the summed results of their norms is checked against "straight enough".
For a "c" curve, only a single 2nd derivative
evaluation needs checking a t = 1/2.
1/2: 3*(p0 - p1 - p2 + p3)
The norm of the result of this equation is similarly checked against "straight enough".
If any evaluation is deemed to be straight enough, the cubic
is then flattened to prevent cracking between adjoining
p0 = p0
p1 = p0 + (p1-p0).Norm() * (p3-p0).Normalize()
p2 = p3 + (p2-p3).Norm() * (p3-p0).Normalize()
p3 = p3
(Since surface splitting is recursive in nature, each half checking whether another split is required, the time expensive "MakeFlat" code need not be performed on the last split).
"s" and "c" curves also exhibit dissimilarities when their
normals are to be found. For speed, "c" curves linearly average
the normals at the cubic endpoints, n0 and n3, even though a
true solution would be quadratic, but empirical evidence
suggests this is adequate.
ncenter = (n0 + n3)/2
"s" curves, however, need a much more time expensive
1st derivative calculation at t = 1/2, that is then
doubly crossed with the averaged ncenter normal.
tcenter = 3 * p0 - 3 * p1 - 3 * p2 + 3 * p3
ncenter = (n0 + n3)/2 X tcenter
ncenter = ncenter X tcenter
Texture parameters, u and v, are simply halved when their
associated spline is split.
ucenter = (u0 + u3)/2
vcenter = (v0 + v3)/2
For speed, once an "s" is turned into two "c" curves, a flag is set to indicate to subsequently perform the "c" type flatness test and normal calculation.
Bezier spline splitting is a simple de Casteljau operation [Coons64].
When the skeletal armature inside a character moves, the encompassing spline mesh needs to bend accordingly. This means tangents must be recomputed to best match the new layout. Spline control points that are affected by the skeletal movement are flagged for re-evaluation, and since a single control point affects all control points that are related (up to two away), this means a single control point will often affect twelve surfaces, and possibly more.
The default tangent direction of a control point is
determined by the control points to either side of it.
d = (pnext - pprev).Normalize()
The default tangent magnitude is determined by the two ends of the spline it defines.
m = (pnext - p).Norm()/2
Obviously, the tangents where the two surfaces meet is C0 (continuous in slope), but not C1 (continuous in magnitude). This discrepancy is essential for animation.
By embracing the simple nature of this surface definition, all subsequent computations are simplified, bringing a robust, fully animatable, visually real simulation to real-time.
This surface definition robustly supports u-v texture mapping through a process very similar to the one described for solving the surface. Each patch has a list of the texture maps that occupy it. These texture maps include their original, twelve control point anchoring information (called "platts"), that are split simultaneously as the patch is split. The coordinates are normalized in x and y (but not z) so that different sized maps can use the same anchoring information. Rendering implementations that do not support multiple maps can have their maps coalesced and saved on a per patch basis. Similarly, implementations that are speed critical can also pre-calculate a single map per patch.
Projection mapping techniques; like spherical, cylindrical, and planar, are supported as long as the rendering implementation is available.
Magnitude and bias values are relative to the geometry, so that as an elbow bends, they can remain constant even though the tangents need recalculated. The default tangent magnitude is considered to be "1"; therefore a value of "2" would be twice as long. Biases are measured in degrees for readability. The default "alpha" bias (perpendicular to the surface’s face) is "0". Alpha changes flatness of the surface. The default "gamma" bias (parallel to the surface’s face) is "0". Gamma changes the contour of the surface.
Relative tangents, while essential for smooth animation, are time expensive to compute. Only the tangents that need to be recalculated are flagged, but the calculations do not actually occur until the surface is ready for use (called "lazy evaluation"), since many things may affect the same control point simultaneously. For example, usually five control points need recalculation when one control point moves due to connectivity. Therefore the current control point’s evaluation needed flag is immediately cleared after calculation so that it is not triggered again during the recursive updating of other control points. In fact, most calculations are better performed lazily for optimum efficiency.
Movement of individually specified control points is called "muscle" motion, since it is most commonly used for facial animation. Control points are uniquely identified by different indexes. Muscle motion is quickly matched to the identification index and applied to the control points’ position, magnitude, or bias (or all three). Due to lazy evaluation, this causes no additional tangent calculation expense should the control points also be affected by skeletal or other motion.
Because the surfaces defined by the Bezier spline mesh have only perimeter control points, there is no interior curvature other than that caused by perimeter curvature. Therefore, if the perimeter is deemed to be flat enough, the resulting surface can be culled from further rendering consideration simply by checking to see if the four corner normals are facing away.
A major concern of real-time characters is resolution isolation. An efficient model should have only the resolution needed in a particular area. For example, the back of a character’s head may be sparsely defined while the face has tremendous detail in the eyes, nose, and mouth. Likewise, where hands connect to forearms, and muscled chests connect to hips, also need to reduce resolution dramatically. "Hooks" are an implementation of as-needed resolution. Hooks are a technique whereby a single patch connects to several patches along a shared edge. For example, two patches may abut a single patch without cracking, even during animation. Hooks achieve this feat by matching the single surface’s tangent at the connection point.
tangent = (lefttangent + righttangent)/2
The last fundamental model construction paradigm is the 5-point patch. Where appendages connect to a character’s torso, the resulting joint leaves multiple topological difficult regions distinguished by five perimeter splines rather than four. A special solution is required to extrapolate these complex surfaces. Essentially, a 5-point patch is divided into five 4-point patches all sharing a single centralized, contrived control point, similar to [Chiyokura86] but without using Gregory patches. (Three perimeter spline regions have a similar, though less used, solution).
For increased detail while retaining a sparse topology, displacement maps can be efficiently implemented. The surface is forced to subdivide beyond its simple "flat enough" criteria, but instead divides until the displacement resolution is reached; the intermediate corner placements can use either algorithmic or texture map information.
By naming bones in the skeletal hierarchy and matching motion based on the name, actions that were made for another character can be reused on different characters, even though the two skeletal layouts are not exactly the same.
Movement is specified as a cubic function of time. Therefore, the curve can be evaluated at any fractional time value, making it possible to vary the frame rate of reusable actions, or to sample at variable frame rates caused by the vagrant redraw times, ensuring smooth motion.
The commercial product, "Animation:Master", has one of the largest installed bases of customers who do computer animation, both amateur and professionally. Literally thousands of finished vignettes are completed yearly. The tool has proven itself robust and easy to use, with examples on display at www.hash.com. The resulting description files, converted to binary, easily migrate to the Internet.
Conclusion and Summary
Processors that implement vector operations, and that can fit the patch splitter into their on-board cache, will benefit greatly from techniques described here. Combined with videocards that can access bus memory for texture maps, and have rendering features such as; bump maps, specular highlights, "immediate mode" lighting, and high resolutions, scalable, animating characters in real-time can be achieved.
These techniques for dealing with a parametric surface may seem simple compared to NURBS and other previously documented techniques, however, this solution’s elegance comes from its simplicity, and for real-time, simplicity equates to speed.
Although there is no direct cubic function s(u,v) that evaluates a point on the surface of this patch, the binary splitting nature of the patch lends itself well to space partitioning algorithms used for ray tracing, view culling, and collision detection.
Appendix: End Tangent Calculation
This part describes how to calculate the input tangent into P2, if P2
is the end point on a spline P2, P3, P4, P5, etc.
float Vector.Norm() = length of vector;
void Vector.Normalized() = normalized vector
Vector * Vector represents dot product
T3 (P2’s new input tangent)
Length from P2 to P3
L1 = (P3-P2).Norm()
L1's length along line segment P2 P4
T1 = (P4-P2).Normalized() * L1
T1 Projected onto line segment P2 P3
T2 = ((T1-P2) * (P3-P2).Normalized()) * (P3-P2).Normalized()
The mirror of T1 across P2 P3
T3 = T2 + (T2-T1)
Cos A1 = (P3-P2) .Normalized() * (T3-P2).Normalized()
Cos A2 = ((P2+P4)/2 - P3).Normalized() * (P2-P3).Normalized()
If A1 > A2 (cos A1 < cos A2_) We must cap A1’s angle
This is the new location of T3. We found by capping the angle of A1, to be no larger than A2, it significantly helped the appearance of the spline. One of our goals of calculating the new tangent (T3) was to preserve its distance from P2, which is L1. If angle A1 is greater than angle A2, then an easy way to adjust T3 so that A1 is the same as A2 is to use the normalized vector A2 to the midpoint of P2P4 and multiply by it the length L1 and add it to P2. This is guarateed to make angle A1 the same as A2 because they are opposite angles of an intersection between two parallel lines.
[Farin88] G. Farin. Curves and Surfaces for Computer Aided Geometric Design 213-215. Academic Press, California, 1988.
[Hosaka84] M. Hosaka and F. Kimura. Non-four-sided patch expressions with control points. Computer Aided Geometric Design 1(1): 75-86, 1984.
[Coons64] S. Coons. Surface for computer aided design. Technical report, MIT, 1964. Available as AD 663 504 from the National Technical Information Service, Springfield, VA 22161.
[Chiyokura86] H. Chiyokura, Solid Modeling with Designbase, Theory and Implementation. Addison Wesley, New York, 1986.