DE3688918T2

DE3688918T2 - System für geometrische Verarbeitung.

Info

Publication number: DE3688918T2
Application number: DE86107047T
Authority: DE
Inventors: Akira Ohsawa
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1985-05-24
Filing date: 1986-05-23
Publication date: 1993-12-23
Anticipated expiration: 2006-05-24
Also published as: EP0202686A3; HK176395A; EP0202686A2; US4944034A; US5056045A; DE3688918D1; EP0202686B1

Description

HINTERGRUND DER ERFINDUNG

Die Erfindung betrifft ein Computermodellsystem zum Nachbilden von Figuren im n-dimensionalen Raum, wie im Oberbegriff von Anspruch 1 beschrieben. Ein solches System ist aus "Fundamentals of Interactive Computer Graphics" von J. D. Foley und A. van Dam; Addison-Wesley Publishing Company; Reading, Massachusetts, USA; 1982, Seiten 505-510 bekannt.
Beispiele für geometrische/graphische Verarbeitung beinhalten den Entwurf von LSI/VLSI-Schaltungen, logischen Schaltungen, Fahrzeugkarosserien, Gebäuden, Maschinen und Anlagen, Computer-Aided-Design(CAD)-Systemen unter Verwendung van Computergraphiktechnologie, Objektanalyse von Satellitendaten und graphische Analyse, wie sie auf medizinischem Gebiet vorgenommen wird.
Z.B. wird in einem CAD-System zum Entwerfen von LSIs, Maschinen, Gebäuden und Anlagen durch geometrische Verarbeitung die Größe der zu verarbeitenden Geometrie oft groß, d. h. die Gesamtzahl der erforderlichen Elemente beträgt 10&sup4;-10&sup7;. Speziell nimmt die Menge zu verarbeitender Daten bei einem Datenverarbeitungssystem beträchtlich zu, bei dem die Verarbeitung für jeden Dateneinzelwert in bezug auf die zugehörigen Daten ausgeführt werden muß. Darüber hinaus nimmt die Verarbeitungszeit zu, wenn der Wert N größer wird. Obwohl die Verarbeitung im Prinzip möglich ist, liegt die Verarbeitungszeit über dem zulässigen Bereich für praktische Datenverarbeitung, weswegen die Verarbeitung in manchen Fällen unmöglich wird.
Ein Grund dafür, weswegen eine Verarbeitung nicht ausgeführt wird, ist der, daß alle geometrischen Daten selbst dann verarbeitet werden, wenn die geometrische Verarbeitung im wesentlichen Beziehungen zwischen benachbarten geometrischen Einzelwerten handhabt, oder überlappende Einzelwerte zwischen geometrischen Daten gehandhabt werden. Dies, da die spezielle Information, die sich auf diese benachbarten geometrischen Daten bezieht, nicht in der geometrischen Datenbasis enthalten ist. D.h., daß selbst dann, wenn nur ein Teil der geometrischen Daten örtlich zu verarbeiten ist, die Datenverarbeitung für alle geometrischen Daten ausgeführt werden soll. Infolgedessen muß auch eine andere Verarbeitung als die für den erforderlichen Bereich notwendige örtliche Verarbeitung ausgeführt werden.
Es wurde ein System entwickelt, bei dem die geometrische Verarbeitung mit einer besonderen Information ausgeführt wird, die sich auf benachbarte geometrische Daten bezieht, die vorab abgespeichert wird, um diese Schwierigkeit zu vermeiden. In einem solchen System ist jedoch die geometrische Form beschränkt; ferner nimmt die Datenmenge zu und demgemäß wird die Verarbeitungszeit länger. Infolgedessen löst dieses Schema nicht die oben beschriebene Schwierigkeit.
Eine solche Schwierigkeit führt im Fall einer dreidimensionalen geometrischen Verarbeitung, bei der die Datenmenge beträchtlich erhöht ist, zu einem größeren Problem.
In "PROCEEDINGS IECON 84 - 1984 International Conference on Industrial Electronics, Control and Instrumentation; Tokio, 22.-24. Oktober 1984, Bd. 1, Seiten 223-230, ist ein Verfahren zum Erzeugen einer dreidimensionalen Oberfläche aus Abschnittsdaten beschrieben, die zweidimensionale Abschnitte eines Körpers im CAD/CAM-System spezifizieren. In COMPUTERS AND GRAPHICS, Bd. 7, Nr. 3/4, 1983, Seiten 215-224, Pergamon Press Ltd., Exeter, GB: H. Matsuka et al "Concept and Tools for Interactive Graphics-A-IDAS" wird eine allgemeine Darstellung eines graphischen Systems gegeben, ohne daß Einzelheiten der aktuellen Datenstruktur offenbart werden.
In dem zu Beginn angegebenen Dokument wird die Repräsentation von Polygonen in einem Verarbeitungssystem durch Zeiger auf eine Eckenliste oder eine Kantenliste der Ecken bzw. Kanten der gegebenen Polygone offenbart.

ZUSAMMENFASSUNG DER ERFINDUNG

Es ist daher eine Aufgabe der Erfindung, ein System anzugeben, das dazu in der Lage ist, geometrische oder graphische Daten örtlich oder teilweise zu verarbeiten, um dadurch wirkungsvolle Datenverarbeitung mit hoher Geschwindigkeit zu erzielen.
Diese Aufgabe wird durch das in Anspruch 1 beschriebene System gelöst. Die Merkmale bevorzugter Ausführungsbeispiele eines solchen Systems sind in den Unteransprüche 2 bis 14 enthalten.
Kurz gesagt, ist die Erfindung wie folgt charakterisiert. Eine geometrische Figur und ein diese enthaltender Raum werden in Unterräume unterteilt, die dann durch Paare jeweiliger Zeiger repräsentiert werden. Benachbarte geometrische Daten und überlappende geometrische Daten werden abgerufen und unter Verwendung der zugehörigen Zeiger verarbeitet, was eine wirkungsvolle Verarbeitung mit hoher Geschwindigkeit realisiert.
Genauer gesagt, werden die Geometrie und der Raum, in dein die Geometrie angeordnet ist, unter Verwendung von Linien unterteilt, die durch charakteristische Punkte wie Ecken gehen, so daß ein so erhaltener Unterraum durch ein Paar charakteristischer Punkte zu den beiden Seiten definiert ist, die den Unterraum einschließen.
Im Ergebnis kann ein Unterraum durch ein charakteristisches Punktepaar abgerufen werden, und demgemäß kann die geometrische Verarbeitung für einen Bereich der Geometrie ausgeführt werden, z. B. kann eine Verarbeitung für benachbarte geometrische Daten als örtliche Verarbeitung ausgeführt werden.
Kurz gesagt, kann eine Verarbeitung wie die Verarbeitung von Beziehungen zwischen benachbarten geometrischen Daten, das Abrufen überlappender dreidimensionaler geometrischer Daten, logische Verarbeitung wie eine solche mit UND und ODER zwischen dreidimensionalen geometrischen Daten sowie eine Verarbeitung für eine versteckte Oberfläche wirkungsvoll ausgeführt werden, wodurch eine geometrische Hochgeschwindigkeitsverarbeitung realisiert wird.

KURZE BESCHREIBUNG DER ZEICHNUNGEN

Die Erfindung geht aus der folgenden detaillierten Beschreibung in Verbindung mit den beigefügten Zeichnungen hervor, in denen:
Fig. 1 ein schematisches Systemblockdiagramm ist, das ein Computersystem zeigt, bei dem das erfindungsgemäße geometrische Verarbeitungssystem angewendet wird;
Fig. 2(a) ein funktionelles Konfigurationsdiagramm einer geometrischen Verarbeitung im geometrischen Verarbeitungssystem ist;
Fig. 2(b) ein Flußdiagramm der Verarbeitung eines Interpreterprogramms in einer Raumdaten-Verarbeitungseinheit des geometrischen Verarbeitungssystems ist;
Fig. 2(c) ein Verarbeitungsflußdiagramm eines Programmsteuerabschnitts in einer zentralen Verarbeitungseinheit desselben ist;
Fig. 3(a) ein schematisches Diagramm zum Erläutern der grundsätzlichen Repräsentation von Raumdaten des Verarbeitungssystems ist;
Fig. 3(b) ein schematisches Diagramm ist, das die grundsätzlichen Abläufe zum Unterteilen eines Raums im System zeigt;
Fig. 4(a) ein erläuterndes Diagramm ist, das ein konkretes Beispiel von Endpunkten in X-Richtung in einer zweidimensionalen Tabelle für charakteristische Punkte zeigt;
Fig. 4(b) ein erläuterndes Diagramm ist, das ein konkretes Beispiel von anderen Endpunkten als solchen in X-Richtung in der Charakteristikpunkttabelle zeigt;
Fig. 4(c) ein schematisches Diagramm ist, das der zweidimensionalen Tabelle von Fig. 4(a) entspricht;
Fig. 4(d) ein erläuterndes Diagramm ist, das der Tabelle von Fig. 4(b) entspricht;
Fig. 4(e) ein schematisches Diagramm ist, das Codes in den Tabellen zeigt;
Fig. 5(a) ein Diagramm ist, das schematisch Beispiele für geometrische Formen zeigt, die mit der zweidimensionalen Repräsentation zu verarbeiten sind;
Fig. 5(b) ein erläuterndes Diagramm von Raumzeigerpaaren ist, wie sie für die geometrischen Formen zu erzeugen sind;
Fig. 6(a) ein erläuterndes Diagramm ist, das einen Ablauf zum Unterteilen eines Raums in dreidimensionaler Repräsentation zeigt;
Fig. 6(b) ein schematisches Diagramm ist, das Beziehungen von Raumzeigerpaaren zwischen dreidimensionalen geometrischen Daten zeigt;
Fig. 6(c) ein schematisches Diagramm ist, das eine verdeckte Schnittstelle in der dreidimensionalen Repräsentation erläutert;
fig. 6(d) ein Diagramm ist, das ein projiziertes Ergebnis für die Geometrie von Fig. 6(c) in Z-Richtung zeigt;
Fig. 7 ein erläuterndes Diagramm ist, das die Beziehungen zwischen geometrischen Formen und Oberflächenzeigerpaaren zeigt;
Fig. 8(a) ein Diagramm ist, das Beziehungen zwischen der Raumunterteilung einer dreidimensionalen Geometrie und Raumzeigerpunkten erläutert;
Fig. 8(b) ein erläuterndes Diagramm von Raumdaten ist, die einer Ecke der Geometrie von Fig. 8(a) zugeordnet sind;
Fig. 9(a) ein schematisches Diagramm ist, das Beziehungen zwischen den Raumdaten und der Information zum Verbinden der Daten links und rechts zeigt;
Fig. 9(b) ein schematisches Diagramm zum Erläutern eines konkreten Beispiels einer Charakteristiktabelle in der dreidimensionalen Repräsentation ist;
Fig. 9(c) ein erläuterndes Diagramm von Raumdaten um eine konvexe Ecke V eines Polygons ist;
Fig. 9(d) ein Diagramm zum Erläutern einer Charakteristiktabelle ist, die Daten um die konvexe Ecke V zugeordnet ist;
Fig. 10(a) ein erläuterndes Diagramm für Raumdaten ist, die einer Ecke mit einem konvexen Raum zugeordnet sind;
Fig. 10(b) ein schematisches Diagramm zum Erläutern einer Charakteristiktabelle, wenn ein konkaver Raum existiert, ist;
Fig. 11(a) ein schematisches Diagramm ist, das überlappende geometrische Daten veranschaulicht, wenn Überlappung festzustellen ist;
Fig. 11(b) ein erläuterndes Diagramm von Attributen im Diagramm von Fig. 11(a) ist;
Fig. 12(a) ein Diagramm ist, das ein Beispiel zeigt, bei dem Zeiger in einer zweidimensionalen, mehrfarbigen Geometrie repräsentiert werden;
Fig. 12(b) ein vereinfachtes Diagramm ist, das Beziehungen von Tabellen charakteristischer Punkte im Fall von Fig. 12(a) zeigt;
Fig. 13 ein erläuterndes Diagramm des Überlappungszustandes der dreidimensionalen geometrischen Daten ist;
Fig. 14(a) bis 14(d) Diagramme zum Erläutern von Abläufen zum Erzeugen der jeweiligen Raumzeigerpaare sind;
Fig. 14(e) ein Flußdiagramm ist, das einen Verarbeitungsablauf zum Erzeugen geometrischer Daten eines Punktes zeigt;
Fig. 14(f) ein Flußdiagramm ist, das einen Verarbeitungsablauf zum Entwickeln geometrischer Daten einer Kante zeigt;
Fig. 15(a) bis 15(g) Diagramme sind, die jeweils Abläufe zum Eingeben von Daten in eine dreidimensionale Datenbasis erläutern;
Fig. 16(a) ein erläuterndes Diagramm einer Wegweiser-oder Leitpunktverarbeitung zum Auffinden charakteristischer Punkte in der zweidimensionalen Repräsentation mit hoher Geschwindigkeit ist;
Fig. 16(b) ein schematisches Diagramm ist, das eine dreidimensionale Leitpunktverarbeitung veranschaulicht;
Fig. 17(a) bis 17(c) erläuternde Diagramme von Abläufen zum Erzeugen von Raumzeigerpaaren bei jeweiligen speziellen Bedingungen sind;
Fig. 17(d) und 17(e) Diagramme zum Erläutern von Abläufen zum Erzeugen von Kantenzeigerpaaren bei jeweiligen Bedingungen sind;
Fig. 17(f) ein erläuterndes Diagramm eines Zeigerpaars im Fall von Schnittpunkten ist;
Fig. 17(g) ein schematisches Diagramm zum Erläutern von Abläufen zum Erzeugen von Raumzeigerpaaren im Fall ist, daß eine Kurve in Bereichen der Geometrie vorhanden ist;
Fig. 18(a) und 18(b) Diagramme zum jeweiligen Erläutern des Durchlaufpunktes der Ecke und der Charakteristikpunkttabelle bei dreidimensionaler Repräsentation sind;
Fig. 18(c) und 18(d) Diagramme zum jeweiligen Erläutern des Schnittpunktes der drei Oberflächen und der Charakteristikpunkttabelle sind;
Fig. 19 ein Diagramm zum Erläutern räumlicher Beziehungen hinsichtlich einer sich bewegenden Geometrie ist;
Fig. 20 ein erläuterndes Diagramm ist, das Abläufe zum Löschen einer verdeckten Oberfläche zeigt;
Fig. 21 ein schematisches Diagramm zum Erläutern eines Falles ist, bei dem ein Ablaufverfolgungsverfahren für einen sichtbaren Raum verwendet wird;
Fig. 22 ein Diagramm ist, das einen Ablauf zum Erläutern von Raumzeigerpaaren für den Fall zeigt, daß die geometrischen Daten in mehrere Unterbereiche unterteilt werden;
Fig. 23 ein schematisches Diagramm zum Erläutern eines Falls ist, gemäß dem eine besondere Geometrie gesucht wird;
Fig. 24 ein erläuterndes Diagramm eines Beispiels ist, bei dem Eckpunkte zu Raumzeigerpaaren hinzugefügt werden, um die Zeit zu minimieren, die für eine Verarbeitung mit rotierender Suche bei zweidimensionaler Repräsentation erforderlich ist;
Fig. 25(a) und 25(b) schematische Diagramme sind, die jeweils Beziehungen zwischen Raumpunktpaaren für einen Fall zeigen, bei dem Kanten bei dreidimensionaler Repräsentation hinzugefügt werden;
Fig. 26 ein Diagramm zum Erläutern eines Falls ist, bei dem die räumliche Unterteilung in einem System mit Polarkoordinaten ausgeführt wird; und
Fig. 27 ein Blockdiagramm eines geometrischen Verarbeitungssystems gemäß einem anderen Ausführungsbeispiel der Erfindung ist.

BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSBEISPIELE

Es wird nun eine detaillierte Beschreibung von Ausführungsbeispielen der Erfindung unter Bezugnahme auf die beigefügten Zeichnungen gegeben.
Fig. 1 ist ein Blockdiagramm eines Computersystems, auf das der erfindungsgemäße geometrische Verarbeitungssystem angewendet wird.
Diese Konfiguration verfügt über eine zentrale Verarbeitungseinheit (CPU) 1, einen Speicher 2 derselben, eine Raumdaten-Verarbeitungseinheit 3, eine E/A-Steuerungseinheit 4, eine Interfaceeinheit 5, einen Systembus 6, eine Anzeigeeinheit 7, eine Tastatur 8 und eine Magnetplatten-Speichereinheit 9 (die nachfolgend der Einfachheit halber als Platte bezeichnet wird). Die CPU 1, der Speicher 2, die Raumdaten- Verarbeitungseinheit 3 und die E/A-Steuerungseinheit 4 sind jeweils unter Verwendung des Systembusses 6 miteinander verbunden, wodurch es ermöglicht ist, zwischen ihnen Daten zu übertragen. Die E/A-Steuerungseinheit 4 bewirkt über die Interfaceeinheit Datenaustausch mit der Anzeigeeinheit 7, der Tastatur 8 und der Platte 9.
Auf den Speicher 2 wird gemeinsam von der CPU 1, der E/A- Steuerungseinheit 4 und der Raumdaten-Verarbeitungseinheit 3 zugegriffen. Der Speicher 2 beinhaltet einen Programmspeicherbereich 2a für einen Raumdateninterpreter, einen Programmspeicherbereich 2b zum Erzeugen von Raumdaten, einen Programmspeicherbereich 2c für E/A-Steuerung, einen Raumdaten-Speicherbereich 2d, einen Programmspeicherbereich 2e für Zeichnungsverarbeitung und einen anderen Datenspeicherbereich 2f. Im Raumdaten-Speicherbereich 2d sind Tabellen 20-21 für zweidimensionale charakteristische Punkte enthalten, wie in den Fig. 4(a) und 4(b) dargestellt, wie auch eine Tabelle 22 für dreidimensionale charakteristische Punkte, die den charakteristischen Punkten (einschließlich solcher außer den Ecken) jeder Geometrie entsprechen. Die jeweiligen Tabellen enthalten jeweils Information wie ein Raumzeigerpaar (SPP = space pointer pair) in vorgegebener Reihenfolge. Auf derartige Informationseinzelwerte wird gemäß ihrem Suchinhalt Bezug genommen.
Der Programmspeicherbereich 2d für den Programmdateninterpreter in Fig. 1 enthält ein Interpreterprogramm für die Raumdaten-Verarbeitungseinheit 3. Auf Grundlage der im Raumdaten-Speicherbereich 2d abgelegten Raumdaten erzeugt das Programm geometrische Information, die von der CPU zu verarbeiten ist.
Der Programmspeicherbereich 2b zum Erzeugen von Raumdaten enthält ein Zeichenprogramm, wie es in diesem Computersystem auszuführen ist, oder ein Verarbeitungsprogramm zum Bilden vorbestimmter Raumdaten (oder eine Raumzeigerdatei SPF = space pointer file) in Form der Tabellen 20-21 für zweidimensionale charakteristische Punkte, wie in den Fig. 4(a) und 4(b) dargestellt, und der Tabelle 22 für charakteristische Punkte, wie in Fig. 9(b) dargestellt.
Bei der Erfindung ist das Konzept zum Nachbilden geometrischer Figuren das Folgende. Zum einfachen Verständnis wird zunächst das zweidimensionale Nachbilden einer Geometrie beschrieben. Wie es später deutlich gemacht wird, wird dreidimensionale oder n-dimensionale Nachbildung als Erweiterung der zweidimensionalen Nachbildung realisiert.
Im Fall einer zweidimensionalen geometrischen Figur werden charakteristische Punkte Pi und Pi+1, die an geeigneten Stellen auf Kanten der geometrischen Figur einzustellen sind, gesetzt, wie dies in Fig. 3(a) dargestellt ist. Es wird angenommen, daß der geometrische Raum, in dem die geometrische Figur angeordnet ist, durch virtuelle Raumunterteilungslinien Di und Di+1, die durch die charakteristischen Punkte Pi bzw. Pi+1 und Kanten der Geometrie gehen, in mehrere Unterräume unterteilt ist. Raumzeiger SPi und SPi+1 werden den jeweiligen charakteristischen Punkten zugeordnet, und die Raumzeiger SPi und SPi+1, die einem Unterraum entsprechen, werden als Paar von Raumzeigern gesetzt, von denen jedes die Adresse des zugeordneten Raumzeigers anzeigt. Dieses Paar wird als Raumzeigerpaar SPPi definiert. Ein von den charakteristischen Punkten Pi und Pi+1 eingeschlossener Raum ωi wird durch dieses Raumzeigerpaar repräsentiert.
Da ein Unterraum ωi als Einzelgröße behandelt wird, wie sie durch ein Raumzeigerpaar SPPi repräsentiert wird, wie oben beschrieben, kann eine den Raum betreffende geometrische Verarbeitung lokal unter Verwendung des Raumzeigerpaars ausgeführt werden, was zum Minimieren der zu verarbeitenden Datenmenge und zum Einsparen von Speicherplatz führt. Wie es später klargestellt wird, wird im Fall einer dreidimensionalen Geometrie lediglich die Linienunterteilung durch eine Oberflächenunterteilung ersetzt, d. h., das Grundkonzept ist dasselbe.
Ein charakteristischer Punkt Pi kann auf eine geeignete Stelle auf einer Kante einer geometrischen Figur gesetzt werden; ferner kann eine willkürliche Anzahl charakteristischer Punkt Pi festgelegt werden. Wenn zu viele charakteristische Punkte vorliegen, muß jedoch die Größe der Geometriedatendatei notwendigerweise erhöht werden.
Um zu verhindern, daß die Größe der Geometriedatendatei oder der Raumzeigerdatei erhöht wird, werden vorzugsweise Punkte als charakteristische Punkte festgelegt, die in positiver oder negativer X-Richtung vorstehen, oder Eckpunkte der Geometrie.
Fig. 3(b) zeigt ein konkretes Beispiel, bei dem eine solche geometrische Datenverarbeitung vorgenommen wird. Der zweidimensionale geometrische Raum ist in mehrere Unterräume mit den Kanten eines Polygons DRW und Unterteilungslinien (strichpunktiert) unterteilt. Im oberen Abschnitt von Fig. 3(b) sind die charakteristischen Punkte auf die Eckpunkte links und rechts am Polygon festgelegt, wohingegen im unteren Abschnitt jeder Eckpunkt der Figur als charakteristischer Punkt festgelegt ist. Wenn z. B. kein anderes geometrisches Objekt links oder rechts von DRW zu zeichnen ist, wird angenommen, daß die Unterräume ω&sub0; und ω&sub4; links und rechts davon jeweils unbegrenzte Unterräume sind. Um es zu ermöglichen, daß ein Zeigerpaar auf einen solchen unbegrenzten Unterraum gesetzt wird, wird im Konzept angenommen, daß die jeweiligen Außenformlinien in X-Richtung und die Raumunterteilungslinien an negativen bzw. positiven unendlichen Stellen liegen. Auf ähnliche Weise wird für die Außenformlinien in Y-Richtung angenommen, daß sie an negativen bzw. positiven unendlichen Stellen liegen. D.h., daß in Raumzeigerpaaren SPP0 und SPP4 für unbegrenzte Unterräume ω&sub0; und ω&sub4; die Raumzeiger der zugeordneten Komponenten der Paare jeweils einen negativen X-Wert mit dem maximalen Absolutwert und den negativen Y-Wert mit dem maximalen Absolutwert sowie den maximalen positiven X-Wert und den maximalen positiven Y-Wert im geometrischen Raum aufweisen. Auf ähnliche Weise sind im unteren Abschnitt von Fig. 3(b) unbegrenzte Unterräume ω&sub0; und ω&sub1;&sub0; Raumzeigern SPP&sub0; und SPP&sub1;&sub0; zugeordnet. In diesen Zeigerpaaren ist angenommen, daß die Raumzeiger der jeweiligen Komponenten X- bzw. Y-Werte anzeigen, die im wesentlichen ±∞ entsprechen. Selbstverständlich können, wenn der gesamte geometrische Raum durch X- und Y-Außenformlinien jeweils geeigneter Größe unterteilt wird, die Raumzeiger für im wesentlichen als unbegrenzt angesehene Unterräume so festgelegt werden, daß sie X- bzw. Y-Werte bezeichnen, die durch die X- bzw. Y-Außenformlinien angezeigt werden.
Der Raumdaten-Speicherbereich 2d enthält verschiedene zwei- und dreidimensionale Raumdatenwerte in Form von Tabellen. Für das Tabellenformat besteht keine Beschränkung. Z.B. sind die Charakteristiktabellen 20 und 21 der Fig. 4(a) bzw. 4(b) typisch für eine zweidimensionale Repräsentation, während die Charakteristiktabellen von Fig. 9(b) für dreidimensionale Raumdatentabellen repräsentativ sind. Mehrere dieser Tabellen sind im Raumdaten-Speicherbereich 2d abgelegt. Es besteht jedoch keine Beschränkung dahingehend, daß die Raumdaten in solcher Tabellenform abzuspeichern sind.
Auf die Raumdaten-Verarbeitungseinheit 3 wird von der CPU 1 zugegriffen, und es wird das Raumdaten-Interpreterprogramm ausgeführt, um auf die Tabellen 20-22 charakteristischer Punkte Bezug zu nehmen. Obwohl keine besondere Beschränkung besteht, wählt die Raumdaten-Verarbeitungseinheit 3 auf Grundlage einer Adresse, auf die von der CPU 1 zugegriffen wird, eine Art auszuführender geometrischer Verarbeitung aus, ruft Raumdaten unter Verwendung des Raumdaten-Interpreterprogramms ab und interpretiert die Daten, um entsprechende geometrische Daten zu erzeugen, und dann werden die geometrischen Daten an die CPU 1 übertragen.
Wenn die CPU 1 die geometrischen Daten empfängt, führt sie eine vorgegebene geometrische Verarbeitung aus und aktiviert die E/A-Steuerungseinheit 4 von Fig. 1. Infolgedessen werden die Daten z. B. an die Anzeigeeinheit 7 übertragen und dort dargestellt.
Die E/A-Steuerungseinheit 4 führt eine vorgegebene E/A-Verarbeitung aus, wenn das Raumdaten-Interpreterprogramm durch die Raumdaten-Verarbeitungseinheit 3 gestartet wird, und es erfolgt ein Zugriff durch die CPU 1. D.h., daß die E/A- Steuerungseinheit 4 dazu verwendet wird, geometrische Daten an die Anzeigeeinheit 7 zu übertragen, um die Daten auf dieser darzustellen, oder um die geometrischen Daten an die Platte 9 zu übertragen, um die Daten in dieser zu speichern. Ferner führt die E/A-Steuerungseinheit eine Interruptverarbeitung auf der CPU 1 aus und empfängt von der CPU 1 ein Interruptsignal.
Der Programmsteuerbereich 2c für das E/A-Steuerungsprogramm für die E/A-Steuerungseinheit 4 enthält verschiedene Programme, die auszuführen sind, um Daten zwischen der E/A- Steuerungseinheit 4 und der Anzeigeeinheit 7, der Platte 9 sowie der Tastatur 8 auszutauschen.
Die oben beschriebene Verarbeitung und der folgende Ablauf sind im wesentlichen derselbe für 2-, 3- und n-dimensionale Raumdaten. Der Dimensionsunterschied erscheint nur als Abweichung im Inhalt der objektiven Raumdaten.
Der Gesamtablauf für die Raumdaten wird nachfolgend gemäß Fig. 2(a) beschrieben.
Das geometrische Verarbeitungsprogramm oder geometrische Daten, wie sie auf der Platte 9 gespeichert sind, werden in einen besonderen Speicherbereich ausgelesen, z. B. den Programmbereich 2e des Speichers 2 für geometrische Verarbeitung, wenn eine vorbestimmte Funktionstaste der Tastatur 7 gedrückt wird. Danach wird, wenn die der Raumdatenerzeugungsverarbeitung zugeordnete Taste auf der Tastatur 8 betätigt wird, die Steuerung von der CPU 1 an die Raumdaten- Verarbeitungseinheit 3 weitergegeben, die ihrerseits auf den Programmspeicherbereich 2b für Raumdatenerzeugung zugreift. Dies führt dazu, daß das Raumdatenerzeugungsprogramm gestartet wird, und wenn ein geometrisches Verarbeitungsprogramm als Ergebnis der Ausführung des Raumdaten-Erzeugungsprogramms ausgeführt wird, werden geometrische Raumdaten erzeugt.
Nachdem die erzeugten Raumdaten in den Speicher 2 eingespeichert sind, arbeitet das Computersystem wie folgt. Die CPU 1 arbeitet so, daß sie ein geometrisches Verarbeitungs-Steuerungsprogramm startet, das es der CPU 1 ermöglicht, als Programmcontroller 10 in Fig. 2(a) zu arbeiten. Ferner dienen das objektive, geometrische Verarbeitungsprogramm und die geometrischen Daten, wie sie jeweils im Programmspeicherbereich 2e für die geometrische Verarbeitung abgelegt sind, als geometrischer Programmspeicher 11 in Fig. 2(a). Jede Anweisung, die im geometrischen Programmspeicher 11 abgelegt ist, wird vom Programmcontroller 10 interpretiert und ausgeführt. Wenn ein entsprechendes geometrisches Verarbeitungsprogramm initiiert wird, arbeitet die Raumdaten-Verarbeitungseinheit 3 in Fig. 1 als Geometriedaten-Umwandlungseinheit 12 abhängig von einer Anweisung von der CPU 1.
Wie oben beschrieben, liest der Programmcontroller 10 das geometrische Verarbeitungsprogramm aus dem Programmspeicher 11 aus, interpretiert dessen Inhalt und führt die dem interpretierten Inhalt zugeordnete Verarbeitung aus. Bei dieser Verarbeitung gibt der Programmcontroller 10 die Steuerung beim Auftreten einer geometrischen Teilverarbeitung an den Geometriedatenumwandlungs-Verarbeitungsabschnitt 12 weiter, z. B. eine Suche für benachbarte geometrische Daten, eine geometrische Überlappungssteuerung oder eine Abtrennung eines spezifizierten Bereichs geometrischer Daten.
Der Geometriedatenumwandlungs-Verarbeitungsabschnitt 12 bestimmt, ob die Anweisung aus dem Programmcontroller 10 eine Raumdatenerzeugungsverarbeitung oder eine Bezugswandlungsverarbeitung für die Raumdaten anzeigt. Abhängig von dieser Ermittlung startet der Umwandlungsverarbeitungsabschnitt 12 das Interpreterprogramm oder das Raumdaten-Erzeugungsprogramm, um dadurch die einschlägige Steuerung zu starten.
Wenn sich herausstellt, daß die Raumdaten-Erzeugungsverarbeitung angefordert ist und das zugehörige Programm für die Verarbeitung ausgewählt und ausgeführt wird, werden die Tabellen 20-22 für charakteristische Punkte, welche Tabellen in den Fig. 4(a) und (b) sowie in Fig. 9 dargestellt sind, für jeden Eckpunkt (oder jeden ausgewählten charakteristischen Punkt) auf Grundlage der geometrischen Daten erstellt, wie sie vom Steuerungsprogramm 10 übertragen werden.
Andererseits führt das Interpreterprogramm die Ausführung eines der Raumdatenanweisung zugeordneten Programms und eine Datenübertragung für das Steuerungsprogramm 10 aus. In Fig. 2(b) ist das Interpreterprogramm im Umwandlungs-Steuerungsprogrammabschnitt 14 und im Zeichnungsprogrammspeicher 15 abgelegt. Der Zeichnungsprogrammspeicher 15 wird dazu verwendet, eine Gruppe von Raumdaten-Umwandlungsprogrammen für verschiedene Suchverarbeitungen zu speichern, die sich auf die Raumdaten beziehen, und für die Erzeugung von Daten, wie sie in einer Teilverarbeitung wie bei einer logischen Verarbeitung einer Geometrie verwendet werden. Z.B. wählt der Umwandlungs-Steuerungsprogrammabschnitt 14 auf Grundlage der Zugriffsadresse eine Gruppe von Raumdaten-Umwandlungsprogrammen aus, die der Verarbeitung aus dem Zeichnungsprogramm-Speicherabschnitt 15 zugeordnet sind.
Das Interpreterprogramm weist die in Fig. 2(b) dargestellte Konfiguration auf. D.h., daß in einem Schritt 1 in Fig. 2(b) bestimmt wird, ob ein Datenwert A (oder eine Anweisung; dies gilt für die folgende Beschreibung) vom Programmcontroller 10 übertragen wurde oder nicht. Wenn dies der Fall ist, führt ein Schritt 2 z. B. die entsprechende Raumdatenverarbeitung aus. In einem Schritt 3 wird ein Interrupt für ein Programm der E/A-Steuerungseinheit (Fig. 2(c)) bewirkt. Wenn sich als Ergebnis im Schritt 1 herausgestellt hat, daß kein Datenwert A übertragen wurde, wird die Verarbeitung eines Schrittes 4 ausgeführt. Der Schritt 4 bestimmt, ob ein Interrupt auftrat oder nicht. In einem Schritt 5 wird ein geometrischer Verarbeitungsdatenwert B, wie er durch die Raumdatenverarbeitung erzeugt wurde, ausgegeben und an das Zeichnungsverarbeitungsprogramm im Programmcontroller 10 oder an den Zeichnungsprogramm-Speicherabschnitt 11 ausgegeben.
Die Raumdatenverarbeitung in Schritt 2 wird wie folgt ausgeführt. Für die zweidimensionale geometrische Verarbeitung wird auf Daten wie auf die in den Fig. 4(a) und 4(b) dargestellten Tabellen 20-21 mit charakteristischen Punkten Bezug genommen, wohingegen für dreidimensionale geometrische Verarbeitung auf Daten wie auf die in Fig. 9(b) gezeigte Tabelle 22 charakteristischer Punkte Bezug genommen wird, um dadurch Information einschließlich der zugeordneten Raumzeigerpaare aufzufinden.
Andererseits arbeitet der Programmcontroller 10 wie folgt. Wenn der Programmcontroller 10 hinsichtlich des Umwandlungs- Steuerungsprogrammabschnitts 14 auf die Zeichnungsdaten-Umwandlungseinheit 12 zugreift, greift ein Schritt 1a in Fig. 2(c) auf eine besondere Adresse im Speicher zu, um den Datenwert A zu erhalten, und dann wird der Datenwert A an die Zeichnungsdaten-Umwandlungseinheit 12 ausgegeben.
Anschließend wird die Steuerung im Schritt 2a an eine Warteschleife übergeben, um ein Interruptsignal von der Zeichnungsdaten-Umwandlungseinheit 12 zu erwarten. Wenn das Interruptsignal von der Umwandlungseinheit 12 erhalten wird, erhält ein Schritt 3a den Zeichnungsverarbeitungsdatenwert B von der Umwandlungseinheit 12 als Eingabedatenwert und gibt den Datenwert B über den Programmcontroller 10 an das Zeichnungsverarbeitungsprogramm des Zeichnungsprogramm-Speicherabschnitts 11 aus. In diesem Fall kann der Zeichnungsverarbeitungsdaten B direkt von der Datenumwandlungseinheit 12 an das Zeichnungsverarbeitungsprogramm weitergeleitet werden.
Die Raumdaten, die die Tabellendaten der charakteristischen Punkte der zweidimensionalen geometrischen Figur von Fig. 4(a) konfigurieren, werden konkret unter Bezugnahme auf die Fig. 5(a) und 5(b) beschrieben.
Es wird angenommen, daß geometrische Figuren A, B, C und D, wie sie in Fig. 5(a) dargestellt sind, beispielsweise auf der Anzeigeeinheit 7 von Fig. 1 dargestellt werden, obwohl keine besondere Beschränkung hierauf besteht. Für die geometrischen Figuren werden geometrische Daten gemäß dem unten beschriebenen Verfahren erzeugt, und eine geeignete Verarbeitung wird abhängig von den erzeugten geometrischen Daten ausgeführt.
Zunächst wird der geometrische Raum, in dem die geometrischen Figuren A und D von Fig. 5(a) angeordnet sind, als in mehrere Unterräume, abhängig von den Figuren A und D angenommen, wie dies in Fig. 5(b) dargestellt ist.
D.h., daß in Fig. 5(b) das X-Y-Koordinatensystem für den geometrischen Raum gilt, der als durch eine Unterteilungslinie Bx unterteilt angenommen wird, die durch eine Ecke jeder Figur geht und rechtwinklig zur X-Achse steht. Obwohl keine Beschränkung auf das Folgende besteht, wird jedoch ein konkaver Raum um jede Ecke (ein Raum, der sich auf der Seite erstreckt, auf der der von den Kanten der Figur eingeschlossene Winkel 180º überschreitet) als Objekt der Raumunterteilung in diesem Fall ausgewählt, um die Anzahl von Unterräumen zu minimieren. Die Raumunterteilung wird nicht für den konvexen Raum ausgeführt (einen Raum, der der Seite zugeordnet ist, auf der der durch die Kanten der Figur eingeschlossene Winkel kleiner als 180º ist).
Wenn das X-Y-Koordinatensystem verwendet wird, wie in Fig. 5(b) dargestellt, muß die Form eines durch ein Raumzeigerpaar SPPi repräsentierten Unterraums nur den folgenden zwei Bedingungen genügen.
(1) Eine Ecke zum Anschließen des SPPi existiert an jeder der Grenzen Bx&supmin; und Bx&spplus; eines Unterraums ωi für X-Werte, bei denen Bx wie Bx&supmin; oder Bx&spplus; eine Linie ist, die entlang der Y-Koordinate ausgehend von der durch SPPi spezifizieren Ecke gezogen ist.
(2) Externe Formlinien By&spplus; und By&supmin; von ωi in Y-Richtung weisen Kanten geometrischer Figuren auf, wobei keine Kante (oder Punkt) innerhalb von ωi existiert.
Fig. 5(b) ist ein Diagramm, das die Unterräume (i = 1 bis n) zeigt, wie sie durch Unterteilung des Raums mit den Kanten der Figuren und den Unterteilungslinien (strichpunktiert) bei den oben angegebenen Bedingungen erhalten werden. Die Unterteilungslinien sind, wie bereits beschrieben, virtuelle Linien und werden demgemäß nicht als Daten behandelt. D.h., daß die Unterteilungslinien jedes Unterraums eingeführt sind, um das Verständnis des Konzeptes der Raumunterteilung zu erleichtern.
In jedem Unterraum dieser Figur existiert immer ein charakteristischer Punkt an jeder entsprechenden Seite in Richtung der X-Achse. Die zwei charakteristischen Punkte zu den beiden Seiten weisen eine Eins-zu-eins-Beziehung hinsichtlich jedes unterteilten Unterraums auf. Ein Zeigerpaar, das das charakteristische Punktepaar anzeigt, kann daher als ein Datenwert verarbeitet werden, der einen Unterraum spezifiziert. Im Diagramm zeigt "Punkt" eine Ecke als charakteristischen Punkt an, und ein Bereich, der mit einer durchgezogenen Linie eingezeichnet ist, zeigt eine Kante einer Figur an.
Wie oben beschrieben, wird in dieser Beschreibung ein Zeigerpaar, das einen Raum ωi (i = 1 bis n) repräsentiert, der innerhalb und außerhalb einer Figur durch Raumunterteilung errichtet ist, als Raumzeigerpaar (SPP) bezeichnet. Das Raumzeigerpaar wird entsprechend dem Unterraum ωi (i = 1 bis n) als SPPi (i = 1 bis n) beziffert.
In Fig. 5(b) ist ein Raumzeigerpaar SPPi als zwei Punkte dargestellt, die durch eine Pfeillinie miteinander verbunden sind. Aus diesem Diagramm ist verständlich, daß jeder Unterraum dem jeweiligen Raumzeigerpaar SPPi entspricht.
Die äußere Form des Unterraums ωi wird z. B. durch die X-Unterteilungslinien Bx&supmin; und Bx&spplus; und die Figurkanten By&supmin; und By&spplus; bestimmt. In diesem Fall ist, wie dies aus dem Diagramm klar erkennbar ist, das Raumzeigerpaar SPP1 so festgelegt, daß es Ecken a&sub1; und a&sub0; der Figuren C bzw. D entspricht. Es existiert jedoch keine Kante, die eine Eins-zu-eins-Beziehung zum Raumzeigerpaar SPP1 hat. Ferner existiert kein Raumzeigerpaar, das eine Eins-zu-eins-Beziehung zur Kante By&supmin; aufweist.
Um diese Schwierigkeit zu überwinden, wird ein Kantenzeiger als Hinweis auf eine Kante festgelegt. D.h., daß eine Kante durch zwei Kantenzeiger repräsentiert wird, die an den Enden der Kante angeordnet sind. Wie das Raumzeigerpaar sind die zwei einer Kante zugeordneten Kantenzeiger so gepaart, daß jede Komponente derselben auf den anderen zeigt. In Fig. 5(b) wird die Kante By&supmin; durch ein Kantenzeigerpaar EPP1 repräsentiert.
Die Suche nach einer externen Form eines Unterraums wird erforderlich, wie dies später beschrieben wird, wenn eine geometrische Figur hinzuzufügen ist oder eine Figurenüberlagerung zu überprüfen ist.
Mindestens ein Anteil der Linien der externen Form eines Unterraums ωi entspricht einem Anteil oder den gesamten Kanten der Figur. Die Außenform wird mit Hilfe eines Programms aufgefunden, das die unten beschriebene Verarbeitung ausführt. Die Beschreibung wird für die Suche gemäß einem Beispiel von ωi gegeben.
Die Suche nach einer Kante der geometrischen Figur wird unter Verwendung einer sequentiellen Suche nach Raum- und Kantenzeigerpaaren ausgeführt, die Ecken der Figur miteinander verbinden, und unter Verwendung einer Bereichsprüfung in X-Richtung, wie sie auszuführen ist, wenn bei der Suche ein Eckenzeiger erhalten wird. Obwohl keine besondere Beschränkung besteht, wird für die Zeigerpaarsuche ein Zeigerpaar entgegen Uhrzeigerrichtung hinsichtlich des Anfangszeigerpaars gesucht, wie es in Fig. 5(b) durch einen Bogen mit Pfeil markiert ist. Dies wird als Rotationssuche bezeichnet.
Im Fall von Fig. 5(b) wird SPP2 durch Rotationssuche gefunden, wobei das Raumzeigerpaar SPP1 als Anfangszeigerpaar gesetzt ist; SPP4 wird durch Rotationssuche erhalten, wobei das Raumzeigerpaar SPP2 als Anfangszeigerpaar gesetzt ist. Entgegen Uhrzeigerrichtung von SPP4 ist ein Kantenzeigerpaar EPP2 angeordnet; demgemäß wird EPP2 durch die Rotationssuche gefunden, wobei SPP4 als Anfangszeigerpaar gesetzt ist. Wenn durch die Suche ein Kantenzeigerpaar erhalten wird, wird die Beziehung zwischen dem durch das erhaltene Kantenzeigerpaar erhaltenen X-Bereich und dem durch das Anfangszeigerpaar SPP1 gekennzeichneten X-Bereich überprüft. Im Fall von Fig. 5(b) unterscheidet sich der EPP2 zugeordnete X-Bereich deutlich von demjenigen, der SPP1 entspricht; demgemäß wird erneut eine Rotationssuche ausgeführt, wobei EPP2 als Anfangszeigerpaar gesetzt ist. Als Ergebnis der Rotationssuche kann ein neues Kantenzeigerpaar EPP2 erhalten werden. Die Beziehung zwischen den jeweils EPP3 und SPP1 zugeordneten X-Bereichen wird erneut überprüft. Als Ergebnis stellt sich heraus, daß die Kante By&spplus;, wie sie durch EPP3 angezeigt wird, ein oberes Ende des Unterraums ωi konfiguriert.
Wie oben beschrieben, wird die Rotationssuche entgegen Uhrzeigerrichtung hinsichtlich des Raumzeigerpaars SPP1 ausgeführt, wie dies durch einen Pfeil mit Bogen dargestellt ist, um sequentiell Zeigerpaare zu suchen; ein aufgefundenes Zeigerpaar wird dahingehend überprüft, ob es im Bereich entlang der X-Richtung des Unterraums vorhanden ist, was es ermöglicht, daß die obere Außenform erhalten wird. D.h. die obere Außenform kann aufgesucht werden.
Ferner kann die untere Außenform dadurch bestimmt werden, daß die Rotationssuche in Uhrzeigerrichtung ausgeführt wird. Wenn der Suchablauf beginnend von einer Kante oder einem Raum ausgeführt wird, kann eine Kante oder ein Raum sequentiell in beliebiger Richtung gesucht werden, d. h. nach oben, unten, links oder rechts, da die Rotationssuche in willkürlicher Richtung ausgeführt werden kann. Wenn ein Punkt nur durch Koordinaten (x, y) spezifiziert ist, wird die Suche in der Richtung auf den durch die Koordinaten (x, y) repräsentierten Punkt hin ausgeführt, wobei ein willkürlicher Raum oder eine Kante als Anfangspunkt gesetzt wird, wodurch schließlich ein Raum mit dem spezifizierten Punkt erreicht wird. Dieser Ablauf erlaubt es, einen Raum zu suchen, der den spezifizierten Punkt enthält. Wenn es erwünscht ist, die Länge der äußeren Form zu erfahren, kann darüber hinaus die Länge leicht dadurch berechnet werden, daß auf die Werte der Koordinaten der Ecken Bezug genommen wird, die den Kanten zugeordnet sind, die die gerade erhaltene äußere Form bilden.
Wie oben beschrieben, kann die Beziehung zwischen einer geometrischen Figur und ihrer benachbarten geometrischen Figur als Satz von Unterräumen repräsentiert werden; demgemäß können Beziehungen zwischen geometrischen Figuren, insbesondere die logische Verarbeitung geometrischer Figuren, das Löschen des Ganzen oder von Teilen einer geometrischen Figur sowie eine Bewegungs-, Änderungs-, Hinzufügungs- und Aktualisierungsverarbeitung einer Figur leicht erzielt werden. Diese geometrische Verarbeitung kann wirkungsvoll unter Verwendung von Attributinformation ausgeführt werden, wie sie später beschrieben wird.
Wie oben beschrieben, kann durch Repräsentieren eines Unterraums durch ein Raumzeigerpaar SPPi eine geometrische Figur zur Verarbeitung unter Verwendung des Raumzeigerpaars SPPi aufgefunden werden, und demgemäß können verschiedene geometrische Datengrößen dadurch erzielt werden, daß die Datenverarbeitung in Einheiten von Unterräumen ausgeführt wird, d. h., daß viele geometrische Datenwerte nicht durch spezielles Ausführen einer umfassenden Datenverarbeitung, die sich auf alle Datenwerte bezieht erhalten werden müssen.
Entsprechend den Ecken oder charakteristischen Punkten einer geometrischen Figur wird eine Eckentabelle erstellt. Die Eckentabelle speichert Raumzeiger, Kantenzeiger und andere, später beschriebene Daten.
Um die oben beschriebene Suche zu realisieren, werden die den Ecken zugeordneten Zeiger als nächstes in vorgegebener Reihenfolge in die Eckentabelle eingetragen, wie dies in den Fig. 4(a) und 4(b) deutlich dargestellt ist. Obwohl keine Beschränkung besteht, werden die Raum- und Eckenzeiger, die von einem Eckpunkt ausgehen, entgegen Uhrzeigerrichtung um die Ecke herum angeordnet. Z.B. wird eine Eckpunkttabelle für einen Eckpunkt a&sub1; in Fig. 5(b) wie folgt gebildet. Z.B. wird zunächst ein Eckenzeiger, der der Eckenzeiger der Ecke a&sub8; ist, zunächst in die Eckpunkttabelle eingetragen; anschließend wird einer der Zeiger des nächsten Zeigerpaars, das entgegen Uhrzeigerrichtung angeordnet ist, d. h. ein Raumzeiger, der den Raumzeiger des Eckpunkts a&sub7; anzeigt, eingetragen. Auf ähnliche Weise werden entgegen Uhrzeigerrichtung angeordnete Zeiger sequentiell in die Eckpunkttabelle eingetragen. D.h., daß in der dem Eckpunkt a&sub1; zugeordneten Eckpunkttabelle sequentiell ein den Raumzeiger auf den Eckpunkt a&sub0; anzeigender Raumzeiger, ein den Eckzeiger auf den Eckpunkt a&sub2; anzeigender Eckzeiger und ein den Eckzeiger auf den Eckpunkt a&sub8; anzeigender Eckzeiger abgespeichert sind.
Bei einer zweidimensionalen geometrischen Figur ist die Eckpunkttabelle vorzugsweise in einer Form konfiguriert, wie sie in den Fig. 4(a) und 4(b) dargestellt ist.
Nachfolgend wird der Inhalt der Tabelle für charakteristische Punkte beschrieben, wie sie in Fig. 4(a) dargestellt ist.
Die Tabelle 20 für charakteristische Punkte wird unter Verwendung eines Codes oder einer Nummer erstellt, die jeden Eckpunkt anzeigt, und sie wird beginnend ab einer vorgegebenen, entsprechenden Adresse in den Speicher 2 eingeschrieben. Bei diesem Beispiel ist die Eckpunkttabelle so ausgebildet, daß sie im Prinzip einen Speicherbereich mit acht Zeilen beinhaltet.
Die Symbole in den Fig. 4(a) und 4(b) weisen jeweils die in der folgenden Tabelle 1 aufgelisteten Bedeutungen auf.
Die Eckpunkttabelle von Fig. 4(a) entspricht dem Eckpunkt a, wie er in den Fig. 4(c) oder (d) dargestellt ist. Jeder Datenwert ist in der Tabelle in der oben angegebenen Reihenfolge abgespeichert. D.h., daß in der Tabelle von Fig. 4(a) den in den Fig. 4(c) oder (d) dargestellten Figuren entsprechende Daten entgegen Uhrzeigerfolge bezüglich der Kante an der Unterseite abgespeichert sind. Die erste Zeile der Tabelle ist die Datenspeicherposition der Figurenbezugskante EP&sub0;, die zweite Zeile ist die Datenspeicherposition des Raumzeigers SP&sub0;&sub1;, die dritte Zeile ist die Datenspeicherposition der nächsten Kante EP&sub1; bei Umdrehung entgegen Uhrzeigerrichtung, die vierte Zeile ist die Datenspeicherposition des Raumzeigers SPr&sub1;&sub0;, die fünfte Zeile ist die Datenspeicherposition eines Raumzeigers SPc&sub1;&sub0; und die sechste Zeile ist die Datenspeicherposition eines Raumzeigers SPL&sub1;&sub0;. Die siebte und die achte Zeile sind Speicherpositionen für Informationen der X- bzw. Y-Koordinate des Eckpunktes a.
Jeder der Raumzeiger SP, SPr, SPc, SPL weist Adressen benachbarter Raumzeiger zu, die mit ihnen zu kombinieren sind, und sie setzen ein Paar zu einem Raumzeigerpaar SPPi zusammen.
Zusätzlich zu Raumzeigern SPi werden Kantenzeiger EPi (i = 1 bis n) zum Bilden von Paaren zu Eckpunkten hin auf beiden Seiten in der Tabelle, wie oben beschrieben abgespeichert. Die Kantenzeiger werden durch EPPi (i = 1 bis n) repräsentiert. Wenn Raumzeigerpaare SPPi und Kantenzeigerpaare EPPi auf diese Weise herangezogen werden, sind im Fall des Eckpunktes a von Fig. 4(c) sechs Zeiger erforderlich und existieren tatsächlich.
Die erste Spalte V/C der Eigenschaftstabelle 20 ist ein Flag zum Entscheiden, ob ein Eck- oder Überkreuzungspunkt in der Figur vorliegt. Wie es aus der oben angegebenen Tabelle 1 erkennbar ist, bedeutet ein Flag "1" einen Eckpunkt, und ein Flag "0" bezeichnet einen Kreuzungspunkt. Die zweite Spalte ART bedeutet einen Code zum Anzeigen der ART, d. h., ob ein Kantenzeigerpaar oder ein Raumzeigerpaar vorliegt. Die dritte Spalte ATR. bedeutet eine Attributbildung und die vierte Spalte ZEIGER zeigt die Adreßposition an, unter der Partner für ein Paar existiert. Wie es aus der Charakteristiktabelle von Fig. 4(b) erkennbar ist, kann ein Raumattribut, z. B. Farbe, eine Datenadresse zum Anzeigen von Information in den Raum einzugebender Daten, Definitionsinformation für den Raum oder dergleichen auch als SA der Tabelle 21 für charakteristische Punkte für einen Eckpunkt angegeben werden, der nicht in X-Richtung liegt. Wenn SA auf diese Weise festgelegt wird, kann beim Suchen des Attributs einer Figur SA leicht unter Bezugnahme auf ATR gesucht werden, wobei es sich um die Attributspalte eines Raumzeigerpaars handelt. Wenn die Größe der Tabelle 21 für charakteristische Punkte für einen Eckpunkt, der nicht in X-Richtung liegt, mit derjenigen der Tabelle 20 für einen Eckpunkt in X-Richtung gleichgemacht wird, enthält die Spalte ZEIGER eines Eckpunktes, der nicht in X-Richtung liegt, natürlich kein Verbindungsobjekt und wird demgemäß leer. Jedoch verwendet dieses System wirkungsvoll die Spalte ZEIGER zum Wiedergeben eines Raumattributs SA und hat daher einen guten Wirkungsgrad bei der Speichernutzung. Da in der Figur kein nicht in X-Richtung liegender Eckpunkt vorhanden ist, wie in Fig. 4(e) dargestellt ist, ist, da keine Position vorhanden ist, an der SA hinzugefügt werden kann, Abhilfe erforderlich, z. B. dahingehend, daß es SA zusätzlich außerhalb der Charakteristikpunkttabelle der Figur angebracht wird, wie in Fig. 4(e) dargestellt. Oder ist es erforderlich, daß ein Eckpunkt, der die Figurenform nicht beeinflußt (Winkel zwischen den Kanten ist 180º) zu den Figurenecken hinzugeführt wird und SA für den hinzugefügten Eckpunkt installiert wird.
Ein besonderes Beispiel des Datenaufbaus der Tabellen 20, 21 für charakteristische Punkte ist in der folgenden Tabelle 2 dargestellt.
Die Inhalte der zweidimensionalen Raumdaten wurden beschrieben. Tabelle 1 SYMBOL Inhalt ADR. Adresse innerhalb der Eckpunkttabelle Untere drei Ziffern 22, 21 und 20 einer Wortadresse V/C V/C = 0; Kreuzungspunkt V/C = 1; Eckpunkt EPi Kantenzeiger zum Zeigen auf eine Kante Raumzeiger zum Zeigen auf einen konvexen Raum (zwischen EPi und EPj) rechts Mitte links Richtung von einem Eckpunkt aus gesehen Zeiger zum Zeigen auf ein Attribut eines Raums Wert der Koordinaten eines Eckpunkts (jeweils vier Byte) ART Code (zwei Bits) zum Anzeigen der ART eines Zeigers (siehe nächste Tabelle) Tabelle 2 Werte Inhalt ADR. ART BIT ATR. Zeigerart Bedeutung von ATR. Geradzahlige Adresse EP für Richtung Kantenattribut Mitte eines konkaven Raumzeigers VERTEX-Attribut Raumattribut Ungeradzahlige (SP)CODE SP eines konvexen Raums Zeigerart; Zusatz zum Zeiger innerhalb einer angrenzenden Seite Nummer der (Index) Index, der einem Eckpunkt entspricht Indexseite
Nachfolgend werden dreidimensionale Raumdaten beschrieben.
Dreidimensionale Raumdaten stellen eine Entwicklung zweidimensionaler Raumdaten dar. Nun wird der dreidimensionale Raum in feste Teilräume unterteilt, die durch ein Raumzeigerpaar SPPi unterteilt werden.
Die Grundeigenschaft dreidimensionaler Raumdaten (oder einer Raumzeigerdatei, SPF) ist dem Fall zweidimensionaler Raumdaten dahingehend ähnlich, daß eine direkte Suche benachbarter/überlappender Räume durch lokale Verarbeitung mit hoher Geschwindigkeit ausgeführt werden kann.
Das bedeutet:
(1) Überlagerungsprüfung durch lokale Verarbeitung und andere dreidimensionale logische Verarbeitung mit hoher Geschwindigkeit;
(2) Anzeige des Beseitigens einer versteckten Oberfläche mit hoher Geschwindigkeit und partielle Korrektur hierzu (partielle Beseitigung einer versteckten Oberfläche);
(3) Ermittlung einer Bewegung und einer Kollision einer Figur im dreidimensionalen Raum und dergleichen kann wirkungsvoll ausgeführt werden.
Da die oben genannte Verarbeitung im wesentlichen eine der zweidimensionalen Verarbeitung ähnliche örtliche Verarbeitung ist, ist Hochgeschwindigkeitsverarbeitung unabhängig vom Maßstab der gesamten Figur möglich und es kann interaktive Onlineverarbeitung ausgeführt werden.
Gemäß einem Beispiel für den Fall des zweidimensionalen Raums, wie er in Fig. 3(b) dargestellt ist, zeigt Fig. 6(a) eine Zeichnung, gemäß der der dreidimensionale Raum als X-Y- Z-Koordinatenraum aufgefaßt wird.
Dreidimensionale Raumunterteilung und ihre Wiedergabe in einem Raumzeigerpaar SPPi wird gemäß den folgenden Regeln ausgeführt.

