DE69230331T2

DE69230331T2 - Computervorrichtung und verfahren zur identifizierung von finite-elementen in der interaktiven modellierung

Info

Publication number: DE69230331T2
Application number: DE69230331T
Authority: DE
Inventors: James Roth
Original assignee: Digital Equipment Corp
Current assignee: Digital Equipment Corp
Priority date: 1991-04-01
Filing date: 1992-03-31
Publication date: 2000-08-24
Anticipated expiration: 2012-04-01
Also published as: EP0532740A1; US5289567A; DE69230331D1; WO1992017854A1; EP0532740B1

Description

Hintergrund der Erfindung

Die "Analyse finiter Elemente" ist ein mathematischer Zugang zum Lösen großer (komplexer) Probleme. Im allgemeinen wird der Gegenstand in viele Stücke segmentiert oder diskretisiert, die Lösungen in geschlossener Form besitzen. Das heißt, jedes Stück ist durch eine lineare Gleichung definierbar, so daß es ein "finites Element" ist. Gemeinsam bilden die linearen Gleichungen der Stücke ein System aus gleichzeitig lösbaren Gleichungen.
Es existieren Computerprogramme zum Simulieren der Analyse finiter Elemente in verschiedenen Anwendungen. Finite Modellierungsprogramme werden z. B. von Entwicklungsingenieuren verwendet. Typischerweise werden viele Tausende von Elementen erzeugt, um ein Gegenstandsobjekt und insbesondere dreidimensionale Objekte zu modellieren. Für jedes Element gibt es geometrische Informationen, z. B. eine (x, y, z)-Koordinate an einem Punkt in dem Element, einen Elementtyp, die Materialeigenschaft, den Beanspruchungswert, die Verschiebung, den Wärmewert usw. Derartige Informationen sind durch lineare Gleichungen für die Elemente definierbar. Deshalb wird die finite Analyse verwendet, um das betreffende Objekt zu modellieren.
Beispielhafte Programme finiter Modellierung umfassen: ANSYS von Swanson Analysis Systems Inc., Houston, PA; SUPERTAB von Structural Dynamics Research Corp., Ohio; und PATRAN von PDA Engineering, Costa Mesa, CA.
Ein Nachteil einer derartigen Modellierung finiter Elemente besteht darin, daß die große Anzahl der Elemente ein Problem bei der Verifizierung der geometrischen Rich tigkeit des Modells und der resultierenden Elementinformationen in dem Modell darstellt. Das heißt, eine Notwendigkeit in Computerprogrammen für die finite Modellierung ist eine sehr schnelle dialogorientierte Weise für einen Ingenieur, ein Modell zu betrachten und Abfragen auszuführen, vorzugsweise durch direktes Zeigen mit dem Bildschirm-Cursor durch Operationen mit der Maus. Typische Informationen, die durch die Abfragefunktionen zurückzuschicken sind, enthalten die geometrischen Informationen und die Informationen über die physikalischen Eigenschaften/Materialeigenschaften. Im Idealfall ist eine Schnittstelle für die "direkte Manipulation" gewünscht, so daß ein Ingenieur die Empfindung hat, daß er auf Stellen an einem Objekt in seiner Hand zeigt.
Manche existierenden Computerprogramme zur Modellierung finiter Elemente, wie z. B. PARTAN von PDA Engineering, Costa Mesa, CA, erlauben Datenabfragen. Insbesondere verwenden diese Programme einfache lineare Suchen durch eine Geometriedatenbank. Typischerweise gibt ein Ingenieur, der derartige Computerprogramme verwendet, einen Befehl ein, der angibt, daß irgendeine Anzahl von Elementen "auszusuchen" ist und daß die bezeichneten Informationen hinsichtlich der Elemente zurückzuschicken sind. Unter Verwendung der Maus bewegt er dann den Bildschirm-Cursor zu einem Punkt an einem angezeigten Modell und betätigt eine Maustaste; nach ein paar Sekunden findet das Computerprogramm die dem Cursor am nächsten gelegenen Elemente und gibt die angeforderten Informationen aus. Oft wird, bedingt durch das Durcheinander eines komplexen 3-dimensionalen Modells in einer zweidimensionalen Bildschirmansicht, ein falsches Element ausgesucht, wodurch ein weiterer Versuch und einige weitere Sekunden des Wartens erforderlich sind. Das wiegt am schwersten an sehr großen Modellen, wo Abfragen in der Größenordnung von zehntausenden auszuführen sind, weil diese Modelle am langsam sten zu verarbeiten sind.
Folglich können die existierenden Abfragetechniken sehr langsam sein, weil Tausende Elemente für einen "Treffer" überprüft werden müssen. Infolge dieses Engpasses schaffen die Computerprogramme für die Modellierung finiter Elemente keine schnelle menschliche Schnittstelle für die Abfragefunktionen. Demzufolge gibt es einen Bedarf an einer besseren dialogorientierten Weise für einen Ingenieur, um ein Modell zu betrachten und Abfragen hinsichtlich der Elemente des Modells auszuführen.
"Proc. Sth Int. Conf. on Data Engineering, 8.-10. Feb. 1998. L. A., CA, USA; Seiten 606-615; Greene: An Implementation and Performance Analysis of Spatial Data Access Methods" offenbart eine Computervorrichtung für den Anwenderdialog mit Objekten, die auf hierarchisch organisierten Bäumen basieren.

