삼각형과 삼각형의 충돌 검사

3차원 공간에서 두 삼각형의 충돌 검사는 매우 중요한 문제로, **Separating Axis Theorem (분리축 정리, SAT)**를 기반으로 수행하는 것이 일반적이다. 이 방법은 두 물체가 충돌하지 않으면 이들을 분리하는 축이 반드시 존재한다는 사실에 기반한다. 즉, 분리축이 하나라도 존재하면 두 삼각형은 충돌하지 않으며, 그렇지 않으면 충돌이 발생한 것이다.

삼각형 정의

두 삼각형 $T_1$과 $T_2$는 각각 3개의 꼭짓점으로 정의된다:

• 삼각형 $T_1$: $\mathbf{v}{1a}, \mathbf{v}{1b}, \mathbf{v}_{1c}$

• 삼각형 $T_2$: $\mathbf{v}{2a}, \mathbf{v}{2b}, \mathbf{v}_{2c}$

분리축 후보

충돌 여부를 확인하기 위해 아래의 여러 분리축을 검토한다:

1. 각 삼각형의 법선 벡터 (Plane Normal Vectors) 삼각형들이 서로 다른 평면에 있을 때, 그 평면 간의 충돌 여부를 확인하기 위해 각 삼각형의 법선 벡터를 이용한다. 각 삼각형의 법선 벡터는 해당 평면의 수직 벡터이다:

   • 삼각형 $T_1$의 법선 벡터:

$$\mathbf{n}_1 = (\mathbf{v}_{1b} - \mathbf{v}_{1a}) \times (\mathbf{v}_{1c} - \mathbf{v}_{1a})$$

• 삼각형 $T_2$의 법선 벡터:

$$\mathbf{n}_2 = (\mathbf{v}_{2b} - \mathbf{v}_{2a}) \times (\mathbf{v}_{2c} - \mathbf{v}_{2a})$$

1. 두 삼각형의 변 벡터와 서로의 변 벡터의 외적 삼각형 간의 변들이 교차하는지를 확인하기 위해, 각 삼각형의 변과 다른 삼각형의 변 벡터의 외적을 분리축으로 사용한다. 이 외적 벡터들이 충돌을 감지할 수 있는 분리축을 제공한다:

$$\mathbf{n}_{edge} = (\mathbf{v}_{1i} - \mathbf{v}_{1j}) \times (\mathbf{v}_{2k} - \mathbf{v}_{2l})$$

여기서 $i, j, k, l \in {a, b, c}$는 삼각형의 변을 의미한다.

분리축에서의 투영

각 분리축에 대해 두 삼각형의 꼭짓점을 투영한 후, 그 투영 범위가 겹치는지를 확인한다:

• 삼각형 $T_1$의 투영 범위: 각 꼭짓점 $\mathbf{v}{1a}, \mathbf{v}{1b}, \mathbf{v}_{1c}$을 분리축 $\mathbf{n}$에 대해 투영하여 최소값과 최대값을 계산한다:

$$p_{1i} = \mathbf{v}_{1i} \cdot \mathbf{n}, \quad \text{(i = a, b, c)}$$

투영된 값 중 최소값과 최대값을 계산하여 해당 축에서의 투영 범위를 얻는다.

• 삼각형 $T_2$에 대해서도 동일한 방식으로 투영을 수행하고 투영 범위를 계산한다.

충돌 여부 판단

모든 분리축에 대해 두 삼각형의 투영 범위가 겹치지 않는 분리축이 하나라도 존재한다면, 두 삼각형은 충돌하지 않는다. 하지만 모든 분리축에서 투영 범위가 겹치면 두 삼각형은 충돌한 것이다.

추가 고려 사항

특수한 경우에 대해 다음과 같은 추가 검사를 할 수 있다:

1. 삼각형이 같은 평면에 있는 경우: 두 삼각형이 동일한 평면에 위치하는 경우, 법선 벡터의 방향이 동일해질 수 있다. 이 경우에는 법선 벡터를 사용한 분리축 검사가 효과적이지 않으므로, 평면 내부에서의 교차 여부를 확인해야 한다. 이를 위해 삼각형 간의 꼭짓점이 다른 삼각형의 내부에 포함되는지, 혹은 두 삼각형의 변이 서로 교차하는지를 추가로 검사해야 한다.

2. 삼각형의 꼭짓점이 다른 삼각형의 내부에 있는 경우: 한 삼각형의 꼭짓점이 다른 삼각형 내부에 위치하는 경우, 이는 충돌로 간주된다. 이를 확인하려면 각 삼각형의 꼭짓점이 다른 삼각형의 면적 내에 포함되는지를 검사할 수 있다.

C++ 구현

