Unity碰撞检测算法

发布时间: 2025-03-24 08:52

↑

# Unity碰撞检测算法

本文将深入探讨Unity物理引擎中的碰撞检测算法实现原理,包括基础算法、优化策略以及实际应用案例。

## 基础概念

### 碰撞检测流程

碰撞检测的基本流程包括:

1. 广义阶段(Broad Phase)
   - 快速剔除不可能碰撞的物体
   - 使用空间划分等技术
   - 生成潜在碰撞对

2. 中间阶段(Mid Phase)
   - 对复杂几何体进行包围体检测
   - 进一步筛选碰撞对
   - 确定需要精确检测的部分

3. 精确阶段(Narrow Phase)
   - 进行精确的几何相交测试
   - 计算接触点和法线
   - 生成碰撞信息

### 包围体系统

```csharp
// 包围体系统示例
public class BoundingVolumeSystem
{
    // 轴对齐包围盒(AABB)
    public struct AABB
    {
        public Vector3 min;
        public Vector3 max;

public bool Intersects(AABB other)
        {
            return (min.x <= other.max.x && max.x >= other.min.x) &&
                   (min.y <= other.max.y && max.y >= other.min.y) &&
                   (min.z <= other.max.z && max.z >= other.min.z);
        }
    }

// 有向包围盒(OBB)
    public class OBB
    {
        public Vector3 center;
        public Vector3 extents;
        public Quaternion orientation;

public bool Intersects(OBB other)
        {
            // 使用分离轴定理(SAT)检测
            var axes = GetSeparatingAxes(this, other);
            foreach (var axis in axes)
            {
                if (!OverlapOnAxis(this, other, axis))
                    return false;
            }
            return true;
        }
    }
}
```

常用包围体类型:

1. AABB(轴对齐包围盒)
   - 实现简单
   - 内存占用小
   - 快速相交测试

2. OBB(有向包围盒)
   - 更紧密的包围
   - 旋转支持
   - 较复杂的相交测试

3. 球体
   - 方向无关
   - 计算最简单
   - 包围不够紧密

## 空间划分

### 网格划分

```csharp
// 均匀网格划分示例
public class UniformGrid
{
    private Cell[,,] cells;
    private float cellSize;
    private Vector3 gridOrigin;

public void Insert(Collider collider)
    {
        // 1. 计算AABB
        var bounds = collider.bounds;

// 2. 确定网格范围
        var minCell = WorldToCell(bounds.min);
        var maxCell = WorldToCell(bounds.max);

// 3. 添加到相关网格
        for (int x = minCell.x; x <= maxCell.x; x++)
        for (int y = minCell.y; y <= maxCell.y; y++)
        for (int z = minCell.z; z <= maxCell.z; z++)
        {
            cells[x,y,z].Add(collider);
        }
    }

public List<Collider> Query(Bounds bounds)
    {
        var result = new List<Collider>();
        var minCell = WorldToCell(bounds.min);
        var maxCell = WorldToCell(bounds.max);

// 收集潜在碰撞对象
        for (int x = minCell.x; x <= maxCell.x; x++)
        for (int y = minCell.y; y <= maxCell.y; y++)
        for (int z = minCell.z; z <= maxCell.z; z++)
        {
            result.AddRange(cells[x,y,z].colliders);
        }

return result;
    }
}
```

网格划分特点:

1. 优点
   - 实现简单
   - 内存连续
   - 快速查询

2. 缺点
   - 空间浪费
   - 物体分布不均
   - 内存占用大

### 八叉树

```csharp
// 八叉树实现示例
public class Octree
{
    private class Node
    {
        public Bounds bounds;
        public Node[] children;
        public List<Collider> objects;
        public bool isLeaf;

public void Split()
        {
            if (isLeaf && objects.Count > maxObjects)
            {
                // 1. 创建子节点
                children = new Node[8];
                var size = bounds.size * 0.5f;
                var center = bounds.center;

// 2. 初始化子节点
                for (int i = 0; i < 8; i++)
                {
                    var offset = new Vector3(
                        (i & 1) != 0 ? size.x : -size.x,
                        (i & 2) != 0 ? size.y : -size.y,
                        (i & 4) != 0 ? size.z : -size.z
                    ) * 0.5f;

children[i] = new Node
                    {
                        bounds = new Bounds(
                            center + offset,
                            size)
                    };
                }

// 3. 重新分配对象
                foreach (var obj in objects)
                {
                    InsertObject(obj);
                }

isLeaf = false;
                objects.Clear();
            }
        }
    }

public List<Collider> Query(Bounds bounds)
    {
        var result = new List<Collider>();
        QueryNode(root, bounds, result);
        return result;
    }

private void QueryNode(
        Node node,
        Bounds bounds,
        List<Collider> result)
    {
        if (!node.bounds.Intersects(bounds))
            return;

if (node.isLeaf)
        {
            result.AddRange(node.objects);
        }
        else
        {
            foreach (var child in node.children)
            {
                QueryNode(child, bounds, result);
            }
        }
    }
}
```

