DE69801113T2

DE69801113T2 - Längste-kanten verfeinerungs- und vergröberungssystem und -verfahren zur automatischen maschen-erzeugung

Info

Publication number: DE69801113T2
Application number: DE69801113T
Authority: DE
Inventors: Maria-Cecillia Rivara
Original assignee: RIVARA MARIA CECILLIA
Current assignee: RIVARA MARIA CECILLIA
Priority date: 1997-10-08
Filing date: 1998-10-01
Publication date: 2002-03-14
Anticipated expiration: 2018-10-02
Also published as: DE69801113D1; AU1028899A; EP1021798A2; AU747230B2; US20040117163A1; WO1999018517A2; EP1021798B1; US6266062B1; WO1999018517A3; CA2304492A1

Description

GEBIET DER ERFINDUNG

Diese Erfindung betrifft das computergestützte geometrische Modellieren eines Körpers, wie es bei der Verwendung einer finite Elemente Analyse benötigt wird. Insbesondere betrifft die Erfindung die Erzeugung eines verbesserten und/oder verfeinerten und/oder vergröberten Netzes von finiten Elementen unter Verwendung eines verbesserten und flexiblen Netzerzeugungsverfahrens, eine verbesserte Netzdatenstruktur, und eine Vorrichtung dafür.

HINTERGRUND DER ERFINDUNG

Eine finite Elemente Analyse ist ein leistungsfähiges computerbasiertes Werkzeug zum Lösen von Ingenieur- und physikalischen Problemen, geleitet durch partielle differentielle Gleichungen. Eine finite Elemente Analyse wird bei einer Approximation einer beliebigen kontinuierlichen physikalischen Charakteristik eines Objekts oder eines geometrischen Bereichs verwendet, wie beispielsweise Temperatur, Wärme, Vibration, Fluss von Fluiden, elektrischen Feldern, Druck, etc. Eine finite Elemente Analyse ist besonders wichtig, wenn die Geometrie des zu modellierenden Objektes relativ komplex ist, z. B. kleine Details enthält, da die differentiellen Gleichungen für solche Anwendungen verstärkt schwierig genau zu aproximieren sind.
Ein anfänglicher Schritt einer finite Elemente Analyse umfasst den Aufbau eines Netzes von finiten Elementen, die den geometrischen Bereich abdecken, deren Eckpunkte wiederum Punkte sind, die auf einer Oberfläche und in dem Inneren des Objektes ausgewählt sind. Genaue und moderne finite Elemente Analyse erfordert, dass ein flexibles Netzverbesserungs/Verfeinerungs/Vergröberungsverfahren, alternativ als Punktanordnungs/Eliminationsverfahren beschrieben, verwendet wird, um ein Netz zu erzeugen, das mindestens fünf Kriterien erfüllt: (1) Die gesamte Punkt- oder Eckpunktdichte kann spezifiziert und modifiziert werden; (2) die Dichte von Eckpunkten sollte sich in kritischen Bereichen erhöhen und/oder vermindern (d. h. in solchen, die kleine Merkmale und konkave Ecken aufweisen oder wie es in manchen zeitabhängigen Problemen erforderlich ist); (3) schlecht geformte finite Elemente sollten verhindert werden; (4) ein Netz aus einem Satz von Eckpunkten sollte in bestimmten Bereichen durch den Benutzer oder das finite Elemente Analyse Lösungsverfahren verfeinert und/oder vergröbert werden können; (5) das Netz sollte die Objektbegrenzungen und Schnittstellen respektieren.
Es ist bekannt, dass die Erzeugung eines 3-D-Netzes, geeignet für eine finite Elemente Analyse, bei der Verwendung eines Computers eine der zeitaufwendigsten Schritte ist, um ein komplexes Ingenieursproblem zu analysieren. Das meiste der zurückliegenden Arbeit in Verbindung mit dreidimensionaler Netzverbesserung/Verfeinerung/Vergröberung und/oder Punktanordnung/Elimination hatte heuristische Natur. Für eine genaue Analyse forderten viele Ansätze signifikante Benutzerinteraktionen zwischen dem Benutzer und dem Netzerzeugungssystem.
Mehrere wissenschaftliche Artikel, die Netzerzeugungsverfahren zur Verwendung bei finiter Elementanalyse betrachten, wurden veröffentlicht. Insbesondere betrachten mehrere Veröffentlichungen in dem International Journal for Numerical Methods in Engineering die Erzeugung eines Netzes durch die Delaunay Triangulation. Diese Veröffentlichungen sind die folgenden: Cavendish et al., Vol. 21, S. 329-347, (1985); Frey, Vol. 24, S. 2183- 2200, (1987); Schroeder et al., Vol. 26, S. 2503-2115, (1988); Schroeder et al., Vol. 29, S. 35-55, (1990); Golias et al., Vol. 37, S. 793-812, (1994); Field et al., Vol. 31, S. 413-425, (1991); Wheaterill et al., Vol. 37, S. 2005-2039 (1994).
Andere Veröffentlichungen, die die Delaunay Triangulation berücksichtigen sind die folgenden: Baker, Engineering with Computers, Vol. 5, S. 161-175, (1989); Mitchell et al., IEEE Transactions on Magnetics, Vol. 28, S. 1751-1754 (1992); Ruppert, Journal of Algorithms, Vol. 18, 548-585 (1995); Rebay, J. Comp. Physics, Vol. 106, 125-138 (1993); Joe, Siam J. Sci. Comput. Vol. 16, 1292-1307 (1995).
Jede der vorhergehend genannten Veröffentlichungen verwendet eine Lehre von Delaunay, um eine planare Triangulation und dreidimensionale Tetraederisierung zu erzielen. Ein tetraedales Netz ist als "Delaunay Tetraederisierung" definiert, dann und nur dann, wenn jeder Tetraeder in dem Netz, dessen Bereich durch vier Kanten des Tetraeders definiert ist, sein Umfang genannt, keine Netzkanten in seinem Innenbereich aufweist. Kanten auf der Umfangsbegrenzung sind erlaubt. Die gleiche Eigenschaft trifft auf zweidimensionale Oberflächen zu: eine Oberflächentriangulation wird als Delaunay-Triangulation bezeichnet, dann, und nur dann, wenn für jedes Dreieck in dem Netz, ein durch die drei Eckpunkte definierter Kreis keine anderen Eckpunkte in seinem Inneren aufweist.
Es ist jedoch dem Fachmann wohlbekannt, dass die Fähigkeit des dreidimensionalen Delaunay-Verfahrens, hochqualitative Netze zu erzeugen, stark von dem Punktanordnungsverfahren abhängt. Qualität ist ein sehr wichtiger Faktor, da ein Netz mit schlechter Qualität eine ungenaue numerische Annäherung bewirken kann. Demzufolge sind schlecht geformte Tetraeder zu vermeiden, insbesondere "Scheiben", d. h. Tetraeder, die durch 4 annähernd koplanare Kanten definiert werden und deren längste Kante und kürzeste Kante "vergleichbare Größe" aufweisen. Die meisten der vorhergehend genannten Dokumente diskutieren einige Punktanordnungsstrategien und einige Netzverbesserungs- und/oder Netzverfeinerungswerkzeuge.
Cavendish et al.(1985) implementierte solch eine Triangulation durch Zurückweisen, aus dem Satz von allen möglichen Dreiecken, die gebildet werden können, von solchen, die keine nicht leeren zugeordneten Kreise aufweisen. Die nicht abgewiesenen Dreiecke bilden die Delaunay- Triangulation. Schroeder et al. (1988) wendet solche Lehren auf dreidimensionale Oberflächen an.
Frey (1987) lehrt ein Verfahren zur selektiven Verfeinerung einer anfänglichen Triangulation. Eine Abstufung des Netzes wird durch eine Knotenbeabstandungsfunktion gesteuert, wobei ein möglicher Knoten eingefügt wird und seine Beabstandung von benachbarten Knoten bewerten wird. Jeder neue mögliche Knoten wird auch getestet, um festzustellen, ob seine Einfügung zu einer Delaunay-Triangulation mit einem akzeptablen Beabstandungsgrad an jedem Knoten führen würde. Schroeder et al. (1990) verwendet ein Octree-Verfahren zum Erzeugen eines Satzes von Punkten, die die Geometrie des Objektes repräsentieren.
Golias et al. (1994) beschreibt ein elementbasiertes Verfahren zum Durchführen einer automatischen Netzverfeinerung, die Beinahe-Delaunay-Triangulationen wie folgt erzeugt: der Mittelpunkt der längsten Kante jedes Zielelementes wird ausgewählt und alle Elemente, die diese Kante auch aufweisen, werden partitioniert; das so erhaltene Nicht-Delaunay-Netz wird dann der wiederholten Anwendung eines Satzes von lokalen topologischen Transformationen unterzogen, durchgeführt an allen Elementen des Netzes, gefolgt durch ein insgesamtes Knotenrelaxationsverfahren, bis das Gleichgewicht des Netzes erzielt ist.
Field et al. (1991) verwenden auch lokale Transformationen zum Erzeugen von Beinahe-Delaunay-Netzen, die ein lokales max-min Festwinkelkriterium erfüllen. Weatherill et al. (1994) wählen die dem Netz hinzuzufügenden Punkte zwischen den Schwerpunkten der Elemente des Netzes aus durch Verwendung von unterschiedlichen Punktverteilungsfunktionen, interpoliert zu den Inneneckpunkten. Baker (1989) betrachtet die Hinzufügung eines neuen Eckpunkts nahe jeder Scheibe, gefolgt durch einen Retriangulierungsschritt. Mitchell et al. (1992) verwendet eine Elementgrößenfunktion im gesamten Netz und eine lokale Neuausrichtung der Knoten zum Verbessern des Netzes. Joe (1995) verwendet weiter lokale topologische Transformationen zum Erzeugen von verbesserten Beinahe- Delaunay-Netzen.
Ruppert (1995) lehrt ein Punkteinfügungsverfahren, das den Aufbau von 2-D-Delaunaytriangulationen mit guter Qualität garantiert, durch Hinzufügen von Punkten im Umfangsbereich der schlechtesten kleinwinkligen Dreiecke des momentanen Netzes. Rebay (1993) lehrt ein alternatives Punkteinfügungsverfahren basierend auf einem Auswählen eines maximalen nicht akzeptierten Dreiecks, was auch benachbart zu einem akzeptierten Dreieck liegt; dann Auswählen eines Punktes, der über dem Segment angeordnet ist, der den Umfangskreis der zwei Dreiecke verbindet.
In der wissenschaftlichen Literatur wurde auch Verfahren beträchtliche Aufmerksamkeit gezollt, die die Verfeinerung eines allgemeinen Nicht-Delaunay-Netzes betrachten, durch ein Durchführen von selektiven Längste-Kante-Unterteilungen eines Satzes von geeigneten Elementen des Netzes. In zwei Dimensionen wird eine Längste-Kante-Bisektion erhalten durch ein Unterteilen des Elementes durch die Linie, definiert durch den Mittelpunkt der längsten Kante und den gegenüberliegenden Eckpunkt. In drei Dimensionen wird eine Längste-Kante-Bisektion (Teilung) wiederum erhalten durch ein Partitionieren des Elementes durch die Ebene, definiert durch den Mittelpunkt der längsten Kante und die zwei gegenüberliegenden Eckpunkte. Es wurde gezeigt, dass die Längste-Kante-Verfeinerungsverfahren die Punkteverteilung verbessern, durch Aufrechterhalten einiger kleinwinkliger Dreiecke, die von der Qualität des anfänglichen Netzes abhängen. Die folgenden Dokumente betrachten die Anwendung dieser Ideen und die Erzeugung eines Netzes dafür:
Rivara, International Journal for Numerical Methods in Engineering, Vol. 20, S. 745-756 (1984a); Rivara, ACM Trans, on Mathematical Software, Vol. 10, S. 242-264 (1984b) Rivara, In Accuracy Estimates and Adaptive Refinements in Finite Element Computations; John Wiley and Sons, Chichester, S. 359-370 (1986); Rivara, International Journal for Numerical Methods in Engineering, Vol. 24, S. 1343-1354 (1987); Rivara, International Journal for Numerical Methods in Engineering, Vol. 28, S. 2889-2906 (1989); Rivara et al. Communications on Applied Numerical Methods, Vol. 8, S. 281-290 (1992); Liu et al., SIAM J. Sci. Computing, Vol. 16, S. 1269-1291 (1995); Liu et al., Mathematics of Computation, Vol. 65, S. 1183-1200 (1996); Muthukrishnan, et al. AIAA Journal, Vol. 33, S. 928-932, (1995); Jones et al., Computing Systems in Engineering, Vol. 5, S. 297-309, 1994.
Rivara (1984a) lehrt zwei Arten von Längste-Kante- Bisektionsverfeinerungsverfahren in zwei Dimensionen, die einige Nachbarverfeinerungs- und einige zwischengelagerte ungültige Netze erzeugen, und legt deren mathematische Eigenschaften dar; Rivara (1984b und 1986) diskutiert die Anwendung dieser Lehren in adaptiver Multigitterfinitelementanalyse; Rivara (1987) lehrt die Implementierung eines 4-Dreiecke-Verfahrens, ebenso basierend auf den Eigenschaften von Längste-Kante-Bisektionen, das auch einige zwischengelagerte ungültige Netze erzeugt; Rivara (1989) generalisiert diese Lehren auf die Vergröberung von geschachtelten Triangulationen basierend auf einer Zuordnung, für jeden neuen Eckpunkt, der Erzeugungsebene, und rekursive Verwendung dieses "Etiketts" zur Identifizierung eines Satzes von Eckpunkten, Kanten und Dreiecken, die zu eliminieren sind. Das Vergröberungsverfahren erzeugt einige zwischengelagerte nicht gültige Netze.
Rivara et al. (1992) lehrt und diskutiert ein dreidimensionales Längste-Kante-Verfeinerungsverfahren basierend auf einer Durchführung einer rekursiven Bisektion der Zielelemente und einiger derer größter Nachbarn. Liu et al. (1995 und 1996) betrachtet zwei Arten von dreidimensionalen Verfahren basierend auf einer Bisektion.
Rivara (1984b) und Rivara et al. (1992) lehren Netzdatenstrukturen basierend auf einer Zuordnung an einen jeweiligen Eckpunkt des Satzes von geordneten Nachbareckpunkten, und des Satzes der Dreiecknachbaroberflächen. Muthukrishnan et al. (1995) lehren eine Abwandlung des Längste-Kante-Verfahrens von Rivara et al. (1992) basierend auf einer Durchführung einer Sortierung der Liste von zu verfeinernden Elementen in aufsteigender Reihenfolge nach ihren längsten Kanten; Zuordnen eines Verfeinerungsverhältnisses zu diesen Elementen und Verteilen auf deren Abkömmlinge; Einfügen der benachbarten Elemente eines jeden ausgewählten Elementes in die Liste an einer Position basierend auf der längsten Kante; und Verwendung der Reihenfolge, um den Elementunterteilungsvorgang durchzuführen.
Jones et al. (1994) lehrt ein paralleles skalierbares Bisektionsverfahren für die Verfeinerung von zweidimensionalen Triangulationen basierend auf dem 4- Dreiecke-Verfahren von Rivara (1984a) unter der Annahme, dass die Prozessoren durch einen gemeinsam genutzten Speicher kommunizieren. Jedes zu verfeinernde Zieldreieck wird einem Prozessor zugeordnet, der die Nachbarverfeinerung in dem Netz nachverfolgt, was zwischengelagerte ungültige Netze erzeugt. Um Synchronisationsprobleme zu vermeiden (da zwei unterschiedliche Prozessoren Eckpunkte an dem gleichen Ort erzeugen könnten, wenn ein Dreieck bisektioniert wird) bestimmt das parallele Verfahren Sequenzen von unabhängigen Sätzen von Dreiecken und verfeinert die Dreiecke in diesen Sätzen parallel.
Die folgenden neueren Veröffentlichungen betrachten die Kombination von Längste-Kante-Punkteinfügungsverfahren und Delaunay Triangulationen: Rivara et al., International Journal for Numerical Methods in Engineering, Vol. 40, 581- 597 (1997a); Rivara, Proceedings 5th International Meshing Roundtable, Pittsburgh, October 10-11 1996, S. 77-86 (1996); Rivara, International Journal for Numerical Methods in Engineering, Vol. 40, 3313-3324 (1997); Rivara et al., AMD- Vol. 220, The American Society of Mechanical Engineers, S. 1- 8 (1997b).
Rivara et al. (1997a) betrachtet eine Delaunay Triangulation in zwei Dimensionen und lehrt ein Verfahren, das für jedes Zielelement die Delaunay-Einfügung eines Clusters (Ansammlung) von Punkten durchführt, definiert durch das Längste-Kante-Bisektionsverfahren, gelehrt durch Rivara (1984a). Dieses Verfahren verbessert die Punktverteilung und erhält einige kleinwinklige Dreiecke, die von der anfänglichen Triangulation abhängen.
Rivara (1996 und 1997) lehrt ein neues Längste-Kante- Punkteinfügungsverfahren für zweidimensionale Delaunay-Netze, das immer die Triangulation verbessert. Für jedes Dreieck wird der einzufügende Punkt gefunden durch ein Nachverfolgen der Sequenz von benachbarten sich vergrößernden Dreiecken, bis die letzten zwei größten Dreiecke in der Sequenz sich eine gemeinsame längste Kante teilen, genannt eine Endkante. Dann wird der Mittelpunkt dieser längsten Kante gemäss Delaunay in das Netz eingefügt. Rivara (1997) beweist, dass das systematische Verwenden dieses Verfahrens bei den kleinwinkligen Dreiecken des Netzes Triangulationen mit guter Qualität mit kleinstem Winkel größer als oder gleich 30º erzeugt. Rivara (1996 und 1997) führt auch eine Generalisierung dieses Verfahrens für 3-Dimensionen aus, unter Bereitstellung eines groben 3-dimensionalen rekursiven Verfahrens, das für jedes Zielelement einem 3-dimensionalen Fortschrittspfad folgt, assoziiert mit dem Längste-Kante- Bisektionsverfahren, und die Delaunay-Einfügung eines Clusters von Punkten an Endkanten, dem 3-dimensionalen Fortschrittspfad zugeordnet, durchführt. Rivara et al. (1997b) berichtet numerische Experimentation mit sowohl en 2- D- und 3-D-Verfahren.
Rivara (1996 und 1997) lehrt auch rekursive 2-dimensionale und 3-dimensionale Längste-Kante-Verfeinerungsverfahren für Nicht-Delaunay-Qualitätsnetze, die die gleichen Netze erzeugen wie die Verfahren von Rivara (1984a) und Rivara et al. (1992), wobei lediglich Sätze von Elementen, die Endkanten des Netzes gemeinsam nutzen (alle Elemente jedes Satzes teilen sich die gemeinsamen Endkanten) partitioniert werden.
Weder Rivara (1996) noch Rivara (1997) noch Rivara et al. (1997b) offenbaren jedoch irgendein nicht rekursives Längste- Kante-Suchverfahren zum Auffinden von zielelementbezogenen Sätzen von Endkanten, noch nutzen sie den Vorteil deren Eigenschaften, um die Verwendung von parallelen Suchverfahren zum Auffinden von Sätzen von Endkanten zu offenbaren, noch offenbaren sie parallele Verfeinerungsverfahren für terminale Elementsätze in Bezug zu zugeordneten Endkanten, noch offenbaren sie Datenstrukturen für die Handhabung des Endkanten-Ansatzes. Sie offenbaren keine Begrenzungspunkteinfügungsschritte für Begrenzungszielelemente und für Begrenzungs- (oder Beinahe- Begrenzungs-) Endkanten, wie es erforderlich ist, um eine Qualitätsverteilung von Punkten in der Umgebung der Objektbegrenzung für ein Netzverbesserungsverfahren zu garantieren. Sie offenbaren kein Endkanten-basiertes Verfahren für Netzvergröberung, noch ein integriertes Netzerzeugungssystem, das die Kombination der Endkanten basierten Netzverfeinerung, Netzvergröberung und Netzverbesserungsverfahren, die hierin beschrieben sind, vollständig ausnutzt.
Muthukrishnan S N et al.: Refinement of 3D Meshes at Surface Intersections', COMPUTER AIDED DESIGN, Vol. 27, Nr. 8, 1 August 1995, S. 637-645 (Muthukrishnan, 1995b) adressiert ein anderes Problem, das durch die Offenbarung des Anmelders adressiert ist. Dieses Dokument verwendet ein Längste-Kante- Verfeinerungsverfahren, das vorhergehend durch Muthukrishnan et al. (1995) offenbart wurde, das eine Abwandlung des Längste-Kante-Verfahrens von Rivara (1992) darstellt und nicht auf einer Terminalen-Kanten-Methodologie basiert, wie oben diskutiert.
Insbesondere offenbart Muthukrishnan (1995b) ein Verfahren für die Verfeinerung von Netzen im Zusammenhang mit geometrischen Objekten, die durch kurvige Oberflächen begrenzt sind, und in diesem Sinn, "die neu hinzugefügten Punkte sollten auf die wahren Begrenzungen des Objekts angeordnet werden, zum Aufrechterhalten der Integrität der Geometrie des Objekts" auf S. 637, linke Spalte.
Insoweit die Objektbegrenzung betroffen ist, befasst sich die vorliegende Offenbarung nicht mit der "Kurvenoberflächenfrage", sondern mit der Erzeugung eines verbesserten Netzes des Objektes, mit sowohl einer inneren als auch auf der Begrenzung liegenden verbesserten Punktverteilung, und mit der Sicherstellung von verbesserten geometrischen Qualitätselementen.
Insbesondere lehrt Muthukrishnan (1995b) "curved surface point insertion" (Kurvenoberflächenpunkteinfügung) keine, und legt dies auch nicht nahe, Begrenzungspunkteinfügung in Beziehung mit Begrenzungszielelementen, oder und eine Begrenzungspunkteinfügung mit Bezug auf Begrenzungs- oder zu nahe zur Begrenzung liegenden Begrenzungs-Endkanten. Beide diese Punkteinfügungsschritte verhindern die Erzeugung von Objektinnenpunkten, die unnötig nahe an der Objektbegrenzung liegen, und stellen die Erzeugung einer globalen und räumlichen Qualitätspunktverteilung für das gesamte räumliche Objekt bereit.
Kurz gesagt, in Muthukrishnan (1995b) wird die Verwendung einer Endkantenmethodologie und deren Eigenschaften zum Erzeugen einer Netzverbesserung, Netzverfeinerung und Netzvergröberung und einer Erzeugung reines integrierten allgemeinen und automatischen Begrenzungskantennetzerzeugungssystems, das die Kombination dieser Methoden voll ausnutzt, nicht gelehrt oder nahegelegt.
Im US-Patent Nr. 4,912,664 an Weiss et al., ist ein 2-D- Ansatz zum Erzeugen eines Netzes unter Verwendung einer Delamay-Triangulation beschrieben. Welss et al. verwenden ein Expertensystem-basiertes Punktplatzierungsverfahren und ein Elementqualitätskriterium für eine Punktauswahl. Im US-Patent Nr. 4,933,889 an Meshkat et al. ist ein weiterer 2-D-Ansatz zur Erzeugung eines Netzes unter Verwendung einer symmetrischen Achsendekomposition beschrieben. Das dort beschriebene Verfahren ist nicht punktbasiert, verwendet jedoch die symmetrische Achse eines Körpers, um die Berechnung eines finiten Elements zu ermöglichen. Im US- Patent Nr. 5,214,752 an Meshkat et al. wird ein automatisches 3-D-Punktplatzierungsverfahren zur Erzeugung eines Netzes unter Verwendung einer Delaunay-Triangulation beschrieben. Das Verfahren berücksichtigt einen Untersatz von Eckpunkten und wählt für jeden Eckpunkt den Punkt aus, der zwischen Schnittpunkten einer Kugel mit einem Radius R, zentriert an dem betrachteten Eckpunkt, und Begrenzungen und Kanten einzufügen ist. Zusätzlich wird für eine Eliminierung von Scheibenelementen aus dem Netz das Zentrum der Umfangskugel entsprechend eines solchen Elements in das Netz eingefügt.
Im US-Patent Nr. 5,315,537 an Blacker wird ein automatisiertes quadrilaterales Oberflächendiskretisierungsverfahren und -vorrichtung beschrieben, das ein Netz mit vollständig quadrilateralen Elementen erzeugt. Im US-Patent Nr. 5,440,674 an Park wird ein 2-dimensionales Verfahren zum Erzeugen von gleichmäßigen und abgestuften Triangulationen unter Verwendung von 4 Lokaloperatoren beschrieben.
Weitere Patente, die Verfahren bezüglich einer Netzerzeugung beschreiben, sind die folgenden: Nackman, US-Pat. Nr. 4,797,842; Finnigan et al., US-Pat. Nr. 5,345,490; Meshkat et al., US-Pat. 4,933,889; Shigyo et al., US-Pat. Nr. 4,941,114; Arakawa, US-Pat. Nr. 5,010,501; Arakawa, US-Pat. Nr. 5,398,307; Glassner, US-Pat. Nr. 5,428,717; Holmes, US-Pat. Nr. 5,497,451; Mesbkat, US-Pat. Nr. 5,553,206; Akiyama, US- Pat. Nr. 5,774,696; Yamashita et al., US-Pat: Nr. 5,760,779; Yamamoto et al., US-Pat. Nr. 5,748,865; Strumulo et al., US- Pat. Nr. 5,729,670; Kumashiro, US-Pat. Nr. 5,677,846; Yokota, US-Pat. Nr. 5,617,332. Eine Netzerzeugung kann auch verwendet werden, um das Rendern von dreidimensionalen Darstellungen verschiedener Körper zu ermöglichen, wie beispielsweise in Falk, US-Pat. Nr. 4,888,713 beschrieben.
Trotz des obigen ist immer noch Raum für eine Verbesserung vorhanden zur Verbesserung einer Netzqualität, Verfeinerung/Vergröberung eines Qualitätsnetzes, ein automatisches Steuern einer Netzabstufung und Verfeinerung/Vergröberung, einer automatischen Steuerung einer Punktdichte durch Punkteinfügung/Elimination, zum Eliminieren von unerwünschten Scheibchen ohne Verwendung von speziellen Verfahren, und Verhindern, dass schlecht geformte Netzelemente in dem sich ergebenden Netz auftreten. Es wäre wünschenswert, ein Suchen von einzufügenden und/oder zu eliminierenden ausgewählten Punkten zu erlauben, unter Betrachtung nur der Verteilung von sich erhöhenden Nachbarelementen, und nicht der Delaunay-Eigenschaft des Netzes. Es wäre wünschenswert, die Verfeinerung/Vergröberung des Netzes zu erlauben, unter Vermeidung der Verwendung von zwischengelagerten, nicht gültigen Netzen. Es wäre wünschenswert, die Verfeinerung/Vergröberung/Verbesserung des Netzes unter Verwendung nicht-rekursiver Verfahren zu erlauben. Es wäre wünschenswert, eine einfache integrierte Verbesserung/Verfeinerung/Vergröberung des Netzes zu erlauben, unter voller Ausnutzung der Eigenschaften der geometrischen Endkantenabstraktion. Es wäre wünschenswert, eine einfache parallele skalierbare Verfeinerung/Vergröberung des Netzes zu erlauben, mittels lokaler Modifizierung nur von Sätzen von Nachbarelementen, die eine gemeinsame Kante (Längste-Kante) teilen, was keine Interprozessorkommunikation erfordert. Es wäre wünschenswert, eine einfache Handhabung von Delaunay- und Nicht-Delaunay-Netzen zu erlauben. Und es wäre wünschenswert, das verbesserte Netzdatenstrukturen integrierte Netzverbesserungs/Verfeinerungs/Vergröberungsverfahren zu implementieren.
Es ist daher wünschenswert, ein verbessertes Punktplatzierungs/Eliminierungsverfahren und eine Vorrichtung dafür bereitzustellen, für eine Verwendung in einem dreidimensionalen automatischen Netzerzeugungssystem.
Es ist weiter wünschenswert, ein automatisiertes Netzverbesserungsverfahren bereitzustellen, alternativ als ein verbessertes Punktplatzierungsverfahren beschrieben, und eine Vorrichtung dafür, wobei eine Qualitätsnetzverbesserung automatisch gesteuert wird.
Es ist weiter wünschenswert, ein automatisiertes Netzverfeinerungs/Vergröberungsverfahren bereitzustellen, alternativ auch als ein automatisiertes Punktplatzierungs/Eliminierungsverfahren beschrieben, und eine Vorrichtung dafür, wobei eine Netzabstufung und Netzverfeinerung/Vergröberung automatisch gesteuert wird.
Es ist weiter wünschenswert, ein Punktplatzierungs/Eliminierungsverfahren bereitzustellen, und eine Vorrichtung dafür, wobei eine Punktdichte automatisch gesteuert wird.
Es ist weiter wünschenswert, ein verbessertes Punktplatzierungs/Eliminierungsverfahren bereitzustellen, und eine Vorrichtung dafür, was ein Auftreten von schlecht geformten Netzelementen im resultierenden Netz verhindert.
Es ist weiter wünschenswert, ein verbessertes nichtrekursives Netzverfeinerungs/Vergröberungsverfahren bereitzustellen, das keine Verwendung von zwischengelagerten nicht gültigen Netzen erfordert.
Es ist weiter wünschenswert, ein verbessertes skalierbares Verfahren und eine Vorrichtung dafür bereitzustellen, für die parallele Verfeinerung/Vergröberung des Netzes, durch Durchführen lokaler Arbeitsschritte, zentriert auf Modifizierungssätze von Nachbarelementen, die eine gemeinsame Längste-Kante teilen, was keine Interprozessorkommunikation erfordert.
Es ist weiter wünschenswert, eine verbesserte Netzdatenstruktur bereitzustellen, für die integrierte Implementierung des Verbesserungs/Verfeinerungs/Vergröberungsverfahrens dieser Erfindung, und eine entsprechende Vorrichtung.
Es ist weiter wünschenswert, ein Verfahren und eine Vorrichtung bereitzustellen, die eine schnellere Verarbeitungszeit für die integrierte Verfeinerung und/oder Vergröberung und/oder Verbesserung von geometrischen Netzen erzielt.

