3D碰撞检测系统 基于SAT算法+Burst优化(Unity)

本文介绍如何实现3D碰撞检测系。

技术栈：

基于Unity凸体碰撞检测，核心实现为 分离轴定理（SAT）与 Burst高性能优化，高性能运行要求。

• 实现 SAT 算法三维版本：
• 支持任意凸多面体之间的精确碰撞检测，包括面-面、边-边间的最小投影距离求解。
• 使用ISMinkowskiFace 优化轴筛选，跳过不构成分离轴的边对组合，减少计算量。
• 接触点计算与裁剪优化：
• 通过 ClipPlane 与裁剪算法（Sutherland-Hodgman 变体）生成精确接触点。
• 自动处理接触法线翻转与世界空间变换，提升物理求解稳定性。
• Burst 高性能优化：
• 所有数据结构均为 unmanaged + ［BurstCompatible］，确保完全兼容
  Burst.
• 利用 stackalloc 和 NativeBuffer<T> 进行堆栈内存分配，避免GC 压力。
• 使用 UnsafeUtility + NativeDisableunsafePtrRestriction 实现原始指针访问，进一步压缩性能开销。
• 自定义 NativeHull，NativePlane，NativeManifold 等轻量结构体，提供零 GC的碰撞数据结构。

首先我们先要知道什么是SAT算法：

翻译成大白话就是：

对于凸多边形来说，存在一条线能把这两个图形分开，这两条线就是分离线Separating line

与之垂直的就是分离轴Separating axis

如何找到分离轴呢？ 很简单，如果存在分离轴，那么凸多边形中的任意一条边，会和至少一条分离轴平行，只需要每条边遍历即可。

那3D中的SAT如何理解？

然后我们要简单了解以下知识

1.Burst编译器

Burst是Unity的一个编译器技术，用于在运行时编译C#代码成Native代码，以提高性能。

它是基于LLVM技术的，并使用了SIMD指令来加速数学和向量操作。

Burst使用了多种优化技术，例如循环展开、常量传播和内联，以生成高效的机器代码。

Burst还提供了一些工具，例如性能分析器和调试器，以帮助开发人员更好地优化和调试他们的代码。

2.Native代码

编译是将源代码转换为可执行代码的过程，而编译成Native代码是将源代码编译成与特定硬件平台相关的机器码，以便能够直接在该硬件上运行。Native代码相对于其他形式的代码（如中间代码）具有更高的性能和更好的优化能力，因为它直接针对特定的硬件平台进行优化。

在，NET平台中，C#代码通常被编译成中间代码，然后在运行时进行JIT编译，转换为Native代码。而使用Burst技术可以将方法或类直接编译为Native代码，避免了JIT编译的性能损失，从而提高应用程序的性能。

3.LLVM技术

LLVM （Low Level Virtual Machine）是一个开源的、模块化的、可重用的编译器和工具链技术集合。LLVM的核心是一个中间表示（IR），它允许将不同语言的代码转换为统一的中间形式，然后进行优化和转换为目标平台的机器码。

4.ECS架构

ECS（Entity-Component-System）架构是一种以属性为中心的软件架构风格，遵循“组合优于继承”的思想，采用类似数据库的结构来存储游戏对象。ECS架构的核心思想是将数据和逻辑分离，通过组件来存储数据，通过系统来处理逻辑，从而实现高度的数据驱动和解耦。

流程：在使用burst技术后，从。NET的IL到Native的代码流程大致如下

步骤

C#----→> NET IL -----> LLVM IR -----> C++ -----> native assembly

1. 第一个阶段是由.NET或者mono的编译器，将C#代码编译为.NET IL指令
2. 第二个阶段是由Burst，或者说是LLVM，将.NET IL指令转译为LLVM IR指令，在这一阶段LLVM会对IR进行优化
3. 将LLVMIR通过I2CPP转换为C++代码
4. 通过C++编译器将C++代码编译为对应平台的汇编指令

BurstAction类:

