Polygonal mesh를 생성하는 다양한 방법이 있습니다. 그 중 winged edge 는 여러 가지 이유로 자주 사용되는 방법입니다.
장점
winged edge 는 아래와 같은 장점을 같습니다.
- 모든 인접 영역에 대한 탐색 시간 복잡도가 O(1)
- 많은 추가 용량을 차지하지 않음
- 임의의 다양한 polygons 에도 적용이 가능
Winged edge table
이런 winged edge 방법을 구현하기 위해 winged edge table을 구현하게 되는데요, 예제를 통해 이해해 보겠습니다.
edge table을 보면 해당 edge(e3), 시작 Vertex(V2), 도착 Vertex(V3), 왼쪽 Face(F1), 오른쪽 Face(F2), e11, e12, e21, e22 항목이 있음을 확인할 수 있습니다. 이때,
왼쪽 탐색(Left Traverse)은 e21 -> e3 -> e11 시계방향으로
오른쪽 탐색(Right Traverse)은 e12 -> e3 -> e22 같은 시계방향으로 탐색이 진행됩니다.
참고
winged edge 관련하여 검색을 하다 보면 아래와 같은 설명 또한 확인해 볼 수 있는데요, 위 edge table의 e11, 12, 21, 22 순서가 다른 구성의 테이블임을 명심하시기 바랍니다.
출처
https://www.cs.cmu.edu/afs/cs/academic/class/15462-s14/www/lec_slides/lec6.pdf
https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/model/winged-e.html
The Winged-Edge Data Structure
The Winged-Edge Data Structure Perhaps the oldest data structure for a B-rep is Baumgart's winged-edge data structure. It is quite different from that of a wireframe model, because the winged-edge data structure uses edges to keep track almost everything.
pages.mtu.edu
'컴퓨터공학' 카테고리의 다른 글
| [강화학습] Numpy를 활용한 Q-Learning 이해하기 (0) | 2023.06.01 |
|---|---|
| [자료구조] Planar graph 와 plane graph (0) | 2023.05.31 |
| [머신러닝] Linear Regression (0) | 2023.04.25 |
| [머신러닝] Introduction (0) | 2023.04.25 |
| [컴퓨터그래픽스] 영상 워핑(warping)과 모핑(morphing) (0) | 2023.04.25 |