Bounding Box

2.9.4 Bounding moving bounding boxes

アニメーション変換されたBounds3fがあると、アニメーション期間中のすべての動きを包含する境界ボックスを計算できるのは便利なことです。 たとえば、アニメーション化されたジオメトリック プリミティブのモーションをバウンディングできれば、プリミティブのバウンドをレイの時間に補間して交差を確認するコストが発生する前に、このバウンドでレイを交差させてオブジェクトと交差する可能性があるかどうかを判断することができます。 AnimatedTransform::MotionBounds() メソッドはこの計算を実行し、バウンディングボックスを取り、AnimatedTransform の時間範囲にわたるその動きのバウンディングボックスを返す。 Interpolate() 106

AnimatedTransform:: MotionBounds() 108

AnimatedTransform::R 103

AnimatedTransform::R (アニメートトランスフォーム)。S 103

Float 1062

Matrix4x4 1081

Point3f 68

クォータニオン 99

Quaternion::ToTransform() 101

Ray 73

Ray::time 73

RayDifferential 75

Slerp() 103

Transform 83

Translate() 87

Vector3f 60

簡単に言うと2つのケースがあります。 第一に、キーフレーム行列が等しい場合、任意に開始変換のみを適用して完全な境界を計算することができます。 2 つ目は、変換にスケーリングおよび/または移動のみが含まれる場合、開始時刻と終了時刻の両方で境界ボックスの変換された位置を包含する境界ボックスが、そのすべての動きを境界します。 なぜそうなるかを見るために、変換された点pの位置を時間の関数として考えてみましょう。この2つの行列、点、時間の関数をa(M0, M1, p, t)と表記します。

この場合、分解の回転成分は恒等式なので、行列分解で

aM0M1pt=TtStp,

ここで移動とスケールは両方とも時間の関数として書かれています。 簡単のためにS(t)を通常のスケールと仮定すると、a(M0, M1, p, t)の成分の式が求まる。 例えば、x成分については、次のようになる。

aM0M1ptx=1−ts0,0+ts0,0′px+1−td0,3+td0,3′=s0,0px+d0,3+−s0,0px+s0,0′px−d0,3+d0,3′t,

where s0,0はM0のスケール行列の対応する要素、s0,0′はM1の同じスケール行列の要素、並進行列の要素も同様にdで示される。 (tはすでに時間を表しているので、ここではdをデルタとした)tの一次関数として、この関数の極値は開始時刻と終了時刻にある。

〈AnimatedTransformメソッドの定義〉 + ≡

Bounds3f AnimatedTransform::MotionBounds(const Bounds3f &b) const {

if (!actuallyAnimated)

return (*startTransform)(b);

if (hasRotation == false)

return Union((*startTransform)(b), (*endTransform)(b));

〈回転アニメーションを考慮した運動量を返す 108〉

}

回転アニメーションを含む一般的な場合、運動関数は時間範囲の真ん中の点で極値を持つことがあります。 これらのポイントを見つける簡単な方法を私たちは知りません。 多くのレンダラーは、時間範囲内の多数の時間をサンプリングし、それぞれで補間された変換を計算し、対応するすべての変換されたバウンディングボックスの和を取ることによって、この問題に対処しています。 ここでは、これらの運動境界を堅牢に計算することができる、より根拠のある方法を開発する。

我々は、バウンディングボックスの8つの角の運動を個別に計算し、それらの境界の和を求めるという、少し簡単な保守的境界を使用する。

〈アニメーションの回転を考慮した運動量を返す〉≡108

Bounds3f bounds;

for (int corner = 0; corner <8; ++corner)

bounds = Union(bounds, BoundPointMotion(b. Bounds)).Corner(corner));

return bounds;

各バウンディングボックスのコーナーpについて、アニメーション時間範囲におけるaの極値を見つける必要があります。 微積分学で、ある領域上の連続関数の極値は、領域の境界点か、関数の一次導関数がゼロになる点のどちらかにあることを思い出してください。 したがって、全体の境界は、動きの開始と終了時の位置と、任意の極値での位置の和で与えられる。

AnimatedTransform:: actuallyAnimated 103

AnimatedTransform::: BoundPointMotion() 110

AnimatedTransform:: hasRotation 103

Bounds3::Corner() 78

Bounds3::Union() 78

Bounds3f 76

図2.Bounds3::Curr:Bound() 78

