JPH0724073B2 - 図形処理装置 - Google Patents

Description

【発明の詳細な説明】 A.産業上の利用分野 本発明は、三次元立体を１つの視点から１つの観察方向
に沿つて見たときに眼に映る二次元像を発生する図形処
理装置に関する。

B.従来技術 種々の技術を使用することにより図形処理装置中で種々
の物体（object）を表現することができる。立体を表現
するのに特に適当な技術としては、“組立て立体幾何
（CSG）”があげられる。この技術によると、三次元
（３−Ｄ）立体は、その物体内に位置する点の組を特定
する関数定義によつて表現する。典型例においては、物
体は、当該物体内の点をアクセスしたときには“真”
を、そうでないときには“偽”を生じさせるブール関数
によつて特定する。この技術は、物体の体積ではなく物
体の稜線及び面を特定する線描画技術と好対照をなす。

物体の関数定義すなわち表現は、物体を作り出す点の組
を有効に特定する。例えば、球の関数定義は、中心から
ある値の半径内に入る点の組を特定する。複合物体は、
構造上基本的な物体すなわち“原始物体（Primitiv
e）”例えば球、無限面、無限円筒の関数定義を組合せ
ることにより特定する。例えば、ダンベルの関数定義
は、異なる位置の２つの球のそれぞれの関数定義と、球
の中心を通る軸を有する無限円筒の関数定義と、球の位
置で円筒の頭部を切り捨てる２つの平らな半空間の関数
定義とを含む。球、円筒および半空間の関数定義は、和
集合（set union）演算子および積集合（intersectio
n）演算子のような組合せ演算子を使用して（すなわち
集合論を使用して）組合せる。また、例えば、切抜きす
なわち穴を有する複合物体を定義するために、減算演算
子を使用して“原始物体”を組合せることができる。こ
のように、大きな物体から小さな物体を減じることによ
つて中空複合物体を定義することができる。このような
複合体は、この明細書中で用いる言葉の定義からすれば
依然として“立体”である。何故なら、複合物体を作り
出す個々の物体の定義が立体だからである。

原始物体から形成される複合物体は、多くの方法で組み
立てることができる。しかし、木構造を使用し、複合物
体を木の根において定義し、原始物体を葉において定義
し、副物体および／または原始物体から物体を構成する
のに実行すべき組合せ動作を特定する演算子を節におい
て定義し、副物体または原始物体をより下位の節におい
て定義するのが一般的である。

このようにして定めることのできる形の範囲は、実際に
は、選択された原始物体の組に依存する。多くの従来装
置においては、物体は平らな半空間からのみ構成され
る。平らな半空間は、平面の一方の側に存在する無限物
体の関数定義である。立方体の関数定義は、例えば、積
集合（set intersection）演算子を使用して６個の半空
間の関数定義を組合わせることによつて定める。他の装
置は、円筒、球、円環面体、楕円面および一様な螺旋
（even helices）を使用する。

三次元（３−Ｄ）立体を変換して二次元（２−Ｄ）像
（すなわち物体の２−Ｄ透視像）を発生する標準的技術
は、物体を透視図に符号するように変換するものであ
る。換言すれば、透視変換アルゴリズムを適用すること
により物体が存在する空間（ワールド空間）から透視空
間（観察空間）へ物体を変換する。そして、透視空間中
において、どの面が物体の前面にあるかということ並び
にどの面が２−Ｄ透視像上に現れるかということについ
てテストを行う。通常、空間再分割（spatialsub-divis
ion）という技術を使う。

この方法は、1982年３月に発行された“電子計算機設計
（Computer Design）"Vol14、No.2に掲載されたウツド
ワーク（Woodwark）およびクインラン（Quinlan）の
“立体モデル評価における複雑性の低減（Reducing the
effect of complexity on volume model evaluatio
n）”という題名の論文に取り入れられている。

空間再分割を使用して３−Ｄ立体の２−Ｄ透視図を作り
出すこれらの方法は、次のように要約できる。

問題にしている物体を透視空間に変換する。物体のこの
透視表現を、三次元矩形ボツクスで囲む。そして、ボツ
クスがこの物体と交差するかテストを行う。交差するな
ら、ボツクスを８個の同一の副ボツクスに再分割し、各
正方形面を４個の小さな矩形に分割する。そして、これ
らの小さな矩形ボツクスをテストし、空のボツクスを捨
てる。物体の一部を含む副ボツクスを保持し、再び再分
割する。この処理は、矩形ボツクスが１つのスクリーン
画素に一致するほど十分に小さくなるまで続ける。そし
て、これらの画素はスクリーン上で適当に着色する。

