(57)【特許請求の範囲】
【請求項１】
２個以上の格子点を１個の格子点に集結してポリゴンモデルのエッジもしくは面を収縮することにより当該ポリゴンモデルを構成する複数の三次元座標データのデータ数を削減する三次元形状データのデータ削減方法であって、評価値算出手段が、上記ポリゴンモデルのエッジもしくは面を収縮することにより変形を受ける全ての面について、各面と各面の変形に関与した全ての最初の格子点との距離に基づく所定の評価値を算出する工程と、比較手段が、上記評価値を予め設定された許容値と比較する工程と、データ削減手段が、上記評価値が上記許容値以下であるとき、上記エッジもしくは面の収縮を行って上記三次元形状データの削減を行う工程とを備えたことを特徴とする三次元形状データのデータ削減方法。
【請求項２】
上記評価値は、下記（１）式で定義される誤差εであることを特徴とする請求項１記載の三次元形状データのデータ削減方法。
【数１】
0004192377.tif 000010
【請求項３】
２個以上の格子点を１個の格子点に集結してポリゴンモデルのエッジもしくは面を収縮することにより当該ポリゴンモデルを構成する複数の三次元座標データのデータ数を削減する三次元形状データのデータ削減装置であって、上記ポリゴンモデルのエッジもしくは面を収縮することにより変形を受ける全ての面について、各面と各面の変形に関与した全ての最初の格子点との距離に基づく所定の評価値を算出する評価値算出手段と、上記評価値を予め設定された許容値と比較する比較手段と、上記評価値が上記許容値以下であるとき、上記エッジもしくは面の収縮を行って上記三次元形状データの削減を行うデータ削減手段とを備えたことを特徴とする三次元形状データのデータ削減装置。
【請求項４】
上記評価値算出手段は、下記（１）式で定義される誤差εを評価値として算出するものであることを特徴とする請求項３記載の三次元形状データのデータ削減装置。
【数２】
0004192377.tif 000011
【請求項５】
上記評価値算出手段は、最初のポリゴンモデルを構成する全ての格子点ｖについてそれぞれ誤差行列Ｋｖを算出しておき、２個以上の格子点ｖｐ（ｐ＝１，２，…）を１の格子点ｖｑに集結したときは、集結させた各格子点ｖｐの誤差行列Ｋｖｐの和をその格子点ｖｑの誤差行列Ｋｖｑとして上記（１）式により誤差εを算出するものであること特徴とする請求項４記載の三次元形状データのデータ削減装置。
【請求項６】
上記評価値算出手段は、最初の格子点についてそれぞれ算出した誤差行列の対角元素とこの対角元素よりも上側の元素のみを記憶手段に記憶しておき、この記憶手段に記憶された対角元素とこの対角元素より上側の元素とを用いて誤差行列を復元し、この誤差行列を用いて上記（１）式により誤差εを算出することを特徴とする請求項５記載の三次元形状データのデータ削減装置。
【請求項７】
上記評価値算出手段は、最初の格子点の三次元形状データの列ベクトルＶが下記（２）式で表されるとき、各面ｐｉ毎に算出される誤差行列ΣＫｖｊ（ｊ＝１，２，…ｍｉ）の右下隅の元素を加算することで上記（１）式の総数Σｍｉ（ｉ＝１，２，…ｎ）を算出することを特徴とする請求項４記載の三次元形状データのデータ削減装置。
【数３】
0004192377.tif 000012
【請求項８】
上記評価値算出手段は、上記格子点ｖｊの誤差行列Ｋｖｊに代えて重み付誤差行列ｗｊ・Ｋｖｊを用いて上記（１）式により誤差εを算出することを特徴とする請求項４記載の三次元形状データのデータ削減装置。
【請求項９】
上記ポリゴンモデルのエッジ収縮もしくは面収縮に関与する格子点は、三角形ポリゴンモデルのエッジもしくは面を構成する格子点であることを特徴とする請求項１記載の三次元形状データのデータ削減方法。
【請求項１０】
２個以上の格子点を１個の格子点に集結することにより変形を受ける三角形の面を構成する格子点は、データ削減後の三角形ポリゴンモデルの面を構成する格子点であることを特徴とする請求項１記載の三次元形状データのデータ削減方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ポリゴンモデルを構成する三次元形状データのデータ削減方法及びその方法を用いたデータ削減装置に関するものである。
【０００２】
【従来の技術】
例えば空間分解能の極めて高い三次元形状計測装置で得られる描画品質の高い計測データはデータ数が膨大であるため、必要以上の描画品質を備えている場合は、その後の処理において記憶装置への負担が大きく、処理速度も著しく低下するという問題が生じる。このため、計測データのデータ数を削減して上記問題をできる限り低減することが必要となるが、この場合、データ削減後の計測データで構成されるポリゴンモデル（すなわち、近似化されたポリゴンモデル）と実測された三次元形状データで構成されるポリゴンモデル（以下、最初のポリゴンモデルという。）との相違が大きすぎると、データ削減後の計測データを有効に活用することができなくなるので、データ削減処理においては、近似化されたポリゴンモデルと最初のポリゴンモデルとの誤差を管理する必要がある。
【０００３】
特に三次元形状計測装置で得られた三次元形状データの場合、実測された三次元形状データがデータ削減処理によって近似値に変換されるので、最初のポリゴンモデルと近似化されたポリゴンモデルとの誤差管理は、実測された三次元形状データを基準に行うことが好ましい。
【０００４】
その一方、従来、三角形ポリゴンモデルにおいて、所望の許容誤差範囲内でモデルの近似化を図ることにより当該三角形ポリゴンモデルを構成する三次元形状データのデータ数を削減する方法が種々提案されている。
【０００５】
例えば論文「３次元ポリゴンモデルの階層的近似」（堀川，戸塚、Proceedings  of  the  5th  Sony  Research  Forum，pp3-7，1995）には、三角形ポリゴンモデルを構成する各エッジのモデル形状への寄与を当該エッジを除去した場合に変化する体積を表す評価関数で評価し、例えばエッジと周辺の面とが平行である場合や面が小さい場合やエッジが短い場合等の評価値が小さいエッジを除去することで、三次元形状データのデータ数を削減する方法が示されている。
【０００６】
また、論文「Simplification  Envelopes」(Cohen  Jonathan，Amitabh  Varshney，Dinesh  Manocha，Greg  Turk，Hans  Weber，Pankai  Agarwal，Frederick  Brooks  and  William  Wright．Proceedings  of  SIGGRAPH  96  In  Computer  Graphics  Proceedings，Annual  Conference  Series，1996，ACM  SIGGRAPH，pp．119-128）には、最初のポリゴンモデルを誤差εで縮小したモデルと誤差εで拡大したモデルとを作成し、最初のポリゴンモデルを近似化したポリゴンモデルが拡大／縮小した両モデルの間に入るように最初のポリゴンモデルのデータ数を削減する方法が示されている。
【０００７】
また、論文「Surface  Simplification  Using  Quadric  Error  Metrics」（Michael  Garland  and  Paul  S．Heckbert．Carnegie Mellon University  Proceedings  of  SIGGRAPH  97．1997）には、例えば三角形ポリゴンモデルのエッジ又は面を構成する２個以上の格子点（三次元形状データ）を１個の格子点（三次元形状データ）に集結することにより三角形ポリゴンモデルを構成する三次元形状データのデータ数を削減する方法として、エッジ収縮もしくは面収縮により集結される格子点とエッジ収縮もしくは面収縮により影響を受けた最初の三角形ポリゴンモデルを構成する各平面との距離の離れ具合をデータ削減処理における誤差として管理し、この誤差が所定の許容誤差範囲内であるエッジ収縮もしくは面収縮の処理のみを行うことで、所定の許容誤差範囲内でデータ数の削減を行う方法が示されている。
【０００８】
【発明が解決しようとする課題】
上記論文「３次元ポリゴンモデルの階層的近似」に示されるデータ削減方法は評価値によってエッジを除去するだけであるので、ポリゴンモデルの特徴的な部分の三次元データは残るものの、エッジ除去によるモデルの近似化における誤差を評価することはできない。従って、ＣＧ（Computer Graphics）におけるＶＲ（Virtual Reality）やゲーム等のように、単に三次元画像を表示するためにポリゴンモデルのデータ数を削減する場合には有効であるが、三次元形状計測装置で得られた計測データのように、最初の計測データとデータ削減後の近似モデルのデータとの誤差管理を必要とする場合には有効な方法となり得ない。
【０００９】
一方、上記論文「Simplification Envelopes」に示されるデータ削減方法は、厳密な誤差管理は可能であるが、データ削減処理の過程で誤差εで拡大及び縮小したポリゴンモデルを作成し、それらのポリゴンモデルのデータを保持する必要があるので、処理に関係するデータ数が膨大となり、メモリ容量やデータ削減のための演算処理の負担が大きいという問題がある。
【００１０】
また、上記論文「Surface Simplification Using Quadric Error Metrics」に示されるデータ削減方法は、最初のポリゴンモデルを構成する面に対する近似後のポリゴンモデルを構成する格子点の離れ具合を誤差として管理しているため、三次元形状計測装置の計測データのように最初のポリゴンモデルを構成する格子点に対して近似後のポリゴンモデルの誤差を管理してデータ削減を行いたい場合には必ずしも適切な方法とは言い難い。
【００１１】
また、三次元形状計測装置で測定対象物の粗い面や切削された面を測定して得られた計測データの場合、例えばポリゴンモデルにおいて局所的に面の向きがジグザグに急変するような場合、それらのジグザグな面に対する誤差を評価することになるので、データの削減が進むにつれて誤差が大きく評価され、データ削減が十分に行なわれないという問題がある。
【００１２】
本発明は、上記課題に鑑みてなされたものであり、三次元形状計測装置で得られた計測データに対して正確な誤差評価に基づき適正にデータ削減が可能な三次元形状データのデータ削減方法及びそのデータ削減方法を用いたデータ削減装置を提供するものである。
【００１３】
【課題を解決するための手段】
請求項１記載の発明は、２個以上の格子点を１個の格子点に集結してポリゴンモデルのエッジもしくは面を収縮することにより当該ポリゴンモデルを構成する複数の三次元座標データのデータ数を削減する三次元形状データのデータ削減方法であって、評価値算出手段が、上記ポリゴンモデルのエッジもしくは面を収縮することにより変形を受ける全ての面について、各面と各面の変形に関与した全ての最初の格子点との距離に基づく所定の評価値を算出する工程と、比較手段が、上記評価値を予め設定された許容値と比較する工程と、データ削減手段が、上記評価値が上記許容値以下であるとき、上記エッジもしくは面の収縮を行って上記三次元形状データの削減を行う工程とを備えるものである。
【００１４】
また、請求項３記載の発明は、２個以上の格子点を１個の格子点に集結してポリゴンモデルのエッジもしくは面を収縮することにより当該ポリゴンモデルを構成する複数の三次元座標データのデータ数を削減する三次元形状データのデータ削減装置であって、上記ポリゴンモデルのエッジもしくは面を収縮することにより変形を受ける全ての面について、各面と各面の変形に関与した全ての最初の格子点との距離に基づく所定の評価値を算出する評価値算出手段と、上記評価値を予め設定された許容値と比較する比較手段と、上記評価値が上記許容値以下であるとき、上記エッジもしくは面の収縮を行って上記三次元形状データの削減を行うデータ削減手段とを備えたものである。
【００１５】
上記構成によれば、ポリゴンモデルのエッジもしくは面を収縮することにより変形を受ける全ての面について、各面と各面の変形に関与した全ての最初の格子点との距離に基づく所定の評価値が算出され、この評価値は予め設定された許容値と比較される。そして、その評価値が許容値以下であるとき、そのエッジもしくは面の収縮を行ってポリゴンモデルを構成する三次元形状データが削減される。
【００１６】
なお、上記評価値は、下記（１）式で定義する誤差εとするとよい（請求項２，４）。
【００１７】
【数４】
0004192377.tif 000002
【００１８】
この構成によれば、ポリゴンモデルを構成するエッジもしくは面について、（１）式で定義される誤差εが当該エッジもしくは面の収縮の可否を判定する評価値として算出され、その誤差εが所定の許容値以下であるとき、当該エッジもしくは面を収縮させてポリゴンモデルを構成する格子点（三次元形状データ）が削減される。
【００１９】
ここに、（１）式における分母は、ポリゴンモデルを構成する面のうち、エッジ収縮もしくは面収縮により変形を受ける全ての面についての、当該面と当該面の変形に関与した最初の格子点との距離の２乗和を示し、（１）式の分子は、分母の距離の２乗和の項の総数を示している。従って、誤差εは、エッジ収縮もしくは面収縮により変形を受ける面が当該面の変形に関与した最初の格子点からどの程度離れているかを示す離れ具合（距離の２乗）の平均値を示している。
【００２０】
また、請求項５記載の発明は、請求項４記載の三次元形状のデータ削減装置において、上記評価値算出手段は、最初のポリゴンモデルを構成する全ての格子点ｖについてそれぞれ誤差行列Ｋｖを算出しておき、２個以上の格子点ｖp（ｐ＝１，２，…）を１の格子点ｖqに集結したときは、集結させた各格子点ｖpの誤差行列Ｋｖpの和をその格子点ｖqの誤差行列Ｋｖqとして上記（１）式により誤差εを算出するものである。
【００２１】
上記構成によれば、データ削減処理に際し、最初のポリゴンモデルを構成する全ての格子点ｖについてそれぞれ誤差行列Ｋｖが算出され、エッジ収縮処理もしくは面収縮処理により２個以上の格子点ｖp（ｐ＝１，２，…）が１の格子点ｖqに集結されたときは、次のエッジ収縮もしくは面収縮でこの格子点ｖqを集結させる際、格子点ｖqに集結させた各格子点ｖpの誤差行列Ｋｖpの和がその格子点ｖqの誤差行列Ｋｖq（＝ΣＫｖp）として算出され、この誤差行列Ｋｖqを用いて上記（１）式により誤差εが算出される。
【００２２】
集結後の格子点の誤差行列は、最初の格子点の誤差行列を加算することで算出されるので、演算が容易となる。また、最終的に各格子点について当該エッジ収縮もしくは面収縮で関係した最初の格子点の誤差行列の和を対応付けることで、誤差評価を行うことができる。
【００２３】
また、請求項６記載の発明は、請求項５記載の三次元形状のデータ削減装置において、上記評価値算出手段は、最初の格子点についてそれぞれ算出した誤差行列の対角元素とこの対角元素よりも上側の元素のみを記憶手段に記憶しておき、この記憶手段に記憶された対角元素とこの対角元素より上側の元素とを用いて誤差行列を復元し、この誤差行列を用いて上記（１）式により誤差εを算出するものである。
【００２４】
上記構成によれば、最初の格子点についてそれぞれ算出された誤差行列は対称行列となり、その誤差行列の対角元素とその対角元素の上側の元素が記憶されるので、メモリの低減に寄与する。
【００２５】
また、請求項７記載の発明は、請求項４記載の三次元形状のデータ削減装置において、上記評価値算出手段は、最初の格子点の三次元形状データの列ベクトルＶが下記（２）式で表されるとき、各面ｐi毎に算出される誤差行列ΣＫｖj（ｊ＝１，２，…ｍi）の右下隅の元素を加算することで上記（１）式の総数Σｍi（ｉ＝１，２，…ｎ）を算出するものである。
【００２６】
【数５】
0004192377.tif 000003
【００２７】
上記構成によれば、格子点ｖの三次元形状データの烈ベクトルＶが（２）式で表されるとき、この格子点ｖの誤差行列Ｋｖは下記（Ａ）式のようになり、右下隅の元素は常に「１」となる。従って、ΣＫｖjの総数は各誤差行列Ｋｖjの右下隅の元素の総和となるので、これを演算することで別途総和を演算する必要がない。
【００２８】
【数６】
0004192377.tif 000004
【００２９】
また、請求項８記載の発明は、請求項４記載の三次元形状データのデータ削減装置において、上記評価値算出手段は、上記格子点ｖjの誤差行列Ｋｖjに代えて重み付誤差行列ｗj・Ｋｖjを用いて上記（１）式により誤差εを算出するものである。
【００３０】
上記構成によれば、誤差εは、格子点ｖjの誤差行列Ｋｖjに代えて重み付誤差行列ｗj・Ｋｖjを用いて上記（１）式により算出される。
【００３１】
【発明の実施の形態】
図１は、本発明に係るデータ削減方法を適用した三次元形状計測データの処理システムのブロック構成図である。
【００３２】
同図に示す三次元形状計測データの処理システム（以下、形状データ処理システムという。）は、被測定物Ｇの三次元形状データを計測する三次元形状計測装置１、三次元形状計測装置１で計測された三次元形状データを記憶する外部記憶装置２、三次元形状計測装置１で計測された三次元形状データを本発明に係るデータ削減方法を用いて削減し、所定のデータ処理を行う形状データ処理装置３、形状データ処理装置３で処理された三次元形状データを記憶する外部記憶装置４、データ削減後の三次元形状データを用いて、例えばポリゴンモデル等の測定物Ｇの三次元形状画像を表示する表示装置５及び形状データ処理装置３で処理された三次元形状データが利用されるＣＡＤ／ＣＡＭ（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＋Ｄ  …（４）
で算出され、行列式でベクトル表記すると、下記（５）式のようになる。
【００６０】
【数７】
0004192377.tif 000005
【００６１】
従って、距離ｄの２乗は、下記（６）式のようになる。
【００６２】
【数８】
0004192377.tif 000006
【００６３】
上記（６）式は、１つの平面ｐとこの平面ｐに含まれない１個の点ｖとの距離ｄの２乗を示すものであるが、平面ｐに対して複数個の点ｖ1，ｖ2，…ｖmがある場合、これらの点ｖi（ｉ＝１，２，…ｍ）との距離の２乗和Δ（ｐ）は、下記（７）式のようになる。
【００６４】
【数９】
0004192377.tif 000007
【００６５】
本実施形態に係るデータ削減方法においては、例えばエッジ収縮によりデータ削減をする場合、あるエッジの収縮によって影響を受けるポリゴンモデルの平面がｎ枚あるとする場合、それらの平面の全てについて、各平面とその平面への近似化のためにデータ削減処理に関与した複数個の最初の格子点（元の三次元形状データ）との距離の離れ具合を評価するようにしているので、各平面毎に上記（７）式によって算出される距離の２乗和Δ（ｐ）を算出し、これらの総和をデータ削減処理に関与した全ての格子点の総数Ｍで除した、下記（８）式で示されるεを誤差の評価値としている。
【００６６】
【数１０】
0004192377.tif 000008
【００６７】
なお、上記（８）式において、Δ（ｐ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）は下記（９）式のようになる。
【００７４】
【数１１】
0004192377.tif 000009
【００７５】
このとき、例えば平面ｐ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」に示される評価値を採用している場合にも広く適用することができる。
【０１２６】
また、上記実施の形態では三次元形状計測装置１で計測された三次元計測データのデータ削減を例に説明したが、本発明はこれに限定されるものではなく、コンピュータグラフックス等で創作された三次元データについても広く適用することができる。
【０１２７】
【発明の効果】
以上説明したように、本発明によれば、２個以上の格子点を１個の格子点に集結してポリゴンモデルのエッジもしくは面を収縮することにより当該ポリゴンモデルを構成する複数の三次元形状データのデータ数を削減する三次元形状データのデータ削減方法であって、ポリゴンモデルのエッジもしくは面を収縮することにより変形を受ける全ての面について、各面と各面の変形に関与した全ての最初の格子点との距離に基づく所定の評価値を算出し、この評価値が所定の許容値以下であるとき、エッジ収縮もしくは面収縮により三次元形状データの削減を行うようにしたので、データ削減処理において、最初の三次元形状データからの近似誤差という直感的に理解し易い評価基準で誤差管理を行うことができる。
【０１２８】
また、例えばポリゴンモデルにおいて局所的に面の向きがジグザグに急変するような場合にも比較的正確に誤差を管理しつつ好適にデータ削減処理を行なうことができる。
【０１２９】
特に評価値を上記（１）式で定義する誤差εとしたので、最初の三次元形状データについて算出された誤差行列を保存しておくだけで、誤差εが容易に算出でき、高速処理が可能であるとともに、データ削減処理の演算に要するメモリの効率的な利用も可能となる。
【図面の簡単な説明】
【図１】本発明に係るデータ削減方法を適用した三次元形状計測データ処理システムの構成を示すブロック図である。
【図２】形状データ処理装置の構成を示すブロック図である。
【図３】データ削減によるポリゴンモデルの近似化の一例を示す図である。
【図４】エッジ収縮によるデータ削減方法の概念図である。
【図５】面収縮によるデータ削減方法の概念図である。
【図６】本実施形態に係るデータ削減方法に適用される評価値を説明するための図である。
【図７】三次元形状データのデータ削減処理の手順を示すフローチャートである。
【図８】ランダムなノイズのデータによってポリゴンモデルに不連続面が生じている部分のエッジ収縮を示す図である。
【図９】図８に示すデータ削減処理における本実施形態に係る誤差評価値と従来の誤差評価値との差異を説明するための図である。
【図１０】ジグザグな面を有するポリゴンモデルの当該ジグザグ面の収縮を示す図である。
【図１１】図１０に示すデータ削減処理における従来の誤差評価値を説明するための図である。
【図１２】図１０に示すデータ削減処理における本実施形態に係る誤差評価値を説明するための図である。
【図１３】三次元形状データのデータ削減処理手順の他の実施形態を示すフローチャートである。
【図１４】図１３に示す処理手順によるデータ削減プロセスの一例を説明するための図である。
【図１５】図１３に示すフローチャートの変形例を示す図である。
【符号の説明】
１  三次元形状計測装置
１０１  照明部
１０２  共焦点型光学系
１０３  受光部
１０４  ビームスプリッタ
１０５  演算部
１０６  測定テーブル
２，４  外部記憶装置
３  形状データ処理装置（データ削減装置）
３１  ポリゴン生成部
３２  データ削減部
３２１  評価値演算部（評価値算出手段）
３２２  評価値ソート部
３２３  エッジ／面収縮処理部（比較手段、データ削減手段）
３３  許容値入力部
３４  データ出力部
５  表示装置
６  外部処理装置
【図１】
0004192377.tif 000013
【図２】
0004192377.tif 000014
【図３】
0004192377.tif 000015
【図４】
0004192377.tif 000016
【図５】
0004192377.tif 000017
【図６】
0004192377.tif 000018
【図７】
0004192377.tif 000019
【図８】
0004192377.tif 000020
【図９】
0004192377.tif 000021
【図１０】
0004192377.tif 000022
【図１１】
0004192377.tif 000023
【図１２】
0004192377.tif 000024
【図１３】
0004192377.tif 000025
【図１４】
0004192377.tif 000026
【図１５】
0004192377.tif 000027