JPH03168884A - ジオメトリツク・オブジエクトのインタラクシヨン判定処理方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ．産業上の利用分野 本発明は、一般にはジオメトリック・オブジェクトのモ
デリングと表示の方法に関し、特にジオメ　　ト　　リ
　　ッ　　ク　　●　　オ　ブ　ジ　　ェ　　ク　　ト
　の　外　接　ボ　ッ　　ク　　ス（ｂｏｕｎｄｌｎｇ
　ｂｏｘ）のオーバラップを効半的に判定するために外
接ボックスを前処理する方法に関する。

この方法は、たとえば隠線消去やレイ●トレーシングの
手法に採用できる。・またこの方法では、特定のボック
スに接するかまたはオーバラフプするボックスをすべて
高速に識別できるように、ソーティング対象として一組
の多次元ボックスを任意に選択することができる。この
方法には、外接ボックスのオーバラップを゜ｒ＋＋定す
るときに、高速、高効率でサーチしやすいバイナリ・ツ
リー・データ●ストラクチャを構成するステップが含ま
れる。

Ｂ．従来の技術 隠線消去、マージなどの代表的なジオメトリック　●　
アルゴリズムでは、　エッジ、　面、　ソ　リ　ッ　ド
なとのジオメトリック・オブジェクトのインターセクシ
ョンを求める必要がある。しかしこのようなインターセ
クシａンの判定処理にはかなりのコストがかかる。そこ
で対象のオブジェクトを包含するために、モデラにより
、２次元（２−ｄ）または３次元（３−ｄ）の外接ボッ
クスを生成することが多い。外接ボックスは、オーバラ
ップの有無についてテストされる。しかしモデルが大き
くなると、これら外接ボックスの比較がアルゴリズムの
大半を占め、アルゴリズムの実行に非常に時間がかかる
。

このような背景から、外接ボックスのオーバラップを効
率的にｉｌ＋定できるように、よってジオメトリソク●
オブジェクトのインターセクン日ソを判定するアルゴリ
ズムの効率が大幅に向上するように、外接ボックスを前
処理する効率のよい方法が求められている。

たとえば、エッジが約５００ないし５０．０００の小規
模ないし中規模のサイズの一組のオブジェクトが、ＧＤ
Ｐ（ジオメトリック●デザイン●プロセッサ）と呼ばれ
る３Ｄソリッド●モデリング●プログラムによってモデ
ル化されたことがある。ＧＤＰについては、ジャーナル
記事“Ｓｏｌｉｄｍｏｄｅｌｉｎｇ　ｆｏｒ　ｐｒｏｄ
ｕｃｔｉｏｎ　ｄｅｓｌｇｎ″　　Ｒ．Ｎ．ｆｏｌｆｅ
　ｅｔ　ａｔ．、ＩＢＭ　Ｊ．　Ｒｅｓ．　Ｄｅｖｅｌ
ｏｐ．、Ｖｏｌ．３　１Ｎｏ．３　　５／８７、ｐｐ．
２７７−２９５、およびジャーナル記事“Ａ　Ｇｅｏｍ
ｅｔｒｌｃ　Ｍｏｄｅｌｌｎｇ　Ｓｙｓｔｅｍｆｏｒ　
　Ａｕｔｏｍａｔｅｄ　　Ｍｅｃｈａｎｌｃａｌ　　Ａ
ｓｓｅｍｂｌｙ”　　　　Ｍ．Ａ．Ｗｅｓｌｅｙ　　ｅ
ｔ　　ａｔ．、　ＩＢＭ　　Ｊ．Ｒｅｓ．　　Ｄｅｖｅ
ｌｏｐ．、　Ｖｏｌ．　　２４　　Ｎｏ．１、１　／　
８　０％ｐｐ．ｅ　４　−　７　４、に説明されてＬｘ
る。第ＩＡ図は、コンピュータ●シャシーの一部をモデ
ル化するためにＧＤＰを採用したときの出力を示す。図
の出力は隠線モードでの表現である。表現されたオブジ
ェクトは、多数のオブジェクト●エッジを含む。第ＩＢ
図は、第ＩＡ図にＡ，　　Ｂと示したエッジの図である
。水平●垂直のスクリーン座標を用いると、エッジＡは
外接ボックスＡ′を持つが、この外接ボックスの幅は０
である。Ｂに件う外接ボックスは、外接ボックスＡ゜と
エッジ八の両方と交わる。隠線ｌｒｌ去アルゴリズムは
、このような情報を用いて、Ｂの一部がエッジＡに伴う
表面または面の下に隠れているかどうかを判定する。

