Computer Controlled Animation System Based on Definitional Animated Objects and Methods of Manipulating Same

1. Field of the Invention

The present invention relates to an architecture and model for computer animation. Specifically, the present invention concerns the field of generation and manipulation of moving objects in a computer system.

2. Prior Art

"Computer Animation" is a term that is used to describe any application in which a computer aids in the generation and manipulation of moving images. This broad category of activities includes motion control, computer-assisted frame animation, key frame animation, color table animation, solid model animation, and two-dimensional (2D) and three-dimensional (3D) simulation. As a field, computer animation is rapidly growing. In the past ten years improvements in computer speed, size and cost have made animation by computer feasible for many new applications. Computer animation is now widely sought by applications in industry, science, manufacturing, entertainment, advertising and education. The present invention describes a comprehensive computer animation architecture.

Developing an architecture for animation means providing a mechanism (i.e. structures, utility routines, etc.) for manipulating computer displayable objects in space and time. In the following description, an object is defined as any entity controllable within an animation. This object can be visible (an animated character) or invisible (a camera or light). It can be entirely self controlled (a weight within a physics simulation) or can be controlled by external inputs (joystick or mouse). The object's physical representation can be in two dimensions or in three dimensions, a bitmap, or a collection of points and edges. Just as there are many possibilities for types of objects, there are an equal number of possibilities for types of object interactions. Combine these parameters with all of the different kinds of animation that one can create with these objects and interactions and it becomes apparent that the basic architecture must be readily extensible as well as customizable to individual application needs. It also becomes apparent that one of the primary features of an animation architecture is to provide a data-interchange format so that applications or other software components can share and include other kinds of animations, objects, etc. All of these options must be considered when designing the facilities to manipulate objects through space in real-time.

Animation presents a different way of looking at data or information. Just as graphics help to interpret large databases, animation can be even more useful for visualizing data. Simple and complete animation support will provide this power to applications that were never before able to use animation.

To date, sophisticated animation systems have been far from real-time. This is due to the demand for production quality animation coupled with insufficient hardware capabilities. As a result, the creation of a single frame of animation (typically 1/24 or 1/30 of a second) can take anywhere from several seconds to several days. An animation frame is a collection of objects or images displayable on a display screen. The animation frame represents the position and condition of objects at an instant in time. Keyframes are animation image frames initially provided to the animation system and used as a reference when moving objects.

Animation in interactive situations can often settle for a lesser quality of imaging than production graphics demand. For example, both television and video games have graphics quality of much less quality than that of traditional static graphic arts; yet, television and games remain a successful media because they are coupled with motion and sound. This kind of imaging, when used in conjunction with high quality sound and motion, can be very effective for many applications, especially those focusing on user interaction. If we further reduce the computation time by adding the capabilities of high performance hardware we will be able to create reasonable quality animation in real-time. The present invention provides a solution for efficiently generating real-time animation, since real-time response was a primary goal at the outset. In addition, the present invention provides a robust animation model providing features not available in existing prior art systems.

Currently, the world of computer animation can be divided into two separate categories: assisted animation employing a descriptive representation, and full-synthesis animation employing a numerical representation. Assisted animation consists of animation in which the computer mainly provides camera control, inbetweening (interpolation of images between keyframes), the process of coloring images, compositing (combining object images into frames), and digital sequencing of images. The input into an assisted animation system is a collection of keyframe images (or bitmaps). Input is often limited to scanned images or images generated in a paint program. The output is generally a sequence of these images, occasionally including simple inbetween frames that have been calculated from keyframes. Assisted animation includes most varieties of motion control graphics, computer-assisted frame animation and color table animation. The computer is responsible for calculating inbetween frames from keyframes and for sequencing generated frames in real-time.

Full-synthesis animation differs substantially from assisted animation. In full-synthesis animation, the computer manipulates numerical data bases instead of material artwork or image bitmaps. In full-synthesis animation, all characters, objects and environments have a mathematical description that is modified either interactively or by a script. All of these systems are based on the concept of manipulating a mathematical model for a variety of parameters including position, velocity, and proximity of objects. A "language" exists to specify actions as well as compositing and sequencing. The animation language includes a "vocabulary" to specify when actions begin and end (duration), and their rates of change (eases). Much of the current research in the field of computer animation and simulation falls under the category of full-synthesis animation.

There is a strong demand in the animation community for the ability to accurately model real world phenomena. The application of physics to bodies within a system, namely kinematics, and more recently dynamics, has inspired the creation of what is now being called procedural animation. Kinematics approaches physical systems by taking the positional goal for an object and solving for the velocities that will cause an object to arrive at that position. Conversely, dynamics takes the forces and torques being applied to an object and solves for the resultant positional information. Very often these systems are designed so that the language to specify actions is a collection of constraints. Constraints include any method that defines the relationship between parts of an object and between the objects themselves. The vocabulary that determines the duration and eases, including the actual position and velocity related information, are procedures that apply the laws of physics to the interacting objects. In general, the concept of full-synthesis animation can be stretched to cover a large variety of approaches to computer animation. The major distinction to be made here is that full-synthesis animation systems are designed to manipulate mathematical representations of objects instead of descriptive representations.

Prior art animation systems handle sound in animation either independently or loosely-coupled from the displayed images. In fact, in a typical animation production a significant amount of time is spent just synchronizing the sound track with the visual aspects of the animation. Separating the auditory from the visual aspects of an animation limits the generality of the animation system, since such an arrangement does not permit sophisticated sound generation from object interaction to be handled automatically. Consequently, it is very hard to have the sound achieve the same realism as the visual aspects of the animation.

There are certainly advantages to each variety of animation. Assisted animation has very little computational overhead; thus, it is a more practical choice for doing animation in an interactive environment. Full-synthesis animation provides a better animation model; however, such systems presently cannot operate at a real-time speed. A better solution is to support both assisted animation and full-synthesis animation within the same environment. The idea is to allow descriptive and numerical representations of objects to be mixed and matched freely within a single animation domain. For example, it may be practical to treat objects of less distinction (i.e. backgrounds and objects that do not interact with other objects) as bitmaps (descriptive representations), while the more prominent objects are mathematically represented. To extend this idea further, one may want to model an object descriptively while it is inactive and then switch to the numerical definition when the object becomes active. The present invention provides a system that has the flexibility of a full-synthesis system with the overhead approaching that of a computer assisted animation system.

1. Armstrong, William and Mark Green and Robert Lake, "Near Real-Time Control of Human Figure Models," University of Alberta, IEEE Computer Graphics and Applications, June 1987.

2. Badler, Norman I. and Kamran H. Manoochehri and Graham Walters, "Articulated Figure Positioning by Multiple Constraints," University of Pennsylvania, IEEE Computer Graphics and Applications, June 1987.

3. Bagrodia, Rajive L. And K. Mani Chandy and Jayadev Misra, "A Message-Based Approach to Discrete Event Simulation," IEEE Transactions on Software Engineering, Vol. SE-13, #6, June 1987.

4. Borning, Alan, "Thinglab - A constraint Oriented Simulation Laboratory," XEROX Palo Alto Research Center, Computer Graphics, Vol. 16, #3, July 1982.

5. Entis, Glenn, "Computer Animation - 3D Motion Specification and Control," Pacific Data Images, Siggraph '86 Tutorial Notes.

6. Fox, David, "Do it Yourself Computer Animation," Lucasfilm Ltd., May 1, 1985.

7. Girard, Michael, "Interactive Design of 3D Computer-Animated Legged Animal Motion," Ohio State University, IEEE Computer Graphics and Applications, June 1987.

8. Korein, James U. and Norman I. Badler, "Techniques for Generating the Goal-Directed Motion of Articulated Structures," University of Pennsylvania, IEEE Computer Graphics and Applications, Nov. 1982.

