（计算机应用技术专业论文）力觉绘制算法的一些研究.pdf

摘要 摘要 袭褪熬、辑懿一样，力觉邀麓入类感翔癸赛终重要搂态之一。在奏实餐赛 中，人类通过力觉系统感知物体的形状、温度、硬度等。在虚拟世界里，人们 使溺各种枫电设备来感籍计算视产生的寝报物体，这些辊电设备被称为力觉设 备。人们使用力觉设备感知虚拟物体的过程被称为力觉绘制。 在过去的几十年中，人们已经研究开发了大量有效的力觉绘制算法。然而， 要取得更稳定、熨准确蛉反馈力，使用户隧够更囊实遗感知虚拟物体，述嚣要 进一步研究开发熨有效的力觉绘制算法。力觉绘制算法的研究开发充满着挑战， 这转挑战体现在三今方瑟：燕一，力觉绘剿算法对效率要求程当麓，运鬻嚣要 达到1 k h z 以上；第二，力觉绘制算法需要基于力觉设备交互的特点定制，因 为力觉绘麓与力觉设备密镯穗关；第三，力觉绘裁算法往往对强称模壅的复杂 度比较敏感，其性能依赖于目标模型的复杂度。 有一蹙交互怒面接触交互。商很多力觉设备提供了丽接触交互接口，如 c y b e r g r a s p 。针对甄接触交互的力觉设备，我们掇出了一张新的蒸于面接触的 力觉绘制算法。它采用共点的线段簇作为力觉代理，而不像已有的力觉绘制算 法将力觉代理表示残一个点或三缵网揍。共点线毅簇逶造采样接触囊掘逡，较 好体现了面接触交互的特点。算法还对目标物体进行均匀空间剖分，以加快力 赞绘裁豹过程，浇是力爨绘裁舞法效率熬需求。算法篾符合力受设备交互懿特 点又有足够高的效率，能够提供稳定且真实的反馈力。 高度复杂模羹的实对力觉绘潮是力觉绘制领域的难题和热点。对模羹复杂 威敏感的算法都不能很好地实时绘制高度复杂模型。为了克服这个问题，我们 掇出一种新的基于力觉包围盒的实时力觉绘制算法。力觉包围盒怒目标物体的 一j 孛表示，专用予力觉绘铡。它记录羞离散采样的炎线与嚣标物体媳相交傣患。 为目标物体构造好力觉包围盒之后，碰撞检测算法只需要执行一次有向线段与 惫嚣盒求交运算帮五次双绫牲捶馕运算裁霹鞋袭滋磋撞繁惑。检测过程避免了 大量不必臻的求交运算，从而变得相当快速。碰撼检测过程得到碰撞信息可直 跤甭予反馈力计算。绘翻过程中，算法与原来静麓度复杂摸鍪不簌接相关，跌 摘要 而不对原始模型的复杂度敏感。实验证明，我们的算法快速有效。 关键词：力觉绘制，碰撞检测，力觉包围盒，高度复杂模型，面接触 i i 垒! 皇塑一 p b s t r a c t t h es e n s eo ff o r c ei sav e r yi m p o r t a n ts e n s o r ym o d a lo fh u m a nb e i n g ，j u s tl i k e v i s i o na n da u d i t i o n i nr e a lw o r l d ，m a n yp r o p e r t i e so fp h y s i c a lo b j e c t sa r ee x p l o r e d b yf o r c ec u e s ，s u c ha st h es h a p ei n f o m m t i o n ，t h et e m p e r a t u r e ，a n dt h es t i f f n e s sa n d s oo n w h i l e ，i nv i r t u a lw o r l d ，t h eg e o m e t r ya n do t h e rp r o p e r t i e s o f c o m p u t e r - g e n e r a t e dv i r t u a lo b j e c t sa r eh a p t i c a l l yp e r c e i v e dt h r o u g ha l l k i n d so f e l e c t r o - m e c h a n i c a ld e v i c e sw h i c ha r ec a l l e dh a p t i cd e v i c e s t h ep r o c e s so f e x p l o r i n g v i r t u a lo b j e c t sb yh a p t i cd e v i c e si sc a l l e dh a p t i cr e n d e r i n g d u r i n gt h ep a s ts e v e r a ld e c a d e s ，m a n ye f f e c t i v eh a p t i cr e n d e r i n ga l g o r i t h m s h a v eb e e nd e v e l o p e d h o w e v e r , i no r d e rt om a k eu s e r si n t e r a c tw i t hv i r t u a lo b j e c t s m o r er e a l i s t i c a l l y , m o r ee f f e c t i v eh a p t i cr e n d e r i n ga l g o r i t h m ss h o u l db ed e s i g n e dt o a c h i e v em o r es t a b l ea n dr e a l i s t i cf e e d b a c kf o r c e d e v e l o p i n gs u c ha l g o r i t h m si sf u l l o fc h a l l e n g e s t h ec h a l l e n g e sl i ei nt h r e ea s p e c t s f i r s t l y , t h ee f f i c i e n c yo fh a p t i c r e n d e r i n ga l g o r i t h m si sr e q u i r e dt ob er a t h e rh i g h , n o r m a l l yh i g h e rt h a n 1k t t z s e c o n d l y ，h a p t i cr e n d e r i n ga l g o r i t h m ss h o u l db ed e s i g n e dr e g a r d i n gt h es p e c i f i c p h y s i c a l f e a t u r e so fa h a p t i cd e v i c e ，f o rh a p t i cr e n d e r i n g i sah i g h l y d e v i c e - d e p e n d e n tp r o c e s s l a s t l y , t h eo p t i m a lr t m n i n gt i m e o fh a p t i cr e n d e r i n g a l g o r i t h m si n t r i n s i c a l l yd e p e n d so nt h ec o m p l e x i t yo f i n p u tm o d e l s t h e r ei sak i n do fi n t e r a c t i o nn a m e da r e a c o n t a c ti n t e r a c t i o na n dm a n yh a p t i c d e v i c e sp r o v i d ea r e a - c o n t a c ti n t e r a c t i o ni n t e r f a c e ，w h i c hi sc a l l e da r e a c o n t a c th a p t i c d e v i c e ss u c ha sc y b e r g r a s p w ep r o p o s e dan e wa r e a - b a s e dh a p t i cr e n d e r i n g a l g o r i t h mf o ra r e a - c o n t a c th a p t i cd e v i c e s u n l i k ep r e v i o u sw o r k ，t h ea l g o r i t h m e m p l o y sc l u s t e r so fl i n es e g m e n t sw i t hc o m a - l i o no r i g i n a lp o i n t sa sh a p t i cp r o x i e s ，n o t j u s tap o i n to r3 dm e s h c o n s i d e r i n gt h ef e a t u r eo fa r e a - c o n t a c ti n t e r a c t i o n ，o u r h a p t i cp r o x i e sa r ec o n s t r u c t e db ys a m p l i n gt h ec o n t a c ta r e a s t h et a r g e to b j e c t sa r e u n i f o r m l yp a r t i t i o n e dt oa c c e l e r a t et h eh a p t i cr e n d e r i n gp r o c e s s o u ra l g o r i t h mc a n h a p t i c a l l yr e n d e rs t a b l ea n dr e a l i s t i cf e e d b a c kf o r c e ，f o ri tn o to n l yr e s p e c t st h e i i i a b s t r a c t f e a t u r eo fa r e a c o n t a c th a p t i cd e v i c e sb u t h a sr e a s o n a b l ee f f i c i e n c y h a p t i c a l l yr e n d e r i n gh i g hc o m p l e x i t yo b j e c t si n r e a l t i m e i sd i f f f i c u l ta n dh a s b e e nr e c e i v e dm a n yi n t e r e s t s h a p t i cr e n d e r i n ga l g o r i t h m s ，w h o s ee f f i c i e n c y d e p e n d so nt h ec o m p l e x i t yo fi n p u tm o d e l s ，c a l ln o tr e n d e rh i g hc o m p l e x i t yo b j e c t s f a i r l yg o o d t oo v e r c o m et h i sp r o b l e m ，w ep r o p o s e dan e wh a p t i c b o x b a s e d r e a l t i m eh a p t i cr e n d e r i n ga l g o r i t h m h a p t i c b o xi sak i n do f r e p r e s e n t a t i o no f t a r g e t o b j e c tf o rh a p t i cr e n d e n n g ，w h i c he n c o d e st h ec o n t a c ti n f o r m a t i o no fs a m p l e dr a y s w i t ht a r g e to b j e c t w i t hh a p t i c - b o xr e p r e s e n t e dt a r g e to b j e c t ，c o l l i s i o nd e t e c t i o n a l g o r i t h mo n l yt a k e s6o p e r a t i o n st oc a l c u l a t ec o n t a c ti n f o r m a t i o nb e t w e e nal i n e s e g m e n ta n dt a r g e to b j e c t o n eo p e r a t i o ni st od e t e r m i n et h ec o n t a c ti n f o r m a t i o n b e t w e e nal i n es e g m e n ta n dab o x ，w h i c hi sf a s t t h eo t h e rf i v eo p e r a t i o n sa r e b i l i n e a r i n t e r p o l a t i o n ，w h i c ha l ef a s tt o o t h u s ，m a n yu n n e c e s s a r yc o n t a c t d e t e r m i n a t i o no p e r a t i o n sa r ea v o i d e da n dt h ep r o c e s so fc o l l i s i o nd e t e c t i o ni sv e r y r a p i d t h ec o n t a c ti n f o r m a t i o nf r o mc o l l i s i o nd e t e c t i o np r o c e s sc a nb ed i r e c t l yu s e d t oc o m p u t ef e e d b a c kf o r c e ，i nt h ep r o c e s so fh a p t i cr e n d e r i n g ，o u ra l g o r i t h md o e s n t d i r e c t l yd e a lw i t ht h ei n p u th i 曲c o m p l e x i t ym o d e l s ，h e n c ei ti si n d e p e n d e n to ft h e c o m p l e x i t yo fi n p u tm o d e l s e x p e r i m e n t ss h o wt h a to u ra l g o r i t h mi sb o t hr a p i da n d e f r e c t i v e k e y w o r d s ：h a p t i cr e n d e r i n g ，c o l l i s i o nd e t e c t i o n , h a p t i c b o x ，h i g hc o m p l e x i t y m o d e l ，a r e ac o n t a c t i v 第一章绪论 与视觉、听觉一样，力觉也是人类感知外部世界的重要模态之一。然而力 觉与视觉、听觉又有重要的区别，它与环境的交互是双向的，不仅接受场景给 人的信息，还作用于场景。尽管早在2 0 世纪早期，就有了关于力觉原理与机制 的研究，但是由于其复杂性，很多的机理到现在仍然是一个谜。随着计算机的 出现与迅速发展，计算机力觉学( c o m p u t e rh a p t i c s ) 逐渐成为人们研究的热点。 本章将概述力觉绘制的动机、相关工作，以及文章主要内容和组织结构。 1 1 力觉绘制的动机 1 1 1 定义 力觉( h a p t i c s ) 是指人与物体进行的物理交互，人类通过这种交互来感知 和操纵物体。这种交互可能发生在人与真实物体之间，也可能发生在机器人终 端操纵装置与真实物体之间，还可能发生在人手与虚拟物体之间。 计算机力觉学是一门研究如何为用户产生和绘制力觉的科学，就像计算机 图形学是研究如何产生和绘制图像一样。计算机力觉是一种允许人类与虚拟场 景交互的重要形式。在过去的几十年中，计算机图形学在显示与操纵虚拟物体 方面已经成为人机接口的最主要部分。随着计算机图形硬件的飞速发展，计算 机可以产生相片般的真实感图像、动画，以及实时交互仿真。我们期望计算机 力觉学能有同样的发展速度。近年来，越来越多的研究者投入到计算机力觉学 的研究当中。 力觉绘制是人感知场景中虚拟物体的过程。力觉绘制算法要正确计算虚拟 环境中力觉代理与虚拟物体的交互力，且通过力觉设备将交互力正确地作用到 用户。其中，力觉代理是力觉设备的虚拟表示，专用于力觉绘制。例如，在力 觉绘制算法中，力觉设备p h a n t o m 的探针往往被表示成一个点或一条线，而 力觉设备c y b e r g r a s p 经常用虚拟手的三维网格作为力觉代理。如图1 1 所示， 力觉绘制算法一般由两个步骤组成：碰撞检测和反馈力计算。碰撞检测算法首 先根据传感器或跟踪器传来的位置信息计算力觉代理与目标物体的碰撞位置、 方向等信息。然后，反馈力计算过程根据碰撞信息计算反馈力的大小与方向， 并将反馈力通过力觉设备传送给用户。这里的目标物体指的是需要进行力觉绘 制的虚拟物体。 一一，协簧饼息 罐攮点。，j t i ；, l反竣力 两螂踪器 痤母咂蜊至圜 1 1 2 力觉设备 图1 1 力觉绘制流程 由图1 1 知，碰撞检测算法必须根据力觉代理的位置计算碰撞信息，而力 觉代理的选择与力觉设备是密切相关的。反馈力计算过程计算出的反馈力最终 需要通过力觉设备施加于用户。可见，力觉绘制与力觉设备密切相关，好的力 觉绘制算法必须根据力觉设备交互的特点来设计。 力觉设备就像一个小机器人，它与用户交换着机械能量。市面上已经有很 多各种各样的力觉设备。力觉设备根据装载的位置不同，可以分为陆基的力觉 设备( g r o u n d - b a s e dh a p t i cd e v i c e ) 和可穿戴的力觉设备( b o d y - b a s e dh a p t i cd e v i c e l 两类鲥研j 。陆基的力觉设备往往装置于地面或桌面上，如s e n s a b l e 公司的 p h a n t o m 设备一般置于桌面上。而可穿戴的力觉设备一般穿戴在人体上，表 现为外骨骼形式，例如i m m e r s i o n 公司的c y b e r g r a s p 设备往往穿戴于人手上。 可穿戴的力觉设各具有良好的优点，它的运动模型与伸展空间和人类相当一致。 但是这些设备的设计却非常的复杂。所以，现阶段，还只有陆基的力反馈设备 能够取得良好性能。这里，我们只详细介绍一种典型的外骨骼设备c y b e r g r a s p 和一种常用陆基的力反馈设备p h a n t o m 。如果读者想了解更多力觉设备的信 息，请参见l a t i n 9 5 】【s r i n 9 7 s a l l i 0 4 】 w i n 9 0 6 】 v r l 0 0 6 。 c y b e r g r a s p 是i m m e r s i o n 公司开发的一种可穿戴的外骨骼力觉设备，它一 般穿戴于用户手上。使用它用户可以方便地去感知虚拟的三维物体i i ”m e 0 6 1 。如 图1 2 所示，c y b e r g r a s p 是一种很轻的外骨骼，它仅重3 5 0 克，却可以为每个 绪论 手指的指尖提供个最大1 2 n 的持续力，这个力的方向大致垂直予指失的播面。 i m m e r s i o n 公司提供了v i r t u a l h a n d i 具钰寒瓠牙力觉绘毒l 任务，v i r t u a l h a n d 工 具包使用g j k 【g i l b r g 。”。明绒者p q p t 9 q p 0 q 算法来进行实时碰撞检测。 图1 2 力觉设备c y b e r g r a s p p h a n t o m 怒由s e n s a n e 公避开发瀚基予戆蘸蕊一系捌力懿瑷备，它察一 般装置于桌面或地丽上。如图1 3 所示，用户通过操纵力反馈杆来感知与操作 寝锨物体【删。p h a n t o m 系列设备可戳提供给糟户高精度输入与高谦真的反 馈力输出ns e n s a b l e 公司提供了g h o s t 工具包著乏进行力觉绘制。 翻1 3 力赏设鍪p h a n t o m 1 1 3 力觉绘制的应用 力觉绘制有着广泛应用，这些应用需求刺激着力觉设备的开发和力觉绘制 算法的研究开发。而商用力觉设备的广泛使用与力觉绘制理论研究的突破又反 过来推动着实际的应用发展，甚至产生了新的应用。下面我们简单列举了力觉 绘制在医疗、娱乐、教育、工业等方面的一些应用。 在医疗方面，无论是远程诊断还是手术模拟，如果只有图像反馈而没有力 觉刺激，医生或学生都不能方便地正确诊断病情或得到真实感的训练。力觉系 统的加入，产生的准确反馈力可以使医生更精确地诊断病情，使实习生得到沉 浸式的仿真手术训练。例如有人描述了利用体数据的力觉绘制仿真颞骨手术 b r y 删】【a g u s 0 2 p e t e 0 2 1 。此外，对那些对图像不敏感的人来说，力觉绘制可以给他们 以更大的帮助，比如利用力觉界面帮助盲人学习与工作。 在娱乐方面，仅仅全三维的视频游戏已经不能够让玩家们感到满足，力觉 的缺失让玩家们感觉不到沉浸感。而力觉设备和模拟器能够让用户感知和操作 虚拟物体，使用户仿佛置身于真实的场景中。现在市面上存在很多具有力反馈 功能的游戏器材。罗技公司的w i n g m a n 力反馈游戏杆就是这种设备m 酗1 。 在教育方面，精美的图片能够让学生们了解自然界事物的形状，但却没有 办法让他们去更深层次的去了解事物的发生过程。如果能让学生去“触摸”，那 么学生可以真实了解更多的信息，比如事物硬度、凸凹性等。例如有人提出了 一种感知流体介质的方法，让用户可以较真实去感知流体介质8 “渊。 在工业方面，虚拟装配系统如果没有力觉系统的加入，就发挥不了其应有 的作用。力觉设备的发展与力觉绘制理论的突破，使人们可以把力觉系统方便 地集成到虚拟装配系统中，用户可在沉浸式虚拟环境中自由地进行虚拟装配操 作 j a y a 9 9 ；有人将力觉系统集成于c a d 软件系统，它不仅能够让操作者看到几 何物体的形状，还能让操作者感知物体的动态力或其它属性，比如硬度，纹理 等【h 0 1 1 9 7 ；力觉系统还可以用来辅助机械设计。例如，有人利用力觉系统辅助设 计了医用羊膜刺穿术机械装置【z h “0 3 】；力觉系统在反向工程中也找到了很好的应 用。有人提出了一种基于力觉的体积移除的一种新反向工程方法，并将这种方 法成功用于雕塑上r 9 0 射。 此外，力觉绘制还有着新的应用，比如科学可视化【t a y 】o 剐，雕塑变形 d a c “9 9 j 4 m c d 0 0 ” v “g o s ) ，绘图【b 删1 】i v “k 0 2 】等等。 1 2 相关工作 计算机力觉的广泛应用吸引了越来越多研究者的兴趣。近年来，随着计算 机硬件的飞速发展，计算机力觉学也成为研究热点。在过去的几十年里，研究 者已经针对各种各样的力觉设备研究开发了许多力觉绘制算法。这些算法根据 力觉代理的不同，大致可以分成两类：基于点的力觉绘制算法和基于物体的力 觉绘制算法。 1 2 。1 基于点的力觉绘制 在基于点的力觉绘制算法中，力觉代理常常表示成一个点或一条有向线段， 把绘制力觉设备与目标物体的交互简化成绘制一个点或一条有向线段与目标物 体的交互，如图1 4 所示。这种简化可以大大加速力觉绘制的速度，以满足力 觉设备更新频率的需求。 浚最近点 ( a ) 基于点的力觉交互 ( b ) 基于有向线段的力觉交互 图1 4 基于点的力觉绘制 在基于点的力觉交互中，力觉代理表示力觉设备的端点，且力觉代理在与 虚拟物体碰撞后能够刺入虚拟物体。每次用户移动力觉设备通用探针，碰撞检 测算法检查与其端点对应的力觉代理是否在虚拟物体内部。如果是，则找出力 觉代理与虚拟物体表面上的一个点( 如表面最近点) 之间的距离作为刺穿深度 x ，如图1 4 ( a ) 所示。在基于有向线段的力觉交互中，力觉代理表示为一条有向 线段，即将力觉设备的通用探针表示为一条有向线段。该有向线段与物体表面 求交得到的交点称为碰撞点p 。碰撞点p 与有向线段终点的距离称为刺入长度 绪论 m 曲o l 】【驴”，绘图口删1 】m 。0 2 喀等。 1 2 相关工作 训算机力觉的广泛应用吸引了越来越多研究者的兴趣。近年来，随着计算 机硬件的飞速发展，计算机力觉学蛆成为研究热点。住过去的几十年单，研究 者已经针对各种各样的力觉设蔷研究扦发了许多力觉绘制算法。这些算法根据 力觉代理的不同，人致可以分成两类：基丁点的力觉绘制算法和基于物体的力 觉绘制算法。 1 2 。1 基于点的力觉绘制 在基于点的力觉绘制算法中，力觉代理常常表示成一个点或一条有向线段， 把绘制力觉设备与目标物体的交互简化成绘制一个点或一条有向线段与目标物 体的交互，如图1 4 所示。这种简化可以大大加速力觉绘制的速度，以满足力 觉设备更新频率的需求。 袭俺最近点 ( a ) 基于点的力觉交互( b ) 基于有向线段的力觉交互 图t 4 基于点的力觉绘制 在基于点的力觉交互中。力觉代理表示力觉设备的端点，目力觉代理在与 虚拟物体碰撞后能够刺入虚拟物体。每次用户移动力觉设备通用探针，碰撞检 测算法检查与其端点对应的力觉代理是否在虚拟物体内部。如果是，则找出力 觉代理与虚拟物体表面上的一个点( 如表面最近点) 之间的距离作为刺穿深度 * ，如图1 4 ( a ) 所示。在基于有向线段的力觉交互中，力觉代理表示为一条有向 线段，即将力觉设备的通用探针表示为一条有向线段。谚有向线段与物体表面 求交得到的交点称为碰撞点，。碰撞点p 与有向线段终点的距离称为刺入长度 求交得到的交点称为碰撞点，。碰撞点p 与有向线段终点的距离称为刺入长度 d ，刺入长度在碰撞点p 法向方向的长度称为刺穿深度x ，x = d c o s a ，其中口 是有向线段与碰撞点p 处表面法向的夹角，如图1 4 ( b ) 所示。 在基于点的力觉绘制中，反馈力f 通常是用虎克定律f = h 计算的，其中k 是物体的硬度，x 表示刺穿深度。在没有磨擦的交互中，f 的方向为碰撞点所 在表面处的法向。 早期的工作大多集中在基于点的力觉绘制方法。m a s s i e 和s a l i s b u r y 为力觉 设备p h a n t o m 开发了一种基于点力觉绘制方法m “9 4 1 ，其原理如图1 4 ( a ) 所 示。力觉代理表示成一个点，代表力觉设备端点，力觉代理与物体表面最近点 的距离为刺穿深度z ，反馈力的大小利用虎克定律来计算。为了确定f 的方向， 算法将目标物体分解成若干子空间，每一块小表面都与这些子空间相关，由力 觉代理所在子空间来决定反馈力f 的方向。这种方法也被称为基于惩罚的方法。 基于惩罚的方法也被用来对体数据进行力觉绘制脚“9 6 1 1 w a t 9 3 。 基于惩罚的方法最大的优点就是简单。在绘制简单形体( 如球面、平面等) 时，反馈力的大小和方向都很容易确定。然而这种方法也有一些的缺点 z i l l 9 5 1 。 首先，如图1 5 ( a ) 所示，当力觉代理从一个子空间移动到另一个子空间时，其反 馈力的大小与方向都发生了很大的变化。其次，如图1 5 ( b ) 所示，对于细长物 体，力觉代理很容易穿透过去，算法从而得出错误结论。 ( a ) 力的不连续性( b ) 穿透细物体 图1 ，5 基于惩罚方法的缺点 为了克服基于惩罚方法的缺点，z i l l e s 等提出了一种基于约束的方法 z i l l 9 4 1 。 作者将当前虚拟物体表面上的一个点称为“g o d o b j e c t ，这个点到力觉代理的距 离最小。每次用户操纵力觉设各时，力觉代理位置发生变化，算法同时更新 “g o d - o b j e c t ”的位置，但是“g o d o b j e c t 的更新位置被约束在当前虚拟表面上。图 1 6 显示了基于约束的力觉绘制过程。当力觉代理还没有刺入目标物体时，力觉 绪论 代理和“g o d o b j e c t ”的位置是重叠的。力觉代理刺入目标物体后，“g o d o b j e c t 仍 然被约束在当前物体表面上。即使最后力觉代理刺透了目标物体，“g o d o b j e c t ” 仍然被约束在物体表面上。在基于约束的方法中，反馈力的方向很容易确定， 不会出现图1 5 ( a ) 所示的情况。1 5 ( b ) 中显示的穿透现象也同样得到避免。然而， 由于“g o d o b j e c t ”本质是只是一个没有大小的点，所以，当物体网格有极小的间 隙时，“g o d o b j e c t ”不能跳过这些间隙，从而绘制出来的反馈力也不正确。要正 确绘制这种网格表示的物体，算法必须重构网格的拓扑。 九馓代理 g o d o b j e c t 声护 p 毋 图1 6 基于约束的力觉绘制方法 r u s p i n i 等扩展了 g o d o b j e c t 的想法，他们用一个虚拟代理代替 “g o d o b j e c t ，而这个虚拟代理是有大小的【r u s p 9 ”。当这个虚拟代理的大小合适 时，就可以避免 g o d - o b j e c t ”方法产生的问题。除此以外，虚拟代理还可以用来 刻画摩擦力、表面硬度、纹理信息等。 b a s d o g a n 等提出了一种基于有向线段的力觉绘制方法 b ”d 9 7 】。有向线段的 方向与位置由力觉设备的探针决定。算法执行三步来进行碰撞检测。首先有向 线段与物体的包围体求交；然后有向线段与物体各面片的包围体求交：最后有 向线段再与物体各面片求交。这三步可加速碰撞检测过程。基于有向线段的方 法简单快速，特别适于那种细长的工具对象，比如力觉设备的探针等。但它也 绪论 有不足。用它计算的反馈力，方向容易发生突变。如图1 7 所示，当力觉设备 探针移动时，可能与另外一个面片相交，如果这个面片的法向与原来面片的法 向很不一样，就会造成反馈力f 的方向发生突变。 9 、 fv 图1 7 基于有向线段的力觉绘制 1 2 2 基于物体的力觉绘制 与基于点的力觉绘制算法不同，很多力觉绘制算法致力于直接绘制两个三 维物体之间的交互，这类算法被称为基于物体的力觉绘制算法。基于物体的力 觉绘制算法功能非常强大，可以绘制各样类型的交互。然而，由于两个三维物 体之间的碰撞检测操作计算复杂性比较高，所以基于物体的力觉绘制算法主要 致力减少力觉绘制的计算复杂性，提高力觉绘制的效率。 有人利用凸分解技术来提高力觉绘制效率恤酬 e h m a 0 1 。算法先用凸分解方 法将两个三维物体分解成两组凸块，然后对这两组凸块进行碰撞检测。由于凸 块之间的碰撞检测算法效率比较高，所以凸分解技术的应用可以提高两个三维 物体之间碰撞检测运算的速度，从而提高力觉绘制的效率。这种算法可以对模 型复杂度不高的三维物体进行力觉绘制，但是却较难用于高度复杂模型。这是 因为高度复杂模型凸分解之后会产生过多凸块，超出机器的处理能力。如图1 8 所示，应用 e h m a 0 1 凸分解方法，1 0 万个面片的国际象棋模型被分解成3 2 1 1 7 个凸块。如果绘制两个这种国际象棋的交互，凸块之间的碰撞检测效率再高， 也不能处理如此多凸块之间的碰撞检测。 8 ( a ) 原始模型( b ) 网格模型( c ) 凸分解后模型 图1 8 象棋模型的凸分解 细节层次技术( l e v e l o f - d e t a i l ) 是一种广泛应用于计算机图形绘制的技术。 有人将l o d 技术借鉴到力觉绘制中铀枷5 】 o t 鲥0 3 】。层次细节技术的力觉绘制的关 键思想在于为物体建立一个多分辨率的层次表示，在定的层次之下，用户感 受不出算法绘制出来的力的差异。通过案例分析，可以得到一个临界感知系数 瓯。算法在遍历层次时计算当前层次的感知系数s ，比较s 和鼠的大小，只 有s 大于爵时，算法才继续遍历下一层次。当s 小于瓯，算法就停止遍历，并 用当前层的模型计算反馈力。 s h a h 0 5 】和【o t a d 0 3 】中的方法不同在于， s h a h 0 5 】 中的方法采用的是一种与图形网格相关的力觉网格来建立层次结构，而 o t a d 0 3 1 中的方法没有引入力觉网格，其层次结构是通过对原始网格进行力觉保持的网 格简化操作得到。 细节层次技术力觉绘制算法不需要遍历所有层次，所以算法速度是比较快 速的。但是高度复杂模型的层次结构层次过深，要遍历到临界感知系数对应 的层次，需要消耗大量的时间，算法的计算复杂度不便于控制。对于更新频率 要求苛刻的力觉设备，这种方法往往不能胜任。 m c n e e l y 等提出了一种基于物体离散表示的力觉绘制算法 v o x m a p p o i n t s h e l l ( v p s ) m c n 删。在v p s 中，静态物体被分解为一组体素，而 动态物体则被离散成一个点壳，如图1 9 所示。这样，两个一般物体的力觉绘 制问题便被转化成动态物体的点壳与静态物体的体素之间的力觉绘制。 ， _ - j ， 、 ，江、_ ， 9 ， ( * - 。 2 气 。t ， 、 ，一 l_ 一。 图1 9 v p s 力觉绘制 v p s 方法的优势在于算法的复杂性是可控的。场景中静态物体与动态物体 的离散精度是可以根据计算机的计算能力来调节的，计算能力弱时，采用低离 散精度，计算能力强时则采用高离散精度，从而确保算法可以提供实时的反馈 力。但是这种离散算法也有它的不足之处。算法要有高效率，必须降低物体离 散精度，离散精度的降低导致物体表面细节特征的丢失，从而损失了绘制出来 的反馈力的精度。而且，v p s 对所有静态物体采取同样的离散精度，可能会致 使有些物体离散精度不够，而有些物体却获得不必要的高精度。 后来，m c n e e l y 等又对v p s 作为了改进t m 州e 0 5 1 。他们利用距离场、空间紧 致性、冗余判交运算剔除等方法进一步提高算法效率，从而提高物体的离散精 度。但是这种提高是有限的，离散精度仍满足不了高度复杂模型的要求。 1 3 本文研究内容与结构 从以上介绍可知，目前力觉绘制的研究还处于初级阶段，好力觉绘制算法 的研究开发仍然极富挑战，尤其是绘制面接触交互的好力觉绘制算法。在已有 的算法中，要么把问题过于简化，不能够很好绘制面接触的交互，比如基于点 l o 的力觉绘制算法；要么把问题复杂化，疲于应付高计算复杂性，比如基于物体 的力觉绘制算法；在计算复杂性可控时，却又较大牺牲了算法的绘制精度。 本文的研究目标有两个：一个是在仔细分析面接触交互特点的基础上，研 究开发适用于面接触的力觉绘制算法；另一个是研究一种适于高度复杂模型的 实时力觉绘制算法，要求这种算法不仅能够较精确地实时绘制高度复杂模型， 而且其计算复杂度是可控的。 本文的主要内容与组织结构为： 第一章：绪论。介绍本文的研究背景( 包括力觉绘制的软硬环境) 、相关概 念、前人工作、应用前景等。 第二章：基于面接触的力觉绘制算法。在分析和总结前人工作的基础上， 提出了基于面接触的力觉绘制的概念，并且研究开发了适于绘制面接触交互的 力觉绘制算法。该算法采用共点线段簇作为力觉代理，既尊重了面接触交互的 特点，又能够快速地进行力觉绘制，从而绘制出真实稳定的反馈力。 第三章：高度复杂模型的实时力觉绘制算法。提出了力觉包围盒的概念， 并研究开发了基于力觉包围盒的实时力觉绘制算法。力觉包围盒记录着离散采 样光线与目标物体的相交信息，由位置包围盒和方向半立方体组成。其中，位 置包围盒用于位置双线性插值，方向半立方体用于方向双线性插值。给定一个 有向线段表示的力觉代理，算法只需要执行一次有向线段与包围盒的求交运算 和五次双线性插值运算即可确定力觉代理与目标物体之间的碰撞信息以计算反 馈力。 第四章：工作总结与展望。总结了本文工作的优点与不足，并针对本文工 作的不足，提出未来可能的改进思路。 基于面接触的力觉绘制算法 第二章基于面接触的力觉绘制算法 2 1 引言 好的力觉绘制算法必须满足两个条件：首先，算法必须针对力觉设备交互的 物理特性设计。这是因为算法与力觉设备密切相关。其次，算法效率必须达到力 觉设备更新频率的要求( 很多力觉设备的更新频率在1 k h z 以上) 。两个条件缺少 任何一个，算法都不可能绘制出真实稳定的反馈力。 有一类交互是面接触交互。有很多力觉设备提供了面接触交互接口。然而这 类力觉设备供应商提供的力觉绘制算法并不能很好绘制面接触交互。以 i m m e r s i o n 公司的c y b e r g r a s p 为例，c y b e r g r a s p 在虚拟环境中一般表示为一个虚 拟手，虚拟手与场景中的虚拟物体之间的交互是面接触的。i m m e r s i o n 公司提供 v i r t u a l h a n d 工具包来进行力觉绘制。在我们的实际使用中，发现即使绘制中等 复杂的三维物体，v i r t u a l h a n d 工具包产生的反馈力也极为不稳定。我们分析得 出反馈力不稳定的原因主要有以下两方面： 首先，v i r t u a l h a n d 工具包使用的碰撞检测引擎效率不高，无法满足实时力 觉绘制的需求。v i r t u a l h a n d 工具包使用g j k e o i m 8 8 l c a m 。9 7 1 或p q p p q p 0 6 】算法来进行 实时碰撞检测，虽然g j k 和p q p 算法非常适合于邻近查询的应用，但不能有效 地执行实时碰撞检测任务。 其次，v i r t u a l h a n di 具包使用的力觉绘制算法并没有尊重虚拟手与虚拟物 体的交互是面接触这个物理特征。g j k 和p q p 算法都只返回两个三维物体之间 的最近点对。 已有的力觉绘制算法中是否有合适的呢? 答案是否定的。基于点的力觉绘制 算法将力觉代理表示成一个点或一条有向线段。将虚拟手指尖表示成一个点或一 条有向线段，显然没有尊重虚拟手指尖与虚拟物体是面接触这个物理特征。 基于物体的力觉绘制算法往往将虚拟手直接表示成三维网格。尽管基于物体 的力觉绘制算法功能很强大，可以模拟绘制面接触的交互，但却受到高计算复杂 度的制约。 所以，我们需要研究开发新的算法来绘制面接触交互。该算法既要求尊重面 基于面接触的力觉绘制算法 接触交互的特点，又要求有足够高的效率进行实时力觉绘制。基于这两个要求 我们提出了一种新的基于面接触的力觉绘制算法。 2 2 算法框架 在这一节，我们将简要介绍我们算法的框架。该算法由两个阶段组成：预处 理阶段与运行时阶段。图2 1 显示了我们算法的体系结构。 l| 构造力鲎代理 l 。一 i i _ _ _ _ _ _ - _ - _ - 。_ _ _ _ _ _ _ _ _ _ _ 。_ _ _ _ - 。1 。_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 。_ _ 一 ：j 均匀翱丹i ：| i 标物体 l i 一一一一一飞一一一一一1襁处理衍段 一一一一一一一_ 毒忡- 一一卅一一一一一一忡一一， 千；。= 二= = = = 。_ 。而运 j 时阶段 i 从传感器嬲r 鲸器取褥。ii i浆位嚣信息ii 舔赢丽焉 拦 取得碱撩髂息 汁蛑麟馈力 通过力觉泣簪转送反馈 鲥撵 乍者 图2 1 算法的体系结构 在预处理阶段，我们首先为虚拟手的指尖构造力觉代理。在我们的算法中， 虚拟手指尖的力觉代理被定义成共点的线段簇，这个共点线段簇通过对指尖接触 面的离散采样得到。使用这种力觉代理进行力觉绘制的算法尊重了面接触交互的 特点。然后，我们将目标物体空间精确均匀剖分成一系列网格，网格上记录着目 标物体的面片信息。对目标物体空间的均匀剖分加快了光线与目标物体的求交过 程。在图形绘制中，这种空间剖分方法有着，“泛的应用。在我们的算法中，它同 样能够大大加速力觉代理与目标物体之间的碰撞检测运算。 算法构造好力觉代理和均匀剖分好目标物体空间之后，进入运行时阶段。算 基于面接触的力觉绘制算法 法首先从传感器或跟踪器取得力觉代理与目标物体的最新位置信息，然后根据位 置信息执行碰撞检测运算，检测力觉代理与目标物体是否发生了碰撞。如果发生 了碰撞，再根据碰撞信息计算最终的反馈力。最后，将反馈力通过力觉设备作用 到操作者。 碰撞检测往往是力觉绘制算法最费时的步骤。有了线段簇表示的力觉代理和 均匀剖分的目标物体，我们的碰撞检测算法简单且快速。下面，我们将详细介绍 力觉代理的构造，目标物体空间的均匀剖分，以及反馈力的计算过程。 2 3 力觉代理的构造 好的力觉代理必须能够高效地绘制面接触的交互。我们的力觉代理是通过对 可能接触面采样构造的共点线段簇组成，如图2 2 所示，它是一个简单而有效的 力觉代理。下面，我们将以虚拟手指尖为例，描述我们力觉代理的构造过程。 ( a ) 蓝色包围的是接触区域 ( b ) 红线表示力觉代理 图2 2 力觉代理的构造 1 4 基于面接触的力觉绘制算法 给定虚拟指尖的网格表示，我们通过以f 四步构造需要的力觉代理。