(57)【要約】データベース内のオブジェクトの表現画像を表示するための３次元グラフィック環境をオブジェクトのデータベースと関連メタデータに応じて区分する装置および方法について説明する。本装置および方法によると、オブジェクトのデータベースはデータオブジェクトメタデータ(20)から導出された階層ツリーで表現される。ツリーは、親ノード(23,24,25)と、それらに関連付けられた子ノード(24,25,26)と、データオブジェクトノード(26)とを含み、全てのノードに重みが関連付けられる。未分割の３次元グラフィック環境に対応する領域(27)を所定の親ノード(23)に事前に割り当てる。次いで、ツリー内で少なくとも２つの子ノードを有する各親ノードについて、その領域を子ノードのそれぞれに対応した複数の領域へと、それらの子ノードの重みに比例するようにして再帰的に区分する。
2005508056.tif 000002
【特許請求の範囲】
【請求項１】
データベース内のオブジェクトの表現画像を表示するための３次元グラフィック環境を区分する方法であって、
前記オブジェクトのデータベースをオブジェクトメタデータから導出された階層ツリーで表現することと（２０）、
所定の親ノードを未分割のグラフィック環境に対応する領域に事前に割り当てることと（２１）、
前記所定のノードから開始して、前記ツリー内で少なくとも２つの子ノードを有する各親ノードに対応する各領域について該領域を、関連する子ノードのそれぞれに対応し、各子ノードのそれぞれの重みに比例した複数の領域へと、再帰的に区分することと（２２）
からなる方法。
【請求項２】
前記再帰的に区分することは、
ａ）前記親ノードの前記関連付けられた子ノードを１以上のノードからそれぞれなるＮ個のグループへと、各グループの合計正規化ノード重みＷNにそれぞれ応じて、各グループのＷNが比率Ｒ＝１／Ｎに近くなるように分割することと（３１）、
ｂ）前記親ノードに関連付けられた前記領域を区分し、隔壁により作成された領域を、各グループの合計重みに応じて各グループに割り当てることと（３３）、
ｃ）前記親ノードに関連する全グループについて、各グループに含まれるノードが１つになるまでａ）およびｂ）を繰り返すことと（３４）
をさらに含む、請求項１の方法。
【請求項３】
前記ＮがＮ＝２である、請求項２の方法。
【請求項４】
前記再帰的に区分することは、横方向隔壁と縦方向隔壁のうちのいずれか一方を選択することをさらに含む、請求項２の方法。
【請求項５】
前記再帰的に区分することは、前記横方向隔壁および前記縦方向隔壁のそれぞれによって作成される領域の縦横比に応じて、前記横方向隔壁と前記縦方向隔壁のうちのいずれか一方を選択することをさらに含む、請求項４の方法。
【請求項６】
前記再帰的に区分することは、横方向隔壁と縦方向隔壁のうちの最小の縦横比を有するいずれか一方を選択することをさらに含む、請求項５の方法。
【請求項７】
データベース内のオブジェクトの表現画像を表示するための３次元グラフィック環境を区分する装置であって、
オブジェクトメタデータからオブジェクトのデータベースを表現する階層ツリーを導出するツリー導出器（４０、５０）と、
前記ツリーの各ノードについて関連付けられた重みを判定する重み判定器（４１、５１）と、
前記グラフィック環境に関連付けられた領域を複数の領域に区分し、該複数の領域がノードの重みに比例するようにする、領域区分器（４２）と、
からなる装置。
【請求項８】
親に関連付けられた子ノードを１以上のノードからなるＮ個のグループへと、合計正規化ノード重みにそれぞれ応じて分割する、ノードグループ化器（５２）をさらに含む、請求項７の装置。
【請求項９】
前記領域区分器は、縦方向に区分するための縦方向区分器（５３Ｂ）と、横方向に区分するための横方向区分器（５３Ａ）とをさらに含む、請求項７の装置。
【請求項１０】
前記領域区分器は、前記縦方向区分器および前記横方向区分器のそれぞれによって作成される領域の縦横比を判定し、該縦横比に応じて縦方向隔壁と横方向隔壁のうちのいずれか一方を選択する、縦横比判定器（５３Ｃ）をさらに含む、請求項９の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は３次元グラフィック環境のレイアウトを設計する技術に関し、特に本開示は、データオブジェクトデータベースおよびデータオブジェクトに関連付けられたメタデータに応じて３次元グラフィック環境を区分する装置および方法を提供する。
【背景技術】
【０００２】
データベースは多くの場合、製品、美術品、遺物、書籍などのような、多数の物品に関する情報を記憶するのに使用される。データベースは、その大きさが原因でデータベースに記憶された情報の検索や閲覧が困難になる場合がある。多くの用途において、とりわけ不慣れなコンピュータユーザや閲覧者にとって、それらのデータベースの閲覧を直観的かつ簡単な手順にすることが特に求められている。例えば、オンラインショッピングはその利便性が主な理由で人気を得てきた。特に、昼夜問わず何時でも自分の自宅や職場で快適に素早くショッピングを行なうことができる。その結果、多くの小売ストアがインターネット上にウェブサイトを持ち、ユーザが製品を選びそれを購入できるようにしている。しかしながら、そのウェブサイトで製品を見つけることがコンピュータの知識をあまり持たない一般の顧客にとって困難なものであれば、オンラインショッピングの利便性は大幅に減少することになる。
【０００３】
３次元グラフィック環境は、情報やデータベースの閲覧や検索を直感的な方法で行なうのに利用されてきた（小売店のウェブサイトなどにおいて）。具体的には、３次元グラフィック環境を用いると、ユーザは仮想空間内を直観的に移動し、仮想空間内で物品を容易に見つけ出して閲覧することが可能になる。３次元グラフィック環境を作成するためには、その環境内に物品を論理的に分類して陳列する働きをもつ複数の３次元領域（例えば部屋など）に、その３次元グラフィック環境を分割すなわち区分するのが一般的である。実際、そのように環境を区分し、区分された環境内に物品を分散配置することで、その環境内を検索するのが容易になる。
【０００４】
現在のところ、３次元グラフィック環境を区分するアルゴリズムは、区分された各領域内に配置される物品の数が変化しない、静的区分環境に適するように設計されている。そのため、区分は一回しか決める必要がなく、アルゴリズムの複雑さはほとんど問題にならないか、全く問題にもならない。しかしながら、環境が絶えず再区分され、物品の数、グループ分け、配置などに変更が加えられる可能性がある動的区分環境の場合、区分アルゴリズムは、その３次元グラフィック環境をレンダリングする全体のプロセスに与える影響を最小限にする必要がある。
【０００５】
本発明は、データベース内の複数のオブジェクトを閲覧するための３次元グラフィック環境を生成する装置および方法であり、詳しくは、３次元グラフィック環境を美観的に美しく論理的かつ簡単な方法で分割し、その環境の閲覧能力と操作性をさらに向上させる装置および方法である。
【発明の開示】
【課題を解決するための手段】
【０００６】
オブジェクトのデータベースを表す画像を表示する３次元グラフィック環境を区分する装置および方法を説明する。
【０００７】
本方法の一実施形態によると、オブジェクトのデータベースは、データオブジェクトメタデータから導出された階層ツリーで表現される。所定の親ノードを未分割の３次元グラフィック環境に対応する領域に事前に割り当てる。次いで、その所定の親ノードから開始して、そのツリー内で少なくとも２つの子ノードを有する各親ノードについて、その領域をそれらの子ノードのそれぞれに対応した複数の領域へと、各領域が子ノードの重みに比例するように再帰的に区分する。
【０００８】
本発明の一実施形態による装置は、ツリー導出器と、重み判定器と、領域区分器とを含む。ツリー導出器は、オブジェクトメタデータからオブジェクトのデータベースを表現する階層ツリーを導出する。重み判定器は、ツリーの各ノードについて重みを判定してその重みを領域区分器に渡し、グラフィック環境に関連する領域が階層ツリーのノードの重みに比例した複数の領域に分割されるようにする。
【発明を実施するための最良の形態】
【０００９】
データオブジェクトの表現画像を表示するための３次元グラフィック環境を、データオブジェクトとデータオブジェクトに対応するメタデータに従って区分する装置および方法について説明する。本発明は概して、データオブジェクトに関連付けられたメタデータから導出される階層ツリーに応じて区分けを実施する装置および方法に関する。階層ツリーは、データベース内のデータオブジェクトのグループ分けを少なくとも１つの選択されたメタデータの種類に従って定義するのに使用される。階層ツリーは、データオブジェクトノードの重みに少なくとも部分的に依存して重み付けされた複数のノードを含む。そして、そのノードの重みを用いて３次元グラフィック環境がノード重みに比例した領域に分割される。
【００１０】
本明細書の説明によると、データオブジェクトは、有形もしくは無形のオブジェクトまたは有形もしくは無形の要素に対応してデータベース内に記憶されるデータとして広く定義される。データオブジェクトの種類の例としては、画像データ、音声データ、ワープロデータ、ビデオデータ、および３Ｄモデルなどがあるが、それらに限定はしない。オブジェクトまたは要素の種類の例としては、映画ビデオ、ＣＤ、美術品、電子ワープロ文書、個人的な電子記録、およびコマーシャル製品カタログなどがあるが、それらに限定はしない。例えば、オブジェクトの種類が映画ビデオである場合、その種類の特定のオブジェクトは特定の映画である。
【００１１】
各データオブジェクトは、メタデータと呼ばれる関連データを有する。このメタデータは、データオブジェクトそれ自体とは異なる他の任意のデータに対応し、そのデータオブジェクトを説明するか、または、データオブジェクトに関係する。各データオブジェクトは、異なる種類のメタデータを有する場合がある。例えば、オブジェクトの種類が映画ビデオである場合、メタデータの種類には、映画のタイトル、映画監督、映画の公開日、映画俳優、および映画のジャンル（例えば、コメディ、ドラマ）などに対応するデータが含まれる。一方、オブジェクトの種類が美術品である場合、メタデータの種類には、その美術品のタイトルおよび美術品の流派（例えば、モダン派、印象派）などが含まれる。メタデータは、データオブジェクトと共に記憶することもできるし、データオブジェクトと関連メタデータとの間にリンクを作るようにして個別に記憶してもよい。
【００１２】
一般に、データベース内に記憶される複数のデータオブジェクトは、それらに関連付けられたデータオブジェクトまたはメタデータに関して、何らかの方法で論理的に表示、分類、グループ分け、及び／又は配置できるように、関連付けられている。例えば、データベース内に記憶された映画は、閲覧者がそのデータを特定の映画監督で検索できるように、映画監督でグループ分けされる場合がある。
【００１３】
本発明によると、データベース内に記憶されたデータオブジェクトの表現画像が３次元グラフィック環境内に表示され、そのデータベースを閲覧したいユーザに対し、データオブジェクトを直観的に閲覧する機能が提供される。本発明によると、表現画像は、データオブジェクトに関連する、またはデータオブジェクトを表すテキストラベル、自然画像、グラフィック画像、文書およびファイルフォルダの画像、ビデオ画像、３次元モデル、または任意の種類の視覚データとして具体化することができる。さらに、表現画像は、ユーザによって直接または間接的に選択されたときに対話的なものにすることができる。例えば、ユーザは３次元モデルとして具体化された表現画像を回転させることができ、それによってユーザは、そのモデルの他の眺めを更に得ることができる。あるいは、ビデオ画像として具体化された表現画像は、３次元グラフィック環境中でユーザがその表現画像に近づいたときに再生を始めることもできる。さらに、表現画像を直接または間接的に選択し、関連マルチメディアデータに更にアクセスすることもできる。例えば２次元表現画像を選択することで、そのデータオブジェクトに関連付けられたオーディオクリップにアクセスしたり、その２次元画像に対応する３次元モデルにアクセスしたり、ビデオシーケンスにアクセスしたりすることなどができる。
【００１４】
３次元画像をレンダリングして表示するシステムの一例を図１に示す。このシステムは、グラフィックス処理ユニット１０、レンダリングエンジン１１、ユーザ出力１２、ユーザ入力１３、およびメモリ１４を含む。グラフィックス処理ユニット１０は、グラフィックスの画像処理の分野で既知のように、データオブジェクトデータ１０Ａを受け取り、該データオブジェクトの表現画像を含む３次元グラフィック環境に対応する３次元画像データ１０Ｂを生成する。レンダリングエンジン１１は、画像データ１０Ｂを受け取ってレンダリングデータ１１Ａを生成し、ユーザ出力１２を作動させる。例えば、レンダリングデータ１１Ａは、モニタ（図示せず）を作動させ、表現画像を含む３次元グラフィック環境を表示する。ユーザ入力１３は、ユーザが３次元環境と対話できるようにするための、ユーザと３次元環境との間のインターフェースを提供する。例えば、ユーザ入力１３により、ユーザは、表示されたカーソルをキーボードまたはマウスを用いて移動させることによる３次元環境内での視点の変更が可能になる。他の種類のユーザ入力１３としては、ジョイスティックや感圧スクリーンなどが含まれるが、それらに限定はしない。グラフィックス処理ユニット１０がデータオブジェクトの表現画像を生成してもよいし、表現画像データはメモリ１４内に記憶され、データオブジェクトデータベースにリンクされてもよい。
【００１５】
図２Ａに示すような本発明の方法の第１の実施形態によれば、オブジェクトのデータベースは、オブジェクトメタデータから導出された階層ツリーによって表現される（ブロック２０）。所定のノードを未分割の３次元グラフィック環境に対応する領域に事前に割り当てる（ブロック２１）。次いで、その所定のノードから開始して、そのツリー内で少なくとも２つの子ノードを有する各親ノードに対応する各領域について、その領域をそれらの子ノードのそれぞれに対応した複数の領域へと、各領域が子ノードの重みに比例するように再帰的に区分する（ブロック２２）。
【００１６】
図２Ｂは、階層ツリーで表現されたデータベースの例を示す。このツリーは、複数のノード２３、２４Ａ、２４Ｂ、２５Ａ〜２５Ｃ、２５Ｄ〜２５Ｆ、および２６を含む。ツリーのノードは、ツリー中の他のノードとの関係に応じて、親ノードに分類されることも、子ノードに分類されることもある。例えば、ノード２３は子ノード２４Ａおよび２４Ｂに対して親ノードであり、ノード２４Ａは子ノード２５Ａ〜２５Ｃに対して親ノードであり、ノード２４Ｂは子ノード２５Ｄ〜２５Ｆに対して親ノードである。ノード２６はデータオブジェクトノードであり、各ノードがデータベース内のデータオブジェクトのうちの１つに対応する。したがって、ノード２５Ａ〜２５Ｆはそれぞれ、対応する１群のデータオブジェクト子ノードの親ノードになっている。
【００１７】
また、ノード２３〜２５はそれぞれ、データオブジェクトノード２６を分類するのに使用される様々なメタデータの種類に対応する。例えば、ノード２４は、製品の機能の種類に対応し、計算型製品と画像処理型製品とを含む。計算型製品ノードの下にあるのは、ノートブック、ハンドヘルド、およびデスクトップを含む、機器型ノードの第１の集合である。画像処理型製品ノードの下にあるのは、スキャナ、プリンタ、およびカメラを含む、機器型ノードの第２の集合である。それらの機器型ノードのそれぞれの下にあるのは、データベース内のデータオブジェクトに対応した実際の各製品である。
【００１８】
ツリーの各ノードは、そのノードに関連付けられたデータオブジェクトの重み付けによって決まる重みを有する。所与のノードの重みは、そのツリー内の連続した経路を全てデータオブジェクトノードまで下方にたどり、その連続した経路に沿ってその所与のノードに関連付けられたデータオブジェクトの重みを結合したものを判定することにより判定される。例えば、この例において各データオブジェクトノードの重みが１であると仮定した場合、ノード２５Ａの重みはＷ＝４であり、ノード２５Ｂの重みはＷ＝２であり、ノード２５Ｃの重みはＷ＝３であり、ノード２５Ｄの重みはＷ＝４であり、ノード２５Ｅの重みはＷ＝２であり、ノード２５Ｆの重みはＷ＝５である。したがって、ノード２４Ａおよび２４Ｂのそれぞれからデータオブジェクトノード２６までツリー内の連続した経路を全てたどることにより、ノード２４Ａの重みはＷ＝９になり、ノード２４Ｂの重みはＷ＝１１になる。本発明の装置および方法によれば、ノードは、ユーザの好みやシステムのデフォルト設定、またはその他のノード重み付け方法に従って、さまざまな方法で重み付けすることができる点に注意して欲しい。例えば、オブジェクトノードの重みは１より大きくてもよく、オブジェクトノード以外のノード（例えば２３〜３５）の中には、それに関連付けられたデータオブジェクトの重みとは無関係の重み要素を更に有しているものがあってよい。そのため、ノードの重み判定は、そのノードに関連するデータオブジェクトの重みだけでなく、ツリーのノードを最初に重み付けする方法によっても異なる場合がある。その他、ノードの重みは、そのノードに関連するデータオブジェクトの重みに間接的に関係する場合もある。
【００１９】
図２Ｃは、図２Ｂに示した階層ツリーを用い、本発明の方法に従って区分された３次元グラフィック環境のレイアウトに対応する２次元領域の例である。この例では、データベースのオブジェクトを電気製品、それらの機能、および機器タイプからなる３つのメタデータの種類に従ってグループ分けすることにより、オブジェクトのデータベースをメタデータから導出された階層ツリーで表現する。次に、ツリーの最上位のノードであるノード２３を未分割の３次元グラフィック環境に事前に割り当てる。この例の場合、未分割の３次元環境は、頂点Ａ、Ｉ、Ｊ、Ｄ（図２Ｃ）によって画定された２次元領域２７に対応する。ノード２３は、ノード２４Ａおよび２４Ｂを含む少なくとも２つの子ノードを有する親ノードである。子ノード２４Ａおよび２４Ｂは、重みＷ＝９およびＷ＝１１をそれぞれ有する。次に、ノード２３から開始して、領域２７を隔壁２７Ａで分割し、ノード２４Ａおよび２４Ｂの重みにそれぞれ比例した２つの領域を形成する。一方の領域は計算型製品に対応し、他方の領域は画像処理型製品に対応する。具体的には、計算型製品に対応する領域は領域２７全体の９／２０であり、画像処理型製品に対応する領域は領域２７全体の１１／２０である。同様に、ツリー内の次の親ノードであるノード２４Ａに関連する計算型製品領域（図２Ｃ）は、隔壁２８Ａおよび２８Ｂにより、ノード２５Ａ〜２５Ｃの重みに応じて比例分割される。また、最後の親ノード２４Ｂに関連付けられた画像処理型製品領域（図２Ｃ）は、隔壁２９Ａおよび２９Ｂにより、ノード２５Ｄ〜２５Ｆの重みに応じて比例分割される。
【００２０】
図３は、３次元グラフィック環境を区分する方法の第２の実施形態を示す。まず、オブジェクトのデータベースをオブジェクトメタデータから導出された階層ツリーで表現し（ブロック３０）、未分割の３次元グラフィック環境に対応する領域に所定のノードを事前に割り当てる（ブロック３１）。
次に、この所定のノードから開始して、少なくとも２つの子ノードを有する各親ノードの子ノードを、１以上のノードからそれぞれなるＮ個のグループに分割する（ブロック３２）。例えばＮ＝２の場合、図２Ｂに示す例を参照すると、親ノード２４Ａの子ノード２５Ａ〜２５Ｃは２つのグループに分割される。それらのノードの分割は、各グループで合計正規化重みＷNが、比率Ｒ＝１／Ｎに近くなるように行なう（ブロック３２）。すなわち、この場合はＲ＝０．５である。なお、ノード２５Ａ、２５Ｂ、２５Ｃの正規化重みはそれぞれ、ＷN＝４／９、ＷN＝２／９、およびＷN＝３／９である。以下の表は、それら３つのノードを２つのノードグループにグループ化する３つの可能なグループ化と、それら２つのグループ（グループ１およびグループ２）それぞれの合計正規化重み（重み１および重み２）とを示したものである。
【００２１】
【表１】
2005508056.tif 000003
【００２２】
表１は、グループ化番号２がグループ１およびグループ２を有し、グループ１がノード２５Ａを含み、グループ２がノード２５Ｂとノード２５Ｃを含む場合、グループ１およびグループ２それぞれの合計正規化重みが比率０．５に近くなることを示している。表１に示したように可能なすべてのグループ化を評価する必要は、必ずしも無いということに注意して欲しい。ツリーのノード数が多いときは特にそうである。例えば、一実施形態では、このツリーに図示したのと同じ左から右への並びを維持するグループ化しか考慮しない場合がある。上記例を参照すると、グループ化番号３は左から右への並びを維持しないので、グループ化番号１およびグループ化番号＃２だけが、可能なグループ化として考慮される。
【００２３】
次に、子ノードのグループに関連する親ノードに対応する領域を、各グループの比に応じて区分する（ブロック３３）。この場合、親ノードに関連付けられた領域は計算型製品領域であり、計算型製品領域は隔壁２８Ａによって、合計比率（すなわち４／９および５／９）のそれぞれに応じて２つの領域に比例分割される。小さい方の領域はノード２５Ａ（すなわちグループ１）に対応し、大きい方の領域はノード２５Ｂおよび２５Ｃ（すなわちグループ２）に対応する。図２Ｃに示すように、隔壁２８Ａは、コーナＡ、Ｂ、Ｃ、Ｄによって画定された計算型製品に対応する領域を２つの領域Ａ、Ｂ、Ｆ、ＥおよびＥ、Ｆ、Ｃ、Ｄに分割する。領域Ａ、Ｂ、Ｆ、Ｅは、ノートブック製品グループ（ノード２５Ａ、グループ１）に割り当てられる。領域Ｅ、Ｆ、Ｃ、Ｄは、ハンドヘルド製品およびデスクトップ製品（ノード２５Ｂおよび２５Ｃ、グループ２）に割り当てられる。
【００２４】
図３に示す方法によると、ブロック３２〜３３は、親ノードに関連する全グループについて、各グループに含まれるノードが１つになるまで繰り返される。グループ２が２つのノード２５Ｂおよび２５Ｃを含む例の場合、ブロック３４によると、このグループに対してブロック３２〜３３が繰り返され、グループ２が２つのグループに分割される（ブロック３２）。グループ２にはノードが２つしかなく、このグループを分割する方法は１つしかないので、ノードの重みがこのグループの分割方法を決めることはない。次に、その領域を各グループの正規化重みに応じて区分する（ブロック３２）。この例では、ノード２５Ｂの正規化重みが２／５であり、ノード２５Ｃの正規化重みが３／５である。したがって、領域の２／５がノード２５Ｂに割り当てられ、領域の３／５がノード２５Ｃに割り当てられるように、領域Ｅ、Ｆ、Ｃ、Ｄを隔壁２８Ｂによって２つの領域に比例分割する。図２Ｃに示すように、領域Ｅ、Ｇ、Ｈ、Ｄはハンドヘルド製品（ノード２５Ｂ）に割り当てられ、領域Ｇ、Ｆ、Ｃ、Ｈはデスクトップ製品（ノード２５Ｃ）に割り当てられる。画像処理型製品領域Ｂ、Ｉ、Ｊ、Ｃも、計算型製品領域と同じ方法で隔壁２９Ａおよび２９Ｂによって比例分割される。
【００２５】
図４は、３次元グラフィック環境をオブジェクトのデータベースおよび対応するオブジェクトメタデータに応じて区分する装置の第１の実施形態を示す。この装置は、ツリー導出器４０、重み判定器４１、および領域区分器４２を含む。ツリー導出器４０は、データベースおよびオブジェクトメタデータに接続され、オブジェクトのデータベースを表す階層ツリーをオブジェクトメタデータに基づいて導出する。重み判定器４１は、ツリー導出器４０から階層ツリー情報を得る。この階層ツリー情報は、少なくとも、親ノード情報、子ノード情報、およびオブジェクトノード情報と共に、それらのノードの何らかの初期重みを含む。重み判定器４１は、各親ノードの重みを判定し、それらの重みを領域区分器４２に提供する。領域区分器４２は、重み判定器４１から提供されたノードの重みを用いて、少なくとも２つの子ノードを有する各親ノードに関連する各領域を、関連付けられた子ノードの重みのそれぞれに対応する複数の領域に比例分割することで、隔壁位置情報を判定する。
【００２６】
図５は、３次元グラフィック環境を区分する装置の第２の実施形態を示す。この装置は、ツリー導出器５０、重み判定器５１、ノードグループ化器５２、および領域区分器５３を含む。ツリー導出器５０は導出した階層ツリー情報を重み判定器５１に提供する。続いて、重み判定器５１が各ノードの重みを判定し、その重みをノードグループ化器５２に提供する。ノードグループ化器は、親ノードを特定し、各親ノードの子ノードを、各ノードグループの合計正規化ノード重みが比率Ｒ＝１／Ｎに近づくように、１以上のノードからなるＮ個のグループに分割する。領域区分器５３は、親ノードに関連付けられた領域を子ノードの各グループの正規化重みに応じて区分する方法を決定する。
【００２７】
この実施形態によると、親ノードに関連付けられた領域を横方向隔壁または縦方向隔壁で分割することができる。図２Ｃを参照すると、２８Ａおよび２９Ａは横方向隔壁であり、２７Ａ、２８Ｂ、および２９Ｂは縦方向隔壁である。領域区分器は、横方向区分器５３Ａ、縦方向区分器５３Ｂ、および縦横比判定器５３Ｃを含む。隔壁によって作成されることになる領域の縦横比に応じて、横方向隔壁と縦方向隔壁のいずれか一方が、その領域の分割に使用される。一般に３次元グラフィック環境の場合、正方形の部屋の方が細長い部屋よりも美観的に美しいため、３次元グラフィック環境は、比較的正方形に近い領域に、すなわち縦横比が比較的小さい領域に分割するのが好ましい。そのため、縦横比判定器５３Ｃは、縦方向隔壁および横方向隔壁のそれぞれによって作成されることになる各領域の縦横比を判定し、各領域について、最小の縦横比を作り出す隔壁を選択してその領域を区分する。代替実施形態として、選択された縦横比の何らかの関数となる面積を作り出す隔壁の種類（すなわち縦方向または横方向）を選択する実施形態も可能である。さら他の実施形態としては、他の選択基準に応じて、縦方向でもなく横方向でもない隔壁の種類（図示せず）を選択することもできる。例えば隔壁は、直角以外の角度であってもよいし、直線的な隔壁でなくてもよい。
【００２８】
図４および図５に示した装置は、ハードウェア、ソフトウェア、ファームウェアのうちのいずれの組み合わせでも実施することができる。
【００２９】
上記の説明では、本発明を完全に理解してもらう目的で、多数の具体的な詳細について説明した。しかしながら、当業者であれば、本発明を実施する上でそれらの特定の詳細を用いる必要が必ずしもないことは、明らかであろう。その他、既知の技術については、本発明を不必要に分かりにくくすることを避けるため、詳細に説明していない。
【００３０】
また、本発明の要素は特定の実施形態と共に説明されているが、当然ながら、本発明は他にも様々な方法で実施できることができる。したがって、例示目的で図示・説明した特定の実施形態に限定の意図は全くない。それら特定の実施形態の詳細を参照することに、本発明にとって重要だと考えられる特徴のみを列挙した特許請求の範囲を限定する意図はない。
【図面の簡単な説明】
【００３１】
【図１】３次元グラフィック環境をレンダリングして表示する従来技術のシステムを示す図である。
【図２Ａ】本発明により３次元グラフィック環境を区分する方法の第１の実施形態を示す図である。
【図２Ｂ】関連メタデータに応じてデータオブジェクトのデータベースを表現する階層ツリーの例を示す図である。
【図２Ｃ】図２Ａに示す本発明の方法に従って区分された３次元グラフィック環境の例を示す図である。
【図３】本発明による３次元グラフィック環境を区分する方法の第２の実施形態を示す図である。
【図４】３次元グラフィック環境を区分する装置の第１の実施形態を示す図である。
【図５】３次元グラフィック環境を区分する装置の第２の実施形態を示す図である。
【図１】
2005508056.tif 000004
【図２Ａ】
2005508056.tif 000005
【図２Ｂ】
2005508056.tif 000006
【図２Ｃ】
2005508056.tif 000007
【図３】
2005508056.tif 000008
【図４】
2005508056.tif 000009
【図５】
2005508056.tif 000010
【国際公開パンフレット】
2005508056.tif 000011
2005508056.tif 000012
2005508056.tif 000013
2005508056.tif 000014
2005508056.tif 000015
2005508056.tif 000016
2005508056.tif 000017
2005508056.tif 000018
2005508056.tif 000019
2005508056.tif 000020
2005508056.tif 000021
2005508056.tif 000022
2005508056.tif 000023
2005508056.tif 000024
2005508056.tif 000025
2005508056.tif 000026
2005508056.tif 000027
2005508056.tif 000028
2005508056.tif 000029
2005508056.tif 000030
2005508056.tif 000031
【国際調査報告】
2005508056.tif 000032
2005508056.tif 000033