Le calcul d'une AABB pour une sphère transformée

Question

I ont une sphère représentée dans l'espace de l'objet en un point central et un rayon. La sphère se transforme en espace mondial avec une matrice de transformation qui peut inclure des échelles, des rotations et des traductions. Je dois construire un axe cadre de délimitation aligné pour la sphère dans l'espace mondial, mais je ne suis pas sûr de savoir comment le faire.

Voici mon approche actuelle, qui fonctionne pour certains cas:

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

Cependant, je suis sceptique que cela fonctionnera toujours. Ne devrait pas échouer à l'échelle non uniforme?

Answer 1

En général, une sphère sera transformé un ellipsoïde de quelque sorte. Il est pas trop difficile d'obtenir un cadre de délimitation exacte pour elle; si vous ne voulez pas passer par toutes les mathématiques:

• Notez que M est votre matrice de transformation (échelles, rotations, traductions, etc.)
• lire la définition de S ci-dessous
• R calcul telle que décrite à la fin
• calculer la x, y, et les limites de z basée sur R comme décrit dernier.

---

conique générale (qui comprend les sphères et leurs transformées) peut être représenté comme une matrice 4x4 symétrique: un point homogène p est à l'intérieur du S conique lorsque p^t S p < 0. Transformer votre espace par la matrice M transforme la matrice S comme suit (la convention est inférieure à celle des points sont des vecteurs de colonne):

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)

Le double de la conique, applicable à des plans au lieu des points est représentée par l'inverse de S; pour le plan q (représenté par un vecteur de ligne):

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)

Alors, vous êtes à la recherche d'avions alignés axe qui sont tangentes à la conique transformée:

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 ]

Pour plans tangents aligné 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

De même, pour les avions alignés XZ-:

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

et des plans YZ-alignés:

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

Cela vous donne une zone de délimitation exacte de la sphère transformé.

Answer 2

Cela ne fonctionnera pas pour mise à l'échelle non uniforme. Il est possible de calculer pour transformer affines inversible arbitraire avec des multiplicateurs de Lagrange (théorème KKT) et je crois qu'il va devenir laid.

Cependant - êtes-vous sûr que vous avez besoin d'un AABB exact? Vous pouvez approximer en transformant l'AABB d'origine de la sphère et obtenir son AABB. Il est plus grand que l'AABB exacte de sorte qu'il pourrait adapter à votre application.

Pour cela, nous devons avoir trois pseudo-fonctions:

GetAABB(sphere) obtiendra l'AABB d'une sphère.

GetAABB(points-list) obtiendra le AABB de l'ensemble donné de points (juste les coordonnées min / max sur tous les points).

GetAABBCorners(p, q) obtiendra tous les 8 points d'angle d'un AABB (p et q sont parmi eux).

(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

La réponse de

@ comingstorm est grande, mais peut être beaucoup simplifié. Si M est la matrice de transformation de la sphère, indexée de 1, puis

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)

(ce qui suppose la sphère avait un rayon de 1 et de son centre à l'origine avant qu'il ne soit transformé.)

J'ai écrit un billet de blog la preuve ici , ce qui est beaucoup trop long pour une réponse raisonnable Stack Overflow.