ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA ELEKTROTECHNICKÁ

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA ELEKTROTECHNICKÁ

DIPLOMOVÁ PRÁCE

Animace s pomocí inverzní kinematiky

Autor: Bohuslav Franc

Vedoucí diplomové práce: Doc. Ing. Jiří Žára, CSc.

Akademický rok: 2004/2005

Poděkování Na tomto místě bych chtěl poděkovat všem kantorům a studentům, kteří mi věnovali svůj drahocenný čas, hodnotné rady a podporu při vývoji této práce. Dále bych chtěl poděkovat své rodině a přátelům za duševní oporu, která mě udržovala při zdravém rozumu a obnovovala sílu vydržet.

Prohlášení

Prohlašuji, že jsem svou diplomovou práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu.

Nemám závažný důvod proti užití tohoto školního díla ve smyslu § 60 Zákona č.121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů.

V Praze dne ……………………….

………………………………. podpis

Obsah

1 Obsah 1 Obsah ...............................................................................................................................3 2 Seznam obrázků ..............................................................................................................5 3 Abstrakt............................................................................................................................6 4 Úvod .................................................................................................................................7 5 Animace ...........................................................................................................................8 5.1 Kloubová struktura ....................................................................................................10 5.2 Inverzní kinematika ...................................................................................................11 5.2.1 Iterativní metody ..............................................................................................12 5.3 Inverzní kinematika humanoidů.................................................................................13 6 Algoritmy a datové typy ................................................................................................15 6.1 Kloubová struktura ....................................................................................................15 6.1.1 Klouby..............................................................................................................15 6.1.2 Problém pořadí dílčích kloubů .........................................................................17 6.1.3 H-Anim.............................................................................................................20 6.2 Inverzní kinematika ...................................................................................................22 6.2.1 Algoritmus CCD ...............................................................................................22 6.2.2 Více koncových efektorů..................................................................................23 6.2.3 Hledání kinematického řetězce........................................................................25 6.3 Reprezentace rotace ve 3D ......................................................................................28 6.3.1 Převody reprezentací rotace............................................................................30 7 Implementace ................................................................................................................33 7.1 Výpočet změny úhlu..................................................................................................34 7.1.1 Analytický výpočet ...........................................................................................35 7.1.2 Maticový výpočet .............................................................................................36 7.1.3 Vektorový výpočet ...........................................................................................39 7.2 Limity a odpory..........................................................................................................42 7.2.1 Limity kloubů....................................................................................................42 7.2.2 Odpor svalů .....................................................................................................43

3

Obsah

7.3 Aktualizace struktury.................................................................................................44 7.3.1 Počáteční transformace ...................................................................................45 8 Experimentální program ...............................................................................................48 8.1 Kloubová struktura ....................................................................................................48 8.1.1 ikElement.........................................................................................................49 8.1.2 ikJoint ..............................................................................................................49 8.1.3 ikSite................................................................................................................50 8.2 Načtení humanoida z VRML scény ...........................................................................50 8.2.1 Převod z H-Anim..............................................................................................51 8.3 CCD ..........................................................................................................................52 8.4 ikAnimation ...............................................................................................................54 8.4.1 Vytváření snímků .............................................................................................54 8.4.2 Zamezení dlouhého výpočtu............................................................................55 8.4.3 Animace...........................................................................................................56 8.4.4 Ukládání animací do souboru ..........................................................................57 8.5 Optimalizace rychlosti ...............................................................................................58 8.5.1 Operační složitost ............................................................................................60 9 Závěr...............................................................................................................................61 Příloha A – Uživatelská příručka.......................................................................................62 A.1 Ovládání aplikace .....................................................................................................62 A.1.1 Normální mód ..................................................................................................63 A.1.2 Reálný mód .....................................................................................................64 A.1.3 Okno animační knihovny..................................................................................65 A.2 Speciální soubory .....................................................................................................66 A.2.1 Formát scény...................................................................................................67 Příloha B – Obsah CD........................................................................................................69 Literatura ............................................................................................................................70

4

Seznam obrázků

2 Seznam obrázků Obrázek 5.1: Definice základních pojmů.................................................................................9 Obrázek 5.2: Druhy kinematiky .............................................................................................10 Obrázek 5.3: Počáteční a koncový stav kloubové struktury ..................................................11 Obrázek 5.4: Nezávislost limitů kloubů na celkové situaci ....................................................14 Obrázek 6.1: Reprezentace kloubu.......................................................................................16 Obrázek 6.2: Rozložení celého kloubu na dílčí klouby..........................................................16 Obrázek 6.3: Orientace humanoida v souřadném systému...................................................17 Obrázek 6.4: Nesprávné pořadí dílčích kloubů .....................................................................18 Obrázek 6.5: Rovnoběžnost kostí s osami............................................................................19 Obrázek 6.6: Struktura H-Anim .............................................................................................21 Obrázek 6.7: Iterace CCD metody ........................................................................................23 Obrázek 6.8: Střídání iterací .................................................................................................24 Obrázek 6.9: Oscilace kinematických řetězců.......................................................................25 Obrázek 6.10: Kinematický řetězec ......................................................................................26 Obrázek 6.11: Nalezení společného předchůdce .................................................................27 Obrázek 6.12: Aplikace změny úhlu v kinematickém řetězci.................................................28 Obrázek 6.13: Eulerovy úhly.................................................................................................29 Obrázek 6.14: Rotace osa - úhel ..........................................................................................29 Obrázek 7.1: Změna úhlu ve 2D ...........................................................................................34 Obrázek 7.2: Analytický výpočet ...........................................................................................36 Obrázek 7.3: Transformace lokální souřadné soustavy ........................................................37 Obrázek 7.4: Minimalizace chyby orientace..........................................................................38 Obrázek 7.5: Příklad vektorového výpočtu............................................................................40 Obrázek 7.6: Limity kloubu ...................................................................................................42 Obrázek 7.7: Počáteční transformace...................................................................................45 Obrázek 7.8: Posunutí kořene ..............................................................................................46 Obrázek 7.9: Změna počáteční transformace .......................................................................47 Obrázek 8.1: Hierarchie tříd..................................................................................................48 Obrázek 8.2: Ortonormální vektory .......................................................................................53 Obrázek 8.3: Výpočet předpokládaného počtu iterací...........................................................56 Obrázek 8.4: Tabulka optimalizací........................................................................................59

5

Abstrakt

3 Abstrakt Úkolem této práce je prostudovat animaci virtuálních humanoidů zadaných specifikací H-Anim a ukázat možné postupy při vytváření aplikace této úlohy. Animace využívá inverzní kinematiky, konkrétně metody CCD (cyclic coordinate descent). Přihlíží se k současnému využití více koncových efektorů, limitům kloubů a odporu svalů, což jsou nezanedbatelné atributy animace lidské postavy. První část práce se zabývá seznámením s inverzní kinematikou, kloubovou strukturou, specifikací H-ANIM, osvětlením teorie, možnostmi reprezentace a různými problémy, které se mohou vyskytnout během implementace. Druhá část je zaměřena na samotné programování knihovny a aplikace, jež ji využívá.

The task of this work is studying of virtual humanoid animation engaged by specification H-Anim and to show available progress during creating of the application. Animation uses CCD (cyclic coordinate descent) method of inverse kinematics. The work looks on multiple end effectors, joint limits and stiffness of muscles that are indispensable attributes of human body animation. The first part handles identification of inverse kinematics, articulated structure, H-ANIM specification, theory explaining, chances of representation and possible obstacles that can occur in implementation. The second part focuses at library programming and application.

6

Úvod

4 Úvod Co si běžný člověk představí pod pojmem „animace“? Pokud je model napodobení originálního předmětu, tak animace je napodobení originálního pohybu. Animaci lze chápat různě, což jenom podporuje její masivní rozšíření v aktuálním časovém horizontu. Animací můžeme nazvat mnoho věcí kolem nás. V televizi můžeme sledovat animované pohádky, můžeme hrát počítačové hry nebo navštěvovat divadelní představení, v kterých se herci snaží napodobit pohyb stromu ve větru. Všude tam lze nalézt animaci. V některých případech může hrát animace pouze vedlejší roli, uveďme například kontroverzní seriál South Park. Na druhé straně ve vojenském trenažéru stíhacího letadla je realističnost animace hlavním požadavkem. Při ověřování odolnosti automobilů pomocí takzvaných crash-testů je animace dokonce jediným schůdným řešením. V poslední době dosáhla animace asi největšího rozkvětu na poli zábavního průmyslu. Filmy a počítačové hry mají výrazný podíl na vývoji animace. Pro srovnání jmenujme slavný japonský film Godzilla z roku 1954, který v době svého vzniku vyvolal velké nadšení, zatímco o čtyřicet let mladší a daleko propracovanější verzi nebylo stejného úspěchu dopřáno. Hlavním úkolem tohoto projektu bylo prostudování problému implementace animace na virtuálních humanoidech. Zkoumaným animačním mechanismem se stala CCD metoda inverzní kinematiky. Jsou zde řešeny problémy na úrovni fyzických atributů člověka jako je odpor svalů či limity kloubů. Reprezentacím 3D rotace a převodům mezi nimi byla zvlášť věnována jedna kapitola. Text se dále zaměřuje na animaci pomocí více efektorů a řešení oscilace či nedosažení cíle. Nemalou část práce tvoří plnohodnotná aplikace, která zároveň slouží jako demonstrace zde pospaných algoritmů. Aplikace umožňuje provádět výpočty libovolných animací pomocí volně konfigurovatelných souborů. Vzhled a struktura humanoida také čistě závisí na tvořivosti uživatele [Bei]. Animace lidské postavy je rozšíření animace libovolné struktury, a proto není uplatnění tohoto programu závislé pouze na humanoidech, což jeho použití ještě více rozšiřuje. Díky rozlehlé struktuře některých humanoidů a výpočetní složitosti algoritmů byl brán ohled i na optimalizaci rychlosti. Od počátku se předpokládalo použití dosažených výsledků i v jiných projektech, a proto byl výsledný program koncipován na dvě části. Hlavním artiklem jsou knihovny provádějící animaci za použití inverzní kinematiky, které využívá demonstrační program. Důkazem může být použití animačních knihoven v paralelně vznikající diplomové práci Martina Lindy [Lin05].

7

Animace

5 Animace Ve výpočetní technice lze považovat za animaci cokoliv, co se hýbe. Pro naši potřebu je nutné tento výrok zkonkretizovat. Nyní budeme za animaci považovat pohyb celého objektu a jeho částí. Existuje mnoho technik jak animovat nějaký objekt. Pohyb lze snímat přímo z originálu nebo jej pouze simulovat pomocí vhodných algoritmů. V poslední době velmi oblíbenou technikou, která poskytuje kvalitní a autentické výsledky, je technologie motion capture. Tato metoda pracuje na principu snímání pohybu z originálu. Je mnoho způsobů, jak pohyb snímat, ale většinou je objekt pokryt reflexními body, které jsou snímány vysokofrekvenčními digitálními kamerami. Použití lze nalézt například v české počítačové hře Mafia či v americkém animovaném filmu Polární Express. Počet a umístění bodů se různí. Díky finanční nákladnosti této technologie se volí malý počet reflexních bodů, jež se umísťují pouze na nejdůležitější části těla. Zpravidla se jedná o klouby na rukou, nohou a trupu těla. V takových případech jsou pozice zbylých částí těla dopočítávány pomocí algoritmů, například metodou inverzní kinematiky. Animační metody, které žádoucí pohyb pouze vypočítávají bez předlohy, mají mnohem složitější práci. Aby byla zachována co největší věrohodnost animace musejí během výpočtů simulovat mnoho fyzikálních aspektů objektu i okolí. V závislosti na animované scéně lze pracovat například s gravitací, větrem, tuhostí či kolizí s jinými objekty. Objekt lze reprezentovat mnoha způsoby. Je ale nutné přihlédnout k faktu, že objekt bude animován a proto by měla jeho reprezentace animaci umožňovat. Mechanický objekt či humanoid zpravidla zachovává svoji topologii a mění se pouze pozice jeho částí. Animace je tedy docílena různým ohýbáním elementů objektu. Při volbě reprezentace je možno se motivovat kostrou člověka. Topologie je zachována díky kostem, které nemění svoji délku, a ohýbání elementů je zajištěno klouby mezi kostmi. Pro reprezentaci animovaného objektu se tedy volí kloubová struktura, se kterou pracují animační algoritmy. Pro popis animačních algoritmů je nutné zavést několik pojmů. K tomu je vhodné definovat animaci jako umístění jisté části objektu do cílové pozice a orientace. Element objektu, pro který je znám cíl a jehož funkcí je dosažení tohoto cíle, se nazývá koncový efektor (nebo jen efektor). Nechť je objektem člověk a touženou animací je předpažení ruky z běžného postoje. Koncovým efektorem může být v tomto případě dlaň ruky. Poloha, do které je nutné koncový efektor situovat, bude v tomto projektu nazvána jednoduše cílem. Koncový efektor i cíl mají mimo pozice přiřazenou i orientaci. Při předpažení ruky nejsou ovlivňovány všechny prvky těla. Mění se pouze ta část, které se to bezprostředně týká. Měnící se část kloubové struktury je připojena ke statické části, která je nazývána bází.

8

Animace

V případě předpažení je bází rameno. Báze je pevný bod v kloubové struktuře, jehož pozice je globální pro měnící se část, zatímco koncový efektor je prvek určující celou animaci. Ta část kloubové struktury, která je animací ovlivňována, se nazývá kinematický řetězec. Kinematický řetězec je z jedné strany ohraničen efektorem a z druhé strany bází. Kinematickým řetězcem je v našem příkladě celá ruka.

Obrázek 5.1: Definice základních pojmů

Nyní se věnujme malému úvodu k principu animace. Kinematika je věda o pohybu fyzikálních objektů bez ohledu na působící síly. V tomto textu se kinematika chápe pouze jako animační technika. Lze ji rozdělit do dvou vzájemně opačných tříd: dopředná kinematika a inverzní kinematika. Jejich odlišnost je založena na vztahu mezi částmi objektu a výsledným pohybem. Zatímco dopředná kinematika získá pohyb z ovládání částí objektu, tak inverzní kinematika zjišťuje umístění částí objektu z požadovaného pohybu. Problém lze ilustrovat na jednoduchém příkladě, ve kterém nám jako animovaný objekt opět poslouží ruka. Umístění částí ruky reprezentují úhly, které jsou svírány klouby. Koncovým efektorem je opět dlaň ruky. Dopředná kinematika vypočte pozici efektoru z úhlů kloubů, zatímco inverzní kinematika vypočte úhly kloubů z pozice efektoru (Obrázek 5.2). V případě dopředné kinematiky je poloha efektoru funkčně závislá na úhlech kloubů, narozdíl od inverzní kinematiky, kde je vztah přesně opačný. Znamená-li funkce f výpočet pozice a orientace efektoru z úhlů kloubů, tak lze dopřednou kinematiku vyjádřit vztahem:

poloha dlaně = f ( úhly kloubů )

9

(1)

Animace

a pro inverzní kinematiku platí:

úhly kloubů = f -1 ( poloha dlaně )

a) dopředná kinematika

(2)

b) inverzní kinematika

Obrázek 5.2: Druhy kinematiky

