一种基于半边折叠的LOD模型构造方法

吴捷　+唐红锁

摘要摘要：实时渲染技术一直是图形学中的热点问题，大量模型数据给实时渲染带来了极大的挑战。作为一种有效的控制模型精度方法，LOD算法近年来得到了广泛重视，但已有算法在计算复杂度和保持外形特征等方面兼顾不周。针对此问题，提出了一种基于半边折叠的LOD模型构造方法，在空间距离计算、尖锐特征保持、光照效果等几方面进行了改进。实验结果表明，该算法能较好地保持模型的外形特征，实现起来快速有效。

关键词关键词：实时渲染；LOD；半边折叠

DOIDOI：10.11907/rjdk.1431086

中图分类号：TP317.4

文献标识码：A文章编号

文章编号：16727800（2015）004014503

0引言

实时渲染技术一直是图形学领域研究的热点。当需要生成具有真实感的模型时，由于模型本身的复杂性，实时实现往往很难。

所谓LOD技术，就是针对每个物体建立多个简化模型，各个模型的简化率互不相同。根据物体在屏幕上所占

区域的大小及距离用户远近等视觉因素，为各物体选择不同的简化模型，从而减少实际显示所需的数据量。由于网格特征的复杂性与多样性，通常采用海量的三角网格对模型进行描述，因而LOD模型生成就转化为三角网格的简化问题，即把一个复杂三角网格表示的模型用一系列简化的模型表示，简化模型保持了原模型的基本特征，但顶点数目少于原网格的顶点数目。

三角网格简化的方法较多，主要有基于顶点删除的简化算法、重新划分网格的简化算法、小波分解的简化算法、边折叠的简化算法等等。近年来国内有很多关于网格简化的研究成果。其中文献[1]基于顶点聚类提出了新的网格简化算法，实现快速，但是简化结果误差较大，对于尖锐特征比较明显的模型，简化效果欠缺；文献[2]基于边折叠，设计了一种保持外形特征的网格简化算法，但是未能有效处理边界点和边界三角形。本文基于半边折叠提出了一种新的网格简化算法，并以此算法为基础设计了LOD模型的构造方法。

1基于半边折叠的网格简化算法

1.1算法关键问题

本文对传统的边折叠算法进行了改进，采用半边折叠。作为边折叠算法的特例，半边折叠的简化流程和边折叠是一致的，一次半边折叠移去一个顶点和两个面。不同之处在于，半边折叠不产生新的顶点，而是将待折叠的边uv折叠到其中的一个顶点v 上，顶点u 被顶点v 所代替（如图1），这样就减少了内存占用，且不必像文献[3]那样为了计算新顶点的位置而进行复杂计算，有利于渲染系统构建可以直接处理的数据结构，提高渲染效率。

（u→v）与（v→u）是两个不同的删除操作，需要分别计算半边折叠的代价，在简化队列中对半边折叠代价进行排序。本文算法的关键问题就在于如何确定半边折叠顺序，也就是顶点的先后删除顺序。

1.2算法核心内容

为了确定顶点的先后删除顺序，本文引入了顶点“价值”概念：计算每个顶点的“价值”，并放入网格简化队列中。在进行简化时，价值越低的点先出队并被删除，然后更新队列中受影响的顶点信息，再对队列重新排序。本文给出的顶点价值计算公式为：Cost（v）=αD（v）+βN（v）+γC（v），其中D（v）为空间距离值，N（v）为顶点法矢值，C（v）为顶点尖锐度，α，β，γ为用户设定参数。

空间距离值计算。Garland在1997年提出了二次误差测度（QEM）概念，以新顶点到被折叠边的两个顶点相关联平面的距离平方和作为误差测度，取得了较好的简化效果。近年来很多学者的研究都是基于Garland的算法进行改进；对QEM算法进行研究发现，QEM计算的是点到三角网格所在平面的垂直距离，而不是点到三角面的实际距离[4]。本文以顶点到三角面的实际距离之和作为误差的基本控制手段。下面给出点到三角面实际空间距离的计算过程：