Zusammenfassung der Erfindung

Die vorliegende Erfindung ist in den unabhängigen Ansprüchen 1 und 4 definiert. Die abhängigen Ansprüche definieren besondere Ausführungsformen der Erfindung

Kurzbeschreibung der Zeichnung

Die vorangehenden und weitere Aufgaben, Merkmale und Vorteile der Erfindung werden deutlich aus der folgenden, ausführlicheren Beschreibung bevorzugter Ausführungsformen der Erfindung, die in der beigefügten Zeichnung veranschaulicht sind, worin sich gleiche Bezugszeichen auf dieselben Teile in sämtlichen verschiedenen Ansichten beziehen. Die Zeichnung ist nicht notwendigerweise maßstabgerecht, die Betonung liegt statt dessen auf der Erläuterung der Prinzipien der Erfindung.
Fig. 1 ist eine schematische Darstellung eines Computersystems, das eine Ausführungsform der vorliegenden Erfindung verwendet.
Fig. 2a ist eine schematische Darstellung einer Ausführungsform der vorliegenden Erfindung, die in dem System nach Fig. 1 verwendet wird.
Fig. 2b und 2c sind Blockdiagramme der Datenstrukturen, die durch die vorliegende Erfindung verwendet werden.
Fig. 3a-3c sind Ablaufpläne der vorliegenden Erfindung.
Fig. 4a-4g sind Darstellungen der Schritte, die in dem Ablaufplan nach Fig. 3a-3c ausgeführt werden.

Genaue Beschreibung der bevorzugten Ausführungsformen

