Frankiezafe (Talk | contribs) |
Frankiezafe (Talk | contribs) (→References) |
||

(25 intermediate revisions by the same user not shown) | |||

Line 1: | Line 1: | ||

− | Notes about computation of inverse kinematics<ref>Inverse kinematics sur [[wikipedia:Inverse_kinematics|wikipedia]]</ref> | + | Notes about computation of inverse kinematics<ref>Inverse kinematics sur [[wikipedia:Inverse_kinematics|wikipedia]]</ref>, first implementation done in threejs<ref>Three.js is a 3d rendering engine written in javascript, more on [[wikipedia:Three.js|wikipedia]]</ref>. |

[[File:Solving-ik-001.png|800px]] | [[File:Solving-ik-001.png|800px]] | ||

Line 7: | Line 7: | ||

The main issue seems to be the computation of the knee position. All distances are easily computed: | The main issue seems to be the computation of the knee position. All distances are easily computed: | ||

− | * | + | * upperleg (red) keeps its length |

* leg (yellow) keeps its length also | * leg (yellow) keeps its length also | ||

* distance between the target and the origin of the upper leg can be easily computed in world space. | * distance between the target and the origin of the upper leg can be easily computed in world space. | ||

− | Rendering the position of the knee is crucial to compute the rotation | + | Rendering the position of the knee is crucial to compute the rotation of the upper leg. Once correct, the rotation of the leg will be simple to render, as it is the rotation from the current direction to the [knee - target] direction. |

+ | |||

+ | == Spheres == | ||

A little warning: the graphic here above is in 2d. In a 3d world, the position of the knee is a circle on a sphere: any point being at the right distance of the target point '''and''' the upperleg origin will be a valid candidate! The circle of possibilities is the intersection of 2 spheres having their radii equals to bones length. | A little warning: the graphic here above is in 2d. In a 3d world, the position of the knee is a circle on a sphere: any point being at the right distance of the target point '''and''' the upperleg origin will be a valid candidate! The circle of possibilities is the intersection of 2 spheres having their radii equals to bones length. | ||

Line 25: | Line 27: | ||

[[File:Sphere-Sphere Intersection.png]] | [[File:Sphere-Sphere Intersection.png]] | ||

− | The tricky point | + | The tricky point is to forget about the spheres' position and only consider the distance of their centers as the ''d'' parameter. The normal of the intersection plane can be computed independently. |

<html><iframe src="https://www.openprocessing.org/sketch/539606/embed/?plusEmbedHash=ZTk4N2UyMzUyM2U4ZDc5OWUzYmYyM2NkYjZjYTUwNGYyZGU0YTNhMjJlZDM0NTI2NzE2NzlmMzM4MThmZTRkNTU1NjFiOGU1ZjhjYThmNGJhMTlkYTgxNmJhZjJkM2NmYjI3OTBlNDBlNzBhYjNlZjFiNmI5NDg3MGRkMDYyOWYwU2ZqdDEvS2ZaMHJiaUtKeWY3WkJXVDRYQ1J1bUpBUXYzZklmSnRBTjQrU1Fid3NMbzhxSWlsbUU4Q0ZKT1dEQ1luRjZoVmVxY1FGcnZNR2g1dnBiZz09" width="800" height="600"></iframe></html> | <html><iframe src="https://www.openprocessing.org/sketch/539606/embed/?plusEmbedHash=ZTk4N2UyMzUyM2U4ZDc5OWUzYmYyM2NkYjZjYTUwNGYyZGU0YTNhMjJlZDM0NTI2NzE2NzlmMzM4MThmZTRkNTU1NjFiOGU1ZjhjYThmNGJhMTlkYTgxNmJhZjJkM2NmYjI3OTBlNDBlNzBhYjNlZjFiNmI5NDg3MGRkMDYyOWYwU2ZqdDEvS2ZaMHJiaUtKeWY3WkJXVDRYQ1J1bUpBUXYzZklmSnRBTjQrU1Fid3NMbzhxSWlsbUU4Q0ZKT1dEQ1luRjZoVmVxY1FGcnZNR2g1dnBiZz09" width="800" height="600"></iframe></html> | ||

Line 31: | Line 33: | ||