図2.18は、ある点の興味深い運動経路について、運動関数とその導関数の1つの座標をプロットしたものである。 時間範囲にわたる関数の最大値は、微分がゼロになる点で到達していることに注意。

図2.18。 (a)2つのキーフレームマトリックスで決まる点pのx座標の時間関数としての動き。 (b)運動関数の微分,式(2.12)である。

1点の動きを拘束するために、無回転の場合に用いたアプローチに従って、式(2.9)のT、R、S成分の3つを時間の関数として展開し、それらの積を求めることから導出を開始します。 5656>

aM0M1pt=TtRtStpとなる。

この結果は展開するとかなり複雑で、そのほとんどがスラープと結果の四元数から行列への変換によるもので、この関数を扱うにはコンピュータ代数システムが必要条件となる。

微分 ∂a(M0, M1, p, t)/∂t も非常に複雑で、その完全な代数的栄光は、与えられた分解行列のペア、ポイントと時間についてその値を評価するために 2,000 以上の演算が必要です。 しかし、特定の変換行列と特定の点が与えられると、a は大幅に簡略化されます。ここでは、t のみの特殊な関数を aM, p(t) と表記します。 その微分を評価するには、各座標について評価するために、およそ10の浮動小数点演算、サイン、コサインが必要です:

daM,ptdt=c1+c2+c3tcos2θt+c4+c5tsin2θt,

ここでθは二つの四元数のドットプロダクトのarc cosine、5つの係数ciは二つの行列と位置pに依存する3-ベクトルとします。

ここで、2 つのタスクがあります。まず、キーフレーム行列のペアと点 p が与えられたら、最初に係数 ci の値を効率的に計算できるようにする必要があります。

最初の課題として、まず、キーフレーム行列のペアごとに複数の点の動きに対するバウンディングボックスが計算される(今回のケース)と仮定して、キーフレーム行列に依存する係数の寄与を点pに依存する係数から除外することにします。

cip=ki,c+ki,xpx+ki,ypy+ki,zpz.

したがって、ki 係数と動きを拘束したい特定の点 p があれば、式 (2.12) の導関数係数 ci を効率的に計算することができます。 DerivativeTerm構造体は、これらの係数とこの計算をカプセル化します。

〈AnimatedTransform Private Data〉 + ≡

struct DerivativeTerm {

DerivativeTerm(Float c, Float x, Float y, Float z)

: kc(c), kx(x), ky(y), kz(z) { }

Float kc, kx, ky, kz;

Float Eval(const Point3f &p) const {

return kc + kx * p.x + ky * p.y + kz * p.z;

};

属性c1〜c5には式(2.12)の5項に対応する微分情報が格納されます。) 3つの配列要素は空間の3次元に対応する。

〈AnimatedTransform Private Data〉+≡〈5656> DerivativeTerm c1, c2, c3, c4, c5;

ここに含まれていないAnimatedTransformコンストラクタ内の断片〈Compute terms of motion derivative function〉は自動生成コードでこれらの項の初期化をしています。 数千の浮動小数点演算を必要とすることを考えると、この作業を一度だけ行い、複数のバウンディング ボックス コーナーに渡って償却することは有用です。 ki 係数は、標準的な時間範囲を想定すると、より簡単に計算できます。後で、運動関数のゼロの t 値を実際のシャッター時間範囲にマッピングし直す必要があります。

〈AnimatedTransformメソッドの定義〉 + ≡

Bounds3f AnimatedTransform::BoundPointMotion(const Point3f &p) const {

Bounds3f bounds((*startTransform)(p), (*endTransform)(p));

Float cosTheta = Dot(R, R);

Float theta = std:.R;

BoundPointMotion((*startTransform)(p));

Float theta = std::acos(Clamp(cosTheta, -1, 1));

for (int c = 0; c <3; ++c) {

〈成分cの運動微分ゼロを探す 111〉

〈見つかった運動微分ゼロに対して境界ボックスを広げる 111〉

}

boundsを返す。

}

Bounds3f 76

DerivativeTerm 110

Float 1062

Point3f 68

続いてご紹介する IntervalFindZeros() 関数は式 (2.) の 0 番を数値的に検出する関数であります。12).

〈成分cの運動微分ゼロを探す〉≡110

Float zeros;

int nZeros = 0;

IntervalFindZeros(c1.Zeros);

〈成分cの運動微分ゼロを探す〉≡110

Float zeros;

