"Studio e implementazione di un algoritmo per lo skinning automatico di mesh poligonali deformabili"

U

NIVERSITÀ DI

P

ISA

F

S

M

F

N

C

I

T

Studio e Implementazione di un

Algoritmo per lo Skinning Automatico

di Mesh Poligonali Deformabili

Candidato:

Giovanni Sacchetti

Relatori:

Prof. Marcello Carrozzino

Prof. Franco Tecchia

Controrelatore:

Prof. Roberto Grossi

1

INDICE

Introduzione ... 6

Struttura della ricerca ... 7

Capitolo 1L’animazione 3D ... 9

1.1 Panoramica sui modelli tridimensionali ... 9

1.2 Metodi d’animazione ... 12

1.3 Animazione Scheletrica ... 13

1.4 Skinning ... 17

1.5 Utilizzo dei pesi (LBS) ... 19

1.5.1 Problemi dell’LBS ... 22

1.6 Obbiettivo: calcolo automatico dei pesi ... 27

Capitolo 2Tecniche di calcolo automatico dei pesi di Skinning. ... 29

2.1 Distanza Euclidea ... 30

2.1.1 Distanza Euclidea semplice ... 31

2.1.2 Problematiche della distanza Euclidea ... 33

2.1.3 Distanza Euclidea + euristiche ... 36

2

2.3 Diffusione del Calore ... 39

2.3.1 Pinocchio ... 41

2.4 Addestramento basato-su-esempi... 43

2.5 Tool per lo skinning ... 44

2.5.1 La DemoUI di Pinocchio ... 45

2.5.2 Mixamo ... 46

2.5.3 Blender ... 50

2.5.4 3D Studio Max ... 50

2.5.5 Maya ... 51

2.6 Scelta del metodo da implementare ... 51

Capitolo 3L'algoritmo di skinning automatico Atlas-Based ... 53

3.1 Overview ... 53

3.2 Fase 1: decomposizione della mesh ... 55

3.2.1 Rilevamento del confine ... 56

3.2.2 Segmentazione ... 59

3.3 Fase 2: estensione delle regioni ... 60

3.3.1 Calcolo della distanza geodetica ... 61

3.3.2 Calcolo delle aree di sovrapposizione ... 62

3.3.3 Generazione dell’area sovrapposta ... 63

3.4 Fase 3: definizione dei pesi ... 63

3.4.1 La funzione β ... 64

3

3.5 Generalizzazione del metodo ... 68

3.5.1 Generalizzazione con la distanza armonica ... 68

3.5.2 Generalizzazione con la distanza Euclidea ... 68

3.5.3 Secondo metodo di calcolo dei pesi... 71

3.6 Analisi ... 73

3.6.1 Analisi della decomposizione ... 73

3.6.2 Problematiche della decomposizione tramite singoli piani ... 77

3.6.3 Analisi della funzione β ... 79

3.6.4 Analisi del calcolo dei pesi del primo metodo... 81

3.6.5 Analisi del calcolo dei pesi del secondo metodo ... 83

3.7 Nuova decomposizione della mesh ... 84

3.7.1 Nuovo metodo di segmentazione... 87

3.7.2 Nuovo rilevamento del confine ... 89

3.8 Nuova estensione delle regioni ... 90

3.9 Nuovo calcolo dei pesi ... 92

Capitolo 4Implementazione ... 95

4.1 Librerie ... 96

4.1.1 ASSIMP - importazione ... 96

4.1.2 PINOCCHIO - strutture e sviluppo algoritmo ... 96

4.1.3 FTLK - interfaccia ... 97

4.1.4 CAL3D - esportazione ... 98

4

4.2 Fase 1: implementazione della decomposizione ... 103

4.2.1 Decomposizione - implementazione... 106

4.2.2 Rilevamento del confine - implementazione ... 110

4.3 Fase 2: implementazione dell’estensione ... 112

4.3.1 Calcolo della distanza geodetica - implementazione ... 112

4.3.2 Calcolo della distanza di estendibilità - implementazione ... 114

4.3.3 Generazione dell’area sovrapposta - implementazione ... 114

4.4 Fase 3: implementazione del calcolo pesi ... 115

Capitolo 5Risultati ... 119

5.1 Ricerca di una metrica ... 120

5.2 Costi computazionali ... 121

5.2.1 Analisi dei costi ... 121

5.2.2 Tempi d’esecuzione sperimentali ... 124

5.3 Assegnazione dei pesi coerente con la geometria ... 125

5.4 Riduzione degli artefatti ... 126

5.5 Problemi di uniformità della mesh ... 128

5.6 Confronto con Pinocchio ... 128

5.6.1 Mesh trattabili ... 129

5.6.2 Costi ... 129

5.6.3 Fasce di massima deformazione ... 130

5.6.4 Artefatti ... 131

5

Conclusioni e sviluppi futuri ... 135

APPENDICE A ... 138

LBS con quaternioni duali... 138

APPENDICE B ... 142

La decomposizione di superfici ... 142

APPENDICE C ... 144

Calcolo delle distanze geodetiche ... 144

6

Introduzione

L’animazione tridimensionale è un argomento di grande interesse in svariati ambiti, che vanno dal puro intrattenimento a più serie simulazioni. Esistono numerosissime tecniche di animazione che bilanciano in modo diverso prestazioni, qualità dei risultati, semplicità dell’approccio e possibilità di riutilizzo.

In questo scenario trova uno spazio tutto suo l’animazione di figure umanoidi, i cosiddetti Virtual Humans (VHs). Da circa 50 anni la ricerca ha prodotto una gran quantità di metodi per trattare VHs, adatti alle più diverse esigenze e occupandosi di riprodurre le molteplici sfaccettature del movimento umano. Tra i molti campi di applicazione dell’animazione umana, citiamo alcuni esempi: la simulazione per l’addestramento nell’eseguire operazioni pericolose, difficili o comunque che comporterebbero alti costi; l’analisi dell’interazione umana con oggetti ed ambienti; la creazione di attori virtuali per l’entertainment; lo studio di nuovi metodi di interazione uomo-macchina; le ricostruzioni di attività umane a scopo didattico o per riprodurre e studiare le dinamiche di eventi.

Tra i metodi per modellare il movimento di figure umane, uno dei paradigmi più diffusi si basa sull’utilizzo di due elementi: il primo è un’approssimazione dello scheletro (skeleton) che viene usato per descrivere le animazioni in modo indipendente dalla figura da animare, così da poter essere riutilizzabile con diversi modelli; il secondo è il modello da animare, che viene visto come una superficie detta pelle (skin), la quale si modifica seguendo lo skeleton. Un approccio per far si che la

7

skin si deformi secondo le ossa (bones) dello skeleton è chiamato skinning. L’algoritmo più diffuso per effettuare lo skinning nel campo delle applicazioni real-time è noto sotto il nome di Linear Blend Skinning (LBS). Tale approccio consiste nell’associare ad ogni vertice della skin un peso che varia tra 0 e 1 per ogni bones, di modo che più il bone ha influenza sul vertice più tale peso è vicino a 1. I pesi vengono poi usati in un blend lineare di trasformazioni rigide per deformare la skin.

Il settaggio dei pesi per ogni vertice avviene generalmente in modo manuale tramite l’ausilio di appositi tool, integrati in strumenti di modellazione. Quest’operazione comporta comunque un certo sforzo da parte del modellatore. Inoltre in certi applicativi si preferirebbe che la determinazione dei pesi avvenisse in modo totalmente automatico e con buoni risultati visivi, senza la necessità di intervento da parte di un modellatore esperto.

In questa tesi si analizzano i metodi più noti per il calcolo automatico dei pesi da utilizzare assieme all’LBS, di modo da ottenere una distribuzione dei pesi il più realistica possibile. Vengono quindi studiati i pregi ed i difetti degli algoritmi esistenti, quindi si propone un nuovo algoritmo per offrire una soluzione ai problemi più importanti emersi dalla precedente analisi.

Struttura della ricerca

 Il primo capitolo dà una breve spiegazione su cosa significhi animare un modello tridimensionale, su cosa sia l’animazione basata su uno skeleton e sullo skinning modellato tramite pesi ed LBS.

 Il secondo capitolo descrive le principali tecniche note per il calcolo automatico dei pesi.

 Nel terzo capitolo verrà descritto uno di questi metodi basato sul concetto di “Atlas of Chart”. Verrà data una descrizione di tutte le fasi dell’algoritmo e di

8

una sua generalizzazione più recente. A questa seguirà una dettagliata analisi delle fasi evidenziando possibili difetti, da cui poi verranno studiate nuove soluzioni per ottenere una versione rielaborata dell’algoritmo.

 Il quarto capitolo si occuperà di descrivere come il metodo rielaborato è stato concretamente implementato in un’applicazione dimostrativa.

 Nel quinto capitolo si analizzeranno i risultati ottenuti comparandoli a quelli di altri metodi.

 Infine verranno tratte le conclusioni complessive del lavoro e si indicheranno possibili sviluppi futuri.

9

Capitolo 1

L’animazione 3D

1.1 Panoramica sui modelli tridimensionali

La Computer Graphics (CG) si occupa di creare immagini ed animazioni con un computer tramite elaborazione di modelli. In particolare per quanto riguarda la CG 3D, questi modelli, sono prevalentemente descritti nello spazio tridimensionale tramite un insieme di triangoli.

Figura 1.1: triangoli immersi in uno spazio tridimensionale.

Tali triangoli vengono anche chiamati in gergo facce. Questa rappresentazione è prassi divenuta abituale per diversi motivi sia teorici che pratici. Dal punto di vista teorico possiamo dire che un triangolo è definibile tramite un buon formalismo

x y

10

essendo un simplesso 2-dimensionale1 ed inoltre offre meno casi degeneri, per esempio è sempre planare, cioè passa sempre tramite un unico piano. Dal punto di vista pratico un triangolo è rappresentabile tramite una struttura dati semplice e facile da gestire; inoltre l’hardware delle schede grafiche è fortemente orientato alla gestione efficiente di triangoli.

Per ogni faccia vengono memorizzati i 3 vertici (v1, v2 e v3) che la compongono

ed ogni vertice è memorizzato tramite le sue coordinate (x,y,z) nello spazio.

Figura 1.2: vertici di un triangolo.

Anche se non sempre, nella stragrande maggioranza dei casi ogni triangolo è posto in modo da avere ogni suo lato (detto edge) adiacente con il lato di un altro triangolo.

Figura 1.3: facendo coincidere i bordi dei 4 triangoli si ottiene la rappresentazione di una superficie solida.

In questo modo si ottengono delle superfici connesse di triangoli. Se di questi visualizziamo solo i bordi delle facce (questo tipo di visualizzazione è detta

1 _{Un simplesso è il politopo n-dimensionale col minor numero di punti linearmente indipendenti.}

Ricordiamo che un politopo d-dimensionale o d-politopo è una generalizzazione della definizione di poligono e di quella di poliedro nello spazio Euclideo reale: i poligoni sono 2-politopi (d = 2), mentre i poliedri sono 3-politopi (d = 3). Un simplesso 2-dimensionale è quindi l’inviluppo di tre punti non allineati, ovvero un triangolo.

v1(x1,y1,z1)

v2(x2,y2,z2)

v3(x3,y3,z3

11

wireframe) ci appaiono delle “reti” di triangoli e per questo tali raggruppamenti di

triangoli connessi vengono anche chiamati mesh di poligoni, o semplicemente mesh (maglie, reti)2. Una mesh triangolare rappresenta quindi un’approssimazione di una superficie reale continua.

Le facce della mesh descrivono come la luce della scena viene riflessa su una superficie (appunto triangolare in questo caso) sino ad arrivare all’occhio dell’osservatore.

Figura 1.4: trasformazione del modello in un’immagine.

La simulazione della riflessione della luce sulla superficie dell’oggetto fino all’occhio dell’osservatore dà così vita ad un’immagine ben definita.

Figura 1.5: una mesh composta da diversi triangoli connessi che rappresenta un delfino.

2 _{Essendo i triangoli dei simplessi questi raggruppamenti di triangoli sono anche noti come}

complessi simpliciali, ovvero aggregazioni di simplessi che si intersecano tra loro su facce comuni. In

un k-complesso simpliciale Σ: ogni faccia di un simplesso appartenente a Σ è a sua volta un simplesso appartenente a Σ; l’intersezione tra due simplessi appartenenti a Σ o è vuota o è a sua volta un simplesso appartenente a Σ; ogni simplesso di Σ ha massimo ordine pari a k. Una mesh di triangoli è quindi un 3-comlpesso simpliciale (k = 3).

osservatore sorgente luminosa

schermo raggi

12

1.2 Metodi d’animazione

Appare quindi evidente come le figure che si vogliono rappresentare tramite questi triangoli siano generalmente statiche, poiché le coordinate di ogni vertice sono fisse (in un dato sistema di riferimento). Le tecniche di animazione esistenti consistono nell’alterare in un lasso di tempo spezzettato, o se preferiamo discretizzato, queste coordinate, secondo diversi criteri che dipendono dalla tecnica scelta. Queste alterazioni, o trasformazioni, avvengono dunque per passi discreti: in ogni istante tempo t1, t2, t3, … si applica una trasformazione e si disegna l’immagine. Alternando

trasformazione e disegno (detto rendering) si dà l’illusione del movimento.

Figura 1.6: in ogni istante di tempo ti si applica una o più trasformazioni ai vertici della mesh.

Esistono diverse tecniche d’animazione che modificano le coordinate dei vertici, tra cui le più famose sono:

 Interpolazione tra forme. Consiste nel trasformare le coordinate dei vertici di una forma geometrica nelle coordinate di un’altra forma. Calcolando le coordinate intermedie che ogni vertice deve assumere per passare da una forma all’altra tramite una funzione di interpolazione, si ottengono tutte le trasformazioni necessarie per simulare l’animazione. Tale tecnica viene utilizzata ad esempio molto spesso per l’animazione facciale, ossia per animare mesh (o sottomesh) che rappresentano volti, poiché le espressioni del viso si basano principalmente su contrazioni muscolari e non su spostamenti ossei, mentre è meno adatta per esempio ad animare gli arti.

13

 Animazione diretta di vertici o di punti di controllo-spline. Consiste nello specificare esplicitamente le nuove coordinate che i vertici devono avere nel tempo, oppure tramite punti di controllo che descrivono curve attraverso cui i vertici devono passare.

 Deformazione basata-sulla-fisica. Consiste nel trasformare le coordinate dei vertici simulando la reazione ad eventi fisici, quali la pressione, l’urto, ecc.  Metodi basati sull’anatomia. Consiste nel deformare i vertici in modo

diverso a seconda del tipo di forma anatomica che rappresenta la mesh o parte di essa. Un esempio può essere la simulazione di effetti muscolari.

 Metodi misti basati su anatomia e fisica. Consiste nello sfruttare contemporaneamente le due tecniche sopra descritte per ottenere risultati più realistici.

 Animazione Scheletrica (o guidata dalle ossa). Sfrutta la struttura di uno scheletro approssimato per deformare una mesh secondo i suoi arti.

Queste diverse tecniche possono anche essere combinate assieme. Nel nostro caso ci concentriamo sull’ultimo metodo di animazione, l’Animazione Scheletrica, rimandando ad altri studi (Collins, et al., 2001) per una panoramica più ampia dell’animazione di personaggi.

1.3 Animazione Scheletrica

L’Animazione Scheletrica è una tecnica diffusa per deformare le forme articolate. Consiste nell’utilizzo di una struttura scheletrica aggiuntiva detta skeleton. Proprio la presenza di questa struttura sottostante rende l’Animazione Scheletrica molto diversa dalle altre forme di animazione.

Da un punto di vista ad alto livello lo skeleton è un’approssimazione di uno scheletro reale. Lo scheletro reale può essere umano, se stiamo trattando modelli umani, ma può essere di qualsiasi genere se trattiamo altre forme anatomiche o anche

14

solo parti di anatomie, come ad esempio solo la mano. Possiamo avere quindi tanti diversi tipi di skeleton, a seconda dei tipi di anatomie che vogliamo trattare. Inoltre lo skeleton è una forte approssimazione, perché in genere non riprende l’intera forma di uno scheletro reale ma solo la sua struttura e quasi sempre in un numero limitato e semplificato di componenti. In genere questa approssimazione consiste nel rappresentare lo skeleton tramite segmenti, detti bones (ossa), aventi in comune i loro vertici estremi, detti joints (giunti), che quindi legano i bones in una struttura ad albero. Come ogni struttura ad albero vi sarà quindi un joint radice, ogni joint avrà almeno un joint padre ed potrà avere più joint figli. Alla stessa maniera possiamo definire bones padri e figli (ma non un bone radice). Il numero di bones utilizzabili può variare a seconda di quanti arti mobili vogliamo e sono questi bones che vengono animate. Dunque, oltre a skeleton diversi per anatomie diverse, possiamo avere anche diversi tipi di skeleton per uno stesso tipo di anatomia.

Figura 1.7: alcuni esempi di skeleton diversi: a) umano, b) sempre umano ma di complessità maggiore e c)

animale. I segmenti rappresentano i bones, mentre i pallini sono le joints.

Lo skeleton viene poi utilizzato per simulare i movimenti reali di una certa forma anatomica.

Da un punto di vista implementativo lo skeleton altro non è che una gerarchia di trasformazioni: ogni bone descrive una trasformazione e possiamo pensarlo come la

15

definizione di un sistema di coordinate a se stante, con una estremità del bone (il joint

padre) all’origine e la lunghezza del bone distesa lungo un asse del sistema stesso.

Ogni bone di trasformazione influenza poi anche i suoi sottobones. Solitamente le trasformazioni nello spazio sono rappresentate da matrici 4 × 4 tramite l’uso di coordinate omogenee3. Tali matrici di trasformazione convertono le coordinate di un punto, che sono relative al sistema di coordinate locali del bone, in coordinate relative al sistema di coordinate del modello. Vedremo successivamente che vi sono anche altri metodi per rappresentare le trasformazioni oltre a queste matrici. Normalmente un’unica matrice di trasformazione può rappresentare la combinazione di diverse rotazioni, traslazioni e scalature. In generale comunque le trasformazioni cui sono sottoposti i bones di uno skeleton, visti i vincoli di continuità nella catena cinematica, sono per lo più rotazioni rispetto al bone padre: ogni bone figlio rappresenta una rotazione rispetto al sistema di riferimento del bone padre.

Figura 1.8: ogni bone figlio rappresenta una rotazione rispetto al bone padre.

Allo skeleton possono quindi essere legate una serie di animazioni muovendo i suoi bones. I bones possono essere animati direttamente, specificando le nuove

3

Le coordinate omogenee sono utilizzate per descrivere i punti nella geometria proiettiva. Oggetti rappresentati tramite sequenze [x0,…,xn] sono in coordinate omogenee se, quando una sequenza è multipla di un’altra, allora le due sequenze rappresentano lo stesso oggetto, cioè:  λ  K tale che [x01,…,xn1] = λ[x02,…,xn2] = [λx02,…,λxn2]. Grazie a questo strumento si possono rappresentare tutte le trasformazioni affini, ovvero tutte le composizioni di una trasformazione lineare con una traslazione, tramite operazioni su matrici. Usando quindi un unico meccanismo si semplifica l’implementazione e si possono ottimizzare le operazioni.

16

rotazioni bone per bone, oppure indirettamente, tramite ad esempio cinematica inversa, catturando le rotazione attraverso apposite tecniche.

Lo skeleton viene quindi incorporato nel modello e i vertici della mesh vengono legati ad uno o più bones. Dopo tale operazione i vertici seguono ogni trasformazione dei bones a cui sono legati. Quindi ogni rotazione di un bone implica una rotazione anche di tutti i vertici influenzati da quel bone.

Figura 1.9: esempio di skeleton immerso in una mesh. Ogni bone ha un colore diverso.

Osserviamo che la mesh non è animata direttamente, come negli altri metodi di animazione, ma indirettamente tramite il suo legame con lo skeleton, il quale è invece animato direttamente. Uno stesso skeleton può essere legato anche a diverse animazioni. Possiamo poi usare lo stesso skeleton con tutte le sue animazioni per diverse mesh anatomicamente simili. L’importanza dell’animazione scheletrica deriva da questo suo semplice modo di animare mesh aventi una certa struttura anatomica. Ciò rende tale metodo molto adatto ad esempio per l’animazione di personaggi.

Vanno anche considerate le esigenze di renderig: mentre per ambiti dove il rendering avviene off-line (per esempio la produzione di film) sono preferibili tecniche come quelle basate su simulazioni fisiche, qualitativamente migliori ma assai più pesanti, per il rendering on-line è estremamente più adatta l’Animazione Scheletrica. Questo l’ha resa tecnica dominante nel campo dell’animazione real-time, tipica di videogiochi e applicazioni interattive.

17

1.4 Skinning

In principio mesh e skeleton sono totalmente disconnessi. Dobbiamo quindi specificare come legare mesh e skeleton, ossia come la superficie della mesh si modifica con i movimenti dello skeleton. In altre parole si deve mappare il movimento articolato dello skeleton per ottenere una deformazione della superficie del personaggio. Questo avviene fissando lo skeleton alla superficie in modo che variazioni dello skeleton portino a deformazioni superficiali plausibili ed uniformi ai bones; il movimento dei bones provoca così distorsioni della mesh stessa. Proprio per questo genere di deformazione che ricorda come la pelle si stira a seconda del movimento delle ossa, la superficie viene generalmente chiamata skin (pelle) ed il processo per legare ogni vertice della skin allo skeleton è detto Skinning4 o a volte

Enveloping (Rivestimento).

Come è noto il primo articolo (Magnenat-thalmann, et al., 1988) a trattare il problema della deformazione della skin guidata da uno skeleton trattava il caso particolare della mano. Questo documento ha avuto una grande influenza e a partire da esso è stata proposta una grande varietà di metodi. Oggigiorno il metodo più comune per effettuare lo Skinning consiste nello specificare per ogni vertice a “quali” bones è legato e “quanto” vi è legato. Una rotazione è tanto più marcata ed evidente su un vertice quanto più tale vertice è legato al bone che rappresenta tale rotazione. Per esempio un vertice che si trova in prossimità di una giuntura in generale si legherà a tutti i bones incidenti sulla giuntura, in modo che la skin si deformi uniformemente

4 _{In realtà, purtroppo, c’è una gran confusione in letteratura nell’uso dei termini skinning e}

rigging. A volte, specialmente nell’ambito della modellazione, con rigging si intende un unico procedimento che si occupa sia dell’inserimento dello skeleton in una mesh, sia della determinazione dei pesi. Altre volte, in ambito di modellazione, con skinning si intende il processo di calcolo dei pesi, mentre in alcuni articoli di ricerca si intende l’applicazione dei pesi durante l’animazione, come avviene ad esempio nell’LBS. Per quanto ci riguarda in questa ricerca consideriamo il rigging come l’inserimento dello skeleton all’interno della mesh, lo skinning come l’applicazione dell’algoritmo che deforma la mesh secondo le bones e il calcolo dei pesi di skinning come il metodo utilizzato per stabilire i pesi da usare con l’algoritmo di skinning scelto.

18

attorno alla giuntura. Al contrario un vertice in cima alla testa si legherà esclusivamente al bone della testa.

Per realizzare nel concreto questi legami ogni vertice può essere quindi assegnato a uno o più bone con una serie di pesi di skinning (skinning weights) che indicano l’influenza che ha ciascuno dei bones su quel vertice. Tali pesi rappresentano quindi la quantità di influenza dei bones sui vertici. I pesi di ogni bone sono indicati con valori che variano tra 0 e 1. Tanto più il vertice è legato ad un bone, tanto più il peso di tale bone per quel vertice è vicino ad 1. Viceversa tanto meno il vertice è influenzato da un bone, tanto più il peso sarà prossimo a 0. Inoltre la somma di tutti i pesi di un dato vertice deve essere uguale a 1.

