Il miglior punto di vista per grafi tridimensionali



Scaricare 39.36 Kb.
22.12.2017
Dimensione del file39.36 Kb.

Ricerca del miglior punto di vista per disegni di grafi tridimensionali


(Tratto da un articolo di Peter Heades, Michael E. Houle,Richard Webber [EHW])
Docente Tiziana Calamoneri

Curato da Marco Fanelli


Ci sono molti lavori sulla creazione di disegni di grafi che sono sia facili da apprendere che facili da capire [BETT94]. Molti di questi generano disegni bidimensionali ma ultimamente si considera sempre più il disegno 3D per i grafi [CELR96]. Molto del lavoro fatto si concentra sul trovare un buon disegno tridimensionale che ottimizzi vari criteri estetici come Area, lunghezza degli archi, numero di svolte, ecc; consideriamo, invece, il problema di rappresentare un disegno tridimensionale di un grafo tramite un supporto bidimensionale come lo schermo. Dato un disegno tridimensionale di un grafo cerchiamo di ottenere il miglior risultato possibile scegliendo in modo accurato il punto di vista, quindi non andando a modificare il disegno tridimensionale del grafo

Ci sono alcuni esperimenti che evidenziano i vantaggi del disegno tridimensionale sul disegno bidimensionale. Uno di questi (riportato da Ware e Franck [WF96]) mette in mostra che la terza dimensione permette agli utenti di lavorare con grafi di maggiore estensione in cui le naturali azioni di rotazione e traslazione permettono agli utenti di risolvere le ambiguità di un grafo esteso mentre mantengono la loro mappa mentale.

In [WF96] Ware e Franck hanno affrontato il problema di misurare la leggibilità di un disegno tridimensionale di un grafo confrontando molte combinazioni tra varie tipologie di disegno di sistemi di navigazione, una misura di leggibilità consiste nell’interpretare correttamente l’esistenza di un arco tra due nodi del grafo; usando una serie di esperimenti sugli utenti Ware e Franck mostrano che l’utente commette meno errori se ha la possibilità di ruotare e traslare nello spazio il disegno tridimensionale del grafo, purtroppo ciò richiede, all’utente, un tempo maggiore per decidere se un arco è incidente a due nodi.

Si congettura che l’aumento de tempo di decisione sia parzialmente dovuto al tempo speso per trovare manualmente un buon punto di vista.

Sarebbe auspicabile invece l’uso di una selezione automatica del punto di vista in cui l’utente specifica una regione del grafo da mostrare e il sistema sceglie automaticamente il miglior punto di vista locale. In più l’uso del miglior punto di vista è necessario quando si deve rappresentare un disegno 3D in una immagine bidimensionale statica.

Di seguito per, semplicità di trattazione, assumeremo di operare su di un disegno tridimensionale rettilineo; per molte tipologie di disegno dove gli archi sono composti da segmenti di retta consecutivi è sempre possibile trasformare il disegno in uno rettilineo sostituendo, in tempo lineare, le svolte di ogni arco con dei nodi fittizi, d’altra parte questa approssimazione comporta una modifica alla stima del tempo di esecuzione e di spazio d’occupazione, infatti sia s il numero di svolte totali andremo ad operare su un insieme di vertici V`=V+s e di archi E`=E+s questo non si traduce in un aumento quando il numero di svolte per arco è limitato da una costante (s = O(kE) dove k è il numero massimo di svolte per arco)


Definizioni


Un disegno tridimensionale rettilineo D:VR3 di un grafo astratto G=(V,E) associa ad ogni vertice viV una posizione nello spazio vi =<xi, yi, zi> e ogni arco eij=(vi,vj ) viene disegnato come un segmento vivj tra i suoi vertici.

Un vertice senza archi incidenti è chiamato vertice isolato, chiamiamo V0 l’insieme dei vertici isolati.


Per visualizzare un disegno tridimensionale su di un supporto bidimensionale, come lo schermo o la stampa, si deve utilizzare una proiezione dei punti, i tipi di proiezioni più comuni sono la parallela, la prospettiva.

Un parametro molto importante di una proiezione è il punto di vista; il quale è definito dalla posizione, dell’osservatore nello spazio tridimensionale e dalla direzione in cui questo sta guardando.