ZUSAMMENFASSUNG DER ERFINDUNG

Es ist ein Verfahren, eine Netzdatenstruktur und eine Vorrichtung offenbart, zum Erzeugen eines verbesserten/verfeinerten/vergröberten Netzes aus finiten Elementen für ein dreidimensionales Objekt, das Begrenzungen und Oberflächen aufweist. Das Verbesserungs/Verfeinerungsverfahren sucht wiederholt für aufeinanderfolgende Sätze von zu verfeinernden oder verbessernden Aktivzielelementen ein zugeordnetes Unternetz und einen Satz von Endkanten, wobei der Suchprozess die Netzdatenstruktur nicht modifiziert; dann wird in Übereinstimmung mit dem gewählten Punkteinfügungsverfahren der Punkt oder die Punkte ausgewählt, die zwischen den Mittelpunkten der Endkanten einzufügen sind, modifiziert mit einigen Randbedingungen; Einfügen des gewählten Punktes oder der Punkte in das anfängliche Netz; und dann Fortschreiten zu dem nachfolgenden Satz von aktiven Zielelementen, bis ein benutzerdefiniertes Haltekriterium erreicht ist.
Das Vergröberungsverfahren enthält für jeden Zieleckpunkt ein Auffinden eines zugeordneten Satzes von Nachbareckpunkten, die zu vergröbern sind; Eliminieren des Eckpunktes in Übereinstimmung mit einer geeigneten Reihenfolge, so dass die Vergröberung des Eckpunktes es erlaubt, eine vorhergehende Begrenzungskante, deren Unterteilung den Eckpunkt erzeugte, erneut zu erhalten. Das Verfahren, die Netzdatenstruktur und Vorrichtung dieser Erfindung erlauben die parallele skalierbare Verfeinerung/Vergröberung des Netzes durch lokales Modifizieren von Sätzen von Nachbarelementen, die die gemeinsame Längste-Kante teilen.

KURZE BESCHREIBUNG DER ZEICHNUNG

Die Merkmale der Erfindung, von denen angenommen wird, dass sie neuartig sind, sind in den angefügten Ansprüchen ausgeführt. Die Erfindung kann jedoch am besten zusammen mit weiteren Aufgaben und Vorteilen mit Bezug auf die folgende Beschreibung in Zusammenschau mit den begleitenden Zeichnungen verstanden werden:
Fig. 1 zeigt eine perspektivische Ansicht eines dreidimensionalen Objektes, nachdem es einer Neu- Tetraedrisierung unterzogen wurde.
Fig. 2 zeigt eine perspektivische Ansicht eines Tetraeders, der in Fig. 1 aufgefunden wurde, und der die Längste-Kante AB aufweist.
Fig. 3 zeigt eine perspektivische Ansicht von zwei Nachbartetraedern, die die gemeinsame Kante AB teilen (Fall 1 von 2).
Fig. 4 zeigt eine perspektivische Ansicht von zwei Nachbartetraedern, die die gemeinsame Kante AB teilen (Fall 2 von 2).
Fig. 5 zeigt eine perspektivische Ansicht des Längste- Kante Unternetzes in Verbindung mit dem Tetraeder ABCD, die Endkanten EB und BF aufweisend.
Fig. 6 veranschaulicht die Systemarchitektur der Vorrichtung dieser Erfindung.
Fig. 7 zeigt ein allgemeines (auf hoher Ebene) Flussdiagramm, das das Verbesserungs/Verfeinerungsverfahren dieser Erfindung beschreibt, wie es durch eine Hauptverarbeitungseinheit der in Fig. 6 veranschaulichten Vorrichtung ausgeführt wird.
Fig. 8 zeigt ein allgemeines Flussdiagramm, das das Verbesserungs/Verfeinerungsverfahren dieser Erfindung beschreibt, ausgeführt durch Netzspeicher und Längste-Kante Parallelcomputereinheiten der in Fig. 6 veranschaulichten Vorrichtung.
Fig. 9 zeigt ein Flussdiagramm, das einen Betriebsvorgang von Fig. 7 weiter veranschaulicht, nämlich die Auswahl von Punkten in Übereinstimmung mit einem gewählten Punkteinfügungskriterium.
Fig. 10 zeigt ein Flussdiagramm, das einen Betriebsvorgang von Fig. 7 weiter veranschaulicht, nämlich die Netzneuberechnung.
Fig. 11 zeigt ein Flussdiagramm, das einen Betriebsvorgang von Fig. 7 weiter veranschaulicht, nämlich die Vorverarbeitung von Begrenzungs-Aktivelementen.
Fig. 12 zeigt ein Flussdiagramm, das einen Betriebsvorgang von Fig. 9 weiter veranschaulicht, nämlich die Auswahl eines Punktes für eine Delaunay-Einfügung.
Fig. 13 zeigt eine perspektivische Ansicht der Längste- Kante Unterteilung eines Tetraeders mit Eckpunkten ABCD und einer Längste-Kante AB, wobei M Mittelpunkt von AB ist.
Fig. 14 veranschaulicht ein verfeinertes Längste-Kante zweidimensionales (Nicht-Delaunay) Netz, seine Eckpunkte, und in Klammern zugeordnete VE-IND Indikatorwerte.
Fig. 15 veranschaulicht das sich ergebende Netz (nach Durchführung der Vergröberung des Eckpunkts J von dem Netz von Fig. 13), dessen Eckpunkte, und in Klammern die zugeordneten VE-IND Indikatorwerte.
Fig. 16 zeigt eine Tabelle der entsprechenden zugeordneten VE-IND Werte und Generatorkanten für jeden der Eckpunkte des verfeinerten Netzes von Fig. 14.
Fig. 17 veranschaulicht die Längste-Kante Netzdatenstruktur, und beschreibt schematisch die EDGE, ELEMENT, VERTEX und GEN-EDGE Darstellungen.
Fig. 18 zeigt ein allgemeines Flussdiagramm, das die Initialisierung der Längste-Kante Netzdatenstruktur nach der Eingabe des anfänglichen Netzes beschreibt.
Fig. 19 veranschaulicht in einem Flussdiagramm weiter einen Betriebsvorgang von Fig. 20, nämlich die Modifikation der Längste-Kante Netzdatenstruktur nach einer Verfeinerung einer Endkante.
Fig. 20 veranschaulicht die Systemarchitektur einer zusätzlichen Vorrichtung, die die parallele Verfeinerung des Satzes von Endkanten als eine Alternative zu dem Block 570 in Fig. 10 durchführen kann.
Fig. 21 zeigt ein allgemeines Flussdiagramm, das das Vergröberungsverfahren dieser Erfindung beschreibt.
Fig. 22 veranschaulicht in einem Flussdiagramm weiter einen Betriebsvorgang von Fig. 21, nämlich den Aufbau des Eckpunktsatzes, der die Eckpunkte enthält, die von dem Netz zu vergröbern sind.
Fig. 23 veranschaulicht die Systemarchitektur einer zusätzlichen Vorrichtung, die die parallele Vergröberung eines Satzes von ausgewählten Eckpunkten durchführen kann.
Fig. 24 veranschaulicht in einem Flussdiagramm weiter einen Betriebsvorgang von Fig. 23, nämlich die lokale Modifikation der Netzdatenstruktur nach der Vergröberung des individuellen Eckpunkts.
Fig. 25 veranschaulicht in einem allgemeinen Flussdiagramm ein bevorzugtes Ausführungsbeispiel eines integrierten Netzerzeugungsverfahrens.
Fig. 26 veranschaulicht in einem Flussdiagramm weiter einen Betriebsvorgang von Fig. 25, nämlich die lokale Aktualisierung der Netzdatenstruktur aufgrund der Modifikation der Eckpunktkoordinaten.