9. Lasseter, John, "Principles of Traditional Animation Applied to 3D Computer Animation," Pixar, ACM Computer Graphics, Vol. 21, #4, July, 1987.

10. McQueen, Gleen, "Applying Classical Techniques to Computer Animation," New York Institute of Technology, Siggraph '87 Tutorial Notes.

11. Reynolds, Craig W., "Computer Animation with Scripts and Actors," Information International Inc., Computer Graphics, Vol. 16, #3, July 1982.

12. Shelley, Kim L. and Donald D. Greenberg, "Path Specification and Path Coherence," Cornell University Computer, Computer Graphics, Vol. 16, #3, July 1982.

13. Sleketee, Scott N. and Norman I. Badler, "Parametric Keyframe Interpolation Incorporating Kinetic Adjustment and Phrasing Control," Department of Computer and Information Science, University of Pennsylvania, San Francisco, Vol. 19, #3 July 1985.

14. Smith, Karen E., "Requirements and Design for Intercoast-A Constraint Oriented Animation System," Institute for Research in Information and Scholarship, Brown University.

15. Sturman, David, "Interactive Keyframe Animation of 3D Articulated Models," New York Institute of Technology, Siggraph '87 Tutorial Notes.

16. Thalmann, Daniel and Nadia Magnenat-Thalmann, Computer Animation Theory and Practice, Tokyo, Springer Verlag, 1985

17. Thalmann, Daniel and Nadia Magnenat-Thalmann, "Controlling Evolution and Motion Using the CINEMIRA-2 Animation Sublanguage," University of Montreal.

18. Thomas, Frank and Johnston, Ollie, Disney Animation--The Illusion of Life, Abbeville Press, New York, 1981.

19. Wilhelms, Jane, "Dynamics for Everyone," University of California, Santa Cruz, IEEE Computer Graphics and Applications, Vol. 7, #6, June, 1987.

20. Wilhelms, Jane, "Toward Automatic Motion Control," University of California, Santa Cruz, IEEE Computer Graphics and Applications, Vol. 7, #4, April, 1987.

The present invention provides an architecture and model for computer animation. A computer system and animation model of the present invention provides a means and a method for the efficient generation and manipulation of animated objects in a computer-controlled environment. The animated objects include state data and methods defining the behavior of the object. The animated objects also have an associated affect volume and affect agents. An interaction manager controls the interaction between objects as the animation sequence progresses. An animation sequence is controlled by a set of rules, state graphs, or scripts. The behavior of objects is modeled using a descriptive and a mathematical representation. Objects containing visual characteristics are finally rendered to a display screen.

It is a goal of the present invention to provide a unique and useful set of features in an animation architecture which are not provided by any existing computer animation systems. These features can be broken into the following five categories: real-time performance, ease of use, extensibility, hardware independence, and data interchangeability.

Real-Time Performance. Although some people use computers for non-real-time animation applications, the vast majority of users will not. People expect interactivity from computers. They are accustomed to the graphics and sound responding immediately to their manual input. The present invention provides an animation model for use in real-time.

Affordable output also necessitates real-time performance from an animation system. Just as the printed document is the standard output medium of computer-generated text and diagrams, videotape is the standard output medium of computer-generated animation. Except for very expensive studio versions, videotape machines cannot record frame-by-frame; they can only record at a continuous rate. Consequently, if an animation system generates frames in non-real-time, it will be beyond most people's means to record their animations, even if they have the patience to wait for the frames to be generated. Thus, the present invention also provides a means for producing an inexpensive animation output.

Ease of Use. Animation must be as easy to use as static graphics is today. If the animation tools provided by the animation system are simple and complete, applications that normally would not be able to represent their ideas with motion will suddenly have the power to do so. The present invention provides the power of animation in conjunction with a user interface that is easy to use.

Extensibility. An animation system must be extensible in terms of new hardware and software capabilities. Computer manufacturers and third party developers are designing hardware that can accelerate the performance of animation. Special purpose hardware should be able to improve the performance of segments of the animation system in an architecturally controlled way. Similarly, the software implementation of the animation system must be modular so that advanced software components can augment or replace existing modules in the system. The present invention provides this flexibility and extensibility.

Hardware Independence. One of the fundamental principles of the animation architecture of the present invention is to provide hardware independence to application software and hardware. By designing a complete animation environment independent of hardware, the animation model is not vulnerable to unexpected hardware modifications. The animation architecture of the present invention is not dependent upon any specific computer hardware configuration.

Data Interchangeability. Users should be able to extract animated objects that are created in one computer application and use them in another application. The animation model of the present invention allows users to cut and paste animated objects between application programs.

FIG. 1 illustrates a computer system incorporating the present invention.

FIG. 2 illustrates World Model space depicted over a time interval.

FIG. 3 illustrates instantaneous snapshots and motion blur.

FIG. 4 illustrates a parametric path used to describe movement.

FIG. 5 illustrates an affect volume for an object.

FIGS. 6a-6d illustrate the interaction between two objects.

FIGS. 7 and 8 illustrate an object with its associated affect agents and affect volumes.

FIG. 9 illustrates the interaction between two objects as related to their affect volumes and affect agents.

FIG. 10 illustrates a state graph for an object with three states.

FIG. 11 illustrates the processing flow for animated objects.

The present invention provides a means and method for the efficient generation and manipulation of objects and images in a computer animation model. The animation of objects occurs in a domain called the world model. The actions and reactions of the objects within the domain over a period of time are monitored and controlled through the processes of the present invention.

The World Model

The World Model provides the skeletal structure for animation in the present invention. The essence of animation is motion and change: the motion of characters and their metamorphoses or change in shape, concept and color. Though motion and change have physical or spatial characteristics, they are events that can only be perceived over a period of time. Thus, the only completely independent variable in an animation system is time. All spatial transformations are dependent upon this time variable.

One might look at this world model as a reflection of the real world. Time cannot be repeated; the motions of an event that happened an hour ago can be reenacted, but not recreated. In the same sense, time proceeds steadily in our animation environment. Although a character's motion may repeat (e.g. a walking sequence), each reenaction of that motion is a unique event in time.

The World Model (World) defines a three dimensional physical space within which all objects and their time dependent interactions exist. Though this global space is defined in three dimensions, all elements within their animation environment do not have to be geometrically defined in three dimensions. For example, objects can have 21/2D (two-dimensional (2D) description with a limited Z-axis location) or full 3D representations within this space. In this way, the most simple description possible can be used for every object.

Objects

Objects are isolated entities unto themselves; each with its own local frame of reference for space and time. When an object is geometrically defined it makes sense for that object to have a local origin of (0,0,0). Similarly, when an action for an object is defined it can be specified to begin at local time 0. By working in a local space objects are defined without regard for their space and time mappings in the World. These global locations are not defined until animation time when mappings are made from the local frames to the global frames of reference for space and time. World Model space over a time interval is depicted in FIG. 2. As shown in FIG. 2, objects 1-7, each with their own local frame of reference, are moved from their position at time t.sub.0 to a position at time t.sub.1 in reference to a world frame of reference.

Aside from having its local frame of reference for space and time, an object has: 1) a collection of values (e.g. current size, orientation, color, temperament) which represent other states of the object and, 2) a collection of methods (actions that the object can perform) that describe its behavior. This combination of state and behavior completely defines an object's characteristics and abilities within an animation environment. These independent objects are then able to communicate with each other to determine the response to interactions that can occur within an animation.

It is within this definition of an object that everything (other than management of time and the management of space for an interval of time) is modeled. Stick figures, cartoon characters, lights, cameras and even input devices are treated as animation objects with state and behavior. In the sections that follow, it will become clearer how time and space are maintained, how objects are defined within this time and space, and how objects interact.

Time