Nella proiezione parallela i punti sono traslati, parallelamente alla direzione del punto di vista, su di un piano chiamato piano di proiezione (fig. 1) il quale generalmente è perpendicolare alla direzione del punto di vista (proiezione parallela ortogonale).
S
e una proiezione mappa due punti tridimensionali in un solo punto bidimensionale allora c’è una occlusione, si dice che il punto frontale (il più vicino alla superficie di proiezione) occlude quello dietro

Un buon Punto di vista


Il disegno tridimensionale di un grafo è principalmente utilizzato per comunicare vari tipi di informazione:

  • Informazioni Relazionali: date dai vertici, dagli archi e dalle incidenze tra loro.

  • Informazioni di Attributi: come la forma e il colore dei vari elementi.

  • Informazioni Geometriche: come la posizione di ogni elemento relativamente a dei punti prestabiliti (come l’origine) o più semplicemente le distanze tra varie coppie di elementi.

Quando proiettiamo il disegno sulle due dimensioni vogliamo preservare queste informazioni; le informazioni Geometriche e degli attributi dipendono dal tipo di disegno utilizzato.Sebbene le principali proiezioni mantengano le informazioni degli Attributi, le informazioni Geometriche sono fortemente condizionate dalla proiezione e dal punto di vista utilizzati.

Le informazioni Relazionali invece dipendono unicamente dal grafo astratto da visualizzare, quindi la definizione di un buon punto di vista è motivata principalmente dal preservare queste ultime informazioni:
Definizione 1: Dato un grafo astratto G e un suo disegno tridimensionale D, un buon punto di vista è quello in cui il grafo astratto G e il grafo che è possibile ricostruire dalla proiezione bidimensionale di D appaiono uguali, cioè non vengono perse o modificate le informazioni relazionali.
La bontà del punto di vista quindi dipende a sua volta da come la proiezione mappa ogni singolo elemento.

Per ora faremo queste poche assunzioni semplificative:




  1. utilizziamo una proiezione parallela ortogonale.

  2. non c’è clipping. [non vengono tolte le parti del disegno non visibili]

  3. tutti i vertici e gli archi sono matematicamente ideali, non hanno spessore per quanto riguarda il calcolo delle occlusioni.

Sotto queste assunzioni è possibile parametrizzare il punto di vista con il suo vettore direzione normalizzato d^ S2, dove S2 è la sfera unitaria centrata nell’origine di R3.


Dati due elementi a e b appartenenti al grafo, denotiamo con (a,b) il set di punti di vista che generano l’occlusione di b per via di a (a si trova di fronte a b) quindi gli elementi di (a,b) sono per definizione dei cattivi punti di vista.
Tra gli elementi di un grafo ci sono quattro tipi di accoppiamenti che generano occlusioni:
Occlusione vertice-vertice: quando due vertici vengono mappati in un unico punto il grafo astratto della proiezione perde un vertice e gli archi incidenti ai due vertici appaiono incidenti ad uno solo. Il set (vi, vj) contiene un solo elemento; il vettore normalizzato, appartenente quindi alla sfera unitaria S2 , che va da vi a vj indichiamolo con d^ij={(vj-vi)/|vj-vi|}.





Occlusione arco-vertice / vertice-arco: un vertice viene mappato all’interno di un arco, il grafo astratto della proiezione sembra così avere due archi al posto di quello iniziale, entrambi incidenti al vertice. La differenza tra le due categorie dipende da quale elemento si trova di fronte. in questo caso il set (vi, ejk) contiene un arco di circonferenza massima sulla sfera unitaria S2 che va da d^ij a d^ik .



Va notato che il set delle occlusioni arco-vertice / vertice-arco è un superset delle occlusioni vertice-vertice in quanto i punti finali di un arco coincidono con i vertici a cui incide:


(vi, vj)  (vi, vk) (vi, ejk).
Diremo che l’occlusione arco-vertice / vertice-arco copre le occlusioni vertice-vertice
Quindi se stiamo computando le occlusioni arco-vertice / vertice-arco è necessario controllare solo le occlusioni vertice-vertice tra tutte le coppie di vertici isolati denominate appunto occlusioni tra vertici-isolati.
Occlusione arco-arco: ci sono due casi di occlusione arco-arco.

  1. due archi che vengono mappati in archi differenti ma che hanno un incrocio, si incontrano solo in un punto interno ad entrambi. Idealmente, dato che il disegno è rettilineo, è possibile tracciare mentalmente il percorso dei due archi e quindi il grafo astratto deducibile dalla proiezione bidimensionale non presenta variazioni per via di un incrocio.

  2. occlusioni arco-arco significative: i due archi mappati condividono un a serie continua di punti, il che accade quando i due archi sono complanari. Il grafo astratto della proiezione sembrerà avere tre archi invece dei due per via dei nodi che si trovano all’interno di un altro arco.



Per le occlusioni arco-arco significative il set(eij, ekl) è l’unione di (e quindi è coperto da) quattro occlusioni arco-vertice / vertice-arco.


(eij, ekl) = (vi, ekl)  (vj, ekl)  (eij, vk)  (eij, vl)
Quindi se stiamo computando le occlusioni arco-vertice / vertice-arco non è necessario controllare le occlusioni arco-arco, da cui il seguente lemma:
Lemma 1: un buon punto di vista è quello che non genera occlusioni tra vertici-isolati o occlusioni vertice-arco/ arco vertice.

Punti di vista Occludenti


D
|V0|

 2 
ato un disegno tridimensionale di un grafo G=(V,E), vogliamo trovare tutti i punti di vista occludenti. Applicando il lemma 1 è possibile trovare tutti i punti di vista non buoni per il modello scelto confrontando i tutti i vertici isolati e tutti gli archi , inserendo 2 punti ( uno per ogni d^ij e per il suo opposto -d^ij ) e 2|V||E| archi di circonferenza massima sulla sfera unitaria S2, ottenendo il set , questo set non è ordinato e potrebbe contenere molte sovrapposizioni di archi e di punti isolati. Vogliamo riordinare il set  ed eliminare tutte le sovrapposizioni e le intersezioni in modo che due archi di circonferenza massima in  si intersechino solo negli estremi, definiamo il set  così modificato un “Ordinamento dei punti di vista occludenti”.

In una proiezione parallela ortogonale e senza clipping, i punti di vista con vettore normalizzato d^ e -d^ si trovano su rette parallele e quindi generano la stessa proiezione, quindi possiamo costruire un ordinamento per una sola semisfera di S2, quella con coordinata z0 chiamiamola S2+.

Possiamo trasformare i luoghi di una semisfera in punti e segmenti del piano utilizzando una proiezione centrale, trattando i punti tridimensionali come punti bidimensionali con coordinate omogenee [PS85]; cioè operando la trasformazione F(x,y,z)=(x/z,y/z,z), questo permette di esprimere i punti all’infinito lasciando che il peso sia uguale a zero (z=0).

Con questa trasformazione possiamo utilizzare un algoritmo di intersezione di segmenti nel piano per costruire il nostro ordinamento, utilizzando un semplice algoritmo sweep-line in tempo O((||+k)log) [PS85] o un algoritmo più complesso in tempo (||log||+k) descritto i[ChEd92].

Abbiamo raggiunto quindi il seguente risultato:


R
|V0|

 2 
isulato 1: (ordinamento delle Occlusioni).
Dato un disegno tridimensionale di un grafo G=(V,E), è possibile costruire un ordinamento delle occlusioni in tempo O(||log||+k) con ||=2 +2|V||E| corrispondente al numero di punti e archi di circonferenza nell’ordinamento ; k è il numero di intersezioni tra i segmenti con dimensione O(||2) nel caso peggiore. L’ordinamento occupa uno spazio O(||+k).


Punti di vista Migliori


Gli ordinamenti di punti di vista appena costruiti distinguono un generico punto di vista buono da uno cattivo. È preferibile invece disporre di una misura continua per la bontà del punto di vista, vediamo due tipi di misurazione che si basano sull’ordinamento appena definito e che ci permettono di trovare il miglior punto di vista.

Separazione rotazionale

