计算转换球体的AABB [英] Calculating an AABB for a transformed sphere

问题描述

我有一个由对象空间中心点和半径表示的球体。这个球体被转换成世界空间，其中有一个转换矩阵，其中可能包括尺度，旋转和平移。我需要为世界空间中的球体构建一个轴对齐的边界框，但我不知道如何去做。

这是我目前的方法，对于一些情况：

  public void computeBoundingBox（）{
 // center是球体的中间
 // averagePosition是AABB 
的中间// getObjToWorldTransform（）是从obj到世界空间的矩阵
 getObjToWorldTransform（）。rightMultiply（center，averagePosition）; 
 
 Point3 onSphere =新的Point3（center）; 
 onSphere.scaleAdd（radius，new Vector3（1,1,1））; 
 getObjToWorldTransform（）。rightMultiply（onSphere）; 
 
 //但你怎么知道变换的半径是统一的？ 
 double transformedRadius = onGeneration.distance（averagePosition）; 
 
 // maxBound是AABB 
的上限maxBound.set（averagePosition）; 
 maxBound.scaleAdd（transformedRadius，new Vector3（1,1,1））; 
 
 // minBound是AABB 
 minBound.set（averagePosition）的下限; 
 minBound.scaleAdd（transformedRadius，new Vector3（-1，-1，-1））; 
} 
  

然而，我怀疑这总会奏效。它不应该失败的非均匀缩放？

解决方案

一般来说，转换后的球体将是某种椭球体。为它确定一个确切的边界框并不难;如果你不想完成所有的数学运算：

• 注意 M 是您的转换矩阵（比例尺，旋转，翻译等）
  
• 读取 S 下面的定义


• 按照最后描述计算 R
  
• 计算 x ， y 和 z 基于 R 如上所述。

---

一般的圆锥曲线（包括球体及其变换）可以被表示为对称的4×4矩阵：当时，同构点 p 位于圆锥曲线 S p ^ t S p < 0 。通过矩阵M变换你的空间如下变换S矩阵（下面的惯例是点是列向量）：

  A以原点为单位的半径球体表示为：
 S = [1 0 0 0] 
 [0 1 0 0] 
 [0 0 1 0] 
 [0 0 0 -1] 
 
点p在圆锥曲面上时：
 0 = p ^ t S p 
 = p ^ t M ^ t M ^ t ^ -1 SM ^ M 
 =（M p）^ t（M ^ -1 ^ t SM ^ -1）（M p）
 
变换点（M p）应保持发生率
  - >由矩阵M转换的圆锥曲线S是：（M ^ -1 ^ t SM ^ -1）
  

用于飞机而不是点的圆锥曲线的对偶表示为S的倒数;对于平面q（表示为行向量）：

 平面q在以下情况下与锥体相切：
 0 = （q M ^ -1）（MS ^  -  1）（1）其中， 1 M ^ t）（q M ^ -1）^ t 
 
变换平面（q M ^ -1）应保持发生率
  - >由矩阵M转换的双圆锥是：（MS ^ -1 M ^ t）
  

重新寻找与变换圆锥相切的轴对齐平面：

$ $ $ $ $ $ $ $ $ R = [r11 r12 r13 r14]（注意R是对称的：R = R ^ t）
[r12 r22 r23 r24]
[r13 r23 r33 r34]
[r14 r24 r34 r44 ]

轴对齐的平面是：
xy平面：[0 0 1 -z]
xz平面：[0 1 0 -y]
yz平面： [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对齐的飞机：

<$ p $ （r24 +/- sqrt（r24 ^ 2 - r44 r22））/ r44

和yz对齐的平面：

  x =（r14 +/- sqrt（r14 ^ 2  -  r44 r11））/ r44 
  

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

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?

解决方案

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.

这篇关于计算转换球体的AABB的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！