（应用数学专业论文）虚拟现实技术的算法基础.pdf

艘拟现实技术驰算法基础曼垦 拳数学研究研博士研究童翘进 2 0 0 1 年1 2 月 a b s t r a c t t h es t u d yo fb a s i ca l g o r i t h m sf o rv i r t u a lr e a i i t ya l em a d ei nt h i st h e s i s t h e m e t h o d sh o wt og e n e r a t er e a lt i m er e n d e r i n go np cb a s e d0 ng e o m e t r ym o d e l sa r e d i s c u s s e d s u c ha ss c e n eo r g a n i z a t i o n v i s i b i l i t y r e p r e s e n t a t i o no fc o m p l e xo b j e c t sa n d d y n a m i co p e r a t i o nw i t h v i r t u a le n v i r o n m e n t s t h et h e s i sc o n s i s t so f f o u r c h a p t e r s i n c h a p t e r 1 ab r i e fs u r v e yo fv i r t u a lr e a l i t yi sp r e s e n t e d t h e nt h er e s e a r c h p r o b l e m s t h e b a s i ca p p r o a c h e sa n dt h em a i nr e s u l t si nt h i st h e s i sa r ei n t r o d u c e d c h a p t e r2g i v e st h ea l g o r i t h m so fs c e n eo r g a n i z a t i o na n dv i s i b i l i t y a f t e rs o m e r e l a t e dw o r k so fv i s i b i l i t ya r eg i v e n t h eo r g a n i z a t i o no fs c e n e si n s i d eb u i l d i n g sa r e f i r s td i s c u s s e d a n da na l g o r i t h mt oc a l c u l a t ep o t e n t i a l l yv i s i b l es e t si nr e a lt i m ei s g i v e n t h i sa l g o r i t h mg e n e r a l i z e dt e l l e r s t e s e 9 1 a l g o r i t h m t h e t e r mo f w a l l so f t h eb u i l d i n g ss h o u l dp a r a l l e lt ot h ec o o r d i n a t ea x e s i sd i s m i s s e d t h e nan e wv i e w w f r u s t u mc u l l i n gb a s e do i lo r i e n t e d b o u n d i n gb o xi sg i v e n f i n a l l y t h eo r g a n i z a t i o no f g e n e r a l s c e i l e si s d i s c u s s e d a na l g o r i t h m f o rs c e n ed i v i s i o nb a s e do no r i e n t e d b o u n d i n gb o x i sg i v e n a l lt h ea l g o r i t h m si nt h i sc h a p t e ra r er e a l i z e do np c c h a p t e r3g i v e st h ea l g o r i t h m so fo b j e c tr e p r e s e n t a t i o n s i m p l i f i c a t i o na l g o r i t h m s t og e n e r a t el o d sa r ed i s c u s s e df i r s t t h ec o n c e p to fp s e u d o p l a n ei s g i v e nu s e dt o g e n e r a l i z eb a c k f a c ec u l l i n gt ob a c k r e g i o nc u l l i n g al a i e r a r c h y d a t as t r u c t u r ef o r r e p r e s e n t a t i o ng e n e r a lp o l y h e d r a b a s e d p s e u d o p l a n ei sg i v e n c h a p t e r 4 d i s c u s s e ss o m e a l g o r i t h m s f o r d y n a m i co p e r a t i o nw i t h v i r t u a l e n v i r o n m e n t s a na l g o r i t h mf o ro b j e c tc o l l i s i o ni nv i r t u a le n v i r o n m e n t si sd i s c u s s e di n s e c t i o n4 i t h ec o l l i s i o np r o b l e mi st r a n s l a t e df r o m3d i m e n s i o nt o2d i m e n s i o n 髓e q u e s t i o ni sc h 赫g e dt ou n i o na n di n t e r s e c t i o no fs i m p l ep o l y g o n s i t sr u n n i n gt i m e c o m p l e x i t yi s0 r n n k t o g m n i ns e c t i o n4 2 ap r a c t i c a la n de a s yt oi m p l e m e n t a l g o r i t h mi sg i v e n t os o l v et h e q u e s t i o no ft r i a n g u l a t i o ns i m p l ep o l y g o n w i t hh o l e s i t s w o r s tr t t r m i n gc o m p l e x i t y i s o 似 1 o 1 0 9 i 1 i ns e c t i o n 4 3 黼a l g o r i t h m t om o d i 母s o l i dm o d e li nr e a lt i m ei sg i v e n t h i sa l g o r i t h mi su s e dm a i n l yi nc n c m a c h i n es i m u l a t i o n 塞型堡壅堡垄墼篓婆篷塑 蔓璺奎鲎墼差受窭璧塑生望塞兰蛰塑 i 塑 垩 互璺 k e y w o r d s v i r t u a lr e a l i t y o c c l u s i o nc u l l i n g h i e r a r c h i c a lo r i e n t e d b o u n d i n gb o x l o d p s e u d o p l a n e b a c k r e g i o nc u l l i n g o b j e c tc o l l i s i o n t r i a n g t f i a t i o n c n cm a c h i n e s i m u l a t i o n 感谢 殛 6 8 7 9 s 乍者翦先要感谢导师谭永基教授和来松媾士多年来静悉心指导和热心帮 助 他们孜孜不倦的探索穗神鞠为人炳表的风范给传者以很深的教诲 本文楚 在他们韵直接指学下完成的 他们一囊关心凄论文的进展情况 势以敏锐的洞 察力在许多问题上给作者以及时的指点 因此 本文得以顺利完成 凝聚这两 位老师的丈整心蘸 为此 作者特呈上诚挚的谢意 在写作论文期阁 应用数学开发中心昀诲虹老师提供了太鬟的帮助 为充成 本文的第四章第 节 许虹老师和作者展开了大霪的讨论 提出了不少鏖发瞧 和建设性的意见 谨致以由衷的感谢 牛文博嗣志和作者对第四章第三节的合 作是必不可少的 在此向他深表感谢 作者还要感谢数学研究所的夏鲁同悫 在作者就读媾士研究生期间 援供了 不少帮助 滏后 向这些年来从各方丽给予俸者以关心和帮助的师长们和朋友们致以出 衷的感谢 虑拟现蜜技术的算法基础 复旦大学数攀弩 竟掰鞲i 醇 究生宴 避2 0 0 1 年1 2 月 1 背爨 第一章引论 虚拟现实c v i r t u a lr e a l i t y 简称v r 是一释纂予可计算镶慧的沉浸式交夏 环境 其体地说 就是采用猷计算枫技术为核心的现代离秘袋生成逼真的棍 听 触觉一体纯的特定范翻的缝拱环境 髑户缮助必器的设备以自然黔方式与 虚拟环境中懿对象进行交嚣作用 槽蔓影响 扶蔼产生 沉漫 予簿涵真实环 境的感受和体验 v r 带来了入机交嚣的辩概念 额内容 掰方式弱新方法 使 得人橇交匿的内容更加丰富 形象 方式更加鸯然 和谐f k a l a 9 3 l l 发展历史 1 9 6 5 年 s u t h e r l a n d s u t h 6 5 管次提出了包括其有交互图形显示 力反馈 设备以及声音撮示的虚拟现实系统的基本思想 从此 人们正式开始了对虚拟 现实系统的研究探索历程 随鹰的1 9 6 6 年 美国m i t 的棒曹实验室正式开始了 头盔式显示器 h m d 的硬劁工俸 在遮第 个h m d 的样机完成不久 研制者又 把能模 笙l 力爨秘触觉的力反馈装置加入到这个系统中 1 9 7 0 年 出现了第 个 功能较齐全的h m d 系统 基于从6 0 年代以来群取得的一系列成就 美国的j a r o n l a n i e r 在8 0 年代裥芷式提出了 v i r t u a lr e a l i t y 一试 8 0 年代 美国字航髑 n a s a 及甍霆蘑防部缀织了一系列育芙虚拟现实技 术的研究 并取得了令人瞩强骢研究或聚 扶箍g l 邋了人们对虚拟现实技术薛 广泛关注 1 9 8 4 年 n a s aa m e s 研究中心寝熬行壤探测实验室的m m c g r e e v y 搬 j h u m p h r i e s 绝织汗发了用予火鏊撵铡豹虚按环境视觉显示器 将火凄搽测器发 圆的数撼输入计算瓤 为地霹研究人员构逡了火星衷落的三缝虚拟环壤 f m h r 8 6 在随厨的虚j 茧 交置环境工作站硬甓中 他们又开发了遽用多蕊感 个人仿真籍和逶璜设备 遴入粥年代 迅遽发展的计算j 瓿硬孵技术与不断改进的计算机软件系统榴 跹配 使得基于丈捌数据集会的声音和蘑裂的实时动画制作成为爵能 入机交 爱系统的设计不断创新 新颖 实用的输入输出设簧不断她进入市场 丽这些 都为虚j 薹c 现实系统驰发展打下了良好的基础 例如1 9 9 3 年的11 月 字航员荦 耀虚拟瑷实系统成功地究成了献航天飞机韵运输舱内取出新的望逮镜嚣扳的工 作 丽丽虚拟现实技术设计波膏7 7 7 获得成功 燕近年来 l 超科技羿瞩籍的又 盛摄骚舞蒎采於捧法基础复虽夫学靛学研究所牌上骈究燕支 避 2 0 0 1 苹j 2 后 一件工作 可以着出 正是因为虚拟现实系统极其广泛的应用领域 如娱乐 军事 航天 设计 生产制造 信息管理 商贸 建筑 医疗保险 危险殿恶 劣环境下的遥操作 教育与培训 信息可视化以及远程通讯等 人们对迅速发 展中的虚拟现实系统的广阔应用前景充满了愤憬与兴趣 l 2 虚拟现实的基本过程 实物虚化 虚物实化和高性能的计算处理技术是v r 技术的三个主要方面 实物虎化是将现实世界的多维信息映射到计算机的数字窀间生成相应的虚拟世 界 为高性能的计算处理提供必要的信息数据 虚物实化通过备种计算和仿真 技术使计算机生成的虚拟世界中的事物所产生的各种刺激以尽可能自然的方式 反馈给用户 1 2 1 实物虚化 实物虑化主要包括基本模型构建 场景模型组织 空间跟踪 声音定位 视 觉舔踪和筏点感应等关键技术 逸些技术使得真实感虚拟越界的生成 虚拟环 境对用户操作的裣测和操作数精静获取成为可能 1 基本模型构建技术 基本模型的构建是应用计算机技术生成虚拟世界的基础 它将真盛世界的对 象物体在稻应的三维虚拟 眭界中重构 并根据系统需求保存部分物理属性 模 型构建酱兔要建立对象物体的几何模疆 确寇萁空间位鬣和几何元素的属往 镶辩 通过c a d c a m 或二维图纸构建产品或建筑的三维几何模型 通过g i s 数据稻卫星 遥感线靛掐照片构造大型虚瓠战场 为了增强虚拟环境的真实感 物理特性和行为规则建模要表现出对象物体豹 质爨 动量 材料等物理特性 并在虚拟环境中遵循一定的运幼 移动力学规德 当死俺模叠潲豹理模型很难准确斑刻西岛真实氆界中存在的某些特别对象或 现象时 可根据吴体静需要采爝一些特别的模型构建方法 例如 可以对气象 数攒迸行建模生成寝攒环境的气象情况 蕊天 晴天 雨 雾 2 场景模裂组织技术 随骜c a d c a m 技术的发展 纂本建横技术包括实体建模 曲筒建模和离散 建模等建模技术己蒸本发袋成熬 虚稼环境中往稼包括成千上万的萎本模型 2 寝舔瑷实技术抟算法莲瑞炭旦大学数学轿究所博士研究生潮进 2 0 0 1 年1 2 胃 要处理极大的数据量 整个环境的数据量要达到数百万 数千万甚至更多的三 角片 因此对虚拟环境中大量模型如何进行有效组织以提高实时处理效率成为 虚拟现实中的关键技术之 3 空闻跟踪技术 虚拟环境的空间跟踪主要是通过头盔鼹示器 数据手套 数据衣等交互设备 上的空间传感器 确定用户的头 手 躯体或其他操作物在三维虚拟环境中的 位鬻和方向 4 声音跟踪技术 利用不同声源的声音到达菜一特定地点的时间差 相位差 声压差等进行虚 拟环境的声音跟踪是实物虚化的重要组成部分 5 援觉鼹踪与飘点感应接零 实物虚化的视觉跟踪技术使用从视频掇像机到x y 平面阵列 周围光或者 跟踪光在图像投影平面不同时刻和不同位置上的投影 计算被跟踪对象的位置 和方向 1 2 2 虚物实化 确保用户在虚拟环境中获取视觉 听觉 力觉和触觉等感官认知的荧键技术 是鹰物实化的主要研究内容 1 视赞感知 虚拟环境中大部分具有 定形状的物体或现象 可以通过多种途径使用户产 生真实感很强的视觉感知 视频显示器 大屏幕投影 多方位电子墙 立体眼 镜 头淼显示器 h m d 等是虚拟现实系统中常见的蠹示设备 除了硬佟设备之秘 褪燮感翔黪器熬是一个重要方嚣是实黪哥交互翡动态滔 像 为了达到实对的基豹 歪少要豫涯熙形豹刷凝率不 豪于 5 峻 秒 露纛羧蒌 境中存楚箦大量豹物体 热倪蠢效合理熬是现这些伤 奉姆潞提裹整体处理效率 产生提大的影响 特别是对一墩复杂物体戎不超熬远近距舞下 从苓翅豹角度 进行观察时 采用 定的简化手段以提离显示效率成为必錾 蘧这正是实酵三 维图形生成技术灼核心所在 虚拟蕊赛技术的箨法蒸穑复曼大学教学讲究群簿士研究生刘进 2 0 0 1 年1 2 弼 2 听觉感知 错觉是仅次予视觉的感稚途径 瘟撂环蠛酾声音效暴 可疆弥补褫觉效柒酶 4 i 筵 增强环境逼真凄 3 力览和触觉感知 能否让参与者产袋 沉浸 惑曲关疆因素之 是角户能否在操级虚掇物体的 澎露 感受笺虚拟物体鹃反作魔力 扶褥产生触觉藕力觉感知 例如 当你焉 手扳动虚按驾驶系统的汽车档往杼辩 像静手畿感觉蓟档位秆豹震动私松紧 这是人嬲嚣稳豹难题之一 3 高性能计算处理技术 纛叛瑗实是以诗算梳技术为核 t l 的现代离新季萼技 高性能的计算处理技术蔻 壹接影稠系统性能静关键所在 场景模型组织技术和实时三维图形生成技术是虚拟现实投术蹋个除段实物虚 化和虚物实化中的核心问题 几何模型处理的关键技术 而逸两种技术又是 密切相关 成为前因后果的 本文首先耍讨论的就是这两种技术 随后将讨论 虚拟环境中物体实时交互变化的问题 这又可以分为两个方面 一是虚拟环境 中物体运动引起桐互位置变化 需要对由此引起的物体相互碰撞进行实时检测 二是虚拟环境中交互操作g f 起的物体变仡 需要对物俸进行实时修改 图1 1 描 述了虚拟现实的全过耧 4 璇揪现实拄术的算法基础复鱼大学数举研究新博 研塞圭 墅誊 一一 塑 兰 星 图1 虚拟现实的全过程 1 3 场景模型组织和实时三维图形生成 瘸虚拟觋蜜按零构造鲍蕊拟环境的蕊本内容最酊橇化的场景 在实琢寝掰 中 个虚拟弱最往往最高度熨杂的 裥如 粥c a d 软件构遣的模型往往包含 了数以十万诗熊凡秘元素c 角形等 用有敝元方法逃衙铸萁的时镞 往棱将籁 单物体分割成数以予计的几留元素 丽描述现实避界串室外场景麴廛撤模型掰 瓣的几何元黎燹是蓬大的 虚拟环境的真实性和复杂蠼与突孽重交至之阈鲍霭求 形成了一对矛嚣 能否与系统避行实时交瓦主要受虚拟现实较侮的影嘲 刍虚 拟环境嶷化嚣重 款件必须在 秒钟内对虚拟环境避行至少十次班上静修改 从 这里可以看到虚拟瑷实按术的核心其实楚窦实鹅黧形豹实时绘制技术 鬈与传 统囊实感图形绘制算法的区g 在予鬟求在一定时闽内完成对场景瓣绘素 对任意几何形状的寅时显示主瑟是靠图形硬件来宛成的 目前瀛雩亍鲍圈形加 艨献现实技术鹳雾法基础 复旦走学数学研窭簸麟 坦 墼 鳖 一 塑 垩 兰望 速设餐通常支持三维塞啕中静点 直线 多边形豹绘制 在趱拱环境中 三维 几何体的最示是最基本的阏题 蕊在磨蒜上所显示的每 个齑蕊是在泠定的视 点和视线方向巳 兰维几何体在藿赢于视线方淘鲍二维平面上的投影 根据我 3 从现实世界肆1 获取的经验 八眼能看到的线摄像橇能观察到的役仅鼹空阍中 舶巢一个区域 在计算机圈形学中 人们用 个豳棱锻柬描述这个蓬域 图2 褪最臻 我们祢懑2 所示的西援镰为褫景锥 v i e w f r u s t u m 其中d 燕视点 怒 视缝方向 p i 为近乎蕊 p 2 为远平蕊 只有位于视萦锉熄近平露秽远乎蕊之间 的多边澎方是胃觅的 在羼幕上显恭三维景物敬过程是这礴的 p e b j 9 9 敷嚣物体至q 场景中 物体局部 坐标系变换导场爨坐标蒙 l 上 指定视点位鬻秘视线方向 进 行透视交换 税景锻裁减 转 换到裰躅坐椿系 i l 0 指定屏幕的剪关参数 程羼幕 坐标燕中避行绘制 裰鬃光照 横型避纷建蹙度诗算 绽壤映 射 光栅他 隐瓣两酒除 可觅 性判断 图3 嚣幕上显示兰维最物的过程 尽管圈形硬 串酶牲能在不断避辊商 复杂几俺模型豹实辩显示仍然是一馋寝 6 虚拟现实接拳转算法基砒复虽丈学攀避煮斟主婴塞生塑垡 三塑 兰鎏壁 有挑战性的工作 通常图形碗件所提供的绘制纯粹的多边形的速度往往不能满 足实时交互的疆求 而通过对透视投影的特征和复杂模型的分析 人 可以构 造能擒供院原始的图形硬件更高性能的算法 这些算法往往需要对模型进行特 殊的维织 可能是事先的由模型提供者完成的组织成算法良身对模型的组织 常 用的方法有层次式包闰盒 h i e r a r c h i c a lb o u n d i n gv o l u m e s s v n b 9 9 k m g l 9 6 g r k v 1 9 3 z m h h 9 7 z h a s 9 8 e t c 静态的可觅信 g s t a t i cv i s i b i l i t y 对每 个 褫点事先计算好豹可能可冕的多边澎靛集合 c f h z 9 8 d d t p 0 0 s d d s 0 0 t e s e 9 1 k o c c 0 0 e t c 以及层次细节篱纯技术 l e v e lo f d e t a i ll o d fl u e b 9 7 h e g a 9 7 g e p a 0 0 e t c 一个有效静算法应该糍够清楚地表达横鍪能特 证 在 不破坏虚拟环境懿完熬牲瓣蘸挺下 传送尽鬓少鼢多边形数据绘图形硬件 保 证强形硬终8 够在给定弱对阂内完成一帧蕊西鑫冬绘制 由予磷前堡篓窭塞蔓篓罗器的窭塑叁掣夔壅不辨乎基予景物几何模型的绘制 援术鞫基于隅像的绘制技术 s c h a 9 8 本文浆讨论如帮鸯p c 上运用基于景物 几何模型的绘制按术来构筑实时绘铡图澎的方法 我们将从场景缀织 可见性 一 判断 复杂物体袭这以及动态交曩譬凡方面展开讨论 文章的第一郝分偿 二章 讨论了复杂场景的组织 绘出了可见往蛳断的算法 f 瓿秘囊的讨论中 我们已经知道由于图形加速设备豹糍力的疆制 要实对绘制 复杂场景 必须在保持显示结果究整性瓣前提下 熙尽曩短的时间确宠必颓向 图形加速设备发送的几何元素的集合 如何合理蛾缍织场最是实现这一疑标的 主要途径 在遮一窘中我们旨毙讨论了建筑杨内部场景的组织以及一个实对计 算哥能可见物体的方法 接广了f t e s e 9 t 的方法 取淡了 t e s e 9 1 方法串舞求 分割空闽的平砸 平行予嫩标轴 的限制 然后给出了一个基于物体有囱聚定 盒的视最锥选取方法 最戚我们讨论了一般场景的组织 提出了餍一个屡次商 商 受定盒糖柬分割场景的算法 改避了馋统的层次驻定盒方法 绘出了 秘不 嚣z 缓持器查询并已l 在瞽通p c 槐上实现的实翳计算可见多边形熟算法 f 文章的第 部分f 第三章 游谚了复杂物馋的袭示方法 f 基予场景屡次上的讨 论可以解决可见性间题 但蹙由于场景中的物体有可能是板菇复杂的 裔韵物 体能包含了数以万计甚至蔓多的几何元繁 如祭对可冤性进行处理 簧实时显 示这些物体仍然是十分豳难的 豳北如何表示这些物体 也是一个非常黧要的 闯题 本章的第一节讨论了攘杂物体的简化方法 讨论了基于屡次缨带麓化技 术的一些算法 第二节提啦了 类平醯 静概念 将 葳向藤剃除 控拳维广 艘 反向送域剔除 为解决一般多西体表蔼静反自匿域快速翔颧鞠遥 我们运 用g a u s s 妖照的方法 结合 类平疆 的概念 给出了一个裘承物体的屡次式结 构 快速判断多蔼体巾的反肉区域 文章第一部分秘第二部分的簿法叠经运塌到了一个实际壤鹭 上海科技馆主 体建筑虚拟现实系统 中 该项弱运行在普邋p c 上 能够避 亍实时交互测煦和 查询 予2 0 0 1 零7 嚣通过了上海市科委鉴定 鉴定意见认为该项目 在蜚通p c 祝上 实现建筑虚拟蕊实方盈已达到篱瓣先进农平 h u k j o i 并且 褥该项 嚣作为箕予项疆之一的上海科技镩磺嚣跫通过了2 0 0 1 年度上海市科学技术进步 奖一等奖的初评f f s k m 0 u 寝撼现实技术靛算法基础复旦犬学数学研究辑媾士氍筵刘遵 一一兰塑l 笙1 2 星 文章的第三部分 第西章 给出了在虚拟场景中与物体进行动怨交互的几个算 法 i 虚拟场景中不仅仅有静态的物体 可能还有动态的物体 例如运动物体 形状在不断变化的物体等等 本章首先讨论t y 维空闻中运动物体的碰撞闻题 通过投影三维物体蓟蹩标平磷上的手段 将运动物体的碰撼问越转变成了平面 上多边形井轮廓求并与求交的问膳 提出了 个复杂性为0 m 十 十移l o g m n 的算法 其中 1 n 分稍为两个物体投影之后掰褥外轮廓多边形韵颈煮个数 k 为 交点个数 该章的第二节稻第三苇讨论了场景中实潜修改物体抟闻题 苞据带 潺多边形区域豹快速三危鞠分和三维实体模型的实辩修潋算法 第三节讨沦的 多这形三角副分怒一个十分经典黪阏题 许多应雳酆需要用三麓割分进行予簧处 理 在虚季 场景中显示豹物体都楚三恁他之詹懿结繁 蕊三焦割分瓣效率燕接 影响了与虚拟场景进行交互的效率 因此提供一个惑效豹易于实现的冀法楚十 分有意义蚋 当然篾肇的算法可能需要大量购对阅 男 方嚣有些理论上慰闻 复杂技低豹算法所采用麴数据结构以及计算过程极其复杂 难于实现 铡如 c h a z e l l e 等提如的用线性时间定成三角化的算法 c h a z 9 l 本节提出了一个裹 效的易于实现的带洞多边彤区域三角剖分的毅算法 该算法分成了两个过程 1 将带溺静多边形区域分害l 戏若子个簿革多边形 2 分别对麓单多边形进行三魏捌分 分割带漏多边形区域瞬时问复杂性为o n 掰 1 0 0 0 9 m l 势 其中n 是 所有榭成该多边形区域静预点的慧数 时十l 袭示多边形的个数 对每一个简单 多迭影来说 英露趣复杂褴为o k 1 其中露建馨颈点戆个数 女 泰透明 其中r 是一个耪定的闽值 0 t o i 遥表示在捡鸯覆 盖关系的时候 可以不考虑遮挡物中的小孔 其q p 阮力表示了 x y 处像素点的颜色 o 黑色 l 白色 对于深度测试 z h a n g 等给出了两种方法 较麓单韵一种是计冀遮挡物集会 躺最大z 坐标 诧为o 当最仅当一个物体豹酸像被宪金覆羲著姓所有顶点的z 擞标大予矗时 物体是不哥见的 第二秘方法是对第一种方法的改进 用深度 估计缓冲区记蒙每 个遮挡物的最大z 坐标 实际上是一个z b u t i e r 每一个点记 袋的是绘割遮挡物的包围鑫慝穆到的最大z 坐标 建立了这个结构之层 可以 通过摸拟绘判p 的包围鑫皋测试是否落农遮挡物之蕨 对于初始豹遮挡锈的集合 z h a n g 等蛉舞法在于处理阶段剔除了被认必较小 的物体 然鹰为剩余的物体集建立蔗次氡圈鑫缕构 褒执行阶段 用视最锥选 取昀方法获褥可缝可见的物体的集会 周遂 礁的方法虫适要n 远选取遮撼物 意 到这到一个绘定豹闽德 这棒就可以建立h o m 褥和深菠售诗缓渖嚣 最后绘割 物体 z h a n g 等的箕法改进了层次式z b u f f e r 的器要频繁访问z b u f f e r 的不足 罴 一个蔓加高效的算法 但是仍然存在蔫如下的缺点 h o m 和深度假计缓冲区郝 采用眈实际图像更低的分辨率 这种方式必然导致最终图像的失真 4 虚歙现实技术粒算法基础复旦大学数学研究所簿士研究生刘进 1 3 保守的全局可觅性算法 镍守靛全弱可见牲算凌是一类带预处理的隐藏物消除算法 莛疑标是罔一个 保守的算法 为每一个绘定的视点和场景建立可能可见的多边形集合 p o t e n t i a l v i s i b i l i t ys e t p v s 并存馕在数据结构中 这样 每次剧灏视图时 只要从p v s 中获取需要的多边形进行馒示就可以了 能够大幅度地提高刷掰频率 县体做 法是这样的 将场景划分成一系列的网格 然后对每 网格 用3 6 0 的视角计 算位于网格中的视点的所有可能可见的多边形 在计算p v s 的过程中 往 圭采 用 些大的物体作为遮挡物 c o t e 9 7 1 或者将一些小物体通过一定的规则组合 成一些虚拟的遮挡物 k o c c 0 0 虽然 采用隐藏物消除方式可以有效地去除 不可见多边形 但是每一个网格的p v s 的尺度与网格的大小有关 网格越大 p v s 尺度越大 这将给后面的实时绘制带来沉重的负担 而网格越小 p v s 尺度越 小 实时绘制效率越高 但是小的网格尺度带来的是巨大的网格和p v s 的数量 如 果阏格的尺寸缩小到原来的 则数量将增加到原来的k 3 倍 而且预处理的时 定 阊也会不凝增船 c f h z 9 8 d d t p 0 0 k o c c 0 0 s o d s 0 0 z m h h 9 7 z h a s 9 8 e t c l 的算法都照在麓档耀形工传菇上实现的 不太适合普遂p c 上灼应用 2 复杂场景的组织及场景的可见性判断方法 2 1 建筑物内部场景的组织及可见性判断 对建筑物睁鄯场景 t e l l e r 等 f 程s 毫9 1 霸平行于坐标辎鹤平覆 壤谣 对场景 律二叉割分 萍遗过网格每网格闻的掰觅淫采构造潜在黪哥觅蟊表 该箨浚采 用溺捂蠲霹冤往寒信诗潜在鹃哥冤嚣裳 姨露避免了辖确计算潜在霹冕褥表蠢 起的巨大戆幸 算耗费 徨是该冀法瓣缺点罴它只适合予其朝舞与坐标辘方彝 一致懿建筑凌模型 缺乏一般键 受 t e s e 9 1 算法的启发 我们发现不管建筑物的朝向怎样 分割建筑物的 墙颐的形状如何 我们都可以按照建筑物物理结构来划分场景 结合视景锥 物体限定盒等实时她计算当前视点下可能可见的物体的列表 梗摧按照建筑物兹建结挎划分绣景辩 逶磐我靛将一个单独熬房瓣定义成 个场景 露在房阕蠹都 掇撂菸建筑缝构又霹以褥到一些视线可以穿透熬边舆 称其梵视线遴道 穿过每一视线通道 可以看到与此通道摆关的其它房闯 不必一般性 我们假定与每一视线通邀相荧的房阏有且仅有两个 投摆这些约 艟扭班蜜技术躺箕法基础复星大学数学研究赝博士研究蓬型垄 定我们可以榆选出这样的场景维织续橡 槐线通遗 棍线通道的凡僻数据 相关场景一 用场景列表申的下标来表示 相关场景二 用场景列表率砖下标柬表示 场景 场荣中鹳所有视线通道 用褫线遗道列表中的下赫采表示 场景中的其他数据 建筑物 场景列表 视线通道列表 如累视点位于慕一个场景内 称其为当前场景 根据这个场荣的视线逶道 我们可以譬孽到直接相关场景 这些场景都是可能可觅的 而与这爨可能可觅的 场景棚关的其他场景也是可能可觅的 如诧不断地递稽 可以得到所有可能可 见的其他场景 如图6 图中 a b c d e 蹩建筑物中的场景 胛是场景x 冬 y 之间的褫线通道 并 y 芒 a b c d e 骰设视点位于场景点a 内 则由a 感 发 得到的可能看的场景为 b c d 琶 图6 建筑豹内部场景结稳 一 赢拟瑶鬟箍术辫舞法辇稿复挂 丈掌数学研究所博 研究生刘避 2 0 0 1 年1 2 月 我们知道 在慕一个场景中观察物 本时 所能见到的内蜜与褫点位嚣和褫线 方南密切相芙 始图7 凿7 祝景锥与视线通道静美系 设p 楚视点 射线p p i p p 2 楚横景镶在场景所在平瑟上豹投影 射线p p l p p 2 是通过视线通道a b 之后的税景锥的投影 射线p p l p p 2 是逶过视线逯遵b c 之螽的视景锻的授影 从醋中我们可以知道 从视点p 出发 经过场最边界的 遮挡 最终可觅静场景是a b c 蓬于上述讨论 我们可以褥到如下的舅法 表 2 1 1 算法一 基于韵空间的方法 搜寻可能可见的场景列表 害前场景下标 橇萦舔 可能可见的场景的下标列 输入参数 毒前场景下标 输入参数 视景镣 骑出参数 髓有可能可见的场景的下标列表 b e g i n f o r 当前场荣的所有视线通道 b e g i n i f 视线通道与规景镑有交 b e g i n 得到与视线通道相关的场景的下静s c e n e i d x i i f s c e n e i d x i 没有出珑在 所有可能可见下标列表 幸 b e g i n 根据视线通道修改视景雏 视线通道 橇景锥 新橇景锥 i f 麓穗素锥非空 艘拟现实技术的算法基础复臣夫学数学磺究掰博士骈宄生刘进 2 0 0 1 罐1 2 月 将s c e n e l d x i 加入至 所有可能可觅下标列表 中 e n d e n d e n d f o r 鼹有新加入媾场詈下标 搜寻可能可见的场景列表 s c e n d i d x i i 新视崇锥i i 可能可觅的场景下标 列表1 e n d 根据视线通遭修改税荣锥 税线遗遘 税景锥 新的视景锥 输入参数 视线通道 输入参数 视景舔 输出参数 斯畿视裴锥 b e g i n 褫残通道姆每一务边的顶点与税点的连线得到一个锥t m p f r u s t u m 截的视景饿 t m p f r u s t u m 与梳景雏的交 e n d 21 2 尊法二 基予褥筷线通道的选器映射掰像空闻的方法 设e 1 是场景a 中的 个视线通道 通过视图变换 我们将它映射到像空间 中 褥到 个多边形区域p e i 场景b 楚与视线通道e 1 相关的另 场景 e 2 是b 中的一个视线通道 c 是与视线通道e 2 相关的勇一场景 如聚将e 2 映射 到像空阀秸 褥到的多边形区域p e 2 与p e l 有交 则场景c 是研觅的 否黄日场 景c 不可鬼 其体葬法知下 援寻可能可觅的场景列表2 当前场景 橇景锥 像交间中的一个有效区域 所毒可能可见的场景下标列表 输入参数 当前场景 输入参数 祝荣锥 输入参数 像空间中的一个有效嚣城 初始值为整个像空间 输出参数 所霹可能可见的场景下标列表 b e g i n f o r 誊静场景的视线逶莲个数 b e g i n 投影橇残通道置僚空闷 祝景锥 视线通道 投影区域p r i f p r 非空 b e g i n 区域求交 像空问的有效联域 投影区域p r 有效区域a p r i f a p r 非宜 b e g i n 礁搬现譬技术的算法基鼬复里太学数擘研究所博士研究生妻 j 进 2 0 0 t 年1 2 月 e n d e n d e n d 获取与视线通道相美的场景s c e n e i d x i 将s c e n e i d x i 加入到 可能可见的谤景下标列表 中 f r 奎前场景的有效区域肆空的视线通道 搜寻可携可见的场繁列表2 s c e n e l d x 税景舔 a p r 可能可见酶场景下标 列表 e n d 2 2 基予有向限定盒的可见性判断 摇袋锥 v i e w f h l s m m 选取技术秘反向嚣国a c k f 沁e 剿除技术可以鼠场最中 获取所有可见的多边形 但是由予这两静技术处理敬对象都垦多边形 嚣北对 有大量多选形构成的物体来说效枣并不是镄麓 基于簸定盒抟可见性刿断是一 种保守却菇效的判龋方法 箕想法来自于 觉线跟踪葵法的层次琶罱盒技术 它能够潦完全位于可视区域之外的物体从可见集中去除 扶藩提高显示效率 基于限定寂的可见性方法厢一个形状较简单髂限定鑫 如球 长方体等 褥复 杂物 本色嘲起来 在进行视景锻选取之前 蓠必将鞭定盒写视豢锥求交 如栗 育交 则认为在隈定盒的屡次上哥见 讴剥不可见 由于隈定盒与视景锻的求 交非常简单 通过少爨的计算就可以翔断构成物俸的丈量的多边形的可见性 丽限定盘的形状非常祷尊 可能慰物体包裹不紧 酸定盒与梗景锥商交并不能 说鹊物体可见 圈北这是一个僳守的算法 爝这种葵法判断得到可见物体只熊 认为是可能珂见的 此处 我们分别对球体和长方体的鞭定盒进 亍讨论 2 2 j 计算物体的限定囊 设豫 i 1 2 n 鼹攒述物体的多边形鲍顶点 试蹭寻拨 个落禽此物体鼢 长方体 此长方体的体积达到极小 r 薯 r x 将僻 分别投影到坐标轴上r 得到最大畿小值 i f 戳这两点为顶 l o 燕 边平行予坐标轴的长方形龟含她物体 通过搬标系的旋转 我们w 戳求得 体积最小的隧定盒 设o x y z 楚初始堂括系 o x y z 蔗旋转之厝的坐标系 其中 9 查鳖墨壅丝垄篓墨鏊堇鳖壅墨奎鲎篓堂矍茎星鎏主墼篓兰型鲨 塑 竺堡墨 绕o x y z 坐拣系的z 轴旋转角度为癌 绕x 轴的旋转角度为筘 则从0 船2 殛摭 系变换剑丽中的变换矩睁为 为 r 缸 功 fc o s 饯 一s i n a c o s f l ls i n 搿s i n 6 f 蕾 设ly 是霉在删坐标系中的坐标 引 8 m 浅 c o s g c o s 届 一c o s 口 s i n 嚣i 鞠 f 葛1 则脯碱坐探种的坐栋引 件如 捌 i 莓jh j f 工 妇 芦 1 l k 翻 气2 i 慧尉 k l i o 驯 i l i q p jk 缸 芦 j 矿 p 6 筘 一x 娜x y 缸 所一y 缸 夕鞭z 妊 一k q 夕 因此我们的姻题转变成求m 遮y q 国 考虑到坐标系的对称性 旋转热瘦的 缸 声 f o g 筻手 岁 三 l j 算法2 2 1 计算物体限定盒 计算限定盒f 顶点列表 限定盒 输入参数 磺点列表 输出参数 限定鑫 b e g i n 穗 o 要 屈 o 晟 兰 虚般蜣实按术翁算法基础 复盈戈学数学科究所博士错究生划进 搿 垒 蝴 掣 n 与需要达到的糖度有关 p 一2 十 初始化最小体袒值 当步长太予给定的婧度时 酪c z i n 聍陋 d 1 x 泌 岛 莲域内按照步长陋 题 划分的所有网格点 b e g i n 旋转坐标系到杠 刃 获驭顷点在斯坐姆系申的坐梅 计莽投影到坐标轴之后得到的长方体奇 体积v 如粜圪 0 2 璧型錾壅羹查堕墨堡警塑 篓墨查兰矍堂塑壅塑璧主堡垫兰燮 0 穗景锥与长方体有公共部分 返回t r u e 否则返回f a l s e e n d 算法2 2 2 球侮与秘景锥求交 如图2 3 设v 是视点 是规线方向 薯芦为近乎嚣长方形上与边界平行豹 题个方魏自量 口为视角 f 分剐为裰点到近乎匿帮透乎瑟之阐静距离a o 分剐是被稔查球的球心在沁 与沁 y 平面上的投影 则该球可见韵充分条 譬是 球与祝羡锥在沁瓤x 所张成平面上的投影以及在扣 z 所张藏的平蕊上的 投影宙公共部分 鲻2 3 所示菠楚有 无公共酃势静瞒器位置 以下我们将给出 判断球体与褫寮锥育无公共蘸分的算法 g 书 群 图8 球体与税最镶球交 球俸与祝景锥求梵 球体 祝蚤锥 输入参教 球俸 徐入参数 税景锥 返回t r u e 有交 f a l s e 走交 b e g i n 带 汹 咖 节 如 p 弦 如器 l l 译l i 湖一叫 蚓l 蛐目 r c o s 群 f 睁q 2 l 阿 一帮 l l 带7 拓m 稿十r c o s c t 都成立 则蜷体与祝景锥宥公簧部分 远筒t r u e 否蹦遂饼f a l s e 从以上的讨论中 运建艇定鑫静方法 我们珂以月线性时阐判断场景中哪黪 理拟现实技术豹算法基础复里大学数学研究所蹲士磋究生刘避 2 0 01 年i 2 月 物体可见 2 3 场景组织 本章的2 1 节中讨论了一种建筑物内部场景的组织方法 虽然这种方法有其 简单高效的特点 但它有一个很大的局限性就感只邋合建筑物内部场蒜 不能 应用到一般的场景中去 例如对复杂的机械装置或塞外的场景就不适用 为解 决这个问题 我们为场景建立一裸层次限定盒树 在真正绘制场景之前 我们 基于这稞限定盒树进行可见性判断 然后再绘制可能可觅的物体的集合 豳2 4 一个衣效灼场景级织结构能够更快地想到与视景锥有交物体 能够更快地消 除隐藏物 黼9 场景的罄次结构 虚拟现实技术的算法基础 复旦大学数学研究所博士研究生刘进 2 0 0 1 年1 2 月 第三章复杂物体的表示方法 可见性算法可以将场景中大量的不可见物体剔除并可显著提高帧刷新频率 但是实际上 对于一个复杂的场景 在给定的视点处往往大大超出了能在指定 的时间内渲染完毕的三角形的数量 而且这个数量是没有上限的 例如 当我 们漫游在一个摆放了各种各样的物品的百货商场中 或者观察或装配一个汽车 或飞机的完整的引擎 显然单靠可见性判断是不能充分保证所需的帧刷新频率 的 因此寻找合适的物体表示方法是一个很重要的问题 本章中 我们将讨论 适当简化物体表面细节的层次细节简化技术 以及用来加速反向面剔除的物体 层次结构表示 简化方法通常在不牺牲最终绘制图像质量的前提下 简化需要绘制对象的表 面细节来提高显示速度 有的简化算法用图像来替换场景中的某些部分 m a c i e l a n d s h i r l e y9 5 s c h a u f l e ra n ds t u e r z l i n g e r9 6 a l i a g aa n dl a s t r a9 9 另外的算法运 用多面体的简化技术 用含有少量多边形的多面体来替换复杂的物体 本文将 首先讨论多面体的简化技术 多面体简化的目标是生成物体的多重精度 m u l t i r e s o l u t i o n 的表示 c l a r k7 6 h e c k b e r ta n dg a r l a n d9 4 1 基于视点和物体之间的距离 绘制某一种精度模型 当一个物体距离视点较远时并且最终图像只包含了屏幕上的少数几个像素点 时 一个较低精度的模型就已经足够了 而当视点与物体相互接近时 就需要 逐步采用较高精度的模型 多边形简化的问题就在于如何在保持三维物体的外 形的情况下 减少多边形的数量 以及在视点和物体相互接近时 采用哪种精 度的模型并且要求在两种不同精度的模型之间切换时不会引起视觉跳跃 图3 1 示意性地描述了不同细节的模型与距离之间的关系 e r i k 0 0 2 4 虚拟现实技术的算法基础复旦大学数学研究所博士研究生刘进 2 0 0 年1 2 月 图 o 按躐离选择小兔子的l o d 模罄 扶左蓟右三角彩的数鬟分粥为 1 7 3 6 1 8 6 8 0 4 3 4 0 2 1 6 9 1 0 8 0 小兔子的原始模翟酌三角形数量为6 9 4 5 1 3 1 如何建立l 0 0 3 1 1 几何简化 几何简化是通过考察物体表面多面体阀格的几何特性 来简化物体的方法 而元素删除法是最常用的的几何简化方法 基本思路是从原始模型开始 递归 地删除模楚中的点 边 面 直翻模型不能继续简化或糟达到用户指定的误差 晃限 常用的方法有顶点蒯除 v e r t e xr e m o v a l 边压缩 e d g ec o l l a p s e 顶点台 并 v e r t e xm e r g e 顶点删除法每次廊除一个顶点以及与顶点相关的所有的面 然后对产生的空洞重新进行三角剖分 s c z l 9 2 c v m t 9 6 边压缩法将 条边 的两个顶点合并成 一令顶点 确走薪插入顶点的位置 觚丽达到减少多边彤以 及谦持表耐拓挣结构的舀的 h o p p 9 6 l i t u 9 8 顶点合并法将两个顶点合并成 一个 这类方法与透压缩法的区剩在予允许两个璎点不在褥一条边上 圈1 1 各种元素翮除方法 倒顶点嗣除御边压缩 顶点合并 3 1 1 1 顶点删除法 用顶点删除对证意曲面黼格进行简化的方法最草是由s c h r 6 e d e r 等 s c z l 9 2 1 1 入稳出的 基本过程蹙按照一定的准掰每次删除