nZeros = 0;〈成分cの運動微分ゼロを探す〉≡110Eval(p), c2.Eval(p), c3.Eval(p), c4.Eval(p),

c5.Eval(p), theta,

Interval(0., 1.), zeros, &nZeros);

ゼロはt∈にわたって求められるので、対応する時刻に点を変換するメソッドを呼ぶ前に時間範囲内で補間しておく必要があります。 また、極限はx,y,zのうち1次元にしかないので、その1次元で境界を更新するだけでよいことに注意してください。 便宜上、ここでは、2次元は無視できてもすべての次元を考慮するUnion()関数を使用します。

〈見つかった運動微分ゼロの境界ボックスを拡張する〉≡110

for (int i = 0; i <nZeros; ++i) {

Point3f pz = (*this)(Lerp(zeros, startTime, endTime), p);

bounds = Union(bounds, pz);

}

運動微分関数のゼロを求める、式(2.12)の零点を求めるには、代数的な計算では無理であり、数値的な方法が必要である。 幸いなことに、この関数は挙動がよく、かなり滑らかで、ゼロの数も限られている。 (異常に複雑な代表であった図2.18のプロットを思い出してください。)

2分割法による探索やニュートン法を使うことができますが、関数が軸を一時的に横切るだけでは、0を見逃す危険性があります。 そこで、算術の拡張で、値の範囲に対する関数の振る舞いを洞察する区間算術を使うことで、関数のゼロをロバストに見つけることが可能になる。

区間算術の基本概念を理解するために、例えば、関数f (x) = 2xを考える。 値の区間∈ℝがあれば、その区間では、fの範囲は区間.となることがわかる。 つまり、f () ⊂ .

より一般的には、算術の基本操作はすべて、区間に対してどのように操作するかを記述する区間拡張を持つ。 例えば、2つの区間と ,

ab+cd⊂a+c,b+d.

言い換えれば、1つが範囲内にあり2つ目が , にある2つの値を一緒に足せば、結果は範囲 .

区間演算は、それが与える区間が保守的であるという重要な特性を持っている。 特に、f () ⊂とc > 0であれば、fが負になるような値はないことが確実にわかる。 以下では、区間上で式(2.12)を計算する方法を示し、計算された区間の保守的な境界を利用して、通常のルート探索法が確実に使用できるゼロクロスを持つ小さな区間を効率的に見つけることを目指す。

Bounds3::Union() 78

Float 1062

Interval 112

IntervalFindZeros() 113

Lerp() 1079

Point3f 68

〈インターバルの定義〉≡

class Interval {

public:

〈Interval Public Methods 112〉

〈7662〉 Float low, high;

};実数直線上の1点を表す1つの値、または0以外の幅を持つ区間を指定する2つの値で初期化されることがあります。

〈Interval Public Methods〉≡112

Interval(Float v) : low(v), high(v) { }

Interval(Float v0, Float v1)

: low(std::min(v0, v1)), high(std::max(v0, v1)) { }

このクラスは基本的な算術演算のオーバーロードも提供している。 引き算の場合、2番目の区間の高い値が1番目の区間の低い値から引き算されることに注意してください3。

〈Interval Public Methods〉 + ≡ 112

Interval operator + (const Interval &i) const {

return Interval(low + i.low, high + i.high);

}

Interval operator-(const Interval &i) const {

return Interval(low – i.).high, high – i.low);

}

乗算の場合、各区間のどの辺が結果区間の最小値と最大値を決めるかは、それぞれの値の符号に依存する。

〈Interval Public Methods〉+≡112

インターバル operator*(const Interval &i) const {

return Interval(std::min(std::min(low * i.low, high * i.low),

std::min(low * i.high, high * i.high)),

std::max(std::max(low * i.low, high * i.low),

std::max(low * i.high, high * i.high))).を返送します。

}

また、Intervals用の関数としてSin()とCos()を実装しています。 これらの実装は与えられた間隔が , であることを仮定しており、これらの関数の使用はこれに当てはまります。 ここでは、Sin() の実装のみを記載します。Cos() は基本的な構造において非常によく似ています。

Float 1062

Interval 112

Interval::high 112

Interval::low 112

〈Interval Definitions〉 + ≡

