JPS60181933A - オクト・トリ−生成方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔発明の技術分野〕 本発明は、３次元データ構造であるへ分本（オクト・ト
リー）を２次元配列より作成するに際して、カレント・
パス・リストを用いて高速に生成できるようにしたオク
ト・トリー生成方式に関する。

〔従来技術と問題点〕

第１図はオクト−トリーを説明するものである。

２次元間列Ａ　Ｃｉ’：１．　Ｃノ〕があり、この値が
高さを表わすものとする。いま、この配列よりオクト−
トリーを作るものとする。

ｋ　＝Ａ［：已〕　〔）〕 とすると、第１図（イ）に示すように、ｘ＝ｉ、ｙ＝ノ
。

ｚ　＝　ｋの関係がある。点＜ｉ、ｊ、ｋ）は第１図（
ハ）に示すようなノードの集合で表現される。第１図（
ロ）は空間上の点とノードとの関係を説明するものであ
る。先ず最初に、立方２体の空間をｘ−ｙ平面に平行な
面で２分し、次いでｙ　−ｚ平面で平行な面で２分し、
更にｚ　−ｘ平面で平行な面で２分する。

この結果、体積か１の８個の立方体の部分空間が作られ
る。これらの部分空間に０．１，２．・・・７の番号を
与え、点（ｉ、）’、ｋ）が何の部分空間に属している
かを調べる。例えば点（ｉ、ｊ、ｋ）が第０番の体積か
■の部分空間に属しておれば、ルート・ノードＲの第０
番の枝にレベル１のノードＮ（０）を作る。次にこの第
０番の体積が■の立方体を８等分し、体積がし８２の立
方体を８個作る。これらの体積が／８２の立方体にも０
，１，２．・・・７の番号を与え、点＜ｉ、ｊ、ｋ）が
何の部分空間に属しているかを調べる。例えば、点い、
ｊ、ｋ）が第０番の体積が／８２の部分空間に属してお
れば、ノードＮ（０）の第０番の枝にレベル２０ノード
Ｎ（０，０）を作成する。次に、この第０番の体積がし
８２を８等分し、体積が１／８ｓの立方体を８面作る。

これらの体積がｈ３の立方体にも０，１，２．・・・７
の番号を与え、点（ｉ、ｊ、ｋ）が何の部分空間に属し
ているかを調べる。例えば、点＜ｉ、ｊ、ｋ）が第０番
の体積がし♂の部分空間に属しており、体積を！／８３
以下に分解できないとすると、ノードＮ（０，０）の第
０番の枝にリーフ・ノードＬ（０，０，０）を作る。図
示の例では、オクト・トリー上においてリーフΦノード
しく０．０．０）に至るパスは、０．０．０　で表わさ
れる。

これをトラベル・リストという。

記憶装置上には、ルート・ノードＲ，ノードＮ（０）、
ノードＮ（０，０）及びリーフＱノードのそれぞれと１
対１の対応をなす記憶域が設けられている。ルート−ノ
ードＲの記憶域は、第０ないし第７のポインタ部を有し
ており、上述の例では第０のポインタ部にノードＮ（０
）の記憶域のアドレスが記入されており、他のポインタ
部には例えば−１が記入されている。ノードＮ（０）の
記憶域も第０ないし第７のポインタ部を有しており、上
述の例では第Ｏのポインタ部にノードＮ（０，０）の記
憶域のアドレスが記入されている。ノードＮ（０，０）
の記憶域も第Ｏないし第７のポインタを有しており、と
述の例では第０のポインタ部に９−フ◆ノードＬ（０，
０，０）の記憶域のアドレスが記入されている。

リーフ・ノードＬ（０，０，０）の記憶域には、対応す
る部分空間に点が存在することを示す情報及び色を表わ
す情報などが記入されている。

２次元間列　ｋ＝Ａ〔ｉ　］　Ｃｊ　）は曲面を表わし
ているが、Ａ　［ｉ〕Ｃノ＋１３で表わされる点につい
ても、同様にトラベル・リストが作成され、これを表わ
すだめのデータが記憶装置に書き込まれる。

従来のオクト拳トリー生成方式においては、その生成時
において、ルート・ノードより探索し、まだないノード
を生成する方式であった。この方式では、いちいち、ル
ートよりトリーの探索をしなければならず、所要時間が
莫大なものになる。

〔発明の目的〕

本発明は、上記の考察に基づくものであって、従来方式
よりも高速でオクト・トリーを作成できるようになった
オクトψトリー作成方式を提供することを目的としてい
る。

〔発明の横取〕