DETAILLIERTE BESCHREIBUNG DER ERFINDUNG

Diese Erfindung umfasst ein Verbesserungs- /Verfeinerungsverfahren, ein Vergröberungsverfahren, eine Netzdatenstruktur, ein integriertes, automatisiertes Netzerzeugungsverfahren, und eine Vorrichtung dafür.
Auch wenn jeder Bestandteil dieser Erfindung alle Vorteile der Endkantenabstraktion eines Netzes von Elementen und deren geometrischer Eigenschaften nutzt, und auch wenn alle diese Bestandteile geeignet zusammengefügt werden können, um ein flexibles und automatisches Netzerzeugungssystem zu erzeugen, können der Verbesserungsbestandteil, der Verfeinerungs-/ Vergröberungsbestandteil alleine bestehen, unabhängig voneinander in dem Sinne, dass diese Bestandteile getrennt in unterschiedlichen Anwendungen verwendet werden können. Das Vergröberungsverfahren kann jedoch nur verwendet werden, um Netze zu vergröbern, die während der vorherigen Verwendung des Längste-Kante Verfeinerungsverfahrens erzeugt wurden, und umfasst und generalisiert in diesem Sinne das Verfeinerungsverfahren.
Fig. 1 bis Fig. 5 beziehen sich auf einige geometrische Gesichtspunkte des Verfahrens und der Vorrichtung der vorliegenden Erfindung.
Unter Bezugnahme auf Fig. 1 wurde ein einfaches dreidimensionales Objekt mit Eckpunkten A, B, C, D, E, F und G einer Tetraedrisierung unterzogen. Fig. 2 zeigt einen der Tetraeder, die in Fig. 1 enthalten sind, mit Eckpunkten A, B, C, D; Kanten AB, AC, AD, BD, BC und DC, und Dreieckoberflächen ACB, ADC, ADB und DBC. Die in "Längste- Kante" des Tetraeders ABCD ist die Kante AB; d. h., die Kante deren Länge größer als die Länge jeder anderen der verbleibenden fünf Kanten AC, AD, BD, BC und DC ist. Das Verfahren der vorliegenden Erfindung betrachtet entweder eine Delaunay oder Nicht-Delaunay Tetraedrisierung.
Fig. 3 und Fig. 4 veranschaulichen Beispiele der einzigen zwei eindeutig möglichen Fälle eines gültigen Nachbartetraeders mit der gemeinsam genutzten Längste-Kante AB. In Fig. 3 nutzen zwei Tetraeder mit Eckpunkten A, B, C, D und Eckpunkten B, C, A, E, die gemeinsame Dreiecksoberfläche ABC, und insbesondere die Kante AB. In Fig. 4 teilen sich die Nachbartetraeder von jeweiligen Eckpunkten A, B, C, D und Eckpunkten A, B, E, F nur die gemeinsame Kante AB. In dem allgemeineren Fall, in dem die Kante AB eine innere Kante ist, existiert immer ein Satz von durchgehenden Nachbarelementen, die den Raum um die Kante AB füllen.
Die Ableitung einer anfänglichen Tetraedisierung erfordert, dass durch den Benutzer Koordinatenwerte für jeden der Eckpunkte des Körpers und seine Begrenzungen eingegeben werden. Wie es aus Fig. 7 (Block 200) ersichtlich ist, werden diese Werte ebenso durch diese Erfindung verwendet. Somit umfassen die Eingaben für diese Erfindung: die Eckpunkte eines Modells des zu analysierenden Körpers, die Begrenzungen des Modells und eine anfängliche Tetraedrisierung (Netz) des Objektmodells.
Das Verfeinerungs-/Verbesserungsverfahren dieser Erfindung basiert auf einem wiederholten Auffinden unter den Tetraeder des Netzes, des Satzes von Nachbartetraedern, die eine ausgewählte Kante gemeinsam verwenden, wobei diese ausgewählte Kante die längste Kante unter den sechs Kanten individueller Tetraeder ist, wie vorher in Verbindung mit dem Beispiel von Fig. 1 betrachtet. Beginnend mit einem aktiven Zielelement und dessen entsprechender längster Kante, erlaubt die wiederholte Verwendung dieses Ansatzes die Identifikation eines "Längste-Kante" Unternetzes, dass in einem gewissen Sinne die lokale Punktverteilung in Zusammenhang mit diesem Zielelement misst. Unter den Mittelpunkten eines Satzes von "Endkanten", auf der "Oberfläche" eines solchen Unternetzes gelegen, wird der Punkt oder die Punkte ausgewählt, die in das Netz einzufügen sind.
Die Endkanten eines Netzes, wobei jede der Endkanten der gemeinsamen längsten Kante aller Elemente, die die Endkante teilen, entspricht, sind Schlüsselkomponenten des verbesserten Verfahrens und der Vorrichtung der vorliegenden Erfindung, was die Vorteile der folgenden Eigenschaften nutzt: (1) Endkanten von Delaunay-Netzen identifizieren die besten Orte (Kanten), so dass die Einfügung des Mittelpunktes einer jeden dieser Endkanten die Punktverteilung und die Qualität von Nachbarelementen verbessert; (2) das verbesserte Verfahren und die Vorrichtung der vorliegenden Erfindung verwenden wiederholt die Identifikation von Sätzen von Endkanten des Netzes, wobei dieser Arbeitsschritt durchgeführt wird, ohne das Netz zu modifizieren; (3) das verbesserte (Längste-Kante) Verfeinerungs- /Vergröberungsverfahren der vorliegenden Erfindung reduziert sich letztendlich auf die lokale Verfeinerung und/oder Vergröberung von individuellen Endkanten des Netzes, wobei lokale Arbeitsschritte nur den Satz von Elementen umfassen, die jede dieser Begrenzungskanten gemeinsam nutzen; (4) die vorhergehenden zwei Eigenschaften werden durch das verbesserte (skalierbare) Verfahren dieser Erfindung und die Vorrichtung dafür verwendet, sowohl für ein effizientes Durchführen einer parallelen Suche des Satzes von einbezogenen Endkanten, als auch für die parallele lokale Verfeinerung und/oder Vergröberung von Endkanten, was keine Interprozessorkommunikation erfordert; (5) die Eigenschaften (2) und (3) werden verwendet, um eine effiziente (gemeinsam genutzte bzw. geteilte) Netzdatenstruktur auszulegen, die lokal aktualisiert wird, wenn eine parallele Verfeinerung/Vergröberung des Netzes durchgeführt wird.
Das Verbesserungs-/Verfeinerungsverfahren dieser Erfindung verwendet zwei alternative Punkteinfügungskriterien in Übereinstimmung mit einem nutzerdefiniertem Parameter: (1) Delaunaypunkteinfügung oder (2) Endkantenverfeinerung. Das Dlaunauykriterium ist am besten geeignet für ein Verbessern eines Netzes mit schlecht geformten Elementen. Das Endkantenverfeinerungsverfahren ist am besten geeignet für ein Verfeinern eines Netzes mit Qualitätselementen, wie dies benötigt wird bei adaptiven und/oder Multigitter-Finite- Elemente-Analyse-Anwendungen (für eine Diskussion siehe Rivara (1986)).
Wenn das Delaunaykriterium für eine Punkteinfügung (über Entscheidungsblock 500, Fig. 9) ausgewählt ist, und wann immer einige "innere" Bedingungen erfüllt sind (siehe Fig. 12, Blöcke 730, 750), wird der Mittelpunkt der längsten Endkante als ein Punkt ausgewählt, der in das Netz einzufügen ist (Block 240 in Figur, zu Block 510 in Fig. 9 führend, und dann zu Block 770 in Fig. 12). Wenn eine Endkantenverfeinerung gewählt wird (wieder über den Entscheidungsblock 500 in Fig. 9,) werden die Mittelpunkte solcher Endkanten ausgewählt, um in das Netz eingefügt zu werden (Block 520 in Fig. 9).
Fig. 5 veranschaulicht ein einfaches Netz, bei dem ein Tetraeder mit Eckpunkten A, B, C, D und einer längsten Kante AB zwei Nachbartetraeder mit jeweiligen Eckpunkten A, D, B, F und A, B, C, E aufweist, die die gemeinsame Kante AB teilen. Diese Tetraeder haben jeweilige längste Kanten BF und ED wobei die Länge von BF größer ist als die Länge von EB. Die drei Tetraeder definieren das Längste-Kante-Unternetz in Zusammenhang mit dem Tetraeder ABCD mit Endkanten BF und EB. Da die Kante BF die größte Endkante ist, ist der vorhersehbare Punkt für eine Delaunayeinfügung der Mittelpunkt von BF, als MPT markiert. Wenn eine Endkantenverfeinerung gewählt ist, werden die Mittelpunkte von beiden Kanten BP und EB ausgewählt, um in das Netz eingefügt zu werden.
Anfänglich wird ein Satz von Zielelementen in dem Netz definiert (Block 210 in Fig. 7). Eine geeignete Zuordnung und Handhabung des Satzes von Zielelementen macht entweder eine adaptive Netzverfeinerung möglich, oder eine automatische Netzverbesserung. Falls beispielsweise ein Qualitätsnetz mit einer adaptiven finite Elemente Analyse durchlaufen wird, und ein Konvergieren in einigen Elementen fehlschlägt, kann das Verbesserungs-/Verfeinerungsverfahren automatisch neuerlich durchgeführt werden, wobei der Satz von Zielelementen solchen Elementen entspricht, und das Punkteinfügungskriterium als Endkantenverfeinerung in Block 220 ausgewählt wird. Wenn andererseits ein Netz mit einigen schlecht geformten Elementen betrachtet wird, kann das Verbesserungs- /Verfeinerungsverfahren automatisch neuerlich durchgeführt werden, wobei der Satz von Zielelementen diesen Elementen entspricht, und das Punkteinführtungskriterium in Block 220 als Delauneyeinfügung ausgewählt wird. Das in Block 220 gewählte Kriterium, dass ein Einfügungs-IFLAG einstellt, steuert dann das Ergebnis des Entscheidungsblocks 230.
Allgemeiner gesagt, unter Bezugnahme auf Fig. 6-12, ist das Verbesserungs-/Verfeinerungsverfahren der vorliegenden Erfindung auf ein Verfahren und eine Vorrichtung gerichtet für ein automatisches Erzeugen eines verbesserten verfeinerten Netzes von finiten Elementen für ein zu analysierendes Objekt, wobei das Objekt Begrenzungen und Oberflächen aufweist. Ein Längste-Kante- Punktplatzierungsverfahren zum automatischen Erzeugen des verbesserten verfeinerten Netzes des Objektes wird verwendet.
Unter Bezugnahme auf Fig. 6 ist ein bevorzugtes Ausführungsbeispiel des Verbesserungs- /Verfeinerungsverfahrens der vorliegenden Erfindung gezeigt, dass die folgenden Mittel umfasst: (1) eine Eingabe- /Ausgabeeinheit 20 für eine Eingabe der geometrischen Daten - und eine Ausgabe des Netzes; (2) eine Anzeigeeinheit 30 zum Visualisieren des Netzes und des Punkt-Platzierungsvorgangs; (3) eine Hauptverarbeitungseinheit (Vorrichtung) 40 zum Steuern des gesamten Netzverbesserungs-/-verfeinerungs-/- vergröberungsvorgangs; (4) eine Netzspeichervorrichtung 10 zum Speichern der geometrischen Eingabedaten, der Netzdatenstruktur und eine zusätzliche Einrichtung zum Durchführen des Netzverbesserungs-/-verfeinerungs-/- vergröberungsvorgangs; und (5) eine Parallelverarbeitungsvorrichtung 50 bestehend aus N Prozessoren, sowohl für das parallele Suchen von Sätzen von Begrenzungskanten, als auch für das parallele Verfeinern/Vergröbern von Sätzen von Elementen in Bezug auf ausgewählte Endkanten.
Die Eingabe-/Ausgabeeinheit 20 kann eine konventionelle CAD/CAM Eingabe-/Ausgabeeinheit zum Eingeben der geometrischen Daten des Objektes in den Netzspeicher 10 und zur Ausgabe des Netzes sein. Ein externes Delaunay-Programm, dass zur Veranschaulichung, nicht zur Beschränkung, hier als Teil der Eingabe-/Ausgabe- (CAD/CAM) Vorrichtung 20 und deren zugeordneter Programmierung betrachtet wird, ist ebenso erforderlich.
Fig. 7 ist ein allgemeines Flussdiagramm, dass das Verfahren dieser Erfindung beschreibt, so wie es wie folgt durch die Hauptverarbeitungseinheit durchgeführt wird; Nach einer Eingabe der Geometriedaten des anfänglichen Netzes (Block 200) wird ein Satz Zielelemente in dem Netz (Block 10) identifiziert. Aus diesen Zielelementen wird ein Untersatz von einem oder mehreren aktiven Zielelementen ausgewählt und ein Punkteinfügekriterium - Delaunay- oder Endkantenverfeinerungs - - wird gewählt (Blöcke 220, 230). Dann wird, unter Bezugnahme auf Block 240, unter Verwendung des Parallelcomputers 50 von Fig. 6 (dieser Parallelcomputer 50 ist in Fig. 8 detailliert dargestellt), der Satz von aktiven Elementen verarbeitet; wobei jedes aktive Zielelement einen Satz von Endkanten (Block 460 in Fig. 8) erzeugt. Dann wird unter Verwendung dieses Satzes von Endkanten der ausgewählte Punkt oder die Punkte gefunden (Fig. 9), die wiederum in das (neu berechnete) Netz in Übereinstimmung mit dem gewählten Punkteinfügekriterium (Fig. 10 Block 550) eingefügt werden. Insbesondere wird, unter Bezugnahme auf Fig. 10 für eine Delaunayeifügung, das Delaunayverfahren verwendet (Block 560), während für eine Nicht- Delaunayeinfügung eine Endkantenverfeinerung für jede Endkante (Block 570) durchgeführt wird. Zuletzt wird der Vorgang für aktualisierte Sätze von Aktivelementen und aktualisierte Sätze von Zielelementen wiederholt, bis ein benutzerdefiniertes Endkriterium erreicht ist (Blöcke 270, 280).
Wenn eine Delaunay-Punkt-Einfügung ausgewählt ist, wird ein Begrenzungsvorprozess (Block 235 in Fig. 7) in Fig. 11 detailliert beschrieben, verwendet, bevor der Prozess von Block 240 initiiert wird. Unter Bezugnahme auf Fig. 11 funktioniert dies wie folgt: nachdem die längste Kante LE jedes Elements T in dem Untersatz von Zielelementen gefunden ist, und der Mittelpunkt MPT einer jeder solchen LE gefunden ist (Block 600), werden innere Elemente oder Elemente mit der Längste-Kante über der Begrenzung nicht vorverarbeitet (Blöcke 610, was zu Block 660 führt). Alternativ (über Block 610) werden für jedes Begrenzungsverarbeitungselement T, mit der inneren Längste-Kante LE, die Abstände DB und DI jeweilig als die Maximallänge der Begrenzungskanten von T berechnet, und die Minimallänge der inneren Kanten von T (Block 620). Falls DB > ALFA1*DI, wobei der Parameter ALFA1 Nicht-Null- Faktor ist, (Block 630), wird ein zusätzlicher Begrenzungspunkt AUX gleich dem Mittelpunkt der längsten Begrenzungskante gefunden (Block 640); und ein Begrenzungspunkt, der die Begrenzungspunktverteilung um AUX verbessert, wird dann ausgewählt und in das Netz eingefügt, und es wird weiter fortgefahren, T aus dem Untersatz von aktiven Zielelementen (Block 650) zu entfernen. Solch ein ausgewählter Begrenzungspunkt kann beispielsweise durch Anwenden des Verfahrens dieser Erfindung auf eine beschränkte dreidimensionale Oberflächentriangulierung aufgefunden werden.
Fig. 8 zeigt ein allgemeines Flussdiagramm, dass das Verfahren dieser Erfindung beschreibt, wie es durch die Netzspeicher (10) und Längste-Kante-Parallelcomputer (50) Einheiten der in Fig. 6 veranschaulichten Vorrichtung ausgeführt wird. In Fig. 8 beginnt die Parallelverarbeitung für jedes Verarbeitungselement mit einem leer verarbeiteten Unternetz (Block 240). Dann führt jeder individuelle Prozessor die folgenden Aufgaben aus, wie in Blöcken 410 - 470 ausgeführt: ein individuelles Verarbeitungselement T der Längste-Kante LE wird dem Prozessor zugeordnet, und das Element T wird als verarbeitet markiert, durch Hinzufügen von T zu dem Unternetz (Block 410). Für dieses Verarbeitungselement werden zwei Sätze von Nachbarelementen identifiziert: der Satz von Aktivelementen, der die Elemente umfasst, die in dem Unternetz mit LE als eine Kante nicht vorhanden sind, und deren jeweilige längste Kante größer als LE (Block 420) ist; und der Satz von nicht-aktiven Elementen, der die Elemente umfasst, die in dem Unternetz nicht vorhanden sind, mit LE als eine Kante, und deren jeweilige längste Kante geringer als oder gleich LE (Block 430) ist. Dann wird bei Entscheidungsblock 440, falls der Satz von Aktivelementen nicht leer ist, jedes Aktivelement zu dem Satz von Verarbeitungselementen in dem Netzspeicher 10 (Block 450) zugefügt, um später verarbeitet zu werden; andernfalls sind keine nicht-aktiven Elemente mit dem Element TE verknüpft, und die Kante LE wird dem Satz von Endkanten im Netzspeicher 10 (Block 460) hinzugefügt. Zuletzt (jedes Element in dem Satz von nicht-aktiven Elementen ist als in dem Netz verarbeitet markiert, und) wird der Satz von Verarbeitungselementen durch Löschen (Entfernen) solcher Elemente aktualisiert, die in dem Unternetz bereits vorhanden sind (Block 470).
Fig. 12 beschreibt das Punkt-Auswahl-Verfahren, wenn eine Delaunaypunkteinfügung gewählt wurde (Blöcke 500 und 510 in Fig. 9). Das Verfahren verläuft wie folgt: sobald der Satz von Endkanten gefunden wurde, wird dann G-EDGE gefunden, die größte von diesen Endkanten, deren Mittelpunkt MPT als möglicher in das Netz einzufügender Punkt ausgewählt wird (Block 700). Falls G-EDGE eine innere Kante mit inneren Eckpunkten ist, wird der Punkt MPT als in das Netz einzufügen ausgewählt (Block 770). Andernfalls wird eine Begrenzungsbehandlung verwendet, die umfasst: entweder (1) Auswählen eines zusätzlichen Begrenzungspunktes gleich MPT, falls MPT ein Begrenzungspunkt ist (Blöcke 730 und 740); oder (2) Auswählen eines zusätzlichen Begrenzungspunktes gleich der Projektion von MPT über der Begrenzung, falls MPT nahe der Begrenzung liegt (Blöcke 750 und 760). Sobald der zusätzliche Begrenzungspunkt gefunden ist, wird ein Begrenzungspunkt, angeordnet in der Nachbarschaft solch eines zusätzlichen Begrenzungspunktes, und die Begrenzungspunktverteilung verbessernd, ausgewählt (Block 780). Solch ein Begrenzungspunkt kann beispielsweise aufgefunden werden, indem das Verfahren dieser Erfindung auf eine beschränkte dreidimensionale Oberflächentriangulierung angewendet wird. In jedem anderen Fall wird der Punkt MPT ausgewählt, der von der Begrenzung weit weg liegt (Block 770).
Unter erneuter Bezugnahme auf Blöcke 210 und 220 von Fig. 7, wenn eine Delaunaypunkteinfügung ausgewählt ist, betrachtet das bevorzugte Ausführungsbeispiel für diese Erfindung die Identifikation von Sätzen von Zielelementen und Untersätzen von Zielelementen wie folgt. Für jedes Element in dem Netz wird ein Geometriequalitätsmaß berechnet. Wann immer dieses Element ein Tetraeder ist, kann dieses Maß als das Verhältnis zwischen dem Volumen solch eines Elements und dem Volumen des rechtwinkligen Blocks mit einer Kante gleich der Länge der Längste-Kante dieses Elements definiert werden; dieses Verhältnis wird mit einer Normalisierungskonstante multipliziert, um ein Maß gleich 1 dem äquilateralen Tetraeder zuzuordnen. Der Satz von Zielelementen wird aufgefunden, indem als Zielelemente jedes Element identifiziert wird, dessen entsprechendes Element-Qualitäts- Maß unterhalb eines Schwellwerts liegt. Optional wird der Satz von Zielelementen erhöht, indem Sätze von Elementen hinzugefügt werden, die in Übereinstimmung mit einigen der folgenden Kriterien erzeugt sind: Elemente mit einem Finite- Elemente-Fehlerindikator unterhalb eines Schwellwerts; Elemente, deren Längste-Kante unterhalb eines Wertes liegt, der in Übereinstimmung mit einer benutzerdefinierten Größenfunktion und/oder anderen benutzerdefinierten Kriterien definiert ist. Der Untersatz von aktiven Zielelementen kann wiederum aufgefunden werden, indem aus dem Satz von Zielelementen all solche Elemente ausgewählt werden, deren entsprechenden Qualitätsmaße unterhalb eines Schwellwerts liegen, berechnet als ein Bruchteil des Durchschnittswertes des Elementqualitätsmaßes für den Satz von Zielelementen. Zusätzlich wird, wenn der Durchschnittswert oberhalb eines Parameterwerts liegt, der Globalsatz von Aktivelementen aufgefunden, indem alle Elemente des Satzes von Zielelementen betrachtet werden.
Die Fig. 13-16 beziehen sich auf das geometrische Verhältnis zwischen den Verfeinerungs- und Vergröberungsverfahren in Übereinstimmung mit der Erfindung.
Unter Bezugnahme auf das Verfeinerungsverfahren der Erfindung (IFLAG = TERMINAL - EDGES-REFINEMENT in Block 220 Fig. 7), gründet das Verfahren auf der Längste-Kante-Teilung von individuellen Tetraedern, wie in Fig. 13 für den Tetraeder mit Eckpunkten A, B, C, D und der längsten Kante AB veranschaulicht, wobei M der Mittelpunkt der Kante AB ist. Genauer gesagt wird die Längste-Kante-Unterteilung wiederholt angewendet, um Sätze von Elementen zu unterteilen, wobei alle Elemente eines jeden solchen Satzes eine gemeinsame (längste) Endkante teilen.
Das Längste-Kante-Vergröberungsverfahren dieser Erfindung kann (hinsichtlich der Endkantenabstraktion) wie folgt beschrieben werden: für jedes Zielelement, das zu vergröbern ist (oder entsprechend für jeden Eckpunkt VX) der zu eliminieren ist, ist wiederholt ein zugeordneter Satz von Elementsätzen zu finden, wobei jedes Element jedes Elementsatzes einen Eckpunkt VA und eine Kante VA-V1 oder VA- V2 gemeinsam nutzt, so dass der Eckpunkt VA als der Mittelpunkt einer vorhergehenden Endkante von Eckpunkten V1, V2 in einem vorhergehenden Netz erhalten wurde, durch Längste-Kante-Teilung jedes Elements, das die Endkante in dem vorhergehenden Netz gemeinsam nutzt. Man eliminiere dann jeden solchen Eckpunkt VA in geeigneter Reihenfolge, so dass die Eliminierung von Eckpunkt VA sich lokal auf die Eliminierung von Elementen reduziert, die den Eckpunkt gemeinsam nutzen, und auf die Erzeugung eines Satzes von neuen Elementen, die die zugeordnete Endkante gemeinsam nutzen (Block 1650 in Fig. 23). Dieser lokale Arbeitsvorgang wird einem individuellen Prozessor des Parallelcomputers von Fig. 23 zugewiesen.
Für jeden zu eliminierenden (zu vergröbernden) Zieleckpunkt VX findet das bevorzugte Ausführungsbeispiel des Vergröberungsverfahrens dieser Erfindung den Satz von zu eliminierenden Nachbareckpunkten (VERTEX-SET von Block 1240 in Fig. 21), indem die folgenden zusätzlichen (Verschachtelungs-) Eigenschaften des Längste-Kante- Verfeinerungsverfahrens genutzt werden: (1) jeder neue Punkt wird als Mittelpunkt der Längste-Kante eines vorhergehenden Elements aufgefunden; (2) die Form und relative Größe von Nachbarelementen bestimmen die Reihenfolge eines Vorrangs in dem Punkterzeugungsprozess; (3) jedes neue Element verbleibt vollständig enthalten in einem oder mehreren Vorläuferelementen, und die meisten der neuen Kanten sind tatsächlich Teile der vorhergehend existierenden Kanten.
Das bevorzugte Ausführungsbeispiel des Vergröberungsverfahrens dieser Erfindung verwendet eine ganzzahlig wertige Indikatorfunktion VE-IND (verknüpft mit dem Verhältnis eines Vorrangs beim Erzeugungsvorgang zwischen jedem Eckpunkt und dessen Nachbarn), so dass für jeden Eckpunkt VE entweder (1) VE-IND ist gleich Null, ob VE ein Eckpunkt des anfänglichen oder verbesserten Netzes (nicht unter Verwendung des Längste-Kante-Verfeinerungsverfahrens dieser Erfindung erhalten) ist, initialisiert in Block 910 von Fig. 18, oder VE-IND gleich dem Nachfolger des Maximalwertes unter den Werten der VE-IND-Funktion für die Eckpunkte V1 und V2 (Block 1060 in Fig. 19), wobei der Eckpunkt VE der Mittelpunkt der "Generatorkante" V1-V2 ist, wobei die Generatorkante eine vorhergehend existierende Endkante ist, deren Unterteilung den Eckpunkt VE erzeugte.
Unter Bezugnahme auf Fig. 14-16 veranschaulicht Fig. 14 ein zweidimensionales Verfeinerungsnetz, dessen Eckpunkte und (zugehörige VE-IND Indikatorwerte). Fig. 16 zeigt eine Tabelle, die für jeden Eckpunkt VE den korrespondierenden VE- IND-Wert und die zugehörige Generatorkante GENEDGE (G-EDGE) enthält. Die Eckpunkte, deren VE-IND-Wert gleich Null ist (und deren Generatorkante gleich NULL ist) entspricht dem anfänglichen Netz und kann nicht durch den Vorgang vergröbert werden.
Die Fig. 17-19, Fig. 24 und Fig. 26 beziehen sich auf die (geteilte) Netzdatenstruktur für das bevorzugte Ausführungsbeispiel der Erfindung (mit Bezug auf Block 10 in Fig. 8), dazu ausgelegt, die geometrischen Eigenschaften des Verfahrens und der Vorrichtung der vorliegenden Erfindung auszunutzen, was erlaubt: (1) die effiziente Implementierung des Verbesserungs-/Verfeinerungs-/Vergröberungsverfahrens dieser Erfindung und eine Vorrichtung dafür, (2) die effiziente Implementierung des parallelen Auffindens von geeigneten Sätzen von Endkanten (Fig. 8) zum Auswählen des Punktes oder der Punkte, die in das Netz einzufügen sind (Verbesserung/Verfeinerung des Netzes); (3) die parallel skalierbare Verfeinerung von Endkanten, was keine Zwischenprozessorkommunikation benötigt, wie in Fig. 20 beschrieben (eine verbesserte Alternative zu Block 570 in Fig. 10); (4) die effiziente parallele skalierbare Vergröberung des Netzes, was keine Zwischenprozessorkommunikation erfordert, wie in Block 1280 in Fig. 21 und in Fig. 23 gezeigt.
Unter Bezugnahme auf Fig. 17 entspricht die Längste-Kante- Netzdatenstruktur dieser Erfindung einer Netzdarstellung, die folgendes ausnutzt: (1) das inhärente Nachbar-Längste-Kante- Verhältnis, das zwischen den Elementen des Netzes besteht, gültig für Delaunay- und Nicht-Delaunay-Netze; und (2) die Verschachtelungseigenschaft von Längste-Kante verfeinerten Netzen (für eine Diskussion dieser Eigenschaft siehe z. B. Rivara(1989)), geeignet dargestellt durch sowohl die VE-IND Indikatorfunktion (die das Verhältnis eines Vorrangs zwischen den Eckpunkten der verschachtelten Elemente berücksichtigt), als auch der GENEDGE Darstellung, die die Generatorkante eines jeden Eckpunktes speichert (die vorhergehende Kante, deren Unterteilung diesen Eckpunkt erzeugt), wobei jeder Eckpunkt zu dem Netz durch Längste-Kante-Unterteilung eines Satzes von Nachbarelementen, die diese gemeinsame längste Kante teilen, hinzugefügt wird. Ein bevorzugtes Ausführungsbeispiel für die gemeinsam genutzte Netzdatenstruktur dieser Erfindung betrachtet die folgende Längste-Kante-Darstellung (in Zusammenhang mit dem Netz und seinem Aufbau): EDGE, ELEMENT, VERTEX und GEN-EDGE.
Jede spezielle EDGE (Kante) (Block 800 in Fig. 17) wird dargestellt mittels: (1) zwei Zeigern (Pointer) zu den zwei Eckpunkten (in der VERTEX-Darstellung), die diese EDGE definieren; (2) die Länge dieser EDGE; (3) ein Satz S1 von Zeigern, zu den Elementen der ELEMENT-Darstellung, so dass diese Elemente eine längste Kante gleich dieser EDGE haben; (4) ein Satz S2 von Zeigern zu den Elementen (in der ELEMENT- Darstellung) sodass die Elemente diese EDGE als eine Kante aufweisen, und deren längste Kante größer als diese EDGE ist (S2 ist leer für Endkanten des Netzes).
Jedes spezielle ELEMENT (Block 820 in Fig. 17) wird dargestellt mittels: (1) vier Zeigern zu den vier Eckpunkten (in der VERTEX-Darstellung); vier Zeigern zu den vier Nachbarelementen (in der ELEMENT-Darstellung), die eine gemeinsame Oberfläche mit dem Element aufweisen; (3) ein Zeiger zu einer Kante (in der EDGE-Darstellung), die diese Kante ist, die längste Kante des ELEMENT.
Jeder spezielle VERTEX (Eckpunkt) (Block 840 in Fig. 17) ist dargestellt mittels (1) den räumlichen Koordinaten des VERTEX; (2) einem VERTEX-Indikatorwert VE-IND, wobei dieser Wert gleich Null ist, falls VERTEX zu dem Anfangsnetz gehört (VERTEX wurde nicht erhalten durch ein Verfeinern einer vorhergehenden Kante), oder gleich dem Vorläufer der maximal VE-IND-Werte der vorhergehenden Eckpunkte V1, V2, deren Eckpunkt als Mittelpunkt der vorhergehenden Kante von Eckpunkten V1, V2 erhalten wurde, andernfalls; (3) ein Zeiger zu der Generatorkante von VERTEX (in der GEN-EDGE- Darstellung), wobei die Generatorkante eine vorhergehende Kante ist, die nicht in dem momentanen Netz existiert, deren Unterteilung den VERTEX produzierte; (4) ein Zeiger zu einem der Elemente (in der ELEMENT-Darstellung) mit dem VERTEX als einem Eckpunkt.
Jede spezielle GEN-EDGE (Block 860 in Fig. 17) ist dargestellt mittels: (1) zwei Zeigern auf die zwei Eckpunkte (in der VERTEX-Darstellung) die die GEN-EDGE als eine Kante (GEN-EDGE existiert nicht als eine Kante in dem momentanen Netz) definieren; (2) die Länge der GEN-EDGE.
Fig. 18 zeigt ein allgemeines Flussdiagramm, dass die Initialisierung der Längste-Kante-Netzdatenstruktur beschreibt, mit den Schritten: (1) nach der Eingabe des anfänglichen Netzes (Block 900), Initialisieren der VERTEX, EDGE und ELEMENT Darstellungen wie folgt (Block 910): für jeden Eckpunkt im Netz, Erzeugen eines Eckpunkts in der VERTEX-Darstellung und Einstellung von VE-IND = 0 und PGENEDGE = Null; für jeden Eckpunkt in dem Netz, Erzeugen einer Kante in der EDGE-Darstellung, Einstellen von LENGTH (Länge) der Kante, und leeren Sätzen S1 und S2; für jedes Element in dem Netz, Erzeugen eines Elements in der ELEMENT- Darstellung, und Einstellen von Zeigern auf dessen vier Eckpunkte und dessen vier gegenüberliegenden Nachbarelemente. (2) Für jeden Eckpunkt in der VERTEX-Darstellung, Einstellen von einem Zeiger auf eines der Elemente, die den Eckpunkt gemeinsam nutzt (Block 940). (3) Dann (Block 920), für jedes Element T in der ELEMENT-Darstellung, Vorgehen wie folgt: (a) Finden der längsten Kante LE-EDGE von T und Einstellen von PLEDGE (Zeiger zu LE-EDGE in der EDGE-Darstellung); und (b) für LE-EDGE in der EDGE-Darstellung, Einfügen von T in den Satz S1, und Einfügen von allen Nachbarelementen, die die LE- EDGE gemeinsam nutzen und mit einer längsten Kante größer als LE-EDGE, in den Satz S2.
Die Aktualisierung der Längste-Kante-Netzdatenstruktur, entweder durch Punkteinfügung (Verfeinerung) oder durch Punkteliminierung (Vergröberung), wird durch die Parallelcomputer von Fig. 20 bzw. Fig. 23 lokal durchgeführt, die wiederum ihrerseits die gemeinsam genutzte Netzdatenstruktur in Übereinstimmung mit den Diagrammen von Fig. 19 bzw. 24 modifizieren.
Fig. 20 zeigt ein allgemeines Flussdiagramm, dass die Systemarchitektur einer zusätzlichen Vorrichtung beschreibt, die eine parallel skalierbare Endkantenverfeinerung durchführen kann (Ersetzen und Verbessern der Arbeitsschritte, die durch Block 570 in Fig. 10 beschrieben sind), wann immer das Punkteinfügekriterium gleich TERMINAL- EDGE-REFINEMENT ausgewählt wurde (Block 220 in Fig. 7). In diesem Fall wird ein Satz von Punkten für eine Punkteinfügung ausgewählt (Mittelpunkt der Endkanten, die in Block 520 gefunden werden), wobei jeder individuelle Punkt durch eine Längste-Kante-Unterteilung von jedem der Elemente, die die zugeordnete Endkante gemeinsam nutzen, eingefügt wird, wie in Fig. 13 gezeigt. Die parallele Punkteinfügung, die ein im wesentlichen lokaler Arbeitsvorgang ist, und keine Zwischenprozessorkommunikation erfordert, läuft wie folgt ab: die Steuermaschine von Block 1100, die mit dem gemeinsam genutzten Netzspeicher von Block 1130 interagiert, führt die folgenden Schritte durch: (1) Eingeben des Netzes und des Satzes von zu verfeinernden Endkanten; (2) Initialisieren jedes Eckpunkts des Netzes als nicht belegt, und jeder Endkante, die zu verarbeiten ist, als nicht verarbeitet; (3) für jede Endkante, Auffinden des Satzes S von Elementen, die die Endkante gemeinsam nutzen, und des Satzes S auch von Nachbareckpunkten, die die Eckpunkte der Elemente S enthalten und die Eckpunkte der Elemente, die in S nicht enthalten sind, und mindestens einen Eckpunkt gemeinsam mit einem Element von S aufweisen; (4) Steuern der Zuordnung von jeder individuellen Endkante (als nicht verarbeitet markiert) zu einem individuellen freien Prozessor, wann immer alle Eckpunkte des Satzes V in Zusammenhang mit der Endkante als nicht belegt markiert sind; in solch einem Fall Markieren der zugeordneten Endkante als verarbeitend und die Eckpunkte des Satzes SV als belegt.
Zusätzlich führt jeder individuelle Prozessor die folgenden Schritte aus (Block 1150); (1) Eingeben der Endkante T-EDGE von Eckpunkten V1, V2, Mittelpunkt MPT und den zugeordneten Sätzen S und SV; (2) Durchführen der Endkantenverfeinerung (oder äquivalent der MPT Punkteinfügung) folgend den Unterschritten: (a) Unterteilen jedes Elementes des Satzes S (Elemente, die die Endkante gemeinsam nutzen) durch die Ebene, die durch MPT und Eckpunkte gegenüber der Endkante von Eckpunkten V1, V2, wie in Fig. 13 gezeigt, definiert ist; (b) Identifizieren von Sätzen von Elementen und Kanten, die aus der Datenstruktur zu eliminieren sind, Umsetzen von neuen Kanten und Elementen, die zu der Netzdatenstruktur hinzuzufügen sind; (c) lokales Modifizieren der Netzdatenstruktur, wie in Fig. 19 ausgeführt; (d) Markieren der Eckpunkte von SV als nicht belegt; (e) Markieren der Endkante als verarbeitet; und (f) Freigeben des Prozessors.
Fig. 19 zeigt ein allgemeines Flussdiagramm, dass die lokale Modifikation der Netzdatenstruktur beschreibt, wann immer ein neuer Punkt eingefügt wird, entweder mittels einer Delaunay- Einfügung (IFLAG = DELAUNAY in Block 220 von Fig. 7) oder durch individuelle Verfeinerung einer Endkante (IFLAG = TERMINAL - EDGE - REFINEMENT in Block 220 von Fig. 7). In beiden Fällen wurde der eingefügt neue Punkt als der Mittelpunkt einer Begrenzungskarte des momentanen Netzes aufgefunden. Das Datenstrukturmodifikationsverfahren (mittels Punkteinfügung) umfasst im wesentlichen die Schritte: (1) Einfügen der folgenden Bestandteile (Block 1100): den neuen Eckpunkt VN Mittelpunkt der Kante von Eckpunkten V1, V2; das zugehörige IFLAG; die Sätze S-EL und S-EDG, die jeweilig die Elemente und Kanten enthalten, die aus der Netzdatenstruktur zu eliminieren sind; die Sätze SNEW-EL und SNEW-ED, Sätze von neuen Elementen und neuen Kanten, die jeweilig zu der Netzdatenstruktur hinzuzufügen sind. (2) Eliminierung der Elemente von S-EL und der Kanten von S-EDG aus ELEMENT bzw. EDGE-Darstellung; (3) Erzeugen von Eckpunkt VN in VERTEX- Darstellung, Erzeugung der Kanten SNEW-ED in der EDGE- Darstellung und Erzeugung der Elemente von SNEW-EL in der ELEMENT-Darstellung; (4) Aktualisierung der Nachbarschaftsinformation und Längste-Kante-Verhältnisse für die alten verbleibenden Nachbarelemente und Eckpunkte in der EDGE, ELEMENT und VERTEX-Darstellung.
Wenn IFLAG = TERMINAL - EDGE - REFINEMENT ausgewählt wurde (über Entscheidungsblock 1040, was zu Block 1060 führt) umfasst das Netzdatenstrukturmodifikationsverfahren, die zusätzlichen Schritte: (1) Hinzufügen der Generatorkante von Eckpunkten V1, V2 zu der GEN-EDGE-Darstellung; (2)für Eckpunkt VN in der Eckpunktdarstellung, Einstellen des zugeordneten VE-IND-Wertes gleich dem Nachfolger der Maximalwerte zwischen VE-IND-Werten der Eckpunkte V1 und V2, und Einstellen des zugehörigen Zeigers auf die Generatorkante in der GEN-EDGE-Darstellung und (3) für jeden Eckpunkt VN in der VERTEX-Darstellung, Einstellen eines Zeigers auf eines der Elemente, die VN teilen (Block 1080).
Wenn IFLAG = DELAUNAY ausgewählt ist, führt der Entscheidungsblock 1040 direkt zu Block 1080, wo für Eckpunkt VN in der VERTEX-Darstellung der Zeiger auf eines der Elemente, die den Eckpunkt teilen, gesetzt wird.
Mit Bezug auf Fig. 21 umfasst das Vergröberungsverfahren dieser Erfindung im wesentlichen für jeden Eckpunkt VX, der zu vergröbern oder zu eliminieren ist (Block 1200), vom zugehörigen Knoten (VX, NX, GX), wobei NX der VE-IND-Wert von VX ist und GX dessen Generatorkante (Block 1220), Auffinden eines zugehörigen VERTEX-SET von Knoten (VZ, NZ, GZ) entsprechend dem Satz von Eckpunkten, der von dem Netz zu eliminieren ist (mit den zugehörigen VE-IND-Werten VZ und Generatorkanten GZ), wie in Block 1240 gezeigt. Die geordnete Vergröberung jedes der Eckpunkte (in Übereinstimmung mit der in Block 1260 gezeigten Reihenfolge), erlaubt es, eine Endkante erneut zu erlangen, die vorhergehend mittels des Verfeinerungsprozesses verfeinert wurde, als ein Ergebnis der Erzeugung des Eckpunktes VX. Wiederholen dieses Vorgangs, bis die Generatorkante von Eckpunkt VX ebenso vergröbert ist (Entscheidungsblock 1290) und der Eckpunkt VX eliminiert ist, was das vergröberte Netz (Block 1300) erzeugt.
Fig. 22 zeigt ein allgemeines Flussdiagramm, dass den inkrementalen VERTEX-SET Aufbau beschreibt. Das Verfahren umfasst die folgenden Schritte: (1) Initialisieren von VERTEX-SET und VP-SET mit dem Knoten (VX, NX, GX), was VP-SET ist, und einem zusätzlichen Satz, der die zu verarbeitenden Knoten speichert (Block 1400); (2) Aufgreifen von Knoten (VX. NY. GY) von VP-SET (Block 1420); (3) Auffinden von SN, den Satz von Nachbarknoten (VZ, NZ, GZ), sodass VZ der Nachbareckpunkt von VY in dem Netz ist (1440); (4) für jeden Knoten (VZ, NZ, GZ) in der SN, Vorgehen wie folgt: falls NZ > NY (Entscheidungsblöcke 1460, 1480, was zu Block 1520 führt), Hinzufügen von Knoten (VZ, NZ, GZ) zu sowohl dem VERTEX-SET als auch dem VP-SET, falls NZ = NY (Block 1480) und falls GY < GY (Block 1500) Hinzufügen von Knoten (VZ, NZ, GZ) sowohl zum VERTEX-SET als auch VP-SET. Der Knoten (VZ, NZ, GZ) wird andernfalls von den Verarbeitungsknoten entfernt; (S) wann immer VP-Set nicht leer ist (Block 1540), Wiederholen des Prozesses, mit Block 1240 beginnend (Aufgreifen eines neuen Knotens)(VY, NY, GY) von VP-Set usw.). Der Prozess ist beendet, wenn VP-SET leer ist, was die vollständige Identifikation des VERTEX-SET produziert (Satz von Knoten, die von dem Netz zu eliminieren sind, als eine Folge der Eliminierung des Zieleckpunkts VX).
Unter Bezugnahme auf das zweidimensionale Beispiel von Fig. 14, umfasst die Vergröberung (Eliminierung) von Eckpunkt G ein Auswählen von G und darauffolgende Nachbarn mit einer VE- IND-Funktion, die größer als oder gleich zu der VE-IND- Funktion des vorhergehenden Eckpunkts ist (Eckpunkte H, J, F und deren Nachbarn); im Falle von gleich der VE-IND-Funktion, den Eckpunkt nur dann auswählen, wenn die Länge der Generatorkante des Eckpunkts kleiner als die Länge der Generatorkante des vorhergehenden Eckpunkts ist (Block 1500). Dieses entfernt sowohl Eckpunkt E (Nachbareckpunkt von F), als auch Eckpunkt I (Nachbareckpunkt von J), da diese jeweilige Generatorkanten aufweisen, die größer als die Generatorkante des jeweiligen vorhergehenden Eckpunkts sind. Dieses definiert den VERTEX-SET (der die Eckpunkte G, H, J, F enthält), den Satz der Eckpunkte, der in dem Netz zu vergröbern ist. Das Vergröbern von jedem der Eckpunkte (d. h. Eckpunkt J und zugeordneter Generatorkante FB in Fig. 14, was das Netz von Fig. 15 erzeugt), umfasst einfach nur ein Austauschen der Elemente, die den Eckpunkt J gemeinsam haben, durch größere Elemente, die die Generatorkante FB gemeinsam haben, was die FB-Endkante in dem verfeinerten Netz von Fig. 15 ist (wobei FB die längste Kante der umgebenden Elemente GFB und FIB ist). Die Vergröbung der Eckpunkte wird in Übereinstimmung mit der folgenden Reihenfolge durchgeführt (Block 1260 in Fig. 21): Verringern der Ordnung der VE-IND- Funktion, und, für gleiche VE-IND-Werte, in aufsteigender Reihenfolge gemäß der Länge der zugeordneten Generatorkanten (Eckpunkte J, H und F in dieser Reihenfolge in dem Netz von Fig. 14). Die Reihenfolge garantiert die Vergröberung der Endkanten, wie für Eckpunkt J beschrieben. Das Verfahren schreitet dann zu der parallelen Vergröberung der geordneten Knoten von VERTEX-SET voran (Block 1280 in Fig. 21 und Fig. 23).
Unter Bezugnahme auf Fig. 23 wird die Systemarchitektur einer zusätzlichen Vorrichtung beschrieben, die eine parallele skalierbare Vergröberung der geordneten Eckpunkte, die den Knoten von VERTEX-SET (Block 1280 in Fig. 21) zugeordnet sind, durchführen kann.
Da dies ein wesentlich lokaler Arbeitsschritt ist, erfordert die parallele Punktvergröbung (Eliminierung) keine Interprozessorkommunikation, und schreitet voran wie folgt: die Steuermaschine von Block 1600, die mit dem gemeinsam genutzten Netzspeicher von Block 1630 interagiert, führt die folgenden Schritte durch: (1) Eingeben des geordneten Satzes von zu vergröbernden Eckpunkten; (2) Initialisieren aller Eckpunkte des Netzes als nicht belegt, und aller Eckpunkte des Satzes von Eckpunkten, die zu vergröbern sind, als nicht verarbeitet; (3) Steuern der geordneten Zuordnung der individuellen Eckpunkte zu einem individuellen freien Prozessor wie folgt: (a) Wähle den folgenden Eckpunkt VA von VE-IND Indikatorwert NA und die Generatorkante von Eckpunkten V1, V2; (b) Finde den Satz S von Nachbareckpunkten von VZ von VA (die Kante VA-VZ ist eine Kante des Netzes); (c) Falls die Eckpunkte V1, V2 zu S gehören, und alle Eckpunkte von S als nicht belegt markiert sind, Markieren von diesen als belegt, Markieren von Eckpunkt VA als verarbeitet und Zuordnen des Eckpunkts (und dessen zugeordnete NA, V1, V2 und S) zu einem individuellen freien Prozessor. Andernfalls wird der nächste Eckpunkt ausgewählt. Für jeden zugeordneten neuen Eckpunkt (Block 1650) führt der entsprechende individuelle Prozessor die folgenden Schritte durch: (1) Eingeben des Eckpunkts VA, dessen VE-IND-Wert NA, dessen Generatorkante von Eckpunkten V1, V2 und des zugeordneten Satzes von Nachbareckpunkten S. (2) Auffinden des Satzes von Elementen, die aus dem Netz zu eliminieren sind (Elemente, die den Eckpunkt V alle gemeinsam nutzen); (3) Auffinden des Satzes von neuen Elementen des Netzes (neue Elemente, die die Endkante V1-V2 gemeinsam nutzen) und des Satzes von neuen Kanten, der zu dem Netz hinzuzufügen ist (neue Kante V1-V2); (4) lokales Modifizieren der Längste-Kante-Netzdatenstruktur, wie in Fig. 24 ausgeführt; (5) Markieren der Eckpunkte von S als nichtbelegt und Markieren von VA als verarbeitet; (6) Freigeben des Prozessors.
Unter Bezugnahme auf Fig. 24 wird mit einem allgemeinen Flussdiagramm die lokale Modifikation der Netzdatenstruktur beschrieben, wann immer ein existierender Punkt von dem momentanen Netz vergröbert wird (Block 1650 in Fig. 23). Das Datenstrukturmodifikationsverfahren (durch Eckpunkteliminierung) führt die folgenden Schritte durch: (1) Eingabe des Eckpunkts VA, der zu vergröbern ist, dessen Generatorkante V1-V2 und von Sätzen S-EL, S.-EDG, SNEW-EL und SNEW-ED, dem jeweiligen Satz von Elementen, die von dem Netz zu eliminieren sind, den Satz von Kanten, die von dem Netz zu eliminieren sind, den Satz von Elementen, die zu dem Netz hinzuzufügen ist, und der Satz von neuen Kanten, der dem Netz hinzuzufügen ist (Block 1700); (2) danach Durchführen der lokalen Aktualisierung der Netzdatenstruktur wie folgt: (a) Eliminierung der Elemente von S-EL und der Kanten von S-EDG von der ELEMENT- bzw. EDGE-Repräsentation; (b) Erzeugung der Kanten von SNEW-ED und der Elemente von. SNEW-EL in der EDGE- bzw. ELEMENT-Darstellung; (c) Aktualisieren der Nachbar- und Längste-Kante-Information bezüglich der neuen Elemente und der neuen Kanten mit den verbleibenden Nachbarelementen und - kanten in der EDGE-, ELEMENT- und VERTEX-Darstellung; (d) Eliminierung der Generatorkante von den Eckpunkten V1, V2 aus der GENEDGE-Darstellung.
Unter Bezugnahme auf Fig. 25 wird in dieser Figur ein bevorzugtes Ausführungsbeispiel für ein automatisches Netzerzeugungsverfahren beschrieben, das die unterschiedlichen Verfahren dieser Erfindung integriert und diese voll ausnutzt. Das integrierte Verfahren betrachtet insbesondere die folgenden Punkte: (1) kombinierte Benutzung von sowohl des Oberflächenverbesserungsverfahrens als auch des Volumenverbesserungsverfahrens dieser Erfindung, um den Bezug der Objektbegrenzung und geometrischen Schnittstellen einzuführen, wann immer das eingegebene Volumennetz Elemente aufweist, die die Objektbegrenzung schneiden und/oder einige geometrische Schnittstellen; (2) kombinierte Verwendung von sowohl des Oberflächenverbesserungsverfahrens als auch des Volumenverbesserungsverfahrens dieser Erfindung, um ein Qualitätsnetz zu erzeugen, das der Geometrie angepasst ist; (3) Verwendung des Längste-Kante-Verfeinerungs- /Vergröberungsverfahrens dieser Erfindung, um ein verfeinertes/vergröbertes Qualitätsnetz zu erzeugen; (4) Verwendung von externen Netzmodifikationsverfahren, wie in dem Fall einer Änderung von Objektbegrenzungen und/oder Schnittstellen und die entsprechende Aktualisierung der Netzdatenstruktur.
Nach einer Eingabe des Begrenzungsmodells (Block 1800), umfasst das integrierte Verfahren die folgenden Schritte (Block 1810): (1) Erzeugen eines Oberflächennetzes der Objektbegrenzung einschließlich Schnittstellen; (2) Verwenden des Oberflächenverbesserungsverfahrens dieser Erfindung (mit I-FLAG = DELAUNAY), um ein Qualitätsoberflächennetz einschließlich Schnittstellen zu erzeugen; (3) Verwenden der Oberflächeneckpunkte, um ein Volumennetz zu erzeugen; (4) Fortschreiten, um die Geometriebegrenzung und Schnittstellen (Block 1820) wie folgt zu berücksichtigen: Auffinden des Satzes von Volumenelementen, der die Begrenzung oder Schnittstellen schneidet; dann, für jedes Element T in S und bis S leer ist, Durchführen der folgenden Schritte: (a) Auffinden eines Oberflächenelements T-SURF des Oberflächennetzes, das T schneidet; (b) Verwenden des Oberflächenverbesserungsverfahrens (mit IFLAG = DELAUNAY) zum Auswählen eines Nachbarpunktes und Einfügen dessen in das Oberflächennetz; (c) Einfügen des neuen Punktes in das Volumennetz; (d) Aktualisieren des Satzes S von momentanen Volumenelementen, die die Begrenzung und Schnittstellen schneiden.
Sobald ein Volumennetz erzeugt ist, das die Begrenzung und Schnittstellen berücksichtigt, erhalten ist, schreitet das integrierte Verfahren damit voran, das Volumennetz zu verbessern, unter Verwendung des Volumenverbesserungsverfahrens dieser Erfindung mit IFLAG = DELAUNAY (Block 1830).
Sobald ein Volumenqualitätsnetz erhalten wurde, schreitet das integrierte Verfahren dann voran, das Verfeinerungsverfahren dieser Erfindung zu verwenden, gefolgt durch die kombinierte Verwendung des Verfeinerungs- /Vergröberungsverfahrens dieser Erfindung, und optionales Verwenden eines externen Netzmodifikationsverfahrens, um ein aktualisiertes Netz (Block 1840) zu erzeugen; und dann Fortschreiten zu einer Aktualisierung der Netzdatenstruktur, wann immer die Objektgeometrie (Begrenzungen und/oder Schnittstellen) und/oder einige Eckpunktkoordinaten geändert wurden (Block 1840 in Fig. 26), wobei alle Änderungen zu Eckpunktänderungen reduziert sind.
Dann, wann immer das momentane Netz ein akzeptables Netz ist, in Übereinstimmung mit einem benutzerdefinierten externen Kriterium (Entscheidungsblock 1850 was zu Block 2000 führt) ist der Netzerzeugungsvorgang beendet. Andernfalls folgt das integrierte Netzerzeugungsverfahren zu Entscheidungsblock 1860, wobei die Qualität des Netzes überprüft wird. In dem Fall, dass das Netz ein akzeptables Qualitätsnetz ist, schreitet das Verfahren wiederum zur Verfeinerung und/oder Vergröberung und/oder Modifikation des Netzes voran (Block 1840) usw. Andernfalls führt der Entscheidungsblock 1860 zum Block 1870 und erzeugt die Neuberechnung des Delaunay-Netzes der momentanen Eckpunkte, gefolgt durch die Verwendung des Netzverbesserungsverfahrens dieser Erfindung, bevor wiederum zum Block 1840 geschritten wird.
Zuletzt zeigt Fig. 26 ein allgemeines Flussdiagramm, dass die lokale Aktualisierung der Netzdatenstruktur beschreibt, wann immer einige Eckpunktkoordinaten modifiziert wurden (Geometrieänderungen und/oder Eckpunktänderungen). In solch einem Fall haben sich die relativen Positionen einiger Eckpunkte geändert, was einige Elementformen und die Längste- Kante-Beziehung zwischen den Elementen modifiziert. Das Aktualisierungsverfahren umfasst im wesentlichen die Schritte (1) Eingabe des Satzes S von geänderten Eckpunkten (deren Koordinaten geändert wurden) und den entsprechenden neuen Koordinaten (Block 1900); dann, in Übereinstimmung mit Block 1920, (2) Auffinden des Satzes SV von Nachbareckpunkten in dem Netz, nicht enthalten in S, und mindesten mit einem Eckpunkt von S verbunden; (3) Hinzufügen der Eckpunkte von SV zu dem Satz S, (4) Auffinden des Satzes S-EDG der Kanten des Netzes, einschließlich mindestens eines Eckpunkts von S; (5) Auffinden des Satzes S-EL von Elementen des Netzes, einschließlich mindestens eines Eckpunkts von S. dann, in Übereinstimmung mit Block 1940 (6) Voranschreiten, um die (beschränkte) Längste-Kante-Netzdatenstruktur aufzubauen, zugeordnet zu dem Unternetz (nicht notwendigerweise verbunden), definiert durch die Sätze S, S-EDG und S-EL, durch Verwendung der Prozedur von Fig. 18; (7) dann, Aktualisieren der globalen Netzdatenstrukturen in Übereinstimmung mit den Daten der beschränkten Datenstruktur, zugeordnet zu dem Unternetz, und Einstellen von VE-IND = 0 für die Eckpunkte von S. (8) Löschen von der GENEDGE- Darstellung solcher Generatorkanten, die mindesten einen Eckpunkt in SV haben, und Einstellen von VE-IND = 0 für die Eckpunkte dieser Generatorkanten; (9) Aktualisieren der zugeordneten VE-IND-Werte für die Nachbareckpunkte, deren VE- IND-Werte sich in den Schritten 7 und 8 geändert haben.
Es wird darauf hingewiesen, dass, auch wenn jede Komponente dieser Erfindung die Endkantenabstraktion des Netzes von Elementen und deren geometrischer Eigenschaften voll ausnutzt, und alle diese Komponenten geeignet integriert werden können, um ein flexibles und automatisches Netzerzeugungssystem bereitzustellen, die Verbesserungskomponente, die Verfeinerungskomponente und die Verfeinerungs-/Vergröberungskomponente alleine arbeiten können, unabhängig von einander in dem Sinne, dass diese Komponenten separat in unterschiedlichen Anwendungen verwendet werden können. Das Vergröberungsverfahren kann jedoch nur verwendet werden, um Netze zu vergröbern, die mittels vorhergehender Verwendung des Längste-Kante- Verfeinerungsverfahrens erzeugt wurden, und in diesem Sinne umfasst und generalisiert es das Verfeinerungsverfahren.
Es versteht sich, dass die vorhergehende Beschreibung diese Erfindung und deren Anwendungen lediglich veranschaulicht. Verschiedene Alternativen und Abwandlungen können durch den Fachmann getätigt werden, ohne die Erfindung zu verlassen. Zusätzlich soll diese Offenbarung und die zugeordneten Ansprüche die Beschränkung und/oder Generalisierung des Punktplazierungs-/-eliminierungsverfahren und die Vorrichtung dafür für Ebene- und Oberflächentriangulierungen umfassen, mit Anwendung auf die automatische Trangulierung von nichtkonvexen ebenen Geometrieren, die automatische Oberflächentriangulierung von dreidimensionalen Objekten, und die Oberflächentriangulierung, wie in Geländemodellen oder Computergrafikanwendungen erforderlich. Diese Offenbarung und zugeordneten Ansprüche sollen die Handhabung von Sequenzen von verschachtelten Netzen umfassen, wie in Multigitteranwendungen erforderlich (für eine Referenz siehe Rivara-Modell (1986)). Zusätzlich soll diese Offenbarung und zugeordneten Ansprüche die Handhabung von Quasi-Delaunay- Netzen umfassen. Diese Offenbarung und die zugeordneten Ansprüche sollen die Generalisierung des Verfahrens dieser Erfindung umfassen, der Netzdatenstruktur, und Vorrichtungen dafür, für (1) die verteilte Verfeinerung/Vergröberung/Verbesserung des Netzes unter Verwendung einer verteilten Längste-Kante-Netzdatenstruktur; (2) für allgemeine Netze, bestehend aus Unternetzen, die entweder Delaunay-Unternetze und/oder verschachtelte Längste- Kante (Nicht-Delaunay) Netze sind, erhalten durch das Längste-Kante-Verfeinerungs-/Vergröberungsverfahren dieser Erfindung. Diese Erfindung soll auch die Generalisierung des Punktplatzierungsverfahrens, und die Vorrichtung dafür, bis N-Dimensionen umfassen, wobei N größer als 3 ist, verwendbar beispielsweise im Bereich von "Range Searching" (Bereichssuche), einem Gebiet mit extensiven praktischen Anwendungen, beispielsweise in Datenbanken. Demzufolge soll die vorliegende Erfindung alle solche Alternativen, Abwandlungen, Veränderungen, Beschränkungen und Generalisierungen umfassen, die innerhalb des Umfangs der angefügten Ansprüche liegen.
Die vorliegende Erfindung umfasst und generalisiert die Verfahren, die durch Rivara (1984 /(a), 1984 (b), 1986, 1996 und 1997) beschrieben wurden, durch Rivara et al. (1992) und durch Rivara et al (1997), was eine Handhabung von Delaunay- und Nicht-Delaunay-Netzen erlaubt; und verbessert und generalisiert das Vergröberungsverfahren, das durch Rivara (1989) beschrieben ist.
Diese Erfindung verbessert Verfahren, die durch den Stand der Technik gelehrt werden und liefert einen nützlichen Gewinn in mindestens den folgenden Weisen:
Die Verbesserung eines Netzes mit schlecht geformten Elementen wird einfach und natürlich durch ein Auswählen von Punkten durchgeführt, die die Qualität der lokalen Punktverteilung um die schlecht geformten Elemente herum verbessern, und dann Einfügen solcher Punkte unter Verwendung der Delaunay Lehre oder Abwandlungen der Delaunay Lehre. Um diese Punkte zu suchen, wird nur die Verteilung von ansteigenden Nachbarelementen betrachtet, nicht die Delaunay- Eigenschaft des Netzes. Das Suchverfahren modifiziert nicht die geteilte Netzdatenstruktur.
Das Verfahren dieser Erfindung eliminiert natürlich unerwünschte dünne Scheiben, ohne spezielle Techniken, um diese zu behandeln.
Da das Punktsuchverfahren nicht von der Delaunay-Eigenschaft des Netzes abhängt, arbeitet die Erfindung gut mit Delaunay- und Nicht-Delaunay-Netzen. Demzufolge betrachtet das Verfahren der vorliegenden Erfindung optional die pure Verfeinerung/Vergröberung von Qualitätsnetzen, wie erforderlich in adaptiven und/oder Multi-Gitter finite Elemente-Analyseanwendungen (eine Diskussion kann in Rivara (1986) gefunden werden). Ein einfaches Punkteinfügeverfahren, das nur die Längste-Kante-Verfeinerung von Sätzen von Elementen verwendet, von denen alle die längste Kante gemeinsam haben (Endkante), wird in diesem Fall verwendet.
Das kritische Suchverfahren der vorliegenden Erfindung umfasst ein wiederholtes Überschreiten nachfolgender Nachbarelemente über dem Netz, Starten mit einem aktiven Zielelement, bis ein Satz von Endkanten in dem Netz identifiziert ist, wobei die Mittelpunkte solcher Endkanten die möglichen Punkte sind, die in das Netz einzufügen sind. Die Vorrichtung der vorliegenden Erfindung nutzt die Vorteile der inhärenten Eigenschaften des Suchverfahrens unter Verwendung eines einfachen effizienten parallelen Computers, der die parallele Suche ohne Modifikation des Netzes durchführen kann, und die folgenden Ergebnisse produziert: (1) die Erhöhung des Satzes von Nachbarelementen, über dem die parallele Suche fortzuführen ist, und (2) die Identifikation eines Satzes von Endkanten.
Das Verfahren und die Vorrichtung dieser Erfindung erlaubt die parallele Verfeinerung/Vergröberung des Netzes durch lokales Modifizieren von Sätzen von Nachbarelementen, die die gemeinsame längste Kante teilen, ohne zwischengelagerte nicht gültige Netze zu erzeugen, und ohne eine Interprozessorkommunikation zu erfordern.
Das Verfahren und die Vorrichtung dieser Erfindung verwenden eine verbesserte Netzdatenstruktur, die die integrierte Verbesserung/Verfeinerung/Vergröberung des Netzes unterstützen.
Während nur bestimmte bevorzugte Merkmale der Erfindung veranschaulicht und beschrieben wurden, sind dem Fachmann viele Abwandlungen und Änderungen offensichtlich. Es versteht sich daher, dass die angefügten Ansprüche alle solche Modifikationen und Änderungen abdecken sollen, die innerhalb des Umfangs der Erfindung liegen, wie durch die Ansprüche definiert.