using Unity.Burst;
using Unity.Collections.LowLevel.Unsafe;
using Unity.Jobs;

namespace Common
{
    
    // 定义一个基础接口，用于标识所有 Burst 操作
    public interface IBurstOperation
    {

    }
    
    // 定义一个接口，用于声明带有引用参数的操作
    public interface IBurstRefAction<T1, T2, T3, T4, T5> : IBurstOperation
    {
        // 执行方法，接受五个参数，其中第一个参数为引用类型
        void Execute(ref T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5);
    }

    // 一个 Burst 编译的结构体，执行带有引用参数的操作
    // 这个结构体实现了 IJob，允许在 Unity 作业系统中异步执行
    [BurstCompile]
    public struct BurstRefAction<TFunc, T1, T2, T3, T4, T5> : IJob
        where TFunc : struct, IBurstRefAction<T1, T2, T3, T4, T5> // TFunc 必须实现 IBurstRefAction 接口
        where T1 : unmanaged // T1 必须是非托管类型
        where T2 : struct
        where T3 : struct
        where T4 : struct
        where T5 : struct
    {
        // 使用 NativeDisableUnsafePtrRestriction 属性标记指针类型字段，
        // 防止 Unity 分配内存时对其进行额外的安全性检查
        [NativeDisableUnsafePtrRestriction]
        public unsafe void* FunctionPtr; // 存储函数指针
        [NativeDisableUnsafePtrRestriction]
        public unsafe T1* Argument1Ptr; // 存储第一个参数的指针
        [NativeDisableUnsafePtrRestriction]
        public unsafe void* Argument2Ptr; // 存储第二个参数的指针
        [NativeDisableUnsafePtrRestriction]
        public unsafe void* Argument3Ptr; // 存储第三个参数的指针
        [NativeDisableUnsafePtrRestriction]
        public unsafe void* Argument4Ptr; // 存储第四个参数的指针
        [NativeDisableUnsafePtrRestriction]
        public unsafe void* Argument5Ptr; // 存储第五个参数的指针

        // 执行作业的核心方法
        public unsafe void Execute()
        {
            // 将函数指针转换为具体的 TFunc 类型
            //把 FunctionPtr 指向的原始内存数据，反序列化/复制为一个结构体 TFunc 的实例 func
            UnsafeUtility.CopyPtrToStructure(FunctionPtr, out TFunc func);

            // 将指针转换为相应类型的参数
            UnsafeUtility.CopyPtrToStructure(Argument2Ptr, out T2 arg2);
            UnsafeUtility.CopyPtrToStructure(Argument3Ptr, out T3 arg3);
            UnsafeUtility.CopyPtrToStructure(Argument4Ptr, out T4 arg4);
            UnsafeUtility.CopyPtrToStructure(Argument5Ptr, out T5 arg5);

            // 执行实际的操作，注意第一个参数是引用类型
            func.Execute(ref *Argument1Ptr, arg2, arg3, arg4, arg5);
        }

        // 静态方法，用于启动该作业
        public static unsafe void Run(TFunc func, ref T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5)
        {   
            // 创建一个 BurstRefAction 实例，并初始化所有字段
            new BurstRefAction<TFunc, T1, T2, T3, T4, T5>
            {
                //UnsafeUtility.AddressOf(...)	返回 func 在内存中的地址,把地址赋给 Job 的 FunctionPtr 字段，
                //便于 Job 内部后续还原为原始对象
                FunctionPtr = UnsafeUtility.AddressOf(ref func),
                Argument1Ptr = (T1*)UnsafeUtility.AddressOf(ref arg1),
                Argument2Ptr = UnsafeUtility.AddressOf(ref arg2),
                Argument3Ptr = UnsafeUtility.AddressOf(ref arg3),
                Argument4Ptr = UnsafeUtility.AddressOf(ref arg4),
                Argument5Ptr = UnsafeUtility.AddressOf(ref arg5),
            }.Run(); // 调用 Run 方法执行作业
        }
    }
}

面检测：Hullcollision

