JP4151185B2 - Data reduction method and data reduction apparatus for three-dimensional shape data - Google Patents

Description

【００５０】
従って、距離ｄの２乗は、下記（４）式のようになる。
【００５１】
【数２】

【００５２】
上記（４）式は、１つの平面ｐとこの平面ｐに含まれない１個の点ｖとの距離ｄの２乗を示すものであるが、平面ｐに対して複数個の点ｖ₁，ｖ₂，…ｖ_mがある場合、これらの点ｖ_i（ｉ＝１，２，…ｍ）との距離の２乗和Δ（ｐ）は、下記（５）式のようになる。
【００５３】
【数３】

【００５４】
本実施形態に係るデータ削減方法においては、例えばエッジ収縮によりデータ削減をする場合、あるエッジの収縮によって影響を受けるポリゴンモデルの平面がｎ枚あるとする場合、それらの平面の全てについて、各平面とその平面への近似化のためにデータ削減処理に関与した複数個の最初の格子点（元の三次元形状データ）との距離の離れ具合を評価するようにしているので、各平面毎に上記（５）式によって算出される距離の２乗和Δ（ｐ）を算出し、これらの総和をデータ削減処理に関与した全ての格子点の総数Ｍで除した、下記（６）式で示されるεを誤差の評価値としている。
【００５５】
【数４】

【００５６】
なお、上記（６）式において、Δ（ｐ_i）は、ｉ番目の平面ｐ_iに対する当該平面ｐ_iの近似化に寄与した全ての最初の格子点との距離の２乗和であり、ｍ_iはその距離の２乗和における項数である。
【００５７】
また、上記（６）式の演算処理においては、行列Ｋｖ_iは上記（４）式で示したように対称行列となるので、最初の格子点ｖ_iについて算出される行列行列Ｋｖ_iは、対角元素とその対角元素より上側の元素とをメモリに記憶させるようにするとよい。このようにすれば、演算処理に必要なメモリ容量を低減することができる。また、上記（６）式の分子の各要素ｍ_iはｉ番目の近似面ｐ_iにおける距離の２乗和の項数であるが、行列Ｋｖの右下隅の元素は常に「１」であり、この距離の２乗和の演算結果における行列ΣＫｖの右下隅の元素はｍ_iとなるから、この元素の値を利用して上記（６）式の演算を行うようにするとよい。このようにすれば、改めて項数ｍ_iを算出する必要がなく、演算処理が容易となる。
【００５８】
なお、上記（５）式をある平面ｐに対する誤差の評価に適用した場合、当該平面ｐに至るエッジ収縮もしくは面収縮の処理過程で関与した最初の格子点ｖ_iが特定されると、それらの格子点ｖ_iの三次元形状データから得られる行列Ｋｖ_iを加算したΣＫｖ_iはそのエッジ収縮もしくは面収縮における誤差の程度が示すパラメータとなる。そこで、以下の説明ではこのΣＫｖ_iを誤差行列と呼ぶ。
【００５９】
次に、三次元形状データのデータ削減処理の手順について、図７のフローチャートを用いて説明する。
【００６０】
三次元形状計測装置１により取り込まれた測定対象物Ｇの三次元形状データは、形状データ処理装置３に入力され、まず、ポリゴン生成部３１で三角形のポリゴンモデルが生成される（＃１）。また、操作者により許容値入力部３３からエッジ収縮処理の可否を判定するための許容値が入力される（＃３）。
【００６１】
続いて、評価値演算部３２１で最初のポリゴンモデルの全エッジについてエッジ収縮した場合の評価値ε_j（ｊ＝１，２，…Ｎ，Ｎはエッジ総数）が上記（６）式により算出される（＃５）。例えば図４の例では、エッジＥｄ_1r（ｒ＝２〜５，９，１０）、Ｅｄ_2s（ｓ＝５，６，…９）、Ｅｄ_tt+1（ｔ＝３，４，…１０、但し、ｔ＋１＝１１はｔ＋１＝３とする。）についてエッジ収縮した場合の評価値ε_j（ｊ＝１，２，…１９）が算出される。
【００６２】
このとき、例えば格子点ｖ₁，ｖ₂を格子点ｖ₁’に集結してエッジＥｄ₁₂を収縮した場合、最初の面は全て変形し、格子点ｖ₁’とエッジ収縮に関係しない格子点ｖ₃〜ｖ₁₀とによって８枚の平面面ｐ₁，ｐ₂，…ｐ₁₀（以下、変形後の平面を近似面という。）が形成されるが、これらの近似面ｐ_k（ｋ＝１，２，…８）についてそれぞれ距離の２乗和Δ（ｐ_k）（ｋ＝１，２，…８）が算出されるとともに、これらの距離の２乗和Δ（ｐ_k）全体に含まれる要素の総数Ｍが算出され、上記（６）式によりエッジＥｄ₁₂の収縮処理における評価値ε（Ｅｄ₁₂）が算出される。なお、評価値ε（Ｅｄ₁₂）は下記（７）式のようになる。
【００６３】
【数５】

