Вычисление AABB для трансформированной сферы

Я имею сферу, представленную в пространстве объектов, центральной точкой и радиусом. Сфера преобразуется в мировое пространство с матрицей преобразования, которая может включать в себя масштабы, вращения и переводы. Мне нужно построить ориентированную по оси рамку для сферы в мировом пространстве, но я не уверен, как это сделать.

Вот мой текущий подход, который работает в некоторых случаях:

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

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

3 ответа

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

  • обратите внимание, что 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

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


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

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

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

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

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

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


@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 и ее центр в начале координат до того, как он был преобразован.)

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

licensed under cc by-sa 3.0 with attribution.