As discussed above, time is the main independent variable in the animation system. There are, however, many different ways to measure time. If we look at our own world, we have several different calendars that refer to the same time by different units of measure. This is because the references upon which time is being measured are different. Similarly, objects within an animation system can utilize different time bases. A relationship between these time bases and global time must be defined and maintained if an animation is to behave consistently.

World Time vs. Local Time

Every animation has a master clock that maintains the global time to which all other events are related. This independent time measure is called World Time. World Time is considered to begin at some arbitrary time 0, and proceed uninterrupted throughout the life of an animation. World Time does not necessarily have an exact relationship (e.g. that of equality) with the host computer's real-time clock. "Fast-forwarding" an animation is an example of World Time being shorter than real-time, and "Slow-rewind" is an example of World Time being longer than and inversely related to real-time.

We have previously mentioned that an object has its own local time frame for the specification of actions performed by the object. This local time frame is not an independent variable. It specifies the duration of a set of events that must then be related or mapped to World Time. These mappings, as well as the master clock itself, must be maintained throughout the animation.

The ability to nest relative time frames is important. Objects made of moving parts, each with their own relative measure of time, can be combined to create more complex objects. A simple example of this is a moving car; the wheels rotate in their own time frame on axes relative to the frame of the car and the car moves in a time frame relative to background. All of these local time frames represent measures of time that must eventually (at the top of the hierarchy) be related to World Time.

Intervals vs. Instants

Although time is a continuum, the host computer is a system which deals with discrete entities. Consequently, there must be a means to break up time into individual units. Furthermore, all display mediums are at some level divided into discrete frames. There must be a method of subdividing continuously changing images into frames.

A simple method to break continuous time into discrete time is to sample it at instants or snapshots in time. When these "snapshots" of time are combined into a sequence, however, they only preserve the illusion of continuous time to a certain level of fidelity. Events occurring too quickly (effectively falling between the samples) will be missed. This has many ramifications in a time-modeling system, with two notable ramifications being collision detection failures and the visual perception of jerky motion. These problems are all due to temporal aliasing.

One method to compensate for the effect of temporal aliasing is to break up time into discrete intervals (periods of time) instead of instants (points in time). All changes are then considered for the duration of an interval, rather than the particular state at an instant. If object changes are described in terms of continuous functions rather than step functions, an object's state can be evaluated over an interval of time by an integration of these continuous functions across that interval. Motion blur is an example of this kind of integration. Instantaneous snapshots related to motion blur is illustrated in FIG. 3.

The present invention is built around discrete time intervals to compensate for the effects of temporal aliasing. The user may express time as instants (e.g. keyframes) if she chooses, leaving the system to interpret time continuously (e.g. generating inbetween frames based on an interval of time). The present invention also approximates intervals with instants for less robust applications which do not require the most sophisticated model.

Object Motion

All objects can be defined in four continuous dimensions (4D), three spatial and one temporal. Other definitions for an object might include properties and abilities that do not equate with a dimensional model. For example, the color, the sound, and even the mood of an object can be defined. Maintaining space-time as a continuum provides the necessary data for objects to be accurately rendered, free of aliasing, for any interval of time and from any point of view (POV). Traditional animation techniques provide continuity in space, but model time as a sequence of discrete events. An illusion of temporal continuity is created by use of object distortions such as "squash" and "stretch". These distortions can be effected by a human animator because he/she has a complete understanding of what the objects are and how they would appear for given motions. This complex understanding is not generally available to computer animation systems.

Objects are simply unclassified data for the computer. Thus, the animation system requires a mathematical definition of how an object changes through time. In the present invention, a method for achieving this mathematical definition is through the use of parametric equations.

There is a parametric equation (which can be specified as a script or a compiled data structure) in time for every time-variant parameter of an object. We call this equation a parameter path. It is intuitive to see how a path can apply to positional parameters such as the vertex of a polygon (see FIG. 4), since the application of the path to the positional parameter through time causes physical motion along a path through space. It is less obvious to see how a path applies to a non-positional parameter such as color. But nonetheless, it is a useful model for the modulation of a parameter (e.g. hue or intensity for color) through time. A parametric path for modeling the movement of an object is illustrated in FIG. 4.

Continuity in 21/2D computer animation (e.g. cel-type animation) has been traditionally achieved through keyframing methods. Essentially, a set of discrete animation keyframes is defined or initially provided to the animation model, along with an equation specifying a means for interpolating between keyframes (usually a cubic spline). The present invention defines an animation in terms of discrete parameters instead of discrete keyframes so that the animator has control of the object continuously, not just at moments in time. If an animator does not want any more control than keyframing provides, then a keyframe system can be implemented as a subset of parameter paths simply by applying a set of parameterized cubic splines for the path with the end of the spline resulting in what would have been the keyframe. A suitable editor to create and modify these splinal paths can provide an environment for an animator which is functionally equivalent to that of a keyframe animation system, but nonetheless creates parametric paths as its resultant output.

An editor to create and modify these paths for the specification of animation is a beneficial. Such an editor is provided by a tool to manipulate a 2D graphical representation of a path for each parameter (direction, color, etc.) versus time. The animator is able to freely move between path specification and a 4D viewing of the animation. A library of parametric equations is available to the editor to aid in the creation and manipulation of paths. These equations could either be viewed and edited via the editor, or manipulated directly. In this way, those who are more comfortable working within the mathematical domain will have the ability to do so.

Object Interactions

One of the characteristics of an object-based animation system is that each animated object is independent and isolated from the other objects. In an environment where objects interact with each other, a protocol must be established for the objects to communicate. Because interactions occur in space across intervals of time, the present invention includes a communication methodology which works in a space of interaction for an interval of time.

The following sections discuss the nature of object interactions within a single interval of time and interactions over several intervals of time.

Affect Volumes

Although an object can have very complex interactions with other objects, in general there is a limited range in which interaction is relevant. For example, a mechanical collision interaction with another object can only occur within the range of the object's physical extent in space. We say, then, that for a particular interaction, an object has a range of interactivity which is delineated as a volume in space. We call such a volume within the present invention a volume of affectation, or an affect volume. FIG. 5 depicts an example of affect volume for two cube-shaped objects.

An affect volume may be the exact volume of an object's physical extent, as is the usual case in mechanical collisions. However, there are many interactions, even some types of collision, for which the affect volume is different than an object's physical extent. Consider the case of two magnets approaching each other with opposing poles: the collision occurs before the objects actually touch so the affect volumes of these objects must be larger than their physical extents. In fact, an object may have a space of interaction that is equal to the entire world space. For example, a camera that looks at the entire world would need an affect volume that delineates all of World Space. We call this volume the World Volume. An object will usually have several different affect volumes, one for every different spatial delineation of the object. Some objects contain an affect volume which is nil and will not intersect with anything. Such an affect volume is called an empty affect volume. An empty affect volume may be used to indicate that an object is not participating in the interaction associated with the volume. This is a useful way of making objects oblivious to certain types of interactions for one part of the animation and aware of them during another part.

An affect volume covers a continuous range of space, but in order to maintain the concept's generality, interactions between it and other affect volumes must be evaluated across an interval of time. If we consider interactions without regard to time (e.g. evaluate collisions at instants rather than intervals in time), then we run the risk of missing or misinterpreting interactions. For example, a rapidly moving object may collide with another object, but because the collision falls between instants of evaluation it is missed. A more general method of evaluating a mechanical collision of an object moving through space is to use an affect volume which is the object's physical extent extruded along its path of motion for that time interval. Thus, an object's affect volume may change over time. For example, the affect volume of an accelerating object would elongate along the path of motion over every time interval. An elongated affect volume is depicted in FIGS. 6a-6d. Such an affect volume comprehends the potential interaction of an object through space across the entire intervals of time. FIGS. 6a and 6b illustrate the interaction between objects using the elongated affect volume technique where only one object is moving. FIGS. 6c and 6d illustrate the technique where both objects are moving.

