多边形和三角形网格

,辽宁师范大学计算机与信息技术学院 宋传鸣,多边形和三角形网格,图形与游戏开发的,3D,数学,宋传鸣,多边形和三角形网格,辽宁师范大学计算机与信息技术学院,计算机科学与技术专业研究型课程,几何造型,概览,多边形表示,三角形表示,几何造型技术是一项研究在计算机中如何表示物体模型形状的技术,几何造型技术在航空航天、汽车、造船、机械、建筑和电子等行业得到了广泛应用,并非所有物体的几何形状都可用数学公式,精确描述,采用,大量的平面片,来逼近物体外形,平面片,:,三角形,四边形,或,n-,边形,物体的多边形几何表示实例,概览,多边形表示,三角形表示,多边形表示是图形学中,最常用的物体几何表示方法,野鸭模型的多边形表示包括,6656,个面片,3474,个顶点,(a),线框图,(b),原始法向着色图,(c),平均法向着色图,多边形表示物体的主要来源,概览,多边形表示,三角形表示,通过,三维数字化仪,或者,三维激光测距装置,直接对物体,表面进行采样,来获取相应的顶点数据,三维测量和扫描,多边形表示物体的主要来源,概览,多边形表示,三角形表示,三维数字化仪,多边形表示物体的主要来源,概览,多边形表示,三角形表示,通过,三维数字化仪,或者,三维激光测距装置,直接对物体,表面进行采样,来获取相应的顶点数据,断层扫描重建,如,CT,、,MRI,等值面抽取,原始数据一般为三维空间中的点集,采用适当的重建算法得到其多边形表示,这种基于测量的造型方法适用于外形复杂、难以用数学公式直接描述的实物,多边形表示物体的主要来源,概览,多边形表示,三角形表示,解析数学公式的逼近,常用的物体外形数学表示方法包括,参数曲面,、,细分曲面,、,隐式曲面,等,通过控制逼近误差,对表面进行离散采样,就可以得到满足精度的曲面物体的多边形逼近表示,参数曲面的多边形逼近,多边形表示物体的主要来源,概览,多边形表示,三角形表示,解析数学公式的逼近,细分曲面的多边形逼近,隐式曲面的多边形逼近,多边形表示的数据结构,:OBJ,格式,概览,多边形表示,三角形表示,顶点坐标表,(,x,y,z,),每个顶点处可能有多个平面片,一般情况下顶点数小于面片数,鸭子模型中含有,3474,个顶点,纹理坐标表,(,u,v,),存储多边形表面,每一顶点在相应纹理图像平面上的坐标,以确定表面上各顶点的颜色等材质属性,鸭子的身体、脚趾、眼睛和嘴具有不同的颜色,多边形表示的数据结构,:OBJ,格式,概览,多边形表示,三角形表示,法向表,(,n,x,n,y,n,z,),控制物体绘制时的着色光滑程度,如果顶点法向取作所在,面片的法向,绘制出来的多边形物体是处棱角分明的,如果顶点法向,是周围面片法向的某种平均,则绘制结果是光滑的,基于面片法向着色,基于平均法向着色,多边形表示的数据结构,:OBJ,格式,概览,多边形表示,三角形表示,面表,由指向顶点、纹理坐标以及法向的指针组成,鸭子模型含有,6656,个面,顶点坐标表,v,i,=(,x,i,y,i,z,i,),i,=1,2,顶点数目,纹理坐标表,vt,p,=(,u,p,v,p,),p,=1,2,纹理坐标数目,法向表,vn,a,=(,nx,a,ny,a,nz,a,),a,=1,2,法向数目,面表,f,s,=(,v,i,/,vt,p,/,vn,a,v,i,/,vt,p,/,vn,a,v,j,/,vt,q,/,vn,b,v,k,/,vt,r,/,vn,c,),s,=1,2,面片数,多边形表示的优势,概览,多边形表示,三角形表示,表示简单,可以表示具有任意拓扑的物体,可以表示具有丰富细节的物体,大部分图形硬件支持多边形物体的加速绘制,多边形表示的大规模场景,草地,16.710,6,个多边形,多边形表示的优势,概览,多边形表示,三角形表示,表示简单,可以表示具有任意拓扑的物体,可以表示具有丰富细节的物体,大部分图形硬件支持多边形物体的加速绘制,多边形表示的大规模场景,草地,多边形表示的复杂物体,油轮,多边形表示的不足,概览,多边形表示,三角形表示,只是物体的逼近表示,局部放大将导致几何失真,难以用传统方法修改,(,编辑,),物体外形,缺乏解析表达式,几何属性计算困难,在表示复杂拓扑和具有丰富细节的物体时,数据量庞大,建模、编辑、绘制、存储的负担重,物体的三角网格表示,概览,多边形表示,三角形表示,用三角形组成的面片列表来近似三维模型,容易通过三维扫描技术大量获取,当采用足够多的面片时,可以任意精度逼近复杂曲面,数据结构简单,光照计算和显示速度快,适合并行处理,三角网格的存储,:OBJ,格式,概览,多边形表示,三角形表示,首先是一系列,由,v,开头的行,每行表示一个,顶点,v,后有,3,个浮点数,彼此用空格分开,分别为,x,y,z,坐标,顶点编号从,1,开始,依次类推,然后是一系列,由,f,开头的行,每行表示一个,三角面片,f,后有,3,个整数,彼此用空格分开,对应三角面片的三个顶点的编号,顶点顺序为逆时针,该结构的,优点,格式简单,便于模型的读取和保存,该结构的,不足,不利于检索和遍历,如要按逆时针顺序遍历包含某个顶点的所有三角面片,则需要遍历整个模型,三角网格的半边表示,概览,多边形表示,三角形表示,也称为双向链接边表,(Doubly Connected Edge List),基本思想,把一条无向的边拆分成两条有向的半边,边的方向沿着逆时针方向,半边结构需要存储,顶点,、,半边,和,面,的信息,v,1,v,2,v,3,v,4,v,5,f,1,f,2,f,3,e,1,1,e,2,1,e,3,1,e,3,2,e,4,1,e,5,1,e,4,2,e,6,1,e,7,1,三角网格的半边表示,概览,多边形表示,三角形表示,顶点的数据结构,坐标值,指向以此顶点为起始端点的半边,v,1,v,2,v,3,v,4,v,5,f,1,f,2,f,3,e,1,1,e,2,1,e,3,1,e,3,2,e,4,1,e,5,1,e,4,2,e,6,1,e,7,1,顶点,坐标,以此为起点的半边,v,1,(x,1,y,1,z,1,),e,2,1,v,2,(x,2,y,2,z,2,),e,1,1,v,3,(x,3,y,3,z,3,),e,4,1,v,4,(x,4,y,4,z,4,),e,7,1,v,5,(x,5,y,5,z,5,),e,5,1,三角网格的半边表示,概览,多边形表示,三角形表示,半边的数据结构,起始顶点的指针,邻接面的指针,(,如果为边界,指针为,NULL),下一条半边,(,逆时针方向,),相邻的半边,前一条半边,(,可选,),v,1,v,2,v,3,v,4,v,5,f,1,f,2,f,3,e,1,1,e,2,1,e,3,1,e,3,2,e,4,1,e,5,1,e,4,2,e,6,1,e,7,1,半边,起点,相邻半边,面,下条半边,前条半边,e,3,1,v,3,e,3,2,f,1,e,1,1,e,2,1,e,3,2,v,2,e,3,1,f,2,e,4,1,e,5,1,e,4,1,v,3,e,4,2,f,2,e,5,1,e,3,2,e,4,2,v,5,e,4,1,f,3,e,6,1,e,7,1,三角网格的半边表示,概览,多边形表示,三角形表示,面的数据结构,边界上的一条半边,v,1,v,2,v,3,v,4,v,5,f,1,f,2,f,3,e,1,1,e,2,1,e,3,1,e,3,2,e,4,1,e,5,1,e,4,2,e,6,1,e,7,1,面,半边,f,1,e,1,1,f,2,e,3,2,f,3,e,4,2,三角网格的半边表示,:,操作举例,概览,多边形表示,三角形表示,按逆时针顺序遍历包含某个顶点的所有三角面片,三角网格顶点的额外信息,概览,多边形表示,三角形表示,纹理映射坐标,:,对每个需要渲染的像素都要计算,2D,纹理映射坐标,这些坐标用以索引纹理图,从而为相应像素着色,表面法向量,计算光照,进行背面剔除,模拟例子在表面弹跳的效果,光照值,三角网格顶点的额外信息,概览,多边形表示,三角形表示,光照值,:,对每个需要渲染的像素都要计算,2D,纹理映射坐标,这些坐标用以索引纹理图,从而为相应像素着色,表面法向量,计算光照,进行背面剔除,模拟例子在表面弹跳的效果,通过只考虑正面而加速碰撞检测,大规模网格模型,:,雕塑,概览,多边形表示,三角形表示,三角网格操作,概览,多边形表示,三角形表示,逐片操作,:,三角网格的一系列基本操作都是逐点和逐三角形应用基本操作的结果,渲染三角网格、旋转和缩放网格等,焊接顶点,:,当两个或更多顶点相同,(,也许有误差,),时,将它们焊接在一起,只保留一个,删除其它的顶点,扫描三角形列表,将对,B,的引用全部换成对,A,的引用,现在,B,是孤立点,将它从顶点列表中删除,三角网格操作,概览,多边形表示,三角形表示,焊接顶点时会出现的问题,焊接前应去除孤立点,否则易导致网格变形,当两个顶点均来自细长三角形时,焊接可能产生退化三角形,三角网格操作,概览,多边形表示,三角形表示,焊接顶点时会出现的问题,焊接若应用原顶点的平均作为新顶点,可能会导致多米诺效应,三角网格操作,概览,多边形表示,三角形表示,面拆分,:,复制顶点,使边不再被共用,使得几何间断的地方拓扑也是间断的,三角网格操作,概览,多边形表示,三角形表示,边缩坍,:,将边缩减为顶点,网格消减,:,将三角形和顶点数较多的网格变为三角形和顶点数较少的网格,并且保持网格外观和主要顶点尽可能不变,