Lameije Corporation

ナビゲーションメッシュによる3D環境内の移動

概要

3Dで作成された環境内の移動を行うために使用するナビゲーションメッシュの説明です。

ナビゲーションデータの作成

ナビゲーションメッシュは、オブジェクトが移動可能な場所のみを表したポリゴンモデルをベースとしており、デモではそのポリゴンモデルから、専用のナビゲーションデータを作成しています。

図1のスクリーンショットは、デモで使用したナビゲーションメッシュのポリゴンモデルを自社専用ツールに取り込み、表示させたものです。図2はそのナビゲーションメッシュを使用して実際に移動する3Dマップのモデルです。

(図1)

(図2)

ナビゲーションメッシュ（図1）の緑色で表示されている辺は、隣のポリゴン（以降セルを呼びます）と接続している事を表しており、紫の辺はその移動可能な隣接するセル同士の中点を結んで表示したものです。白い辺は壁ですのでそこから先へは移動できません。

ナビゲーションメッシュを作成する際には、移動可能なセル同士の接続に図3のようなルールがあります。

(図3)

左側のポリゴンのように、移動可能な隣接するセルの辺は同じ頂点を共有している必要があります。共有していなくてもほぼ同じ位置である必要があります（このあたりのさじ加減は、ナビゲーションデータを作成するツールの仕様によります）。右側のポリゴンのように、セルが重なっていたり、頂点を共有していなかったり、頂点は共有していても面が裏返っていたりしてはいけません。

ナビゲーションメッシュのモデルを作成したら、実際にナビゲーションデータに変換します。ナビゲーションデータは、全てのセルの位置と、移動可能なセル同士の接続を調べて保存した独自フォーマットのデータファイルです。ゲームでは、このナビゲーションデータファイルを読み込んで使用します。ナビゲーションメッシュのポリゴンモデルをそのまま使用しても一応実現はできますが、毎回ポリゴンモデルからセル同士の接続を調べていては動作が遅いので、専用のナビゲーションデータに変換した方が速度面でも現実的です。ナビゲーションデータの作成例はナビゲーションデータの作成に記述されています。

オブジェクトの配置

ナビゲーションデータを作成したら、実際にオブジェクトをセル上に配置します。オブジェクトを初期位置に配置する際には、初期位置の座標を元に乗っているセルを探します。

ある点がセルの内部にあるかどうか調べるために、まずはセルの座標を三次元座標からXZ平面の二次元座標に変換し（Y座標を取るだけ）、各辺の法線をセルの内部を向くように計算しておきます(図4)。この処理は、ナビゲーションデータ作成時に行って、データファイルに保存しておいても良いでしょう。

(図4)

それぞれの法線は、次のように計算できます。

D3DXVECTOR2 vec2V0;         //V0のXZ平面の座標
D3DXVECTOR2 vec2V1;         //V1のXZ平面の座標
D3DXVECTOR2 vec2V2;         //V2のXZ平面の座標
D3DXVECTOR2 vec3Normal0;    //N0
D3DXVECTOR2 vec3Normal1;    //N1
D3DXVECTOR2 vec3Normal2;    //N2

//N0を計算
vec3Normal0.x = vec2V1.y - vec2V0.y;
vec3Normal0.y = -(vec2V1.x - vec2V0.x);
D3DXVec2Normalize(&vec3Normal0, &vec3Normal0);

//N1を計算
vec3Normal1.x = vec2V2.y - vec2V1.y;
vec3Normal1.y = -(vec2V2.x - vec2V1.x);
D3DXVec2Normalize(&vec3Normal1, &vec3Normal1);

//N2を計算
vec3Normal2.x = vec2V0.y - vec2V2.y;
vec3Normal2.y = -(vec2V0.x - vec2V2.x);
D3DXVec2Normalize(&vec3Normal2, &vec3Normal2);

各辺の法線が計算できたら、調べたい点と各辺の法線との位置関係を、内積使って調べれば内部にあるかどうかわかります。図5のP0のように内積の結果（青いライン）が全て正の値ならば、セルの内部にあるという事になります。 P1のように一つでも内積の結果（緑のライン）が負の値（緑の破線）があれば、セルの内部には無いという事になります。このとき、調べたい点もXZ平面の二次元座標に変換しておきます。

(図5)

具体的には次のようなコードで、調べたい点がセルの内部にあるかどうかチェックします。

