DE3855012T2

DE3855012T2 - Graphisches Anzeigeverfahren

Info

Publication number: DE3855012T2
Application number: DE3855012T
Authority: DE
Inventors: James G Fiasconaro
Original assignee: Hewlett Packard Co
Current assignee: HP Inc
Priority date: 1987-02-05
Filing date: 1988-02-04
Publication date: 1996-06-13
Anticipated expiration: 2008-02-05
Also published as: DE3855012D1; EP0466283A3; DE3855541D1; EP0277832A2; EP0466283A2; EP0464962A3; EP0466282A2; US4999789A; EP0464963B1; DE3889134D1; DE3856110D1; DE3855639T2; US5363478A; EP0464963A3; JPH01201777A; EP0277832B1; EP0466281A2; DE3855541T2; EP0466281B1; EP0466282A3

Description

Hintergrund und Zusammenfassung der Erfindung

Ein typisches dreidimensionales Graphiksystem mit hoher Leistungsfähigkeit wird eine zu liefernde Oberfläche als Oberflächenstücke beschreiben, die durch Funktionen für jedes Stück definiert sind. Solche Funktionen können beispielsweise nicht gleichförmige, rationale B-Splines sein. Die Verwendung von B-Splines erlegt den Kanten der Oberflächenstücke bestimmte Begrenzungen aull. Den B-Spline-Funktionen ist ein normalerweise rechtwinkliger uv-Parameterraum zugeordnet. Parametrische erzeugende Funktionen für die Stücke für u und v berechnen die Werte der Koordinaten im XYZ-Raum. Der rechtwinklige uv-Raum begrenzt die Exaktheit, mit der die B-Spline-Erzeugerfunktionen für die Stücke Oberflächenstücke darstellen können, die Kanten bestimmter Formen haben. Beispielsweise ist es schwierig, eine gute B-Spline-Beschreibung für ein Stück zu erzeugen, das ein rechwinkliger Bereich ist, wobei ein kreisförmiger Abschnitt aus seinem Inneren entfernt ist. Sowohl der rechtwinklige Bereich als auch der kreisförmige Abschnitt für sich würden praktisch handhabbar sein, jedoch ist ihre Kombination ein zu komplexes Grundelement für eine eindeutige vereinheitlichte B-Spline-Beschreibung auf dem Stücke-Level Unterteilen des Stückes widerspricht erstens dem Beweggrund, überhaupt Stücke zu haben. Das Trimmen ist ein Weg, um die B-Spline-Beschreibung des rechtwinkligen Bereiches mit einer anderen für den kreisförmigen Abschnitt zu verbessern und einen Rybrid-Flächenstück zu erzeugen, in dem eine B-Spline-Beschreibung die durch eine andere beschriebene Oberfläche "wegschneidet". Im Stand der Technik (IEEE COMPUTER GRAPHICS AND APPLICATIONS. vol. 7, no. 1, Jan. 1987 NFW YORK US, pages 33-43; M.S. CASALE: "Free-form solid modeling with trimmedd surface patches") ist das Trimmen von der Software des Graphiksystems durchgeführt worden, bevor die Gerätekoordinaten zu der Anzeige-Hardware geliefert wurden Ein solches Trimmen ist notwendigerweise eine sehr komplexe Aufgabe und ist im allgemeinen zu langsam zur Verwendung bei sich bewegenden Bildern oder interaktiven Systemen Es würde wünschenswert sein, die Verwendung von B-Splines beizubehalten und die Vorteile zu erreichen, die durch die Technik der Oberflächenbeschreibung angeboten werden, jedoch gleichzeitig ein Hochgeschwindigkeits-Trimmen erlauben.
Dies wird mit dem Verfahren gemäß Anspruch 1 erreicht.
Gemäß einem bevorzugten Verfahren der Erfindung wird das Trimmen auf B-Spline-Flächenstücken-Beschreibungen in einem Hardware-Graphikbeschleuniger durchgeführt. Er empfängt B-Spline-Beschreibung der Erzeugerfunktionen für die Stücke der ungetrimmten Stücke und B-Spline-Beschreibungen von Trimmkurven in dem uv-Parameterraum der Erzeugerfunktionen für die Stücke Die B-Spline-Beschreibungen der Trimmkurven sind selbst Funktionen eines Parameters t Der Graphikbeschleuniger berechnet eine ausreichend dichte Punkt-zu- Punkt-Darstellung jeder Trimkkurve in dem uv-Raum, zusätzlich zu Punkt-zu-Punkt-Darstellungen der einzelnen Unterbereiche im uv-Raum, deren zugeordnete Polygone in dem XYZ-Raum das Stück annähern. Der Graphikbeschleuniger bestimmt, wo gerade Linien, die sich Segmente der Tritnmkurven nähern, Unterbereichsgrenzen überschneiden und ändert die Scheitelpunkte der Unterbereiche, um Teile des zugeordneten Polygons wegzuschneiden. Er tut dies, indem eine Datenstruktur verbundener Listen von Scheitelpunkttabellen aufgebaut wird, die das ungetrimmte Polygon und Trimmkurven, die es schneiden, darstellen. Eine geeignete Durchquerung der Listen in der Datenstruktur erzeugt eine Liste getrimmter Polygon- Scheitelpunkte in Gerätekoordinaten. Die Liste kann dann weiter auf dem Pixel-Level von weiterer Hardware in dem Graphikbeschleuniger verarbeitet werden.
Beträchtliche Aufmerksamkeit wird dem Vermeiden des Unheils von Rundungsfehlern geschenkt. Ein Mechanismus zum Beschreiben, wo in einem Bereich eine Trimmkurve liegt, erlaubt es, daß der Trimmbetrieb diejenigen Trimmkurven aus der Betrachtung ausschließt, die das Polygon wahrscheinlich nicht beeinflußen können, das verarbeitet wird. Ein weiterer Mechanismus gleicht die Wirkungen einer nicht idealen Parametrisierung der Trimmkurven-Funktionen aus, um zu verhindern, daß eine unnötig große Anzahl von Polygon-Scheitelpunkten erzeugt wird. Das Trirnmverfahren ist auch mit rekursiver Unterteilung von Stücken kompatibel, um Stücke mit einer hohen Anzahl von Trimmkurven handzuhaben.
Erste und zweite Verfahren gemäß der Erfindung sind in den Ansprüchen 1 und 2 aufgeführt.

Kurzbeschreibung der Zeichnungen

Figur 1 ist eine Veranschaulichung einer Fläche in dem XYZ-Raum, die durch Stücke angenähert ist, die durch abbildende Bereiche eines zweidimensionalen uv-Parameterraums in den XYZ-Raum gebildet sind, mit parametrischen Erzeugerfunktionen für die Stücke, so wie nicht gleichförmigen, rationalen B-Splines.
Figur 2 zeigt, wie eine parametrische Funktion eines eindimensionalen t-Raums eine Trimmkurve in dem uv-Raum definieren kann, die wiederum in den XYZ-Raum abgebildet werden kann, um einen Bereich zu identifizieren, der bei der Fläche fehlt.
Figur 3 veranschaulicht eine parametrische Trimmkurvenfunktion, die über mehrere Bereiche des eindimensionalen t-Raumes segmentiert ist und eine Trimmkurve in dem zweidimensionalen uv-Raum definiert.
Figur 4 veranschaulicht, wie eine segmentierte Trimmkurvenfunktion mehrere Bereiche des uv-Raumes schneiden kann, um eine abgebildete Trimmkurve in einer entsprechenden Anzahl von Stücken im XYZ-Raum zu definieren.
Figur 5 veranschaulicht die segmentierte Trimmkurve der Figur 4 in größeren Einzelheiten.
Figur 6 zeigt, wie Bereiche in dem uv-Raum in Unterbereiche aufgeteilt werden, um flächennähernde Polygone für die Fläche in dem XYZ-Raum zu erzeugen, und gibt auch an, daß die Trimmkurve in dem uv-Raum die Unterbereiche schneidet, während die abgebildete Trimmkurve Polygone auf der Fläche abschneidet.
Figur 7 ist eine vergrößerte Ansicht eines Teiles der Figur 6, die das Vorliegen zusätzlicher Scheitelpunkte entlang von Grenzen der Stücke und entlang abgebildeter Trimmkurven für bessere Stück-zu-Stück-Übergänge veranschaulicht und das Vorliegen von Punkten entlang der abgebildeten Trimmkurve, die Schnittpunkte mit den Polygonkanten ebenso wie genäherte Punkte innerhalb von Innenbereichen von Polygonen, die von der abgebildeten Trimmkurve geschnitten werden, definiert.
Figur 8 ist eine Vergrößerung eines Teiles der Figur 7, die zeigt, wie die Formen der Polygone geändert werden, wenn sie von einer abgebildeten Trimmkurve geschnitten werden.
Figuren 9A - C umfassen einen vereinfachten Abschnitt eines Pseudocodes, der die Verarbeitungsschritte beschreibt, die verwendet werden, um Polygone zu erzeugen, welche von abgebildeten Trimmkurven geschnitten werden und deren Formen dementsprechend eingestellt worden sind, und sie umfassen eine Veranschaulichung der Struktur einer Polygon-Scheitelpunkttabelle, deren Einträge miteinander zu Listen verbunden sind, die Polygone beschreiben.
Figur 10 zeigt die Anordnung innerhalb eines Bereiches, in dem Unterbereiche gewählt werden, um die nähernden Polygone für die Fläche in dem XYZ-Raum zu erzeugen.
Figur 11 veranschaulicht einige Typen von Trimmkurven, die auf einem Bereich definiert sind, und gibt das Vorliegen eines Schutzbereiches um den Bereich an, um Unterstützung beim Vermeiden arithmetischer Rundungsfehler zu liefern.
Figuren 12A - B zeigen, wie ein Schneidemechanismus auf genäherten, geradlinigen Liniensegmenten von Trimmkurven arbeitet, die Unterbereiche schneiden, um Schnittpunkte zwischen den geradlinigen Liniensegmenten der Trimmkurve und den Grenzen des Unterbereiches zu erzeugen.
Figuren 13A - B beschreiben bestimmte Spezialfälle, in denen Trimmkurven Punkte im uv-Raum zeigen, die sehr nahe an den Grenzen des interessierenden Unterbereiches liegen.
Figur 14 veranschaulicht ein nützliches Beispiel eines Unterbereiches im uv-Raum, der von bestimmten speziellen Trimmkurven geschnitten wird und der als Grundlage einer Erläuterung dazu dient, wie die verbundene Grenzen-Liste von Schnittpunkt-Tabellen und ihre verbundene Trimmkurven-Unterliste durchquert werden, um Polygone zu erzeugen, die auf der Fläche vorliegen.
Figur 15 ist eine vereinfachte schematische Darstellung einer verbundenen Grenzen-Liste und von Trimmkurven-Unterlisten für die Scheitelpunkttabellen, die dem Beispiel der Figur 14 entsprechen.
Figur 16A - C umfassen ein vereinfachtes Ablaufdiagramm zum Verarbeiten der verbundenen Liste von Scheitelpunkttabellen gemäß dem Schritt 12 der Figur 9C.
Figur 17 ist ein vereinfachter Abschnitt eines Pseudocodes, der zu demselben Gegenstand wie die Figuren 16A - C gehört, jedoch mit weiteren Einzelheiten, die die Struktur der Scheitelpunkttabellen betrifft, welche in der Figur 9B und in der Figur 15 gezeigt sind.
Figur 18 ist ein Schaubild einer Trimmkurve in dem uv-Raum, die eine Verfeinerung bei der Auswahl von Punkten in dem uv-Raum veranschaulicht, die die Trimmkurve bei den Arbeitsschritten des Schneidens und Abschneidens darstellen.
Figur 19 ist ein vereinfachtes Hardware-Blockschaubild der Jnstrumentkomponenten, die bei einer Ausführungsform benutzt werden, die das bevorzugte Verfahren der Erfindung verkörpert.
Figuren 20A - C zeigen ein vereinfachtes Hardware-Blockschaubild des Graphikbeschleunigers der Figur 19.

Beschreibung eines bevorzugten Verfahrens

