在Unity中实现体素化

体素化

类似与用网格存储二维平面，将三维空间划分成大量尺寸相同的小方块的过程就称之为体素化。

为什么要体素化

以下是个人理解

当场景中多边形(Polygon)数量众多且相互没什么联系时(称其为Polygon Soup)，我们在计算处理起来会比较困难。如下图中有三个凌乱的三角形，它们相互有一些相交，同时也形成了一些小的狭缝。这些都会带来较大的计算量（比如重叠的区域要做一些判断/重复计算、小的接缝可能还有一些精度上的问题）。而将其转换为网格（体素）后，虽然折损了很多精度（可以通过控制体素的大小控制精度），但是大大简化了后续的计算。

Polygon soup

易于处理动态生成的物体。比如像RTS游戏中玩家可以在游戏中建造很多建筑，动态的产生了很多障碍物。如果我们是用体素存储的世界，那么我们将建筑物体素化后直接标记对应的体素为不可通过即可。
对于一部分游戏类型（比如RTS）可能到体素化这一步就已经用起来很方便了。但是为了能够支持更大的地图，其实是需要利用体素化得到的数据去生成NavMesh。

体素存储方案

Dense Array

最简单的一种存储方式，即用数组记录每个体素的数据。例如创建三维数组 VoxelState[][][] Voxels; 这种方式非常暴力，需要消耗大量内存。但是优势是实现容易，且修改、查询的效率都非常高。

若用voxelXNum, voxelYNum, voxelZNum分别记录在x, y, z三个方向上的体素的数量，记总体素数量voxelCount = voxelXNum * voxelYNum * voxelZNum。则我们也可以使用一个一维数组VoxelState[] Voxels来存储，此时第(i, j, k)个体素存储的位置为index = i * voxelYNum * voxelZNum + j * voxelZNum + k，即Voxels[index]。

如果我们只需要存储一个体素是否被占用，即只有0|1两种状态，可以利用状态压缩的思路在一定程度上优化内存的使用量。首先假设我们开一个Bool[] Voxels来存储体素，需要开一个大小为voxelCount 的 bool数组。由于bool类型大小为1字节，故而共占用内存 voxelCount 字节。但是如果我们把数组中相邻的32个元素用一个unsigned int存储，那我们只需要voxelCount / 32 * 4 = voxelCount / 8 字节。这样就在一定程度上节省了空间。此时第(i, j, k)个体素存储的位置为index = (i * voxelYNum * voxelZNum + j * voxelZNum + k) >> 5 ，但是这个位置存的是一个32位的无符号数，而体素(i, j, k)存在这个数的第bit位，其中bit = (i * voxelYNum * voxelZNum + j * voxelZNum + k) % 32。

在下图中画出了将一维bool数组每8位压缩成一个unsigned int存储的示意。那么每32位去做压缩也是一个原理。

bool数组压缩方法

此时如果我们想要查找原数组第i位的值，其实就是查找压缩后数组第 i / 8 位的值的第i % 8位。我们可以用按位与&操作去查：_voxels[i / 8] & (1 << (7 - i % 8));

不过也可以将每个8位反过来存，这样就可以写成如下：_voxels[i / 8] & (1 << (i % 8)); 在下面的代码中，我就是运用的这种方式。

/// <summary>
/// 设置体素(i, j, k) 的状态为 state
/// </summary>
/// <param name="state">true -> 标记体素被占用，false -> 标记体素取消占用</param>
private void SetVoxelState(int x, int y, int z, bool state)
{
	int originalIndex = x * _voxelYNum * _voxelZNum + y * _voxelZNum + z;
	int compressedIndex = originalIndex >> 5; // 对应上文中的index
	int offset = originalIndex - (compressedIndex << 5); // 对应上文中的bit

	if (state)
	{
		_voxels[compressedIndex] |= (uint)(1 << offset);
	}
	else
	{
		_voxels[compressedIndex] &= ~(uint)(1 << offset);
	}
}

Solid Height Field

虽然我们用压缩相邻32位的方式，节省了一点点内存。但是在地图很大的情况下，其内存消耗依然不容乐观。不过我们很容易想到，地图上有大量的空的地方（尤其是半空中），我们没必要全都为其记录体素，我们只记录有障碍的地方即可。由此我们可以想到，以平面上的每个体素为头，向上建立链表，连接起来所有为障碍物的体素。

Solid Height Field示意图

