ＣＡＤメッシュにおける接平面連続境界の抽出システム及び抽出方法
【課題】CADメッシュにおけるセグメンテーションのためのG1連続境界を精度良く抽出する。
【解決手段】3次元CADモデルを三角形分割することにより生成された三角形メッシュであるCADメッシュのデータからPアークとPラインとを抽出する。Pアークが平滑Pアークかどうか、及び、Pラインが平滑Pラインかどうかを判定する。抽出された平滑Pアークを判定することにより、円弧G1連続境界を抽出できる。また、抽出された平滑Pラインを判定することにより、直線G1連続境界を抽出できる。
【解決手段】3次元CADモデルを三角形分割することにより生成された三角形メッシュであるCADメッシュのデータからPアークとPラインとを抽出する。Pアークが平滑Pアークかどうか、及び、Pラインが平滑Pラインかどうかを判定する。抽出された平滑Pアークを判定することにより、円弧G1連続境界を抽出できる。また、抽出された平滑Pラインを判定することにより、直線G1連続境界を抽出できる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元CADモデルを三角形分割することにより生成された三角形メッシュであるCADメッシュから、G1連続境界を抽出するための技術に関するものである。
【背景技術】
【０００２】
機械設計では、CAD (Computer Aided Design)システムによって、機械部品の形状が、曲面を含む3次元の形状モデルとして、コンピュータ内に表現されている。このCADモデルには、平面、円柱面、球面やトーラス面などの解析的曲面(プリミティブ曲面)と、自由な形状を表現するためのスプライン曲面とが含まれている。図１には、プリミティブ曲面によって構成されたCADモデルの例を示す。このような形状モデルを活用することによって、機械設計における様々な検討やシミュレーションを行うことができる。
【０００３】
図１から分かるように、CADモデルは、曲面のパッチを張り合わせた形になっており、それぞれのパッチは球面や円柱面の一部になっている。本明細書の説明では、前者（曲面のパッチ）をフェースと呼び、後者（パッチを構成する球面や円柱面）を母曲面と呼ぶ。また、単に曲面といった場合には、フェースと母曲面の両方を意味することにする。また、本明細書におけるCADモデルとは、厚みのない面だけを表すサーフェスモデルと体積を持ったソリッドモデルとの両方を含む。
【０００４】
さて、CADモデルは、このように多種類の曲面で構成されており、そのデータ表現も複雑なために、異なるCADシステム間でデータをやり取りするのが困難な場合が多い。また、形状を表示するだけであったり、ある種の計算を行ったりする上では、曲面データは不要で、曲面を近似した多面体モデルで十分な場合も多い。さらに、CADモデルは機密性が高い情報であるため、それを社外に提供する場合には、曲面を多面体で近似したデータを用いることが多い。
【０００５】
このような多面体モデルは、CADモデルのフェースを三角形で分割すること(いわゆる三角形分割)によって生成されることが一般的であり、分割の結果は、三角形の集合となる(図２参照)。このような三角形の集合は、一般に三角形メッシュと呼ばれる。また、本明細書では、CADモデルを三角形分割して生成された三角形メッシュをCADメッシュと呼ぶ。三角形メッシュを格納したファイルとして代表的なものに、STLファイル(stereo lithography format)があり、これは産業界において広く流通している。
【０００６】
CADメッシュは、一般に非常に多数の三角形を含んでいるが、CADモデルにおける曲面の情報は失われてしまっている。したがって、例えば、CADモデルに含まれていた、円柱における中心軸の位置を修正したり、円柱の半径を変えたり、といった操作を行うことが出来ない。また、CADモデルで行われるその他の多くの処理もCADメッシュでは不可能となる。
【０００７】
CADメッシュから、プリミティブ曲面（平面、円柱面、円錐面、球面又はトーラス面）上のフェースを抽出することによって、CADメッシュの元となったCADモデルを復元することができれば、このCADモデルを用いて、前記の処理が可能となる。このようなCADモデル復元の基礎的処理として、これらのフェースの境界を高精度に求めるアルゴリズムが必要になる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１０−１８６４７９号公報
【特許文献２】特開２００６−２７７７１３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
CADモデルを分割してCADメッシュを生成すると、フェースは多数の三角形に分割され、またフェースの境界曲線は折れ線になる。CADモデルを復元するためには、CADメッシュに含まれる多数の三角形を、元のCADモデルを構成していたフェースに相当する領域に適切に分割し、またフェースの境界に相当する折れ線を認識することが必要である。分割することを、一般に三角形メッシュのセグメンテーションといい、分割された領域をセグメントと呼ぶ。図 3に図 2のメッシュモデルに対応するセグメントを示す。
【００１０】
セグメンテーションに関しては、コンピュータグラフィックスの分野で多数の研究が行われている。従来の研究ではほとんどの場合、各三角形を処理の単位とする。例えば、
・複数の三角形が滑らかに接続している場合、あるいは、
・複数の三角形に曲面を当てはめてみて、あてはまる場合
に、それらの三角形を同じ領域としてセグメンテーションを行う（前記特許文献１及び２参照）。なお、前記特許文献２では、三角形の法線を評価することにより、境界抽出を試みている。
【００１１】
ところで、G0連続境界（後述）では、境界が折れているため、CADメッシュにおいても、三角形の間の稜線が折れている。これを判別することで、容易に境界を認識することができる。しかし、例えば図４のように平面と円柱面が滑らかに接したり、図５のように球面と円錐面が滑らかに接することで構成されるG1連続境界（後述）の部分では、三角形も非常に滑らかに接続している。このため、従来の技術では、CADメッシュ上でこのようなG1連続境界を正確に抽出することが困難であった。
【００１２】
本発明は、CADメッシュが一定の規則に従って三角形分割されていることを利用してセグメントの境界を正確に抽出するためのものである。
【課題を解決するための手段】
【００１３】
本発明は、従来のセグメンテーションのように三角形メッシュの個々の三角形を主たる処理の対象とするのではなく、CADメッシュから円弧又は直線を抽出してG1連続境界の抽出を行うという、従来の手法とは基本的に異なる考え方を採用したものである。本発明における課題を解決する手段は、以下の項目のように記載できる。
【００１４】
（項目１）
CADメッシュ受付部と、Pアーク抽出処理部と、Pライン抽出処理部と、平滑Pアーク判定処理部と、平滑Pライン判定処理部と、円弧G1連続境界抽出部と、直線G1連続境界抽出部と、出力部とを備えており、
前記CADメッシュ受付部は、3次元CADモデルを三角形分割することにより生成された三角形メッシュであるCADメッシュのデータを受け付ける構成となっており、
前記Pアーク抽出処理部は、前記CADメッシュからPアークを抽出する構成となっており、
前記Pライン抽出処理部は、前記CADメッシュからPラインを抽出する構成となっており、
前記平滑Pアーク判定処理部は、前記Pアークが平滑Pアークかどうかを判定する構成となっており、
前記平滑Pライン判定処理部は、前記Pラインが平滑Pラインかどうかを判定する構成となっており、
前記円弧G1連続境界抽出部は、抽出された前記平滑Pアークを判定することにより、円弧G1連続境界を抽出する構成となっており、
前記直線G1連続境界抽出部は、抽出された前記平滑Pラインを判定することにより、直線G1連続境界を抽出する構成となっており、
前記出力部は、抽出された円弧G1連続境界及び直線G1連続境界を、その後のセグメンテーションのために出力する構成となっている
接平面連続境界の抽出システム。
【００１５】
（項目２）
前記円弧G1連続境界抽出部は、内部Pアーク判定部と、第１種円弧、第２種円弧及び／又は第３種円弧のための円弧G1連続境界判定部とを備えており、
前記内部Pアーク判定部は、前記Pアークが内部Pアークか否かを判定する構成となっており、
前記第１種円弧のために、円弧G1連続境界判定部は、前記Pアークが内部Pアークでなく、かつ、次の条件ａ）〜ｃ）
ａ）前記Pアークの片側で、その頂点に一つあるいは複数の他のPアークが端点で直交接続していること；
ｂ）前記Pアークの反対側に、平坦稜線を介して、三角形（すなわち平面）が接続していること；
ｃ）前記条件ａ）に記載した前記Pアークの頂点に端点で接続した一つあるいは複数の前記他のPアークの接線が、前記Pアークの片側において、前記Pアークの反対側の平面上にあること；
を満足する場合に、円弧G1連続境界と判定する構成となっており、
前記第２種円弧のために、円弧G1連続境界判定部は、前記Pアークが内部Pアークでなく、かつ、次の条件ａ）〜ｃ）
ａ）前記Pアークの片側で、その頂点に一つあるいは複数のPアークが端点で直交接続していること；
ｂ）前記Pアークの反対側で、その頂点に一つあるいは複数のPラインが端点で直交接続していること（但しPラインがPアークの軸と直交する場合を除く）；
ｃ）前記条件ａ）に記載した前記Pアークの頂点に端点で接続した一つあるいは複数の前記他のPアークの接線が、前記Pアークの片側において、前記Pアークの反対側のPラインと平行であるか、あるいは、前記Pアークの接線と前記Pアークの軸とがなす角と、前記Pラインと前記Pアークの軸とがなす角度とが同じであること；
を満足する場合に、円弧G1連続境界と判定する構成となっており、
前記第３種円弧のための円弧G1連続境界判定部は、前記Pアークが内部Pアークでなく、かつ、次の条件ａ）〜ｂ）
ａ）前記Pアークの両側でその頂点に一つあるいは複数の他のPアークが端点で直交接続していること；
ｂ）前記条件ａ）に記載した前記Pアークの両側に端点で接続した一つあるいは複数の前記他のPアークの接線が、前記Pアークの軸と平行となっていること；
を満足する場合に、円弧G1連続境界と判定する構成となっている
項目１に記載の抽出システム。
【００１６】
（項目３）
前記直線G1連続境界抽出部は、第１種直線及び／又は第２種直線のための直線G1連続境界判定部を備えており、
前記直線G1連続境界判定部は、第１種直線のために、次の条件ａ）〜ｃ）
ａ）前記平滑Pラインの片側において、前記平滑Pラインの頂点に一つあるいは複数のPアークが端点で直交接続していること；
ｂ）前記平滑Pラインにおける反対側に、一つの三角形あるいは平坦稜線を介して三角形（すなわち平面）が接続していること；
ｃ）前記平滑Pラインの端点に接続した前記Pアークの接線が、前記反対側の三角形で構成される平面上にあること；
を満足する場合に、直線G1連続境界と判定する構成となっており、
前記直線G1連続境界判定部は、第２種直線のために、次の条件ａ）〜ｂ）
ａ）前記平滑Pラインの両側において、前記平滑Pラインの頂点にそれぞれ一つあるいは複数のPアークがその端点で直交接続していること；
ｂ）前記平滑Pラインの両側の前記Pアークが、相異なる円弧上にあり、且つ、前記平滑Pラインと、前記Pアークの前記端点における接線とは、同じ平面上にあること
を満足する場合に、直線G1連続境界と判定する構成となっている
項目１又は２に記載の抽出システム。
【００１７】
（項目４）
以下のステップを備えることを特徴とする、接平面連続境界の抽出方法：
CADメッシュ受付部が、3次元CADモデルを三角形分割することにより生成された三角形メッシュであるCADメッシュのデータを受け付けるステップ；
Pアーク抽出処理部が、前記CADメッシュからPアークを抽出するステップ；
Pライン抽出処理部が、前記CADメッシュからPラインを抽出するステップ；
平滑Pアーク判定処理部が、前記Pアークは平滑Pアークかどうかを判定するステップ；
平滑Pライン判定処理部が、前記Pラインは平滑Pラインかどうかを判定するステップ；
円弧G1連続境界抽出部が、抽出された前記平滑Pアークを判定することにより、円弧G1連続境界を抽出するステップ；
直線G1連続境界抽出部が、抽出された前記平滑Pラインを判定することにより、直線G1連続境界を抽出するステップ；
出力部が、抽出された円弧G1連続境界及び直線G1連続境界を、その後のセグメンテーションのために出力するステップ。
【００１８】
（項目５）
項目４記載の抽出方法をコンピュータにより実行するためのコンピュータプログラム。
【発明の効果】
【００１９】
本発明によれば、CADメッシュ上でこのようなG1連続境界を正確に抽出することが可能となる。
【図面の簡単な説明】
【００２０】
【図１】プリミティブ曲面によって構成されたCADモデルを示す図である。
【図２】図１のCADモデルを三角形分割して得られた三角形メッシュを示す図である。
【図３】セグメンテーションによって復元されたプリミティブ曲面の一例を示す説明図である。
【図４】直線G1連続で接続する平面と円柱面との境界を示すための説明図である。
【図５】円弧G1連続で接続する球面と円錐面との境界を示すための説明図である。
【図６】本発明の一実施形態における抽出システムの全体的な構成を説明するためのブロック図である。
【図７】本実施形態の抽出方法の手順を説明するためのフローチャートである。
【図８】二面角を説明するための説明図である。
【図９】平坦稜線、折れ稜線と平滑稜線を説明するための説明図である。
【図１０】Pアークを説明するための説明図である。
【図１１】Pアークの抽出方法を説明するための説明図である。
【図１２】連続Pラインと単独Pラインとを説明するための説明図である。
【図１３】折れPアーク、平滑Pアーク及び平坦Pアークを説明するための説明図である。
【図１４】平滑な内部Pアークと平滑な境界Pアークとを説明するための説明図である。
【図１５】折れた境界Pアークと平坦な内部Pアークを説明するための説明図である。
【図１６】十字交差、Ｔ交差及び仮想Ｔ−Ｐアーク交差の例を示す説明図である。
【図１７】T-PアークとボーダーPアークを説明するための説明図である。
【図１８】球面及びトーラス面におけるT-Pアークを説明するための説明図である。
【図１９】球面あるいはトーラス面上に平滑Pアークがある場合における、内部Pアークの判定処理を説明するための説明図である。
【図２０】第１種円弧のG1連続境界抽出の処理を説明するための説明図である。
【図２１】第２種円弧のG1連続境界抽出の処理を説明するための説明図である。
【図２２】第３種円弧のG1連続境界抽出の処理を説明するための説明図である。
【図２３】第１種直線のG1連続境界抽出の処理を説明するための説明図である。
【図２４】第２種直線のG1連続境界抽出の処理を説明するための説明図である。
【発明を実施するための形態】
【００２１】
以下、添付図面を参照しながら、本発明の実施形態に係る接平面連続境界の抽出システム及び抽出方法について説明する。
【００２２】
（前提説明）
プリミティブ曲面（平面、円柱面、円錐面、球面又はトーラス面）から構成されるCADモデルで使われる用語及び概念についてここで説明する。
【００２３】
（プリミティブ曲面）
本実施形態においては、CADモデルの曲面を、平面、円柱面、円錐面、球面、トーラス面のいずれかであると仮定する。これらの曲面をプリミティブ曲面という。
【００２４】
（プリミティブ曲面の間の交線）
CADモデルは、これらのプリミティブ曲面を交差させることによって作られ、曲面同士が交差することによって、それらの交線として曲線が生成される。この交差曲線が、CADモデルのフェースの境界曲線となる。プリミティブ同士の交差曲線は、円弧（円を含む）、直線及びその他の曲線から構成される。ここで、後述するように、G1連続境界は、円弧か直線なので、これら以外の曲線については無視できる。
【００２５】
交差の仕方は、「曲面どうしがある角度をもって交差する場合」と「曲面同士が接する場合」に限られる。なお、交線上のある点（特異点）で、二つの曲面の法線が一致し、二つの曲面がこの点で「角度なし」で交差することがあるが、この特異点については、極微小な点なので、無視して差し支えない。前者の場合（曲面どうしがある角度をもって交差する場合）には、２曲面が角度をもって交差することになり、後者の場合（曲面同士が接する場合）には、２曲面が滑らかに交差する。前者の交差をG0連続交差と呼び、その交線をG0連続交線あるいはG0連続境界と呼ぶ。また、後者の交差をG1連続交差、その交線をG1連続交線あるいはG1連続境界と呼ぶ。下記表1では、プリミティブ曲面の可能なすべての組み合わせについてG1連続境界が生成される場合を示す。
【００２６】
【００２７】
表1に示すように、G1連続境界は、直線あるいは円弧のいずれかになる。
【００２８】
G1連続境界が直線になるのは、交差する２曲面が、次の組み合わせの場合に限られる。
【００２９】
［第１種直線］（平面×円柱面）あるいは、（平面×円錐面）の場合；
［第２種直線］（円柱面×円柱面）、（円柱面×円錐面）あるいは（円錐面×円錐面）の場合。
【００３０】
さらにG1連続境界が円弧になるのは、交差する２曲面のうちの少なくとも一方が球面あるいはトーラス面の場合に限られ、かつ、次の組み合わせの場合に限られる。
【００３１】
［第１種円弧］（平面×トーラス面）の場合；
［第２種円弧］（球面×円柱面）、（トーラス面×円柱面）、（球面×円錐面）あるいは（トーラス面×円錐面）の場合；
［第３種円弧］（球面×トーラス面）、（トーラス面×トーラス面）の場合。
【００３２】
（CADメッシュ上の円弧と直線）
CADソフトウェアからCADメッシュを作成する際に、CADモデルの曲面間を境界で分割し、さらに、曲面も規則的に分割し、三角形メッシュを作成することが多い。そのため、CADメッシュには、多数の内部曲線及び境界曲線が存在する。
【００３３】
そこで、CADメッシュから円弧と直線を抽出し、交差する円弧あるいは直線からプリミティブを認識可能であると考えられる。さらに［第１種円弧］、［第２種円弧］、［第３種円弧］、［第１種直線］、［第２種直線］の性質を用いて、G1連続境界をCADメッシュ上で抽出することが可能になる。以下、詳しく説明する。
【００３４】
（本実施形態の構成）
本実施形態の抽出システムは、接平面連続境界、即ち前記したG1連続境界を抽出するためのシステムである。
【００３５】
このシステムは、図６に示すように、CADメッシュ受付部１０と、Pアーク抽出処理部２０と、Pライン抽出処理部３０と、円弧G1連続境界抽出部４０と、直線G1連続境界抽出部５０と、出力部６０とを備えている。さらにこのシステムは、平滑Pアーク判定処理部７０と、平滑Pライン判定処理部８０とを備えている。
【００３６】
CADメッシュ受付部１０は、3次元CADモデルを三角形分割することにより生成された三角形メッシュであるCADメッシュのデータを受け付ける構成となっている。したがって、本実施形態で対象となるCADメッシュは、３次元CADモデルから生成されたものである。CADメッシュのデータは、例えばSTLファイルとして受け渡される。
【００３７】
Pアーク抽出処理部２０は、CADメッシュからPアーク（後述）を抽出する構成となっている。
【００３８】
Pライン抽出処理部３０は、CADメッシュからPライン（後述）を抽出する構成となっている。
【００３９】
円弧G1連続境界抽出部４０は、抽出されたPアークを判定することにより、円弧G1連続境界を抽出する構成となっている。
【００４０】
円弧G1連続境界抽出部４０は、内部Pアーク判定部４１と、円弧G1連続境界判定部４３とを備えている。
【００４１】
内部Pアーク判定部４１は、Pアークが内部Pアーク（後述）か否かを判定する構成となっている。
【００４２】
G1連続境界判定部４３は、［第１種円弧］、［第２種円弧］及び［第３種円弧］のために、G1連続境界を判定する構成となっている。判定条件については後述する。
【００４３】
直線G1連続境界抽出部５０は、抽出されたPラインを判定することにより、直線G1連続境界を抽出する構成となっている。直線G1連続境界抽出部５０は、第１種直線及び第２種直線のための直線G1連続境界判定部５２を備えている。
【００４４】
直線G1連続境界判定部５２は、第１種直線及び第２種直線のために直線G1連続境界と判定する構成となっている。判定条件については後述する。
【００４５】
出力部６０は、抽出された円弧G1連続境界及び直線G1連続境界を、その後のセグメンテーションのために、適宜の処理システムあるいは処理要素に出力する構成となっている。もちろん、出力部６０は、得られたデータを一旦記憶部（図示せず）に出力するものであってもよい。
【００４６】
平滑Pアーク判定処理部７０は、Pアーク抽出処理部２０で抽出されたPアークが平滑Pアーク（後述）であるかどうかを判定するものである。
【００４７】
平滑Pライン判定処理部８０は、Pライン抽出処理部３０で抽出されたPラインが平滑Pライン（後述）であるかどうかを判定するものである。
【００４８】
前記した各機能要素は、適宜なハードウエアに実装されたコンピュータプログラムにより構成可能である。もちろん、コンピュータプログラムで実行される機能をハードウエアで実行することは可能であり、その逆も可能である。
【００４９】
（本実施形態における抽出方法）
つぎに、前記した抽出システムを用いた抽出方法の一例を、図７を参照しながら説明する。
【００５０】
（図７のステップＳＡ−１）
まず、CADメッシュ受付部１０は、CADメッシュを受け取る。このCADメッシュは、例えば上記のSTLファイルで提供される。
【００５１】
（三角形メッシュ及び位相化）
ここで、三角形メッシュの一般的な性質について説明する。各三角形は、三つの頂点から構成される。メッシュの三角形は、連続な曲面を分割したものであるから、三角形はバラバラではなく、稜線と稜線とで隙間なく接続されている。つまり、メッシュにおいて三角形の頂点は複数の三角形で共有されており、また、三角形の稜線は一般に2個の三角形により共有されている。さらに、メッシュの三角形集合から、次のような接続関係を導出することができる。まず、三角形メッシュにおいて、3次元座標値が一致する頂点を同一の頂点とし、さらに、同じ2頂点を結ぶ辺を同一の稜線とする。このように三角形の頂点、稜線の接続関係を構築することを位相化という。以下では、このような位相化が行われた三角形メッシュを前提とする。
【００５２】
（二面角(dihedral angle)と、平坦稜線、平滑稜線及び折れ稜線）
上記の位相化された三角形メッシュでは、各三角形は、その隣りの三角形と関係付けられているので、図８に示すように、隣り合う三角形が、それらの間の稜線において交差する角度を容易に計算することができる。この角度（図８中の角度γ）を二面角と呼ぶ。二面角が180度である稜線を平坦稜線と呼ぶ（図９参照）。二面角が180度からある程度離れた角度である稜線は、角があるので折れ稜線と呼ぶ（図９参照）。また、二面角が180度ではないが、それに近い値の場合は、滑らかな曲面上の稜線を表すので、平滑稜線と呼ぶ（図９参照）。「それに近い値」は、基本的にはユーザの指定により決定される。ただし、CAD側で「円を多角形近似するときの分割数」を指定する場合があるので、その値を参照してこの値を決めることもできる。例えば、円を36分割している場合には、「それに近い値」は、内接正36多角形の１つの内角＝170度より大きい値、例えば、175度とできる。
【００５３】
（図７のステップＳＡ−２…Pアークとその抽出）
前記した三角形メッシュは多面体であるので、その稜線を辿っていくと、頂点の列即ち折れ線が生成される。折れ線の中には、そのすべての頂点が、ある一つの円弧上に乗っているものがあり、本明細書ではこれをPアーク(polyline arc)と呼ぶ。ただし、円弧上においても折れ線の頂点の並び順は変わらないものとする。すなわち、円弧上で折れ線の始点に対して各頂点がなす円弧の中心角は、折れ線上の頂点の並び順に対して単調に増加するものとする。例えば、図１０では、球面が三角形分割されているので、その球面上に多数のPアークが存在する。
【００５４】
よって、Pアーク抽出処理部２０は、この性質を使って、PアークをCADメッシュから抽出する。すなわち、前述の位相付きの三角形メッシュでは、頂点と頂点が稜線で接続されているので、ある頂点からそれに隣接する頂点を次々と辿って行くことによって折れ線を作ることができる。空間中の円は(一直線上にない)3点で一意に決定できるので、稜線で接続された3頂点(但し3頂点がメッシュの三角形をなす場合を除く)について、図１１に示すように、その3頂点V1,V2,V3を通る円弧を定めることができる。そして、その3頂点の両端の2頂点から、その円弧に沿って、他の接続する頂点を稜線沿いに辿って行き、辿れなくなるか、あるいは、一周して既に辿った頂点に行き着くまで辿る。
【００５５】
このようにして辿った折れ線が4個以上の頂点を含む場合には、折れ線の頂点は円弧上にあるので、これをPアークとする。この手続きを、すべての連続する3頂点の組に付いて行うことによって、Pアーク抽出処理部２０は、Pアークを抽出することができる。
【００５６】
Pアークは、空間の円弧を折れ線で近似したものである。Pアークに対して、その中心、半径、Pアークの円弧を含む平面、中心軸(中心を通り、平面の法線を方向ベクトルとする直線)がそれぞれ定義される、それらをPアークの中心、Pアークの半径、Pアークの平面、Pアークの中心軸と呼ぶ。
【００５７】
（図７のステップＳＡ−３…Pラインとその抽出）
CADメッシュにおいて、円柱面フェース、あるいは円錐面フェースの上で、一つあるいは複数の稜線が連続して一つの直線をなすものをPラインという。一本の稜線で構成されるものを単独Pラインといい、複数の稜線出構成されるものを連続Pラインという。(図１２（ａ）（ｂ）参照)。
【００５８】
連続Pラインについては、Pアークと同様にして、同じ直線上にある稜線を辿ることによって、Pライン抽出処理部３０により、容易に抽出できるが、本例では、Pアークに接続しているPラインだけが必要なので、次にようにして求める。すなわち、あるPアークの頂点（端点も含む）と直交接続して、且つPアークの軸を通る平面上の稜線から出発し、それに隣接する稜線で、出発した稜線と同じ直線上にある稜線を次々と辿れるところまで辿って行くことによって連続Pラインを抽出する。また、一つの稜線も辿れなかったときは、出発した稜線は単独Pラインとなる。
【００５９】
ステップＳＡ−３は、ステップＳＡ−２の後に行われる。
【００６０】
（図７のステップＳＡ−４…平滑Pアークの判定処理）
上で述べたように、G1連続境界が円弧になるのは、２曲面のうちの少なくとも一方が球あるいはトーラスの場合に限られる。
【００６１】
この場合について、円弧G1連続境界抽出部４０により、Pアークを用いて、円弧G1連続境界を求める方法を以下に示す。
【００６２】
（折れPアーク、平滑Pアーク、平坦Pアーク）
ステップＳＡ−２で求めたPアークは、それに含まれる稜線が折れ稜線のもの、平滑稜線のもの、そして平坦稜線のものに分けられる。それぞれ、折れPアーク、平滑Pアーク、平坦Pアークと呼ぶ(図１３)。この平滑Pアークの定義から、平滑Pアーク判定処理部７０は、Pアークが平滑Pアークであるかどうかを判定することができる。折れPアークは、CADモデルでは、平面が円柱の中心軸に直交するように交差する場合の交線に対応する。平滑Pアークは、曲面を分割した場合や曲面のG1連続境界として現れる。また、平坦Pアークは、円柱面あるいは円錐面を分割したときに現れる。
【００６３】
（図７のステップＳＡ−５…内部Pアークと境界Pアーク）
さらに、CADメッシュに含まれる平滑Pアークには、二つのタイプがある。一つは、図１４及び図１５に示すように、球面とトーラス面とを母曲面とするフェースを三角形分割することによって、フェースの内部に現れるものである。これを内部Pアークと呼ぶ。これらは滑らかな曲面上のPアークなので、平滑Pアークとなる。また、円柱面や円錐面状に現れる平坦Pアークも内部Pアークとなる。もう一つのタイプの平滑Pアークは、フェースの境界に対応するもので、これを境界Pアークと呼ぶ。
【００６４】
上に述べた、折れPアーク、平滑Pアーク及び平坦Pアークと、内部Pアーク及び境界Pアークとの関係を表２にまとめる。
【００６５】
【００６６】
なお、表２において、○は、折れPアーク、平滑Pアーク及び平坦Pアークが、内部Pアークあるいは境界Pアークになる可能性があることを示し、×はこれらが内部Pアークあるいは境界Pアークになる可能性がないことを示す。
【００６７】
求めたいG1連続境界に関係するのは、平滑で境界のPアークである。これを平滑境界Pアークと呼ぶことにする。平滑Pアークかどうかは、前述のように二面角を用いて決めることができる。そこで、このステップＳＡ−５では、平滑Pアークを、内部Pアークと境界Pアークに判定する。この両者は排他的関係にあるので、一方だけを判定すればよい。すなわち、内部Pアーク判定部４１により、内部Pアークでないことがわかれば、それは境界Pアークとする。よって、以下では、内部Pアーク判定部４１による内部Pアークの判定法について述べる。これには、後述するように、図１６で示すような、Pアーク間の位置関係によって、十字交差による判定方法と、T交差による判定方法と、仮想T-Pアーク交差による判定方法とがある。
【００６８】
（十字交差による判定）
球面やトーラス面の三角形分割では、等パラメタ線というものに沿って三角形分割されるのが一般的である。例えば、半径1の球面は、二つのパラメタu,vを用いて、
p=(cos u cos v, cos u sin v, sin u)
のようにパラメタ表現することができる。この式で、u＝一定、あるいはv＝一定とすると曲線(等パラメタ曲線)が定義される。特に球面とトーラス面では、等パラメタ曲線は円弧となる。CADモデルの三角形分割では、この等パラメタ線にそって三角形分割されるのが一般的であるため、CADメッシュではこの等パラメタ線の円弧に対応するPアークが含まれることになる。
【００６９】
さらに、図１０に示すように、u＝一定の等パラメタ線とv＝一定の等パラメタ線は、曲面上で交差することから、CADメッシュから求めたPアークで十字状に交差しているものは等パラメタ線に対応することになる。これはトーラス面でも同様である。このような、u＝一定の等パラメタ線とv＝一定の等パラメタ線の交差を十字交差と呼ぶことにする。
【００７０】
言い換えると、二つの平滑Pアークが十字交差していれば、これらのPアークは球面フェースあるいはトーラス面フェースの内部Pアークになる。内部Pアーク判定部４１は、まず、この条件を用いて、内部Pアークを判定できる。
【００７１】
（T交差による判定）
図１７に示すように、Pアークが、その端点で別のPアーク内にT字型に交わる場合をT交差とし、その交点をT交点とする。さらに、前者のPアークをT-Pアークと呼び、後者をボーダーPアークと呼ぶ。ここで、T交差とは、Pアークの端点がボーダーPアークの内部の頂点(ボーダーPアークの端点以外)に一致する場合をいう。さらに、その場合だけでなく、Pアークの端点に外挿した円弧(図１７中の破線で示す)がPアークに交差する場合も、T交差に含める。これらを区別するために、前者を直接T-Pアークと呼び、後者を間接T-Pアークと呼ぶ。すなわち間接T-Pアークとは、図１７に破線で示すようにPアークを延長したときにT交差となるPアークをいう。
【００７２】
前記（十字交差による判定）では、Pアークの十字交差によって内部Pアークの判定を行っていたが、CADの三角形分割の方法によっては、まれに球面・トーラス面のメッシュの内部Pアークが十字交差しないことがある。この場合、T交差によって内部Pアークを判定することができる(図１８)。
【００７３】
これは以下のように証明できる。
・まずボーダーPアークが境界Pアークの場合を考える。もしT-Pアークも境界Pアークとすると、T交点において三つ以上の曲面(ボーダーPアークの両側の曲面と、T-Pアークの両側の曲面を含む三つの曲面)が交差していることになり、T交点はボーダーPアークの端点でなければならない。しかし、T-Pアークは、ボーダーPアークの端点以外で交差しなければならないので仮定に反する。よってT-Pアークは内部Pアークでなければならない。
・次にボーダーPアークが内部Pアークである場合を考える。もしT-Pアークが境界Pアークであるとすると、T交点において、曲面はボーダーPアークの方向に不連続になっており、ボーダーPアークはそこに端点を持たなければならない。これは、T交点が端点ではないことに矛盾する。よって、T-Pアークは内部Pアークでなければならない。
【００７４】
したがって、前記の判定基準により、内部Pアーク判定部４１は、内部Pアークを判定することができる。
【００７５】
（仮想T-Pアーク交差による判定）
図１９に示すように、三角形分割の方法によっては、等パラメタ線による分割がuあるいはv方向の内の一方向だけの場合があり、その方向にだけ等パラメタ線に対する平滑Pアークが存在し、他の方向には平滑Pアークが存在しないことがある。すなわち、Pアークに十字交差あるいはT交差が存在しない場合がある。このような場合、内部Pアーク判定部４１は、次の方法で内部Pアークを判定する。これらの平滑Pアークを
a1, a2 …, an
とすると、もしすべての隣り合う二つの平滑Pアーク
ai, ai+1
が、仮想的な平滑稜線Q（仮想T-Pアークという）を介して接続しているならば、その平滑稜線Qの内部頂点と接続する平滑Pアークは内部Pアークとなる。等パラメタ線のPアークが球面あるいはトーラス面上にあることを判定するために、
（１）この等パラメタ線のPアークの軸を通る平面を作成して、
（２）Pアーク群とその平面との交点群を求め、
（３）その交点群を補間して、もしその交点群が円弧であれば、その交点で仮想T-Pアークを作成し、
（４）上記の十字交差あるいはT交差判定によって、内部Pアーク及び境界Pアークを判定することができる。
【００７６】
（図７のステップＳＡ−７…球面、トーラス面のG1連続境界の抽出）
ステップＳＡ−５の処理によって、平滑Pアークで、かつ、内部Pアークであるものをすべて判定することができる。平滑Pアークは、内部Pアークか境界Pアークのいずれかであるので、ステップＳＡ−５の方法によって内部Pアークと判定されなかった平滑Pアークは境界Pアーク、すなわち平滑境界Pアークとする。
【００７７】
この平滑境界Pアークは、CADモデルにおいて母曲面同士がG1連続で交差することによって生成された交差曲線に対応するので、フェースのG1連続境界になる。
【００７８】
この平滑境界Pアークは、G1連続境界であることを次の判定処理で確認できる。
【００７９】
前述のように、G1連続境界が円弧になるのは、次の三つの場合である。
【００８０】
［第１種円弧］（平面×トーラス面）
［第２種円弧］（球面×円柱面）、（トーラス面×円柱面）、（球面×円錐面）あるいは（トーラス面×円錐面）
［第３種円弧］（球面×トーラス面）、（トーラス面×トーラス面）
それぞれの場合について、円弧G1連続境界の抽出の方法を説明する。
【００８１】
（図７のステップＳＡ−７・・・［第１種円弧］の場合）
前述の
［第１種円弧］（平面×トーラス面）
の場合は、平面領域が平滑な境界でトーラス面に接している場合である。
【００８２】
本実施形態では、円弧G1連続境界判定部４３が、以下の３条件を判定することによって、［第１種円弧］のために、平滑Pアークを抽出することができる。この手順を、図２０をさらに参照しながら説明する。なお、これらの条件を全て満たした場合にG1連続境界Pアークとなる。
ａ）PアークPの片側（図２０において下側）において、PアークPのいずれかの頂点（図示例では頂点Ａ）に一つあるいは複数のPアーク（図示例ではPアークＱ）がその端点で直交接続していること。ここで、本例では、PアークQの端点AでPアークQの接線Tを求めておく；
ｂ）その反対側（図２０において上側）でPアークPが、互いに平坦稜線で接続している三角形（平面S）と接続していること；
ｃ）前記したすべてのPアークQの接線Tが平面S上にあること；
以上の条件により抽出されたPアークPは、円弧G1連続境界である。
【００８３】
（図７のステップＳＡ−７・・・［第２種円弧］の場合） 前述の
［第２種円弧］：（（球面×円柱面）、（トーラス面×円柱面）、（球面×円錐面）あるいは（トーラス面×円錐面））
の場合とは、球面あるいはトーラス面が平滑な境界で円柱面あるいは円錐面に接している場合である。
【００８４】
本実施形態では、円弧G1連続境界判定部４３が、以下の３条件を判定することによって、［第２種円弧］のために平滑Pアークを抽出することができる。図２１をさらに参照しながら説明する。なお、これらの条件を全て満たした場合にG1連続境界Pアークとなる。
ａ）PアークPの片側（図２１において上側）において、PアークPのいずれかの頂点（図２１においてAi）に一つあるいは複数のPアークＱが端点で直交接続していること。ここで本例では、PアークQの端点AでPアークQの接線Tを求めておく；
ｂ）その反対側（図２１において下側）でPアークPの頂点に、一つあるいは複数のPラインLが端点で直交接続していること。ここでPラインLの端点は、図２１においてAｊである；
ｃ）すべてのPアークQの接線Tが、すべてのPラインLと平行であるか、あるいは、「PアークPの軸Oと接線Tの角度」と「軸OとPラインLの角度」とが同じである（つまり図２１において角度α＝角度βである。ただし、α≠９０°である）こと。ここで、角度αの値は、０°＜α＜１８０°となる；
このようにして抽出されたPアークPは、円弧G1連続境界である。
【００８５】
（図７のステップＳＡ−７・・・［第３種円弧］の場合）
前述の
［第３種円弧］（球面×トーラス面）、（トーラス面×トーラス面）
の場合は、球面あるいはトーラス面が平滑な境界でトーラス面に接している場合である。
【００８６】
本実施形態では、円弧G1連続境界判定部４３が、以下の２条件を判定することによって、［第３種円弧］のために平滑Pアークを抽出することができる。図２２をさらに参照しながら説明する。なお、これらの条件を全て満たした場合にG1連続境界Pアークとなる。
ａ）PアークPの両側（図２２における左右両側）で、PアークPの頂点（図２２では頂点Ａ）に一つあるいは複数の異なるPアーク（図２２のQ1,Q2）が、それらの端点Aで直交接続していること。本実施形態では、その端点AにおけるPアーク（Q1，Q2）の接線（図２２のT1、T2）をそれぞれ求める；
ｂ）すべてのPアーク（Q１、Q2）の接線（T1、T2）は、PアークPの軸Oと平行であること；
このようにして抽出されたPアークPは、円弧G1連続境界である。
【００８７】
（図７のステップＳＡ−８…平滑Pライン判定処理）
前述のように、G1連続境界が直線になるのは、次の二つの場合である。
【００８８】
［第１種直線］（平面×円柱面）あるいは、（平面×円錐面）
［第２種直線］（円柱面×円柱面）、（円柱面×円錐面）あるいは（円錐面×円錐面）
それぞれの場合について、直線G1連続境界の抽出の方法を説明する。
【００８９】
（折れPライン、平滑Pライン）
直線G1連続境界は、メッシュ上のPラインを構成する。Pラインは、折れPライン、平滑Pラインに分けられる。Pラインに含まれる稜線がすべて折れ稜線の場合を折れPライン、すべて平滑稜線の場合を平滑Pラインと称する。
【００９０】
したがって、平滑Pライン判定処理部８０は、この定義に基づいて、平滑Pラインを判定することができる。
【００９１】
（図７のステップＳＡ−１０…［第１種直線］の場合）
前述の
［第１種直線］（平面×円柱面）あるいは、（平面×円錐面）
の場合は、平面領域が平滑な境界で円柱面あるいは円錐面に接している場合である。
【００９２】
本実施形態では、直線G1連続境界判定部５２が、以下の３条件を判定することによって、［第１種直線］のために平滑Pラインを抽出することができる。図２３をさらに参照しながら説明する。なお、これらの条件を全て満たした場合にG1連続境界Pラインとなる。
ａ）PラインL（図２３中の頂点AB間）の片側（図２３において左側）において、L上の頂点ＡにPアークPが端点Ａで直交接続していること。ここで本実施形態では、PアークPの端点AでPアークPの接線Tを求める；
ｂ）その反対側（図２３において右側）で、PラインLが三角形Mと接続しており、かつ、三角形Mと三角形Nは平坦稜線CBで接続していて、三角形Mと三角形Nが一つの平面になっていること；
ｃ）PアークPの接線Tは、三角形Mの平面上にあること；
この条件により抽出されたPラインは、直線G1連続境界である。
【００９３】
（図７のステップＳＡ−１１…［第２種直線］の場合）
最後に残ったのが、円柱面や円錐面どうしが接することによって直線G1連続境界をもつ次の場合である。
［第２種直線］（円柱面×円柱面）、（円柱面×円錐面）あるいは（円錐面×円錐面）
【００９４】
この場合も、直線G1連続境界は、三角形メッシュ上の平滑Pラインとなる。本実施形態では、直線G1連続境界判定部５２が、以下の２条件を判定することによって、［第２種直線］のために平滑Pラインを抽出することができる。図２４をさらに参照しながら説明する。なお、これらの条件を全て満たした場合にG1連続境界Pラインとなる。
ａ）PラインLの両側で、L上の頂点Ａに、それぞれ少なくとも一つのPアークP1,P2が端点で直交接続していること。ここで、本例では、端点Aにおいて、これらのPアークP1,P2の接線T1、T2を求める。
ｂ）これらのPアークP1、P2は、相異なる円弧上にあり、かつ、PラインLとこれらの接線T1,T2が、同じ平面上にあること。
【００９５】
この条件により抽出されたPラインは、直線G1連続境界である。
【００９６】
前記のようにして、円弧及び直線のＧ１連続境界をいずれも抽出することができる。その後、抽出されたＧ１連続境界を、出力部６０により、所望のメモリあるいはシステムに送る。これにより、抽出されたＧ１連続境界を、例えばＣＡＤメッシュのセグメントのために利用することができる。
【００９７】
なお、本発明は、前記した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変更を加え得るものである。
【００９８】
例えば、前記した各構成要素は、機能ブロックとして存在していればよく、独立したハードウエアとして存在しなくても良い。また、実装方法としては、ハードウエアを用いてもコンピュータソフトウエアを用いても良い。さらに、本発明における一つの機能要素が複数の機能要素の集合によって実現されても良く、本発明における複数の機能要素が一つの機能要素により実現されても良い。
【００９９】
また、本発明を構成する各機能要素は、離散して存在しても良い。離散して存在する場合には、例えばネットワークを介して必要なデータを受け渡すことができる。各部の内部における各機能も、同様に、離散して存在することが可能である。例えば、グリッドコンピューティングやクラウドコンピューティングを用いて、本実施形態における各機能要素あるいはその一部分を実現することも可能である。
【符号の説明】
【０１００】
１０ CADメッシュ受付部
２０ Pアーク抽出処理部
３０ Pライン抽出処理部
４０ 円弧G1連続境界抽出部
４１ 内部Pアーク判定部
４３ G連続境界判定部
５０ 直線G1連続境界抽出部
５２ 直線G1連続境界判定部
６０ 出力部
７０ 平滑Pアーク判定処理部
８０ 平滑Pライン判定処理部
【技術分野】
【０００１】
本発明は、３次元CADモデルを三角形分割することにより生成された三角形メッシュであるCADメッシュから、G1連続境界を抽出するための技術に関するものである。
【背景技術】
【０００２】
機械設計では、CAD (Computer Aided Design)システムによって、機械部品の形状が、曲面を含む3次元の形状モデルとして、コンピュータ内に表現されている。このCADモデルには、平面、円柱面、球面やトーラス面などの解析的曲面(プリミティブ曲面)と、自由な形状を表現するためのスプライン曲面とが含まれている。図１には、プリミティブ曲面によって構成されたCADモデルの例を示す。このような形状モデルを活用することによって、機械設計における様々な検討やシミュレーションを行うことができる。
【０００３】
図１から分かるように、CADモデルは、曲面のパッチを張り合わせた形になっており、それぞれのパッチは球面や円柱面の一部になっている。本明細書の説明では、前者（曲面のパッチ）をフェースと呼び、後者（パッチを構成する球面や円柱面）を母曲面と呼ぶ。また、単に曲面といった場合には、フェースと母曲面の両方を意味することにする。また、本明細書におけるCADモデルとは、厚みのない面だけを表すサーフェスモデルと体積を持ったソリッドモデルとの両方を含む。
【０００４】
さて、CADモデルは、このように多種類の曲面で構成されており、そのデータ表現も複雑なために、異なるCADシステム間でデータをやり取りするのが困難な場合が多い。また、形状を表示するだけであったり、ある種の計算を行ったりする上では、曲面データは不要で、曲面を近似した多面体モデルで十分な場合も多い。さらに、CADモデルは機密性が高い情報であるため、それを社外に提供する場合には、曲面を多面体で近似したデータを用いることが多い。
【０００５】
このような多面体モデルは、CADモデルのフェースを三角形で分割すること(いわゆる三角形分割)によって生成されることが一般的であり、分割の結果は、三角形の集合となる(図２参照)。このような三角形の集合は、一般に三角形メッシュと呼ばれる。また、本明細書では、CADモデルを三角形分割して生成された三角形メッシュをCADメッシュと呼ぶ。三角形メッシュを格納したファイルとして代表的なものに、STLファイル(stereo lithography format)があり、これは産業界において広く流通している。
【０００６】
CADメッシュは、一般に非常に多数の三角形を含んでいるが、CADモデルにおける曲面の情報は失われてしまっている。したがって、例えば、CADモデルに含まれていた、円柱における中心軸の位置を修正したり、円柱の半径を変えたり、といった操作を行うことが出来ない。また、CADモデルで行われるその他の多くの処理もCADメッシュでは不可能となる。
【０００７】
CADメッシュから、プリミティブ曲面（平面、円柱面、円錐面、球面又はトーラス面）上のフェースを抽出することによって、CADメッシュの元となったCADモデルを復元することができれば、このCADモデルを用いて、前記の処理が可能となる。このようなCADモデル復元の基礎的処理として、これらのフェースの境界を高精度に求めるアルゴリズムが必要になる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１０−１８６４７９号公報
【特許文献２】特開２００６−２７７７１３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
CADモデルを分割してCADメッシュを生成すると、フェースは多数の三角形に分割され、またフェースの境界曲線は折れ線になる。CADモデルを復元するためには、CADメッシュに含まれる多数の三角形を、元のCADモデルを構成していたフェースに相当する領域に適切に分割し、またフェースの境界に相当する折れ線を認識することが必要である。分割することを、一般に三角形メッシュのセグメンテーションといい、分割された領域をセグメントと呼ぶ。図 3に図 2のメッシュモデルに対応するセグメントを示す。
【００１０】
セグメンテーションに関しては、コンピュータグラフィックスの分野で多数の研究が行われている。従来の研究ではほとんどの場合、各三角形を処理の単位とする。例えば、
・複数の三角形が滑らかに接続している場合、あるいは、
・複数の三角形に曲面を当てはめてみて、あてはまる場合
に、それらの三角形を同じ領域としてセグメンテーションを行う（前記特許文献１及び２参照）。なお、前記特許文献２では、三角形の法線を評価することにより、境界抽出を試みている。
【００１１】
ところで、G0連続境界（後述）では、境界が折れているため、CADメッシュにおいても、三角形の間の稜線が折れている。これを判別することで、容易に境界を認識することができる。しかし、例えば図４のように平面と円柱面が滑らかに接したり、図５のように球面と円錐面が滑らかに接することで構成されるG1連続境界（後述）の部分では、三角形も非常に滑らかに接続している。このため、従来の技術では、CADメッシュ上でこのようなG1連続境界を正確に抽出することが困難であった。
【００１２】
本発明は、CADメッシュが一定の規則に従って三角形分割されていることを利用してセグメントの境界を正確に抽出するためのものである。
【課題を解決するための手段】
【００１３】
本発明は、従来のセグメンテーションのように三角形メッシュの個々の三角形を主たる処理の対象とするのではなく、CADメッシュから円弧又は直線を抽出してG1連続境界の抽出を行うという、従来の手法とは基本的に異なる考え方を採用したものである。本発明における課題を解決する手段は、以下の項目のように記載できる。
【００１４】
（項目１）
CADメッシュ受付部と、Pアーク抽出処理部と、Pライン抽出処理部と、平滑Pアーク判定処理部と、平滑Pライン判定処理部と、円弧G1連続境界抽出部と、直線G1連続境界抽出部と、出力部とを備えており、
前記CADメッシュ受付部は、3次元CADモデルを三角形分割することにより生成された三角形メッシュであるCADメッシュのデータを受け付ける構成となっており、
前記Pアーク抽出処理部は、前記CADメッシュからPアークを抽出する構成となっており、
前記Pライン抽出処理部は、前記CADメッシュからPラインを抽出する構成となっており、
前記平滑Pアーク判定処理部は、前記Pアークが平滑Pアークかどうかを判定する構成となっており、
前記平滑Pライン判定処理部は、前記Pラインが平滑Pラインかどうかを判定する構成となっており、
前記円弧G1連続境界抽出部は、抽出された前記平滑Pアークを判定することにより、円弧G1連続境界を抽出する構成となっており、
前記直線G1連続境界抽出部は、抽出された前記平滑Pラインを判定することにより、直線G1連続境界を抽出する構成となっており、
前記出力部は、抽出された円弧G1連続境界及び直線G1連続境界を、その後のセグメンテーションのために出力する構成となっている
接平面連続境界の抽出システム。
【００１５】
（項目２）
前記円弧G1連続境界抽出部は、内部Pアーク判定部と、第１種円弧、第２種円弧及び／又は第３種円弧のための円弧G1連続境界判定部とを備えており、
前記内部Pアーク判定部は、前記Pアークが内部Pアークか否かを判定する構成となっており、
前記第１種円弧のために、円弧G1連続境界判定部は、前記Pアークが内部Pアークでなく、かつ、次の条件ａ）〜ｃ）
ａ）前記Pアークの片側で、その頂点に一つあるいは複数の他のPアークが端点で直交接続していること；
ｂ）前記Pアークの反対側に、平坦稜線を介して、三角形（すなわち平面）が接続していること；
ｃ）前記条件ａ）に記載した前記Pアークの頂点に端点で接続した一つあるいは複数の前記他のPアークの接線が、前記Pアークの片側において、前記Pアークの反対側の平面上にあること；
を満足する場合に、円弧G1連続境界と判定する構成となっており、
前記第２種円弧のために、円弧G1連続境界判定部は、前記Pアークが内部Pアークでなく、かつ、次の条件ａ）〜ｃ）
ａ）前記Pアークの片側で、その頂点に一つあるいは複数のPアークが端点で直交接続していること；
ｂ）前記Pアークの反対側で、その頂点に一つあるいは複数のPラインが端点で直交接続していること（但しPラインがPアークの軸と直交する場合を除く）；
ｃ）前記条件ａ）に記載した前記Pアークの頂点に端点で接続した一つあるいは複数の前記他のPアークの接線が、前記Pアークの片側において、前記Pアークの反対側のPラインと平行であるか、あるいは、前記Pアークの接線と前記Pアークの軸とがなす角と、前記Pラインと前記Pアークの軸とがなす角度とが同じであること；
を満足する場合に、円弧G1連続境界と判定する構成となっており、
前記第３種円弧のための円弧G1連続境界判定部は、前記Pアークが内部Pアークでなく、かつ、次の条件ａ）〜ｂ）
ａ）前記Pアークの両側でその頂点に一つあるいは複数の他のPアークが端点で直交接続していること；
ｂ）前記条件ａ）に記載した前記Pアークの両側に端点で接続した一つあるいは複数の前記他のPアークの接線が、前記Pアークの軸と平行となっていること；
を満足する場合に、円弧G1連続境界と判定する構成となっている
項目１に記載の抽出システム。
【００１６】
（項目３）
前記直線G1連続境界抽出部は、第１種直線及び／又は第２種直線のための直線G1連続境界判定部を備えており、
前記直線G1連続境界判定部は、第１種直線のために、次の条件ａ）〜ｃ）
ａ）前記平滑Pラインの片側において、前記平滑Pラインの頂点に一つあるいは複数のPアークが端点で直交接続していること；
ｂ）前記平滑Pラインにおける反対側に、一つの三角形あるいは平坦稜線を介して三角形（すなわち平面）が接続していること；
ｃ）前記平滑Pラインの端点に接続した前記Pアークの接線が、前記反対側の三角形で構成される平面上にあること；
を満足する場合に、直線G1連続境界と判定する構成となっており、
前記直線G1連続境界判定部は、第２種直線のために、次の条件ａ）〜ｂ）
ａ）前記平滑Pラインの両側において、前記平滑Pラインの頂点にそれぞれ一つあるいは複数のPアークがその端点で直交接続していること；
ｂ）前記平滑Pラインの両側の前記Pアークが、相異なる円弧上にあり、且つ、前記平滑Pラインと、前記Pアークの前記端点における接線とは、同じ平面上にあること
を満足する場合に、直線G1連続境界と判定する構成となっている
項目１又は２に記載の抽出システム。
【００１７】
（項目４）
以下のステップを備えることを特徴とする、接平面連続境界の抽出方法：
CADメッシュ受付部が、3次元CADモデルを三角形分割することにより生成された三角形メッシュであるCADメッシュのデータを受け付けるステップ；
Pアーク抽出処理部が、前記CADメッシュからPアークを抽出するステップ；
Pライン抽出処理部が、前記CADメッシュからPラインを抽出するステップ；
平滑Pアーク判定処理部が、前記Pアークは平滑Pアークかどうかを判定するステップ；
平滑Pライン判定処理部が、前記Pラインは平滑Pラインかどうかを判定するステップ；
円弧G1連続境界抽出部が、抽出された前記平滑Pアークを判定することにより、円弧G1連続境界を抽出するステップ；
直線G1連続境界抽出部が、抽出された前記平滑Pラインを判定することにより、直線G1連続境界を抽出するステップ；
出力部が、抽出された円弧G1連続境界及び直線G1連続境界を、その後のセグメンテーションのために出力するステップ。
【００１８】
（項目５）
項目４記載の抽出方法をコンピュータにより実行するためのコンピュータプログラム。
【発明の効果】
【００１９】
本発明によれば、CADメッシュ上でこのようなG1連続境界を正確に抽出することが可能となる。
【図面の簡単な説明】
【００２０】
【図１】プリミティブ曲面によって構成されたCADモデルを示す図である。
【図２】図１のCADモデルを三角形分割して得られた三角形メッシュを示す図である。
【図３】セグメンテーションによって復元されたプリミティブ曲面の一例を示す説明図である。
【図４】直線G1連続で接続する平面と円柱面との境界を示すための説明図である。
【図５】円弧G1連続で接続する球面と円錐面との境界を示すための説明図である。
【図６】本発明の一実施形態における抽出システムの全体的な構成を説明するためのブロック図である。
【図７】本実施形態の抽出方法の手順を説明するためのフローチャートである。
【図８】二面角を説明するための説明図である。
【図９】平坦稜線、折れ稜線と平滑稜線を説明するための説明図である。
【図１０】Pアークを説明するための説明図である。
【図１１】Pアークの抽出方法を説明するための説明図である。
【図１２】連続Pラインと単独Pラインとを説明するための説明図である。
【図１３】折れPアーク、平滑Pアーク及び平坦Pアークを説明するための説明図である。
【図１４】平滑な内部Pアークと平滑な境界Pアークとを説明するための説明図である。
【図１５】折れた境界Pアークと平坦な内部Pアークを説明するための説明図である。
【図１６】十字交差、Ｔ交差及び仮想Ｔ−Ｐアーク交差の例を示す説明図である。
【図１７】T-PアークとボーダーPアークを説明するための説明図である。
【図１８】球面及びトーラス面におけるT-Pアークを説明するための説明図である。
【図１９】球面あるいはトーラス面上に平滑Pアークがある場合における、内部Pアークの判定処理を説明するための説明図である。
【図２０】第１種円弧のG1連続境界抽出の処理を説明するための説明図である。
【図２１】第２種円弧のG1連続境界抽出の処理を説明するための説明図である。
【図２２】第３種円弧のG1連続境界抽出の処理を説明するための説明図である。
【図２３】第１種直線のG1連続境界抽出の処理を説明するための説明図である。
【図２４】第２種直線のG1連続境界抽出の処理を説明するための説明図である。
【発明を実施するための形態】
【００２１】
以下、添付図面を参照しながら、本発明の実施形態に係る接平面連続境界の抽出システム及び抽出方法について説明する。
【００２２】
（前提説明）
プリミティブ曲面（平面、円柱面、円錐面、球面又はトーラス面）から構成されるCADモデルで使われる用語及び概念についてここで説明する。
【００２３】
（プリミティブ曲面）
本実施形態においては、CADモデルの曲面を、平面、円柱面、円錐面、球面、トーラス面のいずれかであると仮定する。これらの曲面をプリミティブ曲面という。
【００２４】
（プリミティブ曲面の間の交線）
CADモデルは、これらのプリミティブ曲面を交差させることによって作られ、曲面同士が交差することによって、それらの交線として曲線が生成される。この交差曲線が、CADモデルのフェースの境界曲線となる。プリミティブ同士の交差曲線は、円弧（円を含む）、直線及びその他の曲線から構成される。ここで、後述するように、G1連続境界は、円弧か直線なので、これら以外の曲線については無視できる。
【００２５】
交差の仕方は、「曲面どうしがある角度をもって交差する場合」と「曲面同士が接する場合」に限られる。なお、交線上のある点（特異点）で、二つの曲面の法線が一致し、二つの曲面がこの点で「角度なし」で交差することがあるが、この特異点については、極微小な点なので、無視して差し支えない。前者の場合（曲面どうしがある角度をもって交差する場合）には、２曲面が角度をもって交差することになり、後者の場合（曲面同士が接する場合）には、２曲面が滑らかに交差する。前者の交差をG0連続交差と呼び、その交線をG0連続交線あるいはG0連続境界と呼ぶ。また、後者の交差をG1連続交差、その交線をG1連続交線あるいはG1連続境界と呼ぶ。下記表1では、プリミティブ曲面の可能なすべての組み合わせについてG1連続境界が生成される場合を示す。
【００２６】
【００２７】
表1に示すように、G1連続境界は、直線あるいは円弧のいずれかになる。
【００２８】
G1連続境界が直線になるのは、交差する２曲面が、次の組み合わせの場合に限られる。
【００２９】
［第１種直線］（平面×円柱面）あるいは、（平面×円錐面）の場合；
［第２種直線］（円柱面×円柱面）、（円柱面×円錐面）あるいは（円錐面×円錐面）の場合。
【００３０】
さらにG1連続境界が円弧になるのは、交差する２曲面のうちの少なくとも一方が球面あるいはトーラス面の場合に限られ、かつ、次の組み合わせの場合に限られる。
【００３１】
［第１種円弧］（平面×トーラス面）の場合；
［第２種円弧］（球面×円柱面）、（トーラス面×円柱面）、（球面×円錐面）あるいは（トーラス面×円錐面）の場合；
［第３種円弧］（球面×トーラス面）、（トーラス面×トーラス面）の場合。
【００３２】
（CADメッシュ上の円弧と直線）
CADソフトウェアからCADメッシュを作成する際に、CADモデルの曲面間を境界で分割し、さらに、曲面も規則的に分割し、三角形メッシュを作成することが多い。そのため、CADメッシュには、多数の内部曲線及び境界曲線が存在する。
【００３３】
そこで、CADメッシュから円弧と直線を抽出し、交差する円弧あるいは直線からプリミティブを認識可能であると考えられる。さらに［第１種円弧］、［第２種円弧］、［第３種円弧］、［第１種直線］、［第２種直線］の性質を用いて、G1連続境界をCADメッシュ上で抽出することが可能になる。以下、詳しく説明する。
【００３４】
（本実施形態の構成）
本実施形態の抽出システムは、接平面連続境界、即ち前記したG1連続境界を抽出するためのシステムである。
【００３５】
このシステムは、図６に示すように、CADメッシュ受付部１０と、Pアーク抽出処理部２０と、Pライン抽出処理部３０と、円弧G1連続境界抽出部４０と、直線G1連続境界抽出部５０と、出力部６０とを備えている。さらにこのシステムは、平滑Pアーク判定処理部７０と、平滑Pライン判定処理部８０とを備えている。
【００３６】
CADメッシュ受付部１０は、3次元CADモデルを三角形分割することにより生成された三角形メッシュであるCADメッシュのデータを受け付ける構成となっている。したがって、本実施形態で対象となるCADメッシュは、３次元CADモデルから生成されたものである。CADメッシュのデータは、例えばSTLファイルとして受け渡される。
【００３７】
Pアーク抽出処理部２０は、CADメッシュからPアーク（後述）を抽出する構成となっている。
【００３８】
Pライン抽出処理部３０は、CADメッシュからPライン（後述）を抽出する構成となっている。
【００３９】
円弧G1連続境界抽出部４０は、抽出されたPアークを判定することにより、円弧G1連続境界を抽出する構成となっている。
【００４０】
円弧G1連続境界抽出部４０は、内部Pアーク判定部４１と、円弧G1連続境界判定部４３とを備えている。
【００４１】
内部Pアーク判定部４１は、Pアークが内部Pアーク（後述）か否かを判定する構成となっている。
【００４２】
G1連続境界判定部４３は、［第１種円弧］、［第２種円弧］及び［第３種円弧］のために、G1連続境界を判定する構成となっている。判定条件については後述する。
【００４３】
直線G1連続境界抽出部５０は、抽出されたPラインを判定することにより、直線G1連続境界を抽出する構成となっている。直線G1連続境界抽出部５０は、第１種直線及び第２種直線のための直線G1連続境界判定部５２を備えている。
【００４４】
直線G1連続境界判定部５２は、第１種直線及び第２種直線のために直線G1連続境界と判定する構成となっている。判定条件については後述する。
【００４５】
出力部６０は、抽出された円弧G1連続境界及び直線G1連続境界を、その後のセグメンテーションのために、適宜の処理システムあるいは処理要素に出力する構成となっている。もちろん、出力部６０は、得られたデータを一旦記憶部（図示せず）に出力するものであってもよい。
【００４６】
平滑Pアーク判定処理部７０は、Pアーク抽出処理部２０で抽出されたPアークが平滑Pアーク（後述）であるかどうかを判定するものである。
【００４７】
平滑Pライン判定処理部８０は、Pライン抽出処理部３０で抽出されたPラインが平滑Pライン（後述）であるかどうかを判定するものである。
【００４８】
前記した各機能要素は、適宜なハードウエアに実装されたコンピュータプログラムにより構成可能である。もちろん、コンピュータプログラムで実行される機能をハードウエアで実行することは可能であり、その逆も可能である。
【００４９】
（本実施形態における抽出方法）
つぎに、前記した抽出システムを用いた抽出方法の一例を、図７を参照しながら説明する。
【００５０】
（図７のステップＳＡ−１）
まず、CADメッシュ受付部１０は、CADメッシュを受け取る。このCADメッシュは、例えば上記のSTLファイルで提供される。
【００５１】
（三角形メッシュ及び位相化）
ここで、三角形メッシュの一般的な性質について説明する。各三角形は、三つの頂点から構成される。メッシュの三角形は、連続な曲面を分割したものであるから、三角形はバラバラではなく、稜線と稜線とで隙間なく接続されている。つまり、メッシュにおいて三角形の頂点は複数の三角形で共有されており、また、三角形の稜線は一般に2個の三角形により共有されている。さらに、メッシュの三角形集合から、次のような接続関係を導出することができる。まず、三角形メッシュにおいて、3次元座標値が一致する頂点を同一の頂点とし、さらに、同じ2頂点を結ぶ辺を同一の稜線とする。このように三角形の頂点、稜線の接続関係を構築することを位相化という。以下では、このような位相化が行われた三角形メッシュを前提とする。
【００５２】
（二面角(dihedral angle)と、平坦稜線、平滑稜線及び折れ稜線）
上記の位相化された三角形メッシュでは、各三角形は、その隣りの三角形と関係付けられているので、図８に示すように、隣り合う三角形が、それらの間の稜線において交差する角度を容易に計算することができる。この角度（図８中の角度γ）を二面角と呼ぶ。二面角が180度である稜線を平坦稜線と呼ぶ（図９参照）。二面角が180度からある程度離れた角度である稜線は、角があるので折れ稜線と呼ぶ（図９参照）。また、二面角が180度ではないが、それに近い値の場合は、滑らかな曲面上の稜線を表すので、平滑稜線と呼ぶ（図９参照）。「それに近い値」は、基本的にはユーザの指定により決定される。ただし、CAD側で「円を多角形近似するときの分割数」を指定する場合があるので、その値を参照してこの値を決めることもできる。例えば、円を36分割している場合には、「それに近い値」は、内接正36多角形の１つの内角＝170度より大きい値、例えば、175度とできる。
【００５３】
（図７のステップＳＡ−２…Pアークとその抽出）
前記した三角形メッシュは多面体であるので、その稜線を辿っていくと、頂点の列即ち折れ線が生成される。折れ線の中には、そのすべての頂点が、ある一つの円弧上に乗っているものがあり、本明細書ではこれをPアーク(polyline arc)と呼ぶ。ただし、円弧上においても折れ線の頂点の並び順は変わらないものとする。すなわち、円弧上で折れ線の始点に対して各頂点がなす円弧の中心角は、折れ線上の頂点の並び順に対して単調に増加するものとする。例えば、図１０では、球面が三角形分割されているので、その球面上に多数のPアークが存在する。
【００５４】
よって、Pアーク抽出処理部２０は、この性質を使って、PアークをCADメッシュから抽出する。すなわち、前述の位相付きの三角形メッシュでは、頂点と頂点が稜線で接続されているので、ある頂点からそれに隣接する頂点を次々と辿って行くことによって折れ線を作ることができる。空間中の円は(一直線上にない)3点で一意に決定できるので、稜線で接続された3頂点(但し3頂点がメッシュの三角形をなす場合を除く)について、図１１に示すように、その3頂点V1,V2,V3を通る円弧を定めることができる。そして、その3頂点の両端の2頂点から、その円弧に沿って、他の接続する頂点を稜線沿いに辿って行き、辿れなくなるか、あるいは、一周して既に辿った頂点に行き着くまで辿る。
【００５５】
このようにして辿った折れ線が4個以上の頂点を含む場合には、折れ線の頂点は円弧上にあるので、これをPアークとする。この手続きを、すべての連続する3頂点の組に付いて行うことによって、Pアーク抽出処理部２０は、Pアークを抽出することができる。
【００５６】
Pアークは、空間の円弧を折れ線で近似したものである。Pアークに対して、その中心、半径、Pアークの円弧を含む平面、中心軸(中心を通り、平面の法線を方向ベクトルとする直線)がそれぞれ定義される、それらをPアークの中心、Pアークの半径、Pアークの平面、Pアークの中心軸と呼ぶ。
【００５７】
（図７のステップＳＡ−３…Pラインとその抽出）
CADメッシュにおいて、円柱面フェース、あるいは円錐面フェースの上で、一つあるいは複数の稜線が連続して一つの直線をなすものをPラインという。一本の稜線で構成されるものを単独Pラインといい、複数の稜線出構成されるものを連続Pラインという。(図１２（ａ）（ｂ）参照)。
【００５８】
連続Pラインについては、Pアークと同様にして、同じ直線上にある稜線を辿ることによって、Pライン抽出処理部３０により、容易に抽出できるが、本例では、Pアークに接続しているPラインだけが必要なので、次にようにして求める。すなわち、あるPアークの頂点（端点も含む）と直交接続して、且つPアークの軸を通る平面上の稜線から出発し、それに隣接する稜線で、出発した稜線と同じ直線上にある稜線を次々と辿れるところまで辿って行くことによって連続Pラインを抽出する。また、一つの稜線も辿れなかったときは、出発した稜線は単独Pラインとなる。
【００５９】
ステップＳＡ−３は、ステップＳＡ−２の後に行われる。
【００６０】
（図７のステップＳＡ−４…平滑Pアークの判定処理）
上で述べたように、G1連続境界が円弧になるのは、２曲面のうちの少なくとも一方が球あるいはトーラスの場合に限られる。
【００６１】
この場合について、円弧G1連続境界抽出部４０により、Pアークを用いて、円弧G1連続境界を求める方法を以下に示す。
【００６２】
（折れPアーク、平滑Pアーク、平坦Pアーク）
ステップＳＡ−２で求めたPアークは、それに含まれる稜線が折れ稜線のもの、平滑稜線のもの、そして平坦稜線のものに分けられる。それぞれ、折れPアーク、平滑Pアーク、平坦Pアークと呼ぶ(図１３)。この平滑Pアークの定義から、平滑Pアーク判定処理部７０は、Pアークが平滑Pアークであるかどうかを判定することができる。折れPアークは、CADモデルでは、平面が円柱の中心軸に直交するように交差する場合の交線に対応する。平滑Pアークは、曲面を分割した場合や曲面のG1連続境界として現れる。また、平坦Pアークは、円柱面あるいは円錐面を分割したときに現れる。
【００６３】
（図７のステップＳＡ−５…内部Pアークと境界Pアーク）
さらに、CADメッシュに含まれる平滑Pアークには、二つのタイプがある。一つは、図１４及び図１５に示すように、球面とトーラス面とを母曲面とするフェースを三角形分割することによって、フェースの内部に現れるものである。これを内部Pアークと呼ぶ。これらは滑らかな曲面上のPアークなので、平滑Pアークとなる。また、円柱面や円錐面状に現れる平坦Pアークも内部Pアークとなる。もう一つのタイプの平滑Pアークは、フェースの境界に対応するもので、これを境界Pアークと呼ぶ。
【００６４】
上に述べた、折れPアーク、平滑Pアーク及び平坦Pアークと、内部Pアーク及び境界Pアークとの関係を表２にまとめる。
【００６５】
【００６６】
なお、表２において、○は、折れPアーク、平滑Pアーク及び平坦Pアークが、内部Pアークあるいは境界Pアークになる可能性があることを示し、×はこれらが内部Pアークあるいは境界Pアークになる可能性がないことを示す。
【００６７】
求めたいG1連続境界に関係するのは、平滑で境界のPアークである。これを平滑境界Pアークと呼ぶことにする。平滑Pアークかどうかは、前述のように二面角を用いて決めることができる。そこで、このステップＳＡ−５では、平滑Pアークを、内部Pアークと境界Pアークに判定する。この両者は排他的関係にあるので、一方だけを判定すればよい。すなわち、内部Pアーク判定部４１により、内部Pアークでないことがわかれば、それは境界Pアークとする。よって、以下では、内部Pアーク判定部４１による内部Pアークの判定法について述べる。これには、後述するように、図１６で示すような、Pアーク間の位置関係によって、十字交差による判定方法と、T交差による判定方法と、仮想T-Pアーク交差による判定方法とがある。
【００６８】
（十字交差による判定）
球面やトーラス面の三角形分割では、等パラメタ線というものに沿って三角形分割されるのが一般的である。例えば、半径1の球面は、二つのパラメタu,vを用いて、
p=(cos u cos v, cos u sin v, sin u)
のようにパラメタ表現することができる。この式で、u＝一定、あるいはv＝一定とすると曲線(等パラメタ曲線)が定義される。特に球面とトーラス面では、等パラメタ曲線は円弧となる。CADモデルの三角形分割では、この等パラメタ線にそって三角形分割されるのが一般的であるため、CADメッシュではこの等パラメタ線の円弧に対応するPアークが含まれることになる。
【００６９】
さらに、図１０に示すように、u＝一定の等パラメタ線とv＝一定の等パラメタ線は、曲面上で交差することから、CADメッシュから求めたPアークで十字状に交差しているものは等パラメタ線に対応することになる。これはトーラス面でも同様である。このような、u＝一定の等パラメタ線とv＝一定の等パラメタ線の交差を十字交差と呼ぶことにする。
【００７０】
言い換えると、二つの平滑Pアークが十字交差していれば、これらのPアークは球面フェースあるいはトーラス面フェースの内部Pアークになる。内部Pアーク判定部４１は、まず、この条件を用いて、内部Pアークを判定できる。
【００７１】
（T交差による判定）
図１７に示すように、Pアークが、その端点で別のPアーク内にT字型に交わる場合をT交差とし、その交点をT交点とする。さらに、前者のPアークをT-Pアークと呼び、後者をボーダーPアークと呼ぶ。ここで、T交差とは、Pアークの端点がボーダーPアークの内部の頂点(ボーダーPアークの端点以外)に一致する場合をいう。さらに、その場合だけでなく、Pアークの端点に外挿した円弧(図１７中の破線で示す)がPアークに交差する場合も、T交差に含める。これらを区別するために、前者を直接T-Pアークと呼び、後者を間接T-Pアークと呼ぶ。すなわち間接T-Pアークとは、図１７に破線で示すようにPアークを延長したときにT交差となるPアークをいう。
【００７２】
前記（十字交差による判定）では、Pアークの十字交差によって内部Pアークの判定を行っていたが、CADの三角形分割の方法によっては、まれに球面・トーラス面のメッシュの内部Pアークが十字交差しないことがある。この場合、T交差によって内部Pアークを判定することができる(図１８)。
【００７３】
これは以下のように証明できる。
・まずボーダーPアークが境界Pアークの場合を考える。もしT-Pアークも境界Pアークとすると、T交点において三つ以上の曲面(ボーダーPアークの両側の曲面と、T-Pアークの両側の曲面を含む三つの曲面)が交差していることになり、T交点はボーダーPアークの端点でなければならない。しかし、T-Pアークは、ボーダーPアークの端点以外で交差しなければならないので仮定に反する。よってT-Pアークは内部Pアークでなければならない。
・次にボーダーPアークが内部Pアークである場合を考える。もしT-Pアークが境界Pアークであるとすると、T交点において、曲面はボーダーPアークの方向に不連続になっており、ボーダーPアークはそこに端点を持たなければならない。これは、T交点が端点ではないことに矛盾する。よって、T-Pアークは内部Pアークでなければならない。
【００７４】
したがって、前記の判定基準により、内部Pアーク判定部４１は、内部Pアークを判定することができる。
【００７５】
（仮想T-Pアーク交差による判定）
図１９に示すように、三角形分割の方法によっては、等パラメタ線による分割がuあるいはv方向の内の一方向だけの場合があり、その方向にだけ等パラメタ線に対する平滑Pアークが存在し、他の方向には平滑Pアークが存在しないことがある。すなわち、Pアークに十字交差あるいはT交差が存在しない場合がある。このような場合、内部Pアーク判定部４１は、次の方法で内部Pアークを判定する。これらの平滑Pアークを
a1, a2 …, an
とすると、もしすべての隣り合う二つの平滑Pアーク
ai, ai+1
が、仮想的な平滑稜線Q（仮想T-Pアークという）を介して接続しているならば、その平滑稜線Qの内部頂点と接続する平滑Pアークは内部Pアークとなる。等パラメタ線のPアークが球面あるいはトーラス面上にあることを判定するために、
（１）この等パラメタ線のPアークの軸を通る平面を作成して、
（２）Pアーク群とその平面との交点群を求め、
（３）その交点群を補間して、もしその交点群が円弧であれば、その交点で仮想T-Pアークを作成し、
（４）上記の十字交差あるいはT交差判定によって、内部Pアーク及び境界Pアークを判定することができる。
【００７６】
（図７のステップＳＡ−７…球面、トーラス面のG1連続境界の抽出）
ステップＳＡ−５の処理によって、平滑Pアークで、かつ、内部Pアークであるものをすべて判定することができる。平滑Pアークは、内部Pアークか境界Pアークのいずれかであるので、ステップＳＡ−５の方法によって内部Pアークと判定されなかった平滑Pアークは境界Pアーク、すなわち平滑境界Pアークとする。
【００７７】
この平滑境界Pアークは、CADモデルにおいて母曲面同士がG1連続で交差することによって生成された交差曲線に対応するので、フェースのG1連続境界になる。
【００７８】
この平滑境界Pアークは、G1連続境界であることを次の判定処理で確認できる。
【００７９】
前述のように、G1連続境界が円弧になるのは、次の三つの場合である。
【００８０】
［第１種円弧］（平面×トーラス面）
［第２種円弧］（球面×円柱面）、（トーラス面×円柱面）、（球面×円錐面）あるいは（トーラス面×円錐面）
［第３種円弧］（球面×トーラス面）、（トーラス面×トーラス面）
それぞれの場合について、円弧G1連続境界の抽出の方法を説明する。
【００８１】
（図７のステップＳＡ−７・・・［第１種円弧］の場合）
前述の
［第１種円弧］（平面×トーラス面）
の場合は、平面領域が平滑な境界でトーラス面に接している場合である。
【００８２】
本実施形態では、円弧G1連続境界判定部４３が、以下の３条件を判定することによって、［第１種円弧］のために、平滑Pアークを抽出することができる。この手順を、図２０をさらに参照しながら説明する。なお、これらの条件を全て満たした場合にG1連続境界Pアークとなる。
ａ）PアークPの片側（図２０において下側）において、PアークPのいずれかの頂点（図示例では頂点Ａ）に一つあるいは複数のPアーク（図示例ではPアークＱ）がその端点で直交接続していること。ここで、本例では、PアークQの端点AでPアークQの接線Tを求めておく；
ｂ）その反対側（図２０において上側）でPアークPが、互いに平坦稜線で接続している三角形（平面S）と接続していること；
ｃ）前記したすべてのPアークQの接線Tが平面S上にあること；
以上の条件により抽出されたPアークPは、円弧G1連続境界である。
【００８３】
（図７のステップＳＡ−７・・・［第２種円弧］の場合） 前述の
［第２種円弧］：（（球面×円柱面）、（トーラス面×円柱面）、（球面×円錐面）あるいは（トーラス面×円錐面））
の場合とは、球面あるいはトーラス面が平滑な境界で円柱面あるいは円錐面に接している場合である。
【００８４】
本実施形態では、円弧G1連続境界判定部４３が、以下の３条件を判定することによって、［第２種円弧］のために平滑Pアークを抽出することができる。図２１をさらに参照しながら説明する。なお、これらの条件を全て満たした場合にG1連続境界Pアークとなる。
ａ）PアークPの片側（図２１において上側）において、PアークPのいずれかの頂点（図２１においてAi）に一つあるいは複数のPアークＱが端点で直交接続していること。ここで本例では、PアークQの端点AでPアークQの接線Tを求めておく；
ｂ）その反対側（図２１において下側）でPアークPの頂点に、一つあるいは複数のPラインLが端点で直交接続していること。ここでPラインLの端点は、図２１においてAｊである；
ｃ）すべてのPアークQの接線Tが、すべてのPラインLと平行であるか、あるいは、「PアークPの軸Oと接線Tの角度」と「軸OとPラインLの角度」とが同じである（つまり図２１において角度α＝角度βである。ただし、α≠９０°である）こと。ここで、角度αの値は、０°＜α＜１８０°となる；
このようにして抽出されたPアークPは、円弧G1連続境界である。
【００８５】
（図７のステップＳＡ−７・・・［第３種円弧］の場合）
前述の
［第３種円弧］（球面×トーラス面）、（トーラス面×トーラス面）
の場合は、球面あるいはトーラス面が平滑な境界でトーラス面に接している場合である。
【００８６】
本実施形態では、円弧G1連続境界判定部４３が、以下の２条件を判定することによって、［第３種円弧］のために平滑Pアークを抽出することができる。図２２をさらに参照しながら説明する。なお、これらの条件を全て満たした場合にG1連続境界Pアークとなる。
ａ）PアークPの両側（図２２における左右両側）で、PアークPの頂点（図２２では頂点Ａ）に一つあるいは複数の異なるPアーク（図２２のQ1,Q2）が、それらの端点Aで直交接続していること。本実施形態では、その端点AにおけるPアーク（Q1，Q2）の接線（図２２のT1、T2）をそれぞれ求める；
ｂ）すべてのPアーク（Q１、Q2）の接線（T1、T2）は、PアークPの軸Oと平行であること；
このようにして抽出されたPアークPは、円弧G1連続境界である。
【００８７】
（図７のステップＳＡ−８…平滑Pライン判定処理）
前述のように、G1連続境界が直線になるのは、次の二つの場合である。
【００８８】
［第１種直線］（平面×円柱面）あるいは、（平面×円錐面）
［第２種直線］（円柱面×円柱面）、（円柱面×円錐面）あるいは（円錐面×円錐面）
それぞれの場合について、直線G1連続境界の抽出の方法を説明する。
【００８９】
（折れPライン、平滑Pライン）
直線G1連続境界は、メッシュ上のPラインを構成する。Pラインは、折れPライン、平滑Pラインに分けられる。Pラインに含まれる稜線がすべて折れ稜線の場合を折れPライン、すべて平滑稜線の場合を平滑Pラインと称する。
【００９０】
したがって、平滑Pライン判定処理部８０は、この定義に基づいて、平滑Pラインを判定することができる。
【００９１】
（図７のステップＳＡ−１０…［第１種直線］の場合）
前述の
［第１種直線］（平面×円柱面）あるいは、（平面×円錐面）
の場合は、平面領域が平滑な境界で円柱面あるいは円錐面に接している場合である。
【００９２】
本実施形態では、直線G1連続境界判定部５２が、以下の３条件を判定することによって、［第１種直線］のために平滑Pラインを抽出することができる。図２３をさらに参照しながら説明する。なお、これらの条件を全て満たした場合にG1連続境界Pラインとなる。
ａ）PラインL（図２３中の頂点AB間）の片側（図２３において左側）において、L上の頂点ＡにPアークPが端点Ａで直交接続していること。ここで本実施形態では、PアークPの端点AでPアークPの接線Tを求める；
ｂ）その反対側（図２３において右側）で、PラインLが三角形Mと接続しており、かつ、三角形Mと三角形Nは平坦稜線CBで接続していて、三角形Mと三角形Nが一つの平面になっていること；
ｃ）PアークPの接線Tは、三角形Mの平面上にあること；
この条件により抽出されたPラインは、直線G1連続境界である。
【００９３】
（図７のステップＳＡ−１１…［第２種直線］の場合）
最後に残ったのが、円柱面や円錐面どうしが接することによって直線G1連続境界をもつ次の場合である。
［第２種直線］（円柱面×円柱面）、（円柱面×円錐面）あるいは（円錐面×円錐面）
【００９４】
この場合も、直線G1連続境界は、三角形メッシュ上の平滑Pラインとなる。本実施形態では、直線G1連続境界判定部５２が、以下の２条件を判定することによって、［第２種直線］のために平滑Pラインを抽出することができる。図２４をさらに参照しながら説明する。なお、これらの条件を全て満たした場合にG1連続境界Pラインとなる。
ａ）PラインLの両側で、L上の頂点Ａに、それぞれ少なくとも一つのPアークP1,P2が端点で直交接続していること。ここで、本例では、端点Aにおいて、これらのPアークP1,P2の接線T1、T2を求める。
ｂ）これらのPアークP1、P2は、相異なる円弧上にあり、かつ、PラインLとこれらの接線T1,T2が、同じ平面上にあること。
【００９５】
この条件により抽出されたPラインは、直線G1連続境界である。
【００９６】
前記のようにして、円弧及び直線のＧ１連続境界をいずれも抽出することができる。その後、抽出されたＧ１連続境界を、出力部６０により、所望のメモリあるいはシステムに送る。これにより、抽出されたＧ１連続境界を、例えばＣＡＤメッシュのセグメントのために利用することができる。
【００９７】
なお、本発明は、前記した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変更を加え得るものである。
【００９８】
例えば、前記した各構成要素は、機能ブロックとして存在していればよく、独立したハードウエアとして存在しなくても良い。また、実装方法としては、ハードウエアを用いてもコンピュータソフトウエアを用いても良い。さらに、本発明における一つの機能要素が複数の機能要素の集合によって実現されても良く、本発明における複数の機能要素が一つの機能要素により実現されても良い。
【００９９】
また、本発明を構成する各機能要素は、離散して存在しても良い。離散して存在する場合には、例えばネットワークを介して必要なデータを受け渡すことができる。各部の内部における各機能も、同様に、離散して存在することが可能である。例えば、グリッドコンピューティングやクラウドコンピューティングを用いて、本実施形態における各機能要素あるいはその一部分を実現することも可能である。
【符号の説明】
【０１００】
１０ CADメッシュ受付部
２０ Pアーク抽出処理部
３０ Pライン抽出処理部
４０ 円弧G1連続境界抽出部
４１ 内部Pアーク判定部
４３ G連続境界判定部
５０ 直線G1連続境界抽出部
５２ 直線G1連続境界判定部
６０ 出力部
７０ 平滑Pアーク判定処理部
８０ 平滑Pライン判定処理部
【特許請求の範囲】
【請求項１】
CADメッシュ受付部と、Pアーク抽出処理部と、Pライン抽出処理部と、円弧G1連続境界抽出部と、直線G1連続境界抽出部と、平滑Pアーク判定処理部と、平滑Pライン判定処理部と、出力部とを備えており、
前記CADメッシュ受付部は、3次元CADモデルを三角形分割することにより生成された三角形メッシュであるCADメッシュのデータを受け付ける構成となっており、
前記Pアーク抽出処理部は、前記CADメッシュからPアークを抽出する構成となっており、
前記Pライン抽出処理部は、前記CADメッシュからPラインを抽出する構成となっており、
前記平滑Pアーク判定処理部は、前記Pアークが平滑Pアークかどうかを判定する構成となっており、
前記平滑Pライン判定処理部は、前記Pラインが平滑Pラインかどうかを判定する構成となっており、
前記円弧G1連続境界抽出部は、抽出された前記平滑Pアークを判定することにより、円弧G1連続境界を抽出する構成となっており、
前記直線G1連続境界抽出部は、抽出された前記平滑Pラインを判定することにより、直線G1連続境界を抽出する構成となっており、
前記出力部は、抽出された円弧G1連続境界及び直線G1連続境界を、その後のセグメンテーションのために出力する構成となっている
接平面連続境界の抽出システム。
【請求項２】
前記円弧G1連続境界抽出部は、内部Pアーク判定部と、第１種円弧、第２種円弧及び／又は第３種円弧のための円弧G1連続境界判定部とを備えており、
前記内部Pアーク判定部は、前記Pアークが内部Pアークか否かを判定する構成となっており、
前記第１種円弧のために、円弧G1連続境界判定部は、前記Pアークが内部Pアークでなく、かつ、次の条件ａ）〜ｃ）
a) 前記Pアークの片側で、その頂点に一つあるいは複数の他のPアークが端点で直交接続していること；
b) 前記Pアークの反対側に、平坦稜線を介して、三角形（すなわち平面）が接続していること；
c) 前記条件ａ）に記載した前記Pアークの頂点に端点で接続した一つあるいは複数の前記他のPアークの接線が、前記Pアークの片側において、前記Pアークの反対側の平面上にあること；
を満足する場合に、円弧G1連続境界と判定する構成となっており、
前記第２種円弧のために、円弧G1連続境界判定部は、前記Pアークが内部Pアークでなく、かつ、次の条件ａ）〜ｃ）
a) 前記Pアークの片側で、その頂点に一つあるいは複数のPアークが端点で直交接続していること；
b) 前記Pアークの反対側で、その頂点に一つあるいは複数のPラインが端点で直交接続していること（但しPラインがPアークの軸と直交する場合を除く）；
c) 前記条件ａ）に記載した前記Pアークの頂点に端点で接続した一つあるいは複数の前記他のPアークの接線が、前記Pアークの片側において、前記Pアークの反対側のPラインと平行であるか、あるいは、前記Pアークの接線と前記Pアークの軸とがなす角と、前記Pラインと前記Pアークの軸とがなす角度とが同じであること；
を満足する場合に、円弧G1連続境界と判定する構成となっており、
前記第３種円弧のための円弧G1連続境界判定部は、前記Pアークが内部Pアークでなく、かつ、次の条件ａ）〜ｂ）
a) 前記Pアークの両側でその頂点に一つあるいは複数の他のPアークが端点で直交接続していること；
b) 前記条件ａ）に記載した前記Pアークの両側に端点で接続した一つあるいは複数の前記他のPアークの接線が、前記Pアークの軸と平行となっていること；
を満足する場合に、円弧G1連続境界と判定する構成となっている
請求項１に記載の抽出システム。
【請求項３】
前記直線G1連続境界抽出部は、第１種直線及び／又は第２種直線のための直線G1連続境界判定部を備えており、
前記直線G1連続境界判定部は、第１種直線のために、次の条件ａ）〜ｃ）
ａ）前記平滑Pラインの片側において、前記平滑Pラインの頂点に一つあるいは複数のPアークが端点で直交接続していること；
ｂ）前記平滑Pラインにおける反対側に、一つの三角形あるいは平坦稜線を介して三角形（すなわち平面）が接続していること；
ｃ）前記平滑Pラインの端点に接続した前記Pアークの接線が、前記反対側の三角形で構成される平面上にあること；
を満足する場合に、直線G1連続境界と判定する構成となっており、
前記直線G1連続境界判定部は、第２種直線のために、次の条件ａ）〜ｂ）
a)前記平滑Pラインの両側において、前記平滑Pラインの頂点にそれぞれ一つあるいは複数のPアークがその端点で直交接続していること；
b)前記平滑Pラインの両側の前記Pアークが、相異なる円弧上にあり、且つ、前記平滑Pラインと、前記Pアークの前記端点における接線とは、同じ平面上にあること
を満足する場合に、直線G1連続境界と判定する構成となっている
請求項１又は２に記載の抽出システム。
【請求項４】
以下のステップを備えることを特徴とする、接平面連続境界の抽出方法：
CADメッシュ受付部が、3次元CADモデルを三角形分割することにより生成された三角形メッシュであるCADメッシュのデータを受け付けるステップ；
Pアーク抽出処理部が、前記CADメッシュからPアークを抽出するステップ；
Pライン抽出処理部が、前記CADメッシュからPラインを抽出するステップ；
平滑Pアーク判定処理部が、前記Pアークは平滑Pアークかどうかを判定するステップ；
平滑Pライン判定処理部が、前記Pラインは平滑Pラインかどうかを判定するステップ；
円弧G1連続境界抽出部が、抽出された前記平滑Pアークを判定することにより、円弧G1連続境界を抽出するステップ；
直線G1連続境界抽出部が、抽出された前記平滑Pラインを判定することにより、直線G1連続境界を抽出するステップ；
出力部が、抽出された円弧G1連続境界及び直線G1連続境界を、その後のセグメンテーションのために出力するステップ。
【請求項５】
請求項４記載の抽出方法をコンピュータにより実行するためのコンピュータプログラム。
【請求項１】
CADメッシュ受付部と、Pアーク抽出処理部と、Pライン抽出処理部と、円弧G1連続境界抽出部と、直線G1連続境界抽出部と、平滑Pアーク判定処理部と、平滑Pライン判定処理部と、出力部とを備えており、
前記CADメッシュ受付部は、3次元CADモデルを三角形分割することにより生成された三角形メッシュであるCADメッシュのデータを受け付ける構成となっており、
前記Pアーク抽出処理部は、前記CADメッシュからPアークを抽出する構成となっており、
前記Pライン抽出処理部は、前記CADメッシュからPラインを抽出する構成となっており、
前記平滑Pアーク判定処理部は、前記Pアークが平滑Pアークかどうかを判定する構成となっており、
前記平滑Pライン判定処理部は、前記Pラインが平滑Pラインかどうかを判定する構成となっており、
前記円弧G1連続境界抽出部は、抽出された前記平滑Pアークを判定することにより、円弧G1連続境界を抽出する構成となっており、
前記直線G1連続境界抽出部は、抽出された前記平滑Pラインを判定することにより、直線G1連続境界を抽出する構成となっており、
前記出力部は、抽出された円弧G1連続境界及び直線G1連続境界を、その後のセグメンテーションのために出力する構成となっている
接平面連続境界の抽出システム。
【請求項２】
前記円弧G1連続境界抽出部は、内部Pアーク判定部と、第１種円弧、第２種円弧及び／又は第３種円弧のための円弧G1連続境界判定部とを備えており、
前記内部Pアーク判定部は、前記Pアークが内部Pアークか否かを判定する構成となっており、
前記第１種円弧のために、円弧G1連続境界判定部は、前記Pアークが内部Pアークでなく、かつ、次の条件ａ）〜ｃ）
a) 前記Pアークの片側で、その頂点に一つあるいは複数の他のPアークが端点で直交接続していること；
b) 前記Pアークの反対側に、平坦稜線を介して、三角形（すなわち平面）が接続していること；
c) 前記条件ａ）に記載した前記Pアークの頂点に端点で接続した一つあるいは複数の前記他のPアークの接線が、前記Pアークの片側において、前記Pアークの反対側の平面上にあること；
を満足する場合に、円弧G1連続境界と判定する構成となっており、
前記第２種円弧のために、円弧G1連続境界判定部は、前記Pアークが内部Pアークでなく、かつ、次の条件ａ）〜ｃ）
a) 前記Pアークの片側で、その頂点に一つあるいは複数のPアークが端点で直交接続していること；
b) 前記Pアークの反対側で、その頂点に一つあるいは複数のPラインが端点で直交接続していること（但しPラインがPアークの軸と直交する場合を除く）；
c) 前記条件ａ）に記載した前記Pアークの頂点に端点で接続した一つあるいは複数の前記他のPアークの接線が、前記Pアークの片側において、前記Pアークの反対側のPラインと平行であるか、あるいは、前記Pアークの接線と前記Pアークの軸とがなす角と、前記Pラインと前記Pアークの軸とがなす角度とが同じであること；
を満足する場合に、円弧G1連続境界と判定する構成となっており、
前記第３種円弧のための円弧G1連続境界判定部は、前記Pアークが内部Pアークでなく、かつ、次の条件ａ）〜ｂ）
a) 前記Pアークの両側でその頂点に一つあるいは複数の他のPアークが端点で直交接続していること；
b) 前記条件ａ）に記載した前記Pアークの両側に端点で接続した一つあるいは複数の前記他のPアークの接線が、前記Pアークの軸と平行となっていること；
を満足する場合に、円弧G1連続境界と判定する構成となっている
請求項１に記載の抽出システム。
【請求項３】
前記直線G1連続境界抽出部は、第１種直線及び／又は第２種直線のための直線G1連続境界判定部を備えており、
前記直線G1連続境界判定部は、第１種直線のために、次の条件ａ）〜ｃ）
ａ）前記平滑Pラインの片側において、前記平滑Pラインの頂点に一つあるいは複数のPアークが端点で直交接続していること；
ｂ）前記平滑Pラインにおける反対側に、一つの三角形あるいは平坦稜線を介して三角形（すなわち平面）が接続していること；
ｃ）前記平滑Pラインの端点に接続した前記Pアークの接線が、前記反対側の三角形で構成される平面上にあること；
を満足する場合に、直線G1連続境界と判定する構成となっており、
前記直線G1連続境界判定部は、第２種直線のために、次の条件ａ）〜ｂ）
a)前記平滑Pラインの両側において、前記平滑Pラインの頂点にそれぞれ一つあるいは複数のPアークがその端点で直交接続していること；
b)前記平滑Pラインの両側の前記Pアークが、相異なる円弧上にあり、且つ、前記平滑Pラインと、前記Pアークの前記端点における接線とは、同じ平面上にあること
を満足する場合に、直線G1連続境界と判定する構成となっている
請求項１又は２に記載の抽出システム。
【請求項４】
以下のステップを備えることを特徴とする、接平面連続境界の抽出方法：
CADメッシュ受付部が、3次元CADモデルを三角形分割することにより生成された三角形メッシュであるCADメッシュのデータを受け付けるステップ；
Pアーク抽出処理部が、前記CADメッシュからPアークを抽出するステップ；
Pライン抽出処理部が、前記CADメッシュからPラインを抽出するステップ；
平滑Pアーク判定処理部が、前記Pアークは平滑Pアークかどうかを判定するステップ；
平滑Pライン判定処理部が、前記Pラインは平滑Pラインかどうかを判定するステップ；
円弧G1連続境界抽出部が、抽出された前記平滑Pアークを判定することにより、円弧G1連続境界を抽出するステップ；
直線G1連続境界抽出部が、抽出された前記平滑Pラインを判定することにより、直線G1連続境界を抽出するステップ；
出力部が、抽出された円弧G1連続境界及び直線G1連続境界を、その後のセグメンテーションのために出力するステップ。
【請求項５】
請求項４記載の抽出方法をコンピュータにより実行するためのコンピュータプログラム。
【図６】
【図７】
【図８】
【図１】
【図２】
【図３】
【図４】
【図５】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図７】
【図８】
【図１】
【図２】
【図３】
【図４】
【図５】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【公開番号】特開２０１３−８８８２５（Ｐ２０１３−８８８２５Ａ）
【公開日】平成２５年５月１３日（２０１３．５．１３）
【国際特許分類】
【出願番号】特願２０１１−２２５４０７（Ｐ２０１１−２２５４０７）
【出願日】平成２３年１０月１３日（２０１１．１０．１３）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２３年度、独立行政法人科学技術振興機構、若手ベンチャー創出推進事業、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（５０４１３７９１２）国立大学法人 東京大学 (1,942)
【Ｆターム（参考）】
【公開日】平成２５年５月１３日（２０１３．５．１３）
【国際特許分類】
【出願日】平成２３年１０月１３日（２０１１．１０．１３）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２３年度、独立行政法人科学技術振興機構、若手ベンチャー創出推進事業、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（５０４１３７９１２）国立大学法人 東京大学 (1,942)
【Ｆターム（参考）】
[ Back to top ]