DIRECTORY G2dSpline, G3dBasic, G3dMatrix, G3dQuaternion, G3dSpline, LinearSystem, Rope; G3dTimeTrees: CEDAR DEFINITIONS ~ BEGIN 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; TTInterpolateProc: TYPE ~ PROC [time: REAL, keys: KeySequence, object: REF, clientData: REF] RETURNS [REF]; TTReportProc: TYPE ~ PROC [strobe: REF, object: REF, clientData: REF]; TTNodeActionProc: TYPE ~ PROC [node: Node] RETURNS [continue: BOOL ¬ TRUE]; 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 ]; 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 ]; CreateTimeTree: PUBLIC PROC RETURNS [timeTree: TimeTree]; PushTimeTree: PUBLIC PROC [timeTree: TimeTree]; PopTimeTree: PUBLIC PROC [timeTree: TimeTree]; RegisterKeyType: PUBLIC PROC [timeTree: TimeTree, name: ROPE, type: KeyType, report: TTReportProc ¬ NIL, interp: TTInterpolateProc ¬ NIL, interpType: InterpolationType ¬ smooth]; SetNodeObject: PUBLIC PROC [ timeTree: TimeTree, object: REF ¬ NIL, clientData: REF ¬ NIL] RETURNS [Node]; NodeFromName: PUBLIC PROC [timeTree: TimeTree, name: ROPE] RETURNS [Node]; RenameNode: PUBLIC PROC [timeTree: TimeTree, oldName, newName: ROPE]; PruneNode: PUBLIC PROC [node: Node]; GraftNode: PUBLIC PROC [orphan, newParent: Node]; MoveNode: PUBLIC PROC [moveNode: Node, newParent: Node]; ClearNodeObject: PUBLIC PROC [node: REF ANY]; SetLocalTransform: PUBLIC PROC [tt: TimeTree, m: Matrix]; GetActiveNode: PUBLIC PROC [tt: TimeTree] RETURNS [REF ANY]; SetActiveNode: PUBLIC PROC [tt: TimeTree, n: REF ANY]; GetRoot: PUBLIC PROC [node: Node] RETURNS [TimeTree]; EnumerateNodes: PUBLIC PROC [tt: TimeTree, action: TTNodeActionProc]; InsertKey: PUBLIC PROC [ timeTree: TimeTree, time: REAL, data: REF, name: ROPE ¬ NIL, keyHead: KeyHead ¬ NIL ]; InsertDirtyKeys: PUBLIC PROC [timeTree: TimeTree, time: REAL]; SetTransformDirty: PUBLIC PROC [node: Node, dirty: BOOL ¬ TRUE]; GetTransformDirty: PUBLIC PROC [node: Node] RETURNS [BOOL ¬ FALSE]; SetKeyHeadProcs: PUBLIC PROC [ timeTree: TimeTree, keyName: ROPE, interpProc: TTInterpolateProc ¬ NIL, reportProc: TTReportProc ¬ NIL]; SetKeyHeadInterpType: PUBLIC PROC [timeTree: TimeTree, keyName: ROPE, interpType: InterpolationType ¬ smooth]; InsertTransform: PUBLIC PROC [timeTree: TimeTree, time: REAL, transform: Matrix]; SetTransformProcs: PUBLIC PROC [timeTree: TimeTree, report: TTReportProc ¬ NIL, interp: TTInterpolateProc ¬ NIL, interpType: InterpolationType ¬ smooth]; SetTransformInterpType: PUBLIC PROC [timeTree: TimeTree, interpType: InterpolationType ¬ smooth]; RrsrtpToMatrix: PUBLIC PROC [rrsrtp: RrsrtpNode] RETURNS [m: Matrix]; RrsrtpComponentsToMatrix: PUBLIC PROC [q1: Quaternion, qc: Quaternion, s: Triple, q2: Quaternion, t: Triple, p: Triple] RETURNS [Matrix]; MatrixToRrsrtp: PUBLIC PROC [m: Matrix, oldQ: Matrix ¬ NIL, propagate: BOOL ¬ TRUE] RETURNS [rrsrtp: RrsrtpNode]; GetNodeKeyHead: PUBLIC PROC [node: Node, name: ROPE] RETURNS [KeyHead]; GetStrobedKey: PUBLIC PROC [node: Node, name: ROPE] RETURNS [REF ANY]; TransformNode: PROC [node: Node, matrix: Matrix, order: TransformOrder]; GetGlobalTransform: PUBLIC PROC [node: Node] RETURNS [Matrix]; SaveNode: PUBLIC PROC [node: Node, clientBackup: REF ANY ¬ NIL]; RestoreNode: PUBLIC PROC [node: Node] RETURNS [REF ANY]; LockActiveNode: PUBLIC PROC [timeTree: TimeTree]; UnlockActiveNode: PUBLIC PROC [timeTree: TimeTree]; ReportTimeTree: PUBLIC PROC [timeTree: TimeTree]; StrobeTimeTree: PUBLIC PROC [timeTree: TimeTree, time: REAL]; InitializeGraphicsTimeTree: PUBLIC PROC [tt: TimeTree]; ReportDiffuse: PUBLIC TTReportProc; ReportSpecular: PUBLIC TTReportProc; ReportMetallicity: PUBLIC TTReportProc; ReportShininess: PUBLIC TTReportProc; ReportTransmittance: PUBLIC TTReportProc; ReportColor: PUBLIC TTReportProc; ReportTransform: PUBLIC TTReportProc; 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]; 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. &B G3dTimeTrees.mesa Copyright Ó 1988, 1992 by Xerox Corporation. All rights reserved. Glassner, July 19, 1990 12:19:32 pm PDT Bloomenthal, July 15, 1992 11:31 pm PDT Type Declarations Public Type Declarations -- evaluate a key sequence at a given time -- respond to the new strobe value -- callback proc to process a node Private Type Declarations -- data structure for holding Rrsrtp decomposition of an arbitrary 4-by-3 matrix 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 Returns a new TimeTree initialized to default values Create a new child of the active node and make it active Make the parent of the active node the active node 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 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. Return a named node. Change the name of a node. Delete the specified node. Its children are inherited by its parent 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). Convenience for { PruneNode[moveNode]; GraftNode[moveNode, newParent]; } Set the object pointer for the given node to NIL 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. Return the active node. Specify the node n to be the active node. Return the TimeTree associated with this node 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 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. Insert a time/data pair from the strobe value into the active node for any keys marked as dirty. Set the dirty bit for the transformKeyHead at this node to the value of dirty. The transformKeyHead is instantiated if necessary. Get the dirty bit for the transformKeyHead at this node. Set the procedures for a particular keyHead. This is similar to RegisterKeyType, but it is specific to a keyHead, rather than an entire tree. Set the interpolation type to be asscoiated with the named keyHead. Insert a time/transform pair into the distinguished, inherited transform keyHead. Set the procedures to be associated with the distinguished, inherited transform key. Set the interpolation type to be asscoiated with the distinguished, inherited transform key. -- Rrsrtp conversion Compose an RrsrtpNode to a matrix Compose the explicit components of an RrsrtpNode to a Matrix Decompose a matrix into an RrsrtpNode. If propagating matrices, oldQ is the initial rotation to be matched. Node evaulation Returns the keyHead built for the named interpolant, or NIL if it doesn't exist. Return the strobed value for this key at this node, or NIL if it doesn't exist. Apply this transformation to this matrix. Note: there is no propagation. Get the transformation associated with this node, derived from its strobed parents. Save all the strobed keyheads for this node. Restore all the strobed keyheads for this node from the last "save"d value. Node interactivity Set the lock field on the currently active node to TRUE. Set the lock field on the currently active node to FALSE. Tree evaulation 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). 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 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. 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. 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. Ê ú•NewlineDelimiter –"cedarcode" style™™Jšœ Ïeœ6™BJ™'J™'J˜JšÏk œN˜WJ˜—JšÑbln œžœž ˜Jšœž˜headšÏl™Jšœžœ˜6Jšœ žœ˜!Jšœžœ˜.Jšœžœ˜.Jšœ žœ˜%Jšœ žœ˜%Jšœžœ˜2Jšœžœ˜0Jšœžœ$˜=Jšœžœ'˜BJšœžœ˜3Jšœ žœ˜)Jšœžœ˜*Jšœ žœ˜$Jšžœžœžœ˜Jšœžœ˜3—š ™šœžœžœžœžœžœžœžœ˜kJšœ*™*—J˜š œžœžœ žœ žœžœ˜FJšœ"™"—J™š œžœžœžœ žœžœ˜KJ™"—J˜Jšœ žœ,Ïc$˜]J˜Jšœžœ'¡˜WJ˜Jšœ žœžœ˜šœ žœžœ˜Jšœ žœ ¡˜/Jšœ žœžœ¡˜/˜J˜——Jšœ žœžœ ˜šœ žœžœ˜Jšœ žœžœ¡˜0Jšœ žœžœ¡#˜?Jšœ žœžœ¡&˜DJšœžœžœ¡˜;Jšœžœžœ¡˜>Jšœžœ¡$˜FJšœžœ¡˜5Jšœžœ¡˜:Jšœžœ¡˜9Jšœžœ¡˜@Jšœžœ¡%˜JJšœžœžœ žœ¡˜=J˜J˜—Jšœžœžœ˜(šœžœžœ˜ Jšœ!¡˜/Jšœ žœžœ¡˜9Jšœ1¡˜IJšœžœžœ¡˜AJšœ$žœ¡˜EJšœžœžœ¡˜AJšœžœ¡˜CJ˜J˜—Jšœ žœžœ ˜#šœžœžœ˜Jšœžœ˜#Jšœžœžœ¡˜?Jšœžœžœ¡˜7Jšœ žœžœ¡˜,Jšœ žœžœ¡$˜BJšœ žœžœ¡$˜@Jšœžœ¡˜6J˜—J˜Jšœ žœžœ ˜$šœžœžœ˜Jšœžœ¡˜Jšœ žœ¡˜Jšœ`™`J˜—š ¤œžœžœžœžœ˜@J™‚—J˜š ¤œžœžœžœžœžœ˜CJ™8—J˜š ¤œžœžœ žœ"žœžœ˜‡J™ŽJ˜—š¤œžœžœžœ*˜nJ™CJ˜—š¤œžœžœžœ˜QJ™QJ˜—š ¤œžœžœ-žœžœ*˜™J™TJ˜—š¤œžœžœ>˜a™\J˜——Jšœ™š¤œžœžœžœ ˜EJ™!—J˜š¤œžœžœRžœ ˜‰J™J™SJ™—š ¤œžœžœžœžœžœ˜@J™,J™—š ¤ œžœžœžœžœžœ˜8J™KJ™——š£™J™š¤œžœžœ˜1J™8J˜—š¤œžœžœ˜3J™9J™——š£™J™š¤œžœžœ˜1J™œJ˜—š¤œžœžœžœ˜=J™ª———J™š£™J™³J™š£™š¤œžœžœ˜7J™¾—J˜—š£ ™ J™OJ™Jš¤ œžœ˜#Jš¤œžœ˜$Jš¤œžœ˜'Jš¤œžœ˜%Jš¤œžœ˜)Jš¤ œžœ˜!Jš¤œžœ˜%J˜—š£™J™ÒJ™Jš ¤ œžœžœžœ žœ˜EJš ¤œžœžœžœ žœ˜GJš ¤œžœžœžœžœ˜MJš ¤œžœžœžœ žœ˜IJš ¤œžœžœžœžœ˜QJš¤ œžœžœžœ˜CJ˜š¤œžœžœžœ˜KJ™——J˜—š£™J™yJ™Jš¤œžœžœ)˜QJš¤œžœžœ)˜RJš¤œžœžœ)˜UJš¤œžœžœ)˜SJš¤!œžœžœ)˜WJš¤œžœžœ)˜OJš¤œžœžœ)˜S—J˜—J˜J˜J˜—Jšžœ˜J˜—…—&rZ®