"多視点画像を生成する方法であり、多視点シルエットエッジを用いて放射輝度の関数の不連続性を検出する段階を備える、方法。シェーディング点とカメララインとの間の分析可視性を計算する段階をさらに備える、請求項1に記載の方法。多視点シルエットエッジを用いて再構成を行う段階をさらに備え、ピクセルは複数の領域に分割される、請求項2に記載の方法。前記分析可視性に基づき逆追跡サンプルを挿入する段階をさらに備える、請求項2または3に記載の方法。サンプルを含まない領域に対して新たな光線を照射する段階をさらに備える、請求項3または4に記載の方法。前記カメラライン上の可視性セグメントに関するシェーディング計算を共有する段階をさらに備える、請求項2から5のいずれか1項に記載の方法。前記シェーディング計算を複数の構成部分へ分割し、異なる頻度で前記複数の構成部分を評価する段階をさらに備える、請求項6に記載の方法。逆追跡トライアングル内の多視点シルエットエッジを検出する段階をさらに備える、請求項1から7のいずれか1項に記載の方法。交点から見て後ろ向きのトライアングルのみを処理することにより、シルエットエッジを見つけ出す段階をさらに備える、請求項1から8のいずれか1項に記載の方法。逆追跡トライアングル平面と交差するトライアングルのみをテストすることによりシルエットエッジを見つけ出す段階をさらに備える、請求項1から9のいずれか1項に記載の方法。コンピュータに、多視点シルエットエッジを用いて放射輝度の関数の不連続性を検出することにより多視点画像を生成する手順を実行させる、コンピュータプログラム。シェーディング点とカメララインとの間の分析可視性を計算する手順をさらにコンピュータに実行させる、請求項11に記載のコンピュータプログラム。多視点シルエットエッジを用いて再構成を行う手順をさらにコンピュータに実行させ、ピクセルは複数の領域に分割される、請求項12に記載のコンピュータプログラム。前記分析可視性に基づき逆追跡サンプルを挿入する手順をさらにコンピュータに実行させる、請求項12または13に記載のコンピュータプログラム。サンプルを含まない領域に対して新たな光線を照射する手順をさらにコンピュータに実行させる、請求項13または14に記載のコンピュータプログラム。前記カメラライン上の可視性セグメントに関するシェーディング計算を共有し、異なる頻度frequencyでシェーディングを行う手順をさらにコンピュータに実行させる、請求項12から15のいずれか1項に記載のコンピュータプログラム。逆追跡トライアングル内の多視点シルエットエッジを検出する手順をさらにコンピュータに実行させる、請求項11から16のいずれか1項に記載のコンピュータプログラム。交点から見て後ろ向きのトライアングルのみを処理することにより、シルエットエッジを見つけ出す手順をさらにコンピュータに実行させる、請求項11から17のいずれか1項に記載のコンピュータプログラム。逆追跡トライアングル平面と交差するトライアングルのみをテストすることによりシルエットエッジを見つけ出す手順をさらにコンピュータに実行させる、請求項11から18のいずれか1項に記載のコンピュータプログラム。エッジを共有する後ろ向きのトライアングルを見つけ出し、シルエットエッジを見つけ出す際に、共有された前記エッジを無視する手順をさらにコンピュータに実行させる、請求項11から19のいずれか1項に記載のコンピュータプログラム。グラフィックを処理する装置であり、多視点シルエットエッジを用いて放射輝度の関数の不連続性を検出することにより多視点画像を生成するプロセッサと、前記プロセッサと関連付けられた記憶部とを備える、装置。前記プロセッサは、シェーディング点とカメララインとの間の分析可視性を計算する、請求項21に記載の装置。前記プロセッサは、多視点シルエットエッジを用いて再構成を行い、ピクセルは複数の領域に分割される、請求項22に記載の装置。前記プロセッサは、前記分析可視性に基づき逆追跡サンプルを挿入する、請求項22または23に記載の装置。前記プロセッサは、サンプルを含まない領域に対して新たな光線を照射する、請求項23または24に記載の装置。前記プロセッサは、前記カメラライン上の可視性セグメントに関するシェーディング計算を共有し、異なる頻度でシェーディングを行う、請求項22から25のいずれか1項に記載の装置。前記プロセッサは、逆追跡トライアングル内の多視点シルエットエッジを検出する、請求項21から26のいずれか1項に記載の装置。前記プロセッサは、交点から見て後ろ向きのトライアングルのみを処理することにより、シルエットエッジを見つけ出す、請求項21から27のいずれか1項に記載の装置。前記プロセッサは、逆追跡トライアングル平面と交差するトライアングルのみをテストすることによりシルエットエッジを見つけ出す、請求項21から28のいずれか1項に記載の装置。前記プロセッサは、エッジを共有する後ろ向きのトライアングルを見つけ出し、シルエットエッジを見つけ出す際に、共有された前記エッジを無視する、請求項21から29のいずれか1項に記載の装置。光線追跡を用いて効率的に多視点画像を生成する特別なアルゴリズムを説明する。シーン内の幾何学的なエッジによって生成される放射輝度の関数の明確な不連続性を検出するのに用いる、多視点シルエットエッジを導入する。さらに、シェーディング点とカメララインとの間の分析可視性を計算すること、およびシェーディング計算を共有することにより、シェーダコヒーレンスを活用する。サンプリングする空間は、x,y,vで示される3次元空間である。ここでvはカメララインに沿った視点パラメータであり、x,yは、画像平面パラメータである。図1はこのことを示す。光照射野Lx,y,vをサンプリングし再構成することにより、裸眼マルチ立体automultiscopicディスプレイ上で当該光照射野の高品質な表示を行うことを目的とする。そのようなディスプレイは、概念的に格子状に配置されたピクセルを有し、各ピクセルは、カメララインに沿った異なる位置viに向けて放射されるn個の独立した放射輝度値で同時に表示を行うことができる。それらの視点は小さな範囲内で可視性であり、通常は、ディスプレイの光学特性に依存して、視点の重なりがいくらかある。視点の数が少ないので例えば、8~64、ディスプレイのvに沿った帯域幅は、非常に限られたものとなる。視点間のエイリアスを避けるべく、再構成工程において、Lを視点依存性フィルタと統合し、n個の独立した画像Liを計算する。1ここでgiは、視点iのフィルタカーネルである。このことにより効果的に、観察者が動くときに知覚される、焦点平面の前方および後方の物体がぼけるストロボ効果をなくすことが出来る。なお通常通り、最終的なピクセル値を求める際、Liは空間アンチエイリアス処理フィルタとも統合される。Lのランダムサンプリングは多くの演算量を要する。サンプルごとに、シーンとの交点を見つけ出すべく順光線がvからx,yを通って送り出され、シェーディングが評価される。Lの不連続性は、2つのことに起因し得る。それらは、シェーディングの急激な変化、およびソーン内の幾何学的なエッジである。多視点の状況に特有のシェーディングコヒーレンスを活用することにより少ない演算量でサンプルを生成する、多視点光線追跡に用いられる特別なアルゴリズムを提案する。順光線を用いた幾何学的なシルエットエッジのランダムなサンプリングに代わり、逆追跡により交点からカメララインへ後ろ向きにトライアングルを追跡することにより、それらエッジを分析検出する。図9のブロック102を参照されたい。このデータを符号化する多視点シルエットエッジと呼ばれる概念を導入する。シェーダは、それに関する情報が知られていない未知のものであるので、シェーディングの不連続性に関しては、引き続き適応サンプリングを用いる。幾何学的なエッジを分析検出するので、副次的な効果として、シェーディング点とカメララインとの間の可視性の程度を正確に知ることも出来る。よって、さらに光線追跡を必要とすることなく、可視性であることが知られているセグメントに沿って、サンプルを追加的に任意の数だけ挿入することが出来る。例えば入射する放射輝度のサンプリングなど視点に依存する計算の全てを再利用することが出来るので、これら追加的な逆追跡サンプルのシェーディングは、演算量が比較的少なくて済む。再構成工程において、格納されたサンプルおよびエッジに関する情報に基づいて、連続的な関数が作成される。従来の方法ではサンプルごとの勾配を計算することによりエッジを検出するという手間を要していたが、本発明では、幾何学的なシルエットエッジの正確な位置を知ることが出来る。いくつかの実施形態においては、これにより、再構成の品質をかなり向上させることが出来、よって、統合後の最終的な成果物の品質も向上させることが出来る。サンプルがどのように生成され、多視点シルエットがどのように計算され、シェーディング計算がどのように再利用されるかについて説明する。図1に示すような順光線が表面に当たると、通常、シェーディングはx,y,v座標で表されるサンプルとして計算され、格納される。カメララインの一部に関しつまり、交点を見ることの出来るvの値に関し、全てのシェーディングの視点に依存しない部分を、それら全てのvの値に再利用することが出来る。このコヒーレンスを活用する直接的な方法は順光線の交点から後方へ、カメララインに向かって光線の組を追跡する方法である。しかし、このことによって、異なるエリア間でサンプル密度にばらつきが生じ得、再構成の際に対処を取らない限り、幾何学的なエッジの僅かなずれが起こり得る。図7を参照されたい。本明細書で説明するアルゴリズムの逆追跡工程は、交点において順光線が物体に当たった後に開始される。逆追跡トライアングルは、図1に示すように当該交点とカメララインとによって形成される。このことの目的は、カメララインのどの部分が交点から見て可視性であるかを計算することである。本実施形態ではこのことを、平面におけるシャドウボリュームレンダリングshadowvolumerenderingと最後の部分が同様であるアプローチを用いて分析的に行う。ここで取り上げたシーンにおけるトライアングルの幾何学の全ては、軸に並行な直方体axis-alignedboundingboxesAABBを用いたboundingvolumehierarchyBVHで格納される。最初に、BVHを検討し、AABBについて、当該逆追跡トライアングルとの重複がないか確認する。このことを最適化トライアングル/AABB重複テストを用いて行う。概念として、トライアングルのエッジが逆追跡トライアングルと交差する場合、当該トライアングルの逆追跡平面と交差する全てのエッジが、当該エッジの2つの頂点に関する指標から作成されるハッシュキーを有するハッシュ表へ挿入される。シルエットエッジは本明細書において、トライアングルの逆追跡平面と交差するエッジとして定義し、さらに、トライアングルは交点から見て後ろ向きであり、当該エッジは他の後ろ向きのトライアングルとさらに繋がっていない。つまり、2次元多様体の開かれた、および閉じられた表面の両方bothopenandclosed2-manifoldsurfacesを扱うことが出来る。可視性を決定づけるのは交点から見たシルエットエッジのみであるので、これらのシルエットエッジを迅速に検出することが所望される。本願発明では、シルエットエッジを、いくつかの最適化を用いて見つけ出す。図9のブロック104を参照されたい。最初に、交点から見て後ろ向きのトライアングルのみを処理する。次に、テスト対象のトライアングルは逆追跡トライアングルの平面に交差してなければならなく、また逆追跡トライアングルの平面はテスト対象のトライアングルに交差していなければならない。次に、ハッシュ内において重複がある場合、エッジを共有する2つの後ろ向きのトライアングルに基づいて、その共有される当該エッジが挿入されたということである。トライアングルは両方とも後ろ向きであるので、共有されたエッジはシルエットエッジとなり得ず、よって両方のエントリがハッシュ表から削除される。さらに、1つの頂点が交点の後方にあり、少なくとも1つの頂点が交点の前方にあるトライアングルを検出する。極稀にしか起こらないケースではあるが、当該トライアングルの逆追跡トライアングルに対するクリッピング処理を行い、その後、エッジを挿入する。全ての処理が完了すると、可能性のある全てのシルエットエッジがハッシュ表に含まれる。図2は、交点IPから後方へ、カメララインに向かう分析可視性の計算をどのように行うかを図示する。オクルーダは、図示を簡潔にするべく、2次元で示す。よって3次元方向に存在するトライアングルは、2次元において線として示され、シルエットエッジは、シルエット点黒点で示される交点を向く線は点線で示す。図2の左側の図面では、最初に逆追跡トライアングルに基づいてカリングを行えない物体のトライアングルが処理されている。ハッシュ表を用い、残りの線の上のシルエット点を迅速に見つけ出す。図2の中央の図面では、シルエット点の屈曲を用い、1か、または-1の重み付けを行う。図2の右側の図面では、左から右にかけて重みの加減を行い、閉塞したoccluded部分は加減の結果、重みがゼロより大きくなるセグメントである。カメラライン上の黒色のセグメントSが閉塞した部分である。全てのシルエットエッジを見つけ出すと、シルエットエッジの、逆追跡トライアングルの平面との交点を、カメララインに沿って左から右へ処理する。図9のブロック106を参照されたい。トライアングルが外部から始まり、バック追跡トライアングルの左側にあるシルエットエッジの数となるようカウンタを初期化する。屈曲の順番に従い、それぞれの点は1か、または-1の重みを有する図2において小さな矢印で示す。カメララインに沿って重みの合計を計算し、合計がゼロより大きい場合、カメララインは閉塞した状態である。そうでない場合、交点から見て可視性である。最後に、外側のシルエットポイント、つまり図2の黒色のセグメントSの端点のみを残す。なお、カメラライン上の少なくとも1点から交点が可視性であるので、カメララインの全体が閉塞した状態は起こらない。多視点シルエットは、シーン内の幾何学的なエッジの代表的なサブセットを符号化する。上述した逆追跡工程において、外側のシルエットポイントの数を特定した。それらの各点は、カメラライン上の少なくともいずれかのvおよび画像平面におけるyに関するシルエットであるトライアングルのエッジから生成される。トライアングルのエッジは画像平面に投射されると、特定のvに関する線となる。三次元のx,y,v空間において、これらの線は、双線形パッチである表面を描く。これらのパッチを、多視点シルエットエッジと呼ぶことにするが、パッチという語も同じ意味で用いることもある。図3は幾何学的な例を示し、ここで、多視点シルエットエッジは4つの点pi、i∈{0,1,2,3}により定められる。これら4つの点は、トライアングルエッジの端点をカメララインの端点へ向けて投射した際、画像平面と交わる点として得られる。シルエットエッジの端点がカメララインの端点に向けて投射されると、4つの点p0、p1、p2、p3が得られる。これら4つの点により、双線形パッチである多視点シルエットエッジが定められる。本願発明の再構成アルゴリズムでは、多視点シルエットエッジを用いて、幾何学的なエッジをより良好に表現する。なお焦点平面は、図3における画像平面と同一である。多視点シルエットエッジのそれぞれは、サンプルドメインを、シーン内の幾何学的な不連続性を表す、重なりをもたない領域に局所的に分割する。再構成工程において、この情報を用い、本質的にエッジを考慮した再構成フィルタを用いることにより、実質的に品質を向上させる。以下では、多視点シルエットをどのように処理し、少ない演算量で、近似するエッジの表現を構成するかについて説明する。図9のブロック108を参照されたい。最初に、対象となるのは、カメララインから見て可視性であるシルエットのみである。各パッチにおいて少なくとも1点は可視性であり逆追跡段階で見つけ出される外側のシルエット点、他の部分は、他のパッチによって閉塞されているということが十分にあり得る。一般的に、各パッチの限られた領域のみがカメララインから見て可視性である。第1の最適化として、可能であれば、v次元の多視点シルエットエッジの程度を低下させる。シルエットエッジを共有するトライアングルの2つの平面を用いて、エッジがカメララインから見て内側のシルエットではなく真のシルエットであるvの範囲を求める。これらの平面は、カメララインに対してテストされる交点であり、それにしたがって、カメララインに対し、クリッピング処理が行われる。図4は、1つの一般的なケースと、2つの特別なケースを示す。多視点シルエットに対し、v次元でクリッピング処理が行われる。シルエットエッジに入射する平面を用い、v軸に沿った多視点シルエットエッジの程度を制限する。図4において、多視点シルエットエッジに対し、v軸上の間隔Iまでクリッピング処理が行われる。これら3つの全てのケースにおいて、カメララインのうち、エッジが実際にシルエットであり、交点が少なくとも1点から見て可視性である部分のみを残す。多視点シルエットのうち、カメララインから見て可視性であることが分かっている部分のみつまり、順光線が生じる部分のみを残す。次に、次元に関する問題は、y次元をいわゆるyバケットへと離散化させるdiscretizingことにより検討しないでよいものとする。各バケットは、座標yiを中心とする。通常、1つの走査線あたり1つか、またはいくつかのバケットを用いれば十分であるが、複雑な幾何学を有するシーンにおいては、さらに多くのものを用いてもよい。双線形パッチとして多視点シルエットを扱う代わりに、多視点シルエットを、yバケットのx,v平面における線分として残す。このことにより、全てのクリッピング処理およびその他の処理を2次元上で行うので、アルゴリズムを大幅に単純化することが出来る。各バケットに関し、2次元のkDツリーを用いて線分を維持するhold。新たなシルエットは挿入されたときは常に、当該バケット内の既存のエッジに対してクリッピング処理が行われる。この目的において、奥行き値およびエッジの屈曲を考慮すること、つまり、左側を向くシルエットであるか右側を向くシルエットであるかを検討することが重要である。kDツリーに新たなエッジが挿入されると、カメララインンにより近いエッジに対しクリッピング処理が行われ、より遠いエッジのクリッピング処理を行う。最も前面にあるエッジの屈曲により、クリッピング処理が行われたエッジのうちどのセグメントを残すかどうかが決定される。性能面での理由により、いくつかの実施形態において、パッチが重なる全てのバケットではなく、現在のyバケット内の多視点シルエットのデータのみを挿入する。代替的に、他の交点からの逆追跡を活用して、同じ多視点シルエットエッジを繰り返して見つけ出し、当該多視点シルエットエッジを他のバケットに挿入する。このことは直観的な処理には見えないかもしれないが、いくつかのケースにおいては、より良好な性能で同等の品質を得ることが出来る。計算の複雑性を軽減するべく、パッチごとの全ての設定つまり、端点piおよび他の必要な情報が一度のみ計算され、ハッシュマップに格納され、エッジを構成するトライアングルid:sに適合させられるkeyedon。最後に、多視点シルエットを見つけ出すべく、いくつかの実施形態において、y方向のジッタリングを行わず、yバケットの中心を通る順光線のみを照射する。このことにより、稀にではあるが視覚的なアーチファクトを引き起こし得る、順光線のy座標に沿ってのみ可視性であるが、yバケットの中心からのものではないパッチを得ることがなくなる。本実施例での目的は、多視点シルエットエッジを全て表現するということではなく、代わりに、誤差測定および再構成をサポートすべく、エッジの代表的な組を迅速に構成することである。幾何学的なエッジがないドメインの領域においては、シェーダの不連続性の検出にコントラストの測定値を用いる通常の多次元適応サンプリングMDASを自動的に用いるようなアルゴリズムとなる。Hachisuka,T.,Jarosz,W.,Weistroffer,R.,K.Dale,G.H.Zwicker,M.,andJensen,H.W.2008,MultidimensionalAdaptiveSamplingandReconstructionforRayTracing,ACMTransactionsonGraphics,27,3,33.1-33.10を参照されたい。分析逆追跡によりカメラライン上の可視セグメントの組を特定すると、逆追跡サンプルの組がそれらセグメント内で生成され、これらサンプルが、全てのサンプルを有する3次元のkDツリーへ挿入される。逆追跡サンプルは、カメララインv上の点から見た、順光線が当たる交点から生じる放射である。同じ交点から生成された逆追跡サンプルのシューディング計算を再利用することにより、シェーダコヒーレンスを活用する。図9のブロック110を参照されたい。順光線のそれぞれが、シェーディングを必要とする交点に当たる。最も単純化した実施例において、シェーダを視点に依存する部分と視点に依存しない部分とに分割する。逆追跡サンプルの全てに関し、双方向反射率分布係数BRDFの視点に依存する部分の評価を行う。このことには、例えば、鏡面ハイライト、反射および屈折などが含まれる。BRDFの視点に依存しない部分は、1つの順光線ごとに一度のみ評価される。この例としては、放射照度の収集irradiancegathering、可視性の計算例えば影など、および拡散照明などが挙げられる。このことだけでも、速度が格段に速くなる。また、ミップマップテクスチャフィルタリングまたは異方性テクスチャフィルタリングから抽出した色は、視点に依存する。表面上の点の方を見ると、テクスチャルックアップはカメラライン上の視点に依存して、異なるフットプリントが得られる。これまでのところ、本願発明のシェーディング最適化は正確なものである。近似シェーダ再利用方法により、異なる頻度frequenciesでのシェーディングが可能となり、また当該方法に、任意のカメラ位置でのシェーディングサンプルを得るべく、補間または最近傍探索を用いてもよい。例えば、BRDFの鏡面反射成分は急速に変わり得るので、シェーディングサンプルを忠実に再構成するには、密にサンプリングを行う必要がある。しかし、いくつかのケースにおいては、低い頻度で鏡面反射成分のサンプリングを行い、その後それらサンプル間で補間を行ってもよい。同様に、テクスチャルックアップが変わる頻度はさらに低いことが多く、よりまばらなサンプリングでもよい。図5は、シェーディングの再利用の一実施形態を示す。図中左に進む順光線は交点において球形の物体に当たる。分析可視性は、本願発明のアルゴリズムを用いて計算する。交点からは、垂直方向に延びるカメララインの、太線でない部分のみが可視性である。5つの新たな逆追跡サンプルが生成される右側に進む光線。拡散シェーディング計算は何らかのテクスチャルックアップを伴わない場合、6つの全ての光線に関し一度行うことが出来、その後、全ての光線に再利用することが出来る。右に示す文字は、一実施形態における、鏡面反射シェーディング計算の頻度を視覚的にわかるようにするものである。sが付された光線の全てについては、鏡面反射シェーディングの計算が最初から行われ、他のiが付された光線は、隣接する光線からの補間が行われる。先行する工程において可視性が分析によって判断されているので、逆追跡においては、可視性の計算は行われない。シェーディングの再利用に関する他の実施形態において、カメララインvに沿った、ランダムであり、かつ逆追跡サンプルよりもまばらな位置においてシェーディングが行われる。その後、その結果得られるシェーディング値を用いて、逆追跡サンプルに対す直線的な補間が行われる。逆追跡サンプルが最も外側のシェーディングサンプルのカメララインパラメータvより上方または下方に位置する場合、これら逆追跡サンプルに割り当てられた、シェーディングされた色の値に対して、最も近いシェーディングサンプルへのクランピングが行われる。同様に、テクスチャルックアップは、シェーディングサンプルよりもさらにまばらに行うことが出来る。シェーディングサンプルおよび逆追跡サンプルに関して説明した補間およびクランピングのルールに従って、テクスチャ色の値をシェーディングサンプルに割り当てる。1つの順光線あたりの逆追跡サンプルの数は、変数パラメータであり、シェーダによって調整することが出来る。しかし一般的に本願発明では、逆追跡サンプルの数を、分析逆追跡工程で見つけ出されるカメララインの可視セグメントの長さの合計に比例するものとする。さらに、逆追跡サンプルのカメラライン上でのジッタリングを行い、順光線が生じるサブセグメントに関し、対応する逆追跡サンプルが削除される。代替的に、順光線は、誤差測定値が最も大きいMDASにより生成されたものであり重要度が高いので、そのままの位置で用いられる。一般的に逆追跡サンプルは、MDASにより生成される完全なサンプルよりも重要性は低い。よって、逆追跡サンプルの数を必要以上に大きくしても意味がない。なぜなら、kDツリールックアップの速度が、実質的に遅くなるからである。しかし、演算量の多いシェーダに関しては、シェーダの計算を再利用し、シェーダの部分をより低い頻度で評価することの利点は大きく、このことは特に視点の数が大きくなると顕著になる。次に、本願発明の再構成アルゴリズムを説明する。図9のブロック112を参照されたい。サンプルは全てが3次元であり、つまり、x,y,v座標を持つ。さらに、それぞれのサンプルは色およびz座標といった何らかの補助的なデータを有する。このサンプルセットから、n個の異なる画像を再構成する。ここでnは対象となる表示に依存して決まる。例えば、立体表示ではn=2である。図6に示すように、本願発明のアルゴリズムにおけるサンプル生成工程の後、サンプルの3次元空間x,y,vが得られる。ここでvは視点の次元、つまり、カメララインに沿ったパラメータである。このサンプルセットから、n個の画像が再構成される。この場合、n=9であるが、3つの画像のみを右側に示す。v軸に沿った任意のフィルタカーネルgiを用いることが出来る。図6の下部に、9つの画像すべてを示す。第1の工程は、MDASの再構成アルゴリズムと同一である。簡単に説明すると、最初に、kDツリーが、各ノードが1つのサンプルを有するようになるまで細分化される。各サンプルが処理されると、最も近くのサンプルが見つけ出され、勾配が計算され、最終的に構造テンソルがサンプルごとに計算される。この処理の後、ピクセルの中間、つまり固定されたx,y座標において、v次元内のvラインと呼ばれる線に沿って統合を行うことにより、ピクセルの最終的な色が見つけ出される。多視点の状況において、特定の視点に関しては特定の範囲のvのみを処理する必要がある図6を参照。その後MDASによって、vラインと重なるkDツリーノードを見つけ出し、各kDツリーノードのピクセル色への影響を蓄積する。この影響は、kDツリーノードの中間において、vライン上の統合点x,yを設定し、隣接するサンプルの統合点への色に関する影響を計算することにより、計算される。MDASではこのことを、ユークリッド空間theEuclideansenseにおけるノードの中心に最も近いkDツリーのs個のサンプルを見つけ出し、近似する、最も近く隣接するサンプルの大体の組を得ることによって行い、この組は、各ノードに格納される。続いて、構造テンソルを用いてこれらのサンプルに関しマハラノビス距離を計算する。統合点の色は、最も近いサンプルの色となる。MDASによると、kDツリーが真のエッジの忠実な表現を有する場合、高品質のエッジを再構成できる。しかし、本願発明の演算量が少なくて済む逆追跡サンプルが挿入されると、多くの場合において、このことは正しくはない。図7はこのことの一例を示しており、逆追跡による、不均一なサンプル密度を示す。図7の一番左の図面は、シーンのxz平面内での走査線を示しており、2つの水平な線Rには焦点があっており、水平な線Bは背景である。各順光線について、光線の組が、交点からカメララインまで追跡される。理解いただけるように、線Bに当たる順光線については、逆光線の一部分のみがカメララインに到達する。中央の図面は、適当な数の順光線および対応する逆光線の追跡が行われた後のエピポーラ平面を示す。エピポーラ平面は、特定のyに関するxv空間である。線Rからのサンプルは四角Qとして示されており、背景Bからのサンプルは、黒点Dとして示されている。なお、サンプル密度は、領域Rにおいて著しく低い。最後に右側の図面において、エピポーラ平面からの拡大された視点が示されている。シェーディングされた背景は、真の幾何学的なエッジの位置を示しているが、サンプリング密度が異なるので、再構成されたエッジ垂直線Sは、より密度の低いサンプル領域Mへとはみ出すこともあり得、よって、真のエッジTとは異なる場所に配置してもよい。これらの図面は例示的なものであり、実際のサンプル分布を示すものではない。よって、このことを解決すべく、本願発明の再構成技術では多視点シルエットが用いられ、本願発明のアルゴリズムが生成するタイプのサンプルの組の再構成品質を向上させる。次に、vラインに重なる各kDツリーノードを処理する際の、ピクセル領域上への統合を実質的にどのように向上させるかを説明する。特定のkDツリーノードおよびピクセルxp,ypに関し、において統合点も作成する。概念としては、次に、多視点シルエットデータ構造において、x方向に、統合点に最も近い2つのエッジを探す。このことは以下のように行う。双線形パッチである多視点シルエットエッジ図3の、平面y=ypとの交点は、構成によりxv空間において直線となる。次にこの線形の方程式を用いて、における多視点シルエットのx座標を計算する。このことを最も近い多視点シルエットの全てに関して行い、x<xpである最も近いエッジ、およびx≧xpである最も近いエッジは残す。この状況を図8の左側に示す。図8の左側において、エピポーラ平面xvで見られる、サンプルのkDツリーからのノード四角Gを示す。×印は、このkDツリーノードに関して選択された統合線上の統合点であり、黒色の丸はサンプルである。において、本願発明のアルゴリズムは、xにおいて2つの最も近い多視点シルエット線EおよびFを探す。最も近い多視点シルエットは、ピクセル中心のy値に関し評価される。最も近い多視点シルエットエッジが見つけ出されると、における当該多視点シルエットエッジから新たな線形の方程式を作成することにより、それら最も近い多視点シルエットエッジを画像平面x,yに投射する。その後これらの線は、ピクセルの範囲extentに対してクリッピング処理が行われる。2つのエッジがあるので、このことによって図8の右側に示すような4つの異なる構成となる。ここでピクセルは1~4個の領域に分割される。その後、各領域の色が、当該各領域内のマハラノビス距離で測って最も近いサンプルを用いて計算される。同時に、これらのピクセル領域の面積ai、i∈{1,2,3,4}が計算される。ここでこれらの面積の合計は、ピクセルの面積と等しい。次に、ノードの中心点の周りの、ユークリッド空間において最も近いs個のサンプルが直接ノードからフェッチされる。その後、最も近いサンプルは異なる領域に分類され、ピクセルに重なる各領域の色ciが、当該領域内のサンプルのみを用いて、マハラノビス距離に基づいて選択される。その後、kDツリーノードの最終的な色の影響は、となる。ここで、aiはゼロであってよい。結果として、kDツリーノードの、ピクセルに重なるエッジが1~2個ある場合、本願発明のアルゴリズムは、アンチエイリアス処理された高品質のエッジを画像内で生成する。なお、エッジがピクセルを2つの部分へと分割する場合図8の右上の例、a3=a4=0となる。いくつかの実施形態において、ユーザは、3つ以上の分割エッジを用いることを所望するかもしれない。なお、いくつかの非常に稀なケースにおいては、1以上の領域にサンプルが1つもないかもしれない。この場合、再構成された色は単純に不正確なものとなり、このことに対する解決策として、これらの領域に対し新たな光線を照射し、再構成において当該サンプルの色を用いることである。kDツリーの再構築、勾配および構造テンソルの再計算などを避けるべく、新たなサンプルは、用いられた後、単純に破棄される。y次元は、走査線ごとに、少ない数のyバケットの中心へと離散化させられるdiscretized。結果的に、このことによってy方向のエイリアシングが起こる可能性が高いこの影響を軽減するべく、再構成の間、ノードおよび走査線ごとに、ピクセル内の統合点のy値のジッタリングを行う。ジッタリングされた統合点に最も近いyバケットを局所的な幾何学の代表として用いる。yバケットの数が十分に大きければ、このことによって、ノイズを含むエイリアシングをなくすことが出来る。図10に示すコンピュータシステム130は、ハードドライブ134および取り外し可能媒体136を含んでよい。取り外し可能媒体136は、バス104を介し、チップセットのコアロジック110と結合される。キーボードおよびマウス120、または従来の他のコンポーネントが、バス108を介し、チップセットのコアロジックに結合されてよい。一実施形態においてコアロジックは、バス105を介してグラフィックプロセッサ112に、およびメインまたはホストプロセッサ100に結合されてよい。グラフィックプロセッサ112も、バス106を介してフレームバッファ114に結合されてよい。フレームバッファ114は、バス107を介してディスプレイスクリーン118に結合されてよい。一実施形態において、グラフィックプロセッサ112は単一命令多重データSIMDアーキテクチャを用いるマルチスレッド、マルチコアパラレルプロセッサであってよい。ソフトウェアを用いた実施例において、関連するコードが、メインメモリ132またはグラフィックプロセッサ内の任意の利用可能なメモリを含む、任意の適した半導体、磁気または光メモリに格納されてもよい。よって、図9の一連の段階を実行するコードは、一実施形態において、メモリ132またはグラフィックプロセッサ112などの機械可読またはコンピュータ可読媒体に格納されてよく、また一実施形態において、プロセッサ100またはグラフィックプロセッサ112によって実行されてよい。図9は、フローチャートである。いくつかの実施形態において、本フローチャートに示す一連の段階をハードウェア、ソフトウェアまたはファームウェアで実装することが出来る。ソフトウェアを用いた実施形態においては、半導体メモリ、磁気メモリまたは光メモリなどの非一時的なコンピュータ可読媒体を用いて命令を格納し、図9に示す一連の段階を実施するようプロセッサが命令を実行してもよい。本明細書で説明するグラフィック処理技術は、様々なハードウェアアーキテクチャにより実装することも出来る。例えば、グラフィック機能をチップセット内で実装してもよい。代替的に、独立したグラフィックプロセッサを用いてもよい。さらに他の実施形態において、グラフィック機能をマルチコアプロセッサなどの汎用プロセッサで実装してもよい。本明細書を通して一実施形態または実施形態といった用語を用いた場合、対応する実施形態に関連して説明される特定の特徴、構造または特性が本願発明に包含される少なくとも1つの実施形態に含まれることを意味する。よって、一実施形態または実施形態といった用語を用いた場合、常に同じ実施形態を指すものとは限らない。さらに、特定の特徴、構造または特性は、示される特定の実施形態以外の他の適した形態で用いてもよく、それらの全ての形態が、本明細書の請求項に包含される。本願発明を、限られた数の実施形態に関して説明してきたが、当業者であれば様々な修正例および変形例を考え付くであろう。以下の請求項は、そのような修正例および変形例を本願発明の思想および態様に含まれるものとして網羅する。"