基于非线性规划的凸多面体间碰撞检测算法_赵伟
- 格式:pdf
- 大小:163.82 KB
- 文档页数:4
凸多边形碰撞检测的分离轴算法(SAT) 碰撞检测可分为 Broad Phase (粗略检测)与 Narrow Phase (精细检测)两个阶段。
粗略检测阶段可直接⽐较两个物体的AABB包围框是否碰撞以节省计算量和时间。
在精细检测中,SAT(Separating Axis Theorem,分离轴定理)碰撞检测算法直观且⾼效,它的原理清晰易懂,即若两个物体没有发⽣碰撞,则总会存在⼀条直线,能将两个物体分离。
分离轴适⽤的是凸多边形之间的检测,不适⽤于凹多边形,凹多边形的检测,可以通过算法将凹多边形分割成多个凸多边形再进⾏计算。
算法步骤如下: 步骤⼀:从需要检测的多边形中取出⼀条边,并找出它的法向量,这个向量将会是我们的⼀个“投影轴”。
步骤⼆:循环获取第⼀个多边形的每个点,并将它们投影到这个轴上。
步骤三:对第⼆个多边形做同样的处理。
步骤四:分别得到这两个多边形的投影,并检测这两段投影是否重叠。
如果你发现了这两个投影到轴上的“阴影”有间隙,那么这两个图形⼀定没有相交。
但如果没有间隙,那么它们则可能接触,你需要继续检测直到把两个多边形的每条边都检测完。
如果你检测完每条边后,都没有发现任何间隙,那么它们是相互碰撞的。
根据上⾯步骤两个凸多边形之间碰撞检测的关键代码如下(参考):1def flatten_points_on(points, normal, result):2 minpoint = math.inf3 maxpoint = -math.inf45for i in range(len(points)):6 dot = points[i].dot(normal)7if dot < minpoint:8 minpoint = dot9if dot > maxpoint:10 maxpoint = dot1112 result[0] = minpoint13 result[1] = maxpoint141516def is_separating_axis(a_pos, b_pos, a_points, b_points, axis):17 range_a = [0, 0]18 range_b = [0, 0]1920 offset_v = b_pos-a_pos2122 projected_offset = offset_v.dot(axis)2324 flatten_points_on(a_points, axis, range_a)25 flatten_points_on(b_points, axis, range_b)2627 range_b[0] += projected_offset28 range_b[1] += projected_offset2930if range_a[0] > range_b[1] or range_b[0] > range_a[1]:31return True3233return False343536def test_aabb(b1,b2):37return b1[0][0] <= b2[1][0] and b2[0][0] <= b1[1][0] and b1[0][1] <= b2[2][1] and b2[0][1] <= b1[2][1]383940def test_poly_poly(a, b):41 a_points = a.rel_points42 b_points = b.rel_points43 a_pos = a.pos44 b_pos = b.pos4546for n in a.normals:47if is_separating_axis(a_pos, b_pos, a_points, b_points, n):48return False4950for n in b.normals:51if is_separating_axis(a_pos, b_pos, a_points, b_points, n):52return False5354return True555657def collide(a, b):58if not test_aabb(a.aabb, b.aabb):59return False6061return test_poly_poly(a, b) 对于参数指定的两个凸多边形,碰撞检测函数collide先调⽤test_aabb来判断其AABB包围框是否相交,若外包围框不相交则证明两个多边形之间不可能发⽣碰撞,函数值返回False,反之则使⽤分离轴算法进⾏精细检测。
判断两个凸多面体是否相交的一个快速算法
任世军;洪炳熔;孟庆鑫
【期刊名称】《软件学报》
【年(卷),期】2000(011)004
【摘要】在机器人路径规划中,碰撞检测算法占有十分重要的地位.在智能机器人仿真系统中,碰撞检测耗用的时间在整个路径规划过程所用时间中占有相当大的比例.于是,如何进一步提高碰撞检测的速度在智能机器人路径规划系统中就起到了非常关键的作用.而碰撞检测问题最终转化为判断三维空间中两个凸多面体是否相交的问题.就这一问题,给出了一种新的算法,其思想是取一个从一个凸多面体指向另一个多面体的向量,根据两个多面体中的面与这一向量的相对位置关系来寻找相交的平面.即有两个多面体的交点位于这一平面,若能找到一个相交平面则可以断定两个多面体相交.
【总页数】6页(P563-568)
【作者】任世军;洪炳熔;孟庆鑫
【作者单位】哈尔滨工程大学机电工程学院,哈尔滨,150001;哈尔滨工业大学计算机科学与工程系,哈尔滨,150001;哈尔滨工业大学计算机科学与工程系,哈尔
滨,150001;哈尔滨工程大学机电工程学院,哈尔滨,150001
【正文语种】中文
【中图分类】TP242
【相关文献】
1.判断简单多边形的核是否为空的一个快速算法 [J], 王钲旋;徐长青;庞云阶
2.判定由线性不等式围成的凸空间是否为空的一个快速算法 [J], 任世军;洪炳熔
3.一个计算凸多面体间碰撞点的快速算法 [J], 王兆其;赵沁平;汪成为
4.判断两个凸多面体相交的简单方法 [J], 周水生;容晓锋;周利华
5.计算两个凸多面体间距离的一个新算法 [J], 周水生;容晓锋;周利华
因版权原因,仅展示原文概要,查看原文内容请购买。
一种基于MPI的并行碰撞检测算法
张炯迨;夏嘉忆;牛兰平;赵伟
【期刊名称】《长春工业大学学报(自然科学版)》
【年(卷),期】2009(030)001
【摘要】提出了一种快速的碰撞检测算法.主要对虚拟空间划分,计算体元尺寸,通过检测体元内物体的状态构建物体的相邻物体链表.通过时空相关性,确定树的遍历次序,并采用MPI并行处理方式将各子任务分配到各子进程执行.实验结果表明,本算法减少了碰撞检测次数以及包围盒的遍历深度,提高了碰撞检测的效率.
【总页数】6页(P53-58)
【作者】张炯迨;夏嘉忆;牛兰平;赵伟
【作者单位】长春工业大学,计算机科学与工程学院,吉林,长春,130012;长春工业大学,计算机科学与工程学院,吉林,长春,130012;长春工业大学,计算机科学与工程学院,吉林,长春,130012;长春工业大学,计算机科学与工程学院,吉林,长春,130012;吉林大学,计算机科学与技术学院,吉林,长春,130012
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.一种基于距离聚类的并行碰撞检测算法 [J], 张进;李淑琴
2.一种新的基于混合层次包围盒的并行碰撞检测算法 [J], 赵伟;谭睿璞;丁文保
3.一种基于分治和流水线技术的并行碰撞检测算法 [J], 赵伟;何艳爽;王晓兵
4.一种基于多面体剖分的快速并行碰撞检测算法 [J], 熊玉梅
5.一种快速的基于并行的碰撞检测算法 [J], 赵伟;何艳爽
因版权原因,仅展示原文概要,查看原文内容请购买。
基于可见性查询的凸体碰撞检测算法
徐建国;张友良
【期刊名称】《图学学报》
【年(卷),期】2009(030)004
【摘要】虚拟制造、机器人路径规划等许多应用都需进行实时的碰撞检测.论文提出一种新的凸体碰撞检测算法,此算法基于主流图形硬件的可见性查询功能,克服了同类图像空间算法需从显存回读大量数据的缺点,并可一次提交多个物体对的碰撞检测.实验表明该算法有效提高了碰撞检测的效率.
【总页数】6页(P107-112)
【作者】徐建国;张友良
【作者单位】南京航空航天大学能源与动力学院,江苏南京210016;南京理工大学机械工程学院,江苏南京210094
【正文语种】中文
【中图分类】TP391
【相关文献】
1.基于Minkowski差构造技术的凸体碰撞检测算法 [J], 李学庆;孟祥旭;汪嘉业
2.基于GPU流计算模式的非凸体碰撞检测算法的研究 [J], 张雪飞;刘书桂;刘新凯
3.一种基于OBB矩形碰撞检测算法的r堆取料机防碰撞方法 [J], 尹艳艳;吕崇晓
4.虚拟手术中基于可碰撞集的软组织自碰撞检测算法 [J], 李艳波;印桂生;张菁;倪军
5.基于GJK的凸体快速连续碰撞检测研究 [J], 刘丽;张国山;邴志刚;刘敏
因版权原因,仅展示原文概要,查看原文内容请购买。
复杂虚拟环境下的实时碰撞检测算法
赵伟;谭睿璞;李勇
【期刊名称】《系统仿真学报》
【年(卷),期】2010()1
【摘要】提出了一种共享存储系统的并行碰撞检测算法。
利用AABB包围盒的优点来构建任意物体的混合包围盒层次,利用并行模型来并行遍历混合包围盒层次,进一步加速碰撞检测算法。
实验结果表明,与现有的经典算法相比,该算法在效率、精确性方面具有明显优势,能够满足交互式复杂虚拟环境的实时性和精确性的要求。
【总页数】5页(P125-129)
【作者】赵伟;谭睿璞;李勇
【作者单位】吉林农业大学信息技术学院;吉林大学数学学院;福建经济管理干部学院
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.复杂背景下运动目标的改进实时检测算法
2.复杂环境下基于信息融合的视频实时抠像算法
3.复杂场景下基于YOLOv5的口罩佩戴实时检测算法研究
4.虚拟环境下运动线缆碰撞检测算法研究与实现
5.虚拟环境下变形线性体实时建模算法研究
因版权原因,仅展示原文概要,查看原文内容请购买。
碰撞检测算法范文碰撞检测算法是计算机图形学中的一个重要问题,它用于检测两个或多个物体是否发生碰撞。
在游戏开发、虚拟现实、物理仿真等领域中都有广泛的应用。
这个问题可以通过多种算法来解决,下面将介绍几种常用的碰撞检测算法。
1.矩形边界框碰撞检测算法(AABB碰撞检测算法):矩形边界框是一种简单的表示物体边界的方式。
这个算法利用矩形边界框的位置和尺寸信息来判断两个物体是否相交。
如果两个矩形边界框相交,那么可以认为物体发生了碰撞。
这个算法的时间复杂度较低,适用于处理大量物体,但是对于复杂形状的物体可能存在误判。
2.圆形碰撞检测算法:圆形碰撞检测算法适用于处理圆形物体之间的碰撞。
它利用圆心之间的距离与两个圆的半径之和进行比较,如果距离小于或等于半径和,则认为两个圆发生了碰撞。
这个算法较为简单,但是只适用于处理圆形物体。
3.分离轴定理(SAT碰撞检测算法):分离轴定理是一种用于判断多边形之间是否发生碰撞的算法。
它基于一个原理:如果两个多边形没有共用的分离轴,则它们一定发生了碰撞。
分离轴定理需要判断多个分离轴是否存在,对于复杂形状的物体,计算量较大。
4.基于包围体的碰撞检测算法:基于包围体的碰撞检测算法是一种将物体用较简单的几何形状包围起来,然后对包围体进行碰撞检测的方法。
常见的包围体形状有球体、盒子、球树等。
这种算法可以大大减少需要进行精确碰撞检测的物体数量,以提高性能。
5.网格碰撞检测算法:网格碰撞检测算法适用于处理三维物体之间的碰撞。
它将物体分解为离散的小三角形网格,然后通过对网格之间的关系进行遍历检测碰撞。
这个算法对于复杂的三维物体具有较高的准确性,但是计算量较大。
综上所述,碰撞检测算法在计算机图形学中是一个非常重要且复杂的问题。
不同的算法适用于不同的场景和物体形状,开发人员需要根据具体需求选择合适的算法。
同时,随着计算机硬件的不断升级和算法的不断改进,碰撞检测算法也在不断发展,相信未来会出现更加高效和准确的算法来解决这个问题。
收稿日期:2008205226 基金项目:国家自然科学基金资助项目(60573182,69883004) 作者简介:赵 伟(1967-),男,汉族,吉林长春人,长春工业大学副教授,主要从事虚拟现实技术研究,E 2mail :prince1205@163.com. 第29卷第6期 长春工业大学学报(自然科学版) Vol 129,No.6 2008年12月 Journal of Changchun University of Techonology (Natural Science Edition ) Dec 12008一种新的基于混合层次包围盒的并行碰撞检测算法赵 伟, 谭睿璞, 丁文保(长春工业大学计算机科学与工程学院,吉林长春 130012)摘 要:提出了一种基于混合层次包围盒(HBVs )的快速并行碰撞检测算法。
利用AABB 包围盒较好的紧密性和包围球计算简单的优点及并行技术中的分治策略来构建物体的混合包围盒层次(S 2AABB ),通过遍历混合包围盒层次组成任务树,采用OpenM P 并行模型并行遍历任务树来加速碰撞检测算法。
实验结果表明,该算法在效率、精确性方面具有明显优势。
关键词:碰撞检测;混合层次包围盒;OpenM P 中图分类号:TP301.6 文献标识码:A 文章编号:167421374(2008)0620693206A new parallel collision detection algorit hm based on mixed BV HZHAO Wei , TAN Rui 2p u , DIN G Wen 2bao(School of Computer Science &Engineering ,Changchun University of Technology ,Changchun 130012,China )Abstract :A fast parallel collision detection algorit hm based o n mixed hierarchical bounding volumes (HBVs )was p roposed.Considering t he tight ness of AABB bounding volumes and simple calculation of t he bounding sp heres ,we use t he detached st rategy in t he parallel technology to const ruct a hybrid hierarchical bounding volumes (S 2AABB ),t hen built t he task t rees by traversing t he mixed hierarchical bo unding volumes and speeded up t he collision detection algorit hm by applying a OpenM P parallel p rogramming model.The experimental result s show t hat t he algorit hm is effective and p recise.Key words :collision detection ;hybrid bounding volume hierarchy ;OpenM P.0 引 言 在虚拟现实技术中,物体之间的碰撞检测是虚拟现实的一个重点和难点,快速高效的碰撞检测算法对于增强虚拟场景的沉浸感和真实感至关重要。
求解三维空间内任意两个多面体间的最近距
离的方法
在计算几何学中,求解三维空间内任意两个多面体间的最近距离是一个具有挑战性的问题。
这个问题在计算机图形学、机器人路径规划和分子模拟等领域中是常见的。
一种常用的方法是使用碰撞检测算法。
该方法通过检测两个多面体是否相交,来判断它们之间的最近距离。
其中一种常见的碰撞检测算法是分离轴定理,它基于以下原理:如果两个多面体之间没有重叠的投影,那么它们之间的最近距离就是它们在某个方向上的最短距离。
另一种方法是使用包围体。
包围体是一个能够完全包围一个多面体的简单几何体,例如包围盒(axis-aligned bounding box)、包围球(bounding sphere)或包围圆柱体(bounding cylinder)。
通过比较两个多面体的包围体,可以初步确定它们之间的最近距离。
一种更高级的方法是使用迭代最近点算法。
该算法基于以下原理:两个多面体之间的最近距离可以通过它们的最近点之间的距离来逐步逼近。
算法通过不断调整多面体的位置和形状,直到找到它们的最近点,并计算出它们之间的最近距离。
需要注意的是,以上提到的方法都是近似方法,不一定能够得到精确的最近距离。
而且,计算复杂的多面体之间的最近距离是一个 NP 困难问题,因此找到一个高效且精确的算法仍然是一个挑战。
总结起来,求解三维空间内任意两个多面体间的最近距离是一个具有挑战性的问题,在实际应用中需要根据具体情况选择合适的方法。
碰撞检测算法、包围体和迭代最近点算法是常用的方法,但并不保证得到精确结果。
在实际情况中,我们需要权衡计算资源和精度要求,选择最适合的方法。
基于Minkowski和的多面体碰撞检测算法作者:耿清甲张步英来源:《电子技术与软件工程》2016年第21期摘要Minkowski和已被证实为一种有效的完成快速、精确碰撞检测的方法。
基于Minkowski的定义及其特点,本文提出了基于改进射线方法的两多面体相互位置关系检测算法,并给出了最短距离检测算法。
通过上述两种算法,可快速的实现两多面体的碰撞检测。
【关键词】Minkowski和碰撞检测多面体碰撞检测技术是机器人路径规划、虚拟装配仿真中的关键技术。
Minkowski和已被证实为一种精确的、有效的解决碰撞检测的方法。
通过构造Minkowski和,可精确的表示出在参数工作空间中的障碍物空间,从而将两多面体间的相对位置关系问题转化为点与Minkowski和多面体的相对位置关系。
基于此,本文提出改进的射线法。
该算法能够快速、准确的检测出两多面体间的位置关系(相交、相离或者相互渗透)。
1 相互位置关系检测算法判断点与多面体的位置关系,射线法是一种常用的方法,即从检测点向任意方向引一条射线,求该射线与多面体的面交点的数目。
若有奇数个交点,则点在多面体中;否则,点在多面体外。
虽然射线法简单、有效,但它很难处理一些奇异性情况。
例如,射线位于某个面上或射线经过多面体的顶点时,就很难统计射线与多边形的交点个数等。
为此,基于多面体Minkowski和的性质,对射线法进行了改进。
算法思想:假设Q和P分别为参数空间中的两多面体,以坐标原点(位于Q的中心)为起点,向P的中心点连接成线段OP。
由Minkowski和的定义可知,-Q和P的Minkowski和为P的一个外包多面体,故只需判断线段OP与的交点个数便可快速的得出两多面体间的位置关系,有如下三种情况:(1)有零个交点,表明原点位于其内,两多面体已经发生碰撞并相互渗透;(2)有奇数个交点且坐标原点O不是交点,则两多面体相离;(3)原点O是交点,则两多面体相交(碰撞)。
第38卷 第3期吉林大学学报(工学版) Vol.38 No.32008年5月JournalofJilinUniversity(EngineeringandTechnologyEdition) May2008
收稿日期:2007-02-18.基金项目:国家自然科学基金项目(60573182);高等学校博士学科点专项科研基金项目(20060183042);吉林省科技发展计划项目(20060527,20040531).作者简介:赵伟(1967-),男,博士研究生.研究方向:数据库系统,虚拟现实技术等.E-mail:prince1205@163.com通讯联系人:李文辉(1961-),男,教授,博士生导师.研究方向:计算机图形学.E-mail:liwh@jlu.edu.cn
基于非线性规划的凸多面体间碰撞检测算法赵 伟1,2,李文辉1,夏云飞2(1.吉林大学计算机科学与技术学院,长春130012;2.长春工业大学计算机科学与工程学院长春130012)摘 要:为了提高碰撞检测算法的速度,提出用顶点的凸包表示凸多面体,将两个凸多面体间距离的问题归结为一个带约束条件的非线性规划问题,利用模拟退火遗传算法对该问题进行求解。利用模拟退火的接收准则进行交叉、变异,降低了时间复杂度。结果表明,模拟退火遗传算法计算效率高、速度快。关键词:计算机软件;碰撞检测;凸多面体;非线性规划;模拟退火遗传算法中图分类号:TP311.132 文献标识码:A 文章编号:1671-5497(2008)03-0676-04
Researchonconvexpolyhedroncollisiondetectionalgorithmbasedonnon-linearprogramming
ZhaoWei1,2,LiWen-hui1,XiaYun-fei2(1.CollegeofComputerScienceandTechnology,JilinUniversity,Changchun130012,China;2.CollegeofComputerScienceandEngineering,ChanchunUniversityofTechnology,Changchun130012,China)
Abstract:Toincreasetherunningspeedofthecollisiondetectionalgorithm,anewapproachisproposed,whichusesconvexBoundingVolumeHierarchies(BVHs)toexpressconvexpolyhedron.Thusthedistanceproblemoftwoconvexpolyhedronsiscomedowntoanon-linearprogrammingproblemwithconstraints.Thenon-linearprogrammingproblemcanbesolvedbysimulatedannealinggeneticalgorithm.Applyingtheacceptancecriterionofthesimulatedannealinggeneticalgorithm,intersectionandvariationarecarriedouttooptimizethetimecomplexity.Resultsshowthattheefficiencyofthesimulatedannealinggeneticalgorithmishighandthecomputingspeedisfaster.Keywords:computersoftware;collisiondetection;convexpolyhedron;non-linearprogramming;annealgeneticalgorithms
求解物体间最短距离是碰撞检测算法的关键技术之一[1],该类算法通过寻找和跟踪两个多面体之间的最近点来计算它们之间的距离,当距离小于或等于零时,两者就发生了碰撞[2]。目前著名的碰撞检测算法有Lin-Candy算法[3]和EnhancedGJK算法[4]。两种算法均借鉴了时空连续性和几何连续性的原理来提高算法的速度。本文提出的方法是将碰撞检测中物体间距离的计算问题归结为带约束条件的非线性规划问题。传统的求解非线性规划的方法有很多种[5]。每种方法都有其适用范围和局限性。与以上方法第3期赵 伟,等:基于非线性规划的凸多面体间碰撞检测算法相比,遗传算法具有极强的鲁棒性和自适应搜索能力,可以在一个复杂的、多极值点的、具有不确定性空间中寻找到最优解。但是遗传算法容易过早收敛,使搜索陷入局部最优解。把模拟退火引入到遗传算法中,可以防止遗传算法过早收敛,容易得到全局最优解,本文采用模拟退火遗传算法来求解带约束条件的非线性规划问题。1 理论基础1.1 非线性理论定义1 给定m个点V1,V2,,,VmIRn和实数K1,K2,,,Km,称表达式K1V1+,+KmVm为点V1,V2,,,Vm的线性组合,特别的当K1+,+Km=1,且K1,K2,,,Km\0时,称K1V1+K2V2+,+KmVm为点V1,V2,,,Vm的凸组合。其中Rn为n维空间[5]。定义2 设sARn,则s中任意有限个点的所有凸组合称为s的凸包(convexhull),记为H(s),即H(s)=Emi=1KiVi|ViIs,Ki\0,i=1,,,mEmi=1Ki=1,mIN+式中:N+为所有正数的集合。1.2 凸多面体的距离模型用MindA,B=||x-y||表示凸多面体A和B之间的最短距离,其中x表示物体A上的一点y表示物体B上的一点。根据上面的理论可以将物体间最短距离表示为MindA,B=Emi=1KiVi-Enj=1Rjyj式中:Emi=1KiVi表示A上的一点x;Enj=1Rjyj表示B上的一点y;Ki和Rj分别满足:stEni=1Ki=1,Ki\0,i=1,2,,,n;stEnj=1Rj=1;Rj\0,j=1,2,,,n。这样通过用顶点的凸包来表示凸多面体,可将求解物体间最短距离的问题转化为带有约束条件的非线性规划问题。在满足约束的等式和不等式中寻找使MindA,B取最小值的点,设为Ki和Rj。如MindA,B=0,则物体A和B碰撞;如果MindA,B>0,则物体A和B分离。由于A和B的顶点信息已知,所以主要是求解优化的时间复杂度,本文将采用模拟退火遗传算法进行求解。2 模拟退火遗传算法2.1 遗传算法遗传算法是模拟自然界生物进化过程的一种计算模型。它不需要求导或其他辅助知识,只需要确定搜索方向的目标函数和相应的适应度函数,它强调概率转换规则,而不是确定的转换规则[6,7]。2.2 模拟退火算法模拟退火算法是利用固体物质退火过程的热平衡问题与随机搜索寻优问题的相似性寻找全局最优或近似全局最优的一种算法[8]。在搜索最优解的过程中,模拟退火算法除了可以接受优化解外,还有一个随机接受准则,即有限度地接受恶化解,并且接受恶化解的概率慢慢趋向于0,这使得算法有可能从局部极值区域中跳出,即可能找到全局最优解,并保证了算法的收敛性。2.3 约束条件的处理将模拟退火遗传算法应用于约束最优化问题的关键是对约束条件的处理。本文提出的数学模型只需对等式约束条件进行处理和对只含上、下限的约束条件进行处理。对等式约束条件的处理:假设等式约束中有m个独立的等式,则m个变量可以用剩余的n-m个变量线性表示。将转换后的等式带入含上、下限的约束条件或不等式约束条件,从而消除了等式约束件。m个变量消除后,若原约束条件不存在不等式约束,则原约束条件全部转化为新的只含上、下限的约束;若原约束条件存在不等式约束,则原等式约束条件转化为新的不等式约束,且原上、下限约束同时被改变。对只含上、下限约束条件的处理:对于变量的上、下限约束,依据解的精度要求利用二进制码表示变量,将n个二进制位串顺序连接起来,完成一个编码。2.4 算法思想虽然遗传算法使用简单、鲁棒性强、应用范围广,但是它本身也存在着许多不足。尤其是容易过早收敛,使搜索陷入局部最优解,因此把模拟退火引入到遗传算法中,既可以防止求解过程的过早收敛,也可以防止使搜索陷入局部最优解,从而保证了算法的收敛性。本文所采用的模拟退火接收准则为
#677#吉林大学学报(工学版)第38卷Metropolis准则,即P(Tk+1)=1,fk+1变异:变异就是随机地改变染色体中的某一个值。变异时随机产生染色体中某个变异位置,然后产生min{xi}和max{xi}中的随机数,替换该位置的染色体基因。2.6 算法的实例分析步骤1 输入原始数据及所需的参数。步骤2 形成初始化解群。步骤3 赋初值Tk=T0,A=A1,计算适应函数值,操作数operatornum=0。步骤4 交叉、变异取舍新解,采用上面给出的交叉、变异方法。步骤5 操作数加一,即operatornum++。步骤6 如果满足最优解,则输出结果结束;否则Tk+1=Tk,A=Ak1,转到步骤4。
3 实验结果与性能分析为了便于性能评价,实验时选定惩罚函数法、遗传算法、模拟退火遗传算法。计算两个多面体之间的距离及所用的时间并进行比较。其测试环境为WindowsXP操作系统,CPU为赛扬IV1.7GHz,内存256MB,磁盘盘页大小1024字节,采用随机数据进行性能测试。分别作两个相交多面体和两个分离多面体的碰撞检测试验。每个实验选定四组随机实验数据,每组的实验数据个数分别为:500,1000,5000,10000,用G表示实验数据的个数,每个实验数据为两个多面体的顶点坐标。分别采用3种算法计算当两个物体之间的距离达到最小时(即碰撞)所需要的时间,然后对每组实验数据取平均值,这样会得到实验数据近似精确的结果。(1)选取两个相交的多面体任意给定两个多面体的坐标。多面体A的顶点坐标为x1(0,0,0),x2(0,0,1),x3(0,1,0),x4(1,0,0)多面体B的顶点坐标为y1(3,-2,0),y2(0,-2,3),y3(1,0,0),y4(0,-2,0)则多面体间的距离求解过程如下
mindA,B=E4i=1Kixi-E4
j=1Riyj
s.t E4i=1Ki=1;E4j=1Rj=1Ki\0,i=1,2,3,4,Rj\0,j=1,2,3,4分别采用惩罚函数法,遗传算法,模拟退火遗传算
#678#