Wir werden beginnen, indem wir einen Weg betrachten, auf dem eine dreidimensionale Fläche innerhalb eines Graphiksystems dargestellt werden kann. Es sei beispielsweise angenommen, daß eine sattelförmige Fläche 1, so wie die, die in Figur 1 dargestellt ist, dargestellt werden soll. Dies würde erreicht werden, indem die gesamte Fläche 1 in kleinere Abschnitte unterteilt wird (die üblicherweise Stücke genannt werden), von denen das Stück 2 veranschaulicht wird. Um auf adäquate Weise eine Fläche zu liefern, die so kompliziert wie die Sattelform 1 ist, würden sehr viele Stücke erforderlich sein. Aus Gründen der Einfachheit beginnen wir, indem wir nur ein Stück 2 zeigen; es wird verstanden werden, daß das Graphiksystem irgendeine Einrichtung umfassen würde, um die Fläche in geeignete Stücke zu unterteilen. Auch sind die verschiede nen weiteren gekrümmten Linien in der Figur 1 nicht da, um andere Stücke anzudeuten (obwohl sie es könnten), sondern sind stattdessen als eine Hilfe beim Veranschaulichen der Form der Fläche 1 angeboten. Weiterhin wird es verstanden werden, daß, obwohl die Fläche 1 einem hyperbolischen Paraboloid ähnelt, das zu beschreibende Verfahren insbesondere auf unregelmäßige ("solche mit freier Form") Flächen anwendbar ist, insbesondere solchen, die aus parametrischen B-Spline-Beschreibungen erhalten werden.
Einem Stück zugeordnet ist ein Teil 5 eines Parameterraumes 3. Der Teil wird ein Bereich genannt. Um eine dreidimensionale Fläche im XYZ-Raum zu beschreiben, wird ein zweidimensionaler Parameterraum benutzt. Bei dem vorliegenden Beispiel sind die beiden Parameter u und v, und jeder kann sich zwischen zugeordneten maximalen und minimalen Werten ändern. Wie es in der Figur gezeigt ist, bildet eine Menge von parametrischen Stücke-Erzeugungsgleichungen 4 Werte in dem Parameterraum 3 in den XYZ-Raum ab, um (X, Y, Z)-Triplets zu erzeugen, die auf dem Stück 2 liegen.
Ein modernes Graphiksystem mit hoher Leistungsfähigkeit wird eine vollständige Beschreibung des Objektes speichern, unabhängig von irgendeiner bestimmten Ansicht, die gewünscht werden kann. Oftmals nimmt die Beschreibung die Form einer Datenbank an, insbesondere wenn Unterteilen des Objektes getrennt beschrieben werden und wird sich dann durch Bezugnahme entfalten, möglicherweise oftmals. Anstatt in der Datenbank eine umfangreiche Sammlung von Punkten auf der Fläche zu speichern, ist es üblich, stattdessen einen kompakteren Typ der Beschreibung zu benutzen, so wie nähernde Funktionen, die Werte zu einem bestimmten Grad der Auflösung geben. Wenn eine bestimmte Ansicht gewünscht wird, wird sie gefunden, indem Verschiebungen oder Drehungen von Punkten berechnet werden, die zunächst durch die Berechnung der nähernden Funktionen in der Datenbank gefunden werden.
B-Splines sind eine Technik zum Erreichen einer solchen kompakten Darstellung durch parametrische Funktionen.
Selbst eine einführende Erläuterung von B-Splines geht über das hinaus, was hierin aufgenommen werden kann, und der Leser wird auf die verschiedenen Referenzwerke über das Thema verwiesen "z.B.: Fundamentals of Interactive Computer Graphics, von J.D. Foley und A. Van Dam, Addison-Wesley, 984, und einen Artikel mit dem Titel Rational B-Splines for Curve and Surface Representation, IEEE Computer Graphics und Applications, Band 3, Nr. 6, September 1983). Glücklicherweise ist es hier nicht nötig, in Tiefe zu verstehen, was B-Splines sind und wie sie arbeiten. Verschiedene Software- Pakete existieren, um B-Spline-Beschreibungen von gewünschten festen Gegenständen und Oberflächen zu erzeugen. Der Punkt jedoch, auf den hier hingewiesen werden soll, ist, daß, obwohl das Verfahren der Erfindung sich selbst gut zur Verwendung mit B-Spline-Beschreibungen fester Gegenständen und Flächen eignet, die Verwendung von B-Splines in keiner Weise gefordert ist. Da jedoch das bevorzugte Verfahren mit einem Graphiksystem benutzt worden ist, das B-Splines benutzt, ist es höchst zweckmäßig, das Verfahren in diesem Kontext zu beschreiben. Das Graphiksystem ist das Hewlett- Packard 9000 Modell 320SRX, das insbesondere einen Graphikbeschleuniger des Typs HP Modell 98720A umfaßt.
Speziell erläutert Figur 1, daß jeder Punkt 6 auf einer interessierenden Fläche 1 durch einen entsprechenden Punkt 7 in einem Teil 5 eines Parameterraumes 3 dargestellt werden kann. Der Benutzer des Graphiksystems tritt in Wechselwirkung mit dem System auf definierte Weise, die in einem Betriebshandbuch für das System erläutert ist. Indem geeignete Befehle benutzt werden, kann eine gewünschte Fläche aufgebaut werden. Jm allgemeinen wird die Fläche aus einer Vielzahl von Stücken bestehen. Für jedes Stück auf einer Fläche in dem XYZ-Raum erzeugen die internen Aktivitäten des Graphiksystems drei (oder vielleicht vier) erzeugende Funktionen für die Stücke in u und v. Die Variablen u und v gehören zu dem Parameterraum 3. Die x-Koordinate des Punktes 6 wird gefunden, indem eine (polynome) Funktion Fx(u,v) berechnet wird. Entsprechende Funktionen Fy und Fz erzeugen die y- und die z-Koordinaten des Punktes 6. Ein allgemeinerer Fall (rationale B-Splines) für drei Koordinaten benutzt vier Funktionen:
x = Fx(u,v)/H(u,v)
y = Fy(u,v)/H(u,v)
z = Fz(u,v)/H(u,v).
In diesem Fall ist jede der Funktionen Fx, Fy und Fz durch Division durch die Funktion H rational gemacht worden. Das zu beschreibende Verfahren ist sowohl mit rationalen als auch mit nicht rationalen nicht gleichförmigen B-Spline-Darstellungen kompatibel.
Begrifflich könnte man alle Pixelwerte für die Fläche berechnen, indem man die erzeugenden B-Spline-Funktionen für die Stücke für ein ausreichend dichtes kartesisches Produkt der Variablen u und v berechnet; d.h. durch Berechnen einer ausreichend dichten Ansammlung von Punkten in dem Parameterraum 3. In der Praxis jedoch erfordert ein solcher Ansatz eine unmäßige Menge an Ausführungszeit, und er wird im allgemeinen zugunsten eines solchen vermieden, der nur schnellere und leichter durchzuführende Rechnungen erfordert. Das Polygonverfahren, das in Verbindung mit den Figuren 6 - 8 beschrieben werden soll, ist ein solcher günstiger Ansatz. Gemäß diesem Ansatz wird die Menge der Punkte, die in dem Parameterraum für ein gegebenes Stück berechnet wird, so ausgewählt, daß sie gerade dicht genug ist, um Polygon-Scheitelpunkte für Polygone zu liefern, die, wenn sie durch Schattieren interpoliert werden, eine akzeptabel glatte Fläche erzeugen. Da jedes Polygon eine Vielzahl von Pixeln enthält, deren Werte auf relativ einfache Weise durch lineare Interpolation, die hardwaremäßig durchgeführt werden kann, gefunden werden können, wird eine beträchtliche Reduktion bei der Erstellungszeit für das Bild erreicht.
Es ist unwahrscheinlich, daß ein Satz von Funktionen 4 vollständig eine komplette interessierende Oberfläche beschreibt. Stattdessen werden Sammlungen von B-Spline-Erzeugerfunktionen für Stücke gefunden, die gute Näherungen für die gewünschte Fläche über kleine Bereiche liefern. Diese stückweise Näherung teilt den Parameterraum in Abschnitte, die Bereiche genannt werden. Die stückweise Näherung ist es, die tatsächlich die Oberfläche in die entsprechenden Stücke teilt Um ein Stück zu erhalten, werden seine entsprechenden B-Spline-Funktionen über die Erstreckung des zugeordneten Bereiches berechnet. Entsprechend der gewünschten Auflösung für das anzuzeigende Objekt (d.h. die Polygongröße) wird eine geeignete Schrittgröße für Zuwächse in u und v gewählt. Der Parameter u darf in gleichen Schritten von umin bis umax laufen, während der Parameter v in gleichen Schritten (die nicht notwendigerweise dieselben sind, wie die für u) von vmin bis vmax läuft. Diese Berechnung des Bereiches erzeugt "rohe" Polygon-Scheitelpunkte, die im allgemeinen einer akzeptablen Größe weiterer Bearbeitung ausgesetzt werden, bevor sie angezeigt werden.
Somit sehen wir, daß die anzuzeigende Fläche als eine Ansammlung von Stücken beschrieben wird, von denen jedes einen zugeordneten Bereich hat. Zugeordnet zu jedem Bereich ist eine spezielle Sammlung von B-Spline-Erzeugerfunktionen für die Stücke.
Man rufe sich das ins Gedächtnis zurück, was oben dahingehend gesagt worden ist, daß durch Verwenden geeigneter Befehle der Benutzer eine gewünschte Fläche aufbauen kann. Es sei beispielsweise angenommen, daß eine ebene Platte mit einem Loch darin das gewünschte Objekt sein würde. Mit einem typischen Festmodellpaket würde ein Benutzer aus einem Menü eine geeignete erzeugende Form auswählen, so wie einen rechteckigen Festkörper, und seine Dimensionen festlegen. Er würde dann den Ort des Mittelpunktes des Loches festlegen und dann aus der Platte einen Zylinder des gewünschten Durchmessers "subtrahieren". Es ist eine praktische Angelegenheit, eine B-Spline-Darstellung einer rechteckigen Platte zu erzeugen. Es ist auch eine praktische Angelegenheit, eine B-Spline-Darstellung des Zylinders zu erhalten, der entfernt werden soll, indem das Loch "gebohrt" wird. Jedoch ist es keine praktische Angelegenheit, die Platte mit dem schon darin befindlichen Loch als eine erzeugende Form zu betrachten, die ihre eigene spezielle B-Spline-Beschreibung hat.
Das Verfahren der Erfindung bietet eine Lösung für das Problem komplexer Flächen, die eine praktische B-Spline-Beschreibung nicht haben. Gerade wie das Loch in der Platte eine Kante in dem XYZ-Raum hat, gibt es entsprechende Punkte in dem uv-Raum, die, wenn sie berechnet werden, exakt oder eng angenähert die Kante des Materials beschreiben wird, das entfernt werden soll, um das Loch zu erzeugen. Diese Punkte liegen entlang einer Kurve in dem uv-Raum, die eine Trimmkurve genannt wird. Die Trimmkurve kann durch eine oder mehrere Funktionen dargestellt werden. Diese Funktionen können durch das Festmodellpaket gefunden werden. Danach kann das Bereitstellen eines Stückes mit einem "subtrahierten" Teil durch eine qualifizierte Berechnung der Erzeugerfunktion für Stücke für den zugeordneten Bereich vollzogen werden. Die nähere Bestimmung erfordert das Bestimmen, während der Berechnung der erzeugenden Funktionen für die Stücke, ob das (u, v)-Paar, das behandelt wird, auf, innerhalb oder außerhalb der Trimmkurve liegt. Die nähere Bestimmung erzeugt eine Entscheidung darüber, ob das zugeordnete (X, Y, Z)-Tripel angezeigt wird oder nicht. Wenn das Tripel angezeigt werden soll, schreiten die Dinge fort, wie zuvor beschrieben. Wenn jedoch die Berechnung des (u, v)-Paares einen Polygon Scheitelpunkt erzeugen würde, das in dem zu subtrahierenden Bereich liegt, dann kann das Tripel nicht angezeigt werden, und die existierende Polygonstruktur muß modifiziert.
Figur 2 veranschaulicht die Verwendung einer Trimmkurve 8, um die Grenzen in dem XYZ-Raum eines Bereiches 9 zu beschreiben, der von dem Stück 2 subtrahiert werden soll. Die Trimmkurve 8 ist in einem Bereich 5 des Parameterraumes 3 definiert. Bei dem bevorzugten Verfahren kann die Trimmkurve 8 selbst durch B-Splines definiert sein. Ein Paar parametrischer Gleichungen 9 eines Parameters t kann eine zweidimensionale Trimmkurve in einem uv-Raum definieren. Nach der Art der Erzeugerfunktionen für die Stücke können die Trimmkurvenfunktionen 9 entweder rationale oder nicht rationale nicht gleichförmige B-Splines sein.
Ebenso wie eine Fläche aus Stücken und ihren zugeordneten Sammlungen unterschiedlicher Erzeugerfunktionen für die Stücke zusammengesetzt ist, muß eine Trimmkurve im allgemeinen stückweise aus Unterteilen zusammengesetzt werden, die Segmente genannt werden. Jedes Segment hat seine eigenen speziellen Trimmkurvenfunktionen 9.
Dieser Tatsachenverhalt ist in Figur 3 für die Trimmkurve 8 der Figur 2 veranschaulicht. Diese Trimmkurve ist in eine Anzahl von Segmenten S&sub1; bis S&sub6; aufgebrochen worden. Es sei angemerkt, daß jedes Segment seine eigenen Funktionen hat, die über entsprechende Bereiche des t-Raumes 10 definiert sind.
Figur 4 beschreibt eine Verallgemeinerung der Anwendung von Trimmkurven. Was gezeigt ist ist ähnlich der Situation, die in den Figuren 2 und 3 veranschaulicht ist, jedoch mit dem Unterschied, daß die Trimmkurve 11 nun verschiedene Bereiche 12 - 15 in dem uv-Raum durchquert. Diese Situation tritt auf, da, wie es der Zufall wollte, der Teil 9, der von der Fläche 1 subtrahiert werden soll, die vier entsprechenden Stücke 16 - 19 besetzt. Die Segmentgrenzen der Trimmkurve 11 sind auf der Kurve in Figur 4 gezeigt. Es sei angemerkt, daß im allgemeinen die Grenzen zwischen den Segmenten S&sub1; bis S&sub9; irgendwo entlang der Trimmkurve 11 fallen können. Insbesondere benötigen sie keine spezielle Beziehung zu den Grenzen zwischen den Bereichen 12 - 15.
Figur 5 veranschaulicht die stückweise Darstellung der segmentierten Trimmkurve 11 der Figur 4. Man bemerke die Verwendung der unterschiedlichen parametrischen Gleichungen für jedes Segment und daß jede Menge der Gleichungen über ihren eigenen zugeordneten Bereich in dem t-Raum 20 definiert ist.
Während der Diskussion der Figur 1 und der Erzeugerfunktionen für die Stücke wurde die Notation der Polygone kurz eingeführt. Beginnend nun mit der Figur 6 kehren wir zu diesem Thema zurück und untersuchen in weiteren Einzelheiten die Wirkungen des Abschneidens bei der Technik des Erstellens einer Fläche mit Polygonen.
Figur 6 zeigt vier Bereiche 12 - 15, die entsprechend der fetten Pfeile in die vier Stücke 16 - 19 abgebildet werden. Jeder dieser Bereiche wird von einer Trimmkurve 12 durchquert, deren Zweck es ist, den abgeschnittenen (oder "subtrahierten") Bereich 9 in der sich ergebenden Fläche zu definieren. Gegenwärtig besteht unser Interesse an der Figur 6 in der Erzeugung von (ungeschnittenen) Polygonen; die Einwirkungen der Trimmkurve 11 auf diese Polygone wird betrachtet werden, wobei mit den Figuren und dem Text begonnen wird, der der Figur 6 folgt.
Der Prozeß des Erzeugens der Stücke wird mit einem Stück zur Zeit durchgeführt. Demgemäß wird ein Bereich zur Zeit berechnet; jeder Bereich erzeugt ein zugeordnetes Stück. Die Berechnung eines Bereiches umfaßt die Bestimmung der Schrittgrößen für u und v. Diese Schrittgrößen sind nicht notwendigerweise für u und v dieselben, und jede wird wiederum beim Beginn der Berechnung des nächsten Bereiches festgelegt. Das heißt, die Schrittgrößen delta ui und delta vi für den Bereich 13 brauchen nicht einander gleich zu sein, noch brauchen sie irgendeine Beziehung zu den Schrittgrößen delta uj und delta vj für den Bereich 12 zu zeigen. Insbesondere gibt es keine Forderung dahingehend, daß delta ui gleich delta um oder gleich delta un ist, selbst wenn für die Einfachheit sie in der Figur gleich zu sein scheinen. Eine ähnliche Aussage gilt für die delta v's.
Der Benutzer des Graphiksystems wird wenigstens indirekte Kontrolle über die Schrittgrößen haben. Bei manchen Systemen kann es für den Benutzer möglich sein, sie direkt zu spezifizieren, obwohl es wahrscheinlicher ist, daß die Spezifizierung indirekt erhalten wird. Beispielsweise kann der Verwender das Graphiksystem instruieren, Schrittgrößen so zu wählen, daß die sich ergebenden Polygonkanten ungefähr eine bestimmte Anzahl von Pixel haben. Man sollte berücksichtigen, daß im allgemeinen die Schrittgrößen für jeden Bereich neu wiederbestimmt werden können.
Die Auswahl der Schrittgrößen für einen Bereich bestimmt eine Sammlung von (u, v)-Paaren innerhalb des Bereiches. Dies wird durch die gepunkteten Linien innerhalb der Bereich 12 - 15 dargestellt. Die Schnitte der gepunkteten Linien untereinander und der gepunkteten Linien mit den durchgezogenen Linien, die die Grenzen der Bereiche darstellen, sind die Punkte, an denen die Erzeugerfunktionen für die Stücke berechnet werden. Beispielsweise erzeugt die Berechnung der Erzeugerfunktionen für die Stücke an den Punkten 21 - 23 die Polygon-Scheitelpunkte 24 - 26.
Es sollen zwei weitere Dinge angemerkt werden, bevor Figur 6 verlassen wird. Als erstes sind die benachbarten Kanten der Polygone in den Stücken 16 - 19 gerade Liniensegmente. Es ist in der Figur ein Versuch gemacht worden, dies zu zeigen. Im Gegensatz dazu erscheinen die Grenzen und die Kante des abgeschnittenen Bereiches 9 viel glatter. Sie sind auch mit geraden Liniensegmenten geliefert worden, aber mit solchen, die bedeutend kürzer sind. Das heißt, es gibt mehr Punkte in dem uv-Raum, die berechnet worden sind, um diese Linien in den Stücken zu erzeugen. Im wesentlichen gibt es einen Mechanismus zum Einbringen von zusätzlichen Punkten in den Berechnungsprozeß für den Bereich. Diese Notation der differentiellen Dichte wird unter den Themen, die folgen, weiter diskutiert werden. Als zweites berechnet der oben beschriebene Prozeß des Berechnens von Erzeugerfunktionen der Stücke an Punkten in dem uv-Raum Punkte in allen Teilen des Bereiches, einschließlich in denen, die gegebenenfalls weggeschnitten werden. Wegschneiden ist ein recht komplizierter Prozeß, der die Analyse mehrerer möglicher Situationen erfordert. Beispielsweise kann ein gegebener Scheitelpunkt zu einem Polygon gehören, das durch das Wegschneiden vollständig unbeeinflußt bleibt, zu einem, das in seiner Gesamtheit weggeschnitten wird, oder zu einem, das von der Trimmkurve geschnitten wird. In diesem letzteren Fall verbleibt ein Teil des Polygons und ein Teil davon verbleibt nicht. Dies erfordert das Ändern der Form des Polygones, um es an die Trimmkurve anzupassen. Das wiederum erfordert das Auffinden neuer Scheitelpunkte für das Polygon; solche, die nicht bei der Berechnung des Bereiches an den Schritten in u und v erzeugt worden sind, wie es in Figur 6 gezeigt ist.
Man wende sich nun der Figur 7 zu. Was dort gezeigt ist, ist eine Vergrößerung eines Teiles der Figur 6. Insbesondere werden Teile der Stücke 16 und 17 veranschaulicht, zusammen mit einem Teil der abgebildeten Trimmkurve 37. Mit "abgebildeter" Trimmkurve meinen wir die Trimmkurve 11, wie sie durch die Erzeugerfunktionen für die Stücke in die Stücke abgebildet wird.
Zwei Arten von Polygon-Scheitelpunkten entlang der Grenzen von Stücken sind in Figur 7 gezeigt. Die offenen Kreise entsprechen der Abbildung in die Stücke a) der Schnittpunkte der gepunkteten Linien der Figur 6 mit den Grenzen des Bereiches und b) den Schnittpunkten der gepunkteten Linien mit sich selbst. Die geschlossenen Kreise entsprechen "zusätzlichen" Scheitelpunkten, die hinzugefügt werden, indem zusätzliche "u, v)-Paare entlang der Grenze des Bereiches berechnet werden. Diese zusätzlichen Punkte teilen jeden Schritt von delta u in gleiche Unterteile; die Schritte von delta v werden auf ähnliche Weise geteilt. Es ist üblich, daß der Benutzer zu einem gewissen Grad die Kontrolle über den Prozeß des Hinzufügens dieser zusätzlichen Scheitelpunkte hat.
Figur 7 zeigt auch Polygon-Scheitelpunkte entlang der abgebildeten Trimmkurve 27. Aus einer Untersuchung der Zeichnung wird es deutlich, daß sehr viele zusätzliche Scheitelpunkte zu den Polygonen als Teil des Trimmprozesses hinzugefügt worden sind. Wir werden über dieses viel zu sagen haben und wenden uns nun der Figur 8 zu, die eine weitere Vergrößerung des Teiles der abgebildeten Trimmkurve 27 ist, die zu dem Stück 17 gehört.
Es gibt im Grunde zwei Themen, die in Verbindung mit Figur 8 von Interesse sind. Das erste ist, woher die ausgefüllten schwarzen Quadrate kommen. Sie sind Punkte entlang der abgebildeten Trimmkurve 27, die als Polygon-Scheitelpunkte für Polygone genommen werden, die von der abgebildeten Trimmkurve 27 geschnitten werden. Man erinnert sich (siehe Figur 5), daß die Trimmkurve 11 aus Segmenten zusammengesetzt ist. Für die spezielle Trimmkurve 11 in Figur 5, die als Grundlage für unser Beispiel hier in Figur 8 dient, sind die Segmente S&sub6; bis S&sub8; diejenigen, die das Stück 17 abschneiden.
Die Segmente S&sub6; bis S&sub8; (ebenso wie alle anderen Segmente der oder irgendwelcher weiteren Trimmkurven) werden berechnet, indem für jedes Segment ein delta t aufgefunden wird, das auf ideale Weise Schritte in u und v erzeugt, die jede grob gleich der Entfernung in dem uv-Punkt zwischen den Punkten entlang der Grenze des Bereiches sind, der einem offenen Kreis und seinem nächsten schwarz ausgefüllten Kreis-Nachbar an Grenzen der Stücke der Figur 7 ist. Diese Arbeit des Auswählens der delta t's wird durch die Wahl des Benutzers beeinflußt, die in Verbindung mit zusätzlichen Scheitelpunkten für Grenzen der Stücke gemacht worden ist. Tatsächlich (und im Gegensatz zu dem idealen Fall) erzeugt die Berechnung der Trimmkurve 11, wie oben beschrieben, viele (u, v)-Paare, die zu nahe beieinanderliegen, um nützlich zu sein. Eine weitere Verfeinerung besteht darin, die Paare zu untersuchen, die durch die Berechnung der parametrischen Funktionen erzeugt worden sind (beispielsweise sind diese vorliegend Fu6 & Fv6, Fu7 & Fv7, Fu8 & Fv8) und Paare zu unterdrücken, die von ihren Vorgängern unzureichend weit entfernt sind. Die ausgefüllten schwarzen Quadrate der Figur 8 (und auch die der Figur 7) ergeben sich aus dem Berechnen der Erzeugerfunktionen für Stücke an diesen weiter ausgewählten (u, v)-Paaren.
Die zweite Sache, die in der Figur 8 von Interesse ist, sind die offenen Quadrate. Diese stellen den Schnittpunkt der abgebildeten Trimmkurve 27 und der Polygonkanten dar. Anstatt daß die Schnittpunkte in dem XYZ-Raum aufgefunden werden, wird der entsprechende Schnittpunkt in dem uv-Raum gefunden und dann in den XYZ-Raum abgebildet. Genauer ist, was aufgefunden wird, der Schnittpunkt von zwei geraden Liniensegmenten in dem uv-Raum. Eines der geraden Liniensegmente liegt zwischen zwei aufeinanderfolgenden weiter verbesserten (u, v)-Paaren entlang der Trimmkurve 11. Die anderen geraden Liniensegmente würden ein Teil (z.B. 28 oder 29 in Figur 6) der gepunkteten Linien oder Bereichsgrenzen der Figur 6 sein.
Bevor Figur 8 verlassen wird, sollte auch angemerkt werden, daß die gepunkteten Linien, die Polygonteile und gesamte Polygone darstellen, welche durch den Trimmprozeß so bestimmt sind, daß sie unsichtbar sind, somit auch nicht angezeigt werden.
Wir wenden uns nun der Figur 9 zu. Die Figur ist eine vereinfachte Pseudocode-Darstellung von Aktivitäten, die von einem Tranformations-Maschinenabschnitt eines Hardware-Gerätes des Graphiksystems mit hoher Leistungsfähigkeit durchgeführt wird. Das Hardwaregerät ist der Gegenstand der Beschreibung, die an einem späteren Abschnitt dieser Beschreibung und ihrer Figuren auftritt. Die oben genannte Aktivität ist hauptsächlich das Abschneiden von Polygonen, wie es in Figur 8 veranschaulicht ist. Figur 9 kann als eine zusammengefaßte Karte zum Erreichen des Typs des Abschneidens, der in Verbindung mit Figur 8 beschrieben ist, verstanden werden.
Bei einem bevorzugten Verfahren ist das Graphiksystem in der Lage, verschiedene B-Spline-Flächen anzuzeigen, von denen jede auf verschiedene Weise geschnitten sein kann. Jede Fläche würde im allgemeinen aus einer Anzahl von Stücken zusammengesetzt sein. Die Schneideaktivitäten treten auf dem Level des Polygon-Handhabens innerhalb jedes Stückes auf. Demgemäß wenden sich die Schritte 1 und 2 (im Zusammenhang mit den Schritten 15 und 16> der Figur 4 auf den Prozeß an, der im Zusammenhang mit den Schritten 3 - 14 beschrieben werden soll, auf jedes der Stücke in allen Flächen. Schritt 2 wird sof twaremäßig durch den Computer ausgeführt, der dem Graphiksystem zugeordnet ist. Unter anderem teilt der Schritt 2 die Fläche in Stücke, wählt ein zu behandelndes Stück aus, berechnet umin, umax, vmin und vmax für den zugeordneten Bereich und entscheidet, welche Segmente welcher Trimmkurven für das Schneiden des Stückes gebraucht werden. Die Schritte 3 - 14 erzeugen abgeschnittene Polygon-Scheitelpunkte&sub1; die durch einen Polygon-Bereitstellungsmechanismus in der Hardware des Graphiksystems angezeigt werden können.
Wir betrachten nun die Aktivität innerhalb des Bereiches der FOR-Schleife der Schritte 3 bis 14. Diejenige Aktivität umfaßt die erstmalige Erzeugung der verschiedenen Polygone (wie durch die Schritte 3 und 14 angegeben) und ihre nachfolgenden (und dazwischengeschalteten) Schneideschnitte (wie durch die Schritte 4 bis 13 angegeben> .
Die allgemeine Reihenfolge der Polygonerzeugung innerhalb eines Stückes ist durch den Beispielbereich 30 der Figur 10 veranschaulicht. Derjenige Bereich ist in diesem Beispiel in sechzehn Unterbereiche aufgeteilt, einen für jedes ungetrimmte Polygon, das erzeugt werden soll. Die Größe jedes Unterbereiches wird gemäß der Benutzerinstruktionen bestimmt, die zu der gewünschten sichtbaren Glätte der Fläche gehört. Bei einem bevorzugten Verfahren werden die Polygone durch eine Technik erzeugt, die Vorwärts-Differenzierung genannt wird, die nicht die explizite Berechnung der u- und v-Werte für die Grenzen jedes der Unterbereiche erfordert. Vorwärts-Differenzieren ist bevorzugt, da es schneller ist als das Berechnen der Erzeugerfunktionen für die Stücke an jeder der Ecken der Unterbereiche. Für eine Beschreibung des Vorwärts-Differenzierens siehe Foley und Van Dam, Seiten 535-536.
Die Abschneideaktivitäten, die folgen sollen, erfordern die Verwendung von Schneidegrenzen, die dem Unterbereich für das Polygon entsprechen, das erzeugt werden soll. Wie üblich bezieht sich der Ausdruck "Schneidegrenzen" auf ein interessierendes Fenster. Gegenstände innerhalb des Fensters werden beibehalten, während solche, die außerhalb fallen, entfernt werden. Die Schneidegrenzen, die für das hierin beschriebene Abschneiden von Interesse sein werden, sind die Unterbereichsgrenzen in dem uv-Raum, die den erzeugten Polygonen zugeordnet sind.
Unglücklicherweise, wie es oben angemerkt ist, sieht die Arbeitsweise des Berechnens von Polygon-Scheitelpunkten im XYZ-Raum durch Vorwärts-Differenzieren nicht explizit die uund v-Werte vor, die die Unterbereichsgrenzen sind. Wenn die Schneidegrenzen benutzt werden sollen, die oben erwähnt sind, müssen sie dann getrennt gefunden werden. Schritt 4 berechnet die Schneidegrenzen (im uv-Raum) für das Polygon, das gegenwärtig erzeugt und beschnitten wird. Figur 9A umfaßt einen Unterbereich 35 mit Schneidegrenzen ulinks, urechts, voben und vunten. Der Unterbereich 35 könnte beispielsweise dem Unterbereich N6 in Figur 10 entsprechen: ulinks würde der Wert 31 sein, urechts würde der Wert 32 sein, voben würde der Wert 34 sein und vunten würde der Wert 33 sein.
Mit Bezug auf Figur 10 sei angemerkt, daß das Auffinden der Schneidegrenzen für die verschiedenen Unterbereiche das Bestimmen der u-Werte 31, 32, ... und der v-Werte 33, 34 ... erfordert, die die u- und v-Achse teilen. Bei einer bevorzugten Ausführungsform sind diese Fließpunkt-Binärzahlen mit 32 Bit. Man kann sich eine Prozedur zum unabhängigen Auffinden der vier Ecken irgendeines ausgewählten Unterbereiches vorstellen. Eine jegliche solche Prozedur sollte vermieden werden, wenn nicht absolut sichergestellt werden kann, daß dasselbe (u, v)-Paar (d.h. ihre Bitmuster sind identisch) immer für eine gemeinsame Ecke erhalten wird (d.h. es beschreiben der u-Wert 31 und der v-Wert 33 eine gemeinsame Ecke für die Unterbereiche Al, A2, AS und A6 in Figur 10), ungeachtet dessen, welcher Unterbereich gegenwärtig von Interesse ist. Anstatt daß man derartige Garantien für unabhängig ausgewählte Unterbereiche gibt, erlaubt es ein bevorzugtes Verfahren, das als nächstes beschrieben wird, daß die Polygone zu unterschiedlichen Zeiten erzeugt werden, wobei sichergestellt wird, indem bestimmte Hauptwerte, die interessieren, gerettet werden, daß gemeinsame Ecken identische u-Werte und Identische v-Werte haben.
Wie es in Figur 10 gezeigt ist, ist die Reihenfolge der Polygonerzeugung innerhalb von Zeilen von links nach rechts und dann zeilenweise von oben nach unten. Schrittgrößenwerte (delta u und delta v) werden gefunden, wie es zuvor beschrieben ist. Während eine Reihe durchquert wird (z.B. vom Unterbereich A2 zum Unterbereich A3), wird urechts des Unterbereichs A2 gerettet und als ulinks des Unterbereiches A3 wiederverwendet. Am Beginn einer Zeile wird umin für den Bereich (exakt) als ulinks genommen. Entlang einer Zeile wird ein neues urechts gefunden, indem delta u zu dem alten Wert von urechts hinzuaddiert wird. Am Ende der Zeile wird umax für den Bereich (exakt) als urechts genommen. Die Werte umin und umax treten auf, wenn die B-Spline-Erzeugersoftware eine Fläche in Stücke segmentiert (siehe Figur 1)
Am Anfang der ersten Zeile wird vmin (exakt) als vunten genommen. Der Wert für voben wird gefunden, indem delta v zu vunten addiert wird. Danach, am Beginn einer neuen Zeile, wird der alte Wert von voben gerettet und als das neue vunten wiederverwendet. Das neue voben wird gefunden, indem delta v zu dem alten Wert von voben addiert wird. Wenn die allerunterste Zeile des Unterbereichs bearbeitet wird, wird vmax (exakt) als voben genommen.
Schritt 5 (in Verbindung mit Schritt 10) der Figur 9A kann besser mit Bezug auf die Figur 11 verstanden werden. Diese Figur zeigt einen Bereich 36, der von einer Vielzahl zugeordneter Trimmkurven 37 - 40 geschnitten wird. Man erinnere sich, daß Trimmkurven im allgemeinen als segmentierte B-Splines definiert sind. Wenn betrachtet wird, welche Maßnahmen beim Beschneiden eines bestimmten Stückes vorzunehmen sind, brauchen nur diejenigen Trimmkurvensegmente, die innerhalb des zugeordneten Bereiches liegen, betrachtet zu werden. Entsprechend dem, was in Verbindung mit Schritt 2 der Figur 9 gesagt worden ist, wird ein Mechanismus in der Software des Grafiksystems eine oder mehrere Listen von Trimmkurvensegmenten jedem Bereich zuordnen. Wenn beispielsweise das Stück für den Bereich 36 der Figur 11 geliefert werden sollen, dann würden vier Listen von Trimmkurvensegmenten "d.h. ihre B-Spline-Beschreibungen), die bestimmten Erzeugerfunktionen für das Stück, die Bereichsdef inition ebenso wie einige andere Information zu dem Mechanismus übertragen werden, der die Schritte 3 - 14 der Figur 9 ausführt. Von den vier Listen der Trimmkurven in unserem Beispiel werden die beiden, die den Trimmkurven 37 und 38 zugeordnet sind, markiert werden, da sie "geschlossene" Trimmkurven beschreiben, während die beiden Listen für die Trimmkurven 39 und 40 als "offen" markiert werden. Damit meinen wir, daß die Listen für die Trimmkurven 37 und 38 abgeschlossene Kurven beschreiben, die auf sich selbst schließen. Jedoch können Teile der Trimmkurven 39 und 40 ausgesondert werden, da sie keine Wirkung auf das Beschneiden des Stückes haben, das erzeugt wird, indem der Bereich 36 geliefert wird. (Die ausgesonderten Teile können jedoch benötigt werden, wenn ein anderes Stück wiedergegeben wird, und werden in Listen auftauchen, die den Bereich für das andere Stück begleiten.) Offene Trimmkurven müssen außerhalb ihres zugeordneten Bereiches beginnen und enden. Bei einem bevorzugten Verfahren wird die Zahl der Trimmkurvensegmente, die in eine Liste für eine offene Trimmkurve eingeschlossen werden sollen, erhöht, um Anfangs- und Endsegmente zu umfassen, die "deutlich" innerhalb des Bereiches oder "deutlich" außerhalb des Bereiches liegen, außerhalb jeglichen möglichen Zweifels oder Fehlers, der durch Rundungsfehler eingeführt werden könnte. Dies kann beispielsweise erreicht werden, indem man den Bereich als etwa fünf Prozent größer betrachtet, als er wirklich ist, wie es durch die gepunktete Linie 41 gezeigt ist.
Wir wenden uns nun dem Schritt 6 der Figur 9 zu, der (in Verbindung mit Schritt 9) die Notation der geraden Liniensegmente entlang einer Trimmkurve betrifft. Die Aufgabe des Beschneidens wird das Auffinden vieler Punkte entlang jeder Trimmkurve umfassen. Man rufe sich beispielsweise Figur 8 zurück; alle offenen und ausgefüllten Quadrate entlang der abgebildeten Trimmkurve 27 müssen gefunden werden (lokal, wo sie liegen), als ein Teil des Beschneideprozesses. Insbesondere entsprechen die "geraden Liniensegmente" des Schrittes 6 der Figur 9 den geraden Linien zwischen den geschlossenen Quadraten der Figur 8. Implizit im Schritt 6 enthalten ist das Auffinden von (u, v)-Paaren, die, wenn sie von den Erzeugerfunktionen 4 für das Stück berechnet werden, die geschlossenen Quadrate erzeugen werden. Es ist das Auffinden dieser (u, v)-Paare, das im Moment interessiert.
Man wird sich erinnern, daß die abgebildete Trimmkurve 27 der Figur 8 den Segmenten S&sub6; bis S&sub8; der Trimmkurve entspricht, die in Figur 5 gezeigt ist. Man erinnere sich auch, daß dieselbe Trimmkurve in dem uv-Raum in Figur 6 gezeigt ist. Die (u,v)-Paare, die wir gegenwärtig suchen, gehören zu demselben uv-Raum, wie er in Figur 6 gezeigt ist. Wir benutzten Figur 6 zuletzt in Verbindung mit einer Diskussion, wie Polygone entstehen; hier wird eine ähnliche Arbeitsweise eine separate Sammlung von (u, v) -Paaren erzeugen, um die Näherung durch gerade Liniensegmente jedes B-Spline-Segmentes jeder Trimmkurve zu konstruieren.
Was gewünscht wird, sind (u, v)-Paare entlang der Trimmkurve mit ungefähr demselben Abstand zwischen sich, wie die zusätzlichen Scheitelpunkte, die für die Polygonerzeugung zu den Bereichsgrenzen hinzugefügt worden sind. Das heißt, die Schritte in u entlang der Trimmkurve sollten nicht größer sein als die Entfernung in u zwischen den zusätzlichen Scheitelpunkten. Wenn es keine zusätzlichen Scheitelpunkte gibt, dann sollten die maximalen Entfernungen als die Entfernung zwischen den Eck-Scheitelpunkten genommen werden.
Eine ähnliche Forderung wird auf Schritte in v entlang der Trimmkurve angewendet. Diese Sammlung von (u, v)-Paaren ist eine getrennte Sammlung von Punkten, die voneinander unterschiedlich sind, das heißt, denen, die für die Polygonerzeugung benutzt werden. Die Schritte entlang der Trimmkurve werden den geschlossenen Quadraten der Figur 8 entsprechen. Sie werden benutzt werden, um zusätzliche (u, v) -Paare zu bestimmen, die den offenen Quadraten der Figur 8 entsprechen. Wir beschreiben nun, wie die anfänglichen Schritte entlang der Trimmkurve gefunden werden.
Man erinnere sich, daß die Trimmkurven durch parametrische Gleichungen beschrieben werden, die t als ihre unabhängige Variable haben. Wenn man weiß, welche Schrittgrößen für u und v gewünscht werden, impliziert die nicht unmittelbar eine Schrittgröße in t zum tatsächlichen Berechnen der Trimmkurvenfunktionen. Weiterhin würde es wünschenswert sein, wenn die Technik der Vorwärts-Differenzen benutzt werden könnte, um die Trimmkurvenfunktionen zu berechnen, so wie es für die Berechnungsfunktionen der Stücke beschrieben worden ist. Das erfordert eine gleichförmige Schrittgröße in t. Was somit gebraucht wird, ist eine Schrittgröße in t, die während der Berechnung des Trimmkurvensegmentes unverändert bleibt und die eine ausreichend dichte Sammlung von (u, v)-Paaren für die Verwendung als die ausgefüllten Quadrate der Figur 8 erzeugt.
Die grundlegende Idee ist es, jedes Segment jeder Trimmkurve an einigen ausgewählten (und handhabbar kleinen) Anzahl von Punkten zu berechnen. Das größte der sich ergebenden Inkremente in u und das größte der sich ergebende Inkremente in v werden jeweils gespeichert. Diese Inkremente werden mit den entsprechenden Entfernungen in u und v zwischen den zusätzlichen Scheitelpunkten entlang der Stückgrenzen verglichen. Wenn der Vergleich günstig ist, ist die gewünschte Schrittgröße in t gefunden. Wenn der Vergleich ungünstig ist, dann wird die Schrittgröße in t gemäß dem Verhältnis der größten sich ergebenden Schrittgröße und der gewünschten Schrittgröße eingestellt. Dieser Bestimmungsprozeß wird für u und v separat durchgeführt, was zu zwei Kandidaten für eine Schrittgröße in t führt. Die kleinere der beiden Schrittgrößen wird gewählt.
Schritt 7 in Figur 9 kann mit Bezug auf Figur 12 und einer Würdigung des Schneidealgorithmus von Cohen & Sutherland verstanden werden. (Bezüglich einer Beschreibung dieses Algorithmus siehe Seiten 146 - 149 in Foley und Van Dam). Figur 12A zeigt ein gerades Liniensegment 42 (mit einer Richtung, die von P&sub1; bis P läuft), das ein interessierendes Schneidefenster 43 überkreuzt. Der Zweck, eine gleichförmige Schrittweite in t aufzufinden und das Vorwärts-Differenzieren zu benutzen, um die Trimmkurvenfunktion zu berechnen (in der Richtung zunehmender Werte von t) ist es, eine ausreichende Anzahl von Punkten entlang der Trimmkurve zu finden. Diese Punkte sind die ausgefüllten Quadrate der Zeichnungen, und die gerichteten geraden Liniensegmente zwischen ihnen sind eine enge Näherung der idealen Trimmkurve, die durch die B-Spline-Funktionen beschrieben wird. Das Abschneiden findet die Schnittpunkte (wenn es welche gibt) zwischen jedem geraden Liniensegment 42 und dem Schneidefenster 43. Dies ermöglicht die Bestimmung dessen, genau welcher Teil 44 des geraden Liniensegmentes 42 innerhalb des Schneidefensters 43 liegt. In dem Beispiel der Figur 12A ist der Teil 44 die Linie zwischen P&sub1; NEU und P NEU. P&sub1; NEU und P NEU werden durch den Schneideprozeß berechnet. Die Indizes geben an, daß das Liniensegment 44 eine Richtung hat. Wie es deutlich werden wird, benutzt das zu beschreibende Trimmverfahren die Notation der direkten Bewegung entlang der Trimmkurven. Einfach ausgedrückt, wenn man sich entlang der Trimmkurve (oder ihrer geradlinigen Näherung) bewegt, wird alles, was rechts davon liegt, weggeschnitten.
Der Schneidealgorithmus von Cohen & Sutherland, der oben erwähnt ist, wird im Zusammenhang mit einer Vielzahl von Verbesserungen benutzt. Mit Bezug nun auf Figur 12 und auf die Art, die der Schneidealgorithmus von Cohen & Sutherland auf den Seiten 146 - 149 in Foley und Van Dam beschrieben wird, umfaßt das bevorzugte Verfahren die folgenden Verbesserungen:
1. Die Schneidgrenzen werden in der Reihenfolge ulinks, urechts, vunten, voben überprüft, da dies die Reihenfolge ist, in der die Polygone erzeugt werden (d.h. von links nach rechts innerhalb einer Zeile und zeilenweise von unten nach oben).
2. Abhängig von der relativen Position des Schneidefensters des geraden Liniensegmentes, wird entweder P&sub1; NEU oder P NEU oder beide berechnet. (Figur 12 zeigt nur zwei von vielen möglichen Situationen.) Die Berechnung eines solchen Schnittpunktes in irgendeinem Stadium des Schneidealgorithmus wird immer relativ zu dem ursprünglichen P&sub1; ausgeführt, um zu gewährleisten, daß identische Schnittpunkte für benachbarte Schneidefenster berechnet werden, wie es in Figur 12B gezeigt ist. Wenn das Fenster&sub1; und das gerade Liniensegment von P&sub1; nach P betrachtet werden, wird der Schnittpunkt, der im Fenster&sub1; mit P NEU markiert ist, berechnet werden. Wenn dasselbe gerade Liniensegment für Fenster betrachtet wird, wird der Schnittpunkt, der in Fenster mit P&sub1; NEU bezeichnet ist, berechnet werden. Die numerischen Werte, die für P&sub1; NEU berechnet werden, müssen mit den numerischen Werten, die für P NEU berechnet werden, identisch sein. Die Gleichungen
V NEU = v&sub1; + ((urechts - u&sub1;)/(u - u&sub1;)) (v - v&sub1;)
V&sub1; NEU = v&sub1; + ((ulinks - u&sub1;)/(u - u&sub1;)) (v - v&sub1;)
wobei:
u&sub1; und v&sub1; die Koordinaten von P&sub1; sind,
u und v die Koordinaten von P sind, geben die Werte der v-Koordinate des Schnittpunktes für die beiden Fenster. Die u-Koordinate ist urechts für Fenster&sub1; und ulinks für Fenster.
3. Nach dem Abschneiden gegenüber der linken, rechten&sub1; unteren und oberen Grenze ist es möglich (wegen der Fließpunkt-Rundungsfehler), daß eine der Koordinaten, entweder P&sub1; NEU oder P NEU, leicht außerhalb des Schneidefensters liegt. Dies wird korrigiert, indem die außerhalb liegende Koordinate von P&sub1; NEU (und/oder P NEU) nach dem Schneiden zur Schneidegrenze bewegt wird. Diese Überprüfung wird für alle vier Schneidegrenzen durchgeführt. "Rundungsfehler können ebenfalls auf einfache Weise eine Koordinate der Endpunkte in das Innere des Schneidefensters bewegen. Dieser Fall macht später bei den Trimmvorgängen keine Probleme und kann außer Acht gelassen werden.)
4. Wenn die Trimmkurven als B-Splines dargestellt werden, wird es typischerweise der Fall sein, daß das (u, v)-Paar, das erhalten wird, wenn ein gegebenes Segment am Ende seines Bereiches berechnet wird (d.h. für den größten Wert von t in dem Bereich), so daß dieses nicht genau gleich dem (u, v)-Paar ist, das erhalten wird, wenn das nächste Segment an dem Beginn seines Bereiches berechnet wird (d.h. für den kleinsten Wert von t in dem anderen Bereich). Dies kann das Ergebnis von Fließpunkt-Rundungsfehlern sein oder kann daran liegen, daß die B-Spline-Näherungen nicht exakt an ihren "Verbindungen" zwischen den Segmenten konvergieren. Dieses Problem wird vermieden, indem der erste Punkt des späteren Segmentes anstelle des letzten Punktes des früheren Segmentes benutzt wird. Somit läuft das letzte gerade Liniensegment der geraden Liniensegment-Näherung für ein gegebenes Trimmkurvensegment von dem nächsten zum letzten Punkt des Segmentes zum ersten Punkt des nächsten Segmentes.
5. Typischerweise wird P eines gegebenen geraden Liniensegmentes P&sub1; des nächsten geraden Liniensegmentes. Wenn dies auftritt, kann der alte Wert von P in P&sub1; kopiert werden. Dann kann der Schneidmechanismus Information über die Position von P relativ zu dem Schneidefenster speichern und es vermeiden, diese Information neu zu berechnen.
6. Der Schneidemechanismus setzt drei Merker (die später benutzt werden):
ACCEPT:= WAHR, wenn das gerade Liniensegment von P&sub1; nach P teilweise oder vollständig innerhalb des Schneidefensters liegt;
CNEUP&sub1;:= WAHR, wenn ein neues P&sub1; berechnet worden war "d.h. P&sub1; lag außerhalb des Schneidefensters); und
CNEUP:= WAHR, wenn ein neues P berechnet worden war (d.h. P lag außerhalb des Schneidefensters).
7. Wenn der ACCEPT-Merker WAHR ist, aktualisiert der Schneidemechanismus P&sub1; NEU und P NEU. Wenn P&sub1; auf oder innerhalb des Schneidefensters liegt, dann wird P&sub1; NEU = P&sub1;. P wird ähnlich behandelt.
Es wird nun auf Schritt 8 der Figur 9 Bezug genommen. Nachdem jedes gerade Liniensegment gegen das gegenwärtig gültige Schneidefenster geschnitten worden ist, wird Information über die Punkte P&sub1; NEU und P NEU in einer Liste von Tabellen gespeichert, wenn der ACCEPT-Merker WAHR ist. Im allgemeinen kann eine Trimmkurve viele Punkte innerhalb des gegenwärtig gültigen Schneidefensters haben. (Figur 8 ist hier hilfreich; sie zeigt Polygon-Scheitelpunkte entlang der abgebildeten Trimmkurve 27. In jedem Unterbereich gab der Schneideprozeß eine Vielzahl von Punkten für die Trimmkurve wieder.) Eine Trimmkurve kann in ein Schneidefenster eintreten und in ihm über viele Punkte weiterlaufen, bevor sie austritt. Sie kann austreten und dann wieder eintreten. Sie kann sogar einfach (bei t = 0) an irgendeiner Stelle in der Mitte des Schneide fensters beginnen. Eine Trimmkurve kann ein Schneidefenster an genau einer Ecke des Fensters schneiden. In Ausdrücken von Tabellen, die dann zu der Liste hinzugefügt werden, kann eine gegebene Trimmkurve eine oder mehrere Tabellen erzeugen, die zu der Liste hinzugefügt werden sollen. Da Trimmkurven eine Richtung haben, die ihnen zugeordnet ist (zunehmende Werte von t), ist es zweckmäßig, zwischen: a) Schnittpunkten entlang der Grenze eines Schneidefensters, wo eine Trimmkurve in das Fenster eintritt; b) Punkte entlang einer Trimmkurve, die innerhalb des Schneidefensters liegen; und c) Schnittpunkte entlang der Grenze eines Schneidefensters, wo eine Trimmkurve das Fenster verläßt, zu unterscheiden. Diese Punkte werden "ANFANGS-", "MITTEL-" bzw. "END-"Punkte genannt werden. Im allgemeinen kann ein Schneidefenster von mehreren Trimmkurven geschnitten werden. Es ist wünschenswert, die Tabellen für jede einzelne Trimmkurve in getrennte kreisförmig verbundene Unterlisten innerhalb der größeren Liste der gesamten Tabellen, die für ein bestimmtes Schneidefenster erzeugt werden, zu gruppieren.
Das allgemeine Format der Tabellen ist in Figur 9 gezeigt. Die ersten beiden Einträge 45 und 46 in einer Tabelle sind die binären Fließpunktwerte der u- und v-Koordinaten für den interessierenden Punkt (entweder P&sub1; NEU oder P NEU). Der dritte Eintrag 47 enthält drei Teile: entweder Null oder eine von Null verschiedene Trimmkurvenzahl (eine ganze Zahl mit acht Bit); entweder Null oder eine von Null verschiedene B-Spline-Segmentzahl (auch eine ganze Zahl mit acht Bit), die die Trimmkurve identifiziert, auf der der Punkt in dem uv-Raum liegt; und sechs Merker-Felder. (Nullen in den ersten beiden Teilen geben spezielle Fälle an, die später in einer genaueren Beschreibung einer bevorzugten Implementierung beschrieben werden.) Die sechs Merker-Felder sind:
FF1 Ein Zwei-Bit-Feld, das angibt, ob diese Tabelle für einen "ANFANGS-", "MITTEL-", "END-" oder "ANDEREN" Punkt ist. "ANDERE" Punkte umfassen Ecken und zusätzliche Scheitelpunkte, wie es unten beschrieben werden wird.
FF2 Ein Zwei-Bit-Feld, das angibt, auf welcher Kante des Schneidefensters (d.h. der linken, rechten, unteren oder oberen) der Punkt liegt. Dieses Feld wird hauptsächlich für Tabellen benutzt, die Ecken und zusätzliche Scheitelpunkte beschreiben.
FF3 Ein Ein-Bit-Feld, das angibt, ob diese Tabelle übersprungen werden sollte. Dieses Bit wird gesetzt werden, wenn diese Tabelle einen der speziellen Fälle darstellt, die in Verbindung mit Schritt 11 der Figur 9 beschrieben werden sollen. Dieser Merker wird der SKIP-Merker genannt.
FF4 Ein Ein-Bit-Feld, das in dem Schritt 12 der Figur 9 benutzt werden wird, um anzugeben, daß diese Tabelle bereits behandelt worden ist. Dieser Merker wird der MARK-Merker genannt und ist anfangs FALSCH.
FFS Ein Ein-Bit-Feld, das im Schritt 12 der Figur 9 benutzt werden wird, um anzugeben, daß diese Tabelle die erste Tabelle ist, die behandelt werden soll. Dieser Merker wird der START-Merker genannt und ist anfangs FALSCH.
FF6 Ein Ein-Bit-Feld, das in Schritt 11 der Figur 9 bestimmt werden wird und das angibt, ob der Scheitelpunkt in dem XYZ-Raum, der dieser Tabelle entspricht, "AUF" der Oberfläche vorliegen bleibt (er ist nicht weggeschnitten worden) oder auf ihr fehlt oder "WEG" von der Fläche ist (er ist weggeschnitten worden). Dieser Merker wird der AUF-Merker genannt.
(AUF der Oberfläche vorliegen bleibend bedeutet NICHT, daß der Scheitelpunkt tatsächlich sichtbar sein wird. Entfernen verdeckter Flächen, rückwärts gerichtetes Auslegen und Schneideoperationen können verhindern, daß ein Punkt, der AUF der Oberfläche vorliegt( schließlich angezeigt wird. Andererseits ist ein Punkt, der WEG von der Fläche ist, NIEMALS sichtbar.)
Wir werden viele zukünftige Gelegenheiten haben, um auf das Vorliegen oder Fehlen eines Scheitelpunktes Bezug zu nehmen, oder darauf, ob es AUF der Fläche oder WEG von ihr liegt. In derselben Weise wird es zweckmäßig sein, sich auf Polygone und ganze Stücke als entweder vorliegend oder fehlend, AUF oder WEG, zu beziehen. Polygone und Stücke haben nicht einzelne eigene AUF-Merker; ihr Vorliegen oder Fehlen wird durch das Vorliegen oder Fehlen bestimmter Scheitelpunkte in ihnen bestimmt werden. Die AUF-Merker jener wichtigen Scheitelpunkte werden gespeichert, wenn man ihnen begegnet.
Der vierte Eintrag 48 enthält die Hülladresse und die nächste Adresse. Von Null verschiedene Hülladressen sind die kreisförmigen Verbindungen in einer ansonsten linearen (d.h. räumlich geordneten) Liste von Tabellen. Eine Hülladresse Null gibt an, daß die nächste räumliche Tabelle auch die nächste logische Tabelle in der Liste ist. Tabellen werden an das Ende der Liste von Tabellen in einer geordneten Weise eingefügt, wenn Trimmkurven in der Richtung zunehmender Werte von t durchquert werden. Um die gewünschte kreisförmig verbundene Unterliste für eine Trimmkurve zu bilden, ist es bloß notwendig, die Adresse der ersten Tabelle für die Trimmkurve in die Hülladresse der letzten Tabelle für die Trimmkurve einzufügen.
Die nächste Adresse ist durch die Schritte 11 und 12 in Figur 9 bestimmt. Sie verbindet die Tabellen in einer weiteren Liste, die verwendet wird, um Teile von Polygonen anzuzeigen, die vorliegen.
Als ein Teil der Diskussion des Schrittes 8 der Figur 9 ist es zweckmäßig, die Kriterien zu beschreiben, die benutzt werden, um die Liste von Tabellen abhängig von Information, die von dem Schneidemechanismus zur Verfügung gestellt wird, aufzubauen. Im allgemeinen, abhängig von der Position der Zeile von P&sub1; zu P relativ zu dem Schneidefenster, wird es notwendig sein, null, eine oder zwei Tabellen zu der Liste hinzuzufügen. Die folgenden Entscheidungstabellen beschreiben, wie dieses gemacht wird. In diesen Entscheidungstabellen wird der Merker INNERHALB verwendet, um daran zu erinnern, ob P innerhalb oder außerhalb des Schneidefensters liegt. ENTSCHEIDUNGSTABELLE FÜR DAS ERSTE (P&sub1;, P)-PAARE ENTLANG JEDER TRIMMKURVE Falls ACCEPT = FALSCH, dann INNERHALB: = FALSCH Falls ACCEPT = WAHR, dann Wenn die gegenwärtig gültige Trimmkurve eine offene Schleife ist, dann füge zu der Liste eine ANFANGS-Tabelle für P&sub1; NEU hinzu, sonst tue nichts. Wenn P der letzte Punkt auf einer offenen Schleifen-Trimmkurve ist, dann füge zu der Liste END-Tabelle für P NEU hinzu, sonst füge eine MITTEL-Tabelle für P NEU hinzu. INNERHALB: WAHR. Wenn die gegenwärtig gültige Trimmkurve eine offene Schleife ist, dann füge zu der Liste eine ANFANGS-Tabelle für P&sub1; NEU hinzu, sonst tue nichts. Füge zu der Liste eine END-Tabelle für P NEU hinzu. INNERHALB := FALSCH Füge zu der Liste eine ANFANGS-Tabelle für P NEU hinzu. Füge zu der Liste eine MITTEL-Tabelle für P NEU hinzu. INNERHALB : = WAHR W W Wenn P&sub1; NEU < > P NEU, dann füge zu der Liste eine ANFANGS-Tabelle für P&sub1; NEU und eine END-Tabelle für P NEU hinzu, sonst tue nichts. INNERHALB := FALSCH ENTSCHEIDUNGSTABELLE FÜR DIE VERBLEIBENDEN (P&sub1;, P)-PAARE JEDER TRIMMKURVE Falls INNERHALB = WAHR dann Wenn P der letzte Punkt auf einer Trimmkurve mit offener Schleife ist, dann füge zu der Liste eine END- Tabelle für P NEU hinzu, sonst füge eine MITTEL-Tabelle für P NEU hinzu. Füge zu der Liste eine END-Tabelle für P NEU hinzu. INNERHALB := FALSCH kann nicht auftreten.
Falls INNERHALB = FALSCH, dann
Falls ACCEPT = FALSCH, dann gehe zu dem nächsten (P&sub1;, p2)-Paar über. Falls ACCEPT = WAHR, dann kann nicht auftreten. Wenn P der letzte Punkt auf einer Trimmkurve mit offener Schleife ist, dann füge zu der Liste eine END-Tabelle für P NEU hinzu, sonst füge eine MITTEL-Tabelle für P NEU hinzu. INNERHALB := WAHR Wenn P&sub1; NEU < > P NEU ist, dann füge zu der Liste eine ANFANGS-Tabelle für P&sub1; NEU und eine END-Tabelle für P NEU hinzu, sonst tue nichts.
Die Schritte 9 und 10 arbeiten mit den Schritten 6 bzw. 51 die oben beschrieben sind, zusammen. Das Ergebnis dieser eingebetteten FOR-Schleifen ist die Aufteilung jeder Trimmkurven in gerade Liniensegmente. Diese werden dann durch den Schritt 7 gegen den Unterbereich abgeschnitten, dessen Polygon geliefert werden soll. Der Schritt 8 baut eine Liste von Tabellen auf, die die geschnittenen geraden Liniensegmente beschreibt.
In den Schritten 11 (a) - (d) wird die Liste der Tabellen, die im Schritt 8 erzeugt wird, auf vier Arten weiterverarbeitet. Die erste davon ist eine Untersuchung durch den Schritt 11 (a) für die beiden Spezialfälle, die in den Figuren 13A - B gezeigt ist.
Es wird nun auf Figur 13A Bezug genommen, was dort gezeigt ist, ist ein Unterbereich 49 und eine Trimmkurve 50 mit einem Punkt 51, der "gerade außerhalb" des Schneidefensters liegt. Gemäß dem Schneidealgorithmus, der in Schritt 7 der Figur 9 beschrieben ist, wird ein Schnittpunkt 52 dafür berechnet werden, wo die Trimmkurve 50 aus dem Schneidefenster 49 "herausgeht". Entsprechend dem Beispiel kommt die Trimmkurve genau dort wieder zurück. Der Schneidemechanismus wird zuverlässig einen weiteren Schnittpunkt 53 erzeugen. Wenn der Punkt 51 ausreichend nah der Schneidegrenze liegt "die in dem Beispiel die rechte Kante ist, aber sie könnte irgendeine Kante sein), kann die finite Auflösung der Zahlen, die bei den Berechnungen benutzt werden, dazu führen, daß der Ausgangs- und der Eintrittspunkt aufeinanderliegen. Dies ist es, was die Figur 13A behandelt; innerhalb des Grades der arithmetischen Präzision, die verwendet wird, sind die Punkte 53 und 52 derselbe Punkt. Dies ist tatsächlich das, was wir mit "fast nicht" außerhalb meinen.
Wenn die oben beschriebene Situation auftritt, werden zwei Tabellen mit bestimmten Eigenschaften nacheinander zu der Liste hinzugefügt. Insbesondere wird die erste eine END-Tabeile sein (siehe FFI in Verbindung mit Schritt 8 der Figur 9), und die zweite wird eine ANFANGS-Tabelle sein. Weiterhin werden beide Tabellen genau identische u-Werte und genau identische v-Werte haben. Dieser Zustand ist der erste spezielle Fall, der mit dem Verarbeiten der Liste von Tabellen durch den Schritt 11(a) verbunden ist.
Der erste Spezialfall wird aufgefunden, indem jede der kreisförmig verbundenen Unterlisten, die den Trimmkurven zugeordnet ist, untersucht wird. Wenn irgendeine Unterliste logisch benachbarte (d.h. bei geeigneter Berücksichtigung der Hülladresse, um eine korrekte logische Anordnung zu erzeugen) ANFANGS- und END-Tabellen enthält, die jede dasselbe identische (u, v)-Paar enthalten, dann wird jede der Tabellen in eine MITTEL-Tabelle umgewandelt.
Der zweite Spezialfall, auf den untersucht wird, ist in der Figur 13B veranschaulicht. Dieser Fall ist im allgemeinen dem ersten Spezialfall analog, mit dem Unterschied, daß sich die Trimmkurve 54 "praktisch kaum" in das Schneidefenster 55 erstreckt. Insbesondere wird die finite Auflösung der Zahlen, die bei der Berechnung der Schnittpunkte benutzt wird, eine ANFANGS-Tabelle und eine END-Tabelle für Punkte 56 und 57 mit demselben (u, v)-Paar erzeugen. Jedoch werden in diesem Fall die ANFANGS- und END-Tabellen durch eine MITTEL-Tabelle für den Punkt 58 getrennt werden.
Der zweite Spezialfall wird in dem Schritt 11(a) durch eine Untersuchung der Liste auf Unterlisten gefunden, die ANFANGS- MITTEL- END-Sequenzen enthalten, mit ANFANGS- und END-Tabellen, die dasselbe identische (u, v)-Paar enthalten. Wenn eine solche Sequenz gefunden wird, wird der SKIP-Merker (siehe Schritt 8 der Figur 9) in allen drei Tabellen gesetzt. Die Nettowirkung davon beim späteren Verarbeiten dieser Tabellen ist ihre tatsächliche Löschung; sie werden einfach ignoriert.
In Schritt 11(b) wird die Liste der Tabellen verarbeitet&sub1; um vier neue Unterlisten zu erstellen; eine Unterliste für jede Kante des Schneidefensters, wobei jede solche Unterliste die Trimmkurven benennt, die die zugeordnete Kante überqueren. Diese neuen Kanten-Unterlisten werden an Ort und Stelle gebildet, wie es zuvor gewesen ist, indem das Feld NÄCHSTE ADRESSE der Tabellen benutzt wird, um die Kanten-Unterlisten miteinander zu verbinden. (Dies wird lediglich eine zwischengeschaltete Verbindung des Feldes NÄCHSTE ADRESSE sein, nicht ihre endgültige Verwendung.)
Nur ANFANGS- und END-Tabellen ohne ihre gesetzten SKIP-Merker werden in Kanten-Unterlisten eingeschlossen. Beim Bilden der Kanten-Unterlisten wird spezielle Aufmerksamkeit den Fällen geschenkt, in denen ein (u, v) -Paar in einer ANFANGS- oder END-Tabelle auch ein Eckpunkt des Schneidefensters ist. In diesem Zusammenhang wird es hilfreich sein, sich nun auf Figur 14 zu beziehen, welche ein Schneidefenster veranschaulicht, das von verschiedenen Trimmkurven durchquert wird. Eine ANFANGS- oder END-Tabelle, deren (u, v)-Paar auch (zufällig) den Eckpunkt I beschreibt, geht in die Kanten-Unterliste für die obere Kante 59 ein. Auf ähnliche Weise geht eine ANFANGS- oder END-Tabelle an der Ecke II in die linke Kante 60 ein. Eine ANFANGS- oder END-Tabelle an der Ecke III geht in die untere Kante 61 ein. Auf ähnliche Weise geht eine ANFANGS- oder END-Tabelle an der Ecke IV in die rechte Kante 62 ein.
Wenn sie einmal gebildet ist, wird jede Kanten-Unterliste nach entweder aufsteigenden oder abnehmenden Werte entweder von u oder v sortiert, abhängig davon, welche Kante die Unterliste darstellt. Die Attribute ANFANG und ENDE beeinflussen das Sortieren nicht. Die Kanten-Unterliste für die linke Kante wird entsprechend abnehmender Werte von v sortiert. Die Kanten-Unterliste für die untere Kante wird entsprechend zunehmender Werte von u sortiert. Die Kanten-Unterliste für die rechte Kante wird entsprechend zunehmender Werte von v sortiert. Die Kanten-Unterliste für die obere Kante wird entsprechend abnehmender Werte für u sortiert.
In dem Schritt 11(c) wird die Liste der Tabellen derart verarbeitet, daß vier Kanten-Unterlisten mit Tabellen in der Hauptliste für Ecken und zusätzliche Scheitelpunkte belassen werden, um eine neue kreisförmige Anordnung in der Liste zu erzeugen. Dies ist die endgültige Verwendung des Feldes NÄCHSTE ADRESSE. Die Verschachtelung beginnt (beliebig) mit dem Eckscheitelpunkt I und schreitet im Gegenuhrzeigersinn um die Grenze des Schneidefenster herum fort. Das Feld NÄCHSTE ADRESSE für jede Tabelle für einen Punkt entlang der Grenze wird mit dem nächsten Punkt weiter entlang der Grenze verbunden, ob es ein zusätzlicher Scheitelpunkt ist oder ein Schnittpunkt mit einer Trimmkurve. Es könnte sogar der Fall sein, daß der nächste Scheitelpunkt die nächste Ecke ist. Diese Neuordnung ist in Figur 14 durch die Pfeile dargestellt, die die Punkte verbindet, die mit den C's&sub1; X's, B's und E's markiert sind. Indem zufällig mit dem Scheitelpunkt I begonnen wird, ist die sich ergebende Anordnung C-X-E-X-X-C-X-B-X-E-C-B-C-E-B-C. Die einzigen Arten von Tabellen, die in dieser Neuanordnung mit dem Feld NÄCHSTE ADRESSEN eingeschlossen sind, sind Ecken, zusätzliche Scheitelpunkte und die ANFANGS- und END-Schnittpunkttabellen; ungestört gelassen werden die Unterlisten für jede Trimmkurve, die die Punkte entlang jeder Trimmkurve innerhalb des Schneidefensters aufzählt (die MITTEN zwischen den ANFÄNGEN und ENDEN).
Es wird an dieser Stelle bemerkt werden, daß nichts Spezielles über die Art und Weise gesagt worden ist, in der Tabellen für die Eck-Scheitelpunkte und Tabellen für zusätzliche Scheitelpunkte in der Gesamtliste der Tabellen für das interessierende Schneidefenster einbehalten werden. Es ist klar, daß irgendein Mechanismus gebraucht wird&sub1; um solche Tabellen hinzuzufügen und später aufzufinden, so daß die Verschachtelung, die oben beschrieben worden ist, erreicht werden kann. Verschiedene Techniken sind wohl bekannt, um diese Dinge zu erreichen, und diejenige, die in irgendeiner speziellen Ausführungsform benutzt werden wird, wird zum großen Teil von den Neigungen des Gestalters abhängen. Bei der vorliegenden Ausführungsform liegen sie in ihren eigenen verbundenen Unterlisten, die durch zugeordnete Zeiger identifiziert werden.
Der Schritt 11(d) der Figur 9 berechnet den AUF-Merker für jede Tabelle in der kreisförmig verbundenen Liste, die gerade oben in Verbindung mit der Figur 14 und dem Schritt 11(c) der Figur 9 beschrieben worden ist. Der AUF-Merker gibt an, ob ein Scheitelpunkt AUF der Fläche vorliegen bleibt oder weggeschnitten wird Was uns hier interessiert ist, wie der AUF-Merker berechnet werden kann. Einfach ausgedrückt wird dies durchgeführt, indem ein Punkt aufgefunden wird, wo eine Trimmkurve den Unterbereich verläßt. Durch Definition wird angenommen, daß jeder Punkt auf einer Trimmkurve vorliegt. Das Trimmen umfaßt die weitere Annahme, daß alles in einem Unterbereich, der links von der Trimmkurve liegt (wobei man entlang der Trimmkurve in der Richtung zunehmenden t's fortschreitet) auch vorliegend ist. Demgemäß, wenn wir an einem Punkt auf der Grenze des Unterbereichs beginnen, der auch das Austreten einer Trimmkurve darstellt, liegen auch der nächste Scheitelpunkt in der Richtung des Gegenuhrzeigersinns und alle nachfolgenden Scheitelpunkte, bis man einer Trimmkurve begegnet, vor. Der Leser kann sich selbst bezüglich der Beziehung zwischen "nach links (bei zunehmendem t)" und "im Gegenuhrzeigersinn um den Unterbereich" befriedigen, indem er auf die Figur 14 blickt. Man nehme einen Scheitelpunkt heraus, der AUF der Fläche vorliegt und versuche, sowohl im Uhrzeigersinn als auch entgegen dem Uhrzeigersinn zu gehen.
AUF-Merker werden berechnet, indem irgendeine END-Tabelle als ein Startpunkt aufgenommen wird, etwa der Punkt 63 in Figur 14. Sein AUF-Merker gibt schon AUF an. Dann wird die kreisförmige Liste von Tabellen durchquert, und jeder AUF-Merker wird auch so eingestellt, daß er AUF bezeichnet, bis man einer ANFANGS-Tabelle gegenübersteht. Die AUF-Merker für nachfolgende Tabellen werden gelöscht, um WEG anzugeben, bis man einer END-Tabelle gegenübersteht. Dieser Prozeß wird fortgeführt, bis man wieder zu der anfänglichen END-Tabelle 63 kommt. Wenn dieses bei dem Beispiel durchgeführt wird, das in der Figur 14 gezeigt ist, beginnend mit dem END-Punkt 63 wird die folgende Sequenz von AUF-Merkern erhalten werden (1/0=AUF/WEG) 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0.
Es kann der Fall sein, daß die kreisförmig verbundene Liste für einen Unterbereich keine ANFANGS- oder END-Tabellen enthält. Dies kann auf zwei unterschiedliche Weisen geschehen. Als erstes kann der Unterbereich keine Trimmkurven haben, die ihm überhaupt zugeordnet sind. Ein solcher Unterbereich wird nur Tabellen für Ecken und zusätzliche Scheitelpunkte haben. In dem zweiten Fall kann ein Unterbereich vollständig eine oder mehrere Trimmkurven enthalten. (Diese können die Grenzen des Unterbereichs berühren oder mit ihnen übereinstimmen, übercrueren sie aber nicht, und die Wirkung wird dieselbe sein, wenn die Kurve vollständig innerhalb liegt, ohne zu berühren.) Ein solcher Unterbereich wird eine Liste erzeugen, die Tabellen für Ecken, zusätzliche Scheitelpunkte und MITTEN für die Trimmkurve(n) hat.
Wenn ein Polygon geliefert wird, das dem ersten Fall oben entspricht, wird das Vorliegen des Polygons durch das Vorliegen der benachbarten Polygone bestimmt; es wird entweder vollständig vorliegen oder vollständig fehlen. In dem zweiten Fall ist die Trimmkurve kleiner als die kleinste "interessierende Einheit" (d.h. das Polygon). Die Trimmkurve wird ignoriert werden und das gesamte Polygon wird versuchsweise gehalten. Jedoch folgt es nicht notwendigerweise, daß das Polygon vorliegen bleibt; es kann selbst in einer größeren Trimmkurve liegen und so weggeschnitten werden. In dem zweiten Fall, wie in dem ersten, wird das Vorliegen des Polygons von dem Vorliegen benachbarter Polygone abhängen.
Der zweite Fall oben bleibt wie beschrieben, selbst wenn die innere Trimmkurve selbst eine weitere Trimmkurve enthält. Es wird angenommen, daß diese Situation abwechselnden Bereichen des Vorliegens und Fehlens auf der Oberfläche entspricht. Jedoch sind solche Merkmale zu klein, daß sie innerhalb der gewählten Polygongröße zu sehen sind. Verwechseln Sie diese Situation nicht mit dem Fall, wenn die Polygongröße dahingehend verringert wird, daß die Trimmkurve anfängt, Grenzen des Unterbereiches zu schneiden. Dies erzeugt einfach normales Trimmen, wie üblich.
Aus dem Vorangehenden ist es klar, daß während des Verarbeitens jedes einzelnen Polygons irgendein Mechanismus benötigt wird, um sich zu erinnern, ob bestimmte Polygone vorlagen oder fehlten. Der Mechanismus wird das Speichern der Werte des AUF-Merkers für bestimmte Tabellen für ausgewählte Unterbereiche während des Verarbeitens eines Stückes umfassen. Es wird nun auf die Figuren 10 und 14 Bezug genommen, wobei zurückgerufen werden sollte, daß Unterbereiche in einer bestimmten Reihenfolge genommen werden. Für den ersten Unterbereich innerhalb jeder Zeile wird der AUF-Merker für den Scheitelpunkt IV 64 für die Verwendung bei der Verarbeitung der nächsten Zeile gespeichert. Innerhalb einer Zeile wird der AUF-Merker für den Scheitelpunkt III jedes Unterbereiches zeitweilig zur Verwendung beim Liefern des nächsten Polygons in der Zeile gespeichert. Zusätzlich wird der AUF-Merker für den Scheitelpunkt III 66 des letzten Unterbereiches der ersten Zeile zur Verwendung beim Verarbeiten eines Stückes rechts vom gegenwärtig gültigen Stück gespeichert. (Obwohl wir es bezüglich dieses Punktes nicht erwähnt haben, wird eine Fläche aus Zeilen und Spalten von Stücken gebildet; Figur 10 könnte sich darauf ebenso einfach wie auf Unterbereiche wie innerhalb eines Stückes beziehen.) Ähnlich (um Zeilen von Stücken unterzubringen) wird der AUF-Merker für den Scheitelpunkt I 67 des ersten Unterbereiches der letzten Zeile von Unterbereichen innerhalb eines Stückes auch gespeichert, nach dem Beenden, falle es eine ANFANGS- oder END-Tabelle gibt, die exakt mit dem Scheitelpunkt I übereinstimmt. Ein solches Speichern geschieht auch für die Verwendung beim Verarbeiten eines nachfolgenden Stückes; das Komplementieren berücksichtigt einen speziellen Fall, der in dem Absatz beschrieben wird, welcher folgt.
Man erinnere sich, daß in Verbindung mit Schritt 11(b) der Figur 9 es gesagt wurde, daß eine ANFANGS- oder END-Tabelle, die zufällig dasselbe (u, v)-Paar als Scheitelpunkt I hatten, in die Kanten-Unterliste für die obere Kante des Unterbereiches eingeschlossen würden. Beim Schritt 11(c) wurde gesagt, daß die vier Kanten-Unterlisten im Gegenuhrzeigersinn um den Unterbereich verschachtelt wurden, beginnend mit dem Scheitelpunkt I. Dies bedeutet, daß in dem speziellen Fall, in dem eine Trimmkurve eine Grenze schneidet, indem sie durch den Scheitelpunkt I 67 läuft, es in der kreisförmig verbundenen Liste tatsächlich zwei Tabellen gibt, die den Scheitelpunkt I beschreiben; eine für den Scheitelpunkt I selbst und eine für den ANFANG oder das ENDE, welcher/welches mit dem Scheitelpunkt I übereinstimmt. Jede dieser Tabellen hat einen AUF-Merker; spezielle Aufmerksamkeit muß darauf gerichtet werden, wie diese im Licht der Regeln, über die sie eingestellt wurden, und dem vorliegenden speziellen Fall interpretiert werden.
Es gibt drei zuvor erwähnte Regeln oder Normen, die auf den AUF-Merker anwendbar sind. Diese sind:
1. Alle Punkte entlang einer Trimmkurve liegen AUF der Oberfläche.
2. Wenn man entlang einer Trimmkurve in die Richtung zunehmender Werte von t fortschreitet liegen Punkte auf der Fläche links von der Trimmkurve AUF der Fläche.
3. Wenn im Gegenuhrzeigersinn um den Unterbereich fortschreitet, haben Scheitelpunkte, die sich unmittelbar an ein ENDE anschließen, Tabellen, die mit AUF markiert sind, bis zum nächsten ANFANG, der auch mit AUF markiert werden wird. Ähnlich sind Scheitelpunkte unmittelbar nachfolgend an einen ANFANG WEG, bis zum nächsten ENDE, das selbst mit AUF markiert ist.
Nun sei angenommen, daß ein ANFANG mit dem Scheitelpunkt I übereinstimmt. Entsprechend der Regel 3 wird der Scheitelpunkt I mit WEG bezeichnet werden (er fehlt). Jedoch ist das benachbarte Stück oberhalb des gegenwärtig gültigen Stückes wegen der Regel II AUF (es liegt vor). Somit muß der Wert des AUF-Merkers für den Scheitelpunkt I 67, der zu dem nächsten Stück fortschreitet, von WEG zu AUF umgeschaltet werden.
Es sei angenommen, daß ein ENDE mit dem Scheitelpunkt I übereinstimmt. Entsprechend der Regel 3 wird der Scheitelpunkt I mit AUF markiert werden. Jedoch ist das benachbarte Stück oberhalb des gegenwärtig gültigen Stückes wegen der Regel 2 WEG. Somit muß der AUF-Merker für den Scheitelpunkt I 67, der zu dem nächsten Stück fortschreitet, von AUF zu WEG umgeschaltet werden.
Somit ist die allgemeine Regel zum Fortschreiben des AUF-Merkers für den Scheitelpunkt I 67 des ersten Unterbereichs der letzten Zeile: wenn es keinen ANFANG oder kein ENDE gibt, das mit dem Scheitelpunkt I 67 übereinstimmt, dann schreibe den ungeänderten Wert des AUF-Merkers für den scheitelpunkt I 67 fort. Wenn es einen ANFANG oder ein ENDE gibt, das mit dem Scheitelpunkt I 67 übereinstimmt, dann schreibe das Komplement des Wertes des AUF-Merkers des Scheitelpunktes I 67 fort.
Eine spezielle Regel wird gebraucht, um den AUF-Merker für jeden allerersten Scheitelpunkt einer gesamten Fläche zu berechnen. Eine solche Regel entspricht einer Konvention, sollte aber konsistent mit den Schneideoperationen sein, die auf den allerersten Scheitelpunkt anwendbar sein können. Beispielsweise, wenn angenommen wird, daß der allererste Scheitelpunkt immer AUF der Fläche vorliegt, könnte dieses es nicht erlauben, daß der Scheitelpunkt weggeschnitten wird. Eine zweckmäßige Regel für die Berechnung des AUF-Merkers des allerersten Scheitelpunktes ist es zu fordern, daß Flächen, Kanten oder Teile davon, die vorliegen (AUF), von einer Trimmkurve begrenzt werden. Mit diesem Ansatz kann angenommen werden, daß der erste Scheitelpunkt WEG ist. Dieser angenommene Wert wird ignoriert, wenn eine Trimmkurve wenigstens ein ANFANGS/ENDE-Paar von Scheitelpunkt-Tabellen für das erste Polygon erzeugt, da in einem solchen Fall es möglich ist, wie es oben gezeigt ist, den richtigen Wert des AUF-Merkers für jeden Scheitelpunkt zu berechnen. Beim Fehlen eines solchen Paares von Scheitelpunkt-Tabellen ist dann tatsächlich das gesamte erste Polygon weggeschnitten worden.
Ein interessanter Spezialfall tritt auf, wenn die Trimmkurve um die Kante der Fläche die einzige Trimmkurve ist, die dem allerersten Polygon zugeordnet ist. In dem Fall stimmen die linke und untere Kante des Polygons mit der Trimmkurve überein, und zwei Sätze von Scheitelpunkten treten auf, die diese beiden Kanten beschreiben. Ein Satz sagt, daß die Ecken und zusätzlichen Scheitelpunkte für die Polygon-Kanten bei der Fläche fehlen, während die Scheitelpunkte, die für den Schnitt solcher Kanten mit der Trimmkurve berechnet werden, durch Definition AUF der Fläche liegen. Wegen der Art, wie der Schneidemechanismus arbeitet, werden die Eck-Scheitelpunkte, die WEG sind, als Scheitelpunkte auf der Trimmkurve repliziert, was somit die Form des ersten Polygons erhält. Der Mechanismus, der die verbundene Liste von Scheitelpunkttabellen verarbeitet, was unten in Verbindung mit den Figuren 16 und 17 beschrieben ist, toleriert doppelte Beschreibungen und wird WEG-Kanten ignorieren und ein Polygon aus den AUF-Kanten erzeugen. Er würde sich nicht darum kümmern, daß zwei der WEG-Kanten dieselben wie zwei der AUF-Kanten wären. Somit heißt dies, daß eine WEG-Ecke auf einem AUF-Polygon vorliegt.
Nun werde der Schritt 12 der Figur 9 betrachtet. Seine Aufgabe ist es, die Liste der Tabellen zu durchqueren. Schritt 11 fügte zu der Liste Information darüber hinzu, welche ursprünglichen Scheitelpunkte nach dem Schneiden vorliegen bleiben, ebenso, welche Trimmkurven-Scheitelpunkte in das geschnittene Polygon eingeschlossen werden. Es sei angemerkt, daß der Schritt 11 in seiner Wirkung das ursprüngliche Polygon in zwei oder mehr kleinere Polygone geteilt haben kann. Der Schritt 12 benutzt eine einfache Prozedur eingebetteter Schleifen, um die Datenstruktur zu durchqueren, die durch den Schritt ii bereitgestellt worden ist. Eine vereinfachte Darstellung davon, wie die Datenstruktur die Situation der Figur 14 darstellen würde, ist in Figur 15 veranschaulicht. Das Ergebnis des Durchquerens durch den Schritt 12 sind Sequenzen der vorliegenden Polygon-Scheitelpunkte, die durch den Schritt 13 an einen Mechanismus zum tatsächlichen Anzeigen der Polygone gesendet werden. Der Schritt 12 wird eine vollständige Liste von Scheitelpunkten für jedes vorliegende Polygon auf jedem vorliegenden Unterpolygon (einem Teil eines Polygons, das verbleibt, nachdem ein weiterer Teil weggeschnitten worden ist) erzeugen, das sich aus dem Schneideprozeß ergibt.
Die Figur 15 ist eine vereinfachte Veranschaulichung einer möglichen kreisförmig verbundenen Liste von Scheitelpunkt-Tabellen, die sich daraus ergeben könnte, daß der Schritt 11C der Figur 9B auf das Beispiel der Figur 14 angewendet würde. Die Annahtne wurde gemacht, daß die Trimmkurve #1 (für dieses spezielle Polygon) am Punkt 68 der Figur 14 beginnt (t = 0), und daß die andere der beiden Trimmkurven etwas außerhalb des Unterbereiches beginnt. Die gesamte kreisförmig verbundene Liste der Figur 15 kann durch eine Grenzen-Liste benannt werden. Das Feld "nächste Adresse" verbindet unbeschnittene Polygon-Scheitelpunkte und Schnittpunkte zwischen den Polygonkanten und den Trimmkurven in der Grenzen-Liste. Eingebettet innerhalb der Grenzen-Liste sind Trimmkurven-Unterlisten. Die Trimmkurven-Unterlisten werden durch eine Kombination der räumlichen Anordnung und des Hülladressenfeldes verbunden. Es gibt eine Trimmkurven-Unterliste für jede Trimmkurve. Wenn man einem ANFANG begegnet, während man die Grenzen-Liste durchquert, kann eine Auswahl getroffen werden, entweder entlang der Grenzen-Liste fortzufahren oder dazu überzugehen, die Trimmkurven-Unterliste zu durchqueren. (Die Grenzen-Liste und die Trimmkurven-Unterliste) teilen sich ANFANGS- und END-Tabellen; um umzuschalten, ist alles, was nötig ist, der anderen Kette der Verbindungen zu folgen.) Wenn eine Trimmkurven-Unterliste bis zu ihrem ENDE durchquert wird, wird die Grenze an dem Punkt wieder betreten.
Der Schritt 12 ist in Figur 16 als ein vereinfachtes Ablaufdiagramm dargestellt und in Figur 17 als Pseudocode zum Arbeiten auf der Liste von Tabellen, die die Information enthalten, welche im Schritt 8 der Figur 9 beschrieben ist.
Es wird vermutet, daß das Ablaufdiagramm der Figur 16 praktisch selbsterklärend ist, wenn man es in dem Kontext dessen sieht, was ihm vorangegangen ist. Es umfaßt eine äußere Schleife, gezeigt in Figur 16A, die einen beliebigen Scheitelpunkt in der kreisförmig verbundenen Grenzen-Liste als einen anfänglichen Scheitelpunkt auswählt, was ihn dann als "ersten" markiert. Die äußere Schleife läuft dann durch die Grenzen-Liste. Wenn sie entdeckt, daß sie zurück zu dem Scheitelpunkt gekommen ist, der mit "erster" markiert worden ist, ist der Prozeß beendet, und die Schleife endet. Die Hauptaktivität der äußeren Schleife ist es, Scheitelpunkte zu identifizieren, die noch nicht aufgesucht worden sind und die auf der Fläche liegen. Wenn ein solcher Scheitelpunkt gefunden ist, wird sein Ort in der Grenzen-Liste gespeichert, so daß die äußere Schleife wieder das Durchlaufen der Liste nach diesem Punkt aufnehmen kann, nachdem die mittleren und inneren Schleifen die Liste selbst durchlaufen konnten. Mit der auf diese Weise "abgehängten" äußeren Schleife, wie es war, beginnt das weitere Verarbeiten der Liste durch die Mittelschleife
Die Mittelschleife fügt zu einer Polygonliste irgendwelche vorliegenden Nicht-Scheitelpunkte für Trimmkurven hinzu und identifiziert einen ANFANGS- oder END-Scheitelpunkt. Wenn ein ANFANGS-Scheitelpunkt gefunden ist, wird er zu der Polygonliste hinzugefügt und es wird dann in die innere Schleife eingetreten. Ein END-Scheitelpunkt wird auch zu der Polygonliste hinzugefügt, da er ein nächster Scheitelpunkt ist, der AUF dem Polygon vorliegt, und weil er nun als aufgesucht markiert worden ist und nicht weiter verarbeitet werden wird, wenn er wieder aufgesucht wird.
Die innere Schleife durchläuft eine Trimmkurven-Unterliste, deren Kopf erreicht worden ist, indem mit der Jußeren und mittleren Schleife entlang der Grenzen-Liste gelaufen worden ist. Die mittlere Schleife tritt in die innere Schleife nach dem Hinzufügen eines ANFANGS-Scheitelpunktes zu der Polygonliste ein; die innere Schleife kehrt zu der mittleren Schleife zurück, wenn der entsprechende Teil der Trimmkurven- Unterliste vollständig durchquert worden ist und die zugeordneten Scheitelpunkte zu der Polygonliste hinzugefügt worden sind. Die mittlere Schleife nimmt dann ihren Weg durch die Grenzen-Liste wieder auf. Die innere Schleife wird wie notwendig jedesmal dann wiederverwendet, wenn man dem Kopf einer neuen Trimmkurven-Unterliste begegnet. Die mittlere Schleife wird sich selbst beenden, wenn ein gesamtes geschlossenes Polygon zu der Polygonliste hinzugefügt worden ist. Dieser Zustand wird erfaßt, wenn die mittlere Schleife zu einem Scheitelpunkt zurückkehrt, der bereits aufgesucht worden ist. Dies bedeutet nicht notwendigerweise, daß die Grenzen-Liste vollständig abgearbeitet worden ist; das Trimmen kann ein ursprüngliches Polygon in zwei oder mehr Subpolygone schneiden. Solange die äußere Schleife nicht vervollständigt worden ist, können weitere Subpolygone durch die Grenzen-Liste beschrieben werden.
Nach dem Zusatz eines vollständigen Polygons zu der Polygonliste kehrt die mittlere Schleife zu der äußeren Schleife zurück. Sie nimmt ihre Bearbeitung an dem Punkt in der Grenzen-Liste wieder auf, wo sie sie verlassen hat. Sie fährt fort, die Liste zu durchqueren, wobei nach Scheitelpunkten Ausschau gehalten wird, die noch nicht aufgesucht worden sind. Wenn sie einen findet, verwendet sie die mittlere Schleife wieder, um ein weiteres vollständiges Subpolygon auf die Polygonliste zu setzen.
Es ist wesentlich einfacher, Scheitelpunkt-Information für Ecken und zusätzliche Scheitelpunkte (Operation 69 in Figur 16) in die Polygonliste aufzunehmen, als es für Punkte entlang von Trimmkurven (Operationen 70 und 71 in Figur 16) ist. Die frühere Information wird, wie zuvor erwähnt, durch die Vorwärts-Differenziertechnik berechnet. Die letztere Information umfaßt das Berechnen, für beliebige Punkte in dem uv-Raum, der Scheitelpunkt-Position in dem XYZ-Raum und des Flächennormalenvektors an dem Scheitelpunkt. Obwohl dies vom Konzept her nicht schwierig ist, ist dies eine viel Zeit verbrauchende Operation.
Figur 17 ist ein vereinfachter Abschnitt des Pseudocodes zum Durchführen derselben Aktivität, wie sie in der Form des Ablaufdiagramms in Figur 16 beschrieben ist. Der Unterschied ist, daß die Figur 17 mehr der Tabellenstruktur umfaßt, die in Verbindung mit den Schritten 8 - 11 der Figur 9 beschrieben worden ist.
Wir beschließen unsere Erläuterung eines bevorzugten Verfahrens der Trimmf lächenpolygone mit einer Untersuchung bestimmter Verbesserungen, die in das Verfahren eingefügt werden können. Wir werden in den nächsten paar Absätzen Wege betrachten, die Wirkungen einer weniger als idealen Parametrisierung der Trimmkurvenfunktionen zu minimieren und die Anzahl der Trimmkurven, die betrachtet werden muß, während jeder Unterbereich und sein Polygon verarbeitet werden, auf ein Minimum zu reduzieren.
Idealerweise würde man gern gleiche Schritte in t haben, um gleiche Zuwächse in u und gleiche Zuwächse in v zu erzeugen. Diese Eigenschaft ergibt sich aus der Natur der B-Spline- Funktionen, die gewählt werden, um die Trimmkurven darzustellen, und werden in einem größeren oder kleineren Ausmaß erhalten. Wenn eine solche Gleichheit erhalten wird, wird gesagt, daß es eine gute Parametrisierung für die Trimmkurvenfunktionen gibt. Eine schlechte Parametrisierung kann nicht immer vermieden werden, und, wenn sie unkorrigiert gelassen wird, wird sie bestimmte Probleme für den Trimmprozeß hervorrufen. Insbesondere kann sie bewirken, daß die Anzahl der Polygon-Scheitelpunkte für geschnittene Polygone unangemessen groß wird. Das wiederum erhöht die Menge an Speicher, der für das Beschneiden der Polygone zur Verfügung gestellt werden muß. Anstatt daß man Speicher zusätzlich bereitstellt, um einem Phänomen zu begegnen, das keinen besonderen Nutzen hat, ist es ein befriedigender Ansatz, die uv-Paare zu untersuchen, die durch Berechnen der Trimmkurven funktion mit einer gewählten Schrittgröße in t erzeugt worden sind, und solche zu unterdrücken, die von ihren Vorgängern keine ausreichende Entfernung haben. Bezüglich einer weiteren Einführung dessen, was wir diskutieren wollen, wende man sich zu der Beschreibung der Figur 8.
Man betrachte die Trimmkurve 72, die in einem Bereich des uv-Raumes durch Figur 18 gezeigt ist. Gleiche Schrittgrößen von delta t 73 erzeugen veränderliche delta u's 74 und veränderliche delta v's 75. Man bemerke, wie die Zeichenmarkierungen auf der Kurve 72 einen veränderlichen Abstand haben; sie sind die berechneten Koordinaten in dem uv-Raum entsprechend der gleich beabstandeten Zeigermarken in dem t-Raum.
Aus der Diskussion der Figur 8 und aus Schritt 6 der Figur 9 wird man sich erinnern, daß eine Schrittgröße in t (delta t) so ausgewählt ist, daß sie maximal für delta u und delta v erzeugt, die ungefähr gleich der Entfernung zwischen Polygon- Scheitelpunkten entlang der Kante des Stückes sind, wobei die Entfernung als Kanten-Schrittgröße bezeichnet werden kann. Auf diese Weise wird das delta t 73 der Figur 18 ausgewählt. Zu Veranschaulichungszwecken sei angenommen, daß das größte delta v 75, das in Figur 18 gezeigt ist, benutzt wurde, um delta t zu bestimmen. Bei der vorliegenden Veranschaulichung werden die delta v's größer sein als die delta u's. Für eine davon verschiedene Trimmkurve kann es der Fall sein, daß das größte delta u das größte delta v überschreitet und verwendet werden würde, um delta t zu wählen. Der Prozeß des Wählens von delta t ist in Verbindung mit Schritt 6 der Figur 9 beschrieben.
Die gerade Liniensegment-Näherung der Trimmkurve 72, die sie erhielt, indem sie berechnet wurde, arbeitet bei den gleichen Schrittgrößen von delta t 73 und wird verfeinert, indem gefordert wird, daß wenigstens eines von delta u und delta v zweiundfünfzig Prozent der Kanten-Gittergröße überschreitet. Wenn es keines tut, dann wird der Punkt in dem uv-Raum ignoriert und der nächste wird betrachtet usw. Entsprechend dieser Technik würde der Punkt 76 ignoriert werden und das gerade Liniensegment 77 würde vom Punkt 78 zum Punkt 79 laufen. Der erste Punkt entlang jedes B-Spline-Trimmkurvensegmentes ist der Anfangspunkt, an dem der Punktauswahlprozeß beginnt. Dies gewährleistet, daß die B-Spline-Trimmkurvensegmente sich wie beabsichtigt verbinden.
Das zweiundfünfzig-Prozent-Kriterium kommt aus einer Beziehung, die zwischen dem kürzesten und längsten akzeptierten geraden Liniensegment besteht. Die Beziehung umfaßt eine Gleichheit zwischen dem Betrag, um den ein längstes akzeptiertes gerades Liniensegment (eines bei fünfundvierzig Grad) die Kantenschrittgröße einerseits überschreitet, und der Größe des kürzesten akzeptierten geraden Liniensegmentes (eines&sub1; das horizontal oder vertikal liegt), die größer ist als die Kantenschrittgröße andererseits. Es kann gezeigt werden, daß die gewünschte Gleichheitsbeziehung erhalten werden wird, wenn das Auswahlkriterium etwa zweiundfünfzig Prozent der Kantenschrittgröße beträgt.
Die Anzahl der Trimmkurven, die betrachtet werden muß, während ein Unterbereich und sein Polygon verarbeitet werden, kann verringert werden, indem man die folgende Technik benutzt. Einfach ausgedrückt wird Information über den Ort jedes Trimmkurvensegmentes innerhalb des Bereiches seiner B-Spline-Definition zugeordnet. Diese Information wird benutzt, um aus der Betrachtung diejenigen Segmente auszuschließen, die möglicherweise nicht den Unterbereich schneiden werden, der verarbeitet werden soll.
Vor der Erzeugung des ersten Polygons für ein neues Stück wird für jedes B-Spline-Segment jeder Trimmkurve ein vextent gefunden. Das vextent ist der Bereich in v von dem minimalen v-Wert bis zu dem maximalen v-Wert in der Menge (u, v)-Paaren, die sich aus der verfeinerten Parametrisierung ergeben, die in Verbindung mit Figur 18 beschrieben worden ist. Das unten erwähnte uextent ist auf ähnliche Weise definiert. Das vextent für jedes B-Spline-Segment wird an einem Ort innerhalb einer Datenstruktur gespeichert, die die Trimmkurven für das Stück enthält.
Man erinnere sich, daß die Polygone mit einer zeilenweise Anordnung der Unterbereiche erzeugt werden. Siehe die Diskussion der Figur 10. Am Anfang jeder Zeile der Polygone wird das vextent jedes Trimmkurvensegmentes für das Stück untersucht. Diejenigen Trimmkurvensegmente, welche ein vextent haben, das über den Bereich von v für die gegenwärtig gültige Zeile liegt, werden weiter berechnet, um ihr zugeordnetes uextent zu entdecken. Das uextent für jedes derartige überlappende Segment wird auch in der Trimmkurven-Datenstruktur gespeichert.
Für jedes Polygon entlang der Zeile werden nur diejenigen B-Spline-Segmente, bei denen sowohl das uextent und das vextent den gegenwärtig gültigen Unterbereich überlappen, in dem Schneide- und Trimmprozeß betrachtet, der in Verbindung mit den Figuren 6 - 16 beschrieben worden ist. Beispielsweise, und wiederum mit Bezug auf Figur 6, würde das Trimmkurvensegment 80 für keinen Unterbereich/Polygon in der Zeile 82 des Stückes 12 von Interesse sein; das Segment 80 hat kein vextent, das mit dem vextent der Zeile 82 überlappt. Andererseits überlappt vextent des Segmentes 81 mit dem der Zeile 82, und das uextent des Segmentes 81 wird vor dem Verarbeiten irgendeines der Unterbereiche entlang der Zeile 82 berechnet. Da das uextent des Segmentes 81 das uextent des Unterbereiches 83 überlappt, wird das B-Spline-Segment 81 der Trimmkurve 11 in die Schneide- und Trimmaktivitäten für den Unterbereich eingeschlossen. Das Segment 80 würde nicht in irgendwelche Aktivitäten für irgendeinen Unterbereich/Polygon entlang der Zeile 82 eingeschlossen werden, noch würde es, als weiteres Beispiel, in Verbindung mit dem Unterbereich 84 benutzt werden. Und in derselben Weise würden weder das Segment 80 noch das Segment 81 in die Aktivitäten für irgendeinen Unterbereich/Polygon entlang der Zeile 85 eingeschlossen werden; kein vextent für die Segmente überlappt dasjenige für die Zeile.
Man nehme nun Bezug auf die Figur 19, in der eine bildhafte Darstellung eines tatsächlichen Graphiksystems gezeigt ist, das das Verfahren der Erfindung verkörpert. Insbesondere umfaßt das Graphiksystem einen Computer 86, eine Tastatur 87, eine Tastenbox 88, eine Drucktasterbox 89 und eine Maus 90. Der Computer 86 kann die Software ausführen, die am Beginn dieser Beschreibung erwähnt worden ist, die mit dem Benutzer wechselwirkt und die B-Spline-Beschreibungen der Fläche und ihrer Trimmkurven vorbereitet. Der Computer 86 ist mit einem Graphikbeschleuniger 91 durch einen örtlichen Hochgeschwindigkeits-Graphikbus 92 verbunden. Der Graphikbeschleuniger 91 ist wiederum mit einem Farbmonitor 94 durch drei Koaxialkabel zum Übertragen der roten, grünen und blauen (RGB) Videosignale gekoppelt.
Die oben beschriebenen Trimmaktivitäten werden vollständig innerhalb des Graphikbeschleunigers 91 durchgeführt. Während es denkbar ist, daß das Trimmverfahren, das beschrieben worden ist, in der Software in dem Computer 86 ausgeführt werden kann, umfaßt ein solcher Ansatz notwendigerweise eine wesentliche Strafe durch verringerte Leistungsfähigkeit verglichen mit dem Trimmen durch geeignete Hardware. Um dieses und weitere Ziele zu erreichen, spricht der Graphikbeschleuniger 91 auf den Computer 86 über die Ausführung einer Anzahl von Befehlen an. Unter diesen sind einige, die: den Graphikbeschleuniger anweisen, in einer Datenstruktur die Definition einer oder mehrerer Trimmkurven zu speichern; in einer Datenstruktur eine Flächen-Stückedefinition zu speichern und sie dann mit dem Trimmen entsprechend der zuvor definierten Trimmkurve bereitzustellen; und einen Befehl, um alle zuvor definierten Triminkurven zu löschen. Auch eingeschlossen sind Befehle, einen Stapel von AUF-Merkern aufzubauen und abzubauen. Die AUF-Merker für die obere rechte und untere linke Ecke ausgewählter Stücke werden in zwei getrennten Stapeln gespeichert, um die Unterteilung der Stücke zu vereinfachen. Die Unterteilung von Stücken in Unterstücke tritt auf, wenn ein gegebenes Stück zu viele Trimmkurven enthält; es gibt praktische und kostenbezogene Betrachtungen (d.h. die Speichergröße), die die Anzahl der Trimmkurven für irgendein einziges Stück begrenzen, die von dem Graphikbeschleuniger 91 behandelt werden können.
Die Speicherbegrenzungen, die oben erwähnt worden sind, erlegen keine praktischen Beschränkungen auf die Anzahl der Trimmkurven, die für ein Stück angewendet werden müßten. Die Software in dem Computer bestimmt die Notwendigkeit für eine Stück-Unterteilung, wenn die Anzahl der Trimmkurvensegmente für ein gegebenes Stück ungefähr vierzig bis sechzig überschreitet (die Software kann entweder Beschränkungen in dem Graphikbeschleuniger voraussetzen oder ansprechend auf einen angegebenen Überlauf, der von dem Graphikbeschleuniger zurückgegeben wird, unterteilen.) Ein zuvor ungeteiltes Stück kann bis zu sechzehnmal geteilt werden. Jeder Akt der Unterteilung kann das gegenwärtig vorliegende Stück in vier Unterstücke unterteilen.
Jedesmal, wenn eine Unterteilung auftritt, werden die AUF-Merker für die geeigneten anderen Stücke, die bereits bereitgestellt worden sind, auf ihre Stapel geschoben. Es gibt einen Stapel für den Scheitelpunkt I des ersten Polygons der letzten Zeile der Polygone jedes Stückes und einen weiteren Stapel für den Scheitelpunkt III des letzten Polygons der ersten Zeile von Polygonen jedes Stückes. Diese Stapel werden getrennt in Zusammenarbeit mit der Software, die von dem Computer 86 ausgeführt wird, gehalten. Der sich ergebende Mechanismus für die Unterteilung der Stücke öffnet sich dem beschriebenen Verfahren für das Schneiden von Stücken. Das Verfahren arbeitet immer in derselben Weise, ungeachtet dessen, ob das gegenwärtig vorliegende Stück ein Unterstück ist oder nicht.
Die Figuren 20A - C umfassen ein Blockschaubild des Graphikbeschleunigers, der in Figur 19 gezeigt ist. Ein Schnittstellen-Mechanismus 95 koppelt die Trimmkurve und die Stücke-Definitionsbefehle von dem Computer 86 zu einer Wandlermaschine 96. Die Definitionen werden von einer Mikrosequenziereinrichtung 97 in einem Daten-RAM 98 gespeichert. Die Mikrosequenziereinrichtung arbeitet auf diesen Definitionen, um die Koordinaten der Scheitelpunkte für das beschnittene Polygon zu erzeugen. Bildschirmkoordinaten für die Scheitelpunkte der beschnittenen Polygone werden über einen DC (Gerätekoordinaten)-Bus 99 an einen Abtastwandler 100 gesendet, wo der Prozeß des Polygonlieferns weiter auf dem Pixel-Level durchgeführt wird (z.B. Flächenfüllung und Farbinterpolation für die Schattierung).
Die Mikrosequenziereinrichtung 97 arbeitet zusammen mit verschiedenen arithmetischen Einheiten für ganze Zahlen und für Fließpunktoperationen und kann beispielsweise ein AMD 2910 von Advanced Micro Devices sein.

Claims

Verfahren zum Abbilden einer Oberfläche (1) in einem XYZ- Raum mit ersten Parameterfunktionen (4) in einem uv-Gebiet in einem dreidimensionalen graphischen Darstellungs- System, wobei die ersten Parameterfunktionen mittels einer Trimmkurve (8) getrimmt werden, die aus einer geordneten Vielzahl von Segmenten (S&sub1; - S&sub9;) zusammengesetzt ist, von denen jedes durch entsprechende Sätze von Trimmfunktionen definiert ist, gekennzeichnet durch die folgenden Schritte:

Verlagern der geordneten Vielzahl von Segmenten der Trimmkurve durch Auswerten der Sätze von parametrischen Trimmfunktionen bei ausgewählten Werten eines Parameters zum Auffinden von Punkten im uv-Gebiet, welche die ersten parametrischen Funktionen trimmen;

Benutzen des Punktes im uv-Gebiet entsprechend dem Anfang des nächsten Segmentes der Trimmkurve anstelle des Punktes entsprechend dem aktuellen Ende des betreffenden Segmentes und

Darstellen eines sichtbaren Bildes einer Oberfläche auf dem graphischen Darstellungssystem gemäß den Sätzen der parametrischen Trimmfunktionen und gemäß dem vorbeschriebenen Benutzungsschritt.