JPS6224371A - 図形処理システム - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［産業上の利用分野コ この発明は、図形処理システムに関し、特に、計算機に
おいて図形／画像処理をするときに図形／画像データを
部分処理によって効率的でかつ高速な処理できるような
図形／画像処理のデータベースシステムに関するもので
ある。

［従来の技術］ 図形／ｌＩＩ！ｌ像処理の例としては、ＬＳＩ、ＶＬＳ
■の設計、論理回路、重体、建築物９機械、プラントの
設置；１など、コンピュータグラフィックス技術を利用
したＣ　Ａ　Ｉ）システム、衛星からのデータに対する
対象鰻析、そして医療関係における画像解析等、各種の
分野で図形／画像処理が行われている。

ここで、図形処理のＣＡ　Ｉ）システムを例に採れば、
その全図形型素数Ｎは、最近では１０”−１０７に達す
る大規模図形の処理が必髪になることが多く、特に、図
形データ相互に関係する処理にあってはそのデータ処理
Ｍが非常に膨大なものとなっている。しかもこのような
場合に計算機の処理時間は、この数値Ｎとともに急増す
るため原理的には処理が可能であっても、実用１−処理
に相当の時間がかかりその処理が不ｉ”＋Ｊ能な状態と
なることも少なくない。

［解決しようとする問題点コ このように処理ができない一因としては、この種の図形
処理が本来隣接図形間の関係や図形相互の重なりを処理
する場合であっても図形データ全体の処理を行うことに
よる。その理由は、図形データベースにこれら隣接図形
に関するような特別の情報が記述されていないためであ
って、　・部分の図形処理か図形全体に対してのデータ
処理となり、２認な部分たけの部分的な処理で済まない
からである。

このようなことを回避するために隣接に関係する情報を
特別に設けて処理をすることも考えられているが、図形
形状に制限があったり、さらにデータｊｉ）を増加させ
て、処理時間を大きくシ、充分な問題点の解決にはなっ
ていない。

しかも、このようなことは、データ驕が膨大となる立体
的な図形処理の場合にさらに大きな問題となる。

［発明の目的］ この発明は、このような従来技術の問題点等にかんがみ
てなされたものであって、このような問題点等を解決す
るとともに、立体的な図形又は画像データを部分的に処
理することができ、効率的でかつ高速に処理できるよう
な図形処理システムを提供することを目的とする。

［問題点を解決するための１段］ この発明の特徴は、図形及び図形の置かれた空間を部分
＼１体空間に分割して、部分＼ｒ体空間をポインタの組
で表現するものであって、隣接図形。

小なりＸ７体図形等をこのポインタ検索より求めて処理
することにより高速で効率的な処理を三次元の＼γ体図
形又はそれ以−［−の次元の図形において実現するとい
うものである。

しかして、このような目的を達成するためのこの発明の
Ｌ段は、少なくとも第１．第２．第３の変数により表現
される）ｙ体重間座標系に配置された図形についてのデ
ータ処理において、第１の変数に対応する軸に関し図形
の特徴点を通る−に行な面で、ｑ体重間座標系を分割し
、・１行な面により挟まれた空間の両側の特徴点に対応
してそれぞれ特徴点情報が生成される図形処理システム
であって、各特徴点情報と、隣接する他の１つ又は複数
の特徴点情報とを、相互に連結関係を持って生成し、こ
の連結関係により・１行な面により挟持される空間を定
義するというものである。

［作用コ このようにすることにより特徴点のペアにより部分＼゛
ｆ体空同空間ｎ次元の空間の検索が可能となり、部分に
注目したｑ体間形の処理ができ、隣接図形の処理を部分
的に取り出した形で処理ができる。

その結果、隣接図形の関係処理とか市なり＼ｒ体図形の
検索、＼ｙ体図形同七のＡＮＤ、ＯＲ等の論理的な処理
、隠れ面の処理等が効率的に実行でき、高速な処理を実
現できるものである。

［実施例］ 以ド、図面を用いてこの発明の−・実施例について詳細
に説明する。

第１図は、この発明の図形処理システムを適用した計算
機システムのブロック図であり、第２図（ａ）は、その
図形処理システムによる図形処理の機能構成図、第２図
（ｂ）は、そのスペースデータ処理部におけるインタプ
リタプログラムの処理の流れ図、第２図（ｃ）は、その
演算処理装置におけるプログラム制御部の処理の流れ図
、第３図（ａ）は、そのスペースデータの原理的な表現
の説明図、第３図（ｂ）は、その基本的な空間分割の処
理の仕方の説明図である。また、第４図（ａ）は、二次
元における特徴点テーブルのＸ方向端点についての具体
例の説明図、第４図（ｂ）は、その特徴点テーブルのＸ
方向でない端点の具体例の説明図、第４図（Ｃ）は、第
４図（ａ）の二次元テーブルに対応する図形の説明図、
第４図（ｄ）は、第４図（ｂ）のテーブルに対応する図
形の説明図、第４図（ｅ）？：、テーブルにおける符シ
、＞の説明図、第４図（ｆ）は、テーブルにおける各デ
ータの具体的構成を示す−・例の説明図、第４図（ｇ）
は、空間属性が設置できない場合の説明図、第５図（ａ
）は、二次元での処理されるべき図形の一例を示す図、
第５図（ｂ）は、その図形において発生するスペースポ
インタペアの説明図、第６図（ａ）、二次元における空
間分割の仕方の説明図、第６図（ｂ）は、Ｘ７．体間形
相互におけるスペースポインタペアの関係を示す説明図
、第６図（Ｃ）は、三次元における蔭の交叉についての
説明図、第６図（ｄ）は、そのＺ方向の投影図、第７図
は、図柄と面ポインタペアとの関係の説明図である。そ
して、第８図（ａ）は、＼γ体同図形空間分割とスペー
スポインタペアとの関係の説明図、第８図（ｂ）は、そ
の１つの頂点から出るスペースデータの説明図、第９図
（ａ）は、スペースデータと左右の連結情報との関係の
説明図、第９図（ｂ）は、三次元における特徴点テーブ
ルの具体例の説明図、第９図（Ｃ）は、多面体の凸頂点
Ｖのまわりのスペースデータの説明図、第９図（ｄ）は
、凸頂点Ｖのまわりの特徴点テーブルの説明図、第第１
Ｏ図（ａ）は、凹なる立体空間を持つ１つのｒｔｒ点か
ら出るスペースデータの説明図、第１０図（ｂ）は、凹
なる立体空間が存在する場合の特徴点テーブルの説明図
、そして第１１図（ａ）は、市なりを判定する場合の重
なり図形の　・例を示す説明図、第１１図（ｂ）は、そ
の場合の属性の説明図、第１２図（ａ）は、二次元での
多色図形の各ポインタの表現例の説明図、第１２図（ｂ
）は、その場合の特徴点テーブルの関係を、ドす概要図
、第１３図は、１γ体図形の重複状態の説明図である。

また、第１４図（ａ）及び第１４図（ｂ）は、それぞれ
スペースポインタペアの生成の仕方についての説明図、
第１４図（Ｃ）は、二次元において図形等を人力する場
合の特徴点についてのスペースポインタペアの生成の仕
方の説明図、第１４図（ｄ）は、第１４図（ｃ）の表に
従って五角形を図形データベースの中に入力する場合の
スペースポインタペアの生成関係を説明する図、第１５
図（ａ）は、立体図形において点と線の位置を入力する
場合の説明図、第１５図（ｂ）は、図形の辺を人力する
場合についての立体空間での関係を説明する図、第１５
図（Ｃ）は、入力辺の先端が既設面を通過する前後の関
係を説明する図、第１５図（ｄ）、第１５図（ｅ）、第
１５図（ｆ）及び第１５図（ｇ）は、それぞれ面の入力
手順を説明する図、第１６図（ａ）は、二次元において
特徴点を高速に検索するための道しるべ処理の説明図、
第１６図（ｂ）は、三次元の道しるべ処理の説明図、第
１７図（ａ）、第１７図（ｂ）及び第１７図（Ｃ）は、
それぞれ特殊な状態におけるスペースポインタペアの形
成の仕方の説明図、第１７図（ｄ）、第１７図（ｅ）は
、それぞれ特殊な状態における辺ポインタペアの形成の
仕方の説明図、第１７図（ｆ）は、交叉点の場合のポイ
ンタペアの説明図、第１７図（ｇ）は、図形の−・都に
曲線がある場合のスペースポインタペアの形成について
の説明図、第１８図（ａ）及び（ｂ）は、それぞれ三次
元におけるコーナＩ！ｊ通点とその特徴点テーブルの説
明図、第１８図（ｃ）及び（ｄ）は、それぞれ三面交叉
点とその特徴点テーブルの説明図、第１９図は、運動図
形についての空間関係を示す説明図、第２０図は、隠れ
面消去の説明図、第２１図は、可視空間追跡法を用いる
場合の説明図、第２２図は、図形データが複数の領域に
分割されているような場合のスペースポインタペアの形
成の仕方の説明図、第２３図は、特定の図形についてサ
ーチする場合の説明図、第２４図は、二次元において回
転サーチ処理を高速化するためスペースポインタペアに
対する頂点を増設する例の説明図、第２５図（ａ）及び
（ｂ）は、それぞれ三次元において同様に増設辺を設定
した場合のスペースポインタペアとの関係の説明図、第
２６図は、空間の分割を極座標とした場合の説明図、第
２７歯は、他の実施例における図形処理システムのブロ
ック図である。

第１図中、■は、演算処理装置（ＣＰＵ）であって、２
は、そのメモリである。３は、スペースデータ処理部、
４は、Ｉ１０制御部、５は、インタフェース、６は、シ
ステムバス、７は、ディスプレイ、８は、キーボード、
そして９は、外部記憶装置としての磁気ディスク記憶装
置（以トリ１にディスク）である。演算処理装置１とメ
モリ２、スペースデータ処理部３、そしてＩ　／　Ｏ；
ｌ１ｌＪ御部４とは、それぞれシステムバス６にて相ｒ
７に接続されていて、これらの間でデータ転送が打われ
る。

そしてＩ１０制御部４は、インタフェース５を介してデ
ィスプレイ７、キーボード８、ディスク９等との間でデ
ータ交換を１テう。

ここで、メモリ２は、演算処理装置１とＩ１０制御部４
、スペースデータ処理部３とから共通に・アクセスされ
るものであって、メモリ２には、スペースデータインタ
プリタプログラム記憶部２ａ。

スペースデータ発生プログラム記憶部２ｂ、Ｉ１０制御
プログラム記憶部２ｃ、　　スペースデータ記憶部２ｄ
、図形処理プログラム記憶部２　ｅ　１そしてその他デ
ータ記憶部２ｆ等の領域が設けられていて、スペースデ
ータ記憶部２ｄには、第４図（ａ）、（ｂ）に見るよう
な二次元の特徴点テーブル２０．２１等及び第９（ｂ）
に見る二次元の特徴点テーブル２２等が各図形の特徴点
（頂点以外の点も含む）対応に設けられ、これらは、ス
ペースポインタペア（ＳＰＰ）等の情報が所定の順序で
記憶されていて、検索内容に応じてこれらが参照される
ものである。

方、第１図のスペースデータインタプリタプログラム記
憶部２ａには、スペースデータ処理部３がこのインクプ
リタブログラムを実１１゛シて、スペースデータ記憶ｉ
Ｗ＜２ｄに記憶されたスペースデータにノ＾づき、演′
Ｓ１処理装置１により処理される図形情報を発生する処
理プログラムが記憶されている。

また、スペースデータ発生プログラム記Ｌａ部２ｂには
、この＋ｉｌ算機ンステｌ、で処理される図形処理プロ
グラド又は図形データから第４図（ａ）。

（ｂ）に見るような二次元の特徴点テーブル２０゜２１
）・及び第９図（ｂ）に見るような特徴点テーブル２２
等の形で所定のスペースデータ（又はスペースデータフ
ァイル、５ＰＦ）を発生する処理プログラムが記憶され
ている。

ところで、三次元のスペースポインタペア５ＰＰｉの図
形データ処理について説明する前に、三次元の理解を容
易にするために二次元におけるスペースポインタペア５
ＰＰＩの図形データ処理から説明する。なお、この−０
次元のスペースポインタペア５ＰＰｉによる図形データ
処理に一ついては、すでに出願済みである。

さて、スペースデータの考え方は、−次元においては、
第３図（ａ）に見るように、特徴点Ｐ１゜Ｐ　ｉ＋１を
通る空間分割線［）ｉ　、　Ｄｉａｌを考えて、それぞ
れの特徴点にスペースポインタＳＰｉ、ＳＰ　Ｉｌｌを
設けてこれらスペースポインタＳＰｉ　。

Ｓ　Ｐ　ｉ＋１　ヲ相！ｊ’、に他方のアドレスを指す
ペアとして形成し、この組を１つのスペースポインタペ
ア５ＰＰＩで定義付ける。そして特徴点Ｐｉ　、　　ｐ
ｉｌｌに挟まれる空間ω１をこのスペースポインタペア
にて捉えるというものである。

そして、この部分空間ω１は、スペースポインタペア５
ＰＰＩで表現されたものとして取り扱い、その空間に関
係する図形処理をこのスペースポインタペアで部分的に
行うものであって、データの処理用が減少するのみなら
ず記憶すべきメモリ８漬の節約に貢献する。また、三次
元においては、この線分割が面による分割となるだけで
、その基本的な考え方は前記と同じである。

第３図（ｂ）は、このような図形データ処理を代表的な
図形について行った二次元の場合の−・例であって、図
形の各辺と分割線（一点鎖線）との間で分割して複数の
部分空間に分けたものである。

そしてその１−側の図は、特徴点を両側の「１点とした
場合であって、ド側の図は、各頂点を特徴点とした場合
である。なお、１・、の図においてω０．ωｑのスペー
スポインタペア５ＰＰｏ　、　　５ＰＰＱの場合は、相
ト方のスペースポインタか出国に存在する。

同様にド側の図面においてω０．ω１０のスペースポイ
ンタペア５ＰＰｏ　、　５ＰＰＩＯは、相り方のスペー
スポインタが士■に存在する。

さて、スペースデータ記憶部２ｄには、スペースデータ
としてこのような条件のもとで生成した一次元及び三次
元の各種のスペースデータが、テーブルとして記憶され
ることになるが、このテーブルは、どのような形態を採
ってもよく、その−例として示すテーブル形態が二次元
では第４図（ａ）、（ｂ）に見る特徴点テーブル２０で
代表され、三次元では第９図（ｂ）に見るような特徴点
テーブルで代表されるような形式であって、このような
テーブルが形成され、これらがスペースデータ記憶部２
ｄに数多く記憶されている。なお、このスペースデータ
は、このようなテーブルとして記憶するものに限定され
るものではない。

、スペースデータ処理部３は、演算処理装置１からアク
セスヲ受けて、スペースデータインタプリタプログラム
の実行によってこの特徴点テーブル２０．２１．２２等
を参！１（１するものであるが、演算処理装置ｌからア
クセスされるアドレスにより、実現すべき図形処理の種
別を選択して、スペースデータインタプリタプログラム
がスペースデータを検索し、解釈して対応する図形デー
タを発生する。そしてそれを演算処理装置１側に転送す
る。

演算処理装置１は、これを受けて、所定の図形処理をし
て第１図に見るＩ１０制御部４を起動し、例えばディス
プレイ７に所定のデータを転送して求められるデータを
表示する。

ここで、■１０制御部４は、スペースデータインタプリ
タプログラムが起動され演算処理装置１からアクセスが
有った場合に、所定のＩ１０処理を実＜１゛シて、図形
データを例えばディスプレイ７に転送して表示したり、
ディスク９に転送して記憶する等の処理をする。そして
演算処理装置１側への割り込み処理、演算処理装置ｌか
らの割り込み信−じの受は付は処理等を行う。

なお、この場合におけるＩ１０制御プログラム記憶部２
ｃには、いわゆるディスプレイ７、ディスク９．キーボ
ード８等との間でのデータ転送をする各種の処理プログ
ラムか記憶されている。

以１−の処理及び次の動作については、二次元のスペー
スデータでも、三次元のスペースデータの処理であって
も、また、ｎ次元のスペースデータ処理であっても、基
本的には同様なものである。

そして次元の相違は、対象とするスペースデータの内容
の相違として現れるに過ぎない。

次に、第２図（ａ）に従って、スペースデータの全体的
な動作について説明する。

さて、ある図形処理プログラム又は図形データがディス
ク９に記憶され、キーボード７からの所定の機能キーの
人力により、メモリ２の特定の記憶部９例えば図形処理
プログラム記憶部２ｅに読込まれる。そしてキーボード
８からスペースデータ発生処理のキーが入力されると、
演算処理装置１からスペースデータ処理部３に制御が渡
されてスペースデータ処理部３がスペースデータ発生プ
ログラム記憶部２ｂを参照してスペースデータ発生プロ
グラムを起動し、図形処理プログラムから図形スペース
データを生成するものである。

このようにスペースデータが生成されて記憶された後に
、この計算機／ステムが動作を開始すると、演算処理装
置１が動作して図形処理の制御プログラムが起動され、
この演算処理装置１が第２図（ａ）に見るプログラム制
御部１０として機能する。そして、図形処理プログラム
記憶部２ｅに記憶された対象となる図形処理プログラム
及び図形データが図形プログラムメモリ部１１として機
能し、これがプログラム制御部１０により解釈されて、
実行されて行く。また、スペースデータ処理部３は、対
応する図形処理プログラムが起動されたときには、演算
処理装置１から所定の指令に応じて図形データ変換処理
部１２として機能する。

さて、プログラム制御部１０は、図形処理プログラムの
内容をプログラムメモリ部１１から読出し、この読出さ
れた内容を解釈して実１１’する。ここでの実行処理の
際に、プログラド制御部ＩＯは、例えば隣接図形のサー
チとか、図形の市なり制御とか、範囲指定の図形の切り
たし、図形間１ｓの論理処理等の部分的な図形処理が発
生したときに図形データ変換処理部１２にその制御を渡
す。

図形データ変換処理用＜１２では、プログラム制御部１
０からの指令に従って、そのデータからスペースデータ
生成処理であるか、スペースデータによる参照変換処理
であるかを判定し、この判定に応じてインタプリタプロ
グラムか、スペースデータ生成プログラムのいずれかを
起動して制御を開始する。

ここで、スペースデータ生成プログラムと判定されて、
これが選択され動作したときには、制御プログラム１０
側から図形データの転送を受けてそのデータから第４図
（ａ）、（ｂ）又は第９図（ｂ）に見るような特徴点テ
ーブル２０．２１゜２２等を図形の各Ｄ’ｉ点対応（又
は選択された特徴点対応）に生成することになる。

−ツバインタプリタプログラムは、生成したスペースデ
ータのインタプリタとして指令に対応した処理を実行し
て、制御プログラム１０側との間でデータ転送を行う。

ここでは、これは、変換制御プログラム部１４と図形プ
ログラムメモリ部１５とで実現され、図形プログラムメ
モリ部１５は、スペースデータに対する各種の検索処理
１図形の論理処理等の部分的な処理のデータ生成のため
のスペースデータ変換処理プログラム群が記憶され、こ
れらにて構成されている。そして例えば変換制御プログ
ラム部１４は、そのアクセスアドレスによって、その処
理を規定するスペースデータ変換処理プログラム群を図
形プログラムメモリ部１５の中から選択する。

そして、インタプリタプログラムの動作としては、第２
図（ｂ）のステップ■に見るように、データＡ（又は指
令、以下同じ）をプログラム制御部１０から受は取った
と仮定するとると、ステップ■で例えば対応するスペー
スデータ処理を実行し、ステップ■にて割り込みを発生
する。そして次の動作として、ステップ■にて割り込み
発生機かを判定して、ステップ■にて、スペースデータ
処理の結果発生した図形処理データＢを出力してプログ
ラム制御部１０叉は図形プログラムメモリ部１１の図形
処理プログラムに渡す処理をする。

この場合のステップ■のスペースデータ処理は、−次元
では、第４図（ａ）、（ｂ）に見る特徴点テーブル２０
．２１’Ｖを参照し、二次元では第９図（ｂ）に見る特
徴点テーブル２２等を参照して、そのスペースポインタ
ペア等を検索することにより１１・われる。

一方、プログラム制御部１０の動作としては、プログラ
ム制御部１０か変換制御プログラム部１４を対象として
図形データ変換処理部１２をアクセスした場合には、第
２図（Ｃ）に見るように、メモリの特定アドレスをアク
セスしてデータＡを？７Ｉて、ステップ■ａで図形デー
タ変換処理部１２に対してデータＡを出力する。

次に、ステップ■ａにて図形データ変換処理部１２から
の割り込み信号待ちの、待ちループに人る。ここで図形
データ変換処理部１２から割り込み信号を受は付けると
、ステップ■ａにてデータ人力として図形データ変換処
理部１２から図形処理データＢを受は付けてプログラム
制御部１０を介して図形プログラムメモリ部１１の図形
処理プログラム側へと渡す。なお、この場合図形データ
変換処理部１２から直接図形処理データＢを図形処理プ
ログラムに渡すようにしてもよい。

