L'angolo di 6502Free Span Buffer [2]
2002-12-28
Indice

Benvenuti!
Chi sono
Demo
Documenti
Quelli piccoli
Problemi
Scacchi
Immagini
Musica
Il mio blog
Scrivimi

English version 


Descrizione algoritmo

L'algoritmo che ora descrivero', diversamente dallo z-buffer, richiede che l'ordinamento dei poligoni in ingresso sia perfetto (come l'algoritmo del pittore) ma permette di elaborare l'immagine finale molto piu' rapidamente evitando calcoli relativi a parti nascoste (anche i calcoli di profondita' che lo z-buffer richiede sempre e comunque).

Note:Esiste un altro algoritmo di cui l'inventore afferma di essere il mio amico Paul Nette (Midnight) che viene chiamato "s-buffer". Quell'algoritmo offre il vantaggio di non richiedere un ordinamento perfetto e permette comunque di risparmiare molti calcoli rispetto a uno z-buffer se la scena e' relativamente semplice. D'altra parte la complessita' dell'elaborazione cresce al complicarsi della scena e ritengo che, a parte qualche caso molto particolare, non si tratti di un buon algoritmo. Quello descritto in queste note NON e' l'algoritmo s-buffer descritto da Paul Nette.

L'idea principale e' quella di disegnare i poligoni sullo schermo partendo dal piu' vicino per arrivare al piu' lontano mantenendo una traccia di quali zone dello schermo risultino gia' coperte e quali invece risultino ancora da coprire. Questa traccia viene conservata in una lista di "span" (intervalli) per ogni scanline:

/*
** Ogni span e' caratterizzata dall'ascissa iniziale
** e finale e da un puntatore alla prossima span
** libera della stessa scanline.
**
**   x0   = ascissa iniziale della span
**   x1   = ascissa finale della span
**   next = prossima span sulla stessa scanline
*/
typedef struct SPAN
{
  int x0;
  int x1;
  struct SPAN *next;
} Span;

/*
** Per ogni scanline viene mantenuto il puntatore
** alla prima span disponibile sulla scanline.
** MAXYRES e la massima risoluzione verticale
** ammessa per lo schermo.
*/
Span *FirstSpan[MAXYRES];

Inizialmente verra' creata una sola span per ogni scanline, larga quanto lo schermo in modo da definire l'intera area come "disponibile". Durante il disegno dei poligoni bisognera' mantenere aggiornate le liste modificando, eliminando o aggiungendo nuove span. Poiche' durante il disegno ci saranno numerose creazioni/distruzioni di span e' preferibile gestire internamente l'allocazione/deallocazione in modo da evitare rallentamenti che il memory manager protrebbe introdurre.

/*
** Lista delle span riutilizzabili
*/
static Span *FirstUnusedSpan;

/*
** Allocazione di una nuova span: prima di chiamare
** il gestore memoria per una allocazione vera e
** propria viene controllata la presenza di
** eventuali span riutilizzabili.
*/
static Span *NewSpan(void)
{
  Span *s;
  if ((s=FirstUnusedSpan)==NULL)
    s=(Span *)Malloc(sizeof(Span));
  else
    FirstUnusedSpan=s->next;
  return s;
}

/*
** Deallocazione di una span: non si tratta di una
** vera e propria deallocazione ma piuttosto di un
** inserimento nella lista delle span riutilizzabili
*/
static void FreeSpan(Span *s)
{
  s->next=FirstUnusedSpan;
  FirstUnusedSpan=s;
}