[_CDCSL_93-16_]<1>Cedar>release>G3dScene>G3dTimeTrees.mesa

G3dTimeTrees.mesa

Glassner, July 19, 1990 12:19:32 pm PDT

Bloomenthal, July 15, 1992 11:31 pm PDT

DIRECTORY G2dSpline, G3dBasic, G3dMatrix, G3dQuaternion, G3dSpline, LinearSystem, Rope;

G3dTimeTrees: CEDAR DEFINITIONS

~ BEGIN

Type Declarations

Spline1dSequence: TYPE ~ G2dSpline.Spline1dSequence;

Pair: TYPE ~ G3dBasic.Pair;

PairSequence: TYPE ~ G3dBasic.PairSequence;

RealSequence: TYPE ~ G3dBasic.RealSequence;

Matrix: TYPE ~ G3dMatrix.Matrix;

Triple: TYPE ~ G3dMatrix.Triple;

TripleSequence: TYPE ~ G3dBasic.TripleSequence;

Quaternion: TYPE ~ G3dQuaternion.Quaternion;

QuaternionSequence: TYPE ~ G3dQuaternion.QuaternionSequence;

QuaternionSequenceRep: TYPE ~ G3dQuaternion.QuaternionSequenceRep;

SplineSequence: TYPE ~ G3dSpline.SplineSequence;

ColumnN: TYPE ~ LinearSystem.ColumnN;

MatrixN: TYPE ~ LinearSystem.MatrixN;

RowN: TYPE ~ LinearSystem.RowN;

ROPE: TYPE ~ Rope.ROPE;

TransformOrder: TYPE ~ G3dMatrix.TransformOrder;

Public Type Declarations

TTInterpolateProc: TYPE ~ PROC
[time: REAL, keys: KeySequence, object: REF, clientData: REF] RETURNS [REF];

-- evaluate a key sequence at a given time

TTReportProc: TYPE ~ PROC [strobe: REF, object: REF, clientData: REF];

-- respond to the new strobe value

TTNodeActionProc: TYPE ~ PROC [node: Node] RETURNS [continue: BOOL ¬ TRUE];

-- callback proc to process a node

KeyType: TYPE ~ { matrix, triple, real, unknown }; -- key types (use triple for colors)

InterpolationType: TYPE ~ { constant, linear, smooth }; -- forms of interpolation

Key: TYPE ~ REF KeyRep;

KeyRep: TYPE ~ RECORD [

time: REAL ¬ 1.0, -- time of this key

data: REF ¬ NIL -- data for this key

];

Node: TYPE ~ REF NodeRep;

NodeRep: TYPE ~ RECORD [

name: ROPE ¬ NIL, -- name of this node

object: REF ¬ NIL, -- object associated with this node

locked: BOOL ¬ FALSE, -- if false, node data may be changed

clientData: REF ¬ NIL, -- client data for this node

clientBackup: REF ¬ NIL, -- backup field for client use

timeTree: TimeTree ¬ NIL, -- the TimeTree supporting this node

children: NodeSequence ¬ NIL, -- children nodes

parent: Node ¬ NIL, -- parent node (NIL iff root)

transformKeyHead: KeyHead ¬ NIL, -- propagated xform

localTransform: Matrix ¬ NIL, -- local xform (can be keys)

globalTransform: Matrix ¬ NIL, -- global (inherited) xform at a time

keyHeads: LIST OF KeyHead ¬ NIL -- key sets for this node

];

FlavorInfo: TYPE ~ REF FlavorInfoRep;

FlavorInfoRep: TYPE ~ RECORD [

type: KeyType ¬ matrix, -- type of key

name: ROPE ¬ NIL, -- name for this type of key

interpolationType: InterpolationType ¬ smooth, -- kind of interpolation

gotInterpProc: BOOL ¬ FALSE, -- flag for cached interpProc

interpProc: TTInterpolateProc ¬ NIL, -- interpolate key sequence

gotReportProc: BOOL ¬ FALSE, -- flag for cached reportProc

reportProc: TTReportProc ¬ NIL -- report proc after strobing

];

KeyHead: TYPE ~ REF KeyHeadRep;

