《基于速度驱动的复杂场景多层级力觉交互算法.doc》由会员分享，可在线阅读，更多相关《基于速度驱动的复杂场景多层级力觉交互算法.doc（14页珍藏版）》请在金锄头文库上搜索。
1、计算机学报2009年8期速度驱动的复杂场景多层级力觉交互算法周万琳，王党校，张玉茹，王瑜(北京航空航天大学虚拟现实技术与系统国家重点实验室，北京 100191)摘要：随着触/力觉交互技术应用环境的复杂化，对复杂触/力觉场景的研究提出了新的挑战。本文以虚拟现实牙科手术训练系统为背景，研究基于速度驱动的复杂场景多层级力觉交互算法。本文采用CATIA对下牙列大量数据进行网格简化，建立了下牙列场景的层次细节（Levels Of Detail,简称LOD）模型；基于人类触觉感知的精度随交互速度的变化规律，设计了速度驱动的LOD模型触发机制；提出了虚拟工具化身SCP（Surface Contact Poi
2、nt）层级映射算法，保证了力觉交互设备的稳定性，并发现了映射约束线段的长度是保证力觉逼真性及实时性协调的关键变量；最后，设计了针对一般几何体和复杂曲面的实验量化评价本文算法的逼真性及实时性，证明了将人手运动速度作为场景模型复杂度切换驱动条件的有效性。关键词：虚拟现实、触/力觉、复杂场景、层次细节、速度驱动11.引言针对大数量单元存在的虚拟场景，场景的实时刷新问题是制约力觉研究的一个难点。本文研究背景是虚拟牙科手术培训系统，牙科手术培训的重点是医生手部精细操作能力的训练，牙齿不同病变组织存在微小几何特征和不同物理属性（如硬度、摩擦等），虚拟牙齿要提供精细的触觉感受，必须建立在拥有大量数据的精细模
3、型基础之上。在本文研究对象中，如图1a)所示的全口内单排牙列，其表面三维测量数据顶点数143,865，面对数量如此巨大的模型，仿真系统难以满足1KHz的力觉渲染需求。如果简化数据，虽然能满足视觉和力觉渲染的实时性，但感受牙齿表面的微小几何特征（如图1b）所需的力觉逼真度难以保证。 a) 大数据量单排牙列 b) 单牙龋齿模型：精细的几何与物理特征 图1牙科手术培训系统交互场景示意图 在复杂场景图形场景渲染研究中，对于不必要使用高分辨率模型的场合，通常采用网格简化技术来提高渲染效率，主要分为两类方法：静态和动态化简方法1。对模型准确度和计算时间折中的做法是采用层次细节（LOD）技术，其方法有两种：
4、静态构造几个LOD模型以及动态构造连续的LOD模型，后者一般采用渐进式网格来实现2。例如Xia3将连续LOD发展为一个基于视点的为地形建模服务的LOD，这种方法精细化用户凝视的地方，其他部分保持粗糙的模型。然而将LOD技术推广到力觉交互中，面临力觉循环1000Hz的计算需求，产生了新的问题。ElSana等人将多分辨率用于力觉渲染，在探针附近区域采用精细网格，在其余区域采用粗网格4。Otaduy开发了针对凸面片的多分辨率包围盒构建方法，但是不支持渐进的传输，因此不适合具有有限内存空间的力觉渲染环境5。Liu等介绍了一种新型的“局部细分”方法来满足力觉渲染对快速碰撞检测的要求6，精确的碰撞检测只在
5、局部细分的网格上进行。Zhang等提出在粗糙网格模型上细分感兴趣的区域的方法，通过控制模型的节点数，来调和柔软物体变形时力反馈计算要求快速与图形显示要求计算细节的矛盾，以保证仿真能够高效率的进行7。Pavel8等人将人的探查速度作为多分辨率模型之间切换的触发条件，利用归并树数据结构构造多分辨率的交互模型，但其数据结构比较复杂，不容易保证算法稳定性。综合上述研究情况，基于LOD模型的力觉交互技术，尚未解决的两个关键问题是：1. 选择何种类型的LOD模型？所选模型既要能保留模型的几何特征，又要能够适应力觉渲染计算的快速性要求；2. 不同的LOD模型的触发条件如何定义？在图形学领域中，基于视点的LO
6、D模型触发条件很好地模拟了人类的视觉感知特性。在触觉感知中，如何定义新的触发条件，并保证交互过程的稳定性？针对上述问题，本文提出了速度驱动的复杂场景多层级力觉渲染方法。根据人在不同速度下探查物体表面的不同触觉特征，通过测量交互速度来触发不同的模型层级调用，以满足力觉/视觉渲染实时性和逼真性的要求。全文组织如下：第二节，针对复杂场景逼真性与力觉交互实时性之间的矛盾，提出了复杂场景的力觉建模技术，支持力觉交互的LOD模型以及速度驱动的多分辨率渲染算法。第三节，介绍实验结果。第四节，给出全文结论和未来工作展望。2.速度驱动的力觉渲染算法2.1 复杂场景层次建模牙齿手术接触仿真中用到的牙齿原始数据为激
7、光扫描得到的牙齿轮廓数据。本系统采用三角片模型描述牙齿，采用点模型描述探针工具。LOD模型的建立方法主要有离线LOD模型、关注局部区域进行细化的局部细节方法和渐进式网格等。而离线LOD模型因其算法简单稳定，成为快速检验LOD切换触发条件合理性的最佳方法。本文在测试Simplifier等开源网格简化软件包以后，发现在三角片简化过程中容易出现局部细节丢失、三角片破裂等缺陷。目前图形学中已有许多较为实用的面片简化算法1，但由于本文的工作重点在于验证速度驱动的力觉渲染算法，故直接采用现成工具软件。调研发现CATIA商用软件中数据编辑器模块含有网格简化的功能，可以在给定顶点删除率的情况下，首先选择删除对
8、表面曲率影响小的点，从而保证简化的效果能够有效的保留模型的几何特征，并且可以方便的对面片进行修补等操作。最终选择基于CATIA来进行模型的三角片网格简化工作。如图2所示为Stanford bunny模型在CATIA中的简化效果，可以看到利用CATIA进行三角片网格模型的简化可以很好的保留模型的几何特征。a)顶点数30,000 b) 顶点数4,000 c) 顶点数400图2 CATIA模型简化效果针对LOD模型，需要分别对每个层次细节，结构化存储对应层级模型的拓扑信息，包括：三角片网格内部元素拓扑信息和三角片网格与空间包围盒信息两类。每个层级的模型为一个基本数据单元LODNode,其数据结构设计
9、如表1。在程序的初始化阶段，需要离线完成这些数据结构的建立工作,将力觉渲染计算的碰撞响应模块中需要用到的模型拓扑信息进行预计算,并加载到内存中,方便仿真交互过程中的快速调用。表1 三角片网格顶点法向量列表三角片相邻几何元素集合三角片网格与包围盒关联关系三角片法向量列表顶点相邻几何元素集合将上述网格简化方法和LOD模型应用于虚拟牙科手术系统得到模型效果如图： 图3下牙列低层级线框表示 图4 下牙列高层级线框表示2.2 速度驱动的多分辨率渲染算法基于人类触觉感知的规律，在人与虚拟环境交互的过程中，交互速度与可感知特征之间存在一定关系，Pavel8等人的研究结果表明：当被探测的物体表面曲率比较大的时
10、候，人会不自觉的放慢探测的速度。Susan等人通过实验证明人类触觉感知的精度随交互速度的变化规律可以近似拟合为二次曲线，随着速度增加，感知能力相应降低9。上述研究结果表明通常在高速探查的情况下，可以忽略局部细节特征，这样并不会损失触觉感受的真实程度。因此本文选择交互速度为LOD模型的触发条件。另一方面，在交互过程中，不同交互速度也将带来计算时间复杂度的差异。在碰撞检测算法中，用代表本次仿真循环的力觉设备点位置，代表上次仿真循环的力觉设备点位置，代表上次仿真循环结束时虚拟工具点的位置。则本次仿真循环的轨迹线段长度定义为，用表示本次仿真循环的人机交互速度（即交互设备运动速度，也即人手速度运动）的大
11、小，则： (1)即轨迹线段的长度与人机交互速度成正比。人手移动交互设备末端杆的速度越快，一个采样周期内虚拟工具点的运动轨迹线段就越长，参与碰撞检测计算的三角片数量就会增加，从而延长了力觉循环所需要的时间，从一定程度上影响交互系统的实时性和逼真性。分析可知，以满足力觉渲染实时性为前提（力信号刷新频率大于1KHz），模型可支持的最大交互速度与该模型的复杂度相关，交互速度越快，能支持的模型复杂度越低，呈减函数。由于其非线性规律未知，基于离散LOD的思想，本文提出如图5的离散LOD速度驱动模型，其中层级0为最精细层级，层级精细程度随序号增加而递减。图5 速度驱动的离散LOD切换模型上图中的层级精度根据
12、具体任务的模型精度需求预先给定，速度参数则根据层级模型由实验确定。首先通过对给定几个层级的模型进行力觉交互实验，确定能满足每种模型交互实时性需求的速度阈值，从而确定模型切换的速度。例如三个层级需要两个层级切换速度，分别为（层级0）和（层级1）之间的切换速度，（层级1）和（层级2）之间的切换速度。在仿真系统中应用速度驱动LOD力觉渲染算法时，当速度小于等于时，调用最精细的层级，当速度大于小于时，调用中间层级，当速度大于等于时，调用最粗糙的层级。基于上述模型，在力觉伺服线程中，首先计算交互速度，根据交互速度解算出目标层级的序号，将该层级设置为当前交互的模型对象，根据交互工具的运动信号，进行碰撞检测
13、、碰撞响应计算，从而实现LOD速度驱动模型。2.3 SCP层级映射算法在验证如图5的离散速度驱动模型以后，发现在接触交互发生LOD层级切换时，操作者可以感受到明显的振动。分析振动发生的原因后，本文提出一种SCP（Surface Contact Point）层级映射算法。该算法减少了振动，提升了力觉交互的逼真度。分析振动发生是由于不同层级之间存在结构误差，其原因如下：如图6，当交互速度从减慢到时，接触交互LOD模型需要从较为粗糙的，切换到较为精细的。从力觉渲染流程可以看到，上一时刻碰撞发生，当前的交互状态处于碰撞发生阶段，当前时刻应该继续碰撞响应模块，根据上一仿真循环结束时的虚拟工具点位置SCP
14、，基于其所从属的几何元素，进行碰撞响应阶段的计算。然而，SCP点位于的几何元素上，而该几何元素可能在多分辨率模型建立的网格简化过程中受到过简化，且不同层级的几何元素有着不同的拓扑结构，因此需要在目标层级从切换到的同时，将位于上的点向做映射，求解。从而保证层级切换时力信号的连续性，以消除振动感。图6 LOD切换中的SCP层级映射下面介绍SCP层级映射算法。为方便描述问题，本文定义映射约束线段、映射约束包围盒单元如下：定义1-映射约束线段上次仿真循环结束时所计算出的交互力用表示，方向为，虚拟工具点位置用表示。定义映射约束线段的起点为，方向沿，线段的长度为L。则可解算出映射约束线段，其中： (2)(
15、3)定义2-映射约束包围盒单元定义映射约束包围盒单元为与映射约束线段相交的哈希包围盒单元，如图7。为了计算位于上的点，需要计算与三角片网格的交点，首先应该获取与相交的包围盒，然后根据三角片网格与包围盒之间的关联关系，将遍历相交包围盒中的三角片与求交计算得到。图7 映射约束线段与映射约束包围盒单元根据和的体素坐标，计算包围盒对象的两个角点，利用GHOST SDK的求交函数，对这两个角点内的所有体素进行遍历，记录相交体素为一个相交包围盒单元，所有相交包围盒单元构成映射约束包围盒集合。SCP层级算法流程如下：1. 设置映射约束线段长度为L；2. 根据与构造映射约束，并求解映射约束包围盒集合；3. 遍历包围盒中所有关联三角片，判断三角片与映射约束线段是否相交； 1) 相交则记录交点为目标层级Li上的，同时设置映射发生标志为真； 2) 不相交，则判断包围盒遍历是否结束； a) 包围盒遍历结束则，记录为，设置映射标志发生为假； b) 否则，返回3继续遍历包围盒中关联三角片. 分析上述算法可以看到，正确设置映射约束线段的长度L对于提高算法效率非常重要。过大的L会无谓增加映射约束包围盒单元，增加三角片遍历和求交计算的耗时；过小的L可能导致解算为空，错误设置映射发生标志进入碰撞检测计算模块，此时的碰撞检测
