(57)【要約】      （修正有）【課題】並列実行のための塗りつぶし方法を提供する。【解決手段】塗りつぶしターゲット色で置き換えられる塗りつぶしソース色を有する第１の要素と、塗りつぶしソース色を有さない第２の要素を含む画像を受け取るステップと、階層内の複数のレベルでセルを形成するために、階層的空間分割方式により画像を分割するステップと、第２の要素によって各セルの占有を検出するステップと、第２の要素による占有を有さない任意のセルについて、そのセルの子セルの深度の標高値をそのセルの値よりも１大きく設定し、塗りつぶしはセルの深度の標高分だけルートセルに向かってレベルをナビゲートし、第２の要素のないノードのみを占有し、それによって塗りつぶし可能な最大の親セルに到達することを示すステップと、第２の要素による占有を有さないセルの塗りつぶしソース色を塗りつぶしターゲット色で塗りつぶし、それによって受け取った画像を修正するステップを含む。【選択図】図１５
2020015314.tif 000002
【特許請求の範囲】
【請求項１】
並列実行のための塗りつぶし方法であって、
塗りつぶしターゲット色で置き換えられる塗りつぶしソース色を有する第１の要素と、前記塗りつぶしソース色を有さない第２の要素と、を含む画像を受け取るステップと、
階層内の複数のレベルでセルを形成するために、階層的空間分割方式により前記画像を分割するステップと、
第２の要素によって各セルの占有を検出するステップと、
第２の要素による占有を有さない任意のセルについて、そのセルの子セルの深度の標高値をそのセルの前記値よりも１大きく設定し、前記塗りつぶしは、セルの前記深度の標高分だけルートセルに向かってレベルをナビゲートし、第２の要素のないノードのみを占有し、それによって塗りつぶし可能な最大の親セルに到達することを示すステップと、
第２の要素による占有を有さないセルの前記塗りつぶしソース色を、前記塗りつぶしターゲット色で塗りつぶし、それによって前記受け取った画像を修正するステップと、
を含む方法。
【請求項２】
前記画像は２次元であり、前記階層的空間分割方式は四分木であり、前記セルは直線的である、請求項１に記載の方法。
【請求項３】
前記画像は体積であり、前記階層的空間分割方式は八分木であり、前記セルは立方体である、請求項１に記載の方法。
【請求項４】
セルを処理する場合に、セルが入力された少なくとも１つの側面が格納され、処理のための追加のセルが、前記セルが入力された前記格納された側面上の前記セル以外の隣接セルとして識別される、請求項１から３のいずれか一項に記載の方法。
【請求項５】
セルを処理する場合に、前記セルが入力された少なくとも１つの側面が格納され、前記格納された少なくとも１つの側面に隣接する前記子セルについて作業項目が生成される、請求項１から４のいずれか一項に記載の方法。
【請求項６】
複数のセルの各々に対して作業項目が生成され、２つ以上のそれぞれの作業項目が並行して処理される、請求項１から５のいずれか一項に記載の方法。
【請求項７】
前記２つ以上のそれぞれの作業項目は、グラフィック処理装置によって処理される、請求項６に記載の方法。
【請求項８】
塗りつぶしターゲット色で置き換えられた前記画像要素は塗りつぶしマスクを表す、請求項１から７のいずれか一項に記載の方法。
【請求項９】
前記塗りつぶしマスクの外側の画像領域は閉領域として定義される、請求項８に記載の方法。
【請求項１０】
２つの閉領域間の距離に対して距離に基づくメトリックが決定され、前記メトリックが所定のしきい値よりも小さい場合には、前記２つの領域の少なくとも一方は、
ｉ．前記２つの領域が交差するまで、前記２つの領域の少なくとも一方を移動させることと、
ｉｉ．前記２つの領域が交差するまで、前記２つの領域の少なくとも一方の少なくとも一部のサイズを大きくすることと、
からなるリストにおける１つまたは複数の修正によって修正される、請求項９に記載の方法。
【請求項１１】
前記２つの領域の少なくとも一方が修正された場合には、前記塗りつぶしアルゴリズムが繰り返される、請求項１０に記載の方法。
【請求項１２】
前記画像は、３Ｄ印刷されるオブジェクトの一部または全部を表す、請求項９から１１のいずれか一項に記載の方法。
【請求項１３】
前記塗りつぶしターゲット色を有する１つまたは複数の要素で形成された穴を、閉領域として識別された前記画像の領域に追加することによって前記画像を修正するステップを含む、請求項１２記載の方法。
【請求項１４】
前記塗りつぶされた画像に応じて３Ｄ印刷命令を生成するステップと、
３Ｄプリンタ用の前記３Ｄ印刷命令を出力するステップと、
を含む、請求項１２または１３に記載の方法。
【請求項１５】
コンピュータによって実行されると、請求項１から１４のいずれか一項に記載の方法を実行するプログラム命令を含むコンピュータプログラム製品。
【請求項１６】
塗りつぶしプロセッサであって、動作時に、
塗りつぶしターゲット色で置き換えられる塗りつぶしソース色を有する第１の要素と、前記塗りつぶしソース色を有さない第２の要素と、を含む画像を受け取り、
階層内の複数のレベルでセルを形成するために、階層的空間分割方式により前記画像を分割し、
第２の要素によって各セルの占有を検出し、
第２の要素による占有を有さない任意のセルについて、そのセルの子セルの深度の標高値をそのセルの前記値よりも１大きく設定し、前記塗りつぶしは、前記深度の標高分だけルートセルに向かってレベルをナビゲートし、第２の要素のないノードのみを占有し、それによって塗りつぶし可能な最大の親セルに到達することを示し、
第２の要素による占有を有さないセルの前記塗りつぶしソース色を、前記塗りつぶしターゲット色で塗りつぶし、それによって前記受け取った画像を修正する、
ように適合された塗りつぶしプロセッサを含む娯楽装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、塗りつぶしの並列方法および対応する装置に関する。
【背景技術】
【０００２】
３Ｄ印刷は、２次元ピクセルを平面上に堆積させるのではなく、プリンタが体積内に３次元ボクセルを堆積させる体積印刷の手段である。これを達成するための技術は、構造を構築するためにインクリメントされる層の金属粉末などの材料を溶融して融着させるためのレーザーの使用、または冷却し硬化して３Ｄモデルを構築するプラスチックの液滴を堆積させるための高温印刷ヘッドの使用を含む。
【０００３】
そのような３Ｄモデルの設計は、通常、ユーザが仮想モデルの表面および体積を定義するコンピュータ支援設計プログラムで生成される。次に、３Ｄプリンタを使用して仮想モデルをレンダリングするために材料を融着または堆積する順序を指定するプログラムによって、描画リストが生成される。
【０００４】
この手法は、多くの審美的および機能的にユニークなオブジェクトの作成をもたらしたが、それらのいくつかは、従来のプロセスを使用して作るのが難しいものである。しかし、３Ｄプリンタの有用性はまだ十分に探究されていない。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、３Ｄプリンタの新しい用途を提供することを目的としている。
【課題を解決するための手段】
【０００６】
第１の態様では、並列実行のための塗りつぶし方法が請求項１に従って提供される。
【０００７】
別の態様では、娯楽装置が請求項１６に従って提供される。
【０００８】
本発明のさらなるそれぞれの態様および特徴は、添付の特許請求の範囲において定義されている。
【図面の簡単な説明】
【０００９】
次に、添付の図面を参照しながら、本発明の実施形態を例として説明する。
【図１】本発明の実施形態による娯楽装置の概略図である。
【図２Ａ】本発明の実施形態による３Ｄプリンタの側面図の概略図である。
【図２Ｂ】本発明の実施形態による３Ｄプリンタの平面図の概略図である。
【図３】本発明の実施形態によるビデオゲーム仮想環境の概略図である。
【図４】本発明の実施形態による３Ｄモデル空間への投影の概略図である。
【図５】本発明の実施形態による仮想写真測量プロセスのためのデフォルト仮想カメラ位置の概略図である。
【図６Ａ】デフォルト仮想カメラ位置からのレンダリングに基づいて仮想写真測量プロセスによって生成された３Ｄモデルを示す図である。
【図６Ｂ】デフォルト仮想カメラ位置からのレンダリングに基づいて仮想写真測量プロセスによって生成された３Ｄモデルを示す図である。
【図７】本発明の実施形態による３Ｄ印刷モデリングの方法の流れ図である。
【図８Ａ】本発明の実施形態によるターゲットオブジェクトの画像を示す図である。
【図８Ｂ】本発明の実施形態による、ターゲットオブジェクトの表面のボクセルモデルの画像を示す図である。
【図９】本発明の実施形態による３Ｄ印刷モデリングの方法の流れ図である。
【図１０Ａ】本発明の実施形態による３Ｄ印刷用の幾何学的形状を生成するプロセスを示す概略図である。
【図１０Ｂ】本発明の実施形態による３Ｄ印刷用の幾何学的形状を生成するプロセスを示す概略図である。
【図１０Ｃ】本発明の実施形態による３Ｄ印刷用の幾何学的形状を生成するプロセスを示す概略図である。
【図１０Ｄ】本発明の実施形態による３Ｄ印刷用の幾何学的形状を生成するプロセスを示す概略図である。
【図１０Ｅ】本発明の実施形態による３Ｄ印刷用の幾何学的形状を生成するプロセスを示す概略図である。
【図１１】本発明の実施形態による３Ｄ印刷可能なビデオゲームキャラクタの概略図である。
【図１２】本発明の実施形態による３Ｄ印刷可能なビデオゲームキャラクタの概略図である。
【図１３Ａ】従来の塗りつぶし作業を示す図である。
【図１３Ｂ】従来の塗りつぶし作業を示す図である。
【図１３Ｃ】従来の塗りつぶし作業を示す図である。
【図１４】本発明の実施形態により塗りつぶされる２Ｄ画像の概略図である。
【図１５】本発明の実施形態による、階層的空間分割方式のセル内の画像占有に基づく標高深度値の表現を示す図である。
【図１６】本発明の実施形態による、階層的空間分割方式のセル内の画像占有に基づく標高深度値の概略図である。
【図１７Ａ】本発明の実施形態による、階層的空間分割方式内の子セルへの再帰を示す図である。
【図１７Ｂ】本発明の実施形態による、階層的空間分割方式内の隣接セルへの移動を示す図である。
【図１８Ａ】不適切な塗りつぶし作業を示す図である。
【図１８Ｂ】不適切な塗りつぶし作業を示す図である。
【図１８Ｃ】不適切な塗りつぶし作業を示す図である。
【図１９Ａ】３Ｄ印刷用に組み立てられるオブジェクトの図である。
【図１９Ｂ】不適切な塗りつぶし作業を示す図である。
【図１９Ｃ】不適切な塗りつぶし作業を示す図である。
【図１９Ｄ】不適切な塗りつぶし作業を示す図である。
【図２０】本発明の実施形態による正しい塗りつぶし作業を示す図である。
【図２１】本発明の実施形態による画像に対する修正を示す図である。
【図２２】本発明の実施形態による並列実行のための塗りつぶし方法の流れ図である。
【発明を実施するための形態】
【００１０】
並列実行のための塗りつぶしシステムおよび方法が開示されている。以下の説明では、本発明の実施形態の完全な理解を提供するために、いくつかの特定の詳細が提示されている。しかしながら、これらの特定の詳細が本発明を実施するために使用される必要がないことは当業者には明らかであろう。逆に、当業者に知られている特定の詳細は、必要に応じて明確にする目的で省略されている。
【００１１】
本発明の一実施形態では、娯楽装置は３Ｄプリンタに動作可能に結合されている。本明細書で後述するように、娯楽装置は、動作中に、３Ｄプリンタによる複製のためのビデオゲームプレイのスナップショットを取り込むように構成される。
【００１２】
[娯楽装置]
適切な娯楽装置の例は、Ｓｏｎｙ（登録商標）ＰｌａｙＳｔａｔｉｏｎ  ４（登録商標）装置である。
【００１３】
図１は、Ｓｏｎｙ（登録商標）ＰｌａｙＳｔａｔｉｏｎ  ４（登録商標）娯楽装置の全体的なシステムアーキテクチャを概略的に示す。システムユニット１０には、システムユニットに接続可能な様々な周辺装置が設けられている。
【００１４】
システムユニット１０は、中央処理装置（ＣＰＵ）２０Ａおよびグラフィック処理装置（ＧＰＵ）２０Ｂを順に含む単一チップである加速処理装置（ＡＰＵ）２０を含む。ＧＰＵは、複数の作業成果物を並行して実行することができる。ＡＰＵ２０は、ランダムアクセスメモリ（ＲＡＭ）ユニット２２にアクセスする。
【００１５】
ＡＰＵ２０は、任意選択でＩ／Ｏブリッジ２４を介して、バス４０と通信し、Ｉ／Ｏブリッジ２４は、ＡＰＵ２０の別個の構成要素またはその一部であってもよい。
【００１６】
バス４０に接続されているのは、ハードディスクドライブ３７、および互換性のある光ディスク３６Ａ上のデータにアクセスするように動作可能なブルーレイ（登録商標）ドライブ３６などのデータ記憶構成要素である。さらに、ＲＡＭユニット２２はバス４０と通信することができる。
【００１７】
任意選択でバス４０には補助プロセッサ３８も接続されている。補助プロセッサ３８は、オペレーティングシステムを実行またはサポートするために提供されてもよい。
【００１８】
システムユニット１０は、オーディオ／ビジュアル入力ポート３１、イーサネット（登録商標）ポート３２、ブルートゥース（登録商標）無線リンク３３、Ｗｉ−Ｆｉ（登録商標）無線リンク３４、あるいは１つまたは複数のユニバーサルシリアルバス（ＵＳＢ）ポート３５を介して周辺装置と適宜通信する。オーディオおよびビデオは、ＨＤＭＩ（登録商標）ポートなどのＡＶ出力３９を介して出力されてもよい。
【００１９】
周辺装置は、ＰｌａｙＳｔａｔｉｏｎ  Ｅｙｅ（登録商標）またはＰＳカメラ（登録商標）などの単眼または立体ビデオカメラ４１、ＰｌａｙＳｔａｔｉｏｎ  Ｍｏｖｅ（登録商標）などのワンドスタイルのビデオゲームコントローラ４２およびＤｕａｌＳｈｏｃｋ  ４（登録商標）などの従来のハンドヘルドビデオゲームコントローラ４３、ＰｌａｙＳｔａｔｉｏｎ  Ｐｏｒｔａｂｌｅ（登録商標）およびＰｌａｙＳｔａｔｉｏｎ  Ｖｉｔａ（登録商標）などの携帯娯楽装置４４、キーボード４５および／またはマウス４６、例えばリモコンの形態のメディアコントローラ４７、ならびにヘッドセット４８を含んでもよい。電話もしくはタブレット、プリンタ、または３Ｄプリンタ（図示せず）などの他の周辺装置も同様に考慮することができる。
【００２０】
ＧＰＵ２０Ｂは、任意選択でＣＰＵ２０Ａと連携して、ＡＶ出力３９を介して出力するためのビデオ画像およびオーディオを生成する。任意選択で、オーディオは、オーディオプロセッサ（図示せず）と共に、または代わりにそれによって生成されてもよい。
【００２１】
ビデオおよび任意選択でオーディオはテレビ５１に提示されてもよい。テレビによってサポートされている場合、ビデオは立体的であってもよい。オーディオは、ステレオ、５．１サラウンドサウンドまたは７．１サラウンドサウンドなどのいくつかのフォーマットのうちの１つでホームシネマシステム５２に提示されてもよい。ビデオおよびオーディオも同様に、ユーザ６０が装着しているヘッドマウントディスプレイユニット５３に提示されてもよい。ヘッドマウントディスプレイユニットは、一体型ヘッドフォン、取り付け可能なヘッドフォン／イヤホンを有してもよく、またはユーザに供給される別個のオーディオに依存してもよい。
【００２２】
動作中、娯楽装置はデフォルトでＦｒｅｅＢＳＤ  ９．０の変種などのオペレーティングシステムになる。オペレーティングシステムは、ＣＰＵ２０Ａ、補助プロセッサ３８、またはこれら２つの組み合わせ上で動作することができる。オペレーティングシステムは、ＰｌａｙＳｔａｔｉｏｎ  Ｄｙｎａｍｉｃ  Ｍｅｎｕなどのグラフィカルユーザインターフェースをユーザに提供する。このメニューにより、ユーザはオペレーティングシステムの機能にアクセスし、ゲームや任意選択的に他のコンテンツを選択することができる。
【００２３】
[３Ｄプリンタ]
前述のように、娯楽装置は３Ｄプリンタに動作可能に結合されている。
【００２４】
当然のことながら、３Ｄ印刷のための多数の技術があり、それらは通常、モデルを作成するために層がどのように構築されるかによって区別される。１つの技術は選択的レーザー焼結（ＳＬＳ）として知られており、そこでは粉末の層がレーザーによって選択的に一緒に融着されて固体領域を作り出す。その後に、新しい粉末層が上に配置され、モデルを構築するためのプロセスが繰り返される。別の技術はステレオリソグラフィとして知られており、１つまたは複数のレーザーと組み合わせて光反応性液体を使用して、定義されたポイントで液体を硬化させ、それによってモデルを、やはり通常は層状に構築する。これらの技術は両方とも本発明の実施形態の範囲内で想定されているが、強力なレーザーとモデルの周囲に粉末または液体の形態の大量のマトリックス材料との両方を必要とするという欠点があり、家庭での使用には実用的ではない。その結果、好ましい技術は融着堆積モデリング（ＦＤＭ）である。この手法は、モデルの連続層上を移動するプリンタヘッド内のプラスチックを溶融し、インクジェットプリンタにより紙のシート上へインクの液滴を堆積させるのと同様の方法で、各層の選択的位置にプラスチックの液滴を堆積させる。これにより、モデルで使用されるレーザーまたは原材料の周囲のマトリックスが不要になる。したがって、理解する目的で、ＦＤＭ  ３Ｄプリンタを、図２Ａおよび図２Ｂを参照して本明細書で簡単に説明する。
【００２５】
図２Ａは単純なＦＤＭ  ３Ｄプリンタ１００の側面図を示し、図２Ｂは同じＦＤＭ  ３Ｄプリンタの平面図を示す。プリンタ１００は、印刷モデルを組み立てるための作業面を提供するベース構造１１０と、その上にプリンタフレーム１２０を昇降させることができる支持ストラット１０２と、を含む。
【００２６】
例示的な機構では、モータ１１２Ｙは、ねじ山を含む駆動バー１０４に結合されており、プリンタフレーム１２０は、ねじ穴と滑らかな穴とを有する結合部を含み、ねじ穴は駆動バーと係合し、滑らかな穴は支持ストラットの１つと係合する。プリンタドライバからの指示の下で、モータ１１２Ｙが駆動バーを時計回りまたは反時計回りに回転させると、プリンタフレームが駆動バーおよび支持ストラットを上下に動かし（すなわち、ｙ軸に沿って）、したがって、それに取り付けられたプリンタキャリッジ１３０を上下させる。
【００２７】
図２Ｂから分かるように、プリンタフレーム１２０は通常は４つの支持ストラット１０２に取り付けられている。任意選択で、第２のモータ、駆動バーおよび結合部をフレームの反対側の隅に設けて、フレームおよびモータにかかる歪みを低減することができる。
【００２８】
プリンタフレーム１２０は、プリンタキャリッジ１３０を支持する。モータ１１２Ｘは、固定手段１２４によってプリンタキャリッジ１３０に固定されている駆動バンド１２２に結合されている。プリンタドライバからの指示の下で、モータ１１２Ｘが駆動バンドを時計回りまたは反時計回りに回転させると、プリンタキャリッジ１３０は、プリンタフレーム１２０に沿って（すなわち、ｘ軸に沿って）左右に移動し、したがって取り付けられたプリンタ機構１４０を横方向に移動させる。
【００２９】
プリンタキャリッジ１３０は、プリンタ機構１４０を支持する。モータ１１２Ｚは、固定手段１３４によってプリンタ機構１４０に固定されている駆動バンド１３２に結合されている。プリンタドライバからの指示の下で、モータ１１２Ｚが駆動バンドを時計方向または反時計方向に回転させると、プリンタ機構１４０は深度方向に（すなわちｚ軸に沿って）移動する。
【００３０】
プリンタ機構１４０自体は、機構（図示せず）に供給された１つまたは複数のプラスチック糸の端部を加熱するため、または機構（図示せず）上のホッパーから得られるプラスチック粉末の粒子を加熱するための加熱手段を含む。プラスチックの加熱、あるいは加熱されたプラスチックの放出は、プリンタドライバからの指示によって制御される。次いで、得られた溶融プラスチックのビードまたは液滴を、プリンタヘッドまたはノズル１４２を通して、必要に応じてプリンタの作業面１１０または部分的に構築されたモデル（図示せず）上に堆積させる。
【００３１】
このように、プリンタドライバからの適切な指示の下で、モータ１１２Ｘ、１１２Ｙ、１１２Ｚを使用してプリンタヘッドを３Ｄプリンタの作業体積内のどこにでも配置でき、その位置にプラスチックの液滴を堆積させることができ、次に冷却して硬化し、３Ｄモデルのボクセルを形成する。プリンタヘッドの連続的な移動およびプラスチック液滴の選択的な溶融または放出によって、このような複数のボクセルから、完成した３Ｄモデルを構築することができる。
【００３２】
通常、プリンタドライバ自体は、３Ｄモデルを記述するモデルの幾何学的形状を受け取るコンピュータ支援設計システム内のソフトウェアモジュールである。次に、プリンタドライバは、ｙ方向に各層について１ボクセル厚の３Ｄモデルの薄いスライスを生成し、その層内の各ボクセルについてｘ、ｚ座標を決定する。次に、プリンタドライバは、一連の命令をプリンタ１００に出力して、プリンタヘッド１４２を層ｙ内の各ボクセルについてそれぞれのｘ、ｚ座標に移動させる。そこで、プリンタ機構は、プラスチックの液滴を加熱および／または放出するように指示されて、その位置にボクセルを形成する。このようにして、デジタル３Ｄモデルは３Ｄプリンタによって物理モデルとして再構築される。
【００３３】
本発明の一実施形態では、プリンタドライバは、ビデオゲーム、または娯楽装置のオペレーティングシステム、またはビデオゲームまたはオペレーティングシステムのいずれかによって使用されるサポート機能のミドルウェアライブラリに組み込まれる。
【００３４】
［仮想環境］
ここで図３を参照すると、娯楽装置上で実行されるビデオゲームは、ユーザが視点の位置を変更したり、ゲームのエンティティや要素がスクリプト化されたアクティビティを実行したり、ユーザの行動に反応したり、あるいは両方が混在する場合、通常複数のエンティティまたは環境要素が動的に見られる仮想環境を含む。
【００３５】
図３には、ドア２１２を有する部屋２１０を含む単純な環境２００が示されており、一方の壁には、ろうそくホルダ２１４内にろうそくが取り付けられている。部屋の中にはプレイヤーのキャラクタ２２０がいる（ここでは架空のゲームキャラクタのブロブマンが描かれている）。
【００３６】
仮想環境は、幾何学的形状データから３Ｄで、通常はオブジェクトの表面を定義するポリゴンの形式で構築されている。これらのポリゴンは、例えば静的オブジェクトおよび背景風景の場合には予め定義されてもよく、あるいはプレイヤーのキャラクタなどの環境内の移動エンティティの場合にはワープ／再配置または手続き的に生成されてもよい。当然のことながら、本明細書における「ポリゴン」への言及は、ポリゴンが構築される頂点などの予備的な幾何学的特徴を包含し、これらはグラフィックスパイプラインにおいて使用される。同様に、ボクセルレンダリングは、オブジェクトを記述するために同等の幾何学的特徴を使用する。それ故、ポリゴンに適用するように記述されたプロセスは、必要に応じてそのような他の幾何学的特徴に全体的にまたは部分的に適用することができる。
【００３７】
仮想環境は、選択された視点からユーザに提示するために準備される。ユーザの視線を有する環境の要素は、それらが表すオブジェクトに適したテクスチャ情報でパターン化され、テクスチャ化された幾何学的形状は、仮想光源からの明るさの変化などの照明効果、ならびにテクスチャがそのような仮想光源と相互作用する方法をシミュレートするためのバンプマッピング（または変位マッピングや等値面の使用などの同様の手法）のためにさらに処理される。さらに、体積フォグや粒子効果などの他の効果を含めることができる。
【００３８】
次いで、最終的にレンダリングされた画像は、通常は２Ｄもしくは３Ｄテレビを介してまたはヘッドマウントディスプレイを介してユーザに提示される。
【００３９】
そのようなゲームの中ではしばしば、ユーザは彼らが友人および／またはより広い世界と共有したいという経験を有する。このため、前述のように、ＰｌａｙＳｔａｔｉｏｎ  ４（登録商標）などの娯楽装置のコントローラには「共有」ボタンがあり、ユーザに提示される画像の取り込みを容易にすることができ、その後に、ソーシャルメディアサイトなどの共有サイトにアップロードすることができる。
【００４０】
［画像のコレクションから環境の３Ｄモデルを印刷する］
本発明の一実施形態では、３Ｄ印刷モデルを作成するためのゲーム内の瞬間を選択するための選択肢がユーザに提供される。このようにして、ユーザは彼らのゲーム内経験の有形の記念品を作成することができる。
【００４１】
本発明の一実施形態では、娯楽装置が、ユーザが現在のシーンの３Ｄ印刷を作成したいことを示す入力を受け取ると、ゲーム状態は、３Ｄ印刷用に解析することができるようにフリーズ（例えば一時停止）される。
【００４２】
当然のことながら、ゲームにとって、多くの目に見える特徴は、ゲーム内の幾何学的形状またはモデル単独のテクスチャに固有のものではない。例えば、ゲーム内の幾何学的形状は、ポリゴンとスケルトンモデルを組み合わせたものであってもよく、フレームごとに加えられた配置や変形などの物理的効果を有してもよい。手続き的効果やパラメータ化されたモデルなどの他のレンダリング効果は、レンダリング中にシェーダにおいて実行することができる。一方、シェーダはバンプマップなどに従ってテクスチャを視覚的に処理することもできる。その結果、画面に表示するためにレンダリングされるときに、最終的なシーン（ユーザから見た場合）が１つの場所で１つのフォーマットでのみ結合されることがしばしばある。
【００４３】
したがって、本発明の一実施形態では、仮想環境の幾何学的形状の潜在的に異なる内部的なゲーム内表現に対して優先的にこれらのレンダリングされた画像を使用して、３Ｄ印刷用の３Ｄモデルが構築される。そのような技術を仮想写真測量と呼ぶことがある。しかしながら、単一のレンダリングされた画像は、通常、３Ｄ印刷用の仮想環境を完全にモデル化するのには不十分な情報を含むであろう。
【００４４】
本明細書で前述したように、通常のプレイ中に仮想環境は特定の視点に対してレンダリングされる。さらに、高いフレームレートおよび効率的な処理を可能にするために、このレンダリングプロセスの一部として、その特定の視点から見えない環境の要素がレンダリングプロセスの早い段階で間引かれる。
【００４５】
その結果、選択された視点から見える環境の要素だけが保存されレンダリングされる。このレンダリングを使用して環境の３Ｄプリンタモデルを生成すると、その特定の視点からは見えないモデルのすべての様相が失われるか、あるいは何らかの形の補間アルゴリズムを使用して塗りつぶす必要がある。実際の印刷モデルをその他の角度から見た場合、明らかにこれは満足のいく結果をもたらさないであろう。
【００４６】
したがって、本発明の一実施形態では、ゲーム状態がフリーズされている間に、娯楽装置は、異なる視点から仮想環境の複数のレンダリング画像を生成する。
【００４７】
好ましくは、少なくとも２つの対向する視点がレンダリングされ、第１の視点は通常は最初にユーザに表示されたものである。２つの画像の間では、これによって、元のレンダリングされたビューで間引きされた環境のすべての要素ではないにしても、ほとんどの要素がレンダリングされる。
【００４８】
任意選択的に３つの視点がレンダリングされ、好ましくは平面上に均等に分布され、第１の視点は最初にユーザに表示されたものであり、その平面はその第１の視点の視線方向を中心にして水平に置かれる。再び、これによって、元のレンダリングされたビューで間引きされた環境のすべての要素ではないにしても、ほとんどの要素がレンダリングされるが、その前後のオブジェクトによって遮られている可能性があるため、上記の２つの視点のいずれでもレンダリングされない環境の要素をより多く取り込む可能性がある。
【００４９】
より一般的には、平面上に分布する視点が多くなるほど、レンダリングされないまま残る環境の要素は少なくなる。例えば、娯楽装置は、環境内で「フライバイ」を行い、Ｎ枚の画像を取り込むことができ、ここでＮは、例えば、２〜３６０である。取り込まれた画像の数は、（本明細書で後述するように）最終モデルの忠実度と、取り込まれた画像を解析するのに必要な娯楽装置のメモリおよび処理能力と、の間のトレードオフである。
【００５０】
任意選択で、仮想環境の上から見下ろす１つまたは複数の視点を（個別の画像として、またはフライバイシーケンスの一部として）レンダリングして、いくつかの環境フィーチャの上面など、単一平面上の以前に取り込まれた視点と実質的に平行な環境の要素にさらなる詳細を提供することもできる。
【００５１】
本発明の一実施形態では、各画像の視点を表す仮想カメラの位置および観察方向に関するメタデータも記録され、それぞれの画像に関連付けられる。
【００５２】
当然のことながら、仮想環境は広い領域を表してもよいが、３Ｄモデルは特定の３Ｄプリンタによって生成することができるモデルのサイズと、環境が印刷されるスケールと、によって決定される限られた領域を含むであろう。特定の３Ｄプリンタの特性は、娯楽装置と通信している場合には既知であることが望ましい（そうでない場合は、デフォルトのモデルサイズを想定したり、ユーザがサイズを指定したりできる）。同様に、環境が印刷されるスケールは、ユーザによって選択されてもよいし、ユーザのアバターなど、環境内のキーキャラクタを参照して自動的に決定されてもよい。このアバターは、最終的な３Ｄプリンタモデル内の特定のサイズ（非限定的な例として、デフォルトで５ｃｍの高さ）になるように選択されてもよく、したがって、同じスケールで印刷される環境の範囲が計算されてもよい。あるいは、「キャラクタ印刷」モードでは、ゲーム内の環境機能を取り囲むことなく、ユーザのアバターなどの特定のキャラクタのみを印刷することができる。これは、ユーザが自分自身のゲーム内キャラクタをカスタマイズすることを許可され、それに感情的に付き合うようになる場合に特に価値があるかもしれない。
【００５３】
したがって、２つ以上の視点の等距離分布は、このキーキャラクタを中心とすることができ、任意選択でゲーム内カメラ制御ロジックを使用して、各取り込み画像内でキーキャラクタを中心に配置するために必要な視野方向を決定することができる。
【００５４】
ゲームが一人称視点を提示する場合、モデルのサイズおよび想定されたもしくはユーザ設定のスケールに基づいて、モデルの中心点を計算することができ、視点をその周囲に分布させることができる。
【００５５】
上記の手法を組み合わせると、娯楽装置は、所定の半径の球上の、その中心点を中心とするサンプル点を選択することによって画像を取り込むことができる。任意選択的に、環境バリアによって遮られたサンプルポイント（地面の下や山の中などの球体上のポイント）をスキップすることができ、あるいは環境バリアによって表面が遮られなくなるまで球体の半径を局所的に小さくすることができる。あるいは、３Ｄ印刷されるターゲットオブジェクトの一部ではない環境の要素は、遮られないビューを提供するためにレンダリングから省略されてもよい（より広い仮想環境からのターゲットオブジェクトの選択については後述する）。サンプリング方式では、最初に、元の視点と中心点を含み、元の視点の水平軸に平行な上記の平面上の視点を選択し、その後に、任意選択的に、この平面の上方の球で１つまたは複数の視点を選択し、任意選択的に、この平面の下方の球で１つまたは複数の視点を選択することができる。所定の半径は、元の取り込み画像との一貫性を維持するために、元の視点とモデルの決定された中心点との間の距離に等しくすることができる。あるいは、元の画像と後続の追加画像は、異なる有効半径、例えば、画像の視野が３Ｄ印刷モデルに含まれる地上領域を含む最小半径で再レンダリングされてもよい。注目すべきことに、伝統的に、ゲームはレンダリングプロセスを単純化するためにより長い描画距離でより忠実度の低いモデルを使用する。したがって、任意選択で、ゲームが画像の重要な要素（ユーザのアバターなど）の低忠実度モデルを選択するレンダリング距離に等しい最大距離に半径を制限することができる。さらに任意選択的に、これは審美的な目的のために、あるいは特定の環境的特徴または特徴の組み合わせが最終モデルに含まれることを確実にしたいという理由でユーザによって無効にされてもよい。これは、例えばいわゆる「ｍｏｄ」を作成することによってユーザが環境をカスタマイズすることを許可されている場合に特に価値がある。
【００５６】
いずれにせよ、結果は、所与のゲーム状態について仮想環境の２つ以上の相補的な視点を取り込む一組の画像である。
【００５７】
当然のことながら、上記の画像取り込み手順は、娯楽装置によって制御されてもよい。しかしながら、あるいはまたはさらに、ユーザは、これらの視点自体を選択して従来の画像取り込みプロセスを使用することによって、１つまたは複数の異なる視点から同じシーンの画像を取り込むことができる。これらの視点は、本明細書において前述した好ましい分布に対応しなくてもよい。同様に、異なる視点からの同じシーンの画像は、異なる娯楽装置で異なる時間に異なるユーザによって取り込まれてもよいことが理解されよう。ユーザがプールされた一組の画像にアクセスできるようにすれば（例えば、オンラインフォーラムに投稿された場合、またはビデオゲーム用トレーラービデオに含まれるような視点を移動または変更する「フライバイ」ビデオから抽出された静止画の場合）、仮想環境の２つ以上の相補的な視点の同等のセットを取得することができる。
【００５８】
これらの画像と、視点の位置および方向に関する任意選択の関連するメタデータと、を考えると、娯楽装置はこれらの画像を解析して３Ｄモデルデータを生成することができる。
【００５９】
任意選択的に相補的な方法で、いくつかの解析技術を使用することができる。
【００６０】
シルエット解析は、取り込まれた画像内のオブジェクトのエッジを使用して、そのエッジにローカルなオブジェクトのプロファイルを推定する。オブジェクトプロファイルを、別の押し出しプロファイル（通常は別の視点から押し出される）と交差するまで、各視点のプロファイルと直交する方向に押し出して、オブジェクトの形状の近似値を作成することができる。当然のことながら、本明細書で前述した方式に従って視点の数が増加するにつれて、各押し出しはオブジェクトの周りにより小さな角度を成し、その結果、対象物のより正確な全体モデルが得られる。
【００６１】
立体解析では、重なっている２つの視点内の同じオブジェクトの相対的な変位を使用して、各視点からの距離を計算する。この情報から、両方の視点から見える領域内のオブジェクトの３Ｄ形状を示す深度マップを構築することができる。したがって、さらに多くの視点が利用可能である場合には、視点の連続する対を使用して、見ているオブジェクトの表面のマップを構築することができる。
【００６２】
どちらの場合も、視点情報がない場合、これは、画像間の環境的特徴を相関させ、これらの特徴の相対位置に対して最良の相関をもたらす視点位置および方向を選択することによって推定することができる。
【００６３】
当然のことながら、シルエット解析および立体解析を互いに補完するために使用することができる。例えば、２つの技法を使用して、互いのモデルのエラーを検出することができる。２つの技法がしきい値量だけ異なるオブジェクト表面の推定値を生成する場合、しきい値一致内にある２つの技法からのオブジェクト表面の近くの推定値の間の補間に最も近い推定値を使用することができ、他の推定値は破棄される。任意選択的に、モデルのそのような領域はまた、本明細書で後述するように、印刷前にユーザによる検査および／または編集のために強調表示されてもよい。
【００６４】
上記の技法は、画像データが第三者から（例えばフォーラムのスクリーンショットから）取得され、利用可能な追加のメタデータがない場合に特に有用である。
【００６５】
しかしながら、娯楽装置によって生成され取り込まれた画像の場合、娯楽装置自体によって生成された関連する深度情報も取り込むことが好ましい。前述のように、視点の従来のレンダリング中に、レンダリングされたビューから遮られている環境の要素が間引かれる。この遮蔽は、少なくとも部分的には、仮想カメラからの環境内のオブジェクトの相対距離によって決定される。例えば、他のオブジェクトの背後にあるオブジェクトは遮られているとみなされ、したがって間引かれる。これらの距離は、この目的のために娯楽装置によって計算される。これは、取り込まれた画像ごとに、正確でピクセル単位（またはサブピクセル単位）の解像度の距離または「深度」マップが利用可能であることを意味する。
【００６６】
本発明の一実施形態では、この深度マップもまた取り込まれ、３Ｄモデルの生成に使用するために娯楽装置によって取り込まれた各画像と関連付けられる。原則として、この情報は、画像を生成するときに使用されるいわゆるｚバッファをコピーすることによって、レンダラの動作に対して透過的な方法で取得することができる。その結果、画像取り込みプロセスは、ゲームレンダリングエンジンの修正を必要としない。
【００６７】
より一般的には、当然のことながら、各取り込まれた画像内のレンダリングされたピクセルの表面位置を識別するための任意の適切な技法を、３Ｄ原点（または例えばゲーム世界内の原点または分離したターゲットオブジェクトのレンダリングの原点）に対して行うことができ、これにより、潜在的に複数のレンダリングにわたってピクセルの一貫した表現を生成することができる。
【００６８】
ここで図４を参照すると、各画像の位置Ａおよび視点方向Ｂに関する情報が、関連する距離情報ｚと共に与えられると、各画像のピクセルは、例えば共通の原点に基づいて、共有仮想モデリング空間３００内のそれぞれの点に投影することができる。実際には、各ピクセルは、画像視点の位置Ａから、画像にローカルな座標方式でｘ、ｙ、ｚの量だけ変位する（しかし、既知の技法を使用して、共有仮想モデリング空間に共通の座標方式に回転することができる）。ここで、ｘとｙは取り込まれた画像（概念上の画面Ｃで表される）のピクセル座標であり、ｚはカメラ位置Ａからのそのピクセルの関連する深度または距離値である。分かりやすくするために、図４では１列のピクセル（つまり、ｘの単一の値）のみが投影されているが、当然のことながら、この方法で任意の数の画像のピクセルを投影することができ、例えば、それらはターゲットオブジェクトに対応する。
【００６９】
その結果、ブロブマンの例を使用して図４に示すように、各画像のピクセルは、シーン内の仮想オブジェクトの表面の３Ｄの正しい位置にある共有仮想モデリング空間内に配置される。各画像が共有仮想モデリング空間に投影されるにつれて、シーン内の各オブジェクトのより多くの表面が、このように「塗りつぶされ」る。２つの画像が３Ｄ空間内の同じ点に同じ画素を投影する場合、第２の投影された画素は廃棄されてもよく、または第１の画素を置き換えてもよく、または平均値が生成されてもよい。
【００７０】
当然のことながら、ピクセルは２次元オブジェクトである。したがって、本発明の一実施形態では、画像からの画素が共有仮想モデリング空間内の位置ｘｉ、ｙｊ、ｚｋに投影されると、実際にはボクセル（通常は立方体の３次元画素）がその位置に作成される。そして、投影されたピクセルに関連した色情報がボクセルの色情報として使用される。
【００７１】
その効果は、仮想環境の可視表面を表すボクセルのシェルが、各画像内の画像ピクセルの色データを共有仮想モデリング空間内のｘ、ｙ、ｚ位置に投影することによって構築されることである。
【００７２】
当然のことながら、娯楽装置からのｚバッファ深度情報を使用して、複数の画像を共有モデリング空間に投影する代わりに、この深度情報は、前述の立体深度推定および／またはシルエット解析および表面押し出しの技法を使用して推定することができる。それ故、これらの技術はまた、上記の方法で共有モデル空間内でボクセルシェルのアセンブリを駆動するために使用することができる。
【００７３】
いずれにせよ、いったんすべての画像が使用されると、結果として得られるボクセルのシェルを完全性について解析することができる。表面内の任意のギャップ（任意選択でしきい値サイズ以下）は、周囲の表面からの補間によって塗りつぶすことができる。
【００７４】
ボクセルシェルの形で環境の３Ｄ形状の推定値を生成したので、印刷のために３Ｄモデルを生成することができる。
【００７５】
［モデルの完全性の決定および改善］
次に図５を参照すると、本発明の一実施形態では、（図示されているキャラクタ５２０などの）ターゲットオブジェクトが複数の視点からレンダリングされている。これまでに、少なくとも２つの画像、またはほんの数個の画像を使用できることを示唆したが、実際には、ターゲットオブジェクトを十分に網羅するためにかなり多くの画像を使用することができる。したがって、図５では、非限定的な例として、仮想カメラによってキャラクタの３つの円軌道の各々に対して８０個のレンダリングが生成され、各軌道は軌道自体に直交する円の周りに等距離にある。当然のことながら、軌道の数と軌道あたりのレンダリングの数は純粋に例示であり、レンダリングと軌道の適切な組み合わせ（または部分的な軌道、例えばターゲットオブジェクトのベースの高さより上の半円形）、または軌道以外の分布を考慮することができる（均一または不均一の球体の有効面上のカメラ位置の分布などであって、例えば、オブジェクトを取り込む最初の指示が行われたときのゲーム内カメラの位置の近くに追加のカメラ位置があるなど）。同時に、レンダリングごとに、任意選択で、仮想カメラ位置からのレンダリングされた各ピクセルの深度（距離）データも記録されるので、レンダリング空間でレンダリングされた各ピクセルの位置は、レンダリング、深度情報、カメラの位置から決定することができる。
【００７６】
当然のことながら、十分な視点が提供されることになる任意の方式が適切であり得る。それ故、３つの周回仮想カメラの代替として、（例えば８０個の）静止仮想カメラの立体配置を使用することができる。同様に、いずれの場合も、ターゲットオブジェクトは静止していてもよく、あるいはそれ自体が１つまたは複数の軸で回転して、例えばいくつかの隣接ビューを有するカメラの小さな立体配置の各々を提供し、大きな立体配置における異なる視点での欠けているカメラを効果的に補償してもよい。
【００７７】
得られたＮ個の画像（この例では２４０）は、例えば前述のように、既知の写真測量技術への入力として提供される。
【００７８】
この技法の出力例を図６Ａおよび図６Ｂに示す。図６Ａは、仮想写真測量法を用いて導出したキャラクタのモデルを示し、表面的にはそれは正確であるように見える。しかしながら、図６Ｂから分かるように、楕円形のリングによって強調されているように、主に銃によって隠されたキャラクタの胴体の領域は正確にはモデル化されておらず、モデルの領域は融着または歪曲される。
【００７９】
明らかに、そのようなモデルを印刷したユーザは結果の品質に失望するであろう。
【００８０】
したがって、ここでまた図７を参照すると、本発明の一実施形態では、３Ｄ印刷モデリングの方法は、第１のステップｓ７１０において、ターゲット仮想オブジェクトの表面のボクセル表現を生成するステップを含む。
【００８１】
当然のことながら、多重レンダリングの目的で仮想環境／ターゲットオブジェクトを凍結したので、実際のオブジェクトモデルは仮想写真測量プロセスの間には静的なままである。その結果、連続する各レンダリングによるデータ収集の進行状況を追跡するために、モデルの個別の永続的な表現を生成することが可能である。ここで図８Ａおよび図８Ｂを参照すると、図８Ａにレンダリングされるようなサムライキャラクタの例の場合、そのキャラクタの表現は、図８Ｂに示すように生成することができる（この場合、わずかに異なるポーズで、斧を振ろうとしている）。
【００８２】
分離した持続的な表現は、印刷されるターゲットオブジェクトの表面のボクセルモデルである。図８Ａと図８Ｂとの比較から分かるように、通常はボクセル解像度はレンダリング解像度よりも低いので、レンダリングされた表面内の複数のピクセルはボクセルモデル内の対応するボクセルにマッピングされる。
【００８３】
ボクセル解像度は、使用される３Ｄプリンタのボクセル解像度に対応するように任意選択で選択されてもよい。したがって、例えば、３Ｄプリンタのボクセル解像度が１ｍｍ３で、印刷されるモデルの高さが１０ｃｍの場合、ボクセルモデルの高さは１００ボクセルになる。当然のことながら、３Ｄプリンタと少なくとも同じかそれより高いボクセル解像度を使用することが好ましいが、これは必須ではない。
【００８４】
ボクセルモデルは、レンダリングプロセス中に抽出されたモデルデータを使用して生成することができ、または同じターゲットオブジェクトモデルデータを使用して別々にレンダリングすることができる。
【００８５】
第２のステップｓ７２０において、カウンタが各ボクセルに関連付けられる。このカウンタは、後で説明するように、そのボクセルに対応するターゲットオブジェクトの部分からのピクセルを含むレンダリングされた画像の数を集計するために使用される。したがって、ボクセルは、それらのカウンタと共に、ボクセルに対応する各表面領域が写真測量プロセス中に何回レンダリングされるかのボクセルヒストグラムを形成する。したがって、このカウンタはボクセルの主ヒストグラムカウンタと考えることができる。
【００８６】
第３のステップｓ７３０において、ターゲット仮想オブジェクトは、例えば図５を参照して前述したように複数の視点からレンダリングされる。
【００８７】
次に、レンダリングされた視点ごとに、第４のステップｓ７４０において、ボクセルに対応するオブジェクト表面の一部分上の第１のピクセルがレンダリングされる場合、ボクセルに関連付けられた主ヒストグラムカウンタがインクリメントされる。
【００８８】
前述のように、通常はボクセルの解像度はレンダリングされたピクセルの解像度より低く、これは潜在的に複数の（そして可変の）数のピクセルが任意の与えられたレンダリングにおいて対応するボクセルにマッピングできることを意味する。結果として、レンダー内のボクセルに対応するピクセルの総数は意味のないものになり、カウントが複数のレンダーにわたって累積した場合、これは複雑になる。
【００８９】
むしろ、ボクセルにマッピングし直すレンダリング内の最初のピクセルは、ボクセルに対応するモデルの領域がそのレンダリング内で適切に視覚的に表されていることを示すものとみなすことができると考えることができる。
【００９０】
このチェック手法を実行する簡単な方法は、各レンダリングに対して第１の状態（例えば、慣例に応じて非アクティブ、低、または０）にリセットされるフラグを各ボクセルにさらに関連付けることである。続いて、ボクセルのカウンタは、そのボクセルに対応するオブジェクト表面の一部にピクセルをレンダリングするという前述の条件が、その関連するフラグが第１の状態にあるという条件と共に満たされる場合にのみインクリメントされる。次に、主ヒストグラムカウンタがインクリメントされると、フラグも第２の状態（例えば、慣例に応じてアクティブ、高、または１）に切り替えられる。
【００９１】
主ヒストグラムカウンタがインクリメントされた場合にフラグを別の状態に切り替え、フラグがデフォルトの初期状態にある場合にのみそのカウンタをインクリメントすることにより、主ヒストグラムカウンタは、レンダリングごとに１回しかインクリメントできない。つまり、最初にレンダリングされたピクセルは、そのボクセルに対応するターゲットオブジェクトの表面の領域にあることが検出される。
【００９２】
当然のことながら、原則として、フラグ方式に加えてまたはその代わりに、異なるカウント方式を使用することができる。例えば、任意選択で、そのボクセルに対応するピクセルがレンダリングに表示される場合、Ｍまでカウントするボクセルごとに並列カウンタを提供することができる（例えば、Ｍは原則的にボクセルにマップされるピクセルの一部に対応する数値である）。
【００９３】
したがって、例えば、１０ｃｍモデルの１ｍｍ３ボクセルの前のケースでは、ボクセル表現は１００ボクセルの高さになり、レンダリングされたオブジェクトの高さが１０００ピクセルの場合には、例えば遮蔽なしに顔を見た場合、潜在的に１００ピクセル（１０ｘ１０ピクセル）がボクセルにマッピングされると推測することができる。
【００９４】
それ故、ピクセルの１／２に対して、並列カウンタはＭ＝５０までカウントする。一方、２５分の１ピクセルの場合、並列カウンタはＭ＝４までカウントする。この場合、主ヒストグラムカウンタは、パラレルカウンタが選択されたＭ個のしきい値に到達した場合にのみインクリメントすることができる。これは、そのボクセルに対応するピクセルの自明でない割合が所与のビュー内でレンダリングされたことを示すであろう。この割合は、例えば１００％から１％の範囲内のどこでもよいが、より典型的には５０％から１％の範囲内、さらに典型的には２５％から２％の範囲内、さらに典型的には１５％から３％の範囲内、さらに典型的には１０％から４％の範囲内である。
【００９５】
同様に任意選択で、Ｐまでカウントアップする並列カウンタを設けることもでき、ここでＰは、レンダリングすることができる可能なピクセルの割合である。特定のレンダリングの解析が終了すると、パラレルカウンタの最終値が主ヒストグラムカウンタに追加される。これにより、ビュー内のボクセルごとにレンダリングされるピクセルの異なる量を反映しながら、ヒストグラム値間の不均衡の程度を制限することができる（上記の例を続けると、分数が１／１０で、Ｐ＝１０の場合、１００個の対応するピクセルがレンダリングされたボクセルは、ヒストグラムに１０だけを追加する。一方、対応する５つのピクセルがレンダリングされたボクセルでは、５つすべてがヒストグラムに追加される）。時間の経過と共に、モデルのどの部分が他の部分よりよく表現されているのかは明らかであるが、値の格差が潜在的に複数桁になることがないため、その後の処理が困難になる可能性がある。
【００９６】
したがって、この場合、この方法は、各ボクセルを、所定の最大カウント値に制限されている第２のカウンタに関連付けるステップを含み、主ヒストグラムカウンタをインクリメントするステップは、所定の最大カウント値に従って、ボクセルに関連付けられた第２のカウンタをインクリメントするステップを含み、そのボクセルに対応するオブジェクト表面の一部のピクセルがレンダリングされる場合には、主ヒストグラムカウンタを第２のカウンタの最終値でインクリメントする。
【００９７】
再び図５および図８Ｂを参照すると、所定のカメラ位置でのすべてのレンダリングが完了し、写真測量に関連するデータが蓄積されると、個別のボクセルモデルの主ヒストグラムカウンタは、ターゲットオブジェクトの対応する領域がすべての異なるカメラ位置でレンダリングされた頻度を示す（または任意選択で、完全性を示す）値を有する。
【００９８】
次に図９を参照すると、本発明の一実施形態では、３Ｄ印刷モデリングの方法は各ボクセルについて以下のように進行する。
【００９９】
第５のステップｓ９５０において、カウンタが所定のしきい値と比較されて、それがその値を下回るかどうかを検出する。それがしきい値を上回る場合には、そのボクセルに対応するターゲットオブジェクトの領域は、写真測量プロセスへの良好な入力を提供するのに十分な頻度で撮像されていると仮定され、３Ｄ表面の幾何学的形状を（任意選択で、好ましくは関連するテクスチャも）生成するために前述のように続行することができる。生成された３Ｄ表面の幾何学的形状は、ポリゴン、点群、高解像度ボクセルシェル、または本明細書で後述するように後続の処理のための任意の適切な表現の形態であってもよい。
【０１００】
しかしながら、カウンタがしきい値を下回る場合には、そのボクセルに対応するターゲットオブジェクトの領域は、写真測量プロセスへの良好な入力を提供するのに十分な頻度で撮像されていないと仮定され、したがって少なくとも１つの追加のレンダリングが必要である。例えば、Ｑ−Ｒレンダリングが求められてもよく、ここでＱが所定のしきい値であり、Ｒがそのボクセルの主ヒストグラムカウンタの実際の値である。あるいは、１つの追加のレンダリングのみが求められてもよい。
【０１０１】
このレンダリングを得るために、第６のステップｓ９６０において、ボクセルの位置から複数の線が投影される（例えば、ボクセルの中心または表面から等距離に放射する１６、３２、６４、１２８、２５６本の線）。これらの線は、（ボクセル位置に向かって線を見下ろすときに）ボクセルに対応するターゲットオブジェクトの領域と交差することが保証されている仮想カメラに対する候補視線方向と考えることができる。
【０１０２】
次に、第７のステップｓ９７０は、他のボクセルから遮蔽されることなく任意の線が所定の距離に達するかどうかを検出するステップを含む。例えば図５を参照すると、他のボクセルによる中断／遮蔽なしに、仮想カメラが配置されている球の表面に線が到達するかどうかを検出することができる。
【０１０３】
当然のことながら、カメラが同等の線に沿っている場合には、任意の線とその球との交点は、仮想カメラが、ボクセルに対応するターゲットオブジェクトの領域の少なくとも一部を含むレンダリングを得るために配置され得る位置を表す。
【０１０４】
したがって、第８のステップｓ９８０において、少なくとも１つのそのような線（レンダリング空間が異なる座標を使用する場合はレンダリング空間に置き換えられる）が、ターゲット仮想オブジェクトのさらなるレンダリングのための光軸として選択され、次いで、ステップｓ９９０において、選択された光軸または各選択された光軸に沿ったターゲットオブジェクトのレンダリングが生成される。
【０１０５】
複数の線が途切れることなく所定の距離に達する場合、任意選択でそれらのすべてをこのように使用することができ、あるいは所定の数の線、またはそれらのＱ−Ｒ、あるいは１つだけとすることができる。利用可能な線のサブセットが使用される場合、任意選択で、ターゲットモデルの関連領域の多様な視点を得るように、カメラ球上の選択された線の間の距離を最大にするように線が選択される。
【０１０６】
このようにして、ターゲットモデルの表現不足の領域のビューを取り込むための追加のレンダリングを識別して取得し、写真測量の目的のためにモデルの必要な範囲を改善することができる。
【０１０７】
したがって、カウントが所定のしきい値を下回るボクセルの処理が完了した後に、再びレンダリングは写真測量プロセスへの適切な入力を提供することができ、これは、３Ｄ表面の幾何学的形状を（任意選択であるが、好ましくは関連するテクスチャも）生成するために前述のように進むことができる。再び、生成された３Ｄ表面の幾何学的形状は、ポリゴン、点群、高解像度ボクセルシェル、または本明細書で後述するように後続の処理のための任意の適切な表現の形態であってもよい。
【０１０８】
したがって、追加のレンダリングが必要であるかどうかにかかわらず、写真測量プロセスの直接生成物は、ターゲットオブジェクト（および任意選択で任意の関連テクスチャ）の３Ｄ表面の幾何学的形状である。この３Ｄ表面の幾何学的形状（および任意選択のテクスチャ）は、本明細書で後述するように修正のために別個の装置にエクスポートすることができ、または、ローカルまたはリモート、プライベートまたはパブリックリポジトリに保存し、共有することができる。
【０１０９】
一方、特定のボクセルについて、他のボクセルからの遮蔽なしに所定の距離に到達するラインがない場合、任意選択でラインの数を増やすことができ（例えば、１２８から２５６ライン）、したがって、回線密度が高くなり、回線が途切れないルートを有する機会が増える。そのようなプロセスは、最大行数（例えば５１２）に達するまで続けることができる。
【０１１０】
遮蔽なしでラインが所定の距離に到達しない場合には（任意選択でライン数を増やした後）、この方法は、結果の写真測量がターゲットオブジェクトの不完全なビューに基づいていることをユーザに警告するステップを含むことができ、したがって、レンダリングされたオブジェクトの仮想写真測量に基づく３Ｄ印刷モデルにはエラーが含まれる場合がある。方法は次に終了し、ユーザに終了の選択肢を提供するか、ユーザに続行の選択肢を提供するか、または続行することができる。
【０１１１】
特に、ラインの数が所定の距離に到達せずに最大数に達した場合、これはボクセルに対応するモデル領域のビューが非常に制限されていることを意味し、そのため、その領域のモデルに結果として生じる歪みやエラーは、美的影響を最小限に抑えることができる。
【０１１２】
任意選択的に、対応するボクセルのヒストグラムカウンタ値に基づいてモデルの領域を色分けする、いわゆる「ヒートマップ」を重ね合わせたモデルの１つまたは複数のレンダリングをユーザに提供することができる。これは、レンダリングの任意の所与の領域についてのソースデータの品質（例えば、レンダリングの数）の単純な指示をユーザに提供する。
【０１１３】
同様に、写真測量が完了した後に、結果として得られるモデルは、例えばユーザが視点を制御してモデルを検査することができるように、ユーザに対してレンダリングされてもよい。やはり任意選択で、得られたモデルは、得られたモデルの任意の所与の領域についてのソースデータの品質（例えば、レンダリング数）をユーザに示すために提供される色ヒートマップオーバーレイを有することができる。これは、モデルの３Ｄ印刷にコミットする前に、ユーザが、エラーを含む可能性があるモデルの領域をより詳細に検査するのを助けることができる。
【０１１４】
［モデルを修正する］
当然のことながら、写真測量プロセスによって生成された３Ｄ表面の幾何学的形状は、ポリゴンで表現されているか、点群として、または高解像度ボクセルシェルとして表現されているかにかかわらず、概念上のゼロの厚さ、１ピクセルの厚さ、または１（高解像度）ボクセルの厚さに対応する無視できる厚さを有する。いずれにしても、３Ｄプリンタに変換されるとき、これは１つの印刷ボクセル厚（例えば、上記の例を使用して、１ｍｍ厚）として解釈される可能性が高い。これは、与えられたモデルに対して実際には適切であるとは考えにくい。
【０１１５】
したがって、３Ｄ表面の幾何学的形状を今度は印刷されるボクセルのシェルとして扱うと、シェルを所定の厚さに押し出すことができる。押し出しは、隣接するボクセルを共有仮想モデリング空間に投影された側とは反対側（すなわち、シェルの内側または下側）の各側面のボクセルに追加することによって実行することができる。追加されるボクセルの数は、Ｙ個のボクセルのうちの少ない方、またはオブジェクトの反対側に存在する表面に到達するのに必要とされる数であってもよい。モデルを印刷するために使用されている材料の重量および強度に応じた厚さとなるようにＹを選択することができる。
【０１１６】
同様に、（現在押し出されている）モデル内の最も低い点を決定することができる。通常はシェルの下面にある少なくとも２つの追加の点をさらに押し出して最も低い点と一致させることができ、したがって物理モデルに対して少なくとも３つの支持点を提供する。好ましくは、これらの支持点はモデルの計算された質量中心の周りに分布している。
【０１１７】
このようにして、仮想環境の３Ｄモデルは、物理的に印刷されたときには動かなくなり、複数の角度から見ることができる複数のゲーム内画像から構築することができる。
【０１１８】
次にモデルは３Ｄプリンタドライバに送信され、３Ｄプリンタドライバはモデルを下から上に向かって層にスライスする。次いで、これらの層は、前述のように３Ｄプリンタによって連続的に印刷される。
【０１１９】
上述のように、仮想環境の少なくとも一部の写真測量を使用して、３Ｄ印刷モデルの基礎として使用することができるボクセルシェルを生成することができる。いくつかの環境は他のものよりこの３Ｄ印刷プロセスにより適している。例えば、Ｍｉｎｅｃｒａｆｔ（登録商標）内の単純なブロックベースの環境は、３Ｄプリンタでレンダリングするのに非常に適している。
【０１２０】
しかし、これは規則ではなく例外である。ビデオゲームの特別な魅力は、通常の物理学の法則にとらわれない環境やキャラクタを提示する能力である。特に、オブジェクトは、物理的な接続を持たずに、互いに所定の関係で存在することができ、（この図では手と足が胴体に物理的に取り付けられていない図３のキャラクタ「ブロブマン」で例示されている）、一方、他のオブジェクトは、カーテン、ケープなどの３次元環境内の２次元でのみ定義され、多くの場合、壁などの環境構成要素で定義される。これは、物理的強度が仮想環境の要件ではないためであり、プログラム規則では特定の境界を超えた移動が妨げられ、壁はそのような境界を画定するテクスチャを装飾するための表面に過ぎない。
【０１２１】
したがって、仮想環境は、厚さがゼロのいくつかの境界面を含むことができ、その上に物理的オブジェクトが置かれ、そのうちのいくつかは、物理的に印刷された場合さらに不安定になるかまたは支持されない場合がある。そのような境界面の一例は、図３の仮想環境２００内の部屋２１０の壁であり得る。
【０１２２】
３Ｄプリンタを使用してこのような仮想環境を忠実に印刷することは不可能であり得る。
【０１２３】
したがって、本発明の一実施形態では、前述のボクセルシェルは、３Ｄ印刷モデルの物理的要件を考慮するように修正される。
【０１２４】
前述のように、ボクセルのシェルは、ある程度の物理的強度を提供するために、Ｍボクセル厚になるように押し出すことができる。これらのオブジェクトに対応するボクセルのシェルはボクセルのシェルのその他の要素と同じように押し出されるので、これは環境内の２Ｄオブジェクトの問題にも対処する。
【０１２５】
しかしながら、環境のいくつかの要素については、これは十分な物理的支持を提供しない場合があり、または環境内の空中のオブジェクトの場合には、支持が完全に失われる場合がある。
【０１２６】
［手続き型補足幾何学的形状］
したがって、ボクセルシェルに対する手順上定義された修正は、３Ｄ印刷の目的のために提供することができる。これらの手続き上の変更は、普通なら３Ｄ印刷モデルで複製することが実行可能ではないであろう仮想環境のいくつかの要素に対する構造強度および／または物理的支持を提供する。
【０１２７】
これ以降、「プリンタ幾何学的形状」への言及は、印刷用の３Ｄモデルを定義するために作成されたボクセルを指す。
【０１２８】
初期ボクセルシェルが生成されると、手続き的に生成または修正されたプリンタ幾何学的形状を娯楽装置によって生成することができる。
【０１２９】
ボクセルシェルは、いくつかの基本的な規則に従って、追加の幾何学的形状が必要かどうかを検出するために解析される。
【０１３０】
解析ステップの１つは、環境内にサポートされていないオブジェクトがあるかどうかを検出することである。
【０１３１】
もしそうであれば、これらは、例えば雪片、弾丸などのような、しきい値未満のオブジェクトが無視され、その後３Ｄモデル内に保持されないように、最小サイズしきい値に従うようにされてもよい。ボクセルシェル内の関連するボクセルを削除してもよい。任意選択で、このステップは、モデルのための画像を収集するときにこれらの項目が最初の場所で決してレンダリングされないように、修正されたレンダリングプロセスで実行され、画像の解析をより簡単にする。
【０１３２】
一方、しきい値を満たすオブジェクトについては、接続ロッドなどの支持構造のためのプリンタ幾何学的形状は、オブジェクトと近くのアンカーポイントとの間に手続き的に生成されてもよく、アンカーポイントは最終的に地面に接続される環境の一部である。地面自体は、ボクセルシェルの最も低い点に接続されているとみなすことができる。任意選択的に、ボクセルシェルの最も低い部分から上方に解析を進めることができ、それによって、支持されていないオブジェクトを順次支持することができ、それらが次のオブジェクトを順番に支持することを可能にする。
【０１３３】
その結果、例えばビデオゲームキャラクタが空中に跳躍している場合、ボクセルのシリンダ、例えばデフォルトではＭ個のボクセルを作成することによって、足の付け根と地面との間に支持ロッドが形成される。
【０１３４】
しかしながら、ロッドの太さも基本的な規則に従って手続き的に決定されてもよい。所与のタイプのプリンタについて、一般的な３Ｄプリンタ材料の体積による重量、ならびにそれらの圧縮強度および曲げ強度が分かるであろう。さらに、印刷モデルの予想サイズも分かる。したがって、娯楽装置は、支持されていないオブジェクトの重量を推定し、モデル内でオブジェクトを適切に支持するのに必要な支持ロッドの太さを計算することができる。特に接続ロッドが部分的または全体的に横方向であり、したがって曲がる可能性がある場合、支持されていないオブジェクトのモーメントはその重量にロッドに沿った現在位置からの距離を乗じたものである。さらに、そのようなオブジェクトのために接続ロッドを構成する場合、接続ロッド自体の重量は、重量のかなりの割合を占める可能性がある。その結果、ロッドのそれぞれの部分が支持されていないオブジェクトよりもアンカーポイントでより大きな重量を支持するので、ロッドはアンカーポイントに近づくにつれて太くなり、支持されていないオブジェクトに向かって先細になる。
【０１３５】
別の解析ステップでは、上記の原理はボクセルシェルの他の部分にも適用することができる。例えば、ゲーム内の仮想モデルの机の脚部が細すぎて、机の表面や机の上にあるオブジェクトの総質量を支えられない場合がある。例えば、机の上にキャラクタが立っていても、机の脚部の太さが数ボクセルしかない場合、物理モデルをサポートするのに十分な強度がない可能性がある。したがって、ボクセルシェルの特徴を評価してそれらがモデルで支持する総重量を決定することができ、これがこの重量を支持するボクセルシェルの断面積に対する安全なマージンを超える場合、その断面を拡大することによって厚くし、ボクセルでそれを塗りつぶすことができる。この原則は、例えば環境内の樹木にも適用することができ、３Ｄプリンタに関連付けられた特定のマテリアルを使用して３Ｄモデルとしてレンダリングした場合に、既存の幾何学的形状が重量に対応するには局所的に不十分な状況においては、枝と幹の累積重量を使用して、枝または幹の幾何学的形状を局所的に変更し、重量に対応するために断面を大きくする。
【０１３６】
その後に、調整されたモデルの重心を計算して、それが倒れるかどうかを検出することができる。もしそうであれば、安定性を回復するために支持体を動かしてもよいし、あるいは任意選択でボクセルシェルを１つまたは複数の選択された場所で厚くして重心を安定位置に戻してもよい。
【０１３７】
前述のように、環境の２次元成分は、初期ボクセルシェルの他の部分と共に押し出されて、少なくとも最小厚さを有する３次元オブジェクトを作成する。しかしながら、この押し出しプロセスは、下記のようにさらに修正することができる。
【０１３８】
ここで図１０Ａ〜図１０Ｅを参照すると、図１０Ａは環境２００からの２次元壁を表し、その上にはろうそくとろうそく立てがゲーム内に配置されていることが分かる。次に、図１０Ｂは、壁平面に垂直で画像が投影された側とは反対の方向に壁を延ばして、例えばＹボクセルの所定の厚さを有する壁を記述する幾何学的形状を手続き的に生成する押し出しプロセスを示す。しかしながら、図１０Ｃに見られるように、物理的に印刷された壁の累積重量は、壁上の位置に従って変化し、そしてさらにろうそくおよびろうそく立てをさらに支持する壁の部分について段差に遭遇する。したがって、ベースの近くの壁の厚さがモデルの累積重量を適切に支えるには不十分である可能性があるので、一定の厚さの壁は不適切である可能性がある。
【０１３９】
したがって、図１０Ｄ〜図１０Ｅを参照すると、壁の上部での押し出しの最小の好ましい厚さから始めて、押し出しの厚さは累積重量の関数として増加し、その結果、追加の支持を提供するために壁にろうそく立てを取り付ける位置で厚さの段差が得られる。当然のことながら、図１０Ｄ〜図１０Ｅに示すように、ろうそく立ての荷重が壁にかかる前に壁がわずかに厚くなるように、手続き的規則がそのような取り付け点の周りの領域を厚くすることができる。さらに、手続き的規則は、壁の下側部分を押し出すときに、それ自体が支持体を厚くする追加の質量を受け入れることができる。最後に、図１０Ｅに示すように、ろうそく立ておよび支持領域によって加えられる荷重は、横方向および垂直方向に分散させることができ、その結果、厚くなった支持領域は、壁を伝って広がるにつれて横方向に広がる。
【０１４０】
手続き的規則はまた、ゲーム開発者によって提供される追加の情報と相互作用して、望ましい補足的な幾何学的形状を自動的に生成するのを助けることができる。
【０１４１】
例えば、サポートされていないオブジェクトと最も近いアンカーポイントとの間で接続ロッドが手続き的に生成されるという前述の規則は、アンカーポイントは最終的に地面に接続される環境の一部であり、図１１に示すように、ブロブマン２２０’の３Ｄモデルをもたらすことができる。当然のことながら、キャラクタの手が解析されるとき、それらはキャラクタの胴体よりもキャラクタの足に近いこと、およびおそらくキャラクタの胴体がまだアンカー構造自体に接続されていないこともあり得る。したがって、手続き的規則は、利用可能な唯一の接地されたアンカーポイントである足にキャラクタの手を取り付けることができ、その後、胴体を最も近い１つのアンカーポイントである一方の手に固定することができる。その結果、構造は安定しているが、解剖学的にはユーザの期待に沿うものではない。
【０１４２】
したがって、ゲーム開発者（またはユーザ）は、接続ロッドまたは他の接続／支持構造の手続き的な生成を導くために、環境の要素間の好ましい接続点を特定することができる。これらの接続ポイントは、１つまたは複数の色チャネル内で予約値を使用して定義することができ、画像内の特定の色の識別ピクセルを使用して接続ポイントを識別することができる。例えば、値１２８が接続点を示すために青チャネルで予約されている場合には、図１２のブロブマンキャラクタ２２０’’の例でこれを使用して、モデル上の優先接続ポイントの場所を指定することができる。これらの予約値はボクセルシェル内で使用され、手続き的規則で使用するための識別可能なアンカーポイントを作成する。例えば、識別ピクセルの他の２つの色チャネルの一致する値を使用して、ペアの接続ポイントを示すことができる。そのため、識別ピクセルの赤と緑の値が手と胴体で同じになる可能性があり、これらは互いに接続されるセクションとして識別される。このようにして、接続構造の配置の芸術的な制御は、別個のメタデータを必要とせずに開発者によって維持することができる。ブロブマンの場合、これを使用して、図７に示すように、解剖学的に許容できる一組の接続ロッドを確保することができる。その間、接続／支持構造の手続き的生成のための規則は、依然として、印刷構造を適切に支持するために必要とされる必要な断面を決定するであろう。
【０１４３】
また、当然のことながら、レンダリングされたゲームで見つからない補助プリンタ幾何学的形状の要素（上記の「ブロブマン」の例の接続ロッドなど）の場合、既存のボクセルシェルからテクスチャ（色）を推定するか、色を指定しないことがある。色が外挿される場合、任意選択で、色は重力に抗して要素を支持する構造体の部分（例えば地面、またはブロブマンの場合は、それぞれ足から胴体まで、および胴体から手および頭部まで）から外挿されてもよい。これは、モデル内で最も目立たない支持構造を作成する可能性が高いためである。あるいは、テクスチャを使用しない場合、裸のプラスチック（または他の３Ｄプリンタ材料）は露出されたままであり、これが元の画像の一部ではない機能的支持であることを見る人にはっきりさせる。どちらの手法が好ましいかは、ユーザにとって芸術的な決定である。
【０１４４】
また、当然のことながら、印刷用に選択されたスケールで、レンダリングされた画像のピクセル解像度が３Ｄプリンタのボクセル解像度よりも高い場合がある。その結果、レンダリング環境の特徴は、３Ｄプリンタのボクセル解像度に対して高い空間周波数を有することがある。したがって、そのような高い周波数の細部を除去し、それによって結果として生じるモデルにおけるエイリアシング効果を回避するために、共有仮想モデル空間に投影する前に、画像を互換性のある解像度にフィルタリングすることができる。この場合、予約された色チャネル値が手続き的規則によって使用されることになっている場合、これらは保存されるか、またはフィルタ処理後に低解像度画像に再挿入される。深度情報も同様にフィルタリングすることができる。
【０１４５】
したがって、上記の技術または他の適切な技術のいずれかを使用して、３Ｄ表面の幾何学的形状の特性（その厚さまたは結合要素など）を修正して、すぐに、または将来的に３Ｄ印刷用に出力することができる３Ｄ印刷可能なモデルデータを形成することができる。その結果、３Ｄ表面の幾何学的形状の特性を修正して出力される３Ｄ印刷可能モデルデータを形成する直接生成物は、３Ｄ印刷可能モデルデータである。この３Ｄ印刷可能モデルデータは、モデルを印刷する決定をする前に、直接プリンタに出力することも、あるいはローカルまたはリモートのプライベートまたはパブリックリポジトリに出力してユーザまたは他人によるレビューをすることもできる。
【０１４６】
［塗りつぶしアルゴリズム］
当然のことながら、３Ｄ印刷用のモデルがコンピュータ支援設計パッケージからもたらされる場合、それらはうまく構造化されており、３Ｄ印刷用に容易に処理される。しかしながら、ビデオゲームデータが印刷される場合には、取り込まれたモデルは、縮退したポリゴンおよび／または厚さゼロの特徴（例えば、先に図１０に関連して説明したものなど）を含むことができる。
【０１４７】
これらのモデルを印刷可能にするための１つの手法は、例えば、本明細書のどこかに記載されているような手法に従って、最初にモデル内の中実の（囲まれた）領域を識別し、次に必要に応じてこれらの領域を強化または厚くする操作を実行することである。
【０１４８】
ここで図１３Ａ〜図１３Ｃを参照すると、例えば３Ｄボクセルモデルのスライス内の中実領域または囲まれた領域を識別するために、塗りつぶし技術を用いてそのスライス内の中実領域を識別することができる。
【０１４９】
図１３Ａは、この場合は５つの囲まれた領域を含む例示的な２Ｄスライスを示す。これらの領域を識別するために、次に図１３Ｂにおいて、囲まれた領域にないスライスのそれらの部分を占めるように、塗りつぶしをスライスの外側エッジから始めることができる。
【０１５０】
得られた塗りつぶしはマスクとして扱うことができ、図１３Ｃに示すようにこのマスクを反転させることによって囲まれた領域が識別される。
【０１５１】
原則として、個々の囲まれた領域の各々を直接塗りつぶすことは可能であるが、塗りつぶされるスライスの領域がより小さければ、より少ない計算リソースを必要とする可能性があるが、これは囲まれた領域がどこにあるかの事前知識を必要とする。そのような事前知識は保証できない。したがって、スライスの外側から塗りつぶしを使用することで、囲まれた領域を事前知識やそれらの存在や場所に関する仮定なしに識別することができる。
【０１５２】
しかしながら、詳細な３−Ｄモデルでは、この方法で処理するスライスの数は非常に多くなる可能性があり、各スライスは高解像度のものである可能性があることを理解した。結果として、塗りつぶしプロセスの計算負荷は非常に高くなり得る。塗りつぶしプロセスが頻繁に使用される場合、例えば補助幾何学的形状の作成後または作成中、あるいはユーザによる編集が行われた後でモデルの完全性を評価する場合、この問題は悪化する可能性がある。
【０１５３】
それ故、計算的に効率的な塗りつぶしアルゴリズムを実行することが好ましい。
【０１５４】
従来の塗りつぶしアルゴリズムは、同じ色のピクセルの接続領域を代替色で塗りつぶす一般的な方法である。しかしながら、このアルゴリズムは本質的に逐次的であり、それはアルゴリズムが画素ごとにそれらを塗りつぶすようにステップするからである。
【０１５５】
一方、Ｓｏｎｙ  ＰｌａｙＳｔａｔｉｏｎ  ４（登録商標）などの娯楽装置では、そのような塗りつぶしアルゴリズムのための好ましい処理プラットフォームはＧＰＵである。しかし、ＧＰＵには、順次プロセスを効率的に実行しない多数の実行スレッドがある。
【０１５６】
したがって、本発明の一実施形態では、ＧＰＵ処理を利用するために、仮想プロセスの一部を同時に実行することができるように並列塗りつぶしアルゴリズムが提供される。
【０１５７】
簡単に言うと、並列塗りつぶしアルゴリズムは、塗りつぶす画像の四分木を構成する。四分木は、塗りつぶし作業を加速するために、塗りつぶしソースピクセルの多重解像度表現をいくつかの追加データ（本明細書で後述する）と共に格納する。
【０１５８】
四分木のトラバースは、四分木の根（アウトサイドイン塗りつぶしの場合）または四分木の葉ノード（ピクセルシード塗りつぶしの場合）から始まる。トラバースは、画像全体の塗りつぶし速度を向上させるために、画像内の局所特徴サイズによって許容される最も低い四分木レベル（最大面積ノード）でトラバースする。
【０１５９】
トラバース中に、処理される各四分木セルへの入口エッジは、子四分木ノードに正しく行き来し、隣接セルにステップするときに塗りつぶし作業を指示するために追跡される。
【０１６０】
アルゴリズムの結果は、塗りつぶされたピクセルを示すフラッドマスクである。（任意の四分木レベルでの）四分木セルに関連するすべてのピクセルがより速い処理のために連続しているように、マスクはモートン（ｚ次）曲線に格納されるのが好ましい。後で本明細書で説明するように、マスクは、あふれた画素を有するソース画像から、または他の目的のために画像を生成するために後で使用することができる。
【０１６１】
特に、アルゴリズムは、八分木を使用し、セルあたり８つすべての入力面と塗りつぶし結果マスクアドレスの３つの要素からなるモートン曲線を追跡することによって、３次元に拡張することもでき、体積塗りつぶしを実行することができる。
【０１６２】
より詳細には、以下の用語を用いてアルゴリズムを以下に説明する。
−塗りつぶしのソース色：これは、ターゲットの塗りつぶしの色で置き換えられる画像内のソース色である。例えば、画像１３Ａおよび画像１４における塗りつぶしソース色は黒である。
−塗りつぶしターゲット色：塗りつぶしソース色の連結領域を置き換えるターゲット色である。例えば、塗りつぶしターゲット色は白であってもよい。
−境界ピクセル：これらは、塗りつぶしソース色ではないソース画像内のピクセルである。図１４では、境界ピクセルは３つのスパイラルを形成し、主に単色であるが、この色と塗りつぶしソース色を混ぜ合わせたアンチエイリアスエッジも境界ピクセルである。したがって、通常、すべての境界ピクセルは（任意選択で、塗りつぶしソース色の所定の許容範囲内まで）塗りつぶし中に保存される。
−四分木：特徴の詳細に依存して様々な解像度で画像を横切ってマルチスレッドトラバーサルを可能にするために使用される加速構造（空間分割方式）。
【０１６３】
本発明の一実施形態では、塗りつぶしを処理するために使用される四分木は、３つの情報を含む。
１）四分木セル内のすべてのピクセルが境界（非塗りつぶしソース色）であることを示すビット（「全占有」）。
２）四分木セル内の少なくとも１つのピクセルが境界（非塗りつぶしソース色）であることを示すビット（「一部占有）。
３）境界ピクセルが全く空いているセルについては、標高深度が格納され、標高深度は四分木が根に向かっていくらまで登ることができるかを示しながら、まだ完全に境界でないセルに留まる。
【０１６４】
６５５３６ｘ６５５３６までの画像サイズでは、通常、四分木エントリに６ビットが必要である。標高深度の上限はｌｏｇ２（画像サイズ）であり、他の２つのフィールドの各々に１ビットが必要である。
【０１６５】
標高深度は、画像内のどの点でも塗りつぶしのソース色が空いているかどうかを示す適切な指標または代理である。図１５は、図１４の画像の標高深度を視覚化し、より高い標高深度を表すより薄いグレーの濃淡で結果として得られる四分木構造を示し、画像のその領域を塗りつぶすためにより大きな四分木セルが用いられることを意味する。
【０１６６】
塗りつぶしアルゴリズムは、局所的な特徴量について、四分木の根に最も近い四分木レベルを使用して進行する。したがって、塗りつぶし作業がエッジに近づくと、木の葉に向かって移動する。アルゴリズムが塗りつぶされた領域の隙間を通って空き領域に押し込まれると、四分木の根に向かってより効率的に塗りつぶされる。
【０１６７】
第１のステップで、最上位のピクセル占有が生成される。
【０１６８】
これは、塗りつぶしソース色に対してテストすることによって、画像内の境界ピクセルの占有情報を識別する。この結果は、四分木の葉に対する四分木セルの２Ｄ配列であり、各セルはソース画像のピクセルに関連し、全占有ビットと一部占有ビットに同じ値を含む（各セルに１ピクセルが含まれるため）。
【０１６９】
第２のステップでは、ミップマップレベルのピクセル占有が生成される。
【０１７０】
占有レベルの２ｘ２セルの各グループについて、マージされたセルの全占有および一部占有情報は、すべての子全占有フィールドとすべての子一部占有フィールドの論理和をとることによって生成される。これは、最上位が１つのセルだけになり、画像全体に対して、全占有と一部占有を有するようになるまで繰り返される。この段階の後に、四分木構造が完成する。次の段階では、実行中のトラバース処理を高速化するための追加情報がいくつか生成される。
【０１７１】
セル標高深度もまた、上記の第１または第２のステップの前、最中または後の任意の時点でゼロに初期化される。
【０１７２】
第３のステップでは、深度標高値が生成される。
【０１７３】
クワッドの根から始まり、葉に向かって作業し、境界ピクセルが完全に空いているすべてのセル（一部占有＝＝０）について、その４つの子の標高深度を現在のセルより１大きく設定する。これは、四分木の葉ノード（各々が画像内の１ピクセルを表す）までずっと繰り返される。標高深度は、どのセルに対しても、アルゴリズムが空のノード内に留まりながら木の根に向かってステップすることを可能にし、アルゴリズムが塗りつぶしソース色の広い連続領域を迅速に処理することを可能にする。
【０１７４】
図１６は、格納することができるデータを示す四分木（ここでは二分木として表現される）を通るスライスを示す。一番下の行は、木の根にある単一のノードまで組み合わされた、サンプルのソース画像の１６ピクセルから構成されている。各セルの最初の数字は標高深度で、完全に空のセルに留まっている間に木からどれだけ遠くまで移動することができるかを表する。したがって、この場合、５つの最上位セルを識別することができる（１６１０−５０）。
【０１７５】
第４のステップでは、塗りつぶしが実行される。
【０１７６】
塗りつぶしは２つのモードで実行することができる。アウトサイドイン、またはシードピクセルからのいずれかである。２つの方法は、アルゴリズムの開始条件が異なるだけである。アウトサイドインは、画像の外側から、四分木の根（四分木のセルが画像全体を表す）から始まる。ピクセルシードは、四分木の葉ノード（ノードは単一ピクセルを表す）から始まる。
【０１７７】
このアルゴリズムは、並行して実行することができる作業項目のスタックに対して機能する。作業リスト項目は、セルが入力された方向のリストと共に、四分木内のノードを識別する。方向は、四分木を細かくしてより細かいセルに移動するとき、または隣接するセルにスキップするときに、アルゴリズムが対応する決定をすることを可能にする。作業リスト項目の形式は以下の通りである。
【表１】
2020015314.tif 000003
【０１７８】
当然のことながら、塗りつぶしアルゴリズムは、木構造の画像／セルを通って進むにつれて効果的に流れを有する。セルの入口エッジは、塗りつぶしが画像／セルを流れるときに塗りつぶしの方向を追跡する。
【０１７９】
セルは、ゼロ以上のエッジから入力することができる（ゼロは最初のシードフィルピクセルに対してのみ発生し、４つのエッジすべては、アウトサイドイン塗りつぶしの最初の「画像全体」セルに対してのみ発生する）。通常は、セルは、アルゴリズムが進むにつれて、１つの入口エッジ（側面）または２つの入口エッジ（例えば、角）を通って入る。
【０１８０】
セルには４つのエッジがあり、上下左右のエッジが四角形の境界となる。次に、子セルの再帰に関して以下に説明するように、アルゴリズムはセルがどのように入力されたかを追跡し、子セルを正しい順序で選択することができるようにする。これは、セルに、塗りつぶしを妨げる可能性のある境界ピクセルが含まれている場合に発生する。エッジを使用して子セルを選択すると、子セルが正しい順序で処理され、塗りつぶしが境界特徴を飛び越えるのを防ぐことができる。
【０１８１】
当然のことながら、八分木については、６つのエッジ（立方体の面）があるが、それ以外の原理は同じである。
【０１８２】
作業リスト項目は、ＧＰＵスレッドグループ内の複数のスレッドからスタックにプッシュされてポップされる。
【０１８３】
作業リストの初期状態には、塗りつぶしのモードに応じて、単一の作業項目が含まれている。
【０１８４】
アウトサイドインの場合：
【表２】
2020015314.tif 000004
【０１８５】
ピクセルシードの場合：
【表３】
2020015314.tif 000005
【０１８６】
上記のように、アルゴリズムが以下のように進むにつれて、多くの作業項目がスタックからポップされ、多くのＧＰＵスレッドによって並行して処理される可能性がある。作業項目はスタックから取得され、次の情報を指定する。
・四分木レベル。
・セルの入口エッジ。
・セルのＸＹ座標。
【０１８７】
作業項目セルの占有が読み取られ、占有は以下の情報を指定する。
・標高深度。
・全占有ビットは、セル内のすべてのピクセルが境界であることを示す。
・一部占有ビットは、セル内の一部のピクセルが境界であることを示す。
次に、セルは占有からの標高深度を使用して上げられる。これは以下を伴う。
・占有からの標高深度を使用して、作業項目から四分木レベルを調整する。
・標高深度を使用してセル座標を調整する。
【０１８８】
そのセルに対して行われる必要がある作業は、次に、全占有および一部占有ビットに基づいて決定される。
【表４】
2020015314.tif 000006
【０１８９】
その後に、処理する作業項目がなくなるまで、プロセスは最初から繰り返される。
【０１９０】
上記の３つの操作（セル処理の場合）は以下の通りである。
【０１９１】
「セルを破棄し、さらなる操作は必要ない」：この場合、セルは境界色で完全に一杯になっている。このセルに対してこれ以上の処理は行われず、破棄することができる。作業項目スタックに対してそれ以上の作業は生成されない。
【０１９２】
「入口エッジに基づいて子セルに再帰する」：図１７Ａを参照すると、セルは部分的に塗りつぶされており、塗りつぶすスペースを含んでいる可能性がある。作業項目は、入口エッジで選択された子セルに対して生成される。例えば、上および左から親セルを入力すると、図１７Ａに記載されているように、様々な組み合わせまたは入力フラグを用いて、３つの子セルが処理されることになる（入口エッジは太字で示される）。新しい作業項目は、正しいエッジ入口フラグと共に、すべての関連する子セルのスタックにプッシュされる。
【０１９３】
「セルを塗りつぶして、入口エッジに基づいて隣接セルに移動する」：図１７Ｂを参照すると、この場合、セルには境界ピクセルが完全になくなり、塗りつぶしが必要になる。しかし、セルへのルートが複数あるため、このセルはすでに別のスレッド／作業項目で塗りつぶされている可能性がある。セルがまだ塗りつぶされていない場合（塗りつぶしマスクの結果をテストすることによって決定される）、塗りつぶしは隣接するセルをトラバースし、このセルから入ってきた隣接セルを回避する。新しい作業項目は、正しいエッジ入口フラグと共に、すべての関連する隣接セルのスタックにプッシュされる。当然のことながら、入口エッジは、塗りつぶしがセルに入るエッジであり（図１７Ｂの左側の画像に示すように）、図１７Ｂの右側の画像に示すように、隣接セルをトラバースするとき、出力セルは入口エッジセルを除くすべての隣接セルである。その理由は、現在のセルが入力されたときからの方向のセルはすでに処理されていると想定することができるためである。
【０１９４】
この手法を使用すると、塗りつぶしアルゴリズムは塗りつぶしマスクを設定することができる。また、四分木標高メカニズムにより、塗りつぶされるセルが局所的な特徴サイズに基づいてできるだけ大きくなるようにする。塗りつぶしマスクがモートン順で格納されている場合、四分木セルのすべてのピクセルは塗りつぶしマスク内で連続しており、処理は高速である。
【０１９５】
上記の四分木手法は、逐次プロセスを効率的に実行しない多数の実行スレッドを有するＧＰＵまたは同様に並列プロセッサを使用するときに、塗りつぶしの計算上効率的な実行を提供する。それは、将来的に３Ｄ印刷されているモデルの多数のスライスの解析が、完全に囲まれた領域などについて解析されることを可能にする。
【０１９６】
さらに、特定のケースでは、アルゴリズムは従来の塗りつぶしアルゴリズムよりも優れたパフォーマンスを発揮する。図１８Ａを参照すると、これは図１３Ａのサンプルスライスを複製するが、スライス内のオブジェクトは画像の境界まで拡張されている（または別の言い方をすれば、画像はその中のオブジェクトを含む最小サイズに切り取られているので、当然ながら画像全体のサイズ、したがって計算の複雑さが軽減される）。
【０１９７】
しかし、ここで図１８Ｂおよび１８Ｃを参照すると、初期ポイント（例えば画像の左上隅）から始まる従来の塗りつぶしは、図１８Ｂに見られるように画像の左下および右隅に進むことができないが、これは、これらが画像内のオブジェクトによって効果的にブロックされるためである。結果として、囲まれた領域は、図１８Ｃでは誤って特徴付けられている。
【０１９８】
対照的に、本発明は、単一のシードポイントからではなくスライス／画像のエッジに基づいて塗りつぶすことができる（ただし、前述したようにこれも可能である）。その結果、画像の左下隅と右下隅の領域が正しく識別される。
【０１９９】
当然のことながら、これは図１４および図１５にも示されている。らせんパターンの広がりのために、それは実際には背景を４つの別々のセグメントに分割する。しかし、システムはそれらの各々を識別する（図１５の標高マップから推測できるように）。
【０２００】
しかしながら、四分木アルゴリズムでさえも困難に遭遇する可能性があり、それ故さらなる改良の余地がまだある。
【０２０１】
図１９Ａを参照すると、例示的シナリオでは、一対のシリンダ（１９１０、１９２０）がゲーム環境のオブジェクト内に同心円状に配置されて３Ｄ印刷される。図１９Ｂでは、オブジェクトを通して得られたスライスは、スライス内に交互の間隙および囲まれた領域を画定する同心壁を示している。
【０２０２】
図１９Ｃを参照すると、スライス画像のエッジから塗りつぶすときでも、塗りつぶしアルゴリズムは、外側シリンダの外壁を通過することができない（そして通過するべきではない）。結果として、外側シリンダと内側シリンダとの間の中間空隙、および内側シリンダの中央空隙は識別されない。
【０２０３】
その結果、図１９Ｄにおいて、円柱の内部構造は失われ、それは中実のオブジェクトとして表される。明らかにこれはモデルの忠実度の喪失および３Ｄ印刷材料の無駄の両方の点で望ましくない。
【０２０４】
したがって、本発明の一実施形態では、２Ｄ画像スライスをナビゲートするための四分木の使用は、３Ｄ（体積）画像をナビゲートするための八分木によって置き換えられる。
【０２０５】
言い換えれば、四分木を使用してモデルの２Ｄスライスのシーケンスの塗りつぶしを実行する代わりに、アルゴリズムは、八分木を使用してモデルの単一の体積画像に対して塗りつぶしを実行する。理解されるように、四分木の各レベルが四角形を４個の子長方形に分割する場合、八分木の各レベルは直方体を８個の子直方体に分割する。作業項目の標高深度、占有データなどの作成に関するアルゴリズムの残りの部分は、本質的に同じである（２次元セルの４つの可能な入口エッジと同じ機能を満たす体積セルの６つの可能な入口平面を有する）。
【０２０６】
図１９Ａの例に戻ると、当然のことながら、単一の体積画像として表され、前述のアルゴリズムの八分木バージョンを使用して体積塗りつぶしを行うと、同心円筒の問題は解決される。これは、図２０に示すように（説明のために結果の２Ｄスライスに対して）、アルゴリズムがシリンダの上下のギャップを識別し、中間および中央の空隙を塗りつぶすためである。
【０２０７】
したがって、より一般的には、当然のことながら、本明細書で説明する塗りつぶしアルゴリズムは、階層的な空間分割データ構造を使用して、塗りつぶしの問題を並列に処理することができるワークユニットに分割する（例えば、ＧＰＵによって）。構造は通常、２Ｄ画像の場合は四分木、体積画像の場合は八分木である。データ構造の様々なレベルでの画像の特徴の占有に応じた標高深度データの生成により、その効率的なナビゲーションと空の画像領域の効率的な識別を可能にする。
【０２０８】
３Ｄ印刷の目的のために、いつそしてどのようにアルゴリズムを使用するかに関して、さらなる変形例を考慮することができる。
【０２０９】
例として、図８Ａおよび図８Ｂに示すサムライを参照すると、サムライのボクセル取り込みでは、キャラクタの斧は、実際には、ビデオゲーム環境内のキャラクタからわずかに離れた別個のオブジェクトであり得る（例えば、キャラクタは多くの異なるアイテムを保持するようにモデル化されており、それらのすべてが完全に一致するわけではないため、あるいは、印刷のために取り込まれた瞬間のキャラクタ／斧の特定の位置のため、またはキャラクタがちょうど斧を投げる行為を開始したためなどである）。
【０２１０】
しかし、このために、サムライが印刷されると、斧はサムライの手から落ちる（または少なくとも緩んでいる）。
【０２１１】
この問題は、単一のモデルとして作成されるのではなく、ゲームワールド内でアセンブルまたは連結されるビデオゲームキャラクタの一般的な要素にとって問題となる可能性がある。１つの例は、ビデオゲームキャラクタの目がしばしばキャラクタの頭から離れていることである。取り込みプロセスによっては、顔と目との間に隙間があると、目が緩んで印刷された後に、キャラクタの中空の体内に落ちる可能性がある。
【０２１２】
したがって、より一般的には、説明の目的で前述したモデルの２Ｄスライスである事例（ａ）の図２１を参照すると、キャラクタまたは他の印刷可能なオブジェクトは、いくつかの直接隣接する要素ＡおよびＤの複合体である場合があるが、ユーザは、それらに関連するアクセサリＣ（または同様に、完全には整列していないキャラクタのさらなる要素）が付属していることを期待する場合もある。それにもかかわらず、キャラクタ／オブジェクトの全領域内にあり得る環境Ｂの別の要素は、別個であると考えられ、望ましくないかまたは２次的な印刷可能オブジェクト（例えば、キャラクタによって蹴られようとしているフットボール）と考えられる。
【０２１３】
本明細書に記載されているように塗りつぶしアルゴリズムを実行すると、事例（ｂ）に示されているように、Ａ＆Ｄ、ならびに別個にＣおよびＢである３つのオブジェクトの予想された識別が得られる。
【０２１４】
塗りつぶしアルゴリズムは（エッジからではなく）画像内の特定の葉／ポイントで初期化できることを想起すると、アルゴリズムは別の目的に使用することができる。
【０２１５】
第１の塗りつぶしによって囲まれた領域を特定して、ＩＤとして別の色または値を使用して、第２の塗りつぶしを囲まれた領域の１つ（例えば、Ａ＆Ｄに対応する最大の囲まれた領域）内で始めることができる。そのような領域内の正確な開始点は重要ではないが、任意選択で、既存のソース塗りつぶしターゲット色からＮピクセル以上離れていることを確認するテストを行って、最初のピクセルがアンチエイリアス処理された色のブレンドではなく、実際に領域を表していることを確認することができる。しかしながら、明らかに、本明細書に記載される体積測定モデルの場合、そのようなアンチエイリアシングは問題ではなく、したがってこの考慮は本質的ではない。
【０２１６】
部分ＢとＣは接続されていないので、それらは図２１の事例（ｃ）に示すように塗りつぶされない。まだ塗りつぶされていないピクセルを識別し、残りの塗りつぶしソース色／ＩＤを有するピクセルがなくなるまで、したがってすべての切断された部分が識別されるまで、別の色／ＩＤでアルゴリズムを再度適用することができる。結果として、部分ＢおよびＣの各々は、それら自身の塗りつぶしの色／ＩＤを受け取り、図２１の事例（ｄ）に示す最終結果を与える。この時点で、それがさらなるプロセスに関連する場合には、各ＩＤで占められているピクセル／ボクセルの数（または塗りつぶしプロセス中にすでに作成されたカウントを集計）をカウントして、どれが主要部分であるかを判断することが可能である。
【０２１７】
当然のことながら、上記の手法は、八分木および体積画像バージョンのアルゴリズムにも及ぶ。
【０２１８】
この手法によって作成された画像のスライスの完全な特徴付けを考えると、別々のオブジェクトが互いのしきい値距離内にある場所を識別し、それらが実際に結合されるべきかどうかを決定するための規則を適用することが可能である。
【０２１９】
例えば、２つのオブジェクト間の距離を、オブジェクトがその距離内にある（任意選択により重み付けされた）長さまたは面積または（所定のしきい値最大距離）で割った値に基づくメトリックをしきい値と比較して、２つのオブジェクトを結合することができる。
【０２２０】
言い換えれば、不規則な形をした２つのオブジェクトが個々の点で偶然に近接している場合、それらの間の距離は、その距離内の短い共有長で除算することによって相殺されるので、そのようなオブジェクトは、それらを組み合わせてトリガーするために互いにかなり近接していなければならない。これはまた、壊れやすいかもしれない狭い、したがって潜在的にもろいリンクによってオブジェクトを結合することに対して不利に作用する。対照的に、例えば、２つのオブジェクトが適度な距離だけ離れていても、かなりの長さにわたって互いに平行に走っている場合には（通常、オブジェクトは１つとして扱われることを示している）、次に、適度な距離がその長さで除算され、オブジェクトが結合される可能性がより高くなる。
【０２２１】
例えば、マージするべきである２つのオブジェクト間のしきい値距離を単に設定することなどの、他の手法が当業者には明らかであろう。
【０２２２】
いずれの場合も、当然のことながら、接続を提供するために、および／または接続を厚くし強化するために、本明細書で前述した種類の任意選択の相補的な幾何学的形状を使用することができる。
【０２２３】
あるいはまたはさらに、２つのオブジェクトのうち小さい方を移動して大きいオブジェクトとマージすることができ、任意選択で、交差点での小さなオブジェクトの断面積が十分に強い接続を提供するとみなされるしきい値サイズに達するまで、オブジェクトをマージするのに必要な量を移動することができる。任意選択的に、より小さいオブジェクトは、より大きいオブジェクトの近くでその断面積を増大させるために拡張または再スケーリング機能を受けることができる。これは、小さいオブジェクトを大きいオブジェクトとマージすることに直接つながるか、または小さいオブジェクトの断面積を単に増加させて強い接続を達成するのに必要な移動を少なくすることができる。
【０２２４】
同様に、２つのオブジェクトのうちの小さい方が大きい方のオブジェクトと交差するように押し出されてもよく、また任意選択で、十分に強い結合を提供すると考えられる所定の断面積を有する小さいオブジェクト内の点から押し出しが開始されてもよい。
【０２２５】
上記では小さいオブジェクトの特徴を調整することに関して説明したが、当然のことながら小さいオブジェクトの近くにあるより大きいオブジェクトの特徴を２つのオブジェクトを接続させるように、あるいはまたはさらに調整することができる。
【０２２６】
図２１の事例（ｅ）および（ｆ）に拡張または再スケーリングの選択肢が示されており、この場合、結果として、オブジェクトＣ全体が大きくなり、十分な大きさの断面積で主オブジェクトと交差して、強いリンクを形成する。
【０２２７】
任意選択で、この点で、オブジェクトの移動またはサイズ変更がオブジェクト全体内の接続性に他の変化を引き起こした場合には、画像内のオブジェクトを識別するプロセスを塗りつぶしアルゴリズムを使用して再実行することができる。
【０２２８】
その結果、元のオブジェクトＡ、Ｃ、およびＤが結合された単一体になる（事例（ｇ）を参照）。一方、より遠いオブジェクトＢは、距離／共有長メトリック、絶対距離メトリック、またはマージのためのその他の適切なメトリックを満たさなかったので、図２１の事例（ｈ）に示すように分離したままである。
【０２２９】
当然のことながら、実際には、現実的なビデオゲームキャラクタの様々な要素が平坦で互いに平行である可能性は低いため、この手法は、八分木およびアルゴリズムの体積画像バージョンを使用して実行することが好ましい。そのため、このようなモデルの２つの要素は、連続する断面で互いの間で距離が異なる場合がある。その結果、２次元要素の個々のスライスをそのスライスに固有の条件に従って移動、サイズ変更、または押し出しすると、モデル全体として一貫性のない結果が生じる可能性がある。したがって、連続するスライス間で制約を継承することはできるが、このプロセスを立体画像内で実行する方がかなり簡単である。
【０２３０】
また、当然のことながら、モデルは、手動で編集するためにユーザに提示されてもよく、おそらく図２１の事例（ｄ）を参照して上記の塗りつぶしアルゴリズムを使用してマークアップして、注意が必要なすべての個別の囲まれた任意の／各々の領域を識別することができ、結果として得られるモデルの変更により、ユーザの操作が同じ方法で再評価される。
【０２３１】
ここで図２２も参照すると、本発明の要約的実施形態では、並列実行のための塗りつぶし方法は、以下を含む。
【０２３２】
第１のステップｓ２２１０では、画像を受け取り（例えば、ゲーム内オブジェクトの２Ｄスライスまたは３Ｄ体積画像、任意選択で、本書の他の場所で説明されているように他の修正が適用される前、その間、またはその後に）、画像は、塗りつぶしターゲット色で置き換えられる塗りつぶしソース色を有する第１の要素と、塗りつぶしソース色を有さない第２の要素（例えば、前述の境界ピクセルなど）と、を含む。
【０２３３】
第２のステップｓ２２２０では、階層的空間分割方式（例えば、四分木または八分木）に従って画像を分割し、階層内の複数のレベルでセルを形成する（図１６に示すものなど）。
【０２３４】
第３のステップｓ２２３０では、第２の要素による各セルの占有を検出する（例えば、本明細書で前述したように、全占有ビットおよび一部占有ビットを使用する）。
【０２３５】
第２の要素による占有を有さない任意のセルについて、第４のステップｓ２２４０において、そのセルの子セルの深度の標高値をそのセルの値よりも１大きく設定し、塗りつぶしは、セルの深度の標高分だけルートセルに向かってレベルをナビゲートし、第２の要素のないノードのみを占有し、それによって塗りつぶし可能な最大の親セルに到達することを示す（例えば、本書で前述し、図１６に示す）。
【０２３６】
第５のステップｓ２２５０では、第２の要素による占有を有さないセルの塗りつぶしソース色を、塗りつぶしターゲット色で塗りつぶし、それによって受け取った画像を修正する。
【０２３７】
この要約的実施形態の事例では、画像は２次元であり、階層的空間分割方式は四分木であり、セルは直線的である。
【０２３８】
この要約的実施形態の事例では、画像は体積であり、階層的空間分割方式は八分木であり、セルは立方体である。
【０２３９】
この要約的実施形態の事例では、セルを処理する場合に、セルが入力された少なくとも１つの側面が格納され、処理のための追加のセルが、セルが入力された格納された側面上のセル以外の隣接セルとして識別される。
【０２４０】
この要約的実施形態の事例では、セルを処理する場合に、セルが入力された少なくとも１つの側面が格納され、格納された少なくとも１つの側面に隣接する子セルについて作業項目が生成される。
【０２４１】
この要約的実施形態の事例では、複数のセルの各々に対して作業項目が生成され、２つ以上のそれぞれの作業項目が並行して処理される。
【０２４２】
この場合、任意選択で、２つ以上のそれぞれの作業項目は、グラフィック処理装置によって処理される。
【０２４３】
この要約的実施形態の事例では、塗りつぶしターゲット色で置き換えられた画像要素は塗りつぶしマスクを表す。
【０２４４】
この事例のバージョンでは、塗りつぶしマスクの外側の画像領域は閉領域として定義される。
【０２４５】
このバージョンでは、任意選択で、２つの閉領域間の距離に対して距離に基づくメトリックが決定され、メトリックが所定のしきい値よりも小さい場合には、２つの領域の少なくとも一方は、２つの領域が交差するまで、２つの領域の少なくとも一方を移動させることと、２つの領域が交差するまで、２つの領域の少なくとも一方の少なくとも一部のサイズを大きくすることと、からなるリストにおける１つまたは複数の修正によって修正される。
【０２４６】
任意選択的に、２つの領域のうちの少なくとも１つが修正された場合には、塗りつぶしアルゴリズムを繰り返すことができる。
【０２４７】
このバージョンでは、画像は３Ｄ印刷されるオブジェクトの一部または全部を表すことができる。
【０２４８】
任意選択で、画像は、塗りつぶしターゲット色を有する１つまたは複数の要素で形成された穴を、閉領域として識別された画像の領域に追加することによって修正することができる。これは、普通なら囲まれた領域内に閉じ込められる可能性がある３Ｄ印刷材料用の排水路を作り出すために行うことができる（後述の「廃棄材料」のセクションを参照）。任意選択で穴を追加することは、閉領域がしきい値サイズまたは体積より大きいことを条件としてもよい。穴は、固定長（例えば、既知のシェルの厚さと等しいかそれ以上）であってもよいし、あるいはピクセルの所定の幅（例えば、境界ピクセル）を塗りつぶしのターゲット色で置き換えることで、ピクセルの幅が塗りつぶしソース色を含むことが検出されるまで拡張されてもよく、それは囲まれた領域の「壁」が破られたことを示している。
【０２４９】
画像が３Ｄ印刷されるオブジェクトの一部または全部を表す場合には、任意選択で、本方法は、塗りつぶされた画像に応じて３Ｄ印刷命令を生成するステップと、３Ｄプリンタ用の３Ｄ印刷命令を出力するステップと、を含むことができる。
【０２５０】
［オブジェクトの選択］
上記の説明は、ターゲットオブジェクトが仮想環境の領域から選択されたと仮定した。例えば、ユーザは自分のアバター、または自分のアバターと対戦相手を単に印刷するように選択することができる。
【０２５１】
この選択は、例えば、所望のオブジェクトの周囲に境界ボックスを定義するためのユーザインターフェースによって、またはカーソルまたはレチクルを使用してゲーム環境内の特定のオブジェクトを示すためのユーザインターフェースによって行うことができる。
【０２５２】
このようにしてオブジェクトが支持面から分離して選択される場合、選択されたオブジェクトのサイズに応じた面積を有するフラットパネルなどのデフォルト面が生成されてもよい。選択されたオブジェクトは、次に、本明細書に記載の技術を用いて支持面に結合することができる。
【０２５３】
［編集］
規定通りに上記の技法を使用してプリンタの幾何学的形状が得られると、任意選択でそれらを編集用アプリケーションに転送し、ユーザがモデルをプリンタに送信する前にプレビューまたは修正することができる。例えば、起こり得るエラーについてモデルを見直すこと、および／または特定のキーキャラクタのポーズおよび位置を編集することが望ましい場合がある。ユーザがモデルの表面にメッセージを効果的に彫刻することができるように、エディタは、純粋に塗装されたテクスチャ、または例えば表面ボクセルを削除することによってオブジェクトの表面構造のいずれかにデカールを追加することを同様に可能にする。
【０２５４】
［最終的な印刷］
ユーザが自分の３Ｄモデルに満足したら、それをプリンタに送信することができる。前述のように、プリンタドライバはモデルを解析し、連続印刷のためにそれをボクセルの層に分割する。
【０２５５】
プリンタが家庭用装置でありコンソールに物理的に接続されているかまたはホームネットワークを共有している場合、プリンタドライバは娯楽装置上に実装され、結果として得られる描画リストが娯楽装置によってプリンタに送信される。
【０２５６】
しかしながら、任意選択で、印刷サービスが娯楽装置のネットワーク（すなわち、例えば娯楽装置の製造業者によって提供されるネットワーク）によって提供されてもよい。これは、平均的な消費者が買うことができるよりも高価で洗練された３Ｄプリンタへのアクセス、およびその結果としてより良い品質のモデルを可能にするかもしれない。これらの状況では、プリンタドライバは依然として処理負荷をユーザ間で分散するためにコンソール上にあってもよいし、または３Ｄプリンタに接続された中央サーバにあってもよい。第１の事例では、ローカルプリンタドライバは、ユーザのアドレスに関連するメタデータと共に、中央印刷キューサーバに安全に送信することができる描画リストを生成する。第２の事例では、娯楽装置は、印刷のためにそれらを待ち行列に入れる前に必要な描画リストを生成するために関連解析を実行する中央プリンタドライバに３Ｄモデルプリンタ幾何学的形状を安全に送信する。これらのいずれの場合でも、モデルの印刷は、例えば娯楽装置のネットワークに登録された支払いカードを介して、料金の支払いを条件としてもよいし、あるいは同様に、例えばトロフィーやその他のゲーム内賞として、またはゲームの購入価格の一部として獲得することができるバウチャーの受領を条件としてもよく、ユーザにそのゲームから所定の数の３Ｄモデルを作成する権利が与えられる。
【０２５７】
したがって、出力された３Ｄ印刷可能モデルデータに基づいてモデルを３Ｄ印刷するステップは、３Ｄ印刷モデルを直接もたらす。
【０２５８】
［廃棄材料］
当然のことながら、選択的レーザー焼結などの３Ｄプリンティング技術は、結果として生じるモデルの内側に大量の未加工プリンタ材料をトラップする可能性がある。これは、このような手法では、印刷中にモデルの上に連続して粉体層が塗布され、モデルの周囲に対応するごく一部だけが融合するが、周囲に残っている粉体はそのまま残るためである。全体的な結果は、内部に融着したシェルがある粉末の体積であって、そのシェルの外側の粉末は除去可能であるが、シェルの内側の粉末がトラップされている。
【０２５９】
これは、廃棄される原材料に関して不必要なコストを生み出す。それは得られたオブジェクトのバランスにも影響する。その結果、３Ｄ印刷用に設計されたモデルに通気孔や開口部を含めて、不要な粉末を流したり洗い流したりできるようにするのが一般的である。
【０２６０】
しかしながら、そのような通気孔または開口部は、ビデオゲームのキャラクタには存在せず、そして望ましくない。
【０２６１】
したがって、本発明の一実施形態では、粉体ベースのプリンタを使用する場合、印刷シーン内のオブジェクト内の空間の有効容積を計算するための手続き的規則が実装される。その体積がしきい値量を超える場合、オブジェクトは中空体として扱われ、手続き的規則により、中空体のボクセルシェル内にプリンタ粉末が流出することを可能にするサイズの開口部が形成される。好ましくは、開口部は、ユーザがシーンを印刷したいことを示したときに、中空体の下面および／またはユーザにスクリーン上に表示された元の視点とは反対側に配置される。開口部は、ボクセルシェルの穴、または好ましくはリングまたは他の形状の閉ループを形成する環状の間隙であってもよい。環状の間隙の場合、これは、粉体を排除するために除去することができるが、次いでモデル上に再び付着させることによって印刷体の緩いカバーをもたらし、完成したオブジェクト上の粉体を除去することの審美的影響を最小にする。
【０２６２】
当然のことながら、３Ｄ印刷シーンは、このような複数の中空体を含む場合がある。例えば、シーンは、地面、ブロブマンなどのキャラクタ、および木を含むことができる。地面は通常オープンシェルである。その間、木はその上に乗っており、地面が木の根元を形成している。モデル内の体積の計算に続いて、木の幹は中空のオブジェクトとして識別することができる。したがって、木の下の地面に穴が空いている可能性があり、モデルを下から見た場合にのみ見える。対照的に、ブロブマンのキャラクタは地上の接続ロッドによって支持されている。その結果、キャラクタの胴体が中空のオブジェクトとして識別された場合、元の視点から見て反対側に、任意選択的に任意の接続ロッドからしきい値距離の位置に環状の間隙が含まれる。これにより、胴体から粉末が排出されるだけでなく、環状の間隙によって形成された胴体の取り外し可能な構成要素を所定の位置に固定することによって修復することも可能になる。
【０２６３】
任意選択的に、手続き的規則はオブジェクト自体の機能を使用して、例えば、モデルのテクスチャ色間の境界に隣接するように、および／またはモデル表面の隆起または他の不連続部に隣接するように、穴または間隙の１つまたは複数のエッジの一部またはすべてを設定することにより、穴または環状の間隙の審美的な影響を軽減することができる。
【０２６４】
システムは、３Ｄモデルデータを使用して必要なプリンタ原材料の量を推定し、ユーザがそうすることを約束する前にモデルを印刷するコストを推定する見積もりを提供することができる。
【０２６５】
最後に、図１に戻って参照すると、当然のことながら、装置または装置のシステムは、上記の方法の要約的実施形態または変形例、バージョンおよびオプション、より一般的には本明細書で説明する塗りつぶし技術を実行することができる。
【０２６６】
したがって、例えば、別の要約的実施形態では、娯楽装置（ＰｌａｙＳｔａｔｉｏｎ４（登録商標）１０など）は、塗りつぶしプロセッサ（適切なソフトウェア命令で動作するＧＰＵ  ２０Ｂなど）であって、動作時に、塗りつぶしターゲット色で置き換えられる塗りつぶしソース色を有する第１の要素と、塗りつぶしソース色を有さない第２の要素と、を含む画像を受け取り、階層内の複数のレベルでセルを形成するために、階層的空間分割方式により画像を分割し、第２の要素によって各セルの占有を検出し、第２の要素による占有を有さない任意のセルについて、そのセルの子セルの深度の標高値をそのセルの値よりも１大きく設定し、塗りつぶしは、深度の標高分だけルートセルに向かってレベルをナビゲートし、第２の要素のないノードのみを占有し、それによって塗りつぶし可能な最大の親セルに到達することを示し、第２の要素による占有を有さないセルの塗りつぶしソース色を、塗りつぶしターゲット色で塗りつぶし、それによって受け取った画像を修正する、ように適合された塗りつぶしプロセッサを含む。
【０２６７】
したがって、適切なソフトウェア命令の下で動作する汎用コンピュータは、前述の塗りつぶし方法を実行することができる。
【０２６８】
本明細書に記載の追加の方法および技法はまた、適切なソフトウェア命令の下で動作する装置１０によって実行することができ、そして３Ｄ印刷自体は、３Ｄプリンタ１００と連携して動作する装置によって実行することができる。
【０２６９】
上記の説明から、本明細書に記載された方法は、ソフトウェア命令によって、または専用ハードウェアの包含または置換によって適用されるように適切に適合された従来のハードウェア上で実行することができることが理解される。
【０２７０】
したがって、従来の同等の装置の既存の部分への必要な適応は、フロッピー（登録商標）ディスク、光ディスク、ハードディスク、ＰＲＯＭ、ＲＡＭ、フラッシュメモリ、またはこれらもしくは他の記憶媒体の任意の組み合わせなどの非一時的な機械可読媒体に格納されたプロセッサ実装可能な命令を含むコンピュータプログラム製品の形で実装されてもよいし、あるいは、ＡＳＩＣ（特定用途向け集積回路）またはＦＰＧＡ（フィールドプログラマブルゲートアレイ）または従来の同等の装置を適合させるのに使用するのに適した他の構成可能な回路としてハードウェアで実現されてもよい。別に、そのようなコンピュータプログラムは、イーサネット、無線ネットワーク、インターネット、またはこれらもしくは他のネットワークの任意の組み合わせなどのネットワーク上のデータ信号を介して送信されてもよい。
【図１】
2020015314.tif 000007
【図２Ａ】
2020015314.tif 000008
【図２Ｂ】
2020015314.tif 000009
【図３】
2020015314.tif 000010
【図４】
2020015314.tif 000011
【図５】
2020015314.tif 000012
【図６Ａ】
2020015314.tif 000013
【図６Ｂ】
2020015314.tif 000014
【図７】
2020015314.tif 000015
【図８Ａ】
2020015314.tif 000016
【図８Ｂ】
2020015314.tif 000017
【図９】
2020015314.tif 000018
【図１０Ａ】
2020015314.tif 000019
【図１０Ｂ】
2020015314.tif 000020
【図１０Ｃ】
2020015314.tif 000021
【図１０Ｄ】
2020015314.tif 000022
【図１０Ｅ】
2020015314.tif 000023
【図１１】
2020015314.tif 000024
【図１２】
2020015314.tif 000025
【図１３Ａ】
2020015314.tif 000026
【図１３Ｂ】
2020015314.tif 000027
【図１３Ｃ】
2020015314.tif 000028
【図１４】
2020015314.tif 000029
【図１５】
2020015314.tif 000030
【図１６】
2020015314.tif 000031
【図１７Ａ】
2020015314.tif 000032
【図１７Ｂ】
2020015314.tif 000033
【図１８Ａ】
2020015314.tif 000034
【図１８Ｂ】
2020015314.tif 000035
【図１８Ｃ】
2020015314.tif 000036
【図１９Ａ】
2020015314.tif 000037
【図１９Ｂ】
2020015314.tif 000038
【図１９Ｃ】
2020015314.tif 000039
【図１９Ｄ】
2020015314.tif 000040
【図２０】
2020015314.tif 000041
【図２１】
2020015314.tif 000042
【図２２】
2020015314.tif 000043
【外国語明細書】
2020015314000001.pdf