D3DXVECTOR2 vec2Pos;        //調べたい点のXZ平面の座標
D3DXVECTOR2 vec2V0;         //V0のXZ平面の座標
D3DXVECTOR2 vec2V1;         //V1のXZ平面の座標
D3DXVECTOR2 vec2V2;         //V2のXZ平面の座標
D3DXVECTOR2 vec3Normal0;    //N0
D3DXVECTOR2 vec3Normal1;    //N1
D3DXVECTOR2 vec3Normal2;    //N2
float fDot;                 //内積結果
int iInside = 0;            //内積結果が正だった数

//N0との位置関係を計算
fDot = D3DXVec2Dot(&vec3Normal0, &(vec2Pos - vec2V0));
if(fDot > 0.0f){
    ++iInside;
}

//N1との位置関係を計算
fDot = D3DXVec2Dot(&vec3Normal1, &(vec2Pos - vec2V1));
if(fDot > 0.0f){
    ++iInside;
}

//N2との位置関係を計算
fDot = D3DXVec2Dot(&vec3Normal2, &(vec2Pos - vec2V2));
if(fDot > 0.0f){
    ++iInside;
}

//結果を確認
if(iInside == 3){
    //セルの内部にある
    //...
}
else{
    //セルの内部にない
    //...
}

これでオブジェクトの乗っているセルが分かったわけですが、ここでひとつ注意があります。ナビゲーションメッシュにオーバーハングしている部分があると、XZ平面で調べているため、これだけではオブジェクトの乗っているセルが複数出てきてしまう可能性があり、1つには確定できません。ですので、ナビゲーションメッシュにオーバーハングしている部分がある場合は、調べたい点と一番近いセルを見つける必要があります。これは、セルの中点と調べたい点との距離を三次元座標で測り、一番近いセルを選択すれば良いでしょう。

オブジェクトの乗っているセルが分かったら、セルの上に乗せるわけですが、実際に乗せる座標のXZ座標はオブジェクトの初期位置として指定された座標をそのまま使用しますが、 Y座標はきちんとセルの上に乗るように計算します。指定される初期位置のY座標がぴったりセルの上に乗る座標ならばこのような計算をする事もありませんが、アバウトな指定がされた時と、しっかりとセルの上に乗せるという意味も含めて、ここではY座標の計算を行います。また、セル上のY座標の計算は、オブジェクトをナビゲーションメッシュに合わせて移動する際にも使用します。

同じような理由から、XZ座標もアバウトな値で指定された場合、どのセル内にも初期位置が無いという事もあります。その場合は、一番近いセルの内部に初期位置を移動するなどの処理が別途必要になりますが、ここではXZ座標は必ずどこかのセル内にあると仮定して、この処理は行いません。

セル上のY座標は、乗っているセルの平面方程式から簡単に計算できます。平面を(a, b, c, d)とすると平面方程式は、

ax + by + cz + d = 0

ですから、これを展開して、

y = -(ax + cz + d) / b

になります。これを踏まえて、オブジェクトの乗っているY座標を計算します。

D3DXVECTOR3 vec3InitPos;     //オブジェクトの初期座標
D3DXVECTOR3 vec3V0;          //V0の三次元座標
D3DXVECTOR3 vec3V1;          //V1の三次元座標
D3DXVECTOR3 vec3V2;          //V2の三次元座標
D3DXVECTOR3 vec3V1V0;        //V1-V0の方向
D3DXVECTOR3 vec3V2V0;        //V2-V0の方向
D3DXVECTOR3 vec3CellNormal;  //セルの法線
D3DXPLANE plnCellPlane;      //セルの平面

//セルの法線を計算
D3DXVec3Normalize(&vec3V1V0, &(vec3V1 - vec3V0));
D3DXVec3Normalize(&vec3V2V0, &(vec3V2 - vec3V0));
D3DXVec3Cross(&vec3CellNormal, &vec3V1V0, &vec3V2V0);

//平面を求める
plnCellPlane.a = vec3CellNormal.x;
plnCellPlane.b = vec3CellNormal.y;
plnCellPlane.c = vec3CellNormal.z;
vec3CellNormal = -vec3CellNormal;
plnCellPlane.d = D3DXVec3Dot(&vec3CellNormal, &vec3V0);

//平面から点のY座標を計算
vec3InitPos.y = -((plnCellPlane.a * vec3InitPos.x) + (plnCellPlane.c * vec3InitPos.z) + plnCellPlane.d)
                     / plnCellPlane.b;

これで、オブジェクトを最初に配置する座標が分かったので、その座標にオブジェクトを置きます。

オブジェクトの移動

オブジェクトの配置ができたら、ナビゲーションメッシュに合わせてオブジェクトを移動してみます。オブジェクトを移動するには、現在の位置（開始点）と新しい位置（終着点）を使います（以降、現在の位置から新しい位置までの動きをモーションと呼びます）。

