计算机图形学课件cgmeshes

计算计算机图形Computer三维物体的表•二三维物体的表•二次球面、抛物面圆柱锥••••复杂数学表函数数学表函数参数表如何画曲面？如何画曲面？--离函数参数表多面体网多面体网格模•每个面为平面多边WhyWhymeshSourcesSourcesof3DTwoTwomaintypesof正多正多面Euler对于Euler对于简单多面体V+F–E顶点数：V,面数F边数例如，立方体：V=8,F=6,V+F–E=2+H–••Euler公式VEuler公式V=16,F=16,E=32,H=G=V=24,F=15,E=36,H=G=如何表达模型的表面如何表达模型的表面•3D空间的3D3D物体的数字表3D物体的数字表达：点和三角•点三维坐标三角网格(Triangular•三角网格(Triangular•点•线•面如何存储如何存储•网格模型数据格WavefrontOBJFile•WavefrontOBJFile•StartwithcharStartwithcharIndicesofitsverticesinthe••–Normal,texturecoordinates,material,v1.00.0v0.01.0v0.0-1.0v0.00.0f12f14f32f13Demo:Demo:Mesh2D2DDelaunayandMeshBorisN.BorisN.••RussianMarch15,1890-JulyIntroduceDelaunaytriangulationin•GeorgyF.GeorgyF.••RussianApril28,1868-20,PropertiesofPropertiesofDT•Emptysphereproperty:nopointsinsidecircum-sphereofany–DelaunayPropertiesofDTPropertiesofDT•DTmaximizesthesmallest–[Lawson1977]and[SibsonPropertiesofPropertiesofDT•Convexhull:unionofallPropertiesofDTPropertiesofDT•DTmaximizesthearithmeticmeanoftheradiusinscribedcirclesofthe[LambertDTminimizesroughness(theDirichletenergyofanypiecewise-linearscalarfunction)–[RippaDTminimizesthemaximumcontainingradius(theradiusofthesmallestspherecontainingthesimplex)[AzevedoandSimpson1989],[Rajan••PropertiesofPropertiesofDT•TheDTind-spacesistheprojectionthepointsofconvexhullontoa(d+1)-dimensional–[BrownPropertiesofPropertiesofDT•DTminimizesthespectrumoftheLaplacian(spectral–[Chenetal.Edge[SibsonEdge[SibsonStartwithany1.findanytwoadjacenttrianglesthatformaconvexquadrilateralthatdoesnotsatisfyemptyspherecondition2.swapthediagonalofthequadrilateraltobeaDeluanytriangulationofthatfourpoints3.repeatstep1,2until•Convergence?IsitpossibletoendwithaninfiniteMesh•GivenMesh•Givenafixedpointset,DelaunaywilltrytomakethetriangulationmoreregularandthusisconsideredasaMesh•WhatMesh•Whatdowemeana“good”MinimalAspect/radiusMean–Itisnoteasytodefineauniversalmeshqualityacceptablebyeveryone.Buteveryoneagreesonthe"best"simplex:equilateraltriangleandtetrahedra.•DTisDTisnotnecessaryagoodDTonlyoptimizetheconnectivitywhenpointsarefixed.distributionofpointsismoreimportantforagoodCentroidalVoronoiCentroidalVoronoi•Definition:TheVTisacentroidaltessellation(CVT),ifeachseedwiththecentroidofitsVoronoiLloyd••••ConstructtheLloyd••••ConstructtheVTassociatedwiththeComputethecentroidsoftheVoronoiregionsMovethepointstothecentroidsIterateuntilDefinitions&StandardGraphCBADLJIKEStandardGraphCBADLJIKEHFGGraphGraphPlanarPlanarPlanarPlanarGraphsandTopologyTopology•Delaunay•DelaunayTriangulationvs.VoronoiMeshMeshDataUsesofMesh•–UsesofMesh•–TriangleGeometry•–––WhataretheverticesoffaceArevertices#iand#jWhichfacesareadjacenttoface•Geometry–––Remove/addaMeshStoringMeshStoringMeshData•StorageofgenericHardtoimplement•StoringMeshDataStoringMeshData•How“good”isadataSpace•••Timetoconstruct-TimetoansweraTimetoperformanoperation(updatethedataTrade-offbetweentimeandDefineaMeshDefineaMesh•Howdovertices•DefineaDefineaMesh••••ListofVertex-3DMesh•Surface&3DMesh•Surface&material––––MaterialTexturecoordinates•Rendering–––RenderingGeneralUsedMeshGeneralUsedMesh•Generalusedmesh––––––3DMax(*.max,*.3ds)Inventor(*.iv)•WavefrontOBJFile•WavefrontOBJFile•StartwithcharStartwithcharIndicesofitsverticesinthe••–Normal,texturecoordinates,material,v1.00.0v0.01.0v0.0-1.0v0.00.0f12f14f32f13ListListofListofListof•ListofPositionListofTripletsofpointerstofaceverticesWhataretheverticesoffaceAnsweredinO(1)-checkingthirdAreverticesiandjApassoverallfacesisnecessary–NOT••ListListofFaces–ListofListofFaces–•Convenientandefficient(memoryCanrepresentnon-manifoldToosimple-notenoughinformationonrelationsbetweenvertices&faces•AdjacencyAdjacencyAdjacencyMatrixAdjacencyMatrix–ViewmeshasconnectedGivennverticesbuildn*nmatrixofadjacencyEntry(i,j)isTRUEvalueifverticesiandjareGeometriclistofvertexAddlistoftripletsofvertexindices••••AdjacencyAdjacencyMatrix–AdjacencyMatrix–AdjacencyMatrix–•WhataretheverticesoffaceO(1)–checkingthirdtripletofAreverticesiandjO(1)-checkingadjacencymatrixatlocationWhichfacesareadjacenttovertexFullpassonallfacesis••AdjacencyMatrixAdjacencyMatrix–•InformationonvertexStoresnon-manifoldConnectsfacestotheirvertices,BUTNOconnectionbetweenvertexanditsface•Doubly-ConnectedDoubly-ConnectedEdgeRecordRecordforeachface,edgeandGeometricHalf-Edge••DCELDCELDCELDCEL–DCELDCEL–ExampleDCEL–DCEL–•AllqueriesinO(1)AlloperationsareO(1)Representson