结论:关于碰撞检测的综述
最编程
2024-08-14 11:59:14
...
Sweep and Prune:
1.将物体的AABB分离到三个坐标轴上。得到若干个区间。
2.根据区间的终点坐标由小到大排序。
3.逐个遍历排序结果,当遇到一个区间的起始点的时候,就将这个区间放到一个列表中;当遇到一个区间的终点时,就将这个区间从列表中清除。
当在列表中存在区间,而又遇到一个新区间的起始点时,则遇到的区间与列表中的所有区间重叠。
4.如果一对物体在三个坐标轴上的区间都重叠,那么他们的AABB相叠。
Mid-phase碰撞检测
碰撞检测树就是将要碰撞的网格分离成多个部分,并将这些部分按树的结构组织起来。我的碰撞检测树就是一BVH树,和标准的AABB碰撞检测树相比,AABB树是2叉树,我的树的节点数是不定的。
两种建树过程如下:
AABB: 1.计算三角形集合的AABB包围体 |
我的碰撞检测树: 1.计算三角形集合的包围体 2.计算三角形集合的几何重心,将几何重心视为原点,按三个坐标平面将三角形集合分成8部分 3.穿过这个坐标平面的三角形按中点分配到平面一侧,如果中点还在平面上,随便分配 4.如果有的部分中没三角形,那么去掉它。如果只有一部分且这部分包含多个三角形,强行随便的将这部分分成多部分(防止死递归)。 5.将分出的n部分作为子节点继续分割(步骤1),直到分出的部分只有一个三角形 |
包围体有: |
包围球 |
碰撞检测树一般在物体定坐标系下建立出来
可以根据情况,为不同节点选择不同类型的包围体,使得包围体包围得最紧凑
碰撞检测:
一个几何图形vs树
按深度优先或广度优先遍历树,对于非最末级节点,判断几何图形是否和节点包围体相交,如果相交那么继续遍历它的子节点。对于最末级节点,还要进行几何图形和最末节点所对应的三角形求交。这样,遍历完一次即可找到所有碰撞。
注:
1.碰撞检测需检测出碰撞点,碰撞法向量,和刺穿深度
2.球和三角形碰撞:
以下过程按顺序执行,一旦相交就return,停止和这个三角形继续检测:
(1).判断球心与三角面垂直且过三边的平面的位置关系,如果被包围,那么直接判断球心到三角面所在平面距离是否<=半径
(2).根据(1)的结果,如果球心在哪条边外,那么试着和那条线段求交
(3).判断球心到三角形某顶点距离<=半径
3.球和棱、点碰撞,碰撞法向量为那个面在碰撞点的切平面的法向量
4.通过更精确的包围体测试,会遍历更少节点,但更精确的包围体测试一般会花更多时间。
树vs树
对于一对节点,判断两个节点的包围体是否相交。如果相交,那么测试它们的子节点包围体是否相交。
如果有一个节点是最末级节点,它对应着一个三角形,另一个是一个非最末级节点,那么问题转化为上面“一个几何图形vs树”。
如果两个节点都是最末级节点,那么进行三角形求交。
注:
对于刚体,它们会转动,转动了的AABB可以用AABB加上一个刚体变换矩阵表示。也可懒一些,直接把树放入全局坐标系下,更新树。
树的更新:
如果物体不是刚体,可能会形变,这就需要更新树。一般自下而上的更新树。先根据最末级节点对应的三角形,更新最末级节点。然后一级一级更新上面的节点,使它们的包围体包住子节点。
以后安排(先把想法记下来)
物体破裂 :
将物体网格表示成一张无向图(不用邻接矩阵表示),在压强足够大的地方细化网格,细化出的部分作为图的一部分,然后从压强足够大的几个顶点遍历图。遍历时根据物体物理材质选择图的边(第一条边应选择最和切向量正交的),将其并入断裂线,必要时就细化网格,直到这条线首尾封闭。这样做是因为不同材质的物体,其断裂口有的光滑,有的粗糙,甚至有尖刺。这样应该能生成一条满意的断裂线。然后取出子图,成为分裂出的物体的网格的一部分。不过断口的填充就暂无想法了……
脚本:
设想了一种托管脚本。先写好脚本,经过编译器将其编译为自定的较低级中间语言,或者直接IL代码。运行前加载时,对其进行JIT编译,除了.Net的JIT以外,还有自己的一些,当然肯定是自己先处理后再交给.Net……这样脚本最终就是本机代码,执行速度比解释型的快,而且异常也不用一下一下的考虑。
一开始编译为直接IL代码时,不能直接转为它的字节码,而是自己规定的字节码,但其指令还是一一对应的(就是把IL代码用2进制形式表示了一下)。这主要是因为代码中有一些东西,还不能直接转为标准的IL字节码
最终应该可以构建复杂的物体,比如一个人,由Joint、刚体(骨骼和关节)和柔体(头发和肥膘)组成。他做个什么动作要是碰到了什么倒是自然能模拟出来。不过他的行走,怎么维持重心不好说,我的想法是对已做好的动画解析,将其数值微分,最后算出各部分的作用力……维持重心不管他用那些肌肉,维持重心的力 应该包括在里面……
以前有外国人拟做过类似的东西,第六届全国中小学电脑制作活动上还有即将得一得奖的抄过——botz,一个2D质点弹簧系统模拟程序,它的欧拉法积分不严密(或者说就不是),碰撞检测就和边界检查了一下,但是要注意他的“肌肉”思想,质点弹簧系统组成机器人,然后肌肉伸缩运动,我这个应该和那个在这一点有着类似之处。更接近一点的东西就是Dr.Jan Bender的那些机器人了。
当然稍微遥远的东西别想得太多,毕竟还有不少东西未完成……
推荐阅读
-
结论:关于碰撞检测的综述
-
RCWL-0516/RCWL-9196模块简介 & 微波感应模块简介-前言 RCWL-0516是一款由无锡日晨物联科技有限公司开发的微波感应模块(资料下载),见图0.0、图0.1,用于检测物体(人体)移动,具有以下特征: 1.穿透感应:可穿透适当厚度的玻璃、木板以及墙壁。 2.抗干扰:不受温度、灰尘等环境因素影响。 3.感应距离:5~8m(可调,见后文) 4.可重复触发、触发时间可调(见后文) 5.工作电压:3.3~18V 6.稳压输出:提供3.3V电压输出(最大100mA) 7.夜晚自动工作:外接光敏电阻和一个电阻实现 当模块检测到物体在感应范围内移动时,OUT引脚输出一段时间的高电平(该时间可通过电容“C-TM”调节,见后文);若在输出高电平期间再次检测到物体移动,高电平持续时间将延长一段时间(又称为重复触发),该时间不可叠加。 模块使用的注意事项如下,示意图见图0.2: 1. 感应面正前方不能有金属遮挡。 2. 感应面前后方预留2cm以上空间。若对灵敏度要求很高,应预留4cm以上距离,且模块后方遮挡空间应尽可能小。 3. 模块与安装载体平面尽可能平行。 4. 有元器件面为正感应面,反面为负感应面,负感应面效果略差。 5. 相同模块,单个个体之间间距应大于2m。 图0.0-模块实物图(正) 图0.1-模块实物图(反) 图0.2-感应区域示意图 原理 关于此模块的原理,有2种主流观点,这些观点所争论的焦点在于哪种解释是最主要的: 1. 以Roger Clark为代表的“反射”解释:模块上的振荡器会发射出微波信号,位于模块感应区域内的物体会反射模块所发出的微波信号,这些反射信号又被模块所接收,接收到的反射信号会改变流经晶体管发射极的电流I。外界环境不变的情况下,模块内部的调节电路会稳定振荡器,此时振荡器处于稳定状态,电流I也处于稳定;当外界环境发生变化(例如,有物体进入感应区域),该物体的反射信号会使振荡器暂时失去稳定,从而导致电流I发生变化。模块通过检测该电流I的变化,以检测物体移动。此过程中,发射频率的变化只是由于振荡器受反射信号影响而进入一个“暂稳态”所导致。 2.以Joe Desbonnet为代表的“多普勒效应”解释:位于模块感应区域内的物体会反射模块所发出的微波信号,这些反射信号的频率由于物体移动而发生改变(多普勒效应)。模块通过对比发射与反射频率的差异,以判断是否有物体进入感应区域。 应用 降低感应距离:模块背面丝印“R-GN”处添加1MΩ的电阻,模块的感应距离可降低到5m;如果不接,感应距离为7m。 调节触发时间:模块背面丝印“C-TM”处添加不同容值的电容,可以调节触发时间(“C-TM”电容容值的选择见后文);若不安装电容,触发时间为2~4s。 夜晚自动工作:模块正面丝印“CDS”处添加光敏电阻、模块背面丝印“R-CDS”处添加适当阻值的电阻,可控制模块在夜晚自动工作。“CDS”与“R-CDS”的选择方法见后文。 以上应用的实际电路请参考图1.0、图1.1。 图1.0-测试电路(正) 图1.1-测试电路(反) 测试 测试由5部分组成: 1.测量模块处于不同状态时的功耗,见表0.0。 2.未接入电阻“R-GN”时,测试模块最大感应距离,见表0.1。 3.接入电阻“R-GN”,测试模块最大感应距离,见表0.2。 4.以下步骤将介绍如何根据确定的光敏电阻“CDS”,选择电阻“R-CDS”的阻值,以实现模块夜间自动工作的功能。 1-白天,接入可调电阻“R-CDS”(推荐2MΩ)、光敏电阻“CDS”。 2-触发模块后(在模块面前走动),调节可调电阻,直到触发消失。再次尝试触发模块,正常情况下,模块应该无法被触发(如果可以触发,重复步骤2)。 3-将光敏电阻感光面遮住,尝试触发模块,正常情况下,模块应该可以被触发(如果无法触发,重复步骤3)。 4-此时可调电阻阻值即为电阻“R-CDS”的正确阻值。 5.电容“C-TM”分别接入不同容值的无极电容,测试模块单次触发所持续的时间,见表0.3。 测试条件 总电流(mA) 总功耗(mW) +5V供电电压,模块未触发 3.63 18.15 +5V供电电压,模块被触发 4.33 21.65 表0.0-模块功耗信息 正面最大感应距离(M) 6 反面最大感应距离(M) 2 表0.1-未接入电阻“R-GN”时,模块最大感应距离[1] 正面最大感应距离(M) 5 反面最大感应距离(M) 1 表0.2-接入电阻“R-GN”=1MΩ时,模块最大感应距离[1] 电容“C-TM”容值 悬空 103(10nF) 104(100nF) 224(220nF) 474(470nF) 105(1uF) 理论单次触发时间(s) 2~4 6 30 66 140 300 实际单次触发时间(s) 3 6 32 67 122 210 表0.3-电容“C-TM”容值 vs. 模块单次触发持续时间 结论 RCWL-0516是一款性价比高的人体感应模块,具有以下优缺点: 优点:
-
10,000字文章 | 关于多目标跟踪的最新综述(基于Transformer/图模型/检测和关联/双子网络)(下一篇)
-
一些关于对称多项式的结论
-
关于网络技术的综述