(57)【要約】【課題】製品内部の隙間空間を３次元的に高速可視化し、その隙間空間の体積計算を高速化する。【解決手段】３次元の製品モデルを含む計算領域を設定し、その計算領域から複数の断面画像を切り出す。各断面画像を複数のボクセルデータに分割し、該ボクセルデータから製品内部の隙間領域のボクセルデータを生成する。各断面画像から得られた隙間領域のボクセルデータを基に、製品内部の隙間領域の３次元モデルを生成すると共に、製品内部の隙間領域の体積を計算する。【選択図】図２
2007334820.tif 000002
【特許請求の範囲】
【請求項１】
製品の３次元モデルの表面データから、複数の断面画像を切り出す断面画像切出し手段と、
該断面画像切出し手段により切り出された断面画像を、部品領域と隙間領域に分ける断面画像処理手段と、
該断面画像処理手段により得られた断面画像を積層して、３次元格子データを生成する３次元格子データ生成手段と、
該３次元格子データ生成手段により生成された３次元格子データを基に、製品内部の隙間空間の３次元モデルを生成する３次元モデル生成手段と、
を備えることを特徴とする３次元モデルの画像処理装置。
【請求項２】
請求項１記載の３次元モデルの画像処理装置であって、
前記断面画像処理手段は、前記断面画像の凸包構成を計算し、その計算結果を基に、凸包内部から隙間領域を抽出することを特徴とする。
【請求項３】
請求項１記載の３次元モデルの画像処理装置であって、
さらに、製品の一部を指定する部分指定手段を備え、
前記断面画像切出し手段は、該部分指定手段によって指定された部分の断面画像のみを切り出し、
前記断面画像処理手段、前記３次元格子データ生成手段及び前記３次元モデル生成手段は、前記断面画像切出し手段によって切り出された断面画像について、それぞれの処理を行うことを特徴とする。
【請求項４】
製品の３次元モデルの表面データから、複数の断面画像を切り出す断面画像切出し手段と、
該断面画像切出し手段により切り出された断面画像を、部品領域と隙間領域に分ける断面画像処理手段と、
該断面画像処理手段により得られた断面画像を積層して、３次元格子データを生成する３次元格子データ生成手段と、
該３次元格子データ生成手段により生成された３次元格子データを基に、製品内部の隙間空間の体積を計算する体積計算手段と、
を備えることを特徴とする３次元モデルの画像処理装置。
【請求項５】
請求項４記載の３次元モデルの画像処理装置であって、
前記断面画像処理手段は、前記断面画像の凸包構成を計算し、その計算結果を基に、凸包内部から隙間領域を抽出することを特徴とする。
【請求項６】
請求項４記載の３次元モデルの画像処理装置であって、
さらに、製品の一部を指定する部分指定手段を備え、
前記断面画像切出し手段は、該部分指定手段によって指定された部分の断面画像のみを切り出し、
前記断面画像処理手段、前記３次元格子データ生成手段及び前記体積計算手段は、前記断面画像切出し手段によって切り出された断面画像について、それぞれの処理を行うことを特徴とする。
【請求項７】
製品の３次元モデルの表面データから、複数の断面画像を切り出す第１のステップと、
該第１のステップにより切り出された断面画像を、部品領域と隙間領域に分ける第２のステップと、
該第２のステップにより得られた断面画像を積層して、３次元格子データを生成する第３のステップと、
該第３のステップにより生成された３次元格子データを基に、製品内部の隙間空間の３次元モデルを生成する第４のステップと、
から成る処理をコンピュータに実行させるプログラム。
【請求項８】
製品の３次元モデルの表面データから、複数の断面画像を切り出す第１のステップと、
該断面画像切出し手段により切り出された断面画像を、部品領域と隙間領域に分ける第２のステップと、
該第２のステップにより得られた断面画像を積層して、３次元格子データを生成する第３のステップと、
該第３のステップにより生成された３次元格子データを基に、製品内部の隙間空間の体積を計算する第４のステップと、
から成る処理をコンピュータに実行させることを特徴とするプログラム。（８）
【請求項９】
製品の３次元モデルの表面データから、複数の断面画像を切り出す断面画像切出し手段と、
該断面画像切出し手段により切り出された断面画像を、部品領域と隙間領域に分ける断面画像処理手段と、
該断面画像処理手段により得られた断面画像を積層して、３次元格子データを生成する３次元格子データ生成手段と、
該３次元格子データ生成手段により生成された３次元格子データを基に、製品内部の隙間空間の３次元モデルを生成する３次元モデル生成手段と、
該３次元格子データ生成手段により生成された３次元格子データを基に、製品内部の隙間空間の体積を計算する体積計算手段と、
を備えることを特徴とする３次元モデルの画像処理装置。
【請求項１０】
製品の３次元モデルの表面データから、複数の断面画像を切り出すステップと、
該断面画像切出し手段により切り出された断面画像を、部品領域と隙間領域に分けるステップと、
該断面画像処理手段により得られた断面画像を積層して、３次元格子データを生成するステップと、
該３次元格子データ生成手段により生成された３次元格子データを基に、製品内部の隙間空間の３次元モデルを生成するステップと、
から成る処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元モデルの画像処理に係り、特に製品内部の隙間空間の３次元モデルに関する画像処理装置に関する。
【背景技術】
【０００２】
ノートパソコン（ノート型パーソナルコンピュータ）、ＰＤＡ（携帯情報端末）、さらには、携帯電話、携帯型音楽プレーヤなどの小型電子機器において、軽量・小型化に対する要求が高まってきている。これらの電子機器の製品設計は、ＣＡＤ(Computer Aided Design)により行われる。製品の小型化には、部品を高密度に実装することが不可欠であり、そのためには、製品内部の隙間を最小限にすることが必要である。
【０００３】
従来、製品内部の隙間を可視化する技術として、３次元モデルの断面画像を表示する方法があった。また、製品内部の隙間体積を測定する技術として、その測定機能を備えた機械系３次元ＣＡＤがあった。この３次元ＣＡＤは、３次元モデルの積和演算機能を備えており、製品全体のモデルの体積から全ての部品モデルの体積を減算することで、製品内部の隙間空間の体積を正確に計算することができる。
【０００４】
ところで、本発明に関連する技術としては、ボクセルデータを用いて３次元格子データを生成する装置（特許文献１）や、立体配置モデルにおける実体領域と空洞領域とをもつ初期断面モデルを把握して、鋳型断面モデルを規定する方法（特許文献２）がある。また、ボクセルデータを用いた３次元モデルの高速生成方法として、マーチングキューブス法が知られている（特許文献３、４参照）
【特許文献１】特許第３２６５８７９号公報
【特許文献２】特開２０００−２４７５４号公報
【特許文献３】米国特許４，８８５，６８８
【特許文献４】米国特許４，７１０，８７６
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上記従来の３次元モデルの断面画像の表示方法では、２次元的にしか隙間を可視化することはできなかった。このため、製品内部の隙間を正確に把握するのが困難であった。また、上記従来の３次元ＣＡＤによる隙間空間の体積計算では、製品全体のモデルを作成する必要があり、この作成作業の負担が大きく、作業時間にも多大な時間を費やす必要があった。また、３次元ＣＡＤは、ソリッドモデルで３次元形状を表現しているため、隙間空間の体積計算に多大な時間を要するという問題があった。
【０００６】
本発明の目的は、製品内部の隙間空間を３次元的に可視化できるようにすることである。本発明の別の目的は、製品内部の隙間空間の３次元モデルを高速に生成することである。また、本発明の別の目的は、該３次元モデルを利用して、製品内部の隙間空間の体積を高速に計算できるようにすることである。
【課題を解決するための手段】
【０００７】
本発明の３次元モデルの画像処理装置の第１態様は、断面画像切出し手段、断面画像処理手段、３次元格子データ生成手段及び３次元モデル生成手段を備える。
前記断面画像処理手段は、製品の３次元モデルの表面データから、複数の断面画像を切り出す。前記断面画像処理手段は、該断面画像切出し手段により切り出された断面画像を、部品領域と隙間領域に分ける。前記３次元格子データ生成手段は、該断面画像処理手段により得られた断面画像を積層して、３次元格子データを生成する。前記３次元モデル生成手段は、該３次元格子データ生成手段により生成された３次元格子データを基に、製品内部の隙間空間の３次元モデルを生成する。
【０００８】
本発明の３次元モデルの画像処理装置の第１態様によれば、製品の３次元モデルの表面データから製品の隙間空間の３次元モデルを生成するので、隙間空間の３次元モデルを可視化でき、しかもその３次元モデルを高速に生成できる。
【０００９】
本発明の３次元モデルの画像処理装置の第２態様は、上記第１態様において、前記断面画像処理手段は、前記断面画像の凸包構成を計算し、その計算結果を基に、凸包内部から隙間領域を抽出する。
【００１０】
本発明の３次元モデルの画像処理装置の第２態様によれば、凸包構成を利用することにより、製品内部と製品外形を明確に区別して、製品内部の隙間空間を正確に抽出できる。
本発明の３次元モデルの画像処理装置の第３態様は、前記第１態様において、さらに、製品の一部を指定する部分指定手段を備える。そして、前記断面画像切出し手段は、該部分指定手段によって指定された部分の断面画像のみを切り出し、前記断面画像処理手段、前記３次元格子データ生成手段及び前記３次元モデル生成手段は、前記断面画像切出し手段によって切り出された断面画像について、それぞれの処理を行う。
【００１１】
本発明の３次元モデルの画像処理装置の第３態様によれば、製品の３次元モデルの表面データから、製品内部の望む部分における隙間空間の３次元モデルを可視化でき、しかもその３次元モデルを高速に生成することができる。
【００１２】
本発明の３次元モデルの画像処理装置の第４態様は、断面画像切出し手段、断面画像処理手段、３次元格子データ生成手段及び体積計算手段を備える。
断面画像切出し手段は、製品の３次元モデルの表面データから、複数の断面画像を切り出す。前記断面画像処理手段は、該断面画像切出し手段により切り出された断面画像を、部品領域と隙間領域に分ける。前記３次元格子データ生成手段は、該断面画像処理手段により得られた断面画像を積層して、３次元格子データを生成する。前記体積計算手段は、該３次元格子データ生成手段により生成された３次元格子データを基に、製品内部の隙間空間の体積を計算する。
【００１３】
本発明の第４態様によれば、製品の３次元モデルの表面データを基に、製品内部の隙間空間の体積を高速に計算できる。
本発明の３次元モデルの画像処理装置の第５態様は、上記第４態様において、前記断面画像処理手段は、前記断面画像の凸包構成を計算し、その計算結果を基に、凸包内部から隙間領域を抽出する。
【００１４】
本発明の第５態様によれば、凸包構成を利用することにより、製品内部と製品外形を明確に区別して、製品内部の隙間空間の体積を正確に計算できる。
本発明の３次元モデルの画像処理装置の第６態様は、上記第４態様において、さらに、製品の一部を指定する部分指定手段を備える。そして、前記断面画像切出し手段は、該部分指定手段によって指定された部分の断面画像のみを切り出し、前記断面画像処理手段、前記３次元格子データ生成手段及び前記体積計算手段は、前記断面画像切出し手段によって切り出された断面画像について、それぞれの処理を行う。
【００１５】
本発明の第６態様によれば、製品の３次元モデルの表面データを基に、製品内部の望む部分の隙間空間の体積を高速に計算できる。
本発明の第７態様の３次元モデルの画像処理装置は、断面画像切出し手段、断面画像処理手段、３次元格子データ生成手段、３次元モデル生成手段及び体積計算手段を備える。
【００１６】
前記断面画像切出し手段は、製品の３次元モデルの表面データから、複数の断面画像を切り出す。前記断面画像処理手段は、該断面画像切出し手段により切り出された断面画像を、部品領域と隙間領域に分ける。前記３次元格子データ生成手段は、該断面画像処理手段により得られた断面画像を積層して、３次元格子データを生成する。前記３次元モデル生成手段は、該３次元格子データ生成手段により生成された３次元格子データを基に、製品内部の隙間空間の３次元モデルを生成する。前記体積計算手段は、該３次元格子データ生成手段により生成された３次元格子データを基に、製品内部の隙間空間の体積を計算する。
【００１７】
本発明の第７態様によれば、製品の３次元モデルの表面データを基に、製品内部の隙間空間の３次元モデルを可視化でき、しかも、その３次元モデルを高速に生成できる。さらに、製品内部の隙間空間の体積を高速に計算できる。  
【発明の効果】
【００１８】
本発明によれば、製品の３次元モデルの表面データから断面画像を生成し、各断面画像を隙間領域と部品領域に分る。そして、各断面画像を積層して、３次元の格子データを生成し、その３次元格子データを基に、製品内部の隙間領域の３次元モデルを生成する。また、その３次元格子データを基に、製品内部の隙間領域の体積を計算する。
【００１９】
したがって、製品内部の隙間空間の３次元モデルを高速に生成し、該隙間空間を３次元的に可視化することができる。また、製品内部の隙間空間の体積を高速に計算することができる。
【発明を実施するための最良の形態】
【００２０】
以下、図面を参照しながら本発明について説明する。
［本発明の原理］
本発明は、例えば、部品形状を３次元モデルを含む３次元空間を格子構造で表現する。また、サーフェイスモデル(surface model)により３次元モデルの形状を表現し、その３次元モデルの表面データを、部品内部の格子と部品外部の格子に分け、部品外部の格子を隙間空間（隙間領域）の格子として抽出する。
【００２１】
このように、隙間空間を格子構造で表現することで、製品の３次元モデルの生成と製品の体積計算の高速化が可能となる。
例えば、格子として直交格子を用いると、３次元構造はボクセルデータとなり、３次元モデルは、隙間空間の表面のボクセルから生成することができる。この生成には、公知のマーチングキューブス法などの高速な３次元モデルの生成方法などを利用することができる。また、製品の体積は、隙間空間のボクセルを計数することで算出可能である。
【００２２】
ボクセルデータの分解能を調整することで、精度を変化させて、製品のモデル化及び製品の体積計算を実施することが可能である。つまり、製品全体を粗く調べたいときは、分解能を低くして（ボクセルサイズを大きくして）、体積計算を行う。逆に、製品全体を詳細に調べたいときは、分解能を高くして（ボクセルサイズを小さくして）、体積計算を行う。この場合、製品調査の粗密の度合いをモデル形状に合わせて変化させることで、体積計算を効率よく実行可能である。すなわち、表面形状が単純な部分は粗いボクセルで、複雑な部分は細かいボクセルで、それぞれ表現することで、精度を保ちつつ、ボクセル数を減らすことができる。
【００２３】
ボクセルデータを高速に生成する最も簡単な方法の一つとして、例えば、部品モデルの表面データから、各格子が部品の外部か内部かを判定していく方法がある。しかしながら、この方法の場合、部品数や格子数が多くなると、処理コストが非常に大きくなる。
【００２４】
本発明では、３次元モデルの断面を切り出し、この断面表示において、部品内部を塗りつぶして描画することにより、断面画像から隙間部分を簡単に抽出する。抽出した隙間画像を積層することで、隙間のボクセルデータを構築する。この断面画像の生成は、グラフィックス・ハードウェアを利用できるので、高速化が可能である。
【００２５】
図１は、本発明の原理を示す模式図である。
同図（ａ）は、３次元の製品モデル１の全体を斜め上方から見た俯瞰図である。
この製品モデル１を、同図（ｂ）に示す鉛直方向の切断平面２を用いて幾層にも切り出す。同図（ｃ）は、切断平面２により切り出された断面画像３の一つを示す図である。この断面画像３において、黒の着色部分は部品領域、白い部分は隙間領域をそれぞれ示している。
【００２６】
次に、断面画像３を  同図（ｄ）に示すように格子上に分割し、それそれの格子を黒画素と白画素で表現する。同図（ｄ）において、“１”の格子は黒画素、“０”の格子は白画素である。この例では、断面画像３を、縦８×横８の６４個の格子で区切っている。断面画像３における隙間領域は、白画素、つまり、“０”の画素の連結領域を求めることにより抽出できる。
上記の例は、断面画像が白黒画像である場合の例であるが、カラー画像である場合には、格子をＲ、Ｇ、Ｂの各色の画素値で表現するようにしてもよい。
【００２７】
［実施形態］
｛概略｝
図２は、本発明の実施形態（以下、本実施形態）の概略を説明する図である。
図２では、３次元の製品モデルの一例として、ノートパソコンを取り上げている。
同図（ａ）に示すように、隙間領域の生成及び体積計算の対象である３次元製品モデル１１に対して、その全体を囲む計算領域１２（破線で示された部分）を設定する。次に、計算領域１２に対して、複数の切断平面１３を設定する。続いて、同図（ｄ）に示すように、計算領域１２と各切断平面１３との交差平面の画像を、断面画像１４として生成する。そして、同図（ｄ）に示すように、複数の断面画像１４を積層して、ボクセルデータ１５を生成する。このボクセルデータ１５は、例えば、マーチングキューブス法により生成する。
【００２８】
本実施形態では、このようにして生成したボクセルデータ１５を基に、後述する方法により、３次元製品モデル１１の隙間領域の表面データを生成し、さらに、その隙間領域の体積を計算する。
【００２９】
｛システム構成｝
図３は、本実施形態のハードウェアのシステム構成を示す図である。
本実施形態は、ＣＰＵ２１、ユーザ入力装置２２、グラフィックスボード２３、記憶装置２４及びディスプレイ２５を備えている。
【００３０】
記憶装置２４は、ストレージであり、ＨＤＤ（ハードディス駆動装置）や光ディスク駆動装置、さらには、ＣＤやＤＶＤなどの可搬型記憶媒体駆動装置等の外部記憶装置から構成されている。記憶装置２４は、ＢＩＯＳ（基本入出力システム）などのファームウェアや、基本ソフト（ＯＳ）、周辺装置のドライバ、さらには、製品モデルの隙間領域の生成や該隙間領域の体積計算など行う手順が記述された本実施形態のプログラムなどのソフトウェアを格納している。
【００３１】
ＣＰＵ２１は、記憶装置２４に記憶されている上記ソフトウェアを実行して、システム全体を制御すると共に、ユーザ入力処理、画面表示処理などを行い、３次元モデルの生成や３次元モデルの体積計算を行う。尚、ＣＰＵ２１は、内部にメモリを備えている。
【００３２】
ユーザ入力装置２２は、例えば、キーボードやマウスなどのポインティングデバイスなどから構成されている。本実施形態のユーザは、ユーザ入力装置２２を介して本実施形態のシステムを起動させ、各種データの設定やコマンド入力などを行う。
【００３３】
グラフィックスボード２３は、ＧＰＵ(Graphic Processor Unit)２３１とフレームバッファ２３２を備えており、ディスプレイ２５に表示する画像データの描画処理を行う。ＧＰＵ２３１は、描画処理専用のプロセッサである。フレームバッファ２３２は、ＧＰＵ２３１が生成するディスプレイ２５の表示データを格納するメモリである。フレームバッファ２３２は、ディスプレイ２５に表示されるグラフィックスデータを、例えば、ビットマップ形式で格納する。
【００３４】
ディスプレイ２５は、例えば、ＣＲＴやＬＣＤなどの薄型表示装置から成り、ＧＰＵ２３１から送られてくる画像データをスクリーンに表示する。本実施形態では、３次元モデルやその断面画像などを表示する。
【００３５】
｛ソフトウェア構成｝
図４は、上記ハードウェア構成を有する本実施形態のソフトウェア構成を示す図である。
【００３６】
本実施形態のソフトウェア構成は、機能的に、入力機能３０、計算機能４０及び出力機能５０に大別される。入力機能３０は、表面データ入力部３１と計算条件入力部３２で構成される。計算機能４０は、断面画像計算部４１、ボクセル計算部４２、表面データ計算部４３及び体積計算部４４から構成される。出力機能５０は、データ保存部５１と描画表示部５２から構成される。
【００３７】
入力機能３０は、ユーザ入力装置２２とＣＰＵ２１のプログラム実行によって実現される。計算機能４０は、記憶装置２４とＣＰＵ２１のプログラム実行によって実現される。出力機能５０は、ＣＰＵ２１のプログラム実行とグラフィックスボード２３によって実現される。
【００３８】
表面データ入力部３１は、製品の３次元モデル（以下、製品モデル）を構築する部品の表面データを入力する。計算条件入力部３２は、製品モデルの体積計算をするために必要な条件を入力する。
【００３９】
断面画像計算部４１は、製品モデルの断面画像を計算（描画）する。ボクセル計算部４２は、断面画像計算部４１によって得られた断面画像を積層してボクセルデータを生成する。表面データ計算部４３は、該ボクセルデータを基にして、製品モデルの隙間領域の３次元モデルの表面データを計算（生成）する。体積計算部４４は、ボクセルデータを基にして、製品モデルの隙間領域の体積を計算する。
【００４０】
データ保存部５１は、断面画像計算部４１、ボクセル計算部４２、表面データ計算部４３及び体積計算部４４によって生成されたデータを保存する。描画表示部５２は、データ保存部５１から断面画像データ、隙間領域の表面データ及び隙間領域の体積計算結果などを読み出し、製品モデルの断面画像、製品の隙間領域の３次元モデル画像及び隙間領域の体積などをディスプレイ２５に表示させる。
【００４１】
｛全体的な処理手順｝
図５は、本実施形態における製品モデルの隙間領域の３次元モデル生成及び体積計算処理の全体的な処理手順を示すフローチャートである。
【００４２】
まず、ユーザ入力装置２２を介して、製品モデルを構成する各部品の表面データを入力する（Ｓ１）。次に、ユーザ入力装置２２を介して、該製品モデルの計算領域(Bounding Box)と該計算領域の分解能を入力する（Ｓ２）。計算領域は、上述したように、製品モデルの計算対象となる領域である。分解能は、検出する最小の隙間の閾値である。ステップＳ１、２における入力は、ユーザ入力装置２２を介して行われる。
【００４３】
本実施形態では、計算領域として、図６に示すような直方体６０を指定する。この直方体（計算領域）６０には、図６の左下に示すような、互いに直交するｘ軸、ｙ軸、ｚ軸から成る３次元座標系（ｘ、ｙ、ｚ）が設定される。この３次元座標系において、原点は直方体６０の底面の左下隅に位置する頂点に設定される。
【００４４】
次に、上記計算領域におけるボクセルサイズとボクセル数を計算する（Ｓ３）。
ボクセルサイズは、１個のボクセルの大きさであり、上記分解能に相当する。ボクセル数は、前記計算領域内でのボクセルの個数である。ステップＳ３では、図７に示すように、ステップＳ２で入力された計算領域と分解能を基に、計算領域６０をボクセル６１で分割し、ｘ軸方向のボクセル数Ｎｘ、ｙ軸方向のボクセル数Ｎｙ及びｚ軸方向のボクセル数Ｎｚを計算する。
【００４５】
続いて、ステップＳ３で得られたボクセルデータの配列ａ［Ｎｘ］［Ｎｙ］［Ｎｚ］を作成する（Ｓ４）。そして、各ボクセルデータの値（ボクセル値）を計算する（Ｓ５）。このボクセル値の計算方法の詳細は後述する。本実施形態では、ボクセル値は“１”または“０”の２値データであり、部品領域内のボクセルデータは“１”、隙間領域のボクセルデータは“０”に設定される。
【００４６】
ステップＳ５で得られたボクセル値を基に、ボクセルデータから隙間領域の３次元モデルの表面データを計算する（Ｓ６）。この表面データの計算方法の詳細についても後述する。ボクセルデータを基に、隙間領域の３次元モデルの体積を計算する（Ｓ７）。この隙間領域の体積計算方法についても後述する。
【００４７】
図５のフローチャートにおいて、ステップＳ３〜Ｓ５の処理は、ＣＰＵ２１が記憶装置２４に格納されている本実施形態のプログラムを実行することにより行われる。また、ステップＳ１、Ｓ２の入力データ処理、ＣＰＵ２１が上記プログラムを実行することにより行われる。
【００４８】
このように、本実施例では、製品の３次元モデルの表面データから製品の３次元モデルの格子データを生成する。そして、その３次元格子データを基に、製品の隙間空間の３次元モデルの生成並びにその隙間空間の体積計算を行う。したがって、該隙間空間の３次元モデルの生成並びに体積計算を高速に実行できる。また、その隙間空間の３次元モデルをディスプレイ２５に表示することで、隙間空間を３次元的に可視化して表示できる。
【００４９】
｛部品表面データ｝
図６のステップＳ１で入力する各部品ｉ（ｉ＝１、２、・・・、ｎ）の表面データ（部品表面データｉ）は、下記に示すように、「部品名」、「部品座標」、「ポリゴンデータの集合」などのパラメータで構成される。
【００５０】
＜部品表面データ１＞
・部品名
・部品座標（ワールド座標に対する部品座標の位置と姿勢）
位置：double Pc[3]，姿勢：double Rc[3],[3]
・ポリゴンデータの集合
ポリゴンデータは、三角形ポリゴンの３つの頂点の位置（部品座標に対する位置）を示すデータである。ポリゴンデータは、下記の形式で指定される。
位置：double Pv0[3]，double Pv1[3]，doublePv2[3]
・・・
＜部品表面データ２＞
・・・
【００５１】
図８に、６個のポリゴンデータ７１で定義された３次元の部品表面データ７０の例を示す。
｛ボクセルデータ表現｝
図９は、計算領域内での製品モデルの隙間空間（隙間領域）の３次元モデルをボクセルデータにより表現する方法を示す図である。
同図に示す計算領域８０は、３２０（＝５×８×８）個のボクセル８１に分割されている。同図では、各ボクセルの頂点を、隙間領域または部品領域のいずれに属すかに応じて、○（隙間領域）と●（部品領域）で示している。
【００５２】
｛ボクセルによる表面の複雑度の表現｝
図１０は、表面形状の複雑度をボクセルの粗密化により表現した図である。
同図に示す計算領域９０おいて、破線で囲まれた部分が隙間空間（隙間領域）の表面データ９１である。表面データ９１は、図面の右半分が単純な形状となっており、左方半分は凹凸のある複雑な形状となっている。この場合、右半分については、４個のボクセル９２を統合した大きなボクセル９３で表現し、左半分については指定された分解能のボクセル９２で表現する。このような表現により、隙間空間の表面データ９１の右半分は８個のボクセルデータで表現でき、その左半分は１５個のボクセルデータ（１２個の隙間領域を示すボクセルデータと３個の部品領域を示すボクセルデータ）で表現できる。
【００５３】
このように、表面を表現する場合、形状が複雑な部分については指定された分解能のボクセルで表現し、形状が単純な部分については指定分解能のボクセルを統合した大きなボクセルで表現することにより、隙間領域の体積計算で使用するボクセルデータの個数を削減できる。
【００５４】
｛ボクセル値計算処理の詳細｝
図１１は、図５のステップＳ５におけるボクセル値計算処理の詳細を示すフローチャートである。
【００５５】
本実施形態では、計算領域をｘ方向にＮｘ個に分割する。したがって、ボクセルのｘ方向の幅ｄｘは、
ｄｘ＝ｉ×Ｗｘ／Ｎｘ＋ｘ_ｍｉｎ                            （１）
ｉ：ｘ方向のインデックス
Ｗｘ：計算領域のｘ方向の幅
ｘ_ｍｉｎ：計算領域のｘ方向の最小値
となる。
【００５６】
本実施形態では、図１１のフローチャートの処理を、ｉ＝１〜Ｎｘについて実行する。
まず、ｘ方向ｉ番目のｘ座標値ｄｘを、上記式（１）により算出する（Ｓ１１）。次に、ｘ＝ｄｘの平面（切断平面）で部品表面を切断した断面図を計算する（Ｓ１２）。
【００５７】
部品表面は三角形ポリゴンデータの集合なので（図８参照）、ステップＳ１２では、各三角形と切断平面との交差を計算する。
ステップＳ１２で得られた断面図の閉じた図形の内部を三角形に分割する（Ｓ１３）。
【００５８】
ステップＳ１２で得た交差線分を接続すると、閉じた図形（多角形）ができるので、これを三角形に分割する。この処理は、表面データを描画するとき該三角形が必要となるために行う。
【００５９】
計算領域内の断面図を、Ｎｙ×Ｎｚ個の画素から成る画像に描画する（Ｓ１４）。
ステップＳ１４での描画はＧＰＵ２３１により実行し、描画データはフレームバッファ２３２に格納する。ＣＰＵ２１で描画計算する場合は内部メモリを使用する。この描画では、部品内部の画素を“１”（黒）、背景（隙間領域）の画素を“０”に設定する。
断面図の画像データＩｍａｇｅ［Ｎｙ］［Ｎｚ］を取得する（Ｓ１５）。
ここで、Ｉｍａｇｅ［Ｎｙ］［Ｎｚ］は断面図の画像データの画素を表す２次元配列である。断面図は、Ｎｙ×Ｎｚ個の画素に分割される。
Ｉｍａｇｅ［ｊ］［ｋ］の値が部品色（“１”）ならばボクセルａ［ｉ］［ｊ］［ｋ］＝１、背景色（“０”）ならばボクセルａ［ｉ］［ｊ］［ｋ］＝０に設定する（Ｓ１６）。
ここで、ｊ、ｋは、それそれ、ｙ方向、ｚ方向のインデックスであり、ｊ＝１〜Ｎｙ、ｋ＝１〜Ｎｚである。
【００６０】
｛ボクセルデータに基づく隙間領域の表面データ計算｝
図１２は、図５のステップＳ６における処理の詳細を示すフローチャートである。
図１２のフローチャートの処理は、ｉ＝１〜Ｎｘ−１、Ｎｙ＝１〜Ｎｙ−１、ｋ＝１〜Ｎｚ−１について実行する。
【００６１】
ａ［ｉ］［ｊ］［ｋ］、ａ［ｉ］［ｊ］［ｋ＋１］、ａ［ｉ］［ｊ＋１］、ａ［ｉ］［ｊ＋１］［ｋ］、ａ［ｉ］［ｊ＋１］［ｋ＋１］、ａ［ｉ＋１］［ｊ］［ｋ］、ａ［ｉ＋１］［ｊ＋１］［ｋ］、ａ［ｉ＋１］［ｊ＋１］、ａ［ｉ＋１］［ｊ＋１］［ｋ＋１］の８個のボクセルの中心を頂点とする直方体（セル）を構成する（Ｓ２１）。図１３に、上記セルの構成を示す。
【００６２】
上記セルの８個の頂点Ｖｍ(ｍ＝１〜８)のボクセル値Ｃｍを取得する（Ｓ２２）。図１４に、セルの頂点Ｖ１〜Ｖ８を示す。
マーチングキューブス法などを利用して、｛Ｃ１、Ｃ２、…、Ｃ８｝の組み合わせに対応する三角形パターンを検索・取得する（Ｓ２３）。
【００６３】
該三角形パターンは、一個の三角形パターンだけでなく、複数の三角形パターンで構成される多角形のパターンも示す。ステップＳ２３では、記憶装置２４に、予め、図１５（ａ）、（ｂ）、…、（ｏ）に示すような各種三角形パターンを有するセルを登録しておき、この登録データを検索することで、対応する三角形パターンを取得する。
ステップＳ２３で取得した各三角形パターン（三角形）の頂点位置を計算する（Ｓ２４）。そして、頂点位置情報を有する三角形データを記憶装置２４に保存する（Ｓ２５）。
【００６４】
｛ボクセルデータを基にした隙間領域の体積計算｝
図１６は、図５のステップＳ７における処理の詳細を示すフローチャートである。
セルの頂点はＶ１〜Ｖ８の８個であり、それら各頂点Ｖｍ（ｍ＝１〜８）のボクセル値Ｃｍは“０”か“１”の２通りである。したがって、８個の頂点Ｖ１〜Ｖ８のボクセル値の組み合わせは２５６通りである。つまり、セル内部の体積が取りうる値は２５６通りとなる。本実施例では、このセル内部の体積値が２５６種類のパターンを「体積パターン」と定義する。そして、これらの各体積パターンの数を個別に計数するためのカウンタｃｎｔ［ｐ］（ｐ＝１〜２５６）を、ＣＰＵ２１のメモリ内に設ける。
【００６５】
図１６のフローチャートの説明を始める。
まず、上記２５６個のカウンタｃｎｔ［ｐ］（ｐ＝１〜２５６）を“０”に初期設定する（Ｓ３１）。
【００６６】
次に、下記のステップＳ３２〜Ｓ３５の処理を、ｉ＝１〜Ｎｘ−１、ｊ＝１〜Ｎｙ−１、ｋ＝１〜Ｎｚ−１に対して実行する。
８個のボクセルａ［ｉ］［ｊ］［ｋ］，ａ［ｉ］，［ｊ］［ｋ＋１］，ａ［ｉ］［ｊ＋１］，［ｋ＋１］，ａ［ｉ＋１］［ｊ］［ｋ］，ａ［ｉ＋１］［ｊ］［ｋ＋１］，ａ［ｉ＋１］［ｊ＋１］［ｋ］，ａ［ｉ＋１］［ｊ＋１］［ｋ］，ａ［ｉ＋１］［ｊ＋１］［ｋ＋１］の中心を原点とするセルを構成する（ステップＳ３２）。
【００６７】
次に、上記セルの８個の頂点Ｖｍ（ｍ＝１〜８）のボクセル値Ｃｍを取得し（Ｓ３３）、｛Ｃ１、Ｃ２、…、Ｃ８｝の組み合わせに対応する体積パターンｐを検索する（Ｓ３４）。８個のボクセル値Ｃ１〜Ｃ８の組み合わせに対応する体積パターンｐは、記憶装置２４内に、予め、データベースとして登録しておく。このデータベースの構成については、後述する。
【００６８】
ステップＳ３４で検索された体積パターンｐに対応するカウンタｃｎｔ［ｐ］の値を１つインクリメントする（Ｓ３５）。
計算領域内の全てのセルについて、ステップＳ３２〜Ｓ３５の処理が終了すると、体積パターンｐに対する体積Ｖｏｌ［ｐ］を計算する（Ｓ３６）。この体積Ｖｏｌ［ｐ］は、セルの大きさで決まる。体積パターンｐに対応する体積Ｖｏｌ［ｐ］も、上記データベースに登録されている。
そして、ΣＶｏｌ［ｐ］×ｃｎｔ［ｐ］（Σは、ｐ＝１〜２５６の総和）を計算して、その結果である隙間領域の体積を求める（Ｓ３７）。
【００６９】
｛体積パターンに対応する体積の検索用データベース｝
図１７は、図１６のステップＳ３４、Ｓ３６で使用される上記データベースの構成を示す図である。
本実施例では、前述したように、セルの８つの頂点に対して、図１７（ａ）に示すようにＶ１〜Ｖ８の記号を割り当てる。図１７（ｂ）に示すように、データベース１００には、パターン１〜パターン２５６までの２５６種類の体積パターンが登録されており、各体積パターンのそれぞれについて、頂点Ｖ１〜Ｖ８のボクセル値の組み合わせ「｛Ｃ１，Ｃ２，…、Ｃ８｝」と「隙間領域の体積」が登録されている。図１７（ｂ）では、「セルにボクセル値」も図示されているが、これは、セルの各体積パターンにおけるボクセル値をイメージ的に分かりやすいうようにするためのものであり、データベース１００には実際には登録されない。
【００７０】
パターン１は、頂点Ｖ１〜Ｖ８のボクセル値Ｃ１〜Ｃ８が、全て“１”である体積パターンであり、このパターンについて「｛１，１，１，１，１，１，１，１｝」（ボクセル値の組み合わせ）と「０」（隙間領域の体積）が登録されている。また、パターン２は、Ｃ１のみが“０”でＣ２〜Ｃ８が全て“１”である体積パターンであり、その隙間領域に体積は１／４８Ｌである。パターン３は、Ｃ１とＣ２が“０”でＣ３〜Ｃ８が全て“１”である体積パターンであり、その隙間領域に体積は１／８Ｌｄである。ここで、Ｌはセルの体積である。図示してはいないが、パターン４〜２５６についても、「｛Ｃ１，Ｃ２、…，Ｃ８｝」と「隙間領域の体積」がデータベース１００に登録されている。
【００７１】
図１６のステップＳ３４では、｛Ｃ１，Ｃ２，…，Ｃ８｝をキーとしてデータベース１００を検索して体積パターンｐを取得する。ステップＳ３６では、上記取得した体積パターンｐをキーとしてデータベース１００を検索し、隙間領域の体積ＶｏＬ［ｐ］を取得する。
【００７２】
本実施例では、このように、セルのパターンに応じた体積が登録されたデータベースを利用することで、製品内部の隙間空間の体積計算を高速化できる。尚、以後の説明では、説明を簡略化するために、製品内部の隙間空間を、単に隙間空間と記載する場合もある。
【００７３】
｛凸包構成を用いた部品外形の切り出し｝
断面画像は、製品の画像だけでなく、製品外部の画像も含んでいる。本実施例は、断面画像から製品の部品部分の画像のみでなく、製品の外形部分の画像も切り出すことによって、断面画像から製品の隙間領域の画像のみを正確に抽出する。
【００７４】
図１８は、製品の３次元モデルの外形切り出しとして凸包構成を用い、凸包内部から隙間領域を抽出する方法のアルゴリズムを示すフローチャートである。このフローチャートは、ｘ方向にｉ番目に切り出した断面画像に関する処理を示しており、この処理をｉ＝１〜Ｎｘについて実行する。
【００７５】
図１８では、説明の重複を避けるため、図１１のステップＳ１５以降の処理を示している。図１８のステップＳ４１は、１１のステップＳ１５と同様な処理である。
まず、画像データＩｍａｇｅ［Ｎｙ］［Ｎｚ］を取得し（Ｓ４１）、Ｉｍａｇｅ［ｊ］［ｋ］の値（色）が部品色ならＩｍａｇｅ［ｊ］［ｋ］＝１、背景色ならＩｍａｇｅ［ｊ］［ｋ］＝０に設定する。ここで、ｊ＝１〜Ｎｙ−１、ｋ＝１〜Ｎｚ−１である（Ｓ４２）。
【００７６】
ステップＳ４２の処理により、図１９（ａ）に示すように、断面画像１１０において部品（製品）内部の画像１１１が“１”（図中では黒）で塗りつぶされる。
Ｉｍａｇｅ［Ｎｙ］［Ｎｚ］を基に、断面画像１００において画素の値が“０”と“１”の境界にある画素Ｂ（ｊ，ｋ）を抽出する（Ｓ４３）。
【００７７】
ステップＳ４３の処理により、図１９（ｂ）に示すように、断面画像１１０から境界線１１２が抽出される。
前記画素Ｂ（ｊ，ｋ）の集合から凸包構成を計算し、凸包外形を切り出す（Ｓ４４）。この凸包構成の計算には、例えば、「コンピュータ・ジオメトリ  計算幾何学：アルゴリズムと応用」（浅野哲夫訳、２０００年１月１５日  初版発行、近代科学社）に記載されている手法を用いる。
【００７８】
ステップＳ４４の処理により、図１９（ｃ）に示すように、断面画像１１０から凸包外形１１３（図中の太線部分）が抽出される。
凸包外形と境界線１１２から、凸包外形に対して凹んでいる部分を抽出する（ステップＳ４５）。
【００７９】
ステップＳ４５の処理により、図１９（ｄ）に示すように、凸包外形１１３に対する凹み部分１１４ａ、１１４ｂ（図中、破線で囲んだ部分）が抽出される。
上記凹み部分を基に、凸包外形に対する凹みの深さを調べ、その深さが閾値未満ならば元の境界を外形（製品外形）に選択、閾値以上ならば凸包外形を外形に選択する（Ｓ４６）。
【００８０】
ステップＳ４６の処理により、図１９（ｅ）に示すように、凹み部分１１４ａの深さｄ１と、凹み部分１１４ｂの先端から凸包外形１１２までの深さｄ２が閾値以上であるか否かが評価される。そして、ｄ１が閾値未満、ｄ２が閾値以上であれば、凹み部分１１４ａのみが外形と判断される。この結果、図１９（ｆ）に示すように、最終的な部品（製品）の外形１１５が決定される。
【００８１】
断面画像において、前記最終外形より外側にある画素のＩｍａｇｅ［ｉ］［ｊ］を“１”に設定する（Ｓ４７）。
ステップＳ４７の処理により、図１９（ｇ）に示すように、ステップＳ４２で塗りつぶした部分とステップＳ４７で塗りつぶした部分を合成した画像１１６の白い部分が、最終的に製品内部の隙間領域の画像として得られる。
【００８２】
本実施例によれば、凸包構成を利用することにより、断面画像から製品（部品）の外部の画像と内部の画像を区別できるので、製品内部の隙間領域の画像を正確に抽出できる。また、製品表面部に凹み部分がある場合、断面画像において、その凹み部分の画像が製品内部の凹みの画像なのか製品外部の凹みの画像なのか判定して、断面画像から製品内部の凹み部分（製品の隙間領域）の画像をより正確に抽出することができる。
【００８３】
｛セルの合成｝
本実施例では、隣接する２つのセル（直方体）が同じパターンである場合、それらのセルを合成して１つのセルに統合する。これにより、セル数を削減できる。
図２０Ａ、２０Ｂは、そのセル合成のアルゴリズムを示すフローチャートである。
まず、ボクセルデータａ［Ｎｘ］［Ｎｙ］［Ｎｚ］を入力する（Ｓ６１）。次に、セル
の表面データを格納する配列Ｃ［Ｎｘ］［Ｎｙ］［Ｎｚ］を作成する（Ｓ６２）。この配列は、Ｎｘ×Ｎｙ×Ｎｚ個の要素から成る３次元配列である。
【００８４】
続いて、下記のステップＳ６３〜Ｓ６６の処理を、ｉ＝１〜Ｎｘ−１、ｊ＝１〜Ｎｙ−１、ｋ＝Ｎｚ−１に対して実行する。ステップＳ６３〜Ｓ６５の処理は、図１２のステップＳ２１〜Ｓ２３の処理と同じである。
【００８５】
８個のボクセルデータａ［ｉ］［ｊ］［ｋ］，ａ［ｉ］［ｊ］［ｋ＋１］，ａ［ｉ］［ｊ＋１］［ｋ］，ａ［ｉ］［ｊ＋１］［ｋ＋１］，ａ［ｉ＋１］［ｊ］［ｋ］，ａ［ｉ＋１］［ｊ］［ｋ＋１］，ａ［ｉ＋１］［ｊ］［ｋ＋１］，ａ［ｉ＋１］［ｊ＋１］［ｋ］，ａ［ｉ＋１］［ｊ＋１］［ｋ＋１］の中心を原点とするセル（直方体）を構成する（Ｓ６３）。
【００８６】
上記セルの８つの頂点Ｖｍ（ｍ＝１〜８）のボクセル値Ｃｍを取得し（Ｓ６４）、｛Ｃ１、Ｃ２、…、Ｃ８｝の組み合わせに対応するパターンを検索・取得する（Ｓ６５）。そして、セル内の表面データが単一の平面となるパターンならば、その平面のパラメータ（平面パラメータ）を配列Ｃ［ｉ］［ｊ］［ｋ］に格納する（Ｓ６６）。
【００８７】
図２１は、セル内の表面データが単一平面となるパターンの例を示す図である。
同図（ａ）に示すセル１２０内の表面データ１２１は、ｘｙ平面に平行な単一の長方形のみとなっている。同図（ｂ）に示すセル１３０内の表面データ１３１は、ｙｚ平面に平行な長方形となっている。平面の方程式は、ａｘ＋ｂｙ＋ｃＺ＋ｄ＝０であり、上記パラメータは、ａ、ｂ、ｃ、ｄである。ここで、ａ２＋ｂ２＋ｃ２＝１である。
【００８８】
続いて、下記ステップＳ６７〜Ｓ７８の処理を、ｉ＝１〜Ｎｘ−１、ｊ＝１〜Ｎｙ−１、ｋ＝１〜Ｎｚ−１に対して実行する。尚、以後の説明では、前記平面パラメータが格納された配列Ｃ［ｉ］［ｊ］［ｋ］に対応するセルを、セルＣ［ｉ］［ｊ］［ｋ］と表現する。
【００８９】
セルＣ［ｉ］［ｊ］［ｋ］が未連結であるか判別し（Ｓ６７）、未連結であれば、ｉ２＝ｉ，ｊ２＝ｊ，ｋ２＝ｋとする（Ｓ６８）。一方、未連結でなければ、セルセルＣ［ｉ］［ｊ］［ｋ］の処理を終了する（Ｓ７８）。
【００９０】
ステップＳ６８に続いて、配列Ｃ［ｉ２］［ｊ２］［ｋ２］と配列Ｃ［ｉ２＋１］［ｊ２］［ｋ２］が同じ平面パラメータを格納しているか判別し（Ｓ６９）、同じ平面パラメータを格納していればステップＳ７０に移行し、格納していなければステップＳ７１に移行する。
【００９１】
ステップＳ７０では、セルＣ［ｉ２］［ｊ２］［ｋ２］とセルＣ［ｉ２＋１］［ｊ２］［ｋ２］を連結し、ｉ２の値を“１”インクリメントする。その後、ステップＳ６９に戻る。ステップＳ７１では、ｉ２の値を“ｉ”にリセットし、ステップＳ７２に移行する。
【００９２】
ステップＳ６９〜Ｓ７０の処理を、図２２Ａを参照しながら説明する。
セルＣ［ｉ］［ｊ］［ｋ］が図２２Ａ（ａ１）に示すような単一平面１４１ｐを有するセル１４１であるとする。このとき、そのセル１４１のｘ方向の隣接セル１４２（セルＣ［ｉ＋１］［ｊ］［ｋ］）の単一平面１４２ｐが、同図（ｂ１）に示すように、セル１４１の単一平面１４２ｐと同じパターンであれば、これらのセル１４１、１４２を、同図（ｂ２）に示すように連結し、単一平面１５２ｐを有する直方体１５２を作成する。一方、セル１４１のｘ方向の隣接セルが同じ単一平面を有していなければ、図２２Ａ（ａ２）に示すように、セル１４１は隣接セルを連結されない。
【００９３】
続いて、セル１４２のｘ方向の隣接セルについても、セル１４１と同様な処理を行う。そして、図２２Ａ（ｃ１）に示すように、セル１４２の隣接セル１４３が、セル１４２の単一平面１４２ｐと同じパターンの単一平面１４３ｐを有していれば、同図（ｃ２）に示すように直方体１５２にセル１４３を連結し、単一平面１５３ｐを有する直方体１５３を作成する。
【００９４】
以後、同様な処理を、ｉの値が等しい、つまり、セル１４１とｘ方向に平行なセル１４３以降のセルについて、同じ単一平面を有しない隣接セルが出現するまで実施する。この結果、同じパターンの単一平面を有するセルがｘ方向に連続して配置されている場合、それらのセルが連結される。
【００９５】
次に続くステップＳ７２〜Ｓ７３では、ｙ方向について、上述したステップＳ６９〜Ｓ７０と同様の処理を行う。
配列Ｃ［ｉ２］［ｊ２］［ｋ２］と配列セルＣ［ｉ２］［ｊ２＋１］［ｋ２］が同じ平面パラメータを有するか判別し（Ｓ７２）、同じ平面パラメータを有する場合にはステップＳ７３に移行し、同じ平面パラメータを有しない場合にはステップＳ７４に移行する。
【００９６】
ステップＳ７３では、セルＣ［ｉ２］［ｊ２］［ｋ２］とセルＣ［ｉ２］［ｊ２＋１］［ｋ］を連結してから、ｊ２の値を“１”インクリメントして、ステップＳ６９に戻る。
ステップＳ７４では、ｊ２の値を“ｊ”にリセットし、ステップＳ７５に移行する。
【００９７】
図２２Ｂは、ステップＳ７２〜Ｓ７３の処理を説明する図である。
図２２Ａ（ｃ１）の状態でステップＳ７２に移行した場合、ステップＳ７２で、セル１４１（セルＣ［ｉ２］［ｊ２］［ｋ２］）の単一平面１４１ｐと、それとｙ方向に隣接するセル１４４（セルＣ［ｉ２］［ｊ２＋１］［ｋ２］）の単一平面１４４ｐが同じパターンであるか調べる、そして、同じパターンであれば、ステップＳ７３で、図２２Ｂ（ｄ１）に示すように、セル１４１とセル１４４を連結し、図２２Ｂ（ｄ２）に示すように、直方体１５３とセル１４４が連結された立方体を作成する。
【００９８】
次に、セル１４２の平面パターンとそれとｙ方向に隣接するセル（不図示）の平面パターンが同じであるか調べ、異なれば、次に、ｉ２＝ｉ＋１ついてステップＳ７２の処理を行い、セル１４２（セルＣ［ｉ２＋１］［ｊ２］［ｋ２］）の単一平面１４２ｐとそれとｙ方向に隣接するセル１４５（セルＣ［ｉ２＋１］［ｊ２＋１］［ｋ］）の単一平面１４５ｐが同じパターンであるか調べる。そして、同じパターンであれば、図２２Ｂ（ｅ１）に示すようにセル１４２とセル１４５を連結して、単一平面１５５Ｐを有する直方体１５５を作成し、その直方体１５５と直方体１５３とが連結された立体を作成する。
【００９９】
次に、セル１４５とそれとｙ方向に隣接するセル（不図示）が同じ平面パターンを有していなければ、ｊ２の値を“ｊにリセットする。そして、今度は、ｉ２＝ｉ＋２として、再びステップＳ７２の処理を行い、今度は、セル１４３（セルＣ［ｉ２＋２］［ｊ２］［ｋ］）の単一平面１４３ｐとそれとｙ方向に隣接するセル１４６（セルＣ［ｉ２＋２］［ｊ２＋１］［ｋ］）の単一平面１４６ｐが同じパターンであるか調べる。そして、両平面パターンが同じであれば、図２２Ｂ（ｆ１）に示すようにセル１４３とセル１４６を連結し、図２２Ｂ（ｆ２）に示すように、単一平面１５６Ｐを有する直方体１５６を作成し、その直方体１５６と直方体１５３が連結された直方体を作成する。
【０１００】
ステップＳ７５〜Ｓ７６では、上記ステップＳ６９〜Ｓ７１の処理と同様の処理をｚ方向について行う。
配列Ｃ［ｉ２］［ｊ２］［ｋ２］の平面パラメータと配列Ｃ［ｉ２］［ｊ２］［ｋ２＋１］の平面パラメータが同じであるか判別し（Ｓ７５）、同じであれば、セルＣ［ｉ２］［ｊ２］［ｋ２］とセルＣ［ｉ２］［ｊ２］［ｋ２＋１］を連結し、ｋ２の値を“１”インクリメントする（Ｓ７６）。そして、ステップＳ７５に戻る。一方、ステップＳ７５で、両平面パラメータが同じでないと判別すると、連結したセルを再連結する（Ｓ７７）。
【０１０１】
ステップＳ７６の処理では、図示していないが、上記ｘ方向及びｙ方向の処理と同様にして、ｚ方向に配置されたセルについて、同じ平面パターンを有する隣接するセル同士を連結する。
【０１０２】
ステップＳ７７では、例えば図２２Ｂ（ｆ２）に示すように直方体１５３と直方体１５６が連結した直方体を、図２２Ｃ（ｇ）に示すように再連結して、単一の平面パターン１６０ｐを有する直方体１６０を作成する。
【０１０３】
このようにして、計算領域全体のセルについて、ｘ方向、ｙ方向及びｚ方向の各方向について、同じパターンの単一平面を有する隣接セル同士を連結する処理を続けていくことで、より大きなセルを作成する。これにより、セルの数を削減することができる。
【０１０４】
本実施例の場合、セル数を減少できるので、隙間空間の体積計算を高速化できる。また、データベースを利用して上記体積計算を行う場合、図１７に示す体積パターンに加え、上記セルの連結により得られる直方体（セル）に対応する体積パターンとそれに対応する隙間領域の体積が登録されたデータベースを利用することにより、隙間領域の体積計算のさらなる高速化が可能となる。
【０１０５】
尚、上記実施例は単一平面を有するセルを連結する例であるが、複数の平面を有するセルについても、隣接するセルの接触面で、セル内の少なくとも一つの平面の点または線分が一致していれば、それらの隣接するセル同士を連結することができる。
【０１０６】
｛ボクセルデータの分解能調整｝
図２３は、本実施形態におけるボクセルデータの分解能の調整方法を示すフローチャートである。このフローチャートにおける入力は、ユーザ入力装置２２を介して行われる。
まず、計算領域のサイズを指定するデータ（ｘ_ｍｉｎ，ｘ_ｍａｘ，ｙ_ｍｉｎ，ｙ_ｍａｘ，ｚ_ｍｉｎ，ｙ_ｍａｘ）を入力する（Ｓ９１）。
【０１０７】
図２４（ａ）は、上記入力で規定される計算領域のサイズを示す図である。
同図（ａ）に示すように、（ｘ_ｍｉｎ，ｙ_ｍｉｎ，ｚ_ｍｉｎ）は、計算領域２００の左下隅の頂点の座標を規定する。計算領域２００は、この頂点を基点とする、ｘ方向の長さが（ｘ_ｍａｘ−ｘ_ｍｉｎ）、ｙ方向の長さが（ｙ_ｍａｘ−ｙ_ｍｉｎ）、ｚ方向の長さが（ｚ_ｍａｘ−ｚ_ｍｉｎ）の直方体である。
【０１０８】
次に、計算領域の分解能（ｓ）を入力し（Ｓ９２）、ボクセルサイズ（ｂｘ，ｂｙ，ｂｚ）を計算する（Ｓ９３）。ここで、ｂｘ＝ｂｙ＝ｂｚ＝ｓとなる。
この入力により、図２４（ｂ）に示すように、ボクセル２０１のｘ方向の長さがｂｘ、ｙ方向の長さがｂｙ、ｚ方向の長さがｂｚに設定される。
【０１０９】
そして、最後に、ボクセル数（Ｎｘ，Ｎｙ，Ｎｚ）を計算する（Ｓ９４）。Ｎｘ，Ｎｙ、Ｎｚは、
Ｎｘ＝（ｘ_ｍａｘ−ｘ_ｍｉｎ）／ｂｘ
Ｎｙ＝（ｙ_ｍａｘ−ｙ_ｍｉｎ）／ｂｙ
Ｎｚ＝（ｚ_ｍａｘ−ｚ_ｍｉｎ）／ｂｚ
の式を計算することによって得られる。
【０１１０】
図２４（ｃ）、（ｄ）に、分解能に応じた計算領域の分解能の精度を示す。同図（ａ）は分解能が粗いときのボクセルデータ２０１ａを示し、同図（ｂ）は分解能が細かいボクセルデータ２０１ｂを示す。
【０１１１】
本実施例によれば、分解能を調整できるので、精度を変えて、隙間空間の３次元モデルの生成及びその隙間空間の体積計算を実施することが可能である。すなわち、隙間空間全体を粗く調べたい場合には分解能を低くして（ボクセルサイズを小さくして）、隙間空間に体積を高速に計算する。隙間空間を詳細に調べたい場合には、分解能を高くして（ボクセルサイズを小さくして）、隙間空間の体積を計算する。つまり、表面形状が単純な部分は粗いボクセルで、複雑な部分は細かいボクセルで表現することで、精度を保ちながらボクセル数を減少することができる。
【０１１２】
｛計算領域の分割によるメモリ使用量の削減｝
図２５Ａ、２５Ｂは、計算領域を分割して、計算領域の３次元形状の生成と隙間領域の体積計算を行う方法を示すフローチャートである。このフローチャートにおける、パラメータ入力や設定はユーザ入力装置２２を介して行われ、計算はＣＰＵ２１及びＧＰＵ２３１により行われる。
【０１１３】
最大ボクセル数（ＭａｘＸ、ＭａｘＹ、ＭａｘＺ）を設定する（Ｓ１０１）。
ここで、
ＭａｘＸ：ｘ方向のボクセル数
ＭａｘＹ：ｙ方向のボクセル数
ＭａｘＺ：ｚ方向のボクセル数
である。
【０１１４】
計算領域を定義するパラメータ（ｘ_ｍｉｎ，ｘ_ｍａｘ，ｙ_ｍｉｎ，ｙ_ｍａｘ，ｚ_ｍｉｎ，ｙ_ｍａｘ）を入力する（Ｓ１０２）。これらのパラメータは、図２３のステップＳ９１で入力するパラメータと同じものである（図２４（ａ）参照）。
【０１１５】
分解能（ｓ）を入力し（Ｓ１０３）、ボクセルサイズ（ｂｘ，ｂｙ，ｂｚ）を計算する（Ｓ１０４）。ここで、ｂｘ＝ｂｙ＝ｂｚ＝ｓである（図２４（ｂ）参照）。
全体のボクセル数（ＡＮｘ，ＡＮｙ，ＡＮｚ）を下記の式により計算する（Ｓ１０４）。
【０１１６】
ＡＮｘ＝（ｘ_ｍａｘ−ｘ_ｍｉｎ）／ｂｘ
ＡＮｙ＝（ｙ_ｍａｘ−ｙ_ｍｉｎ）／ｂｙ
ＡＮｚ＝（ｚ_ｍａｘ−ｚ_ｍｉｎ）／ｂｚ
領域分割数（ＤＮｘ，ＤＮｙ，ＤＮｚ）を下記に式により計算する（Ｓ１０６）。
【０１１７】
ＤＮｘ＝ＡＮｘ／ＭａｘＸ＋１
ＤＮｙ＝ＡＮｙ／ＭａｘＹ＋１
ＤＮｚ＝ＡＮｚ／ＭａｘＺ＋１
図２６は、計算領域を領域分割数ＤＮｘ，ＤＮｙ，ＤＮを用いて分割したときに得られる計算領域の分割例を示す図である。
【０１１８】
同図は、ＤＮｘ＝３，ＤＮｙ＝１，ＤＮｚ＝２の場合の例である。この場合、計算領域４００は、ｘ方向に３分割、ｙ方向に１分割、ｚ方向に２分割されるので、計算領域４００は、６個の分割領域４０１〜４０６に分割される。
【０１１９】
分割領域（計算領域を前記領域分割数で分割したときの１つの領域）の計算領域のサイズ（ＤＳｘ，ＤＳｙ，ＤＳｚ）を、下記の式により計算する（Ｓ１０７）。
ＤＳｘ＝（ｘ_ｍａｘ−ｘ_ｍｉｎ）／ＤＮｘ
ＤＳｙ＝（ｙ_ｍａｘ−ｙ_ｍｉｎ）／ＤＮｙ
ＤＳｚ＝（ｚ_ｍａｘ−ｚ_ｍｉｎ）／ＤＮｚ
前記分割領域のボクセル数（Ｎｘ，Ｎｙ，Ｎｚ）を、下記の式により計算する（Ｓ１０８）。
【０１２０】
Ｎｘ＝ＤＳｘ／ｂｘ
Ｎｙ＝ＤＳｙ／ｂｙ
Ｎｚ＝ＤＳｚ／ｂｚ
ｄｉ＝１〜ＤＮｘ、ｄｊ＝１〜ＤＮｙ、ｄｚ＝１〜ＤＮｚに対して、下記のステップＳ１０９、Ｓ１１０を実行する。尚、ステップＳ１１０の処理の詳細は、前述した図５のステップＳ４〜Ｓ７と同じであるので、詳しい説明は省略する。
【０１２１】
分割領域の計算領域（ｘ_ｍｉｎ２，ｘ_ｍａｘ２，ｙ_ｍｉｎ２，ｙ_ｍａｘ２，ｚ_ｍｉｎ２，ｚ_ｍａｘ）を下記の式により計算する（Ｓ１０９）。
ｘ_ｍｉｎ２＝ｘ_ｍｉｎ＋ＤＳｘ×（ｄｉ−１）
ｘ_ｍａｘ２＝ｘ_ｍｉｎ２＋ＤＳｘ
ｙ_ｍｉｎ２＝ｙ_ｍｉｎ＋ＤＳｙ×（ｄｊ−１）
ｙ_ｍａｘ２＝ｙ_ｍｉｎ２＋ＤＳｙ
ｚ_ｍｉｎ２＝ｚ_ｍｉｎ＋ＤＳｚ×（ｄｋ−１）
ｚ_ｍａｘ２＝ｚ_ｍｉｎ２＋ＤＳｚ
分割領域内の隙間領域の３次元モデル計算と体積計算を行う（Ｓ１１０）。
【０１２２】
上記ステップＳ１０９〜Ｓ１１０の繰り返し計算で得られた各分割領域の表面データをマージして、３次元モデルの隙間領域の表面データを生成する（Ｓ１１１）。続いて、上記ステップＳ１０９〜Ｓ１１０繰り返し計算で得られた各分割領域の隙間領域の体積をマージして、３次元モデルの隙間領域の体積を計算する（Ｓ１１２）。
【０１２３】
本実施例によれば、計算領域を複数に分割し、各分割領域ごとに計算することで、隙間空間の３次元モデル計算と体積計算で使用するメモリ容量を削減できる。このため、メモリ容量が小さい計算領域でもそれらの計算が可能となる。
【０１２４】
{分割領域の分散処理}
図２７は、上記のように計算領域を分割した場合に、分割領域を複数の計算機により分散処理するシステムの構成例を示す図である。
【０１２５】
この分散処理システム３００は、メイン計算機３０１、複数のサブ計算機３０３及びメイン計算機３０１と複数のサブ計算機３０３を接続するネットワーク３０５から構成されている。
【０１２６】
メイン計算機３０１は、前記分割領域を各サブ計算機３０３に割り当てる。サブ計算機３０３は、メイン計算機３０１から割り当てられた分割領域の計算（隙間領域の表面データの計算と体積計算）を実行し、その計算結果をメイン計算機３０１に返す。メイン計算機３０１は、各サブ計算機３０３から上記計算結果を収集し、それらの実行結果を基に、３次元モデルの隙間領域の生成と体積計算を行う。
【０１２７】
図２８は、上記分散処理システム３００における隙間領域の３次元モデルの生成処理と体積計算処理を示すフローチャートである。
まず、メイン計算機３０１は、図２５Ａのフローチャートに示すステップＳ１０１〜Ｓ１０８の処理を行う。続いて、メイン計算機３０１は、使用計算機数Ｐを、Ｐ＝ＤＮｘ×ＤＮｙ×ＤＮｚを計算して求め（Ｓ１２１）、分割領域（ｄｉ，ｄｊ，ｄｋ）の計算をＰ台のサブ計算機３０３（Ｐm）に割り当てる（Ｓ１２２）。ここで、Ｐm＝１〜Ｐ、mはサブ計算機３０３の識別子である。また、ｄｉ＝１〜ＤＮｘ、ｄｊ＝１〜ＤＮｙ、ｄｋ＝１〜ＤＮｚである。すなわち、本実施形態では、メイン計算機３０１が１つの分割領域の計算を１台のサブ計算機３０３に割り当て、各分割領域の計算処理をＰ台のサブ計算機３０３で並列処理する。
【０１２８】
各サブ計算機３０３は、メイン計算機３０１から割り当てられた分割領域内の隙間領域の３次元モデル計算と体積計算を実行する（Ｓ１２３）。メイン計算機３０１は、各サブ計算機３０３から計算結果（分割領域内における隙間領域の３次元モデルと体積）を取得する（Ｓ１２４）。そして、各分割領域の隙間領域の表面データをマージして隙間領域の３次元形状データを生成し（Ｓ１２５）、各分割領域の隙間領域の体積をマージして隙間領域の体積を求める（Ｓ１２６）。
【０１２９】
本実施例では、計算領域を分割し、各分割領域を複数の計算機で並列に計算するので、隙間空間の３次元モデルの生成と体積計算を高速に実行できる。
｛分割領域の逐次計算｝
図２９は、本実施形態における計算領域の逐次計算方法の例を示す図である。
図２９に示す方法では、同図（ａ）、（ｂ）、（ｃ）、…、（ｄ）に示すように、計算領域５００をｘ方向に２ボクセル単位で分割しながら、該分割により得られた領域における隙間領域の３次元モデル計算と体積計算を逐次実行していく。このとき、前記分割は、ｘ方向に１ボクセルづつスライドさせながら行う。
【０１３０】
図２９に示す計算領域５００は、Ｎｘ＝８、Ｎｙ＝６、Ｎｚ＝８となっている。したがって、１回目は領域５０１（同図（ａ）参照）、２回目は領域５０２（同図（ｂ）参照）、３回目は領域５０３（同図（ｃ）参照）、・・・、７回目は領域５０７を逐次計算していく。
【０１３１】
図３０は、本実施形態における計算領域の逐次計算方法を示すフローチャートである。
図５のフローチャートのステップＳ１、Ｓ２と同様にして、部品表面データ、計算領域及び分解能を入力する（Ｓ１３１）。入力された計算領域と分解能を基に、上述したようにして、ボクセルサイズ（ｂｘ，ｂｙ，ｂｚ）とボクセル数（Ｎｘ，Ｎｙ，Ｎｚ）を計算する（Ｓ１３２）。
【０１３２】
Ｎｘ２にＮｘを設定し、Ｎｘ＝２とする（Ｓ１３３）。続いて、ボクセルデータの配列ａ［２］［Ｎｙ］［Ｎｚ］を作成する（Ｓ１３４）。この配列は、各回の計算対象となる領域のボクセルデータを格納するためのものである。
【０１３３】
次に、下記のステップＳ１３５〜Ｓ１３８を、ｔ＝１〜Ｎｘ２に対して実行する。
ｘ方向の計算領域（ｘ_ｍｉｎ２，ｘ_ｍａｘ２）を計算する（ステップＳ１３５）。ここで、
ｘ_ｍｉｎ２＝ｘ_ｍｉｎ＋ｂｘ×（ｔ−１）
ｘ_ｍａｘ２＝ｘ_ｍｉｎ２＋ｂｘ×２
である。
【０１３４】
ボクセル値を計算する（Ｓ１３６）。配列ａ［２］［Ｎｘ］［Ｎｚ］に格納されているボクセルデータを基に、隙間領域の表面データを計算する（Ｓ１３７）。該ボクセルデータを基に、隙間領域の体積を計算する（Ｓ１３８）。ステップＳ１３６、１３７の処理は、ボクセルデータの配列が異なるだけで、図５のステップＳ６、Ｓ７の処理のアルゴリズムと同様にして実行できる。
【０１３５】
本実施形態では、このように、ｔの値を１、２、…、Ｎｘ２と変化させながら、ステップＳ１３５〜Ｓ１３８の処理をＮｘ２回繰り返し行う。
本実施形態の場合、作成するボクセルデータの格納配列はａ［２］［Ｎｘ］［Ｎｚ］であり、そのサイズは２×Ｎｘ×Ｎｚである。図５に示す計算領域全体を１度で計算する方法の場合は、サイズがＮｘ×Ｎｙ×Ｎｚの配列ａ［Ｎｘ］［Ｎｘ］［Ｎｚ］を作成する必要があるので、その方法に比べ、使用するメモリ容量を２／Ｎｘに削減できる。
【０１３６】
また、ステップＳ１３６のボクセル値の計算において、ｔが２以上ならば、（ｔ−１）回目の計算結果が格納されているａ［２］［Ｎｙ］［Ｎｚ］を、ｔ回目の計算でａ［１］［Ｎｘ］［Ｎｚ］として使用することができる。これにより、計算回数を半分にできる。
ところで、上記実施例では、ｘ方向に逐次計算を行っているが、ｙ方向またはｚ方向に逐次計算を行うようにしてもよい。
【０１３７】
本実施例では、一部の断面画像からボクセルデータを生成した段階で、隙間空間の３次元モデルの生成及び体積計算を行い、この処理を全計算領域に対して逐次的に行うので、それらの計算に使用するメモリ容量を削減できる。このため、メモリ容量の小さな計算機でも、隙間空間の３次元モデルの生成及び体積計算が可能となる。
【０１３８】
｛グラフィックスボードによる処理の並列化｝
本実施形態では、隙間空間の３次元モデルの計算と体積計算の処理を、グラフィックスボード２３による処理とその他の処理に分ける。そして、グラフィックスボード２３ではボクセル値の計算を行い、ＣＰＵ２１では該ボクセル値を基に、隙間領域の表面データの計算と隙間領域の体積計算を行う。
【０１３９】
図３１は、本実施形態におけるグラフィックスボードによる処理の並列化を示すフローチャートである。同図において、ステップＳ１６１〜Ｓ１６３の処理がグラフィックスボード２３で実行される。
【０１４０】
部品表面データ、計算領域及び分解能を、ユーザ入力装置２２から入力する（Ｓ１５１）。上記入力を基に、ボクセルサイズとボクセル数を計算し、さらに、ボクセルデータの配列ａ［Ｎｘ］［Ｎｙ］［Ｎｚ］を作成する（Ｓ１５２）。ＣＰＵ２１は、ボクセル値の計算プロセスを起動し（Ｓ１５３）、ステップＳ１５４に移行する。
【０１４１】
これにより、グラフィックスボード２３がボクセル値の計算プロセスを起動する（Ｓ１６１）。グラフィックスボード２３は、ｉ＝１〜Ｎｘに対して、下記のステップＳ１６２、Ｓ１６３の処理を実行する。
【０１４２】
ｘ方向のｉ番目のボクセル値を計算する（Ｓ１６２）。該計算が終了すると、その計算完了通知をＣＰＵ２１に送信する（Ｓ１６３）。
ＣＰＵ２１は、ｔ＝１〜Ｎｘに対して下記のステップＳ１５４〜Ｓ１５６の処理を実行する。
【０１４３】
グラフィックスボード２３からの計算完了通知を基に、ｘ方向のｔ番目と（ｔ＋１）番目のボクセル値の計算が完了したか判別し（Ｓ１５４）、完了するまでステップＳ１５４の処理を繰り返す。
【０１４４】
ステップＳ１５４で上記計算が完了したと判別すると、ａ［ｔ］［Ｎｙ］［Ｎｚ］とａ［ｔ＋１］［Ｎｙ］［Ｎｚ］に格納されたボクセル値を基に、隙間領域の表面データを計算する（Ｓ１５５）。次に、ａ［ｔ］［Ｎｙ］［Ｎｚ］とａ［ｔ＋１］［Ｎｙ］［Ｎｚ］に格納されたボクセル値を基に、隙間領域の体積を計算する（Ｓ１５６）。
本実施例では、計算機で行う処理とグラフィックスボードで行う処理を並列に実行するので、隙間空間の３次元モデルの生成及び体積計算を高速化できる。
【０１４５】
｛微小な隙間領域のボクセル削除｝
本実施形態では、一定の大きさ以下の隙間領域を抽出しないようにして、隙間領域の３次元モデルの生成処理に要する時間と隙間領域の体積計算時間の短縮を図る。
【０１４６】
図３２は、計算領域に囲まれた微小な隙間領域のボクセルを除去する方法の例を示す図である。同図において、黒の矩形は部品領域のボクセルを、白の矩形は隙間領域のボクセルを示す。
【０１４７】
同図（ａ）に示すボクセルデータａが入力されると、このボクセルデータａ内の隙間領域の全ボクセルについて、それに隣接するボクセル（２６個の隣接ボクセル）の中に１つでも部品領域のボクセルがあるか調べる。そして、部品領域のボクセルがある隙間領域のボクセルを部品領域のボクセルに変換する（部品領域の膨張処理）。
【０１４８】
この結果、ボクセルデータａ内の隙間領域のボクセル６０１〜６１３は部品領域のボクセルに変換され、同図（ｂ）に示すボクセルデータｂが生成される。
次に、今度は、ボクセルデータｂ内の部品領域の全てのボクセルについて、それに隣接するボクセル（２６個の隣接ボクセル）の中に１つでも隙間領域のボクセルがあるか調べる。そして、隙間領域のボクセルがある部品領域のボクセルは、隙間領域のボクセルに変換する（部品領域の収縮処理）。
【０１４９】
この結果、ボクセルデータｂ内のボクセル６０４〜６１３は隙間領域のボクセルに戻され、同図（ｃ）に示すボクセルデータｃが生成される。このようにして、ボクセルデータａから、最終的に、ボクセル６０１〜６０４が除去され（ボクセル６０１が隙間領域のボクセルから部品領域のボクセルに変換され）、ボクセルデータａの部品領域は収縮される。
【０１５０】
このように、ボクセルデータに対して画像処理の膨張収縮法を適用して、抽出した隙間領域から微小領域を除去する。
図３３は、上記微小隙間領域内のボクセル除去方法のアルゴリズムを示すフローチャートである。ここで、計算領域のサイズは、Ｎｘ×Ｎｙ×Ｎｚとする。
【０１５１】
計算領域内の全てのボクセルａ［Ｎｘ］［Ｎｙ］［Ｎｚ］のデータをユーザ入力装置２２から入力する（Ｓ１７１）。処理の途中結果を格納する配列ｂ［Ｎｘ］［Ｎｙ］［Ｎｚ］を作成する。（Ｓ１７２）。
【０１５２】
下記のステップＳ１７３〜Ｓ１７７を、ｉ＝２〜Ｎｘ−１、ｊ＝２〜Ｎｙ−１、ｋ＝２〜Ｎｚ−１に対して実行し、図３２（ｂ）に示すように、部品領域の膨張処理を行う。
ボクセルａ［ｉ］［ｊ］［ｋ］のデータが“０”であるか判別し（Ｓ１７３）、“０”（隙間領域）であればステップＳ１７４に移行し、“１”（部品領域）であればステップＳ１７７に移行する。
【０１５３】
ステップＳ１７４では、ボクセルａ［ｉ］［ｊ］［ｋ］に隣接するボクセル（２６個のｘ方向、ｙ方向、ｚ方向の縦、横、斜めに隣接するボクセル）の中に１つでも値が“１”（部品領域）のボクセルがあるか判別する。そして、値が“１”のボクセルがあれば、ボクセルｂ［ｉ］［ｊ］［ｋ］に“１”を設定し（Ｓ１７５）、無ければ、ボクセルｂ［ｉ］［ｊ］［ｋ］に“０”を設定する（Ｓ１７６）。ステップＳ１７７では、ボクセルｂ［ｉ］［ｊ］［ｋ］に“１”を設定する。
【０１５４】
ステップＳ１７３〜Ｓ１７７の繰り返し処理が終了すると、ｉ＝２〜Ｎｘ−１、ｊ＝２〜Ｎｙ−１、ｋ＝２〜Ｎｚ−１に対して、下記のステップＳ１７８〜Ｓ１８２の処理を実行する。
【０１５５】
ボクセルｂ［ｉ］［ｊ］［ｋ］の値が“１”であるか判別し（Ｓ１７８）、“１”（部品領域）であればステップＳ１７９に移行し、“０”（隙間領域）であればステップＳ１８２に移行する。
【０１５６】
ステップＳ１７９では、ボクセルｂ［ｉ］［ｊ］［ｋ］に隣接するボクセル（２６個の隣接ボクセル）の中に１つでも値が“０”（隙間領域）のボクセルがあるか判別し、値が“０”のボクセルがあればボクセルａ［ｉ］［ｊ］［ｋ］に“０”（隙間領域）を設定し（Ｓ１８０）、無ければボクセルａ［ｉ］［ｊ］［ｋ］に“１”（部品領域）を設定する（Ｓ１８１）。ステップＳ１８２では、ボクセルａ［ｉ］［ｊ］［ｋ］に“０”を設定する。
【０１５７】
ステップＳ１７８〜Ｓ１８２の繰り返し処理が終了すると、本フローチャートの処理を終了する。
この結果、図３２（ｃ）に示すように、部品領域の収縮が行われ、微小な隙間領域のボクセルのみが部品領域のボクセルに変換される。
【０１５８】
図３３のフローチャートは１ボクセル分の幅の隙間を除去する実施例である。２ボクセル分の幅の隙間を除去する場合には、部品領域の拡大と縮小を２回行うようなアルゴリズムにすればよい。
本実施例では、一定の大きさ以下の隙間領域は抽出しないようにするので、隙間空間の３次元モデルの生成及び体積計算の高速化が図れる。
【０１５９】
｛３次元モデルの部分指定｝
本実施形態では、３次元モデルの製品モデルについて、その一部を計算領域として指定できる。
図３４は、このような製品モデル（この例では、ノートパソコン）の計算領域の部分指定方法を示す図である。
製品モデルの計算領域を部分指定する場合、まず、同図（ａ）に示す方法で、計算領域のｘｙ平面を指定し、次に、同図（ｂ）に示す方法で、計算領域のｙｚ平面を指定する。このようにして計算領域のｘｙ平面とｙｚ平面を指定することで、３次元の計算領域を指定できる。
【０１６０】
計算領域のｘｙ平面指定を指定する場合、ディスプレイ２５に製品モデルの上面図７００が表示されている状態で、その上面図７００内の矩形７０１を指定することで行う。この矩形７０１の指定は、例えば、矩形７０１の左下隅頂点７０１ａの座標（ｘ_ｍｉｎ，ｙ_ｍｉｎ）と右上隅頂点７０１ｂの座標（ｘ_ｍａｘ，ｙ_ｍａｘ）を指定することによって行う（図３４（ａ）参照）。
【０１６１】
計算領域のｙｚ平面指定は、ディスプレイ２５に製品モデルの正面図６１０が表示されている状態で、その正面図７１０内の矩形７１１を指定することで行う。この矩形７１１の指定は、例えば、矩形７１１の左下隅頂点７１１ａの座標（ｙ_ｍｉｎ，ｚ_ｍｉｎ）と右上隅頂点７１１ｂの座標（ｙ_ｍａｘ，ｚ_ｍａｘ）を指定することによって行う（図３４（ｂ）参照）。
【０１６２】
図３５は、上述した計算領域の部分指定方法のアルゴリズムを示すフローチャートである。
ディスプレイ２５に３次元製品モデルの上面図を表示する（Ｓ１９１）。ユーザ入力装置２２を介して、該上面図内に第一の矩形（ｘ_ｍｉｎ、ｘ_ｍａｘ，ｙ_ｍｉｎ，ｙ_ｍａｘ）を計算領域として入力する（Ｓ１９２）。
【０１６３】
ディスプレイ２５に上記３次元製品モデルの正面図を表示する（Ｓ１９３）。ユーザ入力装置２２を介して、上記正面図内に第２の矩形（ｙ_ｍｉｎ，ｙ_ｍａｘ，ｚ_ｍｉｎ，ｚ_ｍａｘ）を計算領域として入力する（Ｓ１９４）。
【０１６４】
以上のようにして、第１及び第２の矩形を入力することにより、３次元製品モデルの一部が計算領域として指定される。
本実施例では、３次元製品モデルについて、その一部を計算領域として指定することにより、所望する部分についてのみ、隙間領域の３次元モデルの生成や体積計算を実施することが可能となる。
【０１６５】
上記実施例では、上面図と正面図で計算領域を指定しているようにしているが、上面図と側面図で計算領域を指定するようにしてもよい。また、上面図のみ、正面図のみ、または側面図のみで計算領域を指定するようにしてもよい。
【０１６６】
ところで、上述した各実施例では、断面画像の格子データとして直交格子を採用しているが、本発明は、該格子データを直交格子に限定するものではない。例えば、六角形などの他の格子を使用するようにしてもよい。また、本発明は、上述した実施形態に限定されるものではなく、様々な変形例が可能である。
【０１６７】
（付記１）
製品の３次元モデルの表面データから、複数の断面画像を切り出す断面画像切出し手段と、
該断面画像切出し手段により切り出された断面画像を、部品領域と隙間領域に分ける断面画像処理手段と、
該断面画像処理手段により得られた断面画像を積層して、３次元格子データを生成する３次元格子データ生成手段と、
該３次元格子データ生成手段により生成された３次元格子データを基に、製品内部の隙間空間の３次元モデルを生成する３次元モデル生成手段と、
を備えることを特徴とする３次元モデルの画像処理装置。
（付記２）
付記１記載の３次元モデルの画像処理装置であって、
前記断面画像処理手段は、前記断面画像内の部品領域を塗りつぶして描画することを特徴とする。
（付記３）
付記２記載の３次元モデルの画像処理装置であって、
前記断面画像処理手段による前記断面画像の部品領域の描画を、グラフィックス処理専用のハードウェアで行うことを特徴とする。
（付記４）
付記３記載の３次元モデルの画像処理装置であって、
前記グラフィックス処理専用のハードウェアの処理とその他の処理を並列に実行することを特徴とする。
（付記５）
付記１記載の３次元モデルの画像処理装置であって、
前記断面画像処理手段は、前記断面画像の凸包構成を計算し、その計算結果を基に、凸包内部から隙間領域を抽出することを特徴とする。
（付記６）
付記５記載の３次元モデルの画像処理装置であって、
前記断面画像処理手段は、凸包外形から３次元モデル表面までの深さが所定の閾値以下の凹み部分を、製品の外形と判定することを特徴とする。
（付記７）
付記１記載の３次元モデルの画像処理装置であって、
さらに、
前記断面画像のサイズを指定する第１の指定手段と、
前記断面画像の分解能を指定する第２の指定手段と、
前記第１及び第２の指定手段によって指定された前記断面画像にサイズ及び分解能を基に、前記３次元格子データの格子サイズを調整する調整手段を、
備えることを特徴とする。
（付記８）
付記１記載の３次元モデルの画像処理装置であって、
さらに、前記製品の３次元モデルの表面データを含む３次元計算空間を分割する分割手段を備え、
前記断面画像処理手段は、該分割手段によって得られた各分割領域の断面画像を、部品領域と隙間空間に分け、
前記３次元格子データ生成手段は、前記断面画像処理手段によって得られた前記各分割領域の断面画像を積層して、前記各分割領域の３次元格子データを生成し、
前記３次元モデル生成手段は、前記３次元格子データ生成手段によって生成された各分割領域の３次元格子データを基に、前記各分割領域域内の製品内部の隙間領域の３次元モデルを生成し、
前記格子データ変換手段、前記３次元格子データ生成手段及び前記３次元モデル生成手段によって得られた各分割領域内の製品内部の隙間領域の３次元モデルを統合することにより、前記製品内部の隙間領域の３次元モデルを生成することを特徴とする。
（付記９）
付記８記載の３次元モデルの画像処理装置であって、
さらに、前記断面画像処理手段、前記３次元格子データ生成手段及び前記３次元モデル生成手段の前記分割領域ごとの処理を、分割領域単位で分散処理する分散処理手段を備えることを特徴とする。
（付記１０）
付記１記載の３次元モデルの画像処理装置であって、
さらに、前記製品の３次元モデルの表面データを含む３次元計算空間を逐次的に分割する分割手段を備え、
前記断面画像処理手段は、該分割手段によって得られた分割領域の断面画像を、分割領域と隙間領域に分け、
前記３次元格子データ生成手段は、前記断面画像処理手段によって得られた前記分割領域の断面画像を積層して、前記分割領域の３次元格子データを生成し、
前記３次元モデル生成手段は、前記３次元格子データ生成手段によって生成された前記分割領域の３次元格子データを基に、前記分割領域の製品内部の隙間領域の画像データを生成し、
前記格子データ変換手段、前記３次元格子データ生成手段及び前記３次元モデル生成手段が、前記分割手段により逐次的に得られる分割領域を逐次処理していくことにより、前記製品内部の隙間領域の３次元モデルを生成することを特徴とする。
（付記１１）
付記１記載の３次元モデルの画像処理装置であって、
前記３次元格子データはボクセルデータであり、
前記３次元格子データ生成手段は、前記ボクセルデータに対して膨張収縮処理を施して、微小な空き領域のボクセルを、前記隙間領域から除去することを特徴とする。
(付記１２)
付記１記載の３次元モデルの画像処理装置であって、
さらに、製品の一部を指定する部分指定手段を備え、
前記断面画像切出し手段は、該部分指定手段によって指定された部分の断面画像のみを切り出し、
前記断面画像処理手段、前記３次元格子データ生成手段及び前記３次元モデル生成手段は、前記断面画像切出し手段によって切り出された断面画像について、それぞれの処理を行うことを特徴とする。
（付記１３）
製品の３次元モデルの表面データから、複数の断面画像を切り出す断面画像切出し手段と、
該断面画像切出し手段により切り出された断面画像を、部品領域と隙間領域に分ける断面画像処理手段と、
該断面画像処理手段により得られた断面画像を積層して、３次元格子データを生成する３次元格子データ生成手段と、
該３次元格子データ生成手段により生成された３次元格子データを基に、製品内部の隙間空間の体積を計算する体積計算手段と、
を備えることを特徴とする３次元モデルの画像処理装置。
（付記１４）
付記１３記載の３次元モデルの画像処理装置であって、
前記断面画像処理手段は、前記断面画像内の部品領域を塗りつぶして描画することを特徴とする。
（付記１５）
付記１４記載の３次元モデルの画像処理装置であって、
前記断面画像処理手段による前記断面画像の部品領域の描画を、グラフィックス処理専用のハードウェアで行うことを特徴とする。
（付記１６）
付記１５記載の３次元モデルの画像処理装置であって、
前記グラフィックス処理専用のハードウェアの処理とその他の処理を並列に実行することを特徴とする。
（付記１７）
付記１３記載の３次元モデルの画像処理装置であって、
前記断面画像処理手段は、前記断面画像の凸包構成を計算し、その計算結果を基に、凸包内部から隙間領域を抽出することを特徴とする。
（付記１８）
付記１７記載の３次元モデルの画像処理装置であって、
前記断面画像処理手段は、凸包外形から３次元モデル表面までの深さが所定の閾値以下の凹み部分を、製品の外形と判定することを特徴とする。
（付記１９）
付記１３記載の３次元モデルの画像処理装置であって、
前記体積計算手段は、
直交格子で前記３次元格子データを表現し、前記３次元格子データを隣接する８個の格子を頂点とする直方体から構成される３次元空間に変換する手段と、
該変換手段によって得られた直方体を、その８個の格子の値の組み合わせのパターンに分類し、該直方体の各パターンに対応する該直方体内部の隙間領域の体積を格納している格納手段と、
前記分割手段によって得られた直方体について、そのパターンを基に前記格納手段を検索して、該直方体内部の隙間部分の体積を取得する手段と、
該取得手段によって得られた各直方体内部の隙間部分の体積を基に、製品内部の隙間領域隙の体積を計算する計算手段と、
を備えることを特徴とする。
（付記２０）
付記１８記載の３次元モデルの画像処理装置であって、
前記体積計算手段は、
さらに、隣接する前記直方体が同じパターンであれば、それらを１つの直方体に統合する手段を備えることを特徴とする。
（付記２１）
付記１３記載の３次元モデルの画像処理装置であって、
さらに、
前記断面画像のサイズを指定する第１の指定手段と、
前記断面画像の分解能を指定する第２の指定手段と、
前記第１及び第２の指定手段によって指定された前記断面画像にサイズ及び分解能を基に、前記３次元格子データの格子サイズを調整する調整手段を、
備えることを特徴とする。
（付記２２）
付記１３記載の３次元モデルの画像処理装置であって、
さらに、前記製品の３次元モデルの表面データを含む３次元計算空間を分割する分割手段を備え、
前記断面画像処理手段は、該分割手段によって得られた各分割領域の断面画像を、部品領域と隙間領域に分け、
前記３次元格子データ生成手段は、前記断面画像処理手段によって得られた前記各分割領域の断面画像を積層して、前記各分割領域の３次元格子データを生成し、
前記体積計算手段は、前記３次元格子データ生成手段によって生成された各分割領域の３次元格子データを基に、前記各分割領域域内の製品内部の隙間領域の体積を計算し、
前記格子データ変換手段、前記３次元格子データ生成手段及び前記体積計算手段によって得られた各分割領域内の製品内部の隙間領域の体積の総和を算出することにより、前記製品内部の隙間領域の体積を計算することを特徴とする。
（付記２３）
付記２２記載の３次元モデルの画像処理装置であって、
さらに、前記断面画像処理手段、前記３次元格子データ生成手段及び前記体積計算手段の前記分割領域ごとの処理を、分割領域単位で分散処理する分散処理手段を備えることを特徴とする。
（付記２４）
付記１３記載の３次元モデルの画像処理装置であって、
さらに、前記製品の３次元モデルの表面データを含む３次元計算空間を逐次的に分割する分割手段を備え、
前記断面画像処理手段は、該分割手段によって得られた分割領域の断面画像を、分割領域と隙間領域に分け、
前記３次元格子データ生成手段は、前記断面画像処理手段によって得られた前記分割領域の断面画像を積層して、前記分割領域の３次元格子データを生成し、
前記体積計算手段は、前記３次元格子データ生成手段によって生成された前記分割領域の３次元格子データを基に、前記分割領域の製品内部の隙間領域の体積を計算し、
前記格子データ変換手段、前記３次元格子データ生成手段及び前記体積計算手段が、前記分割手段により逐次的に得られる分割領域を逐次処理していくことにより、前記製品内部の隙間領域の体積を計算することを特徴とする。
（付記２５）
付記１３記載の３次元モデルの画像処理装置であって、
前記３次元格子データはボクセルデータであり、
前記３次元格子データ生成手段は、前記ボクセルデータに対して膨張収縮処理を施して、微小な空き領域のボクセルを、前記隙間領域から除去することを特徴とする。
(付記２６)
付記１３記載の３次元モデルの画像処理装置であって、
さらに、製品の一部を指定する部分指定手段を備え、
前記断面画像切出し手段は、該部分指定手段によって指定された部分の断面画像のみを切り出し、
前記断面画像処理手段、前記３次元格子データ生成手段及び前記体積計算手段は、前記断面画像切出し手段によって切り出された断面画像について、それぞれの処理を行うことを特徴とする。
（付記２７）
製品の３次元モデルの表面データから、複数の断面画像を切り出す第１のステップと、
該第１のステップにより切り出された断面画像を、部品領域と隙間領域に分ける第２のステップと、
該第２のステップにより得られた断面画像を積層して、３次元格子データを生成する第３のステップと、
該第３のステップにより生成された３次元格子データを基に、製品内部の隙間空間の３次元モデルを生成する第４のステップと、
から成る処理をコンピュータに実行させるプログラム。
（付記２８）
付記２６記載のプログラムであって、
前記第２のステップにおいて、前記断面画像内の部品領域を塗りつぶして描画することを特徴とする。
（付記２９）
付記２７記載のプログラムであって、
前記第２のステップにおける前記断面画像の部品領域の描画処理を、グラフィックス処理専用のハードウェアで実行させることを特徴とする。
（付記３０）
付記２７記載のプログラムであって、
前記グラフィックス処理専用のハードウェアの処理とその他の処理を並列に実行させることを特徴とする。
（付記３１）
付記２７記載のプログラムであって、
前記第２のステップにおいて、前記断面画像の凸包構成を計算し、その計算結果を基に、凸包内部から隙間領域を抽出することを特徴とする。
（付記３２）
付記３１記載のプログラムであって、
前記第２のステップにおいて、凸包外形から３次元モデル表面までの深さが所定の閾値以下の凹み部分を、製品の外形と判定することを特徴とする。
（付記３３）
付記２７記載のプログラムであって、
さらに、
前記断面画像のサイズを指定する第５のステップと、
前記断面画像の分解能を指定する第６のステップと、
前記第５及び第６のステップによって指定された前記断面画像にサイズ及び分解能を基に、前記３次元格子データの格子サイズを調整する第７のステップ
をコンピュータに実行させることを特徴とする。
（付記３４）
付記２７記載のプログラムであって、
さらに、前記製品の３次元モデルの表面データを含む３次元計算空間を分割する第５のステップをコンピュータに実行させ、
前記第２のステップにおいては、該分割によって得られた各分割領域の断面画像を、部品領域と隙間空間に分け、
前記第３のステップにおいては、前記第２のステップによって得られた前記各分割領域の断面画像を積層して、前記各分割領域の３次元格子データを生成し、
前記第４のステップにおいては、前記３次元格子データ生成手段によって生成された各分割領域の３次元格子データを基に、前記各分割領域域内の製品内部の隙間領域の３次元モデルを生成し、
前記第２、前記第３及び前記第４のステップによって得られた各分割領域内の製品内部の隙間領域の３次元モデルを統合することにより、前記製品内部の隙間領域の３次元モデルを生成することを特徴とする。
（付記３５）
付記３４記載のプログラムであって、
さらに、前記第２、前記第３及び前記第４のステップの前記分割領域ごとの処理を、分割領域単位で分散処理する第６のステップをコンピュータに実行させることを特徴とする。
（付記３６）
付記２７記載のプログラムであって、
さらに、前記製品の３次元モデルの表面データを含む３次元計算空間を逐次的に分割する第５のステップをコンピュータに実行させ、
前記第２のステップにおいては、該第５のステップによって得られた分割領域の断面画像を、分割領域と隙間領域に分け、
前記第３のステップにおいては、前記第２のステップによって得られた前記分割領域の断面画像を積層して、前記分割領域の３次元格子データを生成し、
前記第４のステップにおいては、前記第３のステップによって生成された前記分割領域の３次元格子データを基に、前記分割領域の製品内部の隙間領域の画像データを生成し、
前記第２、前記第３及び前記第４のステップを、前記第のステップにより逐次的に得られる分割領域に対して逐次実行していくことにより、前記製品内部の隙間領域の３次元モデルを生成することを特徴とする。
（付記３７）
付記２７記載のプログラムであって、
前記３次元格子データはボクセルデータであり、
前記第のステップにおいては、前記ボクセルデータに対して膨張収縮処理を施して、微小な空き領域のボクセルを、前記隙間領域から除去することを特徴とする。
（付記３８）
付記２７記載のプログラムであって、
さらに、製品の一部を指定する第５のステップをコンピュータに実行させ、
前記第１のステップにおいては、該第５のステップにおいて指定された部分の断面画像のみを切り出し、
前記第２、前記第３及び前記第４のステップにおいては、前記第１のステップにおいて切り出された断面画像について、それぞれの処理を行うことを特徴とする。
（付記３９）
製品の３次元モデルの表面データから、複数の断面画像を切り出す第１のステップと、
該断面画像切出し手段により切り出された断面画像を、部品領域と隙間領域に分ける第２のステップと、
該第２のステップにより得られた断面画像を積層して、３次元格子データを生成する第３のステップと、
該第３のステップにより生成された３次元格子データを基に、製品内部の隙間空間の体積を計算する第４のステップと、
から成る処理をコンピュータに実行させることを特徴とするプログラム。
（付記４０）
付記３９記載のプログラムであって、
前記第２のステップにおいては、前記断面画像内の部品領域を塗りつぶして描画することを特徴とする。
（付記４１）
付記３９記載のプログラムであって、
前記第２のステップによる前記断面画像の部品領域の描画を、グラフィックス処理専用のハードウェアで実行させることを特徴とする。
（付記４２）
付記４１記載のプログラムであって、
前記グラフィックス処理専用のハードウェアの処理とその他の処理を並列に実行させることを特徴とする。
（付記４３）
付記３９記載の製品内部のプログラムであって、
前記第２のステップにおいては、前記断面画像の凸包構成を計算し、その計算結果を基に、凸包内部から隙間領域を抽出することを特徴とする。
（付記４４）
付記４３記載のプログラムであって、
前記第２ステップにおいては、凸包外形から３次元モデル表面までの深さが所定の閾値以下の凹み部分を、製品の外形と判定することを特徴とする。
（付記４５）
付記３９記載のプログラムであって、
前記第４のステップは、
直交格子で前記３次元格子データを表現し、前記３次元格子データを隣接する８個の格子を頂点とする直方体から構成される３次元空間に変換する第５のステップと、
該変換手段によって得られた直方体を、その８個の格子の値の組み合わせのパターンに分類し、該直方体の各パターンに対応する該直方体内部の隙間領域の体積を記憶手段に格納させる第６のステップと、
前記第１のステップによって得られた直方体について、そのパターンを基に前記格納手段を検索して、該直方体内部の隙間部分の体積を取得する第７のステップと、
該第７のステップによって得られた各直方体内部の隙間部分の体積を基に、製品内部の隙間領域隙の体積を計算する第８のステップと、
を備えることを特徴とする。
（付記４６）
付記４５記載の製品内部のプログラムであって、
前記第４のステップは、
さらに、隣接する前記直方体が同じパターンであれば、それらを１つの直方体に統合するステップを備えることを特徴とする。
（付記４７）
付記３９記載のプログラムであって、
さらに、
前記断面画像のサイズを指定する第５のステップと、
前記断面画像の分解能を指定する第６のステップと、
前記第１及び第２の指定手段によって指定された前記断面画像にサイズ及び分解能を基に、前記３次元格子データの格子サイズを調整する第７のステップを、
コンピュータに実行させることを特徴とする。
（付記４８）
付記３９記載のプログラムであって、
さらに、前記製品の３次元モデルの表面データを含む３次元計算空間を分割する第５のステップをコンピュータに実行させ、
前記第２のステップにおいては、該第５のステップによって得られた各分割領域の断面画像を、部品領域と隙間空間に分け、
前記第３のステップにおいては、前記第２のステップによって得られた前記各分割領域の断面画像を積層して、前記各分割領域の３次元格子データを生成し、
前記第４のステップにおいては、前記３のステップによって生成された各分割領域の３次元格子データを基に、前記各分割領域域内の製品内部の隙間領域の体積を計算し、
前記第２、前記第３３及び前記第４のステップによって得られた各分割領域内の製品内部の隙間領域の体積の総和を算出することにより、前記製品内部の隙間領域の体積を計算することを特徴とする。
（付記４９）
付記４８記載の３次元モデルの画像処理装置であって、
さらに、前記第２、前記第３及び前記第４のステップの前記分割領域ごとの処理を、分割領域単位で分散処理するステップを備えることを特徴とする。
（付記５０）
付記３９記載のプログラムであって、
さらに、前記製品の３次元モデルの表面データを含む３次元計算空間を逐次的に分割する第５のステップを備え、
前記第２ステップにおいては、該第５のステップによって得られた分割領域の断面画像を、分割領域と隙間領域に分け、
前記第３のステップにおいては、前記第５のステップによって得られた前記分割領域の断面画像を積層して、前記分割領域の３次元格子データを生成し、
前記第４のステップにおいては、前記第のステップ３によって生成された前記分割領域の３次元格子データを基に、前記分割領域の製品内部の隙間領域の体積を計算し、
前記第２、前記第３及び前記第４のステップにおいて、前記第５のステップにより逐次的に得られる分割領域を逐次処理していくことにより、前記製品内部の隙間領域の体積を計算することを特徴とする。
（付記５１）
付記３９記載のプログラムであって、
前記３次元格子データはボクセルデータであり、
前記第３のステップにおいては、前記ボクセルデータに対して膨張収縮処理を施して、微小な空き領域のボクセルを、前記隙間領域から除去することを特徴とする。
(付記５２)
付記３９記載のプログラムであって、
さらに、製品の一部を指定する第５のステップをコンピュータに実行させ、
前記第１のステップにおいては、該第５のステップにおいて指定された部分の断面画像のみを切り出し、
前記第１、前記第３及び前記第４のステップにおいては、前記第５のステップにおいて切り出された断面画像について、それぞれの処理を行うことを特徴とする。
（付記５３）
製品の３次元モデルの表面データから、複数の断面画像を切り出す断面画像切出し手段と、
該断面画像切出し手段により切り出された断面画像を、部品領域と隙間領域に分ける断面画像処理手段と、
該断面画像処理手段により得られた断面画像を積層して、３次元格子データを生成する３次元格子データ生成手段と、
該３次元格子データ生成手段により生成された３次元格子データを基に、製品内部の隙間空間の３次元モデルを生成する３次元モデル生成手段と、
該３次元格子データ生成手段により生成された３次元格子データを基に、製品内部の隙間空間の体積を計算する体積計算手段と、
を備えることを特徴とする３次元モデルの画像処理装置。
（付記５４）
製品の３次元モデルの表面データから、複数の断面画像を切り出すステップと、
該断面画像切出し手段により切り出された断面画像を、部品領域と隙間領域に分けるステップと、
該断面画像処理手段により得られた断面画像を積層して、３次元格子データを生成するステップと、
該３次元格子データ生成手段により生成された３次元格子データを基に、製品内部の隙間空間の３次元モデルを生成するステップと、
から成る処理をコンピュータに実行させるプログラム。
【図面の簡単な説明】
【０１６８】
【図１】本発明の原理を示す模式図であるである。
【図２】本発明の実施形態の概略を説明する図である。
【図３】本実施形態のハードウェアのシステム構成を示す図である。
【図４】本実施形態のソフトウェア構成を示す図である。
【図５】本実施形態における製品モデルの隙間領域の３次元モデル生成及び体積計算処理の全体的な処理手順を示すフローチャートである。
【図６】本実施形態における計算領域の形状を示す図である。
【図７】本実施形態の計算領域のｘ方向、ｙ方向及びｚ方向のボクセル数を示す図である。
【図８】６個のポリゴンデータで定義された３次元の部品表面データの例を示す図である。
【図９】計算領域内での製品モデルの隙間空間（隙間領域）の３次元モデルをボクセルデータにより表現する方法を示す図である。
【図１０】表面形状の複雑度をボクセルの粗密化により表現した図である。
【図１１】ボクセル値計算処理の詳細を示すフローチャートである。
【図１２】ボクセルデータを基に、隙間領域の表面データを計算する処理の詳細を示すフローチャートである。
【図１３】８個のボクセルの中心を頂点とする直方体（セル）の構成を示す図である。
【図１４】セルの８つの頂点を示す図である。
【図１５】登録されている三角形パターンの一部を示す図である。
【図１６】ボクセルデータを基に、隙間領域の３次元モデルの体積を計算する処理の詳細を示すフローチャートである。
【図１７】セルの８個の頂点のボクセル値のパターンから該セルの体積を検索するためのデータベースの構成例を示す図である。
【図１８】部品（３次元モデル）の外形切り出しとして凸包構成を用い、凸包内部から隙間領域を抽出する方法のアルゴリズムを示すフローチャートである。
【図１９】図１８のフローチャートの処理を説明する図である。
【図２０Ａ】セル合成の方法を示すフローチャート（その１）である。
【図２０Ｂ】セル合成の方法を示すフローチャート（その２）である。
【図２１】セル内の表面データが単一平面となるパターンの例を示す図である。
【図２２Ａ】ｘ方向にセルを連結して一つの直方体にしていく処理を説明する図である。
【図２２Ｂ】ｙ方向にセルを連結して一つの立方体にしていく処理を説明する図である。
【図２２Ｃ】連結したセルを再連結した後の直方体を示す図である。
【図２３】本実施形態におけるボクセルデータの分解能の調整方法を示すフローチャートである。
【図２４】（ａ）は計算領域のサイズを示す図、（ｂ）はボクセルのサイズを示す図、（ｃ）は分解能が粗いボクセルデータ、（ｄ）は分解能が細かいボクセルデータを示す図である。
【図２５Ａ】計算領域を分割して、計算領域の３次元形状の生成と隙間領域の体積計算を行う方法を示すフローチャート（その１）である。
【図２５Ｂ】計算領域を分割して、計算領域の３次元形状の生成と隙間領域の体積計算を行う方法を示すフローチャート（その２）である。
【図２６】計算領域の分解例を示す図である。
【図２７】分割領域を複数の計算機により分散処理するシステムの構成例を示す図である。
【図２８】図２７の分散処理システムにおける隙間領域の３次元モデルの生成処理と体積計算処理を示すフローチャートである。
【図２９】本実施形態における計算領域の逐次計算方法の例を示す図である。
【図３０】本実施形態における計算領域の逐次計算方法を示すフローチャートである。
【図３１】本実施形態におけるグラフィックスボードによる処理の並列化を示すフローチャートである。
【図３２】計算領域に囲まれた微小な隙間領域のボクセルを除去する方法の例を示す図である。
【図３３】微小隙間領域内のボクセル除去方法のアルゴリズムを示すフローチャートである。
【図３４】製品モデルの計算領域の部分指定方法を示す図である。
【図３５】分割領域の計算領域の部分指定方法のアルゴリズムを示すフローチャートである。
【符号の説明】
【０１６９】
１、１１      ３次元製品モデル
２、１３      切断平面
３、１４      断面画像
１２、６０    計算領域
１５          ボクセルデータ
２１          ＣＰＵ
２２          ユーザ入力装置
２３          グラフィックスボード
２３１        ＧＰＵ
２３２        フレームバッファ
２４          記憶装置
２５          ディスプレイ
３０          入力機能
３１          表面データ入力部
３２          計算条件入力部
４０          計算機能
４１          断面画像計算部
４２          ボクセル計算部
４３          表面データ計算部
４４          体積計算部
５０          出力機能
５１          データ保存部
５２          描画表示部
６０          直方体（計算領域）
６１          ボクセル
７０          ３次元の部品表面データ
７１          ポリゴンデータ
８０          計算領域
８１          ボクセル        
９０          計算領域
９１          隙間空間（隙間領域）の表面データ
９２、９３    ボクセル
１００        体積パターンに対応する体積の検索用データベース
１１０        断面画像
１１２        境界線
１１３        凸包外形
１１４ａ、１１４ｂ  凹み部分
１１５        部品（製品）の外形
１１６      部品の画像
１２０        セル
１２１      セル内の表面データ
１４１、１４２、１４３、１４４、１４５、１４６  セル
１４１ｐ、１４２ｐ、１４３ｐ、１４４ｐ、１４５ｐ、１４６ｐ  単一平面
１５２、１５３，１５５、１５６  直方体
１５２ｐ、１５３ｐ、１５５ｐ、１５６ｐ  単一平面
２００        計算領域
２０１      ボクセル
２０１ａ    分解能が粗いときのボクセルデータ
２０１ｂ    分解能が細かいときのボクセルデータ
３００      分散処理システム
３０１      メイン計算機
３０３      サブ計算機
３０５      ネットワーク
４００        計算領域
４０１〜４０６  分割領域
５００        計算領域
５０１〜５０７  ｘ方向の計算領域（逐次計算する領域）
６０１〜６１３  入力ボクセルデータの隙間領域のボクセル
７００        ３次元製品モデルの上面図
７０１        矩形（指定部分）
７０１ａ      矩形の左下隅頂点
７０１ｂ      矩形の右上隅頂点
７１０        ３次元製品モデルの正面図
７１１        矩形（指定部分）
７１１ａ      矩形の左下隅頂点
７１１ｂ      矩形の右上隅頂点
【図３】
2007334820.tif 000003
【図４】
2007334820.tif 000004
【図５】
2007334820.tif 000005
【図６】
2007334820.tif 000006
【図８】
2007334820.tif 000007
【図９】
2007334820.tif 000008
【図１０】
2007334820.tif 000009
【図１１】
2007334820.tif 000010
【図１２】
2007334820.tif 000011
【図１３】
2007334820.tif 000012
【図１４】
2007334820.tif 000013
【図１６】
2007334820.tif 000014
【図１７】
2007334820.tif 000015
【図１８】
2007334820.tif 000016
【図１９】
2007334820.tif 000017
【図２０Ａ】
2007334820.tif 000018
【図２０Ｂ】
2007334820.tif 000019
【図２１】
2007334820.tif 000020
【図２２Ａ】
2007334820.tif 000021
【図２２Ｂ】
2007334820.tif 000022
【図２２Ｃ】
2007334820.tif 000023
【図２３】
2007334820.tif 000024
【図２５Ａ】
2007334820.tif 000025
【図２５Ｂ】
2007334820.tif 000026
【図２６】
2007334820.tif 000027
【図２７】
2007334820.tif 000028
【図２８】
2007334820.tif 000029
【図３０】
2007334820.tif 000030
【図３１】
2007334820.tif 000031
【図３３】
2007334820.tif 000032
【図３４】
2007334820.tif 000033
【図３５】
2007334820.tif 000034
【図１】
2007334820.tif 000035
【図２】
2007334820.tif 000036
【図７】
2007334820.tif 000037
【図１５】
2007334820.tif 000038
【図２４】
2007334820.tif 000039
【図２９】
2007334820.tif 000040
【図３２】
2007334820.tif 000041