5.1 Kloubová struktura Každý objekt, se kterým lze manipulovat, lze zjednodušit na tzv. kloubovou strukturu. Jedná se o strukturu kloubů a segmentů, které jsou na sebe navzájem napojeny [Bae01]. V případě člověka je kloubová struktura takřka totožná s kostrou, kde segmenty zastupují kosti. Kloubová struktura odpovídá stromové struktuře, kde kloubům korespondují uzly a segmenty jsou spojnice mezi uzly. Manipulaci se strukturou zajišťují pouze klouby. Existují klouby posuvné a rotační. Posuvné klouby umožňují posun ve směru předchozího segmentu. Zrod inverzní kinematiky pochází totiž z robotiky, kde ramena robotů umožňují teleskopické prodloužení. Lidská postava tuto přednost nevlastní, a tak se posuvné klouby v tomto projektu nevyskytují. Rotační klouby dovolují rotaci kolem svého středu. V případě dvourozměrného souřadného systému svírá každý kloub mezi dvěma segmenty jeden úhel, a proto má pouze jeden stupeň volnosti, což se zkráceně zapisuje jako 1DOF (degrees of freedom). Trojrozměrný prostor však umožňuje kloubům větší volnost. Podle Eulerova teorému lze libovolnou rotaci ve 3D popsat třemi proměnnými [EWW]. Každý kloub tedy disponuje maximálně třemi stupni volnosti. Slovo maximálně je použito záměrně, neboť některé klouby

10

Animace

mohou mít pouze jeden nebo dva stupně volnosti. Například při zanedbání mírného natáčení nohy můžeme prohlásit, že lidské koleno má k dispozici pouze jeden stupeň volnosti. Na druhou stranu rameno má všechny tři. Pomocí DOF lze vyjádřit i volnost celého kinematické řetězce. Volnosti jednotlivých kloubů se jednoduše sčítají. Stupeň volnosti kinematického řetězce se spočítá jako součet stupňů volnosti všech jeho kloubů. Kinematický řetězec, který se skládá z deseti plnohodnotných kloubů, tedy disponuje třiceti stupni volnosti.

5.2 Inverzní kinematika Cílem algoritmů inverzní kinematiky je najít takové hodnoty úhlů kloubů mezi koncovým efektorem a bází, aby byla pozice a orientace efektoru shodná s pozicí a orientací cíle (Obrázek 5.3). Výpočetní metody inverzní kinematiky se dají v základě rozdělit mezi exaktní a iterativní. Exaktní neboli analytické metody jsou přesné, ale většinou špatně použitelné při různých podmínkách kloubové struktury jako je například odpor svalů nebo limity kloubů. Jsou jednoprůchodové a pokouší se najít přesné vyjádření funkce f -1 ze vztahu (2). Jejich použití je velmi omezené, protože není známě řešení pro více stupňů volnosti kinematického řetězce [Kav02].

Obrázek 5.3: Počáteční a koncový stav kloubové struktury

11

Animace

5.2.1 Iterativní metody Iterativní neboli numerické metody jsou víceprůchodové a jsou zaměřeny více na kloubovou strukturu a její procházení. Jejich výhodou je rychlost a aplikovatelnost různých parametrů kloubů. Na druhou stranu ale nemusí být tak přesné a v některých krajních situacích nemusejí ani dosáhnout kýženého výsledku. Jedním ze zástupců iterativních metod, který zde nebude popsán do detailů, je inverze Jakobiánu. Vztah mezi pozicí efektoru a úhly kloubů lze popsat pomocí soustavy nelineárních rovnic. Přímě řešení takové soustavy rovnic není možné a proto je nutné převézt tuto soustavu na lineární, která by však vyjadřovala pouze přibližné řešení. V této transformaci figuruje Jakobián jako vícerozměrné rozšíření derivace neboli zastupuje přechod od diferenciálních změn úhlů k diferenciálním změnám polohy efektoru. Protože jsou však hledány úhly kloubů, tak je nutné vypočítat inverzi Jakobiánu. Transpozice Jakobiánu je jistou obměnou předešlého algoritmu, která je založena na výpočtu transpozice Jakobiánu namísto obtížné inverze. Obě metody jsou hlouběji objasněny v [Bar03], [Bae01], [Wel93]. Asi nejjednodušší iterativní metodou inverzní kinematiky je CCD - Cyclic Coordinate Descent, která byla použita v tomto projektu. Princip je založen na procházení kloubů kinematického řetězce od efektoru k bázi a každý kloub je pootočen tak, aby byl efektor nejblížeji k cíli a zároveň nejlépe naorientován. Jedno projití kinematického řetězce se nazývá iterace. Iterace se opakují, dokud není dosaženo požadovaného výsledku. Podrobněji je tato metoda popsána v kapitole 6.2.1. Protože iterativní metody nejsou jednoprůchodové a v každé iteraci efektor pouze přibližují, tak ve skutečnosti efektor nikdy nedosáhne stejné polohy jako cíl. Mohou nastat i výjimky, ale v běžné praxi je to nepravděpodobné. Díky tomuto faktu se definuje tzv. chyba koncového efektoru, která představuje jisté ohodnocení aktuální polohy koncového efektoru vůči svému cíli. Je to součet vzdálenosti efektoru od cíle a odchylek jejich orientací. Je tedy nutné zvolit si práh přesnosti, který definuje maximální povolenou chybu koncového efektoru. Pokud je chyba koncového efektoru menší než práh přesnosti, tak se algoritmus ukončí a výsledná poloha je považována za dosažení cíle. Princip iterativních metod je tedy ve skutečnosti minimalizace chyby koncového efektoru v každém kroku metody. Existují však případy, kdy je cíl příliš daleko a neexistuje žádná kombinace úhlů kloubů, která by zapříčinila, aby efektor dosáhl cíle. Pro tyto případy musí být zavedeno jisté ošetření, aby se výpočet přerušil. Tento fakt je podrobněji zpracován v kapitole 8.4.2.

12

Animace

5.3 Inverzní kinematika humanoidů Inverzní kinematika humanoidů přímo navazuje na dosud probíranou inverzní kinematiku. Jedná se pouze o různé modifikace algoritmů a datových typů s přihlédnutím k animaci lidské postavy. V případě, že bychom aplikovali výpočty prosté inverzní kinematiky na strukturu humanoida, tak by bylo možné ovládat lidskou postavu libovolným způsobem. To ale v reálném světě není úplně možné kvůli omezení kostí, svalů, šlach atd. Tato omezení musejí být také nějakým způsobem zahrnuta při výpočtech inverzní kinematiky. Jak již bylo uvedeno, každý animovaný objekt je při výpočtu inverzní kinematiky nahrazen kloubovou strukturou. Je to mu tak i u reprezentace humanoidů. Kloubová struktura odpovídá kostře člověka, a proto tvoří acyklický graf, přesněji nepravidelný n-ární strom. Důležitým prvkem stromu je jeho kořen. Ten by měl být umístěn tak, aby se nejméně měnila jeho pozice a zároveň byl určitým těžištěm kloubové struktury. V případě člověka je umístěn v oblasti pánve. Pánev se zpravidla pohybuje nejméně a proto je to vhodný bod pro aplikaci globální transformace humanoida. Velmi důležitým a při animaci lidské postavy takřka nezbytným prvkem jsou limity kloubů. Jsou ekvivalentem fyzického omezení kostí a díky limitům lze zabránit, aby se humanoid

pohyboval

v libovolných

polohách

[Fen81].

Slouží

k omezení

obecně

nekonečného množství řešení úlohy inverzní kinematiky. Převážně pomocí limitů lze určit rozsah působnosti humanoida, protože omezují rotaci kloubů. Zaručí, že výsledná animace bude proveditelná lidskou bytostí, která je animována. Bohužel limity kloubů jsou individuální záležitostí a každý člověk disponuje jinými omezeními. Hodnoty limitů použité v tomto projektu byly nejprve převzaty z dodaných materiálů, ale během vývoje se ukázalo, že jsou nepoužitelné, a byly postupně nahrazovány novými, které byly získávány intuitivně či z výsledků testovacích scén. Další komplikací je fakt, že limity jsou ve skutečnosti závislé na aktuálním uskupení kostry člověka. Svaly a šlachy totiž omezují některé krajní pohyby a tím se také podílejí na limitech pohybu. Uveďme pregnantní ilustraci. Každý člověk dokáže v koleni napnout nohu, což odpovídá poloze ve stoje. Téměř každý člověk také dokáže přitisknout koleno ke své bradě. Ale málo který člověk dokáže tyto úkony vykonat najednou (Obrázek 5.4).

13

Animace

Obrázek 5.4: Nezávislost limitů kloubů na celkové situaci

Jak je v kapitole 5.2.1 popsáno, CCD metoda mění úhly kloubů od efektoru k bázi. To v praxi znamená, že se nejvíce mění úhly u kloubů, které jsou blíže k efektoru na úkor kloubů bližších bázi. Ve skutečnosti však klouby ohýbáme odlišným způsobem. Pro vyvážení tohoto faktu a zároveň pro větší realismus výsledku jsou zavedeny odpory svalů. Protože kloubová struktura ale svaly neobsahuje, tak je výhodnější použít termín tuhost nebo odpor kloubů. Zatímco limity určovali spíše statickou část rozsahu humanoida, tak se odpor kloubů podílí na dynamické stránce inverzní kinematiky. Ač to není příliš patrné, tak odpor má v inverzní kinematice velký význam. Pomocí odporu lze dolaďovat výpočty tak, aby animace vypadala věrohodně. Bohužel neexistuje unikátní nastavení odporů pro humanoida. To znamená, že pro jistou animaci mohou odpory plně dostačovat, ale v jiné situaci ovlivňují výpočet nepříznivě. Hodnoty odporů pro jednotlivé klouby nejsou pravděpodobně nikde uvedeny a je to pouze jistá aproximace reálného pohybu člověka. Hodnoty byly tedy získány čistě během testování.

14

Algoritmy a datové typy

6 Algoritmy a datové typy Úkolem této kapitoly je nastínění reprezentací algoritmů a datových typů pro výpočty inverzní kinematiky. Přibližuje náhled na vnitřní strukturu projektu pomocí jejich zjednodušených verzí, které dostačují pro vysvětlení problému. Každý algoritmus i datový typ má své přednosti i nedostatky, jež jsou zde popsány. V sekci kloubové struktury je uveden formát H-Anim, ze kterého bylo nutné vycházet při výběru reprezentace celé kloubové struktury i jednotlivých atributů kloubů. Přihlíží se i k algoritmu CCD metody a jeho výchozí verze je základem i v jiných kapitolách tohoto projektu. Reprezentaci rotace ve 3D byla věnována celá kapitola, protože existuje mnoho druhů a na její volbě velmi záleží.

6.1 Kloubová struktura V kapitole 5.1 je nastíněno schéma kloubové struktury, které bude v tomto textu upřesněno. Jak již bylo uvedeno, kloubová struktura má tvar stromu skládajícího se z kloubů a segmentů. Protože se strom větví v uzlech, které odpovídají kloubům, tak i kloubová struktura se musí větvit v kloubech. Segmenty tedy zajišťují čistě spojnice mezi klouby, což znamená pouhé posunutí souřadného systému. Protože nemají žádnou další funkci, nebudou implementovány jako datový typ.

6.1.1 Klouby Hierarchické uspořádání kloubové struktury umožňuje definování sama sebe pouze pomocí kloubů. Předkem kloubu bude nazýván jakýkoliv kloub, který je v hierarchii nad aktuálním kloubem a leží na nejkratší cestě mezi kořenem a popisovaným kloubem. Jediný kloub, který nemá žádného předka je kořen. Potomkem kloubu je libovolný kloub, který leží v podstromu, jehož kořenem je popisovaný kloub. Nejbližším předek kloubu se nazývá otec a nejbližší potomci kloubu budou označeny jako synové (Obrázek 6.1a). Protože segmenty nebudou zvlášť implementovány, tak musí být přiřazeny ke kloubům jako atribut. Každý kloub obsahuje informace o segmentu, který leží mezi ním a otcem. Kloub může nebo nemusí mít více synů, ale vždy (až na kořen) má pouze jednoho otce, a proto je tato volba výhodnější.

15


Kloubová struktura se ohýbá v kloubech, a proto každý kloub umožňuje rotaci kolem svého středu [Bae01]. Díky tomu je natáčen celý podstrom, jehož je kořenem. Rotace kloubu je bohužel definována pouze pro kloub a to znamená, že jsou ovlivňovány všechny synové kloubu a nejednou. Úhel mezi jednotlivými syny proto nelze měnit. Tento fakt lze naznačit tak, že segmenty, které jsou přímými následníky uzlu, jsou pevně svázány (Obrázek 6.1b).

a) okolí kloubu

b) svázání sousedních segmentů Obrázek 6.1: Reprezentace kloubu

Rotace kloubu je v tomto projektu reprezentována Eulerovými úhly. Jejich popis a důvod použití je uveden v kapitole 6.3. Práce s rotací v trojrozměrném prostoru není lehká záležitost, a proto se provádí jisté zjednodušení kloubu. Velkým přínosem je rozdělení kloubu o 3DOF na tři klouby o 1DOF (Obrázek 6.2).

Obrázek 6.2: Rozložení celého kloubu na dílčí klouby

16


Obecné klouby budou tedy nazývány jako celé klouby, které lze rozložit na tři dílčí klouby. Každý dílčí kloub disponuje pouze jedním stupněm volnosti stejně jako kloub v plošné reprezentaci. Tento fakt umožňuje rozložit Eulerovy úhly celého kloubu na své složky, které jsou přiděleny dílčím kloubům. Problém hledání třech úhlů jednoho kloubu je tedy převeden na trojité hledání jednoho úhlu, což je mnohem jednodušší. Je nutné připomenout, že dílčí klouby se ve skutečnosti v kloubové struktuře nevyskytují a slouží pouze jako imaginární zjednodušení pro výpočty a popis situací.

6.1.2 Problém pořadí dílčích kloubů Jak již bylo popsáno v kapitole 6.1.1, kloub struktury se dělí na dílčí klouby, aby se rozdělili složky Eulerových úhlů. Ač to není příliš zjevné, tak při výpočtech inverzní kinematiky záleží na pořadí dílčích kloubů. Rozdělením na dílčí klouby totiž určíme pořadí a prioritu složek Eulerových úhlů. To bohužel velmi ovlivňuje výsledný efekt. První problém se vyskytuje ve spojení s limity (7.2.1). V následujícím příkladu předpokládejme, že pořadí dílčích úhlů je uspořádáno podle názvů složek v abecedním pořádku. Nejprve tedy probíhá rotace kolem osy x, poté kolem y a nakonec kolem osy z. Orientace humanoida v souřadném systému je zakreslena na obrázku (Obrázek 6.3).

Obrázek 6.3: Orientace humanoida v souřadném systému Vezměme v úvahu ramenní kloub, který má možnost rotace kolem svislé osy y pouze ± 40° a kolem os x a z prakticky celý rozsah. Cíl prvního kroku bude rozpažení. V ramenním

17


kloubu k rotaci kolem osy x nedochází, kolem osy y také ne a jedinou změnu podstoupí úhel kolem osy z. Poslední dílčí kloub ramene tedy rozpaží ruku o 90° (Obrázek 6.4a).

a) rozpažení

b) předpažení

Obrázek 6.4: Nesprávné pořadí dílčích kloubů