Definiamo la funzione (p,q) come la distanza angolare tra il punto p e il punto q sulla sfera unitaria S2 , da notare che (p,q) può essere interpretata sia come lunghezza dell’arco che come angolo tra i due punti. Espandendo la notazione stabiliamo che (d^,(a, b)) è la distanza minima tra il versore d^ e il set di punti (a,b); più esplicitamente, per un’occlusione vertice-vertice (vi, vj),  è semplicemente la distanza angolare tra i punti d^ e d^ij; mentre per un occlusione vertice-arco / arco-vertice (vi,ejk),  è definita come l’arco che parte da d^ ed è perpendicolare all’arco passante per d^ij e d^ik, se la perpendicolare passa all’interno dell’arco d^ijd^ik , altrimenti  vale min[(d^,d^ik),(d^,d^ij)]





Chiamiamo (d^,(a, b)) separazione rotazionale di d^ da (a, b), e usiamo il suo minimo rispetto a tutte le occlusioni per misurare la bontà del punto di vista d^ . Va notato che (d^,(a, b))=0 implica d^(a, b), quindi trovare un buon punto di vista che preserva le informazioni relazionali di un disegno evita anche il peggior punto di vista per la misura di separazione rotazionale.

Per trovare la direzione d^ per cui una occlusione data (a, b) è la più vicina per  si può utilizzare un diagramma di separazione rotazionale (RSD: rotational separation diagram). Questo diagramma è una variante del Diagramma di Voronoi [Aur91], dove i siti S sono le occlusioni appartenenti all’Ordinamento definito prima e le risultanti bisettrici del diagramma sono archi di circonferenza e parabole sferiche. È possibile costruire il diagramma di separazione rotazionale modificando un algoritmo planare per il diagramma di Voronoi su segmenti in modo da farlo lavorare sulla sfera unitaria S2, il diagramma risultante avrà dimensione O(|S|) e tempo di esecuzione O(|S|log|S|), dove |S| è la dimensione dell’ordinamento dei punti di vista occludenti utilizzati come siti di Voronoi.
La bontà di un punto di vista aumenta all’aumentare della distanza del più vicino punto di vista occludente, questo è quindi massimizzato localmente nei vertici di Voronoi del diagramma di separazione rotazionale. È possibile, in questo modo, trovare il miglior punto di vista sotto un criterio locale arbitrario, scansionando il diagramma di separazione rotazionale in un tempo proporzionale alla sua dimensione (O(|S|) assumendo che il criterio possa essere testato in tempo costante).Se vogliamo trovare il miglior punto di vista più vicino, rispetto alla distanza angolare, per una direzione data possiamo ri-calcolare il diagramma di separazione rotazionale utilizzando i vertici di Voronoi del primo diagramma come siti, il tutto con lo stesso tempo di esecuzione e spazio, dopo di che è sufficiente applicare un algoritmo di locazione-dei-punti [PS85]. Il diagramma risultante viene utilizzato per trovare il sito più vicino (il miglior punto di vista locale) in un tempo O(log|S|).
R
|V0|

 2 
isulato 2:
il diagramma di separazione rotazionale ha dimensione O(|S|) e richiede un tempo O(|S|log|S|) per essere calcolato, dove la dimensione |S| dei punti di vista occludenti è O(||+k); ||=2 +2|V||E| e k è O(||2) nel caso peggiore ma può essere molto di meno.È possibile utilizzare il diagramma di separazione rotazionale per trovare il miglior punto di vista per la separazione rotazionale, sotto un criterio locale arbitrario, in tempo O(|S|) e il più vicino punto di vista, rispetto alla distanza angolare, in tempo O(log|S|).


Separazione osservata

Dati due punti a e b di un disegno tridimensionale di un grafo e un punto di vista con vettore normalizzato d^ , definiamo (d^,(a, b)) come la più piccola distanza Euclidea tra le proiezioni di a e b, chiamiamo questa misura Separazione osservata tra a e b per d^.

Sia (a,b) la distanza Euclidea tra gli elementi a e b in R3. per un occlusione vertice-vertice (vi, vj) è semplicemente la distanza ||vj- vi||, mentre per un’occlusione vertice-arco / arco-vertice (vi, ejk) è definita come la distanza Euclidea perpendicolare da vi alla linea vjvk, quando la perpendicolare interseca la linea all’interno di vj e vk ; altrimenti vale min(||vj-vi||,||vk-vi||).

