(57)【特許請求の範囲】
【請求項１】
仮想空間内の点群を示す点群データに基づいて、複数のポリゴンを含むポリゴンモデルを生成するポリゴンモデル生成部と、
前記点群の分布に基づいて、当該点群に属する点に対応付けられる点密度の値を決定する点密度値決定部と、
前記ポリゴンを構成する辺の長さが、当該辺の端点に対応付けられる前記点密度の値に応じた閾値を超える場合に、当該ポリゴンを前記ポリゴンモデルから削除する長辺ポリゴン削除部と、
を含むことを特徴とするポリゴンモデル生成装置。
【請求項２】
前記仮想空間内における前記ポリゴンモデルを望む第１位置と前記点群に属する点の位置である第２位置とを両端とする線分と交差する前記ポリゴンである交差ポリゴンを特定する交差ポリゴン特定部と、
前記交差ポリゴンを前記ポリゴンモデルから削除する交差ポリゴン削除部と、をさらに含む、
ことを特徴とする請求項１に記載のポリゴンモデル生成装置。
【請求項３】
実空間において実カメラが被写体を撮影した画像を取得する画像取得部と、
前記画像に基づいて、属する点がそれぞれ前記実空間内における前記被写体上の点に相当する前記点群データを生成する点群データ生成部と、
前記被写体を撮影した際の前記実カメラの前記実空間内における位置に相当する、前記仮想空間内の位置を特定する対応カメラ位置特定部と、をさらに含み、
前記交差ポリゴン特定部は、前記対応カメラ位置特定部で特定される位置を前記第１位置として前記交差ポリゴンを特定する、
ことを特徴とする請求項２に記載のポリゴンモデル生成装置。
【請求項４】
前記交差ポリゴン特定部は、対応付けられる前記点密度の値が所定値よりも大きな点の少なくとも一部のそれぞれのみについて、当該点の位置を前記第２位置として前記交差ポリゴンを特定する、
ことを特徴とする請求項２又は３に記載のポリゴンモデル生成装置。
【請求項５】
前記仮想空間内に設定される１又は複数の仮想カメラのいずれにおいても不可視な前記ポリゴンである不可視ポリゴンを特定する不可視ポリゴン特定部と、
前記不可視ポリゴンを前記ポリゴンモデルから削除する不可視ポリゴン削除部と、をさらに含む、
ことを特徴とする請求項１から４のいずれか一項に記載のポリゴンモデル生成装置。
【請求項６】
仮想空間内の点群を示す点群データに基づいて、複数のポリゴンを含むポリゴンモデルを生成するポリゴンモデル生成ステップと、
前記点群の分布に基づいて、当該点群に属する点に対応付けられる点密度の値を決定する点密度値決定ステップと、
前記ポリゴンを構成する辺の長さが、当該辺の端点に対応付けられる前記点密度の値に応じた閾値を超える場合に、当該ポリゴンを前記ポリゴンモデルから削除する長辺ポリゴン削除ステップと、
を含むことを特徴とするポリゴンモデル生成方法。
【請求項７】
仮想空間内の点群を示す点群データに基づいて、複数のポリゴンを含むポリゴンモデルを生成するポリゴンモデル生成手順、
前記点群の分布に基づいて、当該点群に属する点に対応付けられる点密度の値を決定する点密度値決定手順、
前記ポリゴンを構成する辺の長さが、当該辺の端点に対応付けられる前記点密度の値に応じた閾値を超える場合に、当該ポリゴンを前記ポリゴンモデルから削除する長辺ポリゴン削除手順、
をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ポリゴンモデル生成装置、ポリゴンモデル生成方法及びプログラムに関する。
【背景技術】
【０００２】
点群の輪郭に沿ったポリゴンモデルを生成する技術が存在する。このような技術の一例として、特許文献１には、実空間に配置されたオブジェクトを撮影することで取得される深さ情報を含む画像から仮想空間内に配置されるポリゴンモデルを生成する技術が記載されている。【０００３】
この技術では、まず、三角形のポリゴンを含むイニシャルスカルプチャが仮想空間内に生成される。そして取得された画像内の画素及び当該画素の深さとの組合せに対応付けられる仮想空間内の点（データポイント）が特定される。そして特定されたデータポイントに対して原点からレイキャストが実行され、レイキャストされた光線とポリゴンとの交点が特定される。そして特定された交点とデータポイントとの間の長さに応じて上記のポリゴンの頂点を移動させることで、イニシャルスカルプチャが変形される。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】国際公開第２０１５／１９３７０８号
【発明の概要】
【発明が解決しようとする課題】
【０００５】
発明者らは、点群の輪郭に沿ったポリゴンモデルを生成する新たな手法を検討している。この手法では、まず、深さ情報を含む画像などから仮想空間内の点群を示す点群データが生成される。そして例えば当該点群に属する点をドロネー点とするドロネー三角形分割（四面体分割）などを行うことによって、それぞれ当該点群に属する点を頂点とする複数のポリゴンを含むポリゴンモデルが生成される。【０００６】
しかしこのようにして生成されるポリゴンモデルは外表面が点群の輪郭に沿ったものとはならない。ここで例えば所定長よりも長い辺を含むポリゴンをポリゴンモデルから削除することでポリゴンモデルを点群の輪郭に沿ったものにより近づけることが考えられる。しかしこのようにしても点群の粗密等の影響で点群の輪郭に沿った充分な精度のポリゴンモデルが得られないことがあった。【０００７】
本発明は上記課題に鑑みてなされたものであって、その目的の１つは、点群の輪郭に沿ったポリゴンモデルを精度よく生成できるポリゴンモデル生成装置、ポリゴンモデル生成方法及びプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明に係るポリゴンモデル生成装置は、仮想空間内の点群を示す点群データに基づいて、複数のポリゴンを含むポリゴンモデルを生成するポリゴンモデル生成部と、前記仮想空間内における前記ポリゴンモデルを望む第１位置と前記点群に属する点の位置である第２位置とを両端とする線分と交差する前記ポリゴンである交差ポリゴンを特定する交差ポリゴン特定部と、前記交差ポリゴンを前記ポリゴンモデルから削除する交差ポリゴン削除部と、を含む。【０００９】
本発明の一態様では、実空間において実カメラが被写体を撮影した画像を取得する画像取得部と、前記画像に基づいて、属する点がそれぞれ前記実空間内における前記被写体上の点に相当する前記点群データを生成する点群データ生成部と、前記被写体を撮影した際の前記実カメラの前記実空間内における位置に相当する、前記仮想空間内の位置を特定する対応カメラ位置特定部と、をさらに含み、前記交差ポリゴン特定部は、前記対応カメラ位置特定手順で特定される位置を前記第１位置として前記交差ポリゴンを特定する。【００１０】
また、本発明の一態様では、前記仮想空間内に設定される１又は複数の仮想カメラのいずれにおいても不可視な前記ポリゴンである不可視ポリゴンを特定する不可視ポリゴン特定部と、前記不可視ポリゴンを前記ポリゴンモデルから削除する不可視ポリゴン削除部と、をさらに含む。【００１１】
また、本発明の一態様では、前記点群の分布に基づいて、当該点群に属する点に対応付けられる点密度の値を決定する点密度値決定部と、前記ポリゴンを構成する辺の長さが、当該辺の端点に対応付けられる前記点密度の値に応じた閾値を超える場合に、当該ポリゴンを前記ポリゴンモデルから削除する長辺ポリゴン削除部と、をさらに含む。【００１２】
この態様では、前記交差ポリゴン特定部は、対応付けられる前記点密度の値が所定値よりも大きな点の少なくとも一部のそれぞれのみについて、当該点の位置を前記第２位置として前記交差ポリゴンを特定してもよい。【００１３】
また、本発明に係るポリゴンモデル生成方法は、仮想空間内の点群を示す点群データに基づいて、複数のポリゴンを含むポリゴンモデルを生成するポリゴンモデル生成ステップと、前記仮想空間内における前記ポリゴンモデルを望む第１位置と前記点群に属する点の位置である第２位置とを両端とする線分と交差する前記ポリゴンである交差ポリゴンを特定する交差ポリゴン特定ステップと、前記交差ポリゴンを前記ポリゴンモデルから削除する交差ポリゴン削除ステップと、を含む。【００１４】
また、本発明に係るプログラムは、仮想空間内の点群を示す点群データに基づいて、複数のポリゴンを含むポリゴンモデルを生成するポリゴンモデル生成手順、前記仮想空間内における前記ポリゴンモデルを望む第１位置と前記点群に属する点の位置である第２位置とを両端とする線分と交差する前記ポリゴンである交差ポリゴンを特定する交差ポリゴン特定手順、前記交差ポリゴンを前記ポリゴンモデルから削除する交差ポリゴン削除手順、をコンピュータに実行させる。
【図面の簡単な説明】
【００１５】
【図１】本発明の一実施形態に係るポリゴンモデル生成装置の構成図である。
【図２】被写体が実空間に配置されている様子の一例を模式的に示す図である。
【図３】被写体を模したポリゴンモデルが仮想空間内に配置されている様子の一例を模式的に示す図である。
【図４】点群データが示す点群に属する複数の点の一例を模式的に示す図である。
【図５】点データの一例を示す図である。
【図６】最初ポリゴンモデルが仮想空間内に配置されている様子の一例を模式的に示す図である。
【図７】ポリゴンデータの一例を示す図である。
【図８】長辺ポリゴン削除処理の一例を説明する説明図である。
【図９】交差ポリゴン削除処理の一例を説明する説明図である。
【図１０】中間ポリゴンモデルが仮想空間内に配置されている様子の一例を模式的に示す図である。
【図１１】仮想空間画像の一例を示す図である。
【図１２Ａ】法線方向修正処理の一例を説明する説明図である。
【図１２Ｂ】法線方向修正処理の一例を説明する説明図である。
【図１３】本発明の一実施形態に係るポリゴンモデル生成装置で実装される機能の一例を示す機能ブロック図である。
【図１４】本発明の一実施形態に係るポリゴンモデル生成装置で行われる処理の流れの一例を示すフロー図である。
【図１５】本発明の一実施形態に係るポリゴンモデル生成装置で行われる処理の流れの一例を示すフロー図である。
【図１６】本発明の一実施形態に係るポリゴンモデル生成装置で行われる処理の流れの一例を示すフロー図である。
【図１７】本発明の一実施形態に係るポリゴンモデル生成装置で行われる処理の流れの一例を示すフロー図である。
【発明を実施するための形態】
【００１６】
以下、本発明の一実施形態について図面に基づき詳細に説明する。
【００１７】
図１は、本発明の一実施形態に係るポリゴンモデル生成装置１０の構成図である。本実施形態に係るポリゴンモデル生成装置１０は、例えば、ゲームコンソールやパーソナルコンピュータなどのコンピュータである。図１に示すように、本実施形態に係るポリゴンモデル生成装置１０は、例えば、プロセッサ１２、記憶部１４、操作部１６、表示部１８、を含んでいる。
【００１８】
プロセッサ１２は、例えばポリゴンモデル生成装置１０にインストールされるプログラムに従って動作するＣＰＵ等のプログラム制御デバイスである。本実施形態に係るプロセッサ１２には、ＣＰＵから供給されるグラフィックスコマンドやデータに基づいてフレームバッファに画像を描画するＧＰＵ（Graphics Processing Unit）も含まれている。
【００１９】
記憶部１４は、ＲＯＭやＲＡＭ等の記憶素子やハードディスクドライブなどである。記憶部１４には、プロセッサ１２によって実行されるプログラムなどが記憶される。また、本実施形態に係る記憶部１４には、ＧＰＵにより画像が描画されるフレームバッファの領域が確保されている。
【００２０】
操作部１６は、キーボード、マウス、ゲームコンソールのコントローラ等のユーザインタフェースであって、ユーザの操作入力を受け付けて、その内容を示す信号をプロセッサ１２に出力する。
【００２１】
表示部１８は、液晶ディスプレイ等の表示デバイスであって、プロセッサ１２の指示に従って各種の画像を表示する。
【００２２】
なお、ポリゴンモデル生成装置１０は、ネットワークボードなどの通信インタフェース、ＤＶＤ−ＲＯＭやＢｌｕ−ｒａｙ（登録商標）ディスクなどの光ディスクを読み取る光ディスクドライブ、ＵＳＢ（Universal Serial Bus）ポートなどを含んでいてもよい。
【００２３】
図２は、本実施形態に係る被写体２０が実空間２２内に配置されている様子の一例を模式的に示す図である。図２には、スタンフォードバニーのような形状の実オブジェクトが被写体２０の一例として示されている。
【００２４】
図３は、被写体２０を模したポリゴンモデルが仮想空間３２内に配置されている様子の一例を模式的に示す図である。本実施形態に係るポリゴンモデル生成装置１０では、例えば、実空間２２に配置された実カメラ２４が図２に例示する被写体２０を撮影した１又は複数の撮影画像に基づいて、最終的には図３に示すポリゴンモデルが生成される。以下、最終的に生成されるポリゴンモデルを最終ポリゴンモデル３０と呼ぶこととする。
【００２５】
図３に示す最終ポリゴンモデル３０は、複数のポリゴン３４から構成されている。本実施形態に係る仮想空間３２は、実空間２２をモデリングした空間となっている。本実施形態では実空間２２内における被写体２０の位置や向きは、仮想空間３２内の最終ポリゴンモデル３０の位置や向きに反映される。以下、実空間２２内における位置はＸ１Ｙ１Ｚ１座標系で表現され、仮想空間３２内における位置はＸ２Ｙ２Ｚ２座標系で表現されることとする。
【００２６】
以下、ポリゴンモデル生成装置１０で行われる、被写体２０に基づく最終ポリゴンモデル３０の生成処理について説明する。
【００２７】
本実施形態に係るポリゴンモデル生成装置１０は、まず、実カメラ２４が被写体２０を撮影した１又は複数の撮影画像を取得する。なお、複数の実カメラ２４のそれぞれによって同時に撮影画像が撮影されてもよいし、１の実カメラ２４によって様々な向きから被写体２０の撮影画像が撮影されてもよい。また実カメラ２４は、ステレオカメラや赤外線測距センサ付きのカメラなどといった、深さ情報を含む撮影画像の撮影が可能なカメラであってもよい。この場合例えば、撮影画像に含まれる画素のそれぞれに対応付けられる、実カメラ２４から被写体２０までの距離の分布を示すデプス画像が、実カメラ２４によって撮影画像とともに生成されてもよい。
【００２８】
図４は、１又は複数の撮影画像に基づいて生成される点群データが示す点群に属する複数の点３６の一例を模式的に示す図である。本実施形態では、ポリゴンモデル生成装置１０が取得する１又は複数の撮影画像に基づいて、公知の手法により、仮想空間３２内の複数の点３６が属する点群を示す点群データが生成される。また撮影画像とデプス画像に基づいて点群データが生成されてもよい。
【００２９】
本実施形態では、複数の撮影画像が撮影される場合には、各撮影画像が撮影される際の被写体２０と実カメラ２４との間の距離の違いや撮影画像を撮影する複数の実カメラ２４の解像度の違いなどによって、点群に属する点３６の密度に粗密が生じることがある。また実カメラ２４に対する被写体２０の向きによっても点群に属する点３６の密度に粗密が生じることがある。
【００３０】
図５は、点群データに含まれる、１の点３６に対応付けられる点データの一例を示す図である。図５に示す点データには、当該点データに対応付けられる点３６の識別情報である点ＩＤと当該点３６のＸ２Ｙ２Ｚ２座標系で表現された位置を表す３次元座標値を示す座標データとの組合せが含まれる。本実施形態で生成される点群データには、図５に例示する点データが点群に属する点３６の数だけ含まれる。
【００３１】
そして図４に示す点３６の位置は、１又は複数の撮影画像に基づいて特定される、被写体２０の表面上の点の位置に対応付けられる。そして本実施形態では例えば、実空間２２のＸ１Ｙ１Ｚ１座標系における座標値（ｘ１，ｙ１，ｚ１）が、仮想空間３２内のＸ２Ｙ２Ｚ２座標系における座標値（ｔ・ｘ１，ｔ・ｙ１，ｔ・ｚ１）（ｔは定数）にマッピングされる。そのため本実施形態では、図４に示す点群の輪郭に沿った立体の形状は、図２に示す被写体２０の形状と概ね同じになる。
【００３２】
そして本実施形態に係るポリゴンモデル生成装置１０は、図４に示す点群に属する点３６に基づいて、複数のポリゴン３４から構成される、ポリゴンモデルを示すポリゴンモデルデータを生成する。ここでは例えば、それぞれ図４に示す点群に属する点３６を頂点とするポリゴン３４から構成される、図６に例示するポリゴンモデルを示すポリゴンモデルデータが生成されることとする。なお点群に属する点３６のなかには、ポリゴン３４の頂点とはならずにポリゴン３４の面上の点となるものがあってもよい。以下、図６に示すポリゴンモデルを最初ポリゴンモデル４０と呼ぶこととする。例えば、図４に示す点群に属する点３６をドロネー点とするドロネー三角形分割（四面体分割）を行うことで、複数の三角形から構成される最初ポリゴンモデル４０が生成されてもよい。なおドロネー三角形分割によって最初ポリゴンモデル４０が生成される必要はなく、その他の方法によって最初ポリゴンモデル４０が生成されても構わない。
【００３３】
図７は、１のポリゴン３４に対応付けられるポリゴンデータの一例を示す図である。本実施形態では、最初ポリゴンモデル４０に含まれるポリゴン３４の数だけポリゴンデータを含むポリゴンモデルデータが生成される。ポリゴンデータには、例えば、当該ポリゴンデータに対応付けられるポリゴン３４の識別情報であるポリゴンＩＤと、当該ポリゴン３４の頂点である点３６の点ＩＤの順序付きリストである頂点データと、が含まれる。
【００３４】
またポリゴンデータによって当該ポリゴンデータに対応付けられるポリゴン３４の法線方向（表裏）が定義されてもよい。例えばポリゴン３４を表側から見た際において反時計回りとなるような頂点の順序である、各頂点に対応付けられる点３６の順序付きリストが頂点データとしてポリゴンデータに含まれるようにしてもよい。そしてこの場合にポリゴン３４の裏側から表側に向かう方向が法線方向として定義されてもよい。
【００３５】
なおポリゴンデータのデータ構造は図７に示すものに限定されない。
【００３６】
ここで図６に例示する最初ポリゴンモデル４０には、図４に示す点群の凸包が含まれており、図４に示す点群の輪郭に沿ったものであるとは言えない。そこで本実施形態では、以下で説明する長辺ポリゴン削除処理、交差ポリゴン削除処理、及び、不可視ポリゴン削除処理が実行されることによって、図６に例示する最初ポリゴンモデル４０を構成するポリゴン３４が順次削除される。そしてこのようにすることで本実施形態によれば、図５に例示する最初ポリゴンモデル４０が、図４に示す点群の輪郭に沿ったポリゴンモデル、すなわち被写体２０の再現精度の高いポリゴンモデルに近づいていく。
【００３７】
ここで図８を参照しながら長辺ポリゴン削除処理の一例について説明する。
【００３８】
長辺ポリゴン削除処理では、まず、図４に示す点群の分布に基づいて、当該点群に属するそれぞれの点３６に対応付けられる点密度の値が決定される。
【００３９】
ここで特定の点３６を中心とする所定の体積の六面体に含まれる点３６の数が、当該特定の点３６に対応する点密度の値として決定されてもよい。
【００４０】
また、点群データが、仮想空間３２内に配置されるそれぞれの点３６の位置を、当該点群データが示す点群を覆う立方体が占める３次元空間を再帰的に８つに分割した部分空間に対応付けた八分木データ構造のデータを含んでいてもよい。この場合、八分木に基づいて大まかに特定される点３６の密度が当該点３６に対応付けられる点密度の値として決定されてもよい。このようにすれば点密度の値が高速に決定される。
【００４１】
なお点密度の値の決定方法は以上の方法には限定されない。
【００４２】
次に、最初ポリゴンモデル４０に含まれるそれぞれの辺４２につき、当該辺４２の端点である点３６に対応付けられる点密度の値に基づいて、当該辺４２に対応付けられる閾値が決定される。図８の例において、辺４２ａの一方の端点である点３６ａに対応付けられる点密度の値がｖ１と特定されたとする。また辺４２ａの他方の端点である点３６ｂに対応付けられる点密度の値がｖ２と特定されたとする。この場合は例えば、値ｖ１と値ｖ２とに基づいて、辺４２ａに対応付けられる閾値ｔｈが決定される。ここで例えば値ｖ１と値ｖ２のうちの小さな値に対応付けられる閾値が閾値ｔｈとして決定されてもよい。また例えば値ｖ１と値ｖ２のうちの大きな値に対応付けられる閾値が閾値ｔｈとして決定されてもよい。また例えば値ｖ１と値ｖ２の平均値に対応付けられる閾値が閾値ｔｈとして決定されてもよい。
【００４３】
なお本実施形態では点密度の値と閾値との対応規則は予め定められており、点密度の値に基づいて閾値が決定可能であることとする。また点密度の値が大きいほど当該点密度の値に対応付けられる閾値として小さな値が決定されることとする。
【００４４】
そして最初ポリゴンモデル４０に含まれる辺４２のうちから、当該辺４２に対応づけられる閾値よりも当該辺４２の長さの方が大きな辺４２が特定される。そして特定された辺４２を含むポリゴン３４が最初ポリゴンモデル４０から削除される。すなわち、特定された辺４２を含むポリゴン３４に対応するポリゴンデータが、ポリゴンモデルデータから削除される。図８の例では、辺４２ａの長さＬが閾値ｔｈを超える場合には、辺４２ａを含むポリゴン３４ａ及びポリゴン３４ｂが最初ポリゴンモデル４０から削除される。
【００４５】
上述の長辺ポリゴン削除処理を実行せずに、図６に例示する最初ポリゴンモデル４０から所定長よりも長い辺４２を含むポリゴン３４を一律で削除するようにすると、図４に示す点群の粗密の影響で精度の高いポリゴンモデルが得られないことがある。例えば、上述の所定長を短くすると凹部においてもポリゴンモデルが点群の輪郭に沿ったものとなる一方でポリゴンモデルに穴が空く可能性が高くなる。また上述の所定長を長くするとポリゴンモデルに穴が空く可能性は低減されるが凹部においてポリゴンモデルが点群の輪郭に沿ったものとならない可能性が高くなる。
【００４６】
本実施形態に係る長辺ポリゴン削除処理では、点群に属する点３６の密度が反映された閾値に基づき長辺を含むポリゴン３４が削除される。具体的には例えば、点３６が密である部分においては比較的短い辺を含むポリゴン３４であっても削除される一方で、点３６が粗である部分においては比較的長い辺を含むポリゴン３４であっても削除されない。このようにして本実施形態では、精度の高いポリゴンモデルを得ることができる。
【００４７】
そして本実施形態ではポリゴンモデルの精度をさらに高めるため、以下で説明する交差ポリゴン削除処理が実行される。ここで図９を参照しながら交差ポリゴン削除処理の一例について説明する。
【００４８】
交差ポリゴン削除処理では、まず、撮影画像を撮影した際の実空間２２における実カメラ２４の位置に相当する、仮想空間３２内における位置が特定される。上述のように実カメラ２４の位置のＸ１Ｙ１Ｚ１座標値が（ｘ１，ｙ１，ｚ１）である場合には、この実カメラ２４の位置に相当する仮想空間３２内の位置のＸ２Ｙ２Ｚ２座標値として（ｔ・ｘ１，ｔ・ｙ１，ｔ・ｚ１）が特定される。以下、このようにして特定される、実空間２２における実カメラ２４の位置に相当する、仮想空間３２内における位置を、当該実カメラ２４の対応カメラ位置と呼ぶこととする。
【００４９】
そして実カメラ２４によって撮影された撮影画像に含まれる画素に対応付けられる被写体２０の表面上の点に相当する、仮想空間３２内における点３６が特定される。以下、このようにして特定される点３６を、当該実カメラ２４の可視点と呼ぶこととする。
【００５０】
そして実カメラ２４の対応カメラ位置から、当該実カメラ２４の可視点のうち対応付けられる点密度の値が所定値よりも大きな点３６のそれぞれに対してレイキャストが実行される。
【００５１】
そしてレイキャストにおけるレイと交差するポリゴン３４がポリゴンモデルから削除される。例えば図９に示す、実カメラ２４の対応カメラ位置Ｐ１から当該実カメラ２４の可視点である点３６ｃに対してレイキャストを実行した際に、当該レイキャストにおけるレイとポリゴン３４ｃが位置Ｐ２において交差したとする。すなわち、対応カメラ位置Ｐ１と点３６ｃの位置とを両端とする線分と交差するポリゴン３４としてポリゴン３４ｃが特定されたとする。この場合、このポリゴン３４ｃがポリゴンモデルから削除される。すなわち、ポリゴン３４ｃに対応するポリゴンデータが、ポリゴンモデルデータから削除される。
【００５２】
上述の交差ポリゴン削除処理によれば、長辺ポリゴン削除処理では削除しきれないポリゴン３４の削除が可能となり、交差ポリゴン削除処理が実行された後のポリゴンモデルは点群の輪郭に沿ったものにより近づく。
【００５３】
しかし以上の長辺ポリゴン削除処理及び交差ポリゴン削除処理を実行しても、ポリゴンモデルの外表面よりも内側のポリゴン３４が残ることがある。このようなポリゴン３４は、ポリゴンモデルの外観の表現に寄与しない。そのため、このようなポリゴン３４に対応するポリゴンデータはポリゴンモデルデータにおける無駄といえる。
【００５４】
そこで本実施形態では、以下で説明する不可視ポリゴン削除処理によって、ポリゴンモデルの外表面よりも内側のポリゴン３４が削除され、その結果、ポリゴンモデルデータのデータサイズの無駄が低減されるようにした。ここで図１０〜図１２Ｂを参照しながら不可視ポリゴン削除処理の一例について説明する。
【００５５】
まず図１０に示すように、長辺ポリゴン削除処理及び交差ポリゴン削除処理が実行されたポリゴンモデルが、仮想空間３２内に配置される。以下、長辺ポリゴン削除処理及び交差ポリゴン削除処理が実行されたポリゴンモデルを、中間ポリゴンモデル５０と呼ぶこととする。中間ポリゴンモデル５０は、外観は最終ポリゴンモデル３０と同様であるが、上述のように外表面よりも内側のポリゴン３４が残っている。ここで中間ポリゴンモデル５０に含まれるポリゴン３４が互いに識別可能な状態で仮想空間３２内に配置されてもよい。例えば、ポリゴン３４のポリゴンＩＤに対応付けられるテクスチャや色等の可視属性が当該ポリゴン３４に設定されてもよい。
【００５６】
そして中間ポリゴンモデル５０を望む仮想空間３２内の位置に配置された仮想カメラ５２から中間ポリゴンモデル５０の方向を見た様子を表す、図１１に例示する仮想空間画像５４がレンダリングされる。図１１には、図１０における位置Ｐ３に配置された仮想カメラ５２中間ポリゴンモデル５０の方向を見た様子を表す仮想空間画像５４が示されている。ここでポリゴン３４に設定されている可視属性が仮想空間画像に反映されてもよい。そして当該仮想空間画像５４を撮影した位置から可視であるポリゴン３４（可視ポリゴン３４ｄ）が特定される。ここで例えば、仮想空間画像５４に像が含まれるポリゴン３４に設定されている可視属性に対応付けられるポリゴンＩＤに対応するポリゴン３４が、可視ポリゴン３４ｄとして特定されてもよい。
【００５７】
ここで図１０に示すように、仮想空間３２内の複数の位置のそれぞれについて、順次、上述の仮想カメラ５２の配置、仮想空間画像５４の生成、及び、可視ポリゴン３４ｄの特定が行われてもよい。また仮想空間３２内の複数の位置のそれぞれにおける、仮想カメラ５２の配置、仮想空間画像５４の生成、及び、可視ポリゴン３４ｄの特定が並列処理で実行されてもよい。そしていずれの仮想空間画像５４においても可視ポリゴン３４ｄとして特定されなかったポリゴン３４が、不可視ポリゴンとして特定される。
【００５８】
ここで例えば、初期状態では空である可視ポリゴンＩＤリストに、可視ポリゴン３４ｄとして特定されたポリゴン３４のポリゴンＩＤが追加されるようにしてもよい。そして可視ポリゴンＩＤリストにポリゴンＩＤが含まれていないポリゴン３４が不可視ポリゴンとして特定されてもよい。
【００５９】
そして、不可視ポリゴンとして特定されたポリゴン３４が、中間ポリゴンモデル５０から削除される。すなわち不可視ポリゴンに対応するポリゴンデータが、ポリゴンモデルデータから削除される。
【００６０】
また本実施形態では、不可視ポリゴン削除処理の際に、それぞれの仮想空間画像５４において可視ポリゴン３４ｄとして特定されたポリゴン３４については、法線方向修正処理が実行される。
【００６１】
ここでは例えば図１２Ａに示すように、可視ポリゴン３４ｄの法線方向が仮想カメラ５２に向かっていない場合は、当該可視ポリゴン３４ｄに対応付けられる法線反転カウント値が１増加する。すなわち仮想カメラ５２による撮影方向のベクトルＶ１と可視ポリゴン３４ｄの法線方向のベクトルＶ２との内積が正である場合は、当該可視ポリゴン３４ｄに対応付けられる法線反転カウント値が１増加する。
【００６２】
逆に例えば図１２Ｂに示すように、可視ポリゴン３４ｄの法線方向が仮想カメラ５２に向かっている場合は、当該可視ポリゴン３４ｄに対応付けられる法線反転カウント値が１減少する。すなわち仮想カメラ５２による撮影方向のベクトルＶ１と可視ポリゴン３４ｄの法線方向のベクトルＶ２との内積が負である場合は、当該可視ポリゴン３４ｄに対応付けられる法線反転カウント値が１減少する。なお、可視ポリゴン３４ｄに対応付けられる法線反転カウント値の初期値は０であることとする。
【００６３】
そしてすべての仮想空間画像に対して法線反転カウント値の増加や減少が実行された結果において、対応付けられる法線反転カウント値が正である可視ポリゴン３４ｄが特定される。そして特定された可視ポリゴン３４ｄに対応付けられるポリゴンデータが示す法線方向が反転される。ここでは例えば、ポリゴンデータの頂点データに含まれる３つの点ＩＤのうち２番目の点ＩＤと３番目の点ＩＤの順序が入れ替わる。
【００６４】
図６に示す最初ポリゴンモデル４０を構成するポリゴン３４が順次削除された結果、法線方向がポリゴンモデルの外表面の内側から外側に向かっていないポリゴン３４が存在することがある。このようなポリゴン３４についても上述の法線方向修正処理によって、その法線方向がポリゴン３４の外表面の内側から外側に向かうよう修正される。
【００６５】
そして以上のようにして不可視ポリゴン削除処理及び法線方向修正処理が行われることで、図３に例示する最終ポリゴンモデル３０が生成される。
【００６６】
ＧＰＵのレンダリング機能を用いれば、仮想空間画像５４は容易に生成できる。そして本実施形態ではこのように容易に生成可能な仮想空間画像５４に基づいて、可視ポリゴン３４ｄが特定されるため、不可視ポリゴンを容易に特定できる。
【００６７】
以上で説明したように、本実施形態では、図５に例示する最初ポリゴンモデル４０からポリゴン３４を削除するというシンプルな処理によって、低処理負荷で、被写体２０を模した高精度の最終ポリゴンモデル３０を生成することができる。
【００６８】
以下、本実施形態に係るポリゴンモデル生成装置１０の機能、及び、ポリゴンモデル生成装置１０で実行される処理についてさらに説明する。
【００６９】
図１３は、本実施形態に係るポリゴンモデル生成装置１０で実装される機能の一例を示す機能ブロック図である。図１３に示すように、ポリゴンモデル生成装置１０は、機能的には例えば、撮影画像記憶部６０、カメラデータ記憶部６２、ポリゴンモデルデータ記憶部６４、撮影画像取得部６６、カメラデータ取得部６８、点群データ生成部７０、最初ポリゴンモデル生成部７２、点密度値決定部７４、閾値決定部７６、長辺ポリゴン削除部７８、対応カメラ位置特定部８０、交差ポリゴン削除部８２、可視属性設定部８４、仮想カメラ配置部８６、仮想空間画像生成部８８、可視ポリゴン特定部９０、法線方向修正部９２、不可視ポリゴン削除部９４、を含んでいる。
【００７０】
撮影画像記憶部６０、カメラデータ記憶部６２、ポリゴンモデルデータ記憶部６４は、記憶部１４を主として実装される。撮影画像取得部６６、カメラデータ取得部６８、点群データ生成部７０、最初ポリゴンモデル生成部７２、点密度値決定部７４、閾値決定部７６、長辺ポリゴン削除部７８、対応カメラ位置特定部８０、交差ポリゴン削除部８２、可視属性設定部８４、仮想カメラ配置部８６、仮想空間画像生成部８８、可視ポリゴン特定部９０、法線方向修正部９２、不可視ポリゴン削除部９４は、プロセッサ１２を主として実装される。
【００７１】
以上の機能は、コンピュータであるポリゴンモデル生成装置１０にインストールされた、以上の機能に対応する指令を含むプログラムをプロセッサ１２で実行することにより実装されてもよい。このプログラムは、例えば、光ディスク、磁気ディスク、磁気テープ、光磁気ディスク、フラッシュメモリ等のコンピュータ読み取り可能な情報記憶媒体を介して、あるいは、インターネットなどを介してポリゴンモデル生成装置１０に供給されてもよい。
【００７２】
撮影画像記憶部６０は、本実施形態では例えば、実空間２２において実カメラ２４が被写体２０を撮影した１又は複数の撮影画像を記憶する。撮影画像記憶部６０は、デプス画像などといった深さ情報に関連付けられた撮影画像を記憶してもよい。
【００７３】
カメラデータ記憶部６２は、本実施形態では例えば、撮影画像を撮影した際における、実空間２２内における実カメラ２４の位置、向き、画角、などを示すカメラデータを記憶する。撮影画像記憶部６０に複数の撮影画像が記憶される場合は、カメラデータ記憶部６２には、それぞれ撮影画像に対応付けられる複数のカメラデータが記憶される。
【００７４】
ポリゴンモデルデータ記憶部６４は、本実施形態では例えば、図５に例示する点データを複数含む点群データ、及び、図７に例示するポリゴンデータを複数含むポリゴンモデルデータを記憶する。
【００７５】
撮影画像取得部６６は、本実施形態では例えば、撮影画像記憶部６０に記憶されている１又は複数の撮影画像を取得する。
【００７６】
カメラデータ取得部６８は、本実施形態では例えば、カメラデータ記憶部６２に記憶されている１又は複数のカメラデータを取得する。
【００７７】
点群データ生成部７０は、本実施形態では例えば、撮影画像取得部６６が取得する撮影画像、及び、カメラデータ取得部６８が取得するカメラデータに基づいて、点群データを生成して、生成された点群データをポリゴンモデルデータ記憶部６４に記憶させる。
【００７８】
最初ポリゴンモデル生成部７２は、本実施形態では例えば、ポリゴンモデルデータ記憶部６４に記憶されている点群データに基づいて、複数のポリゴン３４を含む最初ポリゴンモデル４０を生成する。ここで例えば、それぞれポリゴンモデルデータ記憶部６４に記憶されている点群データが示す点群に属する点３６を頂点とする複数のポリゴン３４を含む最初ポリゴンモデル４０が生成されてもよい。そして最初ポリゴンモデル生成部７２は、本実施形態では例えば、生成された最初ポリゴンモデル４０をポリゴンモデルデータ記憶部６４に記憶させる。
【００７９】
点密度値決定部７４は、本実施形態では例えば、ポリゴンモデルデータ記憶部６４に記憶されている点群データが示す点群の分布に基づいて、上述のようにして、当該点群に属するそれぞれの点３６に対応付けられる点密度の値を決定する。
【００８０】
閾値決定部７６は、本実施形態では例えば、ポリゴンモデルデータ記憶部６４に記憶されているポリゴンデータが示すそれぞれのポリゴン３４について、上述のようにして、当該ポリゴン３４を構成する辺４２に対応付けられる閾値を決定する。ここで点密度の値が大きいほど当該点密度の値に対応付けられる閾値として小さな値が決定されるようにしてもよい。また閾値決定部７６は、点密度の値と閾値との対応規則を示すデータを保持していてもよい。そして閾値決定部７６は、このデータを用いて閾値を決定してもよい。
【００８１】
長辺ポリゴン削除部７８は、本実施形態では例えば、ポリゴン３４を構成する辺４２の長さが、当該辺４２の端点に対応付けられる点密度の値に応じた閾値を超える場合に、当該ポリゴン３４をポリゴンモデルから削除する。ここで長辺ポリゴン削除部７８は、上述のようにして、対応づけられる閾値よりもその長さの方が大きな辺４２を含むポリゴン３４をポリゴンモデルから削除してもよい。また、対応づけられる閾値よりもその長さの方が大きな辺４２を含むポリゴン３４のポリゴンＩＤを含むポリゴンデータが、ポリゴンモデルデータから削除されてもよい。
【００８２】
対応カメラ位置特定部８０は、本実施形態では例えば、カメラデータ取得部６８が取得するカメラデータに基づいて、当該カメラデータが示す実空間２２における実カメラ２４の位置に相当する仮想空間３２内の位置である対応カメラ位置を特定する。
【００８３】
交差ポリゴン削除部８２は、本実施形態では例えば、仮想空間３２内におけるポリゴンモデルを望む位置と、点群データが示す点群に属する点３６の位置とを両端とする線分と交差するポリゴン３４を特定する。
【００８４】
ここで上述のように、実カメラ２４の対応カメラ位置と、当該実カメラ２４によって撮影された撮影画像に像が含まれる被写体２０の表面に相当する点３６とを両端とする線分に交差するポリゴン３４が特定されてもよい。また、対応付けられる点密度の値が所定値よりも大きな点３６の少なくとも一部のそれぞれのみについて、当該点３６の位置と仮想空間３２内におけるポリゴンモデルを望む位置とを両端とする線分に交差するポリゴン３４が特定されてもよい。
【００８５】
また例えば、仮想空間３２における、ポリゴンモデルの中心に対する無限遠点と、点３６とを両端とする線分に交差するポリゴン３４が特定されてもよい。また例えば、ポリゴンモデルの中心から、当該ポリゴンモデルを内包する球の半径の所定倍（例えば１．５倍や３倍など）以上離れた位置と、点３６とを両端とする線分に交差するポリゴン３４が特定されてもよい。
【００８６】
また例えば、ユーザによって設定された仮想空間３２内におけるポリゴンモデルを望む位置と、点３６とを両端とする線分に交差するポリゴン３４が特定されてもよい。
【００８７】
そして交差ポリゴン削除部８２は、本実施形態では例えば、特定されたポリゴン３４をポリゴンモデルから削除する。ここで例えば、特定されたポリゴン３４のポリゴンＩＤを含むポリゴンデータがポリゴンモデルデータから削除されてもよい。
【００８８】
可視属性設定部８４は、本実施形態では例えば、仮想空間３２内に配置されている中間ポリゴンモデル５０を構成するそれぞれのポリゴン３４に、当該ポリゴン３４に対応付けられる可視属性を設定する。
【００８９】
仮想カメラ配置部８６は、本実施形態では例えば、仮想空間３２内における仮想カメラ５２の位置及び撮影方向を決定する。ここで例えば、仮想カメラ配置部８６は、ユーザによる操作部１６の操作に応じて、仮想カメラ５２の位置や向きを変更してもよい。そして、仮想カメラ配置部８６は、ユーザの決定操作に応じて、仮想カメラ５２の配置を決定してもよい。
【００９０】
仮想空間画像生成部８８は、本実施形態では例えば、仮想カメラ配置部８６により配置された仮想カメラ５２の位置から仮想カメラ５２の撮影方向を見た様子を表す仮想空間画像５４を生成する。ここで例えば、それぞれ互いに異なる位置から見た様子を表す複数の仮想空間画像５４が生成されてもよい。
【００９１】
可視ポリゴン特定部９０は、本実施形態では例えば、仮想空間画像５４に基づいて、仮想カメラ５２から可視である可視ポリゴン３４ｄを特定する。
【００９２】
法線方向修正部９２は、本実施形態では例えば、可視ポリゴン特定部９０が特定するそれぞれの可視ポリゴン３４ｄに対して、上述の法線方向修正処理を実行する。
【００９３】
不可視ポリゴン削除部９４は、本実施形態では例えば、仮想空間３２内に設定される１又は複数の仮想カメラ５２のいずれにおいても不可視なポリゴン３４である不可視ポリゴンを特定する。そして不可視ポリゴン削除部９４は、本実施形態では例えば、特定される不可視ポリゴンをポリゴンモデルから削除する。ここで例えば、不可視ポリゴンのポリゴンＩＤを含むポリゴンデータが、ポリゴンモデルデータから削除されてもよい。またいずれの仮想空間画像５４においても可視ポリゴン３４ｄとして特定されなかったポリゴン３４に対応付けられるポリゴンデータが、ポリゴンモデルデータから削除されてもよい。
【００９４】
ここで、本実施形態に係るポリゴンモデル生成装置１０で行われる処理の流れの一例を、図１４に例示するフロー図を参照しながら説明する。なお以下の処理例では、以下の処理の開始の際には空である可視ポリゴンＩＤリストが可視ポリゴン特定部９０によって保持されていることとする。
【００９５】
まず、撮影画像取得部６６が、撮影画像記憶部６０に記憶されている１又は複数の撮影画像を取得する（Ｓ１０１）。そしてカメラデータ取得部６８が、カメラデータ記憶部６２に記憶されている、Ｓ１０１に示す処理で取得された撮影画像に対応付けられるカメラデータを取得する（Ｓ１０２）。本処理例ではＳ１０１に示す処理で複数の撮影画像が取得され、Ｓ１０２に示す処理でそれぞれ撮影画像に対応付けられる複数のカメラデータが取得されることとする。
【００９６】
そして点群データ生成部７０が、複数の点データを含む点群データを生成して、生成された点群データをポリゴンモデルデータ記憶部６４に記憶させる（Ｓ１０３）。ここでＳ１０１に示す処理で取得された撮影画像に基づいて点群データが生成されてもよい。あるいはＳ１０１に示す処理で取得された撮影画像及びＳ１０２に示す処理で取得されたカメラデータに基づいて点群データが生成されてもよい。
【００９７】
そして最初ポリゴンモデル生成部７２が、Ｓ１０３に示す処理で記憶された点群データに基づいて、最初ポリゴンモデル４０のポリゴンモデルデータを生成して、生成されたポリゴンモデルデータをポリゴンモデルデータ記憶部６４に記憶させる(Ｓ１０４)。
【００９８】
そして上述の長辺ポリゴン削除処理（Ｓ１０５）、交差ポリゴン削除処理（Ｓ１０６）、不可視ポリゴン削除処理（Ｓ１０７）の順に処理が実行され、最終ポリゴンモデル３０に対応付けられるポリゴンモデルデータが最終的には生成される。
【００９９】
以下、本実施形態に係るポリゴンモデル生成装置１０で行われる、Ｓ１０５に示す長辺ポリゴン削除処理の流れの一例を、図１５に例示するフロー図を参照しながら説明する。
【０１００】
まず、点密度値決定部７４が、Ｓ１０３に示す処理で記憶された点群データが示す点群の分布に基づいて、当該点群データに含まれる複数の点データのそれぞれに対応する点３６について、当該点３６に対応する点密度の値を決定する（Ｓ２０１）。
【０１０１】
そして閾値決定部７６が、Ｓ１０４に示す処理で生成されるポリゴンモデルデータに含まれる複数のポリゴンデータのそれぞれについて、当該ポリゴンデータが示すポリゴン３４の辺４２に対応付けられる閾値を決定する（Ｓ２０２）。ここで例えば、辺４２は、ポリゴンデータの頂点データに含まれる２つの点ＩＤの組合せに対応付けられる点３６の組合せに対応する。そしてこれら２つの点ＩＤのそれぞれに対応付けられる点３６についてＳ１０５に示す処理で決定された点密度の値に基づいて、辺４２に対応付けられる閾値は決定可能である。
【０１０２】
そして長辺ポリゴン削除部７８は、Ｓ２０２に示す処理で閾値が決定された辺４２のなかから、辺４２の長さが当該辺４２について決定された閾値を超える辺４２を含むポリゴン３４を特定する（Ｓ２０３）。
【０１０３】
そして長辺ポリゴン削除部７８は、Ｓ２０３に示す処理で特定されたポリゴン３４のポリゴンＩＤを含むポリゴンデータを、ポリゴンモデルデータ記憶部６４に記憶されているポリゴンモデルデータから削除する（Ｓ２０４）。そして長辺ポリゴン削除処理（Ｓ１０５）は終了される。
【０１０４】
以下、本実施形態に係るポリゴンモデル生成装置１０で行われる、Ｓ１０６に示す交差ポリゴン削除処理の流れの一例を、図１６に例示するフロー図を参照しながら説明する。
【０１０５】
まず対応カメラ位置特定部８０が、Ｓ１０２に示す処理で取得されたカメラデータに基づいて、それぞれカメラデータに対応付けられる、実カメラ２４の対応カメラ位置を特定する（Ｓ３０１）。本処理例ではカメラデータが複数取得されるので、対応カメラ位置は複数特定される。
【０１０６】
そして交差ポリゴン削除部８２が、Ｓ３０１に示す処理で特定された対応カメラ位置のうちから、以下のＳ３０３〜Ｓ３０７に示す処理が実行されていない１つを選択する（Ｓ３０２）。
【０１０７】
そして、交差ポリゴン削除部８２は、Ｓ３０２に示す処理で選択された対応カメラ位置に対応する実カメラ２４が撮影した撮影画像を特定する（Ｓ３０３）。
【０１０８】
そして交差ポリゴン削除部８２は、Ｓ３０３に示す処理で特定された撮影画像に像が含まれる被写体２０の表面に相当する複数の点３６を特定する（Ｓ３０４）。
【０１０９】
そして交差ポリゴン削除部８２は、Ｓ３０４に示す処理で特定された複数の点３６のうちから、Ｓ２０１に示す処理で決定された、対応付けられる点密度の値が所定値よりも大きいものを抽出する（Ｓ３０５）。
【０１１０】
そして交差ポリゴン削除部８２は、Ｓ３０５に示す処理で抽出された複数の点３６のそれぞれについて、当該点３６の位置とＳ３０１に示す処理で選択された対応カメラ位置とを両端とする線分を交差するポリゴン３４を特定する（Ｓ３０６）。
【０１１１】
そして交差ポリゴン削除部８２は、Ｓ３０６に示す処理で特定されたポリゴン３４のポリゴンＩＤを含むポリゴンデータを、ポリゴンモデルデータ記憶部６４に記憶されているポリゴンモデルデータから削除する（Ｓ３０７）。
【０１１２】
そして交差ポリゴン削除部８２は、Ｓ３０２に示す処理で未選択である、Ｓ３０３〜Ｓ３０７に示す処理が実行されていない対応カメラ位置が存在するかを確認する（Ｓ３０８）。存在する場合は（Ｓ３０８：Ｙ）、Ｓ３０２に示す処理に戻る。存在しない場合は（Ｓ３０８：Ｎ）、交差ポリゴン削除処理（Ｓ１０６）は終了される。
【０１１３】
以下、本実施形態に係るポリゴンモデル生成装置１０で行われる、Ｓ１０７に示す不可視ポリゴン削除処理の流れの一例を、図１７に例示するフロー図を参照しながら説明する。
【０１１４】
まず、可視属性設定部８４が、ポリゴンモデルデータ記憶部６４に記憶されているポリゴンモデルデータに含まれるポリゴンデータのそれぞれに対して互いに異なる可視属性を設定する（Ｓ４０１）。
【０１１５】
そして仮想カメラ配置部８６が、仮想空間３２内における、ポリゴンモデルを望む仮想カメラ５２の位置、及び、仮想カメラ５２の撮影方向を決定する（Ｓ４０２）。ここで例えば、位置及び撮影方向がランダムに決定されてもよいし、ユーザの指定に応じて位置及び撮影方向が決定されてもよい。
【０１１６】
そして仮想空間画像生成部８８が、仮想カメラ５２の位置から仮想カメラ５２の撮影方向を見た様子を表す仮想空間画像５４を生成する（Ｓ４０３）。
【０１１７】
そして可視ポリゴン特定部９０が、Ｓ４０３に示す処理で生成された仮想空間画像５４に基づいて、仮想カメラ５２から可視である可視ポリゴン３４ｄを特定する（Ｓ４０４）。
【０１１８】
そして可視ポリゴン特定部９０が、Ｓ４０４に示す処理で特定された可視ポリゴン３４ｄのポリゴンＩＤを可視ポリゴンＩＤリストに追加する（Ｓ４０５）。なお本処理例では、可視ポリゴンＩＤリストにポリゴンＩＤが追加される際に、初期値が０である法線反転カウント値が当該ポリゴンＩＤに関連付けられることとする。
【０１１９】
そして法線方向修正部９２は、Ｓ１２０に示す処理で特定された可視ポリゴン３４ｄのそれぞれについて、仮想カメラ５２による撮影方向のベクトルＶ１と当該可視ポリゴン３４ｄの法線方向のベクトルＶ２との内積の値を計算する（Ｓ４０６）。
【０１２０】
そして法線方向修正部９２は、Ｓ４０５に示す処理で計算される内積の値に応じて、可視ポリゴンＩＤリストに含まれるポリゴンＩＤに関連付けられている法線反転カウント値を更新する（Ｓ４０７）。ここで例えば、計算された内積の値が正である可視ポリゴン３４ｄのポリゴンＩＤに関連付けられている法線反転カウント値は１増加される。また、計算された内積の値が負である可視ポリゴン３４ｄのポリゴンＩＤに関連付けられている法線反転カウント値は１減少される。
【０１２１】
そして不可視ポリゴン削除部９４が、Ｓ４０３〜Ｓ４０７に示す処理が予め定められた回数だけ繰り返し実行されたか否かを確認する（Ｓ４０８）。ここで実行回数が予め定められた回数に達していないことが確認されたとする（Ｓ４０８：Ｎ）。この場合は、仮想カメラ配置部８６が、仮想空間３２内における、ポリゴンモデルを望む仮想カメラ５２の位置、及び、仮想カメラ５２の撮影方向を変更して（Ｓ４０９）、Ｓ４０３に示す処理に戻る。ここで位置及び撮影方向は、ランダムに変更されてもよいし、ユーザが指定した位置及び撮影方向に変更されてもよい。
【０１２２】
Ｓ４０８に示す処理において、実行回数が予め定められた回数に達したことが確認されたとする（Ｓ４０８：Ｙ）。この場合、法線方向修正部９２が、可視ポリゴン特定部９０が保持する可視ポリゴンＩＤリストに含まれるポリゴンＩＤのうちから、関連付けられている法線反転カウント値が正であるポリゴンＩＤを特定する（Ｓ４１０）。
【０１２３】
そして法線方向修正部９２は、ポリゴンモデルデータ記憶部６４に記憶されている、Ｓ４０９に示す処理で特定されたポリゴンＩＤを含むポリゴンデータが表す法線方向を反転させる（Ｓ４１１）。Ｓ４１１に示す処理では例えば、法線方向修正部９２が、Ｓ４１０に示す処理で特定されたポリゴンＩＤを含むポリゴンデータの頂点データに含まれる３つの点ＩＤのうち２番目の点ＩＤと３番目の点ＩＤの順序を入れ替える。
【０１２４】
そして不可視ポリゴン削除部９４が、可視ポリゴン特定部９０が保持する可視ポリゴンＩＤリスト及びポリゴンモデルデータ記憶部６４に記憶されているポリゴンデータに基づいて、不可視ポリゴンを特定する（Ｓ４１２）。
【０１２５】
そして不可視ポリゴン削除部９４が、Ｓ４１１に示す処理で特定された不可視ポリゴンのポリゴンＩＤを含むポリゴンデータを、ポリゴンモデルデータ記憶部６４に記憶されているポリゴンモデルデータから削除する（Ｓ４１３）。そして不可視ポリゴン削除処理（Ｓ１０７）は終了される。
【０１２６】
なお図１７に示す処理例において、Ｓ４０６、Ｓ４０７、Ｓ４１０、及び、Ｓ４１１に示す処理が、上述の法線方向修正処理に相当する。
【０１２７】
以上で説明した処理例において、例えば、Ｓ１０５に示す長辺ポリゴン削除処理が実行されずに、Ｓ１０６に示す交差ポリゴン削除処理が実行されてもよい。またＳ１０５に示す長辺ポリゴン削除処理の代わりに、所定長よりも長い辺４２を含むポリゴン３４を一律で削除する処理が実行されてもよい。また所定長よりも長い辺４２を含むポリゴン３４を一律で削除する処理が実行された後に、Ｓ１０５に示す長辺ポリゴン削除処理が実行されてもよい。
【０１２８】
またＳ３０５に示す処理が実行されず、Ｓ３０４に示す処理で特定されたすべての点３６について、Ｓ３０６、Ｓ３０７に示す処理が実行されてもよい。
【０１２９】
また上述のＳ４０３〜Ｓ４０９に示す処理が繰り返し処理として実行されるのではなく、Ｓ４０２に示す処理で仮想カメラ５２の位置及び仮想カメラ５２の撮影方向が複数決定されるようにした上で、Ｓ４０３〜Ｓ４０７に示す処理が並列処理で実行されてもよい。
【０１３０】
またＳ１０５に示す長辺ポリゴン削除処理やＳ１０６に示す交差ポリゴン削除処理が実行されていないポリゴンモデルに対して、Ｓ１０７に示す不可視ポリゴン削除処理が実行されてもよい。またＳ１０６に示す交差ポリゴン削除処理が実行された後にＳ１０７に示す不可視ポリゴン削除処理が実行されなくてもよい。
【０１３１】
なお、本発明は上述の実施形態に限定されるものではない。
【０１３２】
また、上記の具体的な文字列や数値及び図面中の具体的な文字列や数値は例示であり、これらの文字列や数値には限定されない。
【図１】
0006700480.tif 000002
【図２】
0006700480.tif 000003
【図３】
0006700480.tif 000004
【図４】
0006700480.tif 000005
【図５】
0006700480.tif 000006
【図６】
0006700480.tif 000007
【図７】
0006700480.tif 000008
【図８】
0006700480.tif 000009
【図９】
0006700480.tif 000010
【図１０】
0006700480.tif 000011
【図１１】
0006700480.tif 000012
【図１２Ａ】
0006700480.tif 000013
【図１２Ｂ】
0006700480.tif 000014
【図１３】
0006700480.tif 000015
【図１４】
0006700480.tif 000016
【図１５】
0006700480.tif 000017
【図１６】
0006700480.tif 000018
【図１７】
0006700480.tif 000019