2.9.4 Bounding moving bounding box
Egy animált transzformációval átalakított Bounds3f esetében hasznos, ha ki tudunk számítani egy olyan határoló dobozt, amely az animáció teljes mozgását magában foglalja az animációs időszak alatt. Ha például le tudjuk határolni egy animált geometriai primitív mozgását, akkor ezzel a határolással metszhetjük a sugarakat, hogy meghatározzuk, hogy a sugár metszheti-e az objektumot, mielőtt a primitív határolásának interpolálási költségei a sugár idejébe kerülnének, hogy ellenőrizzük a metszést. Az AnimatedTransform::MotionBounds() metódus végzi el ezt a számítást, fog egy határolódobozt, és visszaadja a mozgás határolódobozát az AnimatedTransform időtartományában.
AnimatedTransform 103
AnimatedTransform:: Interpolate() 106
AnimatedTransform:: MotionBounds() 108
AnimatedTransform::R 103
AnimatedTransform::S 103
Float 1062
Matrix4x4 1081
Point3f 68
Quaternion 99
Quaternion::ToTransform() 101
Ray 73
Ray::time 73
RayDifferential 75
Slerp() 103
Transform 83
Translate() 87
Vector3f 60
Két egyszerű eset van: Először is, ha a kulcskocka mátrixok egyenlőek, akkor tetszőlegesen csak a kezdő transzformációt alkalmazhatjuk a teljes korlátok kiszámításához. Másodszor, ha a transzformáció csak skálázást és/vagy transzlációt tartalmaz, akkor az a határoló doboz, amely a kezdő- és a végidőpontban is magában foglalja a határoló doboz transzformált pozícióit, korlátozza a teljes mozgást. Hogy lássuk, miért van ez így, tekintsük egy p transzformált pont helyzetét az idő függvényében; ezt a függvényt két mátrix, egy pont és egy idő függvényeként a(M0, M1, p, t) jelöljük.
Mivel ebben az esetben a dekompozíció forgatási komponense az azonosság, akkor a mátrixbontásunkkal
ahol a transzlációt és a skálát is az idő függvényeként írjuk fel. Ha az egyszerűség kedvéért feltételezzük, hogy S(t) egy szabályos skála, akkor kifejezést találhatunk az a(M0, M1, p, t) összetevőire. Például az x komponensre a következőket kapjuk:
where s0,0 a skálamátrix megfelelő eleme M0 esetében, s0,0′ ugyanez a skálamátrix eleme M1 esetében, a transzlációs mátrix elemeit pedig hasonlóképpen d-vel jelöljük. (A d-t itt a “delta” helyett választottuk, mivel a t-t már az időre állítjuk.) Mint a t lineáris függvénye, ennek a függvénynek a szélsőértékei a kezdő- és a végidőpontoknál vannak. A többi koordináta és az általánosított skála esete hasonlóan következik.
〈AnimatedTransform módszer definíciói〉 + ≡
Bounds3f AnimatedTransform::MotionBounds(const Bounds3f &b) const {
if (!actuallyAnimated)
return (*startTransform)(b);
if (hasRotation == false)
return Union((*startTransform)(b), (*endTransform)(b));
〈A mozgási határok visszaadása az animált forgás figyelembevételével 108〉
}
Az animált forgások általános esetére a mozgásfüggvénynek lehetnek szélsőértékei az időtartomány közepén lévő pontokban. Nem ismerünk egyszerű módszert arra, hogy ezeket a pontokat megtaláljuk. Sok renderelő úgy oldja meg ezt a problémát, hogy az időtartományban nagyszámú mintavételt végez, minden egyes alkalommal kiszámítja az interpolált transzformációt, és a megfelelő transzformált határoló dobozok unióját veszi. Itt egy megalapozottabb módszert fogunk kifejleszteni, amely lehetővé teszi, hogy robusztusan kiszámítsuk ezeket a mozgáshatárokat.
Egy valamivel egyszerűbb konzervatív korlátot használunk, amely azzal jár, hogy a határoló doboz nyolc sarkának mozgását egyenként kiszámítjuk, és ezek unióját keressük.
〈Az animált forgást figyelembe vevő mozgáshatárok visszaadása〉 ≡ 108
Bounds3f bounds;
for (int corner = 0; corner <8; ++corner)
bounds = Union(bounds, BoundPointMotion(b.Corner(corner))));
return bounds;
Minden p határoló doboz sarkához meg kell találnunk az a szélsőértékeit az animációs időtartományban. Emlékezzünk vissza a számtanból, hogy egy folytonos függvény szélsőértékei valamilyen tartományban vagy a tartomány határpontjaiban, vagy azokban a pontokban vannak, ahol a függvény első deriváltja nulla. Így a teljes korlátot a mozgás kezdetén és végén lévő pozíciók, valamint bármely szélsőértéknél lévő pozíció egyesítése adja.
AnimatedTransform:: actuallyAnimated 103
AnimatedTransform:: BoundPointMotion() 110
AnimatedTransform:: hasRotation 103
Bounds3::Corner() 78
Bounds3::Union() 78
Bounds3f 76
Figure 2.A 18. ábra a mozgásfüggvény egyik koordinátájának és deriváltjának ábrázolását mutatja egy pont érdekes mozgáspályájára. Vegyük észre, hogy a függvény maximális értékét az időtartományon belül egy olyan ponton érjük el, ahol a deriváltja nulla.
2.18. ábra. (a) Egy p pont x koordinátájának mozgása az idő függvényében, két kulcskoordinátamátrix által meghatározott módon. (b) A mozgásfüggvény deriváltja, (2.12. egyenlet). Megjegyezzük, hogy a mozgásfüggvény szélsőértékei az adott időtartományban a derivált nulla értékének felelnek meg.
Egyetlen pont mozgásának lehatárolásához a levezetést a forgás nélküli esetben alkalmazott megközelítéssel kezdjük, a (2.9) egyenlet három T, R és S komponensét az idő függvényeként kibontva és ezek szorzatát megtalálva. Megvan:
Az eredmény kibontva meglehetősen bonyolult, főként a slerp és a kapott kvaternion mátrixszá alakítása miatt; a függvénnyel való munkához számítógépes algebrai rendszer szükséges.
A ∂a(M0, M1, p, t)/∂t derivált szintén meglehetősen bonyolult – teljes algebrai pompájában több mint 2000 műveletre van szükség ahhoz, hogy értékét egy adott dekomponált mátrixpárra, pontra és időre kiértékeljük. Konkrét transzformációs mátrixok és egy adott pont esetén azonban az a jelentősen leegyszerűsödik; csak a t-re specializált függvényt aM, p(t)-ként jelöljük. Deriváltjának kiértékelése nagyjából 10 lebegőpontos műveletet, egy szinusz és egy koszinusz kiértékelését igényli minden egyes koordinátára:
ahol θ a két kvaternion pontprodukciójának ívkoszinusza, és ahol az öt együttható ci a két mátrixtól és a p pozíciótól függő 3 vektor. Ez a specializáció jól bevált, hiszen egy adott ponthoz sok időértéknél kell majd kiértékelnünk a függvényt.
Most két feladatunk van: először is, adott egy pár kulcskocka-mátrix és egy p pont, először is hatékonyan ki kell tudnunk számítani a ci együtthatók értékeit. Ezután a ci és θ által meghatározott viszonylag egyszerű függvényt tekintve meg kell találnunk a (2.12.) egyenlet nullpontjait, amelyek a mozgás szélsőértékeinek időpontját jelenthetik.
Az első feladathoz először a keyframe mátrixoktól függő együtthatókhoz való hozzájárulásokat faktoráljuk ki a p ponttól függő együtthatókból, feltételezve, hogy minden egyes keyframe mátrixpárhoz kiszámítjuk a több pont mozgásának határoló dobozait (mint ahogy ez itt is történik). Az eredmény szerencsére nagyon egyszerű – a ci vektorok a pont x, y és z komponensének lineáris függvényei.
Így a ki együtthatók és egy adott p pont, amelynek a mozgását korlátozni akarjuk, adottak a (2.12. egyenletben szereplő derivált függvény ci együtthatói hatékonyan kiszámíthatók.) A DerivativeTerm struktúra magában foglalja ezeket az együtthatókat és ezt a számítást.
〈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;
}
};
A c1 – c5 attribútumok a (2.12) egyenlet öt tagjának megfelelő derivált információt tárolják. A három tömbelem a tér három dimenziójának felel meg.
〈AnimatedTransform Private Data〉 + ≡
DerivativeTerm c1, c2, c3, c4, c5;
Az itt nem szereplő 〈Compute terms of motion derivative function〉 fragmentum az AnimatedTransform konstruktorban inicializálja ezeket a kifejezéseket, automatikusan generált kód segítségével. Tekintettel arra, hogy ez néhány ezer lebegőpontos műveletet igényel, hasznos, ha ezt a munkát egyszer végezzük el, és a több határoló doboz sarkára amortizáljuk. A ki együtthatókat könnyebben kiszámíthatjuk, ha kanonikus időtartományt feltételezünk ; később a mozgásfüggvény nulláinak t értékeit át kell alakítanunk a tényleges záridő tartományra.
A kulcskocka mátrixok alapján megadott ki együtthatók alapján a BoundPointMotion() kiszámítja a p mozgásának robusztus korlátját.
〈AnimatedTransform Módszer definíciói〉 + ≡
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) {
〈Minden mozgás derivált nullát keresünk a c komponenshez 111〉
〈Tágítsuk a határoló keretet minden talált mozgás derivált nullára 111〉
}
return bounds;
}
Bounds3f 76
DerivativeTerm 110
Float 1062
Point3f 68
A rövidesen bemutatásra kerülő IntervalFindZeros() függvény numerikusan keresi az egyenlet (2.12). Legfeljebb négy lehetséges.
〈A c〉 ≡ 110
IntervalFindZeros bármely mozgás deriváltjának zérusait megtalálni;
int nZeros = 0;
IntervalFindZeros(c1.Eval(p), c2.Eval(p), c3.Eval(p), c4.Eval(p),
c5.Eval(p), theta,
Interval(0., 1.), zeros, &nZeros);
A nullák megtalálása t ∈ alatt történik, ezért interpolálnunk kell az időtartományon belül, mielőtt meghívjuk a módszert a pont megfelelő időpontban történő átalakítására. Vegyük észre azt is, hogy a szélsőérték csak az x, y és z dimenziók egyikében van, így a határokat csak ebben az egy dimenzióban kell frissíteni. Az egyszerűség kedvéért itt csak az Union() függvényt használjuk, amely minden dimenziót figyelembe vesz, bár kettőt figyelmen kívül is hagyhatnánk.
〈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);
határok = Union(határok, pz);
}
A mozgás derivált függvényének nullpontjainak megtalálása, egyenlet (2.12), nem végezhető el algebrai úton; numerikus módszerekre van szükség. Szerencsére a függvény jól viselkedik – meglehetősen sima és korlátozott számú nullpontja van. (Emlékezzünk a 2.18. ábrán látható ábrára, amely egy szokatlanul összetett képviselő volt.)
Míg használhatnánk egy felező alapú keresést vagy Newton-módszert, megkockáztatnánk, hogy kihagynánk nullákat, amikor a függvény csak rövid ideig keresztezi a tengelyt. Ezért az intervallumaritmetikát fogjuk használni, az aritmetika egy olyan kiterjesztését, amely betekintést nyújt a függvények értéktartományok feletti viselkedésébe, ami lehetővé teszi a függvények nullpontjainak robusztus megtalálását.
Az intervallumaritmetika alapgondolatának megértéséhez tekintsük például az f (x) = 2x függvényt. Ha van egy ∈ ℝ értékű intervallumunk, akkor láthatjuk, hogy az intervallumon belül f tartománya az intervallum . Más szóval f () ⊂ .
Általánosabban, az aritmetika minden alapműveletének vannak intervallumkiterjesztései, amelyek leírják, hogyan működnek intervallumokon. Például adott két intervallum és ,
Más szóval, ha összeadunk két értéket, amelyek közül az egyik a tartományban van, a másik pedig a , akkor az eredménynek a .
intervallum-aritmetika fontos tulajdonsága, hogy az általa adott intervallumok konzervatívak. Különösen, ha f () ⊂ és ha c > 0, akkor biztosan tudjuk, hogy nincs olyan érték a-ban, ami miatt f negatív lenne. A következőkben megmutatjuk, hogyan lehet a (2.12) egyenletet intervallumokon keresztül kiszámítani, és kihasználjuk a kiszámított intervallumok konzervatív határait, hogy hatékonyan találjunk olyan zérusátmenettel rendelkező kis intervallumokat, ahol a szokásos gyökkeresési módszerek megbízhatóan használhatók.
Először definiálunk egy Intervallum osztályt, amely valós számok intervallumait reprezentálja.
Bounds3::Union() 78
Float 1062
Intervallum 112
IntervalFindZeros() 113
Lerp() 1079
Point3f 68
〈Intervall Definitions〉 ≡
class Interval {
public:
〈Interval Public Methods 112〉
Float low, high;
};
Egy intervallum inicializálható egyetlen értékkel, ami a valós számegyenes egyetlen pontját jelenti, vagy két értékkel, ami egy nem nulla szélességű intervallumot határoz meg.
〈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)) { }
Az osztály túlterhelést biztosít az alapvető aritmetikai műveletekhez is. Vegyük észre, hogy a kivonásnál a második intervallum nagy értéke kivonásra kerül az első intervallum kis értékéből.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);
}
A szorzásnál az adott értékek előjelétől függ, hogy az egyes intervallumok mely oldalai határozzák meg az eredményintervallum minimális és maximális értékét. A különböző lehetőségek szorzása és az összminimum és -maximum figyelembevétele egyszerűbb, mint annak kidolgozása, hogy melyiket használjuk, és ezek szorzása.
〈Intervallum nyilvános módszerek〉 + ≡ 112
Intervallum operator*(const Intervallum &i) const {
return Intervallum(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)));
}
Az intervallumok Sin() és Cos() függvényeit is implementáltuk. Az implementációk feltételezik, hogy az adott intervallum a , ami a mi használatunkban ezeknek a függvényeknek az esete. Itt csak a Sin() implementációját közöljük; a Cos() alapstruktúrája meglehetősen hasonló.
Float 1062
Intervallum 112
Intervallum::high 112
Intervallum::low 112
〈Intervallum 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);
}
Az intervallumgépezetet megadva most implementálhatjuk az IntervalFindZeros() függvényt, amely a (2.12) egyenlet bármely zérusátmenetének t értékét megtalálja a megadott tIntervallumon.
〈Intervallum meghatározások〉 + ≡
void IntervalFindZeros(Float c1, Float c2, Float c3, Float c4,
Float c5, Float theta, Interval tInterval, Float *zeros,
int *zeroCount, int depth = 8) {
〈Mozgás deriváltjának kiértékelése intervallum formában, visszatér, ha nincs nulla 113〉
if (depth> 0) {
〈felosztja a tIntervallumot és ellenőrzi mindkét kapott intervallumot 114〉
} else {
〈A Newton-módszert használjuk a nulla finomítására 114〉
}
}
A függvény a tIntervallum intervallumtartományának kiszámításával kezdődik. Ha a tartomány nem terjed ki nullára, akkor a tInterval fölött a függvénynek nincsenek nullái, és a függvény visszatérhet.
〈A mozgás deriváltjának kiértékelése intervallumos formában, visszatér, ha nincsenek nullák〉 ≡ 113
Intervallumtartomány = Intervallum(c1) +
(Intervallum(c2) + Intervallum(c3) * tIntervallum) *
Cos(Interval(2 * theta) * tInterval) +
(Interval(c4) + Interval(c5) * tInterval) *
Sin(Interval(2 * theta) * tInterval);
if (range.low> 0. ∥ range.high <0. ∥ range.low == range.high)
return;
Ha az intervallumtartomány valóban átfogja a nullát, akkor a tInterval intervallumban lehet egy vagy több nulla, de az is lehet, hogy valójában nincs is, hiszen az intervallumhatárok konzervatívak, de nem a lehető legszűkebbek. A függvény a tIntervallumot két részre osztja, és rekurzívan ellenőrzi a két részintervallumot. Az intervallumtartomány méretének csökkentése általában csökkenti az intervallumtartomány kiterjedését, ami lehetővé teheti annak megállapítását, hogy az egyik vagy mindkét új intervallumban nincsenek nullák.
Float 1062
Intervallum 112
Intervallum::high 112
Intervallum::low 112
Pi 1063
〈Split tInterval and check both resulting intervals〉 ≡ 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);
Mihelyt van egy szűk intervallumunk, ahol a mozgás derivált függvényének intervallumértéke nullára terjed ki, a megvalósítás áttér a Newton-módszer néhány iterációjára a nulla megtalálásához, az intervallum középpontjából kiindulva. A Newton-módszerhez szükség van a függvény deriváltjára; mivel a mozgás derivált függvény zérusát keressük, ez a (2.11) egyenlet második deriváltja:
〈A Newton-módszer használata a nulla finomítására〉 ≡ 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;