当前位置： 文江博客话题详情

计算变换球体的 AABB

发布于 2024-10-06 18:18:35 字数 1026 浏览 7 评论 0原文

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

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

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));
}

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

原文

I have a sphere represented in object space by a center point and a radius. The sphere is transformed into world space with a transformation matrix that may include scales, rotations, and translations. I need to build a axis aligned bounding box for the sphere in world space, but I'm not sure how to do it.

Here is my current approach, that works for some cases:

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));
}

However, I am skeptical that this would always work. Shouldn't it fail for non-uniform scaling?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（4）

度的依靠╰つ 2024-10-13 18:18:35

一般来说，变换后的球体将是某种椭球体。为其获得精确的边界框并不难；如果您不想完成所有数学运算：

  • 请注意，M 是您的变换矩阵（缩放、旋转、平移等），
  • 下面的 S 的定义
  • 请阅读计算 R 如最后所述，
  • 根据 R< 计算 x、y 和 z 边界/code> 如前所述。

一般圆锥曲线（包括球体及其变换）可以表示为对称 4x4 矩阵：当 p^t 时，齐次点 p 位于圆锥曲线 S 内部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

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

In general, a transformed sphere will be an ellipsoid of some sort. It's not too hard to get an exact bounding box for it; if you don't want go through all the math:

  • note that M is your transformation matrix (scales, rotations, translations, etc.)
  • read the definition of S below
  • compute R as described towards the end
  • compute the x, y, and z bounds based on R as described last.

A general conic (which includes spheres and their transforms) can be represented as a symmetric 4x4 matrix: a homogeneous point p is inside the conic S when p^t S p < 0. Transforming your space by the matrix M transforms the S matrix as follows (the convention below is that points are column vectors):

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)

The dual of the conic, which applies to planes instead of points, is represented by the inverse of S; for plane q (represented as a row vector):

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)

So, you're looking for axis-aligned planes that are tangent to the transformed conic:

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 ]

To find xy-aligned planes tangent to R:

  [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

Similarly, for xz-aligned planes:

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

and yz-aligned planes:

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

This gives you an exact bounding box for the transformed sphere.

回复 原文
深海蓝天 2024-10-13 18:18:35

@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，其中心位于原点。）

我写了一篇博客文章，其中证明 此处，对于合理的堆栈溢出来说太长了回答。

@comingstorm's answer is great but can be simplified a lot. If M is the sphere's transformation matrix, indexed from 1, then

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)

(This assumes the sphere had radius 1 and its center at the origin before it was transformed.)

I wrote a blog post with the proof here, which is much too long for a reasonable Stack Overflow answer.

回复 原文
终止放荡 2024-10-13 18:18:35

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

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

在此处输入图像描述

，约束是椭球方程

在此处输入图像描述

拉格朗日为

在此处输入图像描述

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

在此处输入图像描述

给出

在此处输入图像描述

@comingstorm's answer is elegant in the way that it uses the homogeneous coordinates and the duality of the conic.

The problem can also be viewed as a constrained maximization problem that can be solved by the Lagrange multiplier method. Use the AABB at y axis as an example. The optimization target is

enter image description here

and the constraint is the ellipsoid equation

enter image description here

and the Lagrange is

enter image description here

where lambda is the multiplier. The extrema are simply the solutions of the following equations

enter image description here

which gives

enter image description here

回复 原文
没有心的人 2024-10-13 18:18:35

这不适用于非均匀缩放。可以使用拉格朗日乘子（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);

This will not work for non-uniform scaling. It is possible to calculate for arbitrary invertible affine transform with Lagrange multipliers (KKT theorem) and I believe it will get ugly.

However - are you sure you need an exact AABB? You can approximate it by transforming the original AABB of the sphere and getting its AABB. It is larger than the exact AABB so it might fit your application.

For this we need to have three pseudo-functions:

GetAABB(sphere) will get the AABB of a sphere.

GetAABB(points-list) will get the AABB of the given set of points (just the min/max coordinates over all points).

GetAABBCorners(p, q) will get all the 8 corner points of an AABB (p and q are among them).

(p, q) = GetAABB(sphere);
V = GetAABBCorners(p, q);
for i = 1 to 8 do
    V[i] = Transform(T, V[i]);
(p, q) = GetAABB(V);
回复 原文
~没有更多了~

关于作者

心的位置

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

苦中寻乐

文章 0 评论 0

lueluelue

文章 0 评论 0

嗼ふ静

文章 0 评论 0

王权女流氓

文章 0 评论 0

与花如笺

文章 0 评论 0

残酷

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文