次に、第４図（ａ）の二次元における特徴点テーブルの
データを構成するためのスペースデータについて第５図
（ａ）、（ｂ）を参照して具体的に説明する。

まず、第５図（ａ）に見る二次元図形Ａ、　　Ｂ。

Ｃ９１）を図形データとして処理（例えばディスプレイ
］−に表示）し、所定の処理を行う場合を例として説明
すると、これらの図形に対して第５図（ｂ）にあっては
、Ｘ−Ｙ座標系をこれらの置かれた空間に採り、各図形
の頂点を通ってＸ軸に昨直な線で図形の置かれた空間を
分割する。たたし、この場合の空間分割の条件としてこ
こでは分割空間の数を抑えるために各頂点の周りの門な
空間（各図形の辺により挟まれる各か鈍角となる側に対
応する空間）を対象として行い、凸な空間（各図形の辺
により挟まれる各が鋭角となる側に対応する空間）につ
いては空間分割を行わないものとする。

ところで、第５図（ｂ）のようにＸ−Ｙ座標系の場合に
あっては、スペースポインタペア５ＰＰｉで表現される
部分空間の形状は、次の２つの条件を満たせばよい。

（ＩＩＳ分空間ω１のｘ”、ｘ一端境界Ｂｘ　　Ｉ−に
はＳＰ、Ｐｉを接続すべきＤ′１点が必ず１個づつ存在
し、Ｂｘは５ＰＰＩで指された［＋’ｉ点からＹ座標に
沿って引いた線であること。

（２）ωＩのＹ方向の外形線Ｂｙ”、Ｂｙ−は図形辺よ
りなり、かつωｉの内部には図形辺（又は点）が存在な
いこと。

このような条件のもとに図形の各辺と分割線（一点鎖線
）との間で分割された部分空間をωＩ　（ｉ＝１〜ｎ　
）として表したものが第５図（ｌ〕）である。なお、こ
の分割線は、゛仮想線であり、データとしては取り扱わ
れないものである。すなわち各分割空間の分割線は説明
の都合」二挿入されているに過ぎない。

さて、図中、各部分空間には、そのＸ軸方向に対応する
両側に必ず特徴点が存在し、これら両側の２つのポイン
タのペアは、それぞれ分割された部分空間に１対１に対
応することになる。そこでこの頂点ペアを部分空間を指
標するデータとして処理することがｉ＋Ｊ能となる。な
お、図中、「・」が頂点であり、実線で示す部分が各図
形の辺である。

このようにして分割された図形の内外にある部分空間ω
Ｉ　　（ｉ＝１−ｎ）を表すことになるポインタペアを
ここではスペースポインタペア（ＳＰＰ）と呼ぶもので
あって、これらを各部分空間ω１　（ｉ＝１〜Ω）に対
応して番号付けて５ＰＰｉ（ｉ＝１〜ｎ）で表すもので
ある。

図中、相互に矢線で結合したものがこのスペースポイン
タペア５ＰＰＩであり、各部分空間ωＩとこのスペース
ポインタペア５ＰＰｉ、：が対応していることが理解で
きよう。

ここで、部分空間ωｉの外形線の少なくとも一方は、図
形の辺の一部又は全部に対応している。

この外形は、次のような処理を行うプログラムにて検索
される。例えばωｌを例に採って説明すると、スペース
ポインタペアＳ　ＰＰ／から白抜き矢線のように反時ｉ
ｊｌ方向に回転サーチによって順次サーチして行き、サ
ーチした各スペースポインタペアがその部分空間のＸ方
向の範囲に入るか（又は含むか）否かを判定することに
より−に側の外形を決定する。その結果として上側の外
形を探し出すことができる。

また、時計方向に回転させて同様な処理をすれば、上側
の外形を決定できる。さらに外形の長さを知りたいとき
には、今求めた外形となる辺の各頂点の座標値を参！ｔ
（ｌ　して算出することにより血中に求めることができ
る。しかもこのように部分空間の集合として各図形及び
その図形と隣接する図形との関係を表現できることによ
り、図形同上の関係、特にその論理処理９図形の全体／
部分の削除、その移動、変更、追加、更新処理等が丘１
単に１工能となる。なお、これらの図形処理としては後
述する属性情報を利用して処理することによりより効率
的に処理することが可能である。

以−１−のようにスペースポインタペア５ＰＰｉにより
部分空間を表すことにより、図形をスペースポインタペ
ア５ＰＰＩで検索して処理することが可能であり、多く
の図形データを特別に全体的な演算処理で求めなくても
部分空間中位でのデータ処理として種々の図形データを
得ることができる。

ところで、このような検索処理に対処するために、この
スペースポインタペアＳＰＰ＋は、二次元では、第４図
（ａ）、（ｂ）に見るような内容の特徴点テーブル２０
．２１等として管理して記憶することが好ましい。

次に、第４図（ａ）に見る二次元の特徴点テーブル２０
の内容について説明する。

この特徴点テーブル２０は、各頂点を識別する符号又は
番号で管理されていて、メモリ２上の所定の対応するア
ドレス位置に記憶されているものであって、ここの例で
は、原則として８行の記憶領域を持つテーブルとして構
成されている。

そして、その各記憶位置は、第４図（ｃ）に見る図形に
対応しているものであって、その上側の辺を基準として
反時計回りに順次データが記憶されている。すなわちそ
の第１行［１は、図形の基準辺ＥＰｏのデータ記憶位置
、第２行［１は、スペースポインタペア旧のデータ記憶
位置、第３行ｒ１は、反時計回りに回転した場合の次の
辺ＥＰ、のデータ記憶位置、第４行［１はスペースポイ
ンタＳ　Ｐ　’ｍのデータ記憶位置、第５行［１は、ス
ペースポインタＳＰεのデータ記憶位置、第６行１１は
、スペースポインタＳＰｉのデータ記憶位置である。そ
して第７行目、第８行［１は、それぞれこの頂点のＸ。

Ｙの座標情報の記憶位置である。

ここでは、スペースポインタｓｐ、ｓｐ’、ｓＰＣ，Ｓ
ＰＬは、それぞ、れこれらと組になる隣接するスペース
ポインタのアドレスを指してペアを組みそれぞれスペー
スポインタペアが５ＰＰＩとして形成されることになる
。

ところで、スペースポインタペア５ＰＰＩのほかに各辺
について同様にその両側の頂点に対するペアを採るため
の辺ポインタＥＰｉ　　（ｉ＝ｌ〜ｎ）として特徴点テ
ーブルに記憶し、その辺ポインタペアをＥＰＰｉ　　（
ｉ　＝　１−ｎ）で表すことにする。

このようにスペースポインタペア５ＰＰＩと辺のポイン
タペアＥＰＰＩ　とを採ると、通常は、１頂点には６木
のポインタが必ｄとなり、それだけ存在している。

ここで、この特徴点テーブル２０の最初の欄Ｖ／Ｃは、
図形における頂点か交叉点かを判定するフラグであって
、第４図（ｅ）に見るようにこれが”１゛のときには頂
点を、そしてこれが”０”のとき交叉点を意味する。第
２欄のＫＩＮＤは、辺ポインタペアかスペースポインタ
ペアかの種別を表す符号を意味し、第３欄のＡＴＴＲ，
は、その属性を意味し、第４欄のＰＯＩＮＴＥＲは、ペ
ア相りの存在するアドレス位置を示している。なお、第
４図（ｂ）の特徴点テーブル２１に見るようにこの空間
属性９例えば色とか、その空間の中に入るべきデータの
情報を示すデータアドレスとか、その空間が持っている
定義情報等は、Ｘ方向でない頂点の特徴点テーブル２１
のＳＡとして記述することもできる。このようにＳＡを
設ければ、ある図形の属性を検索する場合には、ＳＡは
、スペースポインタペアの属性欄であるＡＴＴＲ，を参
照することで簡単に探し出すことができる。この方式は
、本来なら接続先がなくて空欄になるはずのＸ方向でな
い頂点のポインタ（ＰＯＩ　ＮＴＥＲ）欄を空間属性Ｓ
Ａの表現用に６効活用するのでメモリ使用効率がよいが
、第４図（ｇ）に示すようなＸ方向でない頂点を持たぬ
図形では、ＳＡを付加する場所がなくなるので、同図に
示すように、図形の特徴点テーブルの外ｍくにＳＡを増
設する等の対策を要する。

なお、これら特徴点テーブル２０．２１のデータ構成の
具体的な一例を挙げれば第４図（ｆ）に見るようなもの
となる。

以上が二次元のスペースデータの内容である。

以上の説明をもとに、次に、三次元のスペースデータに
ついて説明する。

三次元のスペースデータは、二次元スペースデータの拡
張であり、三次元空間を部分＼ｒ体体間間分割して部分
立体空間をスペースポインタペア５ＰＰＩで表現する。

三次元スペースデータ（又はスペースデータファイル、
５ＰＦ）の基本的性質は、二次元の場合と同じく隣接７
重なり空間の直接的な検索が部分処理で１′：ｆＪ速に
できることである。

すなわち、 （１）ｉ’ｌ＜分処理による干渉チェック他、三次元高
速論理操作。

（２）高速隠れ面消去表示とその部分修正（スタ分隠れ
面消去）。

（３）三次元空間における図形の運動と衝突の検出。

等が効率的に実行できる。

以上の処理は、二次元と同様に本質的に部分処理である
ため、図形全体の規模の増加によらず、高速処理が可能
で、オンライン対話処理ができる。

二次元の場合の例として挙げた第３図（ｂ）の例に対比
させて、二次元空間をｘ−ｙ−ｚの座標空間として捉え
た場合について説明する。

それは、第６図（ａ）に見るように、三次元の空間分割
とそのスペースポインタペア５ＰＰＩ　ノ表現が次のよ
うなルールに従って行われる。

（１）　Ｘ境界面Ｂｘ 図形をＺ方向正負に投影してできる角柱状の空間（第６
図（ａ）参照）において、二次元の場合と同様に頂点を
中心としてＺ軸の回りに凹角空間が存在するとき、その
頂点を通りＸ軸に垂直でＹ−２面に平行な而（第６図（
ａ）の例では、平面）で凹角空間を区分し、この而をＸ
境界面Ｂｘとする。

（２）Ｙ境界面Ｂｙ 図形を構成する各面の辺（Ｅｄｇｅ）をＺ方向正負に投
影するときのＺ軸に平行な而（第第６図（ａ）の例では
、平面）を部分空間のＹ方向境界面Ｂｙとする。ここで
而Ｂｙの２方向への広がりは、Ｚ方向（トド）にある隣
接面まで伸びて、そこで終わることになる。

（３）Ｚ境界面Ｂｚ 部分空間の上底面又は下底面としての境界面Ｂｚは、当
該空間にＺ方向に隣接する図形そのものである。

