打开文本图片集
摘 要：本文对可拓学基本理论、可拓方法、转换桥进了研究。针对虚拟场景漫游常规检测方法算法复杂、计算量大的问题，提出了通过多次利用转换桥，分解并分散碰撞检测物体的方法，并将该方法运用于3D档案馆项目中，降低算法复杂度，提高了效率和精确度，实践表明，该方法可行，并且系统运行良好。
关键词：可拓学；碰撞检测；3D；虚拟环境
中图分类号：TP31 文献标识码： A 文章编号： 2095-8595 （2016） 04-460-04电子科学技术 URL： http//.cn DOI： 10.16453/j.issn.2095-8595.2016.04.022
Abstract： Research the basic theory of extenics， the extension method， transforming bridge into. The virtual scene roaming algorithm of conventional detection method is complex with huge computation， this article puts forward method of decomposing and decentralizing collision detection of objects by the transforming bridge， and applies this method to the 3D Archive Project， reduce algorithm complexity， improve the efficiency and accuracy. Practice shows that， this method is feasible， and the system runs well.
Key words： Extenics； Collision Detection； 3D；Virtual Environment引言
可拓學融和数学、工程学、哲学于一体，和控制论、信息论、系统论一样，是一门涉及范围广泛的学科，在科学与工程技术领域，它是非常有效的，不是为了验证新的实验事实，而是提供了新的思路和方法。
转换桥是解决对立矛盾问题的方法之一。利用转换桥方法，可以使对立问题转化为共存问题。文献[2]中，蔡文教授首次提出转换桥的概念和思路，文献[3]和文献[4]讨论了转换桥在解决不相容问题的应用，文献[5]和文献[6]提出了转换桥系和转折物元的概念，并对转换桥系的结构和构造方法作了讨论，文献[10]完整介绍了转换桥的概念、解决对立问题的流程。
在3D游戏中，如果增加了碰撞检测，大大增强3D游戏的真实感，有了碰撞检测，人物不再可以穿墙而过，当子弹打中物体，我们需要知道何时何处发生了碰撞，才能进行下一步反应。
一个碰撞检测场景通常包括数千个可移动和不可移动物体。假设场景中有n个物体，则需要测试的次数为：n2。
1 理论分析
转换桥一般是由转折部Z和转换通道J构成的，通常记作：
B（G1，G2）=Z*J
1.1 分隔式转折部
对一个系统中的对立问题，可以作变换T，把S分隔成S1和S2，Z化解对立问题，称为分隔式转折部，记作：
TS=S1"Z|S2
a） 若Z为某分隔式转折对象，可表示为：
B1=（S1Z，c，v1），B2=（ZS2Z，c，v2）
b） 若Z为某分隔式转折量值，原量值为v，则量值分隔式转折基元可表示为：
其中，“v1Z”和“Zv2”表示由v分解而成的两个量值，且有v1Z+Zv1=v。当量值为数量量值时，与数学中数量的分解相同。
1.2 转换通道
要把对立问题转化为共存，有的通过直接构造转折部使它们共存，有的要通过一定的变换后，才构造转折部。转换通道就是基元变换到转折部的过程。
1.2.1 转折目标
给定对立问题P=（G1∧G2）*L，（G1∧G2） L，若存在基元G"1和G"2，G"1→G1，G"2→G2，使（G"1∧G"2） L，则称（G"1，G"2）为转折目标。
1.2.2 转折条件
给定对立问题P=（G1∧G2）*L，（G1∧G2） L，若存在某一变换T和基元L"，L"=TL， 使（G"1∧G"2） L"，则称 为转折条件。
2 系统分析
2.1 场景分析
在场景中有N个静态物体，M个动态物体，总共N+M个物体，如使用包围盒检测每一帧是否发生碰撞，物体需要检测是否与除自身之外的物体发生碰撞，则需要测试的次数为1+2+3…..+ N+M-1=（N+M-1） （N+M）/2，算法复杂度为O（（N+M）/ 2）。实体的数量多，算法的复杂度过高严重影响效率，导致场景每秒刷新的次数自动减少，场景变换不连续，画面的效果差。
算法的复杂度P1与效率P2形成对立问题。
2.2 转换桥构造
所有实体在同一场景中，便把所有实体放入同一个容器中，检测碰撞时，依次取出每个实体，两两检测是否发生碰撞。
则（G1∧G2） L。
作条件对象O的分隔部Z，使0=S1|Z|S2，则有条件基元的分解变换：
TL=L"={L1，L2}
其中M1+M2......+M0=M；
同理对M进行转换，转换后的结果如下：
则（G"1∧G"3∧G"4∧......∧G"n+2） L"。其中O=S1|Z|S2|Z|S3|......Sn+1为分隔式转折物。
对静态实体做同样的转换，并直接将静态物体在地图上标注，表示这是不可去区域。
再作目标基元对应的变换：
则（G"1∧G"2） L"。其中O=S1|Z|S2为分隔式转折物。
转换后算法复杂度为O（N2）+O（M2），相对未使用转换桥的算法复杂度O（（N+M）2）已经基本符合目标和条件了，但我们继续使用转换桥分离物体。
对动态实体集
使用可拓分析原理中的可分解分析对基元进行分解，B//{B1，B2，…，Bm}。
即在场景中事先建立一张地图，将静态实体集、动态实体集分别标注，其中动态实体集与动态实体集互不发生碰撞，动态实体只与本动态实体集以及静态实体集发生碰撞。将分类好的实体集分别放入各自的容器中，实体集之间采用层次包围盒、BSP树、八叉树检测碰撞；将静态实体集直接在地图上标注，表示这是不可去区域。算法的复杂度为 O（M12）+O（M22）+O（M32）......+O（Mn2）。
3 应用案例
3.1 项目背景
在3D档案项目中，建立了3D了漫游场景，其中，摄像头不能穿过墙过，也不能穿过其他静态实体，档案馆中的密集架是可以移动的，摄像头是不穿过密集架的，密集架之间也不能相互穿过。
3.2 核心算法
核心算法如图1所示。
4 實验结果分析
我们选了五个场景进行测试，测试结果如表1。
可以看出，使用了可拓学的方法比未使用此方法的帧频要快一些，尤其是在静态实体数占总实体数较大，而最大动态实体数又较小的情况下，效率提高更为明显。
5 结论
通过转换桥的设计，引入地图分离动态实体集，直接在地图上标注静态物体的方法，降低了系统的复杂度，提高了效率，使对立问题变成了共存问题，这在实现虚拟场景漫游有重要作用。
基金项目：
本文受国家自然科学基金项——基于可拓学和HowNet的策略生成方法与系统研究（61273306）资助。
参考文献
蔡文.建设转换桥发展高科技[R].国家自然科学基金委员会《决策系统中处理矛盾冲突问题的规律》材料之四.1990：153-156.
陈俊.转换桥结构初探[J].广东工学院学报，1993，lO（4）：17-20.
高丽娜，马尧海.虚拟漫游中的碰撞检测问题的解决方法[J].计算机仿真，2006，23（2），111-113.
王剑，陆国栋，谭建荣.三维场景中图形对象的拾取方法[J].机械，2004，31（7），1.