モデル内のエッジの各ペアのオーバラップをテストする
ための隠線消去アルゴリズムでは、実行回数はＯ（ｎ’
）になることが分かる（ｎはエブジ数）。これに代えて
、ソートされていない外接ボックスを用いて、エッジと
エツノの比較にかかる時間を少なくしようとすれば、隠
線消去アルゴリズムの効率が定数因子分向上するが、漸
近的計算ｆｆｉ　（ａｓｙｍｐｔｏｔｌｃ　ｃｏｍｐｌ
ｅｘｉｔｙ）は変わらない。ある改良された方法では、
第１図のモデルの各部、各面に、２−ｄおよび３−ｄの
外接ボックスが生成され、エッジには２−ｄの外接ボッ
クスが用いられた。その結果、ボックスの階層が５レベ
ルとなり、計算量はＯ（ｎ”’　　）に減少した。しか
しそれでも、モデルのサイズが大きくなると、隠線アル
ゴリズムでは、許容できないほど実行時間がかかること
がある。

文献には、２−ｄまたは３−ｄのボックスのインターセ
クシｌンを求めるアルゴリズムがいくつか見られる。た
とえば“ＣｏｍｐｕｔａｔｉｏｎａｌＧａｏｉ＋ｅｔｒ
Ｆ：　Ａｎ　ＩｎｔｒｏｄｕｃｔＩｏｎ″ｂｙ　Ｆ，Ｐ
．Ｐｒｅｐａｒａｔａａｎｄ　Ｍ．ｌ．　Ｓｈａｍｏｓ
，　Ｓｐｒｌｎｇｅｒ　ｖｅｒｌａｇ　　（　１　９　
８　５　）で説明されているアルゴリズムがある。しか
しこのようなアルゴリズムを適用したものにはいくつか
欠点のあることが認められている。

米国特許第４５９４８７３号明細書は、リンクされたデ
ータ●リストをソートする隠面プロセッサについて説明
している。ここでデータは、ある大きさのスキャン●ラ
イン●セグメント開始座標に従ってリストに押入される
という。その結果、ソートされたリストの配置は、１個
の変数の値を基にしたものになる。このほか、１個のパ
ラメータを基にしたソーティング方法も知られている。

ただしこのような方法は、ボックスのすべての次元のイ
ンタラクシげンによってオーダが決定されるｋ次元（　
ｋ　＝　ｄ　）ボックスのソーティングを実現するもの
ではない。したがって２−ｄボックスの場合、ボックス
のオーバラップは、ボックス上のレファレンス●ポイン
トによってのみ、たとえばボックスのコーナの位虞によ
ってのみ決定されるのが通常である。つまり従来の技術
には、あるレファレンス●ポイントによってオーダが決
定されるだけではなく、ボックスの幅と高さの関係など
、他の属性によっても決定されるような、ｋ−ｄボック
スのンーティング方法が欠けているのである。

Ｊ，Ｌ．　　Ｂｅｎｔｌｅｙは、ジャーナル記車“Ｍｕ
ｌｔｌｄｌｍｅｎｓｌｏｎａｌ　ｂｉｎａｒｙ　ｓｉａ
ｒｃｈ　ｔｒｅｅｓ　ｕｓｅｄｆｏｒ　ａｓｓｏｃｌａ
ｔｌｙｅ　ｓｅａｒｃｈｌｎｇ″　Ｃｏｓｍｕｎｌｃａ
ｔｌｏｎｓｏｆ　ｔｈｅ　ＡＣＭ，　Ｖｏｌ．１　８　
（１　９７５）　、ｐｐ．　　５０９−５１７、の中で
、多次元バイナリ●サーチ●ツリ−（ｋ−ｄツリー）を
、連想サーチによって検索された情報を格納するデータ
構造として展開している。Ｈｅｎ　ｔ　ｌ　ｅｙが考案
したｋ−ｄツリー構造の適用例は、ターミナル指向情報
サーチ●システムと音声認識に関するものである。

Ｃ．発明が解決しようとする課題 本発明の目的は、質問（ｑｕｅｒｙ）に対する応答効率
を高めるために、ジオメトリ，ク●オブジェクトを空間
的にソートする方法を提供するすることにある。

本発明の目的には、多次元ツリー●データ構造を構成す
るジオメトリック・オブジェクトの処理方法を提供する
ことも含まれる， 本発明の目的には、高速かつ高効率でサーチしやすい多
次元ツリー●データ構造を構成するジオメトリック・オ
ブジェクトの表示に用いる方法を提供するすることも含
まれる。