Fig. 1 veranschaulicht ein Computersystem 11, das eine Ausführungsform der vorliegenden Erfindung verwendet. Im allgemeinen ist ein digitaler Prozessor 13 gezeigt, der an eine Tastatur 17 und eine Maus 15 gekoppelt ist, um davon die Anwendereingabe zu empfangen, und der an eine Anzeigeeinheit 19 gekoppelt ist, um darauf die Ausgabe anzuzeigen. Im digitalen Prozessor 13 befindet sich ein Computerprogramm 21 zur Modellierung finiter Elemente, das die Computervorrichtung 23 der vorliegenden Erfindung verwendet. Das Computerprogramm 21 ermöglicht einem Anwender, unter Verwendung der Analyse finiter Elemente ein gewünschtes Objekt zu modellieren. Insbesondere erzeugt das Computerprogramm 21 ein Modell eines betreffenden Objekts, das mehrere diskrete Elemente besitzt, die teilweise durch Eingabedaten des Anwenders und teilweise durch Berechnungen des Prozessors, die mit den Eingabedaten ausgeführt werden, definiert sind. Das Computerpro gramm 21 ermöglicht (durch den digitalen Prozessor 13) die Anzeige des erzeugten Modells in einer Bildschirmansicht auf der Anzeigeeinheit 19, wobei es einen Anwenderdialog mit der Bildschirmansicht des Modells durch Operationen mit der Tastatur 17 und/oder der Maus 15 ermöglicht. Die Verfahren und Mittel, um das Vorangehende zu erreichen, sind in der Technik bekannt, wobei sie Computerprogramme wie z. B. "ANSYS" von Swanson Analysis Systems, Inc., "PATRAN" von PDA Engineering, Costa Mesa, CA und Softwaresysteme des Graphikstandards "PHIGS" (Programmers Hierarchical Interactive Graphics System - hierarchisches Programmiererdialoggraphiksystem) enthalten, die von der Digital Equipment Corporation, der Hewlett Packard Company und dergleichen für die entsprechenden Arbeitsplatzrechner verfügbar sind.
Spezifisch für die Computervorrichtung 23 der vorliegenden Erfindung gibt es anschließend an die Erzeugung des Modells Zeitpunkte, zu denen ein Anwender die Dateneingabe (die in den Berechnungen verwendeten unbearbeiteten Daten) oder die Ausgabe (die Ergebnisse der Berechnungen) für jeden Punkt in dem Modell zu kennen wünscht. Um derartige Daten zu erhalten, wirkt der Anwender vorzugsweise durch die Maus 15 mit der Bildschirmansicht des Modells wie folgt zusammen. Der Anwender wählt aus einem Menü einen "Abfrage"-Punkt oder ähnliches, der in der Bildschirmansicht angezeigt wird, indem er den Bilschirm- Cursor 29 in der Position der Bildschirmansicht der gewünschten Menüauswahl anordnet und eine Maustaste betätigt (klickt). Der Anwender betätigt dann die Maus, um den Bildschirm-Cursor 29 zu verschiedenen Positionen in der Bildschirmansicht des Modells zu bewegen, um in Wirklichkeit auf verschiedene Elemente in dem Modell zu zeigen (oder sie auszuwählen). Als Antwort darauf führt die Computervorrichtung 23 der vorliegenden Erfindung die folgenden Handlungen aus. In Echtzeit veranlaßt die Com putervorrichtung 23 der vorliegenden Erfindung, daß das Element, auf das der Cursor 29 gegenwärtig zeigt, in der Bildschirmansicht hervorgehoben angezeigt wird. Außerdem gibt die Computervorrichtung 23 der vorliegenden Erfindung in der Bildschirmansicht die vom Anwender angeforderten Informationen gemäß dem gewählten Menüabfragepunkt aus (d. h., sie zeigt sie an), ungeachtet wie komplex das Modell ist. Es gibt folglich keine Notwendigkeit für den Anwender, die Maustasten zu betätigen und zu warten; lediglich das Bewegen des Cursors 29 anderswohin in der Bildschirmansicht des Modells wählt ein neues abzufragendes Element, was wiederum die Anzeige der vom Anwender angeforderten Informationen erzeugt.
Ferner schafft die Computervorrichtung 23 der vorliegenden Erfindung einen geteilten Bildschirm (oder ein separates Fenster in) der Bildschirmansicht des Modells. Speziell schafft die vorliegende Erfindung in einem Teil 27 der Bildschirmansicht eine lokalisierte, ausführliche Ansicht eines Elements oder angrenzender Elemente, auf das der Cursor 29 gegenwärtig zeigt. In einem zweiten Teil 25 der Bildschirmansicht ist das Modell gänzlich mit einem Hinweis, wie z. B. einem Rechteck mit gestrichelten Linien, auf den Abschnitt des Modells, der in dem ersten Teil 27 gezeigt ist, angezeigt.
Im Ergebnis schafft die vorliegende Erfindung eine unmittelbare Rückkopplung für den Anwender, sie neigt weniger zu Fehlern (d. h., sie schafft eine genauere Anwenderauswahl der zu betrachtenden Modellelemente) und sie ermutigt zu einer viel gründlicheren Verfikation und Interpretation eines Modells. Die Grenze ist nicht die Verarbeitungszeit, sondern der Speicher, um das Modell zu halten.
Um das Vorangehende zu erreichen, verwendet die Computer vorrichtung 23 der vorliegenden Erfindung einen Speicherblock 31 zum Halten der unbearbeiteten und der berechneten Daten jedes Elements des Modells, sowie eine Baumdatenstruktur 33 im Arbeitsspeicher zum Durchsuchen des Speicherblocks 31 und zum Zugreifen auf den Speicherblock 31 in kürzeren Zeitspannen als denjenigen, die im Stand der Technik möglich sind. Wie in Fig. 2a veranschaulicht ist, ist die Baumdatenstruktur 33 mit einer Wurzel 39 an der Baumeinsprungebene, verschiedenen nachfolgenden Ebenen aus Unterbäumen, die aus Baumknoten 35 und inneren Blattknoten 55 gebildet ist, und einer Abschlußebene aus Blattknoten 37 angeordnet. Jeder Blattknoten 37, 55 hält einen Zeiger 57 zu der entsprechenden Stelle in dem Speicherblock 31, der die gewünschten (unbearbeiteten und berechneten) Daten eines entsprechenden Elements des Modells hält. Die Zeiger 57 werden erzeugt, während der Baum 33 aufgebaut wird.
Der Baum 33 wird in einer Vorverarbeitungsphase aufgebaut und in der Dialogphase genutzt, wie in den Fig. 3a-3b veranschaulicht ist. Die Idee besteht darin, daß die geometrischen Daten des Modells zu dem Zeitpunkt, zu dem eine Abfrageoperation ausgelöst wird, statisch sind. Folglich wird die für die Vorverarbeitung der geometrischen Daten aufgewandte Zeit über eine große Anzahl von Dialogabfragen amortisiert. Das Abfragen wird so schnell abgewickelt, daß die Ausgangsdaten sogar auf preiswerten Tisch-Arbeitsplatzrechnern kontinuierlich als Antwort auf die Cursor-Bewegung aktualisiert werden können.

Vorverarbeitungsphase

