JP4418468B2 - ３次元オブジェクトのデジタル表現を操作するための方法およびシステム - Google Patents

Description

本発明は、３次元オブジェクトのデジタル表現の操作に関する。より詳細には、本発明は、２次元カーソルの動きによる３次元仮想ビルディング・ブロック・モデルのコンピュータによって実施される操作に関し、仮想ビルディング・ブロック・モデルは、一組の結合規則に従って仮想ビルディング・ブロックを別の仮想ビルディング・ブロックと結合するための、いくつかの結合要素をそれぞれが含む、複数の仮想ビルディング・ブロックを含む。

仮想現実のコンピュータ支援モデル化は、コンピュータ・システムにおいて、物理的オブジェクトのモデルを作成する、モデルを操作する、また、それ以外の形で、物理的オブジェクトのモデルを扱う作業である。

第１の観点では、仮想現実のモデル化は、アイディアが現実世界で実際に実施される前に、アイディアを視覚化することを可能にするという点で、興味深い主題である。仮想現実モデルが、変更するのが十分に容易である場合、物理的オブジェクトを開発し、改良するプロセスにおいて、同一のプロセスが、現実世界で実行されなければならなかったとした状況と比べて、多くの時間を節約することができる。現実世界でオブジェクトに塗装を施す単純な作業は、容易に数時間かかる可能性がある一方で、コンピュータは、数ミリ秒内、または数秒内でモデルに新たな色を適用することができる。

第２の観点では、仮想現実のモデル化は、現実世界に存在するオブジェクトのモデルを作成し、コンピュータを介して、モデルを視覚化して、操作することを可能にするという点で興味深い。このため、オブジェクトのモデルは、異なる目的で、例えば、高度なドキュメンテーションの目的で、格納することができる。

コンピュータ支援仮想現実モデル化に関する莫大な量のアプリケーションが存在するが、特別なアプリケーションは、エンターテイメント向け、または教育向けに仮想現実モデル化を使用することである。

物理的な組み立て玩具セットの様々なタイプのモデル化概念が、そうしたものとして知られている。特に、モジュールまたは半モジュールの概念を使用する概念が、非常に普及している。通常、それらの概念は、あらかじめ製造された要素のモジュールに従って、何らかの所定の形で互いに結合することができる、一組のあらかじめ製造された要素を提供する。そのような組み立て玩具セットの例が、ＬＥＧＯという名称の下で入手できる、一組のプラスチック玩具組み立て要素である。

コンピュータ上で３次元（３Ｄ）のオブジェクトまたはシーンの表現を操作する際、３Ｄのオブジェクトの位置付け、選択、または動きが、２次元で動作している入力デバイスを使用して、例えば、マウス・パッド上のコンピュータ・マウスの２次元（２Ｄ）の動きを使用して実行されることは、一般的な問題である。さらに、コンピュータの表示領域も２次元である。詳細には、コンピュータ・スクリーンの２Ｄ表示領域上のすべての選択された位置が、選択された２Ｄ位置に対応する２Ｄ表示領域上への射影を有する３Ｄ空間内の複数の位置に対応する。ユーザの意図と一致する可能性が高い位置の１つを特定することは、問題である。

３Ｄコンピュータ・グラフィックスでオブジェクトを操作するのにより適しているコンピュータ・インタフェース・デバイスを開発する相当な取り組みが行われてきたが、そのようなツールは、依然、広く使用されておらず、特に、ホーム・エンターテイメント向け、教育向けなどに使用されるコンピュータ・システムに関連して広く使用されていない。

仮想ビルディング・ブロックの位置付けが行われる既知の組み立てゲームは、通常、オブジェクトの動きおよび回転の自由度、またはオブジェクトを他のオブジェクトと結合する仕方の点で、制限されている。

米国特許第６４２６７４５号が、３Ｄの動きが、動きを一度に１つの平面、または１つの方向に制限することによって実行され、それにより、３Ｄの動きを制限された動きの連続として、例えば、３Ｄ座標系のｘ方向の動き、ｙ方向の動き、最後にｚ方向の動きの連続として実行する、マウスを使用して３Ｄグラフィックス・オブジェクトを操作する方法を説明する。

慣用のユーザ・インタフェースを使用した、３Ｄシーンにおけるビルディング・ブロックの配置、および３Ｄ構造へのビルディング・ブロックの結合が、高いレベルの技能および訓練を要求する面倒なプロセスであることは、前述した先行技術のシステムの問題である。詳細には、子供およびティーンエージャのエンターテイメントおよび教育の文脈において、これは、問題である。というのは、子供は、しばしば、延々と続く操作プロセスを実行するのに十分な運動技能、または要求される忍耐力がまだ、発達していないからである。その結果、子供は、仮想組み立てゲームへの関心をすぐに失う可能性がある。
米国特許第６４２６７４５号 米国特許第６３８９３７５号 Ｄａｖｉｄ Ｈ．Ｅｂｅｒｌｙ，「３Ｄ Ｇａｍｅ Ｅｎｇｉｎｅ Ｄｅｓｉｇｎ」，Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ，２００１

以上、およびその他の問題が、２次元のカーソルの動きによって３次元仮想ビルディング・ブロック・モデルを操作する、コンピュータによって実施される方法によって解決され、仮想ビルディング・ブロック・モデルは、一組の結合規則に従って仮想ビルディング・ブロックを別の仮想ビルディング・ブロックと結合するためのいくつかの結合要素をそれぞれが含む複数の仮想ビルディング・ブロックを含み、方法は、
−３次元座標系において、いくつかの前記仮想ビルディング・ブロックを含む構造のデジタル表現を提供すること、
−前記構造の射影を表す２次元コンピュータ表示領域内のカーソルの動きにより、構造に結合されるべき第１の仮想ビルディング・ブロックの２次元射影の位置付けを行い、２次元位置座標をもたらすこと、
−２次元位置座標から、３次元座標系における第１の仮想ビルディング・ブロックのいくつかの３次元候補位置を算出すること、および
−結合規則、および所定の一組の位置評定（格付け）規則に基づき、前記候補位置の１つを選択すること、および
−選択された候補位置で、第１のビルディング・ブロックを前記構造に結合することを含む。

このため、ユーザに直観的な形で、２Ｄ表示領域内の位置を対応する３Ｄ位置にするように分解して、ユーザが、３Ｄ仮想構造を操作するのを大幅により容易にする、３次元オブジェクトのデジタル表現を操作するための効率的な方法が提供される。ユーザは、単に、２Ｄスクリーン領域内で新たなビルディング・ブロックの位置付けを行い、これにより、２つの方向に沿って、その新たなビルディング・ブロックの座標を単に調整することができる。次に、２Ｄ配置と整合性のある複数の可能な３Ｄ位置の適切な１つが、いくつかの結合規則、および一組の位置評定規則に従って自動的に特定される。

詳細には、所定の一組の位置評定規則に従って、いくつかの候補位置の１つを選択することにより、プロセスは、ユーザの意図と一致する可能性が高い３Ｄシーン内の位置に、ビルディング・ブロックを位置付けることをもたらす。

結合要素に関する結合規則と矛盾する位置が拒否されることは、さらなる利点である。例えば、組み立てシステムにおいて、相当に様々な異なる結合要素、例えば、異なる形状および／またはサイズの突起部、ならびに突起部の対応するものと連結するための、異なるタイプの空隙が存在することが可能である。

新たなビルディング・ブロックが、２Ｄ配置と整合性のある候補３Ｄ位置に配置されるものと想定して、新たなビルディング・ブロックの結合要素の近くの候補結合要素を選択し、その候補結合要素との有効な結合が可能であるかどうかを試験することにより、コンピュータ・スクリーン上の新たなビルディング・ブロックの２Ｄ配置が正しく分解されて、３Ｄモデル内の３Ｄ位置になる。さらに、一組の結合規則に従って、無効な結合を生じさせる、例えば、異なるタイプの空隙に対する突起部の結合を生じさせる２Ｄ−３Ｄ分解が、回避される。