inline Interval Sin(const Interval &i) {

Float sinLow = std::sin(i.X) {

Inline Interval Sin(const Interval &i.low), sinHigh = std::sin(i.high);

if (sinLow> sinHigh)

std::swap(sinLow, sinHigh);

if (i.low <Pi / 2 && i.low), (i.high), (i.high), (sinLow> sinHigh);

if(singLow>sin)、(sinLow>sin)。high> Pi / 2)

sinHigh = 1.;

if (i.low <(3.f / 2.f) * Pi && i.high> (3.f / 2.f) * Pi)

sinLow = -1.;

return Interval(sinLow, sinHigh);

}

間隔機械が与えられると、今度は与えられた間隔tIntervalにわたって式(2.12)の任意のゼロクロスのt値を見つけるIntervalFindZeros()関数を実装することができます。

〈区間定義〉+≡

void IntervalFindZeros(Float c1, Float c2, Float c3, Float c4,

Float c5.Float c1, Float c2, Float c3, Float c4, Float c4), Float theta, Interval tInterval, Float *zeros,

int *zeroCount, int depth = 8) {

〈運動微分を区間形式で評価する。 ゼロがなければ戻る 113〉

if (depth> 0) {

〈tIntervalを分割し、できた両方の区間をチェック 114〉

} else {

〈ニュートン法でゼロを絞り込む 114〉

}

この関数はまずtIntervalの区間範囲を計算することから始まる。 もし範囲が0に及ばないなら、tInterval上の関数の0は存在せず、関数は戻ることができます。

〈区間形式での運動微分を評価する。 ゼロでなければ戻る〉≡113

区間範囲 = 区間(c1) +

(区間(c2) + 区間(c3) * tInterval) *

区間? Cos(Interval(2 * θ) * tInterval) +

(Interval(c4) + Interval(c5) * tInterval) *

Sin(Interval(2 * θ) * tInterval)の場合。

if (range.low> 0. ∥ range.high <0. ∥ range.low == range.high)

return;

区間の範囲がゼロに及ぶ場合、間隔 tInterval に一つ以上のゼロがあるかもしれませんが、間隔の境界は保守的ですができるだけタイトではないので実際には何もないこともありえます。 この関数は,tIntervalを2つに分割し,その2つの部分区間を再帰的にチェックします. 区間領域のサイズを小さくすることは、一般的に区間範囲の範囲を小さくします。これにより、新しい区間の一方または両方に0がないことを決定することができるかもしれません。

Float 1062

Interval 112

Interval::high 112

Interval::low 112

Pi 1063

〈tIntervalを分割して、できた両方の区間をチェック〉≡113

Float mid = (tInterval.low + tInterval.high) * 0.5f;

IntervalFindZeros(c1, c2, c3, c4, c5, theta,

Interval(tInterval.low, mid), zeros, zeroCount, depth – 1);

IntervalFindZeros(c1, c2, c3, c4, c5, theta,

Interval(mid, tInterval.high, thea),

Interval(tInterval.low), zeros, zeroCount, depth – 1);

インターバルファインダーを使用することにより、インターバルファインダーを使用することができます。high), zeros, zeroCount, depth – 1);

運動微分関数の区間値がゼロにまたがる狭い区間ができると、実装は、区間の中間点からゼロを見つけるニュートン法の数回の反復に切り替わります。 ニュートン法では関数の導関数が必要で、運動微分関数のゼロを求めるので、これは式(2.11)の2次導関数になります:

d2aM,ptdt2=c3,x+2θc4,x+c5,xtcos2θt+c5,x-2θc2,x+c3,xtsin2θt.

〈ニュートン法でゼロを絞り込む〉≡113

Float tNewton = (tInterval.low + tInterval.high) * 0.5f;

for (int i = 0; i <4; ++i) {

Float fNewton = c1 +

(c2 + c3 * tNewton) * std::cos(2.2.f * theta * tNewton) +

(c4 + c5 * tNewton) * std::sin(2.f * theta * tNewton);

Float fPrimeNewton =

(c3 + 2 * (c4 + c5 * tNewton) * theta) *

std::cos(2.a * c2 + c3 * theta *tNewton)f * tNewton * theta) +

(c5 – 2 * (c2 + c3 * tNewton) * theta) *

std::sin(2.Newton:cos)(c5:cos:cos:tNewton:θ)。f * tNewton * theta);

if (fNewton == 0 ∥ fPrimeNewton == 0)

break;

tNewton = tNewton – fNewton / fPrimeNewton;

fNewton * fPrimeNewton == 0

コメントする