unity-任意の座標がオブジェクトの内部にあるかどうか調べる処理で軽い方法を知りたい

Question

指定した座標がオブジェクトの内部なのか外部なのか調べたいです。

realsenceD435を使って障害物検知と回避をしようとしているのですが、まずは一定の範囲内に障害物があるかどうかを判定する部分を作ろうとしています。

そこで、一定の範囲はオブジェクトを配置することで設定し、realsenceから取得したvector3の各データの座標に対してオブジェクト内部か外部かの判定をしようと考えました。
オブジェクトを範囲とすることで感覚的にその範囲を変更出来るのでそうしました。現在は円柱Cylinderオブジェクトの範囲で実現したいと考えています。

まずは、「ClosestPoint」で実現させようとしました。数点のデータなら問題なく実現できたのですが、460x640個のpointに対して全て実行すると重すぎで使い物になりません。
そこで次に、「raycast」でやってみようかと考えたのですがこの処理は重いので沢山使うのは良くないとの情報が多く出たので別の方法を探しているところです。
よろしくお願いします。

「ClosestPoint」の使用部分のコードは以下です。

                        var collider = checkarea.GetComponent<Collider>();
                        for (int i = 0; i < mesh.vertices.Length; i = i + 100000) {
                            if (collider.ClosestPoint(mesh.vertices[i]) == mesh.vertices[i])
                            {
                                // コライダーの中にある
                                Debug.Log("inside!!!!");
                                break;
                            }
                            else
                            {
                                // コライダーの外にある
                                //Debug.Log("outside");
                            }
                        }

Comments

[ganta7188]

アドバイス的なことだけになってしまいますが、
・当たり判定を、コライダーを使わず計算でやってみる
（球の当たり判定なら２点の距離だけで判定できる）
・pointの数を間引いてみる
・マルチスレッドにして複数のCPUで距離の計算をする
・GPGPU（コンピュートシェーダーを使ってGPUに距離の更新計算をさせる）
などが考えられます。自分も詳しくはないのでとりあえずの方向だけ・・・。GPU使えれば一番早くなるとは思います。

[masa246]

アドバイスありがとうございます！
コライダーを使わないで距離計算だけでしようかとも考えたのですが、判定範囲を柔軟に簡単に調整したくて避けていたところでした。
また、GPGPUをやったことがないのでこれを期に挑戦してみたいと思います。

Answer 1

簡単に試せて効果も大きいのはMesh.verticesの使用を控えることだろうと思います。
Mesh.verticesはただのフィールドのように見えるかもしれませんが、正体は「メッシュデータから頂点位置属性を抜き出して、新規配列に詰めて返す」といった動作をする重量級のプロパティのようです。ですのでご提示のコードのようにmesh.vertices[i]などとアクセスするのは、一つの頂点座標を得るために数十万個すべての頂点を取得してすぐ捨ててしまうというもったいない動作になってしまうかと思います。
verticesから頂点データを取ってくるのはループに入る前の1回だけにするのがいいでしょう。その頂点データ取得にしても、verticesから取ってくる代わりにGetVerticesを使ってもいいと思います。こちらは配列をいちいち生成せず、既存のList<Vector3>にデータを詰めてくれるのでもっと効率的になるはずです。

ganta7188さんからご指摘のあった「データの間引き」も組み合わせれば十分実用的な速度で動かせそうです。ご提示のコードでi = i + 100000という風にインデックスを読み飛ばしていますが、おそらく今回のようなメッシュには効果的な方法だと思います。頂点が均一に分布しているでしょうから、適当な間隔で読み飛ばすといい感じに均一な間引きができるような気がします。

さらに高速化したいとなると、これもganta7188さんのおっしゃるように並列化の方針でいくことになるでしょう。おそらく判定もClosestPointには頼れなくなるので自前で何とかしないとならないはずです。球とか直方体のようなシンプルな形状がいいでしょうね。
GPUを活用する場合、メッシュから頂点を取得するのではなくデプステクスチャの状態で取得してやればシェーダー上での交差判定もやりやすいんじゃないかと思います。