このため、仮想ビルディング・ブロックは、対応する現実世界の組み立てセットの物理的限界と整合性があり、それにより、仮想組み立てゲームの教育的価値が向上させられることは、利点である。詳細には、仮想組み立ては、同一タイプのビルディング・ブロックから物理的モデルを組み立てることにより、物理的モデルに後に移すことができる。

方法が、動きおよび結合の大きい自由度を与えることは、さらなる利点である。例えば、ビルディング・ブロックは、任意の方向で位置付け、結合することができる。詳細には、水平面と垂直面の両方において、他のビルディング・ブロックとの結合が可能である。さらに、ビルディング・ブロックは、ビルディング・ブロックが、例えば、垂直軸または水平軸を中心に回転させられた場合でも、正しく位置付けが行われる。

好ましくは、グラフィック表現の位置付けは、ポインティング・デバイスなどの適切な入力デバイスを介してユーザから受け取られた、制御コマンドによって制御される。例えば、位置付けは、「ドラッグ・アンド・ドロップ」操作、「クリック・ドラッグ・リリース」操作などの、標準のカーソル操作技術として実行されることが可能である。

好ましい実施形態では、いくつかの３次元候補位置を算出する工程は、３次元座標系において、第１の仮想ビルディング・ブロックのいくつかの候補の向きを算出することをさらに含む。回転させられたビルディング・ブロックの候補位置を得るように第１のビルディング・ブロックを回転させることにより、ユーザによって制御された２Ｄ位置が分解されて、３Ｄ配置、および３次元の向きになり、これにより、単に、２Ｄスクリーン領域内の単一のカーソル制御に依拠して、３Ｄシーンにおける配置の６つすべての自由度が算出される。第１のビルディング・ブロックの回転が、ユーザによって選択された向きを中心とした所定の空間角度に制限される場合、ビルディング・ブロックを完全に反転させることなどの、回転を混同することが回避され、これにより、ユーザが、向きが分からなくなることが回避される。この実施形態では、ユーザが、仮想ビルディング・ブロックの向きを選択することを可能にすることにより、さらなる方向づけを実現することができる。

好ましい実施形態では、方法は、
−第１の仮想ビルディング・ブロックの結合要素の射影のまわりの所定の近傍内に、２次元表示領域内で射影をそれぞれが有する、前記構造のいくつかの候補結合要素を特定すること、
−結合規則、および所定の一組の位置評定規則に基づき、前記候補結合要素の１つを選択すること、および
−第１の仮想ビルディング・ブロックと前記構造の間の結合が、その一組の結合規則に従って有効である場合、少なくとも選択された候補結合要素を介して、第１の仮想ビルディング・ブロックを構造と結合することをさらに含む。

このため、候補位置を検出する計算上、効率的な方法が提供される。というのは、検出は、個々の結合要素の位置および特性だけに依拠するからである。さらに、ユーザの意図と一致する可能性が最も高い３Ｄ位置を選択するための効率的な選択機構も提供される。

評定が、以下の評定規則の１つまたは複数を含む場合、結合要素の特に有利な評定が提供される。すなわち、
−仮想カメラ位置からの候補結合要素の距離に関して、候補結合要素を評定すること、
−現在の仮想カメラ位置から見えない候補結合要素を破棄すること、および
−第１の仮想ビルディング・ブロックの対応する結合要素の２次元射影までの、候補結合要素の２次元射影の距離に関して、候補結合要素を評定することである。

詳細には、信頼できる３Ｄ位置付けは、評定規則が、仮想カメラ位置からの距離の組み合わせ、および第１の仮想ビルディング・ブロックの対応する結合要素の２次元射影までの、候補結合要素の２次元射影のそれぞれの距離に基づく場合、達せられる。

好ましい実施形態では、前記構造のデジタル表現は、各仮想ビルディング・ブロックに関して、結合要素をそれぞれが表すいくつかの格子点をそれぞれが含む、仮想ビルディング・ブロックの表面の少なくとも１つに対応する、いくつかの規則的な格子を含む。これにより、ビルディング・ブロックが多数の結合要素を有し、異なるタイプの結合要素さえ有している場合でも、多数の異なるビルディング・ブロックの３Ｄ位置の正しい分解、および正しい相互結合を可能にする体系的な枠組みが提供される。

好ましくは、第１の仮想ビルディング・ブロックの結合要素の射影のまわりの前記所定の近傍は、対応する規則的な格子の近隣の格子点間の距離に相当する、直径などの、直線寸法を有する。その結果、予測可能であり、ユーザにトランスペアレントな３Ｄ分解およびビルディング・ブロック結合をもたらす、正確できめ細かい、ユーザによって制御された配置が提供される。
さらなる好ましい諸実施形態は、従属請求項で開示する。

本発明は、以上、および以下で説明する方法、データ処理システム、およびさらなる製品手段を含む、異なる形で実施することができ、それぞれが、最初に述べた方法に関連して説明した便益および利点の１つまたは複数をもたらし、それぞれが、最初に述べた方法に関連して説明した、好ましい諸実施形態に対応する、１つまたは複数の好ましい諸実施形態を有する。

以上、および以下で説明する方法の特徴は、ソフトウェアで実施することができ、データ処理システム、またはコンピュータ実行可能命令の実行によって生じさせられる、他の処理手段において実行されることが可能であることに留意されたい。命令は、記憶媒体から、またはコンピュータ網を介して別のコンピュータから、ＲＡＭなどのメモリの中に読み込まれるプログラム・コード手段であることが可能である。代替として、説明する特徴は、ソフトウェアの代わりに、またはソフトウェアとの組み合わせで、ハードワイヤド回路によって実施してもよい。

本発明は、プログラムがコンピュータ上で実行された際、以上、および以下に説明する方法のすべての工程を実行するためのプログラム・コード手段を含むコンピュータ・プログラムにさらに関する。コンピュータ・プログラムは、コンピュータ可読記憶媒体、搬送波などとして実現されたデータ信号などとして実現されることが可能である。

本発明は、コンピュータ・プログラムがコンピュータ上で実行された際、以上、および以下に説明する方法を実行するための、コンピュータ可読媒体上に格納されたプログラム・コード手段を含むコンピュータ・プログラム製品にさらに関する。
本発明を、好ましい実施形態に関連し、図面を参照して、以下により完全に説明する。

図１ａ〜図１ｂは、幾何オブジェクトのコンピュータ可読モデルを生成し、操作するためのデータ処理システムを示す。
図１ａは、コンピュータ・システムの実施例の概略図を示す。コンピュータ・システムは、ディスプレイ１２０、キーボード１２１、およびコンピュータ・マウス１２２、および／またはタッチパッド、トラックボール、ライトペン、タッチスクリーンなどの、別のポインティング・デバイスを含む、適切にプログラミングされたコンピュータ１０１、例えば、パーソナル・コンピュータを含む。

１０１として示されたコンピュータ・システムは、仮想ビルディング・ブロック・モデルの設計、格納、操作、および共有を容易にするように適合されている。コンピュータ・システム１０１は、スタンドアロン・システムとして、またはクライアント／サーバ・システムにおけるクライアントとして使用することができる。

図１ｂは、コンピュータ可読仮想ビルディング・ブロック・モデルを生成し、操作するためのデータ処理システムのブロック図を示す。コンピュータ１０１は、一部は揮発性メモリ手段として、一部は不揮発性メモリ手段として、例えば、ランダム・アクセス・メモリ（ＲＡＭ）およびハードディスクとして、実装することができるメモリ１０２を含む。メモリは、中央処理装置１０３によってそれぞれ実行可能な、モデル・コード・インタープリタ１０７、モデル・コード・ジェネレータ１０８、ＵＩイベント・ハンドラ１０９、およびモデル化アプリケーション１１０を格納している。さらに、メモリは、モデル・データ１１１、すなわち、物理的オブジェクトのデジタル表現を表す一組のデータ構造、例えば、仮想ビルディング・ブロック・オブジェクトも格納している。仮想ビルディング・モデルを格納するためのデータ・フォーマットの実施例は、米国特許第６３８９３７５号で開示している。