这个方法呢，能很大程度上节省内存空间，不过每次访问的时候要从下向上去遍历链表，算是用时间换空间了。

Compact Height Field

这个方法的思路是，只记录可以行走的体素，而丢弃掉不可行走的体素。

Compact Height Field示意图

这个方式在寻路上会有较快的效率，因为所有记录的体素都是可行走的。不过在处理加入新障碍物然后进行修改，以及不同大小的单位寻路会复杂度高一些。

在本文中，我们采用Dense Array来存储体素。

在Unity中获取Mesh数据

顶点和三角面

Unity文档 Mesh

在Unity中，组件MeshFilter记录了物体所使用的Mesh，我们可以利用如下方式获取到：

// go -> 场景中的一个gameObject
var mf = go.GetComponent<MeshFilter>();
var mesh = mf.mesh;
int[] triangles = mesh.triangles;
Vector3[] vertices = mesh.vertices;

其中vertices就是mesh中的顶点，而triangles则是由这些顶点组成的三角面。我们可以获取一个Quad的Mesh，然后输出vertices和triangles如下：

顶点与三角面

不难看出triangles数组中存的其实是顶点在vertices数组中的下标，连续的三个数顺时针描述了一个三角面的三个顶点。

不过vertices中顶点的坐标是本地坐标(localPosition)，在使用的时候我们要将其转为世界坐标(worldPosition)才可以去计算体素化。

// local -> world
// go -> 场景中的一个gameObject
... // 获取go的mesh、vertices、triangles
for (int i = 0; i < vertices.Length; i++)
{
	vertices[i] = go.transform.TransformPoint(vertices[i]);
}

// local -> world 使用矩阵运算
// Unity 提供了 Matrix4x4 
// goTrans -> go.transform
Matrix4x4 transMatrix = new Matrix4x4();
transMatrix.SetTRS(goTrans.position, goTrans.rotation, goTrans.localScale);
for (int i = 0; i < vertices.Length; i++)
{
	var vertex = vertices[i];
	vertex = transMatrix.MultiplyPoint(vertex);
	vertices[i] = vertex;
}

Unity 文档 TransformPoint
Unity 文档 Matrix4x4.SetTRS

Bounds

一个Mesh对应的AABB盒(Axis Aligned Bounding Box)即是Bounds，我们可以通过mesh.bounds获取它。不过和顶点一样，mesh.bounds是本地坐标下的，我们需要转换成世界坐标才能用。这时我们可以从MeshRenderer中获取它，GetComponent<MeshRenderer>().mesh.bounds; 就是世界坐标下的AABB盒。

Bounds

我们拿到Bounds的目的是简化碰撞判断，当一个Mesh的Bounds与我们限制体素化范围的物体的Bounds相交，我们才去着手对其进行体素化操作。

// 获取场景内所有的gameObject，逐个判断是否在VoxelizationBox范围内。
foreach (var go in Object.FindObjectsOfType<GameObject>())
{
	if (go.transform == _startPoint || go.transform == _destPoint)
		continue;

	var mf = go.GetComponent<MeshFilter>();
	if (mf == null) continue;
	var mesh = mf.mesh;
	var bounds = go.GetComponent<MeshRenderer>().bounds;

	if (!_voxelBox.Intersects(bounds)) continue;

	// 物体和VoxelizationBox有交叉
	// 获取物体Mesh的全部三角面，逐个光栅化（标记其占用的体素）
	int[] triangles = mesh.triangles;
	Vector3[] vertices = mesh.vertices;
	var goTrans = go.transform;

	// local -> worldPosition
	Matrix4x4 transMatrix = new Matrix4x4();
	transMatrix.SetTRS(goTrans.position, goTrans.rotation, goTrans.localScale);
	for (int i = 0; i < vertices.Length; i++)
	{
		var vertex = vertices[i];
		vertex = transMatrix.MultiplyPoint(vertex);
		vertices[i] = vertex;
	}

	// 对每个三角面进行体素化
	for (int i = 0; i < triangles.Length; i += 3)
	{
		int j = i + 1, k = i + 2;
		RasterizeTriangle(vertices[triangles[i]], 
							vertices[triangles[j]], 
							vertices[triangles[k]]);
	}
}

体素化三角面

基本思路

如果是二维的三角面，体素化（网格化）会比较容易。假设我们的三角形在$XOZ$平面上，我们可以按照如下步骤：

