计算一个变换后的球体的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));
}

然而，我对这种方法的可靠性持怀疑态度。对于非均匀缩放，它不应该失败吗？

- Nick Heiner

---

这是哪种语言？（看起来像Java。） - BoltClock

看起来像是C#，但实际上这是一个与语言无关的问题。 - bobobobo

Answer 1

一般来说，转换后的球体将成为某种椭球体。要获得精确的边界框并避免进行数学计算，请注意：

- M 是您的变换矩阵（缩放、旋转、平移等）； - 请查看下面关于 S 的定义； - 按照最后的描述计算出 R； - 根据上述过程计算基于 R 的 x、y 和 z 界限。

---

一般的锥体（包括球体及其变换）可以表示为对称的 4x4 矩阵：当一个齐次点 p 在锥体 S 中时，满足 p^t S p < 0。通过矩阵 M 对您的空间进行转换会按以下方式转换 S 矩阵（该约定是将点视为列向量）。

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

这将为您提供变换后球体的精确边界框。

- comingstorm

---

请注意，S是一个对合矩阵，因此S=S^-1。 - Tavian Barnes

Answer 2

@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 的回答。

- Tavian Barnes

Answer 3

@comingstorm的答案非常优雅，因为它使用了齐次坐标和圆锥的对偶性。

问题也可以视为一个受限制的最大化问题，可以通过拉格朗日乘数法来解决。以y轴上的AABB为例。优化目标是：

约束条件是椭球方程。

"拉格朗日方程为："

其中 lambda 是乘数。极值点简单地是以下方程的解：

这提供了

- user6048

Answer 4

这种方法对于非均匀缩放是不起作用的。可以使用拉格朗日乘数（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);

- Alex Shtof

---

我不需要一个精确的AABB。但是，我不确定你建议的替代方案是什么。（你能提供伪代码吗？）我应该从未经变换的球体生成由两个点定义的原始AABB，然后变换这两个点，然后...？ - Nick Heiner

当然。为此，我们需要三个伪函数：GetAABB（sphere）将获取球体的AABB。 GetAABB（points-list）将获取给定点集的AABB（所有点的最小/最大坐标）。 GetAABBCorners（p，q）将获取AABB的所有8个角点（p和q是其中之一）。（p，q）= GetAABB（sphere）; V = GetAABBPoints（p，q）; 对于i = 1到8， V [i] = Transform（T，V [i]）; （p，q）= GetAABB（V）; - Alex Shtof

好的，我知道在评论中发布代码不起作用。我会编辑我的答案 :) - Alex Shtof