Die Erfindung betrifft ein Verfahren, ein Computerprogrammprodukt und eine

Computervorrichtung zum Auswerten volumetrischer Subdivisionsmodelle.

Technische Systeme, Baugruppen, Werkstücke oder allgemeine Objekte müssen oftmals hinsichtlich ihrer Eigenschaften oder ihres Verhaltens überprüft werden. Neben realen Versuchen hat sich hierfür die computergestützte Simulation als ein gängiges Mittel etabliert. Voraussetzung einer aussagekräftigen Simulation ist, dass ein Objekt möglichst genau modelliert wird.

Typischerweise wird in einer sogenannten Designphase zunächst mittels

softwarebasierter CAD-Anwendungen [Computer-Aided Design] ein virtuelles 3D-Modell eines Objekts erstellt. Anschließend wird dieses Modell in einer Simulationsphase dahingehend untersucht, wie sich z.B. einwirkende Kräfte, Temperaturen oder andere Einflüsse auswirken, wozu in der Regel numerische Simulationsansätze verwendet werden. Die Simulationsphase kann auch als CAE [Computer-Aided Engineering] bezeichnet werden.

Um den Entwicklungsprozess zu beschleunigen, müssen Informationen bezüglich der (insbesondere geometrischen) Eigenschaften des Produkts, wie sie am Ende der Designphase vorliegen, in einer solchen Form bereitgestellt werden, dass sie mittels einer Simulationsumgebung (zum Beispiel in Form eines Computerprogrammprodukts) möglichst ohne umfassende Umformatierungen, Umwandlungen oder zusätzliche

Anpassungen simuliert werden können. Im gängigen CAD-CAE-Workflow steht am Übergang zwischen Design und Simulation in der Regel die Konvertierung der kontinuierlichen CAD-Repräsentation in eine CAE- bzw. simulationskompatible, diskrete Geometrie (z.B. in Form diskreter finiter Elemente). Diese Konvertierung wird auch als „Diskretisierung“ oder„Meshing“ bezeichnet. Einerseits ist dieser Schritt zeitaufwändig und oft mit manuellen Eingriffen und Fehlerbehandlungen versehen. Andererseits gehen dabei unwiederbringlich Informationen der CAD-Geometrie verloren. Eine Umwandlung in die entgegengesetzte Richtung, um zum Beispiel automatisiert Schlussfolgerungen aus den Simulationsergebnissen zu ziehen, ist mit den aktuellen Ansätzen in der Regel ebenfalls nicht möglich.

In aktuell am Markt befindlichen Simulationssystemen wird die oben genannte

Konvertierung durchgeführt, um ein simulationskompatibles Modell zu erzeugen. Die Simulation wird dabei oftmals mit der Finiten Elemente Methode (FEM) durchgeführt. Neben linearen finiten Elementen kommen teilweise auch Elemente mit quadratischer oder kubischer Ordnung zum Einsatz, die vergleichbare Ergebnisse bei weniger

Freiheitsgraden erreichen (sh. z.B. Daniel Weber, Johannes Mueller-Roemer, Christian Altenhofen, Andre Stork und Dieter Fellner: Deformation Simulation using cubic finite elements and efficient p-multigrid methods, Computers & Graphics 53 (2015), 185-195). Wissenschaftliche Arbeiten zur Simulation auf kontinuierlichen Repräsentationsformen haben sich bisher meistens auf Darstellungen mit trivariater NURBS-Geometrie beschränkt und lassen sich unter dem Begriff„Iso-Geometrische Analyse - IGA“ zusammenfassen (sh. z. B. Thomas JR Hughes, John A Cottrell und Yuri Bazilevs:

Isogeometric analysis: CAD, finite elements, NURBS, exact geometry and mesh refinement, Computer methods in applied mechanics and engineering 194, 39 (2005), 4135-4195). Des Weiteren existieren wissenschaftliche Arbeiten zur Simulation von dünnwandigen Objekten (sog.„Shells“) direkt auf Limit-Oberflächen durch kontinuierliche Facettenzerlegung (siehe Fehmi Cirak, Michael J Scott, Erik K Antonsson, Michael Ortiz und Peter Schröder: Integrated modeling, finite-element analysis, and engineering design for thin-shell structures using subdivision, Computer-Aided Design 34, 2 (2002), 137-148 & A. Riffnaller-Schiefer, U.H. Augsdörfer und D.W. Fellner: Isogeometric Shell analysis with NURBS compatible subdivision surfaces Appl. Math. Comput. 272, Part 1 (2016), 139 - 147). Andere Verfahren nutzen die der hier vorgestellten Erfindung zu Grunde liegende Zellzerlegung bzw. Subdivision für eine diskrete Simulation mittels der finiten Elemente Methode (Christian Altenhofen, Felix Schuwirth, Andre Stork und Dieter Fellner:

Volumetrie subdivision for consistent implicit mesh generation Computers & Graphics 69, Supplement C (2017), 68 - 79).

Zu unterscheiden ist ferner zwischen Modellen, die sich auf eine reine

Oberflächenbeschreibung beschränken, und Modellen, die auch Volumenanteile berücksichtigen bzw. eine volumetrische Repräsentation zugrunde legen. Die Erfindung betrifft insbesondere die letzte Variante. Ein Vorteil der Subdivision bzw. Zellzerlegung ist die Vermeidung von Informationsverlust zwischen einem CAD-Modell und einem für die Simulation verwendeten Modell. Oftmals kann sogar die gleiche Objektbeschreibung (bzw. das gleiche diskrete Kontrollpunktnetz) beiden Modellen zugrunde gelegt werden, beispielsweise wenn die CAD-Modelle ebenfalls als volumetrisches Subdivisionsmodell erzeugt werden. Mit den bisher bekannten Modellierungs- und Simulationsansätzen ist dies hingegen nicht immer möglich. Im Rahmen der vorliegenden Offenbarung werden Kontrollpunktnetze allgemein auch als Kontrollnetze bezeichnet.

Im Detail geht die hier vorgestellte Erfindung von einer Subdivision aus, die auch als eine Unterteilung und/oder Zellzerlegung bezeichnet werden kann. Bei der Subdivision wird ein Ausgangsvolumenmodell und/oder ein Ausgangs-Kontrollpunktnetz gemäß

vorbestimmten Regeln weiter unterteilt, insbesondere derart, dass das resultierende Kontrollpunktnetz sukzessive weiter verfeinert wird. Theoretisch kann hierdurch ein sogenanntes Limit-Volumen erreicht werden, welches die größtmögliche Verfeinerung darstellt. Da das Durchführen einer solchen maximalen Limit-Verfeinerung rechnerisch aufwendig ist, wird stattdessen eine direkte mathematische Auswertung des Limits bevorzugt, also ein mathematisches Berechnen und Auswerten von Punkten des Limit- Volumens, ohne das Limit-Volumen tatsächlich vollständig bilden zu müssen. Ein Beispiel eines hierfür verwendbaren Algorithmus ist der Catmull-Clark-Algorithmus für Volumen (Catmull Clark Solids), dessen Regeln zum Beispiel in der folgenden wissenschaftlichen Arbeit zusammengefasst sind, die nachstehend auch mit„Burkhart et al.“ referenziert wird: Daniel Burkhart, Bernd Hamann und Georg Umlauf: Iso-geometric Finite Element Analysis Based on Catmull-Clark: Subdivision Solids In Computer Graphics Forum, Vol. 29. Wiley Online Library, 1575-1584. Ebenfalls wird verwiesen auf folgende

wissenschaftliche Arbeit: The refinement rules for Catmull-Clark solids, Kl Joy, R

MacCracken, Citeseer, 1999.

Der Catmull-Clark-Algorithmus sieht allgemein vor, basierend auf einem Ausgangsnetz aus mittels Kanten verbundener Kontrollpunkte ein verfeinertes Netz zu berechnen, wobei in jedem Unterteilungsschritt neue Kontrollpunkte bestimmt werden, welche das Netz in kleinflächigere (oder im dreidimensionalen Fall kleinvolumetrigere) Zellen unterteilen. Ein Problem bei derartigen Subdivisionsmodellen besteht oftmals dahingehend, dass diese die Form eines Objektvolumens (oder auch lediglich der Objektoberfläche) über ein Gitter aus Kontrollpunkten lediglich annähern. Insbesondere können die einzelnen Kontrollpunkte als sogenannte Knotenpunkte oder Steuerknoten von die Objektform und insbesondere Oberflächenform beschreibenden Funktionen definiert sein (zum Beispiel von B-Spline-Funktionen). Möchte man daher einen bestimmten Ort des Objekts z.B. auf dessen Oberfläche oder in dessen Volumen auswerten (d. h. diesen Ort im Rahmen einer Simulation untersuchen und beispielsweise die dort entstehenden Verschiebungen und/oder Kräfte oder auch andere Eigenschaften bestimmen und/oder die Limit-Position und den Gradienten dieses Punktes bestimmen), kann man daher nicht immer unmittelbar auf einen der Kontrollpunkte des Subdivisionsmodells zurückgreifen. Dieses Problem verdeutlicht sich beispielhaft aus der beigefügten Figur 1 , in der für einen

zweidimensionalen Fall eine Zelle eines Subdivisionsmodells aus vier Kontrollpunkten 100 gezeigt ist. Diese beschreiben eine kreisförmige Objektform 102 mittels über die

Kontrollpunkte 100 definierter B-Spline-Funktionen, ohne aber selbst Bestandteil des Objekts 102 zu sein oder innerhalb von dessen Fläche zu liegen.

Dieses Problem wird insbesondere in der folgenden wissenschaftlichen Arbeit behandelt: Jos Stam: Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values, In Proceedings of the 25th annual Conference on Computergraphics and

Interactive techniques ACM (1998), 395^104. Die dort dargelegten Überlegungen und Lösungsvorschläge sind auch in der DE 699 15 837 T2 zusammengefasst, die

wesentliche Grundgedanken und Berechnungsansätze enthält, auf denen auch die vorliegende Offenbarung aufbaut. Der Inhalt der DE 699 15 837 T2 und auch von dessen US-Äquivalent US 6 389 154 B1 werden daher vollumfänglich per Bezugnahme in die vorliegende Offenbarung aufgenommen. Ein Unterschied zwischen diesen Lehren und der vorliegenden Offenbarung liegt jedoch dahingehend vor, dass dort lediglich

Oberflächenmodelle im dreidimensionalen Raum betrachtet werden, wohingegen sich die vorliegende Offenbarung auf dreidimensionale d.h. volumetrische Fälle richtet, bei denen Kontrollpunktnetze mit Zellen betrachtet werden, die miteinander verbunden sind und das Volumen definieren.

In der DE 699 15 837 T2 wird das Problem des direkten Auswertens eines beliebigen Ortes im Subdivisionsmodell derart beschrieben, dass die Koordinaten der Kontrollpunkte eines Subdivisionsmodells B-Spline-Basisfunktionen definieren können, um die Kontur einzelner Flächenstücke innerhalb eines zweidimensionalen (Flächen-) Modells eines Objekts zu beschreiben. Die Kontrollpunkte können dabei über allgemeine

Raumkoordinaten definiert sein (zum Beispiel als X-, Y-und Z-Werte). Da die

Kontrollpunkte aber, wie vorstehend gezeigt, nicht immer mit tatsächlichen Orten innerhalb des Flächenstücks übereinstimmen, wird ein weiterer Parametersatz herangezogen, der tatsächlich Orte innerhalb des Flächenstücks beschreibt bzw. in einem entsprechenden Koordinatensystem des Flächenstücks definiert ist. Im

zweidimensionalen Fall wird hierfür ein sogenanntes u-v-Koordinatensystem bzw. ein u-v- Parametersatz definiert.

Mittels der B-Spline-Basisfunktionen, die das Flächenstück selbst beschreiben, können die u-v-Parameter in dreidimensionale Ortskoordinaten im Raum übersetzt werden. Mit anderen Worten können für einen mittels u-v-Parametern im Flächenstück definierten Ort anhand der Basisfunktionen die korrespondierenden X-, Y-und Z-Werte ermittelt werden. Allgemein ausgedrückt wird somit ein Zusammenhang zwischen den Parametern für die Orte im Raum und der Flächenstückdefinition durch die B-Spline-Basisfunktionen definiert, um schlussendlich die Koordinaten beliebiger Objektorte in einem vorzugsweise gewöhnlichen kartesischen Raumkoordinatensystem angeben zu können (zum Beispiel in einem gewöhnlichen X-, Y-und Z-Koordinatensystem). Wie nachstehend erläutert, können die Basisfunktionen aber nicht nur lediglich die Objektform, sondern auch

Objekteigenschaften, wie zum Beispiel eine Materialdichte oder eine Materialart definieren. Folglich können mittels der geschilderten Parametrisierung auch konkrete Eigenschaften eines vorgegebenen u-v-Ortes anhand der Basisfunktionen bestimmt werden.

Wenn jeder Objektort mathematisch eindeutig definiert ist und/oder dessen Koordinaten (vorzugsweise in Form von X-Y-Z-Raumkoordinaten) sowie Gradient (Ableitung der Koordinate nach u und v bei Flächen, bzw. nach u, v, w bei Subdivisionsvolumen) oder Eigenschaften mittels der B-Spline-Basisfunktionen des Subdivisionsmodells bestimmt werden können, kann dieses Modell an jedem beliebigen Ort ausgewertet werden. Es wird verwiesen auf die Schilderung des entsprechenden als Parametrisierung

bezeichneten Vorgehens in der DE 699 15 837 T2 zum Beispiel im Zusammenhang mit der dortigen Figur 4. Auch im Rahmen der vorliegenden Offenbarung kann das Auswerten eines Ortes im Subdivisionsmodell die vorstehend geschilderten bzw. Parametrisierungen umfassen.

Eine nachfolgend noch näher erläuterte Gleichung, die zum Auswerten eines beliebigen Ortes p, der ein Ort auf der Limit-Oberfläche ist und daher auch als Limit-Ort oder Limit- Punkt bezeichnet werden kann, mit den Parametern u, v verwendet wird, kann im zweidimensionalen Fall wie folgt formuliert werden:

Dabei enthält die Matrix C Kontrollpunkte eines betrachteten Oberflächen-Elements und die Matrix die Koeffizienten der bikubischen B-Spline-Basisfunktionen an den

entsprechenden Kontrollpunkten. Im dreidimensionalen Fall würde diese Gleichung um eine weitere Dimension w erweitert werden.

Wie ferner ausführlich in der DE 699 15 837 T2 dargelegt, ist die Auswertung an beliebigen Orten aber nur dann mit geringem Aufwand möglich, wenn der entsprechende Ort in einem Flächenstück liegt, das einen sogenannten regulären Satz von

Kontrollpunkten umfasst. Insbesondere handelt es sich dabei um ein Flächenstück, das durch ein Netz aus 4 x 4 Kontrollpunkte aufgespannt wird und lediglich reguläre

Kontrollpunkte enthält (d.h. die Kontrollpunkte innerhalb des Netzes müssen regulär sein, wohingegen Kontrollpunkte auf den Rändern oder auch Außenkanten des Netzes nicht zwingend regulär sein müssen). Ein Kontrollpunkt wird als regulär bezeichnet, wenn dieser eine Valenz (oder auch einen Grad oder Knotengrad) von vier aufweist. Die Valenz entspricht der Anzahl an Kanten, die von einem Kontrollpunkt ausgehen bzw. an diesem Zusammentreffen.

Werden hingegen Flächenstücke betrachtet, die Kontrollpunkte mit einer von vier verschiedenen Valenz enthalten (d. h. der Kontrollpunkt mit einer von 4 verschiedenen Valenz liegt im Flächenstück und nicht an oder auf dessen Rand und ist somit im

Flächenstück enthalten), können die Koordinaten eines beliebigen Ortes innerhalb dieses Flächenstücks nicht mittels der vorstehend erläuterten Parametrisierung bzw. dem Satz von Basisfunktionen bestimmt werden. Derartige Kontrollpunkte werden allgemein als irregulär, außerordentlich oder extraordinär bezeichnet und können auf das Ausgangsnetz zurückzuführen sein, das zum Beispiel von einem Bediener zur Objektformbeschreibung definiert wurde. In derartigen Ausgangsnetzen ist es für eine genaue Formbeschreibung nicht immer möglich, irreguläre Kontrollpunkte von vornherein zu vermeiden. In der DE 699 15 837 T2 werden deshalb Ansätze vorgeschlagen, um das Auswerten beliebiger Orte auch innerhalb nicht regulärer Flächenstücke zu ermöglichen. Wie erwähnt, beschränken sich diese Ansätze allerdings rein auf den zweidimensionalen Fall.

Kurz zusammengefasst wird in der DE 699 15 837 T2 anerkannt, dass ein Netz mit einem irregulären Kontrollpunkt durch (rechnerisches) Ausführen einer bestimmten Anzahl von weiteren Unterteilungsschritten zu einem regulären Netz wird. Mit anderen Worten werden im Rahmen dieser Unterteilungsschritte neue Kontrollpunkte definiert und/oder berechnet, welche schlussendlich dazu führen, dass ein Flächenstück (insbesondere ein durch ein Netz (Ausgangsnetz) definiertes Flächenstück) mit einem ursprünglich irregulären Kontrollpunkt in Flächenstücke mit nur noch regulären Kontrollpunkte unterteilt wird. Die Unterteilung erfolgt dabei derart, dass das Flächenstück bzw. dessen Ausgangsnetz so lange weiter unterteilt wird, bis der auszuwertenden Kontrollpunkt in einem regulären und gegenüber dem Ausgangsnetz kleinflächigeren 4 x 4 Kontrollpunktnetz liegt. Mit jedem Unterteilungsschritt verringert sich dabei der flächenmäßige Anteil des den irregulären Kontrollpunkt enthaltenen und aus der Unterteilung hervorgehenden Kontrollpunktnetzes. Genauer gesagt resultiert die Unterteilung des irregulären Ausgangsnetzes bzw.

Flächenstücks in drei regulären und einem irregulären Flächenstück, welches, wenn es den irregulären Kontrollpunkt enthält, wiederum weiter unterteilt werden könnte, wobei der Flächenanteil des irregulären Flächenstücks an der Gesamtfläche des ursprünglichen Ausgangsnetzes mit jedem Unterteilungsschritt abnimmt. Um jedoch den damit einhergehenden Berechnungsaufwand zu reduzieren und insbesondere eine konstante Berechnungszeit zu erreichen, wird in der DE 699 15 837 T2 im Bereich eines irregulären Kontrollpunktes die Eigenstruktur einer dazugehörigen Subdivisionsmatrix berechnet.