Claims

1. Ein Verfahren zum Verfeinern von sowohl einer Eckpunktverteilung als auch eines Netzes von Elementen für ein zu analysierendes Objekt, wobei jedes Element des Netzes eine Vielzahl von Eckpunkten und Kanten aufweist, ein Körper des Objekts Begrenzungen und Schnittstellen aufweist, und die Elemente des Netzes Begrenzungselemente umfassen, definiert als solche Netzelemente, die mindestens eine der Begrenzungen schneiden, unter Verwendung einer computerisierten Vorrichtung, die Schritte umfassend:

a) Erzeugen eines Netzes von Elementen für das Objekt (200), identifizieren eines Satzes von Zielelementen unter den Elementen des Netzes (210) unter Verwendung von vorgegebenen Zielelement- Identifizierungskriterien, und identifizieren eines Untersatzes des Satzes von Zielelementen (220) unter Verwendung von vorgegebenen Zielelementuntersatz-Identifizierungskriterien;

c) für jedes Element in dem Untersatz von Zielelementen (240), suchen eines Satzes von Endkanten (460) unter Verwendung eines Längste- Kante-Suchverfahrens, und Einfügen mindestens eines ausgewählten Punktes, der mindestens einer der Endkanten zugeordnet ist, in das Netz, um ein verfeinertes Netz (240) zu erzeugen, wobei jede der Endkanten als eine gemeinsame Längste-Kante von jedem der Netzelemente definiert ist, die die Endkante teilen;

