岡田を切る技術
他サイトに掲載していた過去記事サルベージ
以下本文
これはとある回顧録
何度も諦めかけましたが、数年の歳月を経て遂に岡田を切る技術が一旦の完成へと至りました。その技術を巡る奮闘の歴史と成果について、ここに記録を残していきたいと思います。
画像時代
まずは「切る」という動作が何を指すかを明確にしておきます。 厳密な定義というよりは、切った感を得るために必要そうなふるまいとして定義します。
- 平面上のある領域が、任意の直線を境界として分割されること
- 分割された領域は物理法則に準じてふるまうこと
要するに気持ちよく岡田を切ることができれば目標は無事達成です。
物理エンジン
切った感を高めるためにはやはり「物理法則」に準じたふるまいが欲しくなります。つまりブラウザ上で動く物理エンジンが必要です。 世の中にはフルスクラッチで物理エンジンを作れる人間と作れない人間が居ると思われますが、残念ながら私は後者でした。勝ち目の薄い勝負は避け、素直に巨人の方にすがります。
今回採用したのはmatter.jsというjavascript製の2D物理エンジンです。 http://brm.io/matter-js/
リンク先のデモを見てもらうと分かりますが、めっちゃ物理エンジンしています。描画機能も内蔵しているのでそのまま使うだけで物理エンジン制御下の世界をさっとwebページ上に作り出せます。
**「でもこの物理エンジンだけでは岡田は切れないから・・」**と自分がやるべきことはまだ残っているんだと必死に言い聞かせて先に進みます。
最古の岡田
作図系な処理において最も基本的かつ扱いやすいのは矩形でしょう。そして矩形に「岡田」と書いた画像を貼れば最もシンプルに岡田を物理エンジンの世界に登場させることが可能です。
成功しました、最古の岡田です。まだまだ先は長いですが、小さな成功体験の積み上げこそが大事です。
matter.jsを使えば一瞬で終わりそうに見えますが、画像を矩形に貼り付けるために、matter.jsの描画機能は使わず自前でcanvasに描画する処理を作っています。
とはいえ今回扱う図形は全て剛体なので、物理エンジン世界における図形の中心と回転角さえ分かればcanvasの変形描画機能をそのまま使うことができます。そして勿論matter.jsはそれらのプロパティを提供してくれます。
ctx.save()
ctx.translate(body.position.x, body.position.y)
ctx.rotate(body.angle)
~~ 物理演算の考慮不要な描画処理 ~~
ctx.restore()
両断
次は早速一刀両断していきます。ここからは物理エンジンは無関係で、座標をいじくり倒してポリゴンを直線で両断します。
しかしこの時点ではそれほど複雑な計算は必要ありません。なぜなら登場しているポリゴンは凸多角形 であることが保証されているからです。
凸多角形であることの何が良いかというと、両断した後のポリゴンが必ず2つの凸多角形になることです。 （証明や出展は探していないですが、直感的に正しそうなのでそう信じておきます。）
図だとこんな感じで、左が非凸多角形、右が凸多角形です。
断面となる頂点を2つ追加し、その断面が辺となるように他の頂点を拾い集めて2つのポリゴンを作れば両断処理の完成です。
そして新たに生まれた２つのポリゴンも凸多角形なので、両断前と後で物理エンジンの世界に存在するポリゴンの特性は何も変化していません。それっぽく言うと、凸多角形は切るという処理において完備なわけです。
こうして最古の岡田は無事に切ることができました。
両断後のポリゴンに若干の動きを加えたりすれば、切った感はさらに高まります。
SVG時代
葛藤
「それ岡田じゃなくて画像切っただけじゃない？」
わかる。
ただ岡田と書かれた画像を貼り付けた矩形を切っただけだ、これでは岡田を切ったなんて到底言えない。 画像を切りたいんじゃないんだ、岡田を切りたいんだ。
岡田を求めて
岡田を切るためには、とにかくまずは物理エンジンの世界に岡田を登場させなくてはいけません。 手段は色々あると思いますが、2Dでの表現ができ、かつ座標が扱いやすそうなSVGを入力として採用しました。
SVGを入力に使うと決めたはいいものの、もちろんSVGのデータ表現をそのまま物理エンジンの世界に突っ込むことはできません。最終的には両断計算をする必要もあるので座標としてパースする必要があります。
というわけでSVGの仕様を懇切丁寧にまとめてくださっていていつもお世話になっているサイトを熟読しながらパース処理を作ります。 http://defghi1977.html.xdomain.jp/tech/svgMemo/svgMemo_03.htm
<path>エレメントはコマンドと座標の羅列で図形を表現するのが若干ややこしいものの、M x yやL x yなどのコマンドはそのまま座標として抜き出せます。
曲線という強敵
しかしここで、SVGを入力として使うことに潜んでいた問題に気づきます。ベジェ曲線、円弧、楕円の存在です。
物理エンジンが対応しているのだろうか、両断するときにどんな計算が必要になるのだろうかと瞬時に様々な問題が頭をよぎります。そして早々にそれは無理だと諦め、直線で近似する方針をとりました。 ただでさえ面倒な座標計算にさらに曲線も考慮に入れるなんてやり遂げられる気がしません。まともに勝負するには多角形の世界に持ち込むしかありません。
2次ベジェは2次方程式を、3次ベジェは3次方程式を、楕円は楕円方程式を近似用の頂点を導出していきます。ここは気合で計算していくしかありません。
特に<path>エレメントにおける楕円の表現は、楕円の中心ではなく弧上の始点と終点を指定するという特殊なものだったため、楕円方程式を求めるまでにも手間がかかりました。
https://triple-underscore.github.io/SVG11/implnote.html#ArcImplementationNotes W3Cのドキュメントからも楕円の面倒くささが伺えます。ただでさえ式が難しいのにさらに特殊ケースの分岐まで豊富でとにかく気合が求められます。岡田を切るには気合が必要なのです。
こうして曲線の近似も乗り越え、遂にSVGからポリゴンを座標リストとしてパースすることに成功しました。
3次ベジェの近似サンプルはこんな感じです。近似に使う頂点数を増やせば違和感もかなり減っていきます。
非凸多角形の両断
SVGパースという頭の体操を乗り越え、ついに岡田を物理エンジンの世界に登場させることができました。なんと岡田にはベジェも楕円も必要なかったという事実から目をそらすために、飾り付けも入念に行います。
上の画像を見れば明らかなように、非凸な多角形が世界に溢れ出します。かつて凸多角形の完備性に頼って実装した両断処理にも調整が必要となってくるわけです。
と思わせぶりに書いたものの、実は違いは分割後のポリゴン数が3以上の場合もあり得るというだけです。 一気に分割しようとするとなかなかややこしいですが、やることは2つのポリゴンへの分割を繰り返すだけです。
手順はこうです。
- 直線とポリゴンの各辺との交点を求め、直線の方向順に並べる
- 並べた交点のうち先頭2点だけを分断面として採用してポリゴンを2つに分割する
- 分割したポリゴンそれぞれで１からの処理を繰り返す（分割されなくなったら終わり）
1で並び替えるときは、直線がx軸と重なるような回転を交点にかけるとx座標の比較だけで済んで楽です。雰囲気は下記のような感じ。
const rad = getRadian(line[0], line[1])
crossList.sort((a, b) => rotate(a, -rad).x - rotate(b, -rad).x)
非凸多角形を凸多角形に分解する余談
実はこれを作った当初（2016年頃？）は、matter.jsが非凸な多角形に対応していませんでした。なのでSVGからパースした多角形を三角分割し、分割された三角形をグループ化することで無理やり物理エンジンに食わせていたりしました。
しかし現在のmatter.jsはpoly-decomp.js という外部モジュールと一緒に使うことで非凸な多角形でも問題なく扱えるようになっています。 結局やっていることは同じく凸多角形への分割とグループ化なのですが、凸多角形の最小単位である三角形ではなく、パーツ数が少なくなるよう最適化された分割をしてくれます。
すごい。
matter.jsの進化を喜ぶ共に、いらなくなってしまったかつての処理をここで供養しておきます。
欲しかったのはバッサリ感
準備は整いました。いきましょう、バッサリと。
フォント時代
葛藤と妥協
「それ岡田っぽい形をした図形を切っただけじゃない？」
わかる。
見て見ぬふりをしていましたが、SVGから作り出した岡田っぽい図形には多くの制限事項がありました。
「岡」はまぁ許せなくはないです。
しかし「田」には大きな誤魔化しがあります。不自然な隙間が所々に存在しています。
隙間が気になるなら無くせばいいと思われるかもしれませんが、この隙間には大きな意味がありました。もしこの隙間をなくし、「田」という字そのままを表現しようとすると、ポリゴンに穴が空いてしまうのです。
物理エンジンが対応しているのだろうか、両断するときにどんな計算が必要になるのだろうかと瞬時に様々な問題が頭をよぎる以前に、そもそもデータ構造として今のままでは穴空きポリゴンを表現することはできません。 岡田っぽい図形が切れて満足してしまったこともあり、この難題に再び立ち向かうまでにはさらに３年ほどの年月を待つこととなりました。
転機
月日は流れ、岡田を切ることへの情熱も忘れ去っていたある日、複雑GUI会 という名前の通りディープな集会に参加する機会に恵まれました。 そしてその場で、opentype.jsというライブラリの存在を知りました。 https://github.com/opentypejs/opentype.js/blob/master/README.md
注目の機能は、上の画像のようにフォントからパスを取得することができる機能です。 特に理由はありませんが岡田のパスを取得すべく早速試してみます。
とりあえずREADME通りに使ってみてパスがどんな形式になっているのか調べてみます。
一部界隈の方ならこの画像だけでどんなデータフォーマットなのか一目瞭然でしょう。そうです、これはSVGの<path>エレメントにおけるd属性フォーマットに違いありません。
まるで運命だったかのように、SVGから座標をパースする処理はすでに手元にあります。 しかもこの半年ほど前に、typescriptの素振りをしようとパース処理をリプレイスし、かつては無かったテストまでも大幅に充実させていました。
若干のインタフェース調整は必要でしたが、それほど苦もなく岡田のフォントパースに成功します。
穴あきポリゴンの正体
岡田フォントのパースに成功すると共にあることに気づきました。フォントのパスデータにはポリゴンがフラットな配列で存在するのみなのにも関わらず、opentype.jsは穴の空いたポリゴンもしっかりと描画しています。
穴あきポリゴンを表現するには特別なデータ構造を用意しなければいけないと思い込んでいた身からすると、これは大きな衝撃でした。 もしかしてSVGには白抜き描画用のコマンドも用意されているのではと調べていたら、SVGの教科書 としていつも大活用させてもらっているサイトにてその答えを見つけました。
つまり、ポリゴンにはパスの向きという概念が存在し、逆向きなポリゴンを内包している場合、その内容ポリゴン部分は白抜きされます。この仕様によって、特別なデータ構造を用意しなくとも穴の空いたポリゴンを表現することが可能となっています。
穴空きポリゴンの描画
SVGの仕様から発覚した穴空きポリゴンの表現ですが、これはcanvasでも同様です。 描画方法は既にこちら で記事化しています。
物理エンジン世界での穴あきポリゴン
描画方法は分かりましたが、物理エンジン世界で穴あきポリゴンをどう扱うか考える必要があります。 アイディアはいくつかありそうですが、実装がシンプルそうなので外枠以外は模様として扱うことにしました。
例えばこのような図形があった場合、物理エンジン世界での実態はただの矩形です。そして内部の穴あき矩形はただの模様であり、外枠から独立した物理計算をされることはありません。
ポリゴンの包含判定
この模様方針を実現するために面倒だったのは、物理エンジンに入れ込む外枠ポリゴンと、その内部模様となるポリゴンをグルーピングする必要があることです。 一般的にある面が他の面に含まれているかを判定するのは様々なケースが考えられてとても面倒です。
シンプルなケースは下図左のようなものです。この場合、全ての頂点があるポリゴンに含まれているならば、その頂点から構成されるポリゴンも包含されているとみなすことができます。
しかし右のケースでは早くもその判定が破綻します。同じく全ての頂点が他のポリゴンに含まれているのに、明らかにはみ出している部分が存在しています。 辺の交差判定も加えたらいけるかもしれません。それでは下図左のように、凹のくぼみにぴったり嵌まり込んでいるようなケースはどうでしょうか。
頂点は全て大きいポリゴンの辺上にあり、辺同士での交差もしていません。しかし内包関係にないことは目で見れば明らかです。 中心点がポリゴンに含まれているかの判定も加えたらいけるかもしれません。しかし右のケースから分かるように、中心点が含まれるかどうかはポリゴンの形次第でとても頼りにはできません。
このように一般的なポリゴンの包含判定はとても面倒です。やっぱり手に負えないと投げ出したくもなりましたが、幸運なことにとある抜け道を見つけることができました。 その抜け道とは、今回扱っているポリゴンがフォント由来のものであることでした。
要するに、包含関係は最もシンプルな上記のパターンしかないはずなのです。これも証明などは無く直感的に正しそうだという程度のものですが、先に挙げた面倒なケースのどれも、フォントとしての表現で使われることはないはずです。 このことを前提とするならば、ポリゴンの包含判定は、頂点全てが他のポリゴンに含まれているかを判定するだけで十分となります。
点の包含判定
ある点がポリゴンに包含されているかは、その点から任意の方向に伸ばしたベクトルがポリゴンの辺と何回交差するかを数えることで判定可能です。奇数回なら内部、偶数回なら外部とみなします。 Crossing Number Algorithmと呼ぶそうです。 https://www.nttpc.co.jp/technology/number_algorithm.html
この手法についてはweb上にも多くの資料があるので紹介程度に留めておきます。頭の体操兼素振りと思って手を動かしてみるのも楽しいと思います。
グルーピング
判定の準備は整ったので、あとは外枠用ポリゴンと模様用ポリゴンをグルーピングしていくだけです。複数グループに所属するというケースはないので、意外と単純にグルーピングが可能です。
具体的な手順はこのような感じになりました。
- ポリゴンを面積の大きい順にソート
- 面積最大のポリゴンから順に、その内部に他のポリゴンを含むか判定
- 含むなら同じグループとして確定、含まないならグループ未確定として保留
- 面積最小のポリゴンまでループを回せば全てのグループが確定する
フォント to 物理エンジン世界
こうしてまずは、フォントからパースした岡田を物理エンジン世界に登場させることに成功しました。
穴あきポリゴンの両断
最後の砦です。岡田を切るには、穴あきポリゴンを両断する処理を作らなければなりません。
まずはやるべきことを整理します。
このような穴あきポリゴンを両断したら、
こういうポリゴンの破片が欲しいわけです（もう一方の破片は一旦無視しておきます）。
ここで注目したいのは、穴としての役割を担っていたポリゴンが両断対象になった場合、その穴は消滅して窪みになるということです。 やるべきことが段々と見えてきました。
下図を使ってさらに整理します。
- 下向きの矢印: 両断線
- 左側の図: 外枠ポリゴンを両断した後のポリゴン
- 中央の図: 両断線がヒットした元々の穴用ポリゴン
- 右側の図: 穴開きポリゴンを両断した後に欲しいポリゴン
もうお分かりのように、「両断後の外枠ポリゴン」から「両断線がヒットした穴用ポリゴン」を差し引くことで「両断後のポリゴン」が手に入るということです。所謂ポリゴンのブーリアン演算 です。
ブーリアン演算
今回やりたい演算はこれです。
https://upload.wikimedia.org/wikipedia/commons/1/16/Boolean_operations_on_shapes.png
例によって一般的なポリゴンに対するブーリアン演算を実装するのはとても面倒で心が折れそうになるのですが、今回はある程度状況が限定されています。
ブーリアン判定を行うことになる２つのポリゴンは先述の通り、「両断後の外枠ポリゴン」と「両断線がヒットした穴用ポリゴン」という組み合わせのみです。つまり多少の形の違いはあれど、下記のようにシンプルな状況のみを考えれば十分となります。
さらに外枠ポリゴンと穴用ポリゴンという特性から、両者の回転方向は逆向きであることも保証されています。 両断後の外枠ポリゴンの辺で穴用ポリゴンの辺と交差しうるものは、両断線によって作られた辺だけであることにも注目です。
ここまで条件が揃えばあとは地道に頂点を拾い集めるだけです。
- 両断後の外枠ポリゴンの頂点をインデックス順に拾っていく
- 両断線による辺の始点に辿り着いたら、交点を経由して穴用ポリゴンに移る
- 穴用ポリゴンの頂点をインデックス順に拾っていく
- 両断線による辺と交差する辺の始点に辿り着いたら、交点を経由して両断後の外枠ポリゴンに移る
- 両断後の外枠ポリゴンの残りの頂点を全て拾い集めて完了
両断されなかった穴
先程後回しにしておいたもう片方の破片についても考えます。
両断される穴部分の扱いはすでに解決しました。 残りの両断されなかった穴の扱いですが、両断処理の際は何もする必要はありません。そして両断後のポリゴンが出揃ったタイミングで、外枠用ポリゴンと模様用ポリゴンのグルーピング処理を再適用すれば、両断後の外枠ポリゴンの模様としてあり続けることに成功します。
ありがとう、岡田
こうして、数年に渡った岡田を切るための全ての準備は整いました。様々な困難がありましたが、全てはここへと繋がる道だったのだと考えると感慨深いものがあります。
ここまでの道のり全てに感謝を込めて、バッサリいきます。
さらば、岡田。
付録
計算系リポジトリ
幾何計算や、SVGのパース処理などは使い回しやすいようライブラリ化しています。テストもそれなりに頑張って書いたので、もしSVGから図形をパースしてポリゴン化したいという稀有な希望をお持ちの方が居たらご活用ください。 https://github.com/miyanokomiya/okageo
アプリ用リポジトリ
アプリとしての形を整えたものはここにあります。ただこちらは試行錯誤のままに作っていたのであまり整理はされていないです。 https://github.com/miyanokomiya/okadaphy
最終成果物は静的サイトとして公開もしてあるので、俺も岡田を切りたいという欲求をお持ちの方はご活用ください。 https://hopeful-visvesvaraya-3dafb6.netlify.com/