hexahedria

Daniel Johnson's personal fragment of the web

Whiteboard Drawing Bot – Part 3: Editor

After completing the basic design and software for the whiteboard drawing bot, I decided to make an interactive simulator and shape editor to allow people to generate their own commands. I thought it would be cool to share it as well, in case other people wanted to play with the stroking/filling algorithms or use it to run their own drawing robots or do something else with it entirely.

For the simulator, I wrote a parser to parse the command sequence, and then animated it drawing the command out onto the screen. The parser is written with PEG.js, which I'll be discussing a bit later. The parameters for the generation and rendering are controlled using DAT.gui, and the drawing itself is done using two layered canvases: the bottom one to hold the actual drawing that persists from frame to frame, and the top one to render the arms, which are cleared and redrawn each frame. I separated them because I did not want to have to re-render the entire drawing each time the simulator drew anything new.

Below the simulation, there is a CodeMirror instance running without a parsing mode and without syntax highlighting. I use it for its handy auto-indenting and the ability to mark regions with CSS classes, which I use to point out user syntax errors in my custom-defined PEG.js grammar.

Parsing Exression Grammars and PEG.js

PEG.js is a remarkable tool that allows you to easily compile a parser for a language. Definitions look a bit like this:

start
  = cmdseq

cmdseq
  = left:cmd right:cmdseq { return [left].concat(right); }
  / left:cmd { return [left]; }

cmd "command"
  = "M" left:integer "," right:integer {return {action:"move", a:left, b:right}; }
  / "Pd" {return {action:"pen", pos:"down"}; }
  / "Pu" {return {action:"pen", pos:"up"}; }
  / "Pr" {return {action:"pen", pos:"retract"}; }
  / "A" path:advances {return {action:"advance", path:path}; }
  / "Sa" sign:sign length:integer {return {action:"sweep", dir:"a", sign:sign, len:length}; }
  / "Sb" sign:sign length:integer {return {action:"sweep", dir:"b", sign:sign, len:length}; }

sign "sign"
  = "+" { return 1; }
  / "0" { return 0; }
  / "-" { return -1; }

advances
  = left:advance right:advances {return [left].concat(right); }
  / left:advance {return [left]; }

advance
  = a:sign b:sign { return [a,b];}

integer "integer"
  = digits:[0-9]+ { return parseInt(digits.join(""), 10); }

This is the grammar for the simulator. It reads the command string as a sequence of commands, and recursively builds up an array of objects that can be iterated later. The result of a sub-expression is passed back up to the parent expression, where it can be further modified and combined with other results.

Quick guide to reading it: = defines a command, / means "or", and anything in curly brackets is executed as Javascript when its expression matches. Space-separated expressions must appear consecutively, and colons allow you to specify variable names that are bound to the results of the subrule (a:sign b:sign means "two signs right next to each other, let a equal the result of the first and b equal the result of the second")

That parser can take something like PuM6,22PdA0-+-0-0-+-0-+------00+-+-+0+-+-++++++++0Pu and turn it into this:

[
    {"action":"pen","pos":"up"},
    {"action":"move","a":6,"b":22},
    {"action":"pen","pos":"down"},
    {"action":"advance","path":
        [[0,-1],[1,-1],[0,-1],[0,-1],[1,-1],[0,-1],[1,-1],[-1,-1],[-1,-1],[-1,0],[0,1],[-1,1],[-1,1],[0,1],[-1,1],[-1,1],[1,1],[1,1],[1,1],[1,0]]
    }
]

I also wrote a more complex parser for my shape language, which can be used to generate shapes to input into the algorithm:

{
    var SG = options.ShapeGen;
    var GEO = options.Geometry;
    var FONTS = options.fonts;
}

start
    =  s* items:items s* {return items;}

items
    = left:item s* right:items { return SG.multiple(left,right); }
    / item

item
    = unit / grouping

unit
    = 'rect[' s*  x:number s* ',' s* y:number s* ',' s* w:number s* ',' s* h:number s* ']' { return SG.rect(x,y,w,h); }
    / 'circle[' s* x:number s* ',' s* y:number s* ',' s* r:number s* ']' { return SG.circle({x:x,y:y},r); }
    / 'line[' s* x1:number s* ',' s* y1:number s* ',' s* x2:number s* ',' s* y2:number s* ']' { return SG.line({x:x1,y:y1},{x:x2,y:y2}); }
    / 'curve[' s* x1:number s* ',' s* y1:number s* ',' s* x2:number s* ',' s* y2:number s* ',' s* x3:number s* ',' s* y3:number s* ']' { return SG.bezier([{x:x1,y:y1},{x:x2,y:y2},{x:x3,y:y3}]); }
    / 'curve[' s* x1:number s* ',' s* y1:number s* ',' s* x2:number s* ',' s* y2:number s* ',' s* x3:number s* ',' s* y3:number s* ',' s* x4:number s* ',' s* y4:number s* ']' { return SG.bezier([{x:x1,y:y1},{x:x2,y:y2},{x:x3,y:y3},{x:x4,y:y4}]); }
    / 'path[' s* path:path s* ']' s* { return SG.polyshape(path); }
    / 'text[' s* str:string s* ',' s* x:number s* ',' s* y:number s* ',' s* fs:number s* ',' s* font:string s* ']' { return SG.textGlyphObjects(str,FONTS[font],{x:x,y:y},fs); }

