论文部分内容阅读
层次细节(Levels of Detail,LOD)方法是一种全新的模型表示方法,改变了传统的“图形质量越精细越好”的观点,在实时图象通信、碰撞检测、限时图形绘制、交互式可视化和虚拟现实等领域有广泛的应用。层次细节方法通过建立原始精细模型的多个近似简化模型,表示原始模型不同程度的细节,使得图形绘制系统可以在不同情况下针对待绘制景物的重要度、对绘制时间的实时性要求等因素,选用或重建适当的层次细节模型,快速、有效的对复杂场景进行绘制,在保证实时图形显示的前提下,最大程度地提高视觉效果。渐进层次细节方法是连续分辨率的表示法,图形可以逐渐地变化,网格的形状不会出现突然的变化。拓扑简化通过改变模型的拓扑来对网格进行简化,能够将任意网格逐渐简化至一个最简单的亏格为0的表面(称为四面体)。在层次细节方法中应用拓扑简化,能够对简化过程进行优化,产生更好的简化效果。目前还没有一种渐进层次细节方法能够进行拓扑简化。现有的层次细节方法不能一直保持模型的二维流形性。在计算机图形学中,如何保持模型的二维流形性是一个基础性的重要课题。许多在计算机图形学中常用的算法都要求或假设被操作的模型是二维流形的,比如细分(subdivision)操作,就要求网格必须是一个有效的二维流形体。如果模型是非二维流形体,这些算法或者不能处理,或者采取特例的方式来处理,但算法往往会变得非常复杂。在层次细节的运算中,如果不能保证模型的二维流形性,一些意想不到的奇异体就会出现。本文研究并提出了一种能够进行拓扑简化,并一直保持模型的二维流形性的渐进层次细节方法,主要取得了以下创新性成果:1.提出了一种新的基于图形旋转系统的数据结构——双链接旋转系统(Doubly Linked Rotation System,DLRS)数据结构,并在DLRS数据结构上构造了一种完备(Complete)的和健全(Sound)的操作集合。大多数现有的数据结构不能一直保持模型的二维流形性。本文提出的DLRS数据结构只支持二维流形体的表示,能够完整地表示多面体的顶点、边、面之间的所有9种拓扑关系,是一种完全拓扑关系表达的数据结构。本文提出的DLRS数据结构上的操作集合是完备的和健全的,完备的是指任何一个二维流形体都可以通过该操作集合中的一系列操作来生成,健全的是指一个二维流形体如果使用该操作集合中的任何一个操作都仍然保持着二维流形性。因此,采用DLRS数据结构表示网格模型,并只采用其操作集合中的操作来对模型进行操作,就可以保证模型始终是二维流形的。与双链接面列表(DLFL)相比,DLRS结构更为简单直观,算法实现简单,与图形邻接表和双链接边列表(DCEL)相比,DLRS效率更高。并且,一个图的DLRS数据结构表示与其DLFL和DCEL数据结构表示能够在线性时间内互相转化。2.提出了一种新的渐进层次细节方法——基于图形旋转系统的渐进层次细节方法(Progressive LOD based on Graph Rotation System,PLG方法)。PLG方法能够进行拓扑简化,并且保持模型的二维流形性。PLG方法采用渐进方式,图形可以逐渐地变化,是一种无损的方法。PLG方法采用本文提出的DLRS数据结构表示模型,以基网格和操作序列的形式表示及存储层次细节。PLG方法分为两个部分,一个部分用于生成层次细节,是一个离线的前处理过程,另一个部分在线使用层次细节,是一个实时绘制过程。生成层次细节过程的操作分为两个层次:直接操作层次和间接操作层次。直接操作层次的操作是DLRS数据结构操作集合里的操作,在前处理过程中得到的操作序列就是这些操作。间接操作层次的操作分为两类,一类是不改变拓扑的操作,另一类是拓扑改变操作。PLG方法支持三角形网格和多边形网格,支持多种误差估计方法。3.提出了基于图形旋转系统的边收缩(Edge Collapse)操作、顶点删除(Vertex Decimation)操作、CutTunnel/CreateTunnel操作和PCreateTunnel/PCutTunnel操作,这6种操作都能够保持模型的二维流形性。基于图形旋转系统的边收缩操作和顶点删除操作是PLG方法间接操作层次的不改变拓扑的操作。CutTunnel/CreateTunnel操作和PCutTunnel/PCreateTunnel操作是拓扑改变操作。CutTunnel操作能够切断一根复杂的柄,也可以封闭一个洞,CreateTunnel是其逆操作。这两个操作使用方便,执行速度快。PCutTunnel操作用一个平面切断一根柄,在切断柄处的模型视觉上不会发生变化,操作效果好,PCreateTunnel操作是其逆操作。PCutTunnel/PCreateTunnel操作解决了CutTunnel/CreateTunnel操作对模型外观改变较大的问题。4.采用本文提出的DLRS数据结构、PLG方法和基于图形旋转系统的边收缩操作、顶点删除操作、CutTunnel/CreateTunnel操作和PCutTunnel/PCreateTunnel操作,对Stanford大学的cow、bone、bunny、dragon和buddhaf模型进行了实验,实验模型运行速度很快,画面流畅,所有模型都始终保持了二维流形性。实验结果表明,本文提出的DLRS数据结构、PLG方法和基于图形旋转系统的边收缩操作、顶点删除操作、CutTunnel/CreateTunnel操作和PCutTunnel/PCreateTunnel操作效果很好,是完全可行的。