JAVA智能设备基于OpenGL的3D开发技术 之AABB碰撞检测算法论述

摘要：无论是PC机的3D还是智能设备应用上，碰撞检测始终是程序开发的难点，甚至可以用碰撞检测作为衡量3D引擎是否完善的标准。现有许多3D碰撞检测算法，其中AABB碰撞检测是一种卓有成效而又经典的检测算法，本文将为读者详细论述AABB碰撞检测的各各技术点。

关键词：J2ME；Open GL；JSR-184；M3G；CLDC2.0；3D引擎；Swerve引擎；AABB碰撞检测；

第一部分、前述：

对于移动 终端有限的运算能力，几乎不可能检测每个物体的多边形和顶点的穿透，那样的运算量对手机等设备来讲是不可完成的，所以移动设备上使用的碰撞检测不可能使用 太精确的检测，而且对于3D碰撞检测问题，还没有几乎完美的解决方案。目前只能根据需要来取舍运算速度和精确性达到目地。

第二部分、J2ME技术：

1、体系结构

为 满足消费者和嵌入式市场不断发展和多样化的需求，SUN公司的J2ME平台采用模块化、可扩展的设计。这种设计是通过三层软件模型来实现的，这三层都构建 于智能设备的操作系统之上。J2ME体系结构依照各种设备的特性，将架构分为简表、配置、虚拟机三层，这使J2ME可在每一类设备的限制下工作。

2、J2ME 3D开发包

JSR184标准为java移动应用程序定义了一个简洁的3D API接口，J2ME程序可以非常方便地使用它来实现3D应用，如游戏等。此API为非常轻量级的，整个API的完整实现不超过150KB。

3、M3G开发包

M3G是J2ME的一个可选包，以Open GL为基础的精简版，一共有30 个类，只运行在CLDC1.1及CLDC2.0上（因为必须支持浮点运算，而CLCD1.0不支持），可以在MIDP1.0和MIDP2.0中使用。

4、开发环境

操作系统：Microsoft Windows XP

IDE: Ecplise  Latefrom Version 3.3.1.1

开发包：Java2 Platform Micor Edition、JSR184、M3G

三维图形处理：3D MAX 设计3D环境

平面图像处理：Photo Shop设计在3D MAX或其它用到的图片

3D环境测试：M3G Tool Kit

模拟机：WTK2.5.2或NOKIA6131等

第三部分、需求分析

好 的碰撞检测要求人物在场景中可以平滑移动，遇到一定高度的台阶可以自动上去，而过高的台阶则把人物挡住，遇到斜率较小的斜坡可以上去，斜率过高则会把人物 挡住，在各种前进方向被挡住的情况下都要尽可能地让人物沿合理的方向滑动而不是被迫停下，在满足这些要求的同时还要做到足够精确和稳定，防止人物在特殊情 况下穿墙而入。

AABB碰撞检测算法对于以上要求都能达到比较理想的效果。

第四部分、算法具体论述

一、AABB检测前述

在游戏中的大多数物体是方形的或者是长条形的，在进行碰撞检测时应该用方盒来代表物体。一种常见的检测模型是立方体边界框，如图1-1展示了一个AABB检测盒和它里面的物体。

 

 

图1-1

在 此涉及到坐标轴平行（Axially-aligned）这个概念，坐标轴平行不仅指盒体与世界坐标轴平行，同时也指盒体的每个面都和一条坐标轴垂直，这样 一个基本信息就能减少转换盒体时操作的次数。AABB技术在当今的许多游戏中都得到了应用，开发者经常用它们作为模型的检测模型，当然，提高精度的同时也 会降低速度。

因为AABB总是与坐标轴平行，不能在旋转物体时简单地旋转AABB盒体，而是应该在每一帧都重新计算。如果知道每个对象的内容，这个计算就不算困难了，也不降低游戏的速度。然而，还面临着精度的问题。

假如有一个3D的细直刚性直棒，并且要在每一帧动画中都有重建它的AABB包装盒。可以看到每一帧中的包装盒都不一样而且精度也会随之改变，如图1-2。

 

图1-2

可 以注意到AABB对物体的方向很敏感，同一物体的不同方向，AABB也可能不同（由于球体只有一个自由度，所以检测球对物体方向不敏感）。当物体在场景中 移动时，它的AABB也需要随之移动，当物体发生旋转选择：用变换后的物体来重新计算AABB，或者对AABB做和物体同样的变换。

如果物体没有发生扭曲，可以通过“变换后的AABB”重新计算，因为该方法要比通过“变换后的物体”计算快得多，因为AABB只有8个顶点。变换AABB得出新的AABB要比变换物体的运算量小，但是也会带来一定的误差，如图1-3。

 

图1-3

比较图中原AABB（蓝色部分）和新AABB（右边比较大的方框图），它是通过旋转后的AABB计算得到的，新AABB几乎是原来AABB的两倍，注意，如果从旋转后的物体而不是旋转后的AABB来计算新的AABB，它的大小将和原来的AABB相同。

二、AABB的表达方法

先介绍AABB的表达方法，AABB内的点满足以下条件：

Xmin≤X≤Xmax;

Ymin≤Y≤Ymax;

Zmin≤Z≤Zmax;

因此只需要知道两个特别重要的顶点（Xmin， Ymin， Zmin）、(Xmax ，Ymax ，Zmax)，记作：

float [] min = new float [] {0.0f,0.0f,0.0f};

float [] max = new float [] {0.0f,0.0f,0.0f};

中心点是两个顶点的中点，代表了包装盒的质点。

Float [] center= new float [] {0.0f,0.0f,0.0f};

中心点的计算方法如下：;

float[] center() {

          center[0] = (min[0] + max[0]) * 0.5f;

          center[1] = (min[1] + max[1]) * 0.5f;

          center[2] = (min[2] + max[2]) * 0.5f;

          return center;

   }

通过这两个顶点可以知道以下属性。

float xSize() {return (max[0] - min[0]);   }返回X轴坐标点

   float ySize() {     return (max[1] - min[1]);}返回Y轴坐标点

   float zSize() {     return (max[2] - min[2]);} 返回Z轴坐标点

当添加一个顶点到包装盒时，需要先与这两个顶点进行比较。

void add(float[] p) {

          if (p[0] < min[0])               min[0] = p[0];

          if (p[0] > max[0])               max[0] = p[0];

          if (p[1] < min[1])               min[1] = p[1];

          if (p[1] > max[1])               max[1] = p[1];

          if (p[2] < min[2])               min[2] = p[2];

          if (p[2] > max[2])               max[2] = p[2];

   }

检测包装盒是不为空，可以将这两个顶点进行比较。

boolean isEmpty()

{return (min[0] > max[0]) || (min[1] > max[1]) || (min[2] > max[2]);  }

检测某个点是否属于AABB范围之内的代码如下：

boolean contains(float[] p) {

                 return (p[0] >= min[0]) && (p[0] <= max[0]) && (p[1] >= min[1])

                       && (p[1] <= max[1]) && (p[2] >= min[2]) && (p[2] <= max[2]);

   }

三、AABB对不可移动物体的静态检测

AABB的静态检测比较简单，检测两静止包装盒是否相交，它是一种布尔测试，测试结果只在相交或者不相交。这里我们提供了获取相交范围信息的方法，一般来说，这种测试的目的是为了返回一个布尔什。碰撞的示意如图1-4

 

图1-4

可以利用AABB的结构来加快新的AABB的计算速度，而不用变换8个顶点，再从这8个顶点中计算新AABB。下面简单地回顾4×4矩阵变换一个3D点的过程。

 

图1-5

通过原边界框（Xmin， Ymin，Zmin，Xmax ，Ymax ，Zmax)计算新边界框（Xmin， Ymin， Zmin，Xmax ，Ymax ，Zmax)，现在的任务是计算X1min的速度。换句话说，希望找到m11x+m12y+m13z+m14的最小值。其中[X， Y，Z]是原8个顶点的任意一个。

变换的目的是找出这些点经过变换后哪一个的X坐标最小。看第一个乘积m11x，为了最小化乘积，必须决定是用Xmin还是Xmax来替换其中的X。显然，如果m11>0，用Xmin能得到最小化的乘积；如果说m11<0，则用Xmax能得到最小化乘积。

比较方便的是，不管Xmin还是Xmax中哪一个都应用这个计算过程（其它元素不影响大小）。

根据变换矩阵和原有的AABB包装盒 计算新的AABB包装盒的代码如下：

void setToTransformedBox(Transform t) {

                  // 如果是空则返回

                  if (isEmpty()) {return;}

                  float[] m = new float[16];

                  t.get(m);

                  // 检查所有的点并计算新的盒子                     

                  float minx = 0,             miny = 0,                    minz = 0;

                  float maxx = 0, maxy = 0,        maxz = 0;

                  minx += m[3];              maxx += m[3];

                  miny += m[7];              maxy += m[7];

                  minz += m[11]; maxz += m[11];

                  if (m[0] > 0.0f) {minx += m[0] * min[0];maxx += m[0] * max[0];

                  } else {minx += m[0] * max[0];maxx += m[0] * min[0];                        }

                  if (m[1] > 0.0f) {minx += m[1] * min[1];maxx += m[1] * max[1];

                  } else {minx += m[1] * max[1];maxx += m[1] * min[1];}

                  if (m[2] > 0.0f) {minx += m[2] * min[2];maxx += m[2] * max[2];

                  } else {minx += m[2] * max[2];maxx += m[2] * min[2];}

                  if (m[4] > 0.0f) {miny += m[4] * min[0];maxy += m[4] * max[0];

                  } else {miny += m[4] * max[0];maxy += m[4] * min[0];}

                  if (m[5] > 0.0f) {miny += m[5] * min[1];maxy += m[5] * max[1];

                  } else {miny += m[5] * max[1];maxy += m[5] * min[1];}

                  if (m[6] > 0.0f) {miny += m[6] * min[2];maxy += m[6] * max[2];

                  } else {miny += m[6] * max[2];maxy += m[6] * min[2];}

                  if (m[8] > 0.0f) {minz += m[8] * min[0];maxz += m[8] * max[0];

                  } else {minz += m[8] * max[0];maxz += m[8] * min[0];}

                  if (m[9] > 0.0f) {minz += m[9] * min[1];maxz += m[9] * max[1];

                  } else {minz += m[9] * max[1];maxz += m[9] * min[1];}

                  if (m[10] > 0.0f) {minz += m[10] * min[2];maxz += m[10] * max[2];

                  } else {minz += m[10] * max[2];maxz += m[10] * min[2];}

                  min[0] = minx; min[1] = miny;

                  min[2] = minz; max[0] = maxx;

                  max[1] = maxy;            max[2] = maxz;

      }

为了使用AABB包装盒进行碰撞检测，将这些方法和属性封装为AABB类，代码如下：

import java.lang.Math;

import javax.microedition.m3g.Transform;

class AABB {

   public AABB() {     }

   float[] getMin() {  return min;  }

   float[] getMax() {  return max;  }

void setMin(float x, float y, float z) {

          min[0] = x;

          min[1] = y;

          min[2] = z;

   }

   void setMax(float x, float y, float z) {

          max[0] = x;

          max[1] = y;

          max[2] = z;

   }

void reset() {   for (int i = 0; i < 3; i++) {min[i] = 0;max[i] = 0;} }

}

为了检验碰撞检测的使用构造了两个立方体，并各自绑定了一个包装盒。

/**************************立方体1************************/

Mesh1= createCube();

Mesh1.setTranslation{1.0f,0.0f,0.0f};

Mesh1.setOrientation{90,0.0f,1.0f,0.0f};

Mesh1.setScale{0.5f,0.5f,0.5f};

Box1 = new AABB();

Box1.setMin{-1.0f,-1.0f,-1.0f};

Box1.setMax{1.0f,1.0f,1.0};

Mesh1.getCompositeTransform(cubeTransform);

World.addChild(mesh1);

/**************************立方体2************************/

Mesh2= createCube();

Mesh2.setTranslation{1.0f,0.0f,0.0f};