Implementation of the equation in an [https://www.openprocessing.org/sketch/539606 openprocessing] sketch. | Implementation of the equation in an [https://www.openprocessing.org/sketch/539606 openprocessing] sketch. | ||

− | + | == Selecting a point on the circle == | |

− | + | To select a point on the intersection of the 2 spheres, we first computed a quaternion representing the rotation to apply on a unit vector. As the Z axis is pointing forward in the model, we can use a vector( 0, 0, 1 ) to compute the orientation: | |

− | + | ||

− | = | + | var spheres_center_quat = new THREE.Quaternion().setFromUnitVectors( |

+ | new THREE.Vector3( 0, 0, 1 ), | ||

+ | spheres_center_dir.clone().normalize() ); | ||

− | + | [[File:Ik-avatar-bone axis.png|200px]] | |

+ | |||

+ | We apply this rotation on a perpendicular vector, vector( 0, 1, 0 ) in this case, and multiply it by the circle's radius (''CRAD''). | ||

+ | |||

+ | var offset = new THREE.Vector3( 0, 1, 0 ); | ||

+ | offset.applyQuaternion( spheres_center_quat ); | ||

+ | offset.multiplyScalar( CRAD ); | ||

+ | |||

+ | We now have the offset relatively to the circle center, but we still don't know where it is. Basic geometry will give us its location: | ||

+ | |||

+ | var length = Math.sqrt( Math.pow( sphereA_radius,2 ) - Math.pow( CRAD,2 ) ); | ||

+ | |||

+ | The circle's center position is found by adding the normalised vector joining the 2 spheres centers multiplied by this length, to the position of the sphereA. | ||

+ | |||

+ | The knee position is found by adding the offset to the circle's center, represented here below by the yellow sphere. | ||

+ | |||

+ | [[File:Threejs-ik-end of the day.png|400px]] | ||

+ | |||

+ | <html><video width="400" height="400" controls> | ||

+ | <source src="https://frankiezafe.org/images/b/b0/Ik_cropped0001-0629.ogv" type="video/mp4"> | ||

+ | Your browser does not support the video tag. | ||

+ | </video></html> | ||

+ | |||

+ | Computation of inverse kinematics on left and right legs. | ||

+ | |||

+ | This method is not too bad, but only works if the orientation of the higher bone in the hierarchy is close to the world's orientation. Once this bone is not aligned anymore, the procedure fails to output valid results: the leg is twisted when the avatar is lying on the floor, for instance, and the arm kinetics are simply wrong. | ||

+ | |||

+ | == Projection of initial orientation == | ||

+ | |||

+ | The first version of the algorithm is not taking into account the initial orientation of the origin bones (higher one in the hierarchy). The problem is solved in world space, independently of the orientation of the limb before the computation of the IK. | ||

+ | |||

+ | To solve this, we need a bit more complex projection of axis. | ||

+ | |||

+ | Here above, we have computed: | ||

+ | |||

+ | # the radius of the circle; | ||

+ | # the position of the circle center; | ||

+ | # the orientation of the plane; | ||

+ | # and the '''offset''' vector bringing us form the center to a specific point on its perimeter. | ||

+ | |||

+ | The 3 first point are valid, but the last one is based on world axis! We can based a fourth steps on the orientation of the plane, as it's give us 3 valid axis. 2 of them are coplanars to the circle's plane, X and Y unit axis, and Z is representing the normal<ref>Definition of normal vector on [http://mathworld.wolfram.com/NormalVector.html wolfram]</ref>. This last one is the only valid one (there's only one normal to a plane), X and Y must be re-aligned with the origin ones, without leaving the plane. | ||

+ | |||

+ | To achieve this, we have to project one relevant axis onto the circle's plane. | ||

+ | |||

+ | == References == | ||

<references/> | <references/> | ||

+ | |||

+ | * [https://www.youtube.com/watch?v=LNidsMesxSE Animation Bootcamp: An Indie Approach to Procedural Animation] - a [http://www.gdconf.com GDC] talk about character animation in a computation effective way. | ||

+ | * [http://wiki.roblox.com/index.php?title=Inverse_kinematics#FABRIK Inverse kinematics] on roblox via [http://lephas.me/ Sébastien Courvoisier]. | ||

+ | * [http://www.gaalop.de/dhilden_data/ICCA7.pdf Inverse kinematics computation in computer graphics and robotics using conformal geometric algebra] by Dietmar Hildenbrand, Julio Zamora and Eduardo Bayro-Corrochano, AMS Subject Classification: 15A66, 17B37, 20C30, 81R25 [[Media:ICCA7.pdf|pdf]]. | ||

+ | [[File:ICCA7 graphic.png|400px]] | ||

+ | * [[wikipedia:Frenet–Serret_formulas| Frenet–Serret formulas]], about normals and tangents. | ||

+ | [[File:Frenet.png|200px]] | ||

+ | * [https://stackoverflow.com/questions/9605556/how-to-project-a-point-onto-a-plane-in-3d How to project a point onto a plane in 3D?] on stackoverflow. | ||

[[category:javascript]] | [[category:javascript]] | ||

[[category:avatar]] | [[category:avatar]] | ||

[[category:threejs]] | [[category:threejs]] | ||

− | [[category: | + | [[category:3D]] |

[[category:animation]] | [[category:animation]] |

Notes about computation of inverse kinematics^{[1]}, first implementation done in threejs^{[2]}.

At this moment, the research is focusing on solving a 2 bones system, the leg in this case, but it would be applicable on the arms or any other part of a skeleton having at least 2 parents.

The main issue seems to be the computation of the knee position. All distances are easily computed:

- upperleg (red) keeps its length
- leg (yellow) keeps its length also
- distance between the target and the origin of the upper leg can be easily computed in world space.

Rendering the position of the knee is crucial to compute the rotation of the upper leg. Once correct, the rotation of the leg will be simple to render, as it is the rotation from the current direction to the [knee - target] direction.

A little warning: the graphic here above is in 2d. In a 3d world, the position of the knee is a circle on a sphere: any point being at the right distance of the target point **and** the upperleg origin will be a valid candidate! The circle of possibilities is the intersection of 2 spheres having their radii equals to bones length.

The radius of the cyan circle can be solved by using this equation^{[3]}:

a = 1/(2d)sqrt(4d^2R^2-(d^2-r^2+R^2)^2)

A little screenshot for better readability:

The tricky point is to forget about the spheres' position and only consider the distance of their centers as the *d* parameter. The normal of the intersection plane can be computed independently.

Implementation of the equation in an openprocessing sketch.

To select a point on the intersection of the 2 spheres, we first computed a quaternion representing the rotation to apply on a unit vector. As the Z axis is pointing forward in the model, we can use a vector( 0, 0, 1 ) to compute the orientation:

var spheres_center_quat = new THREE.Quaternion().setFromUnitVectors( new THREE.Vector3( 0, 0, 1 ), spheres_center_dir.clone().normalize() );

We apply this rotation on a perpendicular vector, vector( 0, 1, 0 ) in this case, and multiply it by the circle's radius (*CRAD*).

var offset = new THREE.Vector3( 0, 1, 0 ); offset.applyQuaternion( spheres_center_quat ); offset.multiplyScalar( CRAD );

We now have the offset relatively to the circle center, but we still don't know where it is. Basic geometry will give us its location:

var length = Math.sqrt( Math.pow( sphereA_radius,2 ) - Math.pow( CRAD,2 ) );

The circle's center position is found by adding the normalised vector joining the 2 spheres centers multiplied by this length, to the position of the sphereA.

The knee position is found by adding the offset to the circle's center, represented here below by the yellow sphere.

Computation of inverse kinematics on left and right legs.

This method is not too bad, but only works if the orientation of the higher bone in the hierarchy is close to the world's orientation. Once this bone is not aligned anymore, the procedure fails to output valid results: the leg is twisted when the avatar is lying on the floor, for instance, and the arm kinetics are simply wrong.

The first version of the algorithm is not taking into account the initial orientation of the origin bones (higher one in the hierarchy). The problem is solved in world space, independently of the orientation of the limb before the computation of the IK.

To solve this, we need a bit more complex projection of axis.

Here above, we have computed:

- the radius of the circle;
- the position of the circle center;
- the orientation of the plane;
- and the
**offset**vector bringing us form the center to a specific point on its perimeter.

The 3 first point are valid, but the last one is based on world axis! We can based a fourth steps on the orientation of the plane, as it's give us 3 valid axis. 2 of them are coplanars to the circle's plane, X and Y unit axis, and Z is representing the normal^{[4]}. This last one is the only valid one (there's only one normal to a plane), X and Y must be re-aligned with the origin ones, without leaving the plane.

To achieve this, we have to project one relevant axis onto the circle's plane.

- ↑ Inverse kinematics sur wikipedia
- ↑ Three.js is a 3d rendering engine written in javascript, more on wikipedia
- ↑ Sphere-Sphere Intersection
- ↑ Definition of normal vector on wolfram

- Animation Bootcamp: An Indie Approach to Procedural Animation - a GDC talk about character animation in a computation effective way.
- Inverse kinematics on roblox via Sébastien Courvoisier.
- Inverse kinematics computation in computer graphics and robotics using conformal geometric algebra by Dietmar Hildenbrand, Julio Zamora and Eduardo Bayro-Corrochano, AMS Subject Classification: 15A66, 17B37, 20C30, 81R25 pdf.

- Frenet–Serret formulas, about normals and tangents.

- How to project a point onto a plane in 3D? on stackoverflow.

**online identity** ∋ [ **social** ∋ [mastodon♥, twitter®, ~~facebook®~~, diaspora, ~~linkedin®~~]
∥ **repos** ∋ [github®, gitlab♥, bitbucket®, sourceforge] ∥ **media** ∋ [itch.io®, vimeo®, peertube♥, twitch.tv®, tumblr®] ∥ **communities** ∋ [godotengine♥, openprocessing, stackoverflow, threejs]]