JPH06215133A - データ処理装置および方法 - Google Patents

Abstract

(57)【要約】 【目的】 共面オブジェクトとピッキング・ボリューム
との交差を処理する簡単な装置および方法を提供する。 【構成】 共面オブジェクトをディスプレイ上に表示
し、表示されたオブジェクトを含む面がピッキング・ボ
リュームのいずれかのエッジと交差するかどうかを計算
し、次いで、オブジェクトの面がピッキング・ボリュー
ムのエッジと交差すると判断されるときは、表示された
オブジェクトとピッキング・ボリュームとが交差するか
どうかを計算し、表示されたオブジェクトがピッキング
・ボリュームと交差するかどうかの指摘を提供する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、一般にオブジェクトの
ピッキングおよび特にオブジェクトが多次元的グラフィ
ック・アプリケーションの中でピッキング・ボリューム
と交差するかどうかを決める技術に関連する。

【０００２】

【従来の技術】多次元的会話型グラフィックス・アプリ
ケーションにおいて、オブジェクトまたは基本立体 (pr
imitive) がピッキング・ボリュームと呼ばれるある量
のインタレストと交差するかどうか検出することが必要
である。これはピッキング問題として知られている。ピ
ッキング・ボリュームはディスプレイ目的のためのクリ
ッピング・ボリュームであるかもしれない。または、ク
リッピング・ボリューム中の基本立体を選択するための
通常より小さいボリュームに分かれるかもしれない。典
型的にはピッキング・ボリュームは、複数の面によって
囲まれたボリュームであって通常立方体である。一般に
使われるクリッピング技術の１つを使用して、すべての
基本立体をピッキング・ボリュームでクリップすること
によって、ピッキング問題を解決するのが伝統であっ
た。

【０００３】

【発明が解決しようとする課題】これらのクリッピング
技術は典型的に、簡単な受け入れおよび拒絶のテストを
提供するために、コーヒン・スーザーランド（Cohen-Su
therland）コーディング技術を利用する。しかし、基本
立体を受け入れるか、あるいはピック・ボリュームの中
にあるとして拒絶するテストが矢敗するならば、クリッ
ピング技術は、典型的には基本立体とピッキング・ボリ
ュームの交差を計算するが、これは計算としては集中的
なタスクである。

【０００４】

【課題を解決するための手段】本発明は、共面上のオブ
ジェクトがピッキング・ボリュームと交差するかどうか
を処理する方法を含み、ディスプレイ上のオブジェクト
を表示し、表示されたオブジェクトを含んでいる面がピ
ッキング・ボリュームのエッジを交差するかどうかを最
初に計算し、オブジェクトの面が、ピッキング・ボリュ
ームのエッジと交差すると決められたとき、表示された
オブジェクトおよびピッキング・ボリュームが交差する
かどうかを計算し、表示されたオブジェクトがピッキン
グ・ボリュームと交差するかどうかの指摘を出すステッ
プを含んでいる。本発明は、共面上のオブジェクトがピ
ッキング・ボリュームと交差するかどうかを処理する装
置を含む。

【０００５】この装置は、オブジェクトを含んでいる面
がピッキング・ボリュームのエッジと交差するかどうか
を決めるための第１の装置、オブジェクトの面がピッキ
ング・ボリュームのエッジを交差すると決定したとき、
オブジェクトおよびピッキング・ボリュームが交差する
かどうかを計算するための第２の装置を含んでいる。

【０００６】

【実施例】本発明は、既知のクリッピング・技術を使用
してオブジェクトまたは基本立体とピッキング・ボリュ
ームとの交差を決定することなしに、オブジェクトまた
は基本立体がピッキング・ボリュームの範囲内に位置す
るかどうかを検知することによりピック事象を処理する
ことに向けられる。ほとんどのアプリケーションの中で
ピックされるようなオブジェクトまたは基本立体を処理
するためには、交差の点を計算することなく、オブジェ
クトまたは基本立体がピッキング・ボリュームを交差す
るかどうかを検出することで十分である。この簡略化に
より、ハードウェアを単純化することができ、コストが
低減され、実行速度が速くなる。

【０００７】図１は、発明の好まれた実施例によって利
用された典型的ディジタルコンピュータ１００のブロッ
ク図である。コンピュ ーターは、メモリ１２０、入力
装置１３０および出力装置１４ ０に結びつけられたメ
イン・プロセッサ１１０を含む。メイン・プロセッサ１
１０は、ひとつのプロセッサでも複数のプロセッサでも
よい。入力装置１３０は、入力装置のキーボ ード、マ
ウス、タブレットなどを含む。出力装置１４０は、出力
装置のテキスト・モニタ、プロッタなどを含む。メイン
・プロセッサは、また、グラフィックス・アダプタ２０
０を通してグラフィックス・ディスプレイのようなグラ
フィックス出力装置１５０に接続することができる。