(1) X-Grenzfläche Bx

In einem prismenähnlichen Raum, wie er durch Projektion der Figur in Z-Richtung auf der positiven und negativen Seite (siehe Fig. 6(a)) erzeugt wird, wird, wenn ein konkaver Winkelraum um die Z-Achse ausgehend vom Eckpunkt in der Mitte (Raum mit einem Winkel größer als 180º bei einem Schnitt mit einer Fläche rechtwinklig zur Z-Achse) ähnlich wie im zweidimensionalen Raum geschnitten wird, der konkave Winkelraum durch die Fläche unterteilt, die durch den Eckpunkt geht, und ist rechtwinklig zur X-Achse und parallel zur X-Z-Ebene (Ebene des Beispiels von Fig. 6(a)), und die unterteilte Fläche wird zur X-Grenzfläche Bx gemacht. Die Erstreckung der Fläche Bx in Y- und Z-Richtung geht zu Linien, die die By-Fläche und die Bz-Fläche schneiden, wie nachfolgend beschrieben.

(2) Y-Grenzfläche By

Wenn die Kante jeder Fläche zum Bilden der Figur in Z-Richtung auf der positiven und negativen Seite projiziert wird, wird die Fläche parallel zur Z-Achse (Ebene im Beispiel von Fig. 6(a)) zur Y-Grenzfläche By des Teilraums gemacht. Die Erstreckung der Fläche By geht bis zur benachbarten Fläche Bz in Z-Richtung (nach oben und unten) und endet dort.

(3) Z-Grenzfläche Bz

