(57)【要約】 【課題】仮想空間に配置される複数のポリゴンからなるオブジェクトを分割した様子を表す画像を生成する画像処理装置等を提供する。【解決手段】画像処理装置８０１において、記憶部８０２にはオブジェクトの基本姿勢におけるボーン、制御点、グループの情報が記憶され、ボーン移動部８０３がボーンの移動先を求め、制御点移動部８０４がボーンの移動に付随して制御点の移動先を求め、配置部８０５は制御点が属するグループの基準位置等に基づいて頂点の位置を求めて頂点を結ぶポリゴンを仮想空間に配置し、選択部８０６は分割面と交差するポリゴンを選択し、分割部８０７は選択されたポリゴンの辺を分割面が内分する内分比に基づいて、記憶部８０２の制御点、グループの情報を必要最小限だけ書き換え、グループ移動部８０９は各グループの基準位置等を移動し、生成部８０８は仮想空間に配置されたポリゴンの様子を表す画像を生成する。【選択図】図１３
2011065492.tif 000002
【特許請求の範囲】
【請求項１】
互いに連結された複数のボーンの初期位置および初期向きと、複数の制御点の初期位置と、当該複数の制御点のそれぞれが前記複数のボーンのそれぞれに依存する重みを表す依存情報と、複数のポリゴンのそれぞれが前記複数の制御点のいずれを頂点とするかを表す頂点情報と、前記複数のポリゴンのそれぞれがいずれのグループに属するかを表すグループ情報と、前記グループのそれぞれに対する仮想空間内の基準位置および基準向きと、が記憶される記憶部、
前記複数のボーンが互いに連結される相対的な向きを変化させるときの、前記複数のボーンのそれぞれの前記初期位置および前記初期向きからの位置ならびに向きの変化量（以下「ボーン変化量」という。）を求めるボーン移動部、
前記複数の制御点のそれぞれについて、前記複数のボーンのそれぞれが前記求められた変化量だけ移動するのに連動して、当該制御点の位置を前記記憶される初期位置から移動するときの、当該制御点の位置の変化量（以下「連動変化量」という。）を求め、当該求められた連動変化量のそれぞれに、当該制御点が当該ボーンに依存する重みを適用して重み付き平均をとることにより、当該制御点の位置の変化量（以下「制御点変化量」という。）を求める制御点移動部、
前記複数のポリゴンのそれぞれについて、当該ポリゴンが属するグループに対する基準位置および基準向きに対する当該ポリゴンの頂点の相対的な位置を、当該頂点に対する制御点について前記求められた制御点変化量とすることにより、当該ポリゴンを当該仮想空間内に配置する配置部、
前記複数のポリゴンのうち、同じグループに属するポリゴンについて、当該ポリゴンの有する辺が前記仮想空間に配置された分割面と交差するポリゴンを選択する選択部、
前記選択されたポリゴンにおいて、前記分割面と交差する辺の交点が、当該辺の頂点の間を内分する内分比を求め、当該辺の頂点とされる制御点について前記記憶部に記憶される初期位置の間を、当該求められた内分比で内分する位置（以下「内分位置」という。）を求め、当該求められた内分位置を新たな制御点の初期位置として、前記記憶部に記憶させ、当該辺の頂点とされる制御点に対する依存情報を当該混合して、当該混合した結果を、当該新たな制御点に対する依存情報として、前記記憶部に記憶させ、前記選択されたポリゴンに対する頂点情報を、前記記憶部から削除することにより、分割されたポリゴンを消去し、前記選択されたポリゴンを前記分割面により分割することにより得られる新たなポリゴンの頂点を、前記分割面により分割されない辺の頂点とされる制御点ならびに前記分割面により分割される辺の交点に対する制御点とする頂点情報を、前記記憶部に記憶させることにより、新たなポリゴンを生成し、前記記憶部に記憶される分割面と交差するポリゴンが属するグループに対するグループ情報を、前記分割面に対して当該ポリゴンの頂点がいずれの側にあるか、ならびに、当該ポリゴンが共通する辺を有することにより連結されているか、により、複数のグループ情報に分割し、当該複数のグループ情報に対する基準位置および基準向きを、当該分割前のグループ情報に対する基準位置および基準向きとする分割部
を備えることを特徴とする画像生成装置。
【請求項２】
請求項１に記載の画像生成装置であって、
前記記憶部に記憶されるグループ情報のそれぞれに対する基準位置および基準向きを変化させ、前記配置部に前記複数のポリゴンを再度配置させるグループ移動部、
前記仮想空間に配置された複数のポリゴンを、当該仮想空間に配置される視点から当該仮想空間に配置される視線の方向に見た様子を表す画像を生成する生成部
をさらに備えることを特徴とする画像生成装置。
【請求項３】
請求項１または２に記載の画像生成装置であって、
前記分割部は、前記分割面と交差する辺の頂点に対する依存情報のそれぞれの重みを前記内分比で内分することにより当該依存情報を混合して、当該内分された結果の依存情報を前記新たな制御点に対する依存情報とする
ことを特徴とする画像生成装置。
【請求項４】
請求項３に記載の画像生成装置であって、
前記依存情報のそれぞれにおいて、非０である重みの個数には上限があり、前記内分された結果の依存情報において非０である重みの個数が当該上限を超える場合、当該重みが小さい順に、当該重みを０に修正して、前記混合結果の依存情報における非０である重みの個数を当該上限とする
ことを特徴とする画像生成装置。
【請求項５】
請求項１から４のいずれか１項に記載の画像生成装置であって、
前記複数のポリゴンはいずれも三角形であり、
前記選択されたポリゴンが、点Ａ、Ｂ、Ｃを頂点とする三角形ＡＢＣであり、辺ＡＢが、交点Ｄで分割され、辺ＡＣが、交点Ｅで分割され、角ＥＤＣと角ＤＣＢの和が角ＤＥＢと角ＥＢＣの和以下である場合、前記新たなポリゴンを、三角形ＡＤＥ、三角形ＤＥＢ、三角形ＥＢＣとする
ことを特徴とする画像生成装置。
【請求項６】
請求項１から５のいずれか１項に記載の画像生成装置であって、
前記複数のボーンは、各ボーンをノードとし、連結された２つのボーンのうち、一方のボーンを親ノードに、他方のボーンを子ノードに、それぞれ割り当てた木構造に階層化され、親ノードのボーン（以下「親ボーン」という。）に固定された座標系における子ノードのボーン（以下「子ボーン」という。）が当該親ボーンに連結される連結点の座標、ならびに、当該子ボーンの向きを表すオイラー角もしくはクォータニオンにより、当該子ボーンの初期位置および初期向きが表現され、
前記ボーン移動部は、前記子ボーンの向きを表すオイラー角もしくはクォータニオンを変化させることにより、当該親ボーンに対する当該子ボーンの相対的な向きを変化させる
ことを特徴とする画像生成装置。
【請求項７】
互いに連結された複数のボーンの初期位置および初期向きと、複数の制御点の初期位置と、当該複数の制御点のそれぞれが前記複数のボーンのそれぞれに依存する重みを表す依存情報と、複数のポリゴンのそれぞれが前記複数の制御点のいずれを頂点とするかを表す頂点情報と、前記複数のポリゴンのそれぞれがいずれのグループに属するかを表すグループ情報と、前記グループのそれぞれに対する仮想空間内の基準位置および基準向きと、が記憶される記憶部、ボーン移動部、制御点移動部、配置部、選択部、分割部、を有する画像処理装置が実行する画像処理方法であって、
前記ボーン移動部が、前記複数のボーンが互いに連結される相対的な向きを変化させるときの、前記複数のボーンのそれぞれの前記初期位置および前記初期向きからの位置ならびに向きの変化量（以下「ボーン変化量」という。）を求めるボーン移動工程、
前記制御点移動部が、前記複数の制御点のそれぞれについて、前記複数のボーンのそれぞれが前記求められた変化量だけ移動するのに連動して、当該制御点の位置を前記記憶される初期位置から移動するときの、当該制御点の位置の変化量（以下「連動変化量」という。）を求め、当該求められた連動変化量のそれぞれに、当該制御点が当該ボーンに依存する重みを適用して重み付き平均をとることにより、当該制御点の位置の変化量（以下「制御点変化量」という。）を求める制御点移動工程、
前記配置部が、前記複数のポリゴンのそれぞれについて、当該ポリゴンが属するグループに対する基準位置および基準向きに対する当該ポリゴンの頂点の相対的な位置を、当該頂点に対する制御点について前記求められた制御点変化量とすることにより、当該ポリゴンを当該仮想空間内に配置する配置工程、
前記選択部が、前記複数のポリゴンのうち、同じグループに属するポリゴンについて、当該ポリゴンの有する辺が前記仮想空間に配置された分割面と交差するポリゴンを選択する選択工程、
前記分割部が、前記選択されたポリゴンにおいて、前記分割面と交差する辺の交点が、当該辺の頂点の間を内分する内分比を求め、当該辺の頂点とされる制御点について前記記憶部に記憶される初期位置の間を、当該求められた内分比で内分する位置（以下「内分位置」という。）を求め、当該求められた内分位置を新たな制御点の初期位置として、前記記憶部に記憶させ、当該辺の頂点とされる制御点に対する依存情報を当該混合して、当該混合した結果を、当該新たな制御点に対する依存情報として、前記記憶部に記憶させ、前記選択されたポリゴンに対する頂点情報を、前記記憶部から削除することにより、分割されたポリゴンを消去し、前記選択されたポリゴンを前記分割面により分割することにより得られる新たなポリゴンの頂点を、前記分割面により分割されない辺の頂点とされる制御点ならびに前記分割面により分割される辺の交点に対する制御点とする頂点情報を、前記記憶部に記憶させることにより、新たなポリゴンを生成し、前記記憶部に記憶される分割面と交差するポリゴンが属するグループに対するグループ情報を、前記分割面に対して当該ポリゴンの頂点がいずれの側にあるか、ならびに、当該ポリゴンが共通する辺を有することにより連結されているか、により、複数のグループ情報に分割し、当該複数のグループ情報に対する基準位置および基準向きを、当該分割前のグループ情報に対する基準位置および基準向きとする分割工程
を備えることを特徴とする画像生成方法。
【請求項８】
コンピュータを、
互いに連結された複数のボーンの初期位置および初期向きと、複数の制御点の初期位置と、当該複数の制御点のそれぞれが前記複数のボーンのそれぞれに依存する重みを表す依存情報と、複数のポリゴンのそれぞれが前記複数の制御点のいずれを頂点とするかを表す頂点情報と、前記複数のポリゴンのそれぞれがいずれのグループに属するかを表すグループ情報と、前記グループのそれぞれに対する仮想空間内の基準位置および基準向きと、が記憶される記憶部、
前記複数のボーンが互いに連結される相対的な向きを変化させるときの、前記複数のボーンのそれぞれの前記初期位置および前記初期向きからの位置ならびに向きの変化量（以下「ボーン変化量」という。）を求めるボーン移動部、
前記複数の制御点のそれぞれについて、前記複数のボーンのそれぞれが前記求められた変化量だけ移動するのに連動して、当該制御点の位置を前記記憶される初期位置から移動するときの、当該制御点の位置の変化量（以下「連動変化量」という。）を求め、当該求められた連動変化量のそれぞれに、当該制御点が当該ボーンに依存する重みを適用して重み付き平均をとることにより、当該制御点の位置の変化量（以下「制御点変化量」という。）を求める制御点移動部、
前記複数のポリゴンのそれぞれについて、当該ポリゴンが属するグループに対する基準位置および基準向きに対する当該ポリゴンの頂点の相対的な位置を、当該頂点に対する制御点について前記求められた制御点変化量とすることにより、当該ポリゴンを当該仮想空間内に配置する配置部、
前記複数のポリゴンのうち、同じグループに属するポリゴンについて、当該ポリゴンの有する辺が前記仮想空間に配置された分割面と交差するポリゴンを選択する選択部、
前記選択されたポリゴンにおいて、前記分割面と交差する辺の交点が、当該辺の頂点の間を内分する内分比を求め、当該辺の頂点とされる制御点について前記記憶部に記憶される初期位置の間を、当該求められた内分比で内分する位置（以下「内分位置」という。）を求め、当該求められた内分位置を新たな制御点の初期位置として、前記記憶部に記憶させ、当該辺の頂点とされる制御点に対する依存情報を当該混合して、当該混合した結果を、当該新たな制御点に対する依存情報として、前記記憶部に記憶させ、前記選択されたポリゴンに対する頂点情報を、前記記憶部から削除することにより、分割されたポリゴンを消去し、前記選択されたポリゴンを前記分割面により分割することにより得られる新たなポリゴンの頂点を、前記分割面により分割されない辺の頂点とされる制御点ならびに前記分割面により分割される辺の交点に対する制御点とする頂点情報を、前記記憶部に記憶させることにより、新たなポリゴンを生成し、前記記憶部に記憶される分割面と交差するポリゴンが属するグループに対するグループ情報を、前記分割面に対して当該ポリゴンの頂点がいずれの側にあるか、ならびに、当該ポリゴンが共通する辺を有することにより連結されているか、により、複数のグループ情報に分割し、当該複数のグループ情報に対する基準位置および基準向きを、当該分割前のグループ情報に対する基準位置および基準向きとする分割部
として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想空間に配置される複数のポリゴンからなるオブジェクトをある分割面で分割した様子を表す画像を生成するのに好適な画像処理装置、画像処理方法、ならびに、これらをコンピュータにて実現するプログラムに関する。
【背景技術】
【０００２】
従来から、仮想空間内に配置されるオブジェクトの外観を表す画像を生成する技術が種々提案されている。たとえば、特許文献１に開示される技術では、オブジェクトの形状が、ボーン、制御点、頂点、ポリゴンを用いて形成される。
【０００３】
ボーンは、人間でいう骨に相当するものであり、ボーン同士は、連結点で互いに連結される。隣接するボーン同士の相対的な位置や向きを変化させると、オブジェクトの概形が変形する。
【０００４】
典型的には、ボーンは、ボーンをノードとする木構造的な階層によって管理される。木構造の根ノードに対するボーン（以下「根ボーン」という。）の位置や向きは、仮想空間におけるオブジェクト全体の位置や向きを表す。親ノードのボーン（以下「親ボーン」という。）と子ノードのボーン（以下「子ボーン」という。）は直接連結されており、親ボーンに対する子ボーンの向きを変化させることで、ボーン同士の相対的な位置や向きを変化させる。
【０００５】
オブジェクトの外観は、ボーンの変形に伴って移動する頂点を結ぶポリゴンにテクスチャを貼ることによって形成される。このポリゴンによって形成される表面をスキンと呼ぶ。
【０００６】
各ボーンには、複数の制御点が対応付けられており、これらの制御点は、そのボーンと連動して動作する。すなわち、ボーンが位置や向きを変えたとしても、制御点のボーンに対する相対的な位置は、変化しない。
【０００７】
各頂点は、複数の制御点に重み付きで対応付けられている。ボーンが位置や向きを変化させたときの各頂点の位置は、その頂点に対応付けられた制御点の位置に、重みを付けて平均した位置とする。
【０００８】
また、各ボーンには初期位置、初期向きが定められており、ボーンが初期位置、初期向きをとるときには、各頂点と、その頂点に対応付けられる制御点と、が、同じ位置で重なるように構成するのが典型的である。
【０００９】
このような処理を行うことで、オブジェクトが変形したときに、スキンに不自然なくびれや潰れが生じることを防止することができる。
【００１０】
このようなオブジェクトは、仮想空間内に配置されるキャラクターやモンスターが互いに戦闘するようなゲーム等において、キャラクターやモンスターの外観を表す際にも使用されている。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特許第４０１１２８５号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
ここで、現実世界においては、とかげの尻尾を切断した場合には、とかげ本体も切断された尻尾単体も、そのまま動き続けることがある。ゲームにおいても、キャラクターがモンスターを刀で攻撃した場合に、同様の表現を行いたい、という要望がある。
【００１３】
一般に、仮想空間に配置されたオブジェクトが分割面（切断面）によって分割（切断）される際に、分割されて互いに離間することとなった複数のオブジェクトの様子を、適切に画像表現できるようにしたい、という要望は強い。
【００１４】
さらに、オブジェクトが分割された場合であっても、必要な情報はできるだけ再利用して、メモリ使用量を抑制したい、という要望もある。
【００１５】
本発明は、上記のような課題を解決するもので、仮想空間に配置される複数のポリゴンからなるオブジェクトをある分割面で分割した様子を表す画像を生成するのに好適な画像処理装置、画像処理方法、ならびに、これらをコンピュータにて実現するプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１６】
以上の目的を達成するため、本発明の原理にしたがって、下記の発明を開示する。
【００１７】
本発明の第１の観点に係る画像処理装置は、記憶部、ボーン移動部、制御点移動部、配置部、選択部、分割部、生成部、グループ移動部を備え、以下のように構成する。
【００１８】
すなわち、記憶部には、以下の情報が記憶される。
（ａ）互いに連結された複数のボーンの初期位置および初期向き。
（ｂ）複数の制御点の初期位置。
（ｃ）複数の制御点のそれぞれが複数のボーンのそれぞれに依存する重みを表す依存情報。
（ｄ）複数のポリゴンのそれぞれが複数の制御点のいずれを頂点とするかを表す頂点情報。
（ｅ）複数のポリゴンのそれぞれがいずれのグループに属するかを表すグループ情報。
（ｆ）グループのそれぞれに対する仮想空間内の基準位置および基準向き。
【００１９】
ここで、分割前のオブジェクトの外観は、１つのグループに属するポリゴンによって形成されるが、このオブジェクトが２つに分割されると、ポリゴンが属するグループも２つになる。また、切断された各部分が独立して移動できるようにするため、グループごとに、基準位置と基準向きが定められる。
【００２０】
一方で、各情報が分類されて記憶されることにより、後述するように、オブジェクトが分割された場合であっても、各情報のコピーや削除、書き換えをできるだけしないようにする。
【００２１】
一方、ボーン移動部は、複数のボーンが互いに連結される相対的な向きを変化させるときの、複数のボーンのそれぞれの初期位置および初期向きからの位置ならびに向きの変化量（以下「ボーン変化量」という。）を求める。
【００２２】
ボーンの移動は、ユーザの指示に基づいて行われることもあるし、時間経過にあらかじめ対応付けられた変化量に基づいて行われることもあるし、あるアルゴリズムや乱数にしたがって行われることもある。各ボーンについてボーン変化量を決定する手法には、たとえば以下に掲げる手法等、種々の態様を採用することができる。
（ａ）木構造において、親ボーンから子ボーンへ、の方向に位置や向きの変化量が伝播していくフォワードキネマティクス法。
（ｂ）木構造において、葉ノードのボーン（以下「葉ボーン」という。）を目的位置に移動させ、根ボーンに向かって位置や向きの変化量を伝播させるインバースキネマティクス法。
【００２３】
複数のボーンから構成されるオブジェクト全体の仮想空間内における位置や向きは、オブジェクト全体に対応するグループの基準位置や基準向きにより表現される。
【００２４】
また、基準位置や基準向きは、仮想空間内における根ボーンの位置や向きを表す情報でもある。
【００２５】
したがって、ボーン変化量として、根ボーンに固定された座標系における各ボーンの座標値そのものを利用することも可能である。
【００２６】
さらに、制御点移動部は、以下の機能を果たす。
（ａ）複数の制御点のそれぞれについて、複数のボーンのそれぞれが求められた変化量だけ移動するのに連動して、当該制御点の位置を記憶される初期位置から移動するときの、当該制御点の位置の変化量（以下「連動変化量」という。）を求める。
（ｂ）当該求められた連動変化量のそれぞれに、当該制御点が当該ボーンに依存する重みを適用して重み付き平均をとることにより、当該制御点の位置の変化量（以下「制御点変化量」という。）を求める。
【００２７】
たとえば、制御点がN個、ボーンがM個用意されている状況を考える。j番目のボーンが移動したときに、j番目のボーンに対する相対的な位置が変化しないように、i番目の制御点を移動したときの連動変化量を表すベクトルをr[i,j]とする。また、i番目の制御点がj番目のボーンに依存する重みをw[i,j]とする。
【００２８】
すると、i番目の制御点の制御点変化量は、
〔Σj=1M w[i,j]r[i,j]〕/〔Σj=1M w[i,j]〕
のように計算することができる。
【００２９】
制御点変化量は、その制御点に対応付けられる頂点の位置や向きの変化を表すベクトルである。
【００３０】
なお、w[i,j] = 0の場合、i番目の制御点はj番目のボーンに依存しないこととなるので、この場合にはr[i,j]を求める必要はない。
【００３１】
多くの場合、制御点が依存するボーンの数は、１個〜４個程度とすれば十分である。そこで、後述するように、制御点が依存するボーンの数には、上限を設けるのが典型的である。
【００３２】
さらに、配置部は、複数のポリゴンのそれぞれについて、当該ポリゴンが属するグループに対する基準位置および基準向きに対する当該ポリゴンの頂点の相対的な位置を、当該頂点に対する制御点について求められた制御点変化量とすることにより、当該ポリゴンを当該仮想空間内に配置する。
【００３３】
制御点変化量は、基準位置および基準向きに対する相対的な位置および向きに相当する情報である。また、上記のように、基準位置および基準向きは、ポリゴンが属するグループごとに定められる。
【００３４】
そこで、あるポリゴンを仮想空間内に配置する際には、まず、そのポリゴンが属するグループを調べ、そのグループの基準位置および基準向きを取得する。ついで、そのポリゴンの頂点に対する制御点を調べ、その制御点の制御点変化量を取得する。
【００３５】
すると、仮想空間内の頂点の位置および向きは、
（ａ）基準位置および基準向きと、
（ｂ）頂点の初期位置および初期向きと、
（ｃ）制御点変化量と、
を座標変換することによって得られることになる。
【００３６】
なお、上記のように、頂点の初期位置および初期向きを、根ボーンの初期位置および初期向きと一致させる手法もありうる。この場合は、基準位置および基準向きに制御点変化量を加算すれば、仮想空間内における位置および向きが得られる。
【００３７】
１つの頂点は、一般には、複数のポリゴンで共有される。また、ある頂点を共有するポリゴンは、同じグループに属する場合が殆どである。したがって、
（ａ）どのグループを基準として頂点の位置を得たか、の情報と、
（ｂ）得られた頂点の位置と、
を対応付けてキャッシュすることにより、計算量を抑制することができる。
【００３８】
上記の構成によって、グループごとに分類されたポリゴンが、仮想空間内に配置されることになるので、後述するように、仮想空間内の様子をあらわす画像を生成することができる。
【００３９】
複数のボーン全体の情報をあるグループのポリゴンと、別のグループのポリゴンと、が、共有することもできる。たとえば、２つに分離可能なオブジェクトを考える。
【００４０】
当該オブジェクトの概形は、一群のボーン情報によって表現される。このオブジェクトが分離している場合には、各グループの基準位置と基準向きが異なる。このオブジェクトが分離しておらず一体となっている場合には、各グループの基準位置と基準向きが一致している。
【００４１】
すなわち、オブジェクトが分割されているか否かに関わらず、ボーンに関する情報そのものを、追加したり削除したり分離したり複製したりする必要がない。これは、本発明の特徴の一つである。
【００４２】
そして、選択部は、複数のポリゴンのうち、同じグループに属するポリゴンについて、当該ポリゴンの有する辺が仮想空間に配置された分割面と交差するポリゴンを選択する。
【００４３】
同じグループに属するポリゴンは、互いの相対的な位置を変化させることはあるものの、仮想空間内を一体となって移動する。分割面は、これらのポリゴンを、複数のグループに分割する。
【００４４】
分割面は、仮想空間内に配置されているポリゴンと交差するのであるから、分割面が切断するのは、基準位置・基準姿勢ならびに初期位置・初期姿勢のオブジェクトの表面を構成するポリゴンではなく、仮想空間内で移動したり変形したりしたオブジェクトの表面を構成するポリゴンである。
【００４５】
たとえば、敵キャラクターのオブジェクトが刀によって切断された場合を考える。この場合、刀の移動の軌跡が分割面に相当し、分割面と交差するポリゴンは、刀と衝突して切り裂かれた皮膚の部位に相当する。
【００４６】
なお、分割面の形状を仮想空間内に配置される円や扇型あるいは平面等、平らな形状とすれば、交差判定の計算を容易にすることができる。
【００４７】
一方、分割部は、以下の機能を果たす。
（ａ）選択されたポリゴンにおいて、分割面と交差する辺の交点が、当該辺の頂点の間を内分する内分比を求める。
（ｂ）当該辺の頂点とされる制御点について記憶部に記憶される初期位置の間を、当該求められた内分比で内分する位置（以下「内分位置」という。）を求める。
（ｃ）当該求められた内分位置を新たな制御点の初期位置として、記憶部に記憶させる。
（ｄ）当該辺の頂点とされる制御点に対する依存情報を当該混合して、当該混合した結果を、当該新たな制御点に対する依存情報として、記憶部に記憶させる。
（ｅ）選択されたポリゴンに対する頂点情報を、記憶部から削除することにより、分割されたポリゴンを消去する。
（ｆ）選択されたポリゴンを分割面により分割することにより得られる新たなポリゴンの頂点を、分割面により分割されない辺の頂点とされる制御点ならびに分割面により分割される辺の交点に対する制御点とする頂点情報を、記憶部に記憶させることにより、新たなポリゴンを生成する。
（ｇ）記憶部に記憶される分割面と交差するポリゴンが属するグループに対するグループ情報を、分割面に対して当該ポリゴンの頂点がいずれの側にあるか、ならびに、当該ポリゴンが共通する辺を有することにより連結されているか、により、複数のグループ情報に分割する。
（ｈ）当該複数のグループ情報に対する基準位置および基準向きを、当該分割前のグループ情報に対する基準位置および基準向きとする。
【００４８】
上記（ａ）において選択されたポリゴンとは、分割面と交差したポリゴンのことである。ポリゴンが凸な多角形で構成されており、分割面が平面状の形状である場合、ポリゴンの辺のうち２つが分割面と交差する。また、その交点を結ぶ線分が、分割面とポリゴンとが交差する線分に相当する。
【００４９】
なお、ポリゴンの頂点が交点と偶然一致した場合には、当該頂点から伸びる２つの辺のうちいずれか一方を任意に選択し、当該交点は選択された辺を０対１に内分する、と考えれば良い。
【００５０】
上記（ｂ）では、オブジェクトが移動・変形した後のポリゴンが分割面と交差する割合に基づいて、変形後のポリゴンの交点が、変形前のポリゴンのどの位置に相当するか、を求めている。
【００５１】
上記のように、ポリゴンの頂点の位置は、１つまたは複数のボーン変化量に依存する。したがって、ここで得られる内分位置は、変形前のポリゴンの辺が切断される位置を近似するものである。
【００５２】
上記（ｃ）では、内分位置を初期位置とする新たな制御点を追加しており、上記（ｄ）では、追加される制御点が、どのような重みでどのボーンに依存するか、を定めている。
【００５３】
新たな制御点の位置は、ポリゴンの辺を、上記（ａ）で得られた内分比で内分することによって得られる。
【００５４】
また、新たな制御点がj番目のボーンに依存する重みを求めるためには、後述する内分比を用いる手法のほか、以下のような手法を混合に用いることができる。
（１）新たな制御点が内分する２つの頂点のうち、当該内分点に近い方の頂点の重みをそのまま利用する手法。
（２）ボーンごとに、新たな制御点が内分する２つの頂点の重みの平均を用いる手法。
（３）ボーンごとに、新たな制御点が内分する２つの頂点の重みのうち大きい方を、採用する手法。
（４）ボーンごとに、新たな制御点が内分する２つの頂点の重みのいずれかを、ランダムに採用する手法。
【００５５】
上記（ｅ）では、分割面と交差するポリゴンの頂点情報を削除している。一方で、分割面と交差するポリゴンの頂点情報は、変更する必要がない。
【００５６】
上記（ｆ）では、削除されたポリゴンにかえて、上記（ｃ）で追加された制御点を頂点に含むようなポリゴンを追加することとしている。
【００５７】
したがって、上記（ｅ）と上記（ｆ）により、分割面に交差するポリゴンが、複数のポリゴンに分割されることになる。
【００５８】
上記（ｇ）は、ポリゴンのグループ分けを行うものである。本発明は、１つのグループに属するポリゴンが分割面により分離される状況を考えている。多くの場合は、分割面によって、１つのグループが２つのグループに分割される。
【００５９】
ただし、分割面の大きさや形状によっては、１つのグループが３つ以上のグループに分割されることもありうるし、切断されたとしても、全体として１つのグループのまま、ということもありうる。
【００６０】
そこで、共通する辺を持つ２つのポリゴンは、互いに連結されている、と考えることとし、この連結性によって、ポリゴンが属するグループを決めることとする。
【００６１】
なお、分割面との交差によって新たに追加された制御点を頂点とする辺は、ポリゴン同士の連結性の判定の対象にはしない。
【００６２】
上記（ｈ）は、グループごとに基準位置と基準向きを定めるものである。切断の直後は、切断後のグループの基準位置と基準向きは一致するので、切断後のグループは、分割面を境界に、互いに密着することになる。
【００６３】
本発明によれば、オブジェクトが移動・変形した後に切断された状況に基づいて、移動・変形がされる前の状況において一部のポリゴンを分割し、ポリゴン全体のグループ分けを再度行うことにより、オブジェクトの位置や形状を定める種々の情報の複製・削除・変更等をできるだけ抑制するとともに、簡易な計算によってオブジェクトの切断をシミュレートすることができるようになる。
【００６４】
また、本発明の画像生成装置は、グループ移動部、生成部をさらに備え、以下のように構成することができる。
【００６５】
すなわち、グループ移動部は、記憶部に記憶されるグループ情報のそれぞれに対する基準位置および基準向きを変化させ、配置部に複数のポリゴンを再度配置させる。
【００６６】
たとえば、時間の経過とともに、両者のずれが大きく変化すると、オブジェクトの切断された部位同士が次第に離間していく状況が再現できる。
【００６７】
一方、生成部は、仮想空間に配置された複数のポリゴンを、当該仮想空間に配置される視点から当該仮想空間に配置される視線の方向に見た様子を表す画像を生成する。
【００６８】
なお、一旦形成されたグループを新たな分割面によって切断する場合にも、上記の構成がそのまま利用できる。たとえば、ゲームにおいてプレイヤーが敵キャラクターに何回も刀を振り下ろして、敵キャラクターを細切れにするような状況に適用することも可能である。
【００６９】
画像の生成が所定の時間間隔で繰り返し行われ、生成されるごとに画像が画面に表示されると、オブジェクトが切断される様子を表す動画が提示されることになる。
【００７０】
本発明によれば、オブジェクトが分割された状況において、グループごとにポリゴンを移動することによって、オブジェクトが切断された様子を表す画像を生成することができるようになる。
【００７１】
また、本発明の画像生成装置であって、分割部は、分割面と交差する辺の頂点に対する依存情報のそれぞれの重みを内分比で内分することにより当該依存情報を混合して、当該内分された結果の依存情報を新たな制御点に対する依存情報とするように構成することができる。
【００７２】
すなわち、内分される辺の頂点がそれぞれp番目、q番目であり、内分比がA:Bであるとする。すると、新たな制御点がj番目のボーンに依存する重みは、
〔B×w[p,j] + A×w[q,j]〕/〔A + B〕
のように計算することができる。
【００７３】
本発明によれば、分割面が辺を切断する内分比に基づいて、内分点をなす新たな制御点の重みを計算することにより、簡易な計算で重みを得ることができるようになる。
【００７４】
また、本発明の画像生成装置において、依存情報のそれぞれにおいて、非０である重みの個数には上限があり、内分された結果の依存情報において非０である重みの個数が当該上限を超える場合、当該重みが小さい順に、当該重みを０に修正して、混合結果の依存情報における非０である重みの個数を当該上限とするように構成することができる。
【００７５】
上記のように、ある制御点が依存するボーンの数に上限を設けた場合、新たな制御点が依存するボーンの数も、その上限を超えないようにしなければならない。
【００７６】
そこで、1番目のボーンに依存する重みからM番目のボーンに依存する重みまでのM個の重みを、大きいものから順に上限の個数まで選ぶことにするのである。
【００７７】
ここで、当該上限をL個とした場合を考える。すると、新たな制御点に対して内分計算によって得られる重みのうち、非０となる重みの個数は、L個〜2×L個のいずれかとなる。
【００７８】
そこで、これらの中から、重みの値が大きい順にL個を選択し、残りについては、重みを０に修正することになる。
【００７９】
なお、ある制御点がM個のボーンに依存する重みは、M個の要素を持つベクトルと考えることができるが、このベクトルの要素の値のほとんどは０である。すなわち、このベクトルは、疎なベクトルである。したがって、このベクトルは、M個の要素を持つ１次元配列として実装するのではなく、非０の重みのインデックスと、そのインデックスに対応する重みと、の対がL個含まれる配列で表現することにより、メモリの使用量を抑制することが可能である。
【００８０】
本発明によれば、制御点が依存するボーンの数を適切に抑制して、計算量やメモリの使用量を抑制することができるようになる。
【００８１】
また、本発明の画像生成装置において、複数のポリゴンはいずれも三角形であり、選択されたポリゴンが、点Ａ、Ｂ、Ｃを頂点とする三角形ＡＢＣであり、辺ＡＢが、交点Ｄで分割され、辺ＡＣが、交点Ｅで分割され、角ＥＤＣと角ＤＣＢの和が角ＤＥＢと角ＥＢＣの和以下である場合、新たなポリゴンを、三角形ＡＤＥ、三角形ＤＥＢ、三角形ＥＢＣとするように構成することができる。
【００８２】
仮想空間内に配置されるオブジェクトの表面を形成するポリゴンは、三角形もしくは四角形で構成されるのが一般的であるが、本発明では、ポリゴンの形状を三角形に限定することとしている。
【００８３】
ここで、三角形の形状が細長くなると、画像を生成した際に、不自然なくびれや潰れが生じやすくなる。
【００８４】
そこで、本発明では、ある三角形を分割して３つの三角形を得る際に、三角形が細長くならないようにするため、頂点を挟む辺同士の角度を利用する。
【００８５】
本発明によれば、ポリゴンを分割する際に、分割後のポリゴンの形状を適切に選択することにより、生成される画像が不自然になることをできるだけ防止することが可能となる。
【００８６】
また、本発明の画像生成装置は、以下のように構成することができる。
【００８７】
すなわち、複数のボーンは、各ボーンをノードとし、連結された２つのボーンのうち、一方のボーンを親ノードに、他方のボーンを子ノードに、それぞれ割り当てた木構造に階層化される。
【００８８】
そして、親ノードのボーン（以下「親ボーン」という。）に固定された座標系における子ノードのボーン（以下「子ボーン」という。）が当該親ボーンに連結される連結点の座標、ならびに、当該子ボーンの向きを表すオイラー角もしくはクォータニオンにより、当該子ボーンの初期位置および初期向きが表現される。
【００８９】
さらに、ボーン移動部は、子ボーンの向きを表すオイラー角もしくはクォータニオンを変化させることにより、当該親ボーンに対する当該子ボーンの相対的な向きを変化させる。
【００９０】
本発明は、上記発明の好適実施形態に係るもので、単体のボーンの位置や姿勢は、そのボーンの親となるボーンに対する相対的な位置や姿勢によって定められる、とするものである。
【００９１】
本発明によれば、ボーンを階層的に管理することで、フォワードキネマティクスやインバースキネマティクスに基づいてオブジェクトの概形を適切に変化させることができるようになる。
【００９２】
本発明のその他の観点に係る画像処理方法は、記憶部、ボーン移動部、制御点移動部、配置部、選択部、分割部、生成部、グループ移動部を有する画像処理装置が実行する。
【００９３】
そして、本発明の画像処理方法は、ボーン移動工程、制御点移動工程、配置工程、選択工程、分割工程を備える。
【００９４】
ここで、記憶部には、互いに連結された複数のボーンの初期位置および初期向きと、複数の制御点の初期位置と、当該複数の制御点のそれぞれが複数のボーンのそれぞれに依存する重みを表す依存情報と、複数のポリゴンのそれぞれが複数の制御点のいずれを頂点とするかを表す頂点情報と、複数のポリゴンのそれぞれがいずれのグループに属するかを表すグループ情報と、グループのそれぞれに対する仮想空間内の基準位置および基準向きと、が記憶される。
【００９５】
一方、ボーン移動工程では、ボーン移動部が、複数のボーンが互いに連結される相対的な向きを変化させるときの、複数のボーンのそれぞれの初期位置および初期向きからの位置ならびに向きの変化量（以下「ボーン変化量」という。）を求める。
【００９６】
さらに、制御点移動工程では、制御点移動部が、複数の制御点のそれぞれについて、複数のボーンのそれぞれが求められた変化量だけ移動するのに連動して、当該制御点の位置を記憶される初期位置から移動するときの、当該制御点の位置の変化量（以下「連動変化量」という。）を求め、当該求められた連動変化量のそれぞれに、当該制御点が当該ボーンに依存する重みを適用して重み付き平均をとることにより、当該制御点の位置の変化量（以下「制御点変化量」という。）を求める。
【００９７】
そして、配置工程では、配置部が、複数のポリゴンのそれぞれについて、当該ポリゴンが属するグループに対する基準位置および基準向きに対する当該ポリゴンの頂点の相対的な位置を、当該頂点に対する制御点について求められた制御点変化量とすることにより、当該ポリゴンを当該仮想空間内に配置する。
【００９８】
一方、選択工程では、選択部が、複数のポリゴンのうち、同じグループに属するポリゴンについて、当該ポリゴンの有する辺が仮想空間に配置された分割面と交差するポリゴンを選択する。
【００９９】
さらに、分割工程では、分割部が、選択されたポリゴンにおいて、分割面と交差する辺の交点が、当該辺の頂点の間を内分する内分比を求め、当該辺の頂点とされる制御点について記憶部に記憶される初期位置の間を、当該求められた内分比で内分する位置（以下「内分位置」という。）を求め、当該求められた内分位置を新たな制御点の初期位置として、記憶部に記憶させ、当該辺の頂点とされる制御点に対する依存情報を当該混合して、当該混合した結果を、当該新たな制御点に対する依存情報として、記憶部に記憶させ、選択されたポリゴンに対する頂点情報を、記憶部から削除することにより、分割されたポリゴンを消去し、選択されたポリゴンを分割面により分割することにより得られる新たなポリゴンの頂点を、分割面により分割されない辺の頂点とされる制御点ならびに分割面により分割される辺の交点に対する制御点とする頂点情報を、記憶部に記憶させることにより、新たなポリゴンを生成し、記憶部に記憶される分割面と交差するポリゴンが属するグループに対するグループ情報を、分割面に対して当該ポリゴンの頂点がいずれの側にあるか、ならびに、当該ポリゴンが共通する辺を有することにより連結されているか、により、複数のグループ情報に分割し、当該複数のグループ情報に対する基準位置および基準向きを、当該分割前のグループ情報に対する基準位置および基準向きとする。
【０１００】
本発明のその他の観点に係るプログラムは、コンピュータを上記の画像処理装置として機能させるように構成する。
【０１０１】
また、本発明のプログラムは、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、半導体メモリ等のコンピュータ読取可能な情報記憶媒体に記録することができる。
【０１０２】
上記プログラムは、プログラムが実行されるコンピュータとは独立して、コンピュータ通信網を介して配布・販売することができる。また、上記情報記憶媒体は、コンピュータとは独立して配布・販売することができる。
【発明の効果】
【０１０３】
本発明によれば、仮想空間に配置される複数のポリゴンからなるオブジェクトをある分割面で分割した様子を表す画像を生成するのに好適な画像処理装置、画像処理方法、ならびに、これらをコンピュータにて実現するプログラムを提供することができる。
【図面の簡単な説明】
【０１０４】
【図１】典型的な情報処理装置の概要構成を示す模式図である。
【図２】本実施形態の画像処理装置にて処理されるオブジェクトのボーン、制御点、頂点の様子を示す説明図である。
【図３】本実施形態の画像処理装置にて処理されるオブジェクトのボーン、制御点、頂点の様子を示す説明図である。
【図４】本実施形態の画像処理装置にて処理されるオブジェクトのスキンをなすポリゴンと頂点の様子を示す説明図である。
【図５】本実施形態の画像処理装置にて処理されるオブジェクトのスキンをなすポリゴンと頂点の様子を示す説明図である。
【図６】オブジェクトが分割面によって切断される状況を表す説明図である。
【図７】オブジェクトが分割面によって切断される状況を表す説明図である。
【図８】変形後に切断されることにより生じた新たなポリゴンと頂点の様子を示す説明図である。
【図９】切断されて生じたポリゴンと頂点の基本姿勢における様子を示す説明図である。
【図１０】オブジェクトの分割後のポリゴンと頂点の基本姿勢における様子を示す説明図である。
【図１１】仮想空間内において各グループが異なる位置、向きに配置された場合の様子を示す説明図である。
【図１２】仮想空間内において各グループが異なる位置、向きに配置された場合の様子を示す説明図である。
【図１３】本実施形態に係る画像処理装置の概要構成を示す模式図である。
【図１４】本実施形態に係る画像処理装置が実行する画像処理の制御の流れを示すフローチャートである。
【図１５】複雑な形状のオブジェクトが切断される様子を示す説明図である。
【図１６】複雑な形状のオブジェクトが切断される様子を示す説明図である。
【図１７】複雑な形状のオブジェクトが切断される様子を示す説明図である。
【図１８】ポリゴンが分離される場合に、どのような分離が考えられるか、を示す説明図である。
【図１９】ポリゴンが分離される場合に、どのような分離が考えられるか、を示す説明図である。
【発明を実施するための形態】
【０１０５】
以下に本発明の実施形態を説明する。以下では、理解を容易にするため、ゲーム用の情報処理装置を利用して本発明が実現される実施形態を説明するが、以下に説明する実施形態は説明のためのものであり、本願発明の範囲を制限するものではない。
【０１０６】
したがって、当業者であればこれらの各要素もしくは全要素をこれと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本発明の範囲に含まれる。
【実施例１】
【０１０７】
図１は、プログラムを実行することにより、本実施形態の画像処理装置として機能しうる典型的な情報処理装置の概要構成を示す模式図である。以下、本図を参照して説明する。
【０１０８】
本図に示す情報処理装置１００は、いわゆるコンシューマゲーム機に相当するもので、ＣＰＵ（Central Processing Unit）１０１、ＲＯＭ（Read Only Memory）１０２、ＲＡＭ（Random Access Memory）１０３、インターフェース１０４、コントローラ１０５、外部メモリ１０６、画像処理部１０７、ＤＶＤ−ＲＯＭ（Digital Versatile Disc ROM）ドライブ１０８、ＮＩＣ（Network Interface Card）１０９、音声処理部１１０、マイク１１１、ハードディスク（Hard Disk；ＨＤ）１２１を有する。各種の入出力装置は、適宜省略することができる。
【０１０９】
情報処理装置１００を典型的なコンシューマゲーム機として機能させる場合には、ゲーム用プログラムおよびデータを記憶したＤＶＤ−ＲＯＭをＤＶＤ−ＲＯＭドライブ１０８に装着し、電源を投入する。すると、当該ゲームプログラムが実行され、ゲームをプレイすることができるようになる。
【０１１０】
ただし、本実施形態においては、典型的には、ＤＶＤ−ＲＯＭドライブ１０８に装着されたＤＶＤ−ＲＯＭから、アプリケーションをＨＤ  １２１にインストールする。そして、当該ＨＤ  １２１に記憶されたプログラムを実行することによって、ゲームを含む各種のアプリケーションを実行することとする。
【０１１１】
なお、携帯型のゲーム装置においては、携帯可能とするために、ＤＶＤ−ＲＯＭドライブ１０８を利用するのではなく、ＲＯＭカセット用スロットにＥＥＰＲＯＭ（Electrically Erasable Programmable ROM）カセットを装着して、ＨＤ  １２１を省略したりすることも可能である。この場合、アプリケーション用プログラムをＥＥＰＲＯＭカセットに書き込んだ上で、当該プログラムを実行することとなる。このほか、外部メモリ１０６にアプリケーション用プログラムをインストールすることも可能である。
【０１１２】
さて、ＣＰＵ  １０１は、情報処理装置１００全体の動作を制御し、各構成要素と接続され制御信号やデータをやりとりする。また、ＣＰＵ  １０１は、レジスタ（図示せず）という高速アクセスが可能な記憶域に対してＡＬＵ（Arithmetic Logic Unit）（図示せず）を用いて加減乗除等の算術演算や、論理和、論理積、論理否定等の論理演算、ビット和、ビット積、ビット反転、ビットシフト、ビット回転等のビット演算などを行うことができる。さらに、マルチメディア処理対応のための加減乗除等の飽和演算や、三角関数等、ベクトル演算などを高速に行えるように、ＣＰＵ  １０１自身が構成されているものや、コプロセッサを備えて実現するものがある。
【０１１３】
ＲＯＭ  １０２には、電源投入直後に実行されるＩＰＬ（Initial Program Loader）が記録され、これが実行されることにより、ＤＶＤ−ＲＯＭに記録されたプログラムをＲＡＭ  １０３に読み出してＣＰＵ  １０１による実行が開始される。また、ＲＯＭ  １０２には、情報処理装置１００全体の動作制御に必要なオペレーティングシステムのプログラムや各種のデータが記録される。
【０１１４】
ＲＡＭ  １０３は、データやプログラムを一時的に記憶するためのもので、ＨＤ  １２１やＤＶＤ−ＲＯＭ等から読み出したプログラムやデータ、その他通信対戦ゲームの進行やチャット通信に必要なデータが保持される。また、ＣＰＵ  １０１は、ＲＡＭ  １０３に変数領域を設け、当該変数に格納された値に対して直接ＡＬＵを作用させて演算を行ったり、ＲＡＭ  １０３に格納された値を一旦レジスタに格納してからレジスタに対して演算を行い、演算結果をメモリに書き戻す、などの処理を行う。
【０１１５】
インターフェース１０４を介して接続されたコントローラ１０５は、ユーザがゲーム実行の際に行う操作入力を受け付ける。
【０１１６】
なお、コントローラ１０５は、必ずしも情報処理装置１００に対して外付けにされている必要はなく、一体に形成されていても良い。携帯可能な端末装置のコントローラ１０５は、各種のボタンやスイッチから構成され、これらの押圧操作を操作入力として扱う。このほか、タッチスクリーンを利用した情報処理装置１００では、ユーザがペンや指を利用してタッチスクリーンをなぞった軌跡を操作入力として扱う。
【０１１７】
インターフェース１０４を介して着脱自在に接続された外部メモリ１０６には、ゲーム等のプレイ状況（過去の成績等）を示すデータ、ゲームの進行状態を示すデータ、ネットワーク対戦の場合のチャット通信のログ（記録）のデータなどが書き換え可能に記憶される。ユーザは、コントローラ１０５を介して指示入力を行うことにより、これらのデータを適宜外部メモリ１０６に記録することができる。
【０１１８】
上述の通り、アプリケーションプログラムを外部メモリ１０６にインストールして実行するような形態を採用することもできる。これは、外部メモリ１０６が大容量である場合に好適である。
【０１１９】
ＤＶＤ−ＲＯＭドライブ１０８に装着されるＤＶＤ−ＲＯＭには、ゲームを実現するためのプログラムとゲームに付随する画像データや音声データが記録される。ＣＰＵ  １０１の制御によって、ＤＶＤ−ＲＯＭドライブ１０８は、これに装着されたＤＶＤ−ＲＯＭに対する読み出し処理を行って、必要なプログラムやデータを読み出し、これらはＲＡＭ  １０３等に一時的に記憶される。
【０１２０】
画像処理部１０７は、ＤＶＤ−ＲＯＭから読み出されたデータをＣＰＵ  １０１や画像処理部１０７が備える画像演算プロセッサ（図示せず）によって加工処理した後、これを画像処理部１０７が備えるフレームメモリ（図示せず）に記録する。フレームメモリに記録された画像情報は、所定の同期タイミングでビデオ信号に変換され画像処理部１０７に接続されるモニタ（図示せず）へ出力される。これにより、各種の画像表示が可能となる。
【０１２１】
携帯可能な端末装置のモニタとしては、小型の液晶ディスプレイを利用するのが典型的であり、コントローラ１０５としてタッチスクリーンを利用する場合には、当該タッチスクリーンの表示パネルがモニタとして機能する。自宅で遊ぶための端末装置やネットワークゲームのサーバ装置のモニタとしては、ＣＲＴ（Cathode Ray Tube）やプラズマディスプレイなどの表示装置を利用することも可能である。
【０１２２】
画像演算プロセッサは、２次元の画像の重ね合わせ演算やαブレンディング等の透過演算、各種の飽和演算を高速に実行できる。
【０１２３】
また、仮想３次元空間に配置され、各種のテクスチャ情報が付加されたポリゴン情報を、Ｚバッファ法によりレンダリングして、所定の視点位置から仮想３次元空間に配置されたポリゴンを所定の視線の方向へ俯瞰したレンダリング画像を得る演算の高速実行も可能である。
【０１２４】
さらに、ＣＰＵ  １０１と画像演算プロセッサが協調動作することにより、文字の形状を定義するフォント情報にしたがって、文字列を２次元画像としてフレームメモリへ描画したり、各ポリゴン表面へ描画することが可能である。
【０１２５】
ＮＩＣ  １０９は、情報処理装置１００をインターネット等のコンピュータ通信網（図示せず）に接続するためのものであり、ＬＡＮを構成する際に用いられる１０ＢＡＳＥ−Ｔ／１００ＢＡＳＥ−Ｔ規格にしたがうものや、電話回線を用いてインターネットに接続するためのアナログモデム、ＩＳＤＮ（Integrated Services Digital Network）モデム、ＡＤＳＬ（Asymmetric Digital Subscriber Line）モデム、ケーブルテレビジョン回線を用いてインターネットに接続するためのケーブルモデム等と、これらとＣＰＵ  １０１との仲立ちを行うインターフェース（図示せず）により構成される。
【０１２６】
また、ＮＩＣ  １０９経由でコンピュータ通信網から入手した情報を元に、ＨＤ  １２１等にアプリケーションプログラムをインストールすることも可能である。
【０１２７】
音声処理部１１０は、ＨＤ  １２１やＤＶＤ−ＲＯＭから読み出した音声データをアナログ音声信号に変換し、これに接続されたスピーカ（図示せず）から出力させる。また、ＣＰＵ  １０１の制御の下、ゲームの進行の中で発生させるべき効果音や楽曲データを生成し、これに対応した音声をスピーカや、ヘッドホン（図示せず）、イヤフォン（図示せず）から出力させる。
【０１２８】
音声処理部１１０では、ＨＤ  １２１やＤＶＤ−ＲＯＭに記録された音声データがＭＩＤＩデータである場合には、これが有する音源データを参照して、ＭＩＤＩデータをＰＣＭデータに変換する。また、ADPCM形式やOgg Vorbis形式等の圧縮済音声データである場合には、これを展開してＰＣＭデータに変換する。ＰＣＭデータは、そのサンプリング周波数に応じたタイミングでＤ／Ａ（Digital/Analog）変換を行って、スピーカに出力することにより、音声出力が可能となる。
【０１２９】
さらに、情報処理装置１００には、インターフェース１０４を介してマイク１１１を接続することができる。この場合、マイク１１１からのアナログ信号に対しては、適当なサンプリング周波数でＡ／Ｄ変換を行い、ＰＣＭ形式のディジタル信号として、音声処理部１１０でのミキシング等の処理ができるようにする。
【０１３０】
本実施形態で利用する情報処理装置１００は、上述のように、ＨＤ  １２１等の大容量外部記憶装置を用いるのが典型的である。ＨＤ  １２１は、ＲＯＭ  １０２、ＲＡＭ  １０３、外部メモリ１０６、ＤＶＤ−ＲＯＭドライブ１０８に装着されるＤＶＤ−ＲＯＭ等と同じ機能を果たすこともできる。
【０１３１】
このほか、ユーザからの文字列の編集入力を受け付けるためのキーボードや、各種の位置の指定および選択入力を受け付けるためのマウスなどを接続する形態も採用することができる。また、本実施形態の情報処理装置１００にかえて、汎用のパーソナルコンピュータやサーバ用コンピュータ等を利用することもできる。
【０１３２】
以上で説明した情報処理装置１００は、コンシューマ向けゲーム装置に相当するものであるが、各種の入出力処理が可能な電子機器であれば、本発明の端末装置やサーバ装置を実現することができる。したがって、携帯電話、携帯ゲーム機器、カラオケ装置、一般的なビジネス用コンピュータなど、種々の計算機上で本発明の端末装置やサーバ装置を実現することが可能である。
【０１３３】
たとえば、ビジネス用コンピュータは、上記情報処理装置１００と同様に、ＣＰＵ、ＲＡＭ、ＲＯＭ、ＤＶＤ−ＲＯＭドライブ、および、ＮＩＣ、ＨＤを構成要素として有するほか、情報処理装置１００よりも簡易な機能を備えた画像処理部を備え、外部記憶装置としてフレキシブルディスク、光磁気ディスク、磁気テープ等が利用できるようになっており、コントローラ１０５ではなく、キーボードやマウスなどを入力装置として利用するのが典型的である。
【０１３４】
図２、図３は、本実施形態の画像処理装置にて処理されるオブジェクトのボーン、制御点、頂点の様子を示す説明図であり、図４、図５は、本実施形態の画像処理装置にて処理されるオブジェクトのスキンをなすポリゴンと頂点の様子を示す説明図である。以下、これらの図を参照して説明する。
【０１３５】
これらの図においては、理解を容易にするため、オブジェクトとして、棒状の形状を有するものを想定している。たとえば、シャクトリムシのようなモンスターを表すものと考えても良いし、人間の上腕から下腕まで、あるいは、腿から脛までを表すものと考えることもできる。
【０１３６】
オブジェクト２０１は、３本のボーン２１１、２１２、２１３によってその概形が定められる。ボーン２１１とボーン２１２は、両者の端点で連結され、ボーン２１２とボーン２１３は、両者の端点で連結されている。
【０１３７】
一般に、キャラクターやモンスターなど、仮想空間に配置される変形するオブジェクトのデザインを行うデザイナーは、そのオブジェクトの最も自然な形状を基本姿勢として採用する。ここで、最も自然な形状とは、一般には、関節の曲がりが少なく、ボーン同士の距離が近付き過ぎないような姿勢で、オブジェクトが人間のような姿態を持つ場合には、両手両足を真っ直に広げた形状を採用することが多い。
【０１３８】
図２、図４は、オブジェクト２０１の基本姿勢に相当するものである。図２を見ればわかるように、ボーン２１１、２１２、２１３は、ほぼ一直線上に並んでいる。
【０１３９】
図３、図５は、オブジェクト２０１が、基本姿勢から変形したものである。図３を見ればわかるように、ボーン２１１そのものの傾きが変化している他、ボーン２１２はボーン２１１に対して傾いており、ボーン２１３はボーン２１２に対して、同じ方向に傾いている。したがって、オブジェクト２０１を全体として見ると、山形に曲がっていることになる。
【０１４０】
ボーン２１１、２１２、２１３には、以下のように、制御点２２１乃至２２９が対応付けられている。なお、本図では、制御点２２１乃至２２９は、×印で表記されている。
（ａ）制御点２２１、２２２は、ボーン２１１のみに依存する。
（ｂ）制御点２２３、２２４は、ボーン２１１、２１２に依存する。
（ｃ）制御点２２５は、ボーン２１１、２１２、２１３に依存する。
（ｄ）制御点２２６、２２７は、ボーン２１２、２１３に依存する。
（ｅ）制御点２２８、２２９は、ボーン２１３に依存する。
【０１４１】
ここで「ある制御点がある１つのボーンに依存する」とは、基本姿勢のときの制御点のボーンに対する相対的な位置が、ボーンの位置や向きが変わったあともそのまま維持されることを意味する。
【０１４２】
また、「ある制御点がある複数のボーンに依存する」とは、基本姿勢のときの制御点が各ボーンに対して分裂して、分裂後の制御点のボーンに対する相対的な位置がボーンの位置や向きが変わったあともそのまま維持されることを意味する。
【０１４３】
図２と図３を比較すると、制御点２２１、２２２は、分裂はしておらず、制御点２２３は、制御点２２３ａ、２２３ｂの２つに分裂しており、制御点２２４は、制御点２２４ａ、２２４ｂの２つに分裂しており、制御点２２５は、制御点２２５ａ、２２５ｂ、２２５ｃの３つに分裂しており、制御点２２６は、制御点２２６ｂ、２２６ｃの２つに分裂しており、制御点２２７は、制御点２２７ｂ、２２７ｃの２つに分裂しており、制御点２２８、２２９は、分裂していない。
【０１４４】
たとえば、２つのボーン２１１、２１２に依存する制御点２２３を考えたとき、図３における制御点２２３ａとボーン２１１の相対的な位置関係は、図２における制御点２２３とボーン２１１の相対的な位置関係と一致している。また、図３における制御点２２３ｂとボーン２１２の相対的な位置関係は、図２における制御点２２３とボーン２１２の相対的な位置関係と一致している。
【０１４５】
このように、基本姿勢からボーンの位置や向きが変わった場合に、そのボーンに依存する制御点が、そのボーンに連動して移動した先を求めるのである。
【０１４６】
さらに、各制御点はポリゴンの頂点に対応付けられている。具体的には、制御点２２１は、頂点２３１に、制御点２２２は、頂点２３２に、制御点２２３（２２３ａ、２２３ｂ）は、頂点２３３に、制御点２２４（２２４ａ、２２４ｂ）は、頂点２３４に、制御点２２５（２２５ａ、２２５ｂ、２２５ｃ）は、頂点２３５に、制御点２２６（２２６ｂ、２２６ｃ）は、頂点２３６に、制御点２２７（２２７ｂ、２２７ｃ）は、頂点２３７に、制御点２２８は、頂点２３８に、制御点２２９は、頂点２３９に、それぞれ対応付けられている。
【０１４７】
そして、制御点が分裂しない場合は、制御点と同じ位置に頂点が配置され、制御点が分裂する場合には、制御点の位置の重み付き平均の位置に頂点が配置される。本図では、重みはいずれも等しく設定された状態を想定しているので、２つの制御点に分裂した場合には、その中点、３つの制御点に分裂した場合には、制御点を頂点とする三角形の重心が頂点の位置となる。
【０１４８】
図４、図５は、頂点２３１乃至２３９により、ポリゴンを配置した様子を表す説明図である。以下、本図を参照して説明する。
【０１４９】
本図に示すように、ポリゴン２４１は、頂点２３１、２３２、２３４を有する三角形であり、ポリゴン２４２は、頂点２３１、２３３、２３４を有する三角形であり、ポリゴン２４３は、頂点２３３、２３４、２３５を有する三角形であり、ポリゴン２４４は、頂点２３３、２３５、２３６を有する三角形であり、ポリゴン２４５は、頂点２３５、２３６、２３７を有する三角形であり、ポリゴン２４６は、頂点２３６、２３７、２３８を有する三角形であり、ポリゴン２４７は、頂点２３７、２３８、２３９を有する三角形である。
【０１５０】
このようにして、オブジェクトが変形した場合であっても、不自然なくびれや潰れが生じないようにして、自然な変形を実現することができるのである。
【０１５１】
なお、オブジェクトを構成するボーンの数、制御点の数、ポリゴンの数、ポリゴンとしてどのような多角形を選択するか、制御点とボーンとの重みは、用途に応じて任意に変更が可能である。
【０１５２】
また、これらのポリゴンは、すべて１つのグループに属しており、仮想空間内では一体となって移動する。
【０１５３】
さて、このように変形されたオブジェクト２０１が平面状の分割面により切断される状況を考える。図６、図７は、オブジェクト２０１が分割面によって切断される状況を表す説明図である。以下、本図を参照して説明する。
【０１５４】
図６に示す例では、分割面３０１とポリゴン２４４、２４５が交差している。すなわち、ポリゴン２４４、２４５は、いずれも、切断によって、複数のポリゴンに分割されることになる。
【０１５５】
また、分割面３０１に交差するポリゴン２４４、２４５を除去して考えると、図７に示すように、ポリゴン２４１、２４２、２４３の一群と、ポリゴン２４６、２４７の一群と、は、分離している。
【０１５６】
これは、分割面３０１から見て異なる側に配置されているとともに、ポリゴン２４１、２４２、２４３は、辺を共有することで連結されており、ポリゴン２４６、２４７は、辺を共有することで連結されているからである。
【０１５７】
一方、ポリゴン２４４、２４５は、分割面３０１と交差することによって、いずれも２つの新たなポリゴンに分割されている。図８は、変形後に切断されることにより生じた新たなポリゴンと頂点の様子を示す説明図である。以下、本図を参照して説明する。
【０１５８】
本図に示すように、分割面３０１とポリゴン２４４、２４５の辺が交差した交点に、新たな頂点４３１、４３２、４３３が配置されており、ポリゴン４４１、４４２、４４３、４４４が形成されることとなっている。
【０１５９】
上記のように、本実施形態においては、
（ａ）基本姿勢において頂点と重なる位置に制御点を配置し、
（ｂ）制御点が依存する各ボーンが移動すると、そのボーンに連動して制御点が移動した先を求め、
（ｃ）制御点の移動先を、依存する重みによって平均化した位置を、変形後の頂点の位置とする。
【０１６０】
したがって、切断によって新たに生じた頂点４３１、４３２、４３３が、基本姿勢においてどの位置となるのか、を定める必要がある。
【０１６１】
本実施形態では、新たに定められる頂点が切断された辺を内分する内分比が変形後と基本姿勢とで一致するようにして、基本姿勢における頂点の位置を求める。
【０１６２】
図９は、切断されて生じたポリゴンと頂点の基本姿勢における様子を示す説明図である。以下、本図を参照して説明する。
【０１６３】
図８と図９とで、頂点４３１は、頂点２３３、２３６を結ぶ辺を内分しているが、その内分比は基本姿勢と変形後で共通している。頂点４３２は、頂点２３５、２３６を結ぶ辺を内分しているが、その内分比は基本姿勢と変形後で共通している。頂点４３３は、頂点２３５、２３７を結ぶ辺を内分しているが、その内分比は基本姿勢と変形後で共通している。
【０１６４】
なお、頂点４３１、４３２、４３３は、一つの平面（分割面３０１をなす平面）上にあったため、図８では一直線上に並んでいるが、基本姿勢を示す図９では、一直線上に並ぶとは限らない。
【０１６５】
図１０は、オブジェクトの分割後のポリゴンと頂点の基本姿勢における様子を示す説明図である。以下、本図を参照して説明する。
【０１６６】
本図に示すように、分割によって、
（ａ）分割面と交差したポリゴン２４４、２４５が削除され、
（ｂ）新たな制御点４３１、４３２、４３３が追加され
（ｃ）新たな制御点４３１、４３２、４３３を頂点の一部とするポリゴン４４１、４４２、４４３、４４４が追加される
こととなっている。
【０１６７】
また、図４では、ポリゴン２４１乃至２４７は一つのグループをなし、一体となっていたが、切断によって、図１０においては、ポリゴン２４１、２４２、２４３、４４１、４４３が第１のグループを、ポリゴン４４２、４４４、２４６、２４７が第２のグループを、それぞれなすこととなっている。
【０１６８】
第１のグループにおいては、ポリゴン２４１、２４２が、共通の辺２３１−２３４を有し、ポリゴン２４２、２４３が、共通の辺２３３−２３４を有し、ポリゴン２４３、４４１が、共通の辺２３３−２３５を有し、ポリゴン４４１、４４３が、共通の辺２３５−４３２を有している。
【０１６９】
第２のグループにおいては、ポリゴン４４２、４４４が、共通の辺２３６−４３２を有し、ポリゴン４４４、２４６が、共通の辺２３６−２３７を有し、ポリゴン２４６、２４７が、共通の辺２３７−２３８を有している。
【０１７０】
そして、両グループは、切断によって新たに生じた辺４３１−４３２、辺４３２−４３３を介して接している。
【０１７１】
すなわち、既存の頂点同士を結ぶ辺、もしくは、既存の頂点と新たな頂点を結ぶ辺によって隣接するポリゴンを次々とたどることによって、グループを定めることができる。
【０１７２】
また、新たな頂点同士を結ぶ辺によって隣接するポリゴンは、分割面を介して対峙するポリゴンであり、切断によって異なるグループに属することとなる。
【０１７３】
さて、各グループのポリゴンが変形する状況は、従来と同様に、ボーン２１１、２１２、２１３によって定められる。すなわち、本実施形態においては、ボーンを分割する必要はない。これは、オブジェクトを形成するための情報を記憶する領域の更新をできるだけ少なくし、メモリの使用量を抑制するのに役立つ。
【０１７４】
一方、仮想空間における位置や向きを各グループに対して割り当てることとすれば、あるグループに属するポリゴンは一体として移動し、グループ同士は独立して移動することが可能となる。
【０１７５】
さて、新たな頂点４３１、４３２、４３３の位置と、これらに対する制御点の位置は、基本姿勢では重なるように定められる。したがって、あとは、制御点がいずれのボーンにどのような重みで依存するか、を定めれば、既存の制御点と新たな制御点を区別する必要がなくなる。
【０１７６】
たとえば、頂点４３１は、頂点２３３と頂点２３６を内分している。そして、頂点２３３に対する制御点２２３は、ボーン２１１、２１２に依存し、頂点２３６に対する制御点２２６は、ボーン２１２、２１３に依存する。そこで、本実施形態では、頂点４３１に対する制御点は、ボーン２１１、２１２、２１３に依存するものとする。
【０１７７】
すなわち、分割により生じた頂点の制御点に対する各ボーンの重みは、分割された辺の頂点の制御点に対する各ボーンの重みを、分割の際の内分比で内分したものとするのである。
【０１７８】
たとえば、制御点２２３のボーン２１１、２１２に対する重みをw11，w12とし、制御点２２６のボーン２１２、２１３に対する重みをw22，w23とする。制御点２２３はボーン２１３に依存しないから、制御点２２３のボーン２１３に対する重みは、０である。同様に、制御点２２６のボーン２１１に対する重みも、０である。
【０１７９】
そして、頂点４３１が、頂点２３３（制御点２２３）と頂点２３６（制御点２２３）との間をA対Bに内分するとする。
【０１８０】
すると、頂点４３１に対する制御点の
（ａ）ボーン２１１に対する重みは、〔B×w11 + A×0〕/〔A+B〕であり、
（ｂ）ボーン２１２に対する重みは、〔B×w12 + A×w22〕/〔A+B〕であり、
（ｃ）ボーン２１３に対する重みは、〔B×0 + A×w23〕/〔A+B〕である。
【０１８１】
このように、ボーンは分割せずに新たな頂点、制御点、重みを定めることで、オブジェクトを分割した後のポリゴンの形状を、自然に保つことができるようになるのである。
【０１８２】
図１１、図１２は、仮想空間内において各グループが異なる位置、向きに配置された場合の様子を示す説明図である。以下、本図を参照して説明する。
【０１８３】
図１１は、ボーン２１１、２１２、２１３の相対的な位置関係が、図２、図４、図１０と同じ状況において、グループごとの基本位置が異なる場合の、オブジェクト２０１の様子を示す図である。
【０１８４】
図１１は、ボーン２１１、２１２、２１３の相対的な位置関係が、図３、図５、図６と同じ状況において、グループごとの基本位置が異なる場合の、オブジェクト２０１の様子を示す図である。
【０１８５】
これらの図に示すように、各グループごとにオブジェクト２０１の概形をなすポリゴンは、ポリゴン２４１、２４２、２４３、４４１、４４３が第１のグループを、ポリゴン４４２、４４４、２４６、２４７が第２のグループを、なしており、それぞれが一体となっている。
【０１８６】
このように、ボーンの相対的な位置や向きの情報は、切断前と切断後とで変わりなく、一体となったまま処理をするが、ポリゴンは、グループごとに位置を定める点が、本発明の特徴の一つである。
【０１８７】
以下では、上記の技術を適用した画像処理装置の詳細について、説明する。
【０１８８】
図１３は、本実施形態に係る画像処理装置の概要構成を示す模式図であり、図１４は、当該画像処理装置が実行する画像処理の制御の流れを示すフローチャートである。以下、これらの図を参照して説明する。
【０１８９】
本実施形態の画像処理装置８０１は、記憶部８０２、ボーン移動部８０３、制御点移動部８０４、配置部８０５、選択部８０６、分割部８０７、生成部８０８、グループ移動部８０９を備え、情報処理装置１００にプログラムを実行させることにより実現される。
【０１９０】
ここで、記憶部８０２は、ＲＡＭ  １０３等により構成され、ボーン、制御点、頂点、ポリゴンの情報が記憶される。
【０１９１】
また、ボーン移動部８０３は、ボーンを移動させる機能を果たす。
【０１９２】
一方、制御点移動部８０４は、ボーンの移動に連動させて制御点を移動させる。
【０１９３】
さらに、配置部８０５は、移動した制御点の位置からポリゴンの頂点の位置を定める。
【０１９４】
そして、選択部８０６は、仮想空間内の分割面と交差するポリゴンを選択する。
【０１９５】
一方、分割部８０７は、記憶部８０２に記憶される情報を、変更、修正、追加、削除などをできるだけしないように工夫しつつ、更新することによって、分割面に基づいてポリゴンを分割し、ポリゴンのグループ分けを行う。
【０１９６】
グループ移動部８０９は、ポリゴンの位置を定めるための基準位置をグループ単位で移動させる。
【０１９７】
これら、ボーン移動部８０３、制御点移動部８０４、配置部８０５、選択部８０６、分割部８０７、グループ移動部８０９は、ＲＡＭ  １０３等に記憶される情報を参照してＣＰＵ  １０１や画像処理部１０７が計算を行うことにより実現される。
【０１９８】
一方、生成部８０８は、仮想空間内にポリゴンが配置される位置に基づいて、画像を生成するもので、ＣＰＵ  １０１の制御の下、画像処理部１０７により実現される。
【０１９９】
以下、画像処理装置８０１が実行する画像処理の制御の流れを、さらに詳細に説明する。
【０２００】
本処理が開始されると、ＣＰＵ  １００は、ＲＡＭ  １０３を初期化する（ステップＳ９０１）。ここで、ＲＡＭ  １０３により実現される記憶部８０２には、以下の情報が記憶される。
【０２０１】
（ａ）互いに連結された複数のボーンの初期位置および初期向き。すなわち、オブジェクトが基本姿勢をとっているときの、複数のボーンの位置および向き。
【０２０２】
典型的には、複数のボーンは、木構造に階層化されて管理される。木構造の各ノードには、各ボーンが割り当てられる。連結された２つのボーンのうち、一方のボーンを親ノードに、他方のボーンを子ノードに、割り当てられる。
【０２０３】
本実施形態では、親ノードのボーン（以下「親ボーン」という。）に固定された座標系における子ノードのボーン（以下「子ボーン」という。）が当該親ボーンに連結される連結点の座標、ならびに、当該子ボーンの向きを表すオイラー角もしくはクォータニオンにより、当該子ボーンの初期位置および初期向きが表現される。
【０２０４】
このほか、親ボーンに固定された座標系と、子ボーンに固定された座標系と、の位置関係の差分によって、初期位置および初期向きを表現する手法を採用しても良い。
【０２０５】
また、木構造の根ノードのボーン（以下「根ボーン」という。）に固定された座標系における、各ボーンの位置や向きを、上記の手法によって表現することで、初期位置や初期向きを表現することもできる。
【０２０６】
（ｂ）複数の制御点の初期位置。これは、オブジェクトが基本姿勢をとっているときの頂点の位置に重なるものである。
【０２０７】
（ｃ）複数の制御点のそれぞれが複数のボーンのそれぞれに依存する重みを表す依存情報。
【０２０８】
概念的には、依存情報は、制御点が依存しないボーンに対しては重みを０として、各重みを並べたベクトルと考えることができる。ただし、殆どの場合、このベクトルは疎なベクトルである。したがって、ベクトルの添字、すなわち、各ボーンを区別するための番号から重みへのペアの配列、あるいは、ハッシュなどの構造を採用して記憶すると、メモリの利用効率が良くなる。
【０２０９】
（ｄ）複数のポリゴンのそれぞれが複数の制御点のいずれを頂点とするかを表す頂点情報。
【０２１０】
ポリゴンの形状を定義するものであり、ポリゴンの識別番号と、所定個数の制御点の識別番号と、のペアの配列等によって表現することができる。なお、後述するように、ポリゴンを三角形に限定したり、三角形と四角形に限定することで、計算を簡易化することができる。
【０２１１】
（ｅ）複数のポリゴンのそれぞれがいずれのグループに属するかを表すグループ情報。
【０２１２】
ポリゴンが同じグループに属する、ということは、それらのポリゴンは一体となって仮想空間内を移動することを意味する。すなわち、それらのポリゴンは、まだ切断されていない、ということを意味する。
【０２１３】
（ｆ）グループのそれぞれに対する仮想空間内の基準位置および基準向き。
【０２１４】
各グループに属するポリゴンの位置は、根ボーンに固定された座標系に対する相対的な座標により表現される。そこで、根ボーンの位置と向きを、ポリゴンが属するグループの基準位置および基準向きに設定することで、仮想空間内におけるポリゴンの頂点の絶対的な位置を求めることができる。
【０２１５】
グループごとに基準位置および基準向きが設定されるので、同じグループに属するポリゴンは一体となって移動する。
【０２１６】
このほか、ＲＡＭ  １０３には、各ボーンの現在の位置および向き、各ボーンの移動に連動して移動する制御点の位置および向き、各頂点の現在の位置および向きなどの情報も記憶される。
【０２１７】
ついで、ＣＰＵ  １０１は、ユーザがコントローラ１０５などを指示操作して行う指示や時間経過、所定のアルゴリズム、乱数などに基づいて、ＲＡＭ  １０３内に記憶される各ボーンの現在の位置や向きを更新する（ステップＳ９０２）。この際の変化量を「ボーン変化量」と呼ぶ。
【０２１８】
各ボーンについてボーン変化量を決定する手法には、たとえば以下に掲げる手法等、種々の態様を採用することができる。
【０２１９】
（ａ）木構造において、親ボーンから子ボーンへ、の方向に位置や向きの変化量が伝播していくフォワードキネマティクス法。
【０２２０】
フォワードキネマティクスは、あらかじめ定めたアルゴリズムやモーションキャプチャデータを利用してオブジェクトを変形させる場合によく使われる手法である。たとえば、キャラクターに決められた振り付けのダンスを踊らせたり、必殺技や勝ち名乗りの決めポーズをとらせるような場合である。
【０２２１】
（ｂ）木構造において、葉ノードのボーン（以下「葉ボーン」という。）を目的位置に移動させ、根ボーンに向かって位置や向きの変化量を伝播させるインバースキネマティクス法。
【０２２２】
インバースキネマティクスは、たとえば、キャラクターに何らかの物体を拾わせたりするような場合によく使われる。このような場合では、目的位置が動的に変化するので、腕をどのように伸ばしてから縮めれば良いか、を求める必要がある。
【０２２３】
なお、ボーン変化量の表現法もさまざまであり、初期位置や初期向きからの変位で表現しても良いし、根ボーンに固定された座標系に対する当該ボーンに固定された座標系の、現在の位置および向きにより表現しても良い。
【０２２４】
なお、ボーン変化量によるボーンの変形は、図２から図３に至るまでのボーン２１１、２１２、２１３の相対的な位置の変化に相当する。
【０２２５】
さらに、ＣＰＵ  １０１は、制御点のそれぞれについて、以下の処理を繰り返す（ステップＳ９０３〜ステップＳ９０９）。
【０２２６】
まず、制御点が依存するボーン、すなわち、制御点のボーンに対する重みが非０であるようなボーンのそれぞれについて、当該ボーンに対する制御点の位置が相対的に変化しないように、制御点を移動する（ステップＳ９０４）。ここでの移動量を「連動変化量」と呼ぶ。
【０２２７】
これは、図２から図３に至るまでの図中の×印を、それぞれ求めることに相当し、制御点が複数のボーンに依存する場合には、移動先も複数箇所となる。
【０２２８】
次に、制御点の移動先を、そこへ移動する原因となったボーンの重みをつけて、平均をとる（ステップＳ９０５）。この結果が「制御点変化量」である。
【０２２９】
制御点変化量を求める処理は、図２から図３に至るまでの図中の○印をそれぞれ求めることに相当する。
【０２３０】
たとえば、制御点がN個、ボーンがM個用意されている状況を考える。j番目のボーンが移動したときに、j番目のボーンに対する相対的な位置が変化しないように、i番目の制御点を移動したときの連動変化量を表すベクトルをr[i,j]とする。また、i番目の制御点がj番目のボーンに依存する重みをw[i,j]とする。
【０２３１】
連動変化量は、オブジェクトが
【０２３２】
すると、i番目の制御点の制御点変化量は、
〔Σj=1M w[i,j]r[i,j]〕/〔Σj=1M w[i,j]〕
のように計算することができる。
【０２３３】
制御点変化量は、その制御点に対応付けられる頂点の位置や向きの変化を表すベクトルである。
【０２３４】
なお、w[i,j] = 0の場合、i番目の制御点はj番目のボーンに依存しないこととなるので、この場合にはr[i,j]を求める必要はない。
【０２３５】
ついで、ＣＰＵ  １０１は、当該制御点が属するグループを調べ（ステップＳ９０６）、当該グループの基準位置および基準向きを取得し（ステップＳ９０７）、当該制御点に対応付けられる頂点の、仮想空間内における絶対的な位置を計算する（ステップＳ９０８）。
【０２３６】
すると、仮想空間内の頂点の位置および向きは、
（ａ）基準位置および基準向きと、
（ｂ）頂点の初期位置および初期向きと、
（ｃ）制御点変化量と、
を座標変換すれば得られる。
【０２３７】
なお、頂点の初期位置および初期向きを、根ボーンの初期位置および初期向きと一致させる手法、すなわち、制御点変化量を、根ボーンに固定される座標系における制御点の座標で表現する手法もありうる。
【０２３８】
この場合は、単純に、基準位置および基準向きに基づいて、制御点変化量を平行移動および回転すれば、仮想空間内における位置および向きが得られる。
【０２３９】
１つの頂点は、一般には、複数のポリゴンで共有される。また、ある頂点を共有するポリゴンは、同じグループに属する場合が殆どである。したがって、
（ａ）どのグループを基準として頂点の位置を得たか、の情報と、
（ｂ）得られた頂点の位置と、
を対応付けてキャッシュすることにより、計算量を抑制することができる。
【０２４０】
なお、切断されていないオブジェクトを構成するポリゴンは、１つのグループに属するので、基準位置と基準向きが一致している。
【０２４１】
一方、オブジェクトが切断されると、そのオブジェクトを構成するポリゴンは、複数のグループのいずれかに属することとなる。各グループの基準位置と基準向きは、一般には異なるので、同じグループに属するポリゴンは一体となって移動するが、異なるグループに属するポリゴンは別個に移動することになる。
【０２４２】
このようにして、全制御点から頂点の位置を得る処理を繰り返す（〜ステップＳ９０９）。
【０２４３】
全頂点の位置が得られたら、ＣＰＵ  １０１は、画像処理部１０７を駆動して、仮想空間内に配置されたポリゴンを所定の視点位置から所定の視線方向に見た様子を表す画像を、３次元グラフィックス技術によって生成する（ステップＳ９１０）。
【０２４４】
すなわち、オブジェクトが分割されているか否かに関わらず、ボーンに関する情報そのものを、追加したり削除したり分離したり複製したりする必要がない。これは、本発明の特徴の一つである。
【０２４５】
ついで、ＣＰＵ  １０１は、垂直同期割込が発生するまで待機し（ステップＳ９１１）、垂直同期割込みが発生したら、画像処理部１０７を制御して、生成した画像をモニタの画面に表示させる（ステップＳ９１２）。
【０２４６】
本実施形態では、以降の処理を実行した後にステップＳ９０２に戻ることとしているので、モニタ画面に表示される画像は、垂直同期割込周期ごとに更新されることになる。このため、オブジェクトが変形している場合には、その様子が動画表示されることになる。
【０２４７】
なお、待機中（ステップＳ９１１）には、他の計算処理をコルーチン的に並行して実行することや、以降の計算を先行して行うことも可能である。
【０２４８】
さらに、ＣＰＵ  １０１は、仮想空間内に分割面が配置されたか否かを判定する（ステップＳ９１３）。分割面が配置される状況とは、ユーザがコントローラ１０５などを指示操作して切断を指定した場合や、所定のアルゴリズムに基づく場合など、種々の態様を採用することができる。分割面の配置は、上記の待機中（ステップＳ９１１）に行っても良いし、ステップＳ９１３において、コントローラ１０５等の押圧操作状況を監視することにより行っても良い。
【０２４９】
さて、分割面が配置されていない場合（ステップＳ９１３；Ｎｏ）、ステップＳ９２１に進む。一方、分割面が配置されている場合（ステップＳ９１３；Ｙｅｓ）、ＣＰＵ  １０１は、現在仮想空間内に配置されている全ポリゴンのうち、当該分割面と交差するポリゴンを選択する（ステップＳ９１４）。
【０２５０】
この処理は、図６において分割面３０１と交差するポリゴン２４４、２４５を選択する処理に相当する。
【０２５１】
たとえば、プレイヤーが刀をコントローラ１０５で操作し、仮想空間内で姿勢を変化させながら移動する敵キャラクターのオブジェクトを切断する場合を考える。
【０２５２】
この場合、刀の移動の軌跡が分割面に相当し、分割面と交差するポリゴンは、刀と衝突して切り裂かれる皮膚の部位に相当する。
【０２５３】
分割面の形状を仮想空間内に配置される円や扇型あるいは平面等、平らな形状とすれば、交差判定の計算を容易にすることができる。
【０２５４】
ついで、ＣＰＵ  １０１は、選択された各ポリゴンにおいて、分割面と交差する辺の交点が、当該辺の頂点の間を内分する内分比を求める（ステップＳ９１５）。
【０２５５】
これは、図８において、頂点４３１、４３２、４３３が、辺２３２−２３６、２３５−２３６、２３５−２３７を内分する内分比を求める処理に相当する。
【０２５６】
さらに、ＣＰＵ  １０１は、当該辺の頂点とされる制御点について記憶部８０２に記憶される初期位置の間を、当該求められた内分比で内分する位置（以下「内分位置」という。）を求める（ステップＳ９１６）。
【０２５７】
これは、図９において、頂点４３１、４３２、４３３の位置を計算する処理に相当する。
【０２５８】
ついで、ＣＰＵ  １０１は、当該求められた内分位置を新たな制御点の初期位置として、記憶部８０２に記憶させる。
【０２５９】
これにより、図１０に示すように、新たな頂点４３１、４３２、４３３が、オブジェクト２０２のスキンを定義するための制御点として採用されることになる。
【０２６０】
さらに、ＣＰＵ  １０１は、当該辺の頂点とされる制御点に対する依存情報を当該混合して、当該混合した結果を、当該新たな制御点に対する依存情報として、記憶部８０２に記憶させる。
【０２６１】
これは、上記のように、頂点４３１、４３２、４３３が、ボーン２１１、２１２、２１３に依存する重みを内分によって計算した処理に相当する。
【０２６２】
そして、ＣＰＵ  １０１は、選択されたポリゴンに対する頂点情報を、記憶部８０２から削除することにより、分割されたポリゴンを消去する（ステップＳ９１７）。
【０２６３】
この処理により、図２に示されていたポリゴン２４４、２４５が消去されることになる。
【０２６４】
さらに、ＣＰＵ  １０１は、選択されたポリゴンを分割面により分割することにより得られる新たなポリゴンの頂点を、分割面により分割されない辺の頂点とされる制御点ならびに分割面により分割される辺の交点に対する制御点とする頂点情報を、記憶部８０２に記憶させることにより、新たなポリゴンを生成する（ステップＳ９１８）。
【０２６５】
この処理により、図１０に示されるポリゴン４４１、４４２、４４３、４４４が生成されることになる。
【０２６６】
ついで、ＣＰＵ  １０１は、記憶部８０２に記憶される分割面と交差するポリゴンが属するグループに対するグループ情報を、分割面に対して当該ポリゴンの頂点がいずれの側にあるか、ならびに、当該ポリゴンが共通する辺を有することにより連結されているか、により、複数のグループに分割する（ステップＳ９１９）。
【０２６７】
上記の例では、ポリゴン２４１、２４２、２４３、４４１、４４３が１つのグループに、ポリゴン４４２、４４４、２４６、２４７が他のグループに、それぞれ属することとなる。
【０２６８】
なお、上記のように、辺を介してポリゴンが連結されることを基準に切断の判定を行うと、一回の切断によって、複雑な姿勢に変形したオブジェクトが多数のオブジェクトに分離されるような場合であっても、正しくグループ分けを行うことができる。
【０２６９】
そして、ＣＰＵ  １０１は、当該複数のグループ情報に対する基準位置および基準向きを、当該分割前のグループ情報に対する基準位置および基準向きに、初期化して設定する（ステップＳ９２０）。
【０２７０】
切断の直後は、切断後のグループの基準位置と基準向きは一致するので、図６、図１０に示すように、切断直後のグループは、分割面を境界に、互いに密着することになる。
【０２７１】
また、切断されて時間が経過すると、一般には、各グループの基準位置や基準向きは変化する。したがって、図１１、図１２に示すように、各グループは分離するが、グループ内のポリゴンは一体に移動する。
【０２７２】
図１５、図１６、図１７は、複雑な形状のオブジェクトが切断される様子を示す説明図である。以下、本図を参照して説明する。
【０２７３】
図１５は、敵キャラクターのオブジェクトが両手を下に下げている状態で、右上から左下に刀で切断されたときの様子を示す説明図である。なお、本図では、理解を容易にするため、分割面から離れるように、各ポリゴンを移動している。
【０２７４】
本図に示すように、一つの分割面によって、オブジェクトは３つの部分に分離されている。また、分割面が平面状であることもわかる。
【０２７５】
図１６は、図１５のオブジェクトの基本姿勢に相当する様子を示す説明図である。本図でも、理解を容易にするため、分割面から離れるように、各ポリゴンを移動している。
【０２７６】
本図を見ると、基本姿勢における分割面は、複雑な折れ曲がり形状を持っていることがわかる。
【０２７７】
図１７は、分割面により切断されたポリゴンを強調して表示する説明図である。
【０２７８】
本図を見ると、切断されたポリゴンの数は、切断されていないポリゴンの数に比べて、かなり少ないことがわかる。
【０２７９】
しかも、本実施形態では、基本姿勢においてポリゴンを分割しているため、分割面と交差しないポリゴンについては、以前と同じデータをそのまま利用できる。このため、記憶部８０２の書き換えが少なくてすみ、メモリの利用効率が向上する。
【０２８０】
さて、このようにポリゴンのグループ分けが済んだら、ＣＰＵ  １０１は、物理シミュレーション計算やユーザの指示入力等に基づいて、各グループの基準位置や基準向きを変化させ（ステップＳ９２１）、ステップＳ９０２に戻る。
【０２８１】
この処理によって、再度ポリゴンが仮想空間内に配置され、画像が生成される処理が繰り返されることになる。
【０２８２】
物理シミュレーションによって、時間の経過とともに、両者のずれが大きくなるように変化すると、オブジェクトの切断された部位同士が次第に離間していく状況が再現できる。
【０２８３】
このように、本実施形態では、分割面によって切断される一部のポリゴンに関係する情報のみを書き換えることとしている。また、書き換えた後の情報は、さらなる切断が可能となっている。たとえば、ゲームにおいてプレイヤーが敵キャラクターに何回も刀を振り下ろして、敵キャラクターを細切れにするような状況に適用することも可能である。
【０２８４】
また、画像の生成や画像の表示が所定の時間間隔で繰り返し行われるので、オブジェクトが切断される様子を表す動画が提示されることになる。
【０２８５】
本発明によれば、オブジェクトが移動・変形した後に切断された状況に基づいて、移動・変形がされる前の状況において一部のポリゴンを分割し、ポリゴン全体のグループ分けを再度行うことにより、オブジェクトの位置や形状を定める種々の情報の複製・削除・変更等をできるだけ抑制するとともに、簡易な計算によってオブジェクトの切断をシミュレートすることができるようになる。
【実施例２】
【０２８６】
上記実施形態では、辺を内分する内分点を新たな頂点とするときに、辺の元の頂点に割り当てられた重みを、内分比で内分することによって、新たな制御点の重みを得ることとしていた。
【０２８７】
たとえば、制御点がN個、ボーンがM個用意されている状況で、i番目の制御点がj番目のボーンに依存する重みをw[i,j]とし、内分される辺の頂点がそれぞれp番目、q番目であり、内分比がA:Bであるとしたとき、新たな制御点がj番目のボーンに依存する重みは、
〔B×w[p,j] + A×w[q,j]〕/〔A + B〕
のように計算することができる。
【０２８８】
しかしながら一般には、制御点が依存するボーンの数は１個〜４個程度とすることが多い。ここで、制御点が依存するボーンの数の上限をL個とすると、w[p,1]，w[p,2]，…，w[p,M]のうち、非０の要素は多くともL個しかない。w[q,1]，w[q,2]，…，w[q,M]についても、同様に、非０の要素は多くともL個しかない。
【０２８９】
このため、新たな制御点に対する各ボーンの重み
〔B×w[p,1] + A×w[q,1]〕/〔A + B〕,
〔B×w[p,2] + A×w[q,2]〕/〔A + B〕,
… ,
〔B×w[p,M] + A×w[q,M]〕/〔A + B〕
のうち、非０の要素は、多くとも2L個となる。
【０２９０】
そこで、得られた重みのうち非０の重みがL個を超える場合には、重みが大きい順からL個だけを選び、それ以外の重みを０にクリアする。
【０２９１】
すると、制御点は、選ばれた重みを持つL個のボーンには依存するが、それ以外のボーンには依存しない、ということになる。
【０２９２】
この構成は、ボーンに対する依存性を近似するものである。また、既存の３次元グラフィックスライブラリやハードウェアにおいては、制御点が依存するボーンの数に上限を設けていることが殆どである。本発明は、このようなライブラリ・ハードウェアを有効活用することができる。
【０２９３】
なお、ボーンに対する重みは、M個の要素を持つ１次元配列として実装するのではなく、非０の重みのインデックスと、そのインデックスに対応する重みと、の対がL個含まれる配列で表現することにより、メモリの使用量を抑制することが可能である。
【０２９４】
本発明によれば、制御点が依存するボーンの数を適切に抑制して、計算量やメモリの使用量を抑制することができるようになる。
【実施例３】
【０２９５】
上記実施形態では、ポリゴンが分割面で分離された後は、分離されたポリゴンをそのまま利用していた。本実施形態では、ポリゴンの形状として、三角形のみを採用することとする。
【０２９６】
図１８、図１９は、ポリゴンが分離される場合に、どのような分離が考えられるか、を示す説明図である。以下、本図を参照して説明する。
【０２９７】
これらの図において、分割面と交差するポリゴンは、点Ａ、Ｂ、Ｃを頂点とする三角形ＡＢＣである。分割面と交差することにより、辺ＡＢが、交点Ｄで分割され、辺ＡＣが、交点Ｅで分割されている。
【０２９８】
すべてのポリゴンを三角形にするためには、四角形ＤＢＣＥを対角線ＢＥもしくは対角線ＣＤで分割する必要がある。
【０２９９】
ここで、三角形の形状が細長くなると、画像を生成した際に、不自然なくびれや潰れが生じやすくなる。
【０３００】
そこで、本実施形態では、頂点を挟む辺同士の角度を利用する。
【０３０１】
すなわち、角ＥＤＣと角ＤＣＢの和（図１８）と、角ＤＥＢと角ＥＢＣの和（図１９）と、を比較する。すると、前者の方が、和が大きい。
【０３０２】
そこで、新たなポリゴンを、図１６に基づいて、三角形ＡＤＥ、三角形ＤＥＣ、三角形ＥＤＣとするのである。
【０３０３】
本実施形態によれば、ポリゴンを分割する際に、分割後のポリゴンの形状を適切に選択することにより、生成される画像が不自然になることをできるだけ防止することが可能となる。
【産業上の利用可能性】
【０３０４】
以上説明したように、本発明によれば、仮想空間に配置される複数のポリゴンからなるオブジェクトをある分割面で分割した様子を表す画像を生成するのに好適な画像処理装置、画像処理方法、ならびに、これらをコンピュータにて実現するプログラムを提供することができる。
【符号の説明】
【０３０５】
１００  情報処理装置
１０１  ＣＰＵ
１０２  ＲＯＭ
１０３  ＲＡＭ
１０４  インターフェース
１０５  コントローラ
１０６  外部メモリ
１０７  画像処理部
１０８  ＤＶＤ−ＲＯＭドライブ
１０９  ＮＩＣ
１１０  音声処理部
１１１  マイク
１２１  ＨＤ
２０１  オブジェクト
２１１  ボーン
２１２  ボーン
２１３  ボーン
２２１  制御点
２２２  制御点
２２３  制御点
２２４  制御点
２２５  制御点
２２６  制御点
２２７  制御点
２２８  制御点
２２９  制御点
２３１  頂点
２３２  頂点
２３３  頂点
２３４  頂点
２３５  頂点
２３６  頂点
２３７  頂点
２３８  頂点
２３９  頂点
２４１  ポリゴン
２４２  ポリゴン
２４３  ポリゴン
２４４  ポリゴン
２４５  ポリゴン
２４６  ポリゴン
２４７  ポリゴン
４３１  頂点
４３２  頂点
４３３  頂点
４４１  ポリゴン
４４２  ポリゴン
４４３  ポリゴン
４４４  ポリゴン
８０１  画像処理装置
８０２  記憶部
８０３  ボーン移動部
８０４  制御点移動部
８０５  配置部
８０６  選択部
８０７  分割部
８０８  生成部
８０９  グループ移動部
【図１】
2011065492.tif 000003
【図２】
2011065492.tif 000004
【図３】
2011065492.tif 000005
【図４】
2011065492.tif 000006
【図５】
2011065492.tif 000007
【図６】
2011065492.tif 000008
【図７】
2011065492.tif 000009
【図８】
2011065492.tif 000010
【図９】
2011065492.tif 000011
【図１０】
2011065492.tif 000012
【図１１】
2011065492.tif 000013
【図１２】
2011065492.tif 000014
【図１３】
2011065492.tif 000015
【図１４】
2011065492.tif 000016
【図１５】
2011065492.tif 000017
【図１６】
2011065492.tif 000018
【図１７】
2011065492.tif 000019
【図１８】
2011065492.tif 000020
【図１９】
2011065492.tif 000021