::: <<Prev(001) | List | Next(003)>>

Tips 002
線と線の当たり判定(比較編)

Tips 001で紹介した方法以外の判定法


Lunaで用いられている判定法

世の中に数多存在するゲーム開発用ライブラリの中に、Lunaというものがあります。 こちらはワシがよく使っていたDXライブラリとは少々違い、DirectXを薄くラップしただけの低レベルインターフェイスを持つライブラリです。

で、そのライブラリにはLunaCollisionという衝突判定クラスがあり、その中で線と線の当たり判定が実装してありました。

なので、無謀にもワシのアルゴリズムと比較を行ってみました。

いきなり比較

以下の手順で行ってみました。

  1. VisualStudio 2003.net にて、比較用プロジェクトを作成。GUIなんか要らないのでコンソールで。
  2. LunaCollisionクラスの線分判定関数とその付随物を、別のヘッダファイル「LunaLine.h」として抽出。
  3. 線分データ型の座標をLuna側のfloat型にあわせる。
  4. ランダムな線分に対する判定を、それぞれ一千万回繰り返し、所要時間を計算するプログラムを作成。
  5. 最適化オプション「実行速度 (/O2)」でReleaseコンパイル、実行。

ちなみに、乱数生成アルゴリズムとして Mersenne Twister法を、 乱数のシード値として4992を使用しました。時間の計測には、WindowsのGetTickCount()関数を使いました。

で、結果です。

Base : 3285ms
Totoki : 4136ms(2313804 collisions)
Luna : 3836ms(2313804 collisions)

Baseってのは、判定を行わないランダム線分の生成のみの所要時間です。

はい、ごらんの通り見事に敗退しております。実質的な関数所要時間ではLuaCollisionはこちらの1.5倍の性能です。

やってる内容は・・・

//======================================================================
// 点(x,y)が直線分 l のどちら側にあるか調べる
// 直線分 l の右側にある場合 + を返す
// 直線分 l の直線上にある場合 0 を返す
// 直線分 l の左側にある場合 - を返す
//======================================================================
static inline float Side( float x, float y, LINE2D &l )
{
  return ( (x-l.a.x)*(y-l.b.y) - (y-l.a.y)*(x-l.b.x) );
}



//======================================================================
// 直線と直線
//======================================================================
bool LunaCollision::Line_Line( LINE2D &l1, LINE2D &l2 )
{
  static float n1, n2;

  //-------------------------------------------
  // l1 が l2 をまたいでいるか否か
  //-------------------------------------------
  n1 = Side( l2.a.x, l2.a.y, l1 );
  n2 = Side( l2.b.x, l2.b.y, l1 );
  float ret1 = (n1 * n2);

  //-------------------------------------------
  // l2 が l1 をまたいでいるか否か
  //-------------------------------------------
  n1 = Side( l1.a.x, l1.a.y, l2 );
  n2 = Side( l1.b.x, l1.b.y, l2 );
  float ret2 = (n1 * n2);

  return ((ret1<=0) && (ret2<=0) );
}

ソースコードを直接抜粋させていただきました。問題がありましたらご一報を。

はっきり言ってしまうと、コメントの通りです。

side関数はベクトルの外積を使って点が直線のどちら側にあるかを求めています。 それを直線の二点について行って、符号が異なっていれば(掛けて負ならば)その直線をまたいでいることになります。 で、さらにそれを両方の直線に関してチェックしてどちらもまたいでいれば線分は交わっている、というわけです。

・・・あれぇ、でも計算コストとしては大差はないような気がするんだけどなぁ。


著作権情報

今回引用したLunaのソースは、作者である葉迩倭さんに帰属します。

 DirectX Library "Luna for DirectX 9.0c"
 Copyright (C) 2003-2005 葉迩倭
 All rights reserved.

脚注

※ 低レベルというのはこの場合、よりDirectXの操作に近いという意味であって、 質が悪いという意味ではありません。結構わかりにくい言い回しですが、よくある言い方でもあります。

この記事にコメントをする

::: <<Prev(001) | List | Next(003)>>