Die Grenzfläche Bz als obere Grundfläche oder untere Grundfläche für den Teilraum ist eine reelle Figur neben dem Raum in Z-Richtung.
Wie oben beschrieben, weist der feste Teilraum, der gemäß diesen drei Regeln unterteilt wird, im allgemeinen Prismenform auf, mit einer oberen Grundfläche Bz und einer unteren Grundfläche Bz, die eine obere und untere Fläche der dreidimensionalen Figur sind und rechtwinklig zur X-Y-Ebene stehen.
Auch bei den dreidimensionalen Raumdaten wird ein gemäß den oben angegebenen Regeln unterteilter fester Teilraum ähnlich wie bei den zweidimensionalen Raumdaten durch ein Raumzeigerpaar SPPi ausgedrückt. Das Raumzeigerpaar SPPi erstreckt sich zwischen Eckpunkten am positiven X-Ende und negativen X-Ende des festen Teilraums, in ähnlicher Weise wie beim Fall des zweidimensionalen Raums, wie in Fig. 3(b) und Fig. 5(b) dargestellt. In Fig. 6(a) (i) repräsentiert Ω einen festen Teilraum in drei Dimensionen, entsprechend ω in zwei Dimensionen. Fig. 6(a) (ii) ist eine Ansicht von Fig. 6(a) (i) aus der Richtung Z&spplus;. Fig. 6(b) zeigt eine dreidimensionale feste Figur in Vereinfachung, die Fig. 5(b) entspricht.
Nun muß in drei Dimensionen darauf hingewiesen werden, daß selbst dann, wenn eine Kante einer Figur nicht direkt eine Kante einer anderen Figur schneidet, die Kante der einen Figur durch die Kante einer anderen Figur verdeckt sein kann, wodurch eine Überkreuzung einer Bildabschattung erzeugt werden kann. Fig. 6(c) und (d) veranschaulicht eine Bildabschattungsüberkreuzung.
Fig. 6(c) zeigt ein relativ einfaches Beispiel, bei dem ebene Figuren A und B in fester Anordnung stehen. D.h., daß die Figur B an der Oberseite der Figur A angeordnet ist (positive Seite in Z-Richtung) und ein Teil der Figur B in fester Überkreuzung mit einem Teil der Fig. 1 steht, getrennt in Z-Richtung. Bei diesem Aufbau weist, da Raumunterteilung gemäß den oben angegebenen drei Regeln ausgeführt wird, der Teilraum ΩABL in Festüberkreuzungsposition der Figur B mit der Figur A, d. h. der an der unteren Seite der Figur B und der oberen Seite der Figur A angeordnete Teilraum einen Teil der Fläche auf, die durch die Kante zwischen Punkte C&sub2;'-C&sub1;' in Figur B bestimmt wird. Damit jenes Raumzeigerpaar für den Teilraum ΩABL gesetzt werden kann, muß ein Überkreuzungspunkt, der nicht jeweils in den Figuren A und B existiert, in Betracht gezogen werden. In Fig. 6(c) sind Linien C&sub1;-C&sub1;', C&sub2;-C&sub2;' Überkreuzungslinien einer Bildabschattung. Vier Teilräume stoßen um die Überkreuzungslinien aneinander, und zwei diagonale Räume unter ihnen werden Eckpunkte von in Richtung der X-Achse spitz zulaufenden Räumen, und das Raumzeigerpaar SPPi wird entsprechend diesen festgelegt.
Fig. 6(d) ist eine Ansicht der Figuren von Fig. 6(c) bei Projektion in Richtung der Z-Achse. Aus Fig. 6(d) wird ersichtlich, daß die Raumunterteilung der dreidimensionalen Figur und der Festlegungsaufbau des der Unterteilung entsprechenden Zeigerpaars dem Fall der zweidimensionalen Figur ziemlich ähnlich sind.
Im Fall der dreidimensionalen Figur ist das Vorhandensein von Information zum Spezifizieren von Attributen der Oberflächen der festen Figur zusätzlich zum Raumzeiger SP und dessen Raumzeigerpaar SPPi und zum Kantenzeiger EP und dessen Kantenzeigerpaar EPPi bevorzugt. So wird ein Zeigerpaar für diese Flächen durch ein Flächenzeigerpaar FPPi repräsentiert, das der Tabelle für charakteristische Punkte als neue Information hinzugefügt wird. Das Oberflächenzeigerpaar FPPi wirkt dann, wenn ein Muster auf der Oberfläche eines Körpers vorhanden ist, wie dies in Fig. 7 dargestellt ist.
Nachfolgend werden angesichts dieser Gesichtspunkte unter Bezugnahme auf Fig. 8(a) Raumdaten für eine dreidimensionale Figur A1 gebildet, die denjenigen der zweidimensionalen Figur entsprechen, wie in Fig. 4(c) oder (d) dargestellt. Wenn verschiedene Zeiger in Fig. 8(a) dargestellt werden, wird die Zeichnung deutlich kompliziert. So ist Fig. 8(b) für einfaches Verständnis aufbereitet. Fig. 8(b) zeigt einen Eckpunkt a&sub0; der festen Figur in Fig. 8(a) und einen dazu entsprechend festgelegten Raumzeiger SP, einen Kantenzeiger EP und einen Oberflächenzeiger FP.
Die folgenden Zeiger werden entsprechend dem Eckpunkt a&sub0; festgelegt. D.h., daß ein Raumzeiger SP&sub1; auf ein Raumzeigerpaar SPP&sub5;, das dem Teilraum Ω&sub5; in Fig. 8(a) entspricht, ein Kantenzeiger EP&sub1; auf ein Kantenzeigerpaar EP&sub1;, das der Kante zwischen den Eckpunkten a&sub0;-a&sub1; entspricht, ein Oberflächenzeiger FP&sub1;, der der durch die Eckpunkte a&sub0;, a&sub1; und a&sub2; festgelegten Fläche entspricht, und dergleichen festgelegt werden.
Fig. 9(a) zeigt einen Eckpunkt V einer dreidimensionalen Figur, mit Figurkanten EGi bis EGk, wobei verschiedene Zeiger entsprechend der Kante EGi festgelegt sind. In Fig. 9(a) repräsentiert SP mit einem Index ein Raumzeigerpaar und FP repräsentiert einen Flächenzeiger. LP mit einem Index repräsentiert einen Kantenzeiger und RP repräsentiert einen Flächenzeiger oder einen Raumzeiger. Die Denkweise hinsichtlich der Zeiger LP und RP wird nachfolgend beschrieben.
Im Fall einer zweidimensionalen Figur oder einer dreidimensionalen wird, da örtliche Datenverarbeitung ausgeführt wird, dann, wenn jeweilige Information in der Charakteristikpunkttabelle nicht gemäß einer Regel zum Ermöglichen des Auffindens jedes Raums unter mehreren Teilräumen gebildet wird, die Datenverarbeitung bedeutungslos.
Im Fall der zweidimensionalen Figur können, wie dies oben beschrieben und in den Fig. 4(a) und (b) dargestellt ist, EP und SP um einen Eckpunkt eindeutig durch die Charakteristikpunkttabelle dargestellt werden, wobei verschiedene Zeiger entgegen Uhrzeigerweise festgelegt werden, und Aneinandergrenzen der Kanten im Raum um den Eckpunkt kann vollständig dargestellt werden. Dadurch kann hohe Geschwindigkeit einer Rotationssuche erzielt werden.
Dagegen sind im Fall einer dreidimensionalen Figur, wie dies durch Fig. 9(a) veranschaulicht wird, benachbarte Räume nicht nur links und rechts von einer Kante EGi, sondern auch an deren Ober- und Unterseite vorhanden. Demgemäß kann ein Zusammenhängen des dreidimensionalen Figurenraums nicht nur durch ein Verfahren repräsentiert werden, wie eine Tabelle in eindimensionaler Schleifenform, die für die zweidimensionale Figur festzulegen ist, d. h. durch ein Verfahren, bei dem mehrere Zeiger in vorgegebener Folge in die Tabelle eingeschrieben werden.
Im Fall einer dreidimensionalen Figur ist es daher für eine Raumbestimmungsregel mit Eindeutigkeit erforderlich, eine Beziehung zu errichten, gemäß der jeder feste Teilraum einer festgelegten Information entspricht.
Fig. 9(b) zeigt ein System für eine Vielzwecktabelle für charakteristische Punkte für eine dreidimensionale Figur, das das Problem der Zusammenhängigkeit lösen kann und die Zusammenhängigkeit der Figurenräume repräsentiert, ohne von der Anzahl von Kanten EGi abzuhängen, die vom Eckpunkt erzeugt werden, und ohne von der Anzahl von Räumen oder Flächen abzuhängen, die benachbart zu den Kanten EGi liegen. Die Charakteristikpunkttabelle von Fig. 9(b) weist Datenblöcke auf, die gemäß den Nummern von Kanten EG angeordnet sind, d. h. mehrere Datenblöcke entsprechen einzeln jeder Kante. Kantenzeiger zusammen mit Raumzeigern SP und Flächenzeigern werden für jeden Datenblock gemäß der folgenden Regel festgelegt.
D.h., daß eine Kante als Gegenstand eines EG-Blocks (nachfolgend als "Bezugskante" bezeichnet) und mehrere Raumzeiger und Flächenzeiger benachbart zur Bezugskante notiert werden. Eine Entscheidung wird dahingehend gefällt, daß die mehreren Zeiger links zur Bezugskante oder rechts derselben angeordnet sind. Das Kriterium zum Bestimmen der linken oder rechten Seite ist in diesem Fall relativ und nicht absolut. Obwohl keine besondere Beschränkung besteht, wird davon ausgegangen, daß der Eckpunkt V der wesentliche Gesichtspunkt zur Bezugnahme für die Bezugskante ist, und daß die positive Seite der Z-Achse die Oberseite ist. Gemäß einem solchen Verfahren zum Bestimmen der linken oder rechten Seite werden Raumzeiger SPz und Flächenzeiger FPz, die als an die linke Seite der Bezugskante angrenzend angesehen werden (z: Folge von SPz und FPz, von der Oberseite der Z-Achse her gezählt, Z = 1, 2, . . . ) in Folge in den EG-Block eingeschrieben. Durch Eingabe in den Block EGi kann die Zusammenhängigkeit der Kante EGi mit SPz, FPz an seiner linken Seite oder mit dem Teilraum repräsentiert werden.
Z.B. wird die Tabelle von Fig. 9(a) wie folgt erstellt. Der Bequemlichkeit halber wird die folgende Beschreibung für den Block EGi ausgeführt, der der Kante EGi in Fig. 9(a) entspricht.
Im Block EGi von Fig. 9(b) wird der Kantenzeiger EPi für die Kante EGi von Fig. 9(a) in die erste Zeile eingeschrieben, für die die oberste Adresse i&sub0; des Blocks gegeben ist, obwohl keine besondere Beschränkung hierauf besteht. Selbstverständlich zeigt der Kantenzeiger EPi als Eckpartner auf die Ecke V oder der Kantenzeiger auf den charakteristischen Punkt, gemäß dem Zweck des Zeigerpaars.
In Fig. 9(a) ist ein auf der linken Seite der Kante EGi und überwiegend auf der positiven Seite der Z-Achse angeordneter Teilraum Ω¹, der an der Oberseite der Fläche F² angeordnet ist, wie sie durch die Kanten EGi und EGj festgelegt wird. Demgemäß wird der Raumzeiger SP&ijlig;i für den Teilraum Ω¹ in die zweite Zeile (Adresse i&sub1;) des Blocks EGi eingeschrieben.
Im Fall von Fig. 9(a) ist der nächste Zeiger, der an der Unterseite des Raumzeigers SP&ijlig;¹ angeordnet ist, der Oberflächenzeiger FP&ijlig;² für die Oberfläche F². Demgemäß wird der Oberflächenzeiger FP&ijlig;² in die dritte Zeile (Adresse i&sub2;) der Tabelle EGi eingeschrieben.
Der Teilraum benachbart zur Unterseite des Teilraums Ω¹ ist ein Teilraum Ω³, bei dem die obere Fläche die Fläche F² und die untere Fläche die Fläche F&sup4; ist, wie sie durch die Kanten EGi und EGk festgelegt werden. Demgemäß wird der Raumzeiger SP&ijlig;³ für den Teilraum Ω³ in die vierte Zeile (Adresse i&sub3;) der Tabelle EGi eingeschrieben.
Auf ähnliche Weise wird der Flächenzeiger FPik&sup4; für die Fläche F&sup4; in die fünfte Zeile (Adresse i&sub4;) der Tabelle EGi eingeschrieben. Auch wird ein Raumzeiger SPik&sup5; für den an der Unterseite der Fläche F&sup4; angeordneten Teilraum Ω&sup5; in die sechste Zeile (Adresse i&sub5;) eingeschrieben.
In Fig. 9(a) sind, um zu verhindern, daß die Zeichnung deutlich verkompliziert wird, Zeiger, die an der linken Seite der Kanten EGj, EGk angeordnet wären, nicht dargestellt. Im Block EGj und im Block EGk von Fig. 9(b) sind tatsächlich ein Raumzeiger und ein Flächenzeiger, die den Kanten EGj und EGk entsprechen, eingeschrieben. Jedoch ist kein Symbol für denjenigen Bereich von Fig. 9(b) dargestellt, in dem der Raumzeiger und der Flächenzeiger des Blocks EGj und des Blocks EGk festgelegt sein sollten, und zwar aus dem einfachen Grund, den Kontrast von Fig. 9(a) gegenüber Fig. 9(b) zu erleichtern.
Die oben angegebenen Zeiger werden zusammen mit Zeigern LP, RP in die Blöcke EG von Fig. 9(b) eingetragen. Die Zeiger LP, RP werden so eingetragen, daß sie die Zusammenhangsbeziehung eines Teilraums und einer Fläche, die zur linken Seite der Kante EGi angeordnet sind, wie durch den Raumzeiger SPz und den Flächenzeiger FPz im Block EGi dargestellt, z. B. mit dem Teilraum und der Fläche repräsentieren, die weiter zur linken Seite angeordnet sind, wie dies durch den Raumzeiger und den Flächenzeiger angezeigt wird, die den unten EGj, EGk links von der Kante EGi entsprechen. Kurz gesagt, wird die Zusammenhangsbeziehung durch wechselseitiges Zeigen zwischen dem Innentabellenzeiger LP (Zeiger auf die linke Kante), der zu jedem SPz, FPz gehört, und der auf EP auf der linken Seite zeigt, und dem Innentabellenzeiger RPz (rechter SP oder FP) repräsentiert, der zu jedem EPj, EPk gehört und auf den auf der rechten Seite zeigt.
Die Notwendigkeit des Ausdrückens des Zusammenhangs durch Zeiger LP, RP wird nun beschrieben.
Beim oben angegebenen System, d. h. bei einem System, bei dem die Blöcke EG festgelegt sind, und Kantenzeiger zusammen mit Raumzeigern und Flächenzeigern für jeden Block EG festgelegt sind, kann dreidimensionale Rotationssuche unterstützt werden.
D.h., daß dann, wenn die Eckpunkttabelle unterteilt und für jede Kante eingestellt wird, die Verbindung der Oberfläche eines Teilraums benachbart zu einer Kante nach oben und unten in Richtung der Z-Achse direkt entsprechend der oben angegebenen Anordnung jedes Zeigers innerhalb jedes Blocks gesucht werden kann. Anders gesagt, wird Rotationssuche in Längsrichtung möglich. Im Gegensatz hierzu kann eine Zusammenhangsbeziehung für jeden Teilraum, gesehen von der Oberseite der Z-Achse nach unten, d. h. die Zusammenhangsbeziehung in der Richtung nach links und rechts, d. h. in Querrichtung, nicht direkt gesucht werden. Z.B. sind Raumzeiger und Flächenzeiger, die für den Block EGj entsprechend der Kante EGj von Fig. 9(a) festgelegt sind, Zeiger zum Repräsentieren von Teilräumen benachbart der linken Seite der Kante EGj, wie oben beschrieben, und nicht Zeiger zum Repräsentieren von Teilräumen Ω¹, Ω³ oder dergleichen auf der rechten Seite der Kante EGj. Demgemäß können im wesentlichen Teilräume benachbart zur rechten Seite der Kante EGj nicht durch Zeiger im Block EGj gesucht werden.
Für Rotationssuche in Querrichtung im Fall von drei Dimensionen wird daher Information LP, RP erstellt, so daß die Querbeziehung des Teilraums direkt klargestellt ist.
Die Information von LP, RP spezifiziert die Querbeziehung hinsichtlich des Raumzeigerpaars SPPi und des Flächenzeigerpaars FPPi, bei denen es sich um Raumdaten handelt, und sie wird jeweils in Felder LP, RP des Blocks EG eingeschrieben; LP, RP werden zu einem Zeigerpaar gemacht und dadurch miteinander verbunden, daß in jedem die Adresse angezeigt wird. Die Information LP, RP wird nun als Verknüpfungsinformation bezeichnet, und das Zeigerpaar wird als Verknüpfungszeigerpaar bezeichnet. Da die das Verknüpfungszeigerpaar bildenden Zeiger LP, RP Zeiger sind, die einen Partner innerhalb der Tabelle desselben Eckpunkts anzeigen, können sie als Daten mit wenigen Bits dargestellt werden, z. B. mit einem Byte.
Fig. 9(b) zeigt eine Charakteristikpunkttabelle, wie sie für Eckpunkte in Fig. 9(a) gebildet ist. In Fig. 9(b) zeigen linke Pfeillinien die Verbindung in Querrichtung durch das Verknüpfungszeigerpaar LP-RP an (Verbindung innerhalb einer Fläche in Richtung der X-Y-Ebene).
Im Block EGi von Fig. 9(b) ist der erste Raumzeiger SP&ijlig;¹ in das Zeigerfeld der zweiten Zeile (Adresse i&sub1;) eingeschrieben, und der Verknüpfungsraumzeiger LP¹ ist in das Feld LP desselben eingetragen. Der Verknüpfungsraumzeiger LP¹ zeigt die Adresse innerhalb der Eckpunkttabelle an, unter der der Verknüpfungsraumzeiger RPj¹ zum Bilden eines Paars eingeschrieben ist.
Da sich der Zeiger LP¹ auf den ersten Raumzeiger SP&ijlig;¹ im Block EGi bezieht, ist der linke Raumzeiger RPj¹ in eine Linie eingeschrieben, in die der erste Raumzeiger des Blocks EGj einzuschreiben ist, d. h. die zweite Zeile (Adresse j&sub1;) des Blocks EGj. Der Zeiger RPj¹ zeigt die Adresse innerhalb der Eckpunkttabelle an, unter der der Zeiger LP¹ auf ähnliche Weise wie oben beschrieben eingetragen wird.
Der linke Verknüpfungsflächenzeiger LP² und der linke Raumzeiger LP³ werden in den Block EGi eingeschrieben, wie dies in Fig. 9(b) der Fall ist, entsprechend den Figuren in Fig. 9(a). Der rechte Verknüpfungsflächenzeiger RPj² und der rechte Verknüpfungsraumzeiger RPj³ zum Bilden jeweiliger Paare mit diesen Zeigern LP², LP³ werden in den Block EGj eingeschrieben.
Der rechte Verknüpfungsflächenzeiger RPk² zum Bilden eines Paars mit dem linken Verknüpfungsflächenzeiger LP&sup4; wird zum ersten, rechten Verknüpfungsflächenzeiger gemacht, der in den Block EGk eingeschrieben wird, obwohl keine besondere Beschränkung hierauf besteht. Entsprechend hierzu wird der Zeiger RPk² in diejenige Zeile eingeschrieben, in die der erste Flächenzeiger des Blocks EGk einzuschreiben ist, d. h. in die dritte Zeile (Adresse k&sub2;).
So werden die rechten Verknüpfungszeiger zum Bilden jeweiliger Paare mit linken Verknüpfungszeigern in Folge in jeden Block EG eingeschrieben.
Im allgemeinen sind mehrere SP, FP in Z-Richtung überlappt und sind auch zur rechten Seite einer Kante EG benachbart. Entsprechend solchen SP, RP auf der rechten Seite kann, wenn Zeiger RP auch im Block EP von der Plusseite der Z-Achse angeordnet sind, wie in der Figur dargestellt, ein vollständiger Ausdruck erzielt werden.
In Fig. 9(a) sind rechte Verknüpfungszeiger RPi³ auf den Teilraum benachbart zur rechten Seite der Kante EGi dargestellt. Während RPi¹ und RPi³ Verknüpfungsraumzeiger bedeuten, bedeutet RPi² einen Verknüpfungsflächenzeiger. Dementsprechend werden die Verknüpfungszeiger RPi¹ bis RPi³ der Reihenfolge nach in den Block EGi eingeschrieben, wie dies in Fig. 9(b) dargestellt ist.
Da die Eckpunkttabelle wie oben beschrieben aufgebaut ist, ist die Verknüpfungsinformation LP auf der linken Seite eines Zeigerpaars mit Verknüpfungsinformation RP auf der rechten Seite eines Zeigerpaars zu einem LP-RP-Zeigerpaar verknüpft. In Fig. 9(b) ist die Verbindungsweise in Richtung nach oben und unten, wie durch die Pfeillinien angezeigt, d. h., das Problem, das Zeiger wie RPj¹ bis RPj³ in der Eckpunkttabelle an der Vorderseite oder Rückseite von Zeigern wie LP¹ bis LP³ angeordnet sein sollten, keine wesentliche Schwierigkeit. Eine solche obere und untere Positionsbeziehung von Verknüpfungszeigern in Fig. 9(b) ist nur das Ergebnis der Tatsache, daß Raumdaten von Teilräumen und Flächen, die auf der linken Seite der Grenzfläche in Y-Richtung angeordnet sind, die der Kante EGi entspricht, der Reihenfolge nach von der Aufwärtsrichtung der positiven Seite der Z-Achse repräsentiert werden. Da die Relativposition jedes Blocks EG durch Einschreiben des Verknüpfungszeigerpaars deutlich wird, ist die Folge jedes Blocks EG innerhalb der Eckpunkttabelle keine besondere Schwierigkeit. Demgemäß ändert sich die Oben- und Untenbeziehung, wie sie oben beschrieben wurde, abhängig davon, in welcher Position der Eckpunkttabelle jeder Block EG angeordnet ist. In Fig. 9(b) ist, unabhängig davon, zu welchen Raumdaten eine Verbindungsbeziehung besteht, der Inhalt oder die Art der Raumdaten dadurch spezifiziert, daß auf die Information im Feld ART des Blocks Bezug genommen wird. Anders gesagt, wird erkannt, daß die Raumdaten ein Raumzeigerpaar SPPi oder ein Kantenzeigerpaar EPPi oder ein Flächenzeigerpaar FPPi sind.
Eine solche Tabelle 22 charakteristischer Punkte wird gebildet, wodurch die dreidimensionale Eigenschaftstabelle zusammenhängend in einer Reihenfolge ähnlich derjenigen bei der zweidimensionalen Charakteristikpunkttabelle durchsucht werden kann, und örtliche Verarbeitung eines Teilraums oder einer Fläche wird mit Eindeutigkeit möglich.
In diesem Fall bestehen, wie oben beschrieben, zwei Arten von Suchverfahren. Das eine ist eine Rotationssuche, bei denen Zeigern innerhalb jeder Kante in Aufwärts- und Abwärtsrichtung gefolgt wird, d. h. eine Rotationssuche in Aufwärts- und Abwärtsrichtung der Z-Achse. Das Andere ist eine Rotationssuche, die ausgehend von einem Zeigerpaar für Raumdaten zu einem Querverknüpfungsinformations-Zeigerpaar LP-RP entwickelt wird, d. h. eine Rotationssuche um die Z-Achse in rechtwinklig stehender Richtung. Bei einer tatsächlichen geometrischen Verarbeitung werden diese Suchmethoden kombiniert und verwendet.
Die Eckpunkttabelle oder die Tabelle 22 charakteristischer Punkte für die dreidimensionale Figur des Beispiels von Fig. 9(b) weist einen Aufbau dahingehend auf, daß die Koordinatenwerte (x, y, z) des Eckpunkts in der Kopfposition angeordnet sind und daß weitere Blöcke der Charakteristikpunkttabelle der Reihenfolge nach ausgehend vom Block der Bezugskante EPo angeordnet sind, wie oben beschrieben, obwohl keine besondere Beschränkung hierauf steht.
Fig. 9(c), (d) zeigt ein Beispiel von Raumdaten für den konvexen Eckpunkt V des Polyeders, die in ähnlicher Weise wie bei Fig. (a), (b) entwickelt wurden, d. h. ein Beispiel, das die Beziehung des Raumzeigerpaars SPPi, des Kantenzeigerpaars EPPi und des Zeigerpaars FPPi anzeigt, die für den konvexen Eckpunkt V (Fig. 9(c)) einzustellen sind, wie auch die Beziehung der Charakteristikpunkttabelle hierzu (Fig. 9(d)).
Im Fall der in Fig. 9(c) dargestellten Figur ist der X-Koordinatenwert des Eckpunkts V größer eingestellt als derjenige eines anderen Eckpunkts (nachfolgend als "Eckpunkt V&sub0;" bezeichnet) eines (nicht dargestellten) Partners, der durch die Kante EGo gerichtet ist. D.h. der Eckpunkt V liegt relativ auf der positiven Seite. Der X-Koordinatenwert des Eckpunktes V wird auch kleiner eingestellt als derjenige eines anderen Eckpunkts (nachfolgend als "Eckpunkt V1" bezeichnet) eines (nicht dargestellten) Partners, der durch die Kante EG1 gerichtet ist. Infolgedessen wird ein der Fläche mit den Kanten EGo und EG1 benachbarter Teilraum z. B. durch ein Raumzeigerpaar repräsentiert, das für die Eckpunkte V&sub0; und V&sub1; festzulegen ist. Kein Raumzeiger wird in den Block EGo innerhalb der Eckpunkttabelle für den Eckpunkt V eingetragen. Kein Oberflächenzeiger wird aus ähnlichen Gründen eingetragen.
In der Eckpunkttabelle von Fig. 9(d) wird ein zu leerendes Datenfeld wirkungsvoll benutzt. Z.B. wird ein Datenwert SAo1¹, der ein Raumattribut anzeigt, in das Zeigerfeld in der zweiten Zeile des Blocks EGo eingetragen, und ein Datenwert FAo1², der ein Oberflächenattribut anzeigt, wird in ein ähnliches Feld in der dritten Zeile eingetragen. Welche Daten in ein Zeigerfeld jeder Zeile eingetragen werden sollten, wird durch Unterscheidungsdaten angezeigt, die in das Feld ART eingetragen sind. Der Verknüpfungszeiger RP1¹ in der zweiten Zeile des Blocks EG1 wird durch den Verknüpfungszeiger LP¹ angezeigt, der in das Feld LP in der zweiten Zeile des Blocks EGo eingetragen ist.
Attributdaten für einen Teilraum werden wie folgt gesucht. Z.B. zeigt der in den Block EGo in der Eckpunkttabelle zum Eckpunkt V eingetragene Wert SAo1¹ das Raumattribut eines Raums benachbart zu einer Fläche mit den Kanten EGo und EG1 an, d. h. eines Raums, der für die Eckpunkte Vo und V1 festzeigt ist und durch das Raumzeigerpaar Sppo1¹ der Figur repräsentiert wird. Wenn SPPo1¹ gegeben ist, wird, um sein Raumattribut abzuschätzen, zunächst gemäß der durch den weißen Pfeil ausgehend von SPPo1¹ dargestellten Raumsuche (Suche zum Abschätzen von RPvoz der Figur) ein Zeiger EPo¹ entsprechend der Kante EGo und der Z-Wert von RPvoz (Einzeldatennummer von RPvoz innerhalb des Blocks EG mit EPo¹, Z = 1 in diesem Fall). Nachfolgend wird aus EPo¹ EPo innerhalb der Charakteristikpunkttabelle zum Eckpunkt Vo unter der durch EPo¹ angezeigten Adresse abgeschätzt. Im EPo anzeigenden Block EG wird die Position der Einzelwertnummer, für die die Bedingung Z = 1 vorab eingeschrieben ist, gesucht, wodurch SAo1¹ abgeschätzt wird. Dann wird auf das Feld ART und das Zeigerfeld in derselben Zeile Bezug genommen. Im Ergebnis wird der Attributdatenwert SAo1¹ abgeschätzt. Da in diesem Fall der Attributdatenwert SAo1¹ in das erste Raumzeigerfeld des Blocks EGo eingeschrieben wird, wird angenommen, daß er ein Attribut eines Teilraums an der Oberseite in Z-Richtung benachbart zur linken Seite der Kante EGo anzeigt, d. h. eines Teilraums auf einer Fläche mit den Kanten EGo und EG1.
Attributdaten für eine Fläche können auf ähnliche Weise gesucht werden. Fig. 10(a) zeigt ein Beispiel eines konkaven Raums und einer Fläche (in der Figur sind der Raum und die Oberfläche auf der linken Seite von EPo gesehen von V1 aus, und auch auf der linken Seite von EP1, angeordnet). Fig. 10(b) zeigt ein Beispiel, bei dem der konkave Raum und die Fläche von Fig. 10(a) in einer Charakteristikpunkttabelle repräsentiert sind. Ein Raumzeiger SP oder ein Flächenzeiger FP ist mit Indizes r, c, L für Unterscheidung versehen, auf ähnliche Weise wie im Fall von zwei Dimensionen. Da die Informationsmenge im Block EG zunimmt, wo Zeiger, die einen konkaven Raum und eine Fläche in der Charakteristikpunkttabelle repräsentieren, eingetragen sind, wird, wenn diese Werte für denselben Block EG eingetragen sind, das Feld für den Block EG mit einem festen Teilraum konkaver Form groß.
Demgemäß wird für einen konkaven Block spezifische Information in einem leeren Feld eines nicht konkaven anderen Blocks abgespeichert, und es kann Bezugnahme auf die abgespeicherte Information erfolgen.
In der Tabelle 23 charakteristischer Punkte von Fig. 10(b) wird die Information für den Block EGo im Block EG1 und im Block EG2 abgespeichert, und der abgespeicherte Block ist mit einem Hinweiszeichen * im Feld des Blocks EG1 und des Blocks EG2 markiert. Die Information des Hinweiszeichens * ist eine solche, die ursprünglich im Block EPo abzuspeichern ist, und die abzuspeichernde Position wird durch das Verknüpfungsinformationszeigerpaar cp-rp angezeigt.
Fig. 11(a) zeigt eine Überlappungsfigur, in der Figuren E und F in der zweidimensionalen Figur überlappt sind. Für Hochgeschwindigkeitssuche nach einer Figur mit einer solchen überlappten Figur wird Farbinformation wie "e, f" oder ein Raumattributdatenwert, der einen geometrischen Code bedeutet, wie in Fig. 11(b) dargestellt, zur Charakteristiktabelle hinzugefügt, um ein Raumzeigerpaar zu bilden. Der Raumattributdatenwert wird z. B. in das Feld ATR. der Charakteristikpunkttabelle eingetragen. Genauer gesagt, wird zum Einschreiben mehrerer Raumattributdaten, die der überlappten Figur entsprechen, das Feld ATR. der Charakteristikpunkttabelle in mehrere Raumattributfelder unterteilt, und Raumattributdaten S-ATR werden in jeweiligen Feldern angezeigt. Für die Raumattributdaten können spezielle Felder hinzugefügt werden, die Raumzeigern entsprechen. Auch können für die Raumattributdaten mehrere Bits unter den Bits für das Feld ATR. zugeordnet werden.
In der Charakteristikpunkttabelle oder der Eckpunkttabelle, die einem Figureneckpunkt entspricht, der kein Endpunkt in X-Richtung ist, könnte kein Raumzeiger zum Bilden eines Paars eingeschrieben werden. Anders gesagt, könnte ein leerer Bereich in der Charakteristikpunkttabelle erzeugt werden. So könnten die Raumattributdaten SA im leeren Bereich der Charakteristikpunkttabelle eines Eckpunktes eingetragen werden, der kein Endpunkt in X-Richtung ist. Wenn die Figur jedoch keinen nicht in X-Richtung liegenden Eckpunkt aufweist, wie in Fig. 4(e) dargestellt, kann kein Raumattribut SA eingetragen werden. In diesem Fall muß SA wie in Fig. 4(e) hinzugefügt werden, oder es muß ein Eckpunkt mit einem Winkel von 180º zwischen zwei Kanten ohne Beeinflussung der Figurenform direkt an einer Position auf der Figurenkante hinzugefügt werden, und SA muß in den freien Bereich der Eckpunkttabelle Vo eingetragen werden, die diesem hinzugefügten Eckpunkt entspricht.
Fig. 12(a) zeigt ein Beispiel einer Figur, bei der ein leerer Zeiger ähnlich wie bei Fig. 4(d) erzeugt wird. In Fig. 12(a) kann ein Raumattributdatenwert SA in einen leeren Zeigerbereich eingeschrieben werden. Fig. 12(b) zeigt eine Charakteristikpunkttabelle entsprechend der Figur in Fig. 12(a). Es sollten Koordinatendaten eines in jede Tabelle einzutragenden Eckpunktes ausgegeben werden.
Bei diesem Aufbau kann leicht herausgefunden werden, ob die Figur überlappt oder nicht, wenn durch die Programmverarbeitung auf das Attributfeld ATR. der Charakteristikpunkttabelle zum Eintragen des Raumzeigerpaars Bezug genommen wird.
Fig. 19 zeigt den Fall, bei dem eine Figur T im geometrischen Raum bewegt wird. Beim Bewegen einer solchen Figur wird es eine wesentliche Aufgabe, zu ermitteln, auf welche Figur die Figur T auftreffen wird. Zum Beobachten der Beziehung zu einer benachbarten Figur, um das Zusammenstoßen einer bewegten zweidimensionalen Figur mit einer anderen vorherzusehen, wie dies in Fig. 19 dargestellt ist, ist das vorstehende Raumdatensystem besonders wirkungsvoll. D.h., daß im Fall einer Bewegung die Koordinaten einer sich bewegenden Figur als Funktion der Zeit die Nachbarzustände von Teilräumen leicht unter Verwendung des Raumzeigerpaars gesucht werden können. Wenn ein Zusammenstoßen der Figuren auftritt oder sich der Raumaufteilungsmodus ändert, werden neue Raumdaten für die zuletzt geltenden Raumunterteilungen geschaffen. Demgemäß kann das System leicht dadurch realisiert werden, daß Raumdaten sequentiell gesucht und geschaffen werden.
Es ist zu beachten, daß die obige Situation auch für die Tabelle 22 charakteristischer Punkte in Fig. 9(b) gilt. Das Folgende handelt von überlappenden Figuren in einem dreidimensionalen Raum. Ein Beispiel überlappender Figuren, die zweidimensionalen Figuren entsprechen, wie dies in den Fig. 11(a) und 11(b) dargestellt ist, ist ein Paar Tetraeder, wie in Fig. 13 dargestellt. Die Zeichnungs/Daten-Beziehung für die zweidimensionale Figur in den Fig. 12(a) und 12(b) ist identisch mit einer dreidimensionalen Zeichnung. In diesem Fall ist die Darstellung der geometrischen Beziehung der Zeichnung allerdings komplex und ist hier nicht dargestellt.
Das Hinzufügen einer neuen Figur zum geometrischen Raum und das Entfernen einer Figur aus dem geometrischen Raum bedeutet das Schaffen und Löschen eines neuen Teilraums. Das Folgende beschreibt das Schaffen eines Raumzeigerpaars in einem zweidimensionalen Raum unter Bezugnahme auf die Fig. 14(a), 14(b), 14(c) und 14(d). Zunächst wird die in Fig. 14(a) dargestellte Zeichnung beschrieben. Fig. 14(a) zeigt ein einfachstes Beispiel, bei dem ein Punkt P eingetragen und danach ein Punkt Q eingetragen wird. Anfangs wird ein charakteristischer Punkt P als Bezugspunkt in den geometrischen Raum eingefügt. In diesem Fall wird nur ein einziger Punkt P eingefügt und es existiert kein anderer charakteristischer Punkt. Zum Vereinfachen des Verständnisses der Tabelle von Fig. 14(a) werden die Eigenschaften der Charakteristikpunkttabelle in Verbindung mit Fig. 4(c) und Fig. 12(a) beschrieben.
Wie es zuvor erläutert wurde, wird angenommen, daß ein geometrischer Raum durch charakteristische Punkte, wie Eckpunkte, die Endpunkte in der X-Achse der Zeichnung bilden, in mehrere Teilräume unterteilt wird. In diesem Fall ist, wie dies aus Fig. 4(c) und Fig. 12(a) offensichtlich ist, ein konkaver Raum, der aus zwei Räumen besteht, die unter einem Winkel von 180º oder mehr zwischen zwei Kanten mit den Endpunkten in der X-Achse zusammenstoßen, dadurch definiert, daß drei Raumzeiger eingetragen sind, die von den Eckpunkten ausgehen. Ein Raumzeiger dient für den Teilraum, der sich auf der linken Seite des Eckpunkts zum konkaven Raum erstreckt, wie SPL1,0 in Fig. 4(a) und SPL in Fig. 12(a), und ein anderer Zeiger dient dazu, einen Teilraum wiederzugeben, der benachbart zur linken Seite der Figurenseite P&sub1; besteht und sich vom Eckpunkt zum konkaven Raum erstreckt, wie SPr1,0 und SPr. Ein verbleibender Raumzeiger dient dazu, einen Teilraum wiederzugeben, der in der Mitte des konkaven Raums besteht, wie SPC1,0 und SPc.
In Fig. 14(a) stellt das Einfügen des charakteristischen Punktes P keine Beschränkung dar, sondern der charakteristische Punkt P wird virtuell als zwei Punkte betrachtet. Daher wird der Raumzeiger SPc1 so geschaffen, daß er den Raumzeiger SPc2 in derselben Tabelle für den charakteristischen Punkt P anzeigt, während der Raumzeiger SPc2 so geschaffen wird, .daß er den Raumzeiger SPc1 anzeigt. Auf Grundlage der Idee der oben beschriebenen Raumunterteilung wird ein geometrischer Raum entlang einer imaginären Linie aufgeteilt, die durch den Punkt P geht und sich rechtwinklig zur X-Achse erstreckt, was durch Einfügen des charakteristischen Punktes P erfolgt. Wenn nur der charakteristische Punkt P existiert, stellt ein Raum, dessen X-Achsen-Koordinate negativer als die von P ist, eine Verbindung von X = -∞ bis X = +∞ her, mit dem Ergebnis der Verbindung mit einem Raum, dessen X- Achsen-Koordinate positiver als die von P ist, und es kann angenommen werden, daß beide Räume integriert sind und durch die Kombination von Raumzeigern SPc1 und SPc2 wiedergegeben werden. Der Punkt auf der Zeichnung kann als spezielle Kante betrachtet werden, d. h. als Kante ohne Länge. Daher ist der Kantenzeiger EPo in der Tabelle von Fig. 14 so ausgebildet, daß er seine eigene Adresse anzeigt, obwohl er nicht hierauf beschränkt ist. In diesem Fall wird es deutlich, daß eine Eckpunkttabelle eine Figur durch die Bezugnahme auf den Kantenzeiger EPo als Punkt kennzeichnet, und es ist zu beachten, daß keine inhärente Unterscheidung zwischen den Raumzeigern SPc1 und SPc2 besteht. Die verbleibenden Raumzeiger können dadurch behandelt werden, daß z. B. ein Raumattribut SA eingeschrieben wird, das eine Leerstelle ausdrückt.
Anschließend wird, wenn der Charakteristikpunkt Q als zweiter Charakteristikpunkt eingeführt wird, die oben genannte Schleife für den Charakteristikpunkt P freigegeben, und ein Raumzeigerpaar wird gegen den Charakteristikpunkt Q gebildet.
Das Raumzeigerpaar für die Charakteristikpunkte P und Q folgend auf das Hinzufügen von Q wird wie folgt geschaffen. Die Speicheradresse, unter der die Raumzeigerinformation (rechter Raumzeiger SPc2) für den Charakteristikpunkt Q eingespeichert ist, wird in die Position des Raumzeigers SP (linker Raumzeiger SPc1) entsprechend der Charakteristikpunkttabelle für den Charakteristikpunkt P eingetragen, und die Adresse, unter der die Raumzeigerinformation (linker Raumzeiger SPc1) für den Charakteristikpunkt P abgespeichert wird, wird in die Position des Raumzeigers SP (rechter Raumzeiger SPc2) eingetragen, der der Charakteristikpunkttabelle für den Charakteristikpunkt Q entspricht. Dementsprechend wird das Raumzeigerpaar für den Teilraum zwischen den Charakteristikpunkten Q und P erstellt. Auf ähnliche Weise wird hinsichtlich der Eintragung des Raumzeigerpaars für den Charakteristikpunkt P außerhalb des Charakteristikpunkts Q die Speicheradresse, unter der die Raumzeigerinformation (linker Raumzeiger SPc1) für den Charakteristikpunkt Q abgespeichert ist, in den Ort des Raumzeigers SP (rechtes Raumzeigerpaar SPc2) eingetragen, die der Charakteristikpunkttabelle für den Charakteristikpunkt P entspricht, und die Adresse, unter der die Raumzeigerinformation (rechter Raumzeiger SPc2) für den Charakteristikpunkt P abgespeichert ist, wird am Ort des Raumzeigers SP (linker Raumzeiger SPc1) eingetragen, der der Charakteristikpunkttabelle für den Charakteristikpunkt Q entspricht.
Nachfolgend wird die Erzeugung eines Raumzeigerpaars auf Grundlage des Bezugscharakteristikpunkts (der nachfolgend einfach als "Bezugspunkt" bezeichnet wird) beschrieben. Wie in Fig. 14(b) dargestellt, beinhalten, wenn der erste und der zweite Bezugspunkt auf dem Ursprung und einem unendlich entfernten Punkt (x = +∞, y = +∞) im X-Y-Koordinatensystem angeordnet werden, andere Charakteristikpunkte außer dein zunächst eingegebenen Charakteristikpunkt P lediglich den ersten Bezugspunkt O und den zweiten Bezugspunkt ∞. Demgemäß wird das Raumzeigerpaar zwischen diesen beiden Punkten ausgebildet. Das Raumzeigerpaar wird wie folgt erzeugt. Das Raumzeigerpaar für den ersten Bezugspunkt O für den charakteristischen Punkt P wird auf solche Weise erzeugt, daß die die Raumzeigerinformation für den ersten Bezugspunkt O enthaltende Adresse am Ort desjenigen Raumzeigers SP abgespeichert wird, der der Charakteristikpunkttabelle für den Charakteristikpunkt P entspricht, während die die Raumzeigerinformation für den Charakteristikpunkt P enthaltende Adresse am Ort des Raumzeigers SP abgespeichert wird, der der Charakteristikpunkttabelle für den ersten Bezugspunkt O entspricht. Auf ähnliche Weise wird das Raumzeigerpaar für den zweiten Bezugspunkt ∞ für den Charakteristikpunkt P auf solche Weise erzeugt, daß die die Raumzeigerinformation für den zweiten Bezugspunkt ∞ enthaltende Adresse am Ort des Raumzeigers SP entsprechend der Charakteristikpunkttabelle für den Charakteristikpunkt P eingetragen wird, während die die Raumzeigerinformation für den Charakteristikpunkt P am Ort des Raumzeigers SP entsprechend der Charakteristikpunkttabelle für den zweiten Bezugspunkt ∞ eingetragen wird. Die Charakteristikpunkttabelle für die anfänglichen Charakteristikpunkte wird so vervollständigt und infolgedessen wird das Raumzeigerpaar erzeugt.
Wenn angenommen wird, daß der Charakteristikpunkt Q als zweiter Charakteristikpunkt zwischen dem Ursprung und dem ersten Charakteristikpunkt P eingefügt wird, sind auf der X-Achse existierende Punkte, die positiver sind als der Charakteristikpunkt P, der Charakteristikpunkt Q und der zweite Bezugspunkt ∞. Der Charakteristikpunkt Q ist zwischen dem ersten Bezugspunkt, d. h. dem Ursprung, und dem Charakteristikpunkt P angeordnet. Der auf der X-Achse negativere Raumzeiger des Charakteristikpunkts P ist mit dem Raumzeiger für den Charakteristikpunkt Q gepaart. D.h., daß die die Raumzeigerinformation für den Charakteristikpunkt Q enthaltende Adresse am Ort des der Charakteristikpunkttabelle für die Charakteristikpunkttabelle für den Charakteristikpunkt P entsprechenden Ort abgespeichert wird, während die die Raumzeigerinformation für den Charakteristikpunkt P am Ort des der Charakteristikpunkttabelle für den Charakteristikpunkt Q entsprechenden Raumzeigers SP abgespeichert wird. In diesem Fall wird der Raumzeiger auf der Seite +∞ nicht verändert. Auf ähnliche Weise wird das Raumzeigerpaar für den ersten Bezugspunkt O des Charakteristikpunkts Q dadurch erzeugt, daß die Raumzeigerinformation für den ersten Bezugspunkt O unter der Position des der Charakteristikpunkttabelle für den Charakteristikpunkt Q entsprechenden Raumzeigers abgespeichert wird, während die die Raumzeigerinformation für den ersten Bezugspunkt 0 enthaltende Adresse am Ort des der Charakteristikpunkttabelle für den Charakteristikpunkt Q entsprechenden Raumzeigers abgespeichert wird. Dies ist die Methode zum anfänglichen Eingeben von Punktdaten in die graphische Datenbasis, und ein ähnliches Verfahren ist für den Fall anwendbar, bei dem mehrere Zeichnungen bereits in der Graphikdatenbasis abgespeichert sind.
Das Eintragen einer Punktfigur wird dadurch realisiert, daß der geometrische Raum sukzessive abhängig von eingegebenen Punkten unterteilt wird, wie oben beschrieben. Im Gegensatz hierzu wird es beim Eintragen von Figurenkanten erforderlich, die Beziehung zwischen neu einzutragenden Figurenkanten und bereits in den geometrischen Raum und seine Teilräume eingetragenen Figurenkanten klarzustellen. Das geometrische Verarbeitungssystem beinhaltet ein neues Verarbeitungsverfahren für solche neuen Figurenkanten. Kurz gesagt, wird das Eintragen von Figurenkantendaten dadurch realisiert, daß Anfangspunkte eingegeben werden und dann geeignete Linien entlang zu enthaltenden Kanten dadurch gezogen werden, daß auf diese Punkte Bezug genommen wird (diese werden nachfolgend als "Eingabelinien" bezeichnet). Wenn die Eingabelinien gezogen werden, treten Änderungen in der Topologie der Unterteilung der Eingabelinien und der Topologie von Teilräumen auf. Während dieser Änderungen verändert sich die Verbindungsbeziehung für die Kantenzeigen und die Raumzeiger. Punkte an denen Änderungen in der Verbindungsbeziehung der Kantenzeiger und der Raumzeiger auftreten, werden in der folgenden Diskussion als "Ereignisse" bezeichnet.
Das Folgende beschreibt, zunächst für den zweidimensionalen Fall, das Verfahren zum Eingeben von Figurenkanten auf Grundlage von Punkten, die mit dem vorstehenden Punktdaten- Eingabeverfahren eingegeben wurden. Zunächst wird die Eingabe einer Figur (die nachfolgend als Figur A bezeichnet wird) unter Bezugnahme auf die Fig. 14(c) und 14(d) beschrieben. Zum Eingeben der Figur A wird ein Eckpunkt ao durch die oben beschriebene Eingabeverarbeitung für Punkte eingegeben. Danach wird, wie dies unter (I)-(VI) von Fig. 14(d) erkennbar ist, eine Polygonlinie aot ausgehend vom Eckpunkt ao entlang den Kanten der Figur A gezogen. Das Ausdehnen der Linie aot erfordert Änderungen der räumlichen Aufteilung (genannt "Ereignis Ej"); das Raumzeigerpaar SPPi wird darauffolgend erneuert. Nachdem die Figur A entlang ihrer Kanten abgerundet wurde, werden Raumattribute einschließlich des Figurennamens und der Farbe der Figur A zum Raumzeigerpaar SPPi für den Raum innerhalb der Figur A hinzugefügt. So wird die Eingabe der Figur A abgeschlossen.
Der obige Ablauf wird als "Entwicklungsprozeß" für die Figur A bezeichnet. Ereignisse, die durch Erstreckung von aot hervorgerufen werden, treten im wesentlichen nur dann auf, wenn die Spitze t der sich erstreckenden aot durch die Grenze Bx oder By des Raumes bricht. Dabei erfordert das Raumzeigerpaar SPPi nur eine Zwischenwartung.
Mögliche Typen von Ereignissen sind das oben angegebene Durchbrechen durch die Grenzen Bx und By durch aot und Verarbeitungen am Start- und am Endpunkt von aot, wie in Fig. 14 (c) aufgelistet.
Das Ereignisverarbeitungsprogramm ist so ausgebildet, daß es den Typ eines anschließend auftretenden Ereignisses identifiziert und die Verbindung von Zeigern abhängig vom festgestellten Ergebnis verändert. Um die Handhabung durch Verringern der Typen von Ereignissen zu vereinfachen, besteht ein mögliches Verfahren darin, die Erstreckung von aot in einer Richtung dadurch zu beschränken, daß alle Kanten der zusätzlichen Figur in Polygonlinien in Richtung von X&supmin; nach X&spplus; zu Beginn aufgelöst werden, wie dies in Fig. 14(d) dargestellt ist.
Der Entwicklungsprozeß ist ein lokaler Prozeß, der auf einen Raum um die Eingabefigurenkanten (Erstreckungsprozeß für aot) und das Innere der Eingabefigur (Hinzufügen von Raumattributen) beschränkt ist, wie im Fall der vorstehend genannten Rotationssuche und dergleichen. Dabei wird erwartet, daß die Wartungszeit für die Raumzeigerdatei (SPF) um o (Nº) neben der Geschwindigkeitszunahme der Punkteingabe (Leitpunktprozeß) verbessert wird, was später unter Verwendung der Fig. 16(a) und 16(b) beschrieben wird, und es wird erwartet, daß sich die Anfangserzeugungszeit für die gesamte SPF um o (N) verbessert, vorausgesetzt, daß Spezialfälle außer Betracht bleiben können und die Anzahl geometrischer Räume, denen Raumattribute innerhalb der Eingabefigur zugeordnet werden, unabhängig von der Gesamtzahl N von Ecken ist.
Infolgedessen wird, obwohl die obigen Bedingungen auferlegt werden, erwartet, daß die SPF eine hochentwickelte graphische Datenbasis ist, die sowohl für Online- als auch Stapelverarbeitungen geeignet ist.
Fig. 14(e) zeigt als Flußdiagramm ein Beispiel für die Verarbeitung zum Bilden von Raumdaten. Das Flußdiagramm zeigt die Verarbeitung von konvexe oder charakteristische Punkte einer Figur, wie sie anfangs beim Eingeben geographischer Daten-ausgeführt wird. Die Verarbeitung für die Kanten der Figur wird später in Verbindung mit dem Flußdiagramm von Fig. 14(f) erläutert.
Im Verarbeitungsschritt STPA1 in Fig. 14(e) werden Koordinaten Xa und Ya eines konvexen Objekts ao und Attributdaten für die Figur in die Eingabedatenliste eingetragen. Unter Bezugnahme auf die Eingabedatenliste wird ein Datenwert zum Anzeigen unverarbeiteter Eckpunkte, die dem Eckpunkt ao entsprechen, in die anhängige Eckpunkttabelle eingetragen.
In einem auf den Schritt STPA1 folgenden Schritt STPA2 wird der Beginn der Punktdatenverarbeitung angewiesen.
In Schritten STPA3 und STPA4 wird derjenige Teilraum gesucht, in dem der Gegenstandseckpunkt angeordnet ist. D.h., daß der Schritt STPA3 nach einem Raumzeigerpaar SPPj sucht, das die X-Koordinate Xa des Eckpunktes a0 beinhaltet. Die Suche wird dadurch ausgeführt, daß mit einem geeigneten Raumzeigerpaar begonnen wird und Raumzeigerpaaren nahe Xa gefolgt wird. Das Folgende beschreibt den Suchprozeß unter Verwendung der Eckpunkttabellen der Fig. 4(a) und 4(b) und des Beispiels des in Fig. 5(b) gezeigten geometrischen Raums genauer.
Anfangs wird auf den ersten Raumzeiger in der ersten Eckpunkttabelle entsprechend dem Startzeigerpaar Bezug genommen. Unter Verwendung dieses Raumzeigerpaars wird das der zweiten Eckpunkttabelle entsprechende Raumzeigerpaar (das im folgenden als "zweiter Raumzeigerzeiger" bezeichnet wird) direkt gesucht. Es erfolgt Bezugnahme auf das X-Koordinaten- Feld der zweiten Eckpunkttabelle, in dem der zweite Raumzeiger eingetragen wurde. Die X-Koordinate in der ersten Eckpunkttabelle wird mit dem Gegenstück Xa in der zweiten Eckpunkttabelle verglichen. Wenn Xa innerhalb des durch die X- Koordinaten in der ersten und der zweiten Eckpunkttabelle festgelegten Bereichs liegt, endet die Verarbeitung des Schritts STPA3. Wenn andererseits Xa außerhalb des durch die X-Koordinaten in der ersten und der zweiten Eckpunkttabelle festgelegten Bereichs liegt, läuft die folgende Verarbeitung ab. D.h., daß eine Eckpunkttabelle mit einem X-Koordinaten- Datenwert näher an Xa in der ersten und zweiten Eckpunkttabelle ausgewählt wird. In der ausgewählten Eckpunkttabelle wird ein neuer Raumzeiger ausgewählt und dazu verwendet, eine Bezugnahme zu einem Raumzeiger in einer anderen Eckpunkttabelle vorzunehmen. Ein ähnlicher Prozeß wird wiederholt und schließlich wird der Raumzeiger SPPj, der Xa beinhaltet, aufgesucht. Um die Suche im Schritt STPA3 schneller zu machen, muß ein Raumzeiger nahe Xa zu Beginn ausgewählt werden. Ein wünschenswertes Verfahren zum anfänglichen Einstellen eines geeigneten Zeigers verwendet eine Leitpunkt-Adreßtabelle, wie in Fig. 16(a) und 16(b) dargestellt; dieses Verfahren wird später im einzelnen erläutert.
Nachdem das Raumzeigerpaar SPPj im Schritt STPA3 gesucht wurde, bestimmt der folgende Schritt STPA4 die Außenform des Teilraums, wie er durch SPPj ausgedrückt wird. Unter den Faktoren für die Außenform wird die X-Grenze durch die X-Koordinate in der Eckpunkttabelle angezeigt, in die die Raumzeigerpaare eingetragen sind. Die Außenform in Y-Richtung wird durch Rotationssuche erhalten, wie in Fig. 5(b) dargestellt. Es besteht die folgende Beziehung zwischen der Rotationssuche und den Eckpunkttabellen, wie in den Fig. 4(a) und 4(b) dargestellt. In einer Eckpunkttabelle sind Raumzeiger und Kantenzeiger, die sich auf einen Eckpunkt einer Figur beziehen, entgegen Uhrzeigerichtung um den Eckpunkt herum eingetragen. Demgemäß entspricht eine Rotationssuche entgegen Uhrzeigerrichtung einer Bezugnahme auf eine Zeile, die benachbart zu einer aktuellen Zeile in jeder Eckpunkttabelle liegt. Wenn z. B. ein Raumzeiger SPc aus der fünften Zeile in der Tabelle, wie in Fig. 4(a) dargestellt, als Ergebnis einer Suche nach SPPj im Schritt STPA3 erhalten wird, erfolgt Bezugnahme auf den Zeiger SPL1,0 in der sechsten Zeile derselben Tabelle durch Realisierung einer Rotationssuche entgegen Uhrzeigerrichtung. Der Zeiger SPL1,0 wird dazu verwendet, auf einen Zeiger in einer anderen Eckpunkttabelle (zweite Eckpunkttabelle) Bezug zu nehmen, die durch den Zeiger SPL1,0 angezeigt wird. Auf ähnliche Weise wird in der zweiten Eckpunkttabelle auf die Zeile benachbart zu dem Zeiger Bezug genommen, auf den Bezugnahme erfolgte.
Nachdem ein Kantenzeiger aufgesucht wurde, wird dieser dazu verwendet, die Kanten der Figur zu erhalten. D.h., daß auf den Kantenzeiger Bezug genommen wird, um den entsprechenden Kantenzeiger zu erhalten, und anschließend wird durch Bezugnahme auf die X- und Y-Koordinaten in den zwei Eckpunkttabellen, in die die zwei Kantenzeiger eingetragen sind, die Kante für die Figur erhalten. Wenn der X-Bereich der durch die zwei Kantenzeiger klargelegten Kante innerhalb des Bereichs des Teilraums liegt, wie er durch das Objekt-Raum- Zeigerpaar SPPj klargelegt ist, zeigt die erhaltene Kante die Außenformkante in positiver Y-Richtung im zu bestimmenden Teilraum an. Andernfalls erfolgt Bezugnahme auf einen Zeiger in der Zeile benachbart zum neu erhaltenen Kantenzeiger. Eine ähnliche Suche und bestimmende Abläufe werden wiederholt, bis die Außenformkante in positiver Y-Richtung für den geometrischen Objektraum erhalten ist.
Nachdem die Außenform des durch den Raumzeiger SPPj wiedergegebenen Teilraums im Schritt StPA4 erhalten wurde, geht die Folge zum nächsten Prozeß (Schritt STPA5) über. Der Schritt STPA5 testet, ob der Eckpunkt (Xa, Ya), wie er einzutragen ist, innerhalb des im Schritt STPA4 erhaltenen Teilraums liegt. Wenn festgestellt wird, daß der Eckpunkt außerhalb des Bereichs liegt, wird der Prozeß in einem Schritt STPA6 ausgeführt. Der Schritt STPA6 dient dazu, nach einem näher beim Eckpunkt (Xa, Ya) liegenden Teilraum zu suchen (Suche in Y-Richtung), der unter Teilräumen einzutragen ist, die benachbart über oder unter dem zuvor erhaltenen Teilraum liegen. Beim Suchablauf wird eine Bezugnahme auf Raumzeiger realisiert, die in den Zeilen über und unter dem zuvor erhaltenen Raumzeiger liegen, und es wird eine Bestimmung ähnlich zu der oben angegebenen ausgeführt. Dieser Bezugnahme- und Bestimmungsprozeß ist identisch zum zuvor angegebenen, und eine detaillierte Beschreibung desselben wird hier weggelassen.
Folgend auf die Suche in Y-Richtung im Schritt STPA6 werden die Prozesse der Schritte STPA4 und STPA5 erneut ausgeführt. Die Schritte STPA4 bis STPA6 finden zyklisch so lange statt, bis der zu erhaltende Teilraum den Eckpunkt (Xa, Ya) enthält.
Nachdem der den Eckpunkt (Xa, Ya) enthaltende Teilraum durch die obigen Schritte erhalten wurde, geht die Folge zum nächsten Schritt STPA7 über. Der Schritt STPA7 erstellt Raumdaten, so daß der vorab erhaltene Teilraum durch den Eckpunkt (Xa, Ya) unterteilt wird. D.h., daß der Raumzeiger, der einen SPPj bildenden Raumzeiger anzeigt, in ein Raumzeigerfeld eingetragen wird, wie in die zweite Zeile der Eckpunkttabelle für den Eckpunkt (Xa, Ya), und ein Raumzeiger, der einen anderen SPPj bildenden Raumzeiger anzeigt, in ein Raumzeigerfeld eingetragen wird, wie in die vierte Zeile der Eckpunkttabelle. SPPj bildende Raumzeiger werden so modifiziert, daß sie Raumzeiger in der Eckpunkttabelle für den Eckpunkt (Xa, Ya) anzeigen. Nach dem Schritt STPA7 werden Daten, die die Erzeugung der Eckpunkttabelle für den Eckpunkt a0 anzeigen, aus der anhängigen Eckpunkttabelle gelöscht, obwohl dies in der Figur nicht dargestellt ist. Danach wird überprüft, ob in der anhängigen Eckpunkttabelle Daten verbleiben, die "nicht verarbeitet" anzeigen. Wenn eine Zeichnung nur aus Punkten besteht, enthält die anhängige Eckpunkttabelle nach dem obigen Löschprozeß Leerstellen und der Figureneingabeprozeß wird abgeschlossen.
Fig. 14(f) zeigt ein Flußdiagramm für die Verarbeitung zum Bilden von Kantendaten, d. h. für den Entwicklungsprozeß. Der Prozeß von Fig. 14(f) ist so ausgebildet, daß er eine Eckpunkttabelle für einen der Eckpunkte einer Figur erstellt und dann Kanten ausgehend von diesem Eckpunkt erstreckt, obwohl keine Beschränkung hierauf besteht. Dieses Verfahren ermöglicht es, einen Prozeß im Vergleich zu einem Verfahren zum Erzeugen von Eckpunkttabellen für alle Eckpunkte durch den Prozeß, wie er in Fig. 14(e) dargestellt ist, zu beschleunigen.
Anfangs wird in einem Schritt STPB1 der in Fig. 14(e) dargestellte Prozeß ausgeführt und anschließend wird die Eckpunkttabelle für den ersten Eckpunkt ao einer Figur erzeugt.
In einem nächsten Schritt STPB2 erfolgt eine Bezugnahme auf die anhängige Eckpunkttabelle für den Eckpunkt ao und es wird überprüft, ob Daten vorhanden sind oder fehlen, die nicht verarbeitete Daten anzeigen. Wenn der Eckpunkt ao eine Punktfigur anzeigt, führt das in Verbindung mit Fig. 14(e) erläuterte Löschen zum nicht Vorhandensein von Daten, die nicht verarbeitete Daten anzeigen, und in diesem Fall endet der Prozeß. Wenn der Eckpunkt ao einer von mehreren Eckpunkten einer Figur ist, verbleiben Daten, die die Ausbildung von Kanten zwischen den Eckpunkten anzeigen selbst nach dem oben angegebenem Löschvorgang in der anhängigen Eckpunkttabelle; in diesem Fall wird der nächste Schritt STPB3 ausgeführt. Der Schritt STPB3 nimmt auf den nächsten Eckpunkt ai Bezug, wie er durch die anhängige Eckpunkttabelle angezeigt wird.
In einem Schritt STPB4 wird eine Hilfseckpunkttabelle erstellt, um einen Hilfseckpunkt anzuzeigen, zu dem eine Linie ait, wie in Fig. 14(d) dargestellt, zwischen dem ersten ausgewählten Eckpunkt ao und dem nächsten Eckpunkt a1 gezogen wird. In diesem Fall wird die Linie ait zwischen den Eckpunkten ao und t erstellt, und daher werden ein Kantenzeigerpaar und ein Raumzeigerpaar in den Eckpunkttabellen dieser Eckpunkte eingetragen. Der im Schritt STPB4 erstellte Eckpunkt t wird so erzeugt, daß er im wesentlichen dieselben X- und Y-Koordinaten wie der Eckpunkt ao aufweist, obwohl keine Beschränkung hierauf besteht. D.h., daß die Linie ait so erstellt wird, daß sie eine Länge aufweist, die im wesentlichen null entspricht.
Dem Schritt STPB4 folgt ein Schritt STPB5. Im Schritt STPB5 wird der Hilfseckpunkt t zum beabsichtigten Eckpunkt ai um eine beabsichtigte Entfernung auf den Koordinaten bewegt. D.h., daß die X- und Y-Koordinatenfelder in der Hilfseckpunkttabelle modifiziert werden.
Der folgende Schritt StPB6 überprüft die Erzeugung eines Ereignisses Ej. Das Erzeugen eines Ereignisses Ej kann dem Grunde nach durch den Test überprüft werden, ob der bewegte Hilfseckpunkt t die X&supmin;- oder X&spplus;-Grenze überquert hat, wie sie abhängig von den vorhandenen Eckpunkten oder Kanten der vorhandenen Figur erzeugt werden, wie dies aus den Fig. 14(c) und 14(d) offensichtlich ist.
Nach Ermittlung einer Ereigniserzeugung durch den Schritt StPB6 wird die Ereignisverarbeitung im Schritt StPB7 realisiert. Die Ereignisverarbeitung im Schritt StPB7 dient dazu, verschiedene Zeiger in der Hilfseckpunkttabelle zu verbinden. Dieser Prozeß ist im wesentlichen aus der obigen Beschreibung zu den Fig. 14(c) und 14(d) ersichtlich und seine Erläuterung wird hier weggelassen.
Folgend auf die Schritte STPB6 oder STPB7 findet ein Bestimmungsprozeß in einem Schritt STPB8 statt, in dem überprüft wird, ob der Hilfseckpunkt t bis zum beabsichtigten Eckpunkt ai hochbewegt wurde. Wenn das Testergebnis negativ ist, wird eine Reihe von Prozessen beginnend mit STPB5 erneut ausgeführt. Sobald der Hilfseckpunkt t mit dem Eckpunkt ai zusammenfällt, wie im Schritt STPB8 bestimmt, geht die Folge zum nächsten Schritt STPB9 über. Im Schritt STPB9 wird, wenn sich herausstellt, daß der Eckpunkt ai ein unverarbeiteter Eckpunkt ist, der Anzeigedatenwert für den Eckpunkt ai in die anhängige Eckpunkttabelle eingetragen und danach geht die Folge zum Schritt STPB10 über. Im Schritt STPB10 wird eine Eckpunkttabelle für den Eckpunkt ai bereitgestellt. Dies kann einfach erfolgen, da der für den Eckpunkt ai einzutragende Zeigerwert vorab in die Eckpunkttabelle für den Hilfseckpunkt t eingetragen ist. Der folgende Schritt STPB11 löscht Daten, die die Ausbildung einer Kante zwischen den Eckpunkten ao und ai in der anhängigen Eckpunkttabelle anzeigen.
Im folgenden Schritt STPB12 wird auf die anhängige Eckpunkttabelle Bezug genommen, um zu überprüfen, ob Daten vorhanden sind oder nicht, die das Vorhandensein oder Fehlen in ihr vorhandener unverarbeiteter Daten anzeigen. Wenn eine Zeichnung nur aus einer Linie zwischen den Eckpunkten ao und ai besteht, ist nach dem oben angegebenen Löschvorgang kein Anzeigedatenwert mehr in der anhängigen Eckpunkttabelle vorhanden und daher schließt die Verarbeitung ab. Im anderen Fall, bei dem die Zeichnung eine Polygonfigur ist, sind mehrere Kanten für jeden der Eckpunkte ao und ai vorhanden. In diesem Fall sind noch Daten, die unverarbeitete Daten anzeigen, in der anhängigen Eckpunkttabelle vorhanden, und demgemäß wird der folgende Schritt STPB13 ausgeführt.
Der Schritt STPB13 nimmt Bezug auf Daten, die unverarbeitete Kanten in der anhängigen Eckpunkttabelle anzeigen. Unter Eckpunkten, die in den obigen Schritten mit Eckpunkttabellen versehen wurden, wird der alte Eckpunkt ao durch einen neuen Eckpunkt mit einer unverarbeiteten Kante ersetzt. Es erübrigt sich zu sagen, daß dann, wenn der alte Eckpunkt immer noch eine unverarbeitete Kante aufweist, die Stelle eines neuen Eckpunkts einnehmen kann. Nach dem Schritt STPB13 wird die Verarbeitung des Schritts STPB2 erneut ausgeführt. Auf diese Weise fährt der Prozeß von Fig. 14(f) fort, bis die anhängige Eckpunkttabelle leer wird. Es existiert ein Löschprozeß im Gegensatz zum Entwicklungsprozeß, jedoch wird dessen Erläuterung hier weggelassen, da es sich um eine vollständige umgekehrte Prozedur handelt.
Nachfolgend wird der Erzeugungsprozeß für ein dreidimensionales Raumzeigerpaar SPPi beschrieben. Die Erzeugungsverarbeitungszeit für drei Dimensionen ist von der Größenordnung O (N), wenn Spezialfälle nicht berücksichtigt werden, und der Wartungsprozeß wie für Teilmodifizierung ist bis zu O (Nº) schnell (ohne Beziehung zu N). Dreidimensionale SPF-Erzeugung kann dadurch erzielt werden, daß der SPF wie im Fall von zwei Dimensionen eine Figur nach der anderen hinzugefügt wird.
Wie in Fig. 15(a) dargestellt, besteht ein denkbares Verfahren für den Eintrag einer Figur A in einem Schritt-für- Schritt-Verfahren, bei dem ein Eckpunkt ao zunächst eingegeben wird, was kurz beschrieben wird, ein Drahtrahmen aus Kanten der Figur eingegeben wird, die Rahmen mit Oberflächen versehen werden und schließlich der Innenraum mit Raumattributen aufgefüllt wird (Attribute werden dem SPP hinzugefügt). Neben dem obigen Verfahren bestehen denkbare Verfahren zum Hinzufügen einer Figur in der direkten Eingabe von Oberflächen ohne Vorsehen eines Drahtrahmens folgend auf die Eingabe eines Punktes ao, und in der Ausdehnung des Volumens der Figur A ausgehend von einem Punkt ao.
Ein Hinzufügen eines Punktes ao (xao, yao, zao) zur SPF ist grundsätzlich identisch zum zweidimensionalen Fall. D.h., daß die SPF nach einem den Punkt ao enthaltenden Raum SPPao durchsucht wird und der aufgefundene Raum SPPao geschnitten wird, mit dem der Punkt ao verknüpft ist. Suche nach SPPao wird wie folgt realisiert. Zunächst wird SPPº willkürlich gewählt und ausgehend hiervon wird dem benachbarten Raum in X-Richtung gefolgt, bis die X-Koordinate des Punktes ao den Xao enthaltenden Raum erreicht. Anschließend wird nur Räumen in Y-Richtung gefolgt, die xao enthalten. D.h., daß Räume durchsucht werden, die sowohl xao als auch yao enthalten. Schließlich wird ausgehend von hier benachbarten Räumen in Z-Richtung gefolgt, die sowohl xao als auch yao enthalten. Mit diesem Verfahren wird immer der Punkt ao erreicht (für ein Beispiel eines zweidimensionalen Falles siehe Fig. 14(c) und 14(d).
Dieses Verfahren vermeidet Schleifenbildung und Schwingungen auf dem Suchweg und die Suchzeit ist im wesentlichen proportional zum Abstand zwischen SPPº und dem Punkt ao. Daher kann eine mittlere Geschwindigkeit um O (N1/3) für die Gesamtzahl N von Eckpunkten erzielt werden, vorausgesetzt, daß Spezialfälle nicht berücksichtigt werden. Für eine weitere Beschleunigung des Prozesses wird der gesamte geometrische Raum in m Segmente unterteilt, wie dies in Fig. 16(b) dargestellt ist, wobei Leitpunkte gi (i = 1, 2, . . . , m), auf die direkt zugegriffen werden kann, vorab eingetragen werden, und wenn die Koordinaten des Punkts ao gegeben sind, erfolgt ein direkter Sprung auf den nächsten Punkt gi, ausgehend von dem eine Annäherung zum Punkt ao mit dem oben angegeben Verfahren ausgeführt wird. Dieses Verfahren vom Typ eines Bucketsortsystems erzielt eine Beschleunigung der Größenordnung O (N) mit Ausnahme von Spezialfällen.
Nachfolgend wird die SPF-Entwicklung für den Drahtrahmen beschrieben. Folgend auf die Eingabe des Punktes ao, wie oben beschrieben, wird eine Linie aot beginnend ab dem Punkt so entlang den Kanten der Eingabefigur A gemäß Fig. 15(b) gezogen. D.h., daß ein aus den Kanten der Figur A bestehender Drahtrahmen aus der SPF entwickelt wird. Wenn sich aot erstreckt und ihr Vorderende t durch eine Wand des umgebenden Raums bricht, ändert sich die Topologie der Raumunterteilung, was bewirkt, daß das Erfordernis zum Verändern der Verbindung von SPP in entsprechender Weise auftritt. Dies wird, wie im Fall der vorstehenden zweidimensionalen Zeichnung, als Ereignis Ej (j = 1, 2, . . . ) bezeichnet.
Bei jedem Auftreten eines Ereignisses erfolgt eine Erneuerung von SPP, während ait entlang der Kanten von Figur A so erstreckt wird, daß die gesamte Figur A bedeckt wird, und die Eingabe des Drahtrahmens wird abgeschlossen. Zum Typ von Ej gehört das Durchbrechen von Bz (Oberfläche der Figur) durch ait (siehe Fig. 15(c)) in diesem dreidimensionalen Fall, während der Rest mit dem zweidimensionalen Fall identisch ist. Dies ist aus der Tatsache ersichtlich, daß die Raumunterteilung von Fig. 6(d), gesehen aus der Richtung Z identisch zum zweidimensionalen Fall erscheint. Durch Eingabe des Drahtrahmens wird der Raum um die Figur A neu durch eine Ebene Bx unterteilt, die durch den Eckpunkt der Figur A geht und rechtwinklig zur X-Achse ist, und durch eine Ebene, die den Eckpunkt von Figur A enthält und parallel zur Z-Achse ist; SPP wird für jeden der neuen Räume eingetragen. Diese Verarbeitungen finden nur im Nachbarraum um die Eingabefigur statt, was die Größenordnung O (Nº) erfordert, abgesehen von Spezialfällen.
Nachfolgend wird die Entwicklung einer Fläche beschrieben. Der Eingabe eines Drahtrahmens folgt die Ausbildung von Flächen. Der Flächenentwicklungsprozeß für die Figur A wird realisiert, wie dies in Fig. 15(d) dargestellt ist. In dieser Figur ist der Ausgangspunkt am Ende ai von X&supmin; auf der Ebene G der Figur A ausgewählt, und eine Teilebene aiT, die auf der Ebene G der Figur A angeordnet ist und eine obere Linie T rechtwinklig zur X-Achse aufweist, wird entwickelt, während die obere Linie T vom X&supmin;-Ende nach X&spplus; hin bewegt wird, so daß SPP des umgebenden Raums um aiT progressiv erneuert wird. Wenn die sich in X&spplus;-Richtung bewegende obere Linie T über eine Polygonlinie der Außenwände By und Bz des durch die existierende Figur erstellten Raums gelaufen ist, ändert sich die Topologie der Raumunterteilung plötzlich. Dies wird als Ereignis Ej (j = l, 2, . . . ) bezeichnet, und T direkt nach dem Auftreten von Ej wird als Tj bezeichnet. Eckpunkttabellen (Charakteristikpunkttabellen) werden an Schnittstellen tjk (k = 1, 2, . . ) von Tj und By/Bz erstellt, und SP, der SPP für den umgebenden Raum bildet, wird in diese Tabellen eingetragen. Die Eckpunkttabellen werden mit jedem Auftreten eines Ereignisses Ej aktualisiert. Da die Änderung der Topologie des Raums bei einem Ereignis Ej nur in der auf das Ereignis Ej bezogenen Umgebung von tjk auftritt, kann die Wartung der Eckpunkttabellen dann, wenn sich die obere Linie T bewegt hat, von einem Programm vorgenommen werden, das einen Abschnitt τj beim Durchlaufen des Ereignisses Ej bei Tj-1 hinzufügt und τj-1 löscht, wie dies in Fig. 15(e) dargestellt. Bereiche a und b in der Figur weisen vor und nach dem Ereignis Ej dieselbe Form auf; sie können unverändert verwendet werden. Das Hinzufügen von τj wird wie folgt realisiert. Wie in Fig. 15(e) dargestellt, wird eine Linie tj·0 R auf der Fläche der Zeichnung A entlang τj gezogen und Eckpunkttabellen werden an Schnittstellen mit den vorhandenen Raumgrenzen b3, b4, b5 usw. erstellt. Anschließend werden auf der X&supmin;-Seite Ebenen ausgebildet (ausgedrückt dadurch, daß ein getrennter SPP für jeden Raum auf der Z&spplus;- und Z&supmin;-Seite der Figur A erstellt wird). Dieses Verfahren kann Ereignisse Ej bei verschiedenen Formen meistern.
Die Fig. 15(f) und 15(g) sind Beispiele für eine SPP-Verbindung vor und nach einem Ereignis Ej. Um Ej+1, wie es auf das Ereignis Ej folgt, zu finden, wird der nächste der Eckpunkte in X&spplus;-Richtung (kleinste X-Koordinate) von SPP ausgehend von einer Kante verwendet, die tj,k oder tj,k erzeugt. Wenn die obere Linie T für das letzte Ereignis Ej+1 bewegt wurde, schließt der Entwicklungsprozeß ab.
Die vorstehende Oberflächenentwicklung ist ein Prozeß der Größenordnung 0 (Nº), da der gesamte Prozeß im Nachbarschaftsraum um die Ebene der Eingabefigur A eingeschlossen ist, mit Ausnahme von speziellen Fällen, und da er unabhängig von entfernten Figuren ist. Schlußfolgernd sind alle Eckpunkteinträge, die Drahtrahmenbildung und die Oberflächenentwicklung Prozesse mit 0 (Nº), und es ist zu erwarten, daß das Anfangserzeugnis für die Gesamt-SPF eine Geschwindigkeit von 0 (N) aufweist, wenn Spezialfälle nicht berücksichtigt werden.
Nachfolgend wird das Einfügen und Hinzufügen von Charakteristikpunkten beschrieben. Beim Überlagerungsprozeß, logischen Graphikprozeß, Zusammenstoßprozeß usw. ist es erforderlich, wenn beabsichtigt wird, einen besonderen Charakteristikpunkt (oder Eckpunkt) in einem bestimmten Teilraum hinzuzufügen oder einzufügen, nach einem Raumzeigerpaar zu suchen, das für diesen Teilraum repräsentativ ist, wie dies zuvor beschrieben wurde (Fig. 14(e)), und eine neue Verknüpfungsbeziehung zwischen ihm und seinem benachbarten Charakteristikpunkt und dem speziellen Charakteristikpunkt zu bilden. Für die Bildung einer solchen Verknüpfungsbeziehung besteht ein Verfahren darin, Stück-für-Stück nach Raumzeigerpaaren zu suchen, jedoch nimmt dies übermäßig Zeit in Anspruch. Die Suchzeit kann durch das folgende Verfahren des Einstellens eines Hilfscharakteristikpunktes und des Suchens nach einem Raumzeigerpaar in engster Beziehung verringert werden.
Im Fall von zwei Dimensionen, werden, wie dies aus Fig. 16(a) erkennbar ist, die Koordinaten des Raums, in dem eine Figur angeordnet ist, in einem Zustand unterteilter, matrixähnlicher Blöcke eingestellt. In der Mitte jedes Blocks des geometrischen Raums sind Charakteristikpunkte g¹, g², . . . , gi . . . , gm (diese werden nachfolgend als "Führungspunkt-Charakteristikpunkte" bezeichnet) völlig unbezogen zu den Charakteristikpunkten im geometrischen Raum der Figur eingetragen. Eine Charakteristikpunkttabelle wird für den der Hilfs- oder Führungspunkt-Charakteristikpunkte g¹, g², . . . , gi . . . , gm erstellt. Was die Charakteristikpunkttabellen betrifft, die dem Leitpunkt-Charakteristikpunkt gi oder gm entsprechen, wird ein Raumzeigerpaar so festgelegt, daß g1 und gm sich einander auf solche Weise beziehen. Wenn eine Figur im geometrischen Raum vorhanden ist, werden Raumzeiger zwischen Charakteristikpunkten der Figur und den Leitpunkt-Charakteristikpunkten festgelegt.
Beim Suchen nach einem Raumzeigerpaar, das für den Teilraum repräsentativ ist, der den hinzuzufügenden Charakteristikpunkt ao beinhaltet, werden zunächst Leitpunkt-Charakteristikpunkte g¹, g², . . . , gi, . . . , gm auf Grundlage der Koordinaten des Charakteristikpunktes ao gesucht, und als Ergebnis des Charakteristikpunktes gi, der der Block mit den Koordinaten des hinzuzufügenden Charakteristikpunktes ao wird, wird aufgefunden. Anschließend wird unter Verwendung des Charakteristikpunktes gi als Ausgangspunkt ein Raumzeigerpaar SPPao, das den Raum mit dem hinzuzufügenden Charakteristikpunkt ao ausdrückt, durch die in Fig. 14(e) dargestellte Prozedur gesucht. Einer der Charakteristikpunkte, mit dem SPPao verbunden ist, wird als ko bezeichnet. Nachfolgend wird das Raumzeigerpaar SPPao zerlegt und ein anderes Raumzeigerpaar SPPalko für den Charakteristikpunkt ao und den Charakteristikpunkt ko wird neu erzeugt. Auf dieselbe Weise wird für einen anderen Charakteristikpunkt ko', mit dem
SPPao verbunden wird, das Raumzeigerpaar in Verbindung mit dem Charakteristikpunkt ao erzeugt.
Um die Suche nach Gleitpunkt-Charakteristikpunkten nahe dem hinzuzufügenden oder zu löschenden Charakteristikpunkt ao zu erleichtern, wird eine Leitpunktadreßtabelle erstellt, obwohl keine Beschränkung hierauf besteht. Die Leitpunktadreßtabelle weist Speicherbereiche auf, auf die unter Verwendung von Daten X1-X4 zugegriffen wird, die den Bereich in X- Richtung des geometrischen Raums anzeigen, und unter Verwendung von Daten Y1-Y4, die den Bereich in Y-Richtung anzeigen, wie dies in Fig. 16(a) dargestellt ist. Jeder Speicherbereich beinhaltet vorgegebene Daten, die die Adresse der Charakteristikpunkttabelle für den Leitpunkt-Charakteristikpunkt anzeigen. Obwohl der geometrische Raum sowohl entlang der X- als auch der Y-Achse zum Vereinfachen der Erläuterung viergeteilt ist, kann er in der Praxis in eine willkürliche Anzahl von Räumen unterteilt sein. Genauer gesagt, wird die Leitpunktadreßtabelle dazu verwendet, das Raumzeigerpaar für den Leitpunkt-Charakteristikpunkt gi aus den Koordinaten (xo, yo) für einen Charakteristikpunkt ao zu erhalten, und danach wird der Charakteristikpunkt ko für die tatsächliche Zeichnung in Verbindung mit dem Raumzeigerpaar, das den Raum, in den der Charakteristikpunkt ao einzufügen ist, repräsentativ ist, im Bereich der Raumblöcke für den Charakteristikpunkt gi gesucht. Das Raumzeigerpaar für die Leitpunkt-Charakteristikpunkte wird getrennt vom Raumzeigerpaar für Charakteristikpunkte der tatsächlichen Zeichnung bereitgestellt, und es wird mit einem Raumzeiger für jeden Charakteristikpunkt einer anderen Figur innerhalb des Bereichs des Blocks gepaart, obwohl keine Beschränkung hierauf besteht. Wenn eine bestimmte Anzahl von Figuren bereits in die SPF eingetragen ist, besteht keine Schwierigkeit beim Verwenden von Endpunkten oder Charakteristikpunkten dieser Figuren als Leitpunkte.
Im Fall einer dreidimensionalen Zeichnung wird der geometrische Raum in matrixförmig angeordnete Blöcke unterteilt, wie dies in Fig. 16(b) dargestellt ist, und der Leitpunkt-Charakteristikpunkt g1 oder gm wird in jeden Block eingetragen. Demgemäß ist die Verarbeitung für eine dreidimensionale Zeichnung identisch mit dem Fall einer zweidimensionalen Verarbeitung.
Beim Erzeugen eines Raumzeigerpaars werden besondere Bedingungen auf spezielle Figuren und Linien angewendet. Ein Beispiel ist der Fall einer Kombination von Linien wie sie in einem Polygondiagramm erkennbar sind. Probleme, die beim Handhaben von Figuren wie Polygondiagrammen auftreten, entsprechen Schwierigkeiten dahingehend, wie die Linien auszudrücken sind. Eine Linie wird z. B. als eine Art einer Kante einer Figur angesehen. Die Enden eines Polygondiagramms sind offen, im Gegensatz zu Kanten einer Figur wie z. B. eines Dreiecks. Demgemäß wird jede Linie, die ein Polygondiagramm bildet, als Raumzeigerpaar ausgedrückt, das zwischen den Endpunkten und einem Kantenzeigerpaar errichtet wird. In den Charakteristikpunkttabellen, die einem Ende und einem anderen Ende eines Polygondiagramms entsprechen, werden Attributdaten, die die Linienenden kennzeichnen, eingetragen.
Wenn die zwei Endpunkte einer geraden Linie oder der Kante einer Figur dieselbe Koordinate aufweisen, ist es erforderlich, die Eindeutigkeit der Raumnachbildung wiederzugewinnen, um eine Entsprechung zwischen Teilräumen und Raumzeigerpaaren herzustellen. Zu diesem Zweck wird, wenn z. B. eine Linie oder eine Kante rechtwinklig zur X-Achse vorhanden ist, wie dies in Fig. 17(a) dargestellt ist, die Linie oder die Kante als verdrehte Linie angesehen. Mit dieser Annahme muß sich jedoch das Zeichnungsverarbeitungsprogramm beschäftigen, und es bedeutet keine Änderung der X-Koordinaten, wie sie in die Charakteristikpunkttabelle eingetragen sind. D.h., wenn als Ergebnis der Bezugnahme auf zwei Charakteristikpunkttabellen für die Linie oder Kante bestimmt wird, daß beide Endpunkte der Linie oder Kante dieselbe X-Koordinate aufweisen, bestimmt das Zeichnungsverarbeitungsprogramm, daß der eine Endpunkt mit der größeren Y-Koordinate mehr rechts oder mehr links angeordnet ist, wie dies in Fig. 17(a) dargestellt ist. Auf ähnliche Weise wird ein Raumzeigerpaar für den Fall einer gleichen X-Koordinate unter der Annahme gebildet, daß einer der zwei Punkte mehr rechts (oder mehr links) als der andere angeordnet ist, wie dies in Fig. 17(b) dargestellt ist. Im anderen Fall, bei dem zwei Linien überlappende Abschnitte aufweisen, wird angenommen, daß sie um einen kurzen Abstand voneinander beabstandet sind, wie dies in Fig. 17(c) dargestellt ist.
Die Fig. 17(d) und 17(e) sind Diagramme, die spezielle Zustände des Kantenzeigerpaars erläutern. Es sind Beispiele, daß eine Selbstpaarung als Partnerkantenzeiger stattfindet. Fig. 17(f) zeigt ein Beispiel eines Raumzeigerpaars und eines Kantenzeigers an einer Schnittstelle. Fig. 17(g) ist ein Diagramm zum Erläutern der Ausbildung eines Raumzeigerpaars, wenn eine Figur teilweise eine Kurve beinhaltet.
Ähnliche Zustände existieren in einer dreidimensionalen Zeichnung. Im Fall einer Durchdringungszeichnung mit einem Eckdurchdringungspunkt, wie dies in Fig. 18(a) dargestellt ist, wird eine Charakteristikpunkttabelle erstellt, wie sie in Fig 18(b) dargestellt ist. Daraus ergibt sich eine Dreiebenen-Schnittbeziehung, wie sie in den Fig. 18(c) und 18(d) dargestellt ist.
Im Fall der Durchdringungszeichnung, wie sie in Fig. 18(a) dargestellt ist, bilden der Kantenzeiger EPo, der die Vorderkante wiedergibt, und der Kantenzeiger EP2, der die Hinterkante wiedergibt, von Natur aus eine einzige Kante. Um den Zeichnungsprozeß entlang der Durchdringungskante zu erleichtern, ist es erwünscht, Zeiger einzutragen, die wechselseitig auf Durchdringungskanten zeigen (dies wird nachfolgend als Durchdringungszeiger beschrieben). Ein solcher Durchdringungszeiger ist in Fig. 18(b) mit PEP symbolisiert. Da der Block EG für eine dreidimensionale Zeichnung in Fig. 9(b) im Detail gezeigt wurde, ist Fig. 18(b) relativ vereinfacht. In Fig. 18(b) ist der Zeiger PEP des Blocks EGo in das Feld RP derjenigen Zeile eingetragen, in der der Kantenzeiger EPj des Blocks EGj in Fig. 9(b) einzutragen ist. Auf ähnliche Weise wird PEP des Blocks EP2 in das Feld RP derjenigen Zeile eingetragen, in die der Kantenzeiger des Blocks EGi in Fig. 9(b) einzutragen ist. Im Fall von Fig. 18(a) sind die Kanten EP1 und EP3 keine Durchdringungskanten im oben angegebenen Sinn. Daher bleibt das Attributfeld für die Durchdringungskante innerhalb des Kantenblocks in der Tabelle von Fig. 18(b) leer. Die Fig. 18(c) und 18(d) für den dreidimensionalen Schnitt sind auf ähnliche Weise angeordnet wie im vorigen Fall eines zweidimensionalen Schnitts.
Die Bewegung einer Figur ist im Fall einer zweidimensionalen Zeichnung diejenige, wie sie in Fig. 19 dargestellt ist. Aus der Figur ist erkennbar, daß die Bewegung einer Figur T zu einer Änderung in der Raumbeziehung nur für die schraffiert eingezeichneten Räume führt. Demgemäß wird durch Ausdrücken des Raums unter Verwendung der oben beschriebenen Raumzeigerpaare die Verarbeitung auf den Bereich benachbarter Räume beschränkt, und bei der Verarbeitung sind nur Daten in der Charakteristikpunkttabelle, die den schraffierten Räumen in der Figur entsprechen, zu beachten. Dasselbe gilt für eine dreidimensionale Zeichnung, die unter Beachtung von Nachbarräumen verarbeitet wird. Dies bedeutet, daß die Zusammenstoßfeststellung und der Bewegungsprozeß für eine Zeichnung ein äußerst einfacher Prozeß wird. Insbesondere ist es bei einer dreidimensionalen Zeichnung möglich, die Zusammenstoßermittlung bei der Bewegung eines Roboters beim Laden des Bewegungszeitplans des Roboters vorab zu verarbeiten. Selbstverständlich ist es möglich, dieses Prinzip auf den Fall eines Labyrinthprozesses in einer zweidimensionalen Zeichnung anzuwenden.
Ein wichtiger Prozeß für dreidimensionale Zeichnungen ist das Löschen nicht sichtbarer Flächen. Fig. 20 ist ein Diagramm zum Erläutern des Löschens nicht sichtbarer Flächen. Durch die Matrixumwandlung für eine dreidimensionale Zeichnung in eine zweidimensionale perspektivische Zeichnung können nicht sichtbare Bereiche hinter vorderen, sichtbaren Bereichen gelöscht werden.
Fig. 20 zeigt das Konzept einer dreidimensionalen Anzeige. Beim Löschprozeß für eine nicht sichtbare Fläche werden eine Überlappungsprüfung und eine Anzeigeprioritätsentscheidung für eine auf einen Schirm projizierte zweidimensionale Zeichnung in einer SPF für einen zweidimensionalen Schirm realisiert. Da die SPF dazu in der Lage ist, einen Zeichnungsprozeß auf Eins-zu-eins-Basis auszuführen, wird sie mit einer SPF für die dreidimensionale Welt kombiniert, und die Verarbeitungsgeschwindigkeit kann durch ein Ablaufverfolgungsverfahren für den sichtbaren Raum drastisch erhöht werden, wie dies im folgenden beschrieben wird.
Fig. 21 zeigt das Prinzip dieses Verfahrens. In einer dreidimensionalen SPF beginnt die Verarbeitung mit einem Teilraum Ωo, der den Betrachtungspunkt beinhaltet. Wende (sichtbarer) Teilräume, durch die die von diesem Betrachtungspunkt ausgehende Blicklinie läuft, werden sequentiell perspektivisch transformiert und einer Überlappungsprüfung in der Schirm-SPF und einem Sichtbarkeitstest für die Zeichnung unterzogen. Unter Verwendung der Suchfunktion der SPF für einen benachbarten Raum werden darzustellende Räume sequentiell in Vorwärtsrichtung aufgesucht. In diesem Fall werden auf Grundlage der Tatsache, daß ein sichtbarer Raum immer mit der anderen Seite eines sichtbaren, durchsichtigen Raums zusammenhängt, und ein Raum hinter einer undurchlässigen oder nicht sichtbaren Wand nicht zu sehen ist, nur sichtbare Räume aufgefunden, nicht sichtbare Räume jedoch nicht, wodurch der Prozeßwirkungsgrad in unvergleichlicher Weise im Vergleich mit den herkömmlichen Verfahren verbessert werden kann. Dieses Verfahren hat die folgenden Merkmale.
(1) Kontinuierlicher Prozeß in einer dreidimensionalen SPF.
(2) Hochgeschwindigkeitsprozeß nur für sichtbare Räume.
Wenn z. B. in Fig. 20 ein Haus als Figur von außen gesehen wird, wird nach der Raumanordnung, der Möblierung und dergleichen nicht gesucht. Es werden auch keine unsichtbaren Räume außerhalb des Schirms untersucht, und daher ist der Wirkungsgrad höher als beim herkömmlichen Abschneiden. Die Verarbeitungszeit ist O (N&sup0;) mit Ausnahme spezieller Fälle, und sie ist O (n), wenn n die Anzahl sichtbarer Räume bezeichnet.
(3) Schnelle und willkürliche Änderungen des Betrachtungspunktes.
Das herkömmliche System, das Abschneiden nach perspektivischer Transformation realisiert, erfordert die Verarbeitung für die gesamte Zeichnung, wenn der Betrachtungspunkt verändert wird, während das erfindungsgemäße System lediglich sichtbare, aufgefundene Räume verarbeitet; es ist schnell.
(4) Hochgeschwindigkeits-Auslesekartierung für dreidimensionale Zeichnungen.
Eine Figur auf dem Schirm, die durch einen Stift, eine Maus oder dergleichen bezeichnet wird, kann auf zweidimensionaler SPF-Basis mit hoher Geschwindigkeit gesucht werden. Eine Figur der SPF der dreidimensionalen Welt kann leicht dadurch identifiziert werden, daß sie mit Hilfe der Zeigeeinrichtung mit der Schirm-SPF verbunden wird.
(5) Teilschirmveränderung.
Es kann dafür gesorgt gesorgt werden, daß nur ein modifizierter Bereich der Verarbeitung für eine versteckte Oberfläche durch die Schirm-SPF unterzogen wird. Eine teilweise Löschung einer Zeichnung erfordert eine Ablaufverfolgung für den sichtbaren Raum nur für diesen Bereich.
(6) Einfache Vektor/Raster-Konversion für den Schirm.
Die Schirm-SPF stellt eine logische UND-Verknüpfung zwischen der Zeichnung und dem Raster her und das Ergebnis wird direkt an einen elektrostatischen Plotter oder dergleichen ausgegeben.
(7) Spezielle Hardware wie ein Z-Puffer ist nicht erforderlich. Aufgrund des gesamten softwaregeschützten, vielseitigen und stark einebnenden Entwurfs besteht keine durch Pixel auferlegte Genauigkeitsgrenze und der Schirm wird nicht durch zoomen gestört. Die Ausgabe der Löschung einer verdeckten Oberfläche ist selbst für einen großen Schirm wie einen Plotter möglich.
Fig. 22 ist ein Diagramm, das dazu verwendet wird, die Ausbildung von Raumzeigerpaaren für eine zweidimensionale Zeichnung zu erläutern, wenn die Zeichnungsdaten so enorm daß sie insgesamt im Hauptspeicher abgelegt sind. In diesem Fall wird der Zeichnungsraum in mehrere Bereiche unterteilt. In Grenzabschnitten der Bereiche sind Grenzlinien eingefügt, die für den Benutzer unsichtbar sind, und Raumzeiger sind so angeordnet, daß sie innerhalb des Wertebereichs für jeden Bereich verarbeitet werden. Dieses Schema ist auch auf dreidimensionale Zeichnungen anwendbar.
Ein wirksames Verfahren für Teilverarbeitung ist Mustererkennung. Wenn z. B. nach einer quadratischen Figur R mit einem Dreieck in ihr gesucht wird, kann diese einfach dadurch gefunden werden, daß Raumzeiger sequentiell aufgesucht werden und in einem Prozeß für eine benachbarte Zeichnung eine eingeschlossene Figur ermittelt wird. Zweidimensionale und dreidimensionale Zeichnungen können im Hinblick auf diesen Gesichtspunkt identisch behandelt werden.
Fig. 24(a) zeigt den Fall einer Unterteilung des zweidimensionalen Raums, bei der charakteristische Eckpunkte ausgewählt werden und der Raum selektiv unterteilt wird, anstatt daß alle Eckpunkte der Figur verwendet werden. Dieses Konzept ist identisch zum Fall einer dreidimensionalen Zeichnung, wie sie in den Fig. 25(a) und 25(b) dargestellt ist.
Fig. 26(b) zeigt ein Beispiel, bei dem das Polarkoordinatensystem für einen zweidimensionalen Raum verwendet wird, und es kann auch auf einen dreidimensionalen Raum angewendet werden. Die Raumnachbildung ist unabhängig vom Koordinatensystem.
Wie in Fig. 27(c) dargestellt, ist es möglich, eine Zeichnung unter Verwendung eines Verarbeitungssystems zu verarbeiten, das ein Tablett, eine Maus, einen Plotter und einen Drucker beinhaltet.
Vorstehend wurde beschrieben, daß die erfindungsgemäße Zeichnungsverarbeitung extensiv z. B. auf das Layoutdesign von LSI-Bauelementen, auf das Auffinden eines optimalen Weges, auf die Steuerung von Roboterbewegung und auf das Verhindern von Zusammenstößen anwendbar ist.
Das Raumzeigerpaar einer Figur ist nicht auf einen Eckpunkt beschränkt, sondern jeder beliebige charakteristische Punkt der Figur ist zugelassen. Obwohl bei den vorstehenden Ausführungsbeispielen ein Raum durch flache Ebenen unterteilt wird, können Grenzen unter Verwendung schiefer Ebenen, gekrümmter Ebenen oder dergleichen hergestellt werden, und das Koordinatensystem kann willkürlich als dreidimensional oder n-dimensional gewählt werden.
Obwohl die Ausführungsbeispiele hauptsächlich für eine Zeichnung beschrieben wurden, ist eine ähnliche Verarbeitung für Videobilder durch die direkte Entwicklung charakteristischer Punkte auf den Bildern und die Umsetzung in eine Zeichnung anwendbar.
Obwohl bei den vorstehenden Ausführungsbeispielen das Zeichnungsverarbeitungsprogramm von der Raumdatenverarbeitung getrennt ist, ist es auch möglich, die gesamten Daten im Raumdatenformat bereitzustellen und Zeichnungsdaten aus den Raumdaten zu erzeugen.
Obwohl bei den vorstehenden Ausführungsbeispielen einer spezieller Raumdatenprozessor bereitgestellt ist, ist es selbstverständlich möglich, dessen Prozeß als Funktion der zentralen Verarbeitungseinheit auszuführen.
Wie es aus der obigen Beschreibung der Erfindung zu würdigen ist, wird ein Raum, in dem eine Figur angeordnet ist, durch Linien, die durch charakteristische Punkte der Figur gehen, unterteilt, Teilräume werden durch Paare charakteristischer Punkte (z. B. Zeigerpaare) zu beiden Seiten der Räume definiert, und Beziehungsdaten, die die Beziehung jedes charakteristischen Punktes zu einem anderen charakteristischen Punkt anzeigen (z. B. ein Zeigerpaar) werden eingetragen, wodurch Suche nach Teilräumen durch das Eckpunktpaar ermöglicht ist und Zeichnungsverarbeitung unter Zuwenden der Aufmerksamkeit auf einen Bereich möglich wird. Infolgedessen kann die Suche nach aufeinanderfolgenden Figuren oder überlappenden Figuren wirkungsvoll ausgeführt werden, und es wird ein Hochgeschwindigkeits-Zeichnungsprozeß realisiert.
Für Datenverarbeitung einer Figur, die in einem stereographen Koordinatensystem angeordnet ist, in dem die Figur durch mindestens eine erste, zweite und dritte Variable ausgedrückt wird, wird das Koordinatensystem durch parallele Ebenen unterteilt, die durch die charakteristischen Punkte hinsichtlich der der ersten Variablen entsprechenden Achse gehen, und Charakteristikpunktinformation wird abhängig von den Charakteristikpunkten zu beiden Seiten des Raums zwischen den parallelen Ebenen erzeugt. Ein Satz von Charakteristikpunktinformation und ein benachbarter Satz oder mehr als ein Satz von Charakteristikpunktinformation werden mit einer Verknüpfungsbeziehung erzeugt, und ein Raum zwischen den parallelen Ebenen wird auf Grundlage der Verknüpfungsbeziehung festgelegt. Dies ermöglicht die Suche eines stereographen Teilraums durch das Charakteristikpunktpaar, und es wird ein Zeichnungsprozeß ermöglicht, bei dem einem Bereich Beachtung geschenkt wird. Infolgedessen können die Suche nach aufeinanderfolgenden Figuren und überlappenden stereographen Figuren sowie ein Prozeß betreffend versteckte Oberflächen wirkungsvoll ausgeführt werden, wodurch eine dreidimensionale Zeichnungsverarbeitung mit hoher Geschwindigkeit realisiert ist.

Claims

1. Computermodellsystem zum Nachbilden von Figuren in einem n-dimensionalen Raum, wobei die Figuren charakteristische Punkte (Pi, Pi+1) und n-1-dimensionale Grenzen enthalten, die die charakteristischen Punkte verbinden, welches Computermodellsystem folgendes aufweist: - eine Einrichtung (1, 2, 3), die eine Datenstruktur einschließlich mehrerer Charakteristikpunkttabellen definiert, die Zeiger (SPi, SPi+1) beinhalten, die auf die charakteristischen Punkte (Pi, Pi+1) zeigen, wobei jede Charakteristikpunkttabelle Positionsinformation zum Repräsentieren der Position des charakteristischen Punktes im n-dimensionalen Raum enthält, dadurch gekennzeichnet, daß - die genannte Datenstruktur mehrere Teilräume (ωi; Ωi) innerhalb des geometrischen Raums repräsentiert, wobei jeder Teilraum hinsichtlich eines Paars charakteristischer Punkte auf Grundlage der n-1-dimensionalen Grenzen und n-1-dimensionaler imaginärer Unterteilungen (Di, Di+1; Bx, By, Bz) definiert ist, die jeweils durch einen jeweiligen charakteristischen Punkt gehen, wobei die Charakteristikpunkttabelle für jeden charakteristischen Punkt des Paars einen Zeiger (SP) beinhaltet, der auf einen anderen Zeiger in der Charakteristikpunkttabelle für einen anderen Charakteristikpunkt des Paars in solcher Weise zeigt, daß das Zeigerpaar einen Teilraum (ω&sub1;; Ωi) repräsentiert, der von den n-1-dimensionalen Grenzen unterteilt wird, wobei die imaginären Unterteilungen durch das Paar charakteristischer Punkte gehen.

2. Computermodellsystem nach Anspruch 1, bei dem der n-dimensionale Raum ein zweidimensionaler Raum ist.

3. Computermodellsystem nach Anspruch 2, bei dem der zweidimensionale Raum zwei Koordinatenachsen aufweist, und bei dem sich die imaginäre Unterteilung in Richtung einer der zwei Koordinatenachsen erstreckt.

4. Computermodellsystem nach Anspruch 1, bei dem der n-dimensionale Raum ein dreidimensionaler Raum ist.

5. Computermodellsystem nach Anspruch 1, bei dem die Charakteristikpunkttabellen Eckpunkten der Figuren entsprechen.

6. Computermodellsystem nach einem der Ansprüche 1 oder 5, bei dem die Charakteristikpunkttabellen Kanteninformation (n-1-dimensionale Grenzinformation) zu Kanten (n-1-dimensionale Grenzen) der Figuren enthalten.

7. Computermodellsystem nach einem der Ansprüche 1, 5 oder 6, bei dem die Charakteristikpunkttabellen Attributinformation beinhalten, die ein Attribut des Teilraums anzeigen.

8. Computermodellsystem nach Anspruch 6, bei dem die Eckpunkte Kreuzungspunkte der Kanten der Figuren beinhalten.

9. Computermodellsystem nach Anspruch 1, bei dem das Computermodellsystem geometrische, örtliche Einstellabläufe ausführt.

10. Computermodellsystem nach Anspruch 9, bei dem die geometrischen, örtlichen Einstellabläufe ODER-Abläufe beinhalten.

11. Computermodellsystem nach Anspruch 9, bei dem die geometrischen, örtlichen Einstellabläufe Überlagerungs-Prüfabläufe beinhalten.

12. Computermodellsystem nach Anspruch 1, bei dem das Computermodellsystem Zusammenstoß-Prüfabläufe für bewegte Figuren in einem örtlichen Prozeß ausführt.

13. Computermodellsystem nach Anspruch 1, bei dem das Computermodellsystem Beseitigungsabläufe für verdeckte Linien ausführt.

14. Computermodellsystem nach Anspruch 1, bei dem das Computermodellsystem Beseitigungsabläufe für verdeckte Flächen ausführt.