(模式识别与智能系统专业论文)一种虚拟组装平台下的关键技术研究.pdf_第1页
(模式识别与智能系统专业论文)一种虚拟组装平台下的关键技术研究.pdf_第2页
(模式识别与智能系统专业论文)一种虚拟组装平台下的关键技术研究.pdf_第3页
(模式识别与智能系统专业论文)一种虚拟组装平台下的关键技术研究.pdf_第4页
(模式识别与智能系统专业论文)一种虚拟组装平台下的关键技术研究.pdf_第5页
已阅读5页,还剩78页未读, 继续免费阅读

(模式识别与智能系统专业论文)一种虚拟组装平台下的关键技术研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法,我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权,即:( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质印刷本及电子版) ,学校可以采用影印、缩印或其他复制手段保存研究生学位论文, 并编入南开大学博硕士学位论文全文数据库;( 2 ) 为教学和科研目的,学校可以将公开 的学位论文作为资料在图书馆等场所提供校内师生阅读,在校园网上提供论文目录检索、文 摘以及论文全文浏览、下载等免费信息服务;( 3 ) 根据教育部有关规定,南开大学向教育部 指定单位提交公开的学位论文;( 4 ) 学位论文作者授权学校向中国科技信息研究所和中国学 术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文数据库, 通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文,保密期限内不向外提交和提供服务,解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站:h t t p :2 0 2 1 1 3 2 0 1 6 1 :8 0 0 1 i n d e x h t m 。 本人承诺:本人的学位论文是在南开大学学习期间创作完成的作品,并已通过论文答辩; 提交的学位论文电子版与纸质本论文的内容一致,如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份,由研究生院和图书馆留存。 作者暨授权人签字:黄匝麴 2 0 1 0 年6 月3 日 南开大学研究生学位论文作者信息 论文题目 一种虚拟组装平台下的关键技术研究 姓名黄际劲学号2 1 2 0 0 7 0 2 7 8答辩日期2 0 1 0 年5 月2 8 日 论文类别博士口学历硕士硕士专业学位口高校教师口同等学力硕士口 院系所信息技术科学学院 专业 模式识别与智能系统 联系电话 l5 8 2 2 8 8 2 2 9 4e m a i l h u a n g j i j i n g 1 2 6 t o m 通信地址( 邮编) :天津市南开大学伯苓楼机器人所一楼3 0 0 ( 1 7 1 备注:是否批准为非公开论文 否 注:本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆,非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 4舢4川83 mmi舢8刖引i1-y 。擎幂直萃拱珥素士妨非娶审甭苗地素¥拦晕例澎革祺码丢拦妨非岛 皓圈辫蕈笋者焉( 曰鲤箪一) 量茸晕勘甲。革砚爵毒朝千逊千斟尊挺明士群瓣桂日娶难斟藓章:翼 2 茸珏妊影爿lk 裂= 群显并:孕母 。 一 j i 一 7o 戳一冬螂誓懿孓缈著¥士节譬攀, y - :( 嘴蜊) 1 耳w 署甄 w o 了归蹦! ! 帅竹i l ! m m 功毛双譬g 欲器si 尝印显靳 1 逻秽投钎f 3 研¥戤 不每 掣舅舅恬泮话、重挚 蟛竖黝 口千照华亲金剧口蛳辚辫掣口母亲亦每千班d :- r - 洫幽杀 e千斟 路椠茸现 曰舡酯匆4 ,o 嘶目挺最g 文o0 口之l 0 、胎n 0 、 p c n 0 、肋n 0 这四个条件同时成立。 图5 3 拉索选择 剪面 与点选一样,拉索选择仍然是基于物体包围盒的拾取,于是判断一个积木是 否被拉索选择等价于判断其包围盒上8 个点是否同时满足上述条件。 5 1 2 移动操作 5 1 2 1 普通移动操作 将场景中的物体选中之后,用户可以操作所选物体来进行三维空间中的运 动,由于鼠标仍是二维平面的操作,所以理论上只能操作物体在场景中的一个 特定的平面上运动,这个特定的平面可以用摄像机的当前视角来确定,这样, 通过不断的旋转摄像机就可以使物体运动至三维空间中的任何一个地方;另一 种方法是使用c o i n 3 d 提供的拖拽器,拖拽器是c o i n 3 d 引擎提供的操作物体动 作的工具,c o i n 3 d 包含多种常用的拖拽器,利用拖拽器可以实现多种方式的拖 第五章组装操作与辅助功能设计 拽运动。 5 1 2 2 “搭搭看 中的移动操作 通过摄像机法线与拖拽器实现的移动操作都需要不断的调节视角才能使物 体的精确定位,操作将会非常的复杂,考虑到在实际的虚拟组装应用中,对物 体的精确定位其实并不必要,重要的是将一个物体精确组装,所以在“搭搭看 平台下,使用了沿桌面移动的移动策略,即在场景中设置一个作为组装操作台 的虚拟桌面,所有的积木必须只能在上面移动,鼠标拖拽积木移动时,将鼠标 所指的二维坐标投影到三维桌面上,交点为p 1 ,此时,调用物体的位移函数 s e t p o s i t i o n ( p 1 ) 便使物体移动到p 1 处,当鼠标移动至投影交点为p 2 处,再 s e t p o s i t i o n ( p 2 ) ,便实现了物体对鼠标的跟随操作。 5 1 3 旋转操作 在“搭搭看平台下,支持两种旋转方式,分别是绕本体与世界坐标系下 的一点进行旋转。 1 绕本体坐标系一点旋转 绕本体坐标系一点旋转是旋转操作中最常用的一种方式,用户可以通过旋 转操作,调整物体的姿态,从而得到想要的组装效果。如图5 4 中的( a ) 图所示, 定义物体a a b b 包围盒的底面中心点为参考点o ,在参考点o 上建立本体坐标 系,坐标系上的三个轴分别平行与世界坐标系的三个轴,用户可以操作物体分 别绕着坐标系上的三个轴进行旋转。 2 绕世界坐标系一点旋转 在一些虚拟组装平台下会有一些特殊的零件,它们之间的咬合部分是一个 可以旋转的轴或者铰链等机构,意味着它们之间组合后,其相对的位姿关系不 确定,一个物体可以相对于另一个物体的旋转点或旋转轴进行旋转,这里,我 们称之为绕世界坐标系下一点的旋转。“搭搭看 平台下带条形状与球状的咬合 部分的积木便具有这样的旋转功能,本文设计了相应的3 d 操作方式,支持在组 合积木块中操作一个积木的旋转,在三维世界中,我们将其抽象成绕固定轴与 固定点的旋转。 3 5 第五章组装操作与辅助功能设计 图5 4 展示了三种典型的旋转情况: ( a ) 绕本体坐标系一点旋转( b ) 绕世界坐标系下轴旋转( c ) 绕世界坐标系下球旋转 图5 4 “搭搭看”的旋转操作情况 事实上,无论上述的哪种旋转情况,都可以被三个关键参数所描述,即世 界坐标描述下的旋转点p 与旋转轴y ,还有旋转角度a ,在这三个参数的共同作 用下,将得到一个变换矩阵t ,物体在这个变换矩阵t 的作用下将会产生相应的 旋转操作。 如图5 5 所示,要得到世界坐标下的变换矩阵t ,需要分三步,首先,在旋 转点p 上建立一个坐标系b ,得到世界坐标系u 在坐标系b 下的表示 纷( 此时,点p 即为坐标系b 的原点,绕旋转轴矿旋转角度a , 坐标系表示法的绕一般轴旋转公式得挖3 , 砭= ( 矧 ( 5 1 ) 利用等效轴角 ( 5 2 ) fk 匕( 1 一c o s a ) l v y ( 1 一c o s c a ) 一匕s i n 0 匕匕( 1 一c o s a ) + ,ys i n a l r = lv x v y ( 1 一c o s o ) + v :s i n ob b ( 1 一c o s a ) + c o s ob 屹( 1 一c o s 0 ) 一吃s i n al ( 5 4 ) i 吃屹( 1 一c o s o ) 一一s i n ov j ,v ( 1 一c o s o ) + v ,s i n 0 匕屹( 1 一c o s o ) + c o s aj 最后将其变换回世界坐标表示,记 咿1 = ( 5 5 ) 第五章组装操作与辅助功能设计 将这三步依次左乘,得到 丁= u 靠言丁= ( 言尸- 即) 变换到世界坐 标系下 ( 5 6 ) h 图5 5 绕点轴旋转示意图 5 1 4 摄像机操作 在虚拟场景下,摄像机模拟了人眼的功能,通过调整摄像机的位置与姿态, 可以使人多方位的观察虚拟场景。在三维场景中,可以存在多个摄像机,但是 每一时刻只能有一个摄像机被激活,通过对摄像机的切换可以达到一些特殊的 视觉效果。“搭搭看 中的虚拟场景中只配备了一个摄像机,提供了三种基本的 摄像机操作,分别是摄像机的平移、旋转和放缩。 不管是对摄像机的何种操作,都是操作摄像机对应的姿态矩阵,姿态矩阵 可分解为观察点与观察角这两个决定性参数,摄像机的平移与放缩分别只影响 观察点与观察角,而旋转操作同时影响了观察点与观察角。 3 7 第五章组装操作与辅助功能设计 第二节组装算法 5 2 1 基本算法设计 5 21l 时间响应紧急度 对于3 d 交互式程序来说,程序的核心算法与数据结构不一定要设计的精妙, 却一定要设计的合理。“搭搭看”由于支持成千上万个积木的组装,属于复杂的 强交互式虚拟系统,普通的遍历操作都会给程序带来很大的负担,所以数据结 构设计的好坏直接影响着软件系统的运行效率u 驯。 “搭搭看 是一个实时的虚拟组装平台。在平台的操作下,将涉及到许多 不同的算法,每种算法的计算都将给平台的实时性带来挑战,而算法的优化本 身有它的极限,但是在不同的情况下,算法却有轻重缓急之分,于是,本文提 出了“时间响应紧急度的概念。顾名思义,它表示了一种算法动作对响应时 间快慢的要求的高低。不同的算法、或者同样的算法在不同的情况下,它们的 “时间响应紧急度”均会有区别。“时间响应紧急度 本身应该是一个模糊的概 念,一个算法的“时间响应紧急度”不取决于一个定性的指标,而取决于在特 定情况下,它在所处算法群中的时间响应情况。引入这个概念后,可以帮助平 台合理的分配算法计算时间,从而让平台达到另一种意义上的实时。 下面,本文将对场景下几种典型的算法动作进行分析: 一对“时间响应紧急度 要求高的情况: a ) 场景更新 在对场景中的物体进行动作或者操作摄像机使场景发生变化后,需要立即 对仿真场景进行渲染,即让场景发生变化。 b ) 搜寻可组装情况 鼠标拖拽场景中的物体移动时,每个移动的变化会带来一次回调函数的调 用,在这个回调函数中,将要检查所有与移动积木块组装的情况,这个检查的 动作必须在两次鼠标移动的间隔中完成,所以它对“时间响应紧急度 的要求 也是非常高的。 曲碰撞检测 碰撞检测实际上是对物体的组装和空间情况进行可靠性分析,需要的实时 性很强,本文在第三章第三节已经对其实时性进行了详细的分析,所以它也是 第五章组装操作与辅助功能设计 属于对“时间响应紧急度 的要求很高的一种情况。 二对“时间响应紧急度 要求低的情况: a ) 摄像机操作 “搭搭看”的组装算法中,摄像机参数对组装将会有影响。在摄像机的移 动中,一些相关的信息将需要更新,在下次积木组装的时候作为参数代入算法 进行计算,但由于摄像机的操作与组装的操作不可能同时进行,此时将有足够 的时间来对相应的数据结构进行更新,所以,它对“时间响应紧急度 的要求 较低。 b ) 桌面更新 “搭搭看引入了动态桌面的概念,虚拟的桌面可以无限的延伸,桌面的 大小取决与场景中所有物体的位置,由于桌面只是虚拟组装平台下的一个辅助, 而且它的更新可以等移动操作结束时再进行,所以,它也是属于对“时间响应 紧急度要求低的情况。 c ) 场景分割 场景分割过滤虽然是组装算法的一部分,本应对“时间响应紧急度 要求 高,但是在下一节过滤算法中我们将了解到,整个场景分割的更新发生在所有 动作完成之后,此时已有足够的时间来进行场景分割,所以它也属于一种对“时 间响应紧急度要求低的情况。 从以上的分析可以看出,“时间响应紧急度 直接关系到算法数据结构的设 计,我们设计的数据结构应该向“时间响应紧急度 高的情况倾斜,而让“时 间响应紧急度”低的算法承担更多的计算量,从而达到提高整个仿真程序的运 行效率的目的。 5 212 投影吸附策略 由于虚拟操作的特点,使得鼠标在同一时刻只能操作积木在一个平面上运 动,要让积木移动到一个精确的三维位置的操作会比较烦琐,所以如果利用绝 对坐标的策略去操作积木进行搭建操作,虽然真实模拟了现实世界中搭建,但 会使得整体操作复杂化。于是我们提出了一种投影吸附的策略,在不改变鼠标 的移动策略的前提下,让积木块始终贴着动态桌面移动,然后对移动积木上的 搭建部分进行投影,若投影与静止积木的同类型的搭建部分满足一定的几何关 系时,静止积木块对移动积木块便会有个吸附动作,使得移动积木块“跳变 第五章组装操作与辅助功能设计 过去与其相互搭建n 4 1 。 摹差旃昏葛 黟一缓, 圜 陵 专 ,。氯翻 鬯一疆_ ”一jj 一1 飞和“峰“一睁哪 ( a ) 投影 图5 6 投影吸附示意图 ( b ) 吸附 由于所有的吸附操作都是基于积木的搭建部分,而搭建部分可以分为点、 线、面三种几何形体,这三种不同的几何形体对应着不同吸附操作u ,本文将 对这三种几何体的搭建属性代表球、轴、面进行吸附操作分析: 1 球搭建属性。对于球的投影来说,可以把它抽象成一个点,类似于拾取 操作,球形点将会与摄像机形成一条射线,判断与其他球型积木是否能吸附只 用判断其他的球的中心点与射线的距离是否满足吸附条件。 摄像机 图5 7 球形投影分析 2 轴搭建属性。轴代表了一个线段,描述一个轴需要两个点,根据不共线 第五章组装操作与辅助功能设计 三点组成一个平面的事实,可以将被投影轴与摄像机组成一个平面,再利用另 一个轴到这个面的距离来判断是否满足吸附条件。 摄像机 图5 8 轴形投影分析 静止轴 3 面搭建属性。在投影吸附操作中,面是种比较复杂的形体,需要考虑 的情况比较多,l e g o 积木的面包含了许多突起或凹陷的部位,本文称之为搭建 点,面的搭建既要考虑它的平面投影,也要考虑面上的搭建点。由于两面相交 才能搭建,所以先将面投影到需要判断吸附的平面上,考虑到一个面由面上的 四个顶点组成,我们可以选取一个特定的点进行投影,这个点叫做参考点 ( r e f e r e n c ep o i n t ) ,点被投影后再在投影面上进行面还原u 。 图5 9 平面投影分析 假设摄像机一点为c ,参考点记为p ,在摄像机投影下,将会在由法向量n 4 1 第五章组装操作与辅助功能设计 描述下的投影面上得点q ,点q 便是我们需要的目标点。 现记c 点到p 点的向量为y ,由于c ,q ,p 三点共线,则可记p q 向量为k ,。 另有投影平面上一点o ,记为参考点,设o p 向量为e ,则向量 o q = k o v - e( 5 7 ) 由于o q 向量在平面内,与平面法向量垂直,所以有 ( 后v - e ) 刀= 0( 5 8 ) 既而可得 七= 0 n ) ( v 刀)( 5 9 ) 于是 q = p + k ,( 5 1 0 ) 通过点q 将被投影面在投影面上还原,若参与吸附运算的两面不满足重合条 件,则不能被吸附,若满足还需要进行搭建点的判断才能进行吸附操作。如图 5 1 0 所示,l e g o 积木的面上,按一定规律的间隔分布着不同的搭建点,当两平 面重合时,需要验证搭建点是否匹配。由于投影吸附算法本身是一种粗略的吸 附策略,若对两个面之间的搭建点进行精确的坐标匹配会使得搭建吸附变得困 难,所以本文采取了循环扫描搭建点的方法机械能搭建点的匹配,一个面上的 一点将按图5 1 0 中的序号所标明的顺序对另一面上的搭建点进行循环匹配1 。 图5 1 0 搭建点循环扫描示意图 4 2 第五章组装操作与辅助功能设计 5 2 2 过滤算法 在虚拟组装平台下,对计算效率的高要求与无法回避的遍历操作始终是一对 矛盾,所以,为了提高平台运行效率,需要设计一系列的过滤算法,过滤掉一 些不必要的操作,但过滤操作实际上也是一个遍历的过程,其核心思想在于用 计算量小的遍历操作来代替计算量大的遍历操作,避免进行无效的复杂组装算 法计算。本文将介绍“搭搭看 中所设计的三种过滤算法,分别是圆锥投影过 滤、场景分割过滤、组装点匹配过滤。 5 2 2 1 圆锥投影过滤 由于“搭搭看 的算法是基于摄像机投影的,所以在摄像机投影区域之外 的物体都不可能参与到组装操作中来,这将成为过滤的一个条件。假设摄像机 是个点光源,在其作用下,场景中的任何物体都会有一个投影,而圆锥投影过 滤的思路则是利用这个投影条件进行判断,将不满足投影区域条件的物体过滤。 由于一般的物体形状并不规则,简单的计算投影会消耗过多的c p u 资源, 与过滤算法的初衷相悖,考虑到过滤操作本身是一个不精确的计算行为,所以 在投影过滤中,本文选择了计算最为简单的球形包围盒来进行投影计算,假设 每个积木块都具有一个最小的球形包围盒,则它在摄像机的投影下,在3 d 空间 中会形成一个空间圆锥,如图5 1 l 所示,当场景中其他包围盒与这个空间圆锥 有交集的时候便参与下一步算法计算,无交集则会被过滤。如此,接下来的问 题便简化成了一个空间圆锥与球是否相交的问题u 驯: 图5 1 l 圆锥投影过滤原理图 4 3 第五章组装操作与辅助功能设计 假设圆锥体的顶点为v ,准线单位向量为才,准线与母线的夹角为口,球体 球心为c ,半径为r 。现将原圆锥体以半径r 扩充,形成一个类圆锥体,但它 的顶部是一个扇形,为了计算方便,将其近似为一个新的圆锥体,其新的顶点 为矿,如图5 1 2 ( c ) 所示,两顶点之间的距离为 iv - v 。f = r s i n 8 ( 5 1 1 ) 再由 矿一v = y y i j ( 5 1 2 ) 得 矿= v 一( r s i n o ) j( 5 1 3 ) 判断球与圆锥是否相交便等价为判断球心c 是否在这个新的圆锥体内。假设 圆锥体外表面上有一点x ,它满足 j ( x 一矿) = x vic o s o( 5 1 4 ) 而在锥体外的点y 则满足 才( 】,一y 。) qy vlc o s l 9 ( 5 1 5 ) 将球心c 代入上式,得到球与圆锥没有交集的判断条件 么( c y 。) lc ylc o s 0 ( 5 1 6 ) 其中 矿= 矿一( r s i n o ) a ( 5 1 7 ) 第五章组装操作与辅助功能设计 ( a )( b )( c ) 图5 1 2 空间圆锥与球相交证明示意图 5 2 2 2 场景分割过滤 场景分割是计算机图形学中一个经典的加速算法,一般利用八叉树将场景 进行递归细分,树中的子节点对应于一个子场景,当子节点中含有目标物体时, 则在子节点中保存目标物体的指针m 1 ,下图是三维场景的一个八叉数表示: 图5 1 3 基于八叉数的场景分割 场景分割过滤也是投影过滤的一种,它的算法过程分为两部分: 1 场景分割 场景分割过程即是将场景递归细分的一个过程,理论上讲,它的细分程度, 4 5 第五章组装操作与辅助功能设计 或者说场景分割树的深度应该是越深越好,但场景树的过度细分会对接下来的 射线跟踪带来算法压力,所以应该取一个合理的深度值。由于“搭搭看 系统 的3 d 空间很大,但实际操作空间却可能很小,并且与其他场景分割应用场合不 一样的地方是,“搭搭看 系统中没有静态的物体,所有物体都可能被移动,考 虑到这两点,传统的场景分割策略并不太合适,于是本文提出了一种可变的场 景分割算法,根据当前积木块的位置范围来动态的对场景进行分割,这个将要 被分割的场景相当于一个大的包围盒,我们称之为分割包围盒,它的尺寸取决 于场景中所有积木的最大最小坐标,一旦场景积木的运动改变了这个尺寸的话, 分割包围盒将会被改变,场景将会重新被分割u 。 图5 1 4 “搭搭看”中的场景分割策略 判断当前物体是否包含在分割后的立方体内,我们仍然选择物体的a a b b 包围盒来代替复杂的具体形体进行分割计算,以提高场景分割的效率,这时, 分割操作便是寻找与对比物体包围盒的边界坐标,从而判断是否进行下一步分 割操作,直到每个子空间最多只能包含一个场景形体。 2 射线跟踪 场景分割的最终目的还是为了最后的射线跟踪操作,射线跟踪实际上是对 场景分割树的一个遍历过程,整个遍历与相交算法都是计算机图形学里的基本 算法,这里不再赘述。由于同一个物体可能被包含在多个子节点中,为了避免 对同一个物体的重复相交计算,正确的遍历顺序应该是先判断当前子节点中保 存的物体是否已经被射线相交,若否再进行相交判断。 场景分割过滤在功能上与圆锥投影过滤有一定的重复,但也有一定的区别, 第五章组装操作与辅助功能设计 因为圆锥投影过滤始终还是避免不了遍历操作,所以随着积木块的增多,算法 的耗时将也会线性增多,而场景分割过滤由于其景深几乎是确定的,所以随着 积木块的增多,其算法耗时虽然也会增加,但较前者会增加的“慢 一些。还 有很重要的一点就是场景分割是一种预处理,通常情况下并不发生在关键的组 装计算过程中,其耗时是程序可以忍受的。在效率上,理论上场景分割过滤要 比圆锥投影过滤要高一些,但圆锥投影过滤的优点在于原理简单,效果明显, 不需要像场景分割过滤算法那样需要进行复杂的算法管理。 5 2 2 3 属性过滤 圆锥投影过滤与场景分割过滤是对场景中的所有积木块进行过滤,而属性过 滤是在前面两个流程过后进行的单个积木块的内部过滤,属性过滤包含类型匹 配过滤与向量过滤两个小部分,在本文第四章规则库中讲到,每种积木块都具 有一定的组装属性,设积木块中所有的组装属性为全集u ,任何积木块的组装属 性集合为a ,有彳u ,由于只有相同的组装类型才能彼此组合,所以设积木l 的组装属性集合为s ,积木2 的组装属性集合s ,当s n & = g 时,积木将会 被过滤;向量过滤是运行在类型匹配过滤之后的另一种过滤方法,在虚拟组装 的过程中,两个物体的组装部分需要在一定的姿态条件下才能够组合,反映到 数据结构中,则是描述他们的向量需要满足一定的条件,对于一个面,这个向 量将是面的法向量;对于一个轴,这个向量将是它的方向向量。由于“搭搭看 的基本操作是一种吸附式的操作,所以向量条件是两向量的一个夹角范围,“搭 搭看 中定义两向量夹角4 5 。为临界角度,假设积木a 某中属性的向量为圪, 积木b 对应属性的向量为k ,则当向量满足以下条件时,这个属性将会被过滤。 一生2 巧巧生2 ( 5 1 8 ) 4 7 第五章组装操作与辅助功能设计 ( a ) 面向量夹角范围( b ) 轴向量夹角范围 图5 1 5 面与轴的属性过滤 5 2 3 算法实现流程 “搭搭看”中搭建算法的完整算法流程包括了过滤算法、排序算法、吸附 算法、碰撞算法等等在内的所有与组装相关的算法,它从响应用户的输入开始, 到反馈结果给用户结束,贯穿在整个用户的操作过程。 图5 1 6 算法执行顺序 由于操作的不同,需要对一些算法单独考虑。对于单积木块的组装算法, 只需考虑鼠标当前操作的积木块的一些信息,而本文所实现的算法需要考虑组 合积木块的情况,与一般的虚拟操作不太一样的是,一般的虚拟操作或直接操 作单物体,或操作一些互不相关的多物体移动,而在现实积木操作中,只有组 合的积木块才能作为一个整体被操作,操作一个组合的积木块与一堆散列的积 木块在算法实现上可以相同,但考虑到组合积木块在数据结构上的特性,本文 为此提出了一些特定的算法策略,从而提高算法的运行效率,这些算法策略具 体包括: 1 】设计一个组合积木块类嵋,将其看作一个整体,它具有单个积木块的所 有属性,其包围盒尺寸可以由它包含的所有单个积木块包围盒在三个坐标轴方 向上极值所确定,对多积木块的所有操作都通过这个整体去分配执行。 笙亘童望茎塑堡皇堕壁垫丝堡生 _ _ _ _ i _ _ _ l - l - _ _ - - _ _ _ _ _ - _ - _ 一一 2 1 过滤算法先对组合积木块计算再细分到单个积木。 【3 1 检测碰撞时,不检测组合积木块之间的碰撞。 f 4 1 如果两个积木之间内部具有搭建关系,则它们在空间位置上会有更多的 相似性,在检测碰撞与组装上,将根据搭建关系设置被检测积木的优先级。 在设计算法流程时,可以将单积木看作是多积木操作的一种特殊情况,所 以并不需对其单独考虑。 “搭搭看 的组装算法流程图如下: 图5 1 7 “搭搭看”组装算法流程 , 4 9 第五章组装操作与辅助功能设计 组装算法的第一步是过滤算法,负责将散列在场景中的静止积木块挑选出 来,挑选出来的积木块称之为候选积木块,候选积木块是能通过第一批过滤的 积木块,然后在将候选积木块进行排序操作,准备进行下一轮过滤与组装操作, 候选积木块的排序将以积木离摄像机的距离作为排序因子,离摄像机近的积木 将排在前列,为了让排序结果具有更好的平均性能,这里我们采用了快速排序 法: 考虑到积木的吸附策略是投影吸附,排序操作可以让离摄像机近的积木具 有更高的搭建优先级,这么做的优点在于在同时存在几种搭建可能性的时候, 首选吸附到离摄像机近的积木块处,这从观察者的视角来看,将更符合观察者 的操作习惯。 积木块排序完毕后,需要将积木块依次进行搭建属性的投影吸附操作,按 照面线点的顺序进行过滤与吸附,若所有属性都不能被吸附的话则进行下一个 积木的检查,当有吸附操作发生时,此时将积木块“尝试”吸附过去,所谓的 “尝试 吸附指的是并不真正的将积木块最终进行移动,而是先试着移动过去, 一旦吸附的结果会让积木块产生碰撞,则此次“尝试”吸附失败,积木将回到 原来的位置,并进行下一轮吸附检查。若“尝试 吸附后并没有发生碰撞干涉, 说明此次吸附可以被接受,此时,在新的姿态位置更新被吸附积木块的搭建属 性。至此,这一轮组装算法结束,属性吸附操作的伪代码如下: 第五章组装操作与辅助功能设计 第三节作品保存与加载 作品的保存与加载是虚拟组装平台下的一个基本辅助要求,用户可以利用 这个功能保存一份未完成的工作,并且在必要的时候可以对其进行修改。 5 3 1 保存文件格式的设计 在虚拟组装平台下,对文件的保存与加载的功能有两个最基本的要求 一真实性、二是实现效率。平台需要将当前场景的最真实的信息保存到文件中, 加载文件后,所保存场景能被还原。另一方面,考虑到用户的等待忍耐时间, 当需要保存的场景比较复杂的时候,保存场景与加载文件的时间不允许过长。 以下列举出了“搭搭看中的文件保存功能需要保存的数据: 1 积木块索引号。它保存了当前积木块在保存积木块顺序序列中的索引, 用于辅助确定组装情况。 2 积木块d 号。它标示了积木块的种类,用于加载时确定加载积木块的 形体数据。 3 积木块材质。它保存积木块的颜色与透明度等信息。 4 积木块的旋转矩阵。它保存积木块的位置与姿态信息。 5 积木块的组装情况。它保存积木块的组装情况,标示当前积木与哪些积 木有组装的关系。 在“搭搭看 平台设计的保存文件数据结构中,一个数据项具有唯一的一 个索引号,每个索引号下都带有几种不同的属性,积木块组装子属性又需要考 虑每种小类型的所有组装实例,这是一个典型的树形结构,仍然可以用x m l 文 件的格式去保存文件。 5 1 第五章组装操作与辅助功能设计 “搭搭看 中的保存文件格式如下所示: 5 3 2 作品保存与加载的实现 在需要保存文件时,主程序要去遍历场景中所有物体的信息,并将这些信 息以x m l 格式填充到其中的每一个小项中。考虑到安全问题,保存的文件仍然 需要加密,所以在保存文件时,需要先把x m l 信息作为文件流保存在内存中, 再通过加密算法,将其加密后写入到磁盘,“搭搭看将以后缀名为d d k 的格式 保存。 由于保存的文件是一个加密的文件,所以在作品加载前,要先对其进行解 密,为了防止不可避免的对保存文件进行的误操作而带来的文件内容修改,解 密后需要对文件进行一次可靠性验证,通过验证后的x m l 文件将以文件流的格 式保存在内存当中,再通过x m l 操作组件读取文件流中的数据,再保存到程序 第五章组装操作与辅助功能设计 中,处理好当前场景后,还原文件中保存的场景信息。 “搭搭看 的文件保存加载的具体流程图如下: 保存文件开始)( 加载文件开始 选择路径与文件名 保存) q 礼内容 翌 篇 保存文件结束 选择要加载的文件 件存参 查 l解密文件 冬完多锺 童 读取) 国艮内容 。+ 一 i 扣更新场景 加载文件结束 图5 1 8 “搭搭看文件保存加载流程图 第四节回放功能 回放功能是虚拟组装平台下的一个很重要的辅助功能,它重现了用户的操 作过程,能帮助用户对以前的操作流程进行回顾与检查,而且它也是作品保存 与加载功能的一个扩充,通过回放功能的实现,能更好的实现对作品的共享。 5 4 1 回放功能的设计与实现 要设计回放功能的数据结构,首先要确定回放效果的策略,在一般主流软 件的做法中,大概可分为两大类设计策略: 1 基于操作流程的算法策略 这种策略的优点在于能最全面的记录下用户所有的操作与回放流程,它也 可分为两种记录模式,一种是记录场景中的所有动作,像录制屏幕一样以一个 间隔时间为单位对场景全部进行记录,回放时,顺着时间轴对流程进行回放; 第五章组装操作与辅助功能设计 另一种是记录用户的关键操作,在操作i o 处进行拦截记录,保存动作信息与当 前操作的时间点信息,在回放时,每到达一个时间点便对场景发送记录的i o 操 作,场景对操作进行响应,相当于重新模拟了一遍用户操作。 2 基于操作结果的算法策略 基于操作结果的算法并不侧重于对原来场景的完全重现,而是注重对操作 结果的记录,在一个虚拟组装操作中,它可以分为: 增加物体操作结果 删除物体操作结果 删除所有物体操作结果 改变物体位姿操作结果 摄像机操作结果 操作结果算法将忽略掉所有的中间操作细节,只保存最终的操作结果,待 到回放时,只对这些结果进行一一重现。 这两种算法策略都有各自的优缺点,需要根据实际情况进行选择,“搭搭看” 采用了基于操作结果的算法策略,因为虽然基于操作流程的算法策略可以最完 整的重现当时的操作过程,但保存操作流程的代价过大,且有太多的冗余信息。 而基于操作结果的策略对操作结果进行重现,可以在保证较小的保存代价的同 时,完全满足用户操作的需求。 5 4 2 记录与加载回放文件 5 42l 记录文件 在记录操作之前,需要定义相应的数据结构,虽然每种操作都不一样,但 为了防止数据结构出现冗余,本文仍然定义同一种数据结构去保存所有的操作 结果,观察到不管是哪种操作结果,都可以被三种数据所描述,即操作的类型 ( t y p e ) 、操作物体的索引号( i n d e x ) 与操作的数据( d a t a ) ,如下图所示: 图5 1 9 回放文件数据结构 操作类型指示了何种类型的操作,指示了场景中的积木,由于可能是对多 积木进行操作,所以索引号可以不止一个,而数据区保存了具体的操作数据, 第五章组装操作与辅助功能设计 它是由操作类型决定的。由于记录文件是一个顺序操作,所以将它们保存在一 个向量( v e c t o r ) q b 。 对于过程的记录,都是基于一些回调函数来完成的,用户的操作结果会产 生一系列事件,回调函数将对这些事件进行函数响应,然后将记录文件的功能 函数加入到其中,从而实现了对回放的记录,各函数功能详见表5 1 : 表5 1 回放功能记录函数 操作子躏数名同调函数名触发条件 增加积木a d d b r i c k om o u s e m o v c c a l l b a c k ( ) 场景中拖拽进一积木块 摄像机操作 s e t c a m e r a om o u s e m o v e c a l l b a c k o , 鼠标操作改变摄像机 m o u s e b u t t o n c a l l b a c k 0 删除积木 d e l b r i c k 0 k e y b o a r d c a l l b a c k 0 按键盘d e l e t e 键 删除所有积木 d e l a l l b r i c k s 0k e y b o a r d c a l l b a c k o 按键盘d e l e t e 键并删 除所有积木 改变物体位姿 c h a n g e t r a n s f o r m 0 m o v e f i n i s h e d c a l l b a c k 0 鼠标操作积木块结束 5 4 2 2 回放文件 “搭搭看 为整个平台定义了几种操作模式,一般状态下,“搭搭看 运行 在搭建模式下,在搭建积木时,或者是导入了d d k 文件后,其回放信息会被自 动的保存在内存中,一旦用户发送命令,平台便自动的切换到回放模式下,从 而进行回放操作。 “搭搭看”的回放操作是基于记录文件时所产生的回放向量,一旦回放开 始,“搭搭看 便开始顺序去读这个向量,通过对数据结构的头字节( t y p e ) 的判断, 将会对数据区( d a t a ) 进行不同的解析,再对指定索弓l ( i n d e x ) 的积木进行响应,从 而实现回放功能。 “搭搭看 的文件记录回放的具体流程图如下: 5 5 第五章组装操作与辅助功能设计 5 5 1 网络传输架构 图5 2 0 “搭搭看”文件记录回放流程图 第五节网络支持 “搭搭看 引入网络环境是为了增加平台的趣味性与竞争性,让用户在互 联网上同时使用本平台。此外,通过互联网,可以对“搭搭看很好的起到推 广作用。 平台的网络实现需要服务器的支持,项目组开发的“青少年智能机器人体 验平台 是一个支持多用户、多客户端的网络应用平台,此平台可以为其挂接 下的客户端提供网络支持,“搭搭看即是体验平台支持下的客户端之一。网络 平台采用当今流行的“大厅房间桌面网络体系结构,用户需要依次登陆大厅、 选择房间和桌面进行体验,当所有用户准备就绪时,主机控制开始,本地的“搭 搭看 程序以参数启动的方式被启动,从而实现联机运行。平台的网络架构图 如下图所示: 第五章组装操作与辅助功能设计 数据库 图5 2 1 网络平台架构图 在网络平台下,客户端进入房间服务器连机成功之后的网络通信依赖于体 验平台提供的通信组件,服务器提供的n k t yt c p c i i e n t d l l 文件包含客户端所 需要的接收数据与发送数据组件,根据组件的设计思想,通信组件只提供给客 户端最基本的通信函数接口,客户端针对接口编程,不需要关心其内部的实现 细节。服务器给客户端提供的接口函数如下: 发送组件的接口函数为: i n l i n el o n gi n k t y _ c l i e n t c o m m :l n i t l o n ga _ p l a y e r n u m ,l o n ga _ p r o c e s s l d ,l o n g a _ m y p l a y e r l d ,s a f e a r r a y a _ p l a y e r l n f o ) i n l i n el o n gi n k t y _ c l i e n t c o m m :s e n d d a t a ( i o n ga - - a c t i o n t y p e ,s a f e a r r a y ad a t a ) 接收组件的接口函数为: 在对组件进行初始化函数c o c r e a t e l n s t a n c e 初始化以后,便可使用这两个组 件进行通信。 i n l i n el o n gi n k t y _ c l i e n t c o m m :r e c v d a t a ( 1 0 n g 搴a c t i o n t y p e ,l o n g 木a _ p l a y e r l d , s a f e a r r a y 事ad a t a ) 第五章组装操作与辅助功能设计 5 5 2 客户端网络传输策略 在“搭搭看平台中,网络部分的功能分为两大块,一是用户的即时通信; 二是用户可以看到互相之间的虚拟场景,我们称之为偷窥功能。“搭搭看 最多 支持每四个用户在一起同时进行操作,用户可以通过平台界面中的偷窥区观看 其他三位用户的操作情况。 由于聊天功能相对简单,也比较普遍,所以本文不详述。对于偷窥功能,目 的是将其他三位用户的行为通过网络传输过来,考虑到网络的通信带宽和本地 场景的渲染压力,不可能也不必要将对方的所有真实动作数据真实的传送过来 在本地重现,在“搭搭看 中所传输的数据是一些关键动作数据。需要传输的 关键动作分为: 添加积木块动作。 删除积木块动作。 删除所有积木块动作。 改变积木块位姿动作。 添加和删除积木是用户操作的两个基本操作,通过索引机制进行控制,以使 两边的场景同步。删除所有积木块并不与删除部分积木块的功能相重合,删除 部分积木与删除所有积木的网络传输的结构体如下所示: 当场景中的积木块很多的若需要删除所有积木,如果用单个删除的策略,需 要耗费太多的时间,而删除所有积木块消息动作正是为解决这个问题所设计的, 此时只用发送一个j a g d e l 甜l 结构体就可以代替传输多个j a g d d 结构体。 改变积木块位姿动作的网络传输结构体如下: 第五章组装操作与辅助功能设计 从改变积木块位姿动作的数据结构中可以看到,位姿改变动作将会产生较多 的网络传输数据,此时需要考虑到网络实际传送带宽的情况,当操作大量积木 块整体移动时,简单的单个积木传输策略会很快将带宽占满,同时迅速增加了 服务器的压力。为了解决这个问题,本文采用了整体式的传输方法,如图5 2 2 所示,单个积木块传输策略需要将每一个积木块信息封装成包再发送出去,而 整体式的传输策略将多积木块看成一个整体,只传输整体的旋转矩阵变化与所有 参与变化的积木块索引,多积木块中的具体积木的姿态变化将在接收端的本地 进行计算。 单个积木 整体式传 图5 2 2 “搭搭看”网络传输策略 在传输策略确定下来后,仍有一个问题需要考虑,“搭搭看 定义的一个数 据包的最大长度为l k ,当实际操作的积木太多时,一个数据包往往传输不了所 有数据,所以在传输上述动作数据时,还需要考虑拆包的问题。 第六章总结与展望 第六章总结与展望 第一节工作总结 本文实现了模拟l e g o 积木的三维搭建,在此基础上开发出了具有自主知 识产权的“搭搭看”v i 0 版程序,在开发“搭搭看 v 1 0 的过程当中,我们解 决了在开发虚拟组装平台时所会遇到的一些困难,并且提出了模块化的开发思 路,本文所实现的开发流程对一般虚拟组装平台的开发能起到一定的借鉴作用。 截止到目前,“搭搭看”v 1 0 版已经实现并投入了试运行,在操作方面,v i 0 版提供了一种友好的搭建操作方式;在积木方面,有9 3 块不同的积木可供选择, 而在虚拟场景中可以支持上千个积木的搭建;在辅助功能中,不仅提供了作品 与作品信息的加载与保存,而且还提供了回放功能,从而能让作品动态的复现。 此外平台还带有截图功能;网络功能则是为了增加“搭搭看”的娱乐性与竞争 性而设计的。至此,“搭搭看v 1 0 版已经具有了一个完整虚拟组装平台所应该 具有的基本功能。 在软件开发的规范化管理方面,为了规范开发过程与提高开发效率,我们 采用了模块化的开发理念,而模块化的管理即是不同开发人员的管理,随着“搭 搭看开发的不断深入,开发人员的工作分工越来越明确,通过模块化的分类, 我们将开发人员的工作分为3 d 开发、图形几何计算、模型文件仿真与测试、碰 撞检测、网络开发等几个工作点,项目负责人先把软件框架制定好,通过与其 他模块开发人员的交互,将模块的内容添加到主程序中嵋“。在开发过程中,团 队同时设有专门的软件测试人员,软件测试人员定时为测试结果形成文档,交 与开发人员参考。这种规范的软件管理会让开发人员之间的工作内容耦合度降 低,从而更能提高程序的鲁棒性比“。 “搭搭看”的开发是一个不断的完善过程,在版本的管理当中,“搭搭看 还经历了一个过渡版,通过对其不断的进行修改与完善,才形成了现在功能相 对比较完善的v 1 0 版,这些完善的工作具体包括: 1 软件运行效率的提高。在模型文件方面,通过任意改变模型文件的顶点 序,从而将原来的双面渲染改为现在的单面渲染,减轻了程序的渲染压力,提 高了程序运行效率;在组装算法方面,我们引入了各种过滤算法,而在最耗资 第六章总结与展望 源的碰撞检测这块,也阅读了大量的参考文献,采用的碰撞包围盒分解与碰撞 算法效率都越来越高。 2 完善开发引擎的功能。由于“搭搭看 使用的3 d 开发引擎是一个上层 的开发包,内部封装了许多现成的功能,在程序的初始开发之际,的确给软件 的开发带来了很多的方便,但随着开发的推进,引擎所提供的功能在效率上已 经越来越不满足程序实际的需求,所以我们完善和取代了引擎提供的许多功能, 如所有的3 d 操作等等。 3 程序b u g 的修改。在开发人员开发的同时,团队的测试人员也在对“搭 搭看 在做各种测试,通过反馈,我们修改了程序中存在的许多b u g ,并在用户 试用的反馈中,修改了一些不方便用户操作的地方。 4 软件商业规范化。在实现了v 1 0 版的大多数功能时,我们对软件进行了 一系列的商业规范化操作,其中包括对关键文件的加密、对资源文件的封装和 软件的商业注册功能。 第二节工作展望 6 2 13 d 引擎的选择 o p e ni n v e n t o r 是s g i 公司开发的基于o p e n g l 的面向对象三维图形软件开 发包,它本身用c + + 书写,但是可用 在纯c 程序中。通过对o p e n g l 的封 装,o p e ni n v e n t o r 有一套强大的图形 开发库,库中有大量的对象模块,开发 人员可以任意的使用,修改和扩展这些 模块。o p e ni n v e n t o r 具有平台无关性, 它可以在m i c r o s o f tw i n d o w $ 、u n i x 、 l i n u x 等多种操作系统中使

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论