날개 달린 가장자리
Winged edge
 |
컴퓨터 그래픽스에서 날개 달린 가장자리 데이터 구조는 컴퓨터 메모리에서 폴리곤 메쉬를 표현하는 방법입니다.경계 표현의 한 유형이며 모델의 지오메트리와 토폴로지를 모두 설명합니다.정점 레코드, 가장자리 레코드 및 얼굴 레코드 등 세 가지 유형의 레코드가 사용됩니다.에지 레코드에 대한 참조를 지정하면 여러 유형의 인접 쿼리(인접 에지, 정점 및 면에 대한 쿼리)에 일정한 시간 내에 응답할 수 있습니다.이러한 인접 정보는, 분할 표면등의 알고리즘에 도움이 됩니다.
특징들
날개 달린 모서리 데이터 구조는 세 개 이상의 표면이 함께 모여 공통 모서리에서 만날 때 면, 모서리 및 정점의 지오메트리와 위상을 명시적으로 설명합니다.순서는 교차로 가장자리의 고유 방향에 대해 표면이 시계 반대 방향으로 정렬되도록 합니다.게다가 [clarification needed]표현은 아래와 같이 수치적으로 불안정한 상황을 가능하게 한다.
날개 달린 가장자리 데이터 구조를 사용하면 네트워크의 명시적으로 연결된 구조로 인해 면, 가장자리 및 정점 사이를 빠르게 통과할 수 있습니다.스토리지 오버헤드를 최소화하면서 인접 관계 쿼리를 일정 시간 내에 처리합니다.이렇게 구조화되지 않은 그리드를 지정하는 풍부한 형태는 노드 및 요소 목록과 같은 폴리곤 메쉬의 단순한 사양이나 일반 그리드의 암묵적인 연결과는 대조적입니다.날개 달린 가장자리 데이터 구조의 대안으로 하프 에지 데이터 구조가 있습니다.
구조 및 의사 코드
면 레코드와 정점 레코드는 비교적 단순하지만 가장자리 레코드는 더 복잡합니다.
- 각 정점에 대해 해당 레코드는 정점의 위치(예: 좌표)와 하나의 입사 모서리에 대한 참조만 저장합니다.다른 에지는 에지에서 추가 참조를 따라가서 찾을 수 있습니다.
- 마찬가지로 각 페이스 레코드는 페이스 주위의 가장자리 중 하나에 대한 참조만 저장합니다.면(CCW 또는 CW)을 기준으로 모서리의 방향을 저장할 필요가 없습니다. 면을 모서리의 왼쪽 및 오른쪽 면과 3회 비교할 수 있기 때문입니다.
- 마지막으로 엣지 레코드의 구조는 다음과 같다.가장자리가 지향하는 것으로 가정합니다.가장자리 레코드에는 가장자리의 끝점을 구성하는 정점에 대한 두 가지 참조, 가장자리 양쪽에 있는 면에 대한 두 가지 참조 및 왼쪽 및 오른쪽 면을 둘러싼 이전 및 다음 모서리에 대한 네 가지 참조가 포함됩니다.
즉, 엣지 레코드는 인접 정점 또는 인접 면 주위를 횡단할 때 모든 인접 레코드에 대한 참조를 가집니다.
클래스 에지 { 정점 *vert_origin, *vert_destination; 면 *왼쪽, *face_right; 엣지 *edge_left_cw, *edge_left_ccw; } 클래스 정점 {플로트 x, y, z; 엣지 *edge;} 클래스 면 {Edge};
「 」를 참조해 주세요.
외부 링크
- 브루스 G. 바움가트, 1972년날개 달린 모서리 다면체 표현..테크니컬 리포트스탠포드 대학교, 스탠포드, 캘리포니아, 미국
- 브루스 G. 바움가트 1975년컴퓨터 비전의 다면체 표현.1975년 5월 19일부터 22일까지의 회의에서는, 전국 컴퓨터 회의와 박람회(AFIPS '75).ACM, 뉴욕, 뉴욕, 미국, 589-596. DOI=10.1145/149949.1500071 https://doi.acm.org/10.1145/1499949.1500071 (날개의 모서리 다면체 표현)
- 미시간공대 Winged-Edge 데이터 구조
- 피사대학교 날개끝
