Вычисление 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?
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));
}
Однако я скептически отношусь к тому, что это всегда будет работать.Разве это не должно привести к сбою из-за неравномерного масштабирования?
Решение
В общем случае преобразованная сфера будет представлять собой своего рода эллипсоид.Получить для него точную ограничивающую рамку не так уж сложно;если вы не хотите, пройдите всю математику:
- обратите внимание , что
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)
получит Абб-аффера.
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);
@ Ответ приходства велик, но может быть упрощен. Если 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 и его центр в начале, прежде чем он был преобразован.)
Я написал сообщение в блоге с доказательством здесь, что слишком много времени для разумного переполнения стека.