The algorithm of Beautyを読んで植物モデルに関する事物をまとめ、モデリングソフトHoudiniで具体的な実装をします。たまに別文献を参照します（目標）。

L-systemの定義

一部生成文法の知識を説明なしに用いています
この記事内では特に指定がない場合「L-system=DOL-system」として用います。

L-systemとは1968年にAristed Lindenmayerによって提案された植物モデルの一つです。まずはL-systemの最も基礎的なものであるDOL-systemについて考えます。

DOL-systemとは決定性(deterministic)で文脈自由(contest-free)である形式文法により記述されるL-systemです。つまりその生成規則は非終端記号1つ（a,bなど）の置き換えにより記述されます。
定義は以下です。

G=〈\,V,\omega,P\,〉\quad(\omega\in V^+\,,P\subset V\times V^+)

$V$はアルファベット集合、$\omega$は初期の文字列(axiom)、$P$は生成規則(rewriting rules)でPを全て同時に適用します。例を一つ挙げます。

V = \{a,b\}

\omega = a

P =\{(a,ab)\,(b,a)\}

$P$内の$(a,b)$は$a\to b$の意味です。このとき$a$から始まり次のように文字列が生成されることが分かります。
$a\Rightarrow ab\Rightarrow aba \Rightarrow abaab \Rightarrow abaababa$
またここで$abaababa$の世代数を4とします。

2次元L-systemでの適用法

Turtle-interpretation

L-systemの非終端記号に二次元空間での直進、回転等の意味を付与して終端記号のように扱います。これをturtle-interpretationといいます。
具体的には以下のようなコマンドが使えます。

turtle-interpretationの法則
記号	意味
F	決められた長さ$d$前進（線を描く）
f	決められた長さ$d$前進（線を描かない）
+	反時計回りに決められた角度$\theta$回転
-	時計回りに決められた角度$\theta$回転

ではHoudiniを利用してみます。今回はHoudini19.5を使用します。Geometry→L-System SOPを使います。

図1 : L-systemの設定

L-System SOP内のContext Ignoreが$V$,Premiseが$\omega$,Ruleが$P$に対応します。Ruleでは"="で生成規則を記入できます。また決められた長さ$d$はValuesのStep Sizeで、決められた角度$\theta$はAngle(0~360)で変更できます。
$\theta=90°$とし、上記のルールで生成される図形を確認してみます。

図2 : L-systemの図解

生成規則については上の図の通りです。
1本の直線から3本分の長さの直線の集合に置換されることを考慮すると、直線の長さを1回の置換ごとに1/3倍するのが自然と考えられます。よって、直線の長さ$d$は

d = 1 / 3^{世代数}

となります。下記は第3世代と第4世代の生成される図形です。

第3世代	第4世代

Edge-rewriting(エッジ書き換え)

エッジ書き換えは、$F$に変数を付与してL-systemを拡張する手法です。
例えば、$F_l,F_r$のように$F$に添え字をつけて区別します。これにより$F_l,F_r$に別々の生成規則を割り当てることができるようになり、表現の幅が増えます。
ここで下記のL-systemの例について考えてみます。

\omega = F_l\newline

P=\{(F_l,\, F_l+F_r++F_r-F_l--F_lF_l-F_r+),\,

(F_r,\,-F_r+F_rF_r++F_r+F_l--F_l-F_r)\}

なお、$\theta=60°$とします（本質的には関係ないです）。こちらも図解してみます。ただし$F_l$を赤、$F_l$を青で表記します。

図3 : Edge-rewritingの図解

$F_l$は左のように置き換えられます。ここで$F_l$には進行方向に対して左手側、$F_r$には進行方向に対して右手側に正六角形を右図のように書き足します。その結果曲線は正六角形に（だいたい）収まることが分かります。
つまり、$F_l$や$F_r$は正六角形を代表する直線を表し、生成規則に従うとより小さな正六角形を代表する$F_l$や$F_r$に置き換えることができる、さらにその正六角形は元の正六角形を余すことなく埋めることができるということが分かります。
あとは正六角形は小さな正六角形7個に分割されることから

d = 1 / \sqrt7^{世代数}

とするかL-systemを適用した後にTransform SOPで面積を1/7する（今回はこちらを採用しました）ことに気をつけるとHoudiniでは以下のようになります。

図4 : Edge-rewritingの設定

