Strumenti grafici di supporto al progettista per la gestione e il controllo di relazioni e vincoli in modelli CAD avanzati

Articolo scritto con Davide Castellazzi e Domenica Ferretti e pubblicato il 26 giugno 1998 in occasione del II Seminario Italo-Espanol “Progettazione e fattibilità dei prodotti industriali“, Vico Equense, Napoli

Sommario

L’evoluzione dei sistemi di supporto alla progettazione affida ai sistemi software la gestione di quantità sempre maggiori di informazioni ed in particolare di relazioni tra dati, modelli e documenti. La presenza di una tale mole di informazioni non garantisce di per sé l’accessibilità e la fruibilità agli utenti che si trovano sovente a dover interagire con strumenti disomogenei e inutilmente complessi. Al fine di sperimentare nuove modalità interazione che rendano meglio e più velocemente utilizzabili tali risorse, e riconosciuta la generalità delle strutture a grafo, è stato messo a punto un algoritmo per la visualizzazione di grafi in uno spazio tridimensionale. L’algoritmo proposto, basato su un modello fisico a molle, simula l’evoluzione di un sistema fisico da una configurazione instabile iniziale verso una configurazione di equilibrio cui corrisponde una disposizione dei nodi tale da massimizzare le caratteristiche di leggibilità e fruibilità visiva.

1. INTRODUZIONE

L’evoluzione dei sistemi software di supporto alle attività di sviluppo prodotto, i sistemi CAD/CAM/CAE/ecc., è caratterizzata da un continuo arricchimento e potenziamento dei corrispondenti modelli. Allo scopo di rappresentare aspetti sempre più ampi del prodotto e del processo di progettazione, si accresce il numero e la varietà di informazioni numeriche, geometriche e testuali e, con altrettanta rapidità si accrescono le relazioni tra queste. Questa continua crescita del numero e dell’importanza delle relazioni tra dati precedentemente appartenenti a contesti applicativi precedentemente distinti, è principalmente motivata dal processo di integrazione del sistema CAD con gli altri strumenti software utilizzati nelle fasi a monte della produzione. Questo progresso offre ai progettisti strumenti caratterizzati da funzionalità sempre più ampie, ma contemporaneamente non riesce a garantire un accesso alle informazioni sufficientemente semplice e diretto, dunque ostacolandone la creazione, il controllo e la fruizione. Pertanto, nell’ambito degli utenti dei sistemi più avanzati, è maturata e si è diffusa l’esigenza di strumenti di supporto che consentano modalità alternative di accesso e controllo delle informazioni, così da affiancare le tradizionali modalità di interazione grafiche e testuali. A fronte di queste esigenze si è avviato uno studio per individuare e sperimentare nuove modalità alternative per la visualizzazione e l’interazione con strutture informative caratterizzate da ricche strutture relazionali. In particolare, si è sperimentato uno strumento per la visualizzazione di tali strutture in termini di grafi aciclici orientati, cioè grafi in cui è definita una funzione di ordinamento parziale sui nodi, opportunamente disposti in uno spazio tridimensionale. Sulla base delle tecniche descritte in letteratura per la visualizzazione di grafi, per il vero limitate alla visualizzazione in uno spazio bidimensionale, è stato messo a punto e implementato un nuovo algoritmo per il calcolo della posizione dei nodi di un grafo in uno spazio tridimensionale. L’algoritmo associa al grafo un modello fisico, e ne simula l’evoluzione da una configurazione iniziale casuale verso uno stato d’equilibrio cui corrisponde, dal punto di vista della chiarezza e della leggibilità delle informazioni in esso contenute, ad uno stato ottimale. In particolare il modello fisico utilizzato associa ad ogni nodo una massa puntiforme e ad ogni relazione tra i nodi una molla attrattiva. Inoltre, ogni coppia di nodi appartenente alla medesima classe d’uguaglianza è soggetta ad una forza elastica (repulsiva o attrattiva).

2. I DAG (DIRECTED ACYCLIC GRAPH).

I Grafi Aciclici Orientati costituiscono uno schema di riferimento cui è possibile ricondurre gran parte delle strutture relazionali impiegate dagli strumenti di supporto alla progettazione. Un Grafo Aciclico Orientato è un grafo G = (N, E), dove N = {ni} è l’insieme dei nodi e E = {ej} è l’insieme degli archi. Ciascun arco e = (ni, nj) rappresenta una relazione orientata dal nodo ni al nodo nj. Inoltre, le caratteristiche di aciclicità del grafo garantiscono che non esistono cammini chiusi orientati.

