JP3602304B2 - Virtual space data converter using tree structure - Google Patents
Virtual space data converter using tree structure Download PDFInfo
- Publication number
- JP3602304B2 JP3602304B2 JP23283097A JP23283097A JP3602304B2 JP 3602304 B2 JP3602304 B2 JP 3602304B2 JP 23283097 A JP23283097 A JP 23283097A JP 23283097 A JP23283097 A JP 23283097A JP 3602304 B2 JP3602304 B2 JP 3602304B2
- Authority
- JP
- Japan
- Prior art keywords
- tree structure
- information
- virtual space
- specialized
- shape
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Processing Or Creating Images (AREA)
Description
【０００１】
【発明の属する技術分野】
この発明は、木構造を用いた仮想空間データの変換装置に関するものであり、特にブラウザの描画速度を向上させるものである。
【０００２】
【従来の技術】
各中間ノードにおいてモデリング変換行列・バウンディングボックス情報のうち少なくともいずれか一つを有し、また各葉ノードにおいて形状（ポリゴン）・テクスチャ・イベントハンドリング・ライティング・色情報のうち少なくともいずれか一つを有する根付き順序木構造で表現される仮想空間データの一例として、ＶＲＭＬ（Ｖｉｒｔｕａｌ Ｒｅａｌｉｔｙ Ｍｏｄｅｌｉｎｇ Ｌａｎｇｕａｇｅ，文献：例えば、三浦憲二朗著、朝倉書店刊、ＶＲＭＬ２．０：３Ｄサイバースペース構築言語）がある。
【０００３】
ＶＲＭＬはインターネット上において仮想空間を公開・共有する環境を実現するために開発された言語である。上記環境は、ＶＲＭＬファイルをインターネットを介してやりとりし、本データ専用の描画ソフトウェア（ブラウザ）が、与えられた木構造を深さ優先探索で走査しながら任意視点の映像を描画することで実現される。
【０００４】
ある仮想空間に対応したＶＲＭＬデータを作成するには無数の表現方法があるが、一般的に、描画時にブラウザが走査するノードの数とテクスチャ（描画属性）のスイッチング回数が少なければ少ない程、また、ポリゴンがメッシュ表現（隣接する三角形から構成される幾何学図形）されている程、ブラウザの描画速度は向上する。従って、ある仮想空間に対応したＶＲＭＬデータが存在した場合に、本ＶＲＭＬデータを、データに組み込まれた仮想空間に関する各種情報を破壊することなく、上記条件を満たすように変換することができれば、同一の仮想空間をより高速に描画するＶＲＭＬデータを作成することができる。
【０００５】
上記変換を自動的に行う従来法として、ｉｖｆｉｘというソフトウェア（シリコングラフィックス社製）がある。ｉｖｆｉｘはＶＲＭＬのベースとなったＯｐｅｎ Ｉｎｖｅｎｔｏｒファイルフォーマットで記述された根付き順序木構造で表現される仮想空間データに対し、ブラウザの描画速度が向上するようにデータを変換する。
【０００６】
図２０は従来の技術における仮想空間データの変換装置を示すブロック図であり、図において、１は入力された木構造内の各形状情報に関する情報を一つの形状情報とそれに関連する情報群（カメラ、光源モデル、テクスチャ、材質、座標変換等）を一つの組として形状関連情報テーブル７に格納していく形状関連情報テーブル作成部、２は形状関連情報テーブル内の組を描画属性をキーとして並べ替える形状関連情報テーブルソート部、３は形状関連情報テーブルの組で描画属性情報が同一のものを一つの組に結合する形状関連情報テーブルマージ部、４は形状関連情報テーブル７から一つの木構造を生成する木構造生成部、５は形状情報をメッシュ化するメッシュ形状生成部、６は木構造の冗長なノードを除去する冗長情報削除部である。
【０００７】
次に動作について図２１から図２６を参照しながら説明する。
図２１は従来の技術における処理手順を示すフローチャートである。まずステップＳＴ１において、形状関連情報テーブル作成部１は、入力データの木構造を解析し、木構造内で定義されている形状情報とそれに関連する情報群を一つの組として、形状関連情報テーブル７を作成する。
【０００８】
次にステップＳＴ２において、形状関連情報テーブルソート部２は、形状関連情報テーブル７の各組を、描画属性をキーとして並べ替える。次にステップＳＴ３において、形状関連情報テーブルマージ部３は、ソート後の形状関連情報テーブル７に対し、相違水準という属性を追加し、第ｎ組と第ｎ−１組の相違水準を６段階（０，１，２，３，４，５）で判定したものを第ｎ組の相違水準の属性値とする。但し、第１組の相違水準の属性値は１とする。
【０００９】
ここで上記ステップＳＴ３において、形状関連情報テーブルマージ部３が、形状関連情報テーブル７の第ｎ組ｃｎ と第ｎ−１組ｃｎ−１ の描画属性を比較してｃｎ の相違水準ｌｎ を求める処理手順の詳細について図２２に示すフローチャートに従って説明する。まず、ステップＳＴ３１において、ｃｎ とｃｎ−１ の描画属性において、カメラが同じであるかどうかを判定し、ＮＯの場合にはステップＳＴ３２において、ｌｎ ＝１として処理を終了する。
【００１０】
上記ステップＳＴ３１においてＹＥＳと判定された場合には、ステップＳＴ３３において、ｃｎ とｃｎ−１ の描画属性において、光源・大気効果・光源モデルが同じであるかどうかを判定し、ＮＯの場合にはステップＳＴ３４において、ｌｎ ＝２として処理を終了する。
【００１１】
上記ステップＳＴ３３においてＹＥＳと判定された場合には、ステップＳＴ３５において、ｃｎ とｃｎ−１ の描画属性において、テクスチャが同じであるかどうかを判定し、ＮＯの場合にはステップＳＴ３６でｌｎ ＝３として処理を終了する。
【００１２】
上記ステップＳＴ３５においてＹＥＳと判定された場合には、ステップＳＴ３７で、ｃｎ とｃｎ−１ の描画属性において、描画スタイル・材質・頂点の定義順序が同じであるかどうかを判定し、ＮＯの場合にはステップＳＴ３８において、ｌｎ ＝４として処理を終了する。
【００１３】
上記ステップＳＴ３７においてＹＥＳと判定された場合には、ステップＳＴ３９で、ｃｎ とｃｎ−１ の描画属性において、両方の形状が同一ファイル上で定義されているかどうかを判定し、ＮＯの場合にはステップＳＴ４０において、ｌｎ ＝５として処理を終了し、ＹＥＳの場合にはステップＳＴ４１において、ｌｎ ＝０として処理を終了する。
【００１４】
次に図２１のステップＳＴ４において、ステップＳＴ３で得られた形状関連情報テーブル７の組で、相違水準が０である組（第ｎ組）が、上の組（第ｎ−１組）と描画属性情報が同一である場合には、形状関連情報テーブルマージ部が、第ｎ組と第ｎ−１組を結合する操作を逐次的に実行する。
【００１５】
ここで、このステップＳＴ４における組の結合操作の処理手順の詳細について、図２３を用いて説明する。ここで、形状関連情報テーブル７の第ｎ組ｃｎ の相違水準の属性値が０で、第ｎ組ｃｎ と第ｎ−１組ｃｎ−１ の描画属性情報ＲＡが同じであるとする。この時、ｃｎ−１ の形状情報ｓｎ−１ に変形情報ｔｎ−１ を作用させたものをｓ’ｎ−１、ｃｎ の形状情報ｓｎ に変形情報ｔｎ を作用させたものをｓ’ｎとすると、形状情報がｓ’ｎ−１＋ｓ’ｎ、変形情報がＮＵＬＬ、描画属性情報がＲＡ、相違水準がｌｎ−１ （ｃｎ−１ の相違水準の属性値）である組を生成し、これをｃｎ−１ 及びｃｎ の結合結果とする。
【００１６】
次に図２１のステップＳＴ５において、木構造生成部４は、結合操作後の形状関連情報テーブル７から、図２４に示すフローチャートに従って、一つの木構造Ｔを生成する。まず図２４のステップＳＴ５１において、図２５に示すような深さ５の中間ノードのみからなる直線状の根付き順序木構造Ｔを生成する。この根付き順序木構造Ｔにおいて、Ｒ１ にはカメラに関する情報がどのファイル上にあるかについての情報が格納され、以下、Ｒ２ には光源・大気効果・光源モデル、Ｒ３ にはテクスチャ、Ｒ４ には描画スタイル・材質・頂点の定義順序、Ｒ５ には形状情報というように、各情報がどのファイル上にあるかについての情報が各々格納されていく。
【００１７】
次にステップＳＴ５２において、組番号を示す変数ＮをＮ＝１に初期設定する。そしてステップＳＴ５３において、Ｎが形状関連情報テーブル７の組の数より大きいかどうかを判定し、大きい場合には処理を終了する。Ｎが形状関連情報テーブル７の組の数以下の場合には、ステップＳＴ５４において、深さｄの直線状の根付き順序木構造ＴＮ を生成する。ここで、深さｄの値は相違水準ｌＮ により次式で与えられる。
ｄ＝０ ｉｆ ｌＮ ＝０
ｄ＝６−ｌＮ ｏｔｈｅｒｗｉｓｅ
【００１８】
次にステップＳＴ５５において、木構造ＴＮ に形状関連情報テーブル７の第Ｎ組の情報を挿入していく。ＴＮ においてＴＮ の中の深さｉの各ノードｓ（ｉ，ＴＮ ）に挿入する情報は、ＴＮ の深さとＴＮ の中の深さｉにより決定される。
次にステップＳＴ５６において、図２６に示すように、ＴＮ の根が、Ｔの深さｄ（ＴＮ ）すなわち図２６では２で、最も右側のノード（深さ優先頂位で最も順位が大きい深さｄ（ＴＮ ）のノード）の最も右側の子となるように、ＴＮ をＴに挿入する。ここで、深さｄ（ＴＮ ）の値は相違水準ｌＮ により次式で与えられる。
ｄ（ＴＮ ）＝５ ｉｆ ｌＮ ＝０
ｄ（ＴＮ ）＝ｌＮ −１ ｏｔｈｅｒｗｉｓｅ
そしてステップＳＴ５７において、Ｎ＝Ｎ＋１とインクリメントして、ステップＳＴ５３へ戻る。
【００１９】
次に図２１のステップＳＴ６において、メッシュ形状生成部５はステップＳＴ５で得られた根付き順序木構造Ｔ内の形状情報をメッシュ化する。そして最後にステップＳＴ７において、冗長情報削除部６は根付き順序木構造Ｔをブラウザと同様に深さ優先探索で走査することで、冗長なノードを検知・除去し出力する。
【００２０】
以上のように、従来の技術における仮想空間データの変換装置は、根付き順序木構造で表現される仮想空間データを変換することで、描画時におけるテクスチャ（描画属性）のスイッチング回数が減少し、ほとんどの場合において変換前に比べ木構造のノード数が減少することにより、また形状をメッシュ化することによりポリゴンの描画速度が向上する。
【００２１】
【発明が解決しようとする課題】
しかし従来の仮想空間データの変換装置は、結合操作により形状の階層構造・独立性が損なわれ、映像情報以外の情報が破壊されるという課題があった。従って、ユーザからのインタラクション（マウスによりあるオブジェクトをクリックする等）に応じてなんらかのアクションを定義しているような仮想空間データに本手法を適用すると、変換後には正常に動作しなくなる。
【００２２】
また、形状情報の位置・大きさに関係なく描画属性が同一のものを一つの形状情報として結合するため、視野領域外のポリゴンについても、それと同じ描画属性情報をもつポリゴンが視野領域内に存在する場合には描画処理される。従って、ほとんどのポリゴンが視野領域外となる広域な仮想空間を表現した木構造の場合には、無駄な描画処理が頻繁に発生し、描画速度が遅くなるという課題があった。
【００２３】
この発明は上記のような課題を解決するためになされたもので、映像情報以外の情報損失が生じることなく、広域な仮想空間を表現したデータに対してもブラウザの描画速度が向上するような木構造を用いた仮想空間データの変換装置を得ることを目的とする。
【００２４】
【課題を解決するための手段】
この発明に係る木構造を用いた仮想空間データの変換装置は、木構造を用いた仮想空間データを入力し、与えられた木構造を、木構造自身に組み込まれた情報を破壊することなく、各木構造が元の木構造の情報の一部を保持している木構造群に分解するシーン木構造分解手段と、上記分解された木構造群に対し、一つの木構造に関する情報を一つの組として記憶する木構造記憶テーブルを生成すると共に、上記各組の形状の領域情報としてバウンディングボックス情報を付加する木構造記憶テーブル生成手段と、上記バウンディングボックス情報をもとに、空間検索に特化した基準木構造を生成する基準木構造生成手段と、上記基準木構造生成手段により生成された基準木構造と上記木構造記憶テーブルに記憶されている木構造群を結合する木構造結合手段とを備えたものである。
【００２５】
この発明に係る木構造を用いた仮想空間データの変換装置は、木構造を用いた仮想空間データを入力し、与えられた木構造を、木構造自身に組み込まれた情報を破壊することなく、各木構造が元の木構造の情報の一部を保持している木構造群に分解するシーン木構造分解手段と、上記分解された木構造群に対し、一つの木構造に関する情報を一つの組として記憶する木構造記憶テーブルを生成すると共に、上記各組の形状の領域情報としてバウンディングボックス情報を付加する木構造記憶テーブル生成手段と、上記木構造記憶テーブルを各組が保持しているテクスチャ情報に応じて少なくとも同じテクスチャを１種類は保持している組が同じテーブル内に存在するように複数のテーブルに分割する木構造記憶テーブル分割手段と、上記分割された木構造記憶テーブルごとに、上記バウンディングボックス情報をもとに、空間検索に特化した基準木構造を生成する基準木構造生成手段と、上記基準木構造生成手段により生成された基準木構造と上記分割された木構造記憶テーブルに記憶されている木構造群を結合する木構造結合手段とを備えたものである。
【００２６】
この発明に係る木構造を用いた仮想空間データの変換装置は、木構造結合手段で生成された木構造内の形状情報をメッシュ化するメッシュ形状生成手段を備えたものである。
【００２７】
この発明に係る木構造を用いた仮想空間データの変換装置は、複数の空間検索に特化した基準木構造を生成する方法を記憶し、記憶されている複数の方法の中から、ユーザの指示により所定の方法を選択する基準木構造生成方法選択手段を備え、基準木構造生成手段が木構造記憶テーブルの各組が管理している形状のバウンディングボックス情報をもとに、上記基準木構造生成方法選択手段が選択した上記所定の空間検索に特化した基準木構造を生成する方法を使用し、空間検索に特化した基準木構造を生成するものである。
【００２８】
この発明に係る木構造を用いた仮想空間データの変換装置は、複数の空間検索に特化した基準木構造を生成する方法を記憶し、記憶されている複数の方法の中から、ユーザの指示により所定の方法を選択する基準木構造生成方法選択手段を備え、基準木構造生成手段が、分割された木構造記憶テーブルごとに、木構造記憶テーブルの各組が管理している形状のバウンディングボックス情報をもとに、上記基準木構造生成方法選択手段が選択した上記所定の空間検索に特化した基準木構造を生成する方法を使用し、空間検索に特化した基準木構造を生成するものである。
【００２９】
この発明に係る木構造を用いた仮想空間データの変換装置は、空間検索に特化した木構造として、２次元空間を複数の小空間に分割し、その小空間内のデータをかためて管理する木構造を用いたものである。
【００３０】
この発明に係る木構造を用いた仮想空間データの変換装置は、空間検索に特化した木構造として、３次元空間を複数の小空間に分割し、その小空間内のデータをかためて管理する木構造を用いたものである。
【００３１】
この発明に係る木構造を用いた仮想空間データの変換装置は、空間検索に特化した木構造として、２次元空間をデータの分布状況に応じて領域分割する木構造を用いたものである。
【００３２】
この発明に係る木構造を用いた仮想空間データの変換装置は、空間検索に特化した木構造として、３次元空間をデータの分布状況に応じて領域分割する木構造を用いたものである。
【００３３】
【発明の実施の形態】
以下、この発明の実施の一形態を説明する。
実施の形態１．
図１はこの発明の実施の形態１における木構造を用いた仮想空間データの変換装置を示すブロック図であり、図において、１０１は与えられた木構造を木構造自身に組み込まれた情報を破壊しないように、各木構造が元の木構造の情報の一部を保持している木構造群に分解するシーン木構造分解部（シーン木構造分解手段）、１０２はシーン木構造分解部１０１で分解された木構造群に対し、一つの木構造に関する情報を一つの組として記憶することにより木構造記憶テーブル１０３を生成する木構造記憶テーブル生成部（木構造記憶テーブル生成手段）である。
【００３４】
また、１０４は木構造記憶テーブル１０３の各組が管理している形状のバウンディングボックス（各組が保持している形状を含む最小の直方体）情報をもとに空間検索に特化した基準木構造を生成する基準木構造生成部（基準木構造生成手段）、１０５は基準木構造と木構造記憶テーブルで記憶されている木構造群を結合することで与えられた木構造と等価な仮想空間を表現した一つの木構造を生成する木構造結合部（木構造結合手段）である。
【００３５】
次に動作について説明する。
図２はこの実施の形態１における木構造を用いた仮想空間データの変換装置の処理手順を示すフローチャートである。まずステップＳＴ１０１において、シーン木構造分解部１０１は、ある仮想空間を表現した木構造が与えられると、木構造自身に組み込まれた情報を破壊しないように、各木構造が元の木構造の情報の一部を保持している木構造に分解する。
【００３６】
ここで、このシーン木構造分解部１０１によるステップＳＴ１０１の処理手順の詳細について、図３のフローチャートを用いて説明する。
まずステップＳＴ１１０１において、処理対象となる木構造を示す変数ＴＰを変換対象となる木構造Ｔに設定し、分解処理の深さを示す変数Ｑの値を０に初期化する。
【００３７】
次にステップＳＴ１１０２において、変数ＴＰがこれ以上分解可能かどうかを判定する。このステップＳＴ１１０２でＮＯと判定されるのは、
イ．ＴＰに形状情報が存在しない、
ロ．ＴＰ内の全ての形状に共通のユーザからの入力に対する動作メカニズムが定義（例えば、ＶＲＭＬにおけるＴｏｕｃｈ Ｓｅｎｓｏｒを利用したアニメーション機能）されている、
ハ．ＴＰの深さが１以下である、
のいずれかの条件が満たされる場合である。
【００３８】
上記ステップＳＴ１１０２でＹＥＳと判定された場合には、ステップＳＴ１１０３において、Ｑ＝Ｑ＋１とする。
そしてステップＳＴ１１０４において、ＴＰの根の子で葉でないものを中間ノードｖｉ （ｉ＝１，２，・・・，ｎ：ｎ＝ＴＰの根の子で葉でないものの個数）とした時に、図４に示すようにＴＰを、
（ａ）ＴＰの根とその子で葉であるもののみからなる木構造ＴＰ（Ｑ，０）
［根に葉が存在する場合のみ］、
（ｂ）ＴＰの根と中間ノードｖｉ とその子孫とからなる木構造ＴＰ（Ｑ，ｉ）
［ｉ＝１，２，・・・，ｎ］、
に分解する。
【００３９】
次にステップＳＴ１１０５において、各ＴＰ（Ｑ，ｉ）［１≦ｉ≦ｎ］に対し、図５に示すように、根から分岐が１であるノード（Ｒｉ （ｉ＝０，１，・・・，ｒ））までを、Ｒｉ が保持しているモデリング変換行列情報をＭｉ ，各Ｍｉ を乗算したモデリング変換行列情報をＭ（Ｍ＝Ｍｒ ×Ｍｒ−１ ×・・・×Ｍ０ ），Ｒ０ の子孫ノードが管理している形状のバウンディングボックスをＢとした時に、モデリング変換行列情報としてＭを有し、バウンディングボックス情報としてＢを有するノードＲに置き換えることで、Ｒｉ （ｉ＝０，１，・・・，ｒ）を情報損失がないように一つのノードＲにまとめる。
【００４０】
次にステップＳＴ１１０６において、深さＱにおける分解処理で生成された木構造の数ＮＮ［Ｑ］を、ＮＮ［Ｑ］＝ｎ＋１とし、深さＱにおける分解処理のインデックスＮＩ［Ｑ］を、ＮＩ［Ｑ］＝０とする。
そしてステップＳＴ１１０７において、ＮＩ［Ｑ］＞ＮＮ［Ｑ］であるかどうか判定する。このステップＳＴ１１０７でＮＯと判定された場合には、ステップＳＴ１１０８でＴＰ＝ＴＰ（Ｑ，ＮＩ［Ｑ］）とし、ステップＳＴ１１０２へ戻る。ＹＥＳと判定された場合には、ステップＳＴ１１０９でＱ＝Ｑ−１とし、ステップＳＴ１１１０でＱ≦０であるかどうかを判定する。
【００４１】
上記ステップＳＴ１１１０でＮＯと判定された場合には、ステップＳＴ１１１１でＮＩ［Ｑ］＝ＮＩ［Ｑ］＋１とし、ステップＳＴ１１０７へ戻り、ＹＥＳと判定された場合には終了する。また、上記ステップＳＴ１１０２でＮＯと判定された場合には、ステップＳＴ１１１２でＴＰを出力し、ステップＳＴ１１１３でＮＩ［Ｑ］＝ＮＩ［Ｑ］＋１としてステップＳＴ１１０７へジャンプする。
【００４２】
次に図２のステップＳＴ１０２において、木構造記憶テーブル生成部１０２は、ステップＳＴ１０１で生成された木構造群ＴＰ（ｉ） （ｉ＝０，１，・・・，ｎ：ｎ＋１＝ステップＳＴ１０１で生成された木構造の個数）に対し、一つの木構造ＴＰ（ｉ） に関する情報を木構造記憶テーブル１０３の一つの組ｃｉ に格納する。次にステップＳＴ１０３において、木構造記憶テーブル１０３に対し、木構造記憶テーブル生成部１０２は領域情報という属性を付加し、バウンディングボックス（各組が保持している形状を包含する最小の直方体）をその組の領域情報の属性値とする。但し、形状情報が存在しない場合には、領域情報はＮＵＬＬとする。
【００４３】
次にステップＳＴ１０４において、図６に示すように、ステップＳＴ１０３で得られた木構造記憶テーブル１０３の組で領域情報がＮＵＬＬでないものをｃｊ 、ｃｊ の領域情報をｒｊ （バウンディングボックス）、ｒｊ のＸＺ平面（Ｘ軸：幅方向、Ｚ軸：奥行き方向）への投影図形をｐｊ とした時に、基準木構造生成部１０４は、ｐｊ （１≦ｊ≦ｎ）を２次元図形の効率的な管理を行う木構造でパケット型であるもの（一つの葉に複数の図形データに関する情報を管理するもの）に逐次投入することで木構造Ｔｂ を生成し、これを基準木構造とする。
【００４４】
なお、２次元図形を効率的に管理する木構造（範囲検索が０（ｌｏｇＮ）となるもの：Ｎ＝データ数）は、例えば、中村泰明他３名による「多次元データの平衡木による管理−ＭＤ木の提案−」（電子情報通信学会論文誌、Ｖｏｌ．Ｊ７１−Ｄ，Ｎｏ．９，１９８８年９月）等に示されている公知のものである。
【００４５】
最後にステップＳＴ１０５において、木構造結合部１０５が、基準木構造Ｔｂ と木構造記憶テーブル１０３で記憶されている木構造群を結合することで与えられた木構造と等価な仮想空間を表現した一つの木構造Ｔｏｐｔ を生成・出力して処理を終了する。
【００４６】
このステップＳＴ１０５において、Ｔｏｐｔ を生成する処理手順の詳細について図７を用いて説明する。
まず、基準木構造Ｔｂ の葉ｌｋ （１≦ｋ≦Ｌ，Ｌ＝Ｔｂ の葉の個数）が保持している２次元図形をｐ（ｋｍ ）（ｍ＝１，２，・・・，Ｍ：Ｍ＝葉ｌｋ が管理している２次元図形の個数）とした時に、ｌｋ をステップＳＴ１０１で生成した木構造Ｔｐ（ｋｍ ）（ｍ＝１，２，・・・，Ｍ）に置き換える。次に、Ｔｂ の葉でないノードを、その全ての子孫ノードが保持している形状情報のバウンディングボックス情報をもったノード（例えば、ＶＲＭＬにおけるＧｒｏｕｐノード）に置き換える。そして最後に、Ｔｂ の根にステップＳＴ１０１で生成した木構造で形状情報を持たないものを追加する。
【００４７】
ブラウザは図８に示すように、根付き順序木構造を深さ優先探索で走査し、ノード到達時に、そのノードの子孫ノードが視野領域内に存在するか否かをノードが保持しているバウンディングボックス情報をもとに判定し、存在しない場合には子孫ノードへの探索は行わない。例えば、図９においてノードＡの子孫ノードへの探索は、視野領域外なので行われないが、ノードＢの子孫ノードへの探索は、視野領域内なので行われる。
【００４８】
以上のように、この実施の形態１によれば、与えられた木構造を、情報損失がないように複数の木構造に分解し、分解した木構造群を走査ノード数が（Ｏ（ｌｏｇＮ）：Ｎは図４で示された分解された木構造の数）となるように再構築するため、映像情報以外の情報を損失することなく描画時に操作するノード数を大幅に減らすことができ、その結果、ブラウザの描画速度が向上するという効果が得られる。
【００４９】
この実施の形態をもとに実際の都市の約１ｋｍ四方のＶＲＭＬファイル（バージョン２．０）を変換したところ、ブラウザ（シリコングラフィックス社：ｃｏｓｍｏｐ１ａｙｅｒ）の描画速度が３〜４倍向上した。
【００５０】
実施の形態２．
図１０はこの発明の実施の形態２による木構造を用いた仮想空間データの変換装置を示すブロック図であり、図１と対応する部分には図１と同一符号を付してその説明を省略する。図１０において、１０６は、木構造記憶テーブル１０３を各組が保持しているテクスチャ情報に応じて、少なくとも同じテクスチャを１種類は保持している組が同じテーブル内に存在するように、複数のテーブルに分割する木構造記憶テーブル分割部（木構造記憶テーブル分割手段）である。
【００５１】
次に動作について説明する。
図１１はこの実施の形態２における木構造を用いた仮想空間データの変換装置の処理手順を示すフローチャートである。まずステップＳＴ１０１及びＳＴ１０２の処理は、実施の形態１の図２におけるステップＳＴ１０１及びＳＴ１０２の処理と同じである。
そしてステップＳＴ２０１において、木構造記憶テーブル分割部１０６は、ステップＳＴ１０２で生成された木構造記憶テーブル１０３を、各組が使用しているテクスチャ情報に応じて複数のテーブルに分割する。
【００５２】
ここでこのステップＳＴ２０１において、木構造記憶テーブル分割部１０６が木構造記憶テーブル１０３を分割する処理手順の詳細について、図１２のフローチャートを用いて説明する。
まずステップＳＴ２１０１において、木構造記憶テーブル１０３内で使用されているテクスチャをテクスチャサイズについて降順にソートしたものをｔｅｘ１ ，ｔｅｘ２ ，・・・，ｔｅｘｑ とする。
次にステップＳＴ２１０２において、テクスチャ番号ＩをＩ＝１に初期設定し、ステップＳＴ２１０３において、木構造記憶テーブル１０３の各組に選択フラグという属性を付加し、全ての組の選択フラグをＦＡＬＳＥに設定する。
【００５３】
次にステップＳＴ２１０４において、木構造記憶テーブル１０３の組でテクスチャｔｅｘＩ を使用しており、選択フラグがＦＡＬＳＥであるものからなるテーブルＴＢＬＩ を作成する。
そしてステップＳＴ２１０５で、上記ステップＳＴ２１０４で選択された組の選択フラグをＴＲＵＥに設定する。
次にステップＳＴ２１０６において、Ｉ＝ｑであるかどうか判定し、ＹＥＳの場合には、ステップＳＴ２１０７で、選択フラグがＦＡＬＳＥである組（即ち、テクスチャを使用していない組）からなるテーブルＴＢＬ０ を作成して処理を終了する。
上記ステップＳＴ２１０６においてＮＯと判定された場合には、ステップＳＴ２１０８でＩ＝Ｉ＋１とインクリメントして、ステップＳＴ２１０４へ戻る。
【００５４】
次に図１１のステップＳＴ２０２において、基準木構造生成部１０４は、各ＴＢＬｊ ごとに実施の形態１の手順に従ってＴＢＬｊ に対応した仮想空間を表現した木構造Ｔｏｐｔ（ｊ）を生成する。
そしてステップＳＴ２０３において、図１３に示すように、木構造結合部１０５がＴｏｐｔ（０），Ｔｏｐｔ（１），・・・Ｔｏｐｔ（ｑ）を結合して一つの木構造Ｔｏｐｔ を生成・出力して処理を終了する。
【００５５】
以上のように、この実施の形態２によれば、同じテクスチャを持っているテーブルをソートしているので、実施の形態１に比べ描画時におけるテクスチャ（描画属性）のスイッチング回数を減少させることができ、ブラウザの描画速度を向上させることができるという効果が得られる。
【００５６】
実施の形態３．
図１４はこの発明の実施の形態３による木構造を用いた仮想空間データの変換装置を示すブロック図であり、図１０と対応する部分には図１０と同一符号を付してその説明を省略する。図１４において、１０７は木構造結合部１０５で生成した木構造内の形状情報をメッシュ化するメッシュ形状生成部（メッシュ形状生成手段）である。
【００５７】
次に動作について説明する。
図１５はこの実施の形態３における木構造を用いた仮想空間データの変換装置の処理手順を示すフローチャートである。この実施の形態では、上記実施の形態２において、ステップＳＴ２０３で生成した木構造Ｔｏｐｔ 内の各形状情報を、ステップＳＴ３０１において、メッシュ形状生成部１０７がメッシュ化するようにしたものである。
【００５８】
以上のように、この実施の形態３によれば、形状をメッシュ化することでグラフィックスエンジンの描画コストが軽減するように与えられた木構造と等価な仮想空間を表現した木構造を生成することができ、ブラウザの描画速度を向上させることができるという効果が得られる。
【００５９】
この実施の形態３では、実施の形態２にメッシュ形状生成部１０７を追加しているが、実施の形態１にメッシュ形状生成部１０７を追加しても、同様の効果が得られる。
【００６０】
実施の形態４．
図１６はこの発明の実施の形態４による木構造を用いた仮想空間データの変換装置を示すブロック図であり、図１と対応する部分には図１と同一符号を付してその説明を省略する。図１６において、１０８は空間検索に特化した木構造を生成する方法を複数種類記憶しておき、基準木構造生成部１０４において空間検索に特化した木構造を生成する際の木構造を、ユーザの指示により選択する基準木構造生成方法選択部（基準木構造生成方法選択手段）である。
【００６１】
次に動作について説明する。
図１７はこの実施の形態４における木構造を用いた仮想空間データの変換装置の処理手順を示すフローチャートである。この実施の形態におけるステップＳＴ１０１からＳＴ１０３までの処理は、上記実施の形態１の図２におけるステップＳＴ１０１からＳＴ１０３までの処理と同じである。
ステップＳＴ４０１において、基準木構造生成方法選択部１０８が、あらかじめ用意しておいた空間検索に特化した木構造の中からユーザの指示により木構造を選択する。
そしてステップＳＴ１０４において、基準木構造生成部１０４が、選択された木構造を用いて基準木構造を生成する。ステップＳＴ１０５の処理は実施の形態１と同様である。
【００６２】
空間検索に特化した木構造としては、実施の形態１で用いた２次元図形を効率的に管理する木構造の他に、３次元空間を効率的に管理する木構造（例えばｏｃｔｒｅｅ、文献：Ｃ．Ｌ．Ｊａｃｋｉｎｓ ａｎｄ Ｓ．Ｌ．Ｔａｎｉｍｏｎｏ，“Ｏｃｔ−Ｔｒｅｅｓ ａｎｄ Ｔｈｅｉｒ Ｕｓｅ ｉｎ Ｒｅｐｒｅｓｅｎｔｉｎｇ Ｔｈｒｅｅ−Ｄｉｍｅｎｓｉｏｎａｌ Ｏｂｊｅｃｔｓ”，Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ａｎｄ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，Ｎｏｖ．１９８０，ｐｐ．２４９−２７０）がある。変換対象となる仮想空間データが都市空間のように、平面方向（ＸＹ平面）の広がりに比べ、高さ方向（Ｚ軸）の広がりが非常に小さいような空間である場合には、空間を２次元的に管理する方が効率的である。
【００６３】
一方、大規模な分子モデルや科学シミュレーション結果の３次元視覚化データのように、高さ方向についても平面方向と同程度の広がりを持つ仮想空間データについては、３次元的に管理する方が効率的であり、変換対象となる仮想空間データの空間特性に応じてユーザが基準木構造を生成する際に使用する木構造を選択する方が、実施の形態１に比べ、よりブラウザの描画速度が向上する木構造を生成することができる。
【００６４】
この実施の形態４では、実施の形態１に基準木構造生成方法選択部１０８を追加しているが、実施の形態２に基準木構造生成方法選択部１０８を追加しても、同様の効果が得られる。
【００６５】
実施の形態５．
この発明の実施の形態５では、上記実施の形態１から実施の形態４において空間検索に特化した木構造として、２次元空間を複数の小空間に分割し、その小空間内のデータをかためて管理する木構造を用いることで、図１８に示すように仮想空間を管理するものである。
【００６６】
この実施の形態では木構造の実装が容易であり、また仮想空間内において３次元形状が均等に分布し、かつ仮想空間の高さ方向の広がりが非常に小さい場合には実施の形態１で用いた２次元図形を効率的に管理する木構造（範囲検索、すなわち走査ノード数が０（ｌｏｇＮ））と同等の検索効率を実現することができるという効果が得られる。
【００６７】
実施の形態６．
この発明の実施の形態６では、上記実施の形態１から実施の形態４において空間検索に特化した木構造として、３次元空間を複数の小空間に分割し、その小空間内のデータをかためて管理する木構造を用いることで、図１９に示すように仮想空間を管理するものである。
【００６８】
この実施の形態でも木構造の実装が容易であり、また仮想空間内において３次元形状が均等に分布する場合には実施の形態４で用いた３次元図形を効率的に管理する木構造（範囲検索、すなわち走査ノード数が０（ｌｏｇＮ））と同等の検索効率を実現することができるという効果が得られる。
【００６９】
実施の形態７．
この発明の実施の形態７では、上記実施の形態４において空間検索に特化した木構造として、２次元空間をデータの分布状況に応じて領域分割することで、動的なデータに対しても静的なデータに対しても、ともに良好な領域分割を実現する木構造を複数用意するものである。これら木構造として、実施の形態１で用いた木構造の他に、例えば、大沢、坂内：「良好な動特性を持つ多次元データ管理構造の一提案」（電子情報通信学会論文誌、Ｖｏｌ．Ｊ６６−Ｄ、Ｎｏ．１０、１９８３）等があり、これら木構造には、実装の容易さ、検索効率、木の生成時間等でそれぞれ特徴があることから、複数用意することで目的に応じて最適な木構造を選択することができる。
【００７０】
実施の形態８．
この発明の実施の形態８では、上記実施の形態４において空間検索に特化した木構造として、３次元空間をデータの分布状況に応じて領域分割することで、動的なデータに対しても静的なデータに対しても、ともに良好な領域分割を実現する木構造を複数用意するものである。これら木構造として、実施の形態４で用いた木構造の他に、“Ｊａｎｓｅｎ、Ｆ．，Ｄａｔａ Ｓｔｒｕｃｔｕｒｅｓ ｆｏｒ Ｒａｙ Ｔｒａｃｉｎｇ、Ｄａｔａ Ｓｔｒｕｃｔｕｒｅｓ ｆｏｒ Ｒａｓｔｅｒ Ｇｒａｐｈｉｃｓ、ｐ５７−７３、１９８６”等があり、これら木構造には、実装の容易さ、検索効率、木の生成時間等でそれぞれ特徴があることから、複数用意することで目的に応じて最適な木構造を選択することができる。
【００７１】
【発明の効果】
以上のように、この発明によれば、情報損失を生じることなく、描画時に操作するノード数を大幅に減らすことができるので、ブラウザの描画速度が向上する効果がある。
【００７２】
また、この発明によれば、同じテクスチャを持っているテーブルをソートしているので、描画時におけるテクスチャ（描画属性）のスイッチング回数を減少させることができ、ブラウザの描画速度を向上させることができる効果がある。
【図面の簡単な説明】
【図１】この発明の実施の形態１による木構造を用いた仮想空間データの変換装置を示すブロック図である。
【図２】この発明の実施の形態１による処理手順を示すフローチャートである。
【図３】木構造分解の処理手順を示すフローチャートである。
【図４】木構造分解の説明図である。
【図５】ノード結合の説明図である。
【図６】３次元形状と領域情報・投影図形の関係についての説明図である。
【図７】基準木構造からシーン木構造への変換の説明図である。
【図８】描画時におけるブラウザのノード走査手順の説明図である。
【図９】ノード走査とバウンディングボックスの関係の説明図である。
【図１０】この発明の実施の形態２による木構造を用いた仮想空間データの変換装置を示すブロック図である。
【図１１】この発明の実施の形態２による処理手順を示すフローチャートである。
【図１２】木構造記憶テーブル分割の処理手順を示すフローチャートである。
【図１３】Ｔｏｐｔ （０），Ｔｏｐｔ （１），・・・Ｔｏｐｔ （ｑ）からＴｏｐｔ 生成の説明図である。
【図１４】この発明の実施の形態３による木構造を用いた仮想空間データの変換装置を示すブロック図である。
【図１５】この発明の実施の形態３による処理手順を示すフローチャートである。
【図１６】この発明の実施の形態４による木構造を用いた仮想空間データの変換装置を示すブロック図である。
【図１７】この発明の実施の形態４による処理手順を示すフローチャートである。
【図１８】２次元空間を複数の小空間に分割し、その小空間内のデータをかためて管理する木構造による仮想空間管理の説明図である。
【図１９】３次元空間を複数の小空間に分割し、その小空間内のデータをかためて管理する木構造による仮想空間管理の説明図である。
【図２０】従来の木構造を用いた仮想空間データの変換装置を示すブロック図である。
【図２１】従来の処理手順を示すフローチャートである。
【図２２】従来の相違水準決定手順を示すフローチャートである。
【図２３】従来の形状関連情報テーブルの結合操作手順の説明図である。
【図２４】従来の形状関連情報テーブルから木構造を生成する処理手順を示すフローチャートである。
【図２５】従来における深さ５の直線上の木構造の説明図である。
【図２６】従来における木構造の生成手順の説明図である。
【符号の説明】
１０１ シーン木構造分解部（シーン木構造分解手段）、１０２ 木構造記憶テーブル生成部（木構造記憶テーブル生成手段）、１０３ 木構造記憶テーブル、１０４ 基準木構造生成部（基準木構造生成手段）、１０５ 木構造結合部（木構造結合手段）、１０６ 木構造記憶テーブル分割部（木構造記憶テーブル分割手段）、１０７ メッシュ形状生成部（メッシュ形状生成手段）、１０８ 基準木構造生成方法選択部（基準木構造生成方法選択手段）。[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to an apparatus for converting virtual space data using a tree structure, and more particularly to improving the drawing speed of a browser.
[0002]
[Prior art]
Each intermediate node has at least one of modeling transformation matrix and bounding box information, and each leaf node has at least one of shape (polygon), texture, event handling, lighting, and color information An example of virtual space data represented by a rooted ordered tree structure is VRML (Virtual Reality Modeling Language, literature: for example, Kenjiro Miura, published by Asakura Shoten, VRML 2.0: 3D cyberspace construction language).
[0003]
VRML is a language developed to realize an environment in which a virtual space is disclosed and shared on the Internet. The above environment is realized by exchanging VRML files via the Internet, and drawing software (browser) dedicated to this data to draw a video from an arbitrary viewpoint while scanning a given tree structure in a depth-first search. You.
[0004]
There are countless expression methods for creating VRML data corresponding to a certain virtual space. In general, the smaller the number of nodes scanned by the browser and the number of switching of textures (drawing attributes) during drawing, The rendering speed of the browser is improved as the polygons are expressed in a mesh (a geometric figure composed of adjacent triangles). Therefore, if there is VRML data corresponding to a certain virtual space, if the VRML data can be converted so as to satisfy the above conditions without destroying various information related to the virtual space incorporated in the data, the same VRML data that renders the virtual space at a higher speed can be created.
[0005]
As a conventional method for automatically performing the conversion, there is software called ivfix (manufactured by Silicon Graphics). The ivfix converts data into virtual space data expressed in a rooted ordered tree structure described in the Open Inventor file format, which is the base of VRML, so as to improve the drawing speed of the browser.
[0006]
FIG. 20 is a block diagram showing a virtual space data conversion apparatus according to a conventional technique. In the figure,
[0007]
Next, the operation will be described with reference to FIGS.
FIG. 21 is a flowchart showing a processing procedure in the related art. First, in step ST1, the shape-related information
[0008]
Next, in step ST2, the shape-related information
[0009]
Here, in step ST3, the shape-related information
[0010]
If YES is determined in the step ST31, in step ST33, c n And c n-1 It is determined whether or not the light source, the atmospheric effect, and the light source model are the same in the drawing attribute of, and if NO, at step ST34, n = 2 and the process ends.
[0011]
If YES is determined in step ST33, then in step ST35, c n And c n-1 It is determined whether or not the textures are the same in the drawing attribute of. n = 3 and the process ends.
[0012]
If it is determined YES in step ST35, c in step ST37 n And c n-1 It is determined whether or not the definition order of the drawing style, the material, and the vertex is the same in the drawing attribute of “No.”. n = 4 and the process ends.
[0013]
If YES is determined in the above step ST37, c is determined in step ST39. n And c n-1 It is determined whether or not both shapes are defined on the same file in the drawing attribute of “1”. n = 5 and ends the processing. In the case of YES, in step ST41, l n = 0 and the process ends.
[0014]
Next, in step ST4 of FIG. 21, in the set of the shape-related information table 7 obtained in step ST3, the set having the difference level of 0 (the n-th set) is drawn with the upper set (the n-1st set). When the attribute information is the same, the shape-related information table merging unit sequentially executes an operation of combining the n-th set and the (n-1) -th set.
[0015]
Here, the details of the processing procedure of the set combination operation in step ST4 will be described with reference to FIG. Here, the n-th set c of the shape-related information table 7 n The attribute value of the difference level is 0, and the n-th set c n And the (n-1) th set c n-1 Are assumed to have the same drawing attribute information RA. At this time, c n-1 Shape information s n-1 To the deformation information t n-1 S ' n-1 , C n Shape information s n To the deformation information t n S ' n Then the shape information is s' n-1 + S ' n , Deformation information is NULL, drawing attribute information is RA, and difference level is l n-1 (C n-1 Is generated, and this is represented by c n-1 And c n Is the result of combining.
[0016]
Next, in step ST5 of FIG. 21, the tree
[0017]
Next, in step ST52, a variable N indicating the set number is initialized to N = 1. Then, in step ST53, it is determined whether or not N is larger than the number of sets in the shape-related information table 7, and if it is larger, the process ends. If N is equal to or less than the number of sets in the shape-related information table 7, in step ST54, a linear rooted ordered tree structure T having a depth d is set. N Generate Here, the value of the depth d is the difference level l N Is given by the following equation.
d = 0 if l N = 0
d = 6-1 N otherwise
[0018]
Next, in step ST55, the tree structure T N Into the N-th set of information of the shape-related information table 7. T N At T N Each node s (i, T N ) Is T N Depth and T N Is determined by the depth i.
Next, in step ST56, as shown in FIG. N Is the depth d of T (T N 26, that is, in FIG. 26, the rightmost node (depth d (T N ) To be the rightmost child of node) N Into T. Here, the depth d (T N ) Is the difference level l N Is given by the following equation.
d (T N ) = 5 if l N = 0
d (T N ) = L N -1 otherwise
Then, in step ST57, N = N + 1 is incremented, and the process returns to step ST53.
[0019]
Next, in step ST6 of FIG. 21, the mesh
[0020]
As described above, the virtual space data conversion device according to the related art converts virtual space data expressed by a rooted ordered tree structure, thereby reducing the number of times of switching of textures (drawing attributes) at the time of drawing. In the case of (1), the number of nodes in the tree structure is reduced as compared with before conversion, and the meshing of the shape improves the polygon drawing speed.
[0021]
[Problems to be solved by the invention]
However, the conventional virtual space data conversion apparatus has a problem that the hierarchical structure and independence of the shape are impaired by the joining operation, and information other than the video information is destroyed. Therefore, if this method is applied to virtual space data in which some action is defined in response to an interaction from the user (such as clicking a certain object with a mouse), it will not operate properly after conversion.
[0022]
In addition, polygons having the same drawing attribute are combined as one shape information regardless of the position and size of the shape information. If so, a drawing process is performed. Therefore, in the case of a tree structure expressing a wide virtual space in which most polygons are outside the viewing area, there is a problem that useless drawing processing frequently occurs and the drawing speed is reduced.
[0023]
SUMMARY OF THE INVENTION The present invention has been made to solve the above-described problems, and does not cause loss of information other than video information and improves the drawing speed of a browser even for data representing a wide virtual space. It is an object to obtain a virtual space data conversion device using a tree structure.
[0024]
[Means for Solving the Problems]
A virtual space data conversion device using a tree structure according to the present invention receives virtual space data using a tree structure and converts a given tree structure into pieces without destroying information incorporated in the tree structure itself. A scene tree structure decomposing means for decomposing each tree structure into a group of tree structures holding a part of the information of the original tree structure; Tree structure storage table generating means for generating a tree structure storage table to be stored as a set and adding bounding box information as area information of the shape of each set, and specializing in spatial search based on the bounding box information Reference tree structure generating means for generating a reference tree structure, and combining the reference tree structure generated by the reference tree structure generating means with a tree structure group stored in the tree structure storage table. Those having a structure coupling means.
[0025]
A virtual space data conversion device using a tree structure according to the present invention receives virtual space data using a tree structure and converts a given tree structure into pieces without destroying information incorporated in the tree structure itself. A scene tree structure decomposing means for decomposing each tree structure into a group of tree structures holding a part of the information of the original tree structure; A tree structure storage table generating means for generating a tree structure storage table to be stored as a set and adding bounding box information as area information of the shape of each set, and a texture holding each of the tree structure storage tables Tree structure storage table dividing means for dividing the table into a plurality of tables so that a set holding at least one type of the same texture exists in the same table in accordance with the information; A reference tree structure generating means for generating a reference tree structure specialized for spatial search, based on the bounding box information, for each of the extracted tree structure storage tables; and a reference tree structure generated by the reference tree structure generating means. And tree structure combining means for combining the tree structure groups stored in the divided tree structure storage table.
[0026]
An apparatus for converting virtual space data using a tree structure according to the present invention includes mesh shape generation means for meshing shape information in the tree structure generated by the tree structure connection means.
[0027]
An apparatus for converting virtual space data using a tree structure according to the present invention stores a method for generating a reference tree structure specialized for a plurality of spatial searches, and specifies a user's instruction from among the plurality of stored methods. And a reference tree structure generation method selecting means for selecting a predetermined method according to the reference tree structure generation means based on the bounding box information of the shape managed by each set of the tree structure storage table. A method for generating a reference tree structure specialized for spatial search using a method for generating a reference tree structure specialized for the predetermined space search selected by the method selecting means.
[0028]
An apparatus for converting virtual space data using a tree structure according to the present invention stores a method for generating a reference tree structure specialized for a plurality of spatial searches, and specifies a user's instruction from among the plurality of stored methods. And a reference tree structure generation method selecting means for selecting a predetermined method according to the following. The reference tree structure generation means outputs, for each divided tree structure storage table, a bounding box of a shape managed by each set of the tree structure storage tables. Generating a reference tree structure specialized in spatial search using a method of generating a reference tree structure specialized in the predetermined spatial search selected by the reference tree structure generation method selecting means based on information; It is.
[0029]
A virtual space data conversion apparatus using a tree structure according to the present invention divides a two-dimensional space into a plurality of small spaces as a tree structure specialized for space search, and manages data in the small spaces. It uses a tree structure.
[0030]
A virtual space data conversion device using a tree structure according to the present invention divides a three-dimensional space into a plurality of small spaces and manages the data in the small spaces as a tree structure specialized for space search. It uses a tree structure.
[0031]
An apparatus for converting virtual space data using a tree structure according to the present invention uses a tree structure that divides a two-dimensional space into regions according to the distribution state of data as a tree structure specialized for space search.
[0032]
An apparatus for converting virtual space data using a tree structure according to the present invention uses a tree structure that divides a three-dimensional space into regions according to the distribution state of data as a tree structure specialized for space search.
[0033]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, an embodiment of the present invention will be described.
FIG. 1 is a block diagram showing an apparatus for converting virtual space data using a tree structure according to
[0034]
[0035]
Next, the operation will be described.
FIG. 2 is a flowchart showing a processing procedure of the virtual space data conversion device using the tree structure in the first embodiment. First, in step ST101, given a tree structure representing a certain virtual space, the scene tree structure decomposition unit 101 converts each tree structure into information of the original tree structure so as not to destroy information incorporated in the tree structure itself. Decomposes into a tree structure that holds a portion of the
[0036]
Here, the processing procedure of step ST101 by the scene tree structure decomposition section 101 will be described in detail with reference to the flowchart of FIG.
First, in step ST1101, a variable TP indicating a tree structure to be processed is set to a tree structure T to be converted, and a value of a variable Q indicating the depth of the decomposition process is initialized to zero.
[0037]
Next, in step ST1102, it is determined whether or not the variable TP can be further decomposed. The reason for determining NO in step ST1102 is that
I. There is no shape information in TP,
B. An operation mechanism for an input from a user common to all the shapes in the TP is defined (for example, an animation function using a Touch Sensor in VRML).
C. The depth of the TP is 1 or less,
Is satisfied.
[0038]
If YES is determined in step ST1102, Q = Q + 1 is set in step ST1103.
Then, in step ST1104, a root child of the TP which is not a leaf is set to the intermediate node v i (I = 1, 2,..., N: n = the number of non-leaf root children of TP), as shown in FIG.
(A) Tree structure TP (Q, 0) consisting of only the roots of TP and their offspring that are leaves
[Only when there is a leaf in the root],
(B) Root of TP and intermediate node v i Tree structure TP (Q, i) consisting of and its descendants
[I = 1, 2,..., N],
Decompose into
[0039]
Next, in step ST1105, for each TP (Q, i) [1 ≦ i ≦ n], as shown in FIG. 5, the node (R i (I = 0, 1,..., R)) i The modeling transformation matrix information held by i , Each M i Is multiplied by the modeling transformation matrix information into M (M = M r × M r-1 × ・ ・ ・ × M 0 ), R 0 When the bounding box of the shape managed by the descendant nodes of B is B, the node is replaced with a node R having M as the modeling transformation matrix information and B as the bounding box information. i (I = 0, 1,..., R) are combined into one node R so that there is no information loss.
[0040]
Next, in step ST1106, the number NN [Q] of tree structures generated in the decomposition processing at the depth Q is set to NN [Q] = n + 1, and the index NI [Q] of the decomposition processing at the depth Q is set to NI [Q]. Q] = 0.
Then, in step ST1107, it is determined whether or not NI [Q]> NN [Q]. If NO is determined in this step ST1107, TP = TP (Q, NI [Q]) is set in step ST1108, and the process returns to step ST1102. If it is determined as YES, Q = Q−1 is set in step ST1109, and it is determined whether or not Q ≦ 0 in step ST1110.
[0041]
If NO is determined in step ST1110, NI [Q] = NI [Q] +1 is set in step ST1111 and the process returns to step ST1107. If YES is determined, the process ends. If NO is determined in step ST1102, TP is output in step ST1112, and in step ST1113, the process jumps to step ST1107 with NI [Q] = NI [Q] +1.
[0042]
Next, in step ST102 of FIG. 2, the tree structure storage
[0043]
Next, in step ST104, as shown in FIG. 6, a set of tree structure storage tables 103 obtained in step ST103 whose area information is not NULL is set to c. j , C j Area information of r j (Bounding box), r j Is the projected figure on the XZ plane (X axis: width direction, Z axis: depth direction) j , The reference tree structure generation unit 104 j (1 ≦ j ≦ n) is sequentially input to a packet-type tree structure that manages two-dimensional figures efficiently (one that manages information related to a plurality of graphic data in one leaf). T b Is generated, and this is set as a reference tree structure.
[0044]
Note that a tree structure for efficiently managing two-dimensional figures (a range search is 0 (logN): N = number of data) is described in, for example, “Management of Multidimensional Data Using Balanced Tree-MD by Yasuaki Nakamura et al. Tree Proposal— ”(Transactions of the Institute of Electronics, Information and Communication Engineers, Vol. J71-D, No. 9, September 1988) and the like.
[0045]
Finally, in step ST105, the tree
[0046]
In this step ST105, T opt The details of the processing procedure for generating the data will be described with reference to FIG.
First, the reference tree structure T b Leaf l k (1 ≦ k ≦ L, L = T b The two-dimensional figure held by the number of leaves m ) (M = 1, 2,..., M: M = leaf l) k Is the number of two-dimensional figures managed by k To the tree structure Tp (k) generated in step ST101 m ) (M = 1, 2,..., M). Next, T b Is replaced by a node having the bounding box information of the shape information held by all its descendant nodes (for example, a Group node in VRML). And finally, T b Of the tree structure generated in step ST101 and having no shape information is added to the root of.
[0047]
As shown in FIG. 8, the browser scans the rooted ordered tree structure by the depth-first search, and when the node arrives, the bounding box holding whether or not a descendant node of the node exists in the view area. Judgment is made based on the information, and if it does not exist, search for descendant nodes is not performed. For example, in FIG. 9, the search for the descendant node of the node A is not performed because it is outside the visual field area, but the search for the descendant node of the node B is performed because it is within the visual field area.
[0048]
As described above, according to the first embodiment, a given tree structure is decomposed into a plurality of tree structures so that information loss does not occur, and the decomposed tree structure group has a scan node count of (O (logN) : N is the number of decomposed tree structures shown in FIG. 4), so that the number of nodes operated at the time of drawing can be greatly reduced without losing information other than video information, As a result, the effect that the drawing speed of the browser is improved can be obtained.
[0049]
When a VRML file (version 2.0) of about 1 km square of an actual city was converted based on this embodiment, the drawing speed of the browser (Silicon Graphics: cosmoplayer) was improved 3 to 4 times.
[0050]
FIG. 10 is a block diagram showing an apparatus for converting virtual space data using a tree structure according to a second embodiment of the present invention. Parts corresponding to those in FIG. 1 are denoted by the same reference numerals as in FIG. I do. In FIG. 10,
[0051]
Next, the operation will be described.
FIG. 11 is a flowchart showing a processing procedure of the virtual space data conversion device using the tree structure according to the second embodiment. First, the processing of steps ST101 and ST102 is the same as the processing of steps ST101 and ST102 in FIG. 2 of the first embodiment.
Then, in step ST201, the tree structure storage
[0052]
Here, the details of the processing procedure in which the tree structure storage
First, in step ST2101, textures used in the tree structure storage table 103 are sorted in descending order of texture size into tex. 1 , Tex 2 , ..., tex q And
Next, in step ST2102, the texture number I is initially set to I = 1, and in step ST2103, an attribute called a selection flag is added to each set of the tree structure storage table 103, and the selection flags of all sets are set to FALSE. .
[0053]
Next, in step ST2104, the texture tex is stored in the set of the tree structure storage table 103. I And the selection flag is set to FALSE. I Create
Then, in step ST2105, the selection flag of the set selected in step ST2104 is set to TRUE.
Next, in step ST2106, it is determined whether or not I = q, and in the case of YES, in step ST2107, a table TBL including a pair whose selection flag is FALSE (that is, a pair not using a texture). 0 Is created, and the process ends.
If NO is determined in step ST2106, I = I + 1 is incremented in step ST2108, and the process returns to step ST2104.
[0054]
Next, in step ST202 of FIG. 11, the reference tree
Then, in step ST203, as shown in FIG. opt (0), T opt (1), ... T opt (Q) to form one tree structure T opt Is generated and output, and the process ends.
[0055]
As described above, according to the second embodiment, since the tables having the same texture are sorted, the number of switching of the texture (drawing attribute) at the time of drawing can be reduced as compared with the first embodiment. Thus, the effect that the drawing speed of the browser can be improved can be obtained.
[0056]
FIG. 14 is a block diagram showing an apparatus for converting virtual space data using a tree structure according to a third embodiment of the present invention. Parts corresponding to those in FIG. 10 are denoted by the same reference numerals as in FIG. I do. In FIG. 14,
[0057]
Next, the operation will be described.
FIG. 15 is a flowchart showing a processing procedure of the virtual space data conversion device using the tree structure according to the third embodiment. In this embodiment, the tree structure T generated in step ST203 in the second embodiment is used. opt In step ST301, the mesh
[0058]
As described above, according to the third embodiment, a tree structure representing a virtual space equivalent to a given tree structure is generated by meshing the shape to reduce the drawing cost of the graphics engine. And the drawing speed of the browser can be improved.
[0059]
In the third embodiment, the mesh
[0060]
FIG. 16 is a block diagram showing a virtual space data conversion apparatus using a tree structure according to a fourth embodiment of the present invention. Parts corresponding to those in FIG. 1 are denoted by the same reference numerals as in FIG. I do. In FIG. 16,
[0061]
Next, the operation will be described.
FIG. 17 is a flowchart showing a processing procedure of the virtual space data conversion device using the tree structure according to the fourth embodiment. The processing of steps ST101 to ST103 in this embodiment is the same as the processing of steps ST101 to ST103 in FIG. 2 of the first embodiment.
In step ST401, the reference tree structure generation
Then, in step ST104, the reference tree
[0062]
As a tree structure specialized for spatial search, in addition to the tree structure for efficiently managing two-dimensional figures used in
[0063]
On the other hand, it is more efficient to manage three-dimensional virtual space data, such as large-scale molecular models and three-dimensional visualization data of scientific simulation results, in which the height direction is almost the same as the plane direction. Therefore, when the user selects a tree structure to be used when generating the reference tree structure according to the spatial characteristics of the virtual space data to be converted, the rendering speed of the browser is higher than in the first embodiment. An improved tree structure can be generated.
[0064]
In the fourth embodiment, the reference tree structure generation
[0065]
In a fifth embodiment of the present invention, a two-dimensional space is divided into a plurality of small spaces as a tree structure specialized for space search in the first to fourth embodiments, and data in the small space is divided into a plurality of small spaces. By using a tree structure to be managed, virtual space is managed as shown in FIG.
[0066]
In this embodiment, it is easy to mount a tree structure, and when the three-dimensional shape is evenly distributed in the virtual space and the spread of the virtual space in the height direction is very small, it is used in the first embodiment. An effect is obtained that a search efficiency equivalent to a tree structure (range search, that is, the number of scan nodes is 0 (logN)) that efficiently manages the existing two-dimensional figure can be realized.
[0067]
According to the sixth embodiment of the present invention, a three-dimensional space is divided into a plurality of small spaces as a tree structure specialized for space search in the first to fourth embodiments, and data in the small space is divided. By using a tree structure to be managed, virtual space is managed as shown in FIG.
[0068]
Also in this embodiment, the tree structure is easy to implement, and when the three-dimensional shapes are evenly distributed in the virtual space, the tree structure (range) for efficiently managing the three-dimensional figures used in the fourth embodiment The effect that the search, that is, the search efficiency equivalent to the number of scan nodes of 0 (logN) can be realized is obtained.
[0069]
In the seventh embodiment of the present invention, a two-dimensional space is divided into regions according to the distribution state of data as a tree structure specialized for space search in the fourth embodiment, so that dynamic data can be obtained. A plurality of tree structures that realize good area division for static data are prepared. As these tree structures, besides the tree structure used in the first embodiment, for example, Osawa and Sakauchi: “A proposal of a multidimensional data management structure having good dynamic characteristics” (Transactions of the Institute of Electronics, Information and Communication Engineers, Vol. J66-D, No. 10, 1983), and these tree structures are characterized by ease of implementation, search efficiency, tree generation time, and the like. An optimal tree structure can be selected.
[0070]
Embodiment 8 FIG.
In the eighth embodiment of the present invention, a three-dimensional space is divided into regions according to the distribution state of data as a tree structure specialized for space search in the fourth embodiment, so that dynamic data can be obtained. A plurality of tree structures that realize good area division for static data are prepared. As these tree structures, in addition to the tree structures used in the fourth embodiment, there are "Jansen, F., Data Structures for Ray Tracing, Data Structures for Raster Graphics, p57-73, 1986" and the like. Has characteristics in terms of ease of implementation, search efficiency, tree generation time, and the like. Therefore, by preparing a plurality of such, an optimal tree structure can be selected according to the purpose.
[0071]
【The invention's effect】
As described above, according to the present invention, it is possible to greatly reduce the number of nodes operated at the time of drawing without causing information loss, so that there is an effect that the drawing speed of the browser is improved.
[0072]
Further, according to the present invention, since the tables having the same texture are sorted, the number of switching of the texture (drawing attribute) at the time of drawing can be reduced, and the drawing speed of the browser can be improved. effective.
[Brief description of the drawings]
FIG. 1 is a block diagram showing an apparatus for converting virtual space data using a tree structure according to a first embodiment of the present invention.
FIG. 2 is a flowchart showing a processing procedure according to the first embodiment of the present invention.
FIG. 3 is a flowchart illustrating a processing procedure of tree structure decomposition.
FIG. 4 is an explanatory diagram of a tree structure decomposition.
FIG. 5 is an explanatory diagram of node connection.
FIG. 6 is an explanatory diagram of a relationship between a three-dimensional shape and area information / projected figure.
FIG. 7 is an explanatory diagram of conversion from a reference tree structure to a scene tree structure.
FIG. 8 is an explanatory diagram of a browser node scanning procedure at the time of drawing.
FIG. 9 is an explanatory diagram of a relationship between node scanning and a bounding box.
FIG. 10 is a block diagram showing an apparatus for converting virtual space data using a tree structure according to a second embodiment of the present invention;
FIG. 11 is a flowchart showing a processing procedure according to the second embodiment of the present invention.
FIG. 12 is a flowchart illustrating a processing procedure for dividing a tree structure storage table.
FIG. 13 opt (0), T opt (1), ... T opt (Q) to T opt It is explanatory drawing of generation.
FIG. 14 is a block diagram showing a virtual space data conversion device using a tree structure according to a third embodiment of the present invention.
FIG. 15 is a flowchart showing a processing procedure according to the third embodiment of the present invention.
FIG. 16 is a block diagram showing an apparatus for converting virtual space data using a tree structure according to a fourth embodiment of the present invention.
FIG. 17 is a flowchart showing a processing procedure according to the fourth embodiment of the present invention.
FIG. 18 is an explanatory diagram of virtual space management using a tree structure that divides a two-dimensional space into a plurality of small spaces and manages the data in the small spaces by preserving them.
FIG. 19 is an explanatory diagram of virtual space management using a tree structure that divides a three-dimensional space into a plurality of small spaces and manages the data in the small spaces by preserving them.
FIG. 20 is a block diagram showing a conventional virtual space data conversion device using a tree structure.
FIG. 21 is a flowchart showing a conventional processing procedure.
FIG. 22 is a flowchart showing a conventional difference level determination procedure.
FIG. 23 is an explanatory diagram of a conventional joining operation procedure of a shape-related information table.
FIG. 24 is a flowchart showing a processing procedure for generating a tree structure from a conventional shape-related information table.
FIG. 25 is an explanatory diagram of a conventional tree structure on a straight line having a depth of 5;
FIG. 26 is an explanatory diagram of a conventional tree structure generation procedure.
[Explanation of symbols]
101 scene tree structure decomposition unit (scene tree structure decomposition unit), 102 tree structure storage table generation unit (tree structure storage table generation unit), 103 tree structure storage table, 104 reference tree structure generation unit (reference tree structure generation unit), 105 tree structure connection unit (tree structure connection unit), 106 tree structure storage table division unit (tree structure storage table division unit), 107 mesh shape generation unit (mesh shape generation unit), 108 reference tree structure generation method selection unit (reference Tree structure generation method selection means).
Claims (9)
上記分解された木構造群に対し、一つの木構造に関する情報を一つの組として記憶する木構造記憶テーブルを生成すると共に、上記各組の形状の領域情報としてバウンディングボックス情報を付加する木構造記憶テーブル生成手段と、
上記バウンディングボックス情報をもとに、空間検索に特化した基準木構造を生成する基準木構造生成手段と、
上記基準木構造生成手段により生成された基準木構造と上記木構造記憶テーブルに記憶されている木構造群を結合する木構造結合手段と
を備えたことを特徴とする木構造を用いた仮想空間データの変換装置。Virtual space data using a tree structure is input, and each tree structure retains part of the information of the original tree structure without destroying the information provided in the given tree structure. Scene tree structure decomposition means for decomposing into a tree structure group
For the decomposed tree structure group, a tree structure storage table that generates a tree structure storage table that stores information on one tree structure as one set and adds bounding box information as region information of the shape of each set Table generation means;
A reference tree structure generating means for generating a reference tree structure specialized for spatial search based on the bounding box information;
A virtual space using a tree structure, comprising: a reference tree structure generated by the reference tree structure generation means; and a tree structure coupling means for coupling a tree structure group stored in the tree structure storage table. Data conversion device.
上記分解された木構造群に対し、一つの木構造に関する情報を一つの組として記憶する木構造記憶テーブルを生成すると共に、上記各組の形状の領域情報としてバウンディングボックス情報を付加する木構造記憶テーブル生成手段と、
上記木構造記憶テーブルを各組が保持しているテクスチャ情報に応じて少なくとも同じテクスチャを１種類は保持している組が同じテーブル内に存在するように複数のテーブルに分割する木構造記憶テーブル分割手段と、
上記分割された木構造記憶テーブルごとに、上記バウンディングボックス情報をもとに、空間検索に特化した基準木構造を生成する基準木構造生成手段と、
上記基準木構造生成手段により生成された基準木構造と上記分割された木構造記憶テーブルに記憶されている木構造群を結合する木構造結合手段と
を備えたことを特徴とする木構造を用いた仮想空間データの変換装置。Virtual space data using a tree structure is input, and each tree structure retains part of the information of the original tree structure without destroying the information provided in the given tree structure. Scene tree structure decomposition means for decomposing into a tree structure group
For the decomposed tree structure group, a tree structure storage table that generates a tree structure storage table that stores information on one tree structure as one set and adds bounding box information as region information of the shape of each set Table generation means;
The tree structure storage table is divided into a plurality of tables in accordance with the texture information held by each set, so that a set holding at least one type of texture exists in the same table. Means,
Based on the bounding box information, for each of the divided tree structure storage tables, a reference tree structure generating unit that generates a reference tree structure specialized for spatial search;
A tree structure combining means for combining a reference tree structure generated by the reference tree structure generation means and a tree structure group stored in the divided tree structure storage table; Virtual space data conversion device.
基準木構造生成手段が木構造記憶テーブルの各組が管理している形状のバウンディングボックス情報をもとに、上記基準木構造生成方法選択手段が選択した上記所定の空間検索に特化した基準木構造を生成する方法を使用し、空間検索に特化した基準木構造を生成することを特徴とする請求項１記載の木構造を用いた仮想空間データの変換装置。A method for storing a method for generating a reference tree structure specialized for a plurality of spatial searches, and a reference tree structure generation method selection unit for selecting a predetermined method according to a user's instruction from a plurality of stored methods,
Based on the bounding box information of the shape managed by each set of the tree structure storage table, the reference tree structure generation unit selects the reference tree specialized in the predetermined space search selected by the reference tree structure generation method selection unit. The apparatus for converting virtual space data using a tree structure according to claim 1, wherein a reference tree structure specialized for spatial search is generated using a method for generating a structure.
基準木構造生成手段が、分割された木構造記憶テーブルごとに、木構造記憶テーブルの各組が管理している形状のバウンディングボックス情報をもとに、上記基準木構造生成方法選択手段が選択した上記所定の空間検索に特化した基準木構造を生成する方法を使用し、空間検索に特化した基準木構造を生成することを特徴とする請求項２記載の木構造を用いた仮想空間データの変換装置。A method for storing a method for generating a reference tree structure specialized for a plurality of spatial searches, and a reference tree structure generation method selection unit for selecting a predetermined method according to a user's instruction from a plurality of stored methods,
The reference tree structure generation method selection means selects, for each divided tree structure storage table, the reference tree structure generation method selection means based on the bounding box information of the shape managed by each set of the tree structure storage tables. 3. The virtual space data using a tree structure according to claim 2, wherein the method of generating the reference tree structure specialized in the predetermined space search is used to generate the reference tree structure specialized in the space search. Conversion device.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP23283097A JP3602304B2 (en) | 1997-08-28 | 1997-08-28 | Virtual space data converter using tree structure |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP23283097A JP3602304B2 (en) | 1997-08-28 | 1997-08-28 | Virtual space data converter using tree structure |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH1173526A JPH1173526A (en) | 1999-03-16 |
| JP3602304B2 true JP3602304B2 (en) | 2004-12-15 |
Family
ID=16945465
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP23283097A Expired - Fee Related JP3602304B2 (en) | 1997-08-28 | 1997-08-28 | Virtual space data converter using tree structure |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3602304B2 (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20190046210A (en) * | 2017-10-25 | 2019-05-07 | 광운대학교 산학협력단 | Space reassembly method and virtual roadmap decision method for virtual reality and space reassembly apparatus performing the same |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7030875B2 (en) | 2002-09-04 | 2006-04-18 | Honda Motor Company Ltd. | Environmental reasoning using geometric data structure |
| JP5218109B2 (en) | 2009-01-30 | 2013-06-26 | 富士通株式会社 | Visualization data processing device, visualization data processing device control method, and visualization data processing device control program |
| JP5274717B2 (en) * | 2010-11-18 | 2013-08-28 | 三菱電機株式会社 | 3D image display apparatus and 3D image display program |
-
1997
- 1997-08-28 JP JP23283097A patent/JP3602304B2/en not_active Expired - Fee Related
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20190046210A (en) * | 2017-10-25 | 2019-05-07 | 광운대학교 산학협력단 | Space reassembly method and virtual roadmap decision method for virtual reality and space reassembly apparatus performing the same |
| KR102004048B1 (en) * | 2017-10-25 | 2019-07-25 | 광운대학교 산학협력단 | Space reassembly method and virtual roadmap decision method for virtual reality and space reassembly apparatus performing the same |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH1173526A (en) | 1999-03-16 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Greuter et al. | Real-time procedural generation ofpseudo infinite'cities | |
| US8612040B2 (en) | Automated derivative view rendering system | |
| US6154215A (en) | Method and apparatus for maintaining multiple representations of a same scene in computer generated graphics | |
| Baert et al. | Out-of-core construction of sparse voxel octrees | |
| US6184897B1 (en) | Compressed representation of changing meshes and method to decompress | |
| US8497860B2 (en) | Spatial decomposition methods using bit manipulation | |
| Chrysanthou et al. | Computing dynamic changes to BSP trees | |
| Ernst et al. | Early split clipping for bounding volume hierarchies | |
| JPH10208077A (en) | Method for rendering graphic image on display, image rendering system and method for generating graphic image on display | |
| JPH05266212A (en) | Method for generating object | |
| WO2002045025A9 (en) | Multiple processor visibility search system and method | |
| JPH10255081A (en) | Image processing method and image processor | |
| US20040201584A1 (en) | Spatial decomposition methods using bit manipulation | |
| JP3602304B2 (en) | Virtual space data converter using tree structure | |
| Garg et al. | GIOTTO3D: A system for visualizing hierarchical structures in 3D | |
| US6104409A (en) | Three-dimensional object data processing method and system | |
| Erikson et al. | Simplification culling of static and dynamic scene graphs | |
| El-Sana et al. | Efficiently computing and updating triangle strips for real-time rendering | |
| Park et al. | Case study: Interactive rendering of adaptive mesh refinement data | |
| Tan et al. | Computing bounding volume hierarchies using model simplification | |
| Roberts et al. | Piecewise linear hypersurfaces using the marching cubes algorithm | |
| Tamada et al. | An efficient 3D object management and interactive walkthrough for the 3D facility management system | |
| Jones | Direct surface rendering of general and genetically bred implicit surfaces | |
| Erikson et al. | Hierarchical levels of detail for fast display of large static and dynamic environments | |
| Hill et al. | Generating surface geometry in higher dimensions using local cell tilers |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Effective date: 20040824 Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20040922 |
|
| R150 | Certificate of patent (=grant) or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20071001 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Year of fee payment: 4 Free format text: PAYMENT UNTIL: 20081001 |
|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20091001 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Year of fee payment: 6 Free format text: PAYMENT UNTIL: 20101001 |
|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111001 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20121001 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Year of fee payment: 9 Free format text: PAYMENT UNTIL: 20131001 |
|
| LAPS | Cancellation because of no payment of annual fees |