(57)【特許請求の範囲】
【請求項１】
コンピュータを用いて、外部データ取得手段（Ｓ１）により対象物（１）の境界データからなる外部データ（１２）を取得し、外部データ入力手段（Ａ）により、外部データ（１２）をコンピュータに入力し、セル分割手段（Ｂ）により前記外部データを境界平面が直交する直方体セル（１３）に分割し、セル区分手段（Ｃ）により分割された各セルを境界データを含む境界セル（１３ａ）と境界データを含まない非境界セル（１３ｂ）とに区分し、空間区分手段（Ｄ）により前記非境界セル（１３ｂ）を境界セル（１３ａ）で仕切られた複数の空間に区分する、境界データの内外判定方法であって、
前記空間区分手段（Ｄ）は、空間番号ｋを初期設定する初期設定手段（Ｄ１）と、前記直方体セル（１３）の全てを順に走査して空間番号ｋをラベル付けするラベル付手段（Ｄ２）と、ラベル付けした空間番号ｋを付け直すラベル修正手段（Ｄ３）とからなり、
該ラベル付手段（Ｄ２）は、直前のセルと走査中のセルが非境界セル（１３ｂ）である場合には走査セルに直前セルと同じ空間番号ｋをラベル付けする手段（Ｅ１）と、走査セルが境界セル（１３ａ）である場合には走査セルに境界セルの空間番号をラベル付けする手段（Ｅ２）と、直前セルが境界セル（１３ａ）であり走査セルが非境界セル（１３ｂ）である場合には空間番号ｋをｋ＋１に更新しかつ走査セルに更新した空間番号ｋをラベル付けする手段（Ｅ３）とからなり、
ラベル修正手段（Ｄ３）は、隣接するセルの空間番号を比較する手段（Ｆ１）と、その最も小さい空間番号に隣接するすべてのセルの空間番号ｋを付け直す手段（Ｆ２）とからなる、ことを特徴とする境界データの内外判定方法。
【請求項２】
前記セル分割手段（Ｂ）において、直方体セル（１３）を外部データに含まれる境界面を構成する境界形状要素が再構成できる十分な切断点が得られるまで、八分木分割により再分割する、ことを特徴とする請求項１に記載の境界データの内外判定方法。
【請求項３】
前記セル分割手段（Ｂ）において、ボクセルデータを同一の大きさの直方体セル（１３）に分割する、ことを特徴とする請求項１に記載の境界データの内外判定方法。
【請求項４】
前記ラベル付手段（Ｄ２）は、Ｘ，Ｙ，Ｚの３方向に対して順に繰返し、或いは再帰的な処理により、前記直方体セル（１３）の全てを順に走査する、ことを特徴とする請求項２に記載の境界データの内外判定方法。
【請求項５】
前記ラベル付手段（Ｄ２）とラベル修正手段（Ｄ３）は、走査セル毎に順に行い、或いは、ラベル付手段（Ｄ２）をすべてのセルに対して行った後、ラベル修正手段（Ｄ３）を行う、ことを特徴とする請求項２に記載の境界データの内外判定方法。
【請求項６】
コンピュータを、対象物の境界データからなる外部データ（１２）を入力する外部データ入力手段（Ａ）と、前記外部データを境界平面が直交する直方体セル（１３）に分割するセル分割手段（Ｂ）と、分割された各セルを境界データを含む境界セル（１３ａ）と境界データを含まない非境界セル（１３ｂ）とに区分するセル区分手段（Ｃ）と、前記非境界セル（１３ｂ）を境界セル（１３ａ）で仕切られた複数の空間に区分する空間区分手段（Ｄ）として機能させるためのプログラムであって、
前記空間区分手段（Ｄ）は、空間番号ｋを初期設定する初期設定手段（Ｄ１）と、前記直方体セル（１３）の全てを順に走査して空間番号ｋをラベル付けするラベル付手段（Ｄ２）と、ラベル付けした空間番号ｋを付け直すラベル修正手段（Ｄ３）とからなり、
該ラベル付手段（Ｄ２）は、直前のセルと走査中のセルが非境界セル（１３ｂ）である場合には走査セルに直前セルと同じ空間番号ｋをラベル付けする手段（Ｅ１）と、走査セルが境界セル（１３ａ）である場合には走査セルに境界セルの空間番号をラベル付けする手段（Ｅ２）と、直前セルが境界セル（１３ａ）であり走査セルが非境界セル（１３ｂ）である場合には空間番号ｋをｋ＋１に更新しかつ走査セルに更新した空間番号ｋをラベル付けする手段（Ｅ３）とからなり、
ラベル修正手段（Ｄ３）は、隣接するセルの空間番号を比較する手段（Ｆ１）と、その最も小さい空間番号に隣接するすべてのセルの空間番号ｋを付け直す手段（Ｆ２）とからなる、ことを特徴とする境界データの内外判定プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、シミュレーションにおいて２次元又は３次元の対象物の境界面の内側か外側かを判定する境界データの内外判定方法とそのプログラムに関する。
【０００２】
【従来の技術】
研究開発・技術開発の現場において、ＣＡＤ（Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｄｅｓｉｇｎ）、ＣＡＭ（Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｍａｎｕｆａｃｔｕｒｉｎｇ）、ＣＡＥ（Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｅｎｇｉｎｅｅｒｉｎｇ）、ＣＡＴ（Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｔｅｓｔｉｎｇ）などが、それぞれ設計、加工、解析、試験のシミュレーション手段として用いられている。
また、連続的なシミュレーションであるＣ−Ｓｉｍｕｌａｔｉｏｎ（Ｃｏｏｒｐｏｒａｔｉｖｅ  Ｓｉｍｕｌａｔｉｏｎ）、加工プロセスも考慮したＡ−ＣＡＭ（Ａｄｖａｎｃｅｄ  ＣＡＭ）、究極の精度が出せるＤ−ｆａｂｒｉｃａｔｉｏｎ（Ｄｅｔｅｒｍｉｎｉｓｔｉｃ  ｆａｂｒｉｃａｔｉｏｎ）なども、普及しつつある。
【０００３】
上述した従来のシミュレーション手段では、対象物の境界面は重要な意味をもち、例えば、対象物を境界で表現し、境界面の内部は一様に扱うようなことが広く行われる。このような場合、２次元又は３次元の境界面の内側か外側かを判定する内外判定方法が必要となる。
従来の内外判定方法としては、（１）光線交差法、（２）境界追跡を用いた領域成長（拡張）法、（３）画像処理におけるラスタ追跡、（４）多方向追跡、（５）Ｃｕｒｌｅｓｓの方法、（６）八分木を使ったＳｚｅｌｉｓｋｉの方法やＰｕｌｌｉの方法、特開平９−８１７８３号等が知られている。
【０００４】
【発明が解決しようとする課題】
（１）の領域成長（拡張）法（Ｒａｙ  ｃｒｏｓｓｉｎｇｓ  ｍｅｔｈｏｄ）は、入力境界面がある場合にある点から発した光線（半直線）と境界との交点が偶数か奇数かで、偶数だと光線の視点は物体の外部、奇数だと物体の内部と判別するものである。かかる領域成長（拡張）法は、たとえば、“Ｃｏｍｐｕｔａｔｉｏｎａｌ  ｇｅｏｍｅｔｒｙ  ｉｎ  Ｃ  ｓｅｃｏｎｄ  ｅｄｉｔｉｏｎ”（Ｊ．Ｏ’Ｒｏｕｒｋｅ，ｐ．２４６，Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，１９９８．）に開示されている。
領域成長（拡張）法は、光線がたまたま境界と接する場合には、重根となるために本来２つあるはずの交点が一つになってしまうため適用できず、境界情報に不備（ＣＡＤデータなどで異なるソフトウェアから読み込む場合に表現の仕方の違いや、数値誤差の要因からデータの欠落が起こるがある）の場合にも適用できないという問題があった。
【０００５】
（２）境界情報のみが与えられた画像処理における境界追跡を用いた領域成長（拡張）法は、例えば、「ディジタル画像処理」（Ｒｏｓｅｎｆｅｌｄ  ＆  Ｋａｋ  長尾訳、近代科学社、ｐｐ．３５３〜３５７）に開示されているが、処理が全体に及ぶために遅くなること、および表面情報に不備があると内外判定が正しくできないなどの問題があった。
【０００６】
（３）画像処理におけるラスタ追跡は、同「ディジタル画像処理」、ｐ．３３４に開示されており、Ｘ軸など座標軸に沿ってセルを走査しながら境界や境界にはさまれる領域を追跡してゆく方法であるが、やはり不備（閉曲面となっていない）のある境界情報を量子化した画像とした場合には正しく内外判定ができない。
【０００７】
（４）これを回避する方法として多方向追跡（同ｐ．３３２）もあるが効率が低い。
【０００８】
（５）リバースエンジニアリング（測定点群から表面情報を再構築する方法）の分野におけるＣｕｒｌｅｓｓの方法は、規則的に並んだ測定点と測定対象に対する複数のカメラの方向などの外部的な情報を用いて、距離に基づく陰関数を場全体で定義して、表面情報を再構築する頑健な方法であり、“Ａ  ｖｏｌｕｍｅｔｒｉｃ  ｍｅｔｈｏｄ  ｆｏｒ  ｂｕｉｌｄｉｎｇ  ｃｏｍｐｌｅｘ  ｍｏｄｅｌｓ  ｆｒｏｍ  ｒａｎｇｅ  ｉｍａｇｅｓ．”  （Ｂ．Ｃｕｒｌｅｓｓ  ａｎｄ  Ｍ．Ｌｅｖｏｙ，Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＳＩＧＧＲＡＰＨ  、“９６，ｐａｇｅｓ  ３０３-３１２，Ａｕｇｕｓｔ  １９９６）に開示されている。
しかしＣｕｒｌｅｓｓの方法は、全てのセルにおける距離場計算をしなくてはいけない点で、データ量と計算時間のデメリットがある。またセルのサイズより薄い構造や鋭角な面において距離関数が正しく計算できないなどの精度上の問題も指摘されている。これは内外判定においても誤判断を招くものである。
【０００９】
（６）八分木を使ったＳｚｅｌｉｓｋｉの方法（Ｒ．Ｓｚｅｌｉｓｋｉ．”Ｒａｐｉｄ  ｏｃｔｒｅｅ  ｃｏｎｓｔｒｕｃｔｉｏｎ  ｆｒｏｍ  ｉｍａｇｅ  ｓｅｑｕｅｎｃｅｓ．”）やＰｕｌｌｉの方法（”Ｒｏｂｕｓｔ  ｍｅｓｈｅｓ  ｆｒｏｍ  ｍｕｌｔｉｐｌｅ  ｒａｎｇｅ  ｍａｐｓ．”  Ｋ．Ｐｕｌｌｉ，Ｔ．Ｄｕｃｈａｍｐ，Ｈ．Ｈｏｐｐｅ，Ｊ．ＭｃＤｏｎａｌｄ，Ｌ．ｈａｐｉｒｏ，Ｗ．Ｓｔｕｅｔｚｌｅ．Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｒｅｃｅｎｔ  Ａｄｖａｎｃｅｓ  ｉｎ  ３−Ｄ  Ｄｉｇｉｔａｌ  Ｉｍａｇｉｎｇ  ａｎｄ  Ｍｏｄｅｌｉｎｇ，  Ｍａｙ  １９９７，ｐａｇｅｓ  ２０５−２１１．）も幾つか取得した対象のレンジデータ（距離データ）と空間を八分木で分割したセルとの関係を内部、外部、境界の３つに分類して境界を再構築する方法である。これらの方法では、投影（ｐｒｏｊｅｃｔｉｏｎ）操作を各セルにおいて用いているために、処理が煩雑、時間がかかる、ひいては投影操作における計算の不安定性の問題がある。
【００１０】
特開平９−８１７８３号の「有限要素モデル処理システム及びその方法」は、判定対象の分割要素の面積と、該分割要素の各辺の節点と判定対象の節点とを頂点とする各３角形の面積の和とが一致するかを判定するものである。しかし、この方法は、境界情報に不備がある場合に適用できないという問題があった。
【００１１】
本発明は上述した問題点を解決するために創案されたものである。すなわち、本発明の目的は、境界情報の不備に対して頑健であり境界情報に不備があっても内外判定ができ、処理時間が短く高速であり、計算機への実装が容易であり、異なる空間が一つの空間に分類されてしまうおそれが少なく、多重空間にたいしても適用可能である境界データの内外判定方法とそのプログラムを提供することにある。
【００１２】
【課題を解決するための手段】
本発明によれば、コンピュータを用いて、外部データ取得手段（Ｓ１）により対象物（１）の境界データからなる外部データ（１２）を取得し、外部データ入力手段（Ａ）により、外部データ（１２）をコンピュータに入力し、セル分割手段（Ｂ）により前記外部データを境界平面が直交する直方体セル（１３）に分割し、セル区分手段（Ｃ）により分割された各セルを境界データを含む境界セル（１３ａ）と境界データを含まない非境界セル（１３ｂ）とに区分し、空間区分手段（Ｄ）により前記非境界セル（１３ｂ）を境界セル（１３ａ）で仕切られた複数の空間に区分する、境界データの内外判定方法であって、
前記空間区分手段（Ｄ）は、空間番号ｋを初期設定する初期設定手段（Ｄ１）と、前記直方体セル（１３）の全てを順に走査して空間番号ｋをラベル付けするラベル付手段（Ｄ２）と、ラベル付けした空間番号ｋを付け直すラベル修正手段（Ｄ３）とからなり、
該ラベル付手段（Ｄ２）は、直前のセルと走査中のセルが非境界セル（１３ｂ）である場合には走査セルに直前セルと同じ空間番号ｋをラベル付けする手段（Ｅ１）と、走査セルが境界セル（１３ａ）である場合には走査セルに境界セルの空間番号をラベル付けする手段（Ｅ２）と、直前セルが境界セル（１３ａ）であり走査セルが非境界セル（１３ｂ）である場合には空間番号ｋをｋ＋１に更新しかつ走査セルに更新した空間番号ｋをラベル付けする手段（Ｅ３）とからなり、
ラベル修正手段（Ｄ３）は、隣接するセルの空間番号を比較する手段（Ｆ１）と、その最も小さい空間番号に隣接するすべてのセルの空間番号ｋを付け直す手段（Ｆ２）とからなる、ことを特徴とする境界データの内外判定方法が提供される。
【００１３】
また、本発明によれば、コンピュータを、対象物の境界データからなる外部データ（１２）を入力する外部データ入力手段（Ａ）と、前記外部データを境界平面が直交する直方体セル（１３）に分割するセル分割手段（Ｂ）と、分割された各セルを境界データを含む境界セル（１３ａ）と境界データを含まない非境界セル（１３ｂ）とに区分するセル区分手段（Ｃ）と、前記非境界セル（１３ｂ）を境界セル（１３ａ）で仕切られた複数の空間に区分する空間区分手段（Ｄ）として機能させるためのプログラムであって、
前記空間区分手段（Ｄ）は、空間番号ｋを初期設定する初期設定手段（Ｄ１）と、前記直方体セル（１３）の全てを順に走査して空間番号ｋをラベル付けするラベル付手段（Ｄ２）と、ラベル付けした空間番号ｋを付け直すラベル修正手段（Ｄ３）とからなり、
該ラベル付手段（Ｄ２）は、直前のセルと走査中のセルが非境界セル（１３ｂ）である場合には走査セルに直前セルと同じ空間番号ｋをラベル付けする手段（Ｅ１）と、走査セルが境界セル（１３ａ）である場合には走査セルに境界セルの空間番号をラベル付けする手段（Ｅ２）と、直前セルが境界セル（１３ａ）であり走査セルが非境界セル（１３ｂ）である場合には空間番号ｋをｋ＋１に更新しかつ走査セルに更新した空間番号ｋをラベル付けする手段（Ｅ３）とからなり、
ラベル修正手段（Ｄ３）は、隣接するセルの空間番号を比較する手段（Ｆ１）と、その最も小さい空間番号に隣接するすべてのセルの空間番号ｋを付け直す手段（Ｆ２）とからなる、ことを特徴とする境界データの内外判定プログラムが提供される。
【００１４】
上記本発明の方法とそのプログラムによれば、セル分割手段（Ｂ）ですべての外部データ（１２）を境界平面が直交する直方体セル（１３）に分割し、セル区分手段（Ｃ）で分割された各セルを境界セル（１３ａ）と非境界セル（１３ｂ）とに区分するので、外部データ（１２）は仮に境界情報の不備があっても、必ず境界セル（１３ａ）又は非境界セル（１３ｂ）に区分される。
【００１５】
また、直方体セル（１３）は、元の境界データに比べて大きいので、境界データの一部（例えば１点）のみを含むものを境界セル（１３ａ）とすることにより、境界データは必ず境界セル（１３ａ）に含まれる。更に、データの欠落等、境界情報に不備があっても、その欠落の大きさが非境界セル（１３ｂ）の大きさより小さい限り、欠落を含む境界データも必ず境界セル（１３ａ）に含まれる。
したがって本発明の方法とそのプログラムは、境界情報の不備に対して頑健であり境界情報に不備があっても内外判定ができる。
【００１６】
また、本発明の方法によれば、直方体セル（１３）の全てに対して、ラベル付手段（Ｄ２）とラベル修正手段（Ｄ３）を１回ずつ行うだけで、すべての非境界セル（１３ｂ）を境界セル（１３ａ）で仕切られた複数の空間に区分することができる。
従って、セル数ｎが大きい場合でも、処理時間はＯ（ｎ）のオーダー（ｎに比例）するのみであり、高速処理ができる。
また、計算手順がシンプルであり、プログラム化や計算機への実装が簡単である。
更に、境界セル（１３ａ）で仕切られた複数の空間には異なる空間番号ｋが付けられるので、異なる空間が一つの空間に分類されてしまうおそれが少なく、多重空間にたいしても適用可能である。
【００１７】
また、前記セル分割手段（Ｂ）において、直方体セル（１３）を外部データに含まれる境界面を構成する境界形状要素が再構成できる十分な切断点が得られるまで、八分木分割により再分割する、ことが好ましい。また、前記セル分割手段（Ｂ）において、ボクセルデータを同一の大きさの直方体セル（１３）に分割する、ことが好ましい。
セル分割手段（Ｂ）において八分木分割することにより、Ｖ−ＣＡＤデータに適用することができる。また、等分割することにより、通常のボクセルデータを扱うこともできる。
【００１８】
前記ラベル付手段（Ｄ２）は、Ｘ，Ｙ，Ｚの３方向に対して順に繰返し、或いは再帰的な処理により、前記直方体セル（１３）の全てを順に走査する。
ボクセルデータの場合には、Ｘ，Ｙ，Ｚの３方向に対して順に繰返すことにより、Ｖ−ＣＡＤデータの場合には、再帰的な処理により、直方体セル（１３）の全てを順にもれなく走査することができる。
【００１９】
前記ラベル付手段（Ｄ２）とラベル修正手段（Ｄ３）は、走査セル毎に順に行い、或いは、ラベル付手段（Ｄ２）をすべてのセルに対して行った後、ラベル修正手段（Ｄ３）を行うことが好ましい。
ラベル付手段（Ｄ２）とラベル修正手段（Ｄ３）を、走査セル毎に順に行うことで、隣接するすべてのセルの空間番号ｋを最も小さい空間番号に随時付け直すことができ、空間番号ｋの最大値を小さくできる。
また、ラベル付手段（Ｄ２）をすべてのセルに対して行った後、ラベル修正手段（Ｄ３）を行うことにより、ラベル修正の回数を少なくできる。
【００２０】
【発明の実施の形態】
以下、本発明の好ましい実施形態を図面を参照して説明する。
【００２１】
本発明の発明者等は、先に、「形状と物性を統合した実体データの記憶方法」を創案し出願している（特願２００１−０２５０２３）。この方法は、形状と物性を統合した実体データを小さい記憶容量で記憶することができ、これにより、物体の形状・構造・物性情報・履歴を一元的に管理し、設計から加工、組立、試験、評価など一連の工程に関わるデータを同じデータで管理することができ、ＣＡＤとシミュレーションを一元化することできる実体データの記憶方法に関するものである。この方法によるデータを「Ｖ−ＣＡＤデータ」と呼び、このデータを用いた設計やシミュレーションを「ボリュームＣＡＤ」又は「Ｖ−ＣＡＤ」と呼ぶ。
【００２２】
本発明の境界データの内外判定方法は、Ｖ−ＣＡＤデータへ適用するのに特に適しているが、これに限定されず、通常のボクセルデータにも同様に適用することができる。
【００２３】
初めに本発明における用語を説明する。
入力としての境界（表面）データがあるときにボクセルや八分木のオクタントなどの３次元空間を分割する直方体の表面およびその内部の領域を「セル（ｃｅｌｌ）」とよび、セルに対して表面の情報を保持させる場合のセルを「境界セル（ｂｏｕｎｄａｒｙ  ｃｅｌｌ）」、表面の情報をもたないセルを「非境界セル（ｎｏｎ−ｂｏｕｎｄａｒｙ  ｃｅｌｌ）」（特願２００１−０２５０２３では「内部セル（ｉｎｎｅｒ  ｃｅｌｌ）」）とよぶ。
対象としている３次元空間は有限の広がりを持つもの（「ボリューム世界（ｖｏｌｕｍｅ  ｗｏｒｌｄ）」または単に「世界（ｗｏｒｌｄ）」と呼ぶ）とし、世界は境界セルと非境界セルの２種類のうちどちらかで隙間なく、かつセルの内部の広がりは重複なく覆われている（胞複体（ｃｅｌｌ  ｃｏｍｐｌｅｘ））。
【００２４】
言い換えると、境界セルはセルを構成するセルの内部、およびセルの境界である面、稜、頂点のどれかに入力境界データとの交点があるものであり、そうでないものは全て非境界セルである。隣接するセルどうしはその種類を問わずセル境界のみを共有している。２次元多様体を境界としてもつ３次元の内部が詰まった物体を「空間」と呼ぶ。それぞれの空間は互いに連結でない場合は異なる空間として認識される。したがって閉曲面で表現される境界（表面）で囲まれた部分（点集合）を指し、現実世界ではおなじ材質の物体を限定する単位として用いる。逆に異なる空間を区別する境を「境界（ｂｏｕｎｄａｒｙ：数学で用いられる境界と同じ定義）」もしくは「表面」と呼ぶ。
【００２５】
図１は、コンピュータに実装した本発明の境界データの内外判定方法のフロー図である。この図に示すように、本発明の方法は、外部データ入力手段（Ａ）、セル分割手段（Ｂ）、セル区分手段（Ｃ）、及び空間区分手段（Ｄ）からなる。
【００２６】
外部データ入力手段（Ａ）では、外部データ取得手段Ｓ１で取得した対象物１の境界データからなる外部データ１２を本発明の方法を記憶したコンピュータ等に入力する。セル分割手段（Ｂ）では、外部データ１２を境界平面が直交する直方体セル１３に分割する。直方体セル１３は直方体セルの他、立方体セルでもよい。
セル区分手段（Ｃ）では、分割された各セルを境界データを含む境界セル１３ａと境界データを含まない非境界セル１３ｂとに区分する。空間区分手段（Ｄ）では、非境界セル１３ｂを境界セル１３ａで仕切られた複数の空間に区分する。
【００２７】
本発明の方法を、Ｖ−ＣＡＤデータへ適用する場合には、セル分割手段（Ｂ）において、直方体セル１３を外部データに含まれる境界面を構成する境界形状要素が再構成できる十分な切断点が得られるまで、八分木分割により再分割する。
また、通常のボクセルデータに適用する場合には、セル分割手段（Ｂ）において、同一の大きさの直方体セル１３に分割する。
【００２８】
図２は、図１の空間区分手段（Ｄ）のフロー図である。この図に示すように、空間区分手段（Ｄ）は、初期設定手段（Ｄ１）、ラベル付手段（Ｄ２）及びラベル修正手段（Ｄ３）からなる。
初期設定手段（Ｄ１）では、空間番号ｋを初期設定（ｋ＝１）する。ラベル付手段（Ｄ２）では、直方体セル１３の全てを順に走査して空間番号ｋをラベル付けする。ラベル修正手段（Ｄ３）では、ラベル付けした空間番号ｋを付け直す。
【００２９】
ラベル付手段（Ｄ２）は、通常のボクセルデータに適用する場合には、Ｘ，Ｙ，Ｚの３方向に対して順に繰返す。また、Ｖ−ＣＡＤデータへ適用する場合には、再帰的な処理により、直方体セル１３の全てを順に走査する。
【００３０】
図２において、ラベル付手段（Ｄ２）は、手段（Ｅ１）、手段（Ｅ２）及び手段（Ｅ３）からなる。
手段（Ｅ１）において、直前のセルと走査中のセルが非境界セル１３ｂである場合には走査セルに直前セルと同じ空間番号ｋをラベル付けする。手段（Ｅ２）において、走査セルが境界セル１３ａである場合には走査セルに境界セルの空間番号をラベル付けする。手段（Ｅ３）において、直前セルが境界セル１３ａであり、かつ走査セルが非境界セル１３ｂである場合には、空間番号ｋをｋ＋１に更新し、かつ走査セルに更新した空間番号ｋをラベル付けする。
【００３１】
また図２において、ラベル修正手段（Ｄ３）は、隣接するセルの空間番号を比較する手段（Ｆ１）と、その最も小さい空間番号に隣接するすべてのセルの空間番号ｋを付け直す手段（Ｆ２）とからなる。
【００３２】
なお、ラベル付手段（Ｄ２）とラベル修正手段（Ｄ３）は、走査セル毎に順に行っても良く、或いは、ラベル付手段（Ｄ２）をすべてのセルに対して行った後、ラベル修正手段（Ｄ３）を行っても良い。
【００３３】
図３は、２次元におけるラベル付手段（Ｄ２）の模式図であり、図４は、３次元におけるラベル付手段（Ｄ２）の模式図である。図３及び図４を参照して、本発明の方法を更に詳細に説明する。
【００３４】
入力データとして、空間の境界情報と世界を分割するための最小の分解能を必要とする。境界情報は、変換や計算の結果、部分的に情報の欠落しているようなケースも許すものとする）  。
外部から入力する外部データ１２は、多面体を表すポリゴンデータ、有限要素法に用いる四面体又は六面体要素、３次元ＣＡＤ又はＣＧツールに用いる曲面データ、或いはその他の立体の表面を部分的な平面や曲面で構成された情報で表現するデータである。
外部データ１２は、このようなデータのほかに、Ｖ−ＣＡＤ独自のインターフェースにより人間の入力により直接作成されたデータと、（２）測定機やセンサ、デジタイザなどの表面のデジタイズデータや、ＣＴスキャンやＭＲＩ、および一般的にＶｏｌｕｍｅレンダリングに用いられているボクセルデータなどの内部情報ももつＶｏｌｕｍｅデータであってもよい。
【００３５】
出力データは、空間ごとに異なるラベルがつけられた２次元多様体の境界と最小の空間分解能以上のサイズのセルからなるＶ−ＣＡＤデータである。このＶ−ＣＡＤデータは、境界を直接的に持つセル（境界セル）と持たないセル（非境界セル）で充填された全空間を有する。
【００３６】
図２において、「ラベル」は空間を区別するための番号（空間番号）として用いている。また、予めセルの種類（境界セルまたは内部セル）はセル区分手段（Ｃ）において判定されている。これは個々のセルの内部（セルの境界も含む）と入力である境界情報との交わりがあるかどうかで簡単に判別できる。
【００３７】
（１）初期設定手段（Ｄ１）においてｋ＝１にセットしておく。
（２）ボリューム世界の原点は必ず非境界セルとなるように世界を定義し、空間ｋを指定する。なお、原点は図５における頂点ＬＤＢ（最左下手前側）とするのがよい。
（３）以下、ボクセル版ではＸ，Ｙ，Ｚの３方向に対してそれぞれループ（順に繰り返し）を走らせることによって全セルを走査する。八分木の場合は再帰的な処理（階層的に深くなる）により、やはり全セルを順番に走査する。
【００３８】
図３では、走査の方向を矢印で示し、境界セル１３ａをハッチングで示し、各セルの空間番号ｋをセル内に示している。また、図４では、セルの間隔を離して示し、走査済みのセルを符号Ｓ、走査中のセル（走査セル）を符号Ｐで示している。
（４）手段（Ｅ１）では、当該セルが境界セルになるまでは、すでにラベル付けされた隣接するセルのなかから非境界セル１３ｂがあればそれと同じ空間番号ｋをセットする。
手段（Ｅ２）では、境界セルには空間０（境界を示すラベル）をセットする。
手段（Ｅ３）では、再び非境界セルが来た場合に、ｋをｋ＋１に更新し、新しい空間ｋをセットする。図３では、各境界セル１３ａに空間番号０をセットし、各非境界セル１３ｂに空間番号ｋ、ｋ＋１、ｋ＋２、ｋ＋３をセットした状態を示している。
【００３９】
（５）ラベル付手段（Ｄ２）とラベル修正手段（Ｄ３）を走査セル毎に順に行う場合には、既にラベル付けされた隣接するセルのなかから走査中の非境界セルと異なるラベルを持つもの（番号ｊとする）があり次第、現在の空間番号をｊにさかのぼってふりなおす。隣接するセルはボクセル版の場合は図５におけるＬ側９個とＤ側３個およびＢ側１個の計１３個（２６隣接の半分）が既知である。
図３の例では、空間番号ｋ、ｋ＋１、ｋ＋２、ｋ＋３のうち、最も小さいふりなおす。
【００４０】
（６）以下（３）〜（５）を繰り返して最後まで行く。（もしくは現在のｋとｊをペアとして不具合リストに追加する。
（７）ラベル付手段（Ｄ２）をすべてのセルに対して行った後、ラベル修正手段（Ｄ３）を行う場合には、最初から全数を走査し、リストにある空間番号のペアにふくまれるセルがあれば、番号の若い方にふりなおす（空間番号の圧縮）。
【００４１】
上述した本発明の方法は、セル単位の処理で、先に内部セルのみを頂点、稜、面隣接で辿れる範囲を全て同じ空間とする方法であり、境界セルによって完全に囲まれない限り同じ空間となる。したがって以下の特徴がある。
（１）領域成長法による内外判定に比べて局所処理で済むので頑健である、境界情報（ｓｕｒｆａｃｅ）を使う光線交差法と比べても境界情報に不備があっても内外判定ができるので頑健である。
（２）画像処理の境界追跡を用いる領域成長法に比べて高速である（セルの数をｎとすると処理時間はＯ（ｎ）のオーダー）となる。
（３）実装が簡単である。
（４）安全側（異なる空間が混ざる（一つの空間）に分類されてしまうことのない。
（５）局所的な情報を使って境界セルに囲まれるまで成長するので多空間（多重空間）（境界セルとしては非多様体的な接続）にたいしても適用可能である。
【００４２】
【実施例】
以下、本発明の実施例を説明する。図６から図１１は境界表現としてはかなり複雑な例題でソリッドモデリングでは変換や数値誤差に弱い例題だが本方法により頑健に内外判定が処理されているのを示している。
【００４３】
図６は、入力データの画像であり、自動車のバンパーのプレス金型をソリッドモデルで示している。
図７は、図６の入力データを変換したセルと境界データを示している。
【００４４】
図８は、図７の部分拡大図であり、細線で囲まれたセルを境界データと同時に示している。
図９は、図７のある断面であり、楕円部分が境界データの欠落部分である。この図から、セルの大きさに近い比較的大きな欠落があっても、境界セルを認識できることがわかる。
【００４５】
図１０は、図９の全体図に切断点を追加した図であり、本発明において、入力データとセルの稜との切断点をもつ境界セルをセル区分手段（Ｃ）で予め設定し、その他のセル（非境界セル１３ｂ）を優先させてラベル付けをすることにより、内外判定がより頑健に処理できることがわかる。
図１１は、図１０と同様の別の断面であり、横穴があって非連結でも頑健に処理できることを示している。
【００４６】
【発明の効果】
上述した本発明の方法によれば、セル分割手段（Ｂ）ですべての外部データ１２を境界平面が直交する直方体セル１３に分割し、セル区分手段（Ｃ）で分割された各セルを境界セル１３ａと非境界セル１３ｂとに区分するので、外部データ１２は仮に境界情報の不備があっても、必ず境界セル１３ａ又は非境界セル１３ｂに区分される。
【００４７】
また、直方体セル１３は、元の境界データに比べて大きいので、境界データの一部（例えば１点）のみを含むものを境界セル１３ａとすることにより、境界データは必ず境界セル１３ａに含まれる。更に、データの欠落等、境界情報に不備があっても、その欠落の大きさが非境界セル１３ｂの大きさより小さい限り、欠落を含む境界データも必ず境界セル１３ａに含まれる。
【００４８】
したがって本発明の方法とそのプログラムは、境界情報の不備に対して頑健であり境界情報に不備があっても内外判定ができ、処理時間が短く高速であり、計算機への実装が容易であり、異なる空間が一つの空間に分類されてしまうおそれが少なく、多重空間にたいしても適用可能である、等の優れた効果を有する。
【図面の簡単な説明】
【図１】  本発明の境界データの内外判定方法のフロー図である。
【図２】  図１の空間区分手段（Ｄ）のフロー図である。
【図３】  ２次元におけるラベル付手段（Ｄ２）の模式図である。
【図４】３次元におけるラベル付手段（Ｄ２）の模式図である。
【図５】  境界データを含むセルの各部を示す図である。
【図６】  ディスプレー上に表示した入力データの中間調画像である。
【図７】  入力データを変換したセルと境界データをディスプレー上に表示した中間調画像である。
【図８】  細線で囲まれたセルと境界データをディスプレー上に表示した中間調画像である。
【図９】  境界データの欠落部分をディスプレー上に表示した中間調画像である。
【図１０】  図９の全体図に切断点を追加しディスプレー上に表示した中間調画像である。
【図１１】  横穴がある図１０と同様の別の断面をディスプレー上に表示した中間調画像である。
【符号の説明】
１２  外部データ、１３  セル、
１３ａ  境界セル、１３ｂ  非境界セル、
１４  Ｖ−ＣＡＤデータ
【図１】
0004175536.tif 000002
【図２】
0004175536.tif 000003
【図３】
0004175536.tif 000004
【図４】
0004175536.tif 000005
【図５】
0004175536.tif 000006
【図６】
0004175536.tif 000007
【図７】
0004175536.tif 000008
【図８】
0004175536.tif 000009
【図９】
0004175536.tif 000010
【図１０】
0004175536.tif 000011
【図１１】
0004175536.tif 000012