Movimentum - Not yet: We need "all the constraints for each frame"

I was to rash. We are not yet at the rim.

The constraint solver will have to solve the equations for a single frame - but I still have to implement the logic that selects which constraints are valid for each frame.

To this end, I want to compute a list of frames, where each frame contains all the constraints valid at its time. The frames are then, so-to-speak, "unsolved frames" - we know the constraints that place the things in each frame, but we have not yet computed explicit coordinates for the anchors of each object.

Here is a rough outline of the algorithm:

  Step currentstep = first step;
  List activeConstraints = constraints of current step;

  // time is incremented in, say, 0.1 second intervals.
  for (time = 0; t < end; time += frame_delta_t) {
    if (t > currentstep.AbsoluteTime) {
      // The time flow jumped into the next step!
      currentstep = next step;
      recompute activeConstraints;
    }
    frameList.Add(new Frame(t, activeConstraints);
  }

Obviously, such an algorithm needs enough testing. For which cases do we have to look out? If you think about it, you see that we have two interlocked sequences of instants:

• The sequence of frame instants
• The sequence of step instants

And there can be

• "n" frame instants between any two step instants 
• "n" step instants between any two frame instants

Of course, in practice, only the former will happen: We will have many frames, but only comparatively few steps. This means that typically, there will be many frames between two step instants.
However, our algorithm should also work correctly for the latter case where there is more than one step between two frames. This could e.g. come in handy if you want to create a sequence of slides that show the mechanism at intervals of two or even 10 seconds.
The standard practice for "testing an n" is to select tests with n=0, n=1, and n>1. In our case, we therefore need test cases for

• zero frames between two steps
• one frame between two steps
• two (or more) frames between two steps

and

• zero steps between two frames
• one step between two frames
• two or more steps between two frames

Moreover, we also need cases where a step instant falls exactly on a frame instant. Of course, we also need boundary tests for no steps and one step - but we'll do that after the algorithm works.
Here is my first test input - the comments indicate the frames we want to appear. For each frame,

• T is the absolute time;
• t is the relative time inside the step;
• iv is the length of the step;
• a, b, etc. are the constraints that should hold in this step.

       const string s = @"
       .config(1);

       @10.0     a = 1;
       // Frame at 10: T = 10, t = 0, iv = 1; a
       @11.0     b = 1;
       // Frame at 11: T = 11, t = 0, iv = 1.3;  a, b
       // Frame at 12: T = 12, t = 1, iv = 1.3;  a, b
       @12.3     c = 1;
       @12.5     d = 1;
       @12.7     e = 1;
       // Frame at 13: T = 13, t = 0.3, iv = 0.8;  a, b, c, d, e
       @13.5     f = 1;
       // Frame at 14: T = 14, t = 0.5, iv = 2;  a, b, c, d, e, f
       // Frame at 15: T = 15, t = 1.5, iv = 2;  a, b, c, d, e, f
       @15.5     g = 1;
       @16.0     h = 1;
       // Frame at 16: T = 16, t = 0, iv = 0;  a, b, c, d, e, f, g, h
       ";

We must also assert that the frames are the correct ones. A helper method comes in handy:

    Assert.AreEqual(7, frames.Length);
    AssertFrame(frames[0], 10, 0, 1, "a");
    AssertFrame(frames[1], 11, 0, 1.3, "a", "b");
    AssertFrame(frames[2], 12, 1, 1.3, "a", "b");
    AssertFrame(frames[3], 13, 0.3, 0.8, "a", "b", "c", "d", "e");
    AssertFrame(frames[4], 14, 0.5, 2, "a", "b", "c", "d", "e", "f");
    AssertFrame(frames[5], 15, 1.5, 2, "a", "b", "c", "d", "e", "f");
    AssertFrame(frames[6], 16, 0, 0, "a","b","c","d","e","f","g","h");

where AssertFrame checks the three time values and constraint existence:

    private void AssertFrame(Frame f, double absoluteTime, double t,
                           double iv, params string[] constraintChecks) {
        Assert.AreEqual(absoluteTime, f.AbsoluteTime, 1e-9);
        Assert.AreEqual(t, f.T, 1e-9);
        Assert.AreEqual(iv, f.IV, 1e-9);
        {
            // Check the number of constraints
            int checkSum = constraintChecks.Count();
            Assert.AreEqual(checkSum, f.Constraints.Count());
        }
        {
            foreach (var checkKey in constraintChecks) {
                Assert.IsTrue(f.Constraints.Any(c => c.Key == checkKey));
            }
        }
    }

Writing the algorithm in C# and running the test reveals one conceptual error (that is obvious if you think about it): The if-statement in the pseudo-code above needs to be replaced with a while statement - after all, there can be more steps between two frames. Therefore, we have to deal with all of these steps before emitting the next frame!

Of course, I had a handful of other errors in the code until I got these enumerators right - the test case above helped me to eradicate them one by one.

The complete algorithm is not that long - maybe 25 statements -, but it deserves a few comments:

    public IEnumerable<Frame> CreateFrames() {
        var result = new List<Frame>();
        IEnumerator<Step> stepEnumerator = _steps.GetEnumerator();

        if (stepEnumerator.MoveNext()) {
            var activeConstraints =
                     new Dictionary<string, List<Constraint>>();

            Step currentStep = stepEnumerator.Current;
            Step nextStep = UpdateActiveConstraintsAndGetNextStep
                           (currentStep, activeConstraints, stepEnumerator);

            // We do not want t to miss a step due to rounding, hence
            // we "push each frame a little bit too far" (< a nanosec ...).
            double deltaT = 1.0 / _config.FramesPerTimeunit + 1e-10;

            int seqNo = 1;
            for (var t = currentStep.Time; nextStep != null; t += deltaT) {

                while (nextStep != null && t >= nextStep.Time) {
                    currentStep = nextStep;
                    nextStep = UpdateActiveConstraintsAndGetNextStep
                           (currentStep, activeConstraints, stepEnumerator);
                }

                result.Add(new Frame(
                    absoluteTime: t,
                    relativeTime: t - currentStep.Time,

                    // In last step - when nextStep is null -, we use
                    // currentStep instead of nextStep -> iv is set to 0.
                    iv: (nextStep ?? currentStep).Time - currentStep.Time,

                    // ToArray() necessary to COPY result into Frame.
                    // Otherwise, the iterator will run on the constraints
                    // of the LAST frame when it is executed at some time.
                    constraints: activeConstraints.Values
                                    .SelectMany(c => c)
                                    .ToArray(),
                    sequenceNo: seqNo++)
                );
            }
        }
        return result;
    }

    /// <summary>
    /// Concept: If there are constraints with key K in this step, we
    /// remove ALL earlier constraints with that key from the active
    /// constraints; and afterwards add all the constraints with this
    /// key from the step.
    /// </summary>
    /// <returns>next step; or null if there is none.</returns>
    private Step UpdateActiveConstraintsAndGetNextStep(Step step,
            Dictionary<string, List<Constraint>> activeConstraints,
            IEnumerator<Step> stepEnumerator) {

        foreach (var c in step.Constraints) {
            // For more than one constraint with same key, the following
            // will init c.Key to the empty list more than once. So what.
            activeConstraints[c.Key] = new List<Constraint>();
        }
        foreach (var c in step.Constraints) {
            activeConstraints[c.Key].Add(c);
        }
        return stepEnumerator.MoveNext() ? stepEnumerator.Current : null;
    }

A second test has to show that the key handling of the constraints is done correctly - i.e., that all constraints with some key are removed if there is one new constraint in the current step with that key; and that all the new constraints are then added. Moreover, tests for no step and a single step are necessary (although such scripts should not occur in real life). I do not show these tests here - they are in the code I'll push to github today.