Compressione e decompressione di mesh

Le classi che effettuano la compressione e decompressione di una mesh sono rispettivamente la classe Compressor e Uncompressor (figura 4.10 nella pagina seguente). Esse hanno molte caratteristiche in comune: la pi`u eviden- te `e che entrambe derivano dalla classe Huffman, che implementa l’algoritmo per la costruzione dell’albero e dei codici di Huffman e dispone dei metodi per la loro lettura e scrittura su file.

Implementazione della codifica di Huffman

Come noto, i codici di Huffman sono rappresentati con un numero varia- bile di bits; le comuni classi di IO presenti nella Standard C++ Library non sono quindi adatte a questo scopo poich´e orientate al byte. Si `e reso perci`o necessario realizzare una classe di IO specifica, denominata BitFile, i cui metodi read() e write() operano con un numero arbitrario di bits anzich´e con multipli interi di bytes.

I codici di Huffman non possono essere emessi durante l’esecuzione del- l’algoritmo di compressione poich´e per poterli calcolare devono essere note le frequenze di apparizione di tutti i simboli. Per questa ragione il compres- sore accumula i simboli di output in una coda e ne aggiorna le frequenze

tramite la funzione count(Symbol) della classe Huffman15_{. Al termine del}

processo di compressione viene chiamato il metodo buildTrees() con cui sono costruiti due alberi di Huffman distinti: uno per i simboli relativi alla geometria ed uno per quelli concernenti la connettivit`a. I codici sono quindi

15_{per la precisione tale coda contiene soltanto i riferimenti ad i simboli, ottenuti come} valore di ritorno della funzione count()

CAPITOLO 4. INTEGRAZIONE DELLE TECNICHE PRESENTATE 95

calcolati effettuando una visita ricorsiva dell’albero a partire dalla radice con la funzione visitTrees().

Formato del file compresso

L’ultima operazione eseguita dal compressore `e la scrittura del file di uscita. Tale procedura comprende l’emissione di un header al quale seguo- no le traduzioni dei simboli presenti nella coda di output. L’header `e cos`ı composto:

• Fattore di quantizzazione16 _{→ writeQFactor()}

• Bounding Box → writeBoundingBox() • Materiale → writeMaterial()

• Numero di vertici → writeNumVertices() • Numero di triangoli → writeNumTriangles() • Tabella dei simboli → writeSymbolTable()

Alcune componenti dell’header possono apparire ridondanti, ma servono per l’inizializzazione del decompressore. La bounding box, ad esempio, pu`o essere calcolata automaticamente dopo aver letto le coordinate di tutti i ver- tici; in questo caso per`o essa deve essere nota sin dall’inizio al decompressore per poter ricostruire le coordinate quantizzate. Anche il numero di vertici e di triangoli `e ridondante ai fini della compressione, ma `e utile al decompres- sore per allocare la memoria necessaria a contenere tutti gli elementi della mesh.

La quantizzazione della coordinate

L’algoritmo di codifica implementato include una parte lossy: la com- pressione della geometria prevede infatti che i simboli relativi alle coordinate dei vertici rappresentino il valore degli indici di quantizzazione, piuttosto che

Figura 4.11: La classe Quantizer

gli effettivi numeri a virgola mobile. Il fattore di quantizzazione `e un para- metro del costruttore della classe Compressor, con il quale esso inizializza il membro q di tipo Quantizer (figura 4.11).

La classe Quantizer `e in grado di effettuare una quantizzazione uniforme delle coordinate di un qualsiasi punto interno alla bounding box. Con il metodo quantize(float *p, short *q) ciascuna coordinata del punto p `e trasformata in un punto dell’intervallo [0; 1] relativo alla bounding box; il rispettivo indice di quantizzazione viene restituito con il vettore q. Il metodo dequantize(short *q, float *p) ricava invece il valore quantizzato delle coordinate a partire dagli indici di quantizzazione.

Implementazione del valence based encoding

L’algoritmo valence based encoding possiede la particolarit`a di avere una fase di decompressione perfettamente simmetrica a quella di compressione. Per questo motivo le classi Compressor ed Uncompresor sono molto simili tra loro ed hanno metodi e dati membri analoghi, perci`o questa analisi sar`a incentrata in modo particolare soltanto sul compressore.

