JPS6365576A - 立体図形処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は、三次元立体の空間表現を発生する手段を有す
る立体モデル作成装置に係シ、時に三次元立体の変換の
関数表現を発生する立体図形処理装置に関する。

Ｂ、従来技術 檀々の技術と使用することにより図形処理装置中で種々
の物体（ｏｂｊｅｃｔ）を表現することができる。立体
を表現するのに特に適当な技術としては、“組立て立体
幾何（Ｃ８Ｇ）”があげられる。

この技術によると、三次元（３−Ｄ）立体は、その物体
内に位置する点の組を特定する関数定義によって表現す
る。典型例においては、物体は、当該物体内の点？アク
セスしたときには“真”を、そうでないときには“偽″
を生じさせるプール関数によって特定する。この技術は
、物体の体積ではなく物体の稜線及び面を特定する線描
画技術と好対照をなす。

□　　物体の関数定義すなわち表現は、物体を作り出す
点の組を有効に特定する。例えば、球の関数定義は、中
心からある値の半径内に入る点の組？特定する。複合物
体は、構造上基本的な物体すなわち“原始物体（基本物
体）″例えば球、無限面、無限円筒の関数定義を組合せ
ることにより特定する。例えば、ダンベルの関数定義は
、異なる位置の２つの球のそれぞれの関数定義と、球の
中心を通る軸を有する無限円筒の関数定義と、球の位置
で円筒の頭部が切り捨てられる２つの平らな半空間の関
数定義とを含む。球、円筒および半空間の関数定義は、
和集合（ｓｅｔ　　ｕｎｉｏｎ）演算子および槓集合（
ｉｎｔｅｒｓｅｃｔｉｏｎ）演算子のような組合せ演算
子と使用して（すなわち集合論を使用して）組合せる。

また、例えば、切抜きすなわち穴を有する複合物体を定
義するために、減算演算子を使用して′”原始物体”を
組合せることができる。

このように、大きな物体から小さな物体を減じることに
よって中空複合物体を定義することができる。このよう
な複合体は、この明細誉中で用いる言葉の定義からすれ
ば依然として゛立体″である。

何故なら、複合物体を作り出す個々の物体の定義が立体
だからである。

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

このようにして定めることのできる形の範囲は、実際に
は選択された原始物体の組に依存する。多くの従来装置
においては、物体は平らな半空間からのみ構成される。

平らな半空間は、平面の一方の側に存在する無限物体の
関数定義である。立方体の関数定義は、例えば、積集合
（ｓｅｔ　１ｎｔｅｒｓｅｃｔｉｏｎ）演算子を使用し
て６個の半空間の関数定義を組合わせることによって定
める。他の装置は、円筒、球、円環面体、楕円面および
一様な螺旋（ｅｖｅｎｈｅｌｉｃｅａ）と使用する。

しかし、これらの技術と使用しても正確に定義できない
形がある。例えば、卵形（これは基本的に先細の球形で
める〕、断面がボックス形状の螺旋、二重巻き螺旋がそ
うである。これらは、従来、より単純な形状、規定の平
らな半空間で近似するのが非常に困難でめった。

従来、現存する原始物体に変換？施すことにより上述の
ような形？発生することが提案されている。例えば、卵
形は、球に先細シ変換（スケール・ファクタが１つの軸
に沿って変化する変換）を施すことにより発生できる。

円筒は、これを軸に関してねじる変換ｒ使用することに
より螺旋になる。このような変換の例は、“コンピュー
タ・グラフィックス（Ｃｏｍｐｕｔｅｒ　　Ｇｒａｐｈ
ｉｃｓ）”Ｖｏｌ。

１８、Ｎｏ、３、第２１頁乃至第６０頁に掲載されたア
ラン・′バー（Ａｌａ、ｎ　　Ｂａｒｒ）著の論文に記
載されている。この論文に記載された技術を使用しても
、比較的単純な種類の物体の有効表現を発生できるだけ
である。

”有効辰現”とは、有用な結果を発生するために実際に
処理にかけることのできる表現をいう。