Ad esempio un vertice posizionato su un ginocchio in prossimità della rotula ed esattamente a metà tra femore e tibia, sarà equamente influenzato dal bone rappresentante il femore e da quello rappresentante la tibia e quindi assegneremo ad entrambi i bones un peso di 0,5 per tale vertice e 0 a tutti gli altri bones.

Figura 1.10: supponendo che il vertice v sulla superficie sia equamente influenzato dai due bones bf e bt, i pesi dei

due bones per tale vertice saranno: wk = ws = 0,5. Il peso del vertice per un qualsiasi altro bones j sarà wj = 0.

Notare come abbiamo accuratamente evitato di dire “un vertice equamente distante da femore e tibia”. Anticipiamo che tale asserzione infatti andrebbe forse bene in questo particolare esempio, ma non in generale. Approfondiremo il problema nel capitolo successivo relativamente ai difetti della distanza Euclidea.

bf : bone femore

bt : bone tibia joint rotula superficie

19

1.5 Utilizzo dei pesi (LBS)

Una volta stabiliti i pesi si applica un algoritmo che descrive come questi deformano, o per meglio dire trasformano i vertici. L’algoritmo, in assoluto il più diffuso nel campo dell’animazione 3D real-time, è conosciuto sotto diversi nomi, tra cui Linear Blend Skinning (LBS), Skeleton Subspace Deformazione (SSD),

Single-Weight Enveloping, Smooth Skinning, Vertex Blending e a volte (in maniera un po’

ambigua) semplicemente Enveloping. Tale algoritmo non ha una pubblicazione originale in letteratura, comunque ne esistono buone descrizioni (Praun, et al., 2000) spesso con estensioni e miglioramenti [ (Lewis, et al., 2000), (Sloan, et al., 2001), (Wang, et al., 2002), (Kry, et al., 2002), (Mohr, et al., 2003), (Mohr, et al., 2003)].

I vantaggi principali di questo algoritmo sono l’efficienza, la semplicità, il fatto che è già supportato in molti pacchetti di animazione ed infine che è implementabile su GPU. Proprio queste caratteristiche l’hanno reso l’algoritmo più popolare ed utilizzato per tutte le applicazioni real-time, come simulatori o videogame.

Brevemente: l’algoritmo consiste nel determinare la nuova posizione di un vertice combinando linearmente ogni sua trasformazione rigida dei bones che lo coinvolgono. Ad ogni vertice viene cioè associato un blend lineare pesato delle trasformazioni di ogni bone coinvolto. L’algoritmo parte da una posa di riposo o bind pose (“posa di associazione”, cosi detta perché anche usata per legare i vertici alle bones in una fase precedente all’applicazione dell’LBS) della mesh e dello skeleton. Per generare una nuova deformazione dalla bond pose, per ogni vertice, viene calcolata di volta in volta e separatamente una trasformazione diversa per ogni bone. Si prendono quindi tutte queste trasformazioni rigide e si applicano al vertice, pesandole diversamente a seconda di quanto ogni bone influenza realmente il vertice.

Nella posa di riposo ogni vertice ha posizione e ogni bone j ha trasformazione . Si determina quindi quale è la trasformazione del vertice separatamente per ogni

20

bone j, applicando la trasformazione inversa del bone j alla posizione del vertice nella posa di riposo :

Per ottenere una nuova posizione del vertice si applica la nuova trasformazione :

Quindi è la posizione del vertice quando viene spostato rigidamente con il bone j. Avremo quindi tanti vertici quanti sono i bones e tali vertici saranno le trasformazioni rigide di : una per ogni bone appunto.

Ora bisogna decidere come usare queste trasformazioni per ogni vertice. Un caso estremo è quello in cui decidiamo che ogni vertice è legato ad un solo bone k, o meglio ad una sola matrice di trasformazione. Avremo così una sola trasformazione _{e quindi un solo che coinciderà da solo con la nuova posizione del}

vertice.

Questo significa che con questa scelta estrema i vertici seguono rigidamente un solo bone e non vi è una deformazione della superficie.

Se invece si utilizza l’LBS per ottenere la posizione del vertice rispetto a più bones che lo influenzano, si usano tutte le posizioni rigide combinate con i pesi di ogni rispettivo bone. Si ottiene quindi l’equazione che definisce l’LBS e che viene applicata indipendentemente ad ogni :

21

Ponendo _{per avere una sola trasformazione, possiamo anche scrivere:}

I pesi devono essere valori normalizzati: . Notiamo inoltre che tale equazione viene applicata indipendentemente ad ogni vertice , ovvero per calcolare la nuova posizione del vertice non serve conoscere nulla di tutti gli altri vertici. Il caso delle trasformazioni rigide dei vertici è in effetti un caso particolare dell’LBS in cui per ogni vertice vi è un solo bone per cui vale e per tutte le altre bone i pesi sono uguali a 0:

Riassumendo, in modo informale possiamo dire che per generare ogni movimento si parte sempre dalla posa di riposo ( ) e si calcola la nuova posizione usando diverse trasformazioni ( ) combinandole secondo un peso che gli è stato assegnato ( ).

È possibile impostare un numero massimo di bones che influenzano il vertice. Un numero basso di bones produce deformazioni rigide e marcate; in tal caso molti pesi si annullano e quindi i pesi vanno ribilanciati portando un incremento dei pesi relativi ai bones coinvolti. Il vantaggio è che limitando il numero di bones coinvolti a 2 o 4 l’LBS si può implementare su GPU (programmando vertex shader tramite

CG-language ad esempio, un linguaggio high-level orientato allo shading che permette di

programmare ed effettuare calcoli sulla GPU) parallelizzando e velocizzando così i calcoli. Viceversa un numero elevato di bones utilizzate produce deformazioni

22

smussate che possono anche essere poco realistiche, oltre ad accentuare in certi casi problemi che vengono descritti di seguito.

1.5.1 Problemi dell’LBS

Nonostante la sua diffusione l’LBS ha numerose lacune. Per esempio tra i difetti secondari notiamo che ha un limitato potere di modellazione e non può riprodurre in modo attendibile certi effetti, come il rigonfiamento muscolare. Tuttavia tra i vari difetti i più problematici sono due: il collapsing elbow e il candy-wrapper. Entrambi questi artefatti causano delle perdite di volume, ovvero il volume attorno al joint si riduce in modo innaturale. Il collapsing elbow (gomito collassante) avviene quando un arto viene piegato molto.

Figura 1.11: perdita di volume dovuta ad un piegamento eccessivo (collapsing elbow).

Il candy-wrapper (incarto di caramella) avviene quando un arto si torce.

23

Entrambi sono causati dal fatto che l’LBS sfrutta una combinazione lineare di matrici di rotazione che, quando si usa un grande angolo di rotazione tra loro, comportano inevitabili perdite di volume. Questo perché l’interpolazione lineare di matrici è diversa dall’interpolazione lineare delle loro rotazioni e così le articolazioni tendono a collassare.

Prendiamo per esempio un vertice influenzato da due soli bones con il medesimo peso, quindi con . Supponiamo di effettuare rotazioni solo attorno all’asse y: una matrice di trasformazione per tale rotazione ha forma:

dove è l’angolo di rotazione applicato. Teniamo fisso uno dei 2 bones, per esempio il primo ( ). Dunque la rotazione applicata da tale bone è di 0 gradi, mentre ruotiamo l’altro bone ad esempio di 90 gradi. L’interpolazione lineare delle matrici sarà:

Notiamo come la matrice di trasformazione del primo bone non sia altro che l’identità ( .

24

Interpolando invece la rotazione della prima matrice che è di 0° e la rotazione della seconda matrice che è di 90°, si avrebbe una rotazione di 45° (sempre attorno all’asse y) che è definita dalla seguente matrice di rotazione:

Tale matrice è ovviamente diversa da quella ottenuta precedentemente tramite l’interpolazione delle matrici sfruttata dall’LBS.

Dunque interpolando linearmente le matrici si ottiene una matrice diversa da quella che si otterrebbe interpolando le rotazioni. Un’ulteriore analisi delle perdite di volume dovute all’uso di matrici di rotazione nell’LBS è descritta nella prima parte dell’APPENDICE A.

Figura 1.13: v1 indica la posizione del vertice secondo una trasformazione rigida rispetto al bone b1,

mentre v2 indica la posizione del vertice secondo una trasformazione rigida rispetto al bone b2.

La combinazione di queste due trasformazioni rigide da la nuova posizione v e genera una perdita di volutme.

Ciò significa che l’LBS funziona abbastanza bene per angoli di rotazione minori, mentre dà problemi per angoli grandi di rotazione. È da notare anche che maggiore è il numero di bones che coinvolgono un vertice con un peso non irrilevante, maggiore sarà anche il collasso quando queste ruotano tutte assieme (vedremo come questo è spesso evidente in zone come l’inguine: zona normalmente influenzata dai bones delle cosce e del bacino, i quali solitamente ruotano molto tra loro).

25

Come abbiamo detto esistono numerosi varianti dell’LBS che mirano a risolvere o quantomeno a ridurre questi difetti. Di seguito ne citiamo alcuni con una breve descrizione:

 Innesto di muscoli. (Wang, et al., 2010)

Si inseriscono meccanismi per simulare il gonfiamento muscolare. Questo è un ibrido tra i metodi basati su anatomia e l’LBS standard. Ha il vantaggio di essere implementabile su GPU e la qualità aumenta, tuttavia aumentano anche i costi.

 Uso di reticoli (Chen, et al., 2011).

Tramite un reticolo di supporto formato da voxel5 si può velocizzare lo skinning, applicare deformazioni secondarie e preservare lo spessore del volume. Il problema cardine di questo metodo è la scelta della granularità dei voxel.

 Interpolazioni non-lineari.

Come spiegato i problemi dell’LBS sorgono poiché l’interpolazione lineare di matrici è diversa dall’interpolazione delle loro rotazioni. Con questi metodi si sfruttano quindi interpolazioni non-lineari per superare i difetti. Questa categoria di metodi è comunque meno efficiente dell’LBS standard.

- Bone aggiuntivi o interpolazione sferica (Mohr, et al., 2003).

Si introducono pseudo-bones che vengono ruotati di metà dell’angolo di rotazione della giuntura. Questa è un’interpolazione sferica, non lineare e permette di evitare artefatti di collapsing elbow. Per di più si possono introdurre pseudo-bones per avere anche scalature piuttosto che rotazioni, così da supportare effetti di rigonfiamento muscolare. Il vantaggio di questo metodo è che viene alterato solo il modello dello skeleton, e non

5 _{. La voxellizzazione di un volume consiste nell’approssimare il volume stesso tramite dei cubi di}

dimensioni identiche; tali cubi sono appunto chiamati voxel (contrazione di volumetric pixel o

26

l’LSB. Tuttavia, il numero di influenze ossee per vertice aumenta, il che riduce le prestazioni di rendering e può anche rendere impraticabile l’accelerazione hardware (poiché, nella programmazione della GPU, si può passare solo un numero fisso di attributi per vertice).

- Operatore di fusione di matrici (Magnenat-Thalmann, et al., 2004). Utilizzando un operatore di fusione tra matrici come quello descritto in “Linear combination of transformations” (Alexa, 2002) per eseguire l’interpolazione. In tal modo si migliorano i risultati a discapito dei costi. - Spherical Blend Skinning o quaternioni duali (Zhai, et al., 2011).

Si calcola un’interpolazione lineare di quaternioni anziché di matrici (si veda APPENDICE A). I risultati sono meno precisi dell’interpolazione sferica e si trattano solo rotazioni, ma il costo computazionale è più basso.

 Pesi aggiuntivi.

Sono metodi che aumentano il numero di pesi utilizzati nell’equazione dell’LBS.

- MWE: MultiWeight Enveloping (Wang, et al., 2002).

I pesi scalari vengono sostituiti con matrici di peso 44. I pesi aggiuntivi producono effetti non-lineari; si hanno così gradi di libertà aggiuntivi che evitano molti dei difetti dell’LSB. Di contro il metodo necessita di più memoria, più banda e tempi maggiori.

- AS: Animation Space (Merry, et al., 2003).

Ogni peso è sostituito da un vettore di 4 componenti, similmente all’MWE ma con un numero di pesi tre volte inferiore. Anche se il numero di pesi aumenta comunque di 4 volte non è più necessario memorizzare la posa di riposo. Allo stesso modo l’overhead dovuto ai parametri in più si bilancia col fatto che il metodo necessita di una moltiplicazione scalare in meno dell’LBS standard.

Alcune di queste tecniche possono essere anche combinate tra loro per bilanciare qualità ed efficienza. Tra tutte abbiamo deciso di rifarci alla famiglia di metodi che

27

sfruttano interpolazioni non-lineari, in particolare ai metodi che utilizzano quaternioni per descrivere rotazioni. Tali metodi bilanciano bene qualità ed efficienza. Questa scelta è stata fatta anche per la disponibilità di codice già pronto, orientato all’uso di quaternioni per animazioni scheletriche. Un approfondimento dell’uso di quaternioni si può trovare in APPENDICE A.

1.6 Obbiettivo: calcolo automatico dei pesi

Il lavoro svolto in questa tesi rientra in un progetto più ampio. Il progetto complessivo mira a creare un’estensione del framework XVR (eXtreme Virtual Reality) (Carrozzino, et al.). Questo è un ambiente di sviluppo integrato per l’implementazione veloce di applicazioni per ambienti virtuali sviluppato da VRMedia. Usando un’architettura modulare e un linguaggio di scripting proprio, attualmente, XVR è una componente ActiveX che può essere incorporata in molte applicazioni, come ad esempio il browser web Internet Explorer. ActiveX è infatti una tecnologia che permette l’estensione di potenzialità di applicazioni, come comandi, funzionalità e caratteristiche. Il linguaggio di programmazione di XVR è simile al C++ e possiede vari costrutti e comandi appositamente creati per applicazioni di realtà virtuale, come animazioni tridimensionali, effetti sonori posizionali e interazioni dell’utente. Inoltre è possibile espandere XVR attraverso moduli aggiuntivi che ne aumentano le funzionalità. Un esempio è il modulo HALCA che consente di visualizzare e gestire avatar conformi al formato CAL3D.

L’estensione che puntiamo a creare per XVR permetterà di generare in modo automatico avatar tridimensionali possibilmente simili agli utenti, per poter poi utilizzare tali avatar in una o più applicazioni di simulazione grazie appunto al modulo HALCA. Per fare ciò, come prima cosa, la nostra estensione dovrà acquisire tramite un dispositivo di scansione tridimensionale una mesh e calcolarne opportunamente il relativo skeleton dell’utente, quindi dovrà legare lo skeleton alla mesh calcolando in

28

maniera automatica i pesi, ed infine caricherà l’avatar nell’applicazione, che poi verrà usato insieme ad un sistema di animazione (o tramite animazioni predefinite o tramite l’acquisizione real-time dei movimenti dell’utente con uno strumento di motion capture). In particolare ciò che ci prefiggiamo in questa ricerca è quindi trovare un metodo per legare la mesh allo skeleton, ossia un metodo possibilmente automatico di calcolo dei pesi, che riesca a fornire risultati soddisfacenti.

Nell’ambito di questa tesi daremo per già acquisiti e presenti sia la mesh e che il relativo skeleton, attraverso operazioni che avverranno in una prima fase nella quale verrà chiesto agli utenti di mettersi in una posa specifica per l’acquisizione della loro immagine, ad esempio in T-pose (cioè dritti, in piedi e con le braccia allargate orizzontalmente in modo da formare appunto una T con il corpo), oppure in A-pose (con gambe leggermente divaricate e braccia allargate), o in una posa ibrido tra la A-pose e la T-A-pose, o comunque in una posa dove gli arti siano ben separati e distinguibili.

Figura 1.14:la figura a sinistra è in T-pose, mentre quella a destra è in A-pose.

Inoltre si suppone che gli utenti non indossino né tengano oggetti troppo complessi, così da garantire una buona acquisizione della mesh. Date queste premesse possiamo fare delle assunzioni sulle mesh che ci semplificano il problema: mesh e skeleton sono in una posa standard, sono antropomorfi e lo skeleton è già perfettamente inserito all’interno della mesh. Trattiamo quindi mesh con relativi skeleton di esseri umani in una posizione standard.

29

Capitolo 2

Tecniche di calcolo

automatico dei pesi di

Skinning.

Il nostro lavoro è focalizzato sul calcolo automatico dei pesi per lo skinning. Ovvero trattiamo le tecniche più conosciute per calcolare per ogni vertice i pesi di ogni bone, in maniera automatica o semi-automatica.

Trovare questi pesi non è semplice. Com’è ovvio l’assegnazione manuale dei pesi risulta eccessivamente onerosa per un qualsiasi modellatore, basti pensare a mesh composte da milioni di vertici. Tutt’oggi, anche quando aiutati da un supporto automatico, gli animatori spesso sono costretti a ritoccare a mano i valori dei pesi calcolati, il che può essere comunque un’operazione noiosa e che porta via molto tempo ed energie. Nel nostro particolare caso poi cerchiamo un metodo che dia risultati soddisfacenti in maniera più automatica possibile.

30

Ci sono diverse proprietà che desideriamo per i pesi. In primo luogo vorremmo un’assegnazione geometricamente coerente, per esempio ci aspettiamo che un vertice sulla fronte sia prevalentemente legato al bone corrispondente alla testa e sia totalmente slegato da altri bones come quelli dei piedi, delle gambe o delle mani. Un’altra proprietà che vogliamo è che i valori dei pesi non devono dipendere dalla risoluzione della mesh. Inoltre, per ottenere buoni risultati visivi, i pesi devono variare dolcemente lungo la superficie. Infine, per evitare artefatti di piegatura (collapsing elbow), la larghezza di una transizione tra due bones che si incontrano in un joint dovrebbe essere approssimativamente proporzionale alla distanza tra il joint e la superficie: in questo modo infatti come vedremo tali artefatti, inevitabili per la natura intrinseca dell’LBS standard, vengono in un qualche modo mascherati.

Nella nostra ricerca abbiamo individuato principalmente 4 metodi basati su: 1. Distanza Euclidea.

2. Distanza Geodetica. 3. Diffusione del Calore.

4. Addestramento basato-su-esempi

Ognuno di questi metodi si limita a calcolare i pesi per lo skinning ed è quindi integrabile con qualsiasi estensione dell’LBS citata sopra. Per evitare confusione, esprimeremo nelle formule l’indice di un vertice tramite i e l’indice di un bone tramite

j, anche quando magari nei documenti originali l’uso degli indici è invertito o

comunque diverso.

2.1 Distanza Euclidea

Parlando di distanza Euclidea in realtà più che di un metodo parliamo di una famiglia di metodi. Ci sono diversi modi infatti di utilizzare la distanza Euclidea per calcolare i pesi. Questi metodi risultano in assoluto i più semplici e veloci rispetto alle

31

altre alternative, sia in termini di realizzazione che in termini di costo. Essi si fondano sul principio secondo cui “un vertice è maggiormente influenzato dai bones ad esso più vicini”. Per questo tali metodi sfruttano la distanza Euclidea per stabilire la vicinanza di un bone al vertice. Il peso del bone sarà inversamente proporzionale alla distanza, dopo di che si normalizzano i pesi rendendo la loro somma pari ad 1.

2.1.1 Distanza Euclidea semplice

Come abbiamo detto esistono diverse formule che sfruttano la distanza Euclidea. Di seguito indichiamo con il peso di un bone j su un vertice fissato ed indichiamo con la distanza Euclidea tra il vertice e il bone j.

Una formula basata sulla distanza Euclidea dai bones è la seguente (Wang, et al.):

In questo caso è calcolato come un rapporto: al denominatore abbiamo la somma di tutte le distanze da tutti i bones coinvolti moltiplicato il numero di bones coinvolti, mentre al numeratore abbiamo la somma di tutte le distanze da tutti i bones escluso il bone corrente j.

Altri approcci circondano ogni bones con involucri detti capsule interne e capsule

esterne e sfruttano la distanza Euclidea in modo diverso a seconda della posizione dei

vertici rispetto a queste capsule (Komura). Se il vertice è dentro solamente ad un singola capsula interna, il peso per il corrispondente bone è settato a 1, mentre per tutti gli altri bones è 0. Se il vertice si trova dentro più capsule interne, viene calcolata la distanza da ogni bone e i pesi vengono poi impostati con un valore inversamente proporzionale alla distanza (poiché una distanza maggiore indica minor peso) tramite normalizzazione:

32

Infine se il vertice è dentro la capsula interna di un solo bone di indice s e nelle capsule esterne di altri bones, si utilizza nuovamente la distanza, ma con una funzione di caduta di forza (fall-off function):

e fall-off function:

Figura 2.1: il vertice v è dentro ad un’unica capsula interna, quella di b1, quindi avremo e ; il

vertice v' è dentro a più capsule interne, quindi verranno usate le semplici distanze Euclidee ottenendo

e

; il vertice v'' è dentro alla capsula interna di b1 e dentro la capsula esterna di b2,

quindi verrà usata la funzione di fall-off ed i pesi saranno e .

Vi sono anche metodi che tengono in considerazione la lunghezza dei bones, per esempio (Dominio, 2010):

dove  IR è la distanza (norma Euclidea) del vertice i dal bone j e σ  IR è un valore proporzionale alla lunghezza del bone.

Poco più avanti, parlando di euristiche, vedremo ancora un’altra formula parametrizzabile (su un valore α). Inoltre, nel terzo capitolo, vedremo che nella

capsula esterna di b1 capsula interna b1 b1 b2 v'' _v' v capsula interna b2 capsula esterna di b2

33

generalizzazione del metodo basato su Atlante di Carte il calcolo dei pesi può essere applicato con qualsiasi distanza, compresa l’Euclidea (ereditandone pregi e i difetti).

2.1.2 Problematiche della distanza Euclidea

Nonostante la distanza Euclidea sia usata molto spesso come metodo per calcolare i pesi per la sua estrema elementarità, essa presenta diversi difetti. Questi difetti derivano dal fatto che la distanza Euclidea non tiene conto della geometria o, se preferiamo, dell’anatomia del soggetto. Infatti l’asserzione di fondo non sempre è verificata: non è detto che un vertice debba essere maggiormente influenzato dai bones ad esso più vicini.

Il caso più evidente in cui questo approccio fallisce capita quando si da influenza maggiore ad un bone a cui il vertice non appartiene anatomicamente. Si pensi ad esempio ad un personaggio con una pancia grossa ed un braccio più sottile steso lungo il fianco: in questo modello se prendiamo un vertice nella parte più esterna della pancia, sul fianco, questo risulterà più vicino al bone del braccio che al bone dell’addome. Così, nonostante il vertice appartenga al fianco avrà peso maggiore il bone del braccio e non un bone del fianco.

Figura 2.2: i vertici sul fianco sono più vicini ai bones sul braccio che ai bones del fianco stesso.

34

Per lo stesso motivo le parti di superficie dove si ripercuote maggiormente la flessione dell’arto possono non corrispondere esattamente alle zone che ci aspetteremmo. In pratica si individuano aree di massima flessione poco realistiche.

Figura 2.3: nella figura destra la fascia nera contrassegna la parte di superficie di maggiore flessione individuata

tramite la distanza Euclidea. Tale area non è la più anatomicamente adatta come superficie di maggior flessione, come potrebbe essere invece quella indicata nella figura a destra.

Questo non è un grosso errore dal punto di vista matematico, né per la morbidezza del risultato, ma è poco realistico dal punto di vista anatomico. Per esempio nel caso il modello abbia un torace molto più ampio rispetto alle braccia (cosa che si verifica naturalmente nell’anatomia umana), muovendo un braccio si potrebbe generare una flessione della superficie non esattamente corrispondente alla zona dell’ascella, ma leggermente spostata da questa.

Figura 2.4: la distanza Euclidea individua una zona di massima flessione non precisamente sull’ascella, ma più

spostata: questo comporta una deformazione non realistica per l’anatomia quando l’arto viene mosso.

Anche quando si riesce a far si che un vertice venga pesato maggiormente dal suo bone principale si possono creare problemi. Ad esempio se il modello è in T-pose le

35

gambe sono molto vicine tra loro e dunque, anche se la distanza Euclidea per ogni vertice ci garantisce (in questo caso giustamente) che il bone più vicino è quello più influente, i bones di una gamba finiranno per influenzare molto i vertici dell’altra ed anche se tale influenza è minore rispetto a quella del bone principale in realtà dovrebbe essere totalmente nulla, dato che gli arti sono completamente separati.

Figura 2.5: i bones della gamba destra influenzano troppo i vertici della gamba sinistra a causa della loro

vicinanza nonostante le due gambe siano totalmente separate e quindi la gamba si deforma in modo irrealistico.

Tutte queste anomalie in realtà sono manifestazioni dello stesso unico difetto: nel calcolare la distanza Euclidea, si valuta solamente il singolo vertice e i bones, ma non si tiene conto in alcun modo della geometria e dell’anatomia del modello. Esiste un video (Roselle, 2012) che mostra questi difetti in un’implementazione per Maya, oltre a come questi vengono risolti dal metodo della diffusione del calore che descriveremo in seguito.

D’altro canto non considerare la geometria può portare anche alcuni vantaggi sotto altri aspetti: le mesh non devono per forza essere manifold6, chiuse e completamente connesse per garantire la navigabilità (elementi che, come vedremo,

6 _{Una superficie manifold è una superficie in cui ogni punto ha un intorno locale topologicamente}

ad un disco unitario. In oggetti manifold dunque gli edge possono appartenere al massimo solo a due facce. L’utilizzo di mesh manifold comporta diversi vantaggi. Ad esempio un contorno manifold separa in modo non ambiguo una regione interna da una esterna. Inoltre consentono l’utilizzo di rappresentazioni della mesh efficienti per la sua navigazione topologica.

36

sono invece spesso necessari in altri metodi). Addirittura questi metodi possono funzionare anche su mesh dove ogni faccia è una tripla di vertici a-sé-stante (una nuvola di facce). Questo avviene perché, non considerando per forza la geometria, il legame tra un bone ed un vertice è sempre definibile e calcolabile. La stessa cosa non vale per altri metodi, a meno che non si sfruttino opportune strategie, come ad esempio la voxellizzazione (in realtà in certe implementazioni degli altri metodi viene usata, ma non in modo mirato a superare questo problema, tant’è che in tali implementazioni vengono comunque richieste mesh completamente connesse).

2.1.3 Distanza Euclidea + euristiche

Per ovviare a questi inconvenienti in genere gli sviluppatori ricorrono ad euristiche per correggere almeno gli errori più evidenti, che comunque migliorano la situazione solo superficialmente.

In “Local Volume Preservation for Skinned Characters” (Rohmer, et al., 2008) ad esempio si utilizza il seguente approccio. Intanto per calcolare il peso di un bone j su un vertice i, si sfrutta la seguente formula:

dove è la distanza Euclidea tra il bone j ed il vertice i, è la lunghezza del bone ed α è un valore tale che α > 0. Il metodo è quindi parametrizzabile tramite α.

Per correggere eventuali assegnamenti anatomicamente sbagliati si resetta il peso a 0 nel caso in cui il raggio tra il vertice i e il bone j su cui è calcolata la minima distanza Euclidea esca dalla mesh.

37

Figura 2.6: il raggio dal vertice pk al bone j esce dalla mesh, quindi il peso di j per pk viene resettato a 0.

Per stabilire quando ciò avviene si potrebbe usare un algoritmo di ray-tracing7 che però risulterebbe pesante. In alternativa al ray-tracing gli autori utilizzano un’approssimazione confrontando il prodotto scalare tra il raggio e la normale8 alla superficie. Quando l’angolo tra queste due direzioni è troppo piccolo si assume che il raggio esce dal dominio del corpo ed il valore di viene resettato a 0.

Figura 2.7: utilizzo della normale nk per stabilire se il raggio dal vertice pk al bone j esce.

Con quest’approccio (che sia basato su ray-tracing o su normale) possono comunque presentarsi vertici non raggiungibili con nessuno dei raggi minimi, si pensi ad esempio ad un vertice su un lobo di un orecchio. In questo caso si utilizza un’euristica: si considerano tali vertici della mesh come parti rigide e dunque si setta ad 1 il peso di skinning associato con il bone più prossimo. Infine tutti i pesi di uno stesso vertice vengono normalizzati a 1.

7 _{Il ray-tracing è una tecnica di calcolo di un percorso in un ambiente ed è solitamente utilizzato}

per tracciare i raggi della luce. Nel nostro caso il percorso che ci interessa tracciare è definito dal raggio minimo tra il vertice e il bone. Solitamente tale algoritmo è abbastanza costoso.

8 _{La normale è un attributo della superficie che specifica in che modo la luce viene riflessa sulla}

superficie stessa. Può quindi essere usata per stabilire qual è il versante della superficie rivolto verso l’esterno del volume.

38

Tuttavia la correzione effettuata può comunque dare dei risultati poco uniformi nel caso di skin molto rugosa. In questi casi infatti le normali di vertici vicini tra loro possono anche avere direzioni molto diverse e quindi coinvolgere bones diversi. Questo si è dimostrato quindi un approccio efficace nel caso di superfici morbide ed uniformi, ma non per superfici irregolari. In tali casi la correzione dovrebbe essere effettuata a mano, oppure bisognerebbe applicare l’algoritmo su una versione semplificata della skin. Inoltre come soluzione si tiene conto dell’anatomia, ma solo per l’esclusione di bones non coinvolti. Il metodo continua quindi ad avere un’individuazione delle fasce di massima deformazione non anatomicamente ottimale.

2.2 Distanza geodetica

Questo metodo verrà approfondito più avanti, per questo ora diamo solo un’infarinatura dei principi su cui si basa. Come descritto in “Atlas-Based Character Skinning with Automatic Mesh Decomposition” (Lu, et al., 2008), tale metodo sfrutta la distanza geodetica ispirandosi alla nozione di Atlante di Carte. Un atlante in topologia descrive come uno spazio complesso, nel nostro caso una mesh, sia formato da pezzi più semplici, detti appunto carte. Questo approccio si basa quindi su un atlante, cioè una segmentazione o decomposizione della mesh in parti chiamate carte (o anche patches, pezze o come le chiameremo noi regioni) disconnesse. La decomposizione è fatta sulle joints dello skeleton: tramite le joints si ritaglia la mesh e si dividono i vertici nelle varie patches.

Una volta segmentata la mesh abbiamo i boundaries (bordi, confini) di ogni regione. Partendo da questi bordi possiamo muoverci sulla superficie della mesh e raggiungere tutti i vertici calcolando la distanza geodetica. Questa è la minima distanza necessaria a raggiungere due punti muovendosi e scorrendo sopra una superficie. Proprio grazie a ciò questo metodo tiene conto intrinsecamente della geometria e dell’anatomia del modello ed evita i problemi della distanza Euclidea.

39

Ovviamente il costo è maggiore rispetto ai metodi basati su distanza Euclidea, ma ha comunque costi accettabili e la semplicità è notevole. Dunque è un buon compromesso tra bontà dei risultati e semplicità.

2.3 Diffusione del Calore

Un metodo che sta riscontrando molto successo si basa su un modello di diffusione del calore volumetrico (volumetric heat diffusion). Questo metodo utilizza un sistema di temperatura sfruttando l’analogia con l’equilibrio del calore per trovare i pesi.

Figura 2.8: la figura sopra rappresenta l’equilibrio del calore per due bones;

la figura sotto mostra i risultati dopo una deformazione.

Praticamente il volume del personaggio viene trattato come un corpo conduttore di calore isolato ed ogni bone come un filamento che genera calore. Si forza quindi la temperatura su un bone j ad 1, mentre per tutti gli altri bones viene posta a 0. Dopo di ciò si diffonde il calore attraverso il modello.

La diffusione può essere realizzata ad esempio sul modello voxellizzato per facilitare l’operazione (Rosen, 2009).

40

Figura 2.9: la mesh viene approssimata tramite una serie di cubi di dimensione identica

che riempiono completamente il volume (voxellizzazione).

Per ogni voxel impostiamo il calore con una media pesata tra il calore dei suoi vicini. Ripetiamo il procedimento fino a quando il calore non si diffonde completamente. Dunque per ogni vertice i prendiamo come peso di j la temperatura di equilibrio sulla superficie. Alla fine la distribuzione del calore è proporzionale al percorso più breve dal bone ad un qualsiasi punto del modello. In questo modo possiamo ottenere i pesi per ogni vertice confrontando il calore da ogni bone ad ogni vertice.

41

2.3.1 Pinocchio

Una tassellatura completa del volume può rallentare il procedimento. Per questo motivo un’ implementazione dell’heat diffusion in una libreria chiamata Pinocchio, risolvone l’equilibrio solo sopra la superficie (Baran, et al., 2007), ma ad alcuni vertici aggiunge poi il calore trasferito dal bone più vicino. L’equilibrio sopra la superficie per il bone j è dato dalla formula riscrivibile come:

Dove:

 ∆ è la superficie Laplaciana discreta calcolata con la formula della cotangente (Meyer, et al., 2003)

 è un vettore tale che: se j è il bone più vicino al vertice i, e altrimenti

 H è la matrice diagonale con Hii rappresentante il peso del contributo di calore del bone più vicino al vertice i.

Siccome ∆ ha unità di lunghezza–2, lo stesso vale per H.

Per ogni vertice i viene quindi calcolata la distanza da ogni bones e si prende la minima d(i), identificando così anche quale sia il bone più vicino. A questo punto si utilizza un campo di distanza (calcolato in precedenza per effettuare anche il rigging) per stabilire se il segmento dal vertice al bone più vicino è completamente all’interno del volume del personaggio. Se ciò avviene si prende la distanza dal vertice i al bone più vicino d(i) e si pone , mentre si prende se il segmento passa

al di fuori della mesh. Il termine c è una costante per la quale, per valori del tipo c ≈ 0.22, il metodo ritorna pesi con transizioni simili a quelle calcolate trovando l’equilibrio sul volume. Pinocchio usa c = 1, corrispondente ad una diffusione di calore anisotropa, ossia che segue la direzione del bone. In questo modo i risultati

42

sembrano più naturali. Quando k bones sono equidistanti dal vertice j, vengono usati tutti i loro contributi di calore: = 1/k per ciascuno dei k bones e si ha .

L’equazione del calore sopra definita è un sistema lineare sparso e osserviamo che la matrice a sinistra non dipende dal bone j per il quale stiamo calcolando il peso. Per questo si può fattorizzare il sistema una volta per tutte e sostituire all’indietro per trovare i pesi per ogni bone. Come descritto in “Efficient linear system solvers for mesh processing” (Botsch, et al.) si può usare un risolutore sparso di Cholesky9 per calcolare la fattorizzazione per questo tipo di sistema. Pinocchio sfrutta la libreria TAUCS (Toledo, et al., 2003) per effettuare tale calcolo. Si noti che per ogni vertice la somma dei pesi da 1:

Gli autori aggiungono anche che il metodo è leggermente velocizzabile trovando i vertici che sono non-ambiguamente attaccati ad un unico bone e forzando il loro peso ad 1. Tuttavia asseriscono anche di aver implementato una variante di questo genere in precedenza, ma che tale soluzione portava miglioramenti trascurabili, tra l’altro introducendo occasionalmente artefatti.

Questo metodo dà dei risultati molto buoni, è assai più affidabile del metodo della prossimità dei vertici basato su distanza Euclidea e fornisce distribuzioni di peso lisce e realistiche. Di contro si ha una maggiore complessità nell’implementazione e nel costo. Inoltre, poiché la diffusione del calore in Pinocchio parte dai bones, diventa

9

In generale il metodo di Cholesky viene utilizzato per risolvere sistemi lineari descritti tramite matrici simmetriche e definite positive. Un risolutore sparso di Cholesky ottimizza questo metodo alla trattazione di matrici sparse (Franco, 2009).

43

preponderante l’anatomia dello skeleton invece di quella del modello. Di conseguenza le fasce di massima deformazione non sono sempre ottimali e in certi casi si perde parte dell’anatomia della mesh.

2.4 Addestramento basato-su-esempi

Questo metodo è descritto in molti articoli [ (Merry, et al., 2003), (Mohr, et al., 2003), (Wang, et al., 2002), (Jacka, et al., 2007)]. Rispetto agli altri metodi esaminati ha un approccio totalmente diverso al problema. Sfrutta infatti un database pre-calcolato di esempi creati manualmente da un artista o generati automaticamente da un sistema di modellazione basato-sulla-fisica, come quello sfruttato da Kry, James e Pai (Kry, et al., 2002). Come sappiamo tali metodi danno risultati di altissima qualità, ma il loro costo a run-time sarebbe esagerato. Tuttavia questi modelli ci servono solo per generare alcune pose che useremo per trovare i pesi; una volta stabiliti i pesi, sia i modelli del database che i metodi usati per generarli vengono completamente dimenticati e si utilizza l’LBS classico (o una sua estensione).

Il database è un set di mesh in alcune posizioni che rappresentano in qualche modo il risultato ottimale che vorremmo ottenere quando applichiamo l’LBS. Questo è quindi un approccio guidato dal risultato. Quello che si cerca di fare è “addestrare” l’LBS impostando i pesi in modo che forniscano il fit geometrico più vicino possibile al set di esercitazione di pose d’esempio. In pratica si prende una posa d’esempio dal database, si applica l’LBS per mettere la posa di riposo nella stessa posizione di quella d’esempio, dopo di che si guarda di quanto i vertici tra le due pose non coincidono memorizzando le differenze dei vettori e infine si tenta di correggere l’errore, ad esempio impostando un sistema di equazioni. Risolvendo quindi il sistema troviamo i pesi. Tale sistema avrà probabilmente più condizioni che variabili e può quindi essere

44

risolto tramite un solutore di minimi-quadrati10 per fornire un’approssimazione che dia risultati più vicini agli esempi.

Un problema di questo metodo si evidenzia soprattutto quando il numero dei pesi è grande. Può capitare infatti che ad alcuni pesi venga data poca considerazione dalle pose esemplari. Ad esempio questo può verificarsi quando vi sono pose d’esempio in cui il movimento di un giunto giace su un piano. In tal caso il modello che dà il fit più vicino al set di esempi potrebbe causare problemi quando l’articolazione si muove per tutta la sua ampiezza. Per superare questo problema si introducono dei parametri che regolano in modo diverso i valori dei pesi non determinati e di quelli determinati.

La qualità è indubbiamente alta ed è possibile ottenere anche effetti secondari. Il problema principale è che le pose d’esempio devono essere scelte con cura per evitare problemi. Inoltre il metodo non è scalabile e i tempi per calcolare i pesi e la qualità dei risultati crescono col numero di pose d’esempio del database.

2.5 Tool per lo skinning

Esistono anche software dedicati ad effettuare lo skinning ed anche i più famosi programmi di modellazione (3D Studio Max, Maya e Blender) hanno propri metodi di generazione (semi-)automatica dei pesi. In tutti questi software spesso le operazioni di skinning sono abbinate anche al rigging.

10 _{Il metodo dei minimi quadrati è metodo che permette di trovare una funzione, nota come curva}

di regressione, che il più vicina possibile ad un insieme di dati (tipicamente punti del piano). Tale