コード・インタープリタ１０７は、モデルを定義するコード、すなわち、モデルのビルディング・ブロックのデータ構造を表現するコードを読み取り、解釈するように適合されている。コード・インタープリタの好ましい実施形態は、モデルを読み取り、そのようなモデルを、コンピュータ・ディスプレイ上で提示するための既知のグラフィック・フォーマットに変換するように適合されている。

ＵＩイベント・ハンドラ１０９は、ユーザ・インタフェースとのユーザの対話を、コード・ジェネレータ１０８が認識できる、適切なユーザ・コマンドに変換するように適合されている。一組の可能で認識可能なコマンドは、以下を含む。すなわち、要素のライブラリからビルディング・ブロックを獲得する、ビルディング・ブロックを別のビルディング・ブロックに結合されるように配置する、ビルディング・ブロックを分離する、ビルディング・ブロックを破棄する、例えば、回転を開始することにより、ビルディング・ブロック、一群のビルディング・ブロックなどを操作する、その他である。各コマンドとともに、一組のそれぞれのパラメータ、例えば、ディスプレイ座標系に対するカーソル座標、ビルディング・ブロックのタイプなどが関連していることが可能である。

コード・ジェネレータ１０８は、ユーザのコマンドに応答して、モデルのデータ構造を変更するように適合されている。同時実行または後続のタスクとして、コード・インタープリタが、コード・ジェネレータの結果を提示するために実行されることが可能である。
モデル化アプリケーション１１０は、メモリ、ファイル、ユーザ・インタフェースなどを制御するように適合されている。

ユーザ１０５は、好ましくは、コンピュータ・スクリーン上に表示されたグラフィカル・ユーザ・インタフェースを含む、ユーザ・インタフェース１０６、ならびにキーボードおよび／またはポインティング・デバイスなどの１つまたは複数の入力デバイスを使用して、コンピュータ・システム１０１と対話することができる。

モデル、幾何学的記述、またはその他のデータの読み込み、保存、または通信を行うため、コンピュータ・システムは、入出力ユニット（Ｉ／Ｏ）１０４を含む。入出力ユニットは、異なるタイプの記憶媒体、および異なるタイプのコンピュータ網、例えば、インターネットに対するインタフェースとして使用することができる。さらに、入出力ユニット（Ｉ／Ｏ）１０４は、他のユーザと、例えば、インタラクティブな形でモデルを交換するために使用することもできる。

メモリ１０２、中央処理装置（ＣＰＵ）１０３、ユーザ・インタフェース（ＵＩ）１０６、および入出力ユニット１０４の間のデータ交換は、データ・バス１１２を介して達せられる。

図２は、仮想ビルディング・ブロック・システムのグラフィカル・ユーザ・インタフェースを示す。
ユーザ・インタフェースは、ベース・プレート２０２、ならびにいくつかの互いに結合された仮想ビルディング・ブロック２０４を含む３Ｄ構造２０３を有する３Ｄシーンのビューを示す、表示領域２０１を含む。シーンは、所定の視点から示されている。以下に、視点は、表示領域内に示されたグラフィック・ピクチャに対応する現実の構造のピクチャをカメラが記録するであろう位置に対応するため、（仮想）カメラ位置とも呼ぶ。

ビルディング・ブロック２０４のそれぞれは、そのビルディング・ブロックを選択するように、例えば、コンピュータ・マウスを使用してクリックすることにより、アクティブにすることができる、グラフィカル・ユーザ・インタフェースのアクティブな要素に対応する。一実施形態では、選択された仮想ビルディング・ブロックは、外見が変化する。例えば、選択されたビルディング・ブロックは、色、テクスチャなどが変化することが可能であり、つまり、ビルディング・ブロックは、選択されたビルディング・ブロックのまわりにバウンディング・ボックスを示すことなどにより、強調表示されることが可能である。ユーザは、選択されたビルディング・ブロックを操作する、例えば、ブロックの特性を変えること、例えば、ブロックの色を変えること、ブロックを削除すること、コピーおよび貼り付けの操作を実行すること、ブロックを異なる位置までドラッグすることなどを行うことができる。

ユーザ・インタフェースは、ユーザが選択することができる、いくつかの異なるビルディング・ブロック２０６を含む、パレット・パネル２０５をさらに含む。例えば、ユーザは、マウスを使用して、ビルディング・ブロック２０６の１つの上でクリックして、そのビルディング・ブロックを選択し、選択されたビルディング・ブロックを表示領域２１０の中にドラッグして、そのブロックを構造２０３に、またはベース・プレート２０２に結合することができる。

ユーザ・インタフェースは、様々な機能またはツールをアクティブにするための、いくつかのメニュー・ボタン２０８を含む、メニュー・バー２０７をさらに含む。例えば、ツール・バーは、仮想カメラ位置を変更して、ユーザが、異なる方向から組み立て領域を見ることができるようにするための、回転ツールを含むことが可能である。メニュー・バーは、３Ｄシーンにズームインするため、および３Ｄシーンからズームアウトするためのズーム・ツールをさらに含むことが可能である。ツールのその他の実施例には、異なる一組のビルディング・ブロックをそれぞれが含む、異なるパレット２０５を選択するためのパレット・ツール、構造の諸部分に着色を行うための着色ツール、ビルディング・ブロックを消去するための消しゴム・ツールなどが含まれる。

メニュー・バー２０７は、モデルを保存するための機能、以前に保存済みのモデルを開くための機能、モデルのイメージを印刷するための機能、ヘルプ機能などの、標準の諸機能をさらに提供することが可能である。

図３ａ〜図３ｄは、ビルディング・ブロック、ならびにビルディング・ブロックの結合要素の実施例を示す。
図３ａは、ビルディング・ブロック３０１の透視図を示す。ビルディング・ブロック３０１は、別のビルディング・ブロックの対応する穴、例えば、別のビルディング・ブロックの底面上の穴と連結することが可能な、８つのノブ３０３ａ〜３０３ｈを備えた、上面３０２を有する。相応して、ビルディング・ブロック３０１は、対応する穴を有する底面（図示せず）を含む。ビルディング・ブロック３０１は、結合要素を全く含まない側面３０４をさらに含む。

一般に、結合要素は、異なるクラスの結合要素に、例えば、コネクタ、レセプタ、および混合要素にグループ化することができる。コネクタは、別のビルディング・ブロックのレセプタによって受けられて、ビルディング・ブロック間の結合を提供することが可能な結合要素である。例えば、コネクタは、別の要素の部分の間、穴の中などにはまることが可能である。レセプタは、別のビルディング・ブロックのコネクタを受けることができる結合要素である。混合要素は、他方のビルディング・ブロックの協働する結合要素のタイプに通常、依存して、レセプタとしても、コネクタとしても機能することが可能な部品である。

図３ｂは、下から見たビルディング・ブロック３１０の透視図を示す。ビルディング・ブロック３１０は、長方形でない上面および底面を有する。底面は、他の１つまたは複数のビルディング・ブロック、例えば、図３ａのビルディング・ブロック３０１の対応するノブを受けるための、穴３１１、３１２、および３１３を含む。穴は、端部３１４、２次ピン３１５、ならびにコーナ３１６および３１７によって定義される。このため、以上の要素群のすべての要素の特性により、ビルディング・ブロック３１０の底面の結合特性が決まる。

図３ｃは、ビルディング・ブロック３２１に結合されて、複合ビルディング・ブロックを形成するビルディング・ブロック３２０を示す。ビルディング・ブロック３２０は、別のビルディング・ブロックの対応する穴にはまるノブ３２２を上面に含む。しかし、図３ｃに示すとおり、他のタイプの結合も達することができる。すなわち、ノブの間の間隙３２３が、ブロック３２１の側面３２４などの、他のコネクタに対するレセプタとして機能する。物理的ビルディング・ブロックの場合、この特性は、間隙の寸法、およびビルディング・ブロック３２１の寸法、すなわち、ブロック３２１の側部の幅３２５によって決まる。しかし、デジタル表現では、以上の特性は、以下により詳細に説明するとおり、規則的な格子上の結合点の対応する属性によって表される。