In Fig. 3a führt die Computervorrichtung 23 der vorliegenden Erfindung zuerst eine Initialisierung 65 in der Vorverarbeitungsphase aus. Die Initialisierung 65 enthält die Herstellung eines Zeigers auf die Wurzel 39 der Baum datenstruktur 33, das Zuweisen von Speicher für den Baum 33 und den Speicherblock 31 sowie die Aufzeichnungsidentifikation (oder -zuordnung) des Baums 33 und des Speicherblocks 31 mit dem speziellen Modell. Ferner ermöglicht die Computervorrichtung 23 der Erfindung während der Initialisierung 65, daß die geometrischen finiten Elemente und die relevanten Menüs, die in die Bildschirmansicht zu projizieren sind. Dieses wird typischerweise als Antwort auf eine Anwenderauswahl einer Ansicht des Modells ausgeführt. In Wirklichkeit dient dieses zum Definieren einer aktuellen Sitzung und der Arbeitselemente (Gegenstandselemente) des Modells für die Sitzung.
Wenn durch eine Menüauswahl eine Abfrageoperation ausgelöst wird, konstruiert die Computervorrichtung 23 der Erfindung rekursiv den Baum 33, einen Baumknoten 35 und die zugeordneten Blattknoten 37, 55 zu einem Zeitpunkt, wie bei 67 in Fig. 3a angezeigt und als nächstes mit Bezugnahme auf den Ablaufplan nach Fig. 3b und die Veranschaulichung nach Fig. 4a-4g beschrieben ist. In dem Beispiel, das in Fig. 4a-4g veranschaulicht ist, ist ein gewünschtes Modell gezeigt, das aus im allgemeinen prismaförmigen Elementen 83 gebildet ist, die in Reihe verbunden sind.
Die Computervorrichtung 23 der vorliegenden Erfindung berechnet einen zweidimensionalen Grenzkasten 81 (z. B. ein Rechteck, wie in Fig. 4a gezeigt ist) um die aktuelle Menge der Elemente 83, die in dem Modell angezeigt werden. Die Computervorrichtung 23 der vorliegenden Erfindung erreicht dieses durch das lineare Abtasten der Menge der Elemente 83 und das Bestimmen der größten Entfernung entlang zweier orthogonaler Achsen (zum Beispiel der x- und y-Achse in den ersten vier Schritten 71 nach Fig. 3b), die die Elemente 83 überbrücken. Als nächstes bestimmt die Computervorrichtung 23 der vorliegenden Erfindung, ob sich weniger als eine vorher zugeordnete An zahl von Elementen (zum Beispiel ungefähr drei) innerhalb des Grenzkastens 81 befinden. Falls es sie gibt, werden die Elemente als eine "überbrückende Menge" bezeichnet und durch einen inneren Blattknoten 55 dargestellt, der von dem aktuellen Arbeitsbaumknoten 35 des Baums 33 abzweigt.
Ansonsten werden typischerweise an den Mittelpunkten der Seiten der rechtwinkligen Form des Kastens zwei orthogonale Trennlinien (Divlne 1 und Divlne 2, die in Fig. 4b gezeigt sind) für den Grenzkasten 81 berechnet, wie bei 69 in Fig. 3b ausführlich beschrieben ist. Es ist selbstverständlich, daß in anderen Implementierungen des Baums 33 andere Punkte geeignet sind. Deshalb liegt eine Trennlinie entlang der Hauptachse des Grenzkastens 81 und teilt die rechteckige Form longitudinal in Hälften. Die zweite Trennlinie liegt entlang der Nebenachse des Grenzkastens 81 und teilt die rechteckige Form entlang einer orthogonalen Richtung weiter in Hälften. Die längste Trennlinie, d. h. die Trennlinie entlang der Hauptachse, wird als die "Teilungsachse" bezeichnet. Es ist selbstverständlich, daß in einer ähnliche Weise die kürzeste Trennlinie als die Teilungsachse dienen kann.
Wie bei 73 (Fig. 3b) gezeigt ist, wird dann die aktuelle Menge der Elemente 83 gemäß den Segmenten, in die der Grenzkasten 81 durch die Trennlinien geteilt worden ist, in Untermengen geteilt. Es wird angemerkt, daß die Segmente, in die der Grenzkasten 81 geteilt worden ist, selbst Rechtecke oder Unter-Grenzkästen sind. Diese Elemente 83, die beide Trennlinien überbrücken, sind in einer "überbrückenden Menge" untergebracht, wobei sie durch einen inneren Blattknoten 55 dargestellt sind, der von dem aktuellen Arbeitsbaumknoten 35 des Baums 33 abzweigt. Die verbleibenden Elemente sind abhängig davon, ob sich die Elemente vollständig auf einer Seite der Teilungs achse befinden, ob sie die Teilungsachse überbrücken oder ob sie sich auf der gegenüberliegenden Seite der Teilungsachse befinden, in den linken, mittleren bzw. rechten Unterbäumen des aktuellen Arbeitsbaumknotens 35 untergebracht. Diese Unterbäume (d. h., die Untermengen der Elemente) sind in den entsprechenden Knoten des Baums 33 aufgezeichnet, insbesondere besitzt jeder Unterbaum einen Wurzelknoten, der durch einen entsprechenden Baumknoten 35 definiert ist, der von dem aktuellen Arbeitsbaumknoten 35 abzweigt.
Als nächstes wird jeder Unterbaum als eine entsprechende Untermenge der Modellelemente 83 gemäß den Segmenten (d. h. den Unter-Grenzkästen) enthaltend interpretiert, in die der Grenzkasten 81 geteilt wurde. Deshalb gibt es für jeden Unterbaum einen entsprechenden Unter-Grenzkasten um die Untermenge der Modellelemente, die den Unterbaum definieren. Jeder Unter-Grenzkasten wird als ein selbständiger Grenzkasten behandelt, wobei er unter Verwendung der vorangehenden Grenzkasten- und Trennlinientechniken rekursiv verarbeitet wird, d. h., durch einen Aufruf der Baumkonstruktionsprozedur 67, die in Fig. 3b umrissen ist.
In dem Beispiel nach Fig. 4a-4g dient die Divlne 2 (Fig. 4b) als die Teilungsachse. Wie in Fig. 4b und 4c gezeigt ist, befindet sich die Untermenge 85 der Modellelemente, die auf der linken Seite der Teilungsachse (Divlne 2) gebildet ist und diese enthält, innerhalb ihres eigenen Grenzkastens. Die Untermenge 85 der Elemente 83 ist in einem linken Unterbaum des aktuellen Arbeitsbaums untergebracht und in einer Menge von Baumknoten (nur der Wurzelknoten ist gezeigt) aufgezeichnet, die von dem aktuellen Arbeitsbaumknoten 35 abzweigen, wie bei L in Fig. 4g veranschaulicht ist.
Die Elementteilmenge 87, die in Fig. 4b gezeigt ist, überbrückt die Teilungsachse. Die Untermenge 87 der Elemente 83 ist in einem mittleren Unterbaum untergebracht und in einer Menge aus Baumknoten mit einem Wurzelknoten aufgezeichnet, der von dem aktuellen Arbeitsbaumknoten 35 abzweigt, wie in Fig. 4g bei M veranschaulicht ist. Es wird angemerkt, daß in Fig. 4d die mittlere Untermenge 87 in ihrem eigenen Grenzkasten (d. h. dem Unter-Grenzkasten des Grenzkastens 81) gezeigt ist, der durch Ausdehnung entlang der x-y-Achsen der Elemente, die die Divlne 2 überbrücken, definiert ist. Die Untermenge 87 schließt die Elemente 83 der obenbeschriebenen überbrückenden Menge 91 aus.
Wie in Fig. 4e unabhängig gezeigt ist, befindet sich die Untermenge 89 (Fig. 4a), die auf der rechten Seite der Teilungsachse gebildet ist und diese enthält, innerhalb ihres eigenen Grenzkastens (d. h. des Unter-Grenzkastens des Grenzkastens 81). Die Untermenge 89 der Elemente 83 ist in einem rechten Unterbaum des aktuellen Arbeitsbaums untergebracht und in einer Menge von Baumknoten mit einem Wurzelknoten aufgezeichnet, der von dem aktuellen Arbeitsbaumknoten 35 abzweigt, wie bei R in Fig. 9 g veranschaulicht ist.
Die Untermenge 91 der Elemente 83, die sowohl die Divlne 1 als auch die Divlne 2 in Fig. 4b überbrückt, bildet eine überbrückende Menge. Diese Menge ist durch einen inneren Blattknoten 55, der von dem aktuellen Arbeitsbaumknoten 35 abzweigt, wie in Fig. 4g veranschaulicht ist, dargestellt und in ihm aufgezeichnet. Fig. 4f zeigt diese Untermenge 91 in ihrem eigenen Grenzkasten, der durch die Ausdehnung entlang der x-y-Achsen der Elemente, die sowohl die Divlne 1 als auch die Divlne 2 überbrücken, definiert ist. Dieses sind die Elemente, die von der mittleren Untermenge 87 ausgeschlossen sind (Fig. 4d).
Gemäß dem Vorangehenden entsprechen die Baumknoten 37, 55 den überbrückenden Mengen, wobei sie in Fig. 2a mit einem "S" bezeichnet sind, während die Baumknoten 35 in Fig. 2a mit einem "T" angezeigt sind. Jeder Baumknoten 35 und jeder Blattknoten 37, 55 des Baums 33 hält die entsprechenden Informationen in Speicherdatensätzen, die in Fig. 2b und 2c veranschaulicht sind. Der Datensatz für einen Baumknoten 35, wie er in Fig. 2b veranschaulicht ist, besitzt eine Kopfzeile 41, die anzeigt, daß der Datensatz einem Baumknoten 35 entspricht, im Gegensatz zu einem Blattknoten 37, 55. Ein Koordinatenfeld 43 des Datensatzes zeigt die x-, y-Koordinaten des Grenzkastens an, der für den Baumknoten 35 des Datensatzes definiert ist. Das Feld 45 zeigt die Teilungsachsen an, die für den Grenzkasten hergestellt sind. Die folgenden Felder 47 schaffen vier Zeiger in den Speicherblock 31. Der erste Zeiger zeigt zu den Adressen des Speicherblocks 31 der Modellelemente der überbrückenden Menge, d. h., der Menge aus Elementen, die beide Trennlinien des Grenzkastens überbrücken. Ein zweiter Zeiger zeigt die Adressen des Speicherblocks 31 der Modellelemente des linken Unterbaums an, der von dem Baumknoten 35 abzweigt, der diesem Datensatz zugeordnet ist. Ein dritter Zeiger zeigt zu den Adressen des Speicherblocks 31, die die Modellelemente eines mittleren Unterbaums enthalten, der von dem Knoten 35 des Datensatzes abzweigt. Ein vierter Zeiger zeigt auf die Adressen des Speicherblocks 31 für die Modellelemente des rechten Unterbaums, der von dem Knoten 35 des Datensatzes abzweigt.
In Fig. 2c besitzt ein Datensatz, der einem Blattknoten 37, 55 des Baums 33 und folglich einer überbrückenden Menge zugeordnet ist, wie folgt drei Felder. Ein Kopffeld 49 stellt einen Hinweis bereit, daß der Datensatz einen Blattkonten 37, 55 (eine überbrückende Menge) betreffende Informationen hält. Ein zweites Feld 51 stellt die geometrischen Koordinaten des Grenzkastens bereit. Ein drittes Feld 53 stellt einen Zeiger auf die Liste der Modellelemente in der überbrückenden Menge bereit.
Wenn auf diese Weise der Baum 33 erzeugt ist, werden die Datensätze für die überbrückenden Mengen (Blattknoten 37, 55) und die Baumknoten 35 erzeugt. Falls keine Modellelemente in irgendeine der gebildeten Untermengen (d. h. Unterbäume) eines Baumknotens 35 fallen, wird statt dessen ein Nullzeiger in den Baum 33 eingefügt.
Die vorangehende Baumanordnung und -bildung ist für eine Art Geometrie gut geeignet, die sich bei der Modellierung finiter Elemente ergibt. Falls irgendein besonders großes Element eines Gegenstandsmodells vorliegt, wird es wahrscheinlich in einer überbrückenden Menge (einem inneren Blattknoten 55) in der Nähe der Wurzel 39 des Baums 33 dargestellt werden, wo es die Klassifikation der verbleibenden Elemente des Modells nicht weiter beeinflussen wird. Andererseits gibt es normalerweise nicht sehr viele überbrückende Mengen (innere Blattknoten 55) in der Nähe der Baumwurzel 39, deshalb wird, wie als nächstes beschrieben ist, die Zeit minimiert, die das Durchlaufen des Baums 33 während der Abfragephase mit sich bringt.