おまけ
あいにくRealSenseを持っていないので、代わりにダミーデータとして下図のような640×480頂点のメッシュを作成し...

下記のような3パターンで間引きなしで速度比較したところ...

vertices版

using System.Diagnostics;
using UnityEngine;
using Debug = UnityEngine.Debug;

public class VerticesHitTest : MonoBehaviour
{
	[SerializeField] private Transform checkarea;
	[SerializeField] private Mesh mesh;
	[SerializeField] private int stride = 1;

	private void Update()
	{
		if (Input.GetKeyDown(KeyCode.Space))
		{
			this.CheckColliderVersusMesh();
		}
	}

	private void CheckColliderVersusMesh()
	{
		var stopwatch = new Stopwatch();
		stopwatch.Start();

		var collider = this.checkarea.GetComponent<Collider>();

		// this.mesh.verticesにアクセスするたびに30万頂点分の配列生成が行われる
		for (var i = 0; i < this.mesh.vertices.Length; i += this.stride)
		{
			if (collider.ClosestPoint(this.mesh.vertices[i]) == this.mesh.vertices[i])
			{
				// コライダーの中にある
				Debug.Log("inside!!!!");
				break;
			}

			// コライダーの外にある
			// Debug.Log("outside");
		}

		stopwatch.Stop();
		var time = stopwatch.ElapsedMilliseconds;
		Debug.Log($"{this.GetType().Name} Time : {time} ms");
	}
}

GetVertices版

using System.Collections.Generic;
using System.Diagnostics;
using UnityEngine;
using Debug = UnityEngine.Debug;

public class GetVerticesHitTest : MonoBehaviour
{
	[SerializeField] private Transform checkarea;
	[SerializeField] private Mesh mesh;
	[SerializeField] private int stride = 1;

	// 格納したい頂点数が分かっているので、あらかじめ格納用Listの容量を増やしておくといい
	private readonly List<Vector3> vertices = new List<Vector3>(640 * 480);

	private void Update()
	{
		if (Input.GetKeyDown(KeyCode.Space))
		{
			this.CheckColliderVersusMesh();
		}
	}

	private void CheckColliderVersusMesh()
	{
		var stopwatch = new Stopwatch();
		stopwatch.Start();

		var collider = this.checkarea.GetComponent<Collider>();
		
		// ループ突入前に一回だけ頂点を取得し...
		this.mesh.GetVertices(this.vertices);
		
		// ループ内ではメッシュにアクセスしないようにする
		var vertexCount = this.vertices.Count;
		for (var i = 0; i < vertexCount; i += this.stride)
		{
			if (collider.ClosestPoint(this.vertices[i]) == this.vertices[i])
			{
				// コライダーの中にある
				Debug.Log("inside!!!!");
				break;
			}

			// コライダーの外にある
			// Debug.Log("outside");
		}

		stopwatch.Stop();
		var time = stopwatch.ElapsedMilliseconds;
		Debug.Log($"{this.GetType().Name} Time : {time} ms");
	}
}

Burst版

using System.Collections.Generic;
using System.Diagnostics;
using System.Reflection;
using Unity.Burst;
using Unity.Collections;
using Unity.Collections.LowLevel.Unsafe;
using Unity.Jobs;
using Unity.Mathematics;
using UnityEngine;
using Debug = UnityEngine.Debug;

public class BurstHitTest : MonoBehaviour
{
	[SerializeField] private Transform checkarea;
	[SerializeField] private Mesh mesh;
	[SerializeField] private int stride = 1;
	[SerializeField] private int innerLoopCount = 128;

	private readonly List<Vector3> vertices = new List<Vector3>(640 * 480);
	private FieldInfo itemsField = typeof(List<Vector3>).GetField("_items", BindingFlags.Instance | BindingFlags.NonPublic);