処理の結果は独々の形ととることができる。物体の二次
元（２−Ｄ）像？発生することが８晋となることが多い
。また、例えば、体積、質量中心、慣性モーメントおよ
び表面積のような物体に関連した臨界データを計算する
ことが必要になることもある。さらに、例えばロボット
制御のように特定の時間において２つの物体がある空間
領域をともに占有しているか否かを知る必要があること
もある。

物体の関数定義を処理するために、空間再分割という蚊
何が頻繁に匣用されている。この技術を３−Ｄ立体の２
−Ｄ透視図を発生する方法に適用した場合のことが、１
９８２年３月に発行された１コンピユータやデザイン（
ＣｏｍｐｕｔｅｒＤｅｓｉｇｎ　）”　Ｖｏｌ、１４、
Ｎｏ、２に掲載されたウッドワーク（Ｗ　ｏ　ｏ　、ｄ
　ｗ　ａ　ｒ　ｋ　）およびフィンラン（Ｑｕｉｎｌａ
ｎ）著の１体積モデル評価における複雑性の低減（Ｒｅ
ｄｕｃｉｎｇ　　Ｔｈｅ　　Ｅｆｆｅｃｔ　　ｏｆＣｏ
ｍｐｌｅｘｉｔｙ　　Ｏｎ　　Ｖｏｌｕｍｅ　　Ｍｏｄ
ｅｌＥｖａｌｕａｔｉｏｎ）”という題名の論文に説明
されている。これを要約すると、次のようになる。

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

Ｃ０発明が解決しようとする問題点 描写しようとする物体が、例えば平らな面を有している
場合のように、ワールド空間および透視空間の双方にお
いて容易に定義できれば、上記従来方法はうまくいく。

しかし、物体が非常に複雑な形をしているときには、物
体の関数定義は、上記従来方法が実用的でなくなってし
まうほど管理不能なものになってしまう。

上記ウッドワーク外の論文は、空間再分割方法を使用す
ることにより三次元立体の二次元像を発生する方法を開
示しているが、保全発生させるためにせよそうでないに
せよ、変換および原始物体を使用して複雑な物体を発生
する方法は示唆していない。

事実、例えば、医学やロボットの分野では、複雑な物体
のモデル作成の必要性が生じている。医学の分野では、
複雑な手術を計画するために、Ｘ線および他のこのよう
なデータから心臓のような器官および血管のような身体
の他の多くの部分の正確な三次元（３−Ｄ）表現を容易
に発生できることは有益なことである。また、ロボット
の分野では、機械加工および組立てプロセスを改良する
ために機械加工されるべき部分のできるだけ正確なモデ
ル作成が必要である。

このように、現在モデル作成？必要としている物体は、
従来技術によっては適当に処理することができないほど
複雑なものである。例として、無限円筒の形の原始物体
２便用して鹿管網のモデルを作成する場合の問題点につ
いて考えてみると、頭部切り取シ、（軸についての）ね
じり、曲げ方向転換、スケーリング、変換および結合と
いった動作と組合せる必要がある。従来技術は、このよ
うな複雑な物体の有効に処理できるモデル表現を発生す
る方法は示唆していない。

本発明は、組立て立体幾何の原理に基き、複雑な物体の
空間表現を容易且つ有効な態様で発生できる立体図形処
理装置を提供することを目的とする。

本発明の別の目的は、三次元立体またはこれに含まれる
原始物体それ自身の変換と行う必要なく、三次元立体の
空間表現と発生できる立体図形処理装置を提供すること
にある。