【０００８】グラフィックス・アダプタ２００は、メイ
ン・プロセッサ１１０からバス１６０の上の、グラフィ
ックスに関する命令を受け取る。グラフィックス・アダ
プタは、それからグラフィックス・アダプタ・メモリ２
３０に結びつけられたグラフィックス・アダプタ・プロ
セッサ２２０でそれらの命令を実行する。グラフィック
ス・アダプタの中のグラフィックス・プロセッサが、そ
れらの命令を実行し、それらの命令に基づいてフレーム
・バッファ２４０を更新する。グラフィック・プロセッ
サ２２０は、また、基本立体の生成のための特有な型を
生成するために、特別なハードウェアを含むであろう。
フレーム・バッファ２４０は、グラフィックス出力装置
上に表示されるためにあらゆるピクセルのためのデータ
を含む。ランダム・アクセス・メモリー・ディジタル・
アナログ変換器（RAMDAC）２５０は、グラフィックス・
ディスプレイ１５０に提供するためにフレーム・バッフ
ァにストアされたディジタル・データをRGB信号に変換
して、メイン・プロセッサから希望のグラフィックス出
力を生成する。

【０００９】図２は、ピック事象のようなグラフィック
ス機能を実行するためにホスト計算機およびグラフィッ
クス・アダプタによって典型的に利用されたコードの層
を図示しているブロック図である。ピック事象は、消
去、カラー変更、移動、その他のようなオブジェクトの
上のある機能を実行するためにピック・ボリュームを使
って、ピックされる事象である。DOSを始めとするオペ
レーティング・システム３００が、ホスト計算機の主要
なコントロールを提供する。オペレーティング・システ
ムのためにハードウェア集中的タスクを提供するオペレ
ーティング・システム・カーネル３１０が、オペレーテ
ィング・システムに結びつけられる。オペレーティング
・システム・カーネルは、直接ホスト計算機マイクロコ
ード３２０と通信する。ホスト計算機マイクロコード
は、ホスト計算機プロセッサによって実行される一次命
令セットである。グラフィックス・アプリケーション３
３０および３３２は、オペレーティング・システム３０
０に結びつけられる。この図形処理への応用ソフトウェ
アには、シリコングラフィック社（Silicon Graphic）
のGL、IBM社のgraPHIGS、MITのPEXその他がある。

【００１０】これらソフトウェアは、２次元または３次
元グラフィック処理の基本的機能を提供する。グラフィ
ックス・アプリケーション３３０および ３３２は図形
処理への応用API（適用業務プログラム・インタフェー
ス）３４０および３４２にそれぞれ結合する。APIは、
図形処理への応用のために計算的に集中的なタスクの多
くを提供し、グラフィックス・アダプタへの デバイス
ドライバのような、グラフィックス・ハードウェア に
より近いアプリケーション・ソフトウェアと適用業務ソ
フトウェアとの間のインターフェースを提供する。たと
えば、API ３４０および３４２は、GAI（図形処理への
応用インターフェース）３５０および３５２とそれぞれ
通信する。GAIは、アプリケーションAPIおよびグラフィ
ックス・アダプタ・デバイスドライバ３７０の間のイン
ターフェースを提供する。あるグラフィックス・システ
ムの中で、APIはまた、GAIの機能を実行する。グラフィ
ックス・アプリケーション、APIおよびGAIは、オペレー
ティング・システムおよびデバイスドライバによって、
ひとつのプロセ スであると考えられる。すなわち,グラ
フィックス・アプリケーション３３０、３３２、API ３
４０、３４２、そして,GAI３５０および３５２は、オペ
レーティング・システム３００およびデバイスドライバ
３７０によってそれぞれ、プロセス３６０および３６２
であると考えられる。プロセスは、オペレーティング・
システム・カーネルによってプロセスに割り当てられた
プロセスＩＤ（PID）によって、オペレーティング・シ
ステムとデバイスドライバによって識別される。プロセ
ス３６０および３６２は、たとえば、２個の別々のウィ
ンドウの中でのあるプログラムの２つの実行のように、
同時に２度実行されている同じコードを使用することが
ある。PIDが、同じコードの別々の実行を区別するため
に使われる。

【００１１】デバイスドライバは、オペレーティング・
システム・カーネル３１０の拡張（部分）であるグラフ
ィックス・カーネル である。グラフィックス・カーネ
ルは、直接グラフィックス・アダプタ３８０のマイクロ
コードと通信する。多くのグラフィックス・システムの
中で、GAI、あるいはGAI階層が使用されていなければAP
Iが、デバイスドライバに初めの要求命令を送り出すこ
とによりアダプタ・マイクロコードへのGAIまたはAPIか
らの直接アクセスを要請するであろう。

【００１２】それに加えて、多くのグラフィックス・シ
ステムは、また、アダプタ・マイクロコードが、デバイ
スドライバに初めの要求命令を送り出すことによって、
アダプタ・マイクロコードからGAI、GAI階層が使用され
ていなければAPI、への直接アクセスを要請することを
許す。両方のプロセスは、以下に直接メモリ・アクセス
（DMA）として参照される。データの大きいブロックを
転送しているとき、DMAが典型的に使われる。DMAは、デ
バイスドライバがDMAをセットするための最初の要求以
外、ディスプレイ・ドライバを経由する必要を排除する
ことにより、ホスト計算機およびアダプタの間のデータ
のより速い伝送を提供する。ケースによっては、アダプ
タ・マイクロコードは、アダプタ・マイクロコードによ
って利用されていた現在の属性を置き換えることを可能
にするコンテクスト・スイッチングを利用する。適応し
たマイクロコードが現在使用しているものと異なる属性
を利用するグラフィックス・アプリケーションからの命
令をアダプタ・マイクロコードが受取る時、コンテクス
ト・スイッチングが使われる。コンテクスト・スイッチ
は、典型的には、属性変更を認めるデバイスドライバに
よって始められる。

【００１３】ブロック３００ー３４０は、利用されてい
る型のグラフィックス・アダプタから典型的に独立して
いるソフトウェア・コード層である。ブロック３５０ー
３８０は、利用されている型のグラフィックス・アダプ
タに典型的に依存するソフトウェア・コード層である。
たとえば、異なるグラフィックス・アダプタが、グラフ
ィックス・アプリケーションソフトウェアによって使わ
れるとしたら、新しいGAI、グラフィックス・カーネル
およびアダプタ・マイ クロコードが必要とされる。そ
れに加えて、ブロック３００ ー３７０は、ホスト計算
機に常駐し実行される。しかし、アダプタ・マイクロコ
ード３８０は、グラフィックス・アダプタに常駐し、こ
れによって実行される。あるケースにおいて、しかし、
アダプタ・マイクロコードは、グラフィックス・アダプ
タの初期状態設定の間にホスト計算機によってグラフィ
ックス・アダプタにロードされる。

【００１４】典型的グラフィックス・システムの中で、
利用者はグラフィックス・アプリケーションに２次元ま
たは３次元モデルからイメージをつくるように命令す
る。利用者は、光源のロケーションおよび型を最初に選
択する。利用者は、それからアプリケーション・ソフト
ウェアに一組の定義済みまたは利用者定義オブジェクト
から要求されたモデルを作るように命令する。各オブジ
ェクトは、オブジェクトを記述しているひとつ以上の共
面上の図面基本立体を含みうる。たとえば、多くの三角
形のような 一組の図面基本立体が、オブジェクトの表
面を定義するために使われうる。利用者は、そのモデル
を見るためにウィンドウの中で透視画を提供し、希望す
るイメージを定義する。アプリケーション・ソフトウェ
ア は、オブジェクトを記述する図面基本立体をAPI、GA
I、そしてDMAが使われていなければデバイスドライバを
通してアダプタ・マイクロコードに送り出すことによ
り、そのモデルからイメージの生成を始める。アダプタ
・マイクロコードは、ウィンドウの中で見えないそれら
の図面基本立体をクリッピン グして（すなわち使用し
ない）、グラフィックス・ディスプレイ上にイメージを
生成する。アダプタ・マイクロコードは、利用者によっ
て与えられた透視画から残りの図面基本立体を見えるピ
クセルに分解する。このピクセルは次いでフレーム・バ
ッファにロードされる。この場合、３次元モデルのとき
は深さバッファがよく使用される。このステップは、図
面基本立体、変数および関係しているピクセルの数のた
めに計算的に非常に集中的である。フレーム・バッファ
の中でストアされて、グラフィックス・ディスプレイの
上に表示されるイメージは、ピクセルがどの図面プリミ
ティブまたはオブジェクトから由来するかというような
オリジナルの情報を典型的には持っていない。この結
果、ウィンドウ、利用者の透視画、モデル、照明、その
他が修正された場合、イメージは部分的あるいは全体的
に再生成される必要があるであろう。ウィンドウの中で
表示されたイメージを選ぼうとしているとき、これがま
た、困難を提示する。典型的３次元モデルにおいて、利
用者がウィンドウの中に表示される多くのオブジェクト
を含むイメージを持つとき、要求されたオブジェクトを
選ぶために、複雑で、ときとして時間がかかるプロセス
が必要となる。

【００１５】好ましい実施例の中で、ピック技術は、ア
ダプタ・フレーム・バッファの近くに存在するアダプタ
・マイクロコードを始めとする多くのロケーションの中
で利用される可能性がある。このアプローチは、また、
比較的に速くて、そしてかなり実行するのが簡単であ
る。それに加えて、ピック技術は、イメージが生成され
る前、あるいは生成後にグラフィックス・アダプタがデ
ータ・バックアップをグラフィックス・アプリケーショ
ン・ソフトウェアに渡すことによって、生成イメージが
システム・メモリに同様にストアされるグラフィックス
・アプリケーションに適用されることができる。このア
プローチは、かなり遅いが、既に存在するグラフィック
ス・アダプタ上でこの技術を利用することをを可能にす
る。ピック技術は、また、グラフィックス・アダプタ・
プロセッサのハードウェアの中で実行される可能性があ
る。このアプローチは、非常に速いが、多分特殊化され
たハードウェアを必要とする。これは、グラフィックス
・アダプタによって表示された基本立体の急速なピッキ
ングを可能にする。この分野の技術者は、この技術がホ
スト計算機またはグラフィックス・アダプタの範囲内で
多くの他のロケーションの中で適用される可能性がある
ことを理解するであろう。

【００１６】図３の中で図示されるように、好ましいピ
ッキング・ボリュームは、典型的には、６個の境界面お
よび１２個の境界エッジによって区切られている。しか
し、ピッキング・ボリュームは、２以上の次元を持っ
て、そしていっそう多くのまたはより少しの境界面によ
って区切られてもよい。境界エッジ５００は、ピッキン
グ・ボリュームにある２個の隣接する境界面が交差する
エッジの部分である。境界面５１０は、ピッキング・ボ
リュームに共通である境界面の部分である。境界面は、
３次元間隔をピッキング・ボリュームがその１つである
２７個の重複しない区域に分割する。２６個の他の区域
は、外区域と呼ばれる。ピッキング・ボリュームの８つ
の頂点（すなわち、３つの隣接する境界面の交差する
点）は境界頂点５２０である。境界表面、エッジおよび
頂点は、ピッキング・ボリュームの内側とする。

【００１７】基本立体は、一組の共面頂点によって典型
的に指定される。基本立体は、凸面でも凹面でもあるこ
とができ、穴を含むことができる。図４は、ピッキング
・ボリュームを横切っている穴をもつ凹形基本立体５４
０のイラストである。このオブジェクトのピッキングが
、図８を参照して詳細に記述される。

【００１８】図５は、共面上にないオブジェクトが全体
的または部分的にピッキング・ボリューム内にあるかど
うかを判断する仕方を示すフロー・チャートである。ス
テップ５５０においてオブジェクトは、各基本立体が一
組の頂点によって定義されている、複数の共面上の基本
立体にモザイク状に分けられる。オブジェクトは、共面
上であるならば、図４に示されるようにひとつの基本立
体でありうる。ステップ５６０において、基本立体はオ
ブジェクトから選ばれる。ステップ５７０において、基
本立体が全体的にあるいは部分的にピック・ボリューム
内に位置するかどうかが決定される。このステップは、
図６、図７の中でより詳細に記述される。基本立体が、
ピック・ボリューム内に位置しないならば、ステップ５
８０でそれがオブジェクトの最後の基本立体であるかど
うか判断される。最後でなければ、処理は次の基本立体
を選択するためにステップ５６０に戻る。そうでなけれ
ば、オブジェクトの基本立体のどれもピック・ボリュー
ム内でないので、オブジェクトが拒絶される。オブジェ
クトの基本立体の１つがステップ５７０でピック・ボリ
ュームと交差するならば、オブジェクトはステップ５９
５で受け入れられる。

【００１９】図６、図７は、一組の頂点により定義され
た共面上の基本立体またはオブジェクトが全体的あるい
は部分的にピッキング・ボリューム内にあるかどうか決
めるための発明の好ましい実施例の方法を示すフロー・
チャートである。最初のステップ６００において、Cohe
n-Sutherland技術に従って基本立体の各頂点のために６
ビット・コードが計算される。すなわち、基本立体の各
頂点は、ピッキング・ボリューム側またはピッキング・
ボリュームの境界面の各々の無限の側のいずれかにある
ように、分類される。ビット・コードの各ビットは０ま
たは１で、頂点が特定の面の内側あるいは外側に存在す
ることを示す。頂点がすべての６つの境界面のピッキン
グ・ボリューム側にあるならば、それはピッキング・ボ
リューム内にあって、そしてビットコード００００００
を持つ。

【００２０】図８は、２７個の区域の各々のためのビッ
トコードを図示する。ビット１は、Ｙ方向のピッキング
・ボリュームの上のポイントを示し、ビット２は、Ｙ方
向のピッキング・ボリュームの下のポイントを示し、ビ
ット３は、Ｘ方向のピッキング・ボリュームの右のポイ
ントを示し、ビット４は、Ｘ方向のピッキング・ボリュ
ームの左のポイントを示し、ビット５は、Ｚ方向のピッ
キング・ボリュームの後のポイントを示し、ビット６
は、Ｚ方向のピッキング・ボリュームの前のポイントを
示す。もちろん、別のビット・コード構成を利用するこ
ともできる。

【００２１】図６のステップ６１０で、基本立体ビット
・コードのいずれかが００００００と等しければ、頂点
は、ピッキング・ボリューム内にある。少くとも基本立
体のある部分は、ピッキング・ボリューム内にある。し
たがって、基本立体は受け入れられ、ステップ８００で
ヒットとして処理される。さもなければ、処理はステッ
プ６２０に続く。ステップ６２０で、頂点ビット・コー
ドのすべての論理積（AND）が計算される。ステップ６
３０の中で、論理積が１つの１（例えば００１０００）
を持つならば、基本立体全体はピッキング・ボリューム
の外側にあり、基本立体は拒絶され、ステップ８１０で
そのように処理される。すなわち、基本立体のすべての
頂点が同じ外区域にあるならば、基本立体はピッキング
・ボリュームを交差することができない。それゆえに、
その基本立体はヒットでない。

【００２２】基本立体が受け入れられるかまたは拒絶さ
れると、その基本立体がピッキング・ボリューム内にあ
るかどうか判断する後続の処理は必要とされない。普通
の適用業務では、ほとんどの基本立体はこうなる。頂点
のどれもピッキング・ボリューム内にないが、基本立体
の一部がピッキング・ボリューム内にあるかもしれない
場合、この後続の処理の間に、特定の問題が起こる。頂
点がピッキング・ボリューム内にあるかどうかチェック
するだけでは、このケースは発見されない。しかし、後
続の処理を必要とする少数の基本立体のために、その処
理は計算的に集中的になりうるが、ここで記述される本
発明を利用して能率的に処理することができる。

【００２３】上述の処理の中で基本立体が拒絶されもせ
ず受け入れられもしないならば、基本立体のより進んだ
処理が必要である。基本立体がピッキング・ボリューム
の範囲内で存在するならば、基本立体のエッジの１つ
が、ピッキング・ボリュームを横切らなければならない
か、またはピッキング・ボリュームの境界エッジが基本
立体を横切らなければならない。好ましい実施例の中
で、したがって、処理は一度に１つの頂点ではなく一度
に１つのエッジについて続けられる。

【００２４】基本立体のエッジがピッキング・ボリュー
ムを交差する かどうか検出するためには、最初にその
ような交差の可能性があるかどうか判断することが効率
的である。たとえば、エッジの両方の頂点がピック・ボ
リュームの外側にあるので、２つの隣接する頂点（基本
立体のエッジを定義する）のビットコードが少なくとも
２つの面において異なる場合のみ交差が起こりうる。そ
れに加えて、エッジの２つの頂点のビットコードを調べ
るだけで、基本立体がピッキング・ボリュームを横切る
ことを受諾あるいは拒絶することができる場合もある。
ステップ６４０で、各基本立体のエッジに対する２個の
頂点ビット・コードは、一緒に論理的排他和を取られる
（XOR'd）。ステップ６５０で、ビット・コードは、論
理積が００００００になるかどうかチェックされ、排他
的論理和（XOR'd）ビット・コードが１１００００、０
０１１００または００００１１であるかどうかチェック
される。両方が真であるならば、エッジはピッキング・
ボリュームを横切り、基本立体はピッキング・ボリュー
ム内にあるとして受け入れられる。ステップ６６０で、
基本立体に対する排他的論理和（XOR'd）ビット・コー
ドが１つの１の集まりより１少ないもの（one one less
ones）を含むならば（そして上に決定されるように頂
点がピッキング・ボリューム内に存在しないとする
と）、ピッキング・ボリューム内に存在しないとして基
本立体が拒絶される。ステップ６６０は、効率ののため
にステップ６３０と組み合わせられるであろう。ここで
は説明しやすいように、これらのステップは別々に示さ
れる。

【００２５】上記に記述された、容認と拒否のテスト、
そしてエッジ交差テストが、効率のために実施例の中で
使われる。しかし、上述のテストが実行されなかったと
しても、下に記述されるプロセスが使われうる。

【００２６】ピッキング・ボリュームを横切る基本立体
の最終的な決定はいっそう難しいが、上に記述されたプ
ロセスと違って決定的である。基本的には、境界エッジ
のいずれかが基本立体を交差するかどうかが判断され
る。基本立体と交差する境界エッジに必要な条件は、そ
の２つ境界エッジの頂点が、基本立体を含んでいる面の
それぞれ反対側になければならないということである。
境界エッジ頂点が面のどちら側にあるか決定するため、
そして境界エッジが基本立体を交差するかどうかチェッ
クするために、基本立体の面から広がっている面がピッ
キング・ボリュームと交差するかどうかが判断される。
ステップ７００の中で、ax + by + cz + d= ０という基
本立体面方程式が、基本立体から選ばれた３個の非共面
頂点から決定される。しばしば、基本立体のためのノー
マル、すなわち上記の公式からのa、b、cは、グラフィ
ックス・アプリケーションによって計算済みでありすぐ
に使うことができる。これらのケースにおいて、d は基
本立体の頂点の座標によって決定される。

【００２７】ステップ７１０で、P(x,y,z) = ax + by +
cz + dであるP(x,y,z)の符号が８つの境界頂点の各々
で評価される。ステップ７２０で、１２個の境界エッジ
のいずれの２つの頂点のどちらも違わないならば、基本
立体はピッキング・ボリュームを横切らず、基本立体は
拒絶される。境界エッジに対する頂点のいずれかの符号
が異なるならば、処理はステップ７３０に続く。

【００２８】ステップ７３０で、基本立体が凸面なら
ば、ステップ７３５の中で基本立体は、基本立体とピッ
キング・ボリュームの交差の計算を試みることによっ
て、それがピッキング・ボリュームと交差するかどうか
テストされる。これは、オプションのテストであって、
利用されないかもしれない。基本立体が凸面でない、ま
たはテストが要求されないならば、処理はステップ７４
０に続く。

【００２９】ステップ７４０で、境界エッジの２つの頂
点が基本立体の反対側にあり、そして境界エッジ上のポ
イントが境界エッジに直角である面上の基本立体の投影
内に含まれるならば、基本立体はピッキング・ボリュー
ムを横切り、受け入れられる。 そうでなければ基本立
体は拒絶される。投影テストと呼ばれるこのテスト
は、、共面上の基本立体が凹形であるか凸面であるか穴
が有るか無いかに関係なく、ステップ７００ー７２０に
記述されるように基本立体の面がピッキング・ボリュー
ムを交差することが既に決定されたかぎり、真である。
結果として、これは非常に強力なテストであり、複雑な
共面上の基本立体を扱っているとき、とくに役に立つ。
すなわち、そのような複雑な共面上の基本立体は、それ
らがピッキング・ボリュームと交差するかどうかを決め
るために、複数の単純な基本立体に分解される必要がな
い。それに加えて、基本立体およびピッキング・ボリュ
ームの間の交差の実際のポイントは計算されておらず、
ピッキングに効率的アプローチを提供する。

【００３０】図９は、図４の中で図示された穴をもつ凹
形基本立体の、基本立体を横切っているピッキング・ボ
リュームの境界エッジが、どのように発見されるかの例
を図示する。図９は、境界エッジE1（この例では左上の
エッジ）に垂直である面Pproj（この例ではx-y面）への
基本立体の投影を示す。境界エッジは、Pprojの中でポ
イントに０を投影する。この境界エッジは、左の境界面
P1、および上の境界面P2の交差点である。エッジE1およ
びE3は、Pprojの中で境界面の投影である。エッジE2お
よびE4は、Pprojの中で境界面の投影である。エッジEl-
E4は、投影の中で４区域R1-R4を生成する。これらの区
域の各々が、E1-E4からの２つのエッジによって境界づ
けられる。０がエッジの上にあるか下にあるか決定でき
るように、基本立体の投影されたエッジが位置づけられ
なければならない。別の実施例では、エッジ方程式に関
して０を計算し評価して、いくつのエッジが０より上に
あるか決めることによって、交差の計算を避けることが
できる。

【００３１】図９で、Ｏは、基本立体の輪郭に奇数回囲
まれるならば、Pprojの基本立体投影内に含まれる。０
が偶数回囲まれるならば、それは基本立体の外側に存在
する。エッジEl-E4のいずれかが輪郭のエッジによって
奇数回横切られるならば、基本立体の輪郭は０を囲む。
エッジEl-E4のいずれかが偶数回横切られるならば、輪
郭は０を囲まない。条件は、前もって計算された６ディ
ジットのビット・コードの使用によって検査される。基
本立体の２個の連続頂点が同じ区域の中でまたは隣接の
区域の中にあるとき、交差の計算は必要でない。頂点V1
およびV2は、このケースの例である。連続する頂点が隣
接しない区域にあるとき、交差の計算は必要である。頂
点V3およびV4は、このケースの例である。エッジV3-V4
およびV5-V6は、交差計算が必要な理由を示す。０がPpr
oj面上の基本立体の投影内に含まれないので、エッジBE
1は、基本立体を横切らない。

【００３２】上に記述された方法を使用して、穴の有る
あるいは無い、凸面および凹形多角形が、本発明によっ
て扱われることができる。

【００３３】表１ー６は、本発明を使用してオブジェク
トがピッキング・ボリュームを交差するかどうか決定す
るための疑似コードを示す。表１は、各基本立体が複数
の頂点を持つ基本立体または複数のコード面に、オブジ
ェクトがモザイク状に分かれるより高いレベルの処理に
向けられたものである。各基本立体は、基本立体のいず
れかがピック・ボリュームに含まれているかどうか決定
するために順次テストされる。基本立体のいずれかがピ
ック・ボリューム内にあるならば、オブジェクトはピッ
ク・ボリューム内にあると決定される。一方、基本立体
のどれもピック・ボリュームを横切らなければ、オブジ
ェクト自体ピック・ボリュームを横切らない。

【００３４】

【表１】 オブジェクト処理に対する疑似コード: object test: 各基本立体がＮ＋１の頂点長さの頂点リスト（vertex list）を有する Ｍの共面基本立体にオブジェクトをモザイク化する、最初の頂点 は最後のエッジを扱うための最後の頂点の後に２度目のリスト； for（オブジェクトの各基本立体）Ｉ＝１ないしＭ： set HIT = NO and MISS = NO; Ｉ番目の基本立体で基本立体 テストを行う； if HIT = YES then go to ヒット宣言（declare_hit）; 次 (基本立体) I: オブジェクトのどの基本立体もヒットでないので、オブジェクトをヒ ットでない、すなわち、ピック・ボリュームと交差しないこと を宣言； プログラム終了; ヒット宣言（declare_hit）: オブジェクトをヒットとして、すなわち、ピック・ボリュームと交 差すると宣言； プログラム終了; 表２は,共面上の基本立体がピッキング・ボリューム内
にあるかどうか決定するための疑似コードである。いく
つかのテストが、共面上の基本立体がピッキング・ボリ
ュームを横切るかどうか決定するために順次実行され
る。Cohen-Sutherland点交差テストは、最初に実行され
るものであり、表３を参照して以下に詳細に説明する。

【００３５】基本立体が受け入れられるかまたは拒絶さ
れるならば、処理は上述のオブジェクト・テストに戻
る。２番目のテストで、基本立体のエッジのいずれかが
ピッキング・ボリュームを横切るかどうか決定される。
これは、表４の参照により以下に詳細に記述される。簡
単な点交差テストおよびエッジ交差テストは、ひとつの
ループに結合することができる。ここでは説明の便宜
上、それらは別々の手続として示される。ヒットまたは
ミスがあるならば、処理はオブジェクト・テストに戻
る。３番目のテストで、基本立体の面の投影が境界エッ
ジのいずれかと交差するかどうかが判定される。これ
は、表５を参照して以下に詳細に記述される。

【００３６】このテストから、基本立体がピッキング・
ボリュームを横切らないと決定されるならば、処理はオ
ブジェクト・テストに戻る。４番目のテストで、多角形
が凸面ならば、多角形がピッキング・ボリュームを横切
るかどうか決定するために、ピッキング・ボリュームと
多角形の実際の交差が計算される。この手続きは、効率
のために、エッジ交差検査およ簡単な点交差検査と組み
合わせることができる。処理は、オブジェクト・テスト
に戻る。基本立体エッジが少くとも２つの面と交差し、
基本立体の面がピッキング・ボリュームを横切るなら
ば、基本立体は、ピッキング・ボリュームと交差するで
あろう。５番目のテストで、多角形が凸面でない、また
は凸面のテストが要求されないならば、投影テストは、
表６の参照により以下に詳細に記述されるテストが終結
すると、処理はオブジェクト・テストに戻る。

【００３７】

【表２】 基本立体処理に対する疑似コード: 基本立体 テスト: 簡単な点交差テストを実行; if HIT = YES or MISS = YES オブジェクト テストに戻る; エッジ 交差 テストを実行； if HIT = YES or MISS = YES オブジェクト テストに戻る； 境界 エッジ テストを実行； if MISS = YES オブジェクト テストに戻る； 多角形が凸面であると知られているならば ピッキング・ボリュームとの交差を計算 交差ならば set HIT = YES else set MISS = YES; オブジェクト テストに戻る； 投影 テストを実行； オブジェクト テストに戻る; 表３は、Cohen-Sutherlandのtrivial容認拒絶テストを
実行するための疑似コードを含む。これは、従来の技で
かなりよく知られた簡単な受け入れ拒絶テストの変形で
ある。このテストは、オプションであるが、エッジ 交
差 テストを実行するならば、必要とされるであろう。

【００３８】

【表３】 Cohen-Sutherland テストに対する疑似コード: 簡単な 点 交差 テスト: set AND_CODE = 111111; for (基本立体のそれぞれの頂点について) J = 1 to N + 1: set V_CODE(J) = 頂点についての６ビットのコード; if V_CODE(J) = 000000 set HIT = YES 基本立体 テストに戻る; set AND_CODE = AND_CODE AND V_CODE(J); next (頂点) J; If AND_CODE が１つの１を持つなら set MISS = YES; 基本立体 テストに戻る； 表４は、基本立体のエッジが少くとも２個の面を横切る
かどうか決定するための疑似コードを含む。加えて、以
下に示されるようにエッジが２個の面の特定のセットを
横切るならば、基本立体はピッキング・ボリュームを横
切るとみなされる。このテストはオプションであるが、
基本立体が凸面であり、凸面の多角形に対する検査が実
行されることになっているならば、実行するのが好まし
い。

【００３９】

【表４】 エッジ交差テストのために疑似コード: set MISS = YES; for (基本立体のそれぞれのエッジについて) J = 1 to N: set XOR_CODE = V_CODE(J) XOR V_CODE(J+l); if (V_CODE(J) AND V_CODE(J+l) =000000) and (XOR_CODE = (000011 or 110000 or 001100)) set HIT = YES and MISS = NO 基本立体 テストに戻る； XOR_CODE が２以上の１を持つなら set MISS = NO; next (エッジ) J; 基本立体 テストに戻る; 表５は、境界エッジのいずれかが基本立体の面によって
横切られるかどうか決定するための疑似コードを含む。
基本立体の面方程式を計算することによって、これが決
定される。しかし、この面式計算は単純なので、面に対
する法線はグラフィックス適用業務または以前の処理に
よってすでに提供されているかもしれない。面がいった
ん計算されると、もし境界エッジのいずれかが、面式が
適用されたときと異なった符号の頂点を持っていれば、
その境界エッジは基本立体によって横切られ、そして後
の処理が必要とされる。このテストは、Cohen-Sutherla
ndまたはエッジ交差テストを必要としない。

【００４０】

【表５】 境界 エッジ テストのための疑似コード: 基本立体の面方程式を計算; P(x,y,z) = ax + by + cz + d 各ピック・ボリュームについて P(x,y,z) を計算 すべての頂点の符号が等しいなら then set MISS = YES プイリミティブ テストに戻る; set E(K) =K 反対の符号の頂点のＫのエッジ; 基本立体 テストに戻る; 表６は潜在的に交差する境界エッジが、エッジの法線へ
の基本立体面の投影内に頂点を持つかどうか決定するた
めの疑似コードである。そうであれば基本立体は、ピッ
キング・ボリュームと交差する。このテストは、境界
エッジ テストの実行の後に実行されるのが好ましい。
しかし、このテストは、Cohen-Sutherlandテストまたは
エッジ 交差 テストが実行されるのを、必要としな
い。

【００４１】

【表６】 投影テストのために疑似コード: for (それぞれの境界エッジ E) J = I to K E(J) のいずれかの境界エッジ頂点がエッジ E(J) がこれに垂直な 基本立体面 P(x,y,z) の投影内あるならば、HIT = YES にセッ トし、基本立体 テストに戻る; next (境界エッジ E) J 結論として、本発明は、クリップ・テクニックによって
利用される大規模な数量の計算を必要としない。これ
は、必要な制御論理を単純化して、それによっりハード
ウェア・コストおよび実行時間を減少させる。

【００４２】本発明が、特定の実施例を参照して説明し
たが、他の実施例も、当技術に通じる者には明らかであ
る。たとえば、上記の手続きは、２次元または４次元以
上のピッキング・ボリュームに適用されるであろう。し
たがって、以上の記述は、請求項によって定義される本
発明の範囲を制限すると考えてはならない。

【００４３】

【発明の効果】以上説明したように、本発明によれば共
面オブジェクトとピッキング・ボリュームとの交差を決
定する簡略化された手段が提供される。

【図面の簡単な説明】

【図１】本発明による典型的ディジタルコンピュータの
ブロック図である。

【図２】グラフィックス機能を実行するためにホスト・
コンピューターおよびグラフィックス・アダプタによっ
て典型的に利用されるコードの層を図示しているブロッ
ク図である。

【図３】表面、エッジおよび頂点によって連結される好
まれたピッキング・ボリュームのイラストである。

【図４】ピッキング・ボリュームを横切っている穴をも
つ凹形基本立体のイラストである。

【図５】オブジェクトがピッキング・ボリューム内にあ
るかまたは部分的にピッキング・ボリューム内にあるか
決めるための好まれた方法を図示しているフロー・チャ
ートである。

【図６】共面上の基本立体またはオブジェクトがピッキ
ング・ボリューム内にあるかまたは部分的にピッキ ン
グ・ボリューム内にあるか、決めるための好まれた方法
を図示しているフロー・チャートである。

【図７】共面上の基本立体またはオブジェクトがピッキ
ング・ボリューム内にあるかまたは部分的にピッキ ン
グ・ボリューム内にあるか、決めるための好まれた方法
を図示しているフロー・チャートである。

【図８】ピッキング・ボリュームの２７個の区域の各々
のためのビットコードを図示する。

【図９】境界となっているエ ッジの１つへの垂直面で
の図４のオブジェクトの投影である。

【符号の説明】

５５０ オブジェクトをモザイク状にするステップ ５６０ 基本立体を選ぶステップ ５７０ ピック・ボリューム内に基本立体があるか判
断するステップ ５９０ オブジェクト拒絶ステップ ５９５ オブジェクト受け入れステップ

Claims (7)

【特許請求の範囲】
1. 【請求項１】 共面オブジェクトをディスプレイ上に表
   示するステップと、 上記表示されたオブジェクトを含む面がピッキング・ボ
   リュームのいずれかのエッジと交差するかどうかを計算
   する第１の計算ステップと、 上記オブジェクトの面が上記ピッキング・ボリュームの
   いずれかのエッジと交差すると判断されるとき、上記表
   示されたオブジェクトと上記ピッキング・ボリュームと
   が交差するかどうかを計算する第２の計算ステップと、 上記表示されたオブジェクトが上記ピッキング・ボリュ
   ームと交差するかどうかの指摘をするステップとを含
   む、データ処理処理方法。
2. 【請求項２】 上記第２の計算ステップは、交差するエ
   ッジの点が上記オブジェクトの投影と交差するかどうか
   の計算を含む請求項１に記載の方法。
3. 【請求項３】 上記第２の計算ステップが、交差される
   エッジの頂点が該エッジに垂直な投影と交差するかどう
   かの計算を含む請求項２に記載の方法。
4. 【請求項４】 上記第１の計算ステップが、上記オブジ
   ェクトの面方程式を得ることを含む請求項３に記載の方
   法。
5. 【請求項５】 共面オブジェクトがピッキング・ボリュ
   ームと交差するかどうかを処理する装置であって、 上記オブジェクトを含む面が上記ピッキング・ボリュー
   ムのいずれかのエッジと交差するかどうかを判断する第
   １手段と、 上記オブジェクトの面が上記ピッキング・ボリュームの
   エッジを交差すると判断されるとき該オブジェクト及び
   該ピッキング・ボリュームが交差するかどうかを判断す
   るための第２手段と、 を備えるデータ処理装置。
6. 【請求項６】 上記第２手段が、交差するエッジの点が
   オブジェクトの投影と交差するかどうかを計算する手段
   を含んでいる請求項５に記載の装置。
7. 【請求項７】 オブジェクトを記憶するためのメモリ
   と、 上記記憶されたオブジェクトを表示するためのディスプ
   レイと、 上記表示されたオブジェクトを処理するためのＯプロセ
   サとを備え、上記プロセサは、 上記表示されたオブジェクトを含む面がピッキング・ボ
   リュームのエッジと交差するかどうかを判断するための
   第１手段と、 上記記憶されたオブジェクトの面がピッキング・ボリュ
   ームのエッジと交差すると判断されるとき、上記表示さ
   れたオブジェクトおよび上記ピッキング・ボリュームが
   交差するかどうかを判断するための第２手段とを有す
   る、データ処理装置。