図３ｄは、２つのビルディング・ブロック３３１および３３２を示す。ビルディング・ブロック３３１は、上面に４つのノブ３３３を有し、底面（図示せず）に対応する４つの穴を有するれんがである。れんが３３２は、互いに直角でない平面を含む面を有するビルディング・ブロックの実施例である。具体的には、ビルディング・ブロック３３２は、傾斜面３３４を有する。図３ｄに示すとおり、現在の位置では、ビルディング・ブロック３３１とビルディング・ブロック３３２は結合しない。というのは、図示する位置では、互いに連結する結合要素が全く存在しないからである。
以上のビルディング・ブロックは、単に、可能なビルディング・ブロックの実施例の役割をするものと理解されたい。

図４ａ〜図４ｃは、物理的ビルディング・ブロックのデジタル表現の実施形態を示す。物理的ビルディング・ブロックのデジタル表現は、コンピュータのメモリの中に格納されたデータ構造を含み、ただし、デジタル表現は、ビルディング・ブロックの特性を表す。この実施形態によれば、ビルディング・ブロックの結合要素は、性質、形状、結合特性などが異なる可能性がある。しかし、ビルディング・ブロック上の結合要素の位置は、一組の規則に従う。

ビルディング・ブロックは、関連するいくつかの平面、例えば、ビルディング・ブロックのバウンディング・ボックスの表面によって定義される平面を有する。ビルディング・ブロックの結合要素は、各結合要素が、関連する軸を有するように、それらの平面に配置される。同一平面におけるすべての結合要素の軸は、近隣の格子点の間に既定の距離がある、規則的な格子の、例えば、直交格子のそれぞれの格子点、いわゆるノットと一致する。好ましくは、ビルディング・ブロックに関連する平面は、例えば、ビルディング・ブロックの上面と底面に対応する一組の水平面、ならびにビルディング・ブロックの側面に対応する、いくつかの垂直面を定義することにより、ペアで互いに平行である。好ましくは、近隣の格子点の間の距離は、すべての水平面で同一である。一実施形態では、垂直面における近隣の格子点間の距離は、水平面における近隣の格子点間の距離とは異なる。

図４ａ〜図４ｂは、データ構造の実施形態が、どのように図３ａのビルディング・ブロック３０１の特性を記述するかを概略で示す。図４ａ〜図４ｂでは、ビルディング・ブロック３０１は、それぞれ上面および底面の対応する直交格子４０５および４０６を有するのが示されている。図４ａが、ビルディング・ブロックの透視図を示すのに対し、図４ｂは、ビルディング・ブロックの上面図を示す。図４ａ〜４ｂで、ビルディング・ブロック３０１の側面上の格子は、図示されていない。ビルディング・ブロック、例えば、ビルディング・ブロック３０１の一部の実施例は、面のいくつか、例えば、側面上には、結合要素を全く有さない。ビルディング・ブロックの他の実施例は、すべての側面上に結合要素を有する。

直交格子は、結合格子とも呼ばれ、格子点は、結合点とも呼ばれる。結合点は、円４０７ａ〜４０７ｋで典型的に示される円で例示される。このため、結合点４０７ａ〜４０７ｈはそれぞれ、ノブ３０３ａ〜３０３ｈに対応する。側面３０４は、結合要素を全く有さないので、側面３０４に関して結合格子は、全く定義される必要がない。代替の実施形態では、無効なレセプタだけを含む結合格子が、すなわち、他の結合要素を結合することも、はねのけることもしないレセプタだけが、側面に関して定義されてもよい。

ビルディング・ブロックのデジタル表現は、内部右手座標系４０８に関して記述される。座標系の選択、特に、座標系の原点の位置、および軸の方向は、任意の適切な慣行に従って選択してよいものと理解されたい。このため、対応するデータ構造の中で、３Ｄシーンにおけるビルディング・ブロックの位置および向きは、外部座標系に対する、例えば、別のビルディング・ブロックの座標系、またはグローバル「世界」座標系に対する座標系４０８の原点の座標、および軸の向きによって表されることが可能である。

図４ａから見て取ることができるとおり、規則的な格子の中に配置された結合点によるビルディング・ブロックの結合要素の表現により、物理的ビルディング・ブロック上の結合要素の物理的配置に、ある制約が課せられる。格子４０５は、ノブ３０３が延びる、ビルディング・ブロックの上面の平面に配置されている。

図４ａ〜図４ｂの実施例では、格子点は、正方格子の中に配置され、ただし、各正方形は、任意の長さ単位（ＬＵ）の５×５単位の寸法を有する。このため、この形状では、結合要素も、対応する正方格子上に配置され、ビルディング・ブロックの平面における結合要素間の距離は、１０ＬＵの倍数である。図４の実施例では、ビルディング・ブロックの上面および下面は、長方形であり、２０ＬＵ×４０ＬＵの寸法を有し、近隣の結合要素は、１０ＬＵだけ離間している。他方、垂直方向では、結合要素は、１２ＬＵだけ離間している。

結合点の位置は、ビルディング・ブロックの内部座標系４０８に対して定義される。各格子点は、結合要素が、対応する結合要素といずれの方向で連結するかを示す、関連する方向をさらに有する。格子点の方向は、平面に直角に、バウンディング・ボックスから出るようにポイントし、すなわち、図４ｂで、図面の平面から出るようにポイントする。

一実施形態では、結合点の格子を表すデータ構造は、各結合点に関して、以下を含む。すなわち、座標系４０８に対する結合点の座標、結合要素の方向、および結合タイプである。

一実施形態では、ビルディング・ブロックを表すデータ構造は、ビルディング・ブロックＩＤと、ビルディング・ブロックのバウンディング・ボックスの位置、向き、および寸法を記述するデータ構造と、それぞれの格子、および対応する結合点を記述する、いくつかのデータ構造とを含む。結合点の格子を表すデータ構造は、以下を含む。すなわち、
−ローカル格子座標系の原点として使用される格子点の座標系４０８に対する座標。格子４０５の実施例では、格子点３０７ｉが、ＬＵ単位で、座標Ｐ_０＝（−５，１２，−１５）を有する原点として使用される。
−結合要素の方向。格子４０５の実施例では、これは、（０，１，０）であり、すなわち、座標系４０８のｙ軸の方向である。
−ｘ方向およびｚ方向における格子点の数。格子４０５の実施例では、それぞれ、ｎ_ｘ＝９およびｎ_ｚ＝５である。
−対応する結合点の結合特性をそれぞれが含む、ｎ_ｘ×ｎ_ｚデータ構造のアレイ。各格子点のデータ構造は、結合点の結合タイプ、例えば、「穴」、「端部」、「ノブ」などを含む。
一実施形態では、各結合点は、結合点のまわりの近傍を定義する、関連するボリューム要素をさらに有する。

図４ｃは、結合点のまわりのボリューム要素の実施例を示す。一実施形態では、各結合点には、中心が結合点である球体が関連している。図４ｃで、これが、上記のビルディング・ブロック３０１の結合格子４０５の結合点４０７ｇおよび４０７ｊによって典型的に示される。結合点４０７ｇおよび４０７ｊに関して、対応する球体４１０ｇおよび４１０ｊがそれぞれ、示されている。球体は、隣接する結合点間の距離の半分に、例えば、図４ａ〜図４ｂの実施例では、２．５ＬＵに等しい半径を有する。代替の諸実施形態では、球体は、より小さくても、より大きくてもよい、すなわち、球体は、交差しても、隣接する球体の球体間に間隙があってもよく、これにより、小さい間違った配置に対する、位置付け方法の感度の制御が可能になるものと理解されたい。

異なる種類のボリューム要素も使用することができることを、さらに理解されたい。例えば、ボリューム要素は、結合点４０７ｃのまわりの円筒４１０ｃで典型的に示されるとおり、結合要素のまわりの円筒であってもよい。この実施例では、円筒は、２．５ＬＵの半径、および５ＬＵの高さを有する。ボリューム要素のさらなる実施例には、立方体、楕円体などが含まれる。