KeyHeadRep: TYPE ~ RECORD [

flavorInfo: FlavorInfo ¬ NIL,

acceleratorsValid: BOOL ¬ FALSE, -- recompute accelerators

accelerators: REF ¬ NIL, -- help for evaluation

strobe: REF ¬ NIL, -- strobed value

dirty: BOOL ¬ FALSE, -- TRUE if strobe was set externally

backup: REF ¬ NIL, -- for backup/restore operations

keys: KeySequence ¬ NIL -- the time/data pairs

];

TimeTree: TYPE ~ REF TimeTreeRep;

TimeTreeRep: TYPE ~ RECORD [

bufferNode: Node ¬ NIL, -- where nodes are built up

activeNode: Node ¬ NIL, -- focus when building tree

flavorList: LIST OF FlavorInfo ¬ NIL, -- default return procs

transformFlavor: FlavorInfo ¬ NIL, -- propagated transforms control

root: Node ¬ NIL -- root of tree

];

KeySequence: TYPE ~ REF KeySequenceRep; -- generic sequence for keys

KeySequenceRep: TYPE ~ RECORD [

length: CARDINAL ¬ 0,

element: SEQUENCE maxLength: CARDINAL OF Key

];

NodeSequence: TYPE ~ REF NodeSequenceRep; -- generic sequence for nodes

NodeSequenceRep: TYPE ~ RECORD [

length: CARDINAL ¬ 0,

element: SEQUENCE maxLength: CARDINAL OF Node

];

Private Type Declarations

-- data structure for holding Rrsrtp decomposition of an arbitrary 4-by-3 matrix

RrsrtpNode: TYPE ~ REF RrsrtpNodeRep;

RrsrtpNodeRep: TYPE ~ RECORD [

matrix: Matrix ¬ NIL, -- input matrix (superfluous?)

decomposed: BOOL ¬ FALSE, -- has matrix been turned into rrsrtp?

q1: Quaternion ¬ [], -- first rotation

qc: Quaternion ¬ [], -- conformance rotation

scale: Triple ¬ [], -- data for scale spline

q2: Quaternion ¬ [], -- second rotation

translate: Triple ¬ [], -- data for translate spline

perspective: Triple ¬ [] -- data for perspective spline

];

RealRef: TYPE ~ REF REAL;

TripleRef: TYPE ~ REF Triple;

MatrixRef: TYPE ~ Matrix;

MatrixAccelerators: TYPE ~ REF MatrixAcceleratorsRep; -- holds rrsrtp decomposition

MatrixAcceleratorsRep: TYPE ~ RECORD [

q1: QuaternionSequence ¬ NIL, -- rotation 1

scaleSpline: SplineSequence ¬ NIL, -- 3d scale spline

qc: QuaternionSequence ¬ NIL, -- conformance rotation

q2: QuaternionSequence ¬ NIL, -- rotation 2

transSpline: SplineSequence ¬ NIL, -- 3d translation spline

perspSpline: SplineSequence ¬ NIL -- 3d perspective spline

];

TripleAccelerators: TYPE ~ REF TripleAcceleratorsRep;

TripleAcceleratorsRep: TYPE ~ RECORD [

tSpline: SplineSequence ¬ NIL -- 3d spline for triples

];

RealAccelerators: TYPE ~ REF RealAcceleratorsRep;

RealAcceleratorsRep: TYPE ~ RECORD [

vSpline: Spline1dSequence ¬ NIL -- 1d spline for reals

];

A Brief Overview of TimeTrees

A TimeTree is a hierarchical data structure arranged as a tree, designed to support a generalized form of interpolation. Each node in the tree has an associated object, and an unlimited number of interpolable parameters associated with that object. Each node has exactly one parent, but it may have any number of children >= 0.

The Tree is built one node at a time. At any moment during its creation, a TimeTree has one distinguished nodes: the active node. Initially the active node is the root. When you save a parameter value for a node, or assign an object to a node, or otherwise adjust the contents of a node, this is always done with respect to the active node. When you call PushTimeTree[], a new node is created as a child of the active node, and becomes the active node itself. When you call PopTimeTree[], the parent of the currently active node becomes the active node.