以１−２のことから、これら３つのルールに従って分割
された部分立体空間は、一般に、十、底面Ｂｚとド底面
Ｂｚが３次元図形のにド面で、ｘ−ｙ面に対して重訂と
なる角柱の形状を採ることになる。

さて、三次元スペースデータにあっても、二次元スペー
スデータと同様に上記のルールによって分割された部分
立体空間をスペースポインタペア５ＰＰｉによって表現
する。このスペースポインタペア５ＰＰＩは、第３図（
ｂ）及び第５図（ｂ）に見てきた二次元の場合と同様に
部分立体空間のＸ＋端とＸ一端の頂点間に張られること
になる。なお、第６図（ａ）中、Ωは、二次元のωに対
応する三次元におる部分立体空間を表している。また、
第６図（ｂ）は、第５図（ｂ）に対応させた場合の三次
元の＼ｒ体図形を簡略化して表現している。

ここで、小波なことは、三次元にあっては、ある図形の
辺が他の図形の辺に直接には交叉してぃな（でも他の図
形の辺の蔭になるような蔭の交叉が生じることである。

この蔭の交叉は、第６図（ｂ）に見るＣ／の部分がそれ
である。

第６図（Ｃ）及び（ｄ）は、この蔭の交叉を説明したも
のであって、第６図（ｄ）は、第６図（Ｃ）の図形をＺ
軸方向へ投影した場合の図である。

ここで１Ｃ／　　Ｃ１’　＊　　Ｃ２Ｃ２”が蔭の交叉
となっている。そしてこの交叉線の周りは、四方の部分
空間がつき合わせの形になり、かつ、そのうち対角の二
つはＸ軸方向に尖る空間の頂点となり、これらに対応し
てそれぞれスペースポインタペア５ＰＰｉが設置される
ことになる。

さて、三次元の場合には、スペースポインタＳＰとその
スペースポインタペア３ＰＰｉ、辺ポインタＥＰとその
辺ポインタペアＥＰＰｉのほかに、立体図形の表面の属
性を規定する情報があったほうが望ましい。そこでこれ
らの面についてのポインタペアを而ポインタペアＦＰＰ
Ｉで表すことにし、これを新たな情報として加える。

また、これらについての特徴点テーブル」二の情報を他
の情報とを区別する意味で、それぞれ而ポインタペアＦ
Ｐとして取り扱う。そして、その而ポインタペアは、Ｆ
ＰＰｉ　として表現する。これは、第７図に見るように
、物体の表面に図柄が存在するような場合に打効である
。

このようなことを考慮して、第８図（ａ）に見るような
、ある三次元図形を想定して、二次元に見る第４図（ｃ
）Ｋは（ｄ）に対応させてそのスペースデータを展開し
て見ると、第８図（ａ）の頂点ａＯは、第８図（ｂ）に
見るような形態となる。そしてこのような立体図形の頂
点とその特徴点テーブルとの関係を示すと第９図（ａ）
及び第９図（ｂ）の特徴点テーブル２２となる。

ところで、二次元の場合でも、三次元の場合であっても
、部分的なデータ処理を実現する関係か□　　ら、特徴
点テーブルは、い（つかの部分空間の中からその１つ１
つの空間を検索できるルールに従ってそれぞれの情報が
形成されていなければ、そのデータ処理１・、意味がな
いものとなる。そこで三次元の場合には、この１つ１つ
の部分立体重間を特定情報に対応させる。関係を樹〜ｙ
するための一義的な空間規定ルールが必要となる。

二次元では、第４図（ａ）、（ｂ）で示したごとく、反
時計回りループ状の特徴点テーブルによって「１点の回
りのＥＰとＳＰを一義的に表現するとともに、両者の隣
接性を完全に表現でき、これによって回転サーチの高速
化も達成された。しかし、三次元では、第９図（ａ）の
ごとく、辺ＥＰ１に隣接する空間が左右それぞれ複数個
存在するため、上記のような三次元ループ状のテーブル
では、隣接性の表現はできない。

この問題を解決し、「１点を発する辺ＥＰＩの数によら
ず、かつ辺ＥＰＩに隣接する空間ＳＰや而ＦＰの数によ
らず隣接性を表現できる汎用的な三次元特徴点テーブル
の方式を第９図（ｂ）に示す。

ここでは、特徴点テーブルは、辺ＥＰの数だけＥＰブロ
ックを！１ｐべたものであり、辺ＥＰＩ　ブロンりには
頂点ＶからＺ軸＋側をヒにしてＥＰｉの辺を眺めたとき
、ＥＰＩの左側に隣接するＳＰ２とＥＰ２　（ｚはこれ
らＳＰ２とＥＰ２をＺ軸１−側から数えた順序、Ｚ＝１
．２．　　・・・、）を順に設置する。ＥＰｉブロック
に入れることによってＥＰｌとその左側のＳＰ２．ＥＰ
２の隣接性が表現される。

これらＳＰ２．ＥＰ２とさらにその左側の辺ＥＰｊ　、
ＥＰｋとの隣接関係は図示のごとく各５Ｐ２１ＦＰ２に
付属してその左側を指す同じくテーブル内ポインタＬＰ
　（Ｌｅ　ｆ　ｔ　　Ｅｄｇｅ　　Ｐ。

１ｎｔｅｒ）と逆に各ＥＰｊ　、ＥＰｋに付属してその
右側を指す同じくテーブル内ポインタＲＰ”（Ｒｉｇｈ
　　５ＰｏｒＦＰ）の相互の指し合いで表現する。

一個のＥＰの右側にも一般にはＳＰ、ＦＰがＺ方向に複
数重なって隣接しているので、これに対応してＲＰにつ
いてもＥＰブロックの中に図のようにＺ軸＋側から並べ
れば完全な表現ができる。

この方式により三次元回転サーチがサポートできる。

すなわち、このように各辺に対応して頂点テーブルを分
割して管理すると、隣接するＺ軸の１・、トノ」向のつ
ながりは、各ブロック内部の・１νび方で縦　　−同転
サーチが可能となるが、Ｚ軸ｌ一方からドを見た場合に
各部分空間の左右両隣の関係はついては、そのままでは
できないために、三次元の場合の横方向の回転サーチと
して左右関係の関連つけるためにＬＰ、ＲＰの情報を設
けている。

このＬＰ、ＲＰの情報は、各スペースデータであるスペ
ースポインタペア５ＰＰ１．辺ポインタペアＥＰＰ！、
ポインタペアをＦｐｐｉについて左右の関係付けをする
ものとしてそれぞれの情報のＬＰ。

ＲＰ欄に記述されることになる。そしてそのポインタペ
アにより相！１：に相手のアドレスを示すことで連結す
る。なお、この情報ＬＰ、ＲＰをここでは、連結情報と
呼び、そのポインタペアを連結ポインタペアと呼ぶこと
にする。

このようにして第９図（ａ）の頂点に対して構成した特
徴点テーブルが第９図（ｂ）に示すものであって、結合
矢線は、それぞれ連結ポインタペアＬＰ−ＲＰによる左
右方向のつながり（Ｘ−Ｙ面方向の面内でのつながり）
を示している。

したがって、あるスペースポインタペア５ＰＰｉの左側
の連結情報ＬＰが、ある辺ポインタペアＥＰＰｉ又はポ
インタペアをＦｐｐｉの右側の連結情報ＲＰと接続関係
（ＬＰ−ＲＰのポインタペア）を組むことになる。なお
、１・、上方向のつながりは、弔に、隣接する各境界面
Ｂｙの左に位置する部分空間及び面のスペースデータを
順次Ｚ軸＋■側の１ユの方向から順次結合しただけであ
る。また、この接続関係にあるスペースデータが何であ
っても、その内容については、そのブロックのＫ　Ｉ　
Ｎ　Ｄの欄の情報を参照することで、スペースポインタ
ペアＳＰＰ＋か、辺ポインタペアＥＰＰｊか、面ポイン
タペアＦｐｐｆかを認識することができる。

このような特徴点テーブル２２を構成するこきで、三次
元特徴点テーブルは、二次元特徴点テーブルと同様に順
次隣接サーチをすることが可能となり、一義的な部分空
間や面の部分処理が可能となる。

なお、この場合のサーチの仕方としては、各辺ブロック
ト、上方向に辿るＺ軸の」−上方向での回転サーチとな
るスペースデータのポインタペアから左右の連結情報ポ
インタペアＬＰ−ＲＰを辿って展開するＺ軸にル直な回
りでの回転サーチとの２種類が存在し、実際の図形処理
は、これらが組み合わされてサーチが行われる。

ところで、この例では、二次元と特徴点テーブル２２は
、その座標値（ｘ＋　　ｙ、ｚ）が先頭位置に配置され
、その次に基準となる辺ＥＰｏのブロックから順次特徴
点テーブルのブロックが・１ｆぶ構成を採る。また、第
９図（ｂ）のＥＰｏブロックのＳＡは、二次元の場合と
同様に、その空間又は面の属性を示すスペースデータで
ある。なお、この場合にも、Ｘ方向でない「１点が存在
しない図形の場合には、第４図（ｇ）で示した二″１次
元の場合と同様にＳＡを増設する必要がある。

第９図（ｃ）、（ｄ）は、多面体の凸頂点における場合
のスペースデータを前記第９図（ａ）。

（ｂ）に対応して展開した場合のスペースポインタペア
５ＰＰＩ、辺ポインタペアＥＰＰ１．　ポインタペアを
Ｆｐｐｉ等の関係とこれに対する特徴点テーブルの関係
の例である。−・方、第１０図（ａ）は、凹なる空間を
特徴点テーブルの中で表現する場合の例であって、二次
元の場合と同様にスペースポインタペアＳＰに＋ｒ＋Ｃ
＋Ｌ、の添え字を設けて区別することになるが、特徴点
テーブルのブロックの情報量が多くなるため、凹なる部
分立体空間を持つテーブルブロック欄が大きくなる欠点
がある。

そこで、凹でない他のブロックの空き欄に凹のブロック
の特定の情報を記憶して、これを参照できるようにした
ものである。

すなわち、第１０図（ｂ）の特徴点テーブル２３におい
て、ＥＰｏブロックの情報をＥＰｔブロックに記憶する
ものであって、このような情報は、ＥＰｔブロックに本
マークを付けて表示されている。この本マークの情報は
、本来は、ＥＰＯブロックに記憶される情報であって、
その記憶される位置は、連結情報ポインタペアＣｐ−ｒ
ｐで示される。

