U.S. Pat. No. 10,864,434

The figures depict various embodiments of the present disclosure for purposes of illustration only.

DETAILED DESCRIPTION

In the following description of embodiments, numerous specific details are set forth in order to provide more thorough understanding. However, note that the embodiments may be practiced without one or more of these specific details. In other instances, well-known features have not been described in detail to avoid unnecessarily complicating the description.

Embodiments relate to simulating the movements of three or more bodies connected on a cord for use in real-time videogame applications. The state of the bodies such as position, velocity, and orientation of the bodies connected by a cord are determined in single pass without iteration. For a given time step and the state of the bodies in the time step, the Jacobian matrix for the connected bodies is calculated. The tension in the cord is calculated based on the Jacobian matrix. From the tension, the state of the bodies for the next time step is obtained.

Among other advantages, embodiments enable simulation of three or more bodies connected by a cord in an accurate and efficient manner without increasing computational resource (e.g., processor cycles or memory space) involved in the simulation. By determining and calculating the Jacobian matrix for the connected bodies, a tension in the cord can be calculated in a single processing pass without iterative processes.

Embodiments are described herein with reference to the figures where like reference numbers indicate identical or functionally similar elements. Also in the figures, the left most digits of each reference number corresponds to the figure in which the reference number is first used.

FIG. 1is a block diagram of a computing device100for creating and displaying a game environment, according to an embodiment. The game environment described herein involves an emulation of a physical environment. Objects in the game environment may be modeled such that they move as they would in the physical environment. In some embodiments, the objects in the game environment include human or creature characters. Furthermore, a game environment may be a playable environment in a video game. For example, a user controls a character that interacts with objects in the game environment.

Illustrated inFIG. 1are at least a central processing unit (CPU)102, a graphics processing unit (GPU)104, memory106, display controller108, user interface110, and sound controller112. These modules102through12communicate via a bus120. Some embodiments of the computing device100have different and/or other components than those shown inFIG. 1.

The computing device100may be a personal computer (PC), a video game console, a tablet PC, a smartphone, or any machine capable of executing instructions (sequential or otherwise) that specify actions to be taken by that device. The computing device100can operate as a standalone device or a connected (e.g., networked) device that connects to other machines. Furthermore, while only a single device is illustrated, the term “device” shall also be taken to include any collection of devices that individually or jointly execute instructions to perform any one or more of the methodologies discussed herein.

