Расчет 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 как описано выше.

---

общих коническое (которая включает в себя сферу и их преобразование) может быть представлена ​​в виде симметричной матрицы 4х4: однородная точка p находится внутри конического S когда это p^t S p < 0.Преобразование вашего пространства матрицы М преобразует матрицу 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; для плоскости д (представляются в виде вектора-строки):

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:

[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 

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

Answer 2

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

Однако, вы уверены, что вам нужен точный 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); 

Answer 3

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

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