오브젝트 안에 3D 포인트

Question

이 질문을 검색하고 검색했지만 찾은 답을 실제로 이해할 수 없습니다. 내 문제는 아주 간단합니다 :

하나의 메쉬 (삼각형으로 만들어진 3D 볼록하지 않은 폴리곤)를 가지고 공간 (xyz)을 스캔하고 나중의 처리를 위해 메쉬의 "내부"에있는 모든 점을 찾아야합니다. 나는 이것에 대해 많은 답변을 보았지만 나는 그것을 이해할 수 없다.

누구든지 도와 줄 수 있습니까 ??

Answer 1

주어진 점이 메시 내부에 있는지 알아 내려고한다고 가정합니다. 그렇지 않으면 분명히 무한한 점이 있습니다.

간단한 해결책은 그 지점에서 광선을 어떤 방향으로 던져서 교차하는 삼각형으로 교차 수를 세는 것입니다. 숫자가 홀수이면 포인트가 안에 있습니다. 광선이 모서리 나 꼭지점에 닿으면 하나의 교차점으로 간주해야합니다. 광선과 삼각형의 교차점은 선을 평면과 교차시켜 점이 광선에 속하고 삼각형 내부에 있는지 확인하여 수행됩니다.

Answer 2

메쉬 내부에 있는지 확인하기 위해 각 점을 확인하지만 성능 측면에서 더 잘 할 수 있습니다. 점의 격자가 에 의해 z이고, 그 격자가 t면을 가진다면 현재 접근 방식은 O(x*y*z*t)에서 실행됩니다.

O(x*y*t)에서 실행되는 대체 방법은 메시를 통과하는 그리드 라인을 고려하는 것입니다. 라인과 메시 사이의 교차점을 찾습니다. 교차점이 짝수 여야합니다. 이러한 교차점이 정렬되면 메쉬 내부에있는 선의 영역을 정의합니다. 그런 다음이 영역에있는 선에 점을 생성하는 것은 간단합니다.

대략 (메쉬가 단위 큐브 내에있는 것으로 가정) :

for each X in [0,1] { 
    for each Y in [0,1] { 
    Let P be a list of points of intersection between the mesh and the line from (X,Y,0) to (X,Y,1) 
    Sort P into ascending order of z-coordinate 
    Let I be false 
    for each Z in [0,1] { 
     if Z > P[0] { 
     I = !I 
     pop P[0] off the list 
     } 
     if(I) { 
     point (X,Y,Z) is inside the mesh 
     } 
    } 
    } 
}