2.9.4 Bounding box in movimento
Dato un Bounds3f che è trasformato da una trasformazione animata, è utile essere in grado di calcolare un bounding box che comprenda tutto il suo movimento durante il periodo di animazione. Per esempio, se possiamo delimitare il movimento di una primitiva geometrica animata, allora possiamo intersecare i raggi con questo limite per determinare se il raggio potrebbe intersecare l’oggetto prima di sostenere il costo di interpolare il limite della primitiva al tempo del raggio per controllare tale intersezione. Il metodo AnimatedTransform::MotionBounds() esegue questo calcolo, prendendo un rettangolo di delimitazione e restituendo il rettangolo di delimitazione del suo movimento nell’intervallo di tempo di AnimatedTransform.
AnimatedTransform 103
AnimatedTransform:: Interpolate() 106
AnimatedTransform:: MotionBounds() 108
AnimatedTransform::R 103
AnimatedTransform::S 103
Float 1062
Matricex4x4 1081
Point3f 68
Quaternion 99
Quaternion::ToTransform() 101
Ray 73
Ray::time 73
RayDifferential 75
Slerp() 103
Transform 83
Translate() 87
Vector3f 60
Ci sono due casi facili: primo, se le matrici keyframe sono uguali, allora possiamo applicare arbitrariamente solo la trasformazione di partenza per calcolare i limiti completi. In secondo luogo, se la trasformazione include solo lo scaling e/o la traslazione, allora il bounding box che comprende le posizioni trasformate del bounding box sia all’ora iniziale che a quella finale delimita tutto il suo movimento. Per vedere perché è così, consideriamo la posizione di un punto trasformato p in funzione del tempo; denoteremo questa funzione di due matrici, un punto e un tempo con a(M0, M1, p, t).
Siccome in questo caso la componente di rotazione della decomposizione è l’identità, allora con la nostra decomposizione della matrice abbiamo
dove la traduzione e la scala sono entrambe scritte come funzioni del tempo. Assumendo per semplicità che S(t) sia una scala regolare, possiamo trovare espressioni per le componenti di a(M0, M1, p, t). Per esempio, per la componente x, abbiamo:
where s0,0 è il corrispondente elemento della matrice di scala per M0, s0,0′ è lo stesso elemento della matrice di scala per M1, e gli elementi della matrice di traslazione sono analogamente indicati con d. (Abbiamo scelto d per “delta” qui, dato che t è già indicato come tempo.) Come funzione lineare di t, gli estremi di questa funzione si trovano ai tempi di inizio e fine. Le altre coordinate e il caso di una scala generalizzata seguono in modo simile.
〈 Definizioni del metodo AnimatedTransform〉 + ≡
Bounds3f AnimatedTransform::MotionBounds(const Bounds3f &b) const {
if (!actuallyAnimated)
return (*startTransform)(b);
if (hasRotation == false)
return Union((*startTransform)(b), (*endTransform)(b));
〈Return motion bounds accounting for animated rotation 108〉
}
Per il caso generale con rotazioni animate, la funzione motion può avere estremi in punti nel mezzo dell’intervallo di tempo. Non conosciamo un modo semplice per trovare questi punti. Molti renderer affrontano questo problema campionando un gran numero di volte nell’intervallo di tempo, calcolando la trasformazione interpolata in ognuna di esse, e prendendo l’unione di tutte le corrispondenti scatole di contorno trasformate. Qui, svilupperemo un metodo più fondato che ci permette di calcolare in modo robusto questi limiti di movimento.
Utilizziamo un limite conservativo leggermente più semplice che comporta il calcolo del movimento degli otto angoli del riquadro di delimitazione individualmente e trovare l’unione di questi limiti.
〈Ritorna i limiti del movimento tenendo conto della rotazione animata〉 ≡ 108
Bounds3f bounds;
for (int corner = 0; corner <8; ++corner)
bounds = Union(bounds, BoundPointMotion(b.Corner(corner));
return bounds;
Per ogni angolo del bounding box p, dobbiamo trovare gli estremi di a nell’intervallo di tempo dell’animazione. Ricordiamo dal calcolo che gli estremi di una funzione continua su un certo dominio sono o nei punti di confine del dominio o nei punti in cui la derivata prima della funzione è zero. Quindi, il limite complessivo è dato dall’unione delle posizioni all’inizio e alla fine del movimento, nonché dalla posizione agli eventuali estremi.
AnimatedTransform:: actuallyAnimated 103
AnimatedTransform:: BoundPointMotion() 110
AnimatedTransform:: hasRotation 103
Bounds3::Corner() 78
Bounds3::Union() 78
Bounds3f 76
Figura 2.18 mostra un grafico di una coordinata della funzione di moto e della sua derivata per un interessante percorso di moto di un punto. Si noti che il valore massimo della funzione nell’intervallo di tempo è raggiunto in un punto in cui la derivata ha uno zero.
Figura 2.18. (a) Movimento della coordinata x di un punto p in funzione del tempo, come determinato da due matrici keyframe. (b) La derivata della funzione di moto, Equazione (2.12). Si noti che gli estremi della funzione di moto nell’intervallo di tempo dato corrispondono agli zeri della derivata.
Per vincolare il moto di un singolo punto, iniziamo la nostra derivazione seguendo l’approccio usato per il caso senza rotazione, espandendo le tre componenti T, R e S dell’equazione (2.9) come funzioni del tempo e trovando il loro prodotto. Abbiamo:
Il risultato è abbastanza complesso se espanso, soprattutto a causa dello slerp e della conversione del quaternione risultante in una matrice; un sistema di algebra del computer è un requisito per lavorare con questa funzione.
Anche la derivata ∂a(M0, M1, p, t)/∂t è piuttosto complessa – nel suo pieno splendore algebrico, sono necessarie oltre 2.000 operazioni per valutare il suo valore per una data coppia di matrici decomposte, punto e tempo. Tuttavia, date specifiche matrici di trasformazione e un punto specifico, a si semplifica sostanzialmente; denoteremo la funzione specializzata di t da sola come aM, p(t). La valutazione della sua derivata richiede circa 10 operazioni in virgola mobile, un seno e un coseno da valutare per ogni coordinata:
dove θ è l’arco coseno del prodotto punto dei due quaternioni e dove i cinque coefficienti ci sono 3 vettori che dipendono dalle due matrici e dalla posizione p. Questa specializzazione funziona bene, poiché avremo bisogno di valutare la funzione a molti valori temporali per un dato punto.
Ora abbiamo due compiti: primo, data una coppia di matrici keyframe e un punto p, dobbiamo prima essere in grado di calcolare in modo efficiente i valori dei coefficienti ci. Poi, data la funzione relativamente semplice definita da ci e θ, abbiamo bisogno di trovare gli zeri dell’equazione (2.12), che possono rappresentare i tempi in cui si verificano gli estremi del movimento.
Per il primo compito, dobbiamo prima calcolare i contributi ai coefficienti che dipendono dalle matrici keyframe da quelli che dipendono dal punto p, assumendo che per ogni coppia di matrici keyframe (come in questo caso) vengano calcolati i limiti del movimento di più punti. Il risultato è fortunatamente abbastanza semplice – i vettori ci sono funzioni lineari delle componenti x, y e z del punto.
Quindi, dati i coefficienti ki e un particolare punto p di cui vogliamo limitare il movimento, possiamo calcolare in modo efficiente i coefficienti ci della funzione derivativa nell’equazione (2.12). La struttura DerivativeTerm incapsula questi coefficienti e questo calcolo.
〈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;
}
};
Gli attributi c1 – c5 memorizzano informazioni sulle derivate corrispondenti ai cinque termini dell’equazione (2.12). I tre elementi della matrice corrispondono alle tre dimensioni dello spazio.
〈AnimatedTransform Private Data〉 + ≡
DerivativeTerm c1, c2, c3, c4, c5;
Il frammento 〈Compute terms of motion derivative function〉 nel costruttore di AnimatedTransform, non incluso qui, inizializza questi termini, tramite codice generato automaticamente. Dato che richiede alcune migliaia di operazioni in virgola mobile, è utile fare questo lavoro una volta sola e ammortizzarlo su più angoli del bounding box. I coefficienti ki sono più facilmente calcolabili se assumiamo un intervallo di tempo canonico; in seguito, dovremo rimappare i valori t degli zeri della funzione di movimento all’intervallo di tempo effettivo dell’otturatore.
Dati i coefficienti ki basati sulle matrici dei keyframe, BoundPointMotion() calcola un limite robusto del movimento di p.
〈AnimatedTransform Method Definitions〉 + ≡
Bounds3f AnimatedTransform::BoundPointMotion(const Point3f &p) const {
Bounds3f bounds((*startTransform)(p), (*endTransform)(p));
Float cosTheta = Dot(R, R);
Float theta = std::acos(Clamp(cosTheta, -1, 1));
for (int c = 0; c <3; ++c) {
〈Trova gli zeri della derivata del moto per il componente c 111〉
〈Espandi il bounding box per gli zeri della derivata del moto trovati 111〉
}
return bounds;
}
Bounds3f 76
DerivativeTerm 110
Float 1062
Point3f 68
La funzione IntervalFindZeros(), che verrà introdotta tra poco, trova numericamente gli zeri dell’equazione (2.12). Sono possibili fino a quattro.
〈Trova eventuali zeri della derivata del moto per il componente c〉 ≡ 110
Float zeri;
int nZeros = 0;
IntervalFindZeros(c1.Eval(p), c2.Eval(p), c3.Eval(p), c4.Eval(p),
c5.Eval(p), theta,
Intervallo(0., 1.), zeri, &nZeri);
Gli zeri si trovano su t ∈ , quindi dobbiamo interpolare nell’intervallo di tempo prima di chiamare il metodo per trasformare il punto al tempo corrispondente. Notate anche che l’estremo è solo in una delle dimensioni x, y e z, e quindi i limiti devono essere aggiornati solo in quella dimensione. Per comodità, qui usiamo solo la funzione Union(), che considera tutte le dimensioni, anche se due potrebbero essere ignorate.
〈Expand bounding box for any motion derivative zeros found〉 ≡ 110
for (int i = 0; i <nZeros; ++i) {
Point3f pz = (*this)(Lerp(zeros, startTime, endTime), p);
bounds = Union(bounds, pz);
}
Trovare gli zeri della funzione derivata del moto, Equazione (2.12), non può essere fatto algebricamente; sono necessari metodi numerici. Fortunatamente, la funzione si comporta bene – è abbastanza liscia e ha un numero limitato di zeri. (Ricordate il grafico in figura 2.18, che era un rappresentante insolitamente complesso.)
Mentre potremmo usare una ricerca basata sulla bisezione o il metodo di Newton, rischieremmo di perdere degli zeri quando la funzione attraversa solo brevemente l’asse. Pertanto, useremo l’aritmetica degli intervalli, un’estensione dell’aritmetica che dà un’idea del comportamento delle funzioni su intervalli di valori, che rende possibile trovare in modo robusto gli zeri delle funzioni.
Per capire l’idea di base dell’aritmetica degli intervalli, consideriamo, per esempio, la funzione f (x) = 2x. Se abbiamo un intervallo di valori ∈ ℝ, allora possiamo vedere che sull’intervallo, l’intervallo di f è l’intervallo . In altre parole f () ⊂ .
Più in generale, tutte le operazioni di base dell’aritmetica hanno estensioni di intervallo che descrivono come operano sugli intervalli. Per esempio, dati due intervalli e ,
In altre parole, se sommiamo due valori dove uno è nell’intervallo e il secondo è in , allora il risultato deve essere nell’intervallo .
L’aritmetica degli intervalli ha l’importante proprietà che gli intervalli che dà sono conservativi. In particolare, se f () ⊂ e se c > 0, allora sappiamo per certo che nessun valore in causa f è negativo. Nel seguito, mostreremo come calcolare l’equazione (2.12) su intervalli e sfrutteremo i limiti conservativi degli intervalli calcolati per trovare in modo efficiente piccoli intervalli con incroci di zero dove i metodi regolari di ricerca delle radici possono essere usati in modo affidabile.
Prima di tutto definiremo una classe Interval che rappresenta intervalli di numeri reali.
Bounds3::Union() 78
Float 1062
Interval 112
IntervalFindZeros() 113
Lerp() 1079
Point3f 68
〈Interval Definitions〉 ≡
classe Interval {
public:
〈Interval Public Methods 112〉
Float low, high;
};
Un intervallo può essere inizializzato con un singolo valore, che rappresenta un singolo punto sulla linea dei numeri reali, o con due valori che specificano un intervallo con larghezza non nulla.
〈Intervallo Metodi pubblici〉 ≡ 112
Intervallo(Float v) : low(v), high(v) { }
Intervallo(Float v0, Float v1)
: low(std::min(v0, v1)), high(std::max(v0, v1)) { }
La classe fornisce anche degli overload per le operazioni aritmetiche di base. Notate che per la sottrazione, il valore alto del secondo intervallo viene sottratto dal valore basso del primo.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);
}
Per la moltiplicazione, quali lati di ogni intervallo determinano i valori minimi e massimi dell’intervallo risultato dipendono dai segni dei rispettivi valori. Moltiplicare le varie possibilità e prendere il minimo e il massimo complessivo è più facile che lavorare su quali usare e moltiplicare questi.
〈Interval Public Methods〉 + ≡ 112
Interval 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));
}
Abbiamo anche implementato le funzioni Sin() e Cos() per gli intervalli. Le implementazioni assumono che l’intervallo dato sia in , che è il caso per il nostro uso di queste funzioni. Qui includiamo solo l’implementazione di Sin(); Cos() è abbastanza simile nella struttura di base.
Float 1062
Intervallo 112
Intervallo::alto 112
Intervallo::low 112
〈Interval Definitions〉 + ≡
inline Interval Sin(const Interval &i) {
Float sinLow = std::sin(i.low), sinHigh = std::sin(i.high);
if (sinLow> sinHigh)
std::swap(sinLow, sinHigh);
if (i.low <Pi / 2 && i.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);
}
Dato il macchinario dell’intervallo, possiamo ora implementare la funzione IntervalFindZeros(), che trova i valori t di qualsiasi attraversamento dello zero dell’equazione (2.12) nell’intervallo tInterval dato.
〈Intervallo Definizioni〉 + ≡
void IntervalFindZeros(Float c1, Float c2, Float c3, Float c4,
Float c5, Float theta, Intervallo tIntervallo, Float *zeros,
int *zeroCount, int depth = 8) {
〈Valuta la derivata del moto in forma di intervallo, ritorna se non ci sono zeri 113〉
if (depth> 0) {
〈Dividere tInterval e controllare entrambi gli intervalli risultanti 114〉
} else {
〈Usa il metodo di Newton per raffinare lo zero 114〉
}
}
La funzione inizia calcolando l’intervallo su tInterval. Se l’intervallo non arriva a zero, allora non ci sono zeri della funzione su tInterval e la funzione può tornare.
〈Valuta la derivata del moto in forma di intervallo, ritorna se non ci sono zeri〉 ≡ 113
Intervallo = Intervallo(c1) +
(Intervallo(c2) + Intervallo(c3) * tIntervallo) *
Cos(Intervallo(2 * theta) * tIntervallo) +
(Intervallo(c4) + Intervallo(c5) * tIntervallo) *
Sin(Intervallo(2 * theta) * tIntervallo);
se (intervallo.low> 0. ∥ range.high <0. ∥ range.low == range.high)
return;
Se l’intervallo di intervallo si estende a zero, allora ci possono essere uno o più zeri nell’intervallo tInterval, ma è anche possibile che non ce ne siano, poiché i limiti di intervallo sono conservativi ma non il più stretto possibile. La funzione divide tInterval in due parti e controlla ricorsivamente i due sottointervalli. Riducendo la dimensione del dominio dell’intervallo si riduce generalmente l’estensione dell’intervallo, il che può permetterci di determinare che non ci sono zeri in uno o entrambi i nuovi intervalli.
Float 1062
Intervallo 112
Intervallo::alto 112
Intervallo::basso 112
Pi 1063
〈Split tInterval e controlla entrambi gli intervalli risultanti〉 ≡ 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), zeros, zeroCount, depth – 1);
Una volta che abbiamo un intervallo stretto in cui il valore dell’intervallo della funzione di derivazione del moto si estende a zero, l’implementazione passa ad alcune iterazioni del metodo di Newton per trovare lo zero, partendo dal punto medio dell’intervallo. Il metodo di Newton richiede la derivata della funzione; poiché stiamo trovando gli zeri della funzione derivata del moto, questa è la derivata seconda dell’equazione (2.11):
〈Usa il metodo di Newton per raffinare lo zero〉 ≡ 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.f * theta * tNewton) +
(c4 + c5 * tNewton) * std::sin(2.f * theta * tNewton);
Float fPrimeNewton =
(c3 + 2 * (c4 + c5 * tNewton) * theta) *
std::cos(2.f * tNewton * theta) +
(c5 – 2 * (c2 + c3 * tNewton) * theta) *
std::sin(2.f * tNewton * theta);
if (fNewton == 0 ∥ fPrimeNewton == 0)
break;
tNewton = tNewton – fNewton / fPrimeNewton;