Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra informatiky a výpočetní techniky. Generování kostry objektů reprezentovaných

Za´padoˇceska´ univerzita v Plzni Fakulta aplikovanyćh vˇed Katedra informatiky a vy´poˇcetn´ı techniky

Diplomov´ a pr´ ace Generov´ an´ı kostry objekt˚ u reprezentovan´ ych troj´ uheln´ıkov´ ymi s´ıtˇ emi

Plzeˇ n, 2015

ˇ ak Michal Z´

Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem diplomovou práci vypracoval samostatnˇe a výhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u. V Plzni dne 21. ˇcervna 2015 ˇ ak Michal Z´

Abstract This diploma thesis deals with automatic generation of animation skeleton for humanoid objects which are represented by triangle meshes. After research focused on existing similar methods, new original method was invented, implemented and afterwards tested on input data set consisted of meshes representing humanoids. Generated animation skeleton keeps desired topological structure and contains movement limits in every joint. In addition to the skeleton generation, we implemented testing application which allows user to animate generated skeleton and original mesh by using inverse kinematics.

Abstrakt Tato diplomová práce se zab´ yvá automatick´ ym generován´ım animaˇcn´ı kostry pro humanoidy reprezentované troj´ uheln´ıkov´ ymi s´ıtˇemi. Na základˇe existuj´ıc´ıch pˇr´ıbuzn´ ych metod byl vytvoˇren a naimplementován vlastn´ı postup, kter´ y byl poté testován na mnoˇzinˇe vstupn´ıch dat, model˚ u reprezentuj´ıc´ıch humanoidy. V´ ysledná animaˇcn´ı kostra dodrˇzuje pˇredem danou topologickou strukturu a obsahuje definice omezen´ı volnosti pohybu v jednotliv´ ych kloubech. Kromˇe samotného generován´ı byla naimplementována také testovac´ı aplikace, ve které uˇzivatel m˚ uˇze interaktivnˇe rozh´ ybat vzniklou kostru a p˚ uvodn´ı model uˇzit´ım inverzn´ı kinematiky.

2

Podˇ ekov´ an´ı Chtˇel bych podˇekovat panu doc. Ing. Josefu Kohoutovi, Ph.D. za cenné rady a pˇripom´ınky pˇri veden´ı diplomové práce.

3

Obsah ´ 1 Uvod

1

2 Metody extrakce kostry

3

2.1

Medial axis transform . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.2

Metody zaloˇzené na geometrii a topologii . . . . . . . . . . . . . . . .

5

2.2.1

Smrˇstˇen´ı modelu s následnou redukc´ı geometrie . . . . . . . .

5

2.2.2

Tvorba kostry spojován´ım v´ yznamn´ ych bod˚ u . . . . . . . . . 10

2.3

Volumetrické metody . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3.1

2.4

Generován´ı kostry sn´ımaného ˇclovˇeka v reálném ˇcase . . . . . 14

Pˇr´ıbuzné oblasti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3 Pˇ r´ım´ a a inverzn´ı kinematika

17

3.1

Pˇr´ımá kinematika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.2

Inverzn´ı kinematika . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2.1

Linearizace pomoc´ı jakobiánu . . . . . . . . . . . . . . . . . . 19

3.2.2

Cyclic coordinate descent

3.2.3

Obohacen´ı o posuvná spojen´ı . . . . . . . . . . . . . . . . . .

4 N´ avrh vlastn´ı metody

. . . . . . . . . . . . . . . . . . . . 20 21 22

4.1

Generován´ı kostry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.2

Interaktivn´ı ukázka . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

5 Podrobn´ y rozbor metody

24

5.1

Vstupn´ı data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5.2

Generován´ı prozat´ımn´ı kostry . . . . . . . . . . . . . . . . . . . . . . 25

5.3

Vytvoˇren´ı animaˇcn´ı kostry . . . . . . . . . . . . . . . . . . . . . . . . 26 5.3.1

Pˇr´ıpravné kroky a pˇriˇrazen´ı hlavy . . . . . . . . . . . . . . . . 26

5.3.2

Pˇriˇrazen´ı list˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5.4

5.3.3

Pˇriˇrazen´ı vnitˇrn´ıch uzl˚ u . . . . . . . . . . . . . . . . . . . . . 28

5.3.4

Zkop´ırován´ı lokáln´ıch souˇradnicov´ ych systém˚ u . . . . . . . . . 30

5.3.5

Zkop´ırován´ı limitace pohybu v kloubech . . . . . . . . . . . . 30

Interaktivn´ı deformace . . . . . . . . . . . . . . . . . . . . . . . . . .

31

5.4.1

Inverzn´ı kinematika . . . . . . . . . . . . . . . . . . . . . . . .

31

5.4.2

Mesh-skinning . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

6 Implementace demonstraˇ cn´ı aplikace

37

6.1

Pouˇzité knihovny a jazyk . . . . . . . . . . . . . . . . . . . . . . . . . 37

6.2

Formát vstupn´ıch dat . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 6.2.1

Vzorová kostra . . . . . . . . . . . . . . . . . . . . . . . . . . 38

6.2.2

Troj´ uheln´ıková s´ıt’ . . . . . . . . . . . . . . . . . . . . . . . . 39

6.3

Generován´ı kostry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

6.4

Ukázková aplikace

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

6.4.1

Inverzn´ı kinematika . . . . . . . . . . . . . . . . . . . . . . . .

41

6.4.2

Mesh-skinning . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

6.4.3

Nastaven´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

7 V´ ysledky

42

7.1

Testovac´ı modely . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

7.2

Nastaven´ı konstant generován´ı kostry . . . . . . . . . . . . . . . . . . 44

7.3

V´ ysledná podoba kostry . . . . . . . . . . . . . . . . . . . . . . . . . 45

7.4

Doba generován´ı kostry . . . . . . . . . . . . . . . . . . . . . . . . . . 47

7.5

Pamˇet’ová sloˇzitost generován´ı kostry . . . . . . . . . . . . . . . . . . 49

7.6

Doba v´ ypoˇctu inverzn´ı kinematiky

7.7

Srovnán´ı s existuj´ıc´ımi metodami . . . . . . . . . . . . . . . . . . . . 50

. . . . . . . . . . . . . . . . . . . 49

8 Z´ avˇ er

52

A Pˇ r´ıloha: Obsah CD

55

B Pˇ r´ıloha: Uˇ zivatelsk´ y manu´ al

56

B.1 Pˇreklad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 B.2 Parametry pˇr´ıkazové ˇra´dky . . . . . . . . . . . . . . . . . . . . . . . . 56 B.3 Ovládán´ı aplikace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

´ 1 Uvod V poˇc´ıtaˇcové grafice se pˇri ˇreˇsen´ı problém˚ u stˇretávaj´ı lidé r˚ uzn´ ych zamˇeˇren´ı, ostatnˇe obor sám se nacház´ı na pomez´ı informatiky, matematiky a estetiky. V ˇradˇe aplikac´ı zejména konzumn´ıho charakteru nepostaˇcuje pouze jej´ı technická funkˇcnost, uˇzivatelé podvˇedomˇe kladou d˚ uraz na v´ ytvarnou stránku. Na v´ yvoji pak pracuj´ı vedle programátor˚ u a analytik˚ u také v´ ytvarn´ıci, kteˇr´ı tvoˇr´ı samotn´ y grafick´ y obsah. K tomu jim pomáhaj´ı r˚ uzné komplexn´ı nástroje pro modelován´ı, kresbu, u ´pravu fotografi´ı atd. Nejvˇetˇs´ı pˇrekáˇzkou je pak samotné pˇrenesen´ı vytvoˇreného grafického obsahu do c´ılové aplikace. Tyto u ´pravy ˇcasto nepoˇzaduj´ı ˇza´dnou invenci nebo estetické c´ıtˇen´ı, nicménˇe mohou být ˇcasovˇe nároˇcné. Takto tráv´ı výtvarn´ık ˇcas ˇremeslnou prac´ı, m´ısto n´ıˇz by mohl produkovat dalˇs´ı origináln´ı obsah. Pro programátory v oboru poˇc´ıtaˇcové grafiky se tak naskytuje pomˇernˇe ˇsiroké pole pro tvorbu nástroj˚ u, které usnadn´ı produkci grafického obsahu. Jedn´ım z typ˚ u dat, které jsou uˇz´ıvány pˇri vizualizac´ıch, jsou troj´ uheln´ıkové s´ıtˇe. V této podobˇe jsou objekty reprezentovány pomoc´ı svého povrchu, respektive aproximac´ı povrchu troj´ uheln´ıky, které mohou sd´ılet své hrany a vrcholy. Problém nastává u rozpohybován´ı (animace) s´ıt´ı. Historicky byl omezuj´ıc´ım faktorem výpoˇcetn´ı výkon, pouˇz´ıvaly se primitivn´ı metody jako napˇr´ıklad pohybuj´ıc´ı se hierarchie nemˇenn´ ych objekt˚ u ˇci animace per-vertex, tedy definován´ı pohybu pro kaˇzdý vrchol s´ıtˇe zvláˇst’. S nár˚ ustem výkonu se prosadily tzv. kostern´ı animace, kdy pohyb povrchu tˇelesa ˇr´ıd´ı kostra znaˇcnˇe jednoduˇsˇs´ı neˇz p˚ uvodn´ı s´ıt’. Zˇrejmou výhodou je u ´spora ukládaných dat, nebot’ staˇc´ı zachytit stav kostry v ˇcase a pˇriloˇzit statickou podobu troj´ uheln´ıkové s´ıtˇe. Animátor nav´ıc dostává ˇr´ıdic´ı mechanismus, kter´ ym m˚ uˇze objekt intuitivnˇeji ovládat oproti animaci per-vertex. Na naˇseho výtvarn´ıka vˇsak spadá také nevdˇeˇcná tvorba této kostry. Uvˇedomme si, ˇze pro ˇradu model˚ u má kostra podobn´ y charakter, zejména pak u model˚ u zv´ıˇrat nebo lid´ı, kdy apriornˇe známe napˇr´ıklad poˇcet konˇcetin, jejich pˇribliˇzné rozloˇzen´ı a pomˇery délek. Pro specifická uˇzit´ı nav´ıc mus´ı výtvarn´ık do kostry doplnit informaci o omezen´ı volnosti v kloubech a dalˇs´ı pomocné u ´daje. Diplomová práce porovnává jiˇz vzniklé metody pro automatickou tvorbu kostry. 1

´ Uvod Na základˇe pr˚ uzkumu pak vytvoˇr´ıme nástroj, kter´ y pro humanoida ztvárnˇeného troj´ uheln´ıkovou s´ıt´ı, u nˇehoˇz uplatn´ıme apriorn´ı znalosti, vytvoˇr´ı jeho animaˇcn´ı kostru s omezen´ımi volnosti pohybu v kloubech. Výsledek bude pˇredveden v aplikaci, která umoˇzn´ı iteraktivnˇe deformovat model pomoc´ı inverzn´ı kinematiky uˇzité na vygenerovanou kostru.

2

2 Metody extrakce kostry K automatické extrakci kostry vznikla ˇrada metod, které jsou zaloˇzeny na r˚ uzných pˇr´ıstupech. Práce se zab´ yvá kostrami sloˇzen´ ymi ze kˇrivek (curve skeletons), které lze definovat jako jednorozmˇernou strukturu zjednoduˇsuj´ıc´ı p˚ uvodn´ı objekt, pˇriˇcemˇz zachovávaj´ı topologickou a geometrickou informaci. Kostra se skládá z d´ılˇc´ıch kˇrivek naz´ yvan´ ych kosti, zpravidla uspoˇra´dan´ ych do hierarchie. Nˇekteré metody produkuj´ı kostru sloˇzenou pouze z u ´seˇcek. Pˇri c´ılovém uˇzit´ı vzniklé kostry ji obvykle rozˇs´ıˇr´ıme do podoby parametrizovaného Frenetova trojhranu (kv˚ uli jednoznaˇcnému urˇcen´ı lokáln´ı soustavy souˇradnic). Objekt b´ yvá obvykle reprezentován povrchovˇe pomoc´ı troj´ uheln´ıkové s´ıtˇe, které kromˇe pozic vrchol˚ u a jejich spojen´ı v troj´ uheln´ıky obsahuj´ı informaci o sousednostech. V tomto pˇr´ıpadˇe nastupuj´ı geometrické a topologické metody tvorby kostry, v pˇr´ıpadˇe objemové (voxelové) reprezentace metody pracuj´ıc´ı v diskrétn´ım prostoru.

2.1

Medial axis transform

Harry Blum v roce 1967 [6] prvnˇe formalizoval stˇredn´ı osu objektu. Z jeho definice v podstatˇe vˇsechny novˇejˇs´ı postupy vycházej´ı, nicménˇe pˇridávaj´ı dalˇs´ı kritéria a upouˇstˇej´ı od pˇresného vyjádˇren´ı.

Obrázek 2.1: Ukázka stˇredn´ı osy dvourozmˇerného objektu (vyznaˇcena pˇreruˇsovanˇe). Stˇredn´ı osa objektu (medial axis) je definována jako mnoˇzina bod˚ u Q maj´ıc´ıch stejnou vzdálenost k alespoˇ n dvˇema bod˚ um hranice objektu, aniˇz by se jin´ y bod náleˇz´ıc´ı hranici nacházel bl´ıˇze k Q.

3

Metody extrakce kostry

Medial axis transform

Formálnˇe lze definici zapsat matematickou formulac´ı: ∀X ∈ E 3 : X ∈ MA(O) ⇐⇒ ∃A1 , A2 ∈ surface(O) : kA1 Xk = kA2 Xk ∧ @B ∈ surface(O) : kBXk < kA1 Xk

(2.2) (2.3)

kde O znaˇc´ı vstupn´ı objekt, MA(O) formálnˇe stˇredn´ı osu objektu O a surface(O) povrch objektu. Pˇr´ıklad stˇredn´ı osy objektu je ukázán na obrázku 2.1. Blum ve svém ˇclánku pouˇzil definici pomoc´ı propagace události v ˇcase: Na poˇcátku vznikne na hranici objektu událost, která se dál homogennˇe ˇs´ıˇr´ı prostorem. Pro pˇr´ıklad si m˚ uˇzeme objekt pˇredstavit jako louku a událost jako ˇs´ıˇr´ıc´ı se poˇzár zaloˇzený na jej´ı hranici. Dan´ ym m´ıstem prostoru m˚ uˇze událost proj´ıt pouze jednou, pˇri pouˇzit´ı naˇs´ı analogie lze ˇr´ıct, ˇze poˇza´r nepokraˇcuje zpˇet na spáleniˇstˇe. Bod, ve kterém se v jednom ˇcase setká v´ıce událost´ı pocházej´ıc´ıch z odliˇsných zdroj˚ u (jiných bod˚ u hranice), tvoˇr´ı stˇredn´ı osu objektu. Proces je znázornˇen na obrázku 2.4.