Dies ermöglicht eine rechnerische Bestimmung beliebig vieler lokaler Unterteilungsschritte und damit zusammenhängender neuer Kontrollpunkte. Da dabei lediglich das

Flächenstück, das den irregulären Kontrollpunkt enthält, rechnerisch unterteilt wird, nicht aber zwingend das gesamte Modell, kann dies als ein lokales Unterteilen bezeichnet werden. Für das geschilderte Unterteilen können dabei einige Matrixausdrücke vorab berechnet und für das rechnerische Durchführen der weiteren Unterteilungsschritte lediglich aus einem Speicher ausgelesen werden. Somit kann diese Berechnung unabhängig von der Position eines zu untersuchenden Ortes und auch den erforderlichen zusätzlichen Unterteilungsschritten im Wesentlichen mit einer konstanten

Berechnungszeit ausgeführt werden.

Sobald die regulären Kontrollpunkte für ein entsprechendes Flächenstück berechnet wurden, können wiederum mittels einem Satz von B-Spline-Basisfunktionen beliebige Orte innerhalb des Flächenstücks im Rahmen einer Simulation ausgewertet werden. Eine detaillierte Darstellung der hierfür erforderlichen Rechenschritte findet sich beispielsweise in den Absätzen [0042-0088] der DE 699 15 837 T2, wobei zum Beispiel in Absatz [0080] auf vorab berechenbare und hinterlegbare Informationen eingegangen wird.

Die in der DE 699 15 837 T2 dargelegten Grundsätze lassen sich jedoch nicht auf volumenmetrische Subdivisionsmodelle übertragen. Dies führt dazu, dass derartige volumenmetrische Subdivisionsmodelle bisher nicht in der gewünschten Weise für das Simulieren von Objekteigenschaften verwendet werden können, beispielsweise um in dem Objekt wirkende Kräfte oder Spannungen zu berechnen und die Konstruktion des Objekts daraufhin geeignet anzupassen. Somit besteht auch keine zufriedenstellende Möglichkeit, den eigentlichen Vorteil von Subdivisionsmodellen in Form der geschilderten geringen Informationsverluste beim Übergang zwischen CAD und CAE im Rahmen entsprechender Simulationen auszunutzen.

So ist zwar aus der vorstehend zitierten wissenschaftlichen Arbeit von Burkhart et al. eine Lösung bekannt, bei der in volumetrischen Modellen irreguläre Volumenelemente rechnerisch so oft lokal unterteilt werden können, bis diese regulär werden und mittels herkömmlicher Rechenansätze auswertbar sind. Aufgrund der erforderlichen Anzahl an zu berechnenden Unterteilungen ist die Rechenzeit jedoch stark von dem Ausmaß an Irregularitäten abhängig und kann allgemein unerwünscht hohe Werte annehmen.

Aufgabe der vorliegenden Erfindung ist es daher, eine computergestützte Designphase und Simulationsphase bei der Entwicklung technischer Objekte oder Systeme besser miteinander zu koordinieren, insbesondere derart, dass präzise Ermittlungen relevanter Eigenschaften mit einer begrenzten Rechenzeit ermöglicht werden. Diese Aufgabe wird durch ein Verfahren, ein Computerprogrammprodukt und eine Computervorrichtung gemäß den beigefügten unabhängigen Ansprüchen gelöst.

Vorteilhafte Weiterbildungen sind in den abhängigen Ansprüchen angegeben. Ferner versteht es sich, dass die in der einleitenden Beschreibung erwähnten Merkmale einzeln oder in beliebiger Kombination auch bei der vorliegend offenbarten Lösung vorgesehen sein können, sofern nicht anders angegeben oder ersichtlich.

Die Erfindung löst das technische Problem, dass Rechenzeiten eines Computers für Simulationen der vorstehenden Art nicht beliebig hoch ausfallen sollen. Als technisches Mittel wird hierfür vorgeschlagen, die Ausrichtung der irregulären Kanten zu

berücksichtigen bzw. zur Grundlage einer Simulation zu machen. Wie nachstehend gezeigt, ermöglicht dies, umfangreich auf vorab gespeicherte Ergebnisse (insb.

Matrixausdrücke) zurückzugreifen, die vorteilhafterweise nicht bei jeder Einzelsimulation neu berechnet und aufgestellt werden müssen. Anders ausgedrückt wird als technisches Mittel ermöglicht, vorab berechnete Ergebnisse bedarfsweise aus einem Speicher auszulesen und in eine Simulationsberechnung einzubinden, um so die Rechenzeit eines Simulationscomputers zu begrenzen. Ein wichtiger Erfindungsgedanke, der ermöglicht, dass die vorab gespeicherten Ergebnisse verwendet werden können und der ferner die Ermittlung ermöglicht, welche dieser Ergebnisse auszulesen und anzuwenden sind, ist das Berücksichtigen der Ausrichtung irregulärer Kanten.

Die Erfinder haben allgemein erkannt, dass es möglich ist, ein volumetrisches

Subdivisionsmodell in Kenntnis einer räumlichen Ausrichtung wesentlicher irreguläre Eigenschaften mittels begrenztem rechnerischen Aufwand und unter Umständen sogar einer im Wesentlichen konstanten Berechnungszeit unabhängig von dem Ausmaß der Irregularität und/oder gegebenenfalls erforderlicher weiterer Unterteilungsschritte auszuwerten. Insbesondere wurde erkannt, dass durch das Bestimmen der Ausrichtung von einer sogenannten irregulären Kante, die in einem den auszuwertenden Ort enthaltenden Volumen-Element des Subdivisionsmodells liegt, das entsprechende Volumen-Element in regulär und irregulär auswertbare Bereiche und/oder Ebenen eingeteilt werden kann. Insbesondere kann in im Wesentlichen orthogonal zu der irregulären Kante verlaufenen Ebenen auf eine analoge Auswertung zurückgegriffen werden, wie für den zweidimensionalen Fall im Stand der Technik bekannt (siehe zum Beispiel DE 699 15 837 T2). Diese Ebenen können ebenfalls auf Basis der erfindungsgemäß vorgeschlagenen Ermittlung der Ausrichtung der irregulären

Eigenschaft bzw. Kante ermittelt werden. In Ebenen, welche die irreguläre Eigenschaft bzw. Kante enthalten, kann unter Umständen hingegen eine reguläre Auswertung gemäß dem zweidimensionalen Fall vorgenommen werden. Um eine tatsächliche

dreidimensionale Auswertung vorzunehmen, kann ferner vorgesehen sein, die irregulären aber gemäß den zweidimensionalen Ansätzen auswertbare Ebenen mit Basisfunktionen entlang bzw. in Richtung der irregulären Eigenschaft zu kombinieren. Auch dies wird wiederum dadurch ermöglicht, dass zunächst die Ausrichtung der irregulären Eigenschaft bzw. Kante ermittelt wird. Insbesondere können auf diese Weise irreguläre Strukturen in nachfolgend erläuterte sogenannte geschichtete Strukturen umgewandelt werden, die in zumindest einer Dimension regulär sind und in sich zu dieser Dimension erstreckenden Ebenen bzw. Schichten irregulär sind. Diese können dann in konstanter Zeit (d. h.

konstanter Berechnungszeit) ausgewertet werden, unabhängig von dem Grad der Irregularität.

Genauer gesagt wird das bisherige Vorgehen im zweidimensionalen Fall anhand der Gleichungen (9) bis (1 1 ) dieser Offenbarung zusammengefasst, wobei sämtliche

Ausdrücke zwischen„C“ und„N“ in Abhängigkeit der für eine lokale Auswertung erforderlichen n-Unterteilungen vorab gespeichert werden können. Darauf basierend können die auch in der referenzierten Arbeit von Jos Stam beschriebenen

Eigenbasisfunktionen cp(u,v) aus Gleichung (1 1 ) formuliert und größtenteils vorberechnet werden.

Wie gezeigt, wurde für den dreidimensionalen Fall z.B. bei Burkhart et al. bisher ein anderer Weg beschritten. So wurde dort zum Kompensieren von lokalen Irregularitäten zwar ebenfalls lokal (rechnerisch) unterteilt, allerdings ohne, dass kurze und vor allem konstante Rechenzeiten erreicht wurden.

Eine überraschende Erkenntnis der Erfindung liegt insbesondere darin, dass irreguläre Elemente eines volumetrischen Subdivisionsmodells unter Berücksichtigung der

Ausrichtung irregulärer Kanten entgegen Burkhart et al. mit einem vertretbaren

Rechenaufwand auswertbar sind. Insbesondere wurde erkannt, dass dies ähnlich wie im 2D-Fall ermöglicht, umfassende Matrixausdrücke vorab zu berechnen und zu speichern, was die Rechenzeit begrenzt. Beispielsweise wurde erkannt, dass dann sogenannte geschichtete Strukturen definiert werden können, wonach gleichartige irreguläre 2D-Ebenen entlang einer dritten

Dimension aneinandergereiht bzw. geschichtet werden können. Die dritte Dimension erstreckt sich dabei bevorzugt entlang der irregulären Kante, deren Ausrichtung als wesentliches neues erfindungsgemäßes Merkmal bestimmt und berücksichtigt wird. Ein zur Auswertung verwendetes Koordinatensystem kann also mit einer seiner Dimensionen bevorzugt entlang dieser Kante ausgerichtet werden.

Dies ermöglicht gemäß nachstehender Gleichung (17), die aus Gleichung (1 1 ) des 2D- Falls bekannten und größtenteils vorab berechneten Eigenbasisfunktionen cp(u,v) erneut zu verwenden und mit einer weiteren Basisfunktionen, die ebenfalls entlang der irregulären Kante ausgerichtet ist, zu multiplizieren. Dies wird nachstehend beispielhaft anhand von Gleichungen (17)-(19) sowie unter anderem Figur 7b und Figur 9 diskutiert.

Die Erfindung zeichnet sich insbesondere durch die folgenden Beiträge und Erkenntnisse aus, die nachstehend noch jeweils detailliert erläutert werden und die teils rein optional sind:

- direktes Auswerten von geschichteten Strukturen mit einer irregulären Kante, wofür die 2D-Basisfunktionen von Stam mit regulären Basisfunktionen in der dritten, einer Ausrichtung der Kante entsprechenden Dimension multipliziert werden können und die Auswertung in konstanter Rechenzeit erfolgt;

- darauf aufbauend: direktes Auswerten von Randzellen eines Subdivisionsmodells, wofür in einer Dimension senkrecht zum Rand des Subdivisionsmodells die sog. Crease-Basisfunktionen verwendet werden können. Dies kann für reguläre und geschichtete Randzellen eingesetzt werden und kann ebenfalls in konstanter Rechenzeit erfolgen;

- ferner darauf aufbauend: ein konstantes und/oder konsistentes

Nummerierungsverfahren für das Auswerten von komplett irregulären Zellen, die mehr als einer irregulären Kante aufweisen. Dabei erfolgt Nummerierung der Kontrollpunkte bevorzugt nach einem festen Schema und ist konsistent für die jeweilige, in der Zelle angetroffene irreguläre Konfiguration. Diese konsistente Nummerierung erlaubt eine Berechnung der Eigenstruktur der Subdivisionsmatrix und das Übertragen von Stams Auswertealgorithmus auf derart irreguläre volumetrische Subdivisionsmodelle, weshalb auch irreguläre Zellen mit mehr als einer irregulären Kante in konstanter Zeit auswertbar sind.

Die Erfindung kann für technische Zwecke vorteilhafterweise wie folgt zum Einsatz kommen:

Finite-Elemente-Analyse (FEA) und/oder Isogeometrische Analyse (IGA), z.B. für Simulationen einer Hitzeausbreitung oder für die Strukturmechanik. Zur

Berechnung der Simulationsergebnisse bzw. zum Lösen des Simulationsszenarios müssen an verschiedenen Stellen im Simulationsalgorithmus Integrale über finite Elemente berechnet werden (z.B. zum Berechnen einer Steifigkeitsmatrix oder eines Volumens des zu simulierenden Bauteils). Verwendet man volumetrische Subdivisionsmodelle als Basis für die Simulation, wie vorliegend allgemein vorgesehen, kann das erfindungsgemäße Vorgehen die Berechnung dieser Integrale und damit die Berechnung der gesamten Simulation beschleunigen, da für jede Zelle (bzw. jedes Element) mehrere Orte (d.h. Integrationsorte) auszuwerten sind. Eine solche Auswertung beliebiger Orte gelingt

erfindungsgemäß durch Rückgriff auf vorab gespeicherte Ausdrücke/Ergebnisse mit geringer und sogar konstanter Rechenzeit.

Additive Fertigungsverfahren, insbesondere 3D-Druck mit mehreren Materialien, z.B. per PolyJet-Verfahren. Um ein Bauteil additiv zu fertigen, wird es für die meisten 3D-Druck-Verfahren in Schichten zerlegt (sog. Slicing). Bei 3D-Druck- Verfahren, die mehrere Materialen in einem Bauteil verarbeiten können, wird für jeden Ort innerhalb jedes Slices der zu verdruckende Materialwert benötigt. Mit volumetrischen Subdivisionsmodellen, wie hierin allgemein verwendet, kann man Multi-Material-3D-Druck-Modelle effizient darstellen und sogar gradierte

Materialübergänge modellieren. Sowohl zur Bestimmung der Slices, als auch zur Bestimmung des Materialwerts an jedem Ort im Slice, sind (zum Teil mehrfache) Auswertungen an beliebigen Orten und genauer gesagt Limit-Orten eines

Subdivisionsmodells erforderlich. Mit dem hierin offenbarten Lösungsweg gelingt dies deutlich schneller als mit bisherigen Verfahren und sogar mit konstanter Rechenzeit pro auszuwertendem Ort. Im Detail wird ein Verfahren zum computergestützten Auswerten eines volumetrischen Subdivisionsmodells, das durch ein Kontrollpunktnetz aus mittels Kanten verbundener Kontrollpunkte beschrieben (oder, mit anderen Worten, definiert) wird, wobei das Verfahren umfasst:

- Erhalten von Informationen hinsichtlich eines in dem Volumen des

Subdivisionsmodells liegenden auszuwertenden Ortes;

- Ermitteln, ob der auszuwertende Ort in einem Volumenelement liegt, das eine irreguläre Kante aufweist, welche eine Kante ist, die einen Kontrollpunkt mit einer von sechs verschiedenen Valenz verbindet,

- und wenn dies der Fall ist:

- Bestimmen einer Ausrichtung der irregulären Kante;

- Auswerten des volumetrischen Subdivisionsmodells an dem auszuwertenden Ort basierend auf der ermittelten Ausrichtung.

Sämtliche aufgelisteten Maßnahmen können computergestützt ausgeführt werden, zum Beispiel mittels einer Rechen- oder Prozessoreinheit eines herkömmlichen PCs, zum Beispiel ein Desktop oder Laptop, eines Servers, eines Handheld-Geräts, zum Beispiel ein Smartphone, und/oder der hierin offenbarten Computervorrichtung. Insbesondere kann auch eine Kombination derartiger Computer (zum Beispiel ein Computer-Netzwerk) zur Ausführung verwendet werden. Insbesondere die Maßnahmen gemäß zumindest einem der letzten vier Gliederungspunkte der vorangehenden Aufzählung können von einem derartigen Computer oder einer Kombination derartiger Computer ausgeführt werden.

Zwischen- und/oder Endergebnisse können in zumindest einer Speichereinrichtung des Computer oder des Computer-Netzwerks gespeichert werden. Allgemein kann das Verfahren einen Schritt des Abspeicherns des ausgewerteten Orts in einer

Speichereinrichtung oder, anders ausgedrückt, in einem Computerspeicher umfassen.

In an sich bekannter Weise kann ein Kontrollpunkt mit mehreren benachbarten

Kontrollpunkten über jeweils individuelle Kanten verbunden sein, d.h. auf den Kanten und an den Enden der Kanten liegen nicht weitere Kontrollpunkte. Eine Mehrzahl von untereinander mittels Kanten verbundener Kontrollpunkte kann eine sogenannte (virtuelle) Fläche (engl face) in dem Subdivisionsmodell definieren. Genauer gesagt kann eine Fläche durch eine Mehrzahl von Kontrollpunkten begrenzt und/oder aufgespannt werden, wobei einer der Kontrollpunkte mit jeweils zwei anderen aus der Mehrzahl von Kontrollpunkten mittels Kanten verbunden ist. Liegt diese Fläche im Bereich der Oberfläche des Subdivisionsmodells kann es sich entsprechend um einen

Oberflächenbereich oder, mit anderen Worten, eine Teilfläche der Oberfläche des

Subdivisionsmodells handeln.

Das Subdivisionsmodell kann allgemein dazu dienen, ein Objekt, ein Werkstück, eine Baugruppe, ein technisches System oder dergleichen zu beschreiben und/oder zu modellieren. Im Unterschied zu dem zweidimensionalen Fall kann ein volumetrisches Subdivisionsmodell allgemein ein dreidimensionales Volumen definieren und/oder umfassen sowie über vorstehend erläuterte Zellen auch das Innere des Volumens modellieren. Insbesondere können hierdurch auch Eigenschaften in einer

Tiefendimension (d. h. in der Tiefe und/oder im Innern des Volumens) und nicht lediglich in einer Ebene auf der Oberfläche bestimmt und/oder modelliert werden.

Die Kontrollpunkte können in der vorstehend geschilderten Weise als Kontrollpunkte oder, anders ausgedrückt, Steuerpunkte oder Steuerknoten von Funktionen definiert sein, die Eigenschaften des Subdivisionsmodells beschreiben. Insbesondere können derartige Funktionen eine Form des Subdivisionsmodells beschreiben, zum Beispiel dessen sogenanntes Limit-Volumen. Letzteres entspricht dem kontinuierlichen volumetrischen Körper, der durch konzeptionell unendliche viele Verfeinerungen der Kontrollpunktnetz- Struktur des Subdivisionsmodells erzeugt wird und für viele Subdivisionsverfahren mathematisch bestimmt werden kann. Eine vergleichsweise hohe oder auch maximal möglichen Anzahl an Unterteilungen des Subdivisionsmodells ergibt eine Annäherung an dieses Limit-Volumen.