終着点は、この時点ではナビゲーションのセルの内部にあるかどうかは気にする必要はなく、単純に移動したい位置を指定します。モーションは開始点から終着点へ向かって、セルの繋がりを見ながらナビゲーション内を移動させて行きます。このとき、オブジェクトの配置で行ったのと同じように、各座標をXZ平面の二次元座標に変換して計算します。

図6のようにモーションの開始点をP0、終着点をP1とします。まず、現在のセルはCell0だとわかっているはずですので、P0からP1へ移動する際にCell0のどの辺を通過するかを調べます。これは、オブジェクトの配置でも行った、辺と点との位置関係を使えばわかります。

(図6)

辺を通過しているという事は、P1が辺の法線とは逆方向にあるということになりますので、Cell0の各辺の法線とP1-V0の内積が負の値の時には、モーションがその辺を通過しているかもしれないということになります。かもしれないというのは、これだけでは辺をただの直線としか見ていないため、辺の法線とは逆方向に点があることが分かっても、実際に辺を通過しているかどうかはわかりません。

例えば図7のように、線分P0P1は辺L1を通過していますが、辺の法線と逆方向であることだけで調べると、辺L0と辺L1の両方の外側にあることになります。

(図7)

辺の法線との内積結果を見るのは、複雑な計算を行う前の第一段階のテストです。このテストをパスした場合には、本当に辺を通過しているかどうか、線分と線分の交差判定を行って調べます。

線分の交差判定には様々な方法があるかと思いますが、ここでは線分の交差を、図8・図9のように平行四辺形の面積を使って判定します。同時に交点も求まります。P0P1はモーションの線分、V0V1は辺の線分です。

緑色で塗りつぶした部分は、モーションと辺の線分を少し移動して考えてみるとわかると思いますが、 P0P1とV0V1で構成される平行四辺形の面積です。この面積は、ベクトルの外積の大きさはその2つのベクトルで構成される平行四辺形の面積と等しいことから、 P1-P0ベクトルとV1-V0ベクトルの外積で計算できます。

次に、どの位置で線分が交差しているのかを調べるために、先ほどと同じ方法でV0P0とV0V1で構成される平行四辺形の面積を計算します。この面積は、図9の紫色で塗りつぶした部分になります。

(図8)

(図9)

ここで、緑色の部分と紫色の部分を重ねてみます。図10の①と②の部分の面積は同じですので、移動して図11のように考えます。

(図10)

(図11)

ここまで出来たら交点の計算は簡単です。P1-P0ベクトルがV1-V0ベクトルと交差する位置は、先ほど計算した2つの平行四辺形の面積比率と同じ比率で分断されている事が図11より分かります。 P1-P0ベクトルをVecP1P0、緑色の平行四辺形の面積をArea1、紫色の平行四辺形の面積をArea2とすると、交点Intersectionは次の式で求めることができます（Normalはベクトルの正規化、Lengthはベクトルの長さを求める関数です）。

Intersection = P0 + Normal(VecP1P0) * (Length(VecP1P0) * (Area2 / Area1))

しかし、まだこの時点では直線上での交点が分かっただけですので、線分同士の交差判定が必要です。判定を行う前に、まず紫色の平行四辺形の面積を計算した時と同じ方法で、V0P0とP0P1で構成される平行四辺形の面積を計算し、図12のように考えます。

(図12)

この水色の平行四辺形の面積をArea3とすると、線分P0P1と線分V0V1の関係は、次のように考えることができます。

Area1が0.0の時、P0P1とV0V1は平行です。
Area1が0.0かつArea2が0.0の時、P0P1とV0V1は平行かつオーバーラップして（重なって）います。
Area2がArea1以下かつArea3がArea1以下の時、線分P0P1と線分V0V1は交差しています。
Area2がArea1より大きく、Area3がArea1以下の時、線分V0V1はP0,P1を通る直線と交差します。
Area2がArea1以下で、Area3がArea1より大きい時、線分P0P1はV0,V1を通る直線と交差します。
上記の全ての条件に当てはまらない時、P0,P1を通る直線とV0,V1を通る直線は交差します。

これらの関係を、簡単に条件分岐で書いてみると以下のようになります。 Area2とArea1の比率(Area2 / Area1)をFactorP、Area3とArea1の比率(Area3 / Area1)をFactorVとします。