本発明の目的には、表示対象のジオメトリック・オブジ
ェクトから多次元ツリー●データ構造を構成し、隠線消
去アルゴリズムの計算量を抑える方法を提供することも
含まれる。

Ｄ．課題を解決するための手段 上述の問題を解決し、本発明の目的を達成するのは、ジ
オメトリック・オブジェクトの外接ボックスに関連した
バイナリ・ツリー・データ構造を構成する方法である。

ｋ次元の外接ボックスは、最小境界（ｂｏｕｎｄ）と最
大境界のペアをｋ個持ち、境界ペアは次元（ｄｌｍｅｎ
ｓｌｏｎ）にっきｌ組である。

外接ボックスの第１境界のすべての値についてメジアン
が求められる。次に、対応する境界がこのメジアンより
も小さい外漬ボックスは、それぞれ第１サブツリーに肚
かれ、対応する境界がこのメジアンより大きい外接ボッ
クスは、それぞれ第２サブツリーに置かれる。ルート・
ノードには；　第１サブツリーのすべての外接ボックス
のその次元の最大値と、第２サブツリーのすべての外接
ボックスのその次元の最小値が置かれる。第１サブツリ
ーと第２サブツリーとに割り当てられたボックスは、そ
の次元の第２境界を用いて同じように処理される。この
プロセスは、結果のサブツリーでも同じように、残りの
次元の境界について継続され、ツリーのリーフがソート
済み外接ボックスであるパイナリ●ツリ一〇データ構造
が生成されるまで繰り返される。

本発明は、質問に応答してバイナリ●ツリ一〇データ構
造をサーチすることにも関係する。たとえば質問ボック
スＱへの応答として、Ｑとオーバラツプし得るすべての
ボックスのサーチは、Ｑの第１次元の境界を、ルートに
格納された第１サブツリーの最大値および第２サブツリ
ーの最小値と比較することからスタートする。比較によ
って、第１サブツリー　第２サブツリー　またはその両
方に対してさらにサーチが必要かどうかが判定される。

いずれのサブツリーも、同じ第１次元に対して分割され
ているので、これらのサーチは、ツリーのルートで行わ
れたサーチと同一の方法で継続する。サーチは、同じ方
法で次のツリーの２つのレベルにある次の次元に進み、
後続のレベルにあるすべての次元を通過し、必要に応じ
て第１次元から再開され、ツリーのリーフに達するまで
繰り返される。

本発明は、ジオメトリック・オブジェクトのインターセ
クシ８冫の判定に適用できる。たとえば、点、エッジ、
面、その他の、外接ボックスを伴いゃすいブロバティの
インターセクンａンの′ｒリ定などがある。本発明は、
ＶＬＳＩデバイスのモデリングによって、異なるデバイ
ス領域間の電気特性を判定するときにも採用できる。本
発明はまた、たとえばエッジを面と比較して、オーバラ
ップが存在するかどうかを判定するときにも採用できる
。

さらにまた、オブジェクトが、様々な許容差をｔ−Ｙつ
構造に形成されたとき、オブジェクトがオーバラツプす
るかどうかを判定するためにも、また、たとえばオブジ
ェクトの投影像がどのようなときにオーバラツプするか
、そしてオブジェクト自体と必ずしもオーバラツプしな
いのはどのようなときかを判定するためにも採用できる
。

Ｅ．実施例 第２図は、本発明の実施に適したデータ処理シ　・ステ
ムｉである。システム１は、リード／ライト●メモリ３
に両方向接続された中央処理装置（　Ｃ　ＰＵ）２を含
む。メモリ３は、本発明を実施するための命令を含めて
、ＣＰＵ２によって実行される命令を格納するストレー
ジ●ロケーシーンを含むほか、ＣＰＵ２によって生成さ
れたデータ構造および他のデータを格納するストレージ
●ロケーシ貨ンを含む。メモリ３はまた、ディスプレイ
４に接続されたストレージ●ロケーシ碕冫も備える。