using Unity.Mathematics;
using Common;
using Debug = UnityEngine.Debug;

namespace UnityNativeHull
{
    // 表示面查询结果的结构体
    public struct FaceQueryResult
    {
        public int Index;   // 面的索引
        public float Distance;  // 面的距离
    };

    // 表示边查询结果的结构体
    public struct EdgeQueryResult
    {
        public int Index1;  // 边1的起始顶点索引
        public int Index2;  // 边1的结束顶点索引
        public float Distance;  // 边之间的距离
    };

    // 表示碰撞信息的结构体
    public struct CollisionInfo
    {
        public bool IsColliding;  // 是否发生碰撞
        public FaceQueryResult Face1;  // 第一个面查询结果
        public FaceQueryResult Face2;  // 第二个面查询结果
        public EdgeQueryResult Edge;  // 边查询结果
    }

    // 包含碰撞检测的逻辑
    public class HullCollision
    {
        // 获取调试用的碰撞信息
        public static CollisionInfo GetDebugCollisionInfo(RigidTransform transform1, NativeHull hull1, RigidTransform transform2, NativeHull hull2)
        {
            CollisionInfo result = default;
            QueryFaceDistance(out result.Face1, transform1, hull1, transform2, hull2);
            QueryFaceDistance(out result.Face2, transform2, hull2, transform1, hull1);
            //主要是物体很有可能两个凸起的地方错开，实际没相交，单纯计算面就相交了。所以必须还检测边
            QueryEdgeDistance(out result.Edge, transform1, hull1, transform2, hull2);
            result.IsColliding = result.Face1.Distance < 0 && result.Face2.Distance < 0 && result.Edge.Distance < 0;
            return result;
        }

        //查询两个体之间的面距离，主要就是再找分离轴，通过每个面法线（即 plane.Normal）作为潜在的分离轴来进行计算的
        public static unsafe void QueryFaceDistance(out FaceQueryResult result, RigidTransform transform1, NativeHull hull1, RigidTransform transform2, NativeHull hull2)
        {
            // 在第二个体的局部空间中进行计算
            RigidTransform transform = math.mul(math.inverse(transform2), transform1);

            result.Distance = -float.MaxValue;  // 初始化最远距离
            result.Index = -1;  // 初始化索引

            //实际上这个for就是再选一组分离轴，挨个算。遍历 hull1 的每一个面，每个面的法线 plane.Normal 被当作一个分离轴
            for (int i = 0; i < hull1.FaceCount; ++i)
            {
                // 获取面平面
                NativePlane plane = transform * hull1.GetPlane(i);  
                // 获取支撑点，注意这里是用的hull2调用的hull1面的法线，
                // 也就是说目的是找到 hull2 在这个法线反方向上最远的点（即最靠近 hull1 面的点）。
                //可以进到这个GetSupport函数一看便知，不断地dot点乘这个内法线，值最大的就是距离最近的。返回值是点的坐标
                float3 support = hull2.GetSupport(-plane.Normal);  
                //计算面到支撑点的距离，法线目前就当做是探索的分离轴
                //support 点沿着分离轴的投影值 - hull1 当前面的投影值,也就是这两个投影区间的距离。
                float distance = plane.Distance(support);  
                
                // 当 distance > 0 时，表示：
                // support 落在了 hull1 这个面所在平面的“外面”；也就是在这个轴上存在投影间隙；
                // 也就是 SAT 中的 "分离轴存在"。

                // 当 distance <= 0 时，表示：
                // support 落在了 hull1 面平面内侧或上面；
                // 在这个轴上投影区间重叠；需要继续检测其它轴。

                //更新最大距离和面索引，所以保存好最大的就行了，知道有存在的即可了，全都小于0那就是真分不开了。
                if (distance > result.Distance)
                {
                    result.Distance = distance;
                    result.Index = i;
                }
            }
        }

