立方体球体相交测试？

Question

有没有更简单的方法来完成这个任务？我对数学不太擅长，在互联网上找到的公式非常复杂...我希望有更简单的方法。

我只需要知道一个球体是否与一个立方体重叠，我不关心它在哪个点重叠。

我也希望利用两种形状都是对称的这一事实。

编辑： 立方体沿着x、y、z轴直线对齐。

- Newbie

---

如果你不发布复杂的问题，我们怎么知道是否有更简单的解决方案呢？ - Puppy

嗯，我以为你能在脑海中想出一些简单的公式。但如果你不能，那么我认为比我找到的复杂公式更简单是不可能的... - Newbie

哦，我忘了提到这个事实，所以立方体确实没有旋转，各个面始终沿着x、y、z轴直线运动。 - Newbie

@新手，你想知道立方体和球是否相交，或者立方体是否完全在球内部？ - Dialecticus

顺便提一下，如果你曾经需要与数学家打交道，对于他们（也就是我们），"球体"指的是平民所说的"球面"，而"球"则包括中间的体积（即所谓的球体内部）。这在这里只是相关的，因为按照这种术语，边长为1的立方体与半径为1且中心相同的球体相交，但不与半径和中心相同的球面相交，因为立方体完全在内部。 - Steve Jessop

Answer 1

仅考虑半空间是不够的，还必须考虑最靠近的点：

借用Adam的符号：

假设有一个轴对齐的立方体，让C1和C2成为对立面的角落，S是球体的中心，R是球体的半径，并且两个物体都是实体：

inline float squared(float v) { return v * v; }
bool doesCubeIntersectSphere(vec3 C1, vec3 C2, vec3 S, float R)
{
    float dist_squared = R * R;
    /* assume C1 and C2 are element-wise sorted, if not, do that now */
    if (S.X < C1.X) dist_squared -= squared(S.X - C1.X);
    else if (S.X > C2.X) dist_squared -= squared(S.X - C2.X);
    if (S.Y < C1.Y) dist_squared -= squared(S.Y - C1.Y);
    else if (S.Y > C2.Y) dist_squared -= squared(S.Y - C2.Y);
    if (S.Z < C1.Z) dist_squared -= squared(S.Z - C1.Z);
    else if (S.Z > C2.Z) dist_squared -= squared(S.Z - C2.Z);
    return dist_squared > 0;
}

- Ben Voigt

---

C1、C2、S是什么意思？我猜R代表球的半径？ - Newbie

x = C1.X 是立方体最左侧的面，C2.X 是最右侧的面，C1.Y 是最底部的面，C2.Y 是最顶部的面，C1.Z 是最远的面，C2.Z 是最近的面。S.{X, Y, Z} 是球心的坐标。 - Ben Voigt

也许您不介意在出租车距离（曼哈顿距离）度量中添加一个等效的代码？ - user1

@mr_jigsaw：只需将“squared”更改为“abs”。我想是这样。 - Ben Voigt

你说得对。这是我一开始做的，但我的程序没有起作用。但后来发现我在其他地方犯了一个错误。 - user1

Answer 2

Jim Arvo在《Graphics Gems 2》中有一个在N维空间中运作的算法。我相信你想要的是this page底部的"case 3"，经过适应你的情况后，它的内容如下：

bool BoxIntersectsSphere(Vec3 Bmin, Vec3 Bmax, Vec3 C, float r) {
  float r2 = r * r;
  float dmin = 0;
  for( int 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] );     
  }
  return dmin <= r2;
}

- Gabe

---

@新手：我投票支持它是因为有参考，但代码确实是相同的。 - Roman L

我的材料没有参考文献，因为我没有使用任何。我已经记住了欧几里得空间中距离的公式，其余部分是简单的几何学。 - Ben Voigt

如果你想知道这段代码的作用，它是找到AABB上最接近球体的点dmin。接着，它会检查dmin是否在球体内部。 - bobobobo

我点赞这个回答，因为它比 @BenVoigt 的回答更清晰。 - Jerfov2

FYI，原始定义将SQR定义为#define SQR(a) ((a)*(a))。我认为你的回答中应该包含这个定义，或者功能上等效的定义，或者至少对SQR的作用进行解释。 - undefined

Answer 3

// Assume clampTo is a new value. Obviously, don't move the sphere
closestPointBox = sphere.center.clampTo(box)

isIntersecting = sphere.center.distanceTo(closestPointBox) < sphere.radius

其他的都只是优化。

哇，-2分。好吧，这里是three.js实现，基本上逐字逐句地表达了同样的意思。https://github.com/mrdoob/three.js/blob/dev/src/math/Box3.js

intersectsSphere: ( function () {

    var closestPoint;

    return function intersectsSphere( sphere ) {

        if ( closestPoint === undefined ) closestPoint = new Vector3();

        // Find the point on the AABB closest to the sphere center.
        this.clampPoint( sphere.center, closestPoint );

        // If that point is inside the sphere, the AABB and sphere intersect.
        return closestPoint.distanceToSquared( sphere.center ) <= ( sphere.radius * sphere.radius );

    };

} )(),

- Samuel Danielson

---

因为要用 C++ 而不是 JavaScript。 - livin_amuk