さて、第１１図（ａ）は、二次元において、図形ＥとＦ
とが市なった１■なり図形を示すものであって、このよ
うな場合のスペースポインタペアを構成する特徴点テー
ブルとしては、第１１図（ｂ）に見るように、それぞれ
にそれぞれの図形を表すものとしてｒｅ、ｆＪの色情報
とか、図形コード等の空間属性を付加して、これを例え
ば特徴点テーブルのＡＴＴＲ，の欄に設ける。具体的に
は、特徴点テーブル２０のＡＴＴＲ，の欄の中を複数の
空間属性欄にわけて、５−ＡＴＲとして表示するか、特
別にこのような欄をスペースポインタ対応に追加する。

また、このよな空間属性としてＡＴＴＲ，の欄のビット
のうち数ビットを空間属性を示すものとして割り当てて
もよい。なお、この空間属性は、Ｘ方向でない頂点の特
徴点テーブルのＳＡとして表示してもよい。ただし、そ
の場合には、第４図（ｇ）に示すようにＸ方向でない頂
点がないと空間属性ＳＡが設置できないので、同図に示
すようにＳＡを外部に増設する必要がある。

このようにすることにより、図形がｆｆｉ？ｓｔしてい
れば、そのスペースポインタペアを構成する特徴点テー
ブルの属性欄であるＡＴＴＲ，をプログラム処理にて参
照することに上り簡明に探し出すことができる。

次に、−次元における多色図形を例に採り特徴点テーブ
ルの関係を説明すると、第１２図（ａ・）。

第１２図（ｂ）のごとくなる。なお、各テーブルの座標
データ専は省略しである。

ところで、この例のように空間をＸ方向に昨直な線で分
割して部分空間を形成することにより、あるスペースポ
インタペアを構成する特徴点テーブルを発生させ、スペ
ースデータとし、これを参照して、それにペアとなる特
徴点テーブル、そして次のスペースポインタペアの特徴
点テーブルと順次検索するとＸ方向でスキャンして図形
の検索が可能となる。しかもスペースポインタペアから
辺ポインタペアを参照してそれにペアとなる特徴点テー
ブル、次のスペースポインタペアそしてその向こう側の
辺ポインタペアというように検索すれば、Ｙ方向でスキ
ャンして図形の検索が１ｉＪ能となる。したがって、必
要なデータの検索まで短時間で処理できる。しかも１つ
の特徴点テーブルでスペースポインタペアを選択すれば
、隣接図形の状態を調査することが簡Ｑｉにできるもの
であり、特徴点テーブルに種々の属性情報を付加すれば
、図形のＡＮＤ処理、ＯＲ処理等論理動作をはじめとし
て多種多様の処理がｉ−＋Ｊ能である。

また、第１９図に示す二次元図形の衝突の予測のように
１つの図形を移動させた状態で隣接図形との関係を見る
ようんな場合には、このようなスペースデータシステム
が特に有効であって、移動図形の座標値を時間の関数と
して時間とともに移動させて隣接状態をスペースポイン
タペアによりサーチし、衝突が発生したり、空間の分割
の仕方が変化したときには、新しいスペースデータを変
化した空間部分において生成して順次そのスペースデー
タを検索することに上り而Ｃ４’−に実現できる。

以」−のことは、Ｅ次元の第９図（ｂ）に見る特徴点テ
ーブル２２等においても同様であることは容易に理解で
きよう。

ところで、重複図形についてＥ次元で考えて見ると、ま
ず、第１１図（ａ）、（ｂ）に対応する市なり図形とし
ては、第１３図のような四面体をもって、その関係とし
て表すことができる。そして第１２図（ａ）、（ｂ）ニ
ー次元の関係については、Ｅ次元でも同様な関係となる
が、その図形関係か複雑となるため、ここでは割愛する
。

次に、第１４図（ａ）、第１４図（ｂ）、第１４図（Ｃ
）、第１４図（ｄ）に従って、まず、二次元におけるス
ペースポインタペアの生成の仕方について説明する。

最初に、第１４図（ａ）に見るように、ある特徴点Ｐを
基準点として１つ挿入する。これは、隣接する特徴点が
存在しない。そこで最初は、特徴点Ｐのスペースポイン
タペアの右側５ＰＣ２と左側３　ｐｃ＋とが相互にスペ
ースポインタペアを形成するようにそれぞれ相〃のアド
レスを指すループ状の形態で入力する。

なお、他のポインタ部分は、空白とするか、辺のスペー
スポインタペアについても同様にその特徴点テーブルの
範囲でループ状形（６）としておく。

そして、第２の特徴点として特徴点Ｑが挿入されたとき
に、特徴点Ｐの前記ループを解除して特徴点Ｑ　’−の
間でスペースポインタペアを形成する。

ここで、この特徴点Ｐ、　Ｑのスペースポインタペアの
生成としては、特徴点Ｐと特徴点Ｑの間にあるペースポ
インタペアは、特徴点Ｑのスペースポインタ情＋％！（
右側のスペースポインタ５ＰＣ２）が記憶されている位
置アドレスが特徴点Ｐの特徴点テーブルの対応するスペ
ースポインタＳＰ（左側のスペースポインタペアＳＰ”
）の位置に記憶され、特徴点Ｐのスペースポインタ情報
（左側のスペースポインタ５ＰＣ１）が記憶されている
位置アドレスが特徴点Ｑの特徴点テーブルの対応するス
ペースポインタＳＰ（！ｉ側のスペースポインタＳＰ”
）の位置に記憶される。

同様にして、特徴点Ｐの特徴点Ｑに対する外側にあるペ
ースポインタペアは、特徴点Ｑのスペースポインタ情報
（左側のスペースポインタＳＰＣ’）が記憶されている
位置アドレスが特徴点Ｐの特徴点テーブルの対応するス
ペースポインタＳＰ（右側のスペースポインタペアＳＰ
Ｃ’）の位置に記憶され、特徴点Ｐのスペースポインタ
情報（右側のスペースポインタＳＰｃ勺が記憶されてい
る位置アドレスが特徴点Ｑの特徴点テーブルの対応する
スペースポインタＳＰ（左側のスペースポインタＳ　Ｐ
ｃｔ）の位置に記憶される。

次に、基準点に基づきスペースポインタペアを生成する
場合について説明する。

第１４図（ｂ）に見るように、第１．第２の基準点をＸ
−Ｙ座標系の原点とω（Ｘ＝＋■、ｙ＝−）−ｏｏ　）
の位置にそれぞれ採った場合には、ある特徴点Ｐの隣接
点は、第１の基準点０と第２の基を点■が隣接点となる
ので、これら２点との間においてスペースポインタペア
が形成される。

したがって、そのスペースポインタペアの生成として、
ある特徴点Ｐの第１の基準点Ｏに対するペースポインタ
ペアは、第１の）に　準焦Ｏのスペースポインタ情報が
記憶されている位置アドレスが特徴点Ｐの特徴点テーブ
ルの対応するスペースポインタＳＰの位置に記憶され、
特徴点Ｐのスペースポインタ情報が記憶されている位置
アドレスが第１の基準点０の特徴点テーブルの対応する
スペースポインタＳＰの位置に記憶される。

同様にして、特徴点Ｐの第２の基準点■に対するペース
ポインタペアは、第２の基準点ωのスペースポインタ情
報が記憶されている位置アドレスが特徴点Ｐの特徴点テ
ーブルの対応するスペースポインタＳＰの位置に記憶さ
れ、特徴点Ｐのスペースポインタ情報が記憶されている
位置アドレスが第２の基準点ωの特徴点テーブルの対応
するスペースポインタＳＰの位置に記憶される。

このようにして、最初の特徴点についての特徴点テーブ
ルを作成し、スペースポインタペアを生成する。

次に、第２の特徴点として特徴点Ｑが追加されて、この
第２の特徴点Ｑが第１の特徴点Ｐと原点０との間に挿入
されたと仮定すると、特徴点Ｐに隣接する点は、特徴点
Ｑと第２の基準点■とになる。そして特徴点Ｑは、第１
の基準点である原点Ｏと特徴点Ｐとに隣接する。そこで
特徴点Ｐのスペースポインタペアは、今度は、その特徴
点Ｑに対するペースポインタペア七して、特徴点Ｑのス
ペースポインタ情報が記憶されている位置アドレスが特
徴点Ｐの特徴点テーブルの対応するスペースポインタＳ
Ｐの位置に記憶され、特徴点Ｐのスペースポインタ情報
が記憶されている位置アドレスが特徴点Ｑの特徴点テー
ブルの対応するスペースポインタＳＰの位置に記憶され
る。しかしその＋ψ側のスペースポインタペアについて
は変更がない。

一方、特徴点Ｑについては、隣接する特徴点Ｐに対する
ベースポインタペアとして、特徴点Ｐのスペースポイン
タ情報が記憶されている位置アドレスか特徴点Ｑの特徴
点テーブルの対応するスペースポインタＳＰの位置に記
憶され、特徴点Ｐのスペースポインタ情報が記憶されて
いる位置アドレスが特徴点Ｑの牛、）°微意テーブルの
対応するスペースポインタＳＰの位置に記憶される。

同様にして、特徴点Ｑの第１の基準点Ｏに対するベース
ポインタペアとして、第１の基準点Ｏのスペースポイン
タ情報が記憶されている位置アドレスが特徴点Ｑの特徴
点テーブルの対応するスペースポインタの位置に記憶さ
れ、第１の基準点Ｏのスペースポインタ情報が記憶され
ている位置アドレスが特徴点Ｑの特徴点テーブルの対応
するスペースポインタの位置に記憶される。

以−１１は、図形データベースへの点データの？ＪＪ　
ｊｔ１１人力の方法であるが、同様な手法は、図形デー
タベースに複数の図形が既に入力されている場合にも同
様に成立する。

次に、以１ユの方法で入力した点をもとにして図形の辺
を人力する方法について二次元の場合から説明する。

まず、第１４図（ｃ）及び第１４図（ｄ）に従って図形
Ａの人力について説明すると、図形Ａの人力は、前述の
点の入力処理により１つの頂点ａ０を入力した後、第１
４図（ｄ）の（Ｉ）から（■）に見るよに、頂点ａｏか
ら出発して図形Ａの辺に沿って折れ線ａｏｔを順に伸ば
しながら、それに伴って起こる空間分割の変化（イベン
トＥｊと呼ぶ）に対処してスペースポインタペア３ＰＰ
ｉヲ１１１ｎ次メンテナンスし、図形Ａの囚を一巡し終
わったら、図形Ａの内部の空間のスペースポインタペア
５ＰＰｊに図形Ａの図形名や色など空間属性を付加して
完γする。

以上の手順を図形Ａの展開処理と呼ぶ。ａｏｔの伸張に
伴なうイベントは基本的には「イが伸びていって、その
先端ｔが周囲の空間の境界ＢＸ又はＢｙを突き抜ける時
点のみに発生するので、スペースポインタペア５ＰＰｉ
のメンテナンスは間欠的でよい。