Cílem druhého kroku bude předpažení z této polohy. Souřadné systémy dílčích kloubů ramene jsou zachovány, protože docházelo k rotaci až za nimi. K rotaci kolem osy x opět nedochází. Nyní je však na řadě rotace kolem osy y. V reálném případě by člověk dokázal z rozpažení předpažit, ale v tomto příkladě je hodnota rotace kolem osy y pouze 40° namísto 90° díky limitům (Obrázek 6.4b). Při tomto pořadí dílčích kloubů ruka nikdy nedosáhne předpažení, pokud je výchozí poloha rozpažení. Pro ramenní kloub je výhodnější, aby bylo pořadí rotací z, x a y. V takovémto případě by byly souřadné soustavy pro dílčí klouby os x a y již ovlivněny rotací kolem osy z. Jsou-li hodnoty rozpažení z=90°, x=0 a y=0, tak pro předpažení je nutné změnit rotaci kolem osy x namísto rotace kolem osy y. Výsledné hodnoty pro předpažení jsou tedy z=90°, x=90° a

y=0. Pro každý kloub je bohužel vhodné různé rozložení kloubů a vzhledem k tomu, že parametry humanoida mohou být jakékoliv, tak se tento problém nedá plně podchytit. Stále tedy zůstává otázka jaké pořadí Eulerových úhlů zvolit, aby docházelo k minimu problémů. Z předchozího příkladu je patrné, že největší problém zapříčinila rotace kolem osy

y a její dílčí kloub byl přesunut na poslední místo v pořadí. Na posledním místě v pořadí by měl být vždy dílčí kloub, který ovlivňuje rotaci kolem osy, která prochází následující kostí. Kosti však nejsou rovnoběžné s osami souřadné soustavy a tak toto pravidlo nelze dobře

18


ošetřit. Avšak maximum kostí je rovnoběžných s osou y, následně s osou x a minimum s osou z (Obrázek 6.5). Tím je určeno pořadí dílčích kloubů v tomto projektu. Pořadí složek Eulerových úhlů se tedy provádí v pořadí z, x, y.

osa x ..........modrá osa y ....... červená osa z ......... zelená Obrázek 6.5: Rovnoběžnost kostí s osami

Jiný pohled na pořadí dílčích kloubů se nabízí při samotném vypočítávání změny úhlů. Záleží totiž i na aktuální poloze efektoru, cíle a aktuálního kloubu. Zanedbáme-li orientaci cíle, tak existuje více možností k jeho dosažení. Například rotace kolem osy x a poté kolem osy y o 90° umístí efektor do stejné pozice jako rotace kolem osy z o 90°. Rozdíl je ve vykonané cestě, na které samozřejmě záleží. V první řadě by se měl měnit úhel dílčího kloubu, jehož změna úhlu bude nejmenší. Tento problém se vyskytuje pouze při zanedbání orientace a proto nebyl nijak hlouběji řešen. Jistou kompenzaci nabízí volba odporů, která zjemní pohyb a automaticky povede efektor přirozenějším způsobem. Na druhé může výpočet trvat o mnoho déle.

19


6.1.3 H-Anim Vývojová skupina H-Anim (Humanoid Animation Working Group) vytvořila stejnojmenný standard pro reprezentaci lidské postavy ve výpočetní technice. H-Anim je naimplementován v jazyce VRML (Virtual Reality Modeling Language), který slouží pro popis trojrozměrných scén a jejich animací. Humanoid je popsán pomocí struktury odpovídající kostře člověka. Přesná specifikace formátu H-Anim verze 1.1, který byl použit v tomto projektu, je k dispozici v [Han11]. Základním objektem je datová struktura Humanoid, která obsahuje informace o jméně humanoida, jeho pozici a orientaci ve scéně a jiné převážně geometrické vlastnosti. Také zahrnuje pole HumanoidRoot, které obsahuje první kloub, který je kořenem celé kloubové struktury. Klouby jsou uspořádány v hierarchické větvící se struktuře. Datová struktura kloubu se nazývá Joint. Jeho atributy obsahují název kloubu, kořeny podstromů a různé doplňující informace, jako jsou například limity nebo odpor svalů, které nejsou ve VRML standardně implementovány, ale mohou být užitečné pro uživatele. Pro vyobrazení těla humanoida slouží datová struktura Segment, která je navázána na kloub a zastupuje grafickou podobu určité části humanoida. Potomci segmentu jsou pouze grafické prvky. Místa vyhrazená pro koncové efektory jsou uvedena jako Site, určují koncová nekloubová místa na těle, jako jsou například konečky prstů nebo hlava. Je nutné připomenout, že tento projekt se neomezuje pouze na tato místa a umožňuje volbu efektoru i na klouby. Názvy kloubů, segmentů a jejich uspořádání je přesně definováno specifikací. Existuje množina prvků, která je definovaná jako povinná a tu musí každý humanoid obsahovat. Kompletní struktura je znázorněna na obrázku (Obrázek 6.6). Rozšíření struktury nad standard je dovoleno, ale uživatel se nemůže spoléhat na plnou podporu ze strany tohoto projektu. Velmi důležité je zmínit formáty a rozsahy polí datových struktur. Formáty dat totiž rozhodují o použitých reprezentacích a operacích v trojrozměrném prostoru. Limity jsou popsány dvěma poli: llimit a ulimit. V poli ulimit jsou maximální možné hodnoty Eulerových úhlů kloubu, zatímco v poli llimit jsou minimální. Již zde je patrná menší nesourodost dat. Rotace kloubů ve VRML je zadávána pomocí vektoru a úhlu narozdíl od limitů, které jsou popsány Eulerovými úhly. Limity jsou bohužel doplňkem a VRML jejich existenci nepředpokládalo. Popsat limity jinou formou než pomocí Eulerových úhlů je velmi obtížné. Problém převodu mezi těmito dvěma typy je řešen v kapitole 6.3.1. Dalším důležitým polem je stiffness, které vyjadřuje odpor svalů. Protože je toto pole obsaženo

20


kloubem, tak se spíše jedná o tuhost příslušných kloubů. Hodnoty tuhosti se pohybují od nuly do jedné a jsou vázány na složky Eulerových úhlů stejně jako limity.

Obrázek 6.6: Struktura H-Anim

21


6.2 Inverzní kinematika

6.2.1 Algoritmus CCD Jak již bylo napsáno v kapitole o iteračních metodách, technika CCD prochází klouby kinematického řetězce od efektoru k bázi a hledá takový úhel kloubu, který by minimalizoval chybu koncového efektoru. Projití všech kloubů kinematického řetězce se nazývá iterace, což lze popsat následujícím algoritmem:

1) Aktuálním kloubem se stane koncový efektor. 2) Aktuálním kloubem se stane následující kloub v kinematickém řetězci. 3) Aktuální kloub se natočí tak, aby se minimalizovala chyba koncového efektoru. 4) Pokud aktuální kloub není báze, skok na bod 2). Algoritmus 6.1: Jedna iterace CCD metody

Toto byla pouze jedna iterace, která zlepší polohu efektoru vůči svému cíli, ale ještě nezaručí požadovaný výsledek. Koncový efektor dosáhne cíle až po několika iteracích. Takže nejednodušší verze algoritmu CCD metody by mohla vypadat takto:

1) Aktuálním kloubem se stane koncový efektor. 2) Aktuálním kloubem se stane následující kloub v kinematickém řetězci. 3) Aktuální kloub se natočí tak, aby se minimalizovala chyba koncového efektoru. 4) Pokud aktuální kloub není báze, skok na bod 2). 5) Pokud je chyba koncového efektoru větší než práh přesnosti, skok na bod 1). Algoritmus 6.2: Základní algoritmus CCD metody

Z algoritmu je patrné, že se nikdy nemění úhel u koncového efektoru. Změna úhlu u efektoru totiž mění pouze orientaci jeho podstromu, ale nikdy nezmění jeho vlastní polohu. V bodě 3 je uvedeno, že se musí minimalizovat chyba efektoru. Zanedbá-li se orientace efektoru, tak se minimalizace chyby docílí rotací v aktuálním kloubu, pokud aktuálně zpracovávaný kloub, efektor a cíl leží na jedné přímce. Obrázek 6.7 znázorňuje jednu iteraci. Zanedbá-li se pozice efektoru a požaduje se pouze minimalizace chyby orientace, tak je nutné dosáhnout stejné orientace efektoru jako cíle. Postupy při minimalizaci chyby pozice a orientace jsou bohužel odlišné a řešením je najít jistý kompromis mezi nimi.

22


a) počáteční poloha

b) první krok

c) druhý krok

d) třetí krok

červený bod......... rotovaný kloub modrý bod ....................... efektor černý bod ................................cíl zelený bod...........................báze Obrázek 6.7: Iterace CCD metody

6.2.2 Více koncových efektorů Ve výpočtech inverzní kinematiky může figurovat i více koncových efektorů [Bae01]. Za pomocí jednoho efektoru lze ovládat pouze jedna část těla humanoida a pro popis složitějších scén je nutné zavést výpočty s více efektory. Ke každému efektoru je přidružen vlastní cíl i báze. Výpočty inverzní kinematiky jsou ekvivalentní jako v případě jednoho efektoru, pouze je nutné řešit spojení výpočtů nad všemi kinematickými řetězci. K dosažení požadovaného výsledku postačí střídat jednotlivé kinematické řetězce. Otázkou zůstává, v kterém stavu výpočtu. K dispozici jsou tři možnosti:

1) střídání po kloubech 2) střídání po iteracích 3) střídání po dosažení cíle Pokud se kinematické řetězce navzájem neovlivňují, tak nijak zvlášť nezáleží na zvolené variantě střídání. Předpokládejme však, že se výpočty nad jednotlivými kinematickými řetězci ovlivňují. Střídání po kloubech znamená, že se střídají výpočty v kinematických řetězcích ihned po výpočtu změny úhlů jednoho kloubu. Tento princip bohužel nelze použít, protože

23


každý kinematický řetězec obsahuje jiný počet kloubů a proto nejsou výpočty korektní. Kinematické řetězce se také velmi rychle střídají a efektory pomalu dosahují svých cílů. Střídání po dosažení cíle také neposkytuje nejlepší výsledky. Kinematické řetězce se střídají po dosažení cíle efektorem. První problém je v možném nedosažení cíle, pokud je například cíl příliš daleko. V tomto případě nemusí ke změně kinematického řetězce ani dojít. Řetězce se také střídají méně často a proto výsledná scéna nemusí vypadat věrohodně.

a) počáteční pozice

b) iterace prvního řetězce

c) iterace druhého řetězce

Obrázek 6.8: Střídání iterací Zlatou střední cestou je střídání po jednotlivých iteracích řetězců. Po každé iteraci inverzní kinematiky, což znamená projití všech kloubů kinematického řetězce, se přestoupí

24


na další kinematický řetězec (Obrázek 6.8). Výpočet probíhá relativně plynule a není příliš zdlouhavý. Tento princip byl použit v tomto projektu. Střídání kinematických řetězců sebou bohužel přináší jistou nepříjemnost. I když se stanoví požadavek, aby byl každý efektor v dostatečné vzdálenosti od svého cíle a měl možnost jeho dosažení, přesto nemusí dojít ke zdárnému výsledku. Mají-li kinematické řetězce jistou část kloubů společnou, tak se může stát, že výpočet osciluje (Obrázek 6.9). Každý z efektorů sice zvlášť může dosáhnout svého cíle, ale protože se navzájem ovlivňují, tak v jednom momentě svých cílů dosáhnout nemohou. Řešení tohoto problému je podrobněji popsáno v kapitole 8.4.2 či v [Bae01].

Obrázek 6.9: Oscilace kinematických řetězců

6.2.3 Hledání kinematického řetězce Kinematický řetězec je ve skutečnosti nejkratší možná cesta mezi efektorem a bází. Poloha efektoru vůči bázi je naprosto libovolná, což umožňuje všechny kombinace nad kloubovou strukturou. Pouze klouby kinematického řetězce mění pozici efektoru. Z tohoto tvrzení lze usoudit, že efektor do kinematického řetězce nepatří. Červené body na následujícím obrázku znázorňují klouby kinematického řetězce (Obrázek 6.10). Dalším důležitým algoritmem je tedy hledání kinematického řetězce. V principu se jedná o procházení po kloubové struktuře směrem ke kořeni, protože otec kloubu je vždy jeden. Algoritmus lze rozdělit od několika kategorií v závislosti na vzájemné poloze efektoru a báze.

25


Obrázek 6.10: Kinematický řetězec

1) Efektor je potomkem báze Toto je standardní varianta, jak je známa z algoritmu inverzní kinematiky (Obrázek 6.12a). Do pole kinematického řetězce se postupně ukládají předkové efektoru, dokud se nedosáhne báze. Příkladem může být ruka jako efektor a rameno je bází.

2) Báze je potomkem efektoru Tato situace je přesně opačná předchozí (Obrázek 6.12b). V tomto případě se procházejí předkové báze a ukládají se do pole odzadu. Až se dosáhne efektoru, tak se algoritmus ukončí. Použití lze nalézt při animaci sedu. Báze se nastaví do kotníku, efektor do kořene humanoida. Takto si humanoid může sednout, aniž by noha změnila svoji polohu.

3) Efektor a báze jsou v jiných podstromech Nejkomplikovanější stav nastává, pokud efektor a báze neleží na jedné větvi struktury (Obrázek 6.10, Obrázek 6.12c). Nejprve se bude muset nalézt společný předek báze a efektoru. Nejjednodušší způsob je najít dva oddělené pomocné řetězce pomocí předchozích způsobů. Jeden od efektoru ke kořeni a druhý od báze ke kořeni. Společný předek se hledá tak, že se souběžně procházejí oba řetězce od kořene a první společný předchůdce efektoru a báze je kloub, který je obsažen v obou řetězcích a je nejdále od kořene (Obrázek 6.11). Tímto způsobem se vynechají klouby, které by se procházeli dvakrát. Algoritmus by nepracoval korektně, kdyby byl použit jako společný předchůdce kořen. Poté, co je znám společný předchůdce, tak se vytvoří kinematický řetězec, do kterého se uloží postupně klouby od efektoru ke společnému předchůdci a následně klouby od společného řetězce k bázi.

26


Obrázek 6.11: Nalezení společného předchůdce

Je důležité zdůraznit jistý fakt, který v základním algoritmu CCD metody chybí (Algoritmus 6.2). Je jím vynechání společného předchůdce ze základního cyklu. Jak bylo uvedeno v kapitole 6.1.1, tak úhel mezi větvemi u jednoho kloubu nelze měnit, a proto je nesprávné zahrnovat ho do výpočtu. Úhly společného předchůdce báze a efektoru totiž ovlivňují celý podstrom, v kterém se nacházejí báze a efektor. Proto se musí společný předchůdce vynechat:

1) Aktuálním kloubem se stane koncový efektor. 2) Aktuálním kloubem se stane následující kloub v kinematickém řetězci. 3) Pokud je aktuální kloub společný předchůdce báze a efektoru, skok na bod 2). 4) Aktuální kloub se natočí tak, aby se minimalizovala chyba koncového efektoru. 5) Pokud aktuální kloub není báze, skok na bod 2). 6) Pokud je chyba koncového efektoru větší než práh přesnosti, skok na bod 1). Algoritmus 6.3: Vynechání společného předka efektoru a báze

Je nutné připomenout, že rotace kloubu se liší v závislosti na umístění kloubu v kinematickém řetězci. Předpokládejme, že se v bodě 4) algoritmu CCD metody (Algoritmus 6.2) hledá změna rotace kloubu a ta se pak aplikuje na dosavadní stav kloub. Prochází-li se kinematický řetězec směrem ke kořeni, tak se tato změna rotace aplikuje klasickým způsobem. To znamená, že se přičte k aktuální rotaci kloubu. Tak tomu je ale pouze v případě, že se procházejí klouby od efektoru směrem ke kořeni. Pokud se prochází klouby

27


kinematického řetězce od kořene k listům, tak je vztah ke kloubové struktuře opačný a je nutné změnu rotace odečíst. Na následujícím obrázku jsou vyobrazeny všechny druhy kinematických řetězců a použitá znaménka při aplikaci změny rotace. Znaménko plus znamená přičtení změny rotace ke stávající rotaci kloubu, mínus znamená odečtení změny rotace. V posledním podstromu nemá nejvýše zakreslený kloub kinematického řetězce přiřazené znaménko. Jedná se totiž o společného předchůdce báze a efektoru. Jak bylo uvedeno dříve, tak se u tohoto kloubu úhel nemění.

a) efektor je potomkem báze b) báze je potomkem efektoru

c) efektor a báze jsou v jiných podstromech

červený bod..................... efektor zelený bod...........................báze modrý bod ......... kloub k. řetězce Obrázek 6.12: Aplikace změny úhlu v kinematickém řetězci

6.3 Reprezentace rotace ve 3D Jednou z nejdůležitějších částí vývoje aplikace je reprezentace objektů a operací v trojrozměrném prostoru. Její výběr v první řadě závisí na vstupních datech, což v tomto případě znamená humanoid ve formátu H-Anim. Dalším aspektem jsou požadované výpočty, které se nad těmito daty provádějí. Je tu i možnost použití reprezentace, která není čistě v souladu se vstupními daty či operacemi nad nimi, pokud existuje dostatek převodních funkcí k jejich propojení s reprezentací.

28


Pozice v prostoru je většinou popsána v kartézském souřadném systému. Zastoupení orientace tak jednoznačné bohužel [Kav03]. Možné alternativy jsou Eulerovy úhly, rotace osa-úhel, kvaternion či transformační matice. Každá z těchto reprezentací má své výhody i nevýhody s přihlédnutím ke skládání či interpolaci.

1) Eulerovy úhly Eulerovy úhly definují orientaci jako otočení kolem hlavních os souřadné soustavy (Obrázek 6.13). Pořadí rotací záleží na zvolené konvenci a není nutné se omezovat pouze na klasické pořadí kolem osy x, y a nakonec kolem osy z. Existuje mnoho standardů jako NASA Standard Aeroplane (y, z, x) či NASA Standard Aerospace (z, y, z) [Bak]. V tomto projektu je ale použitá vlastní konvence z, x, y. Důvod zavedení je uveden v kapitole 6.1.2. Eulerovy úhly jsou použity k zadání limitů kloubů a odporů ve formátu H-Anim.

Obrázek 6.13: Eulerovy úhly

2) Osa – úhel Další možnou interpretací orientace v prostoru je rotace pouze kolem jedné avšak libovolné osy. Tato reprezentace je použita pro rotace v jazyce VRML. Úhel je zadán v radiánech a osa je popsána vektorem v prostoru.

Obrázek 6.14: Rotace osa - úhel

29


3) Kvaterniony Kvaterniony jsou čtyřdimenzionálním rozšířením komplexních čísel (a + bi + cj + dk), které mohou být aplikovány jako reprezentace rotace [Wik]. Jejich hlavní výhodou je bezproblémová interpolace dvou orientací, která se v předchozích případech implementuje poněkud složitěji. Jejich přímé využití v tomto projektu není zjevné, protože se používají pouze k popisu rotace osa - úhel.

4) Transformační matice Posledním možným řešením, které zde doposud nebylo zmíněno jsou transformační matice. Matice v sobě udržují kompletní stav souřadné soustavy, což znamená pozici i orientaci. Jejich výhodou je možnost jednoduchého použití mnoha transformačních operací a skládání.

V tomto projektu byly použity všechny vyjmenované možnosti a to v různém zastoupení. Pro operace nad prostorem byly použity transformační matice společně s Eulerovými úhly. Matice jsou použity pro skládání transformací a Eulerovy úhly popisují úhly kloubů. Zvolení Eulerových úhlů bylo více než nutné, protože ve spojení s tuhostí a limity kloubů by jiná volba nebyla ani možná. Rotace kolem osy a kvaterniony jsou použity při převodech mezi jazykem VRML a kloubovou strukturou.

6.3.1 Převody reprezentací rotace Spojení více reprezentací pro popis rotace v trojrozměrném prostoru vyžaduje v některých případech vzájemný převod. V tomto případě se jedná o převod orientací mezi jazykem VRML a kloubovou strukturou tohoto projektu. Konkrétně se převody týkají Eulerových úhlů, rotací osy - úhel a transformačních matic. 1) Eulerovy úhly à transformační matice: Tato konverze je jednoduchá, protože se jedná o klasickou maticovou rotaci. Transformační matice Tx, Ty a Tz vytvořené z Eulerových úhlů jsou znázorněny ve vztahu (3a), (3b) a (3c). Použití je potřebné při přepočítávání transformačních matic lokálních soustav kloubů.

30


0 1 0 cos α Tx (α ) =  0 sin α  0 0

0 − sin α cos α 0

0 0 0  1

(3a)

cos β  0 Ty (β ) =   sin β   0

0 − sin β 1 0 0 cos β 0 0

0 0 0  1

(3b)

cos γ  sin γ Tz (γ ) =   0   0

− sin γ cos γ 0 0

0 0 0  1

(3c)

0 0 1 0

2) Transformační matice à Eulerovy úhly: Předpokládejme transformační matici T, která byla vytvořena z Eulerových úhlů

α , β , γ (vztah 4). Získání Eulerových úhlů z transformační matice se zdá na první pohled jako lehký úkol, když je znám převod opačný. Obor hodnot funkcí arcsin a arctan je bohužel definován pouze na rozsahu (− π / 2, π / 2 ) , zatímco vstupní úhly se nacházejí v rozsahu

(− π , π ) . Abychom obdrželi správné verze úhlů, musíme přihlédnout ke znaménkům prvků matice. Podle znamének se Eulerovy úhly převedou do správných kvadrantů. Je nutné připomenout, že výsledná matice je závislá na konvenci skládání. Tento převod je použit například pro získání globální orientace z transformační matice efektoru.

T (α , β , γ ) = Tα ⋅ Tβ ⋅ Tγ = cos β cos γ  − sin α sin β cos γ + cos α sin γ =  cos α sin β cos γ + sin α sin γ  px 

− cos β sin γ sin α sin β sin γ + cos α cos γ − cos α sin β sin γ + sin α cos γ py  m  α = arctan − 2,3   m3,3  β = arcsin (− m1,3 )  m  γ = arctan − 1, 2   m1,1 

31

− sin β − sin α cos β cos α cos β pz

0 0 0  1

(4)


3) Eulerovy úhly à rotace osa - úhel: Humanoid zadaný pomocí jazyka VRML akceptuje pro každý kloub pouze rotaci kolem vektoru. Jak bylo zmíněno v předchozím textu, tak popis rotací je v tomto projektu implicitně prováděn pomocí Eulerových úhlů. Eulerovy úhly lze chápat jako složení tří rotací osa - úhel, kde osy jsou totožné s osami souřadné soustavy. Skládání rotací osa – úhel je provedeno pomocí násobení kvaternionů [Wik]. Tento převod je použit při zobrazovaní polohy kloubové struktury do VRML. 4) Rotace osa - úhel à Eulerovy úhly: Počítáme-li s tím, že obdržený humanoid v jazyce VRML nemá žádné počáteční rotace, tak tento převod nebudeme vůbec potřebovat. Bohužel tu existuje možnost, že si uživatel humanoida situuje do libovolné polohy editací vstupního VRML souboru. V tomto případě musíme počáteční rotaci převést na Eulerovy úhly a uložit do kloubové struktury. Nejednoduše se toho docílí složením dvou převodů a to rotace osa – úhel à transformační matice à Eulerovy úhly. 5) Rotace osa - úhel à transformační matice: Tato konverze sama o sobě nic zajímavého nepřináší, ale je potřebná jako mezikrok v předchozím převodu. Osa rotace lze popsat dvěma úhly, které lze přirovnat zeměpisné šířce a délce. Složení rotačních matic těchto úhlů natočí osu rotace tak, že je shodná s osou

x. Na aktuální transformační matici se použije matice rotace úhlu, který patří k rotaci osa – úhel. Poté se provedou zpětné transformace předchozích dvou úhlů a tím se získá transformační matice, která vyjadřuje rotaci osa – úhel. 6) Transformační matice à rotace osa - úhel: Toto je poslední možný převod a nebyl v projektu nikde použit. Pro úplnost je nutné uvést, že lze nahradit převodem transformační matice à Eulerovy úhly à rotace osa - úhel.

32

Implementace

7 Implementace Tato kapitola se zabývá již konkrétními problémy implementace. Je zde popsáno několik metod na výpočet změny úhlu kloubu, který je nejdůležitější částí CCD algoritmu. Nebyla opomenuta ani implementace atributů kloubu potřebných při animaci kloubové struktury humanoidů. Poslední sekce poukazuje na aktualizaci kloubové struktury a existenci počáteční transformační matici. Pro snadnou orientaci v matematických vzorcích je nutné nadefinovat zkratky pro použité veličiny. Označení proměnných není v souladu s označením jiných autorů.

k ......................................................... aktuální (rotovaný) kloub kp ........................................................pozice aktuálního kloubu ko ................................................... orientace aktuálního kloubu qx ......................................................... úhel kloubu kolem osy x qy ......................................................... úhel kloubu kolem osy y qz ......................................................... úhel kloubu kolem osy z q (qx,qy,qz)................................................. Eulerovy úhly kloubu ∆q (∆qx,∆qy,∆qz) .......................................... změna úhlů kloubu e .......................................................................koncový efektor ep .................................................... pozice koncového efektoru eo ................................................ orientace koncového efektoru c .............................................................................. cíl efektoru cp .............................................................................. pozice cíle co ..........................................................................orientace cíle Ti ........................................ transformační matice i-tého kloubu Tk .................................transformační matice aktuálního kloubu Tc ....................................................... transformační matice cíle Te ..............................transformační matice koncového efektoru Tp.................................................................... počáteční matice

33

Implementace

7.1 Výpočet změny úhlu Na jednoduchém algoritmu inverzní kinematiky (Algoritmus 6.2) si lze všimnout, že nejdůležitější část se týká výpočtu natočení úhlu, zatímco ostatní kroky mají za úkol traverzování po kloubové struktuře. Segmenty incidující s kloubem svírají jistý úhel. Po minimalizaci chyby efektoru budou svírat nový úhel, a jediným cílem třetího bodu algoritmu je najít změnu tohoto úhlu a aplikovat jej na stávající úhel. V případě, že zanedbáme orientaci při výpočtu, tak minimalizace chyby nastává, pokud jsou efektor, cíl a aktuální kloub v jedné přímce (Obrázek 7.1).

Obrázek 7.1: Změna úhlu ve 2D

V dvourozměrném prostoru je výpočet změny úhlu triviální. Je to úhel, který mezi sebou svírají dva vektory. Jeden vektor směřuje od aktuálního kloubu k efektoru (ke) a druhý k cíli (kc). Cosinus změny úhlu je roven skalárnímu součinu těchto vektorů vyděleného součinem jejich délek.

 ke ⋅ kc   ∆q = arccos  ke ⋅ kc  

(5)

V poslední řadě zbývá vyřešit, zda změnu úhlu přičíst od stávajícího úhlu q kloubu nebo odečíst. To lze zjistit podle orientace vektorů. Stačí zjistit determinant matice složené z vektorů a jeho znaménko určí znaménko operace při výpočtu nového úhlu q’.

D=

kex kcx

key = kex ⋅ kc y − key ⋅ kcx kc y

34

(6)

Implementace

q′ = q + sign(D ) ⋅ ∆q Pro dvourozměrný případ lze tedy provozovat inverzní kinematiku celkem snadno. Mnohem složitěji se zjišťuje změna rotace v třídimenzionálním prostoru. Jak bylo uvedeno výše, rotace kloubu je definována třemi Eulerovými úhly. Obtíž je v tom, že je nutné nalézt tyto tři úhly namísto jednoho. Každý celý kloub si udržuje transformační matici o své poloze v globálním systému. Díky této matici a úhlech celého kloubu lze získat transformační matice každého dílčího kloubu. Matice dílčích kloubů Tki se vypočítají z matice celého kloubu Tk tímto způsobem:

Tk1 = Tk Tk 2 = Tk1 ⋅ rotacez (q z )

(7)

Tk 3 = Tk 2 ⋅ rotacex (q x ) . Funkce rotace odpovídají rotacím kolem souřadných os ze vztahů (3) s indexem, který vyjadřuje osu rotace. Připomeňme, že konvence rotací je z, x, y. Ze vztahů je patrné, že první dílčí kloub má zcela stejnou polohu jako by měl celý kloub bez rozložení. Ostatní dílčí klouby mají pouze shodnou pozici, ale liší se v orientaci. Pro úplnost můžeme dodat, že transformační matice následujícího kloubu Tk+1 lze získat takto:

Tk +1 = Tk 3 ⋅ rotace y (q y )⋅ posun( x, y , z ) ,

(8)

kde posun je funkce posunutí v souřadném systému o souřadnice (x, y, z), což jsou parametry délky segmentu mezi klouby k a k+1.

7.1.1 Analytický výpočet Historicky první vlastní algoritmus pro výpočet změny úhlu byl pojat čistě analyticky. Aplikuje se na každý dílčí kloub a vždy získá změnu úhlu pouze jedné složky Eulerových úhlů celého kloubu. V době vývoje tohoto algoritmu se projekt zabýval výhradně minimalizací pozice efektoru, a proto se problém zlepšení orientace vůbec neřeší. Princip lze popsat následovně. Předpokládejme, že se nacházíme v souřadné soustavě dílčího kloubu, který umožňuje otáčení pouze kolem své osy x, a hledáme změnu úhlu pro zlepšení pozice koncového

35

Implementace

efektoru (Obrázek 7.2). Pozice aktuálního dílčího kloubu se nachází v počátku své souřadné soustavy. Hledaný úhel ale nesvírají vektory ke a kc, jak by se mohlo zdát. Platilo by to pouze v případě, že by aktuální kloub, cíl i koncový efektor ležely ve stejné rovině yz. Hledaná změna kloubu lze nalézt na rovině yz, která prochází skrze aktuální kloub, pokud do ní promítneme cíl a efektor. Cíl a efektor tedy protínají dvě přímky, které jsou kolmé na tuto rovinu. Průsečíky přímek a roviny vytvoří hledané pomocné body e’ a c’, které s aktuálním kloubem svírají hledanou změnu úhlu.

Obrázek 7.2: Analytický výpočet

Tento algoritmus se provede i pro zbylé dva dílčí klouby v určeném pořadí a kompletní změny Eulerových úhlů aktuálního kloubu jsou získány. Tento způsob výpočtů skrývá několik nevýhod. Při konstruování přímek, výpočtech průsečíků a úhlů vektorů vznikalo za jistých situací mnoho chybných výpočtů. Tyto chyby musely být ošetřovány, což stálo drahocenný výpočetní čas, a tak bylo od analytického způsobu opuštěno.

