메쉬를 조각 내기위한 알고리즘 또는 소프트웨어

Question

3D 메쉬를 슬라이싱하는 올바른 방법은 무엇입니까? 메쉬는 모두 닫힌 서피스이며, 슬라이스는 메쉬 내부의 이진 이미지 여야합니다. 예를 들어, 구형을 나타내는 메쉬와 채우기 이미지는 채워진 원의 이미지입니다.

현재 C++ 프로젝트에 통합 할 수있는 소프트웨어 라이브러리 또는 알고리즘을 찾고 있습니다.

Answer 1

제 오픈 소스 게임 라이브러리에는 메쉬 슬라이스 구현이 포함되어 있습니다. 그것은 Irrlicht API와 함께 작동하지만 겸손한 노력으로 다른 API를 사용하도록 다시 작성할 수 있습니다. BSD 라이센스 조항에 따라 코드를 사용하거나 직접 구현 한 코드를 배울 수 있습니다.

this file for an implementation of mesh slicing에서 MeshTools :: splitMeshZ를 참조하십시오. 내가 처음에 어디 메쉬를 절단하는 지정 축 정렬 경계 상자를 사용하여 생각

: 당신은 그냥 알고리즘을 알고 싶다면

, 여기에 내가 무슨 짓을했는지에 대한 높은 수준의 설명이다. 이것은 많은 특수한 경우를 도입했기 때문에 문제가되었다. 예를 들어, 상자의 모서리를 가로 지르는 가장자리는 단지 두 개가 아닌 세 개의 조각으로 나뉠 수 있습니다.

평면을 사용하여 메쉬를 왼쪽 메쉬와 오른쪽 메쉬로 자르면 가장자리가 평면의 한쪽 또는 다른쪽에 있거나 평면을 가로 지르기 때문에 특수한 경우의 수가 줄어 듭니다. 정확하게 두 조각으로 잘게.

원하는 절삭 구성은 한 번 절단하고, 결과 메쉬 중 하나를 취하여 다른 위치에서 다시 절단하는 등으로 간단하게 만들 수 있습니다. 특히 섹션에서 설명하는 경우 구체의 절반을 잘라 내고 평면을 소량 이동하고 나머지 절반은 잘라내어 얇은 밴드 만 남겨서 원형을 구체에서자를 수 있습니다. (당신이 썼던 코드로는 문자 그대로 깊은 곳까지 메쉬를자를 수는 없지만, 당신은 부동 소수점 동등한 임계 값을 설정 한 값으로 메쉬를자를 수 있습니다. 저는 제 코드에서 임의로 0.001을 선택했다고 생각합니다.)

비슷한 논리를 사용하면 고정 평면을 사용하여 원하는 절단면 각도를 얻을 수 있습니다. 고정 된 절단면을 기준으로 메쉬를 회전시켜 그 결과를 다시 변환하면됩니다. (내 게임에서는 XY 평면에 수직 인 커팅 만 필요했기 때문에 단순화를 위해 커트의 Z 값만 설정하고 Z 위치에 커트가 있다고 가정합니다.)

OK, 이제 우리는 문제를 단순화 한 것으로, 알고리즘은 그렇게 나쁘지 않다 :

시작 조건 : 당신은 절단면이있다. 소스 삼각형 세트가 있습니다. 두 개의 대상 세트 다각형 (삼각형이 아니라 삼각형을 절단하여 쿼드가 생성 될 수 있음)이 있습니다. 두 대상 집합을 왼쪽 및 오른쪽이라고합니다.

처리 : 삼각형의 세 점을 반복합니다. 절단면보다 적은 점의 수를 셉니다. 나는 절단면보다 왼쪽과 절단면보다 큰 것을 호출 할 것이다.

• 모든 삼각형 포인트가 왼쪽에 있습니다 : : 왼쪽에있는 삼각형을 넣어
• 모든 지점 오른쪽에있는 설정 : 오른쪽에있는 삼각형을 넣어
• 하나를 설정할 경우 소수에만있다 point는 Left이고, 다른 것은 Right입니다. 두 개의 가장자리를 가로 지르는 삼각형을 잘라내어 그 중 하나를 잡고 있다면 더 작은 삼각형을 갖게됩니다. Left 점과 왼쪽 모서리가 평면을 횡단하는 두 점으로 구성된 Left 세트에 삼각형을 놓습니다. 오른쪽 집합에 쿼드를 넣습니다 (다음 사례 참조).