Each node contains a list of parameters that can be interpolated. Each parameters is represented by a KeyHead. This is a data structure that contains a name for the parameter so you may refer to it, procedures for interpolating and communicating the parameter, and a list of time/value pairs (or keys) for the parameter. The parameter itself may be any data type: you pass it in as a REF ANY. The implementation provides interpolation procedures for REAL, Triple, and Matrix data types - you may easily register your own in addition to these defaults. To add a new value for a particular parameter at a given time, you call InsertKey[]. You may have as many different parameters at a node as you wish.

There is a single type of distinguished paramter, called the Transform. This is a matrix that (usually) describes a geometric transformation. When you strobe the TimeTree (discussed below), the Transform matrix at each node is propagated downwards to its children. This allows you to easily construct hierarchical models. For example, if you apply a rotation to an upper node, all nodes below that node will rotate as a rigid unit. Details on use of this type of structure in computer graphics can be found in most graphics texts; for example, see (dare I suggest it?) "3 D Computer Graphics for Artists and Designers" by Andrew Glassner (Design Press, 1989) for a description of hierarchical modeling.

Once a TimeTree is constructed, there are two major operations you may perform on it: Strobing and Reporting. When you Strobe a TimeTree you specify a time. Each KeyHead in each node is examined, and the data in that KeyHead is interpolated. If you have provided your own InterpolationProc at that KeyHead or throughout the tree, it is called at this point with the relevant data from the KeyHead. The result of the InterpolationProc is a REF ANY that is stored at that KeyHead as the "strobed" value of that KeyHead at that node at that time. Think of the TimeTree as an enormous structure in motion, and you have fired a single burst of a strobe light upon it.

The other high-level operation is Report. Each KeyHead in each node is examined, and its strobed value is reported back to the object associated with that node. This is done through the ReportProc, which you assign to the KeyHead when you create it, either on a per-tree or per-node basis.

Graphics types may bypass many of the details above and use the higher-level procedures described below in the interface to G3dTimeTreesDefaultsImpl.

Examples of calls on TimeTrees can be found in G3dSceneProcsImpl, which builds a complete TimeTree from a textual description of a model.

The data structure is almost always a tree, though you can disrupt this organization by moving nodes around explicitly (this is strongly discouraged, though sometimes necessary for particular applications. Should it prove important enough, the interface should support such operations more easily).

Impl Public Procs

G3dTimeTreesImpl

Generic Time Trees procedures, not explicitly related to graphics

TimeTree control

CreateTimeTree: PUBLIC PROC RETURNS [timeTree: TimeTree];

Returns a new TimeTree initialized to default values

PushTimeTree: PUBLIC PROC [timeTree: TimeTree];

Create a new child of the active node and make it active

PopTimeTree: PUBLIC PROC [timeTree: TimeTree];

Make the parent of the active node the active node

RegisterKeyType: PUBLIC PROC [timeTree: TimeTree, name: ROPE, type: KeyType, report: TTReportProc ¬ NIL, interp: TTInterpolateProc ¬ NIL, interpType: InterpolationType ¬ smooth];

Each interpolatable entity is signified by a unique name. This call allows you to specify, for an entire tree, descriptive information for a particular type of interpolatable object. You specify the name of the object, and its KeyType. You may also specify a procedure to be called for interpolation, and a procedure to report the interpolated value. You may also specify a default type of interpolation for that object. If the KeyType is one of the defined types (as opposed to the distinguished choice unknown), the default interpolation procedure will be used for that type if you don't override it.

Node control

SetNodeObject: PUBLIC PROC [
timeTree: TimeTree, object: REF ¬ NIL, clientData: REF ¬ NIL] RETURNS [Node];

Specify the object to be associated with the active node. Also specify any clientData you want passed back to the object by the report procedure.

NodeFromName: PUBLIC PROC [timeTree: TimeTree, name: ROPE] RETURNS [Node];

Return a named node.

RenameNode: PUBLIC PROC [timeTree: TimeTree, oldName, newName: ROPE];

Change the name of a node.

PruneNode: PUBLIC PROC [node: Node];

Delete the specified node. Its children are inherited by its parent

GraftNode: PUBLIC PROC [orphan, newParent: Node];

Make the specified orphan a child of newParent. Note that the connection from its original parent to this node is not cut, so this node may be the child of several nodes (though it only points back to its most recent parent).

MoveNode: PUBLIC PROC [moveNode: Node, newParent: Node];

Convenience for { PruneNode[moveNode]; GraftNode[moveNode, newParent]; }