Alternativ oder zusätzlich können derartige Funktionen allgemein auch

Materialeigenschaften, Materialübergänge, Materialdichten oder dergleichen definieren, wobei dies individuell je Knotenpunkt erfolgen kann. Dies ist zum Beispiel vorteilhaft, um Mehr-Material-Werkstücke oder -Baugruppen zu beschreiben, die beispielsweise mittels Rapid-Prototyping-Verfahren (oder allgemeinen generativen Schichtbauverfahren) hergestellt werden.

Unter einem auszuwertenden Ort in dem Volumen des Subdivisionsmodells können auch Orte in oder auf einer Oberfläche des Volumens bzw. des Subdivisionsmodells verstanden werden.

Neben dem bereits beschriebenen Kanten, Kontrollpunkten und Flächen kann das Subdivisionsmodell auch Volumenelemente und/oder Zellen umfassen und/oder mittels solcher definiert werden. Unter einem Volumenelement (engl.: cell oder element) kann allgemein ein beliebiger Volumenanteil des Subdivisionsmodells samt der darin enthaltenen Kanten, Kontrollpunkte etc. verstanden werden. Insbesondere kann es sich um einen mittels nachstehend erläuterter regulärer Berechnungsansätze auswertbaren oder allgemein mittels bevorzugter Auswertemöglichkeiten auswertbaren Volumenanteil handeln. Als Beispiel sei ein Volumenelement genannt, das von 4 x 4 x 4 Kontrollpunkten definiert bzw. aufgespannt wird und das 3 x 3 x 3 Zellen umfassen kann. Für ein

Auswerten können allgemein diejenigen 4 x 4 x 4 Kontrollpunktanordnungen identifiziert werden, welche einen auszuwertenden Ort enthalten. Insbesondere kann es sich bei dem Volumenelement um eine lokale (Kontrollpunkt-) Nachbarschaft eines auszuwertenden Ortes und beispielsweise einer Zelle handeln, welche den auszuwertenden Ort enthält. Genauer gesagt liegt der auszuwertende Ort in einer bestimmten Zelle, wobei für die Auswertung des Ortes eben diese Zelle sowie deren Nachbarn und die dazugehörigen Kontrollpunkte betrachtet werden. Die den auszuwertenden Ort enthaltende Zelle kann entsprechend mittig oder zentral angeordnet sein (zum Beispiel mittig in einem regulären 4 x 4 x 4 Kontrollpunktenetz oder auch mittig in einem zunächst irregulären

Kontrollpunktnetz). Übergeordnet kann ein Volumenelement wenigstens eine Zelle umfassen.

Eine Zelle kann insbesondere von acht paarweise einander gegenüberliegenden und vorzugsweise paarweise zueinander parallelen Flächen definiert und/oder umgeben sein. Allgemein ausgedrückt kann eine Zelle durch eine beliebige Anzahl von Flächen definiert werden, welche ein Volumen innerhalb des Subdivisionsmodells vollständig umgeben und/oder einschließen. Das entsprechende Volumen kann dann die Zelle bilden. Es versteht sich, dass die Zelle auch durch entsprechende Kontrollpunkte und Kanten der Flächen begrenzt ist bzw. diese umfasst.

Die Informationen hinsichtlich des auszuwertenden Ortes können sich auf Koordinaten oder Parameterwerte des Ortes beziehen. Insbesondere kann es sich um

Koordinatenwerte handeln, welche eine Position des Ortes in dem Modellvolumen angeben, beispielsweise in einem Raumkoordinatensystem, das auch als X, Y, Z- Koordinatensystem bezeichnet werden kann. Alternativ kann eine Zelle enthaltend den auszuwertenden Ort identifiziert und können Parameterwerte angegeben werden, die die Position des Ortes in einem lokalen Koordinatensystem dieser Zelle definieren. Dieses lokale Koordinatensystem kann zum Beispiel als u, v, w- Koordinatensystem bezeichnet werden.

Das Subdivisionsmodell kann mittels bekannter Datenformate oder allgemeiner computergestützter Formate beschrieben und/oder gespeichert werden. Aus den entsprechenden Datensätzen können mittels herkömmlicher Algorithmen gesuchte Eigenschaften des Subdivisionsmodells ermittelt werden. Beispielsweise kann die Valenz von Kontrollpunkten und folglich auch das Vorhandensein und/oder eine Position einer irregulären Kante ermittelt werden. Ebenso können Erstreckungen, Positionen oder Ausrichtungen einzelner Volumenelemente oder Zellen bestimmt oder definiert werden, und insbesondere solcher Zellen, die den auszuwertenden Ort enthalten. Prinzipiell ist es aber auch möglich, dass Subdivisionsmodell virtuell darzustellen und es einem Bediener zu ermöglichen, irreguläre Eigenschaften wie Kontrollpunkte oder Kanten manuell zu identifizieren und/oder einzelne Volumenelemente oder Zellen innerhalb des

Subdivisionsmodells manuell auszuwählen.

Gemäß dem vorliegenden Verfahren können insbesondere Volumenelemente, welche irreguläre Eigenschaften aufweisen oder umfassen (oder auch Zellen, die von derartigen Volumenelementen umfasst sind), ermittelt werden, beispielsweise anhand

entsprechender Datensätze. Eine irreguläre Kante kann auch derart definiert werden, dass diese eine von vier verschiedene Valenz aufweist, wobei die Valenz als die Anzahl von an die Kante angrenzenden Flächen oder, mit anderen Worten, als die Anzahl von Flächen definiert sein kann, welche von der Kante ausgehen und/oder über diese bzw. mit dieser verbunden sind. Unter dem Auswerten kann die vorstehend geschilderte Parametrisierung verstanden werden, also insbesondere das Ermitteln von Ortskoordinaten oder Eigenschaften des bzw. an dem auszuwertenden Ort anhand von Funktionen, die von den Kontrollpunkten definiert sind. Bei diesen Funktionen kann es sich allgemein um Basisfunktionen oder, im Fall regulärer Zellen, um (insbesondere trivariate) B-Spline-Funktionen handeln (bei irregulären Zellen können stattdessen modifizierte B-Spline-Funktionen verwendet werden). Die Ausrichtung der Kante kann hierbei dazu verwendet werden, um Bereiche (beispielsweise Ebenen) in einem betrachteten Volumenelement zu identifizieren, die mittels bevorzugter und/oder herkömmlicher Ansätze auswertbar sind (beispielsweise mittels der zweidimensionalen Ansätze aus der wissenschaftlichen Arbeit von Jos Stam bzw. aus der DE 699 15 837 T2). Hierbei kann es sich allgemein um irreguläre oder reguläre Bereiche oder Ebenen handeln, wobei die Irregularität sich wiederum danach richten kann, ob dort Kontrollpunkte mit vorbestimmten Valenzen und im Fall von zweidimensionalen Ebenen mit einer von vier verschiedenen Valenz vorhanden sind.

Ferner ist darauf hinzuweisen, dass dann, wenn sich der auszuwertende Ort nicht in einem Volumenelement und/oder einer Zelle befindet, das eine irreguläre Kante aufweist, eine Ortsauswertung mittels regulärer Ansätze erfolgen kann. Insbesondere kann dann das Volumenelement in Form einer lokalen Nachbarschaft um den auszuwertenden Ort (bzw. die Zelle die diesen Ort enthält) zum Beispiel in Form eines 4 x 4 x 4- Kontrollpunktnetzes oder einer Anordnung von 3 c 3 c 3 Zellen definiert werden. Eine Möglichkeit zur Auswertung besteht dann darin, trivariate Basisfunktionen aus Produkten von univariaten Basisfunktionen der Kontrollpunkte dieses Volumenelements zu bestimmen.

Allgemein ist im Rahmen der vorliegenden Erfindung folgender Ablauf möglich, bei dem nicht sämtliche Maßnahmen zwingend sind und dessen Reihenfolge nicht einschränkend ist:

Es wird ermittelt, ob das Volumenelement mit dem auszuwertenden Ort eine vollständig irreguläre Struktur aufweist, d. h. keine Dimension oder Ebene definiert werden kann, entlang bzw. in der reguläre Eigenschaften (d.h. reguläre Kanten und Kontrollpunkte) vorliegen; und wenn dies der Fall ist (falls nicht liegt bereits eine geschichtete Struktur vor und der folgende Schritt wird übersprungen):

Es wird eine Anzahl an (rechnerischen) Unterteilungsschritten ermittelt (z.B.

anhand folgender Figur 9), bis eine zumindest in einer Dimension reguläre Struktur erhalten wird (sog. geschichtete Struktur, wie nachstehend noch näher erläutert), wobei für diese Unterteilung Einträge einer Unterteilungsmatrix in vorbestimmter Weise gewählt werden, insbesondere in Abhängigkeit nachfolgend erläuterter struktureller Eigenschaften des Kontrollpunktnetzes; und wenn daraufhin die geschichtete Struktur erreicht wurde oder diese bereits vorlag:

Es wird, wie vorstehend erläutert, eine Ausrichtung der (noch) verbleibenden irregulären Kante bestimmt und darauf basierend an dem betrachteten Ort ausgewertet, insbesondere mittels nachfolgender (Unterteilungs-) Basisfunktionen und/oder einer berechneten Eigenstruktur der Unterteilungsmatrix.

Eine Ausführungsform sieht ferner folgende Maßnahme vor:

- Definieren eines Koordinatensystems nach Maßgabe der Ausrichtung der

irregulären Kante und insbesondere derart, sich die irreguläre Kante entlang einer (z.B. vorbestimmten und/oder bevorzugten) Achse des Koordinatensystems erstreckt.

Das Definieren des Koordinatensystems nach Maßgabe der Ausrichtung der irregulären Kante bedeutet, dass die Ausrichtung der irregulären Kante bei der Definition des

Koordinatensystems berücksichtigt wird. Bei diesem Koordinatensystem kann es sich um dasselbe Koordinatensystem handeln, auf das sich auch die Informationen bezüglich des auszuwertenden Ortes beziehen. Insbesondere kann es sich um das vorstehend erläuterte Koordinatensystem zum Definieren von Orten in einer einzelnen Zelle, also beispielsweise einem sogenannten u, v, w- Koordinatensystem. Übergeordnet können sich derartige zellenbezogene Koordinatensysteme vor allem dadurch auszeichnen, dass deren Achsen, die vorzugsweise jeweils orthogonal zueinander verlaufen, jeweils Werte von 0 bis 1 umfassen und die Zelle entsprechend dieser Achsen parametrisiert wird.

Alternativ oder zusätzlich kann es sich um dasselbe Koordinatensystem handeln, in dem auch die Kontrollpunkte definiert sind, oder aber um ein hiervon verschiedenes

Koordinatensystem. Im Rahmen der vorliegenden Offenbarung können sämtliche

Koordinatensysteme als kartesische Koordinatensysteme definiert sein. Es versteht sich, dass die Definition des Koordinatensystems wiederum virtuell bzw. rechnerisch sowie allgemein computergestützt und/oder durch manuelle Eingaben des Benutzers erfolgen kann.

Bezogen auf ein zellenbezogenes (u, v, w-) Koordinatensystem kann dieses

beispielsweise derart definiert werden, dass sich die irreguläre Kante zum Beispiel entlang einer entsprechenden u-, v- oder w-Achse erstreckt. Insbesondere kann in einem ersten Schritt die Ausrichtung der irregulären Kante in dem Koordinatensystem und zum Beispiel auch eine Relativausrichtung zu wenigstens einer Achse des

Koordinatensystems bestimmt werden. Anschließend kann das Koordinatensystem oder das Subdivisionsmodell umfassend die irreguläre Kante neu ausgerichtet werden, sodass sich die irreguläre Kante entlang der vorbestimmten Achse erstreckt. Hierzu können zum Beispiel in an sich bekannter Weise die Koordinaten der Kontrollpunkte und/oder Kanten des Subdivisionsmodells nach Maßgabe der durchzuführenden Anpassung transformiert werden.

Die Erfinder haben erkannt, dass sich hierdurch Zustände erreichen lassen, bei denen ein Volumenelement, welches eine Zelle mit dem auszuwertenden Ort enthält, spätestens nach wenigstens einer weiteren (rechnerischen) Unterteilung in reguläre Ebenen entlang der irregulären Kante und irreguläre Ebenen orthogonal hierzu einteilbar ist. Insbesondere kann hierdurch ein schichtweiser Aufbau und/oder ein schichtweises Auswerten des Volumen-Elements erreicht werden, bei denen im Wesentlichen oder vollständig gleichartig aufgebaute zweidimensionale Knotenpunktnetze bzw. Schichten entlang der irregulären Kante aneinandergereiht sind. Insbesondere können diese Schichten irreguläre Kontrollpunkte an jeweils gleichen Positionen umfassen.

Vorzugsweise werden für eine derartige schichtweise Betrachtung Volumenelemente herangezogen (d. h. in dem Subdivisionsmodell definiert und/oder ausgewählt), die in wenigstens einer Dimension (vorzugsweise sogar zwei oder drei Dimensionen) von 4 Knotenpunkten und/oder 3 Zellen aufgespannt werden, wobei dieser Zustand wiederum nach wenigstens einer weiteren (rechnerischen) Unterteilung erreicht werden kann.

Bei einer Weiterbildung sind ferner folgende Maßnahmen vorgesehen: - Identifizieren einer Zelle des Subdivisionsmodells, welche den auszuwertenden Ort enthält; und

- Ermitteln der Anzahl von Unterteilungen dieser Zelle, die erforderlich ist, damit sich der auszuwertende Ort in einer auswertbaren Zelle befindet, die durch das Unterteilen aus der ursprünglichen Zelle hervorgeht.

Optional kann ferner auch vorgesehen sein, dass die Unterteilung (zumindest lokal d. h. im Bereich der Zelle) rechnerisch durchgeführt wird, um eine auswertbare Umgebung um den auszuwertenden Ort zu schaffen. Das rechnerische Unterteilen kann dabei mit einer (vorbestimmten) konstanten Berechnungszeit erfolgen.

In diesem Zusammenhang kann ferner vorgesehen sein, dass sich die auswertbare Zelle dadurch auszeichnet, dass diese keinen Kontrollpunkt mit einer von sechs verschiedenen Valenz umfasst. Dies trifft beispielsweise auf den nachstehend geschilderten Fall einer regulären Zelle zu. Allerdings können mit der hierin offenbarten Lehre auch Zellen ausgewertet werden, die in einer nachstehend erläuterten geschichteten Struktur vorliegen bzw. (maximal) eine irreguläre Kante aufweisen. Die Anzahl n an notwendigen Unterteilungen für einen auszuwertenden Ort an der Position u, v, w in einem

zellenbezogenen Koordinatensystem einer Zelle kann allgemein mittels folgender Formel bestimmt werden: n = mm j- log _^ , < H ) . - log-, (t>) . - log-, ( w ) | ]

Zusätzlich oder alternativ kann die Anzahl der notwendigen Unterteilungen mittels nachfolgend anhand von Figur 9 erläuterten Zusammenhängen bestimmt werden, welche wiederum auf einem zellenbezogenen Koordinatensystem und insbesondere einer vorbestimmten Ausrichtung der irregulären Kante darin beruhen.

Die Zelle kann im Rahmen eines einzelnen Unterteilungsschritts in acht kleinere

Einzelzellen unterteilt werden, welche in zusammengesetzter Form dasselbe Volumen einnehmen, wie die Ausgangszeile. Befindet sich der auszuwertende Ort anschließend innerhalb einer (neuen) Zelle, die nicht mehr den irregulären Kontrollpunkt umfasst, kann mittels im Rahmen der Ausführungsbeispiele aufgezeigter Ansätze unmittelbar ausgewertet werden. Weist die den auszuwertenden Ort enthaltende (neue) Zelle aber nach wie vor den irregulären Kontrollpunkt auf, muss zumindest diese Zelle noch weiter unterteilt werden. Der Zusammenhang zwischen der Anzahl der erforderlichen

Unterteilungsschritte in Abhängigkeit einer Entfernung des auszuwertenden Ortes von dem irregulären Kontrollpunkt kann vorab rechnerisch bestimmt und hinterlegt werden (siehe auch Darstellung der entsprechenden Zusammenhänge in der nachfolgenden Figur 9), sodass je nach den konkreten Parametern des auszuwertenden Ortes unmittelbar eine rechnerische lokale Unterteilung des Subdivisionsmodells vorgenommen werden kann.

Das Auswerten der Zelle, welche den auszuwertenden Ort enthält, kann unter Verwenden von speziellen Subdivisionsbasisfunktionen erfolgen, wie sie vorstehend für den zweidimensionalen Fall bereits erläutert wurden. Dies bietet den Vorteil, dass zumindest zum Teil auf bereits vorberechneter Matrixausdrücke und/oder Matrix-Matrix-Multiplikation zurückgegriffen und die erforderliche Rechenzeit somit reduziert und insbesondere im Wesentlichen konstant gehalten werden kann.

Durch Bestimmen der erforderlichen Anzahl von Unterteilungen kann insbesondere in Kenntnis der Ausrichtung der irregulären Kante und vorzugsweise mittels zum Teil bereits vorberechneter Matrixausdrücke und/oder Matrix-Matrix-Multiplikation (zum Beispiel im Rahmen der Subdivisionsbasisfunktionen) der gegebene Ort aufwandsarm ausgewertet werden.

Übergeordnet kann ferner vorgesehen sein, dass für das Auswerten an dem gegebenen Ort bzw. des gegebenen Ortes trivariate Basisfunktionen verwendet werden, welche auf Basisfunktionen entlang einer Achse des Koordinatensystems basieren, die entlang der irregulären Kante verläuft.

Ferner kann in diesem Zusammenhang vorgesehen sein, dass die Basisfunktionen für das Auswerten zusätzlich auch auf bivariaten Subdivisionsbasisfunktionen basieren, die in von den verbleibenden Achsen des Koordinatensystems aufgespannten Ebenen bestimmt werden.