C.発明が解決しようとする問題点 物体を透視空間に容易に変換できる限り（例えば、物体
が平らな平面を有していれば）、上記従来方法は原理的
にはうまくいく。しかし、円錐面、球面または円筒面の
ような物体の場合には、透視空間における物体の関数定
義は、従来方法を使用して処理するのが実用的ではなく
なつてしまうほど複雑なものになつてしまう。特に、多
くの円錐面等から成る複合物体（例えば複雑な分子）の
場合には顕著である。

本発明は、三次元立体（物体）それ自身を変換する必要
なく、三次元立体を１つの視点から１つの観察方向に沿
つて見たときに眼に映る二次元像を発生する図形処理装
置を提供することを目的とする。

D.問題点を解決するための手段 本発明による図形処理装置は、 ワールド空間に対して定義された前記三次元立体の関数
表現を記憶する物体定義記憶手段と、 観察空間（例えば透視空間）を定める三次元ボツクスの
関数表現を記憶する観察空間記憶手段と、 上記二次元像を上記三次元ボツクス内に作り出すために
上記ワールド空間中の三次元立体に対して行う変換動作
の逆の動作を行うのに必要な逆変換演算子を記憶する逆
変換演算子記憶手段と、 上記三次元ボツクスをこれより小さい副ボツクスに分割
する処理を、所定の解像度に符号した前面領域を有する
副ボツクスを作り出せるまで漸進的に行うボックス分割
手段と、 上記逆変換演算子記憶手段の出力信号および上記ボツク
ス分割手段の出力信号に応じて、上記所要の解像度に符
号する前面領域を有する副ボツクスに対して上記逆変換
演算子を使用して逆変換動作を行うことにより上記ワー
ルド空間中にテスト・セルを発生するテスト・セル発生
手段と、 上記物体定義記憶手段の出力信号および上記テスト・セ
ル発生手段の出力信号に応じて、上記ワールド空間中に
おいて上記三次元立体と交差するテスト・セルに対応す
る副ボツクスを検出する副ボツクス検出手段と、 上記検出された副ボツクスを示す情報を記憶する手段
と、 を具備する。

E.作用 本発明による図形処理装置は、まず初期ステツプとし
て、 （ｉ） ワールド空間に対して定義された三次元立体の
関数表現を物体定義記憶手段に記憶させ、 （ii） 観察空間を定める三次元ボツクスの関数表を観
察空間記憶手段に記憶させ、 （iii） 上記二次元像を三次元ボツクス内に作り出す
ためにワールド空間中の三次元立体に対して行う変換動
作の逆の動作を行うのに必要な逆変換演算子（変換演算
子の逆数（inverse））を逆変換演算子記憶手段に記憶
させる。

次に、 （iv） 観察空間中の三次元ボツクスをこれより小さな
副ボツクスに再分割する処理を、所要の解像度に符号し
た副ボツクスを作り出せるまで漸進的に行い、所要の解
像度に符号した副ボツクスに対して逆変換を行うことに
より、ワールド空間にテスト・セルを発生させ、 （ｖ） テスト・セルが三次元立体と交差するか検査
し、交差する場合には当該テスト・セルに対応する副ボ
ツクスを特定し（実施例では、観察方向に平行に並んだ
副ボツクス列に対応するテスト・セル列に含まれるテス
ト・セルのうち複数個が三次元立体と交差するときに
は、対応テスト・セルが三次元立体と交差し且つ視点に
最も近い副ボツクスを決定する）、 （vi） ステツプ（ｖ）で特定された副ボツクスを示す
情報を記憶する。

F.実施例 本発明の実施例を詳細に説明する前に、CSGを使用する
ことにより物体の関数定義を評価する原理について説明
する。

一般に、立体モデルの評価は、立体の内側および外側し
たがつて立体の境界を決定する処理ということができ
る。評価処理が最も一般的に使用されるのは、物体の２
−Ｄ画像を描くときである。一般に、物体の表面領域を
決定するために体積や重心のような質量特性を計算する
のも可能であるが、本発明では、このような他の方法は
とらない。

習慣的に、物体は、第2B図に示されたような木構造によ
つて組立て立体幾何（constructivesolid geometry）の
原理に従つて定義される。

