Come funziona Google Earth: bilinear e trilinear filtering e texture mapping

Come funziona Google Earth

Google Earth è il più noto programma di mapping dell’intero globo terrestre, il risultato di un processo di 3D rendering, texture mapping e texture filtering. Ma come funziona tecnicamente Google Earth? Cosa significa texture mapping, bilinear filtering e trilinear filtering? La domanda mi è sorta spontanea (e ho quindi deciso di approfondire l’argomento) quando è stato scoperto che un’isola nel mezzo dell’Oceano Indiano, al largo delle coste dell’Australia Occidentale, tale Sandy Island e ben visibile sullo schermo del computer, in realtà non esiste! Nel vedere come funziona Googel Earth procederemo al contrario, partendo dall’istante in cui la terra, in 3D, appare sullo schermo, per poi tornare al momento in cui vengono forniti i dati. Questo approccio è utile per capire meglio l’intero processo.

Il risultato: creare un globo virtuale in 3D

La circonferenza della Terra, a livello dell’Equatore, è di circa 40.000 Km. Per memorizzare i dati di un solo pixel a colori per ogni chilometro quadrato di superficie, una intera immagine (appiattita) del pianeta sarebbe composta da circa 40.000 pixel in larghezza e circa la metà in altezza. Questi numeri sono di gran lunga superiori alle potenzialità degli hardware grafici 3D disponibili al momento. Parliamo di un’immagine di almeno 800 megapixel e 2.4 gigabyte di memoria. Con queste caratteristiche, inoltre, si può elaborare una porzione di territorio di circa 2 Km di larghezza, senza vedere edifici, fiumi, strade o persone; per le maggiori città degli Stati Uniti, invece, Google Earth lavora con risoluzioni che permettono di visualizzare oggetti di dimensioni più piccole di mezzo metro, quindi almeno quattromila volte più dense (oppure sedici milioni di volte più ingombranti a livello di memoria) rispetto all’esempio precedente.

Parliamo di immagini di dimensioni enormi, che occupano diversi terabyte di memoria; insomma, qualcosa che non potrebbe essere mai eseguita sui normali computer ad ora in commercio, specialmente in tempo reale. Eppure ciò accade lo stesso, ogni volta che si consulta Google Earth. E qui entriamo nel vivo della questione.

Cosa ha di innovativo Google Earth

In un globo virtuale 3D, è possibile ruotare ed inclinare la visuale per vedere ogni diversa angolazione di un’immagine; ma la difficoltà consiste nel trasferire i dati dell’immagine della Terra ad altissima risoluzione, dalle memorie dei globi virtuali ai computer. I dati sorgente, infatti, devono essere inviati e mappati su una sfera virtuale, oppure su piccoli superfici 3D (tipo i triangoli) che simulino il terreno reale, le montagne, i fiumi, ecc. Ora, esistono diversi schemi per permettere di vagare lungo questa immensa texture. Alcuni tagliano l’immagine della terra in piccoli tasselli regolari, e riproducono un certo numero di tali tasselli sullo schermo del PC, sia in 2D (Google Maps) o in 3D, come fa Virtual Earth di Microsoft. Il modo in cui Google Earth ha risolto il problema ha rappresentato una novità, che necessita di un paio di concetti introduttivi per essere spiegata. Concentriamo quindi l’attenzione sul texture mapping e sul texture filtering, perché i dettagli sono fondamentali.

 

Le basi del texture filtering

Il problema relativo alla riduzione, alla rotazione e alla curvatura di immagini in 2D è stato risolto tempo fa; la soluzione più comune è chiamata bilinear filtering (filtraggio bilineare). Per ogni nuovo pixel (scalato, ruotato, ecc.) che si vuole calcolare, si prendono i quattro migliori pixel dall’immagine sorgente e si uniscono insieme. Questo metodo è detto bilineare perché combina linearmente due pixel alla volta, lungo un asse, e poi combina linearmente quei due risultati, lungo un altro asse, per ottenere l’esito finale. Questa funzionalità è integrata negli hardware grafici 3D di un computer.

