ANIMATING OBJECTS USING THE HUMAN BODY

[0001] Computer animation is typically a very time consuming activity requiring computer graphics (CG) expertise and use of specialist software tools and considerable computing power. First a model of an object will be generated in the form of a 3D mesh. A CG animator will then generate and embed a skeleton inside the 3D mesh of the object being animated and paint individual bone weights onto each vertex. At runtime, motion capture data or an inverse kinematics engine drives the bones of the character, which then transforms the mesh. Depending upon the level of experience of the user and the complexity of the object being animated, this process may take hours or days.

[0002] The embodiments described below are not limited to implementations which solve any or all of the disadvantages of known methods of computer animation.

[0003] The following presents a simplified summary of the disclosure in order to provide a basic understanding to the reader. This summary is not an extensive overview of the disclosure and it does not identify key/critical elements or delineate the scope of the specification. Its sole purpose is to present a selection of concepts disclosed herein in a simplified form as a prelude to the more detailed description that is presented later.

[0004] Methods of animating objects using the human body are described. In an embodiment, a deformation graph is generated from a mesh which describes the object. Tracked skeleton data is received which is generated from sensor data and the tracked skeleton is then embedded in the graph. Subsequent motion which is captured by the sensor result in motion of the tracked skeleton and this motion is used to define transformations on the deformation graph. The transformations are then applied to the mesh to generate an animation of the object which corresponds to the captured motion. In various examples, the mesh is generated by scanning an object and the deformation graph is generated using orientation-aware sampling such that nodes can be placed close together within the deformation graph where there are sharp corners or other features with high curvature in the object.

[0005] Many of the attendant features will be more readily appreciated as the same becomes better understood by reference to the following detailed description considered in connection with the accompanying drawings.

[0017] Like reference numerals are used to designate like parts in the accompanying drawings.

[0018] The detailed description provided below in connection with the appended drawings is intended as a description of the present examples and is not intended to represent the only forms in which the present example may be constructed or utilized. The description sets forth the functions of the example and the sequence of steps for constructing and operating the example. However, the same or equivalent functions and sequences may be accomplished by different examples.

[0019] As described above, CG animation is typically limited to experienced animators using specialist tools and hardware. In contrast, the methods and systems described below can be used by anyone (adults and children), including those with little or no CG experience, to create animations in 2D or 3D using consumer hardware (e.g. a PC or games console). The methods use the human body for input and enable rapid and intuitive generation of animated sequences. Furthermore, some of the methods described below are adapted to handle scenarios which are challenging even for specialist animation tools, such as non-humanoid meshes and incomplete surfaces produced by 3D scanning. The applications of the methods and systems described below include interactive storytelling, videoconferencing and gaming and further examples are described below.

[0020] FIG. 1 shows a flow diagram 100 of an example method of animating an object. Alongside the flow diagram 100, FIG. 1 shows a sequence of images 101-106 which illustrate the method in action. The method receives as an input (in block 110) a mesh defining the object to be animated. This object may be referred to as the ‘target’ and may be in 2D or 3D. The mesh may be obtained in any way (e.g. by scanning the object) or from any source (e.g. downloaded off the internet). The mesh may be unstructured data (e.g. unstructured 3D data), for example, where the mesh is obtained by scanning in an object; however, the method works with any data including closed 3D models or geometrically complex off the shelf models. Image 101 shows an example target in the form of a chair. The input mesh is a static representation of the object which is to be animated.

[0021] A deformation graph is generated automatically from the input mesh (block 112) and this deformation graph is used as a proxy for the mesh of the object. The deformation graph is a deformable model of the object, comprising nodes and undirected edges. The nodes are arranged in a shape which approximately conforms to the shape of the object and the undirected edges connect nodes with local dependencies and provide a means for information exchange so that a globally consistent deformation can be found. Image 102 shows an example deformation graph. There are a number of ways in which this deformation graph may be generated (in block 112), for example, by traversing the vertices of the input mesh or by distributing nodes over the surface of the object and then repeatedly removing nodes within a given radius of a randomly chosen node until a desired sampling density is achieved. In some examples, the deformation graph may be the same as the input mesh, in which case, the generation of the deformation graph (in block 112) comprises passing the received input mesh to the next stage of the method.

[0022] As described above, the animation method uses the body of the user as an input and body tracking data for the user is acquired using a sensor and received from the sensor (in block 114). Any suitable sensor may be used, including but not limited to, non-contact sensors such as camera-based systems (e.g. Kinect™, Wii™) and marker-based tracking systems (e.g. using Vicon™ markers) and contact-based sensors such as a multi-touch device. The body tracking data defines positions of one or more points on a body and any type of body tracking data may be used which enables correspondences between the sensor data and nodes in the deformation graph to be determined. Examples include, but are not limited to, tracked human skeleton data (e.g. tracked patches or markers on the body) or use of a model-based tracking approach.

[0023] Image 103 shows an example tracked human skeleton which may be generated from or comprise the body tracking data. To enable the body of the user to be used as an input, this tracked skeleton (as defined by the body tracking data received in block 114) is attached to the deformation graph (block 116). As the deformation graph is a representation of the input mesh, the tracked skeleton may also be considered to be attached to the mesh. The attachment of the skeleton to the graph may be performed automatically without user input or in response to voice commands from the user, as is described in more detail below. A visual display may be provided to the user at this attachment stage so that they can position their body such that it approximates the shape of the object to be animated (e.g. such that their tracked skeleton approximately aligns with the object) and so the attachment of the skeleton to the graph is done in a more intuitive manner. Image 104 shows the overlapping of the skeleton 107 and the chair 108.

[0024] Once the tracked skeleton and the graph are connected, the deformation graph is transformed in real-time as movement of the skeleton is tracked (block 118). For example, as the user moves around in front of the sensor, the motion of the user will be tracked. This motion is then used to transform the deformation graph in a corresponding manner in real-time (i.e. as the user moves). The transformation of the deformation graph (in block 118) involves solving for the optimal transformations on the deformation graph that are smooth, feature-preserving and satisfy the user's motion constraints. This is described in more detail below.

[0025] Once the transformations have been computed on the deformation graph (in block 118), these transformations are applied to the input mesh and the corresponding motion (i.e. the animation) of the object is rendered for display to the user (block 120). Images 105 and 106 show two example images from an animation of the chair. The first image 105 shows the chair walking and the second image 106 shows the chair jumping. These images are generated, using the method described above, when the user walks and jumps respectively.

[0026] As described above, the attachment of the skeleton to the graph and subsequent transformation of both the graph and the mesh (blocks 114-120) are performed in real-time at runtime. The attachment of the skeleton to the graph is performed once, while the transformations (in blocks 118-120) are performed per frame (e.g. at a frame rate of 30 Hz). In contrast, although the deformation graph may be generated (in block 112) at runtime, alternatively this may be considered a pre-processing step and may be performed in advance. As described above, this pre-processing step (block 112) is entirely automatic.

[0027] FIG. 2 shows an alternative representation of the flow diagram shown in FIG. 1. In the example shown in FIG. 2, the method is divided into three blocks 202, 204, 206. The Embed stage (block 202) takes a 3D geometry as input (i.e. the input mesh) and generates the deformation graph (e.g. as in blocks 110-112 in FIG. 1). The Skeleton Tracker (block 204) detects human performance (e.g. the user standing still or motion of the user) and generates the body tracking (or skeleton) data. The Warp stage (block 206) takes the 3D geometry, body tracking data and the deformation graph as inputs, attaches the skeleton to the graph and then performs the transformations of both the deformation graph and 3D geometry based on the tracked changes in the body tracking data, i.e. the motion captured by the Skeleton Tracker (e.g. as in blocks 114-120 in FIG. 1).

[0028] The methods shown in FIGS. 1 and 2 and described above may be implemented using the system shown in FIG. 3. FIG. 3 illustrates various components of an exemplary computing-based device 300 which may be implemented as any form of a computing and/or electronic device, and in which embodiments of the methods described herein may be implemented. As described above, the computing-based device 300 may be a consumer computing-based device, such as a computer (e.g. desktop, laptop or tablet computer), games console or smart phone.

[0029] Computing-based device 300 comprises one or more processors 302 which may be microprocessors, controllers or any other suitable type of processors for processing computer executable instructions to control the operation of the device in order to perform the animation methods described herein. In an example, the computing-based device 300 may comprise at least one CPU and at least one GPU. In some examples, for example where a system on a chip architecture is used, the processors 302 may include one or more fixed function blocks (also referred to as accelerators) which implement a part of the method of animating objects in hardware (rather than software or firmware). Platform software comprising an operating system 304 or any other suitable platform software may be provided at the computing-based device to enable application software 306 to be executed on the device.

[0030] The computer executable instructions running on the computing-based device 300 (and which may be examples of application software) may include a pre-processing module 308, a warp module 310 and a skeleton tracker module 312. The pre-processing module 308 (which may correspond to the Embed stage, block 202 in FIG. 2) comprises computer executable instructions which, when executed, cause the processor to generate a deformation graph from an input mesh. The warp module 310 comprises computer executable instructions which, when executed, cause the processor to attach a skeleton to the graph and to transform the graph and the input mesh in response to motion of a tracked skeleton. The body tracking (or skeleton) data is provided to the warp module 310 by the skeleton tracker module 312 which processes data received from a sensor 314 (e.g. via input/output controller 315) to generate the body tracking data. Although FIG. 3 shows the skeleton tracker module 312 within the computing based device, in other examples, the skeleton tracker module 312 may form part of a separate sensor system which also comprises the sensor 314. In examples where the sensor 314 is a Kinect™ camera, the skeleton tracker module 312 may use the skeletal tracker in the Kinect™ SDK which gives a prediction of 20 joint positions on the human body (e.g. such that the body tracking data comprises these 20 predicted joint positions).

[0031] The computer executable instructions may be provided using any computer-readable media that is accessible by computing based device 300. Computer-readable media may include, for example, computer storage media such as memory 316 and communications media. Computer storage media, such as memory 316, includes volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, RAM, ROM, EPROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other non-transmission medium that can be used to store information for access by a computing device. In contrast, communication media may embody computer readable instructions, data structures, program modules, or other data in a modulated data signal, such as a carrier wave, or other transport mechanism. As defined herein, computer storage media does not include communication media. Therefore, a computer storage medium should not be interpreted to be a propagating signal per se. Propagated signals may be present in a computer storage media, but propagated signals per se are not examples of computer storage media. Although the computer storage media (memory 316) is shown within the computing-based device 300 it will be appreciated that the storage may be distributed or located remotely and accessed via a network or other communication link (e.g. using communication interface 318).

[0032] The memory 316 may further comprise a data store 319 for storing data. Any type of data may be stored in the data store 319 and in an example, the data store 319 may be used to store one or more of: the input mesh (as received in block 110 of FIG. 1), body tracking data (as received in block 114 of FIG. 1), mappings or constraints which are created when attaching the skeleton to the deformation graph (e.g. in block 116 of FIG. 1) and transformations to the deformation graph (e.g. as calculated in block 118 of FIG. 1). The data store 319 may also be used to store the generated animations.

[0033] The input/output controller 315 receives data from the sensor 314 (or sensing system which comprises sensor 314) which may be external to the computing-based device 300 or may be integrated within the device 300. The sensor 314 may use any suitable technology and may, for example, comprise a camera. The input/output controller is also arranged to output display information to a display device 320 which may be separate from or integral to the computing-based device 300. The display information may provide a graphical user interface and is used to display the animation which is generated by the methods described herein and to display any graphical user interface which is used to assist the user in aligning their body to the object (as displayed) or otherwise to assist in the attaching of the skeleton to the object which is being animated.

