6 장 Modeling Shapes With Polygonal Meshs(part 1) 창원대학교 정보통신공학과 박동규

IVIS Lab, Changwon National University Index 6.1 Introduction 6.2 Introduction to Solid Modeling with Polygonal Meshs 6.3 Polyhedra 6.4 Extruded Shapes 6.5 Mesh Approximations to Smooth Objects 6.6 Summary

IVIS Lab, Changwon National University 6.1 Introduction(1/2 ) 다각형 메쉬 (Polygonal mesh) 는 – Simply collections of polygons, – “faces”, that together form the “skin” of an object – A standard way of representing a broad class of solid shapes in graphics – Many rendering systems, including OpenGL, are based on drawing objects by drawing a sequence of polygons

IVIS Lab, Changwon National University 6.1 Introduction(2/2 ) 면을 이용하여 복잡한 다각형 메쉬 만들기 – 일부 오브젝트는 다각형 메쉬로 완벽하게 표현가능, – 근사적으로 밖에 표현할 수 없는 objects 도 있음 –( 그림 a): 평평한 면을 가진 오브젝트로 모서리 사이의 면은 표현가 능함 –( 그림 b, c) : 부드러운 곡선을 가진 벽면은 다각형만으로는 완전하 게 구현 할 수 없음 (chap8 의 shading 방법으로 구현 )

6.2 Introduction to solid modeling with polygonal meshs

IVIS Lab, Changwon National University Introduction to solid modeling with polygonal meshs 다각형 메쉬 (Polygon mesh) – 솔리드 형태와 “ 얇은 ” 껍데기를 가진 메쉬를 사용 – 각 다각형의 면이 향하고 있는 방향에 관한 정보를 가진 다각형의 리스트 로 주어진다 – 방향 정보는 법선 벡터 (normal vector) 라 함.(used in the shading process)

IVIS Lab, Changwon National University Tomas Akenine- Mőller © 2002 State-of-the-Art Real- Time Rendering 2001

IVIS Lab, Changwon National University Tomas Akenine- Mőller © 2002 State-of-the-Art Real- Time Rendering 2001

IVIS Lab, Changwon National University Tomas Akenine- Mőller © 2002 Which one is a real photo, and which one is CG?

IVIS Lab, Changwon National University Tomas Akenine- Mőller © 2002 Complexity: 8 million triangles…

IVIS Lab, Changwon National University Vertex Normals Versus face Normals Vertex normals with each vertex of a face(highly advantageous) : one vector to an entire face –Clipping process –Shading process for smoothly curved shapes 그림과 같이 하나의 정점에 대해서는 여러 개의 법선 벡터가 존재할 수 있다. V1 and V5 are located at the same point in space, but use defferent normals

IVIS Lab, Changwon National University To Define a Polygonal Mesh  A Polygonal mesh is a collection of polygons, along with a normal vector associated with each vertex of each polygon  Example The “basic barn”

IVIS Lab, Changwon National University –Polygonal face : 7, vertices : 10 –Various ways to store information about a mesh  Polygon 에 대한 정보, 각각의 polygons 에 대한 vertices 정보 (30 개 ), 각각의 vertices 에 대한 normal 정보 (30 개 ) : quite redundant  only 10 distinct vertices, 7 normal  3 separate lists : a vertex list, a normal list, a face list

IVIS Lab, Changwon National University Vertex list : locational or geometric information Normal list : orientation information Face list : connectivity or topological information

IVIS Lab, Changwon National University Sample 2D File Format Source: Stanford University Computer Graphics Laboratory Scanner: Cyberware 3030 MS + spacetime analysis Number of scans: ~70 Total size of scans: 2,748,318 points (about 5,500,000 triangles) Reconstruction: vrip (conservatively decimated) Size of reconstruction: 566,098 vertices, 1,132,830 triangles

IVIS Lab, Changwon National University To Find the Normal Vectors If the face is considered flat –Figure 4.16 과 같이 cross product 로 계산  m=(V 1 -V 2 ) ☓ (V 3 -V 2 ) V1, V2, V3 : three adjacent points on the face –Two problems (if V 1 -V 2 and V 3 -V 2 are nearly parallel) cross product will be very small The polygon is not perfectly planar

