CROSS-REFERENCES TO RELATED APPLICATIONS 
     The present application is a Continuation-in-Part of U.S. patent application Ser. No. 11/759,790 filed on Jun. 7, 2007 which claims the benefit and priority under 35 U.S.C. 119(e) from U.S. Provisional Application No. 60/812,300, filed on Jun. 9, 2006 entitled POSITIONING AN ANIMATED OBJECT USING A DEPTH MAP the entire contents of which are incorporated by reference for all purposes. 
    
    
     BACKGROUND 
     The present invention relates generally to computer animation and graphics, and more particularly to techniques for determining a position of a component of an inverse kinematics (IK) controlled animated object relative to a surface object and updating the state of the animated object based upon the determination. 
     Animation involves the generation of a series of still images that, when played back in quick succession, appear as continuously moving. In computer animation, a rendering process is used to generate a two-dimensional image of a three-dimensional scene from a given viewpoint. Animated sequences can be created by rendering a sequence of the rendered images of a scene as a scene is gradually changed over time. A great deal of effort has been devoted to making the rendered images and the resultant animation realistic. 
     Typically, animated objects do not need to know about the environment during an animation process. However, in certain situations, an animated object needs to know about its environment in order to be positioned appropriately with respect to the environment to increase the realism of the animation. For example, an IK controlled character with appendages such as feet being needs to know about the ground so that the feet are properly positioned on the ground when animated so as to provide a physically realistic look, e.g., not penetrating ground and not floating. The character also has to be able to react to changes in terrain of the ground. For example, the terrain changes may correspond to variations in height such as hills or depressions. These terrain changes may not be part of the ground surface representation but instead may be represented by displacement maps in the shader code or additional objects placed on the surface. This cannot be handled by conventional techniques that handle interactions between two surfaces and require that surface characteristics be part of environment surface. 
     Additionally, manually adjusting interactions between a character&#39;s feet or other appendages and a bumpy or uneven terrain adds a heavy layer of work to an animator&#39;s already labor-intensive process. Animators need to tweak the positions and orientations of the feet to make them conform to the ground precisely, neither floating above nor penetrating the ground. Determining foot contact can be difficult where the terrain is complex, e.g., with hills, stairs, rocks and other uneven surface features. Keeping feet on the ground generally is not a one-time task. Whenever the ground environment or animation is changed, animators have to readjust the foot. They find managing foot-ground contact to be a tedious job. 
     Therefore it is desirable to provide improved techniques that overcome the above and other problems. 
     BRIEF SUMMARY 
     Systems and methods are provided for positioning a component of an inverse kinematics (IK) controlled animated object relative to a surface object. 
     In certain aspects, to help animators deal with foot-ground interactions efficiently, a foot-ground locking system is provided as a preprocessor to an inverse kinematics (IK) controller to automatically pose the foot on the ground. The foot is first rotated to reach the maximal contact area with the ground, then translated to touch the ground, and finally deformed to conform more tightly to the ground. The system works properly with other foot shape deformations, such as toe, heel, and ball rotations. The foot-ground locking can be used either as an interactive tool to help animators identify where the ground is or as a batch postprocessing tool to clean up foot-ground contacts whenever the animation or ground environment is changed. It should be appreciated that the techniques provided herein are applicable to other object-to-object interactions, e.g., appendages or objects besides feet making contact with other objects. 
     According to one aspect, a computer implemented method is provided for positioning an inverse kinematics (IK) controlled object relative to a surface object. The surface object, in certain aspects, is represented by a depth map. The method typically includes receiving a specification of an IK object and a surface object, receiving a target pose of the IK object, the target pose having an IK goal for the IK object, and determining a position and/or an orientation of a component of the IK object relative to the surface object. The method also typically includes updating a state of the target pose of the IK object based on the step of determining, wherein the updated state of the target pose of the IK object is such that when used the IK component maintains a specified distance from the surface object within a specified tolerance. In certain aspects, receiving a specification of the surface object includes accessing a depth map representing the surface object and determining includes using the depth map to determine difference values between the surface object and one or more points of the component. In certain aspects, the method further includes modifying a position of the IK goal and/or modifying an orientation of the component of the IK object based on the updated state of the target pose, wherein the position of the IK goal and the orientation of the component of the IK object are modified such that the component lies on the surface of the surface object. In certain aspects, the state of the target pose includes values for one or more animation control variables, and wherein the values for the one or more animation control variables are stored or cached for later use. 
     In certain aspects, the IK controlled object is an animated object used in an animation system and the method might include rendering one or more images including the animated object and the surface object, wherein in the one or more images the IK component maintains the specified distance from the surface object within the specified tolerance. In certain aspects, the method includes using the updated state of the target pose in an image display system to display an image of the IK object. 
     According to another aspect, a computer readable medium is provided that stores code, which when executed by one or more processors, causes the one or more processors to position an inverse kinematics (IK) controlled object relative to a surface object. The stored code typically includes instructions to receive a specification of an IK object and a surface object, to receive a target pose of the IK object, the target pose having an IK goal for the IK object, and to determine a position and/or an orientation of a component of the IK object relative to the surface object. The stored code also typically includes instructions to update a state of the target pose of the IK object based on the determined position and/or orientation, wherein the updated state of the target pose of the IK object is such that when used the IK component maintains a specified distance from the surface object within a specified tolerance. 
     According to yet another aspect, a system for positioning an inverse kinematics (IK) controlled object relative to a surface object is provided. The system typically includes one or more processors, and a memory for storing code modules. Typically, when executed by the one or more processors, the code modules cause the one or more processors to receive a specification of an IK object and a surface object, to receive a target pose of the IK object, the target pose having an IK goal for the IK object, and to determine a position and/or an orientation of a component of the IK object relative to the surface object. When executed, the code modules also typically cause the one or more processors to update a state of the target pose of the IK object based on the determined position and/or orientation, wherein the updated state of the target pose of the IK object is such that when used the IK component maintains a specified distance from the surface object within a specified tolerance. In certain aspects, the system further includes a display module for displaying one or more images of the IK controlled object. 
     Reference to the remaining portions of the specification, including the drawings and claims, will realize other features and advantages of the present invention. Further features and advantages of the present invention, as well as the structure and operation of various embodiments of the present invention, are described in detail below with respect to the accompanying drawings. In the drawings, like reference numbers indicate identical or functionally similar elements. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates a simplified two-dimensional array depth map storing depth or z-values 
         FIG. 2  illustrates a simplified flowchart showing a method of positioning a component of an IK controlled object relative to a surface object according to one embodiment. 
         FIG. 3  illustrates a simplified flowchart showing a method for updating the state of an IK controlled animated object. 
         FIGS. 4A and 4B  illustrate examples where a (single) point may be modified when initially below, or above, the surface object, respectively. 
         FIGS. 5A and 5B  depict pictorial examples of positioning a foot of a character object on a ground surface based on a single point and using a depth map according to one embodiment. 
         FIG. 6  is a block diagram of a computer system that may be used to practice various embodiments. 
     
    
    
     DETAILED DESCRIPTION 
     Embodiments of the present invention provide techniques for determining a position of a component of an IK controlled animated object relative to a surface object and updating the state of the animated object based upon the determination. A component of an IK controlled animated object will also be referred to herein as an IK component. 
     For inverse kinematics modeled objects, components (e.g., representing bones of a human character) are linked together in a hierarchical manner by means of parenting to form the movable joints in a body. For example, the thigh may be the parent object of a shin, the shin may be a parent of the foot, the foot may be the parent of toes, and so on. This linking establishes the hierarchy. When an object (like a thigh) is rotated, the child objects linked to it (shin, foot and toes) will follow along. This is the essential principle of hierarchical motion. And this method of working with a hierarchy is called forward kinematics. In forward kinematics, motion is inherited down the hierarchy from the parents to the children. In inverse kinematics (IK), on the other hand, motion is inherited up the hierarchy, from the extremities to the more proximal joints (closer to the body) which are their parents. This effectively allows an entire arm or leg to be posed by moving one object or point: an IK goal. As the IK goal is moved around, the extremities follow it, and the joints above it in the hierarchy readjust accordingly based on an IK solution algorithm. In order for the joints to readjust appropriately, constraints or “degrees of freedom” are typically assigned to the joints, so they don&#39;t bend beyond a realistic range of motion. Accordingly, as will be described herein, embodiments allow animators or other users to position an IK goal and effectively “lock” the IK component associated with that IK goal to a surface object, e.g., such that the IK component maintains a specified distance from the surface object within a specified tolerance amount. For example, an animator may desire to lock the foot of an animated character object to a ground or surface object. Thus, as an example, and according to certain embodiments, the animator may identify a desired target pose of an IK goal such as an ankle point or other point of a foot component and the system will automatically adjust the position and alignment of the IK component to match with or lock to a ground or surface object. 
     In certain aspects, a ground or surface object is represented by a depth map. A depth map is generally used for representing and storing depth information taken from a scene. A depth map (also typically referred to as a z-map or texture map or a shadow map) is generally a two-dimensional array wherein one dimension (e.g., rows) of the array corresponds to location along the X axis in an image and the other dimension (e.g., columns) corresponds to location along the Y axis in an image. The intersection of a row and a column represents an array element or a pixel. In a depth map, the array elements (pixels) store depth values (z values) for X and Y locations in the image. 
       FIG. 1  depicts a simplified two-dimensional array depth map  100  storing depth or z-values (e.g., Z 0 , Z 1 , Z 2 , etc.). The z-values may be computed from the perspective of a given light source or camera. As depicted in  FIG. 1 , the rows correspond to the X direction and the columns correspond to the Y direction. For each (x,y) index pair of the depth map, a z value is stored that specifies the depth at which the light emitted by a light source positioned at the camera location is blocked by a surface in the scene at the (x,y) location in the image. The values stored in a depth map specify the distance (depth) from the camera at which a first surface is encountered. Depth maps are generally used for determining shadow effects in rendering a scene and are thus sometimes also referred to as shadow maps. A shadow map is used to determine if a point in a scene is in shadow or not. For example, elements having depth values greater than the given z value at a particular (x,y) image location may be shadowed, whereas elements that have depth values less than the given z value may be lit. 
     According to an embodiment, a depth map stores information representing a surface comprised of one or more objects. The z-values of the depth map encode the shape of the surface as seen from one angle. A depth map also captures displacement information associated with the one or more objects such as surface information from bumps maps, displacement maps, shader details, etc. that are not available in the surface representation. Depth maps may represent any number of surfaces. Different techniques may be used to generate a depth map. In one embodiment, a depth map is generated by rendering an image of z values of one or more objects captured using a camera. For example, to generate a depth map for a ground surface, a camera positioned in the direction of gravity may be used to capture and render an image of z values that represent the ground surface. In alternative embodiments, some other camera direction may also be used to define the surface represented by the depth map. 
     According to an embodiment, processing is performed to determine positions and/or orientations of one or more components of an IK controlled animated object relative to a surface object, e.g., represented by a depth map. Initially a target pose of the animated object is received from an animator or other user, and an IK goal of the object is identified. For example, in the case of a foot on a human character, the animator may pose the character proximal the ground or a surface object and identify that the foot or an ankle be locked to the ground or surface object. In certain aspects, the IK goal is moved or posed by an animator either using a direct manipulation tool or using a set of animation control variables to control the degrees of freedom of an object component or point of the object. 
     Since a depth map stores z-values, the surface (of the ground or surface object) represented by a depth map is a thin surface with no volume. As a result, the IK goal may be either positioned below the surface represented by the depth map, on the surface represented by the depth map, or above the surface represented by the depth map. The determination of the position of a component of an IK controlled animated object with respect to the surface represented by a depth map may be used to update or modify the attributes or state of the animated object. Updating the state of an IK controlled animated object may change one or more of the animated object&#39;s geometric and/or non-geometric properties, such as changing the position and/or orientation of a component(s) of the animated object, changing a color associated with the animated object, and the like. 
     As part of the processing, the position and orientation of the component relative to the surface represented by the depth map is first determined. This may be determined by computing the (x,y) position of the component in the image space of the depth map and comparing the z-value of the component with the z value stored by the depth map for that (x,y) position. This comparison determines whether the component is positioned above the surface represented by the depth map, below the surface, or on the surface. Based upon the position of the component of the IK controlled animated object with respect to the surface, the attributes or state of the animated object may be modified or updated. Updating the state may involve changing geometric and/or non-geometric attributes of the animated object. For example, the state of the animated object may be updated such that the position and/or orientation of the component of the animated object or of other components of the animated object is modified. Non-geometric attributes of the animated object may also be modified such as a color associated with the animated object, etc. In certain aspects, an alignment of the IK component with respect to the surface object is also determined so that the IK component (and/or one or more other components of the object) may be rotated to more accurately match the surface object (e.g., based on the normal of the surface object) orientation where contact is to be made. 
     For example, a depth map representing a ground surface may be used to update the state of an animated character object walking over the ground surface. In this example, a component of the character object may be a foot. A depth map representing the ground surface may be used to determine if the points of the foot are below the ground surface, above the ground surface, or on the ground surface. Based upon this determination, the transformation matrix of the character object may be positioned and/or oriented to a position and/or orientation desired by the animator. Since the depth map information encapsulates information about the ground terrain (e.g., information about bumps or holes in the ground surface), as the character walks over the ground surface, the position of the component (e.g., foot) and the orientation may be appropriately modified using the depth map such that the foot is positioned and oriented on the ground surface (see, e.g.,  FIG. 5 , to be discussed below, for a 2-dimensional example). This enhances the realism of the animation and makes it appear that the animated object is reactive to the surface. 
       FIG. 2  depicts a simplified flowchart  200  showing a method of positioning an IK component relative to a surface object according to one embodiment. The processing depicted in flowchart  200  may be performed by hardware modules, software modules (e.g., code or instructions that may be stored on a computer-readable medium) executed by a processor, or combinations thereof. 
     Processing is initiated upon receiving information identifying a component of an IK controlled animated object and a surface object in step  202 . For example, in certain aspects a specification of the IK controlled object (or of the IK component) and of the surface object is received. The specification typically includes all or a subset of the data that describes the object, including constraints. For example, the specification may include a rigged surface mesh or a skeleton system. The component may be an entire component or a specific point of a component, or any other geometric attribute of the animated object. In certain aspects, receiving information identifying, or a specification of, the surface object includes accessing a depth map representing the surface. The depth map may be a rendering of the z-values representing a surface comprised of one or more objects and including their displacement information. The displacement information encoded by a depth map may include the shape of the surface including shader details, bump maps, displacement maps, etc. associated with the one or more objects. The depth map and the animated object specification may be accessed from a memory location accessible to the animation system. The depth map is typically rendered prior to the animation and is thus typically available prior to step  202 . 
     In step  203  a target pose of an IK component is received. For example, an animator may manipulate or otherwise designate a target pose of the animated object at a specific target image frame. This may be done using a direct manipulation tool or animation control variables that control the IK goal position and orientation. The target pose includes an IK goal for the IK object. 
     In certain aspects, where depth maps are used, the position coordinates of the IK component are converted to depth map coordinates (the coordinate-space of the camera used to define the depth map) in step  204 . This is optional and is done to facilitate calculations using the depth map. Since the depth values in the depth map accessed in  202  are in depth map coordinates, by converting the component coordinates to depth map coordinates, the resultant z-values of the component can be directly compared to z-values in the depth map. In step  206 , the position and/or orientation of the IK component relative to the surface object are determined. For example, the position and alignment of the IK component relative to the surface represented by the depth map accessed is determined in step  206 . The determination is made based upon the position coordinates of the component and based on depth values stored in the depth map accessed in  204  for that position. In one embodiment, the determination is done by projecting the z coordinates of the component to the z values stored in the depth map corresponding to the (x,y) location of the component. 
     In one embodiment, the state of the animated object may be updated in  208  to achieve a position and/or orientation of the component (or of other components) of the animated object that is desired by the animator. This may be done to increase the realism of the resultant animation. For example, the state of the target pose of the IK controlled animated object is updated based on the determination made in step  206 . Updating the state of an animated object may change one or more of the animated object&#39;s geometric and/or non-geometric properties, such as changing the position and/or orientation of a component(s) of the IK controlled animated object, changing a color associated with the animated object, and the like. For example, where a component, such a a foot, includes several subcomponents or children, such as the ball of the foot and the toes, the determination in step  206  may cause the contact point (e.g., ball of foot or toes) to change orientation with respect to other components. 
     The state of the animated object may also be modified simply to inform the animator of the determined position of the component relative to the surface represented by the depth map. For instance, the color of a foot of a character object may be changed to a particular color (e.g., red) if any of its points are determined to be below the surface represented by the depth map. 
       FIG. 3  depicts a simplified flowchart  300  showing a method for updating the state of an IK controlled animated object to re-position and/or re-orient a component of the animated object to a desired position and/or orientation with respect to a surface object according to one embodiment. As depicted in  FIG. 3 , upon determining a position and alignment of the component of the animated object relative to the surface object in step  206  of  FIG. 2 , a check is made to see if the component of the animated object is in a position and/or orientation desired by the animator in step  302 . If it is determined in  302  that the component is not in a desired position and/or orientation, then the state of the animated object is changed, e.g., according to method  200 , to place the component in the desired position and/or orientation in step  304 . In this manner, the state of the animated object is updated to change the position and/or orientation of the component of the animated object. It should be appreciated that re-positioning and re-orienting a component may be done in one, two or three translational degrees of freedom and in one, two or three rotation degrees of freedom. 
     While the processing depicted in  FIGS. 2 and 3  refer to a single component of the IK controlled animated object, in alternative embodiments, the processing may also be applied to multiple components of an IK controlled animated object. The state of the animated object may then be updated based upon the result of the processing of the multiple components. For example, the processing depicted in  FIGS. 2 and 3  may be used, for example, to position and/orient components of a character object. In this scenario, the depth map may represent the ground surface, the component of the character object may be one or more feet or other appendages that are supposed to be in contact with a ground surface represented by the depth map. In such a scenario, if it is determined that the points are either above or below the ground surface represented by the depth map, the positions of the points may be changed to place them on the surface represented by the depth map. By doing this, the foot may be “locked” to the surface. As the character changes location over the ground surface (e.g., walks over the ground surface), the depth map representing the ground surface may be used again to determine the position of the relevant points relative to the ground surface and the state of the character object may be updated such that the relevant points are locked to the ground surface whose terrain may change (e.g., hills, holes, bumps, etc.). 
     In one embodiment, the degree of the modification needed to make a point or points of an IK component be placed on or near the surface represented by the depth map may be determined by comparing the position of the point or points of the IK component and the value in the depth map corresponding to the point location. In certain aspects, this is done by projecting the point towards the surface such that the modified position and/or orientation of the point or points is placed on the surface. It is assumed for purposes of describing  FIGS. 2 and 3  that a point is projected in a direction parallel to the direction of a light source, or as defined by a user. Accordingly, the position of a point of the animated object is modified along a direction that is parallel to the direction of the camera used for rendering the depth map. Projecting a point along the view direction of the camera is equivalent to replacing the z-coordinate of the point in camera space with the z value read from the depth map for the (x,y) coordinates of the point. Thus, the projection is very efficient. The position of the point(s) of the IK component is modified based upon the point&#39;s position relative to the surface represented by the depth map.  FIGS. 4   a  and  4   b  illustrate examples where a (single) point may be modified when initially below, or above, the surface object, respectively. 
     It should be understood that the desired position of an IK component does not always have to be on the surface. The desired position of the component may be at some location either above or below the surface represented by the depth map and the state of the animated object may be modified accordingly. In one embodiment, a specified distance is maintained within a specified tolerance, e.g., within about 1% to 5%. In another embodiment, the position of the component of the IK controlled animated object is modified to re-position the IK component on the surface if the position of the component is determined to be below or above the surface. For example, a point on the foot of a character object is projected up to the ground surface if it is determined that the point is below the surface. 
     The position of an IK component relative to the surface represented by a depth map may be used to change the position and/or orientation of other components of the animated object. In one embodiment, where the relative distances between some components of the animated object may stay the same in order to preserve a rigid portion of the animated object, the changes in positions of the other components (e.g., points) of the animated object may be determined based upon the change in position and/or orientation of the IK component whose position is determined relative to the surface. 
       FIGS. 5A and 5B  depict 2-dimensional pictorial examples of positioning a foot of a character object on a ground surface based on a single point and using a depth map according to one embodiment. It should be appreciated that the techniques herein are applicable tio 3-dimensional models. In the example depicted in  FIG. 5A , at time T 1 , the state of the foot component is such that the foot is positioned on the surface of the ground and such that a point P of the foot is placed on the ground. At time T 2 , as the character travels over the ground surface to a new location, a depth map representing the ground surface may be used to determine the position of the foot relative to the ground surface. The terrain or shape of the ground surface at the new location as represented by the depth map may have a bump or hill as depicted in  FIG. 5A . Accordingly, at T 2 , the state of the foot object may be updated such that the position of point P is modified (projected up to the ground surface) such that point P is placed on the ground surface represented by the depth map. The state of the foot object may be modified to update other geometric and/or non-geometric attributes of the character object based upon determination of point P&#39;s position relative to the surface repented by the depth map. At time T 3 , as the character walks over the ground surface to yet another new location, the depth map representing the ground surface may be used again to determine the position of the foot relative to the ground surface. As depicted in  FIG. 5A , at the new location, the ground surface as represented by the depth map may be level again (i.e., not have a bump or hill). Accordingly, at T 3 , upon determining the position of point P relative to the ground surface represented by the depth map, the state of the character animated object may be modified such that the position of point P of the foot is modified (pushed down to the ground surface) to place it on the ground surface. The state of the character object may be modified to update other geometric and/or non-geometric attributes of the character object based upon the determination of point P&#39;s position relative to the surface represented by the depth map. 
     In the example depicted in  FIG. 5B , at time T 1 , the state of the character object is such that the foot is positioned on the ground surface represented by a depth map such that a point P (e.g., ball of foot) of the foot is placed on or near the ground (e.g., foot flat on ground with toe pointing up slightly). Contact with the ground may or may not be made with the foot, ball or toes, where present. At T 2 , as the character walks to a new location, the depth map representing the ground surface may be used to determine the position of the point relative to the ground surface. The terrain of the ground surface at the new location as represented by a depth map may have a front side of a bump as depicted in  FIG. 5B . Accordingly, at T 2 , the state of the character object is modified such that point P is placed on or near (e.g., within a tolerance) the ground surface with the ball of the foot rotated (e.g., the toe is tangential to surface). The state of the character object may be further modified to update one or more other geometric or non-geometric attributes, such as to change the orientation of the foot as depicted in  FIG. 5B . At time T 3 , the character travels to yet another new location. At this new location, the ground surface as represented by the depth map may have a backside of a bump. At T 3 , the position of point P is determined relative to the ground surface using the depth map representing the ground surface. The state of the character object may be updated such that point P is pushed near to the ground surface (as shown, the ball is rotated slightly so that the toe is tangential to the surface). The state of the character object may be further modified to update one or more other geometric or non-geometric attributes, such as to change the orientation of the foot as depicted in  FIG. 5B . At time T 4 , the character travels to yet another new location. At this new location, the ground surface as represented by the depth map may be level again (i.e., not have a bump or hill). Accordingly, at T 4 , the position of point P is determined relative to the ground surface using the depth map representing the ground surface. The state of the character object may be updated such that point P is placed on the ground surface (the toe is pointing up slightly). The state of the character object may be further modified to update one or more other geometric or non-geometric attributes of the character object. 
     In one embodiment, to re-position and align the object multiple points are used. For example, for a foot object, a set of discrete points on the sole of the foot are sampled. These sample points estimate the shape of the sole and the distance from the sole to the IK target (e.g., ankle) point. After computing the current state, the system projects each deformed sample point onto the ground surface. In certain aspects, depth map projection technology is used for ground plane generation and ground projection. To compute the orientation coordinate frame, the furthest projected points at the toe and heel are used to determine the y-direction of the frame, and the furthest left and right points are used to determine the x-direction. Once the foot is oriented properly, its displacement is computed. To accomplish this, the rotated sample points are projected to the ground again, sample point whose projection has the greatest displacement is chosen, and this displacement is used to translate the IK target (the ankle) Thereafter, the system deforms the foot to reflect how it is pushed against the ground. The system also allows users to morph from the initial foot rotation to the ground rotation smoothly, by interpolating between the initial rotation matrix and final rotation matrix. 
     In this manner, the state of the character object is updated such that the resultant position of the foot component(s) is such that the foot of the character is glued or locked to the ground surface (i.e., are positioned on the ground surface) for different ground terrains and the contact of the foot is oriented on the ground surface as desired. If the character walks over varying terrain, then the position and orientation of the character is also modified such that the foot is placed on or near the ground surface. Accordingly, the position and orientation of the foot changes responsive to or reactive to changes in the ground terrain as encoded in the depth map representing the ground, thereby making the resultant animation look more realistic. For a character with multiple feet, each foot of the character may be locked to the ground independently using the techniques described above. 
     IK Solver and UI 
     As an example, for a human object model, three joints at the hip, knee, and ankle are controlled by a two-segment IK solver. The animator chooses a target position for the ankle, which determines the foot position. The ideal solver would maximize the contact area between the two irregular rigid surfaces (the foot and the ground) by simultaneously solving for the translation and rotation of the foot; but this problem has no analytical solution. To keep the solver fast and analytical, the rotation and translation calculations are decoupled in one embodiment. The solution is approximate, but is close enough to the ideal solution that it provides a useful guideline, while it keeps the system fast and history-free. 
     In one embodiment, the ground locking computation is implemented as a controller, which outputs a set of values that can be written to existing animation controls such as “Foot IK Translate” T x , T y , T z  and “Foot Rotate” R x , R y , R z . These animation control variables may be stored or cached for later use and they may also be exported for use by another image processing application. To keep the user interface simple and intuitive in certain aspects, a translation direct manipulation widget is provided to translate, rotate, and deform the foot against the ground. When the foot hits the ground surface, the foot stops. As the animator pulls the widget further below the ground, the foot is rotated smoothly and eventually aligns with the surface. If he/she pulls the widget even further, the foot starts being squashed. Once the animator is satisfied with the look, he/she releases the widget, and all the translation and rotation values are recorded. He/she may tweak the values in the attribute editors or spline editors afterwards. 
     System Components 
       FIG. 6  is a block diagram of a computer system that may be used to practice various embodiments.  FIG. 6  is merely illustrative of an embodiment incorporating the present invention and does not limit the scope of the invention as recited in the claims. One of ordinary skill in the art would recognize other variations, modifications, and alternatives. 
     In one embodiment, computer system  600  typically includes a monitor  610 , computer  620 , a keyboard  630 , a user input device  640 , computer interfaces  650 , and the like. 
     In various embodiments, user input device  640  is typically embodied as a computer mouse, a trackball, a track pad, a joystick, wireless remote, drawing tablet, voice command system, eye tracking system, and the like. User input device  640  typically allows a user to select objects, icons, text and the like that appear on the monitor  610  via a command such as a click of a button or the like. 
     Embodiments of computer interfaces  650  typically include an Ethernet card, a modem (telephone, satellite, cable, ISDN), (asynchronous) digital subscriber line (DSL) unit, FireWire interface, USB interface, and the like. For example, computer interfaces  650  may be coupled to a computer network, to a FireWire bus, or the like. In other embodiments, computer interfaces  650  may be physically integrated on the motherboard of computer  620 , and may be a software program, such as soft DSL, or the like. 
     In various embodiments, computer  620  typically includes familiar computer components such as a processor  660 , and memory storage devices, such as a random access memory (RAM)  670 , disk drives  680 , a GPU  685 , and system bus  690  interconnecting the above components. 
     In some embodiment, computer  620  includes one or more Xeon microprocessors from Intel. Further, one embodiment, computer  620  includes a UNIX-based operating system. 
     RAM  670  and disk drive  680  are examples of tangible media configured to store data such as image files, models including geometrical descriptions of objects, ordered geometric descriptions of objects, procedural descriptions of models, scene descriptor files, shader code, a rendering engine, embodiments of the present invention, including executable computer code, human readable code, or the like. Other types of tangible media include floppy disks, removable hard disks, optical storage media such as CD-ROMS, DVDs and bar codes, semiconductor memories such as flash memories, read-only-memories (ROMS), battery-backed volatile memories, networked storage devices, and the like. 
     In various embodiments, computer system  600  may also include software that enables communications over a network such as the HTTP, TCP/IP, RTP/RTSP protocols, and the like. In alternative embodiments of the present invention, other communications software and transfer protocols may also be used, for example IPX, UDP or the like. 
     In some embodiments of the present invention, GPU  685  may be any conventional graphics processing unit that may be user programmable. Such GPUs are available from NVIDIA, ATI, and other vendors. In this example, GPU  685  includes a graphics processor  693 , a number of memories and/or registers  695 , and a number of frame buffers  697 . 
       FIG. 6  is representative of a computer system capable of embodying the present invention. It will be readily apparent to one of ordinary skill in the art that many other hardware and software configurations are suitable for use with the present invention. For example, the computer may be a desktop, portable, rack-mounted or tablet configuration. Additionally, the computer may be a series of networked computers. Further, the use of other micro processors are contemplated, such as Pentium™ or Itanium™ microprocessors; Opteron™ or AthlonXP™ microprocessors from Advanced Micro Devices, Inc; and the like. Further, other types of operating systems are contemplated, such as Windows®, WindowsXP®, WindowsNT®, or the like from Microsoft Corporation, Solaris from Sun Microsystems, LINUX, UNIX, and the like. In still other embodiments, the techniques described above may be implemented upon a chip or an auxiliary processing board. 
     While the invention has been described by way of example and in terms of the specific embodiments, it is to be understood that the invention is not limited to the disclosed embodiments. To the contrary, it is intended to cover various modifications and similar arrangements as would be apparent to those skilled in the art. Therefore, the scope of the appended claims should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements.
Systems and methods for positioning a component of an inverse kinematics (IK) controlled animated object relative to a surface object. To help users deal with foot-ground (or other object-object) interactions efficiently, a foot-ground locking system is provided as a preprocessor to an inverse kinematics (IK) controller to automatically pose the foot on the ground. The foot is first rotated to reach the maximal contact area with the ground, then translated to touch the ground, and finally deformed to conform more tightly to the ground. The system works properly with other foot shape deformations, such as toe, heel, and ball rotations. The foot-ground locking can be used either as an interactive tool to help animators identify where the ground is or as a batch postprocessing tool to clean up foot-ground contacts whenever the animation or ground environment is changed.