(57)【要約】（ａ）オブジェクトの幾何学的配置を記述するデータを記憶する第１記憶手段と、（ｂ）パイオンの集団を作成する初期化モジュールと、（ｃ）中央演算処理装置であって、ペアでコンバットに供されるパイオンの集団の割合を選択する手段と、コンバットに供される各パイオンペアにおいて各パイオンの特性を評価する比較および計算手段と、トーナメントの各セッションにおいて勝ちまたは負けを有するコンバットに供されたパイオンペアのパイオンを同定するマーク付け手段と、探索的変異をもたらす少なくとも１つのオペレータ、および、少なくとも１つの再定義オペレータの協力によって、進化のために少なくとも１つのコンバットに供されたパイオンを生成する繰り返し手段と、抽出モジュールとを少なくとも備えた中央演算処理装置とを備えた、複数のデジタルシミュレーション化オブジェクトの間で近接領域を同定するシステム。【選択図】  図２６
2008507056.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも第１デジタルシミュレーション化オブジェクトと第２デジタルシミュレーション化オブジェクトとの間の近接領域を同定する方法であって、当該方法は、
（ａ）第１デジタルシミュレーション化オブジェクトおよび第２デジタルシミュレーション化オブジェクトの各々の幾何学的配置を記述するデータを提供し、当該データをメモリ内に格納するステップと、
（ｂ）各第１オブジェクトおよび第２オブジェクトの各上記幾何学的配置に属する点として定義される第１核子および第２核子それ自体によって各々が定義される、パイオンと呼ばれるＮ個体のセットから構成される集団を作成するステップと、
（ｃ）上記作成された集団のＮパイオンに関するトーナメントのセッションを体系化するステップであって、当該各セッションの間に、集団の割合は、コンバットに供された各パイオンペアのために、および、適性基準に基づいて定義された特性の評価関数として供され、どのパイオンが勝ちどのパイオンが負けたかを評価しながら、コンバットに供され、勝者および敗者は、上記トーナメントの各セッションの後で異なるマークにより同定される、ステップと、
（ｄ）上記トーナメントの後で、第１セッションの間に負けたパイオンの探索的変異、第２セッションの間に負けたパイオンの交換、および第３セッションの間に負けたパイオンの無作為再定義を実施するステップと、
（ｅ）上記第１オブジェクトと上記第２オブジェクトとの間の近接領域を決定するために使用される上記パイオンを処理するため、上記コンバットの勝者の集団のみを考慮するステップと、
（ｆ）ステップ（ｃ）、（ｄ）および（ｅ）を、再度繰り返し実行するステップと、
（ｇ）上記繰り返し実行の間に、上記パイオン集団の更新された配置から、需要に応じて幾何学的情報を抽出するステップと、
を含むことを特徴とする、近接領域同定方法。
【請求項２】
上記幾何学的情報を抽出するステップの間に、上記同定された近接領域間の上記距離が評価されることを特徴とする、請求項１に記載の方法。
【請求項３】
上記第１のデジタルシミュレーション化オブジェクトと上記第２のデジタルシミュレーション化オブジェクトのうちの少なくとも１つの上記幾何学的配置を記述する空間領域を同定するための上記データは、多面体表示を含むことを特徴とする、請求項１または２に記載の方法。
【請求項４】
上記第１のデジタルシミュレーション化オブジェクトと上記第２のデジタルシミュレーション化オブジェクトのうちの少なくとも１つの上記幾何学的配置を記述する空間領域を同定するための上記データは、ボクセル表示を含むことを特徴とする、請求項１または２に記載の方法。
【請求項５】
上記第１のデジタルシミュレーション化オブジェクトと上記第２のデジタルシミュレーション化オブジェクトのうちの少なくとも１つの上記幾何学的配置を記述する空間領域を同定するための上記データは、パラメータ化された表面を用いる表示を含むことを特徴とする、請求項１または２に記載の方法。
【請求項６】
上記第１のデジタルシミュレーション化オブジェクトと上記第２のデジタルシミュレーション化オブジェクトのうちの少なくとも１つの上記幾何学的配置を記述する空間領域を同定するための上記データは、点郡を用いる表示を含むことを特徴とする、請求項１または２に記載の方法。
【請求項７】
上記パイオン特性を評価するための上記適性基準は、当該パイオンを定義する上記第１核子と上記第２核子の分離距離の測定にあり、上記パイオン特性が、当該測定された距離に反比例するものであることを特徴とする、請求項１〜６のうちのいずれか１項に記載の方法。
【請求項８】
上記パイオン特性を評価するための上記適性基準からなる上記距離測定は、当該パイオンを定義する上記第１核子と上記第２核子の間の距離の二乗を考慮することを特徴とする、請求項７に記載の方法。
【請求項９】
上記第１デジタルシミュレーション化オブジェクトと上記第２デジタルシミュレーション化オブジェクトの各々の上記幾何学的配置を記述するデータを提供するステップ（ａ）の後で、
（ａ１）上記第１オブジェクトおよび上記第２オブジェクト内で幾何学的要素間の近接性を定義する情報を含む連結マップを作成し、当該連結マップの情報をメモリ内に記憶するステップと、
（ａ２）上記第１オブジェクトと上記第２オブジェクトとの間の近接性を定義する情報を含む近接マップを作成し、当該近接マップの情報をメモリ内に記憶するステップと、
をさらに含むことを特徴とする、請求項１に記載の方法。
【請求項１０】
上記トーナメントのセッションの間に負けた上記パイオンを変異させて、当該負けたパイオンに探索的変異をもたらし、上記第１核子および上記第２核子がそれぞれ属している上記第１オブジェクトおよび上記第２オブジェクトの表面上のパイオンの構成要素となる上記第１核子および上記第２核子を移動させることを特徴とする、請求項１〜９のうちのいずれか１項に記載の方法。
【請求項１１】
上記負けたパイオンに探索的変異をもたらすため、上記トーナメントのセッションの間に、上記負けたパイオンを変異させる場合、上記パイオンの構成要素となり、多面体形状で描写された上記第１オブジェクトおよび上記第２オブジェクトのうちの１つに属する、少なくとも１つの上記第１核子および上記第２核子は、メモリ内に記憶された上記近接性を定義する情報を考慮しつつ、別個のファセットの中心からファセットの中心までの一連の動作に供されることを特徴とする、請求項３、９または１０に記載の方法。
【請求項１２】
上記トーナメントの間に勝ったパイオンを変異させる場合、上記パイオンの構成要素となり、多面体形状で描写された上記第１オブジェクトおよび上記第２オブジェクトのうちの１つに属する、少なくとも１つの上記第１核子および上記第２核子は、当該点の開始位置である上記ファセットの中心、および、上記転移に影響されるファセット領域に依存する最大転移振幅である半径を有する円盤上の同じファセットでの動作に供されることを特徴とする、請求項３、９または１０に記載の方法。
【請求項１３】
上記トーナメントの間に勝ったパイオンを変異させる場合、上記パイオンの構成要素となり、多面体形状で描写された上記第１オブジェクトおよび上記第２オブジェクトのうちの１つに属する、少なくとも１つの上記第１核子および上記第２核子は、メモリ内に記憶された上記近接性を定義する情報を考慮しつつ、１つのファセットの１つの頂点から、必ずしも結合されない別のファセットの近くの頂点までの、「ワームホール」形状での動作に供されることを特徴とする、請求項３、９または１０に記載の方法。
【請求項１４】
上記トーナメントの間に勝ったパイオンを変異させる場合、上記パイオンの構成要素となり、三角形ファセットを含む多面体形状で描写された上記第１オブジェクトおよび上記第２オブジェクトのうちの１つにそれぞれ属する、上記第１核子および上記第２核子が位置付けされ、その結果、上記第１核子および第２核子は、当該第１核子および第２核子がそれぞれ属する２つの三角形ファセット間の最小距離を定義するエッジの境界を定めることを特徴とする、請求項３、９および１０に記載の方法。
【請求項１５】
上記負けたパイオンの交換を生じさせる上記トーナメントのセッションの間に、第１の無作為に選択されたパイオンと第２の無作為に選択されたパイオンとの交差によって生じた新パイオンを定義するために、無作為に選択されたパイオンを交差させることにより上記負けたパイオンを交換する場合、上記新パイオンが、上記第１の無作為に選択されたパイオンの第１核子と、上記第２の無作為に選択されたパイオンの第２核子から構成されるとみなされることを特徴とする、請求項１に記載の方法。
【請求項１６】
Ｐデジタルシミュレーション化オブジェクトのセットにＰ≧２で適用される方法を提供する方法であって、当該方法は、
（ａ）上記Ｐグラフィックシミュレーション化オブジェクトの各々の上記幾何学的配置を記述するデータを提供するステップと、
（ｂ）Ｐオブジェクトのうちの１つとＰオブジェクトのうちの別の１つの各々の幾何学的配置に属する点として定義される第１核子および第２核子それ自体によって各々が定義される、パイオンと呼ばれるＮ個体のセットから構成される集団を作成するステップと、
（ｃ）上記作成された集団のＮパイオンに関するトーナメントのセッションを体系化するステップであって、当該各セッションの間に、集団の割合は、コンバットに供された各パイオンペアのために、および、適性基準に基づいて定義された特性の評価関数として供され、どのパイオンが勝ちどのパイオンが負けたかを評価しながら、コンバットに供され、勝者および敗者は、上記トーナメントの各セッションの後で異なるマークにより同定される、ステップと、
（ｄ）上記トーナメントの後で、第１セッションの間に負けたパイオンの探索的変異、第２セッションの間に負けたパイオンの交換、および、第３セッションの間に負けたパイオンの無作為再定義を実施するステップと、
（ｅ）上記２つのＰデジタルシミュレーション化オブジェクト間の近接領域を決定するために使用される上記パイオンを処理するため、上記コンバットの勝者の集団のみを考慮するステップと、
（ｆ）ステップ（ｃ）、（ｄ）および（ｅ）を、再度繰り返し実行するステップと、
（ｇ）上記繰り返し実行の間に、上記パイオン集団の更新された配置から、需要に応じて幾何学的情報を抽出するステップと、
を含むことを特徴とする、請求項１〜１５のうちのいずれか１項に記載の方法。
【請求項１７】
上記Ｐデジタルシミュレーション化オブジェクトの幾何学的配置を記述する空間領域を同定するための上記データが多面体表示を含み、上記Ｐデジタルシミュレーション化オブジェクトの各々の上記幾何学的配置を記述するデータを提供するステップ（ａ）の後で、
（ａ１）上記各Ｐオブジェクト内で幾何学的要素間の上記近接性を定義する情報を含む連結マップを作成し、当該連結マップの情報をメモリ内に記憶するステップと、
（ａ２）上記各Ｐオブジェクト内で上記特性を定義する情報を含む近接マップを作成し、当該近接マップの情報をメモリ内に記憶するステップと、
をさらに含むことを特徴とする、請求項１６に記載の方法。
【請求項１８】
Ｐ≧２におけるＰ個のデジタルシミュレーション化オブジェクト間の近接領域を同定するためのシステムであって、当該システムは、
（ａ）Ｐオブジェクトの各々の上記幾何学的配置を記述するデータを記憶するための第１の記憶手段（１１１）と、
（ｂ）Ｐオブジェクトうちの１つとＰオブジェクトうちの別の１つの上記幾何学的配置にそれぞれ属する点として定義される第１核子および第２核子それ自体よって各々が定義される、パイオンと呼ばれるＮ個体のセットから構成される集団を作成するための初期化モジュール（１２０）と、
（ｃ）中央演算処理装置（１４０）であって、少なくとも
（ｃ１）トーナメントのセッションの間に、２つのＮパイオンにより２つのコンバットに供するＮパイオンの集団の割合を選択するための手段（１４１）と、
（ｃ２）上記トーナメントのセッションの間に、コンバットに供されるパイオンの各ペアについて、適性基準に基づいて上記パイオンペアの各パイオンの特性を評価するための比較および計算手段（１４２）と、
（ｃ３）上記トーナメントの各セッションにおいて、コンバットに供されたパイオンペアのどのパイオンが勝ったか、コンバットに供された上記パイオンペアのどのパイオンが負けたのかを同定するためのマーク付け手段（１４３）と、
（ｃ４）少なくとも１つのコンバットに供された上記パイオンの進化を生成するための繰り返し手段（１４４）であって、当該繰り返し手段（１４４）が、上記トーナメントの第１セッションの間に負けたパイオンを探索的に変異させるオペレータ、上記トーナメントの第２セッションの間に負けたパイオンを、無作為に選択されたパイオンを交差させることで交換するオペレータ、および、上記トーナメントの第３セッションの間に負けたパイオンを再定義するためのオペレータが少なくとも使用される、繰り返し手段（１４４）と、
（ｃ５）少なくとも２つの上記Ｐオブジェクト間の近接領域を決定するため、上記適性基準の関数として上記集団から最良のパイオンのみを保持するための抽出モジュール（１４５）と、
を備えた中央演算処理装置（１４０）と、
を備えたことを特徴とする、近接領域同定システム。
【請求項１９】
（ａ１）連結マップを描画し、上記各Ｐオブジェクト内の幾何学的要素間の近接性を定義する情報を記憶するための第２記憶手段（１１２）と、
（ａ２）近接マップを描画し、上記各Ｐオブジェクト内の幾何学的要素間の近接性を定義するための情報を記憶するための第３記憶手段（１１３）と、
をさらに備えたことを特徴とする、請求項１８に記載のシステム。
【請求項２０】
上記デジタルシミュレーション化オブジェクトを表示するための表示スクリーン（１３０）をさらに備えたことを特徴とする、請求項１８および１９のうちいずれか１項に記載のシステム。
【請求項２１】
触覚インターフェース（１５０）をさらに備えたことを特徴とする、請求項２０に記載のシステム。
【請求項２２】
上記中央演算処理装置（１４０）が、並行して処理する演算処理ユニットのセットを備えたことを特徴とする、請求項１８〜２１のうちのいずれか１項に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、いくつかのデジタルシミュレーション化オブジェクト間で近接領域を同定し、それらオブジェクト間の距離を評価する方法およびシステムに関する。ここで、オブジェクトは、デジタル環境内で幾何学的配置（ｇｅｏｍｅｔｒｙ）を構成する。
【背景技術】
【０００２】
例えば、デジタル環境内での実世界の会話型シミュレーションは、「バーチャルリアルティ」（ＶＲ）として知られている。
【０００３】
バーチャルリアルティのプラットフォーム（図１）は、バーチャル環境と、シミュレーションに参加しているオペレータとの間にインターフェース１０を備える。数種類のインターフェースがあり、各インターフェースは、操作者の感覚の一つをシミュレートすることを目的としている。したがって、視覚インターフェース１１、聴覚インターフェース１２、および触覚インターフェース１３は、例えば、ＶＲプラットフォームにおいて用いられ得る。
【０００４】
ＶＲプラットフォームは、物理法則およびそれらの相互作用に従って、バーチャル環境における構成要素の進化を実時間で規定すること提供する動的シミュレータをさらに備える。これらの相互作用は、双方向（機械的結合）または一方向（衝突）であり得る。
【０００５】
動的シミュレータ２０は、動力学的特性および幾何学的特性を有するオブジェクトから構成される実世界の進化の規定を提供する物理エンジンに類似している。このタスクは、２つのサブタスク、すなわち、仮想世界の動力学を管理すること（動力学エンジン２１）と仮想世界内で生じる衝突を管理すること（衝突エンジン２２）に分けることができる。
【０００６】
仮想世界の動力学を管理することで、物理法則に従って仮想世界に含まれる個々のオブジェクトの進化を規定する。
【０００７】
図２は、単一のオブジェクトに対する動力学エンジン２１の操作の図である。
【０００８】
第１ステップ２１１では、仮想オブジェクトに適用される力のバランスを確立する。このオブジェクトに供されるこれらの力は、重力、関節の応力（二方向結合としても知られる）、オペレータの操作などの種々の発生源を有し得る。これらの蓄積により、静的力等質空間（ｔｏｒｓｏｒ）を生成する。オブジェクトの線形加速度および角加速度は、基本動態の適用によって第２ステップ２１２にて決定される。次いで、新しい位置および幾何学的配置が、第３ステップ２１３にて二重積分により直接決定される。離散時間における進化が積分近接を課すことが興味深い。これには、いくつかの方法（Ｅｕｌｅｒ法、Ｔｕｓｔｉｎ法、Ｒｕｎｇｅ−Ｋｕｔｔａ法等）が想定され得る。最後のステップ２１４は単に、対象とするオブジェクトの位置および幾何学的配置を更新するために存在する。
【０００９】
衝突エンジン２２は、２つの段階、すなわち、衝突検出および接触力生成に分けられ得るタスクを実行する。
【００１０】
衝突検出は、用いられる幾何学的配置型および期待されるパフォーマンスの関数として、多くの手法により影響され得る。用いられる手法の大部分を構成する離散的方法の場合、この第１段階は、種々のオブジェクトペアの相互貫入を瞬時に検出することからなる。対照的に、連続的方法は、オブジェクト間の最初の接触の正確な時間を検出する。
【００１１】
どちらの方法が用いられても、この第１段階は、動的シミュレータにより影響されるタスクにとって最も負担となることが立証されている。事実、衝突検出のコンテキストにおいて影響される計算量は、仮想世界のオブジェクトの進化の性質、特に、幾何学的複雑性に直接関係する。
【００１２】
この衝突検出の第１段階の後では、対象とする固体のペア間での衝突から生じた力は未だ決定されていない。これらの力は通常、標準的な抗力および接線方向の摩擦推力に分解される。したがって、これらの衝突をモデリングする必要がある。これには主に３つの方法、すなわち、ペナルティー法、パルス法、および、制約法が用いられる。
【００１３】
実時間で操作する動的シミュレーションの場合、衝突の検出であろうと接触力の計算であろうと、単方向制約（衝突）の管理によって、仮想世界の構成要素の幾何学的複雑性（エンティティーの性質、数、および型）に制限が生じる。オブジェクトの性質は、そのオブジェクトの凸性（凸状か凹状）および剛性（無限剛体か変形可能体）の特性の全てで構成される。オブジェクトの幾何学的定義に用いられるエンティティーは、数種類の、メッシュ（三角形、四角形）、ボクセル、点、分析面であり得る。動的オブジェクト間での衝突を検出する主な手法を、以下に記載する。
【００１４】
衝突が起こりやすい領域は、標準的な衝突検出手法、より具体的には、それらの最適化手法によって特定される。これに応じて、この要求に応え得る３つの主要なストラテジー、すなわち、オブジェクト間の最小距離の計算、境界ボリュームの階層化、および、動作中に掃き出された（ｓｗｅｐｔ  ｏｕｔ）ボリュームの考慮が、科学文献中に見られる。
【００１５】
したがって、第１の手法は、多面体型の２つのオブジェクトＥ１とＥ２の間の最小距離を瞬時に計算することで、幾何学的要素ｅ１、ｅ２が互いに最も近いことを見出す（図３参照のこと）。
【００１６】
この最小距離、および、対象とする幾何学的要素を取得する多くの方法が採用される。これらの手法の多くは、凸オブジェクトを考慮するが、凹オブジェクトが凸要素へ細分化される場合は、凹オブジェクトのシミュレーションにも有用であることを証明することができる。この最小距離と対象とする要素を決定する第１の方法は、Ｇｉｌｂｅｒｔ、Ｊｏｈｎｓｏｎ、および、Ｋｅｅｒｔｈｉらによって発表された。その第１の方法とは、Ｍｉｎｋｏｗｓｋｙ差および凸最適化に基づいており、複雑度ｏ（（ｎ＋ｍ）2）において最悪の場合のシナリオに関して、２つの点集合Ｅ１およびＥ２の２つの凸包の間の距離を決定する。ここで、ｎおよびｍは、それぞれＥ１およびＥ２を含む点の数である。
【００１７】
しかしながら、前の処理を繰り返しつつ、得られた結果に基づいて上記方法を最適化し、複雑度をｏ（ｎ）まで減少することが可能である。この方法は、対象とするオブジェクトの性質およびそれらの幾何学的配置の進化を考慮しない。したがって、これは、剛性オブジェクトおよび凸オブジェクト以外のオブジェクトに関する方法において用いられる。ＬｉｎとＣａｎｎｙらは、互いに最も近い２つの点から２つの変形不可能な凸メッシュを、線形時間で決定する計算方法を発表している。この方法は、空間一貫性および時間一貫性に基づいている。仮想世界は動的モデルに従って進化しているので、時間が増分する間のオブジェクトの移動は非常に小さく、その結果、所与のサイクルにおいて、互いに最も近い点は、前のサイクルにおいて互いに最も近かった点の付近に在ると予想される。この方法は、対象とするメッシュ上にて対象領域の「連続」変化を仮定するので、ＤｏｂｋｉｎやＫｉｒｋｐａｔｒｉｃｋらによって提案されたような、メッシュ内で「計算の移動」を加速させる多重解像度方法を用いて、最適化され得る。
【００１８】
境界ボリュームの階層を考慮する第２の方法は、シーンで構成されるオブジェクトで占められたシーンを分割することからなる。したがって、各オブジェクトは、境界ボリュームにより近接され、それ自体は、サブボリュームのツリー（一般に、「ルート」境界ボリュームに類似するトポロジー）へと分割される。上記ストラテジーは、相互貫通しやすい領域を空間的に特定することからなる。実際には、別個のオブジェクトに境界ボリュームのオーバーラップがあるか検定し、この後で、オーバーラップを仮定し、再帰的相似検定を、サブボリュームを含むサブボリュームレベルにて実施する。上記ストラテジーは、多くの無関係な検定を回避し、既存の物理エンジンにおいて非常に広く用いられる。しかしながら、いくつかの構造（例えば、平面対平面）におけるこのようなオーバーラップ検定が非常に多く存在し得るので、これにより、シミュレーションのパフォーマンスが損なわれる。さらに、これらのボリューム（動作、変形（ｄｅｆｏｒｍａｔｉｏｎ））を更新することは、コストがかかり得る。
【００１９】
数種類の幾何学的配置が、この空間分割において用いられ得る。最も一般的に用いられる幾何学的配置は、球１と、軸直交（ｉｓｏｔｈｅｔｉｃ）境界ボックス２（ＡＡＢＢ）と、指向性（ｏｒｉｅｎｔｅｄ）境界ボックス３（ＯＢＢ）である（図４Ａ，４Ｂ，４Ｃを参照のこと）。
【００２０】
これらの型の境界ボリュームの各々は、対象とする幾何学的配置の関数および予期されるパフォーマンスレベルに、ほぼ適している。ここで、境界球の主な利点は、単純なオーバーラップ検定である。事実、２つの球のオーバーラップ検定は、それらの中心間の距離の比較、およびそれら各々の半径の合計に制限される。しかしながら、よりさらに広範にわたるオーバーラップ検定（セパレータ軸定理（ｓｅｐａｒｔｏｒ  ａｘｅｓ  ｔｈｅｏｒｅｍ））にもかかわらず、最小境界ボリュームによって無関係な検定の実行を制限するＯＢＢ等と比較すると、球は通常、対象とする幾何学的配置の次善最適近接を与える。
【００２１】
建築上、境界ボリュームの階層は、ツリー形状をとり、多くの場合、ツリーを最適にスキャンするために、２分木形状をとる。８分木（１ノードに付き８枝）および４分木（２次元に適している、１ノードに付き４枝）もある。
【００２２】
時間単位期間の間に固体を移動させることで掃き出されたボリュームは、この期間の間に占められた空間領域の結合に対応する。その幾何学的ツールは、いくつかの適用分野、すなわち、ロボット工学における作業空間の評価や、ＣＡＤにおける幾何学的モデリングを有する。並進動作の間の球によって掃き出されたボリュームは、図５Ａおよび図５Ｂに一例として示される。これらの図は、それぞれ、オブジェクトの初期位置４および最終位置５と、対応する掃き出されたボリューム６を示す。
【００２３】
シミュレーション内で時間ｔ0にて進化する剛性オブジェクトの動力学および幾何学的配置を考慮すると、水平軸ｔn，ｎ＞０の状態で掃き出されやすいボリュームを評価し、その結果、それら各々の掃かれたボリューム間での相互作用を決定することによってそれらの相互作用を予測することが、実現可能となる。
【００２４】
いくつかの方法が、文献中に記載されている。例えば、Ｋ．Ａｂｄｅｌ−Ｍａｌｅｋらの多くの取り組みが引用され得る。特に興味深い方法の１つがまた、Ｙ．Ｊ．Ｋｉｍらによって説明される。その方法は、比較的大きい複雑度（何千ものファセット）の多面体によって掃き出されたボリュームを迅速かつ確実に同定する。精巧なアルゴリズムに加えて、この方法は、実時間シミュレーションにおいて使用可能な非常に高いパフォーマンスレベルを達成させるハードウェアを使用する。
【００２５】
ボクセルは、時折、任意の幾何学的配置の別個の定義に使用され得る。この理論は、材料に占められた空間領域を、期待される解像度の種々の関数としてのサイズの立方体を用いて、同定および境界付けるためのものである（図６を参照のこと）。上述の境界ボリュームおよび掃かれたボリューム階層手法はまた、ボクセルベース型の方法である最適化に応用され得る。
【００２６】
特に、ボクセルを用いたハイブリッド離散化（「ボクセルマップ（ｖｏｘｍａｐ）」手法）、点郡（または「点の殻（ｐｏｉｎｔ  ｓｈｅｌｌ）」）の関連付け、および、法線に基づいた手法を挙げることができる。この手法は、図７Ａおよび図７Ｂに示される。
【００２７】
図７Ａは、ボクセル８ａの形態で描かれた第１の元オブジェクト８と、点郡および法線９ａの形態で描かれた第２の元オブジェクト９を示す。
【００２８】
図７Ｂは、オブジェクト８の静的表面のボクセル８ａと、オブジェクト９の点郡との間の相互作用を、平面９ｂが静的表面に接線方向にあり、力ベクトル９ａがオブジェクト９の点郡の法線に沿っている状態で、詳細に示す。
【００２９】
このハイブリッド離散化手法は、比較的長い事前演算処理段階を要するが、管理される複雑な幾何学的データを有効にする。
【００３０】
分析方法において、２つの異なる型のモデルとして、影関数曲面（ｉｍｐｌｉｃｉｔ  ｓｕｒｆａｃｅ）およびパラメトリック曲面が挙げられる。前者は、空間における形状を定義する影関数を用いる。影関数曲面は、ｆ（ｘ，ｙ，ｚ）＝０の点セットであり、モデルの内部は、ｆ（ｘ，ｙ，ｚ）＜０の点である。
【００３１】
これら２つのモデリング方法において、衝突における問題を解決することで、これらの関数を操作するようになる。これらの幾何学的定義の型は、ほとんど使用されない。実際のところ、あらゆる複雑なオブジェクト（プリミティブからは生成されていない）を、特に、例えば機械的な構成要素において非常に一般的な、突出領域（切れ目）について、上記の方法で描画することは非常に困難である。
【００３２】
一旦、相互貫通する領域が同定されると、接触力は決定されたままである。換言すると、「反発」力が、相互貫通したオブジェクトを接触の単純状態まで戻す。これを行う３つの方法、すなわち、制約法、パルス法、および、ペナルティー法が科学文献中に見られる。
【００３３】
制約法は、各オブジェクトに特異的な動作方程式のレベルで、非相互貫通の制約を明確に考慮することからなる。制約は、以下の数式に表される。
【数１】
2008507056.tif 000003
ここで、第１の方程式は、各オブジェクトの動作をそのオブジェクトに適用される力の関数として特徴付け、第２の方程式は、非相互貫通の制約を特徴付ける。
【００３４】
上記方法は、摩擦が存在しない場合と、衝突があまり頻繁には起きない場合（衝突計算、すなわち、Ｃ（ｐ（ｔ））の決定のコストがかかる）場合において、特に興味深い。このことは、システム全体の安定性による逆効果を有さないという利点を有する。
【００３５】
パルス法は、２つの剛性オブジェクト間の相互作用を衝突（ｉｍｐａｃｔ）として処理する動的方法である。したがって、衝突は、対象とするオブジェクトに対する強い力（パルスと呼ばれる）を生じる擬似的な瞬間的事象として考慮される。それゆえ、以下の関係を衝突の前後に、速度に適用する。
【数２】
2008507056.tif 000004
ここで、ｅは、回復係数と呼ばれる（ｅ＝０：弾性衝突、ｅ＝１：塑性衝突）。Ｐｏｉｓｓｏｎ仮説は、ｅを計算するために用いられ得る。
【数３】
2008507056.tif 000005
【００３６】
２つのオブジェクトが十分接近している場合は、パルスを、それらオブジェクトを分けるために一回繰り返して計算する。対象とするオブジェクトが弾道経路を有さなければならない状態は、多くの場合、計算を最適化するために適用される。
【００３７】
ペナルティー法は、弾性オブジェクトと変形不可能オブジェクトとの間の反発力を管理する。これは、衝突において、オブジェクト１４、１５に、相互貫通の深さに比例する力（用語「剛性」が用いられる）を適用することからなる。したがって、反発「機構」は、多くの場合、比例する導関数型のシステム１６として処理される（図８を参照のこと）。この方法は、貫通ベクトル（コストがかかり得る）の知識を必要とし、多くの場合、不安定になる（特に多点衝突において）。
【００３８】
距離を評価し近接領域を同定することについては上述に見られ、ここで、デジタル環境内で進化する幾何学的オブジェクト間における適用可能な衝突の検出は、例えば、ロボットシステムの動作についてのバーチャルリアルティまたはシナリオのような多数の研究領域において、明らかに必須工程である。
【００３９】
しかしながら、特に、演算処理時間におけるそれらのコストのため、今までに用いられた種々の方法は、多くの場合、複雑の幾何学的配置を含み、高いレベルのパフォーマンスを要求するシミュレーションにおいては使用され得ない。
【発明の開示】
【発明が解決しようとする課題】
【００４０】
本発明は、従来技術の欠点を改善し、距離の評価または近接領域の同定において繰り返し起こる大部分の問題に取り組み、特に、衝突の検出において、たとえ相互作用するオブジェクトが複雑な幾何学的配置または異なる性質もしくは特性を有していても、実時間アプリケーションを両立しながら演算時間を削減し、高いレベルのパフォーマンスと実装の容易性を提供する解決法を提供することを目的とする。
【課題を解決するための手段】
【００４１】
本発明によると、上の目的は、少なくとも第１デジタルシミュレーション化オブジェクトと第２デジタルシミュレーション化オブジェクトとの間の近接領域を同定する方法によって達成される。この方法は、
（ａ）第１デジタルシミュレーション化オブジェクトおよび第２デジタルシミュレーション化オブジェクトの各々の幾何学的配置を記述するデータを提供し、このデータをメモリ内に格納するステップと、
（ｂ）各第１オブジェクトおよび第２オブジェクトの各幾何学的配置に属する点として定義される第１核子および第２核子それ自体によって各々が定義される、パイオン（ｐｉｏｎ）と呼ばれるＮ個体のセットから構成される集団を作成するステップと、
（ｃ）上記作成された集団のＮパイオンに関するトーナメントのセッションを体系化するステップであって、この各セッションの間に、集団の割合は、コンバット（ｃｏｍｂａｔ）に供された各パイオンペアのために、および、適性基準に基づいて定義された特性の評価関数として供され、どのパイオンが勝ち（ｗｏｎ）どのパイオンが負けた（ｌｏｓｔ）かを評価しながら、コンバットに供され、勝者および敗者は、上記トーナメントの各セッションの後で異なるマークにより同定される、ステップと、
（ｄ）上記トーナメントの後で、第１セッションの間に負けたパイオンの探索的変異（ｅｘｐｌｏｒａｔｏｒｙ  ｍｕｔａｔｉｏｎ）、第２セッションの間に負けたパイオンの交換（ｒｅｐｌａｃｅｍｅｎｔ）、および、第３セッションの間に負けたパイオンの無作為再定義を実施するステップと、
（ｅ）上記第１オブジェクトと上記第２オブジェクトとの間の近接領域を決定するために使用される上記パイオンを処理するため、上記コンバットの勝者の集団のみを考慮するステップと、
（ｆ）ステップ（ｃ）、（ｄ）および（ｅ）を、再度繰り返し実行するステップと、
（ｇ）上記繰り返し実行の間に、上記パイオン集団の更新された配置から、需要に応じて幾何学的情報を抽出するステップと、
を含むことを特徴とする。
【００４２】
幾何学的情報を抽出するステップの間に、同定された近接領域間の距離が評価され得る。
【００４３】
第１のデジタルシミュレーション化オブジェクトと第２のデジタルシミュレーション化オブジェクトのうちの少なくとも１つの幾何学的配置を記述する空間領域を同定するためのデータは、多面体表示、ボクセル表示、パラメータ化された表面または点郡を用いる表示を含み得る。
【００４４】
或る特有の特徴によると、パイオンの特性を評価するための適性基準は、そのパイオンを定義する第１核子と第２核子の分離距離の測定にあり、そのパイオンの特性が、測定された距離に反比例するものである。この距離の測定は、例えば、パイオンを定義する第１核子と第２核子の間の距離の二乗を考慮し得る。
【００４５】
本発明に従う方法は、第１のデジタルシミュレーション化オブジェクトと第２のデジタルシミュレーション化オブジェクトの各々の幾何学的配置を記述するデータを提供するステップ（ａ）の後で、
（ａ１）上記第１オブジェクトおよび上記第２オブジェクト内で幾何学的要素間の近接性を定義する情報を含む連結マップ（ｃｏｎｎｅｃｔｉｖｉｔｙ  ｍａｐ）を作成し、この連結マップの情報をメモリ内に記憶するステップと、
（ａ２）上記第１オブジェクトと上記第２オブジェクトとの間の近接性を定義する情報を含む近接マップ（ｐｒｏｘｉｍｉｔｙ  ｍａｐ）を作成し、この近接マップの情報をメモリ内に記憶するステップと、
をさらに含み得る。
【００４６】
上記トーナメントのセッションの間に負けたパイオンを変異させて（ｍｕｔａｔｉｎｇ）、その負けたパイオンに探索的変異をもたらすことは、有利なことに、第１核子および第２核子がそれぞれ属している第１オブジェクトおよび第２オブジェクトの表面上のパイオンの構成要素となる第１核子および第２核子を移動することからなる。
【００４７】
１つの特有の実施形態において、負けたパイオンに探索的変異をもたらすため、トーナメントのセッションの間に、負けたパイオンを変異させる場合、パイオンの構成要素となり、多面体形状で描写された第１オブジェクトおよび第２オブジェクトのうちの１つに属する、少なくとも１つの第１核子および第２核子は、メモリ内に記憶された近接性を定義する情報を考慮しつつ、別個のファセットの中心からファセットの中心までの一連の動作に供される。
【００４８】
別の特有の実施形態において、トーナメントの間に勝ったパイオンを変異させる場合、パイオンの構成要素となり、多面体形状で描写された第１オブジェクトおよび第２オブジェクトのうちの１つに属する、少なくとも１つの第１核子および第２核子は、その点の開始位置であるファセットの中心、および、転移（ｄｉｓｐｌａｃｅｍｅｎｔ）に影響されるファセット領域に依存する最大転移振幅（ｍａｘｉｍｕｍ  ｄｉｓｐｌａｃｅｍｅｎｔ  ａｍｐｌｉｔｕｄｅ）である半径を有する円盤（ｄｉｓｃ）上の同じファセットでの動作に供される。
【００４９】
さらなる特有の実施形態において、トーナメントの間に勝ったパイオンを変異させる場合、パイオンの構成要素となり、多面体形状で描写された第１オブジェクトおよび第２オブジェクトのうちの１つに属する、少なくとも１つの第１核子および第２核子は、メモリ内に記憶された近接性を定義する情報を考慮しつつ、１つのファセットの１つの頂点から、必ずしも結合されない別のファセットの近くの頂点までの、「ワームホール（ｗｏｒｍｈｏｌｅ）」形状での動作に供される。
【００５０】
さらなる特有の実施形態において、トーナメントの間に勝ったパイオンを変異させる場合、パイオンの構成要素となり、三角形ファセットを含む多面体形状で描写された第１オブジェクトおよび第２オブジェクトのうちの１つにそれぞれ属する、第１核子および第２核子が位置付けされ、その結果、これらの核子は、これら第１核子および第２核子がそれぞれ属する２つの三角形ファセット間の最小距離を定義するエッジの境界を定める。
【００５１】
上記負けたパイオンの交換を生じさせるトーナメントのセッションの間に、第１の無作為に選択されたパイオンと第２の無作為に選択されたパイオンとの交差によって生じた新パイオンを定義するために、無作為に選択されたパイオンを交差させることにより負けたパイオンを交換する場合、上記新パイオンが、上記第１の無作為に選択されたパイオンの第１核子と、上記第２の無作為に選択されたパイオンの第２核子から構成されるとみなされる。
【００５２】
より詳細には、本発明は、Ｐデジタルシミュレーション化オブジェクトのセットにＰ≧２で適用される方法を提供し、この方法は、
（ａ）上記Ｐグラフィックシミュレーション化オブジェクトの各々の幾何学的配置を記述するデータを提供するステップと、
（ｂ）Ｐオブジェクトのうちの１つとＰオブジェクトのうちの別の１つの幾何学的配置にそれぞれ属する点として定義される第１核子および第２核子それ自体によって各々が定義される、パイオンと呼ばれるＮ個体のセットから構成される集団を作成するステップと、
（ｃ）上記作成された集団のＮパイオンに関するトーナメントのセッションを体系化するステップであって、この各セッションの間に、集団の割合は、コンバットに供された各パイオンペアのために、および、適性基準に基づいて定義された特性の評価関数として供され、どのパイオンが勝ちどのパイオンが負けたかを評価しながら、コンバットに供され、勝者および敗者は、上記トーナメントの各セッションの後で異なるマークにより同定される、ステップと、
（ｄ）上記トーナメントの後で、第１セッションの間に負けたパイオンの探索的変異、第２セッションの間に負けたパイオンの交換、および、第３セッションの間に負けたパイオンの無作為再定義を実施するステップと、
（ｅ）上記二つのＰデジタルシュミレーション化オブジェクト間の近接領域を決定するために使用される上記パイオンを処理するため、上記コンバットの勝者の集団のみを考慮するステップと、
（ｆ）ステップ（ｃ）、（ｄ）および（ｅ）を、再度繰り返し実行するステップと、
（ｇ）上記繰り返し実行の間に、上記パイオン集団の更新された配置から、需要に応じて幾何学的情報を抽出するステップと、
を含むことを特徴とする。
【００５３】
Ｐデジタルシミュレーション化オブジェクトの幾何学的配置を記述する空間領域を同定するためのデータが多面体表示を含む場合、Ｐデジタルシミュレーション化オブジェクトの各々の幾何学的配置を記述するデータを提供するステップ（ａ）の後で、上記方法は、有利なことに
（ａ１）上記各Ｐオブジェクト内で幾何学的要素間の近接性を定義する情報を含む連結マップを作成し、この連結マップの情報をメモリ内に記憶するステップと、
（ａ２）上記各Ｐオブジェクト内で上記特性を定義する情報を含む近接マップを作成し、この近接マップの情報をメモリ内に記憶するステップと、
をさらに含む。
【００５４】
本発明はさらに、Ｐ≧２におけるＰ個のデジタルシミュレーション化オブジェクト間の近接領域を同定するためのシステムを提供し、このシステムは、
（ａ）Ｐオブジェクトの各々の幾何学的配置を記述するデータを記憶するための第１記憶手段と、
（ｂ）Ｐオブジェクトうちの１つとＰオブジェクトうちの別の１つの各々の幾何学的配置に属する点として定義される第１核子および第２核子それ自体によって各々が定義される、パイオンと呼ばれるＮ個体のセットから構成される集団を作成するための初期化モジュールと、
（ｃ）中央演算処理装置であって、少なくとも
（ｃ１）トーナメントのセッションの間に、２つのＮパイオンにより２つのコンバットに供するＮパイオンの集団の割合を選択するための手段と、
（ｃ２）トーナメントのセッションの間に、コンバットに供されるパイオンの各ペアについて、適性基準に基づいてパイオンペアの各パイオンの特性を評価するための比較および計算手段と、
（ｃ３）トーナメントの各セッションにおいて、コンバットに供されたパイオンペアのどのパイオンが勝ったか、コンバットに供された上記パイオンペアのどのパイオンが負けたのかを同定するためのマーク付け手段と、
（ｃ４）少なくとも１つのコンバットに供されたパイオンの進化を生成するための繰り返し手段であって、この繰り返し手段が、トーナメントの第１セッションの間に負けたパイオンを探索的に変異させるためのオペレータ、トーナメントの第２セッションの間に負けたパイオンを無作為に選択されたパイオンを交差させることで交換するためのオペレータ、および、トーナメントの第３セッションの間に負けたパイオンを再定義するためのオペレータが少なくとも使用される、繰り返し手段と、
（ｃ５）少なくとも２つのＰオブジェクト間の近接領域を決定するため、適性基準の関数として集団から最良のパイオンのみを保持するための抽出モジュールと、
を備えた中央演算処理装置と、
を備えたことを特徴とする。
【００５５】
上記システムは、
（ａ１）連結マップを描画し、各Ｐオブジェクト内の幾何学的要素間の近接性を定義する情報を記憶するための第２記憶手段と、
（ａ２）近接マップを描画し、各Ｐオブジェクト内の幾何学的要素間の近接性を定義するための情報を記憶するための第３記憶手段と、
をさらに備えたことを特徴とする。
【００５６】
中央演算処理装置は、並行して処理する演算処理ユニットのセットを備え得る。
【００５７】
したがって、本発明に従う方法およびシステムは、確立論的手法に基づいて進化過程を見出す。この進化過程は、単に２進法で定義されるだけでなく、実成分によって定義された個体の集団を処理する。
【発明を実施するための最良の形態】
【００５８】
本発明の他の特徴および利点は、添付の図面を参照し、所与の非限定的な例を用いた特有の実施形態の説明から明らかになる。
【００５９】
本発明に従う方法およびシステムは、それらの特有の一実施形態により説明され、デジタルシミュレーション化オブジェクトまたは仮想オブジェクトから始めて、オブジェクトの幾何学的複雑性および性質（凸性、剛性）に関係なく、オブジェクトの幾何学的表示を用いる動的実時間シミュレーションの間中、衝突が起こりやすい幾何学的領域を同定する。
【００６０】
本発明に従う方法は、これのための進化プロセスを使用する。一般的に言えば、この方法は、最適な配置に向かって収束する集団を生成するのに適した変化（変異、交差）オペレータを用いて進化する個体集団を有することからなるストラテジーを適用する。
【００６１】
個体の特性は、１つ以上の定性基準を測定するのに適した目的（「適合度」）関数を用いて評価される。
【００６２】
新たな個体を生成するこの種の進化プロセスは、非常に効果的でありかつ実施が簡単である。
【００６３】
バーチャルリアルティの進化プロセスを適用する、本発明に従う方法は、多面体で描かれたオブジェクトに関してまず説明されるが、本発明は、より一般的な性質のものであり、対象とするオブジェクトの幾何学的表示にかかわらずこの方法を適用する。
【００６４】
既に示したように、本発明に従う方法の基本ストラテジーは、最適な配置に向かって収束する集団を生成するのに適した変化（変異、交差）オペレータを用いて進化する集団（個体郡）を生成することである。
【００６５】
図９は、個体の遺伝子型（ｇｅｎｏｔｙｐｅ）５１の定義（「パイオン」としてもまた以下で呼ばれる）における一例を示す。この個体は、近接性が評価される第１オブジェクトおよび第２オブジェクトを表す２つのメッシュＯｂｊｅｃｔ1およびＯｂｊｅｃｔ2の各々にそれぞれ属する点から構成される核子のペアとして定義される。
【００６６】
ここで、パイオンの遺伝子型５１は、以下のように表現され得る。
【数４】
2008507056.tif 000006
【００６７】
【数５】
2008507056.tif 000007
【００６８】
上で定義された遺伝子型は、多面体型オブジェクトのシミュレーションのコンテキストにおいて使用されることを意図している。より一般的には、パイオンは単に、あらゆる種類における２つの個別のオブジェクトに属する２つの核子により定義されることを重視することが重要である。暗黙的表面（ｉｍｐｌｉｃｉｔ  ｓｕｒｆａｃｅ）が考慮される場合、例えば、パイオンは、第１の点の座標（ｘ1，ｙ1，ｚ1）、および、第２の点の座標（ｘ2，ｙ2，ｚ2）により定義される。ボクセル型の幾何学的配置に関して、点は、対象とするボクセルのインデックスにより定義され得る。ここで、パイオンの記述は、用いられた幾何学的配置の型に直接関連している。さらに、２つの異なる型の幾何学的配置の間でパイオンを定義することが可能であり、この点の座標は、評価時に直交座標空間（Ｃａｒｔｅｓｉａｎ  ｓｐａｃｅ）で体系的に表現される。
【００６９】
パイオンの特性を評価するための目的（「適合度」）関数または適性基準は、そのパイオンを定義する第１核子と第２核子との間の測定された距離からなる。この測定は、有利なことに、パイオンを構成する２つの核子の間における距離の二乗であり得る。
【００７０】
（ｘ1，ｙ1，ｚ1）および（ｘ2，ｙ2，ｚ2）を、同じ基準系において射影されたパイオンｐ1を構成する核子における個別の直交座標と仮定する。この個体の適合度（ｆｉｔｎｅｓｓ）の式は、以下の通りである。
【数６】
2008507056.tif 000008
【００７１】
平方根関数が演算処理時間の点において非常にコストがかかるので、ノルム（ｎｏｒｍ）の二乗の使用は、好都合である。
【００７２】
個体またはパイオンＰの特性Ｑｕａｌｉｔｙ（ｐ）が、その目的（適合度）関数（ｐ）に反比例することに留意すること。
【００７３】
進化オペレータを参照する変異は、程度の差はあるが、個体の遺伝的遺産（ｇｅｎｅｔｉｃ  ｈｅｒｉｔａｇｅ）の変化として定義され得る。
【００７４】
より詳細には、本発明のコンテキストにおいて、個体を変異させることは、それらの点が属しているオブジェクトの表面上でそれが構成される点を交換することからなる。
【００７５】
いくつかの交換経験則（ｈｅｒｕｒｉｓｔｉｃｓ）は、多面体を用いるシミュレーションのコンテキストにおいて定義され得る。
【００７６】
ここで、図１０の例によって示される探索的オペレータに関して、対象とする個体を定義する点は、オブジェクトの表面上で遠距離移動することができる。このオペレータは、
事前に計算された（ｐｒｅｃｏｍｐｕｔｅｄ）近接マップを用いて取得された、対象とするオブジェクトの連結性（ｃｏｎｎｅｃｔｅｄｎｅｓｓ）を考慮しつつ、ファセット５３の中心５２を別個のファセット５３の中心５２へと転移させる。変異の間に影響されたホップ（ｈｏｐ）の数に対応する、これらの転移の振幅は、無作為に決定される。これは、０からσExplorまでであり、最大転移振幅は、オブジェクトの幾何学的配置に依存する。
【００７７】
図１０は、８ホップの振幅における多面体上の点の不連続な探索的転移を示すが、この値は、ほんの一例として与えられただけである。
【００７８】
図１１に示された、別の変異型に対応する開拓オペレータは、対象とする個体を構成する点の位置決めを精緻化するのに適している。探索的変異とは対照的に、これらの転移は、計量的様式において定義される。ここで、各点は、最大転移振幅であって、中心に対しその点の初期位置を有する、半径σExplitの円盤上の転移に影響する。最大転移振幅（メートルで表現される）は、転移に影響される面５６の領域に依存し得る。したがって、この振幅は、各ファセットについて事前計算段階の間に計算される。
【００７９】
オブジェクトの多面体表示６０の面６１上を、連結性（近接性）のみを考慮して転移することは、特に、薄いかまたは大きく曲がっているオブジェクトについては、制限的であることが立証され得る。ここで、本発明の別の側面によると、頂点の近接度に基づいた第２の「マップ」が、インストールされている。事前計算段階の間、各頂点６２，６３について、最も近い頂点６４，６５のリストが構築される。変異中のパイオンを構成する点（６３）のうちの１つが、転移の終点にある頂点に位置される場合、このことについて、必ずしも連結される必要がない近接した頂点（６４）にむかってスリップするというオプションがある（義務ではない）。この転移型は、Ｅｉｎｓｔｅｉｎ−Ｒｏｓｅｎブリッジ（曲面状の宇宙（ｃｕｒｖｅｄ  ｕｎｉｖｅｒｓｅ）内の離れた領域につながる近道と似ている通路）を参照して、「ワームホール」と呼ばれ得る。
【００８０】
図１２Ａは、面６１を有するオブジェクトの多面体表示６０を示す。
【００８１】
近接マップによると、頂点６４，６５は、頂点６２，６３に近接しているものとして同定される。
【００８２】
図１２Ｂは、ワームホールがない状態の、頂点６３から点６７までの経路６６の例を示す。
【００８３】
図１２Ｃは、「ワームホール」変異オペレータを用いる代替経路を示す。ここで、頂点６３から点６７までの経路は、オブジェクトの表示６０の外側にあり、近接しているものとして同定された頂点６３と頂点６４との間の、「ワームホール」型の通路６８を含む。
【００８４】
上述の３つのオペレータのそれと類似する機能を有する変異オペレータは、他の幾何学的配置型を用いるシミュレーションのコンテキストにおいて定義され得る。
【００８５】
本発明はまた、集団の収束を加速することを目的とする、「交差」オペレータと呼ばれる変化オペレータを使用する（図１３）。この原理は、集団（親）から取得された２つのパイオンを結合することによりパイオン（子）を生成することである。したがって、新たなパイオンは、その２つの親に特有の遺伝特性を有する。実際、このオペレータは、「子」パイオンが、核子１については第１の親のパイオン、および、核子２については第２の親のパイオンを有するという様式において使用され得る。
【００８６】
図１４は、本発明に従う方法の概略図であり、初期化または第１段階７１、トーナメントまたは第２段階７２、および、進化または第３段階７３を含む。
【００８７】
初期化段階７１の間、データは、グラフィックシミュレーション化オブジェクトの各々の幾何学的配置を記述する点の同定するために提供され、このデータは、メモリ内に記憶される。
【００８８】
同じ初期化段階７１の間、ここでは、オブジェクト内の位相幾何学的近接性（ｔｏｐｏｌｏｇｉｃａｌ  ｖｉｃｉｎｉｔｙ  ｐｒｏｐｅｒｔｙ）を定義する情報を含む連結マップもまた作成され、この連結マップの情報は、メモリ内に記憶される。
【００８９】
初期化段階７１は、オブジェクト内の近接（ワームホール）特性を定義する情報を含む近接マップを構築し、この近接マップからの情報をメモリ内に記憶することをさらに含む。
【００９０】
初期化段階７１の間に最終的に作成された、Ｎ個体のセットからなる集団（パイオンと呼ばれる）が存在し、これは、事前に同定された別個の２つのオブジェクトにおける各幾何学的配置に属する点から構成される、第１核子および第２核子によりそれぞれが定義される。
【００９１】
トーナメント段階７２は、個体間でのコンバットを管理することからなる。２つの個体またはパイオン間でのコンバットは、２つのパイオンのうちどちらがより良い特性であるか、すなわち、２つのパイオンのうちどちらが、低い目的（「適合度」）関数（または適性基準）を有するかを評価する。
【００９２】
したがって、トーナメント段階７２の間、作成された集団のＮパイオンに関するセッションは体系化される。この各セッションの間に、集団の割合は、コンバットに供された各パイオンペアについて、および、適性基準に基づいて定義された特性の評価関数として、どのパイオンが勝ちどのパイオンが負けたかを評価されながら、コンバットに供される。そして、この勝者および敗者は、上記トーナメントの各セッションの後で、異なるマークにより同定される。
【００９３】
トーナメント段階７２の種々のセッションは、例えば、後に変異を起こす集団の割合のコンバットからなる第１セッションＭｕｔ％、後に交差を起こす集団の割合のコンバットからなる第２セッションｃｒｏｓｓ％、および、後で無作為に再定義する集団の割合のコンバットからなる第３セッションＲａｎｄ％を含み得る。
【００９４】
第１セッションＭｕｔ％、第２セッションｃｒｏｓｓ％、および第３セッションＲａｎｄ％は、任意の順序で行われてもよい。トーナメント段階７２の後で、勝ちパイオン（ｗｉｎｎｉｎｇ  ｐｉｏｎ）は、負けパイオン（ｌｏｓｉｎｇ  ｐｉｏｎ）の印とは異なるマークにより同定される。パイオンのマーク付けはまた、それらが１つ以上のコンバットに供されていた間のセッションの関数とも異なる。
【００９５】
進化段階７３は、上に定義された変化オペレータを、トーナメント結果の関数として適用することからなり、ここで、この段階は、トーナメントの第１セッションＭｕｔ％の間に、負けたパイオンを変異させること、トーナメントの第２セッションＣｒｏｓｓ％の間に、無作為に選択されたパイオンの交差によって、負けたパイオンを交差すること、および、トーナメントの第３セッションＲａｎｄ％の間に、負けたパイオンを再定義することを含む。良い構成要素であるとみなされるコンバットの勝者は、２つのオブジェクト間の近接領域を決定するために処理される。このプロセスは、繰り返され、段階７２および７３は、連続して繰り返され得る。勝者としてマーク付けされたパイオンのみを利用することにより機能強化された配置をいつでも利用することが可能である。
【００９６】
本発明に従う方法は、オブジェクトの幾何学的性質および特性にそれほど依存しない。シミュレーションのコンテキストにおいて、適切な変化オペレータが定義されている場合は、幾何学的配置の全ての型（多面体、ボクセル、パラメータ化された表面等）を使用することは、有効である。さらに、幾何学的配置を混合することが可能であり、パイオンを構成する点は、それが属する各々のオブジェクトの表面とはまったく異なる様式で進化することが可能である。この方法は、凸性、探索的変異、および無作為再定義に対して敏感ではない。オブジェクトの特性（法線の幾何学的配置、穴など）は、このプロセスの機能にまったく影響しない。このことは、かなり有利である（現在の物理エンジンは、オブジェクトの特性に非常に敏感であり、このことは多くの場合、そのエンジンの正確な機能にかなり影響を与える）。
【００９７】
上記プロセスの第２ステップ７２（トーナメント）および第３ステップ７３（進化）の実行時間は、基本幾何学的エンティティー（ｅｌｅｍｅｎｔａｒｙ  ｇｅｏｍｅｔｒｉｃａｌ  ｅｎｔｉｔｙ）の数に依存しないが、オブジェクトの幾何学的複雑性に依存しないパイオンの数だけには依存する。全ての場合において、パイオンは、基本幾何学エンティティーよりもずっと少ない。したがって、全体のプロセスは、オブジェクトの幾何学的複雑性から比較的独立している。
【００９８】
既に示したように、個体またはＮ個体の集団のパイオンは、核子とも呼ばれる２つの点からなる。
【００９９】
上述のとおり、より詳細には、多面体的に表示されたオブジェクトについて、進化オペレータ（「変異誘発因子（ｍｕｔａｔｏｒ）」）のセットは、それらが属する多面体内で進化するためにパイオンをもたらすのに適している。
【０１００】
別のオペレータは、多面体型のオブジェクトの表示内で三角形に最適な、対象とする個体から構成される核子を位置決めする。
【０１０１】
この変異オペレータは、対象とするパイオンの目的（適合度）関数を正確かつ局所的に最小化する決定論的方法を使用する。この変異オペレータは、集団を構成する個体の精鋭集団（ｅｌｉｔｅ）に適用されることを意図している。これは、収束を加速すること、および、この方法の実施によって得られた結果の正確性の向上を意図している。
【０１０２】
このオペレータの目的は、それらが属する２つの各三角形間の最小距離を定義するエッジを実体化（ｍａｔｅｒｉａｌｉｚｅ）するため、対象とするパイオンを構成する核子を位置決めすることである。
【０１０３】
図１５Ａ、図１５Ｂ、および、図１５Ｃは、２つの三角形８１，８２、２つの三角形８３，８４、および、２つの三角形８５，８６について３つの異なる幾何学的配置を示す。これにおいて、２つの三角形間の最小距離を実体化するエッジ８７、エッジ８８、および、エッジ８９は、それぞれ、頂点対面、頂点対頂点、およびエッジ対エッジの相互作用に対応する。
【０１０４】
以下に記載される決定方法は、これらの種々の状況に対処することができる。
【０１０５】
対象とするパイオンを構成する核子の最適位置を短時間で決定するため、三角形対三角形の場合が、以下に説明されるように６エッジ対三角形へ分割される。したがって、上で定義された幾何学的配置の全てを対象とする。
【数７】
2008507056.tif 000009
上の式において、ΨST（Ｓ，Ｔ）およびΨTT（Ｔ1，Ｔ2）は、エッジ対三角形の場合、および、三角形対三角形の場合の各々において最小距離を実体化するエッジを定義する。
【０１０６】
エッジ対三角形の場合における最小エッジの決定は、それ自体が２つの段階、すなわち、考えられる幾何学的配置の同定および対象とする構成要素（エッジ、点、面）の同定、ならびに、最小エッジの決定に分けられる。
【０１０７】
第１段階は、三角形に含む平面に対して直角なエッジの両端を射影することからなる。三角形に対するそれらの射影の位置を組み合わせることで、考えられる幾何学的配置および潜在的に対象とする構成要素を同定することを可能にする。三角形に対する射影の位置は、それらが、三角形の側面を有する直線によって定義された平面部分のうちの一部に属することを経て形式化される。例えば、図１６に例示されるように、エッジの両端ＰおよびＱの射影Ｐ1，Ｑ1は、それぞれ、三角形（Ａ，Ｂ，Ｃ）を含む平面の領域Ｚ2およびＺ4に属する。
【０１０８】
したがって、考えられる組合せが４９組存在する。
【数８】
2008507056.tif 000010
【０１０９】
以下の表は、各組み合わせについての最小エッジを潜在的に有する要素のペアを与える。ここで、ΨSS（［Ｐ1，Ｑ1］，［Ｐ2，Ｑ2］）およびΨPS（Ｍ，［Ｐ  Ｑ］）は、エッジ対エッジの場合、および、点対エッジの場合の各々において、最小距離を実体化するエッジを定義する。
【表１】
2008507056.tif 000011
【０１１０】
第２段階は、最適パイオンを決定することからなる。ここで、上述の全ての関数は、このパートにおいて定義される。
【０１１１】
点対エッジの場合が、図１７に示され、これは、ΨρS（Ｍ，［Ｐ  Ｑ］）に相当する。
【０１１２】
ここの目的は、以下のようにして係数λを決定することである。
【数９】
2008507056.tif 000012
【０１１３】
これを、式の形で表すと以下になる。
【数１０】
2008507056.tif 000013
【０１１４】
４つの未知数がある４つの式が以下のように得られる。
【数１１】
2008507056.tif 000014
【０１１５】
この式により、以下を導く。
【数１２】
2008507056.tif 000015
【０１１６】
Ｍ’が［ＰＱ］に属することを確実にするため、係数λが、飽和される。換言すると、λ＜０の場合、λに値０が与えられ、λ＞１の場合、λに値１が与えられる。
【０１１７】
エッジ対エッジの場合が、図１８に示され、これは、ΨSS（［Ｐ1，Ｑ1］，［Ｐ2，Ｑ2］）に相当する。
【０１１８】
ここの目的は、以下のようにして係数λおよびμを決定することである。
【数１３】
2008507056.tif 000016
【０１１９】
これを、式の形で表すと以下になる。
【数１４】
2008507056.tif 000017
【０１２０】
８つの未知数がある８つの式が以下のように得られる。
【数１５】
2008507056.tif 000018
【０１２１】
Ｍ1およびＭ2がそれぞれ、［Ｐ1Ｑ1］および［Ｐ2Ｑ2］に属することを確実にするため、係数λおよびμが、上のように飽和される。
【０１２２】
互いに移動しあう複数のオブジェクトを含むオブジェクトのデジタルシミュレーションに関して、オブジェクトの各ペアについてパイオンの集団を作成することは可能である。この方法は、オブジェクトの数ｎが比較的小さい場合は実行され続け得るが、オブジェクトの数ｎが２よりもずっと大きい場合は、演算処理時間においてコストがかかることを立証し得る。
【０１２３】
本発明は、シミュレーション内に存在するオブジェクトの幾何学的表示の全てに適用される、Ｎ個体またはパイオンの単一集団を用いて、実施され得る。
【０１２４】
こうした状況では、同じ集団のパイオンは、シミュレーション内に含まれる幾何学的配置のペアのうちの１つだけではなく、シミュレーション内に含まれる幾何学的配置（メッシュ）のペアの全体にわたって、進化させることができる。
【０１２５】
関連組合せを優先させるために、接触が起り得ないオブジェクトのペア、具体的には、剛性的に接触しているかまたは遠く離れているオブジェクトは、考慮に入れない。
【０１２６】
多面体の場合が考慮されると、パイオンの遺伝子型は、以下の様式において表される。ここで、Ｍｅｓｈ1およびＭｅｓｈ2は、パイオンを構成する２つの点（核子）が属するオブジェクトのメッシュ（多面体）の同定を表示する。
【数１６】
2008507056.tif 000019
【０１２７】
【数１７】
2008507056.tif 000020
【０１２８】
上に定義された変異は、この操作方法には影響されない。核子の内部幾何学的配置「ホップ」は、幾何学的配置の１つだけでなく、スキャンされる全ての空間を対象とする無作為交換の段階の間に、影響される。
【０１２９】
オブジェクトのｎ幾何学的表示Ｍｅｓｈ1〜Ｍｅｓｈ4を対象とするＮパイオンＰｉｏｎ1〜Ｐｉｏｎ4の集団への、上記方法の適用は、ｎ＝４かつＮ＝４の場合について図１９に示される。
【０１３０】
図１９の例における４つのパイオンの遺伝子型は、以下の通りである。
【数１８】
2008507056.tif 000021
【０１３１】
本発明は、例えば、バーチャルリアルティまたはインフォグラフィックスのような多数の応用分野において日常的に用いられる、多面体の幾何学的配置を含むシミュレーションに対して、および、非多面体の幾何学的配置を含むシミュレーションに対して、一様に適用する。
【０１３２】
多面体の幾何学的配置に適した遺伝子型および変異操作は、上で与えられた例において既に説明されている。
【０１３３】
図２０は、多面体構造のファセット上の核子９１，９１’の無作為交換のための変異誘発因子の例を示す。
【０１３４】
非多面体の幾何学的配置を含む、本発明の使用におけるいくつかの例が、以下に記載される。
【０１３５】
図２１は、「パッチ（ｐａｔｃｈ）」と呼ばれるパラメータ化された（ベジエ、Ｂスプライン等）表面によって描かれたオブジェクトを例示する。
【０１３６】
このようなオブジェクトに関して、パイオンの各核子の定義としては、識別子Ｐａｔｃｈ1、それが属し座標がｕ1ｖ1であるパラメータ化された表面の個々のＰａｔｃｈ2、パラメータ化された表面Ｐａｔｃｈ1内の核子の個々のｕ2ｖ2、それが属する個々のＰａｔｃｈ2が挙げられる。
【０１３７】
パイオンの遺伝子型が、以下の通りである。
【数１９】
2008507056.tif 000022
【０１３８】
図２１において、Ｍ1およびＭ2は、Ｐａｔｃｈ1およびＰａｔｃｈ2を個々に定義する数学的表現である。
【０１３９】
パラメータ化された表面に用いられる変異誘発因子に関して、パラメータ化された表面上での核子の進化は、その中での座標の確率論的修飾からなる（すなわち、（ｕ，ｖ）⇒（ｕ＋Δu，ｕ＋Δv））。したがって、変化係数ΔuおよびΔvのために選択された最大値は、変異の型（探索または開拓）を調整する。
【０１４０】
核子の無作為な再位置決めは、その座標の無作為な変化により影響され得る。
【０１４１】
点郡の形態で描かれたオブジェクトは、図２２において例示される。ここで、オブジェクトの２つの表示は、Ｃｌｏｕｄ1およびＣｌｏｕｄ2と参照付けられる。
【０１４２】
こうした状況では、パイオンの遺伝子型を決定するために、核子の各々が、識別子ｐ1、および、それが属する点の個々のｐ2によって、以下のように定義される。
【数２０】
2008507056.tif 000023
変異オペレータに関して、点郡内の核子の進化は、ホップを生じるために、それが属する点を隣接させることからなる。このために、演算処理時間を制限するため、多面体の場合において使用されたものと類似する近接マップを、事前の計算の段階で生成する必要がある。無作為交換の変異誘発因子の条件は、自明である。それは単に、パラメータｐ1およびｐ2を無作為に更新することからなる。
【０１４３】
図２３は、Ｇｅｏｍｅｔｒｙ1およびＧｅｏｍｅｔｒｙ2と名付けられたボクセル幾何学的配置により描かれたオブジェクトを例示する。
【０１４４】
ボクセルに関して、パイオンの遺伝子型を定義するために、核子の各々は、識別子υ1、それが属するボクセルの個々のυ2により、以下のように同定される。
【数２１】
2008507056.tif 000024
【０１４５】
しかしながら、事前に定義されたように遺伝子型は、特定の場合（異なるサイズのボクセルまたはそれが大きすぎる）において不適切であることを立証する。次いで、それは、個々のボクセル内で核子の座標に関してそれらを質を高める必要があることを立証し得る。
【０１４６】
ボクセルに関して、変異誘発因子は、以下のように定義され得る。
【０１４７】
不連続探索：核子は、事前に計算された近接マップを用いて、ボクセルからボクセルへと移動される。
連続的探索：ボクセルが大きいと判明する場合、核子は、それに属するボクセルの表面上を移動され得る（ボクセル内のその座標の確立論的変化）。
確率論的探索：制限された振幅を連続的に探索する。
決定論的探索：２つの立方体間の最小距離を「実体化する」エッジは、決定論的手段によって決定するために、自明である。ここで、決定論的な探索は、ボクセルのペア内でパイオンを局所的に最小化することからなる。
無作為交換：新ボクセルを無作為に選択する。
【０１４８】
多面体の幾何学的配置を関して上に定義された交差オペレータがまた、パラメータ化された表面、点郡、またはボクセルの形態における表示で提示された全ての遺伝子型に、完璧に適合することを留意されたい。
【０１４９】
図２４は、概して、２つのパイオンＰａｒｅｎｔ1およびＰａｒｅｎｔ2から、パイオンＰａｒｅｎｔ1の第１核子Ｎｕｃｌｅｏｎ1およびパイオンＰａｒｅｎｔ2の第２核子Ｎｕｃｌｅｏｎ2から構成されるパイオンＣｈｉｌｄを生成するための、交差オペレータを表す。
【０１５０】
今しがた定義された遺伝子型および変異誘発因子は、異なる型の選択された幾何学的配置内における核子の定義および進化に適した形式の形態をとる。
【０１５１】
しかしながら、上記方法を用いるコンテキストにおいて、パイオンの特性を評価することは、結局、それの構成する核子を分離するユークリッド距離を評価することになることを留意してもよい。
【０１５２】
したがって、このことは、同じシミュレーション内で操作される異なる型の幾何学的配置に関して、異なる種類の核子から構成されるハイブリッド核子を考慮にいれることが、図２５に示されるように、完全に可能である。ここで、一例として、第１のオブジェクトの多面体表示「メッシュ（Ｍｅｓｈ）」、点郡の形態の第２のオブジェクトの表示「郡（Ｃｌｏｕｄ）」、第３のオブジェクトのボクセル表示「ボクセル（Ｖｏｘ）」、および、パラメータ化された表面の形態の第４のオブジェクトの表示「パッチ（Ｐａｔｃｈ）」が見られ、第１のパイオンＰｉｏｎ1が幾何学的表示「ボクセル」および「パッチ」に属し、第２のパイオンＰｉｏｎ2が幾何学的表示「パッチ」および「郡」に属し、第３のパイオンＰｉｏｎ3が幾何学的表示「メッシュ」および「郡」に属する状態で見られる。これは、これら３つパイオンのついての以下の遺伝子型をもたらす。
【数２２】
2008507056.tif 000025
【０１５３】
図２６は、Ｐ≧２において、Ｐ個のグラフィックシミュレーション化オブジェクト間の近接領域の同定のための本発明に従うシステムの例をブロック図形式で示す。
【０１５４】
このシステムは、メモリ領域１１１，１１２，１１３を有する記憶手段１１０を備える。
【０１５５】
第１のメモリ領域１１１は、Ｐグラフィックシミュレーション化オブジェクトの各々の幾何学的配置を記述するデータを記憶する。
【０１５６】
第２のメモリ領域１１２は、連結マップを表し、各Ｐオブジェクト内の隣接性を定義する情報を記憶する。
【０１５７】
第３のメモリ領域１１３は、近接マップを表し、各Ｐオブジェクト内の近接性を定義する情報を記憶する。
【０１５８】
初期化モジュール１２０は、Ｐオブジェクトのうちの１つとＰオブジェクトのうちの別の１つの各々の幾何学的配置に属する、第１の点もしくは核子および第２の点もしくは核子よって各々が定義される、Ｎパイオンのセットから構成される集団を作成する。
【０１５９】
ディスプレイスクリーン１３０は、必要に応じて、Ｐデジタルシミュレーション化オブジェクトを表示する。
【０１６０】
中央演算処理装置１４０は、以下の１４１から１４５までのサブシステムを備える。
トーナメントのセッションの間に、２つのＮパイオンにより２つのコンバットに供するＮパイオンの集団の割合を選択するための手段１４１
上記トーナメントのセッションの間に、コンバットに供されるパイオンの各ペアについて、適性基準に基づいて上記パイオンペアの各パイオンの特性を評価するための比較および計算手段１４２
上記トーナメントの各セッションにおいて、コンバットに供されたパイオンペアのどのパイオンが勝ったか、コンバットに供された上記パイオンペアのどのパイオンが負けたのかを同定するためのマーク付け手段１４３
少なくとも１つのコンバットに供された上記パイオンの進化を生成するための繰り返し手段１４４
少なくとも２つの上記Ｐオブジェクト間の近接領域を決定するため、上記適性基準の関数として上記集団から最良のパイオンのみを保持するための抽出モジュール１４５
【０１６１】
繰り返し手段１４４は、上記トーナメントの第１セッションの間に負けたパイオンを探索的に変異させるオペレータ、上記トーナメントの第２セッションの間に負けたパイオンを、無作為に選択されたパイオンを交差させることで交換するオペレータ、および、上記トーナメントの第３セッションの間に負けたパイオンを再定義するためのオペレータと関連する。
【０１６２】
リファレンス１５０は、例えば、トーナメントおよび進化プロセスの繰り返し実行の間、選択され保持されたパイオンを探索するための触覚インターフェースのような、オプションのインターフェースを示す。
【０１６３】
本発明は、個体の処理の独立性が要因で時間がかかるソート段階を省略していることに留意されたい。これにより、複数のマイクロプロセッサまたはマイクロコントローラに計算を分配する可能性、ならびに、パイオンの各核子をオブジェクトの幾何学的配置の１つの型から別の型へと伝えることで、操作における高い柔軟性を与える可能性を有する並列化に非常に適しているプロセスの使用を実現する。
【０１６４】
個体の集団は、例えば、数百の個体を含み得る。
【図面の簡単な説明】
【０１６５】
【図１】図１は、バーチャルリアルティのプラットフォームの機能アーキテクチャを表すブロック図である。
【図２】図２は、仮想世界に含まれるオブジェクトの物理法則に従う動的進化を示すフローチャートである。
【図３】図３は、多面体型の２つのオブジェクト間の最小距離を計算する既知の方法を例示する図である。
【図４】図４Ａ、図４Ｂ、および図４Ｃは、境界ボリュームによるオブジェクトの近似の３つの例を示す。
【図５Ａ】図５Ａは、並進における球オブジェクトの初期位置と最終位置を示す。
【図５Ｂ】図５Ｂは、図５Ａのオブジェクトの並進に対応する掃き出されたボリュームを示す。
【図６】図６は、オブジェクトのボクセル分解の一例を示す。
【図７Ａ】図７Ａは、点郡および法線の形態で描かれた別のオブジェクトに対応する、ボクセル形態でのオブジェクトのハイブリッド表示の一例を示す。
【図７Ｂ】図７Ｂは、図７Ａのハイブリッド様式で描かれた２つのオブジェクトの相互作用領域を詳細に示す。
【図８】図８は、ペナルティー法に従って反発力に供される２つのオブジェクトの表示を示す。
【図９】図９は、本発明において使用される個々の遺伝子型またはパイオンを示す図である。
【図１０】図１０は、変異のコンテキストにおいて多面体上の点の不連続な探索的転移の例を示す。
【図１１】図１１は、変異のコンテキストにおいて関与する開拓オペレータ（ｅｘｐｌｏｉｔａｔｉｏｎ  ｏｐｅｒａｔｏｒ）の例を示す。
【図１２Ａ】図１２Ａは、多面体形態で描かれたオブジェクトにおける、近接要素の同定を示す。
【図１２Ｂ】図１２Ｂは、図１２Ａに描かれたオブジェクトにおいてワームホールがない状態の経路の例を示す。
【図１２Ｃ】図１２Ｃは、図１２Ａに描かれたオブジェクト内のワームホールを通る経路の例を示す。
【図１３】図１３は、２つのパイオンの交差の原理を表す。
【図１４】図１４は、本発明に従う方法の３つの主要な段階を表す。
【図１５】図１５Ａ、図１５Ｂ、および図１５Ｃは、パイオンを構成する２つの点に属するオブジェクトの多面体表示における２つの三角形間の最小距離を定義するエッジを実体化する幾何学的構成の例を３つ示す。
【図１６】図１６は、相互作用する２つのオブジェクトを表す多面体に属する２つの三角形の間における最小距離を定義するエッジの決定のコンテキストにおいて、三角形を含む平面へ向けたエッジの射影を示す。
【図１７】図１７は、図１６に描かれたプロセスについて、点からエッジまでの最小距離を定義するエッジの決定を、示す。
【図１８】図１８は、図１６に描かれたプロセスについて、エッジからエッジまでの最小距離を定義するエッジの決定を示す。
【図１９】図１９は、異なるオブジェクトを表す異なる多面体間で定義されたいくつかのパイオンの遺伝型を表す。
【図２０】図２０は、多面体形態で描かれたオブジェクトについて、パイオンの無作為交換を示す。
【図２１】図２１は、２つのオブジェクトを表すパラメータ化された表面の間で定義されたパイオンの遺伝子型を示す。
【図２２】図２２は、２つのオブジェクトを表す２つの点群の間で定義されたパイオンの遺伝子型を示す。
【図２３】図２３は、ボクセル表示の２つのオブジェクト間で定義されたパイオンの遺伝子型を示す。
【図２４】図２４は、交差オペレータの関数を示す。
【図２５】図２５は、オブジェクトを表す異なる型の幾何学的配置間で定義されたハイブリッドパイオンを表す。
【図２６】図２６は、本発明に従うシステムの一例を構成する主要なモジュールを示すブロック図である。
【図１】
2008507056.tif 000026
【図２】
2008507056.tif 000027
【図３】
2008507056.tif 000028
【図４】
2008507056.tif 000029
【図５Ａ】
2008507056.tif 000030
【図５Ｂ】
2008507056.tif 000031
【図６】
2008507056.tif 000032
【図７Ａ】
2008507056.tif 000033
【図７Ｂ】
2008507056.tif 000034
【図８】
2008507056.tif 000035
【図９】
2008507056.tif 000036
【図１０】
2008507056.tif 000037
【図１１】
2008507056.tif 000038
【図１２Ａ】
2008507056.tif 000039
【図１２Ｂ】
2008507056.tif 000040
【図１２Ｃ】
2008507056.tif 000041
【図１３】
2008507056.tif 000042
【図１４】
2008507056.tif 000043
【図１５】
2008507056.tif 000044
【図１６】
2008507056.tif 000045
【図１７】
2008507056.tif 000046
【図１８】
2008507056.tif 000047
【図１９】
2008507056.tif 000048
【図２０】
2008507056.tif 000049
【図２１】
2008507056.tif 000050
【図２２】
2008507056.tif 000051
【図２３】
2008507056.tif 000052
【図２４】
2008507056.tif 000053
【図２５】
2008507056.tif 000054
【図２６】
2008507056.tif 000055
【国際調査報告】
2008507056.tif 000056
2008507056.tif 000057
2008507056.tif 000058
2008507056.tif 000059