【００６４】
このとき、例えば平面ｐ₁は格子点ｖ₁’，ｖ₃，ｖ₄によって構成されるが、格子点ｖ₁，ｖ₂，ｖ₃，ｖ₄が実測データである場合はエッジ収縮に関与した格子点はｖ₁，ｖ₂だけであるから、距離の２乗和Δ（ｐ₁）はこれらの格子点ｖ₁，ｖ₂についての誤差行列（Ｋｖ₁＋Ｋｖ₂）を用いて上記（５）式により算出される。この状態で格子点ｖ₁’が更に他の格子点ｖ_m（図示しない実測データ）とともに格子点ｖ₁”（図示していない）に集結されて近似面ｐ₁が近似面ｐ₁’（図示していない）に近似された場合、この近似面ｐ₁’に至るエッジ収縮に関与した格子点はｖ₁，ｖ₂，ｖ_mとなるから、距離の２乗和Δ（ｐ₁’）はこれらの格子点ｖ₁，ｖ₂，ｖ_mについての誤差行列（Ｋｖ₁＋Ｋｖ₂＋Ｋｖ_m）を用いて上記（５）式により算出されることになる。
【００６５】
この２回目のエッジ収縮では、実質的に格子点ｖ₁’の誤差行列Ｋｖ₁’を（Ｋｖ₁＋Ｋｖ₂）として格子点ｖ₁’の誤差行列Ｋｖ₁’と格子点ｖ_mの誤差行列Ｋｖ_mとで上記（５）式により距離の２乗和Δ（ｐ₁’）を算出することになる。
【００６６】
従って、エッジ収縮処理の過程における一般論では、図４において、格子点ｖ₁，ｖ₂，ｖ₃，ｖ₄を実測データでなく、エッジ収縮によって生成されたデータであるとすれば、各格子点ｖ₁，ｖ₂，ｖ₃，ｖ₄に対する誤差行列をそれぞれＫｖ₁，Ｋｖ₂，Ｋｖ₃，Ｋｖ₄とすると、近似面ｐ₁を構成する格子点ｖ₁’に対する誤差行列Ｋｖ₁’をＫｖ₁’＝Ｋｖ₁＋Ｋｖ₂とし、近似面ｐ₁を構成する３個の格子点ｖ₁’，ｖ₃，ｖ₄の誤差行列Ｋｖ₁’，Ｋｖ₃，Ｋｖ₄を加算して得られる誤差行列Ｋ_p1（＝Ｋｖ₁’＋Ｋｖ₃＋Ｋｖ₄＝Ｋｖ₁＋Ｋｖ₂＋Ｋｖ₃＋Ｋｖ₄）を用いて上記（５）式により近似面ｐ₁について距離の２乗和Δ（ｐ₁）が算出される。
【００６７】
なお、距離の２乗和Δ（ｐ₁）の算出式は、
Δ（ｐ₁）＝Ｐ₁ ^T・Ｋ_p1・Ｐ₁ …（８）
となる。ここに、Ｐ₁は近似面ｐ₁の列ベクトル表記、ｍ₁は誤差行列Ｋ_p1に含まれる誤差行列Ｋｖの総数である。
【００６８】
そして、近似面ｐ₂，ｐ₃，…ｐ₈についても上述した近似面ｐ₁と同様の方法で距離の２乗和Δ（ｐ₂），Δ（ｐ₃），…Δ（ｐ₈）が算出され、これらを上記（７）式に代入してエッジＥｄ₁₂の収縮における誤差評価値ε（Ｅｄ₁₂）が算出される。
【００６９】
そして、同様の方法で他のエッジＥｄ_1r，Ｅｄ_2s、Ｅｄ_tt+1についてもエッジ収縮をした場合の誤差評価値ε（Ｅｄ_1r），ε（Ｅｄ_2s）、ε（Ｅｄ_tt+1）が算出される。
【００７０】
続いて、評価値ソート部３２２で誤差評価値ε_jのソーティングが行われ（＃７）、最小の評価値Ｍｉｎ｛ε_j｝がステップ＃３で入力された許容値以下であるか否かが判別される（＃９）。最小評価値Ｍｉｎ｛ε_j｝が許容値よりも大きければ（＃９でＮＯ）、全てのエッジについてエッジ収縮した場合の形状変化が許容できない程大きいので、エッジ収縮によるデータ削減処理を終了する。一方、最小評価値Ｍｉｎ｛ε_j｝が許容値以下であれば（＃９でＹＥＳ）、エッジ／面収縮処理部３２３でその最小評価値Ｍｉｎ｛ε_j｝に対応するエッジの収縮処理が行われる（＃１１）。例えば図４において、最小評価値Ｍｉｎ｛ε_j｝がε（Ｅｄ₁₂）であれば、同図に示すようにエッジＥｄ₁₂の収縮処理が行われる。
【００７１】
続いて、エッジ収縮後のポリゴンモデルについて当該エッジ収縮処理の影響を受けたエッジについて再度、誤差評価値ε_q（ｑ＝１，２，…）が算出された後（＃１３）、ステップ＃７に戻り、これらの誤差評価値ε_qのうち、最小の誤差評価値Ｍｉｎ｛ε_q｝が算出され、それに対応するエッジの収縮処理が行われる（＃７〜＃１１）。以下、１本ずつエッジ収縮処理を繰り返し（＃７〜＃１３のループ）、最小評価値Ｍｉｎ｛ε_q｝が許容値より大きくなった時点でデータ削減処理を終了する（＃９でＮＯ）。
【００７２】
従って、このようなデータ削減処理を行うことにより、データ削減後のポリゴンモデルは、最初のポリゴンモデルに対して最初の計測データに対する誤差評価値εが許容値以下となるように近似化される。
【００７３】
上記のように本実施の形態にかかるデータ削減方法では、エッジ収縮もしくは面収縮により近似化されるポリゴンモデルの面が最初の格子点（計測された三次元形状データ）に対してどの程度の離れ具合となるかを誤差の評価値としているので、直感的にも解り易い評価基準でデータ削減処理を行うことができる。
【００７４】
また、その評価値が所定の許容誤差範囲内となるようにデータ削減を行うようにしているので、近似後のポリゴンモデルを構成する三次元形状データの誤差を比較的正確に管理しつつデータ削減処理を高速に行うことができる。
【００７５】
特に、計測された三次元形状データにランダムなノイズのデータが混入した場合や多数の格子点を１点に集結してデータ削減を行う場合にも誤差評価値の信頼性の低下を抑えることができる。
【００７６】
図８及び図９は、計測された三次元形状データにランダムなノイズのデータが混入した場合の誤差評価方法を従来の誤差評価方法と比較したものである。
【００７７】
図８は、ランダムなノイズのデータによってポリゴンモデルに不連続面が生じている部分（断面で表示している。）のエッジ収縮を示す図である。同図に示すように、ポリゴンモデル表面の不連続な凸凹が大きく生じている部分の格子点ｖ₁，ｖ₂を略中心の格子点ｖ₁’に集結した場合、上記従来の論文「Surface Simplification Using Quadric Error Metrics」に示されるデータ削減方法では、図９に示すように格子点ｖ₁’から、例えば格子点ｖ₁，ｖ₄を含む面ｐ₁₄と格子点ｖ₂，ｖ₅を含む面ｐ₂₅への距離ｄ₁’，ｄ₂’を誤差評価の基礎としているので、感覚的な近似誤差に対して誤差評価値は小さい目に算出されるのに対し、本実施形態に係るデータ削減方法では、例えば格子点ｖ₁，ｖ₂からの格子点ｖ₁’，ｖ₄，ｖ₅を含む平面ｐ₄₅への距離ｄ₁，ｄ₂を誤差評価の基礎としているので、誤差評価値は感覚的な近似誤差に比較的合致し、小さい目に算出されることはない。
【００７８】
図１０、図１１及び図１２は、多数の格子点を１点に集結した場合の誤差評価方法を従来の誤差評価方法と比較したものである。
【００７９】
図１０は、８個の格子点ｖ₁，ｖ₂，…ｖ₈でジグザグな面（断面で表示している。）が形成されているポリゴンモデルの当該ジグザグ面の収縮を示す図である。同図に示すように、格子点ｖ₁，ｖ₂，…ｖ₆を格子点ｖ₇，ｖ₈の略中心の格子点ｖ₁’に集結した場合、上記従来の論文「Surface Simplification Using Quadric Error Metrics」に示されるデータ削減方法では、図１１に示すように格子点ｖ₁’から最初のポリゴンモデルのジクザグな各面ｐ₇₁，ｐ₁₂，ｐ₂₃，ｐ₃₄，ｐ₄₅，ｐ₅₆，ｐ₆₈への距離ｄ₁’，ｄ₂’，…ｄ₆’を誤差評価の基礎としているので、感覚的な近似誤差に対して誤差の評価値は大きい目に算出されるのに対し、本実施形態に係るデータ削減方法では、例えば各格子点ｖ₁，ｖ₂，…ｖ₆からの格子点ｖ₁’，ｖ₇，ｖ₈を含む平面ｐ₇₈への距離ｄ₁，ｄ₂，…ｄ₆を誤差評価の基礎としているので、誤差の評価値は感覚的な近似誤差に比較的合致し、大きい目に算出されることはない。
【００８０】
図１３は、三次元形状データのデータ削減処理手順の変形例を示すフローチャートである。
【００８１】
図７に示すデータ削減処理手順では、エッジ収縮処理を行う毎にそのエッジ収縮により影響を受けたエッジについて再度、評価値εを算出し、その評価値εに基づいて次のエッジ収縮処理を行うようにしていたが、図１３に示すデータ削減処理手順は、エッジ収縮により影響を受けたエッジについての評価値εの演算を行わず、それ以外のエッジについてエッジ収縮を行うようにしたものである。
【００８２】
具体的には、図１３に示すフローチャートは、図７において、ステップ＃１３の処理を「エッジ収縮により影響を受けたエッジの収縮を禁止する」処理のステップ＃１３’に変更し、ステップ＃９と「終了」の処理の間にステップ＃１５，＃１７の処理を追加したものである。
【００８３】
そこで、以下の説明ではフローチャートの共通部分については簡単に説明し、異なる部分について詳細に説明する。
【００８４】
三次元形状計測装置１により取り込まれた測定対象物Ｇの三次元形状データは、形状データ処理装置３に入力され、ポリゴン生成部３１で三角形のポリゴンモデルが生成される（＃１）。また、操作者により許容値入力部３３からエッジ収縮処理の可否を判定するための許容値が入力される（＃３）。
【００８５】
続いて、評価値演算部３２１でポリゴンモデルの全エッジについてエッジ収縮した場合の評価値ε_j（ｊ＝１，２，…Ｎ，Ｎはエッジ総数）が算出され（＃５）、評価値ソート部３２２で誤差評価値ε_jのソーティングが行われて最小の評価値Ｍｉｎ｛ε_j｝が算出される（＃７）。
【００８６】
続いて、最小評価値Ｍｉｎ｛ε_j｝がステップ＃３で許容値以下であるか否かが判別され（＃９）、最小評価値Ｍｉｎ｛ε_j｝が許容値以下であれば（＃９でＹＥＳ）、エッジ／面収縮処理部３２３でその最小評価値Ｍｉｎ｛ε_j｝に対応するエッジの収縮処理が行われる（＃１１）。
【００８７】
続いて、このエッジ収縮処理で影響を受けたエッジの収縮処理が禁止され（＃１３’）、ステップ＃７に戻る。この処理は、次のエッジ収縮処理を今回のエッジ収縮処理で影響を受けなかったエッジについて行うようにするためのものである。
【００８８】
ステップ＃７に戻ると、エッジ収縮が禁止されたエッジ以外のエッジに対する評価値ε_q（ｑ＝１，２，…Ｑ。但し、Ｑ＜Ｎ）についてソーティングが行われ、最小評価値Ｍｉｎ｛ε_q｝が算出される（＃７）。そして、最小評価値Ｍｉｎ｛ε_q｝が許容値以下であるか否かが判別され（＃９）、最小評価値Ｍｉｎ｛ε_q｝が許容値以下であれば（＃９でＹＥＳ）、エッジ／面収縮処理部３２３でその最小評価値Ｍｉｎ｛ε_q｝に対応するエッジの収縮処理が行われ（＃１１）、更にこのエッジ収縮処理で影響を受けたエッジの収縮処理が禁止され（＃１３’）、再度、ステップ＃７に戻る。
【００８９】
そして、以下、同様の処理を繰り返し、エッジ収縮処理を行う毎にそのエッジ収縮で影響を受けたエッジを除外しつつ次のエッジ処理処理が行なわれる（＃７，＃９，＃１１，＃１３’のルーブ）。
【００９０】
一方、上記エッジ収縮処理を繰り返す過程で、最小評価値Ｍｉｎ｛ε_q｝が許容値よりも大きいと（＃９でＮＯ）、エッジ収縮が禁止されたエッジがあるか否かが判別され（＃１５）、エッジ収縮が禁止されたエッジがあれば（＃１５でＹＥＳ）、それらのエッジについて再度、誤差評価値ε_r（ｒ＝１，２，…）が算出された後（＃１７）、ステップ＃７に戻り、これらの誤差評価値ε_rのうち、最小誤差評価値Ｍｉｎ｛ε_r｝が算出され、その最小誤差評価値Ｍｉｎ｛ε_r｝に対応するエッジの収縮処理が行われる（＃７，＃９，＃１１）。
【００９１】
そして、上記エッジ収縮処理を繰り返し、最小評価値Ｍｉｎ｛ε_q｝が許容値よりも大きくなるとともに、エッジ収縮が禁止されたエッジもなくなると（＃９，＃１５でＮＯ）、エッジ収縮によるデータ削減処理を終了する。
【００９２】
図１４は、図１３に示す処理手順によるデータ削減プロセスの一例を示す図である。
【００９３】
同図において、ポリゴンモデルＭ₀は最初のポリゴンモデルである。このポリゴンモデルＭ₀は２８個の格子点ｖ₁，ｖ₂，…ｖ₂₈を各行の個数が（３，４，５，４，５，４，３）個となるように５行に配列し、隣り合う格子点間を結んだものである。
【００９４】
エッジｅ１，ｅ２，ｅ３，ｅ４，ｅ５は、各エッジｅｉ（ｉ＝１，２，…５）を収縮させた場合、互いにその影響を受けない関係にあるから、説明の便宜上、図１３に示す処理手順によって順次、エッジ収縮されるものとして選択したものである。
【００９５】
従って、図１４のデータ削減プロセスは、図１３の処理手順によってポリゴンモデルＭ₀がエッジｅ１，ｅ２，…ｅ５の順に順次、エッジ収縮される場合を示している。そして、ポリゴンモデルＭ₁，Ｍ₂，Ｍ₃，Ｍ₄，Ｍ₅は、ポリゴンモデルＭ₀をエッジｅ１，ｅ２，…ｅ５の順に収縮処理したときの近似化されたポリゴンモデルである。
【００９６】
上述した図１３に示すデータ削減処理手順によれば、まず、最初のエッジ収縮処理でエッジｅ１が収縮されてポリゴンモデルＭ₁に近似化されると、集結された格子点ｖ_aとその周囲に配置される格子点ｖ₉，ｖ₁₀，ｖ₁₁，ｖ₁₃，ｖ₁₆，ｖ₁₈，ｖ₁₉，ｖ₂₀（ポリゴンモデルＭ₁の点線枠内の格子点）とで形成されるエッジが影響を受けることになるため、次のエッジ収縮処理では、これらのエッジを除外したエッジ（ポリゴンモデルＭ₁の点線枠の外にあるエッジ）について再度、評価値ε_qのソーティングが行なわれ、最小評価値Ｍｉｎ｛ε_q｝を有するエッジｅ２についてエッジ収縮処理が行われてポリゴンモデルＭ₂に近似化される。
【００９７】
更に、次のエッジ収縮処理では、集結された格子点ｖ_bとその周囲に配置される格子点ｖ₁，ｖ₂，ｖ₄，ｖ₆，ｖ₈，ｖ₁₀，ｖ₁₃，ｖ_a（ポリゴンモデルＭ₂の点線枠内の格子点）とで形成されるエッジが影響を受けることになるため、これらのエッジを除外したエッジ（ポリゴンモデルＭ₂の点線枠の外にあるエッジ）について再度、評価値ε_sのソーティングが行なわれ、最小評価値Ｍｉｎ｛ε_s｝を有するエッジｅ３についてエッジ収縮処理が行われてポリゴンモデルＭ₃に近似化される。
【００９８】
そして、以下同様の方法でエッジｅ４，ｅ５についてもエッジ収縮が行なわれ、この５回のエッジ収縮処理により最初のポリゴンモデルＭ₀はポリゴンモデルＭ₅に近似化され、データ数は５個削減される。
【００９９】
最初のポリゴンモデルＭ₀を６枚目のポリゴンモデルＭ₆（図示せず。）まで近似化するプロセスを考えると、図１３に示す処理手順ではエッジ収縮によって影響を受けたエッジについては評価値の再計算をしないので、図１４の例では、最初のポリゴンモデルＭ₀を構成する６６本のエッジについて最初に評価値が計算されると、近似化されたポリゴンモデルＭ₁〜Ｍ₄については評価値の再計算は行なわれず、次の再計算はポリゴンモデルＭ₅を構成する５０本のエッジについて行なわれることになる。従って、６枚目のポリゴンモデルＭ₆までの評価値の再計算回数は５０回となる。
【０１００】
一方、図７に示す処理手順ではエッジ収縮によって影響を受けたエッジについて評価値の再計算を行っているので、近似化された各ポリゴンモデルＭ₁〜Ｍ₅毎にエッジ収縮によって影響を受ける１６本のエッジについて評価値の再計算をすることになる。従って、図７に示す処理手順では、６枚目のポリゴンモデルＭ₆までの評価値の再計算回数は１６×５＝８０回となり、図１３に示す処理手順の方が評価値の再計算回数が少なくなり、高速処理が可能になるという利点がある。
【０１０１】
図１５は、図１３に示すフローチャートの変形例である。
【０１０２】
図１５に示すフローチャートは、エッジ収縮後に影響を受けたエッジの評価値を許容値よりも大きい所定の評価値ε_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」に示される評価値を採用している場合にも広く適用することができる。
【０１１５】
また、上記実施の形態では三次元形状計測装置１で計測された三次元計測データのデータ削減を例に説明したが、本発明はこれに限定されるものではなく、コンピュータグラフックス等で創作された三次元データについても広く適用することができる。
【０１１６】
【発明の効果】
以上説明したように、本発明によれば、ポリゴンモデルにおける２個以上の格子点を１個の格子点に集結させる対象となる複数の部分に対して当該集結によって生じる誤差を評価する評価値をそれぞれ算出し、これらの評価値に基づき格子点の集結対象部分のデータ削減を行なう処理を繰り返すことでポリゴンモデルを構成する三次元形状データのデータ数を順次、削減する三次元形状データのデータ削減方法であって、格子点の集結処理が行なわれると、当該格子点の集結処理により影響を受けた格子点の集結対象部分のデータ削減処理を禁止するようにしたので、格子点の集結対象部分の評価値の再計算回数が低減され、データ削減処理の高速化が可能となる。
【０１１７】
また、データ削減により影響を受けた格子点の集結対象部分の評価値を所定の値に変更して次のデータ削減処理では集結対象外となるようにしたので、当該格子点の集結対象部分のデータ削減処理を簡単に禁止させることができる。
【０１１８】
また、所定の条件が満たされると、禁止された格子点の集結対象部分のデータ削減処理の禁止を解除するようにしたので、許容範囲内で可能な限り効率良くデータ削減を行うことができる。
【図面の簡単な説明】
【図１】本発明に係るデータ削減方法を適用した三次元形状計測データ処理システムの構成を示すブロック図である。
【図２】形状データ処理装置の構成を示すブロック図である。
【図３】データ削減によるポリゴンモデルの近似化の一例を示す図である。
【図４】エッジ収縮によるデータ削減方法の概念図である。
【図５】面収縮によるデータ削減方法の概念図である。
【図６】本実施形態に係るデータ削減方法に適用される評価値を説明するための図である。
【図７】三次元形状データのデータ削減処理の手順を示すフローチャートである。
【図８】ランダムなノイズのデータによってポリゴンモデルに不連続面が生じている部分のエッジ収縮を示す図である。
【図９】図８に示すデータ削減処理における本実施形態に係る誤差評価値と従来の誤差評価値との差異を説明するための図である。
【図１０】ジグザグな面を有するポリゴンモデルの当該ジグザグ面の収縮を示す図である。
【図１１】図１０に示すデータ削減処理における従来の誤差評価値を説明するための図である。
【図１２】図１０に示すデータ削減処理における本実施形態に係る誤差評価値を説明するための図である。
【図１３】三次元形状データのデータ削減処理手順の他の実施形態を示すフローチャートである。
【図１４】図１３に示す処理手順によるデータ削減プロセスの一例を説明するための図である。
【図１５】図１３に示すフローチャートの変形例を示す図である。
【符号の説明】
１ 三次元形状計測装置
１０１ 照明部
１０２ 共焦点型光学系
１０３ 受光部
１０４ ビームスプリッタ
１０５ 演算部
１０６ 測定テーブル
２，４ 外部記憶装置
３ 形状データ処理装置（データ削減装置）
３１ ポリゴン生成部
３２ データ削減部
３２１ 評価値演算部（評価値算出手段，禁止手段，解除手段）
３２２ 評価値ソート部
３２３ エッジ／面収縮処理部（判定手段、データ削減手段）
３３ 許容値入力部
３４ データ出力部
５ 表示装置
６ 外部処理装置[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a data reduction method for three-dimensional shape data constituting a polygon model and a data reduction device using the method.
[0002]
[Prior art]
For example, measurement data with high drawing quality obtained with a three-dimensional shape measurement device with extremely high spatial resolution has a huge number of data, so if it has more than necessary drawing quality, the burden on the storage device in the subsequent processing And the processing speed is significantly reduced. For this reason, it is necessary to reduce the number of measurement data to reduce the above problem as much as possible.
[0003]
Conventionally, various methods have been proposed for reducing the number of three-dimensional shape data constituting the triangular polygon model by approximating the model within a desired tolerance range in the triangular polygon model.
[0004]
For example, in the paper “Surface Simplification Using Quadric Error Metrics” (Michael Garland and Paul S. Heckbert, Carnegie Mellon University Proceedings of SIGGRAPH 97. 1997) As a method of reducing the number of data of 3D shape data constituting a triangular polygon model by consolidating original shape data) into one lattice point (3D shape data), a lattice that is gathered by edge contraction or surface contraction The distance between each point and the planes that make up the first triangular polygon model affected by edge contraction or surface contraction is managed as an error in the data reduction process, and this error is within the specified allowable error range. A method of reducing the number of data within a predetermined tolerance range by performing only shrinkage or surface shrinkage processing It is shown.
[0005]
In such a polygon model edge or surface contraction method, for example, if one edge is contracted, the peripheral edge and the surface change due to the contraction of the edge. After the error is recalculated again for the edge affected by the edge contraction constituting the polygon model after contraction, one edge is determined using the error after the recalculation, and the edge is contracted. It is. By repeating this process, the number of three-dimensional shape data is reduced within a predetermined allowable error range.
[0006]
[Problems to be solved by the invention]
In the data reduction method in which the periphery of the contracted portion is affected each time contraction processing is performed, such as the conventional edge contraction or surface contraction, the polygon model after contraction is configured every time one edge contraction or surface contraction is performed. Since the error needs to be recalculated for the edge or surface affected by the edge contraction, there is a problem that the number of calculations is large and the speed of the data reduction process is reduced.
[0007]
The present invention has been made in view of the above problems, and provides a data reduction method for three-dimensional shape data capable of high-speed processing and a data reduction device using the data reduction method.
[0008]
[Means for Solving the Problems]
  The invention according to claim 1 is caused by aggregating a plurality of parts to be aggregated into two or more grid points in a polygon model.Polygon model after data reduction with respect to polygon model composed of measured shape dataCalculates evaluation values for evaluating errorsAnd the process,theseA step of determining a collection target portion of the lattice points to be subjected to data reduction based on the evaluation value, and a step of performing data reduction processing of the collection target portion of the lattice points determined by the determination means, Calculate the evaluation value of the target areaA data reduction method for three-dimensional shape data that sequentially reduces the number of data of the three-dimensional shape data constituting the polygon model by repeatedly performing data reduction of a collection target portion of the lattice points based on an evaluation value, When grid point concentration processing is performed, data reduction processing is prohibited for the lattice point concentration target area affected by the grid point concentration processing.Including processesIt is.