7.1.2 Maticový výpočet Následující dva algoritmy využívali matematiku maticového počtu, který je osvědčený a pracuje téměř bezproblémově. Už se zde objevuje i algoritmus pro minimalizaci chyby orientace. Všem výpočtům dostačovaly maticové operace násobení, posunutí, rotace a inverze. Hlavní myšlenka tkví v transformacích souřadné soustavy.

36

Implementace

1) Minimalizace chyby pozice: Tento algoritmus pracuje ve své podstatě na stejném principu jako jeho analytická verze. Také se provádí na dílčích kloubech a získává složky Eulerových kloubů postupně. Cíli a efektoru je přiřazena transformační matice s orientací aktuálního kloubu (Obrázek 7.3a). Na tyto transformační matice se provede zpětná transformace pomocí souřadné soustavy aktuálního kloubu. To znamená, že souřadný systém, ve kterém jsme se pohybovali v analytické verzi, jsme transformovali do počátku globální soustavy. Aktuální kloub je nyní na souřadnicích 0,0,0 s orientací 0,0,0 (Obrázek 7.3b). Cíl a efektor jsou stále ve stejné topologii s aktuálním kloubem jako byly před transformací. Ve skutečnosti došlo pouze k přemístění pracoviště.

a) přiřazení transformačních matic

b) transformace kloubu do počátku

Obrázek 7.3: Transformace lokální souřadné soustavy

Tento jednoduchý úkon však velmi zjednoduší následující výpočty. Nyní se totiž projekce cíle a efektoru provádí do roviny, kterou svírají osy y a z (za předpokladu, že hledáme složku x). Tato projekce je pouze nastavení x-ové složky na nulu. Pak už zbývá jen vypočítat úhel mezi projekcemi cíle a efektoru u aktuálního kloubu jako ve 2D. U této metody k žádným zbytečným chybám nedochází díky maticovému počtu. Jediné, co je potřeba ošetřit, je opět samotný výpočet úhlu. V některých případech totiž může být velikost vektorů nulová, což znamená, že projekce cíle nebo efektoru má shodnou pozici s aktuálním kloubem. V tomto případě nelze určit úhel mezi vektory a změna úhlu se prohlásí za nulovou.

37

Implementace

2) Minimalizace chyby orientace: Dosud neřešeným

problémem byla minimalizace chyby orientace. Výsledkem

následujícího algoritmu jsou také změny úhlů, ale v tomto případě se získají všechny složky celého kloubu najednou. Hlavní idea spočívá v nalezení transformační matice, která obsahuje pouze změnu úhlů aktuálního kloubu. Po aplikování této matice na transformační matici aktuálního kloubu (včetně jeho rotace) se musí orientace efektoru změnit na orientaci cíle. Následující vztahy přiblíží systém výpočtu požadované matice.

Tk ⋅ Tq ⋅ Tx = Te

(9a)

Tk ⋅ Tq+∆q ⋅ Tx = Toc

(9b)

Vztah (9a) tvrdí, že transformační matice aktuálního kloubu Tk vynásobená transformační matici jeho úhlů Tq vynásobená maticí Tx, která určuje transformaci mezi aktuálním kloubem a efektorem, je rovna matici efektoru. Druhý vztah (9b) říká, že pokud na aktuální kloub aplikujeme transformační matici nových hodnot úhlů Tq+Δq a opět aplikujeme matici Tx, tak získáme matici Toc, která obsahuje orientaci cíle (Obrázek 7.4) s odlišnou pozicí.

a) počáteční pozice (vztah 9a)

b) výsledná pozice (vztah 9b)

Obrázek 7.4: Minimalizace chyby orientace

Nejprve je potřeba vyjádřit matici Tx ze vztahu (9a) pomocí inverze a poté získáme i matici Tq+Δq ze vztahu (9b):

Tx = (Tk ⋅ Tq ) ⋅ Te −1

38

(10a)

Implementace

Tq +∆q = Tk−1 ⋅ Toc ⋅ Tx−1

(10b)

V kapitole 6.3.1 bylo uvedeno extrahování úhlů z matice. To se v tomto případě použije na matici Tq+Δq a tím získáme nové Eulerovy úhly. Potřebujeme-li pouze změnu, tak stačí od nich odečíst předchozí hodnoty úhlů.

3) Sloučení minimalizace chyby pozice i orientace Algoritmy na optimalizaci pozice i orientace pracovali podle požadavků, ale bohužel pouze v případě, že byly aplikovány zvlášť. Sloučení těchto algoritmů se stalo další komplikací. První naivní metodou je střídání minimalizace chyby pozice a orientace. Tato metoda byla ale ihned zavrhnuta. Existuje totiž situace, kdy výpočet zlepšení pozice vypočte přesně opačné úhly než zlepšení orientace. V takovémto případě efektor střídá svoji pozici a v mála případech se jeho situace zlepší. Druhá idea spočívala také ve střídání, ale odlišných kloubů. V případě, že optimalizujeme pozici pomocí kloubu k v kinematickém řetězci, tak následuje optimalizace orientace pomocí kloubu k-1. Tento systém už dosahoval lepších výsledků, ale přesto jen v několika případech. Neobstály ani pokusy optimalizace orientace pomocí jiných kloubů než předchozích. Poslední šancí byla interpolace úhlů získaných pomocí obou algoritmů. Celková změna úhlů se získala z dílčích výpočtů:

∆q = w p ⋅ ∆q p + wo ⋅ ∆qo

(11)

Nejprve byly váhy pozice wp a orientace wo nastaveny na 0.5, což bohužel nepracovalo podle předpokladů. Jiná varianta bylo vypočítávání vah ze vzdálenosti cíle a efektoru. Ani tento způsob nepřinášel kýžené výsledky a tak nezbývalo nic jiného než zanechat vlastních pokusů na implementaci minimalizace chyby.

7.1.3 Vektorový výpočet Algoritmus pro minimalizaci celkové chyby koncového efektoru, který byl použit ve finální verzi tohoto projektu, byl převzat z [Wel93]. Na rozdíl od předchozích výpočtů vypočítává tento algoritmus změnu úhlu pro minimalizaci pozice i orientace najednou, což vlastní

39

Implementace

výzkum nedokázal. Výsledkem je pouze změna úhlu a proto byl použit pro získání jednotlivých složek Eulerových úhlů.

Obrázek 7.5: Příklad vektorového výpočtu

Obrázek 7.5 popisuje situaci pro výpočet rotace. Poloha aktuální pozice efektoru je vyjádřena vektorem Ve od rotovaného kloubu k efektoru. Pokud ∆q je hledaná změna úhlu, tak výsledný vektor od kloubu k efektoru označíme V’e(∆q). Hlavním požadavkem je rovnoběžnost vektorů Vc a V’e(∆q). Tohoto však ve většině případů nelze dosáhnout a proto se spokojíme s maximalizací tohoto vztahu:

g1 (∆q ) = Vc ⋅ Ve′(∆q )

(12a)

Minimální chyba orientace se ekvivalentně dosáhne maximalizací vztahu

3

g 2 (∆q ) = ∑ uic ⋅ uie′ (∆q )

(12b)

i −1

Kombinací předchozích funkcí získáme celkovou funkci, která je jistou alternativou ke vztahu (11):

g (∆q ) = wp ⋅ g1 (∆q ) + wo ⋅ g 2 (∆q )

(12c)

Váhy wp a wo vyjadřují prioritu pozice či orientace a nabývají hodnot v závislosti na aktuální situaci. Váha pozice se narozdíl od váhy orientace mění a je hlavním určujícím prvkem výpočtu. Konstanta α umožňuje mírnou volnost ve výpočtu. Její hodnota byla získána z testovacích úloh tohoto projektu a pro tuto hodnotu byly výpočty prováděny

40

Implementace

v nejmenším počtu iterací. Proměnná ρ je poměr velikostí vektorů v rozsahu od nuly do jedné.

wo = 1

(13a)

wp = α (1 + ρ )

(13b)

α = 4.25

(13c)

ρ=

min (Ve , Vc )

max (Ve , Vc )

(13d)

Za pomocí několika algebraických manipulací lze funkce (12c) zredukovat na vztah

g (∆q ) = k1 (1 − cos ∆q ) + k2 cos ∆q + k3 sin ∆q

(14)

kde se konstanty k1, k2 a k3 získají takto:

3

k1 = wp (Ve ⋅ Vosa )(Vc ⋅ Vosa ) + wo ∑ (uie ⋅ Vosa )(uic ⋅ Vosa )

(15a)

i =1 3

k2 = wp (Ve ⋅ Vc ) + wo ∑ (uie ⋅ uic )

(15b)

3   k3 = Vosa ⋅  wp (Ve × Vc ) + wo ∑ (uie × uic ) i =1  

(15c)

i =1

Ve výpočtu koeficientů se vyskytuje dosud neuvedený jednotkový vektor Vosa, který reprezentuje osu rotace aktuálního kloubu. Extrémní hodnoty funkce (14) najdeme pokud bude její první derivace rovna nule. A z tohoto vztahu lze získat kandidáta na požadovanou změnu úhlu.

(k1 − k2 )sin ∆q + k3 cos ∆q = 0

(16a)

 k  ∆q = arctan 3   k2 − k1 

(16b)

Díky goniometrické funkci arctan se výsledná změna úhlu pohybuje pouze v rozsahu

(− π / 2, π / 2) . Další možné hodnoty nabývají hodnot ∆q±π. Hodnota ∆q je správná pokud je

41

Implementace

druhá derivace funkce (15) menší než nula. V opačném případě je to jedna z hodnot ∆q±π a to ta, která spadá do rozsahu (− π , π ) . Tento algoritmus pracuje podle všech předpokladů a proto byl použit v tomto projektu. V případě minimalizace chyby pouze pozice nebo pouze orientace jsou výsledné změny úhlu rovny výsledkům z předchozích algoritmů. Avšak síla této varianty je ve spojení optimalizace pozice a orientace v jednom výpočtu, čehož za pomocí předchozích alternativ nebylo dosaženo.

7.2 Limity a odpory Jak již bylo uvedeno v kapitole 5.3, pro popis humanoidů jsou použity dva atributy kloubů. Implementace odporů a limitů [Wel93] je triviální, ale přesto jejich nasazení v praxi dává relativně dobré výsledky. Jejich reprezentaci určil formát H-Anim a z ní vyplynula i celá implementace kloubové struktury.

7.2.1 Limity kloubů Každý kloub struktury obsahuje dvě pole po třech hodnotách, které určují maximální a minimální možné limity kloubu. Jejich hodnoty jsou maximální (xmax,ymax,zmax) a minimální (xmin,ymin,zmin) povolené hodnoty Eulerových úhlů kloubu. Požadujeme-li naprostou volnost pro klouby, tak nastavíme minimální hodnoty na (-π,-π,-π) a maximální na (π,π,π).

Obrázek 7.6: Limity kloubu

42

Implementace

Příklad použití je vyobrazen na předchozím obrázku při zanedbání rotace kolem osy x (Obrázek 7.6). Limity se aplikují až po výpočtu změny úhlu kloubu na každou složku výsledných Eulerových úhlů q’ (vztah 17a a 17b). Proměnná qmax a qmin určuje maximální a minimální povolenou hodnotu pro aktuální složku Eulerových úhlů.

if

(q′ > qmax )

q′ = qmax

(17a)

if

(q′ < qmin )

q′ = qmin

(17b)

7.2.2 Odpor svalů Formát H-Anim zavedl u kloubů pole tří hodnot, které reprezentuje odpor. Každá hodnota koresponduje s jednou složkou Eulerových úhlů a je v rozsahu 0 až 1. Pokud je hodnota rovna nule, tak je odpor maximální a kloub je v tomto směru nehybný. V případě jedné je odpor plně pohyblivý. Je-li například u kloubu zadán odpor s hodnotami (0, 0.5, 1), tak to znamená že v lokální souřadné soustavě tohoto úhlu bude nemožné měnit úhel kolem osy x, kloub se může libovolně otáčet kolem osy z a na ose y bude každý předpokládaný úhel dvakrát zmenšen. Z tohoto popisu vyplívá, že změna úhlu kloubu bude vynásobena příslušnou hodnotou odporu. Výsledná hodnota nového úhlu se vypočte takto:

q′ = q + o ⋅ ∆q

(18)

kde proměnná o vyjadřuje odpor kloubu v dané složce Eulerových úhlů. A tak dostáváme konečný výpočet a aplikaci změny úhlu i s omezujícími podmínkami.

q′ = q + o ⋅ ∆q

(19a)

if

(q′ > qmax )

q′ = qmax

(19b)

if

(q′ < qmin )

q′ = qmin

(19c)

Také je důležité vyvrátit možné milné chápání odporů. Má-li kloubová struktura všechny odpory nastaveny na stejnou hodnotu, tak se všechny klouby bohužel nehýbou stejně, jak by se zdálo. Je to zapříčiněno pořadím kloubů v inverzní kinematice. Úhly kloubů, které jsou blížeji k efektoru, se totiž mění mnohem víc. Aby se docílilo požadovaného efektu, tak by musely být odpory měněny dynamicky během výpočtu inverzní kinematiky v závislosti na

43

Implementace

statickém odporu a vzdálenosti od koncového efektoru. Tento problém ale není tak závažný, aby musel být řešen tímto způsobem.

7.3 Aktualizace struktury Po každém výpočtu změny úhlů je nutné aktualizovat informace kloubové struktury. Jedná se hlavně o polohu kloubů včetně efektorů. Změní-li se totiž úhly u jistého kloubu, tak se změní poloha několika jiných kloubů. Kvůli tomuto faktu je nutné celou kloubovou strukturu přepočítávat po každé změně libovolného kloubu. Kloubová struktura a její hierarchie se přímo nabízí k rekurzivnímu aktualizování. Aktualizování se provádí od kořene k listům a to systémem procházení do hloubky. Obnovují se informace pozice a transformační matice kloubu. Pozice kloubu lze snadno zjistit ze své vlastní transformační matice, což znamená, že postačí obnovovat pouze matice kloubů. K tomu účelu je nutné znát informace, které se získávají od otce, který je už aktualizovaný.

Tk = Totec ⋅ rotace(qotec ) ⋅ posun(segmentotec → k )

(20)

Vztah (20) vyjadřuje výpočet transformační matice Tk kloubu k. Na matici otce kloubu

Totec se aplikuje rotace Eulerových úhlů otce qotec podle určeného pořadí a poté se posune souřadná soustava o segment, který je mezi otcem a aktuálním kloubem. Tento vztah se rekurzivně použije na všechny syny aktuálního kloubu a tím se aktualizuje celá kloubová struktura. V předchozím textu bylo uvedeno, že je nutné přepočítávat celou kloubovou strukturu. Ve skutečnosti tomu tak nemusí být vždy. Přepočítávat se musí jen ty klouby, které se pohybují. Podle obrázku (Obrázek 6.12) lze rozlišit dvě situace. Mění-li se kloub se záporným znaménkem, tak se mění i poloha kořene a tudíž je logické, že se změní i poloha převážné většiny všech kloubů. Ale v případě, že se vypočítává změna úhlu u kloubu s kladným znaménkem, tak se mění poloha pouze jeho podstromu. Za těchto okolnostech postačí aktualizovat pouze podstrom, jehož kořenem je aktuální kloub, což výrazně urychlí výpočet.

44

Implementace