Ｄ１問題点を解決するための手段 本発明による立体図形処理装置は、 少くとも１つの原始物体および少くとも１つの変換演算
子を含んで三次元立体を定義する構造と記憶する物体定
義記憶手段と、 ワールド空間会定義する三次元ボックスの関数定義を記
憶するワールド空間定義記憶手段と、上記三次元立体を
定義する構造に含まれた変換演算子によって特定される
変換動作の逆を行うのに必要な逆変換演算子を記憶し、
変換演算子と受けてこれに対応して逆変換演算子を出力
する逆変換演算子記憶手段と、 上記三次元ボックスをこれよシ小さな副ボックスに漸進
的に分割する処ｆ＃Ａを、所要の解像度に符合した寸法
の副ボックスが作り出されるまで続けるボックス分割手
段と、 上記三次元立体と定義する構造に含まれる原始物体に適
用されるべき当該構造中の変換演算子？検出するだめに
上記構造を走査する走査手段と、上記ボックス分割手段
の出力信号および上記逆変換演算子記憶手段から出力さ
れる上記走置手段によって検出された変換演算子に対応
した逆変換演算子を使用して、上記所要の解像度に符合
した副ボックスから原始物体の空間にテスト・セルを発
生するテスト・セル発生手段と、 上記テスト・セルが上記原始物体と交差するか否かを判
断する比較手段と、 上記比較手段の出力信号に応じて、上記原始物体と交差
するテスト・セルに対応する副ボックスと示す情報分記
憶する記憶手段と を具備する。

８０作用 不発明による立体図形処理装置は、まず、初期ステップ
として、 （０少くとも１つの原始物体および少くとも１つの変換
演算子と含んで三次元立体を定義する構造？物体定義記
憶手段に記憶させ、 （１１）　　ワールド空間を定義する三次元ボックスの
関数定義をワールド空間定義記憶手段に記憶させ、輸）
　上記三次元立体と定義する構造に含まれた変換演算子
によって特定される変動動作の逆を行うのに必要な逆変
換演算子を変換演算子に対応させて逆変換演算子記憶手
段に記憶させる。

次に・ Ｏｖ）　　上記三次元ボックスをこれより小さな副ボッ
クスに斯道的に分割する処理？、所要の解像度に符合し
た寸法の副ボックスが作り出されるまで続け、 Ｍ　　上記三次元立体を定義する構造に含まれる原始物
体に適用されるべき当該構造中の変換演算子を検出する
ために上記構造を走査し、（ｖｌ）上記検出された変換
演算子に対応する逆変換演算子を使用して、上記所要の
解像度に符号した寸法の副ボックスから原始物体の占め
る空間にテスト・セルを発生し・ ＆ｉｉＪ　　上記テスト・セルが上記原始物体と交差す
るか否かを判断し、 Ｑｌｌ：　　上記原始物体と交差するテスト・セルに対
応する副ボックスを示す情報を記憶する。

Ｆ、実施例 本発明の実施例と詳細に説明する前に、ＣＳＧを使用す
ることによシ物体の関数定義を評価する原理について説
明する。

一般に、立体モデルの評価は、立体の内側および外側し
たがって立体の境界を決定する処理ということができる
。評価処理が最も一般的に使用されるのは、物体の２−
Ｄ画像を描くときである。

一般に、物体の表面領域を決定するために体積や重心の
ような’Ｊ［置物性を計算するのも可能であるが、本発
明では、このような他の方法はとらない。

習慣的に、物体は、第２Ｂ図に示されたような木構造を
使用して組立て立体幾何（ｃｏｎｓｔｒｕｃｔｉｖｅｓ
ｏ目ｄ　　ｇｅｏｍｅｔｒｙ）の原理に従って定義され
る。

第２Ａ図は、前述のダンベル１０を例示したものである
。第２Ｂ図は、ダンベル１０Ｅ特定する木構造２０を示
す。これは、連結リスト記憶構造（ｌｉｎｋｅｄ−１ｉ
ｓｔ　　ｓｔｏｒａｇｅ　　５ｔｒｕｃｔｕｒｅ）によ
って実現できる。数学的には、ダンベルの定義は次のよ
うに表現することができる。

