Strange behavior in solutions

[dai-ichi]

I'd been racking my brain as to why certain solutions don't seem to be calculated... even though the demo works perfectly in similar conditions. So to debug it, I just changed the demo to the 2-bone structure I'm using. The relevant demo codes looks like:

	FabrikBone2D basebone;
	basebone = new FabrikBone2D(new Vec2f(0,0), new Vec2f(0,6*boneLength));
	basebone.setClockwiseConstraintDegs(90.0f);
	basebone.setAnticlockwiseConstraintDegs(90.0f);		
	chain.addBone(basebone);
	
	// Fix the base bone to its current location, and constrain it to the positive Y-axis
	chain.setFixedBaseMode(true);		
	chain.setBaseboneConstraintType(BaseboneConstraintType2D.GLOBAL_ABSOLUTE);
	chain.setBaseboneConstraintUV( new Vec2f(0.0f, 1.0f) );

	// Create and add the second bone - 135 clockwise, 0 anti-clockwise
	chain.addConsecutiveConstrainedBone(new Vec2f(1.0f, 0.0f), 8*boneLength, 135.0f, 0);

And the demo plots it like this:

It will work correctly for all points right of (0,0). But if you click to the left of 0,0 you get unreachable even though with the set constraints, a solution should be possible.

You can actually get to the solution if you DRAG the effector over to the desired point. But it would be better if the solution was correctly calculated with a single touch.

I looked at the source code, but the cause of the problem wasn't immediately apparent. So I'm kicking it over the fence.

[dai-ichi]

I looked a lot closer into the source code and I think the problem is in how constraints are being handled in FabrikChain2D. Specifically it looks like the outermost bone constraints limit the entire solution. So since my outermost constraints (which reflect the real capabilities of the arm) has a zero counterclockwise constraint, the passes will not consider solutions to the left of zero... even though that zero constraint becomes non-limiting if you move the second bone into the required position. This also explains why "dragging" the effector point works--it's because the micro adjustments of the drag effectively moves the outermost bone (and therefore its constraints) until the target is inside the constraints.

If this is the case, how constraints are handled might need to be rethought.

[alansley]

Interesting. It may be that it needs to be modified so that constraints aren't honoured in the forward pass (end-effector-to-base) but then are honoured in the backward pass (base-to-end-effector). This sounds like it would fix it, but I'm not entirely certain, and I'm not certain what knock-on effects this might have. I'll try to have test it out soon.

[alansley]

Have replicated the issue - what an odd one! Removing the constraints in the forward pass doesn't resolve it - have been experimenting with things like having a first unconstrained pass to help guide the solution. No joy as yet but I'll have another shot at it soon.

[dai-ichi]

The comments in the code are a little confusing. But I had been playing around with the constraint code in Fabrik2D. The comments call "pass 1 of 2" the "forward pass," but I think it is really called the backward pass.

I found that getting rid of the constraint on pass "2 of 2" gives an (unconstrained) solution. But that isn't how to fix the problem, obviously, because we actually want a constrained solution. Unfortunately I don't understand the code enough to efficiently try to find a fix. My approach would have been a flag that says if the effector bone hit the constraint, on the backward pass treat the second bone as the effector bone, until the effector bone reaches the target within its constraints or the loop limit is reached.

But I don't know if it would work--and, like I said, I don't know enough about the code to try it.

[alansley]

Yeah, it is a little confusing that the 'forward' pass goes from tip-to-base - but that's how it's discussed in the FABRIK research paper (http://www.academia.edu/download/35451443/FABRIK.pdf) from which I implemented the algorithm, so I kept with it so everyone's on the same page.

If you take a look at the paper, or even just my code comments (of which there are bazillions) you should be able to work out how the solveIK method is working and try tweaking it. I'll have another crack at it soon, but I'm pushing hard to finish off another project at the moment and the vast amount of my time and energy has to go into that at present.

[jmsjr]

Been late to this thread ... but isn't the issue described here only exhibited if the target's distance from the basebone's startpoint < length of the chain ?

Thus, if the target's distance from the basebone's startpoint >= length of the chain, the solution works, whether you drag or point and click.

[joediscar]

You are correct. The solution is not found only if the distance from the basebone's startpoint < length of the chain. I believe Al is correct in that the problem is found in the backward pass.

[jmsjr]

Is this an acceptable IK solution with the given constraints ?

What I did was to constrain the effector bone on the forward pass

[alansley]

I'd say that would be the best possible solution given the constraints! But will that get there with a single click or does it need a drag?

If it'll do it in one 'cycle' of iterations then I'd be really interested to see if the same modification would help with the 3D snapping inconsistency issue, hard to guestimate these things ;-)