[0034] The sensor 314 operates as a user input device and as described above, may form part of a sensing system. This sensing system may comprise multiple sensors 314. The input/output controller 315, which receives data from the sensor(s) 314 may be arranged to receive and process input from one or more additional devices, which may include one or more additional user input devices (e.g. a mouse, keyboard, camera, microphone or other sensor). The sensor 314 is arranged to detect user gestures or other user actions and provides a natural user interface (NUI). In some examples the sensor 314 or other user input device may detect voice input (e.g. to influence or trigger the attachment of the skeleton to the graph). In an embodiment the display device 320 may also act as the user input device if it is a touch sensitive display device. The input/output controller 315 may also output data to devices other than those shown in FIG. 3, e.g. a locally connected printing device, a second display device, etc.

[0035] As described above, the sensor 314, input/output controller 315, display device 320 and optionally any other user input device may comprise NUI technology which enables a user to interact with the computing-based device in a natural manner, free from artificial constraints imposed by input devices such as mice, keyboards, remote controls and the like. Examples of NUI technology that may be provided include but are not limited to those relying on voice and/or speech recognition, touch and/or stylus recognition (touch sensitive displays), gesture recognition both on screen and adjacent to the screen, air gestures, head and eye tracking, voice and speech, vision, touch, gestures, and machine intelligence. Other examples of NUI technology that may be used include intention and goal understanding systems, motion gesture detection systems using depth cameras (such as stereoscopic camera systems, infrared camera systems, RGB camera systems and combinations of these), motion gesture detection using accelerometers/gyroscopes, facial recognition, 3D displays, head, eye and gaze tracking, immersive augmented reality and virtual reality systems and technologies for sensing brain activity using electric field sensing electrodes (EEG and related methods).

[0036] The communication interface 318 may be used to access remote storage, to receive an input mesh and/or for any form of communication via a network 322. In some examples, the sensor 314 may be located remotely from the computing-based device 300 which is performing the animation method, in which case the computing-based device 300 may communicate with the sensor 314 via the communication interface 318 instead of via the input/output controller 315. In an example scenario, the computing-based device 300 may be a cloud-based server with the sensor 314 and display device 320 located in the same place as the user. In this scenario, the computing-based device 300 will communicate with both the sensor 314 and the display device 320 via the communication interface 318 instead of via the input/output controller 315.

[0037] Although the methods of animation described herein are shown in FIG. 3 as being implemented using software modules 308-312, alternatively, or in addition, the functionality described herein can be performed, at least in part, by one or more hardware logic components. For example, and without limitation, illustrative types of hardware logic components that can be used include Field-programmable Gate Arrays (FPGAs), Program-specific Integrated Circuits (ASICs), Program-specific Standard Products (ASSPs), System-on-a-chip systems (SOCs), Complex Programmable Logic Devices (CPLDs).

[0038] The following paragraphs describe each of the blocks of the flow diagram shown in FIG. 1 in more detail and provide various examples, variations and alternative implementations which may be used. It will be appreciated that aspects described with respect to one block may be combined in any way with aspects described with respect to any other blocks in the method.

[0039] The input mesh, which is received in block 110 of FIG. 1, comprises data (e.g. 3D unstructured data) which may be generated or obtained in any way. In various examples, the input mesh may be downloaded from the internet or may be generated by scanning the object (e.g. using the same sensor 314 which is also used in tracking the user's motion). The methods described herein can use arbitrary meshes, and these meshes need not be complete and may be polygon soups (including incomplete polygon soups), triangle meshes, point clouds, volumetric data, watertight 3D models, etc. In various examples, the input mesh may be generated from a real-world non-human (e.g. inanimate) object of reasonable physical size and surface reflectance.

[0040] In an example, the input mesh may be generated using a technique known as KinectFusion and described in ‘KinectFusion: Real-time 3D reconstruction and interaction using a moving depth camera’ by Izadi et al and published in UIST 2011. This technique uses a Kinect™ camera as the sensor and may be described with reference to FIG. 4, which shows a flow diagram 400 of an example method of generating an input mesh. The Kinect™ camera uses a structured light technique to generate real-time depth maps containing discrete range measurements of the physical scene. This data can be reprojected as a set of discrete 3D points (or point cloud). It will be appreciated that in other examples, alternative depth cameras may be used.

[0041] As shown in the first flow diagram 400 in FIG. 4, this example method of generating an input mesh, comprises three stages (blocks 401-403). The 3D reconstruction stage (block 401) estimates the 6-DoF (Degree of Freedom) pose of the moving Kinect™ camera while the user scans the object with the camera, and fuses depth data continuously into a regular 3D voxel grid data structure which may be stored on a GPU. Surface data is encoded implicitly into voxels as signed distances, truncated to a predefined region around the surface, with new values integrated using a weighted running average. The global pose of the moving depth camera is predicted using point-plane ICP (Iterative Closest Point), and drift is mitigated by aligning the current raw depth map with the accumulated model (instead of the previous raw frame). The system produces a 3D volumetric reconstruction of the scene accumulated from the moving depth camera. It will be appreciated that alternatively, the depth camera may remain static and the user may move the object in front of the camera to create the 3D volumetric reconstruction. It is not necessary for the scan to be complete (e.g. covering all sides of the object) because the methods described herein can accommodate input meshes which are incomplete scans (e.g. where one or more sides of the image are missing).

[0042] The 3D reconstruction which is generated (in block 401) is, in many examples, of the whole scene (e.g. the object which is to be animated, objects around it and the background). The second stage of this example method of generating an input mesh involves segmenting the object of interest from the scene (block 402). To extract a specific object from the full 3D reconstruction (generated in block 401), any suitable segmentation method may be used and two examples are described below. In examples where the 3D reconstruction only comprises the object itself, the segmentation stage (block 402) may be omitted.

[0043] The first segmentation method, which is described in the KinectFusion paper referenced above, relies on the user physically removing the desired object from the reconstructed scene (e.g. the user picks up the chair and moves it out of view of the Kinect™ camera). Taking the derivative of the signed distance values over time, regions of the voxel grid with high change are labeled. A full pass over the voxel grid extracts these labeled connected components and the largest region is chosen as the foreground object. This method works well for objects that are physically small enough to be moved (e.g. a chair); however, for larger objects, the second example segmentation method may be more suitable. This second example method takes the current physical camera pose, raycasts the voxel grid and extracts the dominant plane using RANSAC (Random Sample Consensus), segmenting any resting objects (again the largest 3D connected component is assumed to be the desired object).

[0044] The meshing stage (block 403) automatically extracts and triangulates the desired foreground isosurface stored implicitly in the voxel grid. A geometric isosurface is extracted from the foreground labeled volumetric dataset using a GPU-based marching cubes algorithm. For each voxel, the signed distance value at its eight corners is computed. The algorithm uses these computed signed distances as a lookup to produce the correct polygon at the specific voxel.

[0045] Where KinectFusion techniques are used to generate the input mesh, the flow diagram of FIG. 2 may be extended as shown in the second flow diagram 420 in FIG. 4. The KinectFusion stage 422 generates the 3D geometry from the real-world 3D object and outputs the 3D geometry to both the Embed stage 202 and the Warp stage, block 206. In this example, a Kinect™ camera (e.g. the same Kinect™ camera) may be used both in the generation of the 3D geometry (in the KinectFusion stage 422) and in skeleton tracking (in the Skeleton Tracker, block 204). Alternatively, where a different depth camera is used, this camera may be used both in the generation of the 3D geometry and in tracking the motion of the user.

[0046] As described above, there are a number of ways in which the deformation graph may be generated (in block 112), for example, by traversing the vertices of the input mesh or by distributing nodes over the surface of the object and then repeatedly removing nodes within a given radius of a randomly chosen node until the desired sampling density is achieved. Depending on the sampling density used, the deformation graph may be considered a sparse deformation graph (e.g. it may contain a reduced number of nodes) and use of a sparse graph reduces the computational complexity and has the effect that the method runs more quickly on consumer hardware. An example method of generating a deformation graph can be described with reference to FIG. 5. This method is an extension of a technique described in ‘Embedded deformation for shape manipulation’ by Sumner, Schmid, and Pauly in SIGGRAPH 2007.

[0047] As shown in FIG. 5, the node (or vertex) positions within the deformation graph are defined initially using sampling (block 502). These node positions may defined by traversing the vertices of the input mesh or by distributing nodes over the surface of the object and then using Poisson Disk sampling (which may also be referred to as Poisson Disk pattern generation). Where nodes are defined by traversing the vertices of the input mesh, the method involves selecting a region of surface (e.g. selecting a triangle and then a point inside the triangle), picking a radius based on the total area of surface and using dart throwing until a desired number of samples is reached. Poisson Disk sampling is a technique in which a node is selected at random and then all nodes within a defined radius of the selected node are removed. This process is then repeated many times until a desired sampling density is achieved. The distance metric which is used in performing the Poisson Disk sampling may be a Euclidean distance metric; however, this can miss areas of the surface with high curvature and result in artifacts where semantically unrelated parts are linked. Consequently, an alternative distance metric may be used in sampling: a 5D orientation-aware distance metric. Where this metric is used, the sampling may be referred to as ‘orientation-aware sampling’.

[0048] Given surface samples p and q with normals {right arrow over (n)}_p and {right arrow over (n)}_q, a 5D orientation-aware distance D(p,q) may be defined as:

$\begin{array}{cc}D\left(p,q\right)=\min \left({\mathrm{dist}}_q\left(p\right),{\mathrm{dist}}_p\left(q\right)\right)\mathrm{or}D\left(p,q\right)=\frac{\min \left({\mathrm{dist}}_q\left(p\right),{\mathrm{dist}}_p\left(q\right)\right)}{\max \left(0,{\overrightarrow{n}}_p·{\overrightarrow{n}}_p\right)}& \left(1\right)\end{array}$

where:

dist_q(p)=∥p−q+2((p−q)·{right arrow over (n)}_q){right arrow over (n)}_q∥

dist_p(q)=∥q−p+2((q−p)·{right arrow over (n)}_p){right arrow over (n)}_p∥

The Mahalanobis distance dist_q(p) transforms the spherical isosurfaces around q defined by the Euclidean distance into ellipsoids with the {right arrow over (n)}_q axis squashed by a factor of ⅓. It increases the distance of points that deviate from the plane tangent to q. The distance D(p,q) has the property that distances increase faster when their normals deviate from alignment. When used for Poisson Disk pattern generation, it allows differently oriented samples to be placed arbitrarily close together.

[0049] A Poisson Disk pattern is generated (in block 502) as the node positions of the deformation graph using the distance metric defined in equation (1) above. Since a fixed framerate is generally used, a fixed number of samples N may be used and the minimum separation radius, R, may be defined as R=√{square root over (A/N)}, where A is the total surface area of the input mesh. In an example implementation, N=128. Alternatively, R may be defined by a desired level of detail and the number of samples N may be varied. Actual generation may be performed by brute force dart throwing (e.g. by repeatedly picking a random point on the surface, checking the point's distance to existing samples, and rejecting if it falls within a radius of existing samples). As part of the process of defining node positions (in block 502), the surface normal for each node may be stored as part of the graph node for later use in detecting how to attach a user's skeleton to the graph (as described in more detail below).

[0050] Having generated the node patterns (in block 502), the initial connectivity is computed by defining k-nearest neighbor edges (in block 504) defined using the same 5D orientation-aware distance metric as defined in equation (1) above.

[0051] The k-nearest neighbor graph, as computed in block 502, is not necessarily connected because a lack of scan data or insufficient sampling can lead to a graph composed of several connected components. This can lead to errors when computing transformations (e.g. in block 118 of FIG. 1). To address this, additional edges may be added to increase the connectivity of the deformation graph (block 506). As described in more detail below, these additional edges are added (in block 506) based on analysis of connected components in the nearest neighbor graph.

[0052] To increase the connectivity of the original k-nearest neighbor graph G=(V,E), as output by block 504, the graph is first made undirected (block 561), such that if B is a neighbor of A, A is also a neighbor of B. The connected components of the undirected k-nearest neighbor graph are then computed (block 562) and a new complete, weighted graph G′=(V′,E′), is formed (block 563), whose nodes V′ are the connected components of G, and every pair of nodes (u′,v′) has weight equal to the minimum distance between any two nodes sεu′⊂V and tεv′⊂V. The distance metric used in determining the minimum distance may be the 5D orientation-aware distance metric, as defined in equation (1) above. A minimum spanning tree is then computed on G′ (block 564) and an (undirected) edge (s,t) is added to E (i.e. to the set of edges in the k-nearest neighbor graph, G) if there is an edge between their connected components in the spanning tree (block 565).

[0053] In some examples, the connectivity may be further increased (in block 506) such that each node in the graph G has at least a minimum number of neighbors (block 566). In an example implementation, the minimum number of neighbors may be set at four.

[0054] In examples where additional links are added (e.g. in block 565 and/or block 566), data defining these additional edges may be stored separately (e.g. in a table of special links) or these new edges may be tagged or otherwise identifiable in some way, as in some examples these new edges are treated differently when calculating transformations on the deformation graph (as described in more detail below).

[0055] At runtime, body tracking data is received and attached to the deformation graph (blocks 114-116 in FIG. 1). The body tracking data may be obtained using any suitable sensor or sensor system (e.g. sensor 314 in combination with the skeleton tracker module 312 in FIG. 3) and where a sensor is used in generating the input mesh, the same sensor may, in some examples, be used to track the motion of the user.

[0056] When attaching the tracked skeleton to the deformation graph (in block 116), this may be performed automatically by adding point constraints in space. For example, each joint in the tracked skeleton (or each point in the body tracking data) may be made a constraint. In such an example, at attachment time, the position of each joint p_l (or other point, where joints are not used) is stored along with Euclidean distances to the k-nearest nodes in the deformation graph. As the user moves, each joint (or point) moves to a new position q_l and the graph is transformed such that the k-nearest nodes map p_l→q_l.

[0057] In various examples, which nodes in the graph are linked to each joint (e.g. through the point constraints described above) will depend on the position of the user when the tracked skeleton is obtained. As the user has freedom to adopt different body positions, the user can influence or directly control which parts of their body are mapped to particular parts of the object being animated. In order to assist the user in this, a graphical user interface (GUI) may be provided which provides visual feedback to the user, for example by displaying both the tracked skeleton and the object (or more particularly, the mesh of the object). Various presentation techniques may be used to make this GUI clearer or more intuitive, for example, by making the object partially transparent and/or showing the tracked skeleton in a bright color and/or by displaying skeleton overlaid over the object (or vice-versa). In some examples, the GUI is arranged such that the user appears to walk up to the object within the GUI. In some examples, lines or links 602 may be shown in the GUI 600 between a joint 604 on the skeleton 605 and the k-nearest nodes in the graph representing the object mesh 606 as shown in FIG. 6. The links 602 may be displayed dynamically as the user moves towards the object 606 within the scene displayed in the GUI 600. As the user moves, and their skeleton is tracked, the links may be updated (as the k-nearest nodes change) to enable the user to control the mapping between joints and nodes.

[0058] FIG. 7 shows a flow diagram of an example method of attaching the skeleton to the deformation graph in which the user poses themself such that their body intersects with the input mesh of the object. As described above, the tracked skeleton (e.g. as generated using the data received in block 114 of FIG. 1) is displayed at the same time as the input mesh (block 702). Initially the two may not be displayed overlaid to allow the user to appear (in the GUI) to walk into the scene and towards the object being animated. Once the skeleton and object are close together, they are at least partially overlaid. Lines are displayed between joints on the skeleton and the k-nearest nodes in the deformation graph (block 704). At this stage, the mapping between joints and nodes has not been confirmed and so these lines represent a proposed mapping rather than a confirmed (or actual) mapping that will be used in subsequent animation. As shown in FIG. 6, the GUI comprises multiple lines (e.g. k lines) radiating from each joint in the skeleton to points on the object mesh which correspond to the nodes in the deformation graph. In some examples, to improve clarity of the GUI, fewer than k lines may be displayed. As described above, the k-nearest nodes (i.e. the proposed mapping) may be determined dynamically, such that as the user moves, the k-nearest nodes may change and so the lines displayed in the GUI (and the proposed mapping) may be updated (block 706).

[0059] In various examples, the mapping may be confirmed (in block 710) in response to a verbal command received from the user (block 708) and on confirming the mapping, the current proposed mapping is stored (in block 710) as the actual mapping between joints and nodes, for use in subsequent stages of the animation method. The user may give the command (e.g. “possess”) when they are happy with the linking between joints and parts of the object. Through use of a verbal command, the user does not need to move any of their limbs, the position of which are being tracked, and so the issuance of the command will not affect the resultant confirmed mapping. Where a verbal command is used, this may be detected by a sensor system which is also imaging the user to enable skeleton tracking (e.g. a sensor system comprising both a camera and a microphone). In other examples, other types of commands may be used or the mapping may be performed automatically (e.g. block 708 omitted) when the user remains still, such that the tracked skeleton does not change position, and hence the proposed mapping does not change, for a defined period of time (e.g. 2 seconds). Where the attachment is performed automatically, the user is still in the loop because the position of their tracked skeleton affects the way the attachment is done (i.e. which parts of the skeleton attach to which parts of the deformation graph).

[0060] Although the description of the GUI above refers to the display of the tracked skeleton overlaid with the object, in other examples, captured images of the user's body may be used instead of the tracked skeleton. In some examples, the deformation graph may be displayed instead of the input mesh. It will also be appreciated that the visual feedback may be provided in different ways or other types of feedback may be used (e.g. audible feedback). Where visual feedback is used it may visually embed parts of the user into an object represented by an unstructured mesh (the input mesh).

[0061] In a variation of the methods of attaching the tracked skeleton to the deformation graph, constraints may be placed on bones in addition to (or instead of) attaching joints as point constraints. This makes reproduction (e.g. animation) of complex user motions more accurate and more realistic to the viewer and improves the accuracy of the attachment in cases where the user is not very good at judging whether they are intersecting accurately with the mesh and as a result the user places their limbs outside the surface of the object.

[0062] In this variation, each bone of a tracked skeleton is modeled as a cylinder with a predefined radius (e.g. 4 cm) or other 3D shape. A number of samples are placed along the length and circumference of each bone at a regular spacing (e.g. 16 samples per bone) and the outward facing normal of the bone at each sample position is calculated. When attachment is triggered (e.g. as a result of receiving a verbal command in block 708 of FIG. 7 or based on other criteria), a bone sample is attached to a graph node only if they a separated by less than a defined (Euclidean) distance (e.g. 10 cm) and the outward facing normals of the bone sample and the graph node are less than 90° apart.

[0063] Using this variation, there are now many more samples on each limb (there were only two where just the joints were used) which assists in making the animation match the user motion more accurately for longer bones. Furthermore, using normals makes the system and method robust to small misalignments between the user and the surface. For example, if the user is animating another scanned human, her arms may not be perfectly aligned with those of the scan. The surface normal test lets the front of her arm attach to the front of the arm in the scan, and likewise for the back. It has been shown that this works well with one-sided surfaces that come from the KinectFusion system described above.

[0064] Referring back to FIG. 7, implementation of this variation may only affect the actual mappings that are stored (in block 710) rather than displaying lines for all the additional sample points (in blocks 704-706).

[0065] Having attached the skeleton to the deformation graph (in block 116), when the tracked skeleton moves, as a result of the user moving, the deformation graph is transformed (in block 118). The transformations are determined by solving a non-linear energy minimization problem for each frame in real-time. This identifies the optimal transformations on the deformation graph that are smooth and feature-preserving and which satisfy the user's motion constraints. As the calculations are performed in real-time, this may be described as a dynamic operation.

[0066] The Embedded Deformation technique (as originally described in the Sumner paper referenced above and extended herein) assumes that the set of shape deformations varies smoothly in space and can be expressed as linear combinations of a sparse set of affine transformations. Each node in the deformation graph deforms space in a region surrounding its position g_j with an affine transformation A_j=(R_j,t_j), where R is a 3×3 matrix and t is a 3×1 vector. This affine transform maps the point v to:

A_j[v]=R_j(v−g_j)+g_j+t_j

[0067] The deformation defined by multiple nodes is combined linearly as in linear blend skinning (LBS). Given a point vε³, the deformation graph maps it to:

$\begin{array}{cc}\phi \left(v\right)=\sum _{j=0}^{k-1}w_j\left(v\right)A_j\left[v\right]& \left(2\right)\end{array}$

The blending weights w_j(v) are nonzero only for the k nodes closest to v, fall off linearly with distance, and sum to one. If transformations defined by the nodes vary smoothly, and the nodes are of sufficient density, then the vertices also deform smoothly. Using this technique, features rotate during deformation rather than stretch or shear, as shown in FIG. 8. FIG. 8 is a schematic diagram showing 12 nodes 802 (numbered 0-11) and the space surrounding each node is shown as a square 804. Initially, the nodes are shown in a straight line 806 but if the solid nodes (nodes 0, 6 and 11) are attached to the skeleton and node 6 is moved down, it can be seen that the other unattached nodes (nodes 1-5 and 7-10) move smoothly and the surrounding space is deformed naturally, rotating without stretching. The transformation shown bends the nodes like an arm at an elbow. In 3D, the ellipse 808 would be the surface of the target object and the solid nodes (nodes 0, 6, 11) would correspond to a tracked skeleton.

[0068] To constrain the space of transformations, a number of assumptions are made and formulated as an energy minimization problem. The energy is defined as a weighted sum of four terms: a first term, E_rot, which minimizes stretching by biasing the solution towards isometry, a second term, E_reg, which is a regularization term that ensures that each node maps its neighbors near where they would map themselves, a third term, E_con, which incorporates the point constraints which are used to attach the deformation graph and the skeleton (as described above) and a fourth term, E_rig, which is referred to as the ‘rigidity regularizer’. The energy is therefore given by:

E=w_rotE_rot+w_regE_reg+w_conE_con+w_rigE_rig

Each of these terms, which are all quadratic terms, and their associated weights are described in more detail below. The energy minimization may be performed using the Gauss-Newton algorithm or any other suitable technique.

[0069] The first term, E_rot, which minimizes stretching may be defined as:

$E_{\mathrm{rot}}=\sum _j^{}{R_j^TR_j-I}_F^2$

where I is the identity matrix and ∥•∥_F denotes the Frobenius norm. The associated weight, w_rot, may be set equal to one.

[0070] The second term, E_reg, is a regularization term ensures that each node maps its neighbors near where they would map themselves and hence ensures that the deformation field is smooth. This term may be defined as:

$E_{\mathrm{reg}}=\sum _j^{}\sum _{k\in N\left(j\right)}^{}{A_j\left[g_k\right]-A_k\left[g_k\right]}_2^2$

where N(j) is the set of neighbors of j in the graph. The associated weight, w_reg, may be set equal to 10.

[0071] The third term, E_con, incorporates an arbitrary number of point constraints which are defined when the tracked skeleton is attached to the deformation graph (as described above). Each constraint maps a given point p_l to a desired target q_l and the term may be defined as:

$E_{\mathrm{con}}=\sum _l^{}{\phi \left(p_l\right)-q_l}_2^2$

where φ(p_l) is the result of applying the deformation to p_l (as set out in equation 2 above). The associated weight, W_con, may be set equal to 100.

[0072] The fourth term, E_rig, is the rigidity regularizer which may be included to ensure a stable deformation. The second term, E_reg, as described above is a regularization term, while the fourth term, E_rig, enforces a stronger regularization condition on a subset of the edges in the deformation graph. Without this fourth term, the energy function contains a number of gauge freedoms due to symmetry: a subgraph without user constraints, weakly connected to the rest of the graph through a single cut vertex (a vertex whose removal increases the number of connected components), is free to rotate about that point. These cut vertices include the ones where additional edges were added when the deformation graph was created (e.g. in block 565 of FIG. 5), as described above. Therefore, at these edges (i.e. at all cut vertices in the deformation graph) a stronger regularization condition is enforced and this may be defined as:

$E_{\mathrm{rig}}=\sum _{\left(j,k\right)}^{}{R_k^TR_j-I}_F^2+{t_k-t_j}_2^2$

This fourth term says that if a piece of the mesh is only loosely connected, the bridge edge (j,k) encourages it to be coupled rigidly with the rest of the mesh. As this is a stronger condition than the basic regularizer (12 constraints rather than 3), a smaller weight is used, e.g. w_rig=w_reg/10.

[0073] Once the transformations on the deformation graph have been computed (e.g. using energy minimization methods, as described above), these transformations are applied to the input mesh using an algorithm similar to LBS.

[0074] Once an input mesh has been attached to a skeleton using the methods described above (a process which may be referred to as ‘rigging’ or ‘possessing’), the input mesh may be incorporated into physics-enabled interactions. For example, such that one person can possess a friend's avatar and rampage through a physics-enabled world, knocking over towers of boxes, or a possessed chair or stepladder can be used to play dodgeball. These and more complex examples enable capture of the physical world in the digital domain, before bringing it to life, and enabling it to interact with other virtual objects in both physically plausible and implausible ways and in an example application, this may be used in new gaming scenarios.

[0075] To implement this in a physics simulation, the input mesh is approximated as a series of kinematic sphere proxies. Sphere packing may be performed as follows: repeatedly pick a random vertex (until all vertices are processed) on the mesh and place a sphere centered around it, pruning all neighboring vertices inside the sphere. The sphere radius may be set to four times the mesh's mean edge length.

[0076] As shown in FIG. 9, this approximation stage (block 902) may be done alongside the other stages in the pre-processing phase of the pipeline (e.g. alongside the generation of the deformation graph in block 112). For each frame, after deformations are computed on the graph, the kinematic spheres are moved accordingly (block 904), e.g. by applying the same transformations (as applied to the input mesh in block 120) to the sphere centers. Use of sphere proxies enables efficient modeling of collisions with other dynamic objects in the physical simulation.

[0077] Although many of the examples described above relate to 3D input meshes, the methods described herein may also be implemented using a 2D input mesh, for example, to animate 2D clip art. Use of a 2D input mesh reduces the computation complexity and so the methods may be implemented on hardware with less processing power and still run in real-time (e.g. on smart phones).

[0078] The examples described above involve attaching a single tracked skeleton to a deformation graph (in block 116 of FIG. 1). The methods may, however, be used to attach more than one tracked skeleton to an input mesh, as shown in the schematic diagram of FIG. 10. FIG. 10 shows an input mesh of a horse 1002 which may be attached to two tracked skeletons 1004, 1006 such that motion of the ‘front’ skeleton 1004 results in motion of the head and front legs of the horse and motion of the ‘back’ skeleton 1006 results in motion of the rear legs of the horse. In such an example, the attachment step (as described above), adds constraints associated with joints and/or bones from both skeletons but otherwise the method operates as described above.

[0079] Similarly, the tracked skeleton may be used to animate more than one object (e.g. a user's legs may be attached to a deformation graph of a chair and the same user's arms may be attached to a deformation graph of a desk lamp). Alternatively, only part of a user's body may be mapped to the deformation graph of an object (e.g. only a user's arms or only their fingers). Similarly, an entire skeleton may be used to animate only part of an object. Consequently, the attachment stage described above may be used to attach all or part of one or more skeletons to all or part of one or more deformation graphs. In some examples, the attachment process may occur in multiple phases, for example a first phase may be used to attach a first part of a skeleton to a first part of a deformation graph and a second phase may be used to attach a second part of a skeleton to a second part of a deformation graph and the user may be able to move in between phases (e.g. to better align themselves to the second part of the deformation graph). In such an example, commands (e.g. voice commands) may be used to control each phase and the progression from one phase to the next phase. It will therefore be appreciated that the methods described herein may be used to attach arbitrary parts of one or more skeletons to arbitrary parts of one or more deformation graphs in any manner which is desired by the user.

[0080] In the majority of the examples described above and in many applications, the objects being animated are non-humanoid objects where such objects may be inanimate objects (such as items of furniture or other household items) or animate objects (such as animals). In some examples, however, the objects being animated may be humans, such that, for example, one user can possess the avatar for another user. Furthermore, whilst the skeletons which are tracked and attached to the deformation graph are, in most examples, human skeletons, (i.e. the skeleton(s) of the user(s)), the methods are also applicable to scenarios where the tracked skeleton belongs to an animal and it is the animal skeleton that is attached to the deformation graph generated from the input mesh.

[0081] In some examples there may be a mismatch between the scale (e.g. height) of the tracked skeleton and the input mesh. In such instances, the height of the input mesh may be retargeted to match, at least approximately, the height of the tracked skeleton. Alternatively, the user may use gestures, once the tracked skeleton is embedded in the input mesh (through the attachment process), to manipulate the size or aspect ratio of the input mesh.

[0082] There are many example applications for the methods described above, including but not limited to generation of animated films (e.g. home CG movies), creation of more realistic avatars for gaming and teleconferencing scenarios (for example, an entire 360° reconstruction of a human body can be acquired, segmented from the ground plane and meshed using KinectFusion in less than one minute) and natural control of CAD models for simple assembly tasks. The methods may also be used for quickly previewing an animation before doing more sophisticated animation using a rigging or keyframe system.

[0083] In an example scenario which shows how the methods described herein may be used, a user wants to introduce and animate an existing static physical object, such as a chair, into a 3D game. He picks up a Kinect™ camera and scans in part of the room. The methods described herein automatically generate a 3D mesh of the chair and segment it from the background. At this point the user has a static, incomplete and un-rigged mesh in the CG world. To bring this object to life in realistic ways, the user first places the depth sensor back down so that it can image his full body, and a tracked human skeleton is sensed. The system described herein renders both the human skeleton and scanned object side by side. The user then physically moves such that the desired parts of the rendered skeleton are embedded inside the scanned object. Once in the desired pose, the user issues a voice command to automatically rig (or possess) the mesh. This attaches joints of his current pose to the mesh. The user can now move his body and the system described herein automatically translates his motion into realistic deformations of the previously static mesh. For example, moving his legs causes the legs of the chair to also move, flexing his knees causes the chair to bend, jumping up makes the chair also jump. Motions of the body propagate in real-time to the mesh and provides a natural way for users to perform playful animations of any object that they wish to bring to life in their CG application or game.

[0084] The methods described herein allow animation to be performed quickly by anyone (including novice users and young children) and do not require specialist hardware (consumer hardware can be used). Animation of diverse meshes is possible and the methods work for incomplete surfaces and meshes of any object (humanoid or non-humanoid). Use of the body as an input device provides more degrees of freedom than standard user input devices such as a mouse, keyboard or track pad. The entire pipeline from geometry acquisition to rigging and animation runs at interactive rates and requires no manual pre-processing by an artist.

[0085] The methods and apparatus described above provide a performance based approach to computer animation. Motion of the skeleton is tracked using a non-contact sensor and translated into motion of another object, which may be a non-humanoid object. Where the tracked skeleton is that of the user, the user's own body acts as a high DoF controller in controlling the motion of the animated object.

[0086] Although the present examples are described and illustrated herein as being implemented in a Kinect™-based system, the system described is provided as an example and not a limitation. As those skilled in the art will appreciate, the present examples are suitable for application in a variety of different types of systems using different sensors.

[0087] The term ‘computer’ or ‘computing-based device’ is used herein to refer to any device with processing capability such that it can execute instructions. Those skilled in the art will realize that such processing capabilities are incorporated into many different devices and therefore the terms ‘computer’ and ‘computing-based device’ each include PCs, servers, mobile telephones (including smart phones), tablet computers, set-top boxes, media players, games consoles, personal digital assistants and many other devices.

[0088] The methods described herein may be performed by software in machine readable form on a tangible storage medium e.g. in the form of a computer program comprising computer program code means adapted to perform all the steps of any of the methods described herein when the program is run on a computer and where the computer program may be embodied on a computer readable medium. Examples of tangible (or non-transitory) storage media include computer storage devices comprising computer-readable media such as disks, thumb drives, memory etc and do not include propagated signals. Propagated signals may be present in a tangible storage media, but propagated signals per se are not examples of tangible storage media. The software can be suitable for execution on a parallel processor or a serial processor such that the method steps may be carried out in any suitable order, or simultaneously.

[0089] This acknowledges that software can be a valuable, separately tradable commodity. It is intended to encompass software, which runs on or controls “dumb” or standard hardware, to carry out the desired functions. It is also intended to encompass software which “describes” or defines the configuration of hardware, such as HDL (hardware description language) software, as is used for designing silicon chips, or for configuring universal programmable chips, to carry out desired functions.

[0090] Those skilled in the art will realize that storage devices utilized to store program instructions can be distributed across a network. For example, a remote computer may store an example of the process described as software. A local or terminal computer may access the remote computer and download a part or all of the software to run the program. Alternatively, the local computer may download pieces of the software as needed, or execute some software instructions at the local terminal and some at the remote computer (or computer network). Those skilled in the art will also realize that by utilizing conventional techniques known to those skilled in the art that all, or a portion of the software instructions may be carried out by a dedicated circuit, such as a DSP, programmable logic array, or the like.

[0091] Any range or device value given herein may be extended or altered without losing the effect sought, as will be apparent to the skilled person.

[0092] Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims.

[0093] It will be understood that the benefits and advantages described above may relate to one embodiment or may relate to several embodiments. The embodiments are not limited to those that solve any or all of the stated problems or those that have any or all of the stated benefits and advantages. It will further be understood that reference to ‘an’ item refers to one or more of those items.

[0094] The steps of the methods described herein may be carried out in any suitable order, or simultaneously where appropriate. Additionally, individual blocks may be deleted from any of the methods without departing from the spirit and scope of the subject matter described herein. Aspects of any of the examples described above may be combined with aspects of any of the other examples described to form further examples without losing the effect sought.

[0095] The term ‘comprising’ is used herein to mean including the method blocks or elements identified, but that such blocks or elements do not comprise an exclusive list and a method or apparatus may contain additional blocks or elements.

[0096] It will be understood that the above description is given by way of example only and that various modifications may be made by those skilled in the art. The above specification, examples and data provide a complete description of the structure and use of exemplary embodiments. Although various embodiments have been described above with a certain degree of particularity, or with reference to one or more individual embodiments, those skilled in the art could make numerous alterations to the disclosed embodiments without departing from the spirit or scope of this specification.