(57)【要約】【課題】リメッシュ後のデータ量の増大を抑え三次元モデルの歪みを最小限に抑えることが可能なメッシュ・データの正則化技術を提供する。【解決手段】ポテンシャル最小化手段１１は、三次元メッシュを平面凸包図形内に単射した単射メッシュにおける各内部辺の長さの重み付き二乗和（ポテンシャル）が最小となるように、凸包図形内部の頂点及び辺の単射メッシュ・データ（凸包内部データ）の座標の再配置を行う。重み更新手段１２は、各内部辺の重みデータを、当該内部辺近傍の単射メッシュの密度の逆数に対し単調増加な関数値により更新する。単射メッシュ緩和手段１３は、各内部辺の重みデータの更新を行った後にポテンシャル最小化手段により凸包内部データの座標の再配置を行う操作を、各内部辺の重みデータの更新前後における単射メッシュのポテンシャル変化量が閾値以下となるまで反復実行する。【選択図】        図１
2006285931.tif 000002
【特許請求の範囲】
【請求項１】
平面凸包図形と同位相の三次元メッシュを表す三次元メッシュ・データを、前記三次元メッシュを所定の平面凸包図形内に単射した二次元メッシュ（以下「単射メッシュ」という。）を表す単射メッシュ・データに変換するメッシュ・データのパラメータ化装置であって、
前記三次元メッシュの境界線上の各頂点の三次元メッシュ・データに対応して、前記凸包図形の境界線上の頂点及び辺の単射メッシュ・データ（以下「凸包境界データ」という。）を生成する境界写像手段；
前記三次元メッシュの境界線上以外の各頂点及び辺の三次元メッシュ・データに対応して、前記凸包図形内部の頂点及び辺の単射メッシュ・データ（以下「凸包内部データ」）を生成する初期配置手段；
前記単射メッシュにおける前記凸包図形の境界線上以外の各辺（以下「内部辺」という。）に対応して用意される重みデータを、所定の初期値に初期化する重み初期化手段；
前記単射メッシュにおける前記各内部辺の長さの重み付き二乗和（以下「単射メッシュのポテンシャル」という。）を最小化するように、前記凸包内部データの頂点座標の再配置を行う再配置手段；
を備え、
前記再配置手段は、
前記各重みデータを前記単射メッシュにおける各内部辺の重みとして計算される前記単射メッシュのポテンシャルが最小となるように、前記凸包内部データの座標の再配置を行う第１のポテンシャル最小化手段；
前記各内部辺の重みデータを、当該内部辺近傍の単射メッシュの密度の逆数又は当該内部辺に対応する前記三次元メッシュの辺の周りの曲率の逆数に対し単調増加な関数値により更新する第１の重み更新手段；
及び、前記第１の重み更新手段により各内部辺の重みデータの更新を行った後に前記第１のポテンシャル最小化手段により前記凸包内部データの座標の再配置を行う操作を、前記各内部辺の重みデータの更新前後における前記単射メッシュのポテンシャルの最小値の変化量が所定の閾値以下となるまで反復実行する単射メッシュ緩和手段；
を備えたメッシュ・データのパラメータ化装置。
【請求項２】
前記重み更新手段は、前記各内部辺の重みデータを当該内部辺の長さのｍ１乗（ｍ１＞０）又はその定数倍の値に更新すること
を特徴とする請求項１記載のメッシュ・データのパラメータ化装置。
【請求項３】
前記重み更新手段は、前記各内部辺の重みデータを、当該内部辺に隣接する単射メッシュの平均面積のｍ２乗（ｍ２＞０）又はその定数倍の値に更新すること
を特徴とする請求項１記載のメッシュ・データのパラメータ化装置。
【請求項４】
前記重み更新手段は、前記各内部辺の重みデータを、当該内部辺に対応する前記三次元メッシュ内の辺の周りの曲率の逆数のｍ３乗（ｍ３＞０）又はその定数倍の値に更新すること
を特徴とする請求項１記載のメッシュ・データのパラメータ化装置。
【請求項５】
前記重み更新手段は、前記各内部辺の重みデータを、当該内部辺の長さのｍ１乗（ｍ１＞０）の値、当該内部辺に隣接する単射メッシュの平均面積のｍ２乗（ｍ２＞０）の値、及び当該内部辺に対応する前記三次元メッシュ内の辺の周りの曲率の逆数のｍ３乗（ｍ３＞０）の値の何れか二以上の線形和に、前記各内部辺の重みを更新すること
を特徴とする請求項１記載のメッシュ・データのパラメータ化装置。
【請求項６】
平面凸包図形と同位相の三次元メッシュを表す非正則な三次元メッシュ・データを、正則化された三次元メッシュ・データに変換するメッシュ・データの正則化装置であって、
前記三次元メッシュ・データの各頂点及び辺に対応して、前記三次元メッシュを所定の平面凸包図形内に単射した二次元メッシュ（以下「単射メッシュ」という。）を表す単射メッシュ・データを生成する単射メッシュ生成手段；
前記平面凸包図形に対して所定の正則メッシュを表す正則メッシュ・データを生成する初期グリット生成手段；
正則メッシュ・データの前記凸包図形内部の頂点座標を、前記単射メッシュに近似させて再配置する正則メッシュ変形手段；
再配置された前記正則メッシュの各頂点の座標を、当該頂点が属する前記単射メッシュ内のメッシュの各頂点（以下「単射メッシュ頂点」という。）の凸結合で表す場合における凸結合係数を算出する凸結合係数算出手段；
及び、前記正則メッシュの各頂点が属する前記単射メッシュの単射メッシュ頂点の座標及び前記凸結合係数に基づき正則三次元モデルを再構築する正則三次元モデル構成手段；
を備えたメッシュ・データの正則化装置。
【請求項７】
前記正則メッシュ変形手段は、
前記正則メッシュにおける前記凸包図形の境界線上以外の各辺（以下「内部グリッド辺」という。）に対応して用意される重みデータを、所定の初期値に初期化する重み初期化手段；
前記正則メッシュにおける前記各内部グリッド辺の長さの重み付き二乗和（以下「正則メッシュのポテンシャル」という。）を最小化するように、前記正則メッシュ・データにおける前記凸包図形内部の頂点（以下「内部グリッド」という。）の座標の再配置を行う再配置手段；
を備え、
前記再配置手段は、
前記各重みデータを前記正則メッシュにおける各内部グリッド辺の重みとして計算される前記正則メッシュのポテンシャルが最小となるように、前記正則メッシュ・データにおける、前記内部グリッドの座標の再配置を行う第２のポテンシャル最小化手段；
前記各内部グリッド辺の重みを、当該内部グリッド辺近傍の前記単射メッシュの密度の逆数又は当該内部グリッド辺近傍の前記単射メッシュに対応する三次元メッシュの面積の逆数と単調増加関係にある値により更新する第２の重み更新手段；
及び、前記第２の重み更新手段により各内部グリッド辺の重みデータの更新を行った後に前記第２のポテンシャル最小化手段により前記内部グリッドの座標の再配置を行う操作を、前記各内部グリッド辺の重みデータの更新前後における前記正則メッシュのポテンシャルの最小値の変化量が所定の閾値以下となるまで反復実行する正則メッシュ緩和手段；
を備えたことを特徴とする請求項６記載のメッシュ・データの正則化装置。
【請求項８】
前記重み更新手段は、前記各内部グリッド辺の重みを、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュのメッシュ数のｍ４乗（ｍ４＞０）又はその定数倍の値に更新すること
を特徴とする請求項７記載のメッシュ・データの正則化装置。
【請求項９】
前記重み更新手段は、前記各内部グリッド辺の重みを、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュの各頂点の曲率の和の逆数のｍ５乗（ｍ５＞０）又はその定数倍の値に更新すること
を特徴とする請求項７記載のメッシュ・データの正則化装置。
【請求項１０】
前記重み更新手段は、前記各内部グリッド辺の重みを、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュに対応する前記三次元メッシュの面積の逆数のｍ６乗（ｍ６＞０）又はその定数倍の値に更新すること
を特徴とする請求項７記載のメッシュ・データの正則化装置。
【請求項１１】
前記重み更新手段は、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュのメッシュ数のｍ４乗（ｍ４＞０）の値、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュの各頂点の曲率の和の逆数のｍ５乗（ｍ５＞０）の値、及び当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュに対応する前記三次元メッシュの面積の逆数のｍ６乗（ｍ６＞０）の値の何れか二以上の線形和に、前記各内部辺の重みを更新すること
を特徴とする請求項７記載のメッシュ・データの正則化装置。
【請求項１２】
前記単射メッシュ生成手段は、請求項１乃至５の何れか一のメッシュ・データのパラメータ化装置であること
を特徴とする請求項６乃至１１の何れか一記載のメッシュ・データの正則化装置。
【請求項１３】
平面凸包図形と同位相の三次元メッシュを表す三次元メッシュ・データを、前記三次元メッシュを所定の平面凸包図形内に単射した二次元メッシュ（以下「単射メッシュ」という。）を表す単射メッシュ・データに変換するメッシュ・データのパラメータ化方法であって、
前記三次元メッシュの境界線上の各頂点の三次元メッシュ・データに対応して、前記凸包図形の境界線上の頂点及び辺の単射メッシュ・データ（以下「凸包境界データ」という。）を生成する境界写像ステップ；
前記三次元メッシュの境界線上以外の各頂点及び辺の三次元メッシュ・データに対応して、前記凸包図形内部の頂点及び辺の単射メッシュ・データ（以下「凸包内部データ」）を生成する初期配置ステップ；
前記単射メッシュにおける前記凸包図形の境界線上以外の各辺（以下「内部辺」という。）に対応して用意される重みデータを、所定の初期値に初期化する重み初期化ステップ；
前記単射メッシュにおける前記各内部辺の長さの重み付き二乗和（以下「単射メッシュのポテンシャル」という。）を最小化するように、前記凸包内部データの頂点座標の再配置を行う再配置ステップ；
を備え、
前記再配置ステップにおいては、
前記各重みデータを前記単射メッシュにおける各内部辺の重みとして計算される前記単射メッシュのポテンシャルが最小となるように、前記凸包内部データの座標の再配置を行うポテンシャル最小化ステップ；
及び、前記各内部辺の重みデータを、当該内部辺近傍の単射メッシュの密度の逆数又は当該内部辺に対応する前記三次元メッシュの辺の周りの曲率の逆数に対し単調増加な関数値により更新する重み更新ステップ；
を、前記各内部辺の重みデータの更新前後における前記単射メッシュのポテンシャルの最小値の変化量が所定の閾値以下となるまで反復実行すること
を特徴とするメッシュ・データのパラメータ化方法。
【請求項１４】
前記重み更新ステップにおいて、前記各内部辺の重みデータを当該内部辺の長さのｍ１乗（ｍ１＞０）又はその定数倍の値に更新すること
を特徴とする請求項１３記載のメッシュ・データのパラメータ化方法。
【請求項１５】
前記重み更新ステップにおいて、前記各内部辺の重みデータを、当該内部辺に隣接する単射メッシュの平均面積のｍ２乗（ｍ２＞０）又はその定数倍の値に更新すること
を特徴とする請求項１３記載のメッシュ・データのパラメータ化方法。
【請求項１６】
前記重み更新ステップにおいて、前記各内部辺の重みデータを、当該内部辺に対応する前記三次元メッシュ内の辺の周りの曲率の逆数のｍ３乗（ｍ３＞０）又はその定数倍の値に更新すること
を特徴とする請求項１３記載のメッシュ・データのパラメータ化方法。
【請求項１７】
前記重み更新ステップにおいて、前記各内部辺の重みデータを、当該内部辺の長さのｍ１乗（ｍ１＞０）の値、当該内部辺に隣接する単射メッシュの平均面積のｍ２乗（ｍ２＞０）の値、及び当該内部辺に対応する前記三次元メッシュ内の辺の周りの曲率の逆数のｍ３乗（ｍ３＞０）の値の何れか二以上の線形和に、前記各内部辺の重みを更新すること
を特徴とする請求項１３記載のメッシュ・データのパラメータ化方法。
【請求項１８】
平面凸包図形と同位相の三次元メッシュを表す非正則な三次元メッシュ・データを、正則化された三次元メッシュ・データに変換するメッシュ・データの正則化方法であって、
前記三次元メッシュ・データの各頂点及び辺に対応して、前記三次元メッシュを所定の平面凸包図形内に単射した二次元メッシュ（以下「単射メッシュ」という。）を表す単射メッシュ・データを生成する単射メッシュ生成ステップ；
前記平面凸包図形に対して所定の正則メッシュを表す正則メッシュ・データを生成する初期グリット生成ステップ；
正則メッシュ・データの前記凸包図形内部の頂点座標を、前記単射メッシュに近似させて再配置する正則メッシュ変形ステップ；
再配置された前記正則メッシュの各頂点の座標を、当該頂点が属する前記単射メッシュ内のメッシュの各頂点（以下「単射メッシュ頂点」という。）の凸結合で表す場合における凸結合係数を算出する凸結合係数算出ステップ；
及び、前記正則メッシュの各頂点が属する前記単射メッシュの単射メッシュ頂点の座標及び前記凸結合係数に基づき正則三次元モデルを再構築する正則三次元モデル構成ステップ；
を備えたメッシュ・データの正則化方法。
【請求項１９】
前記正則メッシュ変形ステップは、
前記正則メッシュにおける前記凸包図形の境界線上以外の各辺（以下「内部グリッド辺」という。）に対応して用意される重みデータを、所定の初期値に初期化する重み初期化ステップ；
前記正則メッシュにおける前記各内部グリッド辺の長さの重み付き二乗和（以下「正則メッシュのポテンシャル」という。）を最小化するように、前記正則メッシュ・データにおける前記凸包図形内部の頂点（以下「内部グリッド」という。）の座標の再配置を行う再配置ステップ；
を備え、
前記再配置ステップにおいては、
前記各重みデータを前記正則メッシュにおける各内部グリッド辺の重みとして計算される前記正則メッシュのポテンシャルが最小となるように、前記正則メッシュ・データにおける、前記内部グリッドの座標の再配置を行う再配置ステップ；
及び、前記各内部グリッド辺の重みを、当該内部グリッド辺近傍の前記単射メッシュの密度の逆数又は当該内部グリッド辺近傍の前記単射メッシュに対応する三次元メッシュの面積の逆数と単調増加関係にある値により更新する重み更新ステップ；
を、前記各内部グリッド辺の重みデータの更新前後における前記正則メッシュのポテンシャルの最小値の変化量が所定の閾値以下となるまで反復実行すること
を特徴とする請求項１８記載のメッシュ・データの正則化方法。
【請求項２０】
前記重み更新ステップにおいて、前記各内部グリッド辺の重みを、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュのメッシュ数のｍ４乗（ｍ４＞０）又はその定数倍の値に更新すること
を特徴とする請求項１９記載のメッシュ・データの正則化方法。
【請求項２１】
前記重み更新ステップにおいて、前記各内部グリッド辺の重みを、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュの各頂点の曲率の和の逆数のｍ５乗（ｍ５＞０）又はその定数倍の値に更新すること
を特徴とする請求項１９記載のメッシュ・データの正則化方法。
【請求項２２】
前記重み更新ステップにおいて、前記各内部グリッド辺の重みを、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュに対応する前記三次元メッシュの面積の逆数のｍ６乗（ｍ６＞０）又はその定数倍の値に更新すること
を特徴とする請求項１９記載のメッシュ・データの正則化方法。
【請求項２３】
前記重み更新ステップにおいて、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュのメッシュ数のｍ４乗（ｍ４＞０）の値、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュの各頂点の曲率の和の逆数のｍ５乗（ｍ５＞０）の値、及び当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュに対応する前記三次元メッシュの面積の逆数のｍ６乗（ｍ６＞０）の値の何れか二以上の線形和に、前記各内部辺の重みを更新すること
を特徴とする請求項１９記載のメッシュ・データの正則化方法。
【請求項２４】
前記単射メッシュ生成ステップにおいては、請求項１乃至５の何れか一の方法により三次元メッシュを平面凸包図形に写像することで単射メッシュを生成すること
を特徴とする請求項１８乃至２３の何れか一記載のメッシュ・データの正則化方法。
【請求項２５】
コンピュータに請求項１３乃至１７の何れかのメッシュ・データのパラメータ化方法を実行させるプログラム。
【請求項２６】
コンピュータに請求項１８乃至２４の何れかのメッシュ・データのパラメータ化方法を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明はデジタル・コンテンツとしての三次元モデルを表す三次元メッシュ・データについて、非正則メッシュから正則メッシュへの自動変換を行うメッシュ・データの正則化技術に関する。
【背景技術】
【０００２】  三次元モデルを編集、獲得、表示する技術は、主としてエンターテインメントや医療の分野で発展してきた。近年の半導体技術の進歩やネットワークの高速化に戸のない、テキスト、音声、画像に続くデジタル・コンテンツとしての三次元モデルの需要は更に高まってきており、モデリング及びレタリングを中心とした様々な関連技術が盛んに研究されている。【０００３】  一般に、三次元モデルには、ヴォリューム・モデル、ソリッド・モデル、スプライン・パッチ等、様々な表現方法がある。中でも、物体の表面をポリゴンで近似した三次元メッシュ・モデル（以下「三次元メッシュ」という。）は、高精細なモデルやアニメーションを比較的簡単に表現できるため、広く用いられている。【０００４】  通常、三次元モデリングは、レンジスキャナや接触型三次元センサなどで得られた三次元空間上の点群を辺でつなぎメッシュ化することにより達成される（図８参照）。ここで、メッシュの形状は任意の多角形を用いることができるが、特に、三角形は面の最小単位であり、任意の多角形は複数の三角形により表現できることから、通常は三角形のメッシュが使用される。そこで、以下では、三角形からなるメッシュのみを考える。【０００５】  このようなメッシュ化により得られたメッシュは、一般に、各頂点に接続される辺（又は三角形、頂点）の数が均一ではない。このようなメッシュは「非正則メッシュ（ｉｒｒｅｇｕｌａｒ  ｍｅｓｈ）」と呼ばれる（図９（ａ）参照）。この非正則性が、三次元モデルのフィルタリング、編集、符号化などの各種データ処理を難しくしている。例えば、非正則メッシュで構成された三次元モデルにフィルタをかける際、各頂点が持つ三角形の数に従い異なるフィルタを用いる必要が生じる。【０００６】  これに対して、境界を除くすべての頂点が同数の辺を持つ「正則メッシュ（ｒｅｇｕｌａｒ  ｍｅｓｈ）」（図９（ｂ）参照）は、すべての頂点がＮ個（通常はＮ＝６）の三角形を持つため、各種処理が飛躍的に容易となるという利点がある。【０００７】  そこで、三次元モデルにおける、非正則メッシュから正則メッシュへの自動変換を行う技術が必要とされる。この非正則メッシュから正則メッシュへの変換のことを「リメッシュ」という。【０００８】  リメッシュは、パラメータ化、及び非正則メッシュから正則メッシュへの写像の２つのステップによって行われる（非特許文献１参照）。【０００９】  パラメータ化とは、円板と位相同型の三次元メッシュを平面、円筒などのより単純なプリミティブ（ｐｒｉｍｉｔｉｖｅ）に写像する操作をいう。パラメータ化の手法はテクスチャ・マッピングなど重要な応用例が多く、現在までに多くの方法が提案されている。例えば、Ｆｌｏａｔｅｒにより提案された凸結合によるパラメータ化の方法が公知である（非特許文献２〜４参照）。図１０は凸結合によるパラメータ化の一例を示す図である（非特許文献２参照）。図１０（ｂ）は図１０（ａ）のドーム状の三次元メッシュを、二次元パラメータ空間の凸多角形（この場合は四角形）上に展開したものである。【００１０】  このパラメータ化の方法では、まず、図１０（ａ）のドーム底辺の４つの頂点を図１０（ｂ）の凸多角形の頂点に置く。続��て、図１０（ａ）のドーム境界（ドーム底辺四角形の辺）上のその他の頂点を、図１０（ｂ）の凸多角形の辺上に置く。そして、内部頂点の座標は、ある頂点が隣接する頂点の凸結合となるように配置する。内部頂点の配置計算は、スパー素行列による線形方程式を解くことによって求められる。【００１１】  一方、非正則メッシュから正則メッシュへの写像は、まず、パラメータ化により得られる凸多角形の非正則メッシュと同じアスペクト比（ａｓｐｅｃｔ  ｒａｔｉｏ）を有する正則メッシュ（正確には、境界辺上の頂点の辺の数は、境界内部の頂点の辺の数と異なるので、「準正則メッシュ（ｓｅｍｉ−ｒｅｇｕｌａｒ  ｍｅｓｈ）」と呼ばれる。ここでは、簡単のため準正則メッシュも含めて「正則メッシュ」と呼ぶ。）を用意する（図Ｄ参照）。この正則メッシュの各頂点はグリッド・ピクセル（ｇｒｉｄｓ  ｐｉｘｅｌ）と呼ばれる。例えば、図Ｄに示したように、図Ｄ（ａ）の非正則メッシュに対して図Ｄ（ａ）の正則メッシュが用意される。【００１２】  正則メッシュのグリッドサイズをＭ（＝Ｍｓ×Ｍｔ）とする。また、ｉ番目のグリッド・ピクセルをｑｉ＝（ｓｉ，ｔｉ）（∈Ｒ２，ｉ＝１，２，…，Ｍ）と記す。正則メッシュ内の１つのグリッド・ピクセルｑｉは、非正則メッシュ内の同座標（ｓｉ，ｔｉ）の点ｑｉ’に一対一写像される。この点ｑｉ’は、非正則メッシュ内の１つの三角形ｔｉに属する。この三角形ｔｉの３つの頂点をｐｉ，ｐｊ，ｐｋとする。このとき、点ｑｉ’は、頂点ｐｉ，ｐｊ，ｐｋの凸結合として式（１）により表される。【００１３】
【数１】
2006285931.tif 000003
【００１４】  非正則メッシュの各頂点ｐｉ，ｐｊ，ｐｋは三次元メッシュの各頂点ｖｉ，ｖｊ，ｖｋ（∈Ｒ３）に一対一対応している。従って、グリッド・ピクセルｑｉの三次元メッシュにおける対応点ｕｉは式（３）によって容易に計算される。【００１５】
【数２】
2006285931.tif 000004
【非特許文献１】  Ｋ．Ｎａｇａｔｏｍｏ，Ｄ．Ｙｏｓｈｉｋａｉ，Ｍ．Ｉｋｅｈａｒａ，Ｍ．Ｏｋｕｄａ，Ｓ．Ｔａｋａｈａｓｈｉ，″Ｐｒｏｇｒｅｓｓｉｖｅ  Ｃｏｄｉｎｇ  ｏｆ  Ｔｅｘｔｕｒｅｄ  ３Ｄ  ｍｏｄｅｌｓ″，ＩＣＭＥ−ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍｕｌｔｉｍｅｄｉａ  ａｎｄ  Ｅｘｐｏ，Ａｕｇｕｓｔ  ２６−２９，２００２．  Ｌａｕｓａｎｎｅ，Ｓｗｉｔｚｅｒｌａｎｄ．
【非特許文献２】  Ｍ．Ｓ．Ｆｌｏａｔｅｒ，″Ｐａｒａｍｅｔｒｉｚａｔｉｏｎ  ａｎｄ  Ｓｍｏｏｔｈ  ａｐｐｒｏｘｉｍａｔｉｏｎ  ｏｆ  ｓｕｒｆａｃｅ  ｔｒｉａｎｇｕｌａｔｉｏｎ″，Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｇｅｏｍｅｔｒｉｃ  Ｄｅｓｉｇｎ，１９９７，ｐｐ．２３１−２５０．
【非特許文献３】  Ａ．Ｌｅｅ，Ｗ．Ｓｗｅｌｄｅｎｓ，Ｐ．Ｓｃｈｒｏｄｅｒ，Ｌ．Ｃｏｗｓａｒ，ａｎｄ  Ｄ．Ｄｏｂｋｉｎ，″ＭＡＰＳ：Ｍｕｌｔｉｒｅｓｏｌｕｔｉｏｎ  Ａｄａｐｔｉｖｅ  Ｐａｒａｍｅｔｅｒｉｚａｔｉｏｎ  ｏｆ  Ｓｕｒｆａｃｅｓ″，Ｉｎ  ＳＩＧＧＲＡＰＨ  ’９８，ｐｐ．９６−１０４．
【非特許文献４】  Ｓ．Ｙｏｓｈｉｚａｗａ，Ａ．Ｂｅｌｙａｅｖ，Ｈ−Ｒ．Ｓｅｉｄｅｌ，″Ａ  ｆａｓｔ  ａｎｄ  ｓｉｍｐｌｅ  ｓｔｒｅｔｃｈ−ｍｉｎｉｍｉｚｉｎｇ  ｍｅｓｈ  ｐａｒａｍｅｔｅｒｉｚａｔｉｏｎ″，Ｐｒｏｃ．Ｓｈａｐｅ  Ｍｏｄｅｌｉｎｇ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ，ｐｐ．２００−２０８，Ｊｕｎ７−１１，２００４，Ｇｅｎｏｖａ，Ｉｔａｌｙ．
【発明の開示】
【発明が解決しようとする課題】
【００１６】  しかしながら、上記従来の三次元メッシュの正則化方法においては次のような欠点がある。まず、従来のパラメータ化の方法に関しては、テクスチャ・マッピング等に対しては有利であるものの、リメッシュに応用する場合は適当ではなく、リメッシュ後のモデルの形が大きく変形してしまう問題がある。これは、正則メッシュのグリッド・ピクセルが一定の間隔で規則正しく配置されているのに対し、三次元メッシュのパラメータ化により得られる非正則メッシュは図１０（ａ）に示したようにメッシュの粗密が大きく、これを正則メッシュで近似すると非正則メッシュのメッシュが密の部分の形状が歪められてしまうことによる。【００１７】  また、リメッシュ後のモデルの形の変形を抑えるためには、非正則メッシュの密な部分に適応して正則メッシュのグリッドサイズを小さくすればよい。しかしながら、正則メッシュのグリッドサイズを小さくすると、リメッシュ後のデータ量（頂点や三角形の数）が増大するという欠点がある。【００１８】  そこで、本発明の目的は、リメッシュ後のデータ量の増大を抑えると共に、リメッシュによる三次元モデルの歪みを最小限に抑えることが可能なメッシュ・データの正則化技術、及びその方法に適したパラメータ化を行うためのパラメータ化技術を提供することにある。
【課題を解決するための手段】
【００１９】  本発明に係るメッシュ・データのパラメータ化装置の第１の構成は、平面凸包図形と同位相の三次元メッシュを表す三次元メッシュ・データを、前記三次元メッシュを所定の平面凸包図形内に単射した二次元メッシュ（以下「単射メッシュ」という。）を表す単射メッシュ・データに変換するメッシュ・データのパラメータ化装置であって、前記三次元メッシュの境界線上の各頂点の三次元メッシュ・データに対応して、前記凸包図形の境界線上の頂点及び辺の単射メッシュ・データ（以下「凸包境界データ」という。）を生成する境界写像手段；前記三次元メッシュの境界線上以外の各頂点及び辺の三次元メッシュ・データに対応して、前記凸包図形内部の頂点及び辺の単射メッシュ・データ（以下「凸包内部データ」）を生成する初期配置手段；前記単射メッシュにおける前記凸包図形の境界線上以外の各辺（以下「内部辺」という。）に対応して用意される重みデータを、所定の初期値に初期化する重み初期化手段；前記単射メッシュにおける前記各内部辺の長さの重み付き二乗和（以下「単射メッシュのポテンシャル」という。）を最小化するように、前記凸包内部データの頂点座標の再配置を行う再配置手段；を備え、前記再配置手段は、前記各重みデータを前記単射メッシュにおける各内部辺の重みとして計算される前記単射メッシュのポテンシャルが最小となるように、前記凸包内部データの座標の再配置を行う第１のポテンシャル最小化手段；前記各内部辺の重みデータを、当該内部辺近傍の単射メッシュの密度の逆数又は当該内部辺に対応する前記三次元メッシュの辺の周りの曲率の逆数に対し単調増加な関数値により更新する第１の重み更新手段；及び、前記第１の重み更新手段により各内部辺の重みデータの更新を行った後に前記第１のポテンシャル最小化手段により前記凸包内部データの座標の再配置を行う操作を、前記各内部辺の重みデータの更新前後における前記単射メッシュのポテンシャルの最小値の変化量が所定の閾値以下となるまで反復実行する単射メッシュ緩和手段；を備えたことを特徴とする。【００２０】  この構成により、単射メッシュのポテンシャルを計算する際に、単射メッシュの各内部辺の近傍のメッシュ密度が小さい辺（又は当該内部辺に対応する三次元メッシュの辺の曲率が小さい辺）に対しては大きな重みが加えられる。従って、単射メッシュ緩和手段による凸包内部データの座標の再配置過程において、メッシュ密度が小さい領域（対応する三次元メッシュの曲率が小さい領域）ではメッシュが密となる方向に再配置され、メッシュ密度が大きい領域（対応する三次元メッシュの曲率が大きい領域）ではメッシュが密となる方向に再配置され、全体として単射メッシュのポテンシャルの釣り合いがとれた状態に緩和されて安定する。【００２１】  これにより、単射メッシュにおける頂点分布の粗密が緩和されるため、生成された単射メッシュに正則メッシュを重ねてリメッシュを行う場合のリメッシュによる三次元モデルの歪みを抑えることができる。【００２２】  本発明に係るメッシュ・データのパラメータ化装置の第２の構成は、前記第１の構成において、前記重み更新手段は、前記各内部辺の重みデータを当該内部辺の長さのｍ１乗（ｍ１＞０）又���その定数倍の値に更新することを特徴とする。【００２３】  これにより、単射メッシュの長さの長い各内部辺に対しては大きな重みが加えられ、長さの短い各内部辺に対しては小さな重みが加えられる。一般に、内部辺の長さは、その辺の周囲のメッシュ密度の逆数と正の相関関係があると考えられる。従って、上述のように、単射メッシュにおける頂点分布の粗密が緩和されるため、生成された単射メッシュに正則メッシュを重ねてリメッシュを行う場合のリメッシュによる三次元モデルの歪みを抑えることができる。【００２４】  本発明に係るメッシュ・データのパラメータ化装置の第３の構成は、前記第１の構成において、前記重み更新手段は、前記各内部辺の重みデータを、当該内部辺に隣接する単射メッシュの平均面積のｍ２乗（ｍ２＞０）又はその定数倍の値に更新することを特徴とする。【００２５】  これにより、隣接する単射メッシュの平均面積の大きい各内部辺に対しては大きな重みが加えられ、当該平均面積の小さい各内部辺に対しては小さな重みが加えられる。一般に、内部辺に隣接する単射メッシュの平均面積は、その辺の周囲のメッシュ密度の逆数と正の相関関係があると考えられる。従って、上述のように、単射メッシュにおける頂点分布の粗密が緩和されるため、生成された単射メッシュに正則メッシュを重ねてリメッシュを行う場合のリメッシュによる三次元モデルの歪みを抑えることができる。【００２６】  本発明に係るメッシュ・データのパラメータ化装置の第４の構成は、前記第１の構成において、前記重み更新手段は、前記各内部辺の重みデータを、当該内部辺に対応する前記三次元メッシュ内の辺の周りの曲率の逆数のｍ３乗（ｍ３＞０）又はその定数倍の値に更新することを特徴とする。【００２７】  これにより、対応する三次元メッシュ内の辺の周りの曲率が小さい各内部辺に対しては大きな重みが加えられ、当該曲率が大きい各内部辺に対しては小さな重みが加えられる。一般に、三次元メッシュ内の曲率が大きい領域は、曲面を表現するのに小さいメッシュが必要とされるため細かくメッシュ化される。逆に、曲率が小さい領域は、曲面を表現するのにさほど小さなメッシュは必要とされないため粗くメッシュ化される、従って、内部辺に対応する三次元メッシュ内の辺の周りの曲率の逆数は、その辺の周囲のメッシュ密度の逆数と正の相関関係があると考えられる。従って、上述のように、単射メッシュにおける頂点分布の粗密が緩和されるため、生成された単射メッシュに正則メッシュを重ねてリメッシュを行う場合のリメッシュによる三次元モデルの歪みを抑えることができる。【００２８】  本発明に係るメッシュ・データのパラメータ化装置の第５の構成は、前記第１の構成において、前記重み更新手段は、前記各内部辺の重みデータを、当該内部辺の長さのｍ１乗（ｍ１＞０）の値、当該内部辺に隣接する単射メッシュの平均面積のｍ２乗（ｍ２＞０）の値、及び当該内部辺に対応する前記三次元メッシュ内の辺の周りの曲率の逆数のｍ３乗（ｍ３＞０）の値の何れか二以上の線形和に、前記各内部辺の重みを更新することを特徴とする。【００２９】  上述のように、内部辺の長さ、内部辺に隣接する単射メッシュの平均面積、及び当該内部辺に対応する��記三次元メッシュ内の辺の周りの曲率の逆数は、その内部辺の周囲のメッシュ密度の逆数と正の相関関係があると考えられる。従って、これらの線形和もその内部辺の周囲のメッシュ密度の逆数と正の相関関係があると考えられる。従って、上述のように、単射メッシュにおける頂点分布の粗密が緩和されるため、生成された単射メッシュに正則メッシュを重ねてリメッシュを行う場合のリメッシュによる三次元モデルの歪みを抑えることができる。【００３０】  本発明に係るメッシュ・データの正則化装置の第１の構成は、平面凸包図形と同位相の三次元メッシュを表す非正則な三次元メッシュ・データを、正則化された三次元メッシュ・データに変換するメッシュ・データの正則化装置であって、前記三次元メッシュ・データの各頂点及び辺に対応して、前記三次元メッシュを所定の平面凸包図形内に単射した二次元メッシュ（以下「単射メッシュ」という。）を表す単射メッシュ・データを生成する単射メッシュ生成手段；前記平面凸包図形に対して所定の正則メッシュを表す正則メッシュ・データを生成する初期グリット生成手段；正則メッシュ・データの前記凸包図形内部の頂点座標を、前記単射メッシュに近似させて再配置する正則メッシュ変形手段；再配置された前記正則メッシュの各頂点の座標を、当該頂点が属する前記単射メッシュ内のメッシュの各頂点（以下「単射メッシュ頂点」という。）の凸結合で表す場合における凸結合係数を算出する凸結合係数算出手段；及び、前記正則メッシュの各頂点が属する前記単射メッシュの単射メッシュ頂点の座標及び前記凸結合係数に基づき正則三次元モデルを再構築する正則三次元モデル構成手段；を備えたことを特徴とする。【００３１】  この構成により、正則メッシュ変形手段により、単射メッシュに重ね合わされる前に、正則メッシュの頂点分布と単射メッシュの頂点分布が近似するように、正則メッシュの頂点座標の調整が行われる。従って、リメッシュにおける単射メッシュと正則メッシュとの頂点分布密度の差によるリメッシュ後の三次元モデルの歪みを抑えることが可能となる。【００３２】  また、単射メッシュの頂点分布の濃淡に適応して正則メッシュの頂点分布の濃淡が調整されるため、正則メッシュとして過分に細かいメッシュを用いる必要はない。従って、リメッシュ後のデータ量を抑えることが可能となる。【００３３】  本発明に係るメッシュ・データの正則化装置の第２の構成は、前記第１の構成において、前記正則メッシュ変形手段は、前記正則メッシュにおける前記凸包図形の境界線上以外の各辺（以下「内部グリッド辺」という。）に対応して用意される重みデータを、所定の初期値に初期化する重み初期化手段；前記正則メッシュにおける前記各内部グリッド辺の長さの重み付き二乗和（以下「正則メッシュのポテンシャル」という。）を最小化するように、前記正則メッシュ・データにおける前記凸包図形内部の頂点（以下「内部グリッド」という。）の座標の再配置を行う再配置手段；を備え、前記再配置手段は、前記各重みデータを前記正則メッシュにおける各内部グリッド辺の重みとして計算される前記正則メッシュのポテンシャルが最小となるように、前記正則メッシュ・データにおける、前記内部グリッドの座標の再配置を行う第２のポテンシャル最小化手段；前記各内部グリッド辺の重みを、当該内部グリッド辺近傍の前記単射メッシュの密度の逆数又は当該内部グリッド辺近傍の前記単射メッシュに対応する三次元メッシュの面積の逆数と単調増加関係にある値により更新する第２の重み更新手段；及び、前記第２の重み更新手段により各内部グリッド辺の重みデータの更新を行った後に前記第２のポテンシャル最小化手段により前記内部グリッドの座標の再配置を行う操作を、前記各内部グリッド辺の重みデータの更新前後における前記正則メッシュのポテンシャルの最小値の変化量が所定の閾値以下となるまで反復実行する正則メッシュ緩和手段；を特徴とする。【００３４】  この構成により、正則メッシュのポテンシャルを計算する際に、正則メッシュの各内部グリッド辺の近傍の単射メッシュ密度が小さい辺（又は当該内部グリッド辺近傍の単射メッシュに対応する三次元メッシュの面積が大きい辺）に対しては大きな重みが加えられる。従って、正則メッシュ緩和手段による凸包内部データの座標の再配置過程において、単射メッシュ密度が小さい領域（単射メッシュに対応する三次元メッシュの面積が大きい領域）では正則メッシュが密となる方向に再配置され、単射メッシュ密度が大きい領域（単射メッシュに対応する三次元メッシュの面積が小さい領域）では正則メッシュが密となる方向に再配置され、全体として正則メッシュのポテンシャルの釣り合いがとれた状態に緩和されて安定する。【００３５】  これにより、正則メッシュにおける頂点分布が単射メッシュにおける頂点分布に近似されるため、生成された正則メッシュと単射メッシュとを重ねてリメッシュを行った場合のリメッシュによる三次元モデルの歪みを抑えることができる。【００３６】  本発明に係るメッシュ・データの正則化装置の第３の構成は、前記第２の構成において、前記重み更新手段は、前記各内部グリッド辺の重みを、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュのメッシュ数のｍ４乗（ｍ４＞０）又はその定数倍の値に更新することを特徴とする。【００３７】  各内部グリッド辺を含む所定の半径の円内に入る単射メッシュのメッシュ数は、一般に、その内部グリッド辺の近傍の単射メッシュの密度と正の相関があると考えられる。従って、当該円内に入る前記単射メッシュのメッシュ数のｍ４乗（ｍ４＞０）又はその定数倍を当該内部グリッド辺の重みとすることで、上述のように、正則メッシュにおける頂点分布を単射メッシュにおける頂点分布に近似させることができる。【００３８】  本発明に係るメッシュ・データの正則化装置の第４の構成は、前記第２の構成において、前記重み更新手段は、前記各内部グリッド辺の重みを、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュの各頂点の曲率の和の逆数のｍ５乗（ｍ５＞０）又はその定数倍の値に更新することを特徴とする。【００３９】  各内部グリッド辺を含む所定の半径の円内に入る単射メッシュの各頂点の曲率の和の逆数は、一般に、その内部グリッド辺の近傍の単射メッシュの密度と正の相関があると考えられる。従って、当該円内に入る単射メッシュの各頂点の曲率の和の逆数のｍ５乗（ｍ５＞０）又はその定数倍を当該内部グリッド辺の重みとすることで、上述のように、正則メッシュにおける頂点分布を単射メッシュにおける頂点分布に近似させることができる。【００４０】  本発明に係るメッシュ・データの正則化装置の第５の構成は、前記第２の構成において、前記重み更新手段は、前記各内部グリッド辺の重みを、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュに対応する前記三次元メッシュの面積の逆数のｍ６乗（ｍ６＞０）又はその定数倍の値に更新することを特徴とする。【００４１】  各内部グリッド辺を含む所定の半径の円内に入る単射メッシュに対応する三次元メッシュの面積の逆数は、一般に、その内部グリッド辺の近傍の単射メッシュの密度と正の相関があると考えられる。従って、当該円内に入る単射メッシュに対応する三次元メッシュの面積の逆数のｍ６乗（ｍ６＞０）又はその定数倍を当該内部グリッド辺の重みとすることで、上述のように、正則メッシュにおける頂点分布を単射メッシュにおける頂点分布に近似させることができる。【００４２】  本発明に係るメッシュ・データの正則化装置の第６の構成は、前記第２の構成において、前記重み更新手段は、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュのメッシュ数のｍ４乗（ｍ４＞０）の値、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュの各頂点の曲率の和の逆数のｍ５乗（ｍ５＞０）の値、及び当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュに対応する前記三次元メッシュの面積の逆数のｍ６乗（ｍ６＞０）の値の何れか二以上の線形和に、前記各内部辺の重みを更新することを特徴とする。【００４３】  本発明に係るメッシュ・データの正則化装置の第７の構成は、前記第１乃至６の何れかの構成において、前記単射メッシュ生成手段は、請求項１乃至５の何れか一のメッシュ・データのパラメータ化装置であることを特徴とする。【００４４】  この構成により、リメッシュを実行する前に単射メッシュにおける頂点分布の粗密が緩和される。それに加えて、正則メッシュの頂点分布は単射メッシュにおける頂点分布に近似される。従って、リメッシュを行った場合のリメッシュによる三次元モデルの歪みをより効果的に抑えることができる。【００４５】  本発明に係るメッシュ・データのパラメータ化方法の第１の構成は、平面凸包図形と同位相の三次元メッシュを表す三次元メッシュ・データを、前記三次元メッシュを所定の平面凸包図形内に単射した二次元メッシュ（以下「単射メッシュ」という。）を表す単射メッシュ・データに変換するメッシュ・データのパラメータ化方法であって、前記三次元メッシュの境界線上の各頂点の三次元メッシュ・データに対応して、前記凸包図形の境界線上の頂点及び辺の単射メッシュ・データ（以下「凸包境界データ」という。）を生成する境界写像ステップ；前記三次元メッシュの境界線上以外の各頂点及び辺の三次元メッシュ・データに対応して、前記凸包図形内部の頂点及び辺の単射メッシュ・データ（以下「凸包内部データ」）を生成する初期配置ステップ；前記単射メッシュにおける前記凸包図形の境界線上以外の各辺（以下「内部辺」という。）に対応して用意される重みデータを、所定の初期値に初期化する重み初期化ステップ；前記単射メッシュにおける前記各内部辺の長さの重み付き二乗和（以下「単射メッシュのポテンシャル」という。）を最小化するように、前記凸包内部データの頂点座標の再配置を行う再配置ステップ；を備え、前記再配置ステップにおいては、前記各重みデータを前記単射メッシュにおける各内部辺の重みとして計算される前記単射メッシュのポテンシャルが最小となるように、前記凸包内部データの座標の再配置を行うポテンシャル最小化ステップ；及び、前記各内部辺の重みデータを、当該内部辺近傍の単射メッシュの密度の逆数又は当該内部辺に対応する前記三次元メッシュの辺の周りの曲率の逆数に対し単調増加な関数値により更新する重み更新ステップ；を、前記各内部辺の重みデータの更新前後における前記単射メッシュのポテンシャルの最小値の変化量が所定の閾値以下となるまで反復実行することを特徴とする。【００４６】  本発明に係るメッシュ・データのパラメータ化方法の第２の構成は、前記第１の構成において、前記重み更新ステップにおいて、前記各内部辺の重みデータを当該内部辺の長さのｍ１乗（ｍ１＞０）又はその定数倍の値に更新することを特徴とする。【００４７】  本発明に係るメッシュ・データのパラメータ化方法の第３の構成は、前記第１の構成において、前記重み更新ステップにおいて、前記各内部辺の重みデータを、当該内部辺に隣接する単射メッシュの平均面積のｍ２乗（ｍ２＞０）又はその定数倍の値に更新することを特徴とする。【００４８】  本発明に係るメッシュ・データのパラメータ化方法の第４の構成は、前記第１の構成において、前記重み更新ステップにおいて、前記各内部辺の重みデータを、当該内部辺に対応する前記三次元メッシュ内の辺の周りの曲率の逆数のｍ３乗（ｍ３＞０）又はその定数倍の値に更新することを特徴とする。【００４９】  本発明に係るメッシュ・データのパラメータ化方法の第５の構成は、前記第１の構成において、前記重み更新ステップにおいて、前記各内部辺の重みデータを、当該内部辺の長さのｍ１乗（ｍ１＞０）の値、当該内部辺に隣接する単射メッシュの平均面積のｍ２乗（ｍ２＞０）の値、及び当該内部辺に対応する前記三次元メッシュ内の辺の周りの曲率の逆数のｍ３乗（ｍ３＞０）の値の何れか二以上の線形和に、前記各内部辺の重みを更新することを特徴とする。【００５０】  本発明に係るメッシュ・データの正則化方法の第１の構成は、平面凸包図形と同位相の三次元メッシュを表す非正則な三次元メッシュ・データを、正則化された三次元メッシュ・データに変換するメッシュ・データの正則化方法であって、前記三次元メッシュ・データの各頂点及び辺に対応して、前記三次元メッシュを所定の平面凸包図形内に単射した二次元メッシュ（以下「単射メッシュ」という。）を表す単射メッシュ・データを生成する単射メッシュ生成ステップ；前記平面凸包図形に対して所定の正則メッシュを表す正則メッシュ・データを生成する初期グリット生成ステップ；正則メッシュ・データの前記凸包図形内部の頂点座標を、前記単射メッシュに近似させて再配置する正則メッシュ変形ステップ；再配置された前記正則メッシュの各頂点の座標を、当該頂点が属する前記単射��ッシュ内のメッシュの各頂点（以下「単射メッシュ頂点」という。）の凸結合で表す場合における凸結合係数を算出する凸結合係数算出ステップ；及び、前記正則メッシュの各頂点が属する前記単射メッシュの単射メッシュ頂点の座標及び前記凸結合係数に基づき正則三次元モデルを再構築する正則三次元モデル構成ステップ；を備えたことを特徴とする。【００５１】  本発明に係るメッシュ・データの正則化方法の第２の構成は、前記第１の構成において、前記正則メッシュ変形ステップは、前記正則メッシュにおける前記凸包図形の境界線上以外の各辺（以下「内部グリッド辺」という。）に対応して用意される重みデータを、所定の初期値に初期化する重み初期化ステップ；前記正則メッシュにおける前記各内部グリッド辺の長さの重み付き二乗和（以下「正則メッシュのポテンシャル」という。）を最小化するように、前記正則メッシュ・データにおける前記凸包図形内部の頂点（以下「内部グリッド」という。）の座標の再配置を行う再配置ステップ；を備え、前記再配置ステップにおいては、前記各重みデータを前記正則メッシュにおける各内部グリッド辺の重みとして計算される前記正則メッシュのポテンシャルが最小となるように、前記正則メッシュ・データにおける、前記内部グリッドの座標の再配置を行う再配置ステップ；及び、前記各内部グリッド辺の重みを、当該内部グリッド辺近傍の前記単射メッシュの密度の逆数又は当該内部グリッド辺近傍の前記単射メッシュに対応する三次元メッシュの面積の逆数と単調増加関係にある値により更新する重み更新ステップ；を、前記各内部グリッド辺の重みデータの更新前後における前記正則メッシュのポテンシャルの最小値の変化量が所定の閾値以下となるまで反復実行することを特徴とする。【００５２】  本発明に係るメッシュ・データの正則化方法の第３の構成は、前記第２の構成において、前記重み更新ステップにおいて、前記各内部グリッド辺の重みを、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュのメッシュ数のｍ４乗（ｍ４＞０）又はその定数倍の値に更新することを特徴とする。【００５３】  本発明に係るメッシュ・データの正則化方法の第４の構成は、前記第２の構成において、前記重み更新ステップにおいて、前記各内部グリッド辺の重みを、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュの各頂点の曲率の和の逆数のｍ５乗（ｍ５＞０）又はその定数倍の値に更新することを特徴とする。【００５４】  本発明に係るメッシュ・データの正則化方法の第５の構成は、前記第２の構成において、前記重み更新ステップにおいて、前記各内部グリッド辺の重みを、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュに対応する前記三次元メッシュの面積の逆数のｍ６乗（ｍ６＞０）又はその定数倍の値に更新することを特徴とする。【００５５】  本発明に係るメッシュ・データの正則化方法の第６の構成は、前記第２の構成において、前記重み更新ステップにおいて、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュのメッシュ数のｍ４乗（ｍ４＞０）の値、当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュの各頂点の曲率の和の逆数���ｍ５乗（ｍ５＞０）の値、及び当該内部グリッド辺を含む所定の半径の円内に入る前記単射メッシュに対応する前記三次元メッシュの面積の逆数のｍ６乗（ｍ６＞０）の値の何れか二以上の線形和に、前記各内部辺の重みを更新することを特徴とする。【００５６】  本発明に係るメッシュ・データの正則化方法の第７の構成は、前記第１乃至６の何れかの構成において、前記単射メッシュ生成ステップにおいては、請求項１乃至５の何れか一の方法により三次元メッシュを平面凸包図形に写像することで単射メッシュを生成することを特徴とする。【００５７】  本発明に係るプログラムの第１の構成は、コンピュータに第１乃至５の何れかの構成のメッシュ・データのパラメータ化方法を実行させることを特徴とする。【００５８】  本発明に係るプログラムの第２の構成は、コンピュータに第１乃至７の何れかの構成のメッシュ・データの正則化方法を実行させることを特徴とする。
【発明の効果】
【００５９】  以上のように、本発明に係るメッシュ・データのパラメータ化装置及び方法によれば、三次元メッシュの平面凸包図形への単射により生成される単射メッシュにおける頂点分布の粗密が緩和され、或る程度の頂点分布の均質化が図られる。従って、生成された単射メッシュに正則メッシュを重ねてリメッシュを行う場合のリメッシュによる三次元モデルの歪みを抑えることができる。【００６０】  また、本発明に係るメッシュ・データの正則化装置及び方法によれば、リメッシュを実行する前に、三次元メッシュの平面凸包図形への単射により生成される単射メッシュと、正則メッシュとの間で頂点分布の粗密の整合が行われる。そのため、単射メッシュに正則メッシュを重ねてリメッシュを行う場合のリメッシュによる三次元モデルの歪みを抑えることができる。また、単射メッシュと正則メッシュとの間で頂点分布の粗密の整合を行うため、過分に細かい正則メッシュを使用する必要がなく、リメッシュ後のデータ量を小さく保ったまま歪みの少ないリメッシュを実行することが可能となる。
【発明を実施するための最良の形態】
【００６１】  以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００６２】  図１は、本発明の実施例１に係るパラメータ化装置１の構成を表すブロック図である。パラメータ化装置１は、三次元メッシュ記憶手段２に記憶された、三次元メッシュ・データを、三次元メッシュを所定の平面凸包図形内に単射した二次元メッシュ（単射メッシュ）を表す単射メッシュ・データに変換する装置である。【００６３】  ここで、本実施例においては、三次元メッシュを単射する平面凸包図形として長方形を使用することとする。【００６４】  パラメータ化装置１は、単射メッシュ記憶手段３、辺重み記憶手段４、境界写像手段５、初期配置手段６、重み初期化手段７、再配置手段８、及び出力手段９を備えている。【００６５】  単射メッシュ記憶手段３は、パラメータ化装置１の処理過程で生成される単射メッシュを一時的に記憶する。辺重み記憶手段４は、単射メッシュの各内部辺に対して設定される重みデータを記憶する。【００６６】  境界写像手段５は、三次元メッシュの境界線上の各頂点の三次元メッシュ・データに対応して、凸包図形（四角形）の境界線上の頂点及び辺の単射メッシュ・データ（凸包境界データ）を生成する。初期配置手段６は、三次元メッシュの境界線上以外の各頂点及び辺の三次元メッシュ・データに対応して、包図形内部の頂点及び辺の単射メッシュ・データ（凸包内部データ）を生成する。重み初期化手段７は、単射メッシュにおける内部辺（凸包図形の境界線上以外の各辺）に対応して用意される重みデータを、所定の初期値に初期化する。【００６７】  再配置手段８は、単射メッシュにおける各内部辺の長さの重み付き二乗和（単射メッシュのポテンシャル）を最小化するように、凸包内部データの頂点座標の再配置を行う。出力手段９は、最終的に得られた単射メッシュ・データを出力する。【００６８】  また、再配置手段８は、ポテンシャル最小化手段１１、重み更新手段１２、及び単射メッシュ緩和手段１３を備えている。【００６９】  ポテンシャル最小化手段１１は、辺重み記憶手段４に記憶された各重みデータを単射メッシュにおける各内部辺の重みとして計算される単射メッシュのポテンシャルが最小となるように、凸包内部データの座標の再配置を行う。重み更新手段１２は、各内部辺の重みデータを、当該内部辺近傍の単射メッシュの密度の逆数（又は当該内部辺に対応する三次元メッシュの辺の周りの曲率の逆数）に対し単調増加な関数値により更新する。【００７０】  単射メッシュ緩和手段１３は、重み更新手段１２により各内部辺の重みデータの更新を行った後にポテンシャル最小化手段１１により凸包内部データの座標の再配置を行う操作を、各内部辺の重みデータの更新前後における単射メッシュのポテンシャルの最小値の変化量が所定の閾値以下となるまで反復実行する制御を行う。【００７１】  以上のように構成された本実施例に係るパラメータ化装置１について、以下その動作を説明する。【００７２】  図２は、実施例１のパラメータ化装置１による三次元メッシュのパラメータ化方法を表すフローチャートである。【００７３】  最初に、三次元メッシュ記憶手段２に、三次元メッシュ・データが格納される。この三次元メッシュ・データは、三次元モデルの表面を表すＮ個の頂点ｖｉ＝（ｘｉ，ｙｉ，ｚｉ）（∈Ｒ３，ｉ＝０，２，…，Ｎ−１）と、３つのインデックス（ｉ，ｊ，ｋ）を有する三角形メッシュＴを有する。３つのインデックス（ｉ，ｊ，ｋ）は、それぞれ、三角形のメッシュの頂点のインデックスを表している。例えば、三次元メッシュ記憶手段２には、図３（ａ）に示したようなメッシュが格納される。【００７４】  また、三次元メッシュ・データは、平面凸包図形と同位相であるとする。平面凸包図形と同位相とは、三次元メッシュ・データにより表される曲面が、球のように閉じた部分がなく、かつ、ドーナツ型のように貫通孔が空いておらず、円板と位相的に同型であることをいう。【００７５】  まず、ステップＳ１において、境界写像手段５は、三次元メッシュ記憶手段２から三次元メッシュ・データを読み出す。【００７６】  ステップＳ２において、境界写像手段５は、凸包境界データを生成する。三次元メッシュ・データにより表される曲面は平面凸包図形と同位相であるため、必ず外端縁が存在する。この外端縁を「境界」と呼ぶ。境界写像手段５は、この境界上の頂点から、強化以上の順番がほぼ等間隔となるように４つの頂点を選択する。そして、まずこの４つの頂点を、四角形の単射メッシュ平面の４つの頂点に対応付け（図３（ｂ）参照）、４つの凸包境界データを生成する。次いで、境界上の頂点のうち、上記４つの頂点以外の頂点を、四角形の単射メッシュ平面の各辺に等間隔で割り当て、残りの凸包境界データを生成する。生成された凸包境界データは、単射メッシュ記憶手段３に保存される。【００７７】  ステップＳ３において、初期配置手段６は、三次元メッシュの境界以外の各頂点を、四角形の単射メッシュ平面の内部に適当に割り当てることにより、凸包内部データを生成する。生成された凸包内部データは、単射メッシュ記憶手段３に保存される。【００７８】  ステップＳ４において、重み初期化手段７は、三次元メッシュ記憶手段２に記憶された三次元メッシュの境界以外の各辺に対応して、重みデータωｍ（ｍ＝０，２，…，Ｎｅ−１；Ｎｅは内部辺の数）を生成する。生成した重みデータωｍには、初期値として１を設定する。これらの重みデータωｍは、辺重み記憶手段４に記憶される。【００７９】  ステップＳ５において、ポテンシャル最小化手段１１は、凸包内部データの各頂点の再配置を行う。この再配置は、式（４）で表される単射メッシュのポテンシャル（辺の長さの重み付き二乗和）Ｆが最小となるように決定される。【００８０】
【数３】
2006285931.tif 000005
【００８１】  ここで、ωｍはｍ番目の内部辺の重みを表す。ｕｉ（∈Ｒ２）は単射メッシュ平面における頂点のｉ番目の頂点の位置ベクトルを表す。ｅｍ＝（ｍｉ，ｍｊ）はｍ番目の内部辺を表す。ｍｉ，ｍｊは、内部辺ｅｍを構成する頂点の番号を表す。また、Ｅ＝｛ｅｌ：ｌ＝０，１，…，Ｎｅ−１｝は内部辺の集合を表す。【００８２】  ポテンシャル最小化手段１１は、式（４）のポテンシャルを最小化するようにｕｉ，ｕｊを決定するのであるが、この最小化の問題は式（５）のスパースシステム線形方程式を解くことに帰着される。そして、式（５）の方程式を解くことによって、三次元メッシュのパラメータ化が行われる。得られた単射メッシュ・データは単射メッシュ記憶手段３に保存される。【００８３】
【数４】
2006285931.tif 000006
【００８４】
【数５】
2006285931.tif 000007
【００８５】  ここで、Ｎは頂点の総数を表す。ｘｎ，ｙｎ（ｎ＝０，１，…，Ｎ−１）はｎ番目の頂点のｘ座標及びｙ座標を表す。Ｎｅは辺集合Ｅに含まれる内部辺の数である。【００８６】  Ａ０はＮｅ行２Ｎ列の行列であり、内部辺ｅｍ＝（ｍｉ，ｍｊ）に対してｍ行目が対応し、第ｍ行は、２ｍｉ列目が１、２ｍｊ列目が−１、その他の列がすべて０である。同様に、Ａ１もＮｅ行２Ｎ列の行列であり、内部辺ｅｍ＝（ｍｉ，ｍｊ）に対してｍ行目が対応し、第ｍ行は、２ｍｉ＋１列目が１、２ｍｊ＋１列目が−１、その他の列がすべて０である。【００８７】  ｂ０，ｂ１は境界上の頂点のｘ座標、ｙ座標をそれぞれ要素に持つベクトルである。【００８８】  また、Ｗは式（９）のように、重みωｍを対角要素に持つ対角行列である。【００８９】
【数６】
2006285931.tif 000008
【００９０】  ステップＳ６において、単射メッシュ緩和手段１３は、式（４）を最小化することにより得られたポテンシャルＦと、前回の重みを用いて式（４）を最小化することにより得られたポテンシャルＦ’とを比較する。その結果、｜Ｆ−Ｆ’｜が所定の閾値ＴＦより大きければ次のステップＳ７に進み、ＴＦ以下であればステップＳ８へ移行する。【００９１】  尚、第１回目のループでは前回のポテンシャルＦ’はまだないので、無条件に次のステップＳ７に進む。【００９２】  ステップＳ７において、重み更新手段１２は、各内部辺ｅｍ＝（ｍｉ，ｍｊ）の重みｗｍを更新し、ステップＳ５に戻る。【００９３】  ここで、各内部辺ｅｍの重みの更新は、以下の４つの方法の何れかが用いられる。【００９４】（重み更新法１）
パラメータ化後得られた単射メッシュの各内部辺ｅｍ（ｍ＝０，１，…，Ｎｅ−１）の長さのα乗（α＞０）を重みωｍとする。すなわち、式（１０）により更新を行う。【００９５】
【数７】
2006285931.tif 000009
【００９６】（重み更新法２）
各内部辺ｅｍの周囲にある三角形メッシュの面積の平均のα乗（α＞０）を重みとする。ここで、各内部辺ｅｍと隣接する三角形メッシュとしては、その内部辺を含む三角形メッシュ又はそれに加えてその内部辺の両端の頂点を含むメッシュなどが用いられる。【００９７】（重み更新法３）
各内部辺ｅｍの周囲の曲率を数値化し、その曲率の逆数を重みとする。ここで、距留率を数値化する方法としては、例えば、内部辺ｅｍを挟む二つの三角形メッシュの法線を計算し、その法線の為す角から曲率を計算することができる。【００９８】（重み更新法４）
上記の重み更新法１〜３で得られる重みについて、重み付き線形和をとってこれを重みとする。【００９９】  ステップＳ８において、重みの変化量｜Ｆ−Ｆ’｜が所定の閾値ＴＦ以下となったので、単射メッシュ記憶手段３に保存されているデータを出力する。【０１００】  以上の動作により、ポテンシャル最小化手段１１が単射メッシュのポテンシャルを計算する際に、単射メッシュの各内部辺の近傍のメッシュ密度が小さい辺（又は当該内部辺に対応する三次元メッシュの辺の曲率が小さい辺）に対しては式（４）により大きな重みが加えられる。ポテンシャル最小化手段１１は式（５）のポテンシャルを最小化する方向に頂点座標を動かすため、大きな重みが加えられた辺の長さは短縮され、その周囲のメッシュは密集化する。逆に、重みの小さい辺は引き延ばされ、その周囲のメッシュは疎散化される。【０１０１】  その結果、単射メッシュ緩和手段１３による凸包内部データの座標の再配置過程において、メッシュ密度が小さい領域（対応する三次元メッシュの曲率が小さい領域）ではメッシュが密となる方向に再配置され、メッシュ密度が大きい領域（対応する三次元メッシュの曲率が大きい領域）ではメッシュが密となる方向に再配置され、全体として単射メッシュのポテンシャルの釣り合いがとれた状態に緩和されて安定化する。【０１０２】  これにより、単射メッシュにおける頂点分布の粗密が緩和され、生成された単射メッシュに正則メッシュを重ねてリメッシュを行う場合のリメッシュによる三次元モデルの歪みを抑えることができる。
【実施例２】
【０１０３】  図４は、本発明の実施例２に係るメッシュ・データの正則化装置２０の構成を表すブロック図である。尚、図４において、パラメータ化装置１及び三次元メッシュ記憶手段２は、図１と同様のものである。【０１０４】  正則化装置２０は、平面凸包図形と同位相の非正則な三次元メッシュを正則化し、正則化された三次元メッシュ・データを生成する装置である。【０１０５】  正則化装置２０は、パラメータ化装置１、単射メッシュ記憶手段２１、正則メッシュ記憶手段２２、辺重み記憶手段２３、初期グリッド生成手段２４、重み初期化手段２５、再配置手段２６、凸結合係数算出手段２７、及び正則三次元モデル構成手段２８を備えている。【０１０６】  三次元メッシュ記憶手段２には平面凸包図形と同位相の非正則な三次元メッシュのデータ（三次元メッシュ・データ）が記憶される。また、パラメータ化装置１は、三次元メッシュ・データの各頂点及び辺に対応して、三次元メッシュを所定の平面凸包図形内に単射した二次元メッシュ（単射メッシュ）を表す単射メッシュ・データを生成する。これらは、実施例１と同様である。【０１０７】  単射メッシュ記憶手段２１は、パラメータ化装置１により生成され出力される単射メッシュを記憶する。正則メッシュ記憶手段２２は、リメッシュにより単射メッシュを正則化して得られる正則メッシュを記憶する。辺重み記憶手段２３は、正則メッシュの境界線上以外の各辺（内部グリット辺）ｅｍ（ｍ＝０，１，…，Ｎｅ）に対する重みωｍを記憶する。【０１０８】  初期グリッド生成手段２４は、平面凸包図形に対して所定の正則メッシュを表す正則メッシュ・データを生成する。重み初期化手段２５は、正則メッシュにおける凸包図形の境界線上以外の各辺（内部グリッド辺）に対応して用意される重みデータを、１に初期化する。【０１０９】  再配置手段２６は、正則メッシュにおける各内部グリッド辺の長さの重み付き二乗和（正則メッシュのポテンシャル）を最小化するように、正則メッシュ・データにおける凸包図形内部の頂点（内部グリッド）の座標の再配置を行う。【０１１０】  凸結合係数算出手段２７は、再配置された正則メッシュの各頂点の座標を、当該頂点が属する単射メッシュ内のメッシュの各頂点（単射メッシュ頂点）の凸結合で表す場合における凸結合係数を算出する。【０１１１】  正則三次元モデル構成手段２８は、正則メッシュの各頂点が属する単射メッシュの単射メッシュ頂点の座標及び凸結合係数に基づき正則三次元モデルを再構築する。【０１１２】  また、再配置手段２６は、ポテンシャル最小化手段２９、重み更新手段３０、及び正則メッシュ緩和手段３１を備えている。【０１１３】  ポテンシャル最小化手段２９は、各重みデータを正則メッシュにおける各内部グリッド辺の重みとして計算される正則メッシュのポテンシャルが最小となるように、正則メッシュ・データにおける、内部グリッドの座標の再配置を行う。【０１１４】  重み更新手段３０は、各内部グリッド辺の重みを、当該内部グリッド辺近傍の単射メッシュの密度の逆数（又は当該内部グリッド辺近傍の単射メッシュに対応する三次元メッシュの面積の逆数）と単調増加関係にある値により更新する。【０１１５】  正則メッシュ緩和��段３１は、重み更新手段３０により各内部グリッド辺の重みデータの更新を行った後にポテンシャル最小化手段２９により内部グリッドの座標の再配置を行う操作を、各内部グリッド辺の重みデータの更新前後における正則メッシュのポテンシャルの最小値の変化量が所定の閾値以下となるまで反復実行する。【０１１６】  以上のように構成された本実施例の正則化装置２０について、以下その動作を説明する。図５は、実施例２の正則化装置２０による三次元メッシュの正則化方法を表すフローチャートである。【０１１７】  まず、ステップＳ１１において、パラメータ化装置１は、三次元メッシュ記憶手段２に記憶された非正則メッシュを２次元の長方形状の単射メッシュにパラメータ化する。例えば、図６（ａ）に示したような単射メッシュが生成される。このパラメータ化については、実施例１で説明した通りである。得られた単射メッシュ・データは、単射メッシュ記憶手段２１に保存される。【０１１８】  ステップＳ１２において、初期グリッド生成手段２４は、単射メッシュ記憶手段３に記憶された単射メッシュ・データが表す単射メッシュと同じアスペクト比の正則メッシュ（初期グリッド）を生成する。この初期グリッドは、予め定められたものであり、内部頂点は６つの辺を有する６−準正則メッシュが用いられる（図６（ｂ）参照）。【０１１９】  ステップＳ１３において、重み初期化手段２５は、正則メッシュにおける内部グリッド辺における重みデータを１に初期化し、辺重み記憶手段２３に保存する。【０１２０】  ステップＳ１４において、ポテンシャル最小化手段２９は、正則メッシュのポテンシャルが最小となるように、正則メッシュ・データにおける内部グリッドの座標の再配置を行う。ここで、正則メッシュのポテンシャルは式（４）と同様にして計算される。また、内部グリッドの座標の再配置の方法も、実施例１で説明したスパースシステム線形方程式を用いた方法により行われる。再配置された正則メッシュ・データは、正則メッシュ記憶手段２２に保存される。【０１２１】  ステップＳ１５において、正則メッシュ緩和手段３１は、現在の重みデータに基づいてポテンシャル最小化手段２９が算出した現在のポテンシャルＦと、前回の重みを用いてポテンシャル最小化手段２９が算出した前回のポテンシャルＦ’とを比較する。その結果、｜Ｆ−Ｆ’｜が所定の閾値ＴＦより大きければ次のステップＳ１６に進み、ＴＦ、以下であればステップＳ１７へ移行する。【０１２２】  尚、第１回目のループでは前回のポテンシャルＦ’はまだないので、無条件に次のステップＳ１６に進む。【０１２３】  ステップＳ１６において、重み更新手段３０は、各内部グリッド辺ｅｍ＝（ｍｉ，ｍｊ）の重みｗｍを更新し、ステップＳ１４に戻る。【０１２４】  ここで、各内部グリッド辺ｅｍの重みの更新は、以下の４つの方法の何れかが用いられる。【０１２５】（重み更新法１）
単射メッシュ平面と内部グリッド平面とを重ね合わせ、単射メッシュにおいて、内部グリッド辺ｅｍを含む半径ｒの円を考える。その円内に入る単射メッシュの数の逆数のα乗（α＞０）をその内部グリッド辺ｅｍの新たな重みとする。【０１２６】（重み更新法２）
まず、三次元メッシュのすべての頂点の周りの曲率を計算する。計算された各頂点の曲率を、対応する単射メッシュの頂点の曲率とする。次に、単射メッシュ平面と内部グリッド平面とを重ね合わせ、単射メッシュにおいて、内部グリッド辺ｅｍを含む半径ｒの円を考える。そして、その円内に入るすべての単射メッシュの頂点の曲率の和を求め、その和の逆数のα乗（α＞０）をその内部グリッド辺ｅｍの新たな重みとする。【０１２７】（重み更新法３）
単射メッシュ平面と内部グリッド平面とを重ね合わせ、単射メッシュにおいて、内部グリッド辺ｅｍを含む半径ｒの円を考える。その円内に入る単射メッシュに対応する三次元メッシュの面積の和を求める。そして、その和の逆数のα乗（α＞０）をその内部グリッド辺ｅｍの新たな重みとする。【０１２８】（重み更新法４）
上記の重み更新法１〜３で得られる重みについて、重み付き線形和をとってこれを重みとする。【０１２９】  このように、正則メッシュの各内部グリッド辺の近傍の単射メッシュ密度が小さい辺（又は当該内部グリッド辺近傍の単射メッシュに対応する三次元メッシュの面積が大きい辺）に対しては大きな重みが加えられる。従って、正則メッシュ緩和手段３１による正則メッシュ・データの座標の再配置過程において、単射メッシュ密度が小さい領域（単射メッシュに対応する三次元メッシュの面積が大きい領域）では正則メッシュが密となる方向に再配置され、単射メッシュ密度が大きい領域（単射メッシュに対応する三次元メッシュの面積が小さい領域）では正則メッシュが密となる方向に再配置され、全体として正則メッシュのポテンシャルの釣り合いがとれた状態に緩和されて安定する。【０１３０】  これにより、正則メッシュにおける頂点分布が単射メッシュにおける頂点分布に近似されるため、生成された正則メッシュと単射メッシュとを重ねてリメッシュを行った場合のリメッシュによる三次元モデルの歪みを抑えることができる。【０１３１】  以上のステップＳ１４〜Ｓ１６が繰り返されることにより、正則メッシュの変形が実行される。最終的に、正則メッシュのポテンシャルが、正則メッシュの再構成（Ｓ１４）により変化しなくなった時点で、ステップＳ１７に移る。【０１３２】  ステップＳ１７において、凸結合係数算出手段２７は、正則メッシュ記憶手段２２内の正則メッシュと単射メッシュ記憶手段２１内の単射メッシュとを重ね合わせる。そして、正則メッシュの各頂点が単射メッシュのどの位置にあるかを、式（１１）の凸結合により表し、各凸結合係数α，β，γを求める。【０１３３】
【数８】
2006285931.tif 000010
【０１３４】  ここで、凸結合係数α，β，γは実数である。【０１３５】  ステップＳ１８において、正則三次元モデル構成手段２８は、凸結合係数α，β，γを用いて、正則メッシュの各頂点に対応する三次元空間上の座標を求め、正則三次元モデルを構築する。【０１３６】  以上のように、本実施例２の正則化装置２０では、単射メッシュに重ね合わされる前に、正則メッシュの頂点分布と単射メッシュの頂点分布が近似するように、正則メッシュの頂点座標の調整が行われる。従って、リメッシュにおける単射メッシュと正則メッシュとの頂点分布密度の差によるリメッシュ後の三次元モデルの歪みを抑えることが可能となる。【０１３７】  また、単射メッシュの頂点分布の濃淡に適応して正則メッシュの頂点分布の濃淡が調整されるため、正則メッシュとして過分に細かいメッシュを用いる必要はない。従って、リメッシュ後のデータ量を抑えることが可能となる。【０１３８】  尚、実施例１，２におけるパラメータ化装置１及び正則化装置２０は、ハードウェアにより構成してもよいが、各機能ブロックをプログラムにより構成し、コンピュータで当該プログラムを実行することにより、上記パラメータ化装置１及び正則化装置２０を実現するようにしたもよい。
【図面の簡単な説明】
【０１３９】
【図１】  本発明の実施例１に係るパラメータ化装置１の構成を表すブロック図である。
【図２】  実施例１のパラメータ化装置１による三次元メッシュのパラメータ化方法を表すフローチャートである。
【図３】  パラメータ化の例を表す図である。
【図４】  本発明の実施例２に係るメッシュ・データの正則化装置２０の構成を表すブロック図である。
【図５】  実施例２の正則化装置２０による三次元メッシュの正則化方法を表すフローチャートである。
【図６】  パラメータ後の単射メッシュ（ａ）と初期グリッド生成手段２４により生成される初期グリッド（正則メッシュ）の例を示す図である。
【図７】  三次元メッシュ・モデルのワイヤ・フレーム（ｗｉｒｅ  ｆｒａｍｅ）を表す図である。
【図８】  非正則メッシュ（ａ）と正則メッシュ（ｂ）の例を示す図である。
【図９】  凸結合によるパラメータ化の一例を示す図である。
【図１０】  非正則メッシュから正則メッシュへの写像を説明する図である。
【符号の説明】
【０１４０】１  パラメータ化装置
２  三次元メッシュ記憶手段
３  単射メッシュ記憶手段
４  辺重み記憶手段
５  境界写像手段
６  初期配置手段
７  重み初期化手段
８  再配置手段
９  出力手段
１１  ポテンシャル最小化手段
１２  重み更新手段
１３  単射メッシュ緩和手段
２０  正則化装置
２１  単射メッシュ記憶手段
２２  正則メッシュ記憶手段
２３  辺重み記憶手段
２４  初期グリッド生成手段
２５  重み初期化手段
２６  再配置手段
２７  凸結合係数算出手段
２８  正則三次元モデル構成手段
２９  ポテンシャル最小化手段
３０  重み更新手段
３１  正則メッシュ緩和手段
【図１】
2006285931.tif 000011
【図２】
2006285931.tif 000012
【図３】
2006285931.tif 000013
【図４】
2006285931.tif 000014
【図５】
2006285931.tif 000015
【図６】
2006285931.tif 000016
【図７】
2006285931.tif 000017
【図８】
2006285931.tif 000018
【図９】
2006285931.tif 000019
【図１０】
2006285931.tif 000020