ダンベル＝Ａ＋Ｂ＋Ｃ＊Ｄ＊Ｅ ここで“＊”は、第２Ｂ図において“ＡＮＤ″とじて示
された数学的積集合演真子（１ｎｔｅｒｓｅｃｔｉｏｎ
ｏｐｅｒａｔｏｒ）で＝ｌｌ）、”十″は、第２Ｂ図に
おいて”ＯＲ″として示された数学的オロ演算子（ｕｎ
ｉｏｎ　　ｏｐｅｒａｔｏｒ）である。Ａ、Ｂ、Ｃ，Ｄ
およびＥは、球Ａ、球Ｂ１無限円筒Ｃ１線１２の右側の
半空間りおよび線１４の左側の半空間Ｅに対する数学的
表現である。原始物体Ａ、Ｂ、Ｃ１ＤおよびＥに対応す
る関数定義は、木構造２Ｑ中の梨２２　ａ、２２ｂ、２
２ｃ、２２ｄおよび２２ｅに配置される。数学的演算子
は節２４において定義される。

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

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

空間領域６０は、評価すべき物体を含むものとする。物
体を定義する組立て立体幾何表現２０すなわち関数定義
は、この空間領域５０内で詳しく調べ単純化する。単純
化したものは、いずれの場所でも有効というわけではな
いが、考慮中の領域内のオリジナル物体と等価である。

単純化の手順は次の通りである。

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

２、集合演算子を適用することによって作られる複合物
体に対しては、単純化したオペランドに対して（基本的
に３値の）プール論理を帰納的に適用する。例えば、 空　　　和集合表現２　→表現２ 表現１　和集合空　　　→表現１ 充満　　和集合表現２　→充満 表現１　和集合充満　　−充満 および、 空　　　績果合表現２　→空 表現１　積集合空　　　−空 充満　　槓集合表現２−表現２ 表現１　墳集合充満　　−表現１ この単純化の結果が空ならば、考慮中の空間領域内にお
いて物体の内＃Ｊは無い。画像と描いている最中ならば
、この領域はスクリーン画像に何も寄与しない。（ただ
し、質量特性を計算中のときには、空間は体積またはモ
ーメントに何も寄与しない。） 単純化の結果が“充満″ならば、空間領域は物体によっ
て完全に占有される。１つの視野から画像を構成する場
合、この空間領域は観察者に対向する面？含まないので
二次元像に何も寄与せず、物体の内側はその対向面に隠
れる。（ただし、質量特性については、領域全体が計算
中の体積またはモーメントに寄与する。） 通常、表現は少くとも１つの限界点（線、面）を含む。

ある環境においては、表現は直接取扱えるほど単純であ
る。例えば表現は単一の平らな半孕間である。物体全体
の画像または質量特性への貢献度は直接計算できる。他
の場合には、空間領域はこれより小さな領域に分割する
。最も単純なのは、最も長い寸法の次元に垂直に半分に
分割する。しかし、第２Ｃ図においては、空間領域３０
は、８個の小さな領域６１．３２．６６．３４．５５．
６６．３７および３８に分割する。そして、これらの新
たな領域に対し、“充満”および“空″のような表現ま
たは他の単純化表現が得られるまで単純化処理を繰返し
行う。

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

２個の物体を含む領域は、２つの面が又差する稜線を含
み、６つの物体を含む領域は、通常、頂点を含む。

画像に描くときには、面または稜線を描く。面を描く場
合、空間領域の中心における面の垂線？計算し、これを
、その位置から観察者へ向けて反射する光量？計算する
ために光源の予め知られた位置とともに使用する。より
複雑な稜線または頂黒領域を描くには、このように取扱
うべき１つの可視面と分離するために光線追跡法を使用
する。

（ただし、質量特性を計算するには、セルは単に”半光
満″であると仮定する。） 前述のように、このような方法は理論的にはうまくいく
が、変換された関数定義の複雑性が高い物体および／ま
たは変換の大きな集合に対しては実用的ではない。従っ
て、このような方法は、物体の構成部分が単純な原始図
形によって定義できないときには、実用的でなくなる。

本発明は、複雑な物体と定義できるようにするものであ
る。複雑な物体は、単純な原始物体に対して変換と行い
且つ変換と原始物体とと組合せることによって表現でき
る。実際には、得られた定義は、複雑すぎて直接取り扱
うことはできない。

