2.9.4 Bounding bewegende bounding boxes
Gegeven aan een Bounds3f die getransformeerd is door een geanimeerde transformatie, is het nuttig om een bounding box te kunnen berekenen die al zijn beweging over de animatie-tijdsperiode omvat. Indien we bijvoorbeeld de beweging van een geanimeerde geometrische primitieve kunnen begrenzen, dan kunnen we stralen doorsnijden met deze begrenzing om te bepalen of de straal het object zou kunnen doorsnijden alvorens de kosten op te lopen van het interpoleren van de begrenzing van de primitieve naar de tijd van de straal om die doorsnijding te controleren. De AnimatedTransform::MotionBounds() methode voert deze berekening uit, waarbij een bounding box wordt genomen en de bounding box van zijn beweging over het tijdbereik van de AnimatedTransform wordt teruggegeven.
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::tijd 73
RayDifferential 75
Slerp() 103
Transform 83
Translate() 87
Vector3f 60
Er zijn twee makkelijke gevallen: Ten eerste, als de keyframe matrices gelijk zijn, dan kunnen we willekeurig alleen de starttransformatie toepassen om de volledige grenzen te berekenen. Ten tweede, als de transformatie alleen schaling en/of translatie bevat, dan begrenst de bounding box die de getransformeerde posities van de bounding box op zowel de starttijd als de eindtijd omvat, al zijn beweging. Om te zien waarom dit zo is, beschouwen we de positie van een getransformeerd punt p als een functie van de tijd; we zullen deze functie van twee matrices, een punt, en een tijd aanduiden met a(M0, M1, p, t).
Omdat in dit geval de rotatiecomponent van de decompositie de identiteit is, hebben we met onze matrixdecompositie
waarbij de translatie en de schaal beide geschreven zijn als functies van de tijd. In de eenvoudige veronderstelling dat S(t) een regelmatige schaal is, kunnen we uitdrukkingen vinden voor de componenten van a(M0, M1, p, t). Bijvoorbeeld, voor de x-component hebben we:
where s0,0 het overeenkomstige element van de matrixschaal voor M0 is, s0,0′ hetzelfde element van de matrixschaal voor M1, en de elementen van de vertaalmatrix op dezelfde manier worden aangeduid met d. (We kiezen hier d voor “delta” omdat t al geclaimd is voor tijd.) Als een lineaire functie van t liggen de extrema van deze functie op de begin- en eindtijd. De andere coördinaten en het geval van een gegeneraliseerde schaal volgen op vergelijkbare wijze.
〈AnimatedTransform Methode Definities〉 + ≡
Bounds3f AnimatedTransform::MotionBounds(const Bounds3f &b) const
if (!actuallyAnimated)
return (*startTransform)(b);
if (hasRotation == false)
return Union((*startTransform)(b), (*eindTransform)(b));
〈Return motion bounds accounting for animated rotation 108〉
}
Voor het algemene geval met geanimeerde rotaties kan de bewegingsfunctie extrema’s hebben op punten in het midden van het tijdbereik. We kennen geen eenvoudige manier om deze punten te vinden. Veel renderers pakken dit probleem aan door een groot aantal keren in het tijdbereik te samplen, de ge¨ınterpoleerde transformatie op elk van die punten te berekenen, en de unie te nemen van alle overeenkomstige getransformeerde bounding boxes. Hier zullen we een meer gefundeerde methode ontwikkelen waarmee we deze bewegingsgrenzen robuust kunnen berekenen.
We gebruiken een iets eenvoudiger conservatieve grens die inhoudt dat we de beweging van de acht hoeken van de bounding box afzonderlijk berekenen en de unie van die grenzen vinden.
〈Return motion bounds accounting for animated rotation〉 ≡ 108
Bounds3f bounds;
for (int corner = 0; corner <8; ++corner)
bounds = Union(bounds, BoundPointMotion(b.Corner(corner));
return bounds;
Voor elke bounding box-hoek p moeten we de extrema van a vinden over het animatie-tijdsbereik. Herinner u uit de wiskunde dat de extrema van een continue functie over een bepaald domein ofwel op de grenspunten van het domein liggen, ofwel op punten waar de eerste afgeleide van de functie nul is. De totale grens wordt dus gegeven door de unie van de posities bij het begin en het einde van de beweging en de positie bij eventuele extrema.
AnimatedTransform:: actuallyAnimated 103
AnimatedTransform:: BoundPointMotion() 110
AnimatedTransform:: hasRotation 103
Bounds3::Corner() 78
Bounds3::Union() 78
Bounds3f 76
Figuur 2.18 toont een plot van één coördinaat van de bewegingsfunctie en zijn afgeleide voor een interessant bewegingstraject van een punt. Merk op dat de maximumwaarde van de functie over het tijdsverloop wordt bereikt op een punt waar de afgeleide nul heeft.
Figuur 2.18. (a) Beweging van de x-coördinaat van een punt p als functie van de tijd, zoals bepaald door twee keyframe matrices. (b) De afgeleide van de bewegingsfunctie, Vergelijking (2.12). Merk op dat extrema’s van de bewegingsfunctie in het gegeven tijdbereik overeenkomen met nullen van de afgeleide.
Om de beweging van een enkel punt te begrenzen, beginnen we onze afleiding met de aanpak die gebruikt is voor het geval zonder rotatie, door de drie T, R, en S componenten van vergelijking (2.9) uit te breiden als functies van de tijd en hun product te vinden. We hebben:
Het resultaat is vrij complex als het wordt uitgebreid, vooral door de slerp en de omzetting van de resulterende quaternion in een matrix; een computeralgebra systeem is een vereiste voor het werken met deze functie.
De afgeleide ∂a(M0, M1, p, t)/∂t is ook vrij complex-in zijn volle algebraïsche glorie zijn meer dan 2000 bewerkingen nodig om de waarde te evalueren voor een gegeven paar ontlede matrices, punt en tijd. Echter, gegeven specifieke transformatiematrices en een specifiek punt, wordt a aanzienlijk vereenvoudigd; we zullen de gespecialiseerde functie van t alleen aanduiden als aM, p(t). Het evalueren van de afgeleide vereist ruwweg 10 floating-point bewerkingen, een sinus, en een cosinus om voor elke coördinaat te evalueren:
waarbij θ de boogcosinus is van het scalair product van de twee quaternionen en waarbij de vijf coëfficiënten ci 3-vectoren zijn die afhangen van de twee matrices en de positie p. Deze specialisatie werkt goed, omdat we de functie op vele tijdwaarden voor een gegeven punt zullen moeten evalueren.
We hebben nu twee taken: ten eerste, gegeven een paar keyframe matrices en een punt p, moeten we eerst in staat zijn om efficiënt de waarden van de coëfficiënten ci te berekenen. Vervolgens moeten we, gegeven de relatief eenvoudige functie gedefinieerd door ci en θ, de nulpunten van vergelijking (2.12) vinden, die de tijdstippen kunnen vertegenwoordigen waarop bewegingsextrema’s optreden.
Voor de eerste taak zullen we eerst de bijdragen aan de coëfficiënten die afhangen van de keyframe matrices uitfactoriseren van die welke afhangen van het punt p, in de veronderstelling dat voor elk paar keyframe matrices (zoals hier het geval is) bounding boxes voor de beweging van meerdere punten zullen worden berekend. Het resultaat is gelukkig vrij eenvoudig – de ci-vectoren zijn lineaire functies van de x-, y- en z-componenten van het punt.
Dus, gegeven de ki-coëfficiënten en een bepaald punt p waarvan we de beweging willen begrenzen, kunnen we efficiënt de coëfficiënten ci van de afgeleide functie in Vergelijking (2.12) berekenen. De DerivativeTerm structuur kapselt deze coëfficiënten en deze berekening in.
〈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;
}
};
De attributen c1 – c5 slaan afgeleide informatie op die overeenkomt met de vijf termen in Vergelijking (2.12). De drie elementen van de matrix komen overeen met de drie dimensies van de ruimte.
〈AnimatedTransform Private Data〉 + ≡
DerivativeTerm c1, c2, c3, c4, c5;
Het fragment 〈Compute terms of motion derivative function〉 in de AnimatedTransform constructor, dat hier niet is opgenomen, initialiseert deze termen, via automatisch gegenereerde code. Gegeven het feit dat het een paar duizend floating-point bewerkingen vereist, is het handig om dit werk één keer te doen en het af te schrijven over de meerdere bounding box hoeken. De ki coëfficiënten zijn eenvoudiger te berekenen als we uitgaan van een canoniek tijdbereik; later zullen we de t-waarden van de nullen van de bewegingsfunctie moeten omzetten naar het werkelijke sluitertijdbereik.
Gegeven de coëfficiënten ki op basis van de keyframe matrices, berekent BoundPointMotion() een robuuste grens van de beweging van p.
〈AnimatedTransform Method Definitions〉 + ≡
Bounds3f AnimatedTransform::BoundPointMotion(const Point3f &p) const {
Bounds3f bounds((*startTransform)(p), (*eindTransform)(p));
Float cosTheta = Dot(R, R);
Float theta = std::acos(Clamp(cosTheta, -1, 1));
for (int c = 0; c <3; ++c) {
〈Zoek bewegingsafgeleide nulpunten voor de component c 111〉
〈Breid de bounding box uit voor alle gevonden bewegingsafgeleide nulpunten 111〉
}
return bounds;
}
Bounds3f 76
DerivativeTerm 110
Float 1062
Point3f 68
De functie IntervalFindZeros(), die straks wordt geïntroduceerd, vindt numeriek nulpunten van Vergelijking (2.12). Er zijn er maximaal vier mogelijk.
〈Vind willekeurige bewegingsafgeleide nulpunten voor de component c〉 ≡ 110
Float nulpunten;
int nZeros = 0;
IntervalFindZeros(c1.Eval(p), c2.Eval(p), c3.Eval(p), c4.Eval(p),
c5.Eval(p), theta,
Interval(0., 1.), nullen, &nZeros);
De nullen worden gevonden over t ∈ , dus we moeten interpoleren binnen het tijdbereik voordat we de methode aanroepen om het punt op de corresponderende tijd te transformeren. Merk ook op dat het extremum slechts in één van de x-, y- en z-dimensies ligt, en dat de grenzen dus alleen in die ene dimensie hoeven te worden bijgewerkt. Voor het gemak gebruiken we hier de functie Union(), die alle dimensies in aanmerking neemt, ook al kunnen er twee worden genegeerd.
〈Expand bounding box for any motion derivative neros found〉 ≡ 110
for (int i = 0; i <nZeros; ++i) {
Point3f pz = (*this)(Lerp(neros, startTime, endTime), p);
bounds = Union(bounds, pz);
}
Het vinden van nulpunten van de bewegingsafgeleide functie, Vergelijking (2.12), kan niet algebraïsch worden gedaan; numerieke methoden zijn noodzakelijk. Gelukkig gedraagt de functie zich goed – zij is tamelijk glad en heeft een beperkt aantal nulpunten. (Herinner u de plot in figuur 2.18, die een ongewoon complexe vertegenwoordiger was.)
Want we zouden een op bisectie gebaseerde zoektocht of de methode van Newton kunnen gebruiken, maar we lopen het risico nullen te missen als de functie de as slechts kort kruist. Daarom zullen we gebruik maken van intervalaritmetiek, een uitbreiding van de rekenkunde die inzicht geeft in het gedrag van functies over bereiken van waarden, waardoor het mogelijk wordt om robuust nulpunten van functies te vinden.
Om het basisidee van intervalaritmetiek te begrijpen, beschouw bijvoorbeeld de functie f (x) = 2x. Als we een interval van waarden ∈ ℝ hebben, dan kunnen we zien dat over het interval, het bereik van f het interval is . Met andere woorden f () ⊂ .
Meer in het algemeen hebben alle basisbewerkingen van de rekenkunde intervaluitbreidingen die beschrijven hoe ze werken op intervallen. Bijvoorbeeld, gegeven twee intervallen en ,
Met andere woorden, als we twee waarden bij elkaar optellen waarvan er een in het bereik ligt en de tweede in , dan moet het resultaat in het bereik .
Intervalaritmetiek heeft de belangrijke eigenschap dat de intervallen die het oplevert conservatief zijn. In het bijzonder, als f () ⊂ en als c > 0, dan weten we zeker dat geen enkele waarde in ervoor zorgt dat f negatief is. In het volgende zullen we laten zien hoe we Vergelijking (2.12) kunnen berekenen over intervallen en zullen we gebruik maken van de conservatieve grenzen van de berekende intervallen om efficiënt kleine intervallen te vinden met nuldoorgangen waar reguliere methoden voor het vinden van wortels betrouwbaar kunnen worden gebruikt.
Eerst zullen we een Intervalklasse definiëren die intervallen van reële getallen voorstelt.
Bounds3::Union() 78
Float 1062
Interval 112
IntervalFindZeros() 113
Lerp() 1079
Point3f 68
〈Interval Definitions〉 ≡
class Interval {
public:
〈Interval Public Methods 112〉
Float low, high;
};
Een interval kan geïnitialiseerd worden met een enkele waarde, die een enkel punt op de reële getallenlijn voorstelt, of met twee waarden die een interval met een breedte van niet nul specificeren.
〈Interval Public Methods〉 ≡ 112
Interval(Float v) : laag(v), hoog(v) { }
Interval(Float v0, Float v1)
: low(std::min(v0, v1)), high(std::max(v0, v1)) { }
De klasse biedt ook overloads voor de basis rekenkundige bewerkingen. Merk op dat voor aftrekken, de hoge waarde van het tweede interval wordt afgetrokken van de lage waarde van het eerste.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);
}
Voor vermenigvuldiging hangt het van de tekens van de respectieve waarden af welke zijden van elk interval de minimum- en maximumwaarde van het resultaatinterval bepalen. Het vermenigvuldigen van de verschillende mogelijkheden en het nemen van het totale minimum en maximum is eenvoudiger dan het uitwerken welke te gebruiken en deze te vermenigvuldigen.
〈Interval Public Methods〉 + ≡ 112
Interval operator*(const Interval &i) const {5656>
return Interval(std::min(std::min(low * i.laag, hoog * i.laag),
std::min(laag * i.hoog, hoog * i.hoog)),
std::max(std::max(laag * i.laag, hoog * i.laag),
std::max(laag * i.hoog, hoog * i.hoog)));
}
We hebben ook Sin() en Cos() functies voor Intervallen ge¨ımplementeerd. De implementaties gaan ervan uit dat het gegeven interval in , is, wat het geval is voor ons gebruik van deze functies. We nemen hier alleen de implementatie van Sin() op; Cos() is vergelijkbaar in basisstructuur.
Float 1062
Interval 112
Interval::high 112
Interval::laag 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.hoog> Pi / 2)
sinHoog = 1.;
if (i.laag <(3.f / 2.f) * Pi && i.hoog> (3.f / 2.f) * Pi)
sinLaag = -1.;
return Interval(sinLow, sinHigh);
}
Gegeven de intervalmachines, kunnen we nu de functie IntervalFindZeros() implementeren, die de t-waarden vindt van alle nuldoorgangen van Vergelijking (2.12) over het gegeven interval tInterval.
〈Interval Definitions〉 + ≡
void IntervalFindZeros(Float c1, Float c2, Float c3, Float c4,
Float c5, Float theta, Interval tInterval, Float *zeros,
int *zeroCount, int depth = 8) {
〈Evalueer de bewegingsafgeleide in intervalvorm, geef terug indien geen nullen 113〉
if (depth> 0) {
〈Split tInterval and check both resulting intervals 114〉
} else {
〈Gebruik Newton’s methode om nul te verfijnen 114〉
}
}
De functie begint met het berekenen van het interval bereik over tInterval. Als het bereik niet nul is, dan zijn er geen nullen van de functie over tInterval en kan de functie terugkeren.
〈Bereken de bewegingsafgeleide in intervalvorm, geef terug als er geen nullen zijn〉 ≡ 113
Intervalbereik = Interval(c1) +
(Interval(c2) + Interval(c3) * tInterval) *
Cos(Interval(2 * theta) * tInterval) +
(Interval(c4) + Interval(c5) * tInterval) *
Sin(Interval(2 * theta) * tInterval);
als (bereik.laag> 0. ∥ bereik.hoog <0. ∥ bereik.laag == bereik.hoog)
return;
Als het intervalbereik nul overspant, dan kunnen er een of meer nullen in het interval tInterval zitten, maar het is ook mogelijk dat er eigenlijk geen zijn, omdat de intervalgrenzen conservatief zijn, maar niet zo strak als mogelijk. De functie splitst tInterval in twee delen en controleert recursief de twee sub-intervallen. Het verkleinen van de grootte van het intervaldomein verkleint in het algemeen de omvang van het intervalbereik, waardoor we misschien kunnen vaststellen dat er geen nullen zijn in een of beide nieuwe intervallen.
Float 1062
Interval 112
Interval::high 112
Interval::laag 112
Pi 1063
〈Split tInterval and check both resulting intervals〉 ≡ 113
Float mid = (tInterval.laag + tInterval.hoog) * 0.5f;
IntervalFindZeros(c1, c2, c3, c4, c5, theta,
Interval(tInterval.low, mid), nullen, zeroCount, depth – 1);
IntervalFindZeros(c1, c2, c3, c4, c5, theta,
Interval(mid, tInterval.high), nullen, zeroCount, diepte – 1);
Zodra we een smal interval hebben waar de intervalwaarde van de bewegingsafgeleide functie nul omspant, schakelt de implementatie over op een paar iteraties van de methode van Newton om het nulpunt te vinden, beginnend bij het midden van het interval. Newton’s methode vereist de afgeleide van de functie; aangezien we nulpunten van de bewegingsafgeleide functie vinden, is dit de tweede afgeleide van Vergelijking (2.11):
〈Gebruik Newton’s methode om nul te verfijnen〉 ≡ 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;