收稿日期: 2005-05-29; 修返日期: 2005-07-20
基金项目: 北京市教育委员会项目( KM200410028013)
一 种 基 于 半 边 折 叠 的 多 分 辨 率 模 型 构 造 方 法
*
陈 婧, 刘旭敏, 范彦革
( 首都 师范 大学 信息 工程 学院 , 北京 100037)
摘 要: 虚 拟现 实的 真实 感限 时图 形生 成中 加速 技 术十 分 关 键 , 细 节 层 次 模 型 ( LOD) 在 实 时 绘制 复 杂 场 景 中
得到 了广 泛应 用。提 出了 一种 基于 半边 折叠 的多分 辨率 模型 构造 方法 , 该 算法 能够 快速 简单 并有 效 地 减少 模 型
的多 边形 数, 同时 将简 化记 录紧 致地存 储在 隐含 着多 分辨 率模 型的 单分 辨率模 型中 , 减少 了存 储空 间 , 并能 实 现
快速 地提 取及 显示。
关键 词: 半 边折 叠; 多 细节 层次 ; 多分 辨率 模型
中图 法分 类号 : TP391. 72 文 献标 识码 : A 文 章编 号: 1001-3695( 2006) 06-0173-04
Multi-resolution Model Construction Method Based on Half-edge Collapse
CHEN Jing, LIU Xu-min, FAN Yan-ge
( College of Information Engineering, Capital Normal University, Beijing 100037, China)
Abstract: 3D acceleration of real time graphics rendering is very important in virtual reality applications. Levels of Detail
( LOD) are used in mostcomplex rendering system. A multi-resolution model construction method based onthe half-edge col-
lapse is presented. By this method, polygon reduction can be implemented fast and effectively, and the simplification record is
compactly stored in the single resolution mesh model, in which multi-resolution mesh representation is implicit. This can re-
duce the storage and achieve fastextraction and display easily.
Key words: Half-edge; Levels of Detail( LOD) , Multi-resolution Model
在计算机图形学和几何造型中, 常用多 边形网 格( 通常 是
三角网格) 来描 述场景 中的 图形 对 象。由于 测 量得 到的 数 据
分布十分密集, 由此建立的三维模型所得的网格模型通常是由
几十万个, 几百万个, 甚至 上亿个 面片组 成。而随着 虚拟现 实
和科学计算可视化应用的发展, 要求用户能够对复杂场景进行
交互式显示或处理, 而高 度复杂、数目 庞大的 多边形 网格模 型
非常不利于存 储、传输 和 绘制
[ 1]
。 解决 复杂 场 景实 时绘 制 的
一种技术是多细节层次模型( Level of Detail, LOD) 。所谓 LOD
方法, 即为每个物体建立 多个近 似模型, 不同 模型对 物体的 细
节描述其程度是不同的, 细节描述越精细, 模型越复杂, 根据物
体在屏幕上所占区域的大小及用户视点等因素, 为各物体选择
不同的 LOD模型, 从而减少所需显示的多边形数目, 许多 LOD
技术已经成功地嵌入到各种虚拟现实和可视化应用中
[ 2]
。
虽然 LOD描述充分 考虑 了人们 对图 像的 视觉 效果, 为 控
制场景复杂度和提高图形绘制速度提供了非常有效的方法, 但
是由于 LOD 模型存储的 是若 干个不 同细 节层 次的 模型, 在 实
时绘制的时候, 用户是从有限个已经简化的模型中选取与用户
要求的效果差别最小的那个模 型来进 行绘制。当 从一个 LOD
模型向相邻的另一个 LOD 模 型描述 过渡 时, 会出 现不 连续 的
跳变现象, 因此, LOD 技 术 还 只 是 有 限 个单 分 辨 率 模 型 的 组
合, 不是一种非常完 善的多 分辨率 技术。为了 解决这 个问题,
作为传统 CAD 造型系统的 延伸, 图形学 研究 人员 提出 了多 分
辨率造型的概念
[ 3]
。多 分辨 率 的思 想 最早 是由 Clark 在 1976
年提出的
[ 4]
。进入 20 世纪 90 年代以后, 多分辨率模型作为一
种有效地提高绘制速度的方法, 越来越受到重视。多分辨率模
型与 LOD 模型的主要区别, 就 在于 它提 供的 是一 种紧 凑的 数
据表示方法, 多分辨率造型去除了不同细节的网格描述之间的
冗余信息, 结构紧凑, 存储量相对变小。
由于人们常用多边形网格( 特例 为三角形网 格) 来描述 场
景中的物体, 因而生成多分辨率模型的首要步骤就是三维多边
形网格的简化问题。基于上述讨论, 我们提出了一种基于半边
折叠的多分辨率模型构造方法, 该方法是在半边折叠几何元素
简化操作的基础上, 将简化结果存储于一种适合于任意三角网
格模型的多分辨率表示的数 据结构 之上, 所形 成的一 种简单、
紧致且高效的模型。
1 网格简化
网格简化的目的是在尽可 能保持 原模型 可视特 征的条 件
下, 减少模型的多边形( 三角形) 数目, 实 际上就是用 尽可能 少
的表面采样点来表示原始 模型中 尽可能 多的细 节信息。作 为
层次细节( LOD) 技术 的 基础, 近 十 几年 来网 格 简化 的研 究 得
到了广泛的重视, 研究人员 提出了 多种简 化算法, 大 多数都 是
通过几何元素的删除来达 到简化 目的的。其 中比较 具有代 表
性的 三 个 算 法 是: Schroeder 等 人 在 1992 年 提 出 的 顶 点 删 除
法
[ 5]
, Hoppe 在 1993 年提出的能量函数优化法
[ 6]
和 Garland 在
1997 年提出的二 次误 差函 数法
[ 7]
。同 时, 国内 对这 方面 的 研
究也是卓有成 效
[ 8 ~10]
。这 些算 法各 自有 不同 的 特点, 适 应 不
同的情况, Hoppe 提出的算法中使用边折叠进行 模型简化很 容
易构成连续过渡的多个 LOD 表 示模 型, 便于 进行 多分 辨率 管
·371·第 6 期 陈 婧等: 一种基于半边折叠的多分辨率模型构造方法