小河马 17:13:46
TK, 射线和AABB以及Plane的相交性检测，最好的算法是哪个啊？我找了好几个，实现都不一样，有Woo的，有Arvo的，还有其他的，你用的哪个啊 
汤锴 22:01:22
To 大河马：
直线与AABB：
bool  LineIntersectAABB(
    const Vector3& start, //[in] line start pos
    const Vector3& end,  //[in] line end pos
    const AABB& aabb  //[in]
   )
{
    f32 ld[3];
 Vector3 center;
 center.x = ( aabb.mins.x + aabb.maxs.x ) * F2FP(0.5f);
 center.x = ( aabb.mins.y + aabb.maxs.y ) * F2FP(0.5f);
 center.x = ( aabb.mins.z + aabb.maxs.z ) * F2FP(0.5f);
 Vector3 extents = aabb.maxs - center;
    Vector3 lineDir;
 lineDir.x = F2FP(0.5f) * ( end.x - start.x );
 lineDir.y = F2FP(0.5f) * ( end.y - start.y );
 lineDir.z = F2FP(0.5f) * ( end.z - start.z );
    Vector3 lineCenter = start + lineDir;
    Vector3 dir = lineCenter - center;

    ld[0] = fabsf( lineDir.x );
 if ( fabsf( dir.x ) > extents.x + ld[0] ) {
        return false;
 }

    ld[1] = fabsf( lineDir.y );
 if ( fabsf( dir.y ) > extents.y + ld[1] ) {
        return false;
 }

    ld[2] = fabsf( lineDir.z );
 if ( fabsf( dir.z ) > extents.z + ld[2] ) {
        return false;
 }

    Vector3 cross;
 Vec3Cross( cross, lineDir, dir );
 
 if ( fabsf( cross.x ) > extents.y * ld[2] + extents.z * ld[1] ) {
        return false;
 }

 if ( fabsf( cross.y ) > extents.x * ld[2] + extents.z * ld[0] ) {
        return false;
 }

 if ( fabsf( cross.z ) > extents.x * ld[1] + extents.y * ld[0] ) {
        return false;
 }

    return true;
}

直线与平面：
你要求是什么？直线和平面只有三种位置关系，平行，相交，在平面内。一般在平面内也算成相交。
如果你只需要知道直线和平面是否相交，只要反证它与平面不平行就行了，如果要求出交点，则需更进一步计算。
全面的算法如下：
/// get distance line to plane
//NOTE: line MUST be normalized! plane MUST be normalized!
//NOTE: if distance != 0, not intersect
//  if distance == 0, intersect
f32   DistanceL2PL(
    const Line& lA,   //[in]
    const Plane& plA,  //[in]
    Vector3* pvIns   //[out] intersect point, pass NULL if don't need it!
   )
{
 // get cos
 f32 fCos = PlaneDotNormal( plA, lA.dir );

 // check for 90 degree (line is parall to plane)
 if( fabsf(fCos) < S3D_EPSILON )
 {//parall
  // get distance
  return DistanceP2PL( lA.p, plA, NULL );
 }

 // get intersect point
 if( pvIns )
 {
  // get dist from lA.p to intersect point
  f32 fDist = PlaneDotCoord( plA, lA.p ) /  fCos;

  // get intersect point
  pvIns->x = lA.p.x - lA.dir.x * fDist;
  pvIns->y = lA.p.y - lA.dir.y * fDist;
  pvIns->z = lA.p.z - lA.dir.z * fDist;
 }

 // distance = 0
 return F2FP(0.0f);
}
汤锴 22:02:34
上面的算法，Line与AABB算法来自Doom3 SDK，所以应该接近最优了
Line与Plane我自己写的，不排除有更好的解法

