手続きと制約を用いた図形記述言語の制作

言語実装 Advent Calendar 2017 17 日目の記事です。

制作中の図形記述言語について紹介をしたいと思います。
処理系の実装は https://github.com/agehama/parserTest2 にとりあえずあります（まだあまり動かない）。

概要・目的

図を手ではなくプログラミングによって描くという動機には主に次の3つが考えられます。

1. 似た図形をいくつも使うのでモジュール化したい
2. 手で描くには難しい(or 面倒くさい)図形を描きたい
3. テキストに埋め込みたい / バージョン管理したい

これを既存の図形記述言語(or ツール)に当てはめると、伝統的な TikZ や Asymptote は主に1や3を目的に、かっこいい絵を作るのに使われる Context Free や Processing は主に2を目的としているように感じられます。今ここに挙げた言語は、全て手続きを記述することにより図形を定義する言語です（Context Free は簡単な図は宣言的に書けますが）。

ここで、1 - 3 それぞれの目的について、制約を用いることで解決されうる問題を考えることができます。

1. 似た図形をいくつも使うのでモジュール化したい

手続きでは明示的にパラメータ化した箇所以外は全て決め打ちになってしまうので、一度作った後に変更を加えるのは容易ではありません。それに対し、制約は逆に制限したい箇所を指定する事が定義となるので後からの変更が利きやすいという利点があります。

2. 手で描くには難しい(or 面倒くさい)図形を描きたい

Generative Art、Procedural Art と呼ばれるようなアルゴリズムで何か面白い絵を作る行為には大体乱数の調整が必要になります。これ系で恐らく最もよく生成されているのが木だと思いますが、リアルな木には「重さのバランスが取れるよう成長する」「光をなるべく多く受けられるよう葉を広げる」といった性質があり、これらを制約の形で記述できればパラメータの調整をせずともかっこいい絵を作れると考えられます。

3. テキストに埋め込みたい / バージョン管理したい

描きたい図が頭の中にある時、わざわざそれを作るアルゴリズムを考えるのが面倒くさいという事は少なくないと思います。多くの場合、図をどう生成するかよりも、図が何であるかを記述する方が簡単であり、制約を使うことでより楽に図をテキストに起こせると考えられます。

以上のように、図をプログラミングによって描く際の手作業をなるべく減らすことがこの言語の主な目的となります。

構文

構文の特に図形部分に関する説明をします(処理系がまだ未完成なので、コード下の図は手で作ったものです)。

図形の定義

図形は次のように { } で囲うようにして定義します。

main = {
    a: triangle
    b: circle
}

---

また、図形の直後に { } を付けることでその中に位置や角度など相対的な座標などを記述できます。

main = {
    a: triangle{angle: 180}
    b: circle{pos.y: 0.8, scale: 0.8}
}

図形に対する制約

図形に対する制約を論理式の形で与えることができます。

制約は図形定義中で sat() を呼び出し、その中に true となるべき論理式を記述することで定義します。
また、free() の中に制約を満たすために変更してもよい変数を指定します。

main = {
    a: triangle
    b: arrow{angle: 90}
    sat(a.top() == b.head())
    free(b.pos)
}

図形に対する手続き

図形定義には手続き式を用いることもできます。

main = {
    shapes: []

    for i in 1:15 do(
        shapes = shapes @ (
            if i % 15 == 0 then triangle{angle: 180}
            else if i % 5 == 0 then square
            else if i % 3 == 0 then triangle
            else circle
        )
    )
}

図形の合成

図形に対して集合演算子（& | \ ^）を用いて図形同士の合成を行うことができます。

main = {
    diamond = square{angle: 45}
    
    shapes: [
        (diamond ^ diamond{pos.x: 0.7})
        (circle & circle{pos.x: 0.7}){pos.y: 1.3}
        (triangle \ triangle{pos.x: 0.7}){pos.y: 2.2}
    ]
}

他の例

main = {
    a: square{}
    b: square{scale: {x: 2, y: 1}}
    c: b{}

    sat(a.topRight() == b.bottomLeft() & a.bottomRight() == c.topLeft())
    sat(b.bottomRight() == c.topRight())
    free(b.pos, b.angle, c.pos, c.angle)
}

---

main = {
    cs: for i in 1:5 get(circle{pos.x: i})

    for indexA in 1:cs.size do(
        for indexB in indexA+1:cs.size do(
            sat(!Overlap(cs[indexA], cs[indexB]))
        )
        free(cs[indexA].pos)
    )

    minimize(BoundingBox(self).area())
}

実装

実装で重要なのがジオメトリ計算と制約計算であり、その部分に関して少し説明をします。

ジオメトリ計算について

ジオメトリの計算はこれから実装するところですが、主にベクトル図形に対する手続きとして以下の項目を実装したいと考えています。

• ブーリアン演算
• フォント対応
• 図形をパスに沿って変形
• 図形を移動させた軌跡の計算
• 図形の法線方向への押し出し

制約計算について

一般的な制約をそのまま解こうとすると SMT ソルバを使うことになると思いますが、図形に関する制約はその多くが実数の非線形制約なので SMT ソルバとの相性が良くないという問題があります（実際 2 次元の IK を Z3 で解いてみたけどほとんどうまくいかなかった）。
したがって、本実装では制約を満たすまでの距離 Distance() を次のように定義し、これを最適化問題として解いています（これは今のところうまくいっている）。

Distance(logic\_expr):=
\left\{ \begin{array}{ll}
a = b &\rightarrow& |a - b| \\
a \neq b &\rightarrow& if \ a = b \ then \ 1 \ else \ 0 \\
a < b &\rightarrow& Max(a - b, 0)\\
a > b &\rightarrow& Max(b - a, 0)\\
a \wedge b &\rightarrow& Distance(a) + Distance(b)\\
a \vee b &\rightarrow& Min(Distance(a), Distance(b))\\
\end{array}\right.

終わりに

来年の春にはある程度実用的に使える状態を目指して開発を進めているので、図の生成に興味がある方は触ってみていただけると嬉しいです。

ついでに

この言語は現在、サイボウズ・ラボユースに参加して開発を行っています。
ラボユースは自分で企画を持ち込んで自由に開発でき、意見をもらえる上に時給まで出してくれるという親切な人たちにより構成されています。