(57)【特許請求の範囲】
【請求項１】
木構造を用いた仮想空間データを入力し、与えられた木構造を、木構造自身に組み込まれた情報を破壊することなく、各木構造が元の木構造の情報の一部を保持している木構造群に分解するシーン木構造分解手段と、
上記分解された木構造群に対し、一つの木構造に関する情報を一つの組として記憶する木構造記憶テーブルを生成すると共に、上記各組の形状の領域情報としてバウンディングボックス情報を付加する木構造記憶テーブル生成手段と、
上記バウンディングボックス情報をもとに、空間検索に特化した基準木構造を生成する基準木構造生成手段と、
上記基準木構造生成手段により生成された基準木構造と上記木構造記憶テーブルに記憶されている木構造群を結合する木構造結合手段と
を備えたことを特徴とする木構造を用いた仮想空間データの変換装置。
【請求項２】
木構造を用いた仮想空間データを入力し、与えられた木構造を、木構造自身に組み込まれた情報を破壊することなく、各木構造が元の木構造の情報の一部を保持している木構造群に分解するシーン木構造分解手段と、
上記分解された木構造群に対し、一つの木構造に関する情報を一つの組として記憶する木構造記憶テーブルを生成すると共に、上記各組の形状の領域情報としてバウンディングボックス情報を付加する木構造記憶テーブル生成手段と、
上記木構造記憶テーブルを各組が保持しているテクスチャ情報に応じて少なくとも同じテクスチャを１種類は保持している組が同じテーブル内に存在するように複数のテーブルに分割する木構造記憶テーブル分割手段と、
上記分割された木構造記憶テーブルごとに、上記バウンディングボックス情報をもとに、空間検索に特化した基準木構造を生成する基準木構造生成手段と、
上記基準木構造生成手段により生成された基準木構造と上記分割された木構造記憶テーブルに記憶されている木構造群を結合する木構造結合手段と
を備えたことを特徴とする木構造を用いた仮想空間データの変換装置。
【請求項３】
木構造結合手段で生成された木構造内の形状情報をメッシュ化するメッシュ形状生成手段を備えたことを特徴とする請求項１又は請求項２記載の木構造を用いた仮想空間データの変換装置。
【請求項４】
複数の空間検索に特化した基準木構造を生成する方法を記憶し、記憶されている複数の方法の中から、ユーザの指示により所定の方法を選択する基準木構造生成方法選択手段を備え、
基準木構造生成手段が木構造記憶テーブルの各組が管理している形状のバウンディングボックス情報をもとに、上記基準木構造生成方法選択手段が選択した上記所定の空間検索に特化した基準木構造を生成する方法を使用し、空間検索に特化した基準木構造を生成することを特徴とする請求項１記載の木構造を用いた仮想空間データの変換装置。
【請求項５】
複数の空間検索に特化した基準木構造を生成する方法を記憶し、記憶されている複数の方法の中から、ユーザの指示により所定の方法を選択する基準木構造生成方法選択手段を備え、
基準木構造生成手段が、分割された木構造記憶テーブルごとに、木構造記憶テーブルの各組が管理している形状のバウンディングボックス情報をもとに、上記基準木構造生成方法選択手段が選択した上記所定の空間検索に特化した基準木構造を生成する方法を使用し、空間検索に特化した基準木構造を生成することを特徴とする請求項２記載の木構造を用いた仮想空間データの変換装置。
【請求項６】
空間検索に特化した木構造として、２次元空間を複数の小空間に分割し、その小空間内のデータをかためて管理する木構造を用いたことを特徴とする請求項１から請求項５のうちのいずれか１項記載の木構造を用いた仮想空間データの変換装置。
【請求項７】
空間検索に特化した木構造として、３次元空間を複数の小空間に分割し、その小空間内のデータをかためて管理する木構造を用いたことを特徴とする請求項１から請求項５のうちのいずれか１項記載の木構造を用いた仮想空間データの変換装置。
【請求項８】
空間検索に特化した木構造として、２次元空間をデータの分布状況に応じて領域分割する木構造を用いたことを特徴とする請求項１から請求項５のうちのいずれか１項記載の木構造を用いた仮想空間データの変換装置。
【請求項９】
空間検索に特化した木構造として、３次元空間をデータの分布状況に応じて領域分割する木構造を用いたことを特徴とする請求項１から請求項５のうちのいずれか１項記載の木構造を用いた仮想空間データの変換装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、木構造を用いた仮想空間データの変換装置に関するものであり、特にブラウザの描画速度を向上させるものである。
【０００２】
【従来の技術】
各中間ノードにおいてモデリング変換行列・バウンディングボックス情報のうち少なくともいずれか一つを有し、また各葉ノードにおいて形状（ポリゴン）・テクスチャ・イベントハンドリング・ライティング・色情報のうち少なくともいずれか一つを有する根付き順序木構造で表現される仮想空間データの一例として、ＶＲＭＬ（Ｖｉｒｔｕａｌ  Ｒｅａｌｉｔｙ  Ｍｏｄｅｌｉｎｇ  Ｌａｎｇｕａｇｅ，文献：例えば、三浦憲二朗著、朝倉書店刊、ＶＲＭＬ２．０：３Ｄサイバースペース構築言語）がある。
【０００３】
ＶＲＭＬはインターネット上において仮想空間を公開・共有する環境を実現するために開発された言語である。上記環境は、ＶＲＭＬファイルをインターネットを介してやりとりし、本データ専用の描画ソフトウェア（ブラウザ）が、与えられた木構造を深さ優先探索で走査しながら任意視点の映像を描画することで実現される。
【０００４】
ある仮想空間に対応したＶＲＭＬデータを作成するには無数の表現方法があるが、一般的に、描画時にブラウザが走査するノードの数とテクスチャ（描画属性）のスイッチング回数が少なければ少ない程、また、ポリゴンがメッシュ表現（隣接する三角形から構成される幾何学図形）されている程、ブラウザの描画速度は向上する。従って、ある仮想空間に対応したＶＲＭＬデータが存在した場合に、本ＶＲＭＬデータを、データに組み込まれた仮想空間に関する各種情報を破壊することなく、上記条件を満たすように変換することができれば、同一の仮想空間をより高速に描画するＶＲＭＬデータを作成することができる。
【０００５】
上記変換を自動的に行う従来法として、ｉｖｆｉｘというソフトウェア（シリコングラフィックス社製）がある。ｉｖｆｉｘはＶＲＭＬのベースとなったＯｐｅｎ  Ｉｎｖｅｎｔｏｒファイルフォーマットで記述された根付き順序木構造で表現される仮想空間データに対し、ブラウザの描画速度が向上するようにデータを変換する。
【０００６】
図２０は従来の技術における仮想空間データの変換装置を示すブロック図であり、図において、１は入力された木構造内の各形状情報に関する情報を一つの形状情報とそれに関連する情報群（カメラ、光源モデル、テクスチャ、材質、座標変換等）を一つの組として形状関連情報テーブル７に格納していく形状関連情報テーブル作成部、２は形状関連情報テーブル内の組を描画属性をキーとして並べ替える形状関連情報テーブルソート部、３は形状関連情報テーブルの組で描画属性情報が同一のものを一つの組に結合する形状関連情報テーブルマージ部、４は形状関連情報テーブル７から一つの木構造を生成する木構造生成部、５は形状情報をメッシュ化するメッシュ形状生成部、６は木構造の冗長なノードを除去する冗長情報削除部である。
【０００７】
次に動作について図２１から図２６を参照しながら説明する。
図２１は従来の技術における処理手順を示すフローチャートである。まずステップＳＴ１において、形状関連情報テーブル作成部１は、入力データの木構造を解析し、木構造内で定義されている形状情報とそれに関連する情報群を一つの組として、形状関連情報テーブル７を作成する。
【０００８】
次にステップＳＴ２において、形状関連情報テーブルソート部２は、形状関連情報テーブル７の各組を、描画属性をキーとして並べ替える。次にステップＳＴ３において、形状関連情報テーブルマージ部３は、ソート後の形状関連情報テーブル７に対し、相違水準という属性を追加し、第ｎ組と第ｎ−１組の相違水準を６段階（０，１，２，３，４，５）で判定したものを第ｎ組の相違水準の属性値とする。但し、第１組の相違水準の属性値は１とする。
【０００９】
ここで上記ステップＳＴ３において、形状関連情報テーブルマージ部３が、形状関連情報テーブル７の第ｎ組ｃｎ  と第ｎ−１組ｃｎ−１  の描画属性を比較してｃｎ  の相違水準ｌｎ  を求める処理手順の詳細について図２２に示すフローチャートに従って説明する。まず、ステップＳＴ３１において、ｃｎ  とｃｎ−１  の描画属性において、カメラが同じであるかどうかを判定し、ＮＯの場合にはステップＳＴ３２において、ｌｎ  ＝１として処理を終了する。
【００１０】
上記ステップＳＴ３１においてＹＥＳと判定された場合には、ステップＳＴ３３において、ｃｎ  とｃｎ−１  の描画属性において、光源・大気効果・光源モデルが同じであるかどうかを判定し、ＮＯの場合にはステップＳＴ３４において、ｌｎ  ＝２として処理を終了する。
【００１１】
上記ステップＳＴ３３においてＹＥＳと判定された場合には、ステップＳＴ３５において、ｃｎ  とｃｎ−１  の描画属性において、テクスチャが同じであるかどうかを判定し、ＮＯの場合にはステップＳＴ３６でｌｎ  ＝３として処理を終了する。
【００１２】
上記ステップＳＴ３５においてＹＥＳと判定された場合には、ステップＳＴ３７で、ｃｎ  とｃｎ−１  の描画属性において、描画スタイル・材質・頂点の定義順序が同じであるかどうかを判定し、ＮＯの場合にはステップＳＴ３８において、ｌｎ  ＝４として処理を終了する。
【００１３】
上記ステップＳＴ３７においてＹＥＳと判定された場合には、ステップＳＴ３９で、ｃｎ  とｃｎ−１  の描画属性において、両方の形状が同一ファイル上で定義されているかどうかを判定し、ＮＯの場合にはステップＳＴ４０において、ｌｎ  ＝５として処理を終了し、ＹＥＳの場合にはステップＳＴ４１において、ｌｎ  ＝０として処理を終了する。
【００１４】
次に図２１のステップＳＴ４において、ステップＳＴ３で得られた形状関連情報テーブル７の組で、相違水準が０である組（第ｎ組）が、上の組（第ｎ−１組）と描画属性情報が同一である場合には、形状関連情報テーブルマージ部が、第ｎ組と第ｎ−１組を結合する操作を逐次的に実行する。
【００１５】
ここで、このステップＳＴ４における組の結合操作の処理手順の詳細について、図２３を用いて説明する。ここで、形状関連情報テーブル７の第ｎ組ｃｎ  の相違水準の属性値が０で、第ｎ組ｃｎ  と第ｎ−１組ｃｎ−１  の描画属性情報ＲＡが同じであるとする。この時、ｃｎ−１  の形状情報ｓｎ−１  に変形情報ｔｎ−１  を作用させたものをｓ’ｎ−１、ｃｎ  の形状情報ｓｎ  に変形情報ｔｎ  を作用させたものをｓ’ｎとすると、形状情報がｓ’ｎ−１＋ｓ’ｎ、変形情報がＮＵＬＬ、描画属性情報がＲＡ、相違水準がｌｎ−１  （ｃｎ−１  の相違水準の属性値）である組を生成し、これをｃｎ−１  及びｃｎ  の結合結果とする。
【００１６】
次に図２１のステップＳＴ５において、木構造生成部４は、結合操作後の形状関連情報テーブル７から、図２４に示すフローチャートに従って、一つの木構造Ｔを生成する。まず図２４のステップＳＴ５１において、図２５に示すような深さ５の中間ノードのみからなる直線状の根付き順序木構造Ｔを生成する。この根付き順序木構造Ｔにおいて、Ｒ１  にはカメラに関する情報がどのファイル上にあるかについての情報が格納され、以下、Ｒ２  には光源・大気効果・光源モデル、Ｒ３  にはテクスチャ、Ｒ４  には描画スタイル・材質・頂点の定義順序、Ｒ５  には形状情報というように、各情報がどのファイル上にあるかについての情報が各々格納されていく。
【００１７】
次にステップＳＴ５２において、組番号を示す変数ＮをＮ＝１に初期設定する。そしてステップＳＴ５３において、Ｎが形状関連情報テーブル７の組の数より大きいかどうかを判定し、大きい場合には処理を終了する。Ｎが形状関連情報テーブル７の組の数以下の場合には、ステップＳＴ５４において、深さｄの直線状の根付き順序木構造ＴＮ  を生成する。ここで、深さｄの値は相違水準ｌＮ  により次式で与えられる。
ｄ＝０          ｉｆ  ｌＮ  ＝０
ｄ＝６−ｌＮ      ｏｔｈｅｒｗｉｓｅ
【００１８】
次にステップＳＴ５５において、木構造ＴＮ  に形状関連情報テーブル７の第Ｎ組の情報を挿入していく。ＴＮ  においてＴＮ  の中の深さｉの各ノードｓ（ｉ，ＴＮ  ）に挿入する情報は、ＴＮ  の深さとＴＮ  の中の深さｉにより決定される。
次にステップＳＴ５６において、図２６に示すように、ＴＮ  の根が、Ｔの深さｄ（ＴＮ  ）すなわち図２６では２で、最も右側のノード（深さ優先頂位で最も順位が大きい深さｄ（ＴＮ  ）のノード）の最も右側の子となるように、ＴＮ  をＴに挿入する。ここで、深さｄ（ＴＮ  ）の値は相違水準ｌＮ  により次式で与えられる。
ｄ（ＴＮ  ）＝５          ｉｆ  ｌＮ  ＝０
ｄ（ＴＮ  ）＝ｌＮ  −１    ｏｔｈｅｒｗｉｓｅ
そしてステップＳＴ５７において、Ｎ＝Ｎ＋１とインクリメントして、ステップＳＴ５３へ戻る。
【００１９】
次に図２１のステップＳＴ６において、メッシュ形状生成部５はステップＳＴ５で得られた根付き順序木構造Ｔ内の形状情報をメッシュ化する。そして最後にステップＳＴ７において、冗長情報削除部６は根付き順序木構造Ｔをブラウザと同様に深さ優先探索で走査することで、冗長なノードを検知・除去し出力する。
【００２０】
以上のように、従来の技術における仮想空間データの変換装置は、根付き順序木構造で表現される仮想空間データを変換することで、描画時におけるテクスチャ（描画属性）のスイッチング回数が減少し、ほとんどの場合において変換前に比べ木構造のノード数が減少することにより、また形状をメッシュ化することによりポリゴンの描画速度が向上する。
【００２１】
【発明が解決しようとする課題】
しかし従来の仮想空間データの変換装置は、結合操作により形状の階層構造・独立性が損なわれ、映像情報以外の情報が破壊されるという課題があった。従って、ユーザからのインタラクション（マウスによりあるオブジェクトをクリックする等）に応じてなんらかのアクションを定義しているような仮想空間データに本手法を適用すると、変換後には正常に動作しなくなる。
【００２２】
また、形状情報の位置・大きさに関係なく描画属性が同一のものを一つの形状情報として結合するため、視野領域外のポリゴンについても、それと同じ描画属性情報をもつポリゴンが視野領域内に存在する場合には描画処理される。従って、ほとんどのポリゴンが視野領域外となる広域な仮想空間を表現した木構造の場合には、無駄な描画処理が頻繁に発生し、描画速度が遅くなるという課題があった。
【００２３】
この発明は上記のような課題を解決するためになされたもので、映像情報以外の情報損失が生じることなく、広域な仮想空間を表現したデータに対してもブラウザの描画速度が向上するような木構造を用いた仮想空間データの変換装置を得ることを目的とする。
【００２４】
【課題を解決するための手段】
この発明に係る木構造を用いた仮想空間データの変換装置は、木構造を用いた仮想空間データを入力し、与えられた木構造を、木構造自身に組み込まれた情報を破壊することなく、各木構造が元の木構造の情報の一部を保持している木構造群に分解するシーン木構造分解手段と、上記分解された木構造群に対し、一つの木構造に関する情報を一つの組として記憶する木構造記憶テーブルを生成すると共に、上記各組の形状の領域情報としてバウンディングボックス情報を付加する木構造記憶テーブル生成手段と、上記バウンディングボックス情報をもとに、空間検索に特化した基準木構造を生成する基準木構造生成手段と、上記基準木構造生成手段により生成された基準木構造と上記木構造記憶テーブルに記憶されている木構造群を結合する木構造結合手段とを備えたものである。
【００２５】
この発明に係る木構造を用いた仮想空間データの変換装置は、木構造を用いた仮想空間データを入力し、与えられた木構造を、木構造自身に組み込まれた情報を破壊することなく、各木構造が元の木構造の情報の一部を保持している木構造群に分解するシーン木構造分解手段と、上記分解された木構造群に対し、一つの木構造に関する情報を一つの組として記憶する木構造記憶テーブルを生成すると共に、上記各組の形状の領域情報としてバウンディングボックス情報を付加する木構造記憶テーブル生成手段と、上記木構造記憶テーブルを各組が保持しているテクスチャ情報に応じて少なくとも同じテクスチャを１種類は保持している組が同じテーブル内に存在するように複数のテーブルに分割する木構造記憶テーブル分割手段と、上記分割された木構造記憶テーブルごとに、上記バウンディングボックス情報をもとに、空間検索に特化した基準木構造を生成する基準木構造生成手段と、上記基準木構造生成手段により生成された基準木構造と上記分割された木構造記憶テーブルに記憶されている木構造群を結合する木構造結合手段とを備えたものである。
【００２６】
この発明に係る木構造を用いた仮想空間データの変換装置は、木構造結合手段で生成された木構造内の形状情報をメッシュ化するメッシュ形状生成手段を備えたものである。
【００２７】
この発明に係る木構造を用いた仮想空間データの変換装置は、複数の空間検索に特化した基準木構造を生成する方法を記憶し、記憶されている複数の方法の中から、ユーザの指示により所定の方法を選択する基準木構造生成方法選択手段を備え、基準木構造生成手段が木構造記憶テーブルの各組が管理している形状のバウンディングボックス情報をもとに、上記基準木構造生成方法選択手段が選択した上記所定の空間検索に特化した基準木構造を生成する方法を使用し、空間検索に特化した基準木構造を生成するものである。
【００２８】
この発明に係る木構造を用いた仮想空間データの変換装置は、複数の空間検索に特化した基準木構造を生成する方法を記憶し、記憶されている複数の方法の中から、ユーザの指示により所定の方法を選択する基準木構造生成方法選択手段を備え、基準木構造生成手段が、分割された木構造記憶テーブルごとに、木構造記憶テーブルの各組が管理している形状のバウンディングボックス情報をもとに、上記基準木構造生成方法選択手段が選択した上記所定の空間検索に特化した基準木構造を生成する方法を使用し、空間検索に特化した基準木構造を生成するものである。
【００２９】
この発明に係る木構造を用いた仮想空間データの変換装置は、空間検索に特化した木構造として、２次元空間を複数の小空間に分割し、その小空間内のデータをかためて管理する木構造を用いたものである。
【００３０】
この発明に係る木構造を用いた仮想空間データの変換装置は、空間検索に特化した木構造として、３次元空間を複数の小空間に分割し、その小空間内のデータをかためて管理する木構造を用いたものである。
【００３１】
この発明に係る木構造を用いた仮想空間データの変換装置は、空間検索に特化した木構造として、２次元空間をデータの分布状況に応じて領域分割する木構造を用いたものである。
【００３２】
この発明に係る木構造を用いた仮想空間データの変換装置は、空間検索に特化した木構造として、３次元空間をデータの分布状況に応じて領域分割する木構造を用いたものである。
【００３３】
【発明の実施の形態】
以下、この発明の実施の一形態を説明する。
実施の形態１．
図１はこの発明の実施の形態１における木構造を用いた仮想空間データの変換装置を示すブロック図であり、図において、１０１は与えられた木構造を木構造自身に組み込まれた情報を破壊しないように、各木構造が元の木構造の情報の一部を保持している木構造群に分解するシーン木構造分解部（シーン木構造分解手段）、１０２はシーン木構造分解部１０１で分解された木構造群に対し、一つの木構造に関する情報を一つの組として記憶することにより木構造記憶テーブル１０３を生成する木構造記憶テーブル生成部（木構造記憶テーブル生成手段）である。
【００３４】
また、１０４は木構造記憶テーブル１０３の各組が管理している形状のバウンディングボックス（各組が保持している形状を含む最小の直方体）情報をもとに空間検索に特化した基準木構造を生成する基準木構造生成部（基準木構造生成手段）、１０５は基準木構造と木構造記憶テーブルで記憶されている木構造群を結合することで与えられた木構造と等価な仮想空間を表現した一つの木構造を生成する木構造結合部（木構造結合手段）である。
【００３５】
次に動作について説明する。
図２はこの実施の形態１における木構造を用いた仮想空間データの変換装置の処理手順を示すフローチャートである。まずステップＳＴ１０１において、シーン木構造分解部１０１は、ある仮想空間を表現した木構造が与えられると、木構造自身に組み込まれた情報を破壊しないように、各木構造が元の木構造の情報の一部を保持している木構造に分解する。
【００３６】
ここで、このシーン木構造分解部１０１によるステップＳＴ１０１の処理手順の詳細について、図３のフローチャートを用いて説明する。
まずステップＳＴ１１０１において、処理対象となる木構造を示す変数ＴＰを変換対象となる木構造Ｔに設定し、分解処理の深さを示す変数Ｑの値を０に初期化する。
【００３７】
次にステップＳＴ１１０２において、変数ＴＰがこれ以上分解可能かどうかを判定する。このステップＳＴ１１０２でＮＯと判定されるのは、
イ．ＴＰに形状情報が存在しない、
ロ．ＴＰ内の全ての形状に共通のユーザからの入力に対する動作メカニズムが定義（例えば、ＶＲＭＬにおけるＴｏｕｃｈ  Ｓｅｎｓｏｒを利用したアニメーション機能）されている、
ハ．ＴＰの深さが１以下である、
のいずれかの条件が満たされる場合である。
【００３８】
上記ステップＳＴ１１０２でＹＥＳと判定された場合には、ステップＳＴ１１０３において、Ｑ＝Ｑ＋１とする。
そしてステップＳＴ１１０４において、ＴＰの根の子で葉でないものを中間ノードｖｉ  （ｉ＝１，２，・・・，ｎ：ｎ＝ＴＰの根の子で葉でないものの個数）とした時に、図４に示すようにＴＰを、
（ａ）ＴＰの根とその子で葉であるもののみからなる木構造ＴＰ（Ｑ，０）
［根に葉が存在する場合のみ］、
（ｂ）ＴＰの根と中間ノードｖｉ  とその子孫とからなる木構造ＴＰ（Ｑ，ｉ）
［ｉ＝１，２，・・・，ｎ］、
に分解する。
【００３９】
次にステップＳＴ１１０５において、各ＴＰ（Ｑ，ｉ）［１≦ｉ≦ｎ］に対し、図５に示すように、根から分岐が１であるノード（Ｒｉ  （ｉ＝０，１，・・・，ｒ））までを、Ｒｉ  が保持しているモデリング変換行列情報をＭｉ  ，各Ｍｉ  を乗算したモデリング変換行列情報をＭ（Ｍ＝Ｍｒ  ×Ｍｒ−１  ×・・・×Ｍ０  ），Ｒ０  の子孫ノードが管理している形状のバウンディングボックスをＢとした時に、モデリング変換行列情報としてＭを有し、バウンディングボックス情報としてＢを有するノードＲに置き換えることで、Ｒｉ  （ｉ＝０，１，・・・，ｒ）を情報損失がないように一つのノードＲにまとめる。
【００４０】
次にステップＳＴ１１０６において、深さＱにおける分解処理で生成された木構造の数ＮＮ［Ｑ］を、ＮＮ［Ｑ］＝ｎ＋１とし、深さＱにおける分解処理のインデックスＮＩ［Ｑ］を、ＮＩ［Ｑ］＝０とする。
そしてステップＳＴ１１０７において、ＮＩ［Ｑ］＞ＮＮ［Ｑ］であるかどうか判定する。このステップＳＴ１１０７でＮＯと判定された場合には、ステップＳＴ１１０８でＴＰ＝ＴＰ（Ｑ，ＮＩ［Ｑ］）とし、ステップＳＴ１１０２へ戻る。ＹＥＳと判定された場合には、ステップＳＴ１１０９でＱ＝Ｑ−１とし、ステップＳＴ１１１０でＱ≦０であるかどうかを判定する。
【００４１】
上記ステップＳＴ１１１０でＮＯと判定された場合には、ステップＳＴ１１１１でＮＩ［Ｑ］＝ＮＩ［Ｑ］＋１とし、ステップＳＴ１１０７へ戻り、ＹＥＳと判定された場合には終了する。また、上記ステップＳＴ１１０２でＮＯと判定された場合には、ステップＳＴ１１１２でＴＰを出力し、ステップＳＴ１１１３でＮＩ［Ｑ］＝ＮＩ［Ｑ］＋１としてステップＳＴ１１０７へジャンプする。
【００４２】
次に図２のステップＳＴ１０２において、木構造記憶テーブル生成部１０２は、ステップＳＴ１０１で生成された木構造群ＴＰ（ｉ）  （ｉ＝０，１，・・・，ｎ：ｎ＋１＝ステップＳＴ１０１で生成された木構造の個数）に対し、一つの木構造ＴＰ（ｉ）  に関する情報を木構造記憶テーブル１０３の一つの組ｃｉ  に格納する。次にステップＳＴ１０３において、木構造記憶テーブル１０３に対し、木構造記憶テーブル生成部１０２は領域情報という属性を付加し、バウンディングボックス（各組が保持している形状を包含する最小の直方体）をその組の領域情報の属性値とする。但し、形状情報が存在しない場合には、領域情報はＮＵＬＬとする。
【００４３】
次にステップＳＴ１０４において、図６に示すように、ステップＳＴ１０３で得られた木構造記憶テーブル１０３の組で領域情報がＮＵＬＬでないものをｃｊ  、ｃｊ  の領域情報をｒｊ  （バウンディングボックス）、ｒｊ  のＸＺ平面（Ｘ軸：幅方向、Ｚ軸：奥行き方向）への投影図形をｐｊ  とした時に、基準木構造生成部１０４は、ｐｊ  （１≦ｊ≦ｎ）を２次元図形の効率的な管理を行う木構造でパケット型であるもの（一つの葉に複数の図形データに関する情報を管理するもの）に逐次投入することで木構造Ｔｂ  を生成し、これを基準木構造とする。
【００４４】
なお、２次元図形を効率的に管理する木構造（範囲検索が０（ｌｏｇＮ）となるもの：Ｎ＝データ数）は、例えば、中村泰明他３名による「多次元データの平衡木による管理−ＭＤ木の提案−」（電子情報通信学会論文誌、Ｖｏｌ．Ｊ７１−Ｄ，Ｎｏ．９，１９８８年９月）等に示されている公知のものである。
【００４５】
最後にステップＳＴ１０５において、木構造結合部１０５が、基準木構造Ｔｂ  と木構造記憶テーブル１０３で記憶されている木構造群を結合することで与えられた木構造と等価な仮想空間を表現した一つの木構造Ｔｏｐｔ  を生成・出力して処理を終了する。
【００４６】
このステップＳＴ１０５において、Ｔｏｐｔ  を生成する処理手順の詳細について図７を用いて説明する。
まず、基準木構造Ｔｂ  の葉ｌｋ  （１≦ｋ≦Ｌ，Ｌ＝Ｔｂ  の葉の個数）が保持している２次元図形をｐ（ｋｍ  ）（ｍ＝１，２，・・・，Ｍ：Ｍ＝葉ｌｋ  が管理している２次元図形の個数）とした時に、ｌｋ  をステップＳＴ１０１で生成した木構造Ｔｐ（ｋｍ  ）（ｍ＝１，２，・・・，Ｍ）に置き換える。次に、Ｔｂ  の葉でないノードを、その全ての子孫ノードが保持している形状情報のバウンディングボックス情報をもったノード（例えば、ＶＲＭＬにおけるＧｒｏｕｐノード）に置き換える。そして最後に、Ｔｂ  の根にステップＳＴ１０１で生成した木構造で形状情報を持たないものを追加する。
【００４７】
ブラウザは図８に示すように、根付き順序木構造を深さ優先探索で走査し、ノード到達時に、そのノードの子孫ノードが視野領域内に存在するか否かをノードが保持しているバウンディングボックス情報をもとに判定し、存在しない場合には子孫ノードへの探索は行わない。例えば、図９においてノードＡの子孫ノードへの探索は、視野領域外なので行われないが、ノードＢの子孫ノードへの探索は、視野領域内なので行われる。
【００４８】
以上のように、この実施の形態１によれば、与えられた木構造を、情報損失がないように複数の木構造に分解し、分解した木構造群を走査ノード数が（Ｏ（ｌｏｇＮ）：Ｎは図４で示された分解された木構造の数）となるように再構築するため、映像情報以外の情報を損失することなく描画時に操作するノード数を大幅に減らすことができ、その結果、ブラウザの描画速度が向上するという効果が得られる。
【００４９】
この実施の形態をもとに実際の都市の約１ｋｍ四方のＶＲＭＬファイル（バージョン２．０）を変換したところ、ブラウザ（シリコングラフィックス社：ｃｏｓｍｏｐ１ａｙｅｒ）の描画速度が３〜４倍向上した。
【００５０】
実施の形態２．
図１０はこの発明の実施の形態２による木構造を用いた仮想空間データの変換装置を示すブロック図であり、図１と対応する部分には図１と同一符号を付してその説明を省略する。図１０において、１０６は、木構造記憶テーブル１０３を各組が保持しているテクスチャ情報に応じて、少なくとも同じテクスチャを１種類は保持している組が同じテーブル内に存在するように、複数のテーブルに分割する木構造記憶テーブル分割部（木構造記憶テーブル分割手段）である。
【００５１】
次に動作について説明する。
図１１はこの実施の形態２における木構造を用いた仮想空間データの変換装置の処理手順を示すフローチャートである。まずステップＳＴ１０１及びＳＴ１０２の処理は、実施の形態１の図２におけるステップＳＴ１０１及びＳＴ１０２の処理と同じである。
そしてステップＳＴ２０１において、木構造記憶テーブル分割部１０６は、ステップＳＴ１０２で生成された木構造記憶テーブル１０３を、各組が使用しているテクスチャ情報に応じて複数のテーブルに分割する。
【００５２】
ここでこのステップＳＴ２０１において、木構造記憶テーブル分割部１０６が木構造記憶テーブル１０３を分割する処理手順の詳細について、図１２のフローチャートを用いて説明する。
まずステップＳＴ２１０１において、木構造記憶テーブル１０３内で使用されているテクスチャをテクスチャサイズについて降順にソートしたものをｔｅｘ１  ，ｔｅｘ２  ，・・・，ｔｅｘｑ  とする。
次にステップＳＴ２１０２において、テクスチャ番号ＩをＩ＝１に初期設定し、ステップＳＴ２１０３において、木構造記憶テーブル１０３の各組に選択フラグという属性を付加し、全ての組の選択フラグをＦＡＬＳＥに設定する。
【００５３】
次にステップＳＴ２１０４において、木構造記憶テーブル１０３の組でテクスチャｔｅｘＩ  を使用しており、選択フラグがＦＡＬＳＥであるものからなるテーブルＴＢＬＩ  を作成する。
そしてステップＳＴ２１０５で、上記ステップＳＴ２１０４で選択された組の選択フラグをＴＲＵＥに設定する。
次にステップＳＴ２１０６において、Ｉ＝ｑであるかどうか判定し、ＹＥＳの場合には、ステップＳＴ２１０７で、選択フラグがＦＡＬＳＥである組（即ち、テクスチャを使用していない組）からなるテーブルＴＢＬ０  を作成して処理を終了する。
上記ステップＳＴ２１０６においてＮＯと判定された場合には、ステップＳＴ２１０８でＩ＝Ｉ＋１とインクリメントして、ステップＳＴ２１０４へ戻る。
【００５４】
次に図１１のステップＳＴ２０２において、基準木構造生成部１０４は、各ＴＢＬｊ  ごとに実施の形態１の手順に従ってＴＢＬｊ  に対応した仮想空間を表現した木構造Ｔｏｐｔ（ｊ）を生成する。
そしてステップＳＴ２０３において、図１３に示すように、木構造結合部１０５がＴｏｐｔ（０），Ｔｏｐｔ（１），・・・Ｔｏｐｔ（ｑ）を結合して一つの木構造Ｔｏｐｔ  を生成・出力して処理を終了する。
【００５５】
以上のように、この実施の形態２によれば、同じテクスチャを持っているテーブルをソートしているので、実施の形態１に比べ描画時におけるテクスチャ（描画属性）のスイッチング回数を減少させることができ、ブラウザの描画速度を向上させることができるという効果が得られる。
【００５６】
実施の形態３．
図１４はこの発明の実施の形態３による木構造を用いた仮想空間データの変換装置を示すブロック図であり、図１０と対応する部分には図１０と同一符号を付してその説明を省略する。図１４において、１０７は木構造結合部１０５で生成した木構造内の形状情報をメッシュ化するメッシュ形状生成部（メッシュ形状生成手段）である。
【００５７】
次に動作について説明する。
図１５はこの実施の形態３における木構造を用いた仮想空間データの変換装置の処理手順を示すフローチャートである。この実施の形態では、上記実施の形態２において、ステップＳＴ２０３で生成した木構造Ｔｏｐｔ  内の各形状情報を、ステップＳＴ３０１において、メッシュ形状生成部１０７がメッシュ化するようにしたものである。
【００５８】
以上のように、この実施の形態３によれば、形状をメッシュ化することでグラフィックスエンジンの描画コストが軽減するように与えられた木構造と等価な仮想空間を表現した木構造を生成することができ、ブラウザの描画速度を向上させることができるという効果が得られる。
【００５９】
この実施の形態３では、実施の形態２にメッシュ形状生成部１０７を追加しているが、実施の形態１にメッシュ形状生成部１０７を追加しても、同様の効果が得られる。
【００６０】
実施の形態４．
図１６はこの発明の実施の形態４による木構造を用いた仮想空間データの変換装置を示すブロック図であり、図１と対応する部分には図１と同一符号を付してその説明を省略する。図１６において、１０８は空間検索に特化した木構造を生成する方法を複数種類記憶しておき、基準木構造生成部１０４において空間検索に特化した木構造を生成する際の木構造を、ユーザの指示により選択する基準木構造生成方法選択部（基準木構造生成方法選択手段）である。
【００６１】
次に動作について説明する。
図１７はこの実施の形態４における木構造を用いた仮想空間データの変換装置の処理手順を示すフローチャートである。この実施の形態におけるステップＳＴ１０１からＳＴ１０３までの処理は、上記実施の形態１の図２におけるステップＳＴ１０１からＳＴ１０３までの処理と同じである。
ステップＳＴ４０１において、基準木構造生成方法選択部１０８が、あらかじめ用意しておいた空間検索に特化した木構造の中からユーザの指示により木構造を選択する。
そしてステップＳＴ１０４において、基準木構造生成部１０４が、選択された木構造を用いて基準木構造を生成する。ステップＳＴ１０５の処理は実施の形態１と同様である。
【００６２】
空間検索に特化した木構造としては、実施の形態１で用いた２次元図形を効率的に管理する木構造の他に、３次元空間を効率的に管理する木構造（例えばｏｃｔｒｅｅ、文献：Ｃ．Ｌ．Ｊａｃｋｉｎｓ  ａｎｄ  Ｓ．Ｌ．Ｔａｎｉｍｏｎｏ，“Ｏｃｔ−Ｔｒｅｅｓ  ａｎｄ  Ｔｈｅｉｒ  Ｕｓｅ  ｉｎ  Ｒｅｐｒｅｓｅｎｔｉｎｇ  Ｔｈｒｅｅ−Ｄｉｍｅｎｓｉｏｎａｌ  Ｏｂｊｅｃｔｓ”，Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ  ａｎｄ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ，Ｎｏｖ．１９８０，ｐｐ．２４９−２７０）がある。変換対象となる仮想空間データが都市空間のように、平面方向（ＸＹ平面）の広がりに比べ、高さ方向（Ｚ軸）の広がりが非常に小さいような空間である場合には、空間を２次元的に管理する方が効率的である。
【００６３】
一方、大規模な分子モデルや科学シミュレーション結果の３次元視覚化データのように、高さ方向についても平面方向と同程度の広がりを持つ仮想空間データについては、３次元的に管理する方が効率的であり、変換対象となる仮想空間データの空間特性に応じてユーザが基準木構造を生成する際に使用する木構造を選択する方が、実施の形態１に比べ、よりブラウザの描画速度が向上する木構造を生成することができる。
【００６４】
この実施の形態４では、実施の形態１に基準木構造生成方法選択部１０８を追加しているが、実施の形態２に基準木構造生成方法選択部１０８を追加しても、同様の効果が得られる。
【００６５】
実施の形態５．
この発明の実施の形態５では、上記実施の形態１から実施の形態４において空間検索に特化した木構造として、２次元空間を複数の小空間に分割し、その小空間内のデータをかためて管理する木構造を用いることで、図１８に示すように仮想空間を管理するものである。
【００６６】
この実施の形態では木構造の実装が容易であり、また仮想空間内において３次元形状が均等に分布し、かつ仮想空間の高さ方向の広がりが非常に小さい場合には実施の形態１で用いた２次元図形を効率的に管理する木構造（範囲検索、すなわち走査ノード数が０（ｌｏｇＮ））と同等の検索効率を実現することができるという効果が得られる。
【００６７】
実施の形態６．
この発明の実施の形態６では、上記実施の形態１から実施の形態４において空間検索に特化した木構造として、３次元空間を複数の小空間に分割し、その小空間内のデータをかためて管理する木構造を用いることで、図１９に示すように仮想空間を管理するものである。
【００６８】
この実施の形態でも木構造の実装が容易であり、また仮想空間内において３次元形状が均等に分布する場合には実施の形態４で用いた３次元図形を効率的に管理する木構造（範囲検索、すなわち走査ノード数が０（ｌｏｇＮ））と同等の検索効率を実現することができるという効果が得られる。
【００６９】
実施の形態７．
この発明の実施の形態７では、上記実施の形態４において空間検索に特化した木構造として、２次元空間をデータの分布状況に応じて領域分割することで、動的なデータに対しても静的なデータに対しても、ともに良好な領域分割を実現する木構造を複数用意するものである。これら木構造として、実施の形態１で用いた木構造の他に、例えば、大沢、坂内：「良好な動特性を持つ多次元データ管理構造の一提案」（電子情報通信学会論文誌、Ｖｏｌ．Ｊ６６−Ｄ、Ｎｏ．１０、１９８３）等があり、これら木構造には、実装の容易さ、検索効率、木の生成時間等でそれぞれ特徴があることから、複数用意することで目的に応じて最適な木構造を選択することができる。
【００７０】
実施の形態８．
この発明の実施の形態８では、上記実施の形態４において空間検索に特化した木構造として、３次元空間をデータの分布状況に応じて領域分割することで、動的なデータに対しても静的なデータに対しても、ともに良好な領域分割を実現する木構造を複数用意するものである。これら木構造として、実施の形態４で用いた木構造の他に、“Ｊａｎｓｅｎ、Ｆ．，Ｄａｔａ  Ｓｔｒｕｃｔｕｒｅｓ  ｆｏｒ  Ｒａｙ  Ｔｒａｃｉｎｇ、Ｄａｔａ  Ｓｔｒｕｃｔｕｒｅｓ  ｆｏｒ  Ｒａｓｔｅｒ  Ｇｒａｐｈｉｃｓ、ｐ５７−７３、１９８６”等があり、これら木構造には、実装の容易さ、検索効率、木の生成時間等でそれぞれ特徴があることから、複数用意することで目的に応じて最適な木構造を選択することができる。
【００７１】
【発明の効果】
以上のように、この発明によれば、情報損失を生じることなく、描画時に操作するノード数を大幅に減らすことができるので、ブラウザの描画速度が向上する効果がある。
【００７２】
また、この発明によれば、同じテクスチャを持っているテーブルをソートしているので、描画時におけるテクスチャ（描画属性）のスイッチング回数を減少させることができ、ブラウザの描画速度を向上させることができる効果がある。
【図面の簡単な説明】
【図１】この発明の実施の形態１による木構造を用いた仮想空間データの変換装置を示すブロック図である。
【図２】この発明の実施の形態１による処理手順を示すフローチャートである。
【図３】木構造分解の処理手順を示すフローチャートである。
【図４】木構造分解の説明図である。
【図５】ノード結合の説明図である。
【図６】３次元形状と領域情報・投影図形の関係についての説明図である。
【図７】基準木構造からシーン木構造への変換の説明図である。
【図８】描画時におけるブラウザのノード走査手順の説明図である。
【図９】ノード走査とバウンディングボックスの関係の説明図である。
【図１０】この発明の実施の形態２による木構造を用いた仮想空間データの変換装置を示すブロック図である。
【図１１】この発明の実施の形態２による処理手順を示すフローチャートである。
【図１２】木構造記憶テーブル分割の処理手順を示すフローチャートである。
【図１３】Ｔｏｐｔ  （０），Ｔｏｐｔ  （１），・・・Ｔｏｐｔ  （ｑ）からＴｏｐｔ  生成の説明図である。
【図１４】この発明の実施の形態３による木構造を用いた仮想空間データの変換装置を示すブロック図である。
【図１５】この発明の実施の形態３による処理手順を示すフローチャートである。
【図１６】この発明の実施の形態４による木構造を用いた仮想空間データの変換装置を示すブロック図である。
【図１７】この発明の実施の形態４による処理手順を示すフローチャートである。
【図１８】２次元空間を複数の小空間に分割し、その小空間内のデータをかためて管理する木構造による仮想空間管理の説明図である。
【図１９】３次元空間を複数の小空間に分割し、その小空間内のデータをかためて管理する木構造による仮想空間管理の説明図である。
【図２０】従来の木構造を用いた仮想空間データの変換装置を示すブロック図である。
【図２１】従来の処理手順を示すフローチャートである。
【図２２】従来の相違水準決定手順を示すフローチャートである。
【図２３】従来の形状関連情報テーブルの結合操作手順の説明図である。
【図２４】従来の形状関連情報テーブルから木構造を生成する処理手順を示すフローチャートである。
【図２５】従来における深さ５の直線上の木構造の説明図である。
【図２６】従来における木構造の生成手順の説明図である。
【符号の説明】
１０１  シーン木構造分解部（シーン木構造分解手段）、１０２  木構造記憶テーブル生成部（木構造記憶テーブル生成手段）、１０３  木構造記憶テーブル、１０４  基準木構造生成部（基準木構造生成手段）、１０５  木構造結合部（木構造結合手段）、１０６  木構造記憶テーブル分割部（木構造記憶テーブル分割手段）、１０７  メッシュ形状生成部（メッシュ形状生成手段）、１０８  基準木構造生成方法選択部（基準木構造生成方法選択手段）。
【図１】
0003602304.tif 000002
【図２】
0003602304.tif 000003
【図３】
0003602304.tif 000004
【図４】
0003602304.tif 000005
【図５】
0003602304.tif 000006
【図６】
0003602304.tif 000007
【図７】
0003602304.tif 000008
【図８】
0003602304.tif 000009
【図９】
0003602304.tif 000010
【図１０】
0003602304.tif 000011
【図１１】
0003602304.tif 000012
【図１２】
0003602304.tif 000013
【図１３】
0003602304.tif 000014
【図１４】
0003602304.tif 000015
【図１５】
0003602304.tif 000016
【図１６】
0003602304.tif 000017
【図１７】
0003602304.tif 000018
【図１８】
0003602304.tif 000019
【図１９】
0003602304.tif 000020
【図２０】
0003602304.tif 000021
【図２１】
0003602304.tif 000022
【図２２】
0003602304.tif 000023
【図２３】
0003602304.tif 000024
【図２４】
0003602304.tif 000025
【図２５】
0003602304.tif 000026
【図２６】
0003602304.tif 000027