7.3.1 Počáteční transformace Otázkou zůstává, jak se vypočítá transformační matice kořene Tkoren, který otce nemá. Namísto transformační matice otce Totec vstupuje do vztahu (20) počáteční matice Tp, což je matice počátku souřadné soustavy. V základním postavení humanoida je počáteční matice jednotkou maticí, což situuje počátek souřadné soustavy humanoida do globální pozice 0,0,0 s orientací 0,0,0. V praxi to povětšinou bývá bod mezi chodidly humanoida (Obrázek 7.7).

Obrázek 7.7: Počáteční transformace

Tato matice se během výpočtu mění a určuje pozici a natočení celého humanoida ve scéně. Díky tomu je zbytečné, aby se následně aplikovaly úhly kořene. Není to sice nutné, ale přesto jsou úhly u kořene zanedbávány. V situaci, kdy by mělo dojít ke změně úhlu u kořene, což znamená natočení celého humanoida, tak se změna neaplikuje na úhly, ale na počáteční transformaci. Díky tomuto faktu je vynechána ze vztahu (20) rotace úhlů. Poslední záležitostí je posunutí segmentu. To ve své podstatě zůstává zachováno a dochází k posunu o vzdálenost mezi počáteční maticí a kořenem humanoida. Kompletní výpočet transformační matice kořene je tedy určen vztahem

Tkoren = Tp ⋅ posun( pocatek → koren )

(21)

V předchozím odstavci bylo zmíněno, že se počáteční matice mění během výpočtu inverzní kinematiky. Dochází k tomu při jakékoliv změně polohy kořene. Poloha kořene se mění i v některých případech, kdy není členem kinematického řetězce. Obrázek 6.12

45

Implementace

naznačuje, kdy dochází ke změně polohy kořene. Úhly kloubů, u kterých je znaménko mínus, ovlivňují při výpočtu inverzní kinematiky i pozici kořene, zatímco klouby se znaménkem plus nikoliv. Jak již bylo uvedeno, polohu kořene ve skutečnosti určuje počáteční transformace. Při výpočtech je od báze požadováno, aby neměnila svou pozici v globální souřadné soustavě. Pokud se tedy mění úhel kloubu, který je předkem báze, tak se natočí celá struktura nad bází a pozice podstromu báze zůstane zachována (Obrázek 7.8).

modrý bod ....................... efektor zelený bod...........................báze červený bod......... rotovaný kloub Obrázek 7.8: Posunutí kořene

Počáteční transformace se musí tedy změnit tak, aby po aktualizování struktury byl aktuální kloub situován stále na svém místě a jeho podstrom měl stejnou orientaci jako před změnou úhlu. Tímto se docílí, že ani báze nezmění svou polohu, protože se nachází v podstromu aktuálního kloubu. Pomocí maticových operací lze tuto situaci vyřešit. Změní-li se úhly aktuálního kloubu, tak se změní i pozice jeho podstromu. A proto se musí nalézt nová počáteční transformace, která tuto událost anuluje. Na transformační matici aktuálního kloubu Tk (včetně rotace kloubu) je aplikována matice rotace změny úhlů T∆q, která musí být vykompenzována novou počáteční maticí T’p. Ve vztahu (22a) je matice aktuálního kloubu rozložena na počáteční matici Tp a transformační matici Tx, která vyjadřuje transformaci od počáteční matice k aktuálnímu kloubu.

46

Implementace

Tk = Tp ⋅ Tx

(22a)

Tp ⋅ Tx = Tp′ ⋅ Tx ⋅ T∆q

(22b)

Tp′ = Tp ⋅ Tx ⋅ (Tx ⋅ T∆q )

−1

(22c)

Vztah (22b) formuluje základní rovnost matic, ze které se vyjádří nová počáteční transformace T’p (vztah 22c). Vztah mezi maticemi naznačuje následující nákres (Obrázek 7.9). Ve vztazích (22) je sice obecně uvedena změna všech Eulerových úhlů, ale ve skutečnosti se musí počáteční matice přepočítávat po každé změně složky, což znamená pro každý dílčí uzel.

Obrázek 7.9: Změna počáteční transformace

47

Experimentální program

8 Experimentální program Hlavním cílem tohoto projektu je vznik aplikace, která by využívala algoritmů inverzní kinematiky. Tato sekce popisuje důležité datové typy, algoritmy a komplikace programové implementace. Aplikace je rozdělena na dvě části. Hlavní částí je knihovna, která se stará o výpočty inverzní kinematiky a druhá část je ukázková aplikace, která tuto knihovnu využívá. Humanoid je zadán pomocí jazyka VRML. Pro zobrazení VRML scén byl použit prohlížeč Cortona VRML Client od ParallelGraphics. Tento prohlížeč totiž obsahuje rozhraní EAI (External Authoring Interface), přes které lze komunikovat se zobrazenou scénou z aplikace vytvořené v jazyce Java. V aplikaci se vytvoří okno prohlížeče a pomocí EAI lze číst parametry humanoida a ovládat ho. Volba programovacího jazyka tedy padla na Javu a to na verzi kompatibilní s Microsoft Javou, což znamená verzi 1.1. Hlavní třídou vlastní aplikace je třída s názvem ikDemo. Tato třída slouží jako demoverze a ukazuje všechny možnosti použití knihovny, která pracuje s inverzní kinematikou. Jádrem inverzní kinematiky je knihovna ikAnimation, která zajišťuje animaci pomocí inverzní kinematiky. ikAnimation přímo využívá třídu ikIteration, která je implementací iterace CCD metody. Zbylé třídy jsou podpůrné knihovny, které jsou využívány výše zmíněnými třídami. Jedná se převážně o reprezentaci datových typů jako jsou matice, vektor, bod atd.

ikDemo Ostatní třídy

ikAnimation ikIteration

Obrázek 8.1: Hierarchie tříd

8.1 Kloubová struktura Kloubová struktura je základním pilířem celého projektu, a proto musí být její reprezentace navržena efektivně. Kloubová struktura formátu H-Anim nelze přímo použít, a tak je nutné založit vlastní kloubovou strukturu, která bude obsahovat všechny potřebné vlastnosti k aplikování inverzní kinematiky. Protože je role segmentu v inverzní kinematice

48


pouze posunutí souřadné soustavy, tak jediné potřebné elementy kloubové struktury jsou klouby a nekloubová místa pro koncové efektory. Oba elementy obsahují mnoho společných vlastností, a tak byl vytvořen datový typ ikElement, po kterém dědí shodné vlastnosti. Ekvivalent báze ve vlastní kloubové struktuře neexistuje a její funkci zastupuje obyčejný kloub.

8.1.1 ikElement public class ikElement { String name; ikPoint position; ikMatrix m; ikJoint father; ikVector translation; } Každý element formátu H-Anim obsahuje jméno, které je přesně definováno (Obrázek 6.6). Toto jméno je obsaženo i v ikElement v proměnné name. Pozice v globálním souřadném systému je uložena v position. Lokální souřadná soustava elementu je popsána maticí m, z níž lze vyextrahovat pozice a orientace v globálním systému. Proměnná father slouží jako ukazatel na otce v kloubové struktuře. Vždy ukazuje na kloub, a proto není typu ikElement. Jak již napsáno, segment je nahrazen pouhým posunutím v souřadném systému. Proměnná translation vyjadřuje segment mezi otcem a aktuálním elementem. Datový typ ikElement sice obsahuje více proměnných, ale v tomto místě textu by byl jejich výklad matoucí, a proto budou popsány později.

8.1.2 ikJoint Tento typ je hlavním datovým prvkem a reprezentuje kloub struktury. Rozšiřuje ikElement o proměnné, které jsou nutné k popisu inverzní kinematiky či spojení s humanoidem ve VRML scéně.

public class ikJoint extends ikElement { ikVector angles; ikVector start_angles; ikVector ulimit;

49


ikVector ikVector ikJoint[] ikSite[] Node

llimit; stiffness; children; sites; nodeVRML;

} Hlavní funkcí kloubu je rotace. Její reprezentace je ve formátu Eulerových úhlů a jejich hodnoty jsou uloženy v proměnné angles. V případě potřeby obnovení počáteční polohy humanoida jsou prvotní úhly uloženy do start_angles. Limity, tedy maximální a minimální hodnoty složek Eulerových úhlů, jsou obsaženy proměnnými ulimit a llimit. Vektor stiffness reprezentuje odpor svalů neboli tuhost kloubů. Téměř každý kloub má minimálně jednoho následníka, na které je nutné odkazovat. Pole children odkazuje na následující klouby a pole sites na nekloubové prvky kloubové struktury, tedy případné koncové efektory, které jsou napojeny přímo na aktuální kloub. Spojení mezi humanoidem ve VRML scéně a vlastní kloubovou strukturou je zajištěno ukazatelem na ekvivalentní kloub ve scéně proměnnou nodeVRML.

8.1.3 ikSite Formát H-Anim definoval pro koncové efektory prvek Site, kterému odpovídá ve vlastní struktuře prvek ikSite. Jeho primární funkce je použití jako koncového efektoru. Dědí všechny vlastnosti základního článku ikElement, ale nerozšiřuje jej o nové. ikSite je tedy ekvivalentní s ikElement, a proto by nemusel být implementován. Tento fakt bohužel nebyl při implementaci zřejmý a tak byl prvek ponechán kvůli zachování názvosloví či pozdějšího rozšíření. ikSite je listem kloubové struktury a proto neobsahuje žádné ukazatele na potomky.

8.2 Načtení humanoida z VRML scény Aby bylo možné převést reprezentaci humanoida z formátu H-Anim do vlastní kloubové struktury, je nutné vytvořit v aplikaci okno s VRML scénou. Za pomocí příkazů EAI se nejprve vytvoří okno prohlížeče, které se připojí do aplikace jako komponenta [Ste03]. Prohlížeč se automaticky zobrazí s prvotní scénou. Iniciační scénou by již mohl být humanoid ve formátu H-Anim, ale protože aplikace podporuje změnu humanoida během chodu, tak je iniciační

50


scénou pouze prázdný prostor s ukazatelem na hlavní VRML uzel ikProjectRootNode, na který se budou připojovat další prvky scény. Iniciace VRML prohlížeče není bohužel stoprocentní. Může se stát, že se nepodaří prohlížeč v aplikaci vytvořit či vykreslit. Kvůli těmto nepříjemnostem musí konstruktor prohlížeče následovat několik příkazů, které zajistí jeho úspěšné načtení. Tyto příkazy se musí provádět nezávisle na hlavním chodu programu a proto je nutné spouštět je pomocí vláken. První pomocný příkaz je změna velikosti okna prohlížeče. Tímto je docíleno k okamžitému překreslení scény a tím i nové iniciaci. Prohlížeč se totiž překresluje až v případě čekání na událost ze strany uživatele, což znamená po ukončení základní funkce main. Změna velikosti okna tento fakt ignoruje a překreslí okno ihned. Tím je prohlížeč připraven ke komunikaci s aplikací. Protože nelze s prohlížečem pracovat ihned po iniciačním příkazu, tak je nutné zjistit, kdy je připraven. K tomu slouží jednoduchý cyklus, který po prohlížeči žádá odkaz na hlavní uzel ikProjectRootNode. Cyklus se ukončí v případě vrácení korektního odkazu nebo po určené době s chybovým hlášením. V tomto okamžiku je prohlížeč připraven k použití. Následně se přidává do prázdné scény humanoid, okolní prostředí a jiné podpůrné prostředky. Protože prohlížeč nevrací žádnou odezvu, zda je přidávaný objekt napojen korektně, je nutné ošetřit i toto. Opět postačí čekat v cyklu na odkaz libovolného uzlu, o jehož existenci jsme si v přidávaném objektu jistí.

8.2.1 Převod z H-Anim V případě, že je VRML prohlížeč inicializován a humanoid načten lze získat vlastní kloubovou strukturu. Nejprve se obdrží od prohlížeče odkaz na kořen humanoida HumanoidRoot. Struktura se hierarchicky prochází systémem do hloubky a během traverzování se vytváří vlastní kloubová struktura, která se naplňuje potřebnými daty. Většina dat se čistě zkopíruje (odpory a limity) do příslušných proměnných, ale některá data se musí převést do jiného formátu. V první řadě se to týká geometrie struktury. Pozice kloubu vzhledem k počátku humanoida obsahuje proměnná center. Vlastní kloubová struktura ale používá proměnnou translation, která vyjadřuje posunutí od pozice otce. Ekvivalentem center je proměnná position, která je ale používána pouze dodatečně pro zjištění globální pozice. Dalším nutným převodem je získání počátečních úhlů kloubů. Pomocí převodu č.4 z kapitoly 6.3.1 se získají Eulerovy úhly z rotace osa - úhel, kterou používá jazyk VRML.

51


Aplikace umožňuje obnovení humanoida do počáteční polohy. Vzhledem k tomu, že se mění i humanoid v scéně, tak nejsou počáteční hodnoty úhlů nikde udržovány. Počáteční úhly se tedy poprvé ukládají do proměnné start_angles a při obnovení se použijí tyto narozdíl od úhlů humanoida ve scéně. Po načtení nezbytných proměnných kloubů, což může být pouze posunutí od otce a úhly, se provede aktualizace struktury, aby se dopočítaly globální pozice a transformační matice kloubů. Aktualizace struktury byla popsána v kapitole 7.3.

8.3 CCD Třída ikIteration zajišťuje algoritmus CCD inverzní kinematiky. Lze na ni nahlížet jako na reprezentaci kinematického řetězce, na kterém se provádí jednotlivé iterace.

public ikIteration( ikJoint root, ikElement effector, ikJoint base, ikDestination destination, ikMatrix transformation, ikAnimation sender ){} Hlavička konstruktoru tedy musí obsahovat efektor effector, bázi base a cíl destination, což vyplívá z funkce kinematického řetězce. Tyto data jsou sice dostačující k popsání řetězce, ale nikoliv k jeho nalezení a aplikaci inverzní kinematiky na něm. K hledání kinematického řetězce je nutné znát ještě kořen kloubové struktury. Během výpočtu inverzní kinematiky dochází ke kompletnímu aktualizování struktury a tak musí být známa i počáteční matice transformation. Třída ikIteration je vždy obsluhována třídou ikAnimation, a kvůli předčasnému ukončení výpočtu je nutné ji znát. Odkaz na rodičovskou ikAnimation je v proměnné sender. Jediná funkce konstruktoru je nalézt kinematický řetězec podle algoritmu, který je popsán v kapitole 6.2.3. Funkce doIteration provádí stěžejní algoritmus. Po zavolání této funkce se provede pouze jedna iterace CCD metody. Funkce nevrací žádné hodnoty, pouze aktualizuje vlastnosti kloubů, a proto lze potřebné údaje vyčíst z kloubové struktury. Po provedení iterace se vypočítává chyba pozice i orientace koncového efektoru. Každý element kloubové struktury obsahuje dvě pole, v kterých se udržují informace o posledních dvaceti hodnotách chyb pozice a orientace. Tyto chyby se ukládají pouze do elementu

52


koncového efektoru. Díky tomu lze sledovat blízkou historii výpočtů a podle ní se zachovat. Ošetření hodnot chyb efektoru je popsáno v kapitole 8.4.2. Chyba koncového efektoru lze sice vyjádřit jedním vztahem [Kav02], ale pro naši potřebu je nutné ji počítat zvlášť. Výpočet chyby pozice je prostý. Do pole se jednoduše ukládá vzdálenost mezi cílem a efektorem. Čím blíže je efektor k cíli, tím menší je chyba pozice efektoru. Výpočet chyby orientace je poněkud složitější. Je nutné zajistit, aby s rostoucí chybou orientace rostlo i její číselné vyjádření a shodná orientace cíle a efektoru vracela nulovou hodnotu. Výpočet chyby orientace Eo ukazuje vztah (25).