Mesh2.setOrientation{90,0.0f,1.0f,0.0f};

Mesh2.setScale{0.5f,0.5f,0.5f};

Box2 = new AABB();

Box2.setMin{-1.0f,-1.0f,-1.0f};

Box2.setMax{1.0f,1.0f,1.0};

Mesh2.getCompositeTransform(cubeTransform);

World.addChild(mesh2);

检测包装盒1和包装盒2是否碰撞的代码如下：

isCollided = box1.intersectAABB(box2,null);

编译运行程序，设置两个立方体不同的位置和角度，可以比较精确地检测出它们的碰撞情况，如图1-6与1-7所示。

            

图1-6                                 图1-7

四、AABB对可移动物体的动态检测

移动检测的目标是计算运动AABB碰撞到静态AABB的时刻，因此需要计算出两个AABB在所有维上的第一个点。为了简化起见，可以把上述问题先归结到某一维，然后再将三维结合到一起。假设把问题投影到X轴，如图1-8所示。

 

图1-8

绿色矩形代表沿坐标轴滑动的AABB，t=0时，运动AABB完全位于静止AABB的左边。当t=1时，运动AABB完全位于静止AABB的右边。当t=tenter时，两个AABB刚刚相交，当t=tleave时，两个AABB脱离碰撞。

对照相馆上图，可以推导出两个AABB接触和离开的时间：

 

AABB的动态检测有3个要点。

（1）   如果速度为0，两个包装盒要么一直相交，要么一直分离。

（2）   不管物体从哪个方向运动，碰撞过程中，肯定是先入后出，所以有tenter< tleave。

（3）   如tenter和tleave超出运动时间范围，那么在此范围内它们是不相交的。

检测出某一维碰撞还不够，还需要进行其它两维的检测，然后取结果的交集。如果交集为空，那么AABB包装盒没有相交，如果区间范围在时间段[0，1]之外，那么在此区间也不相交。对AABB进行动态检测的方法定义如下：

boolean intersectAABBs(AABB box2, AABB boxIntersect) {

          float[] box2_min = box2.getMin();

          float[] box2_max = box2.getMax();

                 if (min[0] > box2_max[0])  return false;

          if (max[0] < box2_min[0])  return false;

          if (min[1] > box2_max[1])  return false;

          if (max[1] < box2_min[1])  return false;

          if (min[2] > box2_max[2])  return false;

          if (max[2] < box2_min[2])  return false;

          if (boxIntersect != null) {

                 float[] box_intersect_min = new float[3];

                 float[] box_intersect_max = new float[3];

                 box_intersect_min[0] = Math.max(min[0], box2_min[0]);

                 box_intersect_max[0] = Math.min(max[0], box2_max[0]);

                 box_intersect_min[1] = Math.max(min[1], box2_min[1]);

                 box_intersect_max[1] = Math.min(max[1], box2_max[1]);

                 box_intersect_min[2] = Math.max(min[2], box2_min[2]);

                 box_intersect_max[2] = Math.min(max[2], box2_max[2]);

          }

          return true;

   }

为了对移动AABB进行检测，创建两个AABB如图1-9所示。两个包装盒距离0。5，速度为3。

检测代码如下：

float [] speed = new float [] {3.0f,0.0f,0.0f};

float [] tEnter = intersectAABB(box1,box2,speed);

输出结果为0.16667，完全符合预期的猜测。

第五部分、总结

做 碰撞检测时，该技术的重要性容易被人忽视，显然这符合日常生活中的常识。有时出现BUG，也很不容易被发现，例如人物无缘无故被卡住不能动或人物穿越了障 碍等，所以像AABB这样有效的算法在碰撞检测中是起极重要作用的，由上所述正确使用AABB可并不是件容易的事，这就需要读者下一番功夫。

参考资料

《3D 图形学》，电子工业出版社

《Open GL 开发技术》，电子工业出版社

《J2ME 3D手机游戏开发详解》，人民邮电出版社，2007.11

《J2ME手机游戏开发详解》，清华大学出版社，2005.8

《Java手机/PDA程序设计入门》电子工业出版社出版 2004.3