インボリュート曲線

\displaystyle 下記の記事で現在制作してるゲームの中でのキャラクターの経路制御について書きました.

friendsea.hateblo.jp

この中での曲線の定義にインボリュート曲線を使っています.
理由は

  • 端点の指定によって制御可能
  • 曲線の長さが近似なしに求まる
  • 曲線上の最近傍点が探索なしに求まる

といった感じ.安く高精度で色々できる.
数式は観賞用です.

インボリュート曲線

ここで言うインボリュート曲線は円の伸開線のこと.円柱に巻き付けた糸を弛まないように解いたときの糸の端点の軌跡がインボリュート曲線です.

f:id:FriendSea:20181116075840p:plain

数式にすると次の通り.

$$ \begin{pmatrix} x \\ y \end{pmatrix} = r\begin{pmatrix} \cos\theta + \theta\sin\theta \\ \sin\theta - \theta\cos\theta \end{pmatrix} $$

とりあえず微分すると

$$ \begin{pmatrix} \frac{dx}{d\theta} \\ \frac{dy}{d\theta} \end{pmatrix} = r\theta \begin{pmatrix} \cos\theta \\ \sin\theta \end{pmatrix} $$

このベクトルの向きが接線方向,長さが曲線上の点の移動の速さなので,\(\theta\)がそのまま接線方向の角度であり,点の移動速度は\(\theta\)に比例してます. タートルグラフィックスで言えば,亀さんが一定の角速度で回転してるとして,前方向への移動速度が線形に増加するときに描かれる曲線になります.

端点を指定して制御したい

曲線を扱おうと思ったらやっぱりスプライン曲線のように端点の位置と角度を指定して形を決めたいです. これはインボリュート曲線の渦巻きの中から目的の端点にピッタリ合う部分を探して,適当に拡大縮小/回転すればできます.

f:id:FriendSea:20181116162431p:plain

つまり,端点の指定による制御は,ピッタリ合う部分の始点と終点を求める問題になります.

積分形式で表現

与える入力は始点と終点ですが最終的に適当な座標変換を挟めばいいので始点は原点に持っていきます.接線方向も\(x+\)に固定. 曲線の形の定義としては,さっき出てきた接線の角度と移動量の関係だけで十分だったりします.
角度に対する移動量(曲率半径)が線形ならインボリュート曲線になるので,これを定数\(a, b\)を使って\(a + b\theta\)とします.このとき曲線は

$$ C(\theta) = \int_{0}^{\theta}(a + b\theta) \begin{pmatrix} \cos\phi \\ \sin\phi \end{pmatrix} d\phi = \begin{pmatrix} b\cos\theta + (a + b\theta)\sin\theta - b \\ b\sin\theta - (a + b\theta)\cos\theta + a \end{pmatrix} $$

みたいに表せます.

f:id:FriendSea:20181116080335p:plain

いまこんな状態,曲率半径が\(a\)の点が原点に来ました.
定数\(a\)が始点での曲率半径なので,結局の所うずまきの中での始点の位置を定める値になってます. 終点の位置は始点と終点の接線の角度差から勝手に決まります.

係数を解く

欲しい値は曲率半径\(a + b\theta\)の係数\(a, b\)で,これは普通に方程式を立てて解けば出ます.\(\theta_E\)を終点での接線の角度,始点と終点の間の変位を\(V\)とすると.

$$ C(\theta_{E}) = V $$

書き下すとこんな感じ

$$ \left\{ \begin{array}{} (\sin\theta_{E})a + (\theta_{E}\sin\theta_{E} + \cos\theta_{E} - 1)b = V_x \\ (\cos\theta_{E} + 1)a + (\theta_{E}\cos\theta_{E} + \sin\theta_{E})b = V_y \end{array} \right. $$

\(\theta_E\)も\(V\)も定数なのでただの1次の連立方程式.超簡単なプログラムで解けます.
これで必要な値は全て求まったので,入力の端点にピッタリ合う曲線ができます.めでたい.

曲線の長さ

物体を曲線の上で一定の速さで動かしたければパラメータ(今回は\(\theta\))と長さの関係がわかってないといけません.
まずは始点から\(C(\theta)\)までの曲線の長さですが,そもそも点の移動量を定めているのでそれを積分すれば求まります.

$$ l(\theta) = \int_{0}^{\theta} (a + b\theta)d\theta = a\theta + \frac{b}{2}\theta^{2} $$

今度はこれの逆関数を取れば長さからパラメータ\(\theta\)が得られる.ただの2次式なので所謂解の公式を使って.

$$ \theta(l) = \left\{ \begin{array}{ll} \frac{-a + \sqrt{a^{2} + 2bl}}{b} & (b \neq 0) \\ \frac{l}{a} & (b = 0) \end{array} \right. $$

これを使えば\(l\)を一定の速さで増加させたとき,\(C(\theta(l))\)も等速で動いてくれます.

任意の点からの最近傍点

適当に点\(P\)が与えられたとき,曲線上で最も\(P\)に近い点を求めます.

f:id:FriendSea:20181116170613p:plain:w400

求める点\(C(\theta)\)と\(P\)を通る直線は\(C(\theta)\)での接線と直行する.2つのベクトルの内積が0になるはずなので

$$ (C(\theta) - P)\cdot \begin{pmatrix} \cos\theta \\ \sin\theta \end{pmatrix} = 0 $$

これを頑張ってなんやかんやすると

$$ \theta = \cos^{-1}\frac{b}{\sqrt{(P_y - a)^{2} + (P_x + b)^{2}}} + \tan^{-1}\frac{P_y - a}{P_x + b} $$

こんな感じで求まる.めでたい.

良くないところ

当然扱いづらい部分もあって,クリティカルなのを挙げると変曲点がある曲線(S字の曲線)を作れません. いくら渦巻きの中を探してもS字なんてないので当然です.S字ができるような端点を指定すると代わりに変な形のが出ます.

ゲーム内ではいくつかのインボリュートセグメントを連結して経路として扱っています.制御点配置から自動的に端点位置を定めていますが,このときできるだけ正しく曲線が生成できる端点になるように処理しています.

f:id:FriendSea:20181114215707p:plain:w400