ディスプレイ４は、メモリ３の関連するストレージ●ロ
ケーシ譚ンに格納されたジオメトリック・オブジェクト
の２次元表現を表示する。システム１には、キーボード
５など、ユーザがシステムｌと対話するためのデータ●
エントリ●デバイスも含まれる。マス●ストレージ●デ
バイス（マス●ストア）６は、メモリ３に接続され、デ
ータと命令をオフラインで記憶する。代表的なマス●ス
トア８には、ウインチェスタ●ディスクなどの磁気スト
レージ媒体が含まれる。第２図に示した実施例に適した
システムの一例として、　ＩＢＭ　　５０８０グラフィ
クス●ディスプレイ●システムが接続されたＩＢＭ　　
３０９０などのメインフレーム上で動作する３−ｄソリ
ッド●モデリング●デザイン●システム（前述のＧＤＰ
など）がある。ここで注意したいが、本発明は、ある一
定のハードウェア環境やソフトウェア環境に限定される
ものではない。

ここで本発明の方法について、最初にｋ　−　ｄツリー
●データ構造とあわせて説明する。まずノリー●データ
構造の説明に最適な例として、第３図に示した比較的簡
単な一組のインクーパルを煮える。本発明の目的から、
インターバルは、所定の質問インターバルとオーバラッ
プするインターバルのサブセットを判定するのに必要な
ときに、解を効率的に決定できるように前処理される。

第３図に示すとわり、８個のライン●インターバルから
成るセットを考える（説明の便宜上、３本のライン上に
示した）。各インターバルの上にそれぞれのインターバ
ルの端点の値を示した。最終的なソート順序はローマ数
字で下に示した。第３図は、ソートされていないデータ
を本発明に与えた状態を示したものとみることができる
。第ＳＡ図に、第４図のツリーの表現に用いられるデー
タ構造を、第５Ｂ図に、本発明によってソートされたデ
ータを示す。第４図のパイナリ●ツリー●データ構造は
、インターバルから次のようにして構成される。まず、
各インターバルの左のすべての端点のメジアン（Ｘ）が
求められる。次に、Ｘの左から始まるすべてのインター
バルが、ツリー●ルート１０ａの左のサブツリー１２に
、Ｘの右から始まるすべてのインターバルが、ルート１
０ａの右のサブツリー１４に置かれる。ルート１０ａに
置かれた値（１０と５）は、それぞれ、左サブツリー１
２の値の最大値、右サブツリー１４の値の最小値を表す
。左サブツリー１２および右サブツリー１４に割り当て
られたインターバルは、次の座標すなわちインターバル
の左の端点に対する右の端点を使用して同様に処理され
る。この方法で、左の端点のメジアンの判定と右の端点
のメジアンの判定を交互に行い、繰り返し適用すること
により、図のようなバイナリ●ツリーが生成される。こ
うして得られたソート済みデータ●アレイは、第５Ｂ図
に示したツリー１０のリーフと等しくなり、第５Ａ図の
内容は、すべてのサプノリーの最小値と最大値になる。

これによって簡単なバイナリ・ツリー・データ摺造が得
られる。質問に応答してデータ構造がサーチされるとき
、この構造から得られるメリットは大きい。

本発明は、質問（Ｑ）インターバルに応答してパイナリ
●ツリー●データ構造１０をサーチすることにも関係す
る。図の例では、Ｑインターバルは左端点の値が３．５
で、右端点の値が４．５である。Ｑインターバルに応答
して、Ｑインターバルの左端点の値（３．５）を左サブ
ツリーの最大値（１０）と、Ｑインターバルの右端点の
値（４．６）を右サブツリーの最小値（５）とそれぞれ
比較することによって、Ｑインターバルにオーバラツプ
するすべてのインターバルが求められる。

先に述べたとおり、左サブツリーの最大値と右サブツリ
ーの最小値は、ルートｌＯａに前もって格納されている
。この比較により、左サブツリー１２、右サブツリー１
４、または両方のサブツリーについてさらにサーチを実
行する必要があるかどうかを指定する情報が生成される
。