The memory106is a machine-readable medium on which is stored instructions (e.g., software) embodying any one or more of the methodologies or functions described herein. For example, the memory106may store instructions that when executed by the CPU102configures the CPU102to perform the method500, described below in detail with reference toFIG. 5. Instructions may also reside, completely or at least partially, within the processors102,104(e.g., within a processor's cache memory) during execution thereof by the computing device100.

The term “machine-readable medium” should be taken to include a single medium or multiple media (e.g., a centralized or distributed database, or associated caches and servers) able to store instructions. The term “machine-readable medium” shall also be taken to include any medium that is capable of storing instructions for execution by the device and that cause the device to perform any one or more of the methodologies disclosed herein. The term “machine-readable medium” includes, but is not limited to, data repositories in the form of solid-state memories, optical media, and magnetic media.

The CPU102is a processing circuitry configured to carry out the instructions stored in the memory106. The CPU102may be a general-purpose or embedded processor using any of a variety of instruction set architectures (ISAs). Although a single CPU is illustrated inFIG. 1, the computing device100may include multiple CPUs102. In multiprocessor systems, each of the CPUs102may commonly, but not necessarily, implement the same ISA.

The GPU104is a processing circuit specifically designed for efficient processing of graphical images. The GPU104may render objects to be displayed into a frame buffer (e.g., one that includes pixel data for an entire frame) based on instructions from the CPU102. The GPU104may include one or more graphics processors that may execute graphics software to perform a part or all of the graphics operations.

The display controller108is a circuit that generates a video signal using graphical data from the GPU104. For example, the display controller108drives a display device (e.g., a liquid crystal display (LCD) and a projector). As such, a game environment can be displayed as images or a video sequence through the display controller108.

The sound controller112is a circuit that provides input and output of audio signals to and from the computing device100. For purposes of a game environment, the sound controller112can provide audio signals that align with actions and objects in the game environment.

The user interface110is hardware, software, firmware, or a combination thereof that enables a user to interact with the computing device100. The user interface110can include an alphanumeric input device (e.g., a keyboard) and a cursor control device (e.g., a mouse, a trackball, a joystick, a motion sensor, or other pointing instrument). For example, a user uses a keyboard and mouse to control a character's action within a game environment generated by the computing device100.

The computing device100executes computer program modules for providing functionality described herein. As used herein, the term “module” refers to computer program instructions and/or other logic used to provide the specified functionality. Thus, a module can be implemented in hardware, firmware, and/or software. In some embodiments, program modules formed of executable computer program instructions are loaded into the memory106, and executed by the CPU102or the GPU104. For example, program instructions for the method500describe herein can be loaded into the memory106, and executed by the CPU102and GPU104.

FIG. 2is a block diagram of software modules in the memory106of the computing device100, according to an embodiment. The memory200may store, among other modules, a game system210, a physics system220, an animation system230, a sound module240, a graphics rendering module250, and an operating system (OS)260. The physics system220, animation system230, sound module240, and graphics rendering module250collectively form a game engine. The memory200may include other modules not illustrated inFIG. 2.

The game system210performs operations212A through212N (collectively referred to as “the operations212”) to generate the game environment. Specifically, the game system210performs these operations to instantiate various objects and simulate interactions between the objects within the game environment. The operations212are refer to computing operation that results in changes in various parameters (e.g., state of objects and user status) based upon certain events (e.g., user interaction, expire of time, and triggers occurring in the game). Some operations212are associated with one or more objects in the environment and/or one or more actions associated with the objects. Examples of operations include a catapult launching a rock, a character running, fluid flowing, an arrow flying, a door opening, etc. While some operations212have relatively simple responses (e.g., door opening), other operations may need to be simulated by the physics system220(e.g., movement of connected bodies). When executing the operations212, the game system210may communicate with the components of the game engine (e.g., physics system220) through application programming interfaces (APIs). At least one of these operations212involves simulating three or more bodies connected by a cord. The state of these connected bodies may change in response to forces or impulse applied to the bodies.

The physics system220models and simulates the dynamics of objects in the game environment. After an operation212is initiated in the game system210, the physics system220models how the action affects the object associated with the operation212. For example, the physics system models a rock as it rolls down a hill. Depending on the action and object, other objects and actions may become associated with the action or object. For example, a thrown rock may knock over another object. This may trigger a new operation212where the object is hit by the rock.

For this purpose, the physics system220may include, among other modules, an n-body constraint module222, a 2-body constraint module224, and a collision system226. The physics system220may also include other modules for performing various specific simulation tasks.

The 2-body constraints module224is used to emulate two objects interacting with each other on a cord. For example, the 2-body constrains module224can model the movement of a pendulum. The 2-body constrains module224can simulate three or more bodies interacting on a cord, for each simulation time step, by iteratively modeling interactions of different sets of two bodies within the group of connected bodies. Due to the iterative modeling for each simulation time step, when three or more bodies are simulated on the 2-body constraints module, more computing resources and time are consumed than the n-body constraints module222.

The n-body constraints module222is a module that simulates the movement of three or more bodies connected by a cord using a single processing pass for a simulation time step. The n-body constraints module222determines the state of the bodies in each simulation time step as the bodies or the cord experiences external forces or impulses. The state of the bodies can include a position, linear velocity, angular velocity, mass, inertia tensor, and an orientation of each body. Additionally the n-body constraints module222can perform simulations under various constraints, such as fixing one or more bodies in space, allowing bodies to slide along the cord, etc. The n-body constraints module222is further described with reference toFIG. 4.

The collision system226simulates collisions of objects in the game environment. The collision system226can simulate bodies modeled by the n-body constraints module222. For example, the collision system226can determine the collision dynamics of a rock hitting one or more bodies constrained by a cord.

Some operations212of the game system210may invoke more than one of the modules in the physics system220. For example, when an operation212involves three or more objects sliding on a string and colliding with each other, the operation212may use both n-body constraints module222and the collision system226to simulate the movements of the n-body before and after collision. Such operations212may involve iterative processing between n-body constraints module222and the collision system226for a single simulation time step.

The animation system230is a module that performs kinematic animation of objects or the game environment based on the operations212from the game system210. For example, if an operation212specifies that a robotic arm is moving, the animation system animates the kinematics of the arm movement.

The animation system230may include any number of specialized modules, such as pose characteristics module232and cloth system233, which perform specific animation tasks. The pose characteristics module232animates character appearance and movement in the game environment. The cloth system233animates cloth movement in the game environment. The cloth can include cloth worn by a character or attached to objects. The pose characteristics module232and cloth system233(among other animation modules) may animate interactions between objects within the game environment, such as a cloth interacting with a system of connected bodies.

The sound module240generates sounds corresponding to actions occurring in the game environment. Animation data from the animation system230may be sent to the sound module240to enable the sound module240to produce sound.

The graphics rendering module250renders graphics from the animation system230to generate an image of the game environment. For example, the graphics rendering module250receives a scene file from the animation system230. The graphics rendering module250sends graphical data to the GPU104to render images on a display device via the display controller108.

The operating system (OS)260manages computer hardware and software resources. Specifically, the OS260acts as an intermediary between programs and the computer hardware. For example, the OS260can perform basic tasks, such as recognizing input from the user interface110and sending output to the display controller108.

FIG. 3is a conceptual diagram of bodies B1through Bnconnected by a cord302, according to an embodiment. The number of connected bodies is three or more (i.e., n≥3). Each body is indicated by Bifor 1≤i≤n. Each body can be any object in the game environment, and the cord302can be any material that connects the bodies together, such as rope or string. AlthoughFIG. 3illustrates the end bodies, B1and Bn, as being fixed in space, one or both of bodies B1and Bncan be movable.

The tension in the cord302can be described as follows:

λ=-J⁢⁢VJ⁢⁢M-1⁢JT⁢t(1)
where λ is the tension in the cord302, J is the Jacobian Matrix, V is the velocity matrix, t is the time step, and M is a mass matrix. V describes both linear viand angular wivelocities for each body. For example, three bodies are expressed as follows:

V=[V1V2V3]=[v1ω1v2ω2v3ω3](2)
M is a sparse matrix that includes the mass of each body Miand the Inertia Tensor of each body Ii. For example, for three bodies

M=[M1⁡(Identity)000000I1000000M2⁡(Identity)000000I2000000M3⁢⁢Identity000000I3](3)
As such, each body can have a different or same mass as the other bodies.

To determine the Jacobian matrix for the connected bodies B1through Bn, normalized direction vectors are determined as follows:

di=(Pi,i+1-Pi+1,i)(Pi,i+1-Pi+1,i)·(Pi,i+1-Pi+1,i)(4)
where Pijis a position vector, i is an index identifying the body, and j is an index identifying the location on the body where the cord302is located. For example, for i=1

d1=(P12-P21)(P12-P21)·(P12-P21)(5)
For n bodies, there are (n−1) number of normalized direction vectors

When n bodies are connected by a cord302of length L (e.g., as seen inFIG. 3), the total length can be calculated using the positions of the bodies as follows:
L=∥P12−P21∥+∥P22−P31∥+∥P32−P41∥+ . . . ∥P(n−1)2−P(n)1∥  (6)
By differentiating, Equation (6) becomes
0=d1·(V12−V21)+d2·(V22−V31)+d3·(V32−V41)+ . . .dn·(V(n−1)2−Vn1)  (7)
where Vij=vi+ωi×rijand rijis a position vector originating from the center of the ithbody and directed to position Pij(e.g., see vectors r41and r42inFIG. 3). As a result, equation (7) can be expressed as
0=d1·(v1+ω1×r12−v2−ω2×r21)+d2·(v2+ω2×r22−v3−ω3×r31)+ . . . +dn·(vn−1+ωn−1×r(n−1)2−vn−ωn×rn1)  (8)
After rearranging terms to isolate the linear and angular velocity components, the equation becomes
0=d1Tv1+d1TR12ω1+(d2−d1)Tv2+(d2TR22−d1TR21)ω2+(d3−d2)Tv3+(d3TR32−d2TR31)ω3+ . . . −dnTvn−dnTRn1ωn(9)
where Rij is the negated cross product skew symmetric matrix of rij

Rij=[0rz-ry-rz0rxry-rx0](10)

Thus, the Jacobian matrix for the n bodies is expressed as follows:

J=[d1(d1T⁢R12)Td2-d1(d2T⁢R22-d1T⁢R21)Td3-d2(d3T⁢R32-d2T⁢R31)T⋮dm-dm-1(dmT⁢Rm⁢⁢2-dm-1T⁢Rm⁢⁢1)T⋮-dn-1(-dn-1T⁢Rn⁢⁢1)T]T(11)
for 1<m<n. For example, for three connected bodies (n=3), the Jacobian matrix is J=[d1T, d1TR12, (d2−d1)T, d2TR22−d1TR21, −d2T, −d2TR31]. Therefore, referring to Equation (1), the tension in the cord302can be calculated if the mass matrix M and velocity matrix V are known, and if the Jacobian matrix J is determined by calculating the linear components d1, d2, . . . , dn−1and angular components d1TR12, d2TR22−d1TR21, . . . , −dn−1TRn1of the n bodies.

Depending on the modeled physical system, additional constraints may be included in the Jacobian matrix. Additional constraints may include, for example, the flexibility of the cord, the stiffness of the cord, fixing bodies on the cord, allowing bodies to slide along the cord, the number of bodies or points on the cord that are fixed in space, and the mass of the cord. For example,
∥P12−P21∥+∥P22−P31∥−∥P32−P41∥−∥P42−P51∥−∥P52−P61∥=L1−L2(12)
is a constraint on a set of six connected bodies (n=6), where B3is constrained on the cord, L1is the length of the cord from B1to B3, and L2is the length of the cord from B3to B6.

FIG. 4is a block diagram illustrating modules of the n-body constraints module222ofFIG. 2, according to an embodiment. As discussed above with reference toFIG. 2, based upon an initial state of n connected bodies and forces and/or impulses experienced by the bodies, the n-body constraint module222updates the state of the bodies by simulation as described above with reference to equations (1) through (12). The n-body constraint module222may include, among other modules, an initialization module408and an update module410. Furthermore, the n-body constraints module222receives constraint parameters402and external forces404from the game system210to produces output406. In some embodiments, the n-body constraints module222has different and/or other modules than those shown inFIG. 4.

Using the received constraint parameters402and external forces404(or impulses), the initialization module408determines and assigns initial values to variables to be used by the update module410to determine the updated state of the bodies. The initialization module408also receives the initial state of the bodies (not seen inFIG. 4). In some embodiments, the initialization module408receives the state of the bodies from the update module410. As described above with reference toFIG. 3, the state of the bodies can be the values for the velocity matrix V, the position vectors Pij, normalized direction vectors di, mass matrix M, and inertia tensors Ii.

The constraint parameters402include physical properties of the connected bodies. The constraint parameters402may include, for example, one or more of the following: the number of bodies connected by the cord, the length of the cord, the distance between each body on the cord, whether each body can slide or is fixed along the cord, the flexibility of the cord, and the stiffness of the cord. For example, as described above with reference toFIG. 3, the constraint parameters402provide values for n and L. Generally, these parameters are time invariant, however, time variant parameters may also be used. Time variant parameters may be, for example, the distance between each body on the cord changes if the bodies are not fixed on the cord.

The external forces404include impulses (i.e., momentum transfers) or forces experienced by the connected bodies. For example, the bodies experience a constant downward force from gravity while, at a given time step, several bodies receive an impulse from a character colliding with the bodies. The external forces404may be time variant at each simulation time step. The forces may include, for example, forces from wind, water, and gravity. Impulses may include, for example, collisions or other interactions with objects. In some embodiments, the external forces404contribute to values of the velocity matrix V.

Using the assigned values from the initialization module408, the update module410updates the state of the bodies. Specifically, the update module410determines the Jacobian matrix for the physical system described by the input402,404and determines the tension in the cord that satisfies Equation (1). In some embodiments, the tension in the cord302is an impulse. Using the tension in the cord, the state of the bodies is calculated and updated.

The output406indicates the updated state of the bodies. The output406may be used by any number of systems or modules in the memory200. For example, the output406is sent to the animation system230so that the movement of the bodies and cord can be animated within the game environment. Additionally, the output406can be sent to the collision system226to determine if a collision between the connected bodies or another object occurs.

FIG. 5is a flowchart illustrating a method for simulating movement of connected bodies, according to one embodiment. The n-body constraint module receives502constraint parameters associated with a set of n-bodies connected by a cord. The constraint parameters describe physical properties of the bodies, such as movement of the bodies. These can include the number of bodies connected by the cord, the length of the cord, the distance between each body on the cord, whether each body can slide or is fixed along the cord, the flexibility of the cord, and the stiffness of the cord.

The n-body constraint module receives504the state of the bodies for a current time step. The state of the bodies describes at least one of a position, linear velocity, angular velocity, mass, inertia tensor, and an orientation of each body. The current time step is a discrete time variable within the game environment. To model the movement of the connected bodies, the state of the bodies must be updated for a next time step.

The n-body constraint module receives506external force parameters or external impulse parameters for the current time step. The external force parameters are indicative of external forces applied to the connected bodies (e.g., wind). The external impulse parameters are indicative of external impulses applied to the connected bodies.

The n-body constraint module determines508the Jacobian matrix. The Jacobian matrix is determined based on the previously received constraint parameters and the state of the bodies for the current time step. In some embodiment, the values of the Jacobian matrix are updated for each time step.

The n-body constraint module determines510the tension in the cord for the current time step. The tension is based on the external force parameters, the external impulse parameters, and the Jacobian matrix. In some embodiments, the tension in the cord is an impulse. In some embodiments, the tension is determined by satisfying Equation (1).

The n-body constraint module updates512the state of the bodies for the next time step subsequent to the current time step. The updated state of the bodies is based on the determined tension at the current time step.

In some embodiments, representations of the bodies and the cord at the next time step are displayed on a display device. In some embodiments, the next time step is updated to the current time step and steps “receiving506external force parameters” through “updating512the state of bodies for the next time step” are repeated. In some embodiments, such repetitions are performed in real-time.

The steps illustrated inFIG. 5may be performed in different orders, for example step506can come after step512. Furthermore, the method may include different, additional, or fewer steps than what are illustrated inFIG. 5.

Although embodiments described above were explained primarily in reference to a game system, the simulation of n-bodies connected by a cord can be applied to other applications such as engineering software and educational software, such as flight and spacecraft training software or surgery simulation software. Additionally, embodiments can be applied to research applications, such as simulating molecular dynamics and protein folding.

While particular embodiments and applications have been illustrated and described, it is to be understood that the invention is not limited to the precise construction and components disclosed herein and that various modifications, changes and variations which will be apparent to those skilled in the art may be made in the arrangement, operation and details of the method and apparatus disclosed herein without departing from the spirit and scope of the present disclosure.