AABB球体相交试验

Question

我有一个球体，我想知道我的轴对齐边界框 (AABB) 是否完全、部分或根本不在球体内。我发现了很多算法，但它们只给出部分或外部结果。任何指针？

Answer 1

您可能已经在“Graphics Gems”中找到了 Jim Arvo最流行的确定 AABB 是否与实心球体相交的算法：

        dmin = 0;
        for( i = 0; i < 3; i++ ) {
            if( C[i] < Bmin[i] ) dmin += SQR( C[i] - Bmin[i] ); else
            if( C[i] > Bmax[i] ) dmin += SQR( C[i] - Bmax[i] );     
            }
        if( dmin <= r2 ) return TRUE;

其中Bmin存储每个轴的 AABB 的最小值，Bmax存储每个轴的 AABB的最大值，C 是球心的坐标，r2是平方半径。例如，此解决方案也出现在此 stackoverflow 问题中：立方体球体相交测试？

正如您已经发现的那样，TRUE如果 AABB 完全位于球体内，但您希望将此情况作为特殊情况检测，则此算法也会返回。这样做的一种方法是颠倒上述算法正在做的事情。该算法的工作原理基本上是找到最接近球心的 AABB 点，并将该点与球心之间的平方坐标增量相加。如果该总和小于球体半径的平方，则（在勾股定理之后）AABB 的点位于球体内部。因此，AABB 部分或全部包含在球体内。

现在假设您已经运行了该检查，并且您想确定 AABB 是仅部分包含还是完全包含。为此，让我们运行一个类似的检查，但不是 AABB 的点离圆心最近，而是离圆心最远。如果该点到球心的距离小于球半径，则 AABB 完全包含在球内。

有趣的是，Jim Arvo 被广泛引用的算法已经包含了一个算法来做到这一点。原始代码包含对“空心”或“实心”球体和 AABB 的检查。不幸的是，http://www.ics.uci.edu/~arvo/code/BoxSphereIntersect.c 上的原始代码不再可用，但互联网档案馆仍然有它：http : //web.archive.org/web/ 20100323053111/http://www.ics.uci.edu/~arvo/code/BoxSphereIntersect.c你基本上对空心球的情况感兴趣。我不知道你是否希望你的 AABB 盒子是空心的（区别在于当球体在盒子内时你的检查是否返回 true ）所以我将在这里粘贴这两种情况：

switch( mode )
    {
    case 0: /* Hollow Box and Hollow Sphere */
        dmin = 0;
        dmax = 0;
        face = FALSE;
        for( i = 0; i < n; i++ ) {
            a = SQR( C[i] - Bmin[i] );
            b = SQR( C[i] - Bmax[i] );
            dmax += MAX( a, b );
            if( C[i] < Bmin[i] ) {
                face = TRUE;
                dmin += a;
                }
            else if( C[i] > Bmax[i] ) {
                face = TRUE;
                dmin += b;
                }
            else if( MIN( a, b ) <= r2 ) face = TRUE;
            }
        if( face && ( dmin <= r2 ) && ( r2 <= dmax ) ) return TRUE;
        break;
    case 2: /* Solid Box and Hollow Sphere */
        dmax = 0;
        dmin = 0;
        for( i = 0; i < n; i++ ) {
            a = SQR( C[i] - Bmin[i] );
            b = SQR( C[i] - Bmax[i] );
            dmax += MAX( a, b );
            if( C[i] < Bmin[i] ) dmin += a; else
            if( C[i] > Bmax[i] ) dmin += b;
            }
        if( dmin <= r2 && r2 <= dmax ) return TRUE;
        break;

为了解决您最初的问题，您现在需要更改退货条件。如果dmin小于r2但dmax大于r2则您的 AABB 位于球体表面（部分相交）。如果dmin 和 dmax小于r2那么您的 AABB 完全位于您的球体内。