IVIS Lab, Changwon National University Finding the Normal Vectors 법선을 얻기 위한 확실한 기법 (Martin Newell) – 법선벡터 m 의 m x, m y, m z 성분을 다음 공식에 따라서 구한다. 1. N : the number of vertices in the face(x i, y i, z i ) 2. Next(j) =(j+1) mod N : the index of the “next” vertex around the face after vertex j

IVIS Lab, Changwon National University Case Study 6.2 Derivation of the Newell method

IVIS Lab, Changwon National University

6.2.2 Finding the Normal Vectors Example –Vertiecs P0=(6, 1, 4), P1=(7, 0, 9), and P2=(1,1,2) –Solution 1. Newell method 2. Cross product = (2, -23, -15)  Newell == Cross product

IVIS Lab, Changwon National University Finding the Normal Vectors Practice Exercises –(6,1,4), (2,0,5), (7,0,9) compare(Newell method vs cross product)

IVIS Lab, Changwon National University Finding the Normal Vectors What about a nonplanar polygon? – a 가 zero 가 아닐 때 nonplanar polygon

IVIS Lab, Changwon National University Properties of Meshs 메쉬의 속성 (Properties of Mesh) –Solidity : faces 들이 한정된 공간을 둘러싸고 있으면 mesh 는 solid object 를 표현 –Connectedness : polygon edge 의 끊김없이 path 가 두 개의 vertices 에 존 재하면, mesh 는 connected 고, mesh 가 not connected 이면 하나이상의 object 로 간주 –Simplicity : object 가 solid 로 표현되고, hole 이 없으면 simple –Planarity : 모든 face 들이 planar polygon 으로 표현 –Convexity : 오브젝트의 내부에 존재하는 두 점을 연결한 직선이 오브젝 트의 외부와 만나지 않을 경우

IVIS Lab, Changwon National University Mesh Models for Nonsolid Objects Polygonal mesh 로 이루어지는 오브젝트의 예시 – 무한히 얇은 shell 로 간주함

IVIS Lab, Changwon National University Working with Meshes in a Program Mesh 를 class 로 정의 Mesh : pt(vertex list), norm(normal list), face(face list) 로 구성 F 번째 face 에서 v 번째 vertex : pt[face[f].vert[v].vertIndex] F 번째 face 에서 v 번째 normal : norm[face[f].vert[v].normindex]

IVIS Lab, Changwon National University Working with Meshes in a Program Example 사면체 데이터 – 메쉬를 화면에 그리는 Mesh::draw() 메소드는 메쉬 오브젝트의 면 의 배열을 탐색한 후, 각 면의 정점 리스트와 법선을 OpenGL 그래 픽스 파이프라인으로 전송하여 그리기를 수행

IVIS Lab, Changwon National University draw 메소드의 소스