Abfragephase

In der Abfragephase 75 (Fig. 3a) wird der Baum 33 für das Dialogabfragen oder das Zeichnen verborgener Linien und andere Anwendungen wiederholt verwendet. In der bevorzugten Ausführungsform wählt ein Anwender eine Region eines gewünschten Modells, das in der Bildschirmansicht auf der Anzeigeeinheit 19 dargestellt ist, durch Positionierung des Cursors 29 auf einem angezeigten Element in der gesuchten Region aus. Als Antwort zeigt die vorliegende Er findung die Region in der Nähe des Bildschirm-Cursors 29 in einem Hauptteil 27 der Bildschirmansicht an und gibt auf dem Bildschirm einige numerische Daten (wie z. B. die Beanspruchungswerte oder eine 3D-Koordinate) über das Element aus, das am nächsten zu dem Cursor 29 angeordnet ist. Um dieses zu erreichen, prüft die Computervorrichtung 23 der vorliegenden Erfindung rekursiv die Gegenstandsregion (die vorzugsweise durch ein Rechteck mit vorgegebener Größe oder eine andere geschlossene geometrische Form, die den Cursor 29 umgibt, definiert ist) gegen den Baum 33. Insbesondere folgt die Vorrichtung 23 den Zeigern 47 (Fig. 2b) und durchläuft den Baum 33 von dem Wurzelknoten 39 zu den nachfolgenden Ebenen der Baumknoten 35, wobei er mit den inneren Blattknoten 55 oder den Blattkonten 37 in der unteren Abschlußebene aufhört. Ein derartiges Durchlaufen erfolgt vorzugsweise durch eine rekursive Routine 79, die sich für jeden Baumknoten 35, auf den von den Zeigern 47 eines Knotens gezeigt wird, selbst aufruft, und ansonsten, wie folgt und wie in Fig. 3c umrissen ist, Knoten verarbeitet. Es ist selbstverständlich, daß die anderen gewöhnlichen Verfahren (rekursiv oder nicht) zum Durchlaufen des Baums 33, die die Zeiger und die Grenzkasteninformationen bei jedem Knoten des Baums verwenden, geeignet sind.
Die Vorrichtung 23 bestimmt in Wirklichkeit bei jedem Knoten, ob irgendwelche Unterbäume (Baumknoten 35) oder überbrückende Mengen (Blattknoten 37, 55) des Knotens Grenzkästen besitzen, wie in den entsprechenden Datensatzfeldern 43 bzw. 51 angezeigt ist, die die Gegenstandsabfrageregion überlappen. Falls die Koordinaten eines Grenzkastens eines Knotens bei 43, 51 nach Fig. 2b und 2c im wesentlichen in der Gegenstandsregion liegen, folgt die Vorrichtung 23 dem Zeiger 47, 53 der überbrückenden Menge, der dem Knoten entspricht und erhält die Elementdaten aus dem Speicherblock 31. Die Vorrichtung 23 prüft die Elementposition, die in diesen Daten angezeigt ist, gegen die aktuelle Cursor-Position. Wenn die zwei Positionen übereinstimmen, gibt die Vorrichtung 23 ferner die Elementdaten an die Anzeigeeinheit 19 für die Anzeige auf dem Bildschirmansichtsteil 27 aus.
Die vorangehende Suche ist weit schneller als das lineare Durchsuchen einer vollständigen Liste der Elemente wie im Stand der Technik. Ein typisches Beispiel könnte sein, daß pro Anfrage weniger als zwanzig Elemente aus einem Modell aus zehntausend Elementen in der vorliegenden Erfindung geprüft werden. Folglich ist die Anzahl der geprüften Elemente typischerweise zu dem Logarithmus der Anzahl der Elemente in dem Modell proportional. Diese Geschwindigkeitsverbesserung gegenüber dem Stand der Technik macht Dialogabfragen als Antwort auf die Cursor-Bewegung auf preiswerten Arbeitsplatzrechnern praktisch, was zu großen Zeitersparnissen in der normalerweise langwierigen Phase der Modellverifikation- und -interpretation führt.
Für das Zeichnen verborgener Linien kann die Bildschirmposition der Liniensegmente eines gewünschten Modells schnell nach Schnittpunkten mit den Koordinatenpositionen innerhalb der Grenzkästen der Knoten in dem Baum 33 überprüft werden. Die Bestimmung eines derartigen Schnittpunkts wird durch das Durchlaufen des Baums 33 und das Prüfen der Knoten 35, 37 erreicht, wie oben beschrieben ist. Das heißt, die Positionsinformationen der Elemente, auf die durch besondere Knoten des Baums 33 gezeigt wird, werden gegen die Cursor-Position in der Gegenstandsbildschirmansicht des Modells geprüft, um zu bestimmen, ob überlappende Punkte oder Liniensegmente in dem Modell existieren. Abermals wird durch die vorliegende Erfindung eine logarithmische Zeit pro Zeile anstelle einer linearen Abfragezeit erreicht.

