Last modified 25 August 2003 by jdavis@math.wisc.edu
Inherits from SMKTree : SMKBinaryTree : NSObject
Conforms to NSCoding, NSCopying, SMKDrawing
In the SMea Kit, scene trees are made up of SMKSceneTrees. Each SMKSceneTree node stores an SMKTransformation (which consists of a rotation and a translation) and something that draws. If one or the other is not needed in a node, then it can be left nil. SMKSceneTree offers a few inverse kinematics methods to help coordinate the transformations in various nodes.
Drawing is performed by an attached object called the "drawer", not to be confused with the interface widget NSDrawer. We require only that this object conform to the SMKDrawing protocol.
- (id)setDrawer:(id <SMKDrawing>)drawer;Sets the drawer, retaining it.
Returns the receiver's drawer.
In fact, SMKSceneTree itself conforms to SMKDrawing. When it receives a useResourceManager: message, it passes it on to every drawer in its tree. When it receives draw, it draws the entire tree recursively, by transforming and drawing each node. It responds to select similarly, pushing selection names onto the OpenGL name stack to reflect the tree structure. (See Example 3 in the SMKTester documentation for an idea of what goes on.)
The boundingRadius method recursively computes the bounding radius of the scene tree. This is the radius of the smallest sphere, centered at the origin of the root node, that contains the whole tree. It is a crude estimate of how big the tree is, but it has the advantage of being rotation invariant; that is, it does not depend on the rotations in the tree. This is desirable, because rotations typically change frequently, and we don't want to recompute the bounding radius every time they do. On the other hand, changes in the tree's structure, its drawers, and its translations do affect the bounding radius.
The rest of SMKSceneTree deals with transformations. These methods access the transformation in a node:
- (id)setTransformation:(SMKTransformation *)transformation;Sets the transformation, retaining it.
Returns the receiver's transformation.
A path through a scene tree forms a chain of nodes. Each node has a local coordinate frame; the relationship between it and the global coordinate frame is determined by the transformations in earlier nodes. By the end point of the chain, we mean the origin of the last node, expressed in global coordinates. A common inverse kinematics problem is that of rotating the elements in a chain so that the chain's end point is at a specified global target point.
For simplicity, we assume that the origin of the first node in the chain is at the global origin. Also, if the target is too far away, then we settle for rotating the elements so that the chain points toward the target.
The next two methods solve this problem by an iterative numerical procedure sometimes called cyclic coordinate descent. The path consists of the receiver and some other nodes listed in an NSArray. Because the receiver is assumed to be at the global origin, the end point should be inversely transformed by higher transformations and the receiver's translation before these methods are employed.
- (id)makeEndOfPath:(NSArray *)path startingAtIndex:(unsigned int)index rotateToTarget:(double *)target withResult:(double *)end;Attempts to place the origin of the last node in the path at the indicated target, by calling makeVector:rotateToVector:withResult: on each node's transformation, from (near) the end of the path to the beginning. The path is assumed to start at the starting index; for example, a starting index of 1 causes the first node in the path to be ignored (so the second node needs to be a child of the receiver). This method outputs the actual location to which the end of the path is rotated. The output may alias the input.
Iterates makeEndOfPath:startingAtIndex:rotateToTarget:withResult: until the desired tolerance is achieved or the allowed iterations are used up. This method returns the actual error achieved.
Cyclic coordinate descent seems to enjoy numerical stability and rapid convergence in most cases. On the other hand, it sometimes fails entirely. For example, if every element in the chain starts off pointed directly at the target, then the algorithm might not move it at all. Even when the algorithm succeeds, the end of the chain sometimes ends up rotated more than one might desire; you can prevent this by imposing constraints on the second-to-last transformation.
Now we consider an important special case of the inverse kinematics problem just described. Suppose the path is of length two, so that it contains three nodes, including the root. The composition of their transformations is T0R0T1R1T2R2, where T denotes translation and R rotation. Since we're concerned with only the location of the last node's origin, the rotation R2 is irrelevant. Again, it is assumed that the receiver is at the global origin; so, without loss of generality, T0 is zero. We need to determine R0 and R1.
Suppose also that this "planarity condition" is satisfied: The translations T1 and T2 are parallel, the rotation R1 is about a single axis, and this axis is perpendicular to T1 and T2. For example, this condition is satisfied if the translations are both purely in the Z direction and the rotation is about the X or Y axis.
In this situation, it is easy to determine what R1 should be, and then a single call to makeVector:rotateToTarget: configures R0. Assuming that this method succeeds, the inverse kinematics problem is solved exactly, in just one step.
- (BOOL)makeNode:(SMKNode *)joint andNode:(SMKNode *)end rotateToTarget:(double *)target;Rotates the receiver and joint so that the origin of end is placed at the indicated target, returning YES if and only if successful. In the process, makeVector:rotateToTarget: is invoked on the receiver's transformation, and setPlanarAngle: is invoked on joint's.
Although this problem might sound artificial, it is precisely what is needed to pose a human leg (or arm) so that its ankle (wrist) is at a specified target. The knee (elbow) is a hinge joint, and the planarity condition is quite reasonable.