虚拟穿衣中织物模型的建立和碰撞检测的处理(2)
作者：佚名； 更新时间：2014-12-10
过程中,要求取最小的ＡＡＢＢ,需沿所选择的剖分面将碰撞体分为正负两半,并将所对应的原始几何元素(如三角面)分别归属正、负两边,整个递归过程类似于空间二叉剖分,只是每次剖分的对象是ＡＡＢＢ,而不是空间区域。递归细分一直要进行到每一个叶子节点只包容一个原始几何元素为止,所以具有ｎ个原始几何元素的ＡＡＢＢ树具有ｎ-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)衣片之间的碰撞判断,利用了每个三角形相邻区域的三角形表面曲率来简化求交判断。
参考文献
［1
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)衣片之间的碰撞判断,利用了每个三角形相邻区域的三角形表面曲率来简化求交判断。
参考文献
［1
