Halfedge Data Structure(반모서리 자료구조)

OpenMesh는 Halfedge Data Structure를 

사용하고 있습니다. 우리말로 반모서리 자료구조라고 부릅니다. Edge를 절반으로 자른 형태라고 해서 반모서리라고 합니다. 이 반모서리 구조는 3D 모델링 및 Mesh 데이터 구조에서 많이 사용하고 있습니다. 많이들 사용하시는 CGAL(The Computational Geometry Algorithms Library)도 반모서리 구조를 사용하고 있습니다.

Halfedge 자료 구조는 메쉬의 각 모서리(Edge)를 나타내는데 사용되며, 이를 통해 메쉬의 구조를 효율적으로 저장하고 다양한 연산을 수행할 수 있습니다. 이 자료 구조는 메쉬의 표현을 간소화하고 메쉬 조작 작업을 더 효율적으로 만드는 데 도움이 됩니다.

Halfedge 자료 구조의 기본 아이디어는 위에서 언급하였듯이 각 모서리를 두 개의 반 모서리로 분할하는 것입니다. 이 분할된 모서리는 서로 연결되어 전체 모서리를 형성하며, 각 반 모서리는 특정 방향을 가지고 있습니다.

 

Halfedge 자료 구조의 주요 구성 요소는 다음과 같습니다

- Vertex (정점): 메쉬의 꼭지점을 나타냅니다.(참고로 영어에서 Point는 임의의 점을 나타내고 Vertex는 삼각형의 꼭지점을 말할 때 쓰입니다.)
- Edge (모서리): 메쉬의 모서리를 나타냅니다.
- Face (면): 메쉬의 면을 나타냅니다.
- Halfedge (반 모서리): 모서리를 두 개의 반 모서리로 분할한 것으로, 각각은 반대 방향을 가집니다. 이는 이웃하는 모서리와의 관계를 표현합니다.

이러한 구성 요소들은 서로 연결되어 메쉬의 전체 구조를 형성하며, 각 구성 요소는 이웃하는 구성 요소와의 관계를 효과적으로 표현합니다. Halfedge 자료 구조를 사용하면 메쉬의 삽입, 삭제, 분할 등의 연산이 효율적으로 수행될 수 있으며, 특히 메쉬의 변형 및 조작에 유용합니다.

아래의 그림은 Halfedge Data Structure를 나타냅니다.
한 개의 Halfedge 데이터에 접근해서 주변의 Vertex를 접근한다거나, Face, Next Halfedge 데이터 등을 손쉽게 접근할 수 있습니다.

Halfedge Data Structure