Obrázek 2.4: Medial axis transform, ilustrace propagace události v ˇcase. Vlevo se nacház´ı p˚ uvodn´ı objekt, vpravo objekt s v´ yslednou stˇredn´ı osou. V m´ıstech nespojitosti vzniká stˇredn´ı osa objektu. V souvislosti se stˇredn´ı osou objektu se hovoˇr´ı o tzv. medial axis transform. Jedná se o transformaci, pˇri které povrchem reprezentovaný objekt O nahrad´ıme mnoˇzinou maximáln´ıch prázdn´ ych hyperkoul´ı Si tak, ˇze: [

¯ Si = O

∀i

4

(2.5)


Metody zaloˇzené na geometrii a topologii

Hyperkoule se mohou vzájemnˇe prot´ınat, povrch objektu O vˇsak nesm´ı b´ yt obsaˇzen uvnitˇr objemu libovolné hyperkoule, pouze na jej´ım povrchu (pro stˇredy hyperkoul´ı plat´ı formulace 2.2). Tato transformace plnˇe zachovává p˚ uvodn´ı tvar objektu, spolu se stˇredn´ı osou mus´ıme vˇsak uchovat i polomˇer vznikl´ ych hyperkoul´ı. Sluˇs´ı se poznamenat, ˇze aˇckoli disponujeme elegantn´ı definic´ı stˇredn´ı osy, vyuˇzit´ı jej´ı surové podoby nen´ı pˇr´ıliˇs ˇza´douc´ı. Zaprvé, hledán´ı stˇredn´ı osy je v´ ypoˇcetnˇe nároˇcný u ´kon, zadruhé, výsledná kˇrivka je obt´ıˇznˇe parametrizovatelná. Jako posledn´ı bod zmiˇ nme, ˇze tvorba stˇredn´ı osy je vysoce citlivá na ˇsum na povrchu objektu – sebedrobnˇejˇs´ı nuance tvoˇr´ı nové vˇetve stˇredn´ı osy. Stˇredn´ı osu lze aproximovat pomoc´ı po ˇca´stech lineárn´ım skeletem tvoˇreného vnitˇrn´ımi póly Voroného diagram˚ u. Techniku detailnˇe rozeb´ırá Amenta et al. [3] za u ´ˇcelem rekonstrukce povrchu z navzorkovaných bod˚ u. Mezi dalˇs´ı aplikace stˇredn´ı osy patˇr´ı napˇr´ıklad strukturn´ı popis objekt˚ u.

2.2

Metody zaloˇ zen´ e na geometrii a topologii

V tomto pˇr´ıpadˇe nijak nemˇen´ıme charakter vstupn´ıch dat, bˇehem výpoˇctu vyuˇz´ıváme vstupn´ı troj´ uheln´ıkovou s´ıt’. D´ıky tomu m˚ uˇzeme uˇsetˇrit v´ ypoˇcetn´ı ˇcas, kter´ y bychom museli vˇenovat pˇr´ıpadné konverzi reprezentace dat.

2.2.1

Smrˇ stˇ en´ı modelu s n´ aslednou redukc´ı geometrie

ˇ sen´ı problému, které navrhuje Au et al. [4], se sestává z nˇekolika fáz´ı. Nejprve Reˇ iterativnˇe smrˇst’ujeme troj´ uheln´ıkovou s´ıt’, po dosaˇzen´ı urˇceného objemu pˇricház´ı na ˇradu redukce geometrie, pˇriˇcemˇz vzniká jednorozmˇerná kostra objektu. Na závˇer provedeme u ´pravu pozic vrchol˚ u kostry.

Smrˇ stˇ en´ı s´ıtˇ e Bˇehem smrˇst’ován´ı s´ıtˇe docház´ı k vyhlazován´ı detail˚ u a posunu vrchol˚ u proti ˇ smˇeru vypoˇctené normály. Reˇs´ıme pˇreurˇcenou soustavu rovnic 2.6 pro neznám´ y

5



vektor pozic V 0 , po jeho nalezen´ı pˇriˇrad´ıme V ← V 0 a v´ ypoˇcet opakujeme, dokud nen´ı dosaˇzena zastavuj´ıc´ı podm´ınka. " # WL L WH

" V0 =

0

#

WH V

(2.6)

Popiˇsme si význam jednotlivých ˇclen˚ u soustavy. Vektor V znaˇc´ı vˇsechny aktuáln´ı pozice vrchol˚ u s´ıtˇe, V0 pozice nové, hledané. Diagonáln´ı matice WL (vynucuj´ıc´ı setrván´ı v pozici) a WH (zesiluj´ıc´ı kontrakci) zanáˇsej´ı do v´ ypoˇctu potˇrebné váhy. Matice L provád´ı diskrétn´ı laplaceovské vyhlazován´ı“ proti smˇeru normály a je ” definována následovnˇe:

Lij

 ωij = cotg αij + cotg βij   P = (i,k)∈E −ωik   0

je-li (i, j) hranou mezi vrcholy vi a vj je-li i = j v jiném pˇr´ıpadˇe (2.7)

pˇriˇcemˇz u ´hly αij a βij jsou protilehlé u ´hly v˚ uˇci hranˇe (i, j). Jak jiˇz bylo ˇreˇceno, ˇreˇsen´ı soustavy mus´ıme opakovat, jedna iterace k ˇreˇsen´ı nestaˇc´ı. Za zastavovac´ı podm´ınku autoˇri ˇclánku vol´ı dosaˇzen´ı -násobku p˚ uvodn´ıho objemu, pˇr´ıpadnˇe pˇrekroˇcen´ı maximáln´ıho moˇzného poˇctu krok˚ u (ˇreˇsen´ı soustavy rovnic).

Obrázek 2.8: Smrˇst’ován´ı modelu. Konektivita p˚ uvodn´ı geometrie je zachována.

6


Metody zaloˇzené na geometrii a topologii (0)

(0)

V ˇclánku doporuˇcuj´ı váhy na poˇca´tku nastavit na hodnoty WH = 0 a WL = √ ´ 10−3 A. Uprava vah prob´ıhá po kaˇzdém kroku: (t+1)

WL

(t+1)

WH,i

(t)

← sL WL , pˇriˇcemˇz doporuˇcená hodnota sL = 2 s (0) Ai (t) ← WH,i , kde Ai pˇredstavuje plochu one-ring kolem vrcholu i (t) Ai (2.9)

Pr˚ ubˇeh kontrakce s´ıtˇe je znázornˇen na obrázku 2.22, pro názornost byly vynechány d´ılˇc´ı iterace.

Redukce geometrie Smrˇstˇená s´ıt’ si zachovává svoji p˚ uvodn´ı konektivitu, k dosaˇzen´ı jednorozmˇerné kostry pouˇzijeme redukci geometrie pomoc´ı half-edge collapse. Tento postup lze popsat tak, ˇze vybereme nejménˇe významnou hranu (i, j), kterou ze s´ıtˇe odstran´ıme (viz obrázek 2.10). Vrchol vi je poté ztotoˇznˇen s vrcholem vj a dojde k odstranˇen´ı stˇen inciduj´ıc´ıch s hranou (i, j). Hrany odeb´ıráme opakovanˇe do dosaˇzen´ı zastavovac´ı podm´ınky.

vi 4

1 e

3

2

1+2

vj

3+4

vi + vj

Obrázek 2.10: Half-edge collapse. Vrchol vi je ztotoˇznˇen s vj , hrana e je odstranˇena spolu s inciduj´ıc´ımi troj´ uheln´ıky. Sluˇcován´ı hran je popsáno v obrázku pomoc´ı ˇc´ıslován´ı v obrázku. Ohodnocen´ı hrany stanov´ıme jako váˇzen´ y souˇcet d´ılˇc´ıch funkc´ı: F (i, j) = wa Fa (i, j) + wb Fb (i, j)

doporuˇceno: wa = 1, wb = 0.1

7

(2.11)



Funkce Fa (i, j) vyjadˇruje m´ıru chyby vzniklé odstranˇen´ım hrany (i, j):

Fa (i, j) = F (vj , i) + F (vj , j)

(2.12)

X

(2.13)

pˇriˇcemˇz: F (vj , i) = vjT

(KTij Kij )vj

(i,j)∈E



−az

0

 Kij =  az −ay

0

−bx

ay



 −ax −by 

ax

(2.14)

−bz

0

kde a je normalizovan´ ym vektorem hrany (i, j) a b = a × vi a E pˇredstavuje mnoˇzinu hran s´ıtˇe (viz obrázek 2.15). Pˇredpokládáme, ˇze vi neleˇz´ı v poˇcátku soustavy souˇradnic, jinak vyjde vektor b nulov´ y.

vi

b a

O

vj

Obrázek 2.15: Znázornˇen´ı vektorového souˇcinu b = a×vi , bod O pˇredstavuje poˇcátek soustavy souˇradnic. Vektor b je kolm´ y k a i vi . Funkce Fb (i, j) pokutuje délku hrany (i, j):

Fb (i, j) = kvi − vj k

X

kvi − vk k

(2.16)

(i,k)∈E

Bˇehem redukce udrˇzujeme vazbu redukované geometrie na p˚ uvodn´ı objekt. Pro poˇca´teˇcn´ı stav je triviáln´ı jej nastavit, v kaˇzdém vrcholu vi vytvoˇr´ıme seznam obsahuj´ıc´ı právˇe tentýˇz vrchol (vi ). Pˇri redukci hrany vi vj seznamy vrchol˚ u slouˇc´ıme a uloˇz´ıme do vj . Takto postupnˇe tvoˇr´ıme mapován´ı, které pˇriˇrazuje vrcholu kostry mnoˇzinu pˇr´ısluˇsn´ ych vrchol˚ u p˚ uvodn´ı geometrie.

8



Z´ avˇ ereˇ cn´ au ´ prava pozic Z pˇredchoz´ıho kroku jsme z´ıskali podmnoˇzinu vrchol˚ u reprezentuj´ıc´ı kostru objektu, jej´ıˇz pozice vˇsak mus´ıme dodateˇcnˇe upravit. Vrcholy kostry se totiˇz nemusej´ı nutnˇe nacházet uvnitˇr modelu. Proto docház´ı k závereˇcné u ´pravˇe, jeˇz pˇresune vrcholy kostry smˇerem doprostˇred objemu tvoˇreného s´ıt´ı. Vyuˇzijeme mapován´ı kostry na s´ıt’, které vzniklo v pˇredchoz´ım kroku. K vrcholu kostry u s pomoc´ı mapován´ı z´ıskáme mnoˇzinu pˇr´ısluˇsn´ ych vrchol˚ u vi , která je ohraniˇcena N hranicemi ξk . Korekce pozice vrcholu kostry u je dána jako: u =u−

N X dk k

0 i∈ξk lk,i (vi

P dk =

P

(2.17)

N − vi )

i∈ξk lk,i

(2.18)

kde dk pˇredstavuje d´ılˇc´ı pˇr´ıspˇevek dan´ y vrcholy hranice ξk , vi0 pozici vrcholu po smrˇstˇen´ı s´ıtˇe a lk,i souˇcet délek hran inciduj´ıc´ıch s vrcholem vi , které mus´ı zároveˇ n patˇrit do hranice ξk . Autoˇri pˇriznávaj´ı, ˇze ne pro kaˇzdou s´ıt’ závˇereˇcná u ´prava pozic skuteˇcnˇe pˇrem´ıst´ı vrcholy kostry dovnitˇr modelu. V ˇclánku nezmiˇ nuj´ı, o kolik je zvolen´ y postup lepˇs´ı neˇz pouˇzit´ı obyˇcejného centroidu.

Klady a z´ apory metody Na metodˇe ocen´ıme zejména robustnost v˚ uˇci ˇsumu, nebot’ bˇehem kontrakce s´ıtˇe pomoc´ı diskrétn´ıho laplaciánu docház´ı k jej´ımu vyhlazován´ı. Tvorba kostry je neteˇcná v˚ uˇci rotaci objektu (jako jeden z d˚ uvod˚ u uved’me, ˇze pracujeme s p˚ uvodn´ı s´ıt´ı, ne s diskretizovanou reprezentac´ı v podobˇe voxelové mˇr´ıˇzky). Citelnou nevýhodou je výpoˇcetn´ı nároˇcnost, ostatnˇe pˇri výpoˇctu opakovanˇe ˇreˇs´ıme rozsáhlou pˇreurˇcenou soustavu rovnic. Právˇe tento krok zp˚ usobuje, ˇze v´ ysledná v´ ypoˇcetn´ı algoritmická sloˇzitost je O(IC N 3 ), kde N znaˇc´ı poˇcet vrchol˚ u a IC poˇcet iterac´ı. Nastavitelné parametry se mus´ı volit ruˇcnˇe dle s´ıtˇe, která se nacház´ı na vstupu – ˇclánek nepopisuje vhodnou automatickou volbu, doporuˇcuje osvˇedˇcené“ ” hodnoty. 9


2.2.2


Tvorba kostry spojov´ an´ım v´ yznamn´ ych bod˚ u

ˇ anek od Jaehwan Ma a Sunghee Choi [11] se zaob´ırá tvorbou kostry pˇr´ımo pro Cl´ animaˇcn´ı u ´ˇcely, pˇri generován´ı vznikaj´ı zámˇernˇe dlouhé kosti, nikoliv sada drobných (na rozd´ıl od metody od Au et al. popsané v kapitole ), které bychom museli dodateˇcnˇe na závˇer spojovat. Shrˇ nme si nejdˇr´ıve princip v nˇekolika vˇetách. Nejprve jsou nalezeny v´ yznaˇcné vrcholy s´ıtˇe, ˇr´ıkejme jim kandidáti na listy kostry. Mezi nimi se vyskytuj´ı i takové body, které vznikly kv˚ uli ˇsumu na povrchu s´ıtˇe, proto docház´ı k filtrován´ı kandidát˚ u. Poté zapoˇcne generován´ı kost´ı smˇerem od list˚ u k prozat´ım neznámemu koˇrenu a jejich spojován´ı v kostru. Následuj´ı závˇereˇcné u ´pravy: pˇridán´ı dodateˇcných vnitˇrn´ıch bod˚ u kostry a um´ıstˇen´ı koˇrene kostry.

Pˇ redzpracov´ an´ı dat Autoˇri pouˇzili svoji vlastn´ı metodu hledán´ı aproximace stˇredn´ı osy objektu (Ma et. al, 2012 [10]) k nalezen´ı maximáln´ı teˇcn´ ych koul´ı (tangent balls) v˚ uˇci troj´ uheln´ıkové s´ıti ve vˇsech jeho vrcholech (viz obrázek 2.19). Velikost teˇcné koule pˇr´ısluˇs´ıc´ı vybranému vrcholu je pouˇzita ve v´ ypoˇctu pozdˇeji. v1 v2

v3

m

B1 B2

B3

Obrázek 2.19: Ukázka teˇcn´ ych koul´ı Bi na ˇca´sti s´ıtˇe (vrcholech vi ), m znaˇc´ı odhad stˇredn´ı osy. Stˇred koule leˇz´ı na v pˇr´ısluˇsném vrcholu stˇredn´ı osy (kter´ y odpov´ıdá pólu Voronoi diagramu), polomˇer je volen tak, aby vrchol vi leˇzel na jej´ım povrchu. Pro názornost znázornˇeno ve dvourozmˇerné analogii.

10



Hled´ an´ı v´ yznaˇ cn´ ych vrchol˚ u V´ yznaˇcné vrcholy jsou chápány jako lokálnˇe nejvzdálenˇejˇs´ı vrcholy vzhledem k ostatn´ım v s´ıti. Intiutivnˇe bychom je mohli popsat jako zakonˇcen´ı modelu“. ” Pohybovat se m˚ uˇzeme pouze po hranách s´ıtˇe, t´ım pádem se jedná o grafovou u ´lohu. Nejprve zvol´ıme libovoln´ y vrchol s´ıtˇe vr , ze kterého provedeme ˇca´st známého Dijkstrova algoritmu pro hledán´ı cesty (algoritmická sloˇzitost pˇri pouˇzit´ı binárn´ı haldy a pˇredpokladu rovinného grafu, ve kterém poˇcet hran lineárnˇe závis´ı na poˇctu vrchol˚ u, je O(N log(N )), kde N znaˇc´ı poˇcet vrchol˚ u), tj. vzdálenostn´ı ohodnocen´ı vrchol˚ u. Nejv´ yˇse ohodnocen´ y v0 se stává prvn´ım kandidátem na v´ yznaˇcn´ y vrchol. Jako dalˇs´ı krok opˇet spust´ıme Dijsktr˚ uv algoritmus, ale tentokrát zaˇcneme ve vrcholu v0 . Kandidáty se stávaj´ı vˇsechny vrcholy, pro které plat´ı, ˇze jejich vzdálenostn´ı ohodnocen´ı je vyˇsˇs´ı neˇz ohodnocen´ı jejich libovolného souseda. Z´ıskané body se mohou nacházet mezi kandidáty napˇr´ıklad kv˚ uli ˇsumu na povrchu s´ıtˇe. Vrchol odstran´ıme ze seznamu kandidát˚ u v pˇr´ıpadˇe, ˇze ˇsumem zp˚ usoben´ y v´ yˇcnˇelek s´ıtˇe, kterému vrchol náleˇz´ı, je mˇelˇc´ı neˇz zvolen´ y práh. Pokud se v jednom v´ yˇcnˇelku nacház´ı v´ıce kandidát˚ u, akceptujeme z nich jen takov´ y vrchol, kterému pˇr´ısluˇs´ı nejmenˇs´ı teˇcná koule.

Tvorba kostry Kostru tvoˇr´ıme opakován´ım dvou krok˚ u: odˇrezáván´ım a sluˇcován´ım vˇetv´ı vznikaj´ıc´ı kostry (viz n´ıˇze). D´ılˇc´ı kroky si ve struˇcnosti pˇredstav´ıme. Od vˇsech v´ yznaˇcn´ ych vrchol˚ u vi zaˇcneme pseudoparalelnˇe tvoˇrit vˇetve grafu kostry. To provedeme tak, ˇze z kaˇzdého vrcholu vj spust´ıme Dijkstr˚ uv algoritmus, ˇc´ımˇz vypoˇcteme ostatn´ım vrchol˚ um s´ıtˇe vzdálenost od vj . Poté uniformnˇe navzorkujeme izoˇcáry, které pˇredstavuj´ı mnoˇzinu bod˚ u stejnˇe vzdálených od vi . V metodˇe byl pouˇzit odhad, kdy m´ısto pˇresných izoˇcar byly pouˇzity jejich odhady (vzorkován´ı bylo provedeno na hranách s´ıtˇe a body stejné vzdálenosti byly propojeny do po ˇcástech lineárn´ı uzavˇrené kˇrivky). Izoˇca´ry c oindexujeme podle vzdálenosti od v´ yznaˇcného vrcholu a oznaˇc´ıme je cj . Pokud plat´ı, ˇze |cj+1 | > |cj |, kde |cj | znaˇc´ı poˇcet samostatných izoˇcar stejné u ´rovnˇe, pak doˇslo k topologickému rozdˇelen´ı. V tˇechto m´ıstech se nav´ıc velmi rychle mˇen´ı charakteristika izoˇcáry (stˇredn´ı pr˚ umˇer a rozptyl). 11



Právˇe zde vytvoˇr´ıme nový vrchol, který propoj´ıme s význaˇcným. Pˇr´ısluˇsnou vˇetev kostry t´ımto povaˇzujeme za dokonˇcenou. M˚ uˇze doj´ıt ke slouˇcen´ı s jinou vˇetv´ı, je-li nalezena izoˇcára s podobnou charakteristikou (pro tento u ´ˇcel je vytvoˇren nový vrchol). V opaˇcném pˇr´ıpadˇe v´ ypoˇcet pokraˇcuje v generován´ı izoˇca´r jiné vˇetve modelu. Za zm´ınku stoj´ı, ˇze se v pr˚ ubˇehu algoritmu upˇrednostˇ nuj´ı tenké“ vˇetve modelu (maj´ıc´ı ” nejmenˇs´ı stˇredn´ı pr˚ umˇer izoˇcar) a ˇze velmi d˚ uleˇzitou roli v algoritmu hraje hustota vzorkován´ı izoˇcar (pˇr´ıliˇs velká klade vyˇsˇs´ı výpoˇcetn´ı nároky, pˇr´ıliˇs n´ızká znemoˇzn ˇuje správn´ y chod algoritmu).

Z´ avˇ ereˇ cn´ eu ´ pravy Kaˇzdá vˇetev s´ıtˇe obsahuje nyn´ı pouze jednu kost, která se pne od v´ yznaˇcného vrcholu ke spoji s jinými kostmi (sourozenci a nadˇrazený pˇredek). Do kostry vkládáme vrcholy stˇredn´ı osy objektu maj´ıc´ı od n´ı nejvˇetˇs´ı odchylku. Tento proces opakujeme, dokud vkládán´ı zp˚ usobuje zmˇeny vyˇsˇs´ı, neˇz byl stanoven práh. Posledn´ım krokem je urˇcen´ı pozice koˇrene kostry. Veˇskeré d´ılˇc´ı vˇetve jsou v tento moment odˇrezány, zbyla nám mnoˇzina vrchol˚ u (v ˇclánku oznaˇcené jako root region), z jejichˇz pozic vypoˇcteme váˇzen´ y centroid, pˇriˇcemˇz jako váhy pouˇzijeme polomˇery pˇr´ısluˇsn´ ych teˇcn´ ych koul´ı.

Klady a z´ apory metody Algoritmus produkuje kostru, která je dostateˇcnˇe jednoduchá, abychom ji mohli pouˇz´ıt k animaci objektu. Stejnˇe jako u v´ yˇse popsané metody od Au et al. (viz sekce 2.2.1) je tvorba neteˇcná v˚ uˇci rotaci objektu ˇci jeho póze. Vzhledem k tomu, jak je tvoˇrena hierarchie kost´ı (od list˚ u smˇerem ke koˇreni), má v´ ysledná kostra hvˇezdicovitou“ podobu, kosti se sb´ıhaj´ı do koˇrene. Sami autoˇri ˇclánku pˇriznávaj´ı, ˇze ” to m˚ uˇze bránit praktickému vyuˇzit´ı algoritmu pro generován´ı koster humanoid˚ u. Podle autor˚ u nejvˇetˇs´ı v´ ypoˇcetn´ı zátˇeˇz tvoˇr´ı právˇe stavba kostry (nikoliv prvotn´ı hledán´ı v´ yznaˇcn´ ych bod˚ u). V´ ypoˇcetn´ı sloˇzitost algoritmu závis´ı nejen na poˇctu vrchol˚ u, ale i na pouˇzité hustotˇe vzorkován´ı a topologické sloˇzitosti modelu (kde docház´ı k v´ıce sluˇcován´ı d´ılˇc´ıch vˇetv´ı). Vyˇc´ıslená sloˇzitost O(q c(i) N logE) odpov´ıdá procházen´ı rovinného grafu, kdy v kaˇzdém kroku i srovnáváme mˇen´ıc´ı se poˇcet izoˇcar c, N znaˇc´ı poˇcet vrchol˚ u, E poˇcet hran, q hustotu vzorkován´ı. 12


Volumetrické metody

Za pˇredpokladu, ˇze délky hran jsou srovnatelné, m˚ uˇzeme zvolit parametr q tak, abychom navzorkovali izoˇca´rou kaˇzdou hranu pˇribliˇznˇe jednou. Potom m˚ uˇzeme výpoˇcetn´ı sloˇzitost vyjádˇrit jako O(E N logE). Hrany povrchu s´ıtˇe vˇsak tvoˇr´ı rovinný graf, jejich poˇcet je tedy lineárnˇe závisl´ y na poˇctu vrchol˚ u N , coˇz nám umoˇzn´ı závˇereˇcné zjednoduˇsen´ı sloˇzitosti: O(N 2 logN ). Nezapomeˇ nme vˇsak, ˇze k tomuto pˇredpisu jsme dospˇeli po zm´ınˇeném zjednoduˇsuj´ıc´ım pˇredpokladu.

2.3

Volumetrick´ e metody

Pˇred pouˇzit´ım volumetrick´ ych metod docház´ı k diskretizaci objektu: nahrad´ıme p˚ uvodn´ı objem voxely (obecn´ ym rozˇs´ıˇren´ım pixelu pro prostor), které pˇredstavuj´ı plný prostor. Vzniklý diskretizovaný objekt ztenˇcujeme odeb´ırán´ım hraniˇcn´ıch voxel˚ u. Poˇrad´ı jejich odeb´ırán´ı urˇcuje prioritn´ı funkce, která se v r˚ uzn´ ych metodách liˇs´ı. Stejnˇe tak se rozcház´ı definice hraniˇcn´ıch voxel˚ u ku pˇr´ıkladu z d˚ uvodu pouˇzit´ı rozd´ılné sousednosti (6-okol´ı apod.). Jako pˇr´ıklad ztenˇcován´ı uved’me metodu od Ma et al. [9]. Nev´ yhodou metod zaloˇzen´ ych na ztenˇcován´ı je nemoˇznost práce se surov´ ymi vstupn´ımi daty, nutnost volby hustoty mˇr´ıˇzky a vysoká citlivost na ˇsum, z vytvoˇrené kostry mus´ıme odstraˇ novat bezv´ yznamné vˇetve.

Obrázek 2.20: Ukázka iterac´ı ztenˇcován´ı modelu reprezentovaného voxely. Zdroj: http://csvision.swan.ac.uk/index.php?n=Site.BloodFlowModelling, cit. 6. 2015. Obdobnˇe nerobustn´ı chován´ı (podle Au et al. [4]) maj´ı i metody zaloˇzené na distanˇcn´ım poli (distance field methods), u kterých kaˇzdému voxelu pˇriˇrad´ıme hodnotu 13


Volumetrické metody

odpov´ıdaj´ıc´ı vzdálenosti od hranice objektu. Lokáln´ı maxima reprezentuj´ı kandidáty, jejichˇz spojen´ım z´ıskáme aproximaci stˇredn´ı osy objektu. Pˇri porovnán´ı s geometrick´ ymi metodami, které byly rozebrány v´ yˇse, trp´ı volumetrické metody nˇekolika nepˇrehlédnuteln´ ymi problémy: 1. Geometrická data vyˇzaduj´ı pˇrevod do voxelové reprezentace, nejsou-li jiˇz na vstupu v této podobˇe. 2. Pˇri konverzi mus´ıme vhodnˇe zvolit hustotu voxelové mˇr´ıˇzky. 3. Voxelová reprezentace je zpravidla pamˇet’ovˇe nároˇcnˇejˇs´ı oproti geometrické.

2.3.1

Generov´ an´ı kostry sn´ıman´ eho ˇ clovˇ eka v re´ aln´ em ˇ case

Straka et. al [14] sn´ımali ˇclovˇeka nˇekolika kamerami a v reálném ˇcase byli schopni vypoˇc´ıtat jeho kostru. Sn´ımán´ım z´ıskali pˇribliˇznou volumetrickou reprezentaci osoby, ze které metodou volume scooping [13] vypoˇc´ıtali pˇribliˇznou podobu stˇredn´ı osy objektu. Na prvn´ı pohled se m˚ uˇze zdát, ˇze jsme se ocitli v oblasti strojového vidˇen´ı, principy extrakce kostry vˇsak z˚ ustáváj´ı stejné a m˚ uˇzeme je vyuˇz´ıt pro data libovolného p˚ uvodu. Stˇredn´ı osu nen´ı moˇzné pouˇz´ıt pˇr´ımo jako kostru objektu, nebot’ je zat´ıˇzena nepˇresnostmi – oproti poˇzadovanému stavu obsahuje nadbyteˇcné kosti. Algoritmu proto dodáme tzv. vzorovou kostru S, podle n´ıˇz se doˇcasnˇe vypoˇctená kostra uprav´ı. Vzor velmi zjednoduˇsenˇe reprezentuje ˇclovˇeka, napˇr´ıklad celá paˇze vˇcetnˇe pˇredlokt´ı je reprezentována pouh´ ymi dvˇema kostmi se spoleˇcn´ ym kloubem v lokti. Vzorová kostra S i doˇcasnˇe vypoˇc´ıtaná kostra X jsou obˇe vlastnˇe grafem, pro který urˇc´ıme distanˇcn´ı matici, která poslouˇz´ı v následuj´ıc´ıch výpoˇctech jako metrika pro výpoˇcet chyby pˇriˇrazen´ı dvojic vrchol˚ u z X a S. Následnˇe se zamˇeˇr´ıme na koncové vrcholy E(X) a E(S) (listy grafu), pˇriˇcemˇz chceme nalézt pˇriˇrazen´ı:

f (E(S)) → f (E(X))

(2.21)

takové, ˇze v´ ysledná chyba je minimáln´ı. Autoˇri jej hledaj´ı kombinac´ı dynamic time 14


Pˇr´ıbuzné oblasti

warping (DTW, pouˇzita kv˚ uli moˇznosti rozd´ılného poˇctu koncov´ ych vrchol˚ u) a mad’arské metody (pˇriˇrazen´ı dvojic s nejmenˇs´ı globáln´ı chybou). Obdobným zp˚ usobem jsou spárovány vnitˇrn´ı klouby. D´ıky tomu m˚ uˇzeme vzorovou kostru vloˇzit do skenovaného modelu a provést uˇz jen závˇereˇcné u ´pravy pozic (viz p˚ uvodn´ı ˇclánek). Nesporná v´ yhoda, která se v metodˇe ukr´ yvá, je znemoˇznˇen´ı tvorby nesmyslné topologie kostry (pˇr´ıdavné konˇcetiny apod.). Algoritmus m˚ uˇze selhat a pˇriˇradit k sobˇe ˇspatné dvojice kloub˚ u z koster S a X, poˇzadovaná topologie je vˇsak vˇzdy zachována. Aˇckoliv autoˇri svoji metodu pouˇzili pro volumetrická vstupn´ı data, nic nebrán´ı nasazen´ı vstupu v podobˇe troj´ uheln´ıkové s´ıtˇe, tj. nahradit krok tvorby doˇcasné kostry (odhadu stˇredn´ı osy).

2.4

Pˇ r´ıbuzn´ e oblasti

Metoda od Yoshizawa et al. [16] se zab´ yvá generován´ım kostry v ponˇekud jiné podobˇe neˇz doposud zm´ınˇené pˇr´ıstupy. Kostru pˇredstavuje odhad stˇredn´ı osy s´ıtˇe vypoˇc´ıtan´ y pomoc´ı pól˚ u Voroného diagramu, které jsou spojeny topologicky stejnˇe jako p˚ uvodn´ı troj´ uheln´ıková s´ıt’ [3]. P˚ uvodn´ı s´ıt’ byla v podstatˇe zdeformována do podoby stˇredn´ı osy, k ˇzádné redukci na jednorozmˇern´ y graf zde nedocház´ı. Pro potlaˇcen´ı ˇsumu doporuˇcuj´ı autoˇri vstupn´ı model nejprve zjednoduˇsit.

Obrázek 2.22: Ukázka v´ ysledk˚ u metody Yoshizawa et al. Uvnitˇr modelu se nacház´ı vygenerovan´ y skelet, kter´ y pˇrenáˇs´ı deformaci ruˇcnˇe vytvoˇrené jednorozmˇerné kostry na povrch tˇelesa. 15


Pˇr´ıbuzné oblasti

Po aplikaci libovoln´ ych free-form deformac´ı na vzniklou s´ıt’ stˇredn´ı osy m˚ uˇzeme zrekonstruovat p˚ uvodn´ı objekt se zachován´ım lokáln´ı tlouˇst’ky, coˇz vypl´ yvá z vlastnost´ı medial axis transform. Byla-li p˚ uvodn´ı s´ıt’ pˇred transformac´ı zjednoduˇsena, docház´ı k opˇetovnému zesloˇzitˇen´ı s uˇzit´ım diskétn´ıch diferenciáln´ıch souˇradnic. Skelet, kter´ ym se ˇr´ıd´ı tvarován´ı objektu, nevyuˇzijeme pˇr´ımo, nebot’ je sloˇzen ze stejného poˇctu vrchol˚ u, kter´ y mˇela p˚ uvodn´ı s´ıt’, jen se nacházej´ıc´ı bl´ızko stˇredn´ı osy. Nedosáhli bychom tak ˇza´dného zjednoduˇsen´ı. Autoˇri proto pouˇz´ıvaj´ı ruˇcnˇe vytvoˇrenou (jednorozmˇernou) kostru, kterou ˇr´ıd´ı deformaci generovaného skeletu.

16

3 Pˇr´ımá a inverzn´ı kinematika V pˇredchoz´ı kapitole jsme popsali metody, které slouˇz´ı ke generován´ı kostry. Obohat´ıme-li vzniklou kostru o vhodná omezen´ı pohybu v kloubech (viz n´ıˇze), m˚ uˇzeme ji rozhýbat a animovat p˚ uvodn´ı model. Jeden ze zp˚ usob˚ u animace je vyuˇzit´ı tzv. inverzn´ı kinematiky. Kostra objekt˚ u pˇredstavuje otevˇrenou hierarchickou segmentovou strukturu, ve které bod poloˇzený nejvýˇse v hierarchii bývá pevnˇe ukotven. Volné listy v hierarchii nazveme koncové efektory. Polohu volného tˇelesa v prostoru lze urˇcit pomoc´ı zvoleného souˇradnicového systému a ˇsesti ˇc´ısel, takzvan´ ymi stupni volnosti. Uvaˇzujeme-li systém tˇeles, poˇcet stupˇ n˚ u volnosti roste s jejich pˇridaným poˇctem. Takový systém m˚ uˇze ovˇsem obsahovat r˚ uzná omezen´ı pohybu (vazby mezi objekty, klouby), která naopak sn´ıˇz´ı v´ ysledn´ y poˇcet stupˇ n˚ u volnosti. Na obrázku 3.1 je znázornˇen pˇr´ıklad systému se dvˇema stupni volnosti, jehoˇz celkový stav lze popsat vektorem (α, β). Délka vektoru odpov´ıdá poˇctu stupˇ n˚ u volnosti soustavy, pˇriˇcemˇz poloha koncového efektoru je urˇcena stavov´ ym vektorem jednoznaˇcnˇe. Inverzn´ı kinematika se zab´ yvá urˇcen´ım stavového vektoru na základˇe zadané pozice koncového efektoru a sady omezen´ı pohybu. O základech této problematiky ˇ ara et al. [5], podrobnˇeji Goliáˇs ve své diplomové práci [8]. pojednává napˇr. Z´

β

X

α

Obrázek 3.1: Pˇr´ıklad segmentové struktury se dvˇema stupni volnosti. Koncový efektor je oznaˇcen p´ısmenem X.

17

Pˇr´ımá a inverzn´ı kinematika

3.1

Pˇr´ımá kinematika

Pˇ r´ım´ a kinematika

Pˇr´ımá kinematika slouˇz´ı k výpoˇctu pozice koncového efektoru na základˇe zadaného vstupn´ıho stavového vektoru θ. Vztah lze vyjádˇrit rovnost´ı:

X = f (θ)

(3.2)

kde X znaˇc´ı pozici koncového efektoru a f pouˇzité zobrazen´ı. Pˇr´ımá kinematika se nehod´ı k interaktivn´ım animac´ım, nasazuje se v pˇr´ıpadech, kdy známe ˇcasov´ y pr˚ ubˇeh stavového vektoru θ. Jako pˇr´ıklady vyuˇzit´ı pˇr´ımé kinematiky, které souvisej´ı s animaˇcn´ı kostrou, uved’me:

• Motion capture, tj. zaznamenán´ı pohybu reálného tˇelesa v m´ıstech bl´ızk´ ych jednotliv´ ym kostem a následné pˇrepoˇc´ıtán´ı stavového vektoru θ. • Mesh-skinning, tj. potaˇzen´ı kostry troj´ uheln´ıkovou s´ıt´ı, kdy na základˇe stavového vektoru θ urˇcujeme v´ ysledné pozice povrchu.

3.2

Inverzn´ı kinematika

S pomoc´ı inverzn´ı kinematiky, jak jiˇz bylo v´ yˇse ˇreˇceno, se snaˇz´ıme o urˇcen´ı stavového vektoru θ na základˇe zadané pozice X koncového efektoru. Formálnˇe bychom tuto pˇredstavu mohli zapsat vztahem:

θ = f −1 (X)

(3.3)

Na rozd´ıl od pˇr´ımé kinematiky vˇsak nemus´ı existovat jednoznaˇcné ˇreˇsen´ı, v nˇekterých pˇr´ıpadech dokonce ˇzádné ˇreˇsen´ı neexistuje (viz obrázek 3.5). Právˇe z tohoto d˚ uvodu se zavád´ı omezen´ı volnosti pohybu v kloubech, abychom náleˇzitˇe zjednoduˇsili podobu stavového prostoru. I tak se nevyhneme singularitám, nav´ıc zobrazen´ı f nen´ı lineárn´ı a analytické ˇreˇsen´ı rovnosti prakticky nelze realizovat.

18


3.2.1


Linearizace pomoc´ı jakobi´ anu

Problém tedy ˇreˇs´ıme v linearizované podobˇe za pomoci jakobiánu. V takovém pˇr´ıpadˇe m˚ uˇzeme pˇredpokládat, ˇze v dostateˇcnˇe malém okol´ı bodu X plat´ı: 

∂f1 ∂θ1

  ∂f2  ∂θ  1 ∆X = Jf (θ)∆θ =   ..  .   ∂fm ∂θ1

∂f1 ∂θ2 ∂f2 ∂θ2

.. . ∂fm ∂θ2

···

∂f1 ∂θn

 

   ···  ..  ..  . .   ∂fm  · · · ∂θn ∂f2 ∂θn

∆θ1



     ∆θ2     .   .   .      ∆θn

(3.4)

X

X

Obrázek 3.5: Singulárn´ı pˇr´ıpady. Vlevo dvˇe ˇreˇsen´ı, vpravo u ´loha neˇreˇsitelná. Vektor ∆X je nám znám´ y – jedná se o rozd´ıl poˇzadované a aktuáln´ı pozice. V´ ypoˇcet zmˇeny ∆θ lze formálnˇe zapsat:

∆θ = Jf (θ)−1 ∆X

(3.6)

Matice Jf zpravidla nebude ˇctvercová, klasická inverze tud´ıˇz ani nem˚ uˇze b´ yt pouˇzita – pˇrikroˇc´ıme k tzv. pseudoinverzi obdéln´ıkové matice, kterou m˚ uˇzeme realizovat napˇr´ıklad pomoc´ı metody SVD (singular value decomposition) nebo vyjádˇren´ım (podle Mereditha a Maddocka [12])

Jf (θ)−1 = Jf (θ)T (Jf (θ)Jf (θ)T )−1 .

(3.7)

M´ısto pseudoinverze lze uˇz´ıt také transpozici jakobiánu, v takovém pˇr´ıpadˇe 19



realizujeme vlastnˇe numerické ˇreˇsen´ı vztahu metodou nejvˇetˇs´ıho spádu. Transpozice klade niˇzˇs´ı nároky na v´ ykon v kroc´ıch iterace, na druhou stranu v´ ypoˇcet ztrác´ı na numerické stabilitˇe. Výsledný algoritmus tak ˇci onak pracuje iterativnˇe, dokud nen´ı dosaˇzeno kýˇzené pozice koncového efektoru: 1. Vypoˇcti jakobián Jf (θ). 2. Vypoˇcti pseudoinverzi jakobiánu Jf (θ)−1 . 3. Vypoˇcti nové ∆X jako rozd´ıl c´ılové a aktuáln´ı pozice koncového efektoru. 4. Vypoˇcti zmˇenu vnitˇrn´ıho stavu ∆θ = Jf (θ)−1 ∆X. 5. Pˇriˇrad’ pro novou iteraci vnitˇrn´ı stav θ+1 = θ + α ∆θ, kde α pˇredstavuje ˇr´ıdic´ı konstantu rychlosti konvergence.

3.2.2

Cyclic coordinate descent

Minimalizaci chyby, tj. vzdálenosti koncového efektoru od jeho poˇzadované pozice, lze realizovat také metodou cyclic coordinate descent (CCD). Tento zp˚ usob ˇreˇsen´ı u ´lohy inverzn´ı kinematiky navrhli Wang a Chen [15]. Algoritmus stejnˇe jako pˇredchoz´ı metoda pracuje iterativnˇe, v kaˇzdé iteraci procház´ı hierarchii segment˚ u od koncového efektoru smˇerem ke koˇrenu. Kaˇzdému segmentu pˇr´ısluˇs´ı kloub, kter´ y ji propojuje s nadˇrazen´ ym segmentem. U kloubu provedeme zmˇenu hodnot popisuj´ıc´ı jeho konfiguraci, která minimalizuje vzdálenost koncového efektoru od zadané pozice (viz obrázek 3.8). Lokáln´ı u ´prava poté konˇc´ı a pˇresuneme se k nadˇrazenému segmentu. V aplikac´ıch docház´ı k ukonˇcen´ı v´ ypoˇctu po dosaˇzen´ı prahové hodnoty chyby nebo po stanoveném poˇctu iterac´ı, ˇreˇsen´ı totiˇz nemus´ı existovat a uˇzivatel by marnˇe ˇcekal na odezvu. Metoda se vyznaˇcuje pomˇernˇe rychlou konvergenc´ı v ˇra´du stovek iterac´ı, avˇsak hroz´ı uváznut´ı v lokáln´ım optimu. I pˇres zaveden´ı omezen´ı pohybu v kloubech m˚ uˇze metoda vygenerovat na rozd´ıl od výpoˇctu pomoc´ı jakobiánu velmi nepˇrirozený pohyb. Toto chován´ı je moˇzné redukovat, pokud nedovol´ıme zmˇenu hodnot pˇredstavuj´ıc´ı konfiguraci kloubu vˇetˇs´ı neˇz stanovený práh (v takovém pˇr´ıpadˇe upravujeme konfiguraci 20



o prahovou hodnotu), coˇz na druhou stranu m˚ uˇze zpomalit konvergenci algoritmu. Oproti v´ ypoˇctu pomoc´ı jakobiánu se CCD vyznaˇcuje jednoduˇsˇs´ı implementac´ı.

X

X

X

Obrázek 3.8: Ukázka jedné iterace metody cyclic coordinate descent.

3.2.3

Obohacen´ı o posuvn´ a spojen´ı

Posuvná spojen´ı (také posuvné klouby, anglicky nazývané prismatic joints) mimo jiné umoˇzn´ı realizovat pruˇzné segmenty kost´ı. T´ımto obohat´ıme segmentovou strukturu o dalˇs´ı stupeˇ n volnosti. Uvaˇzme vˇsak, ˇze po formáln´ı stránce z˚ ustává celý výpoˇcet stejn´ y, m˚ uˇzeme pouˇz´ıt v´ ypoˇcty popsané v´ yˇse, pokud zaneseme posuvná spojen´ı do stavového vektoru θ náleˇz´ıc´ıho segmentové struktuˇre. To je moˇzné napˇr´ıklad pouˇzit´ım DH-notace (Denavit–Hartenbergovy parametry [7], popsáno napˇr. v [5], podkapitola 18.2.2).

21

4 Návrh vlastn´ı metody Jak jiˇz bylo ˇreˇceno v u ´vodu práce, zamˇeˇrili jsme se na generován´ı koster humanoid˚ u pro u ´ˇcely animace. D´ıky tomu lze vydedukovat nˇekteré poˇzadavky na vlastnosti kostry. • Kostra topologicky odpov´ıdá stavbˇe humanoida, vstupuje do konˇcetin a hlavy. Pˇredpokládáme humanoida se dvˇema nohama i paˇzemi, v m´ıstˇe hrudn´ıho koˇse je zachycena pouze páteˇr. • Poˇcet kost´ı nen´ı zbyteˇcnˇe vysoký. To by výtvarn´ıkovi znesnadˇ novalo rozanimován´ı modelu, vyˇzadovalo ukládán´ı vˇetˇs´ıho mnoˇzstv´ı dat a kladlo vyˇsˇs´ı nároky na v´ ykon pˇri pˇrehráván´ı animace. • Kostra leˇz´ı alespoˇ n pˇribliˇznˇe uvnitˇr vstupn´ı s´ıtˇe. • Kostra obsahuje omezen´ı na volnost pohybu v kloubech.

4.1

Generov´ an´ı kostry

ˇ adná z metod prozkouman´ Z´ ych v kapitole 2 pˇr´ımo neodpov´ıdá naˇs´ı situaci. Vygenerovat rozumná omezen´ı na volnost pohybu v kloubech ˇcistˇe geometrickou interpretac´ı kostry a s´ıtˇe je velmi obt´ıˇzný, ne-li nemoˇzný u ´kol. Jako vhodnˇejˇs´ı se jev´ı vyuˇz´ıt znalosti, ˇze vstupn´ı s´ıt’ reprezentuje humanoida, a pˇripravit vzor obsahuj´ıc´ı pˇribliˇznou podobu kostry vˇcetnˇe omezen´ı v kloubech. S pˇrihlédnut´ım k seznamu poˇzadavk˚ u a postˇreh˚ u navrhnˇeme koncept ˇreˇsen´ı, kter´ y kombinuje vybrané metody z kapitoly 2: 1. Pˇriprav´ıme si referenˇcn´ı kostru humanoida, která bude obsahovat i omezen´ı na volnost v kloubech. 2. Vygenerujeme kostru smrˇstˇen´ım troj´ uheln´ıkové s´ıtˇe s následnou redukc´ı na 1D graf (Au et al., viz podkapitola 2.2.1). Vzniklá prozat´ımn´ı kostra je vˇsak pˇr´ıliˇs detailn´ı.

22

Návrh vlastn´ı metody

Interaktivn´ı ukázka

3. Uˇzit´ım dynamic time warping a mad’arské metody spárujeme vrcholy (klouby) referenˇcn´ı a prozat´ımn´ı kostry. Jedná se o ˇcást metody od autor˚ u Straky et al. popsané v podkapitole 2.3.1. u kostry je ovlivnˇena 4. Referenˇcn´ı kostru vloˇz´ıme dovnitˇr s´ıtˇe. Pozice kloub˚ partnerskými“ klouby prozat´ımn´ı kostry a napˇr´ıklad pomˇery délek inciduj´ıc´ıch ” kost´ı. 5. Do vzniklé kostry zkop´ırujeme omezen´ı volnosti pohybu v kloubech obsaˇzené v referenˇcn´ı kostˇre. Pˇredpokládáme, ˇze vstupn´ı troj´ uheln´ıková s´ıt’ pˇredstavuje humanoida v klidové póze (rozpaˇzené ruce, plochy dlan´ı smˇeˇruj´ıc´ı vpˇred, spatný stoj).

4.2

Interaktivn´ı uk´ azka

Vlastnosti vzniklé kostry se projev´ı aˇz pˇri jej´ım vlastn´ım uˇzit´ı, tedy pˇri uveden´ı do pohybu. Z tohoto d˚ uvodu na v´ yˇse zm´ınˇené generován´ı, které bychom mohli oznaˇcit jako pˇredzpracován´ı (preprocessing), naváˇze interaktivn´ı vizualizace kostry. V pozic´ıch koncových efektor˚ u budou um´ıstˇeny kontroln´ı body, které uˇzivatel bude moci pˇretáhnout na jiné m´ısto. V tu chv´ıli dojde k aplikaci inverzn´ı kinematiky, která se vynasnaˇz´ı pˇribl´ıˇzit odpov´ıdaj´ıc´ı koncový efektor kýˇzené pozici. Z experimentáln´ıch d˚ uvod˚ u budou naimplementovány dvˇe verze algoritmu: 1. Inverzn´ı kinematika s pevn´ ymi kostmi nemˇenné délky. 2. Inverzn´ı kinematika s pruˇzn´ ymi kostmi, které se mohou libovolnˇe natahovat. Obˇe varianty budou respektovat omezen´ı volnosti pohybu v kloubech, která byla zkop´ırována z referenˇcn´ı kostry. Pˇri zmˇenˇe konfigurace kostry dojde k odpov´ıdaj´ıc´ı deformaci modelu humanoida.

23

5 Podrobný rozbor metody V kapitole 4 byl navrˇzen postup generován´ı kostry a následná demonstrace výsledku pomoc´ı interaktivn´ı vizualizace. Nyn´ı si rozebereme d´ılˇc´ı kroky podrobnˇeji. Pop´ıˇseme si algoritmy, jejich parametry a charakter dat, se kterými se na dané u ´rovni pracuje.

5.1

Vstupn´ı data

Model humanoida, kter´ y naˇcteme na poˇca´tku celého procesu, je reprezentován povrchovˇe pomoc´ı troj´ uheln´ıkové s´ıtˇe. Navrˇzená metoda tvorby kostry poˇzaduje, aby s´ıt’ byla manifoldn´ı (bl´ızké okol´ı libovolného bodu náleˇz´ıc´ıho s´ıti je homeomorfn´ı v˚ uˇci euklidovskému prostoru E 2 ). D´ıky tomu napˇr´ıklad m˚ uˇzeme uˇz´ıt jednoduˇsˇs´ı datové struktury ˇci korektnˇe spoˇc´ıtat objem uzav´ıraný s´ıt´ı. Pˇredpokládáme, ˇze humanoid ve scénˇe stoj´ı, je rozpaˇzen´ y a d´ıvá se ve smˇeru osy z.

y x z

Obrázek 5.1: Znázornˇen´ı rotac´ı kosti podle os x, y, z. Pouˇzit´ y lokáln´ı systém je pravotoˇciv´ y, smˇer osy y je ztotoˇznˇen se smˇerem kosti. Referenˇcn´ı kostra (oznaˇcme si ji SR ) popisuje pozice jednotlivých kloub˚ u a jejich spojen´ı kostmi. Dá se na ni pohl´ıˇzet jako na graf um´ıstˇen´ y v prostoru, ve kterém klouby pˇredstavuj´ı uzly a kosti hrany. Tohoto pozorován´ı vyuˇzijeme bˇehem generován´ı animaˇcn´ı kostry – je moˇzné pouˇz´ıt grafové algoritmy. Podle výˇse uvedených parametr˚ u jsme schopni kosti chápat také jako u ´seˇcky v prostoru. T´ım je dána orientace kosti pouze v jednom smˇeru, proto ke kaˇzdé kosti pˇripoj´ıme lokáln´ı souˇradnicov´ y systém, smˇer osy y ztotoˇzn´ıme se smˇerem kosti. Mimo to známe omezen´ı jej´ı rotace v˚ uˇci 24

Podrobný rozbor metody

Generován´ı prozat´ımn´ı kostry

klidové póze kolem os lokáln´ıho souˇradnihového systému (viz obrázek 5.1), coˇz je ekvivalentn´ı s limitac´ı pohybu v nadˇrazeném kloubu. Podoba referenˇcn´ı kostry je velmi zjednoduˇsenou podobou kostry ˇclovˇeka (viz obrázek 5.2. V prvn´ı ˇradˇe se oproˇst’uje od anatomie, neobsahuje napˇr. hrudn´ı koˇs nebo zdvojené kosti v konˇcetinách – u doln´ıch konˇcetin jsou kost l´ ytková a holenn´ı slouˇceny do jedné, podobnˇe u horn´ıch slouˇc´ıme kost loketn´ı a vˇretenn´ı. Tato podoba kostry pokaz´ı vzhled modelu pouze pˇri extrémn´ıch zkrutech ˇci ohybech. V druhé ˇradˇe nepostihujeme drobné detaily, jimiˇz jsou jednotlivé prsty konˇcetin a ˇcelisti, ˇc´ımˇz odpadá moˇznost otev´ırat u ´sta.

Obrázek 5.2: Referenˇcn´ı kostra, pro ilustraci znázornˇen i obrys ˇclovˇeka.

5.2

Generov´ an´ı prozat´ımn´ı kostry

Z troj´ uheln´ıkové s´ıtˇe vygenerujeme prozat´ımn´ı kostru SG s vyuˇzit´ım metody autor˚ u Au et al. podrobnˇe popsané v kapitole 2.2.2, tj. nejprve smrˇst’ujeme troju ´heln´ıkovou s´ıt’ laplaceovsk´ ym vyhlazován´ım a následnˇe opakovanˇe odstraˇ nujeme technikou edge-collapse nadbyteˇcné hrany, neˇz se zbav´ıme vˇsech troj´ uheln´ık˚ u s´ıtˇe. Vzniklé jednorozmˇerné struktuˇre uprav´ıme pozicován´ı v prostoru.

25


5.3

Vytvoˇren´ı animaˇcn´ı kostry

Vytvoˇ ren´ı animaˇ cn´ı kostry

Pˇripravenou referenˇcn´ı kostru SR humanoida budeme nyn´ı vkládat dovnitˇr modelu. Tato ˇcást metody vycház´ı z metody popsané v kapitole 2.3.1. Hledáme prosté zobrazen´ı M : U (SR ) → U (SG ), které jednoznaˇcnˇe pˇriˇrad´ı uzl˚ um kostry SR uzly z prozat´ımn´ı kostry SG . Pro existenci takového zobrazen´ı mus´ı platit nerovnost: |U (SR )| ≤ |U (SG )|.

(5.3)

V´ ysledná animaˇcn´ı kostra je grafov´ ym isomorfismem referenˇcn´ı kostry SR , jej´ıˇz uzly U jsou um´ıstˇeny na pozice M (U ).

5.3.1

Pˇ r´ıpravn´ e kroky a pˇ riˇ razen´ı hlavy

Pˇredpokládáme, ˇze koncový efektor pˇredstavuj´ıc´ı hlavu se nacház´ı nejvýˇse, tj. jeho souˇradnice y je maximáln´ı (osa y m´ıˇr´ı vzh˚ uru). T´ım urˇc´ıme pozici hlavy v prozat´ımn´ı kostˇre. V obou grafech (referenˇcn´ı i prozat´ımn´ı kostˇre) spoˇcteme vzdálenost mezi vˇsemi dvojicemi vrchol˚ u, coˇz lze provést napˇr´ıklad obl´ıben´ ym Floyd-Warshallov´ ym algoritmem, a následnˇe seˇrad´ıme vrcholy podle geodetické vzdálenosti od uzlu pˇredstaˇ vuj´ıc´ıho hlavu (napˇr. pomoc´ı quick sort nebo merge sort). Razen´ ı je nezbytné pro správnou funkci dalˇs´ıch krok˚ u. Urˇc´ıme nejdelˇs´ı cestu v obou grafech, jej´ı délka bude slouˇzit jako mˇeˇr´ıtko velikosti kostry. Poté provedeme pˇreˇskálován´ı referenˇcn´ı kostry tak, aby velikostnˇe odpov´ıdala prozat´ımn´ı. Zvˇetˇsen´ı s odpov´ıdá vztahu s =

Ltemp , Lref

(5.4)

kde Ltemp pˇredstavuje délku nejdelˇs´ı cesty v grafu prozat´ımn´ı kostry a Lref délku nejdelˇs´ı cesty v grafu kostry referenˇcn´ı. Vypoˇctené délky cest mezi dvojicemi vrchol˚ u pˇrenásob´ıme stejn´ ym faktorem.

26



Jako posledn´ı krok je nutné vyrovnat odliˇsné um´ıstˇen´ı koster – referenˇcn´ı kostra se m˚ uˇze v souˇradnicovém prostoru nacházet na odliˇsné pozici neˇz kostra prozat´ımn´ı. U obou koster zjist´ıme rozmˇery axis-aligned bounding boxu Btemp a Bref (obalové tˇeleso o podobˇe kvádru orientované souhlasnˇe s osami). Posun referenˇcn´ı kostry T(x, y, z) je pak urˇcen jako:   maxx minx maxx minx Btemp − Btemp − Bref + Bref      maxy miny maxy miny  T(x, y, z) =  Btemp − Btemp − Bref + Bref  .     maxz minz maxz minz Btemp − Btemp − Bref + Bref

(5.5)

Proces zarovnán´ı koster je znázornˇen na obrázku 5.6. V´ ypoˇcetn´ı sloˇzitost pˇredzpracován´ı kostry je dána jej´ım nejnároˇcnˇejˇs´ım krokem, kterým je výpoˇcet vzdálenosti mezi vˇsemi dvojicemi uzl˚ u. Floyd-Warshall˚ uv algoritmus, kter´ y dokáˇze problém efektivnˇe ˇreˇsit, nab´ yvá sloˇzitosti O(N 3 + M 3 ), kde N pˇredstavuje poˇcet vrchol˚ u referenˇcn´ı kostry a M poˇcet vrchol˚ u kostry prozat´ımn´ı.

Obrázek 5.6: Znázornˇen´ı sjednocen´ı velikosti a pozice referenˇcn´ı a prozat´ımn´ı kostry. Referenˇcn´ı kostra má vyznaˇcenou hlavu ˇcernˇe, prozat´ımn´ı b´ıle. Teˇckovanˇe jsou vyznaˇceny obaluj´ıc´ı boxy.

5.3.2

Pˇ riˇ razen´ı list˚ u

V této ˇca´sti se zab´ yváme pˇriˇrazen´ım listov´ ych uzl˚ u. Hlava je v tuto chv´ıli uˇz pˇriˇrazena, a proto ji z tohoto procesu vyjmeme. Z listových vrchol˚ u utvoˇr´ıme seznamy, formálnˇe si je oznaˇc´ıme: pro referenˇcn´ı kostru Lref = (r1 , r2 , . . . , rn ), pro prozat´ımn´ı 27



kostru pak Ltemp = (t1 , t2 , . . . , tm ). Obecnˇe nelze ˇr´ıci, ˇze by byl poˇcet list˚ u stejn´ y, naopak pˇredpokládáme, ˇze m ≥ n. Je nutné poznamenat, ˇze respektujeme poˇrad´ı vrchol˚ u vzniklé ˇrazen´ım podle vzdálenosti od hlavy. Listy obou graf˚ u k sobˇe pˇriˇrad´ıme uˇzit´ım mad’arské metody [2], která minimalizuje globáln´ı cenu (penalizaci) pˇriˇrazen´ı. Pro vyˇc´ıslen´ı ceny Ei,j pˇriˇrazen´ı dvojice (ti , rj ) pouˇzijeme vztah: Ei,j = cDW T · DW T (dti , drj )2 + cdist · dist(ti , rj )2 ,

(5.7)

Pˇredpis ceny je váˇzeným souˇctem dvou ˇclen˚ u, neprve si objasn´ıme výraz funkce dist. Ta vrac´ı euklidovskou vzdálenost mezi pˇredanými vrcholy, cdist pˇredstavuje násobic´ı konstantu (váhu). Funkce DW T pak spoˇc´ıtá hodnotu dynamic time warping dvou sekvenc´ı dti a drj . V nich jsou obsaˇzeny geodetické vzdálenosti list˚ u (t1 , t2 , . . . , tm ) a (r1 , r2 , . . . , rn ) od vrcholu ti , respektive rj (vzdálenosti uˇz byly vypoˇcteny bˇehem pˇr´ıpravného kroku Floyd-Warshallov´ ym algoritmem). Konstanta cDW T je váhou funkce DW T . V´ ypoˇcetn´ı sloˇzitost pˇriˇrazen´ı list˚ u se skládá z nˇekolika ˇca´st´ı. V´ ypoˇcet hodnoty DWT pro dvˇe sekvence, z nichˇz má prvn´ı délku N a druhá M , je obecnˇe sloˇzitosti O(M N ). Tento výpoˇcet vˇsak provád´ıme pro vˇsechny prvky matice velikosti M × N , tud´ıˇz sloˇzitost samotné pˇr´ıpravy matice pro mad’arskou metodu bude O(M 2 N 2 ). Následuje výpoˇcet optimáln´ıho pˇriˇrazen´ı (mad’arskou metodou) o sloˇzitosti O(M N 2 ). Jak jiˇz bylo ˇreˇceno výˇse, pˇredpokládáme, ˇze poˇcet list˚ u prozat´ımn´ı kostry je vˇetˇs´ı nebo roven poˇctu list˚ u referenˇcn´ı kostry, tj. M ≥ N . Nˇekteré listy prozat´ımn´ı kostry tak z˚ ustanou nepˇriˇrazeny (viz dále). Nen´ı-li dodrˇzena podm´ınka M ≥ N , algoritmus pˇriˇrazen´ı list˚ u selˇze, nebot’ nen´ı moˇzné nechat jedin´ y list referenˇcn´ı kostry, kterou hodláme ovládat model, nepˇriˇrazen´ y. Po dokonˇcen´ı této fáze se zamˇeˇr´ıme na vnitˇrn´ı uzly.

5.3.3

Pˇ riˇ razen´ı vnitˇ rn´ıch uzl˚ u

Pˇred samotným pˇriˇrazován´ım vnitˇrn´ıch uzl˚ u projdeme graf prozat´ımn´ı kostry od kaˇzdého pˇriˇrazeného listu smˇerem ke koˇreni. Po pr˚ uchodu mohou zbýt nˇekteré vrcholy 28



nenavˇst´ıvené, jedná se o vrcholy spadaj´ıc´ı do vˇetv´ı nepˇriˇrazen´ ych list˚ u. Chápeme je jako neˇza´douc´ı a z grafu je odstran´ıme (viz obrázek 5.8). L2 L3

L1

L4

Obrázek 5.8: Proˇrezáván´ı vˇetv´ı doˇcasné kostry. Nepˇriˇrazené listy L2 , L3 , L4 budou vˇcetnˇe celé vˇetve z doˇcasné kostry odstranˇeny. Vnitˇrn´ı uzly pˇriˇrazujeme pouze na základˇe optimalizace lokáln´ı chyby, tedy bez ohledu na penalizaci ostatn´ıch vrchol˚ u – pro definici chyby vyuˇzijeme hodnoty, které jsou na pˇriˇrazen´ı nezávislé (viz n´ıˇze). Drobnou v´ yjimkou je, ˇze jiˇz pˇriˇrazen´ y vrchol nesm´ı b´ yt pouˇzit opˇetovnˇe (to lze provést napˇr´ıklad oznaˇcen´ım vrcholu). Vnitˇrn´ı vrcholy náleˇz´ıc´ı doˇcasné kostˇre oznaˇc´ıme ui , vnitˇrn´ı vrcholy náleˇz´ıc´ı referenˇcn´ı kostˇre pak vj . Pro kaˇzd´ y ui tedy procház´ıme vˇsechny nepouˇzité uzly vj , pˇriˇcemˇz hledáme takové pˇriˇrazen´ı, které je nejménˇe penalizováno. Pro kaˇzd´ y vrchol lze vyjádˇrit tyto d´ılˇc´ı penalizace: 1. Rozd´ıl vzd´ alenost´ı k list˚ um. Známe pˇriˇrazen´ı list˚ u, v kaˇzdém grafu taktéˇz geodetickou vzdálenost k pˇr´ısluˇsnému listu. Tato vzdálenost se v obou grafech bude nejsp´ıˇse liˇsit. Seˇcten´ım kvadrát˚ u vˇsech rozd´ıl˚ u dostáváme chybu, kterou oznaˇc´ıme EL . 2. Rozd´ıl stupnˇ e vrchol˚ u. Kvadrát rozd´ılu stupnˇe vrchol˚ u ui a vj , oznaˇc´ıme jej ED . 3. Vzd´ alenost vrchol˚ u. Kvadrát euklidovské vzdálenosti vrchol˚ u ui a vj , oznaˇc´ıme jej EP . V´ ysledná chyba odpov´ıdá jejich váˇzenému souˇctu: E = cEL · EL + cED · ED + cEP · EP .

(5.9)

Tato hodnota nen´ı závislá na pˇriˇrazen´ı jin´ ych vnitˇrn´ıch vrchol˚ u, proto m˚ uˇzeme v´ yslednou konfiguraci hledat s pomoc´ı optimalizace lokáln´ı chyby. Sloˇzitost pomoc´ı 29



naivn´ı implementace je pak rovna O(M N ), N znamená poˇcet vnitˇrn´ıch vrchol˚ u vzorové kostry, M poˇcet vrchol˚ u prozat´ımn´ı. Momentálnˇe jsme referenˇcn´ı kostru um´ıstili do vstupn´ı troj´ uheln´ıkové s´ıtˇe, ˇc´ımˇz jsme vytvoˇrili animaˇcn´ı kostru. Kosti jsou v tuto chv´ıli reprezentovány pouze pomoc´ı u ´seˇcek (hrany grafu), pro interaktivn´ı demo deformuj´ıc´ı s´ıt’ mus´ıme urˇcit orientaci lokáln´ıch souˇradnicov´ ych systém˚ u.

5.3.4

Zkop´ırov´ an´ı lok´ aln´ıch souˇ radnicov´ ych syst´ em˚ u

→ − Pro lokáln´ı souˇradnicový systém plat´ı, ˇze osa y je ztotoˇznˇená s orientac´ı kosti B . Dále v´ıme, ˇze animaˇcn´ı kostra si je s referenˇcn´ı velmi podobná (vzhledem k charakteru vstupn´ıch dat). Oznaˇcme si orientaci os lokáln´ıho systému animaˇcn´ı kostry Ax , Ay , Az a u referenˇcn´ı kostry Rx , Ry , Rz . Pak plat´ı: → − B Ay = → − kBk

(5.10)

Az = R x × Ay

(5.11)

Ax = A y × A z

(5.12)

Tento krok má viditelnˇe lineárn´ı sloˇzitost O(N ). Pˇr´ıklad moˇzného v´ ysledku se nacház´ı na obrázku 5.13.

5.3.5

Zkop´ırov´ an´ı limitace pohybu v kloubech

Hodnoty omezen´ı v kloubech jsou do v´ ysledného modelu jednoduˇse zkop´ırovány. Pˇredpokládáme, ˇze jsou oba modely v klidové póze a je d´ıky tomu moˇzné pouˇz´ıt stejné hodnoty.

30


Interaktivn´ı deformace

Obrázek 5.13: Znázornˇen´ı lokáln´ıch souˇradnicov´ ych systém˚ u kost´ı.

5.4


Animaˇcn´ı kostra nyn´ı obsahuje veˇskeré informace nutné pro interaktivn´ı manipulaci. V m´ıstech koncov´ ych efektor˚ u se objev´ı prvky, které uˇzivatel m˚ uˇze pˇresouvat v prostoru a zadá tak novou pozici pˇr´ısluˇsného koncového efektoru, kter´ y se k n´ı pˇribl´ıˇz´ı s vyuˇzit´ım inverzn´ı kinematiky.

5.4.1


Metody ˇreˇs´ıc´ı u ´lohu inverzn´ı kinematiky byly popsány v kapitole 3. Pro v´ ypoˇcet v interaktivn´ı ukázce byl zvolen pˇr´ıstup cyclic coordinate descent (CCD), která konverguje zpravidla bˇehem nˇekolika set iterac´ı a umoˇzn ˇuje ˇreˇsit u ´lohu pˇr´ımo v globáln´ım souˇradnicovém systému. Limity rotac´ı v kloubech jsou zadány jako maximáln´ı hodnoty rotac´ı kolem lokáln´ı osy x, y a z. Krok algoritmu, kdy optimálnˇe natáˇc´ıme právˇe vybranou kost, aby vzdálenost koncového efektoru X od zadané pozice Y byla minimáln´ı, rozloˇz´ıme na 31



tˇri individuáln´ı rotace podle lokáln´ıch os. Pˇrekroˇc´ı-li rotace zadané omezen´ı, je jej´ı hodnota upravena oˇr´ıznut´ım na povolen´ y interval.

A

X

y X'

x

O

α

z

A'

Y'

σ

Obrázek 5.14: Znázornˇen´ı rotace kolem lokáln´ı osy y. Bod X pˇredstavuje pozici koncového efektoru, A novˇe zadanou pozici, O poˇcátek lokáln´ı soustavy souˇradnic. Rovina σ znázorˇ nuje rotaˇcn´ı rovinu, α hledaný u ´hel rotace. X 0 je pr˚ umˇetem koncového 0 efektoru X do roviny rotace, Y pr˚ umˇetem koncového efektoru po proveden´ı rotace. Rotace kolem jedné z os je znázornˇena na obrázku 5.14. Provedeme ortogonáln´ı projekci koncového efektoru X do roviny rotace σ, kterou vyjádˇr´ıme pomoc´ı bodu O a normálového normalizovaného vektoru n (souhlasnˇe orientovan´ ym se zvolenou osou rotace): −−→ X 0 = X − (OX · n) n.

(5.15)

−−→ Obdobnˇe prom´ıtneme do roviny σ i c´ılový bod Y . Takto jsme z´ıskali vektory OX 0 −−→ a OY 0 , které sv´ıraj´ı hledan´ yu ´hel ideáln´ı rotace α, jehoˇz velikost vypoˇcteme podle pˇredpisu: α = arccos

−−→0 −−→0 ! OX OY . −−→0 · −−→0 kOX k kOY k

(5.16)

Výsledná hodnota se nacház´ı v intervalu h0, πi, nebot’ se jedná pouze o absolutn´ı velikost. Naˇstˇest´ı znaménko m˚ uˇzeme snadno urˇcit uˇzit´ım vektorového souˇcinu, výsledný vztah potom nabyde tvaru:

32


α = arccos


−−→0 ! −−→0 −−→ −−→ OY OX 0 0 · sgn (OX × OY ) · n , −−→ · −−→ kOX 0 k kOY 0 k

(5.17)

kde sgn pˇredstavuje matematickou funkci signum, která pro záporné ˇc´ıslo vrac´ı hodnotu −1, pro kladné +1 a pro nulu 0.

A A' X X' y O

x

z Obrázek 5.18: Znázornˇen´ı prodlouˇzen´ı kosti podél lokáln´ı osy y. Bod X pˇredstavuje pozici koncového efektoru, A novˇe zadanou pozici, O poˇca´tek lokáln´ı soustavy souˇradnic. X 0 je pr˚ umˇetem koncového efektoru X na lokáln´ı osu y, A0 pr˚ umˇetem zadané pozice.

Inverzn´ı kinematika s pruˇ zn´ ymi kostmi V pˇr´ıpadˇe, ˇze kosti lze natahovat, pˇridáme kromˇe tˇr´ı rotaˇcn´ıch krok˚ u jeˇstˇe zmˇenu délky kosti. Tento krok bude proveden pouze podél osy y, s n´ıˇz je kost souhlasnˇe orientovaná. Situace je zachycena na obrázku 5.18, na nˇemˇz se pouˇz´ıvá stejné znaˇcen´ı −−→ jako u rotace. Hledaná zmˇena délky kosti odpov´ıdá orientované u ´seˇcce X 0 A0 , body

33



X 0 a A0 urˇc´ıme pomoc´ı pr˚ umˇetu na lokáln´ı osu y: −−→ X 0 = O + (OX · b) b, −→ A0 = O + (OA · b) b.

(5.19) (5.20)

kde b je normalizovaný vektor souhlasnˇe orientovaný s lokáln´ı osou y. Abychom zabránili singularitám, nedovol´ıme zkrácen´ı kosti pod urˇcit´ y práh (napˇr´ıklad nedovol´ıme, aby kost byla kratˇs´ı neˇz v klidovém stavu).

V´ ypoˇ cetn´ı sloˇ zitost Sloˇzitost výpoˇctu u ´lohy inverzn´ı kinematiky metodou CCD záleˇz´ı na poˇctu kost´ı P , ze kter´ ych se skládá segmentová struktura. Dále se mˇen´ı poˇcet nutn´ ych iterac´ı ICCD v závislosti na poˇcáteˇcn´ı a c´ılové konfiguraci struktury. V´ yslednou v´ ypoˇcetn´ı sloˇzitost lze formálnˇe vyjádˇrit pˇredpisem O(ICCD P ).

5.4.2

Mesh-skinning

Zmˇena animaˇcn´ı kostry vyˇzaduje patˇriˇcnou u ´pravu troj´ uheln´ıkové s´ıtˇe. Proto pouˇzijeme tzv. mesh-skinning, techniku deformace s´ıtˇe, kdy se troj´ uheln´ıková s´ıt’ pˇrizp˚ usobuje kostˇre, která je j´ı pˇriˇrazena. Pro demonstraˇcn´ı aplikaci byla naimplementována varianta naz´ yvaná linear blend skinning (LBS). Linear blend skinning (LBS) deformuje s´ıt’ pomoc´ı lineárn´ı kombinace transformaˇcn´ıch matic definovaných v kostech. Jedná se o nejzákladnˇejˇs´ı pˇr´ıstup k problematice, a pˇresto ˇcasto pouˇz´ıvan´ y napˇr´ıklad v poˇc´ıtaˇcov´ ych hrách zejména kv˚ uli jednoduché implementaci a n´ızk´ ym nárok˚ um na c´ılov´ y hardware. Na vstupu máme troj´ uheln´ıkovou s´ıt’ s m vrcholy vi a kostru tvoˇrenou uspoˇra´danou mnoˇzinou n kost´ı bj . Pro kaˇzdou kost bj je definována matice afinn´ı transformace Mj . Kaˇzd´ y vrchol vi obsahuje n definovan´ ych vah pˇr´ıspˇevku kosti wij (viz obrázek 5.21). V´ ystupem je deformovaná mnoˇzina vrchol˚ u, pˇriˇcemˇz p˚ uvodn´ı topologie s´ıtˇe z˚ ustává zachována. Deformace jednoho vrcholu se provád´ı podle vztahu 5.22.

34



Obrázek 5.21: Vizualizace vah kost´ı (ovlivnˇen´ı vrcholu danou kost´ı). Svˇetlá barva znamená velké ovlivnˇen´ı, ˇcerná ˇza´dné. V m´ıstˇe kloubu maj´ı vliv obˇe kosti. Algoritmus je vysoce paralelizovateln´ y, vrcholy lze zpracovat naprosto nezávisle. v0i =

n X

wij (Mj vi ) =

j=0

n X

! wij Mj

vi

(5.22)

j=0

Jednoduchost LBS se podepisuje na viditeln´ ych artefaktech, mezi nˇeˇz patˇr´ı: • ztráta objemu (zborcen´ı s´ıtˇe) zejména v m´ıstˇe velkého ohybu ˇci zkrutu, • sebeprot´ınán´ı s´ıtˇe v m´ıstech velkého ohybu ˇci zkrutu.

V´ ypoˇ cet vah mesh-skinningu Spolu s automaticky vygenerovanou kostrou bohuˇzel nedostáváme rovnou váhy urˇcené pro mesh-skinning. Tyto hodnoty zpravidla tvoˇr´ı v´ ytvarn´ık (animátor) ve vhodném nástroji, lze je vˇsak pro naˇse u ´ˇcely pomˇernˇe dobˇre odhadnout. K výpoˇctu pouˇzijeme s´ıt’ ve stavu, v jakém se nacházela pˇri generován´ı kostry po posledn´ı iteraci laplaceovského smrˇst’ován´ı (tj. pˇred zahájen´ım decimace s´ıtˇe). Od vstupn´ı s´ıtˇe pˇredané aplikaci ke zpracován´ı se liˇs´ı pouze pozicemi vrchol˚ u, které se ale vyskytuj´ı vhodnˇe bl´ızko vygenerované kostry.

35



Na základˇe tohoto pozorován´ı urˇc´ıme váhu kosti bi pro vrchol vj podle vztahu: wij =

1 ε + dist(bi , vj )2

(5.23)

kde ε znaˇc´ı vhodné malé ˇc´ıslo (v aplikaci zvoleno ε = 10−5 , ˇc´ım vyˇsˇs´ı, t´ım plynulejˇs´ı bude zmˇena vlivu kost´ı v okol´ı kloub˚ u), funkce dist vzdálenost vrcholu vj od kosti bi , kterou pˇri v´ ypoˇctu vah chápeme jako u ´seˇcku. Z´ıskané váhy posléze mus´ıme normalizovat:

wij wîj = P i wij

(5.24)

Z v´ ykonnostn´ıch d˚ uvod˚ u se obvykle pouˇz´ıvá stanoven´ y poˇcet vah, nebot’ valná vˇetˇsina je témˇeˇr rovna nule a kost má tak na deformovaný vrchol sotva zanedbatelný vliv. Demonstraˇcn´ı aplikace provád´ı mesh-skinning s uˇzit´ım ˇctyˇr nejv´ yznamˇejˇs´ıch vah na jeden vrchol.

36

6 Implementace demonstraˇcn´ı aplikace Kapitola se zabývá implementac´ı metody generován´ı kostry a následné interaktivn´ı deformace modelu. Popisuje rozhodnut´ı, k nimˇz doˇslo bˇehem vývoje, specifikuje pˇresný formát vstupn´ıch dat a zab´ yvá se architekturou vzniklé aplikace. Demonstraˇcn´ı aplikace je spouˇstˇena jako konzolová aplikace, která posléze vytvoˇr´ı okno pro vykreslován´ı scény. Uˇzivatel tak zadává vstup skrze parametry programu a následnˇe (po dokonˇcen´ı preprocessingu) ovládá scénu interaktivnˇe myˇs´ı a klávesnic´ı skrze vykreslovac´ı okno.

6.1

Pouˇ zit´ e knihovny a jazyk

Demonstraˇcn´ı aplikace byla naprogramována v jazyce C++ verze 2011 (C++11) a závis´ı na frameworku VTK (Visualization Toolkit) a knihovnách libhungarian a Eigen. Mimo tyto knihovny tˇret´ıch stran je pro pˇreklad vyˇzadována standardn´ı knihovna C++ opˇet verze 2011. VTK je open source projektem spoleˇcnosti Kitware, která jej aktivnˇe vyv´ıj´ı a poskytuje k nˇemu podporu. Tento rozsáhl´ y framework mimo jiné nab´ız´ı tˇr´ıdy umoˇzn ˇuj´ıc´ı vizualizace, zpracován´ı obrazu, ale i abstrakci c´ılové platformy. V demonstraˇcn´ı aplikaci má na starosti veˇskeré vykreslován´ı obsahu, zpracován´ı vstup˚ u od uˇzivatele a pohyb ve scénˇe. Kitware poskytuje VTK v dobˇe psan´ı práce (2015) pod benevolentn´ı BSD licenc´ı.1 Knihovna libhungarian poskytuje implementaci mad’arské metody v jazyce C, ˇreˇs´ı tedy jiˇz zmiˇ nované optimáln´ı párován´ı s nejmenˇs´ı ztrátou. Jej´ım autorem je Cyrill Stachniss. Eigen je knihovna pro výpoˇcty z oblasti lineárn´ı algebry. Kromˇe operac´ı s maticemi a vektory disponuje napˇr´ıklad ˇreˇsen´ım soustav lineárn´ıch rovnic. Knihovna je zaˇst´ıtˇena licenc´ı MPL2 2 . 1 2

Ofici´ aln´ı licenˇcn´ı informace lze nalézt na adrese http://www.vtk.org/licensing/. Lze nalézt na adrese http://eigen.tuxfamily.org/index.php?title=Main_Page#License.

37

Implementace demonstraˇcn´ı aplikace

6.2

Formát vstupn´ıch dat

Form´ at vstupn´ıch dat

Abychom ukázkovou aplikaci nezatˇeˇzovali dalˇs´ımi pomocn´ ymi knihovnami, bylo nutné zvolit takov´ y vstupn´ı formát dat, jehoˇz naˇc´ıtán´ı je podporováno jiˇz v rámci frameworku VTK nebo jeho vlastn´ı implementace nen´ı obt´ıˇzná. Druhým poˇzadavkem je, abychom do pouˇzitého formátu snadlo exportovali existuj´ıc´ı data, a to opˇet existuj´ıc´ım ˇreˇsen´ım nebo vlastn´ı implementac´ı.

6.2.1

Vzorov´ a kostra

Pro uchován´ı vzorové kostry, která mus´ı nav´ıc uchovat omezen´ı pohybu kloubech a lokáln´ı trojhrany, bohuˇzel nebyl nalezen vhodn´ y a zároveˇ n jednoduch´ y formát. Kostra byla pˇripravena v modelovac´ım a animaˇcn´ım programu Blender, kter´ y je naˇstˇest´ı rozˇsiˇriteln´ y uˇzivatelsk´ ymi skripty v jazyce Python, pro nˇeˇz poskytuje API v podstatˇe k veˇskeré své funkcionalitˇe 3 . D´ıky tomu mohl vzniknout exportovac´ı skript do vlastn´ıho textového formátu, kter´ y obsahuje pouze námi vyˇzadované informace. Soubor je uvozen nejprve ˇc´ıslem urˇcuj´ıc´ım uloˇzen´ y poˇcet kost´ı, které po nˇem následuj´ı. Kaˇzdé kosti je dle poˇrad´ı pˇriˇrazen index, pˇriˇcemˇz zaˇc´ınáme ˇc´ıslem nula. Zapsané souˇradnice a matice jsou spadaj´ı do svˇetov´ ych souˇradnic, nejsou podˇr´ızeny jiné transformaci. Hodnoty v souboru jsou oddˇeleny libovoln´ ym mnoˇzstv´ım mezer, tabulátor˚ u nebo odˇra´dkován´ı. Následuje strukturovaný popis formátu s vysvˇetlivkami.

Hlaviˇ cka [poˇ cet kost´ ı]

Soubor je uvozen nejprve ˇc´ıslem urˇcuj´ıc´ım uloˇzen´ y poˇcet kost´ı, které po nˇem následuj´ı.

Pro kaˇ zdou kost [index nadˇ razen´ e kosti] Index kosti nadˇrazené v hierarchii, −1 znaˇc´ı, ˇze nadˇrazená v˚ uˇci aktuáln´ı neexistuje. 3

Viz Blender/Python Documentation: http://www.blender.org/api/blender_python_api_2_74_release/

38


Generován´ı kostry

[headx] [heady] [headz] Souˇradnice poˇca´tku kosti zapsané v desetinných ˇc´ıslech. [tailx] [taily] [tailz] Souˇradnice konce kosti zapsané v desetinn´ ych ˇc´ıslech. [rotx-min] [rotx-max]

Limity rotace kosti kolem osy x v radiánech.

[roty-min] [roty-max]

Limity rotace kosti kolem osy y v radiánech.

[rotz-min] [rotz-max]

Limity rotace kosti kolem osy z v radiánech.

[m11] [m12] [m13] [m14] Matice definuj´ıc´ı lokáln´ı prostor kosti. [m21] [m22] [m23] [m24] [m31] [m32] [m33] [m34] [m41] [m42] [m43] [m44] Limitace rotace kosti, která vlastnˇe pˇredstavuje omezen´ı pohybu v nadˇrazeném kloubu, urˇcuje maximáln´ı rotaci kolem dané osy (procházej´ıc´ı nadˇrazeným kloubem) z klidové pózy.

6.2.2

Troj´ uheln´ıkov´ a s´ıt’

Pro vstupn´ı troj´ uheln´ıhovou s´ıt’ reprezentuj´ıc´ı humanoida jsem zvolil formát Wavefront OBJ. Mimo troj´ uheln´ıkové s´ıtˇe poskytuje uchováván´ı Bézierov´ ych plát˚ u, pˇriˇrazen´ı materiál˚ u plochám atd. Aplikace nicménˇe pˇredpokládá, ˇze vstupn´ı soubor obsahuje pouze troj´ uheln´ıky. Shrnuj´ıc´ı informace o formátu lze nalézt napˇr´ıklad v [1]. Formát Wavefront OBJ je podporován drtivou vˇetˇsinou program˚ u pracuj´ıc´ıch s trojrozmˇern´ ymi modely, které jej dokáˇz´ı importovat i exportovat. V naˇs´ı aplikaci jej snadno naˇcteme uˇzit´ım tˇr´ıdy vtkOBJReader, kterou poskytuje VTK.

6.3

Generov´ an´ı kostry

Kostra je v programu reprezentována tˇr´ıdou CSkeleton, která dokáˇze vykonat nad kostrou potˇrebné u ´kony, mimo jiné naˇc´ıst ji ze souboru (vyuˇzito u referenˇcn´ı kostry) nebo pˇriˇradit odpov´ıdaj´ıc´ı vrcholy prozat´ımn´ı a referenˇcn´ı kostry a tak vytvoˇrit v´ yslednou animaˇcn´ı kostru. 39



Tvorba prozat´ımn´ı kostry (viz sekce 5.2) byla naprogramována dˇedˇen´ım abstraktn´ı tˇr´ıdy vtkPolyDataAlgorithm, která poskytuje moˇznost zpracován´ı libovoln´ ych primitiv (pˇresnˇeji vrchol˚ u a jejich spojen´ı v grafická primitiva). D´ılˇc´ı ˇca´sti procesu byly rozdˇeleny do dvou tˇr´ıd: MeshLaplaceFilter zajiˇst’uje smrˇst’ován´ı modelu uˇzit´ım laplaceovského vyhlazován´ı, EdgeCollapseFilter provád´ı redukci geometrie a závˇereˇcnou u ´pravu pozic. Výsledná animaˇcn´ı kostra, jak jiˇz bylo zm´ınˇeno, je vytvoˇrena jednou z metod tˇr´ıdy CSkeleton – statickou metodou CSkeleton::Match, která pˇreb´ırá pˇres argumenty referenˇcn´ı a prozat´ımn´ı kostru. Mechanismus tvorby byl popsán v sekci 5.3.

6.4

Uk´ azkov´ a aplikace

V rámci diplomové práce byla kromˇe generován´ı animaˇcn´ı kostry naimplementována také demostraˇcn´ı aplikace, která dovoluje vzniklou kostru rozhýbat uˇzivatelem, deformovat tak vstupn´ı s´ıt’ s pouˇzit´ım mesh-skinningu a výsledek zobrazovat. Naˇcten´ı s´ıtˇe ve formátu OBJ, rendering a zpracován´ı vstupu byly realizovány pomoc´ı tˇr´ıd nab´ızen´ ych frameworkem VTK (vtkPolyData, vtkPolyDataMapper, vtkActor aj.). Znázornˇen´ı pipeline se nacház´ı na obrázku 6.1.

ˇ e jsou vyznaˇceny ˇcásti Obrázek 6.1: Znázornˇen´ı pipeline demonstraˇcn´ı aplikace. Sedˇ implementované VTK, b´ıle vlastn´ı implementace.

40


6.4.1



Pˇrikroˇc´ıme k interaktivn´ımu ovlivˇ nován´ı scény. Na pozice koncov´ ych efektor˚ u um´ıst´ıme pomocné prvky, jejichˇz pˇretaˇzen´ım dojde pˇrepoˇc´ıtán´ı konfigurace kostry – ˇreˇsen´ı u ´lohy inverzn´ı kinematiky. Pomocné prvky jsou vyb´ırány myˇs´ı, pro v´ ybˇer objektu ve scénˇe byla vyuˇzita jiˇz naimplementovaná tˇr´ıda vtkCellPicker z frameworku VTK. Inverzn´ı kinematika realizovaná pomoc´ı CCD byla naimplementována v pouhých nˇekolika funkc´ıch, nebot’ se jedná o demonstraˇcn´ı ovlivnˇen´ı scény nevelkého rozsahu. Funkce ProcessIK, po jej´ımˇz zavolán´ı dojde k v´ ypoˇctu, má dva parametry: prvn´ı urˇcuje, který koncový efektor byl pˇretaˇzen na jiné m´ısto, druhý je pˇr´ıznak, jestli jsou kosti pevné ˇci pruˇzné.

6.4.2

Mesh-skinning

V demonstraˇcn´ı aplikaci je skinning realizován jako tˇr´ıda CSkinnedMesh, která si udrˇzuje stav kostry v klidové a souˇcasné póze a troj´ uheln´ıkovou s´ıt’ v klidové póze. Tato data jsou uchována v podobˇe hluboké kopie, coˇz umoˇzn ˇuje pˇripravovat dalˇs´ı sn´ımek paralelnˇe. Tˇr´ıda dˇed´ı od vtkPolyDataAlgorithm, jedná se o modul poskytovaný frameworkem VTK, který disponuje vstupn´ımi a výstupn´ımi datovými porty. D´ıky tomu dokáˇze pˇredat výslednou s´ıt’ standardn´ı cestou k dalˇs´ımu zpracován´ı nebo vizualizaci. Pˇri zmˇenˇe konfigurace kostry docház´ı pouze ke zmˇenˇe pozic vrchol˚ u, indexace s´ıtˇe z˚ ustává zachována.

6.4.3

Nastaven´ı

Nastaven´ı kostant a názv˚ u soubor˚ u pouˇz´ıvaných aplikac´ı je shomáˇzdˇeno centrálnˇe ve tˇr´ıdˇe TAppSettings vˇcetnˇe pˇrednastavených hodnot, které byly urˇceny empiricky na základˇe v´ ysledk˚ u testován´ı. TAppSettings je naimplementována jako struktura, coˇz zp˚ usobuje, ˇze vˇsechny jej´ı atributy jsou defaultnˇe veˇrejné. Po spuˇstˇen´ı aplikace nic nebrán´ı dodateˇcné u ´pravˇe hodnot napˇr´ıklad parametry pˇredan´ ymi skrze pˇr´ıkazovou ˇrádku. Pˇresnˇe tak lze mˇenit vybrané konstanty v demonstraˇcn´ı aplikaci. 41

7 Výsledky Metoda byla po implementaci otestována na nˇekolika zkuˇsebn´ıch modelech. Jedná se o manifoldn´ı troj´ uheln´ıkové s´ıtˇe pˇredstavuj´ıc´ı v´ıce ˇci ménˇe humanoidn´ı charaktery. Mezi modely byly zámˇernˇe zaˇrazeny modely, které by mohly ˇcinit pot´ıˇze, napˇr´ıklad se nenacházej´ı pˇresnˇe v klidové póze (coˇz m˚ uˇze ovlivnit generován´ı kostry, ale i fungován´ı inverzn´ı kinematiky, která pro omezen´ı v kloubech pˇredpokládá stále stejné nastaven´ı klidové pózy modelu).

7.1

Testovac´ı modely

Následuje pˇredstaven´ı pouˇzit´ ych model˚ u a jejich charakteristick´ ych vlastnost´ı. Jedná se o modely poskytnuté zdarma v r˚ uzn´ ych databankách, které musely b´ yt m´ırnˇe upraveny, aby byly manifoldn´ı.

Obrázek 7.1: Ukázka vstupn´ıch model˚ u, zleva human, human-low, human-high. • human – Troj´ uheln´ıková s´ıt’ pˇredstavuj´ıc´ı ˇclovˇeka pˇripravená v r˚ uzn´ ych rozliˇsen´ıch (pro testován´ı vlivu na v´ ykon). Hraniˇcn´ı verze human-high obsahuje ˇctyˇrikrát v´ıce troj´ uheln´ık˚ u, verze human-low naopak ˇctyˇrikrát ménˇe neˇz human. Na základˇe tohoto modelu byla vytvoˇrena referenˇcn´ı kostra. Model se nacház´ı vlevo na obrázku 7.1.

42

Výsledky

Testovac´ı modely

• human2 – Troj´ uheln´ıková s´ıt’ pˇredstavuj´ıc´ı ˇclovˇeka. Model nestoj´ı pˇresnˇe v klidové póze, coˇz m˚ uˇze znesnadnit generován´ı kostry (viz uprostˇred na obrázku 7.1).

• human-noise – Jedná se o zaˇsumˇenou podobu modelu human (viz vpravo na obrázku 7.1), tj. pozice vrchol˚ u modelu jsou m´ırnˇe náhodnˇe odch´ yleny.

• armadillo – S´ıt’ pˇredstavuj´ıc´ı stylizovaného humanoidn´ıho pásovce. Model nestoj´ı pˇresnˇe v klidové póze, má ocas a dlouhé uˇsi na hlavˇe (viz vlevo na obrázku 7.2).

• minotauro – Minotaur bez roh˚ u, model má vyˇsˇs´ı poˇcet troj´ uheln´ık˚ u ve srovnán´ı s ostatn´ımi (viz uprostˇred na obrázku 7.2).

1

• stickman – Velmi zjednoduˇsená podoba humanoida, tˇelo je velmi tenké (viz vpravo na obrázku 7.2).

Obrázek 7.2: Ukázka vstupn´ıch model˚ u, zleva armadillo, minotauro, stickman. 1

Autor: https://www.youtube.com/user/blendermodels4free/about.

43

Výsledky

7.2

Nastaven´ı konstant generován´ı kostry

Nastaven´ı konstant generov´ an´ı kostry

Pro výˇse pˇredstavené modely byla vygenerována animaˇcn´ı kostra. Empiricky byly urˇceny optimáln´ı hodnoty konstant, které byly popsány v kapitole 5.2 a 5.3. Pro fázi smrˇst’ován´ı: • maximáln´ı poˇcet iterac´ı IC = 6 • poˇca´teˇcn´ı hodnota WH = 0.5 • zesilovac´ı koeficient sL = 2.5 • práh Vmin = 10−5 Pro fázi redukce geometrie: • penalizace kˇrivosti Cshape = 0.1 • penalizace délky kost´ı Csampling = 1 Pro fázi pˇriˇrazován´ı list˚ u kostry: • váha v´ ysledku DWT cDW T = 1 • váha vzdálenosti od pozice vrcholu cdist = 0.01 Pro fázi pˇriˇrazován´ı vnitˇrn´ıch uzl˚ u kostry: • váha rozd´ılu vzdálenost´ı k list˚ um cEL = 1 • váha rozd´ılu stupnˇe vrcholu cED = 0.1 • váha vzdálenosti k vrcholu cEP = 0 Pˇresto se ukázalo, ˇze u nˇekterých model˚ u je nutné nˇekteré parametry pˇrenastavit na jiné hodnoty.

44

Výsledky

Výsledná podoba kostry

U modelu armadillo docházelo k nedostateˇcnému smrˇst’ován´ı s´ıtˇe, proto byl poˇcet iterac´ı laplaceovského vyhlazován´ı IC zvýˇsen na hodnotu 9 a zesilovac´ı koeficient sL na 3. Model human2 poskytoval nejlepˇs´ı v´ ysledky po pouh´ ych tˇrech iterac´ıch, vyˇsˇs´ı poˇcty zhorˇsovaly podobu kostry v oblasti ramen. Model stickman poskytoval nejlepˇs´ı výsledky po pouhých tˇrech iterac´ıch a nastaven´ı zesilovac´ıho koeficientu sL na hodnotu 1.5.

7.3

V´ ysledn´ a podoba kostry

Ukaˇzme si v´ ysledné animaˇcn´ı kostry vygenerované naˇs´ı metodou. Následuj´ıc´ı seznam popisuje vzniklé vady, výsledky jsou mimo to zachyceny na obrázku 7.4 a 7.5.

Obrázek 7.3: Model human ve dvou r˚ uzn´ ych rozliˇsen´ıch v drátˇené podobˇe vˇcetnˇe vygenerované kostry. • human, human-noise – Kvalitativnˇe výborný výsledek nezávisle na hustotˇe s´ıtˇe ˇci jej´ım zaˇsumˇen´ı (viz obrázek 7.3), kostra m´ısty nepatrnˇe vycház´ı z vnitˇrku s´ıtˇe.

• minotauro – Dobrý výsledek s m´ırn´ ym odch´ ylen´ım pozic vrchol˚ u (ruka z naˇseho pohledu vpravo, noha vlevo). Kostra vycház´ı z vnitˇrku s´ıtˇe.

45

Výsledky

Výsledná podoba kostry

• stickman – Dobr´ y v´ ysledek, nesymetrické um´ıstˇen´ı loketn´ıch, kyˇceln´ıch a ramenn´ıch kloub˚ u, coˇz lze tolerovat vzhledem k jiným proporc´ım oproti vzorové kostˇre. Kostra m´ısty vycház´ı z vnitˇrku s´ıtˇe. Vstupn´ı s´ıt’ nerespektuje pˇresnˇe klidovou pózu (dlanˇe smˇeˇruj´ı dol˚ u), omezen´ı volnosti pohybu v kloubech tak postrádá na správném u ´ˇcinku.

• human2 – Vstupn´ı model nerespektuje klidovou pózu. V´ ysledná kostra je pˇresto vygenerována správnˇe (aˇz na omezen´ı volnosti pohybu v kloubech), m´ırnˇe vyˇcn´ıvá z vnitˇrku s´ıtˇe.

ˇ y v´ ysledek, zmiˇ nme zejména ramenn´ı klouby, které jsou • armadillo – Spatn´ chybnˇe um´ıstˇeny do vnitˇrku hlavy. Problém bude patrnˇe v dlouh´ ych uˇs´ıch, z nichˇz je jedno metodou vybráno jako celá hlava. Navzdory ˇspatnému výsledku v horn´ı ˇcásti tˇela lze dobˇre interagovat s doln´ımi.

Obrázek 7.4: V´ ysledné animaˇcn´ı kostry model˚ u human, human-noise, minotauro (zleva). Z v´ ysledk˚ u plyne následuj´ıc´ı pozorován´ı. Aby byla animaˇcn´ı kostra vygenerována správnˇe, mus´ı vstupn´ı model stát pˇresnˇe v klidové póze a jeho proporce mus´ı co nejv´ıce souhlasit s proporcemi referenˇcn´ı kostry. Patrnˇe by bylo vhodné vytvoˇrit v´ıce referenˇcn´ıch koster s r˚ uzn´ ymi proporcemi, pˇriˇcemˇz by se v´ ypoˇcet provedl s uˇzit´ım kaˇzdé z nich a jako výsledek by byl vybrán ten, který je zat´ıˇzen nejmenˇs´ı chybou. Ta je ostatnˇe vyˇc´ıslována jiˇz nyn´ı v rámci d´ılˇc´ıch krok˚ u pˇriˇrazován´ı vrchol˚ u kostry.

46

Výsledky

Doba generován´ı kostry

Obrázek 7.5: Výsledné animaˇcn´ı kostry model˚ u stickman, human2 a armadillo (zleva).

7.4

Doba generov´ an´ı kostry

Doba generován´ı animaˇcn´ı kostry pro vybrané modely byla zmˇeˇrena na referenˇcTM R n´ım stroji s procesorem Intel Core i5-3350P o frekvenci 3.10 GHz a 8 GB RAM.

Mˇeˇren´ı bylo provedeno opakovanˇe, v potaz byla brána nejlepˇs´ı namˇeˇrená hodnota (pˇredpokládáme, ˇze horˇs´ı v´ ysledek je zp˚ usoben´ y napˇr´ıklad preemptivn´ım chován´ım plánovaˇce operaˇcn´ıho systému, kter´ y rozhodl v neprospˇech naˇseho programu). Nejprve ukaˇzme vliv poˇctu troj´ uheln´ık˚ u modelu na dobu generován´ı kostry, pouˇzijeme s´ıtˇe r˚ uzn´ ych rozliˇsen´ı reprezentuj´ıc´ı tent´ yˇz model human. Vrcholy V

Troj´ uheln´ıky F

ˇ T Cas

human-low

2336

4668

656 ms

human

9338

18672

9110 ms

human-mid-high

18674

37344

67727 ms

human-high

37346

74688

120388 ms

human-high2

55160

110316

680934 ms

human-high3

74690

149376

1163010 ms

Model

V následuj´ıc´ı tabulce prozkoumáme pomˇer T /p(F ), kde p znaˇc´ı polynomiáln´ı funkci, kterou se snaˇz´ıme popsat výpoˇcetn´ı sloˇzitost. Pomˇery jsou normalizovány do srovnatelného ˇrádu. Pokud namˇeˇrená data odpov´ıdaj´ı svou závislost´ı zvolené funkci p, pak budou hodnoty ve sloupci oscilovat kolem konstanty.

47

Výsledky

Doba generován´ı kostry T /F

T /F 2

T /F 3

human-low

1.4053

3.0105

6.4493

human

4.8789

2.6130

1.3994

human-mid-high

18.1360

4.8565

1.3005

human-high

16.1188

2.1581

0.2890

human-high2

61.7258

5.5953

0.5072

human-high3

77.8579

5.2122

0.3489

Model

Strmˇe rostouc´ı hodnoty sloupce T /F nenasvˇedˇcuj´ı lineárn´ı závislosti T na F , naopak pro kvadratickou závislost se mˇen´ı pomˇer nejménˇe. Pˇredpokládaná kubická sloˇzitost algoritmu pˇr´ıliˇs neodpov´ıdá v´ ysledk˚ um – nejsp´ıˇse kv˚ uli tomu, ˇze ˇreˇsené soustavy lineárn´ıch rovnic, které mˇely kubickou výpoˇcetn´ı sloˇzitost zp˚ usobit, jsou ve skuteˇcnosti velmi ˇr´ıdké. Výslednou závislost doby výpoˇctu T na poˇctu troj´ uheln´ık˚ uF zaneseme do grafu (viz obrázek 7.6).

Obrázek 7.6: Namˇeˇrené doby výpoˇctu T v závislosti na poˇctu troj´ uheln´ık˚ u F vˇcetnˇe 0 −6 2 kvadratické regresn´ı funkce T = 0.0515435 · 10 F . V dalˇs´ı tabulce porovnáváme ˇcasy vˇsech vstupn´ıch s´ıt´ı pˇredstaven´ ych v kapitole 7.1:

48

Výsledky

Pamˇet’ová sloˇzitost generován´ı kostry Vrcholy

Troj´ uheln´ıky

Iterace smrˇ st’ov´ an´ı

ˇ Cas

armadillo

34594

69184

9

325405 ms

human

9338

18672

6

9110 ms

human2

14812

29620

3

11601 ms

human-noise

9338

18672

6

9147 ms

minotauro

11832

23660

6

15978 ms

stickman

3798

7592

3

1056 ms

Model

Nesm´ıme zapomenout, ˇze celková doba generován´ı je dána kromˇe poˇctu vrchol˚ u a troj´ uheln´ık˚ u vstupn´ı s´ıtˇe také jej´ım tvarem. Sloˇzitý tvar s´ıtˇe vyˇzaduje v´ıce iterac´ı pro smrˇst’ován´ı laplaceovským vyhlazován´ım, coˇz se projevilo na vysokém ˇcase u modelu armadillo. Zvyˇsován´ı poˇctu iterac´ı má nicménˇe pouze lineárn´ı vliv na výslednou dobu v´ ypoˇctu kostry (jedná se v podstatˇe o opakován´ı jedné ˇcásti algoritmu).

7.5

Pamˇ et’ov´ a sloˇ zitost generov´ an´ı kostry

Z hlediska pamˇet’ové sloˇzitosti se nejedná o zaj´ımavou u ´lohu, pˇri pouˇzit´ı ˇr´ıdkých matic je velikost alokované pamˇeti pro výpoˇcet lineárnˇe u ´mˇerná velikosti vstupn´ıch dat (tj. poˇctu troj´ uheln´ık˚ u). Pouze pˇri tvorbˇe matice pro mad’arskou metodu alokujeme pamˇet’ o velikosti M × N , kde M a N vˇsak odpov´ıdá pouze poˇctu list˚ u prozat´ımn´ı, respektive referenˇcn´ı kostry. Poˇcet list˚ u referenˇcn´ı kostry je vˇsak znám´ y (M = 5), jedná se v podstatˇe o konstantu, a tak se opˇet dostáváme na lineárn´ı sloˇzitost. U nejkomplexnˇejˇs´ıho modelu armadillo nepˇrekroˇcila veˇskerá pamˇet’ alokovaná programem hranici 50 MB bˇehem generován´ı kostry, 150 MB bˇehem vykreslován´ı.

7.6

Doba v´ ypoˇ ctu inverzn´ı kinematiky

Výpoˇcet u ´lohy inverzn´ı kinematiky prob´ıhal v reálném ˇcase. Pro vˇsechny vstupn´ı modely byla doba v´ ypoˇctu shodná, nebot’ pouˇz´ıváme shodnou kostru. Nástroje pro pˇresné mˇeˇren´ı ˇcasu ze standardn´ı knihovny jazyka C++ jsou bohuˇzel stále naimplementovány pro platformu Windows s nedostateˇcn´ ym rozliˇsen´ım, proto musely být pro meˇren´ı uˇzity funkce závislé na platformˇe: QueryPerformaceCounter a QueryPerformaceFrequency. 49

Výsledky

Srovnán´ı s existuj´ıc´ımi metodami

Obrázek 7.7: Inverzn´ı kinematika aplikovaná na model human. V pˇr´ıpadˇe, ˇze byly zakázány pruˇzné segmenty, trval v´ ypoˇcet ménˇe neˇz 10 ms, s pruˇzn´ ymi kostmi pak 15 ms. Ukázky deformovan´ ych model˚ u nalezne ˇctenáˇr na obrázc´ıch 7.7 a 7.8.

Obrázek 7.8: Inverzn´ı kinematika aplikovaná na model stickman.

7.7

Srovn´ an´ı s existuj´ıc´ımi metodami

S ohledem na metody prozkoumané v kapitole 2 m˚ uˇzeme prohlásit, ˇze vznikla unikátn´ı, dosud neexistuj´ıc´ı metoda, která pro vstupn´ı troj´ uheln´ıkovou s´ıt’ humanoida generuje kostru urˇcenou pro animaci, a to vˇcetnˇe definic omezen´ı pohybu

50

Výsledky

Srovnán´ı s existuj´ıc´ımi metodami

v kloubech. V následuj´ıc´ıch nˇekolika odstavc´ıch srovnáme vzniklou metodu a jej´ı v´ ysledky s ostatn´ımi metodami popsan´ ymi v kapitole 2. Metoda od Straka et al. (kapitola 2.3.1), podle které bylo vytvoˇreno pˇriˇrazován´ı vrchol˚ u referenˇcn´ı a prozat´ımn´ı kostry, mˇela vytvoˇrenou poˇca´teˇcn´ı kostru na základˇe sn´ımaných volumetrických dat a zpracován´ı muselo prob´ıhat v reálném ˇcase. Na rozd´ıl od p˚ uvodn´ı podoby byla naˇse ˇcást metody rozˇs´ıˇrena o v´ ypoˇcet orientace lokáln´ıho souˇradnicového systému a zkop´ırován´ı definic omezen´ı pohybu v kloubech. Z oblasti geometrick´ ych metod jsme prozkoumali metodu medial axis transform a jej´ı odhad pomoc´ı spojen´ı pól˚ u Voronného diagramu. Tento pˇr´ıstup je na rozd´ıl od naˇs´ı metody citlivý na zaˇsumˇen´ı povrchových dat a produkuje velké mnoˇzstv´ı prvk˚ u skeletu. Metoda od Au et al., pˇredstavená v kapitole 2.2.2, se stala souˇca´st´ı naˇs´ı metody, slouˇz´ı ke generován´ı prozat´ımn´ı kostry. Tvorba kostry spojován´ım význaˇcných bod˚ u (metoda od Ma et al.), kterou jsme se zab´ yvali v kapitole 2.2.2, na rozd´ıl od naˇs´ı metody nemus´ı nikterak vstupn´ı data iterativnˇe smrˇst’ovat. Jej´ı sloˇzitost, nebereme-li v u ´vahu preprocessing v podobˇe generován´ı teˇcn´ ych koul´ı, je beztak tˇeˇzko vyjádˇritelná a pro komplexn´ı modely bude pravdˇepodobnˇe ˇcasovˇe srovnatelná s metodou Au et al. Pˇr´ıstup spojován´ım v´ yznaˇcn´ ych bod˚ u má tu v´ yhodu, ˇze produkuje pomˇernˇe mal´ y poˇcet kost´ı. Z˚ ustává vˇsak otázkou, maj´ı-li vzniklé kosti alespoˇ n pˇribliˇznˇe anatomické um´ıstˇen´ı pro animaci. Naˇse metoda (podobnˇe jako metoda od Straka et al.) se specializuje na tvorbu kostry humanoida, omezen´ı volnosti pohybu v kloubech proto byla definována napevno u referenˇcn´ı kostry. Bez znalosti referenˇcn´ı kostry bychom omezen´ı mohli aplikovat napˇr´ıklad poloautomatizovanˇe, kdy by uˇzivatel zvolil u vznikl´ ych kloub˚ u jejich typ (kulov´ y, válcov´ y atd.) a limity by byly dopoˇc´ıtány testován´ım koliz´ı. Klouby by se zkrátka zkusmo ohnuly do sv´ ych nejzazˇs´ıch mez´ı, kde jeˇstˇe nedocház´ı ke kolizi obalov´ ych tˇeles sousedn´ıch kost´ı. Nab´ız´ı se ale otázka, zda takto vzniklá kostra skuteˇcnˇe usnadn´ı tvorbu animace, nebot’ se dá pˇredpokládat, ˇze bude vyˇzadovat dodateˇcné u ´pravy, které nakonec budou moˇzná srovnatelnˇe obt´ıˇzné s manuáln´ı tvorbou celé animaˇcn´ı kostry.

51

8 Závˇer C´ılem práce bylo vytvoˇrit metodu, která vygeneruje vhodnou animaˇcn´ı kostru pro model pˇredstavuj´ıc´ı humanoida. Na základˇe pr˚ uzkumu a rozboru nˇekolika metod byl navrˇzen vlastn´ı postup pro automatické generován´ı kostry humanoida z troj´ uheln´ıkové s´ıtˇe. Vzniklá metoda vyuˇz´ıvá referenˇcn´ı kostru, ze které jsou pˇreneseny charakteristické vlastnosti do v´ ysledné kostry: pˇredevˇs´ım poˇcet kost´ı a jejich hierarchické uspoˇrádán´ı, orientace lokáln´ıch souˇradnicov´ ych systém˚ u a omezen´ı volnosti pohybu v kloubech. Metoda byla otestována na troj´ uheln´ıkov´ ych s´ıt´ıch r˚ uzn´ ych hustot a podobnost´ı v˚ uˇci ˇclovˇeku. Ukázalo se, ˇze u model˚ u, které jsou bl´ızké referenˇcn´ı kostˇre (tj. dodrˇzuj´ı klidovou pózu a maj´ı proporce ˇclovˇeka, coˇz je ostatnˇe souˇcasnou nejvˇetˇs´ı limitac´ı naˇseho postupu), dosáhneme kvalitnˇejˇs´ıch v´ ysledk˚ u. Vzniklá animaˇcn´ı kostra tak potˇrebuje jen drobné ruˇcn´ı závˇereˇcné u ´pravy. Kromˇe samotného generován´ı doˇslo na implementaci interaktivn´ı deformace humanoida skrze inverzn´ı kinematiku, coˇz umoˇzn ˇuje snadno zjistit, zda kostra byla vygenerována správnˇe. K ˇreˇsen´ı inverzn´ı kinematiky byla uˇzita vlastn´ı implementace pˇr´ıstupu cyclic coordinate descent. V´ ykonnostnˇe poznamenává generován´ı kostry fakt, ˇze je bˇehem nˇeho opakovanˇe ˇreˇsena soustava lineárn´ıch rovnic. Na druhou stranu, jak jiˇz bylo naznaˇceno v u ´vodu, c´ılem práce bylo automatizovat ˇca´st animátorského procesu – bˇehem výpoˇctu kostry se tak v´ ytvarn´ık m˚ uˇze vˇenovat jiné ˇcinnosti. Demonstraˇcn´ı interakce s modelem oproti tomu prob´ıhá v reálném ˇcase. Navrˇzená metoda by mohla být rozˇs´ıˇrena tak, aby vhodnˇe volila z v´ıce referenˇcn´ıch koster, coˇz by bylo moˇzné realizovat hledán´ım pˇr´ıpadu, kdy se nejménˇe liˇs´ı referenˇcn´ı a vygenerovaná kostra. Dalˇs´ı moˇznost´ı vylepˇsen´ı by byla u ´prava omezen´ı v kloubech podle vlastnost´ı vstupn´ı s´ıtˇe, nebot’ souˇcasná metoda pˇredpokládá nemˇenné hodnoty, pˇr´ıpadnˇe korekce klidové pózy modelu pro správné pˇriˇrazen´ı omezen´ı kloub˚ u.

52

Literatura [1] Wavefront OBJ File Format Summary [online]. cit. 8.4.2015. Dostupné z: http://www.fileformat.info/format/wavefrontobj/egff.htm [2] Hungarian algorithm. Wikipedia: the free encyclopedia [online]. Wikimedia Foundation. 2001-. San Francisco (CA). Dostupné z: http://en.wikipedia.org/wiki/Hungarian_algorithm [3] Amenta, N.; Choi, S.; Kolluri, R. K.: The Power Crust, Unions of Balls, and the Medial Axis Transform. Computational Geometry: Theory and Applications, roˇcn´ık 19, 2000: s. 127–153. [4] Au, O. K.-C.; Tai, C.-L.; Chu, H.-K.; aj.: Skeleton extraction by mesh contraction. ACM Transactions on Graphics, roˇcn´ık 27, ˇc. 3, 2008: s. 1–1722. ˇ ara, J.; Sochor, J.; aj.: Modern´ı poˇc´ıtaˇcová grafika. Brno: Computer [5] Beneˇs, B.; Z´ Press, prvn´ı vydán´ı, 2004. [6] Blum, H.: A Transformation for Extracting New Descriptors of Shape. In Models for the Perception of Speech and Visual Form, editace W. Wathen-Dunn, Cambridge: MIT Press, 1967, s. 362–380. [7] Denavit, J.; Hartenberg, R. S.: A kinematic notation for lower-pair mechanisms based on matrices. Journal of Applied Mechanics, 1955. [8] Goliáˇs, R.: Inverzn´ı kinematika. Diplomová práce. Brno: Masarykova univerzita, 1999. [9] Ma, C.-M.; Wan, S.-Y.; Lee, J.-D.: Three-dimensional topology preserving reduction on the 4-subfields. Pattern Analysis and Machine Intelligence, IEEE Transactions on, roˇcn´ık 24, ˇc. 12, 2002: s. 1594–1605, ISSN 0162-8828, doi:10.1109/TPAMI.2002.1114851. 53

LITERATURA

LITERATURA

[10] Ma, J.; Bae, S.; Choi, S.: 3D medial axis point approximation using nearest neighbors and the normal field. The Visual Computer, roˇcn´ık 28, ˇc. 1, 2012: s. 7–19, ISSN 0178-2789, doi:10.1007/s00371-011-0594-7. [11] Ma, J.; Choi, S.: Kinematic skeleton extraction from 3D articulated models. Computer-Aided Design, roˇcn´ık 46, 2014: s. 221–226. [12] Meredith, M.; Maddock, S.: Real-Time Inverse Kinematics: The Return of the Jacobian. 2004. [13] Rodriguez, A.; Ehlenberger, D. B.; Hof, P. R.; aj.: Three-dimensional neuron tracing by voxel scooping. Journal of Neuroscience Methods, roˇcn´ık 184, ˇc. 1, 2009: s. 169–175, ISSN 0165-0270. [14] Straka, M.; Hauswiesner, S.; R¨ uther, M.; aj.: Skeletal Graph Based Human Pose Estimation in Real-Time. In Proceedings of the British Machine Vision Conference, BMVA Press, 2011, ISBN 1-901725-43-X. [15] Wang, L.-C.; Chen, C.: A combined optimization method for solving the inverse kinematics problems of mechanical manipulators. Robotics and Automation, IEEE Transactions on, roˇcn´ık 7, ˇc. 4, Aug 1991: s. 489–499, ISSN 1042-296X. [16] Yoshizawa, S.; Belyaev, A. G.; Seidel, H.-P.: Skeleton-based Variational Mesh Deformations. Computer Graphics Forum, roˇcn´ık 26, ˇc. 3, 2007: s. 255–264, doi:10.1111/j.1467-8659.2007.01047.x.

54

A Pˇr´ıloha: Obsah CD Tato pˇr´ıloha popisuje adresáˇrovou strukturu pˇriloˇzeného CD.

binary

spustitelné soubory práce a potˇrebná data

build

EXE a DLL soubory

data

modely ve formátu Wavefront OBJ

run

pˇripravené spouˇstˇec´ı skripty

doc tex source

diplomová práce ve formátu PDF zdrojové soubory bakaláˇrské práce (LaTeX) veˇskeré zdrojové soubory aplikace

blender-bones-script

exportovac´ı skript kostry pro program Blender

program

zdrojové soubory samotné aplikace

55

B Pˇr´ıloha: Uˇzivatelský manuál Popiˇsme si nyn´ı ve struˇcnosti pˇreklad zdrojov´ ych kód˚ u aplikace a jej´ı ovládán´ı.

B.1

Pˇ reklad

Aplikace byla naprogramována v jazyce C++ a sestavována pomoc´ı programu CMake a Microsoft Visual Studio. Pro pˇreklad je nutné dodrˇzet následuj´ıc´ı kroky:

1. Stáhneme a nainstalujeme program CMake (http://www.cmake.org/). 2. Stáhneme framework VTK verze 6.0.0 (http://www.vtk.org/). 3. Za pomoci programu CMake vygenerujeme projektový soubor VTK pro Visual Studio, kter´ y umoˇzn´ı pˇreklad a instalaci frameworku. Generován´ı se provád´ı klasickou cestou – zvol´ı se koˇrenový adresáˇr VTK, ve kterém se nacház´ı soubor CMakeLists.txt. 4. Vznikl´ y projekt pˇreloˇz´ıme ve Visual Studiu. y soubor diplomové 5. Za pomoci programu CMake vygenerujeme projektov´ práce pro Visual Studio. Zdrojové soubory se nacházej´ı na CD v adresáˇri source\program. 6. Vznikl´ y projekt diplomové práce pˇreloˇz´ıme ve Visual Studiu.

B.2

Parametry pˇ r´ıkazov´ eˇ r´ adky

Po pˇreloˇzen´ı m˚ uˇzeme spustit aplikaci v pˇr´ıkazové ˇra´dce parametry. Formát je ve tvaru: skeletonGenerator.exe "model.obj"[dalˇ sı ´ moˇ znosti]

56

Pˇr´ıloha: Uˇzivatelský manuál

Ovládán´ı aplikace

Jako prvn´ı parametr pˇredáváme název souboru obsahuj´ıc´ı model ve formátu Wavefront OBJ. Dalˇs´ı dobrovolné moˇznosti jsou pˇredávány vˇzdy po dvojic´ıch; prvn´ı je název, druhá hodnota parametru.

• itercount N – Smrˇst’ován´ı s´ıtˇe bude provedeno maximálnˇe N -krát. Základn´ı hodnota N = 6. • poscoeff p – Váˇzen´ı vlivu pozic pˇri smrˇst’ován´ı s´ıtˇe. Základn´ı hodnota p = 0.5. • areacoeff a – Váˇzen´ı vlivu obsahu troj´ uheln´ık˚ u pˇri smrˇst’ován´ı s´ıtˇe. Základn´ı hodnota a = 1.0. • sl s – Zesilován´ı smrˇst’ován´ı s kaˇzdou iterac´ı, kaˇzdou iteraci zes´ıleno s-krát. Základn´ı hodnota s = 2.5. • volumecoeff V – Prahový objem V , po jeho dosaˇzen´ı jsou iterace smrˇst’ován´ı ukonˇceny. Základn´ı hodnota V = 10−5 .

B.3

Ovl´ ad´ an´ı aplikace

Po dokonˇcen´ı generován´ı kostry je uˇzivateli dovolena interakce s modelem skrze vizualizaˇcn´ı okno. Popiˇsme si moˇznosti ovládán´ı tlaˇc´ıtky klávesnice: Tlaˇc´ıtko

Funkce

1

Skryt´ı/odkryt´ı vygenerované kostry.

2

Skryt´ı/odkryt´ı lokáln´ıch trojhran˚ u.

4

Skryt´ı/odkryt´ı s´ıtˇe.

5

Vizualizace kosti s nejvˇetˇs´ım vlivem (segmentace).

6

Skryt´ı/odkryt´ı smrˇstˇené s´ıtˇe.

7

Povolen´ı pruˇzn´ ych kost´ı inverzn´ı kinematiky.

mezern´ık

Reset pózy modelu.

W

Zobrazit jako drátˇen´ y model.

S

Zruˇsit zobrazen´ı drátˇeného modelu.

Taˇzen´ım myˇsi za stisku levého tlaˇc´ıtka lze rotovat s kamerou, pravé tlaˇc´ıtko ovládá pˇribl´ıˇzen´ı a prostˇredn´ı pozici kamery. Myˇs´ı lze rovnˇeˇz pˇresouvat modré ovladaˇce

57

Pˇr´ıloha: Uˇzivatelský manuál

Ovládán´ı aplikace

(nacházej´ı se v listech kostry), coˇz zp˚ usob´ı deformaci modelu s uˇzit´ım inverzn´ı kinematiky. Do konzole jsou po celou dobu bˇehu programu vypisována informaˇcn´ı hláˇsen´ı.

58

Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra informatiky a výpočetní techniky. Generování kostry objektů reprezentovaných

Recommend Documents