一部の実施形態では、異なるタイプの結合要素が、異なるボリューム要素に、例えば、異なるサイズの、例えば、異なる半径および／または異なる高さのボリューム要素に、あるいは異なる幾何形状のボリューム要素にさえ関連することが可能であることを、さらに理解されたい。そのような実施形態では、結合点を表すデータ構造は、関連するボリューム要素のタイプおよび／または寸法を明らかにする、１つまたは複数のパラメータをさらに含むことが可能である。

ディスプレイ上で、例えば、コンピュータ・スクリーン上でビルディング・ブロックをグラフィックスで表現する際、バウンディング・ボリューム、座標系、ボリューム要素、および格子は、示される必要がないものと理解されたい。好ましくは、グラフィック表現は、ビルディング・ブロック自体のグラフィックスのレンダリングだけを含む。
以下に、新たな仮想ビルディング・ブロックを、３Ｄ構造を含むシーンの中に配置するプロセスをより詳細に説明する。図５、ならびに図６ａ〜図６ｂを参照する。

図５は、３Ｄシーンの中でビルディング・ブロックを位置付け、そのシーンの中に既に存在するビルディング・ブロックの構造に、そのブロックを結合するプロセスの流れ図を示す。

工程５０１で、新たなビルディング・ブロックが、例えば、パレット上でビルディング・ブロックを選択し、ビルディング・ブロックのグラフィック表現を、マウスの動きに従って、２Ｄ表示領域の中のユーザによって選択された位置までドラッグすることによって、シーンの中に配置され、ただし、２Ｄ表示領域は、３Ｄシーンの２Ｄ射影を表す。一実施形態では、マウスの動きが、少なくとも所定の時間にわたって、例えば、ＧＵＩイベント・ハンドラによって検出される時間にわたって停止すると、プロセスが、工程５０３に進む。

図６ａ〜図６ｂは、以前に配置済みのビルディング・ブロックの上に新たなビルディング・ブロックを位置付けることの実施例を示す。新たなビルディング・ブロック６０１は、前述したとおり、結合格子の、全体的に６０３として示す、いくつかの結合点をそれぞれが含む上面６２１および底面６２２を有する、バウンディング・ボックス６２０として示される。同様に、以前に配置済みのビルディング・ブロック６０２も、全体的に６０４として示す、いくつかの結合点を有する。ビルディング・ブロック６０１および６０２の側面の結合格子および結合点は、図６ａには示していない。この実施例では、３Ｄシーンが、１つだけの以前に配置済みのビルディング・ブロック６０２を含む。

図６ａは、２Ｄディスプレイ座標系６３０に対応する、コンピュータ・スクリーンの２Ｄ表示領域６００上で見られる、ビルディング・ブロック６０１および６０２の２Ｄ射影を示す。

図６ｂは、表示領域６００内の２Ｄ射影と、３Ｄ座標系６４０におけるビルディング・ブロック６０１および６０２の３Ｄ位置の間の関係を示す。新たなビルディング・ブロック６０１が、スクリーン６００上に配置されると、２Ｄ座標系６３０におけるブロック６０１の座標だけが算出され、射影６０１ａをもたらすいずれの３Ｄ位置も、破線の射影線６３１で示される、その射影と整合性がある。このため、スクリーン上へのビルディング・ブロックのユーザによって制御された配置は、表示領域に直交する第３の次元についての情報をもたらさない。図６ｂで、射影は、平行射影であり、すなわち、射影線６３１が、射影平面６００から無限遠の仮想カメラ位置６３２に対応して、互いに平行である。

図５を再び参照すると、工程５０３で、プロセスは、新たなビルディング・ブロックの各結合点に関して、その新たなビルディング・ブロックのその結合点の射影の所定の近傍内に２Ｄ射影を有する、シーンの中に既に存在するいずれかのビルディング・ブロックに（または、ベース・プレートに）属する結合点が存在するかどうかを判定する。一実施形態では、新たなビルディング・ブロックの各結合要素に関して、表示領域内の結合要素のまわりの円が算出される。同様に、シーンの中に既に存在する結合要素の対応する円も算出される。それらの円のいずれかが、新たなビルディング・ブロックの結合要素の円と重なり合う場合、対応する結合要素が、候補結合要素として選択される。

図６ａで、上記の工程が、新たなビルディング・ブロック６０１の結合点６０５に関して示されている。符号６０６は、結合要素６０５のまわりの円を示す。同様に、符号６０８、６１０、および６１２は、円６０５と重なり合うビルディング・ブロックの結合要素６０７、６０９、および６１１のまわりの円をそれぞれ示す。このため、この実施例では、結合要素６０７、６０９、および６１１が、候補結合要素として特定される。この実施例では、さらなる結合要素が選択されるものと理解されたい。しかし、それらの結合要素の円は、図６ｂに示していない。

円６０６、６０８、６１０、および６１２は、結合要素６０５、６０７、６０９、および６１１のまわりの対応する球体の射影にそれぞれ対応することに留意されたい。代替の諸実施形態では、いずれの結合要素が、新たなビルディング・ブロックの結合要素の近傍内に射影を有するかを判定するために、異なるタイプのボリューム要素の射影を使用してもよいものと理解されたい。ボリューム要素のさらなる実施例は、上記に図４ｃに関連して説明した。球体を使用する場合、対応する射影の特定は、特に効率的である。というのは、球体の射影は、視点に関わらず、常に円であるからである。
好ましい実施形態では、円の直径は、格子のそれぞれの中の近隣の結合点間の距離と一致する。

一部の実施形態では、候補結合要素の探索は、シーンの中に既に存在するビルディング・ブロックの結合要素のサブセットに限定されて、探索を完了するのに必要な時間が短縮され、候補結合要素の結果リストのサイズが縮小されることが可能であるものとさらに理解されたい。例えば、探索は、別の結合要素に既に結合されてはいない結合要素に限定されてもよい。別の実施形態では、探索は、適切な結合特性を有する結合要素に、すなわち、以下により詳細に説明するとおり、新たなビルディング・ブロックの結合要素に実際に結合することができる結合要素に限定される。

工程５０３は、シーンの中に既に存在するビルディング・ブロックの候補結合要素のリスト５２０をもたらす。その結果、候補結合要素の３Ｄ座標が分かる。一実施形態では、リスト５２０の中の各エントリは、シーンの中に既に存在するビルディング・ブロックの候補結合点の３Ｄ座標、対応するビルディング・ブロックを明らかにする識別子、新たなビルディング・ブロックの識別子、および／または新たなビルディング・ブロックの対応する結合要素を明らかにする座標を含む。

工程５０５で、候補結合要素のリスト５２０が、所定の一組の評定規則に従って候補結合要素を評定することによって並べ替えられる。

一実施形態では、候補結合要素は、仮想カメラからの要素の距離に従って、すなわち、表示領域６００に対応する射影平面からの要素の相対的距離に従って評定され、候補位置とユーザによって選択された配置の２Ｄ距離に従って、すなわち、新たなビルディング・ブロックのグラフィック表現の位置からの、候補位置の表示領域内における射影のずれに従って評定される。例えば、候補位置がカメラ位置により近い結合要素は、より高く評定されること、すなわち、ユーザが意図する位置と一致する可能性がより高いことが可能である。同様に、３Ｄでユーザによって選択された位置からのずれが大きい候補結合点は、より低く評定されることが可能である。

一部の実施形態では、順序付けは、以上の条件に加えて、または以上の条件の代替として、他の基準に従って実行される。そのような位置評定規則の実施例には、以下の１つまたは複数が含まれることが可能である。すなわち、
−カメラ位置からの相対的距離
−ユーザによって選択された２Ｄ位置からのずれ
−候補結合要素との結合を可能にするための、ビルディング・ブロックの必要な回転度
−可視性試験、例えば、候補結合要素が、現在のカメラ位置から見えるかどうか。一部の実施形態では、現在のカメラ位置から見えない候補結合要素は、リストから破棄される。