そこで、物体の構成要素をなす原始物体を定義するかわ
りに、空間を変換する。物体の定義が行われるべき空間
（ワールド空間）を定義する例えば矩形ボックスのよう
なボックスの関数表現を確立する。しかし、単純な原始
物体をそれらのオリジナル座標系からワールド空間に変
換する（これがバー（Ｂａｒｒ）の技術の原理である）
のではなく、その代りに、一般に原始物体に対して行わ
れる変換の逆を行うことにより矩形ボックスを変換する
。

そして、矩形ボックスに対して前述の再分割アルゴリズ
ムを適用し、副ボックスを逆変換したものが原始物体と
そのオリジナル座標系中で交差するかテストする。これ
によシ、原始物体自身と変換する必要がなくなる。

例えば、原始物体を座標系に沿ってａｘｔ　ｓｙおよび
ｓｚなるファクタで拡大する場合、考慮中のワールド空
間の領域（すなわち、拡大縮小した原始物体と含む物体
が存在する空間の領域）と上述のファクタで縮小し、原
始物体がはじめに定義された”物体”空間中で上記縮小
領域と拡大していない原始物体と比較する。この結果は
、ワールド空間中の拡大した原始物体をワールド空間の
拡大していない領域に対してテストするのと同じである
。

スケーリングおよび平行移動のような変換の場合には、
スケーリングされた領域は、変換後ももとの軸に対して
矩形ボックスのままである。回転の場合には、空間は矩
形と維持するが、もはやもとの軸に対して平行ではない
。曲げあるいはねじりのような変換の場合には、空間は
逆方向に曲がるかねじれ、もはや単純に矩形ではない。

このように新たに変換された空間に対して物体をテスト
する必要がるる。＄３Ａ図乃至第６Ｄ図は、バーが曲が
ったダンベルについてのこのような例を示す、。

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

次に、第１図、第６Ａ図および第３Ｄ図と参照して、本
発明の実施例全群しく説明する。

第１図は、立体モデルを作成する本発明による立体図形
処理装置の実施例を示す。

第１図に示された構成要素は、一般的なプログラム可能
図形処理装置を適当にプログラムすることにより実現で
きる。このようにするかわシに、各構成要素を個別の・
・−ドワイヤード回路（論理回路）でも実現できる。一
般に、図形処理装置は、記憶装置、処理手段、データ入
力手段（例えば、キーボード）およびデータ出力手段（
例えば、陰極線管表示装置）を含む。第１図に示された
構成要素は、例えばロボットの制御機構の一部として作
用し得る。

第６Ａ図は、第２Ａ図に示されたダンベルとはバーが曲
がっている点で異なるダンベル１０′を示す。このダン
ベル１０′は、数学的に次のように表現することができ
る。

ダンベル１０’−（ｔｌＡ）＋（ｔ２Ｂ）＋（ｔ３（Ｃ
＊Ｄ＊Ｅ））ここで、“十″は数学的和集合演算子を、
“＊″は数学的和集合演算子を、Ａは第６Ａ図に示され
た点゛ａ″を中心とする球Ａの数学的表現と、Ｂは第３
Ａ図に示された点”ｂ”６中心とする数学的表現を、Ｃ
は第３Ａ図に示された無限円筒Ｃを、Ｄは第６Ａ図の右
側の半空間りを、Ｅは第６Ａ図の左側の半空間Ｅを、ｔ
ｌおよびｔ２は平行移動（ｔｒａｎｓｌａｔｊｏｎ）演
算子、ｔ６は曲げ演算子をそれぞれ示す。

不発明は、物体？定義する構造中に原始物体および組合
せ演算子定義を含むものである。この構造は、第３Ｂ図
に示されたような木構造の形をとることができる。この
構造の１つの実施例は、ある要素が原始物体、組合せ演
算子または変換演算子のいずれを特定するかを当該構造
中で示す異なった型の記憶要素？有する連結リスト構造
の形をとる。第１図の物体定義記憶手段７２は、物体定
義を形成する構造のために設けられている。次に述べる
説明では、物体は、連結リスト木構造の形で定義される
ものとする。

ワールド空間定義記憶手段５４は、ワールド空間？示す
ボックスの関数定義のために設けられている。通常、ボ
ックスは矩形である。しかし、例えば、円筒のような他
の形をとることができる。

関数定義も種々の形をとることができるが、例えば連結
リストの形の木構造とすることができる。

矩形ボックスの定義は、６個の平らな半空間の撰集合（
ｔｎｔｅｒｓｅｃｔｉｏｎ）の形をとることができる。

ただし、立方体は、その中心と、その中心から１つのす
みまでベクトルによって定義できる。

制御手段５日は、ボックス／副ボックス分割手段６０に
物体に対する比較のために矩形ボックスを選択させる。

変換決定および物体単純化手段６８は、変換されるべき
物体が複数の原始物体から形成される場合に単純化され
た関数定義？発生するのに使用される。矩形ボックスの
１回またはそれ以上の分割（再分割）の後、テスト・セ
ル−原始物体比較手段６６の出力によシ、テスト・セル
が物体中の１つまたはそれ以上の原始物体と交差しない
ととが示されることがある。この場合、矩形ボックス領
域をさらに再分割する際、これら原始物体の関数定義は
、その副分割領域に対応したテスト・セルに対して比較
する８敬はない。物体単純化手段６８は、物体全体の関
数定義のうち、前の比較動作の結果に応じて種々の段階
で関係してくる部分を選択する。物体単純化手段６８は
、現在選択されているボックスまたは副ボックス（Ｑ変
換結果に対して比較と行う原始物体？選択する。

このようにして選択された各原始物体に対して、変侠決
定および物体単純化手段６８は、物体乞作り出すのに当
該原始物体をワールド空間に変換するのに必要な変換動
作と特定する。このように特定された変換動作の逆動作
が、逆変換演算子記憶手段５６中で定義される。

現在選択されているボックスまたは副ボックスに対して
逆変換処理手段６２中で逆変換演算子が適用され、テス
ト・ボックスが発生する。このようにして作り出された
テスト・ボックスは、テスト・セル発生手段６４を通過
して比較手段６６にテスト・セルとして直接与えられる
か、または、後述のように、テスト・セル発生手段６４
による矩形ボックス（または副ボックス）の逆変換動作
から単純化テスト・セルが作り出され、これが比較手段
６６に与えられる。

物体およびテスト・セル関数定義は比較手段６６中の比
較動作によって交差するか否かがテストされ、前述のよ
うに、基本的に６値のプール比較出力、すなわち、”充
満″、“空″または゛部分充満″が発生する。比較手段
６６の出力は、制御手段５８および変換決定および物体
単純化手段６８に与えられる。

制御手段５８は、各テスト・セルと原始物体との比較結
果に応じて次の６つのうちのいずれかの態様で動作する
。

（１）交差が検出され且つ考慮中のボックスまたは副ボ
ックスが所要の解像度よりも太きければ、制御手段５８
は、ボックス／副ボックス分割手段６０に、考慮中のボ
ックスまたは副ボックスを次の段階において評価を行う
のに適当な複数のより小さな副ボックスに分割させる。

第３Ｃ図は、８個に再分割したところと示す。ただし、
例えば、２のような別のファクタを選択できる。

（１１）交差が検出され且つ考慮中のボックスまたは副
ボックスの寸法が所要の解像度に符合していれば、この
ことが結果記憶手段７０に記憶される。

輛）　交差が検出されなければ、考慮中のボックスまた
は副ボックスの検査が終了し、このことが記録される。

第３Ｃ図および第３Ｄ図は、本発明の実施例の動作原理
と示す。第３０図に破線で示されているように、物体の
構成要素を成す原始物体（例えば、円筒Ｃならびに２つ
の半空間りおよびＥ）とツールド空間に変換するかわ９
に、原始物体の関数定義をそのオリジナル座標系に保持
し、そのかわりに空間を変換する。すなわち、第３Ｂ図
に示された木構造中に示された曲げ変換ｔ３の逆を使用
してワールド空間中の空間領域３９を変換し、円筒Ｃの
座標系にテスト・セル６９′を発生して、該セルを円筒
Ｃと比較する。球ＡまたはＢに対するワールド空間領域
の比較では、ワールド空間中で異なった変換（それぞれ
ｔ　または１２）１−実行する。何故なら、これらの球
は、ダンベル１０′ト形成するために、曲げることなく
（ａからａ′へまたはｂからｂ′へそれぞれ）単に移動
するだけだからである。

テスト・セルは、副ボックスの逆変換の関数定義によっ
て形成できるが９、副ボックスの逆変換物のか：ｑＤに
、この逆変換物と中心が一致し且つこれに外接する単純
な５−Ｄ体積（ｖｏｌｕｍｅ）を使用できる（単純な３
−Ｄ体積とは、比較的定義および処理が簡単な例えば球
、矩形ボックスまたは楕円面のような体！Ｒ（立体）の
ことをいう）。これは、副ボックスの逆変換物と交差す
る物体のいずれかの部分は、当該逆変換物と中心が一致
する外接球、矩形ボックスまたは楕円面と交差するから
である。単純化されたテスト・セルが使用されても（こ
れはテスト・セル発生手段６４によって発生させられる
）、これによる影響は、逆変換物それ自身（すなわち”
テスト・ボックス”）とテスト・セルとして使用するこ
とによシ得られるのと同じ解像度？得るために、さらに
再分割するステップを導入しなければならないだけのこ
とである。便用されるテスト・セルとテスト・ボックス
との間の不一致の程度を最小にするために、処理は簡単
だがテスト・ボックスの形状および寸法に近いテスト・
セルを選ぶ必要がある。

制御手段５８によって結果記憶手段７０に記憶され実際
の情報は、実行されるべきタスクに依存する。

質量計算を実行中のときは、質量は、検出された（“所
要解像度”の副ボックスに対応する）充満セルの数の相
と、”半充満“セルとして記録される部分的に充満され
たセルとして単に累積される。

例えば、複合物体の二次元（２−Ｄ）像を発生中のとき
ては、像の画素マツプを結果記憶手段７０中に形成でき
る。便宜上、矩形ボックスは、その軸の１本が観察方向
に平行になるように視点（投影点）に対して配列され、
再分割処理は画像形成中に副ボックス列が観察方向に平
行か検査するように調整される。像の視点すなわち投影
点に最も近い面であるボックスの前面は、その像に対す
る観察面と形成する。像の％画素は、観察方向に平行な
画素の寸法に一致した前面領域を有する副ボックスの列
に対応するように配列できる。この配列は必須のもので
はなく、例えば、物体の一般的でない図（例えば、歪曲
図、立体図等）を発生する必要があるときには、他の形
状および向きのボックスと使用することができる。制御
手段５８は、意図する像中で見たときに、物体の前面に
より近い方の副ボックス（例えば観察面に最も近い副ボ
ックス）を遠い方の副ボックスより先に処理させるよう
に構成できる。対応画素に対するセツティングが定まれ
ば、サブ・ボックスは考慮する必要はない。制御プログ
ラムは再分割処理の進行記録と維持する。この記録は、
木得造記録、ピット・マツプまたは他の適当な形をとる
ことができる。

物体の前面が検出されると、これに関連する画素の必要
な色および／または輝度と、例えば光追跡技術？使用し
て決定できる。テスト・セル中の原始物体の面に対する
垂線？示すベクトルは、当該原始物体の関数定義から計
算できる。この原始物体の物体定義構造中に示された変
換と使用してこの垂線ベクトルをワールド空間中に変換
し、この変換されたベクトルを光源と示す１つまたはそ
れ以上のベクトルと比較することにより、テスト・セル
に対応する画素の色および／ｉたは輝度を決定できる。

