第二讲-几何建模

第二讲几何建模内容提要•计算机中如何表达三维模型？•什么是网格？•网格的典型数据结构是什么？•几何建模有哪些典型方法？•几何建模有哪些典型应用？几何建模（GeometricModeling）•在计算机中表达一个真实世界的三维对象或虚拟三维形象，就必须先描述其形状•几何建模–三维对象的表达、构造和处理的计算机算法和过程•要逼真再现一个场景，需要对场景中的每一个细节进行建模数字化几何数据•离散化–易于表达和传输–渲染硬件和软件的基础数据–大多数获取设备的输出格式(CT,MRI,laser,…)–大多数模拟/分析工具需要的输入离散化的圆•理想的圆–如果圆心在(0,0)处，r2=x2+y2(0,y)r(0,0)(x,y)离散化的圆（二）•多边形逼近（分段线性近似）离散化显示：光栅图形反走样OpenGL反走样•glEnable(GL_BLEND)//启用混合•glEnable(GL_LINE_SMOOTH)//启用线段反走样3D模型的表达•原始数据–体素–点云–深度图像–多边形•曲面–曲面网格–细分曲面–参数曲面–隐式曲面•实体模型–八叉树–BSP树–CSG–Sweep•高层次语义结构–SceneGraphMarchingCube[Lorensen&Cline’87]：从体素到三角网格•将一个隐式的曲面转换为三角网格•在3D网格（grid）上定义的隐式曲面•在每个立方体（cube）中根据8个顶点的标量值来确定重构曲面•一般用于医学数据点云深度图像网格（Mesh）–图形学中最常用的表达–简单–可表达复杂形状–图形硬件支持–一般为三角网格为什么是三角网格•其它多边形网格可以容易地剖分为三角形•三点共面：保证平面性•可以容易地定义内外方向、插值操作等网格小知识•三维形体的分段线性（Piecewiselinear）近似•组成成分–几何：顶点–拓扑:边和面•边界边:只与一个面相邻•正则边:与且仅与两个面相邻•奇异边:与多于两个面相邻•流形网格:没有奇异边的网格•封闭网格:没有边界边的网格Non-ManifoldClosedManifoldOpenManifold拓扑v=12f=14e=25c=1g=0b=1图的亏格(genus)：handle的数目。在沿其撕裂后，能够使图保持连通的封闭路径的最大数目的一半Euler-Poincare公式v+f-e=2(c-g)-b游戏时间：猜猜亏格数网格的数据结构表达•网格数据的应用:–渲染–几何查询•face#3包括哪些顶点?•顶点i和顶点j是否相邻?•face#7与哪些面相邻?–几何操作Geometryoperations•添加或者删除一个顶点/边/面•大部分网格难以支持高效的上述操作•一般采用三角流形网格网格的数据结构是否优秀•构建数据结构的时间复杂度•进行一个查询操作的时间复杂度•进行一个网格编辑操作的时间复杂度（更新数据结构）•空间复杂度数据结构举例•面列表（Listoffaces）•邻接矩阵（Adjacencymatrix）•半边结构（Half-edge）一个实际的文件例子.obj文件#Object“object01”gmesh01#NO.points4:v-21.797845.37150v-21.797814.089722.1196v-2.6416214.0897-11.0598v-40.953914.0897-11.0598#NO.normals16:vn0.816500.33330.47140vn00.3333-0.94281…#NO.texutecoordinates4:vt10…#NO.faces4:f1/3/52/2/83/1/11f1/3/73/1/134/4/14f4/4/162/2/101/3/6f4/4/153/1/122/2/9面列表•顶点列表(顶点坐标：coordinates)•面列表-面中顶点的三元组(v1,v2,v3)•查询操作:–face#3包括哪些顶点?•O(1)-查询第三个面的顶点三元组–顶点i和顶点j是否相邻?•O(n)-需要遍历所有的面，效率较低•可满足渲染要求，对于几何处理还不够高效面列表实例面列表的优劣•优点–方便而紧凑–可表达非流形网格•缺点–不能有效地支持点、面之间的邻接关系查询需要查询哪些邻接关系？InputoutputabbrvertexAllneighboringverticesVVAllneighboringedgesVEAllneighboringfacesVFedgeAllneighboringverticesEVAllneighboringedgesEEAllneighboringfacesEFfaceAllneighboringverticesFVAllneighboringedgesFEAllneighboringfacesFF邻接矩阵•将网格视为邻接图•给定一个包含n个顶点的网格，构建一个n*n的矩阵来表达邻接关系–如果顶点i和顶点j邻接，那么矩阵元素(i,j)值为1，否则为0邻接矩阵举例基于邻接矩阵的查询•face#3包括哪些顶点?–O(1)•顶点i和j是否相邻?–O(1)•顶点i与哪些面相邻?–O(n)-遍历所有的面邻接矩阵的优劣•优点–支持顶点之间邻接信息(VV)的高效查询–支持非流形网格•缺点–没有边的显式表达–不支持VF,VE,EV,FE,EF的快速查询半边结构•记录所有的面、边和顶点–几何信息–拓扑信息–附属属性•流行于大部分几何建模应用•AkaDCEL(Doubly-ConnectedEdgeList)半边结构实例•一条半边指向–起始点–所属面–Nexthalfedgeandoppositehalfedge–(可选)previousedge•一个顶点指向–它的某条出射半边•一个面指向–属于它的某条半边Half-edgeOriginTwinIncidentFaceNextPreve3,1v2e3,2f1e1,1e2,1e3,2v3e3,1f2e5,1e4,1e4,1v4e4,2f2e3,2e5,1e4,2v3e4,1f3e7,1e6,1classHalfEdge{HalfEdge*opp;Vertex*end;Face*left;HalfEdge*next;};HalfEdgee;ee-opp()classHalfEdge{HalfEdge*opp;Vertex*end;Face*left;HalfEdge*next;};HalfEdgee;ee-start()e-opp()classHalfEdge{HalfEdge*opp;Vertex*end;Face*left;HalfEdge*next;};HalfEdgee;e-end()e-start()=e-opp()-end();ee-left()e-opp()classHalfEdge{HalfEdge*opp;Vertex*end;Face*left;HalfEdge*next;};HalfEdgee;e-right()e-right()=e-opp()-left();eclassHalfEdge{HalfEdge*opp;Vertex*end;Face*left;HalfEdge*next;};HalfEdgee;e-opp()环左边的面遍历直到e(-next)n=e1.e2.e-next()3.e-next()-opp()4.e-next()-opp()-next()5.e-next()-opp()-next()-opp()6.e-next()-opp()-next()-opp()-next()7.e-next()-opp()-next()-opp()-next()-opp()8.e-next()-opp()-next()-opp()-next()-opp()-next()…untile(-next()-opp())n==e12345678…遍历一个顶点的一环半边半边结构的优劣•优点–所有查询操作时间复杂度均为O(1)–所有的编辑操作时间复杂度均为O(1)•缺点–只能表达流形网格常用的半边结构实现•CGAL–•OpenMesh–细分曲面•虽然理论上可以手动地设定每一个顶点、边、面，但这是异常繁琐的–一个精细的网格往往有上百万个顶点•理想的情况:手工构造一个低分辨率的网格，然后逐渐地用自动算法光滑化，添加更多细节细分曲线细分曲面NURBS•NURBS=Non-UniformRationalB-splines（非均匀有理B样条）隐式曲面•用定义在三维空间中的函数𝜙(𝑥)=0来隐式地表达曲面•容易判断一个点是否在曲面内部–𝜙(𝑥)0内部–𝜙(𝑥)0外部–𝜙(𝑥)=0在曲面上•可高效地进行拓扑变换•高效地进行二元操作：交、并、差等隐式曲面•隐式曲面便于表达复杂的曲面，比如水面•三角网格难以表达水的合并、飞溅、波浪等形变实体建模（CSG）•用简单形体的二元操作来构造复杂形体常用的建模方法•扫描•基于图像的建模方法•过程式建模扫描•构造一个对象的三维模型需要一张或多张深度图像•距离扫描仪测量的是物体表面的三维坐标，并以m*n的距离网格形式返回测量值，这个网格称作深度图像•如果有多张深度图像，对每张深度图像需要计算出一个刚性变换，以与其它深度图像对齐•使用改进版本的ICP算法（IterativeClosestPointAlignment）来计算合适的刚性变换，使得两张深度图像之间点对的最小二乘距离最小移动设备上的3DScanningStructureSensorforiPadAutodesk123DCatch基于图像的建模•从海量图片中构造三维模型（例如从百度上搜索某一名胜的照片）•使用计算机视觉的方法来估计每张照片的相对摄像机位置与朝向，同时得到对象的稀疏点云表达•基本的思想：一个点的位置可以通过多张不同位置拍摄的照片确定（~snavely/bundler/）•给定了这些相机参数和稀疏的点云，有许多致密的的重建算法可以用来重建致密的模型（）。真实的照片重建的模型过程式建模•使用算法创建模型•可容易地构造多样化的模型•一般用来构造复杂的、规则性强的模型–地形–植物–建筑、城市过程式建模•用一个小的数据集或规则来描述目标模型的高层次语义信息–树：分支的性质+叶片的形状–建筑：房间的细分+门/窗的布置•用算法来生成全部的模型–加入随机性–用递归算法毕达哥拉斯树L-System•用来进行植物建模的典型系统•由生物学家Lindenmayer提出，用来研究藻类的生长•递归的形式化语法–符号字母表（端点和非端点）–生成规则集–非端点符号递归地生成新的符号或者符号序列•整个过程从一个初始的符号串开始•最后，由一个解释器将生成的符号解释为几何结构L-System•非端点–A,B:都是画直线•端点–+：右转60度–-：左转60度•初始字符串：A•规则–A→B+A+B–B→A−B−AL-System+栈=树枝•非端点:–X:(无动作)F:drawforward•端点:–+:右转25度–−:左转25度–[:当前状态入栈–]:从栈中读取状态•初始字符串:X•规则:–X→F−[[X]+X]+F[+FX]−X–F→FFL-system•可容易地扩展到3D–用圆柱体来构造树干和树枝–递归地•缩小圆柱体的尺寸•将颜色从棕色变为绿色•用随机L-system来添加更多的变化–为一个符号添加更多规则–随机地选择规则•L-system是一个比较抽象的描述–构造一个指定的形状需要经验分形•从一个形状开始•用缩放的初始形状来替换形状的一部分•递归地进行替换几何建模工具和数据•建模工具–AutodeskMaya(freeforstudents)–Autodesk3DSMax(freeforstudents)–Sk