一种基于体素的射线检测

效果

一个漏检的射线检测

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

    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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

可以看到上图有很多地方因为迭代的步长过大导致漏检
为了补充这些空洞可以使用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;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

oldPoint = posInt;
aabb.center = posInt;
aabb.size = Vector3.one;
if (aabb.IntersectRay(enterRay, out distance))
{
    enterPoint = enterRay.GetPoint(distance);
    if (leavePoint != enterPoint)
    {
        //存在漏检
    }
}
1
2
3
4
5
6
7
8
9
10
11

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

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

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

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

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

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



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

细分方块

把一个方块切成 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);
    }
1
2
3
4
5
6
7
8
9

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

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

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

    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;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

完整代码

using System;
using System.Collections.Generic;
using UnityEngine;

public class BlockWorld : IDisposable
{
    private static BlockWorld world;
    public static BlockWorld CurWorld
    {
        get
        {
            return world ?? (world = new BlockWorld());
        }
    }
    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 bool HasVoxelCollider(Vector3 position)
    {
        if (voxelDict.TryGetValue(Vector3Int.RoundToInt(position), out ulong value))
        {
            int index = VoxelPositionToIndex(PositionToVoxelPosition(position));
            if ((value >> index & 1) == 1)
            {
                return true;
            }
            return false;
        }
        return false;
    }


    public ulong GetVoxelValue(Vector3Int position)
    {
        voxelDict.TryGetValue(position, out var value);
        return value;
    }


    void IDisposable.Dispose()
    {
        Clear();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

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_EDITOR
        isDraw = false;
#endif

        float 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_EDITOR
        int index = 0;
        if (isDraw)
        {
            Debug.DrawLine(from, to, Color.red);
        }
#endif

        while (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 (fillPoint != posInt)
                    {
                        if (checkCollider(fillPoint, ref hitInfo))
                            return true;
                    }

                    fillPoint2 = Vector3Int.RoundToInt(enterPoint - forward * distance);
                    if (fillPoint2 != fillPoint && fillPoint2 != posInt)
                    {
                        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_EDITOR
            if (isDraw)
            {
                Gizmos.color = Color.grey;
                Gizmos.DrawWireCube(origin, Vector3.one);
                UnityEditor.Handles.Label(origin, $"[{index++}]");
            }
#endif
            if (world.HasBlockCollider(origin))
            {
                aabb.center = origin;
                aabb.size = Vector3.one;
                hitInfo.point = origin;
                if (aabb.IntersectRay(enterRay, out distance))
                {
                    hitInfo.point = enterRay.GetPoint(distance);
                    hitInfo.normal = GetNormal(origin, Vector3.one, hitInfo.point);
#if UNITY_EDITOR
                    if (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_EDITOR
        if (isDraw)
        {
            Gizmos.DrawWireSphere(enterPoint, 0.05f);
        }
        int index = 0;
#endif
        while (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_EDITOR
            if (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++}]");
            }
#endif
            if (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);
                    var voxelPoint = world.PositionToVoxelPosition(origin);
                    voxelPoint = world.VoxelPositionToWorldPosition(origin, voxelPoint);
                    hitInfo.normal = GetNormal(voxelPoint, BlockWorld.voxelSize, hitInfo.point);
#if UNITY_EDITOR
                    if (isDraw)
                    {
                        Gizmos.color = Color.red;
                        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;
    }
}

    static Vector3 GetNormal(Vector3 cursorPos, Vector3 size, Vector3 hitPoint)
    {
        Bounds aabb = default;
        aabb.center = cursorPos;
        aabb.size = size;
        Vector3 normal = Vector3Int.zero;

        var offset = cursorPos - hitPoint;
        Vector3 absOffset = default;
        absOffset.x = Mathf.Abs(offset.x);
        absOffset.y = Mathf.Abs(offset.y);
        absOffset.z = Mathf.Abs(offset.z);

        if (Mathf.Approximately(absOffset.x, absOffset.y) && Mathf.Approximately(absOffset.y, absOffset.z))
        {
            for (int i = 0; i < 3; i++)
            {
                normal = Vector3Int.zero;
                normal[i] = -Mathf.Sign(offset[i]);
                if (!GraphicsUtil.IsCollision(BlockWorld.active, hitPoint + normal))
                {
                    return normal;
                }
            }
            return normal;
        }

        int one, two;
        for (int i = 0; i < 3; i++)
        {
            one = (i + 1) % 3;
            two = (i + 2) % 3;
            if (absOffset[i] > absOffset[one])
            {
                if (absOffset[i] > absOffset[two])
                {
                    normal[i] = -Mathf.Sign(offset[i]);
                    if (GraphicsUtil.IsCollision(BlockWorld.active, hitPoint + normal))
                    {
                        i = absOffset[one] > absOffset[two] ? one : two;
                    }
                    normal = Vector3Int.zero;
                    normal[i] = -Mathf.Sign(offset[i]);
                    return normal;
                }
                else if (Mathf.Approximately(absOffset[i], absOffset[two]))
                {
                    normal[i] = -Mathf.Sign(offset[i]);
                    if (GraphicsUtil.IsCollision(BlockWorld.active, hitPoint + normal))
                        i = two;

                    normal = Vector3Int.zero;
                    normal[i] = -Mathf.Sign(offset[i]);
                    return normal;
                }
            }
        }

        return normal;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349