物体の変換物である像（例えば、二次元透視図）を発生
するためには、物体を定義する構造の根の位置に必要な
変換定義を付加し、変換（例えば、透視）観察空間を”
ワールド空間″とみなすだけでよい。このようにして、
像の歪曲をシミュレートでき、また物体の特別の図（例
えば、魚眼レンズを通して見た場合に得られる像の図）
を作り出すことができる。

以上、理解分容易にするために、簡単な物体および変換
ととりあげて説明したが、本発明は、複雑な物体および
変換にも適用できる。本発明によれば、複合物体（複雑
な物体）は、単純な物体を組合せて作り出すことができ
、単純な物体と同様に他の物体と交差させることができ
る。

袈するに、本発明は、ワールド空間を示すボックスを分
割したものから作り出される副ボックスが物体を構成す
る原始物体と交差するかテストするものである。これは
、物体を定義する構造を走査して原始物体の関数定義を
検出し、原始物体に変換演算子を適用すべきか判断し、
適用すべきならば、変換演算子の逆の演算子（逆数）を
使用して副ボックスから原始物体空間中にテスト・セル
を発生し、原始物体空間中において原始物体とテスト・
セルの関数定義を比較して副ボックスに対応したテスト
・セルが原始物体と交差するか判断することにより行わ
れる。このような処理は、交差するかテストすべき各原
始物体および副ボックスについて行う。

Ｇ１発明の効果 以上の説明から明らかなように、本発明は、三次元立体
またはこれに含まれる原始物体それ自身の変換を行う必
要がないから、簡単に三次元立体の空間的表現を作り出
すことができる。

【図面の簡単な説明】

第１図は、本発明による立体図形処理装置の一実施例を
示すブロック図・ 第２Ａ図仕：第２Ｂ図および第２Ｃ図は、従来技術によ
る組立て立体幾何の原理を示す説明図、第５Ａ図、第５
Ｂ図、第３Ｃ図および第３Ｄ図は、第１図の実施例の動
作原理？示す説明図である。 ５４・・・・ワールド空間定義記憶手段、５６・・・・
逆変換演算子記憶手段、６０・・・・ボックス／副ボッ
クス分割手段、６２・・・・逆変換処理手段、６４・・
・・テスト・セル発生手段、６６・・・・テスト・セル
−原始物体比較手段、７０・・・・結果記憶手段、７２
・・・・物体定義記憶手段。 出願人インタづしタナル・ビジ木ス・マシーンズ・コー
ポレーション代理人　弁理士　　岡　　　１）　　次　
　　生（外１名） Ｒ区 第３Ａ図 ： ■ 第３Ｄ図

Claims (1)

1. 【特許請求の範囲】 少くとも１つの原始物体および少くとも１つの変換演算
   子を含んで三次元立体を定義する構造を記憶する物体定
   義記憶手段と、 ワールド空間を定義する三次元ボックスの関数定義を記
   憶する物体定義記憶手段と、 前記三次元立体を定義する構造に含まれた変換演算子に
   よつて特定される変換動作の逆を行うのに必要な逆変換
   演算子を記憶し、入力変換演算子に対応した逆変換演算
   子を出力する逆変換演算子記憶手段と、 前記三次元ボックスをこれより小さな副ボックスに漸進
   的に分割する処理を、所要の解像度に符合した寸法の副
   ボックスが作り出されるまで続けるボックス分割手段と
   、 前記三次元立体を定義する構造に含まれる原始物体に適
   用されるべき当該構造中の変換演算子を検出するために
   前記構造を走査する走査手段と、前記ボックス分割手段
   の出力信号および前記逆変換演算子記憶手段から出力さ
   れる前記走査手段によつて検出された変換演算子に対応
   した逆変換演算子を使用して、前記所要の解像度に符合
   した副ボックスから原始物体の空間にテスト・セルを発
   生するテスト・セル発生手段と、 前記テスト・セルが前記原始物体と交差するか否かを判
   断する比較手段と、 前記比較手段の出力信号に応じて、前記原始物体と交差
   するテスト・セルに対応する副ボックスを示す情報を記
   憶する記憶手段と を具備する立体図形処理装置。