• 두 점은 왼쪽이고 한 점은 오른쪽입니다. 삼각형의 가장자리를 잡고 다른 두 가장자리를 가로 질러 자르면 사다리꼴 모양을 유지하게됩니다. 손에있는 두 점과 컷을 가로 지르는 두 점으로 구성된 왼쪽 세트에 쿼드를 넣습니다. 오른쪽 세트에 삼각형을 놓으십시오 (위의 경우의 대칭 이미지).

• 끝나면 가장 짧은 부분에 링크를 추가하여 쿼드를 삼각형으로 바꿉니다.

그게 전부입니다. 이것이 기본 알고리즘입니다. 실제 코드는 엣지가 컷과 정확히 같은 경우, 삼각형이 정확히 모서리에있는 경우, 축약 된 폴리곤 (예 : 몸체가없는 점)을 추가하지 않는 경우와 같은 몇 가지 사례를 처리합니다.

기타 문제 (연결된 모든 코드에 포함) :

• 가장자리가 절단 평면을 교차 지점을 LERP'ing에 대한 계산을 복잡하게하지 마십시오. 전체 고 선형성 보간이 필요하지 않습니다. 실제로는 고교 대수 II : 런 이상 상승 비율의 비율

• 생성 된 (LERP'ed) 점을 캐시하여 점을 공유하는 삼각형이 언컷 된 메쉬는 해당 메쉬의 해당 새 정점을 공유합니다.

• 꼭지점 공유를 유지하면서 삼각형 인덱스 버퍼를 사용하는 경우 불행히도 왼쪽 및 오른쪽 세트에 삽입 할 모양을 처음 생성 할 때 인덱스를 알 수 없습니다. 미래의 삼각형 인덱스 번호를 나타 내기 위해 "PossibleVertex"라는 클래스를 사용합니다.

• 메시를 표시하려면 권선 순서가 중요합니다. 코드를 작성하는 방법에 대한 신중한 생각은 결과 폴리곤이 그들이 나온 삼각형과 동일한 권선 순서를 사용하도록 보장 할 수 있습니다. 이것은 특히 쿼드를 삼각형화할 때 까다로워집니다. 세부 정보는 기억이 나지 않지만 모두 링크 된 코드로 처리됩니다.

• 내 게임에서는 두 개의 컷 메쉬를 연결하는 플랫 리본을 만들고 싶었습니다. 이것이 splitMeshZ가 단지 2 개가 아닌 3 개의 메시를 생성하는 이유입니다.가운데 메쉬를 사용하거나 무시할 수 있습니다. 당신이 그것을 직접 구현하는 경우

Answer 2

삼각형 메시에 대해 말하는다고 가정합니다.

"올바른"접근 방식은 사용 사례의 특성에 따라 크게 달라집니다.

Jerry에서 제안한 OpenGL 방식이 도움이 될 수 있습니다.

다른 방법은 명시 적으로 절단을 계산하는 것입니다. 당신은 이것을 CGAL으로 할 수 있습니다. 보다 구체적으로 3D 커널. 비행기와 삼각형을 포함한 모든 종류의 프리미티브 간의 교차점을 계산할 수있는 function이 있습니다. 이 기능을 사용하여 교차로 윤곽선을 정확하게 계산하고 이미지로 렌더링 할 수 있습니다. -이 방법은 OpenGL에 의존하지 않고 대신 CGAL에 의존합니다.

Answer 3

저는 비행기 볼륨 교차점을 계산하기위한 알고리즘을 this answer에 요약했습니다. Java에서의 구현이 제공됩니다.

Answer 4

이 (자신을 위해, 실행 시간되지 않음) 빠른 것 :

메쉬

의 모든 삼각형을 1 추출 : 이들은 당신이해야 할 간단한 단계입니다

2의 경우 각 삼각형, 삼각형 포인트 중 하나라도 슬라이스 평면에있는 경우

2-1- 체크,

2-2-1없는 경우, 다음 세 개의 모서리 각각 발견 교차점 이온이 당신의 슬라이스 - 평면과 함께 있다면 (만약 있다면). 당신은 그 중 2 개가 비행기와 교차되거나 없음을 가져야합니다.

2-2-1 2 에지가 평면과 교차하는 경우 평면의이 두 점 사이에 선을 추가합니다.

Answer 5

(C의 소스 코드 ++와) 3D 메쉬 슬라이스에서 프로젝트 :

http://www.dainf.ct.utfpr.edu.br/~rminetto/projects/slicing/