相关热词搜索：
碰撞检测处理论文
碰撞检测处理论文 摘要:结合实现静态虚拟穿衣中的实际问题,详细地介绍了基于弹簧质点模 型的织物变形模型和基于ＡＡＢＢ层次包围盒的碰撞检测算法。借助层次空间分 解法的思想,将缝合衣片的相对位置同人模自身的结构信息相结合,灵活地构造人 模ＡＡＢＢ树,减少了不相交元素的碰撞检测次数,从而提高了算法的效率。最后 还给出了实现整个虚拟穿衣过程的具体步骤。关键词:织物变形仿真;弹簧质点模 型;碰撞检测;空间分解法;层次包围盒法;显式欧拉方法 1前言随着计算机技术和人类社会经济的发展,对于纺织服装业ＣＡＤ/Ｃ ＡＭ的应用要求也越来越高,二维服装ＣＡＤ系统已经不能满足要求,人们迫切希 望借助计算机完成一些更加实用的三维功能。若能直接将二维服装ＣＡＤ系统设 计的衣片,在计算机上真实地模拟出穿在人体上的效果,便可以帮助设计师直接在 计算机上进行着装效果检查、服装裁剪片缝合检查等工作。这样就可大大提高服 装从设计阶段到生产阶段间的效率,具有非常重要的实用价值。要通过计算机实 现这一功能,有两个关键的问题必须解决:1)建立合适的织物变形模型;2)选择高效 而实用的碰撞检测算法。研究织物变形仿真的方法通常分为三类:几何的、物理的和混合的(几何和 物理方法的混合)。纯几何的造型方法很难反映织物的物理特性,因此基于物理的 方法研究,近年来已占据了主导地位。在织物变形物理仿真模型中[1],按比拟织物 结构的方式又可分为两大类:1)离散质点型模型:比较典型的有Ｆｅｙｎｍａ等建 立的质点网格模型、Ｂｒｅｅｎ等建立的粒子模型和ＸＰｒｏｖｏｔ等建立的弹 簧质点模型;2)连续介质型模型:比较典型的有Ｔｅｒｚｏｐｏｕｌｏｓ等建立的 弹性变型模型、Ｌｉｌｉｎｇ等建立的空气动力模型、Ａｏｎｏ建立的波传播模 型、Ｃｏｌｌｉｅｒ等建立的有限元模型等。
以上的织物变形物理仿真模型,由于其建模的原理和方法不尽相同,因此, 它们适用于不同的应用场合有其各自的优缺点。
我们结合设计虚拟穿衣功能的实际,认为ＸＰｒｏｖｏｔ所建立的弹簧质 点模型,模型简单,易于计算机实现,在模拟衣片复杂的动态变形过程时,能够取得 比较真实的模拟效果和较快的模拟速度。
在模拟三维服装穿在人体上的真实效果时,会遇到大量的碰撞现象:衣片同 人模之间以及衣片自身间的一种相互渗透和穿越。只有很好地解决了渗透和穿越的问题,才能逼真地完成虚拟穿衣的模拟过程。因此,碰撞检测是整个模拟过程的 关键。碰撞检测非常耗时,最简单的碰撞检测算法是对两个碰撞体中的所有基本 几何元素(通常为三角形)进行两两相交测试。
现有的碰撞检测算法大致可划分为两大类:空间分解法(ｓｐａｃｅｄｅｃ ｏｍｐｏｓｉｔｉｏｎ),和层次包围盒法(ｈｉｅｒａｒｃｈｉｃａｌｂｏｕｎ ｄｉｎｇｖｏｌｕｍｅｓ)。前者是将整个虚拟空间划分成相等体积的小单元格, 只对占据同一单元格或相邻单元格的几何对象进行相交测试。比较典型的方法有 八叉树和ＢＳＰ树。层次包围盒法的核心思想是利用体积略大而几何特性简单的 包围盒将复杂几何对象包裹起来,在进行碰撞检测时,首先进行包围盒之间相交测 试,只有包围盒相交时,才对其所包裹的对象,做进一步求交计算。在构造碰撞体的 包围盒时,若引入树状层次结构,可快速剔除不发生碰撞的元素,减少大量不必要 的相交测试,从而提高碰撞检测效率。比较典型的包围盒类型有沿坐标轴的包围 盒ＡＡＢＢ(ａｘｉｓａｌｉｇｎｅｄｂｏｕｎｄｉｎｇｂｏｘｅｓ),包围球(ｓ ｐｈｅｒｅ),方向包围盒ＯＢＢ(ｏｒｉｅｎｔｅｄｂｏｕｎｄｉｎｇｂｏｘ)等。
在本文中,我们充分利用了ＡＡＢＢ层次包围盒法的优势,同时在构建静态 人模的ＡＡＢＢ树时,又借助层次空间分解法中子空间在空间排列上的有序性和 相关性的思想,将缝合衣片的相对位置同人模自身的结构信息相结合,灵活地构造 人模ＡＡＢＢ树,这样减少了需相交测试的元素,从而提高了碰撞检测的效率。
2织物的变形模型 2.1织物变形模型的描述 我们建立的织物变形模型是以ＸＰｒｏｖｏｔ的弹簧质点模型作为基础, 将织物设想为一个个质点集合,质点间相互关系归结为质点间的弹簧作用。其中 弹簧分为三类:结构弹簧、剪切弹簧和弯曲弹簧,具体构成如图1所示。图1织物模 型离散成规则网格 1)结构弹簧:在质点Ｐｉｊ和Ｐｉ+1,ｊ间,以及Ｐｉｊ和Ｐｉ,ｊ+1间的弹 簧为结构弹簧,结构弹簧是为了保持质点间初始状态时的距离。
2)剪切弹簧:在质点Ｐｉｊ和Ｐｉ+1,ｊ+1间,以及Ｐｉ+1,ｊ和Ｐｉ,ｊ+1间 的弹簧为剪切弹簧。剪切弹簧是为了防止织物在自身平面过渡和不真实的变形, 而给织物的一个剪切刚性。3)弯曲弹簧:在质点Ｐｉｊ和Ｐｉ+2,ｊ间,以及Ｐｉｊ和Ｐｉ,ｊ+2间的弹簧为弯曲弹簧,弯曲弹簧是为了防止织物弯曲。2.2质点的位移 在缝合衣片过程中,衣片上所有质点因受力而产生一定的位移,质点位移我们选用 Ｎｏｗｔｏｎ运动定律来描述:Ｆ外力(ｉ,ｊ)+Ｆ内力(ｉ,ｊ)=ｍａ(ｉ,ｊ)其中,ｍ 是质点Ｐ(ｉ,ｊ)的质量。在本文中,我们假定布料是各向均质的,因此,质点的质量 可由衣片总质量除以质点总数得到,ａ(ｉ,ｊ)是该点加速度,Ｆ外力(ｉ,ｊ)是该点 所受的外力,Ｆ内力(ｉ,ｊ)是该点所受的内力。为了简化模型,在我们三维服装Ｃ ＡＤ系统中,只考虑两种外力:缝合力和重力。可以用以下公式来表示:Ｆ外力(ｉ, ｊ)=Ｆ缝合力(ｉ,ｊ)+Ｆ重力(ｉ,ｊ) 在衣片缝合过程中,为了将不同的衣片缝在一起,我们在衣片对应缝合边上 加载缝合力。在模型中,缝合力被定义成对应缝合点之间距离的线性函数。对两 个缝合点ｐｉ,ｊ和ｑｉ,ｊ间的缝合力,可以按如下公式计算:Ｆ缝合力(ｉ,ｊ)=Ｃ ｓＤｉｓ(ｐｉ,ｊ,ｑｉ,ｊ)Ｎｐｉ,ｊ-ｑｉ,ｊ式中Ｃｓ为缝合力系数,该系数与织 物的缝合性能有关,通常,较难变形的布料采用较大的缝合力系数;Ｄｉｓ(ｐｉ,ｊ, ｑｉ,ｊ)表示两缝合点ｐｉ,ｊ和ｑｉ,ｊ间的距离;Ｎｐｉ,ｊ-ｑｉ,ｊ表示从ｐｉ, ｊ点指向ｑｉ,ｊ点的单位方向矢量。为了获得较真实的仿真效果,我们在变形模 型中考虑了衣片所受的重力。质点所受的重力可按如下公式计算:Ｆ重力(ｉ,ｊ)= ｍｉ,ｊｇ式中ｍｉ,ｊ为质点ｐｉ,ｊ的质量。在弹簧质点模型中,唯一考虑的弹性 内力是弹簧的弹性变形力,由于采用的是理想的弹簧质点系统,可以利用胡克(Ｈ ｏｏｋｅ)定律来计算弹簧的弹性变形力:Ｆ内力(ｉ,ｊ)=-∑(ｋ,ｌ)∈Ｒｋ(Ｐｉ, ｊＰｋ,ｌ-‖Ｐｉ,ｊＰｋ,ｌ‖0Ｐｉ,ｊＰｋ,ｌ‖Ｐｉ,ｊＰｋ,ｌ‖)其中,ｋ是弹簧的弹 性变形系数,Ｒ是Ｐ(ｉ,ｊ)邻点的集合,‖Ｐｉ,ｊＰｋ,ｌ‖0表示质点Ｐ(ｉ,ｊ)与质 点Ｐ(ｋ,ｌ)之间的原始距离,弹簧的弹性变形系数ｋ可以谰菟选用织物的材料性 能参数曲线确定/P 2.3织物变形模型的求解我们选择显式欧拉方法来求解织物变形模型。求 解公式如下:ａｉ,ｊ(ｔ+△ｔ)=1ｍｉ,ｊＦｉ,ｊ(ｔ)Ｖｉ,ｊ(ｔ+△ｔ)=Ｖｉ,ｊ (ｔ)+△ｔａｉ,ｊ(ｔ+△ｔ)Ｐｉ,ｊ(ｔ+△ｔ)=Ｐｉ,ｊ(ｔ)+△ｔＶｉ,ｊ(ｔ+△ｔ)其 中,Ｆｉ,ｊ是质点Ｐ(ｉ,ｊ)所受所有力的合力,ｍｉ,ｊ(ｔ)是质点Ｐ(ｉ,ｊ)的质量, ａｉ,ｊ(ｔ)、Ｖｉ,ｊ(ｔ)和Ｐｉ,ｊ(ｔ)分别是质点Ｐ(ｉ,ｊ)在时间ｔ的加速度, 速度和位置。△ｔ是系统选定的时间步长。
3基于ＡＡＢＢ树层次包围盒的碰撞检测 3.1建立ＡＡＢＢ树一个碰撞体的ＡＡＢＢ被定义为包含该碰撞体,且边平 行于坐标轴的最小六面体。因此,描述一个ＡＡＢＢ,仅需六个标量。在构造ＡＡＢＢ包围盒时,需沿着碰撞体局部坐标系统的轴向(Ｘ,Ｙ,Ｚ)来构造,所以所有的 ＡＡＢＢ包围盒具有一致的方向。
ＡＡＢＢ树是基于ＡＡＢＢ的二叉树,按照由上至下的递归细分方式构造 生成的。在每一次递归过程中,要求取最小的ＡＡＢＢ,需沿所选择的剖分面将碰 撞体分为正负两半,并将所对应的原始几何元素(如三角面)分别归属正、负两边, 整个递归过程类似于空间二叉剖分,只是每次剖分的对象是ＡＡＢＢ,而不是空间 区域。递归细分一直要进行到每一个叶子节点只包容一个原始几何元素为止,所 以具有ｎ个原始几何元素的ＡＡＢＢ树具有ｎ-1个非叶子节点和ｎ个叶子节点。
对于剖分面的选择,在本文中,选择垂直ＡＡＢＢ的最长轴,且平分该轴的平面。经 试验证明,这种方式,在大多数情况下的算法复杂度仅为Ｏ(ｎｌｏｇｎ),较其它的 剖分面选择方法有了极大的提高。至于原始几何元素的归属则应依据几何元素的 重心Ｐ在最长轴上的投影坐标。若投影坐标大于剖分面的坐标(ｍｉｄ),则在剖分 面的正向,否则在负向,如图2所示。图2三角面归属负区域,因为其质心投影坐标小 于剖分面的基准坐标 3.2ＡＡＢＢ的相交判断ＡＡＢＢ间的相交测试比较简单,两个ＡＡＢＢ相 交当且仅当它们在三个坐标轴上的投影区间均相交。通过投影,我们即将三维求 交问题转化为一维求交问题。而对一维求交问题,我们则采用ＳＡＴ(Ｓｅｐａｒ ａｔｉｎｇＡｘｅｓＴｅｓｔ)[2]法。因ＳＡＴ无需求交计算,只需比较两个包围 盒分别在三个轴向上投影的重叠情况,即可得出相交测试结果,非常简单。现以在 一个轴向上的投影情况为例说明:图3ＡＡＢＢｓ在Ｘ轴向相交判断。
设Ａ,Ｂ为两包围盒,Ｘ为投影轴,ＣＡ,ＣＢ分别为Ａ,Ｂ的中心点,ＰＡ,Ｐ Ｂ为点ＣＡ,ＣＢ在Ｘ上的投影。ＲＡ,ＲＢ分别为包围盒Ａ,Ｂ在Ｘ上的投影。若 ＲＡ+ＲＢ ＰＡＰＢ,(如图3所示)则在轴向Ｘ上Ａ和Ｂ不相交,反之在轴向Ｘ上Ａ和 Ｂ邻接或相53第5期高成英等:虚拟穿衣中织物模型的建立和碰撞检测的处理交。
当包围盒Ａ,Ｂ在三条轴向上的投影均相交时,则Ａ,Ｂ相交。定义ＡＡＢＢ的六个 最大最小值分别确定了它在三个坐标轴上的投影区间,因此ＡＡＢＢ间的相交测 试最多只需六次比较运算,非常简单快速。
3.3ＡＡＢＢ树的更新当衣片移动、旋转后,需要对ＡＡＢＢ进行更新,根据 定义ＡＡＢＢ的6个最大最小值的组合,可以得到ＡＡＢＢ的8个顶点,对这8个顶 点进行相应的旋转和平移变化,并根据变化后的顶点计算新的ＡＡＢＢ。当衣片发生变形时,需要重新计算ＡＡＢＢ树中发生变形了的叶结点的ＡＡＢＢ,再利用 变形叶节点的新ＡＡＢＢ来重新计算它们父节点的ＡＡＢＢ。这种计算必须严格 按照从下到上的方式进行。父节点ＡＡＢＢ的具体求法为:令(Ｘｍａｘ1,Ｘｍｉ ｎ1,Ｙｍａｘ1,Ｙｍｉｎ1,Ｚｍａｘ1,Ｚｍｉｎ1)和(Ｘｍａｘ2,Ｘｍｉｎ2,Ｙｍ ａｘ2,Ｙｍｉｎ2,Ｚｍａｘ2,Ｚｍｉｎ2)分别是两个变形叶结点的ＡＡＢＢ,则父 结点的ＡＡＢＢ即为(ｍａｘ(Ｘｍａｘ1,Ｘｍａｘ2),ｍｉｎ(Ｘｍｉｎ1,Ｘｍｉｎ 2),ｍａｘ(Ｙｍａｘ1,Ｙｍａｘ2),ｍｉｎ(Ｙｍｉｎ1,Ｙｍｉｎ2),ｍａｘ(Ｚｍａ ｘ1,Ｚｍａｘ2),ｍｉｎ(Ｚｍｉｎ1,Ｚｍｉｎ2),只需6次比较运算就完成一个结点 的更新,其效率远远高于重新构造ＡＡＢＢ包围盒树。
3.4基于ＡＡＢＢ树的碰撞检测算法基于ＡＡＢＢ树碰撞检测算法的核心 是通过有效地遍历这两棵树,以确定在当前位置下,两个碰撞体的某些部分是否发 生碰撞,这是一个双重递归遍历的过程。算法描述如下:ｓｔｅｐ1：分别为人模和 衣片构造ＡＡＢＢ树。ｓｔｅｐ2：人模的ＡＡＢＢ树的根结点遍历衣片的ＡＡ ＢＢ树。如果发现人模ＡＡＢＢ树的根结点的包围盒与衣片ＡＡＢＢ树内部结点 的包围盒不相交，则停止向下遍历；
如果遍历能到达衣片ＡＡＢＢ树的叶节点， 再用该叶节点遍历人模ＡＡＢＢ树。如果能到达人模ＡＡＢＢ树的叶节点，则进 一步进行基本几何元素间的相交测试。ｓｔｅｐ3：检测基本几何元素间是否相 交。3.5自碰撞检测在衣片缝合过程中,除了衣片同人模之间的碰撞外,由于衣片的 动态变形,使得衣片与衣片自身间也有碰撞现象,因此必须进行进一步的自相交检 测。在系统设计中,我们利用三角形表面曲率来简化计算。当邻近三角形法线的 夹角较小时,它们不可能发生碰撞,只有当夹角超过阈值,才有可能碰撞。我们为每 个三角形建立它的临近三角形列表,通过判断每个三角形的所有邻近区域的三角 形表面曲率,来排除大部分不可能相交的情况,从而简化了计算。
4虚拟穿衣的具体实现步骤 (1)读入二维服装ＣＡＤ系统设计的衣片 (2)选择所有需要缝合衣片的对应的缝合边 (3)将二维衣片离散并形成初始的弹簧质点系统ａ)将衣片离散成规则四边 域网格,再将四边域网格的对角线相连,形成规则三角形网格的弹簧质点系统。三 角形的顶点形成质点,三角形的边形成相应的弹簧。衣片的三角化,正是为方便地 建立衣片的ＡＡＢＢ树;ｂ)按质点间的相应关系,加入各种弹力。在离散衣片时, 需特别注意的是在(2)中所选择的对应缝合边的长度一定要相等,且当衣片离散化时,在对应缝合边上的原始几何元素(这里为三角形)的个数也应相同。若在(2)中所 选择的对应缝合边长度不等,或原始几何元素个数不同时,系统将需做一些预处 理:将其中一条缝合边的所有信息删除,将另一条缝合边的相应信息赋给它。
(4)将衣片交互式地放置在人体模型附近的初始位置在该步骤中,首先,给 每一缝合衣片赋一个别名(系统自定义的标准别名:左前片,右前片,左后片,右后片 等),根据每一衣片的别名,衣片被自动地放置在人体模型附近的相应初始位置上。
(5)分别为人模和衣片建立ＡＡＢＢ树本文中所涉及的两个碰撞体,分别为 人模和衣片,其中人模在整个动态模拟过程中为静态的,因此,只需在初始化时构 造一次ＡＡＢＢ树即可。为了进一步提高碰撞检测的效率,我们在构造人模的Ａ ＡＢＢ树时,应根据(4)中得到的缝合衣片别名,结合人模的几何结构,灵活构造人 模的ＡＡＢＢ树。例如:假设我们在(4)中,得到衣片分别为:左前片,右前片,左后片, 右后片。我们即可知,将要缝合的为一件四片裁剪片的上衣,所以在构造人模的Ａ ＡＢＢ树,我们只取人模上半身数据来构造人模的ＡＡＢＢ,具体层次结构如图4 所示。在进行人模和衣片间碰撞检测时,根据衣片的别名分别进行局部检测,(例如: 左前片,就只需和人模ＡＡＢＢ树第三层最左边的结点,左前半身的ＡＡＢＢ进行 碰撞检测)有效地减少了需要碰撞检测的元素。系统根据所缝合的衣片不同,建立 的人模ＡＡＢＢ树亦不相同。图4人模的ＡＡＢＢ树层次结构图 (6)动态变形模型的计算根据衣片的缝合信息,我们在衣片的对应缝合边上 加载缝合力。在缝合力、重力和衣片上各质点间内部弹力的共同作用下,二维衣 片将逐步变形,并逐渐被缝合在一起,整个缝合过程是一个动态的迭代过程。在动 态迭代过程中,要同时进行大量的人模―衣片间,及衣片―衣片间的碰撞检测处理, 并给出相应碰撞响应(当有碰撞现象发生时,要重新调整碰撞点处的位置,避免发 生穿越和渗透)的处理。缝合过程结束后,便可以得到缝合好的三维服装穿在静态 人模上的效果。
5结束语实验证明,本文所采用的织物变形模型―――弹簧质点模型,模型 简单,能够较真实地反映虚拟环境下的织物特性。所采用的基于ＡＡＢＢ的层次 包围盒碰撞检测算法,除了ＡＡＢＢ层次包围盒自身在碰撞检测上的较高性能外, 算法还从以下几方面提高了碰撞的检测效率: 1)将缝合衣片的相对位置同人模自身的结构信息相结合,灵活地构造人模 ＡＡＢＢ树,减少了人模和衣片之间不可能相交元素碰撞检测的次数;2)ＡＡＢＢ包围盒的相交判断中,采用ＳＡＴ方法进行包围盒之间的交叠 判断,降低了算法的复杂度,提高算法效率。
3)衣片之间的碰撞判断,利用了每个三角形相邻区域的三角形表面曲率来 简化求交判断。