Tornando al nostro problema, esso viene fuori ogni qualvolta i pixel sorgente vengono mappati in differenti (cioè scalati, ruotati, inclinati, curvati) pixel di output, perché l’informazione visuale va persa. Questo fenomeno è chiamato ‘aliasing’ e si verifica quando l’immagine originale viene campionata digitalmente in un determinato modo, ad una data frequenza (leggi risoluzione) e poi viene ricampionata secondo diversi parametri. In pratica, quando i pixel di output non si allineano con gli intervalli di campionamento (frequenza, risoluzione) dell’immagine sorgente. Il risultato è una bassa resa grafica.

L’obiettivo è quello di minimizzare l’aliasing con ingegnosità ed un buon modello: il miglior modo è quello di avvicinarsi il più possibile ad un corrispondenza di 1:1 tra i pixel di input e quelli di output, o almeno generare una tale quantità di pixel extra, da poter tranquillamente ricampionare l’output per minimizzare l’aliasing. Questa tecnica è detta anti-aliasing.

Per le immagini ridimensionate la situazione peggiora, perché ogni pixel nell’immagine di destinazione potrebbe corrispondere a centinaia di pixel della sorgente, o viceversa. L’interpolazione bilineare prenderà solo i quattro migliori pixel dell’immagine sorgente ed ignorerà il resto; quindi potrebbe escludere dei pixel importanti, come i bordi, le ombre, ecc. Quello che accade si può descrivere come un effetto di sgranatura dell’immagine (detto pixel popping), come avveniva in alcuni videogiochi. Inclinare le immagini (o applicare qualsiasi trasformazione 3D) è ancora più complicato, perché sono presenti anche altri elementi (ridimensionamento e rotazione) ed una grande variazione nella densità dei pixel lungo le superfici renderizzate.

Ecco la soluzione: il trilinear filtering

Cos’è il trilinear filtering? Per capirlo meglio, dobbiamo pensarlo associato alla tecnica del mip-mapping, dove per mip-map si intende la raccolta di immagini ottimizzate, abbinate ad una texture principale.

L’utilizzo di ambedue le tecniche permette all’hardware di calcolare e memorizzare una serie di versioni di un’immagine sorgente, a risoluzione più bassa. Ogni mipmap viene automaticamente ricampionato per un fattore di 2, ripetitivamente, fino a quando non raggiunge un’immagine di 1×1 pixel, il cui colore è la combinazione di tutti i pixel dell’immagine sorgente.

Quindi, ad esempio, se all’hardware viene inviata un’immagine sorgente di 512×512 pixel, esso calcolerà e memorizzerà 8 livelli extra di mip-mapping (256, 128, 64, 32, 16, 8, 2, e 1 pixel quadrato). Se questi valori vengono disposti verticalmente, si visualizza una piramide rovesciata, dove ogni linea orizzontale (i livelli di mipmap) è larga la metà di quella superiore. Durante il rendering 3D, il mipmapping e il trilinear filtering prendono ciascun pixel di destinazione, i due livelli di mipmapping più appropriati, eseguono una combinazione bilineare su entrambi, e quindi combinano i due risultati di nuovo (linearmente) per ottenere la risposta finale trilineare. Il trilinear filtering, quindi, è un’estensione del bilinear filtering.

Riflessione

Finora tutto bene, ma abbiamo preso in considerazione piccole immagini di 512×512, quando la terra presenta una superficie composta da milioni di pixel. Le immagini ad altissima risoluzione implicherebbero la visualizzazione di una piramide mipmap a decine di livelli, con milioni di pixel; questo non è possibile su nessuna scheda video 3D presente al momento sul mercato.

Ecco come Google Earth ha risolto il problema

Universal Texture è un brevetto di Google per il texture mapping su un modello 3D dell’intero globo. Nel caso di Google Earth, esso crea una gigantesca texture virtuale dell’intera terra, di diversi terabyte, in un modo molto intelligente.

Invece di caricare e riprodurre l’immensa texture tutta in una volta, cosa impossibile sugli attuali hardware, e invece di spezzettarla in milioni di tessere (perdendo quindi il miglior filtering e l’efficienza necessaria), utilizza un algoritmo che riesce a capire quali sezioni della texture virtuale (quella dell’intero globo) necessità in ogni dato momento, e alloggia solo quelle dalla memoria di sistema alla memoria texture della scheda grafica del computer.

