폴리곤 메쉬
Polygon mesh | 이 글은 검증을 위해 추가 인용문이 필요합니다.: · · · 학자 · JSTOR ( 6월 삭제 및 삭제 ) |
3D 컴퓨터 그래픽과 솔리드 모델링에서 폴리곤 메쉬(polygon mesh)는 다면체 물체의 모양을 정의하는 정점, 모서리 및 면의 집합입니다.면은 일반적으로 삼각형(삼각형 메쉬), 사변형(사변형) 또는 기타 단순한 볼록형 폴리곤(n-gon)으로 구성됩니다. 이렇게 하면 렌더링이 간소화되지만 일반적으로 오목형 폴리곤 또는 구멍이 있는 폴리곤으로 구성될 수도 있습니다.
폴리곤 메쉬 연구는 컴퓨터 그래픽(특히 3D 컴퓨터 그래픽)과 기하학적 모델링의 큰 하위 분야입니다.폴리곤 메쉬의 표현은 용도 및 목적에 따라 달라집니다.메시에 대해 수행되는 다양한 작업은 다음과 같습니다.부울 로직(구성적 솔리드 지오메트리), 평활, 단순화 등 다양한 기능을 제공합니다.또한 폴리곤 메시를 사용한 광선 추적, 충돌 감지 및 강체 역학을 위한 알고리즘도 존재합니다.메쉬의 모서리가 면 대신 렌더링되면 모델이 와이어프레임 모델이 됩니다.
볼륨메시지는 구조물의 표면과 볼륨을 모두 명시적으로 나타내는 반면, 폴리곤메시는 표면만을 명시적으로 나타낸다는 점에서 폴리곤메시와는 다릅니다(볼륨메시지는 폴리곤메시와는 다릅니다.
메시 생성에는 행진 큐브알고리즘을 포함한 [1]몇 가지 방법이 있습니다.
요소들
폴리곤 메시로 작성된 객체는 서로 다른 유형의 요소를 저장해야 합니다.여기에는 정점, 모서리, 면, 폴리곤 및 표면이 포함됩니다.많은 응용 프로그램에서는 정점, 모서리 및 면 또는 폴리곤 중 하나만 저장됩니다.렌더러는 3면만 지원할 수 있으므로 폴리곤은 위와 같이 많은 면으로 구성되어야 합니다.그러나 많은 렌더러는 쿼드 및 상위측 폴리곤을 지원하거나 폴리곤을 즉시 삼각형으로 변환할 수 있기 때문에 메시를 삼각형 형태로 저장할 필요가 없습니다.
표현
폴리곤 메시는 정점, 모서리 및 면 데이터를 저장하기 위해 다른 방법을 사용하여 다양한 방법으로 표현될 수 있습니다.여기에는 다음이 포함됩니다.
VVmesh는 다른 정점을 가리키는 정점만을 나타냅니다.엣지 정보와 면 정보는 모두 표현에 내포되어 있습니다.그러나 표현의 단순성으로 인해 메시에서 많은 효율적인 작업을 수행할 수 없습니다.위의 각 표현은 Smith(2006)[2]에서 자세히 논의한 바와 같이 특별한 장점과 단점을 가지고 있다.데이터 구조의 선택은 애플리케이션, 필요한 성능, 데이터 크기 및 수행할 작업에 따라 결정됩니다.예를 들어, 일반 폴리곤보다 삼각형을 다루는 것이 더 쉽습니다. 특히 계산 기하학에서 그렇습니다.특정 작업에서는 가장자리 또는 인접 면과 같은 토폴로지 정보에 빠르게 접근할 수 있어야 하며, 이를 위해서는 날개 달린 가장자리 표현과 같은 보다 복잡한 구조가 필요합니다.하드웨어 렌더링을 위해서는 콤팩트하고 단순한 구조가 필요합니다.따라서 모서리 테이블(삼각형 팬)은 DirectX나 OpenGL과 같은 낮은 수준의 렌더링 API에 일반적으로 통합됩니다.
정점-버텍스 메쉬
.png)
정점-버텍스 메시는 다른 정점에 연결된 정점 집합으로 개체를 나타냅니다.이는 가장 간단한 표현이지만 면과 모서리 정보가 암묵적이어서 널리 사용되지 않습니다.따라서 렌더링할 면 목록을 생성하려면 데이터를 이동해야 합니다.또, 엣지나 면의 조작도 용이하지 않다.
그러나 VV 메쉬에는 스토리지 공간이 작고 쉐이프가 효율적으로 모핑되므로 이점이 있습니다.위 그림은 VV 메쉬로 표시된 4면 박스를 나타내고 있습니다.각 정점은 인접 정점을 인덱싱합니다."박스 실린더"의 상단 및 하단 중앙에 있는 마지막 두 개의 정점 8과 9는 5개가 아닌 4개의 연결된 정점을 가지고 있습니다.일반 시스템은 주어진 정점에 연결된 임의의 수의 정점을 처리할 수 있어야 합니다.
VV 메쉬의 상세한 것에 대하여는, Smith(2006)[2]를 참조해 주세요.
페이스-버텍스 메쉬
면-버텍스 메시는 면 집합 및 정점 집합으로 객체를 나타냅니다.이것은 가장 널리 사용되는 메시 표현으로, 현대의 그래픽 하드웨어에서 일반적으로 받아들여지는 입력입니다.
페이스 버텍스 메쉬에서는, 면의 정점과 정점을 둘러싼 면의 명시적인 룩업을 가능하게 하기 때문에, 모델링용의 VV 메쉬가 개선됩니다.위의 그림은 FV 메쉬로서의 "박스 실린더"의 예를 나타내고 있습니다.정점 v5가 강조 표시되어 주변 면들이 표시됩니다.이 예에서는 모든 면에 정확히 3개의 정점이 필요합니다.그러나 이는 모든 정점이 동일한 수의 주변 면을 갖는다는 것을 의미하지는 않습니다.
렌더링의 경우 페이스 리스트는 보통 정점에 대한 인덱스 세트로 GPU에 전송되며, 정점은 위치/색상/통상 구조로 전송됩니다(그림에서는 위치만 지정됨).이 방법에는 면 연결을 업데이트하지 않고 정점 데이터를 재전송하기만 하면 형상을 변경할 수 있지만 형상을 변경할 수는 없다는 장점이 있습니다.
모델링에는 모든 구조를 쉽게 횡단할 수 있어야 합니다.페이스-버텍스 메시를 사용하면 페이스의 꼭지점을 쉽게 찾을 수 있습니다.또한 정점 리스트에는 각 정점에 연결된 면 리스트가 포함됩니다.VV 메쉬와는 달리 면과 정점은 모두 명시적이기 때문에 인접한 면과 정점을 찾는 것은 일정한 시간이 됩니다.단, 가장자리는 암묵적이기 때문에 특정 면을 둘러싼 모든 면을 찾기 위해서는 여전히 검색이 필요합니다.면 분할 또는 병합과 같은 다른 동적 작업도 면-버텍스 메쉬에서는 어렵습니다.
날개 달린 그물
1975년 Baumgart에 의해 도입된 날개 달린 엣지 메쉬(edge mesh)는 메쉬의 꼭지점, 면 및 가장자리를 명시적으로 나타냅니다.이 표현은 분할 및 병합 작업을 신속하게 수행할 수 있기 때문에 메쉬 형상을 동적으로 변경할 때 최대의 유연성을 제공하기 위해 모델링 프로그램에서 널리 사용됩니다.주요 단점은 스토리지 요건이 크고 많은 인덱스를 유지 보수하기 때문에 복잡성이 커진다는 것입니다.날개 달린 엣지 메쉬의 실장 문제에 대한 자세한 내용은 Graphics Gems II를 참조하십시오.
날개 달린 엣지 메쉬를 사용하면 엣지에서 엣지로 이동하여 엣지 주위에 면 세트를 순서대로 제공할 수 있습니다.주어진 에지에 대해 나가는 에지의 수는 임의일 수 있습니다.이를 단순화하기 위해 날개 달린 가장자리 메시는 양 끝에 시계방향과 시계반대방향에 가장 가까운 4개의 가장자리만 제공합니다.다른 가장자리는 점진적으로 통과할 수 있습니다.따라서 각 모서리에 대한 정보는 나비 모양이며, 따라서 "날개형 모서리" 메시입니다.위 그림은 날개 달린 가장자리 메쉬로서의 "박스 실린더"를 보여줍니다.모서리의 총 데이터는 두 개의 꼭지점(끝점), 두 개의 면(각 변) 및 네 개의 모서리(날개 모서리)로 구성됩니다.
그래픽 하드웨어용 날개 달린 가장자리 메쉬를 렌더링하려면 면 인덱스 목록을 생성해야 합니다.이 작업은 일반적으로 지오메트리가 변경될 때만 수행됩니다.날개 달린 가장자리 메쉬가 국소적으로 변경될 수 있으므로 분할 표면 및 대화형 모델링과 같은 동적 지오메트리에 이상적입니다.메시를 통한 트래버설은 충돌 검출에 필요할 수 있으므로 효율적으로 실행할 수 있습니다.
자세한 [3]내용은 Baumgart(1975)를 참조하십시오.
동적 메시 렌더링
날개 달린 모서리 메쉬만이 기하학을 동적으로 변경할 수 있는 유일한 표현은 아닙니다.날개 달린 가장자리 메쉬와 면-버텍스 메쉬를 결합한 새로운 표현은 렌더 다이내믹 메쉬로, 렌더 다이내믹 메쉬에는 면의 정점과 정점의 정점(FV 메쉬와 같은)과 면의 정점과 가장자리(날개의 가장자리)의 정점이 모두 명시적으로 저장됩니다.
렌더링 동적 메쉬에는 표준 날개 달린 가장자리 메쉬보다 저장 공간이 약간 적게 필요하며 면 리스트에 정점 인덱스가 포함되어 있기 때문에 그래픽 하드웨어에서 직접 렌더링할 수 있습니다.또한 정점에서 정점으로의 횡단은 얼굴에서 정점으로의 횡단과 마찬가지로 명시적이다(정수 시간).RD 메쉬에는 4개의 발신 에지가 필요하지 않습니다.이러한 에지는 에지에서 면으로 이동한 다음 인접 에지를 향해 이동할 수 있기 때문입니다.
RD 메쉬에서는 형상을 동적으로 업데이트할 수 있으므로 날개 가장자리 메쉬의 기능을 활용할 수 있습니다.
상세한 [4]것에 대하여는, Tobler & Maierhofer(WSCG 2006)를 참조해 주세요.
메시 표현 요약
| 작동 | 정점-버텍스 | 페이스 버텍스 | 날개 달린 가장자리 | 동적 렌더링 | |
|---|---|---|---|---|---|
| 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} | 명시적 | 명시적 |
| 푸크 | 지정된 정점이 있는 면 찾기 | 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: 메쉬 표현 조작의 개요 | |||||
위의 표에서 명시적(explicit)은 데이터가 직접 저장되기 때문에 일정한 시간에 작업을 수행할 수 있음을 나타냅니다.목록 비교는 작업을 수행하기 위해 두 목록 간의 목록 비교를 수행해야 함을 나타내고 쌍 검색은 두 개의 인덱스에 대해 검색을 수행해야 함을 나타냅니다.avg(V,V)는 주어진 정점에 연결된 평균 정점 수를 의미하며, avg(E,V)는 주어진 정점에 연결된 평균 가장자리 수를 의미하며, avg(F,V)는 주어진 정점에 연결된 평균 면 수입니다.
"V → f1, f2, f3, ... → v1, v2, v3, ..." 표기법은 작업을 수행하기 위해 여러 요소에 걸친 횡단이 필요하다는 것을 나타냅니다.예를 들어 면-버텍스 메쉬를 사용하여 "특정 정점 V 주위의 모든 정점"을 얻으려면 먼저 정점 리스트를 사용하여 지정된 정점 V 주변의 면을 찾아야 합니다.그런 다음 면 리스트를 사용하여 면 주변의 정점을 찾습니다.날개 달린 엣지 메쉬에는 거의 모든 정보가 명시적으로 저장되며 다른 작업은 항상 엣지로 이동하여 추가 정보를 가져옵니다.정점-버텍스 메시는 특정 정점의 인접 정점을 명시적으로 저장하는 유일한 표현입니다.
메시 표현이 복잡해지면(요약에서는 왼쪽에서 오른쪽으로) 명시적으로 저장되는 정보의 양이 증가합니다.이를 통해 보다 직접적이고 일정한 시간, 다양한 요소의 트래버설 및 토폴로지에 접근할 수 있지만 인덱스를 적절하게 유지하는 데 있어 오버헤드와 공간이 증가합니다.
그림 7은 이 문서에서 설명하는4가지 기술 각각에 대한 접속 정보를 나타내고 있습니다.하프 엣지 테이블이나 코너 테이블 등 다른 표현도 존재합니다.이들은 모두 정점, 면 및 모서리가 서로 인덱싱하는 방식의 변형입니다.
일반적으로 면-버텍스 메쉬(face-vertex mesh)는 그래픽 하드웨어에서 오브젝트를 렌더링해야 할 때마다 사용되며, 그래픽 하드웨어에서는 지오메트리(연결성)를 변경하지 않지만 정적 오브젝트나 모핑 오브젝트의 실시간 렌더링과 같이 변형되거나 변형될 수 있습니다(버텍스 위치입니다.윙 에지 또는 렌더 동적 메시는 대화형 모델링 패키지 또는 하위 분할 표면 계산과 같이 지오메트리가 변경될 때 사용됩니다.정점-버텍스 메시는 하드웨어 렌더링이 문제가 되지 않는 한 지오메트리 또는 토폴로지의 효율적이고 복잡한 변경에 이상적입니다.
기타 표현
파일 형식
폴리곤 메쉬 데이터를 저장하기 위한 다양한 파일 형식이 있습니다.각 형식은 제작자가 의도한 목적에 사용할 때 가장 효과적입니다.이러한 형식의 일부를 다음에 나타냅니다.
| 파일 서픽스 | 형식명 | 조직 | 프로그램 | 묘사 |
|---|---|---|---|---|
| .날것의 | 생메쉬 | 알 수 없는 | 여러가지 | ASCII 전용의 오픈 형식.각 라인은 X1 Y1 Z1 X2 Y2 Z2 X3 Z3와 같이 3개의 정점을 공백으로 구분하여 삼각형을 형성합니다. |
| .disclosed(비활성화) | 블렌더 파일 형식 | 블렌더 파운데이션 | 블렌더 3D | 오픈 소스, 바이너리 전용 형식 |
| .fbx | 오토데스크 FBX 형식 | 오토데스크 | 여러가지 | 독자 사양입니다.이진 및 ASCII 사양이 있습니다. |
| 3ds | 최대 3ds 파일 | 오토데스크 | 최대 3ds | 정점 및 면 수에 대한 하드 16비트 제한이 있는 일반적이지만 오래된 형식입니다.표준화도 문서화도 잘 되어 있지 않지만, 이전에는 데이터 교환의 「사실상의 표준」이었습니다. |
| .dae | 디지털 자산 교환(COLLADA) | 소니 컴퓨터 엔터테인먼트, 크로노스 그룹 | 없음 | COLAborative Design Activity의 약자입니다.비호환성을 방지하기 위해 설계된 범용 형식입니다. |
| .dgn | MicroStation 파일 | 벤틀리 시스템즈 | 마이크로 스테이션 | 버전 8 이전과 버전 8(V8)의 두 가지 dgn 파일 형식이 있습니다. |
| 3dm | 코뿔소 파일 | 로버트 맥닐 & 어소시에이션스 | 코뿔소 3D | |
| .tvf, .tvg | 도면 교환 형식 | 오토데스크 | AutoCAD | |
| .obj | Wavefront OBJ | Wavefront 테크놀로지 | 여러가지 | 3D 지오메트리를 설명하는 ASCII 형식입니다.모든 면의 정점은 시계 반대 방향으로 정렬되어 있으며, 면의 규범이 암묵적으로 나타납니다.매끄러운 노멀은 정점마다 지정됩니다. |
| .ply | 폴리곤 파일 형식 | 스탠퍼드 대학교 | 여러가지 | 이진 및 ASCII |
| .pmd | 폴리곤 무비 메이커 데이터 | 히구치 유우 | 미쿠미쿠댄스 | 연결, 재료 및 물리 정보와 함께 휴머노이드 모델 형상을 저장하기 위한 전용 이진 파일 형식입니다. |
| .stl | 입체 리소그래피 형식 | 3D 시스템 | 많이 | 원래 CNC를 지원하기 위해 설계된 바이너리 및 ASCII 형식입니다. |
| .amf | 적층 제조 파일 형식 | ASTM 인터내셔널 | 없음 | STL 형식과 비슷하지만 네이티브 색상, 소재 및 별자리 지원이 추가되었습니다. |
| .wrl | 가상현실 모델링 언어 | Web3D 컨소시엄 | 웹 브라우저 | ISO 표준 14772-1:1997 |
| .wrz | VRML 압축 | Web3D 컨소시엄 | 웹 브라우저 | |
| .x3d, .x3db, .x3dv | 확장 가능한 3D | Web3D 컨소시엄 | 웹 브라우저 | XML 기반의 오픈소스, 로열티 프리, 확장 가능, 상호 운용성.컬러, 텍스처, 씬 정보도 서포트합니다.ISO 표준 19775/19776/19777 |
| .x3dz, .x3dbz, .x3dvz | X3D 압축 바이너리 | Web3D 컨소시엄 | 웹 브라우저 | |
| .c4d | 시네마 4D 파일 | 맥손 | 시네마 4D | |
| .lwo | LightWave 3D 객체 파일 | 뉴텍 | 라이트웨이브 3D | |
| .disclosed(비활성화) | SCORC apf | RPI SCOREC | 뿌미 | PDE 기반 시뮬레이션 워크플로우를 위한 오픈 소스 병렬 적응형 비구조화 3D 메쉬. |
| .msh | Gmsh 메쉬 | GMSH 개발자 | GMSH 프로젝트 | 오픈 소스: 1~3차원으로 선형 및 다항식으로 보간된 요소에 대한 ASCII 메시 설명을 제공합니다. |
| .disclosed(비활성화) | OGRE XML | OGRE 개발팀 | OGRE, 퓨어 베이직 | 오픈 소스이진(.mesh) 및 ASCII(.mesh.xml) 형식을 사용할 수 있습니다.정점 애니메이션 및 Morph 대상 애니메이션(블렌드 쉐이핑)에 대한 데이터를 포함합니다.골격 애니메이션 데이터를 별도의 파일(.skeleton)에 저장합니다. |
| .veg | 베가 FEM 사면체 메시 | 예르네즈 바르비치 | 베가 FEM | 오픈 소스FEM 시뮬레이션을 위해 사면체 망사 및 해당 재료 특성을 저장합니다.ASCII(.veg) 및 바이너리(.veg) 형식을 사용할 수 있습니다. |
| .z3d | Z3d | 올레그 멜라셴코 | 자노자 모델러 | - |
| .sqk | VTK 메쉬 | VTK, 키트웨어 | VTK, 파라뷰 | 점 데이터, 셀 데이터 및 필드 데이터를 비롯한 다양한 데이터 필드를 포함하는 개방형 ASCII 또는 이진 형식입니다. |
| .l4d | LAI4D 도면 | 디자인 인공지능 연구소 | 라이4D | 엔티티의 계층 트리를 설명하는 ASCII 데이터 형식. |
「 」를 참조해 주세요.
- 경계 표현
- 오일러 연산자
- 하이퍼그래프
- 매니폴드(메쉬가 매니폴드 또는 비매니폴드일 수 있음)
- 메쉬 서브섹션(폴리곤 메쉬에 디테일을 추가하는 기술)
- 폴리곤 모델링
- 폴리곤라이저
- 심플렉스
- T스플라인
- 삼각 측량(기하학)
- 와이어 프레임 모델
레퍼런스
- ^ Lorensen, William E.; Cline, Harvey E. (1 August 1987). "Marching cubes: A high resolution 3D surface construction algorithm". ACM SIGGRAPH Computer Graphics. 21 (4): 163–169. CiteSeerX 10.1.1.545.613. doi:10.1145/37402.37422.
- ^ a b Colin Smith, 정점-버텍스 메시와 기하학적 및 생물학적 모델링에서의 그 사용(PDF)
- ^ Bruce Baumgart, 컴퓨터 비전을 위한 날개 달린 다면체 표현1975년 5월, 전미 컴퓨터 회의"Use of Polyhedra in computer vision". baumgart.org. May 1975. Archived from the original on 2005-08-29. Retrieved 2005-08-29.
- ^ Tobler & Maierhofer, 렌더링 및 세분화를 위한 메시 데이터 구조. 2006년. (PDF)
외부 링크
- Weisstein, Eric W. "Simplicial complex". MathWorld.
- Weisstein, Eric W. "Triangulation". MathWorld.
- OpenMesh 오픈 소스 하프 엣지 메쉬 표현.
- 폴리곤 메쉬 처리 라이브러리