Entsprechungen

Während die Erfindung mit Bezugnahme auf eine bevorzugte Ausführungsform davon ausführlich gezeigt und beschrieben worden ist, wird es für Fachleute selbstverständlich sein, daß darin verschiedene Änderungen in der Form und in den Einzelheiten ausgeführt werden können.

Claims

1. Computervorrichtung in einem Computersystem (11) für einen Anwenderdialog mit Modellen finiter Elemente, wobei die Vorrichtung (i) einen Speicher als Quelle von Modellen von Objekten, wobei jedes Modell aus mehreren Elementen (83) gebildet ist, (ii) einen Speicherbereich, der Daten hält, die jedes Element definieren, (iii) eine Anzeigeeinheit (19) zum Anzeigen von Bildschirmansichten eines Modells sowie (iv) einen digitalen Prozessor aufweist, der mit der Quelle von Modellen, dem Speicherbereich und der Anzeigeeinheit gekoppelt ist und den Anwenderdialog mit der Bildschirmansicht eines Modells ermöglicht, wobei die Computervorrichtung im Speicherbereich auf Daten von Elementen eines gewünschten Modells zugreift, mit:

(a) einem Arbeitsspeicher mit einem Datenbaum (33), der umfaßt:

einen Wurzelknoten (39) und

mehrere Baumknoten (35) und Blattknoten (37), die Untermengen von Elementen eines gewünschten Modells entsprechen,