求出三角形的Bounds，获取其所处的网格$z$方向的取值范围；
逐个枚举$z$，将三角形分为上、下两部分，取下部分进行 3 操作；
对于 2 中下部分，求出其所处的网格$x$方向的取值范围；
逐个枚举$x$，标记左侧部分所在的网格，返回 2 。

可以看如下图：

z方向切割

左边红色的线为我们枚举的$z$切割线，按照线可以将三角面分割成右侧6部分，每个部分对应$x$的范围用绿色框框起来了。

x方向切割

右侧红色的线为我们枚举的$x$切割线，按照先将每个多边形分割到每个网格中，最后被标记的网格在左边用浅蓝色的线围起来了。

三维空间中的多边形

三维的其实也是同理，如上图多边形，我们先按照$z$轴分割。拿分割出的多边形，按照$x$轴进行分割。这时候得到的多边形在$XOZ$平面内的投影就在一个体素内了（如下图，红色线表示$z$轴分割，浅蓝色线表示$x$轴分割），我们只需要求出其在$y$轴上占几个体素，将其标记为占用即可。

对投影面进行分割

结果如下图：

体素化结果

分割三角面

现在我们思路已经很明确了，就要去解决分割三角面的问题了。

在$z$方向上的切割，详细过程可以见下图，我们维护两个List，Current和Next。Current表示切割线下方的多边形（即我们将要那它去做$x$轴切割），Next表示切割线上方的多边形（即处理完Current后再继续对它进行$z$方向切割）。

体素化过程

按照顺时针方向枚举目前三角面上的边，例如这里我们按照AB、BC、CA的顺序。

AB： A、B两点位于切割线异侧，故而要求AB与切割线的交点D，随后按照顺时针顺序（A -> D -> B）逐个将顶点放入Current或者Next。

BC： B、C两点位于切割线异侧，故而要求BC与切割线的交点E，随后按照顺时针顺序（B -> E -> C）逐个将顶点放入Current或者Next。

CA： C、A两点位于切割线同侧，直接按照顺时针顺序（C -> A）逐个将顶点放入Current或者Next。

放置规则： 位于切割线上侧，则放入Next；位于切割线下侧，则放入Current；为边线与切割线交点，则同时要被放入Current和Next。

当然同一个点不要在一个List中反复添加，所以下图中，重复添加的行被打上了灰色的删除线。由此在枚举完所有的边之后，我们可以发现不管是Current还是Next，其中记录的点都是按照顺时针顺序排列的，完整了记录了其所对应的多边形。

