Thursday, April 26, 2012

Movimentum - How to test an animation?

Hopefully, we'll create a first, simple animation in a short time. How are we going to check whether the output is correct? Of course, there is always the programmer's answer: Unit testing. However, with graphical objects, our eye (together with the brain) is one of the best gadgets to check for errors, as there are:
  • A "rigid" body that suddenly gets deformed;
  • A moving body that does not move;
  • A body whose image is a mirror of the intended one;
  • ...and many others.
What I want to say is: We need graphical output! We ... need ... movies ...!

This forces me to think about the design of the data flow from the frames back to the things so that we can draw them at the correct place. I scribbled a little bit on the margin of our daily newspaper and came up with the following trivial design for the main loop:

    IEnumerable<Frame> frames = script.CreateFrames();

    foreach (var f in frames) {
        ... Create drawing pane ...

        // Compute locations for each anchor of each thing.
        IDictionary<string,
                    IDictionary<string, ConstVector>>
            anchorLocations = f.SolveConstraints();
         
        foreach (var th in script.Things) {
            th.Draw(drawingPane, anchorLocations[th.Name]);
        }

        ... Save drawing pane to a new file ...
    }

Filling out the missing parts is easy, e.g.:

    var bitmap = new Bitmap(script.Config.Width, script.Config.Height);
    Graphics drawingPane = Graphics.FromImage(bitmap);
    ...
    bitmap.Save(
        string.Format("{0}{1:000000}.jpg", prefix, f.FrameNo),
        ImageFormat.Jpeg);

This requires adding two new parameters to the .config element to define the width and height of the drawing pane and a suitable update of the grammar.

Additionally, I want to test the solver with simple things. For this, I add a simple "bar" thing, which consists of a list of anchor points connected by lines.

    thingdefinition returns [Thing result]
      : IDENT
        ':'          {{ var defs = new List<ConstAnchor>(); }}
        ( FILENAME
          anchordefinitions[defs]
                     { result = new ImageThing($IDENT.Text,
                                ImageFromFile($FILENAME.Text),
                                defs);
                     }
        | BAR
          anchordefinitions[defs]
                     { result = new BarThing($IDENT.Text, defs); }
        )

        ';'
      ;

