From 33058f2b292b3a581333bdfb21b8f671898c5060 Mon Sep 17 00:00:00 2001 From: Peter Bengtsson Date: Tue, 8 Dec 2020 14:40:17 -0500 Subject: initial commit --- .../index.html | 176 +++++++++++++++++++++ .../techniques/3d_collision_detection/index.html | 155 ++++++++++++++++++ 2 files changed, 331 insertions(+) create mode 100644 files/ja/games/techniques/3d_collision_detection/bounding_volume_collision_detection_with_three.js/index.html create mode 100644 files/ja/games/techniques/3d_collision_detection/index.html (limited to 'files/ja/games/techniques/3d_collision_detection') diff --git a/files/ja/games/techniques/3d_collision_detection/bounding_volume_collision_detection_with_three.js/index.html b/files/ja/games/techniques/3d_collision_detection/bounding_volume_collision_detection_with_three.js/index.html new file mode 100644 index 0000000000..3a6bea3106 --- /dev/null +++ b/files/ja/games/techniques/3d_collision_detection/bounding_volume_collision_detection_with_three.js/index.html @@ -0,0 +1,176 @@ +--- +title: THREE.js によるバウンディングボリューム衝突検出 +slug: >- + Games/Techniques/3D_collision_detection/Bounding_volume_collision_detection_with_THREE.js +tags: + - 3D + - Games + - JavaScript + - WebGL + - bounding boxes + - collision detection + - three.js +translation_of: >- + Games/Techniques/3D_collision_detection/Bounding_volume_collision_detection_with_THREE.js +--- +
{{GamesSidebar}}
+ +

この記事では、Three.js ライブラリーを使用してバウンディングボックスとバウンディングスフィアの間の衝突検出を実装する方法を示します。 これを読む前に、まず 3D 衝突検出の紹介記事を読み、かつ Three.js に関する基本的な知識があることを前提としています。

+ +

Box3 と Sphere の使用

+ +

Three.js には、数学的なボリューム（mathematical volumes）と形状を表すオブジェクトがあります。 3D の AABB とバウンディングスフィアには、Box3 オブジェクトと Sphere オブジェクトを使用できます。 インスタンス化されると、他のボリュームに対して交差テストを実行するために使用できるメソッドがあります。

+ +

ボックスのインスタンス化

+ +

Box3 インスタンスを作成するには、ボックスの下と上の境界（対角線の2つの座標）を指定する必要があります。 通常、この AABB を 3D ワールドのオブジェクト（文字など）に「リンク」する必要があります。 Three.js では、Geometry インスタンスにオブジェクトの min と max の境界を持つ boundingBox プロパティがあります。 このプロパティを定義するには、事前に Geometry.computeBoundingBox を手動で呼び出す必要があることに注意してください。

+ +
var knot = new THREE.Mesh(
+  new THREE.TorusKnotGeometry(0.5, 0.1),
+  new MeshNormalMaterial({}));
+
+knot.geometry.computeBoundingBox();
+var knotBBox = new Box3(
+  knot.geometry.boundingBox.min,
+  knot.geometry.boundingBox.max);
+
+ +
+

注: boundingBox プロパティは、Mesh ではなく、Geometry 自体を参照として使用します。 したがって、Mesh に適用された拡大縮小、位置などの変換は、計算するボックスの計算では無視されます。

+
+ +

前の問題を修正するより簡単な代替方法は、後で Box3.setFromObject を使用してこれらの境界を設定することです。 これにより、3D エンティティの変換と子メッシュも考慮して寸法が計算されます。

+ +
var knot = new THREE.Mesh(
+  new THREE.TorusKnotGeometry(0.5, 0.1),
+  new MeshNormalMaterial({}));
+
+var knotBBox = new Box3(new THREE.Vector3(), new THREE.Vector3());
+knotBBox.setFromObject(knot);
+ +

球のインスタンス化

+ +

Sphere オブジェクトのインスタンス化も同様です。 球の中心と半径を指定する必要があります。 これらは、Geometry で使用可能な boundingSphere プロパティで追加できます。

+ +
var knot = new THREE.Mesh(
+  new THREE.TorusKnotGeometry(0.5, 0.1),
+  new MeshNormalMaterial({}));
+
+var knotBSphere = new Sphere(
+  knot.position,
+  knot.geometry.boundingSphere.radius);
+
+ +

残念ながら、Sphere インスタンスに Box3.setFromObject に相当するものはありません。 したがって、変換を適用したり、Mesh の位置を変更したりする場合は、バウンディングスフィアを手動で更新する必要があります。 例えば次のようにです。

+ +
knot.scale.set(2, 2, 2);
+knotBSphere.radius = knot.geometry.radius * 2;
+
+ +

交差テスト

+ +

点 対 Box3 / Sphere

+ +