e) Wiederholen des Schrittes c) für nachfolgende Untersätze (270) von aktualisierten Sätzen der Zielelemente, bis ein vorgegebenes Haltkriterium erreicht ist.

2. Das Verfahren nach Anspruch 1, weiter zum verbessern zusätzlich zum Verfeinern der Eckpunktverteilung und des Netzes von Elementen, umfassend den Schritt, zwischen den Schritten a) und c):

b) Auswählen eines Satzes von Begrenzungspunkten der Begrenzungselemente, die in dem Untersatz von Zielelementen enthalten sind, unter Verwendung eines Längste-Kante-Begrenzungsauswahlverfahrens, Einfügen der ausgewählten Begrenzungspunkte in das Netz, und Aktualisieren des Untersatzes der Zielelementen des Netzes (650); und

wobei der Schritt c) weiter umfasst:

Auswählen des mindestens einen ausgewählten Punktes (510) unter Verwendung eines Endkanten-Auswahlverfahrens und Einfügen des mindestens einen ausgewählten Punktes in das Netz (560), und

wobei Schritt e) weiter umfasst:

Wiederholen des Schritts b) zusätzlich zum Schritt

c) für nachfolgende Untersätze (270) von aktualisierten Sätzen von den Zielelementen, bis ein vorgegebenes Haltkriterium erreicht ist.

