Расчет 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));
}

Однако я скептически отношусь к тому, что это всегда будет работать. Не должно ли это произойти из-за неравномерного масштабирования?

Answer 1

В общем, трансформированная сфера будет эллипсоидом некоторого вида.Нетрудно получить точную ограничивающую рамку для него;если вы не хотите проходить всю математику:

• обратите внимание, что M - это ваша матрица преобразования (масштаб, вращение, переводы и т. д.)
• прочитайте определениеS ниже
• вычислите R, как описано в конце
• вычислите границы x, y и z на основе R, как описано в прошлом.

---

Общая коника (которая включает сферы и их преобразования) может быть представлена ​​в виде симметричной матрицы 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 ]

НайтиВыровненные по xy плоскости, касательные к 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

Аналогично, для выровненных по xz плоскостей:

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

и выровненные по yz плоскости:

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

Thisдает вам точную ограничительную рамку для преобразованной сферы.

Answer 2

@ Ответ comestorm отличный, но его можно упростить. Если 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 и ее центр в начале координат до ее преобразования.)

Я написал пост в блоге с доказательством здесь , что слишком много для разумного ответа переполнения стека.

Answer 3

Это не будет работать для неравномерного масштабирования. Можно рассчитать для произвольного обратимого аффинного преобразования с множителями Лагранжа (теорема ККТ), и я верю, что это будет некрасиво.

Однако - вы уверены, что вам нужен точный AABB? Вы можете приблизить его, преобразовав исходную AABB сферы и получив ее AABB. Он больше, чем точная AABB, поэтому он может соответствовать вашему приложению.

Для этого нам нужно иметь три псевдофункции:

GetAABB(sphere) получит AABB сферы.

GetAABB(points-list) получит AABB заданного набора точек (только минимальные / максимальные координаты по всем точкам).

GetAABBCorners(p, q) получит все 8 угловых точек AABB (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);