삼각형 - 삼각형 교차 테스트

StackOverflow https://stackoverflow.com/questions/1903258

문제

3D 환경에서 삼각형-삼각형 교차 테스트를 이해하고 구현하기 위한 튜토리얼이나 가이드가 있는지 알고 싶습니다.(교차로가 어디서 발생했는지 정확히 알 필요는 없지만 교차로가 발생했다는 것만 알 수 있습니다)

이론적인 PDF를 따라 구현하려고 했으나 꽤 막혔습니다.

  1. 삼각형 2의 평면 방정식을 계산합니다.
  2. 삼각형 1의 모든 점이 같은 면에 있으면 사소한 것으로 기각합니다.
  3. 삼각형 1의 평면 방정식을 계산합니다.
  4. 삼각형 2의 모든 점이 같은 면에 있으면 사소한 것으로 기각합니다.
  5. 교차선을 계산하고 가장 큰 축에 투영합니다.
  6. 각 삼각형의 간격을 계산합니다.
  7. 간격을 교차시킵니다.

이 가이드의 포인트 5.나는 무엇을 요구하는지 정말로 모릅니다(5,6,7 모두).XD

저는 수학에 대한 지식이 높지 않기 때문에(글쎄요, 저는 대학에서 두어 번의 시험을 통해 제게 준 것을 알고 있습니다(저는 원시 프로그래머입니다 XD)), 저에게 최대한 간단하게 설명해주세요.:D (Google에서 검색을 시도했지만 대부분의 링크는 내가 별로 알고 싶지도 않고 이해하지도 못하는 공식으로 가득 찬 4-5페이지 정도를 가리킵니다.)

도와 주셔서 감사합니다

도움이 되었습니까?

해결책

당신은 말했다:

3D 환경에서 삼각형 삼각형 교차로 테스트를 이해하고 구현하기위한 튜토리얼이나 가이드가 있는지 알고 싶습니다.

그리고 당신은 이렇게 말했습니다.

대부분의 링크는 내가 정말로 알고 싶지 않은 공식으로 가득 찬 4-5 페이지를 가리 킵니다.

나는 그 두 진술이 완전히 서로 모순된다는 점에 주목합니다.그래서 그것은 무엇입니까?삼각형-삼각형 교차가 어떻게 작동하는지 이해하고 싶습니까, 아니면 작동하는 구현을 원하지만 이해하지 못합니까?

모든 웹페이지가 다음과 같은 내용으로 가득 차 있는 것은 아닙니다. 불필요한 수학.모든 수학은 필요한 교차 알고리즘이 어떻게 작동하는지 이해합니다.처음부터 시작하여 모든 것이 어떻게 작동하는지 배우십시오.

5, 6, 7단계는 단어의 의미를 알면 이해하기 쉽습니다.교차선은 두 평면이 교차하여 만들어진 선입니다.각 삼각형은 평면에 놓여 있습니다.세 가지 경우가 있습니다:

  • 평면은 평행하고 교차하지 않습니다.삼각형은 분명히 교차하지 않습니다.
  • 비행기는 같은 비행기입니다.삼각형은 만날 수도 있고 그렇지 않을 수도 있습니다.
  • 평면은 한 선에서 만나는 두 개의 서로 다른 평면입니다.삼각형이 교차하는 경우 분명히 해당 선에서 교차해야 합니다.

우리가 세 번째 경우에 있다고 가정해보자.첫 번째 삼각형에 포함된 교차선의 세그먼트를 계산합니다.두 번째 삼각형에 있는 교차선의 세그먼트를 계산합니다.이제 문제는 "이 세그먼트가 겹치는가?"입니다.

세그먼트를 편리한 축에 투영하고 해당 축의 선 세그먼트가 겹치는지 확인하여 이를 해결할 수 있습니다.기본적으로 다음과 같이 작동합니다.그림자가 축에 떨어지도록 선분에 빛을 비추고 있다고 상상해보십시오.축의 그림자가 교차하는 경우 선분도 교차해야 합니다.축의 그림자 사이에 간격이 있는 경우 분명히 선분 사이에 간격이 있어야 하며 따라서 삼각형이 교차하지 않습니다.

이것이 어떻게 작동하는지 이해하고 싶다면 이해해야 한다는 사실을 피할 수 없습니다. 모두 이것들은 평면이 교차하는 방식과 축에 대한 투영이 작동하는 방식을 계산하는 모든 대수입니다.모두 필요합니다.그리고 그 모든 것들은 더 복잡한 변환, 투영 등이 만들어지는 기본 빌딩 블록이므로 더 나아가고 싶다면 기본 사항을 철저히 이해하십시오.

다른 팁

내 대답은 간단합니다 ...이 문제는 임의의 좌표계에서는 어렵 기 때문에 문제를 쉽게 만드는 것으로 변경하십시오. XNA의 매트릭스 클래스에는 Createlookat 기능이 있으며 모든 Verticies에 유용한 변환을 만들 수 있습니다.