IVIS Lab, Changwon National University Using SDL to Create and Draw a Mesh Object 메쉬의 묘사를 SDL 언어를 통해서 읽도록 응용 프로그램 을 작성하는 것이 매우 편리함 shape 으로 부터 Mesh 클래스를 파생시킨후 drawOpenGL() 메소드를 첨가한다 Class Mesh : public Shape{ virtual void drawOpenGL(){ tellMaterialsGL(); glPushMatrix(); //load properties glMultmatrix(transf.m); draw(); glPopMatrix(); } } // end of Mesh class  Push translate scale 333 mesh pawn.3vn pop

IVIS Lab, Changwon National University Quake2 md2 file 1997 년 Quake 2 발표시에 id Software 사에서 개발한 3D 모델 파일 형식 간단하며 이해가 쉽다 Frame-by-Frame animation

IVIS Lab, Changwon National University 6.3 다면체 (POLYHEDRA) 정의 –A Polyhedron is a connected mesh of simple planar polygons that encloses a finite amount of space 정의에 의하여 다면체는 단일 솔리드 오브젝트를 표현하며, 이는 다음을 의미한다 –Every edge is shared by exactly two faces –At least three edges meet at each vertex –Faces do not interpenetrate: Two faces either do not touch at all, or touch only along their common edge.

IVIS Lab, Changwon National University 6.3 다면체 (POLYHEDRA) 오일러 공식 (Euler ’ s Formula) –Faces(F), edges(E), vertices(V) 의 기본적인 관계 제공 –V+F-E =2  Example cube V=8, F=6, E=12 –Hole 이 존재할 때 : V+F-E =2 +H-2G H : faces 에서 발생하는 holes 의 개수 G : polyhedron 을 관통하는 holes 의 개수

IVIS Lab, Changwon National University 6.3 다면체 (POLYHEDRA) Example –figure(a) : V=16, F=16, E=32, H=0, G=1 –figure(b) : V=24, F=15, E=36, H=3, G=1

IVIS Lab, Changwon National University 6.3 다면체 (POLYHEDRA) Schlegel diagram – 하나의 face 의 바깥쪽 center 에서 polyhedron 을 바라보고 있을때 polygon Figure (a) : PYRAMID 의 Schlegel diagram Figure(b), (c) : basin barn 의 Schlegel diagram

IVIS Lab, Changwon National University Prisms and Antiprisms A Prism is a particular type of polyhedron that embodies symmetries A prism is defined by sweeping a polygon Polygon P 는 vector d 를 sweeping( 그림 참조 )

IVIS Lab, Changwon National University Prisms and Antiprisms 정규 프리즘 (Regular prism) – 정다각형을 기반 + side faces 는 정사각형 반프리즘 (Antiprism) – 그림 (b) 와 같이 top n-gon 은 bottom n-gon 에서 180/n rotate 정규 프리즘과 반프리즘은 “ 반정규 (semiregular) ” 다면체 의 예시이다

IVIS Lab, Changwon National University 정다면체 (The Platonic Solids) 정다면체 –Regular polyhedron 또는 Platonic Solid 라 함 – 사이트 참조 –Polyhedron 의 모든 faces 가 동일하고, 각 polyhedron 이 regular polygon –5 개의 object 만 존재 –Hexahedron(6 면체 ) : square( 정사각형 ), dodecahedron(12 면 체 ) :pentagons(5 각형 ), 나머지 3 개 : equilateral triangles –Hexahedron 은 regular prism, octahedron 은 antiprism

IVIS Lab, Changwon National University 정다면체 (The Platonic Solids) 각 solid 에 대한 V, F, E, Schlaefli symbol(p, q) –p : face 를 이루는 p-gon –q : vertex 와 만나는 face 의 수 – 메쉬 목록을 만드는 방법 –Solids 들의 “ duality ” 을 이용하여 20 면체에서 12 면체을 만들수 있음 ( 다음 슬라이드 설명 )

IVIS Lab, Changwon National University 쌍둥이 다변체 (Dual polyhedra) Platonic solid P 는 dual polyhedron D 을 가짐 D 의 vertices 는 P faces 의 중점 D 의 edges 는 인접하는 P 의 faces 의 midpoint 를 연결 Duality –Tetrahedron 의 dual 은 tertrahedron –Cube 와 octahedron 은 dual Duality

IVIS Lab, Changwon National University 쌍둥이 다변체 (Dual polyhedra) Dual 은 E(edges 개수 ) 가 서로 같고, D 의 V 의 개수는 P 의 F 의 개수 One dual 이 Schlaefli symbol (p, q) 이면 (q, p) 임 Build method –Platonic solid P 의 vertex list 를 알면, D 의 vertex list 을 만들 수 있음  D 의 vertex k 는 P 의 face K 의 center Vertex 와 face 의 numbering 을 위해 하나의 model 를 사용 –edge 을 slicing and unfolding 하여 lie flat –Ex) cube and octahedron(dual pair) Cube 의 face 4 는 vertices 1, 5, 6, 2 이므로, octahedron 의 vertex 4 는 faces 1, 5, 6, 2 로 이루어 짐 –Ex1) tertrahedron(self dual) Kth face 을 이루는 vertice list  kth vertex 를 이루는 faces list –Octahedron 의 vertex 4 은 cube 의 face 4 center 이므로

IVIS Lab, Changwon National University Normal Vectors for the Platonic Solids Solid 가 원점을 중점으로 가지면 각 face 의 normal vertor 는 원점에서 face 의 중점으로 통하는 vector 임.

IVIS Lab, Changwon National University The Tetrahedron Tetrahedron 은 cube 내에 정의될수 있음 Tetrahedron 의 4 개의 vertices 는 cube 의 코너에 나타남 Tetrahedron 의 4 개의 edge 는 cube 의 face 에 나타남 Tetrahedron 의 하나의 vertex 가 cube 의 (1, 1, 1) 에 있을때 vertex list 와 Face list