Confrontandosi con la possibilità di realizzare strumenti software più generali, risulta comunque essere conveniente realizzare strumenti software specifici per la visualizzazione e l’interazione con grafi aciclici orientati, anche in considerazione delle specifiche operazioni che sono definite su tali grafi e della loro rilevanza rispetto alle esigenze degli utenti/progettisti.

La realizzazione di uno strumento software orientato alla visualizzazione e interazione con questa classe di grafi, oltre a presentare aspetti d’interesse dal punto di vista algoritmico e delle potenzialità di impiego, consente comunque, qualora sia necessario, ricondursi facilmente alla classe più generale dei grafi, semplicemente rimuovendo una serie di vincoli e disabilitando gli algoritmi più specifici. Il principale vincolo che il software impone per operare su grafi aciclici orientati, è che gli oggetti siano disponibili in ordine gerarchico. In virtù del fatto che, in un grafo aciclico orientato è definito un ordinamento parziale sull’insieme dei nodi, è possibile assegnare o calcolare, per ciascun nodo, un livello di profondità o posizione gerarchica. La generalità degli algoritmi di posizionamento è comunque garantita anche nel caso di grafi più generali, cioè in cui non sia definito un ordinamento parziale. In bibliografia [2] sono disponibili algoritmi, per la disposizione dei nodi di un grafo su livelli “di profondità” determinati sulla base di altre caratteristiche dei grafi, invece che non sulla funzione di ordinamento parziale.

3. LA VISUALIZZAZIONE DI MODELLI TRIDIMENSIONALI.

Nel passare da una visualizzazione bidimensionale a una tridimensionale, i meccanismi d’interazione e le metafore adottate dall’interfaccia utente mutano radicalmente. Usualmente, il dispositivo di visualizzazione cui sono destinate le rappresentazioni 2D di grafi non è solamente il video, ma possono essere anche stampante o plotter. È noto che la lettura di documenti in forma cartacea è di gran lunga preferita dall’uomo rispetto alla presentazione  a video; inoltre, utilizzando il supporto cartaceo è possibile generare rappresentazioni ben maggiori delle limitate dimensioni di un video il quale, anche se supporta scorrimenti dell’immagine, non è in grado di fornire una visione globale del disegno altrettanto efficace quanto quella di un documento cartaceo.

La visualizzazione basata su tecniche tridimensionali dà luogo a rappresentazioni che male si prestano ad essere stampate, e meglio adatte ad un utilizzo interattivo. L’uso di una dimensione in più, rispetto alle rappresentazioni tradizionali, aiuta la comprensione e soprattutto rende la visione più familiare all’utente.

Le operazioni di zoom e pan, offerte da ogni software di visualizzazione 2D, hanno pertanto il fine primario di sopperire alle ridotte dimensioni del video; le stesse funzionalità, in un software di visualizzazione 3D, divengono invece elemento essenziale per consentire all’utente la fruizione di quanto visualizzato.

Gran parte degli strumenti software oggi disponibili stanno gradualmente evolvendosi verso modalità di visualizzazione di tipo tridimensionale, come testimoniato dalla crescente diffusione delle tecniche per la realtà virtuale. Pertanto, è importante lo studio di nuove tecniche per la visualizzazione di grafi basate su modelli tridimensionali.

4. LA SCELTA DEL MODELLO FISICO

In letteratura non è disponibile alcuna pubblicazione che proponga o discuta in modo specifico algoritmi per la visualizzazione di grafi in uno spazio 3D; sono disponibili solamente articoli che affrontano in modo generico il problema della rappresentazione nello spazio di strutture dati. In questo contesto, il numero degli articoli pubblicati ha recentemente subito in significativo incremento, a testimonianza del crescente interesse da parte degli utenti e di una migliore accessibilità alle tecnologie hardware e software di supporto. Nella definizione di un nuovo algoritmo, per il posizionamento degli archi e dei nodi di un grafo aciclico orientato in uno spazio 3D, ci si è pertanto potuti avvalere solamente dei risultati delle ricerche che si sono occupate dell’analogo problema in sole due dimensioni. Sebbene, come indicato, quasi nessuna delle pubblicazioni in materia e neppure la teoria dei grafi prendano in considerazione il problema della visualizzazione tridimensionale, gli algoritmi proposti in [3] hanno fornito interessanti spunti per definire e mettere a punto un nuovo algoritmo. L’algoritmo proposto associa al grafo un modello fisico e ne simula l’evoluzione da una configurazione iniziale, in cui a ciascun nodo è stata assegnata una posizione spaziale in modo casuale, verso uno stato d’equilibrio. La configurazione finale, cui converge l’algoritmo, corrisponde, dal punto di vista della chiarezza e della leggibilità della corrispondente rappresentazione tridimensionale, ad uno stato ottimale. L’algoritmo presenta pertanto caratteristiche d’intuitività e semplicità intrinseca che vanno a vantaggio sia dello sviluppatore sia dell’utente finale.

