(57)【要約】      （修正有）【課題】３Ｄシーンを複数のゾーンに区分化するためのコンピュータによって実行される方法を提供する。【解決手段】各オブジェクトは、コンピューティングリソースコストを発生させるステップと、計算コストの密度を表す第１のマップを計算するステップと、取得されるゾーンの形状に対する制約を表す第２のマップを定義するステップと、３Ｄシーン内において潜在的に移動することができる動的オブジェクトのない３Ｄシーンの空間量子化を計算することによって、セルに離散化するステップと、各セルについて、第１のマップから計算コストを計算するステップと、第２のマップに従って、セルを集約し、そのゾーンに属するセルの計算コストの合計である計算コストを有し、コンピューティングリソース上におけるゾーンのリアルタイムシミュレーションを可能にするステップとを含む。【選択図】図１
2018116695.tif 000002
【特許請求の範囲】
【請求項１】
３Ｄシーンを複数のゾーンに区分化するためのコンピュータによって実行される方法であって、各ゾーンは、前記３Ｄシーンのエリアまたは量を表し、コンピューティングリソースによって処理され、
１つまたは複数のオブジェクトを含む３Ｄシーンを提供するステップであって、各オブジェクトは、コンピューティングリソースコストを発生させる、ステップ（Ｓ１０）と、
前記提供された３Ｄシーンの計算コストの密度を表す第１のマップを計算するステップ（Ｓ２０）と、
前記３Ｄシーンの区分化の結果として取得されるゾーンの形状に対する制約を表す第２のマップを定義するステップ（Ｓ３０）と、
動的オブジェクトのない前記３Ｄシーンの空間量子化を計算することによって、前記提供された３Ｄシーンをセルに離散化するステップであって、動的オブジェクトは、前記３Ｄシーン内において潜在的に移動することができるオブジェクトである、ステップ（Ｓ４０、Ｓ４２）と、
セルごとに、前記３Ｄシーンの前記第１のマップから計算コストを計算するステップ（Ｓ５０）と、
前記第２のマップに従って、前記セルを１つまたは複数のゾーンに集約するステップであって、各ゾーンは、前記ゾーンに属する前記セルの前記計算コストの合計である計算コストを有し、前記ゾーンの前記計算コストは、コンピューティングリソース上における前記ゾーンのリアルタイムシミュレーションを可能にする、ステップ（Ｓ７０）と
を備えることを特徴とするコンピュータによって実行される方法。
【請求項２】
１つまたは複数のゾーンへの前記セルの前記集約は、組み合わせ最適化アルゴリズムを使用してさらに実施されることを特徴とする請求項１に記載のコンピュータによって実行される方法。
【請求項３】
前記組み合わせ最適化アルゴリズムは、蟻コロニアルゴリズムであることを特徴とする請求項２に記載のコンピュータによって実行される方法。
【請求項４】
前記セルの前記集約の前に、
前記第２のマップに従って、１つまたは複数のセルの１つまたは複数のクラスタを計算するステップ（Ｓ６０）
をさらに備え、
前記集約するステップ（Ｓ７０）は、前記クラスタを１つまたは複数のゾーンに集約するステップを含み、各ゾーンは、前記ゾーンに属する前記セルの前記計算コストの前記合計である計算コストを有し、前記ゾーンの前記計算コストは、コンピューティングリソース上における前記ゾーンのリアルタイムシミュレーションを可能にする
ことを特徴とする請求項１乃至３のいずれか一項に記載のコンピュータによって実行される方法。
【請求項５】
前記第２のマップ上において表される前記ゾーンの前記形状に対する前記制約は、
前記３Ｄシーン内において前記３Ｄシーンの１つまたは複数の静的オブジェクトを識別するステップであって、静的オブジェクトは、前記３Ｄシーンにおいて移動することができず、別のオブジェクトによってトラバースすることができないオブジェクトである、ステップと、
識別された静的オブジェクトごとに、１つまたは複数のセルの１つまたは複数のクラスタを生成するルールと関連付けられたジオメトリを計算するステップと
によって取得されることを特徴とする請求項１乃至４のいずれか一項に記載のコンピュータによって実行される方法。
【請求項６】
セルのクラスタを生成するためのジオメトリとルールとの前記関連付けは、
前記ジオメトリはポリゴンであり、および前記ルールは前記ポリゴンに含まれる前記セルのクラスタを生成することと、
前記ジオメトリはポリゴンであり、ならびに前記ルールはベクトルによって表される方向および大きさに従って前記ポリゴンから延在する前記セルのクラスタを生成することと、
前記ジオメトリはポリラインであり、および前記ルールは前記ポリラインに隣接するセルごとにクラスタの前記生成をトリガすることと
のうちの１つであることを特徴とする請求項５に記載のコンピュータによって実行される方法。
【請求項７】
前記３Ｄシーン内における前記３Ｄシーンの１つまたは複数の静的オブジェクトの前記識別は、ユーザの動作のときに実行されることを特徴とする請求項５または６に記載のコンピュータによって実行される方法。
【請求項８】
計算されたジオメトリとのルールの前記関連付けは、ユーザの動作のときに実行されることを特徴とする請求項６または７に記載のコンピュータによって実行される方法。
【請求項９】
前記提供された３Ｄシーンの計算コストの密度を表す前記第１のマップの前記計算は、
前記３Ｄシーン内における位置のセットを決定することと、
各位置を、最も高価な計算コストに達するそれを最大限占有するオブジェクトで満たすことと、
前記３Ｄシーンの位置ごとに、最大計算コストを計算することと、
位置ごとに、比Ｐ／Ａを計算することであって、Ｐは、前記位置を処理するために必要とされるコンピューティングリソースの測定された割合であり、Ａは、前記３次元シーン内における前記位置の面積である、ことと
を含むことを特徴とする請求項１乃至８のいずれか一項に記載のコンピュータによって実行される方法。
【請求項１０】
各位置を、それを最大限占有するオブジェクトで満たすことは、動的オブジェクトに対して実行されることを特徴とする請求項９に記載のコンピュータによって実行される方法。
【請求項１１】
前記３Ｄシーンの前記空間量子化の前記計算は、
関係Ｓq＝（ＣＰＵCA）／（計算コストの密度）Max
によって定義される表面量子を計算することであって、（ＣＰＵCA）は、前記ゾーンを処理するためのコンピュータリソースコストの正確度を表し、（計算コストの密度）Maxは、前記第１のマップ上において表された最高密度である、ことと、
前記提供された３Ｄシーンをセルに離散化することであって、各セルは、前記表面量子Ｓqに等しいサイズを有する、ことと
を含むことを特徴とする請求項１乃至１０のいずれか一項に記載のコンピュータによって実行される方法。
【請求項１２】
セルごとに、前記３Ｄシーンの前記第１のマップから計算コストを計算するステップは、前記表面量子Ｓqと前記セルの計算コストの密度との間の積を計算するステップを含むことを特徴とする請求項１０に記載のコンピュータによって実行される方法。
【請求項１３】
前記組み合わせ最適化アルゴリズムの目的関数は、少なくとも、
１つまたは複数のゾーンへの前記セルの新たな集約の結果として、ゾーンの数Ｎが増加したときに、
ゾーンの前記形状が、鋸歯状の境界であるときに、
非連結なゾーンの数が、ゼロよりも大きいときに、
増加するように定式化される請求項２乃至１１のいずれか一項に記載のコンピュータによって実行される方法。
【請求項１４】
請求項１乃至１３のいずれか一項に記載の方法を実行するための命令を含むことを特徴とするコンピュータプログラム。
【請求項１５】
メモリおよびグラフィカルユーザインターフェースに結合されたプロセッサを備え、前記メモリは、請求項１４に記載のコンピュータプログラムを記憶していることを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータプログラミングおよびシステムの分野に関し、より詳細には、３次元シーンを複数のゾーンに区分化（partition）するための方法、システム、およびプログラムに関し、各ゾーンは、コンピューティングリソースによって処理される。
【背景技術】
【０００２】
３Ｄシミュレーションは、過去３０年の間に、様々な大勢のユーザの視聴者たちの中で大きな成功を収めており、そのようなユーザは、設計段階のシステムが現実にどのように振る舞うかを確認する技術者から、論理的概念を探求または実証する科学者、ビデオゲームをプレイする、または３Ｄアニメーション映画を楽しむ大衆までわたる。３Ｄシミュレーションは、過去３０年にわたって、多くの進化を遂げており、成長の勢いを今でも有している。特に、３Ｄシミュレーションは、より複雑でより現実的な挙動（多体剛体力学、人間のシミュレーション、衣服のシミュレーション、粒子シミュレーションなど）に対する、オブジェクトのより大きい集団およびトポロジに対する、ならびにより大きいスケールに対するユーザの必要性に応えることを目指している。
【０００３】
３Ｄシミュレーションは、リアルタイム要件を満たさなければならず、それは、より具体的には、大規模な仮想世界において対話する非常に多くのユーザをサポートするための特定の技術を開発することによって、ビデオゲーム業界において開始された。接続されたユーザの数にかかわらず、またアプリケーションの解決およびレンダリングのために生じる計算コストにかかわらず、ユーザには、リアルタイム応答が常に提供されなければならない。
【０００４】
超マルチユーザオンラインアプリケーション（ＭＭＯ：Massively Multi-user On line application）は、多くのユーザが、現実世界現象シミュレータ（real-world phenomena simulator）、および没入型アプリケーション（immersive application）などの、アプリケーションを同時に使用することを可能にする。同様に、超マルチユーザオンラインゲーム（ＭＭＯＧ：Massively Multi-user Online Game）は、多くのゲーマが同時にビデオゲームをできることを可能にする。ＭＭＯおよびＭＭＯＧは、ユーザまたはゲーマが、アプリケーションまたはビデオゲームに接続することを可能にするために、コンピュータネットワーク、例えば、インターネットに大きく依存している。本明細書全体において、「アプリケーション」および「ビデオゲーム」という語は、同義語であるとして理解され、ＭＭＯおよびＭＭＯＧという用語は、区別せずに使用される。
【０００５】
ＭＭＯは、ユーザまたはゲームプレイヤに対してより現実的な体験を提供するために、できるだけ詳細かつできるだけリアルタイムに近い時間でレンダリングされることが望まれる、複雑で大規模な仮想環境を伴う。ＭＭＯは、３Ｄシーンの表現および操作のために特に設計され、対話型の順次的なリアルタイム３Ｄシーン生成を必要とするアプリケーションのために、エンドユーザのコンピュータ上において一般に使用される。ユーザが、３Ｄシーンと対話している間、コンピュータは、ユーザが参加しているのが連続的で進行中の現実であるという感覚をユーザに与えるのに十分な速さで、３Ｄ表現を再描画（redraw）していく。シーンは、３Ｄシーンと対話するときに、ユーザによって操作することができる多くの個別のオブジェクトから構成される。したがって、ＭＭＯは、空間的に複雑かつきわめて詳細な仮想環境にリアルタイムに参加する多数のユーザを管理するために、大規模なデータ量、高いデータレート、および高いデータ複雑度が、一般に必要とされることを伴う。
【０００６】
ＭＭＯは、コンピュータモデル内において現実世界現象をシミュレートするために、例えば、多体剛体力学、人間のシミュレーション、衣服のシミュレーション、粒子シミュレーションを行うために一般に使用される。シミュレーションは、プロセスのシミュレーションおよび使用中製品のシミュレーションを生成するために、製造プロセスにおいて使用される材料および製品の物理的特性（強度、弾性など）などの現実世界現象を記述する、正確なデータおよびアルゴリズムを必要とする。３Ｄ  ＣＡＤ／ＣＡＭ（コンピュータ支援設計、コンピュータ支援製造）ツールが、製品または構成部品の３Ｄ表現を生成することを可能にする。ＭＭＯは、３Ｄエクスペリエンスとも呼ばれ、すなわち、技術者がオブジェクトの挙動を研究する仮想環境であり、一般に、シミュレートされる環境は、製造業環境である。「３Ｄシーン」および「３Ｄエクスペリエンス」という表現は、同義語である。
【０００７】
ＭＭＯは、ＭＭＯＧと同様に、絶え間なく変化する作業負荷に動的に適合し、その結果、リアルタイム性能を維持するために、スケーラブルでなければならない。スケーラビリティは、特に、アプリケーションを同時に使用することができるユーザの数、シミュレーションを計算するためのコンピューティングリソースの数、およびアプリケーションによって可能にされる３Ｄシーンのオブジェクト間における同時対話の数などを含む。
【０００８】
ＭＭＯＧの場合、ユーザの数は、全ての含まれる動的オブジェクトの位置的およびグラフィカルな属性と共に著しく変動することがあり、動的オブジェクトは、シーン内において移動する可能性のあるオブジェクトである。それにもかかわらず、周囲のシーナリ（scenery）は、ただ１回限り設定され、動的オブジェクトのトポロジ、およびサポートされる挙動クラスは、ゲームが開始する前に、事前定義される。言い換えると、ＭＭＯＧにおける３Ｄシーンは、コンピューティングリソースの必要性を著しく制限する多数の事前決定された特性を含み、その結果、スケーラビリティを改善する。したがって、コンピューティングリソースの必要性を予測することが、可能である。
【０００９】
対照的に、進化型ＭＭＯの場合、３Ｄシーンのシーナリおよび集団トポロジ（population typology）は、特にアプリケーションが動作している間に、進化し、豊かになることがある。実際に、ＭＭＯは、オブジェクトの挙動が動的であり、事前定義された挙動クラスを排除する、現実世界現象をシミュレートすることを目指している。結果として、ＭＭＯにおける３Ｄシーナリは、ＭＭＯＧの場合のように事前定義された特性を使用することができない。
【００１０】
したがって、３Ｄエクスペリエンスが、ＭＭＯＧと同一の種類のリアルタイムおよび多さについての制約を有する場合であっても、それは、はるかに精巧、現実的かつ正確な物理的挙動についての特定の厳格な要件を有し、したがって、計算能力を要求する。
【００１１】
単一のコンピューティングリソースは、計算を解決することの全てをリアルタイムに対処することはできず、それが理由で、並列化技術が必要とされる。簡潔に言うと、３Ｄエクスペリエンスは、いわゆるゾーン（パーツとも呼ばれる）に区分化され、ゾーンの各々は、３Ｄエクスペリエンスの特定の空間領域を取り扱う。これらのゾーンのサイズは、ゾーンをコンピューティングリソースによってリアルタイムに計算することができるかどうかを決定するので重要である。３Ｄシーン（３Ｄエクスペリエンスとも呼ばれる）がパーツに分けられる（divide）方法、すなわち、ゾーンがどのように区切られる（delimit）かはが基本原理（primordial）である。
【００１２】
ゾーンを区切るときに最も重要な要件は、各ゾーンのシミュレーションが、リアルタイム性を達成するために負荷をコンピューティングリソースの１００％を厳格に下回るようにし、例えば、セキュリティマージンを保つために９５％を下回るようにすることである。３Ｄエクスペリエンスに適切なほぼ無限のゾーンが存在するが、そのうちの僅かのみが、最適数の、すなわち、最小数のパーツを提供せず、それらに対しては、シミュレーションをリアルタイムに実行するのに、まさに同数のコンピューティングリソースで十分である。この選択を人手で実行することは、膨大な時間を費やす作業であり、必ずしも全ての解が人手で探索され得ないとは限らないので効率的ではなく、したがって、最小数のゾーンを有する最良の解は、それらの選択が人手で実行されるときは、妥当な時間枠内において取得されないことがある。
【００１３】
この問題は、全ての可能性を探索して、基準に最も良く一致する１つを探し出すために、解を特徴付けるパラメータが、連続的かつ同時に調整される（tune）、連続問題として定式化されることがある。適用可能であるとき、この選択肢は、最も効率的で、最も品質の良い技術である。しかしながら、いくつか少数の特徴付け（例えば、パーツの数、それらがポリゴンであるように選択されたケースにおける境界点の数など）は、本質的に連続ではなく、ごく普通の関連技術は、追加の高価なアーチファクトを必要とし、この問題を解くのに実用的ではないことが分かる。
【００１４】
このコンテキストの中で、コンピューティングリソースによって処理される３Ｄシーンの複数のゾーンへの区分化を改善するための、改善された方法、コンピュータプログラム、およびシステムに対する必要性が、依然として存在する。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】欧州特許出願公開第２７４５８９２号明細書
【発明の概要】
【００１６】
したがって、３Ｄシーンを複数のゾーンに区分化するためのコンピュータによって実行される方法が提供される。各ゾーンは、３Ｄシーンのエリアまたは量（volume）を表し、コンピューティングリソースによって処理される。方法は、１つまたは複数のオブジェクトを含む３Ｄシーンを提供するステップであって、各オブジェクトは、コンピューティングリソースコストを発生させる、ステップと、提供された３Ｄシーンの計算コストの密度を表す第１のマップを計算するステップと、３Ｄシーンの区分化の結果として取得されるゾーンの形状に対する制約を表す第２のマップを定義するステップと、動的オブジェクトのない（free of）３Ｄシーンの空間量子化を計算することによって、提供された３Ｄシーンをセルに離散化するステップであって、動的オブジェクトは、３Ｄシーンにおいて潜在的に移動ことができるオブジェクトである、ステップと、セルごとに、３Ｄシーンの第１のマップから計算コストを計算するステップと、第２のマップに従って、セルを１つまたは複数のゾーンに集約するステップであって、各ゾーンは、そのゾーンに属するセルの計算コストの合計である計算コストを有し、ゾーンの計算コストは、コンピューティングリソース上のゾーンのリアルタイムシミュレーションを可能にする、ステップと、を備える。
【００１７】
実施例においては、方法は、
１つまたは複数のゾーンへのセルの集約は、さらに、組み合わせ最適化アルゴリズムで実行されることと、
組み合わせ最適化アルゴリズムは、蟻コロニアルゴリズムであることと、
セルの集約の前に、第２のマップに従って、１つまたは複数のセルの１つまたは複数のクラスタを計算することであって、集約することは、クラスタを１つまたは複数のゾーンに集約することを含み、各ゾーンは、ゾーンに属するセルの計算コストの合計である計算コストを有し、ゾーンの計算コストは、コンピューティングリソース上のゾーンのリアルタイムシミュレーションを可能にする、ことと、
第２のマップ上で表されるゾーンの形状に対する制約は、３Ｄシーンにおいて３Ｄシーンの１つまたは複数の静的オブジェクトを識別することであって、静的オブジェクトは、３Ｄシーン内において移動することができず、別のオブジェクトによってトラバースすることができないオブジェクトである、ことと、識別された静的オブジェクトごとに、１つまたは複数のセルの１つまたは複数のクラスタを生成するルールと関連付けられたジオメトリを計算することとによって取得されることと、
ジオメトリとセルのクラスタを生成するルールとの関連付けは、ジオメトリがポリゴンであり、およびルールがポリゴンに含まれるセルのクラスタを生成することと、ジオメトリがポリゴンであり、およびルールがベクトルによって表される方向および大きさ（magnitude）に従ってポリゴンから延在するセルのクラスタを生成することと、ジオメトリがポリライン（polyline）であり、およびルールがポリラインに隣接するセルごとにクラスタの生成をトリガすることと、うちの１つであること、
３Ｄシーンにおける３Ｄシーンの１つまたは複数の静的オブジェクトの識別は、ユーザの動作のときに実行されることと、
計算されたジオメトリとのルールの関連付けは、ユーザの動作のときに実行されることと、
提供された３Ｄシーンの計算コストの密度を表す第１のマップの計算は、３Ｄシーンにおける位置のセットを決定することと、各位置を、最も高価な計算コストに達するそれを最大限占有するオブジェクトで満たすことと、３Ｄシーンの位置ごとに、最大計算コストを計算することと、を含むことと、
位置ごとに、比Ｐ／Ａを計算することであって、Ｐは、その位置を処理するために必要とされるコンピューティングリソースの測定割合であり、Ａは、３次元シーンにおける位置のエリアである、ことと、
各位置を、それを最大限占有するオブジェクトで満たすステップは、動的オブジェクトに対して実行されることと、
３Ｄシーンの空間量子化の計算は、関係Ｓq＝（ＣＰＵCA）／（計算コストの密度）Max
によって定義される表面量子（surface quantum）Ｓｑを計算することであって、（ＣＰＵCA）は、ゾーンを処理するためのコンピュータリソースコストの正確度を表し、（計算コストの密度）Maxは、第１のマップ上で表された最高密度である、ことと、提供された３Ｄシーンをセルに離散化することであって、各セルは、表面量子Ｓｑに等しいサイズを有する、ことと、を含むことと、
セルごとに、３Ｄシーンの第１のマップから計算コストを計算することは、表面量子Ｓｑとセルの計算コストの密度との間の積を計算するステップを含むことと、
少なくとも、１つまたは複数のゾーンへのセルの新たな集約の結果としてゾーンの数Ｎが増加したときに、ゾーンの形状が鋸歯状の境界（jagged border）であるときに、非連結なゾーンの数がゼロよりも大きいときに、組み合わせ最適化アルゴリズムの目的関数が増加するように定式化されることと、
のうちの１つまたは複数を備えてもよい。
【００１８】
方法を実行するための命令を含むコンピュータプログラムがさらに提供される。
【００１９】
方法を実行するための命令を含むコンピュータプログラムがさらに提供される。
【００２０】
コンピュータプログラムを記録したコンピュータ可読記憶媒体がさらに提供される。
【００２１】
メモリに結合されたプロセッサを備えるシステムがさらに提供され、メモリは、コンピュータプログラムを記録している。
【００２２】
本発明の実施形態が、添付の図面を参照して、非限定的な例として、今から説明される。
【図面の簡単な説明】
【００２３】
【図１】方法の実施例のフローチャートである。
【図２】３Ｄエクスペリエンスの実施例を示す図である。
【図３】図２のコスト密度のマップの実施例を示す図である。
【図４】図２の制約のマップの実施例を示す図である。
【図５】セルに離散化された図３のマップの実施例を示す図である。
【図６】コスト密度マップを形成する図３のマップの実施例を示す図である。
【図７】３Ｄエクスペリエンスにおいて識別することができる制約のタイプの実施例を示す図である。
【図８】セルのクラスタに離散化された図４のマップの実施例を示す図である
【図９】システムの実施例を示す図である。
【発明を実施するための形態】
【００２４】
図１のフローチャートを参照すると、３次元（３Ｄ）シーンを複数のゾーンに区分化するためのコンピュータによって実行される方法が提案される。したがって、３Ｄシーンは、ゾーンのセットに区分化される。セットのうちの各ゾーンは、３Ｄシーンのエリアまたは３Ｄシーンの量を表す。各ゾーンは、コンピューティングリソースによって処理される。実際には、各ゾーンはソルバに割り当てられ、各ソルバは自らのコンピューティングリソース上において動作し、コンピューティングリソースは、ＣＰＵ上、マルチコアＣＰＵ上の解決スレッド（solving thread）、マルチＣＰＵコンピュータ上のプロセス、サーバＣＰＵ上のサーバプロセスなどであってもよいが、それらに限定されない。したがって、「ソルバ」および「コンピューティングリソース」の概念は、負荷および性能に関して厳格に等価である。したがって、用語「ソルバ」および表現「コンピューティングリソース」は、本発明においては同義語である。方法は、１つまたは複数のオブジェクトを含む３Ｄシーンを提供するステップを含む。各オブジェクトは、例えば、３Ｄシーンにおいてオブジェクトをインスタンス化するために、および３Ｄシーンにおけるオブジェクトの表現を計算するためになど、コンピューティングリソースコストを発生させる。方法は、提供された３Ｄシーンの計算コストの密度を表す第１のマップを計算するステップをさらに含む。方法は、例えば、ユーザの動作のときに、３Ｄシーンの区分化の結果として取得されるゾーンの形状に対する制約を表す第２のマップを定義するステップを含む。方法はまた、３Ｄシーンにおいて潜在的に移動することができるオブジェクトである動的オブジェクトのない３Ｄシーンの空間量子化を計算することによって、提供された３Ｄシーンをセルに離散化するステップを含む。方法は、第１のマップから各セルの計算コストを計算するステップをさらに含む。方法さらには、第２のマップに従って、セルを１つまたは複数のゾーンに集約するステップを含む。各ゾーンは、ゾーンに属する１つまたは複数のセルの計算コストの合計である計算コストを有する。ゾーンの計算コストは、コンピューティングリソース上のゾーンのリアルタイムシミュレーションを可能にし、言い換えると、時間ステップにおける３Ｄシーンのシミュレーションの計算は、常に新たな時間の開始の前に行われる。
【００２５】
そのような方法は、コンピューティングリソースによって処理される３Ｄシーンの複数のゾーンへの区分化を改善する。特に、第１および第２のマップは、３Ｄシーンから抽出された情報の表現を提供する。抽出された情報は、例えば、３Ｄシーンの静的オブジェクトなどの３Ｄシーンの本質的特徴、および３Ｄシーンをシミュレートするためのコンピューティングリソース上における計算コストなどの３Ｄシーンの付帯的特徴に関する３Ｄシーンの最小離散化を計算することを可能にする。３Ｄシーンのこの最小離散化は、セルの集約の組み合わせの数を減少させることを可能にする。この方法によって、最小数のゾーンを使用する最良の解を、組み合わせ手法の使用による結果として取得することができ、解は、膨大な数の有限個の特定の要素の配置として定式化されてもよい。妥当な時間フレーム内で解を取得することができ、区分化は、自動的に、すなわち、いかなるユーザ介入がなく実施されてもよい。本発明のさらなる利点が説明される。
【００２６】
方法は、コンピュータによって実行される。これは、方法のステップ（または実質的に全てのステップ）が、少なくとも１つのコンピュータまたは同様の任意のシステムによって実行されることを意味する。したがって、方法のステップは、コンピュータによって、場合によっては完全に自動的または半自動的に実行される。実施例においては、方法のステップの少なくともいくつかのトリガは、ユーザ−コンピュータ対話を通じて実行されてもよい。必要とされるユーザ−コンピュータ対話のレベルは、予想される自動化のレベルに依存してもよく、ユーザの要求を実現するための必要性とのバランスを考慮してもよい。実施例においては、このレベルは、ユーザによって定義および／または事前に定義されてもよい。
【００２７】
例えば、３Ｄシーンを提供するステップは、ユーザ選択のときに実行されてもよく、ユーザは、キーボード、マウス、またはスタイラスなどの触覚デバイスを介して選択を実行してもよい。例えば、２つボタンのマウスにおいては、シーンのリスト内のシーンを選択するために左ボタンが使用されてもよい。システムは、デフォルトで、すなわちユーザ選択を必要とすることなくシーンを識別してもよい。
【００２８】
方法がコンピュータによって実行されることの典型的な例は、この目的のために適合されたシステムを使用して方法を実行することである。システムは、メモリおよびグラフィカルユーザインターフェース（ＧＵＩ）に結合されたプロセッサを備えてもよく、メモリは、方法を実行するための命令を含むコンピュータプログラムを記録している。メモリは、データベースを記憶してもよい。メモリは、場合によってはいくつかの物理的に異なる部分（例えば、プログラム用の１つと、場合によってはデータベース用の１つと）含むそのような記憶のために適合された任意のハードウェアである。
【００２９】
「データベース」は、検索および取り出しのために編成されたデータ（すなわち、情報）の任意の集合を意味する（例えば、事前決定された構造化言語、例えば、ＳＱＬに基づいた、例えば、リレーショナルデータベース）。メモリ上に記憶されるとき、データベースは、コンピュータによる迅速な検索および取り出しを可能にする。データベースは、実際に、様々なデータ処理操作に関連したデータの記憶、取り出し、変更、および削除を容易にするように構造化される。データベースは、ファイルまたはファイルのセットから構成されてもよく、ファイルはレコードに分解されてもよく、レコードの各々は１つまたは複数のフィールドから構成される。フィールドは、データ記憶の基本単位である。ユーザは、主にクエリを通じてデータを取り出してもよい。キーワードおよびソーティングコマンドを使用して、ユーザは、多くのレコード内のフィールドを迅速に検索、再配置、グループ化、および選択し、使用されているデータベース管理システムのルールに従って、データの特定の集約を取り出し、またはそれについてのレポート生成することができる。
【００３０】
本方法のケースにおいては、データベースは、３Ｄシーンおよび３Ｄシーンの１つまたは複数のオブジェクトを記憶してもよい。３Ｄシーンは、１つまたは複数のオブジェクトとは独立して、例えば、別のデータベース上に記憶されてもよい。データベースは、システムによる実行のための命令を含むコンピュータプログラムをさらに含んでもよい。命令は、本方法のステップを実行するように適合される。
【００３１】
方法は、一般に、３Ｄシーン内に存在するモデル化オブジェクトを操作する。３Ｄモデル化オブジェクトは３Ｄシーンを形成する。モデル化オブジェクトは、例えば、データベース内に記憶されたデータによって定義された任意のオブジェクトである。拡張によって、「モデル化オブジェクト」という表現は、データ自体を指定する。システムのタイプに従って、モデル化オブジェクトは、異なる種類のデータによって定義されてもよい。システムは、実際には、ＣＡＤシステム、ＣＡＥシステム、ＣＡＭシステム、ＰＤＭシステム、および／またはＰＬＭシステムの任意の組み合わせであってもよい。それらの異なるシステムにおいては、モデル化オブジェクトは、対応するデータによって定義される。したがって、ＣＡＤオブジェクト、ＰＬＭオブジェクト、ＰＤＭオブジェクト、ＣＡＥオブジェクト、ＣＡＭオブジェクト、ＣＡＤデータ、ＰＬＭデータ、ＰＤＭデータ、ＣＡＭデータ、ＣＡＥデータについて言及されてもよい。しかしながら、モデル化オブジェクトは、これらのシステムの任意の組み合わせに対応するデータによって定義されてもよいので、これらのシステムは他に対して排他的なものではない。システムは、３Ｄシーンおよび／または３Ｄモデル化オブジェクトがシミュレートまたは再生される、ＭＭＯまたはＭＭＯＧシステムであってもよい。ＭＭＯ／ＭＭＯＧシステムにおいて使用される３Ｄモデル化オブジェクトは、ＣＡＤシステムを使用して設計されてもよい。
【００３２】
ＣＡＤシステムはさらに、モデル化オブジェクトのグラフィカル表現に基づいてモデル化オブジェクトを少なくとも設計するように適合されたＣＡＴＩＡなどの任意のシステムを意味する。このケースにおいては、モデル化オブジェクトを定義するデータは、モデル化オブジェクトの表現を可能にするデータを含む。例えば、ＣＡＤシステムは、面（face）または表面（surface）を使用する特定ケースにおいては、エッジまたはラインを使用して、ＣＡＤモデル化オブジェクトの表現を提供してもよい。ライン、エッジ、または表面は、様々な方法で、例えば非一様有理Ｂスプライン（ＮＵＲＢＳ）で表されてもよい。特に、ＣＡＤファイルは、ジオメトリがそれから生成されてもよく、それは、次いで、生成される表現を有効にする仕様を含む。モデル化オブジェクトの仕様は、単一のＣＡＤファイルまたは複数のそれらの中に記憶されてもよい。ＣＡＤシステムにおけるモデル化オブジェクトを表すファイルの典型的なサイズは、パーツ当たり１メガバイトの範囲内にある。モデル化オブジェクトは、一般に、数千のパーツの集合体であってもよい。
【００３３】
本発明のコンテキストにおいては、モデル化オブジェクトは、一般に、例えば、パーツもしくはパーツの集合体、または場合によっては製品の集合体などの製品を表す、３Ｄモデル化オブジェクトであってもよい。「３Ｄモデル化オブジェクト」は、それの３Ｄ表現を可能にするデータによってモデル化された任意のオブジェクトを意味する。３Ｄ表現は、全ての角度からパーツを見ることを可能にする。例えば、３Ｄモデル化オブジェクトは、３Ｄ表現されたとき、その表現が表示された画面において操作されてもよく、それの軸のいずれかの周りまたは任意の軸の周りで回転してもよい。これは、特に、３Ｄモデル化されていない２Ｄアイコンを除外する。３Ｄ表現の表示は、設計を容易にする（すなわち、設計者がそれらの仕事を統計的に達成する速度を高める）。製品の設計は、製造プロセスの一部であるので、これは、製造業における製造プロセスを加速化する。
【００３４】
３Ｄシーンおよび３Ｄシーンにおける１つまたは複数の３Ｄモデル化オブジェクトは、（例えば、機械的）パーツ、パーツの集合体（または、パーツの集合体が本方法の観点からはパーツ自体と見なされてもよくもしくは本方法は集合体の各パーツに独立して適用されてもよいので、等価的にパーツの集合体）、またはより一般に、任意の剛体集合体（例えば、移動機構）など、例えば、ＣＡＤソフトウェアソリューションまたはＣＡＤシステムを使用した、仮想設計の完成の後の現実世界において製造される製品のジオメトリを表してもよい。ＣＡＤソフトウェアソリューションは、航空機、建築、建設、消費財、ハイテクデバイス、産業機器、輸送、海事、および／または沖合オイル／ガス生産もしくは輸送を含む、限定のない様々な製造業分野における製品の設計を可能にする。したがって、本方法によって説明される３Ｄモデル化オブジェクトは、（例えば、自動車および軽トラック機器、レーシングカー、オートバイ、トラックおよびモータ機器、トラックおよびバス、列車を含む）地上車両のパーツ、（例えば、機体機器、航空宇宙機器、推進機器、防衛製品、航空機器、宇宙機器を含む）航空機のパーツ、（例えば、海軍機器、商船、沖合機器、ヨットおよび作業船、海事機器を含む）船舶のパーツ、（例えば、製造業製造機械、重移動機械または機器、設置機器、製造業機器製品、製作金属製品、タイヤ製造製品を含む）一般機械パーツ、（例えば、消費者電子機器、セキュリティおよび／または制御および／または計装製品、コンピューティングおよび通信機器、半導体、医療デバイスおよび機器を含む）電子機械または電子パーツ、（例えば、家具、家屋および庭製品、レジャグッズ、ファッション製品、耐久消費財小売製品、織物類小売製品を含む）消費財、（例えば、食品および飲料および煙草、美容およびパーソナルケア、家庭用製品梱包用品を含む）梱包用品など、任意の機械的パーツとすることができる製造業製品を表してもよい。
【００３５】
ＣＡＤシステムは、履歴ベースであってもよい。このケースにおいては、モデル化オブジェクトは、幾何学的特徴の履歴を含むデータによってさらに定義される。モデル化オブジェクトは、実際には、標準的なモデリング機能（例えば、押し出し、回転、切断、および／もしくは丸め）、ならびに／または標準的なサーフェシング機能（例えば、スイープ、ブレンド、ロフト、フィル、デフォーム、および／もしくはスムージング）を使用して、生身の人間（すなわち、設計者／ユーザ）によって設計されてもよい。そのようなモデリング機能をサポートする多くのＣＡＤシステムは、履歴ベースのシステムである。これは、設計機能の生成履歴が、一般に、入力および出力リンクを通じて幾何学的特徴をともに結び付ける非循環データフローを通じて保存されることを意味する。履歴ベースのモデリングパラダイムは、８０年代初め以来公知である。モデル化オブジェクトは、２つの持続的なデータ表現、すなわち、履歴およびＢ−ｒｅｐ（すなわち、境界表現）によって説明される。Ｂ−ｒｅｐは、履歴において定義された計算の結果である。モデル化オブジェクトが表現されるとき、コンピュータの画面上に表示されるパーツの形状は、Ｂ−ｒｅｐ（の、例えば、モザイク細工）である。パーツの履歴は、設計意図である。基本的に、履歴は、モデル化オブジェクトが被った操作についての情報を収集する。Ｂ−ｒｅｐは、複雑なパーツの表示をより容易にするために、履歴とともに保存されてもよい。履歴は、設計意図に従ったパーツの設計変更を可能にするために、Ｂ−ｒｅｐとともに保存されてもよい。
【００３６】
ＰＬＭシステムはさらに、物理的な製造製品（または製造される製品）を表すモデル化オブジェクトの管理のために適合された任意のシステムを意味する。したがって、ＰＬＭシステムにおいては、モデル化オブジェクトは、物理的なオブジェクトの製造に適したデータによって定義される。これらは、一般に、寸法値および／または許容値であってもよい。オブジェクトの正確な製造のために、実際に、そのような値を有することがより好ましい。
【００３７】
ＣＡＭソリューションはさらに、製品の製造データを管理するように適合された任意のソリューション、ハードウェアのソフトウェアを意味する。製造データは、一般に、製造する製品、製造プロセス、および必要とされるリソースに関するデータを含む。ＣＡＭソリューションは、製品の全製造プロセスを計画および最適化するために使用される。例えば、それは、ＣＡＭユーザに、実現可能性、製造プロセスの継続時間、または製造プロセスの特定のステップにおいて使用することができる特定のロボットなどのリソースの数についての情報を提供することができ、その結果、管理または必要とされる投資についての決定を可能にする。ＣＡＭは、ＣＡＤプロセスおよび潜在的なＣＡＥプロセスの後に続くプロセスである。そのようなＣＡＭソリューションは、商標ＤＥＬＭＩＡ（登録商標）の下で、Ｄａｓｓａｕｌｔ  Ｓｙｓｔｅｍｅｓによって提供されている。
【００３８】
ＣＡＥソリューションはさらに、モデル化オブジェクトの物理的挙動の分析のために適合された任意のソリューション、ハードウェアのソフトウェアを意味する。公知の広く使用されているＣＡＥ技術は、物理的挙動が方程式を通じて計算およびシミュレートすることができる要素にモデル化オブジェクトが分けられることを一般に伴う、有限要素法（ＦＥＭ）である。そのようなＣＡＥソリューションは、商標ＳＩＭＵＬＩＡ（登録商標）の下で、Ｄａｓｓａｕｌｔ  Ｓｙｓｔｅｍｅｓによって提供されている。別の開発中のＣＡＥ技術は、ＣＡＤジオメトリデータを使用することなく、物理学の異なる分野からの複数の構成要素から構成される、複雑なシステムのモデリングおよび分析を伴う。ＣＡＥソリューションによって、シミュレーションが可能になり、よって、製造する製品の最適化、改良、および検証が可能になる。そのようなＣＡＥソリューションは、商標ＤＹＭＯＬＡ（登録商標）の下で、Ｄａｓｓａｕｌｔ  Ｓｙｓｔｅｍｅｓによって提供されている。
【００３９】
ＰＤＭは、製品データ管理を表す。ＰＤＭソリューションは、特定の製品に関連する全てのタイプのデータを管理するように適合された任意のソリューション、ハードウェアのソフトウェアを意味する。ＰＤＭソリューションは、主に技術者であるが、プロジェクトマネージャ、財務担当者、販売担当者、および購買担当者をも含む、製品のライフサイクルに含まれる全てのアクタによって使用されてもよい。ＰＤＭソリューションは、一般に、製品指向データベースに基づいている。それは、アクタが、彼らの製品についての整合性のあるデータを共有することを可能にし、したがって、アクタが、一致しないデータを使用することを防止する。そのようなＰＤＭソリューションは、商標ＥＮＯＶＩＡ（登録商標）の下で、Ｄａｓｓａｕｌｔ  Ｓｙｓｔｅｍｅｓによって提供されている。
【００４０】
図９は、システムの例を示しており、システムは、クライアントコンピュータシステム、例えば、ユーザのワークステーションである。システムは、サーバ、例えば、データベースを備えるサーバであってもよい。
【００４１】
実施例のクライアントコンピュータは、内部通信バス１０００に接続された中央処理装置（ＣＰＵ）１０１０、やはりバスに接続されたランダムアクセスメモリ（ＲＡＭ）１０７０を備える。クライアントコンピュータは、バスに接続されたビデオランダムアクセスメモリ１１００と関連付けられたグラフィカル処理ユニット（ＧＰＵ）１１１０をさらに備えてもよい。ビデオＲＡＭ１１００は、本技術分野において、フレームバッファとしても知られている。大容量記憶デバイスコントローラ１０２０は、ハードドライブ１０３０などの大容量メモリデバイスへのアクセスを管理する。コンピュータプログラム命令およびデータを有形に具体化するのに適した大容量メモリデバイスは、例として、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュメモリデバイスなどの、半導体メモリデバイス、内蔵ハードディスク、およびリムーバブルディスクなどの、磁気ディスク、光磁気ディスク、ならびにＣＤ−ＲＯＭディスク１０４０を含む、不揮発性メモリの全ての形態を含む。上記のいずれもが、特別に設計されたＡＳＩＣ（特定用途向け集積回路）によって補われてもよく、またはＡＳＩＣ内に組み込まれてもよい。ネットワークアダプタ１０５０は、ネットワーク１０６０へのアクセスを管理する。クライアントコンピュータは、カーソル制御デバイスまたはキーボードなどの触覚デバイス１０９０を含んでもよい。カーソル制御デバイスは、ユーザが、ディスプレイ１０８０上の任意の所望の位置に選択的にカーソルを位置付けることを可能にするために、クライアントコンピュータにおいて使用される。加えて、カーソル制御デバイスは、ユーザが、様々なコマンドを選択し、制御信号を入力することを可能にする。カーソル制御デバイスは、システムへの入力制御信号のための数々の信号生成デバイスを含む。一般に、カーソル制御デバイスは、マウスであってもよく、マウスのボタンが、信号を生成するために使用される。あるいは、または加えて、クライアントコンピュータシステムは、センシティブパッド、および／またはセンシティブスクリーンを備えてもよい。
【００４２】
コンピュータプログラムは、コンピュータによって実行可能な命令を含んでもよく、命令は、上記のシステムに方法を実行させるための手段を構成する。プログラムは、システムのメモリを含む、任意のデータ記憶媒体上に記録可能であってもよい。プログラムは、例えば、デジタル電子回路で、もしくはコンピュータハードウェア、ファームウェア、ソフトウェアで、またはそれらの組み合わせで実施されてもよい。プログラムは、装置として、例えば、プログラム可能プロセッサによる実行のために機械可読記憶媒体内に有形に具体化された製品として実施されてもよい。方法のステップは、入力データに操作を施し、出力を生成することによって、方法の機能を実行するために、命令を含むプログラムを実行するプログラム可能プロセッサによって実行されてもよい。プロセッサは、したがって、プログラム可能であってもよく、データ記憶システムおよび少なくとも１つの入力デバイスからデータおよび命令を受け取り、データ記憶システムおよび少なくとも１つの出力デバイスにデータおよび命令を送るように結合されてもよい。アプリケーションプログラムは、高水準手続き型プログラミング言語もしくはオブジェクト指向プログラミング言語で、または望ましい場合は、アセンブリ言語もしくは機械言語で実施されてもよい。いずれのケースにおいても、言語は、コンパイル型言語またはインタープリタ型言語であってもよい。プログラムは、フルインストールプログラム、またはアップデートプログラムであってもよい。システムに対するプログラムの適用は、いずれのケースにおいても、方法を実行するための命令を生成する。
【００４３】
「３Ｄシーンの区分化」は、モデルの実行を準備するプロセスを指定し、例えば、３Ｄシーンはシミュレートまたは再生される。モデル、例えば、３Ｄシーンは、経時的に現実世界システムの動作を模倣する。例えば、３Ｄシーンは、３Ｄモデル化オブジェクトを含み、各３Ｄモデル化オブジェクトは、３Ｄシーンによってモデル化されたシステムの一部を再現（またはモデル化）する。３Ｄモデル化オブジェクトは、例えば、ＣＡＤソフトウェアソリューションまたはＣＡＤシステムを使用して仮想設計を完了した後の、および例えば、ＭＭＯアプリケーションを使用してそれのシミュレーションの完了した後の、現実世界において製造される製品のジオメトリを表してもよい。
【００４４】
本方法は、製造プロセスに含まれてもよく、それは、３Ｄシーンを生成した後、３Ｄシーンを区分化するステップと、区分化された３Ｄシーンをシミュレートするステップとを含んでもよい。シミュレートされた３Ｄシーンは、その後、生産されてもよく、すなわち、モデル化システムに対応する物理的製品が生産される。いずれのケースにおいても、本方法によってシミュレートされた３Ｄシーンは、製造オブジェクトを表してもよい。本方法が３Ｄシーンのシミュレーションを改善するので、本方法はなた、製品の製造を改善し、したがって、製造プロセスの生産性も高める。
【００４５】
ここで図１を参照すると、ステップＳ１０において、３Ｄシーンが提供され、すなわち、コンピュータ化されたシステム（例えば、図９のシステム）は、３Ｄシーンのデータにアクセスすることができ、例えば、３Ｄシーンは、システムのメモリ上にロードされる。
【００４６】
３Ｄシーンは、オブジェクト間の空間的関係がその中において記述される空間である。シーンは、少なくとも２つのオブジェクトから構成され、オブジェクトは、モデル化オブジェクトまたは３Ｄモデル化オブジェクトであってもよいが、それらに限定されない。３Ｄモデル化オブジェクトは、３Ｄ空間内におけるオブジェクトの記述である。３Ｄシーンは、物理的世界のモデルであり、それは、座標を使用して３Ｄ空間内のあらゆる点を記述するジオメトリによって数学的に表されてもよい。３Ｄシーンは、一般に、オブジェクト間の現実的な相互作用がシミュレートされる、シミュレートされた現実世界である。現実的な相互作用という表現は、シミュレートされる相互作用が、現実世界の相互作用、例えば、力／作用力（重力、磁力、接触）などの物理法則、情報フローなどの制御法則、制御イベントなどを反映することを意味する。１つまたは複数のオブジェクトは、３Ｄシーンにおいて進化し、シミュレートされる現実世界の法則に支配され、例えば、２つのオブジェクトは、互いに交差することができない。３Ｄシーンは、特定のシナリオの目的のために変更することができるレイアウトを含む。シナリオは、３Ｄシーンにおける１つまたは複数のオブジェクトの少なくとも予想可能な相互作用を記述する。したがって、シナリオは、３Ｄシーンが、アクティビティとの関連において使用されるべき、または使用されることが想定される１つの方法を記述する。各特定のシナリオは、レイアウト上においてシミュレートされる。シナリオは、ユーザによって定義されてもよいことが理解されるべきである。
【００４７】
３Ｄシーンの各オブジェクトは、コンピューティングリソースコストを発生させる。３Ｄシーン上のオブジェクトは、当技術分野において知られているように、インスタンス化されたオブジェクトである。オブジェクトは、それが３Ｄシーンにおいてインスタンス化されるときに計算コストを発生させる。インスタンス化されたオブジェクトの計算コストは、インスタンス化のパラメータの関数である。インスタンス化のこれらのパラメータは、オブジェクトの３Ｄメッシュの選択された複雑性、テクスチャの精度、３Ｄシーンにおけるオブジェクトの反射およびシェーディング、接触／衝突、弾性、熱伝導などの力学的挙動に関連付けられた特性などであってもよいが、それらに限定されない。発生した計算コストは、位置における最大数のオブジェクトに対して、インスタンス化パラメータが最高である（例えば、最高のリアリズムをもったインスタンス化の）ときに、最大であることが理解されるべきである。
【００４８】
一般に、「コンピューティングリソースのコスト」という表現は、例えば、３Ｄシーンのシミュレーションのタイムステップの間に、オブジェクトを計算するのに必要とされるコンピューティングリソースの割合のことを指す。
【００４９】
オブジェクトの計算は、一般に、ソルバによって実施される。ソルバは、３Ｄシーンをシミュレートするコンピュータプログラムによって実行することができるコードの一部である。したがって、ソルバのセットは、完全な３Ｄシーンをシミュレートする。各ソルバは、マルチコアＣＰＵ上の解決スレッド、マルチＣＰＵコンピュータ上のプロセスから、サーバＣＰＵ上のサーバプロセスにわたることができるがそれらに限定されない、自らの専用コンピューティングリソース上において動作することが仮定される。そのため、「ソルバ」および「コンピューティングリソース」の概念は、負荷および性能に関して、厳格に等価である。「コンピューティングリソース」という表現は、したがって、「ソルバ」という用語の同義語である。
【００５０】
図２は、家具を据えることおよび移動することができ、壁紙を変更することができ、人間が進化することができる、家屋をモデル化およびシミュレートした３Ｄシーンの実施例の上面図であり、３Ｄシーンは２種類のオブジェクトを含む。最初の１つは、動的オブジェクトと呼ばれる。動的オブジェクトは、３Ｄシーンにおいて潜在的に移動することができるオブジェクトである。例えば、３Ｄシーンにおいて進化することができる人間をモデル化したオブジェクトは、動的オブジェクトである。同様に、家具をモデル化したオブジェクトは、移動することができ、動的オブジェクトである。動的オブジェクトは、自動的に、またはユーザの動作のときに３Ｄシーンにおいて動きまたは移動する。第２のタイプは、静的オブジェクトと呼ばれる。静的オブジェクトは、３Ｄシーンにおいて移動することができず、別のオブジェクトによってトラバースすることができない。動的オブジェクトは、したがって、静的オブジェクトとは対照的である。
【００５１】
３Ｄシーンの静的オブジェクトのセットは、３Ｄシーンのレイアウトを形成する。例えば、図２の家屋の壁は、静的オブジェクトであり、それらは、３Ｄシーンのレイアウトの一部である。自動車などの３Ｄシーンの他のオブジェクトは、レイアウトに属さないが、その理由は、これらのオブジェクトが静的オブジェクトではないからであり、実際に、自動車は、その自動車がレイアウトの一部として設計され、このケースにおいて静的オブジェクトである場合以外は、移動することができるオブジェクトである。
【００５２】
３Ｄシーンにおいては、動的オブジェクトのリストおよび考えられる動作のリストは、包括的ではなく、アプリケーションの目的および３Ｄシーンによってサポートされるシナリオの性質に依存する。図２に表される３Ｄシーンは、永続的に継続し、またはコンピューティングリソースによって処理される。これは、その間に、ユーザがいつでもログイン／ログアウトし、モールに新たな家具が追加され、仕事を開始することができ、新たな壁が追加または除去されてもよいことなどを含む。言い換えると、レイアウトは、変更されてもよく、動的オブジェクトも変更されてもよく、例えば、顧客は、抑制されて（suppress）、追加されて、またはさらに変更されてもよい。したがって、３Ｄシーンは、静的オブジェクトのレイアウトと、そのレイアウト内において移動する／進化する動的オブジェクトのセットを含むことが意図されてもよい。
【００５３】
引き続き、図２を参照すると、３Ｄシーンが平面上に投影されており、それらはビルディング、工場のデジタルモックアップなどのほとんどの３Ｄシーンのケースである。この例においては、平面はシミュレートされる家屋の地面を表す。定義によって、３Ｄシーンは量である。投影は、３Ｄシーンのプリントの抽出を含み、これは、３Ｄシーンの量の投影が、方向に従って、投影面（例えば、家屋の地面）に対して実行されること、すなわち、投影が、３Ｄ空間内の点を２次元投影面上の点に線形にマッピングすることによって作図されることを意味する。図２の例においては、投影の方向は、家屋の地面に垂直である。これは、地面上を移動する動的オブジェクトによってトラバースすることができない静的オブジェクトの完全な表現を取得することを可能にする。
【００５４】
図１に戻ると、ステップＳ２０において、提供された３Ｄシーンの計算コストの密度を表す第１のマップが計算される。第１のマップは、例えば、３Ｄシーンのシミュレーションのタイムステップの間に、３Ｄシーンをシミュレートするための、表面の単位ごとに要する、コンピューティングリソースの割合をプロットする。
【００５５】
２０１４年６月２５日に公開された特許文献１に開示されるように、第１のマップが確立されてもよい。説明のために、第１のマップの計算の例がここで説明される。第１のステップにおいて、３Ｄシーン内の位置のセットが決定される。位置は、３Ｄシーンのオブジェクトによって到達可能な３Ｄシーンの一部である。一般に、３Ｄシーンの位置は、動的オブジェクトによって到達可能である。位置は、３Ｄシーンのオブジェクトが接近可能な３Ｄシーンの区切られたエリアであってもよく、またはそれは、３Ｄシーンのオブジェクトが包囲される３Ｄシーンの量であってもよい。言い換えると、位置は、１つまたは複数のオブジェクトによって占有された、または１つまたは複数のオブジェクトによる占有のために利用可能な３Ｄシーン内のサイトであってもよい。位置および静的オブジェクトは、緊密に関連している。実際に、レイアウトにおける動的オブジェクトの運動は、動的オブジェクトによってトラバースすることができない３Ｄ空間内の表面または量を定義する静的オブジェクトによって制限される。例えば、図２においては、自動車を表すオブジェクト２１０は、ガレージ２００を出入りすることができる動的オブジェクトである。ガレージ２００の壁は、静的オブジェクトである。（壁によって区切られた）ガレージの地面は、動的オブジェクトによって到達可能であり、したがって、位置として識別することができる。第２のステップにおいて、各位置は、最も高価な計算コストに到達する、それを最大限占有するオブジェクトで保管される。位置を、それを最大限占有するオブジェクトで満たすことは、オブジェクトがその位置上に配置され、この位置上に配置されたオブジェクトの数が、その位置上において許可されたオブジェクトの最大数であることを意味する。オブジェクトのこの最大数は、３Ｄシーンによって再生されまたは３Ｄシーン上において適用される、シナリオによって定義することができる位置の特性である。シナリオは、シミュレートされる現実世界に関して現実的であり、３Ｄシーン内におけるオブジェクトの考えられる動作を制限する。例えば、図２において、位置「ガレージ」（すなわち、ガレージの地面）は、１つの自動車および多くのユーザを含むことができる。実際には、位置を、それを最大限占有するオブジェクトで満たすことは、動的オブジェクトのみを使用して実行される。次のステップにおいて、最大計算コストが、３Ｄシーンの位置ごとに計算される。与えられた位置についての最も高価な計算コストは、位置上に受け入れ可能なオブジェクトの最大数に到達したとき、およびオブジェクトが少なくとも最高のリアリズムでインスタンス化されたときに到達する。したがって、最大コスト状況分析が実行され、仮想世界の各位置が、最大ＣＰＵコスト状況において分析される。次のステップにおいて、３Ｄシーンの各位置の計算コスト密度が計算される。これは、好都合なことに、全ての位置についての最悪コスト状況を定量化および特徴付けることを可能にする。実際には、最大計算コスト密度が計算され、それは、位置のタイプ（エリア、量）に依存する、表面の単位ごとまたは量の単位ごとの計算コストのことを指す。例えば、位置が、図２の例におけるようなエリアである場合、最大計算コスト密度は、表面の単位ごとの計算コストである。実際には、位置ごとに比Ｐ／Ａが計算され、Ｐは、その位置を処理するために必要とされるコンピューティングリソースの割合を定量化し、Ａは、３Ｄシーン内における位置の面積（または表面）である。その後、３Ｄシーンのコスト密度のマップ（第１のマップとも呼ばれる）が、集約された最大計算コスト密度から作成される。
【００５６】
図３は、図２の３Ｄシーンについての第１のマップの表現の例を示している。図２においては、５つの位置２００、２２０、２３０、２４０が、識別されており、それらの最大計算コスト密度が図３に表されている。位置がエリア内に多くのオブジェクトを有し、多くの相互作用を伴うより高い確率を有する場合、密度はより高くなる。リビングルーム２３０においては、コスト密度３３０は、２０％／ｍ2（平方メートル当たりのコンピュータリソースの割合）であり、一方、小さいパティオ（patio）２００は、そこは、３Ｄシーンのシナリオにおいては進化のない静的エリアであるので、０％／ｍ2に等しいコスト密度３２０を有する。この例においては、コスト密度のマップは、３Ｄシーンの投影面と同一の平面上に作成されている。３Ｄシーンと第１のマップとの間の対応は、より容易に表され、維持される。コスト密度のマップが作成されると、それはユーザに対して表示されてもよい。この目的で、マップは、３Ｄシーンの位置の計算された最大計算コスト密度を示す、グラフィカル情報３５０を提供してもよい。例えば、図２に示されるように、カラースケール３５０が、最大コスト密度を表すために使用されてもよい。
【００５７】
ステップＳ３０において、３Ｄシーンの区分化の結果として取得されるゾーンの形状に対する制約を表す第２のマップが定義される。「ゾーンの形状」という表現は、３Ｄシーンの区分化の結果として取得される１つまたは複数のゾーンに対して許可される幾何学的形体を意味する。したがって、第２のマップは、１つまたは複数のゾーンに対して許可される幾何学的形体を制限する。例えば、ゾーンは、３つ以上のエッジを有するポリゴンなどの（しかし、それに限定されない）表面を定義する２Ｄ形状とすることができる。ゾーンは、平行６面体、球などの（しかし、それに限定されない）量を定義する３Ｄ形状であってもよい。第２のマップは、コンピューティングリソースの観点から、３Ｄシーンの区分化が問題を引き起こさないことを保証することを目指している。第２のマップの制約は、特に、動的オブジェクトに関して、ソルバの動作不良およびソルバ間の衝突を回避する。
【００５８】
制約を定義するために、第１のマップを計算するために識別された位置を使用することができる。特に、位置は、３Ｄシーンの静的オブジェクトから決定されてもよく、例えば、３Ｄシーンの壁を動的オブジェクトによって交差することができず、それによって部屋が位置を定義するようになる。
【００５９】
位置の識別を、以下のように一般化することができる。最初に、３Ｄシーンにおいて、３Ｄシーンの１つまたは複数の静的オブジェクトを識別する。例えば、図２を参照すると、壁および階段は、３Ｄシーンの静的オブジェクトである。次に、識別された静的オブジェクトごとに、ジオメトリが計算される。この計算されたジオメトリは、静的オブジェクトのアウトラインを表し、計算されたジオメトリは、動的オブジェクトに対する制約であるとして意図されてもよく、例えば、それらは、計算されたジオメトリを横断することができない。ジオメトリは、位置を定義する３Ｄシーンにおけるエリアを生成するためのルールと関連付けられる。シーンがセルに離散化されている場合、以下で明らかになるように、ルールは、１つまたは複数のセルの１つまたは複数のクラスタを生成する。
【００６０】
第１のマップを計算するために使用される位置にのみ依存する代わりに、第２のマップは、３Ｄシーンにおいて識別される以下の３種類の制約を使用して作成されてもよい。上記説明された位置の概念の一般化が適用されてもよく、すなわち、制約は、静的オブジェクトを識別することによって取得され、ジオメトリは静的オブジェクトから計算され、ルールは計算されたジオメトリに関連付けられる。
【００６１】
第１の制約は、「横断しない（do not Cross）」制約と呼ばれ、「Ｃ」制約と表記される。計算されたジオメトリは、ラインまたはポリラインである。ラインまたはポリラインのラインは、動的オブジェクトによって決して交差されるべきではない。好ましくは、この計算されたジオメトリと接触する３Ｄシーンの他のゾーン（または区画）は、ラインと一致するべきである。この「Ｃ」制約は、エリア内のゾーンを分割（split）して、オブジェクトが決して互いに相互作用しないようにすることを目指している。図４の例においては、「Ｃ」制約４００は、ドア位置４０４を除いた、壁４０２に一致し、その理由は、家具または人間は、そこを横断することができないからである。ポリラインと関連付けられたルールは、そのポリラインと接触し、およびそのポリライン内にほぼ含まれる３Ｄシーンの表面がゾーンを形成することを定義する。
【００６２】
第２の制約は、「完全性を取る（take Integrality）」と呼ばれ、「Ｉ」制約と表記される。計算されたジオメトリはポリゴンであり、ジオメトリと関連付けられたルールは、ポリゴン内に囲まれた（すなわち、ポリゴン内に完全に含まれた）表面がゾーンを形成することを定義する。「Ｉ」制約は、追加の複雑で高価な、時には不可能な計算を防止し、それは、このエリアを２つ以上のゾーンに分割することを止めることからもたらされる。図４においては、「Ｉ」制約４１０は、ジオメトリとして、シミュレートすることに問題となることがある、自動車２１０の２つのパーツへの「切断」を防止する長方形４０２を含む。興味深いことに、ジオメトリ４０２は、エリア４０４を包含しておらず、実際には、このエリアは、自動車２１０を受け入れるには小さすぎ、そのため、エリア４０４が、別のゾーンに帰属される（attached to）場合、自動車が２つのパーツに切断されるリスクは存在しない。
【００６３】
第３の制約は、「方向に従う（follow Direction）」と呼ばれ、「Ｄ」と表記される。計算されたジオメトリはポリゴンであり、ジオメトリと関連付けられたルールは方向および大きさである。方向および大きさはベクトルによって表される。ジオメトリと関連付けられたルールは、ポリゴン内に囲まれた（すなわち、ポリゴン内に完全に含まれた）表面がゾーンを形成すること、およびベクトルに従ってポリゴンのエッジからポリゴンの外側に延在するさらなる表面がゾーンに追加されることを定義する。例えば、図４においては、「Ｄ」制約４２０は、ポリゴン４２６が階段４２２を囲み、ゾーンに属する追加の表面４２４（例えば、階段に役立つ踊り場）を生成するように、ベクトルがポリゴンの上部エッジからポリゴン４２６を広げることを含み、このように、動的オブジェクトによって階段を上り下りすることは、２つの隣接するゾーンの横断を必要とすることを仮定して、それは、常に、いかなる振動（oscillation）もなく、ゾーンから他のゾーンへのオブジェクトの１回限りの移動
で即座に実行される。
【００６４】
３Ｄシーンにおける制約の識別を自動的に実行することができる。この自動的な識別は、３Ｄシーンにおける静的オブジェクトの分析に基づくことができる。その後、識別された静的オブジェクトは、動的オブジェクトの分析に従ってルールと関連付けられてもよく、動的オブジェクトは、（ｉ）識別された静的オブジェクトの近くに位置しており、および／もしくは位置するオブジェクトの履歴、ならびに／または（ｉｉ）静的オブジェクトのカテゴリを示す静的オブジェクトと関連付けられた１もしくは複数のパラメータ、例えば、静的オブジェクトが壁、または階段などであることを示すことができるパラメータに従って実行することができる、静的オブジェクトの近隣に存在してもよい。例えば、本方法を実行するシステムは、ガレージの静的オブジェクトが「壁」であること、および動的オブジェクト「自動車」が、これらの静的オブジェクトの近隣内に位置し、または位置したことがあることを発見することができる。別の例として、階段４２２は、この静的オブジェクト４２２が階段タイプに属することを示すパラメータと関連付けられてもよく、結果として、計算されたジオメトリ４２６と関連付けられたルールは、階段に役立つ踊り場４２４を生成するための方向および大きさである。
【００６５】
３Ｄシーンの１つまたは複数の静的オブジェクトの３Ｄシーンにおける識別は、ユーザの動作のときに実行されてもよい。３Ｄシーンを設計する設計者、または３Ｄシーンをシミュレートする必要があるユーザは、生成されるゾーンの形状を制約すべき静的オブジェクトを指定する。ユーザの動作の結果として、ジオメトリが動的に計算される。ジオメトリは、設計者／ユーザによって変更されてもよい。あるいは、設計者／ユーザは、ジオメトリを直接描画することができる。
【００６６】
計算されたジオメトリとのルールの関連付けは、ユーザの動作のときに実行されてもよく、すなわち、ユーザは、自動的に計算されたジオメトリに、またはユーザが変更もしくは描画したジオメトリに適用されるルールのタイプを選択する。例えば、ジオメトリの生成後、設計者／ユーザは、選択することができるルールのメニューを自動的に提案されるが、１つのルールは、１つの計算されたジオメトリと関連付けられてもよいことが理解される。
【００６７】
本発明の方法のこの段階においては、３Ｄシーンから、２つのマップ、すなわち、３Ｄシーンのコスト密度を表す第１のマップ、および本方法の結果として取得されるゾーンに対する制約を表す第２のマップが取得されている。
【００６８】
次に、図１のステップＳ４０からＳ４２において、ステップＳ１０において提供された３Ｄシーンが、離散化のための量子の計算の後、セルに離散化される。３Ｄシーンを離散化することは、３Ｄシーン、例えば、図２に示されるような平面上に投影される３Ｄシーンが、各セルが同一のサイズ（すなわち、同一の表面）を有する、セルのセットに分けられることを意味する。したがって、セルは表面量子（surface quantum）であり、３Ｄシーン全体が離散化されるので、セルの数は計算された量子に依存する。セルは、２Ｄセルであってもよく、図２に示されるように、３Ｄシーンは２Ｄ平面として表され、セルは２Ｄ表面である。セルは３Ｄセルであってもよく、３Ｄ空間内の３Ｄシーンによって生成される量は、３Ｄ量であるセルに分けられる。要するに、セルは、３Ｄシーン全体をカバーする。３Ｄシーンの空間量子化は、動的オブジェクトのない３Ｄシーンについて計算される。これは、３Ｄシーンの離散化が、３Ｄシーン上の動的オブジェクトを考慮しないことを意味する。３Ｄシーンの空間量子化は、以下のように計算されてもよい。
【００６９】
ステップＳ４０において、Ｓｑと表記される表面量子が、関係（１）の使用によって計算され、
Ｓｑ＝（ＣＰＵCA）／（計算コストの密度）Max                            （１）
ここで、ＣＰＵCAは、ゾーンを処理するためのコンピュータリソースコストの正確度を表し、（計算コストの密度）Maxは、第１のマップ上において表された最高密度を表す。
【００７０】
コンピューティングリソースの正確度ＣＰＵCAは、設計者／ユーザが３Ｄシーンをそれで区分化することを望む、ＣＰＵコストに関する正確度を表す。したがって、より低いコスト密度を有するエリアの場合、ゾーンのジオメトリがそれで調整される表面量子Ｓｑは、必然的にコスト正確度よりも低くなることを表す。したがって、コンピューティングリソースの正確度ＣＰＵCAは、シーンがそれで離散化される感度を表し、「感度を調整する（adjusting sensitivity）」という表現は、正確度ＣＰＵCAを指定するために使用されてもよい。事実、表面量子の値（Ｓｑ）は、３Ｄシーンのコスト密度を表す第１のマップによって指示され、実際に、そのような量子の追加または撤回の後、ソルバの負荷の変動の割合の最大を決定する必要がある。ステップＳ４２において、３Ｄシーンは、全てが表面量子Ｓｑに等しいサイズを有するセルに離散化される。
【００７１】
図５は、表面量子Ｓｑのセルに離散化された図３に表された３Ｄシーンの第１のマップの例を示している。この例は、３Ｄシーンを離散化するセルと、３Ｄシーンのコスト密度のマップとの間の関係を示している。３Ｄシーンおよび第１のマップは、重なり合うこと、すなわち、それらは、同一のサイズを有することが理解される。あるいは、２つのうちの１つは、与えられたサイズファクタよりも小さい。セルのパターンは、全てのセルについて同一のであり、ここでは、３Ｄシーンは、同一のサイズの正方形であるＮ個のセルに分けられる。したがって、３Ｄシーンはグリッドメッシュに従って離散化され、そのステップは表面量子の平方根である。グリッドメッシュの使用は、特に、３Ｄシーンがビルディング、例えば、工場のデジタルモックアップなどのインフラストラクチャをモデル化するときにゾーンの生成をより容易にする。他の規則的メッシュに対しても同様に、または可変メッシュに対しても同様に、離散化が適用されてもよいことが理解されるべきである。
【００７２】
引き続き、図５を参照すると、５％に設定されたＣＰＵコスト正確度および平方メートル当たり２０％の最高密度を使用して、メッシュが取得されている。これは、平方メートルの４分の１（１／４）の表面量子を使用した正方形セルの規則的メッシュ（５０２）の生成をもたらし、正方形メッシュが選択されたので、シーンは、２分の１（１／２）メートルステップの正方形グリッド（５００）に従って離散化される。この例においては、正確度は５％に設定され、それは、セルのＣＰＵコストが、Δ＝±ε、ε≦±５％と表記される最大精度で変動することができることを意味する。したがって、εの値は、密度２０％（図５の黒い正方形）については５％であり、密度１０％については２．５％であり、密度５％については１．２５％である。
【００７３】
次に、ステップＳ５０において、離散化された３Ｄシーンのセルごとに、計算コストが計算される。この計算は、ステップＳ２０において取得された３Ｄシーンの第１のマップから実施される。与えられたセルの計算コストは、与えられたセルの表面量子Ｓqとセルの計算コストの密度との間の数学的な積によって与えられる。与えられたセルの表面量子Ｓqは、ステップＳ４０において計算されている。与えられたセルの計算コストの密度は、ステップＳ２０において計算された第１のマップから取得される。ステップＳ５０の出力は、３Ｄシーンのために以前に取得されたのと同一のセルのセットを含む新たなマップであり、各セルはセルの計算コストと関連付けられる。
【００７４】
図６は、ステップＳ５０を使用して取得されたこの新たなマップの例を示している。新たなマップは、離散化コストマップ６００と呼ばれ、３Ｄシーンを離散化した各セルのＣＰＵコストの割合を含む。例えば、セル６２０は、ゼロに等しい計算コストを有する。別の例として、セル６３０は、５％に等しい計算コストを有する。これは、セル６３０を担当するコンピューティングリソースが、セル６３０を処理するために、それのコンピューティングリソースの５％を必要とすることを意味する。グリッドメッシュの全てのセルコストの合計が、３Ｄシーンを実行するのに必要とされるコンピューティングリソースの量を示すことが理解される。加えて、離散化コストマップは、いくつのゾーンが３Ｄエクスペリエンスをリアルタイムにシミュレートすることができるかについての情報を提供する。図６の例においては、グリッドの全てのセルのコストの合計は、約２９６％である。３つのゾーンが定義されてもよく、各ゾーンは１００％よりも低い全体コストを有する。各ゾーンは、コンピューティングリソースと関連付けられ、安全かつリアルタイムにシーンに対処するはずである。
【００７５】
次に、ステップＳ６０において、１つまたは複数のセルの１つまたは複数のクラスタが、第２のマップに従って計算される。１つまたは複数のクラスタは、ゾーンを定義する時点におけるセルの組み合わせ数を減少させることを目指している。実際に、シーン離散化がＮ個のセルを有すると仮定すると、ソルバから利用可能なコンピューティングリソースの１００％に近い（しかしながら、常にそれより低い）コストを有する、これらのセルをパーツに収集するためのＮ！個の方法が存在する。このステップの目的は、セルのクラスタを構成し、それによって、第２のマップに表される（Ｃ）、（Ｉ）、および（Ｄ）制約が、これらのクラスタによって暗黙的に検証され、以下の段階を簡素化することである。顕著な結果として、これは、探索のための組み合わせを著しく減少させる。
【００７６】
図７は、図４の離散化された第２のマップにおける制約の例を示している。図４の「Ｃ」制約４００は、ポリラインである計算されたジオメトリを有し、ポリライン７００のラインのうちの１つが図７に表されている。図４の「Ｉ」制約４１０は、図７のいくつかのクラスタ７１０を囲む計算されたジオメトリとしてのポリゴンを有する。図４の「Ｄ」制約４２０も、図７に表された計算されたジオメトリ７２０としてのポリゴンを有する。
【００７７】
「Ｃ」制約７００は、ポリラインに隣接するセルごとのクラスタの生成をトリガするルールと関連付けられる。言い換えると、「Ｃ」制約のジオメトリ（ここでは、ポリラインのライン）の周囲に位置する全てのセルは、必ずしもともに集約されない。ライン７００に隣接する各セルは、特定の値ラベルと関連付けられ、より具体的には、図８に示されるように、この制約の一方の側のセルは、この値８００を使用してラベル付けされ、反対側のセルは、反対の値８０２を使用してラベル付けされる。したがって、いずれのさらなるクラスタ集約も、反対ラベルを有するセルを有するときは、ペナルティが課されるはずであり、一方、同一のラベルを有するセルを有するときは、見返りが与えられるはずである。
【００７８】
図７の「Ｉ」制約７１０は、ポリゴン内に含まれるセルを有するセルのクラスタを生成するルールと関連付けられる。したがって、同一の（Ｉ）制約７１０内に位置する全てのセルは、図８に表されるように、単一のクラスタ８１０を形成し、それは、本方法のさらなるステップにおいては全体として扱われる。（Ｉ）クラスタの結果のコストは、コンピューティングリソースの利用可能なコンピューティングリソースの１００％を超えるべきではないことに留意されたい。そうでない場合、それは、シーンがエリアを含み、エリアは、シミュレーションのために選択されたコンピューティングリソースについてリアルタイムではなく、コスト密度のマップがそれで作り上げられることを意味する。制約「Ｉ」、「Ｄ」、または「Ｃ」から取得されるクラスタが、利用可能なコンピューティングリソースの１００％以上を必要とする場合、表面量子の縮小がトリガされてもよく、３Ｄシーンの離散化の作り替え（redo）が実行されてもよい。
【００７９】
図７の「Ｄ」制約７２０は、ジオメトリ内に囲まれるセルを有する１つまたは複数のクラスタを生成するルールと関連付けられる。「Ｄ」制約から生成される各クラスタは、ジオメトリ内に囲まれる少なくとも１つのセルと、ベクトル７２２によって表される方向および大きさに従って、ジオメトリ（ポリゴン）内のこの少なくとも１つのセルから延在する１つまたは複数のセルとを含む。この例においては、同一の（Ｄ）制約７２０内に位置する全てのセルは、制約７２２の方向に平行なスライスクラスタ８２２内に位置する。言い換えると、それの周辺にそのような（Ｄ）クラスタを有するいずれのクラスタ集約も、適切な形状を有する境界を継承する。そのようなスライスクラスタのコストは、１００％を大きく下回ったままであるはずである。
【００８０】
制約「Ｉ」、「Ｄ」、または「Ｃ」から生成されたクラスタに属さないセル８３０は、例えば、図８のセル８３０などの、１セルクラスタと見なされる。
【００８１】
次に、ステップＳ７０において、クラスタは、１つまたは複数のゾーンに集約される。集約の結果として取得された各ゾーンは、そのゾーンに属するセルの計算コストの合計である計算コストを有する。ゾーンの計算コストは、コンピューティングリソース上におけるゾーンのリアルタイムシミュレーションを可能にする。言い換えると、各ゾーンの計算コストは、ソルバから利用可能なコンピューティングリソースの１００％を下回ったままであるはずである。
【００８２】
ゾーンシェイピングは、いわゆる、ビンパッキング問題であり、それは、１００％により近い（しかしながら、１００％未満の）ＣＰＵコストを有するパーツを形成するためにクラスタを集約すること、および後で詳説されるコスト関数を最小化することに本質がある。クラスタの集約は、好ましくは、組み合わせ最適化アルゴリズムを使用して実施される。アルゴリズムによって実行される組み合わせ最適化は、ＣＰＵコストは１００％に近くなければならないが、この閾値を超えないことを考慮したときに取得することができるクラスタの全ての組み合わせの中から、クラスタの最適な集約を発見することを目指している。すなわち、アルゴリズムは、クラスタの計算コストに従って、考えられる集約の全ての組み合わせを計算する。Ｎ個のクラスタを集約するためのＮ！個の方法が存在する。組み合わせの中でいずれが最良の解であるかを決定するために、また計算する組み合わせの数を制限するために、アルゴリズムは到達される目的を表す１つまたは複数の基準を入力としてみなしてもよい。目的関数は、１つまたは複数の基準に従って最良の解を決定するために使用されてもよい。組み合わせ最適化アルゴリズムの目的関数は、少なくとも以下のときに増加するように定式化される。
【００８３】
（ｉ）ゾーンの数Ｚが、１つまたは複数のゾーンへのセルの新たな集約の結果として増加したとき。例えば、目的関数の増加は、Ｚの変化の平方に比例することができる。
【００８４】
（ｉｉ）ゾーンの形状が鋸歯状の境界であるとき。このケースにおいては、目的関数の増加は、凹部の数および／もしくは凸部の数に比例し、ならびに／またはゾーンの周囲の長さとそれらの表面の周囲の長さとの間の比に比例する。
【００８５】
（ｉｉｉ）非連結なゾーンの数がゼロよりも大きいとき。このゾーンのいずれかの位置から他の任意の位置へその境界の１つから出てその境界の１つに再度入ることなく行くことがトポロジ的に可能でないとき、ゾーンは非連結である。そのような状況においては、目的関数の増加は、Ｚの立方（Ｚ3）の変化に比例することができる。
【００８６】
（ｉｖ）Ｚ個のゾーンが、反対のラベル値を使用して「Ｉ」制約から取得されたＫ個のクラスタを含むとき。コスト関数において使用されるゲインＫは、最初はランダムに選択された値に設定されてもよく、その後、経験的に較正されてもよく、または制御理論もしくは機械学習などにおけるアルゴリズムによって調整されてもよい。この較正は、シミュレーションが動作している間に実行されてもよい。目的関数の増加は、Ｚの平方（Ｚ2）の変化に比例することができる。
【００８７】
蟻コロニアルゴリズムなどの組み合わせ最適化アルゴリズムが、妥当なタイムフレーム内において最適解を見つけるために使用されてもよい。他の任意の適切な組み合わせ最適化アルゴリズムが使用されてもよいことが理解されるべきである。
【図１】
2018116695.tif 000003
【図２】
2018116695.tif 000004
【図３】
2018116695.tif 000005
【図４】
2018116695.tif 000006
【図５】
2018116695.tif 000007
【図６】
2018116695.tif 000008
【図７】
2018116695.tif 000009
【図８】
2018116695.tif 000010
【図９】
2018116695.tif 000011
【手続補正書】
【提出日】平成30年1月26日(2018.1.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
３Ｄシーンを複数のゾーンに区分化するためのコンピュータによって実行される方法であって、各ゾーンは、前記３Ｄシーンのエリアまたは量を表し、コンピューティングリソースによって処理され、
１つまたは複数のオブジェクトを含む３Ｄシーンを提供するステップであって、各オブジェクトは、コンピューティングリソースコストを発生させる、ステップと、
前記提供された３Ｄシーンの計算コストの密度を表す第１のマップを計算するステップと、
前記３Ｄシーンの区分化の結果として取得されるゾーンの形状に対する制約を表す第２のマップを定義するステップと、
動的オブジェクトのない前記３Ｄシーンの空間量子化を計算することによって、前記提供された３Ｄシーンをセルに離散化するステップであって、動的オブジェクトは、前記３Ｄシーン内において潜在的に移動することができるオブジェクトである、ステップと、
セルごとに、前記３Ｄシーンの前記第１のマップから計算コストを計算するステップと、
前記第２のマップに従って、前記セルを１つまたは複数のゾーンに集約するステップであって、各ゾーンは、前記ゾーンに属する前記セルの前記計算コストの合計である計算コストを有し、前記ゾーンの前記計算コストは、コンピューティングリソース上における前記ゾーンのリアルタイムシミュレーションを可能にする、ステップと
を備えることを特徴とするコンピュータによって実行される方法。
【請求項２】
１つまたは複数のゾーンへの前記セルの前記集約は、組み合わせ最適化アルゴリズムを使用してさらに実施されることを特徴とする請求項１に記載のコンピュータによって実行される方法。
【請求項３】
前記組み合わせ最適化アルゴリズムは、蟻コロニアルゴリズムであることを特徴とする請求項２に記載のコンピュータによって実行される方法。
【請求項４】
前記セルの前記集約の前に、
前記第２のマップに従って、１つまたは複数のセルの１つまたは複数のクラスタを計算するステップ
をさらに備え、
前記集約するステップは、前記クラスタを１つまたは複数のゾーンに集約するステップを含み、各ゾーンは、前記ゾーンに属する前記セルの前記計算コストの前記合計である計算コストを有し、前記ゾーンの前記計算コストは、コンピューティングリソース上における前記ゾーンのリアルタイムシミュレーションを可能にする
ことを特徴とする請求項１乃至３のいずれか一項に記載のコンピュータによって実行される方法。
【請求項５】
前記第２のマップ上において表される前記ゾーンの前記形状に対する前記制約は、
前記３Ｄシーン内において前記３Ｄシーンの１つまたは複数の静的オブジェクトを識別するステップであって、静的オブジェクトは、前記３Ｄシーンにおいて移動することができず、別のオブジェクトによってトラバースすることができないオブジェクトである、ステップと、
識別された静的オブジェクトごとに、１つまたは複数のセルの１つまたは複数のクラスタを生成するルールと関連付けられたジオメトリを計算するステップと
によって取得されることを特徴とする請求項１乃至４のいずれか一項に記載のコンピュータによって実行される方法。
【請求項６】
セルのクラスタを生成するためのジオメトリとルールとの前記関連付けは、
前記ジオメトリはポリゴンであり、および前記ルールは前記ポリゴンに含まれる前記セルのクラスタを生成することと、
前記ジオメトリはポリゴンであり、ならびに前記ルールはベクトルによって表される方向および大きさに従って前記ポリゴンから延在する前記セルのクラスタを生成することと、
前記ジオメトリはポリラインであり、および前記ルールは前記ポリラインに隣接するセルごとにクラスタの前記生成をトリガすることと
のうちの１つであることを特徴とする請求項５に記載のコンピュータによって実行される方法。
【請求項７】
前記３Ｄシーン内における前記３Ｄシーンの１つまたは複数の静的オブジェクトの前記識別は、ユーザの動作のときに実行されることを特徴とする請求項５または６に記載のコンピュータによって実行される方法。
【請求項８】
計算されたジオメトリとのルールの前記関連付けは、ユーザの動作のときに実行されることを特徴とする請求項６または７に記載のコンピュータによって実行される方法。
【請求項９】
前記提供された３Ｄシーンの計算コストの密度を表す前記第１のマップの前記計算は、
前記３Ｄシーン内における位置のセットを決定することと、
各位置を、最も高価な計算コストに達するそれを最大限占有するオブジェクトで満たすことと、
前記３Ｄシーンの位置ごとに、最大計算コストを計算することと、
位置ごとに、比Ｐ／Ａを計算することであって、Ｐは、前記位置を処理するために必要とされるコンピューティングリソースの測定された割合であり、Ａは、前記３次元シーン内における前記位置の面積である、ことと
を含むことを特徴とする請求項１乃至８のいずれか一項に記載のコンピュータによって実行される方法。
【請求項１０】
各位置を、それを最大限占有するオブジェクトで満たすことは、動的オブジェクトに対して実行されることを特徴とする請求項９に記載のコンピュータによって実行される方法。
【請求項１１】
前記３Ｄシーンの前記空間量子化の前記計算は、
関係Ｓq＝（ＣＰＵCA）／（計算コストの密度）Max
によって定義される表面量子を計算することであって、（ＣＰＵCA）は、前記ゾーンを処理するためのコンピュータリソースコストの正確度を表し、（計算コストの密度）Maxは、前記第１のマップ上において表された最高密度である、ことと、
前記提供された３Ｄシーンをセルに離散化することであって、各セルは、前記表面量子Ｓqに等しいサイズを有する、ことと
を含むことを特徴とする請求項１乃至１０のいずれか一項に記載のコンピュータによって実行される方法。
【請求項１２】
セルごとに、前記３Ｄシーンの前記第１のマップから計算コストを計算するステップは、前記表面量子Ｓqと前記セルの計算コストの密度との間の積を計算するステップを含むことを特徴とする請求項１０に記載のコンピュータによって実行される方法。
【請求項１３】
前記組み合わせ最適化アルゴリズムの目的関数は、少なくとも、
１つまたは複数のゾーンへの前記セルの新たな集約の結果として、ゾーンの数Ｎが増加したときに、
ゾーンの前記形状が、鋸歯状の境界であるときに、
非連結なゾーンの数が、ゼロよりも大きいときに、
増加するように定式化される請求項２乃至１１のいずれか一項に記載のコンピュータによって実行される方法。
【請求項１４】
コンピュータによって実行されるときに、前記コンピュータに請求項１乃至１３のいずれか一項に記載の方法を実行させるための命令を含むことを特徴とするコンピュータプログラム。
【請求項１５】
メモリおよびグラフィカルユーザインターフェースに結合されたプロセッサを備え、前記メモリは、請求項１４に記載のコンピュータプログラムを記憶していることを特徴とするシステム。
【外国語明細書】
2018116695000001.pdf