2.9.4 Bounding rörliga bounding boxes
Genom en Bounds3f som transformeras av en animerad transformation är det användbart att kunna beräkna en bounding box som omfattar all dess rörelse under animationstiden. Om vi till exempel kan avgränsa rörelsen hos en animerad geometrisk primitiv kan vi skär strålar med denna avgränsning för att avgöra om strålen kan skär objektet innan vi ådrar oss kostnaden för att interpolera primitivens avgränsning till strålens tid för att kontrollera denna skärning. Metoden AnimatedTransform::MotionBounds() utför denna beräkning, tar en avgränsande box och returnerar den avgränsande boxen för dess rörelse över AnimatedTransforms tidsintervall.
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
Det finns två enkla fall: För det första, om keyframe-matriserna är lika, kan vi godtyckligt tillämpa endast starttransformationen för att beräkna de fullständiga gränserna. För det andra, om transformationen endast omfattar skalning och/eller translation, så avgränsar den avgränsande boxen som omfattar den avgränsande boxens transformerade positioner vid både starttid och sluttid hela dess rörelse. För att se varför det är så, betrakta positionen för en transformerad punkt p som en funktion av tiden; vi betecknar denna funktion av två matriser, en punkt och en tid med a(M0, M1, p, t).
Då i detta fall rotationskomponenten i dekompositionen är identiteten, har vi med vår matrisdekomposition
där både translationen och skalan skrivs som funktioner av tiden. Om vi för enkelhetens skull antar att S(t) är en vanlig skala kan vi hitta uttryck för komponenterna i a(M0, M1, p, t). För x-komponenten har vi till exempel följande:
where s0,0 är motsvarande element i skalmatrisen för M0, s0,0′ är samma element i skalmatrisen för M1, och translationsmatrisens element betecknas på samma sätt med d. (Vi valde d för ”delta” här eftersom t redan har tagits i anspråk för tid.) Som en linjär funktion av t ligger extremavärdena för denna funktion vid start- och sluttidpunkterna. De andra koordinaterna och fallet med en generaliserad skala följer på liknande sätt.
〈AnimatedTransform Metoddefinitioner〉 + ≡
Bounds3f AnimatedTransform::MotionBounds(const Bounds3f &b) const {
if (!actuallyAnimated)
return (*startTransform)(b);
if (hasRotation == false)
return Union((*startTransform)(b), (*endTransform)(b));
〈Returnerar rörelsegränser som tar hänsyn till animerad rotation 108〉
}
För det allmänna fallet med animerade rotationer kan rörelsefunktionen ha extrema vid punkter i mitten av tidsintervallet. Vi känner inte till något enkelt sätt att hitta dessa punkter. Många renderare löser detta problem genom att ta stickprov ett stort antal gånger i tidsintervallet, beräkna den interpolerade transformationen vid varje tillfälle och ta föreningen av alla motsvarande transformerade avgränsande boxar. Här kommer vi att utveckla en mer välgrundad metod som gör att vi på ett robust sätt kan beräkna dessa rörelsegränser.
Vi använder en något enklare konservativ gräns som innebär att vi beräknar rörelsen för de åtta hörnen av den avgränsande boxen individuellt och finner föreningen av dessa gränser.
〈Returnerar rörelsegränser som tar hänsyn till animerad rotation〉 ≡ 108
Bounds3f bounds;
for (int corner = 0; corner <8; ++corner)
bounds = Union(bounds, BoundPointMotion(b.Corner(corner(corner))));
return bounds;
För varje hörn p i den avgränsande boxen måste vi hitta extremavärdet för a över animationstidsområdet. Minns du från kalkylering att extrema för en kontinuerlig funktion över en viss domän antingen finns vid domänens gränspunkter eller vid punkter där funktionens första derivata är noll. Den övergripande gränsen ges alltså av föreningen av positionerna vid rörelsens början och slut samt positionen vid varje extrema.
AnimatedTransform:: actuallyAnimated 103
AnimatedTransform:: BoundPointMotion() 110
AnimatedTransform:: hasRotation 103
Bounds3::Corner() 78
Bounds3::Union() 78
Bounds3f 76
Figur 2.18 visar en plott av en koordinat av rörelsefunktionen och dess derivat för en intressant rörelsebana för en punkt. Observera att funktionens maximala värde över tidsintervallet uppnås i en punkt där derivatan har en nollpunkt.
Figur 2.18. (a) Rörelse av x-koordinaten för en punkt p som en funktion av tiden, som bestäms av två keyframe-matriser. (b) Derivatan av rörelsefunktionen, ekvation (2.12). Observera att extrema av rörelsefunktionen i det givna tidsintervallet motsvarar nollor i derivatan.
För att binda rörelsen för en enskild punkt börjar vi vår härledning genom att följa det tillvägagångssätt som används för fallet utan rotation, genom att expandera de tre T-, R- och S-komponenterna i ekvation (2.9) som funktioner av tiden och hitta deras produkt. Vi har:
Resultatet är ganska komplext när det expanderas ut, främst på grund av slerp och omvandlingen av den resulterande kvaternionen till en matris; ett datoralgebrasystem är ett krav för att arbeta med denna funktion.
Derivatan ∂a(M0, M1, p, t)/∂t är också ganska komplex – i sin fulla algebraiska prakt krävs över 2 000 operationer för att utvärdera dess värde för ett givet par av dekomponerade matriser, punkt och tid. Givet specifika transformationsmatriser och en specifik punkt förenklas dock a avsevärt; vi betecknar den specialiserade funktionen för enbart t som aM, p(t). Utvärdering av dess derivat kräver ungefär 10 flyttalsoperationer, en sinus och en cosinus för att utvärdera för varje koordinat:
där θ är arc cosinus av punktprodukten av de två kvaternionerna och där de fem koefficienterna ci är 3-vektorer som beror på de två matriserna och läget p. Denna specialisering fungerar bra, eftersom vi kommer att behöva utvärdera funktionen vid många tidsvärden för en given punkt.
Vi har nu två uppgifter: för det första måste vi, givet ett par keyframe-matriser och en punkt p, först kunna beräkna värdena för koefficienterna ci på ett effektivt sätt. Sedan måste vi, givet den relativt enkla funktion som definieras av ci och θ, hitta nollpunkterna i ekvation (2.12), som kan representera de tidpunkter vid vilka rörelseextrema inträffar.
För den första uppgiften kommer vi först att utjämna bidragen till de koefficienter som är beroende av keyframe-matriserna från dem som är beroende av punkten p, med antagandet att bounding boxes för flera punkters rörelser kommer att beräknas för varje par av keyframe-matriser (vilket är fallet här). Resultatet är lyckligtvis ganska enkelt – vektorerna ci är linjära funktioner av punktens x-, y- och z-komponenter.
Så, givet koefficienterna ki och en viss punkt p som vi vill avgränsa rörelsen för, kan vi på ett effektivt sätt beräkna koefficienterna ci till den derivativa funktionen i ekvation (2.12). Strukturen DerivativeTerm kapslar in dessa koefficienter och denna beräkning.
〈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;
}
};
Attributen c1 – c5 lagrar derivatinformation som motsvarar de fem termerna i ekvation (2.12). De tre matriselementen motsvarar rummets tre dimensioner.
〈AnimatedTransform Private Data〉 + ≡
DerivativeTerm c1, c2, c3, c4, c5;
Fragmentet 〈Compute terms of motion derivative function〉 i AnimatedTransform-konstruktören, som inte är inkluderat här, initierar dessa termer, via automatiskt genererad kod. Med tanke på att det krävs några tusen flyttalsoperationer är det bra att göra det här arbetet en gång och avskriva det över flera hörn av den avgränsande boxen. Koefficienterna ki är lättare att beräkna om vi utgår från ett kanoniskt tidsintervall ; senare måste vi omforma t-värdena för nollor i rörelsefunktionen till det faktiska slutartidsintervallet.
Givet koefficienterna ki baserade på keyframe-matriserna beräknar BoundPointMotion() en robust begränsning av rörelsen för p.
〈AnimatedTransform Metoddefinitioner〉 + ≡
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) {
〈Finns eventuella nollor i rörelsederivat för komponenten c 111〉
〈Expanderar den avgränsande boxen för eventuella nollor i rörelsederivat som hittats 111〉
}
return bounds;
}
Bounds3f 76
DerivativeTerm 110
Float 1062
Point3f 68
Funktionen IntervalFindZeros(), som kommer att introduceras inom kort, hittar numeriskt nollor i ekvation (2.12). Upp till fyra är möjliga.
〈Finns alla nollor för rörelsederivat för komponenten c〉 ≡ 110
Float nollor;
int nZeros = 0;
IntervalFindZeros(c1.Eval(p), c2.Eval(p), c3.Eval(p), c4.Eval(p),
c5.Eval(p), theta,
Intervall(0., 1.), zeros, &nZeros);
Nollorna hittas över t ∈ , så vi måste interpolera inom tidsintervallet innan vi anropar metoden för att transformera punkten vid motsvarande tidpunkt. Observera också att extremumet bara finns i en av dimensionerna x, y och z, och därför behöver gränserna bara uppdateras i den ena dimensionen. För enkelhetens skull använder vi här bara funktionen Union(), som tar hänsyn till alla dimensioner, även om två skulle kunna ignoreras.
〈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);
}
Finnande av nollor för rörelsens derivatfunktion, ekvation (2.12), kan inte göras algebraiskt; numeriska metoder är nödvändiga. Som tur är beter sig funktionen väl – den är ganska jämn och har ett begränsat antal nollor. (Minns plottningen i figur 2.18, som var en ovanligt komplex representant.)
Vidare skulle vi kunna använda en bisektionsbaserad sökning eller Newtons metod, men vi skulle riskera att missa nollor när funktionen bara kortvarigt korsar axeln. Därför kommer vi att använda oss av intervallaritmetik, en utvidgning av aritmetiken som ger insikt om funktioners beteende över värdeområden, vilket gör det möjligt att på ett robust sätt hitta nollor i funktioner.
För att förstå den grundläggande idén med intervallaritmetik kan man till exempel betrakta funktionen f (x) = 2x. Om vi har ett värdeintervall ∈ ℝ, kan vi se att över intervallet är intervallet f:s räckvidd intervallet . Med andra ord f () ⊂ .
Mer generellt har alla aritmetikens grundläggande operationer intervallutvidgningar som beskriver hur de verkar på intervall. Till exempel, givet två intervall och ,
Med andra ord, om vi adderar två värden där det ena ligger i intervallet och det andra ligger i , måste resultatet ligga i intervallet .
Intervallaritmetik har den viktiga egenskapen att de intervall som den ger är konservativa. I synnerhet, om f () ⊂ och om c > 0, så vet vi med säkerhet att inget värde i gör att f blir negativ. I det följande kommer vi att visa hur man beräknar ekvation (2.12) över intervaller och kommer att dra nytta av de konservativa gränserna för beräknade intervaller för att effektivt hitta små intervaller med nollgenomgångar där vanliga metoder för att hitta rötter kan användas på ett tillförlitligt sätt.
Först kommer vi att definiera en Intervall-klass som representerar intervaller av reella tal.
Bounds3::Union() 78
Float 1062
Intervall 112
IntervallFindZeros() 113
Lerp() 1079
Point3f 68
〈Intervall Definitioner〉 ≡
class Interval {
public:
〈Interval Public Methods 112〉
Float low, high;
};
Ett intervall kan initialiseras med ett enda värde, som representerar en enda punkt på den reella tallinjen, eller med två värden som anger ett intervall med en bredd som inte är noll.
〈Intervall Offentliga metoder〉 ≡ 112
Intervall(Float v) : low(v), high(v) { }
Intervall(Float v0, Float v1)
: low(std::min(v0, v1)), high(std::max(v0, v1)) { }
Klassen tillhandahåller också överbelastningar för de grundläggande aritmetiska operationerna. Observera att för subtraktion subtraheras det höga värdet i det andra intervallet från det låga värdet i det första.3
〈Intervall Offentliga metoder〉 + ≡ 112
Intervalloperatör + (const Intervall &i) const {
return Intervall(låg + i.low, high + i.high);
}
Intervall operator-(const Interval &i) const {
return Interval(low – i.high, high – i.low);
}
För multiplikation beror vilka sidor av varje intervall som bestämmer minimi- och maximivärdena i resultatintervallet på tecknen på respektive värden. Att multiplicera de olika möjligheterna och ta det totala minimum och maximum är enklare än att arbeta igenom vilka som ska användas och multiplicera dessa.
〈Intervall Offentliga metoder〉 + ≡ 112
Intervalloperatör*(const Intervall &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)));
}
Vi har också implementerat funktionerna Sin() och Cos() för intervall. Implementeringarna förutsätter att det givna intervallet är i , vilket är fallet för vår användning av dessa funktioner. Här inkluderar vi endast implementeringen av Sin(); Cos() är ganska likartad i sin grundstruktur.
Float 1062
Intervall 112
Intervall::high 112
Intervall::låg 112
〈Intervall Definitioner〉 + ≡
inline Intervall Sin(const Intervall &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);
}
Givet intervallmaskineriet kan vi nu implementera funktionen IntervalFindZeros(), som hittar t-värdena för eventuella nollgenomgångar av ekvation (2.12) över det givna intervallet tInterval.
〈Intervall Definitioner〉 + ≡
void IntervalFindZeros(Float c1, Float c2, Float c3, Float c4,
Float c5, Float theta, Intervall tInterval, Float *zeros,
int *zeroCount, int depth = 8) {
〈Evaluerar rörelsens derivat i intervallform, returnera om inga nollor finns 113〉
if (depth> 0) {
〈Split tInterval and check both resulting intervals 114〉
} else {
〈Använd Newtons metod för att förfina nollan 114〉
}
}
}
Funktionen börjar med att beräkna intervallområdet över tInterval. Om intervallet inte sträcker sig över noll finns det inga nollor för funktionen över tInterval och funktionen kan återvända.
〈Utvärdera rörelsederivat i intervallform, Återgå om inga nollor〉 ≡ 113
Intervallområde = Intervall(c1) +
(Intervall(c2) + Intervall(c3) * tIntervall) *
Cos(Intervall(2 * theta) * tIntervall) +
(Intervall(c4) + Intervall(c5) * tIntervall) *
Sin(Intervall(2 * theta) * tIntervall);
if (range.low> 0. ∥ range.high <0. ∥ range.low == range.high)
return;
Om intervallintervallet sträcker sig över noll kan det finnas en eller flera nollor i intervallet tInterval, men det är också möjligt att det faktiskt inte finns några, eftersom intervallgränserna är konservativa men inte så snäva som möjligt. Funktionen delar tInterval i två delar och kontrollerar rekursivt de två delintervallen. Genom att minska storleken på intervalldomänen minskar i allmänhet intervallområdets omfattning, vilket kan göra det möjligt att fastställa att det inte finns några nollor i ett eller båda de nya intervallen.
Float 1062
Intervall 112
Intervall::hög 112
Intervall::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);
När vi väl har ett smalt intervall där intervallvärdet för rörelsens derivatfunktion sträcker sig över noll, övergår implementeringen till några iterationer av Newtons metod för att hitta nollan, med början i mitten av intervallet. Newtons metod kräver funktionens derivat; eftersom vi hittar nollor för rörelsederivatfunktionen är detta den andra derivatan av ekvation (2.11):
〈Använd Newtons metod för att förfina nollan〉 ≡ 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;