IVIS Lab, Changwon National University The Icosahedron Vertex list 만드는 방법 –3 개의 golden rectangles 를 사용 –Golden rectangle 의 긴쪽은 – 1 ~ 1 로 확장 –Golden rectangle 의 짧은 쪽은

IVIS Lab, Changwon National University The Icosahedron Icosahedron 의 모델 위의 icosahedron 을 변경 – 음영으로 된 antiprism 과 2 개의 pentagonal pyramide 로 구성

IVIS Lab, Changwon National University Other Interesting Polyhedra Truncated cube –Archimedan solid: regular polygon 으로 이루어져 있으며, face 는 여러가지 형태를 가지고 있음 –8-gons 과 3-gons 를 가지고 있음 – 각 vertex 는 1 개의 trianlge 과 두개의 8-gons 로 이루어짐  Symbol 3  8  8 로 간략화 –Cube 의 각 edge 는 3 개의 part 로 구성 ( 그림 c) –Edge 의 middle part 의 길이는 – 어떤 cube edge 의 endpoint 가 C, D 라면 두개의 새로운 Vertice V, W 는 아래의 식과 같음

IVIS Lab, Changwon National University

Other Interesting Polyhedra Buckyball –Archimedean solid 중 truncated icosahedron –5  6  6(1 개의 regular pentagon 과 2 개의 hexagon) 으로 구성 –List 생성 Icosahedron 의 model 를 만듦 ( 그림 6.35 참조 ) Icosahedron 의 각 edge 를 3 등분해서 2 개의 new vertice 만듦

6.4 Extruded Shapes Sweeping polygons 에 대해서 mesh 를 생성하는 방법을 다룸

IVIS Lab, Changwon National University Creating Prisms Prism 을 xy-plane 상에 polygon P 로 시작 ( 그림 a) P 는 z 축으로 distance H 만큼 swept( 그림 b)  그림 6.19 의 vector d Prism 의 모든 vertex 개수 : 14 P 의 vertex 가 면 대응하는 vertex 는 ARROW prism 모델 ( 그림 c) Prism 은 flat faces 므로 하나의 face 을 이루는 모든 vector 는 같 은 normal vector 을 가짐

IVIS Lab, Changwon National University Building a Mesh for the Prism  Building a Mesh for the Prism 1.Mesh 을 만들기 위한 가정 1.1 Prism ’ s base(P) 는 N 개의 vertices(xi, yi) 로 이루어진 polygon 1.2 P 의 vertex 수는 0, …., N-1 이고 cap 의 vertex 수는 N, …, 2N-1( 그림 c) 2. Vertex list 는 (xi, yi, 0) 와 (xi, yi, H) 로 쉽게 만들어짐 (i = 0, 1, …, N-1) 3. Face list 만들기 3.1 side face 를 먼저 만들고, base 와 cap face 를 추가 개의 vertex : j, j+N, next(j)+N, next(j) 로 side face 를 만듬 (j=0,1, …,N-1) 주의 ) j = N-1 이면 next(j) =0  next(j) =(j+1) modulo N  P/G code, next =(j<n-1)) ? (j+1) : 0

IVIS Lab, Changwon National University Arrays of Extruded Prisms: “ Bricklaying ” OPENGL 은 convex polygon 에 대해서 완벽하게 drawing 그림 6.28 의 arrow 은 정확한 drawing 을 보장할수 없음  Extrude 을 convex polygon or convex prism 으로 분할 (array) 하여 drawing Prism array 에 대한 method 필요 void mesh :: makePrismArray(convex base polygons 의 list 와 vector d)

IVIS Lab, Changwon National University Special Case: Extruded Quad-Strips –Family of prisms 으로 구성된 prisms 을 좀더 효율적으로 만드는 방 법 (Quad-Strips 사용 ) –Quad-Strips : 체인으로 연결된 4 변형의 array –Quad-strips 은 vertices 의 sequence 에 의해 표현  –Quad-strips 에서의 vertices 는 쌍으로 간주  쌍 : 홀수 vertices 와 연결되는 edge, 짝수 vertices 와 연결되는 edge