5. L’ALGORITMO PROPOSTO

Per fornire una descrizione dettagliata dell’algoritmo è necessario premettere un’illustrazione delle caratteristiche del modello fisico associato al grafo:

  • Si considerano i nodi come oggetti puntiformi aventi una massa propria;
  • Si considerano gli archi come molle esclusivamente attrattive cioè con lunghezza di riposo nulla (nel seguito chiamate molle interplanari);
  • Si vincolano i nodi a giacere sul piano associato ai corrispondenti livelli gerarchici, che caratterizzano i DAG, conservando solamente i gradi di libertà relativi alle possibili traslazioni nel piano di appartenenza.
  • Si inseriscono, tra tutte le possibili coppie di nodi giacenti sullo stesso livello, anche se non connesse da un arco, molle con lunghezza di riposo diversa da zero, chiamate molle planari.

Nel modello risultano quindi essere presenti le seguenti forze: l’attrazione tra nodi legati da una relazione, la reazione vincolare dei livelli gerarchici agente su tutti i nodi, la forza tra nodi del medesimo livello che può essere attrattiva o repulsiva. Per ciascuna molla agente su due nodi esistono nel modello due forze uguali e contrarie. Sommando tutte le forze agenti sul singolo nodo e dovute alle molle e, escludendo la componente ortogonale al piano che risulta sempre contrastata dal vincolo, si ottiene la forza risultante che ne determinerà lo spostamento. Partendo da considerazioni intuitive, e dopo aver sperimentato il comportamento di differenti tipologie di molle, si è scelto il seguente modello delle forze:

  • le molle planari esercitano su nodi appartenenti allo stesso livello una forza logaritmicamente dipendente dalla distanza d secondo la legge: 
  • le molle interplanari esercitano una forza attrattiva sui nodi legati da una relazione pari a:

La variabile d rappresenta la distanza tra i due nodi, mentre K1 e K2 e K3 sono tre costanti. La costante K2 rappresenta la lunghezza di riposo della molla planare; K1 è la corrispondente “pendenza”, mentre K3 è la “pendenza” della forza della molla interplanare. Per tutte le forze, la direzione è data dalla retta congiungente i due nodi; mentre il verso varia, a seconda che la forza sia attrattiva o repulsiva. 

L’azione di queste forze, calcolate per ogni coppia di nodi giacenti sul medesimo piano e per ogni coppia di nodi legati da almeno un arco, ha l’effetto di raggruppare le parti del grafo i cui nodi sono connessi da archi, che si dispongono a “grappoli”, mantenendo possibilmente una distanza minima tra i nodi e una conseguente maggiore leggibilità del grafo.

Una volta definito il modello, l’algoritmo ha il compito di ricercare una posizione di equilibrio statico dei nodi soggetti alle forze presenti nel modello stesso.

Nel lavoro presentato in [2] si suggerisce la seguente tecnica di discretizzazione del tempo: definita una posizione iniziale dei nodi nel piano, in modo iterativo, si calcola la forza risultante su ciascun nodo e quindi lo si riposiziona muovendolo concordemente a direzione e verso della forza calcolata. Una situazione d’equilibrio viene raggiunta quando le risultanti delle forze agenti su ciascun nodo sono tutte nulle. Sperimentalmente si è verificato che, muovendosi su un asse dei tempi discretizzato, è poco probabile raggiungere tale stato; è quindi opportuno considerare come configurazioni d’equilibrio anche quelle che si avvicinano a meno di un valore fissato a priori, alla situazione di equilibrio. 