두 삼각형 간의 충돌 검사를 C++와 Eigen 라이브러리를 사용하여 구현하는 방법을 소개하겠다. 여기에서는 **Separating Axis Theorem (SAT)**을 이용한 충돌 검사를 수행하며, Eigen을 사용하여 벡터 연산을 처리한다.

#include <Eigen/Dense>
#include <iostream>
#include <vector>

// 삼각형을 정의하는 구조체
struct Triangle {
    Eigen::Vector3d v1, v2, v3;
};

// 벡터 외적을 사용해 법선 벡터를 계산하는 함수
Eigen::Vector3d computeNormal(const Triangle& tri) {
    return (tri.v2 - tri.v1).cross(tri.v3 - tri.v1).normalized();
}

// 삼각형의 꼭짓점들을 분리축에 투영하고, 투영 범위를 계산하는 함수
void projectOntoAxis(const Triangle& tri, const Eigen::Vector3d& axis, double& min, double& max) {
    // 각 꼭짓점을 분리축(axis)에 투영하여 최소, 최대 값을 찾음
    double p1 = tri.v1.dot(axis);
    double p2 = tri.v2.dot(axis);
    double p3 = tri.v3.dot(axis);

    // 투영된 값 중 최소값과 최대값을 계산
    min = std::min({p1, p2, p3});
    max = std::max({p1, p2, p3});
}

// 분리축을 기준으로 두 삼각형이 충돌하는지 확인하는 함수
bool isOverlapping(const Triangle& tri1, const Triangle& tri2, const Eigen::Vector3d& axis) {
    double min1, max1, min2, max2;

    // 각 삼각형을 분리축에 투영
    projectOntoAxis(tri1, axis, min1, max1);
    projectOntoAxis(tri2, axis, min2, max2);

    // 투영된 값이 겹치는지 여부 확인
    return !(max1 < min2 || max2 < min1);
}

// 두 삼각형 간의 충돌 여부를 확인하는 함수
bool checkTriangleCollision(const Triangle& tri1, const Triangle& tri2) {
    // 1. 각 삼각형의 법선 벡터를 계산
    Eigen::Vector3d normal1 = computeNormal(tri1);
    Eigen::Vector3d normal2 = computeNormal(tri2);

    // 분리축 리스트
    std::vector<Eigen::Vector3d> axes;

    // 2. 삼각형의 법선 벡터를 분리축에 추가
    axes.push_back(normal1);
    axes.push_back(normal2);

    // 3. 두 삼각형의 변 벡터에 대한 외적을 분리축으로 추가
    std::vector<Eigen::Vector3d> tri1Edges = {tri1.v2 - tri1.v1, tri1.v3 - tri1.v2, tri1.v1 - tri1.v3};
    std::vector<Eigen::Vector3d> tri2Edges = {tri2.v2 - tri2.v1, tri2.v3 - tri2.v2, tri2.v1 - tri2.v3};

    for (const auto& edge1 : tri1Edges) {
        for (const auto& edge2 : tri2Edges) {
            Eigen::Vector3d axis = edge1.cross(edge2);
            if (axis.norm() > 1e-6) { // 축의 유효성을 확인
                axes.push_back(axis.normalized());
            }
        }
    }

    // 4. 각 분리축에 대해 충돌 여부를 확인
    for (const auto& axis : axes) {
        if (!isOverlapping(tri1, tri2, axis)) {
            return false; // 분리축이 존재하면 충돌하지 않음
        }
    }

    return true; // 모든 분리축에서 투영이 겹치면 충돌함
}

int main() {
    // 삼각형 두 개 정의
    Triangle tri1 = {
        Eigen::Vector3d(0.0, 0.0, 0.0),
        Eigen::Vector3d(1.0, 0.0, 0.0),
        Eigen::Vector3d(0.0, 1.0, 0.0)
    };

    Triangle tri2 = {
        Eigen::Vector3d(0.5, 0.5, 0.0),
        Eigen::Vector3d(1.5, 0.5, 0.0),
        Eigen::Vector3d(0.5, 1.5, 0.0)
    };

    // 충돌 여부 확인
    if (checkTriangleCollision(tri1, tri2)) {
        std::cout << "삼각형들이 충돌한다.\n";
    } else {
        std::cout << "삼각형들이 충돌하지 않는다.\n";
    }

    return 0;
}

주요 설명:

1. computeNormal 함수: 삼각형의 법선 벡터를 계산한다. 이 법선 벡터는 분리축으로 사용된다.

2. projectOntoAxis 함수: 삼각형의 꼭짓점들을 분리축에 투영하여 최소 및 최대 값을 계산한다.

3. isOverlapping 함수: 분리축에서 두 삼각형의 투영이 겹치는지 확인한다.

4. checkTriangleCollision 함수: 각 분리축에서 충돌 여부를 검사한다. 법선 벡터뿐만 아니라 변의 외적을 분리축으로 사용하여 교차 여부를 확인한다.