摘 要：Space是计算机科学联合研究院自主研发的三维操作系统。碰撞检测子系统是三维桌面环境中最重要的模块，是系统中所有对象处理过程的基础。必须达到真实、实时。ODE开源物理引擎，是一个专为模拟刚性物体高质量免费函数库,由于其快速、健壮已经被许多开源游戏引擎使用。所以将其移植到Space中是一个非常有意义的工作，可以满足系统对碰撞检测的要求。
关键词：物理引擎；碰撞检测；ODE
1.Space操作系统简介
Space三维操作系统是基于虚拟现实提出的提出设计理念。以房间（room）为分割单位，使得用户凭借日常生活常识即可轻松操控计算机。例如，用户如果想看书，可以进入“图书馆房间”去浏览书籍；如果想写文档，可以进入”办公室房间“，使用Office等各种软件；如果想上网查资料，可以进入”网络房间”,使用IE，FireFox等浏览器。
如图1所示，碰撞检测模块是Space三维桌面环境中最重要的模块，是系统中所有对象处理过程的基础，大部分的人机交互过程都要依靠此模块。所以它必须达到真实、实时，才能使整个系统更能吸引用户使用。
图1 Space中的碰撞检测模块
2.ODE物理引擎的特点
ODE是由Russel Smith开发的一款开源物理引擎，擅长模拟带铰链关节的刚性体结构。该引擎是快速、健壮和稳定的，可以进行交互式或者实时模拟，尤其擅长模拟运动的物体。该引擎使用了高度稳定的积分器，使得模拟错误不会变得失控。下面通过一些具体概念来具体说明：
1) 刚性体（Rigid Body）的属性
从模拟的观点来看,刚性体有多种属性,一些随时间可变:
* 物体引用点的位置矢量(x,y,z)。通常,引用点对应着物体的质心。
* 参考引用点的线速度矢量(vx,vy,vz)。
* 物体的朝向。使用四元数(qs,qx,qy,qz)或者一个3x3旋转矩阵来表示。
* 角速度矢量(wx,wy,wz)，它是用来描述物体随时间旋转的物理量。
其他属性不随时间变化:
* 物体的质量。
* 质心相对于参考引用点的位置。
* 惯性矩阵。一个3x3 矩阵，它描述了物体的质量是如何围绕着质心分布的。
2) 岛屿和失效体
物体之间使用“关节”相互连接，一个“岛屿”就是一组不能分离的物体。在模拟时，单独处理每个世界中的每个岛屿会提高效率。
每个物体可能处于有效状态或者失效状态。在模拟时，可以关掉失效体，不做更新，这样就可以节省计算时间。要使物体的岛屿失效，必须让其上的所有物体失效。如果一个失效的岛屿与另一个有效体接触，则整个岛屿变为有效，同时一个接触关节被加入到岛屿中。
3) 积分器
模拟刚性体系统随时间变化的过程称之为“积分器”：随着时间的移动，调整所有刚性体的状态。其中，有两个重点考虑的问题：
* 精度如何? 即模拟系统应该在多大程度上接近真实生活?
* 稳定性如何? 即计算错误会不会模拟系统产生完全的非物理行为（如引起系统“爆炸”）。
现在ODE的积分器非常稳定，但是只是在步长非常小的情况下才特别精确。
4) 蓄力器
在积分过程的每一步中可以调用函数给刚性体施加力。这些力被增加到“蓄力器”中。当进入下一步时，所有的力施加到物体上。每一步之后，蓄力器中的力归零。
5) 关节和约束
“关节”是类似于铰链，用来连接两个物体，这样两个物体之间有相对的位置和方向。这种关系也可称之为“约束”。每次积分器应用约束力到所有关节和物体上。每个关节有一些参数来控制它的几何体。
6) 关节组.
关节组是一种特殊的约束，能控制一个世界中的多个关节。关节可以添加到一个组中，并且当这些关节都不再需要的时候可以快速销毁一个组中的所有关节。但是，在整个组变为空之前不能销毁单个关节。
7) 关节错误和误差降低参数(ERP)
当用一个关节连接两个物体的时候，这些物体要求有确定的位置和相对朝向。然而，对某些物体有可能处于关节约束不满足的位置。有一种机制可降低关节错误: 在仿真的每一步每个关节使用一个力将物体矫正回正确的位置。这个力由误差降低系数(ERP)来控制。误差降低系数的取值在0到1之间。
ERP 声明了在下一步的仿真中要修正关节错误的比例数。如果ERP为0，不使用矫正力并且物体最终会漂移开。如果ERP为1，仿真在进行下一步之前会矫正所有的关节错误。然而，不推荐将ERP设置为1，由于各种内部的近似处理，关节错误不会被完全修正。通常设为0.1到0.8之间（默认为0.2）。
一个全局的ERP值能够影响大多数关节。然而许多关节有局部的ERP值控制该关节。
3.在Space中使用ODE
如前所述，在Space中是以房间(room)为空间分割单位，因为两个房间内的物体不会发生碰撞，所以我们可以分别模拟。每个房间可以形成一个世界(world)，在其中建立一个空间(space)，里面可以包含很多物体(body)。这样物体与物体之间或者物体与场景(不可移动的物体)之间就会发生碰撞，我们做如下处理：
1) 在每一个模拟开始前，调用碰撞检测函数来决定是否发生碰撞。这些函数返回一个接触点(contact)的列表。每个接触点都声明一个在空间中的位置，一个表面法线矢量，一个传统深度。
2) 为每一个接触点创建一个特定的接触关节，这个关节给出了接触点的额外信息，例如接触面的摩擦系数，弹性或者柔软程度，还有其它的属性。
3) 将所有接触关节放到一个关节组里面。接触点过多，模拟速度会下降。可以使用不同的策略来限制接触点的数量。
4) 进行一步模拟。
5) 从系统中移除所有的接触点关节。
下面以办公室(office room)为例说明代码的结构。其余房间类似。
简化需求：
场景：一个桌子和六个墙壁。
物体：四台笔记本电脑。
初始时：电脑都置于桌子上，只于桌面发生碰撞不至于下落。可以使用鼠标选中某台电脑横向拖动使其与其余电脑发生碰撞。这样电脑会与桌面发生摩擦，或者移开位置，或者掉落至墙面(包括地面)发生反弹。
模拟代码如下：
1) 创建一个动态的世界（world）
dWorldID officeWorld = dWorldCreate();
2) 创建动态世界中的物体（bodies）
//以创建桌子为例，其余物体类似
dBodyID deskBody = dBodyCreate(officeWorld);
3) 设置所有物体的状态（质量，位置，受力等）
//以桌子为例，其余物体类似
dBodySetPosition(deskBody,x,y,z);
4) 创建关节组容纳关节。
dJointGroupID contactgroup = dJointGroupCreate (0);
5) 进入循环，执行如下操作
a) 给物体施加力
b)
调整关节参数
c) 调用碰撞检测函数
d) 为每一个碰撞点创建一个接触关节，并放置到接触关节组中。
e) 进行一步仿真
f) 移除在接触关节组中的关节
具体示例代码如下：
// 注册回调函数：nearCallback
dSpaceCollide(officeSpace,0, &nearCallback);
//设置模拟步长，进行模拟
dWorldQuickStep(officeWorld, 0.01);
//每次模拟后都要清空关节组
dJointGroupEmpty(contactgroup);
在模拟过程中，当两个物体存在潜在碰撞时，执行回调函数处理碰撞检测：
void nearCallback (void *data, dGeomID o1, dGeomID o2)
{
int i;
//取得可能发生碰撞的两个物体
dBodyID b1 = dGeomGetBody(o1);
dBodyID b2 = dGeomGetBody(o2);
//如果这两个物件已经通过关节相连，则不再处理
if(b1 && b2 &&
dAreConnectedExcluding(b1,b2, dJointTypeContact))
return;
//设置接触面的属性，如摩擦系数，弹性系数，ERP等
dContact contact Wendy Stahler , Beginning Math and Physics for Game Programmers New Riders Publishing，2004， 248-297.