Box3 と Sphere の両方に、このテストを実行するための containsPoint メソッドがあります。

+ +
var point = new THREE.Vector3(2, 4, 7);
+knotBBox.containsPoint(point);
+ +

Box3 対 Box3

+ +

Box3.intersectsBox メソッドは、このテストを実行するために使用できます。

+ +
knotBbox.intersectsBox(otherBox);
+ +
+

注: これは、Box3 が別のものを完全に包んでいるかどうかをチェックする Box3.containsBox メソッドとは異なります。

+
+ +

Sphere 対 Sphere

+ +

前のものと同様の方法で、このテストを実行するための Sphere.intersectsSphere メソッドがあります。

+ +
knotBSphere.intersectsSphere(otherSphere);
+ +

Sphere 対 Box3

+ +

残念ながら、このテストは Three.js には実装されていませんが、Sphere にパッチを適用して球対 AABB の交差アルゴリズムを実装できます。

+ +
// THREE.js の Sphere を展開して、対 Box3 衝突テストをサポートします。
+// チェックのたびに Vector3 の新しいインスタンスが生成されないように、
+// メソッドスコープ外でベクターを作成しています。
+
+THREE.Sphere.__closest = new THREE.Vector3();
+THREE.Sphere.prototype.intersectsBox = function (box) {
+    // get box closest point to sphere center by clamping
+    THREE.Sphere.__closest.set(this.center.x, this.center.y, this.center.z);
+    THREE.Sphere.__closest.clamp(box.min, box.max);
+
+    var distance =  this.center.distanceToSquared(THREE.Sphere.__closest);
+    return distance < (this.radius * this.radius);
+};
+ +

デモ

+ +

これらの手法を示すために、いくつかのライブデモと、調べるためのソースコードを用意しました。

+ + + +

+ +

BoxHelper の使用

+ +

生の Box3 オブジェクトと Sphere オブジェクトを使用する代わりに、Three.js には、バウンディングボックスの処理を容易にする便利なオブジェクト BoxHelper があります（以前の BoundingBoxHelper は非推奨となりました）。 このヘルパーは Mesh を取り、そのバウンディングボックスのボリューム（子メッシュを含む）を計算します。 これにより、バウンディングボックスを表す新しいボックスの Mesh が作成されます。 これは、バウンディングボックスの形状を示し、Mesh と一致するバウンディングボックスを作成するために、前に見た setFromObject メソッドに渡すことができます。

+ +
+

BoxHelper は、Three.js のバウンディングボリュームとの 3D 衝突を処理するための推奨される方法です。 球のテストをもらすことになりますが、このトレードオフにはそれだけの価値があります。

+
+ +

このヘルパーを使用する利点は次のとおりです。

+ + + +

主な欠点は、ボックスのバウンディングボリュームのみを作成することです。 したがって、球対 AABB のテストが必要な場合は、独自の Sphere オブジェクトを作成する必要があります。

+ +

これを使用するには、新しい BoxHelper インスタンスを作成し、ジオメトリーと、オプションで、ワイヤーフレームマテリアルに使用する色を指定する必要があります。 また、新しく作成したオブジェクトをレンダリングするには、three.js のシーンに追加する必要があります。 シーン変数は単に scene と呼ばれると仮定します。

+ +
var knot = new THREE.Mesh(
+  new THREE.TorusKnotGeometry(0.5, 0.1),
+  new THREE.MeshNormalMaterial({})
+);
+var knotBoxHelper = new THREE.BoxHelper(knot, 0x00ff00);
+scene.add(knotBoxHelper);
+ +

実際の Box3 バウンディングボックスも作成するために、新しい Box3 オブジェクトを作成し、BoxHelper の形状と位置を想定します。

+ +
var box3 = new THREE.Box3();
+box3.setFromObject(knotBoxHelper);
+ +

Mesh の位置、回転、拡大縮小などを変更する場合は、update() メソッドを呼び出して、BoxHelper インスタンスがリンクした Mesh と一致するようにする必要があります。 Box3 を Mesh に従わせるには、setFromObject を再度呼び出す必要もあります。

+ +
knot.position.set(-3, 2, 1);
+knot.rotation.x = -Math.PI / 4;
+// update the bounding box so it stills wraps the knot
+knotBoxHelper.update();
+box3.setFromObject(knotBoxHelper);
+ +

衝突テストの実行は、上記のセクションで説明したのと同じ方法で実行します。 つまり、Box3 オブジェクトを上記と同じ方法で使用します。

+ +
// box vs box
+box3.intersectsBox(otherBox3);
+// box vs point
+box3.containsPoint(point.position);
+ +

デモ

+ +

ライブデモのページで確認できる2つのデモがあります。 1つ目は、BoxHelper を使用した点対ボックスの衝突を示しています。 2つ目は、ボックス対ボックスのテストを実行します。

+ +