[jmsjr]

I'd say that would be the best possible solution given the constraints! But will that get there with a single click or does it need a drag?

If it'll do it in one 'cycle' of iterations then I'd be really interested to see if the same modification would help with the 3D snapping inconsistency issue, hard to guestimate these things ;-)

It was with a single click. I can make a pull request tomorrow .. I meant later tonight ( its 2am here in Sydney ) if needed.

[alansley]

Nothing's "needed", man - I'm just delighted with the solution and think you've made a really valuable contribution there! I tried relaxing the forward pass and didn't end up with the same results you did...

It's 2am in Melbourne, too - and I'm writing user documentation for my next project, haha =D

[jmsjr]

Pull request #13 created. Need another pair of eyes to verify the results that it has no side-effects.

[alansley]

Might well have a solution to this - #13 updated =D

However, I just tried implementing the same technique on fixed base 3D bones with rotor constraints like in 3D demo 2. Seems to work fine (as did the original), until you really heavily constrain the rotor angle (say 15 degrees or less) - which then makes the chain 'spin' and alternate looking for solutions...

I have a gut feeling that the modification is working to find better solutions than the current 'stock' implementation, but that the solutions just end up being far apart so they jump like crazy. I'll experiment with a fixed seed and some debug output to see if that's the case in the near future.

[alansley]

With massive thanks to jmsjr and some minor tweaking by me I think this issue is now resolved and can be closed. Hope this helps, dai-ichi! =D

-Al

(Re-opened to wait for feedback, got a touch carried away there, lol).

[alansley]

Dammit - still not 'best solution' under some circumstances. Will investigate further soon.

[jmsjr]

Do you have a test case ? Maybe an XML using the MarshallingUtil of the state of the chain before the IK solution and another one after the IK solution ? Just realised the XML does not actually include the actual coordinates target itself ( something to add next time ), but for now, just maybe give the 2D coordinates in this thread.

[joediscar]

Sorry got late--had a short vacation. Yes! That would be an acceptable solution given the constraints.

I was under the impression (from looking at your implementation in solveIK() that you check distance from the target to select a solution). Perhaps have a check that checks the sum of the maximum travel of bone endpoints... and attempt to minimize that too (with distance from target being the primary selector, perhaps). Just a thought.

[alansley]

Hi all,

The not 'best solution' I mention in my above comment is the situation where solve distance can't be met due to constraints. Both the old (1.3.2 and earlier) and new (1.3.3) solveIK behaviour currently aims to beat a solve distance of Float.MAX_VALUE on its first iteration, and if we can improve upon that (which we will) then we consider that a win and take a copy. When we hit the iteration limit before a distance solve we take the best solution found, and if we get within the solve distance threshold before hitting the iteration limit then obviously that's our winner so we take it and move on...

...however, there are times when even our best 'new' solution is worse than our current 'starting' solve distance to the new target location. To see what I mean, here's an example of when the current best solve makes things worse:

https://youtu.be/AQ2HzKJtXVY

And here's what happens if we calculate the distance from the original 'starting' solution to the new target location (i.e. take a copy of original solution) first, and THEN we allow the FABRIK algorithm to have a crack at it to see if it can do any better. If it can, superb - we'll use that. If it can't (and even the best solution after however many iterations is worse than doing nothing at all) - then we keep the original chain configuration. Take a look:

https://youtu.be/uUz4uXgi3Qg

Doing it this way where we might opt to not modify the solution at all has three knock-on effects:

1.) It requires an extra chain copy per solve attempt* (not per iteration - we only clone the chain pre-solve so we can 'revert' to it if we didn't come up with anything better),

* = IF the chain's base location hasn't changed only - see below post.

2.) Solutions may exhibit slightly more discontinuities (i.e. 'jump' more) under overly-constrained conditions, and

3.) Overall, solve distances will be improved because we always give FABRIK a shot at improving the solution. If the solve attempt can't improve upon the starting solution then we simply fall-back to our original solution so that while we may not be able to do any better, we're at least not making things any worse!

Personally, I'd rather take the minor processing hit to attempt a better solution - and then throw that work away if necessary, than provide a worse solution than the one we currently have. That is, the wrong answer is still wrong, regardless of how quickly you can calculate it ;-)

Would love to hear any thoughts on this you guys might have.

Cheers,
Al

P.S. joediscar - hope you had a good break =D

