Skip to content

Instantly share code, notes, and snippets.

@TwistedTwigleg

TwistedTwigleg/GSOC_2020_Final_Evaulation_Report.md

Last active March 11, 2023 15:45
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save TwistedTwigleg/3e4a8dabc6d5f64ba7ed49eb43de5ce9 to your computer and use it in GitHub Desktop.
Save TwistedTwigleg/3e4a8dabc6d5f64ba7ed49eb43de5ce9 to your computer and use it in GitHub Desktop.
Download ZIP
GSOC 2020 Final Evaluation Report
Raw
GSOC_2020_Final_Evaulation_Report.md

Inverse Kinematics additions and extensions - Noah Beard

Project Overview

Over the Google Summer of Code period, I have been working on adding and improving the Inverse Kinematics (IK) capabilities in the Godot game engine. Put simply, Inverse Kinematics is a term given to the process of rotating a set of bones, generally referred to as a "bone chain", algorithmically so that they move and react in an expected, procedural way. IK has many uses in the game development industry and, as such, it is important for Godot to have strong IK offerings that can help game developers achieve their project goals quickly and easily.

My proposal was to implement the following IK solvers in both 2D and 3D: LookAt, CCDIK, FABRIK, Jiggle, and TwoBoneIK. Additionally, my proposal was to improve the Skeleton3D and Skeleton2D APIs, devise a system for IK that can be extendable by users, refactor the code relating to handling bones, and to make the entire process easier for Godot users.

Progress Report

Here is a bullet point list of everything I have accomplished during the GSOC period:

