JPH1173526A - 木構造を用いた仮想空間データの変換装置 - Google Patents
木構造を用いた仮想空間データの変換装置Info
- Publication number
- JPH1173526A JPH1173526A JP23283097A JP23283097A JPH1173526A JP H1173526 A JPH1173526 A JP H1173526A JP 23283097 A JP23283097 A JP 23283097A JP 23283097 A JP23283097 A JP 23283097A JP H1173526 A JPH1173526 A JP H1173526A
- Authority
- JP
- Japan
- Prior art keywords
- tree structure
- information
- virtual space
- specialized
- generating
- 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.)
- Granted
Links
Landscapes
- Processing Or Creating Images (AREA)
Abstract
(57)【要約】
【課題】 結合操作により形状の階層構造・独立性が損
なわれず、映像情報以外の情報が破壊されない仮想空間
データの変換装置を得る。 【解決手段】 シーン木構造分解部１０１は与えられた
木構造を組み込まれた情報を破壊しないように、各木構
造が元の木構造の情報の一部を保持している木構造群に
分解し、木構造記憶テーブル生成部１０２は分解された
木構造群に対し、一つの木構造に関する情報を一つの組
として木構造記憶テーブル１０３に記憶し、基準木構造
生成部１０４は空間検索に特化した基準木構造を生成
し、木構造結合部１０５は基準木構造と木構造記憶テー
ブル１０３で記憶されている木構造群を結合する。
なわれず、映像情報以外の情報が破壊されない仮想空間
データの変換装置を得る。 【解決手段】 シーン木構造分解部１０１は与えられた
木構造を組み込まれた情報を破壊しないように、各木構
造が元の木構造の情報の一部を保持している木構造群に
分解し、木構造記憶テーブル生成部１０２は分解された
木構造群に対し、一つの木構造に関する情報を一つの組
として木構造記憶テーブル１０３に記憶し、基準木構造
生成部１０４は空間検索に特化した基準木構造を生成
し、木構造結合部１０５は基準木構造と木構造記憶テー
ブル１０３で記憶されている木構造群を結合する。
Description
【０００１】
【発明の属する技術分野】この発明は、木構造を用いた
仮想空間データの変換装置に関するものであり、特にブ
ラウザの描画速度を向上させるものである。
仮想空間データの変換装置に関するものであり、特にブ
ラウザの描画速度を向上させるものである。
【０００２】
【従来の技術】各中間ノードにおいてモデリング変換行
列・バウンディングボックス情報のうち少なくともいず
れか一つを有し、また各葉ノードにおいて形状（ポリゴ
ン）・テクスチャ・イベントハンドリング・ライティン
グ・色情報のうち少なくともいずれか一つを有する根付
き順序木構造で表現される仮想空間データの一例とし
て、ＶＲＭＬ（Ｖｉｒｔｕａｌ Ｒｅａｌｉｔｙ Ｍｏ
ｄｅｌｉｎｇ Ｌａｎｇｕａｇｅ，文献：例えば、三浦
憲二朗著、朝倉書店刊、ＶＲＭＬ２．０：３Ｄサイバー
スペース構築言語）がある。
列・バウンディングボックス情報のうち少なくともいず
れか一つを有し、また各葉ノードにおいて形状（ポリゴ
ン）・テクスチャ・イベントハンドリング・ライティン
グ・色情報のうち少なくともいずれか一つを有する根付
き順序木構造で表現される仮想空間データの一例とし
て、ＶＲＭＬ（Ｖｉｒｔｕａｌ Ｒｅａｌｉｔｙ Ｍｏ
ｄｅｌｉｎｇ Ｌａｎｇｕａｇｅ，文献：例えば、三浦
憲二朗著、朝倉書店刊、ＶＲＭＬ２．０：３Ｄサイバー
スペース構築言語）がある。
【０００３】ＶＲＭＬはインターネット上において仮想
空間を公開・共有する環境を実現するために開発された
言語である。上記環境は、ＶＲＭＬファイルをインター
ネットを介してやりとりし、本データ専用の描画ソフト
ウェア（ブラウザ）が、与えられた木構造を深さ優先探
索で走査しながら任意視点の映像を描画することで実現
される。
空間を公開・共有する環境を実現するために開発された
言語である。上記環境は、ＶＲＭＬファイルをインター
ネットを介してやりとりし、本データ専用の描画ソフト
ウェア（ブラウザ）が、与えられた木構造を深さ優先探
索で走査しながら任意視点の映像を描画することで実現
される。
【０００４】ある仮想空間に対応したＶＲＭＬデータを
作成するには無数の表現方法があるが、一般的に、描画
時にブラウザが走査するノードの数とテクスチャ（描画
属性）のスイッチング回数が少なければ少ない程、ま
た、ポリゴンがメッシュ表現（隣接する三角形から構成
される幾何学図形）されている程、ブラウザの描画速度
は向上する。従って、ある仮想空間に対応したＶＲＭＬ
データが存在した場合に、本ＶＲＭＬデータを、データ
に組み込まれた仮想空間に関する各種情報を破壊するこ
となく、上記条件を満たすように変換することができれ
ば、同一の仮想空間をより高速に描画するＶＲＭＬデー
タを作成することができる。
作成するには無数の表現方法があるが、一般的に、描画
時にブラウザが走査するノードの数とテクスチャ（描画
属性）のスイッチング回数が少なければ少ない程、ま
た、ポリゴンがメッシュ表現（隣接する三角形から構成
される幾何学図形）されている程、ブラウザの描画速度
は向上する。従って、ある仮想空間に対応したＶＲＭＬ
データが存在した場合に、本ＶＲＭＬデータを、データ
に組み込まれた仮想空間に関する各種情報を破壊するこ
となく、上記条件を満たすように変換することができれ
ば、同一の仮想空間をより高速に描画するＶＲＭＬデー
タを作成することができる。
【０００５】上記変換を自動的に行う従来法として、ｉ
ｖｆｉｘというソフトウェア（シリコングラフィックス
社製）がある。ｉｖｆｉｘはＶＲＭＬのベースとなった
Ｏｐｅｎ Ｉｎｖｅｎｔｏｒファイルフォーマットで記
述された根付き順序木構造で表現される仮想空間データ
に対し、ブラウザの描画速度が向上するようにデータを
変換する。
ｖｆｉｘというソフトウェア（シリコングラフィックス
社製）がある。ｉｖｆｉｘはＶＲＭＬのベースとなった
Ｏｐｅｎ Ｉｎｖｅｎｔｏｒファイルフォーマットで記
述された根付き順序木構造で表現される仮想空間データ
に対し、ブラウザの描画速度が向上するようにデータを
変換する。
【０００６】図２０は従来の技術における仮想空間デー
タの変換装置を示すブロック図であり、図において、１
は入力された木構造内の各形状情報に関する情報を一つ
の形状情報とそれに関連する情報群（カメラ、光源モデ
ル、テクスチャ、材質、座標変換等）を一つの組として
形状関連情報テーブル７に格納していく形状関連情報テ
ーブル作成部、２は形状関連情報テーブル内の組を描画
属性をキーとして並べ替える形状関連情報テーブルソー
ト部、３は形状関連情報テーブルの組で描画属性情報が
同一のものを一つの組に結合する形状関連情報テーブル
マージ部、４は形状関連情報テーブル７から一つの木構
造を生成する木構造生成部、５は形状情報をメッシュ化
するメッシュ形状生成部、６は木構造の冗長なノードを
除去する冗長情報削除部である。
タの変換装置を示すブロック図であり、図において、１
は入力された木構造内の各形状情報に関する情報を一つ
の形状情報とそれに関連する情報群（カメラ、光源モデ
ル、テクスチャ、材質、座標変換等）を一つの組として
形状関連情報テーブル７に格納していく形状関連情報テ
ーブル作成部、２は形状関連情報テーブル内の組を描画
属性をキーとして並べ替える形状関連情報テーブルソー
ト部、３は形状関連情報テーブルの組で描画属性情報が
同一のものを一つの組に結合する形状関連情報テーブル
マージ部、４は形状関連情報テーブル７から一つの木構
造を生成する木構造生成部、５は形状情報をメッシュ化
するメッシュ形状生成部、６は木構造の冗長なノードを
除去する冗長情報削除部である。
【０００７】次に動作について図２１から図２６を参照
しながら説明する。図２１は従来の技術における処理手
順を示すフローチャートである。まずステップＳＴ１に
おいて、形状関連情報テーブル作成部１は、入力データ
の木構造を解析し、木構造内で定義されている形状情報
とそれに関連する情報群を一つの組として、形状関連情
報テーブル７を作成する。
しながら説明する。図２１は従来の技術における処理手
順を示すフローチャートである。まずステップＳＴ１に
おいて、形状関連情報テーブル作成部１は、入力データ
の木構造を解析し、木構造内で定義されている形状情報
とそれに関連する情報群を一つの組として、形状関連情
報テーブル７を作成する。
【０００８】次にステップＳＴ２において、形状関連情
報テーブルソート部２は、形状関連情報テーブル７の各
組を、描画属性をキーとして並べ替える。次にステップ
ＳＴ３において、形状関連情報テーブルマージ部３は、
ソート後の形状関連情報テーブル７に対し、相違水準と
いう属性を追加し、第ｎ組と第ｎ−１組の相違水準を６
段階（０，１，２，３，４，５）で判定したものを第ｎ
組の相違水準の属性値とする。但し、第１組の相違水準
の属性値は１とする。
報テーブルソート部２は、形状関連情報テーブル７の各
組を、描画属性をキーとして並べ替える。次にステップ
ＳＴ３において、形状関連情報テーブルマージ部３は、
ソート後の形状関連情報テーブル７に対し、相違水準と
いう属性を追加し、第ｎ組と第ｎ−１組の相違水準を６
段階（０，１，２，３，４，５）で判定したものを第ｎ
組の相違水準の属性値とする。但し、第１組の相違水準
の属性値は１とする。
【０００９】ここで上記ステップＳＴ３において、形状
関連情報テーブルマージ部３が、形状関連情報テーブル
７の第ｎ組ｃn と第ｎ−１組ｃn-1 の描画属性を比較し
てｃn の相違水準ｌn を求める処理手順の詳細について
図２２に示すフローチャートに従って説明する。まず、
ステップＳＴ３１において、ｃn とｃn-1 の描画属性に
おいて、カメラが同じであるかどうかを判定し、ＮＯの
場合にはステップＳＴ３２において、ｌn ＝１として処
理を終了する。
関連情報テーブルマージ部３が、形状関連情報テーブル
７の第ｎ組ｃn と第ｎ−１組ｃn-1 の描画属性を比較し
てｃn の相違水準ｌn を求める処理手順の詳細について
図２２に示すフローチャートに従って説明する。まず、
ステップＳＴ３１において、ｃn とｃn-1 の描画属性に
おいて、カメラが同じであるかどうかを判定し、ＮＯの
場合にはステップＳＴ３２において、ｌn ＝１として処
理を終了する。
【００１０】上記ステップＳＴ３１においてＹＥＳと判
定された場合には、ステップＳＴ３３において、ｃn と
ｃn-1 の描画属性において、光源・大気効果・光源モデ
ルが同じであるかどうかを判定し、ＮＯの場合にはステ
ップＳＴ３４において、ｌn＝２として処理を終了す
る。
定された場合には、ステップＳＴ３３において、ｃn と
ｃn-1 の描画属性において、光源・大気効果・光源モデ
ルが同じであるかどうかを判定し、ＮＯの場合にはステ
ップＳＴ３４において、ｌn＝２として処理を終了す
る。
【００１１】上記ステップＳＴ３３においてＹＥＳと判
定された場合には、ステップＳＴ３５において、ｃn と
ｃn-1 の描画属性において、テクスチャが同じであるか
どうかを判定し、ＮＯの場合にはステップＳＴ３６でｌ
n ＝３として処理を終了する。
定された場合には、ステップＳＴ３５において、ｃn と
ｃn-1 の描画属性において、テクスチャが同じであるか
どうかを判定し、ＮＯの場合にはステップＳＴ３６でｌ
n ＝３として処理を終了する。
【００１２】上記ステップＳＴ３５においてＹＥＳと判
定された場合には、ステップＳＴ３７で、ｃn とｃn-1
の描画属性において、描画スタイル・材質・頂点の定義
順序が同じであるかどうかを判定し、ＮＯの場合にはス
テップＳＴ３８において、ｌn ＝４として処理を終了す
る。
定された場合には、ステップＳＴ３７で、ｃn とｃn-1
の描画属性において、描画スタイル・材質・頂点の定義
順序が同じであるかどうかを判定し、ＮＯの場合にはス
テップＳＴ３８において、ｌn ＝４として処理を終了す
る。
【００１３】上記ステップＳＴ３７においてＹＥＳと判
定された場合には、ステップＳＴ３９で、ｃn とｃn-1
の描画属性において、両方の形状が同一ファイル上で定
義されているかどうかを判定し、ＮＯの場合にはステッ
プＳＴ４０において、ｌn ＝５として処理を終了し、Ｙ
ＥＳの場合にはステップＳＴ４１において、ｌn ＝０と
して処理を終了する。
定された場合には、ステップＳＴ３９で、ｃn とｃn-1
の描画属性において、両方の形状が同一ファイル上で定
義されているかどうかを判定し、ＮＯの場合にはステッ
プＳＴ４０において、ｌn ＝５として処理を終了し、Ｙ
ＥＳの場合にはステップＳＴ４１において、ｌn ＝０と
して処理を終了する。
【００１４】次に図２１のステップＳＴ４において、ス
テップＳＴ３で得られた形状関連情報テーブル７の組
で、相違水準が０である組（第ｎ組）が、上の組（第ｎ
−１組）と描画属性情報が同一である場合には、形状関
連情報テーブルマージ部が、第ｎ組と第ｎ−１組を結合
する操作を逐次的に実行する。
テップＳＴ３で得られた形状関連情報テーブル７の組
で、相違水準が０である組（第ｎ組）が、上の組（第ｎ
−１組）と描画属性情報が同一である場合には、形状関
連情報テーブルマージ部が、第ｎ組と第ｎ−１組を結合
する操作を逐次的に実行する。
【００１５】ここで、このステップＳＴ４における組の
結合操作の処理手順の詳細について、図２３を用いて説
明する。ここで、形状関連情報テーブル７の第ｎ組ｃn
の相違水準の属性値が０で、第ｎ組ｃn と第ｎ−１組ｃ
n-1 の描画属性情報ＲＡが同じであるとする。この時、
ｃn-1 の形状情報ｓn-1 に変形情報ｔn-1 を作用させた
ものをｓ'n-1、ｃn の形状情報ｓn に変形情報ｔn を作
用させたものをｓ'nとすると、形状情報がｓ'n-1＋
ｓ'n、変形情報がＮＵＬＬ、描画属性情報がＲＡ、相違
水準がｌn-1 （ｃn-1 の相違水準の属性値）である組を
生成し、これをｃn- 1 及びｃn の結合結果とする。
結合操作の処理手順の詳細について、図２３を用いて説
明する。ここで、形状関連情報テーブル７の第ｎ組ｃn
の相違水準の属性値が０で、第ｎ組ｃn と第ｎ−１組ｃ
n-1 の描画属性情報ＲＡが同じであるとする。この時、
ｃn-1 の形状情報ｓn-1 に変形情報ｔn-1 を作用させた
ものをｓ'n-1、ｃn の形状情報ｓn に変形情報ｔn を作
用させたものをｓ'nとすると、形状情報がｓ'n-1＋
ｓ'n、変形情報がＮＵＬＬ、描画属性情報がＲＡ、相違
水準がｌn-1 （ｃn-1 の相違水準の属性値）である組を
生成し、これをｃn- 1 及びｃn の結合結果とする。
【００１６】次に図２１のステップＳＴ５において、木
構造生成部４は、結合操作後の形状関連情報テーブル７
から、図２４に示すフローチャートに従って、一つの木
構造Ｔを生成する。まず図２４のステップＳＴ５１にお
いて、図２５に示すような深さ５の中間ノードのみから
なる直線状の根付き順序木構造Ｔを生成する。この根付
き順序木構造Ｔにおいて、Ｒ1 にはカメラに関する情報
がどのファイル上にあるかについての情報が格納され、
以下、Ｒ2 には光源・大気効果・光源モデル、Ｒ3 には
テクスチャ、Ｒ4 には描画スタイル・材質・頂点の定義
順序、Ｒ5 には形状情報というように、各情報がどのフ
ァイル上にあるかについての情報が各々格納されてい
く。
構造生成部４は、結合操作後の形状関連情報テーブル７
から、図２４に示すフローチャートに従って、一つの木
構造Ｔを生成する。まず図２４のステップＳＴ５１にお
いて、図２５に示すような深さ５の中間ノードのみから
なる直線状の根付き順序木構造Ｔを生成する。この根付
き順序木構造Ｔにおいて、Ｒ1 にはカメラに関する情報
がどのファイル上にあるかについての情報が格納され、
以下、Ｒ2 には光源・大気効果・光源モデル、Ｒ3 には
テクスチャ、Ｒ4 には描画スタイル・材質・頂点の定義
順序、Ｒ5 には形状情報というように、各情報がどのフ
ァイル上にあるかについての情報が各々格納されてい
く。
【００１７】次にステップＳＴ５２において、組番号を
示す変数ＮをＮ＝１に初期設定する。そしてステップＳ
Ｔ５３において、Ｎが形状関連情報テーブル７の組の数
より大きいかどうかを判定し、大きい場合には処理を終
了する。Ｎが形状関連情報テーブル７の組の数以下の場
合には、ステップＳＴ５４において、深さｄの直線状の
根付き順序木構造ＴN を生成する。ここで、深さｄの値
は相違水準ｌN により次式で与えられる。 ｄ＝０ ｉｆ ｌN ＝０ ｄ＝６−ｌN ｏｔｈｅｒｗｉｓｅ
示す変数ＮをＮ＝１に初期設定する。そしてステップＳ
Ｔ５３において、Ｎが形状関連情報テーブル７の組の数
より大きいかどうかを判定し、大きい場合には処理を終
了する。Ｎが形状関連情報テーブル７の組の数以下の場
合には、ステップＳＴ５４において、深さｄの直線状の
根付き順序木構造ＴN を生成する。ここで、深さｄの値
は相違水準ｌN により次式で与えられる。 ｄ＝０ ｉｆ ｌN ＝０ ｄ＝６−ｌN ｏｔｈｅｒｗｉｓｅ
【００１８】次にステップＳＴ５５において、木構造Ｔ
N に形状関連情報テーブル７の第Ｎ組の情報を挿入して
いく。ＴN においてＴN の中の深さｉの各ノードｓ
（ｉ，ＴN ）に挿入する情報は、ＴN の深さとＴN の中
の深さｉにより決定される。次にステップＳＴ５６にお
いて、図２６に示すように、ＴN の根が、Ｔの深さｄ
（ＴN ）すなわち図２６では２で、最も右側のノード
（深さ優先頂位で最も順位が大きい深さｄ（ＴN ）のノ
ード）の最も右側の子となるように、ＴN をＴに挿入す
る。ここで、深さｄ（ＴN ）の値は相違水準ｌN により
次式で与えられる。 ｄ（ＴN ）＝５ ｉｆ ｌN ＝０ ｄ（ＴN ）＝ｌN −１ ｏｔｈｅｒｗｉｓｅ そしてステップＳＴ５７において、Ｎ＝Ｎ＋１とインク
リメントして、ステップＳＴ５３へ戻る。
N に形状関連情報テーブル７の第Ｎ組の情報を挿入して
いく。ＴN においてＴN の中の深さｉの各ノードｓ
（ｉ，ＴN ）に挿入する情報は、ＴN の深さとＴN の中
の深さｉにより決定される。次にステップＳＴ５６にお
いて、図２６に示すように、ＴN の根が、Ｔの深さｄ
（ＴN ）すなわち図２６では２で、最も右側のノード
（深さ優先頂位で最も順位が大きい深さｄ（ＴN ）のノ
ード）の最も右側の子となるように、ＴN をＴに挿入す
る。ここで、深さｄ（ＴN ）の値は相違水準ｌN により
次式で与えられる。 ｄ（ＴN ）＝５ ｉｆ ｌN ＝０ ｄ（ＴN ）＝ｌN −１ ｏｔｈｅｒｗｉｓｅ そしてステップＳＴ５７において、Ｎ＝Ｎ＋１とインク
リメントして、ステップＳＴ５３へ戻る。
【００１９】次に図２１のステップＳＴ６において、メ
ッシュ形状生成部５はステップＳＴ５で得られた根付き
順序木構造Ｔ内の形状情報をメッシュ化する。そして最
後にステップＳＴ７において、冗長情報削除部６は根付
き順序木構造Ｔをブラウザと同様に深さ優先探索で走査
することで、冗長なノードを検知・除去し出力する。
ッシュ形状生成部５はステップＳＴ５で得られた根付き
順序木構造Ｔ内の形状情報をメッシュ化する。そして最
後にステップＳＴ７において、冗長情報削除部６は根付
き順序木構造Ｔをブラウザと同様に深さ優先探索で走査
することで、冗長なノードを検知・除去し出力する。
【００２０】以上のように、従来の技術における仮想空
間データの変換装置は、根付き順序木構造で表現される
仮想空間データを変換することで、描画時におけるテク
スチャ（描画属性）のスイッチング回数が減少し、ほと
んどの場合において変換前に比べ木構造のノード数が減
少することにより、また形状をメッシュ化することによ
りポリゴンの描画速度が向上する。
間データの変換装置は、根付き順序木構造で表現される
仮想空間データを変換することで、描画時におけるテク
スチャ（描画属性）のスイッチング回数が減少し、ほと
んどの場合において変換前に比べ木構造のノード数が減
少することにより、また形状をメッシュ化することによ
りポリゴンの描画速度が向上する。
【００２１】
【発明が解決しようとする課題】しかし従来の仮想空間
データの変換装置は、結合操作により形状の階層構造・
独立性が損なわれ、映像情報以外の情報が破壊されると
いう課題があった。従って、ユーザからのインタラクシ
ョン（マウスによりあるオブジェクトをクリックする
等）に応じてなんらかのアクションを定義しているよう
な仮想空間データに本手法を適用すると、変換後には正
常に動作しなくなる。
データの変換装置は、結合操作により形状の階層構造・
独立性が損なわれ、映像情報以外の情報が破壊されると
いう課題があった。従って、ユーザからのインタラクシ
ョン（マウスによりあるオブジェクトをクリックする
等）に応じてなんらかのアクションを定義しているよう
な仮想空間データに本手法を適用すると、変換後には正
常に動作しなくなる。
【００２２】また、形状情報の位置・大きさに関係なく
描画属性が同一のものを一つの形状情報として結合する
ため、視野領域外のポリゴンについても、それと同じ描
画属性情報をもつポリゴンが視野領域内に存在する場合
には描画処理される。従って、ほとんどのポリゴンが視
野領域外となる広域な仮想空間を表現した木構造の場合
には、無駄な描画処理が頻繁に発生し、描画速度が遅く
なるという課題があった。
描画属性が同一のものを一つの形状情報として結合する
ため、視野領域外のポリゴンについても、それと同じ描
画属性情報をもつポリゴンが視野領域内に存在する場合
には描画処理される。従って、ほとんどのポリゴンが視
野領域外となる広域な仮想空間を表現した木構造の場合
には、無駄な描画処理が頻繁に発生し、描画速度が遅く
なるという課題があった。
【００２３】この発明は上記のような課題を解決するた
めになされたもので、映像情報以外の情報損失が生じる
ことなく、広域な仮想空間を表現したデータに対しても
ブラウザの描画速度が向上するような木構造を用いた仮
想空間データの変換装置を得ることを目的とする。
めになされたもので、映像情報以外の情報損失が生じる
ことなく、広域な仮想空間を表現したデータに対しても
ブラウザの描画速度が向上するような木構造を用いた仮
想空間データの変換装置を得ることを目的とする。
【００２４】
【課題を解決するための手段】この発明に係る木構造を
用いた仮想空間データの変換装置は、木構造を用いた仮
想空間データを入力し、与えられた木構造を、木構造自
身に組み込まれた情報を破壊することなく、各木構造が
元の木構造の情報の一部を保持している木構造群に分解
するシーン木構造分解手段と、上記分解された木構造群
に対し、一つの木構造に関する情報を一つの組として記
憶する木構造記憶テーブルを生成すると共に、上記各組
の形状の領域情報としてバウンディングボックス情報を
付加する木構造記憶テーブル生成手段と、上記バウンデ
ィングボックス情報をもとに、空間検索に特化した基準
木構造を生成する基準木構造生成手段と、上記基準木構
造生成手段により生成された基準木構造と上記木構造記
憶テーブルに記憶されている木構造群を結合する木構造
結合手段とを備えたものである。
用いた仮想空間データの変換装置は、木構造を用いた仮
想空間データを入力し、与えられた木構造を、木構造自
身に組み込まれた情報を破壊することなく、各木構造が
元の木構造の情報の一部を保持している木構造群に分解
するシーン木構造分解手段と、上記分解された木構造群
に対し、一つの木構造に関する情報を一つの組として記
憶する木構造記憶テーブルを生成すると共に、上記各組
の形状の領域情報としてバウンディングボックス情報を
付加する木構造記憶テーブル生成手段と、上記バウンデ
ィングボックス情報をもとに、空間検索に特化した基準
木構造を生成する基準木構造生成手段と、上記基準木構
造生成手段により生成された基準木構造と上記木構造記
憶テーブルに記憶されている木構造群を結合する木構造
結合手段とを備えたものである。
【００２５】この発明に係る木構造を用いた仮想空間デ
ータの変換装置は、木構造を用いた仮想空間データを入
力し、与えられた木構造を、木構造自身に組み込まれた
情報を破壊することなく、各木構造が元の木構造の情報
の一部を保持している木構造群に分解するシーン木構造
分解手段と、上記分解された木構造群に対し、一つの木
構造に関する情報を一つの組として記憶する木構造記憶
テーブルを生成すると共に、上記各組の形状の領域情報
としてバウンディングボックス情報を付加する木構造記
憶テーブル生成手段と、上記木構造記憶テーブルを各組
が保持しているテクスチャ情報に応じて少なくとも同じ
テクスチャを１種類は保持している組が同じテーブル内
に存在するように複数のテーブルに分割する木構造記憶
テーブル分割手段と、上記分割された木構造記憶テーブ
ルごとに、上記バウンディングボックス情報をもとに、
空間検索に特化した基準木構造を生成する基準木構造生
成手段と、上記基準木構造生成手段により生成された基
準木構造と上記分割された木構造記憶テーブルに記憶さ
れている木構造群を結合する木構造結合手段とを備えた
ものである。
ータの変換装置は、木構造を用いた仮想空間データを入
力し、与えられた木構造を、木構造自身に組み込まれた
情報を破壊することなく、各木構造が元の木構造の情報
の一部を保持している木構造群に分解するシーン木構造
分解手段と、上記分解された木構造群に対し、一つの木
構造に関する情報を一つの組として記憶する木構造記憶
テーブルを生成すると共に、上記各組の形状の領域情報
としてバウンディングボックス情報を付加する木構造記
憶テーブル生成手段と、上記木構造記憶テーブルを各組
が保持しているテクスチャ情報に応じて少なくとも同じ
テクスチャを１種類は保持している組が同じテーブル内
に存在するように複数のテーブルに分割する木構造記憶
テーブル分割手段と、上記分割された木構造記憶テーブ
ルごとに、上記バウンディングボックス情報をもとに、
空間検索に特化した基準木構造を生成する基準木構造生
成手段と、上記基準木構造生成手段により生成された基
準木構造と上記分割された木構造記憶テーブルに記憶さ
れている木構造群を結合する木構造結合手段とを備えた
ものである。
【００２６】この発明に係る木構造を用いた仮想空間デ
ータの変換装置は、木構造結合手段で生成された木構造
内の形状情報をメッシュ化するメッシュ形状生成手段を
備えたものである。
ータの変換装置は、木構造結合手段で生成された木構造
内の形状情報をメッシュ化するメッシュ形状生成手段を
備えたものである。
【００２７】この発明に係る木構造を用いた仮想空間デ
ータの変換装置は、複数の空間検索に特化した基準木構
造を生成する方法を記憶し、記憶されている複数の方法
の中から、ユーザの指示により所定の方法を選択する基
準木構造生成方法選択手段を備え、基準木構造生成手段
が木構造記憶テーブルの各組が管理している形状のバウ
ンディングボックス情報をもとに、上記基準木構造生成
方法選択手段が選択した上記所定の空間検索に特化した
基準木構造を生成する方法を使用し、空間検索に特化し
た基準木構造を生成するものである。
ータの変換装置は、複数の空間検索に特化した基準木構
造を生成する方法を記憶し、記憶されている複数の方法
の中から、ユーザの指示により所定の方法を選択する基
準木構造生成方法選択手段を備え、基準木構造生成手段
が木構造記憶テーブルの各組が管理している形状のバウ
ンディングボックス情報をもとに、上記基準木構造生成
方法選択手段が選択した上記所定の空間検索に特化した
基準木構造を生成する方法を使用し、空間検索に特化し
た基準木構造を生成するものである。
【００２８】この発明に係る木構造を用いた仮想空間デ
ータの変換装置は、複数の空間検索に特化した基準木構
造を生成する方法を記憶し、記憶されている複数の方法
の中から、ユーザの指示により所定の方法を選択する基
準木構造生成方法選択手段を備え、基準木構造生成手段
が、分割された木構造記憶テーブルごとに、木構造記憶
テーブルの各組が管理している形状のバウンディングボ
ックス情報をもとに、上記基準木構造生成方法選択手段
が選択した上記所定の空間検索に特化した基準木構造を
生成する方法を使用し、空間検索に特化した基準木構造
を生成するものである。
ータの変換装置は、複数の空間検索に特化した基準木構
造を生成する方法を記憶し、記憶されている複数の方法
の中から、ユーザの指示により所定の方法を選択する基
準木構造生成方法選択手段を備え、基準木構造生成手段
が、分割された木構造記憶テーブルごとに、木構造記憶
テーブルの各組が管理している形状のバウンディングボ
ックス情報をもとに、上記基準木構造生成方法選択手段
が選択した上記所定の空間検索に特化した基準木構造を
生成する方法を使用し、空間検索に特化した基準木構造
を生成するものである。
【００２９】この発明に係る木構造を用いた仮想空間デ
ータの変換装置は、空間検索に特化した木構造として、
２次元空間を複数の小空間に分割し、その小空間内のデ
ータをかためて管理する木構造を用いたものである。
ータの変換装置は、空間検索に特化した木構造として、
２次元空間を複数の小空間に分割し、その小空間内のデ
ータをかためて管理する木構造を用いたものである。
【００３０】この発明に係る木構造を用いた仮想空間デ
ータの変換装置は、空間検索に特化した木構造として、
３次元空間を複数の小空間に分割し、その小空間内のデ
ータをかためて管理する木構造を用いたものである。
ータの変換装置は、空間検索に特化した木構造として、
３次元空間を複数の小空間に分割し、その小空間内のデ
ータをかためて管理する木構造を用いたものである。
【００３１】この発明に係る木構造を用いた仮想空間デ
ータの変換装置は、空間検索に特化した木構造として、
２次元空間をデータの分布状況に応じて領域分割する木
構造を用いたものである。
ータの変換装置は、空間検索に特化した木構造として、
２次元空間をデータの分布状況に応じて領域分割する木
構造を用いたものである。
【００３２】この発明に係る木構造を用いた仮想空間デ
ータの変換装置は、空間検索に特化した木構造として、
３次元空間をデータの分布状況に応じて領域分割する木
構造を用いたものである。
ータの変換装置は、空間検索に特化した木構造として、
３次元空間をデータの分布状況に応じて領域分割する木
構造を用いたものである。
【００３３】
【発明の実施の形態】以下、この発明の実施の一形態を
説明する。 実施の形態１．図１はこの発明の実施の形態１における
木構造を用いた仮想空間データの変換装置を示すブロッ
ク図であり、図において、１０１は与えられた木構造を
木構造自身に組み込まれた情報を破壊しないように、各
木構造が元の木構造の情報の一部を保持している木構造
群に分解するシーン木構造分解部（シーン木構造分解手
段）、１０２はシーン木構造分解部１０１で分解された
木構造群に対し、一つの木構造に関する情報を一つの組
として記憶することにより木構造記憶テーブル１０３を
生成する木構造記憶テーブル生成部（木構造記憶テーブ
ル生成手段）である。
説明する。 実施の形態１．図１はこの発明の実施の形態１における
木構造を用いた仮想空間データの変換装置を示すブロッ
ク図であり、図において、１０１は与えられた木構造を
木構造自身に組み込まれた情報を破壊しないように、各
木構造が元の木構造の情報の一部を保持している木構造
群に分解するシーン木構造分解部（シーン木構造分解手
段）、１０２はシーン木構造分解部１０１で分解された
木構造群に対し、一つの木構造に関する情報を一つの組
として記憶することにより木構造記憶テーブル１０３を
生成する木構造記憶テーブル生成部（木構造記憶テーブ
ル生成手段）である。
【００３４】また、１０４は木構造記憶テーブル１０３
の各組が管理している形状のバウンディングボックス
（各組が保持している形状を含む最小の直方体）情報を
もとに空間検索に特化した基準木構造を生成する基準木
構造生成部（基準木構造生成手段）、１０５は基準木構
造と木構造記憶テーブルで記憶されている木構造群を結
合することで与えられた木構造と等価な仮想空間を表現
した一つの木構造を生成する木構造結合部（木構造結合
手段）である。
の各組が管理している形状のバウンディングボックス
（各組が保持している形状を含む最小の直方体）情報を
もとに空間検索に特化した基準木構造を生成する基準木
構造生成部（基準木構造生成手段）、１０５は基準木構
造と木構造記憶テーブルで記憶されている木構造群を結
合することで与えられた木構造と等価な仮想空間を表現
した一つの木構造を生成する木構造結合部（木構造結合
手段）である。
【００３５】次に動作について説明する。図２はこの実
施の形態１における木構造を用いた仮想空間データの変
換装置の処理手順を示すフローチャートである。まずス
テップＳＴ１０１において、シーン木構造分解部１０１
は、ある仮想空間を表現した木構造が与えられると、木
構造自身に組み込まれた情報を破壊しないように、各木
構造が元の木構造の情報の一部を保持している木構造に
分解する。
施の形態１における木構造を用いた仮想空間データの変
換装置の処理手順を示すフローチャートである。まずス
テップＳＴ１０１において、シーン木構造分解部１０１
は、ある仮想空間を表現した木構造が与えられると、木
構造自身に組み込まれた情報を破壊しないように、各木
構造が元の木構造の情報の一部を保持している木構造に
分解する。
【００３６】ここで、このシーン木構造分解部１０１に
よるステップＳＴ１０１の処理手順の詳細について、図
３のフローチャートを用いて説明する。まずステップＳ
Ｔ１１０１において、処理対象となる木構造を示す変数
ＴＰを変換対象となる木構造Ｔに設定し、分解処理の深
さを示す変数Ｑの値を０に初期化する。
よるステップＳＴ１０１の処理手順の詳細について、図
３のフローチャートを用いて説明する。まずステップＳ
Ｔ１１０１において、処理対象となる木構造を示す変数
ＴＰを変換対象となる木構造Ｔに設定し、分解処理の深
さを示す変数Ｑの値を０に初期化する。
【００３７】次にステップＳＴ１１０２において、変数
ＴＰがこれ以上分解可能かどうかを判定する。このステ
ップＳＴ１１０２でＮＯと判定されるのは、 イ．ＴＰに形状情報が存在しない、 ロ．ＴＰ内の全ての形状に共通のユーザからの入力に対
する動作メカニズムが定義（例えば、ＶＲＭＬにおける
Ｔｏｕｃｈ Ｓｅｎｓｏｒを利用したアニメーション機
能）されている、 ハ．ＴＰの深さが１以下である、 のいずれかの条件が満たされる場合である。
ＴＰがこれ以上分解可能かどうかを判定する。このステ
ップＳＴ１１０２でＮＯと判定されるのは、 イ．ＴＰに形状情報が存在しない、 ロ．ＴＰ内の全ての形状に共通のユーザからの入力に対
する動作メカニズムが定義（例えば、ＶＲＭＬにおける
Ｔｏｕｃｈ Ｓｅｎｓｏｒを利用したアニメーション機
能）されている、 ハ．ＴＰの深さが１以下である、 のいずれかの条件が満たされる場合である。
【００３８】上記ステップＳＴ１１０２でＹＥＳと判定
された場合には、ステップＳＴ１１０３において、Ｑ＝
Ｑ＋１とする。そしてステップＳＴ１１０４において、
ＴＰの根の子で葉でないものを中間ノードｖi （ｉ＝
１，２，・・・，ｎ：ｎ＝ＴＰの根の子で葉でないもの
の個数）とした時に、図４に示すようにＴＰを、（ａ）
ＴＰの根とその子で葉であるもののみからなる木構造Ｔ
Ｐ（Ｑ，０）［根に葉が存在する場合のみ］、（ｂ）Ｔ
Ｐの根と中間ノードｖi とその子孫とからなる木構造Ｔ
Ｐ（Ｑ，ｉ）［ｉ＝１，２，・・・，ｎ］、に分解す
る。
された場合には、ステップＳＴ１１０３において、Ｑ＝
Ｑ＋１とする。そしてステップＳＴ１１０４において、
ＴＰの根の子で葉でないものを中間ノードｖi （ｉ＝
１，２，・・・，ｎ：ｎ＝ＴＰの根の子で葉でないもの
の個数）とした時に、図４に示すようにＴＰを、（ａ）
ＴＰの根とその子で葉であるもののみからなる木構造Ｔ
Ｐ（Ｑ，０）［根に葉が存在する場合のみ］、（ｂ）Ｔ
Ｐの根と中間ノードｖi とその子孫とからなる木構造Ｔ
Ｐ（Ｑ，ｉ）［ｉ＝１，２，・・・，ｎ］、に分解す
る。
【００３９】次にステップＳＴ１１０５において、各Ｔ
Ｐ（Ｑ，ｉ）［１≦ｉ≦ｎ］に対し、図５に示すよう
に、根から分岐が１であるノード（Ｒi （ｉ＝０，１，
・・・，ｒ））までを、Ｒi が保持しているモデリング
変換行列情報をＭi ，各Ｍi を乗算したモデリング変換
行列情報をＭ（Ｍ＝Ｍr ×Ｍr-1 ×・・・×Ｍ0 ），Ｒ
0 の子孫ノードが管理している形状のバウンディングボ
ックスをＢとした時に、モデリング変換行列情報として
Ｍを有し、バウンディングボックス情報としてＢを有す
るノードＲに置き換えることで、Ｒi （ｉ＝０，１，・
・・，ｒ）を情報損失がないように一つのノードＲにま
とめる。
Ｐ（Ｑ，ｉ）［１≦ｉ≦ｎ］に対し、図５に示すよう
に、根から分岐が１であるノード（Ｒi （ｉ＝０，１，
・・・，ｒ））までを、Ｒi が保持しているモデリング
変換行列情報をＭi ，各Ｍi を乗算したモデリング変換
行列情報をＭ（Ｍ＝Ｍr ×Ｍr-1 ×・・・×Ｍ0 ），Ｒ
0 の子孫ノードが管理している形状のバウンディングボ
ックスをＢとした時に、モデリング変換行列情報として
Ｍを有し、バウンディングボックス情報としてＢを有す
るノードＲに置き換えることで、Ｒi （ｉ＝０，１，・
・・，ｒ）を情報損失がないように一つのノードＲにま
とめる。
【００４０】次にステップＳＴ１１０６において、深さ
Ｑにおける分解処理で生成された木構造の数ＮＮ［Ｑ］
を、ＮＮ［Ｑ］＝ｎ＋１とし、深さＱにおける分解処理
のインデックスＮＩ［Ｑ］を、ＮＩ［Ｑ］＝０とする。
そしてステップＳＴ１１０７において、ＮＩ［Ｑ］＞Ｎ
Ｎ［Ｑ］であるかどうか判定する。このステップＳＴ１
１０７でＮＯと判定された場合には、ステップＳＴ１１
０８でＴＰ＝ＴＰ（Ｑ，ＮＩ［Ｑ］）とし、ステップＳ
Ｔ１１０２へ戻る。ＹＥＳと判定された場合には、ステ
ップＳＴ１１０９でＱ＝Ｑ−１とし、ステップＳＴ１１
１０でＱ≦０であるかどうかを判定する。
Ｑにおける分解処理で生成された木構造の数ＮＮ［Ｑ］
を、ＮＮ［Ｑ］＝ｎ＋１とし、深さＱにおける分解処理
のインデックスＮＩ［Ｑ］を、ＮＩ［Ｑ］＝０とする。
そしてステップＳＴ１１０７において、ＮＩ［Ｑ］＞Ｎ
Ｎ［Ｑ］であるかどうか判定する。このステップＳＴ１
１０７でＮＯと判定された場合には、ステップＳＴ１１
０８でＴＰ＝ＴＰ（Ｑ，ＮＩ［Ｑ］）とし、ステップＳ
Ｔ１１０２へ戻る。ＹＥＳと判定された場合には、ステ
ップＳＴ１１０９でＱ＝Ｑ−１とし、ステップＳＴ１１
１０でＱ≦０であるかどうかを判定する。
【００４１】上記ステップＳＴ１１１０でＮＯと判定さ
れた場合には、ステップＳＴ１１１１でＮＩ［Ｑ］＝Ｎ
Ｉ［Ｑ］＋１とし、ステップＳＴ１１０７へ戻り、ＹＥ
Ｓと判定された場合には終了する。また、上記ステップ
ＳＴ１１０２でＮＯと判定された場合には、ステップＳ
Ｔ１１１２でＴＰを出力し、ステップＳＴ１１１３でＮ
Ｉ［Ｑ］＝ＮＩ［Ｑ］＋１としてステップＳＴ１１０７
へジャンプする。
れた場合には、ステップＳＴ１１１１でＮＩ［Ｑ］＝Ｎ
Ｉ［Ｑ］＋１とし、ステップＳＴ１１０７へ戻り、ＹＥ
Ｓと判定された場合には終了する。また、上記ステップ
ＳＴ１１０２でＮＯと判定された場合には、ステップＳ
Ｔ１１１２でＴＰを出力し、ステップＳＴ１１１３でＮ
Ｉ［Ｑ］＝ＮＩ［Ｑ］＋１としてステップＳＴ１１０７
へジャンプする。
【００４２】次に図２のステップＳＴ１０２において、
木構造記憶テーブル生成部１０２は、ステップＳＴ１０
１で生成された木構造群ＴＰ(i) （ｉ＝０，１，・・
・，ｎ：ｎ＋１＝ステップＳＴ１０１で生成された木構
造の個数）に対し、一つの木構造ＴＰ(i) に関する情報
を木構造記憶テーブル１０３の一つの組ｃi に格納す
る。次にステップＳＴ１０３において、木構造記憶テー
ブル１０３に対し、木構造記憶テーブル生成部１０２は
領域情報という属性を付加し、バウンディングボックス
（各組が保持している形状を包含する最小の直方体）を
その組の領域情報の属性値とする。但し、形状情報が存
在しない場合には、領域情報はＮＵＬＬとする。
木構造記憶テーブル生成部１０２は、ステップＳＴ１０
１で生成された木構造群ＴＰ(i) （ｉ＝０，１，・・
・，ｎ：ｎ＋１＝ステップＳＴ１０１で生成された木構
造の個数）に対し、一つの木構造ＴＰ(i) に関する情報
を木構造記憶テーブル１０３の一つの組ｃi に格納す
る。次にステップＳＴ１０３において、木構造記憶テー
ブル１０３に対し、木構造記憶テーブル生成部１０２は
領域情報という属性を付加し、バウンディングボックス
（各組が保持している形状を包含する最小の直方体）を
その組の領域情報の属性値とする。但し、形状情報が存
在しない場合には、領域情報はＮＵＬＬとする。
【００４３】次にステップＳＴ１０４において、図６に
示すように、ステップＳＴ１０３で得られた木構造記憶
テーブル１０３の組で領域情報がＮＵＬＬでないものを
ｃj、ｃj の領域情報をｒj （バウンディングボック
ス）、ｒj のＸＺ平面（Ｘ軸：幅方向、Ｚ軸：奥行き方
向）への投影図形をｐj とした時に、基準木構造生成部
１０４は、ｐj （１≦ｊ≦ｎ）を２次元図形の効率的な
管理を行う木構造でパケット型であるもの（一つの葉に
複数の図形データに関する情報を管理するもの）に逐次
投入することで木構造Ｔb を生成し、これを基準木構造
とする。
示すように、ステップＳＴ１０３で得られた木構造記憶
テーブル１０３の組で領域情報がＮＵＬＬでないものを
ｃj、ｃj の領域情報をｒj （バウンディングボック
ス）、ｒj のＸＺ平面（Ｘ軸：幅方向、Ｚ軸：奥行き方
向）への投影図形をｐj とした時に、基準木構造生成部
１０４は、ｐj （１≦ｊ≦ｎ）を２次元図形の効率的な
管理を行う木構造でパケット型であるもの（一つの葉に
複数の図形データに関する情報を管理するもの）に逐次
投入することで木構造Ｔb を生成し、これを基準木構造
とする。
【００４４】なお、２次元図形を効率的に管理する木構
造（範囲検索が０（ｌｏｇＮ）となるもの：Ｎ＝データ
数）は、例えば、中村泰明他３名による「多次元データ
の平衡木による管理−ＭＤ木の提案−」（電子情報通信
学会論文誌、Ｖｏｌ．Ｊ７１−Ｄ，Ｎｏ．９，１９８８
年９月）等に示されている公知のものである。
造（範囲検索が０（ｌｏｇＮ）となるもの：Ｎ＝データ
数）は、例えば、中村泰明他３名による「多次元データ
の平衡木による管理−ＭＤ木の提案−」（電子情報通信
学会論文誌、Ｖｏｌ．Ｊ７１−Ｄ，Ｎｏ．９，１９８８
年９月）等に示されている公知のものである。
【００４５】最後にステップＳＴ１０５において、木構
造結合部１０５が、基準木構造Ｔbと木構造記憶テーブ
ル１０３で記憶されている木構造群を結合することで与
えられた木構造と等価な仮想空間を表現した一つの木構
造Ｔopt を生成・出力して処理を終了する。
造結合部１０５が、基準木構造Ｔbと木構造記憶テーブ
ル１０３で記憶されている木構造群を結合することで与
えられた木構造と等価な仮想空間を表現した一つの木構
造Ｔopt を生成・出力して処理を終了する。
【００４６】このステップＳＴ１０５において、Ｔopt
を生成する処理手順の詳細について図７を用いて説明す
る。まず、基準木構造Ｔb の葉ｌk （１≦ｋ≦Ｌ，Ｌ＝
Ｔb の葉の個数）が保持している２次元図形をｐ（ｋ
m ）（ｍ＝１，２，・・・，Ｍ：Ｍ＝葉ｌk が管理して
いる２次元図形の個数）とした時に、ｌk をステップＳ
Ｔ１０１で生成した木構造Ｔｐ（ｋm ）（ｍ＝１，２，
・・・，Ｍ）に置き換える。次に、Ｔb の葉でないノー
ドを、その全ての子孫ノードが保持している形状情報の
バウンディングボックス情報をもったノード（例えば、
ＶＲＭＬにおけるＧｒｏｕｐノード）に置き換える。そ
して最後に、Ｔb の根にステップＳＴ１０１で生成した
木構造で形状情報を持たないものを追加する。
を生成する処理手順の詳細について図７を用いて説明す
る。まず、基準木構造Ｔb の葉ｌk （１≦ｋ≦Ｌ，Ｌ＝
Ｔb の葉の個数）が保持している２次元図形をｐ（ｋ
m ）（ｍ＝１，２，・・・，Ｍ：Ｍ＝葉ｌk が管理して
いる２次元図形の個数）とした時に、ｌk をステップＳ
Ｔ１０１で生成した木構造Ｔｐ（ｋm ）（ｍ＝１，２，
・・・，Ｍ）に置き換える。次に、Ｔb の葉でないノー
ドを、その全ての子孫ノードが保持している形状情報の
バウンディングボックス情報をもったノード（例えば、
ＶＲＭＬにおけるＧｒｏｕｐノード）に置き換える。そ
して最後に、Ｔb の根にステップＳＴ１０１で生成した
木構造で形状情報を持たないものを追加する。
【００４７】ブラウザは図８に示すように、根付き順序
木構造を深さ優先探索で走査し、ノード到達時に、その
ノードの子孫ノードが視野領域内に存在するか否かをノ
ードが保持しているバウンディングボックス情報をもと
に判定し、存在しない場合には子孫ノードへの探索は行
わない。例えば、図９においてノードＡの子孫ノードへ
の探索は、視野領域外なので行われないが、ノードＢの
子孫ノードへの探索は、視野領域内なので行われる。
木構造を深さ優先探索で走査し、ノード到達時に、その
ノードの子孫ノードが視野領域内に存在するか否かをノ
ードが保持しているバウンディングボックス情報をもと
に判定し、存在しない場合には子孫ノードへの探索は行
わない。例えば、図９においてノードＡの子孫ノードへ
の探索は、視野領域外なので行われないが、ノードＢの
子孫ノードへの探索は、視野領域内なので行われる。
【００４８】以上のように、この実施の形態１によれ
ば、与えられた木構造を、情報損失がないように複数の
木構造に分解し、分解した木構造群を走査ノード数が
（Ｏ（ｌｏｇＮ）：Ｎは図４で示された分解された木構
造の数）となるように再構築するため、映像情報以外の
情報を損失することなく描画時に操作するノード数を大
幅に減らすことができ、その結果、ブラウザの描画速度
が向上するという効果が得られる。
ば、与えられた木構造を、情報損失がないように複数の
木構造に分解し、分解した木構造群を走査ノード数が
（Ｏ（ｌｏｇＮ）：Ｎは図４で示された分解された木構
造の数）となるように再構築するため、映像情報以外の
情報を損失することなく描画時に操作するノード数を大
幅に減らすことができ、その結果、ブラウザの描画速度
が向上するという効果が得られる。
【００４９】この実施の形態をもとに実際の都市の約１
ｋｍ四方のＶＲＭＬファイル（バージョン２．０）を変
換したところ、ブラウザ（シリコングラフィックス社：
ｃｏｓｍｏｐ１ａｙｅｒ）の描画速度が３〜４倍向上し
た。
ｋｍ四方のＶＲＭＬファイル（バージョン２．０）を変
換したところ、ブラウザ（シリコングラフィックス社：
ｃｏｓｍｏｐ１ａｙｅｒ）の描画速度が３〜４倍向上し
た。
【００５０】実施の形態２．図１０はこの発明の実施の
形態２による木構造を用いた仮想空間データの変換装置
を示すブロック図であり、図１と対応する部分には図１
と同一符号を付してその説明を省略する。図１０におい
て、１０６は、木構造記憶テーブル１０３を各組が保持
しているテクスチャ情報に応じて、少なくとも同じテク
スチャを１種類は保持している組が同じテーブル内に存
在するように、複数のテーブルに分割する木構造記憶テ
ーブル分割部（木構造記憶テーブル分割手段）である。
形態２による木構造を用いた仮想空間データの変換装置
を示すブロック図であり、図１と対応する部分には図１
と同一符号を付してその説明を省略する。図１０におい
て、１０６は、木構造記憶テーブル１０３を各組が保持
しているテクスチャ情報に応じて、少なくとも同じテク
スチャを１種類は保持している組が同じテーブル内に存
在するように、複数のテーブルに分割する木構造記憶テ
ーブル分割部（木構造記憶テーブル分割手段）である。
【００５１】次に動作について説明する。図１１はこの
実施の形態２における木構造を用いた仮想空間データの
変換装置の処理手順を示すフローチャートである。まず
ステップＳＴ１０１及びＳＴ１０２の処理は、実施の形
態１の図２におけるステップＳＴ１０１及びＳＴ１０２
の処理と同じである。そしてステップＳＴ２０１におい
て、木構造記憶テーブル分割部１０６は、ステップＳＴ
１０２で生成された木構造記憶テーブル１０３を、各組
が使用しているテクスチャ情報に応じて複数のテーブル
に分割する。
実施の形態２における木構造を用いた仮想空間データの
変換装置の処理手順を示すフローチャートである。まず
ステップＳＴ１０１及びＳＴ１０２の処理は、実施の形
態１の図２におけるステップＳＴ１０１及びＳＴ１０２
の処理と同じである。そしてステップＳＴ２０１におい
て、木構造記憶テーブル分割部１０６は、ステップＳＴ
１０２で生成された木構造記憶テーブル１０３を、各組
が使用しているテクスチャ情報に応じて複数のテーブル
に分割する。
【００５２】ここでこのステップＳＴ２０１において、
木構造記憶テーブル分割部１０６が木構造記憶テーブル
１０３を分割する処理手順の詳細について、図１２のフ
ローチャートを用いて説明する。まずステップＳＴ２１
０１において、木構造記憶テーブル１０３内で使用され
ているテクスチャをテクスチャサイズについて降順にソ
ートしたものをｔｅｘ1，ｔｅｘ2 ，・・・，ｔｅｘq
とする。次にステップＳＴ２１０２において、テクスチ
ャ番号ＩをＩ＝１に初期設定し、ステップＳＴ２１０３
において、木構造記憶テーブル１０３の各組に選択フラ
グという属性を付加し、全ての組の選択フラグをＦＡＬ
ＳＥに設定する。
木構造記憶テーブル分割部１０６が木構造記憶テーブル
１０３を分割する処理手順の詳細について、図１２のフ
ローチャートを用いて説明する。まずステップＳＴ２１
０１において、木構造記憶テーブル１０３内で使用され
ているテクスチャをテクスチャサイズについて降順にソ
ートしたものをｔｅｘ1，ｔｅｘ2 ，・・・，ｔｅｘq
とする。次にステップＳＴ２１０２において、テクスチ
ャ番号ＩをＩ＝１に初期設定し、ステップＳＴ２１０３
において、木構造記憶テーブル１０３の各組に選択フラ
グという属性を付加し、全ての組の選択フラグをＦＡＬ
ＳＥに設定する。
【００５３】次にステップＳＴ２１０４において、木構
造記憶テーブル１０３の組でテクスチャｔｅｘI を使用
しており、選択フラグがＦＡＬＳＥであるものからなる
テーブルＴＢＬI を作成する。そしてステップＳＴ２１
０５で、上記ステップＳＴ２１０４で選択された組の選
択フラグをＴＲＵＥに設定する。次にステップＳＴ２１
０６において、Ｉ＝ｑであるかどうか判定し、ＹＥＳの
場合には、ステップＳＴ２１０７で、選択フラグがＦＡ
ＬＳＥである組（即ち、テクスチャを使用していない
組）からなるテーブルＴＢＬ0 を作成して処理を終了す
る。上記ステップＳＴ２１０６においてＮＯと判定され
た場合には、ステップＳＴ２１０８でＩ＝Ｉ＋１とイン
クリメントして、ステップＳＴ２１０４へ戻る。
造記憶テーブル１０３の組でテクスチャｔｅｘI を使用
しており、選択フラグがＦＡＬＳＥであるものからなる
テーブルＴＢＬI を作成する。そしてステップＳＴ２１
０５で、上記ステップＳＴ２１０４で選択された組の選
択フラグをＴＲＵＥに設定する。次にステップＳＴ２１
０６において、Ｉ＝ｑであるかどうか判定し、ＹＥＳの
場合には、ステップＳＴ２１０７で、選択フラグがＦＡ
ＬＳＥである組（即ち、テクスチャを使用していない
組）からなるテーブルＴＢＬ0 を作成して処理を終了す
る。上記ステップＳＴ２１０６においてＮＯと判定され
た場合には、ステップＳＴ２１０８でＩ＝Ｉ＋１とイン
クリメントして、ステップＳＴ２１０４へ戻る。
【００５４】次に図１１のステップＳＴ２０２におい
て、基準木構造生成部１０４は、各ＴＢＬj ごとに実施
の形態１の手順に従ってＴＢＬj に対応した仮想空間を
表現した木構造Ｔopt（ｊ）を生成する。そしてステッ
プＳＴ２０３において、図１３に示すように、木構造結
合部１０５がＴopt（０），Ｔopt（１），・・・Ｔopt
（ｑ）を結合して一つの木構造Ｔo pt を生成・出力して
処理を終了する。
て、基準木構造生成部１０４は、各ＴＢＬj ごとに実施
の形態１の手順に従ってＴＢＬj に対応した仮想空間を
表現した木構造Ｔopt（ｊ）を生成する。そしてステッ
プＳＴ２０３において、図１３に示すように、木構造結
合部１０５がＴopt（０），Ｔopt（１），・・・Ｔopt
（ｑ）を結合して一つの木構造Ｔo pt を生成・出力して
処理を終了する。
【００５５】以上のように、この実施の形態２によれ
ば、同じテクスチャを持っているテーブルをソートして
いるので、実施の形態１に比べ描画時におけるテクスチ
ャ（描画属性）のスイッチング回数を減少させることが
でき、ブラウザの描画速度を向上させることができると
いう効果が得られる。
ば、同じテクスチャを持っているテーブルをソートして
いるので、実施の形態１に比べ描画時におけるテクスチ
ャ（描画属性）のスイッチング回数を減少させることが
でき、ブラウザの描画速度を向上させることができると
いう効果が得られる。
【００５６】実施の形態３．図１４はこの発明の実施の
形態３による木構造を用いた仮想空間データの変換装置
を示すブロック図であり、図１０と対応する部分には図
１０と同一符号を付してその説明を省略する。図１４に
おいて、１０７は木構造結合部１０５で生成した木構造
内の形状情報をメッシュ化するメッシュ形状生成部（メ
ッシュ形状生成手段）である。
形態３による木構造を用いた仮想空間データの変換装置
を示すブロック図であり、図１０と対応する部分には図
１０と同一符号を付してその説明を省略する。図１４に
おいて、１０７は木構造結合部１０５で生成した木構造
内の形状情報をメッシュ化するメッシュ形状生成部（メ
ッシュ形状生成手段）である。
【００５７】次に動作について説明する。図１５はこの
実施の形態３における木構造を用いた仮想空間データの
変換装置の処理手順を示すフローチャートである。この
実施の形態では、上記実施の形態２において、ステップ
ＳＴ２０３で生成した木構造Ｔopt 内の各形状情報を、
ステップＳＴ３０１において、メッシュ形状生成部１０
７がメッシュ化するようにしたものである。
実施の形態３における木構造を用いた仮想空間データの
変換装置の処理手順を示すフローチャートである。この
実施の形態では、上記実施の形態２において、ステップ
ＳＴ２０３で生成した木構造Ｔopt 内の各形状情報を、
ステップＳＴ３０１において、メッシュ形状生成部１０
７がメッシュ化するようにしたものである。
【００５８】以上のように、この実施の形態３によれ
ば、形状をメッシュ化することでグラフィックスエンジ
ンの描画コストが軽減するように与えられた木構造と等
価な仮想空間を表現した木構造を生成することができ、
ブラウザの描画速度を向上させることができるという効
果が得られる。
ば、形状をメッシュ化することでグラフィックスエンジ
ンの描画コストが軽減するように与えられた木構造と等
価な仮想空間を表現した木構造を生成することができ、
ブラウザの描画速度を向上させることができるという効
果が得られる。
【００５９】この実施の形態３では、実施の形態２にメ
ッシュ形状生成部１０７を追加しているが、実施の形態
１にメッシュ形状生成部１０７を追加しても、同様の効
果が得られる。
ッシュ形状生成部１０７を追加しているが、実施の形態
１にメッシュ形状生成部１０７を追加しても、同様の効
果が得られる。
【００６０】実施の形態４．図１６はこの発明の実施の
形態４による木構造を用いた仮想空間データの変換装置
を示すブロック図であり、図１と対応する部分には図１
と同一符号を付してその説明を省略する。図１６におい
て、１０８は空間検索に特化した木構造を生成する方法
を複数種類記憶しておき、基準木構造生成部１０４にお
いて空間検索に特化した木構造を生成する際の木構造
を、ユーザの指示により選択する基準木構造生成方法選
択部（基準木構造生成方法選択手段）である。
形態４による木構造を用いた仮想空間データの変換装置
を示すブロック図であり、図１と対応する部分には図１
と同一符号を付してその説明を省略する。図１６におい
て、１０８は空間検索に特化した木構造を生成する方法
を複数種類記憶しておき、基準木構造生成部１０４にお
いて空間検索に特化した木構造を生成する際の木構造
を、ユーザの指示により選択する基準木構造生成方法選
択部（基準木構造生成方法選択手段）である。
【００６１】次に動作について説明する。図１７はこの
実施の形態４における木構造を用いた仮想空間データの
変換装置の処理手順を示すフローチャートである。この
実施の形態におけるステップＳＴ１０１からＳＴ１０３
までの処理は、上記実施の形態１の図２におけるステッ
プＳＴ１０１からＳＴ１０３までの処理と同じである。
ステップＳＴ４０１において、基準木構造生成方法選択
部１０８が、あらかじめ用意しておいた空間検索に特化
した木構造の中からユーザの指示により木構造を選択す
る。そしてステップＳＴ１０４において、基準木構造生
成部１０４が、選択された木構造を用いて基準木構造を
生成する。ステップＳＴ１０５の処理は実施の形態１と
同様である。
実施の形態４における木構造を用いた仮想空間データの
変換装置の処理手順を示すフローチャートである。この
実施の形態におけるステップＳＴ１０１からＳＴ１０３
までの処理は、上記実施の形態１の図２におけるステッ
プＳＴ１０１からＳＴ１０３までの処理と同じである。
ステップＳＴ４０１において、基準木構造生成方法選択
部１０８が、あらかじめ用意しておいた空間検索に特化
した木構造の中からユーザの指示により木構造を選択す
る。そしてステップＳＴ１０４において、基準木構造生
成部１０４が、選択された木構造を用いて基準木構造を
生成する。ステップＳＴ１０５の処理は実施の形態１と
同様である。
【００６２】空間検索に特化した木構造としては、実施
の形態１で用いた２次元図形を効率的に管理する木構造
の他に、３次元空間を効率的に管理する木構造（例えば
ｏｃｔｒｅｅ、文献：Ｃ．Ｌ．Ｊａｃｋｉｎｓ ａｎｄ
Ｓ．Ｌ．Ｔａｎｉｍｏｎｏ，“Ｏｃｔ−Ｔｒｅｅｓ
ａｎｄ Ｔｈｅｉｒ Ｕｓｅ ｉｎ Ｒｅｐｒｅｓｅｎ
ｔｉｎｇ Ｔｈｒｅｅ−Ｄｉｍｅｎｓｉｏｎａｌ Ｏｂ
ｊｅｃｔｓ”，Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ
ａｎｄ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，Ｎｏｖ．
１９８０，ｐｐ．２４９−２７０）がある。変換対象と
なる仮想空間データが都市空間のように、平面方向（Ｘ
Ｙ平面）の広がりに比べ、高さ方向（Ｚ軸）の広がりが
非常に小さいような空間である場合には、空間を２次元
的に管理する方が効率的である。
の形態１で用いた２次元図形を効率的に管理する木構造
の他に、３次元空間を効率的に管理する木構造（例えば
ｏｃｔｒｅｅ、文献：Ｃ．Ｌ．Ｊａｃｋｉｎｓ ａｎｄ
Ｓ．Ｌ．Ｔａｎｉｍｏｎｏ，“Ｏｃｔ−Ｔｒｅｅｓ
ａｎｄ Ｔｈｅｉｒ Ｕｓｅ ｉｎ Ｒｅｐｒｅｓｅｎ
ｔｉｎｇ Ｔｈｒｅｅ−Ｄｉｍｅｎｓｉｏｎａｌ Ｏｂ
ｊｅｃｔｓ”，Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ
ａｎｄ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，Ｎｏｖ．
１９８０，ｐｐ．２４９−２７０）がある。変換対象と
なる仮想空間データが都市空間のように、平面方向（Ｘ
Ｙ平面）の広がりに比べ、高さ方向（Ｚ軸）の広がりが
非常に小さいような空間である場合には、空間を２次元
的に管理する方が効率的である。
【００６３】一方、大規模な分子モデルや科学シミュレ
ーション結果の３次元視覚化データのように、高さ方向
についても平面方向と同程度の広がりを持つ仮想空間デ
ータについては、３次元的に管理する方が効率的であ
り、変換対象となる仮想空間データの空間特性に応じて
ユーザが基準木構造を生成する際に使用する木構造を選
択する方が、実施の形態１に比べ、よりブラウザの描画
速度が向上する木構造を生成することができる。
ーション結果の３次元視覚化データのように、高さ方向
についても平面方向と同程度の広がりを持つ仮想空間デ
ータについては、３次元的に管理する方が効率的であ
り、変換対象となる仮想空間データの空間特性に応じて
ユーザが基準木構造を生成する際に使用する木構造を選
択する方が、実施の形態１に比べ、よりブラウザの描画
速度が向上する木構造を生成することができる。
【００６４】この実施の形態４では、実施の形態１に基
準木構造生成方法選択部１０８を追加しているが、実施
の形態２に基準木構造生成方法選択部１０８を追加して
も、同様の効果が得られる。
準木構造生成方法選択部１０８を追加しているが、実施
の形態２に基準木構造生成方法選択部１０８を追加して
も、同様の効果が得られる。
【００６５】実施の形態５．この発明の実施の形態５で
は、上記実施の形態１から実施の形態４において空間検
索に特化した木構造として、２次元空間を複数の小空間
に分割し、その小空間内のデータをかためて管理する木
構造を用いることで、図１８に示すように仮想空間を管
理するものである。
は、上記実施の形態１から実施の形態４において空間検
索に特化した木構造として、２次元空間を複数の小空間
に分割し、その小空間内のデータをかためて管理する木
構造を用いることで、図１８に示すように仮想空間を管
理するものである。
【００６６】この実施の形態では木構造の実装が容易で
あり、また仮想空間内において３次元形状が均等に分布
し、かつ仮想空間の高さ方向の広がりが非常に小さい場
合には実施の形態１で用いた２次元図形を効率的に管理
する木構造（範囲検索、すなわち走査ノード数が０（ｌ
ｏｇＮ））と同等の検索効率を実現することができると
いう効果が得られる。
あり、また仮想空間内において３次元形状が均等に分布
し、かつ仮想空間の高さ方向の広がりが非常に小さい場
合には実施の形態１で用いた２次元図形を効率的に管理
する木構造（範囲検索、すなわち走査ノード数が０（ｌ
ｏｇＮ））と同等の検索効率を実現することができると
いう効果が得られる。
【００６７】実施の形態６．この発明の実施の形態６で
は、上記実施の形態１から実施の形態４において空間検
索に特化した木構造として、３次元空間を複数の小空間
に分割し、その小空間内のデータをかためて管理する木
構造を用いることで、図１９に示すように仮想空間を管
理するものである。
は、上記実施の形態１から実施の形態４において空間検
索に特化した木構造として、３次元空間を複数の小空間
に分割し、その小空間内のデータをかためて管理する木
構造を用いることで、図１９に示すように仮想空間を管
理するものである。
【００６８】この実施の形態でも木構造の実装が容易で
あり、また仮想空間内において３次元形状が均等に分布
する場合には実施の形態４で用いた３次元図形を効率的
に管理する木構造（範囲検索、すなわち走査ノード数が
０（ｌｏｇＮ））と同等の検索効率を実現することがで
きるという効果が得られる。
あり、また仮想空間内において３次元形状が均等に分布
する場合には実施の形態４で用いた３次元図形を効率的
に管理する木構造（範囲検索、すなわち走査ノード数が
０（ｌｏｇＮ））と同等の検索効率を実現することがで
きるという効果が得られる。
【００６９】実施の形態７．この発明の実施の形態７で
は、上記実施の形態４において空間検索に特化した木構
造として、２次元空間をデータの分布状況に応じて領域
分割することで、動的なデータに対しても静的なデータ
に対しても、ともに良好な領域分割を実現する木構造を
複数用意するものである。これら木構造として、実施の
形態１で用いた木構造の他に、例えば、大沢、坂内：
「良好な動特性を持つ多次元データ管理構造の一提案」
（電子情報通信学会論文誌、Ｖｏｌ．Ｊ６６−Ｄ、Ｎ
ｏ．１０、１９８３）等があり、これら木構造には、実
装の容易さ、検索効率、木の生成時間等でそれぞれ特徴
があることから、複数用意することで目的に応じて最適
な木構造を選択することができる。
は、上記実施の形態４において空間検索に特化した木構
造として、２次元空間をデータの分布状況に応じて領域
分割することで、動的なデータに対しても静的なデータ
に対しても、ともに良好な領域分割を実現する木構造を
複数用意するものである。これら木構造として、実施の
形態１で用いた木構造の他に、例えば、大沢、坂内：
「良好な動特性を持つ多次元データ管理構造の一提案」
（電子情報通信学会論文誌、Ｖｏｌ．Ｊ６６−Ｄ、Ｎ
ｏ．１０、１９８３）等があり、これら木構造には、実
装の容易さ、検索効率、木の生成時間等でそれぞれ特徴
があることから、複数用意することで目的に応じて最適
な木構造を選択することができる。
【００７０】実施の形態８．この発明の実施の形態８で
は、上記実施の形態４において空間検索に特化した木構
造として、３次元空間をデータの分布状況に応じて領域
分割することで、動的なデータに対しても静的なデータ
に対しても、ともに良好な領域分割を実現する木構造を
複数用意するものである。これら木構造として、実施の
形態４で用いた木構造の他に、“Ｊａｎｓｅｎ、Ｆ．，
Ｄａｔａ Ｓｔｒｕｃｔｕｒｅｓ ｆｏｒ Ｒａｙ Ｔ
ｒａｃｉｎｇ、Ｄａｔａ Ｓｔｒｕｃｔｕｒｅｓ ｆｏ
ｒ Ｒａｓｔｅｒ Ｇｒａｐｈｉｃｓ、ｐ５７−７３、
１９８６”等があり、これら木構造には、実装の容易
さ、検索効率、木の生成時間等でそれぞれ特徴があるこ
とから、複数用意することで目的に応じて最適な木構造
を選択することができる。
は、上記実施の形態４において空間検索に特化した木構
造として、３次元空間をデータの分布状況に応じて領域
分割することで、動的なデータに対しても静的なデータ
に対しても、ともに良好な領域分割を実現する木構造を
複数用意するものである。これら木構造として、実施の
形態４で用いた木構造の他に、“Ｊａｎｓｅｎ、Ｆ．，
Ｄａｔａ Ｓｔｒｕｃｔｕｒｅｓ ｆｏｒ Ｒａｙ Ｔ
ｒａｃｉｎｇ、Ｄａｔａ Ｓｔｒｕｃｔｕｒｅｓ ｆｏ
ｒ Ｒａｓｔｅｒ Ｇｒａｐｈｉｃｓ、ｐ５７−７３、
１９８６”等があり、これら木構造には、実装の容易
さ、検索効率、木の生成時間等でそれぞれ特徴があるこ
とから、複数用意することで目的に応じて最適な木構造
を選択することができる。
【００７１】
【発明の効果】以上のように、この発明によれば、情報
損失を生じることなく、描画時に操作するノード数を大
幅に減らすことができるので、ブラウザの描画速度が向
上する効果がある。
損失を生じることなく、描画時に操作するノード数を大
幅に減らすことができるので、ブラウザの描画速度が向
上する効果がある。
【００７２】また、この発明によれば、同じテクスチャ
を持っているテーブルをソートしているので、描画時に
おけるテクスチャ（描画属性）のスイッチング回数を減
少させることができ、ブラウザの描画速度を向上させる
ことができる効果がある。
を持っているテーブルをソートしているので、描画時に
おけるテクスチャ（描画属性）のスイッチング回数を減
少させることができ、ブラウザの描画速度を向上させる
ことができる効果がある。
【図１】 この発明の実施の形態１による木構造を用い
た仮想空間データの変換装置を示すブロック図である。
た仮想空間データの変換装置を示すブロック図である。
【図２】 この発明の実施の形態１による処理手順を示
すフローチャートである。
すフローチャートである。
【図３】 木構造分解の処理手順を示すフローチャート
である。
である。
【図４】 木構造分解の説明図である。
【図５】 ノード結合の説明図である。
【図６】 ３次元形状と領域情報・投影図形の関係につ
いての説明図である。
いての説明図である。
【図７】 基準木構造からシーン木構造への変換の説明
図である。
図である。
【図８】 描画時におけるブラウザのノード走査手順の
説明図である。
説明図である。
【図９】 ノード走査とバウンディングボックスの関係
の説明図である。
の説明図である。
【図１０】 この発明の実施の形態２による木構造を用
いた仮想空間データの変換装置を示すブロック図であ
る。
いた仮想空間データの変換装置を示すブロック図であ
る。
【図１１】 この発明の実施の形態２による処理手順を
示すフローチャートである。
示すフローチャートである。
【図１２】 木構造記憶テーブル分割の処理手順を示す
フローチャートである。
フローチャートである。
【図１３】 Ｔopt （０），Ｔopt （１），・・・Ｔ
opt （ｑ）からＴopt生成の説明図である。
opt （ｑ）からＴopt生成の説明図である。
【図１４】 この発明の実施の形態３による木構造を用
いた仮想空間データの変換装置を示すブロック図であ
る。
いた仮想空間データの変換装置を示すブロック図であ
る。
【図１５】 この発明の実施の形態３による処理手順を
示すフローチャートである。
示すフローチャートである。
【図１６】 この発明の実施の形態４による木構造を用
いた仮想空間データの変換装置を示すブロック図であ
る。
いた仮想空間データの変換装置を示すブロック図であ
る。
【図１７】 この発明の実施の形態４による処理手順を
示すフローチャートである。
示すフローチャートである。
【図１８】 ２次元空間を複数の小空間に分割し、その
小空間内のデータをかためて管理する木構造による仮想
空間管理の説明図である。
小空間内のデータをかためて管理する木構造による仮想
空間管理の説明図である。
【図１９】 ３次元空間を複数の小空間に分割し、その
小空間内のデータをかためて管理する木構造による仮想
空間管理の説明図である。
小空間内のデータをかためて管理する木構造による仮想
空間管理の説明図である。
【図２０】 従来の木構造を用いた仮想空間データの変
換装置を示すブロック図である。
換装置を示すブロック図である。
【図２１】 従来の処理手順を示すフローチャートであ
る。
る。
【図２２】 従来の相違水準決定手順を示すフローチャ
ートである。
ートである。
【図２３】 従来の形状関連情報テーブルの結合操作手
順の説明図である。
順の説明図である。
【図２４】 従来の形状関連情報テーブルから木構造を
生成する処理手順を示すフローチャートである。
生成する処理手順を示すフローチャートである。
【図２５】 従来における深さ５の直線上の木構造の説
明図である。
明図である。
【図２６】 従来における木構造の生成手順の説明図で
ある。
ある。
１０１ シーン木構造分解部（シーン木構造分解手
段）、１０２ 木構造記憶テーブル生成部（木構造記憶
テーブル生成手段）、１０３ 木構造記憶テーブル、１
０４ 基準木構造生成部（基準木構造生成手段）、１０
５ 木構造結合部（木構造結合手段）、１０６ 木構造
記憶テーブル分割部（木構造記憶テーブル分割手段）、
１０７ メッシュ形状生成部（メッシュ形状生成手
段）、１０８ 基準木構造生成方法選択部（基準木構造
生成方法選択手段）。
段）、１０２ 木構造記憶テーブル生成部（木構造記憶
テーブル生成手段）、１０３ 木構造記憶テーブル、１
０４ 基準木構造生成部（基準木構造生成手段）、１０
５ 木構造結合部（木構造結合手段）、１０６ 木構造
記憶テーブル分割部（木構造記憶テーブル分割手段）、
１０７ メッシュ形状生成部（メッシュ形状生成手
段）、１０８ 基準木構造生成方法選択部（基準木構造
生成方法選択手段）。
Claims (9)
- 【請求項１】 木構造を用いた仮想空間データを入力
し、与えられた木構造を、木構造自身に組み込まれた情
報を破壊することなく、各木構造が元の木構造の情報の
一部を保持している木構造群に分解するシーン木構造分
解手段と、 上記分解された木構造群に対し、一つの木構造に関する
情報を一つの組として記憶する木構造記憶テーブルを生
成すると共に、上記各組の形状の領域情報としてバウン
ディングボックス情報を付加する木構造記憶テーブル生
成手段と、 上記バウンディングボックス情報をもとに、空間検索に
特化した基準木構造を生成する基準木構造生成手段と、 上記基準木構造生成手段により生成された基準木構造と
上記木構造記憶テーブルに記憶されている木構造群を結
合する木構造結合手段とを備えたことを特徴とする木構
造を用いた仮想空間データの変換装置。 - 【請求項２】 木構造を用いた仮想空間データを入力
し、与えられた木構造を、木構造自身に組み込まれた情
報を破壊することなく、各木構造が元の木構造の情報の
一部を保持している木構造群に分解するシーン木構造分
解手段と、 上記分解された木構造群に対し、一つの木構造に関する
情報を一つの組として記憶する木構造記憶テーブルを生
成すると共に、上記各組の形状の領域情報としてバウン
ディングボックス情報を付加する木構造記憶テーブル生
成手段と、 上記木構造記憶テーブルを各組が保持しているテクスチ
ャ情報に応じて少なくとも同じテクスチャを１種類は保
持している組が同じテーブル内に存在するように複数の
テーブルに分割する木構造記憶テーブル分割手段と、 上記分割された木構造記憶テーブルごとに、上記バウン
ディングボックス情報をもとに、空間検索に特化した基
準木構造を生成する基準木構造生成手段と、 上記基準木構造生成手段により生成された基準木構造と
上記分割された木構造記憶テーブルに記憶されている木
構造群を結合する木構造結合手段とを備えたことを特徴
とする木構造を用いた仮想空間データの変換装置。 - 【請求項３】 木構造結合手段で生成された木構造内の
形状情報をメッシュ化するメッシュ形状生成手段を備え
たことを特徴とする請求項１又は請求項２記載の木構造
を用いた仮想空間データの変換装置。 - 【請求項４】 複数の空間検索に特化した基準木構造を
生成する方法を記憶し、記憶されている複数の方法の中
から、ユーザの指示により所定の方法を選択する基準木
構造生成方法選択手段を備え、 基準木構造生成手段が木構造記憶テーブルの各組が管理
している形状のバウンディングボックス情報をもとに、
上記基準木構造生成方法選択手段が選択した上記所定の
空間検索に特化した基準木構造を生成する方法を使用
し、空間検索に特化した基準木構造を生成することを特
徴とする請求項１記載の木構造を用いた仮想空間データ
の変換装置。 - 【請求項５】 複数の空間検索に特化した基準木構造を
生成する方法を記憶し、記憶されている複数の方法の中
から、ユーザの指示により所定の方法を選択する基準木
構造生成方法選択手段を備え、 基準木構造生成手段が、分割された木構造記憶テーブル
ごとに、木構造記憶テーブルの各組が管理している形状
のバウンディングボックス情報をもとに、上記基準木構
造生成方法選択手段が選択した上記所定の空間検索に特
化した基準木構造を生成する方法を使用し、空間検索に
特化した基準木構造を生成することを特徴とする請求項
２記載の木構造を用いた仮想空間データの変換装置。 - 【請求項６】 空間検索に特化した木構造として、２次
元空間を複数の小空間に分割し、その小空間内のデータ
をかためて管理する木構造を用いたことを特徴とする請
求項１から請求項５のうちのいずれか１項記載の木構造
を用いた仮想空間データの変換装置。 - 【請求項７】 空間検索に特化した木構造として、３次
元空間を複数の小空間に分割し、その小空間内のデータ
をかためて管理する木構造を用いたことを特徴とする請
求項１から請求項５のうちのいずれか１項記載の木構造
を用いた仮想空間データの変換装置。 - 【請求項８】 空間検索に特化した木構造として、２次
元空間をデータの分布状況に応じて領域分割する木構造
を用いたことを特徴とする請求項１から請求項５のうち
のいずれか１項記載の木構造を用いた仮想空間データの
変換装置。 - 【請求項９】 空間検索に特化した木構造として、３次
元空間をデータの分布状況に応じて領域分割する木構造
を用いたことを特徴とする請求項１から請求項５のうち
のいずれか１項記載の木構造を用いた仮想空間データの
変換装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP23283097A JP3602304B2 (ja) | 1997-08-28 | 1997-08-28 | 木構造を用いた仮想空間データの変換装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP23283097A JP3602304B2 (ja) | 1997-08-28 | 1997-08-28 | 木構造を用いた仮想空間データの変換装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH1173526A true JPH1173526A (ja) | 1999-03-16 |
| JP3602304B2 JP3602304B2 (ja) | 2004-12-15 |
Family
ID=16945465
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP23283097A Expired - Fee Related JP3602304B2 (ja) | 1997-08-28 | 1997-08-28 | 木構造を用いた仮想空間データの変換装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3602304B2 (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2004023394A1 (en) * | 2002-09-04 | 2004-03-18 | Honda Giken Kogyo Kabushiki Kaisha | Environmental reasoning using geometric data structure |
| JP2010176596A (ja) * | 2009-01-30 | 2010-08-12 | Fujitsu Ltd | 可視化対象データの構造化装置、方法、及びプログラム、可視化対象データの可視化装置、方法、及びプログラム |
| WO2012066603A1 (ja) * | 2010-11-18 | 2012-05-24 | 三菱電機株式会社 | ３次元画像表示装置及び３次元画像表示プログラム |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR102004048B1 (ko) * | 2017-10-25 | 2019-07-25 | 광운대학교 산학협력단 | 가상 현실을 위한 공간 재구성 방법 및 가상 로드맵 결정 방법 및 이를 수행하는 공간 재구성 장치 |
-
1997
- 1997-08-28 JP JP23283097A patent/JP3602304B2/ja not_active Expired - Fee Related
Cited By (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2004023394A1 (en) * | 2002-09-04 | 2004-03-18 | Honda Giken Kogyo Kabushiki Kaisha | Environmental reasoning using geometric data structure |
| US7030875B2 (en) | 2002-09-04 | 2006-04-18 | Honda Motor Company Ltd. | Environmental reasoning using geometric data structure |
| JP2010176596A (ja) * | 2009-01-30 | 2010-08-12 | Fujitsu Ltd | 可視化対象データの構造化装置、方法、及びプログラム、可視化対象データの可視化装置、方法、及びプログラム |
| US8819016B2 (en) | 2009-01-30 | 2014-08-26 | Fujitsu Limited | Apparatus, method, and program for structuring visualization object data; and apparatus, method, and program for visualizing visualization object data |
| WO2012066603A1 (ja) * | 2010-11-18 | 2012-05-24 | 三菱電機株式会社 | ３次元画像表示装置及び３次元画像表示プログラム |
| CN103221979A (zh) * | 2010-11-18 | 2013-07-24 | 三菱电机株式会社 | 三维图像显示装置以及三维图像显示程序 |
| JP5274717B2 (ja) * | 2010-11-18 | 2013-08-28 | 三菱電機株式会社 | ３次元画像表示装置及び３次元画像表示プログラム |
| US9311747B2 (en) | 2010-11-18 | 2016-04-12 | Mitsubishi Electric Corporation | Three-dimensional image display device and three-dimensional image display program |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3602304B2 (ja) | 2004-12-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5467444A (en) | Method of three-dimensional display of object-oriented figure information and system thereof | |
| Greuter et al. | Real-time procedural generation ofpseudo infinite'cities | |
| US8612040B2 (en) | Automated derivative view rendering system | |
| US5448696A (en) | Map information system capable of displaying layout information | |
| US6184897B1 (en) | Compressed representation of changing meshes and method to decompress | |
| US8497860B2 (en) | Spatial decomposition methods using bit manipulation | |
| US6154215A (en) | Method and apparatus for maintaining multiple representations of a same scene in computer generated graphics | |
| US20080225048A1 (en) | Culling occlusions when rendering graphics on computers | |
| JPH10208077A (ja) | グラフィック画像を表示上にレンダリングするための方法および画像レンダリングシステム、ならびにグラフィック画像を表示上に生成するための方法 | |
| JPH1091649A (ja) | 構造化情報空間での情報検索方法及び装置 | |
| JPH10255081A (ja) | 画像処理方法及び画像処理装置 | |
| CN116842121A (zh) | 一种多层级瓦片联合的大规模数字孪生场景构建方法 | |
| WO2004075110A2 (en) | Image display, manipulation, and spatial decomposition methods | |
| JP3602304B2 (ja) | 木構造を用いた仮想空間データの変換装置 | |
| Garg et al. | GIOTTO3D: A system for visualizing hierarchical structures in 3D | |
| Hanson et al. | Overview of the SRI cartographic modeling environment | |
| JPH0969163A (ja) | コンピュータグラフィックスモデルのポリゴン重なり抽出方法と、ポリゴンのグループ化方法及び装置 | |
| 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 | |
| Fellner et al. | Modeling of and navigation in complex 3D documents | |
| Lee et al. | Adaptive synthesis of distance fields | |
| Bochicchio et al. | Extending Web applications with 3D features | |
| Tamada et al. | An efficient 3D object management and interactive walkthrough for the 3D facility management system | |
| Erikson et al. | Hierarchical levels of detail for fast display of large static and dynamic environments | |
| JP3764191B2 (ja) | ３次元画像処理装置 |
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 |