第2A図は、前述のダンベル10を例示したものである。第
2B図は、ダンベル10を特定する木構造20を示す。これ
は、連結リスト記憶構造（linked-list storage struct
ure）によつて実現できる。演算子、関数定義等の組合
せを特定するために異なる要素種類を連結リストに含ま
せることができる。数学的には、ダンベルの定義は次の
ように表現することができる。

ダンベル＝Ａ＋Ｂ＋Ｃ＊Ｄ＊Ｅ ここで、“＊”は、第2B図において“AND"として示され
た数学的積集合演算子（intersectionoperator）であ
り、“＋”は、第2B図において“OR"として示された数
学的和演算子（unionoperator）である。Ａ、Ｂ、Ｃ、
ＤおよびＥは、球Ａ、球Ｂ、無限円筒Ｃ、線12の右側の
半空間Ｄおよび線14の左側の半空間Ｅに対する数学的表
現である。原始物体Ａ、Ｂ、Ｃ、ＤおよびＥに対応する
関数定義は、木構造20中の葉22a、22b、22c、22dおよび
22eに配置される。

このような定義に基いて計算を行うには、後に第2C図を
参照して説明するように、空間再分割技術を使用するの
が一般的である。

空間再分割方法は、基本的に次のようなものである。

空間領域30は、評価すべき物体を含むものとする。物質
を定義する組立て立体幾何表現20すなわち関数定義は、
この空間領域30内で詳しく調べ単純化する。単純化した
ものは、考慮中の領域内のオリジナル物体と等価であ
る。単純化の手順は次の通りである。

1.原始物体に対し、該物体が立方体空間の完全に外側に
あるか判断する。完全に外側にあるならば、該物体を、
空物体すなわち内側の無い物体に置換える。また、該物
体が空間領域を完全に包囲するか判断する。完全に包囲
するならば、該物体を、充満物体すなわち外側の無い物
体に置換える。

2.集合演算子を適用することによつて作られる複合物体
に対しては、単純化したオペランドに対して（基本的に
３値の）ブール論理を帰納的に適用する。例えば、 空 和集合表現２→表現２ 表現１ 和集合空 →表現１ 充満 和集合表現２→充満 表現１ 和集合充満 →充満 および、 空 積集合表現２→空 表現１ 積集合空 →空 充満 積集合表現２→表現２ 表現１ 積集合充満 →表現１ この単純化の結果が空ならば、考慮中の空間領域内にお
いて物体の内側は無い。画像を描いている最中ならば、
この領域はスクリーン画像に何も寄与しない。（ただ
し、質量特性を計算中のときには、空間は体積またはモ
ーメントに何も寄与しない。） 単純化の結果が“充満”ならば、空間領域は物体によつ
て完全に占有される。１つの視野から画像を構成する場
合、この空間領域は観察者に対向する面を含まないので
二次元像に何も寄与せず、物体の内側はその対向面に隠
れる。（ただし、質量特性については、領域全体が計算
中の体積またはモーメントに寄与する。） 通常、表現は少くとも１つの限界点（線、面）を含む。
ある環境においては、表現は直接取扱えるほど単純であ
る。例えば表現は単一の平らな半平面である。物体全体
の画像または質量特性への貢献度は直接計算できる。他
の場合には、空間領域はこれより小さな領域に分割す
る。最も単純なのは、最も長い寸法の次元に垂直に半分
に分割する。しかし、第2C図においては、空間領域30
は、８個の小さな領域31、32、33、34、35、36、37およ
び38に分割する。そして、これらの新たな領域に対し、
“充満”および“空”のような表現または他の単純化表
現が得られるまで単純化処理を繰返し行う。

しかし、小さい方の領域寸法限界に到達しているのにあ
る領域では非単純表現を依然として含んでいるというこ
とが起りうる。画像を描く場合、都合のいい停止点は、
領域が単一画素より小さくなるときである。この段階で
は、単一物体を含む領域は、物体の画素寸法面を含む。
２個の物体を含む領域は、２つの面が交差する稜線を含
み、３つの物体を含む領域は、通常、頂点を含む。

画像を描くときには、面または稜線を描く。面を描く場
合、空間領域の中心における面の垂線を計算し、これ
を、その位置から観察者へ向けて反射する光量を計算す
るために光源の予め知られた位置とともに使用する。よ
り複雑な稜線または頂点領域を描くには、このように取
扱うべく１つの可視面を分離するために光線追跡法を使
用する。（ただし、質量特性を計算するには、セルは単
に“半充満”であると仮定する。） 立体の２−Ｄ画像を発生する際、物体のある変換に基く
像を発生することが必要となることがある。一般に、真
の透視図中に物体の像を発生するのが好ましい。この場
合、関係する変換は透視変換である。

