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-Spagnolo “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, in particolare delle relazioni tra dati, modelli e documenti. La presenza di una tale mole di informazioni non garantisce di per sé l’accessibilità e la fruibilità per gli utenti, che si trovano sovente a dover interagire con strumenti disomogenei e inutilmente complessi. Al fine di sperimentare nuove modalità di interazione che rendano tali risorse più utilizzabili e più rapidamente, 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 del prodotto, come i sistemi CAD/CAM/CAE, è caratterizzata da un continuo arricchimento e potenziamento dei rispettivi modelli. Allo scopo di rappresentare aspetti sempre più ampi del prodotto e del processo di progettazione, si accrescono 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 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 dotati di funzionalità sempre più ampie, ma al contempo non riesce a garantire un accesso alle informazioni sufficientemente semplice e diretto, ostacolando di conseguenza 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 offrano modalità alternative di accesso e di controllo delle informazioni, affiancando le tradizionali modalità di interazione grafiche e testuali. A fronte di queste esigenze, si è avviato uno studio per individuare e sperimentare nuove modalità di visualizzazione e interazione con strutture informative caratterizzate da ricche relazioni. In particolare, si è sperimentato uno strumento per la visualizzazione di tali strutture in forma 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 quale è vero limitato 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, uno stato ottimale. In particolare, il modello fisico utilizzato associa a ogni nodo una massa puntiforme e a 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 esistano cammini chiusi orientabili.

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 all’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 necessario, di ricondursi facilmente alla classe più generale dei grafi, semplicemente rimuovendo una serie di vincoli e disattivando 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 per grafi più generali, cioè per quelli 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 sulla funzione di ordinamento parziale.

3. LA VISUALIZZAZIONE DI MODELLI TRIDIMENSIONALI.

Nel passaggio da una visualizzazione bidimensionale a una tridimensionale, i meccanismi di interazione e le metafore adottate dall’interfaccia utente mutano radicalmente. Usualmente, il dispositivo di visualizzazione a cui sono destinate le rappresentazioni 2D di grafi non è soltanto il video, ma può essere anche una stampante o un 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 rispetto alle limitate dimensioni di un video, il quale, anche se supporta lo scorrimento 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, diventano invece un elemento essenziale per consentire all’utente la fruizione di quanto visualizzato.

Gran parte degli strumenti software oggi disponibili sta evolvendo gradualmente verso modalità di visualizzazione tridimensionali, come testimoniato dalla crescente diffusione delle tecniche di realtà virtuale. Pertanto, è importante lo studio di nuove tecniche di 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 soltanto 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 un 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, fino a uno stato d’equilibrio. La configurazione finale, cui converge l’algoritmo, corrisponde, dal punto di vista della chiarezza e della leggibilità della rappresentazione tridimensionale, a uno stato ottimale. L’algoritmo presenta pertanto caratteristiche di intuitività e di 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 livelli gerarchici corrispondenti, che caratterizzano i DAG, conservando soltanto 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, anche molle con lunghezza di riposo diversa da zero, dette 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, nel modello esistono 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 K₁, K₂ e K₃ sono tre costanti. La costante K₂ rappresenta la lunghezza di riposo della molla planare; K₁ è la corrispondente “pendenza”, mentre K₃ è 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 si ha 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 a priori fissato, 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 è determinata disponendoli in un cerchio il cui raggio dipende dal 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 l’asse dei tempi è discretizzato. 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: deve rilevare il verificarsi di tale inconveniente e ridurre quindi la durata dell’intervallo temporale. La costante K4, pertanto, può essere variata dall’algoritmo: rimane invariabile soltanto per la durata di un intero passo di simulazione, alla fine del quale un test decide se ridurne il valore. 

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 aumenti da un passo di simulazione all’altro, è necessario ridurre K4.

Oltre alla media delle lunghezze degli archi, a ogni passo l’algoritmo misura un’altra grandezza significativa: il massimo spostamento di un nodo. Questo valore, con la costante K₄, è 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 è inferiore a un valore di soglia predefinito.
2. La lunghezza media degli archi, , oscilla con un’ampiezza inferiore  a una soglia predefinita; a causa della discretizzazione temporale, l’oscillazione attorno a un valore non necessariamente indica il raggiungimento di una configurazione minima 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.

La condizione [C.1] è stata introdotta considerando che, nell’ambito della posizione di equilibrio, la risultante delle forze agenti sui nodi tende a zero e, dunque, lo spostamento dei nodi. In realtà, lo spostamento dei nodi dipende fortemente anche dalla costante K4: valori troppo grandi inducono il grafo a 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.

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 ridotto 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.

Si è inoltre osservato che, per alcune configurazioni, durante il processo di contrazione successivo all’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 è d’ampiezza sufficientemente piccola. Questo controllo, che consente di arrestare il calcolo solo in una posizione prossima a quella di equilibrio, è stato introdotto per mitigare 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 posizione dei nodi “migliorata”.

6. POTENZIALITÀ E UTILIZZO: UN ESEMPIO.

Al fine di verificare sul campo le reali potenzialità e i limiti dello strumento proposto, sono state realizzate alcune interfacce applicative che consentono di visualizzare le strutture relazionali di modelli creati con alcuni dei più noti sistemi CAD. Uno degli esempi più 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 associato a un parametro del modello.

La figura 4 illustra il grafo così come disposto nello spazio tridimensionale dall’algoritmo proposto. Nei primi livelli gerarchici si osservano alcuni cluster di nodi che presentano 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 a 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 a o si appoggiano a tale asse (tali nodi vengono indicati come maggiori diretti).

All’utente sono offerte tre modalità per realizzare questa operazione: la prima, illustrata in Figura 5, assegna ai nodi non selezionati il colore grigio, lasciando agli altri nodi il colore originale; la seconda, illustrata in Figura 6, nasconde temporaneamente i nodi non selezionati; la terza, illustrata in Figura 7, 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 nodo indicato dall’utente: cioè, di quei nodi raggiungibili mediante un cammino orientato che parta dal nodo indicato.
• Selezione dei nodi appartenenti a un livello gerarchico dato: per definizione, non esistono archi tra i 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).

Bibliografia

1. F. Folini, I. Bozza, Interaction with the relational structures of computer-aided design models; 4th IFAC Workshop on Intelligent Manufacturing Systems: 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), November 1988.
3. K. Sugiyama, K. Misue, Graph drawing by the magnetic spring model; Journal of Visual Languages and Computing, Vol. 6 (3), September 1995.
4. D. Castellazzi, Studio e sperimentazione di tecniche per la visualizzazione 3D di basi di dati strutturate in grafi aciclici orientati (DAG); Tesi di Laurea, Politecnico di Milano, dicembre 1997.