図の例では、Ｑインターバルの左端点は、左サブツリー
の最大値よりも小さい（３．５＜１０）が、Ｑインター
バルの右端点は、右サブツリーの最小値よりも大きくは
ない（　４．　　５　＜　５　）。その結果、右サブツ
リー１４は否定され、サーチは、左サブツリーｌ２の７
ードに限定される。子ノード１２ａにわいては、Ｑイン
ターバルの左端点は、左サブツリーの最大値よりも小さ
い（　３．　　５　＜　４　）ことが分かり、Ｑインタ
ーバルの右端点は右サブツリーの最小値よりも大きい（
　４．　　５　＞　Ｏ　）。その結果、サーチは、子ノ
ード１２ａに示したように、左サブツリー１２ｂと右サ
ブツリー１２Ｃの両方で継続される。子ノード１２ｂで
は、Ｑイ／ターバルの左端点は左サブツリーの最大値よ
りも小さい（３．５＞２）ことが分かるが、Ｑインター
バルの右端点は右サブツリーの最小値よりも大きい（４
．５＞１）。その結果、サーチは、子ノード１２ｂに示
したように、右サブツリーにおいて継続される。子ノー
ド１２ｃでは、Ｑインターバルの左端点は左サブツリー
の最大値よりも小さい（３．５＜１０）ことが分かり、
Ｑイ／ターバルの右端点は右サブツリーの最小値よりも
大きい（　４．　　５　＞　３　）。その結果、サーチ
は、子ノード１２ｃに示したように、左右両方のサブソ
リーで継続される。ツリー１０のリーフでは残リ３回の
判定が行われ、Ｑインターバルにオーバラップするすべ
てのインターバル（ＩＩＸ　ＩＩＩ，ＩＶ）の判定が行
われる。

パイナリ●ツリー●データ構造が構成されるこの方法は
、各ノードに対する一組のインターバルの端点のメジア
ンを゛Ｉ’ｌ１定する過程を伴う。これが最も効果的に
達成されるのは、クィック●ソートに似たメジアン発見
アルゴリズムを採用した場合であり、前処理ステップの
予測時間は、代表値で０（ｎ　　ｌｏｇ　　ｎ）となる
。第６図に、本発明を用いた場合（ラインＡ）と用いな
い場合（ラインＢ）について隠線消去アルゴリズムを実
行した結果を、仮想ＣＰＵ時間（秒）と処Ｐ１！エッジ
数で示した。本発明を採用することで、処理に要する時
間が大幅に短縮されているのが分かる。

ｌ次元リニア●インターバルに関する上述の内容は、第
１次元の境界について反復する前に、連続した境界の組
またはペアを順に考慮することによって、高位の次元に
簡単に拡大できる。したがって、２次元ボックスの場合
、バイナリ・ツリー・データ構造は、最初にボックスの
左右の座標を考慮し、次に上下の座標を順に考慮するこ
とによって構成される。これは、すべてのデータがソー
トされるまで繰り返される。この方法は、所用時間や実
行計算量のどちらも増加させずに高次元に容易に一般化
できる。

たとえば、水平リニア●インターバルをンート／サーチ
する前記の例は、インターバルの左右の境界を表す２つ
の座標Ｘ１、Ｘ２で実現できる。

２−ｄ・ンオメトリック●オブンエク１・のソーティン
グは、ボックスの上下左右の境界を表す４つの座標ＸＩ
、Ｘ２、５’ｌＮ　ｙ２によって実現できる。

３−ｄジオメトリック●オブジェクｉ・のソーティング
は、ボックスの上下左右前後の境界を表す６つの座標×
１、×２、ｙ１、ｙ２、ｚ１、ｚ２によって実現できる
。これより高次元のオブジェクトでは、それに応じた数
の座標が必要になる。座標は、オブジェクトのコーナま
たは、リニア◆インターバルの場合にはオブジェクトの
端邪に対応ずる。ジオメトリック・オブジェクトやボッ
クスの数を２倍にすれば、バイナリ・ツリー・データＩ
Ｍ造のレベルが増す。たとえば５０．０００個の外接ボ
ノクスを表現するには、１６レベルのツリーが必要であ
る（Ｏ（ｌｏｇ２５０，０００）。

第４図の例を引けば、２−ｄオブジェクトの場合、ノー
ド１０ａは、外接ボックスの左サイドに、ノード１２ａ
ｓ　　ｌ４ａは右サイドに、ノーｔ’ｌ２ｂ，　　１　
２　Ｃ）　　１　４　ｂ．　　１　４　ｃは下側に関連
する。

２−ｄ外接ボックスの上側を表現するには、１レベル１
６個の子ノード（図示なし）を追加する必要がある。そ
のときバイナリ・ツリー・データ構造を構成するために
、孤立した外接ボックスによってツリーのリーフが表現
されるまで、境界がサイクルスルーされる。

すなわち、この方法は、ジオメトリック・オブジェクト
のインタラクシＦ冫をすり定するため（こ、ジオメトリ
ック・オブジェクトの外接ボックスに関連するバイナリ
・ツリー・データ構造を横或するものである。構成プロ
セスは、外接ボックスのすべての左サイドのメジアン値
など、外接ボックスの第１境界または第１次元のすべて
の値についてメジアン値Ｘを求めることによって、ルー
ト・ノードからスタートする。次に、対応する境界がＸ
より小さい外接ボックスが、ツリー●ルートの左サブツ
リーなど、第１サブツリーに置かれる。