Durante la fase di inizializzazione ogni vertice del Subset `e marcato come

non visitato ed il suo membro degree `e impostato al valore della valenza.

Quando un vertice verr`a conquistato, il suo membro degree sar`a decrementa- to mano a mano che gli spigoli ad esso incidenti sono a sua volta conquistati, in modo tale da tenere il conto di quelli ancora liberi. Quando la variabile

CAPITOLO 4. INTEGRAZIONE DELLE TECNICHE PRESENTATE 97

degree giunger`a a zero significa che il rispettivo vertice `e divenuto pieno e potr`a essere rimosso dalle liste attive cui appartiene.

Dopo questa fase ha inizio la visita della mesh. Il punto di partenza `e un triangolo arbitrario17<sub>: una nuova lista attiva `e creata ed inizializzata con</sub> i vertici di tale triangolo. In seguito la classe Compressor itera la funzione step() fino a quando tutta la mesh non sar`a conquistata.

L’elemento centrale del processo di codifica `e lo stack delle liste attive. Esso `e stato implementato con la classe ActiveStack, che deriva il tipo stack<ActiveList*> della STL aggiungendo il metodo isIn(Vertex) atto a restituire l’indice della lista attiva alla quale appartiene un determinato vertice.

Gli elementi dell’ActiveStack sono i puntatori alle istanze della classe ActiveList (figura 4.12 nella pagina precedente), che rappresentano le liste

attive correntemente non vuote. La classe ActiveList memorizza i vertici

del bordo di taglio ad essa associato in un contenitore di tipo list<Vertex*>. Questa classe `e la responsabile dell’esecuzione delle operazioni di conquista:

• add(Vertex v): aggiunge il vertice v al bordo di taglio marcandolo

come visitato

• split(int idx): esegue lo split del bordo di taglio restituendo l’indi-

rizzo di una nuova ActiveList creata per ospitare uno dei due bordi di taglio formatisi

• merge(ActiveList l, int idx): unisce il bordo di taglio corrente

con quello della lista attiva l

• removeFullVertices(): rimuove tutti i vertici pieni dalla lista

Ciascuna di queste funzioni restituisce inoltre un vettore di tre puntatori a Vertex ed un valore del tipo enumerato TriangleMode. Tali elementi indicano quali sono i vertici a cui `e necessario modificare il degree ed in

17_{cio`e quello relativo al primo elemento del vettore dei vertici che non `e marcato come} visitato

CAPITOLO 4. INTEGRAZIONE DELLE TECNICHE PRESENTATE 99

che modo. Il metodo statico adjustDegrees(), prendendo in input queste informazioni, esegue l’aggiornamento delle variabili degree coinvolte.

La politica di selezione del focus `e stata implementata invece nel metodo selectFocus(): esso sceglie come focus il vertice del bordo di taglio con minore degree, cio`e quello a cui resta da aggiungere il minor numero di spigoli incidenti.

Un’altra tecnica implementata dalla classe ActiveList `e quella della pre-

dizione del vertice secondo la regola del parallelogrammo. Il metodo atto a

svolgere tale funzione `e predictVertex(), che restituisce il vettore delle coor- dinate del vertice predetto. Esso opera con le coordinate gi`a quantizzate, in modo da annullare l’errore di predizione in fase di ricostruzione.

Per seguire in modo interattivo la fase di compressione/decompressione di una mesh `e possibile eseguire la procedura in una modalit`a passo-passo in cui il metodo step() viene richiamato una sola volta per iterazione. Tramite il metodo draw() della classe Compressor/Uncompressor `e possibile inol- tre seguire lo stato di espansione della regione conquistata disegnando sullo schermo i bordi di taglio delle liste attive, ciascuna con un colore differente.