次に行う本発明の説明は、２−Ｄ透視画像の発生に関す
るものである。しかし、本発明は、例えば、物体の歪曲
をシミュレートするといつた他の変換に基く画像の発生
にも同様に適用できる。

第３図は、従来技術による透視像の作り方を示す。

第３図（ａ）のワールド空間中には、頭部が切断された
角錐（ピラミツド）の形をした空間領域44内の円筒46が
示されている。空間領域44は、頭部が切断された角錐の
前面と同一面にあるウインドー40を通して見る観察者に
よつて観察される空間の広がりを示す。一般に、２−Ｄ
透視像を発生するために、頭部が切断された角錐の形を
した空間領域44が第３図（ｂ）に示された矩形ボツクス
（三次元ボツクス）48内に収納されるように物体（円筒
46）が透視（変換）空間（観察空間）の二次元像50に変
換される。そして、前述の空間再分割方法を適用するこ
とにより、歪曲した二次元像（物体）50を評価する。な
お、第３図において、VPは視点を、VDは観察方向をそれ
ぞれ示す。

このような従来方法は、理論的にはうまく行くが、物体
の組および／または変換の数が多くなつた場合には実用
的ではない。何故なら、変換された関数定義が複雑にな
るからである。本発明は、空間を変換することにより物
体それ自身の変換を不要にし、より広い範囲の物体およ
び変換の評価を可能にするものである。

説明を簡単にするために、１つの円筒体の２−Ｄ透視像
の発生についてのみ説明するが、通常、物体は、より複
雑であり、第2A図に示されたダンベルよりも複雑なこと
もある。

実際には、物体のある特定のまたは各原始構成要素をそ
れ自身の座標系に保持し、その座標系中の空間領域に対
してテストする。関数定義ボツクス48すなわち透視空間
を定義する矩形ボツクスを設定する。ボツクス48は、物
体がその中に変換されるボツクスである。ただし、従来
のように物体を変換するのではなく、通常行われる変換
の逆を行うことにより、透視空間（第４図（ｂ））の矩
形ボツクス48が、頭部の切断された角錐44に変換され
る。透視空間（第４図（ｂ））の矩形ボツクス48に上述
の再分割アルゴリズムを適用し、副ボツクスを逆変換し
たもの（テスト・ボツクス）が物体を構成する原始物体
と交差するかテストすることにより、物体それ自身を変
換する必要が無くなる。

考慮中の空間領域がそれが占めるべき大きさよりも多少
大きくても、再分割アルゴリズムは悪影響を受けない。
単純化したものから得られる表現が、厳密にいえば除去
されるべき限界点（線、面）を含むことがあるだけであ
る。考慮中の領域が小さくなるにつれてエラーが減少す
るものとすると、これら余分な限界点（線、面）は後の
評価において除去される。効率が低下しより小さな最小
領域寸法まで評価を続ける必要はあるが、再分割アルゴ
リズムは正しく動作し続ける。

次に、第１図および第４図を参照して、本発明による円
筒の二次元透視像を発生につれて説明する。

第１図は、本発明による図形処理装置の実施例を示す。
この実施例に示された構成要素は、プログラム可能図形
処理装置をプログラムすることにより実現できる。そう
でなければ、これらの構成要素は、図形処理装置中に別
個に設けられたハードワイヤード回路（論理回路）によ
つて実現できる。一般に、図形処理装置は、記憶装置、
処理手段、データ入力手段（例えば、キーボード）、お
よびデータ出力手段（例えば、陰極線管表示装置）を具
備する。

最初に、変換すべき物体の関数定義、この例では円筒4
6、を物体定義記憶手段72に記憶させる。複合物体の場
合には、第2B図を参照して説明したタイプの木構造を物
体定義記憶手段72に記憶する。

ボツクス48の関数定義は、観察空間（変換空間−透視空
間−）定義記憶手段54に記憶する。この例では、ボツク
スは矩形である。ただし、他の形態、例えば円筒とする
ことができる。関数定義は、種々の形態をとることがで
きる。例えば、連結されたリストの形をとる木構造とす
ることができる。この場合、矩形ボツクスの定義は、６
個の平らな半空間の交差の形をとる。立方体の定義は、
例えば、中心の特定と、この中心から立方体の頂点まで
のベクトルの特定とによつて行う。ボツクス48は、視点
および観察方向を考慮して透視変換空間中で定義する。
一般に、ボツクス48の前面が観察方向に垂直となるよう
にボツクス48の軸を観察方向に垂直にできる。