[alansley]

Oh, and just because nothing's ever simple - this 'potentially do nothing' approach breaks structures with multiple connected chains, so the 'worse solution' checking may have to be done at the structure level, not the individual chain level - and then we'd need to have some kind of policy, such as:

i.) Every chain in the structure must have a worse solution for us to do nothing, or

ii.) The majority of chains in a structure must have a worse solution for us to do nothing, or

iii.) The combined solve distances each chain in the structure must be greater than the combined 'do-nothing' solve distances for each chain in the structure (could be outlier chain solutions, so not quite the same as i.) ) for us to do nothing, or

iv.) Something else?!

However for a quick fix, the original behaviour for structures with multiple connected chains can still work if we just revert to the 'potentially-make-things-worse' behaviour if the base location of a chain moves. That might actually be the best option...

-Al

Try replacing FabrikChain2D's solveForTarget method with this if you'd like to experiment with it:

public float solveForTarget(Vec2f newTarget)
	{		
		// Same target as before? Abort immediately and save ourselves some cycles
		if ( mLastTargetLocation.approximatelyEquals(newTarget, 0.001f) && mLastBaseLocation.approximatelyEquals(mBaseLocation, 0.001f) )
		{
			return mCurrentSolveDistance;
		}
		
		// Keep starting solutions and distance
		float startingDistance;
		List<FabrikBone2D> startingSolution = null;
		
		// If the base location of a chain hasn't moved then we may opt to keep the current solution if our 
		// best new solution is worse...
		if (mLastBaseLocation.approximatelyEquals(mBaseLocation, 0.001f))
		{			
			startingDistance  = Vec2f.distanceBetween(mChain.get(mChain.size() - 1).getEndLocation(), newTarget);
			startingSolution = this.cloneChainVector();
		}
		else // Base has changed? Then we have little choice but to recalc the solution and take that new solution.
		{
			startingDistance = Float.MAX_VALUE;
		}
		
		// Not the same target? Then we must solve the chain for the new target.
		// We'll start by creating a list of bones to store our best solution
		List<FabrikBone2D> bestSolution = new ArrayList<>(this.mChain.size());
		
		// We'll keep track of our best solve distance, starting it at a huge value which will be beaten on first attempt			
		float bestSolveDistance     = Float.MAX_VALUE;
		float lastPassSolveDistance = Float.MAX_VALUE;
		
		// Allow up to our iteration limit attempts at solving the chain
		float solveDistance;
		for (int loop = 0; loop < mMaxIterationAttempts; ++loop)
		{	
			// Solve the chain for this target
			solveDistance = solveIK(newTarget);
			
			// Did we solve it for distance? If so, update our best distance and best solution, and also
			// update our last pass solve distance. Note: We will ALWAYS beat our last solve distance on the first run. 
			if (solveDistance < bestSolveDistance)
			{	
				bestSolveDistance = solveDistance;
				bestSolution = this.cloneChainVector();
				
				// Did we solve for distance? Great! Break out of the loop.
				if (solveDistance <= mSolveDistanceThreshold) { 
				  break; 
				}
			}
			else // Did not solve to our satisfaction? Okay...
			{
				// Did we grind to a halt? If so then it's time to break out of the loop.
				if (Math.abs(solveDistance - lastPassSolveDistance) < mMinIterationChange) { 
				  break; 
				}
			}
			
			// Update the last pass solve distance
			lastPassSolveDistance = solveDistance;
		}
		
		// Did we get a solution that's better than the starting solution's to the new target location?
		if (bestSolveDistance < startingDistance)
		{
			// If so, set the newly found solve distance and solution as the best found.
			mCurrentSolveDistance = bestSolveDistance;
			mChain                = bestSolution;
		}
		else // Did we make things worse? Then we keep our starting distance and solution!
		{
			mCurrentSolveDistance = startingDistance;
			mChain                = startingSolution; 
		}				
		
		// Update our last base and target locations so we know whether we need to solve for this start/end configuration next time
		mLastBaseLocation.set(mBaseLocation);
		mLastTargetLocation.set(newTarget);
		
		// Finally, return the solve distance we ended up with
		return mCurrentSolveDistance;
	}

[joediscar]

I must be doing something wrong. I replaced the FabrikChain2D.solveForTarget(Vec2f) method with the one you provided, but I don't see any change in behavior. With the constraints from the original post, if I click to the left of the line, it still gives a non-solution.

[jmsjr]

Do a git pull instead, mvn package, try again

[jmsjr]

..andmake sure git status shows you have no modifications