/// <summary>
/// 将三角面abc光栅化(体素化)
/// </summary>
private void RasterizeTriangle(Vector3 a, Vector3 b, Vector3 c)
{
	// Debug.Log($"Triangle: a = {a}, b = {b}, c = {c}");

	// 求出当前三角面abc的AABB盒
	Bounds triBound = new Bounds();
	triBound.max = a.ComponentMax(b).ComponentMax(c);
	triBound.min = a.ComponentMin(b).ComponentMin(c);

	// 如果当前三角面不在体素化范围内，就返回，不处理了。
	if (!_voxelBox.Intersects(triBound))
		return;

	// 求三角面abc在z方向上占用的体素的坐标范围
	var z0 = Mathf.Clamp(
					Mathf.FloorToInt((triBound.min.z - _voxelBox.min.z) / _cellSize),
					0,
					_voxelZNum - 1
				);

	var z1 = Mathf.Clamp(
					Mathf.CeilToInt((triBound.max.z - _voxelBox.min.z) / _cellSize),
					0,
					_voxelZNum - 1
				);

	// 一个三角形被正方形切割得到的图形最多有七个顶点
	List<Vector3> NextRow = new List<Vector3>(7);
	List<Vector3> CurrentRow = new List<Vector3>(7);
	List<Vector3> NextGrid = new List<Vector3>(7);
	List<Vector3> CurrentGrid = new List<Vector3>(7);

	NextRow.Add(a);
	NextRow.Add(b);
	NextRow.Add(c);

	// Debug.Log($"RasterizeTriangle: z0 = {z0}, z1 = {z1}");

	for (int z = z0; z <= z1; z++)
	{
		// 分割线
		float zSecant = _voxelBox.min.z + (z + 1) * _cellSize;
		
		DividePolygon(NextRow, CurrentRow, zSecant, true);
		if (CurrentRow.Count < 3)
			continue;

		// 求经过z分割线分割后，下方多边形的AABB盒
		float minX = CurrentRow[0].x, maxX = CurrentRow[0].x;
		for (int i = 1; i < CurrentRow.Count; i++)
		{
			minX = Mathf.Min(minX, CurrentRow[i].x);
			maxX = Mathf.Max(maxX, CurrentRow[i].x);
		}

		// 求多边形在x方向上占用体素x坐标范围
		var x0 = Mathf.Clamp(
						Mathf.FloorToInt((minX - _voxelBox.min.x) / _cellSize),
						0,
						_voxelXNum - 1
					);

		var x1 = Mathf.Clamp(
						Mathf.CeilToInt((maxX - _voxelBox.min.x) / _cellSize),
						0,
						_voxelXNum - 1
					);

		// Debug.Log($"RasterizeTriangle: x0 = {x0}, x1 = {x1}");

		for (int x = x0; x <= x1; x++)
		{
			float xSecant = _voxelBox.min.x + (x + 1) * _cellSize;

			DividePolygon(CurrentRow, CurrentGrid, xSecant, false);
			if (CurrentGrid.Count < 3)
				continue;

			// 求经过x分割后，左方多边形的AABB盒
			float minY = CurrentGrid[0].y, maxY = CurrentGrid[0].y;
			for (int i = 0; i < CurrentGrid.Count; i++)
			{
				minY = Mathf.Min(minY, CurrentGrid[i].y);
				maxY = Mathf.Max(maxY, CurrentGrid[i].y);
			}

			if (maxY <= _voxelBox.min.y || minY >= _voxelBox.max.y)
				continue;

			// 求多边形在y方向上占用体素y坐标范围
			var y0 = Mathf.Clamp(
							Mathf.FloorToInt((minY - _voxelBox.min.y) / _cellHeight),
							0,
							_voxelYNum - 1
						);

			var y1 = Mathf.Clamp(
							Mathf.CeilToInt((maxY - _voxelBox.min.y) / _cellHeight),
							y0 + 1, 
							_voxelYNum - 1
						);

			// Debug.Log($"RasterizeTriangle: y0 = {y0}, y1 = {y1}");
			for (int y = y0; y < y1; y++)
			{
				SetVoxelState(x, y, z, true);
			}
		}
	}
}

/// <summary>
/// 沿着 secant 将 divided 描述的多边形进行切分
/// </summary>
/// <remarks>
/// 在方法执行完毕后，位于 secant 上侧或右侧的多边形会被存储在 divided 中,
/// 位于 secant 下侧或左侧的多边形会被存储在 result 中 
/// </remarks>
/// <param name="zAxis">为true说明 z = secant, 为false说明是 x = secant </param>
private void DividePolygon(List<Vector3> divided, List<Vector3> result, float secant, bool zAxis)
{
	List<Vector3> nextPart = new List<Vector3>(7);
	result.Clear();

	for (int i = 1; i <= divided.Count; i++)
	{
		Vector3 a = divided[i - 1], b = divided[i % divided.Count];

		// true -> nextPart, false -> result
		bool aBelongs = false, bBelongs = false;
		aBelongs = zAxis ? (a.z >= secant) : (a.x >= secant);
		bBelongs = zAxis ? (b.z >= secant) : (b.x >= secant);

		// Debug.Log($"DividePolygon: aBelongs = {aBelongs}, bBelongs = {bBelongs}");

		if (i == 1)
		{
			if (aBelongs) nextPart.Add(a);
			else result.Add(a);
		}

		if (aBelongs ^ bBelongs)
		{
			float proportion, intersectX, intersectY, intersectZ;

			if (zAxis)
			{
				proportion = (secant - a.z) / (b.z - a.z);
				intersectX = a.x + (b.x - a.x) * proportion;
				intersectZ = secant;
			}
			else
			{
				proportion = (secant - a.x) / (b.x - a.x);
				intersectX = secant;
				intersectZ = a.z + (b.z - a.z) * proportion;
			}

			intersectY = a.y + (b.y - a.y) * proportion;

			var intersect = new Vector3(intersectX, intersectY, intersectZ);
			nextPart.Add(intersect);
			result.Add(intersect);
		}

		if (i != divided.Count)
		{
			if (bBelongs) nextPart.Add(b);
			else result.Add(b);
		}
	}

	divided.Clear();
	divided.AddRange(nextPart);
}

