c++ - AABB的球体相交测试

Question

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

Answer 1

您可能已经找到了 Jim Arvo 在“Graphics Gems”中确定 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 问题中:Cube sphere intersection test?

正如您已经发现的那样，如果 AABB 完全位于球体内，此算法也会返回 TRUE，但您希望将这种情况作为一种特殊情况进行检测。这样做的一种方法是反转上述算法正在做的事情。该算法的工作原理主要是找到 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 盒子是空心的(不同之处在于当球体在盒子内部时你的检查是否返回真)所以我将把这两种情况都粘贴在这里:

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 完全位于您的球体内。