Movimentum - The solver algorithm finally produces a movie

We still had no solution for the moving hockey stick at the end of the previous posting. Seven dead nodes was all we got.

For some of these nodes, it is correct that they are dead. For example, the first one contains the constraint 0 = –10, which can never be true. Also the next two nodes contain unsatisfiable constraints. However, the fourth dead node contains only the following four constraints, which are mathematically correct:

  ! {AtLeastZeroConstraint}0 <= 25
  ! {AtLeastZeroConstraint}0 <= 0
  ! {AtLeastZeroConstraint}0 <= 900
  ! {AtLeastZeroConstraint}0 <= 625

So, we need more rewrites—this time, for AtLeastZeroConstraints with a constant on the right side. The rewrite is as simple as for the 0=C rule (and now you see how rule actions work for template matching):

    new RuleAction<ScalarConstraintMatcher>("0<=C",
         new AtLeastZeroConstraintTemplate(z).GetMatchDelegate(),
         matcher => matcher != null,
         (currNode, matcher, matchedConstraint) => {
             double value = matcher.Match(z).Value;
             return value.Near(0) | value >= 0
                 ? new SolverNode(currNode.Constraints
                                     .Except(matchedConstraint),
                                  currNode)
                 : null;
         });

As a side note, I have defined an extension method double.Near(double) that allows for small rounding errors. It is defined as follows:

public static class DoubleUtils {
     public static bool Near(this double d1, double d2) {
         return Math.Abs(d1 - d2) < 1e-8;
     }
 }

With this addition, we can run our test again. It takes much longer than before—and this time, it is green! The test directory is finally filled with 200 images, which we can now concatenate to a movie. Here it is—the first one that is actually computed by Movimentum:



After more than 30 postings, Movimentum finally begins to take shape.