対応する境界がＸより大きい外接ボックスは、ツリ一一
ルートの右サブツリーなど、第２サブツリーに置かれる
。これら２つのサブツリーは、ツリーの第２レベルを成
す。ルート・ノードには、第１サブツリーの外接ボック
スからの第１次元の最大境界の最大値と、第２サブツリ
ーの外接ボックスからの第１次元の最小境界の最小値が
１２Ｉかれる。第１サブツリーと第２サブツリーに害１
１り当てられたボックスは、第１次元の第２境界を川い
ることで同様に処理される。このプロセスは、得られた
サブツリーについても、他の次元の境界を用いることに
よって同様に継続される。全次元の境界を１回用いてソ
ートできる数よりも外接ボックスの数が多い場合は、得
られたサブツリーのソーティングは、第１次元の第１境
界に対して再開される。これは、ツリーのリーフがソー
ト済み外接ボックスとなるパイナリ●ツリー●デークＬ
ｉ　令が生成されるまで繰り返される。

本発明の方法は、先に挙げたＢｅｎｔｌｅｙのものとは
異なる一一ジャーナル記事“Ｍｕｌｔｌｄｌｍｅｎｓｌ
ｏｎａｌｂｌｎａｒｙ　　Ｓｅａｒｃｈ　　ｔｒｅｅｓ
　　ｕｓｅｄ　　ｆｏｒ　　ａｓｓｏｃｌａｔｌｖｅｓ
ｅａｒｃｈｌｏｇ’　　　　ＣｏｍＩＩｕｎｌｃａｔｌ
ｏｎｓ　　ｏｆ　　ｔｈｅ　　ＡＣＭ，　　Ｖｏｌ．１
８　　（１９７５）。Ｂｅｎｔｌｅｙの方法テハ、本発
明によってリーフに格納されるもの、すなわちソートさ
れたデータが、Ｂｅｎｔｌｅｙのｋ−ｄツリー構造の各
７一ドに格納される。本発明では、バイナリ・ツリーの
各７ードに、左右のサブツリーのリミットが格納される
ので、質問インターバルまたは質問ボックスに応じたツ
リーのサーチ効率が大幅に向上する。その点、Ｂｅｎｔ
ｌｅｙの方法は、本発明によるジオメトリック・オブジ
ェクトのソーティング／サーチ方法よりも効率が低いと
宮える。

本発明はまた、質問に対応したパイナリ●ツリー●デー
タ構造のサーチにも関係する。たとえば質問ボックスＱ
への応答として、Ｑとオーバラツプし得るすべてのボッ
クスのサーチが、Ｑの第１次元の最小境界を、ルートに
格納された第１サブツリーの最大値と、およびＱの第１
次元の最大境界を、第２サブツリーの最小値と比較する
ことからスタートする。Ｑの最小境界が第１サブツリー
の最大値よりも小さい場合は、第１サブツリーに対して
さらにサーチが実行される。Ｑの最大境界が第２サブツ
リーの最小値よりも大きい場合は、第２サブツリーに対
してサーチがさらに実行される。このように、これらの
テストにより、第１サブツリー　第２サブツリー　また
はその両方に対してさらにサーチが必要かどうかが判定
される。これらのサブツリーの各ノードでのサーチ●テ
ストは、ツリーのルートで行われたテストと同一である
。これらサブツリーが、第１次元の最大境界に対してソ
ートされたという事実があるにしても同一である。それ
は、これらのノードに格納された最小値と最大値が、そ
れらのソーティングに用いられた境界とは独立している
からである。

最小／最大値は、境界によって区切られる次元にのみ依
存する。サーチは、同じ方法で、ツリーの第３、第４の
レベルにある第２次元で続けられる。

それらが第２次元に対してソートされたからである。後
続するレベルにおけるサーチは、そのレベルでのソーテ
ィングを制御した次元に対して実行され、ツリーのリー
フに達するまで続けられる。

サーチによって識別された、フリーのリーフにおける外
接ボックスは、質問ボックスとオーバラツプする外接ボ
ックスである。

