当前位置: 首页 > java >正文

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> : IJobwhere TFunc : struct, IBurstRefAction<T1, T2, T3, T4, T5> // TFunc 必须实现 IBurstRefAction 接口where T1 : unmanaged // T1 必须是非托管类型where T2 : structwhere T3 : structwhere T4 : structwhere 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 的实例 funcUnsafeUtility.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);  // 获取边1NativeHalfEdge* 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);  // 获取边2NativeHalfEdge* 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;
#endifnamespace 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;// 遍历每对边,所以迭代为+2for (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.3if (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.8DebugDrawer.DrawSphere(start.Position, 0.02f, color.ToOpacity(0.8f));}// 将所有接触点的位置提取成Vector3数组,绘制凸多边形的轮廓,颜色为前面定义的colorDebugDrawer.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

性能对比​:

方案帧时间(ms)内存占用(MB)
PhysX默认8.2320
纯C# SAT22.5210
Burst优化SAT3.8180
Burst+SIMD SAT1.6190

总结

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

http://www.xdnf.cn/news/16502.html

相关文章:

  • rust- 定义模块以控制作用域和隐私
  • 任务提醒工具怎么选?对比16款热门软件
  • 2025年Agent创业实战指南:从0到1打造高增长AI智能体项目
  • 撤销连续三年不使用注册商标一次下受理书!
  • Spring之【Bean的生命周期】
  • Android MQTT 长连接最佳实践技术分享
  • Amazon Relational Database Service (Amazon RDS)入门课
  • C++ 构造函数中阻止资源泄漏的实践探索
  • Linux驱动20 --- FFMPEG视频API
  • 【 Python 】Collections库权威指南
  • 【多模态】天池AFAC赛道四-智能体赋能的金融多模态报告自动化生成part1-数据获取
  • 卫星图像数据集在农业领域的应用
  • Leetcode力扣解题记录--第136题(查找单数)
  • Redis C++客户端——命令使用
  • Vue 框架 学习笔记
  • 9-大语言模型—Transformer 核心:多头注意力的 10 步拆解与可视化理解
  • 【在Unity游戏开发中Dictionary、List介绍】
  • MongoDB索引及其原理
  • 2025 DevOps开源工具全景指南:构建面向未来的智能交付体系
  • 代码随想录训练因第三十天| 39.组合总和 40.组合总和ll 131.分割回文串
  • PyTorch武侠演义 第一卷:初入江湖 第7章:矿洞中的计算禁制
  • 链表算法综合——重排链表
  • 望言OCR视频字幕提取2025终极评测:免费版VS专业版提全方位对比(含免费下载)
  • 重生之我在暑假学习微服务第二天《MybatisPlus-下篇》
  • 主要分布于内侧内嗅皮层的层Ⅲ的边界向量细胞(BVCs)对NLP中的深层语义分析的积极影响和启示
  • @RefreshScope 核心原理深度解析:Spring Boot 的动态魔法
  • Node.js特训专栏-配置与环境部署:20.PM2进程守护与负载均衡
  • Rust Web 全栈开发(十一):WebAssembly 尝鲜
  • 数学建模——模糊综合评价
  • 【C语言网络编程基础】TCP 服务器详解