时间戳

首页 > 解决方案 > 三角-三角碰撞检测问题

c++ - 三角-三角碰撞检测问题

问题描述

我正在为一个大学项目开发​​游戏引擎，但我无法让碰撞检测系统工作。我发现这篇论文解释了由 Chaman-Leopoldj 创建的三角形-三角形碰撞检测算法，但不知何故我无法实现它。我知道它有点长，但算法可以在第 8 页和第 22-24 页找到

这是我写的代码：

这是包装函数

bool Octree::triangleTriangleIntersection(glm::vec3 A, glm::vec3 B, glm::vec3 C, glm::vec3 P, glm::vec3 Q, glm::vec3 R) {
glm::vec3 U = B - A;
glm::vec3 V = C - A;
glm::vec3 S = Q - P;
glm::vec3 T = R - P;
glm::vec3 AP = P - A;

float sigma = dot(U * V, U * V);
glm::vec3 alpha = (S * (U * V)) / sigma;
glm::vec3 beta = (T * (U * V)) / sigma;
glm::vec3 gamma = (AP * (U * V)) / sigma;

float alphau = dot(alpha, U);
float alphav = dot(alpha, V);
float alphauv = dot(alpha, U - V);
float gammau = dot(gamma, U);
float gammav = dot(gamma, V);
float gammauv = dot(gamma, U - V);
float betau = dot(beta, U);
float betav = dot(beta, V);
float betauv = dot(beta, U - V);

float Xm, XM, Sm = 0, SM = 1;
float Ym, YM, Tm = 0, TM = 1;

if (findSolution_x(-gammau, alphau, betau, 1 - gammau, -1 - gammav, alphav, betav, -gammav, Xm, XM)) {
    if (Xm > Sm) Sm = Xm;
    if (XM < SM) SM = XM;
}
else {
    return false;
}
if (findSolution_x(-gammau, alphau, betau, 1 - gammau, -gammauv, alphauv, betauv, 1 - gammauv, Xm, XM)) {
    if (Xm > Sm) Sm = Xm;
    if (XM < SM) SM = XM;
}
else {
    return false;
}
if (findSolution_x(-1 - gammav, alphav, betav, -gammav, -gammauv, alphauv, betauv, 1 - gammauv, Xm, XM)) {
    if (Xm > Sm) Sm = Xm;
    if (XM < SM) SM = XM;
}
else {
    return false;
}
if (Sm > SM)
    return false;
else {
    float delta = (SM - Sm) / 20;
    for (float s = Sm; s <= SM; s += delta) {
        if (findSolution_y(-gammau, alphau, betau, 1 - gammau, -1 - gammav, alphav, betav, -gammav, s, Ym, YM)) {
            if (Ym > Tm) Tm = Ym;
            if (YM < TM) TM = YM;
        }
        else {
            return false;
        }
        if (findSolution_y(-gammau, alphau, betau, 1 - gammau, -gammauv, alphauv, betauv, 1 - gammauv, s, Ym, YM)) {
            if (Ym > Tm) Tm = Ym;
            if (YM < TM) TM = YM;
        }
        else {
            return false;
        }
        if (findSolution_y(-1 - gammav, alphav, betav, -gammav, -gammauv, alphauv, betauv, 1 - gammauv, s, Ym, YM)) {
            if (Ym > Tm) Tm = Ym;
            if (YM < TM) TM = YM;
        }
        else {
            return false;
        }
        if (Tm > TM)
            return false;
        else
            return true;
    }
}

return false;}

解决_x

bool Octree::findSolution_x(float m, float a, float b, float n, float M, float A, float B, float N, float& Xm, float& XM) {

const float epsilon = 0.00001;

float denom = (a*B- A* b);

float Sm1, SM1;

Sm1 = (m* B- N* b);
SM1 = (n* B- M* b);

if (b< 0 || B< 0) {
    Sm1 *= -1;
    SM1 *= -1;
}

Sm1 /= denom;
SM1 /= denom;

float Sm1Rounded = round(Sm1);
float SM1Rounded = round(SM1);

if (abs(Sm1Rounded - Sm1 <= epsilon)) Sm1 = Sm1Rounded;
if (abs(SM1Rounded - SM1 <= epsilon)) SM1 = SM1Rounded;

Xm = Sm1;
XM = SM1;

if (denom == 0) {
    Xm *= -1;
}

return true;}

解决_y

bool Octree::findSolution_y(float m, float a, float b, float n, float M, float A, float B, float N, float x, float& Ym, float& YM) {

const float epsilon = 0.00001;

float Sm1, SM1, Sm2, SM2;

Sm1 = m- (a* x);
Sm2 = M- (A* x);
SM1 = n- (a* x);
SM2 = N- (A* x);

if (b< 0 || B< 0) {
    Sm1 *= -1;
    SM1 *= -1;
    Sm2 *= -1;
    SM2 *= -1;
}

if (Sm1 > SM1 || Sm2 > SM2) return false;

Sm1 /= b;
SM1 /= b;
Sm2 /= B;
SM2 /= B;

float Sm1Rounded = round(Sm1);
float SM1Rounded = round(SM1);
float Sm2Rounded = round(Sm2);
float SM2Rounded = round(SM2);

if (abs(Sm1Rounded - Sm1 <= epsilon)) Sm1 = Sm1Rounded;
if (abs(SM1Rounded - SM1 <= epsilon)) SM1 = SM1Rounded;
if (abs(Sm2Rounded - Sm2 <= epsilon)) Sm2 = Sm2Rounded;
if (abs(SM2Rounded - SM2 <= epsilon)) SM2 = SM2Rounded;

if (param2 > 0 && param6 > 0) {
    Sm1 >= Sm2 ? Ym = Sm1 : Ym = Sm2;
    SM1 >= SM2 ? YM = SM2 : YM = SM1;
}
else if (param2 > 0) {
    Ym = Sm1;
    YM = SM1;
}
else if (param6 > 0) {
    Ym = Sm2;
    YM = SM2;
}

return true;}

我怀疑我在我的一个 if 中设置了错误的条件，但我只是按照论文的指导方针进行的，所以我真的不知道。希望你们能帮助我。

编辑：需要 epsilon 来舍入低于某个误差的值。这是一个源自 assimp 没有正确读取 OBJ 值的问题，例如将 1.000000 变成 1.0000045。

标签： c++collision-detectiongame-engineoctree

解决方案

我不会尝试为您调试您的代码，并且有人会因为不完整的答案而对我投反对票，但我将提供一些基本建议。

这是调试这么大的东西的基本建议。在我看来，您需要设置一个简单的测试。编写一个与您的代码链接的小程序。手动创建您知道碰撞的两个三角形，然后查看您的代码是否检测到它。

不？弄清楚它们是如何碰撞的以及你应该如何检测到它，然后将打印语句添加到你的代码中应该发生碰撞的地方，看看为什么它没有捕捉到它。

您可能想要做的是使用一些纸张。布置几个三角形，然后手动（不涉及计算机）逐步执行您正在使用的代码，看看它是否有意义。

如果没有，请提出您自己的代码。我认为您可以将三角形碰撞定义为：

  1. 如果 T1 的任何段与 T2 的任何段相交。您应该能够找出测试两条线段是否相交的方法，然后将 T1 的所有线段与 T2 运行。

  2. 或者，如果一个三角形完全封装在另一个三角形内。一个大三角形和一个小三角形。

这是编码的乐趣和沮丧的一部分——学习理解你正在使用的算法。

推荐阅读