与基因座网格碰撞

Question

我想避免我的球员站在墙内.每个游戏勾选我的玩家移动一些小距离和/或旋转.

TL; DR请提供经典线段的变体 - > - 三角交叉算法,它也会返回近乎未命中,或以另一种方式解决问题 如果线段在三角形的给定距离内通过,则线段相交.这个问题有很多细微之处,例如三角形的轨迹角是圆角的,如果线段与三角形相切.

我有通常的光线/三角交叉码.

然而,射线是移动玩家的非常差的近似!我有玩家中心缺失边缘但玩家网格穿过它们的问题.

如何有效地确定玩家在3D环境中与墙壁和障碍物碰撞的时间和位置？

一种通用方法是具有接近未命中的三角形代码,其中射线是球形圆柱体.

我试过的一般解决方案是想象玩家是一个球体; 从内向外翻转,我试图制作一个比实际墙壁大半径的网格,并对其进行碰撞.我想计算一个在这个网格前面有一定距离的网格,即一个立方体会扩展成一个稍大的立方体,边缘和圆角都是圆角.(我的网格比一个立方体更不规则.想象一下锅炉房内部的网格表示,并想象试图计算距离所有墙壁和锅炉和门框等20厘米的网格.)这是一个围绕桶的简单网格:

对于每个面,我可以计算表面法线; 这就是我怎么知道哪种方式'出'.

我的头脑风暴让我想象每个面部的法线乘以固定的距离,然后发出一个带有相应偏移的三角形.

然而,这会在边缘留下孔,并且可能(？)导致一些边缘穿过非常紧的锐角？

我也可以想象将每个边缘连接成球形圆柱体等等.

我用于上面的桶的方法是计算共享顶点的所有面的平均法线,然后将其乘以碰撞半径.它不能很好地应对锐角,如果在相对侧的面之间错误地共享顶点,该怎么办？

我将在Javacsript中计算此网格,然后执行光线交叉.所以性能也是一个考虑因素.进行碰撞检测时,太精细的细网格将是昂贵的.

如何有效地计算出足够好的基因座网格？或者做loci感知模糊三角交叉？或者有更好的方法来进行碰撞,并且能以某种方式模拟物体以弧线而不是直线移动吗？

Answer 1

（没有人获得赏金：（ gamedev.stackexchange 上的 Nathan Reed帮助解释了术语。它被称为胶囊三角形交叉点。）

它的数学令人惊讶地棘手，谷歌搜索并没有找到太多现成的代码可以复制。

标准方法是按半径挤压三角形，并添加将三个三角形边中的每一个都测试为胶囊。

要挤出三角形，只需将三角形的法线乘以胶囊半径，将每个三角形角偏移该量，然后对其进行法线线段三角形测试。

每个三角形边的胶囊测试相当昂贵，因为您必须进行三次。使用三角形测试中的重心坐标可能有助于避免一些胶囊边缘测试，但我还没有考虑清楚。您还可以避免对与其他足够钝的三角形共享的边进行胶囊测试；你可以计算这个并标记那些边缘。我还没有打扰。

我发现预先计算每个面的边界球并与胶囊的边界球进行相交测试是一种超级便宜的方法，可以在大多数情况下避免这种昂贵的测试。我还预先计算了每张脸的法线，尽管这是一个较小的胜利。

由于测试成本如此之高，最好的办法是将玩家视为单个球体，并让相交代码给出面相交的列表。然后，您可以将玩家建模为一系列编队飞行的较小球体，并且您只需对第一次通过较大球体时发现的面进行胶囊面相交代码。