そしてそのため、本発明のオクト−トリー生成方式は、
オクト・トリーを記憶するメモリと、ディスプレイ装置
と、上記メモリに格納されているオクト・トリーを基に
して図形を表示するためのコマンドを作成しこれを上記
ディスプレイ装置に与える計算機とを具備する図形処理
システムにおけるオクト−トリー生成方式であって、今
回のトラベル−リストを記憶する第１のトラベル・リス
ト記憶域と、前回のトラベル・リストを記憶する第２の
トラベル・リスト記憶域と、該第２のトラベル・リスト
記憶域に保存されているトラベル・リストで特定される
ノードの記憶域のアドレスを記憶するカレント・パス記
憶域とを有し、且つ上記計算機は、点の位置を表わす２
次元配列の要素が入力される度にトラベル・リストを作
成し、これを上記第１のトラベル・リスト記憶域に格納
し、第１のトラベル拳リスト記憶域に格納されている今
回のトラベル・リストと上記第２のトラベル・リスト記
憶域に保存されている前回のトラベル・リストとをレベ
ルＯから順番に比較し、レベルＸ＋１で相違が検出され
たとき、今回のトラベル・リストにおけるレベルｚ＋１
のノードないしレベルＮ−１のノードのそれぞれに対応
する記憶域を上記メモリ上に確保し、上記カレント・パ
ス・リスト記憶域に格納されているカレント−パス−リ
ストに特定されるレベルＸのノードの記憶域及び上記レ
ベルｘ＋ｌのノードないしレベルＮ−１のノードに対応
する記憶域に必要な情報を記入するより構成されている
ことを特徴とするものである。

〔発明の実施例〕

以下、本発明を図面を参照しつつ説明する。

第２図は今回のトラベル・リスト記憶域と前回のトラベ
ル・リスト記憶域を示す図、第３図はカレント・パス・
リストを説明する図、第４図は本発明によるオクト・ト
リーの作成方法を説明するフローチャート、第５図は本
発明が適用される図形処理システムの１例を示す図であ
る。

第２図において、ＴＲＡは今回のトラベル・リストを記
憶する記憶域、ＴＲＢは前回のトラベル・リストを記憶
する記憶域をそれぞれ示している。

オクト−トリーのパスは成るレベル（１，ｅｖ）におい
て、 ＜＜ｋ　＆（１＜＜　ｌ！ｅｖ　）Ｋ＜２　）ｌ　（Ｃ
ｊ　＆　（１＜＜Ａ！ｇｖ））＜＜１　）ｌｉ＆Ｄ＜＜
ｚｓｖ）） なる論理式で表わされる。これをレベル０ないしＮ−１
のそれぞれについて作成し、これを今日のトラベル・リ
スト記憶域ＴＲＡに保存する。例えばに、）’、ｉがそ
れぞれＯないし１５の値を取υ得る状態の下において、
ｈ＝２．ｊ＝ｓ、ｉ＝１なる点のレベル０（ルート・）
−ドのレベル）のパスは１’−０１０Ｊであり、レベル
１のパスはｒｏ　ＯＯＪであす、レベル２のパスは１−
１００ｊでアリ、レベル３のパスは「００１」である。

前回のトラベル拳リスト記憶域ＴＲＢには、前回の２次
元配列の要素、例えｔｌ＝ｌｊ）［）−１〕で表わされ
るトラベル・リストが保存される。

第３図はカレント・パス・リストを説明する図である。

同図において、ＣＰＬはカレント・パス・リストを記憶
する記憶域を示している。カレント・パス・リスト記憶
域ＣＰＬは第０ないし第Ｎ−１のエントリを有している
。前回のトラベル・リスト記憶域ＴＲＢに保存されてい
るパスがＰ。。

ｈ　＋　Ｐ　ｔ　＋・・・ＰＮ−１とすると、カレント
・パス・リストの第０エントリにはノードＮ（Ｐｏ）の
記憶域のアドレスが記入され、第１エントリにはノード
Ｎ（Ｐｏ、Ｐ＋＋）の記憶域のアドレスが記入され、第
ｔエンド’ＪにはノードＮ（Ｐ、　、　Ｐ、　、・・・
Ｐｉ）の記憶域のアドレスが記入され、第Ｎ−１エント
リにはり一フ・ノードＬ（ＰＧ　、Ｐ、　、・・・ＰＮ
−１）の記憶域のアドレスが記入されている。

第４図は本発明によるオクト・トリーの生成を説明する
図である。オクト・トリー生成処理は下記のようにして
行われる。

■　２次元配列の要素に＝ｋ　Ｃｉ　〕Ｃｊ　）が入力
をすると、この要素で示される点を特定するためのトラ
ベル・リストを作成し、これを記憶域ＴＲＡに保存する
。

■　記憶域ＴＲＢに保存されている前回のトラベル・リ
ストと、記憶域ＴＲＡに保存されている今回のトラベル
・リストをレベル０より順番に比較する。

