(57)【特許請求の範囲】
【請求項１】
３次元形状データにおける格子状の面の生成装置であって、
３次元形状データを入力する入力手段と、
入力された３次元形状データを処理するＣＰＵと、
前記ＣＰＵが処理を実行するために必要なデータの格納領域および作業領域を提供するメモリと、を有し、
前記ＣＰＵは、
はりつけようとする面の周辺に存在する前記３次元形状データのポリゴンの向きを検出する第１のステップと、
検出されたポリゴンの向きと前記面の格子の向きとが合うように、当該面の向きを決定する第２のステップと、
前記３次元形状データに対して前記面を決定された向きにはりつける第３のステップと、を実行するものであり、
前記第１のステップにおいて、はりつけようとする面の周辺に存在するポリゴンの頂点を始点としそれと繋がる頂点を終点とする複数のベクトルを検出し、
前記第２のステップにおいて、前記面の座標空間におけるＸ軸およびＹ軸に対して前記複数のベクトルについてのｘ成分とｙ成分の積の二乗の総和が最小となるような方向を、前記ポリゴンの向きと前記面の格子の向きとが合う方向として決定して、当該面を配置する、
ことを特徴とする３次元形状データにおける面生成装置。
【請求項２】
３次元形状データにおける格子状の面の生成装置であって、
３次元形状データを入力する入力手段と、
入力された３次元形状データを処理するＣＰＵと、
前記ＣＰＵが処理を実行するために必要なデータの格納領域および作業領域を提供するメモリと、を有し、
前記ＣＰＵは、
はりつけようとする面の周辺に存在する前記３次元形状データのポリゴンの向きを検出する第１のステップと、
検出されたポリゴンの向きと前記面の格子の向きとが合うように、当該面の向きを決定する第２のステップと、
前記３次元形状データに対して前記面を決定された向きにはりつける第３のステップと、を実行するものであり、
前記第１のステップにおいて、はりつけようとする面の周辺に存在するポリゴンの頂点を始点としそれと繋がる頂点を終点とする複数のベクトルを検出し、
前記第２のステップにおいて、前記面の座標空間におけるＸ軸およびＹ軸に対して前記複数のベクトルについて主成分分析を行い、その第１主成分ベクトルの方向をＸ軸の方向と決定して当該面を配置する、
ことを特徴とする３次元形状データにおける面生成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、３次元形状データにおける面生成装置に関する。
【０００２】
【従来の技術】
従来より、光切断法などを利用した３次元計測装置を用いて３次元形状データを生成することが行われている。３次元計測装置は、例えばスリット光を投射し且つ偏向することによって対象物を光学的にスキャンし、三角測定の原理で３次元形状データを演算により求める。対象物の全周を計測し、得られた３次元形状データを繋ぎ合わせることにより、対象物の全体についての３次元形状データが得られる。
【０００３】
しかし対象物の形状、向き、または照明の状態などによっては、部分的に３次元形状データが得られず、データの欠落が生じることがある。
【０００４】
【発明が解決しようとする課題】
そのような場合に、データが欠落した部分に対して穴埋めを行う必要がある。そのために、格子状の面を新たに生成し、生成した面とデータの欠落部分の輪郭部とを繋ぐことが考えられる。
【０００５】
その場合に、どのような面を生成し、また生成した面を元の３次元形状データに対してどのように配置するのかが問題となる。このような場合に、それらをユーザが決定しまたは設定して３次元形状データを生成することは極めて面倒なことである。
【０００６】
本発明は、上述の問題に鑑みてなされたもので、３次元形状データの欠落部分の穴埋め処理などにおいて、新たな面の向きなどを自動的に決定し、より自然な３次元形状データを生成することを目的とする。
【０００７】
【課題を解決するための手段】
本発明に係る装置は、３次元形状データにおける格子状の面の生成装置であって、３次元形状データを入力する入力手段と、入力された３次元形状データを処理するＣＰＵと、前記ＣＰＵが処理を実行するために必要なデータの格納領域および作業領域を提供するメモリと、を有し、前記ＣＰＵは、はりつけようとする面の周辺に存在する前記３次元形状データのポリゴンの向きを検出する第１のステップと、検出されたポリゴンの向きと前記面の格子の向きとが合うように、当該面の向きを決定する第２のステップと、前記３次元形状データに対して前記面を決定された向きにはりつける第３のステップと、を実行するものであり、前記第１のステップにおいて、はりつけようとする面の周辺に存在するポリゴンの頂点を始点としそれと繋がる頂点を終点とする複数のベクトルを検出し、前記第２のステップにおいて、前記面の座標空間におけるＸ軸およびＹ軸に対して前記複数のベクトルについてのｘ成分とｙ成分の積の二乗の総和が最小となるような方向を、前記ポリゴンの向きと前記面の格子の向きとが合う方向として決定して、当該面を配置する。
【００１３】
【発明の実施の形態】
図１は本発明の実施形態に係る３次元処理装置１の概略構成を示すブロック図である。
【００１４】
図１において、３次元処理装置１は、バス１０に接続されたＣＰＵ（処理装置）１１、メモリ１２、補助記憶装置１３、入出力インタフェース１４、キーボード１５、マウス１６、および表示装置１７を備えている。
【００１５】
ＣＰＵ１１は、本発明の面生成方法を含む種々の処理を実行する。メモリ１２は、ＣＰＵ１１が実行する手順を記述した制御プログラムを格納するＲＯＭ１２ａと、ＣＰＵ１１が各種処理を実行するために必要なデータの格納領域および作業領域を提供するＲＡＭ１２ｂとを有する。補助記憶装置１３は、３次元データ（３次元形状データ）、２次元カラー画像データなどの処理対象となるデータを格納するために用いられる。入出力インタフェース１４は、処理対象のデータを装置の外部から入力し、または生成したデータを装置の外部へ出力するために用いられる。
【００１６】
キーボード１５およびマウス１６は、各種のデータ、指示、または設定の入力に用いられる。表示装置１７は、３次元データおよび生成した面の画像を表示するとともに、処理状況や処理結果、および処理過程の表示にも用いられる。表示装置１７はマルチウインドウシステムによって複数のウィンドウを表示することが可能である。
【００１７】
３次元処理装置１により、入力された３次元データに対し、データが欠落した部分に対する穴埋め、新たな面の形成、その他の処理を行うことが可能である。以下において、面の配置および形状に関し、第１ないし第３の３つの実施形態について説明する。
〔第１の実施形態〕
図２は３次元データＴＤ１に対して面生成を行う第１の実施形態を説明するための図、図３は第１の実施形態の面生成処理を示すフローチャートである。第１の実施形態は請求項１の発明に対応する。
【００１８】
図２には３次元データＴＤ１の一部が示されている。３次元データＴＤ１には、データの欠落部分ＫＲ１が存在する。欠落部分ＫＲ１に対し、新たな面ＭＥ１を生成してはりつける。
【００１９】
面ＭＥ１を生成し、またははりつける際に、図２の右下に示されるように、３次元データＴＤ１のポリゴンの向きと合うように面ＭＥ１の向きを決定する。図２の右上に示される面ＭＥＫ１では、その格子の向きが３次元データＴＤ１のポリゴンの向きと合っていない。
【００２０】
図３において、３次元データＴＤ１のうち、欠落部分ＫＲ１、つまりはりつけようとする面の周辺に存在するポリゴンの向きを検出する（＃１１）。次に、検出されたポリゴンの向きと面ＭＥ１の格子の向きとが合うように、面ＭＥ１の向きを決定する（＃１２）。３次元データＴＤ１に対して、面ＭＥ１を決定された向きにはりつける（＃１３）。これによって、欠落部分のない３次元データＴＤ１が生成される。
【００２１】
このような処理が自動的に行われるので、ユーザは面倒な作業を行う必要がなく、より自然な３次元データＴＤ１を生成することができる。
なお、欠落部分ＫＲ１にはりつけるのではなく、新たに面を形成したい任意の部分に面ＭＥ１をはりつけることができる。
〔第２の実施形態〕
図４は３次元データＴＤ２に対して面生成を行う第２の実施形態を説明するための図、図５は第２の実施形態の面生成処理を示すフローチャートである。第２の実施形態は請求項３の発明に対応する。
【００２２】
図４に示す３次元データＴＤ２は円柱形状である。３次元データＴＤ２の周面の一部にデータの欠落部分ＫＲ２が存在する。欠落部分ＫＲ２に対し、新たな面ＭＥ２を生成してはりつける。
【００２３】
面ＭＥ２を生成し、またははりつける際に、図２の右下に示されるように、３次元データＴＤ２の形状と合うように面ＭＥ２の向きを決定する。図４の右上に示される面ＭＥＫ２では、その格子の向きが３次元データＴＤ２の形状と合っていない。
【００２４】
図５において、３次元データＴＤ２のうち、欠落部分ＫＲ２、つまりはりつけようとする面の周辺部分における形状を検出する（＃２１）。次に、検出された形状と面ＭＥ２の格子の向きとが合うように、面ＭＥ２の向きを決定する（＃２２）。３次元データＴＤ２に対して、面ＭＥ２を決定された向きにはりつける（＃２３）。これによって、欠落部分のない３次元データＴＤ２が生成される。
【００２５】
このような処理が自動的に行われるので、ユーザは面倒な作業を行う必要がなく、より自然な３次元データＴＤ２を生成することができる。
なお、欠落部分ＫＲ２にはりつけるのではなく、新たに面を形成したい任意の部分に面ＭＥ２をはりつけることができる。面ＭＥ２は、３次元データＴＤ２の形状に沿って変形することが可能である。
〔第３の実施形態〕
図６は３次元データＴＤ３に対して面生成を行う第３の実施形態を説明するための図、図７は第３の実施形態の面生成処理を示すフローチャートである。第３の実施形態は請求項５の発明に対応する。
【００２６】
図６には３次元データＴＤ３の一部が示されている。３次元データＴＤ３には、データの欠落部分ＫＲ３が存在する。欠落部分ＫＲ３に対し、新たな面ＭＥ３を生成してはりつける。
【００２７】
面ＭＥ３を生成し、またははりつける際に、図６の右中央に示されるように、３次元データＴＤ３のポリゴンの格子の密度と合うように面ＭＥ３の格子の密度を決定する。図６の右上および右下に示される面ＭＥＫ３，４では、その格子の密度が小さ過ぎまたは大き過ぎて３次元データＴＤ３のポリゴンの密度と合っていない。
【００２８】
図７において、３次元データＴＤ３のうち、欠落部分ＫＲ３、つまりはりつけようとする面の周辺に存在するポリゴンの密度を検出する（＃３１）。次に、検出された密度と面の格子の密度とが合うように、面ＭＥ３の格子の密度を決定する（＃３２）。３次元データＴＤ３に対して、決定された密度の格子の面ＭＥ３を、３次元データＴＤ３のポリゴンの向きと合うようにしてはりつける（＃３３）。これによって、欠落部分のない３次元データＴＤ３が生成される。
【００２９】
このような処理が自動的に行われるので、ユーザは面倒な作業を行う必要がなく、より自然な３次元データＴＤ３を生成することができる。
なお、欠落部分ＫＲ３にはりつけるのではなく、新たに面を形成したい任意の部分に面ＭＥ３をはりつけることができる。
【００３０】
次に、これら３つの実施形態についてさらに具体的に詳しく説明する。
〔第１の実施形態の詳細〕
第１の実施形態では、上にも述べたように、３次元データＴＤのポリゴンの向きと合うように、データの欠落部分ＫＲに対して面を生成する。３次元データＴＤの欠落部分ＫＲに格子状の平面をはりつける際に、欠落部分ＫＲの周りのポリゴンの向きと平面の格子の方向、つまり平面のＸＹ座標軸の向きとが合うように、平面の向きを設定する。
〔第１の実施形態の第１実施例〕
図８は３次元データＴＤ４の欠落部分ＫＲ４の周囲のベクトルを示す図、図９はＸ軸およびＹ軸とＸ’軸およびＹ’軸との関係を示す図である。
【００３１】
３次元データＴＤ４の欠落部分ＫＲ４に対して、次に示す（ａ）〜（ｄ）の処理を行う。
（ａ）３次元データＴＤ４の欠落部分ＫＲ４を多角形ポリゴンととらえ、その法線を求める。その法線方向を、生成する平面（面ＭＥ）のＺ軸方向に設定する。これによって、３次元データＴＤ４に対し、欠落部分ＫＲ４が正面となるように見た状態で、その奥行き方向がＺ軸方向となり、欠落部分ＫＲ４に平行な平面内にＸ軸およびＹ軸が設定される。
【００３２】
そこで、Ｘ軸およびＹ軸を適当な方向にとって設定する（図９参照）。例えば、フィットさせる平面と元の座標系のＸＹ平面との交線をＸ軸に設定する。そして、３次元データＴＤ４を、新しく設定したＸＹＺ座標系に変換する。以降において、この新しい座標系におけるＸＹ平面上で考えていく。
（ｂ）図８に示すように、欠落部分ＫＲ４を構成する頂点を始点とし、それと繋がっている頂点を終点とするベクトルｖi ＝（ｘi ，ｙi ）をピックアップする。このとき、ベクトルｖi は大きさ１に正規化しておく。ベクトルｖi を利用して、生成する平面のＸ軸およびＹ軸を決定する。
（ｃ）Ｘ軸およびＹ軸を、Ｚ軸を中心としてθ（０≦θ≦π／２）だけ回転させるとする。回転した後の軸を、Ｘ’軸およびＹ’軸とする。θだけ回転させたときの座標系において、元のベクトルｖi ＝（ｘi ，ｙi ）が回転後にはベクトルｖi ’＝（ｘi ’，ｙi ’）となったとすると、これらの間の関係は次の（１）式で表される。
【００３３】
ｘi ’＝ｘi cos θ＋ｙi sin θ
ｙi ’＝−ｘi sin θ＋ｙi cos θ        ……（１）
（ｄ）上の（ａ）で設定した座標系からθだけ回転させたときの座標系によって生成される平面が、欠落部分ＫＲ４の周りのポリゴンと整合性がとれるようになるためには、このＸ’Ｙ’座標系において、ベクトルｖi ’＝（ｘi ’，ｙi ’）が、（１，０）、（０，１）、（−１，０）、（０，−１）に近ければよい。すなわち、ベクトルｖi ’の方向がＸ’軸またはＹ’軸に平行になればよい。
【００３４】
したがって、ベクトルｖi ’のｘ成分とｙ成分の積の二乗の総和が最小となるようなθを求めてやればよい。これを評価関数Ｅとして表すと、次の（２）式のようになる。
【００３５】
【数１】
0004106839.tif 000002
そして、（２）式に（１）式を代入し、次の（３）式を得る。
【００３６】
【数２】
0004106839.tif 000003
ここで、ａ＝cos θ，ｂ＝sin θとし、（３）式を変形して次の（４）式を得る。
【００３７】
【数３】
0004106839.tif 000004
評価関数Ｅが最小となるθの値は、ｄＥ／ｄθ＝０となるθの値を求めればよい。
【００３８】
上の（４）式をθで微分すると次の（５）式のようになる。
【００３９】
【数４】
0004106839.tif 000005
よって、θは次の（６）式のように求められる。
【００４０】
【数５】
0004106839.tif 000006
なお、θの値は２つ求まる。それらを（４）式に代入し、評価関数Ｅが小さい方のθを採用する。
【００４１】
次に、３次元データＴＤ４の座標逆変換を行い、元の座標系に戻す。そして、上の（ａ）で設定したＸ軸およびＹ軸を、Ｚ軸を中心としてθだけ回転させ、生成する平面（面ＭＥ）の方向（Ｘ軸およびＹ軸）を決定する。
〔第１の実施形態の第２実施例〕
第２実施例においては、主成分分析によってＸ軸およびＹ軸を決定する。まず、第１実施例の（ａ）および（ｂ）を実行する。次に、以下に述べる（ｃ）以下を実行する。
（ｃ）ベクトルｖi ＝（ｘi ，ｙi ）において、主成分分析を行い、その第１主成分ベクトルの方向をＸ軸の方向に決定する。但し、上の（ａ）で３次元データＴＤ４を座標変換しているため、座標逆変換を行う必要がある。
【００４２】
主成分分析の方法は公知であるが、その概略を以下に示す。
〔主成分分析〕
○主成分ベクトルの条件と手順
１．各主成分ベクトルの大きさは１である。
【００４３】
【数６】
0004106839.tif 000007
ここで、ｍは次数であり、本実施形態においてはＸ軸およびＹ軸の２つの軸を求めるので、ｍは２となる。
２．第１主成分ベクトルｕ1 は、その方向の成分ｋ1 の分散が最大になるように決定する。
【００４４】
【数７】
0004106839.tif 000008
３．第２主成分ベクトルｕ2 は、条件１を満足し、かつその方向の成分ｋ2 と無相関になるという条件の下で、ｋ2 の分散が最大になるように定める。
【００４５】
【数８】
0004106839.tif 000009
４．以下、同様にして、第ｊ主成分ベクトルｕj は、その方向の成分ｋj と無相関になるという条件の下で、ｋj の分散が最大になるように定める。
○第１主成分ベクトルの算出
【００４６】
【数９】
0004106839.tif 000010
条件付き最小化問題であるので、ラグランジュの未定係数法を用いる。すなわち、パラメータλを導入して、
【００４７】
【数１０】
0004106839.tif 000011
を最小にするような、ｕ1 とλを求める。そのためには、（７）式をｕ1 の各要素について微分し、０とおいて解けばよい。表現を整理するために、
Ｘ＝［Ｘ1 ，…，Ｘn ］
とおけば、
【００４８】
【数１１】
0004106839.tif 000012
であるから、Ｅ1 は次のように表される。
【００４９】
【数１２】
0004106839.tif 000013
この表現を用いると、目的関数は、
【００５０】
【数１３】
0004106839.tif 000014
と表される。ｕ1 に関して微分して０とおくと、次のようになる。
【００５１】
【数１４】
0004106839.tif 000015
上の式は固有値問題に等しい。上の式が有意な解（ｕ1 ＝０以外）をもつためには、行列式＝０、すなわち、
｜Ｃ−λＩ｜＝０
を満たさなければならない。この行列方程式はλの多項式に展開でき、
ａ0 ＋ａ1 λ＋ａ2 λ2 ＋  …＋ａm λm ＝０
これを満足するλはｍ個あり、共分散行列の非負定値性から、いずれも非負であることが知られている。
【００５２】
λの方程式の解のうち最大のものを探し、それに対応する固有ベクトルを求めれば、それが第１主成分となる。このときの固有値は第１主成分の分散を与える。ｉ番目の解λｉと対応する固有ベクトルを考える。この固有べクトルの方向の分散Ｅi は、次のように示される。
【００５３】
【数１５】
0004106839.tif 000016
すなわち、固有値がそのまま固有ベクトルの分散を与える。
【００５４】
そこで、固有値の解の中から、最大のものを選び、対応する固有ベクトルを第１主成分ベクトルとすればよい。そして、２番目に大きいものに対応する固有ベクトルを第２主成分ベクトルとすればよい。
〔第１の実施形態の第３実施例〕
上に述べた第１および第２実施例では、欠落部分に平面をはりつける例を説明したが、第３実施例では、欠落部分の有無に関係なく、新たに面を形成したい任意の部分に平面をはりつける例について説明する。
【００５５】
すなわち、第３の実施例では、３次元データＴＤのポリゴンの向きと合うように３次元データＴＤに対して面を生成する。３次元データＴＤに格子状の平面をはりつける際に、選択された領域のポリゴンの向きと平面の格子の方向（平面のＸＹ座標軸の向き）とが合うように平面の向きを設定する。
【００５６】
次に示す（ａ）〜（ｃ）の処理を行う。
（ａ）３次元データＴＤで面を生成したい領域のポリゴンを選択する。ユーザが選択することが可能である。
（ｂ）選択状態にあるポリゴンの法線ベクトルの平均値を計算する。
【００５７】
その平均値を、生成する平面の座標系でのＺ軸方向として設定する。Ｘ軸およびＹ軸を適当な方向にとって設定する。例えば、フィットさせる平面と元の座標系のＸＹ平面との交線をＸ軸に設定する。そして、３次元データＴＤを、新しく設定したＸＹＺ座標系に変換する。以降において、この新しい座標系におけるＸＹ平面上で考えていく。
（ｃ）選択状態のポリゴンと非選択状態のポリゴンとの境界となっている頂点をみる。その頂点を始点とし、それと繋がっている非選択状態のポリゴンの頂点を終点とするベクトルｖi ＝（ｘi ，ｙi ）をピックアップする。このとき、ベクトルｖi は大きさ１に正規化しておく。ベクトルｖi を利用して、生成する平面のＸ軸およびＹ軸を決定する。
【００５８】
この軸の決定法は、上に述べた第１の実施形態の第１実施例に示す（ｃ）（ｄ）、および第１の実施形態の第２実施例に示す（ｃ）と同様である。
〔第２の実施形態の詳細〕
第２の実施形態では、３次元データＴＤの形状状態と合うように、欠落部分ＫＲに対して面を生成する。３次元データＴＤの欠落部分ＫＲに格子状の平面をはりつける際に、欠落部分ＫＲの周りの形状の考慮して、形状に沿った方向に平面方向（平面の座標軸の方向）を設定する。
〔第２の実施形態の第１実施例〕
図１０は第２の実施形態の第１実施例におけるバウンディングボックスＢＢ１の状態を示す図、図１１はバウンディングボックスＢＢ１に設定したＸラインおよびＹラインを示す図である。
【００５９】
３次元データＴＤ５の欠落部分ＫＲ５に対して、次に示す（ａ）〜（ｆ）の処理を行う。
（ａ）３次元データＴＤ５の欠落部分ＫＲ５を多角形ポリゴンととらえ、その法線を求める。その法線方向を、生成する平面（面ＭＥ）のＺ軸方向に設定する。Ｘ軸およびＹ軸を適当な方向にとって設定する。そして、３次元データＴＤ５を、新しく設定したＸＹＺ座標系に変換する。以降において、この新しい座標系におけるＸＹ平面上で考えていく。
（ｂ）設定したＸ軸を横方向、Ｙ軸を縦方向とする、欠落部分ＫＲ５に対する矩形のバウンディングボックス（Ｂｏｕｎｄｉｎｇ  ｂｏｘ）ＢＢ１を生成する。バウンディングボックスＢＢ１内に格子状の平面が生成されることになるため、バウンディングボックスＢＢ１のＸ軸およびＹ軸を正しく設定することが目的となる。
（ｃ）図１１に示すように、バウンディングボックスＢＢ１の内外に格子を設定する。格子は、横方向のＸラインおよび縦方向のＹラインにより構成される。この格子のラインの間隔は、予め決めておく。バウンディングボックスＢＢ１の横方向（Ｘ軸方向）にＸラインを伸ばし、間隔Ｈｘ毎にＹラインを引く。
【００６０】
バウンディングボックスＢＢ１の境界とＸラインの交点、およびバウンディングボックスＢＢ１外にあるＹラインとＸラインとの交点のＺ値が境界値となる。境界値は図１１において黒丸で示されている。この境界値は、格子点を３次元データＴＤ５のポリゴンに射影させることによって求めることができる。
（ｄ）境界値から評価値Ｅを計算する。評価値Ｅの計算方法は後で述べる。
（ｅ）Ｚ軸を中心に一定角度θだけ回転させ、３次元データＴＤ５に対して元の座標系に戻るよう座標逆変換を行い、上の（ｂ）に戻る。それを９０度回転するまで繰り返す。
（ｆ）求めた評価値Ｅの中で最小（または最大）になる角度θを、最適な角度として選定する。上の（ａ）で設定したＸ軸およびＹ軸を、求めた最適な角度θだけＺ軸を中心に回転させ、回転させたＸ軸およびＹ軸をそれぞれ辺にするような平面を生成する。
【００６１】
つまり、評価値Ｅが最小（または最大）となる角度θだけ回転させることにより、平面が３次元データＴＤ５の周面に沿った配置となる。例えば、図４に示す３次元データＴＤ２の場合には、面ＭＥ２と円柱の周面との間隔が均等になる方向に面ＭＥ２の向きが決定される。なお、配置された平面は、適当な方法で３次元データＴＤの形状に沿った曲面に変形することができる。
【００６２】
次に、評価値Ｅの計算方法を説明する。
〔評価値の計算方法その１〕
この方法では、傾きの差から評価値Ｅを求める。
【００６３】
図１２は傾きの差から評価値Ｅを求める方法を説明するための図である。
Ｘライン毎に注目する（図１１参照）。図１２に示すように、バウンディングボックスＢＢ１の左側の境界値Ｌｚ０，１，２と右側の境界値Ｒｚ０，１，２とから、それぞれ傾きを求め、傾きの平均gradＬ、gradＲを求める。これに基づいて評価値Ｅを計算する。
【００６４】
ｉ番目のＸライン上にある境界値に注目する。バウンディングボックスＢＢ１の左側および右側の境界値で、２つの連続する境界値から傾きの平均gradＬi 、gradＲi を、次の式で求める。ここで、左側では左向きを正の方向、右側では右向きを正の方向とする。つまり、バウンディングボックスＢＢ１から遠ざかる方向を正の向きとする。なお、ｍは境界値の個数を示す。
【００６５】
【数１６】
0004106839.tif 000017
そして、gradＬi 、gradＲi の差の二乗を計算する。
【００６６】
Ｅi ＝（gradＬi −gradＲi ）2 
Ｘラインがｎ本あった場合に、評価値Ｅは次のように計算される。
【００６７】
【数１７】
0004106839.tif 000018
つまり、Ｘライン毎に計算した左右の傾きの差の二乗平均を評価値Ｅとする。平面（面ＭＥ）が左右に同じように傾いている場合に、評価値Ｅは小さくなる。したがって、評価値Ｅが最小となるような角度θだけ回転させればよいことになる。
〔評価値の計算方法その２〕
この方法も、傾きの差から評価値Ｅを求める。
【００６８】
上に説明したその１と同様に計算するが、このときにｘ方向の正の向きを、左右について同じ方向に設定する。つまり、図１２において、例えば左側の境界値の傾きの向きを、右側と同じ右向きを正の向きとする。このようにすると、周面の曲面でない方向（円柱の軸方向）に沿って平面が配置される。
〔評価値の計算方法その３〕
この方法では、傾きの大きさを計算する。
【００６９】
Ｘライン上に存在する連続する２つの境界値から傾きを計算する。すべてについて傾きを計算し、それの大きさ（絶対値）の平均を評価値Ｅとする。評価値Ｅが最小となるように決定する。評価値Ｅが小さいほど、傾きが小さくなる。評価値Ｅは次の式で示される。
【００７０】
【数１８】
0004106839.tif 000019
ここで、gradは傾きを示す。またnumgrad は求められた傾きの個数であり、これは、次の式で示されるｎの個数だけ存在する。
【００７１】
ｎ＝（Ｘラインの数）×（１つのＸライン上に存在する境界値の数−１）×２〔評価値の計算方法その４〕
この方法では、境界値の分散を計算する。
【００７２】
図１３は境界値の分散から評価値Ｅを求める方法を説明するための図である。図１３において楕円で囲んで示すように、Ｙラインに平行なライン上の境界値に注目する。換言すると、ｘ座標が同じである境界値の集合に注目する。その境界値におけるのｚ値の分散を計算する。それぞれの集合において分散を計算し、その平均を評価値Ｅとする。
【００７３】
ここでも、評価値Ｅが最小となるように決定する。評価値Ｅが小さいほど、各Ｙライン上における境界値のバラツキが小さくなる。
〔評価値の計算方法その５〕
この方法では、境界値の分散を計算する。
【００７４】
図１４は境界値の分散から評価値Ｅを求める方法を説明するための図である。図１４において楕円で囲んで示すように、Ｙラインに平行なラインで、隣り合っている２つのライン上に存在する境界値に注目する。その境界値で、Ｘライン上に乗っている２点から傾きを計算し、すべての傾きから分散を計算する。それぞれの集合において傾きの分散を計算し、その平均を評価値Ｅとする。
【００７５】
ここでも、評価値Ｅが最小となるように決定する。評価値Ｅが小さいほど、各Ｙライン上におけるＸ方向のバラツキが小さくなる。
〔第２の実施形態の第２実施例〕
図１５は第２の実施形態の第２実施例におけるバウンディングボックスＢＢ２の状態を示す図である。
【００７６】
第２実施例では、欠落部分の有無に関係なく、新たに面を形成したい任意の部分に平面をはりつける例について説明する。
すなわち、第２の実施例では、３次元データＴＤ６に対して格子状の平面を生成する際に、３次元データＴＤ６の形状の状態を考慮して、形状に沿った方向に平面方向（平面の座標軸の方向）を設定する。
【００７７】
次に示す（ａ）〜（ｃ）の処理を行う。
（ａ）３次元データＴＤ６で面を生成したい領域のポリゴンを選択する。
（ｂ）選択状態にあるポリゴンの法線ベクトルの平均値を計算する。
【００７８】
その平均値を、生成する平面の座標系でのＺ軸方向として設定する。Ｘ軸およびＹ軸を適当な方向にとって設定する。例えば、フィットさせる平面と元の座標系のＸＹ平面との交線をＸ軸に設定する。そして、３次元データＴＤ６を、新しく設定したＸＹＺ座標系に変換する。以降において、この新しい座標系におけるＸＹ平面上で考えていく。
（ｃ）設定したＸ軸を横方向、Ｙ軸を縦方向とする、ポリゴンの選択部分に対するバウンディングボックスＢＢ２を生成する。バウンディングボックスＢＢ２のＸ軸およびＹ軸を求めることが目的となる。
【００７９】
この軸の決定法は、第２の実施形態の第１実施例に示す（ｃ）〜（ｆ）と同様である。
〔第３の実施形態の詳細〕
第３の実施形態では、上にも述べたように、生成する平面の格子点の密度、すなわち例えば格子点の個数および間隔を自動的に決定する。なお、生成する平面の方向（Ｘ軸方向およびＹ軸方向）は、例えば第１の実施形態または第２の実施形態に述べた方法により決定しているものとする。
〔第３の実施形態の第１実施例〕
図１６は第３の実施形態の第１実施例の３次元データＴＤ７の頂点の状態を示す図である。
【００８０】
３次元データＴＤ７の欠落部分ＫＲ７に対して、次に示す（ａ）〜（ｄ）の処理を行う。
（ａ）３次元データＴＤ７の欠落部分ＫＲ７を多角形ポリゴンととらえ、その多角形ポリゴンを構成する頂点Ｐ０，１，２…について、隣り合う２つの頂点からなるベクトルを考える。
（ｂ）そのベクトルの向きが、平面生成のために決定した座標系におけるｘ軸方向に近いベクトルか、またはｙ軸方向に近いベクトルかを選別して分類する。
【００８１】
具体的には、そのベクトルを正規化し、ｘ成分とｙ成分との絶対値を比較し、ｘ成分の方が大きければｘ軸方向に近いベクトルに分類し、ｙ成分の方が大きければｙ軸方向に近いベクトルに分類する。この選別をすべてのベクトルについて行う。
（ｃ）ｘ軸方向に近いベクトルに分類されたベクトルについて、ｘ成分の平均値をとる。同様に、ｙ軸方向に近いベクトルに分類されたベクトルについて、ｙ成分の平均値をとる。この２つの平均値を、理想的な格子のＸ方向およびＹ方向の間隔とし、それぞれをｘspace 、ｙspace とする。
（ｄ）欠落部分ＫＲ７に対するバウンディングボックスＢＢの縦横の長さをそれぞれＨ、Ｗとすると、発生させる格子点の個数num ｘ、num ｙは、次の式ようになる。
【００８２】
num ｘ＝Ｗ／ｘspace
num ｙ＝Ｈ／ｙspace
num ｘおよびnum ｙで割り切れない場合は四捨五入する。
【００８３】
また、num ｘ、num ｙが１になってしまった場合は、格子状の平面を生成することができないので、その場合は２にする。
〔第３の実施形態の第２実施例〕
図１７は第３の実施形態の第２実施例における３次元データＴＤ８の状態を示す図である。
【００８４】
第２実施例では、欠落部分の有無に関係なく、新たに面を形成したい任意の部分に平面をはりつける例について説明する。
（ａ）３次元データＴＤ８で面を生成したい領域のポリゴンを選択する。
（ｂ）選択状態にあるポリゴンと非選択状態にあるポリゴンとの境界となっている項点で、隣り合うふたつの頂点からなるベクトルを考える。
【００８５】
そのベクトルを利用して格子点の個数を決定する。その決定方法は、第３の実施形態の第１実施例に示した（ｂ）〜（ｄ）と同様である。
上に述べたように、本実施形態の３次元処理装置１によると、３次元データＴＤの欠落部分の穴埋め処理、または任意の面を形成する場合などにおいて、新たな面の向きなどを自動的に決定し、より自然な３次元形状データを生成することができる。
【００８６】
上の述べた実施形態において、３次元処理装置１の全体または各部の構成、処理内容、処理順序、３次元データＴＤの形状などは、本発明の趣旨に沿って適宜変更することができる。
【００８７】
【発明の効果】
本発明によると、３次元データの欠落部分の穴埋め処理または任意の面を形成する処理などにおいて、新たな面の向きなどを自動的に決定し、より自然な３次元形状データを生成することができる。
【図面の簡単な説明】
【図１】本発明の実施形態に係る３次元処理装置の概略構成を示すブロック図である。
【図２】３次元データに対して面生成を行う第１の実施形態を説明するための図である。
【図３】第１の実施形態の面生成処理を示すフローチャートである。
【図４】３次元データに対して面生成を行う第２の実施形態を説明するための図である。
【図５】第２の実施形態の面生成処理を示すフローチャートである。
【図６】３次元データに対して面生成を行う第３の実施形態を説明するための図である。
【図７】第３の実施形態の面生成処理を示すフローチャートである。
【図８】３次元データの欠落部分の周囲のベクトルを示す図である。
【図９】Ｘ軸およびＹ軸とＸ’軸およびＹ’軸との関係を示す図である。
【図１０】第２の実施形態の第１実施例におけるバウンディングボックスの状態を示す図である。
【図１１】バウンディングボックスに設定したＸラインおよびＹラインを示す図である。
【図１２】傾きの差から評価値を求める方法を説明するための図である。
【図１３】境界値の分散から評価値を求める方法を説明するための図である。
【図１４】境界値の分散から評価値を求める方法を説明するための図である。
【図１５】第２の実施形態の第２実施例におけるバウンディングボックスの状態を示す図である。
【図１６】第３の実施形態の第１実施例の３次元データの頂点の状態を示す図である。
【図１７】第３の実施形態の第２実施例における３次元データの状態を示す図である。
【符号の説明】
１  ３次元処理装置
ＴＤ  ３次元データ（３次元形状データ）
ＢＢ  バウンディングボックス
ＫＲ  欠落部分
【図１】
0004106839.tif 000020
【図２】
0004106839.tif 000021
【図３】
0004106839.tif 000022
【図４】
0004106839.tif 000023
【図５】
0004106839.tif 000024
【図６】
0004106839.tif 000025
【図７】
0004106839.tif 000026
【図８】
0004106839.tif 000027
【図９】
0004106839.tif 000028
【図１０】
0004106839.tif 000029
【図１１】
0004106839.tif 000030
【図１２】
0004106839.tif 000031
【図１３】
0004106839.tif 000032
【図１４】
0004106839.tif 000033
【図１５】
0004106839.tif 000034
【図１６】
0004106839.tif 000035
【図１７】
0004106839.tif 000036