清华大学：《计算机图形学基础》课程教学资源（授课教案）网格模型、网格细分和简化

Today’s Topics: mesh Today’s Topics: mesh • Mesh – Mesh tessellation – M h i lifi i Mes h s implificat ion – Subdivision – Mes pa a ete at o : Sea co putat o h pa r a meterizat i o n: Seam co mputat i o n

• Mesh Description – A li f f F (f A list o f faces F = (f1,f2,., fn ) • Each face is a triangle – A list of vertices V = (v1,v 2,.,v n ) – Each face in F is a list of indices in V e.g. f1-(v1,v 2,v 3 ), f2-(v 4,v 5,v 6 ), f3 -(v 7,v 8,v9 ),

Why mesh representation? Why mesh representation? • Computer generated 3D models and captured data ha e different representations data ha v e different representations, – We need a unified representation in graphics – visual accuracy and speed should be acceptable – Due to fast development of graphics hardware Due to fast development of graphics hardware, we could rasterize(光栅化) and render triangles very qui kl d c y nowa days

Source of 3D data Source of 3D data • Models could be generated by: – Directly typing in the geometric file Directly typing in the geometric file – Writing code to create such data: procedure modeling – U i d li ft h 3d / U s ing mo d eling software suc h as 3d s /max, maya – Capturing a real model using a 3D scanner(3D扫描仪 ) – Reconstruction(重构) from one or more photographs (照片), called photogrammetry (照相测量法 ) – Combination of techniques above – Others

Two main type of modelers Two main type of modelers • Solid-based – usually seen in the area of usually seen in the area of Computer Computer -Aided-Design (CAD), often emphasize modeling tools correspond to actual machining processes, such as cutting, drilling( actual machining processes, such as cutting, drilling( 钻 孔), etc. • Surface -based – do not have a built-in concept of solidity; – instead all objects are tho ght of in terms of s rfaces instead, all objects are tho ught of in terms of s urfaces. Direct manipulation of surfaces, such as adding/deleting polygons or vertices polygons or vertices. – Easy for displaying

Tessellation • Tessellation in 2D – We i d 2 ll i b i ’ f l introduce 2D Tessellation because it’s useful in 3D mesh processing – Polygons can arrive in many different forms, and may p have to be split into more tractable primitives, such as convex polygons, triangles or q,p uads this process is called tessellation. If the polygon is split into triangles, this process is called triangulation( called triangulation(三角化)

Tessellation • Various types of tessellation. • The leftmost polygon is not tessellated The The leftmost polygon is not tessellated. The next is partitioned into convex regions, the next i t i l t d d th i ht t i t is triangulated, and the rightmost is uniformly meshed

Tessellation • A basic tessellation method – Examine each line segment between any two given Examine each line segment between any two given vertices on a polygon and see if it intersects or overlaps any edge of polygon overlaps any edge of polygon. – If it does, the line segment cannot be used to split the pol gon so e amine the ne t possible pair of points polygon, so examine the next possible pair of points, else split the polygon into two parts by this segment and t i l t th l b th d triangulate the new polygons by the same method. – inefficient

Tessellation • Another tessellation method: ear clipping – Fi fi d h h l h i First, find the ears over the polygon, that is , to look at all triangles with vertex indices i,i+1,i+2 ( d) mo n and h k li d check line segment ii 2 , + does not intersect any polygon edges. – If so, then triangle i+1 forms an ear. Each ear available is removed from the polygon, and the triangles at vertices i and i+2 are re-examined to see they are ears or not

Tessellation • T-vertices – T-vertex • Appear when joining flat surfaces where two models’ edge meet, but do not share all vertices along them. • Even though the edges should theoretically meet perfectly, the renderer does not have enough preci i i ti t l ti th ision in representing vertex locations on the screen