Abstract:
Techniques are proposed for animating a plurality of objects in a computer graphics environment. A crowd choreography system receives a first beat description defining potential motions for the plurality of objects, where the first beat description includes a first motion characteristic. The crowd choreography system selects a first object from the plurality of objects and selects a first value for the first motion characteristic based on the first beat description. The crowd choreography system creates a first motion path for the first object based on the first value and animates the first object based on the first motion path.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to the field of computer animation and, in particular, to choreography of animated crowds. 
     2. Description of the Related Art 
     Computer-based animation often involves scenes that include groups of characters, objects, or agents, that are engaged in a particular activity, such as walking, running, standing, or sitting. During an animated scene, such character groups may provide an appropriate backdrop to the central action of the scene. For example, an animated scene that takes place on a populated university campus could involve a large number of medium-scale “ambient” crowd shots, where the crowd includes students, professors, and other characters. Although a crowd shot could be animated by separately rigging and animating each character in the crowd individually, such an approach involves a significant amount of human and computing resources and is, therefore, time and cost prohibitive. 
     One possible solution to this problem is to set each character in motion autonomously via a crowd simulator, such as a finite state machine (FSM) based crowd animation tool. One drawback with this approach is that such tools are typically configured to animate a group of characters where all characters are of the same type. For example, a crowd simulator could be configured to animate a group of bipedal characters such as human characters. Alternatively, the crowd simulator could be configured to animate a group of quadripedal characters such as horses. However, controlling both types of characters at the same time is often tedious with traditional systems because the set of animation parameters and options for each type of character may not be the same, particular when character types have significantly differing body morphologies. As a result, the animation artist composes different instructions and animation parameters separately for each character type. For crowds that have many types of characters, each with a variety of animation options, such an approach can quickly become burdensome for the animation artist. As a result, an animated crowd scene with varying character types would involve configuring the crowd simulator at least once for each different character type. 
     Another drawback with this approach is that typical crowd simulators do not handle transitions from one generic set of motions to another generic set of motions at a specific moment in time very well. For example, the animation artist could want a group of characters to stand for some amount of time, and then to begin walking at a certain point in time. In traditional finite state machine setups, the animator typically has to configure this transition uniquely for each type of character. In cases where a scene includes numerous character types, each with a unique set of possible versions of “stand” and “walk” animation sequences, this approach likewise becomes burdensome to the animation artist. 
     SUMMARY OF THE INVENTION 
     One embodiment of the present invention includes a method for animating objects in a computer graphics environment. The method includes receiving a first beat description defining potential motions for the plurality of objects, where the first beat description includes a first motion characteristic. The method further includes selecting a first object from the plurality of objects and selecting a first value for the first motion characteristic based on the first beat description. The method further includes creating a first motion path for the first object based on the first value and animating the first object based on the first motion path. 
     Other embodiments include, without limitation, a computer-readable storage medium that includes instructions that enable a processing unit to implement one or more aspects of the disclosed methods as well as a computing system configured to implement one or more aspects of the disclosed methods. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       So that the manner in which the above recited features of the invention can be understood in detail, a more particular description of the invention, briefly summarized above, may be had by reference to embodiments, some of which are illustrated in the appended drawings. It is to be noted, however, that the appended drawings illustrate only typical embodiments of this invention and are therefore not to be considered limiting of its scope, for the invention may admit to other equally effective embodiments. 
         FIG. 1  is a block diagram of a system configured to implement one or more aspects of the invention; 
         FIG. 2  is a rendered image that illustrates various characters in an animated crowd, according to one embodiment of the invention; 
         FIG. 3  illustrates a graphical user interface for choreographing a crowd of animated characters, according to one embodiment of the invention; 
         FIG. 4  illustrates a graphical user interface for choreographing a crowd of animated characters, according to another embodiment of the invention; 
         FIG. 5  illustrates a crowd choreography system as may be implemented on the computing system of  FIG. 1 , according to one embodiment of the invention; and 
         FIG. 6  sets forth a flow diagram of method steps for choreographing an animated crowd with the system of  FIG. 5 , according to one embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION 
     In the following, reference is made to embodiments of the invention. However, it should be understood that the invention is not limited to specific described embodiments. Instead, any combination of the following features and elements, whether related to different embodiments or not, is contemplated to implement and practice the invention. Furthermore, although embodiments of the invention may achieve advantages over other possible solutions and/or over the prior art, whether or not a particular advantage is achieved by a given embodiment is not limiting of the invention. Thus, the following aspects, features, embodiments and advantages are merely illustrative and are not considered elements or limitations of the appended claims except where explicitly recited in a claim(s). Likewise, reference to “the invention” shall not be construed as a generalization of any inventive subject matter disclosed herein and shall not be considered to be an element or limitation of the appended claims except where explicitly recited in a claim(s). 
     As will be appreciated by one skilled in the art, aspects of the present invention may be embodied as a system, method or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system.” Furthermore, aspects of the present invention may take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon. 
     Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device. 
     A computer readable signal medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device. 
     Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing. 
     Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code may execute entirely on the user&#39;s computer, partly on the user&#39;s computer, as a stand-alone software package, partly on the user&#39;s computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user&#39;s computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). 
     Aspects of the present invention are described below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. 
     These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks. 
     The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. 
     HARDWARE OVERVIEW 
       FIG. 1  depicts one architecture of a system  100  within which embodiments of the present invention may be implemented. This figure in no way limits or is intended to limit the scope of the present invention. 
     System  100  may be a personal computer, video game console, personal digital assistant, rendering engine, or any other device suitable for practicing one or more embodiments of the present invention. 
     As shown, system  100  includes a central processing unit (CPU)  102  and a system memory  104  communicating via a bus path that may include a memory bridge  105 . CPU  102  includes one or more processing cores, and, in operation, CPU  102  is the master processor of system  100 , controlling and coordinating operations of other system components. System memory  104  stores software applications and data for use by CPU  102 . CPU  102  runs software applications and optionally an operating system. Memory bridge  105 , which may be, e.g., a Northbridge chip, is connected via a bus or other communication path (e.g., a HyperTransport link) to an I/O (input/output) bridge  107 . I/O bridge  107 , which may be, e.g., a Southbridge chip, receives user input from one or more user input devices  108  (e.g., keyboard, mouse, joystick, digitizer tablets, touch pads, touch screens, still or video cameras, motion sensors, and/or microphones) and forwards the input to CPU  102  via memory bridge  105 . 
     A display processor  112  is coupled to memory bridge  105  via a bus or other communication path (e.g., a PCI Express, Accelerated Graphics Port, or HyperTransport link); in one embodiment display processor  112  is a graphics subsystem that includes at least one graphics processing unit (GPU) and graphics memory. Graphics memory includes a display memory (e.g., a frame buffer) used for storing pixel data for each pixel of an output image. Graphics memory can be integrated in the same device as the GPU, connected as a separate device with the GPU, and/or implemented within system memory  104 . 
     Display processor  112  periodically delivers pixels to a display device  110  (e.g., a screen or conventional CRT, plasma, OLED, SED or LCD based monitor or television). Additionally, display processor  112  may output pixels to film recorders adapted to reproduce computer generated images on photographic film. Display processor  112  can provide display device  110  with an analog or digital signal. 
     A system disk  114  is also connected to I/O bridge  107  and may be configured to store content and applications and data for use by CPU  102  and display processor  112 . System disk  114  provides non-volatile storage for applications and data and may include fixed or removable hard disk drives, flash memory devices, and CD-ROM, DVD-ROM, Blu-ray, HD-DVD, or other magnetic, optical, or solid state storage devices. 
     A switch  116  provides connections between I/O bridge  107  and other components such as a network adapter  118  and various add-in cards  120  and  121 . Network adapter  118  allows system  100  to communicate with other systems via an electronic communications network, and may include wired or wireless communication over local area networks and wide area networks such as the Internet. 
     Other components (not shown), including USB or other port connections, film recording devices, and the like, may also be connected to I/O bridge  107 . For example, an audio processor may be used to generate analog or digital audio output from instructions and/or data provided by CPU  102 , system memory  104 , or system disk  114 . Communication paths interconnecting the various components in  FIG. 1  may be implemented using any suitable protocols, such as PCI (Peripheral Component Interconnect), PCI Express (PCI-E), AGP (Accelerated Graphics Port), HyperTransport, or any other bus or point-to-point communication protocol(s), and connections between different devices may use different protocols, as is known in the art. 
     In one embodiment, display processor  112  incorporates circuitry optimized for graphics and video processing, including, for example, video output circuitry, and constitutes a graphics processing unit (GPU). In another embodiment, display processor  112  incorporates circuitry optimized for general purpose processing. In yet another embodiment, display processor  112  may be integrated with one or more other system elements, such as the memory bridge  105 , CPU  102 , and I/O bridge  107  to form a system on chip (SoC). In still further embodiments, display processor  112  is omitted and software executed by CPU  102  performs the functions of display processor  112 . 
     Pixel data can be provided to display processor  112  directly from CPU  102 . In some embodiments of the present invention, instructions and/or data representing a scene are provided to a render farm or a set of server computers, each similar to system  100 , via network adapter  118  or system disk  114 . The render farm generates one or more rendered images of the scene using the provided instructions and/or data. These rendered images may be stored on computer-readable media in a digital format and optionally returned to system  100  for display. Similarly, stereo image pairs processed by display processor  112  may be output to other systems for display, stored in system disk  114 , or stored on computer-readable media in a digital format. 
     Alternatively, CPU  102  provides display processor  112  with data and/or instructions defining the desired output images, from which display processor  112  generates the pixel data of one or more output images, including characterizing and/or adjusting the offset between stereo image pairs, in the case of stereoscopic images. The data and/or instructions defining the desired output images can be stored in system memory  104  or graphics memory within display processor  112 . In an embodiment, display processor  112  includes 3D rendering capabilities for generating pixel data for output images from instructions and data defining the geometry, lighting shading, texturing, motion, and/or camera parameters for a scene. Display processor  112  can further include one or more programmable execution units capable of executing shader programs, tone mapping programs, and the like. 
     CPU  102 , render farm, and/or display processor  112  can employ any surface or volume rendering technique known in the art to create one or more rendered images from the provided data and instructions, including rasterization, scanline rendering REYES or micropolygon rendering, ray casting, ray tracing, image-based rendering techniques, and/or combinations of these and any other rendering or image processing techniques known in the art. 
     It will be appreciated that the system shown herein is illustrative and that variations and modifications are possible. The connection topology, including the number and arrangement of bridges, may be modified as desired. For instance, in some embodiments, system memory  104  is connected to CPU  102  directly rather than through a bridge, and other devices communicate with system memory  104  via memory bridge  105  and CPU  102 . In other alternative topologies display processor  112  is connected to I/O bridge  107  or directly to CPU  102 , rather than to memory bridge  105 . In still other embodiments, I/O bridge  107  and memory bridge  105  might be integrated into a single chip. The particular components shown herein are optional; for instance, any number of add-in cards or peripheral devices might be supported. In some embodiments, switch  116  is eliminated, and network adapter  118  and add-in cards  120 ,  121  connect directly to I/O bridge  107 . 
       FIG. 2  is a rendered image  200  that illustrates various characters in an animated crowd, according to one embodiment of the invention. As shown, the rendered image  200  includes several exemplary characters  210 ,  220 ,  230 ,  240 . 
     Three of the exemplary characters are bipeds. As used herein, the term “character” is used interchangeably with “object” or “agent.” The first character  210  is a first type of bipedal character in a standing pose. The second character  220  is a second type of bipedal character in a sitting pose. The third character  230  is a third type of bipedal character in a walking pose. If all three types of bipedal characters  210 ,  220 ,  230  exhibit the same forms of animated movement and styles, then the bipedal characters may share an animation library, so long as the animation library includes standing, sitting, and walking poses. Alternatively, if all three types of bipedal characters  210 ,  220 ,  230  exhibit different forms of animated movement and styles, then each bipedal character type may access a different animation library, where the animation library includes various poses appropriate for the particular character type. Character  240  is a type of pentapedal character in a standing pose. Although bipedal character  210  and pentapedal character  240  are both in standing poses, characters  210  and  240  may access different animation libraries that include standing poses appropriate to each character&#39;s  210 ,  240  type. 
       FIG. 3  illustrates a graphical user interface  300  for choreographing a crowd of animated characters, according to one embodiment of the invention. As shown, the graphical user interface  300  includes a loaded crowd window  302 , a crowd group selection window  304 , a behavior playlist  310 , and an edit playlist  320 . 
     The loaded crowd window  302  indicates the name of the crowd that is currently loaded in memory and available for editing. The loaded crowd window  302  provides a mechanism for creating a new crowd. As used herein, a crowd is global object that includes a group of animatable characters of varying types where each character type may exhibit different forms of animated movement and styles. As shown, the currently loaded crowd is called “Crowd_1.” In addition, new crowds may be created using the “New Crowd:” portion of the loaded crowd window  304 . The new crowd may be created from one or more selected crowds in the crowd group selection window  304  by using the “From Selection” button. Alternatively, the new crowd may be created from the group of all characters in the currently loaded crowd by using the “From All” button. Once a crowd has been created, existing characters may be deleted from and new characters added to the crowd as desired. 
     The crowd group selection window  304  includes the names of crowd groups that are currently accessible via the graphical user interface  300 . As shown, the crowd group selection window  304  includes the name of six different crowd groups. The crowd group named “All” is a crowd group that includes all characters of the currently loaded crowd. The crowd groups named “Biped Type 1,” “Biped Type 2,” and “Quintaped Type 1,” includes characters belonging to a first biped type, a second biped type, and a first quintaped type, respectively. The crowd group named “Five Quintapeds” includes five specific quintaped characters, such as five characters selected from the “Quintaped Type 1” crowd group. The crowd group named “Biped 123” includes one specific character (Biped 123), such as a character selected from either the “Biped Type 1” crowd group or the “Biped Type 2” crowd group. 
     The behavior playlist  310  includes one or more “beat sequences”  312 ,  314 ,  316 , where each beat sequence defines the motion of a crowd group over a specified period of time, where the motion is defined in probabilistic terms. As such, a beat sequence may be thought of as being analogous to one or more “actions” or “story beats” in a screenplay. For example, the definition for a beat sequence  312 ,  314 ,  316  could be analogous to a directorial expression such as, “you fifty characters walk around during this shot while you seventy-five characters stand” or “all of you characters stand around until halfway through the shot, and then start cheering or jumping.” The set of beats and beat sequences form a hierarchical set of probabilistically weighted collections of action specifications. Each beat is associated with a group of characters, or crowd group, where the set of available actions, styles, and alternatives for the crowd group is constrained by the available action inventory for the corresponding crowd group. A beat may be “viewed” from the perspective of different subgroups of characters within a crowd group. A beat may be attached to a single character “view” and then probabilistically sampled to return a fully specified action or motion. 
     In various embodiments, a beat may exist over a precise amount of time or an imprecise amount of time in a shot. Alternatively, a beat may specify actions or motions in the context of a timeless state. For example, a beat could specify an action or motion for a character while that character is positioned within a certain region in 3D space. Such a beat would terminate when the character moves outside of the certain region. 
     During animation, the beats inform a crowd choreography application, an embodiment of which is described in conjunction with  FIG. 5 , that provides high-level fully-directed locomotion for each character in a crowd group associated with each beat. The crowd choreography application creates a new character path for each character by offsetting linear approximations of guide curves, which may appear in a variety of forms, including, without limitation, pre-existing Bezier paths or user-defined 2D sketches. Points sampled from the guide curves are projected onto a ground plane and used for a Bezier curve fit. Adaptive sampling may be used to provide greater resolution in areas of quickly varying terrain. Characters in a crowd group are initially dispersed along the available paths to minimize collisions between characters over time. Layout translation along the path may be applied to each character based on a valid speed determined from an inventory of indexed animation motion clips within an animation library. Metadata associated with the animation motion clips allows for conversion of the beats into sequenced animation clips for each character during animation and image rendering. 
     As further described herein, each beat sequence  312 ,  314 ,  316  similarly describes a general, rather than a specific, direction for a corresponding crowd group. The general direction for the crowd group translates to a specific direction for each character when the scene including the crowd group is rendered. 
     The first beat sequence  312  is the “All” beat sequence that directs motion for all characters in the currently loaded crowd. As shown, the first beat sequence  312  includes a single beat entitled “Beat Walk_Run_Stand.” The beat is defined to begin at frame 1 and end at frame 500. As shown, the first beat sequence  312  has a bold border, indicating that the first beat sequence  312  is selected. As further described below, the edit playlist  320  details parameters associated with the currently selected beat sequence. 
     The second beat sequence  314  is the beat sequence that directs motion for characters included in the “Five Quintapeds” crowd group. As shown, the second beat sequence  314  includes two beats. The first beat is entitled “Beat Cheer.” This first beat is defined to begin at frame 1 and end at frame 213. The second beat is entitled “Beat Sit.” This second beat is defined to begin at frame 214 and end at frame 500. 
     In some embodiments, a transition motion clip may be inserted into the motion for each character between two successive beats in a beat sequence. For example, the two beats of the second beat sequence  314  could indicate that the five quintapeds transition from a cheering action to a sitting action. Because such a transition could appear to be unnatural, a transition motion could be inserted in the motion for each of the five quintapeds between the cheering action and the sitting action, where the transition motion defines a natural movement from a cheering position to a sitting position. By inserting this transition motion, the motion for the five quintapeds would transition smoothly from cheering to sitting. If no appropriate transition motion is found, the five quintapeds could be rendered showing an abrupt change from cheering to sitting, and an error message could be generated. This error message could prompt a user to take appropriate action, including, without limitation, changing the beat sequence to avoid the transition or creating a motion clip with an appropriate transition. 
     The third beat sequence  316  is the beat sequence that directs motion for a crowd group that includes a single character identified as “Biped 123.” As shown, the third beat sequence  316  includes three beats. The first beat is entitled “Beat Stand A.” This first beat is defined to begin at frame 1 and end at frame 160. The second beat is entitled “Beat Stand B.” This second beat is defined to begin at frame 161 and end at frame 340. The third beat is entitled “Beat Walk.” This third beat is defined to begin at frame 341 and end at frame 500. 
     In some embodiments, each beat may not necessarily start and end at the exact frame shown in the behavior playlist  310 . For example, the second beat sequence  314  includes a beat that begins at frame 1 and ends 213 and another beat that begins on 214 and ends at frame 500. When the crowd is rendered, individual characters included in the second beat sequence  314  may transition from “Beat Cheer” to “Beat Sit” at a point in time that is near frames 213 and 214, but not exactly at the frame cut between frames 213 and 214. By allowing a transition from one beat to another to vary slightly from the designated transition point may provide a more natural look when characters in a crowd group sequence from one beat to the next beat. 
     In some embodiments, the weights shown in each of the actions screen  322 , styles screen  324 , and alternatives screen may be initialized to be equal to each other and to sum to 1.0. The weights may then be altered as desired for a particular beat sequence, and the system automatically maintains the characteristic that the set of weights for each screen sum to 1.0 as the individual weights are altered. 
     Although the beats and beat sequences are described in units of time, any technically feasible metric may be used to define the duration of beats and beat sequences. For example, a beat could be specified in positional terms. As such, a first beat in a beat sequence could direct the characters in a crowd group to run from a starting position until each character enters a defined region of space in the scene. A second beat in the beat sequence could direct each character to transition from a running action to a standing action when the character has entered the defined region. 
     If a character is a member of more than one crowd group, then the character&#39;s motion is defined by the highest beat of which the character is a member. For example, the motion of a quintaped who is a member of the “Five Quintapeds” crowd group would be defined by the “Five Quintapeds” beat  314  rather than the “All” beat  312 . The motion of character Biped 123 would be defined by the “Biped 123” beat  316  rather than the “All” beat  312 . The motion of other characters would be defined by the “All” beat  312 . 
     The edit playlist  320  includes three menus where motions related to a selected beat may be specified. As shown, the edit playlist includes an actions menu  322 , a styles menu  324 , and an alternatives menu  326 . 
     The actions menu  322  specifies the top level category defining the motion of the selected beat and crowd group. As shown, the selected beat is from the first beat sequence  312 , identified as Beat Walk_Run_Stand for the All crowd group. The actions menu  322  indicates that the selected beat includes three action types—namely, walk, stand, and run. The weights indicate the relative probability that a given character will exhibit the corresponding action. Typically, the sum of the action weights is 1.00. Accordingly, the actions menu  322  indicates that approximately 21% of the characters in the All crowd group perform the walk action, 58% of the characters perform the stand action, and 21% of the characters perform the run action. In one embodiment, the actions shown in the actions menu  322  may be those actions which all character types in the corresponding crowd group may perform. The “walk” action is in bold type, indicating that the walk action is selected. As a result, the styles menu  324  indicates the various styles of walking that the characters in the All crowd group may perform. 
     The styles menu  324  specifies the second level category defining the motion of the selected beat and crowd group. The styles menu  324  indicates that the selected beat includes five styles of the walking action type—namely, cool, fast, jog, slither, and tall_swagger. The weights indicate the relative probability that a given character will exhibit the corresponding walking style. Typically, the sum of the style weights is 1.00. Accordingly, the styles menu  324  indicates that approximately 20% of the walking characters in the All crowd group perform a cool walk, 20% perform a fast walk, 20% perform a jog, and so on. In one embodiment, the styles shown in the styles menu  324  may be those styles of a given action which all character types in the corresponding crowd group may perform. The “jog” style is in bold type, indicating that the jog style of walking is selected. As a result, the alternatives menu  326  indicates the various alternatives of jogging that the walking characters in the All crowd group may perform. 
     The alternatives menu  326  specifies the third level category defining the motion of the selected beat and crowd group. The alternatives menu  326  indicates that the selected beat includes five alternatives for the jogging style of the walking action type—namely, alternative_1, alternative_2, alternative_3, and alternative_4. The weights indicate the relative probability that a given character will exhibit the corresponding alternative of jogging. Typically, the sum of the alternative weights is 1.00. Accordingly, the alternatives menu  326  indicates that approximately 25% of the jogging characters in the All crowd group perform each of the four jogging alternatives. In one embodiment, the alternatives shown in the alternatives menu  326  may be those styles of a given action which all character types in the corresponding crowd group may perform. In another embodiment, the alternatives shown in the alternatives menu  326  selects a particular motion clip corresponding to a specific motion definition for the selected action and style. The “alternative_2” style is in bold type, indicating that alternative 2 of the jogging style of walking is selected. 
     In one embodiment, various views for a beat may be specified, to further enable the user to express a complex probabilistic intention for crowd behavior that may otherwise be difficult to express. By using views, a beat may be edited for a specific character or a subset of characters associated with the currently loaded crowd. In other words, if a particular crowd includes horses, humans, and aliens, all in the same character group, the view may be set to “horses” to view and edit just the horse behavior. The weights shown in the actions menu  322 , the styles menu  324 , and the alternatives menu  326  may then reflect the relative weights for those actions, styles, and alternatives that apply to horses. Such weights shown for each of the actions menu  322 , the styles menu  324 , and the alternatives menu  326  may be normalized to sum to 1.0 for those characters included in the view. Alternatively, the view may be set to a particular alien, to view and edit just the behavior for the particular alien. The weights shown in the actions menu  322 , the styles menu  324 , and the alternatives menu  326  may then reflect the relative weights for those actions, styles, and alternatives that apply to the particular alien. Such weights shown for each of the actions menu  322 , the styles menu  324 , and the alternatives menu  326  may be normalized to sum to 1.0 for the particular alien included in the view. In each of these cases, edits are made using the relative weights for the current view. Corresponding weight changes are made to correctly reflect the relative weights of the crowd group as a whole. 
     In one example, a loaded crowd group could include horses, humans, and aliens. The available actions and weights could be Vaporize: 0.25, Abduct: 0.25, Trot: 0.25, and FeelEmpathy: 0.25. Actions could apply to only certain character types. So, Vaporize and Abduct could apply to only aliens, Trot could apply to only horses, and FeelEmpathy could apply to only humans. The view could be set to show and edit weights for only the aliens in the crowd group. The beat would then only show aliens, and the actions menu  322  would reflect the choices and weights as follows: Vaporize: 0.5, Abduct: 0.5. The user could then adjust the Vaporize weight to 0.75, reflecting that aliens would be more likely to select the Vaporize action. The weight for Abduct would be reduced to 0.25, so that the sum of the action weights for aliens would sum to 1.0. Correspondingly, the action weights for the crowd group as a whole would be adjusted to Vaporize: 0.375, Abduct: 0.125, Trot: 0.25, FeelEmpathy: 0.25, which sum to 1.0 and reflect the new relative action weights for the aliens, as edited. 
     In this manner, a view would reflect the selections available for a subset of characters in a crowd group. Changes in relative weights would reflect changes in statistical behavior for the characters included in the subset. These relative weight changes would span across the corresponding weights for the crowd group as a whole, while adjusting the relative frequencies within the weight span. When the beat is sampled during simulation to select actions for aliens, the view would be set to just those actions available for aliens, and the edited weights would maintain their relative values as established by the user. Accordingly, the aliens in the crowed group would be three times more likely to select the Vaporize action than the Abduct action. 
     The weights in the overall group of characters would also be maintained, as expressed in the overall group weights. As a result, editing for subgroups within a crowd group would be facilitated, while relative weights defining behavior across the entire crowd group would be maintained. 
     It will be appreciated that the system shown herein is illustrative and that variations and modifications are possible. For example, the edit playlist  320  is described as being associated with three categories specified as actions, styles, and alternatives. However, the edit playlist  320  could be implemented with any number of categories where each category is specified in any technically feasible manner. 
     Once a crowd is defined, an initial image frame may be created by an application program. Alternatively, a user may pose each character defined in the crowd in an initial position. Alternatively, an application program may create an initial frame, and the user may adjust the pose of one or more characters before starting the animation. Then, a crowd choreography application reads the variables as defined in the graphical user interface  300 , creates a specific set of motion directives for each character based on the variables, and animates the actors within the crowd. The crowd choreography application then generates a sequence of rendered image frames by applying the per-character directives to each of the respective characters in the crowd. The crowd choreography application may compute the positions of each character at each image frame using any technically feasible approach, including, without limitation, a simulation-based tool or a finite state machine model. 
       FIG. 4  illustrates a graphical user interface  400  for choreographing a crowd of animated characters, according to another embodiment of the invention. As shown, the graphical user interface  400  includes a loaded crowd window  302 , a crowd group selection window  304 , a behavior playlist  310 , and an edit playlist  420 . The loaded crowd window  302 , crowd group selection window  304 , behavior playlist  310 , and edit playlist  420  function substantially the same as set forth above in conjunction with  FIG. 4 , except as further described below. 
     As shown in  FIG. 4 , the “stand” action is in bold type in the actions menu  422  of the edit playlist  420 , indicating that the stand action is selected. As a result, the styles menu  424  indicates the various styles of standing that the characters in the All crowd group may perform. 
     The styles menu  324  indicates that the selected beat includes five styles of the standing action type—namely, blasé_glance, happy, left_to_right, listen, and nervous. The weights indicate that the relative probability that a given character will exhibit each of the corresponding standing styles is 0.322, 0.119, 0.119, 0.321, and 0.119, respectively. Accordingly, the styles menu  424  indicates that approximately 32.2% of the standing characters in the All crowd group perform a blasé glance standing poses, 11.9% perform a happy standing pose, 11.9% perform a standing pose, and so on. The “blasé_glance” style is in bold type, indicating that the blasé glance style of standing is selected. As a result, the alternatives menu  426  indicates the various alternatives of blasé glance that the standing characters in the All crowd group may perform. 
     The alternatives menu  426  indicates that the selected beat includes one alternative for the blasé glance style of the standing action type—namely, alternative_1. As there is only one alternative, the alternatives menu  426  indicates that 100% of the characters in the All crowd group performing the blasé glance style of standing perform alternative 1. The “alternative_1” style is in bold type, indicating that alternative 1 of the blasé glance style of standing is selected. 
       FIG. 5  illustrates a crowd choreography system  500  as may be implemented on the computing system  100  of  FIG. 1 , according to one embodiment of the invention. As shown, the crowd choreography system  500  includes a crowd choreography application  510 , an input mechanism  520 , an input data store  530 , and an output data store  540 . 
     The crowd choreography application  510  is a software program including instructions that, when executed, performs the techniques described above in conjunction with  FIGS. 2-4 . The crowd choreography application  510  may reside in system memory  104  where the instructions of the software program may be retrieved and executed by the CPU  102 . 
     The input mechanism  520  receives one or more input variables, such as a description including one or more beats, as described herein, and transmits the one or more input variables to the crowd choreography application  510 . For example, the input mechanism  520  could receive a definition of a group of actors including multiple character types and motion types, along with probabilities associated with each motion type, and sequencing information that defines transitions between one motion type and another. The input mechanism  520  may provide data to the crowd choreography application  510  via one or more input devices  108  in conjunction with the graphical user interface  300   400 . 
     The input data store  530  provides input data to the crowd choreography application  510 . As shown, the input data store  530  includes an animation library  532 . The animation library  532  includes motion clips for various character types and motion types. The motion clips may be organized by character type. For example, the animation library  532  could include a first set of motion clips for a type of bipedal characters, such as human characters. The animation library  532  could also include a second set of motion clips for a type of quadripedal characters, such as horses. The animation library  532  could also include a third set of motion clips for a type of quintapedal characters, and so on. For each type of characters, the animation library  532  may include motion clips associated with various motion types, where a motion type may include a particular action, a style for that action, and one of a set of alternatives for that action and style. 
     The motion clips in the animation library  532  may be created via any technically feasible approach, including, without limitation, by simulation, motion capture, and stochastic methods. The motion clips may be organized into character types, actions, styles, and alternatives via any technically feasible technique, including, without limitation, storing motion clips in a particular location in a hierarchical file system, using identifying file names for each motion clip, or inserting appropriate attributes within each motion clip. 
     The input data store  530  may also include any other input information for the crowd choreography application  510  including, without limitation, previously choreographed crowd descriptions (not shown). The input data store  530  may be located within the system disk  114 . 
     The output data store  540  provides output data from the crowd choreography application  510  for storage or display. As shown, the output data store  540  includes an image sequence  542  and error messages  544 . 
     The image sequence  542  includes a series of image frames produced by the crowd choreography application  510 , where each image frame includes a rendered image of each visible character in the crowd in a position based on the character&#39;s type, action, action style, and style alternative. The image frames in the image sequence  542  may be displayed on the display device  110  to view the crowd of characters in motion over time. 
     The error messages  544  include various errors and warnings generated by the crowd choreography application  510 . For example, the crowd choreography application  510  could encounter a sequence that calls for a transition from a first action to a second action, but no appropriate transition motion clip is found in the animation library  532 . In such cases, the crowd choreography application  510  would render the image sequence  542  showing an abrupt change from the first action to the second action. The crowd choreography application  510  would also store an appropriate message in the error messages  544  stating that a particular transition motion clip was not found. The error messages  544  would then be reviewed, and appropriate action could be taken, including, without limitation, changing the parameters of the sequence, or creating an appropriate transition motion clip. 
     The output data store  540  may also include any other output information for the crowd choreography application  510  including, without limitation, a copy of the currently loaded choreographed crowd description (not shown). The output data store  540  may be located within the system disk  114 . Alternatively, the output data store  540  may be located within a memory in a format suitable for display on the display device  110 . 
       FIG. 6  sets forth a flow diagram of method steps for choreographing an animated crowd with the system of  FIG. 5 , according to one embodiment of the invention. Although the method steps are described in conjunction with the systems of  FIGS. 1 and 5 , persons skilled in the art will understand that any system configured to perform the method steps, in any order, falls within the scope of the present invention. 
     A method  600  begins at step  602 , where the crowd choreography system  500  receives a set of beat sequences associated with a crowd group. In various embodiments, the crowd group may include all characters in a given crowd. Alternatively, the crowd group may include a subset of the characters in the crowd, where the subset includes characters of one or more character types. Alternatively, the crowd group may include a single character from the crowd. A beat sequence may include a single beat defined for the crowd group. Alternatively, the beat sequence could include two or more beats defined for the crowd group, along with transition points between the beats within a given beat sequence. 
     At step  604 , the crowd choreography system  500  selects a character that is included within the received crowd group. At step  606 , the crowd choreography system  500  selects a beat associated with the selected character, where the beat is included in one of the beat sequences in the set of beat sequences. If the selected character is a member of only one beat sequence in the set of beat sequences, then an active beat associated with that beat sequence is selected, based on a frame time, character position, or other data associated with the beat sequence. If the selected character is a member of more than one beat sequence in the set of beat sequences, then the crowd choreography system  500  selects the beat sequence with the highest priority of which the selected character is a member. The crowd choreography system  500  then selects an active beat associated with the selected beat sequence, based on a frame time, character position, or other data associated with the beat sequence. At step  608 , the crowd choreography system  500  selects a view for the selected beat, where the view indicates motion actions, styles, and alternatives available for the selected character. 
     At step  610 , the crowd choreography system  500  selects an action for the selected character. In one example, the crowd choreography system  500  could select an action for the character from a list of actions that all characters in the crowd group would be able to perform, based on the composite weights for the crowd group. In another example, the crowd choreography system  500  could select an action for the character from a list of actions that the characters in the view would be able to perform, based on the weights for the characters included in the view. The crowd choreography system  500  could select the action based on relative probabilities defined for the available actions for the character. 
     At step  612 , the crowd choreography system  500  selects a style of action for the selected character. In one example, the crowd choreography system  500  could select a style of action for the character from a list of action styles that all characters in the crowd group would be able to perform, based on the composite weights for the crowd group. In another example, the crowd choreography system  500  could select an action style for the character from a list of action styles that the characters in the view would be able to perform, based on the weights for the characters included in the view. The crowd choreography system  500  could select the action style based on relative probabilities defined for the available action styles for the character. 
     At step  614 , the crowd choreography system  500  selects an alternative of the action style for the selected character. In one example, the crowd choreography system  500  could select an alternative of the action style for the character from a list of action style alternatives that all characters in the crowd group would be able to perform, based on the composite weights for the crowd group. In another example, the crowd choreography system  500  could select an alternative of the action style for the character from a list of action style alternatives that the characters in the view would be able to perform, based on the weights for the characters included in the view. The crowd choreography system  500  could select the action style alternative based on relative probabilities defined for the available action style alternatives for the character. 
     At step  616 , the crowd choreography system  500  animates the selected character based on the selected action, style, and alternative. In one embodiment, the crowd choreography system  500  may determine the initial position for the selected character. In another embodiment, a user may direct the crowd choreography system  500  to place the selected character in an initial position. In yet another embodiment, the crowd choreography system  500  may determine an initial position for the selected character, and the user may adjust the initial position as desired. Once the initial position for the selected character is established, the crowd choreography system  500  animated the selected character. 
     At step  618 , the crowd choreography system  500  determines whether additional characters in the crowd remain that have not yet been animated. If no additional characters remain, then the method  600  terminates. 
     If additional characters remain, then the method  600  proceeds to step  604 , described above. 
     The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order or out of order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions. 
     In sum, computer-generated characters in a crowd are choreographed to perform various motions according to general directions that are organized as “beats.” Each character performs a specific action, style, and alternative for a given motion based on the relative probabilities established for those actions, styles, and alternatives. Multiple beats may form a beat sequence, where one beat ends and another beat begins based on whether a certain time in the shot is reached or when a character reaches a certain defined region in space. Multiple layers of beat sequence may exist, where most characters perform actions according to one beat, while a select few characters or a single character performs motion based on a beat sequence that is different than the beat sequence defined for the rest of the characters. Because the beats are defined in a high-level, generic way, animation directions do not have to be specified for the various types of actors—even when those actors comprise a variety of body morphologies. 
     While the foregoing is directed to embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow.