폴리곤 메시

2. 폴리곤 메시의 구성 요소

• 정점(Vertex): 색상, 법선 벡터, 텍스처 좌표 등 다른 정보와 함께 3차원 공간에서의 위치를 나타낸다.
• 모서리(Edge): 두 정점을 연결한다.
• 면(Face): 닫힌 모서리 집합이다. 삼각형 면은 세 개의 모서리를, 사각형 면은 네 개의 모서리를 가진다.
• 다각형(Polygon): 공면 면의 집합이다. 여러 면을 지원하는 시스템에서 다각형과 면은 동일하지만, 대부분의 렌더링 하드웨어는 3개 또는 4개의 변을 가진 면만 지원하므로 다각형은 여러 면으로 표현된다.
• 표면(Surface): 주로 '''스무딩 그룹'''이라고 불리며, 부드러운 영역을 그룹화하는 데 유용하지만 필수적인 것은 아니다.
• 예시: 뚜껑이 있는 소다 캔과 같은 원통을 생각해 보자. 측면을 부드럽게 셰이딩하려면 모든 표면 법선이 중심에서 수평으로 바깥쪽을 향해야 하고, 뚜껑의 법선은 위아래로 똑바로 향해야 한다. 단일 퐁 셰이딩 표면으로 렌더링하면 겹치는 정점에서 잘못된 법선이 생성된다.
• 따라서 3면으로 구성된 면을 그룹화하는 다각형과 마찬가지로, 메시의 부드러운 부분을 그룹화하기 위해 스무딩을 중단할 위치를 결정하는 방법이 필요하다.
• 표면/스무딩 그룹 대신 메시는 동일한 데이터를 계산하기 위한 다른 데이터를 포함할 수 있다. (예: 분할 각도 - 이 임계값보다 높은 법선을 가진 다각형은 자동으로 별도의 스무딩 그룹으로 처리되거나, 분할 또는 모따기와 같은 기술이 해당 다각형 사이의 모서리에 자동 적용됨)
• 매우 높은 해상도의 메시는 스무딩 그룹이 필요한 문제의 영향을 덜 받는다. 다각형이 너무 작아 스무딩 그룹이 불필요하기 때문이다.
• 표면 자체를 메시의 나머지 부분에서 분리하는 것도 또 다른 대안이 될 수 있다. 렌더러는 비연속 다각형에서 모서리를 스무딩하려고 시도하지 않는다.

• 그룹(Group): 일부 메시 형식은 메시의 별도 요소를 정의하는 그룹을 포함한다. 이는 골격 애니메이션을 위한 별도의 하위 객체나 비골격 애니메이션을 위한 별도의 액터를 결정하는 데 유용하다.
• 재질(Material): 일반적으로 재질이 정의되어 메시의 다른 부분이 렌더링될 때 다른 셰이더를 사용할 수 있다.
• UV 좌표: 대부분의 메시 형식은 메시의 2차원 표현("펼쳐진" 형태)을 통해 메시의 다른 다각형에 적용할 2차원 텍스처 맵의 어느 부분을 보여주는 UV 좌표를 지원한다. 메시는 색상, 접선 벡터, 가중치 맵 등 다른 정점 속성 정보나 애니메이션 제어 정보(채널이라고도 함)를 포함할 수 있다.

2. 1. 정점 (Vertex)

2. 2. 뫼비우스의 띠 (Edge)

2. 3. 면 (Face)

• '''정점''' (Vertex): 색상, 법선 벡터, 텍스처 좌표와 같은 다른 정보와 함께 3D 공간의 위치이다.
• '''모서리''' (Edge): 두 개의 정점 사이의 연결이다.
• '''면''' (Face): 닫힌 모서리 집합이다. '''삼각형 면'''은 세 개의 모서리를 가지고, '''사각형 면'''은 네 개의 모서리를 가진다. '''다각형'''은 공면 면의 집합이다. 여러 면을 지원하는 시스템에서 다각형과 면은 동일하다. 그러나 대부분의 렌더링 하드웨어는 3개 또는 4개의 변을 가진 면만 지원하므로 다각형은 여러 면으로 표현된다. 수학적으로 다각형 메시는 구조화되지 않은 그리드 또는 방향이 없는 그래프로 간주할 수 있으며, 기하학, 모양 및 위상과 같은 추가 속성을 가진다.

2. 4. 다각형 (Polygon)

• 정점(Vertex): 3차원 공간에서의 위치를 나타내며, 색상, 법선 벡터, 텍스처 좌표 등의 정보를 포함한다.
• 모서리(Edge): 두 개의 정점을 연결하는 선분이다.
• 면(Face): 닫힌 모서리 집합으로, 삼각형 면은 3개의 모서리, 사각형 면은 4개의 모서리를 가진다.
• 다각형(Polygon): 공면 면들의 집합이다.
• 표면(Surface): 부드러운 영역을 그룹화하는 데 사용되며, '스무딩 그룹'이라고도 불린다. 퐁 셰이딩을 사용할 때 부드러운 표현을 위해 필요하다. 분할 각도 등의 데이터를 통해 자동으로 처리될 수도 있다.

2. 5. 표면 (Surface)

• 정점(Vertex): 색상, 법선 벡터, 텍스처 좌표와 같은 다른 정보와 함께 3차원 공간에서의 위치이다.
• 모서리(Edge): 두 개의 정점 사이의 연결이다.
• 면(Face): 닫힌 모서리 집합이다. ''삼각형 면''은 세 개의 모서리를 가지고, ''사각형 면''은 네 개의 모서리를 가진다.
• 다각형(Polygon): 공면 면의 집합이다. 여러 면을 지원하는 시스템에서 다각형과 면은 동일하다. 그러나 대부분의 렌더링 하드웨어는 3개 또는 4개의 변을 가진 면만 지원하므로 다각형은 여러 면으로 표현된다. 수학적으로 다각형 메시는 구조화되지 않은 그리드 또는 방향이 없는 그래프로 간주될 수 있으며, 기하학, 모양 및 위상의 추가 속성을 가진다.

2. 6. 기타 요소

• 정점(Vertex): 색상, 법선 벡터, 텍스처 좌표 등 다른 정보와 함께 3차원 공간에서의 위치를 나타낸다.
• 모서리(Edge): 두 정점을 연결한다.
• 면(Face): 닫힌 모서리 집합이다. 삼각형 면은 세 개의 모서리를, 사각형 면은 네 개의 모서리를 가진다.
• 다각형(Polygon): 공면 면의 집합이다. 여러 면을 지원하는 시스템에서 다각형과 면은 동일하지만, 대부분의 렌더링 하드웨어는 3개 또는 4개의 변을 가진 면만 지원하므로 다각형은 여러 면으로 표현된다.
• 표면(Surface): 주로 '''스무딩 그룹'''이라고 불리며, 부드러운 영역을 그룹화하는 데 유용하지만 필수적인 것은 아니다.
• 예시: 뚜껑이 있는 소다 캔과 같은 원통을 생각해 보자. 측면을 부드럽게 셰이딩하려면 모든 표면 법선이 중심에서 수평으로 바깥쪽을 향해야 하고, 뚜껑의 법선은 위아래로 똑바로 향해야 한다. 단일 퐁 셰이딩 표면으로 렌더링하면 겹치는 정점에서 잘못된 법선이 생성된다.
• 따라서 3면으로 구성된 면을 그룹화하는 다각형과 마찬가지로, 메시의 부드러운 부분을 그룹화하기 위해 스무딩을 중단할 위치를 결정하는 방법이 필요하다.
• 표면/스무딩 그룹 대신 메시는 동일한 데이터를 계산하기 위한 다른 데이터를 포함할 수 있다. (예: 분할 각도 - 이 임계값보다 높은 법선을 가진 다각형은 자동으로 별도의 스무딩 그룹으로 처리되거나, 분할 또는 모따기와 같은 기술이 해당 다각형 사이의 모서리에 자동 적용됨)
• 매우 높은 해상도의 메시는 스무딩 그룹이 필요한 문제의 영향을 덜 받는다. 다각형이 너무 작아 스무딩 그룹이 불필요하기 때문이다.
• 표면 자체를 메시의 나머지 부분에서 분리하는 것도 또 다른 대안이 될 수 있다. 렌더러는 비연속 다각형에서 모서리를 스무딩하려고 시도하지 않는다.
• 그룹(Group): 일부 메시 형식은 메시의 별도 요소를 정의하는 그룹을 포함한다. 이는 골격 애니메이션을 위한 별도의 하위 객체나 비골격 애니메이션을 위한 별도의 액터를 결정하는 데 유용하다.
• 재질(Material): 일반적으로 재질이 정의되어 메시의 다른 부분이 렌더링될 때 다른 셰이더를 사용할 수 있다.
• UV 좌표: 대부분의 메시 형식은 메시의 2차원 표현("펼쳐진" 형태)을 통해 메시의 다른 다각형에 적용할 2차원 텍스처 맵의 어느 부분을 보여주는 UV 좌표를 지원한다. 메시는 색상, 접선 벡터, 가중치 맵 등 다른 정점 속성 정보나 애니메이션 제어 정보(채널이라고도 함)를 포함할 수 있다.

3. 폴리곤 메시의 표현 방식

폴리곤 메시는 정점, 변, 면 데이터를 저장하는 다양한 방법으로 표현될 수 있다. 주요 표현 방식에는 면-정점 메시, 윙드-엣지 메시, 정점-정점 메시, 렌더 동적 메시 등이 있다. 이 외에도 하프-엣지 메시, 쿼드-엣지 메시, 코너-테이블 등의 표현 방식이 존재한다.^[2]

각 표현 방식은 특정 장단점을 가지며, 데이터 구조 선택은 응용 프로그램, 필요한 성능, 데이터 크기, 수행할 작업 등에 따라 결정된다.^[2] 예를 들어, 계산 기하학에서는 삼각형을 처리하는 것이 일반 폴리곤보다 쉽다. 특정 작업에서는 변 또는 인접 면과 같은 위상 정보에 빠르게 접근해야 하므로 윙드-엣지 표현과 같은 복잡한 구조가 필요하다. 하드웨어 렌더링의 경우 DirectX 및 OpenGL과 같은 낮은 수준의 렌더링 API에 일반적으로 통합되는 코너-테이블(삼각형 팬)과 같이 간결하고 단순한 구조가 필요하다.

아래 표는 각 메시 표현 방식에 따른 연산 및 저장 크기를 비교한 것이다.

연산		정점-정점	면-정점	윙드 엣지	렌더 동적 메시
V-V	정점 주변의 모든 정점	명시적	V → f1, f2, f3, ... → v1, v2, v3, ...	V → e1, e2, e3, ... → v1, v2, v3, ...	V → e1, e2, e3, ... → v1, v2, v3, ...
E-F	면의 모든 모서리	F(a,b,c) → {a,b}, {b,c}, {a,c}	F → {a,b}, {b,c}, {a,c}	명시적	명시적
V-F	면의 모든 정점	F(a,b,c) → {a,b,c}	명시적	F → e1, e2, e3 → a, b, c	명시적
F-V	정점 주변의 모든 면	쌍 검색	명시적	V → e1, e2, e3 → f1, f2, f3, ...	명시적
E-V	정점 주변의 모든 모서리	V → {v,v1}, {v,v2}, {v,v3}, ...	V → f1, f2, f3, ... → v1, v2, v3, ...	명시적	명시적
F-E	모서리의 양쪽 면	목록 비교	목록 비교	명시적	명시적
V-E	모서리의 양쪽 정점	E(a,b) → {a,b}	E(a,b) → {a,b}	명시적	명시적
Flook	주어진 정점을 가진 면 찾기	F(a,b,c) → {a,b,c}	v1,v2,v3의 집합 교집합	v1,v2,v3의 집합 교집합	v1,v2,v3의 집합 교집합
저장 크기		V*avg(V,V)	3F + V*avg(F,V)	3F + 8E + V*avg(E,V)	6F + 4E + V*avg(E,V)
		정점 10개, 면 16개, 모서리 24개를 사용한 예시:
		10 * 5 = 50	3*16 + 10*5 = 98	3*16 + 8*24 + 10*5 = 290	6*16 + 4*24 + 10*5 = 242
그림 6: 메시 표현 연산 요약

