線分と三角形の衝突判定
概要
分離軸判定という方法を用いた衝突判定を行います。
詳しい解説はこちらのサイトを御覧ください。
マルペケつくろーどっとコム - その13 OBBとOBBの衝突
この手法を使うと凸形状の物体同士ならどんな形状でも衝突判定できるようです。ただあまりに複雑な形状だと計算時間掛かりそうですが…。だから普通は矩形などの簡単な形状に置き換えて判定するんでしょうね。
さて今回はこれをHSPで実装してみました。
ただし都合により三角形と線分の衝突判定です。
モジュール化したサンプル
早速モジュールです。
サンプル付きなのでそのまま実行出来ます。
実行すると画面上にボタンが出るのでそれを適当に何度かクリックして下さい。
;#ifndef __MODULE_NAME__
;#define global __MODULE_NAME__
#module
;---------------------------------------------------------------------------------------------------
;///////////////////////////////////////////////////////////////////////////////////////////////////
;
; 内積
;
;[ Infomation ]
; res = GetInnerProduct2D( double x0, double y0, double x1, double y1 )
; p1=0～(0) :
;
; return : 0
;
;[ comment ]
;
#defcfunc GetInnerProduct2D double x0, double y0, double x1, double y1
return (x0*x1 + y0*y1)
;///////////////////////////////////////////////////////////////////////////////////////////////////
;
; 線分に垂直な単位ベクトルを取得
;
;[ Infomation ]
; GetUnitVectorNormal double segx0, double segy0, double segx1, double segy1, var uvx, var uvy
; double segx0, double segy0 : 線分の一端
; double segx1, double segy1 : 線分の一端
; var uvx, var uvy : 算出した単位ベクトル
;
; return : 0
;
;[ comment ]
;
#deffunc GetUnitVectorNormal double segx0, double segy0, double segx1, double segy1, var uvx, var uvy
; ラインに垂直なベクトル
;(-segy0, segx0) - (-segy1, segx1)
;片方を原点に移動
x = -segy1 + segy0
y = segx1 - segx0
;ベクトル長さ
l = sqrt( x * x + y * y )
;単位ベクトル
uvx = x / l
uvy = y / l
return
;///////////////////////////////////////////////////////////////////////////////////////////////////
;
; 線分と三角形の衝突判定
;
;[ Infomation ]
; IsColLineTri array pts, array lp, array tp
; array pts(2,5) : 頂点
; array lp(2) : 線分頂点ID
; array tp(3) : 三角形頂点ID
;
; return : 衝突判定結果
; 0:衝突していない
; 1:衝突している
;
;[ comment ]
;指定した線分と三角形の衝突判定を行います。
;
;ptsは線分と三角形の頂点データが入った配列変数です。
;例えば頂点番号idのXY座標は、( pts(0, id), pts(1, id) ) となります。
;
;lpは線分の両端の頂点の頂点番号が入った配列変数です。
;tpは三角形の３頂点の頂点番号が入った配列変数です。順番はどちら周りでも関係ありません。
;
;線分と三角形が衝突していた場合、statに結果を返します。
; stat = 0:衝突していない
; stat = 1:衝突している
;
#deffunc IsColLineTri array pts, array lp, array tp
;分離軸を用いて衝突しないケースを探します。
;１つでも衝突しないケースが見つかった場合、衝突していないと判定します。
ddim inp, 5
; 接触フラグ
;hf = 0 : 接触
hf = 0
;-------------------------
;
; 分離軸：線分
;
; 調査する分離軸を取得
; 線分に垂直な単位ベクトル取得
GetUnitVectorNormal pts( 0, lp(0)), pts( 1, lp(0)), pts( 0, lp(1)), pts( 1, lp(1)), brx, bry
; 分離軸に各点を投影
;内積・投影
;A(x0, y0)・B(x1, y1)
;内積： A・B＝ x0*x1 + y0*y1
; ＝ sqrt(x0*x0 + y0*y0) * sqrt(x1*x1 + y1*y1) * cos(t)
;
; 線分
inp(0) = GetInnerProduct2D( brx, bry, pts( 0, lp(0)), pts( 1, lp(0)) )
;inp(1) = GetInnerProduct2D( brx, bry, pts( 0, lp(1)), pts( 1, lp(1)) )
; 三角形
inp(2) = GetInnerProduct2D( brx, bry, pts( 0, tp(0)), pts( 1, tp(0)) )
inp(3) = GetInnerProduct2D( brx, bry, pts( 0, tp(1)), pts( 1, tp(1)) )
inp(4) = GetInnerProduct2D( brx, bry, pts( 0, tp(2)), pts( 1, tp(2)) )
; 衝突判定
;hf = 0 : 衝突
hf = ( inp(2)<inp(0) ) & ( inp(3)<inp(0) ) & ( inp(4)<inp(0) )
hf |= ( inp(0)<inp(2) ) & ( inp(0)<inp(3) ) & ( inp(0)<inp(4) )
if hf : return 0
;-------------------------
;
; 分離軸：三角形の辺
;
n0 = 0
n1 = 1
n2 = 2
repeat 3
; 調査する分離軸を取得
; 辺に垂直な単位ベクトル取得
GetUnitVectorNormal pts( 0, tp(n0)), pts( 1, tp(n0)), pts( 0, tp(n1)), pts( 1, tp(n1)), brx, bry
; 分離軸に各点を投影
; 内積・投影
; 線分
inp(0) = GetInnerProduct2D( brx, bry, pts( 0, lp(0)), pts( 1, lp(0)) )
inp(1) = GetInnerProduct2D( brx, bry, pts( 0, lp(1)), pts( 1, lp(1)) )
if inp(0)<inp(1) : lmax = 1 : lmin = 0 : else : lmax = 0 : lmin = 1
llength = inp( lmax ) - inp( lmin )
; 三角形
inp(2) = GetInnerProduct2D( brx, bry, pts( 0, tp(n0)), pts( 1, tp(n0)) )
;inp(3) = GetInnerProduct2D( brx, bry, pts( 0, tp(n1)), pts( 1, tp(n1)) )
inp(4) = GetInnerProduct2D( brx, bry, pts( 0, tp(n2)), pts( 1, tp(n2)) )
if inp(2)<inp(4) : tmax = 4 : tmin = 2 : else : tmax = 2 : tmin = 4
tlength = inp( tmax ) - inp( tmin )
; 投影時の長さで衝突判定
if inp(lmax)<inp(tmax) : ltmax = tmax : else : ltmax = lmax
if inp(lmin)<inp(tmin) : ltmin = lmin : else : ltmin = tmin
ltlength = inp( ltmax ) - inp( ltmin )
if ltlength > llength + tlength : hf = 1 : break ;衝突しないケースを発見
; n0, n1
;n0 = 0,1,2
;n1 = 1,2,0
;n2 = 2,0,1
n0++
n1++
n2++
if n1>2 : n1 = 0
if n2>2 : n2 = 0
loop
return hf=0
;---------------------------------------------------------------------------------------------------
#global
;#endif ;__MODULE_NAME__
;-------------------------------------------------------------------------------
;
; 仮実行スクリプト（デバッグ作業用）
;
;#####################################################################
;ここにはデバッグ作業用のスクリプトを記述します。
;ここを有効にするとこのファイル単独での実行が可能になります。
;
;0 ：リリースモード 本体側から#includeで連結して動作させる場合です。
;1 ：デバッグモード このファイル単品で動作確認が出来ます。
#if 1
; ここにデバッグ用コードを記述する
dim pts, 2, 5
dim objTri, 3
dim objLine, 2
; オブジェクト
objTri(0) = 0,1,2
objLine(0) = 3, 4
; 頂点作成
gosub *l_make_pts
pos 0,0
button gosub "実行", *l_draw
stop
;----------------------------
;
; 描画実行
;
*l_draw
; 頂点作成
gosub *l_make_pts
redraw 0 : color 255, 255, 255 : boxf : color : pos 0,0
; 衝突判定
IsColLineTri pts, objLine, objTri
if stat : color 255
; 三角形
line pts( 0, objTri(0)), pts( 1, objTri(0)), pts( 0, objTri(1)), pts( 1, objTri(1))
line pts( 0, objTri(1)), pts( 1, objTri(1)), pts( 0, objTri(2)), pts( 1, objTri(2))
line pts( 0, objTri(2)), pts( 1, objTri(2)), pts( 0, objTri(0)), pts( 1, objTri(0))
; ライン
line pts( 0, objLine(0)), pts( 1, objLine(0)), pts( 0, objLine(1)), pts( 1, objLine(1))
; 点番号表示
repeat 5
pos pts( 0, cnt), pts( 1, cnt)
mes "" + cnt
loop
; 情報表示
pos 0,30
repeat 5
mes "p(" + cnt + "): "+ pts(0,cnt) + ", " + pts(1,cnt)
loop
; mes "Tri:" + objTri(0) + ", " + objTri(1) + ", " + objTri(2)
; mes "Line:" + objLine(0) + ", " + objLine(1)
redraw 1
return
;----------------------------
;
; 頂点作成
;
*l_make_pts
randomize
repeat 5
pts(0, cnt) = rnd(ginfo_winx), rnd(ginfo_winy)
loop
return
#endif
;#####################################################################
解説
今回は三角形と線分なので分離超平面は、線分に沿ったもの、三角形の各辺に沿ったものの４つが考えられます。
なので分離軸も４つ。各線に垂直なものを想定しました。
後は内積で投影して適当に判定しました。
もっと効率的な判定方法があるかもしれませんがこれが私の精一杯。（´・ω・｀）
ライセンス
NYSLです。
サンプルもモジュールも好きに使って下さい。