Applicazione di un metodo innovativo per la valutazione delle proprietà cinematiche di un robot

INTRODUZIONE
to, viene calcolata l’isosuperficie interna al volume di lavoro associata a tale valore,
al fine di individuare facilmente posizioni di buon funzionamento, caratterizzate da
elevata rigidezza e precisione. Volumi di lavoro ed isosuperfici vengono visualizzati
sulla scena 3D e possono essere sovrapposti al robot ad essi relativo, per una valu-
tazione immediata dei risultati.
Per la visualizzazione delle superfici si e` fatto uso dell’algoritmo Marching Cubes.
Relativamente alla raccolta dati si utilizzano due metodi di scansione. Il piu` tradi-
zionale prevede la semplice analisi dello spazio secondo una griglia tridimensionale
a passo regolare. Il secondo, piu` innovativo, implica una suddivisione gerarchica
dello spazio in una struttura ad albero ottale, nella quale ad ogni nodo sia associata
una regione cubica. Se questa viene intersecata da una superficie, si procede alla
suddivisione del nodo in otto nodi figli, con lato di dimensioni pari alla meta` del
lato del genitore.
Un’analisi dello spazio di tipo gerarchico permette una risoluzione accurata nelle sole
regioni di interesse, intersecate dalla superficie in esame, evitando analisi raffinate
in regioni in cui siano presenti soltanto vuoti, zone esterne alla superficie, o pieni,
zone completamente interne.
Il metodo dell’albero ottale presenta una complessita` computazionale inferiore ri-
spetto al metodo tradizionale; prove pratiche hanno mostrato significativi vantaggi
in termini di tempo di elaborazione.
In entrambi i casi e` possibile definire la precisione dell’analisi: aumentando la preci-
sione aumentano i tempi di calcolo e di rendering; analisi meno raffinate implicano
maggiori approssimazioni ma tempi inferiori.
Il software contiene un’algoritmo in grado di calcolare il profilo della superficie
trovata e salvarlo in formato dxf, importabile in ambienti CAD.
Per le caratteristiche della programmazione ad oggetti e per le prestazioni in termini
di velocita` di calcolo il linguagio scelto per l’implementazione e` il C++.
6
Capitolo 1
ANALISI DEL LAVORO
In questo capitolo vengono dapprima presentati gli obiettivi della tesi, segue una
panoramica degli argomenti analizzati allo scopo di definire le modalita` di imple-
mentazione del software.
1.1 Definizione degli obiettivi
Il presente lavoro riguarda la definizione di un metodo per la valutazione delle pro-
prieta` cinematiche di robot.
In particolare l’obiettivo principale e` lo sviluppo di un algoritmo computazional-
mente efficiente che permetta una rapida valutazione del volume di lavoro e la de-
terminazione delle zone in cui un robot si trovi ad operare in condizioni ottimali.
Oltre agli aspetti computazionali, si sono affrontate anche alcune tematiche aperte
relative alla visualizzazione tridimensionale di volumi, con particolare riferimento al
rendering di un’isosuperficie a partire da valori campionati nello spazio.
Il volume che si vuole rappresentare risulta infatti definito da una serie di disequa-
zioni. Per ottenere dati relativamente ad esso si procede tramite campionamenti,
cioe` si va a valutare se dati punti dello spazio soddisfino o meno alle disequazioni
che delimitano il volume.
I campionamenti possono provenire o da una semplice griglia tridimensionale a passo
regolare, oppure da strutture piu` complesse che consentano risparmio in termini di
memoria e di tempi di calcolo, come un octree1. Una volta stabilita la modalita` del
1Octree: octal tree, albero ottale.
7
1.2. ALGORITMO DI VISUALIZZAZIONE
campionamento, rimane l’onere di definire una superficie approssimante a partire
da un insieme di punti. Questa viene ricostruita grazie ad un algoritmo dedicato,
risultando tanto piu` vicina a quella reale quanto piu` raffinata e` la definizione del
campionamento. Definizioni piu` accurate comportano tempi di analisi e di rendering
maggiori.
Al fine di raccogliere informazioni inerenti un volume generico V, si consideri un cu-
bo iniziale di ricerca contenente V. Sul cubo si costruisca una griglia tridimensionale
formata da n nodi per ogni spigolo del cubo, della quale ci si serva per compiere dei
test sul volume, valutando per ogni nodo se questo sia interno o esterno all’isosu-
perficie. Il numero dei campionamenti risultera` pari a n3.
Pertanto all’aumentare della definizione della superficie aumenteranno in ragione
piu` che lineare gli oneri computazionali e, con questi, i tempi di calcolo. Da qui
l’esigenza di testare altre tipologie di strutture-dati per l’analisi del volume.
Figura 1.1: Oggetto-sfera entro cubo di ricerca.
1.2 Algoritmo di visualizzazione
L’algoritmo utilizzato per la visualizzazione della superficie e` noto come Marching
Cubes.
Una versione dello stesso, scritta da Cory Gene Bloyd ed etichettata come di publico
8
1.2. ALGORITMO DI VISUALIZZAZIONE
dominio, e` disponibile in rete2 ed e` alla base dell’algoritmo qui utilizzato per il
rendering. Linguaggi di alto livello come il MATLAB forniscono queste procedure gia`
implementate e con poche righe di codice e` possibile visualizzare il volume associato
ad una matrice contenente i punti campionati (si veda fig. 1.2).
Figura 1.2: Volume di lavoro e isosuperfici relative al condizionamento di un robot
S.C.A.R.A. calcolati in ambiente MATLAB.
Si e` invece scelto di operare in C++ per realizzare un programma che potesse
essere portabile, di dimensioni contenute, veloce.
Inoltre per il C++ si e` potuto utilizzare un compilatore libero: Mingw. Si sono
2
In particolare si fa riferimento all’articolo Polygonising a scalar field [1], scritto da Paul Bourke,
contenente un link al codice di riferimento. Lo stesso articolo e` qui considerato come principale
fonte per la descrizione dell’algoritmo assieme a [2]. L’articolo ed il codice in C++ sono stati
reperiti all’indirizzo http://astronomy.swin.edu.au/∼pbourke/modelling/polygonise.
9
1.2. ALGORITMO DI VISUALIZZAZIONE
utilizzate le librerie grafiche OpenGL, che garantiscono la portabilita` del programma,
in congiunzione con i pacchetti GLUT3 e GLUI4.
Le OpenGL costituiscono inoltre uno standard multipiattaforma molto apprez-
zato e gratuito, questo comporta che relativamente ad esse sia facilmente reperibile
molto materiale.
Per contro l’implementazione in C++ e` stata piu` laboriosa di quanto probabil-
mente sarebbe stata in MATLAB.
1.2.1 Marching Cubes
L’algoritmo Marching Cubes fu messo a punto da William E. Lorensen ed Har-
vey E. Cline al fine di rappresentare una superficie a partire da un campo scalare
tridimensionale di valori5. I passi base nell’implementazione dell’algoritmo sono:
• La suddivisione dello spazio in esame in una serie di piccoli cubi.
• La scansione dello spazio attraverso test nei vertici dei cubi.
• La determinazione ed il disegno di un appropriato set di poligoni che, interna-
mente a ciascun cubo, approssimino coerentemente la superficie cercata.
Marching Cubes e` dunque finalizzato alla creazione di una superficie poligonale
rappresentativa di un campo scalare 3D. L’algoritmo combina una relativa sempli-
cita` con un’elevata velocita` poiche` lavora quasi interamente su tavole di lookup.
Queste sono in sostanza tabelle precalcolate di valori che vengono interrogate in ba-
se alla configurazione trovata. Cio` comporta tempi ridotti perche´ essendo gia` state
studiate le possibili combinazioni, ci si limita a determinare a quale set di poligoni
corrisponda il caso in esame.
L’applicazione generica dell’algoritmo e` relativa alla creazione di un profilo tridi-
mensionale di un campo scalare matematico. Il campo deve essere noto dovunque
ed e` campionato nei nodi di una griglia tridimensionale regolare.
3GLUT: The OpenGL Utility Toolkit.
4GLUI: A GLUT Based User Interface Library.
5Una delle principali applicazioni dell’algoritmo e` la ricostruzione di superfici a partire da dati
di interesse medico. la scansione dovuta ad una risonanza magnetica porta infatti all’aquisizione
di dati come campionamenti nei nodi di una griglia regolare 3D.
10
1.2. ALGORITMO DI VISUALIZZAZIONE
Il problema fondamentale e` di formare un’approssimazione discreta, a facce, di un’i-
sosuperficie, attraverso i campionamenti su griglia 3D del campo scalare. Data una
cella della griglia, definita dai propri vertici e dal valore scalare assunto ad ogni
vertice, e` necessario creare le facce piane che meglio rappresentino l’isosuperficie
attraverso questa cella. L’isosuperficie potrebbe non intersecare la cella, potrebbe
escludere qualcuno dei vertici, o passare attraverso essi in complesse configurazioni.
Ogni possibilita` e` caratteristica relativa allo stato di vertici nei quali il campo puo`
assumere valori inferiori o superiori in riferimento a quello dell’isosuperficie. Se un
vertice e` esterno ad essa ed il vertice adiacente interno, allora la superficie tagliera` lo
spigolo compreso fra i due. La posizione dell’intersezione verra` determinata tramite
interpolazione lineare.
  
0 
1 
2 
3 
5 
4 
6 
7 
Indice dei vertici 
Indice degli spigoli 
0 
1 
2 
3 
4 
5 6 
7 
8 
9 
10 
11 
x 
y 
z 
Figura 1.3: Convenzione per la numerazione di spigoli e vertici utilizzata nell’algoritmo
Marching cubes.
Con riferimento a figura 1.3 per le convenzioni di numerazione, sia ad esempio il
valore al vertice 3 inferiore al valore dell’isosuperficie da determinare, ed i valori a
tutti gli altri vertici, superiori: l’algoritmo portera` allora alla determinazione degli
estremi di una faccia triangolare che tagli gli spigoli 2, 3 e 11. La posizione esatta dei
vertici della faccia dipende dalla relazione fra il valore scalare relativo all’isosuperficie
ed i valori ai vertici 0, 3, 2, 7; si veda figura 1.4.
11
1.2. ALGORITMO DI VISUALIZZAZIONE
 
0 
2 
3 
7 
3 
2 
1 
11 
Vertice 3 esterno 
all’isosuperficie

Figura 1.4: Esempio di isosuperficie intersecante una cella.
Per poter generalizzare la trattazione, per ognuna delle celle in esame, e` ne-
cessazio valutare lo stato in-out negli otto vertici, e quindi, potenzialmente, 256
combinazioni. Cio` che rende l’algoritmo complesso e` quindi l’elevato numero di
possibili configurazioni e la necessita` di determinare per ogni soluzione un insieme
coerente di poligoni affinche´ facce da celle adiacenti della griglia si connettano cor-
rettamente. L’analisi puo` essere semplificata riducendo il numero di configurazioni,
considerando che talune fra queste possono essere ottenute tramite:
• rotazioni della cella attorno ad uno dei 3 assi principali
• inversione dello stato nei vertici della cella
• riflessione rispetto ad uno dei piani principali.
Le 256 configurazioni vengono cos`ı ridotte a 15, relativamente alle quali risulta
piu` semplice la definizione di set di poligoni per la determinazione della superficie
approssimante.
La determinazione dei vertici dei triangoli che delimitano la mesh si serve di
tavole di valori precalcolati; la prima ad essere interrogata, denominata CubeEdge-
Flags, mappa gli spigoli intersecati dalla superficie in funzione della configurazione
dei vertici. I primi passi dell’algoritmo prevedono infatti la definizione di un indice
ad otto bit, FlagIndex, in cui ad ogni bit corrisponde lo stato di un vertice, con
12