(57)【要約】  構築要素モデル用の構築説明を生成するコンピュータ実施方法であって、モデルは、複数の構築要素を含み、構築説明は、構築要素モデルを組み立てるための組立ステップの逐次的順序を表し、各組立ステップは、少なくとも１つの構築要素を構築要素モデルに追加することを含む。前記方法は、構築要素モデルのデジタル表現から、構築要素モデルを構築要素に分解するための分解ステップの逐次的順序を決定することであって、各分解ステップが、構築要素モデルから少なくとも１つの構築要素を除去することを含む、決定することと、組立ステップの逐次的順序を獲得するために、分解ステップの決定された逐次的順序を逆転することとを含む。
2010521727.tif 000002
【特許請求の範囲】
【請求項１】
構築要素モデル用の構築説明を生成するコンピュータ実施方法であって、前記モデルは、複数の構築要素を含み、前記構築説明は、前記構築要素モデルを組み立てるための組立ステップの逐次的順序を表し、各組立ステップは、少なくとも１つの構築要素を前記構築要素モデルに追加することを含み、前記方法が、
−前記構築要素モデルのデジタル表現から、前記構築要素モデルを構築要素に少なくとも部分的に分解するための分解ステップの少なくとも１つの系列を決定することであって、各分解ステップが、前記構築要素モデルから少なくとも１つの構築要素を除去することを含む、決定することと、
−前記分解ステップの少なくとも１つの系列に基づいて、組立ステップの前記逐次的順序のうちの少なくとも１つの組立ステップを決定することと、
を含むコンピュータ実施方法。
【請求項２】
分解ステップの少なくとも１つの系列を決定することが、前記構築要素モデルを構築要素に分解するための分解ステップの逐次的順序を決定することであって、各分解ステップが、前記構築要素モデルから少なくとも１つの構築要素を除去することを含む、決定することを含み、組立ステップの前記逐次的順序のうちの少なくとも１つの組立ステップを決定することが、組立ステップの前記逐次的順序を獲得するために、分解ステップの前記決定された逐次的順序を逆転することを含む、請求項１に記載の方法。
【請求項３】
反復プロセスを実行することを含み、前記反復プロセスの一反復が、
−先行する反復からもたらされる組立ステップの逐次的順序を獲得することであって、組立ステップの前記逐次的順序が、第１の部分モデルをもたらす、獲得することと、
−第２の部分モデルをもたらす、少なくとも１つの後続する構築要素の前記第１の部分モデルへの結合を表す、後続する組立ステップを決定することと、
−前記構築要素モデルが、前記構築要素モデルを分解するための分解ステップの系列によって、前記第２の部分モデルをもたらすように分解可能であるかどうかを判定することと、
−前記構築要素モデルが、前記構築要素モデルを分解するための分解ステップの前記系列によって、前記第２の部分モデルをもたらすように分解可能であると判定された場合、前記決定された後続する組立ステップを組立ステップの前記獲得された逐次的順序に追加することと、
を含む、請求項１に記載の方法。
【請求項４】
前記構築要素が、互いに相互結合される、請求項１乃至３のいずれか１項に記載の方法。
【請求項５】
分解ステップの前記逐次的順序を決定することは、反復プロセスを実行することを含み、前記反復プロセスの一反復は、
−先行する反復からもたらされる先行する部分モデルを獲得することと、
−新しい部分モデルをもたらすように、前記先行する部分モデルから分離する少なくとも１つの構築要素を決定することと、
を含む、請求項１乃至４のいずれか１項に記載の方法。
【請求項６】
前記先行する部分モデルから分離する前記少なくとも１つの構築要素を決定することは、
−前記先行する部分モデルの候補部分組立体からなる集合を決定することであって、各候補部分組立体が、前記先行する部分モデルの個々の相互結合された構築要素を含む、決定することと、
−前記新しい部分モデルをもたらすように、前記先行する部分モデルから分離される単一構築要素または候補部分組立体からなる前記決定された集合に属する１つのどちらかを、所定の選択基準の第１の組に従って選択することと、
を含む、請求項５に記載の方法。
【請求項７】
候補部分組立体からなる前記集合を決定することが、前記候補部分組立体を選択基準の第２の組に従って選択することを含む、請求項６に記載の方法。
【請求項８】
選択基準の前記第２の組のうちの少なくとも１つが、前記候補部分組立体の１つまたは複数と前記先行する部分モデルとの結合の結合強度を決定することを含む、請求項７に記載の方法。
【請求項９】
前記構築要素が、少なくとも２つの構築方向に沿って相互結合可能であり、選択基準の前記第２の組のうちの少なくとも１つが、構築方向の変更が生じる、前記先行する部分モデルにおける１つまたは複数の位置を決定することを含む、請求項７または８に記載の方法。
【請求項１０】
１つまたは複数の構築要素が、少なくとも１つの方向の周りで可動な結合を提供するためのコネクタ要素を含み、選択基準の前記第２の組のうちの少なくとも１つが、前記先行する部分モデルに可動に結合される１つまたは複数の部分組立体を決定することを含む、請求項７乃至９のいずれか１項に記載の方法。
【請求項１１】
前記反復プロセスの一反復の最中に除去するために選択された各部分組立体について、分解ステップの系列を決定することをさらに含む、請求項６乃至１０のいずれか１項に記載の方法。
【請求項１２】
前記先行する部分モデルの個々の構築要素を表すノードと、対応する構築要素間の結合を表す個々のノードを接続するエッジとを含むグラフを表すデータ構造によって、前記先行する部分モデルを表現することを含む、請求項５乃至１１のいずれか１項に記載の方法。
【請求項１３】
前記グラフのエッジが、前記エッジによって接続されるノードに対応する構築要素間の結合の結合強度を表す関連する結合強度値を有する、請求項１２に記載の方法。
【請求項１４】
各構築要素が、前記構築要素と別の構築要素の間の結合を提供するために、前記別の構築要素の１つまたは複数の対応する結合要素とかみ合うように適合された１つまたは複数の結合要素を含み、各結合要素は、それを結合要素クラスに関連付け、各結合要素クラスは、それを結合強度に関連付け、前記方法が、少なくとも対応する結合に寄与する結合要素の数およびそれぞれのクラスから、２つの構築要素間の結合に対応するエッジの前記関連付けられた結合強度値を決定することを含む、請求項１３に記載の方法。
【請求項１５】
前記関連付けられた結合強度値を決定することが、前記対応する結合に寄与する結合要素の数およびそれぞれのクラスから、ならびに前記２つの構築要素の体積から前記結合強度を決定することを含む、請求項１３または１４に記載の方法。
【請求項１６】
前記先行する部分モデルが含む候補部分組立体の集合を決定するために、グラフ区分化プロセスを実行することを含む、請求項１２乃至１５のいずれか１項に記載の方法。
【請求項１７】
前記グラフのエッジが、前記エッジによって接続されるノードに対応する構築要素間の結合の構築方向を表す関連する値を有する、請求項１２乃至１６のいずれか１項に記載の方法。
【請求項１８】
前記先行する部分モデルの候補部分組立体の集合を決定するために、前記グラフの１つまたは複数の関節ノードを識別することを含む、請求項１２乃至１７のいずれか１項に記載の方法。
【請求項１９】
前記先行する部分モデルの候補部分組立体の集合を決定するために、前記グラフの１つまたは複数の関節ノード対を識別することを含む、請求項１２乃至１８のいずれか１項に記載の方法。
【請求項２０】
１つまたは複数の構築要素が、少なくとも１つの方向の周りで可動な結合を提供するためのコネクタ要素を含み、前記グラフのノードおよびエッジの少なくとも一方が、可動な結合の存在を表す関連する値を有する、請求項１２乃至１９のいずれか１項に記載の方法。
【請求項２１】
新しい部分モデルをもたらすように、前記先行する部分モデルから分離する少なくとも１つの構築要素を決定することが、前記構築要素の部分集合および構築要素からなる候補部分組立体の集合の少なくとも一方のための１つまたは複数の重み関数を計算することと、前記計算された重み関数の比較に基づいて、単一構築要素および部分組立体の一方を選択すること、とを含む、請求項５乃至２０のいずれか１項に記載の方法。
【請求項２２】
前記１つまたは複数の重み関数の少なくとも１つが、分離されることの適切度を表す第１の部分範囲と、分離されることの不適切度を表す第２の部分範囲とを含む可能な結果の範囲を有する、請求項２１に記載の方法。
【請求項２３】
前記計算された重み関数の比較に基づいて、単一構築要素または部分組立体を選択することが、前記１つまたは複数の計算された重み関数から合計の重みを計算することを含み、前記合計の重みを計算することが、前記計算された重み関数の少なくとも１つが前記第２の範囲内の結果を有する場合には、前記第２の範囲内の値を前記合計の重みに割り当てることを含む、請求項２２に記載の方法。
【請求項２４】
各構築要素が、前記構築要素の別の１つの１つまたは複数の対応する結合要素とかみ合わせるための１つまたは複数の結合要素を含み、各結合要素が、前記構築要素が別の構築要素からそれに沿って分離可能な分離の方向を確定し、構築要素または部分組立体のための前記１つまたは複数の重み関数のうちの第１の重み関数を計算することが、前記先行する部分モデルの１つまたは複数の他の構築要素に結合される前記構築要素または部分組立体のすべてのコネクタのそれぞれの分離の方向が互いに平行であるかどうかを判定することを含む、請求項２１乃至２３のいずれか１項に記載の方法。
【請求項２５】
構築要素または部分組立体のための前記第１の重み関数を計算することが、前記構築要素または部分組立体と前記先行する部分モデルの他の任意の構築要素または部分組立体の間の分離の方向における最小距離を決定することをさらに含む、請求項２４に記載の方法。
【請求項２６】
構築要素または部分組立体のための前記第１の重み関数を計算することが、
−前記構築要素または部分組立体の引き延ばされた幾何学的形状を決定することであって、前記引き延ばされた幾何学的形状は、分離の方向に引き延ばされる、決定することと、
−前記引き延ばされた幾何学的形状が前記先行する部分モデルの他の任意の構築要素または部分組立体と交差するかどうかを判定することと、
をさらに含む、請求項２４に記載の方法。
【請求項２７】
構築要素または部分組立体のための前記１つまたは複数の重み関数のうちの第２の重み関数を計算することが、前記構築要素または部分組立体が関節構築要素または部分組立体であるかどうかを判定することをさらに含む、請求項２１乃至２６のいずれか１項に記載の方法。
【請求項２８】
構築要素または部分組立体のための前記１つまたは複数の重み関数のうちの第３の重み関数を計算することが、前記構築要素または部分組立体が構築要素または部分組立体からなる関節対の一部であるかどうかを判定することをさらに含む、請求項２１乃至２７のいずれか１項に記載の方法。
【請求項２９】
構築要素または部分組立体のための前記１つまたは複数の重み関数のうちの第４の重み関数が、前記構築要素または部分組立体が結合される他の構築要素の数とともに減少する関数である、請求項２１乃至２８のいずれか１項に記載の方法。
【請求項３０】
前記１つまたは複数の重み関数のうちの第５の重み関数が、前記部分組立体の構築要素間の結合の結合強度の関数である、請求項２１乃至２９のいずれか１項に記載の方法。
【請求項３１】
前記第５の重み関数を計算することが、前記部分組立体の相互結合された構築要素間の最弱結合強度を決定することを含み、前記第５の重み関数が、前記決定された最弱結合強度の減少関数である、請求項３０に記載の方法。
【請求項３２】
前記１つまたは複数の重み関数のうちの第６の重み関数が、前記部分組立体の構築要素と前記先行する部分モデルの他の構築要素との結合の結合強度の関数である、請求項２１乃至３１のいずれか１項に記載の方法。
【請求項３３】
前記第６の重み関数を計算することが、前記部分組立体の前記構築要素と前記部分組立体に含まれない前記先行する部分モデルの１つまたは複数の他の構築要素との間の最強結合強度を決定することを含み、前記第６の重み関数が、前記決定された最強結合強度の減少関数である、請求項３２に記載の方法。
【請求項３４】
構築要素または部分組立体の前記１つまたは複数の重み関数のうちの第７の重み関数が、座標系に関する所定の方向沿いの前記構築要素または部分組立体の位置の座標の関数である、請求項２１乃至３３のいずれか１項に記載の方法。
【請求項３５】
構築要素または部分組立体の前記１つまたは複数の重み関数のうちの第８の重み関数が、少なくとも前記構築要素および部分組立体の特性と前記反復プロセスの先行する反復の最中に分離された構築要素または部分組立体の特性との関数である、請求項２１乃至３４のいずれか１項に記載の方法。
【請求項３６】
前記第８の重み関数が、前記構築要素または部分組立体と前記反復プロセスの先行する反復の最中に分離された構築要素または部分組立体との間の距離の関数である、請求項３５に記載の方法。
【請求項３７】
前記第８の重み関数が、前記構築要素または部分組立体と前記反復プロセスの先行する反復の最中に分離された構築要素または部分組立体との間の少なくとも所定の空間的関係を表す類似性の所定の尺度と、前記構築要素または部分組立体および前記反復プロセスの先行する反復の最中に分離された構築要素または部分組立体に関連する１つまたは複数の属性の比較との関数である、請求項３５または３６に記載の方法。
【請求項３８】
前記デジタル表現が、所定の座標系に関する前記構築要素の各々のそれぞれの位置座標を含む、請求項１乃至３７のいずれか１項に記載の方法。
【請求項３９】
仮想構築要素モデルを対話的に組み立てるためのコンピュータ実施組立環境を用いて、前記構築要素モデルの前記デジタル表現を生成することをさらに含む、請求項１乃至３８のいずれか１項に記載の方法。
【請求項４０】
初期部分モデルと、増加部分モデルの系列と、完成モデルとを含む部分モデルの系列に対応するグラフィカル表現の系列を生成することを含み、前記増加部分モデルの各々が、前記系列のうちの直前の増加部分モデルのすべての構築要素と、前記複数の構築要素からの所定の数の追加構築要素とを含み、前記追加構築要素が、組立ステップの前記決定された系列によって決定される、請求項１乃至３９のいずれか１項に記載の方法。
【請求項４１】
前記生成されたグラフィカル表現のユーザ制御操作を容易にするユーザ・インタフェースを提供することをさらに含む、請求項４０に記載の方法。
【請求項４２】
プログラムコード手段を保存するデータ処理システムであって、前記プログラムコード手段が前記データ処理システム上で実行されたときに、請求項１乃至４１のいずれか１項に記載の方法の前記ステップを前記データ処理システムに実行させるように前記プログラムコード手段が適合される、データ処理システム。
【請求項４３】
プログラムコード手段を含むコンピュータ・プログラム製品であって、前記プログラムコード手段がデータ処理システム上で実行されたときに、請求項１乃至４１のいずれか１項に記載の方法の前記ステップを前記データ処理システムに実行させるように前記プログラムコード手段が適合される、コンピュータ・プログラム製品。
【請求項４４】
前記プログラムコード手段を保存するコンピュータ可読媒体を含む、請求項４３に記載のコンピュータ・プログラム製品。
【請求項４５】
搬送波内で実施され、説明の系列を表すコンピュータ・データ信号であって、データ処理システムによって実行されたときに、請求項１乃至４１のいずれか１項に記載の方法の前記ステップを前記データ処理システムに実行させるコンピュータ・データ信号。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、構築要素モデル（ｂｕｉｌｄｉｎｇ  ｅｌｅｍｅｎｔ  ｍｏｄｅｌ）用の構築説明（ｂｕｉｌｄｉｎｇ  ｉｎｓｔｒｕｃｔｉｏｎ）の生成に関する。
【背景技術】
【０００２】
物理的な組立玩具セット（ｃｏｎｓｔｒｕｃｔｉｏｎ  ｔｏｙ  ｓｅｔ）について様々なタイプのモデル作成概念（ｍｏｄｅｌｌｉｎｇ  ｃｏｎｃｅｐｔ）が知られている。特に、モジュール概念または半モジュール概念は、挑戦的で面白い遊戯経験を提供するので、非常に人気がある。一般に、これらの概念は、１組の事前製造された構築要素を提供し、それらは、事前製造された要素の結合要素（ｃｏｎｎｅｃｔｉｏｎ  ｅｌｅｍｅｎｔ）を用いて、いくつかの所定の方法で互いに相互結合することができる。事前製造された構築要素は、特定のモデル作成作業に適合された、よく知られた物に似ている。したがって、例えば、家屋のモデルの構築においては、構築要素は、壁面レンガ、屋根タイル、ドア、および窓に似ていてよい。このように構築要素を選択する目的は、新しいモデルを作成するたびに家屋のすべての細部を確定することになる状況と比べて、家屋のモデルの構築に関与する作業を著しく減少させることである。しかし、家屋または別の物を構築する際の完全な自由は、モデルの構築の簡単さとトレードオフの関係にある。
【０００３】
例えば、ＬＥＧＯという名で入手可能な玩具組立セット（ｔｏｙ  ｃｏｎｓｔｒｕｃｔｉｏｎ  ｓｅｔ）は、複数の異なるタイプの相互結合可能な構築要素を含み、それらは、結合要素として凸部と対応する凹部とを有する。結合要素は、規則的な格子パターンに従って配列され、それによって、構築要素間での多種多様な相互結合を可能にする。
【０００４】
一般に、そのような玩具組立セットは、１つまたは複数の構築要素モデル、例えば、動物、ロボット、もしくは別の生物、自動車、飛行機、宇宙船、または建物などを作成するのに適した１組の構築要素を含む。一般に、組立セットはさらに、セットの構築要素からあるモデルをどのように組み立てたらよいかを説明する、印刷された構築説明または組立説明（ａｓｓｅｍｂｌｙ  ｉｎｓｔｒｕｃｔｉｏｎ）を含む。それにも関わらず、組立セットが子供たちを刺激して自分たちのモデルを作成するよう促すことは、そのような組立セットの興味深い特徴である。
【０００５】
典型的に、玩具組立セットに同梱されている構築説明は、構築要素をどんな順序でどのようにモデルに追加したらよいかを段階的に説明する一連の絵を含む。そのような構築説明は、玩具組立セットにあまり経験のない子供および／または文字を読めない子供であっても理解しやすいという利点を有する。
【０００６】
一般に、モデル用の構築説明は、構築要素が組み立てられる組立ステップおよびサブステップの系列と見なすことができる。その系列は、１つまたは複数の最初の構築要素から始まり、一連のステップにわたって発展して、モデルの組立完成形（ｃｏｎｓｔｒｕｃｔｉｏｎ）である完全な組立体になる。各ステップにおいて、単一構築要素または構築要素の部分組立体（ｓｕｂ−ａｓｓｅｍｂｌｙ）のどちらかが追加される。本明細書では説明のため、部分組立体という用語は、構築要素モデルの、相互結合された構築要素からなる一部分のことを指す。したがって、構築要素の代わりに部分組立体を追加する場合、それに伴って、その部分組立体用の下位構築説明が主構築説明に追加されることがある。本明細書では説明のため、そのような下位構築説明は、サブステップとも呼ばれる。したがって、ステップの系列は一般に、ステップからなる枝分かれしたツリーとして表すことができ、各枝は下位構築説明を含む。
【０００７】
これまでは、そのような構築説明は、例えば、人手で合理的な構築ステップを決定し、対応する説明をＣＡＤシステムで描き、そのようにして生成された説明を最後に印刷することによって、人手で生成されていた。そのような構築説明は高品質、すなわち理解しやすいとしても、上述の生成プロセスは、高度な技能を必要とし、労働集約的であるという不都合を有する。結果として、構築説明は一般に、構築要素の製造業者によって設計された構築要素モデルについて存在するだけである。特に、構築説明を生成するための上述の従来技術の方法は、自分のモデルを友達と共有することを可能にする、自分のモデル用の構築説明を生成したいと望む子供に適していない。
【０００８】
最近では、構築説明は、印刷形式の代わりに電子形式で生成されるようになった。特に、アニメーション化された構築説明では、より複雑化した構築ステップがアニメーションで示される。しかし、そのような構築説明の生成は、依然として、熟練した設計者による構築ステップの設計と描画／アニメーション化を必要とする。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】国際特許出願ＷＯ２００５／１２４６９６
【特許文献２】米国特許第７，０９２，８９９号
【特許文献３】米国特許第６，３８９，３７５号
【特許文献４】国際出願ＷＯ０４１０４８１１
【特許文献５】ＷＯ０４／０３４３３３
【非特許文献】
【００１０】
【非特許文献１】M. Agrawala et al.、「Designing Effective Step-by-Step Assembly Instructions」、http://graphics.stanford.edu/papers/assembly_instructions/
【非特許文献２】Jonathan L. Gross and Jay Yellen、「Graph Theory and Its Applications」、Chapman & Hall/CRC、second edition、2006
【非特許文献３】Jacob Allerelli、「Computer-aided generation of building instructions for LEGO models」、Department of Mathematics and Computer Science、University of Southern Denmark、June 2006
【発明の概要】
【発明が解決しようとする課題】
【００１１】
ＬＥＧＯシステムなどの複雑なシステムでは、あるモデルに対して可能な構築説明の数は、そのモデル内の構築要素の数とともに指数関数的に増加する。結果として、一般に、与えられたモデルに対する実質的に無限個の可能な構築説明から、高品質の１組の命令を決定することは、自動構築説明プロセスにとって難題である。したがって、複雑なモデルに対しても実用的で理解しやすい説明を生成する、自動化プロセスを提供することが望ましい。さらに、穏当な計算用ハードウェア上で穏当な時間内で構築説明を生成する、そのようなプロセスを提供することが望ましい。
【００１２】
さらに、自分のモデルを友達と共有して遊戯経験をさらに改善することを可能にする、自分のモデル用の構築説明を生成したいと望む子供に適した、構築説明を生成するための方法を提供することが望ましい。特に、ユーザとの対話を僅かしかまたはまったく必要とせず、必要な入力はユーザが容易に入手可能なものである方法を提供することが望ましい。
【００１３】
効果的で理解しやすい段階的な構築説明の設計は、いくつかの研究の主題ともなっている。http://graphics.stanford.edu/papers/assembly_instructions/から取得できる、M. Agrawala他によるインターネット刊行物「Designing Effective Step-by-Step Assembly Instructions」は、認知心理学に基づいた効果的な組立説明のための設計原理を説明している。この論文はさらに、組み立てられる物各々についての情報、グラフィカル描画のための組立体の向きおよびカメラ視点、グループ化情報、留め具、部品の重要性、対称性についての情報、ならびに組立順序に対する制約についての情報に基づいて組立説明を生成するためのコンピュータ化されたシステムを開示している。この入力に基づいて、システムは、与えられた制約を考慮に入れた広範囲にわたる探索アルゴリズムに基づいて、一連の組立ステップを計算する。上述の従来技術システムの問題は、それが計算的に高コストであり、複雑な入力データを必要とし、したがってユーザに高度な抽象的思考を要求することである。
【００１４】
公開された国際特許出願ＷＯ２００５／１２４６９６は、仮想構築モデル用の構築説明を生成するための自動化されたプロセスを開示しており、構築説明は、仮想組立環境における仮想モデルの組み立ての最中にユーザによって使用された組立ステップの順序によって決定されるステップの逐次的順序（ｓｅｑｕｅｎｔｉａｌ  ｏｒｄｅｒ）を利用する。この従来技術の方法は、使用しやすい自動化プロセスを提供するものの、自動的に生成された構築説明の質を高めることに依然として問題を残している。
【課題を解決するための手段】
【００１５】
本明細書では、構築要素モデル用の構築説明を生成するコンピュータ実施方法が開示され、モデルは、複数の構築要素を含み、構築説明は、構築要素モデルを組み立てるための組立ステップの逐次的順序を表し、各組立ステップは、少なくとも１つの構築要素を構築要素モデルに追加することを含み、前記方法は、
−構築要素モデルのデジタル表現から、構築要素モデルを構築要素に少なくとも部分的に分解するための分解ステップ（ｄｅｃｏｎｓｔｒｕｃｔｉｏｎ  ｓｔｅｐ）の少なくとも１つの系列を決定することであって、各分解ステップが、構築要素モデルから少なくとも１つの構築要素を除去することを含む、決定することと、
−複数の分解ステップの少なくとも１つの系列に基づいて、組立ステップの逐次的順序のうちの少なくとも１つの組立ステップを決定することと、
を含む。
【００１６】
したがって、分解ステップの１つまたは複数の系列を決定することによって、組立ステップの系列を効率的に決定し得ることが実現された。
【００１７】
モデルの構築分解（ｂｕｉｌｄｉｎｇ  ｄｅｃｏｎｓｔｒｕｃｔｉｏｎ）は、構築要素が分離される、ステップおよびサブステップの系列／反復プロセスと見なすことができる。その系列は、完全なモデルから始まり、一連のステップにわたって進行する。完全な分解においては、プロセスは、すべての構築要素がモデルから分離されるまで継続し、一方、部分的な分解においては、プロセスは、所定の残りの部分モデル（ｐａｒｔ−ｍｏｄｅｌ）だけが残った時点で終了する。各ステップにおいて、単一構築要素または構築要素の部分組立体のどちらかが分離される。したがって、構築要素の代わりに部分組立体を分離する場合、それに伴って、その部分組立体用の下位構築分解が主構築分解に関連付けられることがある。そのような下位構築分解は、サブステップとも呼ばれる。したがって、構築組立（ｂｕｉｌｄｉｎｇ  ｃｏｎｓｔｒｕｃｔｉｏｎ）と同様に、分解プロセスのステップの系列は一般に、ステップからなる枝分かれしたツリーであり、各枝は下位構築分解を含む。
【００１８】
構築分解を見出すことができる場合、この情報は、組立系列を生成するプロセスにおいて使用することができる。したがって、組立ステップは、分解系列を決定するステップに対応して決定することができる。さらに、ある選択基準を満たす分解系列の探索は、穏当な計算リソースを用いて可能であり、高品質の構築説明をもたらすことが分かった。
【００１９】
さらに、この計算的に単純な方法によって生成された構築説明は、ユーザ、特に子供が理解しやすいことが分かった。
【００２０】
さらに、構築説明に対する唯一の入力は、例えば、仮想モデル生成プロセスの最中に記録されるような、構築要素モデルのデジタル表現であるので、ユーザは、設計技能または幾何学、制約などについての抽象的知識を有する必要なく、構築説明を容易に生成できる。さらに、構築説明の生成は、ユーザが実際に仮想モデルを組み立てた順序から独立している。仮想組立環境は、物理的な現実世界のモデルでは実行するのが困難なことがある、または不可能なことさえある順序での組立ステップの実行を可能にすることができるので、これは有利なことがある。
【００２１】
いくつかの実施形態では、方法は、
−構築要素モデルのデジタル表現から、構築要素モデルを構築要素に分解するための分解ステップの逐次的順序を決定することであって、各分解ステップが、構築要素モデルから少なくとも１つの構築要素を除去することを含む、決定することと、
−組立ステップの逐次的順序を獲得するために、分解ステップの決定された逐次的順序を逆転することと、
を含む。
【００２２】
構築分解を見出すことができる場合、ちょうど構築説明を逆方向に辿ることによってモデルを分解することが可能であるように、それを逆転させて、構築説明をもたらすことができる。したがって、組立ステップの系列は、分解ステップの１つまたは複数の系列を決定し、次に分解ステップの順序を逆転させて、組立ステップの系列を獲得することによって、効率的に決定することができる。このプロセスが単一の分解系列の生成しか必要としないことは利点である。
【００２３】
代替実施形態では、方法は、反復プロセスを実行することを含み、反復プロセスの一反復は、
−先行する反復からもたらされる組立ステップの逐次的順序を獲得することであって、組立ステップの逐次的順序が、第１の部分モデルをもたらす、獲得することと、
−第２の部分モデルをもたらす、少なくとも１つの後続する構築要素の第１の部分モデルへの結合を表す、後続する組立ステップを決定することと、
−構築要素モデルが、構築要素モデルを分解するための分解ステップの系列によって、第２の部分モデルをもたらすように分解可能であるかどうかを判定することと、
−構築要素モデルが、構築要素モデルを分解するための分解ステップの系列によって、第２の部分モデルをもたらすように分解可能であると判定された場合、決定された後続する組立ステップを組立ステップの獲得された逐次的順序に追加することと、
を含む。
【００２４】
したがって、この実施形態では、各組立ステップは、完成モデルの部分的分解によって結果の部分モデルを獲得できるように決定される。結果として、構築説明を生成するための効率的なプロセスが、完全なモデルから現在の組立ステージまでの分解が各組立ステップにおいてシミュレートされる組立プロセスによって提供される。
【００２５】
この実施形態は、もっぱら分解に基づく代わりに、（ブロックの空集合から始まり、完全なモデルで終わる）組み立てによって機能する。これは、ユーザにとって、構築説明を考えるより直観的な方法であるので、ユーザが構築説明を生成するプロセスと対話することを可能にするより使いやすく強力な方法を可能にする。ユーザ対話の一例は、ある提案されたブロックに対して反対をとなえ、代替提案を受け入れることとすることができる。この単純な対話は、実際に、ユーザが、特に高品質の構築説明を、非常に短時間で、最小限のユーザ対話を必要とするだけで生成することを可能にする。さらに、ジェネレータは、ハード制約が決して違反されないことを保証することができ、結果として、たとえユーザが反対しても、穏当な提案だけが行われる。
【００２６】
したがって、一実施形態では、後続する組立ステップを決定するステップは、例えば、組立ステップの提案、賛成、および拒否のうちの少なくとも１つの形をとる、ユーザ入力を受け取ることを含むことができる。
【００２７】
構築要素モデルが、構築要素モデルを分解するための分解ステップの系列によって、第２の部分モデルをもたらすように分解可能であるかどうかを判定するステップは、構築要素モデルが、各分解ステップが選択基準の１つまたは複数の所定の組によって選択される分解ステップの系列によって、そのように分解可能であるかどうかを判定するステップを含むことができる。したがって、高品質な構築説明を提供するために見出された効率的な方法が提供される。
【００２８】
いくつかの実施形態では、分解ステップの逐次的順序を決定することは、反復プロセスを実行することを含み、反復プロセスの一反復は、
−先行する反復からもたらされる先行する部分モデルを獲得することと、
−新しい部分モデルをもたらすように、先行する部分モデルから分離する少なくとも１つの構築要素を決定することと、
を含む。
【００２９】
したがって、プロセスは、完成モデルから始まり、各反復において１つまたは複数の構築要素を除去することによって、部分モデルの系列を生成する。高品質の構築説明の探索は一般に、バックトラッキング（ｂａｃｋｔｒａｃｋｉｎｇ）を必要とし、したがって、計算的に非常に高コストであり、大規模なモデルの場合には法外な高コストにさえなるが、構築分解は、計算ハードウェアに対する要求がはるかに小さいワンパス・アルゴリズムによって達成できることが分かった。
【００３０】
一般に、ＬＥＧＯという名称で市販されている玩具構築システム（ｔｏｙ  ｂｕｉｌｄｉｎｇ  ｓｙｓｔｅｍ）などの複雑な構築システムでは、いくつかの構築要素は単一構築要素に分離できないような仕方で互いに組み合わさっていることがあるので、モデルによっては１つ１つの構築要素に分解することが可能でないことがある。しかし、一般に、すべてのモデルは、各ステップにおいて、単一構築要素または構築要素の部分組立体のどちらかを除去することによって分離することができる。
【００３１】
したがって、いくつかの実施形態では、少なくとも１つの構築要素を決定することは、
−先行する部分モデルの候補部分組立体（ｃａｎｄｉｄａｔｅ  ｓｕｂ−ａｓｓｅｍｂｌｙ）からなる集合を決定することであって、各候補部分組立体が、先行する部分モデルの個々の相互結合された構築要素を含む、決定することと、
−新しい部分モデルをもたらすように、先行する部分モデルから分離される単一構築要素または候補部分組立体からなる決定された集合に属する１つのどちらかを、所定の選択基準の第１の組に従って選択することと、
を含む。
【００３２】
したがって、いくつかの実施形態では、部分組立体は、分解系列の目的で、疑似構築要素として扱われる。しかし、構築要素モデルの可能な部分組立体の数は一般に、そのモデル内の構築要素の数とともに指数関数的に増加する。結果として、適度なサイズのモデルであっても、すべての可能な部分組立体にわたって探索を行い、分離される１つの部分組立体を与えられたある基準によって選択するためのトップダウン手法は、もっぱら単一構築要素の除去を考える場合には、そのような手法がおそらく実現可能であるとしても、計算的に法外な高コストになる。
【００３３】
いくつかの実施形態では、本明細書で説明される方法は、上述のトップダウン手法を、トップダウン探索にゆだねる候補部分組立体を生成するためのボトムアップ手法と組み合わせる。候補部分組立体の生成は、１つもしくは複数のジェネレータ・サブプロセスからなる組または選択基準の第２の組に従って実行することができ、したがって、モデルのすべての可能な部分組立体からなる集合の、候補部分組立体からなる部分集合をもたらす。したがって、ボトムアップ手法は、計算的に高コストなトップダウン手法を実行する前に、探索空間を刈り込むために使用される。
【００３４】
トップダウン探索とボトムアップ生成の上述の切り分けは、計算的により低コストで、プログラム的により容易で、例えば、候補部分組立体を生成するための付加的なジェネレータ・サブプロセスを追加することによって、容易に拡大可能なプロセスをもたらす。
【００３５】
さらに、上述の手法は、生成する候補部分組立体の数を制御するためのメカニズムを提供し、したがって、計算コストと結果の構築説明の品質とをトレードオフし、候補のプールのサイズを任意の与えられたハードウェア要件および時間要件に見合ったものに調整するためのメカニズムを提供するので、改善された制御を提供する。
【００３６】
いくつかの実施形態では、選択基準の第２の組のうちの少なくとも１つは、候補部分組立体の１つまたは複数と先行する部分モデルとの結合の結合強度（ｃｏｎｎｅｃｔｉｏｎ  ｓｔｒｅｎｇｔｈ）を決定することを含む。結果として、部分組立体は、先行する部分モデルの残りの部分との結合の強度に従って生成／選択される。部分組立体についてのこの選択／生成戦略は、特に高品質の構築説明をもたらすことが分かった。
【００３７】
候補部分組立体を効率的に選択するための追加的または代替的な選択規則は、構築方向の変更、および／または先行する部分モデルに、例えば、蝶番もしくは継手結合、スライダなどを用いて、可動に結合される部分組立体を決定することを含む。
【００３８】
いくつかの実施形態では、方法は、先行する部分モデルの個々の構築要素を表すノードと、対応する構築要素間の結合を表す個々のノードを接続するエッジとを含むグラフ、例えば、無向グラフを表すデータ構造によって、先行する部分モデルを表現することを含む。先行する部分モデルをグラフとして表現することによって、グラフ理論から知られているグラフ区分化技法および他の技法（例えば、Jonathan L. GrossおよびJay Yellenによる「Graph Theory and Its Applications」、Chapman & Hall/CRC、second edition、2006を参照）が、例えば、グラフ内で関節ノード（ａｒｔｉｃｕｌａｔｉｏｎ  ｎｏｄｅ）または関節対を識別することによって、単一の関節構築要素または１対の構築要素によって先行する部分モデルの残りの部分に結合された部分組立体を識別するなど、適切な候補部分組立体を効率的に識別するために使用できる。したがって、相互結合された構築要素からなるモデルは、接続グラフに対応し、部分組立体は、接続サブグラフに対応する。
【００３９】
グラフのノードおよび／またはエッジは、対応する構築要素および結合の属性にそれぞれ対応する、それらに関連付けられた１つまたは複数の個々の属性を有することができる。例えば、グラフのノードは、それらに関連付けられた以下の属性、すなわち、構築要素タイプ、構築要素体積、構築要素形状／幾何学的配置、体積構築要素質量（ｖｏｌｕｍｅ  ｂｕｉｌｄｉｎｇ  ｅｌｅｍｅｎｔ  ｍａｓｓ）、構築要素のバウンディング・ボックス（ｂｏｕｎｄｉｎｇ  ｂｏｘ）、座標系内における構築要素の位置、構築要素に関連付けられた主構築方向（ｍａｉｎ  ｂｕｉｌｄｉｎｇ  ｄｉｒｅｃｔｉｏｎ）、ならびに／または構築要素の結合要素の位置、タイプ、および／もしくは方向などのうちの１つまたは複数を有することができる。同様に、グラフのエッジは、それらに関連付けられた以下の属性、すなわち、結合タイプ、結合強度、および／または結合方向などのうちの１つまたは複数を有することができる。グラフのエッジが、結合のそれぞれの結合強度を表す、それらに関連付けられたそれぞれの重み／値を有する場合、最小カットを見出すための方法など、特に効率的なグラフ区分化方法が、高品質の構築説明を獲得するために使用できる。
【００４０】
いくつかの実施形態では、各構築要素は、構築要素と別の構築要素の間の結合を提供するために、別の構築要素の１つまたは複数の対応する結合要素とかみ合うように適合された１つまたは複数の結合要素を含む。結合は、例えば、対応する凹部に合致する凸部など、合致した結合要素間でだけ、それも互いに対して正しい位置に配置されたときにのみ可能であるので、そのような結合要素は、構築要素の可能な配置にさらなる制約を課すことがある。各結合要素は、それを結合要素クラスに関連付けることができ、各結合要素クラスは、それを結合強度に関連付ける。いくつかの実施形態では、方法は、少なくとも対応する結合に寄与する結合要素の数およびそれぞれのクラスから、２つの構築要素間の結合に対応するエッジの前記関連付けられた結合強度値を決定することを含む。結果として、構築要素モデルにおける結合強度を計算／推定するための効率的で正確な方法が提供される。
【００４１】
いくつかの実施形態では、前記関連付けられた結合強度値を決定することは、少なくとも対応する結合に寄与する結合要素の数およびそれぞれのクラスから、ならびに２つの構築要素の体積から結合強度を決定し、それによって、結合強度ばかりでなく構築要素のサイズも考慮に入れ、そのようにして、構築プロセスの最中に、構築要素が保持および操作しやすいかどうかを判定することを含む。
【００４２】
いくつかの実施形態では、新しい部分モデルをもたらすように、先行する部分モデルから分離する少なくとも１つの構築要素を決定することは、構築要素の部分集合および構築要素からなる候補部分組立体の集合の少なくとも一方のための１つまたは複数の重み関数を計算することと、計算された重み関数の比較に基づいて、単一構築要素および部分組立体の一方を選択することとを含む。結果として、選択プロセスのための拡張性、拡大性、および柔軟性のあるフレームワークが提供され、そのフレームワークは、代替的または追加的な重み関数によって変更または拡大でき、そのフレームワークにおいては、重要性／優先順位に従って、異なる選択基準に互いに対して相対的に重み付けすることができる。重み関数は、１つまたは複数の構築要素の１つまたは複数の特性についての任意の適切な関数を含むことができる。
【００４３】
いくつかの実施形態では、１つまたは複数の重み関数の少なくとも１つは、分離されることの適切度を表す第１の部分範囲と、分離されることの不適切度を表す第２の部分範囲とを含む可能な結果の範囲を有し、それによって、構築要素および／または部分組立体に正の重みおよび負の重みを割り当てることをともに可能にする。
【００４４】
したがって、いくつかの実施形態では、計算された重み関数の比較に基づいて、単一構築要素または部分組立体を選択することは、１つまたは複数の計算された重み関数から合計の重みを計算することを含み、合計の重みを計算することは、計算された重み関数の少なくとも１つが第２の範囲内の結果を有する場合には、第２の範囲内の値を合計の重みに割り当てることを含み、それによって、他の重み関数からは高い重みを獲得できたとしても、ある基準を満たさない構築要素および／または部分組立体が分離されることを防止する、拒否戦略（ｖｅｔｏ−ｓｔｒａｔｅｇｙ）を提供する。
【００４５】
高品質の構築説明をもたらすことが知られている重み関数の例は、構築要素もしくは部分組立体が物理的に分離可能であるかどうか、または前記構築要素もしくは部分組立体の分離の方向が、例えば、モデルの他の部分によって妨害されていないかどうかを判定する重み関数を含む。例えば、そのような重み関数は、構築要素または部分組立体の引き延ばされた幾何学的形状（ｓｔｒｅｔｃｈｅｄ  ｇｅｏｍｅｔｒｙ）を計算することによって、効率的に計算することができる。
【００４６】
そのような重み関数の別の例は、モデルが独立／分離した部分モデルに分裂することを回避するために、関節構築要素および／または構築要素もしくは部分組立体からなる関節対に含まれる構築要素により低い重みを割り当てる重み関数を含む。重み関数が、構築要素または部分組立体が直接または他の構築要素を介して結合される他の構築要素の数に伴い減少する重み関数を含む場合、小さな独立した部分は、それらが生じた場合、速やかにモデルから除去されることが保証される。
【００４７】
重み関数の１つが、部分組立体の構築要素間の結合の結合強度の関数である場合、残りのモデルから容易に分離可能な構築要素および部分組立体を優遇することができる。特に、より強い内部結合性とより弱い外部結合性を有する構築要素および部分組立体により高い重みを割り当てる重み関数は、高品質の構築説明をもたらすことが分かった。さらに、そのような重み関数においては、結合性強度は、相互結合された構築要素または部分組立体の体積に関連する強度として計算することができる。
【００４８】
適切な重み関数のまたさらなる例は、少なくとも構築要素または部分組立体の特性と、反復プロセスの先行する反復の最中に分離された構築要素または部分組立体の特性との関数である重み関数を含み、そのようにして、対称的に配置された構築要素もしくは部分組立体、および／または別の構築要素もしくは部分組立体の近くに配置された構築要素もしくは部分組立体などの除去を優遇することを可能にする。そのような特性の例は、座標系に関連する構築要素の位置、および／または構築要素タイプなどを含む。いくつかの実施形態では、重み関数はさらに、先行する反復において除去された２つ以上の構築要素の特性の関数とすることができる。例えば、部分モデルを比較するとき、より以前の反復の１つまたは複数には、異なる重みを割り当てることができ、例えば、最近の反復には、より以前の反復よりも高い重みを割り当てることができる。
【００４９】
本明細書で説明される方法の実施形態は、構築要素モデルのデジタル表現を受け取る。そのようなデジタル表現は、例えば、コンピュータ実施組立環境、および／または例えば、物理的モデルまたは別の物体の画像など、１つまたは複数の画像から構築要素モデルのデジタル表現を生成するプロセスなど、任意の適切なプロセスによって提供することができる。そのようなプロセスの１つが、米国特許第７，０９２，８９９号で説明されている。このプロセスにおいては、物品の構築要素モデルのデジタル表現は、ＣＡＤモデルまたは３次元物品の１組の２次元画像から生成される。デジタル表現のいくつかの実施形態は、構築要素のタイプ、位置、および／または相互結合などを表す情報を、任意の適切なデータ形式で含むことができる。デジタル表現の実施形態はさらに、全体的モデルの属性、構築要素のタイプ、色、サイズ、バウンディング・ボックスなどの個々の構築要素の属性についての情報を含むことができる。
【００５０】
仮想構築要素モデルを対話的に組み立てるためのコンピュータ実施組立環境は、コンピュータ上で実行されたときに、構築要素を選択すること、構築要素をモデルに追加すること、構築要素をモデルから削除すること、構築要素の向きを変更すること、例えば、色、タイプ、および／またはサイズなどの構築要素の特性を変更すること、モデルを見ること、モデルのデジタル表現をセーブすること、以前セーブされたモデルのデジタル表現をロードすることなどの操作を含む、仮想構築要素モデルの操作をユーザが行えるようにする、グラフィカル・ユーザ・インタフェースを提供する、コンピュータ・プログラムを含むことができる。仮想構築要素は、対応する物理的な構築要素の仮想的な対応物とすることができ、すなわち、対応する相対的サイズ、形状、色などを有する。
【００５１】
コンピュータ実施組立環境は、構築要素間の衝突検出など、互いとの関係で構築要素の相対的位置に課される所定の１組の制約を強制するように構成することができる。例えば、制約は、対応する物理的な構築要素に適用可能な対応する制約に対応し、それによって、仮想構築要素モデルが、対応する物理的な構築要素からも実際に組み立て得ることを保証する。したがって、生成された構築説明が実際に実現可能であること、すなわち、所望の結果をもたらすことを方法が保証することは利点である。
【００５２】
いくつかの実施形態では、構築説明は、画像などのグラフィカル表現の系列として生成される。各グラフィカル表現は、部分モデルとも呼ばれる部分的な構築要素モデルのグラフィカル描画を含むことができ、それによって、所定の数の構築要素がモデルに追加される、構築プロセスにおけるステップに各グラフィカル表現が対応した、理解しやすい構築説明を提供する。したがって、組立系列の１つまたは複数のステップを組み合わせて構築説明の単一の画像にすることができるので、決定された組立系列を構成するすべての部分モデルまたは部分モデルの一部のみが、最終的な構築説明に含まれ得る。ユーザは、２つの連続するグラフィカル表現を比較することによって、各ステップにおいてどの構築要素を追加するか、それらをどのように追加するかを容易に決定することができる。
【００５３】
方法がさらに、グラフィカル表現を見るためのユーザ・インタフェースを提供することを含み、ユーザ・インタフェースが好ましくは、生成されたグラフィカル表現のユーザ制御操作を容易にする場合、構築要素モデルのデジタル表現をコンピュータ上に便利に表示することができる。特に、モデルのデジタル表現は、構築説明の生成に必要とされるすべての情報を含むので、構築説明は、例えば、記憶媒体に保存され、例えば電子メールの添付ファイルとして通信ネットワークを介して送信され、またはウェブサーバ上にアップロードされるなど、１つのコンピュータから別のコンピュータに便利に伝達することができる。したがって、デジタル表現の受け手は、グラフィカル表現を見ることができ、例えば、表示アングルの変更、ズーム、および／または表示オプションの変更など、それを操作することができる。結果として、ユーザは、構築説明を友達に容易に伝達することができる。デジタル表現が説明の各ステップのグラフィカル描画を含む必要がなく、それによって、デジタル表現のファイルサイズを小さく保てることはさらなる利点である。さらに、デジタル表現は、すべての関連するモデル情報を含むことができるので、モデルの受け手は、構築説明を生成する前に、モデルを修正することさえできる。
【００５４】
いくつかの実施形態では、構築説明は、所定のファイル形式で生成することができ、それによって、印刷された構築説明および／または電子的な構築説明の生成を可能にする。適切なファイル形式の例は、ＨＴＭＬ、ＸＭＬ、ＢＭＰ、ＴＩＦＦなどを含む。
【００５５】
いくつかの実施形態では、段階的説明からなるステップにおいて追加される追加構築要素の所定数は、ユーザ選択可能であり、それによって、ユーザが、例えば、各ステップが単一の新しい構築要素の配置に対応する非常に詳細な段階的説明と、各ステップが多数の新たに配置される構築要素に対応する非常にコンパクトな説明の間で選択することを可能にする。いくつかの実施形態では、各ステップにおいて追加される構築要素の数は、すべてのステップにおいて同じである。他の実施形態では、追加される追加構築要素の数は、構築説明の異なるステップごとに異なることができる。例えば、ステップサイズは、ユーザによってステップごとに制御され、それによって、組み立てのより複雑な部分に対してはよりきめ細かな説明の生成を可能にする。
【００５６】
本発明は、上記および下記の方法、データ処理システム、およびさらなる製品手段を含む異なる方法で実施することができ、各々は、最初に言及される方法に関連して説明される利益および利点の１つまたは複数をもたらし、各々は、最初に言及される方法に関連して説明され、それに関連する従属請求項で開示される好ましい実施形態に対応する、１つまたは複数の好ましい実施形態を有する。
【００５７】
特に、上記および下記の方法の特徴は、ソフトウェアで実施することができ、データ処理システムまたはコンピュータ実行可能命令の実行によって引き起こされる他の処理手段において実施することができる。命令は、記憶媒体から、またはコンピュータ・ネットワークを介して別のコンピュータから、ＲＡＭなどのメモリ内にロードされる、プログラムコード手段とすることができる。代替的に、説明される特徴は、ソフトウェアの代わりにハードワイヤード回路によって、またはソフトウェアとの組み合わせで実施することができる。
【００５８】
したがって、本発明はさらに、上記および下記の方法を実行するように適合されたデータ処理システムに関する。本発明はさらに、コンピュータ・プログラムに関し、コンピュータ・プログラムは、コンピュータ上で実行された場合に、上記および下記の方法のすべてのステップを実行するためのプログラムコード手段を含む。本発明はさらに、コンピュータ・プログラム製品に関し、コンピュータ・プログラム製品は、コンピュータ上で実行された場合に、上記および下記の方法を実行するためのプログラムコード手段を含む。プログラムコード手段は、コンピュータ可読媒体に保存することができ、および／または伝播データ信号として実施することができる。
【００５９】
いくつかの実施形態では、コンピュータ・プログラムは、構築要素モデルのデジタル表現を生成するための第１のソフトウェア・コンポーネントと、生成されたデジタル表現から構築説明を生成するための第２のソフトウェア・コンポーネントとを含み、それによって、モデルのデジタル表現を読み取るためと、対応する構築説明を提示するための別個のソフトウェア・コンポーネントを提供する。結果として、構築説明を伝達する場合、ユーザは、デジタル表現を第２のソフトウェア・コンポーネントと一緒に伝達することができ、それによって、受け手が追加のソフトウェアを必要とせずに見ることができる、構築説明のコンパクトな自己完結型の表現を提供する。しかし、両方のプロセス、すなわち、モデルのデジタル表現の生成および構築説明の生成は、単一のソフトウェア・コンポーネント内に統合できることを理解されたい。
【００６０】
本発明は、図面を参照しながら、好ましい実施形態との関連で、以下でより完全に説明される。
【図面の簡単な説明】
【００６１】
【図１ａ】構築要素モデルの構築説明を生成するためのデータ処理システムを示す図である。
【図１ｂ】構築要素モデルの構築説明を生成するためのデータ処理システムを示す図である。
【図２】全体的な構築説明生成の一実施形態のフローチャートである。
【図３】分解ステップの系列を生成するためのプロセスの一実施形態のフローチャートである。
【図４】構築要素およびその結合要素の一例を示す図である。
【図５】構築要素モデルをデジタル的に表現するためのデータ構造の一実施形態を示す図である。
【図６】構築説明アプリケーションのグラフィカル・ユーザ・インタフェースの一実施形態を示す図である。
【図７】無向グラフとしての構築要素モデルの表現を示す図である。
【図８】選択基準の実施形態を図説する例を示す図である。
【図９】選択基準の実施形態を図説する例を示す図である。
【図１０】選択基準の実施形態を図説する例を示す図である。
【図１１】選択基準の実施形態を図説する例を示す図である。
【図１２】選択基準の実施形態を図説する例を示す図である。
【図１３】選択基準の実施形態を図説する例を示す図である。
【図１４】全体的な構築説明生成の別の実施形態のフローチャートである。
【図１５】部分分解の分解ステップの系列を生成するためのプロセスの一実施形態のフローチャートである。
【図１６】全体的な構築説明生成の別の実施形態のフローチャートである。
【発明を実施するための形態】
【００６２】
図１ａ〜図１ｂは、幾何学的物体からなるコンピュータ可読モデルを生成および操作するためのデータ処理システムを示している。
【００６３】
図１ａは、コンピュータ・システムの一例の概略図を示している。コンピュータ・システムは、ディスプレイ１２０、キーボード１２１、ならびにコンピュータマウス１２２、および／またはタッチパッド、トラックボール、ライトペン、もしくはタッチスクリーンなどの別のポインティング・デバイスを備える、例えばパーソナルコンピュータなど、適切にプログラムされるコンピュータ１０１を含む。
【００６４】
１０１で指示されるコンピュータ・システムは、構築要素モデルのデジタル表現から構築説明を生成するように適合される。コンピュータ・システム１０１はさらに、本明細書で説明されるように、構築説明を生成することばかりでなく、仮想構築要素モデルを設計し、保存し、操作し、共用することも容易にするように適合することができる。コンピュータ・システム１０１は、スタンドアロン・システムとして、またはクライアント／サーバ・システムにおけるクライアントとして使用することができる。いくつかの実施形態では、コンピュータ・システムはさらに、コンピュータを例えばインターネットなどのコンピュータ・ネットワークと接続するための１つまたは複数のインタフェースを含む。
【００６５】
図１ｂは、構築要素モデルの構築説明を生成するためのデータ処理システムのブロック図を示している。コンピュータ１０１は、例えば、ランダム・アクセス・メモリ（ＲＡＭ）およびハードディスクなど、部分的に揮発性メモリ手段として、また部分的に不揮発性メモリ手段として実施され得る、メモリ１０２を備える。メモリは、その中に、モデル・コード・インタプリタ１０７と、モデル・コード・ジェネレータ１０８と、ＵＩイベント・ハンドラ１０９と、モデリング・アプリケーション１１０と、構築説明ジェネレータ１１３とを保存しており、各々は、中央処理装置１０３によって実行可能である。さらに、メモリは、その中に、モデル・データ１１１、すなわち、構築要素モデルのデジタル表現を表す１組のデータ構造を保存している。
【００６６】
コード・インタプリタ１０７は、例えば、モデルの構築要素のデータ構造を表すコードなど、モデルを定義するデジタル表現を読み取り、解釈するように適合される。好ましい一実施形態では、コード・インタプリタは、モデルのデジタル表現を読み取り、そのようなモデルをコンピュータ・ディスプレイ上での提示用の知られたグラフィック形式、好ましくは、モデルの３Ｄ描画に変換するように適合される。
【００６７】
ＵＩイベント・ハンドラ１０９は、ユーザのユーザ・インタフェースとの対話をコード・ジェネレータ１０８によって認識可能な適切なユーザ・コマンドに変換するように適合される。１組の可能で認識可能なコマンドは、要素のライブラリから構築要素を取得すること、別の構築要素に結合されるように構築要素を配置すること、構築要素を分離すること、構築要素を廃棄すること、例えば回転などを開始することによって、構築要素、構築要素のグループなどを操作すること、を含むことができる。各コマンドには、例えば、表示座標系に関するカーソル座標、構築要素のタイプなど、１組のそれぞれのパラメータを関連付けることができる。
【００６８】
コード・ジェネレータ１０８はさらに、ユーザのコマンドに応答して、モデルのデータ構造を変更するように適合することができる。同時または後続タスクとして、コード・ジェネレータの結果を提示するために、コード・インタプリタを実行することができる。
【００６９】
モデリング・アプリケーション１１０は、メモリ、ファイル、ユーザ・インタフェースなどを制御するように適合される。
【００７０】
バーチャル・リアリティ・モデリングの一実施形態が、米国特許第６，３８９，３７５号で説明されている。さらに、新しい仮想構築要素を３Ｄ構造を含むシーン内に対話的に配置するプロセスの一実施形態が、公開された国際出願ＷＯ０４１０４８１１で説明されている。両文献は、参照によりその全体が本明細書に組み込まれる。
【００７１】
構築説明アプリケーション１１３は、モデルのデジタル表現を読み取り、本明細書で説明されるように、読み取ったモデル・データから構築説明を生成するように適合される。構築説明アプリケーション１１３はさらに、本明細書で説明されるような構築ステップの保存された系列、または生成された構築説明のための他の任意の適切な出力形式に従って、部分モデルを表示するためのユーザ・インタフェースを提供することができる。構築説明アプリケーション１１３は、モデルの読み取りおよびグラフィカル描画のため、ならびにユーザ入力の受け取りのため、それぞれ、コード・インタプリタ１０７およびＵＩイベント・ハンドラ１０９によって提供される関数を使用することができる。代替実施形態では、構築説明アプリケーションは、自己完結型であり、すなわち、外部ソフトウェア・コンポーネントに依存しない。いくつかの実施形態では、構築説明アプリケーションは、例えば印刷可能形式など、適切なファイル形式で構築説明を生成する。
【００７２】
ユーザ１０５は、好ましくはコンピュータ画面上に表示されるグラフィカル・ユーザ・インタフェースを含むユーザ・インタフェース１０６と、キーボードおよび／またはポインティング・デバイスなどの１つまたは複数の入力デバイスを用いて、コンピュータ・システム１０１と対話することが可能である。モデル、幾何学的記述、または他のデータをロードし、セーブし、または伝達するため、コンピュータ・システムは、入出力ユニット（Ｉ／Ｏ）１０４を備える。入出力ユニットは、異なるタイプの記憶媒体、および例えばインターネットなど異なるタイプのコンピュータ・ネットワークに対するインタフェースとして使用することができる。さらに、入出力ユニット（Ｉ／Ｏ）１０４は、例えば対話的に、他のユーザとモデルを交換するために使用することができる。メモリ１０２、中央処理装置（ＣＰＵ）１０３、ユーザ・インタフェース（ＵＩ）１０６、および入出力ユニット１０４の間でのデータ交換は、データバス１１２を用いて達成される。
【００７３】
図１のデータ処理システムは、モデリング・アプリケーションおよび構築説明アプリケーションの両方を実行するように構成できることに留意されたい。しかし、他の実施形態では、データ処理システムは、例えば、モデリング・アプリケーションまたはデジタル・モデル表現を生成するための別のアプリケーションが実行されるコンピュータなど、別のコンピュータから受け取ったモデル・データに基づいて、構築説明アプリケーションだけを実行するように構成することができる。同様に、前記他のコンピュータ上に、モデリング・アプリケーションを単独でインストールすることができ、または構築説明アプリケーションと組み合わせてインストールすることもできる。
【００７４】
図２は、構築説明生成の一実施形態のフローチャートを示している。ステップＳ１において、プロセスは、例えば、図１ｂのモデリング・アプリケーション１１０などのモデル生成モジュールによって、または他の任意の適切なプロセスによって生成されるような、構築要素モデルのデジタル表現を受け取る。
【００７５】
デジタル表現は、例えば、構築説明アプリケーションを実行するコンピュータのローカル・ハードディスク、ＣＤ  ＲＯＭ、またはディスケットなどの、記憶媒体２０３から取得することができる。代替的または追加的に、モデルのデジタル表現は、リモートに保存することができ、例えば、それが保存された、コンピュータ・ネットワークの別のコンピュータから受け取ることができる。例えば、デジタル表現は、１人または複数人のユーザがそれを入手できるようにしたウェブサーバからダウンロードすることができる。デジタル表現のデータ構造の例が以下で説明される。
【００７６】
後続ステップＳ２〜Ｓ４において、構築説明アプリケーションは、ロードされたデジタル表現から構築説明２０５を生成する。一実施形態では、構築説明アプリケーションは、部分モデルの３Ｄビューの系列を生成し、各部分モデルは、本明細書で説明されるような構築説明プロセスによって決定される組立ステップの系列に従って、所定の数の追加構築要素がモデルに追加される点で、直前の部分モデルから区別される。構築説明２０５は、電子的に提示し、印刷し、または別の適切な方法で提示することができる。いくつかの実施形態では、構築説明の生成は、ユーザ２０４によって制御することができる。例えば、ユーザは、各ステップにおいて追加される追加構築要素の数を選択することができる。さらに、ユーザは、以下で説明されるように、カメラ位置の変更などを含む、生成された３Ｄビューの操作を行うことができる。ユーザ２０４は、ユーザ２０２と同じユーザでもよく、または異なるユーザでもよい。
【００７７】
特に、ステップＳ２において、プロセスは、例えば、モデルの構築要素および／または部分組立体からなる逐次的リストの形式をとった、モデルの受け取ったデジタル表現から分解系列を生成する。プロセスはさらに、逐次的リストの部分組立体について下位分解系列を生成する。一実施形態では、プロセスは、ステップからなる枝分かれしたツリーとして分解系列を表し、各枝は下位構築分解を含むことができる。分解系列を生成するためのプロセスの一実施形態が、以下でより詳細に説明される。
【００７８】
ステップＳ３において、プロセスは、組立系列を獲得するために、生成された分解系列を逆転させる。
【００７９】
ステップＳ４において、プロセスは、例えば、部分モデルの画像または他の表現の系列としての、生成された組立系列から構築説明を生成し、各部分モデルでは、先行する部分モデルと比較して、生成されたリストに属する構築要素および部分組立体の１つまたは複数が追加されている。プロセスは、本明細書で説明されるように、任意の適切な形式で、生成された説明を保存することができ、および／またはそれらを出力することができる。
【００８０】
図３は、モデルＭの分解プロセスの一例のフローチャートを示している。分解プロセスは、モデル内のすべての構築要素を含む完成モデルＭのデジタル表現に基づいて、モデルＭを分解する（ステップ３０１）。モデルＭの入力は、構築要素のサイズ／寸法、瘤（ｋｎｏｂ）の数、蝶番、釘（ｐｅｇ）、回転軸などの特別な特徴など、個々の構築要素についての情報を含む。デジタル表現は、例えば、適切な座標系に関する構築要素のそれぞれの（ｘ，ｙ，ｚ）位置を指定することによって、各構築要素がモデル内のどこに配置されるかについての情報も含む。
【００８１】
ステップ３０２において、分解プロセスは、モデルＭ（または先行する反復からもたらされた部分モデル）内に分離される構築要素が残っているかどうかのテストを行う。モデル内にまだ構築要素が存在する場合、プロセスは、ステップ３０３に進み、そこにおいて、プロセスはモデルＭから除去するための１つまたは複数の候補部分組立体を選択／生成する。候補部分組立体は、相互結合された構築要素を含む。後続ステップ３０４において、プロセスは、所定の選択基準の第１の組に従って、分離される構築要素または生成された候補部分組立体の１つ（Ｅ）を選択する。所定の選択基準のこの第１の組は、その例が以下でより完全に説明される所定の重み関数に従って、すべての構築要素および生成された部分組立体に重みを割り当てる。したがって、プロセスは、候補のプールから構築要素または部分組立体を決定し、プールは、すべての個々の構築要素および生成された候補部分組立体を含む。したがって、選択プロセスの目的では、実際の構築要素に加えて、部分組立体も、疑似構築要素として扱われるものと見なすことができる。本明細書では説明のため、構築要素および候補部分組立体のプールのメンバは、除去候補とも呼ばれる。
【００８２】
候補部分組立体は、ステップ３０３において、モデルをどのように分離／切断できるかについての決定である選択基準の第２の組を用いて、見出され／選択される。そのような選択基準の例が、以下でより完全に説明される。
【００８３】
ステップ３０５において、プロセスは、ステップ３０４で選択された構築要素または部分組立体Ｅをモデルから分離し、すなわち、選択された候補部分組立体のすべての構築要素のうちの選択された構築要素が除去された、新しい部分モデルＭ’＝Ｍ＼Ｅを生成する。プロセスは、分解系列を表すデータ構造を維持し、分離される部分組立体／構築要素についての情報を用いてデータ構造を更新する。系列は保存され、そのため、構築説明を獲得するために後でそれを逆転することができる。
【００８４】
プロセスが、分離される部分組立体を選択した場合、反復的分解プロセスを継続するためにステップ３０２に復帰して、残りの部分モデル、すなわちモデルＭ’＝Ｍ＼Ｅから分離する次の構築要素を見出す前に、選択された部分組立体は、ステップ３０７において再帰的方式で（すなわち、選択された部分組立体Ｅを入力モデルＭとして利用して）分解プロセスを実行することによって分解することができる。
【００８５】
モデル内にもはや構築要素が存在しない場合、モデルは完全に分解され、分解プロセスはステップ３０８において停止する。
【００８６】
したがって、上述の分解プロセスの一実施形態は、以下の疑似コードによって表すことができる。
【００８７】
Ｄｅｃｏｎｓｔｒｕｃｔ  ｍｏｄｅｌ  Ｍ：
ＣａｎｄｉｄａｔｅｓをＭ内のすべてのブロックからなる集合とする
Ｒｅｓｕｌｔをブロックからなる空系列とする
Ｗｈｉｌｅ（Ｃａｎｄｉｄａｔｅｓは空でない）
Ｄを分離可能なＣａｎｄｉｄａｔｅｓの部分集合とする
ｂをＤに属する「最良分離可能」ブロックとする
ｂをＲｅｓｕｌｔに追加する
Ｃａｎｄｉｄａｔｅｓからｂを除去する
Ｒｅｓｕｌｔを返す
【００８８】
上記の疑似コードにおいて、「最良分離可能」ブロックの選択は、上記のステップ３０４において実行される選択、すなわち、１組の所定の選択基準、例えば、以下で説明される選択基準の１つまたは複数に基づいた選択に対応する。
【００８９】
部分組立体の重み付けは、モデルのすべての可能な部分組立体のうちの部分集合において実行されるだけなので、選択をより多くのステップに分離するときに、選択を処理することが計算的に可能であることは、最初にモデルから分離できる候補部分組立体を選択し、次にその後でそれを分離することがどれだけ好ましいかに従って各候補に重みを割り当てることの利点である。
【００９０】
分解プロセスの一例は、Jacob Allerelliによる論文「Computer-aided generation of building instructions for LEGO models」、Department of Mathematics and Computer Science、University of Southern Denmark、June 2006において、本発明の発明者らの一人によって説明されており、同論文は、参照により本明細書に組み込まれる。以下では、ステップ３０３において候補部分組立体を決定するための選択基準の第２の組の選択規則の例が、より詳細に説明される。これらの選択基準は、カット・ヒューリスティック（ｃｕｔ  ｈｅｕｒｉｓｔｉｃ）とも呼ばれる。
【００９１】
最小カット／グラフ区分化：
適切な候補部分組立体は、グラフをサブグラフに区分化するためのグラフ区分化技法を使用することによって、効率的に決定できることが理解された。この目的を達成するために、プロセスは、ノードおよびノードを接続するエッジを含む無向グラフを表すデータ構造でモデルを表現し、ノードは、構築要素を表し、エッジは、構築要素間の結合を表す。そのようなグラフは、結合グラフとも呼ばれる。結合グラフの一例が、図７に示されている。図７ａは、構築要素ａ、ｂ、ｃ、ｄ、ｅを含む構築要素モデルの一例を示している。図７ｂは、ノードａ、ｂ、ｃ、ｄ、ｅを含む対応する結合グラフを示している。
【００９２】
グラフデータ構造のエッジデータ項目は、エッジによって表される結合によって結合される構築要素の間の対応する結合の（物理的）結合強度を表す属性を含むことができる。そのため、グラフの最小重みカットを識別するためのグラフ区分化プロセスは、部分組立体を分離するのに必要な物理的強度／力が少なくとも近似的に最小化されるような部分組立体をもたらす。このようにして、最も緩やかに結合された部分組立体が選択される。構築要素間の結合強度を決定する一例が、以下でより詳細に説明される。
【００９３】
構築方向変更：
構築方向の変更が生じる場所でモデルを切り離すのが有利である。構築方向の変更は、構築要素が少なくとも２つの構築方向に沿って相互結合される場合に生じることがある。構築方向の変更の位置は、結合グラフにおける局所的グラフ探索によって見出すことができる。構築方向は、方向属性を各構築要素に関連付けることによって定義することができる。代替的または追加的に、構築方向は、方向属性を構築要素間の結合に割り当てることによって定義することができる。この目的を達成するため、結合グラフのノードおよび／またはエッジは、対応する結合の構築方向を表す、それに関連する属性を有することができる。
【００９４】
単一構築要素関節カット：
２つ以上の部分組立体／構築要素を相互結合する構築要素は、関節構築要素と呼ばれ、モデルの分離のための良好なカット位置／ノードとすることができる。ひとたび識別されると、関節構築要素は、分離される部分組立体に含まれる、すなわち除去されることが可能であり、または関節構築要素は、分離される部分組立体から除外される、すなわち除去されないことが可能である。グラフにおいて、関節構築要素は、例えば、いわゆるグラフ彩色（ｇｒａｐｈ  ｃｏｌｏｒｉｎｇ）によってフラグ付けすることができ、それによって、容易に見出すことができる。結合グラフの関節ノードは、グラフの関節ノードを見出すための、例えば縦型探索（ｄｅｐｔｈ  ｆｉｒｓｔ  ｓｅａｒｃｈ）に基づいた、任意の適切なアルゴリズムによって見出すことができる（例えば、Jonathan L. GrossおよびJay Yellenによる「Graph Theory and Its Applications」、Chapman & Hall/CRC、second edition、2006を参照）。
【００９５】
構築要素関節対カット：
関節対という用語は、２つ以上の独立部分組立体を相互結合する２つの構築要素、すなわち、その除去がモデルを２つの独立部分組立体に分離させる構築要素の対のことを指す。関節構築要素または関節対によってモデルの残りの部分に結合された部分組立体は、構築説明を生成する目的で有用な候補部分組立体となることができる。
【００９６】
関節対は、結合グラフＧ内のすべての関節ノードからなるリストＡがセーブされるプロセスによって見出すことができる。次に、Ｇ内の非関節ノードｎが除去された、グラフＧ’が生成される。Ｇ’内のすべての関節ノードからなるリストＢがセーブされる。Ｂ＼Ａ内のすべてのノードｍについて、以下の関節対、すなわち（ｎ，ｍ）が見出される。このプロセスは、グラフＧ内のすべての非関節ノードｎについて繰り返される。
【００９７】
蝶番または継手結合：
蝶番結合は、蝶番方向の周りの１つまたは複数の構築要素の間の蝶番である。構築要素は、２つ以上の構築要素間の蝶番結合を提供するための内部蝶番または蝶番結合要素を含むことができる。蝶番結合によってモデルの残りの部分に結合される部分組立体は、構築説明を生成する目的で有用な候補部分組立体とすることができる。そのような組立体は、グラフのエッジが蝶番構造の存在を表す関連する属性を有する場合、結合グラフ内で識別することができる。例えば、プロセスは、１つまたは複数の蝶番結合によってだけ結合グラフの残りの部分に結合される、結合グラフのサブグラフを探索することができる。図１２ｂは、蝶番結合を提供するための結合要素１２０１を有する構築要素を示している。例えば、継手結合、滑動結合など、他のタイプの可動結合も同様に、候補部分組立体を識別するために有用なことがあることが理解されよう。
【００９８】
特別なケース：
いくつかの構築要素は、それらが唯一の仕方で他の構築要素に結合可能な点で特別である。これらの構築要素の例は、窓内のガラス、車輪のタイヤ、レール上の列車の貨車など、形の基礎の下に単一の結合要素を有する形である。したがって、これらの特別な構築要素は、それらの外部結合、すなわち、それらが対応する構築要素とは異なる任意の構築要素に結合される場所において、モデルから切り離すことができる候補である。
【００９９】
したがって、上述において、候補部分組立体を識別するための多くのカット・ヒューリスティックが開示された。したがって、上述のような１つのカット・ヒューリスティックまたはより多くのカット・ヒューリスティックの組み合わせが、モデルの数多くのすべての可能な部分組立体の中から候補部分組立体を効率的に見出すために、分解プロセスの最中に使用できる。
【０１００】
上述されたように、一実施形態では、各除去候補、すなわち、上記または代替のカット・ヒューリスティック・プロセスによって選択される、モデルの構築要素の各々および候補部分組立体の各々は、最高の重みを有する除去候補、すなわち、モデルから除去されるのに最も適した除去候補Ｅを見出すために（ステップ３０４）、１つまたは複数の重み関数を用いて重み付けされ、その後、この選択された除去候補が分離される（ステップ３０５）。
【０１０１】
一実施形態では、重み関数が選択され、各重み関数は、それが実施する基準に基づいて、構築要素／部分組立体が選択される可能性を高め、または構築要素／部分組立体が選択されることを拒絶する。プロセスは、構築要素／部分組立体についての全体的な重みを獲得するために、各構築要素／部分組立体についてのすべての重み関数の結果を組み合わせる。その後、プロセスは、最高の重みを有する構築要素／部分組立体を選択することができる。統一された重み付けスキームに従って個々の重み付け関数が選択される場合、１組の重み付け関数は容易に変更可能である。
【０１０２】
例えば、一実施形態では、各重み関数は重みをもたらす。重みは、［０，．．．，１］の範囲内の実数か、または負の整数（−１，−２，−３，．．．）である。構築要素／部分組立体の分離が優遇される場合、構築要素／部分組立体に割り当てられた重みは、［０，．．．，１］の範囲内にあり、構築要素／部分組立体を分離することが冷遇も、優遇もされない場合、０が割り当てられ、分離が最適である場合、１が割り当てられる。これら２つの極値の間の実数は、分離がその間で優遇されることを示す。分離が冷遇される場合、重み関数は、（−１，−２，−３，．．．）の範囲内にある、構築要素／部分組立体に割り当てられる負の重みをもたらし、異なる負の値は、分離がどれほど冷遇されるかを示す。重み関数の他の組を異なる範囲を有するように定義し得ることが理解されよう。
【０１０３】
２つの別個の範囲を有する重み関数が、例えば以下で説明されるような、拒否スキームを実施するために使用できる。
【０１０４】
各構築要素／部分組立体ｘについて、１組の重み関数のうちの各々が評価され、それぞれの個々の重みが、以下のように組み合わされる。ｘに対して割り当てられた重みの中に負の重み（そのため「拒否（ＶＥＴＯ）」と呼ばれる）が存在しない場合、合計の重みを獲得するために、すべての重みが累算される。他方、割り当てられた重みの中に１つまたは複数の拒否が存在する場合、すべての非拒否重みが廃棄され、すなわち、０に等しく設定される。これによれば、分離するのに好適な構築要素／部分組立体は、拒否から無縁な、高い累算重みを有する構築要素／部分組立体である。他方、ひとたび構築要素／部分組立体に拒否が与えられると、分解における次の反復まで、拒否状態から離れることができない。すべての構築要素／部分組立体が負の重みを得た場合、プロセスは、絶対値が最小の負の合計の重みを有する構築要素を選択することができる。代替的に、プロセスは、１つまたは複数の反復をバックトラックし、異なる構築要素／部分組立体を選択するよう試み、ユーザ対話を要求し、または別の適切な方法に進むことができる。
【０１０５】
上記の重み付けスキームは、各ステップにおいて拒否から無縁の少なくとも１つの構築要素／部分組立体が存在する分解が見出された場合、高品質の構築要素をもたらすことが分かった。
【０１０６】
重み関数の多くの例が、以下でより詳細に説明される。
【０１０７】
分離戦略：
重み関数の一例は、分離される構築要素／部分組立体が物理的に接近可能であり、モデルの残りの部分から分離可能であるかどうかを判定する。この目的を達成するため、重み関数は、以下の２つの要件の１つまたは複数が満たされるかどうかを確認する。
【０１０８】
１）構築要素／部分組立体がそれに沿って分離可能／結合可能なすべての方向は平行である。したがって、この重み関数は、例えば、結合グラフ内の対応するノードおよび／またはエッジに関連する属性に基づいて、構築方向および／または構築要素のすべての結合の結合方向を決定することができる。すべての方向が平行である場合、構築要素は、平行移動によって分離することができる。例えば、図８ａの構築要素８０３は、平行ではない２つの結合方向を有する。それらは、回転軸８０２と、構築要素８０４に結合される。構築要素８０３の回転軸８０２からの除去は、回転軸８０２に沿った方向の構築要素８０３の移動を必要とするので、回転軸８０２に対する結合は、回転軸８０２に平行な関連する方向を有する。他方、構築要素８０４に対する結合は、回転軸に直交する、すなわち、構築要素８０４の上面から突出する瘤の方向を向いた方向を有する。したがって、構築要素８０３の除去は、モデルに歪みを引き起こすことがあり、例えば子要素についてなど、モデルの他の結合を同時に分離することなしには実行するのが困難なことがある。図１２は、分離可能なそれぞれの方向が矢印によって示された構築要素の例を示している。
【０１０９】
２）結合方向における構築要素／部分組立体の移動は、モデルの他の構築要素との衝突を引き起こさない。例えば、重み関数は、構築要素／部分組立体のバウンディング・ボックスを決定することができ、結合方向における所定の距離にわたるバウンディング・ボックスの平行移動が別の構築要素との衝突／交差を引き起こすかどうかを判定することができる。図１３は、構築要素１３０１が分離可能な方向に沿って距離ｄだけ可動であるモデルを示している。代替的に、重み関数は、結合方向において引き延ばされた構築要素／部分組立体の幾何学的形状を計算することができ、引き延ばされた幾何学的形状が他のいずれかの構築要素／部分組立体と衝突するかどうかを判定することができる。構築要素がどれだけの空間を占めるかは、単純な幾何学的体積によって表すことができる。例えば、例えば図４に示されるような２×４の瘤を有する構築要素は、それを９つの衝突ボックス（ｃｏｌｌｉｓｉｏｎ  ｂｏｘ）と関連付けることができ、１つの衝突ボックスは、８つの瘤を除く構築要素全体を満たし、８つの瘤は、各々の衝突ボックスを満たす。この情報は、構築要素が衝突するか／重なり合うかどうかを推定するために利用することができる。衝突ボックス情報は、構築要素を分離するために必要な空間を表す引き延ばされた形／形状／幾何学的形状を計算するために利用することができる。
【０１１０】
引き延ばされた幾何学的形状／形／形状をどのように計算するかの例は、構築要素を分離できる、ベクトルｄである方向を見出すことを含むことができる。構築要素は、Ｎ個の衝突体積（例えば、上記の２×４の瘤を有する構築要素の例ではＮ＝９）と、位置（ｘ，ｙ，ｚ）を有する。
【０１１１】
構築要素ＢＥ、ベクトルｄ、およびモデルＭを有する場合、分離プロセスは、以下のステップを含むことができ、ＢＥ内のすべての衝突体積ｋについて、ｐ１は、ｋの位置を表す。ｐ２は、ＢＥがｐ１からベクトルｄに沿って移動させられたときのｋの位置を表す。すべての衝突体積は８個の角を有するボックスであるので、ｐ１には８個の点が存在し、ｐ２には８個の点が存在する。点集合には、合計で１６個の点が存在する。衝突体積が凸形である場合、この点集合は、凸図形ｆを構成する。
【０１１２】
プロセスは、図形ｆがモデルＭに属するいずれかの構築要素と衝突するかどうかをテストする。図形ｆがモデルＭに属するいずれかの構築要素と衝突する場合、構築要素ＢＥを分離することはできない。図形ｆがモデルＭ内のどの構築要素とも衝突しない場合、プロセスは、次の衝突体積をテストすることができる。
【０１１３】
最後に、Ｎ個の衝突体積からなる図形ｆのいずれもが、モデルＭに属するどの構築要素とも衝突しない場合、分離戦略に従って、構築要素ＢＥを分離することができる。
【０１１４】
この戦略の効果は、構築要素／部分組立体の分解（したがって逆組立）が、モデルに物理的歪みを与えることなく物理的に可能であることを、少なくとも近似的に保証することである。
【０１１５】
重み関数の以下の例は、物理的に分離可能（または少なくともあまり容易）ではない構築要素／部分組立体の分離を回避する。
【０１１６】
ｘについて上記の条件１）および２）の少なくとも一方が満たされない場合、Ｗｅｉｇｈｔ（ｘ）＝−１とし、
それ以外の場合、０とする。
【０１１７】
関節戦略：
上で言及されたように、その除去がモデルを２つ以上の独立部分に分割させる構築要素／部分組立体は、関節構築要素／部分組立体と呼ばれる。関節構築要素／部分組立体の分離は、構築説明の３Ｄ描画において互いに対して浮かんで／漂っているように見える独立要素／部分組立体を示す構築説明をもたらすことができる。これは分解を複雑にし、それによって、構築説明も複雑にするので、望ましくないことがある。
【０１１８】
以下の重み関数は、関節構築要素／部分組立体の分離を回避する。
【０１１９】
ｘが関節構築要素／部分組立体である場合、Ｗｅｉｇｈｔ（ｘ）＝−１とし、
それ以外の場合、０とする。
【０１２０】
したがって、関節構築要素は、強く冷遇され、そのようにして、構築要素／部分組立体が漂うことを回避する。
【０１２１】
一代替実施形態では、重み関数は、ｘが関節構築要素／部分組立体である場合、中立の重み、例えば、ｗｅｉｇｈｔ＝０を割り当て、ｘが関節構築要素／部分組立体でない場合、正の重み、例えば、ｗｅｉｇｈｔ＝１を割り当てる。したがって、この実施形態では、関節要素の分離は、冷遇も優遇もされない。これは、重み付けスキームを異なる所望の効果に適合させるために、異なる重みに調整できることを示す。また別の実施形態では、重み関数が個々の構築要素に対して計算されるか、それとも部分組立体に対して計算されるかに応じて、異なる重みが割り当てられる。例えば、一実施形態では、ｘが部分組立体である場合、関節部分組立体であれば、ｗｅｉｇｈｔ（ｘ）は−１に設定され、ｘが関節部分組立体でなければ、０に設定され、一方、ｘが個々の構築要素である場合、関節構築要素であれば、ｗｅｉｇｈｔ（ｘ）は０に設定され、それ以外の場合、＋１に設定される。したがって、この実施形態では、関節部分組立体の分離は防止され、一方、関節構築要素の分離は単に冷遇される。
【０１２２】
統合戦略：
残りの部分モデルにおいて分離された（すなわち「漂う」）構築要素／部分組立体を回避することが可能でない状況が存在する。そのような状況の一例が、構築要素８０３の対応する孔を突き抜ける回転軸８０２上に配置されたギア要素８０１を示す、図８ａに示されている。モデルを分解する場合、回転軸８０２を除去することができるが、その結果、図８ｂに示されるように、ギア要素８０１は、モデルの残りの部分から分離された状態に留まる。
【０１２３】
そのような状況では、分離された要素８０１をできるだけ早くモデルから除去して、図８ｃに示される状況をもたらすことが望ましいことがある。
【０１２４】
分離された要素の迅速な除去は、より少数の他の構築要素に（直接または間接に）結合された構築要素／部分組立体に増加した重みを割り当てる重み関数によって優遇することができる。そのような重み関数の一例は、以下の通りである。
【０１２５】
すべての構築要素／部分組立体ｘについて、Ｗｅｉｇｈｔ（ｘ）＝１／（ｘに結合される構築要素の数＋１）。
【０１２６】
図８ｂの例では、ギア８０１は他のどの構築要素または部分組立体にも結合されていないので、上記の重み関数は、小さなギア８０１に重み１を割り当てる。他方、他の構築要素は、８０３、８０４、８０５で指示される５つの要素を含む組立体の部分であるので、重み１／６を割り当てられる。
【０１２７】
したがって、統合戦略は、回避不可能な「漂う」構築要素または部分組立体が結果の構築説明中に示されているステップの数を減少させる。
【０１２８】
類似性戦略：
類似性戦略は、組立／分解における対称性に関係する。組立プロセスにおいて類似性戦略を利用する場合、組立は対称的になる可能性が高く、それは分解プロセスを簡単にする。これに基づいて分解を実行するため、２つの構築要素ＡおよびＢがどれだけ「類似」しているかを示す関数を以下のように決定することができる。
【０１２９】
重み関数は、ｙ軸が基準構築方向、例えば垂直方向に対応する座標系におけるＡの座標およびＢの座標を決定する。ｘ軸およびｚ軸は、他の主構築方向、例えば水平方向に対応する。
【０１３０】
Ｂが分離される最後の構築要素である場合、ＡおよびＢが類似しているかどうかを判定するための重み関数は、以下の形式を有することができる。
【０１３１】
ａ＋ｂ＋ｃ＝１である、所定の重みａ、ｂ、ｃについて、
Ｗｅｉｇｈｔ（ｘ）＝
ＡおよびＢが同じタイプの構築要素である場合のａと、
ＡおよびＢが座標系において同じｘ座標または同じｚ座標を有する場合のｂと、
ＡおよびＢが同じ属性（色、装飾など）を有する場合のｃと
の和。
【０１３２】
０より高い重みは、何らかの程度の類似性を反映する。代替的および／または追加的基準を考えることもできる。
【０１３３】
この戦略は、最後に分離された構築要素または部分組立体に類似する構築要素／部分組立体を分離することである。この戦略の効果は、対称的な部分を含むモデルがしばしば対称的に分解されることである。
【０１３４】
分解のための類似性戦略の一例が、３つの連続する分解ステップの例を図９ａ）〜図９ｃ）にそれぞれ示した図９に与えられている。モデルの左部分において長方形の構築要素９０１が最初に分離され、その後、最初の長方形の構築要素に対して対称的に配置された類似の長方形の構築要素９０２が分離されることが図９から分かる。次のステップは、モデルの右部分において２つの類似の長方形の構築要素９０３を分離することとすることができる。
【０１３５】
基礎戦略：
大きな板または不規則形状の板のような特別な構築要素または部分組立体は、しばしばモデルの基礎／開始構築要素となり、したがって、最後に分離する構築要素となる。板または他の構築要素が開始構築要素であるかどうかを検査するため、構築要素のタイプおよび／またはサイズは、他の構築要素のタイプ／サイズと比較することができ、または開始構築要素はモデルの基礎を形成するせいでしばしば大きいため、構築要素が大きい場合にそのことを表す閾値と比較することができる。さらに、大きな構築要素がモデル内でどれだけ下方に配置されるかを解析することによって、それが開始構築要素であるかどうかも検査することができる。大きく、モデルの下部に配置される構築要素は、開始構築要素である可能性が高い。この目的を達成するため、結合グラフのノードは、それを構築要素のサイズ／体積を表すそれぞれの属性に関連付けることができる。代替的に、構築説明プロセスは、例えば、マウスまたは別のポインティング・デバイスを用いて開始構築要素を指し示すことによって、ユーザが開始構築要素を指示することを可能にすることができる。したがって、開始構築要素がモデルから除去されることを防止する重み関数は、以下の形式を有することができる。
【０１３６】
ｘが開始構築要素である場合、Ｗｅｉｇｈｔ（ｘ）＝−１とし、
そうでない場合、０とする。
【０１３７】
代替的に、重み関数は、ｘが開始構築要素／部分組立体である場合、重み０を割り当て、そのようにして、ｘの分離が優遇されないことを表すことができ、一方、ｘが開始構築要素／部分組立体でない場合、その場合は分離が優遇されるので、高い正の重み、例えばｗｅｉｇｈｔ＝１を割り当てることができる。
【０１３８】
その効果は、結果の構築説明において、いくつかの共通基礎構築要素または部分組立体が組立プロセスの最初または早期に結合されることである。
【０１３９】
サブステップ整合性戦略：
一実施形態によれば、各候補部分組立体ｘについて、結合の質に反映／寄与する２つの寄与側面が存在する。第１の側面は、部分組立体ｘの構築要素間の内部結合の強度であり、第２の側面は、部分組立体ｘの構築要素間の外部結合の強度である。内部結合が相対的に強く、外部結合が相対的に弱い場合、部分組立体内の構築要素は、その部分組立体内では他の構築要素と強く結合しており、モデルの残りの部分とは弱くしか結合していないので、部分組立体は、容易に除去可能であると予想することができる。それに対応して、組立プロセスの最中、強い内部結合と、モデルの残りの部分との弱い結合を有する部分組立体は、安定した部分組立体として相対的に容易に組み立てることができ、結合プロセスの最中に部分組立体が分解するリスクなしに、モデルの残りの部分に結合することができる。
【０１４０】
部分組立体が内部的にどれだけ強く結合しているか、すなわち、部分組立体の異なる構築要素が互いにどのように結合しているかを調査するため、結合グラフまたはすべての構築要素間の結合の別の適切な表現が使用できる。結合グラフは、例えば、各エッジが、対応する結合の強度を表す、それに関連する属性／重みを有する場合、上述されたような、構築要素間の物理的強度を反映する重みを含むことができる。
【０１４１】
例えば、各構築要素は、構築要素間の結合を提供するために、他の構築要素の対応する結合要素とかみ合わせるための１つまたは複数の結合要素を含むことができる。例えば、図４は、別の構築要素の穴（反瘤（ａｎｔｉ−ｋｎｏｂ）とも呼ばれる）とかみ合うように適合された、瘤の形をした突起を有する構築要素の一例を示している。一般に、構築要素は、結合要素の１つまたは複数の異なるクラスに属する結合要素を有することができ、結合要素の各クラスまたは結合要素クラスの各対は、対応する強度の結合を提供することができる。したがって、２つの構築要素間の結合の合計の強度は、２つの構築要素間の結合に寄与する結合要素／協働する結合要素の対の数、および寄与結合要素のそれぞれのクラス／タイプから決定／推定することができる。例えば、プロセスは、合計の結合強度を獲得するために、個々の結合強度を足し合わせることができる。結合に寄与する結合要素の数およびタイプについての情報は、構築要素モデルのデジタル表現から獲得することができ、ならびに／または結合グラフのノードおよび／もしくはエッジに含まれることができる。結合要素の定義をサポートするデータ構造の例が、ＷＯ０４／０３４３３３で説明されている。
【０１４２】
例えば、構築要素ｘおよびｙの間の結合の強度は、以下のように計算することができる。
【０１４３】
【数１】
2010521727.tif 000003
【０１４４】
すべての結合クラスｃにわたって合計が取られる場合、Ｓｃは、結合クラスｃの結合強度であり、Ｎ（ｃ）は、ｘおよびｙの間の結合に寄与するクラスｃの結合要素の数である。
【０１４５】
瘤／反瘤（または穴）の対、釘、および回転軸の形をとる結合要素を有する、図４に示されるタイプの２つの構築要素ｘおよびｙの間で結合の物理的強度がどのように決定できるかの一例は、以下のように定義することができる。
【０１４６】
Ｓｔｒｅｎｇｈｔ（ｘ，ｙ）＝
結合瘤／反瘤の各対の場合の１と、
各釘の場合の１０と、
各回転軸の場合の５と
の合計。
【０１４７】
上記の例における数値は、一例として提供されたに過ぎないことは理解されよう。
【０１４８】
結合の有効強度は、有効強度の計算がさらに構築要素の幾何学的形状を考慮に入れる場合、はるかに正確に推定することができる。
【０１４９】
例えば、図１０は、２つの部分組立体を示しており、各々は、図４に関連して説明された形の単一の結合要素によって相互結合された２つの構築要素を含んでいる。しかし、図１０ａの部分組立体は良く結合されている、すなわち、分離するのが困難である一方、図１０ｂの部分組立体は、構築要素１００１を基板１００２から除去することはユーザにとって非常に容易であるので、良く結合されていない。プロセスは、結合強度に関して最小／最軽量の構築要素の体積または質量を組み入れることによって、この相違を調整することができる。代替的または追加的に、構築要素の幾何学的特性を表す別の適切な量が使用できる。大きな構築要素は小さな構築要素よりもつかむのが容易であるので、これは、ユーザの指で構築要素をつかむことが、例えばユーザにとってどれだけ容易であるかをシミュレートする。
【０１５０】
したがって、そのような修正された重み関数は、以下のように表すことができる。
【０１５１】
Ｃｏｎｎｅｃｔｉｏｎ（ｘ，ｙ）＝Ｓｔｒｅｎｇｈｔ（ｘ，ｙ）／Ｍｉｎｉｍｕｍ（ｘの体積，ｙの体積）
【０１５２】
そのため、図１０に示される例では、どちらのケースでも、小さな構築要素が１つの瘤／反瘤の対で結合されるので、２つの部分組立体は、構築要素の間に同じ強度を有する。しかし、図１０ａの部分組立体では、最小の構築要素１００３がより小さな体積を有し、一方、図１０ｂの部分組立体では、最小の構築要素１００１がより大きな体積を有し、そのため、関数ｃｏｎｎｅｃｔｉｏｎ（ｘ，ｙ）は、図１０ａの部分組立体の場合に最大になる。
【０１５３】
上記の結合尺度に基づいた重み関数の一例は、以下のようにすることができる。
【０１５４】
ｘが部分組立体であり、その最弱内部結合＜内部閾値である場合、Ｗｅｉｇｈｔ（ｘ）＝−１であり、
ｘが部分組立体であり、その最強外部結合＞外部閾値である場合、−１であり、
それ以外の場合、０である。
【０１５５】
内部結合および外部結合の閾値は、所定とすること、ユーザ制御とすること、経験的に見出すこと、またはそれ以外の方法で適切に設定することができる。
【０１５６】
閾値の調整は、結果の構築説明におけるサブステップの数量および質を規制する効果的な方法である。閾値を相対的に高い値に設定することによって、より低品質の多数の候補部分組立体を獲得する代わりに、高品質の少数の候補部分組立体を獲得することができる。これは、分解プロセスをより容易で、より迅速なものにする。
【０１５７】
最近戦略：
構築要素／部分組立体には、先に分離された構築要素／部分組立体からの距離に従って、重みを割り当てることもできる。より具体的には、ｗｅｉｇｈｔ（ｘ）は、ｘの質量中心から先に分離された構築要素／部分組立体の質量中心までの距離、平方距離、または別の適切な距離尺度の関数とすることができる。質量中心の代わりに、構築要素／部分組立体の別の適切な基準点が使用できることが理解されよう。
【０１５８】
先に分離された構築要素／部分組立体により近い構築要素に、より高い重みを与えることができる。構築要素が少なくとも１点で互いに接触している場合、それらの間の距離は、ゼロに設定することができる。最近戦略は、図１１ａおよび図１１ｂにそれぞれ示されるような、互いに隣接する構築要素、角で互いに接触するだけの面および構築要素を区別することができる。したがって、一実施形態では、重み関数は、２つの構築要素間の隣接領域のサイズの増加関数とすることができる。構築要素が互いに隣接するか、それとも他の方法で互いに接触するかは、バウンディング・ボックスまたはデジタル表現の一部として保存された他の幾何学的情報に基づいて、決定することができる。そのような尺度を近似する方法は、それぞれの構築要素の点の間の最大距離を計算することによる。この距離が大きくなるほど、図１１によって示されるように、隣接領域は一般に小さくなる。
【０１５９】
積み重ね戦略：
モデルを構築する場合、底部から上に向かって構築するのがしばしば好ましい。したがって、モデル内の最低構築要素からの距離に従って、構築要素／部分組立体に重みを割り当てることができる。構築要素／部分組立体が底部から遠く離れているほど、分解プロセス内でより高い重みが割り当てられる。したがって、一般に、重み付け関数は、座標系の１つまたは複数の方向に沿った、構築要素の座標の増加関数とすることができる。
【０１６０】
したがって、上では重み関数の多くの例が説明されたが、その各々は、対応するモデル分解戦略に対応する。分解プロセスは、代替または追加の重み関数、および／または代替または追加の分解戦略を含み得ることが理解されよう。さらに、代替および／または追加の重み関数は、本明細書で説明される分解戦略に対応して定義することができる。
【０１６１】
本明細書で説明される戦略のいくつかは、結果の１つまたは別の側面を増進するために変更できる１つまたは複数のパラメータを有し、それによって、フレームワークを、ブラックボックスの代わりに、人との対話によって構築説明を生成するためのツールにすることがさらに理解されよう。
【０１６２】
発明者らは、構築分解の整合性を保証する際に、以下の戦略に対応する重み関数の組み合わせを用いて特に良好な結果を獲得した。それらは一緒になって、ユーザ対話を必要とせずに良好な結果を提供する自動構築説明ジェネレータの一実施形態のバックボーンを形成することができる。
【０１６３】
−分離戦略：構築要素または部分組立体の幾何学的形状および結合が与えられた場合、物理的に除去することが可能な構築要素または部分組立体だけを分離することを許可にする。
−サブステップ整合性戦略：内部的に強く結合され、外部的に弱く結合された組立体だけを分離することを許可にする。正確な要件は、上述されたように、所望の質のサブステップを保証するために変更することができる。
−関節戦略：モデルを２つ以上の分離された組立体に分割しない部分組立体だけを分離することを許可にする。さらに、モデルを２つ以上の分離された部分組立体に分割する個々の構築要素を分離することを冷遇する。
−統合戦略：個々の関節構築要素が除去された場合、分離された構築要素または部分組立体をできるだけ速やかに除去する。
【０１６４】
一実施形態では、上で言及された分離、サブステップ統合、関節、および統合の４つの戦略は、すべての組立／分解のために使用されるのに対して、１つまたは複数のさらなる戦略、例えば、本明細書で説明された残りの戦略の１つまたは複数、例えば、類似性、基礎、最近、および積み重ねは、異なる状況において結果を調整するために使用することができる。そのような戦略は、ユーザによって選択可能とすることができる。
【０１６５】
図４は、構築要素およびその結合要素の一例を示している。特に、図４は、構築要素４０１の斜視図を示している。構築要素４０１は、８つの瘤４０３ａ〜４０３ｈを備える上面４０２を有し、それらの瘤は、別の構築要素の対応する穴、例えば、別の構築要素の底面の穴とかみ合わせることができる。それに対応して、構築要素４０１は、対応する穴を備える底面（図示されず）を含む。構築要素４０１はさらに、どのような結合要素も含まない側面４０４を含む。
【０１６６】
一般に、結合要素は、異なるクラスの結合要素、例えば、コネクタ、レセプタ、および混合要素にグループ化することができる。コネクタは、別の構築要素のレセプタによって受け入れることができ、それによって、構築要素間の結合を提供する結合要素である。例えば、コネクタは、別の要素の部分との間で、穴などにはめ込むことができる。レセプタは、別の構築要素のコネクタを受け入れることができる結合要素である。混合要素は、一般に他の構築要素の協働する結合要素のタイプに応じて、レセプタおよびコネクタの両方として機能できる部分である。
【０１６７】
図４に示されたタイプの構築要素は、ＬＥＧＯという名称の下で入手可能であり、多種多様な形状、サイズ、および色をとる。さらに、そのような構築要素は、様々な異なる結合要素を備えたものが入手可能である。上記の構築要素は、可能な構築要素の例として提供されたに過ぎないことが理解されよう。
【０１６８】
図５は、構築要素モデルをデジタル的に表現するためのデータ構造の一実施形態を示している。データ構造５０１は、モデル全体に関係するグローバル・モデル・パラメータを含む１つまたは複数のデータ・レコード５０２を含むことができる。そのようなモデル・パラメータの例は、モデル名、モデル作成者の名前、モデリング・アプリケーションのプログラム・バージョン番号、作成日付などを含む。モデル・データ構造５０１はさらに、構築要素データ・レコードのリスト５０３または他の適切な構造を含む。図５の例では、リストは、Ｎ個のデータ・レコード「構築要素１」、「構築要素２」、．．．、「構築要素Ｊ」、．．．、「構築要素Ｎ」を含む。リスト５０３の各構築要素データ・レコードは、「構築要素Ｊ」のデータ構造５０４によって示される構造を有する。
【０１６９】
詳細には、各構築要素データ・レコードは、構築要素のタイプに対応する識別子を示す構築要素ＩＤ  ５０５を含む。構築要素ＩＤは、構築要素または構築要素のタイプの特性を一意的に識別することができる。
【０１７０】
構築要素データ・レコードはさらに、色、テクスチャ、装飾など、構築要素の１つまたは複数の属性を表す多くの構築要素属性５０６を含むことができる。
【０１７１】
さらに、構築要素データ・レコード５０４は、構築要素の内部座標系の位置および向きをそれぞれ表すデータ項目５０７および５０８を含む。構築要素の位置および向きは、グローバル「ワールド」座標系に関する構築要素の内部座標系の原点の座標と、グローバル座標系に関する内部座標系の向きによって定義される。
【０１７２】
座標系の階層を含む構築要素モデルを保存するためのデータ形式の一例が、米国特許第６，３８９，３７５号で開示されている。
【０１７３】
さらに、構築要素データ・レコード５０４は、構築要素の他の構築要素との結合特性を検出する際に使用される、構築要素の１つまたは複数のバウンディング・ボックスおよび結合データをそれぞれ表すデータ項目５０９および５１０を含むことができる。図４に示された構築要素のタイプに関する結合データの表現の一実施形態は、構築要素のバウンディング・ボックスの表面によって定義される平面を表すデータ構造を含む。構築要素の結合要素は、各結合要素がそれに関連する軸を有するように、これらの平面上に配置される。同じ平面内のすべての結合要素の軸は、規則的な格子、例えば、隣接格子点間の距離が固定された直交格子のそれぞれの格子点に対応する。図４の構築要素４０１に関連する平面は、対をなす平面が互いに平行であり、それらは、構築要素の上面および底面に対応する１組の水平面と、構築要素の側面に対応する多くの垂直面を含む。隣接格子点間の距離は、すべての水平面内で同じとすることができる。いくつかの実施形態では、垂直面内の隣接格子点間の距離は、水平面内の隣接格子点間の距離と異なる。図４に示されたタイプの構築要素に関する結合特性のデジタル表現が、ＷＯ０４／０３４３３３に開示されており、同文献は、参照によりその全体が本明細書に組み込まれる。
【０１７４】
デジタル表現は、例えば、バイナリ・ファイル、または所定のモデリング記述言語によるテキスト・ファイルなどのような、任意の適切なデータまたはファイル形式で符号化できることが理解されよう。デジタル情報の他の実施形態は、代替的もしくは追加的データ構造を利用でき、および／または代替的もしくは追加的モデル・データを表現できることがさらに理解されよう。
【０１７５】
図６は、構築説明アプリケーション・プログラムのグラフィカル・ユーザ・インタフェースの一実施形態を示している。ユーザ・インタフェースは、１組の段階的な構築説明のうちの一ステップのグラフィカル表現を図示する表示領域７０１を含む。グラフィカル表現は、所定のカメラ位置から示された部分モデル７０２の３Ｄビューを示す。部分モデル７０２は、完成モデルのすべての構築要素の部分集合からなり、その部分集合は、最初に配置される構築要素を含む。表示領域７０１はさらに、直近に配置された構築要素、すなわち、先行するステップの部分モデルから現在の部分モデル７０２を区別する構築要素のグラフィカル表現７０３を含む。この例では、これらは、部分モデル７０２の構築要素７１４、７１５、７１６である。
【０１７６】
ユーザ・インタフェースはさらに、ユーザが段階的な説明のうちのステップのいずれかを選択することを可能にする、マウスを用いた対応するドラッグ操作によって、離散的間隔で移動させることができるスライダ制御要素７０９を含む。図６の例では、説明の各ステップにおいて、３つの新しい構築要素が追加される。
【０１７７】
ユーザ・インタフェースはさらに、グラフィカル表現をそれぞれ順方向および逆方向に順次切り換えること、説明の最初のステップおよび最後のステップにジャンプすること、カメラ位置を変更すること、生成された構築説明を印刷すること、および「自動再生」機能を開始することなど、多くの頻繁に使用される機能をユーザが起動することを可能にするボタン制御要素７０５を含む。自動再生機能は、各部分モデルが所定の期間示されるように、一連の部分モデルを１つずつ表示する。好ましくは、ユーザは、自動再生機能における各部分モデルの表示時間を設定することができる。
【０１７８】
最後に、ユーザ・インタフェースは、ヘルプ機能、カメラ位置を変更するための機能、ズーム機能などの機能をユーザが開始することを可能にする多くのプルダウン・メニュー７０４を含む。さらに、構築説明アプリケーションによって提供される機能は、デジタル表現のローディング、部分モデルのグラフィカル表現を印刷するための印刷機能、および例えば、ＨＴＭＬ形式、またはＴＩＦ、ＪＰＧ、ＢＭＰなどの他の適切なグラフィカル・ファイル形式で、部分モデルのグラフィカル表現の系列をエキスポートするためのエキスポート機能を含む。
【０１７９】
さらに、構築説明アプリケーションによって提供される機能の例は、モデル内のすべての構築要素からなるリストをユーザが表示または印刷することを可能にする材料表（ｂｉｌｌ  ｏｆ  ｍａｔｅｒｉａｌ）機能を含む。
【０１８０】
図１４は、構築説明生成の別の実施形態のフローチャートを示している。ステップＳ１において、プロセスは、例えば、図２のステップＳ１に関連して説明されたように、構築要素モデルのデジタル表現Ｍを受け取る。
【０１８１】
逐次的ステップＳ２〜Ｓ１２において、構築説明アプリケーションは、ロードされたデジタル表現から構築説明２０５を生成する。生成された構築説明２０５は、図２に関連して説明されたような形式をとることができる。
【０１８２】
ステップＳ２において、プロセスは、プロセスを初期化する。詳細には、プロセスは、生成される組立系列を保持するためのデータ構造Ｒｅｓｕｌｔを初期化する。プロセスは、空系列となるように、系列Ｒｅｓｕｌｔを初期化する。プロセスはさらに、モデルＭ内のすべての構築要素および部分組立体からなる集合となるように、Ｃａｎｄｉｄａｔｅｓで表される候補構築要素の集合を初期化する。したがって、先の実施形態におけるように、プロセスは、モデルＭから除去する複数の候補部分組立体を決定することができ、生成された構築要素として部分組立体を扱うことができる。候補部分組立体は、モデルがどのように分離／切断できるかについての決定である１組の選択基準を用いて見出す／選択することができる。そのような選択基準の例は、上でより完全に説明されており、特に、選択基準の第２の組が、図３のステップ３０３に関連して説明された。他の実施形態では、プロセスは、構築要素だけを考慮できることが理解されよう。
【０１８３】
ステップＳ３において、プロセスは、集合Ｃａｎｄｉｄａｔｅｓが空であるかどうか、すなわち、すべての構築要素が処理されたかどうかを判定する。これが成り立つ場合、プロセスは、ステップＳ１２に進み、それ以外の場合、プロセスは、ステップＳ４に進む。
【０１８４】
ステップＳ４〜Ｓ１１において、プロセスは、新しい部分モデルをもたらす組立ステップｂを見出すことができ、完全なモデルＭがこの新しい部分モデルにまで分解できるかどうかを判定する。
【０１８５】
詳細には、ステップＳ４において、プロセスは、集合Ｃａｎｄｉｄａｔｅｓのコピーとして、構築要素および部分組立体からなる補助集合（ａｕｘｉｌｉａｒｙ  ｓｅｔ）Ｃを生成する。
【０１８６】
ステップＳ５において、プロセスは、集合Ｃが空であるかどうか、すなわち、候補ｂが識別されたかどうかを判定する。これが成り立つ場合、プロセスはステップＳ３に復帰し、それ以外の場合、プロセスはステップＳ６に進む。
【０１８７】
ステップＳ６において、プロセスは、集合Ｃから候補構築要素ｂまたは候補部分組立体を選択する。
【０１８８】
本実施形態における候補の選択は、先の実施形態の分解ケースにおける除去される構築要素の選択と類似した方法で、すなわち、１組の選択基準を用いて、行うことができる。詳細には、選択基準は、上述された重み関数、特に、図３のステップ３０４に関連して説明された選択基準の第１の組の重み関数の１つまたは複数など、異なる構築戦略を表す１つまたは複数の重み関数に基づくことができる。いくつかの重み関数は、例えば、上でより詳細に説明された重み関数のように、それぞれ組立バージョンおよび分解バージョンにおいて同一またはほとんど同一である。例えば、１つの戦略は、先行するステップにおいて追加された構築要素からの距離に従って、重みを構築要素に割り当てることができる。その場合、プロセスは、先に追加された構築要素に最も近い構築要素を選択することができる。他の重み関数は、まったく異なるものとすることができる。例えば、上述された分解ケースにおける「関節戦略」は、結合グラフの分裂を回避するが、本実施形態の組立ケースでは、それは、先に選択されたいずれかの構築要素に実際に結合する構築要素が選択されることを保証するに過ぎない。それにも関わらず、どちらのケースでも、「漂う」構築要素は回避される。本明細書で説明される重み関数は、単一構築要素ばかりでなく、部分組立体（疑似構築要素）を重み付けることができるので、組立プロセスおよび分解プロセスの両方は、部分組立体を扱うように生成することができる。純粋な分解ケースにおけるように、これは実際的なばかりでなく、時には望ましくもある。
【０１８９】
代替的または追加的に、候補の選択は、ユーザ入力／対話に部分的または完全に基づくことができる。例えば、プロセスは、候補ｂを表すユーザ入力を受け取ることができる。代替的に、プロセスは、例えばランダムにまたは上述の重み関数に基づいて、１つまたは複数の可能な候補を選択することができ、その候補をユーザに通知することができる。その場合、プロセスは、１つまたは複数の提案された候補に対する承認または拒否を表すユーザ入力を受け取ることができる。
【０１９０】
ステップＳ７において、プロセスは、モデルの受け取ったデジタル表現から、現在の組立系列Ｒｅｓｕｌｔと選択された候補ｂの合併によって獲得可能な残余モデルまでの部分分解系列を生成する。分解系列は、モデルの構築要素および／または部分組立体の逐次的リストの形式で生成することができる。プロセスはさらに、逐次的リストのうちの部分組立体のための下位分解系列を生成することができる。一実施形態では、プロセスは、ステップからなる枝分かれしたツリーとして分解系列を表し、各枝は下位構築分解を含むことができる。部分分解系列を生成するためのプロセスの一実施形態が、以下でより詳細に説明される。
【０１９１】
ステップＳ８において、プロセスは、分解系列を見出すことができたかどうかを判定する。ステップＳ７の分解プロセスが分解系列を決定することに成功した場合、プロセスはステップＳ９に進み、それ以外の場合、プロセスはステップＳ１０に進む。
【０１９２】
ステップＳ９において、プロセスは、集合Ｃａｎｄｉｄａｔｅｓ、Ｒｅｓｕｌｔ、およびＣを更新する。詳細には、プロセスは、（成功した候補が識別されたので）選択された候補ｂを現在の結果系列Ｒｅｓｕｌｔに追加し、候補ｂを候補の集合Ｃａｎｄｉｄａｔｅｓから除去し、すべての要素を補助集合Ｃから除去する。その後、プロセスはＳ５に復帰する。
【０１９３】
ステップＳ１０において、プロセスは、まだ試みられていない候補からなる補助集合Ｃからｂを除去する。ステップＳ１１において、プロセスは、Ｃ内にまだ候補が残っているかどうかを判定する。これが成り立つ場合、プロセスは、ステップＳ５に復帰して、代替候補を識別し、それ以外の場合、プロセスは、組立構築説明の生成が失敗したことを、例えば適切なエラー・フラグまたはメッセージを用いて通知して、終了する。例えば、この状況は、モデルが過剰に制約されている場合、および／またはモデルの構築制約を表す、分解プロセスの最中に使用される重み関数が強過ぎる／制約的であり過ぎる場合、生じることがある。したがって、そのような場合、分解プロセスで使用される重み関数の一部または全部は、例えば自動的にまたはユーザ対話によって、緩和する／弱めることができ、プロセスは、緩和された重み関数を用いて、再スタートすることができる。
【０１９４】
ステップＳ１２において、プロセスは、生成された組立系列Ｒｅｓｕｌｔから、例えば部分モデルの画像または他の表現の系列として構築説明を生成し、各部分モデルでは、先行する部分モデルと比較して、生成されたリストＲｅｓｕｌｔに属する構築要素および部分組立体の１つまたは複数が追加されている。プロセスは、本明細書で説明されるように、任意の適切な形式で、生成された説明を保存することができ、および／またはそれらを出力することができる。
【０１９５】
図１５は、残余モデルＮへのモデルＭの部分分解プロセスの一例のフローチャートを示している。分解プロセスは、モデル内のすべての構築要素を含む完成モデルＭのデジタル表現に基づいて、モデルＭを分解する（ステップ３０１）。モデルＭの入力は、構築要素のサイズ／寸法、瘤の数、蝶番、釘、回転軸のような特別な特徴など、個々の構築要素についての情報を含む。デジタル表現はまた、例えば、適切な座標系に関する構築要素のそれぞれの（ｘ，ｙ，ｚ）位置を指定することによって、モデル内のどこに各構築要素が配置されるかについての情報も含む。プロセスはさらに、残余集合Ｎについて、すなわちモデルＭのサブモデルについての情報を受け取る。部分分解プロセスは、分解ステップの系列を生成し、各分解ステップにおいて、残余モデルＮだけが残っているようになるまで、Ｍ＼Ｎの１つまたは複数の構築要素（すなわち、残余モデルＮに含まれないモデルＭの構築要素）が除去される。
【０１９６】
ステップ３０２において、分解プロセスは、分離されるモデルＭ＼Ｎ（または先行する反復からもたらされた部分モデルＭ’＼Ｎ）内に構築要素が残っているかどうかをテストする。モデル内に除去される構築要素がまだ存在する場合、プロセスは、ステップ３０３に進み、モデルＭ＼Ｎ（または先行する反復からもたらされた部分モデルＭ’＼Ｎ）から除去するために１つまたは複数の候補部分組立体を選択／生成する。候補部分組立体は、相互結合構築要素を含む。後続するステップ３０４において、プロセスは、例えば、図３に関連して説明されたように、所定の選択基準の第１の組に従って、分離される構築要素または生成された候補部分組立体の１つ（Ｅ）を選択する。ステップ３０３における候補部分組立体は、モデルがどのように分離／切断できるかについての決定である選択基準の第２の組を用いて、見出す／選択することができる。そのような選択基準の例は、上でより完全に説明された。
【０１９７】
ステップ３０５において、プロセスは、ステップ３０４において選択された構築要素または部分組立体Ｅをモデルから分離し、すなわち、選択された候補部分組立体のすべての構築要素のうちの選択された構築要素が除去された新しい部分モデルＭ’＝Ｍ＼Ｅを生成する。プロセスは、分解系列を表すデータ構造を維持することができ、分離される部分組立体／構築要素についての情報を用いてデータ構造を更新することができる。
【０１９８】
プロセスが、分離される部分組立体を選択した場合、反復的分解プロセスを継続するためにステップ３０２に復帰して、残りの部分モデル、すなわちモデルＭ’＼Ｎ＝Ｍ＼（Ｅ∪Ｎ）から分離する次の構築要素を見出す前に、選択された部分組立体は、ステップ３０７において再帰的方式で（すなわち、選択された部分組立体Ｅおよび残余モデルＮを入力として利用して）分解プロセスを実行することによって分解することができる。
【０１９９】
やはり残余モデルＮの一部でない、モデルＭから除去される構築要素がもはや存在しない場合、残余モデルＮへのモデルＭの部分分解は完了し、分解プロセスはステップ３０８において停止する。
【０２００】
したがって、一般に、与えられたモデルＭについて、ＭがＮに分解できるならば、ＮはＭに組み立て得ることが分かった。言い換えると、ステージＮにおける組立は、完全なモデルＭがＮにまで分解できる場合（およびその時に限って）、組立ステップの系列中の適切な中間モデルである。
【０２０１】
図１４および図１５に関連して説明された組立系列を生成するためのプロセスの実施形態は、以下の疑似コードによって表すことができる。
【０２０２】
Ｃｏｎｓｔｒｕｃｔ  ｍｏｄｅｌ  Ｍ：
ＣａｎｄｉｄａｔｅｓをＭ内のすべてのブロックおよび部分組立体からなる集合とする
Ｒｅｓｕｌｔをブロックからなる空系列とする
Ｗｈｉｌｅ（Ｃａｎｄｉｄａｔｅｓは空でない）
ＣをＣａｎｄｉｄａｔｅｓのコピーとする
Ｗｈｉｌｅ（Ｃは空でない）
ｂをＣに属するブロックとする
Ｉｆ（Ｍを（Ｒｅｓｕｌｔとｂの合併）まで分解する）
Ｃからすべてのブロックを除去する
Ｃａｎｄｉｄａｔｅｓ＝Ｃａｎｄｉｄａｔｅｓ＼ｂ
ｂをＲｅｓｕｌｔに追加する
Ｅｌｓｅ
Ｃからｂを除去する
Ｉｆ（Ｃは空である）
Ｅｒｒｏｒ：「組立は可能でなかった」
Ｆａｌｓｅを返す
【０２０３】
Ｄｅｃｏｎｓｔｒｕｃｔ  ｍｏｄｅｌ  Ｍ  ｄｏｗｎ  ｔｏ  Ｎ：
ＣａｎｄｉｄａｔｅｓをＭ／Ｎ内のすべてのブロックからなる集合とする；
Ｗｈｉｌｅ（Ｃａｎｄｉｄａｔｅｓは空でない）      Ｄを分離可能なＣａｎｄｉｄａｔｅｓの部分集合とする
Ｉｆ（Ｄは空である）        Ｆａｌｓｅを返す；
Ｅｌｓｅ
ｂをＤに属する「最良分離可能」ブロックとする；
Ｃａｎｄｉｄａｔｅｓからｂを除去する；
Ｔｒｕｅを返す；
【０２０４】
上記の疑似コードにおいて、「最良分離可能」ブロックの選択は、上記のステップ３０４において実行される選択、すなわち、１組の所定の選択基準、例えば上述された選択基準のうちの１つまたは複数に基づいた選択に対応する。
【０２０５】
プロセスの一実施形態はまた、以下の疑似コードによっても表すことができ、この実施形態のフローチャートが、図１６に示されている。
【０２０６】
Ｃｏｎｓｔｒｕｃｔ  ｍｏｄｅｌ  Ｍ：
ＣａｎｄｉｄａｔｅｓをＭ内のすべてのブロックおよび部分組立体からなる集合とする
Ｒｅｓｕｌｔをブロックからなる空系列とする
Ｗｈｉｌｅ（Ｃａｎｄｉｄａｔｅｓは空でない）
ＣをＣａｎｄｉｄａｔｅｓのコピーとする
Ｉｆ（Ｆｉｎｄ  ｃｏｎｓｔｒｕｃｔｉｏｎ  ｓｔｅｐ  ｂ  ｆｒｏｍ  Ｃ）
ｂをＲｅｓｕｌｔに追加する
Ｃａｎｄｉｄａｔｅｓ＝Ｃａｎｄｉｄａｔｅｓ＼ｂ
Ｅｌｓｅ
Ｅｒｒｏｒ：「組立構築説明は可能でない」
Ｆａｌｓｅを返す
Ｔｒｕｅを返す
【０２０７】
Ｆｉｎｄ  ｃｏｎｓｔｒｕｃｔｉｏｎ  ｓｔｅｐ  ｂ  ｆｒｏｍ  Ｃ：
Ｗｈｉｌｅ（Ｃは空でない）
ｂをＣに属する「良好」ブロックとする
Ｉｆ（Ｍを（Ｒｅｓｕｌｔとｂの合併）まで分解する）
Ｔｒｕｅを返す
Ｅｌｓｅ
Ｃからｂを除去する
Ｆａｌｓｅを返す。
【０２０８】
したがって、この実施形態では、次の組立ステップｂが見出され得るかどうかについての判定は、別個の関数として実施される。図１６ａは、全体的なプロセスを示しており、一方、図１６ｂは、可能／有効な次の組立ステップを識別する関数の一例のフローチャートを示している。
【０２０９】
プロセスは、図１４に関連して説明されたように、入力ステップＳ１および初期化ステップＳ２で開始する。ステップＳ３において、プロセスは、集合Ｃａｎｄｉｄａｔｅｓが空であるかどうか、すなわち、すべての構築要素が処理されたかどうかを判定する。これが成り立つ場合、プロセスは、ステップＳ１２に進んで、上述されたように、構築説明を生成し、それ以外の場合、プロセスは、ステップＳ４に進む。
【０２１０】
ステップＳ４において、プロセスは、集合Ｃａｎｄｉｄａｔｅｓのコピーとして、構築要素および部分組立体からなる補助集合Ｃを生成する。
【０２１１】
ステップＳ２０において、プロセスは、有効な次の組立ステップｂを見出し得るかどうかを判定する。これが成り立つ場合、プロセスは、識別されたステップｂをＲｅｓｕｌｔｓデータ構造に追加し、対応する構築要素（または部分組立体）をＣａｎｄｉｄａｔｅｓデータ構造から除去することによって、ＲｅｓｕｌｔｓおよびＣａｎｄｉｄａｔｅｓのデータ構造を更新し、その後、プロセスは、ステップＳ３に復帰する。有効な組立ステップを見出すことができない場合、プロセスは、図１４に関連して説明されたように、組立構築説明の生成が失敗したことを、例えば適切なエラー・フラグまたはメッセージを用いて通知して、終了する。
【０２１２】
図１６ｂは、ステップＳ２０を実施するサブプロセスの一例のフローチャートを示している。最初に、プロセスは、集合Ｃか空であるかどうか、すなわち、すべての候補ｂが処理されたかどうかを判定する。これが成り立つ場合、プロセスは、有効な候補ｂが見出せなかったことを通知する値を返し、それ以外の場合、プロセスはステップＳ６に進む。
【０２１３】
ステップＳ６において、プロセスは、図１４のステップＳ６に関連して説明されたように、集合Ｃから候補構築要素ｂまたは候補部分組立体を選択する。
【０２１４】
ステップＳ７において、プロセスは、図１４のステップＳ７に関連して説明されたように、モデルの受け取ったデジタル表現から、現在の組立系列Ｒｅｓｕｌｔと選択された候補ｂの合併によって獲得可能な残余モデルまでの部分分解系列を生成する。
【０２１５】
ステップＳ７の分解プロセスが分解系列を決定することに成功した場合、プロセスは、プロセスが成功したことを通知する値を返し、それ以外の場合、プロセスはステップＳ１０に進む。
【０２１６】
ステップＳ１０において、プロセスは、まだ試みられていない候補からなる補助集合Ｃからｂを除去し、サブプロセスの先頭に復帰して、Ｃが空であるかどうかを判定する。
【０２１７】
この例では、関数「Ｄｅｃｏｎｓｔｒｕｃｔ  ｍｏｄｅｌ  Ｍ  ｄｏｗｎ  ｔｏ  Ｎ」は、上記の例におけるのと同じ関数とすることができる。
【０２１８】
図１４〜図１６に関連して説明された実施形態では、Ｎ個の構築要素を含むモデルの組立は、Ｎ個の組立ステップを要し、一般に各組立ステップについて、有効な候補ブロックｂを見出すために、数回の分解を実行しなければならないことがある。
【０２１９】
必要な反復の回数は、以下のように、すなわち、Ｎ個のブロックからなる完全な組立構築説明は約Ｎ個の組立ステップを必要とすると推定することができる。各組立ステップは、約Ｎ／２回の分解を必要とすることがある。各分解は、約Ｎ個の分解ステップからなる。各分解ステップは、約Ｎ／２回のブロック重み付けを必要とする。合計で、完全な組立構築説明は、最大で約（Ｎ＾４）／４回の構築要素の重み付けを必要とすることがある。これは、純粋なバックトラッキング探索のために必要とされるｘ＾Ｎ回の重み付けよりはるかに良好である。同様に、図２および図３に関連して説明された完全な分解プロセスは、約（Ｎ＾２）／２回の重み付けを必要とする。
【図１ａ】
2010521727.tif 000004
【図１ｂ】
2010521727.tif 000005
【図２】
2010521727.tif 000006
【図３】
2010521727.tif 000007
【図４】
2010521727.tif 000008
【図５】
2010521727.tif 000009
【図６】
2010521727.tif 000010
【図７】
2010521727.tif 000011
【図８】
2010521727.tif 000012
【図９】
2010521727.tif 000013
【図１０】
2010521727.tif 000014
【図１１】
2010521727.tif 000015
【図１２】
2010521727.tif 000016
【図１３】
2010521727.tif 000017
【図１４】
2010521727.tif 000018
【図１５】
2010521727.tif 000019
【図１６】
2010521727.tif 000020
【国際調査報告】
2010521727.tif 000021
2010521727.tif 000022
2010521727.tif 000023