Eo = 3 − ∑ (uief ⋅ uic ) 3

(25)

i =1

Každý vektor ortonormální matice efektoru uief je skalárně vynásoben s příslušným vektorem ortonormální matice cíle uic. Vektory ortonormální matice jsou na sebe navzájem kolmé a jejich velikost je rovna jedné (Obrázek 8.2). Hodnota každého součinu je tedy v rozmezí od -1 do 1, přičemž maximální hodnota součinu vyjadřuje minimální chybu. Odečtení sumy od hodnoty 3 tedy dává konečné vyjádření chyby orientace, se kterou je zacházeno podobně jako s chybou pozice.

Obrázek 8.2: Ortonormální vektory

53


8.4 ikAnimation Třída ikAnimation zajišťuje výpočet inverzní kinematiky pro více koncových efektorů. Ovládá jejich pravidelné střídání, ošetřuje oscilaci a zdárné ukončení, vytváří snímky a z nich celé animace. Vedlejšími funkcemi je výpočet inverzní kinematiky při interaktivním ovládání humanoida, převod humanoida ze scény do vlastní kloubové struktury, ukládání animací do VRML souboru a v neposlední řadě náhled na aktuální kloubovou strukturu.

8.4.1 Vytváření snímků Snímek lze definovat jako stav humanoida v jistém časovém okamžiku. K vyjádření stavu humanoida je zapotřebí kloubová struktura a počáteční transformace. Datový typ ikFrame, který reprezentuje snímek, obsahuje odkaz root na kořen příslušné kloubové struktury a matici počáteční transformace transformation. V animaci snímek zabírá jistý časový okamžik, jehož hodnota v milisekundách je uložena v proměnné delay. Funkce, která řídí výpočty kinematických řetězců, se nazývá doFrame. Jejím úkolem je polohovat všechny koncové efektory ke svým cílům s nejmenší chybou a vrátit výsledný snímek. Pro každý koncový efektor se vytvoří jedna instance třídy ikIteration, která vytvoří odpovídající kinematický řetězec. Funkce obsahuje cyklus, který střídá kinematické řetězce a vždy na nich provede jednu iteraci. Po provedení iterace na posledním řetězci se ověří poloha efektorů a v případě, že jsou chyby všech efektorů menší než požadovaná přesnost, tak se cyklus přeruší a funkce doFrame vrátí aktuální snímek humanoida.

private ikFrame doFrame( int index, ikElement[] effectors, ikJoint[] bases, ikDestination[] destinations, double DELTA_POS, double DELTA_ORI, int SPENT, boolean REPORT ){} Proměnná index vyjadřuje číslo snímku v celé animaci. Effectors je pole efektoru, kterým odpovídá pole bází bases a cílů destinations. Přesnost výpočtů vyjadřují proměnné DELTA_POS a DELTA_ORI, které odpovídají maximálním přínosným chybám

54


pozice a orientace z kapitoly 8.3. Hodnota SPENT vyjadřuje maximální možný počet iterací, čímž lze zabránit dlouhým výpočtům. Je-li zadána nula, tak se přeruší výpočet až v případě úspěšného dosažení cílů. REPORT povoluje výpis informací o výpočtech do konzole.

Funkce doRealTime byla vytvořena pro rychlé výpočty inverzní kinematiky, kde je cíl interaktivně zadáván pomocí myše. Základ této funkce je stejný jako u funkce doFrame s tím rozdílem, že vstupem je pouze jeden efektor, jedna báze a jeden cíl. Výpočty jsou tedy prováděny pouze na jednom kinematickém řetězci, protože lze interaktivně zadávat pouze jeden cíl. Pokud výpočet přesáhne deset iterací, tak je ukončen, aby bylo dosaženo větší rychlosti.

8.4.2 Zamezení dlouhého výpočtu Hlaví cyklus funkce doFrame se přeruší v případě, že všechny koncové efektory dosáhly svých poloh s požadovanou přesností. V případě více efektoru tato podmínka může nastat po velmi mnoha iteracích nebo nemusí být splněna vůbec. Mnohdy se efektory přiblíží svým cílům v několika málo iteracích a po zbytek iterací je poloha pouze zpřesňována. Při animaci není většinou kladen velký důraz na absolutní přesnost. Hlavní cyklus funkce doFrame tedy musí být obohacen o algoritmus rozpoznání těchto případů, který zabrání dlouhým výpočtům. První podmínkou předčasného ukončení funkce je překročení maximálního počtu povolených iterací. Pokud je čítač iterací counter roven proměnné spent, tak je cyklus přerušen a funkce vrací aktuální snímek. Toto omezení sice zajistí, že se cyklus ukončí v každém případě, ale stále není vyřešen případ, kdy jsou efektory v relativně dobrých polohách, ale již se nepřibližují. Rozpoznání časově dlouhého výpočtu se provádí pomocí výpočtu předpokládaného ukončení. Jak bylo v kapitole 8.3 uvedeno, chyby koncových efektorů se ukládají do speciálních polí těchto efektorů. Každou desátou iteraci se pro každý kinematický řetězec vypočte předpokládaný počet iterací. Z pole chyb efektoru je vybrána hodnota chyby, která nastala před deseti iteracemi a společně s aktuální chybou se vypočte pomocí proložení přímky předpokládaný počet iterací s akceptováním prahu přesnosti (Obrázek 8.3). Pokud předpokládaný počet iterací všech efektorů překročí hodnotu SPENT, tak se cyklus přeruší z důvodu pomalého výpočtu. Přerušení může nastat díky pomalému výpočtu pozice i orientace. Tyto výpočty se provádějí ale až od třiceti iterací výše, protože humanoid se několik prvních iterací velmi mění, což by mohlo mít negativní vliv.

55


Obrázek 8.3: Výpočet předpokládaného počtu iterací

8.4.3 Animace public Vector doAnimation( ikElement[] effectors, ikJoint[] bases, ikDestination[][] destinations, int[] delays, double DELTA_POS, double DELTA_ORI, int SPENT, boolean REPORT ){} Činnost funkce doAnimation je zřejmá již z názvu. Funkce obsahuje cyklus, v kterém se provádí výpočet snímků pomocí funkce doFrame a výsledné snímky jsou ukládány do spojového seznamu java.util.Vector. Až na pár rozdílů je hlavnička funkce identická s hlavičkou doFrame. Pro každý snímek je definována jiná sada cílů a proto pole destinations je dvourozměrné. Velikost prvního rozměru pole zároveň určuje počet snímků. Dalším rozdílem je existence pole delays, které obsahuje trvání jednotlivých snímků. Do každého vygenerovaného snímku se pouze zapíše příslušná hodnota do proměnné delay. První snímek výsledné animace není vypočítáván a je pouze kopií humanoida před vykonáním jakýkoliv změn. Návratová hodnota funkce je výsledný spojový

56


seznam. Třída ikAnimation má za úkol vytvářet animace, a proto je funkce doFrame privátní a hlavní úlohu vykonává funkce doAnimation.

8.4.4 Ukládání animací do souboru Třída ikAnimation také podporuje uložení animací. Funkce saveVRMLscene vytvoří soubor s VRML scénou, která animuje sekvenci snímků na humanoidu, který je v tomto projektu k dispozici. Po kliknutí myší na humanoida ve scéně se přehraje uložená animace. Prvním parametrem je název výstupního souboru out_file a druhým ukládaná animace movie. Návratovou hodnotou je pravdivostní hodnota, zda byl soubor v pořádku uložen.

static public boolean saveVRMLscene( String out_file, Vector movie ){} Systém ukládání pracuje tak, že zkopíruje obsah souboru humanoida do výstupního souboru a za něj zapíše potřebné VRML příkazy, které budou humanoida animovat. Prvním příkazem je dotykový senzor TouchSensor. Protože je umístěn až za celým souborem vstupního humanoida, tak je aktivován po kliknutí myší na jakoukoliv část scény. Dalším příkazem je časový senzor TimeSensor, který je aktivován dotykovým senzorem v případě kliknutí myši. Následně je celá kloubová struktura traverzována a pro každý kloub jsou vytvořeny rotace v závislosti na čase. Aby byla animace věrohodná, tak je prováděná pomocí interpolátorů, což zajišťuje plynulý pohyb skrze snímky. Pro každý kloub je vygenerován OrientationInterpolator, který na základě klíčů časového senzoru interpoluje úhly kloubů. Pomocí příkazu ROUTE je úhel kloubů namapován na příslušný uzel humanoidu. Kořen kloubové struktury vyžaduje zvláštní zacházení. Snímek totiž obsahuje počáteční transformaci, která nelze sama o sobě do VRML uložit. A proto se počáteční transformace aplikuje na pozici a orientaci kořene. Pro kořen se tedy vytvoří nejen příkaz pro interpolaci rotací kloubů, ale také příkaz PositionInterpolator, který plynule mění pozici kořene humanoida.

57


8.5 Optimalizace rychlosti Programovací jazyk Java je známý svojí přívětivostí k vývojáři, z čehož ale pramení i větší paměťová spotřeba a pomalejší vykonávání příkazů než u jiných vyšších programovacích jazyků. Připomeneme-li k tomuto faktu ještě pomalou odezvu při komunikaci mezi aplikací a VRML prohlížečem, tak se složité výpočty inverzní kinematiky při rozsáhlejší kloubové struktuře humanoida provádějí i několik minut. Na požadavek provádění animace „za běhu“ při interakci pomocí myši lze úplně zapomenout. Díky těmto komplikacím bylo nutné přistoupit k optimalizaci nejčastějších operací. Každá optimalizace rychlosti byla měřena na jedné z testovaných úloh několikrát a výsledný čas byl získán jako průměr. V tabulce (Obrázek 8.4) jsou uvedeny průměrné časy a procentuální zastoupení optimalizace vzhledem k neoptimalizovanému stavu. Nejprve bylo nutné zjistit, jaké operace se provádějí nejčastěji. Kupodivu se nejedná o výpočty změny úhlu kloubů, které jsou relativně výpočetně složité vzhledem k ostatním algoritmům. Největší četnost ve výpočtech byla zaznamenána u přepočtu kloubové struktury. Při každé změně úhlu docházelo k přepočítávání kompletní kloubové struktury, což časově zabíralo převážnou část výpočtů. Tuto funkci je bohužel nutné aplikovat při každé změně, protože se změní poloha několik kloubů. První

optimalizací

byla

modifikace

aktualizace

kloubové

struktury,

aby

se

nepřepočítávala poloha kloubů, jejichž poloha se nezměnila. Je-li rotovaný kloub potomkem báze (klouby se znaménkem +, Obrázek 6.12a), tak se mění pouze poloha kloubů jeho podstromu, což velmi zefektivní výpočet. Je-li rotovaný kloub předkem báze (klouby se znaménkem -, Obrázek 6.12a), tak se mění poloha celé kloubové struktury, kromě jeho podstromu. Pouze v tomto případě je nutné aktualizovat celou kloubovou strukturu. Tato optimalizace zapříčinila dvojnásobné zrychlení výpočtů. Dalším krokem bylo optimalizování jednotlivých maticových operací, které jsou potřeba při aktualizaci kloubové struktury. Předchozí zefektivnění aktualizace struktury bylo samozřejmě zachováno. Novou optimalizací bylo složení matic rotací Eulerových úhlů. Prozatímní rotace kloubu pracovala jako násobení třech matic dílčích kloubů, přičemž každá matice byla rotace kolem předepsané osy (vztah 7 a 8). Zkonstruování a vzájemné vynásobení těchto matic je zbytečné zdržení a tak byla vytvořena funkce, která vypočte matici kompletní rotace celého kloubu (matice ve vztahu 4). Tato optimalizace pomohla k trojnásobnému zrychlení neoptimalizovaného algoritmu. Následně na optimalizaci rotace došlo k vylepšování posunutí. K zrychlení přispěl fakt, že se při posunutí nemění orientace. Matice posunu se již nenásobí s aktuální maticí, ale vytvoří se kopie aktuální matice a tři hodnoty pro souřadnice pozice se dopočítají zvlášť.

58


Další výhodou je odpadnutí násobení matic. Tímto způsobem obdržíme matici, na kterou bylo aplikováno posunutí. Asi největší četnost má funkce násobení matic a to nejen v aktualizaci kloubové struktury. Každá matice v tomto projektu je transformační matice v kartézském systému a splňuje jistá pravidla (vztah 26). Prvky oi vyjadřují orientaci a pi pozici v systému, přičemž poslední sloupec je nevyužit. Násobení matice se tedy neprovádí třemi vnořenými cykly, ale prvky se vypočítávají zvlášť a hodnoty posledního sloupce se zadávají přímo.

 o1 o  4  o7   p1

o2 o5 o8 p2

o3 0 o6 0 o9 0  p3 1

(26)

Princip posledních dvou optimalizací přispěl i k druhému zefektivnění rotace. Matice rotace se také neprovádí násobením matic, ale hodnoty se vypočítají přímo. Toto je poslední použitá optimalizace a tak kompletní čas výpočtu se snížil na šestinu celkového výpočtu.

Typ optimalizace

Doba výpočtu [min]

Poměr [%]

Bez optimalizace

2:02

100 %

+ Aktualizace kloubové struktury

1:06

53,6 %

+ Sloučení rotací dílčích kloubů

0:38

31,1 %

+ Optimalizace posunutí

0:27

21,7 %

+ Optimalizace násobení

0:24

19,6 %

+ Optimalizace rotace

0:20

16,3 %

Celkové zrychlení

0:20

16,3 %

Obrázek 8.4: Tabulka optimalizací

Plánovanou ale bohužel nepoužitou optimalizací bylo zefektivnění inverze matice. Při inverzi matice dochází k výpočtu diskriminantu submatice, která odpovídá prvkům orientace. Tento diskriminant je mnohokrát zastoupena v dalších výpočtech inverze. U transformačních matic je hodnota diskriminantu rovna jedné, což by velmi zefektivnilo výpočet. Jeho hodnota se tedy zadala přímo, avšak od této optimalizace se muselo opustit, protože po jistém počtu iterací se hodnoty matic měnily mimo vymezená pravidla. Díky nepřesnostem ve výpočtech

59


při dělení v Javě vycházela hodnota diskriminantu pouze velmi blízká jedné. Po aplikování diskriminantu v dalších výpočtech se tato chyba jistým způsobem vykompenzovala a k chybám nedocházelo. Stávající výpočet inverzní matice musel být tedy zachován.

8.5.1 Operační složitost Metoda CCD není jednoprůchodová, a proto nelze určit operační složitost pouze pomocí počtu kloubů. Základní cyklus vyjadřuje počet iterací i, tedy složitost je O(i). V každém cyklu se přibližuje koncový efektor za pomocí změny kloubů v kinematickém řetězci. Výpočet změny kloubu je konstantní a je-li počet kloubů struktury n, tak jedna iterace má složitost