ClearNodeObject: PUBLIC PROC [node: REF ANY];

Set the object pointer for the given node to NIL

SetLocalTransform: PUBLIC PROC [tt: TimeTree, m: Matrix];

Specify a local transformation to be associated with the active node. If there are also keys in the transformKeyHead for this node, and the node is strobed, the localTransform will be replaced by the interpolated matrix.

GetActiveNode: PUBLIC PROC [tt: TimeTree] RETURNS [REF ANY];

Return the active node.

SetActiveNode: PUBLIC PROC [tt: TimeTree, n: REF ANY];

Specify the node n to be the active node.

GetRoot: PUBLIC PROC [node: Node] RETURNS [TimeTree];

Return the TimeTree associated with this node

EnumerateNodes: PUBLIC PROC [tt: TimeTree, action: TTNodeActionProc];

Call the action proc for each node in the tree

Key control

All key control procs are interpreted with respect to the key lists in the active node

InsertKey: PUBLIC PROC [
timeTree: TimeTree, time: REAL, data: REF, name: ROPE ¬ NIL, keyHead: KeyHead ¬ NIL
];

Insert the specified time/data pair into the active node. Associate this data with the key list with the given name. The optional argument keyHead is provided as an alternative to naming the keyhead; if non-NIL, name is ignored and the specified keyHead is used.

InsertDirtyKeys: PUBLIC PROC [timeTree: TimeTree, time: REAL];

Insert a time/data pair from the strobe value into the active node for any keys marked as dirty.

SetTransformDirty: PUBLIC PROC [node: Node, dirty: BOOL ¬ TRUE];

Set the dirty bit for the transformKeyHead at this node to the value of dirty. The transformKeyHead is instantiated if necessary.

GetTransformDirty: PUBLIC PROC [node: Node] RETURNS [BOOL ¬ FALSE];

Get the dirty bit for the transformKeyHead at this node.

SetKeyHeadProcs: PUBLIC PROC [
timeTree: TimeTree, keyName: ROPE, interpProc: TTInterpolateProc ¬ NIL, reportProc: TTReportProc ¬ NIL];

Set the procedures for a particular keyHead. This is similar to RegisterKeyType, but it is specific to a keyHead, rather than an entire tree.

SetKeyHeadInterpType: PUBLIC PROC [timeTree: TimeTree, keyName: ROPE, interpType: InterpolationType ¬ smooth];

Set the interpolation type to be asscoiated with the named keyHead.

InsertTransform: PUBLIC PROC [timeTree: TimeTree, time: REAL, transform: Matrix];

Insert a time/transform pair into the distinguished, inherited transform keyHead.

SetTransformProcs: PUBLIC PROC [timeTree: TimeTree, report: TTReportProc ¬ NIL, interp: TTInterpolateProc ¬ NIL, interpType: InterpolationType ¬ smooth];

Set the procedures to be associated with the distinguished, inherited transform key.

SetTransformInterpType: PUBLIC PROC [timeTree: TimeTree, interpType: InterpolationType ¬ smooth];

Set the interpolation type to be asscoiated with the distinguished, inherited transform key.

-- Rrsrtp conversion

RrsrtpToMatrix: PUBLIC PROC [rrsrtp: RrsrtpNode] RETURNS [m: Matrix];

Compose an RrsrtpNode to a matrix

RrsrtpComponentsToMatrix: PUBLIC PROC
[q1: Quaternion, qc: Quaternion, s: Triple, q2: Quaternion, t: Triple, p: Triple] RETURNS [Matrix];

Compose the explicit components of an RrsrtpNode to a Matrix

MatrixToRrsrtp: PUBLIC PROC [m: Matrix, oldQ: Matrix ¬ NIL, propagate: BOOL ¬ TRUE] RETURNS [rrsrtp: RrsrtpNode];

Decompose a matrix into an RrsrtpNode. If propagating matrices, oldQ is the initial rotation to be matched.

Node evaulation

GetNodeKeyHead: PUBLIC PROC [node: Node, name: ROPE] RETURNS [KeyHead];

Returns the keyHead built for the named interpolant, or NIL if it doesn't exist.

GetStrobedKey: PUBLIC PROC [node: Node, name: ROPE] RETURNS [REF ANY];

Return the strobed value for this key at this node, or NIL if it doesn't exist.