wobei der Wurzelknoten (39) und die mehreren Baumknoten (35) und Blattknoten (37) hierarchisch in der Weise angeordnet sind, daß sich der Wurzelknoten auf der höchsten Ebene befindet, die Baumknoten (35) sich auf Zwischenebenen befinden und die Blattknoten (37) sich auf einer untersten Ebene befinden, wobei jeder Blattknoten einen Hinweis auf eine Stelle im ersten Speicherbereich von Daten entsprechender Elemente schafft,

wobei auf jeder der Zwischenebenen Knoten auf einer gemeinsamen Ebene gemäß räumlicher Beziehung entsprechender Untermengen von Elementen des Modells in bezug auf wenigstens eine Achse eines geometrischen Bereichs, der von den Elementen der entsprechenden Untermengen in einer Bildschirmansicht des Modells abgedeckt wird, angeordnet sind; und

(b) einer Prozessoreinrichtung, die durch den digitalen Prozessor ausführbar ist und die den Datenbaum als Antwort auf einen Anwenderdialog mit einem gewünschten Element eines auf der Anzeigeeinheit angezeigten Modells durchläuft, wobei die Prozessoreinrichtung den Baum entsprechend einem geometrischen Bereich durchläuft, in dem das gewünschte Element in einer Bildschirmansicht des Modells angeordnet ist, indem sie bestimmt, ob irgendwelche Baumknoten (35) oder Blattknoten (37) mit einer Abfrageregion überlappen, wobei die Prozessoreinrichtung einen Blattknoten (37) in dem dem gewünschten Element entsprechenden Baum lokalisiert und aus dem Blattknoten (37) einen Hinweis auf den Ort im ersten Speicherbereich von Daten des gewünschten Elements erhält, so daß der zugriff auf die Daten durch die Prozessoreinrichtung ermöglicht wird,

wobei die Vorrichtung dadurch gekennzeichnet ist, daß der geometrische Bereich (81), der von Elementen abgedeckt ist, die Knoten auf einer gemeinsamen Ebene entsprechen, rechteckig ist und eine longitudinale Hauptachse besitzt, derart, daß die Knoten auf der gemeinsamen Ebene so angeordnet sind, daß ein erster Knoten, der einer Untermenge von auf einer Seite der longitudinalen Hauptachse liegenden Elementen entspricht, an einem Ende der gemeinsamen Ebene angeordnet ist, ein zweiter Knoten, der einer Untermenge von auf der gegenüberliegenden Seite der longitudinalen Hauptachse liegenden Elementen entspricht, am gegenüberliegenden Ende der gemeinsamen Ebene angeordnet ist und ein dritter Knoten, der einer Untermenge von die longitudinale Hauptachse überbrückenden Elementen entspricht, zwischen dem ersten und dem zweiten Knoten auf der gemeinsamen Ebene angeordnet ist, und wobei der rechteckige geometrische Bereich (81) ferner eine Nebenachse enthält, die transversal zur longitudinalen Hauptachse verläuft; und