■　比較の結果、レベル０からレベル３：まで両者が等
しかったとすると、レベルＸに対応するノードの記憶域
のアドレスをカレント・パス・リスト記憶域ＣＰＬから
める。そして、今回入力された要素によって特定される
レベルｘ＋１のノードないしレベルＮ−１のノードに対
応する記憶域を作成し、上記レベルＸのノードないしレ
ベルＮ−１のノードに対応する記憶域の中に必要な情報
を記憶する。次にトラベル令リスト記憶域ＴＲＡの内容
をトラベル・リスト記憶域ＴＲＢに移すと共に、カレン
トφパスーリスト記憶域ＣＰＬの内容を書き換える。

第５図は本発明が適用される図形処理システムの１例を
示す図である。第５図において、１ないし３はレジスタ
、４は中央処理装置、５はメモリ、６けディスプレイ制
御部、７はディスプレイをそれぞれ示している。レジス
タ１は、今回のトラベル・リスト記憶域ＴＲＡに対応す
るものであり、この中に今回のトラベル・リストが保存
される。

レジスタ２は、前回のトラベルＱリスト記憶域ＴＲＢに
対応するものであり、この中には前回のトラベル・リス
トが保存される。レジスタ３は、カレント・パス・リス
ト記憶域ＣＰＬに対応するものであり、この中にはカレ
ント−パス参リストが保存される。メモリ５には、オク
ト・トリーが記憶される。中央処理装置４は、ホスト計
算機（図示せず）から２次元配列の要素が送られて来る
度に上述のような処理を行ってオクト・トリーを作成し
、これをメモリ５に格納すると共に、メモリ５に格納さ
れているオクト・トリーを基にして図形を表示するため
のコマンドを作成し、コマンドをディスプレイ制御部６
に送るものである。

なお、メモリに格納されているオクト・トリーに基づい
て図形を表示するオクト・トリー・マシンは、既に市販
されている。ディスプレイ制御部６は、中央処理装置４
から送られて来たコマンドに基づいて表示データを作成
し、この表示データをディスプレイ７に与えるものであ
る。

〔発明の効果〕

以上の説明から明らかなように、本発明によれば、オク
ト・トリーを効率よく且つ短時間で作成することが出来
る。

【図面の簡単な説明】

第１図はオクト番トリーを説明する図、第２図は今回の
トラベル・リスト記憶域と前回のトラベル・リスト記憶
域とを示す図、第３図はカレントナすス醗リストを説明
する図、第４図は本発明によるオクト・トリーの生成方
法を説明するフローチャート、第５図は本発明が適用さ
れる図形処理システムの１例を示す図である。 ＴＲＡ・・・今回のトラベル・リスト記憶域、ＴＲＢ・
・・前回のトラベル・リスト記憶域、ＣＰＬ・・・カレ
ント拳パス・リスト記憶域、１ないし３・・・レジスタ
、４・・・中央処理装置、５・・・メモリ、６・・・デ
ィスプレイ制御部、７・・・ディスプレイ。 特許出願人　富士通株式会社 代理人弁理士　京　谷　四　部 ケ１図 （イ） （ロ）（／＼） Ｌ（ｏ、ｏ、ｏ） 牙２図　１１ 第４閏 才５１力

Claims (1)

【特許請求の範囲】
1. オクト・トリーを記憶するメモリと、ディスプレイ装置
   と、上記メモリに格納されているオクト・トリーを基に
   して図形を表示するためのコマンドを作成しこれを上記
   ディスプレイ装置に与える計算機とを具備する図形処理
   システムにおけるオクト参トリー生成方式であって、今
   回のトラベル・リストを記憶する第１のトラベル・リス
   ト記憶域と、前回のトラベル・リストを記憶する第２の
   トラベル・リスト記憶域と、該第２のトラベル・リスト
   記憶域に保存されているトラベル・リストで特定される
   ノードの記憶域のアドレスを記憶するカレント・パス記
   憶域とを有し、且つ上記計算機は、点の位置を表わす２
   次元配列の要素が入力される度にトラベル１リストを作
   成し、これを上記第１のトラベル−リスト記憶域に格納
   し、第１のトラベル・リスト記憶域に格納されている今
   回のトラベル・リストと上記第２のトラベル参リスト記
   憶域に保存されている前回のトラベル・リストとをレベ
   ル０から順番に比較し、レベルｘ＋１で相違が検出され
   たとき、今回のトラベル・リストにおけるレベルｘ＋１
   のノードないしレベルＮ−１のノードのそれぞれに対応
   する記憶域を上記メモリ上に確保し、上記カレント・パ
   ス・リスト記憶域に格納されているカレン）−パス・リ
   ストで特定されるレベルＸのノードの記憶域及び上記レ
   ベルｘ＋１のノードないしレベルＮ−１のノードに対応
   する記憶域に必要な情報を記入するよう構成されている
   ことを特徴とするオクト・トリー生成方式。