一部の実施形態では、例えば、以上の諸条件が寄与する費用関数を、オプションとして、それぞれの重み付け係数を伴って定義することにより、以上の基準のいくつか、またはすべてを組み合わせで使用してもよい。他の諸実施形態では、評定はまず、以上の規則の１つに従って、例えば、必要な２Ｄ移動に従って実行される。２つ以上の候補結合要素が、同一の評定を有する場合、さらなる規則、例えば、カメラからの相対的距離、必要な回転などを使用して、それらの要素を区別することができる。

このため、特定の候補結合要素の評定が達せられ、順序付けられたリスト５２０は、以上の評定による順序付けられたリストに相当する。その時点で、順序付けられたリスト５２０は、以上の位置評定規則に基づいて破棄されていない、すべての候補結合点を含む。

工程５０８で、順序付けられたリスト５２０が空であるかどうかが判定される。リストが空である、すなわち、新たなビルディング・ブロックの結合要素に対して、十分に小さい射影された距離を有する結合要素が全く存在しなかった場合、３Ｄ配置は、拒否される（工程５０９）、すなわち、プロセスは、終了し、それ以外の場合、プロセスは、工程５１０に進む。

プロセスが、３Ｄ配置を拒否することで終了した場合（工程５０９）、そのことは、好ましくは、例えば、視覚的指示を与えることにより、ユーザに示される。例えば、マウスの動きに応答して動かされるビルディング・ブロックのグラフィック表現が、ビルディング・ブロックがまだ配置されていないことを示す形態で示されてもよい。３Ｄ配置が見出された場合にだけ、グラフィック表現は切り替わり、配置が完了したことをユーザに示す。例えば、３Ｄ配置がうまく完了していない限り、ビルディング・ブロックは、トランスペアレントに、かつ／または可視のバウンディング・ボックスとともに、かつ／または点滅して、かつ／または他の任意の適切な形態で示されることが可能である。

工程５１０で、最高の評定を有する候補結合要素が選択され、新たなビルディング・ブロックが、選択された候補結合点の座標と、その新たなビルディング・ブロックの対応する結合点の座標が一致するように、３Ｄ座標系において配置される。このため、最高の評定による候補位置が選択される。この配置は、暫定的であるに過ぎない、すなわち、コンピュータ・スクリーン上にはまだ表示されないものと理解されたい。

工程５１１で、プロセスは、結合が、所定の一組の結合規則に従っているかどうか、例えば、新たなビルディング・ブロックのそれら、およびその他の結合点における結合要素が、その新たなビルディング・ブロックが結合されるべきビルディング・ブロックの結合要素との結合を可能にするかどうかを検証する。実施形態を以下により詳細に説明する、この試験は、結合性検証とも呼ぶ。好ましい実施形態では、プロセスは、新たなビルディング・ブロックが、候補結合要素に結合された場合、カメラ位置から見えるか、または既存の構造によって完全に視界から遮られるかをさらに検証する。結合が拒否された、またはビルディング・ブロックが見えない場合、暫定的な３Ｄ配置は拒否され、プロセスは、工程５１２に進み、そうではなく、プロセスが結合を検証することに成功した場合、プロセスは、工程５１３に進む。

工程５１２で、結合が拒否された候補結合点が、順序リスト５２０から除去され、プロセスは、工程５０８に戻る、すなわち、次の候補結合点が、存在する場合、選択される。

工程５１３で、すなわち、結合試験が合格であった場合、３Ｄ配置は、受け入れられ、すなわち、構造のグラフィック表現が、受け入れられた位置に新たなビルディング・ブロックを「パチンとはめ込み」、ビルディング・ブロックの外見を変更することによって更新される。一実施形態では、ユーザは、例えば、ビルディング・ブロック上でマウスを使用してクリックして、配置プロセスを完了させることにより、位置を受け入れることができる。ユーザは、ビルディング・ブロックを別の位置に配置することを所望する場合、単に、ビルディング上でクリックすることなしに、マウスを動かして、元の外見に戻るように、新たなビルディング・ブロックの外見を変更し、ビルディング・ブロックを２Ｄ表示領域の別の位置に移すことができる。

プロセスは、例えば、図４ａ〜図４ｂに関連して説明したとおり、３Ｄシーン内に配置されたビルディング・ブロックをそれぞれが表す、一組のデータ構造を保持する。新たなビルディング・ブロックの３Ｄ配置を受け入れる際、プロセスは、その新たなビルディング・ブロックに対応するデータ構造の新たなインスタンスを、その一組のデータ構造の一部として追加することにより、その一組のデータ構造を更新する。

図７ａ〜図７ｂは、スクリーン上のグラフィック表現のわずかに異なる２Ｄ配置からもたらされる、図６ａ〜図６ｂの新たなビルディング・ブロックの２つの位置を示す。図７ａでは、ビルディング・ブロック７０１が、構造７０２の上に配置される。他方、図７ｂでは、ビルディング・ブロック７０１は、構造７０２の背後のベース・プレート７０３上に位置付けられる。このため、新たなビルディング・ブロックの２Ｄ位置の小さな調整により、ユーザが、３Ｄシーン内の２つのいくぶん異なる配置を差別化することができるようになる。図７ａ〜図７ｂは、構造７０２のビルディング・ブロック群７０４と比較した、新たなビルディング・ブロック７０１がユーザによって操作されている間の、ブロック７０１の異なる外見をさらに示す。

図８は、暫定的な３Ｄ配置における新たなビルディング・ブロックの結合性検証を行うサブプロセス５１１の実施形態の流れ図を示す。このため、プロセスは、新たなビルディング・ブロックが、既存の構造の少なくとも１つの他のビルディング・ブロックに結合されることが可能であるかどうかを検証する。他のビルディング・ブロックは、第２のビルディング・ブロックと呼ぶ。

初期工程８０１で、プロセスは、衝突検出および可視性試験、すなわち、新たなビルディング・ブロックが、シーンの中に既に存在する他のいずれかのビルディング・ブロックと交差するかどうかの検出、および新たなビルディングが、既存の構造によって完全に視界から遮られ、現在のカメラ位置から見えなくなるかどうかについての試験を実行する。衝突検出は、任意の適切な衝突検出方法によって、好ましくは、ビルディング・ブロックのバウンディング・ボリュームに基づく衝突検出方法によって実行されることが可能である。そのようなアルゴリズムの実施例は、例えば、Ｄａｖｉｄ Ｈ．Ｅｂｅｒｌｙ，「３Ｄ Ｇａｍｅ Ｅｎｇｉｎｅ Ｄｅｓｉｇｎ」，Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ，２００１において開示されている。同様に、可視性試験も、当技術分野で知られている任意の適切な方法によって実行されることが可能である。無効な交差が検出された、すなわち、ビルディング・ブロックのバウンディング・ボリュームが交差する場合、またはビルディング・ブロックが、現在のカメラ位置から見えない場合、その位置および向きにおけるビルディング・ブロックの配置が拒否され、そうではなく、ビルディング・ブロックが、少なくとも部分的に可視であり、有効な交差が検出された場合、すなわち、バウンディング・ボックスの表面の少なくとも一部が交差するが、バウンディング・ボックスのボリュームは交差しない場合、プロセスは、工程８０２に進む。

工程８０２で、バウンディング・ボックスの表面の検出された交差に属する、新たなビルディング・ブロック、および第２のビルディング・ブロックのすべての結合点が特定される。既に結合されてはいない結合点だけが、考慮される必要があり、それらの結合点を、関係のある結合点と呼ぶ。

工程８０３で、新たなビルディング・ブロックの第１の関係のある結合点が、例えば、任意に選択された結合点が選択される。
工程８０４で、新たなビルディング・ブロックの選択された結合点に関して、プロセスは、選択された結合点と同一の座標を有する、第２のビルディング・ブロックの関係のある結合点が存在するかどうかを調べる。一実施形態では、ビルディング・ブロックは、別個のボリューム基準格子の中に入れられ、すべての座標は、任意の長さ単位の倍数であり、座標の厳密な一致が要求されることが可能である。連続的な、または準連続的な基準座標系において、格子点が、所定の限度内で一致することを要求されることも可能である。
そのような一致する結合点が全く見出されない場合、プロセスは、工程８１４に進む。

工程８１４で、選択された結合点の所定の近傍内に、他の関係のある結合点が存在するかどうかが検出される。例えば、２つの隣接する結合要素間の距離が１０ＬＵである実施形態において、所定の近傍は、（ｘ，ｙ，ｚ）における選択された結合点のまわりの立方体（ｘ±５ＬＵ，ｙ±５ＬＵ，ｚ±５ＬＵ）となるように選択することができる。選択された結合点の所定の近傍内に、他の関係のある結合点が存在する場合、その２つのビルディング・ブロックの結合は拒否され（工程８１１）、アルゴリズムは、終了する。このため、この実施形態における結合点が、規則的な格子上に配置された場合、ビルディング・ブロックの無効な配置が、効率的に検出されることが可能である。すなわち、第２のビルディング・ブロックの関係のある結合点との不一致が、新たなビルディング・ブロックの関係のある結合点の１つに関して見出された場合、新たなビルディング・ブロックの残りの結合点は、調べられる必要がなく、検出プロセスの速度が高められる。
工程８１４で、競合する関係のある結合点が全く見出されなかった場合、プロセスは、工程８０９に進む。

工程８０４で、一致する結合点が見出された場合、プロセスは、工程８０５に進み、選択された結合点の所定の近傍内に、例えば、前述した、（ｘ，ｙ，ｚ）における選択された結合点のまわりの立方体（ｘ±５ＬＵ，ｙ±５ＬＵ，ｚ±５ＬＵ）内に、他の関係のある結合点が存在するかどうかが検出される。別の結合点が、所定の近傍内で見出された場合、その位置は、拒否され（工程８１１）、見出されなかった場合、プロセスは、工程８０６に進む。
代替の諸実施形態では、以上の制限は、望ましくない可能性がある。さらに、さらなる別の実施形態では、以上の制限は、ある結合タイプに限定されることが可能である。

工程８０６で、プロセスは、選択された結合点と検出された一致する結合点が、反対の方向を有するかどうか、すなわち、それらの結合点の関連する軸が、共通の線上にあるが、反対の向きであるかどうかを検出する。このため、結合要素が連結するのに適した相対的な向きに位置付けられた結合要素だけが、受け入れられる。

代替の諸実施形態では、この制限は、例えば、結合要素が、ある範囲の向きを受け入れる諸実施形態において、ある範囲の向きを受け入れることにより、緩和されてもよいことに留意されたい。
結合点の相対的方向が受け入れられた場合、プロセスは、工程８０７に進み、受け入れられなかった場合、その位置は、拒否される（工程８１１）。

工程８０７で、選択された結合点の結合タイプと、対応する検出された、一致する結合点の結合タイプが比較される。一実施形態では、各結合点は、関連する結合タイプ、例えば、「ノブ」、「穴」、「端部」、「コーナ」、「ヒンジ」、「ピン」、「小型ピン」などを有する。プロセスは、メモリの中に格納された結合テーブル８１３へのアクセスを有する。結合テーブルは、結合タイプの特定のペアが、２つのビルディング・ブロックの結合にどのように影響を与えるかを示す、結合タイプのすべてのペアに関する結合性タイプを含む。例えば、結合タイプのすべてのペアは、「真」、「偽」、または「無効」という結合性タイプに関連することが可能である。「真」という結合性タイプは、結合が有効であることを示し、対応する結合要素は、２つのビルディング・ブロックを結合するように連結し、例えば、ノブが、対応する穴と連結する。「偽」という結合性タイプは、結合が許されないことを示す。例えば、ノブとノブの間の結合は、可能ではない。すなわち、ノブとノブは、結合をもたらすように連結しないだけでなく、妨げになり／衝突さえして、結合を不可能にする。最後に、「無効」という結合性タイプは、結合を妨げるものは何も存在しないが、実際に結合するものも何も存在しないことを示す。例えば、穴と穴の場合に、これが該当する。このため、結合点の所与のペアに関して、プロセスは、格納された結合テーブル８１３から、対応する結合性タイプを取り出すことができる。

後続の工程８０８では、結合性結果が「偽」であるかどうか、すなわち、対応する結合タイプ間で、有効な結合が全く不可能であるのかどうかが試験される。結合性結果が「偽」であった場合、新たなビルディング・ブロックの位置は、拒否され（工程８１１）、それ以外の場合、結合性結果は、格納され、プロセスは、工程８０９に進む。

工程８０９で、新たなビルディング・ブロックのすべての関係のある結合点が処理済みであるかどうかが試験される。処理済みではない場合、未処理の関係のある結合点が、選択され（工程８１２）、現時点で選択された結合点に対して、上記の工程８０４、８０５、８０６、８０７、および８０８を実行することにより、処理される。

新たなビルディング・ブロックのすべての関係のある結合点が処理され、位置が拒否されなかった場合、その位置は、受け入れられ、プロセスは、工程８１０に進む。工程８１０で、格納された結合性結果に基づき、どのようにビルディング・ブロックが結合するかが判定され、ビルディング・ブロックのそれぞれのデータ構造が、それに相応して更新される。

最初、すべての結合性結果が「無効」であるかどうかが調べられる。「はい」である場合、すなわち、ビルディング・ブロックの位置を妨げるものは何も存在しないが、結合要素のいずれも、ビルディング・ブロックを結合するように実際に連結しない場合、新たなビルディング・ブロックは、現在の位置に許される。一実施形態では、追加のアルゴリズムが、例えば、バウンディング・ボリュームに基づき、その位置に配置された物理的ビルディング・ブロックが、倒れるかどうか、傾くかどうかなどを判定し、それに相応して、その位置を許すか、または拒否することができる。

「無効」ではない場合、すなわち、１つまたは複数の結合性結果が真である場合、プロセスは、ビルディング・ブロックがどのように結合されるか、すなわち、ビルディング・ブロックが固定して結合されるか、または結合が、相対的な回転、並進、および／またはそれに類する動きを許すかを判定する。
データ構造が更新されると、サブプロセスは、終了し、図５の全体的なプロセスに戻る。

図９ａ〜図９ｂは、回転を含むビルディング・ブロックの結合を示す。一部の実施形態では、結合点は、スクリーン上で見える新たなビルディング・ブロックの向きに関してだけ、すなわち、ユーザによって選択された向き、または既定の向きに関してだけ調べられる。ユーザが、新たなビルディング・ブロックを、そのビルディング・ブロックの回転の後に結合することを所望する場合、向きは、例えば、適切なユーザ・インタフェース・コントロールによって、例えば、グラフィカル・ユーザ・インタフェースのメニューの中で選択されることが可能な回転ツール、キーボード・コマンドなどを介して制御されることが可能である。例えば、ユーザは、例えば、異なる軸を中心とする９０度回転に相当する、一連の個々の向きを順に進むように、新たなビルディング・ブロックの向きを制御することができる。例えば、図９ａおよび図９ｂで、ビルディング・ブロック９０１は、ビルディング・ブロック９０１のユーザによって選択された向きに応じて、異なる形で構造９０２に結合される。

図９ａでは、ビルディング・ブロック９０１が、構造９０２の上に結合されている。図９ｂでは、ビルディング・ブロック９０１は、垂直面に配置された、構造９０２のノブ群９０３に結合されている。

代替の実施形態では、ビルディング・ブロックの自動的な向き変更が許される。例えば、図５の工程５１０および５１１で候補位置を分析する際、新たなビルディング・ブロックの異なる回転が、追加の候補位置として考慮され、実施される評定、および後の結合性検証に従って分析されることが可能である。例えば、新たなビルディング・ブロックが、何らかの任意の角度でヒンジに結合されるべき場合、ユーザが、新たなビルディング・ブロックをヒンジの軸と完全に揃えることは必要ない。プロセスは、回転させられた位置を評価し、回転の後に新たなビルディング・ブロックを結合する。一部の実施形態では、自動的向き変更は、所定の空間角度に、例えば、４５度、３０度などに制限されて、ユーザを混乱させ、意図しない結果をもたらす可能性がある大きい回転が回避される。