diff --git a/files/ja/games/techniques/3d_collision_detection/index.html b/files/ja/games/techniques/3d_collision_detection/index.html new file mode 100644 index 0000000000..d17e0d1acc --- /dev/null +++ b/files/ja/games/techniques/3d_collision_detection/index.html @@ -0,0 +1,155 @@ +--- +title: 3D 衝突検出 +slug: Games/Techniques/3D_collision_detection +tags: + - 3D + - Games + - JavaScript + - bounding boxes + - collision detection +translation_of: Games/Techniques/3D_collision_detection +--- +
{{GamesSidebar}}
+ +

この記事では、3D 環境で衝突検出を実装するために使用されるさまざまなバウンディングボリューム手法の概要を説明します。 追求記事では、特定の 3D ライブラリでの実装について説明します。

+ +

座標軸に沿ったバウンディングボックス

+ +

2D 衝突検出と同様に、座標軸に沿ったバウンディングボックス（axis-aligned bounding boxes、AABB）は、2つのゲームエンティティがオーバーラップしているかどうかを判断するための最も速いアルゴリズムです。 これは、ゲームエンティティを回転しない（つまり座標軸に沿った）ボックスで包み、3D 座標空間でこれらのボックスの位置をチェックして、それらが重なっているかどうかを確認することで構成されます。

+ +

+ +

パフォーマンス上の理由から、座標軸に沿った拘束（axis-aligned constraint）があります。 回転しない2つのボックス間の重複領域は、論理比較のみで確認できますが、回転するボックスには追加の三角関数操作が必要であり、計算に時間がかかります。 回転するエンティティがある場合は、バウンディングボックスの寸法を変更してオブジェクトを包むか、球（回転に対して不変）などの別のバウンディングジオメトリータイプを使用することを選択できます。 以下のアニメーション GIF は、回転するエンティティに合うようにサイズを調整する AABB の図形例を示しています。 ボックスは常に寸法を変更して、内部に含まれるエンティティにぴったりとフィットします。

+ +

+ +
+

注: この手法の実際の実装については、Three.js を使用したバウンディングボリュームの記事を確認してください。

+
+ +

点 対 AABB

+ +

点が AABB 内にあるかどうかを確認するのは非常に簡単です。 点の座標が、AABB 内にあるかどうかを確認する必要があります。 各座標軸を個別に検討します。 Px、Py、Pz を点の座標、BminX–BmaxX、BminY–BmaxY、BminZ–BmaxZ を AABB の各座標軸の範囲とすると、次の式を使用して、2つの間で衝突が発生したかどうかを計算できます。

+ +

f(P,B)=(Px>=BminX∧Px<=BmaxX)∧(Py>=BminY∧Py<=BmaxY)∧(Pz>=BminZ∧Pz<=BmaxZ)f(P,B)= (P_x >= B_{minX} \wedge P_x <= B_{maxX}) \wedge (P_y >= B_{minY} \wedge P_y <= B_{maxY}) \wedge (P_z >= B_{minZ} \wedge P_z <= B_{maxZ})

+ +

あるいは、JavaScript では、次のようになります。

+ +
function isPointInsideAABB(point, box) {
+  return (point.x >= box.minX && point.x <= box.maxX) &&
+         (point.y >= box.minY && point.y <= box.maxY) &&
+         (point.z >= box.minZ && point.z <= box.maxZ);
+}
+ +

AABB 対 AABB

+ +

AABB が別の AABB と交差するかどうかのチェックは、点のテストと同様です。 ボックスの境界を使用して、座標軸ごとに1つのテストを実行する必要があります。 次の図は、X 軸上で実行するテストを示しています。 基本的には、AminX–AmaxX と BminX–BmaxX の範囲は重複しているかです。

+ +

updated version

+ +

数学的には、これは次のようになります。

+ +

f(A,B)=(AminX<=BmaxX∧AmaxX>=BminX)∧(AminY<=BmaxY∧AmaxY>=BminY)∧(AminZ<=BmaxZ∧AmaxZ>=BminZ)f(A,B) =

+ +

そして、JavaScript では、これを使用します。

+ +
function intersect(a, b) {
+  return (a.minX <= b.maxX && a.maxX >= b.minX) &&
+         (a.minY <= b.maxY && a.maxY >= b.minY) &&
+         (a.minZ <= b.maxZ && a.maxZ >= b.minZ);
+}
+
+ +

バウンディングスフィア

+ +

バウンディングスフィア（bounding spheres）を使用して衝突を検出することは、AABB よりも少し複雑ですが、それでもテストはかなり迅速です。 球の主な利点は、回転に対して不変であるため、包まれたエンティティが回転しても、バウンディングスフィアは同じままであるということです。 主な欠点は、包んでいるエンティティが実際に球形でない限り、包むのは通常適切ではないことです（つまり、バウンディングスフィアで人を包むと、多くの誤検知が発生しますので、AABB の方が適しています）。