起こり得るイベントの種類は、上述のａｏｔの境界ＢＸ
、ＢｙのＨ通に、ａｏｔの始点と終点の処理を加えて第
１４図（Ｃ）のようになる。

イベント処理プログラムは、次に発生するイベントの種
類を判定してポインタの接続変更をすればよい。イベン
トの種類を減らして取り扱いを部用化するために、第１
４図（ｄ）に示すように最初に追加図形の辺をすべてＸ
−からＸ＋力方向の折れ線に分解して、ａＯｔの伸張を
すべて一方向に限定する方法をとってもよい。

展開処理は、１）；ｊ述の回転サーチ等と同じく、入力
図形辺の付近の空間（ｌｏｔの伸張処理）及び、入力図
形内部（空間属性付加）に限定されたｏ　−カル処理で
あるから、先の点人力の高速化（道しるべ処理）と合わ
せて、スペースポインタファイル（ＳＰＦ）のメンテナ
ンス時間は、ｏ（Ｎ’）程度、ＳＰＦ全体の初期生成時
−ドも０（Ｎ）程度高性能が見込まれる。ただし、特殊
ケースか１１！（視でき、かつ人力図形内部の空間属性
を付加すべき図形空間数が全項点数Ｎと無関係なことが
必要である。

以１の結束からＳＰＦは、［−記条件付きではあるが、
少な（ともオーダーの［−では、オンライン用にも、バ
ッチ処理用にも適した高性能図形データｅベースとなる
ことか期待される。

なお、展開とは逆に削除処理があるが全く逆のなので説
明を省略する。

次に、三次元のスペースポインタペア５ＰＰｉの生成処
理について説明する。

三次元の場合、その生成処理時間が特殊ケースを無視で
きるならば、ｏ（Ｎ）のオーダーであり、一部修１［：
、等メンテナンス処理は、同じ＜ｏ（Ｎ’）（Ｎと無関
係）と高速である。

三次元ＳＰＦの生成も二次元の場合と同様ＳＰＦへの図
形の１個づつの追加の繰り返しで実現する。

第１５図（ａ）に示すように、図形Ａの入力は、最初に
１つの頂点ａＯを後述するように入力した後、図形の辺
よりなるワイヤーフレームを入カシ、次にこれに而を張
り、最後に内部空間を空間属性で埋める（　Ｓ　ＰＰに
属性を付加する）段階的な方法が考え易い。

なお、１個の図形を追加する方法は、−１−記の他、点
ａＯを人力してからワイヤーフレームを作らないで而を
直接人力する方法や、点ａＯから筏の体積を膨張させて
１ｊ・く方法“ｌ・も考えられる。

ＳＰＦに点ａｏ　　（ｘａｏ＋　Ｙａｏ＋　ｚａｏ）を
追加するｒＸ法は、基本的には、二次元と同じで、ます
、点ａＯを含む空間５ＰＰａｏをＳＰＦの中から検索、
切断し、点ａＯを継ぎ込めばよい。５ＰＰａＯを見付け
るには、最初に任意のＳＰＰθをとり、そこからＸ座標
の範囲がＸａＯを含む空間に達するまでＸ方向に隣接空
かを辿り、次は、Ｘａｏを含む空間ばかりをＹ方向に辿
って、ＸａＯとｙａＯの両者を範囲に含む空間に到達し
、最後にそこからＸ　ａ　Ｏ＋　　Ｖ　ａ　ｏ両者を含
むＺ方向隣接空間を辿って行けば必ず点ａＯに到達する
（−゛次元の例。

第１４図（ｃ）、（ｄ）等参照）。

この方法によれば、検索ルートにループや振動はなく、
検索時間は、Ｓ　ＰＰＤと点ａＯの間の距離にほぼ比例
するから、全体頂点ｆｉＮに対し特殊ケースが無視でき
れば・［均ｏ　（Ｎ’）稈度の速度か得られる。　さら
に、高速化するには、第１６図（ｂ）に見るように、全
体をｍ個の区間に分割し、各区間に直接アクセスできる
道しるべ点ｇｉ　　（ｉ＝１．２．　　・・・、ｍ）を
あらかじめセットしておき、点ａＯの座標値が与えられ
たらまず最寄りの点ｇｉへ直接飛んで、そこから前記方
法で点ａＯへ接近する、一種のバケット・ソース方式を
採用すれば、特殊ケースを除いてｏ　（Ｎ）のオーダー
とすることができる。

次に、ワイヤーフレームのＳＰＦ展開について説明する
。

前述したように点ａＯを入力したので、次は、第１５図
（ｂ）に従って点ａＯから発する線分ａＯｔを人力図形
Ａの辺に沿って順に伸ばすことにより、図形Ａの辺より
なるワイヤーフレームをＳＰＦ上に展開する。ａＯｔが
伸びて、先端ｔが周囲空間に１−ド、左右とこかの壁を
突き抜けるとき、空間分割のトポロジーが突然変化し、
ＳＰＰの接続を変える必要が起こる。これをイベントＥ
ｊ　　（ｊ＝１゜２、・φ・）と呼ぶ。

ベンｒ毎にＳＰＰのメンテナンスを行い、図形ハの辺全
体をカバーすればワイヤ・フレーム人力は、完ｒする。

Ｅｊの種類は、二次元では、ａｉｔがＢｚ（図形面）を
貫通する場合（第１５図（Ｃ）参照）があるが他は、二
次元と同じになる。これは、第６図（ｄ）で空間分割を
Ｚ方向から見るとに次元と同様に見えることからも理解
できよう。

ワイヤ・フレーム人力により、図形式の周囲の空間は、
図形Ａの頂点を通りＸ軸に１Ｆ直な而Ｂｘと図形ふの辺
を含みＺ軸に・２行な而Ｂｙによって分割され、それぞ
れの空間にＳＰＰが設定される。

以−Ｌの処理は、人力図形の近傍空間のみでおこなわれ
るから、特殊ケースを除けばｏ（Ｎｏ）のオーダーにな
る。

次に、面の展開について説明する。

ワイヤ・フレーム入力が終わったので、次は、而を張る
。図形式の面の展開処理は、第１５図（ｄ）のごとく、
始点を図形Ａの面のＸ一端ａ１に囲空間のＳＰＰをメン
テナンスして行く処理である。

ＴがＸ＋＋Ｎａ動いて、既設図形によってできている空
間の外壁面ＢＹＩＢＺの折れ線を通過するとき、空間分
割のトポロジが急変する。これをイベントＥｊ　（ｊ：
１，２．・・・）という。

ＴｊとＢＹ＋Ｂｚとの交点ｔｊｋには頂点テーブル（特
徴点テーブル）か設置されて周囲空間のＳＰＰが接続し
ており、イベントＥｊ発生の都度メンテナンスする。

イベントＥｊにおける空間のトポロジーの変化は、イベ
ン１−Ｅｊを発生したｔｊｋのまわりだけであるから、
Ｔのメンテナンスは、第１５図（ｅ）のごとくＴにイベ
ントＥｊを通過する部分τｊを追加して、τｊ−１を削
除するプログラムを作ればよい。このとき同図＠、■部
は、イベント８５前後で同形であるからそのまま流用で
きる。

Ｔｊの追加は、同図に示すように、図形への而」二の線
分ｔｊ、ｏ（７をＴｊに沿って伸ばしながら既設空間境
界ｂ３．ｂ４．ｂｓ等との交点に頂点テーブルを設定し
て行き、続いてそのＸ−側に而を張る（図形へ面ｚ”、
ｚ−側番空間に別々のＳＰＰを設置することで表現）方
式により、各種形状のイベントＥｊに対処できる。

第１５図（ｆ）、（ｇ）は、イベントＥｊｉｉｉ後のＳ
ＰＰの接続状況の例である。

イベントＥｊ通過の次のＥ　Ｊ＋１を見付けるには、ｔ
ｊ、ｋを作っている辺又はｔｊ、ｋから発しているＳＰ
ＰのＸ＋＋Ｎａある頂点のうち、最もＬ＋１ｉ１（Ｘ座
標の小さい）ものをとればよい。Ｔを進めて行って、イ
ベン）Ｅｊ＋１が無くなれば展開は完ｒする。

以−にの面の展開は、特殊なケースを除けばすべて処理
が人力図形Ａの面の周囲近傍空間で閉じ、遠方の図形と
は１！；（関係なので、Ｏ（Ｎ’　）オーダーの処理で
ある。

以に、頂点人力、ワイヤ・フレーム、面の展開それぞれ
がｏ（Ｎ’）の処理なので、全体ＳＰＦの初期生成も、
特殊なケースが無視できれば、０（Ｎ）の高速性が期待
できる。

次に、特徴点の挿入、追加について説明する。

さて、重複処理２図形論理処理、衝突処理等において特
定の特徴点（又は頂点）をある部分空間に追加又は挿入
するためには、この部分空間を代表す　るようなスペー
スポインタペアを探してそれ又はそれに隣接する特徴点
と新しい結合関係を結ぶ必“皮がある。

これは、順次スペースポインタペアをサーチして行くこ
とも考えられるが、それでは時間がかかり過ぎるので次
のような方法により、最も関係するスペースポインタペ
アを探索し、その探索時間を短縮する。

それは、二次元の場合では、第１６図（ａ）に見るよう
に、図形が置かれる空間の座標をマｌ−ＩＪンクス状の
ブロックに区分した状態で管理するものであって、各ブ
ロックの中央に図形状の特徴点とは全く関係しない特徴
点（以下道しるべ特徴点）ｇｔ＋ｇ２．・・・、ｇｉ、
　　・・ｔｇｎ＋を採り、これらを縦方向に沿って一筆
δきの連続空間として、各特徴点ＳＺｔ、ｇ２．　　・
・・＋ｇｉ＋　　・番。

ｇｍについてそれぞれ特徴点テーブルを設け、こレラに
ついてスペースポインタペアを形成しておき、図形の各
特徴点は、これらともスペースポインタペアを形成する
ようにする。

そして、追加すべきある特徴点ａＯを含む部分空間を代
表するスペースポインタペアを探す場合に、まず、特徴
点ａＯの座標値かり、えられたときに、この座標値に基
づき道しるべ特徴点ｇｔ、ｇ２、・０・＋ｇｌ＋　　・
・＋ｇｍをテーブル探索して、その座標値を包含するブ
ロックとなる特徴点ｇ１を探して、この特徴点ｇｉにつ
ながる図形の特徴点例えば特徴点ｋｏの特徴点テーブル
を検索してそのスペースポインタペアを切断し、あらた
に特徴点ａＯについて前記特徴点ｋｏとのスペースポイ
ンタペア３　ＰＰａｏｋｏを生成し、同様に他の隣接特
徴点についても既存のスペースポインタペアを切断し、
特徴点ａＯについてのスペースポインタペアを生成する
ものである。

