For a long time I had been delaying finding a solution to feet etc interpenetrating terrain in my game. Finally I asked for suggestions here, and came to the conclusion that Inverse Kinematics (IK) was probably the best solution.

https://www.gamedev.net/forums/topic/694967-animating-characters-on-sloping-ground/

There seem to be quite a few 'ready built' solutions for Unity and Unreal, but I'm doing this from scratch so had to figure it out myself. I will detail here the first foray into getting IK working, some more steps are remaining to make it into a working solution.

Inverse Kinematics - how is it done?

The two main techniques for IK seem to be an iterative approach such as CCD or FABRIK, or an analytical solution where you directly calculate the solution. After some research CCD and FABRIK looked pretty simple, and I will probably implement one of these later. However for a simple 2 bone chain such as a leg, I decided that the analytical solution would probably do the job, and possibly be more efficient to calculate.

The idea is that based on some school maths, we can calculate the change in angle of the knee joint in order for the foot to reach a required destination.

The formula I used was based on the 'law of cosines':
https://en.wikipedia.org/wiki/Law_of_cosines

I will not detail here but it is easy enough to look up.

For the foot itself I used a different system, I calculated the normal of the ground under the foot in the collision detection, then matched the orientation of the foot to the ground.

My test case was to turn off the animation and just have animals in an idle pose, and get the IK system to try to match the feet to the ground as I move them around. The end effect is like ice skating over the terrain. First I attempted to get it working with the main hero character.

Implementing

The biggest hurdle was not understanding IK itself, but in implementing it within an existing skeletal animation system. At first I considered changing the positions of the bones in local space (relative to the joint), but then realised it would be better to calculate the IK in world space (actually model space in my case), then somehow interpolate between the local space animation rotations and the world space IK solution.

I was quite successful in getting it working until I came to blending between the animation solution and the IK solution. The problems I was having seemed to be stemming from my animation system concatenating transforms using matrices, rather than quaternions and translates. As a result, I was ending up trying to decompose a matrix to a quaternion in order to perform blends to and from IK.

This seemed a bit ridiculous, and I had always been meaning to see whether I could totally work the animation system using quaternion / translate pairs rather than matrices, and it would clearly make things much easier for IK. So I went about converting the animation system. I wasn't even absolutely sure it would work, but after some fiddling, yay! It was working.

I now do all the animation blending / concatenation / IK as quaternions & translates, then only as a final stage convert the quaternion/translate pairs to matrices, for faster skinning.

This made it far easier in particular to rotate the foot to match the terrain.

Another snag I found was that blender seemed to be exporting some bones with an 'extra' rotation, i.e. if you use an identity local rotation the skin doesn't always point along the bone axis. I did some tests with an ultra simple 3 bone rig, trying to figure out what was causing this (perhaps I had set up my rig wrong?) but no joy. It is kind of hard to explain and I'm sure there is good reason for it. But I had to compensate for this in my foot rotation code.

Making it generic

To run the IK on legs, I set up each animal with a number of legs, and the foot bone ID, number of bones in the chain etc. Thus I could reuse the same IK routines for different animals just changing these IK chain lists. I also had to change the polarity of IK angles in some animals .. maybe because some legs work 'back to front' (look at the anatomy of e.g. a horse rear leg).

The IK now appears to be working on most of the animals I have tested. This basic solution simply bends the knees when the ground level is higher than the foot placed by the animation. This works passably with 2 legged creatures but it is clear that with 4 legged creatures such as elephant I will also have to rotate the back / pelvis to match the terrain gradient, and perhaps adjust the leg angles correspondingly to line up with gravity.

At the moment the elephant looks like it is sliding in snow down hills.

Blending

To blend the IK solution with the animation is kind of tricky to get to look perfect. It is clear when the foot from the animation is at ground level or below, the IK solution should be blended in fully. At a small height above the ground I gradually blend back from the IK into the animation. This 'kind of' works, but doesn't look as good as the original animation, I'm sure I will tweak it.

Another issue is that when one leg is on an 'overhang', you can end up with a situation where the fully outstretched leg cannot reach the ground. I have seen that others offset the skeleton downwards in these cases, which I will experiment with. Of course this means that the other leg may have a knee bent further than physically possible. So there are limits to what can be achieved without rotating the animals pelvis / back.
 
 Anyway this is just description of the trials I had, hopefully helpful to those who haven't done IK, and maybe will generate some tips from those of you that have already solved these problems.