逆変換演算子は、逆変換演算子記憶手段56に記憶する。
この例では、演算子は、逆透視変換演算子、すなわち、
物体の目的とする関数表現を作り出すように定義記憶手
段72に記憶された物体を透視観察空間中の矩形ボツクス
48内に変換するのに必要な透視変換演算子の逆関数（in
verse）である。

制御手段58は、ビツクス／副ボツクス再分割手段60に物
体との比較のための矩形ボツクスを選択させる。逆変換
処理手段62は、逆変換演算子を使用して矩形ボツクス48
に対して逆変換動作を行う。この結果得られる頭部の切
断された角錐44（第３図に示された変換の逆動作によつ
て得られる）は、後述のように、テスト・セル発生手段
66を通過して比較手段66に直接供給される。単純化され
たテスト・セルは、テスト・セル発生手段64によつて矩
形ボツクス（または副ボツクス）の逆変換から作り出さ
れ、比較手段66に供給される。

物体およびテスト・セル関数定義は、比較手段66中で行
われる比較によつて交差するかテストし、前述のよう
に、“充満”、“空”または“部分充満”の３値ブール
比較出力を発生する。比較手段66の出力は制御手段58お
よび物体単純化手段68に供給される。

制御手段58は、比較結果に応じて次のように動作する。

（ｉ） 交差が検出されるとともに、考慮中のボツクス
または副ボツクスの前面が所要の解像度よりも大きけれ
ば、制御手段58は、次の段階で順当に評価できるよう
に、再分割手段60に考慮中のボツクスまたは副ボツクス
を複数の（例えば８個）の小さな副ボツクスに再分割さ
せる。

（ii） 交差が検出されるとともに、考慮中のボツクス
または副ボツクスの前面領域が所要の解像度に一致して
いれば、この事実を結果記憶手段70に記憶させる。

（iii） 交差が検出されなければ、考慮中のボツクス
または副ボツクスの検査は終了し、この事実を記録させ
る。

このようにして、画像の画素アツプを制御手段58によつ
て結果記憶手段70中に作り上げることができる。一般
に、矩形ボツクスは、その軸の１つが観察方向に平行に
なるように視点に対して配列し、再分割処理は、画像を
作り上げる際に副ボツクスの列が観察方向に平行か検査
するように調整する。画像の各画素は、観察方向に平行
で画素の寸法に一致した前面領域を有する副ボツクスの
列に対応するように配列できる。しかし、この配列は必
須ではなく、他の形状および向きのボツクスを使用でき
る。特に、物体の一般的でない図（例えば、歪曲図、立
体図等）を作り上げる必要がある場合には特にそうであ
る。制御手段58は、物体の前面を決定するために、企画
した像中に示されているように、物体の前面により近い
副ボツクスがより遠い副ボツクスより前に処理されるよ
うに構成する。１つの列中の画素寸法副ボツクス（すな
わち前面領域が画素寸法にほぼ等しい副ボツクス）が検
出され且つ当該ボツクスに対応するテスト・セルが物体
と交差すると、物体の前面からさらに遠い当該行中の副
ボツクスを考慮する必要はない。制御手段58は、再分割
処理の記録を維持する。この記録は、木構造レコード、
ビツト・マツプ、または他の適当な形をとる。

物体の前面を検出すると、例えば光追跡技術を使用して
関連画素の所要の色および／または輝度を決定すること
ができる。テスト・セル中の物体の面に対する垂線を示
すベクトルは、物体の関数表現から計算できる。光源を
示す１つ又はそれ以上のベクトルと変換ベクトルとを比
較することにより、テスト・セルに対応した色および／
または輝度を決定できる。

物体単純化手段68は、変換されるべき物体が複数の原始
物体から形成される場合に単純化関数定義を発生するの
に使用される。矩形ボツクスの１回以上の再分割の後、
比較手段66の出力は、テスト・セルが物体中の１つ以上
の原始物体と交差しないことを示すことがある。この場
合、矩形ボツクスのその領域をさらに再分割したとき、
これら原始物体の関数定義は当該分割領域のテスト・セ
ルに対して比較する必要はない。物体単純化手段68は、
前の比較動作の結果に応じていずれかの段階において関
連する物体全体の関数定義の当該部分を選択する。これ
は、物体定義記憶装置72に記憶された構造を走査するこ
とにより行われる。

