(57)【特許請求の範囲】
【請求項１】
ポリゴンモデルにおける２個以上の格子点を１個の格子点に集結させる対象となる複数の部分に対して当該集結によって生じる、実測された形状データで構成されるポリゴンモデルに対するデータ削減後のポリゴンモデルの誤差を評価する評価値をそれぞれ算出する工程と、これらの評価値に基づきデータ削減を行なうべき上記格子点の集結対象部分を判定する工程と、上記判定手段により決定された格子点の集結対象部分のデータ削減処理を行なう工程とを備え、上記格子点の集結対象部分の評価値を算出し、その評価値に基づき上記格子点の集結対象部分のデータ削減を繰り返し行なうことで上記ポリゴンモデルを構成する三次元形状データのデータ数を順次、削減する三次元形状データのデータ削減方法であって、上記格子点の集結処理が行なわれると、当該格子点の集結処理により影響を受けた格子点の集結対象部分のデータ削減処理を禁止する工程とを含むことを特徴とする三次元形状データのデータ削減方法。
【請求項２】
予め設定された所定の条件が満たされると、禁止された上記格子点の集結対象部分のデータ削減処理の禁止を解除することを特徴とする請求項１記載の三次元形状データのデータ削減方法。
【請求項３】
上記所定の条件は、上記評価値に基づくデータ削減可能な上記格子点の集結対象部分がなくなったことであることを特徴とする請求項２記載の三次元形状データのデータ削減方法。
【請求項４】
上記所定の条件は、データ削減処理が所定の回数繰り返されることであることを特徴とする請求項２記載の三次元形状データのデータ削減方法。
【請求項５】
ポリゴンモデルにおける２個以上の格子点を１個の格子点に集結させる対象となる複数の部分に対して当該集結によって生じる、実測された形状データで構成されるポリゴンモデルに対するデータ削減後のポリゴンモデルの誤差を評価する評価値をそれぞれ算出する評価値算出手段と、上記評価値に基づきデータ削減を行なうべき上記格子点の集結対象部分を判定する判定手段と、上記判定手段により決定された格子点の集結対象部分のデータ削減処理を行なうデータ削減手段とを備え、上記格子点の集結対象部分の評価値を算出し、その評価値に基づき上記格子点の集結対象部分のデータ削減を繰り返し行なうことで上記ポリゴンモデルを構成する三次元形状データのデータ数を削減する三次元形状データのデータ削減装置であって、上記格子点の集結対象部分のデータ削減処理が行なわれると、当該格子点の集結処理により影響を受けた格子点の集結対象部分のデータ削減処理を禁止する禁止手段を備えたことを特徴とする三次元形状データのデータ削減装置。
【請求項６】
上記禁止手段は、上記判定手段で上記格子点の集結処理により影響を受けた格子点の集結対象部分がデータ削減処理の対象外と判定されるように、当該格子点の集結対象部分の評価値を一時的に所定の値に変更するものであることを特徴とする請求項５記載の三次元形状データのデータ削減装置。
【請求項７】
請求項５又は６に記載の三次元形状データのデータ削減装置において、予め設定された所定の条件が満たされると、禁止された上記格子点の集結対象部分のデータ削減処理の禁止を解除する解除手段を更に備えたことを特徴とする三次元形状データのデータ削減装置。
【請求項８】
上記所定の条件は、上記評価値に基づくデータ削減可能な上記格子点の集結対象部分がなくなったことであることを特徴とする請求項７記載の三次元形状データのデータ削減装置。
【請求項９】
上記所定の条件は、データ削減処理が所定の回数繰り返されることであることを特徴とする請求項７記載の三次元形状データのデータ削減装置。
【請求項１０】
上記判定手段は、最小の評価値を算出する最小評価値算出手段と、上記最小の評価値を予め設定された所定の許容値と比較する比較手段とを備え、上記最小の評価値が上記許容値以下であるとき、当該最小の評価値を有する格子点の集結部分をデータ削減部分と判定するものであることを特徴とする請求項５〜７のいずれかに記載の三次元形状データのデータ削減装置。
【請求項１１】
上記格子点の集結対象は、三角形ポリゴンモデルのエッジであることを特徴とする請求項５〜１０のいずれかに記載の三次元形状データのデータ削減装置。
【請求項１２】
上記格子点の集結対象は、三角形ポリゴンモデルの面であることを特徴とする請求項５〜１０のいずれかに記載の三次元形状データのデータ削減装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ポリゴンモデルを構成する三次元形状データのデータ削減方法及びその方法を用いたデータ削減装置に関するものである。
【０００２】
【従来の技術】
例えば空間分解能の極めて高い三次元形状計測装置で得られる描画品質の高い計測データはデータ数が膨大であるため、必要以上の描画品質を備えている場合は、その後の処理において記憶装置への負担が大きく、処理速度も著しく低下するという問題が生じる。このため、計測データのデータ数を削減して上記問題をできる限り低減することが必要となる。
【０００３】
従来、三角形ポリゴンモデルにおいて、所望の許容誤差範囲内でモデルの近似化を図ることにより当該三角形ポリゴンモデルを構成する三次元形状データのデータ数を削減する方法が種々提案されている。
【０００４】
例えば論文「Surface  Simplification  Using  Quadric  Error  Metrics」（Michael  Garland  and  Paul  S．Heckbert．Carnegie Mellon University  Proceedings  of  SIGGRAPH  97．1997）には、三角形ポリゴンモデルのエッジ又は面を構成する２個以上の格子点（三次元形状データ）を１個の格子点（三次元形状データ）に集結することにより三角形ポリゴンモデルを構成する三次元形状データのデータ数を削減する方法として、エッジ収縮もしくは面収縮により集結される格子点とエッジ収縮もしくは面収縮により影響を受けた最初の三角形ポリゴンモデルを構成する各平面との距離の離れ具合をデータ削減処理における誤差として管理し、この誤差が所定の許容誤差範囲内であるエッジ収縮もしくは面収縮の処理のみを行うことで、所定の許容誤差範囲内でデータ数の削減を行う方法が示されている。
【０００５】
このようなポリゴンモデルのエッジもしくは面を収縮させる方法では、例えば１つのエッジを収縮させると、そのエッジ収縮により周辺のエッジ及び面の状態が変化するため、１本のエッジを収縮させる毎にエッジ収縮後のポリゴンモデルを構成する当該エッジ収縮により影響を受けたエッジについて再度、誤差が再計算された後、再計算後の誤差を用いて１本のエッジが決定され、そのエッジの収縮が行なわれる。そして、この処理を繰り返えすことにより所定の許容誤差範囲内で三次元形状データのデータ数が削減されるようになっている。
【０００６】
【発明が解決しようとする課題】
上記従来のエッジ収縮や面収縮のように収縮処理を行なう毎に収縮部分の周辺が影響を受けるデータ削減方法では、１のエッジ収縮もしくは面収縮を行なう毎に収縮後のポリゴンモデルを構成する当該エッジ収縮により影響を受けたエッジもしくは面について誤差を再計算する必要があるため、計算回数が多く、データ削減処理の速度が低下するという問題がある。
【０００７】
本発明は、上記課題に鑑みてなされたものであり、高速処理が可能な三次元形状データのデータ削減方法及びそのデータ削減方法を用いたデータ削減装置を提供するものである。
【０００８】
【課題を解決するための手段】
請求項１記載の発明は、ポリゴンモデルにおける２個以上の格子点を１個の格子点に集結させる対象となる複数の部分に対して当該集結によって生じる、実測された形状データで構成されるポリゴンモデルに対するデータ削減後のポリゴンモデルの誤差を評価する評価値をそれぞれ算出する工程と、これらの評価値に基づきデータ削減を行なうべき上記格子点の集結対象部分を判定する工程と、上記判定手段により決定された格子点の集結対象部分のデータ削減処理を行なう工程とを備え、上記格子点の集結対象部分の評価値を算出し、その評価値に基づき上記格子点の集結対象部分のデータ削減を繰り返し行なうことで上記ポリゴンモデルを構成する三次元形状データのデータ数を順次、削減する三次元形状データのデータ削減方法であって、上記格子点の集結処理が行なわれると、当該格子点の集結処理により影響を受けた格子点の集結対象部分のデータ削減処理を禁止する工程とを含むものである。
【０００９】
また、請求項５記載の発明は、ポリゴンモデルにおける２個以上の格子点を１個の格子点に集結させる対象となる複数の部分に対して当該集結によって生じる、実測された形状データで構成されるポリゴンモデルに対するデータ削減後のポリゴンモデルの誤差を評価する評価値をそれぞれ算出する評価値算出手段と、上記評価値に基づきデータ削減を行なうべき上記格子点の集結対象部分を判定する判定手段と、上記判定手段により決定された格子点の集結対象部分のデータ削減処理を行なうデータ削減手段とを備え、上記格子点の集結対象部分の評価値を算出し、その評価値に基づき上記格子点の集結対象部分のデータ削減を繰り返し行なうことで上記ポリゴンモデルを構成する三次元形状データのデータ数を削減する三次元形状データのデータ削減装置であって、上記格子点の集結対象部分のデータ削減処理が行なわれると、当該格子点の集結処理により影響を受けた格子点の集結対象部分のデータ削減処理を禁止する禁止手段を備えたものである。
【００１０】
上記データ削減方法もしくはデータ削減装置によれば、ポリゴンモデルにおける２個以上の格子点を１個の格子点に集結させる対象となる複数の部分に対して当該集結によって生じる誤差を評価する評価値がそれぞれ算出され、これらの評価値に基づき１の格子点の集結対象部分のデータ削減処理が行なわれる。そして、この処理が繰り返されることによりポリゴンモデルを構成する三次元形状データのデータ数が順次、削減される。
【００１１】
この場合、データ削減処理が行なわれると、そのデータ削減処理により影響を受けた格子点の集結対象部分はその後のデータ削減処理が禁止され、影響を受けなかった格子点の集結対象部分について既に算出された評価値に基づき次のデータ削減が行なわれる。データ削減処理により影響を受けた格子点の集結部分について繰り返し評価値の再計算を行なわないので、この分、計算回数が低減される。
【００１２】
なお、予め設定された所定の条件が満たされると、禁止された上記格子点の集結対象部分のデータ削減処理の禁止を解除するようにするとよい（請求項２，７）。例えば上記評価値に基づくデータ削減可能な上記格子点の集結対象部分がなくなったときやデータ削減処理が所定の回数繰り返されたとき、禁止された上記格子点の集結対象部分のデータ削減処理の禁止を解除するとよい（請求項３，４，８，９）。
【００１３】
この構成によれば、例えば評価値に基づくデータ削減可能な上記格子点の集結対象部分がなくなったときやデータ削減処理が所定の回数繰り返されたとき等の所定の条件が満たされると、禁止された格子点の集結対象部分のデータ削減処理の禁止が解除される。
【００１４】
従って、例えば格子点の集結対象部分がなくなったときを所定の条件とする場合、エッジ収縮を行なう毎に影響を受けた格子点の集結対象部分が次のエッジ収縮対象から除外され、格子点の集結対象部分がなくなると、全ての格子点の集結対象部分について評価値が再計算され、これらの評価値に基づき１の格子点の集結対象部分のデータ削減処理が行なわれる。そして、この処理が繰り返されることによりポリゴンモデルを構成する三次元形状データのデータ数が順次、削減される。
【００１５】
また、請求項６記載の発明は、請求項５記載の三次元形状データのデータ削減装置において、上記禁止手段は、上記判定手段で上記格子点の集結処理により影響を受けた格子点の集結対象部分がデータ削減処理の対象外と判定されるように、当該格子点の集結対象部分の評価値を一時的に所定の値に変更するものである。
【００１６】
上記構成によれば、エッジ収縮処理が行なわれると、当該エッジ収縮により影響を受けた格子点の集結対象部分の評価値が所定の値に置換される。この後、全ての評価値に基づいてエッジ収縮処理の対象が決定される場合、エッジ収縮により影響を受けた格子点の集結対象部分はデータ削減処理の対象外と判定されるため、実質的にエッジ収縮処理が禁止される。
【００１７】
請求項１０記載の発明は、請求項５〜７のいずれかに記載の三次元形状データのデータ削減装置において、上記判定手段は、最小の評価値を算出する最小評価値算出手段と、上記最小の評価値を予め設定された所定の許容値と比較する比較手段とを備え、上記最小の評価値が上記許容値以下であるとき、当該最小の評価値を有する格子点の集結部分をデータ削減部分と判定するものである。
【００１８】
上記構成によれば、格子点の集結対象部分について算出された評価値の中から最小値が算出され、この最小値が所定の許容値以下であれば、当該最小評価値を有する格子点の結合対象部分のデータ削減処理が行なわれる。
【００１９】
なお、上記三次元形状データのデータ削減装置において、上記格子点の集結対象は、三角形ポリゴンモデルのエッジもしくは面にするとよい（請求項１１，１２）。
【００２０】
【発明の実施の形態】
図１は、本発明に係るデータ削減方法を適用した三次元形状計測データの処理システムのブロック構成図である。
【００２１】
同図に示す三次元形状計測データの処理システム（以下、形状データ処理システムという。）は、被測定物Ｇの三次元形状データを計測する三次元形状計測装置１、三次元形状計測装置１で計測された三次元形状データを記憶する外部記憶装置２、三次元形状計測装置１で計測された三次元形状データを本発明に係るデータ削減方法を用いて削減し、所定のデータ処理を行う形状データ処理装置３、形状データ処理装置３で処理された三次元形状データを記憶する外部記憶装置４、データ削減後の三次元形状データを用いて、例えばポリゴンモデル等の測定物Ｇの三次元形状画像を表示する表示装置５及び形状データ処理装置３で処理された三次元形状データが利用されるＣＡＤ／ＣＡＭ（computer aided design and computer aided manufacturing）等の外部処理装置６から構成されている。
【００２２】
三次元形状計測装置１は共役オートフォーカスシステムを用いて測定対象物Ｇの表面形状の計測を行うものである。三次元形状計測装置１は、図２に示すように、照明光を発生する照明部１０１、照明部１０１からの照明光を測定対象物Ｇに照射するとともに、測定対象物Ｇで反射した照明光を受光部１０３に導く共焦点型光学系１０２、測定対象物Ｇを反射した照明光を受光し、電気信号に光電変換して出力する受光部１０３、この共焦点型光学系１０２（以下、光学系１０２と呼ぶ。）を透過した測定対象物Ｇからの反射光を分光して受光部１０３に導くビームスプリッタ１０４及び受光部１０３から出力される受光信号を用いて測定対象物Ｇの表面の位置座標を算出する演算部１０５からなる基本構成を有している。
【００２３】
測定対象物Ｇの三次元形状は当該測定対象物Ｇを三次元形状装置１の前方に配置された測定テーブル１０６に載置し、当該測定テーブル１０６を高さ方向に所定のピッチで昇降させつつ、各高さ位置で測定対象物Ｇの表面の凹凸を計測することにより行なわれる。すなわち、測定対象物Ｇの高さ方向をＹ方向、光学系１０２の光軸方向をＺ方向、Ｙ方向及びＺ方向に直交する方向をＸ方向とすると、測定対象物ＧのＹ座標を所定のピッチで変化させつつ、各Ｙ座標の位置で測定対象物ＧのＺ座標を計測することにより測定対象物Ｇの三次元形状が計測される。そして、三次元形状計測装置１で計測された測定対象物Ｇの三次元形状データ（ｘ，ｙ，ｚ）は形状データ処理装置３に入力される。
【００２４】
なお、三次元計測装置１はＸ軸と平行に配置されたラインセンサからなる光電変換素子１０３ａを備え、この光電変換素子１０３ａの各画素毎（各画素位置がＸ座標に相当）にその受光信号を用いて測定対象物Ｇの表面の位置座標（Ｚ座標）を計測するようなっている。このため、光電変換素子１０３ａ全体に測定対象物Ｇからの反射光が入射されるように、照明部１０１からはＸ方向に延びるスリット状の照明光が発光される。
【００２５】
測定対象物ＧのＺ座標は以下のように計測される。まず、光学系１０２の像側の焦点位置に配置された照明部１０１からＸ方向に延びるスリット状の照明光を発光させる。この照明光は光学系１０２の物体側の焦点位置に集光され、その焦点位置にＸ方向に延びるライン光が形成される。次に、この状態で光学系１０２の物体側の焦点位置（すなわち、ライン光）を光軸方向に当該焦点位置が測定対象物Ｇの内部に至るまで移動させつつ、所定の周期で光電変換素子１０３ａの露光を繰り返す。そして、各露光位置で受光された受光信号のレベルを用いて、演算部１０５で最大レベルとなる露光位置を光電変化素子１０３ａの各画素毎に算出し、その位置を測定対象物Ｇの表面のＺ座標とする。
【００２６】
形状データ処理装置３は、ポリゴン生成部３１、データ削減部３２、許容値入力部３３及びデータ出力部３４を備えている。ポリゴン生成部３１は三次元形状計測装置１から入力された測定対象物Ｇの三次元形状データ（ｘ，ｙ，ｚ）に基づいて測定対象物Ｇのポリゴンモデルを生成するものである。データ削減部３２はポリゴンモデルのエッジ収縮もしくは面収縮により三次元形状データの削減を行うものである。すなわち、図３に示すように、計測データに基づく精密なポリゴンモデルＡを所定の許容誤差範囲内でポリゴンモデルＢに近似化するように、ポリゴンモデルＡの格子点（三次元形状データ）を適当に削減するものである。
【００２７】
データ削減部３２は、後述するデータ削減処理を実行するため、評価値演算部３２１、評価値ソート部３２２及びエッジ／面収縮処理部３２３を備えている。
【００２８】
評価値演算部３２１は、２個以上の格子点を集結して１個の格子点に置換することによりポリゴンモデルを構成するエッジ又は面を収縮する（すなわち、ポリゴンモデルの近似化を図る）に当たり、各エッジ又は各面の収縮の可否を判定するための評価値を算出するものである。この評価値については後述する。
【００２９】
評価値ソート部３２２は評価値演算部３２１で各エッジ毎もしくは各面毎に算出された複数の評価値を小さい順もしくは大きい順に並べ替えることで最小の評価値を算出するものである。エッジ／面収縮処理部３２３は評価値ソート部３２２で算出された最小評価値を許容値入力部３３から入力された許容値と比較し、許容値以下であるとき、その最小評価値に対応するエッジもしくは面の収縮処理を行うものである。なお、評価値及びエッジ収縮方法については後述する。
【００３０】
許容値入力部３３は上述のようにエッジ収縮もしくは面収縮の可否を判定するための許容値を操作者が入力するためのものである。この許容値はポリゴンモデルを近似化するに当たり、エッジ収縮もしくは面収縮を行ってもポリゴンモデルの特徴部分への影響が少ないとされる許容範囲に相当し、操作者によって測定対象物Ｇの形状に応じて適宜入力される。
【００３１】
データ出力部３４はデータを削減された三次元形状データ（近似化されたポリゴンモデルを構成する三次元形状データ）を外部記憶装置４、表示装置５、外部処理装置６に出力するインターフェースである。
【００３２】
外部記憶装置４は磁気ディスク、光ディスク、磁気光ディスク等の外部記録媒体にデータを記録するもので、形状データ処理装置３から三次元形状データが入力されると、所定のファイル形式で外部記録媒体に記録する。
【００３３】
表示装置５はブラウン管、液晶表示デバイス等の電子ディスプレイ装置からなる表示装置である。表示装置５に形状データ処理装置３から三次元形状データが入力されると、そのデータに基づいて近似化された測定対象物Ｇのポリゴンモデルの画像が表示される（図３のポリゴンモデルＢを参照）。
【００３４】
外部処理装置６は、例えば測定対象物Ｇの表面形状と略同一の形状を有する金型や模型を製作する装置である。外部処理装置６に形状データ処理装置３から三次元形状データが入力されると、その三次元形状データに基づいてワークが切削されて金型等が自動製作される。
【００３５】
次に、本発明に係るデータ削減方法を説明する。
【００３６】
図４はエッジ収縮によるデータ削減方法の概念図である。また、図５は面収縮によるデータ削減方法の概念図である。
【００３７】
エッジ収縮によるデータ削減方法は、図４に示すようにポリゴンモデルが格子点ｖ1〜ｖ10で構成されている場合、例えば格子点ｖ1と格子点ｖ2とを結ぶエッジＥｄ12を収縮するように両格子点ｖ1，ｖ2を格子点ｖ1’に集結させてデータ数を削減する方法である。
【００３８】
エッジ収縮によるデータ削減方法（以下、エッジ収縮法と略称する。）では、まず、全てのエッジＥｄij（ｉ，ｊ＝１，２，…１０。但し、ｉ≠ｊで格子点が互いに隣接する組合わせ）についてエッジ収縮によるポリゴンモデルの形状変化への影響を評価する評価値を算出し、最小の評価値が許容値以下である場合にその評価値に対応するエッジＥｄijの両端の格子点ｖi，ｖjを所定の格子点ｖi’に集結してデータの削減が行なわれる。
【００３９】
次に、格子点ｖi，ｖjを格子点ｖi’に集結したポリゴンモデル（近似化されたポリゴンモデル）について同様の方法でエッジの収縮が行われ、更にデータの削減が行なわれる。そして、以下同様の方法でエッジ収縮後のポリゴンモデルにつきエッジ収縮ができなくなるまで１つずつエッジ収縮を行って（すなわち、最小評価値が許容値よりも大きくなるまでポリゴンモデルの近似化を繰り返して）、データの削減が行われる。
【００４０】
なお、格子点ｖi’は、上述した論文「３次元ポリゴンモデルの階層的近似」に示されるように、例えばエッジＥｄijの中点等の格子点ｖi，ｖj間の適所に設定される近似点である。
【００４１】
面収縮によるデータ削減方法（以下、面収縮法と略称する。）は、図５に示すようにポリゴンモデルが格子点ｖ1〜ｖ11で構成されている場合、例えば格子点ｖ1，格子点ｖ2及び格子点ｖ3で囲まれた面Ｐ123を除去するように格子点ｖ1，ｖ2，ｖ3を格子点ｖ1’に集結させてデータ数を削減する方法である。
【００４２】
面収縮によるデータ削減方法も基本的にエッジ収縮によるデータ削減方法と同様の手順で行なわれる。すなわち、まず、全ての面Ｐijk（ｉ，ｊ，ｋ＝１，２，…１０。但し、ｉ≠ｊ≠ｋで格子点が互いに隣接する組合わせ）について面収縮によるポリゴンモデルの形状変化への影響を評価する評価値を算出し、最小の評価値が許容値以下である場合にその評価値に対応する面Ｐijkを構成する格子点ｖi，ｖj，ｖkを所定の格子点ｖi’に集結してデータの削減が行なわれ、以下同様の方法で面収縮後のポリゴンモデルにつき面収縮ができなくなるまで１つずつ面収縮を行ってデータの削減が行われる。
【００４３】
エッジ収縮法もしくは面収縮法によって三次元形状データを順次削減した場合、データ削減処理後の被測定物Ｇを構成する三次元形状データは三次元形状計測装置１で実測された被測定物Ｇの三次元形状データとは異なり、近似された三次元形状データとなる。このため、実測された三次元形状データで構成されるポリゴンモデル（以下、最初のポリゴンモデルという。）に対するデータ削減後のポリゴンモデル（以下、近似化されたポリゴンモデルという。）の誤差を管理しながらデータ削減処理を行う必要がある。
【００４４】
本実施形態に係るデータ削減方法では、例えばエッジ収縮を繰り返して、例えば図６に示すように格子点ａ，ｂ，ｃ（実測された三次元形状データ）がそれぞれ格子点ａ’，ｂ’，ｃ’に近似され、三角形ポリゴンＰabcが三角形ポリゴンＰabc’に近似されるとすると、近似後の三角形ポリゴンＰabc’を含む面がこの面の近似処理に関与する最初の格子点ａ，ｂ，ｃから離れていく具合を誤差として管理するようにしている。
【００４５】
なお、図６の例では、説明の便宜上、近似処理に関与する格子点を格子点ａ，ｂ，ｃとしたが、実際の処理では、例えば格子点ａが格子点ａ’に集結されていく過程で格子点ａ以外の格子点（実測データ）が含まれているので、上述した誤差にはこれらの格子点と三角形ポリゴンＰabc’との距離も含まれる。
【００４６】
次に、本実施形態に係るデータ削減方法に適用される誤差の評価値について説明する。
【００４７】
一般に、三次元空間における平面ｐは、
Ａ・ｘ＋Ｂ・ｙ＋Ｃ・ｚ＋Ｄ＝０  …（１）
但し、Ａ2＋Ｂ2＋Ｃ2＝１
の方程式で表される。
【００４８】
一方、三次元空間上の点ｖの座標を（ｖx，ｖy，ｖz）とすると、点ｖと平面ｐとの距離ｄは、
ｄ＝Ａ・ｖx＋Ｂ・ｖy＋Ｃ・ｖz＋Ｄ  …（２）
で算出され、行列式でベクトル表記すると、下記（３）式のようになる。
【００４９】
【数１】
0004151185.tif 000002
【００５０】
従って、距離ｄの２乗は、下記（４）式のようになる。
【００５１】
【数２】
0004151185.tif 000003
【００５２】
上記（４）式は、１つの平面ｐとこの平面ｐに含まれない１個の点ｖとの距離ｄの２乗を示すものであるが、平面ｐに対して複数個の点ｖ1，ｖ2，…ｖmがある場合、これらの点ｖi（ｉ＝１，２，…ｍ）との距離の２乗和Δ（ｐ）は、下記（５）式のようになる。
【００５３】
【数３】
0004151185.tif 000004
【００５４】
本実施形態に係るデータ削減方法においては、例えばエッジ収縮によりデータ削減をする場合、あるエッジの収縮によって影響を受けるポリゴンモデルの平面がｎ枚あるとする場合、それらの平面の全てについて、各平面とその平面への近似化のためにデータ削減処理に関与した複数個の最初の格子点（元の三次元形状データ）との距離の離れ具合を評価するようにしているので、各平面毎に上記（５）式によって算出される距離の２乗和Δ（ｐ）を算出し、これらの総和をデータ削減処理に関与した全ての格子点の総数Ｍで除した、下記（６）式で示されるεを誤差の評価値としている。
【００５５】
【数４】
0004151185.tif 000005
【００５６】
なお、上記（６）式において、Δ（ｐi）は、ｉ番目の平面ｐiに対する当該平面ｐiの近似化に寄与した全ての最初の格子点との距離の２乗和であり、ｍiはその距離の２乗和における項数である。
【００５７】
また、上記（６）式の演算処理においては、行列Ｋｖiは上記（４）式で示したように対称行列となるので、最初の格子点ｖiについて算出される行列行列Ｋｖiは、対角元素とその対角元素より上側の元素とをメモリに記憶させるようにするとよい。このようにすれば、演算処理に必要なメモリ容量を低減することができる。また、上記（６）式の分子の各要素ｍiはｉ番目の近似面ｐiにおける距離の２乗和の項数であるが、行列Ｋｖの右下隅の元素は常に「１」であり、この距離の２乗和の演算結果における行列ΣＫｖの右下隅の元素はｍiとなるから、この元素の値を利用して上記（６）式の演算を行うようにするとよい。このようにすれば、改めて項数ｍiを算出する必要がなく、演算処理が容易となる。
【００５８】
なお、上記（５）式をある平面ｐに対する誤差の評価に適用した場合、当該平面ｐに至るエッジ収縮もしくは面収縮の処理過程で関与した最初の格子点ｖiが特定されると、それらの格子点ｖiの三次元形状データから得られる行列Ｋｖiを加算したΣＫｖiはそのエッジ収縮もしくは面収縮における誤差の程度が示すパラメータとなる。そこで、以下の説明ではこのΣＫｖiを誤差行列と呼ぶ。
【００５９】
次に、三次元形状データのデータ削減処理の手順について、図７のフローチャートを用いて説明する。
【００６０】
三次元形状計測装置１により取り込まれた測定対象物Ｇの三次元形状データは、形状データ処理装置３に入力され、まず、ポリゴン生成部３１で三角形のポリゴンモデルが生成される（＃１）。また、操作者により許容値入力部３３からエッジ収縮処理の可否を判定するための許容値が入力される（＃３）。
【００６１】
続いて、評価値演算部３２１で最初のポリゴンモデルの全エッジについてエッジ収縮した場合の評価値εj（ｊ＝１，２，…Ｎ，Ｎはエッジ総数）が上記（６）式により算出される（＃５）。例えば図４の例では、エッジＥｄ1r（ｒ＝２〜５，９，１０）、Ｅｄ2s（ｓ＝５，６，…９）、Ｅｄtt+1（ｔ＝３，４，…１０、但し、ｔ＋１＝１１はｔ＋１＝３とする。）についてエッジ収縮した場合の評価値εj（ｊ＝１，２，…１９）が算出される。
【００６２】
このとき、例えば格子点ｖ1，ｖ2を格子点ｖ1’に集結してエッジＥｄ12を収縮した場合、最初の面は全て変形し、格子点ｖ1’とエッジ収縮に関係しない格子点ｖ3〜ｖ10とによって８枚の平面面ｐ1，ｐ2，…ｐ10（以下、変形後の平面を近似面という。）が形成されるが、これらの近似面ｐk（ｋ＝１，２，…８）についてそれぞれ距離の２乗和Δ（ｐk）（ｋ＝１，２，…８）が算出されるとともに、これらの距離の２乗和Δ（ｐk）全体に含まれる要素の総数Ｍが算出され、上記（６）式によりエッジＥｄ12の収縮処理における評価値ε（Ｅｄ12）が算出される。なお、評価値ε（Ｅｄ12）は下記（７）式のようになる。
【００６３】
【数５】
0004151185.tif 000006
【００６４】
このとき、例えば平面ｐ1は格子点ｖ1’，ｖ3，ｖ4によって構成されるが、格子点ｖ1，ｖ2，ｖ3，ｖ4が実測データである場合はエッジ収縮に関与した格子点はｖ1，ｖ2だけであるから、距離の２乗和Δ（ｐ1）はこれらの格子点ｖ1，ｖ2についての誤差行列（Ｋｖ1＋Ｋｖ2）を用いて上記（５）式により算出される。この状態で格子点ｖ1’が更に他の格子点ｖm（図示しない実測データ）とともに格子点ｖ1”（図示していない）に集結されて近似面ｐ1が近似面ｐ1’（図示していない）に近似された場合、この近似面ｐ1’に至るエッジ収縮に関与した格子点はｖ1，ｖ2，ｖmとなるから、距離の２乗和Δ（ｐ1’）はこれらの格子点ｖ1，ｖ2，ｖmについての誤差行列（Ｋｖ1＋Ｋｖ2＋Ｋｖm）を用いて上記（５）式により算出されることになる。
【００６５】
この２回目のエッジ収縮では、実質的に格子点ｖ1’の誤差行列Ｋｖ1’を（Ｋｖ1＋Ｋｖ2）として格子点ｖ1’の誤差行列Ｋｖ1’と格子点ｖmの誤差行列Ｋｖmとで上記（５）式により距離の２乗和Δ（ｐ1’）を算出することになる。
【００６６】
従って、エッジ収縮処理の過程における一般論では、図４において、格子点ｖ1，ｖ2，ｖ3，ｖ4を実測データでなく、エッジ収縮によって生成されたデータであるとすれば、各格子点ｖ1，ｖ2，ｖ3，ｖ4に対する誤差行列をそれぞれＫｖ1，Ｋｖ2，Ｋｖ3，Ｋｖ4とすると、近似面ｐ1を構成する格子点ｖ1’に対する誤差行列Ｋｖ1’をＫｖ1’＝Ｋｖ1＋Ｋｖ2とし、近似面ｐ1を構成する３個の格子点ｖ1’，ｖ3，ｖ4の誤差行列Ｋｖ1’，Ｋｖ3，Ｋｖ4を加算して得られる誤差行列Ｋp1（＝Ｋｖ1’＋Ｋｖ3＋Ｋｖ4＝Ｋｖ1＋Ｋｖ2＋Ｋｖ3＋Ｋｖ4）を用いて上記（５）式により近似面ｐ1について距離の２乗和Δ（ｐ1）が算出される。
【００６７】
なお、距離の２乗和Δ（ｐ1）の算出式は、
Δ（ｐ1）＝Ｐ1T・Ｋp1・Ｐ1  …（８）
となる。ここに、Ｐ1は近似面ｐ1の列ベクトル表記、ｍ1は誤差行列Ｋp1に含まれる誤差行列Ｋｖの総数である。
【００６８】
そして、近似面ｐ2，ｐ3，…ｐ8についても上述した近似面ｐ1と同様の方法で距離の２乗和Δ（ｐ2），Δ（ｐ3），…Δ（ｐ8）が算出され、これらを上記（７）式に代入してエッジＥｄ12の収縮における誤差評価値ε（Ｅｄ12）が算出される。
【００６９】
そして、同様の方法で他のエッジＥｄ1r，Ｅｄ2s、Ｅｄtt+1についてもエッジ収縮をした場合の誤差評価値ε（Ｅｄ1r），ε（Ｅｄ2s）、ε（Ｅｄtt+1）が算出される。
【００７０】
続いて、評価値ソート部３２２で誤差評価値εjのソーティングが行われ（＃７）、最小の評価値Ｍｉｎ｛εj｝がステップ＃３で入力された許容値以下であるか否かが判別される（＃９）。最小評価値Ｍｉｎ｛εj｝が許容値よりも大きければ（＃９でＮＯ）、全てのエッジについてエッジ収縮した場合の形状変化が許容できない程大きいので、エッジ収縮によるデータ削減処理を終了する。一方、最小評価値Ｍｉｎ｛εj｝が許容値以下であれば（＃９でＹＥＳ）、エッジ／面収縮処理部３２３でその最小評価値Ｍｉｎ｛εj｝に対応するエッジの収縮処理が行われる（＃１１）。例えば図４において、最小評価値Ｍｉｎ｛εj｝がε（Ｅｄ12）であれば、同図に示すようにエッジＥｄ12の収縮処理が行われる。
【００７１】
続いて、エッジ収縮後のポリゴンモデルについて当該エッジ収縮処理の影響を受けたエッジについて再度、誤差評価値εq（ｑ＝１，２，…）が算出された後（＃１３）、ステップ＃７に戻り、これらの誤差評価値εqのうち、最小の誤差評価値Ｍｉｎ｛εq｝が算出され、それに対応するエッジの収縮処理が行われる（＃７〜＃１１）。以下、１本ずつエッジ収縮処理を繰り返し（＃７〜＃１３のループ）、最小評価値Ｍｉｎ｛εq｝が許容値より大きくなった時点でデータ削減処理を終了する（＃９でＮＯ）。
【００７２】
従って、このようなデータ削減処理を行うことにより、データ削減後のポリゴンモデルは、最初のポリゴンモデルに対して最初の計測データに対する誤差評価値εが許容値以下となるように近似化される。
【００７３】
上記のように本実施の形態にかかるデータ削減方法では、エッジ収縮もしくは面収縮により近似化されるポリゴンモデルの面が最初の格子点（計測された三次元形状データ）に対してどの程度の離れ具合となるかを誤差の評価値としているので、直感的にも解り易い評価基準でデータ削減処理を行うことができる。
【００７４】
また、その評価値が所定の許容誤差範囲内となるようにデータ削減を行うようにしているので、近似後のポリゴンモデルを構成する三次元形状データの誤差を比較的正確に管理しつつデータ削減処理を高速に行うことができる。
【００７５】
特に、計測された三次元形状データにランダムなノイズのデータが混入した場合や多数の格子点を１点に集結してデータ削減を行う場合にも誤差評価値の信頼性の低下を抑えることができる。
【００７６】
図８及び図９は、計測された三次元形状データにランダムなノイズのデータが混入した場合の誤差評価方法を従来の誤差評価方法と比較したものである。
【００７７】
図８は、ランダムなノイズのデータによってポリゴンモデルに不連続面が生じている部分（断面で表示している。）のエッジ収縮を示す図である。同図に示すように、ポリゴンモデル表面の不連続な凸凹が大きく生じている部分の格子点ｖ1，ｖ2を略中心の格子点ｖ1’に集結した場合、上記従来の論文「Surface  Simplification  Using  Quadric  Error  Metrics」に示されるデータ削減方法では、図９に示すように格子点ｖ1’から、例えば格子点ｖ1，ｖ4を含む面ｐ14と格子点ｖ2，ｖ5を含む面ｐ25への距離ｄ1’，ｄ2’を誤差評価の基礎としているので、感覚的な近似誤差に対して誤差評価値は小さい目に算出されるのに対し、本実施形態に係るデータ削減方法では、例えば格子点ｖ1，ｖ2からの格子点ｖ1’，ｖ4，ｖ5を含む平面ｐ45への距離ｄ1，ｄ2を誤差評価の基礎としているので、誤差評価値は感覚的な近似誤差に比較的合致し、小さい目に算出されることはない。
【００７８】
図１０、図１１及び図１２は、多数の格子点を１点に集結した場合の誤差評価方法を従来の誤差評価方法と比較したものである。
【００７９】
図１０は、８個の格子点ｖ1，ｖ2，…ｖ8でジグザグな面（断面で表示している。）が形成されているポリゴンモデルの当該ジグザグ面の収縮を示す図である。同図に示すように、格子点ｖ1，ｖ2，…ｖ6を格子点ｖ7，ｖ8の略中心の格子点ｖ1’に集結した場合、上記従来の論文「Surface  Simplification  Using Quadric  Error  Metrics」に示されるデータ削減方法では、図１１に示すように格子点ｖ1’から最初のポリゴンモデルのジクザグな各面ｐ71，ｐ12，ｐ23，ｐ34，ｐ45，ｐ56，ｐ68への距離ｄ1’，ｄ2’，…ｄ6’を誤差評価の基礎としているので、感覚的な近似誤差に対して誤差の評価値は大きい目に算出されるのに対し、本実施形態に係るデータ削減方法では、例えば各格子点ｖ1，ｖ2，…ｖ6からの格子点ｖ1’，ｖ7，ｖ8を含む平面ｐ78への距離ｄ1，ｄ2，…ｄ6を誤差評価の基礎としているので、誤差の評価値は感覚的な近似誤差に比較的合致し、大きい目に算出されることはない。
【００８０】
図１３は、三次元形状データのデータ削減処理手順の変形例を示すフローチャートである。
【００８１】
図７に示すデータ削減処理手順では、エッジ収縮処理を行う毎にそのエッジ収縮により影響を受けたエッジについて再度、評価値εを算出し、その評価値εに基づいて次のエッジ収縮処理を行うようにしていたが、図１３に示すデータ削減処理手順は、エッジ収縮により影響を受けたエッジについての評価値εの演算を行わず、それ以外のエッジについてエッジ収縮を行うようにしたものである。
【００８２】
具体的には、図１３に示すフローチャートは、図７において、ステップ＃１３の処理を「エッジ収縮により影響を受けたエッジの収縮を禁止する」処理のステップ＃１３’に変更し、ステップ＃９と「終了」の処理の間にステップ＃１５，＃１７の処理を追加したものである。
【００８３】
そこで、以下の説明ではフローチャートの共通部分については簡単に説明し、異なる部分について詳細に説明する。
【００８４】
三次元形状計測装置１により取り込まれた測定対象物Ｇの三次元形状データは、形状データ処理装置３に入力され、ポリゴン生成部３１で三角形のポリゴンモデルが生成される（＃１）。また、操作者により許容値入力部３３からエッジ収縮処理の可否を判定するための許容値が入力される（＃３）。
【００８５】
続いて、評価値演算部３２１でポリゴンモデルの全エッジについてエッジ収縮した場合の評価値εj（ｊ＝１，２，…Ｎ，Ｎはエッジ総数）が算出され（＃５）、評価値ソート部３２２で誤差評価値εjのソーティングが行われて最小の評価値Ｍｉｎ｛εj｝が算出される（＃７）。
【００８６】
続いて、最小評価値Ｍｉｎ｛εj｝がステップ＃３で許容値以下であるか否かが判別され（＃９）、最小評価値Ｍｉｎ｛εj｝が許容値以下であれば（＃９でＹＥＳ）、エッジ／面収縮処理部３２３でその最小評価値Ｍｉｎ｛εj｝に対応するエッジの収縮処理が行われる（＃１１）。
【００８７】
続いて、このエッジ収縮処理で影響を受けたエッジの収縮処理が禁止され（＃１３’）、ステップ＃７に戻る。この処理は、次のエッジ収縮処理を今回のエッジ収縮処理で影響を受けなかったエッジについて行うようにするためのものである。
【００８８】
ステップ＃７に戻ると、エッジ収縮が禁止されたエッジ以外のエッジに対する評価値εq（ｑ＝１，２，…Ｑ。但し、Ｑ＜Ｎ）についてソーティングが行われ、最小評価値Ｍｉｎ｛εq｝が算出される（＃７）。そして、最小評価値Ｍｉｎ｛εq｝が許容値以下であるか否かが判別され（＃９）、最小評価値Ｍｉｎ｛εq｝が許容値以下であれば（＃９でＹＥＳ）、エッジ／面収縮処理部３２３でその最小評価値Ｍｉｎ｛εq｝に対応するエッジの収縮処理が行われ（＃１１）、更にこのエッジ収縮処理で影響を受けたエッジの収縮処理が禁止され（＃１３’）、再度、ステップ＃７に戻る。
【００８９】
そして、以下、同様の処理を繰り返し、エッジ収縮処理を行う毎にそのエッジ収縮で影響を受けたエッジを除外しつつ次のエッジ処理処理が行なわれる（＃７，＃９，＃１１，＃１３’のルーブ）。
【００９０】
一方、上記エッジ収縮処理を繰り返す過程で、最小評価値Ｍｉｎ｛εq｝が許容値よりも大きいと（＃９でＮＯ）、エッジ収縮が禁止されたエッジがあるか否かが判別され（＃１５）、エッジ収縮が禁止されたエッジがあれば（＃１５でＹＥＳ）、それらのエッジについて再度、誤差評価値εr（ｒ＝１，２，…）が算出された後（＃１７）、ステップ＃７に戻り、これらの誤差評価値εrのうち、最小誤差評価値Ｍｉｎ｛εr｝が算出され、その最小誤差評価値Ｍｉｎ｛εr｝に対応するエッジの収縮処理が行われる（＃７，＃９，＃１１）。
【００９１】
そして、上記エッジ収縮処理を繰り返し、最小評価値Ｍｉｎ｛εq｝が許容値よりも大きくなるとともに、エッジ収縮が禁止されたエッジもなくなると（＃９，＃１５でＮＯ）、エッジ収縮によるデータ削減処理を終了する。
【００９２】
図１４は、図１３に示す処理手順によるデータ削減プロセスの一例を示す図である。
【００９３】
同図において、ポリゴンモデルＭ0は最初のポリゴンモデルである。このポリゴンモデルＭ0は２８個の格子点ｖ1，ｖ2，…ｖ28を各行の個数が（３，４，５，４，５，４，３）個となるように５行に配列し、隣り合う格子点間を結んだものである。
【００９４】
エッジｅ１，ｅ２，ｅ３，ｅ４，ｅ５は、各エッジｅｉ（ｉ＝１，２，…５）を収縮させた場合、互いにその影響を受けない関係にあるから、説明の便宜上、図１３に示す処理手順によって順次、エッジ収縮されるものとして選択したものである。
【００９５】
従って、図１４のデータ削減プロセスは、図１３の処理手順によってポリゴンモデルＭ0がエッジｅ１，ｅ２，…ｅ５の順に順次、エッジ収縮される場合を示している。そして、ポリゴンモデルＭ1，Ｍ2，Ｍ3，Ｍ4，Ｍ5は、ポリゴンモデルＭ0をエッジｅ１，ｅ２，…ｅ５の順に収縮処理したときの近似化されたポリゴンモデルである。
【００９６】
上述した図１３に示すデータ削減処理手順によれば、まず、最初のエッジ収縮処理でエッジｅ１が収縮されてポリゴンモデルＭ1に近似化されると、集結された格子点ｖaとその周囲に配置される格子点ｖ9，ｖ10，ｖ11，ｖ13，ｖ16，ｖ18，ｖ19，ｖ20（ポリゴンモデルＭ1の点線枠内の格子点）とで形成されるエッジが影響を受けることになるため、次のエッジ収縮処理では、これらのエッジを除外したエッジ（ポリゴンモデルＭ1の点線枠の外にあるエッジ）について再度、評価値εqのソーティングが行なわれ、最小評価値Ｍｉｎ｛εq｝を有するエッジｅ２についてエッジ収縮処理が行われてポリゴンモデルＭ2に近似化される。
【００９７】
更に、次のエッジ収縮処理では、集結された格子点ｖbとその周囲に配置される格子点ｖ1，ｖ2，ｖ4，ｖ6，ｖ8，ｖ10，ｖ13，ｖa（ポリゴンモデルＭ2の点線枠内の格子点）とで形成されるエッジが影響を受けることになるため、これらのエッジを除外したエッジ（ポリゴンモデルＭ2の点線枠の外にあるエッジ）について再度、評価値εsのソーティングが行なわれ、最小評価値Ｍｉｎ｛εs｝を有するエッジｅ３についてエッジ収縮処理が行われてポリゴンモデルＭ3に近似化される。
【００９８】
そして、以下同様の方法でエッジｅ４，ｅ５についてもエッジ収縮が行なわれ、この５回のエッジ収縮処理により最初のポリゴンモデルＭ0はポリゴンモデルＭ5に近似化され、データ数は５個削減される。
【００９９】
最初のポリゴンモデルＭ0を６枚目のポリゴンモデルＭ6（図示せず。）まで近似化するプロセスを考えると、図１３に示す処理手順ではエッジ収縮によって影響を受けたエッジについては評価値の再計算をしないので、図１４の例では、最初のポリゴンモデルＭ0を構成する６６本のエッジについて最初に評価値が計算されると、近似化されたポリゴンモデルＭ1〜Ｍ4については評価値の再計算は行なわれず、次の再計算はポリゴンモデルＭ5を構成する５０本のエッジについて行なわれることになる。従って、６枚目のポリゴンモデルＭ6までの評価値の再計算回数は５０回となる。
【０１００】
一方、図７に示す処理手順ではエッジ収縮によって影響を受けたエッジについて評価値の再計算を行っているので、近似化された各ポリゴンモデルＭ1〜Ｍ5毎にエッジ収縮によって影響を受ける１６本のエッジについて評価値の再計算をすることになる。従って、図７に示す処理手順では、６枚目のポリゴンモデルＭ6までの評価値の再計算回数は１６×５＝８０回となり、図１３に示す処理手順の方が評価値の再計算回数が少なくなり、高速処理が可能になるという利点がある。
【０１０１】
図１５は、図１３に示すフローチャートの変形例である。
【０１０２】
図１５に示すフローチャートは、エッジ収縮後に影響を受けたエッジの評価値を許容値よりも大きい所定の評価値εmaxに置換することにより次のエッジ収縮ではそのエッジを実質的にエッジ収縮の対象外となるようにしたものである。
【０１０３】
具体的には、図１３のフローチャートにおいて、ステップ＃１３’を「エッジ収縮により影響を受けたエッジの評価値をεmaxに設定する」処理のステップ＃１３”に変更するとともに、ステップ＃１５の判定対象及びステップ＃１７の評価値再計算の対象を「評価値がεmaxのエッジ」に変更し、ステップ＃１７’の後に評価値再計算後のエッジに対するエッジ収縮処理を行うステップ#１９，＃２１の処理を追加したものである。
【０１０４】
そこで、以下の説明では図１３のフローチャートと異なる部分について詳細に説明する。
【０１０５】
ステップ＃１１でエッジ／面収縮処理部３２３により最小評価値Ｍｉｎ｛εj｝に対応するエッジの収縮処理が行われると、このエッジ収縮処理で影響を受けたエッジの評価値が許容値よりも大きい所定の評価値εmaxに設定され（＃１３”）、ステップ＃７に戻る。この処理は、これらのエッジが次のエッジ収縮処理で対象外となるようにする、すなわち、エッジ収縮処理で影響を受けなかったエッジについてのみエッジ収縮が行なわれるようにするためのものである。
【０１０６】
ステップ＃７に戻ると、再度、評価値εi（ｉ＝１，２，…Ｎ−１）のソーティングが行われ、最小評価値Ｍｉｎ｛εi｝が算出される（＃７）。そして、最小評価値Ｍｉｎ｛εi｝が許容値以下であるか否かが判別され（＃９）、最小評価値Ｍｉｎ｛εi｝が許容値以下であれば（＃９でＹＥＳ）、エッジ／面収縮処理部３２３でその最小評価値Ｍｉｎ｛εi｝に対応するエッジの収縮処理が行われる（＃１１）。
【０１０７】
続いて、このエッジ収縮処理で影響を受けたエッジの評価値が評価値εmaxに設定され（＃１３”）、再度、ステップ＃７に戻る。以下、同様の処理を繰り返し、エッジ収縮処理を行う毎にそのエッジ収縮で影響を受けたエッジの評価値を評価値εmaxに設定しつつ次のエッジ処理処理が行なわれる（＃７，＃９，＃１１，＃１３”のルーブ）。
【０１０８】
一方、上記エッジ収縮処理を繰り返す過程で、最小評価値Ｍｉｎ｛εi｝が許容値よりも大きくなると（＃９でＮＯ）、評価値εmaxを有するエッジがあるか否かが判別され（＃１５’）、評価値εmaxを有するエッジがあれば（＃１５’でＹＥＳ）、それらのエッジについて再度、誤差評価値εs（ｓ＝１，２，…）が算出される（＃１７’）。
【０１０９】
そして、ソーティングによりこれらの誤差評価値εsのうち、最小の誤差評価値Ｍｉｎ｛εs｝が算出され（＃１９）、その最小評価値Ｍｉｎ｛εi｝が許容値以下であれば（＃２１でＹＥＳ）、ステップ＃１１に移行して上述したその最小評価値Ｍｉｎ｛εi｝に対応するエッジの収縮処理が行われる。
【０１１０】
一方、上記エッジ収縮処理を繰り返し、評価値εmaxを有するエッジがなくなるか（＃１５’でＹＥＳ）、あるいは評価値εmaxを有するエッジについて再計算された評価値εsのうち、最小評価値Ｍｉｎ｛εs｝が許容値よりも大きくなると（＃２１でＮＯ）、エッジ収縮によるデータ削減処理を終了する。
【０１１１】
図１５に示す処理手順もエッジ収縮により影響を受けるエッジの評価値を許容値よりも大きい評価値εmaxに設定することで、実質的に図１３の処理手順に示す当該エッジの収縮を禁止するようにしているので、評価値の再計算回数が低減され、高速処理が可能となる。
【０１１２】
なお、図１３、図１５に示すデータ削減の処理手順では、エッジ収縮処理により影響を受けた部分については、エッジ収縮処理が禁止された部分が全てなくなるまで、評価値の再計算をせず、エッジ収縮処理の対象外とするようにしているが、例えばエッジ収縮処理が所定の回数だけ繰り返されたときや評価値の最小値と許容値との差が所定の範囲内になったとき等の所定の条件が満たされると、エッジ収縮処理の禁止を解除し、全てのエッジについて評価値の再計算を行なって、再度、エッジ収縮を可能にするようにしてもよい。
【０１１３】
このようにすれば、エッジ収縮処理が禁止された部分に許容誤差内でデータ削減処理が可能な部分が残っている場合にもその部分についてデータ削減処理が可能になり、許容範囲内で可能な限り効率良くデータ削減を行うことができる。
【０１１４】
また、図１３、図１５に示すデータ削減の処理手順は、評価値の再計算回数を低減し、処理速度の高速化を図るものであるので、評価値は、上述の（６）式で示した誤差εに限定されるものではない。エッジ収縮もしくは面収縮により評価値が変化し、収縮後に再計算が必要となるような評価値、例えば上述の論文「Surface  Simplification  Using  Quadric  Error  Metrics」に示される評価値を採用している場合にも広く適用することができる。
【０１１５】
また、上記実施の形態では三次元形状計測装置１で計測された三次元計測データのデータ削減を例に説明したが、本発明はこれに限定されるものではなく、コンピュータグラフックス等で創作された三次元データについても広く適用することができる。
【０１１６】
【発明の効果】
以上説明したように、本発明によれば、ポリゴンモデルにおける２個以上の格子点を１個の格子点に集結させる対象となる複数の部分に対して当該集結によって生じる誤差を評価する評価値をそれぞれ算出し、これらの評価値に基づき格子点の集結対象部分のデータ削減を行なう処理を繰り返すことでポリゴンモデルを構成する三次元形状データのデータ数を順次、削減する三次元形状データのデータ削減方法であって、格子点の集結処理が行なわれると、当該格子点の集結処理により影響を受けた格子点の集結対象部分のデータ削減処理を禁止するようにしたので、格子点の集結対象部分の評価値の再計算回数が低減され、データ削減処理の高速化が可能となる。
【０１１７】
また、データ削減により影響を受けた格子点の集結対象部分の評価値を所定の値に変更して次のデータ削減処理では集結対象外となるようにしたので、当該格子点の集結対象部分のデータ削減処理を簡単に禁止させることができる。
【０１１８】
また、所定の条件が満たされると、禁止された格子点の集結対象部分のデータ削減処理の禁止を解除するようにしたので、許容範囲内で可能な限り効率良くデータ削減を行うことができる。
【図面の簡単な説明】
【図１】本発明に係るデータ削減方法を適用した三次元形状計測データ処理システムの構成を示すブロック図である。
【図２】形状データ処理装置の構成を示すブロック図である。
【図３】データ削減によるポリゴンモデルの近似化の一例を示す図である。
【図４】エッジ収縮によるデータ削減方法の概念図である。
【図５】面収縮によるデータ削減方法の概念図である。
【図６】本実施形態に係るデータ削減方法に適用される評価値を説明するための図である。
【図７】三次元形状データのデータ削減処理の手順を示すフローチャートである。
【図８】ランダムなノイズのデータによってポリゴンモデルに不連続面が生じている部分のエッジ収縮を示す図である。
【図９】図８に示すデータ削減処理における本実施形態に係る誤差評価値と従来の誤差評価値との差異を説明するための図である。
【図１０】ジグザグな面を有するポリゴンモデルの当該ジグザグ面の収縮を示す図である。
【図１１】図１０に示すデータ削減処理における従来の誤差評価値を説明するための図である。
【図１２】図１０に示すデータ削減処理における本実施形態に係る誤差評価値を説明するための図である。
【図１３】三次元形状データのデータ削減処理手順の他の実施形態を示すフローチャートである。
【図１４】図１３に示す処理手順によるデータ削減プロセスの一例を説明するための図である。
【図１５】図１３に示すフローチャートの変形例を示す図である。
【符号の説明】
１  三次元形状計測装置
１０１  照明部
１０２  共焦点型光学系
１０３  受光部
１０４  ビームスプリッタ
１０５  演算部
１０６  測定テーブル
２，４  外部記憶装置
３  形状データ処理装置（データ削減装置）
３１  ポリゴン生成部
３２  データ削減部
３２１  評価値演算部（評価値算出手段，禁止手段，解除手段）
３２２  評価値ソート部
３２３  エッジ／面収縮処理部（判定手段、データ削減手段）
３３  許容値入力部
３４  データ出力部
５  表示装置
６  外部処理装置
【図１】
0004151185.tif 000007
【図２】
0004151185.tif 000008
【図３】
0004151185.tif 000009
【図４】
0004151185.tif 000010
【図５】
0004151185.tif 000011
【図６】
0004151185.tif 000012
【図７】
0004151185.tif 000013
【図８】
0004151185.tif 000014
【図９】
0004151185.tif 000015
【図１０】
0004151185.tif 000016
【図１１】
0004151185.tif 000017
【図１２】
0004151185.tif 000018
【図１３】
0004151185.tif 000019
【図１４】
0004151185.tif 000020
【図１５】
0004151185.tif 000021