        // 查询两个体之间的边距离
        public static unsafe void QueryEdgeDistance(out EdgeQueryResult result, RigidTransform transform1, NativeHull hull1, RigidTransform transform2, NativeHull hull2)
        {
            // 在第二个体的局部空间中进行计算
            RigidTransform transform = math.mul(math.inverse(transform2), transform1);

            float3 C1 = transform.pos;  // 获取第一个刚体的位移

            result.Distance = -float.MaxValue;  // 初始化最远距离
            result.Index1 = -1;  // 初始化边1的索引
            result.Index2 = -1;  // 初始化边2的索引

            // 遍历第一个体的边
            for (int i = 0; i < hull1.EdgeCount; i += 2)
            {
                //同在一条直线边上，方向相反而已，就是为了记录下所属边，便于计算
                NativeHalfEdge* edge1 = hull1.GetEdgePtr(i);  // 获取边1
                NativeHalfEdge* twin1 = hull1.GetEdgePtr(i + 1);  // 获取边1的对偶边

                Debug.Assert(edge1->Twin == i + 1 && twin1->Twin == i);  // 确保对偶关系

                float3 P1 = math.transform(transform, hull1.GetVertex(edge1->Origin));  // 边1起点
                float3 Q1 = math.transform(transform, hull1.GetVertex(twin1->Origin));  // 边1终点
                float3 E1 = Q1 - P1;  // 边1向量

                //边本身是没有法线的，但是他属于2个不同的面，面上就有法线了
                float3 U1 = math.rotate(transform, hull1.GetPlane(edge1->Face).Normal);  // 面法线向量
                float3 V1 = math.rotate(transform, hull1.GetPlane(twin1->Face).Normal);  // 面法线向量

                // 遍历第二个体的边
                for (int j = 0; j < hull2.EdgeCount; j += 2)
                {
                    NativeHalfEdge* edge2 = hull2.GetEdgePtr(j);  // 获取边2
                    NativeHalfEdge* twin2 = hull2.GetEdgePtr(j + 1);  // 获取边2的对偶边

                    Debug.Assert(edge2->Twin == j + 1 && twin2->Twin == j);  // 确保对偶关系

                    float3 P2 = hull2.GetVertex(edge2->Origin);  // 边2起点
                    float3 Q2 = hull2.GetVertex(twin2->Origin);  // 边2终点
                    float3 E2 = Q2 - P2;  // 边2向量
                   
                    float3 U2 = hull2.GetPlane(edge2->Face).Normal;  // 面法线向量
                    float3 V2 = hull2.GetPlane(twin2->Face).Normal;  // 面法线向量

                    // 判断是否构成Minkowski支持面
                    if (IsMinkowskiFace(U1, V1, -E1, -U2, -V2, -E2))
                    {
                        // 投影计算距离
                        float distance = Project(P1, E1, P2, E2, C1);
                        if (distance > result.Distance)
                        {
                            result.Index1 = i;
                            result.Index2 = j;
                            result.Distance = distance;
                        }
                    }
                }
            }
        }

        // 判断两个边是否在Minkowski空间中形成面
        //这里比较精髓，先去看文档里Minkowski差的概念，我们没有必要构建真实的差集，利用特性去算即可。
        public static bool IsMinkowskiFace(float3 A, float3 B, float3 B_x_A, float3 C, float3 D, float3 D_x_C)
        {
            // 检查AB和CD是否在单位球上相交
            float CBA = math.dot(C, B_x_A);
            float DBA = math.dot(D, B_x_A);
            float ADC = math.dot(A, D_x_C);
            float BDC = math.dot(B, D_x_C);

            return CBA * DBA < 0 &&
                   ADC * BDC < 0 &&
                   CBA * BDC > 0;
        }