possiamo quindi definire la separazione osservata come:

(d^,(a, b))=(a,b)sin (d^,(a, b))

e
quindi la proporzione della distanza che viene preservata tra a e b dopo la proiezione vista dal punto d^ è data dall’equazione:


questo rapporto è massimizzato quando (d^,(a, b)) è massimizzato; ne consegue che il miglior punto di vista sotto la separazione rotazionale massimizza il minimo di questi rapporti. Un’ altra interpretazione è quella che il miglior punto di vista sotto la separazione rotazionale mantiene le distanze relative tra coppie di punti nella proiezione.

È stato supposto che gli utenti siano sensibili alle condizioni limite di un criterio estetico più che all’aspetto medio e preferiscano massimizzare la separazione minima da questi limiti

Un approccio alternativo sarebbe quello di utilizzare la separazione osservata come misura di bontà del punto di vista; il miglior punto di vista sarebbe quindi quello che massimizza la minor separazione osservata tra coppie di punti nella proiezione.

Il Diagramma di separazione osservata (OSD) è una varante del diagramma di Voronoi come il diagramma di separazione rotazionale i siti sono i punti e gli archi di circonferenza dell’Ordinamento mentre le bisettrici sono molto più complesse in quanto definite dall’equazione : (d^,(a, b))= (d^,(a’, b’)). Questa forma è simile alla variante del diagramma di Voronoi con pesi moltiplicativi[Aur91], ma con un fattore supplementare del seno di .

Per immaginarne la forma consideriamo il caso ristretto del grafo senza archi E=0 dove l’Ordinamento contiene solo occlusioni vertice-vertice le quali generano i siti di Voronoi sa= d^ij con i corrispondenti pesi wa=(vi,vj). Per la simmetria dell’Ordinamento ogni sito sa genera un sito corrispondente -sa di peso uguale; per le caratteristiche della misura di separazione osservata possiamo usare entranbi i siti in modo equivalente in quanto il diagramma risultante è simmetrico rispetto all’origine.

Quando i pesi sono uguali wa=wb , la bisettrice B(a,b) dei siti sa e sb prende la forma di due cerchi di circonferenza massima sulla sfera unitaria, uno equidistante da sa e sb , l’altro da sa e -sb i quali si incontrano ai poli della circonferenza massima passante per sa e sb.

Quando i pesi non sono equivalenti come wa>wb la bisettrice B(a,b) ha la forma di un paio di ellissoidi contenenti rispettivamente sa e -sa ,calcolabili come intersezione tra il doppio cono ellissoide e la sfera unitaria, centrati entrambi nell’origine.

Bibliografia


[Aur91] F.Aurenhammer: “Voronoi diagrams – A survey of fundamental Geometric Data Structure” in ACM Comp. Surveys, Sep 1991; 23(3)

[BETT94] G. Di Battista, P. Eades, R. Tamassia, I. Tollis: “ Algorithms for Drawing Graphs: An Annoted Bibliography”, Jun 1994

[BGRT95] P.Bose, F.Gomez, P.Ramos, G.Toussaint: “Drawing Nice Projection of Objects in Space” in Graph Drawing (sep 1995; Passau, Germany); pp. 52-63

[CELR96] R. Choen, P. Eades, T. Lin, F. Ruskey: “Three dimensional Graph Drawing” in Algorithmica, 1996; 17(2)

[ChEd92] B. Chazelle, H. Edelsbrunner: “An Optimal Algorithm for intersecting Line segments in the Plane” Journal of the ACM, 39:1-54 1992

[EHW]Peter Heades, Michael E. Houle, Richard Webber: “Finding the best viewpoints for Three-Dimensional Graph Drawings”



[PS85] F.Preparata, M.Shamos: “Computational Geometry: an Introduction”, 1985 Spinger-Verlag

[WF96] C. Ware, G. Franck: “Evaluating Stereo and Motion Cues for Visualizating Information Nets in Three Dimensions” in ACM Trans. Graphic, Apr 1996, 15:121-140




©astratto.info 2017
invia messaggio

    Pagina principale