3D changes:

  • Created a extendable Resource for creating IK and other skeleton operations called SkeletonModification3D.

    • This resource is the backbone of the IK system I created. This class is used by all of the IK algorithms I implemented, and is extendable by users. Because the resource can be used for more than IK, I named them "modifications" and will refer to them as such interchangably with IK.
    • This class extends Godot's Resource class, allowing it to be saved to a file. Additionally, all important properties for this class and any modifications that extend it are entirely visible in the Godot editor.
    • Modifications can be told to run in _process or _physics_process on a per-modification basis! This allows you to mix-and-match physics aware modifications with modifications that are not physics aware.
    • The SkeletonModification3D system did not introduce any dependencies into Skeleton3D! The SkeletonModification3D resource only relies on SkeletonModificationStack3D.

  • Created a Resource called SkeletonModificationStack3D, which holds a list/stack of modifications.

    • Through this class, one can use individual SkeletonModification3D resources together. This allows for complex systems of modifications that all work together to achieve a finished result, like full-body IK setups.
    • This class also acts as the bridge between the Skeleton3D and the SkeletonModification3Ds that are executing. The SkeletonModificationStack3D also handles executing all of the SkeletonModification3D resources in the correct order, at the correct time.
    • SkeletonModificationStack3D extends Godot's Resource class so it can be saved to a file, which allows for using the stack with imported scenes without having to worry about reconfiguring everything if the property is lost in reimport.

  • I fully implemented the LookAt solver: SkeletonModification3DLookAt.

    • This solver rotates a single bone in the chain so that it looks at a external, target node. This is commonly used for rotating the head of a character to look at a object of interest, to move the eyes in a character, or really any usecase where you might need to rotate a single bone to look at something in the scene.
    • The solver has many exposed properties and additional functionality, like limiting rotation to a plane, applying additional rotation, and more.

  • I have implemented the CCDIK solver: SkeletonModification3DCCDIK

    • This solver uses the Cyclic Coordinate Descent (CCD) IK algorithm to place the tip given on a end of a chain of bones at the target position. CCDIK rotates each joint on a single axis, and is ideal for robotic joints or skeletons that have realtively mechnical motion requirements.
    • CCDIK operates on a chain of bones and exposes properties for each bone in the chain. These properties include angle constraints, selection of rotation axis, and more.
    • CCDIK also has a high quality solve option, that gives more natural looking results at a slight performance cost. This option was discovered while rewritting the CCDIK solver for the second time during the GSoC period.
    • CCDIK is mostly fully implemented, with the only snag being that it returns different results than those seen in the prototype I made in GDScript prior to the start of GSoC. I am unsure on why this occurs, as algorithmically and code-wise they are practically identical. Outside of that, CCDIK is fully implemented.

  • I have fully implemented the FABRIK solver: SkeletonModification3DFABRIK

    • This solver uses the Forward And Backwards Reaching IK (FABRIK) algorithm to rotate a series of joitns so that final bone in the chain touches the target position. FABRIK is ideal for a huge variety of situations and is the same algorithm used in Godot's SkeletonIK node.
    • FABRIK operates on a chain of bones and exposes a number of helpful properties for getting FABRIK running quickly and easily. These properties incldue: options for auto-calculating joint length, per-joint magnet positions, the option to use a node for calculating the tip length, bone roll/twist, and more.
    • The FABRIK modification also exposes properties for setting the chain tolerance (minimum required distance for a "successful" solve) and the maximum amount of iterations the algorithm can use per solve.
    • Like with Godot's SkeletonIK node, the target node's rotation (Basis) can be used for the tip/final bone in the chain.

  • I have successfully fully implemented the Jiggle solver: SkeletonModification3DJiggle

    • This solver is similar to LookAt, in that it rotates a series of bones to look at a target. Unlike LookAt, it uses a simple physics calculation that allows it to overshoot the target when rotating. This allows the Jiggle modification to act like a spring or the edge of cloth, making it ideal for complementary dynamic anmiations.
    • Jiggle operates on a chain of bones and exposes the physics properties for each joint. By default, all joints use a "global" set of settings, but these can be overriden on a per-joint basis.
    • The Jiggle modifier has physics collider support! The solver can optionally detect colliders when solving using Raycasting, and will not rotate itself into them. This makes the Jiggle modifier much more controllable and usable as a dynamic animation tool. Huge thanks to NHodgesVFX for the suggestion and a link to some code for reference use!

  • I have successfully fully implemented the TwoBoneIK solver: SkeletonModification3DTwoBoneIK

    • This solver uses the Law of Cosigns to find a rotation for the two bones where the second bone touches the target position. It produces results similar to FABRIK, but is not as costly to calculate. However, the algorithm only works on two bones, while FABRIK works on N bones (where N>2). TwoBoneIK is great for arms, legs, and any limbs that cam be composed of just two bones.
    • Exposes many properties to configure how the solver operates. Can automatically calculate joint length for quick and easy setup.
    • Has an option to use an external node as a pole vector, which allows the user to use the node to control the direction that the TwoBoneIK solver will bend the bones when contracting to reach the target.

  • I added a stack holder modification: SkeletonModification3DStackHolder:

    • This modification holds an additional SkeletonModificationStack3D and will execute it when the modification is told to execute. This allows for using more than a single modification stack on any given Skeleton3D.

  • I refactored the code for bones in Skeleton3D

    • Now bones have a new property, local_pose_override, which allows for overriding the transfrom while still being modified by parent bones. I also added functions to make converting between the various bone transforms (local, global, world) easier for both C++ developers and users.
    • Bones now keep tract of their children bones. While this is a compatibility breaking change, it greatly simplifies the code and makes it easier to iterate over the entire skeleton, with full skeleton bone interations no longer requiring a prebaked process order list of bones. This also makes it possible to selectively update just a bone and it's children, something that was not possible prior to this change.

  • I refactored BoneAttachment3D node

    • I decoupled all of the functionality of the BoneAttachment3D node from the Skeleton3D node. This helps make the Skeleton3D and BoneAttachment3D nodes more standalone. All of the code that Skeleton3D had for binding nodes has been removed. BoneAttachment3D now instead relies on a signal to know when to update its transform, and this signal can also be used by GDScript users if they want to write their own, custom BoneAttachment3D node.
    • BoneAttachment3D can now set the bone via its index, rather than only its string. This allows for quickly changing the bone it is bound to if you know roughly which index you want.
    • BoneAttachment3D now no longer requires being a direct child of a Skeleton3D node to operate. There is now properties exposed for using external Skeleton3D nodes. This is extremely helpful for instanced 3D files, as users can now optionally use external BoneAttachment3D nodes and not worry about loosing them on reimporting 3D assets.
    • BoneAttachment3D can now override bone poses. This allows for modifing the bone poses from the node in real time. The bone poses that are currently overridable are global_pose_override, local_pose_override, and custom_pose. When set to override, the BoneAttachment3D node will not follow the transform of the bone it is set to and instead will override it.
    • All new features added to BoneAttachment3D are disabled by default, making the node function exactly as it used to prior to the changes, giving full compatibility with projects that are already using the node.

  • Added a function called rotate_to_align in Godot's Basis class. This function creates a rotation that starts at one vector, and ends at the other vector. It is heavily used in the SkeletonModification3Ds I have implemented.

  • Added class reference documentation for all changes, additions, and anything I touched!

