線分と三角形の衝突判定

概要

分離軸判定という方法を用いた衝突判定を行います。
詳しい解説はこちらのサイトを御覧ください。
マルペケつくろーどっとコム - その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は三角形の3頂点の頂点番号が入った配列変数です。順番はどちら周りでも関係ありません。
;
;線分と三角形が衝突していた場合、statに結果を返します。
;	stat = 0:衝突していない
;	stat = 1:衝突している
;
#deffunc IsColLineTri array pts, array lp, array tp
	;分離軸を用いて衝突しないケースを探します。
	;1つでも衝突しないケースが見つかった場合、衝突していないと判定します。

	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
;#####################################################################

解説

今回は三角形と線分なので分離超平面は、線分に沿ったもの、三角形の各辺に沿ったものの4つが考えられます。
なので分離軸も4つ。各線に垂直なものを想定しました。

後は内積で投影して適当に判定しました。
もっと効率的な判定方法があるかもしれませんがこれが私の精一杯。(´・ω・`)

ライセンス

NYSLです。
サンプルもモジュールも好きに使って下さい。

関連記事

  1. d2cモジュール 前の画像 次の画像 ダウンロード d2cモジュール Ver....
  2. 等速で移動する物体に当てる はじめに  先日実装したHSP3用モジュールの軌道予測関連命...
  3. d2cmでの影の作成 「影」とは  まずはじめに、ここで扱う「影」は便宜上、影っぽ...