(57)【要約】【課題】  本発明は、３次元空間内の物体表面をできるだけ少ない歪みと少ない計算量で平面上に展開する。【解決手段】  本発明の装置は、３次元空間内の物体表面を表現する入力データ３０１から物体表面を構成する多角形の情報を抽出する手段（３０２）と、抽出された各多角形に関して、当該多角形と頂点を共有する周囲多角形を抽出する手段（３０３）と、抽出された当該多角形と周囲多角形との間で共有されるべき頂点間の距離が最小になるという条件に従って、物体表面を構成する多角形の位置を決定する手段（３０４，３０５）と、共有されるべき頂点に対応したすべての頂点の座標の重心位置を求め、その重心位置を前記共有されるべき頂点の座標に設定する手段（３０６，３０７）と、を有する。【選択図】          図３
2005190019.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ上に表現された３次元空間内の物体表面を平面上に展開する方法であって、
前記３次元空間内の物体表面を表現する入力データから前記物体表面を構成する多角形の情報を抽出するステップと、
抽出された各多角形に関して、当該多角形と頂点を共有する周囲多角形を抽出するステップと、
抽出された当該多角形と前記周囲多角形との間で共有されるべき頂点間の距離が最小になるという条件に従って、前記物体表面を構成する多角形の位置を決定するステップと、
共有されるべき頂点に対応したすべての頂点の座標を代表する位置を求め、その代表する位置を前記共有されるべき頂点の座標に設定するステップと、
を有する方法。
【請求項２】
コンピュータ上に表現された３次元空間内の物体表面を平面上に展開する装置であって、
前記３次元空間内の物体表面を表現する入力データから前記物体表面を構成する多角形の情報を抽出する手段と、
抽出された各多角形に関して、当該多角形と頂点を共有する周囲多角形を抽出する手段と、
抽出された当該多角形と前記周囲多角形との間で共有されるべき頂点間の距離が最小になるという条件に従って、前記物体表面を構成する多角形の位置を決定する手段と、
共有されるべき頂点に対応したすべての頂点の座標を代表する位置を求め、その代表する位置を前記共有されるべき頂点の座標に設定する手段と、
を有する装置。
【請求項３】
コンピュータ上に表現された３次元空間内の物体表面を平面上に展開する装置であって、
前記３次元空間内の物体表面の多角形を表現する入力データを受け取り、前記入力データから前記多角形の情報を抽出する多角形スキャン部と、
前記多角形スキャン部に接続され、前記多角形スキャン部で抽出された前記多角形に対して、当該多角形の周囲にある周囲多角形の情報を抽出する周囲多角形抽出部と、
前記多角形スキャン部で抽出された前記多角形の情報及び前記周囲多角形抽出部で抽出された前記周囲多角形の情報に基づいて、前記平面上での各多角形の位置に関する係数を含む一次方程式を作成する一次方程式作成部と、
前記一次方程式作成部に接続され、前記一次方程式を解くことにより、前記各多角形の位置を算出する多角形位置演算部と、
前記多角形位置演算部に接続され、前記多角形位置演算部で算出された前記各多角形の位置に基づいて、前記各多角形に属する頂点の前記平面上での座標を計算する並べ合わせ部と、
前記並べ合わせ部で計算された前記各多角形の頂点を、隣接する多角形間の隙間や重なり合いが無くなるように移動させることにより前記多角形の形状を補正し、最終的な多角形の情報である出力データを出力する多角形形状補正部と、
を有する装置。
【請求項４】
コンピュータ上に表現された３次元空間内の物体表面を平面上に展開する物体表面平坦化装置であって、
入力データから多角形の形状情報を抽出する手段と、
前記多角形と頂点を共有する周囲多角形の形状情報を抽出する手段と、
前記多角形の形状情報及び前記周囲多角形の形状情報から、多角形毎に各多角形の位置に関する一次式の係数を取得する手段と、
前記多角形毎の前記一次式からなる連立した一次式を解くことにより、前記各多角形の位置を算出する手段と、
前記位置を算出された各多角形を並べる手段と、
を有する物体表面平坦化装置。
【請求項５】
前記並べられた各多角形の形状を補正する手段を更に有する請求項４記載の物体表面平坦化装置。
【請求項６】
前記入力データは３次元空間内の物体表面を構成する多角形の形状を表すデータを含み、
前記多角形の形状を表すデータは、共通の始点から多角形の各頂点への２次元ベクトルであり、
前記共通の始点へのベクトルは多角形の位置を表すベクトルである、
請求項４又は５記載の物体表面平坦化装置。
【請求項７】
前記入力データは、３次元空間内の物体表面を構成する多角形の相対位置を表すデータを更に含み、
前記相対位置を表すデータは、３次元空間内の物体表面を構成する多角形の各頂点に対し、各頂点をどの多角形が共有しているかを示す情報、及び／又は、３次元空間内の物体表面を構成する多角形にはどの頂点が存在しているかを示す情報である、
請求項４乃至６のうちいずれか１項記載の物体表面平坦化装置。
【請求項８】
前記各多角形の位置に関する一次式の係数を取得する手段は、ある中心多角形と、その多角形と頂点を共有する周囲多角形との間で、同一点にあるべき頂点間の距離の２乗和が最小になるような、中心多角形と周囲多角形との相対位置を示す一次式の係数を取得する、請求項４乃至７のうちいずれか１項記載の物体表面平坦化装置。
【請求項９】
前記各多角形の位置を算出する手段は、最小２乗法を用いて前記連立した一次式を解くことにより各多角形の位置を算出する、請求項４乃至８のうちいずれか１項記載の物体表面平坦化装置。
【請求項１０】
前記入力データに含まれる多角形は縦横に整列して配置された四角形であり、
前記多角形の形状情報を抽出する手段は、整列して配置された四角形の配置場所に対応した多角形インデクスから前記３次元空間内の物体表面を構成する多角形の相対位置を表すデータを決定し、
前記一次式の係数を取得する手段は、中心多角形と周囲多角形の相対位置から前記一次式の係数を決定する、
請求項４記載の物体表面平坦化装置。
【請求項１１】
前記共通の始点は多角形の所定の頂点に固定されている、請求項６記載の物体表面平坦化装置。
【請求項１２】
多角形の頂点以外の辺上に他の多角形の頂点が存在している場合に、前記多角形の辺上にある前記頂点から線分又は半直線を引くことにより、前記頂点と別の辺との交点を新たな頂点とする多角形分割手段を更に具備する、請求項４乃至１０のうちいずれか１項記載の物体表面平坦化装置。
【請求項１３】
３次元空間内の物体表面を表現する入力データから前記物体表面を構成する多角形の情報を抽出するステップと、
抽出された各多角形に関して、当該多角形と頂点を共有する周囲多角形を抽出するステップと、
抽出された当該多角形と前記周囲多角形との間で共有されるべき頂点間の距離が最小になるという条件に従って、前記物体表面を構成する多角形の位置を決定するステップと、
共有されるべき頂点に対応したすべての頂点の座標を代表する位置を求め、その代表する位置を前記共有されるべき頂点の座標に設定するステップと、
をコンピュータに実行させ、コンピュータ上に表現された３次元空間内の物体表面を平面上に展開するプログラム。
【請求項１４】
請求項１３記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は多面体で構成される３次元空間内の物体を、２次元平面に展開する方法及び装置に関するものである。
【背景技術】
【０００２】
コンピュータ上で現実感を持った画像を生成する手法としてコンピュータグラフィック（以下、ＣＧ）技術が広く利用されている。ＣＧ技術において、物体の表面形状を多角形の集合体として近似することが周知であり、そのための手法として、例えば、サーフェスモデル、又は、ポリゴングラフィックスが使用されている。このように多角形の集合体で表現された３次元空間内の物体表面を２次元平面に展開する技術はコンピュータによる画像処理の種々の場面、例えば、以下の（１）から（３）の場面で利用される。
（１）画像スキャナーで画像をスキャンインした後で、スキャン時の条件により歪んでしまった画像を補正する。例えば、書物の表面を平面化する。
（２）複雑な３次元曲面を２次元平面に変換することにより、３次元曲面へのテクスチャマッピングを、簡易的に２次元平面上で行う。
（３）複雑な３次元曲面を２次元平面に変換することにより、３次元曲面そのままの場合よりも保持するテクスチャ情報量を削減する（例えば、非特許文献２を参照。）。
【０００３】
（１）のタイプの画像スキャナーの歪み補正の方式として、撮影された湾曲物体の表面形状を計算機上で平面形状に変換することが提案されている（例えば、非特許文献１を参照。）。この方式は、撮影された湾曲物体の表面形状を計算機上で平面形状に変換する。例えば、本の表面形状のように、本来は平面であるにもかかわらず、画像のスキャン入力時の制約によって湾曲したまま画像入力せざるを得ない場合に、湾曲物体の表面上の画像を平面上の画像に変換する際に、３次元空間内の物体表面を２次元平面に展開する技術を応用することができる。
【０００４】
（２）のタイプの応用例として、複雑な形状の表面に対して、できるだけ歪みの少ないテクスチャマッピングを行う方式が提案されている（例えば、特許文献１を参照。）。提案されている方法によれば、展開不可能な表面を平面に展開することで、歪みをできるだけ小さくしたテクスチャマッピングを行うことができる。ここで、任意の２点間の距離を変化させずに、３次元空間内の物体表面を２次元平面に変換することができる場合、その物体表面は「展開可能」と定義する。できない場合、「展開不可能」と定義する。一般にガウス曲率が全面にわたって０の曲面は平面に展開可能であり、ガウス曲率が０ではない曲面は平面に展開不可能であることが知られている。例えば、円筒の側面は平面に展開できるが、球面はガウス曲率が０ではないため、平面に展開することはできない。
【０００５】
非特許文献１に記載された方式では、最初に、３次元形状の表面から抽出した点の間の距離(測地線の長さ)を計測し、その距離の変化の大きさができるだけ小さくなるように平面に展開する。次に、展開された平面にテクスチャをマッピングする。最後に、先の曲面から平面への展開の逆操作を行って、平面テクスチャマップを元の３次元形状に変換する。このように、３次元形状を２次元平面に展開する手法は、見た目の歪みが小さなテクスチャマッピング手法に利用することができる。
【０００６】
次に、展開不可能な曲面を平面に展開する方式の他の例として、平面に展開可能な物体表面(可展体面)を媒介として展開を行う方式も提案されている。特に、（３）のタイプの方式として、テクスチャ表面を展開することによって、テクスチャマッピングを効率的に行おうとする方式が知られている（例えば、非特許文献２を参照。）。
【０００７】
非特許文献２に記載された方式では、撮影した２次元データから３次元形状を復元する処理を用いて任意視点の画像を表示する。さらに、この表示方式において、テクスチャ画像情報のデータ量を削減する手法が提案されている。この表示方式においては、２次元データから得られた各微小平面のテクスチャを個々の微小平面ごとに保持するのではなく、３次元形状を平面に展開して、隙間のできるだけ少ない展開図のテクスチャを保持することによって効率的に画像データを保持する。
【０００８】
非特許文献２によれば、３次元オブジェクトの特徴点を可展体面である既知形状面(円筒、柱体、錐体等)の投影面に投影することにより３次元オブジェクトを平面に展開し、次に、各特徴点を頂点とする多角形に対して、この展開平面上でテクスチャマッピングを行う。このように、一度、展開可能な物体表面に投影することによって、複雑な３次元形状を平面に展開することが可能となる。
【特許文献１】特開２０００−２０７３５号公報
【非特許文献１】天野敏之、安部  勉、西川  修、伊與田哲男、佐藤幸男、「アイスキャナによる湾曲ドキュメント撮影」、電子情報通信学会論文誌D-II、Vol. J86-D-II, No. 3, March 2003, pp.409-417
【非特許文献２】「Texture Mapping Using Surface Flattening via Multidimensional Scaling」、IEEE Trans. Visualization and Computer Graphics, vol. 8, no. 2, pp. 198-206, Apr.-June, 2002
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上記（１）のタイプの方式は、適用できる３次元空間内の物体表面が書物の表面、即ち、可展開面に限定されており、一般の展開不可能な物体表面に適用することができない。
【００１０】
上記（２）のタイプの方式は、３次元形状から測地線を求める計算量が非常に大きいという問題点があった。
【００１１】
一方、上記（３）のタイプの方式は、厳密に測地線の距離を求めずに、３次元空間上にある物体表面を一旦可展体面に投影することで展開を行うため、計算量が少なくて済む。しかしながら、上記（３）のタイプの方式では、元の物体の３次元表面形状が平面に展開不可能な場合には、できるだけ元の物体の表面に近い可展体面を選んでも、結局は、可展体面に投影する段階で歪みが発生してしまう、という問題点があった。
【００１２】
したがって、本発明は、上記従来技術の問題点に鑑み、３次元空間内の物体表面が多角形の集合体として表されている場合に、前記物体表面が展開不可能な場合に対しても、できるだけ少ない歪みと少ない計算量で、前記物体表面を展開することのできる物体表面平坦化装置及び方法の提供を目的とする。
【００１３】
また、本発明は、このような物体表面平坦化装置において行われる処理をコンピュータに実現させるためのプログラム、及び、このプログラムを記録した記録媒体の提供を目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するため、本発明は、３次元空間内の物体表面を構成若しくは近似する多角形を平面上に展開する際に、展開によって分割された頂点間の距離をできるだけ小さくするように多角形を並べることによって歪みの小さな展開画像を作成する。
【００１５】
請求項１記載の発明は、コンピュータ上に表現された３次元空間内の物体表面を平面上に展開する方法であって、この方法は、前記３次元空間内の物体表面を表現する入力データから前記物体表面を構成する多角形の情報を抽出するステップと、抽出された各多角形に関して、当該多角形と頂点を共有する周囲多角形を抽出するステップと、抽出された当該多角形と前記周囲多角形との間で共有されるべき頂点間の距離が最小になるという条件に従って、前記物体表面を構成する多角形の位置を決定するステップと、共有されるべき頂点に対応したすべての頂点の座標を代表する位置を求め、その代表する位置を前記共有されるべき頂点の座標に設定するステップと、を有する。
【００１６】
請求項１記載の発明によれば、隣接する多角形間の隙間や重なり合いが無くなるように多角形の位置と形状が決められ、３次元空間内の物体表面は２次元平面上に隙間や重なり合い無く展開される。また、測地線を計算する手間が省略される。
【００１７】
請求項２記載の発明は、コンピュータ上に表現された３次元空間内の物体表面を平面上に展開する装置であって、前記３次元空間内の物体表面を表現する入力データから前記物体表面を構成する多角形の情報を抽出する手段と、抽出された各多角形に関して、当該多角形と頂点を共有する周囲多角形を抽出する手段と、抽出された当該多角形と前記周囲多角形との間で共有されるべき頂点間の距離が最小になるという条件に従って、前記物体表面を構成する多角形の位置を決定する手段と、共有されるべき頂点に対応したすべての頂点の座標を代表する位置を求め、その代表する位置を前記共有されるべき頂点の座標に設定する手段と、を有する。
【００１８】
請求項２記載の発明によれば、隣接する多角形間の隙間や重なり合いが無くなるように多角形の位置と形状が決められ、３次元空間内の物体表面は２次元平面上に隙間や重なり合い無く展開される。また、測地線を計算する手間が省略される。
【００１９】
請求項３記載の発明は、コンピュータ上に表現された３次元空間内の物体表面を平面上に展開する装置であって、
前記３次元空間内の物体表面の多角形を表現する入力データを受け取り、前記入力データから前記多角形の情報を抽出する多角形スキャン部と、
前記多角形スキャン部に接続され、前記多角形スキャン部で抽出された前記多角形に対して、当該多角形の周囲にある周囲多角形の情報を抽出する周囲多角形抽出部と、
前記多角形スキャン部で抽出された前記多角形の情報及び前記周囲多角形抽出部で抽出された前記周囲多角形の情報に基づいて、前記平面上での各多角形の位置に関する係数を含む一次方程式を作成する一次方程式作成部と、
前記一次方程式作成部に接続され、前記一次方程式を解くことにより、前記各多角形の位置を算出する多角形位置演算部と、
前記多角形位置演算部に接続され、前記多角形位置演算部で算出された前記各多角形の位置に基づいて、前記各多角形に属する頂点の前記平面上での座標を計算する並べ合わせ部と、
前記並べ合わせ部で計算された前記各多角形の頂点を、隣接する多角形間の隙間や重なり合いが無くなるように移動させることにより前記多角形の形状を補正し、最終的な多角形の情報である出力データを出力する多角形形状補正部と、
を有する。
【００２０】
請求項３記載の発明によれば、３次元空間内の物体表面を２次元平面に展開する際に、測地線の距離を求める計算が不要になるので計算量を削減することができる。
【００２１】
請求項４記載の発明は、コンピュータ上に表現された３次元空間内の物体表面を平面上に展開する物体表面平坦化装置であって、
入力データから多角形の形状情報を抽出する手段と、
前記多角形と頂点を共有する周囲多角形の形状情報を抽出する手段と、
前記多角形の形状情報及び前記周囲多角形の形状情報から、多角形毎に各多角形の位置に関する一次式の係数を取得する手段と、
前記多角形毎の前記一次式からなる複数の一次式を解くことにより、前記各多角形の位置を算出する手段と、
前記位置を算出された各多角形を並べる手段と、
を有する。
【００２２】
請求項４記載の発明によれば、入力多角形の位置は一次方程式を解くことにより決定し、入力多角形を２次元平面に並べることができる。この構成により、入力画像から測地線等を求めることなく、歪みの小さな展開図を作成することができる。
【００２３】
請求項５に係る発明によれば、前記物体表面平坦化装置は、前記並べられた各多角形の形状を補正する手段を更に有する。したがって、請求項５に係る発明によれば、並べられた多角形間に重なりや隙間がある場合に、その多角形の形を補正して、重なりや隙間のない平面を作ることが可能になる。
【００２４】
請求項６記載の発明によれば、前記入力データは３次元空間内の物体表面を構成する多角形の形状を表すデータを含み、前記多角形の形状を表すデータは、共通の始点から多角形の各頂点への２次元ベクトルであり、前記共通の始点へのベクトルは多角形の位置を表すベクトルである。多角形の形状を表すデータを、共通の始点を表すベクトルと、共通の始点から頂点への２次元ベクトルとによって表現することにより、多角形の位置と形状を別々に操作できるようになる。
【００２５】
請求項７に係る発明によれば、前記入力データは、３次元空間内の物体表面を構成する多角形の相対位置を表すデータを更に含み、前記相対位置を表すデータは、３次元空間内の物体表面を構成する多角形の各頂点に対し、各頂点をどの多角形が共有しているかを示す情報、及び／又は、３次元空間内の物体表面を構成する多角形にはどの頂点が存在しているかを示す情報である。入力データとして、各多角形の頂点のインデクス情報、又は、各頂点の周囲多角形のインデクス情報を持つことによって周囲多角形を効率的に抽出できるようになる。
【００２６】
請求項８に係る発明によれば、前記各多角形の位置に関する一次式の係数を取得する手段は、ある中心多角形と、その多角形と頂点を共有する周囲多角形との間で、同一点にあるべき頂点間の距離の２乗和が最小になるような、中心多角形と周囲多角形との相対位置を示す一次式の係数を取得することを特徴とする。これにより、頂点間距離が最小となるように多角形の位置を決定することができる。
【００２７】
請求項９に係る発明によれば、前記各多角形の位置を算出する手段は、最小２乗法を用いて前記連立した一次式を解くことにより各多角形の位置を算出する。これにより、多角形の位置は、連立一次方程式を最小２乗法で解くという公知の手法を用いて計算することができる。
【００２８】
請求項１０に係る発明によれば、前記入力データに含まれる多角形は縦横に整列して配置された四角形であり、前記多角形の形状情報を抽出する手段は、整列して配置された四角形の配置場所に対応した多角形インデクスから前記３次元空間内の物体表面を構成する多角形の相対位置を表すデータを決定し、前記一次式の係数を取得する手段は、中心多角形と周囲多角形の相対位置から前記一次式の係数を決定する。このように入力多角形が縦横に整列して配置された四角形である場合には、入力データの情報量と、展開処理のための計算量を削減することができる。
【００２９】
請求項１１に係る発明によれば、前記共通の始点は多角形の所定の頂点に固定されている。これにより、多角形の形状を表すデータから、共通の始点として射使用される頂点に対応した２次元ベクトルのデータを省略することが可能になる。即ち、多角形の一つの頂点に対する位置ベクトルをその多角形の位置ベクトルとすることにより、他の頂点の位置ベクトルは、その頂点から他の頂点への相対ベクトルを用いて表わすことができる。したがって、この構成を採用することにより、入力データとして保持することが必要な多角形の形状データの一つを省略することができる。
【００３０】
請求項１２に係る発明によれば、物体表面平坦化装置は、多角形の頂点以外の辺上に他の多角形の頂点が存在している場合に、前記多角形の辺上にある前記頂点から線分又は半直線を引くことにより、前記頂点と別の辺との交点を新たな頂点とする多角形分割手段を更に具備することを特徴とする。多角形分割手段を用いることにより、入力多角形の辺上に頂点がある場合でも、入力多角形の辺上に頂点がない場合と同様に物体表面を平面に展開できるようになる。
【００３１】
請求項１３に係る発明は、３次元空間内の物体表面を表現する入力データから前記物体表面を構成する多角形の情報を抽出するステップと、抽出された各多角形に関して、当該多角形と頂点を共有する周囲多角形を抽出するステップと、抽出された当該多角形と前記周囲多角形との間で共有されるべき頂点間の距離が最小になるという条件に従って、前記物体表面を構成する多角形の位置を決定するステップと、共有されるべき頂点に対応したすべての頂点の座標を代表する位置を求め、その代表する位置を前記共有されるべき頂点の座標に設定するステップと、をコンピュータに実行させ、コンピュータ上に表現された３次元空間内の物体表面を平面上に展開するプログラムである。これにより、本発明の様々な機能をコンピュータに実現させるためのプログラムを提供することができる。このプログラムは、通信回線や記録媒体を用いてコンピュータに提供することが可能である。
【００３２】
更に請求項１４に係る発明によれば、上記プログラムを記録したコンピュータ読み取り可能な記録媒体が提供される。
【発明の効果】
【００３３】
本発明によれば、３次元空間内の物体表面が複数の多面体で構成、若しくは、近似されている場合に、その物体表面を多角形の集合として２次元平面上に展開不可能な表面であっても、その多角形を２次元平面上でできるだけ歪みが小さくなるように並べることができる。
【００３４】
また、本発明によれば、３次元空間内の物体表面を２次元平面に展開する際に、従来技術において歪みの小さな展開図を作成するために使用されていた測地線の距離を求める計算が不要になるので、計算量を削減することができる。
【発明を実施するための最良の形態】
【００３５】
以下、本発明を実施するための最良の形態を図面と共に詳細に説明する。
【００３６】
最初に、図１を用いて本発明の原理を説明する。図１は隣接する多角形の頂点の状態を説明する図であり、同図の（Ａ）には隣接する多角形の頂点が両方の多角形に共有されている状態が示され、同図の（Ｂ）には、隣接する多角形の頂点が２点に分割されている状態が示されている。
【００３７】
図１の（Ａ）に示すように、３次元曲面上で隣接する多角形は、頂点を共有している。例えば、頂点１０１は多角形１０２及び多角形１０３に共有されている。これらの３次元曲面上の多角形を２次元平面に展開して並べたときも、この頂点１０１は隣接する多角形１０２と多角形１０３の間で共有されるのが望ましい。しかしながら、展開不可能な表面の場合、隣接する多角形を隙間無く、かつ、重複無く（重なり合うことなく）並べることが不可能な場合がある。その場合、図１の（Ｂ）に示されるように、この共有されるべき頂点１０１の位置が頂点１０１’と頂点１０１”の二つに分割されてしまう。本発明は、これらの分割された二つの頂点間の距離をできるだけ小さくするように多角形を並べることによって、歪みの小さな展開画像を作成する。
【００３８】
このように、本発明においては、測地線を求めたり、頂点を他の可展開面に投影したりすることなく、出力多角形を直接２次元平面に展開できるので、３次元曲面を展開した平面に直接平面テクスチャ画像を生成することができる。
【００３９】
図２は本発明の一実施例による物体表面平坦化方法のフローチャートである。この物体表面平坦化方法は、この方法の各ステップをコンピュータに実現させるためのプログラムを、コンピュータに接続されるハードディスク装置や、ＣＤ−ＲＯＭ、ＤＶＤ又はフレキシブルディスクなどの可搬型記憶媒体に格納し、本発明を実施する際にコンピュータにインストールし、又は、通信回線からコンピュータにダウンロードし、インストールして、コンピュータのＣＰＵ等でこのプログラムを実行することによって容易に実現される。
【００４０】
本発明の実施例においては、３次元空間内の物体表面、即ち、３次元曲面は、予め、例えば、サーフェイスモデル又はポリゴングラフィックスなどの３次元物体のモデリング手法を用いて多面体の集合で形成・表現されている。各多面体の形状は多面体を表現しているデータから知ることができる。
【００４１】
本発明の一実施例による物体表面平坦化方法を実現するコンピュータは、最初に、このような３次元曲面を表現する入力データから、前記３次元表面を構成する多角形の情報を抽出する（ステップ２０１）。多角形の情報には、多角形の位置に関する情報及び多角形の形状に関する情報が含まれる。
【００４２】
次に、このコンピュータは、ステップ２０１で抽出された各多角形に関して、当該多角形と頂点を共有する多角形、即ち、周囲多角形を抽出する（ステップ２０２）。
【００４３】
次に、このコンピュータは、ステップ２０１で抽出されたすべての多角形に関して、ステップ２０２で抽出された当該多角形と当該多角形に対応する周囲多角形との間で共有されるべき頂点間の距離が最小になるという条件に従って、すべての多角形の位置を決定する（ステップ２０３）。多角形の形状に関する情報は与えられているので、多角形の位置が決定すると、各多角形に属する頂点の座標を決めることができる。
【００４４】
この段階では、隣接する多角形間で本来共有されるべき頂点の座標は、各多角形毎にその多角形の位置に応じて決定されているので、本来一つであるべき頂点に対して、その頂点を共有する多角形の個数分の座標が与えられている。そこで、このコンピュータは、本来同一である頂点に対応したすべての頂点の座標を代表する位置、例えば、すべての頂点の座標の重心位置を求め、その重心位置を本来同一である頂点の座標に設定する（ステップ２０４）。これにより、隣接する多角形間の隙間や重なり合いが無くなるように多角形の形状が補正される。
【００４５】
以上の処理により、３次元空間内の物体表面は２次元平面上に隙間や重なり合い無く展開される。
【実施例１】
【００４６】
本発明の実施例１による物体表面平坦化装置を説明する。図３は本発明の実施例１による物体表面平坦化装置３００の構成図である。物体表面平坦化装置３００は、３次元形状モデリング装置（図示せず）などの外部装置から、３次元空間内の物体表面の多角形を表現する入力データ３０１を受け取り、入力データから多角形の情報を抽出する多角形スキャン部３０２を含む。多角形スキャン部３０２に接続された周囲多角形抽出部３０３は、多角形スキャン部３０２で抽出された多角形に対して、その多角形の周囲にある多角形、即ち、周囲多角形の情報を抽出する。
【００４７】
物体表面平坦化装置３００は、多角形スキャン部３０２及び周囲多角形抽出部３０３で抽出された多角形の情報及び周囲多角形の情報に基づいて、各多角形の位置に関する係数を含む一次方程式を作成する一次方程式作成部３０４を更に有する。一次方程式作成部３０４の後に接続された多角形位置演算部３０５は、この一次方程式を解くことにより、各多角形の位置を算出する。更に、多角形位置演算部３０５の後に接続された並べ合わせ部３０６は、多角形位置演算部３０５で算出された多角形の位置に基づいて、各多角形の形状を保存したまま多角形を平行移動し、各多角形を２次元平面上に配置する。この配置処理は、実際に多角形を平面に貼り付けるのではなく、各多角形に属する頂点の２次元平面上での座標を計算することによって実現される。
【００４８】
物体表面平坦化装置３００は、並べ合わせ部３０６で配置された多角形の間の隙間や重なり合いが無くなるように、多角形の頂点を移動させることにより多角形の形状を補正し、最終的な多角形の情報である出力データ３０８を出力する多角形形状補正部３０７を更に有する。
【００４９】
次に、物体表面平坦化装置３００の各部の動作を詳しく述べる。
【００５０】
最初に、入力データ３０１について説明する。入力データ３０１は、３次元空間内の物体表面を構成する各多角形の形状及び相対位置情報を表すデータである。ここで、物体表面を構成する各多角形を示すインデクスをiとする。総数P個の多角形がある場合、例えば、その多角形に1からPまでの番号をインデクスとして付与することができる。また、物体表面の各頂点を示すインデクスをkとする。総数Q個の頂点がある場合、例えば、各頂点に1からQまでの番号をインデクスとして付与することができる。通常、各頂点は、図１の（Ａ）に示したように複数の多角形によって共有されている。
【００５１】
３次元空間内の物体表面の多角形表現は、頂点の存在条件によって二つのカテゴリーに分類できる。図４は、物体表面の多角形の頂点の存在条件を説明する図である。図４の（Ａ）は、ある多角形を形成する辺上に存在する他の多角形の頂点は、そのある多角形のいずれかの頂点を一致する様子を示している。一方、図４の（Ｂ）は、ある多角形を形成する辺上には、そのある多角形のいずれの頂点とも一致しない他の多角形の頂点が存在する様子を示している。
【００５２】
本実施例１では、全ての多角形の辺上で、その多角形の頂点以外の場所には他の多角形の頂点が存在しない、という図４の（Ａ）のタイプの多角形表現を使用する。
【００５３】
上述の通り、本実施例１では、最初に並べ合わせ部３０６で各多角形の形状を保存したまま、多角形を平行移動し、２次元平面に並べる。次に、多角形形状補正部３０７は、２次元平面に並べられた多角形の形状の補正を行う。即ち、多角形形状補正部３０７の前までは、入力された多角形の形状は保存される。そのため、多角形の形状を表す部分と多角形の位置を表す部分を別々に取り扱うことができるように、多角形の情報は、形状情報と位置情報とに分割して保持することが望ましい。
【００５４】
図５は多角形の形状情報と位置情報の説明図である。多角形iは、N個の頂点k1,k2,...,kNを持つものとする。このとき、本実施例１では、多角形iの形状を、N個の２次元ベクトルaik（k=k1,k2,...,kN）を用いて表す。さらに、多角形iの位置は、２次元ベクトルviを用いて表す。これら２種類のベクトルを用いることにより、図５に示されるように、２次元平面上で多角形iを並べたときの多角形iの各頂点の座標は、
vi＋aik（k=k1,k2,...,kN）
で表すことができる。
【００５５】
多角形の各頂点の座標がこのように指定される場合、多角形の形状を保存しながら多角形の位置だけを平行移動させる場合には、多角形iの形状を示すベクトルaikは変化させないで、多角形iの位置を示すベクトルviのみを変化させれば良いことになる。入力データ３０１は、このようにして定めた多角形形状に関するデータ、即ち、
aik
を持つ。
【００５６】
上記の説明では、多角形iの位置を示すベクトルviの終点位置は任意に設定されているが、この終点位置と多角形iの頂点の座標との間にある条件を導入することにより、入力データの量を削減することが可能である。より詳しく説明すると、図５に示されるように、各頂点の位置は、ベクトルviの終点から、各ベクトルaikを伸ばすことによって得られる。ベクトルviの終点と、多角形iの位置関係は任意であるため、多角形iとベクトルviの終点の位置関係を予め固定しておけば、aik（k=k1,k2,...,kN）のうち、一つのベクトルを入力データ３０１として持つことを省略することが可能である。例えば、常に、aik1=0  としても上記の議論は成り立つ。このようにすることで、aik1を入力データとして保持する必要が無くなる。これは一つの例であり、他の例として、例えば、多角形iの重心をベクトルviの終点とすることによっても、一つのベクトルaikを入力データ３０１から省くことができる。
【００５７】
さらに、３次元曲面を表現する入力データ３０１内には、多角形と頂点の関係を表すデータも含まれている。この多角形と頂点の関係を表すデータは、周囲多角形抽出部３０３において使用される多角形の相対位置情報を表している。この相対位置情報は、以下に示す(情報１)及び／又は(情報２)の形で与えられる。
【００５８】
（情報１）頂点を共有する多角形インデクスのデータ。例えば、頂点を示すインデクスをkとし、多角形を示すインデクスをiとするとき、頂点kを共有する多角形のインデクスiの集合Fkの内容がこの相対位置情報である。
【００５９】
（情報２）多角形毎に、その多角形と頂点を共有する多角形のインデクスのデータ。例えば、頂点を示すインデクスをkとし、多角形を示すインデクスをiとするとき、多角形iの頂点インデクスkの集合Giの内容がこの相対位置情報である。
【００６０】
上記情報１と情報２は相互に変換が可能であるので、どちらか一方を保持していれば良い。しかし、相互に変換する際の計算量が問題となる場合には、情報１と情報２の両方を保持していても良い。
【００６１】
或いは、３次元曲面上に多角形が規則的に並んでいて、多角形インデクスから、多角形の相対位置情報、すなわち、上記の情報１又は情報２が容易に求められる場合には、上記相対位置情報は、予め入力データ３０１に含まれる必要は無い。
【００６２】
入力データ３０１の説明に続き、多角形スキャン部３０２及び周囲多角形抽出部３０３の動作を説明する。多角形スキャン部３０２では、入力された多角形を一つ一つ全て抽出する。より具体的には、入力データ３０１の中から、多角形インデクスiと、多角形iのN個の頂点の座標を抽出することにより、多角形を抽出することができる。多角形スキャン部３０２で多角形iが抽出されたとき、周囲多角形抽出部３０３では、多角形iと頂点を共有する多角形を全て抽出する。より具体的には、入力データ３０１中に情報１が与えられた場合、多角形iに属するすべての頂点kについての集合Fkの和集合を求めればよい。入力データ３０１中に情報２が与えられた場合、多角形iについての集合Giに属する要素と一致する要素を含む頂点インデクス集合をもつ多角形インデクスの集合を求めればよい。
【００６３】
次に一次方程式作成部３０４の動作を説明する。実施例１においては、多角形を２次元平面上に並べたとき、隣接する多角形において共有されるべき頂点間の距離が最も小さくなるように、全ての多角形を並べる。ここでは、所定の距離関数を定義し、この距離関数が最小になるような多角形位置ベクトルviを求めることによって、多角形位置を決定する。
【００６４】
まず、既に述べたように、各頂点を示すインデクスをkとする。また、各多角形を示すインデクスをiとする。さらに、頂点kを共有する多角形のインデクスの集合をFkとする。例えば、図６に示すように、３次元空間内の物体表面において、頂点kの周りに多角形1、2、3、4、5が存在し、かつ、これらの多角形の他には頂点kを持つ多角形がないとする。このとき、
Fk = {1,2,3,4,5}
と表すことができる。一方、多角形iの頂点インデクスの集合をGiとする。例えば、図７に示すように、多角形iが頂点1、2、3、4、5、6を持ち、その他の頂点は持っていないとする。このとき、
Gi = {1,2,3,4,5,6}
と表すことができる。
【００６５】
このような状況において、ある頂点kに関して所定の距離関数が最小になるような多角形位置を決定することを考える。頂点kを共有する多角形の集合はFkである。Fkの各要素である多角形インデクスをiとする。即ち、
i∈Fk
とする。３次元物体表面を２次元平面に展開したときの多角形iの頂点kの位置を示す位置ベクトルは、
vi＋aik
である。Fkの要素である全てのi(i∈Fk)で、上記の位置ベクトルの大きさは、理想的には同じになる。しかし、展開不可能な物体表面では、隣接する多角形の頂点が一致しないので、位置ベクトルの大きさに誤差が生じる。即ち、多角形i(i∈Fk)の頂点kの位置ベクトルvi＋aikと、多角形j(j∈Fk, j≠i)の頂点kの位置ベクトルvj＋ajkは、異なる場合がある。ここで、頂点kに関するこの誤差の２乗を、頂点kに関する所定の距離関数Ekとする。Ekは以下のように表すことができる。
【００６６】
【数１】
2005190019.tif 000003
上記(1)式において、iとｊは対称である。即ち、iとjを交換しても同じ式が成り立つ。よって、
【００６７】
【数２】
2005190019.tif 000004
とすることができる。(1)式と(2)式の両辺を加算すると次式が得られる。
【００６８】
【数３】
2005190019.tif 000005
さらに、i=jの時には、
【００６９】
【数４】
2005190019.tif 000006
であるので、
【００７０】
【数５】
2005190019.tif 000007
である。(3)式の両辺に(4)式の両辺をさらに加算すると、Ekは、以下のように書くこともできる。
【００７１】
【数６】
2005190019.tif 000008
次に、全頂点に亘ってEkを加算することにより、全体の距離関数Eが得られる。
【００７２】
【数７】
2005190019.tif 000009
ここで、Eは、viの２次形式であり、２次の項の係数は正であるので、全ての多角形インデクスiに関して、
【００７３】
【数８】
2005190019.tif 000010
となるviが、Eを最小化する多角形の位置ベクトルとなる。そこで、i=mの時の最小化条件を求める。
【００７４】
【数９】
2005190019.tif 000011
よって、i=mの時の最小化条件は、
【００７５】
【数１０】
2005190019.tif 000012
として表される。(5)式を変形すると、以下のようになる。
【００７６】
【数１１】
2005190019.tif 000013
(8)式は、vi(i=m,j、ただし、j∈Fkかつk∈Gm)の一次式である。一次方程式作成部３０４では、多角形スキャン部３０２で抽出された多角形mおよび、周囲多角形抽出部３０３で抽出された多角形mの周囲の多角形j(j∈Fkかつk∈Gm)の形状情報から、一次方程式(8)の係数を作成する。
【００７７】
ここで、上記で示される形状情報とは、amk(k∈Gm)、及び、ajk(j∈Fkかつk∈Gm)のことである。また、上記(8)式は、２次元ベクトルの式ではあるが、2次元ベクトルの各要素ごとに演算をすることによって、通常のスカラー値と同じように方程式を作ることができる。
【００７８】
以上の処理によって、多角形mに関する一次方程式を作ることができた。
【００７９】
多角形スキャン部３０２では、全ての多角形をスキャンする。その結果、一次方程式作成部３０４では、全ての多角形iに関する一次方程式を作ることができる。ここで、多角形iの位置、即ち、求めようとしている未知情報は、viである。多角形の数をNとすると、未知数は、v1, v2, ..., vN のN個である。尚、実際には、viは２次元ベクトルであるので、未知スカラー値の個数は2×N個であるが、ここではベクトルを一つの数として扱い、未知数の個数をN個として表記した。
【００８０】
また、一つの多角形mに対して、式(8)に示される一次方程式を作ることができる。多角形数はNであるので、N個の一次方程式を作成することができる。この連立一次方程式は、次式(9)のように行列を用いて表すことができる。
Ax=b  (9)
Aは係数行列であり、(8)式の
【００８１】
【数１２】
2005190019.tif 000014
或いは、
【００８２】
【数１３】
2005190019.tif 000015
から計算することができる。AはN×Nの行列である。xはN行1列の未知ベクトルであり、(v1(u), v2(u), ..., vN(u))T である。ここで、vi(u)はベクトルviの第u成分を示す(u=1,2)。さらに、bは、以下に示すN行1列の既知ベクトルである。
【００８３】
【数１４】
2005190019.tif 000016
ここで、(9)式のAは、実際には特異行列であり、逆行列を持たない。そのため、このままでは(9)式を解くことができない。これは、(8)式、或いは、(9)式が多角形の位置ベクトルvi各々の相対値のみを規定しているためである。(9)式を解くためには、何らかの方法によって、絶対的な位置を指定する必要がある。例えば、インデクスが1の多角形の位置ベクトルの値を、v1=0とすることによって、(9)式を解くことが可能となる。このとき、(9)式の係数行列Aの第1列の数値は任意となる。そこで、行列Aから第1列を抜いたN行(N-1)列の行列をBとする。v1=0 としたとき、(9)式は、
Bx=b  (10)
となる。以上の処理によって、多角形の位置を決定するための一次方程式を作成することができる。
【００８４】
次に、多角形位置演算部３０５の動作を説明する。多角形位置演算部３０５は(10)式の解を求める。多角形位置演算部３０５は、未知数がN-1で式の数がNの連立一次方程式(10)を解く。方程式(10)は、最小２乗法を用いて解くことができる。例えば、
x=(BTB)-1BTb
として解くことができる。これにより、N行1列の未知ベクトルである
x=(v1(u), v2(u), ..., vN(u))T
が決まる。上述のように、vi(u)は、多角形インデクスiの位置を表すベクトルviの第u成分を示す(u=1,2)。
【００８５】
次に並べ合わせ部３０６の動作を説明する。並べ合わせ部３０６は、多角形位置演算部３０５で求められた多角形位置viと、多角形の形状情報として既知である多角形形状aik、及び、多角形の相対位置情報に基づいて多角形の並べ合わせを行う。ここで、多角形相対位置情報として、既に述べた情報２を保持しているものとする。即ち、各多角形インデクスiに対して、多角形iの頂点インデクスの集合Giが分かっているものとする。情報１と情報２は相互に変換可能であるため、情報１が分かっている場合でも情報１を情報２に変換することによって情報２を保持することができる。このような条件の下で、各多角形の各頂点の座標は、(i=1,2,...,N)として、
vi＋aik  (i=1,2,...,N、かつ、k∈Gi)
として求めることができる。
【００８６】
最後に、多角形形状補正部３０７の動作及び出力データ３０８について説明する。ある頂点kは、上述の多角形インデクスi∈Fkの関係を満たす多角形によって共有されるべきである。即ち、ある頂点kの座標は、理想的には、この頂点kを含むすべての多角形に亘って同一である。しかし、並べ合わせ部３０６で多角形を並べた結果として得られる頂点kの座標は、この頂点kを含む多角形の間で異なる場合が存在する。この状況では、並べ合わせた多角形の間に隙間が存在したり、多角形同士が重なり合っている。このため、本発明の実施例１では、その隙間や重なり合いを無くすように多角形形状を補正する。多角形形状の補正は、実際には頂点座標の補正によって実現される。具体的には、各多角形の頂点kの座標を、各多角形の頂点kの重心座標で置き換える。即ち、頂点kの座標ベクトルxkは、多角形インデクスi∈Fkの関係を満たす各多角形に属する頂点kの重心として、次式(11)のように決定できる。
【００８７】
【数１５】
2005190019.tif 000017
ここで、
【００８８】
【数１６】
2005190019.tif 000018
は、集合Fkの要素数を示す。
【００８９】
本発明の実施例１による出力データ３０８は、(11)式で表された頂点座標xkである。或いは、出力データ３０８として、頂点座標ではなくて、多角形位置viと、補正された多角形形状a’ikを採用してもよい。この場合、多角形形状補正部３０７では、補正された多角形形状a’ikの計算を次式
a’ik = xk - vi
に従って行う。
【００９０】
以上の処理によって、本発明の実施例１による物体表面平坦化装置３００は、３次元空間内の物体表面を平面上に、隙間と重なり合いを生ずること無く展開することができる。
【００９１】
尚、以上で説明した実施例１は本発明を実施するための最良の形態の一つにすぎず、本発明はその趣旨を逸脱しない限り種々変形して実施可能である。
【実施例２】
【００９２】
上記実施例１による物体表面平坦化装置３００は、３次元空間内の物体表面が一般の多角形で構成されている場合に適用可能である。これに対して、３次元空間内の物体表面を構成する多角形の形状が限定されている場合には、物体表面平坦化装置の構成を簡単化することが可能である。そこで、本実施例２では、特に、物体表面が凸四角形で構成されている場合に関して説明を行う。本実施例２による物体表面平坦化装置の構成は、図３を参照して説明した本実施例１の物体表面平坦化装置３００の構成と同一又は類似しているので、便宜的に図３を参照して実施例２の物体表面平坦化装置を説明する。
【００９３】
また、本実施例２では、物体表面上の多角形が規則的に並び、多角形インデクスから、多角形の相対位置情報、即ち、実施例１で説明した情報１及び／又は情報２が容易に求められる場合を考える。
【００９４】
更に、本実施例２では、実施例１と同様に、全ての多角形の辺上で、その多角形の頂点以外の場所には他の多角形の頂点が存在しない場合を考える。
【００９５】
尚、本実施例２は、多角形iの頂点座標と、多角形iの位置ベクトルviの終点との位置関係を固定することによって、頂点の位置を表す一つのベクトルを入力データから省略している。
【００９６】
図８は、本発明の実施例２により物体表面を構成する多角形が規則的に並べられている様子を示す図である。同図に示されるように、物体表面を構成する多角形、本例では、特に、四角形が、２次元配列の行と列に対応するように、規則正しく並んでいる。図８の四角形内に書かれた数字はその四角形(多角形)のインデクスを示す。例えば、多角形1、2、3、4は第１行、多角形2、6、10、14は第２列などのように２次元配列へのマッピングが可能である。このような場合、多角形インデクスが分かれば、その多角形の周囲多角形のインデクスや、その多角形の頂点インデクスを簡単に求めることができる。したがって、実施例1で説明した相対位置情報、即ち、情報１及び／又は情報２を予め入力データとして準備しなくても構わない。もちろん、入力データが相対位置情報を含んでいてもよい。
【００９７】
これに対して、図９は、物体表面を構成する多角形が不規則的に並べられている様子を示す図である。図９に示されるような四角形の位置関係では、各四角形を２次元配列にマッピングすることができない。
【００９８】
このように、多角形が規則的に並べられているという状況では、周囲多角形抽出部３０３における周囲多角形の抽出が簡単化される。図１０は、本発明の実施例２により抽出された多角形及び周囲多角形を示す図である。図１０には、多角形スキャン部３０２で抽出された多角形インデクスが0、周囲多角形抽出部３０３で抽出された多角形インデクスが1〜8である様子が示されている。また、図１０に示すように、頂点インデクスは0〜3である。
【００９９】
本実施例２においても、一次方程式作成部３０４は、上述の式(8)を用いて一次方程式を作成する。このとき、式(8)において、
m=0,
Gm=G0={0,1,2,3}
F0={0,1,2,3}
F1={0,3,4,5}
F2={0,5 6 7}
F3={0,7,8,1}
となる。このとき(8)式は、
12v0-2v1-v2-2v3-v4-2v5-v6-2v7-v8 =
-3(a00+ a01+ a02+ a03)
+ a10+ a20+ a30
+ a31+ a41+ a51
+ a52+ a62+ a72
+ a73+ a83+ a13              (12)
となる。係数行列Aは、各行の所定の列(各ベクトルvi  に相当する位置)に、係数12,-2,あるいは、-1を入れ、その他の位置に0を入れることによって作ることができる。本実施例２においては、上記の係数12,-2、或いは、-1は、多角形に限らず同じであるため(どのベクトルの係数になるかは異なるが)、中心の多角形と周囲の多角形の相対位置さえわかれば、直ぐに選択することができるので、その都度計算を行う必要はない。例えば、中心多角形のインデクスがpであるときには、vp の係数は12である。中心多角形pの上下左右にある多角形qの場合、vq の係数は-2である。また、中心多角形pの斜め右上、斜め左上、斜め左下、斜め右下にある多角形rの場合、vr の係数は-1である。
【０１００】
更に、実施例２では、上述のように、ベクトルviの終点と各多角形の本来的には任意である位置関係を、例えば、各四角形iの左下の頂点の座標がベクトルviの終点に一致するように固定する。この場合、
a02 = a13 = a20 = a31 = 0
のように固定することができるので、入力データ３０１のデータ量を削減できる。このとき、式(12)は、
12v0-2v1-v2-2v3-v4-2v5-v6-2v7-v8 =
-3(a00+ a01+ a03)
+ a10+ a20
+ a41+ a51
+ a52+ a62+ a72
+ a73+ a83          (13)
となる。
【０１０１】
尚、３次元空間内の物体表面を表現する四角形が特に平行四辺形である場合には、四角形、即ち、この場合の平行四辺形の形状は二つのベクトルで表すことができるので、入力データ３０１のデータ量を更に削減することができる。
【０１０２】
実施例２による物体表面平坦化装置の他の部分は実施例１の物体表面平坦化装置とと同様に動作する。
【０１０３】
尚、以上で説明した実施例２は本発明を実施するための最良の形態の一つにすぎず、本発明はその趣旨を逸脱しない限り種々変形して実施可能である。
【実施例３】
【０１０４】
上述の実施例１及び実施例２では、３次元空間内の物体表面を記述するモデルにおいて、全ての多角形の辺上で、その多角形の頂点以外の場所には他の多角形の頂点が存在しない場合を考えていた。これに対して、実施例３では、ある多角形を形成する辺上には、そのある多角形のいずれの頂点とも一致しない他の多角形の頂点が存在する場合に、本発明に従って３次元空間内の物体表面を２次元平面に展開する。
【０１０５】
実施例３では、物体表面が一般の多角形で表現されている場合について説明する。図１１は、本発明の実施例３による物体表面の多角形表現の説明図である。図１１には、多角形1の辺STに、他の多角形2及び3に属する頂点Vが存在している様子が示されている。このような状況では、実施例１に関して説明した物体表面平坦化方式をそのまま適用することができない。しかし、ある多角形を形成する辺上に、そのある多角形のいずれの頂点とも一致しない他の多角形の頂点が存在する場合に、このある多角形の辺上の他の多角形の頂点の位置で、このある多角形を分割することによって、全ての多角形の辺上で、その多角形の頂点以外の場所には他の多角形の頂点が存在しないようにすることが可能である。全ての多角形の辺上で、その多角形の頂点以外の場所には他の多角形の頂点が存在しない場合には、実施例１及び実施例２で説明した方式を適用することが可能になる。
【０１０６】
そこで、本発明の実施例３による物体表面平坦化装置１２００は、図１２に示されるように多角形スキャン部３０２の前段に頂点存在条件変換部１２０１を有する。頂点存在条件変換部１２０２は、入力データ１２０１に対して頂点の存在条件を変換する処理を行う。物体表面平坦化装置１２００のその他の構成要素、即ち、多角形スキャン部３０２、周囲多角形抽出部３０３、一次方程式作成部３０４、多角形位置演算部３０５、並べ合わせ部３０６及び多角形形状補正部３０７は、図３を参照して説明した本発明の実施例１又は実施例２における各構成要素と同じである。図１１に示された例では、実施例３の頂点存在条件変換部１２０１は、多角形1を、頂点Vの位置を新たな頂点とする二つの多角形に分割する。これにより、頂点存在条件変換部１２０１から多角形スキャン部３０２へ供給されるデータは、図３の入力データ３０１と同様のデータに変換される。したがて、以降の処理では、実施例１又は２の手法を適用することができる。
【０１０７】
頂点存在条件変換部１２０１による多角形の分割には、以下の２種類の方法がある。
【０１０８】
第１の多角形分割処理は、頂点Vから、頂点S、T以外の一つの頂点に線を引くことによって多角形1を分割する。図１３は、この分割方法の説明図である。
【０１０９】
第２の多角形分割処理は、頂点Vから、半直線を多角形1の内部の方向に引く。このように直線を引くことにより、頂点Vは多角形1の辺上の点ではなくなくなる。さらに、第２の分割方法では、半直線の方向を、図１４に示されるように、多角形2と多角形3の間の線分の方向と一致させることによって妥当な分割を行うことができる。
【０１１０】
尚、以上で説明した実施例３は本発明を実施するための最良の形態の一つにすぎず、本発明はその趣旨を逸脱しない限り種々変形して実施可能である。
【図面の簡単な説明】
【０１１１】
【図１】隣接する多角形の頂点の状態を説明する図である。
【図２】本発明の一実施例による物体表面平坦化方法のフローチャートである。
【図３】本発明の実施例１による物体表面平坦化装置の構成図である。
【図４】物体表面の多角形の頂点の存在条件を説明する図である
【図５】多角形の形状情報と位置情報の説明図である。
【図６】本発明の実施例１による多角形インデクス集合Fkの説明図である。
【図７】本発明の実施例１による頂点インデクス集合Giの説明図である。
【図８】本発明の実施例２により物体表面を構成する多角形が規則的に並べられている様子を示す図である。
【図９】物体表面を構成する多角形が不規則的に並べられている様子を示す図である。
【図１０】本発明の実施例２により抽出された多角形及び周囲多角形を示す図である。
【図１１】本発明の実施例３による物体表面の多角形表現の説明図である。
【図１２】本発明の実施例３による物体表面平坦化装置の構成図である。
【図１３】本発明の実施例３による頂点条件変換部の第１の多角形分割処理の説明図である。
【図１４】本発明の実施例３による頂点条件変換部の第２の多角形分割処理の説明図である。
【符号の説明】
【０１１２】
３００  ・・・物体表面平坦化装置
３０１  ・・・入力データ
３０２  ・・・多角形スキャン部
３０３  ・・・周囲多角形抽出部
３０４  ・・・一次方程式作成部
３０５  ・・・多角形位置演算部
３０６  ・・・並べ合わせ部
３０７  ・・・多角形形状補正部
３０８  ・・・出力データ
【図１】
2005190019.tif 000019
【図２】
2005190019.tif 000020
【図３】
2005190019.tif 000021
【図４】
2005190019.tif 000022
【図５】
2005190019.tif 000023
【図６】
2005190019.tif 000024
【図７】
2005190019.tif 000025
【図８】
2005190019.tif 000026
【図９】
2005190019.tif 000027
【図１０】
2005190019.tif 000028
【図１１】
2005190019.tif 000029
【図１２】
2005190019.tif 000030
【図１３】
2005190019.tif 000031
【図１４】
2005190019.tif 000032