（2）顶点法矢值计算。在实时渲染中往往会大量运用光照，而由三维显示原理可知， 在光照模型中，物体顶点和面的法向变化对视觉的影响很大。所以本文在顶点价值计算中加入了法矢值，本文设置的顶点法矢值N（v）计算公式为：

N（v）=与该顶点相关联的面的法向量之和[]与该顶点相关联的面的数量

（3）顶点尖锐度计算。很多简化算法在处理时往往忽略了模型的尖锐特征，为了保持模型重要的细节特征，本文引入特征边和顶点尖锐度概念。

特征边：预先设定阈值θ，对于某一边，若与该边相连的两个面的外法线夹角大于θ，则记该边为特征边。在有边界的模型中，边界边也视为特征边。

顶点尖锐度：对于每个顶点，定义其所关联的特征边数量为其尖锐度。

1.3数据结构设计

某些文献在构造LOD模型时，往往缺乏连续性，不能逆向恢复。本文因为采用了半边折叠算法，不会产生新的顶点，所以非常便于设计数据结构来保持模型的连续性和简化过程的可逆性。

本文进行数据结构设计时主要定义了两个类：顶点类和三角面类。在三角面类中定义了该面所包含的顶点信息和法向量，在顶点类中定义了该顶点的坐标、编号、尖锐度、相邻顶点、顶点价值等信息。有了这些信息，就可以对模型进行逆向恢复。比如当折叠一条边uv时，可以用类似map[v→id] = u→id这样的语句来保存简化记录；当需要对模型逆向恢复时，只需要依次调出记录即可，非常适合LOD模型的构建。

基于半边折叠的简化算法主要步骤：①读入外部数据文件，设计结构组织数据，用户输入简化率、阈值θ及模型简化参数α，β，γ；②计算每个顶点的空间距离值、顶点法矢值及顶点尖锐度，得到各个顶点的价值，并在简化队列中进行排序；③按照简化率要求删除价值小的顶点，更新队列，直至达到简化要求。

2实验结果及分析

对Stan Melax[5]系统进行一些改进，可以非常方便地实现本文算法。本文选择VC++和OpenGL作为三维开发工具，硬件配置是奔腾IV 3.0GHZ处理器，1G内存，操作系统软件是Windows XP（32位）。

图3是采用本文算法对人头模型进行简化的演进图。初始模型有6736个顶点，从图3中可以看出，即使在

顶点数较少时，采用本文算法得到的简化模型在脸部重要

特征的保持上仍然做得较好。图4是本文算法和Garland算法对牛模型进行简化的效果比较。可以看出，用Garland算法简化后的网格分布比较均匀，但模型的重要特征保留不够明显，而本文算法对牛的眼睛、鼻孔、耳朵等重要特征保持得更好。表1给出了本文算法和Garland算法的对比数据，采用本文方法进行简化时，因为采用半边折叠算法，不需要进行新顶点位置的计算，所以执行速度更快。数据显示：当简化率为79.4%时，所用的时间为1.32s，而Garland算法需要1.57s，所以本文算法更加有利于LOD模型的构建。

3结语

本文基于半边折叠算法，提出了一种新的LOD模型生成方法，与其它网格简化算法相比，本文算法在空间距离计算和尖锐特征保持等方面作了一些改进。实验表明，该算法在网格数较少时能较好地保持模型的基本外形特征，并且实现快捷有效。

参考文献参考文献：

[1]吴有用， 万旺根， 金龙存， 等. 一种新的连续性LOD实现算法[J]. 微电子学与计算机，2010，27（6）：185187.

[2]薛峰，袁成凤.保持外形特征的网格简化算法[J].计算机应用，2010，30（9）：24312433.

[3]裴艳云，陈飞翔.一种基于不平滑度的网格简化算法[J].计算机工程与应用，2013，49（14）：174177.

[4]唐杰，张福炎.一种基于误差控制的网格多分辨模型生成算法[J].计算机学报，2005，28（9）：15341539.

[5]STAN MELAX. A simple， fast， and effective polygon reduction algorithm[J].Game Developer， 1998（11）：4449.

责任编辑（责任编辑：杜能钢）