(57)【要約】【課題】見本から要素配置を合成するための方法及び装置を提供する。【解決手段】実施形態は、見本配置から要素配置パターンを合成できる。実施形態は、見本とターゲットの局所的近隣比較に基づくテクスチャ合成テクニックと、局所的成長に基づく手続き的モデリングを結合できる。見本が与えられると、各要素の近隣情報を獲得するように要素の連結性を構成できる。合成プロセスは、単一のシードを伴って開始し、かつシードの場所に新しい要素を１つ１つ置くことによって合成されているパターンを拡大できる。合成されているパターン内のターゲット・シードの近隣特徴にもっとも類似する近隣特徴を有する見本から参照要素を選択できる。非回転モード、回転モード、及びフロー・フィールド・モードを使用できる。ペインティング・ツール、フロー・フィールド・ツール、及び境界ツールを提供できる。【選択図】図４
2009059368.tif 000002
【特許請求の範囲】
【請求項１】
パターンを合成するためのコンピュータで実施される方法であって、
反復的に単一要素を合成されるパターン内に配置することを包含し、前記単一の要素を合成されるパターン内に配置することが、
合成されるパターン・エリア内のターゲット・シードを決定すること、
前記合成されるパターン・エリア内の前記ターゲット・シードについての近隣特徴を決定すること、
前記ターゲット・シードの前記近隣特徴にもっとも類似する近隣特徴を有する複数の要素を包含する参照配置内の参照要素を決定すること、及び
前記参照要素のコピーを前記合成されるパターン・エリア内の前記ターゲット・シードの場所に配置すること、
を包含する方法。
【請求項２】
さらに、前記反復的に単一要素を合成されるパターン内に配置することに先行して、
前記参照配置の前記複数の要素の間の連結性を構成すること、及び
前記要素の前記連結性に従って前記参照配置内の各要素の近隣特徴を決定することを包含する、請求項１に記載の方法。
【請求項３】
前記反復的に単一要素を合成されるパターン内に配置することは、さらに、前記ターゲット・シードの前記場所及び前記参照要素の前記近隣特徴に従って前記合成されるパターン・エリア内に１つ又は複数の新しいシードを生成することを包含する、請求項１に記載の方法。
【請求項４】
前記ターゲット・シードの前記近隣特徴にもっとも類似する近隣特徴を有する複数の要素を包含する参照配置内の参照要素を決定することは、前記参照要素の前記近隣に対して回転を適用して、前記参照要素の前記近隣を前記ターゲット・シードの前記近隣に対して調整することを包含する、請求項１に記載の方法。
【請求項５】
前記反復的に単一要素を合成されるパターン内に配置することは、さらに、フロー・フィールドに従って前記合成されるパターン・エリア内の前記参照要素の前記コピーの配置を調整することを包含する、請求項１に記載の方法。
【請求項６】
さらに、前記フロー・フィールドを指定するユーザ入力を受信することを包含する、請求項５に記載の方法。
【請求項７】
前記合成されるパターン・エリアは１つ又は複数の境界を含み、前記方法は、さらに、前記１つ又は複数の境界に従って前記合成されるパターン・エリア内の前記参照要素のコピーの配置を制限することを包含する、請求項１に記載の方法。
【請求項８】
さらに、前記１つ又は複数の境界を指定するユーザ入力を受信することを包含する、請求項７に記載の方法。
【請求項９】
前記反復的に単一要素を合成されるパターン内に配置することは、ユーザ・インターフェースに設けられたペインティング・ツールを介したユーザ入力の受信に応答して実行される、請求項１に記載の方法。
【請求項１０】
前記参照配置は、複数の異なるタイプの要素を包含する、請求項１に記載の方法。
【請求項１１】
さらに、前記参照配置内の各タイプの各要素に対して記号識別子を割り当てることを包含し、前記記号識別子は、前記参照配置内のそれぞれの要素のタイプを一意的に識別する、請求項１０に記載の方法。
【請求項１２】
さらに、前記参照配置内の各要素にサブ識別子を割り当てることを包含し、前記サブ識別子は、前記参照配置内のそれぞれの要素を一意的に識別する、請求項１１に記載の方法。
【請求項１３】
前記反復的に単一要素を合成されるパターン内に配置することは、さらに、前記参照配置内の前記要素に割り当てられた前記記号識別子及びサブ識別子に従って、前記合成されるパターン・エリア内に配置するために前記参照配置から少なくともいくつかの要素を選択することを包含する、請求項１２に記載の方法。
【請求項１４】
少なくとも１つのプロセッサ、及び
プログラム・インストラクションを包含するメモリを包含し、前記プログラム・インストラクションが、
反復的に単一要素を合成されるパターン内に配置するように前記少なくとも１つのプロセッサによって実行可能であり、それにおいて単一の要素を前記合成されるパターン内に配置することが、
合成されるパターン・エリア内のターゲット・シードを決定すること、
前記合成されるパターン・エリア内の前記ターゲット・シードについての近隣特徴を決定すること、
前記ターゲット・シードの前記近隣特徴にもっとも類似する近隣特徴を有する複数の要素を包含する参照配置内の参照要素を決定すること、及び
前記参照要素のコピーを前記合成されるパターン・エリア内の前記ターゲット・シードの場所に配置すること、
を包含するシステム。
【請求項１５】
前記プログラム・インストラクションが、前記少なくとも１つのプロセッサによって、前記反復的に単一要素を合成されるパターン内に配置することに先行して、
前記参照配置の前記複数の要素の間の連結性を構成し、かつ
前記要素の前記連結性に従って前記参照配置内の各要素の近隣特徴を決定するように実行可能である、請求項１４に記載のシステム。
【請求項１６】
前記反復的に単一要素を合成されるパターン内に配置するために、前記プログラム・インストラクションが、前記少なくとも１つのプロセッサによって、前記ターゲット・シードの前記場所及び前記参照要素の前記近隣特徴に従って前記合成されるパターン・エリア内に１つ又は複数の新しいシードを生成するように実行可能である、請求項１４に記載のシステム。
【請求項１７】
前記ターゲット・シードの前記近隣特徴にもっとも類似する近隣特徴を有する複数の要素を包含する参照配置内の参照要素を決定するために、前記プログラム・インストラクションが、前記少なくとも１つのプロセッサによって、前記参照要素の前記近隣に対して回転を適用して、前記参照要素の前記近隣を前記ターゲット・シードの前記近隣に対して調整するように実行可能である、請求項１４に記載のシステム。
【請求項１８】
前記プログラム・インストラクションが、前記少なくとも１つのプロセッサによって、
前記合成されるパターンのためのフロー・フィールドを指定するユーザ入力を受信し、かつ
前記フロー・フィールドに従って前記合成されるパターン・エリア内の参照要素のコピーの配置を調整するように実行可能である、請求項１４に記載のシステム。
【請求項１９】
前記プログラム・インストラクションが、前記少なくとも１つのプロセッサによって、
前記合成されるパターンのための１つ又は複数の境界を指定するユーザ入力を受信し、かつ
前記１つ又は複数の境界に従って前記合成されるパターン・エリア内の参照要素のコピーの配置を制限するように実行可能である、請求項１４に記載のシステム。
【請求項２０】
前記プログラム・インストラクションが、前記少なくとも１つのプロセッサによって、ユーザ・インターフェースによって提供されるペインティング・ツールを介してユーザ入力を受信するように実行可能であり、前記ユーザ入力は、前記プログラム・インストラクションに、反復的に単一要素を前記合成されるパターン内に配置するように指示する、請求項１４に記載のシステム。
【請求項２１】
前記参照配置は、複数の異なるタイプの要素を包含し、前記プログラム・インストラクションが、前記少なくとも１つのプロセッサによって、
前記参照配置内の各タイプの各要素に対し、記号識別子であって前記参照配置内の要素のそれぞれのタイプを一意的に識別する記号識別子を割り当て、かつ
前記参照配置内の各要素に対し、サブ識別子であって前記参照配置内のそれぞれの要素を一意的に識別するサブ識別子を割り当てるべく実行可能である、請求項１４に記載のシステム。
【請求項２２】
前記反復的に単一要素を合成されるパターン内に配置するために、前記プログラム・インストラクションが、前記少なくとも１つのプロセッサによって、前記参照配置内の前記要素に割り当てられた前記記号識別子及びサブ識別子に従って、前記合成されるパターン・エリア内に配置するために前記参照配置から少なくともいくつかの要素を選択するように実行可能である、請求項２１に記載のシステム。
【請求項２３】
プログラム・インストラクションをストアするコンピュータ可読ストレージ・メディアであって、前記プログラム・インストラクションが、
反復的に単一要素を合成されるパターン内に配置することを実施するようにコンピュータ実行可能であり、前記単一の要素を合成されるパターン内に配置することが、
合成されるパターン・エリア内のターゲット・シードを決定すること、
前記合成されるパターン・エリア内の前記ターゲット・シードについての近隣特徴を決定すること、
前記ターゲット・シードの前記近隣特徴にもっとも類似する近隣特徴を有する複数の要素を包含する参照配置内の参照要素を決定すること、及び
前記参照要素のコピーを前記合成されるパターン・エリア内の前記ターゲット・シードの場所に配置すること、
を包含する、コンピュータ可読ストレージ・メディア。
【請求項２４】
前記プログラム・インストラクションが、前記反復的に単一要素を合成されるパターン内に配置することに先行して、
前記参照配置の前記複数の要素の間の連結性を構成すること、及び
前記要素の前記連結性に従って前記参照配置内の各要素の近隣特徴を決定することを実装するようにコンピュータ実行可能である、請求項２３に記載のコンピュータ可読ストレージ・メディア。
【請求項２５】
前記反復的に単一要素を合成されるパターン内に配置することにおいて、前記プログラム・インストラクションが、前記ターゲット・シードの前記場所及び前記参照要素の前記近隣特徴に従って前記合成されるパターン・エリア内に１つ又は複数の新しいシードを生成することを実施するようにコンピュータ実行可能である、請求項２３に記載のコンピュータ可読ストレージ・メディア。
【請求項２６】
前記ターゲット・シードの前記近隣特徴にもっとも類似する近隣特徴を有する複数の要素を包含する参照配置内の参照要素を決定することにおいて、前記プログラム・インストラクションが、前記参照要素の前記近隣に対して回転を適用して、前記参照要素の前記近隣を前記ターゲット・シードの前記近隣に対して調整することを実装するようにコンピュータ実行可能である、請求項２３に記載のコンピュータ可読ストレージ・メディア。
【請求項２７】
前記プログラム・インストラクションが、
前記合成されるパターンのためのフロー・フィールドを指定するユーザ入力を受信すること、及び
前記反復的に単一要素を合成されるパターン内に配置することにおいて、フロー・フィールドに従って前記合成されるパターン・エリア内の参照要素のコピーの配置を調整することを実装するようにコンピュータ実行可能である、請求項２３に記載のコンピュータ可読ストレージ・メディア。
【請求項２８】
前記プログラム・インストラクションが、
前記合成されるパターンのための１つ又は複数の境界を指定するユーザ入力を受信すること、及び
前記反復的に単一要素を合成されるパターン内に配置することにおいて、前記１つ又は複数の境界に従って前記合成されるパターン・エリア内の参照要素のコピーの配置を制限することを実施するようにコンピュータ実行可能である、請求項２３に記載のコンピュータ可読ストレージ・メディア。
【請求項２９】
前記プログラム・インストラクションが、ペインティング・ツールを介してユーザ入力を受信することを実装するようにコンピュータ実行可能であり、それにおいて前記反復的に単一要素を合成されるパターン内に配置することが、前記ペインティング・ツールを介した前記ユーザ入力の受信に応答して実行される、請求項２３に記載のコンピュータ可読ストレージ・メディア。
【請求項３０】
前記参照配置は、複数の異なるタイプの要素を包含し、それにおいて前記プログラム・インストラクションが、
前記参照配置内の各タイプの各要素に対し、記号識別子であって前記参照配置内の要素のそれぞれのタイプを一意的に識別する記号識別子を割り当てること、
前記参照配置内の各要素に対し、サブ識別子であって前記参照配置内のそれぞれの要素を一意的に識別するサブ識別子を割り当てることを実施するようにコンピュータ実行可能である、請求項２３に記載のコンピュータ可読ストレージ・メディア。
【請求項３１】
前記反復的に単一要素を合成されるパターン内に配置することにおいて、前記プログラム・インストラクションが、前記参照配置内の前記要素に割り当てられた前記記号識別子及び前記サブ識別子に従って、前記合成されるパターン・エリア内に配置するために前記参照配置から少なくともいくつかの要素を選択することを実装するようにコンピュータ実行可能である、請求項３０に記載のコンピュータ可読ストレージ・メディア。
【発明の詳細な説明】
【技術分野】
【０００１】
優先権情報
本件出願は、参照によってその全内容がこれに援用される「イグザンプル‐ベースド・プロシージュアル・シンセシス・オブ・エレメント・アレンジメンツ(Example‐Based Procedural Synthesis of Element Arrangements)」と題されて２００７年８月３１日に出願された米国特許仮出願第６０／９６９，５０８号の優先権の恩典を主張する。
【背景技術】
【０００２】
関連技術の説明
要素配置は、人工的環境（たとえば、タイル、建築物、ファサード、装飾アート等）及び自然環境（たとえば、蜂の巣、花弁、砂利、小石の浜辺、雲等）の両方に遍在する。要素の２次元（２Ｄ）配置は、たとえばタイル、壁紙、ハッチングのストローク、装飾アート、織地、花弁、蜂の巣、動物の毛皮と鱗、波、砂丘等々のように人工又は自然いずれの環境でも観察できる。要素配置の合成は、テクスチャの作成や非フォトリアリスティック(non-photorealistic)・レンダリングのための有用なツールである。配置パターンの合成は、テクスチャ生成や非フォトリアリスティック・レンダリング（ＮＰＲ）に有用なだけでなく、コンピュータ・グラフィクスにも興味深い努力目標を投げかける（たとえば、規則的なパターン、規則的に近いパターン、不規則な分布）。これらの配置は大きな変動を有し、それらのうちのいくつかは、全体を通じて規則的又は規則的に近い特徴を持つが、そのほかは、局所的に規則的でないが、不規則な特徴を一様（不規則一様）に分布している。配置パターンを合成するためには、全体的分布における要素間の局所的な空間的関係を保存するテクニックが必要となる。
【０００３】
一般的なテクスチャ・パターンを生成するためのテクニックの２つの異なるグルーピングは、テクスチャ合成と手続き的モデリングである。テクスチャ合成テクニックは、見本画像を採用して新しいテクスチャを生成する。テクスチャ合成テクニックは、概して３つのグループ、すなわち周波数ドメイン、ピクセル‐ベース、パッチ‐ベース、にカテゴリ分けできる。周波数ドメインのテクニックは、通常、特定タイプのテクスチャだけを扱うことが可能である。ピクセル・ベースとパッチ・ベースのテクニックは、より一般的なテクスチャについての説得力のある結果を達成できる。しかしながら、要素配置では各ピクセルではなく各要素が個別に知覚可能なことから、これらのテクニックを要素配置に直接適用することは困難である。要素間の空間的関係は、ピクセル間のそれより重要である。
【０００４】
手続き的モデリング・テクニックは、要素を単位モジュールとして扱う。手続き的モデリング・システムは、初期特徴から開始し、局所的な生成規則に基づいてモジュールの漸進的な置換と追加を行う。しかしながら手続き的フレームワークは、要素がツリー等の明示的な局所構造を有するパターンに限定されている。たとえば、不規則一様な配置について成長規則を定義することは困難である。いくつかの手続き的モデリング・テクニックは印象的な結果を達成しているが、それらのテクニックは、通常、局所的成長規則を定義するスクリプトの記述をユーザに要求し、初心者ユーザが結果として得られるモデルをコントロールすることを困難にしている。
【０００５】
ストローク・パターン合成
ストローク・パターン合成は、非フォトリアリスティック・レンダリング（ＮＰＲ）分野で好まれているトピックである。ストローク・パターン合成テクニックは、マニュアル選択されるか、又は伝統的な図形上で観察される生成規則に基づいてストローク・パターンを合成する。通常、すべてのストロークが曲線上に線形順序で整列される比較的単純なケースに焦点を当てる見本ベース・システムが開発された。ストローク・ベースの分析及び合成のテクニックは、規則的又は規則的に近いパターンの扱い、及び煉瓦の壁等の構造化されたパターンの合成時に困難を有することがある。
【発明の開示】
【課題を解決するための手段】
【０００６】
見本から要素配置を合成するための方法及び装置の種々の実施態様が説明されている。実施態様は、たとえば、見本配置から要素配置パターンを合成する。実施態様は、従来方法のようにスクリプトを通じてではなく、見本の提供を介して動作する。グリッド上に整列されるピクセルを扱うテクスチャ合成に使用されるアプローチとは対照的に、実施態様のターゲットは、要素が必ずしも整列されなくてよい要素配置である。したがって実施態様は、各要素の「空間的」近隣特性を考慮できる。実施態様は、見本（参照配置）とターゲットの局所的近隣比較に基づくテクスチャ合成テクニックと、局所的成長に基づく手続き的モデリングを結合できる。
【０００７】
１つの実施態様は、参照配置、たとえばユーザによって入力されるか、又はそのほかの指定された見本を採用し、かつ当該配置の要素間における連結性を構成することによって局所的構造が分析される。その参照配置を前提とし、実施態様は、各要素のすぐ隣の情報を獲得するように連結性を構成できる。合成プロセスは、単一のシードを伴って開始し、かつ新しいシードの場所に新しい要素を１つ１つ置くことによって合成中のパターンを外側に拡大できる。１つの実施態様においては、このプロセスが局所的な近隣の比較を適用でき、参照要素は、合成済みパターン内のターゲット・シードの近隣の特徴にもっとも類似する近隣特徴を有する参照配置から選択できる。
【０００８】
実施態様は、参照配置として参照できる入力された例示的な要素の配置を採用し、かつ当該参照配置に類似する新しいより大きなパターンを生成又は合成できる。参照配置は、あらかじめ定義済みの記号のセットから１つ又は複数の記号を使用できる。このセット内の各記号は、記号識別子（記号ＩＤ）を有するか、又は割り当てられるようにできる。それに加えて、参照配置内の各記号は、ここでサブＩＤと呼ばれる、合成プロセス内で同一の記号ＩＤを有する記号間の区別に使用できる一意的な識別子を有するか、又は割り当てられる。
【０００９】
種々の実施態様は、局所的成長プロセス内において１つ又は複数の異なるモードを設けることができる。それらのモードは、限定はされないが、システムが回転を伴わずに参照要素を使用できる非回転モード、システムが回転を考慮に入れて最良フィッティング参照要素をサーチし、より良好な分布を結果としてもたすことができる回転モード、及びシステムが参照を回転し、その局所座標を、基礎をなすユーザ指定のフロー・フィールド方向に対して調整するフロー・フィールド・モードのうちの１つ又は複数を含むことができる。
【００１０】
種々の実施態様は、ユーザ・インターフェースを介して、結果として得られる配置の全体的様相をコントロールするための１つ又は複数の異なるタイプのツールを設ける。それらのツールは、ペインティング・ツール、たとえばカーソル・エリア下のシードをアクティブ化するスプレー・ツールを含むことができる。このツールによって、ユーザは配置パターンをペイントすることができる。またツールは、ユーザがストロークのセットを描くことによってフロー・フィールドをデザインすることを可能にするフロー・フィールド・ツールを含む。システムは、入力されたストロークの方向を制約条件として使用し、かつ２Ｄ空間を、たとえばラジアル・ベース関数を使用して補間することができる。またツールは、局所的成長を制限するか、又は停止させる境界ストロークのセットをユーザが描くことを可能にする境界ツールを含む。
【００１１】
見本から要素配置を合成するための方法及び装置の実施態様は、スタンドアロン・アプリケーション内における見本ベースの手続き的パターン合成モジュールとして、又はグラフィック・アプリケーション又はグラフィック・ライブラリのモジュールとして実装できる。実施態様が実装できるグラフィック・アプリケーションの例は、限定はされないが、ペインティング、出版、写真、ゲーム、アニメーション、及び／又はそのほかのアプリケーションを含む。
【００１２】
本発明は、ここで例としていくつかの実施態様及び例証的図面について説明されているが、当業者であれば、説明されているそれらの実施態様又は図面に本発明が限定されないことを認識されるであろう。理解される必要があるが、図面やそれに対する詳細な説明は、開示されている特定の形式に本発明を限定することを意図するものでなく、むしろ逆にその意図は、付随する請求項によって定義されるとおりの本発明の精神及び範囲内に含まれるあらゆる修正、等価、及び代替を保護するところにある。ここに使用されている小見出しは、整理だけを目的としており、説明又は請求項の範囲を限定するための使用を意味していない。この出願全体を通じて使用されているとおり、表現「できる」は、必須の意味（すなわち、でなければならないという意味）ではなく、随意的な意味（すなわち、可能性を有するという意味）で使用されている。同様に「含む」、「含んでいる」、及び「含まれる」は、包含を意味し、それへの限定ではない。
【発明を実施するための最良の形態】
【００１３】
見本から要素配置を合成するための方法及び装置の種々の実施形態が説明されている。実施形態は、たとえば、１つ又は複数のタイプの複数の要素を含む見本パターンから要素配置パターンを合成できる。種々の実施形態は、局所的近隣比較に基づいて１つ又は複数のテクスチャ合成方法の組み合わせを、及び局所的成長に基づいて１つ又は複数の手続き的モデリング・システムを使用できる。実施形態は、コンピュータにより実施される要素配置合成システムを、使用容易なフレームワークを介して設けることができる。実施形態は、従来方法におけるようなスクリプト記述を通じてではなく、見本の提供を介して動作できる。実施形態は、コントロール可能な合成プロセスを、限定はされないが、ペインティング（たとえばスプレー）ツール、フロー・フィールド・ツール、及び境界ツールを含む１つ又は複数のツールを介して設けることができる。
【００１４】
実施形態は、参照配置と呼ぶことができる見本とターゲットの局所的近隣比較に基づくテクスチャ合成テクニックと、局所的成長に基づく手続き的モデリングとを結合する。実施形態は要素配置に焦点を合わせているが、各要素の形状を合成しなくてもよい。１つの実施形態においては、参照配置の各要素が当該参照配置内における要素のタイプを一意的に識別する記号識別子（ＩＤ）、及び当該参照配置内における要素を一意的に識別するサブＩＤを有するか、又は割り当てられる。
【００１５】
見本から要素配置を合成するための方法及び装置の実施形態は、スタンドアロン・アプリケーション内における見本ベースの手続き的パターン合成モジュールとして、又はグラフィック・アプリケーション又はグラフィック・ライブラリのモジュールとして実装できる。実施形態が実装できるグラフィック・アプリケーションの例は、限定はされないが、ペインティング、出版、写真、ゲーム、アニメーション、及び／又はそのほかのアプリケーションを含む。
【００１６】
図１ａ〜１ｃを参照すると、１つの実施形態は、ユーザによって入力されるか、又はそのほかの指定ができる参照配置を採用し、かつ連結性を構成することによって局所的構造が分析される。その参照配置を前提とし、実施形態は、各要素のすぐ隣の情報を獲得するように連結性を構成できる（図１ａ参照）。合成プロセスは、単一のシードを伴って開始し、新しい要素を１つ１つ置くことによって合成中のパターンを外側に拡大する。１つの実施形態においては、このプロセスが局所的な近隣の比較を適用でき、参照要素は、以前の合成済みパターンのターゲットの場所にもっとも類似する近隣特徴を有する参照配置から選択できる。ほとんどすべての要素が一様に分布されているが、２つのグレイの要素が概して隣接して現れている例示的な合成済みパターンを示している図１ｂに示されているとおり、その後、類似する局所構造を有するより大きなパターンを合成できる。ペインティング、描画、又は配置パターンを用いたそのほかの機能の実行のため、及びフロー・フィールドをコントロールするために、１つ又は複数のユーザ・インターフェース・ツールを設けることができる。たとえば図１ｃは、実施形態によって用意されたスプレー・ツール等の例示的なペインティング・ツールの例示的な結果を示している。
【００１７】
実施形態は、参照配置として参照できる入力された要素の配置を採用し、かつ当該参照配置に類似する新しいより大きなパターンを生成又は合成できる。参照配置は、あらかじめ定義済みの記号のセットから１つ又は複数の記号を使用できる。このセット内の各記号は、記号識別子（記号ＩＤ）を有する。それに加えて、参照配置内の各記号は、ここでサブＩＤと呼ばれる、合成プロセス内で同一の記号ＩＤを有する記号間の区別に使用できる一意的な識別子を有するか、又は割り当てられる。図２ａは、１つの実施形態に従った参照配置を示している。図２ｂは、１つの実施形態に従った図２ａ内の参照配置の要素のための記号ＩＤを示している。図２ｃは、１つの実施形態に従った図２ａ内の参照配置の要素のためのサブＩＤを示している。
【００１８】
１つの実施形態においては、要素配置に焦点が当てられ、したがって記号の形状は合成されなくてよい。それに代わりこの実施形態は、ユーザがランダム・ノイズを導入して合成済み要素の回転及びスケールを修正すること、したがってより変化を獲得することを可能にする。
【００１９】
種々の実施形態は、局所的成長プロセスにおいて１つ又は複数の異なるモードを使用できる。それらのモードは、限定はされないが、次のうちの１つ又は複数を含むことができる。
・  システムが回転を伴うことなしに参照要素を使用できる非回転モード。
・  システムが参照要素の回転を考慮に入れて最良フィッティング参照要素をサーチし、より良好な分布を結果としてもたらすことができる回転モード。
・  システムが参照を回転し、それの局所座標を、基礎をなすユーザ指定のフロー・フィールド方向に対して調整するフロー・フィールド・モード。これは、合成される配置の全体的なフローのコントロールを可能にする。
【００２０】
クリエイティブなデザイン・プロセスをサポートするために、種々の実施形態は、ユーザ・インターフェースを介して、結果として得られる配置の全体的様相をコントロールするための１つ又は複数の異なるタイプのツールを提供できる。それらのツールは、限定はされないが、次のうちの１つ又は複数を含むことができる。
・  ペインティング・ツール、たとえばカーソル・エリアの下のシードをアクティブ化するスプレー・ツール。このツールは、ユーザが配置パターンをペイントすることを可能にする。実施形態は、充分に速く、迅速なフィードバックを返す。
・  ユーザがストロークのセットを描くことによってフロー・フィールドをデザインすることを可能にするフロー・フィールド・ツール。システムは、入力されたストロークの方向を制約条件として使用し、２Ｄ空間を、たとえばラジアル・ベース関数を使用して補間できる。
・  局所的成長を停止させる境界ストロークのセットをユーザが描くことを可能にする境界ツール。
【００２１】
グリッド上に整列されるピクセルを扱うテクスチャ合成に使用されるアプローチとは対照的に、実施形態のターゲットは、要素が必ずしも整列されなくてよい要素配置とすることができる。したがって実施形態は、各要素の「空間的」近隣特性を考慮できる。
【００２２】
図３ａ〜３ｅは、１つの実施形態に従った例示的な分析段階と合成段階を示している。図３ａ、３ｂは、分析段階を示している。図３ａにおいては、見本又は参照配置が提供される。図３ｂにおいては、参照配置内の要素の連結が構成される。図３ｃ〜３ｅは、参照配置に基づいてパターンを合成するための合成段階を示している。図３ｃにおいて、円はシードを表す。新しい要素のための候補ポジション（候補シード）が示されている。図３ｄにおいては、図３ａの参照配置からの最良フィッティング要素が見つけ出される。図３ｅにおいては、その要素を用いて候補シードが置換される。新しいシードが生成される。このプロセスが繰り返し反復され、所望のパターン・エリアが満たされてしまうまでパターン内に単一の参照要素が置かれる。
【００２３】
図４は、１つの実施形態に従って見本から要素配置を合成するための方法を示したフローチャートである。２００においては、参照配置の要素間の連結性が構成される。参照配置は、たとえば、複数の要素を含み、１つ又は複数のタイプの要素を伴うユーザ指定パターンとすることができる。２０２においては、構成済みの連結性に従って参照パターン内の各要素の近隣情報が分析される。２０４においては、合成されるパターン・エリア内のターゲット・シードが決定される。たとえばユーザはスプレー・ツール等のツールを使用してスクリーン上の場所の上をクリックして開始場所を示し、その開始場所を初期ターゲット・シードとして使用する。このほかの方法も、初期ターゲット・シード及びその後に続くシードの決定に使用できる。２０６においては、ターゲット・シードのための近隣特徴が決定される。初期シードは、まだ近隣を有してなくてよく、そのため初期シードのためにデフォルトの「近隣」が仮定されるか、又は初期シードのための近隣特徴を決定するそのほかの方法（たとえば、ランダム配置）を使用する。２０８においては、ターゲット・シードの近隣特徴にもっとも類似する近隣特徴を有する参照配置内の参照要素が決定される。２１０に示されているとおり、参照要素のコピーを、合成されるパターン・エリア内のターゲット・シードの場所に配置できる。新しいシードを、たとえば参照要素の近隣情報を使用して生成する。２１２において、パターンの合成が完了していなければ、プロセスが２０４に戻り、次のターゲット・シードを決定する。完了していればパターンの合成が終了する。
【００２４】
図５ａ〜５ｈは、１つの実施形態に従った例示的な局所的成長プロセスを示しており、単一の繰り返しステップの例を示している。この例においては、白い石の記号ＩＤがＡ、グレイの石の記号ＩＤがＢである。参照配置を前提とし、分析段階の中で、たとえば参照配置の三角形分割法によって近隣要素間の局所的関係が分析される。この合成プロセス又は段階は、単一のシードの配置を伴って開始する。シードは、参照配置及びいくつかの新しいシードからの参照要素を用いて繰り返し置換される。各繰り返しにおいては、シードの近隣の獲得をサポートする、新しい要素とシードについての連結性を構成できる。図５ａ〜５ｈは、単一の繰り返しステップの例を示しているが、各繰り返しの中で実行される例示的なプロセスのいくつかの段階をグラフィカルに示している。図５ａにおいては、ターゲット・シード１００としてシードが選択される。図５ｂにおいては、選択されたシード１００の近隣がチェックされ、矢印によって示されるとおりに連結性が構成される。図５ｃにおいては、選択されたシード１００のそれにもっとも類似する近隣状態を有する参照要素１０２が参照配置の中で見つけ出される。図５ｄにおいては、見つけ出された参照要素１０２のコピーを用いてターゲット・シード１００が置換される。図５ｅと５ｆにおいては、プロセスが参照要素１０２の近隣要素のコピーを獲得する。図５ｇにおいては、プロセスが、コピーのフィッティング未済の部分を新しいシードとして配置する。図５ｈにおいては、エッジが構成される。１つの実施形態においては、滑らかなパターンを獲得するために、各成長プロセスの後に全体的な緩和を導入できる。
【００２５】
図６ａ、６ｂは、１つの実施形態に従った分析段階における与えられた見本又は参照配置（図６ａ）のための連結性の生成（図６ｂ）を示している。連結性を構成するために、１つの実施形態においては、デローネイの三角形分割法を使用できる。１つの実施形態においては、ひずんだ三角形（たとえば、指定スレッショルド、たとえば１５０度より大きい角度を含むすべての三角形）を除去できる。１つの実施形態においては、非境界要素だけ使用できる。１つの実施形態においては、１つ又は複数の設けられたユーザ・インターフェース要素又はコントロールを介してユーザが連結性を修正することが可能である。実施形態は、最長又は最短のエッジ長を計算する。１つの実施形態においては、ガウス分布を仮定する。
【００２６】
１つの実施形態においては、入力された参照配置又は要素を前提とし、デローネイの三角形分割法等の数学的三角形分割テクニックを使用して連結性を抽出する。１つの実施形態においては、三角形分割法の中で各要素の中心ポジションを使用する。デローネイの三角形分割法は、境界周辺でひずんだ三角形を生成できるが、そのため１つの実施形態は、ひずんだ三角形、たとえば２／３×πより大きい角度を有する三角形を除去でき、かつ少なくとも１つのひずんでいない三角形部分であるエッジだけを残す。各要素の直近の相対的ポジション、記号ＩＤ、及びサブＩＤを、その後記録する。１つの実施形態においては、参照配置の境界の周囲の要素が充分な近隣要素を有していないことから、それらは使用されなくてよい。
【００２７】
規則的な、又は規則的に近い配置が入力されるとき、デローネイの三角形分割法等の三角形分割法テクニックは、望ましくない連結を生成することがある。図７ａ〜７ｃ及び８ａ〜８ｃは、１つの実施形態に従った参照配置及び要素間の連結性のいくつかの例を示している。図７ｂにおいては、図７ａ内で入力されたとおりの配置について、いくつかの生成済みエッジが１行を超えるブロックを連結している。図８ａにおいては規則的に近い配置が入力されるが、図８ｂ内には、規則性を持たないエッジが生成される。ここに述べられている合成アルゴリズムは、各要素の局所的連結性によって影響されることがあり、したがって、これらの連結が規則的パターンを乱すことがある。したがって１つの実施形態は、三角形分割法の後にユーザが連結を訂正することが可能である。たとえば、１つの実施形態においては、ユーザが、クリックによって、又は何らかのほかのユーザ・インターフェース・ツール又は方法によってエッジをフリップすることが可能である。これによって、ユーザが望ましい連結性を獲得することが可能である。したがって１つの実施形態においては、図７ａ、８ａに示されているとおりの参照配置に対して、図７ｂ又は８ｂに示されているとおりに、システムが連結性を自動的に生成できるが、ユーザは、実施形態によって提供される１つ又は複数のツールを使用して、図７ｃ、８ｃに示されているとおりに基礎をなす規則性を再構成するようにトポロジを修正できる。
【００２８】
図９ａ〜９ｃは、１つの実施形態に従った、ユーザにより案内される連結性の訂正を示している。図９ａは、例示的な初期参照配置を示している。図９ｂは、システムにより生成される例示的な連結性を示している。図９ｃは、ユーザによって訂正された例示的な連結性を示している。
【００２９】
局所的成長による合成
１つの実施形態は、パターンの中心の要素を用いて開始し、以前の合成済み要素の近隣比較に基づき、新しい要素を１つ１つ置くことによってそれを外側に拡大できる。しかしながらターゲット要素配置は、グリッド上のピクセルの場合におけるように、規則的な構造を有することが必ずしも常に想定されていない。新しい要素を配置するためのポジション及びその近隣が不明確なことがある。さらに、個別の要素のサイズと向きが異なることがある。これらは、従来のテクスチャ合成テクニックと、ここで述べている方法の間における主要な相違である。
【００３０】
１つの実施形態においては、この問題を取り扱うために、参照配置内の要素の連結性に基づいてシードの局所的成長を定義する見本ベースの手続き的方法が使用できる。各成長ステップにおいては、シードを最良フィッティング参照要素を用いて置換することに加え、選択された参照要素の直近をコピーすることによって新しいシードを配置できる。
【００３１】
シーディング
シードは、新しい要素の候補ポジションである。オプションとしてシードは、それに関連付けされた記号ＩＤを有する。記号ＩＤは、シードを特定タイプの要素にするために使用できるが、それが参照配置からの同一記号ＩＤの要素（同一タイプの要素）となる可能性がある。
【００３２】
１つの実施形態においては、単一のシードを配置することによって合成プロセスを開始できる。１つの実施形態においては、初期シードからの距離によってシードをソートでき、各成長ステップにおいては、もっとも近いシードを選択できる。たとえばスプレー・ツール・モードにおいては、ユーザがペインティングを開始するときにカーソル・ポジションに新しいシードを生成でき、スプレー・ツールは、ペイント中のカーソルからユーザが指定したか、又はそのほかの形で示される距離内にあるすべてのシードを成長させることができる。
【００３３】
図１０ａ〜１０ｃは、１つの実施形態に従ったシーディングを示している。各シードは記号ＩＤを有する。図１０ａにおいては、参照配置から最良フィッティング要素が見つけ出される。図１０ｂにおいては、新しいシードが配置される。１つの実施形態においては、非マッチング近隣が新しいシードとして配置される。図１０ｃにおいては、リング・エッジが追加される。緩和が実行される。緩和については、さらに後述する。
【００３４】
要素が異なる重要度を有するいくつかの配置パターンがある。たとえば、配置パターンが、より大きい要素（１つ又は複数）を最初に配置し、より小さい要素（１つ又は複数）を後に用いて空間を埋めることができる。１つの実施形態は、この効果を、要素の記号ＩＤに基づいてシードに配置されることになる要素の優先度を指定することによって提供することができる。１つの実施形態は、近隣エリア内のもっとも高い、又は同一の優先度を伴うシードだけを成長させる。たとえば、１つの実施形態は、参照内のエッジの平均の長さをｌとするとき、５×ｌの半径を伴う円として近隣エリアを定義する。たとえば図１ｂにおいては、より高い優先度がより大きいグレイの石及び白い石に対して指定され、より低い優先度が、フィラーのみとして使用される小さい石に対して指定される。
【００３５】
図１１ａ、１１ｂ、及び図１２ａ、１２ｂは、１つの実施形態に従ったシードの併合の２つの例を示している。図１１ａ、１２ａにおいては、新しいシードの近隣エリアがチェックされ、そのシードの指定距離内に要素又はシードが存在するか否かが調べられる。新しいシードに近い要素又はシードが存在する場合には、当該新しいシード及び当該近隣シード又は要素を、図１１ｂ、１２ｂに示されているとおりに併合する。
【００３６】
図１３ａ〜１３ｃは、１つの実施形態に従った衝突の取り扱いを示している。図１３ａにおいては、新しいシードの近隣エリアがチェックされ、衝突が存在するか否かが調べられる。図１３ｂは、検出された衝突を示している。図１３ｃにおいては、新しいシードが取り除かれる。
【００３７】
図１４ａ〜１４ｆは、１つの実施形態に従ったリング・エッジの生成を示している。図１４ａ、１４ｂにおいて、１つのリング・エッジが生成される。図１４ｃにおいては、新しいエッジの長さがチェックされる。その長さが、参照配置内におけるもっとも長いエッジより長い場合には、図１４ｄに示されているとおり、追加のシードが追加される。図１４ｅにおいては、衝突がチェックされる。衝突が検出される場合には、図１４ｆに示されているとおり、エッジが生成されない。
【００３８】
最良マッチング要素を見つけ出す
図１５ａ〜１５ｃは、１つの実施形態に従ったパターンのマッチングを行う例を示している。システムは、図１５ａ内のターゲット・シード１１０の近隣と、図１５ｂの参照要素１１２のそれの間におけるマッチング・パターンのセットを構成する。図１５ｃにおいては、対応が定義される。
【００３９】
図１５ａ〜１５ｃを参照し、ｅtar（ターゲット・シード１１０）を合成されるパターン内で焦点が当てられたシードとし、ｗ（ｅtar）をそれの直近の要素のセットとする。同様にｅref（参照要素１１２）及びｗ（ｅref）は、参照要素についての表記法である。ｗ（ｅtar）とｗ（ｅref）の間の差に基づいてエラー関数を定義でき、そのエラー関数を最小化する１つを見つけ出すべくすべての参照要素を試験できる。
【００４０】
【数１】
2009059368.tif 000003
【００４１】
注意されたいが、ターゲット・シードが記号ＩＤを有する場合は、対応する参照要素（同一記号ＩＤを伴う参照要素）だけ試験される。
【００４２】
要素配置のための近隣比較は、近隣要素の数とポジションが分布に応じて変動することから、テクスチャ合成のためのものより複雑である。１つの実施形態においては、差を２ステップで計算できる。第１は、参照近隣の要素に対してターゲットの近隣の各要素をマッチングさせるマッチングｆが構成される。いくつかの候補マッチング・パターンが存在することから、マッチング・パターンＦのセットを構成する必要がある。第２は、すべての関連ペアについての差を計算でき、かつ各ｆ∈Ｆに関して総和を求める。
【００４３】
１つの実施形態においては、マッチング・パターンＦのセットを構築するためにスリップやフリップを伴わない場合だけを考慮できる。最初に要素ｅtari∈ｗ（ｅtar）及びｅrefj∈ｗ（ｅref）を、反時計方向の順序でソートする。要素は、反時計方向以外の順序でもソートできる。ターゲットの近隣について、１つの実施形態は、境界上にある要素を伴って開始できる（図１５ａ参照）。１つの実施形態は、１つの対応ｆ0を獲得するように、ｅtar0及びｅref0を初期ペアとして選択し、漸増的にその後に続く要素ｅtari及びｅrefiのマッチングを行う。類似の態様において、１つの実施形態は、ｅtar0及びｅrefkを初期ペアとして選択することによってｆkを獲得できる。１５ａ〜１５ｃに与えられている例においては、６つのマッチング・パターンが獲得される。
【００４４】
１つの実施形態は、ターゲット・シードが成長下にあり、かつその近隣要素の数が比較的小さいことから、ｗ（ｅtar）のサイズがｗ（ｅref）のそれに等しいか、又はそれより小さいこと、及びターゲット・シードが境界上にあることを仮定する。しかしながら、例外的なケースが時折生じることがある。たとえば、シードのすべての近隣要素が、優先度の相違又はスプレー・ツールの使用に起因してすでに配置済みのことがある。シードが境界上にないとき、１つの実施形態は、そのソーティングを任意の要素からソートし、かつｗ（ｅtar）のサイズがｗ（ｅref）より大きいときは、単純にその種の参照要素を無視できる。
【００４５】
マッチング・パターンのセットが獲得されると、１つの実施形態は、各ｆ∈Ｆに関して次のとおりのエラー関数を定義できる。
【００４６】
【数２】
2009059368.tif 000004
【００４７】
ｄ（ｅtar，ｅref）は、ｅtarとｅrefの相対ポジション間のユークリッド距離である。ｉｄ（ｅtar，ｅref）は、ｅtarの記号ＩＤがｅrefのそれと異なる場合に１を返し、それ以外は０を返す。これら２つの項は、局所的な空間的関係を測定する。１つの実施形態においては、再三にわたって同一要素が繰り返し現れることを回避するためにｓｕｂｉｄ（ｅtar，ｅref）を使用できる。この関数は、ｅtar及びｅrefのｓｕｂ＿ｉｄが同一であるとき１を返し、それ以外は０を返す。１つの実施形態においては、重みｗ3が大きい（指定スレッショルドを超える）場合に、結果として得られるパターン内において参照配置の構造をより良好に保存できる。１つの実施形態は、次のエラー関数を定義できる。
【００４８】
【数３】
2009059368.tif 000005
【００４９】
回転モード
種々の実施形態は、異なる目的のために異なる結果を生成するように１つ又は複数のモードを設ける。参照近隣の向きを保存するパターンの生成に使用できる非回転モードが設けられる。局所的なターゲット近隣の向きに対してそれを調整するように参照要素の近隣の向きを変更する回転モードが設けられ、より良好な分布を結果としてもたらす。ユーザ指定の、たとえばユーザによって、ここで述べられているようなフロー・フィールド・ツールの適用を通じて指定されるフロー・フィールドを追従するパターンを生成するフロー・フィールド・モードも設けられている。実施形態は、図１６ａ〜１６ｅの例によって示されるとおりの最良マッチング要素を見つけ出すプロセスに対する修正によってそれらの効果を達成できる。システムは、図１６ａに示されている例示的な参照要素を、図１６ｂに示されている例示的なターゲット・シードに、選択されたモードに応じて異なってフィッティングる。図１６ｃは、非回転モードの例示的な結果を示している。図１６ｄは、回転モードの例示的な結果を示している。図１６ｅは、フロー・フィールド・モードの例示的な結果を示している。
【００５０】
非回転モードにおいては、最良フィッティング要素が、参照パターン（参照要素及びその近隣）の回転を伴わずに見つけ出され、エラー関数（１）はそのまま解かれる。回転モードにおいては、エラー関数（２）の計算時に最良フィッティングの回転を考慮できる。１つの実施形態においては、角度シータを用いて参照要素を回転することによってポジションの差を最小化できる。
【００５１】
【数４】
2009059368.tif 000006
【００５２】
ここでＲθ（ｅrefj）は、ｅrefjの相対ポジションを回転させる。１つの実施形態においては、種々の形状マッチング方法のうちの１つを適用できる。
【００５３】
フロー・フィールド・モードにおいては、最良マッチングを見つけ出すときにユーザ指定のフロー・フィールドを考慮する。ターゲット・シードのポジションにおけるフロー・フィールドの向きが獲得される。その後、その向きに対してその局所ｘ座標を調整し、したがってｅref_flow及びｗ（ｅref_flow）を獲得するように全体の参照パターンが回転される。回転後の参照は、最良マッチングを見つけ出すときに使用できる。
【００５４】
局所的成長
上で述べたプロセスの実施形態を使用し、最良フィッティング参照要素及びオプションとして回転モードにおける最良フィッティング回転又はフロー・フィールド・モードにおけるフロー・フィールド回転を見つけ出すことができる。１つの実施形態は、最良フィッティング要素を使用することによって、リング形状と呼ぶことができるものを形成するターゲット・シード及びその近隣のポイント又は要素を局所的に成長させることができる。注意を要するが、これらの回転のうちの１つが利用可能である場合には、それを、以下に述べるプロセスの前に、参照要素及びそのリング形状に対して適用できる。
【００５５】
再び図５ａ〜５ｈを参照すると、１つの実施形態において、最初にシステムは、見つけ出された参照要素１０２を用いてターゲット・シード１００を置換する（たとえば、図５ｃ及び５ｄ参照）。システムは、記号ＩＤ及びサブＩＤをコピーする。次にシステムは、見つけた参照要素１０２の近隣要素を使用することによって新しいシードを配置し、それらの近隣要素が、ここでリング形状と呼ぶものを形成する。システムは、参照リング形状のコピーをターゲット・シード近隣に重ね（たとえば、図５ｆ参照）、その後、エラー関数の計算時にターゲット近隣要素とペアにされた各近隣要素を削除する。残された要素は、対応する記号ＩＤを伴う新しいシードを形成する（たとえば、図５ｇ参照）。最後に、新しいシードを連結するようにエッジが構成される（たとえば、図５ｈ参照）。
【００５６】
分布の過密又は過疎及び／又はエッジの衝突を回避するため、実施形態は、局所的成長プロセスの間に１つ又は複数のヒューリスティックを実装する。図１７ａ〜１７ｆは、１つの実施形態に従って望ましくない構造を回避するために使用できるヒューリスティック・アプローチを示している。新しいシードの獲得後、１つの実施形態は、各新しいシードの近隣エリアをチェックする。当該シードから距離スレッショルドｌshort内に既存の要素又はシードが見つけ出されると、そのシードが削除され、見つけ出されたオブジェクトにエッジが連結される。１つの実施形態は、参照内におけるもっとも短いエッジ長の２分の１をｌshortとして使用する。ほかの実施形態は、そのほかの長さ又は方法をｌshortの計算に使用する。１つの実施形態は、新しいエッジ間の角度をチェックし、その角度が０．５×ｏｒｉｇｉｎａｌ＿ａｎｇｌｅより小さいときは、新しいシード及びエッジが削除される（図１７ｃ参照）。ｏｒｉｇｉｎａｌ＿ａｎｇｌｅは、選択された参照リング形状内のエッジ間の対応する角度である（図１７ａ参照）。１つの実施形態は、新しいシードのエッジの衝突をチェックし、検出された場合には、当該シード及びエッジが除去される（図１７ｄ参照）。新しいシードの周囲に新しいエッジを構成するとき、１つの実施形態は、各エッジの長さをチェックする。エッジがスレッショルドｌlongより長い場合に、１つの実施形態は、対応する記号ＩＤを伴わない追加シードを生成する（図１７ｅ参照）。１つの実施形態は、対応する角度を二分し、かつその長さが２つの隣接するエッジの平均となる線分の端にシードを配置する（図１７ｅ参照）。１つの実施形態においては、ｌlongを１．５×ｏｒｉｇｉｎａｌ＿ｌｅｎｇｔｈとして定義するが、その際、ｏｒｉｇｉｎａｌ＿ｌｅｎｇｔｈは、重ねられる参照リング形状内の対応するエッジの長さである（図１７ａ参照）。そのほかの実施形態は、スレッショルドｌlongの計算にほかの方法を使用することができる。システムは、その後、再び衝突についてエッジをチェックする。衝突が検出された場合には、１つ又は複数のオブジェクトが、ｅtar、ｓ０、及びｓ１によって構成される三角形内に存在しなければならないため、この実施形態はエッジを構成する（図１７ｆ参照）。
【００５７】
緩和
実施形態は、ターゲット近隣ともっとも類似する形状を有する近隣を伴う参照要素を配置する。しかしながら、システムが常に、誤差の値をゼロにする「ちょうどフィッティング」する要素を見つけ出すことができるとは限らないため、各局所的成長プロセスにおいて誤差が蓄積されることがある。１つの実施形態は、以前に合成された要素のポジションを修正して合成後のパターンの局所的特徴を、可能な限り参照のそれと類似に維持するように緩和プロセスを用意する。１つの実施形態においては、各合成後の要素について、システムが、各合成後の要素のリング形状を、対応する参照要素のそれに対して調整する。注意を要するが、各合成後の要素は、局所的成長プロセスにおいてマッチングされた対応する要素を持つことができる。
【００５８】
図１８ａ〜１８ｃは、１つの実施形態に従った緩和プロセスを示している。各頂点（図１８ａ）の直近の形状が望ましい形状にフィッティングられる（図１８ｂ）。各頂点とそれの望ましいポジションの間におけるギャップが最小化される（図１８ｃ）。
【００５９】
図１８ａ〜１８ｃを参照し、ｘiを合成後の要素ｅrefiのポジション、ｗ（ｘi）をその近隣のポジションのセットとする。対応する参照リング形状の相対的ポジションは、ｒijとすることができ、そのｒijはｘij∈ｗ（ｘi）に対応する（図１８ａ及び１８ｂ参照）。１つの実施形態は、各近隣のポジションｘjと対応する参照リング形状のポジションの間における距離が最小化される（図１８ｃ参照）。
【００６０】
【数５】
2009059368.tif 000007
【００６１】
この表現が平行移動不変量であることから、１つの実施形態は、一意的なミニマイザを有するために１つの要素のポジションをあらかじめ決定する。１つの実施形態においては、初期要素を初期ポジションに保持する。ユーザ指定の境界が存在する場合に１つの実施形態は、要素を、それらの生成されたポジションに拘束する。
【００６２】
【数６】
2009059368.tif 000008
【００６３】
線形拘束を伴う二次最小化問題は、たとえば閉じた形式により解くことができる。１つの実施形態は、ラグランジェの乗数法が適用される。ほかの実施形態は、ほかの方法を使用できる。注意を要するが、成長の間にエッジを失うか又は追加のエッジを獲得する要素が存在する。それらの要素は、すでに対応する参照要素と同じトポロジを持たない。またすべてのシードが、まだ対応する参照要素を有していないこともある。それらのオブジェクトのために、１つの実施形態は、それらの現在の近隣形状をターゲット・リング形状として使用する。ほかの実施形態は、ターゲット・リング形状の決定にほかの方法を使用できる。
【００６４】
図１９ａ〜１９ｆは、１つの実施形態に従った参照配置及び構成された連結及び合成された配置又はパターンを示している。図１９ａ〜１９ｆは、３つの異なるクラス、すなわち規則的パターン（図１９ａ）、規則的に近いパターン（図１９ｃ）、及び不規則一様分布（図１９ｆ）における参照配置を用いて合成されたパターンを示す。図１９ａは、２つの異なる三角形のシェードと２つの異なる矩形のシェードが配置された規則的な参照配置を示しており、図１９ｂは、図１９ａの参照配置から合成されたパターンを示している。図１９ｃは、長短のブロックが配置された規則的に近い参照配置を示しており、図１９ｄは、図１９ｃの参照配置から合成されたパターンを示している。わずかなランダム性が、スケール回転及び各記号の色に導入されている。図１９ｅは、不規則一様分布を伴う参照配置を示している。図１９ｆは、図１９ｅの参照配置から合成されたパターンを示している。水滴を表すスケッチのストロークが、不規則な分布で配置されている。システムが、局所的空間的関係及び近隣間のトポロジの維持を試みることから、これら３つのクラスを同一フレームワーク内でカバーすることが可能である。
【００６５】
図２０ａ〜２０ｃ及び図２１ａ〜２１ｄは、１つの実施形態に従った回転モードの効果を示している。システムは、図２０ａに示されている同一の参照配置を採用し、非回転モード（図２０ｂ）と回転モード（図２０ｃ）において異なる結果を生成する。これらの例においては、より高い優先度がグレイの石に割り当てられている。両方のケースともに、２つのグレイの石が互いに近づいて現れている。それぞれの２つの石の向きが非回転モードにおいては保持されているが、回転モードにおいては局所的に回転させられている。図２１ａ〜２１ｄは、１つの実施形態に従ったフロー・フィールド・モードを示している。ユーザは、基礎をなすフロー・フィールドの指定によって配置パターンをコントロールすることも可能である。フロー・フィールド・モードにおいては、システムがユーザ指定の参照（図２１ａ）及びフロー・フィールド（図２１ｂ）を採用し、当該フロー・フィールドに沿ってパターンを合成する（図２１ｃ）。１つの実施形態においては、ユーザがフロー・フィールド・ツールの使用によってストローク（図２１ｂの曲線）を描くとき、システムが、図２１ｂに示されているとおり、当該ストロークに沿って、フロー・フィールドを生成する。その後システムは、当該フロー・フィールドをはじめ図２１ａの参照配置を採用して、図２１ｃに示されているとおり、鱗がフローに沿って整列される新しいパターンを合成する。１つの実施形態においては、システムが、一様な分布を維持するようにトポロジを変更できる。図２１ｃ内の円は、局所的なトポロジが変化しているポジションを強調している。図２１ｄは結果としてもたらされる連結性を示す。
【００６６】
ユーザ・インターフェース
直観的な合成プロセスを提供するように、及びクリエイティブなデザイン・プロセスをサポートするように、実施形態は、結果としてもたらされるパターンの全体的な特徴をユーザ入力／コントロールに応答してコントロールするための１つ又は複数のタイプのインタラクション・ツールを、ユーザ・インターフェースを介して提供できる。このツールは、限定はされないが、次のうちの１つ又は複数を含むことができる。
・  ペインティング・ツール、たとえばカーソル・エリア下のシードをアクティブ化するスプレー・ツール。このツールは、ユーザが配置パターンをペイントすることを可能にする。実施形態は、充分に速く、迅速なフィードバックを返す。「スプレー・ツール」は、例のためにここで言及されており、限定は意図されず、カーソル又はそのほかのユーザによってコントロールされるユーザ・インターフェース要素の下のシードをアクティブ化するか、又は類似の「ペインティング・ツール」機能を実行するブラシ又はバケツ・ツールといったこのほかのタイプのペインティング・ツールも実施形態の中に設けられる。
・  ユーザがストロークのセットを描くことによってフロー・フィールドをデザインすることを可能にするフロー・フィールド・ツール。システムは、入力されたストロークの方向を制約条件として使用し、２Ｄ空間を、たとえばラジアル・ベース関数を使用して補間できる。
・  局所的成長を停止させる境界ストロークのセットをユーザが描くことを可能にする境界ツール。
【００６７】
図２２ａ〜２２ｂ、図２３ａ〜２３ｂ、図２４ａ〜２４ｂは、実施形態に従い、種々のユーザ・インターフェース・ツールを使用して作り出された例示的な結果を示している。１つの実施形態は、結果が図２２ｂに示されている基礎をなすフロー・フィールドを指定するためのフロー・フィールド・ツールを設ける。フロー・フィールド・ツールは、ユーザがストロークのセットを描くことによってフロー・フィールドをデザインすることを可能にする。システムは、入力されたストロークの方向を制約条件として使用し、２Ｄ空間を補間する。図２２ｂにおいては、図２２ａ内に示されている参照配置から合成された羽根の向きがフロー・フィールド・ツールを使用してコントロールされており、また成長エリアがスプレー・ツールを使用してコントロールされている。図２２ｂ内の矢印を伴う線は、所望のフロー・フィールドを指定するユーザ入力を表す。
【００６８】
１つの実施形態は、図２３ｂに示されているとおり、成長を制限する境界ツールを設ける。境界ツールは、局所的成長を停止させる境界ストロークのセットをユーザが描くことを可能にする。図２３ｂにおいては、図２３ａ内に示されている参照配置から合成されるブロックの成長エリアが、境界ツールによって制限されている。図２３ｂ内の実線は、所望の境界を指定するユーザ入力を表す。
【００６９】
１つの実施形態は、ペインティング・ツール、たとえば結果が図２４ｂに示されている成長エリアを指定するためのスプレー・ツールを設けている。１つの実施形態においては、スプレー・ツールが、カーソル・エリアの下のシードをアクティブ化する。このツールは、ユーザが配置パターンによってペイントすることを可能にする。スプレー・ツールの実施形態は、直ちにフィードバックを返すことができる。図２４ｂにおいては、たとえばスプレー・ツールを使用し、図２４ａ内に示されている参照又は配置パターンから合成される鱗を用いて４つの文字「Ｅｕｒｏ」がペイントされる。基礎をなすフロー・フィールドは、フロー・フィールド・ツールを使用して指定され、成長エリアは、スプレー・ツールを使用して指定できる。
【００７０】
図２２ｂ及び２４ｂに示されている例において、丸められた形状を有し、かつわずかに傾斜された３次元（３Ｄ）オブジェクトが実施形態によって配置されているため、結果が重なり効果を自然に表現している。これらの例示的な図に示されている効果は、要素のレンダリング順序の明示的な指定が要求されることから２Ｄベクトル・ベースのアプローチを用いて作り出すことが困難である。いくつかの実施形態は、合成プロセスにおいて、たとえば局所的エリア内への集中における誤りを回避する補助、及び滑らかな結果を獲得する補助ができる分布の全体的形状を最適化することができる。また実施形態は、配置を獲得した後に各要素の局所的な向き又はサイズを修正する能力も有する。このタイプのコントロールは、ピクセル・ベースのテクスチャ合成にとって困難である。
【００７１】
図２５は、１つの実施形態に従った見本ベースの手続き的パターン合成モジュールを示している。実施形態においては、見本から要素配置を合成するための方法及び装置が、ここで述べられているとおり、モジュール３００として、又は図２５に示されているとおりにその中に実装される。見本ベースの手続き的パターン合成モジュール３００は、スタンドアロン・アプリケーション内で、又はグラフィック・アプリケーション又はそのほかのグラフィック・ツールを設けたグラフィック・ライブラリのモジュールとして実装される。モジュール３００の実施形態が実装できるグラフィック・アプリケーションの例は、限定はされないが、ペインティング、出版、写真、ゲーム、アニメーション、及び／又はそのほかのアプリケーションを含む。モジュール３００は、画像、ビデオ、及び／又はそのほかのグラフィック出力の表示、レンダリング、製作、及び／又はストアに使用できる。
【００７２】
モジュール３００は、境界ツール３０４、フロー・フィールド・ツール３０６、及びペインティング・ツール３０８等の１つ又は複数のツールを含むユーザ・インターフェース３０２を設けている。モジュール３００は、１つ又は複数のパターン３１０（参照配置）を獲得し、かつ当該パターン（１つ又は複数）３１０から、ユーザ・インターフェース３０２を介して受信されるユーザ入力３１２に従って１つ又は複数のディジタル画像３２０内に１つ又は複数の要素配置３２２を生成する。モジュール３００は、ここに述べられているとおり、入力されたパターン（１つ又は複数）３１０からの要素配置３２２の生成において、参照配置と呼ぶことができる見本とターゲットの局所的近隣比較に基づくテクスチャ合成テクニックと、局所的成長に基づく手続き的モデリングとを結合できる。
【００７３】
要素配置のための見本ベースの手続き的方法及び装置の実施形態を説明してきた。実施形態は、見本（参照配置）とターゲットの局所的近隣比較に基づくテクスチャ合成テクニックと、局所的成長に基づく手続き的モデリングとを結合できる。見本ベースの手続き的方法及び装置においてユーザは、要素配置を合成する難しいスクリプトを記述することによって規則を定義する必要がない。実施形態は、ユーザ・インターフェースを介したユーザ・コントロールを用いて、見本から要素配置を合成するためのコントロール可能な合成フレームワークを設けている。ユーザは、ユーザ・インターフェースを介してイネーブルされるプロセスに設けられた１つ又は複数のツールを介して合成プロセスをインタラクティブに、かつ動的にコントロールできる。
【００７４】
例示的なシステム
見本から要素配置を合成するための方法及び装置の実施形態の多様なコンポーネントは、ほかの多様なデバイスとインタラクションできる１つ又は複数のコンピュータ・システム上において実行できる。１つのその種のコンピュータ・システムが図２６によって示されている。示されている実施形態においては、コンピュータ・システム７００が、入力／出力（Ｉ／Ｏ）インターフェース７３０を介してシステム・メモリ７２０に結合される１つ又は複数のプロセッサ７１０を含む。さらにコンピュータ・システム７００は、ネットワーク・インターフェース７４０、及びカーソル・コントロール・デバイス７６０、キーボード７７０、オーディオ・デバイス７９０、及びディスプレイ（１つ又は複数）７８０等といったＩ／Ｏインターフェース７３０に結合された１つ又は複数の入力／出力デバイス７５０も含む。いくつかの実施形態においては、コンピュータ・システム７００の単一インスタンスを使用して当該実施形態を実装できることが企図され、ほかの実施形態においては、複数のその種のシステム又はコンピュータ・システム７００を構成する複数のノードを、実施形態の異なる部分又はインスタンスをホストするように構成できる。たとえば、１つの実施形態においては、いくつかの要素を、ほかの要素を実装するノードと明瞭に異なるコンピュータ・システム７００の１つ又は複数のノードを介して実装できる。
【００７５】
種々の実施形態においては、コンピュータ・システム７００を１つのプロセッサ７１０を含むユニプロセッサ・システムとするか、又はいくつかの（たとえば、２、４、８、又は別の適切な数の）プロセッサ７１０を含むマルチプロセッサ・システムとすることができる。プロセッサ７１０は、インストラクションを実行することが可能な任意の適切なプロセッサとすることができる。たとえば、種々の実施形態においてプロセッサ７１０を、ｘ８６、パワーＰＣ（ＰｏｗｅｒＰＣ）、スパーク（ＳＰＡＲＣ）、又はＭＩＰＳ  ＩＳＡ、又はそのほかの任意の適切なＩＳＡといった種々のインストラクション・セット・アーキテクチャ（ＩＳＡ）のいずれかを実装する汎用又は埋め込みプロセッサとすることができる。マルチプロセッサ・システムにおいては、プロセッサ７１０のそれぞれが、必然ではないが同一ＩＳＡを共通に実装できる。
【００７６】
システム・メモリ７２０は、プロセッサ７１０によってアクセス可能なプログラム・インストラクション及び／又はデータをストアするように構成できる。種々の実施形態においては、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、同期ダイナミックＲＡＭ（ＳＤＲＡＭ）、不揮発性／フラッシュ・タイプのメモリ、又は任意のそのほかのタイプのメモリ等、任意の適切なメモリ・テクノロジを使用してシステム・メモリ７２０を実装できる。示されている実施形態においては、見本から要素配置を合成するための方法及び装置について前述したような所望の機能を実施するプログラム・インストラクション及びデータが、それぞれプログラム・インストラクション７２５及びデータ・ストレージ７３５としてシステム・メモリ７２０内にストアされることが示されている。ほかの実施形態においては、システム・メモリ７２０又はコンピュータ・システム７００とは別の異なるタイプのコンピュータ‐アクセス可能メディア又は類似のメディア上にストアされるか、又は送信されるプログラム・インストラクション及び／又はデータを受信できる。概して言えば、コンピュータ‐アクセス可能メディアは、Ｉ／Ｏインターフェース７３０を介してコンピュータ・システム７００に結合される磁気又は光メディア、たとえばディスク又はＣＤ／ＤＶＤ‐ＲＯＭ等のストレージ・メディア又はメモリ・メディアを含むことができる。コンピュータ‐アクセス可能メディアを介してストアされるプログラム・インストラクション及びデータは、ネットワーク・インターフェース７４０を介して実装できるといった類のネットワーク及び／又は無線リンク等の通信メディアを介して伝達できる電気、電磁気、又はディジタル信号等の送信メディア又は信号によって送信される。
【００７７】
１つの実施形態においては、プロセッサ７１０、システム・メモリ７２０、及びネットワーク・インターフェース７４０又はそのほかの入力／出力デバイス７５０等の周辺インターフェースを含むデバイス内の任意の周辺デバイスの間におけるＩ／Ｏトラフィックを調和するようにＩ／Ｏインターフェース７３０が構成される。いくつかの実施形態においては、Ｉ／Ｏインターフェース７３０は、１つのコンポーネント（たとえば、システム・メモリ７２０）からのデータ信号を別のコンポーネント（たとえば、プロセッサ７１０）による使用に適したフォーマットに変換するための任意の必要なプロトコル、タイミング、又はそのほかのデータの変換を実行できる。いくつかの実施形態においては、Ｉ／Ｏインターフェース７３０が、たとえば各種のペリフェラル・コンポーネント・インターコネクト（ＰＣＩ）バス標準又はユニバーサル・シリアル・バス（ＵＳＢ）標準等の種々のタイプの周辺バスを通じて取り付けられるデバイスのためのサポートを含む。いくつかの実施形態においては、Ｉ／Ｏインターフェース７３０の機能を、２又はそれより多くの別々のコンポーネント、たとえばノース・ブリッジ及びサウス・ブリッジ等に分割できる。加えて、いくつかの実施形態においては、システム・メモリ７２０に対するインターフェース等のＩ／Ｏインターフェース７３０の機能の一部又は全部を、プロセッサ７１０内に直接組み込むことができる。
【００７８】
ネットワーク・インターフェース７４０は、コンピュータ・システム７００と、ネットワークに取り付けられたほかのデバイス、たとえばほかのコンピュータ・システムの間、又はコンピュータ・システム７００のノード間におけるデータの交換を可能にするように構成される。種々の実施形態においては、ネットワーク・インターフェース７４０が、任意の適切なタイプの、たとえばイーサネット（登録商標）・ネットワーク等の有線又は無線の汎用データ・ネットワーク経由、アナログ音声ネットワーク又はディジタル・ファイバ通信ネットワーク等のテレコミュニケーション／電話網経由、ファイバ・チャンネルＳＡＮ等のストレージ・エリア・ネットワーク経由、又はそのほかの任意の適切なタイプのネットワーク及び／又はプロトコル経由の通信をサポートしている。
【００７９】
入力／出力デバイス７５０は、いくつかの実施形態において、１つ又は複数のディスプレイ端末、キーボード、キーパッド、タッチパッド、スキャニング・デバイス、音声又は光学認識デバイス、又は任意のそのほかの、１つ又は複数のコンピュータ・システム７００によるデータの入力又は取り出しに適したデバイスを含むことができる。複数の入力／出力デバイス７５０をコンピュータ・システム７００内に存在させることができるか、又はコンピュータ・システム７００の種々のノード上に分散させることができる。いくつかの実施形態においては、類似する入力／出力デバイスがコンピュータ・システム７００から分離でき、かつネットワーク・インターフェース７４０を介して等の有線又は無線接続を通じてコンピュータ・システム７００の１つ又は複数のノードとインタラクションできる。
【００８０】
図２６に示されているとおり、メモリ７２０は、ここで述べられているとおりの見本から要素配置を合成するための方法及び装置の実施形態を実施するように構成されたプログラム・インストラクション７２５、及びプログラム・インストラクション７２５によってアクセス可能な種々のデータを包含するデータ・ストレージ７３５を含む。１つの実施形態においては、プログラム・インストラクション７２５が、前述の図１ａ〜２５内に示されているとおりの見本から要素配置を合成するための方法及び装置のソフトウエア要素を含む。データ・ストレージ７３５は、実施形態内において使用できるデータを含む。ほかの実施形態においては、このほかの、又は異なるソフトウエア要素及びデータを含むことができる。
【００８１】
プログラム・インストラクション７２５は、種々の実施形態において、見本から要素配置を合成するための方法及び装置を、スタンドアロン・アプリケーションとして、又は別のグラフィック・アプリケーション又はグラフィック・ライブラリのモジュールとして実装するように構成できる。たとえば１つの実施形態においては、プログラム・インストラクション７２５を、ペインティング、出版、写真、ゲーム、アニメーション、及び／又はそのほかのアプリケーション等の１つ又は複数のグラフィック・アプリケーションを実装するように構成し、またそれらのグラフィック・アプリケーションのうちの１つ又は複数の部品として、ここに述べられているとおりに見本から要素配置を合成するように構成してもよい。別の実施形態では、プロセッサ（１つ又は複数）７１０上で、又はネットワーク・インターフェース７４０を介し、何らかのほかのデバイス又はシステム上で実行されている別のグラフィック・アプリケーションによる１つ又は複数の関数呼び出しにおいて、ここに述べられているとおりの見本から要素配置を合成するための方法及び装置を実装するようにプログラム・インストラクション７２５を構成する。またプログラム・インストラクション７２５を、種々の実施形態において、画像のレンダリングを行い、それを１つ又は複数のディスプレイ７８０上に、見本から要素配置を合成するための方法及び装置の出力として呈示するか、かつ／又はレンダリング後の画像データをメモリ７２０内にストアするように構成することもできる。
【００８２】
当業者は認識することになろうが、コンピュータ・システム７００は、単なる例示であって、ここで述べられているとおりの見本から要素配置を合成するための方法及び装置の範囲を限定することが意図されていない。詳細に述べれば、コンピュータ・システム及びデバイスは、コンピュータ、ネットワーク・デバイス、インターネット・アプライアンス、ＰＤＡ、無線電話、ページャ等を含む、望ましい機能の実行が可能なハードウエア又はソフトウエアの任意の組み合わせを含むことができる。またコンピュータ・システム７００は、示されていないこのほかのデバイスに接続できるか、又はそれに代えて、スタンドアロン・システムとして動作できる。加えて、いくつかの実施形態においては、示されているコンポーネントによって提供される機能を、より少ないコンポーネント内において結合すること、又は追加のコンポーネント内に分散させることができる。同様に、いくつかの実施形態においては、示されているコンポーネントのいくつかの機能を設けなくてもよく、かつ／又はそのほかの追加の機能を利用可能にできる。
【００８３】
これもまた当業者は認識することになろうが、使用の間にメモリ内又はストレージ上にストアされるとして種々のアイテムが示されているが、これらのアイテム又はそれらの一部は、メモリ・マネジメントやデータ保全の目的のためにメモリ及びそのほかのストレージ・デバイスの間で転送される。それに代えて、ほかの実施形態においては、ソフトウエア・コンポーネントの一部又は全部を別のデバイス上のメモリ内で実行し、示されているコンピュータ・システムに、コンピュータ間通信を介して伝達することができる。システムコンポーネント又はデータ構造の一部又は全部もまた、種々の例が上で述べられているコンピュータ‐アクセス可能メディア又は適切なドライブによって読み出されるポータブル物品上にストア（たとえば、インストラクション又は構造化されたデータとして）される。いくつかの実施形態においては、コンピュータ・システム７００とは別のコンピュータ‐アクセス可能メディア上にストアされたインストラクションを、ネットワーク及び／又は無線リンク等の通信メディアを介して伝達される電気、電磁気、又はディジタル信号等の送信メディア又は信号を介してコンピュータ・システム７００に送信することができる。多様な実施形態は、さらに、コンピュータ‐アクセス可能メディア上において以上の記述に従って実施されるインストラクション及び／又はデータの受信、送信、又はストアを含む。したがって、本発明は、このほかのコンピュータ・システム構成を用いても実施できる。
【００８４】
結論
種々の実施形態は、さらに、コンピュータ‐アクセス可能メディア上において以上の記述に従って実装されるインストラクション及び／又はデータの受信、送信、又はストアを含む。概して言えば、コンピュータ‐アクセス可能メディアは、磁気又は光メディア等、たとえばディスク又はＤＶＤ／ＣＤ‐ＲＯＭ、揮発性又は不揮発性メディア、たとえばＲＡＭ（たとえば、ＳＤＲＡＭ、ＤＤＲ、ＲＤＲＡＭ、ＳＲＡＭ等）、ＲＯＭ等のストレージ・メディア又はメモリ・メディアをはじめ、ネットワーク及び／又は無線リンク等の通信メディアを介して伝達される電気、電磁気、又はディジタル信号等の送信メディア又は信号を含むことができる。
【００８５】
図面内に示され、ここで説明されているとおりの種々の方法は、方法の例示的な実施形態を表す。それらの方法は、ソフトウエア、ハードウエア、又はこれらの組み合わせにおいて実施できる。方法の順序は変更でき、種々の要素の追加、再順序設定、結合、スリップ、修正等を行うことができる。
【００８６】
この開示の恩典を受ける当業者には自明となるとおり、種々の修正及び変更を行うことができる。本発明がすべてのその種の修正及び変更を囲い込むことが意図されており、したがって上記の説明は限定の意味ではなく例示と考えられるべきとする。
【図面の簡単な説明】
【００８７】
【図１】１つの実施形態に従った見本からのパターンの合成を示した説明図である。
【図２】１つの実施形態に従った例示的な参照配置内の要素のための例示的な記号ＩＤ及びサブＩＤを示した説明図である。
【図３】１つの実施形態に従った例示的な分析及び合成段階を示した説明図である。
【図４】１つの実施形態に従って見本から要素配置を合成するための方法を示したフローチャートである。
【図５】１つの実施形態に従った、単一の繰り返しステップの例を示して例示的な局所的成長プロセスを示した説明図である。
【図６】１つの実施形態に従った、与えられた参照配置のための連結性の生成を示した説明図である。
【図７】１つの実施形態に従った参照配置及び要素間の連結性の例を示した説明図である。
【図８】１つの実施形態に従った参照配置及び要素間の連結性の例を示した説明図である。
【図９】１つの実施形態に従った、ユーザにより案内される連結性の訂正を示した説明図である。
【図１０】１つの実施形態に従ったシーディングを示した説明図である。
【図１１】１つの実施形態に従ったシードの併合の例を示した説明図である。
【図１２】１つの実施形態に従ったシードの併合の例を示した説明図である。
【図１３】１つの実施形態に従った衝突の取り扱いを示した説明図である。
【図１４】１つの実施形態に従ったリング・エッジの生成を示した説明図である。
【図１５】１つの実施形態に従ったパターンのマッチングの例を示した説明図である。
【図１６】１つの実施形態に従った、参照配置からの要素をターゲット・シードにフィッティングるプロセスにおける種々のモードの結果を示した説明図である。
【図１７】１つの実施形態に従って望ましくない構造を回避するために使用できるヒューリスティック・アプローチを示した説明図である。
【図１８】１つの実施形態に従った緩和プロセスを示した説明図である。
【図１９】１つの実施形態に従った参照配置及び構成された連結及び合成された配置又はパターンを示した説明図である。
【図２０】１つの実施形態に従った回転モードの効果を示した説明図である。
【図２１】１つの実施形態に従った種々の回転モードの効果を示した説明図である。
【図２２】１つの実施形態に従ったフロー・フィールド・ユーザ・インターフェース・ツールを使用して作り出された例示的な結果を示した説明図である。
【図２３】１つの実施形態に従った境界ユーザ・インターフェース・ツールを使用して作り出された例示的な結果を示した説明図である。
【図２４】１つの実施形態に従ったスプレー・ツール等のペインティング・ユーザ・インターフェース・ツールを使用して作り出された例示的な結果を示した説明図である。
【図２５】１つの実施形態に従った見本ベースの手続き的パターン合成モジュールを示した説明図である。
【図２６】実施形態内において使用できる例示的なコンピュータ・システムを示した説明図である。
【符号の説明】
【００８８】
１００  シード；ターゲット・シード
１０２  参照要素
１１０  ターゲット・シード
１１２  参照要素
３００  モジュール；見本ベースの手続き的パターン合成モジュール
３０２  ユーザ・インターフェース
３０４  境界ツール
３０６  フロー・フィールド・ツール
３０８  ペインティング・ツール
３１０  パターン
３１２  ユーザ入力
３２０  ディジタル画像
３２２  要素配置
【図１】
2009059368.tif 000009
【図２】
2009059368.tif 000010
【図３】
2009059368.tif 000011
【図４】
2009059368.tif 000012
【図５】
2009059368.tif 000013
【図６】
2009059368.tif 000014
【図７】
2009059368.tif 000015
【図８】
2009059368.tif 000016
【図９】
2009059368.tif 000017
【図１０】
2009059368.tif 000018
【図１１】
2009059368.tif 000019
【図１２】
2009059368.tif 000020
【図１３】
2009059368.tif 000021
【図１４】
2009059368.tif 000022
【図１５】
2009059368.tif 000023
【図１６】
2009059368.tif 000024
【図１７】
2009059368.tif 000025
【図１８】
2009059368.tif 000026
【図１９】
2009059368.tif 000027
【図２０】
2009059368.tif 000028
【図２１】
2009059368.tif 000029
【図２２】
2009059368.tif 000030
【図２３】
2009059368.tif 000031
【図２４】
2009059368.tif 000032
【図２５】
2009059368.tif 000033
【図２６】
2009059368.tif 000034