13

オブジェクト空間で中心点と半径で表される球があります。球は、スケール、回転、および平行移動を含む可能性のある変換行列を使用して、ワールド空間に変換されます。ワールドスペースで球の軸に沿ったバウンディングボックスを作成する必要がありますが、その方法がわかりません。

これが私の現在のアプローチであり、いくつかのケースで機能します。

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

しかし、私はこれが常に機能するのではないかと疑っています。不均一なスケーリングで失敗するべきではありませんか？

4

4 に答える 4

13

一般に、変換された球はある種の楕円体になります。正確なバウンディング ボックスを取得するのはそれほど難しくありません。すべての計算を実行したくない場合:

  • M変換行列 (スケール、回転、平行移動など) であることに注意してください。
  • S以下の定義を読んでください
  • R最後に説明されているように計算します
  • 最後に説明した に基づいてx、y、および境界を計算します。zR

p一般的な円錐曲線 (球とその変換を含む) は、4x4 の対称行列として表すことができ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 ]

R に正接する xy 整列平面を見つけるには:

  [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

これにより、変換された球の正確なバウンディング ボックスが得られます。

于 2010-12-06T19:03:29.730 に答える
5

@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 で、その中心が変換前の原点にあると仮定しています。)

ここに証明を含むブログ投稿を書きましたが、合理的なスタック オーバーフローの回答には長すぎます。

于 2014-06-09T02:17:32.617 に答える
1

これは、不均一なスケーリングでは機能しません。ラグランジュ乗数（KKT定理）を使用して任意の可逆アフィン変換を計算することは可能ですが、それは醜くなると思います。

ただし、正確な AABB が必要ですか? 球の元の AABB を変換し、その AABB を取得することで近似できます。正確な AABB よりも大きいため、アプリケーションに適合する可能性があります。

このためには、3 つの疑似関数が必要です。

GetAABB(sphere)球の AABB を取得します。

GetAABB(points-list)指定されたポイント セットの AABB を取得します (すべてのポイントの最小/最大座標のみ)。

GetAABBCorners(p, q)AABB の 8 つの頂点すべてを取得します (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);
于 2010-12-06T17:34:16.907 に答える