Post on 02-May-2015
1
Modellazione di terreni Modellazione di terreni a risoluzione adattiva a risoluzione adattiva
Leila De Floriani, Paola Magillo,Leila De Floriani, Paola Magillo,
Alessandro Peirano, Enrico PuppoAlessandro Peirano, Enrico Puppo
Dipartimento di Informatica e Scienze dell’InformazioneDipartimento di Informatica e Scienze dell’Informazione
Universita` di GenovaUniversita` di Genova
Con il contributo del Progetto MIUR Con il contributo del Progetto MIUR
““Rappresentazione e gestione di dati spaziali e geografici in Web”Rappresentazione e gestione di dati spaziali e geografici in Web”
2
Che cosa e` un terreno? Che cosa e` un terreno?
Legge / funzione:Legge / funzione:
(x,y) z = f(x,y)(x,y) z = f(x,y)
quota in un terrenoquota in un terreno livello di grigio in livello di grigio in
un’immagineun’immagine …… (x,y)
z=f(x,y)
3
Che cosa e` un terreno? Che cosa e` un terreno?
Non ha una formula matematica!Non ha una formula matematica!
...un insieme finito di punti ...un insieme finito di punti campionaticampionati
4
Campionamento di un terrenoCampionamento di un terreno
Immagini satellitariImmagini satellitari punti disposti a grigliapunti disposti a griglia alta risoluzionealta risoluzione non distingue punti piu` o meno importantinon distingue punti piu` o meno importanti
Misurazioni in locoMisurazioni in loco punti disposti arbitrariamentepunti disposti arbitrariamente acquisizione mirata di punti importanti acquisizione mirata di punti importanti
(vette, crinali, passi, installazioni…)(vette, crinali, passi, installazioni…)
Digitazione di mappeDigitazione di mappe recupero di archivi (curve di livello, recupero di archivi (curve di livello,
fiumi…)fiumi…)
5
Modelli di terreno Modelli di terreno
Un insieme finito di puntiUn insieme finito di punti
campionati...campionati...
E tutti gli altri punti?E tutti gli altri punti?
Necessario un modelloNecessario un modello
per il terreno!per il terreno!
(x,y)
z=??
6
Modelli di terreno basati su triangoli Modelli di terreno basati su triangoli
Triangolazione:Triangolazione: insieme di triangoli nel piano con vertici i punti insieme di triangoli nel piano con vertici i punti campionati e tali che:campionati e tali che:
coprono il dominio x-y NO:coprono il dominio x-y NO:
senza sovrapporsi NO: SI:senza sovrapporsi NO: SI:
combaciando ai lati NO:combaciando ai lati NO:
7
Modelli di terreno basati su triangoliModelli di terreno basati su triangoli
Triangolazione trasportata in 3DTriangolazione trasportata in 3D
usando le quote dei verticiusando le quote dei vertici
(interpolazione)(interpolazione)
Ora ogni punto ha una quota!Ora ogni punto ha una quota!
(x,y)
z
8
Risoluzione di un modello di terrenoRisoluzione di un modello di terreno
Risoluzione = densita` di triangoliRisoluzione = densita` di triangoli
9
Problemi con la risoluzioneProblemi con la risoluzione
Tecniche di acquisizioneTecniche di acquisizione
altissime risoluzionialtissime risoluzioni
maggiore aderenza a morfologiamaggiore aderenza a morfologia maggiore memoria e risorse computazionalimaggiore memoria e risorse computazionali
...fino ad essere ingestibile...fino ad essere ingestibile
(es. visualizzazione interattiva in tempo reale)(es. visualizzazione interattiva in tempo reale)
19...
585...
...16208 triangoli
10
Risoluzione adattivaRisoluzione adattiva
CompromessoCompromesso
Modulare la risoluzione di ciascuna zona adattandola in baseModulare la risoluzione di ciascuna zona adattandola in base
alla sua importanzaalla sua importanza
risoluzione variabilerisoluzione variabile
zone diversezone diverse tempi diversitempi diversi
11
Esempio: visualizzazione interattivaEsempio: visualizzazione interattiva
Qualita’ dell’immagine + Interazione in tempo realeQualita’ dell’immagine + Interazione in tempo reale importanti solo triangoli dentro volume di vistaimportanti solo triangoli dentro volume di vista triangoli vicini piu` importanti dei lontani triangoli vicini piu` importanti dei lontani
12701triangoli
3065triangoli
12
Modelli multi-risoluzioneModelli multi-risoluzione
Non possiamo avere tanti modelli quante situazioniNon possiamo avere tanti modelli quante situazioni Un solo modello che si adatta dinamicamenteUn solo modello che si adatta dinamicamente
Modello multi-risoluzione:Modello multi-risoluzione:
frammenti di triangolazioni frammenti di triangolazioni a risoluzioni diverse a risoluzioni diverse (minima…massima)(minima…massima)
combinati su richiesta in combinati su richiesta in triangolazioni complete a triangolazioni complete a risoluzione variabile risoluzione variabile
13
Modello multi-risoluzioneModello multi-risoluzione
ModificaModifica = raffinamento locale per sostituzione = raffinamento locale per sostituzione
…modifiche...
14
(2) Alcune possono essere omesse (se non impediscono altre)(2) Alcune possono essere omesse (se non impediscono altre) Modifiche in stessa zona - legate da dipendenzaModifiche in stessa zona - legate da dipendenza Modifiche in zone diverse - indipendentiModifiche in zone diverse - indipendenti
Dipendenza tra modificheDipendenza tra modifiche
Sequenza pre-computata di modificheSequenza pre-computata di modifiche
(1) Non necessario eseguirle tutte!(1) Non necessario eseguirle tutte!
15
Dipendenza tra modificheDipendenza tra modifiche
Da ordinamento totale (sequenza)Da ordinamento totale (sequenza)
A ordinamento parziale (grafo diretto aciclico)A ordinamento parziale (grafo diretto aciclico)
16
Ordinamento parzialeOrdinamento parziale
ModificaModifica due triangolazioni locali a due triangolazioni locali a
risoluzioni diverserisoluzioni diverse sostituisce risoluzione sostituisce risoluzione
minore con risoluzione minore con risoluzione maggioremaggiore
OrdinamentoOrdinamento M1 < M2 se M2 sostituisce M1 < M2 se M2 sostituisce
qualche triangolo introdotto qualche triangolo introdotto da M1da M1
M2 non puo’ essere eseguita M2 non puo’ essere eseguita senza M1senza M1
17
Estrazione di triangolazioniEstrazione di triangolazioni
Ogni sotto-insieme di modifiche che rispetti l’ordine parzialeOgni sotto-insieme di modifiche che rispetti l’ordine parziale
produce una triangolazioneproduce una triangolazione
Concentrare modifiche in zone di interesseConcentrare modifiche in zone di interesse Triangolazioni a risoluzione variabile secondo esigenzeTriangolazioni a risoluzione variabile secondo esigenze
18
Come funziona un modello multi-Come funziona un modello multi-risoluzione risoluzione
Memorizza modifiche e relazione d’ordine parzialeMemorizza modifiche e relazione d’ordine parziale Strutture dati compatte (meno memoria che il modello a risoluzione massima)Strutture dati compatte (meno memoria che il modello a risoluzione massima)
Interrogazione:Interrogazione:
Parametri che esprimono la
risoluzione richiesta
triangolazione a risoluzione minima sufficiente a soddisfare i parametri
Modellomulti-risoluzione
19
Parametri di interrogazione Parametri di interrogazione
Funzione di localizzazione dell’interesse:Funzione di localizzazione dell’interesse:
quali zone (triangoli) sono di interessequali zone (triangoli) sono di interesse
Funzione di soglia:Funzione di soglia:
la risoluzione minima richiesta per i triangoli di interessela risoluzione minima richiesta per i triangoli di interesse
Dove raffino?
Quanto raffino?
20
Range queryRange query
Curve di livelloCurve di livello
Funzioni di localizzazione dell’interesseFunzioni di localizzazione dell’interesse
Determinano i tipi di interrogazioneDeterminano i tipi di interrogazione
Point locationPoint location
Window queryWindow query
21
Point locationPoint location
Window queryWindow query
Range queryRange query
Curve di livelloCurve di livello
Funzioni sogliaFunzioni soglia
I triangoli interessanti devono rispettare la sogliaI triangoli interessanti devono rispettare la soglia
Gli altri possono essere grezzi a piacereGli altri possono essere grezzi a piacere
22
Funzioni sogliaFunzioni soglia
A che cosa si applica la soglia?A che cosa si applica la soglia? geometria del triangolo (area, lunghezza dei lati…)geometria del triangolo (area, lunghezza dei lati…) errore di approssimazioneerrore di approssimazione
Che cosa e` la soglia?Che cosa e` la soglia? un valore costanteun valore costante un valore che dipende dalla posizione del triangoloun valore che dipende dalla posizione del triangolo
soglia??
23
EsempioEsempio
Visualizzazione interattiva in un simulatore di voloVisualizzazione interattiva in un simulatore di volo
Funzione di localizzazione dell’interesse:Funzione di localizzazione dell’interesse:
-- il volume di vista 3D-- il volume di vista 3D
Funzione di soglia:Funzione di soglia:
-- si applica all’errore di approssimazione-- si applica all’errore di approssimazione
-- dipende dalla distanza dal punto di vista-- dipende dalla distanza dal punto di vista
24
EsempioEsempio
Dimostrazione pratica…Dimostrazione pratica…
buon divertimento!buon divertimento!