《计算机图形学基础chapadd》由会员分享，可在线阅读，更多相关《计算机图形学基础chapadd（52页珍藏版）》请在金锄头文库上搜索。
1、计算机图形学胡事民胡事民计算机科学与技术系计算机科学与技术系清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学第六讲之补充第六讲之补充层次细节简化技术清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学主要内容主要内容 层次细节简化的背景和定义网格简化的基本操作 网格简化的基本操作 长方体滤波 顶点删除技术 渐进的网格简化技术 基于二次误差度量的几何简化技术 专题基于面片收缩操作的有效网格化简方法 专题：基于面片收缩操作的有效网格化简方法清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学背景: 图形学转折期的新方向背景
2、: 图形学转折期的新方向 真实感的实时绘制问题变的日益突出，因为做实 时绘制而开始了模型简化今天从“场景简化时绘制，而开始了模型简化。今天从场景简化 技术加速真实感画面生成”角度来讲简化。 92年开始，面片简化、压缩、信号处理、纹理合 成成为SIGGRAPH会议的一个热门话题；如今网 格模型的处理，如拓扑修复、细节建模、模型的 动画变形仍然是研究焦点；从而演化为数字几何动画变形仍然是研究焦点；从而演化为数字几何 处理这一研究方向清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学层次细节简化的应用层次细节简化的应用 层次细节简化(LOD：Level of Details
3、)技术主要 应用在应用在：简化采样密集的多面体网格激光扫描测距系统扫描真实三维物体维场景的存储 传输 及绘制三维场景的存储/传输/及绘制清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学层次细节简化的定义层次细节简化的定义 层次细节简化技术就是在不影响画面视觉效果 的条件下通过逐次简化景物的表面细节来减的条件下，通过逐次简化景物的表面细节来减 少场景的几何复杂性，从而提高绘制算法的效 率。清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学 该技术对一个原始多面体模型建立几个不同逼 近程度的几何模型。近程度的几何模型。 从近处观察物体时，采用精
4、细的模型，从处察物体时采用较粗糙的模型 从远处观察物体时，采用较粗糙的模型。 当视点连续变化时，在两个不同层次的模型之间 存在一个明显的跳跃，有必要在相邻层次的模型 之间形成光滑的视觉过渡，即：几何形状过渡之间形成光滑的视觉过渡，即：几何形状过渡 (geomorphs)。清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学层次细节简化的研究方向层次细节简化的研究方向 总之，层次细节简化技术的研究主要集中在： 建立不同层次细节的模型对任意给定的复杂多边 建立不同层次细节的模型。对任意给定的复杂多边 形网格，由精细至粗糙建立一模型序列： 其中M01,nMMML其中。 建立相
5、邻层次的多边形网格之间的几0MM=1,(0)iiM Min+ P ()()()ru vr u vu v=+ n近似地定义原始多边形网格沿其正、负法向的等 面和( , )( , )( , )ru vr u vu v=+ nP 距面和。等距面和上对应顶点， 及其法向()P+()P iv+ iv()P+()P量可分别表示为iiivv+=+ niiivv= niii+=nnn上述方法生成的可能出现自交现象。iiiiiivvniiinnn()P清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学 我们用解析法计算 。现来考察上的任一 P现来考察上的任三角形。1 2 3v v v对
6、上每个与三角形不相邻的三角面片，判P1 2 3v v vj对上每个与三角形不相邻的三角面片，判 别是否与的基本柱体相交。可计算得到到的距离P1 2 3jj1 23v v vjqv v v清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学的距离。1 23v v vjCohen的点删除流程Cohen的点删除流程 采用贪婪搜索策略，将原表面P的所有顶点列 入待处理的顶点队列入待处理的顶点队列。 对当前待处理顶点队列中的一顶点，算法尝试从P 上删除该顶点及与该顶点直接相邻的三角面片， 并试图用如下页所述的三角剖分方法来填补顶点并试图用如下页所述的三角剖分方法来填补顶点删除后在
7、表面P上形成的空洞。清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学 若空洞位于P的包络内且能成功地被填补，则从当前队 列中删除该顶点，简化表面P的模型并重构原来与该顶列中删除该顶点，简化表面P的模型并重构原来与该顶 点相连接的各顶点的拓扑关系。否则，该顶点从当前 待处理队列中退出表面P保持不变上述过程直到待待处理队列中退出，表面P保持不变。上述过程直到待 处理顶点队列变空为止。填补空洞 方正率位于P的包络内 填补空洞: 方正率，位于P的包络内。清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学参考文献参考文献 Cohen J, Varsh
8、ney A, Manocha D, and Turner D, Simplification Evvelopes Computer Graphics 1996 119-Simplification Evvelopes, Computer Graphics, 1996, 119- 128.清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学渐进的网格简化技术渐进的网格简化技术 渐进网格算法中，任一网格均可表示为一粗网格 及n个逐步细化网格的变换且有 M0M(1 2)iM inMM=及n个逐步细化网格的变换，且有 一张网格可定义为1个二元组。(1,2, )iM in=LMM
9、=M(, )K V其中 是一个单纯复形(simplicial complex)，它表示了 的顶点、边和面的邻接关系；MK是的顶点位置向量集，它定义 了网格在中的形状。3|1,2,iVvRim=LMM3R清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学 单纯复形由顶点集及其称之为单形的非空 子集组成K1,2,im=L 子集组成0-单形即为顶点，1-单形为一条边，而2- 单形为个面 iK , i jKi j kK单形为一个面。 , , i j kK清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学拓扑实现的概念拓扑实现的概念 值得注意的是，单纯
10、复形并不包含点集 的所有子集，它仅包含了构造网格所有面边顶K1,2, im=LM的所有子集，它仅包含了构造网格所有面、边、顶 点的子集。为在结构上刻划单纯复形，我们引进拓扑 实现(topological realization)的概念M|K实现(topological realization) 的概念。|K清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学 若将顶点看成为 中的基向量 则定义在中的集合为的拓扑实现： (1,2,)iim=LmR0,0, ,0,0iei=LLmR|KK则定义在中的集合为的拓扑实现：其中 为的个单形为 在空间中的顶点的凸mR|KK|sKKs
11、=U| |其中s为的一个单形， 为s在空间中的顶点的凸 包。K| | smR清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学几何实现的概念几何实现的概念 为此我们记，称为在中的几何实现 (geometric realization)。M| |VK=3R 若不自交，则为1-1映射。此时， 为一嵌入映 射，即对，存在唯一m维向量，使(|)VKVV(|)VpK |bK 得。我们将 b 称为 p 关于单纯复形的重心坐标 向量(barycentric coordinate vector)。事实上，b可表示为:( )Vpb=1mii ibb e=容易知道，当为一三角片网格时，上
12、的任一点的 重心坐标向量 中至多只有三个分量非零。()vKbM清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学显示能量函数度量显示能量函数度量 有了上述定义，Hoppe采用显式能量函数来度量 简化网格与原始网格的逼近度(HOPP96)：()E M 简化网格与原始网格的逼近度(HOPP96)：(6.3)其中为的离能量定义为点集到()()()()()distspringscalardiscE MEMEMEMEM=+其中为的距离能量，定义为点集到 网格的距离平方：()distEM1, ,nXxx=MnM(6.4)21()( ,()ndistiV iEMdxK=清华大学计算
13、机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学 （6.3）式中为的弹性能量，这相当于在的每条边上均放EMM为的弹性能量，这相当于在的每条边上均放 置一条弹性系数为 的弹簧，即(6 5)springEMMk2()EMk(6.5)度量的标量属性的精度，而则度量了 , ()springij i jKEMk vv=()scalarEMM()discEMM上视觉不连续的特征线（如边界线、侧影轮廓线等） 的几何精度。清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学边收缩变换边收缩变换Hoppe利用边收缩变换(edge collapse transformati
14、on)来 逐步迭代计算上述能量的优化过程逐步迭代计算上述能量的优化过程。 下图给出了一个边收缩变换的过程，它将该边的两个 端点收缩为个顶点经过这个变形后其相()v v端点收缩为一个顶点。经过这个变形后，其相 邻两个面和均退化为一条边。(,)stv vsv , stlv v v ,tsrv v v清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学 因此，初始网格可经过 组的边收缩变形后简化 为：nMM =0Mn 为：M10110necolecolecol nMMMM = 清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学顶点分裂变换顶点分裂变换
15、 顶点分裂变换(vertex split transformation)由于边收缩变换是可逆变换我们称其逆变换为 由于边收缩变换是一可逆变换，我们称其逆变换为 顶点分裂变换。ecol清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学 Hoppe利用式(6.3)来选择这些变换，使变换前 后两网格间的能量差达到最小后两网格间的能量差达到最小。E清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学参考文献参考文献Hoppe H, DeRose T, Duchamp T, Mesh Optimization, Computer Graphics 199
16、3 27-4 19-26Computer Graphics, 1993,27-4,19-26.Hoppe H, Progressive Meshes, Computer Graphics, 1996, 30 4 99 10830-4, 99-108.清华大学计算机科学与技术系计算机图形学清华大学计算机科学与技术系计算机图形学基于二次误差度量的简化技术基于二次误差度量的简化技术 Hoppe的边收缩(edge collapse)操作可推广为一般的顶点 合并变换来描述，其含义是将场景中的两个12( ,)v vv合并变换来描述，其含义是将场景中的两个 顶点移到一新的位置，将连向的所有边都 连向并删除所有退化的边和面片12( ,)v