[0009]
  Further, the invention according to claim 5 is caused by the aggregation of a plurality of parts to be aggregated into two or more grid points in the polygon model.Polygon model after data reduction with respect to polygon model composed of measured shape dataAn evaluation value calculating means for calculating an evaluation value for evaluating an error; a determining means for determining a collection target portion of the lattice points to be subjected to data reduction based on the evaluation value; and a lattice point determined by the determining means A data reduction means for performing data reduction processing of the collection target portion, calculating an evaluation value of the collection target portion of the grid point, and repeatedly reducing data of the collection target portion of the grid point based on the evaluation value A data reduction apparatus for three-dimensional shape data that reduces the number of data of three-dimensional shape data constituting the polygon model, and when the data reduction processing of the lattice point concentration target portion is performed, the lattice point concentration processing And a prohibiting means for prohibiting the data reduction processing of the collection target portion of the grid points affected by the above.
[0010]
According to the data reduction method or the data reduction device, an evaluation value for evaluating an error caused by the aggregation of a plurality of portions to be aggregated into two or more grid points in the polygon model. Each data is calculated, and based on these evaluation values, data reduction processing is performed on the collection target portion of one grid point. By repeating this process, the number of three-dimensional shape data constituting the polygon model is sequentially reduced.
[0011]
In this case, when the data reduction processing is performed, the subsequent data reduction processing is prohibited for the lattice point concentration target portion affected by the data reduction processing, and the lattice point concentration target portion that has not been affected is already calculated. The following data reduction is performed based on the evaluated value. Since the recalculation of the evaluation value is not repeated for the clustered points affected by the data reduction process, the number of calculations is reduced accordingly.
[0012]
  In addition, when a predetermined condition set in advance is satisfied, the data reduction processing of the portion to be aggregated of the prohibited grid points is performedProhibitionIs preferably canceled (claims 2 and 7). For example, when there are no more grid points to be collected based on the evaluation value or when the data reduction process is repeated a predetermined number of times, the data reduction process for the prohibited grid points to be collected is repeated.ProhibitionIs preferably canceled (Claims 3, 4, 8, and 9).