Clearly, this system of interaction detection is only as precise in time as the resolution of the time intervals. This is because an affect volume reflects the aggregate volume of affectation across an interval of time. If an entire interaction occurs within a time interval, then it is possible that the interaction may be misinterpreted. Consider the distinction between evaluating the collision of a fast moving object with a static object (FIGS. 6a and 6b) and of two fast moving objects with each other (FIGS. 6c and 6d). In the first case, if the extruded affect volume of the object in motion crosses the affect volume of the static object, we are guaranteed that a collision has occurred. In the second case, even though the extruded affect volumes of the two objects in motion intersect, we are not guaranteed that they actually have collided; one may have passed in the other's wake without incident. Therefore, the present invention subdivides an interval of time when it recognizes that too many interactions are occurring within that interval. This is best done on an object by object basis. Only objects that are moving very quickly or interacting with many objects in a single interval may require the subdivision of time. This compensation for lost accuracy can also be controlled by the application if it understands which objects will be more active over a given interval of time.

Affect Agents

When affect volumes intersect, the resulting interaction is handled by affect agents. An affect agent is a component associated with an object that handles the external communication for interactions with other objects. An object may have many different affect agents, one for every type of interaction in which it can participate. For instance, an object may have an affect agent for collision, one for temperature detection, and another for sensitivity to sound. When an interaction occurs between two or more objects (i.e. their affect volumes intersect), there is an exchange of information between the object's affect agents for the given type of interaction. In the case of a collision, the exchange of information occurs between the two collision agents. Each affect agent inputs and outputs information about the object relevant to the particular interaction for which that agent is responsible. FIG. 7 and FIG. 8 illustrate an object with its associated affect agents and affect volumes.

An affect agent refers to an affect volume which delineates the range of affectation for the particular type of interaction for which the agent is responsible. For example, if an animated object is a bottle of soda, there may be an affect agent for collision which uses an affect volume precisely the size and shape of the bottle (extruded along the path of motion) indicating the region in which collisions are relevant. This same volume can be used to delineate the space that temperature detection is valid. The bottle may have another affect agent for sound radiation that refers to an affect volume larger than the actual size of the bottle. The range of affectation for radiation types of interaction (e.g. light, sound, temperature, magnetism) while, in theory is infinite, in practice is limited to some range beyond which the radiation is at a lower level than ambient noise. For example, a bar magnet's magnetic field has an infinite extent, but beyond some limited range has less effect on another object than the Earth's magnetic field. Consequently, radiation affect volumes, though really infinite, can be limited to some practical range. A clearer example may be the modeling of a microphone. As in the case of the bottle, the collision volume is the volume of the whole microphone. However, the sound receptor agent would have a volume that delineates a space around the head of the microphone. An affect agent also uses input and output properties that are relevant to its type of interaction. These properties are usually a subset of the complete set of properties that describe an object. In our example of a bottle, the collision agent might use properties like the mass of the bottle and its current velocity, while the temperature detection agent might use properties like the atmospheric temperature and pressure. Finally, an affect agent contains a response method or method of interaction that determines the appropriate reaction to an affectation. For our collision affect agent, the method might determine if the bottle moves or breaks. The temperature detection affect agent would determine whether fluid in the bottle freezes or boils upon a temperature affectation and whether the glass cracks from a sudden change in temperature. FIG. 9 depicts the interaction between two objects.

There are three basic kinds of interactions that can occur between affect agents: symmetric, asymmetric and exclusive. A symmetric interaction is an interaction between agents that requires satisfying the same input and output parameters in each agent. There is an identity between the input and output parameters for agents in a symmetric interaction. Collisions, for example, are typically symmetric interactions because the objects involved will require input such as the forces being applied and will also output the forces they are contributing to the collision.

An asymmetric interaction differs in that the input and output parameters of one agent may be completely different than the input and output parameters of the other agents. Indeed, not all affect agents involved in asymmetric interactions need have both input and output. An interaction involving temperature is an example of this type of interaction. The bottle in the previous example has a temperature sensitive affect agent that expects to receive the temperature source being applied as input. If a match were being held near the bottle, the match's temperature radiation affect agent would interact with the bottle's temperature sensitive affect agent and would output its specific heat. There will be more examples of asymmetric interactions presented later in this detailed description.

The third type of interaction is an exclusive interaction. Exclusive interactions provide a means for preventing interactions from occurring between affect agents of a given type while allowing interactions to occur between affect agents of a different type. For example, two light-emitting objects interact with a bottle object by illuminating the bottle. However, the light-emitting objects do not interact with the light emitted by each other. Thus, in this exclusive interaction, affect agents interact with other affect agents while not interacting with each other.

The Interaction Manager

The intersection detection of affect volumes and the management of affect agent interaction is handled by the Interaction Manager (IM). The Interaction Manager is the moderator for inter-object communication. It keeps track of all active affect agents and the current locations of their volumes within the World. When two or more affect volumes of compatible affect agents intersect, an interaction has occurred. The Interaction Manager's function is to effect and monitor the exchange of information between agents. An agent's method of interaction may use the received properties to determine the correct response to the interaction (e.g. change direction or motion, shatter, etc.). Depending on the nature of an interaction, an affect agent may need to execute its method of interaction before it can generate its output properties. The Interaction Manager initiates the interaction and then allows the agents to communicate directly via a multi-tasking operating system call or programming language construct. In an alternative implementation, the Interaction Manager receives the input/output sequencing requirements from the affect agents for a given type of interaction so that it can properly moderate the exchange of data between affect agents. The Interaction Manager cannot satisfy the requirement of two interacting objects that both need input before they provide an output. Such a situation constitutes an error.

Sometimes objects may need certain global information in order to execute their methods of action or interaction. For example, it may be necessary for an object to determine its distance from another object. Because objects operate within local frames of reference, they have no information about another objects' relative position in the world. The Interaction Manager can be queried by an object to obtain this type of global information.

In being responsible for detecting and effecting all object interactions, the Interaction Manager is the focus of control for the World model. Since intervals of evaluation for interaction may vary from object to object and affectation to affectation, the Interaction Manager must maintain World Time and time-keeping functions. Since the Interaction Manager must preserve the spatial relationship between objects in order to determine affect volume intersections, it must also maintain World Space (the limits of the space that the Interaction Manager must monitor, possibly defined to be the user's view volume).

User Interaction with Objects

One of the objectives of the present invention is to provide a system that easily supports interactive animation. Interactive animation is one in which the user can participate. Multimedia education applications and video games are the most common examples of interactive animation. Typically, a user will interact with objects in an animation through some input device such as a keyboard, mouse, or joystick. In the present invention, input devices are simply treated as objects with the same definition and constraints as any other object. Each input device has an affect agent with an affect volume, properties, and a method of interaction. In the most common case, the affect volume is the World Volume, indicating that the input device has continuous interactions with all objects that are receptive within the entire World Space. There is one set of properties for output, and potentially one for input if the device has a feedback mechanism. For example, a typical animated object contains an affect agent associated with a function button (signal generation device) on a mouse or other cursor control device coupled to the computer system. This agent controls the interaction of the object with the user while the mouse function button is activated (MouseDown).

Let us consider the example of a video game that has a single user object: a car, that the user controls with a joystick. The joystick has the World Volume (so that it intersects the car no matter where it is located in World Space), a set of output properties containing positional information about the joystick, and a method that retrieves this information. The car object has a receive-joystick affect agent. The receive-joystick affect agent would also have the World Volume, input properties to receive the positional information, and a method that determines the appropriate reaction to this information. When the joystick is moved, the Interaction Manager determines that an interaction has occurred and output from the joystick's affect agent is passed to the car, controlling its motion.

The Model in Action

As described above, the concept of an object for animation is established. An object is designed, in its own local time frame of reference, to have state and behavior characteristics that determine the actions the object may perform in an animation. Every object has a collection of agents that represent it to the World. These agents determine the interactions in which the object may participate and the extent to which they participate. The agents are registered with the Interaction Manager that controls the activation of agents in response to an interaction. A typical processing flow for the model in action is depicted in FIG. 11.

The following sections describe how this definition of an object with its associated affect agents and affect volumes can be used in action to model more specific objects such as input and output cameras, lights, and sound.

Cameras and Lights

Camera and light models are an important part of displaying a visual image of objects. The present invention supports cameras and lights as two standard types of objects within the system. Each type of object operates within the same constraints and mechanisms as any other object. Each uses affect agents and the Interaction Manager as a means of communication.

A camera is a lens through which the user views the World. A camera has a position and an orientation in the World that determines the distance and perspective from which the user views other objects. A camera also has characteristics that determine, among other things, the aspect ratio of the virtual focal plane. With this information about the camera, it is possible to construct a volume in space which delineates the image portion of the world that is captured on the focal plane of the camera. This volume is often called the view frustrum. Objects within this view frustrum are visible to the camera.

Visibility is treated as an exclusive interaction between objects that have vision (cameras) and objects that are visible. All visible objects that participate in this interaction have associated affect agents that interact only with affect agents that have vision. Objects can decline to participate in this type of interaction by not having the associated affect agent (or having an agent with an empty affect volume). Such objects will be invisible. (Note that an object's affect agent for visibility can only interact with the affect agent of an object that has vision, not with affect agents of other visible objects.) When an affect volume of a visible object intersects with the affect volume of an object with vision, an interaction has occurred. Positional information, as well as "film" type and other properties that affect rendering is collected by the vision affect agent's method of interaction and passed to the intersecting visible object's affect agent. The visible object's affect agent would then execute its method of interaction to determine the object's appearance from the camera's point of view (POV). This data is passed back to the vision affect agent. The camera object does all of the compositing of the image.

Lights are the source of illumination in any scene and are necessary if objects are to be viewed. To realistically model an environment, three different kinds of light are needed: ambient, point, and distributed light. Ambient light is light that impinges from all directions, constantly illuminating all objects, regardless of their orientation. Ambient light by itself produces unrealistic images, since few real environments are illuminated solely by ambient light. A point source is a light that has a position and orientation that determines the amount of illumination striking an object. If a surface is normal to the light rays, the surface is brightly illuminated. The more oblique the surface is to the light rays, the less the illumination. Point light sources are often used to represent a spot light or an incandescent bulb. A distributed source is much like a point source except that the light has no origin in space. Instead of representing light as radiating out from a single point, the light is radiated from a position independent direction. The effect is that the light rays all travel in parallel. This is useful when one wants to represent a bank of lights all as one object, or to represent the natural effects of sun light.

Light rays may be bounded, as they are from the beam of a flashlight, or they may radiate throughout an entire scene as they do from ambient light. Both of these situations can be modeled using affect volumes. The light source is an object with a lighting affect agent. This affect agent has an affect volume which defines which region of space is illuminated by the light source. In the case of a bounded beam of a flashlight, for example, the lighting affect volume is a cone emanating from the "light bulb." In the case of ambient light, the affect volume is the World Volume; because, it affects all objects responsive to light. Each object that is responsive to light has a light receptor affect agent. When the affect volume of a light receptor affect agent intersects the affect volume of a lighting affect agent, an illumination interaction has occurred. The light source executes its method of interaction to determine the characteristics of the light reaching the object (for example, the light may not be as bright if it is travelling a long distance), and passes this information, via the Interaction Manager, to the illuminated object. The illuminated object evaluates how the light affects its visibility (for example, by altering its color) and modifies its appearance for visibility interactions. This is a situation where the order in which interactions take place has relevance. An object needs to calculate the effect that a light has on its appearance before it renders itself. Light receptor affect agents only interact with lighting affect agents and not with each other. This is true in an exclusive interaction. The affect agent model can be used to accomplish even more sophisticated lighting effects such as shadows and diffuse light (from haze, for example).

Sound

Objects may make a variety of sounds while performing actions. However, it may be desirable to make the generation of sound dependent on object interactions. The present invention supports sound interactions with the same level of sophistication and generality that it supports light, utilizing the same model as all other object interactions. An object generates sound through a sound generator affect agent. An object receives sound through a sound receptor affect agent. When the affect volume of a sound generator affect agent intersects with the affect volume of a sound receptor affect agent, a sound interaction has occurred. Information regarding the sound is passed from the sound generator to the sound receptor and the sound receptor executes its method to respond to the sound. In the example of an object which generates a sound to be heard by the user, there is an object with a sound receptor agent that sends the sound to the system's speaker. In the more sophisticated example of generating stereo sound for the user, there are two sound receptors at different locations in the World, each of which produce sound data for one of the system speakers. Clearly, stereo sound is meaningless if both sound receptors receive the same sound information. Just as light becomes less intense over a distance, sound energy gets less intense over a distance. This can be modeled in sound interactions, providing different information to each sound receptor.

The object model of the present invention supports more sophisticated sound interactions than just providing multitrack sound output. Objects can have sound receptors that have nothing to do with audio output, but allow them to respond to sound generated by other objects. For example, a dog object may have a sound receptor affect agent that causes the dog to respond to a whistle or the sound of his name. Also, objects that have sound receptors can have active physical representations, as in the microphone example described above. The flexibility of this model allows sound to be intuitively associated with an object from the object's inception.

Object Representation

In the present invention, an object is composed of two basic parts: state and behavior. The state includes a collection of properties, a physical description, and the local frames of reference. The properties are part of the collection of data that is needed to give the object its character. An affect agent also uses properties from this set that are relevant to its interaction. For example, an object's weight, color and material composition are all types of information that is considered a property. The collection of properties define information including temperature and other non-physical qualities as well. The object's geometric description is defined descriptively (e.g. material artwork) and/or numerically (or geometrically).

The behavior of an object is represented in a collection of methods. A method is implemented in a computer model as a function, subroutine or procedure or a plurality thereof. These methods are definitions of action, not interaction. The methods of affect agents handle interactions. Methods contain programming logic defining the actions an object should perform if it is to crack, move, boil, generate sound, etc. The execution of this behavior method logic is initiated by an affect agent method. As described above, each affect agent has a method which resolves all interacting forces for a particular affectation, and determines what action is to take place. In the soda bottle example described above, if the forces striking the bottle were great enough, the collision affect agent would recognize the fact and signal the bottle to execute its method to break itself.

One important feature to note is that each object is capable of executing methods of action that modify itself. However, the object is not required to have information about the events that can cause this action. That information is determined by the affect agents. For instance, the bottle can break because it was struck or because the temperature dropped. To the object, the cause of the action is unnecessary information as long as the object can be signalled to break itself. The resultant effect is that an animator can create a character (object) that has the ability to perform many different actions upon itself. The causes leading to the performance of these actions is irrelevant. Likewise, the animator does not have to be concerned about the effect her character will have on other characters in the scene.

The affect agents provide rules (defined as methods that resolve interaction data) that govern the behavior of an object, given its current state. Affect agents do not need to be associated with objects until animation time. If implemented correctly, these agents should be simple to create and associate with the objects so that the process of creating a unique animation environment will simply be a modification to the basic rules that govern the animation.

Descriptive vs. Analytical Representation

An object in the present invention can be geometrically defined either descriptively or analytically (mathematically) or both. A descriptive definition is a collection of one or more pixmaps (two-dimensional or three-dimensional array of pixels describing the lighted or unlighted condition of display elements comprising the object) that give different views of an object. These views may be used to create frames which represent a succession of states of a character. The frames can then be incrementally displayed much in the fashion of traditional frame animation or flip books. Unlike frames used in traditional methods of animation, the pixmaps of the present invention are defined to be texture-mapped onto an arbitrary plane, providing additional flexibility. If the animator is only interested in simple frame-type animation, the plane simply defaults to a plane orthogonal to the Z-axis (parallel to the display screen plane) and conventional 21/2D animation results. Multiple renderings of an object from a variety of POVs can be defined and stored so that a camera can move freely through a scene and the appropriate 2D view can be displaced in real-time. Interesting distortions can be conceived by mapping these views into extruded spaces.

The analytical or mathematical definition is simply a collection of points and edges or splines that specify an object in two-dimensional space (two-space) or three-dimensional space (three-space). Points will normally act as controls to which parameter paths can be applied. For example, see FIG. 4 which shows the parametric path (through time) of a vertex of a pentagon. The points can also be modified in real-time in response to interactions with other objects.

We have indicated that both the descriptive and analytical representations can be useful for a single object. While it is often useful to define a geometric object analytically in three-space, on slower machines it may be physically impossible to compute a rendered view of this object in real-time. In this case, the animator may elect to have the computer precompute a collection of different views for every analytical object along the paths the user might traverse. The problem then simply becomes a matter of determining which view is closest to the visible view of the object at a moment in time, and displaying the selected view in real-time. Another useful scenario is when the host computer is fast; but, the animation contains many characters. As long as a character is in the background it may suffice to use its 2D view. For instance, this dual representation technique may be illustrated using the soda bottle example described earlier. The soda bottle in this example may be displayed as it rests on a shelf in a grocery store. A simple 2D view of this bottle could be displayed as long as shoppers are walking around the store and not interacting with the bottle. As soon as a shopper reaches to pick up the bottle the shopper's affect agent of collision and the bottle's affect agent of collision intersect. Upon collision, the analytical definition of the bottle is used instead of the descriptive definition. Thus, the full power of the analytical model can be activated when necessary.

Controlling the Animation

We have described objects and their agents and the fact that they determine the actions and interactions which take place in an animation. The Interaction Manager was described as the component that monitors and controls all interactions between objects and maintains World Time and World Space. Additionally, the concept of parameter paths was described as a means of animating any parameter of an object in time. Finally, objects have been defined to have both descriptive and analytical representations, each representation being used for a different type of action. The following sections specify how all of these variables are controlled within the animation environment. In the present invention, three different methods for controlling an animation are provided: rules, state graphs, and scripts.

Rules

Rules specify the behavior of an object given particular physical constraints. For instance, a rule would specify how an object would respond if a force were applied to it at a given point. For example, see FIG. 4 which shows the parametric path (through time) of a vertex of a pentagon. Rules in the form of equations define the behavior or movement of the pentagon. Rules are encompassed in the definition of an affect agent. Each agent specifies a rule for an object. An agent's input parameters are those that are needed to solve the rule. The method is the actual rule that determines the behavior of the object.

The Interaction Manager detects (by calculating intersecting affect volumes) whether there is an interaction occurring between two objects. If there is an interaction, the corresponding agents are alerted so that they can begin to communicate. The agent's properties contain the current state of the object. It is this information that is passed between the agents. In actuality, there is an entire message passing mechanism that exists to handle inter-object communication. A multi-tasking system is used to create and terminate processes, send messages between processes, and wait for messages and/or simulation time to elapse. Such multi-tasking systems are well known in the existing art. The rule methods are executed to determine the resultant action that the objects must take. This form of control relies on the fact that objects contain all information pertaining to interactions. It utilizes the architecture to the fullest because it is the system, not the animator, that must calculate the state of an object. This model is the most flexible.

State Graphs

A state graph is a data structure which defines the allowable transitions from one state of an object to another state. Each node on the graph is an object state, and each edge is a condition subgraph denoting particular state sequences (e.g. walking). For example, if an object can do three things, walk, eat, and sleep, the state graph would have three nodes (possibly represented by subgraphs) each corresponding to the three states and transitions defining how to get from walking to eating, from eating to sleeping, etc. Such a state graph is depicted in FIG. 10. The subgraphs 910, 920, and 930 associated with a state would contain a collection of images that represent the action of the object in the respective state. The word images is used here to imply either a descriptive representation or an analytical representation that has a particular state at a given time (i.e. every parameter that changes has a set path of motion to describe it over time). The number of images for a subgraph is arbitrary. Eating may require 40 frames to be accurately represented, while sleeping may only need ten.

Transitions 915, 916, 925, 926, 935 and 936 can either be a sequence of images that connect the motion of one state to the motion of another, or can simply be a neutral position image that the motion must reach before it can move to the next motion. Although a state graph's transition across an edge may rely on a condition derived from an interaction, state graphs, in their more general sense, are defined outside of the affect agent rule mechanism. State transitions may rely on no more than the tick of World Time to occur, and consequently can be applied quite usefully to objects with no affect agents at all.

The concept of a state graph is a very powerful tool, for it is a way to create reasonably complex interactive animations at a very low cost. A state graph can be created that has an initial state sequence (e.g. sleeping), and then, upon user input, effects a state change (e.g. to standing). In cases where the data to be animated is descriptive and not mathematical, state graphs are a simple way to sequence artwork in a controlled fashion. Although powerful, the use of state graphs is not required by the present invention.

The present invention provides the ability to create state graphs and interpret them correctly. A state graph can contain the entire animation that is read and sequenced by the Interaction Manager. A state graph can also define the animation of a single object within a larger animation. In the preferred embodiment, such a state graph is a subpart of the object and each state sequence is executed when needed. An object state graph is logically a method of action that has a descriptive definition of action instead of a mathematical definition. In this way, image representations that are computationally inexpensive can easily be combined with objects that are mathematically defined (and potentially expensive).

Scripts

A script is a special purpose animation language used to control objects in an animation. As in conventional programming languages, an animation language provides procedural control over the elements defined in the language. In the case of animation, the elements defined in the language are the objects in The World. Scripts, like state graphs, are control structures which do not rely on affect agents or a rule mechanism. They provide direct control to the animator of the objects of the animation without necessarily depending on object interactions to drive the sequencing.

Traditionally, scripts have been used to do simple keyframe animation. Keyframes represent a succession of views of an object. Intermediate frames (inbetween frames) can be interpolated from keyframes. The scripting language sequentially specifies the graphics operations to be applied to objects at given keyframes, and the interpolation methods to use in calculating the inbetween frames. A scripting model allows simple expansion to provide additional flexibility. A scripting language is easily extensible and can sometimes incorporate new ideas more quickly than the rule-based model. An example of an existing scripting language adaptable to the animation model of the present invention is the XCommand component of the Hypercard.TM. system, developed by Apple Computer, Inc., Cupertino, Calif.

A scripting language is employed in the present invention to define the behavior of objects. Scripts can be encapsulated into an object as well as existing as an external controller of objects. Internal scripts will be used to control subpart movements of one character. External scripts will be used to control the movements of one or many objects. Used together, scripts will be able to direct a complete animation, while still separating specific object behaviors from the overall choreography.

Sophisticated control structures like loops are included so that keyframes can actually be calculated within the script. An extension of this concept allows loops that have dependencies on the animation. Thus, a next frame of animation can only be calculated by inspecting the current frame to determine if a resultant condition has occurred. This resultant condition can be interaction dependent. The result is retrieved from the Interaction Manager or from the affect agents themselves. By providing a mechanism for scripts to query affect agents, the present invention supports input/output (I/O) communication from within a script (user interaction is achieved via affect agents). This provides the flexibility necessary to make the scripting system interactive.

The script language of the present invention includes commands that are "evaluative" by nature such as loops, variables, and "if" statements. This allows scripts to both respond to user input and to react to the state of other objects.

The scripting system of the present invention employs some of the concepts of higher level languages like simple FOR loop constructs. By adding animation specific queries (e.g. collision tests) to loops, the present invention exploits the power of the DO WHILE and DO UNTIL constructs, adding a new semantic extension to scripts. For example, objects can be instructed to perform a task WHILE time is less than t or execute a collection of paths (that specify positional location, color, material, etc. for every frame) UNTIL the object collides with another object.

A key to being able to have interactive script animations is to allow input from the user into the script. This means that the entire script cannot be precomputed. In the preferred embodiment, a script is compiled into an executable program that can then request input from the user. In many ways, this relates back to the state graph in that the script's primary importance is to handle transitions from input to input. The difference is that the frames are not precomputed, but created depending upon user input.

Users can create scripts directly or by using an application. Applications can aid users by hiding the scripting language with a more interactive interface. Applications may want to bypass writing the scripts "long-hand" by generating "compiled" scripts or C++ code. Compiled scripts are still editable directly; but, the command will have to be specified by numeric codes instead of text to enhance performance. The implication is that all three types of control (ASCII scripts, numerically coded scripts, and C++ code) will be able to coexist within one object.

Below are some sample script commands with their associated parameters:

In this sample scripting language, two different kinds of commands exist. The first three commands (get, move, interpolate) are commands that can be issued to any object. All objects have constructors (called by the get command), and a physical location (modified by the move command). Different interpolants (e.g. linear, splined) can be used to calculate inbetween frames for any property (e.g. location, color, size). The last three commands are object specific, addressing behaviors that exist in a particular object. When an object is created, new behaviors may also be created and installed as a command in the language. For these behaviors to be addressable by a script, the creator must add the new behavior to the scripting language.

An Example of Rules, State Graphs, and Scripts

Animation control becomes complex when the different methods of control (rules, state graphs, and scripts) are combined into one animation as may be performed in the present invention. The best way to illustrate this combination is by giving an example. The following example is a physics experiment that shows the interaction of two atoms. For the purpose of the experiment, it may be effective if the atoms shimmer to imply the constant orbital motion surrounding them. This shimmering effect could be achieved quite effectively using a state graph sequence that cycles through images of the atoms that show a slightly different amount of radiance around the core. To accomplish this effect through a rule-based lighting model is very expensive and complex. However, the actual interaction of the two atoms must simulate the laws of physics accurately. To do this, the atoms would need agents to define the rules that they obey during the interactions. Finally, the user may want to set up several different experiments, each giving the atoms different starting locations and velocities. A script is best to initialize the simulation state for each experiment. The experiment could then run for a specific period of time or until an interaction is completed.

This is a simple example, and its portrayal is certainly not the only way this animation could be created. The entire simulation could be achieved in a rule-based model. The shimmering effect could be achieved using scripts. The example is provided to show the power and flexibility of a model where the objects are generally responsible for creating actions; but, external controlling mechanisms can be applied to the objects when convenient.

Processing Logic of the Present Invention

The following section describes the animation program logic and implementation details of the present invention. The Underlying Services section describes some system level services or functions necessary to support animation. The present invention utilizes the underlying services for storage, compositing, and display of objects or images. The User Interface and User Functions section covers input/output (I/O) related issues. Animation Editors section describes the basic editors necessary to create animations.

The present invention is implemented in C++ is providing fully overridable and extensible classes. The use of classes in C++ is a well known technique in the art. C++ classes are most appropriate; since, the present invention is designed around the idea of animated objects. Objects associate well with C++ classes.

Underlying Services

Object Storage

A database is used to store animation objects with their component parts. For example, a 3D animation object has a 3D model associated with it, as well as behavior and motion scripts. A pixmap object or 2D object may have several pixmaps associated with it. Note that in some cases, component parts of an object can be shared between several animation objects. This sharing saves memory (and disk space), instead of having several identical objects.

Compositing

Compositing is the process by which a frame of animation is assembled from its constituent objects. There are three methods of compositing supported by the present invention:

1. Simple Layered Compositing

In this method, each object draws itself into an off-screen buffer. The buffer is then copied to the screen. The objects are drawn in back to front order (but only those objects that have changed since the last frame). This is the best method for high-speed real-time interactivity.

2. Z-Buffer Compositing

In this method, there is both an off-screen graphics buffer, and an associated "Z" buffer. The Z Buffer gives the limited Z coordinate location of each pixel that has been drawn. When new objects are drawn into the graphics buffer, only those pixels of the object that are nearer in Z are actually displayed (and their corresponding Z value put into the Z buffer). Objects do not need to be drawn in back to front order. This is a better method for 3D animation than simple layered compositing. This method allows for concave, interpenetrating objects; but, it takes more processing time and memory.

3.3D Database Rendering

In this method, there is no off screen buffer. Instead, each object adds itself to a 3D "database" for the given frame. Any of several 3D scene renderers can then operate on the 3D database to produce a complete image of the frame (the entire frame is rendered at every frame, even if only a small part of the frame has changed). This gives the most realistic 3D imaging (cast shadows and so forth), but is the least real-time responsive approach.

Compositing is controlled by a compositing manager. This compositing manager has a list of the objects in its view, and controls their imaging onto the screen. The imaging is oriented from a point of view or point of reference (grafport). A "camera" associated with a grafport affects how the scene is constructed. Information about camera position is passed to the objects when they draw themselves. The camera is able to "pan" across a 2D scene, and move freely in a 3D scene. The same is true of lights.

Display Services

Animation objects use well known graphics methods to render themselves as 2D, 3D, or other (e.g., video) images. These methods are used in compositing to copy objects to off-screen buffers, and to copy off-screen buffers onto the screen.

Video Services

Video can be treated as a special type of animation object which draws itself by displaying frames of video. In this way, an area of video can be added to and coexist with an animation. The area of video can even be moving around, or have other objects move on top of it, just like any other object in this environment. However, if the video is going through the compositing buffer this might cause enough slow-down in speed to consider skipping the compositing and going direct to the screen. By skipping compositing, effects like animation objects moving over the video will not be available. Either option, however is provided.

Video will also be used as a method of recording and distributing animations. For non-real time (or "near-real time") animations, video will be used to achieve real-time performance by computing the frames and recording them frame-by-frame.

Having described the underlying services provided by the present invention, the following sections describe in more detail the components of an animated object and the environment in which these objects exist.

Animation Objects

An animation object is composed of a state which defines the status of an object at any given interval of time and behavior which defines the object's capabilities. Any entity that can be animated, or have an effect on another entity, can be derived from an animation object. These entities include characters, cameras, light sources, and even microphones. The objects are all derived from an animation object base class called TAnimObject. This base class is defined in C++. A TAnimObject has states that include current orientation (i.e. location, rotation) and current time (TTime), which is relative to a clock (TClock). Specific objects have additional states. For example, a character might have additional shape and property information. A light might have an associated direction and color.

A TAnimObject also has two guaranteed behaviors; the PrepareMeO method and PresentMeO method. PrepareMeO makes sure that the state of the object is evaluated for a given time. PresentMeO determines the presentation of an object given this updated state. A character might have a PrepareMeO that executes methods to calculate its current position and orientation and a PresentMeO that generates an image given this data.

Animation objects are registered with the compositing manager discussed above. At a given time, this compositing manager signals all of the associated objects to prepare themselves and then present themselves. Upon presentation, objects pass back images or other information about themselves (depending upon the compositor) to be complied into a final image.

Object Class Definitions

The following are some examples of the kinds of objects provided in the animation system of the present invention. The object example is presented in the C++ programming language. It is apparent to those skilled in the art that other programming languages could be used.

The TAnimObject is a base class for all animation objects. Every object participating in an animation will be derived from this class. The PrepareMeO and PresentMeO methods are the general methods described above for all objects. The MoveO method simply assigns an xyz value to fPosition based on an interpolation of the object's position and destination. fReferenceClock can be a link to another clock or the object can actually have a clock of its own. This clock is run by addressing a set of clock parameters including: clock start, stop, rewind, and set. A behavior list is a list of current behaviors. If there is a move in process, MoveO is added to the behavior list so that PrepareMeO can make the appropriate method calls. Interpolation sets the interpolant to use for a given property calculation. In the base class, the only property that can be interpolated is the position.

The TCharacter class is one possible base class for a character object. It is derived from the TAnimObject so it already has basic time references and positional information. TCharacter adds a physical description by also referencing the MGraphic base class, MGraphic includes information about the object's geometry, its properties and its transforms. Two possible additional behaviors might be to add scaling and rotating capabilities to the object. It is apparent that other behaviors may be added, such as controlling the object's sound or other attributes like walking, running, etc.

An Example of Animated Objects

In order to demonstrate the interplay of behaviors and states for an object, the following example is provided. Three animation objects are used in the example. The first object is a dog; the second object is a fire hydrant; the third object is a camera. The camera object is used to effect the views of the dog and the hydrant.

The dog is a 21/2 D object (2 D description with a limited z-axis location). Its visual representation is described through sequences of pixmaps. Its state includes not only the current time and position, but also the current pixmap to be displayed. The dog's behaviors are relatively trivial; the dog can walk, sit, and bark. When the dog is walking, its PrepareMeO method communicates with its WalkO method which selects the next pixmap in the walk cycle.

The hydrant is a 3 D object. Its state includes a 3 D geometry, a scale and a color. At this point, the hydrant does not modify its position or geometry, so PrepareMeO does nothing. However, the hydrant is capable of modifying its appearance. The hydrant has two different methods for rendering, one for smooth shading and one for flat shading. By default, PresentMeO executes the smooth shading method. The object may, however be requested to render itself in flat shading. In this case, the PresentMeO method will execute the flat shading method and return its results.

The camera is a basic 2 D camera that can control panning (an effect similar to scrolling) over the field of the animation. Its state includes information including the field of view. It has a behavior that controls its motion called MoveMeO that gets initiated by the PrepareMeO method. Its PresentMeO method passes information back to the compositor that will effect the clipping of the final image. The camera's position and direction will also affect 3 D objects in the field of view (if any).

Definition of Sample Animated Objects

The class structure for the above objects can be represented in C++ as follows:

Object Communication

There are two kinds of interactions in which objects can participate: those with other objects, and those with the user. Objects can be designed to query and be queried. For example, an object might understand the message "WhereAreYou" and respond with its current location. In our example, an animator can add a WhereAreYou method to the hydrant object. The animator can then add a behavior to the dog object to query the hydrant for its location and walk toward it. If movement is now scripted into the hydrant's location, the dog will track its location.

User's interactions can be programmed into objects in two ways. First, because scripts can have "if" statements, conditions based on user events can be scripted. For example, a script could contain a statement like the following:

"if mousedown then walk the dog to (mouse.sub.-- x, mouse.sub.-- y) for 5 sec". This script statement would execute the dog's walk cycle while moving it to the position of the mousedown (mouse.sub.-- x, mouse.sub.-- y). Mousedown is the position at which a user had activated a function key on a mouse (signal generation device) connected to the computer system of the present invention. Mousedown is a commonly used and well known processing concept.

Objects can also be internally programmed to respond to user events. In this case, the dog object would actually have a behavior called MouseDown that would handle the dog's response to user mouse events. In the first example, the dog's response to mouse events could be configured separately from the dog's base class. In this case, the dog's behavior would not be inherent to all dog objects. In a second example, the dog's response to mouse events could be included within the dog's base class. In this case, all dogs would respond to mousedowns by walking toward the mousedown location; unless, the mousedown routine was overridden.

Cut and Paste/Clip Animation

There are three methods in the present invention for cutting and pasting animation sequences. The most simple method of cutting animation is to retrieve every rendered frame, much like video. The animation portion cut using this method is only editable at the bitmap level. All animation specific information is lost. This method, however is the least computationally expensive option and the option requiring the least amount of disk storage.

The second level of animation cut/paste is to separately cut keyframe and object information. The concept provides that all objects in an animation and their associated paths of motion can be cut. This scheme presumes that a destination component (object or application program in which the animation cutting is pasted) has the ability to reevaluate the paths of motion and generate the inbetween frames. This method is optimal in terms of limiting storage requirements and allowing some level of edit capability at the other end.

The third form of clip animation provides a means for cutting and pasting whole objects including their associated state, behavior, and agents. Once an object is identified by a user for cutting, information related to the object's state, behavior, and agents are transferred to a cut/paste buffer for later retrieval in a paste operation.

An Example of an Implementation of the Present Invention

As an example of an implementation of the present invention, the source code for a video game is provided herewith under Appendix A. The source code provided in Appendix A is written in the C++ programming language; however, it will be apparent that other programming languages may equivalently be used. The example of the present invention in Appendix A is implemented on an Apple Macintosh.TM. computer system developed by the assignee of the present invention.

The video game implemented by the source code of Appendix A is actually two games, both based on the same structures. In the first game, a user controls a triangle with a mouse or trackball device. The user can drag the triangle around the display screen and can shoot arrows by pressing the mouse button. At the same time, the user is being attacked by small green circles that randomly shoot arrows at the triangle. When an arrow hits a circle object or the triangle object, the object explodes. A score keeper is also provided.

In the second game, a collection of simple animation objects are implemented. One type of these objects is bouncing balls that collide with each other. Another object is a bar that grows and shrinks when other objects pass over it. Another object is an eye that appears to look at the user's mouse or the last object that the user touched. Each of the objects of the collection can be dragged using the mouse or trackball.

The source code implementing these games is structured according to the teachings of the present invention. Of particular note is the classes TWorldPort, TWorldObj, and the descendants of TWorldObj. TWorldPort operates as the Interaction Manager. TWorldPort is used for the following purposes:

it keeps track of what World objects currently exist

it tells the World object to calculate its next frame of animation

it calls the World objects to display itself

it handles offscreen compositing (buffering)

it sends events to and between the World objects

it asks World objects to check for collisions

it tells World objects when to die

These functions are called in TWorldPort::Main. The Worldport keeps a list of World objects, and lists of rectangles associated with each World object for purposes of compositing (combining) their images in an offscreen buffer. The Worldport also maintains a list of messages pending, and offers the messages to the World objects until it finds one that is interested in the message.

TWorldObj is an animation object. The various World objects like ball, box, eyes, poly, and bullet, all descend from this object. The World object is used to perform the following functions:

calculate its next frame of animation: Animate()

draw itself: Draw()

check for collisions: CollisionCheck()

return the rectangle within which it will draw: GetUpdateRect()

handle mouse events on itself: HandleMouseDown()

handle World messages from other objects: HandleEvent()

set its position in space: SetPosition();

World objects can create other World objects. For example, TBall:Animate() will create new bullet objects as it randomly shoots arrows (bullets). World objects can directly call methods (i.e. procedures) in other World objects. For example, the bullet can call a routine that terminates another object (i.e. an object's death routine) when it detects that it has intersected the other object (see TBullet::CollisionCheck() ). World objects can post messages to a message queue, and other World objects can look for those messages. For example, when balls die, they post the "ballDied" message, and the score keeper object looks for these messages. This use of messaging by World objects and collision checking is an example of the present invention concept of an affect agent and affect volumes. Each World object can create its own animation and behavior in its own way, completely independent from any of the other World objects. This is an important advantage of the architecture of the present invention. Yet, even though the objects are independent, all these diverse World objects can, nevertheless coexist and interact in the same space.

Thus, a means and a method for the efficient generation and manipulation of animated objects in a computer-controlled environment is disclosed.

Although this invention has been shown in relation to a particular embodiment it should not be considered so limited. Rather, it is limited only by the appended claims. ##SPC1##