grouping
    = 'translate[' s* dx:number s* ',' s* dy:number s* ']{' s* contents:items s* '}' { return SG.translate(contents,dx,dy); }
    / 'rotate[' s* angle:number s* ']{' s* contents:items s* '}' { return SG.rotate(contents,angle); }
    / 'rotate[' s* angle:number s* ',' s* x:number s* ',' s* y:number s* ']{' s* contents:items s* '}' { return SG.rotate(contents,angle,{x:x,y:y}); }
    / 'scale[' s* factor:number s* ']{' s* contents:items s* '}' { return SG.scale(contents,factor); }
    / 'complex{' s* contents:items s* '}' { return SG.combineComplex(contents); }
    / 'reverse{' s* contents:items s* '}' { return SG.reverse(contents); }
    / '~' obj:item { return SG.reverse(obj); }

path
    = pt:pathtail {return [pt.first].concat(pt.rest)}

pathtail
    = l:point s* ',' s* next:pathtail { return {first:l, rest:[next.first].concat(next.rest)}; }
    / l:point s* ',' s* c:offcurve s* ',' s* next:pathtail { return {first:l, rest:[GEO.quadraticToCubic([l,c,next.first]).slice(1,4)].concat(next.rest)}; }
    / l:point s* ',' s* c1:offcurve s* ',' s* c2:offcurve s* ',' s* next:pathtail { return {first:l, rest:[[c1,c2,next.first]].concat(next.rest)}; }
    / l:point { return {first:l, rest:[]}; }

point
    = '(' s* x:number s* ',' s* y:number s* ')' { return {x:x,y:y}; }
offcurve
    = '<' s* x:number s* ',' s* y:number s* '>' { return {x:x,y:y}; }

string 'a string'
    = '"' 
        strchars:(    ('\\' '\\' {return '\\';}) 
                    / ('\\' '"' {return '"';}) 
                    / (!'"' c:.  {return c;}) 
        )* '"' { return strchars.join(''); }

number 'a number'
    = digits:[0-9.]+ {return parseFloat(digits.join(''));}
    / '-' digits:[0-9.]+ {return -parseFloat(digits.join(''));}

s 'a whitespace character' = [ \f\n\r\t\v​\u00a0\u1680​\u180e\u2000​\u2001\u2002​\u2003\u2004​ \u2005\u2006​\u2007\u2008​\u2009\u200a​\u2028\u2029​​\u202f\u205f​\u3000]

This one is a bit more complex; I had to tweak it quite a bit to get it to do what I want. I won't go over all the details, but basically it breaks down the string into either unit commands, which generate shapes, or groupings, which contain shapes and apply transformations to them. All the s*s allow users to input whitespace between commands.

One part of the shape grammar parser took a lot of design: the path parser. I wanted users to be able to insert control points into their paths just by encasing them with arrow brackets (<5,49>, for example). Internally, the shape generator starts with the first point and then stores lines as endpoints and bezier curves as two control points as an endpoint. In each case, the curve is built using the last point of the previous path component as the starting point. In code, this is straightforward: just keep a reference to the last point. In a parsing expression grammar, this is much more difficult.

Of course, with lines and cubic curves, you don't need the starting point to translate into the right kind of path. But with quadratic curves, you need to know the starting point in order to transform it into a cubic, and that translation has to happen in the grammar.

Parsing expression grammars essentially build lists backwards: you can have a recursive reference at the end of a definition but not at the beginning, and recursive children are evaluated first. Thus, there is no way to pass the last point forward to the next path component. To get around this problem, I instead pass the previous endpoint point backward to the parent component, in a special wrapper object that I discard once the path is built. This is why there is the strange line l:point { return {first:l, rest:[]}; }: once the parser gets to the end of the path, it simply passes this last point up to the previous path component, which passes the previous point to its parent, and so on and so forth. Thus, in order to transform quadratics into cubics, I pass information in the opposite direction as one would expect.

The second parsing grammar uses the ShapeGen object to create an actual path object that can be used immediately. Thus, it transforms something like this:

complex{
    rect[0,100,100,100]
    rotate[45,50,150]{ 
        ~rect[20,120,60,60]
    }
}

into something like this:

[[
    [ {"x":0,"y":100},{"x":0,"y":200},{"x":100,"y":200},{"x":100,"y":100},{"x":0,"y":100} ],
    [ {"x":50.000000000000014,"y":107.57359312880715},{"x":92.42640687119285,"y":150},{"x":50,"y":192.42640687119285},{"x":7.573593128807161,"y":150},{"x":50.000000000000014,"y":107.57359312880715} ]
]]

Pretty cool, in my opinion. You can read all about PEG.js grammars here.

If you want to try out the interactive simulator and editor, I've put it up here on the website. I've also put the code on GitHub if you are curious about the implementation.

If you haven't already, you might want to check out parts one and two.

© . All rights reserved. | Top