具体的には、ある特徴点ａＯの座標値（ＸＯ。

０）から道しるべ特徴点ｇ１のスペースポインタペアを
求めて、特徴点ａＯが挿入される空間を代表するスペー
スポインタペアを持つ現実の図形についての特徴点ｋＯ
について特徴点ｇｉの空間ブロックの範囲で検索して行
くものである。

この道しるべ特徴点は、空間検索処理に入る時に、最モ
関係の近いスペースポインタペア（特徴点テーブル）を
検索するためのキーとなる仮想的に設定されたスペース
ポインタペアであって、実際の図形の特徴点のスペース
ポインタペアとは別に設けられ、そのブロックの範囲内
において別途図形の各特徴点とスペースポインタペアが
形成されているものである。

一方、三次元の場合には、先に述べたように第１６図（
ｂ）に見るようなマトリックス配列、１−の１７、体に
おいて同様な処理を行うことになる。

ところで、スペースポインタペアを生成に関して特殊な
図形、線については、それぞれ特定の条件付けを行って
、スペースポインタペアを形成するものであって、空間
分割線に沿った直線、例えばＸ方向の分割の場合の鉛直
線に対するスペースポインタペアは、第１７図（ａ）に
見るように傾斜した線とみなしてスペースポインタペア
を形成するものとする。また、Ｘ座標値が等しい場合の
スペースポインタペアは、第１７図（ｂ）に見るように
、どちらか右（又は左）にある点とみなしてスペースポ
インタペアを形成する。さらに、２木の線が市なるよう
な線のときには、第１７図（Ｃ）に見るようにこれらが
微小に離れているものとしてスペースポインタペアを形
成するものである。

また、第１７図（ｄ）、（ｅ）、（ｆ）は、それぞれ辺
ポインタペアの特殊な状態の説明図であり、これらは、
自己自身を相ｆ方の辺ポインタとしてペアを形成したも
のである。さらに第１０図（ｆ）は、交叉点の場合のス
ペースポインタペア及び辺ポインタの例を示してしる。

また、第１７図（ｇ）は、図形の一部に曲線かある場合
のスペースポインタペアの形成についての説明図である
。

一方、三次元においても同様な状態が存在し、さらに、
コーナーｒＹ通点では、第１８図（ａ）に見るような特
徴点テーブルとなり、三面交叉では、第１８図（ｂ）に
見るような特徴点テーブルの形態を採り、三面交叉関係
では、第１８図（Ｃ）及び（ｄ）に見るようなものとな
る。

さて、図形の運動について二次元で還元した場合、第１
９図に見る運動図形Ｐを考えることができ、この図を見
ると空間関係が変化するのは、斜線で示す空間のみであ
ることが判る。そこで、以１−のようなスペースポイン
タペアにより空間を表現していれば、その処理は、隣接
空間の範囲で処理するようにすればよく、図中、斜線の
部分の空間に対応する特徴点テーブルのデータのみ注意
して処理しればよいことになる。

同様なことは、三次元にあっても言え、隣接＼γ体体間
間注、？ｒ、シて処理すればよいことになる。

したがって、図形の衝突検出とか、移動処理が非常に而
？ｊ１な処理となる。特に、三次元では、ロボットの移
動における衝突検出をあらかじめロボットの移動内容を
データインしておくことで処理が可能である。このよう
なことは二次元における迷路の処理のような場合にも適
用できることはもちろんである。

ところで、三次元において市グな処理の１つのして、隠
れ面消去がある。

第２０図は、隠れ面消去の説明図である。

三次元図形をマトリックス変換して、二次元図形の透視
図に変換し、後ろと前の図形の重なった部分の後ろの図
形部分を削除すると隠れ面消去が１’ｌＪ能となる。

第２０図に五次元図形表示の概念を示す。

隠れ面消去処理では、スクリーン面に投影された二次元
図形の重なりチェックと表示優先度判定を、二次元スク
リーンＳＰＦの１−で行うが、ＳＰＦでは処理が一図形
づつ行えるので、これを三次元ワールドＳＰＦと組み合
わせると以ドに述べるＩＭ視室空間追跡法よって処理速
度を画期的に七げることか可能になる。

第２１図にその原理を示す。最初に三次元ＳＰＦにおい
て視点を含む部分空間ΩＯからスタートし、視点から発
した視線が通過する（可視の）部分空間の壁面を順次透
視変換し、スクリーン５ＰＦｌ−で市なりチェ、りによ
り１ｊＪ視性を判定しながら、ＳＰＦ”の隣接空間検索
機能を使って表示すべき空間をＬ前の側から逐次的に探
索する方法をとる。

この場合、ＩＩＪ視空間は、必ず可視空間透明空間の向
こう側に隣接し、不透明又は不ｔｉ（視壁面の向こう側
の空間は不ｉ＋Ｊ視であるから、ｕＪ視全空間みを検索
し、不−１丁視空間は検索しないことで、従来のｆ法に
比べてオーダー違いの効率向りが可能になる。以ド木方
式の特徴を列挙する。

（１）三次元５ＰＦＩ−で一貫処理が可能。

（２）　ｕＪ視全空間みを処理するので高速。

第２０図の家を外側から見るとき、家の中の間取り、家
具等は検索しない。スクリーン外の不可視空間も調べな
いので、従来のクリッピングより効率が高い。処理時間
は特殊ケースを除きｏ（Ｎ’）、ｉ’Ｔ視空間数をｎと
すればれば、ｏ　（ｎ）となる。

（３）視点偏光が高速で自由。

従来の透視変換後にクリッピングを行う方式では、視ｌ
：“、（変型時には全体図形の＋１処理を冴したが木刀
式では探索したｒｊｌ視空間のみ処理すればよいので高
速。

（４）：、次元図形のビックマツプが高速容易。

スタイラス／ペン、マウス等により指示されたスクリー
ン図形は、−次元ＳＰＦで高速探索できる。：Ｅ、次元
ワールドＳＰＦの図形は、スクリーンＳＰＦの図形とポ
インタで接続しておけば、すぐに判明する。

（５）画面部分の修ｉＥができる。

スクリーンＳＰＦで変更部分のみの隠れ面処理ができる
。図形を一部削除したりしたらその後の部分たけについ
てｉｉＪ視空間追跡を行えばよい。

（６）表面画面のベクター／ラスタ変換が容易。

スクリーンＳＰＦにより、図形とラスタとのＡＮＤをと
ればよい。静電プロッタ等へ直接出力できる。

（７）Ｚ−バッファ等特殊ハード不要。オール・ソフト
、汎用性、移植性高（、低ンステム・コスト、ビクセル
による精度制限がなく、ズーミングでも画面が荒れない
。プロッタ等大画面でも隠れ面消去出力できる。

さて、第２２図は、二次元において、図形データか大規
模で主メモリの中に一度に入りυ）れない場合に全体を
複数の６ａ域に分割する場合のスペースポインタペアの
形成の仕方を説明するものであり、領域の境界部分にユ
ーザには見えない境界線をダミーとして挿入してスペー
スポインタペアをその領域の範囲に限定して処理するよ
うに構成する。これは、三次元においても同様な関係で
取り扱うことができる。

ところで、部分処理として有効な方法として図形認識を
挙げることができるが、例えば第２２図に見るような図
形から四角の中にＥ角形が内在される図形Ｒを探し出す
問題では、スペースポインタペアを順次サーチし、隣接
図形処理として内在された図形を判定することにより部
用に探し出すことがｉｉＴ能であり、この点も二次元図
形、三次元図形とも変わりがない。

さて、第２４図（ａ）は、二次元において、空間の分割
の仕方を図形の各「１点に採ることなく、特徴のある「
１点を選択して選択的に空間分割した場合であるが、−
一次元でも同様であり、第２５図（ａ）、（ｂ）がこれ
に対応する。

また、第２６図（ｂ）は、二次元で座標系を極座標に採
った例であるが、三次元にあっても同様な適用ができ、
座標系によるものではない。

さらに、第２７図（Ｃ）に見るようにタブレット、マウ
ス、プロッタ、プリンタ等を含めた処理システムで図形
処理をすることがｕＪ能である。

以１・１、説明してきたが、この発明における図形処理
は、ＬＳＩのレイアウト図形の処理とか、最適ルートの
探索、ロボットの移動空間の制御、衝突をはじめとして
各種の処理に利用できるものである。

ところで、図形のスペースポインタペアハ、ｒＪ’ｊ点
に限定されるものではなく、図形の特徴点であればよい
。また、実施例では、空間分割する境界而は・［ｉ、而
を採用しているが、これは斜面９曲面等であってもよ＜
１．また、その座標系は、自由に選択でき、三次元、Ｎ
次元のものであっても適用することができる。

実施例では、図形を中心として説明してきたが、いわゆ
る画像に特徴点を採って直接特徴点展開して１．−４’
ｊ図形に変換して同様な処理をしてもよく、画像処理に
対しても図形処理の形態で適用できることはもちろんで
ある。

さらに、実施例では特別に図形処理プログラム七スペー
スデータ処理とを分けているが、全てのデータをスペー
スデータの形式で作成して図形データすべてをこのスペ
ースデータから変換して得るようにしてもよい。

なお、実施例では、スペースデータ処理部を特別に設け
ているが、その処理は、演算処理装置の機能の１つとし
て実現できることはもちろんである。

［発明の効果コ 以上の説明から理解できるように、この発明にあっては
、少なくとも第１．第２．第３の変数により表現される
Ｘ７．空間間座標系に配置された図形についてのデータ
処理において、第１の変数に対応する軸に関し図形の特
徴点を通る平行な面で、〜１１体空空間標系を分割し、
・］４行な面により挟まれた空間の両側の特徴点に対応
してそれぞれ特徴点情報が生成される図形処理システム
であって、各特徴点情報と、隣接する他の１つ又は複数
の特徴点情報とを、相ｔｌＨに連結関係を持って生成し
、この連結関係により平行な面により挟持される空間を
定義するというものであるので、特徴点ペアにより部分
立体空間の検索が可能となり、部分に注１」シた図形処
理ができる。

その結果、隣接図形とか重なり＼γ体図形の検索、隠れ
面の処理等が効率的に処理でき、高速なニー次元図形処
理を実現できるものである。

