基于Bézier曲线的队形保持算法研究

第２７卷第１期　计算机仿真　２０１０年１月　文章编号：１００６—９３４８（２０１０）０１—０００６—０３　基于Ｂ６ｚｉｅｒ曲线的队形保持算法研究　黄玺瑛，赵定海　（装甲兵工程学院指挥管理系，北京１０００７２）　摘要：为了在计算机仿真中减少ＣＧＦ实体用于保持战斗队形而产生的计算量，并使得每个ＣＧＦ实体的自动跟进路线更为光　顺逼真，可采用三次Ｂ６ｚｉｅｒ逼近样条曲线的方法来模拟ＣＧＦ实体的跟进路线。在计算时，只要求实时给出ＣＧＦ实体运动的　起点、终点位置及其运动方向，利用Ｂ￣ｚｉｅｒ曲线的端点特性，用ｄｅ　Ｃａｓｔｌｊａｕ递推算法就可以快速拟合出一条ＣＧＦ实体的运动　轨迹。算法使得采用较少的特征点拟合整条曲线，拟合出的ＣＧＦ实体行进路线较为平直、平滑，且算法的计算量小、计算速　度快，能够满足ＣＧＦ系统对仿真逼真性和实时性的要求。　关键词：计算机生成兵力；贝赛尔曲线；队形保持；仿真　中图分类号：ＴＰ３９１．９　文献标识码：Ｂ　Ａ　Ｍｅｔｈｏｄ　ｆｏｒ　Ｔｅａｍ　Ｏｒｄｅｒ　Ｍａｉｎｔｅｎａｎｃｅ　Ｂａｓｅｄ　ｏｎ　Ｂ６ｚｉｅｒ　Ｓｐｌｉｎｅ　Ｃｕｒｖｅ　ＨＵＡＮＧ　Ｘｉ—ｙｉｎｇ，ＺＨＡＯ　Ｄｉｎｇ—ｈａｉ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｅｑｕｉｐｍｅｎｔ　Ｃｏｍｍａｎｄ＆Ｍａｎａｇｅｍｅｎｔ，Ａｃａｄｅｍｙ　ｏｆ　Ａｒｍｏｒｅｄ　Ｆｏｒｃｅ　Ｅｎｇｉｎｅｅｉｒｎｇ，Ｂｅｉｊｉｎｇ　１０００７２，Ｃｈｉｎａ）　ＡＢＳＴＲＡＣＴ：Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｒｅｄｕｃｅ　ｔｈｅ　ａｍｏｕｎｔ　ｏｆ　ｃｏｍｐｕｔａｔｉｏｎ　ｆｏｒ　ｍａｉｎｔａｉｎｉｎｇ　ｔｅａｍ　ｏｒｄｅｒ　ｏｆ　ＣＧＦ　ｅｎｔｉｔｙ　ｉｎ　ｂａｔｔｌｅｆｉｅｌｄ　ｄｕｒｉｎｇ　ｓｉｍｕｌａｔｉｏｎ，ａｎｄ　ｔｏ　ｍａｋｅ　ｔｈｅ　ａｕｔｏ　ｆｏｌｌｏｗ—ｕｐ　ｌｉｎｅ　ｏｆ　ｅａｃｈ　ＣＧＦ　ｅｎｔｉｔｙ　ｍｏｒｅ　ｒｅａｌｉｓｔｉｃ，ｉｔ　ｉｓ　ａ　ｇｏｏｄ　ｗａｙ　ｔｏ　ｕｓｅ　ｔｈｉｒｄ—ｏｒｄｅｒ　Ｂ６ｚｉｅｒ　ｃｕｒｖｅｓ　ｔｏ　ｓｉｍｕｌａｔｅ　ｔｈｅ　ＣＧＦ　ｅｎｔｉｔｙ　ｆｏｌｌｏｗ—ｕｐ　ｌｉｎｅ．Ｔｈｅ　ｃｏｎｄｉｔｉｏｎｓ　ｏｆ　ｒｅａｌ—ｔｉｍｅ　ｃａｌｃｕｌａｔｉｏｎ　ａｒｅ　ｔｈｅ　ｌｏｃａｔｉｏｎ　ａｎｄ　ｄｉｒｅｃｔｉｏｎ　ｏｆ　ｓｔａｒｔｉｎｇ　ａｎｄ　ｅｎｄｉｎｇ　ｐｏｉｎｔ　ｏｆ　ＣＧＦ　ｅｎｔｉｔｙ．Ｕｓｉｎｇ　ｄｅ　Ｃａｓｔｌｊａｕ　ｒｅｃｕｒｓｉｏｎ　ｍｅｔｈｏｄ　ａｎｄ　ｔｈｅ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｏｆ　ｅｘｔｒｅｍｅ　ｐｏｉｎｔｓ　ｏｆ　ｔｈｅ　ｃｕｒｖｅ，ａ　ｍｏｖｉｎｇ　ｔｒａｃｋ　ｏｆ　ａ　ＣＧＦ　ｅｎｔｉｔｙ　ｃａｎ　ｂｅ　ｑｕｉｃｋｌｙ　ｆｉｔｔｅｄ．Ｔｈｅ　ｅｎｄｐｏｉｎｔ　ｆｅａ—　ｔｕｒｅｓ　ｏｆ　ＢＳｚｉｅｒ　ｃｕｒｖｅ　ｍａｋｅ　ｉｔ　ｐｏｓｓｉｂｌｅ　ｔｈａｔ　ａｌｌ　ｔｈｅ　ｐｏｉｎｔｓ　ｏｆ　ｔｈｅ　ｃｕｒｖｅ　ｃｏｕｌｄ　ｂｅ　ｇｏｔ　ｗｉｔｈ　ｓｅｖｅｒａｌ　ｓｐｅｃｉａｌ　ｐｏｉｎｔｓ．Ｔｈｅ　ｆｉｔ—　ｉｒｎｇ　ｃｕｒｖｅ　ｉｓ　ｓｍｏｏｔｈ　ｅｎｏｕｇｈ　ｆｏｒ　ｍｅｅｔｉｎｇ　ｔｈｅ　ｔｈｅ　ｒｅｑｕｉｒｅｍｅｎｔ　ｏｆ　ＣＧＦ　ｅｎｔｉｔｉｅｓ’ｍｏｖｅｍｅｎｔ．　ＫＥＹＷＯＲＤＳ：ＣＧＦ；Ｂ６ｚｉｅｒ　ｃｕｒｖｅ；Ｔｅａｍ　ｏｒｄｅｒ；Ｓｉｍｕｌａｔｉｏｎ　１　引言　２）对于不规则三角网ＤＥＭ，队形保持算法的复杂度增　计算机生成兵力（Ｃｏｍｐｕｔｅｒ—Ｇｅｎｅｒａｔｅｄ—Ｆｏｒｃｅｓ，ＣＧＦ）作　大，而且由于三角形网格大小不同，计算出来跟进路线会出现　为分布交互仿真中的一个重要组成部分，在军事仿真中起着　不规则的拐点，想要取得较好的效果还要再次进行插值处理。　重要作用，其中实体动力学模型、执行机构和推理机制是　为了在计算机仿真中减少ＣＧＦ实体用于保持战斗队形　ＣＧＦ实体建模的核心部分…。在ＣＧＦ仿真中，战斗队形保　而产生的计算量，并使得每个ＣＧＦ实体的自动跟进路线更　持是实体动力学模型需要解决的一个常见问题。分队或更　为光顺，可以采用逼近样条曲线来对ＣＧＦ的行进路线进行　大建制的战斗团体往往需要按照一定的队形运动，在战斗团　计算。　体中一个战斗实体路线已经确定的情况下，其它战斗实体需　要自动按照较短且平滑的路线跟进。　２　Ｂ６ｚｉｅｒ逼近样条曲线原理及特点　一种常用的ＣＧＦ处理模式是依托栅格ＤＥＭ进行网格检　Ｂ６ｚｉｅｒ逼近样条曲线是一种在造型设计中常用的样条曲　索，根据队形要求和路径选择结果令战斗实体沿着规定的地　线。设计者只需要给定一定数量的控制点，就可以使用　形网格行进　。但这种方法的缺点是：　Ｂ６ｚｉｅｒ多项式或者ｄｅ　Ｃａｓｔｌｊａｕ快速递推算法计算出样条曲线　１）跟进步长受栅格大小的制约，栅格越大，跟进路线的　上指定数量的点，连接这些点即构成逼近样条曲线。用控制　走样现象越明显，而过细小的网格则会大大加重图形渲染负　点来生成曲线的方法与战斗分队按步长进行机动仿真的工　担，使得场景显示速度减慢甚至出现跳帧；　程实践方法相吻合。　２．１　Ｂ６ｚｉｅｒ逼近样条曲线原理　假设给出ｎ＋１个控制点位置：　（　，Ｙ　，　）（ｋ∈［０，　收稿日期：２００８—０６—０１修回日期：２００８—０９—２２　ｎ］），可以使用Ｂ６ｚｉｅｒ混合函数产生位置向量尸（ｕ）（式１），连　——６——　接Ｐ（　）各个元素就得到　和Ｐ　之间（包括　和Ｐ　）的　Ｂ６ｚｉｅｒ曲线　：　Ｐ（“）＝∑Ｐ　ＢＥＺ　（ｕ），０≤Ｍ≤１　其中，ＢＥＺ　（Ｍ）是Ｂｅｒｎｓｔｅｉｎ基函数：　ＢＥＺ　．　（１）　（２）　（ｕ）＝Ｃ（ｎ，ｋ）Ｍ　（１一Ｈ）　一　是参数，取［０，１］之问的任意实数，如果是等间距取　点，则常以步长△　来描述，△　＝÷。　这里，参数Ｃ（ｎ，ｋ）是二项式系数：　ｃ（　）＝　（３）　那么，曲线上任意一点Ｐ（／／，）表示单个曲线坐标三个参　数方程的集合：　（“）＝∑ＸｋＢＥＺ　（ｕ）　ｙ（　）：∑ｙ　ＢＥＺ　（　）　（“）＝∑　ＢＥＺ　（“）　（４）　２．２　Ｂ６ｚｉｅｒ逼近样条曲线特点　由Ｂ６ｚｉｅｒ曲线逼近公式容易推导出Ｂ６ｚｉｅｒ曲线的重要　特点　：　１）曲线起、终点与特征多边形起终点相一致；　２）曲线起、终点斜率与特征多边形第一条边及最后一　条边方向一致；　３）高阶曲线可由低阶曲线拼接而成，在拼接点能够满　足Ｃ　连续性。　在工程实践中常常使用三次Ｂ￣ｚｉｅｒ曲线，因为三次　Ｂ６ｚｉｅｒ曲线不但具有以上Ｂ６　一ｚｉｅｒ曲线的典型特征，而且计算　量小、能够灵活地拼接出高阶Ｂ６ｚｉｅｒ曲线，很好地避免直接　生成高阶Ｂ６ｚｉｅｒ曲线所遇到的其他问题。　在ＣＧＦ队形保持问题中，三次Ｂ６ｚｉｅｒ曲线因其计算速度　快、可控性强的优点而成为解决问题的首选逼近曲线。　３　ＣＧＦ中战斗队形保持问题描述　在ＣＧＦ仿真中，“战斗队形保持”是一类常见问题。这　类问题的基本描述如图１所示。　假设需要描述一个具有三辆战斗车的战斗分队队形保　持问题，其中１号指挥车由操作员或机动驱动程序控制，其　行进路线是由作战想定或仿真剧本给出，而２、３号车由计算　机控制，要求其与１号车保持固定的队形行进，本例为前三　角队形。　当三辆坦克以固定前三角队形行进时，其基本过程是：　当操作员或机动控制程序操作１号车从Ｍ点行进至Ｎ点　时，其行进方向由ＭＭ’改变为ＮＮ’。以２号车为例，此时也　要求计算机控制的２号车以某条跟进路线从Ｎ点行进到Ｎ’　点，同时与１号车保持相同的行进方向和固定的相对位置。　图１　坦克分队队形保持示意图　而由于ＣＧＦ仿真的需要，结合坦克分队队形要求，仿真要求　２号车的跟进路线满足以下四点要求　“　：　１）跟进路线力求短且光滑，不能出现生硬的拐弯；　２）要保证以Ｎ点为出发点，Ｎ’点为终到点；　３）要求初始行进方向为ＮＮ．方向，终了行进方向为　Ｎ２Ｎ’方向；　４）跟进路线的计算速度要简洁、快速。　综合考虑问题本质和跟进路线的四点要求，结合Ｂ６ｚｉｅｒ　曲线的端点特性和光顺特性，可考虑选择Ｂ６ｚｉｅｒ曲线来拟合　这条跟进路线。具体做法是：可以以２号坦克行进初始点　Ｎ、初始行进方向上一点Ｎ　、终点行进方向反向延长线上一　点Ｎ　、终点Ｎ’四点作为特征多边形构造一条三次Ｂ６ｚｉｅｒ曲　线。显然，按照Ｂ６ｚｉｅｒ曲线的端点性质分析发现，该曲线能　够很好地满足以上提到的四点要求：　１）曲线起点和终点分别是２号坦克的出发点和终到　点，满足要求２；　２）曲线起点和终点的切向分别是２号坦克的初始行进　方向和终了行进方向，满足要求３；　３）Ｂ６ｚｉｅｒ曲线由于是逼近样条曲线，因此其形态比较平　直光滑，满足要求１；　４）三次Ｂ６ｚｉｅｒ曲线的逼近函数比较简单，也可利用Ｄｅ　Ｃａｓｌ—　ｊａＬｌ递推算法ｉ　亍加速计算，计算复杂度为Ｏ（ｎ），满足要求４。　因此，令计算机控制的坦克按照上述Ｂ６ｚｉｅｒ三次样条该　曲线运动可以很好地解决坦克分队行进中的队形保持问题。　４用三次Ｂ￣ｚｉｅｒ曲线实现ＣＧＦ队形保持仿真　本文介绍使用ｄｅ　Ｃａ￣ｔｌｊａｕ递推算法计算任意次Ｂ６ｚｉｅｒ曲　线的方法，关于ｄｅ　Ｃａｓｔｌｊａｕ递推算法推导过程，文献［４］有详　细介绍。　ｄｅ　Ｃａｓｔｌｊａｕ递推算法公式是：　Ｐ　：｛　一　ＰＰ　ｉ。＋　Ｐ　：　，　，…，，　。，。，．．．，　一　，（５）　式（５）中，用　来统一表示递推中取到的所有点，ｋ表示　使用该函数能够在已知特征多边形顶点坐标串　Ｃｏｎ—　ｔｒｏｌＰｔ的情况下计算出Ｂ６ｚｉｅｒ曲线点的坐标串￥ＣｕｒｖＰｔ，将这　些点顺次连接起来即是所求的曲线。具体到队形保持的问　题上，仅需输入上一节所讨论的四个控制点的坐标，即可得　到坦克２的跟进路线，令坦克２按照计算出的点移动即实现　了坦克２的自动队形保持仿真。当由操作员控制的坦克１　的位置和方向不断变化时，仅需同时调整四个控制点坐标并　重新计算曲线即可。由于该递推算法速度非常快，每一步递　推的计算量仅是２次乘法、１次加法，因此完全满足仿真的实　时陛要求。在测试中，计算一条具有５００个逼近点的三次　递推的次数，从１开始，ｎ表示特征多边形的顶点数，ｉ表示点　序列号，ｉ＝０，１，…，ｎ—ｋｏ据此公式可设计任意次Ｂ６ｚｉｅｒ曲　线计算函数，将计算步长△ｕ设定为０．０１，这样计算得到的　Ｂ６ｚｉｅｒ样条曲线便由１００个点组成。设计人员可以根据需要　设定合适的计算步长，步长越小，逼近点越多，曲线越细致，　计算量也越大，反之亦然。在本例中，函数限制曲线拟合点　最多不超过１００个，控制点个数最多不超过４０个。控制点　存放在数组ＣｔｒｌＰｏｉｎｔ［ＭＡＸ—ＣＴＲＬＰＴ］中，计算返回的逼近曲　线点存放在数组ＣｕｒｖＰｔ［ＭＡＸ—ＣＵＲＶＥＰＴ］中，实际使用的控　制点个数作为函数参数ｎ传人。　＃ｄｅｆｉｎｅ　Ｕ＿ＳＴＥＰ０．０１　＃ｄｅｆｉｎｅ　ＭＡＸ＿ＣＵＲＶＥＰＴ　１００　＃ｄｅｆｉｎｅ　ＭＡＸＣＴＲＵｙＩ＇４０　—ｖｏｉｄ　ＢｅｚＣａｌｃｕｌａｔｅ（ＣＰｏｉｎｔ　ＣｏｎｔｒｏｌＰｔ，ＣＰｏｉｎｔ￥ＣｕｒｖＰｔ，　ｉｎｔ　ｎ）　｛　／／变量定义　ｌｆｏａｔ　Ｕ＝ｆｌｏａｔ（０．Ｏ）；　ｌｆｏａｔ　ｕｌ＝１；　ＣＰｏｉｎｔ　Ｐ＿ｉｋ［ＭＡＸ—ＣＴＲＬＰＴ］；　ｉｎｔ　ｉ＝０；ｉｎｔ　ｋ＝１；ｉｎｔ　ｊ＝０；ｉｎｔ　ｒ＝０；　／／使用ｄｅ　Ｃａｓｔｅｌｊａｕ算法计算瞳线点　ｆｏｒ（ｊ：０；ｊ＜ＭＡＸ—ＣＵＲＶＥＰＴ；ｊ＋＋）　｛　ｕｌ＝ｆｌｏａｔ（１．０）一Ｕ；　／／将控制点赋给第０次递推产生的计算点　ｆｏｒ（ｉｎｔ　ｒ＝０；ｒ＜＝ｎ；ｒ＋＋）　Ｐ＿ｉｋ［ｒ］＝ＣｏｎｔｒｏｌＰｔ［ｒ］；　／／对于某个ｕ值，依次递推，直到计算出曲线上的一点Ｐ　＿ｉｋ［０］　ｆｏｒ（ｋ＝１；ｋ＜＝ｎ；ｋ＋＋）　｛　ｆｏｒ（ｉ＝０；ｉ＜＝ｎ—ｋ；ｉ＋＋）　ｊ　Ｐ＿ｉｋ［ｉ］．ｘ：ｉｎｔ（ｕｌ｝Ｐ＿ｉｋ［ｉ］．ｘ＋ｔ　Ｐ—ｉｋ［ｉ＋　１］＿ｘ）．　Ｐ＿ｉｋ［ｉ］．ｙ：ｉｎｔ（ｕｌ　Ｐ　ｉｋ　ｅｉｌ．ｙ＋ｔ｛Ｐ—ｉｋ［ｉ＋　１］．ｙ）；　｝　｝　ＣｕｒｖＰｔ［ｊ］＝Ｐ　ｉｋ　Ｅ０］；　ｕ　４－＝Ｕ＿ＳＴＥＰ：　｝　｝　以上代码基于ＶＣ＋４－６．０开发环境设计，设计人员可以　根据需要改写成其他语言适用的函数，在此不再赘述。　一８一　Ｂ６ｚｉｅｒ曲线，其计算时间不足１毫秒。　５结论　Ｂｅｚｉｅｒ逼近样条曲线在造型设计中是一种常用的曲线，　其理论和算法相当成熟。通过研究Ｂｅｚｉｅｒ曲线的特性发现，　其在ＣＧＦ仿真中也能很好地解决战斗分队的队形保持问　题。　它能保证拟合出的行进路线不但具有正确的起点、终点　和方向，而且能够保证路径的平滑形态，在对动力学仿真要　求不高的情况下能够较好地反映一般战斗车辆的机动和转　弯特点。而且Ｂｅｚｉｅｒ样条曲线的计算十分简洁快速，适合计　算机实现，能满足仿真的实时牲要求。　但本文介绍的算法并未考虑地形对车辆机动的影响，对　于一些希望细致反映装备运动学特性的仿真，还应结合数字　高程模型（ＤＥＭ）和战场动态地形模型计算每一点的坡度、坡　向、可通行性等信息，如何令ＣＧＦ实体在尽量保持战斗队形　的情况下又充分考虑战场地形影响是本文下一步要研究的　内容。　参考文献：　［１］王江云，等．通用型计算机生成兵力开发系统【Ｊ］．计算机工　程与应用，２００４。１６：２０６—２０８．　［２］　韩志军，徐克虎，李锰．坦克分队计算机生成兵力（ＣＧＦ）实体　仿真研究［Ｊ］．系统仿真学报，２００４，１６（７）：１３６７—１３６８．　［３］　Ｄｏｎａｌｄ　Ｈｅａｍ．计算机图形学一ＯｐｅｎＧＬ版［Ｍ］．北京：电子工　业出版社，２００３．　孙家广．计算机图形学［Ｍ］．北京：清华大学出版社，１９９８．　张文华等．坦克连排战术教材［Ｍ］．北京：解放军出版社，　１９９６　［作者简介］　黄玺瑛（１９７７一），女（汉族），河北宣化人，讲师，主　要研究方向为地理信息系统、计算机生成兵力和战　场环境仿真；　赵定海（１９７８一），男（汉族），内蒙古包头人，讲师，　主要研究方向为计算机生成兵力、战场环境仿真。