2.9.4 Afgrænsning af bevægelige bounding boxes
Givet en Bounds3f, der er transformeret af en animeret transformation, er det nyttigt at kunne beregne en bounding box, der omfatter alle dens bevægelser i løbet af animationsperioden. Hvis vi f.eks. kan afgrænse bevægelsen af en animeret geometrisk primitiv, kan vi skære stråler med denne afgrænsning for at bestemme, om strålen måske skærer objektet, før vi pådrager os omkostningerne ved at interpolere primitivens afgrænsning til strålens tid for at kontrollere dette skæringspunkt. Metoden AnimatedTransform::MotionBounds() udfører denne beregning, idet den tager en bounding box og returnerer den bounding box for dens bevægelse over AnimatedTransforms tidsinterval.
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
Der er to lette tilfælde: For det første, hvis keyframe-matricerne er ens, kan vi vilkårligt kun anvende starttransformationen for at beregne de fulde grænser. For det andet, hvis transformationen kun omfatter skalering og/eller translation, så afgrænser den bounding box, der omfatter bounding boxens transformerede positioner på både starttidspunktet og sluttidspunktet, hele dens bevægelse. For at se, hvorfor det er sådan, kan man betragte positionen for et transformeret punkt p som en funktion af tiden; vi betegner denne funktion af to matricer, et punkt og et tidspunkt med a(M0, M1, p, t).
Da i dette tilfælde rotationskomponenten i dekompositionen er identiteten, har vi med vores matrixdekomposition
hvor både translationen og skalaen skrives som funktioner af tiden. Hvis vi for nemheds skyld antager, at S(t) er en regulær skala, kan vi finde udtryk for komponenterne i a(M0, M1, p, t). For x-komponenten har vi f.eks:
where s0,0 er det tilsvarende element i skala-matrixen for M0, s0,0′ er det samme element i skala-matrixen for M1, og translationsmatrixelementerne betegnes ligeledes med d. (Vi har valgt d for “delta” her, da t allerede er hævdet for tid.) Som en lineær funktion af t ligger ekstremaerne af denne funktion ved start- og sluttidspunkterne. De andre koordinater og tilfældet med en generaliseret skala følger på tilsvarende vis.
〈AnimatedTransform Metode Definitioner〉 + ≡
Bounds3f AnimatedTransform::MotionBounds(const Bounds3f &b) const {
if (!actuallyAnimated)
return (*startTransform)(b);
if (hasRotation == false)
return Union((*startTransform)(b), (*endTransform)(b));
〈Returnerer bevægelsesgrænser, der tager højde for animeret rotation 108〉
}
For det generelle tilfælde med animerede rotationer kan bevægelsesfunktionen have ekstrema på punkter i midten af tidsintervallet. Vi kender ingen enkel måde at finde disse punkter på. Mange renderere løser dette problem ved at tage prøver et stort antal gange i tidsintervallet, beregne den interpolerede transformation ved hver enkelt gang og tage foreningen af alle de tilsvarende transformerede bounding boxes. Her vil vi udvikle en mere velbegrundet metode, der giver os mulighed for at beregne disse bevægelsesgrænser på en robust måde.
Vi anvender en lidt mere simpel konservativ grænse, der indebærer, at vi beregner bevægelsen af de otte hjørner af den afgrænsende boks individuelt og finder foreningen af disse grænser.
〈Returnerer bevægelsesgrænser, der tager højde for animeret rotation〉 ≡ 108
Bounds3f bounds;
for (int corner = 0; corner <8; ++corner)
bounds = Union(bounds, BoundPointMotion(b.Corner(corner(corner))));
return bounds;
For hvert bounding box-hjørne p skal vi finde ekstrema af a over animationstidsintervallet. Vi husker fra beregning, at ekstremaerne for en kontinuert funktion over et bestemt domæne enten ligger ved domænets grænsepunkter eller ved punkter, hvor funktionens første afledte er nul. Den overordnede grænse er således givet ved foreningen af positionerne ved bevægelsens start og slutning samt positionen ved ethvert ekstrema.
AnimatedTransform::: actuallyAnimated 103
AnimatedTransform:: BoundPointMotion() 110
AnimatedTransform::: hasRotation 103
Bounds3::Corner() 78
Bounds3::Union() 78
Bounds3f 76
Figur 2.18 viser et plot af en koordinat af bevægelsesfunktionen og dens afledte for en interessant bevægelsesvej for et punkt. Bemærk, at den maksimale værdi af funktionen i tidsintervallet nås i et punkt, hvor den afledte har et nul.
Figur 2.18. (a) Bevægelse af x-koordinaten for et punkt p som en funktion af tiden, som bestemt af to keyframe-matricer. (b) Den afledte af bevægelsesfunktionen, ligning (2.12). Bemærk, at ekstrema af bevægelsesfunktionen i det givne tidsinterval svarer til nuller af den afledte.
For at afgrænse bevægelsen af et enkelt punkt starter vi vores afledning ved at følge den fremgangsmåde, der er anvendt i tilfældet uden rotation, idet vi udvider de tre T-, R- og S-komponenter i ligning (2.9) som funktioner af tiden og finder deres produkt. Vi har:
Resultatet er ret komplekst, når det udvides, hovedsagelig på grund af slerp’en og konverteringen af den resulterende quaternion til en matrix; et computeralgebra-system er en forudsætning for at arbejde med denne funktion.
Den afledte ∂a(M0, M1, p, t)/∂t er også ret kompleks – i sin fulde algebraiske pragt kræves der over 2.000 operationer for at evaluere dens værdi for et givet par af dekomponerede matricer, punkt og tid. Men givet specifikke transformationsmatricer og et specifikt punkt er a væsentligt forenklet; vi vil betegne den specialiserede funktion af t alene som aM, p(t). Evalueringen af dens afledte kræver groft sagt 10 flydepunktsoperationer, en sinus og en cosinus at evaluere for hver koordinat:
hvor θ er arc cosinus af punktproduktet af de to kvaternioner, og hvor de fem koefficienter ci er 3-vektorer, der afhænger af de to matricer og positionen p. Denne specialisering fungerer godt, da vi skal evaluere funktionen ved mange tidsværdier for et givet punkt.
Vi har nu to opgaver: For det første skal vi, givet et par keyframe-matricer og et punkt p, først kunne beregne værdierne af koefficienterne ci på en effektiv måde. Derefter skal vi, givet den relativt enkle funktion defineret af ci og θ, finde nulpunkterne i ligning (2.12), som kan repræsentere de tidspunkter, hvor bevægelsesekstremaer opstår.
For den første opgave vil vi først udregne bidragene til de koefficienter, der afhænger af keyframematricerne, fra dem, der afhænger af punktet p, under den antagelse, at der for hvert par keyframematricer (som det er tilfældet her) vil blive beregnet bounding boxes for flere punkters bevægelse. Resultatet er heldigvis ret simpelt – ci-vektorerne er er lineære funktioner af punktets x-, y- og z-komponenter.
Så kan vi, givet ki-koefficienterne og et bestemt punkt p, som vi ønsker at afgrænse bevægelsen af, effektivt beregne koefficienterne ci i den afledte funktion i ligning (2.12). DerivativeTerm-strukturen indkapsler disse koefficienter og denne beregning.
〈〈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;
}
};
Attributterne c1 – c5 gemmer afledte oplysninger svarende til de fem termer i ligning (2.12). De tre array-elementer svarer til de tre dimensioner i rummet.
〈AnimatedTransform Private Data〉 + ≡
DerivativeTerm c1, c2, c3, c4, c5;
Fragmentet 〈Compute terms of motion derivative function〉 i AnimatedTransform-konstruktøren, der ikke er medtaget her, initialiserer disse termer, via automatisk genereret kode. I betragtning af at det kræver et par tusinde floating-point-operationer, er det nyttigt at gøre dette arbejde én gang og afskrive det over de mange bounding box-hjørner. Koefficienterne ki beregnes lettere, hvis vi antager et kanonisk tidsinterval ; senere bliver vi nødt til at omlægge t-værdierne for nuller i bevægelsesfunktionen til det faktiske lukkertidsinterval.
Givet koefficienterne ki baseret på keyframe-matricerne beregner BoundPointMotion() en robust afgrænsning af bevægelsen af p.
〈〈AnimatedTransform Metodedefinitioner〉 + ≡
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) {
〈Find eventuelle bevægelsesderivatnuller for komponenten c 111〉
〈Udvider bounding box for eventuelle bevægelsesderivatnuller, der er fundet 111〉
}
return bounds;
}
Bounds3f 76
DerivativeTerm 110
Float 1062
Point3f 68
Funktionen IntervalFindZeros(), som vil blive introduceret om lidt, finder numerisk nulpunkter i ligning (2.12). Op til fire er mulige.
〈Find eventuelle bevægelsesderivatnuller for komponenten c〉 ≡ 110
Float zeros;
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);
Nullerne findes over t ∈ , så vi skal interpolere inden for tidsintervallet, før vi kalder metoden til at transformere punktet på det tilsvarende tidspunkt. Bemærk også, at ekstremummet kun er på en af dimensionerne x, y og z, og at grænserne derfor kun skal opdateres i denne ene dimension. For nemheds skyld bruger vi her blot funktionen Union(), som tager hensyn til alle dimensioner, selv om to af dem kunne ignoreres.
〈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);
}
Finding zeros of the motion derivative function, Equation (2.12), kan ikke gøres algebraisk; numeriske metoder er nødvendige. Heldigvis opfører funktionen sig godt – den er ret glat og har et begrænset antal nuller. (Husk på plottet i figur 2.18, som var en usædvanlig kompleks repræsentant.)
Selv om vi kunne bruge en bisektion-baseret søgning eller Newtons metode, ville vi risikere at mangle nuller, når funktionen kun kortvarigt krydser aksen. Derfor vil vi bruge intervalaritmetik, en udvidelse af aritmetikken, der giver indsigt i funktioners opførsel over værdiintervaller, hvilket gør det muligt at finde nulpunkter af funktioner på en robust måde.
For at forstå den grundlæggende idé om intervalaritmetik kan man f.eks. betragte funktionen f (x) = 2x. Hvis vi har et interval af værdier ∈ ℝ, så kan vi se, at over intervallet er intervallet intervallet f’s rækkevidde . Med andre ord f () ⊂ .
Mere generelt har alle de grundlæggende aritmetiske operationer intervaludvidelser, der beskriver, hvordan de opererer på intervaller. For eksempel, givet to intervaller og ,
Med andre ord, hvis vi lægger to værdier sammen, hvor den ene er i intervallet og den anden er i , så skal resultatet være i intervallet .
Intervalaritmetik har den vigtige egenskab, at de intervaller, den giver, er konservative. Navnlig, hvis f () ⊂ og hvis c > 0, så ved vi med sikkerhed, at ingen værdi i får f til at være negativ. I det følgende vil vi vise, hvordan man beregner ligning (2.12) over intervaller, og vi vil udnytte de beregnede intervallers konservative grænser til effektivt at finde små intervaller med nul-krydsninger, hvor almindelige rodfindingsmetoder kan anvendes pålideligt.
Først vil vi definere en Interval-klasse, der repræsenterer intervaller af reelle tal.
Begrænsninger3::Union() 78
Float 1062
Interval 112
IntervalFindZeros() 113
Lerp() 1079
Point3f 68
〈Interval Definitions〉 ≡
class Interval {
public:
〈Interval Public Methods 112〉
Float low, high;
};
;
Et interval kan initialiseres med en enkelt værdi, der repræsenterer et enkelt punkt på den reelle tallinje, eller med to værdier, der angiver et interval med en bredde på ikke-nul.
〈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)) { }
Klassen indeholder også overbelastninger for de grundlæggende aritmetiske operationer. Bemærk, at for subtraktion subtraheres den høje værdi af det andet interval fra den lave værdi af det første.3
〈Interval Offentlige metoder〉 + ≡ 112
Intervaloperatør + (const Interval &i) const {
return Interval(lav + i.low, high + i.high);
}
Interval operator-(const Interval &i) const {
return Interval(low – i.high, high – i.low);
}
Ved multiplikation afhænger det af fortegnene på de respektive værdier, hvilke sider af hvert interval der bestemmer minimums- og maksimumsværdierne i resultatintervallet. Det er lettere at multiplicere de forskellige muligheder og tage det samlede minimum og maksimum end at arbejde sig frem til, hvilke der skal bruges, og multiplicere disse.
〈Interval Public Methods〉 + ≡ 112
Interval operator*(const Interval &i) const {
return Interval(std::min(std::min(lav * 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 også implementeret funktionerne Sin() og Cos() for Intervaller. Implementeringerne forudsætter, at det givne interval er i , hvilket er tilfældet for vores brug af disse funktioner. Her medtager vi kun implementeringen af Sin(); Cos() er ret ens i den grundlæggende struktur.
Float 1062
Interval 112
Interval::high 112
Interval::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);
}
Givet intervalmaskineriet kan vi nu implementere funktionen IntervalFindZeros(), som finder t-værdierne af alle nulpunktsoverskridelser af ligning (2.12) over det givne interval tInterval.
〈Interval Definitioner〉 + ≡
void IntervalFindZeros(Float c1, Float c2, Float c3, Float c4,
Float c5, Float theta, Interval tInterval, Float *zeros,
int *zeroCount, int depth = 8) {
〈Evaluerer bevægelsesderivat i intervalform, returnerer hvis ingen nuller 113〉
if (depth> 0) {
〈Split tInterval and check both resulting intervals 114〉
} else {
〈Anvend Newtons metode til at forfine nul 114〉
}
}
}
Funktionen starter med at beregne intervalområdet over tInterval. Hvis intervallet ikke spænder over nul, er der ingen nuller for funktionen over tInterval, og funktionen kan vende tilbage.
〈Evaluerer bevægelsesderivat i intervalform, returnere hvis ingen nuller〉 ≡ 113
Intervalområde = Interval(c1) +
(Interval(c2) + Interval(c3) * tInterval) *
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;
Hvis intervalområdet spænder over nul, så kan der være et eller flere nuller i intervallet tInterval, men det er også muligt, at der faktisk ikke er nogen, da intervalgrænserne er konservative, men ikke så stramme som muligt. Funktionen opdeler tInterval i to dele og kontrollerer rekursivt de to delintervaller. Ved at reducere størrelsen af intervaldomænet reduceres generelt omfanget af intervalområdet, hvilket kan give os mulighed for at fastslå, at der ikke er nogen nuller i et eller begge de nye intervaller.
Float 1062
Interval 112
Interval::high 112
Interval::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, c4, c5, theta,
Interval(mid, tInterval.high), zeros, zeroCount, depth – 1);
Når vi har et smalt interval, hvor intervalværdien af den bevægelsesafledte funktion spænder over nul, skifter implementeringen til et par gentagelser af Newtons metode for at finde nulpunktet, idet der startes ved midtpunktet af intervallet. Newtons metode kræver funktionens afledte værdi; da vi finder nuller af den bevægelsesafledte funktion, er dette den anden afledte værdi af ligning (2.11):
〈Brug Newtons metode til at forfine nul〉 ≡ 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;