Eine Gleichung, aus der die vorstehend geschilderten Berechnungen hervorgehen, ist nachstehend wiedergegeben und wird im Rahmen der Ausführungsbeispiele noch näher erläutert. Die bivariaten Subdivisionsbasisfunktionen (p(u, v) betreffen dabei einen in der wissenschaftlichen Arbeit von Jos Stam bzw. in der DE 699 15 837 T2 definierten Term zum Auswerten irregulärer zweidimensionaler Flächenstücke (dort als Eigenbasisfunktion bezeichnet, aufgrund nachfolgend erläuterter erforderlicher Anpassungen für den dreidimensionalen Fall hierin aber als Subdivisionsbasisfunktionen bezeichnet). Aufgrund der erfindungsgemäß vorgesehenen Ermittlung der Ausrichtung der irregulären Kante sowie der im Rahmen der geschilderten Weiterbildungen vorgesehenen Achsendefinition entlang dieser Kante kann ebenfalls auf diesen Term zurückgegriffen werden, um ihn mit Basisfunktionen N,(w) entlang derjenigen Achse (w) zu multiplizieren, entlang derer auch die irreguläre Kante verläuft. Die resultierenden trivariaten Basisfunktionen, die in Form der nachstehenden erläuterten Gleichung (15) zum Auswerten eines Ortes p (u, v, w) verwendet werden können, lauten:

Weiter kann zur Auswertung auf nachfolgende Gleichungen (18)-(19) zurückgegriffen werden.

Dabei bezeichnet j die jeweiligen Kontrollpunkte in einer i-ten u, v-Ebene bzw. Schicht, die jeweils orthogonal zu der irregulären Kante entlang der w-Achse verlaufen. Ein Vorteil dieser Möglichkeit besteht neben dem grundsätzlichen Bereitstellen einer praktikablen Auswertungsmöglichkeit für den dreidimensionalen Fall vor allem darin, dass durch Verwenden der Subdivisionsbasisfunktionen (p(u, v) der Berechnungsaufwand erheblich reduziert wird. Insbesondere kann eine im Wesentlichen konstante Berechnungszeit erreicht werden, unabhängig von dem Ausmaß etwaiger Irregularitäten. Des Weiteren können wesentliche Matrixausdrücke, auf denen die Subdivisionsbasisfunktionen (p(u, v) basieren, teilweise vorberechnet und für das Auswerten aufwandsarm ausgelesen werden.

Allgemein kann zunächst überprüft werden, ob der auszuwertende Ort in einer sogenannten geschichteten Struktur liegt. Ist dies nicht der Fall, kann im Rahmen einer vorbereitenden rechnerischen Unterteilung die geschichtete Struktur zunächst geschaffen werden. Hierzu kann eine Unterteilungsmatrix in vorbestimmter Weise definiert werden, um ein Unterteilen in konstanter Berechnungszeit zu erzielen. Im Detail ist bei einer Weiterbildung vorgesehen, dann, wenn das Volumenelement keine in wenigstens einer Dimension reguläre Struktur aufweist, das Volumenelement mittels einer Unterteilungsmatrix unterteilt und ausgewertet wird (sh. z.B. nachstehende Beispiel für Unterteilungsmatrix A) und die Einträge der Unterteilungsmatrix abhängig von wenigstens einer strukturellen Eigenschaft des Kontrollpunktnetzes sind. Bei den

Einträgen kann es sich allgemein um die subdivisionsbasierten Gewichtungsfaktoren für Kontrollpunkte bzw. Kontrollpunktkoordinaten handeln. Diese sollten, um eine Auswertung in konstanter Berechnungszeit zu ermöglichen, gemäß bevorzugter Vorschriften in die Unterteilungsmatrix (d. h. mit bevorzugten Spalten- und Reihenpositionen) eingetragen werden. Nachstehend wird hierfür ein Beispiel geschildert, bei der eine Nummerierung bzw. Indexierung und darauf basierende Eintragung in die Unterteilungsmatrix in einer bestimmten Reihenfolge gemäß drei verschiedener Gruppen von Kontrollpunkten erfolgt. Insbesondere können auf diese Weise sogenannte Richtungswechsel während aufeinanderfolgender Unterteilungen unterbunden werden, welche die Berechnungszeit linear mit den erforderlichen Unterteilungsschritten ansteigen lassen würden.

Die strukturelle Eigenschaft kann eine Position eines Kontrollpunktes mit einer von sechs verschiedenen Valenz (hierin auch irregulärer Kontrollpunkt genannt) innerhalb des Kontrollpunktnetzes sein. Genauer gesagt kann ein irregulärer Kontrollpunkt bestimmt werden und zum Beispiel nach Maßgabe eines Abstands zu diesem irregulären

Kontrollpunkt eine Nummerierung bzw. Indexierung der weiteren Kontrollpunkte erfolgen, um diese in die Unterteilungsmatrix einzutragen.

Weiter kann dann, wenn die Zelle mit dem auszuwertenden Ort von einer einzelnen irregulären Kante begrenzt wird, als der irreguläre Kontrollpunkt zum Festlegen der strukturellen Eigenschaften sowie der Einträge der Unterteilungsmatrix ein Kontrollpunkt gewählt werden, der ein Endpunkt der irregulären Kante ist.

Alternativ kann dann, wenn die Zelle mit dem auszuwertenden Ort von einer Mehrzahl von irregulären Kanten begrenzt wird, als der Kontrollpunkt zum Festlegen der strukturellen Eigenschaften sowie der Einträge der Unterteilungsmatrix ein Kontrollpunkt gewählt werden, der mit sämtlichen irregulären Kanten verbunden ist. Allerdings kann dann, wenn kein mit sämtlichen irregulären Kanten verbundener Kontrollpunkt vorliegt, das Kontrollpunktnetz einmal unterteilt werden, um den vorstehend genannten Zustand zu erreichen.

Gemäß einer Weiterbildung wird das volumetrische Subdivisionsmodell ferner in

Abhängigkeit davon ausgewertet, ob sich der auszuwertende Ort in einem Grenzbereich des Subdivisionsmodells zur Umgebung befindet. Die Erfinder haben allgemein erkannt, dass in einem solchen Zustand weitere Vereinfachungen der Auswertung möglich und/oder besondere Auswertungen erforderlich sind. Unter einem Grenzbereich kann allgemein ein Bereich und/oder Volumenelement des Subdivisionsmodells verstanden werden, der bzw. das nahe einer Grenzfläche des Modells zur Umgebung positioniert ist und/oder der eine solche Grenzfläche enthält. Insbesondere kann der Grenzbereich eine Nachbarschaft von wenigstens 3 c 3 c 3 Kontrollpunkten oder wenigstens 3 x 2 x 2 Zellen um die irreguläre Eigenschaft (zum Beispiel die irreguläre Kante) oder die diese

Eigenschaft enthaltene Zelle umfassen.

Wie nachstehend gezeigt, ist es aufgrund von den Erfindern erkannter Besonderheiten möglich, weniger Kontrollpunkte oder Zellen zur Auswertung heranzuziehen als bei in dem Volumen des Subdivisionsmodells liegenden Orten und/oder Zellen. Insbesondere wurden Möglichkeiten erkannt, aus dem Stand der Technik bekannte sogenannte scharfe- Kanten-Funktionen in entsprechenden Grenzbereichen zu verwenden, wodurch sich die Anzahl erforderlicher Kontrollpunkte und Zellen sowie der allgemeine Rechenaufwand verringern.

Beispielsweise kann dann, wenn sich der auszuwertende Ort in einem Grenzbereich des Subdivisionsmodells zur Umgebung befindet, wenigstens eine für das Auswerten verwendete Basisfunktion basierend auf einer scharfe-Kanten-Funktion entlang derjenigen Achse ermittelt werden, entlang derer auch die irreguläre Kante verläuft. Dies verdeutlicht sich zum Beispiel aus der nachstehend und im Folgenden noch näher erläuterten Gleichung (3), in der in nachfolgender Gleichung (15) einsetzbare

Basisfunktionen B, für ein betrachtetes Volumenelement an einzelnen Knotenpunkten i betrachtet werden. In den Richtungen, die in orthogonal zu der irregulären Kante verlaufenden Ebenen verlaufen (im untenstehenden Beispiel die u- und v-Richtung), werden herkömmliche Basisfunktionen betrachtet, während in der Richtung entlang der irregulären Kante (in dem untenstehenden Beispiel w) bzw. in Richtung des Randes oder der Grenze eine im Rahmen der Ausführungsbeispiele noch näher erläuterte scharfe- Kanten-Funktion C betrachtet wird. Bei den eckigen Klammern handelt es sich um einen Aufrund-Operator, der den Klammerinhalt im Fall von Bruchteilen auf die nächst höhere ganze Zahl aufrundet, wohingegen das %-Zeichen einen Modulo-Operator angibt:

Ni{u,v,w) = _]6 («) %4l %4 (v) N (w)

Die vorstehend geschilderte und anhand von Gleichung (3) erläuterte Auswertung kann insbesondere dann erfolgen, wenn ermittelt wird, dass die irreguläre Kante orthogonal zu oder in einer Grenzfläche des Subdivisionsmodells zur Umgebung verläuft. Insbesondere sollten in u- und v-Richtung reguläre Strukturen vorliegen und falls dies nicht der Fall ist, kann auf nachstehend erläuterte Gleichung (19) zurückgegriffen werden.

In einer weiteren Ausführungsform wird dann, wenn sich der auszuwertende Ort in einem Grenzbereich des Subdivisionsmodells zur Umgebung befindet und der auszuwertende Ort in einer Zelle des Subdivisionsmodells liegt, welche mehr als eine Grenzfläche zur Umgebung umfasst, die Zelle vor dem Auswerten wenigstens einmal (rechnerisch) unterteilt werden. Die Erfinder haben erkannt, dass es spätestens nach einer solchen Unterteilung möglich ist, eine der vorstehend erläuterten Auswertungsmöglichkeiten für Grenzbereiche zum Beispiel auf Basis von scharfe-Kanten-Funktionen anzuwenden.

Die Erfindung betrifft ferner ein Computerprogrammprodukt, umfassend

Programmanweisungen, um beim Ausführen dieser Programmanweisungen auf einer Prozessoreinheit ein Verfahren gemäß einem der vorangehenden Aspekte auszuführen. Daher ist das Computerprogrammprodukt, insbesondere ein Computerprogramm, ausgestaltet, das Verfahren gemäß der Erfindung einer der Ausführungsformen auszuführen, die in dieser Beschreibung beschrieben sind. Mit anderen Worten kann das Verfahren mittels Software ausgeführt werden. Es ist jedoch nicht ausgeschlossen, dass zumindest Teile des Verfahrens alternativ durch eine Kombination von Software und zur Ausführung des Verfahrens ausgestalteter Hardware, insbesondere mit zumindest einem zur Ausführung des Verfahrens ausgestalteten integrierten Schaltkreis (wie z.B. einem FPGA) ausgeführt werden, oder ausschließlich von derartiger Hardware. Ferner betrifft die Erfindung eine Computervorrichtung, umfassend eine Prozessoreinheit und eine Speichereinheit, in dem ein Computerprogrammprodukt gemäß dem

vorangehenden Aspekt zum Ausfuhren durch den Prozessor hinterlegt (insbesondere gespeichert und/oder ausführbar geladen) ist.

Die Erfindung wird anhand der beigefügten Zeichnungen im Folgenden näher erläutert. Identische oder in Ihrer Art und/oder Funktion übereinstimmende Merkmale können dabei figurenübergreifend mit den gleichen Bezugszeichen versehen sein.

Fig. 1 eine Prinzipskizze zum Erläutern eines Zusammenhangs von

Kontrollpunkten und einer hiervon definierten Objektform;

Fig. 2a-c Beispiele regulärer und irregulärer zweidimensionaler Flächenstücke;

Fig. 3 eine Darstellung zum Erläutern der notwendigen Anzahl von

Unterteilungsschritten, um reguläre zweidimensionale Kontrollpunktnetze zu erhalten;

Fig. 4 eine Darstellung zum Erläutern der Indexierung einzelner Kontrollpunkte vor und nach einer zusätzlichen Unterteilung;

Fig. 5a-b eine Darstellung zum Erläutern von scharfe-Kanten-Funktionen;

Fig. 6 eine Darstellung eines regulären Volumenelements eines volumetrischen

Subdivisionsmodells in Form eines 4 c 4 c 4-Netzes;

Fig. 7a-b ein Beispiel für ein irreguläres Volumenelement eines volumetrischen

Subdivisionsmodells;

Fig. 8a-b ein weiteres Beispiel für ein irreguläres Volumenelement eines

volumetrischen Subdivisionsmodells;

Fig. 9 eine Darstellung zum Erläutern der notwendigen Anzahl von

Unterteilungsschritten um reguläre Volumenelemente zu erhalten; Fig. 10a-b eine Darstellung der irregulären Volumenelemente aus Figur 7b und Figur 8b nach einer weiteren lokalen Unterteilung;

Fig. 1 1 a-e Bespiele für Zellen eines Volumenelements, die einen auszuwertenden Ort enthalten und die an den Grenzflächen eines Kontrollpunktnetzes zur Umgebung liegen;

Fig. 12 Darstellungen zum Erläutern einer benötigten Rechenzeit; und

Fig. 13a-e Darstellungen zum Erläutern einer Nummerierung von Kontrollpunkten.

Im Folgenden wird zunächst auf einige grundlegende Überlegungen der DE 699 15 837 T2 eingegangen, auf denen die hierin offenbarte Lösung teilweise aufbaut. Eine vollständige Erläuterung der entsprechenden Rechenschritte findet sich in der oben genannten wissenschaftlichen Arbeit von Jos Stam aber auch in der hierzu im

Wesentlichen inhaltsgleichen DE 699 15 837 T2, insbesondere in den Absätzen [0042- 0088]. Die Diskussion dieser vorbekannten Ansätze bezieht sich ausschließlich auf den zweidimensionalen Fall, wohingegen die hierin vorgestellte Lösung eine Erweiterung auf dreidimensionale Fälle ermöglicht.

In den Figuren 2a-c sind Beispiele regulärer und irregulärer Kontrollpunktnetze 10, 1 1 zum Modellieren zweidimensionaler Flächenstücke gezeigt, wie sie von einem

zweidimensionalen Subdivisionsmodell umfasst sein können. Dabei zeigen die durchgezogenen Linien und Punkte ein Ausgangsnetz 10 und die gestrichelten Linien und Punkte ein Netz 1 1 nach dem Durchführen eines Unterteilungsschritts gemäß dem Catmull-Clark-Algorithmus (im Folgenden auch als Unterteilungsnetz 1 1 bezeichnet). Es versteht sich, dass das Subdivisionsmodell mehrere Flächenstücke und somit auch mehrere entsprechende Kontrollpunktnetze 10, 1 1 umfassen kann, die dann

nebeneinander positioniert wären bzw. ineinander übergehen.

In Figur 2b ist ein reguläres Kontrollpunktnetz 10 gezeigt, dass von 4 x 4

Kontrollpunkten 12 aufgespannt wird, welche mittels Kanten 14 untereinander verbunden sind. Eine Mehrzahl von Kanten 14 und Kontrollpunkte 12 schließen jeweils zweidimensionale Zellen 13 zwischen sich ein. Aus Übersichtsgründen sind in sämtlichen der nachstehenden Figuren nicht alle Kontrollpunkte 12 und Kanten 14 mit einem entsprechenden Bezugszeichen versehen. Das Kontrollpunktnetz 10 dient dazu, die Form eines nicht gesondert dargestellten zweidimensionalen Flächenstücks zu modellieren bzw. mathematisch zu beschreiben.

Jeder Punkt innerhalb von dem Kontrollpunktnetz 10 (d. h. mit Ausnahme von dessen Rand) weist eine Valenz von vier auf und ist somit regulär. Ein 4 c 4 Kontrollpunktnetz 10, dass ausschließlich reguläre Kontrollpunkte 12 enthält (d. h. mit Ausnahme des Randes), definiert ein sogenanntes reguläres bikubisches B-Spline-Flächenstück bzw. kann als ein solches mathematisch beschrieben werden. Koordinaten und Eigenschaften von Orten innerhalb eines solchen Flächenstücks können aufwandsarm mittels der eingangs geschilderten B-Spline-Basisfunktionen bestimmt werden. An jedem Ort innerhalb eines derartigen regulären Flächenstücks kann daher eine Auswertung vorgenommen werden.

Obwohl dies im Fall der Figur 2b nicht erforderlich ist, ist aus Anschauungsgründen zusätzlich auch das Kontrollpunktnetz 1 1 nach einer weiteren Unterteilung in Form eines Unterteilungsnetzes 1 1 gestrichelt dargestellt. Man erkennt, dass dieses eine feinere Unterteilung aufweist, da dessen Kontrollpunkte 12 deutlich näher beieinanderliegen. Die Tatsache, dass das Unterteilungsnetz 1 1 und das Ausgangsnetz 10 gemeinsame Punkte aufweisen, ist darauf zurückzuführen, dass das Ausgangsnetz äquidistant voneinander beanstandete Kontrollpunkte 12 umfasst und ergibt sich allgemein aus den

Subdivisionsregeln.

In Figur 2a ist ein erneut mit durchgezogenen Linien dargestelltes Kontrollpunktnetz 10 zur Modellierung eines nicht gesondert dargestellten zweidimensionalen Flächenstücks gezeigt. Das Netz 10 enthält einen irregulären bzw. extraordinären Punkt 18, der eine Valenz von drei aufweist. Das Kontrollpunktnetz 10 ist somit irregulär und kann nicht ohne weiteres mittels B-Spline-Basisfunktionen ausgewertet werden. Insbesondere kann kein reguläres 4 x 4 Kontrollpunktnetz 10 definiert werden, dass ausschließlich reguläre Kontrollpunkte 12 in seinem Innern enthält (teilweise durch gestrichelt dargestellte Kontrollpunkte 12 eines nachfolgend erläuterten unterteilten Kontrollpunktnetzes überlagert). Stattdessen könnte lediglich ein 3 c 3 Netz aus entsprechend mit einem Bezugszeichen versehenen Kontrollpunkten 12 definiert werden, welches den irregulären Punkt 18 umfasst. Dieses Netz definiert jedoch kein bikubisches B-Spline-Flächenstück bzw. kann nicht als ein solches mathematisch beschrieben und ausgewertet werden.

Um dies zu beheben, wird eine weitere lokale Unterteilung nach den Regeln des Catmull- Clark-Algorithmus vorgenommen, die in dem gestrichelt dargestellten Unterteilungsnetz 1 1 resultiert, das in den Figuren 2a-c Kontrollpunkte 12 des Ausgangsnetzes jeweils teilweise überlagert. Infolge der Unterteilung lassen sich drei verschiedene reguläre 4 x 4 Kontrollpunktnetz definieren, wobei in Figur 2a eines davon, welches auch den irregulären Punkt 18 umfasst, wellenförmig umrissen ist. Dieses Netz ist deshalb regulär, da es ausschließlich Kontrollpunkte 12 mit einer Valenz von vier in seinem Innern enthält.

Somit können an sämtlichen Orten in dem regulären Netz 20 (d. h. auch an Positionen zwischen den einzelnen Kontrollpunkte 12) Auswertungen vorgenommen werden, da deren Koordinaten mittels herkömmlicher B-Spline-Basisfunktionen bestimmt werden können. Stimmt der auszuwertende Ort mit einem irregulären Kontrollpunkt 12 überein, müssen theoretisch unendliche Unterteilungen vorgenommen werden oder aber es kann anhand der nachstehend erläuterten Gleichung (7) durch Einsetzen von n = unendlich direkt ausgewertet werden. In letzterem Fall können sogenannte Limit-Regeln vordefiniert sein, die beispielsweise besagen, dass bei einem Potenzieren der Eigenwertmatrix ein mit 1 angegebener Eintrag seinen Wert beibehält, während sämtliche anderen zwischen 0 und 1 liegenden Einträge den Wert 0 annehmen. Allgemein ausgedrückt kann somit lediglich der größte Eigenwert der Eigenwertmatrix beibehalten und sämtliche anderen Einträge können mit 0 angegeben werden.

Fig. 2c zeigt ein weiteres Beispiel, in dem ein Kontrollpunktnetz 10 einen irregulären Punkt 18 enthält, der eine von vier verschiedene Valenz aufweist, nämlich eine Valenz von fünf. Das erneut mittels durchzogenen Linien dargestellte Ausgangsnetz 10 (aber auch kein hiervon umfasstes etwaiges Teilnetz) definiert somit kein reguläres 4 x 4 Kontrollpunktnetz 10, das ausschließlich reguläre Punkte enthält. Um dennoch

Auswertungen von Orten innerhalb des Netzes 10 zu ermöglichen, wird eine weitere Unterteilung gemäß dem gestrichelt dargestellten Unterteilungsnetz 1 1 vorgenommen.

In der Folge lassen sich drei verschiedene reguläre 4 x 4 Netze 20 Definieren, von denen eines in Figur 2c wellenförmig umrissen angedeutet ist. Die weiteren regulären Netze 20 würde man erhalten, wenn man den wellenförmigen Ausschnitt in Figur 2c um eine Reihe nach oben verschiebt oder um eine Spalte nach rechts. Innerhalb dieser regulären Netze 20 kann somit erneut eine Auswertung an jedem beliebigen Ort und somit auch zwischen den Kontrollpunkte 12 durchgeführt werden.

Je nach der Position eines irregulären Kontrollpunktes 18 in einem irregulären Ausgangs- Kontrollpunktnetz 10 und insbesondere eines Relativabstandes des auszuwertenden Ortes von dem irregulären Kontrollpunkt 18 ist eine unterschiedliche Anzahl von

Unterteilungsschritten notwendig, um zu erreichen, dass der auszuwertende Ort in einem regulären Netz bzw. Teilnetz liegt. Allgemein gilt, je geringer der Abstand des

auszuwertenden Ortes von dem irregulären Punkt ist, desto größer ist die Anzahl an erforderlichen Unterteilungsschritten.

Dies verdeutlicht sich auch aus der Darstellung von Figur 3. Dort ist allgemein der Parameterraum in Form eines zellenbezogenen u-v-Koordinatensystems 17 einer zweidimensionalen Zelle 13 bzw. eines zweidimensionalen Teilnetzes, dass eine solche Zelle 13 umschließt, gezeigt (vgl. Fig. 2a). Jede zweidimensionale Zelle 13 kann mittels eines solchen zweidimensionalen zellenbezogenen u-v-Koordinatensystems 17 beschrieben werden, wobei u und v jeweils Werte zwischen 0 und 1 annehmen (d. h. die Zelle 13 wird in einen entsprechenden Wertebereich parametrisiert).

Einem irregulärer Punkt der Zelle 13 werden, sofern vorhanden, die u, v-Koordinaten (0,

0) zugeordnet. Je nachdem, an welcher Position (d. h. an welchen u, v-Koordinaten) sich ein auszuwertender Ort befindet, kann aus dieser Darstellung die Anzahl der notwendigen Unterteilungsschritte abgelesen werden. Genauer gesagt bezeichnet n die Anzahl der aufeinanderfolgend auszuführenden Unterteilungsschritte und k die bei diesem

Unterteilungsschritt jeweils erhaltenen regulären Zellen bzw. Netze. Je

Unterteilungsschritt n werden drei reguläre Zellen bzw. Netze k=1 , 2, 3 erhalten (im Folgenden auch als reguläre Flächenstücke bezeichnet) sowie eine Zelle, die nach wie vor den irregulären Punkt 18 enthält.

Beispielhaft ist in Figur 3 ein erster auszuwertender Ort an einer Position 22 mit den u, v- Koordinaten (0,25; 0,75) gezeigt. Da dieser in einem der Unterteilungsnetze mit dem Wert n=1 liegt, ist nur ein einzelner Unterteilungsschritt erforderlich, um eine reguläre Zelle (k=3) umfassend den Ort 22 zu erhalten, der daraufhin ausgewertet werden kann. Als ein weiteres Beispiel ist ein zweiter auszuwertender Ort an einer Position 24 mit den ungefähren u, v-Koordinaten (0,2; 0,1 ) gezeigt. Da dieser in einem der Unterteilungsnetze mit dem Wert n=3 liegt, sind drei aufeinanderfolgende Unterteilungsschritte erforderlich, um eine reguläre Zelle (k=1 ) umfassend den Ort 24 zu erhalten, der daraufhin

ausgewertet werden kann.

Dies verdeutlicht: Je näher der auszuwertende Ort an dem irregulären Punkt 18, desto höher wird die erforderliche Anzahl der auszuführenden Unterteilungsschritte n. Weitere Hintergründe zu dieser Darstellung und insbesondere eine mathematische Beschreibung der Unterteilungen des in Figur 3 gezeigten sogenannten zweidimensionalen

Einheitsquadrats finden sich in der DE 699 15 837 T2 im Zusammenhang mit der dortigen Figur 10 (siehe insbesondere [0056-0060]).

Eine wesentliche Erkenntnis der wissenschaftlichen Arbeit von Jos Stam und der im Wesentlichen inhaltsgleichen DE 699 15 837 T2 liegt darin, derartige erforderliche Unterteilungsschritte u.a. mittels Matrixmultiplikationen zu berechnen, wobei wesentliche Matrizenausdrücke teilweise vorab gespeichert werden können (d. h. vor dem

Durchführen tatsächlicher Auswertungen und/oder Simulationen). Unabhängig davon, wie viele Unterteilungsschritte für die Auswertung eines bestimmten Ortes erforderlich sind oder theoretisch erforderlich wären, können darauf basierend mit einer im Wesentlichen konstanten Berechnungszeit durch Auslesen und Verwenden der vorab hinterlegten Matrixausdrücke beliebige Orte innerhalb an sich irregulärer Kontrollpunktnetze 10 bzw. Zellen 13 ausgewertet werden.

Die verwendeten Berechnungen, auf denen die hierin offenbarte Lösung teilweise aufbaut, sind im Folgenden kurz zusammengefasst. Detailliertere Angaben und

Hintergründe hierzu finden sich in der wissenschaftlichen Arbeit von Jos Stam (siehe insbesondere Kapitel 4) und der DE 699 15 837 T2 (siehe insbesondere [0060-0087]).

Zunächst wird auf die Figur 4 und die dortige Darstellung zum Erläutern der Indexierung einzelner Kontrollpunkte 12 vor und nach einer zusätzlichen Unterteilung Bezug genommen. Man erkennt wiederum ein mit durchgezogenen Linien dargestelltes

Ausgangs-Kontrollpunktnetz 10, das einen irregulären Punkt 18 enthält. Das Ausgangs- Kontrollpunktnetz 10 umfasst ferner mehrere Kontrollpunkte 12 (nicht sämtliche mit einem entsprechenden Bezugszeichen versehen), welche mit 1 bis 2N+8 bezeichnet sind. Dabei bezeichnet N die Valenz des irregulären Punktes 18. Ferner ist ein Unterteilungsnetz 1 1 gestrichelt dargestellt, das infolge der Unterteilung hinzugefügte Kontrollpunkte 12 enthält, die mit 2N+9 bis 2N+17 nummeriert sind. Diese werden aufgrund ihres Abstandes von dem irregulären Punkt 18 für eine weitere lokale Unterteilung nicht mehr benötigt und sind deshalb gestrichelt dargestellt.

Ausgangspunkt bildet eine Matrix Co, welche die Kontrollpunkte 12 des Ausgangs- Kontrollpunktnetzes 10 enthält. Genauer gesagt sind die in einem X, Y, Z- Koordinatensystem definierten Ortsvektoren der einzelnen Kontrollpunkte 12 als (K x 3)- Matrix Co zusammengefasst, wobei K gleich der Anzahl 2N+8 von Kontrollpunkten 12 ist, die das Ausgangs-Kontrollpunktnetz 10 definieren. Die Nummerierung der

Kontrollpunkte 12 wird ferner dazu verwendet, um den Inhalt der Matrix Co zu definieren. Genauer gesagt wird hierüber die Zeilennummer definiert, bei der die Koordinaten eines jeweiligen Punktes 12 in die Matrix Co einsortiert werden. Die x, y, z-Koordinaten ergeben dabei jeweils einen Spaltenwert (d. h. die erste Spalte enthält die x-, die zweite die y-und die dritte z-Koordinate).

Mit einer sogenannten Subdivisionsmatrix (oder auch Unterteilungsmatrix), die gemäß den allgemeinen Catmull-Clark-Unterteilungsregeln aufgestellt wird, kann eine Matrix Ci bestimmt werden, die 2N+17 Ortsvektoren der einzelnen Kontrollpunkte 12 des

Unterteilungsnetzes 1 1 enthält. Genauer gesagt gilt der Zusammenhang

Ci = ÄCo (4).

Um eine Mehrzahl von aufeinanderfolgenden Unterteilungen vorzunehmen, müssen lediglich die oberen K = 2N + 8 Reihen der -Matrix extrahiert werden, was in einer (K x K)-Matrix resultiert, die im Folgenden mit A bezeichnet wird (siehe auch [0051 -0052] der DE 699 15 837 T2). Diese Matrix kann für eine beliebige Anzahl n von

Unterteilungsschritten vorab berechnet und hinterlegt werden (d. h. vor dem eigentlichen Auswerten und/oder einer eigentlichen Simulation). Für eine beliebige Anzahl von

Unterteilungen gilt somit der folgende Zusammenhang (5), wobei C _n eine Matrix enthaltend die Ortsvektoren der Kontrollpunkte 12 nach n Unterteilungen der Ausgangs- Kontrollpunkt-Matrix Co mittels der Subdivisions- (oder auch Unterteilungsmatrix) A darstellt:

(5).

Die Berechnung der Eigenstruktur von A kann den Berechnungsaufwand der Auswertung eines beliebigen Ortes innerhalb des Flächenmodells stark reduzieren, da für n auszuführende Unterteilungen somit keine n Matrix-Matrix-Multiplikationen ausgeführt werden müssen (siehe auch folgende Gleichung (7)). Für eine Matrix V, welche die Eigenvektoren von A als Spaltenvektoren enthält und L , die eine Diagonalmatrix mit den Eigenwerten von A entlang der Diagonalen ist, gilt dabei folgendes:

AV = VA A= VAV ¹ (6).

Setzt man die diagonale Form von A in die obige Gleichung (5) ein, erhält man den folgenden Zusammenhang, der lediglich eine begrenzte Anzahl von Matrix- Multiplikationen und eine Potenzierung einer Diagonalmatrix voraussetzt, wobei das Potenzieren der Diagonalmatrix gegenüber den Matrix-Multiplikationen insbesondere der Gleichung (5) eine deutlich geringere Rechenleistung und Rechenzeit erfordert:

(7).

Nachdem die erforderliche Anzahl von n Unterteilungen vorgenommen wurde, kann das resultierende reguläre Netz 20 auf Basis der das Netz 20 definierenden Kontrollpunkte 12 mittels einer bikubischen B-Spline Flächenstückevaluation ausgewertet werden. Diese Punkte, die zum Beispiel in Figur 2c für eines der regulären Netze 20 wellenförmig umrissen sind, können aus der Matrix C _n mittels einer sogenannten Auswahlmatrix P _k (auch Aufnahmematrix oder Englisch„picking matrix“) extrahiert werden, die bei einer Multiplikation mit C _n die benötigten Punkte in der korrekten Reihenfolge ausgibt

Hintergründe, um die Auswahlmatrizen P _k zu berechnen, wobei je Flächenstück k=1 , 2, 3 aus Figur 3 eine eigene dazugehörige Auswahlmatrix P _K definiert werden kann, sind zum Beispiel in der wissenschaftlichen Arbeit von Jos Stam auf Seite 19 angegeben. Für einen auszuwertenden Ort p mit den Koordinaten u und v in dem u, v-Parameterraum aus Figur 3, kann folglich folgender Zusammenhang definiert werden, wobei die

Kontrollpunkte des dazugehörigen regulären Netzes 20 bzw. regulären Flächenstücks mit den B-Spline Basisfunktionen N (u, v) an diesen Kontrollpunkten multipliziert werden:

Da die Basisfunktionen Koordinaten und/oder Eigenschaften an den Kontrollpunkten (zum Beispiel Materialeigenschaften wie eine Dichte oder Temperaturleitfähigkeit) angeben und/oder interpolieren können, kann mittels Gleichung (9) ein Auswerten des Ortes p an u, v im Sinne eines Ermittelns von dessen Koordinaten und/oder Eigenschaften vorgenommen werden. Der Ausdruck aus Gleichung (1 1 ) kann ferner als bivariate Subdivisionsbasisfunktion bezeichnet werden.

Im Ergebnis wird somit die Auswertung eines beliebigen Ortes in einem gegebenenfalls auch irregulären Ausgangs-Kontrollpunktnetz 10 ermöglicht, wofür lediglich die Anzahl der erforderlichen Unterteilungen n bestimmt werden muss. Dies kann zum Beispiel mittels Figur 3 und insbesondere einer mathematischen Beschreibung oder tabellarischen Zusammenfassung der dort gezeigten Zusammenhänge erfolgen (beispielsweise eine Tabelle, in der die erforderlichen Unterteilungen n und optional auch ein relevantes Flächenstück k in Abhängigkeit der u, v- Koordinaten eines auszuwertenden Ortes gespeichert sind). Alternativ kann die Anzahl erforderlicher Unterteilungen n mittels folgender Gleichung bestimmt werden: n [min

Ein wesentlicher Teil der Gleichung (1 1 ) bzw. (10) kann vorab berechnet und in einem Speicher hinterlegt werden. In der wissenschaftlichen Arbeit von Stam (sh. S. 1 1 -12) wird insbesondere das Vorberechnen der Ausdrücke V ^_T und V P für k = 1 , 2, 3 detailliert erläutert. In der DE 699 15 837 T2 wird eine computergestützte Implementierung der geschilderten Berechnungen insbesondere ab Absatz [0080] beschrieben. Demnach ist für die tatsächliche Berechnungszeit hauptsächlich oder ausschließlich das Potenzieren der Diagonalmatrix L in Abhängigkeit der Unterteilungsschritte n maßgebend, was jedoch eine vergleichsweise aufwandsarme Rechenoperationen mit einer im Wesentlichen konstanten Rechenzeit darstellt. Die insgesamt erforderliche Berechnungszeit kann somit unabhängig von der Anzahl n der benötigten lokalen Unterteilungsschritte im

Wesentlichen konstant ausfallen, was jedoch, wie bereits erwähnt, mit den bisherigen Ansätzen nur für zweidimensionale Fälle möglich ist.

Eine zusätzliche Besonderheit sowohl bei zweidimensionalen als auch bei

dreidimensionalen Subdivisionsmodellen stellen sogenannte scharfe Kanten dar (auch als Falten bezeichnet, englisch: crease edges). Diese können von einem Bediener zum Beispiel bei dem Erstellen eines Ausgangsnetzes definiert werden. Sie beschreiben allgemein Kanten 14 innerhalb eines Kontrollpunktnetzes 10, an denen keine mit voranschreitenden Unterteilungen bzw. Subdivisionen üblicherweise einhergehende Glättung (d. h. feinere Unterteilung) gewünscht ist. Details zu der Definition von scharfen Kanten und den dort anzuwendenden besonderen Unterteilungsregeln finden sich in der folgenden wissenschaftlichen Arbeit (sh. insbesondere dortige Seiten 102-105 und 122 ff.): Sven Havemann:“Generative Mesh Modeling”, Doktorarbeit 2005, abrufbar unter https://publikationsserver.tu-braunschweig.de/receive/dbbs_m ods_00000008).

Für scharfe Kanten werden ebenfalls in der wissenschaftlichen Arbeit von Havemann erläuterte scharfe Basisfunktionen betrachtet (englisch:„crease basis functions“). Diese ersetzen die üblichen Basisfunktionen aus zum Beispiel Gleichung (9) beim Auswerten von Flächenstücken, welche entsprechende scharfe-Kanten enthalten. Scharfe-Kanten in volumetrischen Modellen können allgemein analog zu scharfen-Kanten in

zweidimensionalen Modellen behandelt werden, weshalb im Folgenden beispielhaft von einem zweidimensionalen Fall ausgegangen wird.

Eine Herleitungsmöglichkeit einer scharfe-Kante-Funktion wird nachstehend erläutert und beruht auf den Beobachtungen in der wissenschaftlichen Arbeit von Havemann, wonach scharfe-Kanten gleichbedeutend mit bzw. gleiche Wirkungen haben wie eine Extrapolation einer Kante an deren Endpunkt. Es wird ferner verwiesen auf folgende Artikel: SCHWEITZER J. E.: Analysis and Application of Subdivision

Surfaces. PhD thesis, 1996; ZORIN D., KRISTJANSSON D.: Evaluation of piecewise smooth subdivision surfaces. The Visual Computer 18, 5-6 (2002), 299-315; KOSINKA J., SABIN M. A., DODGSON N. A.: Semi-sharp creases on subdivision curves and surfaces. In Computer Graphics Forum (2014), vol. 33, Wiley Online Library, S. 217-226.

Bezugnehmend auf Figur 5a-b ist im linken Fall eine von Kontrollpunkten pi-p ₄ definierte gestrichelt dargestellte B-Spline-Kurve gezeigt, wobei die Kontrollpunkte pi-p ₃ kollinear und gleich voneinander beabstandet oder auch gleich voneinander entfernt sind. Der Kontrollpunkt pi stellt hingegen das Resultat der Extrapolation von p ₃ über p ₂ dar.

Insgesamt kann somit der folgende Zusammenhang aufgestellt werden:

P1 - P2 = P2 - P ₃ (12).

Die von pi zu p ₂ verlaufende Kante 14 ist dabei eine Extrapolation der Kante 14, die von P ₃ zu p ₂ verläuft. Die entsprechende B-Spline-Kurve bzw. scharfe-Kantenfunktionen c kann daher wie folgt formuliert werden, wobei in dem abschließenden Spaltenvektor die B-Spline-Basisfunktion stehen (eine pro Kontrollpunkt pi-p ):

(13).

Ersetzt man in dieser Gleichung (13) pi durch 2 x p ₂ - p ₃ basierend auf Gleichung (12), erhält man Folgendes:

(14). Mittels dieser Funktion kann dasselbe Kurvensegment aus Figur 5a mit nur drei

Kontrollpunkten definiert werden, wie entsprechend in Figur 5b gezeigt. Die in der dazugehörigen Gleichung (14) enthaltenen kubischen Funktionen stellen die scharfe- Kanten-Basisfunktionen dar, wobei erstere bei einem Wert von u=0 den Wert 1 annimmt und bei größeren u-Werten abnimmt.

Im Folgenden wird auf die erfindungsgemäß vorgeschlagenen neuen Ansätze

eingegangen, um beliebige Orte auch in volumetrischen Subdivisionsmodellen und nicht nur in zweidimensionalen Subdivisionsmodellen bzw. in deren Flächenstücken auswerten zu können.

Wie auch im zweidimensionalen Fall, bestehen volumetrische Subdivisionsmodelle aus Kontrollpunkten, Kanten und hiervon begrenzten Flächen. Weiterhin umfassen sie Zellen, die jeweils durch einen Satz von Flächen begrenzt werden. Ein Volumenanteil des Modells, in dem eine Auswertung stattfinden soll, wird im Folgenden auch als

Volumenelement bezeichnet. Einen Sonderfall stellen ferner Zellen dar, die in äußeren Randbereichen des Modells liegen und bei denen zumindest einige der Flächen

Grenzflächen zur Umgebung darstellen. Diese Zellen können auch als Grenzzellen bezeichnet werden.

Weiterhin sind im volumetrischen Fall extraordinäre bzw. irreguläre Kontrollpunkte als Punkte definiert, die eine von sechs verschiedene Valenz aufweisen. Zudem existieren auch extraordinäre bzw. irreguläre Kanten, die eine von vier verschiedene Valenz aufweisen. In diesem Fall ist die Valenz als die Anzahl von an die Kante angrenzenden Flächen definiert oder, mit anderen Worten, als die Anzahl von Flächen, welche von der Kante ausgehen und/oder über diese verbunden sind.

Ein trivialer Fall für die Auswertung beliebiger Orte in einem volumenmetrischen

Subdivisionsmodell tritt dann ein, wenn der auszuwertende Ort in einer regulären Zelle 52 ohne irreguläre Kontrollpunkte und/oder irreguläre Kanten liegt. Für eine solche Zelle 52 kann eine Nachbarschaft des Modells in Form eines Volumenelements 50 betrachtet werden, das von 4 x 4 x 4 Kontrollpunkten 12 bzw. 3 c 3 c 3 Zellen 52 aufgespannt wird. Ein solcher Fall ist in Figur 6 gezeigt, wobei erneut nicht sämtliche der vorstehend oder nachstehend erwähnten Elemente mit einem entsprechenden Bezugszeichen versehen sind (gleiches gilt auch für die nachfolgenden weiteren Figuren).

In Figur 6 erkennt eine zentrale Zelle 52, die von sechs Flächen 54 begrenzt wird, wobei jede Fläche 54 von vier Kontrollpunkten 12 samt diese Kontrollpunkte 12 verbindenden Kanten 14 aufgespannt wird. Jeder Kontrollpunkte 12 einer Fläche 54 ist dabei mit zwei der anderen Kontrollpunkte 12 dieser Fläche 54 mittels Kanten 14 verbunden. In dieser Zelle 52 befindet sich der in dem gezeigten Beispiel auszuwertende Ort, weshalb um diese Zelle 30 die entsprechende Nachbarschaft aus 4 x 4 x 4 Kontrollpunkten 12 bzw. 3 x 3 x 3 Zellen 52 in Form des Volumenelements 50 betrachtet wird. Es versteht sich, dass das Subdivisionsmodell aus zahlreichen weiteren Volumenelementen 50 bestehen kann, die an das in Figur 6 gezeigte Volumenelement 50 entsprechend angrenzen können.

In diesem Fall kann eine Auswertung auf Basis trivariater B-Spline Basisfunktionen stattfinden. Dabei werden drei Dimensionen bzw. Parameter u, v, w eines

zellenbezogenen Koordinatensystems 57 betrachtet, dass sich genauer gesagt auf die den auszuwertenden Ort enthaltende zentrale Zelle 52 bezieht. Die Parameter u, v, w dieses Koordinatensystem 57 können jeweils Werte von null bis eins annehmen. Auf Basis der 64 Kontrollpunkte p des gezeigten Volumenelements 50 kann ein beliebiger Ort e in der zentralen Zelle 52 unter Berücksichtigung der jeweils von den Kontrollpunkten p definierten Basisfunktionen wie folgt ausgewertet werden:

Dabei sind die trivariaten Basisfunktionen N,(u, v, w) am i-ten Kontrollpunkt gemäß der nachfolgenden Gleichung (16) , die auch der vorstehend genannten Gleichung (3) entspricht, als ein Produkt von drei univariaten B-spline Basisfunktionen definiert, wobei die eckigen Klammern erneut einen Aufrund-Operator und das %-Zeichen einem Modulo- Operator bezeichnen: Das Auswerten eines Ortes in der in Figur 5 gezeigten Zelle 30 ist somit ohne erheblichen Rechenaufwand und an sich in einer konstanten Berechnungszeit möglich. Erneut können die Basisfunktionen dabei Koordinaten und/oder Eigenschaften von bzw. an den entsprechenden Kontrollpunkten p durch Interpolation angeben.

Dies gilt nicht ohne Weiteres für den irregulären Fall, der sich dadurch auszeichnet, dass ein betrachtetes Volumenelement 50 des Subdivisionsmodells und insbesondere eine Zelle 52 hiervon, die den auszuwertenden Ort enthält, kein reguläres 4 4 4-Netz definiert, beispielsweise da es extraordinäre Knotenpunkte 12 und/oder extraordinäre Kanten 14 umfasst. Eine wesentliche Erkenntnis, auf der die folgende Erfindung aufbaut, ist das derartige irreguläre Elemente 50 unter Berücksichtigung einer Ausrichtung der irregulären Kante dennoch mit einem vertretbaren Rechenaufwand auswertbar sind. Insbesondere wurde erkannt, dass derartige Elemente 50 zumindest dann, wenn sie lediglich eine irreguläre Kante aufweisen, nach einem weiteren Unterteilungsschritt nur noch in zwei Dimensionen irregulär sind und in der Dritten regulär (zum Beispiel irregulär in u und v und regulär w). Eine solche nur noch in zwei Dimensionen irreguläre Struktur eines Volumenelements 50 wird im Folgenden auch als geschichtete Struktur bezeichnet. Ist eine Mehrzahl von irregulären Kanten vorhanden, muss anhand der nachfolgend erläuterten Figur 9 die notwendige Anzahl n von Unterteilungsschritten ermittelt werden, bis die geschichtete Struktur erhalten wird, wobei diese Unterteilungen durch Berechnung der Eigenstruktur der Subdivisionsmatrix in einer konstanten Berechnungszeit

(rechnerisch) durchgeführt werden können.

Im Folgenden wird zunächst von eben diesem Fall ausgegangen, dass noch keine geschichtete Struktur vorliegt und wird aufgezeigt, wie man in einer konstanten

Berechnungszeit zu dieser gelangen kann. Da erfindungsgemäß aber auch von bereits geschichteten Strukturen ausgegangen werden kann, sind diese Maßnahmen nicht zwingend.

Für das Durchführen von Unterteilungsschritten wird vorzugsweise eine Nummerierung oder, mit anderen Worten, Indexierung der Kontrollpunkte vorgenommen, sodass die Topologie des die auswerten Zelle enthaltenden Kontrollpunktnetzes bei jedem

Unterteilungsschritt konsistent bleibt. In diesem Zusammenhang wurde von den Erfindern zunächst erkannt, dass im Gegensatz zum zweidimensionalen Fall keine Nummerierung allein in Abhängigkeit einer Valenz des Kontrollpunktes möglich ist, insbesondere da die Topologie in der Nachbarschaft des irregulären Punktes beliebig sein kann. Stattdessen werden ausgehend von der irregulären Kante 15 und bezogen auf einen irregulären Kontrollpunkt 18, der gemäß nachstehend anhand von Figur 7b erläuterten Regeln auszuwählen ist, die Nummerierungen gemäß der folgenden Reihenfolge vergeben, wie sich auch aus den Figuren 13a-g verdeutlicht (d. h. die kontrollpunktspezifischen

Nummerierungen bzw. Indexe werden für die einzelnen Kontrollpunktgruppen gemäß nachstehender Reihenfolge aufsteigend vergeben). In diesen Figuren 13a-g sind die irregulären Kanten gestrichelt dargestellt.

1. In Figur 13a ist das lokale Koordinatensystem der Zelle gezeigt und der

ausgewählte irreguläre Kontrollpunkt, der mit 0 nummeriert wird. Von diesem verlaufen irreguläre gestrichelt dargestellte Kanten mit der Valenz drei in alle drei Koordinatenrichtungen u, v und w. Wie in Figur 13b gezeigt, werden sämtliche Kontrollpunkte aufsteigend nummeriert, die ausgehend von diesem Punkt durch Abfahren einer einzelnen Kante in dem die irreguläre Zelle enthaltenden

Kontrollpunktnetz (auch lokales Kontrollpunktnetz genannt) erreichbar sind oder, anders ausgedrückt, um eine Kante bzw. eine Kantenlänge von der irregulären Kante beanstandet sind. Diese Kontrollpunkte können auch als direkte Nachbarn der extraordinären Kante bezeichnet werden und sind in Figur 13b mit 1 bis 3 nummeriert. Bildlich gesprochen teilen sich die Punkte 1 bis 3 mit dem irregulären Kontrollpunkt 0 eine gemeinsame Kante.

2. Beginnend mit der auf den letzten Kontrollpunkt der Gruppe 1 nachfolgenden Nummer werden sämtliche Kontrollpunkte aufsteigend nummeriert, die durch Abfahren von zwei aufeinanderfolgenden bzw. aneinander anschließenden Kanten in dem die irreguläre Zelle enthaltenden Kontrollpunktnetz (auch lokales

Kontrollpunktnetz genannt) erreichbar sind oder, anders ausgedrückt, um zwei Kanten bzw. Kantenlängen von der irregulären Kante beanstandet sind (sh. 4 bis 10 in Figur 13c). Weiter wird bei diesen Kontrollpunkten vorausgesetzt, dass sie eine Fläche mit der irregulären Kante teilen (also eine gemeinsame Fläche mit der irregulären Kante begrenzen oder dieser zuzuordnen sind). 3. Beginnend mit der auf den letzten Kontrollpunkt der Gruppe 2 nachfolgenden Nummer werden sämtliche Kontrollpunkte aufsteigend nummeriert, die durch Abfahren von drei aufeinanderfolgenden bzw. aneinander anschließenden Kanten in dem die irreguläre Zelle enthaltenden Kontrollpunktnetz (auch lokales

Kontrollpunktnetz genannt) erreichbar sind oder, anders ausgedrückt, um drei Kanten bzw. Kantenlängen von der irregulären Kante beanstandet sind (sh. 1 1 bis 14 in Figur 13d). Weiter wird bei diesen Kontrollpunkten vorausgesetzt, dass sie eine Zelle mit der irregulären Kante teilen (also eine gemeinsame Zelle mit der irregulären Kante begrenzen oder dieser zuzuordnen sind).

4. In Fig. 13e werden anschließend die Kontrollpunkte der unteren Schicht mit 15 bis 21 nummeriert. Der entlang der w-Achse aus Fig. 13a betrachtet auf einer Linie mit dem Kontrollpunkt 0 liegende Kontrollpunkt dieser Schicht wird mit 15 nummeriert. Ausgehend hiervon werden die diesen Punkt 15 umgebenden, nicht notwendigerweise direkt über eine Kante hiermit verbundenen Punkte mit 16 bis 21 nummeriert. Bildlich gesprochen werden ausgehend von Punkt 15 dessen umliegende Punkte sternförmig nummeriert.

5. In Fig. 13f wird der entlang der v-Achse auf einer Linie mit dem Kontrollpunkt 0 liegende Kontrollpunkt der rechten (äußeren) Schicht mit 22 nummeriert.

Ausgehend hiervon werden die diesen Punkt 22 umgebenden, nicht

notwendigerweise direkt über eine Kante hiermit verbundenen Punkte mit 23 bis 31 nummeriert. Bildlich gesprochen werden ausgehend von Punkt 22 dessen umliegenden Punkte sternförmig nummeriert.

6. In Fig. 13g wird ein entlang der u-Achse auf einer Linie mit dem Kontrollpunkt 0 liegender Kontrollpunkt der hinteren (äußeren) Schicht mit 32 nummeriert.

Ausgehend hiervon werden die diesen Punkt 32 umgebenden, nicht

notwendigerweise direkt über eine Kante hiermit verbundenen Punkte mit 33 bis 45 nummeriert. Bildlich gesprochen werden ausgehend von Punkt 32 dessen umliegenden Punkte sternförmig nummeriert.

Zur Wahrung der Konsistenz beim Durchführen von Unterteilungsschritten ist es erforderlich, dass der Index eines jeden Kontrollpunktes und seines korrespondierenden unterteilten Kontrollpunktes beibehalten wird. Unter der Korrespondenz kann in diesem Fall verstanden werden, dass die Anordnung der Kontrollpunkte rund um die irreguläre Kante bei einer lokalen Subdivision konstant bzw. gleichartig bleibt. Zwar werden bei der Subdivision neue Kontrollpunkte erzeugt, diese weisen jedoch bezogen auf die (ebenfalls unterteilte) irreguläre Kante die gleiche Anordnung/Struktur auf wie die

Ausgangskontrollpunkte vor der Subdivision. Kontrollpunkte vor und nach der Subdivision, die analoge Strukturen aufweisen bzw. definieren, können daher als zueinander korrespondierend bezeichnet werden.

Unter der Annahme, dass das Kontrollpunktnetz ausschließlich hexaedrische Zellen umfasst, kann ferner folgendes für die gemäß der Reihenfolge 1 bis 3 nummerierten Kontrollpunkte angenommen werden:

Für jeden Kontrollpunkt in dem lokalen Kontrollpunktnetz, der eine Kante, Fläche oder Zelle mit der irregulären Kante teilt, ist der korrespondierende Kontrollpunkt in dem unterteilten Kontrollpunktnetz entsprechend ein Kantenpunkt, ein

Flächenpunkt oder ein Zellenpunkt, je nachdem, welches Element mit der irregulären Kante geteilt wird. Die Begriffe Kantenpunkt, Flächenpunkt und

Zellenpunkt gehen auf die herkömmlichen Subdivisionsregeln für Catmull-Clark- Oberflächen bzw. -Volumen zurück, die oben diskutiert wurden und für die auch entsprechende Zitatstellen genannt sind. Ein Kantenpunkt ist ein neuer Punkt, der beim Durchführen eines Subdivisionsschrittes auf einer Kante erzeugt wird, um diese zu unterteilen. Für Flächen- und Zellenpunkte gilt analoges. Für jede Zelle wird z.B. nach den Catmull-Clark-Regeln beim Subdividieren ein Zellenpunkt im arithmetischen Mittelpunkt der Zelle erzeugt.

Die Gewichte der korrespondierenden unterteilten Kontrollpunkte befinden sich in der Reihe i der Unterteilungsmatrix, wobei i der zugeordnete Index des

ursprünglichen Kontrollpunkts in dem lokalen Kontrollpunktnetz ist. Das

Verwenden von Gewichten geht ebenfalls auf die herkömmlichen

Subdivisionsregeln für Catmull-Clark-Oberflächen bzw. -Volumen zurück, die oben diskutiert wurden und für die auch entsprechende Zitatstellen genannt sind.

Darauf basierend kann dann der Block der Unterteilungsmatrix, welcher den

Kontrollpunkten in der direkten Nachbarschaft des irregulären Kontrollpunktes entspricht, zusammengestellt werden. Exakte Formulierungen für Unterteilungsregeln und zum allgemeinen Aufstellen von Unterteilungsmatrizen finden sich in den vorstehend genannten wissenschaftlichen Artikel von Joy und MacCracken. Dort sind auch die Catmull-Clark-Regeln enthalten, wie vorstehend genannt.

Anschließend werden die verbleibenden Kontrollpunkte betrachtet, die keine Kante, Fläche oder Zelle mit der irregulären Kante teilen. Diese Kontrollpunkte bilden die drei äußeren Schichten des Kontrollpunktnetzes, wobei jede Schicht ein zweidimensionales Kontrollpunktnetz bildet. Dies ist in Figur 8b ersichtlich, bei der als äußere Schichten eine unterste Schicht 56a (in Fig. 8b die Basisschicht), eine frontale Schicht 56b, die in der Figur dem Betrachter direkt zugewandt ist, und eine in der Figur rechte äußere Schicht 56c gezeigt sind. Die unterste und frontale Schicht 56a, b umfassen jeweils einen Kontrollpunkt 18 mit der Valenz 5 (siehe jeweils für diese Schichten 56a, b markierten irregulären Punkte 18 mit einer entsprechenden Valenz). Für diese Schichten 56a, b kann daher wie im zweidimensionalen Fall aus Figur 4 vorgegangen werden und eine

Nummerierung nach Maßgabe eines Abstandes zu dem irregulären Punkt 18 erfolgen. Die rechte Schicht 56c umfasst keinen irregulären Kontrollpunkt und definiert ein reguläres zweidimensionales Kontrollpunktnetz.

Für die Kontrollpunkte 12 der äußeren Schichten 56a, 56b können daraufhin der die entsprechenden Zeilen in der Subdivisionsmatrix in einer herkömmlichen Weise erzeugt werden. Dabei muss berücksichtigt werden, dass diese drei äußeren Schichten jeweils vier Kontrollpunkte 12 in dem Ausgangskontrollpunktnetz und fünf in dem unterteilten Kontrollpunktnetz teilen, um zu verhindern, dass diese Kontrollpunkte doppelt berücksichtigt werden. Weiter kann das betrachtete (lokale) Kontrollnetz entlang der Nachbarschaftsbeziehungen (was auch als nachstehend erläuterte lokale

Nachbarschaften oder topologische Informationen bezeichnet wird) traversiert werden, z.B. mittels einer hierfür geschaffenen volumetrischen Datenstruktur. Beim Erstellen der oben beschriebenen Nummerierung werden diese Informationen berücksichtigt und das Kontrollnetz anhand der Nachbarschaften traversiert.

Für jede Reihe der Subdivisionsmatrix können die Gewichte und deren entsprechender Spaltenindex durch Untersuchen der lokalen Nachbarschaft des entsprechenden Kontrollpunktes 12 ermittelt werden. Die Kontrollpunkte 12, welche die Position eines unterteilten Kontrollpunktes 12 beeinflussen, können durch Verwenden der topologischen Informationen bestimmt werden, die in der volumetrischen Datenstruktur enthalten sind. Die topologischen Informationen können z.B. angeben, welche Kontrollpunkte miteinander verbunden sind oder sich eine Fläche, Zelle oder Kante teilen.

Schließlich wird durch Zuordnen der entsprechenden Kontrollpunkte 12 zu ihrem entsprechenden Index in dem aktuellen Kontrollpunktnetz 12 der Spaltenindex die entsprechenden Gewichte erhalten.

Da mit der entsprechend nummerierten Unterteilungsmatrix keine nachstehend erläuterten Richtungswechsel beim Durchführen von rechnerischen Unterteilungen erforderlich sind, kann zum Durchführen der Unterteilungen auf die Diagonalmatrix zurückgegriffen werden, welche die Eigenwerte enthält, wie vorstehend im

Zusammenhang mit den Gleichungen (5) - (7) erläutert.

Um die Eigenstruktur zu berechnen, wird die M x K - Unterteilungsmatrix in eine quadratische Matrix durch Entfernen der letzten M - K (d.h. M weniger K) Reihen umgewandelt, wobei K die absolute Anzahl von Kontrollpunkten in dem ursprünglichen und M die absolute Anzahl von Kontrollpunkten in dem unterteilten Kontrollpunktnetz ist. Die entfernten Reihen entsprechender dabei den drei äußeren Schichten des unterteilten Kontrollpunktnetzes. Unter Berücksichtigung, dass diese Schichten jeweils fünf

Kontrollpunkte miteinander teilen, beträgt die Anzahl von Kontrollpunkten in diesen Schichten:

M-K= 2 (Ni + N ₂ + N ₃ ) + 37, wobei Ni die Valenz der irregulären Kante ist, die benachbart zu der i-ten äußeren Schicht ist. Für das Kontrollpunktnetz in Figur 8b gilt zum Beispiel N _I =N ₂ = 5 und N ₃ = 4.

Im Folgenden wird auf konkrete Beispiele von auszuwertenden Kontrollpunktnetzen eingegangen.

In Figur 7b ist ein Beispiel eines volumetrischen Kontrollpunktnetzes 10 gezeigt, dass irreguläre Kanten 15 mit einer Valenz von drei aufweist. Dies betrifft insbesondere die zentrale Zelle 52, welche den auszuwertenden Ort enthält. Man erkennt unmittelbar, dass für diese Zelle 32 keine reguläre Nachbarschaft vorliegt, wie dies in Figur 6 gezeigt ist.

Das gezeigte Beispiel kann als volumetrische Version des in Figur 7a gezeigten irregulären zweidimensionalen Flächennetzes verstanden werden. In Figur 8b ist hingegen ein Beispiel eines volumetrischen Netzes gezeigt, dass irreguläre Kanten 15 (und insbesondere eine zentrale Zelle 52 mit einer solchen Kante 15) mit einer Valenz von fünf aufweist. Dieses Beispiel kann als volumetrische Version des in Figur 8a gezeigten irregulären zweidimensionalen Flächennetzes verstanden werden.

Wie erwähnt, soll in den Beispielen aus Figur 7b und 8b eine Auswertung an einem Ort stattfinden, der in der inneren zentralen Zelle 52 liegt und für die erneut ein

Volumenelement 50 in Form einer lokalen Nachbarschaft um die innere Zelle 52 definiert wird. In dem gezeigten Zustand stellt das Volumenelement 50 bzw. diese Nachbarschaft noch keine reguläre Anordnung aus 4 x 4 x 4 Kontrollpunkte 12 oder 3 c 3 c 3 Zellen dar. Dies ist insbesondere deshalb der Fall, da die Zelle 52 noch einen irregulären Punkt 18 enthält.

Um das Netz des irregulären Elements 50 und insbesondere die irreguläre Zelle 52 aus Figur 7b (rechnerisch) weiter zu unterteilen, so dass eine geschichtete und gemäß nachstehenden Gleichung auswertbare geschichtete Struktur erhalten wird, muss zunächst einer der darin enthaltenen irreguläre Kontrollpunkt 18 ausgewählt werden. Hierbei handelt es sich um einen der Endpunkte einer irregulären Kante 15, die von der Zelle 52 umfasst ist, und vorzugsweise denjenigen irregulären Kontrollpunkt 18, an dem mehrere oder auch sämtliche irreguläre Kanten 15 zusammenlaufen. Genauer gesagt wird im Fall einer Mehrzahl von irregulären Kanten 15, die eine gemeinsame Zelle 52 begrenzen, allgemein derjenige irreguläre Kontrollpunkt 18 ausgewählt, an dem sämtliche irregulären Kante 15 der Zelle 52 zusammenlaufen. Kann bei einer Mehrzahl von irregulären Kanten 15 kein solcher Kontrollpunkt 18 aufgefunden werden, an dem sämtlichen irregulären Kanten 15 Zusammentreffen, können weitere Unterteilungsschritte durchgeführt werden, bis dieser Zustand erreicht ist. Allgemein ist darauf hinzuweisen, dass eine Kante 14, 15 in dem gezeigten Beispiel derart definiert ist, dass sie sich zwischen zwei Kontrollpunkten 12 aber nicht durch mehrere Kontrollpunkte 12 hindurch erstreckt. Anschließend kann basierend auf vorstehenden Regeln zum Definieren einer Unterteilungsmatrix die geschichtete Struktur erhalten und kann diese dann weiter ausgewählt werden. In Figur 7b ist erneut ein u, v, w-Koordinatensystem 57 zum Beschreiben von Orten in der Zelle 52 definiert. Man erkennt, dass sich die irreguläre Kante 15 entlang der w-Achse dieses Koordinatensystem 57 erstreckt. Dies wird dadurch erreicht, dass in einem ersten Schritt zunächst die Ausrichtung der irregulären Kante 15 in dem entsprechenden Koordinatensystem 57 ermittelt wird. Dies kann aus dem das Subdivisionsmodell definierenden Datensatz ermittelt werden (oder auch durch manuelle Benutzereingaben). Weiterhin wird eine bevorzugte Achse (in diesem Fall w) angegeben, entlang derer sich die irreguläre Kante 15 erstrecken soll. Wird eine Relativabweichung von der irregulären Kante 15 und dieser Achse w zum Beispiel in Form eines Winkels hierzwischen festgestellt, können das Subdivisionsmodell und/oder das Koordinatensystem 57 relativ zueinander verdreht werden. Vorzugsweise erflogt eine Definition des

Koordinatensystems 57 von vornherein aber in der Weise, dass eine solche

Relativabweichung nicht auftritt. Auch dies kann rechnerisch mittels entsprechender Koordinatentransformationen erfolgen. Alternativ kann ohne eine etwaige Veränderung des Subdivisionsmodells (zum Beispiel ohne Veränderung von dessen Ausrichtung) das Koordinatensystem 57 von vornherein derart definiert werden, dass dessen w-Achse entlang der irregulären Kante 15 verläuft. Der in Figur 7b gezeigte Zustand stellt das Endergebnis derartiger Maßnahmen dar. Gleiches gilt auch für Figur 8b, wobei die w- Achse des Koordinatensystem 57 analog zu dem leicht schrägen Verlauf derjenigen ausgewählten irregulären Kante 15 geneigt ist, welche die auszuwertende Zelle 52 begrenzt (in der lediglich schematischen Figur 8b gegebenenfalls nicht eindeutig zu erkennen).Zu beachten ist ferner, dass die sich orthogonal zu der irregulären Kante 15 erstreckenden Ebenen in u und v im Folgenden jeweils als einzelne Schichten 56 des Volumenelements 50 bezeichnet werden.

Analog zu dem zweidimensionalen Fall und wie dort beispielsweise anhand von Figur 3 erläutert, muss auch in dem dreidimensionalen Fall die auszuwertende Zelle 52 lokal zusätzlich unterteilt werden, da sie zunächst den irregulären Punkt 18 enthält und somit nicht mittels Basisfunktionen in üblicher Weise auswertbar ist (d. h. nicht gemäß

Gleichung (15) auswertbar ist). Für die entsprechende Unterteilung wird die nachfolgend erläuterte Figur 9 herangezogen. Allgemein können die Unterteilungsregeln gemäß Catmull-Clark, die zum weiteren Unterteilen der irregulären Zelle 52 verwendet werden, in einer Unterteilungsmatrix (oder Subdivisionsmatrix) mit, zumindest wenn bereits geschichtete Strukturen vorliegen, der Größe 5M x 4K zusammengefasst werden, wobei K der Anzahl von Kontrollpunkten 12 pro Schicht 56 des Kontrollpunktnetzes 10 bzw. Volumenelements 50 und M der

Kontrollpunktanzahl des entsprechend unterteilten Netzes 1 1 entspricht. Es ist darauf hinzuweisen, dass diese Zahlenwerte aber nur stimmen, wenn bereits von einer geschichteten Struktur ausgegangen wird und ansonsten auf die vorstehende alternative Formulierung der M x K-Matrix zurückgegriffen werden müsste. Pro zusätzlicher lokaler Unterteilung (oder, mit anderen Worten, pro zusätzlicher lokaler Subdivision) entstehen acht neue Unterelemente in Form von kleinvolumetrischen Zellen 52 ausgehend von der in Figur 7b gezeigten Zelle 52.

In dem zweidimensionalen Fall führt eine zusätzliche lokale Subdivision dazu, dass sämtliche zusätzlich erhaltenen Flächenstücke regulär werden, mit Ausnahme desjenigen, welches den irregulären Punkt enthält (siehe jeweilige reguläre Flächenstücke k= 1 , 2, 3 in Figur 3 sowie jeweils verbleibende Flächenstücke, die den irregulären Punkt bei 0,0 enthalten). In dem volumetrischen Fall resultiert die zusätzliche lokale Subdivision in sechs Unterelementen (bzw. Zellen 52), die regulär werden, während zwei irreguläre Zellen verbleiben, die nach wie vor die irreguläre Kante 15 enthalten bzw. an dieser angrenzen. Zusätzliche Unterteilungen dieser irregulären Unterelemente würden den Volumenanteil der regulären Zellen erhöhen, jedoch nicht zu einer vollständigen

Auflösung der irregulären Zellen 52 führen.

Der Zusammenhang zwischen der Anzahl zusätzlich erforderlicher Unterteilungsschritte n=1...4 und den daraus resultierenden Unterelementen k=1 ...8 in Abhängigkeit der Parameter u, v, w eines auszuwertenden Ortes ist in Figur 9 dargestellt, wobei n auch deutlich größere Werte annehmen und prinzipiell auch unendlich sein kann. Figur 9 stellt die volumetrische Variante oder auch volumetrische Erweiterung von Figur 3 dar.

Alternativ kann auf die im allgemeinen Beschreibungsteil zitierte Formel zurückgegriffen werden. Bei Figur 9 befindet sich der irreguläre Kontrollpunkt 18 an der Position 0, 0, 0. Die irreguläre Kante 15 erstreckt sich ausgehend hiervon entlang der w-Achse. Diese Zuordnung wird durch die Definition des Koordinatensystem 57 erreicht, welche auf Basis der vorab ermittelten Ausrichtung der irregulären Kante 15 erfolgt. Eine zumindest theoretische Möglichkeit, um einen beliebigen Ort in einer irregulären Zelle 52 auszuwerten wäre, diese bzw. dessen Nachbarschaft in Form des

Volumenelements 50 so oft weiter zu unterteilen, bis der auszuwertenden Ort innerhalb einer vollständig regulären Zelle 52 liegt. Falls sich ein auszuwertender Ort nahe einer irregulären Kante 15, aber nicht nahe zu einem extraordinären Punkt 18 befindet, müsste die Richtung der Unterteilung während des Auswertungsprozesses verändert werden.

Die Richtung der Unterteilung, die entsprechend auch als Unterteilungsrichtung bezeichnet werden kann, wird dabei allgemein durch die Werte der Zielparameter u, v, w definiert und beträgt üblicherweise (0, 0, 0). Diese Richtung bezeichnen keine Richtung im streng geometrischen Sinne. Stattdessen betrifft dies den Fall, dass für einen Ort in Figur 9 infolge iterativer Unterteilungen hin zu einer irregulären Kante, welche entlang der w-Koordinate verläuft, eine Unterteilung„in diese Richtung“ erfolgt. In dem Fall, dass ein auszuwertender Ort nahe zu einem irregulären Punkt 18 aber entfernt von der irregulären Kante 15 liegt (zum Beispiel ein Ort mit den Koordinaten (u, v, w) = (0,1 ; 0,1 ; 0,33)) muss die Richtung der Unterteilung mehrfach geändert werden, um eine lokale reguläre Struktur zu erreichen. Bei bisherigen Lösungen wie zum Beispiel von Burkhart et al. muss ein entsprechender Richtungswechsel immer dann erfolgen, sobald der Ort in dem Bereich k = 3 aus Figur 9 liegt. Bei einem Richtungswechsel ist es jedoch nicht mehr möglich, die diagonale Eigenwertmatrix zu potenzieren, sondern es muss ein neuer Matrixausdruck aufgestellt werden, was die Berechnungszeit erhöht und allgemein zu nicht konstanten Berechnungszeiten führt. Durch den hierin vorgestellten Ansatz wird dies und werden Richtungswechsel allgemein verhindert, da geschichtete Strukturen direkt auswertbar sind. Auch ohne Richtungswechsel ermöglicht die hierin vorgestellte Lösung nämlich das Erhalten einer auswertbaren geschichteten Struktur. Durch das obige

Nummerierungsschema der Unterteilungsmatrix kann ferner die Eigenstruktur der Unterteilungsmatrix erhalten und durch ein Potenzieren der Eigenwertmatrix eine konstante Berechnungszeit erreicht werden.

Zusammengefasst erhöhen Richtungswechsel, wie sie auch bei der vorstehend erwähnten wissenschaftlichen Arbeit von Burkhart et al. verwendet werden, den erforderlichen Berechnungsaufwand und führen insbesondere dazu, dass die

Berechnungszeit mit den erforderlichen zusätzlichen Unterteilungsschritten im Wesentlichen linear steigt (d. h. nicht konstant ist). Ferner können hierbei Informationen verlorengehen, die eine Rücktransformation des unterteilten Kontrollpunktnetzes 10 in dessen Ausgangszustand erschweren oder sogar unmöglich machen. Deshalb wird im vorliegend ein alternativer Auswertungsansatz für irreguläre Volumenelemente 50 samt Zellen 52 erläutert, der u. a. auf einer Unterteilungsmatrix mit dem vorstehend erläuterten Nummerierungsschema beruht.

In Fig. 10a-b ist eine Darstellung der irregulären Volumenelemente 50 aus Figur 7b und Figur 8b nach einer weiteren lokalen Unterteilung des Modells (d. h. einer Unterteilung von dessen Volumenelement 50) gezeigt (in Figur 10a das Netz aus Figur 7b und in Figur 10b das Netz aus Figur 8b). Hierbei wird von dem Fall k=3 aus Figur 9 ausgegangen. Die Kontrollpunktnetze 10 der jeweiligen Volumenelemente 52 bestehen jeweils aus vier Schichten 56, welche sich in jeweils in der u-v-Ebene (d. h. orthogonal zu der irregulären Kante 15) erstrecken, sowie entlang der w-Dimension aneinandergereiht oder, mit anderen Worten, geschichtet sind. Ferner sind wiederum die inneren Zellen 52 markiert, in denen der auszuwertende Ort liegt. Statt bis zu einem Zustand zu unterteilen, bei dem der auszuwertende Ort in einer vollständig regulären 4 x 4 x 4 Kontrollpunkt- Nachbarschaft liegt, reicht es bei der gezeigten Lösung aus, so oft zu unterteilen, bis der irreguläre Punkt 18, nicht aber die irreguläre Kante 15 außerhalb derjenigen Zelle 52 liegt, die den auszuwertenden Ort umfasst.

Man erkennt, dass innerhalb einer jeweiligen u-v-Schicht 56 nach wie vor ein irregulärer Kontrollpunkt 18 mit der Valenz von drei (Figur 10b) bzw. fünf (Figur 10a) vor allem an derselben Position enthalten ist, sodass die entsprechenden Schichten 56 jeweils irregulär sind. In der w-Dimension sind die jeweiligen Elemente jedoch regulär, da dort 4 c 4 Kontrollpunktenetze definiert werden können.

Dies macht sich die hierin offenbarte Lösung dahingehend zunutze machen, als dass die bivariaten Subdivisionsbasisfunktionen (p(u, v) gemäß der vorstehenden Gleichung (1 1 ) des zweidimensionalen Falls berechnet und mit einer regulären B-spline Basisfunktion Ni(w) multipliziert werden. Die resultierende trivariate Basisfunktion lautet: Dabei bezeichnet j die jeweiligen Kontrollpunkte in der i-ten u, v-Schicht 56. In jeder Schicht 56 ist dabei die Valenz der extraordinären Kante 15 gleich der Valenz das extraordinären Punktes 18. Dies ermöglicht das Verwenden der bisher nur für den zweidimensionalen Fall verwendeten Basisfunktionen auch im dreidimensionalen Fall. Diese Basisfunktionen können zum Beispiel in Gleichung (15) verwendet werden, um einen beliebigen Ort e mit den Koordinaten u, v, w zu bestimmen bzw. auszuwerten.

Ebenso kann basierend auf diesen Basisfunktionen und der Eigenstruktur der (gemäß vorstehendem Nummerierungsschema aufgestellten) Unterteilungsmatrix, die in Form eines zu Gleichung (7) analog Ausdrucks enthalten ist, eine Auswertung eines Ortes p basierend auf folgenden Ausdrücken erfolgen:

Dabei ist Pk eine Auswahlmatrix (engl.: picking matrix), die analog zum

zweidimensionalen Fall für k = 0,...,6 definiert ist (siehe auch Gleichung (8)). Der

Ausdruck <p (u, v, w) wird hierin auch als trivariate Subdivisionsbasisfunktion (oder trivariate Unterteilungsbasisfunktion) bezeichnet. Die Basisfunktion N aus Gleichung (17) findet sich auch in Gleichung (18) wieder, dort allerdings in Abhängigkeit des

transformierten u, v, w-Koordinatensystems sowie der nötigen Unterteilungsschritte n und des Bereiches k, in dem der auszuwertende Ort nach n Unterteilungsschritten liegt. Die obigen Gleichungen (18)-(19) stellen zu den Gleichungen (9)-(1 1 ) des zweidimensionalen Falls analoge Gleichungen für den volumetrischen Fall dar, ermöglichen jedoch

Auswertungen in konstanter Berechnungszeit. Die Gleichung (18) enthält den kompletten hier beschriebenen Prozess für die Auswertung bzw. Berechnung des Limit-Punktes p, einschließlich Aufstellen der Subdivisionsmatrix und deren Eigenstruktur, Bestimmung der Anzahl der nötigen Subdivisionsschritte n und der Bereiche k usw.

Es versteht sich, dass die geschilderte Zuordnung der w-Achse zu der irregulären

Kante 15 lediglich beispielhaft ist und dass auch jegliche der anderen u-v-Achsen oder auch gänzlich andersartig bezeichnete Achsen der irregulären Kante 15 zugeordnet werden könnten. Die Zuordnung der u, v, w-Parameter in Gleichung (17) müsste dann entsprechend angepasst werden.

Zusammengefasst wird also eine Auswertung ermöglicht, bei der zunächst eine geschichtete Struktur durch Unterteilungen ohne Richtungswechsel und somit einer konstanten Berechnungszeit erzeugt wird , wobei für diese Struktur zusätzliche lokalen Unterteilungen auf Basis der Eigenwert-Diagonalmatrix des zweidimensionalen Falles erfolgen können, die in dem Eigenbasisfunktions-Term (p(u, v) enthalten ist. Somit können erneut zumindest Teile der relevanten Matrixausdrücke vorab berechnet werden und die Rechenzeit wird maßgeblich durch das im Wesentlichen zeitkonstante Potenzieren der entsprechenden Diagonalmatrix bestimmt. Wie geschildert, wird dies dadurch ermöglicht, dass zunächst die Ausrichtung der irregulären Kante 15 ermittelt und ein lokales u, v, w- Koordinatensystem geeignet gewählt wird, um geschichtete Strukturen zu erhalten und daraufhin von dem Eigenbasisfunktions-Term (p(u, v) Gebrauch machen zu können. Vorstehend wurde lediglich die erfindungsgemäße Auswertung einer inneren Zelle 52 betrachtet. Einen Sonderfall stellen jedoch Zellen 52 und Volumenelemente 50 dar, die Grenzflächen 32 zur Umgebung umfassen. Für derartige Grenzzellen 34 bzw.

Grenzelemente 33 (ein Grenzelement 33 umfasst mehrere Zellen 52, von denen wenigstens eine Grenzzelle 34 ist) sind die in den Figuren 1 1 a-e gezeigten Fälle zu unterscheiden. Genauer gesagt sind in Figur 1 1 a und 1 1 b zwei erste Beispiele für Grenzzellen 34 gezeigt sowie in Figur 1 1 c eine hierzu korrespondierende

zweidimensionale Konfiguration. In den Figuren 1 1 d und 1 1 e sind weitere Beispiele für Grenzfälle gezeigt, für die eine korrespondierende zweidimensionale Konfigurationen Figur 1 1 f gezeigt ist.

In Figur 1 1 a ist ein erster Grenzfall gezeigt, bei dem eine an sich reguläre Struktur einer einzelne Grenzschicht 32 in Form der in dieser Figur obersten Schicht 56 aufweist (die verbleibenden Randflächen des gezeigten Grenzelements 33 grenzen an Flächen benachbarter nicht dargestellte Volumenelemente 52 an und bilden deshalb keine entsprechende Grenzschicht 32). Die Grenzschicht 32 kann in dem gezeigten trivariaten (d. h. dreidimensionalen) Fall allgemein gleichartig zu scharfen Kanten in dem bivariaten (d. h. zweidimensionalen) Fall behandelt werden, weshalb die Grenzschicht 32 in der korrespondierenden zweidimensionalen Konfiguration aus Figur 1 1 c als entsprechende scharfe Kante 17 gezeigt ist.

Insbesondere wird in den Figuren 1 1 c und 1 1 f dargestellt, dass analog zum Fall der Figuren 5a, 5b an den scharfen Kanten 17 extrapoliert werden kann, um die zur Definition einer (für den gezeigten analogen zweidimensionalen Fall) regulären 4 x 4 - Nachbarschaft fehlenden Kontrollpunkte 12 zu ergänzen (siehe entsprechend gestrichelt dargestellte Kontrollpunkte 12 und Kanten in den Figuren 1 1 c, 1 1 f). Eine solche tatsächliche Ergänzung von Kontrollpunkten 12 per Extrapolation muss nicht stattfinden, legimitiert jedoch das Verwenden der scharfe-Kanten-Basisfunktionen. Um einen Ort in der in Figur 1 1 a gezeigte Grenzzelle 34 auszuwerten, welche einen Teil der Grenzschicht 32 bildet, werden die B-spline Basisfunktionen aus der obigen

Gleichung (16) mit scharfe-Kanten-Basisfunktionen in der w-Richtung ersetzt, da dort der Rand bzw. Grenzbereich zur Umgebung vorliegt. Jede der drei einzelnen scharfe-Kanten- Funktionen aus Gleichung (14) entspricht dabei einer der Schichten 56 des

Kontrollpunktnetzes aus Figur 1 1 a, wobei die erste Funktion aus Gleichung (14), die mit dem Wert 1 beginnt, der Grenzschicht 32 entspricht. Die neuen Grenzbasisfunktionen lauten wie folgt:

Der zweite Grenzfall, der in Figur 1 1 b gezeigt ist, zeichnet sich dadurch aus, dass eine irreguläre Kante 15 orthogonal zur Grenzschicht 32 verläuft. Erneut wird dabei ein Koordinatensystem 57 derart definiert, dass dessen w-Achse entlang der irregulären Kante 15 verläuft und die u-v-Ebene parallel zu Schichten 56 des gezeigten

Grenzelements 33 verläuft, die orthogonal zu dieser Kante 15 verlaufen. Für eine

Auswertung eines Ortes in der Grenzelle 34, deren eine Kante mit der irregulären Kante 15 zusammenfällt, werden irreguläre zweidimensionale Subdivisionsbasisfunktionen in der u- und v-Dimension betrachtet und mit der scharfe-Kanten-Basisfunktionen in der w- Dimension kombiniert. Die resultierende Grenzbasisfunktionen Bi (u, v, w) lautet wie folgt, wobei i und j analog zu der vorstehenden Gleichung (17) definiert sind:

Bi j( u, V , w) = ipfi lL V)Ci(w) i 1, 3, j— 1, K (21 ).

In dem dritten Grenzfall aus Figur 1 1 d erstreckt sich eine irreguläre Kante 15 innerhalb bzw. entlang einer Grenzfläche. Mit anderen Worten ist die irreguläre Kante 15 in einer entsprechenden Grenzschicht 32 enthalten. Dies betrifft in Figur 1 1 d die mit einem entsprechenden Bezugszeichen versehene vertikale irreguläre Kante 15, die in einer von dem Betrachter abgewandten Grenzfläche 36 verläuft. Der hierzu korrespondierende zweidimensionale Fall ist in Figur 1 1 f gezeigt. Das Koordinatensystem 57 der den auszuwertenden Ort enthaltenden Grenzzelle 34, das für beide der Figuren 1 1 d und 1 1 e gilt, ist erneut derart definiert, dass die w-Achse entlang der irregulären Kante 15 verläuft. Weiterhin erstrecken sich die orthogonal zu dieser Kante 15 verlaufenden Schichten 56 der in diesen Figuren jeweils gezeigten Grenzelemente 33 parallel zu der u-v-Ebene dieses Koordinatensystem 57.

In dem Fall von Figur 1 1 d wird eine Lösung dadurch erhalten, dass man die

Subdivisionsbasisfunktionen in u und v berechnet und mit den regulären B-Spline- Basisfunktionen in der w-Dimension multipliziert, was im Ergebnis der obigen Gleichung (21 ) entspricht. Genauer gesagt werden hier die zweidimensionalen Basisfunktionen inklusive scharfe Kanten für das irreguläre Flächenstück, wie in Figur 1 1 f abgebildet, berechnet und mit der Funktion in der w-Dimension multipliziert.

In dem vierten Grenzfall, der in Figur 1 1 e gezeigt ist, ist die auszuwertende Grenzzelle 34 derart positioniert, dass zwei ihrer Flächen innerhalb einer Grenzfläche 36 bzw.

Grenzschicht 32 des Grenzelements 33 liegen. Dabei handelt es sich um in Figur 1 1 e markierte obere Grenzfläche 36 und die vom Betrachter abgewandte Grenzfläche 36, die jeweils entsprechende Flächen des Grenzelements 33 enthalten. Die irreguläre Kante 15 wird in diesem Fall als eine von den beiden vom Betrachter abgewandten Grenzflächen 36 der Grenzzelle 34 geteilte Kante definiert und der irreguläre Punkt 18 als ein Endpunkt dieser irregulären Kante 15.

Anschließend wird unter Zuhilfenahme der Unterteilungsregeln aus Figur 9 und in Kenntnis der genauen u, v, w-Koordinaten des auszuwertenden Ortes die Anzahl von Unterteilungsschritten n definiert, die dazu führen, dass eine den auszuwertenden Ort enthaltende und nach einer entsprechenden Unterteilung erhaltene Zelle 34 nur noch eine einzige Fläche in einer entsprechenden Grenzfläche 36 des Grenzelements 33 enthält.

Die Größe der Catmull-Clark-Unterteilungsmatrix auf 4M x 3K reduziert, wobei M der Anzahl der Kontrollpunkte 12 in jeder Schicht 56 des unterteilten Netzes 1 1 und K der entsprechenden Anzahl in dem Ausgangsnetz 10 entspricht. Die Reduzierung ist darauf zurückzuführen, dass aufgrund des betrachteten Grenzfalls eine Reihe von

Kontrollpunkten 12 gegenüber einer im Innern eines Volumens angeordneten Zelle fehlt. Anschließend ist einer der vorstehend erläuterten ersten bis dritten Grenzfälle anwendbar und der relevante Ort kann entsprechend direkt ausgewertet werden. Wenn eine auszuwertende Zelle 34 mehr als zwei Flächen aufweist, die in Grenzfläche 36 liegen, oder zwei derartige Flächen, die aber nicht aneinander angrenzen, muss das Ausgangsnetz 10 des dazugehörigen Grenzelements 33 einmal unterteilt werden. Eine hieraus resultierende Zelle 34, welche den auszuwertenden Ort enthält, fällt dann automatisch unter einen der vorstehenden ersten bis vierten Grenzfälle und ist entsprechend auswertbar.

Zusammengefasst stellt die gezeigte Lösung somit auch Möglichkeiten bereit, um das Subdivisionsmodell in seinen Grenz- bzw. Randbereichen in konstanter Zeit auszuwerten, sodass tatsächlich beliebige Orte in dem gesamten Modell mit einer konstanten

Berechnungszeit auswertbar sind.

Fig. 12 zeigt eine Darstellung, um Vorteile der hierin offenbarten Lösung zu verdeutlichen. Im Detail ist eine erste Gerade 106 und eine zweite Gerade 108 gezeigt, die jeweils einen Zusammenhang zwischen einer benötigten Anzahl von Unterteilungsschritten (d.h.

zusätzlichen lokalen Unterteilungen, um eine Auswertung an einem beliebigen Ort vornehmen zu können) und einer hierfür benötigten Zeit darstellen. Die Zeit ist dabei als relative Zeit bezogen auf die mit 1 normierte Zeit definiert, welche für eine Auswertung mit der erfindungsgemäßen Lösung benötigt wird. Dabei wird von einem Ausgangsnetz 10 ausgegangen, das gemäß dem vorstehenden vierten Grenzfall eine Zelle 34 mit wenigstens zwei Flächen in Grenzflächen des betrachteten Volumenelements 52 sowie einen irregulären Punkt 18 umfasst, der eine Valenz von fünf aufweist.

Die erste Gerade 106 resultiert aus der Anwendung eines Lösungsalgorithmus gemäß Stand der Technik und genauer gesagt von Burkhart et al. (Daniel Burkhart, Bernd Hamann und Georg Umlauf: Iso-geometric Finite Element Analysis Based on Catmull- Clark: Subdivision Solids In Computer Graphics Forum, Vol. 29. Wiley Online Library, 1575-1584). Dort werden bei auszuwertenden Orten in irregulären Zellen und/oder Volumenelementen so oft weitere lokale Unterteilungen vorgenommen, bis der auszuwertende Ort schlussendlich in einem vollständig regulären Bereich liegt.

Entsprechend steigt der rechnerisch Aufwand linear mit der Anzahl der erforderlichen Unterteilungsschritte an. Die Gerade 108 resultiert hingegen aus der Anwendung der hierin offenbarten Lösung. Man erkennt, dass die Berechnungszeit unabhängig von der Anzahl der erforderlichen Unterteilungsschritte n und somit konstant ist sowie ab ca. drei Unterteilungsschritten auch kürzer ist als bei dem Ansatz gemäß Burkhart et al. Der Vorteil wird umso größer, desto näher an einem irregulären Punkt oder einer irregulären Kante ausgewertet wird.

Die konstante und spätestens ab drei Unterteilungsschritten auch kürzere

Berechnungszeit resultiert vor allem daraus, dass für ein gegebenes Ausgangsnetz wesentliche Matrixausdrücke wie die Subdivisionsmatrix und ein Berechnen von deren Eigenstruktur vorab (d.h. vor dem Durchführen von Auswertungen) berechnet und z.B. in einer elektronischen Speichereinheit hinterlegt werden, sowie ferner daraus, dass man nicht n und mit jeder Unterteilungsstufe größer werdende Subdivisionsmatrizen miteinander multiplizieren muss, sondern lediglich die Diagonalmatrix potenziert. Das Berechnen kann computergestützt erfolgen, insbesondere von einer

Computervorrichtung, welche auch die erwähnte elektronische Speichereinheit umfassen kann. Anschließend muss, wie vorstehend erläutert, lediglich eine Diagonalmatrix in Abhängigkeit der Anzahl n von durchzuführenden Unterteilungsschritte potenziert werden, was sich jedoch durch allgemein kurze und vor allem im Wesentlichen unveränderliche Berechnungszeiten auszeichnet.

Wie gezeigt, kann mittels der bereitgestellten Auswertungsmöglichkeit eine

Koordinatenbestimmung und/oder Eigenschaftsbestimmung für beliebige Orte eines Subdivisionsmodells erfolgen, insbesondere auch dann, wenn die Basisfunktionen an einzelnen Kontrollpunkten Materialeigenschaften definieren oder vorgeben.

Zusätzlich oder alternativ kann die geschilderte Lösung insbesondere im Rahmen von Simulationen eingesetzt werden, z.B. wenn Eigenschaften (insbesondere physikalische Eigenschaften) eines Objekts simuliert werden sollen, das mittels eines volumetrischen Subdivisionsmodells modelliert wurde. Darauf basierend kann die Konstruktion des Objekts geeignet gewählt und/oder angepasst werden.

Ein Beispiel ist eine Simulation auf Basis der Finite Elemente Methode (FEM). Hiermit können in an sich bekannter Weise Kräfte ermittelt werden, die in dem Modell bzw. an den ausgewerteten Orten wirken. Das Verfahren kann demnach allgemein auch einen Schritt des Durchführens einer Simulation auf Basis des Subdivisionsmodells und/oder einer Kräfteermittlung an dem auszuwertenden Ort umfassen, wobei dies insbesondere auf Basis einer FEM erfolgen kann.

In an sich bekannter Weise werden bei Finite Elemente Methoden Verschiebungen von finiten Elementen untersucht, in die ein gegebenes Objekt unterteilt wurde. Aus diesen Verschiebungen werden anschließend mittels einer ebenfalls auf Basis der Unterteilung ermittelten Steifigkeitsmatrix die wirkenden Dehnungen und Spannungen (und folglich auch lokal wirkenden Kräfte) bestimmt. Für ein volumetrisches Subdivisionsmodell kann jede Zelle als ein finites Element verstanden und simuliert werden.

Eine Verschiebungsfunktion u für einzelne Kontrollpunkte i kann daher auf Basis der in den jeweiligen Kontrollpunkten definierten Basisfunktionen N, gemäß folgendem

Zusammenhang definiert werden:

Auch in diesem Fall gilt, dass die Basisfunktionen N, auf Basis der vorstehenden Ansätze an jedem beliebigen Ort und mit einer im Wesentlichen konstanten Berechnungszeit ausgewertet werden können und die Simulation und Kräfteermittlung somit besonders recheneffizient erfolgen kann.