2D Changes:

  • I have fully implemented both SkeletonModification2D and SkeletonModificationStack2D resources. Both of these resources work just like the 3D equivalent, but they work on a Skeleton2D node rather than a Skeleton3D one.

  • I have fully implemented a 2D LookAt solver: SkeletonModifiation2DLookat

    • This modification works exactly the same way as the 3D equivalent, just in 2D. As such, it does not have support for rotating on a single axis, since there is only one axis of rotation in 2D. Outside of that change, it supports all the same functionality.
    • The 2D LookAt modification has fully working angle constraints! These constraints can be applied in local-space (relative to the parent bone's rotation) or global-space (relative to the scene's origin).

  • I have fully implemented a 2D CCDIK solver: SkeletonModification2DCCDIK

    • Works just like the 3D algorithm and all the same properties, with slight adjustments to make it run in 2D.
    • Has full angle constraint support in both local-space and global-space.

  • I have fully implemented a 2D FABRIK solver: SkeletonModification2DFABRIK

    • Works just like the 3D algorithm and has all of the same properties, but for 2D instead of 3D.
    • Has full angle constraint support! This is a major difference than the 3D version, which does not support angle constraints. Angle constraints are taken into account when solving. As of when this was written, angle constraints are enforced in local-space. This allows users to constrain each joint in the bone chain to a certain range of angles, and the FABRIK algorithm will take these into account and try to find a solve that satisfies the constraints while still reaching the target.
    • The final bone in the IK chain can use the target's rotation (basis), just like the 3D version and the SkeletonIK node.

  • I have fully implemented a 2D Jiggle solver: SkeletonModification2DJiggle

    • Works just like the 3D version, but in 2D. Supports all the same physics properties and has fully functioning collider support. Collider support even works in the Godot editor!

  • I have fully implemented a 2D TwoBoneIK solver: SkeletonModifiation2DTwoBoneIK

    • Works just like the 3D version, but in 2D. Uses the Bone2D node's to calculate bone length, making it extremely easy to get setup and running. Has basic support for angle constraints, but this is a visual only constraint and is not taken into account by the solver.
    • Has a property for flipping the bend direction rather than supporting a pole node, as the TwoBoneIK solver in 2D can only bend inwards or outwards due to how rotation works in 2D.

  • I added a 2D stack holder modification: SkeletonModification2DStackHolder

    • Works just like the 3D version and has all the same benefits.

  • I added a 2D physics bone node: PhysicalBone2D

    • The node extends RigidBody2D and allows for fully physics aware 2D skeletons. Works just like the 3D PhysicalBone3D node but for 2D.
    • Because it extends RigidBody2D, it can be modified and pushed around the physics world using the exact same API as RigidBody2D. Any changes made to RigidBody2D are automatically felt by the PhysicalBone2D node.
    • The node has to be a child of a Skeleton2D node or another PhysicalBone2D node to function.
    • Will automatically position itself to the Bone2D node its bound to when not simulating physics. Can be told to stay at the transform of the Bone2D node when simulating, so it can be used as the root of a physics chain.
    • Supports Joint2D nodes and can optinally automatically position these nodes in the correct position (for PinJoint2D at least).

  • I added a helper modification for PhysicalBone2D: SkeletonModification2DPhysicalBones

    • This modifier applies the PhysicalBone2D node positions to the Bone2D nodes. It also exposes an API that is almost identical to that of the PhysicalBone3D node in the Skeleton3D. Users who are used to using PhysicalBone3D and Skeleton3D should find the 2D API in PhysicalBone2D and this modification easy to use and adapt to.

  • Skeleton2D changes:

    • Skeleton2D now has a local_pose_override transform. It works just like the Skeleton3D transform with the same name, but in 2D and with Bone2D nodes.

  • Bone2D changes:

    • Bone2D now automatically calculates bone length by default. Bone2D also will calculate a new property, bone_angle, which is the angle from the Bone2D node to it's child (first child if more than one) Bone2D node. This is needed because Bone2D connections are not rotation linked, and therefore the angle between the Bone2D node and its children are needed for bone chains. Both of these properties are calculated automatically, but they can be manually entered if desired.
    • Bone2D now internally caches its Transform when not being modified by skeleton modifications. This is needed for skeleton modification interpolation and for saving the Bone2D node while skeleton modifications are running.
    • Bone2D now handles its own editor gizmo. It works exactly the same as before, but will change color when IK is running, can be hidden on a per-bone basis, takes the bone angle into account, and uses a slightly transparent color so its easier to see what the Bone2D is effecting. The gizmo is only drawn in the Godot editor, costing no performance to exported projects.

  • CanvasItemEditor changes:

    • CanvasItemEditor no logner handles drawing the Bone2D gizmos. This simplified the code nicely and without this change, certain functionality, like coloring the gizmo when IK is running, would have been extremely difficult to implement.
    • The 2D "bone" code and IK code in CanvasItemEditor has been removed! This was confusing for as there was two types of bones in 2D. Additionally, the old IK code was heavily intergated into CanvasItemEditor, could not function during runtime, and added code complexity that is no longer needed due to the SkeletonModification2D system.
    • Changed some of the Bone2D related dropdown options. The Show Bones option now hides the Bone2D gizmos; Create Custom Bone(s) from Node(s) has been replaced with Create Custom Bone2D(s) from Node(s), which creates Bone2D nodes at the selected Node2D positions; and old Bone2D related dropdown options that no longer apply (IK stuff mainly) were removed.

  • Added a looking_at function to Transform2D, increasing the API parity between the 2D and 3D sides of Godot. This function was also required for the LookAt modification in 2D.

  • Added new notifications, NOTIFICATION_EDITOR_PRE_SAVE and NOTIFICATION_EDITOR_POST_SAVE, which are called when the Godot editor is about to save a scene. This was required for the Bone2D to work correctly when saving a scene with IK running, and should also help users making Godot plugins for the Godot editor.

  • Added class reference documentation for all changes, additions, and anything I touched!

Other changes include:

Final Thoughts

I was able to achieve the goals I set out to accomplish. There is still more work to be done and the code still needs review prior to being merged into Godot, but I am confident that I can finish the remaining work and have finished, merge-ready pull requests by the end of the year.

Looking back on this summer, I am really proud of what I have been able to accomplish during the Google Summer of Code period. Having been a part of the Godot community for the last 4 years, I have been amazed to see how much Godot has grown, continues to grow, and the wide range of projects that have been made using the engine. I have no doubt that Godot 4.0 is going to be amazing!

I want to thank Google for providing the opportunity to work throughout this summer on Godot. I also want to thank Joan, my GSoC mentor, for his amazing guidance and support. It has been a great experience working throughout the summer with him and his help has been invaluable. I also want to thank the Godot team for the opportunity, oversight, and support. Finally, I want to thank all of the other Godot contributors who have helped, commented, offered support, and otherwise contributed to making this opportunity possible.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment