Breve descrizione degli algoritmi utilizzati

ALGORITMI PER IL TRACCIAMENTO DELLE CURVE

Sono previsti due algoritmi: Esaustivo ed Incrementale

Algoritmo esaustivo

Viene calcolato il valore della funzione in tutti i punti dello schermo, procedendo sequenzialmente da sinistra a destra una riga dopo l'altra: ogni volta che il valore della funzione cambia di segno, viene disegnato un punto.
Si tratta dell'algoritmo più semplice da programmare, però è lento, perché richiede la valutazione della funzione in tutti i punti dello schermo. È facile da realizzare anche in classe da studenti con minime capacità di programmazione.
Può andare incontro ad errori se la funzione è rapidamente variabile rispetto alla granularità dello schermo.

Algoritmo incrementale

Una volta trovato un punto sulla curva, ci si muove attraverso i punti adiacenti cercando di restare sempre il più possibile vicini alla curva: la vicinanza è desunta dal valore assoluto della funzione. In pratica si calcola il valore della funzione nei punti adiacenti e si sceglie quello in cui il valore assoluto risulta minimo.
Il numero dei punti di test risulta molto ridotto rispetto all'altro algoritmo, soprattutto se si adottano accorgimenti che evitano il calcolo in tutti i punti adiacenti (che al massimo sono 8), e quindi la velocità del disegno è notevole. Se si usa un processore molto veloce la differenza di velocità non è molto apprezzabile, essendo il disegno questione di secondi nel peggiore dei casi.
L'algoritmo base non è difficile da implementare ed è interessante anche come proposta didattica per il laboratorio di informatica. Ci sono tuttavia delle situazioni che richiedono dei raffinamenti, come il trattamento dei punti doppi o delle cuspidi: IMPLICIT si comporta abbastanza bene, eccetto situazioni particolarmente aggrovigliate [d'altra parte altri programmi commerciali si comportano anche peggio nelle stesse situazioni].
Il problema forse più complicato da risolvere in questo algoritmo è la ricerca del primo punto. IMPLICIT adotta un compromesso: partendo da un punto fissato dall'utente, si muove seguendo grosso modo il gradiente della funzione, finchè trova un punto in cui il valore della funzione cambia segno.
Nelle figure seguenti è mostrata in modo pittorico la sequenza delle operazioni descritte. L'equazione è x²+y²-81=0 e il punto di partenza è (5 , 4). I rettangoli gialli rappresentano i pixel che formano il disegno.

Atri algoritmi possibili (non usati in IMPLICIT)

Ci sono altri algoritmi che rappresentano variazioni o miglioramenti di quelli qui presentati o si fondano su principi diversi. Tra questi ultimi segnalo a chi fosse interessato un bel programma (commerciale) chiamato GrafEq (di cui si può avere un demo all'indirizzo www.peda.com/grafeq ), che implementa un algoritmo sottrattivo basato sulla esclusione delle regioni di piano che non contengono di sicuro soluzioni: in certi casi è assai lento, però risulta molto più accurato degli altri.

ALGORITMI PER LA RAPPRESENTAZIONE DELLE SUPERFICI

Le superfici danno origine nel piano a zone corrispondenti a intervalli discreti della variabile z : il disegno delle zone si avvale di due algoritmi diversi a seconda che le equazioni siano del tipo z=f(x,y) o f(x,y,z)=0. Nel primo caso si usa l'algoritmo esaustivo già descritto, mentre nel secondo si usa una combinazione dei due; questo secondo è molto più lento, però il problema da risolvere è anche più difficile, in quanto si pone  il problema della rimozione delle parti nascoste da quelle in primo piano [IMPLICIT immagina sempre che la superficie sia opaca e di guardarla dall'alto].

La resa tridimensionale delle superfici avviene mediante l'uso di autostereogrammi (da guardare a occhio nudo) o anaglifi (da guardare con occhiali bicolori). La scelta di questa modalità non convenzionale deriva dal fatto che è l'unica a non richiedere altre elaborazioni oltre quelle previste per il piano: infatti si passa in modo naturale dal disegno a zone colorate alla vista stereoscopica, mediante semplici algoritmi che si trovano nella letteratura.
Ciò che può stupire è che comunque questa rappresentazione risulta accattivante per chi riesce a vederla, in quanto lascia un'impressione realistica che altre trasmettono con più difficoltà.
L'argomento della rappresentazione stereoscopica potrebbe entrare utilmente anche nella didattica, sia per l'aspetto neurobiologico sia per quello geometrico. Gli algoritmi usati si basano su considerazioni geometriche abbastanza elementari da essere alla portata di studenti appena un pò svezzati nella geometria analitica, ma non sono comunque banali.

ALGORITMI PER IL CALCOLO DELLE FUNZIONI

Come si è visto, tutti gli algoritmi si basano sul calcolo del valore della funzione in molti punti diversi: è chiaro che la velocità del tutto dipende criticamente da questa operazione. Quindi si capisce che una grossa fetta del lavoro è stata dedicata a velocizzare al massimo il calcolo. I passi fondamentali sono stati due: