DE69322575T2

DE69322575T2 - Verfahren und Gerät zur Wiedergabe von abgeglichenen NURB Oberflächen

Info

Publication number: DE69322575T2
Application number: DE69322575T
Authority: DE
Inventors: Salim S. Foster City California 94404 Abi-Ezzi; Srikanth Menlo Park California 94025 Subramaniam
Original assignee: Sun Microsystems Inc
Current assignee: Sun Microsystems Inc
Priority date: 1992-09-30
Filing date: 1993-07-28
Publication date: 1999-07-15
Anticipated expiration: 2013-07-29
Also published as: JP3344597B2; DE69322575D1; JPH06223197A; EP0590765B1; EP0590765A2; EP0590765A3; US5377320A

Description

HINTERGRUND DER ERFINDUNG

1. Gebiet der Erfindung:

Die vorliegende Erfindung bezieht sich auf ein Verfahren und eine Einrichtung zum schnellen und effektiven Wiedergeben graphischer Bilder auf einer Computergraphikanzeigeeinrichtung. Insbesondere bezieht sich die vorliegende Erfindung auf ein Verfahren und eine Einrichtung zum Wiedergeben beschnittener NURBS-Grundelemente auf einer Computergraphikanzeigeeinrichtung.

2. HINTERGRUND IM STAND DER TECHNIK:

In der Vergangenheit erforderten Computergraphiksysteme extensive Anzeige- und Computerressourcen. Die Menge der zur Wiedergabe von Bildern erforderlichen Berechnungszeit war beträchtlich. Bilder einer beliebigen Komplexität erforderten, daß leistungsfähige Computer Stunden rechneten, um das Bild zu erzeugen. Heutzutage hat sich die Technologie beträchtlich verbessert. Die Wiedergabe (Rendering) dreidimensionaler ("3D"-)Objekte ist nicht mehr länger ein Verfahren, das für Hochleistungsgroßrechner reserviert ist. Die Wiedergabe komplexer graphischer Objekte wird jetzt auf kleineren, weniger leistungsfähigen Computern verwirklicht.
Darüber hinaus wurden die graphischen Prozesse ausgeklügelter. Insbesondere die Verwendung ausgeklügelter graphischer Grundelemente ist heutzutage vorherrschend. Jedoch wird die Nützlichkeit der ausgeklügelten graphischen Grundelemente zum Teil gemessen an der Geschwindigkeit, mit der ein Computersystem das Grundelement auf einer Anzeigeeinrichtung wiedergeben kann. Ein Beispiel eines solchen Grundelements ist eine beschnittene NURBS. Eine beschnittene NURBS ist eine nicht-uniforme rationale B-Spline-Fläche mit beschneidenden Schleifen, welche die relevanten Abschnitte der Fläche definieren.
Die Erzeugung eines durch eine beschnittene NURBS dargestellten graphischen Bildes ist ziemlich komplex und zeitaufwendig, was viele der Vorteile aufwiegt, die durch die Verwendung der beschnittenen NURBS-Grundelemente zum Definieren eines graphischen Objekts erlangt worden sind. Das Wiedergabeproblem wird noch verschlimmert, bedenkt man die dynamische und interaktive Natur der heutigen Computergraphiken.
Es wurden Techniken entwickelt, um gekrümmte Oberfächen, wie beispielsweise NURBS, direkt aus den gekrümmten Flächen- Grundelementen, welche die Oberfläche definieren, wiederzugeben. Siehe beispielsweise Jeffrey Lane, Loren Carpenter, Turner Whitted, James Blinn, "Scan Line Methods for Displaying Parametrically Defined Surfaces", Communications of the ACM, 23(1), Januar 1980, und Sheue-Ling Lien, Michael Shantz and Vaughan Pratt, "Adaptive Forward Differencing for Rendering Curves and Surfaces", Computer Graphics, 21(4), Seiten 111 bis 117, Juli 1987. Jedoch sind diese Techniken nicht allgemein anwendbar und finden nur bei einer sehr begrenzten Klasse von NURBS Anwer dung. Darüber hinaus wird das Beschneiden ebenfalls nicht auf allgemeine Weise behandelt.
In dem Artikel von Alyn Rockwood, Kurt Heaton und Tom Davis, "Real-Time Rendering of Trimmed Surfaces", Proceedings of the ACM, SIGGRAPH '89, Computer Graphics, Band 23, Nr. 3, Juli 1989, Seiten 107 bis 116, wird eine Technik zum Zerlegen einer komplexen beschnittenen NURBS-Oberfläche in Dreiecke vor deren Wiedergabe beschrieben. Diese Technik jedoch führt wiederholt komplexe, zeitaufwendige Prozeßschritte für jede wiedergegebene Ansicht des Bildes durch.

ZUSAMMENFASSENDE DARSTELLUNG DER ERFINDUNG

Die Erfindung wird definiert durch die anhängigen Ansprüche 1, 15 und 23. Bevorzugte Ausführungsbeispiele der Erfindung sind in den abhängigen Ansprüchen angegeben.
Es wird eine einzigartige Graphik-Pipeline und ein Verfahren zu deren Verwendung zur Wiedergabe beschnittener NURBS-Oberflächen beschrieben. Eine NURBS(nicht-uniforme rationale B-Spline)-Oberfläche ist ein Grundelement, welches eine Abbildung aus einem begrenzten zweidimensionalen Parameterraum auf eine Menge von Punkten, welche die Oberfläche zusammensetzen, definiert. Um ein graphisches Grundelement, wie beispielsweise eine beschnittene NURBS, wiederzugeben, wird das Grundelement zunächst in einem Kompilierschritt bearbeitet, der von einem zwei-phasigen Traversierschritt und einem Anzeigeschritt gefolgt wird. Durch Kompilieren des graphischen Grundelements vor dem Traversieren wird die NURBS-Oberfläche zur Erzeugungszeit auf eine Form reduziert, die nachfolgend während des Traversierens einer schnellen Verarbeitung zugänglich ist.
Ein Schlüsselmerkmal der bei der Kompilierung erzeugten Informationen besteht darin, daß diese unabhängig von der Tesselierungsschrittweite sind; folglich bleiben die Informationen auch unter starken Änderungen der Modellierung und/oder der Ansichtstransformationen gültig. Darüber hinaus wird ein wesentlicher Teil der Verarbeitungskomplexität beim Wiedergeben der Grundelemente bei der Kompilierung absorbiert, so daß die Komplexität der Tesselierung bei dem Traversieren minimiert wird. Folglich verwenden nachfolgende Wiedergaben des gleichen Grundelements (z. B. unterschiedliche Ansichten) die kompilierten Informationen für ein schnelles Traversieren und Anzeigen.
Beim Kompilieren wird die beschnittene NURBS in monotone v-Bereiche zerlegt, welche für nachfolgende Ansichten und Wiedergaben gültig bleiben. Die NURBS wird überprüft, um die signifikanten Abschnitte der NURBS zu bestimmen. Die NURBS wird dann auf Bezier-Komponenten (oder "Patches") reduziert. Die definierten Beschneideschleifen für die NURBS werden ebenfalls auf die Bezier-Ebene derart reduziert, daß die relevanten Abschnitte der Beschneideschleifen den Bezier-Komponenten, die sie beeinflussen, zugeordnet werden. Jedes Bezier-Patch wird auf einen oder mehrere monotone u-v-Bereiche, genannte "v-Bereiche", reduziert, die durch Abschnitte der relevanten Beschneideschleifen begrenzt sind. Wie bereits erwähnt, brauchen diese Schritte nur einmal ausgeführt zu werden; unterschiedliche Ansichten und Wiedergaben des gleichen Grundelements beeinflussen nicht die erzeugten v- Bereiche.
Sobald das graphische Grundelement in dem Kompilierschritt bearbeitet worden ist, wird das Grundelement in dem Traversierschritt bearbeitet. Die Traversieroperation ist in zwei Phasen aufgeteilt. Die erste Phase ist algorithmisch kompliziert. Folglich ist es vorteilhaft, die erste Phase auf einem Mehrzweckcomputersystem abzuarbeiten. Die zweite Phase ist algorithmisch einfach und erfordert eine begrenzte Speichermenge, ist aber gleitkommaintensiv und sich wiederholend; folglich wird es bevorzugt, daß die zweite Phase auf einem schnellen speziellen Prozessor, wie beispielsweise einem Gleitkommaprozessor, abgearbeitet wird. Da jedoch das Grundelement in monotone v-Bereiche aufgebrochen worden ist, kann die Last des Erzeugens des Bildes unter den Prozessoren für eine Parallelverarbeitung verteilt werden.
In der Phase I des Traversierens wird die einheitliche Schrittweite für jedes Patch bestimmt. Während der Phase 11 des Traversierens wird die beschnittene NURBS in eine Mehrzahl von Dreiecken tesseliert, indem jeder während der Kompilierung bestimmte monotone v-Bereich tesseliert wird. Dann werden Beleuchtungsberechnungen ausgeführt und die die beschnittenen NURBS darstellenden Pixeldaten werden in einem Einzelbildpuffer gespeichert. Auf den Einzelbildpuffer wird durch die Anzeigesteuereinrichtung zugegriffen, welche die Anzeige steuert, um jedes Pixel mit einer Farbe und Intensität zu betätigen, die von den Pixeldaten angezeigt werden.
Das Verfahren schafft ein verteiltes schnelles und kosteneffektives System zum Wiedergeben beschnittener NURBS. Die während der Kompilierung durchgeführte komplexe Verarbeitung wird auf dem Wirts-System ausgeführt. Jedoch braucht die während der Kompilierung erforderliche Verarbeitung nur einmal für mehrere Traversierschritte durchgeführt zu werden. Die während der Kompilierung erzeugten Informationen sind bei variierenden Modellierungen und Ansichtstransformationen wiederverwendbar, wobei sie gleichmäßig die Größen- und/oder Abweichungsschwellwerte in den Anzeigekoordinaten erfüllen.
Die Phase I des Traversierens kann bei dem Wirts-Prozessor oder alternativ durch einen Mehrzweck-Co-Prozessor durchgeführt werden, die so programmiert sind, daß sie die Schrittweite für die Tesselierung jedes Patches bestimmen. Da die beschnittenen NURBS in Bezier-Patches zerlegt worden sind, die jeweils sämtliche für die Tesselierung erforderlichen Informationen enthalten, kann der Traversierschritt der Phase 11 durch eine Mehrzahl von parallel betriebenen Spezialprozessoren implementiert werden, um jedes Patch zu tesselieren, Beleuchtungsberechnungen auszuführen und jedes Dreieck in Pixeldaten zur Speicherung in dem Einzelbildpuffer zu konvertieren. Darüber hinaus können, da jedes beschnittene Bezier-Patch in v-Bereiche zerlegt worden ist, die v-Bereiche ebenfalls parallel verarbeitet werden. Die Anzeigesteuereinrichtung greift dann auf den Einzelbildpuffer zu und aktiviert die zugehörigen Pixel in der Anzeigeeinrichtung.

KURZBESCHREIBUNG DER ZEICHNUNGEN

Die Aufgaben, Merkmale und Vorteile der vorliegenden Erfindung werden für den Fachmann anhand der folgenden detaillierten Beschreibung deutlich, in welcher:
Fig. 1 ein Blockschaltbild ist, das ein bevorzugtes Ausführungsbeispiel des erfindungsgemäßen Systems veranschaulicht.
Fig. 2 ist ein Ablaufdiagramm, das den Gesamtprozeß veranschaulicht.
Fig. 3 ist ein Ablaufdiagramm des Kompilierprozesses.
Fig. 4 veranschaulicht drei Beschneideschleifen im Parameterraum, die mit der Regel der ungeradzahligen Windungen und der Linke-Hand-Regel im Einklang stehen.
Fig. 5 ist ein Ablaufdiagramm, das einige Details des Kompilierprozesses veranschaulicht.
Fig. 6a bzw. 6b veranschaulichen Arten von Extremscheitelpunkten und Schnittscheitelpunkten.
Fig. 7a bis 7e veranschaulichen unterschiedliche Optimierungen der Beschneideketten.
Fig. 8 veranschaulicht mögliche u-v-monotone v-Bereiche, welche auftreten können.
Fig. 9 ist ein Ablaufdiagramm, das den Prozeß des Bestimmers von v-Bereichen gemäß der vorliegenden Erfindung veranschaulicht.
Fig. 10 ist eine beispielhafte beschnittene NURBS mit v- Bereichen, die gemäß der vorliegenden Erfindung bestimmt wurden.
Fig. 11 ist ein Ablaufdiagramm, das die Phase I des Traversierprozesses veranschaulicht.
Fig. 12 veranschaulicht die unterschiedlichen Koordinatenräume, die während des Wiedergabeprozesses verwendet werden.
Fig. 13 ist ein Ablaufdiagramm, das die Phase 11 des Traversierprozesses veranschaulicht.
Fig. 14 ist ein Ablaufdiagramm, das den verwendeten Tesselierungsprozeß veranschaulicht.
Fig. 15a und 15b veranschaulichen unbeschnittene Zellen, rechts beschnittene Zellen, links beschnittene Zellen und doppelt beschnittene Zellen.
Fig. 16a, 16b, 16c veranschaulichen verschiedene Beispiele der Tesselierung von Dreiecken.
Fig. 17a bzw. 17b veranschaulichen eine Lücke und einen Nachbarstreifen zum Ausfüllen der Lücke.
Fig. 18a veranschaulicht einen Nachbarstreifen und Fig. 18b ist ein beispielhafter Pseudo-Befehlscode zum Erzeugen eines Nachbarstreifens.
Fig. 19a und 19b veranschaulichen einen Zusammenheftstreifen und Fig. 19c ist ein beispielhafter Pseudo-Befehlscode zum Erzeugen eines Zusammenheftstreifens.
Fig. 20 veranschaulicht die Aufteilung des Prozesses unter den Verarbeitungskomponenten in dem System.

DETAILLIERTE BESCHREIBUNG DER ERFINDUNG

