コンピュータ読み取り可能なモデル
複数の相互接続可能な構造要素から構成された幾何学的対象物のコンピュータ読み取り可能なモデルを作り出す方法であって、各々の構造要素が、その構造要素を他の構造要素と接続するためのいくつかの接続素子を有する。本方法はそれらの構造要素のうちの第１の１つおよび第２の１つを、対応する構造要素の接続素子であって各々が複数の予め決められた接続タイプのうちの１つを付随して有する接続素子を各々が表現する、対応する第１および第２のデータ構造として符号化する工程を含む。本方法はさらに、互いの予め決められた近接に位置する第１の構造要素の第１の接続素子と第２の構造要素の第２の接続素子を判定する工程と、第１および第２の接続素子が第１と第２の構造要素の間の接続を供給するかどうかの指標である第１および第２の接続素子の対応する接続タイプの接続性情報を取り出す工程とを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、予め規定された幾何学的要素によるバーチャル・リアリティのコンピュータ支援モデル化の分野に関する。
【背景技術】
【０００２】
バーチャル・リアリティのコンピュータ支援モデル化は幾何学的対象物のモデルを作り出し、そのモデルを解釈し、そのモデルを操作し、そうでない場合はコンピュータ・システムの中で幾何学的対象物のモデルを扱う作業である。
【０００３】
第１の観点から見ると、バーチャル・リアリティのモデル化は、現実の世界に導入する前にアイデアを可視化することを可能にするという点で興味深い主題である。もしもバーチャル・リアリティのモデルが十分に変更を加え易ければ、現実世界で同じ処理が実行されなければならなかった状況と比較して幾何学的対象物を開発して洗練する処理で多くの時間が節約されることが可能である。現実世界で対象物を描き出す単純な作業は数時間は簡単にかかるが、それに対してコンピュータは数ミリ秒または数秒以内に新たな色彩を塗布してモデルを可視化することが可能である。
【０００４】
第２の観点から見ると、バーチャル・リアリティのモデル化は、現実世界に存在する対象物のモデルを作り出し、コンピュータを介してそのモデルを可視化し、ある意味で操作することを可能にするという点で興味深い。その結果、現実世界の対象物のモデルは多様な目的で、例えば改善された文書作成のために保存されることが可能である。
【０００５】
コンピュータ支援型のバーチャル・リアリティのモデル化に関して膨大な量の考え得る用途が存在するけれども、特別な用途は娯楽または教育にバーチャル・リアリティのモデル化を使用することである。
【０００６】
物理的構造の玩具セットの様々なタイプのモデル化概念はそれ自体知られている。特に、モジュールもしくは半モジュールを使用する概念は有名であったし今もそうである。通常、これらの概念は予め作成された要素のセットを供給し、それらは予め作成された要素のモジュールに従って何らかの予め決められた方式で互いに相互接続されることが可能である。予め作成された要素は特定のモデル化作業に適したよく知られている対象物に類似している。したがって、例えば家屋のモデルを構築する場合、それらの要素はブロック、屋根瓦、ドア、および窓に類似している。この方式で要素を選択する目的は、新しいモデルが作成されなければならない度に家屋のすべての細部が規定される状況と比較して家屋のモデルの構築に含まれる作業が大幅に減らされることである。しかしながら、家屋または他の対象物を構築する完全な自由度はモデルを構築する簡易性と交換される。
【０００７】
予め規定された要素を有するこの手法はコンピュータ支援型バーチャル・リアリティのモデル化の技術ではよく知られている。また、互いに相互接続されることが可能なモジュール要素を有する概念もよく知られている。しかしそれがコンピュータ内でのそのようなモデルの表現に至ると、予め規定された要素およびモジュール・システムを有する概念の便宜は先行技術では完全に達成されない。
【０００８】
コンピュータ支援型設計およびモデル化にコンピュータが使用されてきた以上、大きな計算努力を必要とする作業はどのようにモデルが見えるかの計算を含めたモデルの可視化と操作であった。その理由の１つはバーチャル・リアリティ・モデルの複雑さおよび微調整が最近利用可能なコンピュータ技術および計算能力に従って拡大されてきたことである。
【０００９】
モデルを表現するデータの転送および交換に至ると、バーチャル・リアリティ・モデルの複雑さおよび微調整の欠点が極めて明確に現れる。現在、記憶ユニットまたはコンピュータ通信ネットワークの形式のいくつかのタイプの外部ユニットがコンピュータに接続され、その結果、モデルを記憶し、ロードおよび／または送信し、受信するための信号経路を拡張する。通常、そのような信号経路は単独のコンピュータ内の信号経路と比較して相対的に低い帯域幅を有する。したがって、モデルを表現するための効率的な仕組みが必要とされる。
【００１０】
特に、コネクタとそれに対応するレセプタといった接続素子を介して互いに相互接続されることが可能な予め規定された要素もしくは構成要素のモデルを作り出す背景では、互いに相対して或る位置に置かれたときに２つの要素が接続可能であるかどうかという全般的問題が発生する。物理的対象物の現実的モデルを作り出すために、例えばバーチャル・モデルが、モデル化される対象物の支持部品に接続されることなく表面よりも上に浮き出るどのような要素も有さないことを確実化するために、接続性の情報は重要な情報である。
【００１１】
殆どの現実世界の構造セットで、多様な方式で相互接続される可能性のある極めて多様な異なる構造要素が存在する。
【非特許文献１】Ｄａｖｉｄ Ｈ．Ｅｂｅｒｌｙ、「３Ｄ Ｇａｍｅ Ｅｎｇｉｎｅ Ｄｅｓｉｇｎ」、Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ、２００１年
【発明の開示】
【発明が解決しようとする課題】
【００１２】
それゆえに、様々な異なる構造要素が相互接続されることが可能である、幾何学的対象物のコンピュータ読み取り可能なモデルを作り出す方法を提供することが本発明の目的である。
【００１３】
構造要素が様々なあり得る方式で相互接続されることが可能である、幾何学的対象物のコンピュータ読み取り可能なモデルを作り出す方法を提供することが本発明のさらなる目的である。
【課題を解決するための手段】
【００１４】
上記およびその他の問題は複数の相互接続可能な構造要素から構築された幾何学的対象物のコンピュータ読み取り可能なモデルを作り出す方法によって解決され、そこでは各々の構造要素がその構造要素を他の構造要素と接続するためのいくつかの接続素子を有し、この方法は、
・複数の構造要素のうちの第１の１つまたは第２の１つをそれに対応する第１および第２のデータ構造として符号化する工程であって、それらの各々が対応する構造要素の接続素子を表わし、接続素子の各々がそれに付随して複数の予め決められた接続タイプのうちの１つを有する工程と、
・互いの予め決められた近隣内に配置された第１の構造要素の第１の接続素子および第２の構造要素の第２の接続素子を判定する工程と、
・第１および第２の接続素子が第１と第２の構造要素の間の接続を与えるかどうかを示す第１および第２の接続素子の対応する接続タイプの接続性情報を取り出す工程とを含む。
【００１５】
モジュールの玩具構造要素もしくは複数要素から成る対象物を表現するために都合の良いモデル構造とモデル構造の表現提供することが本発明の利点である。
【００１６】
極めて多様な構造要素の接続をモデル化するための方法を提供することが本発明のさらなる利点である。
【００１７】
異なるタイプのノブ、穴、チューブ、ヒンジ、エッジ、シャフトなどといった極めて多様な異なる接続素子の接続をモデル化するための方法を提供することが本発明のなおもさらなる利点である。接続のタイプを有する複数の接続素子を供給することによって、構造要素の接続特性の表現が与えられ、それは実際のコネクタの正確な幾何学形状とは無関係である。
【００１８】
特に、極めて多様な異なる接続素子の接続をモデル化するための方法が与えられ、それが物理的接続素子の外見およびそれらの構造と無関係であることは利点である。
【００１９】
それゆえに、異なるタイプの接続素子を含む異なる予め決められた構造要素の大規模なセットがモデル化されることが可能である。
【００２０】
構造要素という用語は、それを１つまたは複数の他の構造的要素へと接続するための接続素子を有するどのようなタイプの構造的要素も含み、物理的対象物を作り出すことが可能であり、コンピュータ上でデジタル式に表現されることが可能である。構造要素の範例は構造玩具セットの要素、例えば積み木などのようなビルディング・ブロックを含む。構造要素という用語はさらに、相互接続されたさらに小さい構造要素の集合体、例えば２つ以上の接続された積み木も含む。
【００２１】
一実施形態では、接続のタイプがいくつかの接続グループ、例えばコネクタ、レセプタ、および混合素子へとグループ化される。コネクタは他の構造要素のレセプタによって受け入れられ、それによって構造要素間の接続を供給する接続素子である。例えば、コネクタは他の要素の部分間を嵌合し、穴などに入ることが可能である。レセプタは他の構造要素のコネクタを受け入れることが可能な接続素子である。混合素子はレセプタおよびコネクタの両方として機能することが可能な部品であり、通常、他の構造要素の協同作用する接続素子のタイプに応じて決まる。
【００２２】
互いに対して回転されることが可能な異なる表面もしくは平面に沿った接続をモデル化するための方法を提供することが本発明のなおもさらなる利点である。
【００２３】
可動部分および／または回転することが可能な部分を有する複雑な対象物のモデル化を可能にする、幾何学的対象物のモデルのコンパクトな表現を提供することが本発明のなおもさらなる利点である。
【００２４】
幾何学的対象物のモデルのコンパクトな表現を提供することが本発明のなおもさらなる利点である。
【００２５】
極めて高速で作成と解釈を行なうことが可能なモデル構造およびモデル構造の表現を提供することがなおもさらなる本発明の利点である。
【００２６】
可視化を受けるモデルが作り出されるかまたは操作されるときの相対的に低い帯域幅の必要性および低い処理時間という意味で、コンピュータ・ネットワークを経由して配信されるために都合の良いモデル構造の表現を提供することがなおもさらなる本発明の利点である。
【００２７】
本発明の好ましい実施形態では、本方法は接続タイプの対の接続性情報を含む接続表を供給する工程をさらに含み、接続性情報を取り出す工程が、この接続表から接続性情報を取り出す工程を含む。
【００２８】
接続表という用語は接続タイプの対に関する接続性情報を保存するためのどのような適切なデータ構造も含むように意図されている。例えば、そのようなデータ構造は接続タイプの対によって索引を付けられるルックアップテーブルであることが可能である。
【００２９】
接続表を供給することによって、接続タイプの対に関する接続性情報を保存するための効率的で拡張可能なデータ構造が与えられる。さらに、高速の接続性検出が可能にされる。
【００３０】
本発明の別の好ましい実施形態では、それぞれのデータ構造の各々は対応する構造要素に相対したいくつかの格子をさらに表現し、各々の格子がいくつかの格子点を有し、構造要素の接続素子の各々が格子点のうちの１つと関係し、対応する接続タイプを有する。
【００３１】
それゆえに、関連する接続タイプを有する格子点を備えた正方形格子、三角形格子などといった格子構造を供給することによって、様々な接続素子の例えばサイズ、形状、接続特性などのような様々な特性は格子点の各々に付随する１つまたは複数の属性へと削減されることが可能である。その結果、構造要素の接続特性の効率的な表現が達成される。
【００３２】
接続素子を格子点と関連付けることによって、２つの接続素子が互いに予め決められた近隣にあるかどうかの特に単純な検出が可能である。例えば、一実施形態では、構造要素が共通の個別体積基準格子内に配置され、すべての座標が任意の長さ単位の倍数である場合、２つの接続素子が予め決められた近隣の中にあると考えられるためには座標の正確な一致が必要とされる可能性がある。連続的もしくは外見上連続的な基準座標系内では、格子点が予め決められた限度内で一致すること、すなわちそれらが互いに予め決められた近接の形式で配置されることが必要とされる可能性がある。近接のサイズはモデル化される物理的接続素子のタイプ、例えば接続のためにそれらが実際にどのように協同作用するかということ、および実行されるべき構造要素の配置の制度に応じて決めることが可能である。
【００３３】
それに沿って構造要素が他の構造要素へと接続され得る各々の平面が格子区分、例えば格子区分の各々が中心に格子点を有する場合には正方形へと分割されることが好ましい。
【００３４】
各々の接続素子がそれに関連する方向性を有し、その方向で接続素子がそれに対応する接続素子と係合し得ることを示すことが好ましい。
【００３５】
すべての接続素子は共通平面に配置され、近隣格子点間で予め決められた距離を備えた直交格子の区分に対応する共通の方向性を有することがさらに好ましい。構造要素のうちのすべての構造要素の接続素子が予め決められた規則に従って構造要素に配置され、各々の接続素子が対応する格子点と関係することを可能にすることが好ましい。
【００３６】
しかしながら、異なる非平行平面上の接続素子がそれぞれの格子点間で同じ距離を有する必要がないことに留意されたい。例えば、水平面上の接続素子間の距離は垂直平面上の接続素子間の距離とは異なることが可能である。
【００３７】
さらに、接続素子を予め決められた格子点と関係付けることによって、第１の構造要素の接続素子が第２の構造要素の接続素子の予め決められた近接内にあるかどうかの判定が効率的な方式で実行されることが可能となり、なぜならばその判定が近接格子点を識別することに限定されることが可能となるからである。
【００３８】
別の好ましい実施形態では、本方法はさらに
・接続タイプの対の予め決められたセットの各々について結果的に生じる接続タイプを含む組み合わせ表を供給する工程と、
・予め決められた幾何学的関係で互いに配置される第１と第２の接続素子を判定する工程と、
・第１と第２の接続素子の結果的に生じた接続のタイプを組み合わせ表から取り出す工程と、
・取り出された結果的に生じた接続のタイプを少なくとも１つの結果的に生じた接続素子へと割り当てる工程を含む。
【００３９】
それゆえに、接続素子の接続のタイプが動的である、すなわちそれらは構造要素がおかれる幾何学的背景に応じて変えられることが可能であり、それにより、物理的構造要素の接続特性のさらに現実的なモデル化を提供することが好都合である。特に、第１の構造要素の第１の接続素子と第２の構造要素の第２の接続素子は、予め決められた幾何学的関係で互いに配置されると個々の接続素子とは異なる接続特性を協同して提供する。
【００４０】
第１と第２の接続素子の協同効果はしばしばそれらの相互の幾何学的関係、すなわち接続素子が互いに関して配置される方式、例えばどの程度接近してそれらが互いに配置されるか、どのような相対的配向でそれらが互いに配置されるか、などによって決まるであろう。一実施形態では、これは第１と第２の接続素子が互いから予め決められた近接内で配置されるかどうかを判定することによってモデル化され、もしもそれらが互いからそのような近接で配置されるならば、判定された結果となる接続タイプを第１と第２の接続素子に割り当てる。
【００４１】
データ構造の中で、これは結果となる接続のタイプを少なくとも結果となる接続素子へと割り当てることによって表わされる。一実施形態では、結果となる接続素子は第１と第２の接続素子のうちの一方である。さらなる好ましい実施形態では、結果となる接続のタイプは第１と第２の接続素子の両方に割り当てられる。
【００４２】
もしも対応する構造要素が、接続素子がもはや必要な幾何学的関係に置かれないように再配置されると、第１と第２の接続素子が再割り当てされたそれらのそれぞれの元の接続タイプを有することがさらに好ましい。
【００４３】
別の代替選択肢となる実施形態では、結果となる接続素子は新たな接続素子である、例えば第１と第２の接続素子の位置に関係する或る位置を有するように規定されることが可能である。
【００４４】
いくつかの実施形態で、２つ以上の接続素子が組み合わされて結果となる接続のタイプを生じさせることが可能であることは理解される。
【００４５】
組み合わせ表という用語は接続タイプの対について結果となる接続タイプを保存するためのどのような適切なデータ構造も含むように意図されている。例えば、そのようなデータ構造は接続タイプの対によって索引を付けられるルックアップテーブルであることが可能であり、ルックアップテーブルの各々の記載事項は接続素子の対の組み合わせから結果的に生じる結果的接続タイプを含み、各々の接続素子は対応する接続タイプの対のうちのそれぞれ１つを有する。
【００４６】
組み合わせ表を供給することによって、接続素子の接続タイプがそれらの他の接続タイプとの組み合わせのせいでどのように変わり得るかについて情報を保存するために効率的で拡張可能なデータ構造が供給される。
【００４７】
特に、バーチャル・ビルディング・ブロックのケースでは、頻繁に生じる状況は２つのビルディング・ブロックが互いに隣り合って、すなわちエッジからエッジへと延びて配置される配座であり、それにより、隣接するビルディング・ブロックのエッジ上の接続素子が特性を変える。
【００４８】
さらなる好ましい実施形態では、この状況は構造要素に付随する格子の各々が少なくとも１つの格子エッジを有するときに効率的にモデル化され、本方法はさらに
・接続タイプの各々の対に関する結果となる接続タイプを含む組み合わせ表を供給する工程と、
・第１の構造要素の第１の格子が第２の構造要素の第２の格子とエッジからエッジへの延長で置かれており、第１の格子の第１のエッジが第２の格子の第２のエッジと位置合わせされているかどうかを検出する工程と、
・第１の格子の第１の接続素子に関して、第２の格子の対応する第２の接続素子を識別する工程と、
・第１と第２の接続素子の組み合わせの結果となる接続タイプを組み合わせ表から取り出す工程と、
・取り出された結果となる接続タイプを第１と第２の接続素子に割り当てる工程を含む。
【００４９】
エッジのうちのそれぞれ１つが互いに密に近接するかまたは互いに接触すらして構造要素が互いに隣り合って置かれると、対応するエッジ上の接続素子が他方の構造要素の対応するエッジ上、もしくは近くの接続素子のタイプに応じてその特性を変えることが可能である。
【００５０】
接続タイプの各々の対に関する結果となる接続タイプを含む組み合わせ表を供給することによって、および結果となる接続タイプを構造要素のエッジ上の接続素子に割り当てることによって、エッジからエッジへの延長が検出されれば、協同している構造要素の複雑な接続特性でさえモデル化されることが可能である。
【００５１】
エッジからエッジへの延長という用語は、対応する格子が組み合わされる格子に結合するように互いに隣り合って置かれた２つの格子の配置を含む。それゆえに、エッジからエッジへの延長という用語は、平行したそれぞれの格子エッジ、およびエッジに近い格子点が一致するように平行格子エッジに沿って予め決められた重なりを有する２つの平行の格子を含む。
【００５２】
本発明の別の好ましい実施形態では、それぞれのデータ構造の各々はさらに、対応する構造要素の境界体積を表わし、格子の各々は境界体積の表面に対応する。
【００５３】
それゆえに、格子が境界体積の表面に対応する構造要素に関して境界体積を供給することによって、たとえ構造要素が複雑な形状を有していても各々の構造要素は少数の格子によって表わされることが可能である。それゆえに、構造要素の形状の複雑さが接続タイプへと翻訳され、それが順々に属性として境界体積の表面に関連する格子点へと結び付けられるので、２つの構造要素の協同する接続素子の効率的な検出が達成されることが可能である。
【００５４】
さらに、知られている衝突検出アルゴリズムを使用することによって、境界体積は隣接する構造要素の検出のために効率的な表現を与える。
【００５５】
境界体積は互いに直行する側部を有する境界ボックスであることが可能であり、あるいは境界体積は異なる形状を有する。
さらなる好ましい実施形態では、本方法はさらに
・第１および第２の構造要素のそれぞれの位置を共通の体積基準格子に関して符号化し、対応する第１と第２の構造要素の第１と第２の格子が体積基準格子の第１と第２の平面にそれぞれ対応し、第１と第２の格子の格子点が体積基準格子のそれぞれの基準格子点に対応する工程と、
・第１と第２の格子が体積基準格子の共通平面に対応するかどうか、および第１の格子の少なくとも第１の格子点が第２の格子の第２の格子点と同じ基準格子点に置かれているかどうかを検出する工程とを含む。
【００５６】
それゆえに、体積基準格子、例えば立方体の体積格子を供給することによって、および表面格子を基準体積格子の平面として規定することによって、隣り合う格子点の特に効率的な検出を可能にする特に単純なデータ構造が与えられる。
【００５７】
境界体積は体積基準格子に関する平面として規定されることが好ましい。一実施形態では、それらは体積基準格子の格子平面と一致することが可能であり、場合によっては、体積基準格子の格子平面間の平面として規定されることが可能である。
【００５８】
本発明のまたさらなる好ましい実施形態では、本方法はさらに
・第１の格子と第２の格子の一致する格子点のすべての対を識別する工程と、
・識別された格子点の対の各々について接続性の表から接続性情報を取り出す工程と、
・少なくとも１つある格子点対が無効な接続に対応していれば第１と第２の構造要素の間の接続を否定し、そうではなく少なくとも１つある格子点対が有効な接続に対応していれば第１と第２の構造要素の間の接続を受け容れる工程とを含む。
【００５９】
それゆえに、２つの隣り合う構造要素が相互接続されることが可能であるかどうかを検出するための効率的な方法が提供される。一致する格子点という用語は同じ座標を有する格子点を含む。構造要素が個別の基準格子に配置され、すべての座標が任意の長さ単位の倍数である一実施形態では、座標の正確な一致が必要とされる、すなわち格子点が共通の基準格子点に置かれる。連続的もしくは外見上連続的な基準座標系では、格子点は予め決められた限度以内で一致することが要求される可能性がある。
【００６０】
接続素子の各々が付随の方向性をさらに有するとき、さらなる属性が各々の格子点に関連付けられ、それにより、さらなる自由度を提供する。
【００６１】
接続性情報という用語は、接続タイプの対の接続特性、例えば接続タイプの所定の対に関してこれらの接続タイプの２つの接続素子が接続を提供するかどうか、それらは接続を不可能にするかどうかについての情報を含むように意図されている。好ましい実施形態では、接続性情報は予め決められたグループの接続性タイプのうちの１つを示す接続タイプの各対に関するインジケータを含み、そのグループは対応する接続素子の対の間の接続を提供する有効接続、対応する接続素子の対の間の接続を妨げる無効接続、および中立の接続で構成される。
【００６２】
中立の接続という用語は、互いから予め決められた近接内に置かれると対応する２つの構造要素を接続するように協同しないが、しかしそのような配置をどちらも妨げない接続タイプの対を含む。
それゆえに、可能な相互接続の効率的な符号化が提供される。
【００６３】
本発明のなおも別の好ましい実施形態では、予め決められた近接で互いに配置された第１の構造要素の第１の接続素子と第２の構造要素の第２の接続素子を判定する工程はさらに、予め決められた接続素子のサブセットから第１と第２の接続素子を判定する工程を含む。それゆえに、接続素子の当該の対を判定するために接続素子のサブセットだけが検索されることを必要とし、それにより、本方法の効率を上げる。
【００６４】
さらなる好ましい実施形態では、それぞれのデータ構造の各々はさらに、対応する構造要素の境界体積も表わす。本方法はさらに、第１と第２の構造要素の境界体積の交差部を検出する工程を含み、予め決められた接続素子のサブセットから第１と第２の接続素子を判定する工程は判定された交差部に含まれる接続素子から第１と第２の接続素子を判定する工程を含む。それゆえに、当該接続素子のサブセットは潜在的に接続を提供することが可能な接続素子として判定されるが、なぜならばそれらは境界ボックスの交差部に含まれるからである。
【００６５】
新たなタイプの構造要素および新たなタイプの接続素子でさえも組み入れるように容易に拡張されることが可能なデータ構造とアルゴリズムを提供することが本発明のさらなる利点である。例えば、異なるタイプの既存の玩具構造要素の２つのセットの接続性特性は、異なる玩具構造セットの構造要素が互いに相互接続され得るように組み合わされることが可能である。
【００６６】
たとえ多数の構造要素を含むモデルを作り出すときでさえ、大きな記憶容量を必要としないデータ構造を提供することが本発明のさらなる利点である。
【００６７】
２つ以上の構造要素が接続されるかどうかを検出する効率的な方法を提供し、それにより、構造要素が相互接続されるかどうかを判定するためにコンピュータが必要とする処理時間を削減することが本発明のさらなる利点である。これは、ユーザが構造要素を２つ互いに相対して位置決めすることが可能な対話式コンピュータ・プログラムで特に重要な特徴であり、なぜならばこの状況ではモデルの構造要素の配置もしくは除去から接続性特性の判定までの短い応答時間が必要とされるからである。
【００６８】
本発明は、上述および下記の方法、システム、およびさらなる製品手段を含めた多様な方式で実施されることが可能であり、最初に述べた方法に関連して述べられた利点および長所のうちの１つまたは複数を各々が生じ、最初に述べた方法に関連して述べられ、かつ従属請求項に開示された好ましい実施形態に対応する１つまたは複数の好ましい実施形態を各々が有する。
【００６９】
本発明はさらに、
・構造要素を他の構造要素と接続するためのいくつかの接続素子を各々が有する複数の相互接続された構造要素から構築された幾何学的対象物のコンピュータ読み取り可能なモデルを作り出すための手段と、
・複数の構造要素のうちの第１の１つおよび第２の１つを、対応する構造要素の接続素子であって各々がそれに付随して複数の予め決められた接続タイプのうちの１つを有する接続素子を各々が表わす対応する第１と第２のデータ構造として符号化するための手段と、
・予め決められた近接で互いに配置された第１の構造要素の第１の接続素子と第２の構造要素の第２の接続素子を検出するための手段と、
・第１と第２の接続素子が第１と第２の構造要素の間の接続を提供するかどうかを示す第１と第２の接続素子の対応する接続タイプの接続性情報を取り出すための手段とを含むデータ処理システムに関する。
【００７０】
上述および下記で述べられる方法の特徴がソフトウェア中に導入され、コンピュータで実行可能な命令の実行によってデータ処理システムまたは他の処理手段の中で実行されることが可能であることに留意されたい。これらの命令は、記憶媒体から、またはネットワークを介して他のコンピュータからＲＡＭのようなメモリにロードされるプログラムコード手段であることが可能である。場合によっては、記述した特徴はソフトウェアの代わりに配線接続された回路またはソフトウェアとそれの組み合わせで導入されることも可能である。
【００７１】
本発明はさらに、上述および下記で述べられる方法を実行するように構成されたデータ処理システムに関する。
【００７２】
本発明はさらに、コンピュータ上でそのプログラムが走ると上述および下記で述べられる方法の工程すべてを実行するためのプログラムコード手段を含むコンピュータ・プログラムに関する。
【００７３】
本発明はさらに、コンピュータ上でそのプログラムが走ると上述および下記で述べられる方法を実行するためのコンピュータ読み取り可能な媒体上に保存されたプログラムコード手段を含むコンピュータ・プログラム製品に関する。
本発明は、好ましい実施形態と関連させ、かつ図面を参照しながら下記でさらに十分に説明されるであろう。
【発明を実施するための最良の形態】
【００７４】
図１ａ〜ｅは本発明の一実施形態による構造要素の表現を示す透視図である。
図１ａは構造要素１０１の表現を示している。構造要素１０１は、他のビルディング・ブロックの対応する穴に接続することが可能な２つのノブ１０２を１０３で指定される面の上に有する物理的ビルディング・ブロックのデジタル表現である。このビルディング・ブロックはさらに、面１０５からビルディング・ブロックの反対側の面へと貫通する穴１０４を有する。この穴は他のビルディング・ブロックの対応するコネクタを受け入れるように構成される。
【００７５】
ビルディング・ブロック１０１のデジタル表現は図１ａ中で太線で表わされた境界体積１０６を有する。境界体積１０６はノブ１０２を有するビルディング・ブロック１０１の境界体積である。ビルディング・ブロックのこのデジタル表現はさらに、内部の右手座標系１０７に関して述べられる。座標系、特にその原点の位置と軸の方向の選択がどのような適切な慣例に従って選択されることも可能であることは理解される。それゆえに、対応するデータ構造の中でビルディング・ブロックの位置と配向は、外部の座標系、例えば他のビルディング・ブロックの座標系もしくは大域的な「ワールド」座標系に関する座標系１０７の原点座標と軸の方向によって表わされることが可能である。
境界体積は座標系１０７に相対して、例えば座標系１０７に関する２つの角１１０の座標によってデータ構造内に表わされることが可能である。
【００７６】
図１ｂは、ビルディング・ブロックを含むがノブ１０２を含まない境界体積１０８を備えたビルディング・ブロック１０１の表現を示している。一実施形態では、異なるビルディング・ブロック間の衝突検出は両方のタイプの境界体積、すなわち図１ａに示された境界体積１０６と図１ｂの境界体積１０８に頼っている。
【００７７】
本発明によると、ビルディング・ブロックがそれに沿って他のビルディング・ブロックへと接続されることが可能な各々の平面は複数の正方形へと分割され、各々の正方形の中心に接続点を備える、すなわち正方形のエッジが隣り合う接続点間の半分の距離に対応する。
【００７８】
図１ｃはビルディング・ブロック１０１を示しており、ビルディング・ブロックの１つの面上の接続素子の表現を例示している。この表現は２つのノブ１０２を有するビルデイング・ブロックの面１０３の平面に正方形の格子１０９を表わしている。この正方形格子はいくつかの正方形を含み、正方形１３０と格子点１１１によって例示されるように各々が格子点を中心として有する。各々の格子点は矢印、例えば格子点１１１の矢印１１２で示されるように付随の方向を有する。格子１０９の格子点の方向は外方向、すなわち座標系１０７のｙ軸の方向を指している。それゆえにデータ構造内で、格子１０９の表現は座標系１０７に関して予め決められた格子点、例えば格子点１１３の座標、座標系に関する格子点の方向、すなわち矢印１１４の方向、格子のサイズ、すなわちｘ方向とｚ方向それぞれでの正方形の数、および格子点の各々に関連する属性を有することが可能である。そのような表現の範例は下記でさらに詳細に述べられるであろう。
【００７９】
図１ｄはビルディング・ブロック１０１の面１０３（図１ｄに図示せず）の反対側の面１１６の接続格子１２０を例示している。ビルディング・ブロックのこの面はエッジ１１８で規定される穴１１７およびいわゆる二次ピンと呼ばれる小さい中心ノブ１１９を有する。物理的ビルディング・ブロックのこれらの穴はノブ１０２のような他のビルディング・ブロックのノブを受け入れることが可能となるように配置され、それにより、２つのビルディング・ブロックを協同して接続する。本発明によると、矢印１２１で表わされるようにこれらの穴は格子１２０の対応する格子点によって表わされる。
この実施形態によると座標系の原点が格子点１２２に対応することが気付かれる。
【００８０】
図１ｅは穴１０４を有するビルディング・ブロック１０１の面１０５の接続格子１２３を例示している。相応して、格子点１２４は穴１０４の接続性特性を表わす。
【００８１】
ディスプレイ、例えばコンピュータ画面上にビルディング・ブロックを図解で表現するとき、境界体積、座標系、および格子は示される必要がない。図解表現はビルディング・ブロック自体の表現を含むだけである。
【００８２】
図２ａ〜ｃは構造要素およびそれらの接続素子の範例を例示している。
図２ａは２つのビルディング・ブロック２０１と２０２を示している。ビルディング・ブロック２０１はその上面に４つのノブ２０３、および底面（図示せず）に４つの対応する穴を有する積み木である。積み木２０２は互いに直交する平面を有する表面を備えたビルディング・ブロックの範例である。特に、ビルディング・ブロック２０２は傾斜面２０４を有する。図２ａに例示されるように、それらの今の位置ではビルディング・ブロック２０１と２０２は接続されない。
【００８３】
図２ｂは非長方形の上面と底面を有するビルディング・ブロック２１０を示している。底面は１つまたは複数の他のビルディング・ブロックの対応するノブを受け入れるための穴２１１、２１２、および２１３を有する。これらの穴はエッジ２１４、二次ピン２１５、ならびに角２１６と２１７によって規定される。それゆえに、上記の要素すべての特性がビルディング・ブロックの面の接続性特性を決定する。
【００８４】
図２ｃはビルディング・ブロック２２１に接続され、それによって組み合わせビルディング・ブロックを形成するビルディング・ブロック２２０を例示している。ビルディング・ブロック２２０はその上面に、他のビルディング・ブロックの対応する穴に係合するノブ２２２を有する。しかしながら、図２ｃで例示されるように、同様に他の接続タイプも達成されることが可能である。ノブの間の隙間２２３はブロック２２１の側面２２４のような他のコネクタのためのレセプタとして機能する。物理的ビルディング・ブロックに関して、この特性は隙間の寸法とビルディング・ブロック２２１の寸法、すなわち側部の幅２２５によって決定される。本発明によるデジタル表現では、これらの特性は下記でさらに詳細に例示されるであろうが、接続点の対応する属性によって表わされる。
【００８５】
図２ｄは、いくつかの積み木を含む他のビルディング・ブロックに対するビルディング・ブロックの無効接続を例示している。ビルディング・ブロック２３１は積み木２３２、２３３、２３４、２３５、２３６、および２３７を有する。各々のビルディング・ブロックが上述したようなノブ・コネクタと対ノブ・レセプタを有する。ビルディング・ブロック２３２、２３３、および２３６は上側ならびに側面にノブ・コネクタを有する。特に、ビルディング・ブロック２３２は側面にノブ２３８を有し、一方ビルディング・ブロック２３３は側面にノブ２３９を有し、ビルディング・ブロック２３６はその側面にノブ２４０を有する。
【００８６】
図２ｄの範例では、ビルディング・ブロックの寸法のせいでそれらのノブおよび、したがってそれらの対応する接続点は規則的な格子を形成しない。その結果、もしもビルディング・ブロックが×印２４２、２４３、および２４４で示されるようなその接続点を備えて点線２４１で示される位置に置かれるように試みられると、有効な接続は不可能である。本発明による方法がどのようにしてこのタイプの状況を検出するかが下記で述べられるであろう。
【００８７】
図３はビルディング・ブロックとそれに対応する接続性格子の透視図を示している。ビルディング・ブロック３０１は８個のノブ３０３ａ〜ｈを備えた上面３０２、対応する穴（図示せず）を備えた底面、および側面３０４を有する。図３では、上面と底面の接続性格子３０５と３０６がそれぞれ示されている。接続点は円３０７ａ〜ｋで例示されるような円によって具体的に示される。それゆえに接続点３０７ａ〜ｈはノブ３０３ａ〜ｈにそれぞれ対応する。側面３０４はどのような接続素子も有さないので、それらについて接続講師が規定される必要はない。別の代替選択肢となる実施形態では、空洞のレセプタだけを有する接続格子が側面に関して規定されることが可能である。
【００８８】
図３から見受けられるように、規則的格子内に配置された接続点によるビルディング・ブロックの接続素子の表現は、物理的ビルディング・ブロック上の接続素子の物理的配置に一定の拘束条件を課す。
格子３０５はビルディング・ブロックの上面の平面内に配置され、そこからノブ３０３が延びる。
【００８９】
図３の範例では、格子点が正方形格子内に置かれ、各々の正方形は任意の長さ単位（ＬＵ）の５×５単位の寸法を有する。それゆえに、この幾何学構造では、接続素子もやはり対応する正方形格子上に配置され、ビルディング・ブロックの平面内の接続素子間の距離は１０ＬＵの倍数である。図３の範例では、ビルディング・ブロックの上側表面と下側表面は長方形であり、２０ＬＵ×４０ＬＵの寸法を有し、隣り合う接続素子は１０ＬＵで間隔を置かれる。
【００９０】
他方で、垂直方向では、接続素子は１２ＬＵで間隔を置かれる。それゆえに、異なる寸法で格子寸法が変えられることが可能であり、それにより、上記の図２ｄに示されるような状況を生じさせることが可能である。
接続点の場所はビルディング・ブロックの内部座標系３０８に関して規定される。
【００９１】
図４は図３のビルディング・ブロックの上面図を示している。接続性格子３０５が格子点を含めて示されている。図３の範例中の格子点の方向は図面平面から外を指している。
【００９２】
一実施形態では、接続点の格子を表わすデータ構造は各々の接続点について、座標系３０８に関する接続点の座標、接続素子の方向、および接続性のタイプを含む。
【００９３】
新たなビルディング・ブロックを設計するとき、ビルディング・ブロックのデジタル表現が作り出されることが必要である。図４の範例中の積み木は上部表面上の４５個の接続点および底部表面上の４５個の接続点を有する。接続点の各々について上記の値を特定することは時間を浪費し、誤りを生じがちな作業である。
【００９４】
しかしながら、多くのタイプのビルディング・ブロックに関して接続点は規則的な構造で配置され、それにより、自動化されたデータ作成が可能になり、かつ好都合である。図４の範例では、接続点の座標は反復的に判定されることが可能であり、接続素子の方向は格子の接続点すべてについて同じである。
【００９５】
それゆえに、好ましい実施形態では接続点の格子を表わすデータ構造は、
・座標系３０８に関する格子点４０１の座標。それゆえに図４の範例では格子点４０１のＬＵでの座標はＰ０＝（−５，１２，−１５）であり、
・接続素子の方向、すなわち図４の範例では（０，１，０）、すなわち座標系３０８のｙ軸の方向、
・ｘおよびｚ方向での格子点の数、すなわち図４の範例ではそれぞれｎｘ＝９、ｎｚ＝５。
・各々が対応する接続点の接続特性を含む５×９データ構造のアレイを含む。そのようなアレイの範例は下記で述べられるであろう。
【００９６】
図４の範例では、各接続点の座標はｉ＝０，．．．，４、ｊ＝０，．．．，８に関して（ＬＵで）Ｐ０＋（５ｉ，０，５ｊ）と表わされることが可能である。
その後、接続点の特性はｉとｊで索引を付けられる二次元のアレイＣとして表わされることが可能であり、ここでＣ［０，０］は接続点４０１に対応し、Ｃ［ｉ，ｊ］は座標Ｐ０＋（５ｉ，０，５ｊ）を備えた接続点に対応する。
【００９７】
別の実施形態では、接続性格子の平面内で二次元座標系が定義されることが可能である。図４では、これは座標系４０２で具体的に示される。その後、二次元座標系はその原点４０１の座標およびビルディング・ブロックの内部座標系３０８に関する回転マトリックスによって表わされることが可能である。
【００９８】
図５ａ〜ｂは、本発明の実施形態による、接続点を表わすデータ構造の範例を具体的に示している。
【００９９】
図５ａは図４のビルディング・ブロックの格子の接続点を表わすデータ構造を具体的に示している。このデータ構造は上述したような二次元アレイＣ［ｉ，ｊ］に対応する。各々のアレイ素子が接続タイプに対応する。例えば、ノブ（例えば図４のノブ３０３）はＣ［ｉ，ｊ］＝Ｋと表わされ、２つのノブの間の隙間（例えば図４の隙間４０４）は「ダブルエッジ・ギャップ」と称され、Ｃ［ｉ，ｊ］＝２ＥＧと表わされ、４つのノブの中心の隙間（例えば図４の隙間４０５）は「チューブ・ギャップ」と称され、Ｃ［ｉ，ｊ］＝ＴＧと表わされる。ノブは他のビルディング・ブロックのレセプタ、例えば図２ｂに例示された穴２１２によって受け入れられることが可能なコネクタである。エッジ・ギャップは、例えば図２ｃに例示されるエッジかまたは図２ｂに例示されるエッジ２１１を受け入れることが可能なレセプタである。チューブ・ギャップは他のコネクタ、例えば適切なサイズのノブもしくはチューブを受け入れることが可能なレセプタである。
【０１００】
ビルディング・ブロックの境界では他の接続タイプが生じる。角（例えば図４の角４０１）は、それらが４つの隣接から１つだけを有するチューブ・ギャップに対応するのでＣ［ｉ，ｊ］＝１／４ＴＧと表わされる。同様に、Ｃ［ｉ，ｊ］＝１／２ＴＧは４つのノブから２つをその周りに有するチューブ・ギャップ、例えば図４の接続点４０６を表わす。最後に、Ｃ［ｉ，ｊ］＝ＥＧは１つだけの隣接ノブを有するエッジ・ギャップ、例えば図４の接続点４０７に対応する。
【０１０１】
図４に描かれたそれのようであるが、しかし異なる数のノブを備えたビルディング・ブロックが図５ａに示されたそれに類似した接続性のアレイに対応することは理解される。それゆえに、このタイプのビルディング・ブロックを表わすデータ構造はビルディング・ブロックの寸法を特定することによって自動的に作り出されることが可能である。
【０１０２】
概して、規則的な幾何学構造を有する構造要素については、接続性アレイの異なるタイプの数が例えば図３のビルディング・ブロックのように規則的なビルディング・ブロックの上部、側部、および底部の表面に関するアレイ・タイプで規定され得ることは理解される。その後これらのアレイ・タイプの例が類似した構造要素の様々な異なるタイプとサイズについて自動的に作り出されることが可能である。それゆえに、多様なビルディング・ブロックを表わすデータ構造が効率的な方式で作り出され得ることが利点である。
【０１０３】
図５ｂは図２ｂに示されたビルディング・ブロックの底面に対応する接続性のアレイを示している。ここで、Ｃ［ｉ，ｊ］＝ＥＣはエッジの角、例えば図２ｂの２１７に対応し、Ｃ［０，０］＝ＥＣに対応する。さらに、Ｃ［ｉ，ｊ］＝Ｅは図２ｂのエッジ２１４のような「エッジ」に対応する。Ｃ［ｉ，ｊ］＝３／４ＥＣは図２ｂの角２１６によって例示されるような角に対応する。Ｃ［ｉ，ｊ］＝ＡＫは「対ノブ」、すなわちノブを受け入れるための穴２１２に対応し、その一方でＣ［ｉ，ｊ］＝ＳＰは「二次ピン」２１５に対応する。
【０１０４】
たとえ図５ａ〜ｂの接続タイプが接続素子の実際の物理的機能のニーモニック表示であるとしても、接続タイプが他のどのような適切な手段、例えば列挙型接続タイプ、ビット・コーディングなどによっても符号化され得ることは理解される。
【０１０５】
概して、接続タイプは接続の種類とパラメータを含むことが可能である。例えば、接続の種類はα＝１／４、１／２、３／４、１を備えたチューブギャップαＴＧである。
【０１０６】
異なる接続タイプの接続特性は対応する接続表に規定される。接続表は、接続タイプの各々の対について接続性特性を示す。接続表はルックアップテーブルとして適切なデータ構造内に保存されることが好ましい。そのような接続表の実施形態が表１に例示されている。
【表１】
【０１０７】
それゆえに、表１の各々の欄は対応する２つの接続タイプの接続性を示している。
表１の短縮表示された接続タイプはつぎの通りである。
Ｋ：ノブ、例えば図１ａ〜ｅのノブ１０２、すなわち円形の素子。
ＳＰ：二次ピン、例えば図２ｂの２１５、すなわち小さいノブ。
Ｅ：エッジ、例えば図２ｂのエッジ２１４、すなわち要素の外側エッジ。
αＥＣ：パラメータαを備えたエッジの角である。３／４ＥＣは図２ｂで角２１６によって例示されるような角に対応する。
ＶＣ：空洞コネクタ、すなわち殆どの他の要素を拒絶せず、また、他の素子、例えば滑らかな表面と接続することもないビルディング・ブロックの部分。空洞コネクタはノブを拒絶するが、しかし他のどのようなレセプタまたはコネクタとも相互作用しない。
αＡＫ：パラメータαを備えた対ノブ、例えば図２ｂの対ノブ２１５、すなわちノブが嵌合する不規則な形状の穴。
αＴＧ：パラメータαを備えたチューブ・ギャップ、例えば、図４はα＝１を備えたチューブ・ギャップ４０５、すなわち４つの隣り合うノブの間の領域であって、これにチューブが嵌合することが可能である。
αＥＧ：パラメータαを備えたチューブ・ギャップ、例えばα＝２を備えたダブルエッジ・ギャップおよびα＝１を備えたエッジ・ギャップ４０７、すなわち２つのノブ間またはノブとエッジ間の隙間。
ＶＲ：空洞レセプタ、すなわちどのような他の素子も拒絶せず、また接続もしないビルディング・ブロックの部分。
Ｔｕ：チューブ、ノブのためのレセプタであることが可能であり、４つの隣り合うノブの間、すなわちチューブ・ギャップに詰め込まれることが可能なコネクタであることが可能な環状のチューブ。
【０１０８】
表１で、上記の接続タイプの接続性は次のように示される。
・Ｔ：真、すなわち接続が有効であり、対応する接続素子が係合することで２つのビルディング・ブロックを接続する。
・Ｆ：偽、すなわち接続はこの位置では許容されない。
・Ｖ：空洞または中立、すなわち接続を妨げるものが存在しないが、しかし実際にどちらか接続するものもない。
【０１０９】
例えば、表１によると、ダブルエッジ・ギャップ（α＝２を備えたαＥＧ）はエッジ（Ｅ）と空洞接続を作り出し、その一方でエッジ・ギャップ、すなわちα＝１を備えたαＥＧはエッジ（Ｅ）と実際に接続する、すなわちこのケースでは接続性が真（Ｔ）である。
表１の接続表が対角線に沿って対称であることが気付かれる。
【０１１０】
それぞれの既にある接続タイプと共に新たな接続タイプの該当する接続性を対応する横列と縦列に追加することによって上記の表が新たな接続タイプを含むように容易に拡張され得ることがさらに気付かれる。
【０１１１】
図６はエッジからエッジへの延長になっている２つの構造要素の上面図を示している。図６の範例では、２つのビルディング・ブロック６０１と６０２がエッジからエッジへの延長で配置される、すなわちそれらの上部表面が同じ平面内に置かれ、それらのそれぞれの接続点が破線６０３で示されるように同一空間を占める。図６の範例では、ビルディング・ブロック６０１と６０２各々は図３と４に示されたタイプであると仮定されている。
【０１１２】
２つのビルディング・ブロックをエッジからエッジへの延長で配置することによって、領域６０３で重複する接続点の有効接続タイプが変えられる。例えば、接続点６０５はビルディング・ブロック６０１のタイプ１／４ＴＧの接続点およびビルディング・ブロック６０２のタイプ１／２ＴＧの接続点に対応する。しかしながら、図６のエッジからエッジへの延長で配置されると、組み合わされた接続点６０５はタイプ３／４ＴＧである。同様に、接続点６０６はビルディング・ブロック６０１と６０２各々のタイプＥＧであるが、組み合わされたビルディング・ブロックではそれはタイプ２ＥＧである。最後に、接続点６０７はビルディング・ブロック６０１と６０２各々のタイプ１／２ＴＧであるが、組み合わされたビルディング・ブロックではそれはタイプＴＧである。
【０１１３】
それゆえに、概して接続素子の接続性特性は他の構造要素と関係した対応する構造要素の配置に応じて変化する可能性がある。
【０１１４】
本発明によると、この状況は組み合わされた、または結果的に生じる重複接続点の接続タイプを記述する組み合わせ表を規定することによってモデル化されることが可能である。表２はそのような組み合わせ表の範例であり、上記で導入された接続タイプの組み合わせを示している。この組み合わせ表はルックアップテーブルとして適切なデータ構造内に保存されることが好ましい。
【表２】
【０１１５】
表２では、各々の欄は組み合わされる接続タイプを含む。もしも２つの接続タイプの組み合わせがどのような他の接続タイプに接続する接続タイプも生じない場合、表の記入事項はＦである。
【０１１６】
例えば、エッジ・ギャップ（βＥＧ）が空洞コネクタ（ＶＣ）、例えば空の表面の隣に配置されると、結果的に生じる接続要素は広い隙間であると考えられる。表２では、これは（β＋１）ＥＧによって近似される。
【０１１７】
上記の組み合わせ表が、２つ以上の接続素子が組み合わされる状況、例えば３つもしくは４つのビルディング・ブロックの角、で結果的に生じる接続タイプを判定するために使用されることもやはり可能であることがさらに理解される。この状況では、例えば３つの接続素子について結果的に生じた接続タイプは、第１に、最初に組み合わされた接続素子の２つについて結果的に生じた接続タイプを判定し、それに続いて、結果的に生じた第１の接続タイプと第３の接続素子の接続タイプの組み合わせの結果として生じた第２の接続タイプを判定することによって判定される。
【０１１８】
それぞれの既にある接続タイプと新たな接続タイプの組み合わせから結果的に得られる該当する結果の接続タイプを該当する横列と縦列に追加することによって上記の表が新たな接続タイプを含むように容易に拡張され得ることがさらに気付かれる。
【０１１９】
それゆえに、上記で、ビルディング・ブロックの接続性特性の効率的で拡張可能な表現のためのデータ構造が、接続タイプをどのように組み合わせるかに関する法則の効率的で拡張可能な表現と同様に開示される。
【０１２０】
図７はビルディング・ブロックの２つの接続グループを有する幾何学的対象物の透視図を示している。この幾何学的対象物は５つの要素７０１、７０２、７０３、７０４、および７０５を含む。図７の範例では、幾何学的対象物はビルディング・ブロックの２つのグループを含み、ビルディング・ブロックの第１のグループはビルディング・ブロック７０１、７０２、および７０３を含み、その一方で第２のグループはビルディング・ブロック７０４と７０５を含む。この範例でのビルディング・ブロック７０１と７０４は、例えば上述の単一のノブと対ノブの接続、またはビルディング・ブロックの互いに相対した回転を妨げない他の何らかの方式、例えばヒンジ接続、共通の線上での２つ以上のノブと対ノブの接続などによって回転可能に接続される。それゆえに、図７の幾何学的対象物は、幾何学的対象物に与えられた位置と配向の制約に必ずしも束縛されないビルディング・ブロックの範例である。そのような接続の他の範例は、接続されたビルディング・ブロックの相対的平行移動を可能にするビルディング・ブロック間の接続を含む。それゆえに、ビルディング・ブロックのそのようなグループは、格子系７０６と７０７で示されるように別々の座標系で述べられることを必要とする可能性がある。
【０１２１】
図８は、幾何学的対象物のコンピュータ読み取り可能なモデルを作り出すコンピュータ導入処理法の一部として構造要素を配置する方法を示すフロー図である。
【０１２２】
最初の工程８０１で、予め決められた初期位置に構造要素が置かれる。この構造要素は上記で例示されたようなデータ構造によって表現され、構造要素の位置と配向は、適切な座標系、例えば三次元の右手「ワールド」座標系または基準座標系に関する構造要素の内部座標系の位置と配向を説明する適切な座標系によって記述される。
【０１２３】
それゆえに、所定の背景、例えば場面、幾何学的対象物などに関すると、この処理法は各々がその背景の中に置かれたビルディング・ブロックを表現するデータ構造のセットを作り出して維持する。その背景の中に新たな構造要素を配置することはデータ構造のそのセットの一部として対応するデータ構造の新たな事例を作り出すことに該当する。
【０１２４】
構造要素の配置は、例えば幾何学的対象物のデジタル・モデルを作成する対話式処理の間にユーザの命令によって生じさせられることが可能である。例えば、コンピュータが、ユーザが異なる構造要素、例えば異なるタイプ、形状、サイズ、色などの構造要素を選択し、選択された構造要素をコンピュータのディスプレイ上に表示される三次元グラフィック場面内で予め決められた位置と配向に配置することを可能にするユーザ・インターフェースを提供することが可能である。例えば、このユーザ・インターフェースは構造要素を置くためのドラッグ・アンド・ドロップ操作ならびに構造要素を操る、例えば回転させるための操作を提供することが可能である。
【０１２５】
一実施形態では、構造要素の配置は、例えばすべての距離が任意の長さ単位（ＬＵ）の倍数として測定され、基準格子の格子点が１ＬＵで間隔を置かれることが可能な系の、例えば予め決められた格子上の別々の位置へと限定されることが可能である。
【０１２６】
工程８０２では、コンピュータ導入による処理が、工程８０１で配置された構造要素がその場面に既に存在する何らかの他の構造要素、例えばユーザによって以前に配置された構造要素と交わる場所を検出する。この衝突検出はどのような適切な衝突検出法で実行されることも可能であり、構造要素の境界体積に基づいた衝突検出法が好ましい。そのようなアルゴリズムの範例は、例えばＤａｖｉｄ Ｈ．Ｅｂｅｒｌｙの「３Ｄ Ｇａｍｅ Ｅｎｇｉｎｅ Ｄｅｓｉｇｎ」、Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ、２００１年に開示されている。
【０１２７】
衝突検出は、構造要素が配置された位置が他の構造要素によって既に占められているという結果に結び付く可能性がある。この状況は予め決められた限度よりも大きい境界体積の交差部を検出することによって検出されることが可能である。もしも無効な交差部が検出されれば、この位置と配向での構造要素の配置は拒絶されることが可能である。
【０１２８】
もしも無効な交差部が検出されなければ、本処理法は工程８０３で新たに配置される構造要素が他の構造要素と有効に交差するかどうかを検査する。有効な交差部は、例えば予め決められた限度よりも小さいそれぞれの境界体積の交差部として検出されることが可能である。
【０１２９】
図１の実施形態では、構造要素の表現は接続素子を含めた境界体積（図１ａ）と構造要素本体を含むが接続素子を含まない境界体積（図１ｂ）の２つの境界体積を有する。衝突検出の工程はこれら２つの境界体積を使用して、もしも構造要素の接続素子を除いた境界体積が重なり合えば無効な衝突を検出することが可能である。もしも接続素子を含む境界体積が重なり合うが、しかし接続素子を除いた境界体積が重ならない場合、あるいはあらゆる境界体積のあらゆる表面が交差するが境界体積が重なり合わない場合、有効な重複が検出される。
さらに、それらの境界体積の軸が同じ基準座標系に対応するように境界体積が配向されているかどうかが検出される。
【０１３０】
もしも有効な衝突が検出されなければ、本処理法は何らかの適切な方策に従って進行することが可能である。いくつかの実施形態ではどのような以前の構造要素にも接続せずに新たな構造要素を空洞内に配置することが受容可能である可能性があり、いくつかの実施形態では、もしも既にその場面に存在する他の構造要素が無い場合にのみこれは受容可能である可能性がある。なおも別の実施形態ではこれが拒否される可能性がある。例えば、一実施形態では、ユーザによって置かれる構造要素を伴なわないどのような初期場面も初期設定の構造要素、例えば基礎平面の上に構造要素を設置するための接続素子を備えた支持平面を有することが可能である。
【０１３１】
工程８０３でもしも新たに設置される構造要素と１つまたは複数の他の構造要素の間に有効な衝突が検出されると、本処理法は工程８０４に続き、新たに設置される構造要素がそれに有効に交差する（複数の）構造要素に有効に接続されることが可能であるかどうかをチェックする。この接続性検出の部分工程の好ましい実施形態は下記でさらに詳しく述べられるであろう。この接続性検出は結果として、もしも構造要素がそれと交差する（複数の）構造要素に有効に接続するならば構造要素の設置の受容につながり、もしも交差する構造要素のうちのいずれか１つと有効に接続しなければ拒絶につながることが可能である。
【０１３２】
いったん構造要素の設置が受容もしくは拒絶されると、本処理法はユーザの行為によって、例えば拒絶された構造要素を別の代替選択肢の位置および／または配向に置き換えることによって、他の構造要素をその場面に設置するなどによって再び開始されることが可能である。
【０１３３】
図９は本発明の一実施形態に従って第１のデジタル構造要素を他の第２のデジタル構造要素に接続する部分工程８０４のフロー図を示している。例えば、第１の構造要素が新たに設置される積み木であり、第２の構造要素が以前に構築された積み木構造であることが可能であり、検出のアルゴリズムが新たに設置される積み木と第２の構造要素の間の交差部を検出し終えている。
【０１３４】
以下では、初期位置で構造要素はそれらの境界体積の主軸が右手直交ワールド座標系のｘ、ｙ、およびｚ軸に対応するように配向されると仮定される。
この実施形態では、接続素子自体は性質および形状で異なるけれども構造要素上の接続素子の設置についていくつかの予め決められた法則が課されることがさらに仮定される。
【０１３５】
接続素子の設置に関する仮定は、各々の構造要素について、同じ水平平面内のすべての接続素子の軸が、隣り合う区分間に一定の距離を備えた直交格子の区分に対応することである。
水平平面内および垂直平面内の接続素子の軸間距離は同じである必要がない。
【０１３６】
最初の工程９０２で、検出された交差部に属する第１の構造要素および第２の構造要素のすべての接続点。既に接続されているわけではないそれら接続点だけが考慮される必要があり、これらの接続点は該当接続点と称されるであろう。
【０１３７】
工程９０３で、第１の構造要素の第１の該当接続点が選択される。これは任意に選択された接続点、ユーザによって選択された接続点などであることが可能である。
【０１３８】
工程９０４で、第１の構造要素の選択された接続点について、本処理法は選択された接続点と同じ座標を有する第２の構造要素のいずれかの該当接続点が存在するかどうかをチェックする。構造要素が別々の体積基準格子内に配置され、すべての座標が任意の単位長さの倍数である一実施形態では、座標の正確な一致が必要とされる可能性がある。連続的または外見上連続的な基準座標系では、格子点が予め決められた限度内で一致することが必要とされる可能性がある。
もしもそのような一致する接続点が見つからない場合、本処理法は工程９１４に続く。
【０１３９】
工程９１４で、選択された接続点の予め決められた近接の中にいずれか他の接続点が存在するかどうかを検出する。図９の実施形態では、予め決められた近接は（ｘ，ｙ，ｚ）の選択された接続点の周りの立方体（ｘ±５ＬＵ，ｙ±５ＬＵ，ｚ±５ＬＵ）に相当するが、なぜならばこの実施形態では２つの隣り合う接続素子の間の距離が１０ＬＵだからである。もしも選択された接続点の予め決められた近接の中にいずれか他の接続点が存在するならば、２つの構造要素の間の接続は拒絶され（工程９１１）、アルゴリズムが終了する。それゆえに、この実施形態で接続点は規則的な格子上に配置されるので、構造要素の無効な設置は効率的に検出されることが可能である。もしも第１の構造要素の該当接続点のうちの１つにに関して第２の構造要素の該当接続点との不一致が見つけられれば、第１の構造要素の残りの接続点はチェックされる必要が無く、それにより、検出工程のスピードを上げる。上記の検査は、ノブ２３９に対応する接続点が規則的な格子に関して置き違えられているので図２ｄに示されたような接続が拒絶されることを確実化する。図２ｄの範例では、高さのわずかの違いのせいで接続点２４３が境界体積の交差部に属することがないので接続点２４３が不一致を生じさせることはない、すなわち積み木２４１と２３６の間の接触はないことが気付かれる。
【０１４０】
もしも工程９１４で不一致を生じる該当接続点が見つけられなければ、本処理法は工程９０９に続く。
もしも工程９０４で一致する接続点が見つけられた場合、本処理法は工程９０５に続き、選択された接続点の予め決められた近接、この実施形態では上述したように（ｘ，ｙ，ｚ）の選択された接続点の周りの立方体（ｘ±５ＬＵ，ｙ±５ＬＵ，ｚ±５ＬＵ）の中にいずれか他の接続点が存在するかどうかが検出される。もしも予め決められた近接の中で他の接続点が見つけられると、その位置が拒絶される（工程９１１）。そうでない場合、本処理法は工程９０６に続く。
【０１４１】
別の代替選択肢となる実施形態では上記の限定が望ましくない可能性がある。さらに、なおも別の実施形態では上記の限定は特定の接続タイプ、例えば上記の範例では「空洞」と異なるすべての接続タイプに限られることが可能である。
【０１４２】
工程９０６で、本処理法は選択された接続点および検出された一致接続点が反対の方向を有するかどうか、すなわちそれらの随伴する方向が共通の線に沿っているが反対の配向であるかどうかを検出する。それゆえに、係合するために適した相対的配向で配置された接続素子だけが受容される。
別の代替選択肢となる実施形態で、この限定が、例えば接続素子が或る範囲の配向を受け容れる実施形態で或る範囲の配向を受容することによって緩和されることに留意されたい。
【０１４３】
もしも接続点の相対的配向が受容されれば、本処理法は工程９０７に続き、そうでない場合、その位置が拒絶される（工程９１１）。
【０１４４】
工程９０７で、選択された接続点およびそれに対応する検出された一致接続点の接続タイプが、保存された接続表９１３、例えば上記の表１による接続表から接続タイプの対応する対の接続性法則を取り出すことによって比較される。この実施形態では、表１に関連して述べられたように接続は真、偽、または空洞であることが可能である。
【０１４５】
それに続く工程９０８で、接続性の結果が「偽」、すなわち対応する接続タイプの間で有効な接続が不可能であるかどうかが検査される。もしも接続性の結果が「偽」であれば、第１の構造要素の位置が拒絶され（工程９１１）、そうでない場合、接続性結果は保存され、本処理法は工程９０９へと進む。
【０１４６】
工程９０９で、第１の構造要素のすべての該当接続点が処理されたかどうかが検査される。そうでなければ、まだ未処理の該当接続点が選択され（工程９１２）、上記の工程９０４、９０５、９０６、９０７、および９０８を現在選択された接続点で実行することによって処理が為される。
【０１４７】
もしも第１の構造要素のすべての該当接続点が処理されており、かつその位置が拒絶されなかった場合、その位置が受容され、本処理法は工程９１０に続く。工程９１０では、保存された接続性結果に基づいてどのようにして構造素子を接続するかが判定され、したがってそれらのそれぞれのデータ構造が更新される。これは図１０に関連してさらに詳しく述べられるであろう。いったんデータ構造が更新されると、この部分工程が終了し、図８の全体的処理法へと戻る。
【０１４８】
図１０は接続された構造要素を表現するデータ構造を更新する部分工程９１０の実施形態のフロー図を示している。この更新は、第１および第２の構造要素の境界体積の交差部のすべての該当接続点について判定された接続性結果に基づいている。
【０１４９】
最初に工程１００１で、すべての接続性結果が「空洞」であるかどうかがチェックされる。もしもそうであれば、すなわちもしもこの構造要素の位置を妨げるものは無いがこの構造要素を接続するように実際に係合する接続素子も無い場合、新たな構造要素はその現在の位置で許容される。
【０１５０】
用途に応じて、第１および第２の構造要素のデータ構造は更新されることが可能である。構造要素は実際に接続されないので、第１の構造要素が第２の構造要素と組み合わされて組み合わせの境界体積などを有する組み合わされた構造要素になるはずがないことが好ましい。
【０１５１】
一実施形態では、追加的なアルゴリズムが、例えば境界体積に基づいて、この位置に置かれた物理的ビルディング・ブロックが落下するかどうか、傾斜するかどうかなどを決定し、したがってその位置を許容するかまたは拒絶する。
【０１５２】
そうでない場合、例えばもしも１つまたは複数の接続性結果が真であれば、本処理法は工程１００２に進み、そこで本処理法は構造要素がどのようにして接続されるか、すなわちそれらが固く接続されるか、または接続が相対的な回転、平行移動などを許容するかを判定する。
【０１５３】
図１ａ〜ｅの実施形態では、もしも正確に１つの接続結果が真であって他のすべてが空洞であれば、接続のタイプに応じて回転および／または平行移動が可能であり得る。さらに、もしも複数の接続結果が真であり、対応する接続点がすべて共通の線上にあれば、回転および／または平行移動が可能であり得る。
【０１５４】
もしも非固定型の接続が検出されると、本処理法は工程１００５に続き、第１と第２の構造要素は、それぞれの基準座標系、境界体積などをそれぞれが有するそれぞれのグループへと割り振られ、それにより、構造要素のグループの多様な相対的位置および／または配向をモデル化することが可能となる。そのような状況は図７に関連して例示された。
【０１５５】
それゆえに、構造要素の接続された構造は構造要素のいくつかのグループを含むデータ構造によって記述されることが可能である。或るグループは、すべての構造要素のすべての接続点が同じ直交格子の格子点となる方式ですべての構造要素が固く接続される構造である。構造要素の各々のグループは１つまたは複数の構造要素を含み、そこではこのグループが共通の直交座標系（格子）、境界体積、およびそのグループの構造要素の接続性格子を決定する。
【０１５６】
もしも工程１００２で固定式の接続が検出された場合、本処理法は工程１００３に続く。上記で図６に関連して述べられたように、第１および第２の構造要素の１つまたは複数の接続点は接続に起因してそれらの接続性を変える可能性がある。それゆえに、工程１００３で第１および第２の構造要素のそれらの接続点が検出され、それらは同じ位置および同じ方向を有する。それらの組み合わされた接続点について、上記で表２に関連して述べられたように、結果的に生じた接続タイプは保存された組み合わせ表１００６で調べられる。
【０１５７】
最後に工程１００４で、第２の構造要素のデータ構造が第１の構造要素から得られる情報で更新され、すなわち第２の構造要素の境界体積が第１と第２の構造要素の境界体積の合併であるように更新され、接続性格子は第１の構造要素の接続点もやはり含むように更新される。
【０１５８】
図８、９、および１０の処理工程を繰り返すことによって、複数の構造要素が、幾何学的対象物のデジタル・モデルを形成するように組み合わされることが可能である。それゆえに、上記で、幾何学的対象物のデジタル・モデルを作り出すための方法が開示された。
【０１５９】
本発明の範囲内で当業者が上記の方法の変形例を実行することが可能であることは理解される。例えば、上記の工程のうちのいくつかの順序が変えられることが可能であり、工程が組み合わされることが可能である等々である。
【０１６０】
さらに、不正確な設置に起因する、例えば同じ位置で接続点が見当たらないという理由、または接続点が正確に反対の方向を有さないという理由による新たな構造要素の位置の拒絶は、単純な拒絶ではなくさらなる処理へとつながることが可能である。一実施形態では、受容可能な位置が達成されることが可能であるかどうかを決定するために仮説に基づいた隣接位置またはわずかな移動が分析されることが可能である。これが結果として、予め決められた限度内で、構造要素が受容可能な位置を提供する最も近い位置にはまり込むことにつながることが可能である。
【０１６１】
さらに、多少の自由度、したがって複雑さをモデル化システムに与えるために、追加的な限定が課されることが可能であり、あるいは他の限定が緩和されることが可能である。
【０１６２】
構造要素が構造から外されると、例えば対応するユーザの命令に応答して、そのデータ構造は組み合わされたデータ構造から外される。一実施形態では、これは残りの構造要素の組み合わされたデータ構造を計算し直すことによって実施される可能性がある。
【０１６３】
図１１は、本発明の実施形態に従って幾何学的対象物のコンピュータ読み取り可能なモデルを作り出すためのデータ処理システムを示している。
１１０１で指定されるコンピュータ・システムは、本発明に従って幾何学的構造の設計、記憶、操作、および共有を容易にするように構成される。コンピュータ・システム１１０１は独立型システム、またはクライアント／サーバ・システムのクライアントとして使用されることが可能である。このコンピュータは、部分的に揮発性および不揮発性のメモリ手段、例えばハードディスクおよびランダム・アクセス・メモリ（ＲＡＭ）として導入されるメモリ１１０２を有する。このメモリはモデル符号インタプリタ１１０７、モデル符号発生部１１０８、ＵＩイベント処理部１１０９、中央演算処理装置１１０３によって実行可能なモデル化アプリケーション１１１０を含む。さらに、このメモリはモデル・データ１１１１を含む。
【０１６４】
符号インタプリタ１１０７は本発明に従ってモデルを規定する符号、すなわちモデルの構造要素のデータ構造を表わす符合を読み取って解釈するように構成される。好ましい実施形態では、符号インタプリタは本発明に従ってモデルを読み取り、コンピュータ・ディスプレイ上に表わすためにそのようなモデルを知られているグラフィック書式へと変換するように構成される。対象物のモデルを表現するための上述のデータ構造に基づいて、この変換はグラフィック計算の分野でよく知られているグラフィックの原理を適用することで当業者によって実行されることが可能である。
【０１６５】
ＵＩイベント処理部１１０９はユーザ・インターフェースとのユーザの対話を符号発生部１１０８で識別可能な適切なユーザ命令へと変換するように構成される。可能性があり、かつ識別可能な命令のセットは、要素のライブラリから構造要素を得る命令、他の構造要素に接続されるべき構造要素を配置する命令、構造要素を切り離す命令、構造要素を廃棄する命令、例えば回転などを開始することによって構造要素、構造要素のグループを操る命令を含むことが可能である。各々の命令と共にそれぞれのパラメータ、例えば構造要素の座標、タイプなどの付随のセットが存在することが可能である。
【０１６６】
符号発生部１１０８は上述のように本発明に従って、かつユーザ命令に応答して実際のモデルを記述するデータ構造を変更するように構成される。同時発生または引き続いて生じる作業として、符号インタプリタは符号発生部の結果を表わすために実行されることが可能である。
【０１６７】
モデル化アプリケーション１１１０はメモリ、ファイル、ユーザ・インターフェースなどを制御するように構成される。
【０１６８】
ユーザ１１０５はユーザ・インターフェース１１０６によってコンピュータ・システム１１０１と対話することが可能である。
【０１６９】
モデル、幾何学的表現、または他のデータをロードするために、コンピュータ・システムは入出力（Ｉ／Ｏ）ユニット１１０４を有する。入出力ユニットは多様なタイプの記憶媒体および多様なタイプのコンピュータ・ネットワーク、例えばインターネットへのインターフェースとして使用されることが可能である。さらに、入出力（Ｉ／Ｏ）ユニット１１０４はモデルを他のユーザと、例えば対話式で交換するために使用されることが可能である。
【０１７０】
メモリ１１０２、中央演算処理装置（ＣＰＵ）１１０３、ユーザ・インターフェース（ＵＩ）１１０６、および入出力ユニット１１０４の間のデータ交換はデータ・バス１１１２によって達成される。
【０１７１】
図１２ａは本発明の第１の実施形態による、傾斜表面および対応する境界体積を備えたビルディング・ブロック、例えば図２ａのビルディング・ブロック２０２の側面図を示している。ビルディング・ブロック２０２は傾斜表面２０４、およびビルディング・ブロック最上部のノブ１２０１を有する。この範例によると、ビルディング・ブロック２０２の表現は境界体積の階層を有する。第１の境界体積１２０２は傾斜表面を含み、その一方で第２の境界体積１２０３は互いに直交する側部を備えたボックスである。この範例によると、境界体積１２０３が他のビルディング・ブロックの対応する境界体積と交差部を有する場合にのみ２つのビルディング・ブロックは接触していると検出される。境界体積１２０２は接続されると考えられるビルディング・ブロックの初期の効率的な検出のために使用されることが可能である。ビルディング・ブロック２０２の表現が、図１ａ〜ｂに関連して述べられたように接続素子を含む境界体積のような追加的な境界体積を含むことが可能であることは理解される。
【０１７２】
図１２ｂは本発明の第２の実施形態による、傾斜表面および対応する境界体積を備えたビルディング・ブロック２０２の側面図を示している。上記の範例のように、このビルディング・ブロック２０２の表現は境界体積の階層を有する。しかしながら、この範例によると、この表現は、傾斜表面を備えた境界体積ではなく階段関数に似た形状を有する境界体積１２０４を含み、それにより、傾斜表面の近似を与えている。
【０１７３】
上記の方法およびシステムは物理的モデルを設計するためのコンピュータ・アプリケーション、例えば物理的構造要素の対応するセットの接続性の挙動をシミュレートするコンピュータ・アプリケーションに関連して応用されることが可能である。例えば、物理的玩具構造セットが前記構造セットのデジタル・バージョンによって補完されることが可能であり、それにより、利用可能な構造要素の数を限定することなくユーザ、例えば児童が模型をデジタル設計することを可能にし、遊び体験の面白さを提供する。物理的構造セットの複雑な接続性特性でさえ現実的にモデル化することを可能にし、同時に効率的なモデル化方法を提供する方法とシステムを提供することが本発明の利点である。その結果、ユーザは構造要素の提案の位置が構造セットの接続法則に対応するかどうかをコンピュータが判定するのを待つことを必要とせずに対話式のデジタル構造化処理を体験する。
【０１７４】
本方法はさらに、設計されたモデルの特性を分析すること、構造化命令を作り出すことなどに応用されることが可能である。概して、本方法はコンピュータ・ゲーム産業、および予め決められた３Ｄ要素が複数の接続法則に従って一体に置かれなければならない他のコンピュータ・グラフィックスの領域すべてで応用されることが可能である。
【図面の簡単な説明】
【０１７５】
【図１ａ】本発明の一実施形態による構造要素の表現を示す透視図である。
【図１ｂ】本発明の一実施形態による構造要素の表現を示す透視図である。
【図１ｃ】本発明の一実施形態による構造要素の表現を示す透視図である。
【図１ｄ】本発明の一実施形態による構造要素の表現を示す透視図である。
【図１ｅ】本発明の一実施形態による構造要素の表現を示す透視図である。
【図２ａ】構造要素およびそれらの接続素子の範例を例示する図である。
【図２ｂ】構造要素およびそれらの接続素子の範例を例示する図である。
【図２ｃ】構造要素およびそれらの接続素子の範例を例示する図である。
【図２ｄ】構造要素およびそれらの接続素子の範例を例示する図である。
【図３】ビルディング・ブロックおよびそれに対応する２つの接続性格子を示す透視図である。
【図４】図３のビルディング・ブロックの上面図である。
【図５ａ】各々が構造要素の表面の接続点を表わすデータ構造を例示する図である。
【図５ｂ】各々が構造要素の表面の接続点を表わすデータ構造を例示する図である。
【図６】エッジからエッジへの延長状態にある２つの構造要素を示す上面図である。
【図７】構造要素の２つの接続されたグループを有する構造要素を示す透視図である。
【図８】幾何学的対象物のコンピュータ読み取り可能なモデルを作り出す方法の中で構造要素を配置する方法を示すフロー図である。
【図９】本発明の実施形態による、デジタル構造要素を他のデジタル構造要素へと接続する方法を示すフロー図である。
【図１０】接続された構造要素を表わすデータ構造を更新する部分的方法を示すフロー図である。
【図１１】本発明の実施形態による、幾何学的対象物のコンピュータ読み取り可能なモデルを作り出すためのデータ処理システムを示す図である。
【図１２ａ】傾斜表面を備えたビルディング・ブロック、および対応する境界体積の範例を示す側面図である。
【図１２ｂ】傾斜表面を備えたビルディング・ブロック、および対応する境界体積の範例を示す側面図である。
【技術分野】
【０００１】
本発明は、予め規定された幾何学的要素によるバーチャル・リアリティのコンピュータ支援モデル化の分野に関する。
【背景技術】
【０００２】
バーチャル・リアリティのコンピュータ支援モデル化は幾何学的対象物のモデルを作り出し、そのモデルを解釈し、そのモデルを操作し、そうでない場合はコンピュータ・システムの中で幾何学的対象物のモデルを扱う作業である。
【０００３】
第１の観点から見ると、バーチャル・リアリティのモデル化は、現実の世界に導入する前にアイデアを可視化することを可能にするという点で興味深い主題である。もしもバーチャル・リアリティのモデルが十分に変更を加え易ければ、現実世界で同じ処理が実行されなければならなかった状況と比較して幾何学的対象物を開発して洗練する処理で多くの時間が節約されることが可能である。現実世界で対象物を描き出す単純な作業は数時間は簡単にかかるが、それに対してコンピュータは数ミリ秒または数秒以内に新たな色彩を塗布してモデルを可視化することが可能である。
【０００４】
第２の観点から見ると、バーチャル・リアリティのモデル化は、現実世界に存在する対象物のモデルを作り出し、コンピュータを介してそのモデルを可視化し、ある意味で操作することを可能にするという点で興味深い。その結果、現実世界の対象物のモデルは多様な目的で、例えば改善された文書作成のために保存されることが可能である。
【０００５】
コンピュータ支援型のバーチャル・リアリティのモデル化に関して膨大な量の考え得る用途が存在するけれども、特別な用途は娯楽または教育にバーチャル・リアリティのモデル化を使用することである。
【０００６】
物理的構造の玩具セットの様々なタイプのモデル化概念はそれ自体知られている。特に、モジュールもしくは半モジュールを使用する概念は有名であったし今もそうである。通常、これらの概念は予め作成された要素のセットを供給し、それらは予め作成された要素のモジュールに従って何らかの予め決められた方式で互いに相互接続されることが可能である。予め作成された要素は特定のモデル化作業に適したよく知られている対象物に類似している。したがって、例えば家屋のモデルを構築する場合、それらの要素はブロック、屋根瓦、ドア、および窓に類似している。この方式で要素を選択する目的は、新しいモデルが作成されなければならない度に家屋のすべての細部が規定される状況と比較して家屋のモデルの構築に含まれる作業が大幅に減らされることである。しかしながら、家屋または他の対象物を構築する完全な自由度はモデルを構築する簡易性と交換される。
【０００７】
予め規定された要素を有するこの手法はコンピュータ支援型バーチャル・リアリティのモデル化の技術ではよく知られている。また、互いに相互接続されることが可能なモジュール要素を有する概念もよく知られている。しかしそれがコンピュータ内でのそのようなモデルの表現に至ると、予め規定された要素およびモジュール・システムを有する概念の便宜は先行技術では完全に達成されない。
【０００８】
コンピュータ支援型設計およびモデル化にコンピュータが使用されてきた以上、大きな計算努力を必要とする作業はどのようにモデルが見えるかの計算を含めたモデルの可視化と操作であった。その理由の１つはバーチャル・リアリティ・モデルの複雑さおよび微調整が最近利用可能なコンピュータ技術および計算能力に従って拡大されてきたことである。
【０００９】
モデルを表現するデータの転送および交換に至ると、バーチャル・リアリティ・モデルの複雑さおよび微調整の欠点が極めて明確に現れる。現在、記憶ユニットまたはコンピュータ通信ネットワークの形式のいくつかのタイプの外部ユニットがコンピュータに接続され、その結果、モデルを記憶し、ロードおよび／または送信し、受信するための信号経路を拡張する。通常、そのような信号経路は単独のコンピュータ内の信号経路と比較して相対的に低い帯域幅を有する。したがって、モデルを表現するための効率的な仕組みが必要とされる。
【００１０】
特に、コネクタとそれに対応するレセプタといった接続素子を介して互いに相互接続されることが可能な予め規定された要素もしくは構成要素のモデルを作り出す背景では、互いに相対して或る位置に置かれたときに２つの要素が接続可能であるかどうかという全般的問題が発生する。物理的対象物の現実的モデルを作り出すために、例えばバーチャル・モデルが、モデル化される対象物の支持部品に接続されることなく表面よりも上に浮き出るどのような要素も有さないことを確実化するために、接続性の情報は重要な情報である。
【００１１】
殆どの現実世界の構造セットで、多様な方式で相互接続される可能性のある極めて多様な異なる構造要素が存在する。
【非特許文献１】Ｄａｖｉｄ Ｈ．Ｅｂｅｒｌｙ、「３Ｄ Ｇａｍｅ Ｅｎｇｉｎｅ Ｄｅｓｉｇｎ」、Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ、２００１年
【発明の開示】
【発明が解決しようとする課題】
【００１２】
それゆえに、様々な異なる構造要素が相互接続されることが可能である、幾何学的対象物のコンピュータ読み取り可能なモデルを作り出す方法を提供することが本発明の目的である。
【００１３】
構造要素が様々なあり得る方式で相互接続されることが可能である、幾何学的対象物のコンピュータ読み取り可能なモデルを作り出す方法を提供することが本発明のさらなる目的である。
【課題を解決するための手段】
【００１４】
上記およびその他の問題は複数の相互接続可能な構造要素から構築された幾何学的対象物のコンピュータ読み取り可能なモデルを作り出す方法によって解決され、そこでは各々の構造要素がその構造要素を他の構造要素と接続するためのいくつかの接続素子を有し、この方法は、
・複数の構造要素のうちの第１の１つまたは第２の１つをそれに対応する第１および第２のデータ構造として符号化する工程であって、それらの各々が対応する構造要素の接続素子を表わし、接続素子の各々がそれに付随して複数の予め決められた接続タイプのうちの１つを有する工程と、
・互いの予め決められた近隣内に配置された第１の構造要素の第１の接続素子および第２の構造要素の第２の接続素子を判定する工程と、
・第１および第２の接続素子が第１と第２の構造要素の間の接続を与えるかどうかを示す第１および第２の接続素子の対応する接続タイプの接続性情報を取り出す工程とを含む。
【００１５】
モジュールの玩具構造要素もしくは複数要素から成る対象物を表現するために都合の良いモデル構造とモデル構造の表現提供することが本発明の利点である。
【００１６】
極めて多様な構造要素の接続をモデル化するための方法を提供することが本発明のさらなる利点である。
【００１７】
異なるタイプのノブ、穴、チューブ、ヒンジ、エッジ、シャフトなどといった極めて多様な異なる接続素子の接続をモデル化するための方法を提供することが本発明のなおもさらなる利点である。接続のタイプを有する複数の接続素子を供給することによって、構造要素の接続特性の表現が与えられ、それは実際のコネクタの正確な幾何学形状とは無関係である。
【００１８】
特に、極めて多様な異なる接続素子の接続をモデル化するための方法が与えられ、それが物理的接続素子の外見およびそれらの構造と無関係であることは利点である。
【００１９】
それゆえに、異なるタイプの接続素子を含む異なる予め決められた構造要素の大規模なセットがモデル化されることが可能である。
【００２０】
構造要素という用語は、それを１つまたは複数の他の構造的要素へと接続するための接続素子を有するどのようなタイプの構造的要素も含み、物理的対象物を作り出すことが可能であり、コンピュータ上でデジタル式に表現されることが可能である。構造要素の範例は構造玩具セットの要素、例えば積み木などのようなビルディング・ブロックを含む。構造要素という用語はさらに、相互接続されたさらに小さい構造要素の集合体、例えば２つ以上の接続された積み木も含む。
【００２１】
一実施形態では、接続のタイプがいくつかの接続グループ、例えばコネクタ、レセプタ、および混合素子へとグループ化される。コネクタは他の構造要素のレセプタによって受け入れられ、それによって構造要素間の接続を供給する接続素子である。例えば、コネクタは他の要素の部分間を嵌合し、穴などに入ることが可能である。レセプタは他の構造要素のコネクタを受け入れることが可能な接続素子である。混合素子はレセプタおよびコネクタの両方として機能することが可能な部品であり、通常、他の構造要素の協同作用する接続素子のタイプに応じて決まる。
【００２２】
互いに対して回転されることが可能な異なる表面もしくは平面に沿った接続をモデル化するための方法を提供することが本発明のなおもさらなる利点である。
【００２３】
可動部分および／または回転することが可能な部分を有する複雑な対象物のモデル化を可能にする、幾何学的対象物のモデルのコンパクトな表現を提供することが本発明のなおもさらなる利点である。
【００２４】
幾何学的対象物のモデルのコンパクトな表現を提供することが本発明のなおもさらなる利点である。
【００２５】
極めて高速で作成と解釈を行なうことが可能なモデル構造およびモデル構造の表現を提供することがなおもさらなる本発明の利点である。
【００２６】
可視化を受けるモデルが作り出されるかまたは操作されるときの相対的に低い帯域幅の必要性および低い処理時間という意味で、コンピュータ・ネットワークを経由して配信されるために都合の良いモデル構造の表現を提供することがなおもさらなる本発明の利点である。
【００２７】
本発明の好ましい実施形態では、本方法は接続タイプの対の接続性情報を含む接続表を供給する工程をさらに含み、接続性情報を取り出す工程が、この接続表から接続性情報を取り出す工程を含む。
【００２８】
接続表という用語は接続タイプの対に関する接続性情報を保存するためのどのような適切なデータ構造も含むように意図されている。例えば、そのようなデータ構造は接続タイプの対によって索引を付けられるルックアップテーブルであることが可能である。
【００２９】
接続表を供給することによって、接続タイプの対に関する接続性情報を保存するための効率的で拡張可能なデータ構造が与えられる。さらに、高速の接続性検出が可能にされる。
【００３０】
本発明の別の好ましい実施形態では、それぞれのデータ構造の各々は対応する構造要素に相対したいくつかの格子をさらに表現し、各々の格子がいくつかの格子点を有し、構造要素の接続素子の各々が格子点のうちの１つと関係し、対応する接続タイプを有する。
【００３１】
それゆえに、関連する接続タイプを有する格子点を備えた正方形格子、三角形格子などといった格子構造を供給することによって、様々な接続素子の例えばサイズ、形状、接続特性などのような様々な特性は格子点の各々に付随する１つまたは複数の属性へと削減されることが可能である。その結果、構造要素の接続特性の効率的な表現が達成される。
【００３２】
接続素子を格子点と関連付けることによって、２つの接続素子が互いに予め決められた近隣にあるかどうかの特に単純な検出が可能である。例えば、一実施形態では、構造要素が共通の個別体積基準格子内に配置され、すべての座標が任意の長さ単位の倍数である場合、２つの接続素子が予め決められた近隣の中にあると考えられるためには座標の正確な一致が必要とされる可能性がある。連続的もしくは外見上連続的な基準座標系内では、格子点が予め決められた限度内で一致すること、すなわちそれらが互いに予め決められた近接の形式で配置されることが必要とされる可能性がある。近接のサイズはモデル化される物理的接続素子のタイプ、例えば接続のためにそれらが実際にどのように協同作用するかということ、および実行されるべき構造要素の配置の制度に応じて決めることが可能である。
【００３３】
それに沿って構造要素が他の構造要素へと接続され得る各々の平面が格子区分、例えば格子区分の各々が中心に格子点を有する場合には正方形へと分割されることが好ましい。
【００３４】
各々の接続素子がそれに関連する方向性を有し、その方向で接続素子がそれに対応する接続素子と係合し得ることを示すことが好ましい。
【００３５】
すべての接続素子は共通平面に配置され、近隣格子点間で予め決められた距離を備えた直交格子の区分に対応する共通の方向性を有することがさらに好ましい。構造要素のうちのすべての構造要素の接続素子が予め決められた規則に従って構造要素に配置され、各々の接続素子が対応する格子点と関係することを可能にすることが好ましい。
【００３６】
しかしながら、異なる非平行平面上の接続素子がそれぞれの格子点間で同じ距離を有する必要がないことに留意されたい。例えば、水平面上の接続素子間の距離は垂直平面上の接続素子間の距離とは異なることが可能である。
【００３７】
さらに、接続素子を予め決められた格子点と関係付けることによって、第１の構造要素の接続素子が第２の構造要素の接続素子の予め決められた近接内にあるかどうかの判定が効率的な方式で実行されることが可能となり、なぜならばその判定が近接格子点を識別することに限定されることが可能となるからである。
【００３８】
別の好ましい実施形態では、本方法はさらに
・接続タイプの対の予め決められたセットの各々について結果的に生じる接続タイプを含む組み合わせ表を供給する工程と、
・予め決められた幾何学的関係で互いに配置される第１と第２の接続素子を判定する工程と、
・第１と第２の接続素子の結果的に生じた接続のタイプを組み合わせ表から取り出す工程と、
・取り出された結果的に生じた接続のタイプを少なくとも１つの結果的に生じた接続素子へと割り当てる工程を含む。
【００３９】
それゆえに、接続素子の接続のタイプが動的である、すなわちそれらは構造要素がおかれる幾何学的背景に応じて変えられることが可能であり、それにより、物理的構造要素の接続特性のさらに現実的なモデル化を提供することが好都合である。特に、第１の構造要素の第１の接続素子と第２の構造要素の第２の接続素子は、予め決められた幾何学的関係で互いに配置されると個々の接続素子とは異なる接続特性を協同して提供する。
【００４０】
第１と第２の接続素子の協同効果はしばしばそれらの相互の幾何学的関係、すなわち接続素子が互いに関して配置される方式、例えばどの程度接近してそれらが互いに配置されるか、どのような相対的配向でそれらが互いに配置されるか、などによって決まるであろう。一実施形態では、これは第１と第２の接続素子が互いから予め決められた近接内で配置されるかどうかを判定することによってモデル化され、もしもそれらが互いからそのような近接で配置されるならば、判定された結果となる接続タイプを第１と第２の接続素子に割り当てる。
【００４１】
データ構造の中で、これは結果となる接続のタイプを少なくとも結果となる接続素子へと割り当てることによって表わされる。一実施形態では、結果となる接続素子は第１と第２の接続素子のうちの一方である。さらなる好ましい実施形態では、結果となる接続のタイプは第１と第２の接続素子の両方に割り当てられる。
【００４２】
もしも対応する構造要素が、接続素子がもはや必要な幾何学的関係に置かれないように再配置されると、第１と第２の接続素子が再割り当てされたそれらのそれぞれの元の接続タイプを有することがさらに好ましい。
【００４３】
別の代替選択肢となる実施形態では、結果となる接続素子は新たな接続素子である、例えば第１と第２の接続素子の位置に関係する或る位置を有するように規定されることが可能である。
【００４４】
いくつかの実施形態で、２つ以上の接続素子が組み合わされて結果となる接続のタイプを生じさせることが可能であることは理解される。
【００４５】
組み合わせ表という用語は接続タイプの対について結果となる接続タイプを保存するためのどのような適切なデータ構造も含むように意図されている。例えば、そのようなデータ構造は接続タイプの対によって索引を付けられるルックアップテーブルであることが可能であり、ルックアップテーブルの各々の記載事項は接続素子の対の組み合わせから結果的に生じる結果的接続タイプを含み、各々の接続素子は対応する接続タイプの対のうちのそれぞれ１つを有する。
【００４６】
組み合わせ表を供給することによって、接続素子の接続タイプがそれらの他の接続タイプとの組み合わせのせいでどのように変わり得るかについて情報を保存するために効率的で拡張可能なデータ構造が供給される。
【００４７】
特に、バーチャル・ビルディング・ブロックのケースでは、頻繁に生じる状況は２つのビルディング・ブロックが互いに隣り合って、すなわちエッジからエッジへと延びて配置される配座であり、それにより、隣接するビルディング・ブロックのエッジ上の接続素子が特性を変える。
【００４８】
さらなる好ましい実施形態では、この状況は構造要素に付随する格子の各々が少なくとも１つの格子エッジを有するときに効率的にモデル化され、本方法はさらに
・接続タイプの各々の対に関する結果となる接続タイプを含む組み合わせ表を供給する工程と、
・第１の構造要素の第１の格子が第２の構造要素の第２の格子とエッジからエッジへの延長で置かれており、第１の格子の第１のエッジが第２の格子の第２のエッジと位置合わせされているかどうかを検出する工程と、
・第１の格子の第１の接続素子に関して、第２の格子の対応する第２の接続素子を識別する工程と、
・第１と第２の接続素子の組み合わせの結果となる接続タイプを組み合わせ表から取り出す工程と、
・取り出された結果となる接続タイプを第１と第２の接続素子に割り当てる工程を含む。
【００４９】
エッジのうちのそれぞれ１つが互いに密に近接するかまたは互いに接触すらして構造要素が互いに隣り合って置かれると、対応するエッジ上の接続素子が他方の構造要素の対応するエッジ上、もしくは近くの接続素子のタイプに応じてその特性を変えることが可能である。
【００５０】
接続タイプの各々の対に関する結果となる接続タイプを含む組み合わせ表を供給することによって、および結果となる接続タイプを構造要素のエッジ上の接続素子に割り当てることによって、エッジからエッジへの延長が検出されれば、協同している構造要素の複雑な接続特性でさえモデル化されることが可能である。
【００５１】
エッジからエッジへの延長という用語は、対応する格子が組み合わされる格子に結合するように互いに隣り合って置かれた２つの格子の配置を含む。それゆえに、エッジからエッジへの延長という用語は、平行したそれぞれの格子エッジ、およびエッジに近い格子点が一致するように平行格子エッジに沿って予め決められた重なりを有する２つの平行の格子を含む。
【００５２】
本発明の別の好ましい実施形態では、それぞれのデータ構造の各々はさらに、対応する構造要素の境界体積を表わし、格子の各々は境界体積の表面に対応する。
【００５３】
それゆえに、格子が境界体積の表面に対応する構造要素に関して境界体積を供給することによって、たとえ構造要素が複雑な形状を有していても各々の構造要素は少数の格子によって表わされることが可能である。それゆえに、構造要素の形状の複雑さが接続タイプへと翻訳され、それが順々に属性として境界体積の表面に関連する格子点へと結び付けられるので、２つの構造要素の協同する接続素子の効率的な検出が達成されることが可能である。
【００５４】
さらに、知られている衝突検出アルゴリズムを使用することによって、境界体積は隣接する構造要素の検出のために効率的な表現を与える。
【００５５】
境界体積は互いに直行する側部を有する境界ボックスであることが可能であり、あるいは境界体積は異なる形状を有する。
さらなる好ましい実施形態では、本方法はさらに
・第１および第２の構造要素のそれぞれの位置を共通の体積基準格子に関して符号化し、対応する第１と第２の構造要素の第１と第２の格子が体積基準格子の第１と第２の平面にそれぞれ対応し、第１と第２の格子の格子点が体積基準格子のそれぞれの基準格子点に対応する工程と、
・第１と第２の格子が体積基準格子の共通平面に対応するかどうか、および第１の格子の少なくとも第１の格子点が第２の格子の第２の格子点と同じ基準格子点に置かれているかどうかを検出する工程とを含む。
【００５６】
それゆえに、体積基準格子、例えば立方体の体積格子を供給することによって、および表面格子を基準体積格子の平面として規定することによって、隣り合う格子点の特に効率的な検出を可能にする特に単純なデータ構造が与えられる。
【００５７】
境界体積は体積基準格子に関する平面として規定されることが好ましい。一実施形態では、それらは体積基準格子の格子平面と一致することが可能であり、場合によっては、体積基準格子の格子平面間の平面として規定されることが可能である。
【００５８】
本発明のまたさらなる好ましい実施形態では、本方法はさらに
・第１の格子と第２の格子の一致する格子点のすべての対を識別する工程と、
・識別された格子点の対の各々について接続性の表から接続性情報を取り出す工程と、
・少なくとも１つある格子点対が無効な接続に対応していれば第１と第２の構造要素の間の接続を否定し、そうではなく少なくとも１つある格子点対が有効な接続に対応していれば第１と第２の構造要素の間の接続を受け容れる工程とを含む。
【００５９】
それゆえに、２つの隣り合う構造要素が相互接続されることが可能であるかどうかを検出するための効率的な方法が提供される。一致する格子点という用語は同じ座標を有する格子点を含む。構造要素が個別の基準格子に配置され、すべての座標が任意の長さ単位の倍数である一実施形態では、座標の正確な一致が必要とされる、すなわち格子点が共通の基準格子点に置かれる。連続的もしくは外見上連続的な基準座標系では、格子点は予め決められた限度以内で一致することが要求される可能性がある。
【００６０】
接続素子の各々が付随の方向性をさらに有するとき、さらなる属性が各々の格子点に関連付けられ、それにより、さらなる自由度を提供する。
【００６１】
接続性情報という用語は、接続タイプの対の接続特性、例えば接続タイプの所定の対に関してこれらの接続タイプの２つの接続素子が接続を提供するかどうか、それらは接続を不可能にするかどうかについての情報を含むように意図されている。好ましい実施形態では、接続性情報は予め決められたグループの接続性タイプのうちの１つを示す接続タイプの各対に関するインジケータを含み、そのグループは対応する接続素子の対の間の接続を提供する有効接続、対応する接続素子の対の間の接続を妨げる無効接続、および中立の接続で構成される。
【００６２】
中立の接続という用語は、互いから予め決められた近接内に置かれると対応する２つの構造要素を接続するように協同しないが、しかしそのような配置をどちらも妨げない接続タイプの対を含む。
それゆえに、可能な相互接続の効率的な符号化が提供される。
【００６３】
本発明のなおも別の好ましい実施形態では、予め決められた近接で互いに配置された第１の構造要素の第１の接続素子と第２の構造要素の第２の接続素子を判定する工程はさらに、予め決められた接続素子のサブセットから第１と第２の接続素子を判定する工程を含む。それゆえに、接続素子の当該の対を判定するために接続素子のサブセットだけが検索されることを必要とし、それにより、本方法の効率を上げる。
【００６４】
さらなる好ましい実施形態では、それぞれのデータ構造の各々はさらに、対応する構造要素の境界体積も表わす。本方法はさらに、第１と第２の構造要素の境界体積の交差部を検出する工程を含み、予め決められた接続素子のサブセットから第１と第２の接続素子を判定する工程は判定された交差部に含まれる接続素子から第１と第２の接続素子を判定する工程を含む。それゆえに、当該接続素子のサブセットは潜在的に接続を提供することが可能な接続素子として判定されるが、なぜならばそれらは境界ボックスの交差部に含まれるからである。
【００６５】
新たなタイプの構造要素および新たなタイプの接続素子でさえも組み入れるように容易に拡張されることが可能なデータ構造とアルゴリズムを提供することが本発明のさらなる利点である。例えば、異なるタイプの既存の玩具構造要素の２つのセットの接続性特性は、異なる玩具構造セットの構造要素が互いに相互接続され得るように組み合わされることが可能である。
【００６６】
たとえ多数の構造要素を含むモデルを作り出すときでさえ、大きな記憶容量を必要としないデータ構造を提供することが本発明のさらなる利点である。
【００６７】
２つ以上の構造要素が接続されるかどうかを検出する効率的な方法を提供し、それにより、構造要素が相互接続されるかどうかを判定するためにコンピュータが必要とする処理時間を削減することが本発明のさらなる利点である。これは、ユーザが構造要素を２つ互いに相対して位置決めすることが可能な対話式コンピュータ・プログラムで特に重要な特徴であり、なぜならばこの状況ではモデルの構造要素の配置もしくは除去から接続性特性の判定までの短い応答時間が必要とされるからである。
【００６８】
本発明は、上述および下記の方法、システム、およびさらなる製品手段を含めた多様な方式で実施されることが可能であり、最初に述べた方法に関連して述べられた利点および長所のうちの１つまたは複数を各々が生じ、最初に述べた方法に関連して述べられ、かつ従属請求項に開示された好ましい実施形態に対応する１つまたは複数の好ましい実施形態を各々が有する。
【００６９】
本発明はさらに、
・構造要素を他の構造要素と接続するためのいくつかの接続素子を各々が有する複数の相互接続された構造要素から構築された幾何学的対象物のコンピュータ読み取り可能なモデルを作り出すための手段と、
・複数の構造要素のうちの第１の１つおよび第２の１つを、対応する構造要素の接続素子であって各々がそれに付随して複数の予め決められた接続タイプのうちの１つを有する接続素子を各々が表わす対応する第１と第２のデータ構造として符号化するための手段と、
・予め決められた近接で互いに配置された第１の構造要素の第１の接続素子と第２の構造要素の第２の接続素子を検出するための手段と、
・第１と第２の接続素子が第１と第２の構造要素の間の接続を提供するかどうかを示す第１と第２の接続素子の対応する接続タイプの接続性情報を取り出すための手段とを含むデータ処理システムに関する。
【００７０】
上述および下記で述べられる方法の特徴がソフトウェア中に導入され、コンピュータで実行可能な命令の実行によってデータ処理システムまたは他の処理手段の中で実行されることが可能であることに留意されたい。これらの命令は、記憶媒体から、またはネットワークを介して他のコンピュータからＲＡＭのようなメモリにロードされるプログラムコード手段であることが可能である。場合によっては、記述した特徴はソフトウェアの代わりに配線接続された回路またはソフトウェアとそれの組み合わせで導入されることも可能である。
【００７１】
本発明はさらに、上述および下記で述べられる方法を実行するように構成されたデータ処理システムに関する。
【００７２】
本発明はさらに、コンピュータ上でそのプログラムが走ると上述および下記で述べられる方法の工程すべてを実行するためのプログラムコード手段を含むコンピュータ・プログラムに関する。
【００７３】
本発明はさらに、コンピュータ上でそのプログラムが走ると上述および下記で述べられる方法を実行するためのコンピュータ読み取り可能な媒体上に保存されたプログラムコード手段を含むコンピュータ・プログラム製品に関する。
本発明は、好ましい実施形態と関連させ、かつ図面を参照しながら下記でさらに十分に説明されるであろう。
【発明を実施するための最良の形態】
【００７４】
図１ａ〜ｅは本発明の一実施形態による構造要素の表現を示す透視図である。
図１ａは構造要素１０１の表現を示している。構造要素１０１は、他のビルディング・ブロックの対応する穴に接続することが可能な２つのノブ１０２を１０３で指定される面の上に有する物理的ビルディング・ブロックのデジタル表現である。このビルディング・ブロックはさらに、面１０５からビルディング・ブロックの反対側の面へと貫通する穴１０４を有する。この穴は他のビルディング・ブロックの対応するコネクタを受け入れるように構成される。
【００７５】
ビルディング・ブロック１０１のデジタル表現は図１ａ中で太線で表わされた境界体積１０６を有する。境界体積１０６はノブ１０２を有するビルディング・ブロック１０１の境界体積である。ビルディング・ブロックのこのデジタル表現はさらに、内部の右手座標系１０７に関して述べられる。座標系、特にその原点の位置と軸の方向の選択がどのような適切な慣例に従って選択されることも可能であることは理解される。それゆえに、対応するデータ構造の中でビルディング・ブロックの位置と配向は、外部の座標系、例えば他のビルディング・ブロックの座標系もしくは大域的な「ワールド」座標系に関する座標系１０７の原点座標と軸の方向によって表わされることが可能である。
境界体積は座標系１０７に相対して、例えば座標系１０７に関する２つの角１１０の座標によってデータ構造内に表わされることが可能である。
【００７６】
図１ｂは、ビルディング・ブロックを含むがノブ１０２を含まない境界体積１０８を備えたビルディング・ブロック１０１の表現を示している。一実施形態では、異なるビルディング・ブロック間の衝突検出は両方のタイプの境界体積、すなわち図１ａに示された境界体積１０６と図１ｂの境界体積１０８に頼っている。
【００７７】
本発明によると、ビルディング・ブロックがそれに沿って他のビルディング・ブロックへと接続されることが可能な各々の平面は複数の正方形へと分割され、各々の正方形の中心に接続点を備える、すなわち正方形のエッジが隣り合う接続点間の半分の距離に対応する。
【００７８】
図１ｃはビルディング・ブロック１０１を示しており、ビルディング・ブロックの１つの面上の接続素子の表現を例示している。この表現は２つのノブ１０２を有するビルデイング・ブロックの面１０３の平面に正方形の格子１０９を表わしている。この正方形格子はいくつかの正方形を含み、正方形１３０と格子点１１１によって例示されるように各々が格子点を中心として有する。各々の格子点は矢印、例えば格子点１１１の矢印１１２で示されるように付随の方向を有する。格子１０９の格子点の方向は外方向、すなわち座標系１０７のｙ軸の方向を指している。それゆえにデータ構造内で、格子１０９の表現は座標系１０７に関して予め決められた格子点、例えば格子点１１３の座標、座標系に関する格子点の方向、すなわち矢印１１４の方向、格子のサイズ、すなわちｘ方向とｚ方向それぞれでの正方形の数、および格子点の各々に関連する属性を有することが可能である。そのような表現の範例は下記でさらに詳細に述べられるであろう。
【００７９】
図１ｄはビルディング・ブロック１０１の面１０３（図１ｄに図示せず）の反対側の面１１６の接続格子１２０を例示している。ビルディング・ブロックのこの面はエッジ１１８で規定される穴１１７およびいわゆる二次ピンと呼ばれる小さい中心ノブ１１９を有する。物理的ビルディング・ブロックのこれらの穴はノブ１０２のような他のビルディング・ブロックのノブを受け入れることが可能となるように配置され、それにより、２つのビルディング・ブロックを協同して接続する。本発明によると、矢印１２１で表わされるようにこれらの穴は格子１２０の対応する格子点によって表わされる。
この実施形態によると座標系の原点が格子点１２２に対応することが気付かれる。
【００８０】
図１ｅは穴１０４を有するビルディング・ブロック１０１の面１０５の接続格子１２３を例示している。相応して、格子点１２４は穴１０４の接続性特性を表わす。
【００８１】
ディスプレイ、例えばコンピュータ画面上にビルディング・ブロックを図解で表現するとき、境界体積、座標系、および格子は示される必要がない。図解表現はビルディング・ブロック自体の表現を含むだけである。
【００８２】
図２ａ〜ｃは構造要素およびそれらの接続素子の範例を例示している。
図２ａは２つのビルディング・ブロック２０１と２０２を示している。ビルディング・ブロック２０１はその上面に４つのノブ２０３、および底面（図示せず）に４つの対応する穴を有する積み木である。積み木２０２は互いに直交する平面を有する表面を備えたビルディング・ブロックの範例である。特に、ビルディング・ブロック２０２は傾斜面２０４を有する。図２ａに例示されるように、それらの今の位置ではビルディング・ブロック２０１と２０２は接続されない。
【００８３】
図２ｂは非長方形の上面と底面を有するビルディング・ブロック２１０を示している。底面は１つまたは複数の他のビルディング・ブロックの対応するノブを受け入れるための穴２１１、２１２、および２１３を有する。これらの穴はエッジ２１４、二次ピン２１５、ならびに角２１６と２１７によって規定される。それゆえに、上記の要素すべての特性がビルディング・ブロックの面の接続性特性を決定する。
【００８４】
図２ｃはビルディング・ブロック２２１に接続され、それによって組み合わせビルディング・ブロックを形成するビルディング・ブロック２２０を例示している。ビルディング・ブロック２２０はその上面に、他のビルディング・ブロックの対応する穴に係合するノブ２２２を有する。しかしながら、図２ｃで例示されるように、同様に他の接続タイプも達成されることが可能である。ノブの間の隙間２２３はブロック２２１の側面２２４のような他のコネクタのためのレセプタとして機能する。物理的ビルディング・ブロックに関して、この特性は隙間の寸法とビルディング・ブロック２２１の寸法、すなわち側部の幅２２５によって決定される。本発明によるデジタル表現では、これらの特性は下記でさらに詳細に例示されるであろうが、接続点の対応する属性によって表わされる。
【００８５】
図２ｄは、いくつかの積み木を含む他のビルディング・ブロックに対するビルディング・ブロックの無効接続を例示している。ビルディング・ブロック２３１は積み木２３２、２３３、２３４、２３５、２３６、および２３７を有する。各々のビルディング・ブロックが上述したようなノブ・コネクタと対ノブ・レセプタを有する。ビルディング・ブロック２３２、２３３、および２３６は上側ならびに側面にノブ・コネクタを有する。特に、ビルディング・ブロック２３２は側面にノブ２３８を有し、一方ビルディング・ブロック２３３は側面にノブ２３９を有し、ビルディング・ブロック２３６はその側面にノブ２４０を有する。
【００８６】
図２ｄの範例では、ビルディング・ブロックの寸法のせいでそれらのノブおよび、したがってそれらの対応する接続点は規則的な格子を形成しない。その結果、もしもビルディング・ブロックが×印２４２、２４３、および２４４で示されるようなその接続点を備えて点線２４１で示される位置に置かれるように試みられると、有効な接続は不可能である。本発明による方法がどのようにしてこのタイプの状況を検出するかが下記で述べられるであろう。
【００８７】
図３はビルディング・ブロックとそれに対応する接続性格子の透視図を示している。ビルディング・ブロック３０１は８個のノブ３０３ａ〜ｈを備えた上面３０２、対応する穴（図示せず）を備えた底面、および側面３０４を有する。図３では、上面と底面の接続性格子３０５と３０６がそれぞれ示されている。接続点は円３０７ａ〜ｋで例示されるような円によって具体的に示される。それゆえに接続点３０７ａ〜ｈはノブ３０３ａ〜ｈにそれぞれ対応する。側面３０４はどのような接続素子も有さないので、それらについて接続講師が規定される必要はない。別の代替選択肢となる実施形態では、空洞のレセプタだけを有する接続格子が側面に関して規定されることが可能である。
【００８８】
図３から見受けられるように、規則的格子内に配置された接続点によるビルディング・ブロックの接続素子の表現は、物理的ビルディング・ブロック上の接続素子の物理的配置に一定の拘束条件を課す。
格子３０５はビルディング・ブロックの上面の平面内に配置され、そこからノブ３０３が延びる。
【００８９】
図３の範例では、格子点が正方形格子内に置かれ、各々の正方形は任意の長さ単位（ＬＵ）の５×５単位の寸法を有する。それゆえに、この幾何学構造では、接続素子もやはり対応する正方形格子上に配置され、ビルディング・ブロックの平面内の接続素子間の距離は１０ＬＵの倍数である。図３の範例では、ビルディング・ブロックの上側表面と下側表面は長方形であり、２０ＬＵ×４０ＬＵの寸法を有し、隣り合う接続素子は１０ＬＵで間隔を置かれる。
【００９０】
他方で、垂直方向では、接続素子は１２ＬＵで間隔を置かれる。それゆえに、異なる寸法で格子寸法が変えられることが可能であり、それにより、上記の図２ｄに示されるような状況を生じさせることが可能である。
接続点の場所はビルディング・ブロックの内部座標系３０８に関して規定される。
【００９１】
図４は図３のビルディング・ブロックの上面図を示している。接続性格子３０５が格子点を含めて示されている。図３の範例中の格子点の方向は図面平面から外を指している。
【００９２】
一実施形態では、接続点の格子を表わすデータ構造は各々の接続点について、座標系３０８に関する接続点の座標、接続素子の方向、および接続性のタイプを含む。
【００９３】
新たなビルディング・ブロックを設計するとき、ビルディング・ブロックのデジタル表現が作り出されることが必要である。図４の範例中の積み木は上部表面上の４５個の接続点および底部表面上の４５個の接続点を有する。接続点の各々について上記の値を特定することは時間を浪費し、誤りを生じがちな作業である。
【００９４】
しかしながら、多くのタイプのビルディング・ブロックに関して接続点は規則的な構造で配置され、それにより、自動化されたデータ作成が可能になり、かつ好都合である。図４の範例では、接続点の座標は反復的に判定されることが可能であり、接続素子の方向は格子の接続点すべてについて同じである。
【００９５】
それゆえに、好ましい実施形態では接続点の格子を表わすデータ構造は、
・座標系３０８に関する格子点４０１の座標。それゆえに図４の範例では格子点４０１のＬＵでの座標はＰ０＝（−５，１２，−１５）であり、
・接続素子の方向、すなわち図４の範例では（０，１，０）、すなわち座標系３０８のｙ軸の方向、
・ｘおよびｚ方向での格子点の数、すなわち図４の範例ではそれぞれｎｘ＝９、ｎｚ＝５。
・各々が対応する接続点の接続特性を含む５×９データ構造のアレイを含む。そのようなアレイの範例は下記で述べられるであろう。
【００９６】
図４の範例では、各接続点の座標はｉ＝０，．．．，４、ｊ＝０，．．．，８に関して（ＬＵで）Ｐ０＋（５ｉ，０，５ｊ）と表わされることが可能である。
その後、接続点の特性はｉとｊで索引を付けられる二次元のアレイＣとして表わされることが可能であり、ここでＣ［０，０］は接続点４０１に対応し、Ｃ［ｉ，ｊ］は座標Ｐ０＋（５ｉ，０，５ｊ）を備えた接続点に対応する。
【００９７】
別の実施形態では、接続性格子の平面内で二次元座標系が定義されることが可能である。図４では、これは座標系４０２で具体的に示される。その後、二次元座標系はその原点４０１の座標およびビルディング・ブロックの内部座標系３０８に関する回転マトリックスによって表わされることが可能である。
【００９８】
図５ａ〜ｂは、本発明の実施形態による、接続点を表わすデータ構造の範例を具体的に示している。
【００９９】
図５ａは図４のビルディング・ブロックの格子の接続点を表わすデータ構造を具体的に示している。このデータ構造は上述したような二次元アレイＣ［ｉ，ｊ］に対応する。各々のアレイ素子が接続タイプに対応する。例えば、ノブ（例えば図４のノブ３０３）はＣ［ｉ，ｊ］＝Ｋと表わされ、２つのノブの間の隙間（例えば図４の隙間４０４）は「ダブルエッジ・ギャップ」と称され、Ｃ［ｉ，ｊ］＝２ＥＧと表わされ、４つのノブの中心の隙間（例えば図４の隙間４０５）は「チューブ・ギャップ」と称され、Ｃ［ｉ，ｊ］＝ＴＧと表わされる。ノブは他のビルディング・ブロックのレセプタ、例えば図２ｂに例示された穴２１２によって受け入れられることが可能なコネクタである。エッジ・ギャップは、例えば図２ｃに例示されるエッジかまたは図２ｂに例示されるエッジ２１１を受け入れることが可能なレセプタである。チューブ・ギャップは他のコネクタ、例えば適切なサイズのノブもしくはチューブを受け入れることが可能なレセプタである。
【０１００】
ビルディング・ブロックの境界では他の接続タイプが生じる。角（例えば図４の角４０１）は、それらが４つの隣接から１つだけを有するチューブ・ギャップに対応するのでＣ［ｉ，ｊ］＝１／４ＴＧと表わされる。同様に、Ｃ［ｉ，ｊ］＝１／２ＴＧは４つのノブから２つをその周りに有するチューブ・ギャップ、例えば図４の接続点４０６を表わす。最後に、Ｃ［ｉ，ｊ］＝ＥＧは１つだけの隣接ノブを有するエッジ・ギャップ、例えば図４の接続点４０７に対応する。
【０１０１】
図４に描かれたそれのようであるが、しかし異なる数のノブを備えたビルディング・ブロックが図５ａに示されたそれに類似した接続性のアレイに対応することは理解される。それゆえに、このタイプのビルディング・ブロックを表わすデータ構造はビルディング・ブロックの寸法を特定することによって自動的に作り出されることが可能である。
【０１０２】
概して、規則的な幾何学構造を有する構造要素については、接続性アレイの異なるタイプの数が例えば図３のビルディング・ブロックのように規則的なビルディング・ブロックの上部、側部、および底部の表面に関するアレイ・タイプで規定され得ることは理解される。その後これらのアレイ・タイプの例が類似した構造要素の様々な異なるタイプとサイズについて自動的に作り出されることが可能である。それゆえに、多様なビルディング・ブロックを表わすデータ構造が効率的な方式で作り出され得ることが利点である。
【０１０３】
図５ｂは図２ｂに示されたビルディング・ブロックの底面に対応する接続性のアレイを示している。ここで、Ｃ［ｉ，ｊ］＝ＥＣはエッジの角、例えば図２ｂの２１７に対応し、Ｃ［０，０］＝ＥＣに対応する。さらに、Ｃ［ｉ，ｊ］＝Ｅは図２ｂのエッジ２１４のような「エッジ」に対応する。Ｃ［ｉ，ｊ］＝３／４ＥＣは図２ｂの角２１６によって例示されるような角に対応する。Ｃ［ｉ，ｊ］＝ＡＫは「対ノブ」、すなわちノブを受け入れるための穴２１２に対応し、その一方でＣ［ｉ，ｊ］＝ＳＰは「二次ピン」２１５に対応する。
【０１０４】
たとえ図５ａ〜ｂの接続タイプが接続素子の実際の物理的機能のニーモニック表示であるとしても、接続タイプが他のどのような適切な手段、例えば列挙型接続タイプ、ビット・コーディングなどによっても符号化され得ることは理解される。
【０１０５】
概して、接続タイプは接続の種類とパラメータを含むことが可能である。例えば、接続の種類はα＝１／４、１／２、３／４、１を備えたチューブギャップαＴＧである。
【０１０６】
異なる接続タイプの接続特性は対応する接続表に規定される。接続表は、接続タイプの各々の対について接続性特性を示す。接続表はルックアップテーブルとして適切なデータ構造内に保存されることが好ましい。そのような接続表の実施形態が表１に例示されている。
【表１】
【０１０７】
それゆえに、表１の各々の欄は対応する２つの接続タイプの接続性を示している。
表１の短縮表示された接続タイプはつぎの通りである。
Ｋ：ノブ、例えば図１ａ〜ｅのノブ１０２、すなわち円形の素子。
ＳＰ：二次ピン、例えば図２ｂの２１５、すなわち小さいノブ。
Ｅ：エッジ、例えば図２ｂのエッジ２１４、すなわち要素の外側エッジ。
αＥＣ：パラメータαを備えたエッジの角である。３／４ＥＣは図２ｂで角２１６によって例示されるような角に対応する。
ＶＣ：空洞コネクタ、すなわち殆どの他の要素を拒絶せず、また、他の素子、例えば滑らかな表面と接続することもないビルディング・ブロックの部分。空洞コネクタはノブを拒絶するが、しかし他のどのようなレセプタまたはコネクタとも相互作用しない。
αＡＫ：パラメータαを備えた対ノブ、例えば図２ｂの対ノブ２１５、すなわちノブが嵌合する不規則な形状の穴。
αＴＧ：パラメータαを備えたチューブ・ギャップ、例えば、図４はα＝１を備えたチューブ・ギャップ４０５、すなわち４つの隣り合うノブの間の領域であって、これにチューブが嵌合することが可能である。
αＥＧ：パラメータαを備えたチューブ・ギャップ、例えばα＝２を備えたダブルエッジ・ギャップおよびα＝１を備えたエッジ・ギャップ４０７、すなわち２つのノブ間またはノブとエッジ間の隙間。
ＶＲ：空洞レセプタ、すなわちどのような他の素子も拒絶せず、また接続もしないビルディング・ブロックの部分。
Ｔｕ：チューブ、ノブのためのレセプタであることが可能であり、４つの隣り合うノブの間、すなわちチューブ・ギャップに詰め込まれることが可能なコネクタであることが可能な環状のチューブ。
【０１０８】
表１で、上記の接続タイプの接続性は次のように示される。
・Ｔ：真、すなわち接続が有効であり、対応する接続素子が係合することで２つのビルディング・ブロックを接続する。
・Ｆ：偽、すなわち接続はこの位置では許容されない。
・Ｖ：空洞または中立、すなわち接続を妨げるものが存在しないが、しかし実際にどちらか接続するものもない。
【０１０９】
例えば、表１によると、ダブルエッジ・ギャップ（α＝２を備えたαＥＧ）はエッジ（Ｅ）と空洞接続を作り出し、その一方でエッジ・ギャップ、すなわちα＝１を備えたαＥＧはエッジ（Ｅ）と実際に接続する、すなわちこのケースでは接続性が真（Ｔ）である。
表１の接続表が対角線に沿って対称であることが気付かれる。
【０１１０】
それぞれの既にある接続タイプと共に新たな接続タイプの該当する接続性を対応する横列と縦列に追加することによって上記の表が新たな接続タイプを含むように容易に拡張され得ることがさらに気付かれる。
【０１１１】
図６はエッジからエッジへの延長になっている２つの構造要素の上面図を示している。図６の範例では、２つのビルディング・ブロック６０１と６０２がエッジからエッジへの延長で配置される、すなわちそれらの上部表面が同じ平面内に置かれ、それらのそれぞれの接続点が破線６０３で示されるように同一空間を占める。図６の範例では、ビルディング・ブロック６０１と６０２各々は図３と４に示されたタイプであると仮定されている。
【０１１２】
２つのビルディング・ブロックをエッジからエッジへの延長で配置することによって、領域６０３で重複する接続点の有効接続タイプが変えられる。例えば、接続点６０５はビルディング・ブロック６０１のタイプ１／４ＴＧの接続点およびビルディング・ブロック６０２のタイプ１／２ＴＧの接続点に対応する。しかしながら、図６のエッジからエッジへの延長で配置されると、組み合わされた接続点６０５はタイプ３／４ＴＧである。同様に、接続点６０６はビルディング・ブロック６０１と６０２各々のタイプＥＧであるが、組み合わされたビルディング・ブロックではそれはタイプ２ＥＧである。最後に、接続点６０７はビルディング・ブロック６０１と６０２各々のタイプ１／２ＴＧであるが、組み合わされたビルディング・ブロックではそれはタイプＴＧである。
【０１１３】
それゆえに、概して接続素子の接続性特性は他の構造要素と関係した対応する構造要素の配置に応じて変化する可能性がある。
【０１１４】
本発明によると、この状況は組み合わされた、または結果的に生じる重複接続点の接続タイプを記述する組み合わせ表を規定することによってモデル化されることが可能である。表２はそのような組み合わせ表の範例であり、上記で導入された接続タイプの組み合わせを示している。この組み合わせ表はルックアップテーブルとして適切なデータ構造内に保存されることが好ましい。
【表２】
【０１１５】
表２では、各々の欄は組み合わされる接続タイプを含む。もしも２つの接続タイプの組み合わせがどのような他の接続タイプに接続する接続タイプも生じない場合、表の記入事項はＦである。
【０１１６】
例えば、エッジ・ギャップ（βＥＧ）が空洞コネクタ（ＶＣ）、例えば空の表面の隣に配置されると、結果的に生じる接続要素は広い隙間であると考えられる。表２では、これは（β＋１）ＥＧによって近似される。
【０１１７】
上記の組み合わせ表が、２つ以上の接続素子が組み合わされる状況、例えば３つもしくは４つのビルディング・ブロックの角、で結果的に生じる接続タイプを判定するために使用されることもやはり可能であることがさらに理解される。この状況では、例えば３つの接続素子について結果的に生じた接続タイプは、第１に、最初に組み合わされた接続素子の２つについて結果的に生じた接続タイプを判定し、それに続いて、結果的に生じた第１の接続タイプと第３の接続素子の接続タイプの組み合わせの結果として生じた第２の接続タイプを判定することによって判定される。
【０１１８】
それぞれの既にある接続タイプと新たな接続タイプの組み合わせから結果的に得られる該当する結果の接続タイプを該当する横列と縦列に追加することによって上記の表が新たな接続タイプを含むように容易に拡張され得ることがさらに気付かれる。
【０１１９】
それゆえに、上記で、ビルディング・ブロックの接続性特性の効率的で拡張可能な表現のためのデータ構造が、接続タイプをどのように組み合わせるかに関する法則の効率的で拡張可能な表現と同様に開示される。
【０１２０】
図７はビルディング・ブロックの２つの接続グループを有する幾何学的対象物の透視図を示している。この幾何学的対象物は５つの要素７０１、７０２、７０３、７０４、および７０５を含む。図７の範例では、幾何学的対象物はビルディング・ブロックの２つのグループを含み、ビルディング・ブロックの第１のグループはビルディング・ブロック７０１、７０２、および７０３を含み、その一方で第２のグループはビルディング・ブロック７０４と７０５を含む。この範例でのビルディング・ブロック７０１と７０４は、例えば上述の単一のノブと対ノブの接続、またはビルディング・ブロックの互いに相対した回転を妨げない他の何らかの方式、例えばヒンジ接続、共通の線上での２つ以上のノブと対ノブの接続などによって回転可能に接続される。それゆえに、図７の幾何学的対象物は、幾何学的対象物に与えられた位置と配向の制約に必ずしも束縛されないビルディング・ブロックの範例である。そのような接続の他の範例は、接続されたビルディング・ブロックの相対的平行移動を可能にするビルディング・ブロック間の接続を含む。それゆえに、ビルディング・ブロックのそのようなグループは、格子系７０６と７０７で示されるように別々の座標系で述べられることを必要とする可能性がある。
【０１２１】
図８は、幾何学的対象物のコンピュータ読み取り可能なモデルを作り出すコンピュータ導入処理法の一部として構造要素を配置する方法を示すフロー図である。
【０１２２】
最初の工程８０１で、予め決められた初期位置に構造要素が置かれる。この構造要素は上記で例示されたようなデータ構造によって表現され、構造要素の位置と配向は、適切な座標系、例えば三次元の右手「ワールド」座標系または基準座標系に関する構造要素の内部座標系の位置と配向を説明する適切な座標系によって記述される。
【０１２３】
それゆえに、所定の背景、例えば場面、幾何学的対象物などに関すると、この処理法は各々がその背景の中に置かれたビルディング・ブロックを表現するデータ構造のセットを作り出して維持する。その背景の中に新たな構造要素を配置することはデータ構造のそのセットの一部として対応するデータ構造の新たな事例を作り出すことに該当する。
【０１２４】
構造要素の配置は、例えば幾何学的対象物のデジタル・モデルを作成する対話式処理の間にユーザの命令によって生じさせられることが可能である。例えば、コンピュータが、ユーザが異なる構造要素、例えば異なるタイプ、形状、サイズ、色などの構造要素を選択し、選択された構造要素をコンピュータのディスプレイ上に表示される三次元グラフィック場面内で予め決められた位置と配向に配置することを可能にするユーザ・インターフェースを提供することが可能である。例えば、このユーザ・インターフェースは構造要素を置くためのドラッグ・アンド・ドロップ操作ならびに構造要素を操る、例えば回転させるための操作を提供することが可能である。
【０１２５】
一実施形態では、構造要素の配置は、例えばすべての距離が任意の長さ単位（ＬＵ）の倍数として測定され、基準格子の格子点が１ＬＵで間隔を置かれることが可能な系の、例えば予め決められた格子上の別々の位置へと限定されることが可能である。
【０１２６】
工程８０２では、コンピュータ導入による処理が、工程８０１で配置された構造要素がその場面に既に存在する何らかの他の構造要素、例えばユーザによって以前に配置された構造要素と交わる場所を検出する。この衝突検出はどのような適切な衝突検出法で実行されることも可能であり、構造要素の境界体積に基づいた衝突検出法が好ましい。そのようなアルゴリズムの範例は、例えばＤａｖｉｄ Ｈ．Ｅｂｅｒｌｙの「３Ｄ Ｇａｍｅ Ｅｎｇｉｎｅ Ｄｅｓｉｇｎ」、Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ、２００１年に開示されている。
【０１２７】
衝突検出は、構造要素が配置された位置が他の構造要素によって既に占められているという結果に結び付く可能性がある。この状況は予め決められた限度よりも大きい境界体積の交差部を検出することによって検出されることが可能である。もしも無効な交差部が検出されれば、この位置と配向での構造要素の配置は拒絶されることが可能である。
【０１２８】
もしも無効な交差部が検出されなければ、本処理法は工程８０３で新たに配置される構造要素が他の構造要素と有効に交差するかどうかを検査する。有効な交差部は、例えば予め決められた限度よりも小さいそれぞれの境界体積の交差部として検出されることが可能である。
【０１２９】
図１の実施形態では、構造要素の表現は接続素子を含めた境界体積（図１ａ）と構造要素本体を含むが接続素子を含まない境界体積（図１ｂ）の２つの境界体積を有する。衝突検出の工程はこれら２つの境界体積を使用して、もしも構造要素の接続素子を除いた境界体積が重なり合えば無効な衝突を検出することが可能である。もしも接続素子を含む境界体積が重なり合うが、しかし接続素子を除いた境界体積が重ならない場合、あるいはあらゆる境界体積のあらゆる表面が交差するが境界体積が重なり合わない場合、有効な重複が検出される。
さらに、それらの境界体積の軸が同じ基準座標系に対応するように境界体積が配向されているかどうかが検出される。
【０１３０】
もしも有効な衝突が検出されなければ、本処理法は何らかの適切な方策に従って進行することが可能である。いくつかの実施形態ではどのような以前の構造要素にも接続せずに新たな構造要素を空洞内に配置することが受容可能である可能性があり、いくつかの実施形態では、もしも既にその場面に存在する他の構造要素が無い場合にのみこれは受容可能である可能性がある。なおも別の実施形態ではこれが拒否される可能性がある。例えば、一実施形態では、ユーザによって置かれる構造要素を伴なわないどのような初期場面も初期設定の構造要素、例えば基礎平面の上に構造要素を設置するための接続素子を備えた支持平面を有することが可能である。
【０１３１】
工程８０３でもしも新たに設置される構造要素と１つまたは複数の他の構造要素の間に有効な衝突が検出されると、本処理法は工程８０４に続き、新たに設置される構造要素がそれに有効に交差する（複数の）構造要素に有効に接続されることが可能であるかどうかをチェックする。この接続性検出の部分工程の好ましい実施形態は下記でさらに詳しく述べられるであろう。この接続性検出は結果として、もしも構造要素がそれと交差する（複数の）構造要素に有効に接続するならば構造要素の設置の受容につながり、もしも交差する構造要素のうちのいずれか１つと有効に接続しなければ拒絶につながることが可能である。
【０１３２】
いったん構造要素の設置が受容もしくは拒絶されると、本処理法はユーザの行為によって、例えば拒絶された構造要素を別の代替選択肢の位置および／または配向に置き換えることによって、他の構造要素をその場面に設置するなどによって再び開始されることが可能である。
【０１３３】
図９は本発明の一実施形態に従って第１のデジタル構造要素を他の第２のデジタル構造要素に接続する部分工程８０４のフロー図を示している。例えば、第１の構造要素が新たに設置される積み木であり、第２の構造要素が以前に構築された積み木構造であることが可能であり、検出のアルゴリズムが新たに設置される積み木と第２の構造要素の間の交差部を検出し終えている。
【０１３４】
以下では、初期位置で構造要素はそれらの境界体積の主軸が右手直交ワールド座標系のｘ、ｙ、およびｚ軸に対応するように配向されると仮定される。
この実施形態では、接続素子自体は性質および形状で異なるけれども構造要素上の接続素子の設置についていくつかの予め決められた法則が課されることがさらに仮定される。
【０１３５】
接続素子の設置に関する仮定は、各々の構造要素について、同じ水平平面内のすべての接続素子の軸が、隣り合う区分間に一定の距離を備えた直交格子の区分に対応することである。
水平平面内および垂直平面内の接続素子の軸間距離は同じである必要がない。
【０１３６】
最初の工程９０２で、検出された交差部に属する第１の構造要素および第２の構造要素のすべての接続点。既に接続されているわけではないそれら接続点だけが考慮される必要があり、これらの接続点は該当接続点と称されるであろう。
【０１３７】
工程９０３で、第１の構造要素の第１の該当接続点が選択される。これは任意に選択された接続点、ユーザによって選択された接続点などであることが可能である。
【０１３８】
工程９０４で、第１の構造要素の選択された接続点について、本処理法は選択された接続点と同じ座標を有する第２の構造要素のいずれかの該当接続点が存在するかどうかをチェックする。構造要素が別々の体積基準格子内に配置され、すべての座標が任意の単位長さの倍数である一実施形態では、座標の正確な一致が必要とされる可能性がある。連続的または外見上連続的な基準座標系では、格子点が予め決められた限度内で一致することが必要とされる可能性がある。
もしもそのような一致する接続点が見つからない場合、本処理法は工程９１４に続く。
【０１３９】
工程９１４で、選択された接続点の予め決められた近接の中にいずれか他の接続点が存在するかどうかを検出する。図９の実施形態では、予め決められた近接は（ｘ，ｙ，ｚ）の選択された接続点の周りの立方体（ｘ±５ＬＵ，ｙ±５ＬＵ，ｚ±５ＬＵ）に相当するが、なぜならばこの実施形態では２つの隣り合う接続素子の間の距離が１０ＬＵだからである。もしも選択された接続点の予め決められた近接の中にいずれか他の接続点が存在するならば、２つの構造要素の間の接続は拒絶され（工程９１１）、アルゴリズムが終了する。それゆえに、この実施形態で接続点は規則的な格子上に配置されるので、構造要素の無効な設置は効率的に検出されることが可能である。もしも第１の構造要素の該当接続点のうちの１つにに関して第２の構造要素の該当接続点との不一致が見つけられれば、第１の構造要素の残りの接続点はチェックされる必要が無く、それにより、検出工程のスピードを上げる。上記の検査は、ノブ２３９に対応する接続点が規則的な格子に関して置き違えられているので図２ｄに示されたような接続が拒絶されることを確実化する。図２ｄの範例では、高さのわずかの違いのせいで接続点２４３が境界体積の交差部に属することがないので接続点２４３が不一致を生じさせることはない、すなわち積み木２４１と２３６の間の接触はないことが気付かれる。
【０１４０】
もしも工程９１４で不一致を生じる該当接続点が見つけられなければ、本処理法は工程９０９に続く。
もしも工程９０４で一致する接続点が見つけられた場合、本処理法は工程９０５に続き、選択された接続点の予め決められた近接、この実施形態では上述したように（ｘ，ｙ，ｚ）の選択された接続点の周りの立方体（ｘ±５ＬＵ，ｙ±５ＬＵ，ｚ±５ＬＵ）の中にいずれか他の接続点が存在するかどうかが検出される。もしも予め決められた近接の中で他の接続点が見つけられると、その位置が拒絶される（工程９１１）。そうでない場合、本処理法は工程９０６に続く。
【０１４１】
別の代替選択肢となる実施形態では上記の限定が望ましくない可能性がある。さらに、なおも別の実施形態では上記の限定は特定の接続タイプ、例えば上記の範例では「空洞」と異なるすべての接続タイプに限られることが可能である。
【０１４２】
工程９０６で、本処理法は選択された接続点および検出された一致接続点が反対の方向を有するかどうか、すなわちそれらの随伴する方向が共通の線に沿っているが反対の配向であるかどうかを検出する。それゆえに、係合するために適した相対的配向で配置された接続素子だけが受容される。
別の代替選択肢となる実施形態で、この限定が、例えば接続素子が或る範囲の配向を受け容れる実施形態で或る範囲の配向を受容することによって緩和されることに留意されたい。
【０１４３】
もしも接続点の相対的配向が受容されれば、本処理法は工程９０７に続き、そうでない場合、その位置が拒絶される（工程９１１）。
【０１４４】
工程９０７で、選択された接続点およびそれに対応する検出された一致接続点の接続タイプが、保存された接続表９１３、例えば上記の表１による接続表から接続タイプの対応する対の接続性法則を取り出すことによって比較される。この実施形態では、表１に関連して述べられたように接続は真、偽、または空洞であることが可能である。
【０１４５】
それに続く工程９０８で、接続性の結果が「偽」、すなわち対応する接続タイプの間で有効な接続が不可能であるかどうかが検査される。もしも接続性の結果が「偽」であれば、第１の構造要素の位置が拒絶され（工程９１１）、そうでない場合、接続性結果は保存され、本処理法は工程９０９へと進む。
【０１４６】
工程９０９で、第１の構造要素のすべての該当接続点が処理されたかどうかが検査される。そうでなければ、まだ未処理の該当接続点が選択され（工程９１２）、上記の工程９０４、９０５、９０６、９０７、および９０８を現在選択された接続点で実行することによって処理が為される。
【０１４７】
もしも第１の構造要素のすべての該当接続点が処理されており、かつその位置が拒絶されなかった場合、その位置が受容され、本処理法は工程９１０に続く。工程９１０では、保存された接続性結果に基づいてどのようにして構造素子を接続するかが判定され、したがってそれらのそれぞれのデータ構造が更新される。これは図１０に関連してさらに詳しく述べられるであろう。いったんデータ構造が更新されると、この部分工程が終了し、図８の全体的処理法へと戻る。
【０１４８】
図１０は接続された構造要素を表現するデータ構造を更新する部分工程９１０の実施形態のフロー図を示している。この更新は、第１および第２の構造要素の境界体積の交差部のすべての該当接続点について判定された接続性結果に基づいている。
【０１４９】
最初に工程１００１で、すべての接続性結果が「空洞」であるかどうかがチェックされる。もしもそうであれば、すなわちもしもこの構造要素の位置を妨げるものは無いがこの構造要素を接続するように実際に係合する接続素子も無い場合、新たな構造要素はその現在の位置で許容される。
【０１５０】
用途に応じて、第１および第２の構造要素のデータ構造は更新されることが可能である。構造要素は実際に接続されないので、第１の構造要素が第２の構造要素と組み合わされて組み合わせの境界体積などを有する組み合わされた構造要素になるはずがないことが好ましい。
【０１５１】
一実施形態では、追加的なアルゴリズムが、例えば境界体積に基づいて、この位置に置かれた物理的ビルディング・ブロックが落下するかどうか、傾斜するかどうかなどを決定し、したがってその位置を許容するかまたは拒絶する。
【０１５２】
そうでない場合、例えばもしも１つまたは複数の接続性結果が真であれば、本処理法は工程１００２に進み、そこで本処理法は構造要素がどのようにして接続されるか、すなわちそれらが固く接続されるか、または接続が相対的な回転、平行移動などを許容するかを判定する。
【０１５３】
図１ａ〜ｅの実施形態では、もしも正確に１つの接続結果が真であって他のすべてが空洞であれば、接続のタイプに応じて回転および／または平行移動が可能であり得る。さらに、もしも複数の接続結果が真であり、対応する接続点がすべて共通の線上にあれば、回転および／または平行移動が可能であり得る。
【０１５４】
もしも非固定型の接続が検出されると、本処理法は工程１００５に続き、第１と第２の構造要素は、それぞれの基準座標系、境界体積などをそれぞれが有するそれぞれのグループへと割り振られ、それにより、構造要素のグループの多様な相対的位置および／または配向をモデル化することが可能となる。そのような状況は図７に関連して例示された。
【０１５５】
それゆえに、構造要素の接続された構造は構造要素のいくつかのグループを含むデータ構造によって記述されることが可能である。或るグループは、すべての構造要素のすべての接続点が同じ直交格子の格子点となる方式ですべての構造要素が固く接続される構造である。構造要素の各々のグループは１つまたは複数の構造要素を含み、そこではこのグループが共通の直交座標系（格子）、境界体積、およびそのグループの構造要素の接続性格子を決定する。
【０１５６】
もしも工程１００２で固定式の接続が検出された場合、本処理法は工程１００３に続く。上記で図６に関連して述べられたように、第１および第２の構造要素の１つまたは複数の接続点は接続に起因してそれらの接続性を変える可能性がある。それゆえに、工程１００３で第１および第２の構造要素のそれらの接続点が検出され、それらは同じ位置および同じ方向を有する。それらの組み合わされた接続点について、上記で表２に関連して述べられたように、結果的に生じた接続タイプは保存された組み合わせ表１００６で調べられる。
【０１５７】
最後に工程１００４で、第２の構造要素のデータ構造が第１の構造要素から得られる情報で更新され、すなわち第２の構造要素の境界体積が第１と第２の構造要素の境界体積の合併であるように更新され、接続性格子は第１の構造要素の接続点もやはり含むように更新される。
【０１５８】
図８、９、および１０の処理工程を繰り返すことによって、複数の構造要素が、幾何学的対象物のデジタル・モデルを形成するように組み合わされることが可能である。それゆえに、上記で、幾何学的対象物のデジタル・モデルを作り出すための方法が開示された。
【０１５９】
本発明の範囲内で当業者が上記の方法の変形例を実行することが可能であることは理解される。例えば、上記の工程のうちのいくつかの順序が変えられることが可能であり、工程が組み合わされることが可能である等々である。
【０１６０】
さらに、不正確な設置に起因する、例えば同じ位置で接続点が見当たらないという理由、または接続点が正確に反対の方向を有さないという理由による新たな構造要素の位置の拒絶は、単純な拒絶ではなくさらなる処理へとつながることが可能である。一実施形態では、受容可能な位置が達成されることが可能であるかどうかを決定するために仮説に基づいた隣接位置またはわずかな移動が分析されることが可能である。これが結果として、予め決められた限度内で、構造要素が受容可能な位置を提供する最も近い位置にはまり込むことにつながることが可能である。
【０１６１】
さらに、多少の自由度、したがって複雑さをモデル化システムに与えるために、追加的な限定が課されることが可能であり、あるいは他の限定が緩和されることが可能である。
【０１６２】
構造要素が構造から外されると、例えば対応するユーザの命令に応答して、そのデータ構造は組み合わされたデータ構造から外される。一実施形態では、これは残りの構造要素の組み合わされたデータ構造を計算し直すことによって実施される可能性がある。
【０１６３】
図１１は、本発明の実施形態に従って幾何学的対象物のコンピュータ読み取り可能なモデルを作り出すためのデータ処理システムを示している。
１１０１で指定されるコンピュータ・システムは、本発明に従って幾何学的構造の設計、記憶、操作、および共有を容易にするように構成される。コンピュータ・システム１１０１は独立型システム、またはクライアント／サーバ・システムのクライアントとして使用されることが可能である。このコンピュータは、部分的に揮発性および不揮発性のメモリ手段、例えばハードディスクおよびランダム・アクセス・メモリ（ＲＡＭ）として導入されるメモリ１１０２を有する。このメモリはモデル符号インタプリタ１１０７、モデル符号発生部１１０８、ＵＩイベント処理部１１０９、中央演算処理装置１１０３によって実行可能なモデル化アプリケーション１１１０を含む。さらに、このメモリはモデル・データ１１１１を含む。
【０１６４】
符号インタプリタ１１０７は本発明に従ってモデルを規定する符号、すなわちモデルの構造要素のデータ構造を表わす符合を読み取って解釈するように構成される。好ましい実施形態では、符号インタプリタは本発明に従ってモデルを読み取り、コンピュータ・ディスプレイ上に表わすためにそのようなモデルを知られているグラフィック書式へと変換するように構成される。対象物のモデルを表現するための上述のデータ構造に基づいて、この変換はグラフィック計算の分野でよく知られているグラフィックの原理を適用することで当業者によって実行されることが可能である。
【０１６５】
ＵＩイベント処理部１１０９はユーザ・インターフェースとのユーザの対話を符号発生部１１０８で識別可能な適切なユーザ命令へと変換するように構成される。可能性があり、かつ識別可能な命令のセットは、要素のライブラリから構造要素を得る命令、他の構造要素に接続されるべき構造要素を配置する命令、構造要素を切り離す命令、構造要素を廃棄する命令、例えば回転などを開始することによって構造要素、構造要素のグループを操る命令を含むことが可能である。各々の命令と共にそれぞれのパラメータ、例えば構造要素の座標、タイプなどの付随のセットが存在することが可能である。
【０１６６】
符号発生部１１０８は上述のように本発明に従って、かつユーザ命令に応答して実際のモデルを記述するデータ構造を変更するように構成される。同時発生または引き続いて生じる作業として、符号インタプリタは符号発生部の結果を表わすために実行されることが可能である。
【０１６７】
モデル化アプリケーション１１１０はメモリ、ファイル、ユーザ・インターフェースなどを制御するように構成される。
【０１６８】
ユーザ１１０５はユーザ・インターフェース１１０６によってコンピュータ・システム１１０１と対話することが可能である。
【０１６９】
モデル、幾何学的表現、または他のデータをロードするために、コンピュータ・システムは入出力（Ｉ／Ｏ）ユニット１１０４を有する。入出力ユニットは多様なタイプの記憶媒体および多様なタイプのコンピュータ・ネットワーク、例えばインターネットへのインターフェースとして使用されることが可能である。さらに、入出力（Ｉ／Ｏ）ユニット１１０４はモデルを他のユーザと、例えば対話式で交換するために使用されることが可能である。
【０１７０】
メモリ１１０２、中央演算処理装置（ＣＰＵ）１１０３、ユーザ・インターフェース（ＵＩ）１１０６、および入出力ユニット１１０４の間のデータ交換はデータ・バス１１１２によって達成される。
【０１７１】
図１２ａは本発明の第１の実施形態による、傾斜表面および対応する境界体積を備えたビルディング・ブロック、例えば図２ａのビルディング・ブロック２０２の側面図を示している。ビルディング・ブロック２０２は傾斜表面２０４、およびビルディング・ブロック最上部のノブ１２０１を有する。この範例によると、ビルディング・ブロック２０２の表現は境界体積の階層を有する。第１の境界体積１２０２は傾斜表面を含み、その一方で第２の境界体積１２０３は互いに直交する側部を備えたボックスである。この範例によると、境界体積１２０３が他のビルディング・ブロックの対応する境界体積と交差部を有する場合にのみ２つのビルディング・ブロックは接触していると検出される。境界体積１２０２は接続されると考えられるビルディング・ブロックの初期の効率的な検出のために使用されることが可能である。ビルディング・ブロック２０２の表現が、図１ａ〜ｂに関連して述べられたように接続素子を含む境界体積のような追加的な境界体積を含むことが可能であることは理解される。
【０１７２】
図１２ｂは本発明の第２の実施形態による、傾斜表面および対応する境界体積を備えたビルディング・ブロック２０２の側面図を示している。上記の範例のように、このビルディング・ブロック２０２の表現は境界体積の階層を有する。しかしながら、この範例によると、この表現は、傾斜表面を備えた境界体積ではなく階段関数に似た形状を有する境界体積１２０４を含み、それにより、傾斜表面の近似を与えている。
【０１７３】
上記の方法およびシステムは物理的モデルを設計するためのコンピュータ・アプリケーション、例えば物理的構造要素の対応するセットの接続性の挙動をシミュレートするコンピュータ・アプリケーションに関連して応用されることが可能である。例えば、物理的玩具構造セットが前記構造セットのデジタル・バージョンによって補完されることが可能であり、それにより、利用可能な構造要素の数を限定することなくユーザ、例えば児童が模型をデジタル設計することを可能にし、遊び体験の面白さを提供する。物理的構造セットの複雑な接続性特性でさえ現実的にモデル化することを可能にし、同時に効率的なモデル化方法を提供する方法とシステムを提供することが本発明の利点である。その結果、ユーザは構造要素の提案の位置が構造セットの接続法則に対応するかどうかをコンピュータが判定するのを待つことを必要とせずに対話式のデジタル構造化処理を体験する。
【０１７４】
本方法はさらに、設計されたモデルの特性を分析すること、構造化命令を作り出すことなどに応用されることが可能である。概して、本方法はコンピュータ・ゲーム産業、および予め決められた３Ｄ要素が複数の接続法則に従って一体に置かれなければならない他のコンピュータ・グラフィックスの領域すべてで応用されることが可能である。
【図面の簡単な説明】
【０１７５】
【図１ａ】本発明の一実施形態による構造要素の表現を示す透視図である。
【図１ｂ】本発明の一実施形態による構造要素の表現を示す透視図である。
【図１ｃ】本発明の一実施形態による構造要素の表現を示す透視図である。
【図１ｄ】本発明の一実施形態による構造要素の表現を示す透視図である。
【図１ｅ】本発明の一実施形態による構造要素の表現を示す透視図である。
【図２ａ】構造要素およびそれらの接続素子の範例を例示する図である。
【図２ｂ】構造要素およびそれらの接続素子の範例を例示する図である。
【図２ｃ】構造要素およびそれらの接続素子の範例を例示する図である。
【図２ｄ】構造要素およびそれらの接続素子の範例を例示する図である。
【図３】ビルディング・ブロックおよびそれに対応する２つの接続性格子を示す透視図である。
【図４】図３のビルディング・ブロックの上面図である。
【図５ａ】各々が構造要素の表面の接続点を表わすデータ構造を例示する図である。
【図５ｂ】各々が構造要素の表面の接続点を表わすデータ構造を例示する図である。
【図６】エッジからエッジへの延長状態にある２つの構造要素を示す上面図である。
【図７】構造要素の２つの接続されたグループを有する構造要素を示す透視図である。
【図８】幾何学的対象物のコンピュータ読み取り可能なモデルを作り出す方法の中で構造要素を配置する方法を示すフロー図である。
【図９】本発明の実施形態による、デジタル構造要素を他のデジタル構造要素へと接続する方法を示すフロー図である。
【図１０】接続された構造要素を表わすデータ構造を更新する部分的方法を示すフロー図である。
【図１１】本発明の実施形態による、幾何学的対象物のコンピュータ読み取り可能なモデルを作り出すためのデータ処理システムを示す図である。
【図１２ａ】傾斜表面を備えたビルディング・ブロック、および対応する境界体積の範例を示す側面図である。
【図１２ｂ】傾斜表面を備えたビルディング・ブロック、および対応する境界体積の範例を示す側面図である。
【特許請求の範囲】
【請求項１】
複数の相互接続可能な構造要素から構成された幾何学的対象物のコンピュータ読み取り可能なモデルを作り出す方法であって、各々の構造要素が、前記構造要素を他の構造要素と接続するためのいくつかの接続素子を有し、
前記複数の構造要素のうちの第１および第２の１つを、対応する前記構造要素の前記接続素子であって各々が複数の予め決められた接続タイプのうちの１つを付随して有する前記接続素子を各々が表現する、対応する第１および第２のデータ構造として符号化する工程と、
互いの予め決められた近接に位置する前記第１の構造要素の第１の接続素子と前記第２の構造要素の第２の接続素子を判定する工程と、
前記第１および第２の接続素子が前記第１と前記第２の構造要素の間の接続を供給するかどうかの指標である前記第１および第２の接続素子の対応する前記接続タイプの接続性情報を取り出す工程とを含む方法。
【請求項２】
前記接続タイプの接続性情報を含む接続表を供給する工程をさらに含み、かつ接続性情報を取り出す前記工程が前記接続表から前記接続性情報を取り出す工程を含むことを特徴とする、請求項１に記載の方法。
【請求項３】
さらに、
・接続タイプの対の予め決められたセットの各々に関する結果的に生じる接続タイプを含む組み合わせ表を供給する工程と、
・互いに予め決められた幾何学的関係で配置される第１および第２の接続素子を判定する工程と、
・前記組み合わせ表から前記第１および第２の接続素子の結果的に生じる接続タイプを取り出す工程と、
・取り出された結果の接続タイプを少なくとも結果の接続素子へと割り当てる工程とを含むことを特徴とする、請求項１または２に記載の方法。
【請求項４】
それぞれの前記データ構造の各々が前記対応する構造要素に相対していくつかの格子をさらに表現し、各々の格子がいくつかの格子点を有し、前記構造要素の前記接続素子の各々が前記格子点のうちの１つと関係し、かつ対応する接続タイプを有することを特徴とする、請求項１乃至３のいずれか１項に記載の方法。
【請求項５】
前記格子の各々が少なくとも１つの格子エッジを有し、
・接続タイプの各々の対に関する結果の接続タイプを含む組み合わせ表を供給する工程と、
・もしも前記第１の構造要素の第１の格子が前記第２の構造要素の第２の格子とエッジからエッジへの延長で配置される場合、前記第１の格子の第１のエッジが前記第２の格子の第２のエッジと位置合わせされることを検出する工程と、
・前記第１の格子の第１の接続素子について、前記第２の格子の対応する第２の接続素子を識別する工程と、
・前記第１および第２の接続素子の結果の接続タイプを前記組み合わせ表から取り出す工程と、
・取り出された前記結果の接続タイプを前記第１および第２の接続素子に割り当てる工程とを含むことを特徴とする、請求項４に記載の方法。
【請求項６】
それぞれの前記データ構造が、対応する構造要素の境界体積をさらに表現し、前記格子の各々が前記境界体積の表面に対応することを特徴とする、請求項４または５に記載の方法。
【請求項７】
さらに、
共通の体積基準格子に関する前記第１および第２の構造要素のそれぞれの位置を符号化する工程であって、前記対応する第１および第２の構造要素の前記第１および第２の格子が前記体積基準格子のそれぞれ第１および第２の平面に対応し、前記第１および第２の格子の前記格子点が前記体積基準格子のそれぞれの基準格子点に対応する工程と、
前記第１および第２の格子が前記体積基準格子の共通平面に対応するかどうか、および前記第１の格子の少なくとも第１の格子点が前記第２の格子の第２の格子点と同じ基準格子点に置かれているかどうかを検出する工程とを含むことを特徴とする、請求項６に記載の方法。
【請求項８】
さらに、
・前記第１の格子および前記第２の格子の一致する格子点のすべての対を識別する工程と、
・識別された格子点の対の各々について、前記接続性表から接続性情報を取り出す工程と、
・もしも格子点の少なくとも１つある対が無効な接続に対応する場合は、前記第１および第２の構造要素の間の接続を拒絶し、そうではなく、もしも格子点の少なくとも１つある対が有効な接続に対応する場合は、前記第１および第２の構造要素の間の接続を受容する工程とを含むことを特徴とする、請求項７に記載の方法。
【請求項９】
前記接続素子の各々が付随の方向をさらに有することを特徴とする、請求項１乃至８のいずれか１項に記載の方法。
【請求項１０】
前記接続性情報が、接続タイプの各対に関するインジケータを含むことで予め決められた接続性タイプのグループのうちの１つを示し、前記グループが接続素子の対応する対の間の接続を供給する有効な接続、接続素子の対応する対の間の接続を妨げる無効な接続、および中立の接続で構成されることを特徴とする、請求項１乃至９のいずれか１項に記載の方法。
【請求項１１】
互いの予め決められた近接に位置する前記第１の構造要素の第１の接続素子および前記第２の構造要素の第２の接続素子を判定する前記工程がさらに、予め決められた接続素子のサブセットから前記第１および第２の接続素子を判定する工程を含むことを特徴とする、請求項１乃至１０のいずれか１項に記載の方法。
【請求項１２】
それぞれの前記データ構造の各々が前記対応する構造要素の境界体積をさらに表現し、前記方法が前記第１および第２の構造要素の前記境界体積の交差部を検出する工程をさらに含み、予め決められた接続素子のサブセットから前記第１および第２の接続素子を判定する前記工程が前記判定された交差部に含まれる接続素子から前記第１および第２の接続素子を判定する工程を含むことを特徴とする、請求項１１に記載の方法。
【請求項１３】
データ処理システムであって、
構造要素を他の構造要素と接続するためのいくつかの接続素子を各々が有する複数の相互接続された前記構造要素から構築された幾何学的対象物のコンピュータ読み取り可能なモデルを作り出すための手段と、
前記複数の構造要素のうちの第１および第２の１つを、対応する前記構造要素の前記接続素子であって各々が複数の予め決められた接続タイプのうちの１つを付随して有する前記接続素子を各々が表現する、対応する第１および第２のデータ構造として符号化するための手段と、
互いの予め決められた近接に位置する前記第１の構造要素の第１の接続素子と前記第２の構造要素の第２の接続素子を判定する手段と、
前記第１および第２の接続素子が前記第１と前記第２の構造要素の間の接続を供給するかどうかの指標である前記第１および第２の接続素子の対応する前記接続タイプの接続性情報を取り出す手段とを含むことを特徴とするデータ処理システム。
【請求項１４】
前記接続タイプの対の接続性情報を含む接続表を記憶するための記憶手段をさらに含むことを特徴とする請求項１３に記載のデータ処理システム。
【請求項１５】
接続タイプの対の予め決められたセットの各々に関する結果の接続タイプを含む組み合わせ表を記憶するための記憶手段をさらに含むことを特徴とする請求項１３または１４に記載のデータ処理システム。
【請求項１６】
プログラムがコンピュータ上でランされると請求項１乃至１２のいずれか１項に記載の工程のすべてを実行するためのプログラムコード手段を含むコンピュータ・プログラム。
【請求項１７】
コンピュータ・プログラム製品がコンピュータ上でランされると請求項１乃至１２のいずれか１項に記載の方法を実行するためのコンピュータ読み込み可能な媒体に記憶されたプログラムコード手段を含むコンピュータ・プログラム製品。
【請求項１】
複数の相互接続可能な構造要素から構成された幾何学的対象物のコンピュータ読み取り可能なモデルを作り出す方法であって、各々の構造要素が、前記構造要素を他の構造要素と接続するためのいくつかの接続素子を有し、
前記複数の構造要素のうちの第１および第２の１つを、対応する前記構造要素の前記接続素子であって各々が複数の予め決められた接続タイプのうちの１つを付随して有する前記接続素子を各々が表現する、対応する第１および第２のデータ構造として符号化する工程と、
互いの予め決められた近接に位置する前記第１の構造要素の第１の接続素子と前記第２の構造要素の第２の接続素子を判定する工程と、
前記第１および第２の接続素子が前記第１と前記第２の構造要素の間の接続を供給するかどうかの指標である前記第１および第２の接続素子の対応する前記接続タイプの接続性情報を取り出す工程とを含む方法。
【請求項２】
前記接続タイプの接続性情報を含む接続表を供給する工程をさらに含み、かつ接続性情報を取り出す前記工程が前記接続表から前記接続性情報を取り出す工程を含むことを特徴とする、請求項１に記載の方法。
【請求項３】
さらに、
・接続タイプの対の予め決められたセットの各々に関する結果的に生じる接続タイプを含む組み合わせ表を供給する工程と、
・互いに予め決められた幾何学的関係で配置される第１および第２の接続素子を判定する工程と、
・前記組み合わせ表から前記第１および第２の接続素子の結果的に生じる接続タイプを取り出す工程と、
・取り出された結果の接続タイプを少なくとも結果の接続素子へと割り当てる工程とを含むことを特徴とする、請求項１または２に記載の方法。
【請求項４】
それぞれの前記データ構造の各々が前記対応する構造要素に相対していくつかの格子をさらに表現し、各々の格子がいくつかの格子点を有し、前記構造要素の前記接続素子の各々が前記格子点のうちの１つと関係し、かつ対応する接続タイプを有することを特徴とする、請求項１乃至３のいずれか１項に記載の方法。
【請求項５】
前記格子の各々が少なくとも１つの格子エッジを有し、
・接続タイプの各々の対に関する結果の接続タイプを含む組み合わせ表を供給する工程と、
・もしも前記第１の構造要素の第１の格子が前記第２の構造要素の第２の格子とエッジからエッジへの延長で配置される場合、前記第１の格子の第１のエッジが前記第２の格子の第２のエッジと位置合わせされることを検出する工程と、
・前記第１の格子の第１の接続素子について、前記第２の格子の対応する第２の接続素子を識別する工程と、
・前記第１および第２の接続素子の結果の接続タイプを前記組み合わせ表から取り出す工程と、
・取り出された前記結果の接続タイプを前記第１および第２の接続素子に割り当てる工程とを含むことを特徴とする、請求項４に記載の方法。
【請求項６】
それぞれの前記データ構造が、対応する構造要素の境界体積をさらに表現し、前記格子の各々が前記境界体積の表面に対応することを特徴とする、請求項４または５に記載の方法。
【請求項７】
さらに、
共通の体積基準格子に関する前記第１および第２の構造要素のそれぞれの位置を符号化する工程であって、前記対応する第１および第２の構造要素の前記第１および第２の格子が前記体積基準格子のそれぞれ第１および第２の平面に対応し、前記第１および第２の格子の前記格子点が前記体積基準格子のそれぞれの基準格子点に対応する工程と、
前記第１および第２の格子が前記体積基準格子の共通平面に対応するかどうか、および前記第１の格子の少なくとも第１の格子点が前記第２の格子の第２の格子点と同じ基準格子点に置かれているかどうかを検出する工程とを含むことを特徴とする、請求項６に記載の方法。
【請求項８】
さらに、
・前記第１の格子および前記第２の格子の一致する格子点のすべての対を識別する工程と、
・識別された格子点の対の各々について、前記接続性表から接続性情報を取り出す工程と、
・もしも格子点の少なくとも１つある対が無効な接続に対応する場合は、前記第１および第２の構造要素の間の接続を拒絶し、そうではなく、もしも格子点の少なくとも１つある対が有効な接続に対応する場合は、前記第１および第２の構造要素の間の接続を受容する工程とを含むことを特徴とする、請求項７に記載の方法。
【請求項９】
前記接続素子の各々が付随の方向をさらに有することを特徴とする、請求項１乃至８のいずれか１項に記載の方法。
【請求項１０】
前記接続性情報が、接続タイプの各対に関するインジケータを含むことで予め決められた接続性タイプのグループのうちの１つを示し、前記グループが接続素子の対応する対の間の接続を供給する有効な接続、接続素子の対応する対の間の接続を妨げる無効な接続、および中立の接続で構成されることを特徴とする、請求項１乃至９のいずれか１項に記載の方法。
【請求項１１】
互いの予め決められた近接に位置する前記第１の構造要素の第１の接続素子および前記第２の構造要素の第２の接続素子を判定する前記工程がさらに、予め決められた接続素子のサブセットから前記第１および第２の接続素子を判定する工程を含むことを特徴とする、請求項１乃至１０のいずれか１項に記載の方法。
【請求項１２】
それぞれの前記データ構造の各々が前記対応する構造要素の境界体積をさらに表現し、前記方法が前記第１および第２の構造要素の前記境界体積の交差部を検出する工程をさらに含み、予め決められた接続素子のサブセットから前記第１および第２の接続素子を判定する前記工程が前記判定された交差部に含まれる接続素子から前記第１および第２の接続素子を判定する工程を含むことを特徴とする、請求項１１に記載の方法。
【請求項１３】
データ処理システムであって、
構造要素を他の構造要素と接続するためのいくつかの接続素子を各々が有する複数の相互接続された前記構造要素から構築された幾何学的対象物のコンピュータ読み取り可能なモデルを作り出すための手段と、
前記複数の構造要素のうちの第１および第２の１つを、対応する前記構造要素の前記接続素子であって各々が複数の予め決められた接続タイプのうちの１つを付随して有する前記接続素子を各々が表現する、対応する第１および第２のデータ構造として符号化するための手段と、
互いの予め決められた近接に位置する前記第１の構造要素の第１の接続素子と前記第２の構造要素の第２の接続素子を判定する手段と、
前記第１および第２の接続素子が前記第１と前記第２の構造要素の間の接続を供給するかどうかの指標である前記第１および第２の接続素子の対応する前記接続タイプの接続性情報を取り出す手段とを含むことを特徴とするデータ処理システム。
【請求項１４】
前記接続タイプの対の接続性情報を含む接続表を記憶するための記憶手段をさらに含むことを特徴とする請求項１３に記載のデータ処理システム。
【請求項１５】
接続タイプの対の予め決められたセットの各々に関する結果の接続タイプを含む組み合わせ表を記憶するための記憶手段をさらに含むことを特徴とする請求項１３または１４に記載のデータ処理システム。
【請求項１６】
プログラムがコンピュータ上でランされると請求項１乃至１２のいずれか１項に記載の工程のすべてを実行するためのプログラムコード手段を含むコンピュータ・プログラム。
【請求項１７】
コンピュータ・プログラム製品がコンピュータ上でランされると請求項１乃至１２のいずれか１項に記載の方法を実行するためのコンピュータ読み込み可能な媒体に記憶されたプログラムコード手段を含むコンピュータ・プログラム製品。
【図１ａ】
【図１ｂ】
【図１ｃ】
【図１ｄ】
【図１ｅ】
【図２ａ】
【図２ｂ】
【図２ｃ】
【図２ｄ】
【図３】
【図４】
【図５ａ】
【図５ｂ】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２ａ】
【図１２ｂ】
【図１ｂ】
【図１ｃ】
【図１ｄ】
【図１ｅ】
【図２ａ】
【図２ｂ】
【図２ｃ】
【図２ｄ】
【図３】
【図４】
【図５ａ】
【図５ｂ】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２ａ】
【図１２ｂ】
【公表番号】特表２００６−５０２４８５（Ｐ２００６−５０２４８５Ａ）
【公表日】平成１８年１月１９日（２００６．１．１９）
【国際特許分類】
【出願番号】特願２００４−５４２２０９（Ｐ２００４−５４２２０９）
【出願日】平成１５年１０月９日（２００３．１０．９）
【国際出願番号】ＰＣＴ／ＤＫ２００３／０００６７４
【国際公開番号】ＷＯ２００４／０３４３３３
【国際公開日】平成１６年４月２２日（２００４．４．２２）
【出願人】（５９４０１２６２３）レゴ エー／エス (19)
【Ｆターム（参考）】
【公表日】平成１８年１月１９日（２００６．１．１９）
【国際特許分類】
【出願日】平成１５年１０月９日（２００３．１０．９）
【国際出願番号】ＰＣＴ／ＤＫ２００３／０００６７４
【国際公開番号】ＷＯ２００４／０３４３３３
【国際公開日】平成１６年４月２２日（２００４．４．２２）
【出願人】（５９４０１２６２３）レゴ エー／エス (19)
【Ｆターム（参考）】
[ Back to top ]