テスト・セルは、副ボツクスの逆変換の関数定義によつ
て形成される。ただし、これに限定されるわけではな
い。このようにする代りに、副ボツクスの逆変換を、当
該逆変換と中心が一致し且つ当該逆変換に外接する単純
３−Ｄ体積で置換できる。（“単純３−Ｄ体積”とは、
例えば球、矩形ボツクスまたは楕円体のような体積をい
う。）これは、副ボツクスの逆変換と交差する物体のあ
らゆる部分は、当該変換と中心が一致し当該変換に外接
する体積とも交差するからである。単純化されたテスト
・セルを使用する場合、これは、ボツクスまたは副ボツ
クスの変換の中心を決定し且つ該変換に外接する単純な
３−Ｄ体積を特定することによつてテスト・セル発生論
理手段64から発生する。ただし、このようにすると、テ
スト・セルを逆変化によつて形成するのと同じ解像度を
得るために、再分割をさらにもう１回必要とする。

副ボツクスの変換とテスト・セルとの間の不一致の程度
を最小にするために、テスト・セルが副ボツクスの変換
の形状および寸法とほぼ一致するように観察方法に沿う
副ボツクスの長さおよび使用するテスト・セルを選択す
る必要がある。（“一致の程度”とは、変換およびテス
ト・セルが同空間にある程度をいう。）これは、このよ
うな副ボツクスの変換の深さを、その深さおよび高さに
ほぼ一致するように選択することにより行う。従つて、
ある特定の行中の副ボツクスのすべての変換は、それら
の寸法が変化しても同じ形状である。

上記実施例は、単純な物体および変換に関するものであ
るが、本発明はこれに限定されず、より複雑な物体およ
び変換にも適用できるのはもちろんである。

G.発明の効果 本発明は、三次元立体を１つの視点から１つの観察方向
に沿つて見たときに眼に映る二次元像を発生するのに、
三次元立体自身をワールド空間から観察空間へ変換する
のではなく、観察空間をワールド空間に逆変換するもの
であるから、簡単に上記二次元像を発生できる。

【図面の簡単な説明】

第１図は、本発明による図形処理装置の一実施例を示す
ブロツク図、 第2A図は、ダンベルを示す説明図、 第2B図は、ダンベルを特定する木構造を示すブロツク
図、 第2C図は、物体を評価するための空間再分割方法を示す
説明図、 第３図は、従来技術に従つて三次元立体から二次元像を
作り出す方法を示す説明図、 第４図は、本発明に従つて三次元立体から二次元像を作
り出す方法を示す説明図である。 54……観察空間定義記憶手段、56……逆変換演算子記憶
手段、62……逆変換演算子記憶手段、64……テスト・セ
ル発生手段、66……比較手段、70……結果記憶手段。

Claims (1)

【特許請求の範囲】
1. 【請求項１】三次元立体を１つの視点から１つの観察方
   向に沿って見たときに眼に映る二次元像を発生する図形
   処理装置において、 ワールド空間に対して定義された前記三次元立体の関数
   表現を記憶する手段と、 前記三次元立体を含む前記ワールド空間中の空間領域に
   対して、前記二次元像を得るための変換を施して得られ
   る空間領域である三次元ボックスの関数表現を記憶する
   手段と、 前記三次元立体を前記三次元ボックス内に変換する動作
   の逆変換を行うのに必要な逆変換演算子を記憶する手段
   と、 前記三次元ボックスをこれより小さい複数の副ボックス
   に分割する処理を、所定の解像度に一致した、副ボック
   スの観察方向に対する前面領域を有する副ボックスを作
   り出せるまで再帰的に行うボックス分割手段と、 前記逆変換演算子を記憶する手段の出力信号および前記
   ボックス分割手段の出力信号に応じて、前記ボックス分
   割手段による分割後の副ボックスの各々について前記逆
   変換演算子を使用して逆変換動作を行うことにより前記
   ワールド空間中に前記三次元立体との交差を検出するた
   めのテスト・セルを発生するテスト・セル発生手段と、 前記三次元立体の関数表現を記憶する手段の出力信号お
   よび前記テスト・セル発生手段の出力信号に応じて、前
   記ワールド空間中において前記三次元立体と交差するテ
   スト・セルに対応する副ボツクスを検出する手段と、 前記検出された副ボックスを示す情報を記憶する手段
   と、 前記副ボックスに対応する前記テスト・セルが前記三次
   元立体に交差しない場合、ボックス分割手段による分割
   を停止する手段と、 を具備する図形処理装置。