小さいので拡大してご覧いただきたいのですが、まずHoudiniには$F_l$や$F_r$を直接Ruleに書くことはできません。そこで、Houdiniのhelp内のL-system SOPの「エッジの書き換え」の部分を見てみると、$F(l,w,s,d)$にもう一つ変数を付与して、$F(l,w,s,d,flag)$のようにすれば$F_l$や$F_r$が実質的に表現できる（$flag = 0\Rightarrow F_l,\ flag = 1\Rightarrow F_r$）と分かります。今回の例ですと、tubeは使いませんのでtubeの分割数を表す$d$やtubeの断面数を表す$s$は使いませんのでここをフラグ化しても構いません。
続いて、$g(i)$についてですが$g$は直後のプリミティブを変数$i$でグループ化します。具体的には$g(0)$で直後のプリミティブをグループの0番に、$g(1)$で直後のプリミティブをグループの1番に入れます。$[$についてはプッシュの意味で（つまりpushmatrix等と意味は同じ）、この時点で新規のプリミティブを生成します。つまり随時プリミティブを作成し、それをグループ化しているということです。この処理はなくてもよいですが、あると分かりやすく可視化できます。
ではまずは生成される図形を見てみます。

第2世代	第3世代	第4世代

次に図3のように正六角形を並べてみます。ただし$F_l$を赤、$F_l$を青の正六角形で表記します。

第2世代	第3世代	第4世代

このように図形はある意味で空間を自己交差なく埋め尽くす性質を持っており、空間充填曲線(FASS-curve)であることが分かります。空間充填曲線ではフラクタルのような自己相似のような関係も見られます。

フラクタル図形の描画

フラクタル図形をEdge-rewritingを使って描画してみます。フラクタルの例に関しては、石村貞夫, 石村園子著「フラクタル数学」を参照します。今回は植物モデルに焦点を当てていることもあり、スギの葉というフラクタル図形ををL-systemで実装してみます。スギの葉については以下の図の通りです。

図5 : スギの葉の図解

初期の図形は角度30度の二等辺三角形です。フラクタルでは、この三角形を2つの（縮小）写像で赤の三角形と青の三角形に写します。これの写像を新たな作成した赤青の二等辺三角形にも適用していきます。
これを無限回返したものを杉の葉の極限図形といいます。極限図形ではフラクタルでいうところの自己相似性が見られます。
今回はこの写像をEdge-rewritingで実装してみます。初期図形中の左側の辺を$F_l$、右側を$F_r$とし、$F_l$を赤い三角形の周の辺に、$F_r$を青い三角形の周の辺に書き換えます。
(数学的なL-systemの記述は省略します。)
また、L-systemのturtleコマンドに関して少し補足します。

turtle-interpretationの法則
記号	意味
[	現在の位置を保存し、プリミティブを生成する(プッシュ)
]	保存した位置を現在の位置とし、プリミティブを閉じる（ポップ）

これらを利用して、Houdini上で組んだL-systemが以下です。

Premise : [+F(1/(2 * cos(30)),1,1,0)]F(1,1,0,2)[-F(-1/(2 * cos(30)),1,2,0)]
Rule1 : F(l,w,s,d):(s=1&d=0) =[--F(l * 2/3,1,1,1)]-F(l * cos(30)*4/3,w,s,2)[+F(-l * 2/3,1,2,1)]
Rule2 : F(l,w,s,d):(s=1&d=1) =[++F(l * 2/3,1,1,0)]+F(l * cos(30)*4/3,w,s,2)[-F(-l * 2/3,1,2,0)]
Rule3 : F(l,w,s,d):(s=2&d=0) = [+F(l / (2*cos(30)),1,2,1)]F(l,w,s,2)[-F(-l / (2*cos(30)),1,1,1)]
Rule4 : F(l,w,s,d):(s=2&d=1) = [-F(l / (2*cos(30)),1,2,0)]F(l,w,s,2)[+F(-l / (2*cos(30)),1,1,0)]
Rule5 : F(l,w,s,d):d=2 = f(l,w,s,d)

ただし、$\theta=30°$($+,-$の回転角度)としています。
$F(l,w,s,d)$の$s$や$d$はtubeの断面数や分割数を表しますが、今回もtubeにはしないのでここをflagとして使用します。$s=1$で$F_r$を$s=2$で$F_l$をさし、$d$については青の三角形が元の三角形に対し横軸中心で反転するため$F_l,F_r$で2パターン用意しています。最後のRuleは図5内の余分な$F$を削除しつつ整合性を保つため、線だけ消して移動は残る$f$コマンドに置き換えています。

以下がスギの葉のL-systemの結果です。

第2世代	第4世代	第6世代

最後に

最後までお読みいただきありがとうございました。記事を書くのはほぼ初めてなので、拙い部分をあったかと思います。いいねをいただけると励みになります。(2)では3次元のL-systemを用いた植物モデルをHoudiniで実装する予定です。

参照

Przemyslaw Prusinkiewicz・Aristed Lindenmayer著 The algorithmic beauty of plants(2004)　Ch1.1~4
https://algorithmicbotany.org/papers/#abop
Houdini 日本語版wiki
https://www.sidefx.com/ja/docs/houdini/nodes/sop/lsystem.html#%E3%82%A8%E3%83%83%E3%82%B7-%E3%81%AE%E6%9B%B8%E3%81%8D%E6%8F%9B%E3%81%88,%E3%82%A8%E3%83%83%E3%82%B8%E3%81%AE%E6%9B%B8%E3%81%8D%E6%8F%9B%E3%81%88
石村貞夫, 石村園子著　フラクタル数学(1990/7/1)
https://www.amazon.co.jp/%E3%83%95%E3%83%A9%E3%82%AF%E3%82%BF%E3%83%AB%E6%95%B0%E5%AD%A6-%E7%9F%B3%E6%9D%91-%E8%B2%9E%E5%A4%AB/dp/4489003323