3D 점이 삼각형 내에 있는지 확인

Question

3D 점 (x, y & z)과 3 개의 다른 3D 점으로 이루어진 삼각형이있는 경우 점이 삼각형인지 어떻게 알 수 있습니까?

저는 2D에서이 작업에 대해 많은 것을 읽었습니다. 가장 유용한 것은 http://imusthaveit.spaces.live.com/blog/cns!B5212D3C9F7D8093!410.entry이지만, 3D로 개념을 옮기기 위해 고심하고 있습니다. 일반 개념이나 코드 예제로 도울 수 있습니까?

궁극적으로 내가하고 싶은 것은 삼각형 내부를 나타낼 수있는 점 목록을 얻는 것입니다.

Answer 1

당신은 실제로 삼각형의 3 점 또는 피라미드의 4 점에 대해 이야기하고 있습니까?

3D 공간에서 평평한 삼각형의 평면에 단일 점이있을 가능성은 극히 낮습니다.

편집 : 삼각형 버전에 대한 아이디어로

(가 보인다 당신이 원하는). 3x2D 검사를 수행 할 수 있습니다. 체크 포인트와 세 개의 삼각형 포인트에서 Z 좌표를 버리고 기존 방법을 사용하여 포인트가 평면에 있는지 확인하십시오. 그런 다음 X 좌표 만 무시하고 다시 Y 좌표를 무시합니다. 가장 효율적인 방법은 아니지만 코드 작성이 간단 할 것입니다.

Answer 2

설명 된 방법 here은 2D 경우에 매우 좋습니다. 3D로 작동하도록 수정하는 것이 가능하다고 생각합니다. 이 질문에 직접 대답하지는 않지만이 방법을 이해하면 3D로 수정하는 방법 (가능한 경우)을 해결할 수 있어야합니다.

Answer 3

1. 그 방정식 요점을 만족하는 경우가
2. 확인을 거짓말하는 평면의 방정식을 계산하는 삼각형의 세 점을 사용합니다.

Answer 4

차원의 점 P와 삼각형 T1, T2의 세 꼭지점, T3

• Find the plane through the three points T1, T2, T3
• 가 closest point on the plane P에 (비행기 위에 프로젝트 P)을 찾아 주어

이제 모든 점을 삼각형의 점을 찾는 2D 문제로 변형 할 수 있습니다. 또한 평면과 P의 거리가 정확히 얼마나 정확하게 삼각형 위에 있는지를 알려줍니다.

당신의 정교함을 정확하게 이해한다면 3D 그리드의 모든 복셀을 검사하여 주어진 삼각형에 있는지 알아볼 계획입니까? 이것은 매우 비효율적 일 것입니다 - 나는 당신이하고 싶은 것을 위해 Bresenham's line algorithm의 3D 버전이 효과가있을 것이라고 생각합니다. T1이있는 복셀을 찾은 다음 복셀을 통해 T2쪽으로 진행하고 T3에서 다시 T1로 돌아갑니다.

Answer 5

는 점 P와 삼각형을 감안할 때 A, B, C, 컴퓨팅 :

1. the unit normal of triange (A, B, P) - call it N1 
2. the unit normal of triangle (B, C, P) - call it N2 

(오른쪽 순서를 얻을!)

이제 내적 N1 * N2에 대해 생각합니다. P가 삼각형의 평면에 있고 세면 내부에있는 경우 해당 법선은 평행해야하므로이 내적은 1.0000 (또는 0.999 ...)이됩니다.P가 평면에 유지되지만 측면 BC를 넘어 이동하면 두 법선이 반대가됩니다. N1 * N2 == - 1. P가 평면에 없으면 내적은 중간 값이됩니다. 우리가 여전히 허점을 가지고 있습니다. P가 지나간 CA를 나가면.

3. the unit normal (C,A,P) called N3 

은 (이상적으로)이 두 시험 확인 : 우리는 한 번 더 계산해야

N1*N2 == 1.0 ? 
N2*N3 == 1.0 ? 

(테스트 N3 * N1이 중복) 물론이 테스트는 몇 가지를 허용해야합니다 컴퓨터 산술의 불완전성에 대한 경멸. 요구되는 정확도와 부동 소수점 유형에 따라 ε이 작은 값인 N1 * N2> 1-ε을 찾으십시오.

이러한 단위 법선에 수식이 필요할 수 있습니다. 주어진 (A, B, C) 교차 곱 N = (B-A) x (C-B)를 계산하라. sqrt (N * N)로 나눕니다. 교과서와 위키 백과 등에서 "내적"과 "외적"의 정의를 쉽게 구할 수 있습니다. 대수학에 따라 제곱근에 대한 성능을 향상시킬 수 있습니다.

나는 이것이 가장 빠른 알고리즘 주장하지 않습니다, 그러나 이것은 (구) 게시물에 너무

Answer 6

private bool PointInTriangle(Vector3[] TriangleVectors, Vector3 P) 
    { 
     Vector3 A = TriangleVectors[0], B = TriangleVectors[1], C = TriangleVectors[2]; 
     if (SameSide(P, A, B, C) && SameSide(P, B, A, C) && SameSide(P, C, A, B)) 
     { 
      Vector3 vc1 = Vector3.Cross(Vector3.Subtract(A, B), Vector3.Subtract(A, C)); 
      if (Math.Abs(Vector3.Dot(Vector3.Subtract(A, P), vc1)) <= .01f) 
       return true; 
     } 

     return false; 
    } 

    private bool SameSide(Vector3 p1, Vector3 p2, Vector3 A, Vector3 B) 
    { 
     Vector3 cp1 = Vector3.Cross(Vector3.Subtract(B, A), Vector3.Subtract(p1, A)); 
     Vector3 cp2 = Vector3.Cross(Vector3.Subtract(B, A), Vector3.Subtract(p2, A)); 
     if (Vector3.Dot(cp1, cp2) >= 0) return true; 
     return false; 

    } 

Answer 7

때까지 (개선 그냥 내 관찰을 작동합니다. 당신 (사전)이 U 계산하는 경우 & 삼각형에 대한 V 벡터 (U는 A에서 B까지의 벡터이고 V는 표준 삼각형 ABC의 A에서 C까지의 벡터입니다. U와 V는 모두 단위 길이가 아닌 입니다) Point)는 다음과 같은 방식으로 사용할 수 있습니다. P와 U의 점 product와 V의 P를 계산합니다. 두 점의 곱이 모두 작거나 같으면 d 합이 1보다 작거나 같으면 점이 안쪽에 있고 그렇지 않으면 바깥 쪽입니다. 이 방법은 먼저 법선 (교차 곱)을 비교 한 다음 도트 제품을 비교하는 것보다 효율적입니다. 이 접근법은 포인트가 실제로 오른 손잡이 삼각형을 형성하는 순서로 더 안정적 일 것을 요구하지 않습니다. 그것이 필요한 것은 대략 정확하기 위해서는 점이 평면에 있거나 (또는 ​​평면에 가깝다는 것입니다).