특정 유형의 요소 (예 : 삼각형, 테트라)가있는 메쉬가 있습니다. 각 요소마다 나는 모든 정점을 알고 있습니다. 즉, 삼각형의 2D 요소는 x, y, z 좌표가 알려져있는 3 개의 정점 v1, v2 및 v3을 갖습니다.메쉬에서 정점 (2D 및 3D)을 사용하여 모서리를 찾는 알고리즘
질문 1
나는이 경우 ... 모든 모서리를 반환하는 알고리즘을 찾고 있는데요 :
에지 (V1, V2), 에지 (V1, V3), 가장자리 (v2, v3). 각 요소의 정점 수를 기반으로 알고리즘은 가장자리를 효율적으로 결정해야합니다.
는는 질문이 나 C++를 사용하고
, 그럼, 위의 알고리즘에 의해 반환 된 모서리에 대한 정보를 저장하는 가장 효율적인 방법이 될 것인가? 예를 들어, 내가 관심을 갖고있는 것은 튜플 (v1, v2)이며 일부 계산에 사용하고 싶다.
고맙습니다.
하프 에지 데이터 구조를 사용할 수 있습니다.
기본적으로 메쉬에는 모서리 목록이 있으며, 각 방향의 verts 쌍마다 하나의 모서리 구조가 있습니다. 즉, A와 B가있는 경우 A-> B와 B-> A의 두 가지 모서리 구조가 있습니다. 각 모서리에는 이전에 호출 된 포인터, 다음에 호출 된 포인터 및 쌍둥이라고하는 포인터가 각각 3 개씩 있습니다. 다음 및 이전 포인터 다음에 메쉬의 삼각형 또는 다각형의 가장자리를 따라 이동합니다. 트윈을 호출하면 인접한 다각형 또는 삼각형의 인접한 가장자리로 이동합니다. (그가 그린 그림을 보라) 이것은 내가 아는 가장 유용하고 장황한 에지 데이터 구조이다. 저는 새로운 모서리를 만들고 포인터를 업데이트함으로써 메시를 매끄럽게 만드는 데 사용했습니다. Btw, 각 모서리는 꼭지점을 가리켜 야하므로 공간에서 어디에 있는지 알 수 있습니다.
알고리즘이 없지만 어디서 볼 수 있는지 알려주고 있습니다.
"Point Set Triangulation" 당신이 찾고있는 것입니다.
정말 귀하의 질문에 세 부분이 아닌 두 가지가 있습니다
적절한 답변을 찾으려면 추가 질문이 필요합니다.
메쉬를 나타 내기 위해 사용되는 데이터 구조는 무엇입니까?
처리해야하는 요소 유형은 무엇입니까?
다각형 (닫힌 루프)과 단순한 노드 (모든 노드가 4 면체와 같이 요소의 모든 다른 노드에 연결됨) 만 처리해야하는 경우 가장자리가 포함될 수 있으므로 순서가 지정된 노드 목록이면 충분합니다. 노드 목록. 한편, 육면체, 프리즘 또는 일반적인 다면체와 같은 요소 유형을 처리해야하는 경우 요소 토폴로지에 대한 추가 정보가 필요합니다. 가장자리 매핑의 간단한 배열로도 충분합니다. 이것은 주어진 요소 유형에 대해 도트를 연결하는 방법을 알려주는 요소의 노드 목록에 대한 배열의 배열 [2]입니다.
Chris가 설명한 하프 엣지 구조는 2D에만 적합합니다. 3D에서는 두 개가 아닌 각 가장자리에 임의의 수의 요소가 부착 될 수 있습니다. 제 생각에는 핀휠 구조라고 불리는 하프 에지 표현에 대한 3D 확장이 있습니다.
임의의 요소 유형을 지원해야하는 경우 요소 토폴로지를 나타내는 데 더 완전한 데이터 구조를 선호합니다. 일반적인 옵션은 가장자리와 가장자리를 사용하는 것입니다. 연결된 각 쌍의 노드에 대한 에지 구조가 있으며 요소의 각 에지 사용에 대한 공동 에지가 있습니다. 이것은 바람개비 접근 방식과 비슷하지만 좀 더 명확합니다.
요소에서 가장자리를 추출하는 데 사용해야하는 알고리즘은 무엇입니까?
속도 또는 메모리의 중요도는 어느 정도입니까? 결과에는 요소 당 한 번씩 각 가장자리가 포함되어야합니까? 아니면 몇 개의 요소가 사용되던 지 한 번만 포함해야합니까? 결과의 가장자리 순서가 중요합니까? 각 가장자리의 노드 순서가 중요합니까?
각 가장자리를 한 번만 방문하는 임의의 요소 유형에 대한 알고리즘을 생각해내는 것은 꽤 어렵습니다. 각 엣지가 한 번만 나타나게하려면 결과를 필터링하거나 조금씩 해치울 수 있고 각 엣지에 "방문한"비트를 유지하여 결과에 두 번 겹치지 않도록 할 수 있습니다.
어떻게 결과를 나타내야합니까?
결과를 사용하는 방법에 대해 중요한 점은 무엇입니까?
계산 집약적 인 계산에서 결과를 사용하려는 경우 큰 좌표 배열이 최선의 방법 일 수 있습니다. 계산 중에 노드 좌표를 계속해서 다시 가져오고 싶지는 않습니다. 그러나 중복 에지를 제거하기 위해 결과를 필터링하는 경우 좌표 (노드 쌍의 경우 6 배)를 비교하는 것은 길이 아닙니다. 필터링하는 경우 먼저 가장자리 구조에 대한 포인터 목록을 생성 한 다음 중복을 필터링하면 이 표시되고은 좌표 목록을 생성합니다. 이 접근법을 노드 쌍에도 사용할 수 있지만 가장자리 당 두 노드 주문에 대해 필터링해야하므로 필터링하는 데 걸리는 시간이 두 배로 늘어납니다.
메모리보다 성능이 중요 할 경우 에지 포인터 목록을 사용할 수도 있습니다. 그러나 가장자리 목록을 좌표 목록으로 변환하는 대신 계산 중에 좌표를 조회합니다. 노드 좌표를 얻는 것은 그렇게 느리지 만 커다란 좌표 목록을 만드는 것을 피할 수 있습니다. 가장자리 당 6 개의 double 대신에 가장자리 당 하나의 포인터를 저장합니다.
많은 메시 응용 프로그램은 모든 좌표를 큰 전역 배열에 저장하며 각 노드에는 배열에 대한 인덱스가 있습니다. 이 경우 가장자리 목록을 좌표 배열로 변환하는 대신 전역 좌표 배열로 색인 목록으로 변환하십시오. 퍼포먼스는 로컬 좌표 배열에서 많이 떨어져서는 안되지만 메모리와 퍼시스턴트 오버 헤드없이 이루어져야합니다.