Kvaterniony a rotace

[costa]

Zdravím,

řeším rotace s využitím kvaternionů, rád bych se zeptal na pár věcí.
Zaprvé, chápu správně, že pro rotaci vezmu vektor objektu _v, převedu na kvaternion, dále vektor rotace převedu na kvaternion q, vypočítám konjugovaný q', vynásobím, získám opět kvaternion, TEN PŘEVEDU NA VEKTOR A MÁM NOVÝ VEKTOR NATOČENÍ OBJEKTU?
Za druhé, řeším transformaci z prostoru objektu (světa) do prostoru kamery, do "ořezávacího" prostoru, jde se tady nějak vyhnout převodu na matice? Jinak řečeno, existuje nějaká další "elegantnější" možnost?

A doplňující otázka, posun objektu z bodu A do bodu B se provede prostým sčítáním vektorů, že?

Díky za odpovědi, costa

[mar]

Nejsem odborník na kvaterniony, ale řekl bych, že ano.
Nicméně řekl bych, že převést kvaternion na matici nemusí být od věci, hardware/driver to stejně potom ztransformuje sám.
Výhoda (jednotkového) kvaternionu je, že se dá reprezentovat pomocí 3 hodnot (čtvrtá se dá snadno dopočítat: w^2 + x^2 + y^2 + z^2 = 1).
Další výhoda je, že pomocí kvaternionů je možné relativně snadno interpolovat mezi rotacemi.
Za druhé, tohle přece vyřeší hardware. Předpočítá si modelview * projection (4x4) a transformuje to jen jednou, přímo. (Pokud tedy nepíšeš vlastní rasterizer nebo neprogramuješ pro Glide na Voodoo Navíc projekční matici nastavíš jenom jednou (Samozřejmě pokud nerendruješ scénu víckrát z různých pozic do textur).
Jinak rotační (ortonormální) matice není přece žádné zlo. Pokud je row-major, pak první řádek reprezentuje vektor doprava, druhý nahoru a třetí dopředu. Navíc inverzní matici k ortonormální rotační 3x3 jednoduše spočítáš transpozicí. Takhle matice se dá převést na kvaternion a stejně tak kvaternion na matici, jenom je občas potřeba si dát pozor na numerickou stabilitu (to platí obecně).

Převod 3x3 rotační matice na 4x4: (row-major)

[costa]

Díky za odpověď. Nezmínil jsem se o tom, že využití bude pro software rendering, takže výhody rychlého hw zpracování matic odpadají - právě proto se ptám, jestli jde řešit projekci i jinak.
Matice samozřejmě nejsou zlo, ale vycházím z ~poloviční paměťové náročnosti kvaternionů vůči maticím, a taky z třetinově dlouhého kódu pro transformaci.
Jediné, co mně zbývá, je vyřešit projekci, a nerad bych to teď převáděl na matice.

[mar]

No myslím si, že použít projekční matici nemusí být od věci. Kdysi jsem psal jednoduchý sw rasterizer (openGL). Šel pod tím rozjet třeba prastarý GLQuake nebo Half-Life. Je to opensource, link je tady: http://sourceforge.net/projects/c00ngl/
Tady jsem používal matice, zdrojáky bexera už nemám, takže jak přesně jsem to řešil tam, už nevím.
Každopádně to používá ordered dithering na u,v při rasterizaci, takže ve slušném rozlišení to dělá něco jako bilinear effect, ale neinterpoluješ mezi 4mi texely, jenom sampluješ z posunutého místa. Myslím, že tohle dělal starý Unreal v sw režimu.
Nejjednodušší, co mě napadá, je ořezat to ve 3d na near plane (ořezat trojůhelník rovinou), případně i far plane a zbytek ve 2d na viewport.
Myslím, že jsem to řešil tak, že se to ořeže left, zbytek right, pak top a nakonec bottom. Ale je možné (a nedivil bych se), kdyby existoval rychlejší způsob kde se to ořeže ve 2d na obdélník přímo.
Navíc pro perspektivní korekci stejně budeš muset něčím dělit na každý transformovaný vertex.
Vždycky jsem pracoval s koplanárními konvexními polygony, ale dalo by se rasterizovat i trojůhelníky (ořezaný trojůhelník dá polygon a ten se dá snadno - triangle fan - tesselovat).
EDIT: jinak paměťová náročnost kvaternionů může být kolem třetiny až čtvrtiny, ale ten třetinově dlouhý kód mi uniká. vektor * 3x3 matice oproti transformaci kvaternionem mi dává jenom o něco málo víc násobení (plácnu 5-10%), takže nevím. Ale možná jsem to špatně spočítal.
A potom dnes se dají využít SSE4.1 instrukce pro dot product (pokud máš CPU co to umí, viz http://msdn.microsoft.com/en-us/library/bb514054.aspx), takže násobení vektoru maticí by mělo být fakt docela rychlé.

[Vilem Otte]

Technicky vzato matice budou stále pro transformaci vektor maticí rychlejší - kód v SSE2 intrinsicích:

[costa]

Děkuji za odpovědi, píšu to jako "playground project"
Narazil jsem ještě na jednu věc, v případě, že chci objekt posunovat po jeho lokálních souřadnicích, tak prosté sečtení vektorů nepomůže, jak tedy vyřešit posun?

[Vilem Otte]

Pokud chceš posouvat projekt po lokálních souřadnicích (a tedy báze lokálních souřadnic je jiná než báze globálních souřadnic) - ztransformuj posunový vektor do báze lokálních souřadnic, pak ti stačí pouhý posun vektorů.

V maticové algebře máš rotační matici M která je "model" maticí objektu (avšak bez transformací - pouze 3x3 rotační část matice), vektor V o který chceš posunout a bod P reprezentující objekt (již ztransformovaný rotační maticí).

P' = P + M * V

Což je posun o vektor V v lokálních souřadnicích objektu P.

S quaterniony je to obdobné, vektor V ztransformuješ quaternionem Q, následně provedeš prosté sčítání.
_________________
Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration.

[costa]

Jsem mírně frustrován,

říká se, že kvaterniony proti maticím mají obecně výhodnější paměťové nároky (7 float u kvaternionů pro posun a rotaci vůči 16 floatům u matice), což je pravda, ale po tom, co jsem si napsal rotaci vektoru pomocí kvaternionů, jsem došel k závěru, že pro transformaci bodů stejně potřebuju někde ukládat minimálně 2 vektory (kam míří osa x, osa y objektu), které transformuju kvaternionem a třetí dopočítat vektorovým součinem, čímž se dostávám na paměťovou náročnost maticových transformací... je to tak?

Mohl by mně někdo vysvětlit, jak se provádí samotná transformace bodu (o které jsem si už myslel, že jí rozumím)?

Jo, a děkuju vám za odpovědi

[mar]

No když pominu, že přesně nerozumím, proč řešíš paměťové nároky u matice vs kvaternion:
Řekněme, že máš množinu bodů v object space (=vektory okolo [0,0,0]).
A ty chceš transformovat do world space.
Řekněme, že nás zajímá jenom posun a rotace.

Každý bod nejdřív orotuješ a pak ho posuneš.
Takže dostaneme v' = v * M + p
v je bod v object space, M je rotační matice a p je počátek objektu ve world space.
v * M (nebo M * v pokud je M column-major) můžeš nahradit těmi kvaterniony.
Pokud použiješ matice, můžes použít třeba 4x3 matici, kde poslední řádek bude počátek a pošleš tam (x,y,z,1), ale to je totéž, jenom zapsáno jinak.
Co se týká dalších pomocných vektorů, tak ty nepotřebuješ. Na rotace stačí jeden kvaternion nebo jedna 3x3 matice. Záleží na tom, čeho chceš přesně docílit.
Dva vektory potřebuješ, pokud počítáš lookat matici.

EDIT:
Pro ortonormální (=rotační) matice 3x3 platí následující:
(A je matice, v je vektor, AT je transponovaná, ^-1 inverzní)
AT = A^-1
v * A = AT * v
proč to píšu: kvůli camera space. transformace do camera space (=world space relative to camera) bude totiž transformace inverzní k rotační matici kamery.
vc = C * (v' - cp)
kde C je rotační matice kamery a cp je pozice kamery a vc je v camera space

[costa]

Takže chápu to správně, že na každý vrchol (vektor) použiju transformaci vektoru kvaternionem rotace, získám novou polohu natočeného bodu, pak ho posunu...?

Jetš jedna otázka, jde pomocí kvaternionů (nebo jiným - ne maticovým způsobem) provést transformaci z world space do camera space?

[pcmaster]

Odpoved na poslednu otazku podla mna je, ze nijakym rozumnym nematicovym sposobom to nejde Ta transformacia (vidno to uz z matice) nie je ani ortonormalna, ani ortogonalna, je tam scale a vsetko mozne, kurvi to homogenny (w) koordinat Mozes to sice rozbit na jednotlive operacie (pozri si dokumentaciu k vyrobe perspektivnych matic v kazdych vysokoskolskych skriptach alebo v MSDN ci OpenGL docs), ale je to IMHO velmi kontraproduktivne Ale ak myslis "camera space" len "view maticu", tak to mozne je (rotacia + translacia + scale...). Do "eye space" (projection matica) to uz nie je mozne.
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.

[mar]

Ano chápeš to správně.
S 4x4 maticemi uděláš i projekci, o tom to celé je, proto Direct3D i OpenGL používají právě tyhle matice.
Potom můžeš skládat libovolná zobrazení jednoduše tak, že násobíš matice.
Takže jak jsem už psal, nastavíš projection matici, pak řekněmě x-krát měníš modelview jak kreslíš různé objekty. Driver si to ale předpočítá (vynásobí ty matice), takže transformace jednoho bodu se zredukuje na jedno násobení maticí.
Rozepsal jsem to pro jednoduchost, aby to šlo IMHO líp pochopit.
Na závěr vydělíš x, y, z w (=dostaneš normalizované souřadnice) a zhomogenizuješ a hotovo, máš to v homogenních souřadnicích ve screen space. (samozřejmě před tím dělením provedeš ten clipping).

Mimochoden pořád nechápu, proč se vyhýbáš maticím?
násobení vektoru maticí 4x4 jsou 4 skalární součiny
A u sw rendereru stejně strávíš nějvíc času rasterizací.

[Marek]

pcmaster> Eye a view space je podle mě jedna stejná věc. Prostor souřadnic po transformaci projekční maticí se nazývá clip space nebo taky post-projective space.
_________________
AMD Open Source Graphics Driver Developer

[mar]

Ještě jedna drobná poznámka: pokud budeš pracovat s normálovými vektory, je potřeba si dát pozor na jednu věc a to je non-uniform scaling.
Pokud například násobím vertexy (2,1,1), musím normály násobit (0.5,1,1), tj. 1/scale.
U matic to znamená normálám dát do w nulu (nx, ny, nz, 0) a násobit transponovanou inverzní maticí. Samozřejmě výsledné normály je potřeba v takovém případě renormalizovat. Pokud vůbec nepoužiješ scaling a řešíš jenom rotace + posunutí, tak tohle všechno odpadá.

[costa]

Děkuji vám za odpovědi,

jenom bych se zeptal ještě na poslední věc, psali jste, že se jde dobrat souřadnic vrcholů v prostoru kamery, (odpovídá modelview matici), .. jak? Pokud beru v úvahu, že kamera může být natočená a posunutá.

Jo, a ještě k tomu kvaternionu (furt dokolečka ), výchozí kvaternion neorotovaného objektu je: 1 + 0i + 0j + 0k, na tento pak aplikuju všechny další rotace... je tak?