TransformNode: PROC [node: Node, matrix: Matrix, order: TransformOrder];

Apply this transformation to this matrix. Note: there is no propagation.

GetGlobalTransform: PUBLIC PROC [node: Node] RETURNS [Matrix];

Get the transformation associated with this node, derived from its strobed parents.

SaveNode: PUBLIC PROC [node: Node, clientBackup: REF ANY ¬ NIL];

Save all the strobed keyheads for this node.

RestoreNode: PUBLIC PROC [node: Node] RETURNS [REF ANY];

Restore all the strobed keyheads for this node from the last "save"d value.

Node interactivity

LockActiveNode: PUBLIC PROC [timeTree: TimeTree];

Set the lock field on the currently active node to TRUE.

UnlockActiveNode: PUBLIC PROC [timeTree: TimeTree];

Set the lock field on the currently active node to FALSE.

Tree evaulation

ReportTimeTree: PUBLIC PROC [timeTree: TimeTree];

The strobed values in the nodes of the TimeTree are reported to the objects through the report procs. Assumes StrobeTimeTree has been called if the tree is to be instanced at a particular time (such a call is not necessary if there is no timing information associated with the tree).

StrobeTimeTree: PUBLIC PROC [timeTree: TimeTree, time: REAL];

Evaluate the data at each key at each node and find its value at the specified time. This value is cached for later communication to the node's object by ReportTimeTree.

G3dTimeTreesDefaultsImpl

These procedures implement the standard and default operations of TimeTrees for computer graphics. Except for the initialization procedure itself, they all assume that InitializeGraphicsTimeTree has been used to set up the appropriate defaults. Such a tree is referred to below as a 'Graphics TimeTree'.

Initialization

InitializeGraphicsTimeTree: PUBLIC PROC [tt: TimeTree];

Set the default report proceduress and key heads for computer graphics, turning the given TimeTree into a Graphics TimeTree. This should be called immediately after creating a new TimeTree.

Report procs

These procedures take the appropriate parameter and set it in a G3dShape.Shape.

ReportDiffuse: PUBLIC TTReportProc;

ReportSpecular: PUBLIC TTReportProc;

ReportMetallicity: PUBLIC TTReportProc;

ReportShininess: PUBLIC TTReportProc;

ReportTransmittance: PUBLIC TTReportProc;

ReportColor: PUBLIC TTReportProc;

ReportTransform: PUBLIC TTReportProc;

Assignment procs

These procedures insert a time/value pair into the active node in a Graphics TimeTree. They provide an easy way to insert information into the tree without the details of keyHeads and names as described above.

AssignDiffuse: PUBLIC PROC [tt: TimeTree, time: REAL, diffuse: REAL];

AssignSpecular: PUBLIC PROC [tt: TimeTree, time: REAL, specular: REAL];

AssignMetallicity: PUBLIC PROC [tt: TimeTree, time: REAL, metallicity: REAL];

AssignShininess: PUBLIC PROC [tt: TimeTree, time: REAL, shininess: REAL];

AssignTransmittance: PUBLIC PROC [tt: TimeTree, time: REAL, transmittance: REAL];

AssignColor: PUBLIC PROC [tt: TimeTree, time: REAL, color: Triple];

AssignTransform: PUBLIC PROC [tt: TimeTree, time: REAL, transform: Matrix];

This is the distinguished transformation at the active node; its values at a particular time will be inherited by its children when the tree is stobed.

Interpolation procs

These procedures allow you to assign the type of interpolation to be used at the active node for the specified parameter.

SetDiffuseInterpolationType: PUBLIC PROC [tt: TimeTree, type: InterpolationType];

SetSpecularInterpolationType: PUBLIC PROC [tt: TimeTree, type: InterpolationType];

SetMetallicityInterpolationType: PUBLIC PROC [tt: TimeTree, type: InterpolationType];

SetShininessInterpolationType: PUBLIC PROC [tt: TimeTree, type: InterpolationType];

SetTransmittanceInterpolationType: PUBLIC PROC [tt: TimeTree, type: InterpolationType];

SetColorInterpolationType: PUBLIC PROC [tt: TimeTree, type: InterpolationType];

SetTransformInterpolationType: PUBLIC PROC [tt: TimeTree, type: InterpolationType];

END.