2.9.4 Liikkuvat rajalaatikot
Koska Bounds3f on muunnettu animoidulla transformaatiolla, on hyödyllistä pystyä laskemaan rajalaatikko, joka kattaa kaiken sen liikkeen animaation ajanjakson aikana. Jos esimerkiksi voimme rajata animoidun geometrisen primitiivin liikkeen, voimme leikata säteet tämän rajan kanssa määrittääksemme, voiko säde leikata objektin, ennen kuin joudumme maksamaan kustannukset primitiivin rajan interpoloimisesta säteen aikaan kyseisen leikkauksen tarkistamiseksi. AnimatedTransform::MotionBounds()-metodi suorittaa tämän laskennan ottamalla rajalaatikon ja palauttamalla sen liikkeen rajalaatikon AnimatedTransformin aika-alueella.
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:: Ensinnäkin, jos avainkuvamatriisit ovat yhtä suuret, voimme mielivaltaisesti soveltaa vain alkutransformaatiota täydellisten rajojen laskemiseksi. Toiseksi, jos transformaatio sisältää vain skaalauksen ja/tai translaation, niin rajoituslaatikko, joka käsittää rajoituslaatikon muunnetut sijainnit sekä alku- että loppuajankohtana, rajoittaa kaiken sen liikkeen. Nähdäksemme, miksi näin on, tarkastellaan muunnetun pisteen p sijaintia ajan funktiona; merkitsemme tätä kahden matriisin, pisteen ja ajan funktiota a(M0, M1, p, t).
Koska tässä tapauksessa dekomposition rotaatiokomponentti on identtinen, niin matriisidepomposition avulla saamme
jossa sekä translaatio että skaalaus kirjoitetaan ajan funktioina. Jos oletetaan yksinkertaisuuden vuoksi, että S(t) on säännöllinen asteikko, voidaan löytää lausekkeet a(M0, M1, p, t):n komponenteille. Esimerkiksi x-komponentille on:
where s0,0 on M0:n vastaava mittakaavamatriisin elementti, s0,0′ on M1:n sama mittakaavamatriisin elementti, ja translaatiomatriisin elementit merkitään vastaavasti d:llä. (Valitsimme d:n tässä ”delta”-merkinnäksi, koska t on jo väitetty ajaksi.) Lineaarisena funktiona t:lle tämän funktion ääriarvot ovat alku- ja loppuajankohdissa. Muut koordinaatit ja yleistetyn asteikon tapaus seuraavat samalla tavalla.
〈AnimatedTransform-menetelmän määritelmät〉 + ≡
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〉
}
Yleisessä tapauksessa, jossa on animoituja kiertoja, liikefunktiolla voi olla ääriarvoja pisteissä aika-alueen keskellä. Emme tiedä mitään yksinkertaista tapaa löytää näitä pisteitä. Monet renderöintilaitteet ratkaisevat tämän ongelman ottamalla näytteitä aika-alueelta useita kertoja, laskemalla interpoloidun transformaation jokaisella kerralla ja ottamalla kaikkien vastaavien transformoitujen rajauskehysten liiton. Tässä kehitämme perustellumman menetelmän, jonka avulla voimme laskea nämä liikerajat vankasti.
Käytämme hieman yksinkertaisempaa konservatiivista rajaa, joka edellyttää rajoituslaatikon kahdeksan kulman liikkeen laskemista yksitellen ja näiden rajojen yhdistämisen löytämistä.
〈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;
Kullekin bounding boxin kulmalle p on löydettävä a:n ääriarvot animaation aika-alueella. Muistetaan matematiikasta, että jatkuvan funktion ääriarvot jollakin alueella ovat joko alueen reunapisteissä tai pisteissä, joissa funktion ensimmäinen derivaatta on nolla. Kokonaisraja saadaan siis liikkeen alku- ja loppupisteiden sekä mahdollisten ääriarvojen sijaintien liitosta.
AnimatedTransform:: actuallyAnimated 103
AnimatedTransform:: BoundPointMotion() 110
AnimatedTransform:: hasRotation 103
Bounds3::Corner() 78
Bounds3::Union() 78
Bounds3f 76
Kuva 2.18 esittää liikefunktion yhden koordinaatin ja sen derivaatan kuvaajaa mielenkiintoiselle pisteen liikeradalle. Huomaa, että funktion suurin arvo aika-alueella saavutetaan pisteessä, jossa derivaatta on nolla.
Kuva 2.18. (a) Pisteen p x-koordinaatin liike ajan funktiona kahden keyframe-matriisin määrittämänä. (b) Liikefunktion derivaatta, yhtälö (2.12). Huomaa, että liikefunktion ääriarvot tietyllä aika-alueella vastaavat derivaatan nollia.
Yksittäisen pisteen liikkeen sitomiseksi aloitamme derivoinnin noudattamalla lähestymistapaa, jota käytettiin, kun yhtälön (2.9) kolme T-, R- ja S-komponenttia laajennetaan ajan funktioiksi ja etsitään niiden tulo. Meillä on:
Tulos on varsin monimutkainen, kun se laajennetaan ulospäin, mikä johtuu lähinnä slerpistä ja tuloksena saadun kvaternionin muuntamisesta matriisiksi; tietokonealgebrajärjestelmä on edellytys tämän funktion kanssa työskentelylle.
Derivaatta ∂a(M0, M1, p, t)/∂t on myös melko monimutkainen – täydessä algebrallisessa loistossaan sen arvon arvioimiseen tietylle hajotettujen matriisien, pisteen ja ajan, parille tarvitaan yli 2000 operaatiota. Kun kuitenkin annetaan tietyt muunnosmatriisit ja tietty piste, a yksinkertaistuu huomattavasti; merkitsemme pelkän t:n erikoistunutta funktiota nimellä aM, p(t). Sen derivaatan arvioiminen vaatii noin 10 liukulukuoperaatiota, sinin ja kosinin arvioimiseksi kullekin koordinaatille:
jossa θ on kahden kvaternionin pistetuoton kaarikosinus, ja jossa viisi kerrointa ci ovat kolmoisvektoreja, jotka ovat riippuvaisia molemmista matriiseista ja sijainnista p. Tämä erikoistuminen onnistuu hyvin, koska joudumme arvioimaan funktiota monilla aika-arvoilla tietylle pisteelle.
Meillä on nyt kaksi tehtävää: ensinnäkin, kun meille on annettu pari avainkuvamatriiseja ja piste p, meidän on ensin kyettävä tehokkaasti laskemaan kertoimien ci arvot. Sitten, kun ci:n ja θ:n määrittelemä suhteellisen yksinkertainen funktio on annettu, meidän on löydettävä yhtälön (2.12) nollakohdat, jotka voivat edustaa aikoja, jolloin liikkeen ääriarvot esiintyvät.
Ensimmäistä tehtävää varten erottelemme ensin kertoimien osuudet, jotka riippuvat näppäinkehysmatriiseista, niistä osuuksista, jotka riippuvat pisteestä p, olettaen, että useiden pisteiden liikkeen rajoittavat laatikot lasketaan jokaiselle parille näppäinkehysmatriisien matriiseja (niin kuin tässä tapauksessa tapahtuu). Tulos on onneksi varsin yksinkertainen – ci-vektorit ovat pisteen x-, y- ja z-komponenttien lineaarisia funktioita.
Siten, kun annamme ki-kertoimet ja tietyn pisteen p liikkeen, jonka liikettä haluamme rajata, voimme tehokkaasti laskea yhtälön (2.12) derivaattafunktion ci-kertoimet. DerivativeTerm-rakenne kapseloi nämä kertoimet ja tämän laskennan.
〈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;
}
};
Attribuutit c1 – c5 tallentavat yhtälön (2.12) viittä termiä vastaavaa derivaatatietoa. Kolme array-elementtiä vastaavat avaruuden kolmea ulottuvuutta.
〈AnimatedTransform Private Data〉 + ≡
DerivativeTerm c1, c2, c3, c4, c5;
AnimatedTransformin konstruktorissa oleva fragmentti 〈Compute termit liikkeen derivaattafunktiota varten〉, jota ei ole sisällytetty tänne, initifioituu näihin termeihin automaattisesti luodun koodin avulla. Kun otetaan huomioon, että se vaatii muutamia tuhansia liukulukuoperaatioita, on hyödyllistä tehdä tämä työ kerran ja amortisoida se useiden rajoituslaatikon kulmien yli. Kertoimet ki on helpompi laskea, jos oletamme kanonisen aika-alueen ; myöhemmin joudumme uudelleensovittamaan liikefunktion nollakohtien t-arvot todelliseen suljinaika-alueeseen.
Given the coefficients ki based on the keyframe matrices, BoundPointMotion() computes a robust bound of the motion of p.
〈AnimatedTransform-menetelmän määritelmät〉 + ≡
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) {
〈Etsitään kaikki liikkeen derivaatan nollakohdat komponentille c 111〉
〈Laajennetaan rajoituslaatikkoa kaikille löydetyille liikkeen derivaatan nollakohdille 111〉
}
return bounds;12). Jopa neljä on mahdollista.
〈Löydä kaikki liikkeen derivaatan nollakohdat komponentille 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);
Nollat löydetään yli t ∈ , joten meidän on interpoloitava aikavälien sisällä ennen metodin kutsumista pisteen muuttamiseksi vastaavalla hetkellä. Huomaa myös, että ääriarvo on vain yhdessä x-, y- ja z-ulottuvuuksista, joten rajat on päivitettävä vain tässä yhdessä ulottuvuudessa. Yksinkertaisuuden vuoksi käytämme tässä vain funktiota Union(), joka ottaa huomioon kaikki ulottuvuudet, vaikka kaksi ulottuvuutta voitaisiin jättää huomiotta.
〈Expand bounding box for any motion derivative zeros found〉 ≡ 110
for (int i = 0; i <nZeros; ++i) {
Point3f pz = (*this)(Lerp(zeros, alkuAika, loppuaika, loppuAika), p);
bounds = Union(bounds, pz);
}
Liikkeen derivaattafunktion nollakohtien löytäminen, yhtälö (2.12), ei voida tehdä algebrallisesti, vaan tarvitaan numeerisia menetelmiä. Onneksi funktio käyttäytyy hyvin – se on melko sileä ja sillä on rajallinen määrä nollia. (Muistetaan kuvan 2.18 kuvaaja, joka oli epätavallisen monimutkainen edustaja.)
Vaikka voisimme käyttää puolitukseen perustuvaa hakua tai Newtonin menetelmää, vaarana olisi nollakohtien puuttuminen, kun funktio ylittää akselin vain lyhyesti. Siksi käytämme intervalliaritmetiikkaa, aritmetiikan laajennusta, joka antaa tietoa funktioiden käyttäytymisestä arvoalueilla, mikä mahdollistaa funktioiden nollakohtien robustin löytämisen.
Ymmärtääksemme intervalliaritmetiikan perusajatuksen, tarkastellaan esimerkiksi funktiota f (x) = 2x. Jos meillä on arvoväli ∈ ℝ, niin voimme nähdä, että intervallilla f:n alue on intervalli . Toisin sanoen f () ⊂ .
Yleisemmin kaikilla aritmetiikan perusoperaatioilla on intervallilaajennuksia, jotka kuvaavat, miten ne toimivat intervalleilla. Jos esimerkiksi annetaan kaksi intervallia ja ,
Muulla sanoen, jos laskemme yhteen kaksi arvoa, joista toinen on välillä ja toinen välillä , niin tuloksen on oltava välillä .
Intervalliaritmetiikalla on se tärkeä ominaisuus, että sen antamat intervallit ovat konservatiivisia. Erityisesti, jos f () ⊂ ja jos c > 0, niin tiedämme varmasti, että mikään arvo in ei aiheuta sitä, että f olisi negatiivinen. Seuraavassa näytämme, miten yhtälö (2.12) voidaan laskea intervallien yli, ja hyödynnämme laskettujen intervallien konservatiivisia rajoja löytääksemme tehokkaasti pieniä intervalleja, joissa on nollapisteiden ylityksiä ja joissa voidaan luotettavasti käyttää tavanomaisia juurenetsintämenetelmiä.
Ensin määrittelemme Interval-luokan, joka edustaa reaalilukujen intervalleja.
Bounds3::Union() 78
Float 1062
Interval 112
IntervalFindZeros() 113
Lerp() 1079
Point3f 68
〈Interval Määritelmät〉 ≡
class Interval {
public:
〈Interval Public Methods 112〉
Float low, high;
};
Väli voidaan alustaa yhdellä arvolla, joka edustaa yhtä pistettä reaalilukulinjalla, tai kahdella arvolla, jotka määrittelevät nollasta poikkeavan leveydeltään poikkeavan aikavälin.
〈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)) { }
Luokka tarjoaa myös ylikuormituksia peruslaskutoimituksille. Huomaa, että vähennyslaskussa toisen intervallin korkea arvo vähennetään ensimmäisen intervallin matalasta arvosta.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);
}
Kertomista varten riippuu kyseisten arvojen merkeistä, mitkä kunkin intervallin sivut määräävät tulosvälin minimi- ja maksimiarvot. Eri mahdollisuuksien kertominen ja kokonaisminimin ja -maksimin ottaminen on helpompaa kuin sen pohtiminen, mitä niistä käytetään ja näiden kertominen.
〈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));
}
Olemme myös toteuttaneet Sin()- ja Cos()-funktiot intervalleille. Toteutukset olettavat, että annettu intervalli on vuonna , mikä pitää paikkansa näitä funktioita käyttäessämme. Tässä esitämme vain Sin():n toteutuksen; Cos() on perusrakenteeltaan melko samanlainen.
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);
}
Välin koneiston annettuna voimme nyt toteuttaa IntervalFindZeros()-funktion, joka etsii yhtälön (2.12) nollakohdan kaikkien nollakohdan läpivientien t-arvot annetulla intervallilla tInterval.
〈Interval Määritelmät〉 + ≡
void IntervalFindZeros(Float c1, Float c2, Float c3, Float c4,
Float c5, Float theta, Interval tInterval, Float *zeros,
int *zeroCount, int depth = 8) {
〈Arvioi liikkeen derivaatan intervallimuodossa, palaa, jos ei nollia 113〉
if (depth> 0) {
〈Jaa tInterval ja tarkista molemmat tuloksena saadut intervallit 114〉
} else {
〈Käytä Newtonin menetelmää nollan tarkentamiseen 114〉
}
}
Funktio aloittaa laskemalla intervallialueen yli tInterval. Jos vaihteluväli ei ulotu nollaan, funktiolla ei ole nollia yli tInterval ja funktio voi palata.
〈Arvioi liikkeen derivaatan intervallimuodossa, palaa, jos ei nollia〉 ≡ 113
Intervallialue = Intervalli(c1) +
(Intervalli(c2) + Intervalli(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;
Jos intervallialue ulottuu nollan yli, voi intervallivälissä tInterval olla yksi tai useampia nollia, mutta on myös mahdollista, että nollia ei oikeastaan olekaan, koska intervallirajat ovat konservatiivisia, mutta eivät mahdollisimman tiukkoja. Funktio jakaa tIntervalin kahteen osaan ja tarkistaa rekursiivisesti nämä kaksi osaväliä. Intervallialueen koon pienentäminen pienentää yleensä intervallialueen laajuutta, jolloin voidaan ehkä todeta, että toisessa tai molemmissa uusissa intervalleissa ei ole nollia.
Float 1062
Interval 112
Interval::high 112
Interval::low 112
Pi 1063
〈Jaa tInterval ja tarkista molemmat tuloksena saadut aikavälit〉 ≡ 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);
Kun meillä on kapea intervalli, jossa liikkeen derivaattafunktion intervalliarvo ulottuu nollan yli, toteutus siirtyy muutamaan Newtonin menetelmän iteraatioon nollan löytämiseksi aloittaen intervallien keskipisteestä. Newtonin menetelmä vaatii funktion derivaatan; koska etsimme liikkeen derivaattafunktion nollakohtia, tämä on yhtälön (2.11) toinen derivaatta:
〈Käytetään Newtonin menetelmää nollan tarkentamiseen〉 ≡ 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;