L’algoritmo utilizzato è dunque il seguente:

  1. Assegna una posizione iniziale a ciascun nodo
  2. Calcola le forze agenti su ciascun nodo
  3. Muovi ciascun nodo in funzione della risultante delle forze
  4. Se lo stato raggiunto è accettabile termina altrimenti torna al punto (B)

La posizione iniziale dei nodi su ciascun piano è ottenuta disponendoli in un cerchio il cui raggio è funzione del loro numero. Lo spostamento di ciascun nodo, conseguente all’applicazione della forza risultante, è ottenuto moltiplicando la risultante, agente sul nodo stesso, per la costante K4. La costante K4 riassume in sé il concetto di massa e di durata dell’intervallo temporale con cui è discretizzato l’asse dei tempi. Pertanto:


dove:

Per alcuni grafi o in corrispondenza di alcuni valori di K4, può accadere che, nello spostarsi, i nodi superino la posizione di equilibrio raggiungendo una posizione ancora più lontana dalla posizione di equilibrio, causando con il progredire dell’algoritmo una vera e propria esplosione, illustrata in Figura 1. Per sopperire a quest’inconveniente, difficilmente prevedibile sulla base della semplice osservazione delle costanti, è opportuno caratterizzare l’algoritmo rendendolo autoadattativo: l’algoritmo deve avere la capacità di rilevare il verificarsi di quest’inconveniente e ridurre quindi la durata dell’intervallo temporale. La costante K4, pertanto, può essere variata dall’algoritmo: rimane invariabile solamente per la durata di un intero passo di simulazione, alla fine del quale un test decide se ridurne il valore. 

Figura 1. Un valore di K4 troppo elevato può causare l’esplosione del grafo.

Questo test si basa sul risultato di una misurazione di una caratteristica del grafo: la media della lunghezza degli archi. In particolare, qualora questo valore cresca tra un passo di simulazione e l’altro, è necessario decrementare K4.

Oltre alla media delle lunghezze degli archi, ad ogni passo l’algoritmo provvede a misurare un’altra grandezza significativa: il massimo spostamento effettuato da un nodo. Questo valore, con la costante K4, è utilizzato dal test che decide l’interruzione del processo iterativo: la simulazione termina quando risulta verificata una delle seguenti condizioni:

  1. Il massimo spostamento subito da un nodo è al di sotto di un valore di soglia predefinito.
  2. La lunghezza media degli archi, , oscilla con un’ampiezza inferiore  ad una sogli predefinita; a causa della discretizzazione temporale l’oscillazione attorno ad un valore non necessariamente indica il raggiungimento di una configurazione di minimo locale.
  3. Viene raggiunto il massimo numero di iterazioni, , usualmente fissato ad un valore tale da evitare interruzioni premature intercettando, nel contempo, situazioni di non convergenza dell’algoritmo.
Figura 2. Se il valore di K4 è troppo piccolo, il sistema si arresta prematuramente.

La condizione [C.1] è stata introdotta in considerazione del fatto che nell’intorno della posizione di equilibrio la risultante delle forze agenti sui nodi tende a zero e dunque anche lo spostamento dei nodi stessi. In realtà, lo spostamento dei nodi dipende fortemente anche dalla costante K4: valori troppo grandi inducono il grafo ad esplodere, mentre valori troppo piccoli generano spostamenti ridotti che portano al verificarsi della condizione di arresto troppo prematuramente, come illustrato in Figura 2, cioè prima del raggiungimento di una configurazione ottimale.

Figura 3. Con un’opportuna taratura dei parametri l’algoritmo genera una configurazione caratterizzata da una discreta leggibilità.

Un ulteriore ragione per la quale si è optato per la tecnica di auto-adattamento della costante K4, è prettamente di natura empirica: si è osservato sperimentalmente un comportamento soddisfacente dell’algoritmo quando, per la costante K4, viene fissato un valore iniziale relativamente elevato. Nel corso della simulazione, questo valore viene poi fatto decrescere dai meccanismi autoadattativi ogniqualvolta si verifica un aumento di . Questa impostazione generalmente dà luogo ad un comportamento iniziale di tipo esplosivo, seguito da una rapida contrazione, per terminare con una configurazione del grafo caratterizzata da una buona leggibilità, come esemplificato in Figura 3.

Figura 4. Il grafo corrispondente al modello CAD di una flangia.

