投稿者 tel | 2014年2月11日

二次ベジェ曲線と線分の当たり判定

二次ベジェ曲線の式。x0,y0は始点、x2,y2は終点、x1,y1は制御点。

bezier2

bezier2_fig

線分の式。px,pyが始点、qx,qyが終点。

segment

上記の式からtを消すと

(q_y-p_y)(x-p_x)=(q_x-p_x)(y-p_y)

ベジェ曲線の式を代入するとtの二次方程式になるので、解の公式で解くとtが求められる。

\begin{align*} v_x &= q_x-p_x \\  v_y &= q_y-p_y \\  a &= x_2-2x_1+x_0 \\  b &= 2(x_1-x_0) \\ c &= x_0 \\ d &= y_2-2y_1+y_0 \\ e &= 2(y_1-y_0)\\ f &= y_0 \end{align*}

式が少々複雑だったので置き換え。

(v_ya-v_xd)t^2+(v_yb-v_xe)t+v_y(b-p_x)-v_x(f-p_y)

tが0から1のときに直線との交点を持つ。tを二次ベジェ曲線の式に戻して座標を得る。

線分と当たっているか求めたいので、直線との交点の座標が線分の範囲にあるか調べればOK。

二次ベジェ曲線の法線

当たった位置の法線は、二次ベジェ曲線の式をtで微分して接線を求め変形する。

normal

\mathbf{n} = (-y', x')

 

法線が分かったら当たった時の反射する方向が求められる。

二次ベジェ曲線のバウンディングボックス

毎回、当たり判定するとコストが高いので、二次ベジェ曲線のバウンディングボックスを求めてまずはAABBと当たり判定をとる。

二次ベジェ曲線の座標の最大、最小を求めるには微分して0のときのtの値から求める。

xlocal

上記を二次ベジェ曲線の式に代入するとxの極値が得られる。
yも同様にして求めたら、あとは始点、終点、極値の座標から最大値最小値を決めてAABBの左上の座標と右下の座標にすればいい。

コード

http://jsdo.it/sapphire_al2o3/RluP


コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

カテゴリー

%d人のブロガーが「いいね」をつけました。