４、図面のｆｆ１ｉ　’ｌｊ−な説明 第１図は、この発明の図形処理システムを適用した計算
機システムのブロック図であり、第２図（ａ）は、その
図形処理システムによる図形処理の機能構成図、第２図
（ｂ）は、そのスペースデータ処理部におけるインクプ
リタブログラムの処理の流れ図、第２図（Ｃ）は、その
演算処理装置におけるプログラム制御部の処理の流れ図
、第３図（ａ　）は、そのスペースデータの原理的な表
現の説明図、第３図（ｂ）は、その基本的な空間分割の
処理の仕方の説明図である。また、第４図（ａ）は、二
次元における特徴点テーブルのＸ方向端点についての具
体例の説明図、第４図（ｂ）は、その特徴点テーブルの
Ｘ方向でない端点の具体例の説明図、第４図（Ｃ）は、
第４図（ａ）の二次元テーブルに対応する図形の説明図
、第４図（ｄ）は、第４図（ｂ）のテーブルに対応する
図形の説明図、第４図（ｅ）は、テーブルにおける符号
の説明図、第４図（ｆ）は、テーブルにおける各データ
の具体的構成を示す一例の説明図、第４図（ｇ）は、空
間属性が設置できない場合の説明図、第５図（ａ）は、
二次元での処理されるべき図形の一例を示す図、第５図
（ｂ）は、その図形において発生するスペースポインタ
ペアの説明図、第６図（ａ）、ら次元における空間分割
の体力の説明図、第６図（ｂ）は、＼ｙ体同図形相ｌｌ
：おけるスペースポインタペアの関係を示す説明図、第
６図（Ｃ）は、巳次元における蔭の交叉についての説明
図、第６図（ｄ）は、そのＺ方向の投影図、第７図は、
図柄と面ポインタペアとの関係の説明図である。　そし
て、第８図（ａ）は、１γ体図形の空間分割とスペース
ポインタペアとの関係の説明図、第８図（１））は、そ
の１つの珀点から出るスペースデータの説明図、第９図
（ａ）は、スペースデータと左右の連結情報との関係の
説明図、第９図（ｂ）は、三次元における特徴点テーブ
ルの具体例の説明図、第９図（Ｃ）は、多面体の凸り′
１点Ｖのまわりのスペースデータの説明図、第９図（ｄ
）は、凸頂点Ｖのまわりの特徴点テーブルの説明図、第
第１０図（ａ）は、凹なる立体空間を持つ１つの珀点か
ら出るスペースデータの説明図、第１０図（ｂ）は、凹
なる立体空間が存在する場合の特徴点テーブルの説明図
、そして第１１図（ａ）は、屯なりを判定する場合の重
なり図形の−例を示す説明図、第１１図（ｂ）は、その
場合の属性の説明図、第１２図（ａ）は、二次元での多
色図形の各ポインタの表現例の説明図、第１２図（ｂ）
は、その場合の特徴点テーブルの関係を示す＋ｌ！ｌｉ
四図、第１３図は、）′１．体図形の重複状態の説明図
である。また、第１４図（ａ）、第１４図（ｂ）、第１
４図（ｃ）及び第１４図（ｄ）は、それぞれスペースポ
インタペアの生成の仕方についての説明図、第１５図（
ａ）、第１５図（ｂ）。

第１５図（Ｃ）、第１５図（ｄ）、第１５図（ｅ）、第
１５図（ｆ）及び第１５図（ｇ）は、それぞれ三次元デ
ータベースへの入力方法を説明する図、第１６図（ａ）
は、二次元において特徴点を高速に検索するための道し
るべ処理の説明図、第１６図（ｂ）は、三次元の道しる
べ処理の説明図、第１７図（ａ）、第１７図（ｂ）及び
第１７図（ｃ）は、それぞれ特殊な状態におけるスペー
スポインタペアの形成の仕方の説明図、第１７図（ｄ）
、・第１７図（ｅ）は、それぞれ特殊な状態における辺
ポインタペアの形成の仕方の説明図、第１７図（ｆ）は
、交叉点の場合のポインタペアの説明図、第１７図（ｇ
）は、図形の−・ｊ■に曲線がある場合のスペースポイ
ンタペアの形成についての説明図、第１８図（ａ）及び
（ｂ）は、それぞれ−二次元におけるコーナ１１通点と
その特徴点テーブルの説明図、第１８図（Ｃ）及び（ｄ
）は、それぞれ−自交叉点とその特徴点テーブルの説明
図、第１９図は、運動図形についての空間関係を示す説
明図、第２０図は、隠れ面消去の説明図、第２１図は、
−４視空間追跡法を用いる場合の説明図、第２２図は、
図形データが複数の領域に分割されているような場合の
スペースポインタペアの形成の仕方の説明図、第２３図
は、特定の図形についてサーチする場合の説明図、第２
４図は、二次元において回転サーチ処理を高速化するた
めスペースポインタペアに対する頂点を増設する例の説
明図、第２５図（ａ）及び（ｂ）は、それぞれ三次元に
おいて同様に増設辺を設定した場合のスペースポインタ
ペアとの関係の説明図、第２６図は、空間の分割を極座
標とした場合の説明図、第２７図は、他の実施例におけ
る図形処理ンステムのブロック図である。

１・・・演算処理装置、２・・・メモリ、３・・・スペ
ースデータ処理部、 ２ａ・・・スペースデータインタプリタプログラム記憶
部、２ｂ・・・スペースデータ発生プログラム記憶部、
２ｃ・・・Ｉ１０制御プログラム記憶部、２ｄ・・・ス
ペースデータ記憶部、 ２ｅ・・・図形処理プログラム記憶Ｍく、２ｆ・・・そ
の他データ記憶部、 ３・・・スペースデータ処理部、 ４・・・Ｉ１０制御部、５・・・インタフェース、６・
・・７ステムバス、７・・・ディスプレイ、８・・・キ
ーボード、９・・・磁気ディスク記憶装置、１０・・・
図形データ変換処理部、 １１・・・制御対象プログラム、 １２・・・図形データ変換処理部、１３・・・スペース
データ生成プログラム部、１４・・・スペースデータ図
形処理プログラム部、 ２０．２１．２２・・・特徴点テーブル、ＳＰ・・・ス
ペースポインタ、ＥＰ・・・辺ポインタ、ＦＰ・・・面
ポインタ、 ５ＰＰＩ・・・スペースポインタペア、ＥＰＰＩ・・・
辺ポインタペア、 Ｆｐｐ！・・・面ポインタペア、

Claims (14)

【特許請求の範囲】
1. （１）少なくとも第１、第２、第３の変数により表現さ
   れる立体空間座標系に配置された図形についてのデータ
   処理において、第１の変数に対応する軸に関し図形の特
   徴点を通る平行な面で、前記立体空間座標を分割し、前
   記平行な面により挟まれた空間の両側の特徴点に対応し
   てそれぞれ特徴点情報が生成される図形処理システムで
   あって、前記各特徴点情報と、隣接する他の１つ又は複
   数の特徴点情報とが、相互に連結関係を持って生成され
   、この連結関係により前記平行な面により挟持される空
   間が定義されることを特徴とする図形処理システム。
2. （２）各特徴点情報は、ポインタを含み、連結関係は、
   隣接する他の１つ又は複数の特徴点情報において相互に
   他のポインタの存在する位置をそのポインタにより相互
   に指定することによりなされることを特徴とする特許請
   求の範囲第１記載の図形処理システム。
3. （３）ポインタにより相互に指定する関係にあるポイン
   タは、ポインタのペアとして取り扱われるものであって
   、このポインタのペアは、分割された部分空間に１対１
   で対応することを特徴とする特許請求の範囲第２記載の
   図形処理システム。
4. （４）特徴点は、図形の頂点であることを特徴とする特
   許請求の範囲第１項ないしは第３項のうちのいずれいか
   １項記載の図形処理システム。
5. （５）図形の置かれた空間は、三次元の座標系であって
   、図形の頂点を通る面は、平面であって、その座標軸の
   １つに垂直な面の方向にあることを特徴とする特許請求
   の範囲第４項記載の図形処理システム。
6. （６）三次元の座標系は、Ｘ−Ｙ−Ｚ座標系であること
   を特徴とする特許請求の範囲第１項ないし第５項のうち
   のいずれいか１項記載の図形処理システム。
7. （７）頂点には識別符号が割り当てられ、頂点の情報は
   、空間に対応するポインタと、面に対応するポインタと
   、図形の辺に対応するポインタと頂点の座標情報とを備
   えることを特徴とする特許請求の範囲第６記載の図形処
   理システム。
8. （８）頂点には識別符号が割り当てられ、頂点の情報は
   、空間に対応するポインタと、面に対応するポインタと
   、図形の辺に対応するポインタと、頂点の座標情報と分
   割された空間の属性又は面についての属性を示す属性情
   報とを備えることを特徴とする特許請求の範囲第７記載
   の図形処理システム。
9. （９）頂点の情報はテーブルとして設けられ、テーブル
   は、辺ごとにブロックとして分割されていて、各ブロッ
   クにおけるテーブルの情報は、前記辺を含む面の両側の
   空間を関係つけるものとして他のブロックのある情報と
   相互に連結関係にあることを特徴とする特許請求の範囲
   第６項又は第８項記載の図形処理システム。
10. （１０）少なくとも第１、第２、第３の変数により表現
    される立体空間座標系に配置された図形についてのデー
    タ処理において、第１の変数に対応する軸に関し図形の
    特徴点を通り、第２、第３の変数に対応する座標面に平
    行な面と、第２の変数に対応する図面の特徴線を含む第
    ３の変数に対応する軸に平行な面と、図形面自体により
    、前記立体空間座標を分割し、前記各面により挟まれた
    空間の両側の特徴点に対応してそれぞれ特徴点情報が生
    成される図形処理システムであって、前記各特徴点情報
    と、隣接する他の１つ又は複数の特徴点情報とが、相互
    に連結関係を持って生成され、この連結関係により前記
    各面により挟持される空間が定義されることを特徴とす
    る図形処理システム。
11. （１１）各特徴点情報は、ポインタを含み、連結関係は
    、隣接する他の１つ又は複数の特徴点情報において相互
    に他のポインタの存在する位置をそのポインタにより相
    互に指定することによりなされることを特徴とする特許
    請求の範囲第１０記載の図形処理システム。
12. （１２）ポインタにより相互に指定する関係にあるポイ
    ンタは、ポインタのペアとして取り扱われるものであっ
    て、このポインタのペアは、分割された部分空間に１対
    １で対応することを特徴とする特許請求の範囲第１１記
    載の図形処理システム。
13. （１３）ポインタにより相互に指定する関係にあるポイ
    ンタは、ポインタのペアとして取り扱われるものであっ
    て、このポインタのペアは、分割された部分空間に１対
    １で対応することを特徴とする特許請求の範囲第１２記
    載の図形処理システム。
14. （１４）特徴線は、図形の線であることを特徴とする特
    許請求の範囲第１０項ないし第１３項のうちのいずれい
    か１項記載の図形処理システム。