网络虚拟环境中两运动物体安全避障互寻相遇的一种算法及实现

２０１４年第０２期　●ｄｏｉ：１０　３９６９／ｊ　ｉｓｓｎ．１６７１－１１２２　２０１４　０２　００７　网络虚拟环境中两运动物体安全避障　互寻相遇的一种算法及实现　唐文政，白成杰　（山东师范大学物理与电子科学学院，山东济南２５００１４）　摘要：文章提出了一种在网络虚拟环境中两运动物体安全避障互寻相遇的方法。已知两个运动物　体的初始位置，通过碰撞检测算法、相互寻找算法以及相遇判定算法，判断两物体是否相遇，模拟两物　体移动的路线，准确定位两物体的相遇地点并记录互寻路线图。该算法能够准确定位两运动物体相遇的　位置，确定安全避障后相遇的路线。　关键词：碰撞检测；相互寻找算法；相遇判定算法；安全避障　中图分类号：ＴＰ３０９　文献标识码：Ａ　文章编号：１６７１—１１２２（２０１４）０２—００３７—０４　Ａｎ　Ａｌｇｏｒｉｔｈｍ　ａｎｄ　Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　Ｔｗｏ　Ｍｏｖｉｎｇ　Ｏｂｊ　ｅｃｔｓ　Ｆｉｎｄ　ａｎｄ　Ｍｅｅｔ　Ｅａｃｈ　Ｏｔｈｅｒ　ａｎｄ　Ａｖｏｉｄ　Ｏｂｓｔａｃｌｅ　Ｓａｆｅｌｙ　ｉｎ　Ｎｅｔｗｏｒｋ　Ｖｉｒｔｕａｌ　Ｅｎｖｉｒｏｎｍｅｎｔ　ＴＡＮＧ　Ｗｌｅｎ—ｚｈｅｎｇ．ＢＡＩ　Ｃｈｅｎｇ－ｊｉｅ　（ＰｈｙｓｉｃａｌａｎｄＥｌｅｃｔｒｏｎｉｃＳｃｉｅｎｃｅＣｏｌｌｅｇｅ　ｏｆＳｈａｎｄｏｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，ＪｉｎａｎＳｈａｎｄｏｎｇ２５００１４，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ａｒｔｉｃｌｅ　ｐｕｔｓ　ｆｏｒｗａｒｄ　ａ　ｍｅｔｈｏｄ　ｔｏ　ｉｆｎｄ　ａ　ｐａｔｈ　ｂｅｔｗｅｅｎ　ｗｏｔ　ｍｏｖｉｎｇ　ｏｂｊｅｃｔｓ　ｗｈｉｃｈ　ｃａ／／ｆｉｎｄ　ａｎｄ　ｍｅｅｔ　ｅａｃｈ　ｏｔｈｅｒ　ａｎｄ　ａｖｏｉｄ　ｏｂｓｔａｃｌｅｓ　ｓａｆｅｌｙ　ｉｎ　ｎｅｔｗｏｒｋ　ｖｉｒｔｕａｌ　ｅｎｖｉｒｏｎｍｅｎｔ．Ｈａｖｉｎｇ　ｋｎｏｗｎ　ｔｈｅ　ｉｎｉｔｉａｌ　ｐｏｓｉｔｉｏｎｓ　ｏｆ　ｈｅ　ｔｔｗｏ　ｍｏｖｉｎｇ　ｏｂｊｅｃｔｓ，ｗｉｔｈ　ｔｈｅ　ｃｏｌｌｉｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ，ｔｈｅ　ｉｆｎｄ—ｅａｃｈ－ｏｔｈｅｒ　ａｌｇｏｒｉｔｈｍ　ｎｄ　ａｈｅｔ　ｍｅｅｔ—ｄｅｃｉｓｉｏｎ　ａｌｇｏｒｉｔｈｍ，　ｈｔｅ　ｓｙｓｔｅｍ　ｃａｎ　ｊｕｄｇｅ　ｗｈｅｔｈｅｒ　ｔｈｅ　ｔｗｏ　ｏｂｊｅｃｔｓ　ｍｅｅｔ　ｅａｃｈ　ｏｔｈｅｒ，ａｎｄ　ｌｏｃａｔｅ　ａｃｃｕｒａｔｅｌｙ　ｈｔｅ　ｍｅｅｔｉｎｇ　ｐｌａｃｅ　ａｎｄ　ｒｅｃｏｒｄ　ｈｔｅ　ｒｏｕｔｅ　ｍａｐ　ｂｙ　ｓｉｍｕｌａｔｉｎｇ　ｈｔｅ　ｗａｌｋｉｎｇ　ｒｏｕｔｅｓ　ｏｆ　ｔｈｅ　ｔｗｏ　ｏｂｊｅｃｔｓ．Ｔｈｅ　ａｌｇｏｒｉｔｈｍ　Ｃａｎ　ｌｏｃａｔｅ　ａｃｃｕｒａｔｅｌｙ　ｈｔｅ　ｍｅｅｔｉｎｇ　ｐｏｓｉｔｉｏｎ　ａｎｄ　ｌｏｏｋ　ｆｏｒ　ｔｈｅ　ｒｏｕｔｅ　ｅｆｆｅｃｔｉｖｅｌｙ　ｉｎ　ｎｅｔｗｏｒｋ　ｖｉｒｔｕａｌ　ｅｎｖｉｒｏｎｍｅｎｔ．　Ｋｅｙ　ｗｏｒｄｓ：ｃｏｌｌｉｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ；ｆｉｎｄ—ｅａｃｈ—ｏｔｈｅｒ　ａｌｇｏｒｉｔｈｍ；ｍｅｅｔ－ｄｅｃｉｓｉｏｎ　ａｌｇｏｒｉｔｍ；ａｖｏｉｈｄ　ｏｂｓｔａｃｌｅ　ｓａｆｅｌｙ　０引言　网络虚拟环境是指采用以网络技术为核心的虚拟现实技术，所生成的逼真的视、听、触觉一体化的特定范围的环境。　用户可以通过一些专用工具，如头盔、数据手套等，以自然方式与虚拟环境中的对象进行交互，从而产生如同真实环境的　感受和体验。近年来，网络虚拟环境—直是信息领域科技工作者和产业界人士研究、开发和应用的热点，而安全问题又是　网络虚拟环境领域的经典问题　。　网络虚拟环境中往往存在多种物体，有静止物体，也有运动物体。如何使运动物体避开静止物体及其他障碍物体，使　其在网络虚拟环境中安全移动，是构建良好网络虚拟环境应解决的技术问题，因此相关研究具有—定的理论意义与应用　价值。　１算法流程　在网络虚拟环境中，为了确定两运动物体安全避障互寻相遇路径，需要解决两个问题：一是判断两物体是否相遇；二　是记录互寻路线图。为了解决这两个问题，在研究互寻路径算法时，制定了两个规则：相遇判定规则和互寻规则。通过分析，　●　收稿日期：２０１３—１０—１０　基金项目：国家自然科学基金［６１３４００１９】、山东省自然科学基金【ＺＫ２０１２ＦＭ０２９】　作者简介：唐文政（１９８８一），男，山东，硕士研究生，主要研究方向：数字图像处理、计算机图形学；白成杰（１９６６一），男，山东，教授，硕士　主要研究方向：数字图像处理、计算机图形学。　３７　Ｉ　２０１４年第Ｏ２期　算法流程如图１所示。　位鬻初始化、　＿ｆ　广—　广——一、　≤ｊ－　碰撞硷测　湮锶硼　Ｊ　ＩＮ　躲避障碍卜　相夏寻找　位置　Ｊ　≮　相遇判定　Ｙ　输出　图１互寻最短路径算法流程　首先对两物体的位置进行初始化赋值，然后执行碰撞　检测，判断两物体是否碰撞障碍物。如果没有碰撞障碍物，　则进行相互寻找；如果碰撞障碍物，则躲避障碍物后再执　行相互寻找。执行相互寻找后，通过相遇判定准则判断两　个物体是否相遇。如果相遇，则输出相遇前的坐标集（即　互寻路线图）以及相遇时的坐标（即汇合位置）；否则记录　当前位置信息并重新定义位置，然后再执行碰撞检测。　２碰撞检测算法　碰撞检测的目的是判断两个运动物体是否与障碍物　发生碰撞，从而保证运动物体的安全性。为了检测是否　发生碰撞，通常将两个物体比作两个矩形区域，然后判　断两个矩形是否重叠，重叠即判为相遇　。这种算法比　较简单，也比较容易实现。但在实际问题中，物体往往　是不规则的，面对不规则物体，采用单纯矩形区域的效　果往往比较差。　根据文献分析，可将不规则物体间的碰撞看作是不　规则多边形的碰撞，而多边形可以用一系列点或三角形　表示　。如果障碍物用多边形的顶点表示，且两个运动　物体用一系列三角形表示，则碰撞检测可简化为点在三　角形内外的问题。　２．１算法描述　同一平面内的点Ｐ和ＡＡＢＣ只有两种位置关系，即点　在三角形外或点在三角形内（包括边界）。而判定点Ｐ在　ＡＡＢＣ内需同时满足３个条件，即点Ｐ和点ｃ在直线ＡＢ　的同侧、点Ｐ和点Ｂ在直线ＡＣ的同侧、点Ｐ和点Ａ在直　线ＢＣ的同侧　。点与三角形的位置关系如图２所示。　Ｃ　（ａ）　（ｂ）　图２点与三角形的位置关系　两点在直线同侧的判定可描述为：将两点分别代人该　直线的一般方程，若得到的两个值同号，则两点在该直线　的同侧。　如果点Ｐ的坐标为Ｐ（ｘ　Ｐ，Ｙ　），点ｃ的坐标为Ｃ（ｘＤｙｃ），　直线的一般方程为ａｘ＋　＋ｃ＝０，那么当　（　＋　＋ｃ）　（幔＋　＋ｃ）／＞０……………………………………（１）　成立，可以判定点Ｐ和点ｃ在直线ＡＢ的同侧。同样，根　据公式（１），可以判定点Ｐ和点Ｂ是否在直线ＡＣ同侧，　点Ｐ和点Ａ是否在直线ＢＣ的同侧。若同时满足以上３个　条件，则可判定点Ｐ在ＡＡＢＣ的内部，否则点Ｐ在ＡＡＢＣ　的外部。　２．２算法实现　编写函数ＩｓｌｎＴｒｉａｎｇｌｅｆ）用于判定点与三角形的位置关　系，该函数有两个人１５参数：ｉｎ—ｔｒｉ和ＩＴＩ—ｐｔ。其中，ｍ—ｐｔ　是需要判定的点，是一个ＣＰｏｉｎｔ类的变量；ｍ—ｔｒｉ是一个　Ｔｒｉａｎｇｌｅ类的变量，包含三角形信息，且Ｔｒｉａｎｇｌｅ是自定义　的类，其原型如下：　ｔｙｐｅｄｅｆ　ｓｔｒｕｅｔ　ｔｒｉａｎｇｌｅ／／定义ｊ角形结构体　ｆ　ＣＰｏｉｎｔ　Ａ：　ＣＰｏｉｎｔ　Ｂ：　ＣＰｏｉｎｔ　Ｃ：　｝Ｔｒｉａｎｇｌｅ；　ＩｓＩｎＴｒｉａｎｇｌｅｆ）原型如下：　ｂｏｏｌ　ＣＭｙＯｂｊｅｅｔＤｌｇ：：ＩｓＩｎＴｒｉａｎｇｌｅ（Ｔｒｉａｎｇｌｅ　Ｉｎ——ｔｒｉ，ＣＰｏｉｎｔ　ｉｎ——ｐｔ）　ｆ　，／求出三条边一般方程的参数　ｄｏｕｂｌｅ　Ａｌ＝ｍｔｒｉ．Ｂ．ｙ－ｍ—ｔｒｉ．Ａ．ｙ；　ｄｏｕｂｌｅ　Ｂｌ＝ｍｒｉ．Ａ．ｘ—ｍｔｒｉ．Ｂ．ｘ；　ｔｄｏｕｂｌｅ　ＣＩ－－ｎｌｔｒｉ．Ｂ．Ｘ　ｉｎｔｒｉ．Ａ．Ｙ—Ｉｎ—ｔｒｉ．Ａ．Ｘ　Ｉｎｔｒｉ．Ｂ．ｙ；　ｄｏｕｂｌｅ　Ａ２＝ｍｔｒｉ．Ｃ．Ｙ一１１１ｔｒｉ．Ｂ．ｙ；　—ｄｏｕｂｌｅ　Ｂ２＝ｍ—ｔｒｉ．Ｂ．Ｘ—Ｉｎ—ｔｒｉ．Ｃ．ｘ；　ｄｏｕｂｌｅ　Ｃ２＝ｍｔｒｉ．Ｃ．Ｘ　ＩＴＩｔｒｉ．Ｂ．Ｙ一１＂Ｉ１ｔｒｉ．Ｂ．ｘ　ｉｎｔｒｉ．Ｃ．ｙ；　～ｄｏｕｂｌｅ　Ａ３＝ｍ—ｔｒｉ．Ａ．Ｙ—ｉｎｔｒｉ．Ｃ．ｙ；　ｄｏｕｂｌｅ　Ｂ３＝ｍｔｒｉ．Ｃ．Ｘ—Ｉｌｌ—ｔｒｉ　Ａ．ｘ；　ｄｏｕｂｌｅ　Ｃ３＝ｍｔｒｉ．Ａ．ｘ　ｍｔｒｉ．Ｃ．ｙ－ｍｔｒｉ．Ｃ．Ｘ　ｍｔｒｉ．Ａ．ｙ；　～—／／判定点与三角形的位置关系　ｉｆ（（Ａｌ＊ｍ—ｔｒｉ．Ｃ．ｘ＋Ｂ１　Ｉｌｌ—ｔｒｉ．Ｃ．ｙ＋Ｃ１）＊（Ａ１　Ｉｌｌ—ｐｔ．ｘ＋Ｂｌ　ｎｌ—　ｐｔ．ｙ＋　１）＞＝ｕ＆＆　（Ａ２　ｍ—ｔｒｉ．Ａ．ｘ＋Ｂ２　Ｉｎ—ｔｒｉ．Ａ．ｙ＋Ｃ２）　（Ａ２　ｍ—ｐｔ．ｘ＋Ｂ２　１１３一　ｐｔ．ｙ＋Ｃ２）＞＝０＆＆　（Ａ３　ｍ—ｔｒｉ．Ｂ．ｘ＋Ｂ３　ｍ—ｔｒｉ．Ｂ．ｙ＋Ｃ３）　（Ａ３　ＩＩ１一ｐｔ．ｘ＋Ｂ３　ｍ—　ｐｔ．ｙ＋Ｃ３）＞＝０）　ｒｅｔｕｒｎ　ｔｒｕｅ；／／在三角形内，返回真　ｅｌｓｅ　ｒｅｔｕｒｎ　ｆａｌｓｅ；／／不在三角形内，返回假　１　ＩｓＩｎＴｒｉａｎｇｌｅ（）返回布尔值。若返回值为真，则点在三　角形内；若返回值为假，则点不在三角形内。　以物体Ｍ、Ｎ为例，执行上述算法实现碰撞检测。　本仿真程序中用一个五边形作为物体Ｍ，如图３（ａ）所示；　用不规则图形代表障碍物，如图３（ｃ）所示。障碍物可用　一系列的点表示，如图３（ｄ）所示，封装到Ｐｏｉｎｔ类中；物　体Ｍ可用一系列三角形表示，如图３（ｂ）所示，封装到　Ｔｒｉａｎｇｌｅ类中。物体碰撞检测简化为判断点在三角形内外　的问题。　１　Ｅ　黔　Ｂ　图３碰撞检测模型　设物体Ｍ的坐标为Ｍ（ｘ　，Ｙ　），若物体Ｍ的　ＩｓｌｎＴｒｉａｎｇｌｅ（）返回值为真，则发生碰撞，重置Ｍ的坐标为　Ｍ＝Ｍ（ｘ　＋１　＋１）；若返回值为假，未发生碰撞，则执行相互　寻找。　另一物体Ｎ的碰撞检测方法与Ｍ相同。　３相互寻找算法　互寻规则的目的是制定互寻路线图。根据两点之间直　线最短原则，互寻规则实际上可归结为画直线问题，即给　定Ｍ、Ｎ两个物体的位置坐标，画它们之间的直线。利用　画直线的方法来统计互寻路径的坐标点，坐标点的集合即　为路线图。　绘制直线的算法比较成熟，如ＤＤＡ算法、Ｂｒｅｓｅｎｈａｍ　算法等　。本文采用优化ＤＤＡ算法记录两物体相遇路线　２０１４年第０２期　上的坐标点，作为互寻移动的路线。　３．１算法描述　ＤＤＡ算　ｄｉｇｉｔａｌ　ｄｉｆｆｅｒｅｎｔｉａｌ　ａｎａｌｙｚｅｒ）又称数值微分法，　是计算机图形学中一种利用基于直线的微分方程来生成直　线的方法。该算法描述如下。　给定Ｍ、Ｎ的坐标为Ｍ（ｘ　，Ｙ　）和Ｎ（ｘ：，Ｙ　），作为直线的　起点和终点坐标。该直线的斜率为：　＝　２－ｙ１）／　２　１）…………………………………………（２）　递推关系为：　………………………………………………（３）　………………………………………………（４）　Ｘｉ＋ｌ　＋１　………………………………………………（５）　ＹⅢ＝ｙｆ＋ｌ…………………………………………………（６）　ｈ　利用上述算法求得的　和Ｙ　可能是浮点数，需要进行　四舍五人，从而保证直线的点是整数像素点吲。对ＤＤＡ算　法进行优化，如果Ｉｋｌ＜ｌ，则　＝ｉｎｔ　０，　’＝ｉｎｔ（ｙ　＋０．５）；否则　Ｘ’＝ｉｎｔ（ｘｆ＋０．５），Ｙ’＝ｉｎｔ（ｙｉ）。　两个运动物体互寻应是从两头向中间画线　，即先求　最外面两个点的坐标，再逐渐向内求值，最终到达汇合点　坐标。　以运动物体Ｍ寻找另一运动物体Ｎ为例。设当前Ｍ、　Ｎ的位置坐标分别为Ｍ（ｘ　，）和Ｎ（ｘ２，ｙ：），根据ＤＤＡ算法的　思想，Ｍ、Ｎ互寻规则算法如下：　１）求得ｘ，Ｙ方向的距离，记作ｄｅｔａｘ和ｄｅｔａｙ：　ｄｅｔａｘ＝ｘｌ－ｘ２………………………………………………（７）　ｄｅｔａｙ＝ｙ￣－Ｙ２………………………………………………（８）　２）判断位移的正负以确定移动的方向。设ｓｔｅｐｘ、ｓｔｅｐｙ　为两个方向上的移动步长：　ｆ．－１　ｄｅｔａｘ‘０　ｓｔｅｐｘ＝｛０　ｄｅｔａｘ＝０……………………………………（９）　Ｉ　１　ｄｅｔａｘ＞０　ｓｔｅｐｙ的计算方法同ｓｔｅｐｘ。　３）判断物体Ｍ、Ｎ在两个方向上的坐标差是否均大于２。　如果均大于２，则根据＠ｔａｘ、ｄｅｔａｙ绝对值大小比较的结果，　确定是对ｓｔｅｐｘ还是对ｓｔｅｐｙ进行加权，加权参数为２。这　样二者的移动更趋于直线：　若　２０１４年第Ｏ２期　ｆｓｔｅｐｘ＊＝２　ａｂｓ（ｄｅｔａｘ）＞ａｂｓ（ｄｅｔａｙ）…………………・………・…・（１Ｏ）　１　ｔｅｐｙ　２　ａｂｓ（ｄｅｔａｘ）＜ａｂｓ（ｄｅｔａｙ）　否则认为物体Ｍ和Ｎ在同一水平位置或者垂直位置，无需　加权。　４）更新Ｍ的位置，￣［Ｊｘ，＋＝ｓｔｅｐｘ，　＋　ｚ　。　Ｎ寻找Ｍ同时进行，方法同Ｍ寻找Ｎ。　３－２算法实现　编写函数ＭＯＶＥ（ＭＮ　ｍｌ１）模拟Ｍ，Ｎ相遇过程，其部　分代码如下：　，／函数返回下一个时刻相对当前时刻的位移　ＰＯＩＮＴ　ＣＭＮＤｌｇ：：ＭＯＶＥ（ＭＮ　ｍｎ）　｛　ＰＯｌＮＴ　ｄｅｔａ；　ＰＯＩＮＴ　ｓｔｅｐ；　ｄｅｔａ．ｘ＝ｍｎ．Ｉｌｌｄｅｓｔｉｎａｔｉｏｎ．Ｘ—ｍＹ１．ｎｌｌｏｃａｔｉｏｎ．ｘ；　ｄｅｔａ．ｙ＝ｍｎ．ｍ—ｄｅｓｔｉｎａｔｉｏｎ．ｙ－ｍｎ．１１１ｌｏｃａｔｉｏｎ．ｖ；　ｉｆ（ａｂｓ（ｄｅｔａ．ｙ］＝＝Ｏ）　ｓｔｅｐ．ｙ＝Ｏ；　ｅｌｓｅ　ｉｆ（ｄｅｔａ．ｙ＞０）　ｓｔｅｐ．ｙ：１；　ｅｌｓｅ　ｓｔｅｐ．ｙ＝一１；　ｉｆ（ａｂｓ（ｄｅｔａ．ｘ１＝＝０１　ｓｔｅｐ．ｘ＝０：　ｅｌｓｅ　ｉｆ（ｄｅｔａ．ｘ＞０１　ｓｔｅｐ．ｘ＝ｌ：　ｅｌｓｅ　ｓｔｅｐ．ｘ＝一ｌ：　ｉｆ（（ａｂｓ（ｄｅｔａ．ｘ）＞２）＆＆ａｂｓ（ｄｅｔａ．ｙ）＞２）　ｉｆ　Ｏｂｓ（ｄｅｔａ．ｘ）＞ａｂｓ（ｄｅｔａ．ｖ））　ｓｔｅｐ．ｘ　＝２：　ｅｌｓｅ　ｓｔｅｐ．Ｙ　＝２：　ｒｅｔｕｒｎ　ｓｔｅｐ；　｝　互寻规则通过返回位移信息，一方面得到两个物体的　互寻路线图，另—方面为相遇判定算法提供位置信息。　４相遇判定算法　相遇判定是判断两个物体是否相遇，其中引入欧式距　离…”。通过判断两个物体之间距离是否小于一个固定阈　值，从而判断是否相遇［１２１￣其算法描述如下：　１）设置阈值ｄ，ｄ＝ｒ　＋ｒ　。其中，ｒ　，ｒ　是物体Ｍ，Ｎ　的最大半径。　２）Ｍ点坐标为Ｍ　，Ｙ　），Ｎ点坐标为Ｎ（ｘ：，Ｙ：），计算两　个物体之间距离ｄｏ：　＝√（　）　＋（　）　…………………………………（１　１）　３）如果　＞　，则两个物体未相遇，执行相互寻找算法；　Ｉ　４。　否则两个物体相遇，记录坐标，作为汇合地点。　５结束语　随着虚拟现实技术的飞速发展，网络虚拟环境更加逼　真，更趋近于现实世界。在智能机器人移动、智能搜救、　大型游戏等领域，绘制网络虚拟环境都是必不可少的环节。　例如，智能机器人可以在一个规划好的虚拟环境中移动，　有效避开障碍，到达指定地点。当前网络虚拟环境虽然提　供了强大的应用，但很多时候还是需要人们自己去定义路　线，尤其在两物体互寻功能上存在欠缺。本仿真程序使用　ｃ＋＋语言在Ｖｉｓｕａｌ　Ｃ＋＋６．０环境下编写。微软公司的Ｖｉｓｕａｌ　ｃ＋＋６．０软件提供了强大的函数基础类库，即ＭＦＣ函数库。　除了可以借助ＭＦＣ函数库轻松编程外，函数库中还提供了　封装好的接口程序，增加了程序的可移植性。本文借助以　上工具实现碰撞检测仿真、相遇判定仿真、互寻移动仿真。　从实验结果看，算法可以较好地实现两个运动物体的互寻　操作，安全躲避障碍物并记录互寻路线和汇合地点。不足　之处在于算法处于网络虚拟环境仿真阶段，将来还要将算　法实际应用到网络虚拟现实环境中，并逐步推广到三维或　者更复杂的网络虚拟环境中。　（责编马珂）　参考文献　［１　Ｊ熊玉梅虚拟环境中物体碰撞检测技术的研究［Ｄ】．上海：上海　大学，２｛）１１　ｆ２］王神．虚拟现实中碰撞检测关键技术研究ＩＬ）１吉林：吉林大学，　２００９．　【３］王志芳碰撞检测技术的研究及应用【Ｉ）ｉ　太原：太原科技大学，　２０１２．　【４］赵伟，谭睿璞，李勇　复杂虚拟环境下的实时碰撞检测算法Ｕ］．　系统仿真学报，２０１０，２２（ｏ１）：１２５—１２９　【５１赵伟，何艳炙．一种快速的基于并行的碰撞检测算法叭　吉林大　学学报（工学版），２００８，（【）１）：１５２—１５７．　［６】张干宗．线性规划【Ｍ］．武汉：武汉大学出版社，２００４．　［７］孙家广，杨长贵．计算机图形学【Ｍ】北京：清华大学出版社，　２０００．　［８１王晓云　多段ＤＤＡ直线扫描转换算法叭．微计算机信息，２（１０５，　２１ｆ０８）：９７～９８　【９］王茂华　改进的直线ＤＤＡ算法卟科技资讯，２００９，（０４）：　２４１－２４３　【１ｆ】】郑崇友，王汇淳，王智秋　几何学引论【Ｍ　Ｊ．北京：高等教育出　版社．２０００，　【１１］李志刚，牛强．一种改进的符号化时间序列聚类方法Ｕ】．微电　子学与计算机，２０１２，（１１）：７４—７７．　『１２１任靖，李春平．最小距离分类器的改进算法——加权最小距离分　类器Ｕ］．计算机应用，２００５，２５（０５）：９９２—９９４