Today's Topics: meshMesh- Mesh tessellation-Mesh simplification-Subdivision- Mesh parameterization: Seam computation
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
·MeshDescription- A list of faces F = (fi,f,...,fn)· Each face is a triangle- A list of vertices V = (Vi,V2,...,Vn)Each face in F is a list of indices in Ve.g.fi --(V1,V2, V3 ), f2 --(V4, V5, V6)f3 --(V7,Vs, V9),
• 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?: Computer generated 3D models and captureddata have different representations.- We need a unified representation in graphics- visual accuracy and speed should be acceptable- Due to fast development of graphics hardware,we could rasterize(光栅化)and render trianglesvery quickly nowadays
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
Sourceof3Ddata: Models could be generated by:- Directly typing in the geometric file- Writing code to create such data: procedure modeling- Using modeling software such as 3ds/max, maya- Capturing a real model using a 3D scanner(3D扫描仪)- Reconstruction(重构) from one or more photographs(照片），calledphotogrammetry(照相测量法）- Combination of techniques above-Others
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: Solid-based usually seen in the area of Computer-Aided-Design(CAD), often emphasize modeling tools correspond toactual machining processes, such as cutting, drilling(钻孔),etc..Surface-based- do not have a built-in concept of solidity;-instead,allobjectsarethoughtofintermsofsurfacesDirect manipulation of surfaces, such as adding/deletingpolygons or vertices.-Easy for displaying
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 introduce 2D Tessellation because it's usefulin 3D mesh processing Polygons can arrive in many different forms, andmay have to be split into more tractableprimitives, such as convex polygons, triangles orquads, this process is called tessellation. If thepolygon is split into triangles, this process iscalled triangulation(三角化)
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. Thenext is partitioned into convex regions, thenext is triangulated, and the rightmost isuniformly meshed
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 eachline segment between any two givenvertices on a polygon and see if it intersects oroverlaps any edge of polygon.- If it does, the line segment cannot be used to split thepolygon, so examine the next possible pair of points,else split the polygon into two parts by this segmentand triangulate the new polygons by the samemethod.inefficient
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- First, find the ears over the polygon, that is , tolook at all triangles with vertex indices i,i+ l,i+2(mod n) and check line segment i,i+2 does notintersect any polygon edges. If so, then triangle i+1 forms an ear. Each earavailable is removed from the polygon, and thetriangles at vertices i and i+2 are re-examined tosee they are ears or not
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 flatsurfaces where two models' edge meet, but do notshare all vertices along them.? Even though the edges should theoretically meetperfectly, the renderer does not have enoughprecision in representing vertex locations on thescreen
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