一种基于体素的射线检测

效果

基于体素的射线检测

一个漏检的射线检测

从起点一直递增指定步长即可得到一个稀疏的检测

    bool Raycast(Vector3 from, Vector3 forword, float maxDistance){int loop = 6666;Vector3 pos = from;Debug.DrawLine(from, from + forword * maxDistance, Color.red);while (loop-- > 0){pos += forword;if((pos - from).magnitude > maxDistance){break;}Vector3Int blockPosition = Vector3Int.RoundToInt(pos);if (world.HasBlockCollider(blockPosition)){return true;}if(world.HasVoxelCollider(blockPosition)){return true;}Gizmos.DrawWireCube(blockPosition,Vector3.one);}return false;}

可以看到上图有很多地方因为迭代的步长过大导致漏检
为了补充这些空洞可以使用Bresenham重新修改算法

填补空缺

修改步长会导致迭代次数暴增，并且想要不漏检需要很小的步长。下面使用了检测相交点是否连续检测是否空缺
首先射线经过的点必然连续，那么可以我们就可以直接对比上一次离开方块时的点和当前进入方块的点

	leavePoint = GetIntersectPoint(aabb, leaveRay, leavePoint);static Vector3 GetIntersectPoint(Bounds aabb, Ray ray, Vector3 point){if (aabb.IntersectRay(ray, out var distance)){point = ray.GetPoint(distance);}else // 由于射线平行于方块的面或边导致没有相交，稍微放大方块强行相交{aabb.size *= 1.01f;if (aabb.IntersectRay(ray, out distance)){point = ray.GetPoint(distance);}}return point;}

如果2个坐标是相等的。可以认为射线并没有漏检

oldPoint = posInt;
aabb.center = posInt;
aabb.size = Vector3.one;
if (aabb.IntersectRay(enterRay, out distance))
{enterPoint = enterRay.GetPoint(distance);if (leavePoint != enterPoint){//存在漏检}
}

否则就需要补充漏检的方块，有可能射线一次漏了2个方块没有检测

先检测最靠近离开位置的坐标是否有方块

distance = (enterPoint - leavePoint).magnitude * 0.01f;
fillPoint = Vector3Int.RoundToInt(leavePoint + forward * distance);
if (checkCollider(fillPoint, ref hitInfo))return true;

再检测靠近进入位置的坐标是否有方块

fillPoint2 = Vector3Int.RoundToInt(enterPoint - forward * distance);
if (fillPoint2 != fillPoint)
{if (checkCollider(fillPoint2, ref hitInfo))return true;
}

手动覆盖漏检的方块，青色为补充的检测



多个轴向观察射线是否在绘制的方块内

细分方块

把一个方块切成 444 共计64个方块

世界坐标转为体素内部坐标

    public Vector3 PositionToVoxelPosition(Vector3 position){var pos = Vector3Int.RoundToInt(position);position -= voxelOffset;position -= pos;position *= voxelScale;position += Vector3Int.one;return Vector3Int.RoundToInt(position);}

切分时使用ulong存储体素信息。如果某一位是1，即当前位置拥有体素
方块内部坐标转索引。使用索引检测当前位是否有体素

    public int VoxelPositionToIndex(Vector3 position){return (int)Mathf.Abs(position.x * BlockWorld.planeCount + position.y * BlockWorld.voxelScale + position.z);}

体素检测，先检测当前位置是否是体素块，如果是，检测方块体内该位置是否有体素

    public bool HasVoxelCollider(Vector3 position, out Vector3 result){if (voxelDict.TryGetValue(Vector3Int.RoundToInt(position), out ulong value)){result = PositionToVoxelPosition(position);int index = VoxelPositionToIndex(result);if ((value >> index & 1) == 1){result = VoxelPositionToWorldPosition(position, result);return true;}result = Vector3.zero;return false;}result = position;return false;}

完整代码

using System;
using System.Collections.Generic;
using UnityEngine;public class BlockWorld:IDisposable
{public const int voxelScale = 4;public const int planeCount = voxelScale * voxelScale;public static Vector3 voxelSize = Vector3.one / voxelScale;public static Vector3 voxelStartOffset = voxelSize * 0.5f;public static Vector3 voxelAABBSize = Vector3.one + BlockWorld.voxelSize * 2;public static Vector3 voxelOffset = Vector3.one * 0.5f + voxelStartOffset;private readonly Dictionary<Vector3Int, bool> blocks = new Dictionary<Vector3Int, bool>();private readonly Dictionary<Vector3Int, ulong> voxelDict = new Dictionary<Vector3Int, ulong>();public void AddBlock(Vector3Int position){blocks[position] = true;}public void AddVoxel(Vector3Int blockPosition, ulong value){voxelDict[blockPosition] = value;}public void AddVoxel( Vector3 voxelPosition){var blockPosition = Vector3Int.RoundToInt(voxelPosition);voxelDict.TryGetValue(blockPosition, out ulong value);voxelPosition = PositionToVoxelPosition(voxelPosition);int index = VoxelPositionToIndex(voxelPosition);value |= (ulong)1 << index;voxelDict[blockPosition] = value;}public Vector3 PositionToVoxelPosition(Vector3 position){var pos = Vector3Int.RoundToInt(position);position -= voxelOffset;position -= pos;position *= voxelScale;position += Vector3Int.one;return Vector3Int.RoundToInt(position);}public Vector3 VoxelPositionToWorldPosition(Vector3 position, Vector3 voxelPosition){return voxelPosition / BlockWorld.voxelScale + BlockWorld.voxelSize + BlockWorld.voxelStartOffset + Vector3Int.RoundToInt(position);}public int VoxelPositionToIndex(Vector3 position){return (int)Mathf.Abs(position.x * BlockWorld.planeCount + position.y * BlockWorld.voxelScale + position.z);}public void Clear(){blocks.Clear();voxelDict.Clear();}public bool HasBlockCollider(Vector3Int position){return blocks.ContainsKey(position);}public bool HasVoxelCollider(Vector3Int position){return voxelDict.ContainsKey(position);}public bool HasVoxelCollider(Vector3 position, out Vector3 result){if (voxelDict.TryGetValue(Vector3Int.RoundToInt(position), out ulong value)){result = PositionToVoxelPosition(position);int index = VoxelPositionToIndex(result);if( (value >> index & 1) == 1){result = VoxelPositionToWorldPosition(position, result);return true;}result = Vector3.zero;return false;}result = position;return false;}public ulong GetVoxelValue(Vector3Int position){voxelDict.TryGetValue(position, out var value);return value;}void IDisposable.Dispose(){Clear();}
}

using UnityEngine;public static class BlockPhysics
{private const int MAX_LOOP_COUNT = 6666;public static bool Raycast(BlockWorld world, Vector3 from, Vector3 forward, float maxDistance, out RaycastHit hitInfo, bool isDraw = false){
#if !UNITY_EDITORisDraw = false;
#endiffloat distance;int loop = MAX_LOOP_COUNT;Vector3 to = from + forward * maxDistance;Vector3 pos = from;Vector3 tForward = forward * 0.9f;Vector3Int posInt = Vector3Int.RoundToInt(pos);Vector3Int oldPoint = posInt;Vector3Int fillPoint;Vector3Int fillPoint2;Vector3 leavePoint = from;Vector3 enterPoint = default;Bounds aabb = default;Ray enterRay = default;Ray leaveRay = default;enterRay.origin = from;enterRay.direction = forward;leaveRay.origin = to + forward * 2;leaveRay.direction = -forward;hitInfo = default;aabb.center = posInt;aabb.size = Vector3.one;if (aabb.IntersectRay(leaveRay, out distance)){leavePoint = leaveRay.GetPoint(distance);}if (maxDistance - (int)maxDistance > 0){maxDistance += forward.magnitude * 0.9f;}#if UNITY_EDITORint index = 0;if (isDraw){Debug.DrawLine(from, to, Color.red);}
#endifwhile (loop-- > 0){pos += tForward;if ((pos - from).magnitude > maxDistance){break;}posInt = Vector3Int.RoundToInt(pos);if (posInt == oldPoint)continue;oldPoint = posInt;aabb.center = posInt;aabb.size = Vector3.one;if (aabb.IntersectRay(enterRay, out distance)){enterPoint = enterRay.GetPoint(distance);if (leavePoint != enterPoint){distance = (enterPoint - leavePoint).magnitude * 0.01f;fillPoint = Vector3Int.RoundToInt(leavePoint + forward * distance);if (checkCollider(fillPoint, ref hitInfo))return true;fillPoint2 = Vector3Int.RoundToInt(enterPoint - forward * distance);if (fillPoint2 != fillPoint){if (checkCollider(fillPoint2, ref hitInfo))return true;}}}if (checkCollider(posInt, ref hitInfo))return true;leavePoint = GetIntersectPoint(aabb, leaveRay, leavePoint);}return false;bool checkCollider(Vector3Int origin, ref RaycastHit hitInfo){
#if UNITY_EDITORif (isDraw){Gizmos.color = Color.grey;Gizmos.DrawWireCube(origin, Vector3.one);UnityEditor.Handles.Label(origin, $"[{index++}]");}
#endifif (world.HasBlockCollider(origin)){aabb.center = origin;aabb.size = Vector3.one;hitInfo.point = origin;if (aabb.IntersectRay(enterRay, out distance)){hitInfo.point = enterRay.GetPoint(distance);
#if UNITY_EDITORif (isDraw){Gizmos.color = Color.red;Gizmos.DrawWireCube(origin, Vector3.one);UnityEditor.Handles.Label(hitInfo.point, $"【{hitInfo.point.x}, {hitInfo.point.y}, {hitInfo.point.z}】");}
#endif}return true;}if (world.HasVoxelCollider(origin)){if (RaycastVoxel(world, from, forward, origin, maxDistance, out hitInfo, isDraw)){return true;}}return false;}}static bool RaycastVoxel(BlockWorld world, Vector3 from, Vector3 forward, Vector3 blockPosition, float maxDistance, out RaycastHit hitInfo, bool isDraw = false){hitInfo = default;float distance = 0f;int loop = MAX_LOOP_COUNT;Vector3 pos = from;Vector3 tForward = forward * 0.24f;Vector3 voxelPosition;Vector3 leavePoint = from;Vector3 result = default;Vector3 fillPoint = default;Vector3 fillPoint2 = default;Vector3 enterPoint = default;Bounds aabb = default;Ray enterRay = default;enterRay.origin = from;enterRay.direction = forward;Ray leaveRay = default;leaveRay.origin = (from + forward * maxDistance) + forward * 2;leaveRay.direction = -forward;aabb.center = blockPosition;aabb.size = Vector3.one;if (aabb.IntersectRay(enterRay, out distance)){enterPoint = enterRay.GetPoint(distance);pos = enterPoint;leavePoint = enterPoint;}#if UNITY_EDITORif (isDraw){Gizmos.DrawWireSphere(enterPoint, 0.05f);}int index = 0;
#endifwhile (loop-- > 0){pos += tForward;if ((pos - from).magnitude > maxDistance){break;}aabb.center = blockPosition;aabb.size = BlockWorld.voxelAABBSize;if (!aabb.Contains(pos))break;voxelPosition = world.PositionToVoxelPosition(pos);voxelPosition = world.VoxelPositionToWorldPosition(pos, voxelPosition);aabb.center = voxelPosition;aabb.size = BlockWorld.voxelSize;if (aabb.IntersectRay(enterRay, out distance)){enterPoint = enterRay.GetPoint(distance);if (leavePoint != enterPoint){distance = (enterPoint - leavePoint).magnitude * 0.01f;fillPoint = leavePoint + forward * distance;if (checkCollider(fillPoint, ref hitInfo)){return true;}fillPoint2 = enterPoint - forward * distance;if (world.PositionToVoxelPosition(fillPoint) != world.PositionToVoxelPosition(fillPoint2)){if (checkCollider(fillPoint2, ref hitInfo))return true;}}}if (checkCollider(pos, ref hitInfo)){return true;}leavePoint = GetIntersectPoint(aabb, leaveRay, leavePoint);}return false;bool checkCollider(Vector3 origin, ref RaycastHit hitInfo){
#if UNITY_EDITORif (isDraw){Gizmos.color = Color.gray;var voxelPoint = world.PositionToVoxelPosition(origin);voxelPoint = world.VoxelPositionToWorldPosition(origin, voxelPoint);Gizmos.DrawWireCube(voxelPoint, BlockWorld.voxelSize);UnityEditor.Handles.Label(voxelPoint, $"[{index++}]");}
#endifif (world.HasVoxelCollider(origin, out result)){aabb.center = result;aabb.size = BlockWorld.voxelSize;hitInfo.point = result;if (aabb.IntersectRay(enterRay, out distance)){hitInfo.point = enterRay.GetPoint(distance);
#if UNITY_EDITORif (isDraw){Gizmos.color = Color.red;var voxelPoint = world.PositionToVoxelPosition(origin);voxelPoint = world.VoxelPositionToWorldPosition(origin, voxelPoint);Gizmos.DrawWireCube(voxelPoint, BlockWorld.voxelSize);UnityEditor.Handles.Label(hitInfo.point, $"【{hitInfo.point.x}, {hitInfo.point.y}, {hitInfo.point.z}】");}
#endif}return true;}return false;}}static Vector3 GetIntersectPoint(Bounds aabb, Ray ray, Vector3 point){if (aabb.IntersectRay(ray, out var distance)){point = ray.GetPoint(distance);}else{aabb.size *= 1.01f;if (aabb.IntersectRay(ray, out distance)){point = ray.GetPoint(distance);}}return point;}
}