Si è inoltre sperimentato che, per alcune configurazioni, durante il processo di contrazione seguente alla esplosione iniziale, il valore di riprende lentamente ad aumentare. In questo caso, la condizione d’arresto [C.2] arresta le iterazioni solo quando l’oscillazione è stata d’ampiezza sufficientemente piccola. Questo controllo, che consente di arrestare il calcolo solo in una posizione prossima alla posizione di equilibrio, è stato introdotto per consentire le forti oscillazioni di assestamento iniziali del valore di , indotte dalla posizione causale assegnata inizialmente ai nodi. L’interruzione dell’algoritmo in corrispondenza della riduzione di non assicura necessariamente una “migliore” posizione dei nodi.

Figura 5. Visualizzazione dei nodi definiti a partire da un nodo dato: prima modalità.

6. POTENZIALITÀ E UTILIZZO: UN ESEMPIO.

Al fine di verificare sul campo le reali potenzialità ed i limiti dello strumento proposto, si sono realizzate alcune interfacce applicative che consentono di visualizzare le strutture relazionali di modelli creati con alcuni dei più noti sistemi CAD. Uno degli esempi maggiormente utilizzati nella messa a punto dell’algoritmo è il modello parametrico bidimensionale di una flangia. Il corrispondente grafo è composto da 198 nodi, ciascuno dei quali rappresenta un’entità grafica bidimensionale o un valore reale corrispondente ad un parametro del modello.

La figura 4 illustra il grafo così come disposto nello spazio tridimensionale dall’algoritmo proposto. Nei primi livelli gerarchici si possono notare alcuni cluster di nodi che assumono la tipica struttura conica, mentre ai livelli più bassi l’intreccio di archi non consente di riconoscere alcuna struttura ricorrente. In una tipica sequenza operativa, potrebbe essere necessario selezionare un sottoinsieme dei nodi del grafo portandoli in evidenza e contemporaneamente mettendo in secondo piano gli altri. Ad esempio selezionando il nodo corrispondente ad un asse della flangia, è possibile richiedere al sistema software di evidenziare tutti quei  nodi che rappresentano entità geometriche o parametri che direttamente o indirettamente fanno riferimento o si appoggiano a tale asse (tali nodi vengono indicati come maggiori diretti).

Figura 6. Visualizzazione dei nodi definiti a partire da un nodo dato: seconda modalità.

All’utente sono offerte tre differenti modalità per realizzare questa operazione: la prima modalità, illustrata in Figura 5, assegna ai nodi non selezionati il colore grigio lasciando agli altri nodi colore originale; la seconda modalità, illustrata in figura 6, nasconde temporaneamente i nodi non selezionati; la terza modalità migliora ulteriormente la visualizzazione dei nodi selezionati ricalcolandone la posizione.

Oltre a questa funzionalità, particolarmente utile nell’interazione con grafi corrispondenti a modelli parametrici o a complessivi, sono state sperimentate anche alcune funzionalità aggiuntive:

  • Selezione ed evidenziazione dei nodi che contribuiscono alla definizione di un noto indicato dall’utente: cioè di quei nodi raggiungibili mediante un cammino orientato che parta dal nodo indicato.
  • Selezione dei nodi appartenenti ad un livello gerarchico dato: per definizione di livello gerarchico non esisto archi tra questi nodi.
  • Evidenziazione dei cammini orientati esistenti tra due nodi liberamente scelti dall’utente.
  • Evidenziazione di tutte le relazioni uscenti da un nodo.
  • Evidenziazione di tutte le relazioni orientate che raggiungono un nodo (entranti).
Figura 6. Visualizzazione dei nodi definiti a partire da un nodo dato: terza modalità.

BIBLIOGRAFIA

[1] F. Folini, I. Bozza, Interaction with the relational structures of computer aided design models; 4th IFAC Workshop on Intelligent Manufacturing System: IMS ’97; Luglio 1997

[2] E. R. Gansner, S. C. North, K. P. Vo, DAG – A program that draws directed graphs; Software-practice and experience, Vol. 18 (11), Novembre 1988.

[3] K. Sugiyama, K. Misue, Graph drawing by the magnetic spring model; Journal of visual languages and computing, Vol. 6 (3), Settembre 1995.

[4] D. Castellazzi, Studio e sperimentazione di tecniche per la visualizzazione 3D di basi di dati strutturate in grafi aciclici orientate (DAG); Tesi di Laurea, Politecnico di Milano, Dicembre 1997.