[0013]
  According to this configuration, for example, it is prohibited when a predetermined condition is satisfied, for example, when there is no collection target portion of the grid points that can reduce data based on the evaluation value, or when the data reduction process is repeated a predetermined number of times. Data reduction processing for gathered grid pointsProhibitionIs released.
[0014]
Therefore, for example, when a predetermined condition is when the grid point concentration target part is eliminated, the affected grid point collection target part is excluded from the next edge contraction target every time the edge contraction is performed. When the collection target portion disappears, the evaluation values are recalculated for the collection target portions of all grid points, and data reduction processing is performed on the collection target portion of one grid point based on these evaluation values. By repeating this process, the number of three-dimensional shape data constituting the polygon model is sequentially reduced.
[0015]
According to a sixth aspect of the present invention, in the data reduction apparatus for three-dimensional shape data according to the fifth aspect of the invention, the prohibiting means is a collection target of grid points affected by the collection process of the grid points by the determination means. The evaluation value of the collection target portion of the grid point is temporarily changed to a predetermined value so that the portion is determined not to be subject to data reduction processing.
[0016]
According to the above configuration, when the edge contraction process is performed, the evaluation value of the collection target portion of the lattice point affected by the edge contraction is replaced with a predetermined value. Thereafter, when the target of the edge contraction process is determined based on all the evaluation values, the collection target part of the lattice points affected by the edge contraction is determined to be excluded from the data reduction process. Edge contraction processing is prohibited.
[0017]
A tenth aspect of the present invention is the data reduction device for three-dimensional shape data according to any one of the fifth to seventh aspects, wherein the determination means includes a minimum evaluation value calculation means for calculating a minimum evaluation value, and the minimum And a comparison means for comparing the evaluation value with a predetermined allowable value set in advance, and when the minimum evaluation value is equal to or less than the allowable value, data collection is reduced for a gathered portion of lattice points having the minimum evaluation value It is determined to be a part.
[0018]
According to the above configuration, the minimum value is calculated from the evaluation values calculated for the collection target portion of the grid point, and if the minimum value is equal to or less than a predetermined allowable value, the grid points having the minimum evaluation value are combined. Data reduction processing for the target portion is performed.
[0019]
In the data reduction apparatus for three-dimensional shape data, the collection target of the lattice points may be an edge or a surface of a triangular polygon model.
[0020]
DETAILED DESCRIPTION OF THE INVENTION
FIG. 1 is a block diagram of a three-dimensional shape measurement data processing system to which a data reduction method according to the present invention is applied.
[0021]
The three-dimensional shape measurement data processing system (hereinafter referred to as a shape data processing system) shown in FIG. 1 is a three-dimensional shape measurement device 1 that measures three-dimensional shape data of an object G to be measured. A shape for performing predetermined data processing by reducing the three-dimensional shape data measured by the external storage device 2 for storing the measured three-dimensional shape data and the three-dimensional shape measuring device 1 using the data reduction method according to the present invention. The data processing device 3, the external storage device 4 for storing the three-dimensional shape data processed by the shape data processing device 3, and the three-dimensional shape of the measuring object G such as a polygon model using the three-dimensional shape data after the data reduction External such as CAD / CAM (computer aided design and computer aided manufacturing) in which the display device 5 for displaying images and the three-dimensional shape data processed by the shape data processing device 3 are used. And a management device 6.
[0022]
The three-dimensional shape measuring apparatus 1 measures the surface shape of the measuring object G using a conjugate autofocus system. As shown in FIG. 2, the three-dimensional shape measuring apparatus 1 illuminates the measurement object G with the illumination unit 101 that generates illumination light and the illumination light reflected by the measurement object G. The confocal optical system 102 that guides the light to the light receiving unit 103; the light receiving unit 103 that receives the illumination light reflected from the measurement object G, photoelectrically converts it into an electrical signal, and outputs the electrical signal; The position of the surface of the measuring object G is measured using the beam splitter 104 that splits the reflected light from the measuring object G that has passed through the system 102 and guides it to the light receiving unit 103 and the light reception signal output from the light receiving unit 103. It has a basic configuration including a calculation unit 105 that calculates coordinates.
[0023]
The three-dimensional shape of the measurement object G is placed on the measurement table 106 arranged in front of the three-dimensional shape apparatus 1 and moved up and down at a predetermined pitch in the height direction. This is done by measuring the unevenness of the surface of the measuring object G at each height position. That is, assuming that the height direction of the measurement object G is the Y direction, the optical axis direction of the optical system 102 is the Z direction, and the direction perpendicular to the Y direction and the Z direction is the X direction, the Y coordinate of the measurement object G is a predetermined value. The three-dimensional shape of the measuring object G is measured by measuring the Z coordinate of the measuring object G at each Y coordinate position while changing the pitch. Then, the three-dimensional shape data (x, y, z) of the measuring object G measured by the three-dimensional shape measuring device 1 is input to the shape data processing device 3.
[0024]
The three-dimensional measuring apparatus 1 includes a photoelectric conversion element 103a composed of a line sensor arranged in parallel with the X axis, and the light reception signal for each pixel of the photoelectric conversion element 103a (each pixel position corresponds to an X coordinate). Is used to measure the position coordinate (Z coordinate) of the surface of the measuring object G. For this reason, slit-like illumination light extending in the X direction is emitted from the illumination unit 101 so that the reflected light from the measurement object G is incident on the entire photoelectric conversion element 103a.
[0025]
The Z coordinate of the measuring object G is measured as follows. First, slit-like illumination light extending in the X direction is emitted from the illumination unit 101 disposed at the focal position on the image side of the optical system 102. The illumination light is condensed at a focal position on the object side of the optical system 102, and line light extending in the X direction is formed at the focal position. Next, in this state, the focal position (that is, the line light) on the object side of the optical system 102 is moved in the optical axis direction until the focal position reaches the inside of the measurement object G, and the photoelectric conversion element with a predetermined cycle. The exposure of 103a is repeated. Then, using the level of the light reception signal received at each exposure position, the calculation unit 105 calculates the exposure position at the maximum level for each pixel of the photoelectric change element 103a, and the position is calculated on the surface of the measurement object G. The Z coordinate is used.
[0026]
The shape data processing device 3 includes a polygon generation unit 31, a data reduction unit 32, an allowable value input unit 33, and a data output unit 34. The polygon generation unit 31 generates a polygon model of the measurement target G based on the three-dimensional shape data (x, y, z) of the measurement target G input from the three-dimensional shape measurement apparatus 1. The data reduction unit 32 reduces the three-dimensional shape data by edge contraction or surface contraction of the polygon model. That is, as shown in FIG. 3, the lattice points (three-dimensional shape data) of the polygon model A are appropriately set so that the precise polygon model A based on the measurement data is approximated to the polygon model B within a predetermined allowable error range. It will be reduced.
[0027]
The data reduction unit 32 includes an evaluation value calculation unit 321, an evaluation value sorting unit 322, and an edge / surface contraction processing unit 323 in order to execute data reduction processing described later.
[0028]
The evaluation value calculator 321 collects two or more lattice points and replaces the lattice points with one lattice point to contract the edges or faces constituting the polygon model (that is, to approximate the polygon model). The evaluation value for determining whether or not each edge or each surface can be contracted is calculated. This evaluation value will be described later.
[0029]
The evaluation value sorting unit 322 calculates a minimum evaluation value by rearranging a plurality of evaluation values calculated for each edge or each surface by the evaluation value calculation unit 321 in ascending order or descending order. The edge / surface contraction processing unit 323 compares the minimum evaluation value calculated by the evaluation value sorting unit 322 with the allowable value input from the allowable value input unit 33, and corresponds to the minimum evaluation value when it is equal to or smaller than the allowable value. Edge or surface contraction processing is performed. The evaluation value and the edge contraction method will be described later.
[0030]
The allowable value input unit 33 is for the operator to input an allowable value for determining whether or not edge contraction or surface contraction is possible as described above. This allowable value corresponds to an allowable range in which even if edge contraction or surface contraction is performed when approximating the polygon model, it is assumed that the influence on the characteristic part of the polygon model is small. Input accordingly.
[0031]
The data output unit 34 is an interface for outputting the reduced three-dimensional shape data (three-dimensional shape data constituting the approximated polygon model) to the external storage device 4, the display device 5, and the external processing device 6.
[0032]
The external storage device 4 records data on an external recording medium such as a magnetic disk, an optical disk, or a magnetic optical disk. When the three-dimensional shape data is input from the shape data processing apparatus 3, the external storage device 4 is stored in a predetermined file format on the external recording medium. Record.
[0033]
The display device 5 is a display device including an electronic display device such as a cathode ray tube or a liquid crystal display device. When the three-dimensional shape data is input from the shape data processing device 3 to the display device 5, an image of the polygon model of the measuring object G approximated based on the data is displayed (polygon model B in FIG. 3 is displayed). reference).
[0034]
The external processing device 6 is a device that manufactures a mold or a model having a shape substantially the same as the surface shape of the measurement object G, for example. When the three-dimensional shape data is input from the shape data processing device 3 to the external processing device 6, the workpiece is cut based on the three-dimensional shape data, and a die or the like is automatically manufactured.
[0035]
Next, the data reduction method according to the present invention will be described.
[0036]
FIG. 4 is a conceptual diagram of a data reduction method by edge contraction. FIG. 5 is a conceptual diagram of a data reduction method by surface contraction.
[0037]
As shown in FIG. 4, the data reduction method by edge contraction uses a polygon model with lattice points v₁~ V_TenFor example, the grid point v₁And lattice point v₂Edge Ed connecting₁₂Both grid points v so that₁, V₂Is the lattice point v₁It is a method of reducing the number of data by collecting together.
[0038]
In the data reduction method by edge contraction (hereinafter abbreviated as the edge contraction method), first, all edges Ed_ij(I, j = 1, 2,... 10, where i ≠ j and the lattice points are adjacent to each other) An evaluation value for evaluating the influence on the shape change of the polygon model due to edge contraction is calculated. When the evaluation value is less than or equal to the allowable value, the edge Ed corresponding to the evaluation value_ijLattice points v at both ends of_i, V_jTo a predetermined grid point v_iData is reduced by concentrating on '.
[0039]
Next, lattice point v_i, V_jIs the lattice point v_iThe polygon models (approximate polygon models) gathered at ′ are subjected to edge contraction by the same method, and further data reduction is performed. Thereafter, the polygon model after the edge contraction is subjected to edge contraction one by one until the edge contraction cannot be performed in the same manner (that is, the approximation of the polygon model is repeated until the minimum evaluation value becomes larger than the allowable value). ), Data reduction is performed.
[0040]
In addition, lattice point v_i′ Is, for example, the edge Ed as shown in the above-mentioned paper “Hierarchical approximation of the three-dimensional polygon model”._ijGrid point v such as midpoint_i, V_jIt is an approximate point set at an appropriate position between.
[0041]
As shown in FIG. 5, a data reduction method using surface contraction (hereinafter abbreviated as “surface contraction method”) uses a polygon model with lattice points v.₁~ V₁₁For example, the grid point v₁, Lattice point v₂And lattice point v_ThreeSurface P surrounded by_{one two Three}To remove the grid point v₁, V₂, V_ThreeIs the lattice point v₁It is a method of reducing the number of data by collecting together.
[0042]
The data reduction method by the surface contraction is basically performed in the same procedure as the data reduction method by the edge contraction. That is, first, all surfaces P_ijk(I, j, k = 1, 2,... 10, where i ≠ j ≠ k and the lattice points are adjacent to each other) An evaluation value for evaluating the influence of the surface contraction on the shape change of the polygon model is calculated. If the minimum evaluation value is less than or equal to the allowable value, the surface P corresponding to the evaluation value_ijkLattice points v constituting_i, V_j, V_kTo a predetermined grid point v_iThe data is reduced by concentrating on ', and the data is reduced by performing surface contraction one by one until the surface of the polygon model after the surface contraction can no longer be contracted by the same method.
[0043]
When the three-dimensional shape data is sequentially reduced by the edge contraction method or the surface contraction method, the three-dimensional shape data constituting the measurement object G after the data reduction processing is the data of the measurement object G actually measured by the three-dimensional shape measurement apparatus 1. Unlike three-dimensional shape data, approximate three-dimensional shape data is obtained. For this reason, the error of the polygon model (hereinafter referred to as an approximated polygon model) after data reduction with respect to a polygon model (hereinafter referred to as the first polygon model) composed of actually measured three-dimensional shape data is managed. However, it is necessary to perform data reduction processing.
[0044]
In the data reduction method according to the present embodiment, for example, edge contraction is repeated, and for example, as shown in FIG. 6, lattice points a, b, c (actually measured three-dimensional shape data) are converted into lattice points a ′, b ′, c ′ and the triangular polygon P_abcIs a triangular polygon P_abcIf approximated to ′, triangular polygon P after approximation_abcThe degree to which the surface including 'is away from the first lattice points a, b, c involved in the approximation processing of this surface is managed as an error.
[0045]
In the example of FIG. 6, for convenience of explanation, the lattice points involved in the approximation process are set as the lattice points a, b, and c. Since grid points (actual measurement data) other than the grid point a are included in the process, the above-described error includes these grid points and the triangular polygon P._abcThe distance from 'is also included.
[0046]
Next, an error evaluation value applied to the data reduction method according to the present embodiment will be described.
[0047]
In general, the plane p in the three-dimensional space is
A.x + B.y + C.z + D = 0 (1)
However, A²+ B²+ C²= 1
It is expressed by the equation
[0048]
On the other hand, the coordinates of the point v in the three-dimensional space are (v_x, V_y, V_z), The distance d between the point v and the plane p is
d = A · v_x+ B ・ v_y+ C ・ v_z+ D (2)
And expressed as a vector using a determinant, the following equation (3) is obtained.
[0049]
[Expression 1]

