3

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

4

3 回答 3

6

您可能已经在“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 问题中：Cube sphere intersection test?

正如您已经发现的那样，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 完全位于您的球体内。

于 2017-01-04T06:55:08.713 回答
0

试试这个算法：如果球体位于（或部分位于）inside sideAABB 的所有平面上，则球体与 AABB 发生碰撞。Inside side平面的意思是指向AABB中心的半空间。

因此，您应该检查 6 个 AABB 平面（xmin/xmax、ymin/ymax、zmin/zmax）中的每一个的球体与轴对齐的平面交叉点。如果您按球体半径拉伸平面并检查sphere center point与extruded plane.

PS我没有在实践中尝试过。该算法基于类似的方法来确定三角形内的点（https://stackoverflow.com/a/2049593/326017）

于 2015-02-05T13:11:00.440 回答
0

此处详细说明了导致true至少部分相交和false无相交的相交测试。

您现在要检查 AABB 是否完全在球体内。您可以通过检查您的所有点是否都在球体内来轻松做到这一点。该测试可以简化为检查 AABB 的两个相对顶点是否在球体内。将平方距离与球体的平方半径进行比较可以使该测试非常快。

您可以轻松地将两个测试链接在一起：

  • 检查 AABB 是否完全包含在内。如果没有，请检查它是否部分包含或根本不包含。
  • 反之亦然：检查 AABB 是否至少部分包含在内。如果是，请检查它是否完全包含在内。

根据每种情况发生的频率，一种或另一种可能更好 - 如果您觉得需要速度，请分析您的代码。

于 2015-02-05T12:58:05.940 回答