der Datenbaum ferner einen Blattknoten (55) besitzt, der einer Untermenge von Elementen entspricht, die sowohl die longitudinale Hauptachse als auch die transversale Nebenachse überbrücken.

2. Computervorrichtung nach Anspruch 1, wobei die Prozessoreinrichtung eine rekursive Routine zum Durchlaufen des Baums aufweist.

3. Computervorrichtung nach Anspruch 1, wobei der Datenbaum in einem Arbeitsspeicher als Antwort auf den anfänglichen Anwenderbefehl zum Abfragen des gewünschten Modells rekursiv konstruiert wird.

4. Verfahren für einen Anwenderdialog mit Modellen finiter Elemente in einem Computersystem, das (i) einen Speicher als Quelle von Modellen von Objekten, wobei jedes Modell aus mehreren Elementen gebildet ist, (ii) einen ersten Speicherbereich, der Daten hält, die jedes Element definieren, (iii) eine Anzeigeeinheit (19) zum Anzeigen von Bildschirmansichten eines Modells und (iv) einen digitalen Prozessor, der den Anwenderdialog mit der Bildschirmansicht des Modells ermöglicht, aufweist, wobei das Verfahren im Speicher auf Daten von Elementen eines gewünschten Elements zugreift und die folgenden Schritte enthält:

Vorsehen eines Datenbaums (33) mit einem Wurzelknoten (39) und mehreren Baumknoten (35) und Blattknoten (37) in einem Arbeitsspeicher, wobei die Blattknoten Elementen eines gewünschten Modells entsprechen und die Baumknoten Mengen der Elemente entsprechen, wobei der Wurzelknoten (39) und die mehreren Baumknoten (35) und Blattknoten (37) hierarchisch in der Weise angeordnet sind, daß sich der Wurzelknoten auf einer höchsten Ebene befindet, die Baumknoten sich auf Zwischenebenen befinden und die Blattknoten sich auf einer untersten Ebene befinden, wobei jeder Blattknoten einen Hinweis auf eine Stelle im ersten Speicherbereich von Daten entsprechender Elemente auf jeder der Zwischenebenen schafft, wobei Knoten auf einer gemeinsamen Ebene gemäß einer räumlichen Beziehung entsprechender Mengen von Elementen des Modells in bezug auf wenigstens eine Achse eines geometrischen Bereichs (81), der von den Elementen in einer Bildschirmansicht des Modells abgedeckt wird, angeordnet sind;

Durchlaufen des Baums entsprechend dem geometrischen Bereich, in dem das gewünschte Element in der angezeigten Bildschirmansicht des Modells angeordnet ist, als Antwort auf einen Anwenderdialog mit einem gewünschten Element eines in der Bildschirmansicht der Anzeigeeinheit angezeigten Modells, indem bestimmt wird, ob irgendwelche Baumknoten (35) oder Blattknoten (37) mit einer Abfrageregion überlappen,

wobei der Schritt des Durchlaufens das Lokalisieren eines Blattknotens in dem dem gewünschten Element entsprechenden Datenbaum umfaßt; und

Erhalten eines Hinweises auf die Stelle im ersten Speicherbereich von Daten des gewünschten Elements aus dem lokalisierten Blattknoten, derart, daß der Zugriff auf die Daten des gewünschten Elements in dem Speicherbereich ermöglicht wird,

wobei das Verfahren dadurch gekennzeichnet ist, daß der Schritt des Vorsehens eines Datenbaums ferner enthält:

Definieren einer rechteckigen Grenze (81) des geometrischen Bereichs, der von den Elementen, die Knoten auf einer gemeinsamen Ebene entsprechen, abgedeckt wird, derart, daß eine longitudinale Hauptachse und eine transversale Nebenachse des geometrischen Bereichs vorhanden sind; und

Anordnen von Baumknoten auf einer gemeinsamen Ebene durch

(i) Anordnen eines ersten Baumknotens, der einer Menge von auf einer Seite der longitudinalen Hauptachse liegenden Elementen entspricht, an einem Ende der gemeinsamen Ebene,

(ii) Anordnen eines zweiten Baumknotens, der Mengen von auf der gegenüberliegenden Seite der longitudinalen Hauptachse liegenden Elementen entspricht, an einem gegenüberliegenden Ende der gemeinsamen Ebene; und

(iii) Anordnen eines dritten Knotens, der Elementen entspricht, die die longitudinale Hauptachse überbrücken, zwischen dem ersten und dem zweiten Baumknoten, und

wobei der Schritt des Vorsehens eines Datenbaums ferner das Definieren von Blattknoten umfaßt, die Elementen des Modells entsprechen, die sowohl die longitudinale Hauptachse als auch die transversale Nebenachse überbrücken.

5. Verfahren nach Anspruch 4, bei dem der Schritt des Vorsehens eines Datenbaums das rekursive Konstruieren des Baums in dem Arbeitsspeicherbereich als Antwort auf einen anfänglichen Anwenderbefehl zum Abfragen des gewünschten Modells umfaßt und bei dem der Schritt des Durchlaufens des Datenbaums und des Lokalisierens eines dem gewünschten Element entsprechenden Blattknotens ferner das rekursive Suchen des Blattknotens umfaßt.