Algorithm for constructing doubly connected edge list in 3d
This post explains how to construct double connected edge list in 2d. One of the steps in the algorithm is to sort the halfedges around a vertex in clockwise order. However this will not work in 3d. We can project the halfedge coordinates onto 2d viewplane and sort them that way (if the construction is user interactive). However this would make the construction dependent on the user view.
What sort of algorithm would we use for 3d case of double connected edge list?
답변
링크 된 게시물의 문제 설명에 따르면 정점과 가장자리 만 알고리즘에 입력되지만 메시면에 대한 추가 입력없이 3D에서 모호하지 않게이 작업을 수행 할 수 있다고 생각하지 않습니다. 2D의 경우 입력이 평면 그래프로 지정 되었기 때문에면은 모호하지 않습니다. 평면의 가장자리 루프 내에 포함되고 내부 가장자리가 비어있는 영역은면입니다. 그러나 3D에서는 어떤 가장자리 루프가면이어야하고 어떤 것이 안되어야하는지 알 수 없습니다.
정점과 가장자리로만 표현되는 정육면체를 고려하십시오. 정육면체의 "일반적인"6면이면으로 취급되기를 원하지만 알고리즘이 입방체의 대각선을 가로 지르는 추가면을 생성하는 것을 원하지 않을 것입니다. 내부적으로. 그러나 알고리즘이이를 알 수있는 방법은 없습니다. 더욱이 정점 / 가장자리 메시는 현명한 방식으로면을 할당하는 것이 불가능할 수도 있습니다. 평면이 아닌면을 가질 수 있으며 방향을 지정할 수 없거나 (예 : Möbius 스트립) 비 다양체 일 수 있습니다.
일반적으로 3D 응용 프로그램에서 우리는 이미 정의 된 메쉬면을 가지고 있으며, 다양하고 방향을 잡을 수있는 메쉬라고 가정 할 수 있습니다. 얼굴 데이터를 알고리즘에 대한 입력으로 사용하면 (예 : 각 얼굴 주변의 반 시계 방향으로 가장자리 또는 꼭지점 목록), 절반 가장자리 관계를 파악하는 것이 간단 해집니다 (지루한 경우).