        /// <summary>
        /// 对两个边向量（分别属于两个物体）构造一个分离轴，
        /// 并将第二个物体相对于第一个物体在该轴上的投影距离作为分离度量返回。
        /// 如果两个边近似平行，则认为无法构造有效分离轴，返回一个极小值（表示忽略此轴）。
        /// </summary>
        /// <param name="P1">第一个物体的边的起点（世界坐标）</param>
        /// <param name="E1">第一个物体的边向量</param>
        /// <param name="P2">第二个物体的边的起点（世界坐标）</param>
        /// <param name="E2">第二个物体的边向量</param>
        /// <param name="C1">第一个物体的质心（用于决定分离轴方向）</param>
        /// <returns>
        /// 返回值为在构造出的分离轴（E1 × E2）方向上，第二个边相对于第一个边的投影距离：
        ///若为正，表示存在间隙；
        /// — 若为负，表示重叠（即发生碰撞）；
        /// — 若返回极小值（-float.MaxValue），表示两边近似平行，不适合作为分离轴。
        /// </returns>
        public static float Project(float3 P1, float3 E1, float3 P2, float3 E2, float3 C1)
        {
            // 步骤1：计算候选分离轴 —— 两条边的叉积方向
            float3 E1_x_E2 = math.cross(E1, E2);

            // 步骤2：判断是否平行（叉积近似为0）
            float kTol = 0.005f;
            float L = math.length(E1_x_E2); // 得到叉积向量的长度，即 sin(θ)·|E1|·|E2|

            // 如果两条边几乎平行（sinθ 很小），则这个分离轴无效，跳过处理
            // 这个判断条件等价于：sin(θ) < kTol
            // 即：|E1 x E2| < kTol * |E1||E2|
            if (L < kTol * math.sqrt(math.lengthsq(E1) * math.lengthsq(E2)))
            {
                return -float.MaxValue; // 极小值表示此分离轴无效
            }

            // 步骤3：归一化分离轴向量（叉积结果）
            float3 N = (1 / L) * E1_x_E2;

            // 步骤4：确保分离轴方向从第一个物体指向第二个物体
            // 用第一个边的起点 P1 到物体1质心 C1 的向量与 N 做点乘判断方向
            // 若为负数，说明 N 朝向物体内部，应当翻转
            if (math.dot(N, P1 - C1) < 0)
            {
                N = -N;
            }

            // 步骤5：将两个边的起点在分离轴方向上做投影
            // 表达式 math.dot(N, P2 - P1) 即为第二条边（P2）到第一条边（P1）
            // 在分离轴方向 N 上的距离。
            // 如果结果为正数 → 有间隙；如果为负数 → 发生重叠。
            return math.dot(N, P2 - P1);
        }

        
    }
}

绘制辅助: HullDrawingUtility

using System;
using System.Collections.Generic;
using System.Linq;
using Unity.Mathematics;
using UnityEngine;
using Common;

#if UNITY_EDITOR
using UnityEditor;
#endif

namespace UnityNativeHull
{
    // 定义调试标志的枚举类型，用于控制在调试过程中显示的内容
    [Flags]
    public enum DebugHullFlags
    {
        None = 0,           // 无标志
        PlaneNormals = 2,   // 显示平面法线
        Indices = 4,       // 显示索引
        Outline = 8,      // 显示轮廓
        All = ~0,           // 所有标志
    }
    