In questo modo, ogni immagine può essere riprodotta in maniera molto efficiente, anche in tempo reale. Da un punto di vista concettuale, c’è una modifica rispetto al mipmapping di base: la piramide capovolta di cui abbiamo parlato prima, è molto più grande (milioni o miliardi di pixel), ma al suo interno si applica ogni volta una sorta di taglio (chiamato clip stack), che include solo i pixel utili ed esclude quelli che non si necessitano al momento.

Google Earth carica progressivamente informazioni ad alta risoluzione, per ciò che si trova nel centro focale dall’utente mentre naviga sul globo. Quindi, mentre si inclina l’immagine, si vola e si vede scorrere la terra verso l’orizzonte, Universal Texture invia solo i migliori, e più utili, livelli di dettaglio all’hardware, in ogni momento. Ciò che non serve non viene neanche considerato, ed è questo che rende Universal Texture estremamente efficiente. Se, ad esempio, partendo da una visuale totale del globo, l’utente iniziasse a scendere verso il Colosseo, il programma calcolerebbe e invierebbe solo i dati compresi nel centro focale, fino a raggiungere il punto di arrivo.

Affinché ciò funzioni, è necessario che i livelli massimi di risoluzione siano presenti ovunque; dove la risoluzione è limitata, dove ci sono dei dati mancanti, il sistema utilizza il livello di risoluzione successivo (più basso), invece di lasciare degli spazi vuoti. Per questo, a volte, quando si zooma in una determinata area, l’immagine si sfoca, mentre in altre zone è precisa e dettagliata.

Tutto dipende dalla disponibilità di dati, non da limiti attribuibili al rendering 3D. Mentre si viaggia su Google Earth, il sistema può efficientemente portare i dati di una nuova texture, dalla cache del disco locale e dalla memoria di sistema alla memoria texture della scheda grafica. E terminiamo con un ultimo argomento, cioè il motivo per cui Universal Texture enfatizza il comportamento asincrono. È presto detto: i dati delle texture impiegano un certo tempo per essere caricati continuamente su un hardware 3D, tempo che viene tolto alla realizzazione di immagini 3D in modo fluido. Per ottenere 60 frame al secondo stabili, sulla maggior parte degli hardware, il caricamento delle texture viene diviso in piccole porzioni, che aggiornano molto rapidamente la memoria video delle schede grafiche con i dati dell’immagine sorgente, per qualsiasi area si stia guardando. Grazie a questo asincronismo, il rendering può andar liscio e l’interfaccia utente essere la più fluida possibile. È proprio Universal Texture a rendere Google Earth il globo virtuale più efficiente.

 

Dopo aver spiegato come funziona tecnicamente Google Earth, rimane sempre l’interrogativo posto all’inizio dell’articolo: come ci è finita Sandy Island sulle sue mappe? Se Google Earth utilizza immagini satellitari, come può ancora visualizzare un’isola che non c’è?

L’innalzamento dell’acqua può aver portato un atollo a scomparire, ok, ma visto che i rilevamenti effettuati alle coordinate in cui si dovrebbe trovare l’isola, hanno trovato fondali profondi 1.400 metri, come è possibile che sia avvenuto un tale sprofondamento dall’ultimo aggiornamento delle mappe? Penso a molti venga in mente l’isola della serie TV Lost..

 

Bibliografia:

- Introduction to 3D Data di Heather Kennedy

- Google Earth For Dummies di David A. Crowder

- http://www.realityprime.com/blog/2007/07/how-google-earth-really-works/

- http://computer.howstuffworks.com/internet/basics/google-earth.htm

 

Quello che hai appena letto è un Articolo Premium reso disponibile affinché potessi valutare la qualità dei nostri contenuti!

Gli Articoli Tecnici Premium sono infatti riservati agli abbonati e vengono raccolti mensilmente nella nostra rivista digitale EOS-Book in PDF, ePub e mobi.

volantino eos-book1

Vorresti accedere a tutti gli altri Articoli Premium e fare il download degli EOS-Book?
Allora valuta la possibilità di sottoscrivere un abbonamento a partire da € 2,95!

Scopri di più

One Response

  1. Piero Boccadoro Piero Boccadoro 29 gennaio 2013

Leave a Reply