八叉树优势:

1. 自适应划分
   - 根据物体分布
   - 空间利用率高
   - 查询效率好

2. 动态更新
   - 支持物体移动
   - 节点分裂合并
   - 树结构平衡

## 精确检测

### GJK算法

```csharp
// GJK算法实现示例
public class GJKAlgorithm
{
    private struct Simplex
    {
        public Vector3[] points;
        public int count;

public void Add(Vector3 point)
        {
            points[count++] = point;
        }
    }

public bool Intersect(
        ConvexMesh meshA,
        ConvexMesh meshB)
    {
        // 1. 初始化单纯形
        var simplex = new Simplex();
        var direction = meshB.center - meshA.center;

// 2. 获取初始支撑点
        var support = Support(
            meshA, meshB, direction);
        simplex.Add(support);

// 3. 迭代检测
        direction = -support;
        while (true)
        {
            support = Support(
                meshA, meshB, direction);

if (Vector3.Dot(support, direction) < 0)
                return false;

simplex.Add(support);

if (ProcessSimplex(
                ref simplex,
                ref direction))
                return true;
        }
    }

private Vector3 Support(
        ConvexMesh meshA,
        ConvexMesh meshB,
        Vector3 direction)
    {
        return meshA.Support(direction) -
               meshB.Support(-direction);
    }
}
```

GJK算法特点:

1. 适用范围
   - 凸多面体
   - 球体
   - 胶囊体

2. 性能特征
   - 迭代收敛
   - 精确检测
   - 计算开销大

### SAT算法

```csharp
// SAT算法实现示例
public class SATAlgorithm
{
    public bool Intersect(
        ConvexMesh meshA,
        ConvexMesh meshB)
    {
        // 1. 获取分离轴
        var axes = GetSeparatingAxes(meshA, meshB);

// 2. 投影检测
        foreach (var axis in axes)
        {
            // 计算投影区间
            var projA = Project(meshA, axis);
            var projB = Project(meshB, axis);

// 检查重叠
            if (!Overlap(projA, projB))
                return false;
        }

return true;
    }

private Vector2 Project(
        ConvexMesh mesh,
        Vector3 axis)
    {
        var min = float.MaxValue;
        var max = float.MinValue;

foreach (var vertex in mesh.vertices)
        {
            var proj = Vector3.Dot(vertex, axis);
            min = Mathf.Min(min, proj);
            max = Mathf.Max(max, proj);
        }

return new Vector2(min, max);
    }
}
```

SAT算法优势:

1. 实现简单
   - 直观易懂
   - 代码清晰
   - 易于调试

2. 性能稳定
   - 固定计算量
   - 无需迭代
   - 并行友好

## 连续碰撞检测

### 扫掠测试

```csharp
// 连续碰撞检测示例
public class ContinuousCollision
{
    public struct Sweep
    {
        public float t;
        public Vector3 normal;
        public Vector3 point;
    }

public Sweep SweepTest(
        Collider collider,
        Vector3 direction,
        float distance)
    {
        var result = new Sweep();

// 1. 计算扫掠体
        var start = collider.worldToLocal;
        var end = start *
            Matrix4x4.Translate(direction * distance);

// 2. 构建扫掠包围体
        var sweep = new SweptVolume(start, end);

// 3. 进行相交测试
        foreach (var other in potentialColliders)
        {
            if (sweep.Intersects(
                other, out var t, out var normal))
            {
                if (t < result.t)
                {
                    result.t = t;
                    result.normal = normal;
                    result.point = start.MultiplyPoint(
                        direction * (distance * t));
                }
            }
        }

return result;
    }
}
```

连续检测特点:

1. 应用场景
   - 快速移动物体
   - 子弹检测
   - 薄壁穿透

2. 实现方式
   - 扫掠测试
   - 时间步进
   - 轨迹预测

元素码农