graphics - 计算变换球体的 AABB

Question

我有一个由中心点和半径在对象空间中表示的球体。球体通过一个可能包括缩放、旋转和平移的变换矩阵被变换到世界空间。我需要为世界空间中的球体构建一个轴对齐的边界框，但我不知道该怎么做。

这是我目前的方法，适用于某些情况：

public void computeBoundingBox() {
    // center is the middle of the sphere
    // averagePosition is the middle of the AABB
    // getObjToWorldTransform() is a matrix from obj to world space
    getObjToWorldTransform().rightMultiply(center, averagePosition);

    Point3 onSphere = new Point3(center);
    onSphere.scaleAdd(radius, new Vector3(1, 1, 1));
    getObjToWorldTransform().rightMultiply(onSphere);

    // but how do you know that the transformed radius is uniform?
    double transformedRadius = onSphere.distance(averagePosition);

    // maxBound is the upper limit of the AABB
    maxBound.set(averagePosition);
    maxBound.scaleAdd(transformedRadius, new Vector3(1, 1, 1));

    // minBound is the lower limit of the AABB
    minBound.set(averagePosition);
    minBound.scaleAdd(transformedRadius, new Vector3(-1,-1,-1));
}

但是，我怀疑这是否总是有效。它不应该因非均匀缩放而失败吗？

score 13 · Accepted Answer

通常，转换后的球体将是某种椭圆体。为它获得一个精确的边界框并不难；如果你不想通过所有的数学：

请注意，这M是您的转换矩阵（缩放、旋转、平移等）
阅读S下面的定义
R按照最后的描述计算
根据最后描述的计算x、y和边界。zR

一般圆锥曲线（包括球体及其变换）可以表示为对称的 4x4 矩阵：当时p，圆锥曲线内部有一个齐次点。用矩阵 M 变换你的空间会按如下方式变换 S 矩阵（下面的约定是点是列向量）：Sp^t S p < 0

A unit-radius sphere about the origin is represented by:
S = [ 1  0  0  0 ]
    [ 0  1  0  0 ]
    [ 0  0  1  0 ]
    [ 0  0  0 -1 ]

point p is on the conic surface when:
0 = p^t S p
  = p^t M^t M^t^-1 S M^-1 M p
  = (M p)^t (M^-1^t S M^-1) (M p)

transformed point (M p) should preserve incidence
-> conic S transformed by matrix M is:  (M^-1^t S M^-1)

二次曲线的对偶，适用于平面而不是点，由 S 的倒数表示；对于平面 q（表示为行向量）：

plane q is tangent to the conic when:
0 = q S^-1 q^t
  = q M^-1 M S^-1 M^t M^t^-1 q^t
  = (q M^-1) (M S^-1 M^t) (q M^-1)^t

transformed plane (q M^-1) should preserve incidence
-> dual conic transformed by matrix M is:  (M S^-1 M^t)

因此，您正在寻找与变换后的圆锥相切的轴对齐平面：

let (M S^-1 M^t) = R = [ r11 r12 r13 r14 ]  (note that R is symmetric: R=R^t)
                       [ r12 r22 r23 r24 ]
                       [ r13 r23 r33 r34 ]
                       [ r14 r24 r34 r44 ]

axis-aligned planes are:
  xy planes:  [ 0 0 1 -z ]
  xz planes:  [ 0 1 0 -y ]
  yz planes:  [ 1 0 0 -x ]

要找到与 R 相切的 xy 对齐平面：

  [0 0 1 -z] R [ 0 ] = r33 - 2 r34 z + r44 z^2 = 0
               [ 0 ]
               [ 1 ]
               [-z ]

  so, z = ( 2 r34 +/- sqrt(4 r34^2 - 4 r44 r33) ) / ( 2 r44 )
        = (r34 +/- sqrt(r34^2 - r44 r33) ) / r44

同样，对于 xz 对齐的平面：

      y = (r24 +/- sqrt(r24^2 - r44 r22) ) / r44

和 yz 对齐的平面：

      x = (r14 +/- sqrt(r14^2 - r44 r11) ) / r44

这为您提供了转换球体的精确边界框。

score 5 · Accepted Answer

@comingstorm 的答案很棒，但可以简化很多。如果M是球体的变换矩阵，从 1 开始索引，则

x = M[1,4] +/- sqrt(M[1,1]^2 + M[1,2]^2 + M[1,3]^2)
y = M[2,4] +/- sqrt(M[2,1]^2 + M[2,2]^2 + M[2,3]^2)
z = M[3,4] +/- sqrt(M[3,1]^2 + M[3,2]^2 + M[3,3]^2)

（这假设球体的半径为 1 并且它的中心在它被变换之前的原点。）

我在这里写了一篇带有证明的博客文章，这对于一个合理的 Stack Overflow 答案来说太长了。

score 2 · Accepted Answer

@comingstorm 的答案很优雅，因为它使用了齐次坐标和二次曲线的对偶性。

该问题也可以看作是一个可以通过拉格朗日乘子法求解的约束最大化问题。以 y 轴上的 AABB 为例。优化目标是

并且约束是椭球方程

拉格朗日是

其中 lambda 是乘数。极值只是以下方程的解

这使

score 1 · Accepted Answer

这不适用于非均匀缩放。可以使用拉格朗日乘数（KKT 定理）计算任意可逆仿射变换，我相信它会变得丑陋。

但是 - 你确定你需要一个精确的 AABB 吗？您可以通过转换球体的原始 AABB 并获得其 AABB 来近似它。它比确切的 AABB 大，因此它可能适合您的应用程序。

为此，我们需要三个伪函数：

GetAABB(sphere)将获得球体的 AABB。

GetAABB(points-list)将获得给定点集的 AABB（只是所有点的最小/最大坐标）。

GetAABBCorners(p, q)将获得 AABB 的所有 8 个角点（p 和 q 在其中）。

(p, q) = GetAABB(sphere);
V = GetAABBCorners(p, q);
for i = 1 to 8 do
    V[i] = Transform(T, V[i]);
(p, q) = GetAABB(V);

graphics - 计算变换球体的 AABB

4 回答 4

Related

Reference