다음 예는 최적화되지 않으며 솔루션을 이해하기 위해서만 작성됩니다. 몇 가지 벡터 변환과 함께 예외 및 해당 IF 문을 모두 제거 할 수 있습니다. 

    public static bool CheckColision(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c)
    {//rotates each edge of the first triangle to the Z axis and checks the second triangle against it then repeats with the second one against the first, and lastly checks to see if all points of the second triangle are on the same side as the first
        if(! CheckColisionLookAt(t1a, t1b, t1c, t2a, t2b, t2c))
            return false;
        if (!CheckColisionLookAt(t1b, t1c, t1a, t2a, t2b, t2c))
            return false;
        if (!CheckColisionLookAt(t1c, t1a, t1b, t2a, t2b, t2c))
            return false;

        if (!CheckColisionLookAt(t2a, t2b, t2c, t1a, t1b, t1c))
            return false;
        if (!CheckColisionLookAt(t2b, t2c, t2a, t1a, t1b, t1c))
            return false;
        if (!CheckColisionLookAt(t2c, t2a, t2b, t1a, t1b, t1c))
            return false;

        return CheckColisionAllOnOneSide(t1a, t1b, t1c, t2a, t2b, t2c);
    }

    public static bool CheckColisionAllOnOneSide(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c)
    {//simply performs a transformation to check if all points on one triangle are on the same side of the other triangle
        Matrix m = Matrix.CreateLookAt(t1a, t1b, t1c - t1a);
        t2a = Vector3.Transform(t2a, m);
        t2b = Vector3.Transform(t2b, m);
        t2c = Vector3.Transform(t2c, m);
        if (t2a.X < 0 && t2b.X < 0 && t2c.X < 0)
            return false;
        if (0 < t2a.X && 0 < t2b.X && 0 < t2c.X)
            return false;
        return true;
    }

    public static bool CheckColisionLookAt(Vector3 t1a, Vector3 t1b, Vector3 t1c, Vector3 t2a, Vector3 t2b, Vector3 t2c)
    {//performs a transformation and checks if all points of the one triangle are under the other triangle after the transformation

        Matrix m = Matrix.CreateLookAt(t1a, t1b, t1c - t1a);
        t1a = Vector3.Transform(t1a, m);//  (0,     0,      0)
        if ( ZERRO < Math.Abs(t1a.X)|| ZERRO < Math.Abs(t1a.Y) || ZERRO < Math.Abs(t1a.Z))
            throw new Exception();
        t1b = Vector3.Transform(t1b, m);//  (0,     0,      maxZ)
        if (ZERRO < Math.Abs(t1a.X) || ZERRO < Math.Abs(t1a.Y))
            throw new Exception();
        t1c = Vector3.Transform(t1c, m);//  (0,     maxY,   someZ)
        if (ZERRO < Math.Abs(t1a.X))
            throw new Exception();
        t2a = Vector3.Transform(t2a, m);
        t2b = Vector3.Transform(t2b, m);
        t2c = Vector3.Transform(t2c, m);
        if (t2a.Y < 0 && t2b.Y < 0 && t2c.Y < 0)
            return false;
        return true;
    }

다음은 많은 교차로에 대한 참조가 포함 된 웹 사이트입니다.

실시간 렌더링 객체/객체 교차 페이지

Tri/Tri에 대한 목록은 다음과 같습니다.

Möller JGT 2 (2);
개최 JGT 2 (4);
gtweb;
Möller;
GPG p.393;
GTCG p.539;
TGS;
RTCD p.155,172;
Shen Jgt 8 (1);
Guigue JGT 8 (1);
Softsurfer;
실시간 렌더링, 2 판 p.590;
실시간 렌더링, 제 3 판 p.757

삼각형 정점에 대한 x, y 좌표가 있다고 생각합니다. 예를 들어.
삼각형 A :
1. 측면 A1 : XA1, YA1 2. 측면 A2 : XA2, YA2 3. 측면 A3 : XA3, Triangle B의 YA3 :
1. 측면 B1 : XB1, YB1 2. 측면 B2 : XB2, YB2 3. 측면 B3 : XB3, YB3

선의 조합이 intercect하면 삼각형이 교차합니다. A1이 B1 또는 B2 또는 B3과 교차하거나 A2가 B1 또는 B2 또는 B3을 교차하는 경우 또는 A3이 B1 또는 B2 또는 B3을 교차하는 경우를 의미합니다.

따라서 두 줄이 교차하면 결정하는 알고리즘이 필요합니다. 내가 찾은 가장 쉬운 예는 다음과 같습니다. http://www.mathopenref.com/coordintersection.html

게시 한 방법은 이 알고리즘 분리 축 정리에 기초하여 볼록한 다각형이 교차하는지 감지합니다. 이해하기는 그리 어렵지 않습니다.

분리 축이라고 불리는 선을 두 다각형 사이에 그릴 수 있다면 교차하지 않습니다. 각 다각형의 각 모서리는 축을 분리하는 후보입니다. 다각형은 그 축에 수직 인 벡터에 투사되며, 1d 범위는 중첩에 대해 테스트됩니다. 1D 오버랩이 없으면 현재 가장자리는 분리 축이고 두 다각형은 교차하지 않습니다. 1D 중첩이있는 경우, 모든 후보 가장자리가 테스트 될 때까지 결과는 결정적이지 않으며,이 시점에서 두 다각형이 교차한다고 결론 지었다. 두 개의 다각형은 가장자리를 공유 할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top