if(Area1 == 0.0){
    if(Area2 == 0.0){
        //P0P1とV0V1は平行かつオーバーラップして（重なって）いる
    }
    else{
        //P0P1とV0V1は平行
    }
}
else{
    if((FactorP > 0.0) && (FactorP <= 1.0) && (FactorV >= 0.0) && (FactorV <= 1.0)){
        //線分は交差している
    }
    else if((FactorV >= 0.0) && (FactorV <= 1.0)){
        //線分V0V1はP0,P1を通る直線により交差する
    }
    else if((FactorP >= 0.0) && (FactorP <= 1.0)){
        //線分P0P1はV0,V1を通る直線により交差する
    }
    else{
        //P0,P1を通る直線と、V0,V1を通る直線は交差する
    }
}

このように同時に様々な交差判定結果がわかりますが、今回は線分同士の交差判定が行えれば良いので、そこに着目してモーションの通過する辺を確定します。通過する辺が分かったら、モーションと辺の交点で開始点（P0）を更新し、通過する辺と隣接するセルがあるかどうか調べて、隣接セルがある場合はそのセルに移動し（図6の場合Cell1へ移動）、今度はそのセルのどの辺を通過するのかを調べて行きます。

この作業を、モーションの終着点に到達するまで繰り返します。モーションの終着点に到達したかどうかは、オブジェクトの配置でも行ったように、セルの全ての辺の法線と終着点との位置関係を内積で調べ、結果が全て正になればそのセル内部に終着点があることになり、目的のセルへ到達したことになります。

目的のセルへ到達したら、XZ平面で計算を行っていたので、到達したセルの平面方程式と終着点のXZ座標からY座標を再計算し三次元座標に戻します。あとは、その位置にオブジェクトを置けば、無事にナビゲーションメッシュでの移動は完了です。

もし、終着点に到達する前に隣接するセルがなくなってしまった場合は、壁に衝突したことになるので、衝突した点でとめたり、跳ね返らせたり、壁に合わせてずったりして補正をしてください。補正方法はゲームの仕様によって様々ですので、何が最適かというのはありません。

モーションをナビゲーションメッシュを元に移動させる一連の流れを仮想言語で書くと次のようになります。

P0                //モーションの開始点
P1                //モーションの終着点
CellVertex[3]     //セルのXZ平面での頂点座標
LineNormal[3]     //セルの各辺の法線
Inside            //終着点がセルの内部にあるかどうかのカウント用

loop{
    Inside = 0
    for(i = 0; i <= 2; ++i){
        if(dot(P1 - CellVertex[i], LineNormal[i]) < 0.0){
            if(線分P0P1と線分CellVertex[(i + 1) % 3]CellVertex[i]が交差した){
                if(隣接セルがある){
                    隣のセルに移動
                    CellVertex = 隣のセルの頂点
                    P0 = 線分P0P1と線分CellVertex[(i + 1) % 3]CellVertex[i]の交点
                    break;
                }
                else{
                    壁に衝突
                    break;
                }
            }
        }
        else{
            ++Inside
        }
    }

    if(Inside == 3){
        終着点に到着
        break;
    }
    else if(壁に衝突した){
        衝突の補正をする
        P1 = 補正後の座標
        break;
    }
}

P1.y = 最終セルの平面方程式とP1のXZ平面の座標からY座標を計算
移動終了（P1が実際の終着点）

サンプルプログラム(実行ファイルのみ)

ダウンロード | 2008年5月30日更新 | 584 KB(598,426 バイト)
MD5： 16e1b6070f313b3961e062bb7cd627ad

DirectXエンドユーザーランタイムは、Microsoft の [ DirectX ダウンロード ] のページからダウンロードできます。

最後に

ナビゲーションメッシュを駆使すれば、複雑な地形の移動も容易に行えるようになります。実際のソースコードはあまり記述しませんでしたが、いろいろと工夫して最適化を行えばかなり高速に処理が行えます。

例えば、平行四辺形の面積を出す時に外積を利用しましたが、実際の面積は外積の大きさを求めなければなりませんが、全ての平行四辺形で条件は同じなので、わざわざ大きさを計算し直さなくても、外積を計算して出てきた値のみを利用すれば済みます（XZ平面に変換して計算しているので、外積の結果もY成分だけ見れば良い）。

誤りなどを見つけましたら、ご連絡ください。

(文： 2008/5/27 ラメイジュ田中)

(修正： 2008/7/2 誤字修正)

(追記： 2008/8/6 ナビゲーションデータの作成へのリンクを追加)

この文章は、予告なく改編される場合がございます。

この文章の無断での転用を禁止いたします。

このページへのリンクは大歓迎です。

■ 参考文献

「Game Programming Gems 日本語版」　編者：Mark DeLoura　翻訳：狩野智英、川西裕幸