    // 用于绘制Hull（凸包）的辅助工具类
    public class HullDrawingUtility
    {
        // 根据选项绘制调试Hull（凸包），外部轮廓方便计算
        public static void DrawDebugHull(NativeHull hull, RigidTransform t, DebugHullFlags options = DebugHullFlags.All, Color BaseColor = default)
        {
            if (!hull.IsValid)
                throw new ArgumentException("Hull is not valid", nameof(hull));

            if (options == DebugHullFlags.None)
                return;

            if (BaseColor == default)
                BaseColor = Color.yellow;

            // 遍历每对边，所以迭代为+2
            for (int j = 0; j < hull.EdgeCount; j = j + 2)
            {
                var edge = hull.GetEdge(j);
                var twin = hull.GetEdge(j + 1);
                
                //hull.GetVertex获取局部空间位置，进而用math.transform根据t来转化为世界空间
                var edgeVertex1 = math.transform(t, hull.GetVertex(edge.Origin));
                var twinVertex1 = math.transform(t, hull.GetVertex(twin.Origin));

                if ((options & DebugHullFlags.Outline) != 0)
                {
                    Debug.DrawLine(edgeVertex1 , twinVertex1 , BaseColor);
                }
            }

            // 绘制平面法线
            if ((options & DebugHullFlags.PlaneNormals) != 0)
            {
                for (int i = 0; i < hull.FaceCount; i++)
                {
                    //得到质心和法线，画出一个箭头来表示法线。都是在世界空间下画，所以做了转换
                    var centroid = math.transform(t, hull.CalculateFaceCentroid(hull.GetFace(i)));
                    var normal = math.rotate(t, hull.GetPlane(i).Normal);
                    DebugDrawer.DrawArrow(centroid, normal * 0.2f, BaseColor);  
                }
            }

            // 绘制索引
            if ((options & DebugHullFlags.Indices) != 0)
            {
                var dupeCheck = new HashSet<Vector3>();
                for (int i = 0; i < hull.VertexCount; i++)
                {
                    // 因为是文本形式的，如果多个顶点处于相同的位置，则偏移标签。
                    var v = math.transform(t, hull.GetVertex(i));           
                    var offset = dupeCheck.Contains(v) ? (float3)Vector3.forward * 0.05f : 0;

                    DebugDrawer.DrawLabel(v + offset, i.ToString());
                    dupeCheck.Add(v);
                }
            }
        }
        
        // 调试绘制一个碰撞接触点集，方便看哪里碰撞相交了
        public static void DebugDrawManifold(NativeManifold manifold, Color color = default)
        {
            // 如果碰撞接触点集没有创建或者长度为0，直接返回，不绘制
            if (!manifold.IsCreated || manifold.Length == 0)
                return;

            // 如果没有传入颜色参数，则默认使用蓝色，并且设置透明度为0.3
            if (color == default)
                color = UnityColors.Blue.ToOpacity(0.3f);

            // 遍历每一个接触点
            for (int i = 0; i < manifold.Length; i++)
            {
                var start = manifold[i];// 当前接触点
                if (manifold.Length >= 2)
                {
                    // 如果有两个及以上点，绘制线段
                    // end点为前一个接触点，i==0时，连接最后一个点形成闭环
                    var end = i > 0 ? manifold[i - 1] : manifold[manifold.Length - 1];
                    Debug.DrawLine(start.Position, end.Position, color);                    
                }
                // 以球体的形式绘制当前接触点，半径0.02，颜色透明度0.8
                DebugDrawer.DrawSphere(start.Position, 0.02f, color.ToOpacity(0.8f));
            }
            // 将所有接触点的位置提取成Vector3数组，绘制凸多边形的轮廓，颜色为前面定义的color
            DebugDrawer.DrawAAConvexPolygon(manifold.ToArray().Select(cp => (Vector3)cp.Position).ToArray(), color);
        }
    }
}

实现效果:

大致流程就是：面检测，面检测，边检测

 3D SAT算法的本质特性

分离轴定理(SAT)在3D空间中的数学基础是超平面分离定理的实践应用。

• ​潜在分离轴数量​：从O(n)增长到O(n²)

  • 每个凸多面体的面法线（平均6-20个）
  • 每对边组合的叉积（对于n边多面体，约n²/2个）

• ​投影计算复杂度​：

  复杂度=O((FA​+FB​+EA​×EB​)×(VA​+VB​))

  其中F为面数，E为边数，V为顶点数

五、实际应用案例分析

5.1 大规模物理模拟场景

​测试环境​：

• 1000个凸多面体（平均12顶点）
• Ryzen 9 5950X @ 4.9GHz

​性能对比​：

总结

这种深度优化的技术方案，标志着Unity高性能物理计算的新范式，特别适用于元宇宙、数字孪生、大规模多人在线游戏等前沿领域，为实时交互体验树立了新的性能标杆，可广泛应用于游戏物理模拟等领域。