위 표에서 '명시적'은 데이터가 직접 저장되어 연산을 상수 시간에 수행할 수 있음을 뜻한다. '목록 비교'는 연산을 위해 두 목록을 비교해야 함을, '쌍 검색'은 두 색인에 대한 검색을 수행해야 함을 의미한다. ''avg(V,V)''는 주어진 정점에 연결된 평균 정점 수, ''avg(E,V)''는 주어진 정점에 연결된 평균 모서리 수, ''avg(F,V)''는 주어진 정점에 연결된 평균 면 수를 나타낸다.

"V → f1, f2, f3, ... → v1, v2, v3, ..." 표기는 연산을 위해 여러 요소를 거쳐야 함을 의미한다. 예를 들어, 면-정점 메시에서 "주어진 정점 V 주변의 모든 정점"을 얻으려면, 먼저 정점 목록에서 V 주변의 면(f1, f2, f3, ...)을 찾고, 그 면들의 면 목록에서 주변 정점(v1, v2, v3, ...)을 찾아야 한다. 윙드 엣지 메시는 거의 모든 정보를 명시적으로 저장하여 다른 연산이 추가 정보를 얻기 위해 항상 모서리를 먼저 거치도록 한다. 정점-정점 메시는 주어진 정점의 인접 정점을 명시적으로 저장하는 유일한 표현이다.

일반적으로 면-정점 메시는 실시간 렌더링과 같이 형상이 변형되거나 변형될 수 있는 경우(정점 위치)나 형상이 변경되지 않는 그래픽 하드웨어(연결성)에서 객체를 렌더링해야 하는 경우에 사용된다. 윙드 엣지 또는 동적 렌더링 메시는 대화형 모델링 패키지 또는 세분화 표면 계산과 같이 형상이 변경되는 경우에 사용된다. 정점-정점 메시는 하드웨어 렌더링이 문제가 되지 않는 한, 형상 또는 토폴로지에서 효율적이고 복잡한 변경을 하기에 적합하다.

3. 1. 면-정점 메시 (Face-Vertex Meshes)

'''면-정점 메시'''는 객체를 면 집합과 정점 집합으로 나타내는 방식으로, 가장 널리 사용되는 메시 표현이다. 현대 그래픽스 하드웨어가 일반적으로 받아들이는 입력 방식이기도 하다.

면-정점 메시는 면의 정점과 정점 주변의 면을 명시적으로 조회할 수 있다는 점에서 VV-메시보다 모델링에 유리하다. 위의 그림은 "상자-원통" 예제를 FV 메시로 보여준다. 정점 v5는 이를 둘러싼 면을 보여주기 위해 강조 표시되었다. 이 예에서 모든 면은 정확히 3개의 정점을 가져야 하지만, 모든 정점이 동일한 수의 주변 면을 갖는 것은 아니다.

렌더링할 때 면 목록은 일반적으로 정점에 대한 인덱스 집합으로 GPU에 전송되고, 정점은 위치, 색상, 법선 구조로 전송된다 (그림에서는 위치만 제공됨). 이를 통해 형상의 변화는 면 연결성을 업데이트하지 않고 정점 데이터만 다시 전송하여 동적으로 업데이트할 수 있다는 이점이 있다.

모델링은 모든 구조를 쉽게 순회할 수 있어야 한다. 면-정점 메시를 사용하면 면의 정점을 쉽게 찾을 수 있다. 또한 정점 목록에는 각 정점에 연결된 면 목록이 포함되어 있다. VV 메시와 달리 면과 정점 모두 명시적이므로 인접한 면과 정점을 찾는 데 상수 시간이 소요된다. 그러나 모서리는 암시적이므로 주어진 면을 둘러싼 모든 면을 찾으려면 여전히 검색이 필요하다. 면 분할 또는 병합과 같은 다른 동적 작업도 면-정점 메시에서는 어렵다.

3. 2. 윙드 엣지 메시 (Winged-Edge Meshes)