+ +

点 対 球

+ +

球に点が含まれているかどうかを確認するには、点と球の中心との間の距離を計算する必要があります。 この距離が球の半径以下の場合、点は球の内側にあります。

+ +

+ +

2つの点 A と B の間のユークリッド距離が (Ax-Bx)2)+(Ay-By)2+(Az-Bz)\sqrt{(A_x - B_x) ^ 2) + (A_y - B_y)^2 + (A_z - B_z)} であることを考慮すると、点対球の衝突検出の式は次のようになります。

+ +

f(P,S)=Sradius>=(Px-Sx)2+(Py-Sy)2+(Pz-Sz)2f(P,S) = S_{radius} >= \sqrt{(P_x - S_x)^2 + (P_y - S_y)^2 + (P_z - S_z)^2}

+ +

あるいは、JavaScript では、次のようになります。

+ +
function isPointInsideSphere(point, sphere) {
+  // Math.pow を呼び出すよりも高速であるため、乗算を使用しています
+  var distance = Math.sqrt((point.x - sphere.x) * (point.x - sphere.x) +
+                           (point.y - sphere.y) * (point.y - sphere.y) +
+                           (point.z - sphere.z) * (point.z - sphere.z));
+  return distance < sphere.radius;
+}
+
+ +
+

上記のコードは平方根を特徴としており、計算にコストがかかる可能性があります。 これを回避する簡単な最適化は、距離の2乗と半径の2乗を比較することで構成されているため、最適化された方程式には、代わりに distanceSqr < sphere.radius * sphere.radius が含まれます。

+
+ +

球 対 球

+ +

球対球のテストは、点対球のテストに似ています。 ここでテストする必要があるのは、球の中心間の距離がそれらの半径の合計以下であることです。

+ +

+ +

数学的には、これは次のようになります。

+ +

f(A,B)=(Ax-Bx)2+(Ay-By)2+(Az-Bz)2<=Aradius+Bradiusf(A,B) = \sqrt{(A_x - B_x)^2 + (A_y - B_y)^2 + (A_z - B_z)^2} <= A_{radius} + B_{radius}

+ +

あるいは、JavaScript では、次のようになります。

+ +
function intersect(sphere, other) {
+  // Math.pow を呼び出すよりも高速であるため、乗算を使用しています
+  var distance = Math.sqrt((sphere.x - other.x) * (sphere.x - other.x) +
+                           (sphere.y - other.y) * (sphere.y - other.y) +
+                           (sphere.z - other.z) * (sphere.z - other.z));
+  return distance < (sphere.radius + other.radius);
+}
+ +

球 対 AABB

+ +

球と AABB が衝突しているかどうかのテストは少し複雑ですが、それでも単純で高速です。 論理的なアプローチは、AABB のすべての頂点をチェックし、それぞれに対して点対球のテストを実行することです。 ただし、これはやり過ぎです。 AABB の最も近い点（必ずしも頂点である必要はありません）と球の中心との間の距離を計算して、球の半径以下であるかどうかを確認するだけで済むため、すべての頂点をテストする必要はありません。 この値は、球の中心を AABB の限界にクランプすることで取得できます。

+ +

+ +

JavaScript では、次のようにこのテストを行います。

+ +
function intersect(sphere, box) {
+  // クランプして球の中心からボックスの最も近い点を取得します
+  var x = Math.max(box.minX, Math.min(sphere.x, box.maxX));
+  var y = Math.max(box.minY, Math.min(sphere.y, box.maxY));
+  var z = Math.max(box.minZ, Math.min(sphere.z, box.maxZ));
+
+  // これは isPointInsideSphere と同じです
+  var distance = Math.sqrt((x - sphere.x) * (x - sphere.x) +
+                           (y - sphere.y) * (y - sphere.y) +
+                           (z - sphere.z) * (z - sphere.z));
+
+  return distance < sphere.radius;
+}
+
+ +

物理エンジンの使用

+ +

3D 物理エンジン（3D physics engines）は、衝突検出アルゴリズムを提供していますが、そのほとんどは、バウンディングボリュームにも基づいています。 物理エンジンが機能する方法は、通常はその視覚的表現に付属した物理的なボディ（physical body）を作成することです。 このボディには、速度、位置、回転、トルクなどのプロパティと、物理的な形状（physical shape）があります。 この形状は、衝突検出の計算で考慮されるものです。

+ +

このような手法が実際に動作していることを確認できるライブ衝突検出デモ（ソースコード付き）を用意しました。 これは、オープンソースの 3D 物理エンジン cannon.js を使用しています。

+ +

関連情報

+ +

MDN の関連記事

+ + + +

外部リソース

+ + -- cgit v1.2.3-54-g00ecf