本発明の方法は、添付の表に示したようなアルゴリズム
で実現できる。表のアルゴリズムは、ボックスをソート
したｋ−ｄツリーを構成するＫＤＳｏｒｔモジュールと
、ボックスのこのｋ−ｄツリーをサーチするＫＤＳｅｅ
ｋモジュールの２つである。アルゴリズムは、特に、ｒ
’￥’ｌ’ｈ小数点システムと併用したときに強力なも
のとなる。このアルゴリズムは既知のサイズのアレイを
用いることで、メモリ３内のアレイ空間の事前割り当て
を可能にする。さらに所要メモリ空間全体が大きくなる
ことはなく、ボックス座標に関係するオリジナル●デー
タの格納に必要な空間の約２倍未満である。アルゴリズ
ムは、隠線消去などを行う既存のプロセッサに、プログ
ラム●ロジックを大きく変更することなく容易に組み込
める。

先にも述べたように、本発明による空間ソーティングは
、隠線消去以外のアプリケーションにも適用でき、複数
のオブジェクトのオーバラップを判定する他のアプリケ
ーシ日ンにも採用できる。

他のアブリケーシｅンとしては、ジオメトリック●マー
ジ●アルゴリズム、高品位レンダリング●アノレゴリズ
ム、インターフェアレンス●チェッカなどがある。

本発明については、その要諦と範囲から逸脱することな
く、種々の変形が可能である。一例として、上述のもの
とは逆の方法により、左サブツリーは、次のサブツリー
の最大リミットを格納するのに、右サブツリーは、低位
のリミットを格納するのに採用できる。

Ｆ．発明の効果 本発明によれば、質問に対する応答効率を高めるために
、ジオメトリック・オブジェクトを空間的にソートする
方法がＵ４供される。

【図面の簡単な説明】 第１Ａ図は、隠線モードで表示されるソリッド●モデリ
ング●プログラムの出力図である。 第ＩＢ図は、第１Ａ図の出力の一部であり、２つのエッ
ジに伴う外接ボックスを示す図である。 第２図は、本発明の実施に適したデータ処理システムの
ハードウェアを示す図である。 第３図は、あるライン」二の一組のインターバルとこれ
に伴う質問インターバルを示す図である。 第４図は、本発明に従って構成された、第３図のインタ
ーバルに対するツリー●データ構造の説明図である。 第５Ａ図は、第３図と第４図の例に対応するツリー●デ
ータＩｌ４造からの情報の説明図である。 第５Ｂ図は、第５Ａ図に対応するソート●データからの
情報の説明図である。 第６図は、 本発明を用いた場合と用いない場合 の隠線消去アルプリ ズムのパフォーマ ン スを７バす 図である。

Claims (12)

【特許請求の範囲】
1. （１）ジオメトリック・オブジェクトのインタラクショ
   ンを判定する方法であって、該ジオメトリック・オブジ
   ェクトの境界に関する情報を表すバイナリ・ツリー・デ
   ータ構造を構成することによって、該オブジェクトをソ
   ートする初期ステップを含む方法。
2. （２）請求項（１）に記載の方法であって、オブジェク
   トをソートするステップが、各ジオメトリック・オブジ
   ェクトの境界の所与のペアについて、 上記オブジェクトの各次元の最小境界値のメジアン値を
   求めるステップと、 最小境界値が上記メジアン値よりも小さいすべてのオブ
   ジェクトを、バイナリ・ツリーの第１サブツリーに割り
   当てるステップと、 最小境界値が上記メジアン値よりも大きいすべてのオブ
   ジェクトを、上記バイナリ・ツリーの第２サブツリーに
   割り当てるステップと、 上記第１サブツリーに割り当てられたすべての境界値の
   最大値を表わす値を上記バイナリ・ツリーのルート・ノ
   ードに格納するステップと、上記第２サブツリーに割り
   当てられたすべての境界値の最小値を表わす値を上記バ
   イナリ・ツリーのルート・ノードに格納するステップ、
   によって実行される方法。
3. （３）請求項（２）に記載の方法であって、メジアン値
   を求めるステップ、第１と第２の割り当てステップ、お
   よび第１と第２の格納ステップが、後続の境界について
   複数回実行され、ツリーのリーフに達するまで繰り返さ
   れる、方法。
4. （４）請求項（３）に記載の方法であって、質問に関係
   する境界にジオメトリック・オブジェクトがオーバラッ
   プするかどうかを判定するために、バイナリ・ツリー・
   データ構造をサーチするステップを含む方法。