O(n) i při více efektorech. Celková operační složitost je tedy O(i⋅n). Rozdělení kloubu do dílčích kloubů je pouhé násobení třemi, což je konstanta, která složitost neovlivní. Po každém výpočtu je nutné aktualizovat kloubovou strukturu, což se provádí se složitostí O(n) a celková složitost je tedy O(i⋅n2). Hledání kinematického řetězce na počátku výpočtu se provádí se složitostí O(n), a tak asymptoticky neovlivní celkovou složitost. Výsledná operační složitost animace o m snímcích je tedy O(m⋅i⋅n2). Při zanedbání pozice či orientace se operační složitost nemění. Výpočet je sice mnohdy daleko rychlejší, ale asymptoticky je stále adekvátní O(m⋅i⋅n2). Operační složitost výpočtu pozice či orientace je konstantní O(1), a proto ani ve svém složení nemají vliv na výslednou operační složitost.

60

Závěr

9 Závěr Animace lidské postavy poskytuje široké pole k bádání. Lidské tělo je složitý systém, který bohužel není ani jednoznačný a liší se od člověka k člověku. Stavba kostí, kloubů a svalů skrývá velkou rozmanitost v pohybu a kloubová struktura se svými atributy, která je chabou aproximací lidského těla, se může jen zlehka přiblížit k reálné situaci. Tento projekt ukázal možnosti postupu při návrhu animace lidské postavy a je malým článkem na počátku dlouhého vývoje tohoto oboru. Byla zde zmíněna reprezentace odporů svalů a limitů kostí, které za pomocí inverzní kinematiky oživují kloubovou strukturu a pravděpodobně v sobě nesou budoucnost při animaci lidské postavy. Bohužel jsou také pouhým zjednodušením a snaží se nahradit všechny zbývající atributy těla, které ovlivňují pohyb. Dalším možným přínosem by mohlo být ošetření kolizí, zdokonalení kloubové struktury či jejích atributů. Experimentální program, který se skládá z animačních knihoven a demonstrační aplikace lze považovat za plnohodnotný software a není pouhou demonstrací algoritmů. Využití již nalezl v [Lin05], kde byly animační knihovny použity ke generování pohybu humanoida pro výuku hry na bicí. Dále se uplatnily v projektu IST-2001-32184 ActIPret, jehož plánem je vyvinout metodu kognitivního počítačového vidění, která interpretuje a zaznamenává aktivity člověka při manipulačních úkolech. Kromě zkoumání kognitivního vidění obsahuje část, jejíž úkol je prezentování výsledků ve virtuální realitě. Jediným zdrojem dat pro animaci byla pozice dlaně operátora, což je ideální případ pro využití inverzní kinematiky [SZH04].

61

Příloha A – Uživatelská příručka

Příloha A – Uživatelská příručka Pro testování algoritmů byla aplikace implementována v programovacím jazyku Java ve verzi 1.1, aby mohla být spouštěna interpretem Java Virtual Machine od firmy Microsoft. Aplikace byla testována na více verzích interpretu, ale plně funkční chod programu byl zajištěn ve verzi 5.0. Interpret se spouští příkazem jview.exe a pro zajištění korektního spuštění aplikace je nutné i uvést i cestu k pracovnímu adresáři. Nacházíme-li se v hlavním pracovním adresáři, tak se aplikace spustí příkazovým řádkem:

jview.exe /cp . ikproject.ikDemo [humanoid] [scena.ikc]

-

ikproject.ikDemo – název hlavní třídy

-

humanoid.wrl – prvním nepovinným parametrem je soubor s humanoidem

-

scena.ikc – další nepovinný parametr je soubor se scénou

A.1 Ovládání aplikace Aplikace (Obrázek A.1) se skládá ze čtyř hlavních objektů. Převážnou část okna aplikace zabírá prohlížeč VRML scény s humanoidem (1), na kterém se aplikují výpočty inverzní kinematiky. Informace o aktuálním stavu a vykonaných operacích se vypisují do konzole (2). Ovládací prvky se nacházejí v levé části (4 a více). Pro každý z objektů uživatelského rozhraní existuje krátká nápověda o jeho významu, která se zobrazuje v nápovědním řádku na spodu okna aplikace (3). Prvním krokem při práci s aplikací je volba humanoida. Ta se provádí pomocí rozbalovací nabídky Humanoid (4). Humanoid se načte do scény a nahradí předcházejícího. V konzoli se vypisují informace o napojení humanoida na scénu a o sejmutí jeho kloubové struktury. Humanoid může být zaveden hned po startu, pokud byl uveden jako parametr v příkazové řádce. Aplikace umožňuje práci ve dvou módech, které lze měnit pomocí tlačítka Reálný mód – Normální mód (5).

62


Obrázek A.1: Aplikace – normální mód

A.1.1 Normální mód Normální mód umožňuje práci se scénami, které generují celé animace s více efektory. Popis souboru scény je uveden v kapitole A.2.1. Volba scény se provádí pomocí nabídky Scéna (6), která obsahuje všechny scény nalezené v pracovním adresáři. Po načtení scény se uvolní všechny dostupné funkce. Výpočet scény se provádí pomocí tlačítka …výpočet (8) a to třemi možnými způsoby:

1) Normální výpočet – standardní výpočet, kdy se vygeneruje scéna a výsledná animace lze přehrát v prohlížeči. Animace nenahrazuje předchozí, ale připojí se za ní, čímž lze vytvořit libovolnou kombinaci animací z jednotlivých dílčích kusů.

2) Simulace snímku – testovací výpočet. Zobrazí se okno (A.1.3) s kostrou humanoida, kde se zobrazuje výpočet po jednotlivých snímkách inverzní kinematiky (neplést si se snímky scény). Okno animace je nezávislé na hlavní aplikaci, takže

63


nevrací výslednou animaci do aplikace a nelze tudíž přehrát v prohlížeči. Tato funkce slouží jako kontrola správnosti výpočtu a je naimplementována v animační knihovně.

3) Simulace Iterace – plní stejnou funkci jako simulace snímku pouze s tím rozdílem, že se zobrazuje stav kostry po každé změně úhlu. Aktuálně měněný kloub je vyznačen modře, efektor červeně a báze zeleně.

Nastavení humanoida do původní polohy, tak jak je definován ve VRML souboru, se vykoná tlačítkem Obnovit (9). Kompletní animaci lze uložit na disk pomocí tlačítka Uložit (7). Do výsledného VRML souboru se uloží jak humanoid, tak i animovaná sekvence. To znamená, že lze výslednou animaci přehrát v jakémkoliv VRML prohlížeči, bez nutnosti existence této aplikace. Ukládání animace umožňuje i samotná animační knihovna, ale animace se provádí na testovacím humanoidu, který je obsažen v tomto projektu. Název souboru lze zadat v textovém poli nad tlačítkem. Soubor bude umístěn ve stejném adresáři jako humanoid kvůli případnému využití externích souborů. Přehrávaní animace (10) lze docílit třemi způsoby:

1) Tlačítko Přehrát – přehraje animaci v hlavním okně prohlížeče 2) Tlačítko Ukázka – přehraje animaci na kostře humanoida ve speciálním okně 3) Tlačítko VRML ukázka – přehraje animaci na testovacím humanoidu v okně

Většina humanoidů implicitně neobsahuje hodnoty odporů a někdy jsou globálně nastaveny na maximální odpor. Z tohoto důvodu lze nastavit globálně hodnoty odporů posuvníkem (11). Výchozí nastavení odporů ve VRML souboru lze použít označením přepínače VRML odpor.

A.1.2 Reálný mód Tento mód umožňuje ovládat humanoida jedním efektorem interaktivně pomocí myši. Na ovládacím panelu v reálném módu (Obrázek A.2) se v nabídce Efektor (1) a Báze (2) zvolí stejnojmenné elementy na prvcích kloubové struktury. Pozice cíle se zobrazuje v textových polích (3). Zadání nových hodnot cíle lze provést vepsáním souřadnic do příslušných polí a následným stisknutím tlačítka OK. Volba cíle a báze se zobrazí pomocí červené (4) a zelené (5) krychle v prohlížeči na adekvátních pozicích.

64


Obrázek A.2: Aplikace – Reálný mód

Pohybovat lze pouze pomocí cíle. Uchopením a tahem myši po příslušné ploše krychle se mění pozice cíle v rovině rovnoběžné s touto plochou krychle. Prvky pro volbu humanoida, pracovního módu či obnovení jsou přístupné i tomto režimu.

A.1.3 Okno animační knihovny Předchozí popisované uživatelské rozhraní se vztahuje pouze k demoverzi animační knihovny. Avšak samotná animační knihovna obsahuje okna (Obrázek A.3) pro sledování běhu výpočtu a přehrávání animací. Kolem zobrazované scény (1) je i několik ovládacích prvků. V levém horním rohu se nachází tlačítko Play (3), které umožňuje přehrát aktuální animaci. Posuvník (5) a informační štítek (4) oznamují uživatele o aktuální pozici přehrávání. Posuvník rovněž umožňuje zvolit zobrazovaný snímek. Zvětšení scény je k dispozici pouze u zobrazení kloubové struktury a to posuvníkem v levé části okna (2). Rychlost přehrávání se nastavuje posuvníkem v pravé části okna (6). V případě zobrazení VRML scény se s obrazem manipuluje pomocí uživatelského rozhraní prohlížeče. Je-li však zobrazena kloubová struktura, tak se kamera otáčí okolo středu stisknutím levého tlačítka a tahem myši. Střed otáčení se mění stisknutím pravého tlačítka a tahem myši.

65


Obrázek A.3: Okna animační knihovny

A.2 Speciální soubory Kromě souborů se scénami jsou k běhu programu potřebné i jiné soubory. Jisté z nich se musí modifikovat pro správný běh programu. Seznam humanoidů je uveden v souboru humanoids.ini v pracovním adresáři. Na lichých řádcích souboru jsou uvedena jména humanoidů, která jsou zobrazena v nabídce aplikace a na sudých řádcích jsou uvedeny názvy souborů humanoidů. Seznam humanoidů je na posledním řádku ukončen vykřičníkem. Zde je ukázka možného souboru humanoids.ini:

Bob bob\bob.wrl Marvin marvin.wrz ! Obrázek A.4: Humanoids.ini

V programovém adresáři ikproject se nalézá několik souborů, které lze modifikovat, přestože se s tímto implicitně nepočítá. Soubor language.ini je v textovém formátu a obsahuje překlad celého programu do češtiny. V případě, že tento soubor není v programovém adresáři obsažen, tak je program spuštěn v anglickém jazyce. Testovací humanoid je obsažen v souboru bob.wrl a soubor scény, v které se humanoid nachází, se nazývá scene.wrl.

66


A.2.1 Formát scény Z hlavního pracovního adresáře se načítají soubory s koncovkou ikc do nabídky scén v aplikaci. Scéna je konfigurační soubor, který určuje data pro vykonání animace. Každá sekce konfiguračního souboru obsahuje úvodní řádek, který usnadňuje práci se souborem. Obsahuje libovolný informační řádek, který je parserem programu přeskakován. Sekce konfiguračního souboru:

1) počet efektorů – celočíselná hodnota; vyjadřující počet efektorů 2) počet snímků – celočíselná hodnota; počet snímků animace, také určuje počet cílů pro každý efektor 3) maximální počet iterací – celočíselná hodnota; určuje maximální počet iterací a přibližnou délku 4) trvání snímků – pole celočíselných hodnot o velikosti počtu snímků; každý snímek je před svým zobrazením zpožděn o určitou hodnotu, která je zadána v milisekundách 5) názvy efektorů – pole řetězců; názvy efektorů, které jsou uvedeny ve vstupním humanoidu 6) názvy bází – pole řetězců; názvy bází, které jsou uvedeny ve vstupním humanoidu 7) cíle pro efektory – dvojrozměrné pole hodnot cílů; pro každý efektor je vyčleněna jedna sekce, která začíná úvodním identifikačním řádkem a pak následuje seznam cílů ve snímkovém pořadí

Cíle umožňují velkou volnost, a je mnoho způsobů, jak je zadat. Standardní situace je zadání pozice i orientace pro cíl, avšak program umožňuje zadat pouze pozici či orientaci. Pozice se zadává v kartézském souřadném systému v metrech a orientace pomocí Eulerových úhlů v radiánech. Oddělovacím znakem je středník, který odlučuje pozici a orientaci. Možné kombinace jsou zde:

0.1 -0.2 0.312 ; 1.57 -0.5 0.3 0.1 -0.2 0.312 1.57 -0.5 0.3

pozice ; orientace

0.1 -0.2 0.312 ;

pozice

0.1 -0.2 0.312

orientace

; 1.57 -0.5 0.3 Obrázek A.5: Možnosti cíle

67


Příklad konfiguračního souboru:

// počet efektorů 3 // počet snímků 2 // maximální počet iterací 100 // trvání snímků 500 2000 // názvy efektorů r_wrist l_wrist l_ankle // názvy bází r_hip r_hip r_hip // cíle pro r_wrist -0.4 0.9 0.35 0 0 -0.75 -0.8 1.1 0.7 0 0 -1.5 // cíle pro l_wrist 0.4 0.9 0.35 0 0 0.75 0.8 1.1 0.7 0 0 1.5 // cíle pro l_ankle 0.1 0.5 -0.5 0.1 1 -1 Obrázek A.6: Příklad souboru scény

68

Příloha B – Obsah CD

Příloha B – Obsah CD

Ø [APPLICATION] - adresář s aplikací, testovacími scénami a humanoidy Ø [SOURCE]

- okomentované zdrojové kódy aplikace

Ø [SUPPORT]

- podpůrný software pro zajištění korektního chodu aplikace

§

Cortona v4.1.exe - prohlížeč VRML scén, nutný pro běh aplikace

§

VM v5.0.exe

- interpret aplikací psaných v jazyce Java verze 1.1

Ø abstract.pdf

- abstrakt tohoto projektu

Ø ik.pdf

- text diplomové práce

Ø readme.txt

- informace o obsahu CD

69

Literatura

Literatura [SZH04]

V. Štěpán, J. Žára and V. Hlaváč. Virtual reality presentation demo: Replay of interpreted aktivity. Research report Czech Technical University, Prague, 2004

[Wel93]

Ch. Welman Inverse kinematics and geometric constraints for articulated figure manipulation Simon Fraser University, 1993

[Bae01]

P. Baerlocher Inverse kinematics techniques for the interactive posture control of articulated figures Lausanne, EPFL, 2001

[Bar03]

L. Bařinka Animace kloubových struktur (in Czech) Czech Technical University, Prague, 2003

[Kav03]

L. Kavan Simulation of Fencing in Virtual Reality Charles University, Prague, 2003

[Lin05]

M. Linda Systém pro výuku hry na bicí (in Czech) Czech Technical University, Prague, 2005

[Ste03]

V. Štěpán Using VRML EAI in Applets and Applications Czech Technical University, Prague, 2003

[Kav02]

L. Kavan Metody skeletální animace (in Czech) Charles University, Prague, 2002

[Fen81]

H. Feneis Anatomický obrazový slovník (in Czech) Avicenum, Prague, 1981

70

Literatura

[Han11]

Humanoid Animation Working Group H-Anim 1.1 specification http://h-anim.org/Specifications/H-Anim1.1/

[EWW]

E. W. Weisstein MathWorld – Euler's Rotation Theorem http://mathworld.wolfram.com/EulersRotationTheorem.html

[Bak]

M.Baker EuclideanSpace – Euler Angles http://www.euclideanspace.com/maths/geometry/rotations/euler/

[Wik]

Wikipedia – Quaternion http://en.wikipedia.org/wiki/Quaternion

[Bei]

Matt Beitler H-Anim 1.1 Compliant VRML97 Humanoid Models http://www.cis.upenn.edu/~beitler/hanim/

71

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA ELEKTROTECHNICKÁ

Recommend Documents