	private void Update()
	{
		if (Input.GetKeyDown(KeyCode.Space))
		{
			this.CheckColliderVersusMesh();
		}
	}

	private void CheckColliderVersusMesh()
	{
		var stopwatch = new Stopwatch();
		stopwatch.Start();

		// 今回の判定はカプセルコライダー専用
		var collider = this.checkarea.GetComponent<CapsuleCollider>();

		// メッシュから頂点を取得
		this.mesh.GetVertices(this.vertices);
		var vertexCount = this.vertices.Count;

		// NativeArrayへの高速データ転送は元データが配列でないといけないので、vertices内部のデータ格納用配列に直接アクセスする
		var vertexArray = (Vector3[])this.itemsField.GetValue(this.vertices);

		// 頂点データ格納用のNativeArrayを確保し、頂点データを転送する
		// Vector3とfloat3は異なる型だが、データ的にはfloatが3つでできていてダイレクトに転送できる
		// ※「Edit」→「Project Settings」の「Player」→「Allow 'unsafe' Code」をオンにする必要がある
		var vertexNativeArray = new NativeArray<float3>(
			vertexArray.Length,
			Allocator.TempJob,
			NativeArrayOptions.UninitializedMemory);
		unsafe
		{
			fixed (void* vertexArrayPointer = vertexArray)
			{
				UnsafeUtility.MemCpy(
					vertexNativeArray.GetUnsafePtr(),
					vertexArrayPointer,
					vertexCount * sizeof(float3));
			}
		}

		// 結果格納用の1要素のNativeArrayを確保する
		var hitNativeArray = new NativeArray<bool>(1, Allocator.TempJob);

		// コライダーの位置、スケール、回転を取得
		var position = (float3)this.checkarea.position;
		var scale = (float3)this.checkarea.lossyScale;
		var rotation = (quaternion)this.checkarea.rotation;
		var center = (float3)collider.center;

		// 軸の向きを取得
		var right = math.rotate(rotation, new float3(1.0f, 0.0f, 0.0f));
		var up = math.rotate(rotation, new float3(0.0f, 1.0f, 0.0f));
		var forward = math.rotate(rotation, new float3(0.0f, 0.0f, 1.0f));

		// コライダーの向きに応じて軸を交換、半径・高さを算出
		float3 mainAxis;
		float3 subAxis1;
		float3 subAxis2;
		float mainScale;
		float subScale1;
		float subScale2;
		switch (collider.direction)
		{
			case 0:
				mainAxis = right;
				subAxis1 = up;
				subAxis2 = forward;
				mainScale = scale.x;
				subScale1 = scale.y;
				subScale2 = scale.z;
				break;
			default:
				mainAxis = up;
				subAxis1 = forward;
				subAxis2 = right;
				mainScale = scale.y;
				subScale1 = scale.z;
				subScale2 = scale.x;
				break;
			case 2:
				mainAxis = forward;
				subAxis1 = right;
				subAxis2 = up;
				mainScale = scale.z;
				subScale1 = scale.x;
				subScale2 = scale.y;
				break;
		}
		var subScale = math.max(subScale1, subScale2);
		var radius = subScale * collider.radius;
		var normalizedHalfBodyHeight = (math.max((collider.height * mainScale) - (radius * 2.0f), 0.0f) * 0.5f) / radius;

		// 座標変換行列を作成
		var localToWorldMatrix = new float4x4(
			new float4(mainAxis * radius, 0.0f),
			new float4(subAxis1 * radius, 0.0f),
			new float4(subAxis2 * radius, 0.0f),
			new float4(math.mul(new float3x3(right, up, forward), center * scale) + position, 1.0f));
		var worldToLocalMatrix = math.inverse(localToWorldMatrix);
		var meshToNormalizedCapsuleMatrix = new float3x4(
			worldToLocalMatrix.c0.xyz,
			worldToLocalMatrix.c1.xyz,
			worldToLocalMatrix.c2.xyz,
			worldToLocalMatrix.c3.xyz);

		// ジョブを実行し完了を待機
		new CheckHitJob
		{
			vertices = vertexNativeArray,
			hit = hitNativeArray,
			stride = this.stride,
			innerLoopCount = this.innerLoopCount,
			vertexCount = vertexCount,
			meshToNormalizedCapsuleMatrix = meshToNormalizedCapsuleMatrix,
			normalizedHalfBodyHeight = normalizedHalfBodyHeight
		}.Schedule((int)math.ceil((double)vertexCount / (this.stride * this.innerLoopCount)), 1).Complete();

		// 結果を取得
		var hit = hitNativeArray[0];

		// NativeArrayは不要になったので廃棄
		vertexNativeArray.Dispose();
		hitNativeArray.Dispose();

		// 結果を表示
		if (hit)
		{
			// コライダーの中にある
			Debug.Log("inside!!!!");
		}

		stopwatch.Stop();
		var time = stopwatch.ElapsedMilliseconds;
		Debug.Log($"{this.GetType().Name} Time : {time} ms");
	}