Eine einzigartige graphische Pipeline und ein Verfahren zum Verwenden derselben geben komplexe beschnittene NURBS- Grundelemente in einer solchen Weise wieder, daß komplexe Operationen, die signifikante Zeit und Ressourcen beanspruchen, nur einmal für ein Grundelement durchgeführt werden, um Sub-Elemente der beschnittenen NURBS zu erzeugen, welche die Charakteristika der die NURBS bildenden Patches und der Abschnitte der Beschneideschleifen für jedes Patch beibehalten. Diese Elemente können dann unabhängig und parallel für jede Wiedergabe der beschnittenen NURBS verarbeitet werden, um eine schnelle, aber genaue Wiedergabe der beschnittenen NURBS zur Verfügung zu stellen.
Das Verfahren und die Einrichtung gemäß der vorliegenden Erfindung ermöglichen die dynamische Wiedergabe beschnittener NURBS-Oberflächen in einem Computergraphiksystem. Die vorliegende Erfindung führt eine Tesselierung der gekrümmter Oberfläche der beschnittenen NURBS in geeignet dimensionierte Dreiecke in Abhängigkeit von der räumlichen Beziehung der Oberfläche zu dem Betrachtungspunkt aus. Diese Beziehung neigt bei interaktiven graphischen Anwendungen dazu, in hohem Maße zu variieren, und somit muß die Auswahl geeignet dimensionierter Dreiecke wiederholt stattfinden. Dies schaffte eine starke Motivation für eine dynamische Tesselierung beschnittener NURBS-Flächen. NURBS sind leistungsfähige geometrische Grundelemente, welche bei den modernen geometriebezogenen Standards und Systemen, beispielsweise in PHIGS-plus, ziemlich populär geworden sind.
NURBS sind stückweise Polynomfunktionen, die in der Lage sind, sowohl konische, als auch frei geformte gekrümmte Oberflächen darzustellen. Eine NURBS(nicht-uniforme rationale B-Spline)-Oberfläche ist definiert als eine Abbildung aus einem begrenzten zweidimensionalen Parameterraum in eine die Oberfläche zusammensetzende Menge von Punkten:
wobei S(u,v) die Oberfläche ist, Pi,j eine n*m-Matrix von DeBoor-Kontrollpunkten darstellt, Bi,k(u) und Bj,l(v) die i-te und j-te B-Spline-Basisfunktionen der Ordnung k und der Ordnung 1 darstellen, die durch die Knotenvektoren {Up} mit p = 1 bis n + k bzw. {Vq} mit q = 1 bis m+1 definiert werden, und u,v die Parameter sind mit Uk ≤ u ≤ Un+1, V&sub1; ≤ v ≤ V ≤ Vm+1. Somit ist die NURBS-Oberfläche durch eine Menge von DeBoor-Kontrollpunkten im 3D-Raum und Knotensequenzen in der u- und v-Richtung im 2D-Parameterraum definiert.
NURBS zeigen die lokale Kontrolleigenschaft und bieten eine Modellierungsflexibilität, während sie die Verwendung von Polynomen hoher Ordnung vermeiden. Gleichzeitig zeigen die NURBS die Eigenschaften von Bezier-Flächen, welche einzelne Polynomfunktionen sind. NURBS können durch Multiplikations- und Additionsoperationen berechnet werden.
Typischerweise hat die B-Spline eine rechteckige Topologie. Wenn nur ein Abschnitt der Fläche verwendet werden soll, werden Beschneideschleifen (trimming 100 ps) im Parameterraum definiert, um einen Abschnitt der Oberfläche zu definieren. Diese Beschneideschleifen sind 2D-NURBS-Kurven, die an den Enden miteinander verbunden sind. Die Bereiche außerhalb der Beschneideschleifen werden nicht verwendet. Die Beschneideschleifen gestatten die Zusammensetzung verschiedener NURBS-Flächen und liefern im wesentlichen das zusammengesetzte NURBS-Grundelement. Diese Fähigkeit macht beschnittene NURBS sehr wichtig, da sie wichtige Einschränkungen der nicht-beschnittenen NURBS-Grundelemente überwinden.
Das System der vorliegenden Erfindung ist konzeptionell durch das Blockschaltbild gemäß Fig. 1 veranschaulicht. Eine CPU 10, ein Systemspeicher 15, Eingabe/Ausgabe(I/O)-Einrichtungen 20 und ein Anzeigeprozessorsystem 25 sind über einen Systembus 30 gekoppelt. Die CPU 10 fungiert als der zentrale oder Wirtsprozessor und führt typischerweise Anwendungsprogramme aus, die die gemäß der vorliegenden Erfindung erzeugten und angezeigten gekrümmten Oberflächen erzeugen. Die CPU 10 arbeitet als leistungsfähiger Mehrzweckprozessor und verwendet die verfügbaren Ressourcen, wie beispielsweise den Systemspeicher 15, I/O-Einrichtungen 20 und andere Peripherieeinrichtungen (nicht gezeigt), um komplexe Programme und Prozesse auszuführen. Die CPU 10 kann in ein System eingebunden sein, beispielsweise eine Computer-Worksstation, wie beispielsweise die von Sun Microsystems, Inc., Mountain View, Kalifornien hergestellte.
Wie im nachfolgenden näher beschrieben werden wird, ist das System des Anzeigeprozessors 25 insbesondere so konfiguriert, daß es einfache, aber sich in hohem Maße wiederholende und berechnungsintensive Prozesse ausführt, die als Teil des Prozesses zur Wiedergabe gekrümmter Oberflächen erforderlich sind. Das System 25 besteht aus einer oder mehreren Gleitkommaverarbeitungseinheiten (FPU) 32, 37, 41 und einem oder mehreren Speichern 35, 38, 42 und zumindest einer speziellen VLSI 33, 34, 36 oder einer ähnlichen Komponente, die bestimmte sich wiederholende Prozesse in einer zeitgerechten und kosteneffektiven Weise ausführt. Das Anzeigeprozessorsystem 25 erzeugt die Pixeldaten, die für die visuelle Darstellung der wiederzugebenden NURBS repräsentativ sind, und speichert die Pixeldaten in dem Einzelbildpuffer 40. Die Pixeldaten werden in dem Einzelbildpuffer 40 in einer Sequenz gespeichert, die auf einfache Weise mit den x-y-Koordinatenraum der Anzeigeeinrichtung 50 identifiziert wird.
Die Anzeigesteuereinrichtung erzeugt die Anzeige der durch die in dem Einzelbildpuffer angeordneten Pixeldaten definierten beschnittenen NURBS. Die Anzeigesteuereinrichtung 45 geht über ihre Steuereinrichtung 55 zyklisch abtastzeilenweise entsprechend der Abtastrate, beispielsweise 60mal pro Sekunde, durch den Einzelbildpuffer. Speicheradressen werden von der Steuereinrichtung 45 erzeugt, um auf die Pixeldaten zuzugreifen. Die Pixeldaten werden aus dem Einzelbildpuffer sequenziell gelesen und der Anzeigesteuereinrichtung-Farbnachschlagetabelle (LUT) 60 eingegeben. Die LUT 60 enthält die digitalen Steuersignale, die zum Steuern der Intensität und Farbe des Ausgangssignals, beispielsweise des Strahls auf der Anzeigeeinrichtung 50 verwendet werden. Die von der LUT 60 ausgebenen Signale werden Digital-Analog- Umsetzern (DACs) 65, 70 und 75 eingegeben, welche die Analogsignale zum Steuern der Anregung oder Erzeugung des Ortes bzw. der Intensität der grünen, roten und blauen Komponenten der anzuzeigenden Pixel erzeugen. Die Anzeigeeinrichtung kann eine Rasteranzeigeeinrichtung, wie beispielsweise einer Kathodenstrahlröhre (CRT), oder eine Hardcopy-Einrichtung, wie beispielsweise ein Plotter, sein. Aus Gründen der Erläuterung ist die Anzeigeeinrichtung hier eine CRT; für den Fachmann ist es jedoch klar, daß andere Anzeigeeinrichtungen gemäß dem System der vorliegenden Erfindung ebenfalls verwendet werden können.
Bei dem Prozeß der vorliegenden Erfindung ist die Verarbeitung der beschnittenen NURBS-Oberflächen in vier grund sätzliche Schritte unterteilt. Es wird auf Fig. 2 Bezug genommen. Der erste Schritt 103 der Kompilierung ist eine einmalige Operation, die das beschnittene NURBS-Grundelement in eine kompakte ansichtsunabhängige Form kompiliert. Ein großer Teil der in der Verarbeitung beschnittener NURBS enthaltenen Komplexität wird bei diesem Schritt absorbiert. Jedesmal, wenn die NURBS-Fläche ausgelegt wird, wird die kompilierte Form als Eingabe in die Tesselierungsverarbeitung verwendet. Der zweite Schritt 105 ist die erste Phase des Auslegens oder Traversierens und enthält Operationen, wie beispielsweise die Schrittweitenbestimmung für die Tesselierung. Diese Phase ist algorithmisch komplex, aber nicht berechnungsintensiv. Der dritte Schritt 107 ist die Phase 11 des Traversierens und ist diejenige Phase, in der die tatsächliche Berechnung der Fläche und die Tesselierung in Dreiecke stattfindet. Diese Phase ist algorithmisch einfach aber berechnungsinteniv. Die Differenzierung zwischen zwei Traversierphasen beruht auf den Fähigkeiten des Graphikbeschleunigers; typischerweise verarbeitet aber ein Mehrzweck- Front-End-Prozessor, wie beispielsweise der Wirts-Prozessor, die erste Phase und eine oder mehrere spezielle Gleitkommaprozessoren, die parallel arbeiten, verarbeiten die zweite Phase. Auf diese Weise können die algorithmisch komplizierten Schritte auf den Front-End-Prozessor und die algorithmisch einfachen, aber gleitkommaintensiven Schritte können auf den speziellen Gleitkommaprozessoren in einer parallelen Weise durchgeführt werden. Sobald die Dreiecke tesseliert sind, werden die Dreiecke schnell und einfach verarbeitet, damit sie Schattierungen erhalten, und werden in Pixeldaten zur Speicherung in den Einzelbildpuffer konvertiert und, wie es während des vierten Schrittes, dem Schritt 109, durchgeführt wird, nachfolgend an die Anzeigeeinrichtung ausgegeben.
Ein Vorteil der vorliegenden Erfindung ist die Fähigkeit der Wiederverwendung zuvor bestimmter Informationen bezüglich der beschnittenen NURBS. Wenn beispielsweise die An sicht geändert werden soll, Schritt 106, können während der Kompilierung, Schritt 103, erzeugte Informationen wieder benutzt werden, wobei die zeitaufwendigen und teuren Berechnungen vermieden werden, die während der Kompilierung auftraten. In ähnlicher Weise kann der Prozeß gemäß der vorliegenden Erfindung unter bestimmten Umständen bestimmte während der Phase I des Traversierens 107 erzeugte Informationen erneut verwenden, wenn die auszuführende Wiedergabe keine Änderung bestimmter Anzeigeparameter, z. B. der für die Tesselierung verwendeten Schrittweite, erfordert.
Im folgenden soll der Kompilierungsprozeß unter Bezugnahme auf Fig. 3 beschrieben werden. Im Block 310 wird die NURBS auf eine Mehrzahl von Bezier-Patches reduziert. Dies vereinfacht die Verarbeitung, da jedes Bezier-Patch ein einzelnes Polynom ist, welches einfacher zu verarbeiten ist. Bezüglich weiterer Informationen, die den Prozeß der Konvertierung der NURBS in Bezier-Patches betreffen, siehe beispielsweise Boehm, Farm, Kahmann, "A Survey of Curve and Surface Method in CAGD", Computer Aided Geometric Desian, Band 1, Seiten 1 bis 60 (1984). Boebm et al beschreiben einen Prozeß zum Konvertieren von NURBS in Bezier-Patches durch Einfügung von Knoten und eine Änderung der Basis.
Die signifikanten Abschnitte der NURBS sind durch die NURBS und ihre Beschneideschleifen definiert. Jede Schleife hat eine Richtung und ist eine geschlossene Schleife. Der signifikante Bereich der beschnittenen NURBS kann durch die Ungeradzahlige-Windungs-Regel oder die Linke-Hand-Regel definiert werden; d. h., der signifikante Abschnitt des Bereichs befindet sich auf der linken Seite jeder Beschneidekurve. Dies wird unter Bezugnahme auf Fig. 4 veranschaulicht. Fig. 4 veranschaulicht drei Beschneideschleifen 400, 410 und 420, welche sowohl mit der Ungeradzahligen-Windungs- Regel als auch der Linke-Hand-Regel konsistent sind. Jede Schleife weist eine Richtung auf, wie sie durch die Pfeile angezeigt ist, und durch Verfolgen von beispielsweise der Linke-Hand-Regel definieren die Beschneideschleifen 400, 410 und 420 zwei signifikante Abschnitte. Der erste Abschnitt 430 wird durch die Beschneideschleifen 400 und 410 begrenzt und der zweite signifikante Abschnitt 440 ist als derjenige innerhalb der Beschneideschleife 420 definiert.
Im Schritt 320 gemäß Fig. 3 werden die Beschneideschleifen in Abschnitte aufgeteilt, so daß die relevanten Abschnitte der Schleifen mit dem Patch, das die Beschneideschleife begrenzt oder beeinflußt, identifiziert werden. Vorzugsweise wird der folgende Prozeß verwendet, um die beschnittenen Patches zu kompilieren. Für den Fachmann ist es jedoch klar, daß andere Prozesse verwendet werden können.
Es wird auf Fig. 5 Bezug genommen, in der das bevorzugte Ausführungsbeispiel für die Kompilierung von Beschneideschleifen beschrieben wird. Im Schritt 450 wird eine zweidimensionale Matrix von Patches als Leer initialisiert. Sobald der Kompilierungsprozeß abgeschlossen ist, wird diese Matrix Informationen enthalten, die die Klasse jedes Patches, den monotonen v-Bereich, welcher jedes Patch bildet, und Informationen bezüglich der Begrenzungsabschnitte (die während des Traversierens zum Ausführen von Zusammenheftoperationen benutzt werden) identifizieren. Patches, die als Leer klassifiziert bleiben, sind Patches die vollständig aus dem signifikanten Bereich herausgeschnitten worden sind. Diese Patches werden während des Traversierens nicht bearbeitet. Patches, die als Vollständig klassifiziert worden sind, sind Patches, die vollständig innerhalb des signifikanten Bereichs liegen. Als Beschnitten klassifizierte Patches weisen Beschneideschleifen durch das Patch hindurch auf.
Im Schritt 455 wird eine Beschneidekette für jede Beschneideschleife erzeugt. Die Beschneidekette ist eine Matrix von Segmenten, die die Beschneideschleife repräsentieren. Jedes Segment ist ein Tupel (u,v, udir, vdir), wobei die Terme u bzw. v die u- und v-Koordinaten des Segments und udir und vdir entweder eine Koordinate des Segments oder das Ansteigen oder Abfallen des Segments identifizieren. Jedes Segment kann ein lineares Segment oder eine Bezier-Kurve im Parameterraum sein.
Die Beschneidekurven werden zunächst in Bezier-Polynomstücke zerlegt. Wenn die Beschneidekurven anfänglich stückweise linear sind, so bleiben diese Stücke linear. Wenn die Beschneidekurven nicht anfänglich stückweise lineare Segmente sind, und der Benutzer es wünscht, Beschneidekurven unter Verwendung einer konstanten Anzahl von Schritten zu tesselieren, werden diese Bezier-Stücke tesseliert und in lineare Segmente zerlegt. Das Ergebnis ist, daß jede Beschneideschleife jetzt aus einer Kette von linearen oder Bezier-Segmenten besteht.
Im Schritt 460 wird jede Beschneidekette sequentiell Segment für Segment durchlaufen, um die Kette in monotone Ketten von Segmenten aufzubrechen. Das erste Segment der Beschneidekette wird verwendet, um eine monotone Kette zu starten. Das Patch, in welchem die Beschneidekette startet, wird in der Matrix als Beschnitten bezeichnet. Jedes nachfolgende Segment in der Beschneidekette wird überprüft. Im Schritt 465 werden die u/v-Extrema in der Beschneidekette identifiziert. Ein u/v-Extremum tritt auf, wenn ein Segment im Vergleich zum vorhergehenden Segment eine entgegengesetzte u/v-Richtung hat, oder wenn ein Bezier-Segment in sich selbst Extrema aufweist. Bei jedem Extremum wird ein "Extremscheitelpunkt" erzeugt.
Im Schritt 470 wird der Extremscheitelpunkt klassifiziert, und der Scheitelpunkt wird in eine dem Patch zugeordnete sortierte Scheitelpunktliste eingegeben. Die Liste von Scheitelpunkten ist nach abfallendem v sortiert. Für das vorliegende Ausführungsbeispiel sind die Typen der Klassifikationen in Fig. 6a veranschaulicht. Ein Scheitelpunkt ist durch die Art des Extremums identifiziert und besteht aus einer Bezugnahme auf die geeigneten Segmente, welchen den Scheitelpunkt bilden. Wie im nachfolgenden beschrieben wird, wird auf die jedem Patch zugeordnete Scheitelpunktliste während des Phase-I-Traversierprozesses Bezug genommen, um die v-Bereiche zu erzeugen, die bei dem Prozeß zum Wiedergeben der beschnittenen NURBS auf der Anzeigeeinrichtung verwendet werden. Zusätzlich wird dann, wenn ein Extremum erfaßt wird, die monotone Kette an dem Scheitelpunkt beendet und eine neue monotone Kette begonnen.
Wenn im Schritt 475 das Segment eine Patch-Begrenzung überquert, wird ein Schnittscheitelpunkt an dem Überquerungspunkt erzeugt. Wenn die Begrenzung eine linke oder eine rechte Begrenzung ist, wird der Scheitelpunkt in Bezug auf sowohl das linke als auch das rechte Patch klassifiziert. Die Klassifikationen für das vorliegende Ausführungsbeispiel sind durch Fig. 6b veranschaulicht. Der Schnittscheitelpunkt wird in die Scheitelpunktliste für die Patches eingefügt. Zusätzlich wird er in die sortierte Liste von Schnittscheitelpunkten für die Patch-Begrenzung eingefügt. Diese Listen weisen Scheitelpunkte auf, die nach absteigendem v (von oben nach unten) sortiert sind. Diese Listen werden nachfolgend verwendet, um v-Bereiche zu erzeugen. Die monotone Kette wird an dem Schnittscheitelpunkt beendet und eine neue Kette wird begonnen. Dieser Prozeß, die Schritte 465, 470, 475 und 480, wird für sämtliche Segmente fortgesetzt.
Die oben beschriebenen Operationen umfassen die Bestimmung von Durchschneidungen von beschneidenden Segmenten mit u/v-Iso-Linien, welche die Begrenzungen von Patches identifizieren, und die Identifikation von Extrema innerhalb des Segments. Um diese Operationen an Bezier-Kurvensegmenten durchzuführen, wird vorzugsweise ein Wurzellösungsalgorithmus (root-solving algorithm) verwendet. Siehe beispielsweise: Philip Schneider, "A Bezier Curve Based Root Solver", Graphic Gems, herausgegeben von Andrew Glassner (Academic Press, 1990).
Überschneidungen mit Iso-Linien werden berechnet, indem die Wurzel (Root) der zu einer Koordinatenachse verschobenen Bezier-Kurve aufgefunden wird. Extrema werden gefunden, indem Wurzeln der ersten Ableitung der Bezier-Kurve gefunden werden. Unter Verwendung des Wurzel-Lösers werden die Extre ma und Patch-Überquerungen in Form der Parameterwerte bestimmt, bei welchen die Extrema oder Patch-Überquerungen auftreten.
Die Bezier-Kurve wird dann bei diesen Parameterwerten in zwei Kurven, die einen gemeinsamen Endpunkt bei dem Parameterwert aufweisen, zerlegt. Diese Technik stellt Informationen zur Verfügung, die zum Fortsetzen des Kompilierens und Traversierens erforderlich sind, ohne die Kurven in Liniensegmente zu tesselieren.
Da die Berechnung von Wurzeln berechnungsintensiv ist, werden die einzigartigen Eigenschaften von Bezier-Kurven ausgenutzt, um die Notwendigkeit zum Bestimmen von Wurzeln zu minimieren. In diesen Fällen wird eine vorläufige Überprüfung an den Kontrollpunkten ausgeführt, bevor der Wurzel- Löser verwendet wird. Beispielsweise kann angenommen werden, daß nur dann, wenn das Kontrollpolygon (das durch Verbinden der Kontrollpunkte der Bezier-Kurve gefunden wird) ein Extremum aufweist, die Kurve selbst ein Extremum aufweisen wird. In ähnlicher Weise wird nur dann, wenn das Kontrollpolygon eine Patch-Begrenzung überquert, die Kurve die Begrenzung überqueren. Drittens werden u/v-Zustände und Scheitelpunktklassifikationen unter Verwendung der Endpunktinterpolationseigenschaften der Bezier-Kurven berechnet (d. h., der Anstieg der Kurve gleicht dem Anstieg des Polygons an den Endpunkten des Polygons).
Eine NURBS wird gebildet durch eine Mehrzahl von Bezier- Patches, die durch Knotenlinien getrennt sind. Die Patches erscheinen rechteckig und weisen Begrenzungen auf, die durch u-Knotenlinien und v-Knotenlinien dargestellt werden. Die Patch-Ecken sind an dem Schnittpunkt einer u-Knotenlinie und einer v-Knotenlinie definiert. Bei Abschluß der Analyse der beschneidenden Kurven ist eine Kompilierung der Patch-Begrenzung-Schnittpunkte und -Extrema für jedes Patch verfügbar. Unter Verwendung dieser Informationen werden, sobald sämtliche beschneidenden Kurven bearbeitet worden sind, im Schritt 485 die Patch-Ecken zeilenweise durchgesehen, um diejenigen Ecken jenes Patches zu bestimmen, welche sich innerhalb des signifikanten Bereichs befinden, und diejenigen Ecken, welche sich außerhalb des signifikanten Bereichs befinden. In Übereinstimmung mit der Ungeradzahlige-Windungs- Regel befindet sich dann, wenn sich ein Strahl von der Oberfläche erstreckt und dieser eine ungerade Anzahl von Patch- Begrenzungen (d. h. Knotenlinien) überquert, das Patch innerhalb des signifikanten Bereichs. Wenn der Strahl eine gerade Anzahl von Patch-Begrenzungen überquert, so ist das Patch vollständig außerhalb des signifikanten Bereichs. Dies kann einfach dadurch ausgeführt werden, daß die Anzahl von Schnittpunkten untersucht wird, die die v-Knotenlinie links von der Ecke enthält. Sofern diese Anzahl ungeradzahlig ist, dann befindet sich unter Beachtung der Ungeradzahlige-Windungs-Regel die Ecke innerhalb des signifikanten Bereichs. Diese Anzahl kann auf einfache Weise aus der sortierten Scheitelpunktliste für die Begrenzungen, welche v-Knotenlinien sind, bestimmt werden. Insbesondere wird die Patch-Begrenzungsliste überprüft, um die Anzahl von Patch-Überquerungen durch beschneidende Kurven links von oder unter der Ecke zu bestimmen. Wenn die Anzahl von Überquerungen ungeradzahlig ist, befindet sich die Ecke innerhalb des signifikanten Bereichs.
Im Schritt 490 werden diejenigen Patches, die nicht von Beschneideschleifen beeinflußt sind, als Vollständig klassifiziert, sofern sich die obere linke Ecke des Patch innerhalb der Beschneideschleife befindet und keine Beschneideschleife das Patch durchläuft. Durch Ausführung der obigen Schritte werden die NURBS-Beschneideinformationen auf die Patch-Ebene reduziert oder aufgelöst. Somit können nachfolgende Verarbeitungen des Beschneidens Patch für Patch unabhängig ausgeführt werden.
Vorzugsweise berücksichtigt die Verarbeitung der Beschneideschleifen eine Reihe spezieller Fälle. Diese werden durch Identifizieren eines Satzes von Vereinbarungen, (Konventionen), welche befolgt werden, wenn die Beschneide ketten verfolgt werden, behandelt, wodurch eine Spezialfallbehandlung vermieden wird, indem die Lösung für den allgemeinen Fall zur Verfügung gestellt wird. Die ausgewählten Konventionen werden beeinflußt durch die Linke-Hand-Regel, auf der die Beschneideschleifen basieren.
Die erste Konvention besagt, daß ein horizontales oder vertikales Beschneidesegment so zu klassifizieren und zu behandeln ist, als ob es geringfügig zur linken Seite geschwenkt wäre. Dies ist gut definiert, vorausgesetzt, daß das Beschneidesegment gemäß der Linke-Hand-Regel orientiert ist. Diese Konvention steht außerdem im Einklang mit dem Fall, bei dem das Beschneidesegment eine Knotenlinie überlappt, da das Segment in der horizontalen oder vertikalen Richtung orientiert ist.
Die zweite Konvention spezifiziert, daß ein Beschneidesegment, das exakt an einem Knotensegment endet, so behandelt wird, als ob es infinitesimal kürzer als das Segment ist. Folglich wird der Scheitelpunkt nicht in der Patch-Begrenzungsliste angegeben. Demzufolge wird dann, wenn sich das nächstfolgende Beschneidesegment in das benachbarte Patch fortsetzt, dieses so behandelt, als ob es das Knotensegment richtig schneidet, so daß ein Segment mit der Patch- Begrenzung gleichgesetzt wird. Andernfalls wird dann, wenn das nachfolgende Beschneidesegment sich nicht in das benachbarte Segment fortsetzt, keine Überschneidung mit dem Knotensegment registriert, und der Punkt auf der Begrenzung wird in der Patch-Begrenzungsliste so behandelt, als ob er nicht auf der Begrenzung liegt.
Fig. 7a veranschaulicht die erste Konvention zum Behandeln horizontaler (2) (4) oder vertikaler (1) (3) Beschneidesegmente so, als ob sie geringfügig zur linken Seite gedreht wären, wie es durch die gezeigten Pfeile angezeigt wird. Fig. 7b veranschaulicht die zweite Konvention, bei der ein Punkt auf der Begrenzung so behandelt wird, als ob er kurz vor der Begrenzung liegt.
Die dritte Konvention spezifiziert, daß dann, wenn ein Beschneidesegment einen Eckpunkt kreuzt, was ein komplizierter Abschnitt von Knotenlinien ist, das Segment so behandelt wird, als ob es geringfügig zur linken Seite verschoben ist. Dies ist in Fig. 7c veranschaulicht, welche zwei Segmente in entgegengesetzten Richtungen zeigt, welche einen Eckpunkt kreuzen, wobei sie jeweils ein zweites benachbartes Segment aufweisen, das geringfügig nach links verschoben ist.
Die nächste Konvention gibt an, daß dann, wenn ein Startpunkt einer Beschneidekette mit einer Ecke zusammenfällt oder auf einer Begrenzung liegt, sich der Punkt auf einer Knotenlinie aufhält und der Punkt so behandelt wird, als ob er geringfügig von der Knotenlinie bzw. den Knotenlinien verschoben ist. Wenn der Punkt auf der B-Spline-Begrenzung liegt, wird er so behandelt, als ob er in das Patch hineingeschoben ist. Beispielsweise wird ein Punkt auf der linken Begrenzung des am weitesten links liegenden Patch behandelt, als ob er nach rechts verschoben ist. Andererseits wird ein Punkt dort, wo die Beschneidekette endet, so behandelt, als ob er in das Patch hineingeschoben ist. Das heißt, der Punkt wird so behandelt, als ob er so verschoben ist, daß das letzte Segment in der Kette nicht das Knotensegment, auf dem der Punkt liegt, überqueren muß. Dies ist in Fig. 7d veranschaulicht.
Eine weitere Konvention kann bei der Festlegung des Vorrangs unter Typen von Scheitelpunkten derart verwendet werden, daß zusammenfallende Extremscheitelpunkte in die sortierte Liste eingefügt werden können. Wenn beispielsweise zwei Scheitelpunkte des Extremum-Typs 2B und 3A zusammenfallen, wird dem 3A-Scheitelpunkt der Vorrang gegeben (siehe Fig. 6A), weil die Beschneideschleife, zu der er gehört, von oben kommt und zu erst bearbeitet werden soll. Vorzugsweise wird dies dadurch erreicht, daß eine Nachschlagetabelle der unterschiedlichen Typen von Scheitelpunkten, die in unterschiedlichen Konfigurationen auftreten können, zur Verfügung gestellt wird und der Vorrang für jede Konfiguration angegeben wird.
Diese Konventionen werden für bestimmte Kombinationen dieser Fälle kombiniert angewendet. Beispielsweise wird, wie es in Fig. 7e gezeigt ist, ein Beschneidesegment, das eine Knotenlinie, überlappt und an einer Ecke endet, so behandelt, als ob es nach linksgedreht wurde und kurz vor der senkrechten Knotenlinie liegt, auf der es endet.
Nachdem die Beschneideschleifen während des Kompilierens verarbeitet worden sind, sind jetzt die folgenden Informationen für jedes Patch verfügbar:
1) Eine Liste von u-v-monotonen Beschneideketten, die durch das Patch laufen. Jede monotone Kette besteht aus einem Startscheitelpunkt, einer Folge von Beschneidesegmenten und einem Endscheitelpunkt.
2) Eine Liste von durch den Typ identifizierten Extremscheitelpunkten, die nach absteigendem v sortiert sind. Die Liste enthält vorzugsweise einen Zeiger, die Segmentinformation darüber, um welchen Typ des Extremums es sich handelt, und Zeiger auf die zwei monotonen Segmente, die es verbindet.
3) Eine sortierte Patch-Begrenzungsliste von Schnittscheitelpunkten für die vier Begrenzungen des Patch. Diese Liste enthält vorzugsweise eine Liste von Scheitelpunkten, die von oben nach unten bzw. von links nach rechts sortiert sind. Es sei angemerkt, daß Schnittscheitelpunkte auf einer linken/rechten Patch-Begrenzung zwei Scheitelpunkttypen aufweisen (einen für jedes Patch).
Die jedes Patch betreffenden Informationen können in einer Vielzahl von Arten von Datenstrukturen und -formaten gehalten werden. Beispielsweise können die Begrenzungs- und Eckinformationen durch ein Umrandungsgitter oder Skelettobjekt in Bezug auf die gesamte wiederzugebende Oberfläche gehalten werden. Die die Extrema betreffenden Informationen könnten von jedem Patch-Objekt gehalten werden. Jeder Extrem- oder Grenzscheitelpunkt identifiziert die u,v-Koordi naten des Extremums, den Typ des Extremums und Zeiger auf die beiden monotonen Ketten, die er verbindet.
Es wird wieder auf Fig. 3 Bezug genommen, gemäß der im Schritt 330 die Patches in etwas unterteilt werden, was hier als v-Bereiche bezeichnet wird. Diese monotonen v-Bereiche haben bestimmte Charakteristika, die ein schnelles Traversieren ermöglichen. Ein monotoner v-Bereich ist aus einer oberen und einer unteren Basis zusammengesetzt, welche horizontal orientiert sind, sowie aus einer linken und einer rechten Seite. Fig. 8 veranschaulicht den primären Satz möglicher u-v-monotoner v-Bereichsarten, die auftreten können, wobei K ein v-Knotenbasissegment darstellt, R eine reguläre Basis darstellt und G eine Basis darstellt, die einen Scheitelpunkt eines Typs aufweist, welcher eine mögliche Lücke anzeigt. Die linke und die rechte Seite bestehen jeweils aus einer Kette von u-v-monotonen Beschneidesegmenten, welche lineare oder Bezier-Segmente sein können. Die Seiten werden klassifiziert als: mit abfallendem u, mit ansteigendem u oder als Rand, was die linke oder die rechte Begrenzung des Patch anzeigt. Die Traversierzeitverarbeitung ist abhängig von den Arten der linken und rechten Seiten. Somit klassifizieren wir beim Kompilieren jeden v-Bereich in einen von 9 Typen, wie es in Fig. 8 gezeigt ist.
Der Prozeß des Abschließens der v-Bereiche ist in Fig. 9 fortgesetzt. Beim Schritt 500 wird auf die sortierte Begrenzungsliste von Schnittscheitelpunkten für die linke, rechte und obere Patch-Begrenzung, die zuvor bestimmt worden ist, zugegriffen und das Patch innerhalb der signifikanten Bereichsecken wird zur Liste hinzugefügt. Im Schritt 505 werden die linken/rechten Randschnittscheitelpunkte (welche von oben nach unten sortiert sind) hereingenommen, die den Seitenrändern der v-Bereiche entsprechen. Im Schritt 510 werden die oberen Schnittscheitelpunktpaare (die Paare, welche die größten v-Koordinatenwerte aufweisen) als Anfang von aktiven Bereichen identifiziert. Aktive Bereiche sind v-Bereiche, deren obere Basis definiert ist, bei denen aber der Boden noch nicht bestimmt worden ist. Dann wird die Verarbeitung begonnen, um den unteren Rand zu bestimmen, um die aktiven v-Bereiche abzuschließen. Folglich wird im Schritt 515 jeder Scheitelpunkt in der sortierten Liste von Extremscheitelpunkten verarbeitet.
Die Typen der Scheitelpunkte sind für die Bildung der v- Bereiche bestimmend. Es wird beispielsweise auf Fig. 6a und 6b Bezug genommen; ein Scheitelpunkt des Typs 1a und 1b zeigt den Abschluß eines aktiven v-Bereichs und die Aktivierung eines neuen Bereichs an. Ein solcher Scheitelpunkt befindet sich am Boden der linken/rechten Seite eines aktiven Bereichs. Es wird eine horizontale Linie durch den Scheitelpunkt gebildet, welche die monotone Kette des die andere Seite des v-Bereichs bildenden Segments zergliedert, um zwei Ketten des Segments zu bilden. Die horizontale Linie zeigt die untere Basis des v-Bereichs und die obere Basis des neuen v-Bereichs, welcher eröffnet wird, an. Die Aufgliederung der Ketten von Segmenten kann erreicht werden, indem eine binäre Suchroutine verwendet wird, um das richtige zu zerteilende Segment zu lokalisieren. Es wird ein neuer Scheitelpunkt an dem Schnittpunkt gebildet. Wenn das geschnittene Segment eine Bezier-Kurve ist, wird vorzugsweise der Wurzel-Lösungsalgorithmus verwendet, um den Schnittpunkt zu berechnen.
Ein Scheitelpunkt des Typs 2A zeigt den Abschluß eines aktiven Bereichs und die Aktivierung von zwei neuen an. Dieser wird durch Auffinden eines aktiven v-Bereichs, welcher diesen Scheitelpunkt einschließt, erreicht. Eine horizontale Linie 533 wird durch den Scheitelpunkt gezogen, um die Unterseite des aktiven Bereichs und die Oberseite der zwei neuen Bereiche zu bilden, wobei ein Bereich links und ein Bereich rechts von dem Scheitelpunkt angeordnet ist.
Die u,v-Koordinatenwerte des Scheitelpunkts werden zusammen mit Informationen gehalten, die die untere Basis des abgeschlossenen v-Bereichs identifizieren. Wie nachfolgend erläutert wird, werden diese Informationen während des Tra versierens verwendet, um eine mögliche Lücke zu vermeiden, welche nachfolgend während der Tesselierung auftreten kann. Durch Halten dieser Informationen zusammen mit jedem betroffenen v-Bereich wird eine Unabhängigkeit unter den v-Bereichen erreicht und es kann folglich eine parallele Bearbeitung der v-Bereiche währendes Traversieren ausgeführt werden.
Ein Scheitelpunkt vom Typ 2B zeigt die Aktivierung eines neuen v-Bereichs an. Ein Scheitelpunkt vom Typ 3A zeigt den Abschluß eines aktiven v-Bereichs an. Ein Scheitelpunkt vom Typ 3B zeigt einen Abschluß von zwei v-Bereichen und den Beginn eines neuen v-Bereichs an. Die an diesem Scheitelpunkt endenden v-Bereiche werden identifiziert und die zwei neuen v-Bereiche werden durch Ziehen einer horizontalen Linie 534 durch den Scheitelpunkt hindurch identifiziert. Diese u,v- Koordinatenwerte des Scheitelpunkts werden als oberer Rand des neuen aktiven v-Bereichs identifiziert, da eine mögliche Lücke zwischen v-Bereichen während des Traversierens auftreten kann.
Im Schritt 520 werden die verbleibenden aktiven v-Bereiche abgeschlossen, indem Abschnitte der unteren Patch-Begrenzung als untere Basis identifiziert werden. Im Schritt 525 werden die v-Bereiche optimiert und für das nachfolgende Traversieren verpackt. Beispielsweise werden entartete v-Bereiche eliminiert. Die entarteten v-Bereiche sind diejenigen Bereiche, bei denen die obere und die untere Basis zusammenfallen, und die keinen Scheitelpunkt aufweisen, von welchem angegeben ist, daß er eine mögliche Lücke aufweist. Die Reihenfolge der Segmente, die durch die monotonen Paare von Schnittscheitelpunkten aus der Schnitt-Liste, welche sich auf der linken Seite befinden, identifiziert werden, wird in ihre Richtung oder Reihenfolge derart umgedreht, daß beide Seiten des v-Bereichs Segmente aufweisen, die von unten nach oben gehen. Zusätzlich werden die von den Schnittscheitelpunkten definierten Segmente in die lokalen Koordinaten des Patch-Parameterraums transformiert, da die Beschneideschlei fen in dem Parameterraum der B-Spline definiert sind. Im Schritt 530 werden sortierte Listen von Q-Punkten auf der linken und der rechten Begrenzung für jeden v-Bereich erzeugt. Die Q-Punkte sind diejenigen neuen Punkte, die infolge des "Abhackens" erzeugt worden sind, das auftrat, wenn ein v-Bereich abgeschlossen wurde und ein neuer aktiver v- Bereich startete. Es werden sortierte Listen von Schnittpunkten und Q-Punkten erzeugt. Diese Q-Punkte werden, wie nachfolgend erläutert wird, beim Zusammenheften von Lücken zwischen benachbarten Patches verwendet.
Sobald die v-Bereiche kompiliert worden sind, kann jeder v-Bereich unabhängig gemäß der während der Kompilierung erzeugten Klassifikation tesseliert werden. Dies führt von selbst zu einer parallelen Verarbeitung durch schnelle spezielle Prozessoren zum schnellen Tesselieren und Erzeugen eine Anzeige der beschnittenen NURBS.
Am Ende der Kompilierung ist jeder v-Bereich durch eine obere und eine untere Basis definiert, die jeweils als reguläre, Knoten- oder Lücken-Basis klassifiziert ist; wobei eine linke und rechte Seite jedes der v-Bereiche aus einer u- v-monotonen Sequenz von linearen/Bezier-Segmenten besteht, welche ein ansteigendes v und ein ansteigendes oder abfallendes u aufweisen, sofern die Seite durch Beschneideschleifen gebildet ist, oder die aus zwei Punkten bestehen, welche die Endpunkte eines Randes des Patch angeben.
Fig. 10 veranschaulicht ein Beispiel einer Kompilierung einer beschnittenen NURBS. Insbesondere wird diese Figur verwendet, um die Schritte zum Kompilieren eines der Patches einer beschnittenen NURBS detailliert anzugeben. Die beschneidenden Schleifen werden zunächst in beschneidende Ketten konvertiert (nicht tesseliert im Falle von Bezier). Die Ketten werden durchlaufen und es werden Schnittpunkte und Extrema für jeden Patch identifiziert, was zu einer Liste von u-v-monotonen Subketten pro Patch führt. Die innenliegenden Patch-Ecken für den signifikanten Bereich werden dann identifiziert.
Es wird auf Fig. 10 Bezug genommen; die Kompilierung der zwei beschneidenden Schleifen führt zu einer Identifizierung der Schnittpunkte (I3/1A) und (I4/1A) auf einer Schleife und Schnittpunkten (I1/2B) und (I2/1B) und Extrema (P1/3B), (P2/2A) und (P3/3A) auf der anderen Schleife. Die Scheitelpunkte, die nicht auf dem oberen oder unteren v-Knotensegment liegen, werden in absteigender v-Reihenfolge sortiert, was zu Scheitelpunkten in der folgenden Reihenfolge führt: (I3, P2, I2, P3, I4, P1, I1). Obwohl die Scheitelpunkte I1 und P1 den gleichen v-Wert haben, wird I1 als "höher" als P1 aufgrund der oben beschriebenen Konventionen behandelt. Für Scheitelpunkte auf dem oberen v-Knotensegment oder für diejenigen Scheitelpunkte mit den Typen 1A, 1B, 2A oder 2B werden abfallende monotone Ketten und ihre Typen bestimmt. Insbesondere I3-I4(D), C3-I2(B), P2-P1(I), P3(I), I1-P1(D), C2(B) und I4-C1(B). Es sei angemerkt, daß D oder I ausreichende Bezeichnungen sind, um die Orientierung anzugeben, da angenommen wird, daß v abfallend ist, und um "reguläre" Patches anzuzeigen. Folglich ist es nur erforderlich, anzuzeigen, wie die Segmente in der u-Richtung orientiert sind.
Sobald die Scheitelpunkte identifiziert sind, werden die v-Bereiche konstruiert. Es wird auf die Scheitelpunkte an der oberen v-Knotenlinie zugegriffen, und jeder Satz von Scheitelpunkten wird in absteigender v-Reihenfolge überprüft, bis die Scheitelpunkte an der unteren v-Knotenlinie erreicht sind. Folglich wird auf der Basis der Inspektion des oberen v-Knotensegments ein v-Bereich aktiviert gleich (I3-I4(D), C3-I2(B), R). Der nächste Scheitelpunkt (P2/2A) (d. h. der Scheitelpunkt am Punkt P2 vom Typ 2A) wird verarbeitet. P2 befindet sich innerhalb eines aktiven Bereichs, da er vom Typ 2A ist. Dann werden die Punkte Q1 und Q2 bestimmt, welche den v-Bereich T1 bilden: (I3-Q1(D), C3-Q2(B), G(P2), R). Dann werden zwei neue v-Bereiche aktiviert, die anfänglich identifiziert sind durch (Q1-I4(D), P2-P1(I), R) und (P2-P3(I), Q2-I2(B), R). Dann wird der nächste Scheitelpunkt 12 verarbeitet. 12 ist vom Typ 1B und befindet sich folglich am unteren Rand der rechten Seite eines aktiven v- Bereichs. Es wird der Q-Punkt Q3 bestimmt und der v-Bereich wird geschlossen. Dieser wird als T2 identifiziert: (P2- Q3(I), Q2-I2(B), R, R).
Der nächste Scheitelpunkt P3 wird verarbeitet. P3 ist vom Typ 3A und schließt den aktiven v-Bereich T3: (Q3-P3(I), I2-P3(D), R, P). Es wird der nächste Scheitelpunkt aus der Liste verarbeitet. 14 ist vom Typ 1A und befindet sich folglich am unteren Rand der linken Seite eines aktiven v-Bereichs. Es wird eine horizontale Linie quer gezogen, wobei der Punkt Q4 bestimmt wird und der v-Bereich T4 geschlossen wird: (Q1-I4(D), P2-Q4(I), R, R). Da der v-Bereich T4 geschlossen wird, wird ein neuer v-Bereich unter Verwendung der Punkte (I4-C1(B), Q4-P1(I), R) geöffnet. Es wird der nächste Scheitelpunkt I1 bearbeitet, welcher vom Typ 2B ist. Folglich wird ein zweiter v-Bereich geöffnet, der durch die Punkte (I1-P1(D), I1-C2(B), P) gebildet wird. Dann wird der nächste Scheitelpunkt P1 verarbeitet. P1 ist der rechte Deszendent und linke Deszendent von zwei aktiven v-Bereichen, d. h. eine rechte Seite und eine linke Seite von zwei aktiven v-Bereichen konvergieren im Punkt P1. Die Punkte Q5 und Q6 werden bestimmt, um die folgenden v-Bereiche zu erzeugen und abzuschließen:
T5: (I4-Q5(B), Q4-P1(I), R, R)
T6: (I1-P1(D), I1-Q6(B), P, R)
Als Teil der Optimierungsprozedur wird festgestellt, daß der Bereich T6 von der Höhe Null ist und er deshalb für die nachfolgende Verarbeitung ignoriert wird. Dann wird ein neuer v-Bereich unter Verwendung der Punkte (Q5-C1(B), Q6- C2(B), G(P1)) aktiviert. Dann werden jegliche aktiven v-Bereiche abgeschlossen, indem ihre untere Basis bezeichnet wird, da nichts weiter zu verändern ist. Dies führt zum Bereich T7; (Q5-C1(B), Q6-C2(B), G(P1), K). Folglich werden während der Kompilierung sieben v-Bereiche T1 bis T7 in dem Patch identifiziert.
Der Phase-I-Traversierprozeß wird initiiert, sobald die Kompilierung abgeschlossen: ist. Es wird auf Fig. 11 Bezug genommen, anhand derer eine Übersicht des Phase-I-Traversierprozesses beschrieben wird. Im Schritt 600 werden die Transformationen zwischen den Koordinatensystemen bestimmt. Bei dem Prozeß der vorliegenden Erfindung, vgl. Fig. 11, werden graphische Objekte in einem Objektkoordinaten- oder Modellkoordinaten(MC)-System definiert. Objekte werden in das Weltkoordinaten(WC)-System durch eine Modelliertransformation "M" transformiert. Das Weltkoordinatensystem ist dasjenige Koordinatensystem, in welchem die graphischen Objekte in dem Computer dargestellt werden. Durch die Transformation "V" wird das graphische Objekt in dem WC-System in das Gerätekoordinaten(DC)-System transformiert, welches dem Bildschirmraum der Computeranzeige entspricht. Ein zusätzliches Koordinatensystem, das Beleuchtungskoordinaten(LC)-System wird zur Verfügung gestellt. Das LC-System wird aus dem WC- System durch eine starre, aber berechnungsintensive Transformation "E" erreicht, und das DC-System wird aus dem LC- System durch eine spärliche "N"-Transformation erreicht. Für weitere Informationen bezüglich des LC-Raums und seiner Transformationen siehe Salim Abi-Ezzi und Michael J. Wozny, "Factoring a Homogeneous Transformation for a More Efficient Graphics Pipeline", Computer and Graphics, Bd. 15, Nr. 2, S. 249-258, 1991.
Wie bereits früher angemerkt, werden die Tesselierungskriterien grundsätzlich in dem DC-System spezifiziert. Wenn die Tesselierung im DC-Raum ausgeführt wird, können adaptive Techniken leicht angewendet werden, um die sich ergebenden Dreiecke mit den Schwellenwerten zu vergleichen und die Tesselierungschrittweiteparameter in der erforderlichen Weise einzustellen. Obwohl die Tesselierung in dem DC-System ausgeführt werden kann, sind die sich ergebenden Dreiecke zum Durchführen nachfolgender Beleuchtungsberechnungen ungeeignet. Die "V"-Transformation, welche das graphische Objekt aus dem WC-Raum in den DC-Raum transformiert, ist eine nicht-starre Transformation; folglich behalten die Dreiecke in dem DC-Raum nicht sämtliche in dem MC- und dem WC-Raum spezifizierten Dimensionscharakteristika bei. Beleuchtungsberechnungen, die an den verzerrten Dreiecken durchgeführt werden, führen zur verzerrten Beleuchtungen und Bildern mit einem verzerrten Schattieren (Shading). Darüber hinaus verwendet die V-Transformation eine homogene 4 · 4-Matrix, welche berechnungsintensiv ist. Darüber hinaus sind dann, wenn die Dreiecke in dem WC-Raum tesseliert und in den DC-Raum transformiert werden, die sich ergebenden Kosten beachtlich. Es wird bevorzugt, die Kosten des Berechnungsaufwands und der Geschwindigkeit, die von der Transformation des großen Volumens von während der Tesselierung dieser Oberflächen erzeugten Abtastpunkten verursacht werden, zu vermeiden und nur die Kontrollpunkte der Bilder vor ihrer Tesselierung zu transformieren.
Um die Effizienz der Wiedergabe des Patch auf ein Maximum zu bringen und gleichzeitig zu sichern, daß die Abweichungskriterien erfüllt sind, wird die Schrittweite im LC- Raum bestimmt. Folglich werden im Schritt 605 der Tesselierungsschwellenwert (tessellation threshold) und die sich auf das Patch beziehenden Informationen, insbesondere die Ableitungsgrenzen (derivative bounds) und Kontrollpunkte, in den LC-Raum transformiert. Der Tesselierungsschwellenwert wird aus dem DC-Raum in den LC-Raum gemäß dem maximalen Maßstab der N-Transformation zurückübersetzt. In ähnlicher Weise werden die Kontrollpunkte des Patch aus dem MC-Raum in den LC-Raum unter Verwendung der ME- oder M'-Transformierten transformiert und die Ableitungsgrenzen des Patch werden in den LC-Raum unter Verwendung der Normierten der M'-Transformierten abgebildet.
Es wurde festgestellt, daß durch Sicherstellen, daß die Ableitungsgrenzen des wiederzugebenden Patch den in den LC- Raum transformierten Tesselierungsschwellenwert erfüllen, die nachfolgend tesselierten Dreiecke den Tesselierungsschwellenwert in dem DC-Raum erfüllen. Die erforderliche Transformation aus dem DC-Raum in den LC-Raum "N" ist "spärlich", d. h., die zum Ausführen der Transformation erforderlichen Berechnungen sind minimal. Somit ist der zum Überführen des Abweichungsschwellenwerts in den LC-Raum erforderliche Mehraufwand minimal. Außerdem werden nur die wiederzugebenden Kontrollpunkte des Patch und die Ableitungsgrenzen aus dem MC-Raum in den LC-Raum transformiert.
Es wird wieder auf Fig. 11 Bezug genommen; im Schritt 610 wird die uniforme Schrittweite bestimmt. Vorzugsweise wird dies ausgeführt, indem die sich auf das graphische Objekt, d. h. die beschnittene NURBS beziehenden Informationen über die ME-Transformation in den Beleuchtungskoordinaten- LC-Raum übersetzt werden, und indem die Nachbetrachtungs- Transformationsschwellenwerte zurück in den LC-Raum aus dem DC-Raum unter Verwendung des maximalen Maßstabs der N-Transformation übersetzt werden. Die uniforme Schrittweite kann dann gemäß den folgenden Gleichungen bestimmt werden:
wobei
wobei nud die Anzahl von gleichmäßig beabstandeten Schritten in der u-Richtung, nvd die Anzahl der gleichmäßig beabstandeten Schritten in der v-Richtung, Duu, Dvv bzw. Duv, die Ableitungsgrenzen zweiter Ordnung darstellen und td den Abweichungsschwellenwert darstellt. Für weitere Informationen bezüglich der Bestimmung einer einheitlichen Schrittweite siehe Salim Abbi-Ezzi, Leon Shirman, "The Tessellation of Curved Surfaces Under Highly Varying Transformation", Hrsg.: F. H. Post, W. Barth, Proceedings Eurographics 91, Eu rographics Association (Elsevier Science Publishers, B. V. Nordholland, 1991). Im Schritt 620 werden dann die beschneidenden Bezier-Segmente in lineare Segmente gemäß der Schrittweite tesseliert.
Um eine Bezier-Kurve im Parameterraum zu tesselieren, wird ein Schrittweitenkriterium verwendet, welches vorsieht, daß die Länge eines Liniensegments nicht die Diagonale einer einzelnen rechtwinkligen Zelle, die durch die Schrittweiten des Patch definiert ist, überschreiten sollte.
Folglich kann die Länge der Liniensegmente bestimmt werden:
wobei k eine Konstante ist, die die Auflösung der tesselierten Beschneidekurve in Bezug auf die Oberfläche, auf der sie liegt, spezifiziert, d die Grenze der ersten Ableitung der Kurve ist und Su, Sv die u/v-Schrittweiten des Patch sind.
An diesem Punkt der Verarbeitung hält jeder v-Bereich unabhängig die Informationen, die zum Fortsetzen der Verarbeitung notwendig sind. Somit kann die Phase II auf einem oder mehreren speziellen Prozessoren implementiert werden, welche jeden v-Bereich unabhängig verarbeiten können. Das System ist vorzugsweise mit einer Mehrzahl von Prozessoren derart konfiguriert, daß das Phase-II-Traversieren parallel ausgeführt werden kann, um die für die Verarbeitung erforderliche Zeitdauer weiter zu verringern.
Fig. 13 gibt den Phase-II-Traversierprozeß an. Gemäß Fig. 13 wird im Schritt 650 für jeden v-Bereich ein gleichmäßiges Gitter überlagert, welches in der v-Richtung angepaßt wird, um auf den v-Bereich zu passen. Das gleichmäßige Gitter wird gemäß den u- und v-Schrittweiten erzeugt, die für das Patch bestimmt worden sind. Dann werden die Dreiecke für jeden v-Bereich im Schritt 660 erzeugt. Beleuchtungsberechnungen werden an den Dreiecken durchgeführt und die Dreiecke werden in den DC-Raum transformiert. Dann wird die Abtastzeilenkonversion im Schritt 670 für jedes Dreieck durchgeführt, um die in den Einzelbildpuffer zu speichernden Pixeldaten zu erzeugen. Im Schritt 680 greift die Anzeigesteuereinrichtung auf den Einzelbildpuffer zu, um die Steuersignale zum Betätigen der Pixelorte bei der durch die Pixeldaten angezeigten Intensität und Farbe zu erzeugen, um eine visuelle Darstellung der beschnittenen NURBS zu erzeugen.
Der Schritt des Überlagerns des gleichmäßigen Gitters über jeden v-Bereich und des Tesselierens des v-Bereichs in Dreiecke wird vorzugsweise gemäß des im Folgenden anhand von Fig. 14 beschriebenen Prozesses durchgeführt. Im Schritt 700 wird zunächst die Initialisierung zur Berechnung der u- und v-Gitterlinien durchgeführt, indem die Oberseite und Unterseite des v-Bereichs, die u- und v-Schrittweiten für das Patch und die "Haft"-Linien, die durch den Bereich hindurchgehen, betrachtet werden.
Bei Graphikstandards (z. B. PHIGS) ist eines der Attribute für NURBS-Flächen die Angabe einer bestimmten Anzahl von als "Haft"-Linien (sticky lines) bezeichneten u- und visoparametrischen Linien, die an der Oberseite der Dreiecke wiedergegeben werden sollen. Dies ist nützlich zum Anreichern der Anzeige der Fläche oder um eine Draht-Einzelbild- Wiedergabe auszuführen, wenn es keine Hardware-Schattierung gibt. Diese Linien können gleichmäßig über der gesamten Oberfläche verteilt sein oder sie können gleichmäßig innerhalb jedes Patch beabstandet sein.
Um Haftlinien unterzubringen, wird dieses Attribut während der Phase I des Traversierens überprüft, und es werden jedem Patch Informationen bezüglich der Haftlinien, die es durchlaufen, zur Verfügung gestellt. Um zu sichern, daß diese Haftlinien nicht die Dreiecke durchdringen, werden während der Phase II des Traversierens zwei benachbarte Haftlinien (oder eine Haftlinie und eine Patch- oder v-Bereichs-Begrenzung) verwendet, um eine neue Schrittweite für den Bereich zwischen den zwei Linien zu kompilieren, während das Gitter im Parameterraum erzeugt wird, wobei die neue Schrittweite auf der dynamischen Schrittweite basiert, die für das Patch und den Abstand zwischen den Linien berechnet wird. Angenommen, daß der Abstand zwischen den zwei Linien d ist und daß die Schrittweite für das Patch S. ist, so ergibt sich die neue Schrittweite S':
Für v-Bereiche ohne "Haftlinien" wird dieselbe Formel verwendet, indem d auf die Höhe des v-Bereichs gesetzt wird. Da S' ≤ S sind die Tesselierungskriterien noch erfüllt. Das Ergebnis besteht darin, daß die Haftlinien stets entlang der Dreieckkanten liegen.
Dann wird die Oberfläche gemäß der Gitterpunkte berechnet. Abtastpunkte auf der Oberfläche des Patch werden an den Gitterpunkten im Parameterraum erzeugt, indem die Gleichung des Patch berechnet wird. Für eine effizientere Berechnung wird die Gleichung des Patch (welche in Bezier-Basis ist) in eine Potenz-Basis konvertiert. Um eine Anzahl von Gitterpunkten auf einer einzigen Zeile zu berechnen, wird die univariate Gleichung der Zeile durch Anwendung der Horner-Regel auf die bivariate Patch-Gleichung bestimmt. Punkte auf der Zeile werden dann durch Berechnung dieser Gleichung an speziellen Gitterintervallen berechnet. Durch Verwendung einer "symmetrischen" Potenz-Basis für die Zeilengleichung (bei der der Parameterwert von -0,5 bis +0,5 reicht und nicht von 0 bis 1) können die Gitterpunkte auf einer Zeile in Paaren berechnet werden, indem die symmetrische Natur der Gleichung ausgenutzt wird. Für Details über dieses schnellere Berechnungsverfahren siehe "Symmetric Evaluation of Polynomials", Graphic Gems, Hrsg.: Andrew Glassner, (Academic Press, 1990).
Die bestimmte normierte Normale wird vorzugsweise bestimmt, indem die zwei Tangenten in u und v berechnet werden, ein Kreuzprodukt berechnet und das Ergebnis unter Verwendung einer inversen Quadratwurzelnachschlagetabelle nor miert wird. Wenn es jedoch bekannt ist, daß die Oberfläche eine einfache Geometrie aufweist (z. B. planar, zylindrisch, konisch oder sphärisch ist), ist es bevorzugt, daß andere, speziell auf die Geometrie angepaßte Verfahren verwendet werden, um die Normale effizienter zu berechnen. Für eine sphärische NURBS-Fläche ist beispielsweise die Normale einfach der normierte Vektor, der das Zentrum und den Punkt auf der Oberfläche verbindet.
Bei dem bevorzugten Ausführungsbeispiel wird jeder Punkt der Beschneidekette als selbständiger Punkt (Stand-Alone- Punkt) berechnet. Alternativ werden diejenigen Punkte auf den Beschneidekurven, welche nicht auf dem gleichmäßigen Gitter liegen, als "Stand-Alone-Punkte" berechnet. Vorzugsweise werden diese Stand-Alone-Punkte und ihre Normalen zur Kompilierzeit unter Verwendung einer Potenz-Basis in Modellkoordinaten (MC) berechnet, da dieser Prozeß berechnungsintensiv ist. Für jeden derartigen Punkt (u,v) wird die univariate Gleichung der Kurve beim dem v-Wert berechnet, und diese Kurve wird dann bei dem u-Wert berechnet. Die normierte Normale wird berechnet, indem die beiden Tangentenflächen in u und v berechnet werden, ein Kreuzprodukt berechnet und normiert wird. Selbstverständlich kann dann, wenn die Oberfläche eine einfache Geometrie aufweist, ein optimaleres Verfahren verwendet werden. Folglich werden beim Traversieren diese Punkte einfach von MC zu LC transformiert. Als weitere Optimierung des Prozesses werden im Falle von dynamisch tesselierten Bezier-Beschneidekurven die tesselierten (und berechneten) linearen Segmente über mehrere Tesselierungen hinweg gespeichert und für jede nachfolgende Tesselierung solange wiederverwendet, wie die Schrittweiten des Patch sich nicht ändern.
Es wird mit dem Prozeß der Tesselierung fortgefahren, wie er in Fig. 14 angegeben ist, wobei im Schritt 705 die untere Zeile des Bereichs berechnet wird, indem die Punkte im WC-Raum entlang der von dem Gitter definierten Zeile und die Normalen an diesen Punkten auf der Oberfläche berechnet werden. Im Schritt 707, 710, 709 wird für jedes Paar von Zeilen die obere Zeile in ähnlicher Weise berechnet, um die Punkte und Normalen zu bestimmen. Der von der oberen und der unteren Zeile von Punkten definierte Streifen wird dann trianguliert.
Während der Tesselierung müssen eine Reihe von Falltypen betrachtet werden. Gemäß Fig. 15a und 15b besteht jeder Streifen aus bis zu drei Zonen oder Gruppen von Zellen. Jeder Streifen kann aus einer links beschnittenen Zone, einer unbeschnittenen oder doppelt beschnittenen und einer rechts beschnittenen Zone bestehen. Wie nachfolgend erläutert werden wird, werden diese Zonen unabhängig voneinander verarbeitet. Darüber hinaus werden dann, wenn die obere oder untere Basis während der Kompilierung als vom Typ Lücke klassifiziert worden ist, die Lückenpunkte berechnet, um die Lückenpunkte im LC und die Normale auf der Oberfläche in diesem Punkt zu erzeugen, und unter Verwendung der Gitterpunkte der Zeile werden die Dreiecke erzeugt, um die Lücke zu schließen, Schritt 715. Vorzugsweise werden die Lückenpunkte bei der Kompilierung im MC-Raum berechnet und nachfolgend in den LC-Raum transformiert. Wenn die obere oder untere Basis vom Typ Knoten ist (d. h. die Basis die vollständige Patch-Begrenzung überspannt), wird ein Nachbarstreifen verwendet, um den Begrenzungsstreifen zu triangulieren. In diesem Fall wird die Begrenzungszeile unter Verwendung der benachbarten Patch-Schrittweite trianguliert. Zusammenheftstreifen werden im Schritt 730 ebenfalls erzeugt, wo dies erforderlich, wenn die Basen keine Knotenlinien sind oder wenn es Haft-Linien gibt.
Die Triangulation wird ausgeführt, indem zwei Zeilen von berechneten Gitterpunkten, welche Zellen und die linke und rechte Beschneideseite für die Zeile von Zellen bilden, verwendet werden. Diese Seiten sind die Punkte entlang der v- Bereichsseiten. Wie bereits früher angemerkt, besteht der Streifen aus bis zu drei Zonen: Links beschnittene Zellen, bei denen die linke Beschneideseite die Zelle durchläuft, unbeschnittene Zellen, durch welche keinerlei beschnittene Seiten laufen, doppelt beschnittene Zellen, durch welche sowohl die linke als auch rechte beschnittene Seite laufen, und rechts beschnittene Zellen, bei denen nur die rechte beschnittene Seite hindurchläuft. Es sei angemerkt, daß eine Zeile sämtliche der obigen Zonen haben oder nicht haben kann. Beispielsweise kann eine einzelne Zeile nicht sowohl unbeschnittene als auch doppelt beschnittene Zellen aufweisen. Ein v-Bereich, bei welchem beide Seiten vom Typ Rand sind, weist nur unbeschnittene Zellen auf.
Eine Sequenz von links beschnittenen Zellen wird trianguliert, indem die untere rechte Ecke verwendet wird, sofern die Seite abfallend ist, und die obere rechte Ecke, sofern die Seite ansteigend ist, siehe beispielsweise Fig. 16a. Fig. 16a zeigt die Tesselierung einer Sequenz beschnittener Zellen mit einer abfallenden Seite, so daß die unteren rechten Ecken verwendet werden. Die Reihenfolge, in welcher die Punkte erzeugt und an den Mechanismus zur Tesselierung übermittelt werden, ist durch die numerische Sequenz angezeigt.
Es gibt zwei Fälle zum Tesselieren doppelt beschnittener Zellen. Wie es in Fig. 16B gezeigt ist, tritt der erste Fall auf, wenn sich die u-Ausdehnungen der beiden Seiten in der Zelle nicht überlappen, was auftritt, wenn die beiden Seiten eine entgegengesetzte Orientierung aufweisen. In diesem Falle wird die Zelle vertikal in eine links beschnittene Zelle und eine rechts beschnittene Zelle aufgeteilt, welche individuell tesseliert werden. Wenn sich die u-Ausdehnungen der beiden Seiten überlappen, was dann geschieht, wenn die beiden Seiten die gleiche Orientierung aufweisen, wird ein allgemeineres Schema zum Triangulieren verwendet. Der sich ergebende Effekt ist visuell in Fig. 16c veranschaulicht.
Um die Triangulation für den allgemeinen Fall auszuführen, wird es bevorzugt, daß eine Anpassung des "O(n)-Algorithmus" von Garey et al zum Triangulieren eines monotonen Polygons verwendet wird. Bei diesem Algorithmus wird das Polygon in zwei monotone Seiten sortiert und Dreiecke werden erzeugt, indem ein Stapel verwendet wird, um Punkte nacheinander zu senden und die Seiten und begleitenden Winkel zu überprüfen. Vorzugsweise sind die Punkte bereits an beiden Seiten sortiert, da die Seiten monoton sind. Für weitete Informationen siehe Garey, Johnson, Preparata, Tarjan, "Triangulating a Simple Polygon", Information Processing Letter, Band 7, Nr. 4, S. 157 bis 180 (1978).
Vorzugsweise wird der folgende Prozeß zur Triangulation verwendet. Zwei Genauigkeit-Linear-Linien (diese Linien entsprechen dem bestimmten aktuellen oberen und unteren Zeilenpaar), die den zu triangulierenden Bereich definieren, werden mit Linien "A" und "B" bezeichnet. Drei Register, A, B, C, werden bei diesem Prozeß verwendet. Während des Traversierens werden die beiden Linien traversiert und es werden Aufrufe in die Routinen "Init" und "Send (A/B)" ausgeführt. Init ist ein Prozeß, um damit zu beginnen, einen Streifen zu triangulieren. Die Send-Routine sendet Punkte auf Linie A oder Linie B an die Register. Das edge_flag und other_edge_flag zeigen an, ob eine Linie zu zeichnen ist zwischen dem neuen Punkt und dem Punkt, den er ersetzt, oder dem Punkt, den er nicht ersetzt. Beispielhafter Pseudo-Befehlscode für die Triangulation ist:
1. Init (a_b_new_cw_flag):count ← 0
2. Send (Reg A/B, Pnt, edge_flag, other_edge_flag):
Count ++;
Reg C ← Pnt;
If Count ≥ 3, (Reg A, Reg B, Reg C);
Reg A/B ← Reg C;
Wenn NURBS-Flächen wiedergegeben werden, besteht eine Möglichkeit, daß Lücken in der Fläche auftreten können. Für benachbarte Patches kann sich eine unterschiedliche Schrittweite ergeben, welche zu Lücken an gemeinsamen Kanten führt. Dies ist in Fig. 17a veranschaulicht. Eine einfache Lösung ist in Fig. 17b veranschaulicht. Fig. 17b veranschaulicht einen Nachbarstreifen, welcher erzeugt wird, um die in Fig. 17a gezeigte Lücke auszufüllen.
Bei der vorliegenden Erfindung werden die Lücken betreffenden Informationen während des Kompilierens und der Phase I des Traversierprozesses erzeugt, so daß die Lücken vermieden werden können, wenn die Patches unabhängig voneinander in Phase II traversiert werden. Die die Lücken entlang der Begrenzung zwischen zwei gegebenen Patches betreffenden Informationen werden zusammen mit einem der Patches zur Verfügung gestellt. Obwohl eine gemeinsame Begrenzung zwischen den beiden Patches vorhanden ist, ist es nur erforderlich, daß eines der zwei Patches sich mit der Lücken-Situation befaßt. Vorzugsweise ist es das Patch mit der größeren Schrittweite entlang der gemeinsamen Begrenzung, daß die Lückenvermeidungsinformationen erzeugt.
Es gibt zwei Arten von Lückenvermeidungsinformationen, die in Abhängigkeit von der durchgeführten Lückenerzeugungstechnik verwendet werden. Die erste Technik ist der Nachbarstreifen (adjacency strip). Wenn zwei gegebene Patches beide nicht beschnitten sind, aber eine unterschiedliche Schrittweite aufweisen, dann erzeugt das Patch mit der größeren Schrittweite einen Nachbarstreifen, um Lücken zu seinem Nachbarn zu vermeiden. Im Falle von beschnittenen Patches kann ein Nachbarstreifen noch dann verwendet werden, wenn die obere oder untere Basis ein Knotensegment ist. Während der Phase I des Traversierprozesses werden die Informationen bezüglich der Schrittweite des Nachbars und des Begrenzungstyps (z. B. oben, unten, rechts, links) mit jedem Patch derart aufrechterhalten, daß das Patch unabhängig von dem Nachbarn bearbeitet werden kann. Während der Phase 11 des Traversierprozesses findet die Triangulation statt und es werden die gegebenenfalls erforderlichen Nachbarstreifen erzeugt. Ein Beispielalgorithmus für die Erzeugung des Nachbarstreifens ist in Fig. 18a angegeben. Unter Verwendung der hier beschriebenen Nachbartechnik, vergleiche Fig. 18b, wird der Streifen erzeugt, indem das Patch mit der größeren Schrittweite B mit Punkten aus dem Patch A trianguliert wird.
Ein Zusammenheftstreifen ist ein allgemeinerer Mechanismus, um Lücken zwischen zwei Patches unterschiedlicher Schrittweite zu schließen. Vorzugsweise wird er verwendet, wenn der Nachbarstreifen nicht verwendet werden kann, da er weniger effizient ist. Ein Zusammenheftstreifen hat eine Breite von Null im Parameterraum und besteht somit aus nahezu degenerierten Dreiecken im Modellraum (siehe Fig. 19a). Die Beschreibung eines Zusammenheftstreifens wird während der Phase I des Traversierens erzeugt und während der Phase II benutzt. Die Zusammenheftstreifenbeschreibung basiert auf den Schnittscheitelpunkten der Begrenzung, den v-Bereichs- Schnittpunkten an beiden Seiten der Begrenzung und der Schrittweite des Patches entlang der Begrenzung. Auf der Basis dieser Informationen werden zwei Sequenzen von Skalaren für jede benachbarte Begrenzung, eine für das erste Patch (A) und eine für das zweite Patch (B), erzeugt. Eine Sequenz von Skalaren für das Patch umfaßt die parametrischen Werte, wo die Patch-Begrenzungs-Abtastpunkte auftreten, in ansteigender Reihenfolge. Die beiden Sequenzen von Skalaren werden dann zu einer Sequenz verbunden, in der Duplikate entfernt werden. Jeder Skalar wird gekennzeichnet, um den Ursprung des Skalars zu identifizieren. Beispielsweise kann ein Etikett "A", "B" oder "C" sein, um anzuzeigen, ob der Skalar von einer Sequenz des Patch A, einer Sequenz des Patch B oder von beiden herrührt. Die Sequenz von Skalaren und Etiketten wird als Zusammenheftpunkte (stitching points) bezeichnet, und es wird auf sie für die Erzeugung des Zusammenheftstreifens währender Phase 11 des Traversierprozesses Bezug genommen.
Fig. 19b veranschaulicht den Zusammenheftstreifen gemäß Fig. 19a im Objektraum. Fig. 19c gibt einen Beispielalgorithmus an zum Erzeugen eines Zusammenheftstreifens aus den Zusammenheftpunkten. Es sei angemerkt, daß die Hauptdifferenz zwischen einem Zusammenheftstreifen und einem Nachbar streifen darin besteht, daß der Erstgenannte das Hinzufügen neuer Dreiecke zum Schließen der Lücke umfaßt, wie es in den Fig. 19a und 19b veranschaulicht ist, während der Letztgenannte das Auswählen der Dreiecke eines Nachbarstreifens zum Vermeiden der Lücken umfaßt. Die Nachbarstreifenlösung ist effizienter, da sie nicht die Erzeugung von zusätzlichen Dreiecken erfordert; jedoch funktioniert der Nachbarstreifen nur in einfachen Fällen, in denen es keine Beschneide- oder Haft-Linien gibt. Somit ist es bevorzugt, den Nachbarstreifen für einfache Fälle zu verwenden und den Zusammenheftstreifen für die komplizierteren Fälle.
Sobald die Dreiecke tesseliert sind, werden die bestimmten Punkte und Normalen jedes v-Bereichs an eine Graphikmaschine oder ein Graphik-Subsystem weitergeleitet. Beleuchtungsberechnungen werden im LC-Raum an jedem Dreieck durchgeführt, vorzugsweise unter Verwendung des Gouraud-Schattierungsverfahrens, welches eine Farbe pro Scheitelpunkt auf der Grundlage der Normalen, der Oberflächeneigenschaft, der Lichtquellen und dem Betrachtungspunkt berechnet und die Farbe über das Dreieck interpoliert. Alternativ kann das Phong-Schattieren verwendet werden, um die Beleuchtungsberechnungen durchzuführen. Das Phong-Schattierverfahren interpoliert die Normalen und berechnet die Farbe für jedes Pixel.
Die Dreiecke werden aus dem LC-Raum in den DC-Raum transformiert, nachdem die Dreiecke so modifiziert worden sind, daß sie die Beleuchtungscharakteristika enthalten. Die N-Transformation, welche die Objekte aus dem LC-Raum in den DC-Raum transformiert, ist eine spärliche Transformation und ist ziemlich unaufwendig zu implementieren. Obwohl eine größere Anzahl von Transformationen erforderlich ist, um sämtliche eine gekrümmte Oberfläche darstellende tesselierte Dreiecke anstelle des Erzeugens von Dreiecken im DC zu transformieren, werden die Kosten durch die Spärlichkeit der Transformation ebenso wie durch den sich ergebenden Effekt des Erzeugens exakt schattierter gekrümmter Oberflächen mehr als gerechtfertigt.
Die Dreiecke werden dann abtast-konvertiert, um die Pixeldaten zu erzeugen, die zur Ansteuerung der Anzeigeeinrichtung verwendet werden. Die im DC-Raum erzeugten Pixeldaten definieren verschiedenen Attribute des anzuzeigenden Objekts, einschließlich der Form, des Orts, der Farbe und Intensität des Objekts auf der Anzeige des Objekts. Die erzeugten Pixeldaten werden in einem Einzelbildpuffer an einem Ort gespeichert, welcher mit einer vorgegebenen Position auf der Anzeigeeinrichtung korrespondiert. Für weitere Informationen bezüglich der Abtastumsetzung siehe Foley, von Dam, Feiner, Hughes, Computer Graphics. Principles and Practice, 2. Auflage, S. 945 bis 965, (1990, Addison-Wesley Publishing). Vorzugsweise wird eine Z-Pufferung zu diesem Zeitpunkt durchgeführt, um eine dimensionale Tiefeninformation des graphischen Objekts zur Verfügung zu stellen.
Die gekrümmte Oberfläche wird auf der Anzeigeeinrichtung gemäß den erzeugten Pixeldaten erzeugt. Die in dem Einzelbildpuffer gespeicherten Pixeldaten werden dekodiert, um die Anzeigesteuereinrichtung und die Anzeigeeinrichtung derart zu steuern, daß sie die Pixel bei dem durch die Pixeldaten spezifizierten Ort, der Farbe und der Intensität erzeugt, um eine sichtbare gekrümmte Oberfläche auf der Anzeigeeinrichtung zu erzeugen.
Der obige Prozeß schafft darüber hinaus ein System, in welchem die komplexen Operationen während des Kompilierens in dem Wirts-Prozessor durchgeführt werden, welcher die Ressourcen zur Ausführung dieser komplexen Prozesse aufweist. Die einfachen, aber sich wiederholenden Operationen können in speziellen Verarbeitungseinrichtungen ausgeführt werden, welche in ihrer Implementierung schnell und unaufwendig zur Verfügung zu stellen sind. Darüber hinaus schafft der oben genannte Prozeß ein System, welches Vorteil aus der parallelen Verarbeitung ziehen kann, um das System weiter zu beschleunigen und seine Effizienz zu erhöhen, da jeder v-Be reich während des Kompilierens so konstruiert wird, daß er die meisten der während des Traversierens erforderlichen Informationen enthält, und die Phase 11 des Traversierens unabhängig und parallel in Bezug auf jeden v-Bereich durchgeführt werden kann.
Das System der vorliegenden Erfindung kann am besten unter Bezugnahme auf Fig. 20 beschrieben werden. Eine Eingabe 800 wird dem Wirts-Computer 810 zur Verfügung gestellt. Der Wirt wird verwendet, um die komplexen Prozesse und Berechnungen durchzuführen, welche signifikante Ressourcen erfordern. Der Co-Prozessor 820 ist ein spezieller Prozessor oder ein Prozessor, welcher einfache, aber in hohem Maße wiederholte Prozeßschritte durchführt. Beispielsweise kann eine Gleitkommaverarbeitungseinheit (FPU) in Verbindung mit einem VLSI-Chip verwendet werden, das so konfiguriert ist, daß es spezielle Funktionen, wie beispielsweise die Abtastkonversion von Dreiecken in Pixel, durchführt. Der Prozeß der vorliegenden Erfindung führt von selbst zu einer Unterteilung der Prozeßschritte, um die Effizienz der Wiedergabe-Pipeline auf ein Maximum zu bringen. Insbesondere führt der Wirt den Kompilierungsprozeß aus.
Bei einem Ausführungsbeispiel werden die einheitliche Schrittweite und die Kontrollpunkte der gekrümmten Oberfläche an den Co-Prozessor 820 gesendet, damit dieser die in hohem Maße wiederholten Berechnungen, wie beispielsweise die Tesselierung der Dreiecke, die die gekrümmte Oberfläche darstellen, die Beleuchtungsbestimmungen und die Abtastkonversion der Dreiecke in Pixeldaten, die in dem Einzelbildpuffer 830 gespeichert werden sollen, ausführt. Bei diesem Ausführungsbeispiel besteht der Co-Prozessor aus einer Gleitkommaverarbeitungseinheit (FPU), einem Speicher, und einem VLSI- Entwurf zum Wiedergeben von Dreiecke, um Pixeldaten zu erzeugen. Die die den Speicher benutzende FPU tesseliert die gekrümmte Oberfläche in Dreiecke, führt Beleuchtungsbestimmungen aus und transformiert die Dreiecke aus dem LC-Raum in den DC-Raum. Die VLSI-Schaltung konvertiert jedes Dreieck in Pixeldaten und speichert die Pixeldaten in den Einzelbildpuffer. Alternativ tesseliert der Wirt 810 die gekrümmte Oberfläche in Dreiecke und der Co-Prozessor führt einfach die Abtastkonversionen aus, um Pixeldaten für jedes Dreieck zu erzeugen. Vorzugsweise ist der Co-Prozessor 820 in spezieller Hardware implementiert, um die Verarbeitungsgeschwindigkeit auf ein Maximum zu bringen. Ein Beispiel eines graphischen Co-Prozessors 820 ist der SPARCstation 2/GT-Graphikbeschleuniger, der von Sun Microsystems, Inc. hergestellt wird.
Die Anzeigesteuereinrichtung, ein zweiter Spezialprozessor, 840 liest die Pixeldaten aus dem Einzelbildpuffer und betätigt die zugehörigen Pixel auf der Anzeigeeinrichtung 850. Wie bereits früher angemerkt, werden die Pixeldaten an vorgegebenen Orten in dem Einzelbildpuffer derart gespeichert, daß es eine vorgegebene Beziehung zwischen dem Ort der Pixeldaten in dem Einzelbildpuffer und der den Pixeldaten entsprechenden Betätigung der Pixel auf der Anzeigeeinrichtung gibt. Vorzugsweise werden die Daten entsprechend den XY-Koordinatenorten der Pixel in dem DC-Raum gespeichert. Die Anzeigesteuereinrichtung 840 liest sequentiell die Pixeldaten aus dem Einzelbildpuffer 830 und gibt Steuersignale an die Anzeigeeinrichtung aus, um den Elektronenstrahl und folglich die Farbe, Intensität und den Ort jedes Pixels zu steuern.