/// <summary>
/// 设置体素(x, y, z) 的状态为 state/>
/// </summary>
/// <param name="state">true -> 标记体素被占用，false -> 标记体素取消占用</param>
private void SetVoxelState(int x, int y, int z, bool state)
{
	// Debug.Log($"Set Voxel ({x}, {y}, {z}) occupied!");
	int originalIndex = x * _voxelYNum * _voxelZNum + y * _voxelZNum + z;
	int compressedIndex = originalIndex >> 5;
	int offset = originalIndex - (compressedIndex << 5);

	if (state)
	{
		_voxels[compressedIndex] |= (uint)(1 << offset);
	}
	else
	{
		_voxels[compressedIndex] &= ~(uint)(1 << offset);
	}
}

体素化结果

简单的寻路演示

用BFS简单做了个基于体素的寻路，效果如下：

效果展示

private List<Vector3Int> PathFinding(Vector3Int startVoxel, Vector3Int destVoxel)
{
	Dictionary<Vector3Int, Vector3Int> precursorDict = new Dictionary<Vector3Int, Vector3Int>();
	List<Vector3Int> path = new List<Vector3Int>();

	Queue<Vector3Int> bfsQ = new Queue<Vector3Int>();
	bfsQ.Enqueue(startVoxel);

	while (bfsQ.Count > 0)
	{
		Vector3Int current = bfsQ.Dequeue();
		if (current == destVoxel)
		{
			// Debug.Log("Find Path!!!!");
			path.Add(destVoxel);
			var prev = precursorDict[current];
			do
			{
				path.Add(prev);
				prev = precursorDict[prev];
			} while (prev != startVoxel);

			break;
		}

		for (int i = 0; i < 6; i++)
		{
			int dx = _dirX[i], dy = _dirY[i], dz = _dirZ[i];
			Vector3Int nextVoxel = current + new Vector3Int(dx, dy, dz);
			if (IsVoxelInside(nextVoxel) 
				&& IsStayableVoxel(nextVoxel) 
				&& !precursorDict.ContainsKey(nextVoxel))
			{
				bfsQ.Enqueue(nextVoxel);
				precursorDict.Add(nextVoxel, current);
			}
		}
	}
	return path;
}

/// <summary>
/// 传入voxel坐标，判断这个位置是否可以停留
/// </summary>
/// <remarks>
/// 一个可以停留的voxel用以下三点判断：<br/>
/// 1. 本身不是障碍物 <br/>
/// 2. 下方是障碍物 （站在地面上） <br/>
/// 3. 四周是障碍物 （爬墙） <br/>
/// 4. 四周正下方一格是障碍物（进入向下爬墙状态） <br/>
/// 其中 1 必须满足，2、3、4满足其一即可
/// </remarks>
/// <returns><see langword="true"/>-> 可以停留，<see langword="false"/>-> 不可停留</returns>
private bool IsStayableVoxel(Vector3Int voxel)
{

	return IsVoxelInside(voxel) && !IsVoxelOccupied(voxel.x, voxel.y, voxel.z) // 1.
			&& (IsVoxelOccupied(voxel.x - 1, voxel.y, voxel.z)                 // 3.
				|| IsVoxelOccupied(voxel.x + 1, voxel.y, voxel.z)              // 3.
				|| IsVoxelOccupied(voxel.x, voxel.y - 1, voxel.z)              // 2.
				|| IsVoxelOccupied(voxel.x, voxel.y, voxel.z + 1)              // 3.
				|| IsVoxelOccupied(voxel.x, voxel.y, voxel.z - 1)              // 3.
				|| IsVoxelOccupied(voxel.x - 1, voxel.y - 1, voxel.z)          // 4.
				|| IsVoxelOccupied(voxel.x + 1, voxel.y - 1, voxel.z)          // 4.
				|| IsVoxelOccupied(voxel.x, voxel.y - 1, voxel.z - 1)          // 4.
				|| IsVoxelOccupied(voxel.x, voxel.y - 1, voxel.z + 1)          // 4.
			);
}

private bool IsVoxelInside(Vector3Int voxel)
{
	return voxel.x >= 0 && voxel.x < _voxelXNum
			&& voxel.y >= 0 && voxel.y < _voxelYNum
			&& voxel.z >= 0 && voxel.z < _voxelZNum;
}

private bool IsVoxelInside(int x, int y, int z)
{
	return x >= 0 && x < _voxelXNum
			&& y >= 0 && y < _voxelYNum
			&& z >= 0 && z < _voxelZNum;
}