Cálculo de un AABB para una esfera transformado

Question

I tiene una esfera representado en el espacio objeto por un punto central y un radio. La esfera se transforma en el espacio mundo con una matriz de transformación que puede incluir escalas, rotaciones y traducciones. Necesito construir un eje alineado cuadro delimitador para la esfera en el espacio mundo, pero no estoy seguro de cómo hacerlo.

Aquí está mi enfoque actual, que funciona para algunos casos:

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

Sin embargo, soy escéptico de que esto siempre iba a funcionar. ¿No debería fallar por escalado no uniforme?

Answer 1

En general, una esfera transformado será un elipsoide de algún tipo. No es demasiado difícil conseguir una caja de delimitación exacta para ello; Si usted no quiere pasar por todos los cálculos:

• nota que M es su matriz de transformación (escalas, rotaciones, traducciones, etc.)
• leer la definición de S continuación
• R compute como se describe hacia el final
• calcular la x, y, y los límites z basado en R como se describe pasado.

---

A cónica general (que incluye esferas y sus transformadas) puede representarse como una matriz 4x4 simétrica: un punto p homogénea está dentro de la S cónica cuando p^t S p < 0. La transformación de su espacio por la matriz M transforma la matriz S como sigue (la convención de abajo es que los puntos son vectores de columna):

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)

El dual de la cónica, que se aplica a los planos en lugar de puntos, está representado por la inversa de S; para el plano q (representado como un vector fila):

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)

Por lo tanto, usted está en busca de aviones ejes alineados que son tangentes a la cónica transformado:

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 ]

Para encontrar xy alineado planos tangentes 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

Del mismo modo, para los planos XZ-alineado:

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

y planos YZ-alineado:

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

Esto le da una caja de delimitación exacta de la esfera transformado.

Answer 2

Esto no funcionará para el escalado no uniforme. Es posible calcular para afín inversible arbitraria transformar con multiplicadores de Lagrange (KKT teorema) y creo que va a poner feo.

Sin embargo - ¿está seguro de que necesita una AABB exacta? Se puede aproximar mediante la transformación de la AABB original de la esfera y conseguir su AABB. Es más grande que la AABB exacta por lo que puede adaptarse a su aplicación.

Para esto se necesita tener tres pseudo-funciones:

GetAABB(sphere) obtendrá la AABB de una esfera.

GetAABB(points-list) obtendrá la AABB del conjunto dado de puntos (sólo el min / max coordenadas sobre todos los puntos).

GetAABBCorners(p, q) obtendrá todos los 8 puntos de esquina de un AABB (p y q son, entre otros).

(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

respuesta

@ de comingstorm es grande, pero se puede simplificar mucho. Si M es matriz de transformación de la esfera, indexadas de 1, entonces

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)

(Esto asume la esfera tenía radio 1 y su centro en el origen antes de que se transformó.)

Me escribió una entrada de blog con la prueba aquí , que es mucho demasiado tiempo para una respuesta razonable de desbordamiento de pila.