Claims

1. Ein Verfahren zur Tesselierung von graphischen Bildern zur Wiedergabe auf einer graphischen Anzeigeeinrichtung (50) unter der Steuerung einer Graphiksteuereinrichtung (45), wobei die graphischen Bilder beschnittene nicht-uniforme rationale B-Spline-Flächen (NURBS-Flächen) aufweisen, wobei jede beschnittene NURBS einen ersten Satz von die Fläche definierenden Kontrollpunkten und einen zweiten Satz von zumindest eine Beschneideschleife über die Fläche definierenden Kontrollpunkten aufweist, wobei die Kontrollpunkte in einem Modellkoordinatenraum (MC-Raum) definiert sind, wobei die graphische Anzeigeeinrichtung (50) entsprechend einem Gerätekoordinatenraum (DC-Raum) definiert ist, wobei das Verfahren die Schritte aufweist:

Kompilieren (103) der beschnittenen NURBS-Flächen in zumindest ein Patch, das zumindest einen v-Bereich aufweist, wobei das Kompilieren die Schritte umfaßt:

Reduzieren (310) der NURBS in zumindest ein Bezier-Patch,

Unterteilen der Beschneideschleifen (320) in monotone Beschneideketten pro Bezier-Patch, und

Unterteilen jedes Patch (330) in zumindest einen u-v-monotonen v-Bereich, wobei jeder v-Bereich von einer oberen Grundlinie, einer unteren Grundlinie, einer linken Seite und einer rechten Seite gebildet wird,

wobei die obere und die untere Grundlinie von isoparametrischen Linien entlang der u-Achse definiert sind und wobei die rechte und die linke Seite von u-v- monotonen Linien definiert sind, die von einer Beschneidekette oder einem Rand des Patch gebildet sind;

Traversieren (105, 107) jedes v-Bereichs, umfassen die Schritte:

Tesselieren (660) jedes v-Bereichs in eine Vielzahl von. Dreiecken;

Erzeugen von jedes Dreieck darstellenden Pixel-Daten (670), wobei die Pixel-Daten die Intensität der auf der graphischen Anzeigeeinrichtung (50) anzuzeigenden Pixel spezifizieren, und

Speichern der Pixel-Daten in einem Einzelbildpuffer (40), wobei die Pixel-Daten an einem Ort in dem Einzelbildpuffer (40) gespeichert werden, der dem Ort des Pixels in dem DC-Raum entspricht; und

Lesen der in dem Einzelbildpuffer (40) gespeicherten Pixel-Daten (680) und Erzeugen von Steuersignalen zum Aktivieren der Pixel auf der graphischen Anzeigeeinrichtung (50) an dem durch die Pixel-Daten angezeigten Ort und in der durch die Pixel-Daten angezeigten Intensität durch die graphische Anzeigesteuereinrichtung (45);

wobei beschnittene NURBS-Flächen erzeugt und auf der graphischen Anzeigeeinrichtung (50) angezeigt werden.

2. Das Verfahren nach Anspruch 1, ferner umfassend den Schritt des Traversierens jedes Patch durch Festlegen einer einheitlichen Schrittweite für jedes Patch, wobei die Schrittweite verwendet wird, um jedes Patch in eine Mehrzahl von Dreiecken zu tesselieren.

3. Das Verfahren nach Anspruch 2, wobei der Schritt des Traversierens (105, 107) jedes v-Bereichs ferner umfaßt den Schritt des Überlagerns eines gleichmäßigen Gitters von Zellen, das von den Grenzen des v-Bereichs und der einheitlichen Schrittweite in u und v bestimmt wird, wobei der Schritt des Tesselierens (660) jedes v-Bereichs das Tesselieren jeder Zeile von Zellen in eine Mehrzahl von Dreiecken umfaßt.

4. Das Verfahren nach Anspruch 3, wobei jede Beschneidekette zumindest ein Segment umfaßt, wobei jedes Segment von einer Koordinate in u, v und einer Anzeige, ob das Segment in der u- oder v-Richtung ansteigend oder abfallend ist, identifiziert wird.

5. Das Verfahren nach Anspruch 4, wobei jedes Segment eine Bezier-Kurve ist.

6. Das Verfahren nach Anspruch 4, wobei jedes Segment ein lineares Segment ist.

7. Das Verfahren nach Anspruch 4, wobei der Schritt des Kompilierens ferner umfaßt den Schritt des Identifizierens der Extremscheitelpunkte (extreme vertices) und Schnittscheitelpunkte (intercept vertices) an den Patch-Rand-Überquerungen der Beschneideketten.

8. Das Verfahren nach Anspruch 7, wobei ein Extremscheitelpunkt identifiziert wird, wenn ein Segment gegenüber einem vorhergehenden benachbarten Segment der Beschneidekette eine entgegengesetzte u- oder v-Richtung hat oder wenn es selbst ein u/v-Extremum aufweist, sofern es eine Bezier- Kurve ist, und wobei ein Randscheitelpunkt (border vertex) an dem Ort identifiziert wird, an dem ein Segment eine Patch-Begrenzung überquert.

9. Das Verfahren nach Anspruch 8, ferner umfassend den Schritt des Klassifizierens jedes Scheitelpunkts nach einem Typ.

10. Das Verfahren nach Anspruch 9, wobei der Schritt des Unterteilens jedes Patch in zumindest einen u-v-monotonen v- Bereich den Schritt umfaßt:

Identifizieren zumindest eines Paars von Schnittscheitelpunkten auf der linken und der rechten Seite;

Identifizieren des Anfangs eines aktiven v-Bereichs entsprechend den identifizierten Schnittscheitelpunkten an einem oberen Rand;

Verarbeiten der verbleibenden Schnittscheitelpunkte und Extremscheitelpunkte in absteigender Reihenfolge gemäß dem v-Koordinatenwert der Scheitelpunkte, wobei dieser Schritt das Überprüfen des Typs jedes Scheitelpunktes und des Bildens der Unterseite und des Abschlusses von aktiven v-Bereichen und des Öffnens von neuen v-Bereichen entsprechend dem Typ des Scheitelpunktes umfaßt.

11. Das Verfahren nach Anspruch 1, wobei der Schritt des Traversierens jedes Patch die Schritte umfaßt:

Bestimmen der Ableitungsgrenzen (derivative bounds) der zu tesselierenden und wiederzugebenden gekrümmten Fläche;

Transformieren der Ableitungsgrenzen in einen Beleuchtungskoordinatenraum (LC-Raum) entsprechend der Normierten der Transformierten aus dem Modellkoordinatenraum (MC-Raum) in den LC-Raum;

Transformieren der Kontrollpunkte in den LC-Raum in Übereinstimmung mit der Transformierten aus dem MC-Raum in den LC-Raum;

Übersetzen der Tesselierungskriterien in den LC-Raum entsprechend dem Maximalmaßstab der Betrachtungstransformation aus dem DC-Raum in den LC-Raum; und

Bestimmen der einheitlichen Schrittweite im LC-Raum unter Verwendung der Ableitungsgrenzen, der Kontrollpunkte und der Tesselierungskriterien.

12. Das Verfahren nach Anspruch 1, wobei der Schritt des Kompilierens ferner den Schritt des Zur-Verfügung-Stellens von Lückenvermeidungsinformationen mit jedem Patch umfaßt; wobei das Verfahren ferner den Schritt des Erzeugens von Dreiecken zum Füllen von Lücken zwischen den Patches umfaßt.

13. Das Verfahren nach Anspruch 12, wobei der Schritt des Erzeugens von Dreiecken zum Füllen der Lücken zwischen den Patches die Erzeugung eines Nachbarstreifens (adjacency strip) umfaßt, dem einem Patch mit einer größeren Schrittweite zugeordnet ist, welcher an die Größe der Dreiecke in dem Nachbarstreifen angepaßt ist, um Lücken zu entfernen.

14. Das Verfahren nach Anspruch 12, wobei der Schritt des Erzeugens von Dreiecken zum Füllen von Lücken zwischen den Patches die Erzeugung eines Zusammenheftstreifens (stitching strip) durch Hinzufügen von Dreiecken zwischen den Patches umfaßt.

15. Eine Einrichtung (25) zum Tesselieren von graphischen Bildern mit beschnittenen nicht-uniformen rationalen B-Spline-Flächen (NURBS-Flächen) zum Wiedergeben auf einer graphischen Anzeigeeinrichtung (50) unter Steuerung einer Graphiksteuereinrichtung (45), wobei jede beschnittene NURBS einen ersten Satz von die Fläche definierenden Kontrollpunkten und einen zweiten Satz von zumindest eine Beschneideschleife über die Fläche definierenden Kontrollpunkten aufweist, wobei die Kontrollpunkte in einem Modellkoordinatenraum (MC-Raum) definiert sind, wobei die graphische Anzeigeeinrichtung gemäß einem Gerätekoordinatenraum (DC-Raum) definiert ist, wobei die Einrichtung (25) aufweist:

einen Kompiler zum Kompilieren (103) der beschnittenen NURBS in zumindest ein Patch, das zumindest einen u-v-monotonen v-Bereich aufweist, aufweisend:

eine Einrichtung zum Reduzieren (310) der NURBS in zumindest ein Bezier-Patch, eine Einrichtung zum Unterteilen der Beschneideschleifen (320) in monotone Beschneideketten pro Bezier-Patch, und

eine Einrichtung zum Unterteilen jedes Patch (330) in zumindest einen u-v-monotonen v-Bereich, wobei jeder v-Bereich von einer oberen Grundlinie, einer unteren Grundlinie, einer linken Seite und einer rechten Seite gebildet ist, wobei die obere und die untere Grundlinie von isoparametrischen Linien entlang der u- Achse definiert sind und wobei die rechte und die linke Seite von u,v-monotonen Linien definiert sind, die von einer Beschneidekette oder einer Begrenzung des Patches gebildet sind;

eine Einrichtung zum Traversieren (105, 107) jedes v-Bereichs, aufweisend:

eine Einrichtung zum Tesselieren (660) jedes v-Bereichs in einer Mehrzahl von Dreiecken und

eine Einrichtung zum Erzeugen von jedes Dreieck darstellenden Pixel-Daten (670), wobei die Pixel-Daten die Intensität des auf der graphischen Anzeigeeinrichtung anzuzeigenden Pixels spezifizieren;

ein mit der Einrichtung zum Erzeugen der Pixel-Daten gekoppelter Einzelbildpufferspeicher (40) zum Speichern der Pixel-Daten an einem dem Ort des Pixels in dem DC-Raum entsprechenden Ort;

wobei die graphische Anzeigesteuereinrichtung (45) die in dem Einzelbildpuffer (40) gespeicherten Pixel-Daten liest (680) und Steuersignale erzeugt, um die Pixel auf der graphischen Anzeigeeinrichtung (50) an einem von den Pixel-Daten angezeigten Ort und in einer von ihnen angezeigten Intensität zu aktivieren;

16. Die Einrichtung nach Anspruch 15, ferner aufweisend eine Einrichtung zum Traversieren jedes Patch, die eine Einrichtung zum Bestimmen einer einheitlichen Schrittweite für jedes Patch aufweist, wobei die Schrittweite verwendet wird, um jedes Patch in eine Vielzahl von Dreiecken zu tesselieren.

17. Die Einrichtung nach Anspruch 16, wobei die Einrichtung zum Traversieren jedes v-Bereichs ferner ein gleichmäßiges Gitter von Zellen umfaßt, das aus den Begrenzungen des v- Bereichs und der einheitlichen Schrittweite in u und v bestimmt wird, wobei die Einrichtung zum Tesselieren eine Einrichtung zum Tesselieren jeder Zeile von Zellen in eine Mehrzahl von Dreiecken aufweist.

18. Die Einrichtung nach Anspruch 17, wobei jede Beschneidekette zumindest ein Segment aufweist, wobei jedes Segment durch eine Koordinate in u, v und eine Anzeige, ob das Segment in der u- oder v-Richtung ansteigt oder abfällt, identifiziert ist.

19. Die Einrichtung nach Anspruch 18, wobei die Einrichtung zum Kompilieren ferner eine Einrichtung zum Identifizieren der Extremscheitelpunkte und der Schnittscheitelpunkte an Patch-Begrenzungsüberquerungen der Beschneideketten aufweist.

20. Die Einrichtung nach Anspruch 19, wobei ein Extremscheitelpunkt identifiziert ist, wenn ein Segment gegenüber einem vorhergehenden benachbarten Segment der Beschneidekette eine entgegengesetzte u- oder v-Richtung hat, und ein Begrenzungsscheitelpunkt an dem Ort, an dem ein Segment eine Patch-Begrenzung überquert, identifiziert ist.

21. Die Einrichtung nach Anspruch 20, ferner aufweisend eine Einrichtung zum Klassifizieren jedes Scheitelpunkts nach einem Typ.

22. Die Einrichtung nach Anspruch 21, wobei die Einrichtung zum Unterteilen jedes Patch in zumindest einen u-v-monotonen v-Bereich aufweist:

eine Einrichtung zum Identifizieren zumindest eines Paares von Schnittscheitelpunkten auf der linken und der rechten Seite;

eine Einrichtung zum Identifizieren des Anfangs eines aktiven v-Bereichs entsprechend den identifizierten Schnittscheitelpunkten an dem oberen Rand;

eine Einrichtung zum Verarbeiten der verbleibenden Schnittscheitelpunkte und Extremscheitelpunkte in absteigender Reihenfolge gemäß dem v-Koordinatenwert der Scheitelpunkte, wobei die Einrichtung das Bestimmen des Typs jedes Scheitelpunkts und das Bilden des Bodens und des Abschlusses aktiver v-Bereiche und die Eröffnung neuer v-Bereiche entsprechend dem Typ des Scheitelpunktes umfaßt.

23. Ein Computersystem zum Tesselieren von graphischen Bildern, die beschnittene nicht-uniforme rationale B-Spline- Flächen (NURBS-Flächen) zur Wiedergabe auf einer graphischen Anzeigeeinrichtung (50) aufweisen, wobei jede beschnittene NURBS einen ersten Satz von die Fläche definierenden Kontrollpunkten und einen zweiten Satz von zumindest eine Beschneideschleife über die Fläche definierenden Kontrollpunkten hat, wobei die Kontrollpunkte in einem Modellkoordinatenraum (MC-Raum) definiert sind, wobei die graphische Anzeigeeinrichtung in Übereinstimmung mit einem Gerätekoordinatenraum (DC-Raum) definiert ist, wobei das System aufweist:

einen Wirtsprozessor (10), wobei der Wirtsprozessor

die beschnittene NURBS-Fläche in zumindest ein Patch mit zumindest einem v-Bereich kompiliert (103), indem die NURBS in zumindest ein Bezier-Patch reduziert wird, die Beschneideschleifen (220) in monotone Beschneideketten gemäß dem Patch, das der Abschnitt der Beschneideschleife begrenzt, unterteilt werden, und indem jedes Patch in zumindest einen u-v-monotonen v-Bereich unterteilt (330) wird, wobei jeder v-Bereich von einer oberen Grundlinie, einer unteren Grundlinie, einer linken Seite und einer rechten Seite gebildet ist, wobei die obere und die untere Grundlinie durch isoparametrische Linien entlang der u-Achse definiert sind und wobei die rechte und die linke Seite von u,v- monotonen Linien definiert sind, die von einer Beschneidekette oder einer Begrenzung des Patch gebildet sind, und

jedes Patch traversiert (105, 107), indem eine einheitliche Schrittweite für jedes Patch bestimmt wird, wobei die Schrittweite verwendet wird, um jedes Patch in eine Vielzahl von Dreiecken zu tesselieren;

ein mit dem Wirtsprozessor gekoppeltes graphisches Verarbeitungssubsystem (25), wobei das graphische Verarbeitungssubsystem ein einheitliches Gitter von Zellen überlagert, das aus den Begrenzungen des v-Bereichs und der einheitlichen Schrittweite u und v bestimmt wird, jede Zeile von Zellen in eine Vielzahl von Dreiecken tesseliert und jedes Dreieck darstellende Pixel-Daten erzeugt, wobei die Pixel-Daten die Intensität des auf der graphischen Anzeigeeinrichtung anzuzeigenden Pixels spezifizieren; und

ein mit dem graphischen Verarbeitungssubsystem gekoppelter Einzelbildpuffer (40) zum Speichern der Pixel-Daten, wobei die Pixel-Daten an einem Ort in dem Einzelbildpuffer gespeichert werden, der dem Ort des Pixels in dem Gerätekoordinatenraum entspricht; und

eine mit dem Einzelbildpuffer (40) und der graphischen Anzeigeeinrichtung (50) gekoppelte graphische Anzeigesteuereinrichtung (45) zum Lesen der in dem Einzelbildpuffer gespeicherten Pixel-Daten und zum Erzeugen von Steuersignalen, um die Pixel auf der graphischen Anzeigeeinrichtung an den von den Pixel-Daten spezifizierten Orten und mit von ihnen spezifizierten Intensitäten zu aktivieren;

wobei beschnittene NURBS-Flächen erzeugt und auf der graphischen Anzeigeeinrichtung angezeigt werden.

24. Die Einrichtung nach Anspruch 23, wobei das graphische Verarbeitungssubsystem aufweist:

zumindest eine Gleitkomma-Verarbeitungseinheit (32, 37, 41) zum Erzeugen von Dreiecken gemäß der einheitlichen Schrittweite, zum Beleuchten der Dreiecke entsprechend den für das wiederzugebende graphische Bild definierten Lichtquellen und zum Transformieren des Polygons aus dem Beleuchtungskoordinatenraum (LC-Raum) in den DC-Raum; und

zumindest einen mit dem Gleitkomma-Prozessor gekoppelten speziellen Graphikprozessor (33, 34, 36) zum Empfangen der transformierten Polygone und zum Erzeugen von Pixel-Daten für jedes empfangene Polygon.