Calcolo di un AABB per una sfera trasformato
Domanda
Ho una sfera rappresentato in spazio oggetti da un punto centrale e un raggio. La sfera si trasforma in spazio di mondo con una matrice di trasformazione che può includere le scale, rotazioni, e traduzioni. Ho bisogno di costruire un asse allineato riquadro per la sfera nello spazio mondo, ma non sono sicuro di come farlo.
Ecco il mio approccio attuale, che funziona per alcuni casi:
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));
}
Comunque, io sono scettico che questo sarebbe sempre lavorare. Non dovrebbe fallire per scalatura non uniforme?
Soluzione
In generale, una sfera trasformato sarà un ellissoide di qualche tipo. Non è troppo difficile da ottenere un esatto riquadro di delimitazione per esso; se non si vuole passare attraverso tutto la matematica:
- Si noti che
M
è la vostra matrice di trasformazione (scale, rotazioni, traduzioni, ecc.) - leggere la definizione di
S
seguente -
R
calcolo come descritto verso la fine - calcolare la
x
,y
e limitiz
sulla base diR
come descritto scorso.
A conica generale (che comprende sfere e loro trasformate) può essere rappresentato come una matrice 4x4 simmetrica: un punto p
omogeneo è all'interno del S
conica quando p^t S p < 0
. Trasformando lo spazio per la matrice M trasforma la matrice S come segue (la convenzione sotto è che i punti sono vettori colonna):
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)
La doppia della conica, che si applica a piani invece di punti, è rappresentato dall'inverso di S; per aereo q (rappresentato come un vettore riga):
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)
Quindi, siete alla ricerca di aerei dell'Asse allineati che sono tangenti alla conica trasformato:
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 ]
Per trovare xy allineato piani tangenti a 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
Analogamente, per piani XZ-allineato:
y = (r24 +/- sqrt(r24^2 - r44 r22) ) / r44
e YZ-allineato:
x = (r14 +/- sqrt(r14^2 - r44 r11) ) / r44
Questo ti dà una casella di delimitazione esatta per la sfera trasformato.
Altri suggerimenti
Questo non funziona per il ridimensionamento non uniforme. E 'possibile calcolare per arbitraria affine invertibile trasformare con moltiplicatori di Lagrange (KKT teorema) e credo che otterrà brutto.
Tuttavia - sei sicuro avete bisogno di un esatto AABB? Si può approssimare che trasformando l'AABB originale della sfera e ottenere la sua AABB. E 'più grande della AABB esatto quindi potrebbe misura la vostra applicazione.
Per questo abbiamo bisogno di avere tre pseudo-funzioni:
GetAABB(sphere)
otterrà l'AABB di una sfera.
GetAABB(points-list)
otterrà l'AABB del dato insieme di punti (solo il min / max coordinate di tutti i punti).
GetAABBCorners(p, q)
otterrà tutti gli 8 punti angolo di un AABB (p e q sono tra loro).
(p, q) = GetAABB(sphere);
V = GetAABBCorners(p, q);
for i = 1 to 8 do
V[i] = Transform(T, V[i]);
(p, q) = GetAABB(V);
@ di comingstorm risposta è grande, ma può essere semplificato molto. Se M
è matrice di trasformazione della sfera, indicizzata da 1, allora
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)
(Premesso che la sfera aveva raggio 1 e il suo centro all'origine prima che fosse trasformato.)
ho scritto un post sul blog con la prova qui , che è troppo lungo per un ragionevole Stack Overflow risposta.