As you might notice, I have replaced the dictionary for the anchors with a list of the new class ConstAnchor. The reason is that I want the code to remember the order of anchors from the input, so that it will draw the lines always in the same order (in Java, I'd just have to replace Hashtable with LinkedHashtable. In .Net, this is not - yet? - possible).

The Bar thing must be able to draw itself (do you remember your first book on object orientation where they told you that in these modern times, objects are drawing themselves? Now you finally know why you learned this!):

    public class BarThing : Thing {
        public BarThing(string name, IEnumerable<ConstAnchor> anchors)
            : base(name, anchors) {
        }

        public override void Draw(Graphics drawingPane,
                IDictionary<string, ConstVector> anchorLocations) {
            float height = drawingPane.VisibleClipBounds.Height;
            Point[] points = Anchors
                .Select(a => new Point(
                    (int)Math.Round(anchorLocations[a.Name].X),
                    (int)(height - Math.Round(anchorLocations[a.Name].Y))))
                .ToArray();
            drawingPane.DrawLines(new Pen(Color.Orange, 3), points);
        }
    }

Now I can create a small crowbar or hockey stick:

    .config (20, 200, 200);
    B : .bar P = [0,0] Q = [5,5] R = [5,30];

I'd also like to move it so that I can test the three lines of graphics programming from above. For this, we need a few constraints, e.g. to move it diagonally:

    @0  B.P = [60 + .t, 60 + .t];
        B.Q = [65 + .t, 65 + .t];
        B.R = [65 + .t, 90 + .t];
    @10

Creating the frames requires a minimal ability of "constraint solving". I implement this ability with a rather hardwired assignment of values - which still requires an astonishing number of lines:

    public IDictionary<string, IDictionary<string, ConstVector>> SolveConstraints() {
        var anchorLocations =
                        new Dictionary<string, IDictionary<string, ConstVector>>();
        #region ------- TEMPORARY CODE FOR TRYING OUT THE DRAWING MACHINE!! -----
        foreach (var c in _constraints) {
            var constraint = c as VectorEqualityConstraint;
            if (constraint != null) {
                Anchor anchor = constraint.Anchor;
                Vector vector = (Vector)constraint.Rhs;
                double x = Get(vector.X as BinaryScalarExpr);
                double y = Get(vector.Y as BinaryScalarExpr);
                var resultVector = new ConstVector(x, y);
                IDictionary<string, ConstVector> anchorLocationsForThing;
                if (!anchorLocations.TryGetValue(anchor.Thing,
                                                    out anchorLocationsForThing)) {
                    anchorLocationsForThing = new Dictionary<string, ConstVector>();
                    anchorLocations.Add(anchor.Thing, anchorLocationsForThing);
                }
                anchorLocationsForThing.Add(anchor.Name, resultVector);
            } else {
                // We ignore the rigid body and 2d constraints for our testing.
            }
        }
        #endregion ---- TEMPORARY CODE FOR TRYING OUT THE DRAWING MACHINE!! --------
        return anchorLocations;
    }

    #region ----------- TEMPORARY CODE FOR TRYING OUT THE DRAWING MACHINE!! --------
    private double Get(BinaryScalarExpr expr) {
        // Expression MUST be (c + .t), with constant c.
        var lhs = (Constant)expr.Lhs;
        return lhs.Value + _relativeTime;
    }
    #endregion -------- TEMPORARY CODE FOR TRYING OUT THE DRAWING MACHINE!! --------

A little script helps us to run the chain of programs to create the animation. Test.mvm contains the Movimentum script, ffmpeg can be found here:

    bin\debug\Movimentum.exe test.mvm f_
    \ffmpeg\bin\ffmpeg -y -f image2 -i f_%%06d.jpg test.mpg
    test.mpg

And here it is - my first Movimentum animation!



Of course, the important part of the animation computation is pure fake: The coordinates of the anchors are directly assigned, and the rigid body constraints as well as the 2d constraints are completely ignored by this "solver."

But - we are finally at the rim of the canyon.

------------------------------------------------------------------------------------

P.S. For those of who who look closely: I have changed the names of the expression classes because they were very ad-hoc. They are still somewhat strange, but at least each class ending in "ScalarExpr" is actually a ScalarExpr, and each class ending in "VectorExpr" is now a VectorExpr. Likewise, "Unary" and "Binary" are applied consistently.

P.P.S. I am quite unsatisfied with the expression grammar because it is almost impossible to add the five multiplication operators that should be there:
  • Scalar multiplication of scalars;
  • Scalar multiplication of vectors ("inner product");
  • Left and right multiplication of scalar and vector;
  • Outer product of 3d vectors.
I guess that I should have thought about an eighth option in that posting with the severe grammar problem: using semantic predicates. I'll deal with these problems after the canyon ... eh, the constraint solver. So those of you who are interested in language design, stay tuned.

P.P.P.S. There's more to do in the grammar - for example, right now you cannot call an anchor "link" (try it). "pink", however, works perfectly. Not what one would expect.

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.

Tuesday, April 24, 2012

Movimentum - Walking over the canyon

Did you see this guy walking over the canyon in China two days ago? I mean - he must be totally crazy: No safety net, no way to succeed except ... to succeed.

Like Movimentum. If the constraint solver does not work, everything up to now is moot. Well - it doesn't kill me, but only the project (which is a small hobby project, to be precise). Still, walking up to this point was like the advance to the rim of the canyon.

Now, we'll start to cross the canyon.

We'll see whether we'll cross it alive.

Movimentum - Better rigid body constraints; and ToString()

Rigid body constraints rewritten


Ok - I botched it. Not really that obviously, but still, the code for the rigid body constraints was not thought out enough. The issue there is the lifetime of things: When do things start to appear in the animation?

My implicit assumption was that the first time a thing (i.e., a thing's anchor) is mentioned, it will be rendered into the animation. But then, I cannot hook all rigid body constraints to the first step - because then, all things will try to appear in the first step. However, at this point the constraints explicitly written in the script are still missing! - so the constraint solver will not be able to compute a location for the things, and hence it will complain.

I therefore rewrote the rigid body constraint code so that it now creates these constraints at the first step where a thing's anchor appears on the left side of a constraint. In the course of this, I also added code to create the 2d constraints (and I found out that the MovimentumParser.ConstAdd() method did not behave well with 2d anchors - it needed another if. The code looks now a little "over-if-ed", but for this helper method, so be it.)

Altogether, the code for these constraints is about 110 lines.

 

Debugging Output = ToString()


Moreover, I now added (hopefully) sensible code for ToString() of constraints and expressions so that they are more or less easily readable in the debugger. I will not explain that code too deeply - it is only for debugging -, but only give a short overview. If you are interested, please look into the github repository.

The main parts of the ToString() code are:
  • Each expression gets a ToString method with an additional parameter for controlling the parentheses. The code of this methods is one of the following if the expresion is a binary or a unary expression:
    protected internal override string ToString(AbstractOperator parentOp) {
        return parentOp.Wrap(_lhs, _operator, _rhs);
    }
    protected internal override string ToString(AbstractOperator parentOp) {
        return parentOp.Wrap(_operator, _inner);
    }
  • This code is used in a ToString() method for all expressions: I wasted the precious resource "base class" for this feature - both ScalarExpr and VectorExpr now derive from a class Expr which has the ToString() method in it:
public abstract class Expr {
    public override string ToString() {
        return ToString(AbstractOperator.IGNORE_OP);
    }

    protected internal abstract string ToString(AbstractOperator parentOp);
}
  • Finally, the following code inside AbstractOperator handles the parenthesizing by a mutually recursive call to the ToString(AbstractOperator parentOp) method from the first item above:
        public string Wrap(Expr lhs, AbstractOperator op, Expr rhs) {
            string s = lhs.ToString(op) + op + rhs.ToString(op);
            return op.Precedence < Precedence ? "(" + s + ")" : s;
        }

        public string Wrap(AbstractOperator op, Expr e) {
            string s = e.ToString(op) + op;
            return op.Precedence < Precedence ? "(" + s + ")" : s;
        }

So that the precedence check and output works, operators need to be defined with the correct precedence and output string. Here is an example for the binay scalar operators - the precedences are copied over from the grammar (if the operator occurs in simpleexpr2, precedence is 2; if it occurs in simpleexpr3, then 3, etc.):

    public class BinaryScalarOperator : AbstractOperator {
        private BinaryScalarOperator(int precedence, string asString) : base(precedence, asString) { }
        public static BinaryScalarOperator PLUS = new BinaryScalarOperator(1, " + ");
        public static BinaryScalarOperator MINUS = new BinaryScalarOperator(1, " - ");
        public static BinaryScalarOperator TIMES = new BinaryScalarOperator(2, " * ");
        public static BinaryScalarOperator DIVIDE = new BinaryScalarOperator(2, " / ");
    }

For the moment, this works as expected. And as it is only debugging output, I confess that I skipped the unit tests for this.

Movimentum - Implementation of rigid body constraints, constraint lifetime, and 3-d troubles

Implementation of rigid body constraints


I have now implemented the creation of the rigid body constraints. This required a change to the grammar and the model: I could not express the squares succinctly, so I added a "squared" (and a "cubed"; and a "square root") expression. Here is the code for the new constraints - it's longer than I would have expected:

    public partial class Script {
        public void AddRigidBodyConstraints() {
            if (Steps.Any()) {
                foreach (var th in _things) {
                    string[] anchorNames = th.Anchors.Keys.ToArray();
                    for (int i = 0; i < anchorNames.Length; i++) {
                        for (int j = i + 1; j < anchorNames.Length; j++) {
                            string anchorName1 = anchorNames[i];
                            string anchorName2 = anchorNames[j];
                            AddRigidBodyConstraint(th.Name,
                                anchorName1, anchorName2,
                                th.Anchors[anchorName1], th.Anchors[anchorName2]);
                        }
                    }
                }
            }
        }

        private void AddRigidBodyConstraint(string thing,
                string anchorName1, string anchorName2,
                ConstVector cv1, ConstVector cv2) {
            string auxVar = thing + "_" + anchorName1 + "_" + anchorName2;
            ScalarEqualityConstraint constraint1, constraint2;
            {
                var anchor1 = new Anchor(thing, anchorName1);
                var anchor2 = new Anchor(thing, anchorName2);
                UnaryScalarExpr xSquared = SquareCoord(UnaryScalarVectorOperator.X, anchor1, anchor2);
                UnaryScalarExpr ySquared = SquareCoord(UnaryScalarVectorOperator.Y, anchor1, anchor2);
                UnaryScalarExpr zSquared = SquareCoord(UnaryScalarVectorOperator.Z, anchor1, anchor2);
                BinaryScalarExpr squaredSum =
                    new BinaryScalarExpr(xSquared,
                        BinaryScalarOperator.PLUS,
                        new BinaryScalarExpr(ySquared,
                            BinaryScalarOperator.PLUS,
                            zSquared
                        )
                    );
                constraint1 = new ScalarEqualityConstraint(auxVar, squaredSum);
            }
            {
                double squaredDistance = Square(cv1.X - cv2.X)
                                       + Square(cv1.Y - cv2.Y)
                                       + Square(cv1.Z - cv2.Z);
                constraint2 = new ScalarEqualityConstraint(auxVar, new Constant(squaredDistance));
            }
            // AddRigidBodyConstraint is only called when Steps.Any() is true - therefore Steps.First() is safe.
            Steps.First().AddConstraint(constraint1);
            Steps.First().AddConstraint(constraint2);
        }

        private double Square(double v) {
            return v * v;
        }

        private static UnaryScalarExpr SquareCoord(UnaryScalarVectorOperator coordOp,
                                                   Anchor anchor1, Anchor anchor2) {
            return new UnaryScalarExpr(UnaryScalarOperator.SQUARED,
                new BinaryScalarExpr(
                    new UnaryScalarVectorExpr(anchor1, coordOp),
                    BinaryScalarOperator.MINUS,
                    new UnaryScalarVectorExpr(anchor2, coordOp))
                );
        }
    }

But - don't I add too many operators ad hoc and just so, like the SQUARED above?

Maybe I should stress the following at this point: At some point, all these mathematical operators will go into that magic constraint solver, and then "all hell will break loose," i.e., I will find out that constraint solving is hard, hard, hard. Therefore, I'll then revise the grammar by excluding operators - so all expression types now in the grammar are more a sort of suggestions. We will see which of them remain - and which are definitely necessary - in the end.

Still, I could not formulate the rigid body constraints directly as in the previous posting. The reason is that the left side of a constraint can only be a variable (which is also used as a key for the lifetime management of the constraint). So I had to formulate each constraints as a constraint pair like that:

   auxVar = (P.x - Q.x)² + (P.z - Q.z)² + (P.z - Q.z)²
   auxVar = constant
  
where the constant is the square of the length. This creates two more issues:

Constraint lifetime


The first issue is that we can have more than one constraint with the same key at the same time (here, "auxVar" is the key of two constraints which should hold simultaneously). Thus, the lifetime management of contraints will probably have to be: If, in a step, new constraints (plural!) are defined for some key, all current constraints with that key are removed; and then the new constraints are enacted.

3-d swiveling


The other issue is that the z coordinate I have added so happily in my 3d posting creates a big headache: Things can now "swing into the third dimension" - and there is no constraint preventing them to do this! What to do? Again, there are at least the following possibilities:
  • Explicitly adding constraints to fix all anchor z-s at zero.
  • Some implicit mechanism. As I allow a two-dimensional vector notation [a,b], the following might help: If an anchor is created with only two coordinates specified, a constraint fixing the z coordinate at 0 is created automatically.
I'll implement the code for the latter.

Still, an item with only two anchors could swivel around the axis defined by them. It seems that placing the images in 3-d will require additional rules - but right now, I separate the constraint solving from the final image creation: The former should create unique solutions also in 3-d, the latter is right now only defined for 2-d machines. This conforms to the item
  • "2D only. Maybe we have 3D ideas later - not now (however, I think I'll give them vectors 3 coordinates from the start)."
in my item list.

Monday, April 23, 2012

Movimentum is on github!

My colleague Thomas (thoemmi) has helped me to put Movimentum on github! It is now available at https://github.com/hmmueller/Movimentum. The support for builds is still rudimentary - e.g., one must run ANTLR manually by calling a Windows BAT file runantlr.bat. I'll leave it at that for the moment ... my focus is on design and continuing the implementation.

Thanks, thoemmi!

Movimentum - Rigid body constraints

We are quickly closing in on the central algorithm of Movimentum: The constraint solver. But before I try to fathom the depths of that topic, there is still something missing: Constraints that capture the rigidity of our things. To see why we need them explicitly, let's write a script for a simple horizontal bar:

    .config(1);

    Bar : 'bar.gif' P = [10,10] Q = [50,10];

    // We place the bar somewhere
    @0.0  Bar.P = [10,10]; Bar.Q = Bar.P + [_,0];

This step can be rewritten into the following scalar equations:

   barPx = 10; barPy = 10; barQx = barPx + d; barQy = barPy;

barQy can readily be computed, but not barQx! Some constraint is obviously missing. This also follows from the fact that we have four equations, but five variables: The four bar.. variables and the "slack variable" d.

Let's now rotate the bar by 45°:

    @1.0 Bar.Q = [e,e];

According to the "key convention", the constraint Bar.P = [10,10] remains in force, but the Bar.Q constraint from @0.0 is replaced. Therefore, we end up with the following four equations:

   barPx = 10; barPy = 10; barQx = e; barQy = e;

Again, we cannot compute some values - in this case, both for barQx and barQy. Again, we have five variables - the bar..s, and e -, but only four equations.

Let's now add a "length constraint":

   // implicit length constraint
   (Bar.P.x - Bar.Q.x)² + (Bar.P.y - Bar.Q.y)² = 40²

Using this constraint, we get a fifth equation. For the initial placement in step @0.0, we can now solve the equations:
 
   barPx = 10; barPy = 10; barQx = barPx + d; barQy = barPy; 
   (barPx - barQx)² + (barPy - barQy)² = 40²

We substitute barPx and barPy (as they are equal to constants) and barQy and get:

    barQx = 10 + d; (10 - barQx)² + (10 - 10)² = 40²

Dropping  (10-10)² = 0 and substituting barQx gives us

    (10 - 10 - d = 40²

and we arrive at the two solutions d = +40 and d = -40. Backsubstitution will give us the variables for the initial placement of the bar.

But ... there are two possible solutions! What do we do about this? Possibilities:
  • We require an additional explicit constraint, e.g. Bar.Q.x > Bar.P.x.
  • We assume additional implicit constraints - my suggestion: If for two anchors A and B of a thing T, we have A.x > B.x, then we also require T.A.x > T.B.x for the solution.
However, I'm afraid that implicit inequality constraints will either
  • hold too short (i.e., they are also necessary for some movements); or 
  • too long (i.e., they will prevent a single solution at some time); or
  • are not sufficient (e.g., when two solution have equal x, or when multiple quadratic equations yield four or more solutions).
So I will, for the moment, require explicit inequality constraints for unique solutions.

But also for explicit inequality constraints, the lifetime seems to be tricky - the three problems above might also occur with them. So we need a lifetime regime for inequality constraints!

Here is my suggestion: Inequality constraints are marked with the variable on the left side and the inequality operator (maybe <= is unified with <, and >= with >). Using the following "vacuous" constraint, an inequality constraint can be "killed:"

    x > _

(Another possibility would be to have infinite lifetime for inequality constraints, but invoke them only if there are two or more solutions ... but I am afraid that then, it gets even harder to get unique solutions).


Let's also try the solution for the @1.0 step: We have the five equations

   barPx = 10; barPy = 10; barQx = e; barQy = e; 
   (barPx - barQx)² + (barPy - barQy)² = 40²

We substitute all four bar.. variables and get:

   (10 - e)² + (10 - e)² = 40²

This can be solved and yields 10 - e ≈ ±28.28, or e ≈ +38.28 or e ≈ -18.28. From this, we can find the values of the bar.. variables. Again, > constraints are needed to select a unique solution.

The rigid body (length) constraints must of course remain in force for the full script. Therefore, I give them a key that can never be given to another constraint - some internal Guid or the like.

Movimentum - Reminder

Before I forget it (I wouldn't, but it should be in the blog): I'll also need non-rigid things. Springs are certainly important in mechanical machinery, but there are others - look at www.animatedengines.com for ideas.

Movimentum - 3-d or not 3-d

Before I think a little bit about the 3d topic, I confess I have played with the grammar somewhat. I want to introduce vector variables and also use the special variable _ for vectors - but when I added this to vectorexpr5, the grammar got ambiguous. So I simplified (or "simplified"?) the vector constraints in the same way as the scalar ones:

    constraint returns [Constraint result]
      : a=anchor // <----- was v1=vectorexpr up to now!
        '='
        v=vectorexpr
        ';'              { result = ...; }
      | i=IDENT
        '='
        s=scalarexpr
        ';'              { result = ...; }
      ...

This disallows "very implicit constraints" - I'll see when I need them. On the other hand, it introduces a clear key also for each vector constraint, which is necessary for the Idea introduced at the end of this posting.

But now onwards to the 3d question. In the "what I want list" over there, there was also an item
  • 2D only. Maybe we have 3D ideas later - not now (however, I think I'll give them vectors 3 coordinates from the start).
I have dodged this up to now. But among my ideas on what I want to animate, there are at least a few mechanisms that are three-dimensional:
  • The valve gear for the center cylinder of UP's 4-12-2 engines, 
  • or the lever train from the route lever to the locking bar in a German "Einheitsstellwerk".
How would one explain these? My idea would be about as follows: Start with 2d explanations - e.g. the standard Walschaerts gear -, but then "zoom out" to present a view on the 3d mechanism. But .... ahhhh ... that means that not only the mechanism has to be 3d, but also the camera's movement!

And this leads to a solution to a problem that has sat in the back of my mind for all that time: A useful animated explanation at times also needs to zoom into some part of the moving mechanism - and I could not see how I could integrate this zooming with the moving mechanism in the script: How can I "scale part of the mechanism"?? But of course: This scaling is not part of the moving mechanism, but of the camera's moving around - which is a completely separate script, probably even with special operations like "zoom center part (of 'diameter' 15 degrees)" or the like, which do not make sense for the mechanism per se. I'll not delve into this "camera script (language)" for the moment, but it will have to be done ...

Another 3d question: Where do the objects ("things") come from? For 2d things, there are standard formats even I know of (GIF with transparency, for example). But are there standard 3d formats which can readily be loaded and rendered by .Net? I do not know, and for the moment, I'll ignore this topic (I'll ask Dennis when I see him next time :) ). The examples above, at least, can be readily explained with "paper-thick 2d objects," which are projected onto a camera moving in 3d.

And as I do now have a somewhat clear understanding of the very limited 3d capabilities Movimentum should have, I'll upgrade my vectors to 3 coordinates!

Here are the changes to ConstVector - for enhanced usability, I continue to allow two-coordinate vectors:

    constvector returns [ConstVector result]
      :       {{ double x = double.NaN, y = double.NaN, z = 0; }}
        '['
        ('-' c=constscalar  { x = -c; }
        |    c=constscalar  { x = c; }
        )
        ','
        ('-' c=constscalar  { y = -c; }
        |    c=constscalar  { y = c; }
        )
        ( ','
          ('-' c=constscalar  { z = -c; }
          |    c=constscalar  { z = c; }
          )
        )?
 
        ']'                 { result = new ConstVector(x,y,z); }
      ;

    constscalar returns [double result]
      : n=number            { result = n; }
      | c=constvector      
        ( X                 { result = c.X; }
        | Y                 { result = c.Y; }
        | Z                 { result = c.Z; }
        )
      ;

with a simple lexer addition:

    Z :  '.z';

And here is the change to Vector:

    vector returns [Vector result]
      : '['
        s1=scalarexpr
        ','
        s2=scalarexpr
        ( ','
          s3=scalarexpr
        )?

        ']' { result = new Vector(s1, s2, s3 ?? new Constant(0)); }
      ;

Both changes, of course, require corresponding changes in the constructors as well as the Equals() and GetHashcode() methods of the mentioned model classes. After I implemented these changes and upgraded a few test cases (I do not allow default parameters - the model is not an API!), all the tests ran without a hitch!

Sunday, April 22, 2012

Movimentum - Unit testing the parser

The parser (and model builder) is not that complicated - but there is a minimal number of tests that we should provide. First of all, each path in the actions should be tested once - a copy paste error could e.g. produce a wrong operator, or drop a part of an expression. Moreover, a few features warrant special testing. They are:
  1. The hard-wired anchor definition computations.
  2. Image loading.
  3. The time computation for the steps (the two variants of the @ feature).
  4. Producing different variables when using the underscore _.
  5. Correct disambiguation in the rule with backtrack=true.
This takes some work. However, when the grammar is extended (and it will be extended - there are already a few features I'd like to have), these unit tests are necessary as a safety net.

A first test for numbers might look like this:

    [Test]
    public void Test_number() {
        Assert.AreEqual(1.0, GetParser("1").number(), 1e-10);
        Assert.AreEqual(1.0, GetParser("1.").number(), 1e-10);
        Assert.AreEqual(10.0, GetParser("1.E1").number(), 1e-10);
        Assert.AreEqual(0.01, GetParser("1.E-2").number(), 1e-10);
        Assert.AreEqual(10.1, GetParser("1.01E1").number(), 1e-10);
        Assert.AreEqual(0.010001, GetParser("1.0001E-2").number(), 1e-10);
    }

Then, a test might just parse all sorts of scalar expressions:

        [Test]
        public void TestJustParse_scalarexpr() {
            GetParser("a+b").scalarexpr();
            GetParser("a+b*c").scalarexpr();
            ...
        }

However, this test will not work - it throws an exception about an "unexpected EOF". Why? Well, the grammar knows that scalar expressions can never be at the very end of an input file. So, it treats an EOF right after a scalar expression as an error. We can repair this by providing enough following symbols for the LL parser so that it remains happy. In our case, a semicolon suffices, as each constraint - which might have a scalar expressions at the end - is terminated by that symbol. So, the following actually tests parsing of scalar expressions:

        [Test]
        public void TestJustParse_scalarexpr() {
            GetParser("a+b ;").scalarexpr();
            GetParser("a+b*c ;").scalarexpr();
            GetParser("(a-b)*c ;").scalarexpr();
            GetParser("a+b*-c*d ;").scalarexpr();
            GetParser("(a-b*c)/-(-d) ;").scalarexpr();
            GetParser(".i(a+2*b) ;").scalarexpr();
            GetParser("(3+.d(-a-b*2))-d ;").scalarexpr();
            GetParser("-.a([0,1],[1,1]) ;").scalarexpr();
            GetParser("_+_ ;").scalarexpr();
            GetParser("3*.t ;").scalarexpr();
            GetParser("(.iv-.t)/2 ;").scalarexpr();
        }

Next, we have to check that the correct model is returned - and here we get a problem: How do we compare two models? There are two possibilities: We can either compare each property, or we implement an Equals method in each class. As we might want to compare model parts also later (e.g. to find out that a constraint is superfluous; or for constant folding), I opt for the Equals methods. So each expression (at least) now gets three methods - here is an example for class BinaryScalarExpr:

        public bool Equals(BinaryScalarExpr obj) {
            return Equals((object)obj);
        }
        public override bool Equals(object obj) {
            BinaryScalarExpr o = obj as BinaryScalarExpr;
            return o != null
                && o._lhs.Equals(_lhs)
                && o._operator.Equals(_operator)
                && o._rhs.Equals(_rhs);
        }
        public override int GetHashCode() {
            return _lhs.GetHashCode() + (int)_operator + _rhs.GetHashCode();
        }

The tests I write look like this. They are a sort of mixture between single-purpose tests (where you would put only exactly one operator or the like into an expression) and integrating tests - and are quite boring to write ...

    ScalarExpr x = CreateParserForSyntacticTests("a+b*-c/d ;").scalarexpr();
    Assert.AreEqual(
        new BinaryScalarExpr(new ScalarVariable("a"),
            BinaryScalarOperator.PLUS,
            new BinaryScalarExpr(
                new BinaryScalarExpr(new ScalarVariable("b"),
                    BinaryScalarOperator.TIMES,
                    new UnaryScalarExpr(UnaryScalarOperator.MINUS,
                        new ScalarVariable("c")
                    )
                ),
                BinaryScalarOperator.DIVIDE,
                new ScalarVariable("d")
            )
        ), x);

I wrote about 20 of them up to now - that should suffice for my enterprise. If I find errors, I'll add more. Tests for the five specific items mentioned at the beginning are still missing, I confess.

Remark: During testing I found -  I think - some quite serious restrictions in my grammar. For example, I cannot write 2*[0,1] for a multiplication of a scalar and a vector, much less a*[b,c]. I'll leave it at that right now:
  • Either one can work around the restrictions - this is an animation program, not a generic mathematical equation solver;
  • or I introduce the {...} braces for vector expressions (if that helps);
  • or I find some other clever way ...
UPDATE: I have now written some more test cases, especially for 4 of the 5 special issues mentioned at the beginning. Still missing are tests for correct (and failing) image loading - I'll push them to later times.

Movimentum - Building the model cont'd

After the things and their anchors, we build the steps. For the time tracking, we keep a global variable in the parser that is set or incremented, depending on the format of the @ directive:

    time
      : '@' n=number         { _currentTime = n; }
      | '@' '+' n=number     { _currentTime += n; }
      ;
   
I therefore changed the creation of a Step in the script rule to

          ...
          )*        { sts.Add(new Step(_currentTime, cs)); }
          ...

The constraint rule creates on of the three constraint types:

    constraint returns [Constraint result]
      : v1=vectorexpr
        '='
        v2=vectorexpr
        ';'     { result = new VectorEqualityConstraint(v1, v2); }
      | i=IDENT
        '='
        v=scalarexpr
        ';'     { result = new ScalarEqualityConstraint(

                                   $i.Text, v); }
      | i=IDENT {{ ScalarInequalityOperator op = 0; }}
        ( '<'   { op = ScalarInequalityOperator.LE; }
        | '>'   { op = ScalarInequalityOperator.GE; }
        | '<='  { op = ScalarInequalityOperator.LT; }
        | '>='  { op = ScalarInequalityOperator.GT; }
        )
        s=scalarexpr
        ';'     { result = new ScalarInequalityConstraint(

                                   $i.Text, op, s); }
      ;
In a similar way, we build vector expression. Here is the top rule for a vector expression:

    vectorexpr returns [VectorExpr result]
      : v=vectorexpr2        { result = v; }
        (                    {{ BinaryVectorOperator op = 0; }}
          ( '+'              {{ op = BinaryVectorOperator.PLUS; }}
          | '-'              {{ op = BinaryVectorOperator.MINUS; }}
          )
          v=vectorexpr2      { result = new BinaryVectorExpr(
                                                 result, op, v); }
        )*
      ;

All the rest is similar and, overall, simple. The only change I made is to Anchor: Originally, I wanted to pass in a ready-made Thing. But this would require to move the Thing collection somewhere where we can access it - I defer this to some later semantic phase of the interpreter.

The complete grammar file with actions is here.