小河马 17:23:04
TK, doom3 sdk里面的Ray和AABB碰撞检测的原理是什么啊，代码看不懂啊，但结果是正确的，我测试过了
/*
============
idBounds::RayIntersection

  Returns true if the ray intersects the bounds.
  The ray can intersect the bounds in both directions from the start point.
  If start is inside the bounds it is considered an intersection with scale = 0
============
*/
bool idBounds::RayIntersection( const idVec3 &start, const idVec3 &dir, float &scale ) const {
 int i, ax0, ax1, ax2, side, inside;
 float f;
 idVec3 hit;

 ax0 = -1;
 inside = 0;
 for ( i = 0; i < 3; i++ ) {
  if ( start[i] < b[0][i] ) {
   side = 0;
  }
  else if ( start[i] > b[1][i] ) {
   side = 1;
  }
  else {
   inside++;
   continue;
  }
  if ( dir[i] == 0.0f ) {
   continue;
  }
  f = ( start[i] - b[side][i] );
  if ( ax0 < 0 || idMath::Fabs( f ) > idMath::Fabs( scale * dir[i] ) ) {
   scale = - ( f / dir[i] );
   ax0 = i;
  }
 }

 if ( ax0 < 0 ) {
  scale = 0.0f;
  // return true if the start point is inside the bounds
  return ( inside == 3 );
 }

 ax1 = (ax0+1)%3;
 ax2 = (ax0+2)%3;
 hit[ax1] = start[ax1] + scale * dir[ax1];
 hit[ax2] = start[ax2] + scale * dir[ax2];

 return ( hit[ax1] >= b[0][ax1] && hit[ax1] <= b[1][ax1] &&
    hit[ax2] >= b[0][ax2] && hit[ax2] <= b[1][ax2] );
}
代码真简洁，可惜就是看不懂。。

汤锴 11:15:08
大河马，刚看了RayIntersection，感觉比较容易看懂。
可是我不知道怎么给你解释。
你多画图，另外把
b[0][1]想象成b.mins.x
start[1]想象成start.x
这样比较容易理解
此外，你想想看scale这个值是什么几何意义，以及当函数返回的时候，scale中返回的值又是什么意义？最后，我发现这段代码有一个小小的问题，修改以后，可以使效率略有提高，你能找出来吗？
汤锴 11:15:45
说错了，
b[0][0] -〉 b.mins.x
b[1][1] ->  b.maxs.y
start[2] -> start.z
小河马 11:16:27
我测试过了,scale返回的是，沿着这个射线，从射线起始点到交点的距离
如果scale<0，说明射线的反方向相交了。还有，dir必须是单位化的，否则返回scale不对。。
汤锴 11:19:01
当然，dir是方向向量
这是常识了
小河马 11:19:32
好，我自己画图推导下
小河马 11:28:29
哦，我可能知道了；首先，先判断射线射出点start离AABB 6个面哪个最近，然后开始求start到这个面的交点，最后看交点是否在矩形范围之内；scale，因为是比率，所以可以是任意一个x,y,z方向的比率；优化的地方，就是在for循环时，检测到ax0 >= 0时，就可以跳出了
而且，函数里面的hit就是交点的坐标
 
小河马 11:41:16
优化的地方我说错了，单纯检测到ax >= 0跳出，是不行的。。结果会不对。。
 

汤锴 13:14:58
你看得很好，让我想起以前的一个家伙。。。
这段代码问题有两个：
1 对于某些肯定不会相交的情形，排除得不够快
2 在找出最近面的过程中，没有必要一直去求scale，可以用维护mindist的方式求最近面，在找到最近面以后，再求scale，这样可以减少一些昂贵的除法
具体你自己研究吧
小河马 13:16:47
除法，最多除3次吧？

汤锴 13:17:05
可是这个函数却很可能被密集执行
数学库的代码都必须经过彻底的优化
假如（我是说假如）每次都能减少2次除法，调用1000次该函数就可以减少2000次除法

小河马 13:25:13
我觉得，jsr184的底层，应该是用定点数来表示浮点数的吧
汤锴 13:21:46
我几乎是100%用定点数的，我把float类型都隐藏掉了
float，除法，不连续内存访问，在手机游戏（其实不光是游戏）编程中，都是要竭力避免的。
不能用float，因为ARM芯片一般都不带有FPU协处理器
不能用除法，因为ARM指令集里没有对DIV的直接支持，要用很多指令去模拟
不能非连续访问内存，因为ARM CPU只有L1 cache，没有L2 cache，而且L1 cache的容量还很小，并且总线速度又很慢