1975년 바움가르트(Baumgart)가 소개한 '''윙드 엣지 메시'''는 메시의 정점, 면, 모서리를 명시적으로 표현한다.^[3] 이 표현 방식은 분할 및 병합 연산을 빠르게 수행할 수 있기 때문에 메시 지오메트리를 동적으로 변경하는 데 가장 큰 유연성을 제공하여 모델링 프로그램에서 널리 사용된다. 주요 단점은 많은 인덱스를 유지 관리해야 하므로 저장 공간 요구 사항이 크고 복잡성이 증가한다는 것이다. 윙드 엣지 메시의 구현 문제에 대한 자세한 내용은 ''Graphics Gems II''에 나와 있다.

윙드 엣지 메시는 모서리에서 모서리로의 이동 문제와 모서리 주변에 정렬된 면 집합을 제공하는 문제를 해결한다. 주어진 모서리에 대해 나가는 모서리의 수는 임의적일 수 있다. 이를 단순화하기 위해 윙드 엣지 메시는 각 끝에서 가장 가까운 시계 방향 및 시계 반대 방향 모서리 4개만 제공한다. 다른 모서리는 점진적으로 이동할 수 있다. 따라서 각 모서리에 대한 정보는 나비와 유사하여 "윙드 엣지" 메시라고 한다. 는 "박스-실린더"를 윙드 엣지 메시로 보여준다. 모서리에 대한 총 데이터는 2개의 정점(끝점), 2개의 면(각 측면), 4개의 모서리(윙드 엣지)로 구성된다.

그래픽 하드웨어를 위한 윙드 엣지 메시 렌더링에는 면 인덱스 목록을 생성해야 한다. 일반적으로 지오메트리가 변경될 때만 수행된다. 윙드 엣지 메시는 메시 변경이 지역적으로 발생할 수 있으므로 세분화 표면 및 대화형 모델링과 같은 동적 지오메트리에 이상적이다. 충돌 감지에 필요할 수 있는 메시 간의 이동은 효율적으로 수행할 수 있다.

자세한 내용은 Baumgart(1975)를 참조하십시오.^[3]

3. 3. 정점-정점 메시 (Vertex-Vertex Meshes)

'''정점-정점 메시'''(Vertex-Vertex Meshes, VV)는 객체를 다른 정점에 연결된 정점 집합으로 나타낸다. 가장 간단한 표현이지만, 면과 변(변) 정보가 암시적이어서 널리 사용되지는 않는다. 따라서 렌더링을 하려면 면 목록을 만들기 위해 데이터를 순회해야 한다. 또한, 변과 면에 대한 연산은 쉽게 수행할 수 없다.^[2]

VV 메시는 저장 공간이 작고 형태 변환이 효율적이라는 장점이 있다. 위 그림은 VV 메시로 표현된 사면 상자를 보여준다. 각 정점은 인접한 정점을 가리킨다. "상자-실린더"의 상단과 하단 중앙에 있는 마지막 두 정점 8과 9는 4개의 연결된 정점을 갖는다(5개가 아님). 일반적인 시스템은 주어진 정점에 연결된 임의의 수의 정점을 처리할 수 있어야 한다.^[2]

3. 4. 렌더 동적 메시 (Render Dynamic Meshes)

'''렌더 동적 메시'''는 윙드 엣지 메시 외에도 기하학적 구조를 동적으로 변경할 수 있는 표현 방식이다. 윙드 엣지 메시와 면-정점 메시를 결합한 새로운 표현 방식으로, 면의 정점과 정점의 면(FV 메시와 유사)과 엣지의 면과 정점(윙드 엣지와 유사)을 명시적으로 모두 저장한다.

렌더 동적 메시는 표준 윙드 엣지 메시보다 약간 적은 저장 공간을 필요로 하며, 면 목록에 정점 인덱스가 포함되어 있으므로 그래픽 하드웨어에서 직접 렌더링할 수 있다. 또한 정점에서 면으로의 탐색, 면에서 정점으로의 탐색 모두 명시적(상수 시간)이다. RD 메시는 4개의 발신 엣지가 필요하지 않은데, 엣지에서 면으로, 면에서 인접 엣지로 탐색하여 찾을 수 있기 때문이다.

RD 메시는 기하학적 구조를 동적으로 업데이트할 수 있도록 함으로써 윙드 엣지 메시의 기능을 활용한다.

자세한 내용은 토블러 & 마이어호퍼 (WSCG 2006)를 참조하십시오.^[4]