Interpolazione lineare (parte prima)

Stampa
( 1 Vote ) 
Valutazione attuale:  / 1
ScarsoOttimo 
Categoria: Informatica
Data pubblicazione
Scritto da Magellano Visite: 3309

Interpolazione lineare

(parte prima)

Algoritmo per una veloce interpolazione lineare in robot cartesiani a due gradi di libertà con motori passo-passo

 Premessa

A partire da questo primo articolo voglio affrontare il problema dell'interpolazione lineare tra due punti per l'azionamento di motori passo-passo, sia in sistemi a due gradi di libertà (nel piano) sia in quelli a tre gradi di libertà (nello spazio), di tipo cartesiano (movimenti ortogonali) o articolati (bracci meccanici).



ROUTINE DI INTERPOLAZIONE LINEARE

Nel 1976 Bruce Artwick creò la prima versione di Flight Simulator per Apple e Commodore, fondò la SubLogic e poco tempo dopo vendette il software alla Microsoft. Per disegnare lo scenario 3D sia pure stilizzato per i lentissimi computer dell’epoca, egli usò un interessante algoritmo di interpolazione per tracciare rapidamente i segmenti delle immagini disegnate.

Qualche decennio fa ebbi la necessità di una routine veloce di interpolazione lineare da scrivere in linguaggio macchina per il Commodore 64 (clock a 1 MHz): il computer doveva controllare un sistema cartesiano di posizionamento con motori passo-passo per un tornio autocostruito, e la routine doveva essere scritta in linguaggio macchina. Mi ispirai allora a quanto fatto da Artwick; vediamo come.

Supponiamo di voler ottenere uno spostamento da un punto P(5,2) ad un punto Q(35,20), in modo da avere incrementi positivi. Si ha:

Dx = 30, Dy = 18

Poiché Dx>Dy, conviene tra le due coordinate incrementare prima la x; gli incrementi da usare sono 18 e 30 con due accumulatori Sx e Sy che vengono confrontati tra loro, sommando 18 ad Sx se esso è minore di Sy, incrementando contemporaneamente la x, oppure sommando 30 a Sy se esso è minore di Sx, incrementando contemporaneamente la y; in questo modo la x verà incrementata più frequentemente della y, ottenendo uno spostamento maggiore. Alla fine della procedura Sx risulterà incrementato di 30 volte e Sy di solo 18 volte, raggiungendo entrambi il valore di 540, pari a Dx∙Dy.

Se Dx∙Dy è troppo grande per essere rappresentato su un registro, si può usare un unico accumulatore sommandogli Dy quando si incrementa x e sottraendogli Dx quando si incrementa la y (in linguaggio macchina basta fare la somma di Sx col complemento a due di Dx).

x
y
Sx
Sy
Sx-Sy
5
2
0
0
0
6
2
18
0
18
6
3
18
30
-12
7
3
36
30
6
7
4
36
60
-24
8
4
54
60
-6
9
4
72
60
12
9
5
72
90
-18
10
5
90
90
0
11
5
108
90
18
...
...
...
...
...
32
19
486
510
-24
33
19
504
510
-6
34
19
522
510
12
34
20
522
540
-18
35
20
540
540
0

L’errore che si commette sul posizionamento è inferiore allo spostamento corrispondente ad un singolo passo; infatti:
- se la retta è parallela ad uno degli assi, lo scostamento dalla retta della posizione ottenuta è nullo;
- se la retta ha una bassa pendenzao un’alta pendenza, si sceglie in partenza lo spostamento in orizzontale o in verticale che corrisponde allo scostamento minore dalla retta, che ovviamente non supera l’entità di un passo; ogni successivo incremento porta al di sopra o al di sotto della retta, garantendo comunque il non superamento di tale passo;

- se la retta ha un’inclinazione di 45°, si sceglie arbitrariamente con quale incremento iniziare; se si inizia con l’incremento della x, si ottiene una sequenza di punti che alternativamente stanno sotto la retta a distanza di 0,707 volte il passo (reciproco della radice di due) oppure sulla retta; se invece si inizia con l’incremento della y, avviene il contrario: i punti che stanno fuori della retta si trovano al di sopra di essa a distanza pari a 0,707 volte il passo.

Se uno dei due incrementi Dx o Dy (o tutti e due) sono negativi, si prendono i loro valori assoluti e si procede come prima con la differenza che la corrispondente variabile viene decrementata invece di incrementarla.
Ogni curva continua può essere scomposta in una appropriata poligonale, scegliendo dei punti della curva che rendano minimo l’errore commesso approssimando la curva con tale poligonale.
Quanto detto vale per un posizionamento con robot cartesiano, in cui due motori passo-passo permettono di variare singolarmente una delle due coordinate. Ne caso di un robot articolato, occorre ragionare in moto totalmente diverso.

Nell'appendice seguente si dà una giustificazione teorica all’algoritmo adottato per la procedura di interpolazione lineare fra due punti:

 interpolazione_1.pdf