	[BurstCompile]
	private struct CheckHitJob : IJobParallelFor
	{
		[ReadOnly] public NativeArray<float3> vertices;
		[NativeDisableParallelForRestriction] public NativeArray<bool> hit;

		public int stride;
		public int innerLoopCount;
		public int vertexCount;
		public float3x4 meshToNormalizedCapsuleMatrix;
		public float normalizedHalfBodyHeight;

		public void Execute(int index)
		{
			// もしヒットが検出されていればジョブを丸ごとスキップ
			if (this.hit[0])
			{
				return;
			}

			var n = this.innerLoopCount * this.stride;
			var i0 = index * n;
			var iN = math.min(i0 + n, this.vertexCount);
			for (var i = i0; i < iN; i += this.stride)
			{
				if (this.CheckCapsule(this.vertices[i]))
				{
					this.hit[0] = true;
					break;
				}
			}
		}

		private bool CheckCapsule(float3 p)(
		{
			// 頂点座標を正規化カプセル座標（方向X軸、半径1.0、原点中心）に直し、
			// さらにカプセルは対称な形状なので絶対値を取って計算を簡略化する
			p = math.abs(math.mul(this.meshToNormalizedCapsuleMatrix, new float4(p, 1.0f)));

			// 円柱判定と球判定のどちらを行うか選択する
			if (p.x > this.normalizedHalfBodyHeight)
			{
				// 両端の球面部分に関する判定
				p.x -= this.normalizedHalfBodyHeight;
				return math.dot(p, p) <= 1.0f;
			}

			// 中央の円柱部分に関する判定
			var yz = p.yz;
			return math.dot(yz, yz) <= 1.0f;
		}
	}
}

実験中の様子
白いカプセルが判定領域、図はワーストケース（一つもヒットがない...30万頂点全部について判定する必要がある）の場合

結果

下記のような特徴がありました。

• vertices版...ヒットなしのケースだと2.6時間もかかり実用上はきつそう
• GetVertices版...序盤でヒットすれば数ミリ秒、ヒットなしでも数百ミリ秒と大幅に改善、Burst版と違ってColliderその他の各種メソッドも制限なく使えるので有用と思われる
• Burst版...やたら長くなった上に入門者向けサイトではまず見ないような異様なコードだが、ヒットなしでも数ミリ秒、せいぜい数十ミリ秒で処理できる（初回のみ数百ミリ秒...Burstはプレイモードだと初回使用時にコンパイルを行うらしく、その影響だろうか?）

よっぽど高速化したいのでもない限り、GetVertices&間引きでいいんじゃないでしょうか?

Comments

[masa246]

回答ありがとうございます！
GetVerticesもBurstも両方やってみたいと思います！
途方に暮れていたのでとても助かりました。また実行結果をここで報告します。