[0050]
Therefore, the square of the distance d is expressed by the following equation (4).
[0051]
[Expression 2]

[0052]
The above equation (4) indicates the square of the distance d between one plane p and one point v not included in this plane p.₁, V₂, ... v_mIf there are these points v_iThe sum of squares Δ (p) of the distance to (i = 1, 2,... M) is expressed by the following equation (5).
[0053]
[Equation 3]

[0054]
In the data reduction method according to the present embodiment, for example, when data reduction is performed by edge contraction, and there are n polygon model planes that are affected by contraction of a certain edge, each plane is defined for all of those planes. Since the distance between the first grid point (original 3D shape data) involved in the data reduction process is evaluated for approximation to the plane, it is evaluated for each plane. The distance square sum Δ (p) calculated by the above equation (5) is calculated, and the sum is divided by the total number M of all grid points involved in the data reduction process, and is expressed by the following equation (6). Ε is an error evaluation value.
[0055]
[Expression 4]

[0056]
In the above equation (6), Δ (p_i) Is the i-th plane p_iThe plane p for_iIs the sum of squares of the distances to all the first grid points that contributed to the approximation of m,_iIs the number of terms in the sum of squares of the distance.
[0057]
In the calculation process of the above equation (6), the matrix Kv_iIs a symmetric matrix as shown in equation (4) above, so the first lattice point v_iMatrix matrix Kv calculated for_iThe diagonal element and the element above the diagonal element may be stored in the memory. In this way, it is possible to reduce the memory capacity required for the arithmetic processing. In addition, each element m of the numerator of the above formula (6)_iIs the i-th approximate surface p_iThe element at the lower right corner of the matrix Kv is always “1”, and the element at the lower right corner of the matrix ΣKv in the calculation result of the square sum of the distance is m._iTherefore, it is preferable to perform the calculation of the above formula (6) using the value of this element. In this way, the number of terms anew_iNeed not be calculated, and the arithmetic processing becomes easy.
[0058]
When the above equation (5) is applied to the error evaluation for a certain plane p, the first lattice point v involved in the process of edge contraction or surface contraction to the plane p is applied._iAre specified, their grid points v_iMatrix Kv obtained from 3D shape data_iΣKv plus_iIs a parameter indicated by the degree of error in edge shrinkage or surface shrinkage. Therefore, in the following explanation, this ΣKv_iIs called an error matrix.
[0059]
Next, the procedure of the data reduction process of 3D shape data will be described using the flowchart of FIG.
[0060]
The three-dimensional shape data of the measurement object G taken in by the three-dimensional shape measurement apparatus 1 is input to the shape data processing apparatus 3, and first, a polygon model of a triangle is generated by the polygon generation unit 31 (# 1). Further, an allowable value for determining whether or not the edge contraction process is possible is input from the allowable value input unit 33 by the operator (# 3).
[0061]
Subsequently, the evaluation value ε when the edge contraction is performed on all edges of the first polygon model in the evaluation value calculation unit 321._j(J = 1, 2,... N, N is the total number of edges) is calculated by the above equation (6) (# 5). For example, in the example of FIG._1r(R = 2 to 5, 9, 10), Ed_2s(S = 5, 6, ... 9), Ed_{tt + 1}(T = 3, 4,..., Where t + 1 = 11 is t + 1 = 3)_j(J = 1, 2,... 19) is calculated.
[0062]
At this time, for example, the lattice point v₁, V₂Is the lattice point v₁Gather at the edge Ed₁₂, The first surface is all deformed and the grid point v₁'And lattice point v not related to edge contraction_Three~ V_TenAnd 8 plane surfaces p₁, P₂, ... p_Ten(Hereinafter, the plane after deformation is referred to as an approximate surface.) These approximate surfaces p are formed._k(K = 1, 2,... 8), the square sum of distances Δ (p_k) (K = 1, 2,..., 8) and the sum of squares Δ (p_k) The total number M of elements included in the whole is calculated, and the edge Ed is calculated by the above equation (6).₁₂Evaluation value ε (Ed₁₂) Is calculated. The evaluation value ε (Ed₁₂) Is expressed by the following equation (7).
[0063]
[Equation 5]

[0064]
At this time, for example, the plane p₁Is the grid point v₁', V_Three, V_Four, But the grid point v₁, V₂, V_Three, V_FourIs the measured data, the grid point involved in edge contraction is v₁, V₂Only the sum of squared distances Δ (p₁) Are these grid points v₁, V₂Error matrix (Kv₁+ Kv₂) Using the above equation (5). In this state, lattice point v₁′ Is another lattice point v_m(Measurement data not shown) and lattice point v₁”(Not shown) gathered to approximate surface p₁Is the approximate surface p₁When approximated to ′ (not shown), this approximate surface p₁The lattice points involved in the edge contraction to '₁, V₂, V_mTherefore, the sum of squared distances Δ (p₁′) Indicates these lattice points v₁, V₂, V_mError matrix (Kv₁+ Kv₂+ Kv_m) And is calculated by the above equation (5).
[0065]
In this second edge contraction, the lattice point v is substantially₁'Error matrix Kv₁’(Kv₁+ Kv₂) As lattice point v₁'Error matrix Kv₁'And lattice point v_mError matrix Kv_mAnd the sum of squares of the distance Δ (p₁′) Is calculated.
[0066]
Therefore, in general terms in the process of edge contraction processing, in FIG.₁, V₂, V_Three, V_FourIs not actual measurement data but data generated by edge contraction, each grid point v₁, V₂, V_Three, V_FourError matrix for Kv₁, Kv₂, Kv_Three, Kv_FourThen, approximate surface p₁Lattice points v constituting₁Error matrix Kv for '₁'Kv₁′ = Kv₁+ Kv₂And approximate surface p₁The three grid points v constituting₁', V_Three, V_FourError matrix Kv₁', Kv_Three, Kv_FourError matrix K obtained by adding_p1(= Kv₁'+ Kv_Three+ Kv_Four= Kv₁+ Kv₂+ Kv_Three+ Kv_Four) Using the above equation (5)₁The sum of squares of the distance Δ (p₁) Is calculated.
[0067]
The square sum of distances Δ (p₁)
Δ (p₁) = P₁ ^T・ K_p1・ P₁  (8)
It becomes. Where P₁Is the approximate surface p₁Column vector notation, m₁Is the error matrix K_p1Is the total number of error matrices Kv included in.
[0068]
And the approximate surface p₂, P_Three, ... p₈Is also the approximate surface p described above.₁The sum of squares of distance Δ (p₂), Δ (p_Three), ... Δ (p₈) Is calculated, and these are substituted into the equation (7) to obtain the edge Ed.₁₂Error evaluation value ε (Ed₁₂) Is calculated.
[0069]
And the other edge Ed in the same way_1r, Ed_2s, Ed_{tt + 1}Error evaluation value ε (Ed in the case of edge contraction as well_1r), Ε (Ed_2s), Ε (Ed_{tt + 1}) Is calculated.
[0070]
Subsequently, in the evaluation value sorting unit 322, the error evaluation value ε_jAre sorted (# 7), and the minimum evaluation value Min {ε_j} Is less than or equal to the allowable value input in step # 3 (# 9). Minimum evaluation value Min {ε_j} Is larger than the allowable value (NO in # 9), the shape change when the edge contraction is unacceptable for all edges is so large that the data reduction process by the edge contraction is terminated. On the other hand, the minimum evaluation value Min {ε_j} Is equal to or less than the allowable value (YES in # 9), the edge / surface contraction processing unit 323 uses the minimum evaluation value Min {ε_j} Is performed (# 11). For example, in FIG. 4, the minimum evaluation value Min {ε_j} Is ε (Ed₁₂), The edge Ed as shown in FIG.₁₂The contraction process is performed.
[0071]
Subsequently, with respect to the polygon model after the edge contraction, the error evaluation value ε is again applied to the edge affected by the edge contraction process._q(Q = 1, 2,...) Is calculated (# 13), the process returns to step # 7, and these error evaluation values ε_qAmong these, the smallest error evaluation value Min {ε_q} Is calculated, and the contraction processing of the corresponding edge is performed (# 7 to # 11). Thereafter, the edge contraction process is repeated one by one (loop of # 7 to # 13), and the minimum evaluation value Min {ε_q} Is over the allowable value, the data reduction process is terminated (NO in # 9).
[0072]
Therefore, by performing such data reduction processing, the polygon model after the data reduction is approximated so that the error evaluation value ε for the first measurement data is equal to or less than the allowable value with respect to the first polygon model.
[0073]
As described above, in the data reduction method according to the present embodiment, how far the surface of the polygon model approximated by edge contraction or surface contraction is from the first lattice point (measured three-dimensional shape data). Since the error evaluation value is determined according to the condition, the data reduction process can be performed based on an evaluation criterion that is easy to understand intuitively.
[0074]
In addition, since data reduction is performed so that the evaluation value falls within a predetermined allowable error range, data reduction is performed while managing the error of the three-dimensional shape data constituting the approximated polygon model relatively accurately. Processing can be performed at high speed.
[0075]
In particular, even when random noise data is mixed in the measured 3D shape data, or when a large number of grid points are gathered into one point to reduce data, it is possible to suppress a decrease in reliability of error evaluation values. it can.
[0076]
8 and 9 compare the error evaluation method when random noise data is mixed in the measured three-dimensional shape data with the conventional error evaluation method.
[0077]
FIG. 8 is a diagram showing edge contraction of a portion (displayed in a cross section) where a discontinuous surface is generated in the polygon model due to random noise data. As shown in the figure, the lattice point v of the portion where the discontinuity unevenness of the polygon model surface is greatly generated₁, V₂Is substantially the center lattice point v₁In the data reduction method shown in the above-mentioned conventional paper “Surface Simplification Using Quadric Error Metrics”, the lattice points v are collected as shown in FIG.₁', For example, a lattice point v₁, V_FourPlane p containing₁₄And lattice point v₂, V_FivePlane p containing_{twenty five}Distance to₁', D₂Since 'is used as the basis for error evaluation, the error evaluation value is calculated for a small sensory approximation error, whereas in the data reduction method according to the present embodiment, for example, the lattice point v₁, V₂Grid point v from₁', V_Four, V_FivePlane p containing₄₅Distance to₁, D₂Therefore, the error evaluation value relatively matches the sensory approximation error and is not calculated for a small eye.
[0078]
10, FIG. 11 and FIG. 12 compare the error evaluation method when a large number of lattice points are gathered into one point with the conventional error evaluation method.
[0079]
FIG. 10 shows eight lattice points v₁, V₂, ... v₈It is a figure which shows shrinkage | contraction of the said zigzag surface of the polygon model in which the zigzag surface (it represents by the cross section) is formed. As shown in FIG.₁, V₂, ... v₆Is the lattice point v₇, V₈Lattice point v at the approximate center of₁In the data reduction method shown in the above-mentioned conventional paper “Surface Simplification Using Quadric Error Metrics”, the lattice points v are collected as shown in FIG.₁Z 'zigzag faces p of the first polygon model₇₁, P₁₂, P_{twenty three}, P₃₄, P₄₅, P₅₆, P₆₈Distance to₁', D₂', ... d₆Since 'is used as the basis for error evaluation, the evaluation value of the error is calculated with respect to a sensory approximation error. On the other hand, in the data reduction method according to the present embodiment, for example, each lattice point v₁, V₂, ... v₆Grid point v from₁', V₇, V₈Plane p containing₇₈Distance to₁, D₂, ... d₆Is the basis of error evaluation, the evaluation value of the error relatively matches the sensory approximation error and is not calculated for a large eye.
[0080]
FIG. 13 is a flowchart illustrating a modification of the data reduction processing procedure for three-dimensional shape data.
[0081]
In the data reduction processing procedure shown in FIG. 7, each time the edge contraction process is performed, the evaluation value ε is calculated again for the edge affected by the edge contraction, and the next edge contraction process is performed based on the evaluation value ε. However, the data reduction processing procedure shown in FIG. 13 does not perform the calculation of the evaluation value ε for the edge affected by the edge contraction, but performs the edge contraction for the other edges. .
[0082]
Specifically, in the flowchart shown in FIG. 13, the process of step # 13 in FIG. 7 is changed to step # 13 ′ of the process of “inhibiting the contraction of the edge affected by the edge contraction”. And Steps # 15 and # 17 are added between the “End” process.
[0083]
Therefore, in the following description, common parts of the flowchart will be briefly described, and different parts will be described in detail.
[0084]
The three-dimensional shape data of the measuring object G captured by the three-dimensional shape measuring apparatus 1 is input to the shape data processing apparatus 3, and a polygonal model 31 is generated by the polygon generating unit 31 (# 1). Further, an allowable value for determining whether or not the edge contraction process is possible is input from the allowable value input unit 33 by the operator (# 3).
[0085]
Subsequently, an evaluation value ε when the edge contraction is performed on all edges of the polygon model in the evaluation value calculation unit 321._j(J = 1, 2,..., N, N is the total number of edges) is calculated (# 5), and the evaluation value sorting unit 322 determines the error evaluation value ε._jAnd the minimum evaluation value Min {ε_j} Is calculated (# 7).
[0086]
Subsequently, the minimum evaluation value Min {ε_j} Is less than or equal to the allowable value in step # 3 (# 9), and the minimum evaluation value Min {ε_j} Is equal to or less than the allowable value (YES in # 9), the edge / surface contraction processing unit 323 uses the minimum evaluation value Min {ε_j} Is performed (# 11).
[0087]
Subsequently, the edge contraction process affected by the edge contraction process is prohibited (# 13 '), and the process returns to step # 7. This process is performed so that the next edge contraction process is performed on the edges that are not affected by the current edge contraction process.
[0088]
Returning to step # 7, the evaluation value ε for the edges other than the edges for which edge contraction is prohibited_q(Q = 1, 2,... Q, where Q <N) is sorted and the minimum evaluation value Min {ε_q} Is calculated (# 7). And the minimum evaluation value Min {ε_q} Is less than or equal to the allowable value (# 9), and the minimum evaluation value Min {ε_q} Is equal to or less than the allowable value (YES in # 9), the edge / surface contraction processing unit 323 uses the minimum evaluation value Min {ε_q} Is performed (# 11), and the edge contraction process affected by the edge contraction process is prohibited (# 13 '), and the process returns to step # 7 again.
[0089]
Thereafter, the same processing is repeated, and each time the edge contraction processing is performed, the next edge processing is performed while excluding the edge affected by the edge contraction (# 7, # 9, # 11, # 13). 'Lube').
[0090]
On the other hand, in the process of repeating the edge contraction process, the minimum evaluation value Min {ε_q} Is larger than the allowable value (NO in # 9), it is determined whether there is an edge for which edge contraction is prohibited (# 15), and if there is an edge for which edge contraction is prohibited (YES in # 15). ) Again, error evaluation value ε for those edges_r(R = 1, 2,...) Is calculated (# 17), the process returns to step # 7, and these error evaluation values ε_rAmong these, the minimum error evaluation value Min {ε_r} Is calculated, and its minimum error evaluation value Min {ε_r} Is performed (# 7, # 9, # 11).
[0091]
Then, the edge contraction process is repeated, and the minimum evaluation value Min {ε_q} Becomes larger than the allowable value, and when there are no edges for which edge contraction is prohibited (NO in # 9 and # 15), the data reduction processing by edge contraction is terminated.
[0092]
FIG. 14 is a diagram illustrating an example of a data reduction process according to the processing procedure illustrated in FIG.
[0093]
In the figure, polygon model M₀Is the first polygon model. This polygon model M₀Is 28 lattice points v₁, V₂, ... v₂₈Are arranged in 5 rows so that the number of each row is (3, 4, 5, 4, 5, 4, 3), and the adjacent lattice points are connected.
[0094]
Since the edges e1, e2, e3, e4, and e5 are not affected by each other when the respective edges ei (i = 1, 2,... 5) are contracted, they are shown in FIG. 13 for convenience of explanation. It is selected that the edges are sequentially contracted according to the processing procedure.
[0095]
Therefore, the data reduction process of FIG. 14 is performed by the polygon model M according to the processing procedure of FIG.₀Shows a case where edges are contracted sequentially in the order of edges e1, e2,... E5. And polygon model M₁, M₂, M_Three, M_Four, M_FiveIs the polygon model M₀Is an approximated polygon model when contraction processing is performed in the order of edges e1, e2,... E5.
[0096]
According to the data reduction processing procedure shown in FIG. 13 described above, first, the edge model e1 is contracted in the first edge contraction processing, and the polygon model M₁Is approximated to the collected grid point v_aAnd lattice points v arranged around them₉, V_Ten, V₁₁, V₁₃, V₁₆, V₁₈, V₁₉, V₂₀(Polygon model M₁The edges formed by the grid line in the dotted line frame are affected, and in the next edge contraction processing, the edges (polygon model M) excluding these edges are affected.₁Again for the edge outside the dotted frame)_qAnd the minimum evaluation value Min {ε_q}, The edge contraction processing is performed on the edge e2 having the polygon model M₂Is approximated by
[0097]
Furthermore, in the next edge contraction process, the collected grid points v_bAnd lattice points v arranged around them₁, V₂, V_Four, V₆, V₈, V_Ten, V₁₃, V_a(Polygon model M₂The edges formed by the grid points in the dotted line frame) are affected. Therefore, the edges excluding these edges (polygon model M)₂Again for the edge outside the dotted frame)_sAnd the minimum evaluation value Min {ε_s}, The edge contraction process is performed on the edge e3 having the polygon model M_ThreeIs approximated by
[0098]
Then, the edge contraction is also performed for the edges e4 and e5 in the same manner, and the first polygon model M is obtained by the five edge contraction processes.₀Is the polygon model M_FiveThe number of data is reduced by five.
[0099]
First polygon model M₀The sixth polygon model M₆Considering the process of approximating (not shown), the processing procedure shown in FIG. 13 does not recalculate the evaluation value for the edge affected by the edge contraction. Therefore, in the example of FIG. Model M₀When the evaluation values are first calculated for the 66 edges forming the approximate polygon model M,₁~ M_FourThe evaluation value is not recalculated for, and the next recalculation is the polygon model M_FiveThis is performed for 50 edges that constitute. Therefore, the sixth polygon model M₆The number of recalculations of evaluation values up to 50 is 50.
[0100]
On the other hand, in the processing procedure shown in FIG. 7, since the evaluation value is recalculated for the edge affected by the edge contraction, each approximated polygon model M₁~ M_FiveEach time, the evaluation value is recalculated for 16 edges affected by the edge contraction. Therefore, in the processing procedure shown in FIG. 7, the sixth polygon model M₆The number of evaluation value recalculations up to 16 × 5 = 80 times, and the processing procedure shown in FIG. 13 has the advantage that the number of evaluation value recalculations is reduced and high-speed processing is possible.
[0101]
FIG. 15 is a modification of the flowchart shown in FIG.
[0102]
In the flowchart shown in FIG. 15, the evaluation value of the edge affected after the edge contraction is set to a predetermined evaluation value ε greater than the allowable value._maxIn the next edge contraction, the edge is substantially excluded from the object of edge contraction.
[0103]
Specifically, in the flowchart of FIG. 13, step # 13 ′ is changed to “evaluate the evaluation value of the edge affected by the edge contraction ε_maxTo "step # 13" of the "set to" process, and the evaluation target of step # 15 and the evaluation value recalculation target of step # 17 are_maxIn step # 19 ', steps # 19 and # 21 for performing edge contraction processing on the edge after recalculation of the evaluation value are added after step # 17'.
[0104]
Therefore, in the following description, portions different from the flowchart of FIG. 13 will be described in detail.
[0105]
In step # 11, the edge / surface contraction processing unit 323 performs the minimum evaluation value Min {ε_j}, A predetermined evaluation value ε in which the evaluation value of the edge affected by the edge contraction processing is larger than the allowable value is obtained._max(# 13 ″) and return to step # 7. This process makes these edges excluded from the next edge contraction process, that is, for edges that were not affected by the edge contraction process. Only for the edge contraction to take place.
[0106]
Returning to step # 7, the evaluation value ε again._i(I = 1, 2,... N−1) is sorted, and the minimum evaluation value Min {ε_i} Is calculated (# 7). And the minimum evaluation value Min {ε_i} Is less than or equal to the allowable value (# 9), and the minimum evaluation value Min {ε_i} Is equal to or less than the allowable value (YES in # 9), the edge / surface contraction processing unit 323 uses the minimum evaluation value Min {ε_i} Is performed (# 11).
[0107]
Subsequently, the evaluation value of the edge affected by the edge contraction process is the evaluation value ε_max(# 13 ″), the process returns to step # 7 again. Thereafter, the same processing is repeated, and each time the edge contraction process is performed, the evaluation value of the edge affected by the edge contraction is evaluated as ε._maxThe next edge processing is performed while setting to (Lube of # 7, # 9, # 11, # 13 ″).
[0108]
On the other hand, in the process of repeating the edge contraction process, the minimum evaluation value Min {ε_i} Becomes larger than the allowable value (NO in # 9), the evaluation value ε_maxIt is determined whether there is an edge having (# 15 '), and the evaluation value ε_maxIf there is an edge having (YES in # 15 '), the error evaluation value ε is again obtained for those edges._s(S = 1, 2,...) Is calculated (# 17 ′).
[0109]
These error evaluation values ε are obtained by sorting._sAmong these, the smallest error evaluation value Min {ε_s} Is calculated (# 19), and its minimum evaluation value Min {ε_i} Is equal to or smaller than the allowable value (YES in # 21), the process proceeds to step # 11 and the minimum evaluation value Min {ε described above._i}, The edge contraction process corresponding to.
[0110]
On the other hand, the above edge contraction process is repeated, and the evaluation value ε_max(No in # 15 ') or evaluation value ε_maxRecalculated evaluation value ε for edges with_sAmong these, the minimum evaluation value Min {ε_s} Becomes larger than the allowable value (NO in # 21), the data reduction process by edge contraction is terminated.
[0111]
The processing procedure shown in FIG. 15 also sets the evaluation value of the edge affected by the edge contraction to an evaluation value ε greater than the allowable value._maxBy setting to, the contraction of the edge substantially shown in the processing procedure of FIG. 13 is prohibited, so the number of evaluation value recalculations is reduced and high-speed processing is possible.
[0112]
In the data reduction processing procedure shown in FIG. 13 and FIG. 15, the evaluation value is not recalculated until there is no part where the edge contraction process is prohibited for the part affected by the edge contraction process. Although it is excluded from the target of the edge contraction process, for example, when the edge contraction process is repeated a predetermined number of times, or when the difference between the minimum evaluation value and the allowable value falls within a predetermined range, etc. When the predetermined condition is satisfied, the prohibition of the edge contraction process may be canceled, and the evaluation values may be recalculated for all edges to enable the edge contraction again.
[0113]
In this way, even if a portion where data reduction processing can be performed within the allowable error remains in the portion where the edge contraction processing is prohibited, the data reduction processing can be performed for that portion, and can be performed within the allowable range. Data can be reduced as efficiently as possible.
[0114]
Further, the data reduction processing procedure shown in FIGS. 13 and 15 is intended to reduce the number of evaluation value recalculations and increase the processing speed. Therefore, the evaluation value is expressed by the above-described equation (6). It is not limited to the error ε. Even when the evaluation value changes due to edge contraction or surface contraction and needs to be recalculated after contraction, for example, the evaluation value shown in the above-mentioned paper `` Surface Simplification Using Quadric Error Metrics '' Can be widely applied.
[0115]
In the above embodiment, the data reduction of the three-dimensional measurement data measured by the three-dimensional shape measuring apparatus 1 has been described as an example. However, the present invention is not limited to this, and is created by computer graphics or the like. It can also be widely applied to three-dimensional data.
[0116]
【The invention's effect】
As described above, according to the present invention, the evaluation value for evaluating the error caused by the aggregation is obtained for a plurality of portions to be aggregated into two or more grid points in the polygon model. Data reduction of 3D shape data that sequentially reduces the number of data of 3D shape data constituting the polygon model by repeating the process of calculating and reducing the data of the collection target part of the grid points based on these evaluation values In this method, when the grid point concentration process is performed, the data reduction process of the grid point concentration target part affected by the grid point concentration process is prohibited. The number of evaluation value recalculations is reduced, and the data reduction processing can be speeded up.
[0117]
In addition, since the evaluation value of the collection target part of the grid point affected by the data reduction is changed to a predetermined value so that it is excluded from the collection target in the next data reduction process, Data reduction processing can be easily prohibited.
[0118]
  In addition, if the prescribed conditions are met, the data reduction processing for the portion of the prohibited grid points to be concentratedProhibitionSince it is made to cancel | release, data reduction can be performed as efficiently as possible within the allowable range.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a configuration of a three-dimensional shape measurement data processing system to which a data reduction method according to the present invention is applied.
FIG. 2 is a block diagram showing a configuration of a shape data processing apparatus.
FIG. 3 is a diagram illustrating an example of approximation of a polygon model by data reduction.
FIG. 4 is a conceptual diagram of a data reduction method by edge contraction.
FIG. 5 is a conceptual diagram of a data reduction method by surface contraction.
FIG. 6 is a diagram for explaining an evaluation value applied to the data reduction method according to the embodiment.
FIG. 7 is a flowchart showing a procedure of data reduction processing of three-dimensional shape data.
FIG. 8 is a diagram showing edge contraction in a portion where a discontinuous surface is generated in a polygon model due to random noise data;
FIG. 9 is a diagram for explaining a difference between an error evaluation value according to the present embodiment and a conventional error evaluation value in the data reduction process shown in FIG. 8;
FIG. 10 is a diagram illustrating contraction of a zigzag surface of a polygon model having a zigzag surface.
FIG. 11 is a diagram for explaining a conventional error evaluation value in the data reduction process shown in FIG. 10;
12 is a diagram for explaining an error evaluation value according to the present embodiment in the data reduction processing shown in FIG.
FIG. 13 is a flowchart showing another embodiment of the data reduction processing procedure for three-dimensional shape data.
FIG. 14 is a diagram for explaining an example of a data reduction process according to the processing procedure shown in FIG. 13;
15 is a diagram showing a modification of the flowchart shown in FIG.
[Explanation of symbols]
1 Three-dimensional shape measuring device
101 Lighting unit
102 Confocal optical system
103 Light receiver
104 Beam splitter
105 Calculation unit
106 Measurement table
2,4 External storage device
3 Shape data processing device (data reduction device)
31 Polygon generator
32 Data reduction department
321 Evaluation value calculation unit (evaluation value calculation means, prohibition means, release means)
322 evaluation value sort part
323 Edge / surface contraction processing unit (determination means, data reduction means)
33 Allowable value input section
34 Data output section
5 display devices
6 External processing device

Claims (12)

Polygon model after data reduction with respect to a polygon model composed of actually measured shape data generated by aggregating two or more lattice points in a polygon model for a plurality of parts to be aggregated into one lattice point A step of calculating an evaluation value for evaluating the error of each of the above, a step of determining a collection target portion of the grid points on which data reduction is to be performed based on these evaluation values, and a collection point of the grid points determined by the determination means A step of performing data reduction processing of the portion, calculating an evaluation value of the lattice point concentration target portion, and repeating the data reduction of the lattice point concentration target portion based on the evaluation value, A data reduction method for three-dimensional shape data for sequentially reducing the number of data of three-dimensional shape data to be configured, comprising: When performed, data reduction method of the three-dimensional shape data characterized by comprising a step of prohibiting the data reduction processing rendezvous target portion of the grid points affected by gathering processing of the grid point. 2. The data reduction method for three-dimensional shape data according to claim 1 , wherein when a predetermined condition set in advance is satisfied, the prohibition of the data reduction processing of the prohibited collection target portion of the lattice points is canceled.   3. The method for reducing data of three-dimensional shape data according to claim 2, wherein the predetermined condition is that there is no portion where the lattice points can be reduced based on the evaluation value.   3. The data reduction method for three-dimensional shape data according to claim 2, wherein the predetermined condition is that data reduction processing is repeated a predetermined number of times. Polygon model after data reduction with respect to a polygon model composed of actually measured shape data generated by aggregating two or more lattice points in a polygon model for a plurality of parts to be aggregated into one lattice point An evaluation value calculation means for calculating an evaluation value for evaluating the error of each of the above, a determination means for determining a collection target portion of the grid points to be subjected to data reduction based on the evaluation value, and a grid point determined by the determination means A data reduction means for performing data reduction processing on the collection target portion of the object, calculating an evaluation value of the collection target portion of the grid point, and repeatedly reducing data of the collection target portion of the grid point based on the evaluation value A data reduction device for three-dimensional shape data that reduces the number of data of the three-dimensional shape data constituting the polygon model. A tertiary having a prohibition means for prohibiting the data reduction processing of the collection target portion of the lattice point affected by the collection processing of the lattice point when the data reduction processing of the collection target portion of the child point is performed Data reduction device for original shape data.   The prohibiting means evaluates the concentration target portion of the lattice point so that the determination target portion determines that the lattice point concentration target portion affected by the lattice point concentration processing is not subject to data reduction processing. 6. The data reduction apparatus for three-dimensional shape data according to claim 5, wherein: is temporarily changed to a predetermined value. 7. The data reduction device for three-dimensional shape data according to claim 5 or 6, wherein when the predetermined condition set in advance is satisfied, the cancellation of the prohibition of the data reduction processing of the prohibited collection target portion of the lattice point is canceled. A data reduction apparatus for three-dimensional shape data, further comprising means.   8. The data reduction apparatus for three-dimensional shape data according to claim 7, wherein the predetermined condition is that there is no portion where the lattice points can be reduced based on the evaluation value.   8. The data reduction apparatus for three-dimensional shape data according to claim 7, wherein the predetermined condition is that data reduction processing is repeated a predetermined number of times.   The determination unit includes a minimum evaluation value calculation unit that calculates a minimum evaluation value, and a comparison unit that compares the minimum evaluation value with a predetermined allowable value that is set in advance. The data of the three-dimensional shape data according to any one of claims 5 to 7, wherein when the value is equal to or smaller than the value, the concentrated portion of the lattice points having the minimum evaluation value is determined as the data reduction portion. Reduction device.   The data reduction apparatus for three-dimensional shape data according to any one of claims 5 to 10, wherein the collection target of the lattice points is an edge of a triangular polygon model.   The data reduction apparatus for three-dimensional shape data according to any one of claims 5 to 10, wherein the collection target of the lattice points is a plane of a triangular polygon model.

Images