5. （５）請求項（４）に記載の方法であって、サーチ・ス
   テップに、 質問の最小境界を、第１サブツリーの対応する最大境界
   値と比較するステップと、 質問の最大境界を、第２サブツリーの対応する最小境界
   値と比較するステップと、 上記第１および第２の比較ステップの結果として、 上記第１サブツリーのみ、上記第２サブツリーのみ、ま
   たは該第１および第２のサブツリーの両方について、サ
   ーチをさらに実行するかどうかを指定するステップ、 が含まれる方法。
6. （６）請求項（５）に記載の方法であって、第１と第２
   の比較ステップおよび指定ステップが、バイナリ・ツリ
   ーの指定されたサブツリーについて、ツリーのリーフに
   達するまで繰り返し実行される方法。
7. （７）ジオメトリック・オブジェクトの外接ボックスの
   オーバラップの判定効率を高めるために、該ボックスを
   前処理する方法であって、 各外接ボックスに伴う次元の境界値のメジアン値を求め
   ることによって、バイナリ・ツリー・データ構造を構成
   するステップと、 対応する最小境界値が上記メジアン値よりも小さいすべ
   ての外接ボックスを上記バイナリ・ツリー・データ構造
   の第１サブツリーに割り当てるステップと、 対応する最小境界値が上記メジアン値よりも大きいすべ
   ての外接ボックスを上記バイナリ・ツリー・データ構造
   の第２サブツリーに割り当てるステップと、 上記第１サブツリーに割り当てられた外接ボックスの対
   応するすべての値の最大値を表す値を上記バイナリ・ツ
   リー・データ構造のルート・ノードに格納するステップ
   と、 上記第２サブツリーに割り当てられた外接ボックスの対
   応するすべての値の最小値を表す値を上記バイナリ・ツ
   リー・データ構造のルート・ノードに格納するステップ
   とを含む、方法。
8. （８）請求項（７）に記載の方法であって、メジアン値
   を求めるステップ、第１と第２の割り当てステップ、お
   よび第１と第２の格納ステップが、バイナリ・ツリー・
   データ構造の各サブツリーの各ノードについて実行され
   る方法。
9. （９）ジオメトリック・オブジェクトのオーバラップを
   判定する方法であって、該ジオメトリック・オブジェク
   トの境界に関する情報を表し、少なくとも第１と第２の
   サブツリーを含むバイナリ・ツリー・データ構造を構成
   することによって、該オブジェクトをソートするステッ
   プと、質問に関連する境界に該ジオメトリック・オブジ
   ェクトがオーバラップするかどうかを判定するために該
   バイナリ・ツリー・データ構造をサーチするステップと
   を含み、該サーチ・ステップが、 上記質問に関連する最小境界を、第１サブツリーの対応
   する最大境界値と比較するステップと、上記質問に関連
   する最大境界を、第２サブツリーの対応する最小境界値
   と比較するステップと、上記第１および第２の比較ステ
   ップの結果として、 上記第１サブツリーのみ、上記第２サブツリーのみ、ま
   たは該第１および第２のサブツリーの両方について、サ
   ーチをさらに実行するかどうかを指定するステップとを
   含む、方法。
10. （１０）請求項（９）に記載の方法であって、第１と第
    ２の比較ステップおよび指定ステップが、バイナリ・ツ
    リーの指定されたサブツリーについて、該バイナリ・ツ
    リーのリーフに達するまで繰り返し実行される方法。
11. （１１）請求項（９）に記載の方法であって、ソーティ
    ング・ステップが、各ジオメトリック・オブジェクトの
    境界の所与のペアについて、上記オブジェクトの各次元
    の最小境界値のメジアン値を求めるステップと、 対応する最小境界値が上記メジアン値よりも小さいすべ
    てのオブジェクトを上記バイナリ・ツリーの第１サブツ
    リーに割り当てるステップと、対応する最小境界値が上
    記メジアン値よりも大きいすべてのオブジェクトを上記
    バイナリ・ツリーの第２サブツリーに割り当てるステッ
    プと、上記第１サブツリーに割り当てられたすべてのオ
    ブジェクトの最大境界値を表す値を上記バイナリ・ツリ
    ーのルート・ノードに格納するステップと、 上記第２サブツリーに割り当てられたすべてのオブジェ
    クトの最小境界値を表す値を上記バイナリ・ツリーのル
    ート・ノードに格納するステップ、によって実行される
    方法。
12. （１２）請求項（１１）に記載の方法であって、メジア
    ン値を求めるステップ、第１と第２の割り当てステップ
    、および第１と第２の格納ステップが、バイナリ・ツリ
    ーの各サブツリーの各ノードについて実行される方法。