この記事は美少女ゲームにまつわる話題を取り扱っています。性的な表現が含まれないよう注意していますが、苦手な方はブラウザバック推奨です 
目次
- 背景: デジタルクラフトについて
- テキストをシーン中に置きたい！
- 正三角形しか置けないなんて、ムリムリ！
- 正三角形を任意の三角形に変形するようなパラメータなんて得られるわけないじゃん、ムリムリ!
- 文字の多角形を三角形分割できるわけないじゃん、ムリムリ！
- ムリじゃなかった！？
- Future Works
- 余談
背景: デジタルクラフトについて
私は最近、デジタルクラフト(以下デジクラ)というゲームで遊んでいます。
これはILLGAMESのタイトルに追加して購入することで遊ぶことのできるゲームであり、同ブランドのゲーム中で作成したキャラクターを自由にマップやアイテムとともに配置しスクリーンショットを撮ることのできるジオラマ的な遊びができるソフトです。
これを使えばゲーム外で自分のキャラを表現する手段が用意されたこととなり、ゲーム中の決まったロジックの中で動くだけのキャラクターに留まらない、自分の見せたいキャラクターの魅力を自由に表現することができます。
↑このようなシーンを
↓このようにアイテムを置いていくことで作成していきます
ゲーム公式でキャラクターのアップローダーやシーンデータのアップローダーを用意していることからも、キャラメイクを単なるゲーム中の一要素ではなくUGCなものとして昇華させたい(そしてコンテンツ寿命をサステインさせたい)思惑が垣間見えます。
テキストをシーン中に置きたい！
さてそんなデジタルクラフトですが、困ったことに 文字を3D空間内に置くことができません。
前作のコイカツサンシャインでは同様のジオラマ機能内にテキスト配置のできるオブジェクトがあり、これを使えばミームの再現やちょっとした文字の差し込みに便利だったのですが、今作ではできなくなってしまいました。
これはおそらくUnityのuGUI Text(Unity内で楽にテキストを配置するためのもの)が2021年にLegacyとなったことに起因していると思われます。ちょうどこの年に発売されたコイカツサンシャインはこのuGUI Textを内部で使用しています。次の作品を作るにあたり、EOLが設定されそうなもの(公式フォーラムにて"will be eventually be deprecated"と言及されている)を使いたくなく一旦オミットしたと考えるのが妥当なところでしょうか。(完全な憶測)
でも、自由に文字が置けるなら表現の幅が増えますし、なによりできないことにこそ挑戦してみたくなりますよね？そう思い、試行錯誤したのがこの記事になります。
正三角形しか置けないなんて、ムリムリ！
さて、早速難しい問題に当たります。それは、デジクラではメッシュレベルで自由な図形を作ることができないというものです。
デジクラでは本来、あらかじめ用意されたアイテムとキャラクターをそのまま配置することが想定されており、好きにポリゴンを作り出すことはmodでなければできません。
つまり最初に取り組むべき問題は「メッシュが自由に作れない状態でどのように任意の三角形をつくるか」でした。
なぜ三角形なのかというと、御存知の通り3Dグラフィックではオブジェクトを構成するもっとも基本的な図形は三角形ポリゴンです。ですので、任意の三角形を作り出すことができれば、そこから自由に図形を作り出すことができるといえます。
普通の操作の範囲内であればできないのですが、一つだけ裏道がありました。それは、親オブジェクトのScaleが等倍でないとき、その子オブジェクトを回転させるとせん断変形(図形がぐにゃりと歪むような変形)が起きる ことです。
TRS変換
Unityなどのゲームエンジン(というより3Dグラフィックを使うすべてのもの)では、オブジェクトに含まれる頂点の座標をTRS行列変換というものを使ってワールドでのオブジェクトの頂点座標を計算しています。
TRSのTは平行移動(Translation)行列、Rは回転(Rotation)行列、Sは拡大(Scale)行列を表しており、2次元に射影するとそれぞれ以下のようになります。(都合上$x$,$z$軸で書き、またUnity内での$y$軸周りの回転を扱うため標準的な数学の教科書とは符号が異なります)
T = \begin{pmatrix}
1 & 0 & t_x \\
0 & 1 & t_z \\
0 & 0 & 1
\end{pmatrix}, \quad
R(\theta) = \begin{pmatrix}
\cos\theta & \sin\theta & 0 \\
-\sin\theta & \cos\theta & 0 \\
0 & 0 & 1
\end{pmatrix}, \quad
S = \begin{pmatrix}
s_x & 0 & 0 \\
0 & s_z & 0 \\
0 & 0 & 1
\end{pmatrix}
この3つの行列をかけ合わせればアフィン変換として変換行列が得られ、あとはそれにオブジェクトのローカル頂点 $\mathbf{p}$ をかければワールド座標を得ることができます。
\mathbf{p}_{\text{world}} = T \cdot R \cdot S \cdot \mathbf{p}_{\text{local}}
親子関係のあるオブジェクトでは、親のTRS変換行列に子のTRS変換行列をそのまま適用するだけです。
\mathbf{p}_{\text{world}} = T_p \cdot R_p \cdot S_p \cdot T_c \cdot R_c \cdot S_c \cdot \mathbf{p}_{\text{local}}
せん断の発生
と、ここまでが基本的な変形です。一方、ここで $S_p$ の値が異方($s_x \neq s_z$)である場合を考えてみましょう。(ちょっと天下り的ですが)
話を本質的な部分だけにするため、平行移動 $T$ を省き、親の回転なし・子のスケールなしとして線形部分のみを見ます。
A = S_p \cdot R_c(\theta)
= \begin{pmatrix} s_x & 0 \\ 0 & s_z \end{pmatrix}
\begin{pmatrix} \cos\theta & \sin\theta \\ -\sin\theta & \cos\theta \end{pmatrix}
= \begin{pmatrix} s_x\cos\theta & s_x\sin\theta \\ -s_z\sin\theta & s_z\cos\theta \end{pmatrix}
この変換後の基底ベクトル $\mathbf{e}_1, \mathbf{e}_2$ は $A$ の列ベクトルです。
\mathbf{e}_1 = \begin{pmatrix} s_x\cos\theta \\ -s_z\sin\theta \end{pmatrix}, \quad
\mathbf{e}_2 = \begin{pmatrix} s_x\sin\theta \\ s_z\cos\theta \end{pmatrix}
本来、単なる回転と等倍スケールであれば基底は直交し、内積は $0$ になるはずです。しかし実際に計算すると
\mathbf{e}_1 \cdot \mathbf{e}_2
= s_x^2 \cos\theta \sin\theta - s_z^2 \sin\theta \cos\theta
= (s_x^2 - s_z^2) \sin\theta \cos\theta
となり、以下のいずれかを満たさない限り内積は $0$ にならず、意図しない基底変換、すなわちせん断が生じます。
- $s_x = s_z$（等倍スケール）
- $\sin\theta = 0$（$\theta = 0°, 180°, \ldots$）
- $\cos\theta = 0$（$\theta = 90°, 270°, \ldots$）
これはUnityに限らず、同じような行列演算を行っているものであれば同様に起こります。が重要なのはこれが ゲーム中の正常な動作の範囲内で意図的に起こせてしまう ことにあります。
実際、デジクラ内にて異方スケールで変形させた親の下に三角柱オブジェクトを潰して作った正三角形を親子付けし、その子を回転させてみると下の画像のように変則的な変形が起きます。
↑三角形が斜交座標にあわせて変形していき、90°の倍数ごとに直交座標に戻ることが分かりますね！
これを利用すれば、どんな図形でも再現できるポテンシャルがあるのでは…？そう考え、さらに深堀りしてみたくなりました。
変形の定式化
そこで、まずはこの変形を定式化することにしました。
普通に考えれば上記のTRS変換がそのまま適用されていると考えられるのですが、若干挙動が異なっていました。それは、子オブジェクトにおいて 親のスケールによる拡大が打ち消される 仕様があることです。具体的には、子のローカルスケールが親の実効スケールで除算されるような形で補正されています。
変形による座標変換のデータポイントをゲーム中で確認・記録し、何度もClaudeやChatGPTと会話を重ねた後……（そしてClaudeのレートリミットに何度も殺された後……
以下のような変換が得られました。
変換式
変形後の頂点座標 $\mathbf{p}'$ は、元の頂点座標 $\mathbf{p}$ から以下のように求まります。
\begin{aligned}
\mathbf{p}' &= R(\alpha) \, S \, R(\theta) \, C \, \mathbf{p} + \mathbf{t} \\
&= A_{\text{forward}}(\alpha, \theta, s_x, s_z, c_x, c_z) \, \mathbf{p} + \mathbf{t}
\end{aligned}
ここで各項は以下のとおりです。
回転行列:
R(\phi) = \begin{pmatrix} \cos\phi & \sin\phi \\ -\sin\phi & \cos\phi \end{pmatrix}
親のスケール:
S = \begin{pmatrix} s_x & 0 \\ 0 & s_z \end{pmatrix}
子のスケール補正:
C = \begin{pmatrix} \dfrac{c_x}{e_x} & 0 \\ 0 & \dfrac{c_z}{e_z} \end{pmatrix}
実効スケール補正 $e_x, e_z$ は、行列 $E = R(\theta)^{T} S , R(\theta)$ の対角成分です。ちょうどここが親スケールでの拡大を取り消す働きをしています。
\begin{aligned}
e_x &= s_x \cos^2\theta + s_z \sin^2\theta \\
e_z &= s_x \sin^2\theta + s_z \cos^2\theta
\end{aligned}
平行移動:
\mathbf{t} = \begin{pmatrix} p_x \\ p_z \end{pmatrix}
実際にこの変換式を使っていくつかゲーム中で座標変換プロセスを確認すると、無事に思った通りの変換ができていることが確認できました！ これを使えば、正三角形を変形して任意の三角形に変換するその過程を完全に把握できたことになります。となると、次に必要なのはこのパラメータをどのように得るのか、ですよね。
正三角形を任意の三角形に変形するようなパラメータなんて得られるわけないじゃん、ムリムリ!
さて、式が得られた今、それを構成するパラメータをまとめてみましょう。
| 記号 | 意味 | 所属 |
|---|---|---|
| $p_x, p_z$ | 親Position | 親 |
| $\alpha$ | 親Rotation y | 親 |
| $s_x, s_z$ | 親Scale | 親 |
| $\theta$ | 子Rotation y | 子 |
| $c_x, c_z$ | 子Scale補正 | 子 |
ここでPositionは単なる平行移動ですので、最適化の対象から外すことができます。(閉形式で求めることができる)
さらに、$s_x, s_z$ については
s_x + s_z = 1
の制約を与えることにします。なぜなら、親のスケール $(s_x, s_z)$ を同じ比率 $k$ 倍しても実効スケール $e_x, e_z$ も $k$ 倍され、子のスケール補正で打ち消されるため、スケールの絶対値ではなく比率だけが変形に影響するからです。
そこで $s_x + s_z = 1$ と正規化し、変数を1つ減らします。
となると、残った変数は $\alpha, \theta, s_x, c_x, c_z$ の5つになります。この問題を整理すると、
(\text{デフォルト正三角形の座標}2\times2) \xrightarrow{\alpha, \theta, s_x, c_x, c_z\text{を使った変換}} (\text{任意の三角形の座標}2\times2)
という最適化問題になります。もちろん、任意の 三角形を表すためには退化ギリギリのほぼ直線みたいな三角形をも表す必要があり…それがこの問題を難しくしました(最終的に、そのような三角形を作らなくて済むような三角形分割のアルゴリズムを採用することで解決しました)
最適化アルゴリズムの試行錯誤
評価方法として、
- パラメータから再構成した三角形と目的の三角形の誤差
- パラメータは壊れていないか?(正値、そしてデジクラの制約上少なくとも0.01以上である必要がある)
の2点を置き、順番にいくつかの最適化アルゴリズムを試してみました。
特異値分解(SVD)
最もベーシックなのは特異値分解による変換です。この問題はぱっと見SVDで解けるように見えます。
というのも、SVDは行列を
A = U \Sigma V^{T}
の形に分解します。そして、これはちょうど回転×拡大×回転の形をしており、今回の求めたいものである回転×拡大×回転x拡大に近い形をしています。
実際、この拡大が仮に等方であったとすると、拡大行列は定数×単位行列の形になるので拡大行列が可換となり一つの拡大行列としてまとまり求める事ができます。…が、もちろん、今回の問題設定では異方ですので使えません。
差分進化アルゴリズム(differential_evolution)
次に確実な解を得るためのベースラインとして、差分進化アルゴリズム(scipy実装)を使用しました。これは安定して解けたのですが、進化アルゴリズムであるためイテレーションごとの計算処理がなかなか重く、一個の三角形に数百msほどかかることになってしまいました。これはフォント一文字に数百の三角形が必要なことを考えるとかなり致命的だったので他のアルゴリズムを試すことにしました。
連立非線形方程式(fsolve)
次に試したのが、制約を増やし連立非線形方程式(scipy実装)として解くものです。上記の $s_x + s_z = 1$ に加えて $c_x = c_z$ (→せん断だけに変形を任せたい意図) という制約を加えて4つの方程式とし解かせてみましたが、かなりの率で再構成に失敗してしまいムリでした。おそらく際どい三角形に対してせん断変形のみでは不十分だったためと考えられます。
最小二乗法(least_squares)
最終的にシンプルに最小二乗法(scipy実装)を利用して解く方法に落ち着きました。まず変換元の三角形の座標 $P_0, P_1, P_2$ と変換先の座標 $Q_0, Q_1, Q_2$ から、目的のアフィン変換
\hat{A} = [Q_1-Q_0,\ Q_2-Q_0][P_1-P_0,\ P_2-P_0]^{-1}
を作ります。（ここで $[Q_1-Q_0,\ Q_2-Q_0]$ は、ベクトルを列として並べた $2\times2$ 行列です）そして、あとはこの $\hat{A}$ に近くなるようなパラメータを得たいので、この差を残差関数としそれを最小化します。
\min_{\alpha, \theta, s_x, c_x, c_z} \|A_{\text{forward}}(\alpha, \theta, s_x, 1-s_x, c_x, c_z)-\hat{A}\|_F^2
あとはこの問題設定を least_squares に与えることで、この変換を表すパラメータを得ることができます!
これはヤコビアンを明示的に与えることで更に高速化もできるはずなのですが、とりあえず問題ない程度の時間まで短縮できたので(1秒に数百個程度の三角形を処理できる)このままにすることにしました。
文字の多角形を三角形分割できるわけないじゃん、ムリムリ！
好きに三角形を作ることができるようになった今、残ったのはあとひとつのトピックです。それは、「どのようにして文字を三角形の組み合わせに変換するのか」です。
これは素直に取り組むには難しいタスクですが、幸いにも今回のプログラムはStreamlit上での実行を想定しており、Pythonの手厚すぎるライブラリ群によってどうにでもできてしまいます(前チャプターで使ったscipyもその片鱗ですね)。ここは一つ、巨人の肩の上に乗ってしまいましょう。
手順としては、
のようになります。1、2はライブラリを使用して順当に処理を行っていけばよい(重なるパスをどうするか、図形中にある穴の部分をどうするかなどの考慮は必要ですが)一方、最後の三角形分割についてはアルゴリズムの試行錯誤が必要でした。この「三角形分割(Triangulation)」はそれだけで一分野がなりたっているものであり、プラクティカルな使いやすさ(どんな図形に対してもロバストか)と理論的な厳密さのトレードオフが存在していると言え、それ故に今もなお新たなアルゴリズムが考案され続けているようです。
Earcut
まず試したのはEarcutというアルゴリズムでした。
これはグリーディー寄りのアルゴリズムとなっており、
- 三角形の内角が180°を超えていないか
- 他の頂点が三角形内にないか
という2つの条件を満たす三角形をEarとみなし、条件を満たしたものをとにかく切り出していくアルゴリズムとなっています。シンプルなだけにとても早い動作です。
これを判定しているのが↓の部分になります。
試しに、佑字 肅フォントに「發」という複雑めな構造の漢字を与え分割させてみると以下のようになります。(これがうまくいけば麻雀牌をデジクラで扱えますね！)
確かに三角形分割ができている一方、
少ない大きな三角形 vs たくさんのとても細長い三角形
のような構造になっていることが分かります。そして、この細長い三角形は退化寸前のものも多く、そのような三角形は極端なパラメータを取りがちであるため前チャプターでやった最適化の段階でよくコケる結果となりました。他のアルゴリズムを試してみることにします。
Triangle
次に試したのはTriangleというアルゴリズムでした。
論文を元に雑にNotebookLMに投入したものからキャッチアップしたことをまとめると、Triangleは以下のような流れで図形を三角形に変換しているようです。
- まずは図形の辺を無視し、図形の頂点のみで分割統治法によりドロネー三角形分割する
- ドロネー三角形分割はある三角形の外接円に他の頂点が存在していないか、を方針に三角形分割するもの
- この段階では辺をすべて無視するので、図形の外部や図形中の穴の部分に存在してはならない辺が残る
- 無視していた図形の辺をドロネーに加える。この際、辺が交わることが起きるので、元図形の辺を優先して残す
- これを論文では制約ドロネー三角形分割(constrained Delaunay triangulation)と呼んでいる
- 存在してほしくない三角形の一つを起点として、ペイントの塗りつぶしのようにそれに繋がっている三角形を連鎖的に消してバリを取っていく
- これを論文中では triangle-eating virus (三角形を食べるウイルス)と呼んでいる
- 品質の悪い三角形を改善する
- まずは元図形にあった辺を追加したことで崩れたドロネーの条件をよりドロネーに近づける。三角形の直径円に他の頂点があればその中点に新たな頂点を加え分割する。
- 次に面積が大きすぎたり角が鋭すぎる"悪い三角形"を、その外接円の中心(外心)に新たな頂点を作りそこで分割する
- このアルゴリズムはRuppert’s Delaunay Refinement Algorithmと呼ぶらしい
これらの手順をまとめたものが元論文では以下のような図になっていました。
また、このアルゴリズムで重要な"品質改善"の部分の図もあります。上は直径円を中点で分割するもの、下が外接円の中心を頂点として加えているものです。どちらも、ドロネー条件を満たさない"悪い三角形"が修正されていますね！
さて、このアルゴリズムで同様に「發」を処理させてみましょう。
確かに極端に細長い三角形は存在せず、おにぎり型に近いような扱いやすい三角形に分割できていますね！
…が、その一方で三角形の数はかなり増えてしまっており、最適化の手間を考えるともっと三角形を減らしつつもいい感じのものが欲しいなと思ってしまいました。(また、たまにSIGSEGVが起きることがあり、ちょっとだけパッチを書く必要があったりと、安定性も少し不安でした。)
そこで、さらなるアルゴリズムを探してみます。
TriWild
上記のTriangleアルゴリズムは1996年に提案されているものですので、より新たなアルゴリズムが提案されているかも？ということで、ChatGPTに最近の研究をDeepResearchさせたところTriWildというアルゴリズムを見つけました。
これは2019年に提案されたアルゴリズムで、本当は今回の問題のような直線メッシュを主眼にしたものではなく、曲線メッシュを扱うためのものなようです。しかし、論文内でTriangleと比較していたりと、直線メッシュの作成にも使えるようです。
再びこの元論文をNotebookLMに投入してキャッチアップしてみます。
このアルゴリズムの一番すごい部分は、現実に存在するどんな不完全なSVGデータでもそのまま変換できるロバスト性にあります。実際、論文にはネットから2万個のSVGデータを収集し、このアルゴリズムにかけた所、データサイズが大きすぎて失敗した一件を除きそれ以外の全てで問題なく変換できたと書かれています。これは重複する辺を減らしたり、交差する辺を新たに頂点を作ってサニタイズする処理を徹底して行っていることによる結果なようです。
このアルゴリズムでは上記のサニタイズを行った後、BSPという方法で図形を三角形化します。(Claudeによる可視化)これはTriangleで使っていたようなドロネー図に基づくものとは異なり、よくない形の三角形が生成される一方、数値的に安定して分割できます。
ではそのよくない形の三角形をどう補正するのか。それはAMIPSという評価関数を下げるように調整しています。
AMIPSとは、ある正三角形を任意の三角形に変換したときのアフィン変換 $T$ のヤコビアン $J$ を考え(すぐ上で聞いたような話ですね…？)、それを使って下の式のように定義した関数です。
E_{\text{AMIPS}}(T) = \exp\!\left(\frac{\|J\|_F^2}{\det J}\right)
この $\exp$ の中身の分数を見ると、
- 分母が小さくなる → 行列式(面積)が小さくなるような変換なので嫌だ
- 分子が大きくなる → 辺長の伸縮が大きい、三角形を歪めるような変形なので嫌だ
というように評価関数が設計されていることが分かりますね。
こちらにClaudeに作ってもらったAMIPSの可視化ツールがあります。ムリのある三角形になると関数値が高くなっていく様子がわかります。
これはまさにさっき数理最適化でやっていたことと似たようなことをやっています！ より正三角形に近いように補正されるのであれば、正三角形を変形させる数理最適化がうまくいくというのも納得ですね。
さて、ちょっと説明が長くなってしまいましたが、「發」をTriWildに任せてみましょう！
これを見ると、Earcutほどムリのない形の三角形であり、そしてTriangleほど数が多くなく表現できていることが分かります。
色々な文字を試してみましたが、確かにこの方法は安定してバランスよく分割してくれていると言えそうです！
ムリじゃなかった！？
さて、とてつもなくあちらこちらに課題がありましたが、無事に文字をデジクラに置くための筋道は整いました！
最終的には、
- 文字をStreamlit上で入力
- fontTool & fontPensで文字を線分に変換
- 線分をTriWildで三角形分割
- 得られた三角形をscipyの最小二乗法でパラメータ推定
- パラメータを自作のライブラリでデジクラのデータにする
というような過程を経て、文字オブジェクトを出現させることができます。
これらの処理すべてを組み合わせたものをこちらのStreamlit Cloud上にて公開しています。("生成方式"を"メッシュ(三角形)"にすることで有効になります。)
そして、コードはこちらにあります。
実際に使ってみると、このようにシーン内にきれいな文字を作り出すことができます！
(この文については↓を見てください！)
そしてもちろん、この文字一つ一つを構成する三角形は、親子付けされたオブジェクトのペアに数理最適化を行ったパラメータを設定することで表示されています。
Future Works
今回はあくまで文字を作るためのものでしたが、TriWildがネットにあるSVGへの耐性にかなり自信があるようですので、SVG画像をそのまま読ませるのも面白いかも？と思い実験しています。
おわりに
この記事のタイトルの元ネタとなった
わたしが恋人になれるわけないじゃん、ムリムリ!（※ムリじゃなかった!?）
はAmazon Primeなどで配信されています！