IVIS Lab, Changwon National University Special Case: Extruded Quad-Strips –Quad-Strip 으로 mesh 형성 Vertex list : 2M 개 Face list : 2M-2 개 필요한 Method(2D Points 의 array 와 extrusion vector(d))  Void mesh::makeExtrudedQuadStrip(Point2 p[], int numpts, vector3 d);

IVIS Lab, Changwon National University Extrusions with a “ Twist ” Twist Extrusions 는 cap polygon 크기를 base polygon 보다 크게 or 작게 and rotation 함 Affine transformation 사용 – 그림 a, b 는 scaling factor 0.7 과 H(z-axis) 만큼 translation – 그림 c 는 angle  만큼 rotate x,y 축 축소 Z 축 translate

IVIS Lab, Changwon National University Extrusions with a “ Twist ” – 그림 d 는 p ’ 로 회전 단면도 Twisted face list 은 original face List 와 동일 Vertex positions 바뀜

IVIS Lab, Changwon National University Building Segmented Extrusion: Tubes and Snakes Extrusions 의 sequence 를 사용하여 modeling –3 번의 square P 를 extruding( 방향, 크기, twists 포함 ) 으로 tube 가 완 성 –Segment : 그림 a(tube) 와 같이 M0P 와 M1P 가 첫번째 segment –Waists: tube 에서 transform 된 square 을 말함 –Vertex list :

IVIS Lab, Changwon National University Building Segmented Extrusion: Tubes and Snakes Designing Tubes Based on 3D Curves –Interesting and useful tubes and snake 디자인 방법 –Tube 는 curve(spine) 를 둘러싸고 있는 것으로 생각 –Curve 는 parametrically 로 표현 (C(t))  chap 3.8 참조 b: 상수 (6.11)

IVIS Lab, Changwon National University Building Segmented Extrusion: Tubes and Snakes – 각각에 Point C(ti) 에 대한 curve 와 수직인 평면상에 transformed polygon 를 만듦  각 Point 마다 local coordinate system 화 –Local coordinate system 을 결정하기 위해 differential geometry 의 Frenet frame(each point 에 대해 ) 을 사용

IVIS Lab, Changwon National University Building Segmented Extrusion: Tubes and Snakes Forming the Frenet Frame –Frame 은 C(t) 의 미분값으로 파생 –C(t) 가 미분가능하면 도함수, 접선을 구할 수 있음 – 을 normalize : unit tangent vector 를 구하기 위해 식 6.11 인 경우 ( 식 6.13) 식 6.13 와 cross product 인 vector 선정 ( :C(t) 의 2 차미분 )  T(t) 와 수직인 벡터를 구함 수직인 벡터 normalize(unit binormal)

IVIS Lab, Changwon National University –T(t) 와 B(t) 에 대하여 수직인 벡터를 구함 ( 외적을 사용 ) – 결국, C(t) 에서 local Frenet frame 를 형성하는 3 개의 vector 가 완성 –B(t), N(t) 를 대입하면 ( 식 6.11) Building Segmented Extrusion: Tubes and Snakes

IVIS Lab, Changwon National University

6.4.4 Building Segmented Extrusion: Tubes and Snakes Finding the Frenet Frame Numerically –C(t) 가 복잡한 공식일때 연속적인 미분은 힘듦 – 아래의 식을 사용하여 근소화 시킴

IVIS Lab, Changwon National University Building Segmented Extrusion: Tubes and Snakes 그림 6.47 –30 개의 Point 에 대해 Frenet frame 을 만 들어 완성 그림 6.48(a: p=2, q=5, b:p=1, q7)

IVIS Lab, Changwon National University “Discretely”Swept Surfaces of Revolution 그전 section 에서는 tube 에 대하여 각각의 spine point 에 대 하여 new coordinate system 을 형성하여 구현 만일 tube 가 pure rotation 이고 원점에 대하여 모든 spine point 가 위치한다면 ? – 여러 개의 polyhedral shapes 집합으로 나타남 – 그림 6.51: profile(base polygon) 을 y 축에 대하여 연속적으로 회전 (surface of revolution)

IVIS Lab, Changwon National University “Discretely”Swept Surfaces of Revolution 그림 6.52 –Polyline base –Y 축에 대하여 등간격 각도 K 에 polyline 를 위치시키면 transformation metrics 는 아래와 같음