ユーザが、新たなビルディング・ブロックがどこに配置され、結合されるかについての明確な指示を受け取ることは、前述したプロセスの別の利点である。さらに、ユーザによって制御される、スクリーン上の新たなビルディング・ブロックの２Ｄ位置の小さな訂正が、即時に考慮に入れられ、滑らかで自然なワークフローの印象がもたらされる。

当業者は、本発明の範囲内で、以上の方法の変形形態を実施することができるものと理解されたい。例えば、以上の工程のいくつかの順序を変更すること、工程を組み合わせることなどができる。

例えば、３Ｄシーンの中に新たなビルディング・ブロックを配置した後、ユーザは、類似した位置を探索するために探索ツールをアクティブにすることができる。一実施形態では、探索ツールは、ユーザが、図５の順序付けられたリスト５２０の位置を順に進むことを可能にし、それにより、ユーザが、可能な位置の１つを選択することが可能になる。

オブジェクトのデジタル表現を「操作する」という言葉は、デジタル表現の任意の、ユーザによって制御された操作を指すこと、例えば、新たなビルディング・ブロックの結合、既存のビルディング・ブロックを１つの位置から別の位置に動かすこと、または３Ｄシーンの中でビルディング・ブロックの位置を変更する他の任意の操作を指すことを意図している。

幾何オブジェクトのコンピュータ可読モデルを生成し、操作するためのデータ処理システムを示す図である。 幾何オブジェクトのコンピュータ可読モデルを生成し、操作するためのデータ処理システムを示す図である。 仮想ビルディング・ブロック・システムのグラフィカル・ユーザ・インタフェースを示す図である。 ビルディング・ブロック、およびビルディング・ブロックの結合要素の実施例を示す図である。 ビルディング・ブロック、およびビルディング・ブロックの結合要素の実施例を示す図である。 ビルディング・ブロック、およびビルディング・ブロックの結合要素の実施例を示す図である。 ビルディング・ブロック、およびビルディング・ブロックの結合要素の実施例を示す図である。 物理的ビルディング・ブロックのデジタル表現の実施形態を示す図である。 物理的ビルディング・ブロックのデジタル表現の実施形態を示す図である。 結合点のまわりのボリューム要素の実施例を示す図である。 ３Ｄシーンにおいてビルディング・ブロックを位置付け、そのシーンの中に既に存在するビルディング・ブロックの構造にそのブロックを結合するプロセスを示す流れ図である。 以前に配置済みのビルディング・ブロックの上に新たなビルディング・ブロックを位置付けることの実施例を示す図である。 以前に配置済みのビルディング・ブロックの上に新たなビルディング・ブロックを位置付けることの実施例を示す図である。 スクリーン上のグラフィック表現のわずかに異なる２Ｄ配置からもたらされる、ビルディング・ブロックの２つの位置を示す図である。 スクリーン上のグラフィック表現のわずかに異なる２Ｄ配置からもたらされる、ビルディング・ブロックの２つの位置を示す図である。 暫定的な３Ｄ配置における新たなビルディング・ブロックの結合性検証を行うサブプロセスの実施形態を示す流れ図である。 回転を含むビルディング・ブロックの結合を示す図である。 回転を含むビルディング・ブロックの結合を示す図である。

Claims (16)

1. 少なくとも入力デバイス、ディスプレイ、中央処理装置、及びメモリを有するコンピュータ・システムにおいて、２次元のカーソルの動きによって３次元仮想ビルディング・ブロック・モデルを操作する、前記仮想ビルディング・ブロック・モデルが、一組の結合規則に従って仮想ビルディング・ブロックを別の仮想ビルディング・ブロックと結合するためのいくつかの結合要素をそれぞれが含む複数の仮想ビルディング・ブロックを含む、前記コンピュータの中央処理装置によって実施される方法であって、
   ３次元座標系において、前記メモリに、いくつかの前記仮想ビルディング・ブロックから成る構造のデジタル表現を、提供する工程と、
   前記入力デバイスの動きに伴い前記ディスプレイに表示される前記構造の射影を表す２次元表示領域内のカーソルの動きにより、前記構造に結合されるべき第１の仮想ビルディング・ブロックの２次元射影の位置付けを行い、２次元位置座標を決定する工程と、
   前記２次元位置座標から、前記３次元座標系における前記第１の仮想ビルディング・ブロックのいくつかの３次元候補位置を算出する工程と、
   前記結合規則、および所定の一組の位置評定（格付け）規則に基づき、前記３次元候補位置の１つを選択する工程と、
   前記選択された候補位置で、前記第１のビルディング・ブロックを前記構造に結合する工程とを含む方法。
2. いくつかの３次元候補位置を算出する前記工程は、前記３次元座標系における前記第１の仮想ビルディング・ブロックのいくつかの候補の向きを算出する工程をさらに含む請求項１に記載の方法。
3. 前記構造のいくつかの候補結合要素を特定する工程であって、前記候補結合要素の各々は、前記第１の仮想ビルディング・ブロックの結合要素の射影の所定の近傍内に、２次元表示領域の射影を有する、工程と、
   前記結合規則、および位置評定規則の所定のセットに基づき、前記候補結合要素の１つを選択する工程と、
   前記第１の仮想ビルディング・ブロックと前記構造との間の結合が、前記結合規則のセットに従って有効である場合、少なくとも前記選択された候補結合要素を介して、前記第１の仮想ビルディング・ブロックを前記構造と結合する工程とをさらに含む請求項１または２に記載の方法。
4. 前記候補結合要素の１つを選択する工程は、前記候補結合要素を、仮想カメラ位置からの該候補結合要素の距離に関して評定する工程をさらに含む請求項３に記載の方法。
5. 前記候補結合要素の１つを選択する工程は、現在の仮想カメラ位置から見えない候補結合要素を破棄する工程をさらに含む請求項３または４に記載の方法。
6. 前記候補結合要素の１つを選択する工程は、前記第１の仮想ビルディング・ブロックの対応する結合要素の前記２次元射影までの、該候補結合要素の２次元射影の距離に関して、前記候補結合要素を評定する工程をさらに含む請求項３乃至５のいずれか１項に記載の方法。
7. 前記構造のデジタル表現は、各仮想ビルディング・ブロックに関して、前記仮想ビルディング・ブロックの表面の少なくとも１つに対応する、結合要素をそれぞれが表すいくつかの格子点をそれぞれが含むいくつかの長方形格子を含む請求項３乃至６のいずれか１項に記載の方法。
8. 前記第１の仮想ビルディング・ブロックの結合要素の射影のまわりの前記所定の近傍は、対応する長方形格子の近隣の格子点間の距離に相当する直径を有する請求項７に記載の方法。
9. 前記いくつかの候補位置を特定する工程は、前記第１のビルディング・ブロックを回転させて、回転させられたビルディング・ブロックの候補位置を獲得する工程をさらに含む請求項１乃至８のいずれか１項に記載の方法。
10. 前記第１のビルディング・ブロックの回転は、ユーザによって選択された向きを中心とする所定の空間角度に制限される請求項９に記載の方法。
11. 前記入力デバイスから、前記第１の仮想ビルディング・ブロックのユーザによって選択された向きを制御するユーザ・コマンドを受け取る工程をさらに含む請求項１乃至１０のいずれか１項に記載の方法。
12. 前記ユーザによって選択された向きは、一組の個別の向きの１つに制限される請求項１１に記載の方法。
13. 前記２次元射影は、平行射影である請求項１乃至１２のいずれか１項に記載の方法。
14. データ処理システム上でコンピュータ・プログラムが実行されると、請求項１乃至１３のいずれか１項に記載のすべての工程を実行するためのプログラム・コードを格納している記憶媒体を含むデータ処理システム。
15. コンピュータ上でコンピュータ・プログラムが実行されると、請求項１乃至１３のいずれか１項に記載のすべての工程を実行するためのプログラム・コードを含むコンピュータ・プログラム。
16. コンピュータ上でコンピュータ・プログラムが実行されると、請求項１乃至１３のいずれか１項に記載のすべての工程を実行するためのプログラム・コードを格納しているコンピュータ可読記憶媒体。

Images