3. Das Verfahren nach Anspruch 2, wobei die Begrenzungselemente als Elemente des Netzes definiert sind, die mindestens eines der folgenden Kriterien erfüllen: Aufweisen mindestens eines Eckpunktes über den Objektbegrenzungen; Schneiden der Objektbegrenzung; und

Schneiden der Objektschnittstelle; wobei das Längste- Kante-Begrenzungsauswahlverfahren von Schritt b), für jedes Begrenzungselement in dem Untersatz von Zielelementen (610), die weiteren Schritte umfasst:

b1) Finden einer längsten Kante des Begrenzungselements und eines Mittelpunktes MPT der längsten Kante (600) des Begrenzungselements;

b2) Überspringen des Begrenzungsprozesses von Schritt b4), falls der Mittelpunkt MPT ein Begrenzungspunkt (610) ist;

b3) Überspringen des Begrenzungsvorgangs von Schritt b4), falls die Maximallänge der Kanten des Begrenzungselements größer als ein Bruchteil ALPHA1 der Minimallänge der inneren Kanten des Begrenzungselements ist, wann immer die Maximallänge existiert, wobei ALPHA1 ein Parameter größer als Null (620, 630) ist;

b4) andernfalls, Identifizieren eines ausgewählten Punktes (650) als einen von den Begrenzungspunkten, die die Begrenzungspunktverteilung in der Nähe eines zusätzlichen Begrenzungspunktes verbessern, und Einfügen des ausgewählten. Punktes in das Netz (650), wobei der zusätzliche Begrenzungspunkt ausgewählt ist aus der Gruppe bestehend aus dem Mittelpunkt der größten Endkante des Elements (640) und der Projektion des MPT über der Begrenzung.

4. Das Verfahren nach Anspruch 1, wobei das Längste-Kante- Suchverfahren von Schritt c) die weiteren Schritte umfasst:

c1) Einrichten eines anfangs leeren Satzes von Endkanten, eines anfangs leeren Verarbeitungsunternetzes, und eines anfangs leeren Satzes von Verarbeitungselementen, und Hinzufügen des Elements zu dem Satz von Verarbeitungselementen (240) als ein Verarbeitungselement davon;

c2) Wählen eines Verarbeitungselements von dem Satz von Verarbeitungselementen, Hinzufügen des Verarbeitungselements zu dem Verarbeitungsunternetz (410), Erzeugen eines vergrößerten Satzes, ausgewählt aus der Gruppe bestehend aus dem Satz von Verarbeitungselementen (450), und dem Satz von Endkanten (460), und Eliminieren des Verarbeitungselements von dem Satz von Verarbeitungselementen; und

c3) Wiederholen des Schrittes c2) für jedes Element in dem Satz von Verarbeitungselementen, bis der Satz von Verarbeitungselementen leer ist.

5. Das Verfahren nach Anspruch 2, wobei das Längste-Kante- Suchverfahren von Schritt c) weiter die Schritte umfasst:

6. Das Verfahren nach Anspruch 4, wobei Schritt c2) weiter die Schritte umfasst:

c2a) Finden einer ausgewählten Kante, die eine längste Kante unter den Kanten des Verarbeitungselements (410) ist;

c2b) Finden eines Satzes von Aktivelementen (420), definiert als solche Elemente im Netz, die nicht in dem Verarbeitungsunternetz vorhanden sind, die die ausgewählte Kante als eine Kante aufweisen, und deren jeweilige längste Kante größer als die ausgewählte Kante (420) ist, und Hinzufügen jedes Elements des Satzes von Aktivelementen zu dem Satz von Verarbeitungselementen (450);

c2c) falls der Satz von Aktivelementen leer ist, Hinzufügen der ausgewählten Kante zu dem Satz von Endkanten (460).

7. Das Verfahren nach Anspruch 5, wobei der Schritt c2) weiter die Schritte umfasst:

8. Das Verfahren nach Anspruch 2, wobei das Endkantenauswahlverfahren von Schritt c) weiter die Schritte umfasst:

c4) Identifizieren eines voraussichtlichen Punktes als Mittelpunkt einer größten Kante unter den Kanten von Elementen innerhalb des Satzes von Endkanten (700);

c5) Auswählen des voraussichtlichen Punktes als einen von den ausgewählten Punkten, die in das Netz einzufügen sind, den ausgewählten Punkt in dem Objektinneren, wodurch das verbesserte Netz erstellt wird, falls der Abstand von dem voraussichtlichen Punkt zu der Objektbegrenzung größer als ein Bruchteil K der Länge der größten Kante ist, wobei K ein Parameter größer als Null (750, 770) ist;

c6) andernfalls Auswählen eines der ausgewählten Punkte, die in das Netz als ein Begrenzungspunkt einzufügen sind, der die Begrenzungspunktverteilung (780) in der Nähe eines zusätzlichen Begrenzungspunkts verbessert, wobei der zusätzliche Begrenzungspunkt gleich dem voraussichtlichen Punkt ist, wenn der voraussichtliche Punkt über der Begrenzung (740) ist, und wobei der zusätzliche Begrenzungspunkt andernfalls gleich der Projektion des voraussichtlichen Punkts über der Begrenzung (760) ist.

9. Das Verfahren nach Anspruch 1, wobei Schritt c) weiter die Schritte umfasst:

Auswählen von Mittenpunkten der zugeordneten Endkanten als die ausgewählten Punkte; und

Einfügen der ausgewählten Punkte in das Netz durch Durchführen einer Längste-Kante-Halbierung jedes Elements in dem Netz, das die zugeordnete Endkante (570) gemeinsam nutzt.

10. Das Verfahren nach Anspruch 1, zur Verwendung wenn die computerisierte Vorrichtung mindestens einen Parallelprozessor enthält, wobei der Schritt c) weiter den Schritt umfasst:

für jedes Element in dem Untersatz von Zielelementen (240) weiter ein Suchen eines zugeordneten Satzes von Endkantensätzen für das Netz, und

wobei das Verfahren von Anspruch 2 weiter den weiteren Schritt umfasst, zwischen den Schritten c) und e):

d) Erzeugen eines verfeinerten Netzes durch sukzessive parallele Verfeinerung eines Untersatzes des Satzes von Begrenzungselementsätzen (1100, 1150), wobei der Untersatz des Satzes von Endkantensätzen vollständig disjunkte Begrenzungselementesätze aufweist, und Verfeinern jedes der Begrenzungselementsätze durch:

d1) Partitionieren jedes Elements in dem Begrenzungselementsatz durch einen Mittelpunkt einer gemeinsamen längsten Kante, wobei die gemeinsame längste Kante gleich der zugeordneten Endkante (1150) ist; und

d2) lokales Aktualisieren der Netzdatenstruktur (1150, 1020, 1060, 1080); und

wobei Schritt e) weiter umfasst:

Wiederholen des Schrittes d) zusätzlich zum Schritt c) für nachfolgende Untersätze (270) von aktualisierten Sätzen von den Zielelementen, bis ein vorgegebenes Haltkriterium erreicht ist.

11. Das Verfahren nach Anspruch 2, zur Verwendung wenn die computerisierte Vorrichtung mindestens einen Parallelprozessor umfasst, wobei das Längste-Kante- Suchverfahren von Schritt c) die weiteren Schritte unter Verwendung mindestens eines Parallelprozessors zum Durchführen einer Parallelsuche umfasst:

c2) Auswählen und Zuordnen zu jedem freien des mindestens einen Parallelprozessors, ein Verarbeitungselements aus dem Satz von Verarbeitungselementen, Hinzufügen des Verarbeitungselements zu dem verarbeiteten Unternetz (410), Erzeugen eines vergrößerten Satzes ausgewählt aus der Gruppe bestehend aus dem Satz von Verarbeitungselementen (450) und dem Satz von Endkanten (460), und Eliminieren des Verarbeitungselements von dem Satz von Verarbeitungselementen; und

c3) Wiederholen des Schrittes c2) für jedes Element in dem Satz von Verarbeitungselementen, bis der Satz von Verarbeitungselementen leer ist; und

wobei der Schritt e) weiter umfasst:

Wiederholen des Schritts c) für nachfolgende Untersätze (270) von aktualisierten Sätzen der Zielelemente, bis ein vorgegebenes Haltkriterium erreicht ist.

12. Das Verfahren nach Anspruch 10, wobei das Längste-Kante- Suchverfahren von Schritt c) die weiteren Schritte umfasst, unter Verwendung des mindestens einen Parallelprozessors, zum Durchführen einer Parallelsuche:

c1) Einrichten eines anfangs leeren Satzes von Endkanten, eines anfangs leeren Verarbeitungsunternetzes und eines anfangs leeren Satzes von Verarbeitungselementen, und Hinzufügen des Elements zu dem Satz von Verarbeitungselementen (240) als ein Verarbeitungselement davon;

13. Das Verfahren nach Anspruch 12, wobei der Schritt c2) weiter die Schritte umfasst:

c2b) Finden eines Satzes von Aktivelementen (420), definiert als solche Elemente im Netz, die nicht in dem Verarbeitungsunternetz vorhanden sind, die die ausgewählte Kante als eine Kante aufweisen, und deren jeweilige längste Kante größer als die ausgewählte Kante (420) ist, und Hinzufügen jedes Elements des Satzes von Aktivelementen zu dem Satz von Verarbeitungselementen(450);

14. Das Verfahren nach Anspruch 1, weiter zum Definieren zusätzlich zum Verfeinern der Eckpunktverteilung und des Netzes von Elementen, weiter für ein Anfangsnetz, vorhergehend durch mindestens die Schritte a), c) und e) erhalten, die folgenden Schritte umfassend:

f) Zuordnen zu jedem Eckpunkt des Anfangsnetzes, einen Eckpunktindikator gleich dem nachfolgenden des Maximums zwischen den Indikatorwerten von zwei Eckpunkten V1 und V2, falls die zwei Eckpunkte eine Endkante in einem dem Anfangsnetz vorangehenden vorhergehenden Netz definieren, und falls der Eckpunkt in dem vorhergehenden Netz als ein Mittelpunkt der Endkante erhalten wurde, die eine zugeordnete Generatorkante für den Eckpunkt definiert, und andernfalls den Eckpunktindikator gleich Null;

g) Produzieren mindestens eine Zieleckpunktes, der in dem Netz (1200) zu definieren ist, und für jeden der Zieleckpunkte:

g1) Erzeugen eines Satzes von Aktivknoten (1240, 1520), wobei jeder Aktivknoten einen Eckpunkt umfasst, und einen zugeordneten Eckpunktindikator und eine zugeordnete Generatorkante;

g2) Ordnen der Knoten des Satzes von Aktivknoten in abwärts gerichteter Ordnung der Eckpunktindikatorwerte, und für Knoten mit gleichem Eckpunktindikatorwert, in aufsteigender Reihenfolge gemäß der Längen der zugeordneten Generatorkanten (1260);

g3) Vergröbern eines Satzes von Aktiveckpunkten, zugeordnet zu dem Satz von Aktivknoten, in Übereinstimmung mit der Reihenfolge der zugeordneten Aktivknoten (1600, 1650), wobei die Eckpunkte der Aktivknoten direkt mit den Eckpunkten der zugeordneten Generatorkanten verbunden sind, und lokales Aktualisieren der Zieleckpunkte; und

h) Wiederholen der Schritte g) für aktualisierte Zieleckpunkte, bis ein nutzerdefiniertes Haltkriterium erreicht ist.

15. Das Verfahren nach Anspruch 2, weiter zum Definieren zusätzlich zum Verfeinern und Verbessern der Eckpunkteverteilung und des Netzes von Elementen, die weiteren Schritte für ein Anfangsnetz, vorhergehend erhalten durch mindestens die Schritte a), b), c) und e) , umfassend:

16. Das Verfahren nach Anspruch 11, weiter zum Definieren zusätzlich zum Verfeinern und Verbessern der Eckpunktverteilung und des Netzes von Elementen, die weiteren Schritte, für ein Anfangsnetz, vorhergehend erhalten durch mindestens die Schritte a), b), c), d) und e), umfassend:

g3) paralleles Vergröbern einer Vielzahl der Aktiveckpunkte innerhalb des Satzes von Aktiveckpunkten, für Aktiveckpunkte mit vollständig disjunkten Sätzen von Nachbarelementen, gemäß der Reichenfolge der zugeordneten Aktivknoten (1600, 1650), wobei die Eckpunkte der Aktivknoten direkt mit den Eckpunkten der zugeordneten Generatorkanten verbunden sind, und lokales aktualisieren der Zieleckpunkte;

17. Ein Verfahren zum Vergröbern eines Anfangsnetzes von Elementen für ein zu analysierendes Objekt, wobei jedes Element des Anfangsnetzes eine Vielzahl von Eckpunkten und Kanten aufweist, ein Körpers des Objektes Begrenzungen und Schnittstellen umfasst, und wobei die Elemente des Anfangsnetzes Begrenzungselemente umfassen, die als solche Netzelemente definiert sind, die mindestens eine der Begrenzungen schneiden, wobei das Anfangsnetz vorhergehend durch zumindest die folgenden Schritte erlangt wurde: i) Erzeugen eines Netzes von Elementen für das Objekt (200), Identifizieren eines Satzes von Zielelementen unter den Elementen des Netzes (210) unter Verwendung von vorgegebenen Zielelement- Identifizierungskriterien, und Identifizieren eines Untersatzes des Satzes von Zielelementen unter Verwendung von vorgegebenen Zielelementuntersatz- Identifizierungskriterien; ii) für jedes Element indem Untersatz von Zielelementen (240), Suchen eines Satzes von Endkanten (40, 460) unter Verwendung eines Längste- Kante-Suchverfahrens, und Einfügen mindestens eines ausgewählten Punktes, zugeordnet mindestens einer der Endkanten, in das Netz, um ein verfeinertes Netz (240) zu erzeugen, wobei jede der Endkanten definiert ist als eine gemeinsame längste Kante jedes Netzelements, das die gemeinsame Kante teilt; und iii) Wiederholen des Schrittes ii) für nachfolgende Untersätze (270) von aktualisierten Sätzen der Zielelemente, bis ein vorgegebenes Haltkriterium erreicht ist, unter Verwendung einer computerisierten Vorrichtung, umfassend die Schritte:

a) Zuordnen zu jedem Eckpunkt des Anfangsnetzes, einen Eckpunktindikator gleich dem nachfolgenden des Maximums zwischen den Indikatorwerten von zwei Eckpunkten V1 und V2, falls die zwei Eckpunkte eine Endkante in einem dem Anfangsnetz vorangehenden vorhergehenden Netz definieren, und falls der Eckpunkt in dem vorhergehenden Netz als ein Mittelpunkt der Endkante erhalten wurde, die eine zugeordnete Generatorkante für den Eckpunkt definiert, und andernfalls den Eckpunktindikator gleich Null;

b) Produzieren mindestens eine Zieleckpunktes, der in dem Netz (1200) zu definieren ist, und für jeden der Zieleckpunkte:

b1) Erzeugen eines Satzes von Aktivknoten (1240, 1520), wobei jeder Aktivknoten einen Eckpunkt umfasst, und einen zugeordneten Eckpunktindikator und eine zugeordnete Generatorkante;

b2) Ordnen der Knoten des Satzes von Aktivknoten in abwärts gerichteter Ordnung der Eckpunktindikatorwerte, und für Knoten mit gleichem Eckpunktindikatorwert, in aufsteigender Reihenfolge gemäß der Längen der zugeordneten Generatorkanten (1260);

b3) Vergröbern eines Satzes von Aktiveckpunkten, zugeordnet dem Satz von Aktivknoten, in Übereinstimmung mit der Reihenfolge der zugeordneten Aktivknoten (1600, 1650), wobei die Eckpunkte der Aktivknoten direkt mit den Eckpunkten der zugeordneten Generatorkanten verbunden sind, und lokales Aktualisieren der Zieleckpunkte; und

c) Wiederholen der Schritte b) für aktualisierte Zieleckpunkte, bis ein nutzerdefiniertes Haltkriterium erreicht ist.

18. Das Verfahren nach Anspruch 17, zur Verwendung, wenn die computerisierte Vorrichtung mindestens einen Parallelprozessor umfasst, wobei der Schritt b3) die weiteren Schritte umfasst:

b3.1) paralleles Definieren einer Vielzahl der Aktiveckpunkte innerhalb des Satzes von Aktiveckpunkten, für aktive Eckpunkte mit vollständig disjunkten Sätzen von Nachbarelementen.

19. Das Verfahren nach Anspruch 17, wobei der Schritt b1) die weiteren Schritte umfasst:

b1.1) Initialisieren des Satzes von Aktivknoten mit einem Triplett (VX, NX, GX), wobei VX der Eckpunkt ist, NX der zugeordnete Eckpunktindikator und GX die zugeordnete Generatorkante (1400) ist;

b1.2) Initialisieren eines Satzes von Verarbeitungsknoten mit dem Triplet (VX, NX, GX) (1400);

b1.3) Wählen eines Knotens (VY, NY, GY) aus dem Satz von Verarbeitungsknoten (1420), und Auswählen eines Satzes von Nachbarknoten, wobei jeder Knoten (VZ, NZ, GZ) vom Eckpunkt VZ, vom zugeordnetem Eckpunktindikator NZ, und zugeordneter Generatorkante GZ, alle zu dem Satz von Nachbarknoten hinzugefügt werden, wenn mindestens eine Bedingung aus der Gruppe der folgenden Bedingungen (1460, 1480, 1500) erfüllt ist:

die Kante von Eckpunkten VZ, VY existiert in dem Netz und NZ > NY; und

die Kante von Eckpunkten VZ, VY existiert in dem Netz und NZ = NY, und GZ < GY;

b1.4) Hinzufügen jedes ausgewählten Nachbarknotens zu dem Satz von Verarbeitungsknoten und Hinzufügen jedes ausgewählten Nachbarknotens zu dem Satz von Aktivknoten (1520);

b1.5) Wiederholen der Schritte b1.3) und b1.4) bis der Satz von Verarbeitungsknoten leer ist und der Satz von Aktivknoten vervollständigt ist (1540).

20. Das Verfahren nach Anspruch 18, wobei der Schritt b1) die weiteren Schritte umfasst:

b1.2) Initialisieren eines Satzes von Verarbeitungsknoten mit dem Triplett (VX, NX, GX) (1400)

die Kante von Eckpunkten VZ, VY existiert in dem Netz und NZ > NY; und

die Kante von Eckpunkten VZ, VY existiert in dem Netz und NZ = NY, und GZ < GY;

21. Das Verfahren nach Anspruch 17, wobei der Schritt b3), für jeden Aktiveckpunkt in dem Satz von Aktiveckpunkten weiter die Schritte umfasst:

b3.1) Eliminieren aus dem Netz: den Aktiveckpunkt, jede Kante, die den Aktiveckpunkt enthält, und jedes der Netzelemente, die den Aktiveckpunkt (1750) enthält; und

b3.2) Addieren zu dem Netz: eine neue Kante gleich der Generatorkante des Eckpunkts, und neuer Elemente umfassend jedes Element, das die Kante (1750) teilt.

22. Das Verfahren nach Anspruch 18, wobei der Schritt b3) für jeden Aktiveckpunkt in dem Satz von Aktiveckpunkten weiter die Schritte umfasst:

23. Ein Verfahren zum Darstellen einer Datenstruktur zum Verfeinern von sowohl einer Eckpunktverteilung als auch eines Netzes von Elementen eines zu analysierenden Objektes, wobei jedes Element des Netzes eine Vielzahl von Eckpunkten und Kanten aufweist, ein Körper des Objektes Begrenzungen und Schnittstellen aufweist, und die Elemente des Netzes Begrenzungselemente umfassen, die als solche Netzelemente definiert sind, die mindestens eine der Begrenzungen schneiden, wobei das Netz verfeinert wird durch mindestens die folgenden Schritte: i) Erzeugen eines Netzes von Elementen für das Objekt (200), Identifizieren eines Satzes von Zielelementen unter den Elementen des Netzes (210) unter Verwendung von vorgegebenen Zielelement- Identifizierungskriterien, und Identifizieren eines Untersatzes des Satzes von Zielelementen unter Verwendung von vorgegebenen Zielelementuntersatz- Identifizierungskriterien; ii) für jedes Element in dem Untersatz von Zielelementen (240), Suchen eines Satzes von Endkanten (40, 460) unter Verwendung eines Längste- Kante-Suchverfahrens, und Einfügen mindestens eines ausgewählten Punktes, zugeordnet mindestens einer der Endkanten, in das Netz, um ein verfeinertes Netz (240) zu erzeugen, wobei jede der Endkanten definiert ist als eine gemeinsame längste Kante jedes Netzelements, das die gemeinsame Kante teilt; und iii) Wiederholen des Schritts ii) für nachfolgende Untersätze (270) von aktualisierten Sätzen der Zielelemente, bis ein vorgegebenes Haltkriterium erreicht ist; wobei die Datenstruktur ein Längste-Kanten-Verhältnis repräsentiert, das zwischen Nachbarelementen in dem Netz von Elementen besteht, nutzbar zum Suchen von Sätzen von Endkanten in dem Netz, wobei jede Endkante als eine gemeinsame längste Kante von einem jeden Netzelement definiert ist, die die Endkante teilt, wobei die Datenstruktur weiter Kanten-, Element- und Eckpunktdarstellungen enthält, und wobei jedes Element des Netzes eine Vielzahl von Eckpunkten und Kanten aufweist, unter Verwendung einer computerisierten Vorrichtung, wobei:

a) die Kantendarstellung für jede repräsentierte Kante, die eine Kante des Netzes (800) ist, umfasst:

a1) Pointer der zwei Eckpunkte der Kante in der Eckpunktdarstellung;

a2) einen Satz von Pointern zu Nachbarelementen in der Elementdarstellung, wobei jedes Nachbarelement die repräsentierte Kante als eine dessen Kanten aufweist, und eine längste Kante aufweist, die größer als die repräsentierte Kante ist; und

b) wobei die Elementrepräsentation für jedes der Elemente (820) umfasst:

b1) einen Pointer zu einer längsten Kante des Elements in der Kantendarstellung.

24. Das Verfahren nach Anspruch 23, umfassend die weiteren Schritte:

Initialisieren der Datenstruktur (910, 920, 940) für ein Anfangsnetz durch Erzeugen der Kanten-, Eckpunkt- und Elementdarstellungen;

Verwenden der Datenstruktur zum Suchen von Sätzen von Endkanten in dem Netz, zugeordnet Zielelementen, die im Netz (460) verfeinert sind; und

Aktualisieren der Datenstruktur nach einem Einfügen jedes ausgewählten Punkts, ausgewählt als Mittelpunkt einer der Endkanten im Netz (1000, 1020, 1040).

25. Das Verfahren nach Anspruch 23, weiter verwendet zum Definieren der Eckpunktverteilung und dem Netz von Elementen für das zu analysierende Objekt, wobei die Datenstruktur weiter ein Vorrangsverhältnis zwischen Nachbareckpunkten im Netz darstellt, wobei die Datenstruktur weiter eine Generatorkantendarstellung umfasst, und das Netz vorhergehend unter Verwendung der computerisierten Vorrichtung verfeinert wurde, wobei weiter:

c) die Eckpunktdarstellung für jeden Eckpunkt des Netzes (840) umfasst:

c1) einen Integerindikator, wobei der Indikator gleich Null ist, wenn der Eckpunkt nicht als Mittelpunkt einer Endkante in einem vorhergehenden Netz erhalten wurde; andernfalls ist der Indikator gleich dem nachfolgenden des Maximalwertes zwischen den Indikatorwerten von zwei Eckpunkten V1 und V2, wobei die Eckpunkte V1 und V2 eine Endkante in einem vorhergehenden Netz definieren, und wobei die Endkante als die Generatorkante des Eckpunktes definiert ist;

c2) einen Pointer zu der Generatorkante für den Eckpunkt in der Generatorkantendarstellung; und

d) wobei die Generatorkantendarstellung für jede Generatorkante davon (800) umfasst:

d1) Pointer zu zwei Eckpunkten, die die Generatorkante in der Eckpunktdarstellung definieren.

26. Das Verfahren nach Anspruch 25, weiter die Schritte umfassend:

Initialisieren der Datenstruktur für ein Anfangsnetz durch Erzeugen der Kanten-, Eckpunkt-, Element- und Generatorkantendarstellungen (910, 920, 940); und

Verwenden der Datenstruktur zum Durchführen einer Netzvergröberung basierend auf einer Endkantenvergröberung; Aktualisieren der Datenstruktur nach einer Netzvergröberung (1000, 1020,1060, 1080).

27. Eine computerisierte Vorrichtung zum Verfeinern sowohl einer Eckpunktverteilung als auch eines Netzes von Elementen für ein zu analysierendes Objekt, wobei jedes Element des Netzes eine Vielzahl von Eckpunkten und Kanten aufweist, ein Körper des Objektes Begrenzungen und Schnittstellen umfasst, und die Elemente des Netzes Begrenzungselemente umfassen, die als solche Netzelemente definiert sind, die mindestens eine der Begrenzungen schneiden, umfassend Bearbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungsbereitstellungsmittel zum:

28. Die computerisierte Vorrichtung nach Anspruch 27, weiter zum Verbessern zusätzlich zum Verfeinern der Eckpunktverteilung und des Netzes von Elementen, wobei die Verarbeitung -, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, zwischen den Schritten a) und c) zum:

und als Teil von Schritt c):

und als Teil von Schritt e):

Wiederholen des Schritts b) zusätzlich zum Schritt c) für nachfolgende Untersätze (270) von aktualisierten Sätzen von den Zielelementen, bis ein vorgegebenes Haltkriterium erreicht ist.

29. Die computerisierte Vorrichtung von Anspruch 28; wobei die Begrenzungselemente als Elemente des Netzes definiert sind, die mindestens eins der folgenden Kriterien erfüllen: Aufweisen mindestens eines Eckpunkts über den Objektbegrenzungen; Schneiden der Objektbegrenzung; und Schneiden der Objektschnittstelle;

wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als Teil des Längste-Kanten-Begrenzungsauswahlverfahrens von Schritt b), für jedes Begrenzungselement in dem Untersatz von Zielelementen (610):

b4) andernfalls, Identifizieren eines ausgewählten Punktes (650) als einen von den Begrenzungspunkten, die die Begrenzungspunktverteilung in der Nähe eines zusätzlichen Begrenzungspunktes verbessern, und Einfügen des ausgewählten Punktes in das Netz (650), wobei der zusätzliche Begrenzungspunkt ausgewählt ist aus der Gruppe bestehend aus dem Mittelpunkt der größten Endkante des Elements (640) und der Projektion des MPT über der Begrenzung.

30. Die computerisierte Vorrichtung von Anspruch 27, wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als Teil des Längste-Kante-Suchverfahrens von Schritt c), zum:

31. Die computerisierte Vorrichtung von Anspruch 28, wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als Teil des Längste-Kante-Suchverfahrens von Schritt c), zum:

c2) Wählen eines Verarbeitungselements von dem Satz von Verarbeitungselementen, Hinzufügen des Verarbeitungselements zu dem Verarbeitungsunternetz (410), Erzeugen eines vergrößerten Satzes, ausgewählt aus der Gruppe bestehend aus dem Satz von Verarbeitungselementen (450), und dem Satz von Endkanten (460), und Eliminieren des Verarbeitungselements von dem. Satz von Verarbeitungselementen; und

32. Die computerisierte Vorrichtung nach Anspruch 30, wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als Teil von Schritt c2), zum:

33. Die computerisierte Vorrichtung von Anspruch 31, wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als Teil von Schritt c2), zum:

c2a) Finden einer ausgewählten Kante, die eine längste Kante unter den Kantendes Verarbeitungselements (410) ist;

34. Die computerisierte Vorrichtung von Anspruch 28, wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als Teil des Endkantenauswahlverfahrens von. Schritt c), zum:

c4) Identifizieren eines voraussichtlichen Punktes als Mittelpunkt einer größten Kante unter den Kanten von Elementen innerhalb des Satzes von Endkanten (700)

35. Die computerisierte Vorrichtung von Anspruch 27, wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als Teil von Schritt c), zum:

36. Die computerisierte Vorrichtung von Anspruch 27, wobei die Verarbeitungsvorrichtung davon mindestens einen Parallelprozessor umfasst, die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als Teil von Schritt c), zum:

für jedes Element in dem Untersatz von Zielelementen (240), weiter Suchen nach einem zugeordneten Satz von Endkantensätzen für das Netz, und

zwischen den Schritten c) und e):

d) Erzeugen eines verfeinerten Netzes durch sukzessive parallele Verfeinerung eines Untersatzes des Satzes von Begrenzungselementsätzen (1100, 1150), wobei der Untersatz des Satzes von Endkantensätzen vollständig disjunkte Begrenztzngselementesätze aufweist, und Verfeinern jedes der Begrenzungselementsätze durch:

d2) lokales Aktualisieren der Netzdatenstruktur (1150, 1020, 1060, 1080); und

als Teil von Schritt e):

Wiederholen des Schrittes d) zusätzlich zum Schritt c) für nachfolgende Untersätze (270) von aktualisierten Sätzen der Zielelemente, bis ein vorgegebenes Haltkriterium erreicht ist.

37. Die computerisierte Vorrichtung von Anspruch 28, wobei die Verarbeitungsvorrichtung davon mindestens einen Parallelprozessor umfasst, die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als Teil des Längste-Kanten-Auswahlverfahrens von Schritt c), zum Durchführen einer Parallelsuche durch:

als Teil von Schritt e):

38. Die computerisierte Vorrichtung von Anspruch 36, wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als Teil des Längste-Kante-Auswahlverfahrens von Schritt c), zum Durchführen einer Parallelsuche durch:

39. Die computerisierte Vorrichtung von Anspruch 38, wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als Teil des Längste-Kante-Auswahlverfahrens von Schritt c2):

40. Die computerisierte Vorrichtung von Anspruch 27, weiter zum Vergröbern zusätzlich zum Verfeinern der Eckpunktverteilung und des Netzes von Elementen, wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, für ein Anfangsnetz, vorhergehend durch mindestens die Schritte a), c) und e) erhalten, zum:

g) Produzieren mindestens eine Zieleckpunktes, der in dem Netz (1200) zu definieren, ist, und für jeden der Zieleckpunkte:

41. Die computerisierte Vorrichtung von Anspruch 28, weiter zum Vergröbern zusätzlich zum Verfeinern und Verbessern der Eckpunktverteilung des Netzes von Elementen, wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, für ein Anfangsnetz, vorhergehend durch mindestens die Schritte a) , b), c) und e) erhalten, zum:

42. Die computerisierte Vorrichtung von Anspruch 37, weiter für ein Vergröbern zusätzlich zum Verfeinern und Verbessern der Eckpunktverteilung und des Netzes von Elementen, wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, für ein Anfangsnetz, vorhergehend erhalten durch mindestens die Schritte a), b), c), d) und e), zum:

g3) parallelen Definieren einer Vielzahl von aktiven Eckpunkten innerhalb des Satzes von Aktiveckpunkten, für Aktiveckpunkte mit vollständig disjunkten Sätzen von Nachbarelementen, in Übereinstimmung mit der Reihenfolge der zugeordneten Aktivknoten (1600, 1650), wobei die Eckpunkte der Aktivknoten direkt mit den Eckpunkten der zugeordneten Generatorkanten verbunden sind, und lokales Aktualisieren der Zieleckpunkte; und

43. Eine computerisierte Vorrichtung zum Vergröbern eines Anfangsnetzes von Elementen für ein zu analysierendes Objekt, wobei jedes Element des Anfangsnetzes eine Vielzahl von Eckpunkten und Kanten aufweist, ein Körper des Objektes Begrenzungen und Schnittstellen umfasst, und die Elemente des Anfangsnetzes Begrenzungselemente umfassen, die als solche Netzelemente definiert sind, die mindestens eine der Begrenzungen schneiden, wobei das Anfangsnetz vorhergehend durch mindestens die Schritte erlangt wurde: i) Erzeugen eines Netzes von Elementen für das Objekt (200), Identifizieren eines Satzes von Zielelementen unter den Elementen des Netzes (210) unter Verwendung von vorgegebenen Zielelement- Identifizierungskriterien, und Identifizieren eines Untersatzes des Satzes von Zielelementen unter Verwendung von vorgegebenen Zielelementuntersatz- Identifizierungskriterien; ii) für jedes Element in dem Untersatz von Zielelementen (240), Suchen eines Satzes von Endkanten (40, 460) unter Verwendung eines Längste- Kante-Suchverfahrens, und Einfügen mindestens eines ausgewählten Punktes, zugeordnet mindestens einer der Endkanten, in das Netz, um ein verfeinertes Netz (240) zu erzeugen, wobei jede der Endkanten definiert ist als eine gemeinsame längste Kante jedes Netzelements, das die gemeinsame Kante teilt; und iii) Wiederholen des Schrittes ii) für nachfolgende Untersätze (270) von zugeordneten Sätzen von Zielelementen, bis ein vorgegebenes Haltkriterium erreicht ist; umfassend Verarbeitungs-, Eingabe-, Ausgabe- und Speicherelemente, die Mittel bereitstellen zum:

44. Die computerisierte Vorrichtung von Anspruch 43, wobei die Verarbeitungsvorrichtung davon mindestens einen Parallelprozessor umfasst, die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als ein Teil des Schrittes b3), zum:

45. Die computerisierte Vorrichtung von Anspruch 43, wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als Teil von Schritt b1), zum:

b1.2) Initialisieren eines Satzes von Verarbeitungsknoten mit dem Triplett (VX, NX, GX) (1400);

die Kante von Eckpunkten VZ, VY existiert in dem Netz und NZ > NY; und

die Kante von Eckpunkten VZ, VY existiert in dem Netz und NZ = NY, und GZ < GY;

46. Die computerisierte Vorrichtung von Anspruch 44, wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als Teil von Schritt b1), zum:

b1.3) Wählen eines Knotens (VY, NY, GY) aus dem Satz von Verarbeitungsknoten (1420), und Auswählen eines Satzes von Nachbarknoten, wobei jeder Knoten (VZ, NZ, GZ) vorn Eckpunkt VZ, vom zugeordnetem Eckpunktindikator NZ, und zugeordneter Generatorkante GZ, alle zu dem Satz von Nachbarknoten hinzugefügt werden, wenn mindestens eine Bedingung aus der Gruppe der folgenden Bedingungen (1460, 1480, 1501) erfüllt ist:

die Kante von Eckpunkten VZ, VY existiert in dem Netz und NZ > NY; und

die Kante von Eckpunkten VZ, VY existiert in dem Netz und NZ = NY, und GZ < GY;

47. Die computerisierte Vorrichtung von Anspruch 43, wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als Teil von Schritt b3), für jeden Aktiveckpunkt des Satzes von Aktiveckpunkten:

48. Die computerisierte Vorrichtung von Anspruch 43, wobei die Verarbeitungs-, Eingabe-, Ausgabe- und Speichervorrichtungen weiter Mittel umfassen, als Teil von Schritt b3), für jeden Aktiveckpunkt des Satzes von Aktiveckpunkten, zum:

49. Eine computerisierte Vorrichtung zum Speichern und Verarbeiten einer Datenstruktur, zum Verfeinern sowohl einer Eckpunktverteilung als auch eines Netzes von Elementen für ein zu analysierendes Objekt, wobei jedes Element des Netzes eine Vielzahl von Eckpunkten und Kanten aufweist, ein Körper des Objektes Begrenzungen und Schnittstellen aufweist, und die Elemente des Netzes Begrenzungselemente umfassen, die als solche Netzelemente definiert sind, die mindestens eine der Begrenzungen schneiden, wobei das Netz verfeinert wird durch mindestens die folgenden Schritte: i) Erzeugen eines Netzes von Elementen für das Objekt (200), Identifizieren eines Satzes von Zielelementen unter den Elementen des Netzes (210) unter Verwendung von vorgegebenen Zielelement-Identifizierungskriterien, und Identifizieren eines Untersatzes des Satzes von Zielelementen unter Verwendung von vorgegebenen Zielelementuntersatz-Identifizierungskriterien; ii) für jedes Element in dem Untersatz von Zielelementen (240), Suchen eines Satzes von Endkanten (40, 460) unter Verwendung eines Längste-Kante-Suchverfahrens, und Einfügen mindestens eines ausgewählten Punktes, zugeordnet mindestens einer der Endkanten, in das Netz, um ein verfeinertes Netz (240) zu erzeugen, wobei jede der Endkanten definiert ist als eine gemeinsame längste Kante jedes Netzelements, das die gemeinsame Kante teilt; und iii) Wiederholen des Schritts ii) für nachfolgende Untersätze (270) von aktualisierten Sätzen der Zielelemente, bis ein vorgegebenes Haltkriterium erreicht ist; wobei die Datenstruktur ein Längste- Kanten-Verhältnis repräsentiert, das zwischen Nachbarelementen in dem Netz von Elementen besteht, nutzbar zum Suchen von Sätzen von Endkanten in dem Netz, wobei jede Endkante als eine gemeinsame längste Kante von einem jeden Netzelement definiert ist, die die Endkante teilt, wobei die Datenstruktur weiter Kanten-, Element- und Eckpunktdarstellungen enthält, und wobei jedes Element des Netzes eine Vielzahl von Eckpunkten und Kanten aufweist, wobei:

a1) Pointer der zwei Eckpunkte der Kante in der Eckpunktdarstellung;

b) wobei die Elementrepräsentation für jedes der Elemente (820) umfasst:

50. Die computerisierte Vorrichtung von Anspruch 49, weiter Mittel umfassend zum:

51. Die computerisierte Vorrichtung von Anspruch 49, weiter verwendet zum Definieren der Eckpunktverteilung und dem Netz von Elementen für das zu analysierende Objekt, wobei die Datenstruktur weiter ein Vorrangsverhältnis zwischen Nachbareckpunkten im Netz darstellt, wobei die Datenstruktur weiter eine Generatorkantendarstellung umfasst, und das Netz vorhergehend unter Verwendung der computerisierten Vorrichtung verfeinert wurde, wobei weiter:

c) die Eckpunktdarstellung für jeden Eckpunkt des Netzes (840) umfasst:

52. Die computerisierte Vorrichtung nach Anspruch 51, weiter Mittel umfassend zum:

Verwenden der Datenstruktur zum Durchführen einer Netzvergröberung basierend auf einer Endkantenvergröberung; Aktualisieren der Datenstruktur nach einer Netzvergröberung (1000, 1020, 1060, 1080).