(57)【特許請求の範囲】
【請求項１】
外部データ入力手段により対象物の境界データをコンピュータに入力し、コンピュータを用いて前記境界データを境界平面が直交する直方体セルが隙間なく集合したセル複合体内のセル内形状データに変換する方法であって、
前記コンピュータの切断点計算手段により、前記境界データを内包するセル複合体を定義し、境界データがセル複合体を構成する直方体セルの稜線又は頂点を切断する切断点を計算する切断点計算ステップと、
前記コンピュータのサイクル形成手段により、前記各直方体セルを、前記切断点のある境界セルと切断点のない非境界セルとに区分し、各境界セル毎に、セル表面と境界データとの切断線分を求め、前記切断点と切断線分を交互に順に結んで閉じた切断線分サイクルを形成するサイクル形成ステップと、
前記コンピュータのサイクル内分割手段により、各境界セル毎に、前記切断線分サイクルの内側を隣接する辺を共有するサイクル内三角形に分割するサイクル内分割ステップと、
前記コンピュータの簡略化手段により、各境界セル毎に、各稜線における複数の切断点の１点化とサイクル内三角形のセルへの登録を行う簡略化ステップとを有し、
前記簡略化ステップにおいて、前記簡略化手段は、各境界セル毎に、
（１）同一のセル稜線上に複数の切断点があれば、原点により近い単一の切断点に一点化し、
（２）一点化された切断点が同じサイクル内三角形内にあれば当該サイクル内三角形を取り除き、
（３）一点化された切断点が異なるサイクル内三角形に所属しているのであれば、 その境界セル内にある全てのサイクル内三角形の対の１つ１つに対して、すべての対がなくなるまで併合操作を行う、ことを特徴とする境界データのセル内形状データへの変換方法。
【請求項２】
前記切断点の位置を、セル稜線を２ｎ（ｎは２以上の整数）で等分した位置に離散化する、ことを特徴とする請求項１に記載の境界データのセル内形状データへの変換方法。
【請求項３】
前記切断点計算ステップの前に、前記コンピュータの境界データ分割手段により、対象物の前記境界データを隣接する辺を共有する境界三角形に分割する境界データ分割ステップを有する、ことを特徴とする請求項１に記載の境界データのセル内形状データへの変換方法。
【請求項４】
前記サイクル形成ステップにおいて、前記サイクル形成手段は、各境界セル毎に、
（１）セル稜線を抽出し、
（２）境界データを構成する前記境界三角形の辺とセル面の面上交点を計算し、
（３）境界三角形の面とセル稜線の稜上交点を計算し、
（４）同一セル面上かつ同一境界三角形上の前記面上交点と稜上交点を近接する順で結んで連続する切断線分を求め、
（５）同一セル面上の前記面上交点を削除して前記連続する切断線分の両端に位置する稜上交点を結ぶ単一の切断線分を求め、
（６）前記セル面上の各切断線分を稜上交点を介して順次連結し、閉じた切断線分サイクルを形成する、ことを特徴とする請求項３に記載の境界データのセル内形状データへの変換方法。
【請求項５】
外部データ入力手段により対象物の境界データをコンピュータに入力し、コンピュータを用いて前記境界データを境界平面が直交する直方体セルが隙間なく集合したセル複合体内のセル内形状データに変換する変換プログラムであって、
コンピュータを、
前記境界データを内包するセル複合体を定義し、境界データがセル複合体を構成する直方体セルの稜線又は頂点を切断する切断点を計算する切断点計算手段と、
前記各直方体セルを、前記切断点のある境界セルと切断点のない非境界セルとに区分し、各境界セル毎に、セル表面と境界データとの切断線分を求め、前記切断点と切断線分を交互に順に結んで閉じた切断線分サイクルを形成するサイクル形成手段と、
各境界セル毎に、前記切断線分サイクルの内側を隣接する辺を共有するサイクル内三角形に分割するサイクル内分割手段と、
各境界セル毎に、各稜線における複数の切断点の１点化とサイクル内三角形のセルへの登録を行う簡略化手段として動作させ、
前記簡略化手段は、各境界セル毎に、
（１）同一のセル稜線上に複数の切断点があれば、原点により近い単一の切断点に一点化し、
（２）一点化された切断点が同じサイクル内三角形内にあれば当該サイクル内三角形を取り除き、
（３）一点化された切断点が異なるサイクル内三角形に所属しているのであれば、 その境界セル内にある全てのサイクル内三角形の対の１つ１つに対して、すべての対がなくなるまで併合操作を行う、ことを特徴とする境界データのセル内形状データへの変換プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、形状と物性を統合したボリュームデータを小さい記憶容量で記憶し、ＣＡＤとシミュレーションを一元化することできるボリュームデータ生成方法に係り、更に詳しくは、コンピュータに入力された対象物の境界データを前記境界データを境界平面が直交する直方体セルが隙間なく集合したセル複合体内のセル内形状データに変換する方法とそのプログラムに関する。
【背景技術】
【０００２】
本発明の発明者等は、「形状と物性を統合した実体データの記憶方法」を創案し出願した（特許文献１）。
【０００３】
この発明は、図８に模式的に示すように、対象物の境界データからなる外部データを八分木分割により境界平面が直交する直方体のセルに分割し、分割された各セルを対象物の内側および外側に位置する非境界セル１３ａと境界面を含む境界セル１３ｂとに区分するものである。なおこの図で１５は切断点である。
【０００４】
この発明により、各セル毎に種々の物性値を記憶することにより、形状と物性を統合した実体データを一元的に記憶することができ、これにより、物体の形状・構造・物性情報・履歴を一元的に管理し、設計から加工、組立、試験、評価など一連の工程に関わるデータを同じデータで管理することができ、ＣＡＤとシミュレーションを一元化することできる。
以下、本出願において、境界平面が直交する直方体セルを「ボリュームセル」、各セル毎に種々の物性値を記憶したものを「ボリュームデータ」、ボリュームデータを用いたシミューション手段を「ボリュームＣＡＤ」又は「ＶＣＡＤ」と呼ぶ。
【０００５】
さらに、本発明の発明者等は、境界表現データからボリュームデータを生成する手段ンとして、特許文献２〜４を提案している。
さらに本発明に関連する先行技術として、特許文献５、非特許文献１〜６が開示されている。
【０００６】
特許文献２の方法は、八分木分割ステップ、セル区分ステップ、切断点決定ステップ、及び境界面決定ステップからなり、特に、切断点の数に応じて別の境界セル種として区分し、各境界セル種毎に切断する稜線の組み合わせを予め設定し、求めた切断点の数と切断した稜線から、パターンマッチングにより境界セル種とその組み合わせを求めるものである。
【０００７】
特許文献３の方法は、分割ステップ、切断点決定ステップ、境界決定ステップ、セル区分ステップ、及び境界セルデータ区分ステップからなり、特に３次元では、切断点決定ステップにおいて、境界データとセルの稜との２１２＝４０９６通りの交点パターンをセル稜切断点として、更に回転操作と鏡映操作による同値類を同一パターンとして全１４４パターンに区分するものである。
【０００８】
特許文献４の方法は、外部データ入力手段により対象物の境界表現データをコンピュータに入力し、データ変換手段により境界表現データを位相付き三角形パッチに変換し、関連付け手段により空間を境界平面が直交する直方体セルに分割しかつどのセルにどの三角形が含まれているかの関連付けを行い、分割配置手段により空間上に浮かんだ位相付き三角形パッチをセル面で分割し、全ての三角形がセルの内部及び境界上に配置される状態とし、稜線統合手段により位相の変更を行わない稜線統合を行い、セル割振手段により頂点の索引データを参考に、各三角形とその頂点をセルに割り振り、ラベリング手段により各セルの属性値を設定するものである。
【０００９】
【特許文献１】特許第３４６８４６４号、「形状と物性を統合した実体データの記憶方法」
【特許文献２】国際公開ＷＯ０３／０４８９８０、「３次元形状データのセル内部データへの変換方法及び変換プログラム」
【特許文献３】国際公開ＷＯ０３／０７３３３５、「境界データのセル内形状への変換方法及び変換プログラム」
【特許文献４】特開２００５-３８２１９号、「境界表現データからボリュームデータを生成する方法及びそのプログラム」
【特許文献５】特開２００３−４４５２８号公報、「物体の表面格子生成方法」
【００１０】
【非特許文献１】Ｈ．  Ｈｏｐｐｅ，  "Ｐｒｏｇｒｅｓｓｉｖｅ  Ｍｅｓｈｅｓ"  Ｐｒｏｃ．  Ｓｉｇｇｒａｐｈ９６  ｐｐ９９-１０８，  Ａｕｇ  １９９６
【非特許文献２】Ｗ．Ｊ．Ｓｈｒｏｅｄｅｒ，  "Ａ  Ｔｏｐｏｌｏｇｙ  Ｍｏｄｉｆｙｉｎｇ  Ｐｒｏｇｒｅｓｓｉｖｅ  Ｄｅｃｉｍａｔｉｏｎ  Ａｌｇｏｒｉｔｍ"，  Ｐｒｏｃ．  Ｖｉｓｕａｌｌｉｚａｔｉｎ９７，  ｐｐ２０５-２１２，  Ｏｃｔ．  １９９７
【非特許文献３】Ｗ．Ｊ．Ｓｈｒｏｅｄｅｒ，  Ｊ．Ａ．  Ｚａｒｇｅ  ａｎｄ  Ｗ．Ｅ．  Ｌｏｒｅｎｓｅｎ，  "Ｄｅｃｉｍａｔｉｏｎ  ｏｆ  Ｔｒｉａｎｇｌｅ  Ｍｅｓｈｅｓ"，  Ｐｒｏｃ．  Ｓｉｇｇｒａｐｈ  ９２，  ｐｐ６５-７０，  Ｊｕｌｙ  １９９２
【非特許文献４】Ｋ．Ｊ．  Ｒｅｎｚｅ  ａｎｄ  Ｊ．Ｈ．  Ｏｌｉｖｅｒ，  "Ｇｅｎｅｒａｌｉｚｅｄ  Ｓｕｒｆａｃｅ  ａｎｄ  Ｖｏｌｕｍｅ  Ｄｅｃｉｍａｔｉｏｎ  ｆｏｒ  Ｕｎｓｔｒｕｃｔｕｒｅｄ  Ｔｅｓｓｅｌｌａｔｅｄ  Ｄｏｍａｉｎｓ"，  Ｐｒｏｃ．  ＶＲＡＩＳ９６，  ｐｐ１１１-１２１，  Ｍａｒ  １９９６
【非特許文献５】Ｋ．  Ｋａｓｅ，  ｅｔ．ａｌ，  “Ｖｏｌｕｍｅ  ＣＡＤ”，  Ｖｏｌｕｍｅ  Ｇｒａｐｈｉｃｓ  （２００３）
【非特許文献６】Ｐｉｅｇｌ  Ｌ，Ｒｉｃｈａｒｄ  Ｍ．Ｔｅｓｓｅｌｌａｔｉｎｇ  ｔｒｉｍｍｅｄ  ＮＵＲＢＳ  ｓｕｒｆａｃｅｓ，Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓ.  １９９５；  ２７（１）：１６−２６．
【発明の開示】
【発明が解決しようとする課題】
【００１１】
特許文献２、３で提案されている、セルとセルに適合化する三角形パッチによる形状表現とそのデータの生成方法は、以下の３ステップで行っている。
（ステップ１）ユーザにより定義されたセル空間と、入力形状としての三角形パッチの交点計算（セル切断点の計算）。
（ステップ２）各セル毎にセル切断点をセル面上で結んでできる閉ループを生成する。その際は、セル内のセル切断点の個数や隣接セルとの関係を元に、一意に定まるものから順に決定する。
（ステップ３）各セルで生成された閉ループ内を、入力形状との差異を元に三角形分割を行う。
【００１２】
しかし、この方法には以下の問題点があった。
（１）ボリュームセルのセルサイズと同程度の複雑さを持つ形状に対し、（ステップ２）の処理が終了しないケースがある。
（２）セルサイズより細かい形状から、徐々に大きな形状に変化する途中で、非多様体形状が発生するため、（ステップ２）の処理に失敗するケースがある。
（３）セルを階層化することを考慮した場合、（ステップ２）の処理において隣接関係の検索が著しく困難である。
【００１３】
これらの問題点を解決する手段として、特許文献４は、入力形状の三角形パッチの位相情報をそのまま使用し、かつ必要に応じて形状の簡略化を行う手段であり、以下のステップを有する。
（ステップ１）元の曲面パッチ（境界表現データ）を位相付き三角形パッチに変換する。
（ステップ２）位相付き三角形パッチをセル面（境界平面が直交する直方体セル）に分割する。
（ステップ３）位相付き三角形パッチの頂点のうち、セル稜線上にあるもの以外を他の頂点に統合する。
（ステップ４）ステップ３の条件や、直方体セルの一稜につき一切断点のみというボリュームデータの基本条件に反する部位の、近似処理による適正化をする。
【００１４】
この手段により、入力とする幾何形状に応じて頑強な計算が実現できる。
しかし、その反面、この手段は、複雑な形状を表現する上での計算負荷が高く、１台のＰＣで大規模データを扱うには限界があった。そのため、より計算負荷の軽い処理手段が要望されていた。
【００１５】
なお、三角形パッチをセルのサイズと同程度に分割して、セルで管理する方法も［特許文献５］に提案されているが、この方法においては、三角形パッチはセルに適合しておらず、セル対三角形パッチが一対一で管理できない方法であり、ＶＣＡＤの目的である、ものつくりにおける上流から下流工程までの一元化したデータ管理には適用し得ない。
【００１６】
また、三角形パッチ単独での処理については、三角形パッチの細分化／統合を行うことにより、形状表現の詳細化／簡略化を行う方法は既にＨｏｐｐｅ等によって提案されており［非特許文献１］、細分化のパラメータや分割方法、ならびに統合時の判断基準により様々な派生システムが存在している。但し、これらの方法では、元の形状の二多様体条件および位相条件をそのまま継承する変換方法となっており、微小な形状を意図的に簡略化したり、分岐や縁のある面などの非多様体表現にする操作には不向きである。［非特許文献２，３，４］
【００１７】
本発明は、上述した問題点を解決するために創案されたものである。すなわち、本発明の目的は、コンピュータを用いて、対象物の境界データを境界平面が直交する直方体セルが隙間なく集合したセル複合体内のセル内形状データに、頑強かつ確実に変換することができ、かつ大規模データを扱う必要がなく計算負荷を軽減できる方法とその変換プログラムを提供することにある。
【課題を解決するための手段】
【００１８】
本発明によれば、外部データ入力手段により対象物の境界データをコンピュータに入力し、コンピュータを用いて前記境界データを境界平面が直交する直方体セルが隙間なく集合したセル複合体内のセル内形状データに変換する方法であって、
前記コンピュータの切断点計算手段により、前記境界データを内包するセル複合体を定義し、境界データがセル複合体を構成する直方体セルの稜線又は頂点を切断する切断点を計算する切断点計算ステップと、
前記コンピュータのサイクル形成手段により、前記各直方体セルを、前記切断点のある境界セルと切断点のない非境界セルとに区分し、各境界セル毎に、セル表面と境界データとの切断線分を求め、前記切断点と切断線分を交互に順に結んで閉じた切断線分サイクルを形成するサイクル形成ステップと、
前記コンピュータのサイクル内分割手段により、各境界セル毎に、前記切断線分サイクルの内側を隣接する辺を共有するサイクル内三角形に分割するサイクル内分割ステップと、
前記コンピュータの簡略化手段により、各境界セル毎に、各稜線における複数の切断点の１点化とサイクル内三角形のセルへの登録を行う簡略化ステップとを有し、
前記簡略化ステップにおいて、前記簡略化手段は、各境界セル毎に、
（１）同一のセル稜線上に複数の切断点があれば、原点により近い単一の切断点に一点化し、
（２）一点化された切断点が同じサイクル内三角形内にあれば当該サイクル内三角形を取り除き、
（３）一点化された切断点が異なるサイクル内三角形に所属しているのであれば、 その境界セル内にある全てのサイクル内三角形の対の１つ１つに対して、すべての対がなくなるまで併合操作を行う、ことを特徴とする境界データのセル内形状データへの変換方法が提供される。
【００１９】
本発明の好ましい実施形態によれば、前記切断点の位置を、セル稜線を２ｎ（ｎは２以上の整数）で等分した位置に離散化する。
【００２０】
また、前記切断点計算ステップの前に、対象物の前記境界データを隣接する辺を共有する境界三角形に分割する境界データ分割ステップを有する。
【００２１】
また、前記サイクル形成ステップにおいて、各境界セル毎に、
（１）セル稜線を抽出し、
（２）境界データを構成する前記境界三角形の辺とセル面の面上交点を計算し、
（３）境界三角形の面とセル稜線の稜上交点を計算し、
（４）同一セル面上かつ同一境界三角形上の前記面上交点と稜上交点を近接する順で結んで連続する切断線分を求め、
（５）同一セル面上の前記面上交点を削除して前記連続する切断線分の両端に位置する稜上交点を結ぶ単一の切断線分を求め、
（６）前記セル面上の各切断線分を稜上交点を介して順次連結し、閉じた切断線分サイクルを形成する。
【００２３】
また本発明によれば、外部データ入力手段により対象物の境界データをコンピュータに入力し、コンピュータを用いて前記境界データを境界平面が直交する直方体セルが隙間なく集合したセル複合体内のセル内形状データに変換する変換プログラムであって、
コンピュータを、
前記境界データを内包するセル複合体を定義し、境界データがセル複合体を構成する直方体セルの稜線又は頂点を切断する切断点を計算する切断点計算手段と、
前記各直方体セルを、前記切断点のある境界セルと切断点のない非境界セルとに区分し、各境界セル毎に、セル表面と境界データとの切断線分を求め、前記切断点と切断線分を交互に順に結んで閉じた切断線分サイクルを形成するサイクル形成手段と、
各境界セル毎に、前記切断線分サイクルの内側を隣接する辺を共有するサイクル内三角形に分割するサイクル内分割手段と、
各境界セル毎に、各稜線における複数の切断点の１点化とサイクル内三角形のセルへの登録を行う簡略化手段として動作させ、
前記簡略化手段は、各境界セル毎に、
（１）同一のセル稜線上に複数の切断点があれば、原点により近い単一の切断点に一点化し、
（２）一点化された切断点が同じサイクル内三角形内にあれば当該サイクル内三角形を取り除き、
（３）一点化された切断点が異なるサイクル内三角形に所属しているのであれば、 その境界セル内にある全てのサイクル内三角形の対の１つ１つに対して、すべての対がなくなるまで併合操作を行う、ことを特徴とする境界データのセル内形状データへの変換プログラムが提供される。
【発明の効果】
【００２４】
上記本発明の方法およびプログラムによれば、切断点計算ステップにおいて、境界データが直方体セルの稜線又は頂点を切断する切断点を計算するので、頑強かつ確実に、すべての切断点を求めることができる。
また、サイクル形成ステップにおいて、セル表面と境界データとの切断線分を求め、前記切断点と切断線分を交互に順に結んで閉じた切断線分サイクルを形成するので、頑強かつ確実に、切断線分サイクルが形成できる。
さらに、サイクル内分割ステップにおいて、前記切断線分サイクルの内側を隣接する辺を共有するサイクル内三角形に分割するので、頑強かつ確実に、サイクル内三角形が形成できる。
また、簡略化ステップにおいて、各稜線における複数の切断点の１点化とサイクル内三角形のセルへの登録を行うので、全体のデータを低減し、計算負荷を軽減できる。
更に、前記サイクル形成ステップ、サイクル内分割ステップ及び簡略化ステップを、境界セル毎に実行するので、大規模データを扱う必要がなく計算負荷を軽減できる。
【発明を実施するための最良の形態】
【００２５】
以下、本発明の好ましい実施形態を図面を参照して説明する。
【００２６】
１．装置構成
図１は、本発明の方法を実行するための装置構成図である。この図に示すように、この装置は、外部データ入力手段２、外部記憶装置３、内部記憶装置４、中央処理装置５および出力装置６を備える。
【００２７】
外部データ入力手段２は、例えばキーボードであり、対象物の境界表現データからなる外部データを入力する。外部記憶装置３は、ハードディスク、フロピィーディスク、磁気テープ、コンパクトディスク等であり、対象物の境界データ、セル内形状データ、及びその変換プログラムを記憶する。内部記憶装置４は、例えばＲＡＭ，ＲＯＭ等であり、演算情報を保管する。中央処理装置５（ＣＰＵ）は、演算や入出力等を集中的に処理し、内部記憶装置４と共に、プログラムを実行する。出力装置６は、例えば表示装置とプリンタであり、記憶したセル内形状データとプログラムの実行結果を出力するようになっている。  
中央処理装置５、内部記憶装置４及び外部記憶装置３は、共同して、後述する境界データ分割手段、切断点計算手段、サイクル形成手段、サイクル内分割手段、および簡略化手段として機能する。
【００２８】
外部から入力する外部データは、多面体を表すポリゴンデータ、有限要素法に用いる四面体又は六面体要素、３次元ＣＡＤ又はＣＧツールに用いる曲面データ、或いはその他の立体の表面を部分的な平面や曲面で構成された情報で表現するデータである。
【００２９】
外部データは、このようなデータ（Ｓ−ＣＡＤデータと呼ぶ）のほかに、（１）Ｖ−ＣＡＤ独自のインターフェース（Ｖ−ｉｎｔｅｒｆａｃｅ）により人間の入力により直接作成されたデータと、（２）測定機やセンサ、デジタイザなどの表面のデジタイズデータや、（３）ＣＴスキャンやＭＲＩ、および一般的にＶｏｌｕｍｅレンダリングに用いられているボクセルデータなどの内部情報ももつＶｏｌｕｍｅデータであってもよい。
【００３０】
２．本発明の方法
図２は、本発明の方法を示すフロー図である。本発明の方法は、外部データ入力手段により対象物の境界データをコンピュータに入力し、コンピュータを用いて前記境界データを境界平面が直交する直方体セルが隙間なく集合したセル複合体内のセル内形状データに変換する方法である。
【００３１】
図２において、本発明の方法は、外部データ入力ステップＳ１、境界データ分割ステップＳ２、切断点計算ステップＳ３、サイクル形成ステップＳ４、サイクル内分割ステップＳ５、簡略化ステップＳ６の各ステップを有する。
【００３２】
外部データ入力ステップＳ１では、外部データ入力手段により対象物の境界データをコンピュータに入力する。
【００３３】
境界データ分割ステップＳ２では、対象物の境界データを隣接する辺を共有する境界三角形に分割する。このステップは必須ではないが、三角形パッチを用いることにより、データ量を低減しかつ各ステップにおける計算負荷を軽減することができる。
【００３４】
切断点計算ステップＳ３では、ステップＳ３１で境界データを内包するセル複合体を定義し、ステップＳ３２で境界データがセル複合体を構成する直方体セルの稜線又は頂点を切断する切断点を計算する。
この切断点の位置は、データの頑強性を高めるためにセル稜線を２ｎ（ｎは２以上の整数）で等分した位置に離散化するのがよい。
【００３５】
サイクル形成ステップＳ４では、ステップＳ４１で各直方体セルを切断点のある境界セルと切断点のない非境界セルとに区分し、各境界セル毎（ステップＳ４２）に、ステップＳ４３でセル表面と境界データとの切断線分を求め、ステップＳ４４で切断点と切断線分を交互に順に結んで閉じた切断線分サイクルを形成する。
【００３６】
図３は、サイクル形成ステップＳ４とサイクル内分割ステップＳ５の説明図である。図３（Ａ）において、細線で示す直方体セルは境界セル１３ｂであり、○を細線で結ぶ面は、境界データを構成する境界三角形７を示している。
サイクル形成ステップＳ４において、各境界セル毎に、以下の（１）〜（６）のステップを順に行う。
（１）まず、境界セル１３ｂのセル稜線を抽出する。セル稜線は、単一階層の場合は、１２本の辺を抽出するだけで済む。隣接セルとの間に階層差のある「つなぎセル」の場合、そのセルと隣接セルの稜線のうち、そのセルの面上及び稜上にあるもの全てを抽出し、重複関係にある稜線について、短いもののみを残す。
（２）次に、図３（Ｂ）に示すように、境界データを構成する境界三角形７の辺とセル面の面上交点８（●）を計算する。
（３）次に、図３（Ｂ）に示すように、境界三角形７の面とセル稜線の稜上交点９（●）を計算する。
（４）次に、図３（Ｃ）に示すように、同一セル面上かつ同一境界三角形上の面上交点８と稜上交点９を近接する順で結んで連続する切断線分１０を求める。
（５）次に、図３（Ｄ）に示すように、同一セル面上の面上交点８を削除して連続する切断線分１０の両端に位置する稜上交点９を結ぶ単一の切断線分１１を求める。
（６）次に、図３（Ｅ）に示すように、セル面上の各切断線分１１を稜上交点９を介して順次連結し、閉じた切断線分サイクル１２を形成する。
【００３７】
サイクル内分割ステップＳ５では、図３（Ｆ）に示すように、各境界セル毎に、切断線分サイクルの内側を隣接する辺を共有するサイクル内三角形１２ａに分割する。
【００３８】
簡略化ステップＳ６では、各境界セル毎に、各稜線における複数の切断点の１点化とサイクル内三角形のセルへの登録を行なう。
この簡略化ステップＳ６において、各境界セル毎に、
（１）同一のセル稜線上に複数の切断点があれば、原点により近い単一の切断点に一点化し、
（２）一点化された切断点が同じサイクル内三角形内にあればその切断三角形をつぶし、
（３）一点化された切断点が異なるサイクル内切断三角形に所属しているのであれば、  その境界セル内にある全てのサイクル内切断三角形の対の１つ１つに対して、すべての対がなくなるまで併合操作を行う。
【００３９】
また、本発明の変換プログラムは、上述したステップＳ１〜ステップＳ６を実行するためのコンピュータプログラムであり、コンピュータに実装して使用する。
以下、本発明を更に詳細に説明する。
【００４０】
３．ＣＷ複体（セル複合体）によるボリューム（３次元領域）と境界の表現
（３．１）ではＣＷ複体の定義と関連する用語の定義をおこなう。（３．２）でＣＷ複体に基づく新しい直方体セル（これを「ボリュームセル」又は「Ｋｉｔｔａ  Ｃｕｂｅ」と呼ぶ）のデータ構造を導入する。
【００４１】
３．１    胞体（セル）とＣＷ複体（セル複合体）
「ｎ‐胞体（セル）」は、代数的位相幾何学における数学用語であり、「０‐胞体」は頂点、「１-胞体」は両端を２つの「０‐胞体」によって仕切られた開線分、「２‐胞体」は３つ以上の「１‐胞体」のループが境界をなす開曲面であり、「３‐胞体」は「２‐胞体」からなる曲面に囲まれている３次元領域（これを「ボリューム」と呼ぶ）である。
【００４２】
「ｎ‐胞体」と胞体複体のより厳密な定義は次の通りである。
ＸはＨａｕｓｄｏｒｆｆ空間であり、開球（円盤）Ｂｎαの連続写像が各次元で数１の式（１）の条件を満たし、（その像、あるいは厳密には写像そのものが胞体、ｎ次元の時にはｎ‐胞体と呼ばれる）かつ各写像はｎ次元球の内部で１対１写像となっているときにのみ「胞体複体」と呼ばれる。
【００４３】
【数１】
0004783100.tif 000002
【００４４】
式（１）でｄｉｍ（ｅλ）は胞体ｅλの次元を表し、式（２）の関係がある。ここで、上部に‐のあるｅはｅの閉包である。
式（１）の（ｉ）は各胞体の和をとったものがＸとなっていること、（ｉｉ）は各胞体が区分的に非連結であることを意味し、（ｉｉｉ）はそれぞれのｎに対して、ｎ‐胞体の境界はその次元がｎより小さい胞体の和の中に存在することを意味している。
【００４５】
本発明において、ＣＷ複体（セル複合体）は式（１）を満たし、さらに次のＣ条件とＷ条件を満たす胞体複体をさす。
Ｃは閉包有限（Ｃｌｏｓｕｒｅ  ｆｉｎｉｔｅ）の頭文字をとっており、任意の点が常に胞体複体の有限な部分集合の、どれか具体的な要素（例えば頂点、稜線、面、など）にあるという条件である。この条件は理論的にはこの胞体複体のどの領域でどのような積分をしても発散しないことを保証しており、数値解析において無限に精度を上げられることを示している。
一方、Ｗは弱位相（Ｗｅａｋ  ｔｏｐｏｌｏｇｙ）の頭文字をとっており、対象あるいはその周囲の環境が開集合であるか閉集合であるかというような大域的な位相的な特徴を、局所的な胞体複体との交わりで決定できるという条件である。この条件は胞体複体の各要素が全体のシステムを構成するモジュールであり、様々な分散・並列手法において有効であることを保証している。
両方の条件は大量データや現実的な工学における解析を扱いためのグリッド計算などの将来的な拡張に必要な条件である。
【００４６】
ＣＷ複体（セル複合体）は、言い換えると、頂点や稜線や面などの位相要素のもれなく重複のない組み合わせ構造と言える。これらは曲面や境界によって仕切られている複数の３次元領域（ボリューム）を自然に表現することができる。このことは多媒質を扱う上で格好の長所であり、セルラベリングには必須である。ＣＷ複体の例としては、ボクセルやＦＥＭ（有限要素法）のメッシュなどが挙げられる。
【００４７】
３．２    Ｋｉｔｔａ  Ｃｕｂｅ（ボリュームセル）
Ｋｉｔｔａ  Ｃｕｂｅは近似三角形（切断三角形と呼ぶ）を持つ直方体（セル）である。切断三角形の各頂点は直方体セルの稜線上にあり、その数は各稜線で多くとも１つである。切断三角形の各辺は切断線分と呼ぶ。
【００４８】
本発明において、Ｋｉｔｔａ  Ｃｕｂｅ（ボリュームセル）の集合がＶＣＡＤの中心的なデータ構造であり、以下の実際に使うことを考慮した条件（１）〜（４）を加えてＣＷ複体の現実的な実装となっている。
【００４９】
（１）「統一性条件」：ＶＣＡＤの３次元対象（ワールド）はＬ×Ｍ×Ｎ個のボクセルの集合として定義される。このボクセルの個数はユーザによって指定され、最終的な解像度が自動的に決定される。この個数決めにはモデルに合わせて注意と経験が必要であり。各ボクセルはベースボクセルと呼ばれる。
（２）「多重解像度条件」：八分木分割による階層化が各ベースボクセルに導入され、各オクタント（３‐胞体＝３次元領域）は階層の異なる隣接するオクタントと細分された面（２‐胞体＝開曲面）を共有する（図５参照、なおこの配置はユークリッド胞体複体では許されないがＣＷ複体としては問題ない）。
（３）「表現力条件」：通常の八分木分割による８細分に加えて末端のオクタントはさらに幾つかの新たに追加された面（これも２‐胞体）によって細分され、「１稜線または頂点に１切断点」のルール（「１稜１切断ルール」と呼ぶ）が適用される。ただしその分解能でもとの境界面を十分に近似できるように、その稜線または頂点上の自由な位置に切断点は置かれる。
【００５０】
図４は、Ｋｉｔｔａ  Ｃｕｂｅの例を示す図である。この図において、左上の図は、ツバメックス社から入手したＩＧＥＳから６４×２５６×６４のベースボクセルのＶＣＡＤに変換した板金プレスの金型であり、固体部分のセルのみ表示している。その他の図はＫｉｔｔａ  Ｃｕｂｅ独特の、Ｍａｒｃｈｉｎｇ  Ｃｕｂｅでは現れない配置を表している。点が切断点。面が切断三角形からなる仕切り面。右下の図では切断点は配置を見やすくするために稜線の中点に移動してある。
【００５１】
図４に示されるように、新たに追加された面（「仕切り面」と呼ぶ。１つの直方体セル内で連結した切断三角形がその定義である。）を表現するために、切断点は末端のオクタントにおいて、その稜線（１‐胞体）かその稜線の２つの境界である頂点（０‐胞体）における再分割点（０‐胞体）とみなすことができる。この結果、仕切り面や直方体セルを構成する面内で再分割されて出来た面を含む全ての面（２-胞体）は非多様体的（２-多様体ではない）面に分類される。すなわち、すべての稜線（１‐胞体）は２つ以上の面（２‐胞体）と隣接している（分岐）。
（４）「頑健性条件」：全ての切断点位置は、数値誤差の累積や丸め誤差による位相的および幾何的な隙間を避けるために、ベースボクセルの稜線を２ｎで等分された位置に離散化される。各仕切り面は切断点を用いて三角形分割（単体細分）される。このためＫｉｔｔａＣｕｂｅの三角形の方向も離散化される。
【００５２】
「統一性条件」は、あらゆる計算課程における大域的な位置決定を簡単にするために導入された。末端のオクタントや八分木をもたないベースボクセルはＫｉｔｔａ  Ｃｕｂｅである。
【００５３】
図５は１つのベースボクセルから開始した２次元の場合のＫｉｔｔａ  Ｃｕｂｅの例を示している。なお、この例では、対象（ワールド）は２次元（四分木、１つのベースボクセルＬ＝Ｍ＝１）である。
この図に示すように、Ｋｉｔｔａ  Ｃｕｂｅは切断点の有無で２種類に分けられる：切断点のあるＫｉｔｔａ  Ｃｕｂｅを「境界セル」、切断点のないＫｉｔｔａ  Ｃｕｂｅを「非境界セル」と名づける。
【００５４】
図６は、階層の異なるＫｉｔｔａ  Ｃｕｂｅの例を示している。この図で左上の図は「１稜１切断ルール」（１稜線または頂点に１切断点のみのルール）に従った結果、隙間が生じた場合を示している。この隙間を埋めるために、左下の図にあるように、大きいほうのセルに新たに「つなぎセル」を導入する。右の図は階層が２段階異なる場合を示しており、各点が切断点を表す。
【００５５】
「表現力条件」では、「１稜１切断ルール」が多重分解能条件の際の分割の目安として採用されている。しかしながら、このルールに厳密に従うと、図６の左上にあるように、双対法と同様、階層の異なるセル間の面や辺において隙間が生じる。これを解決するために、ＣＷ複体の定式化に添って、大きいほうのセルは隣接する小さいほうの幾つかのセルの面、稜線、頂点、切断点をすべて共有するようにする。図６の左下に示されている、この例外的なセルは「つなぎセル」と呼ばれる。つなぎセルのみが１稜線または頂点に１切断点ルールに従わない。階層差は必ずしも１階層である必要はなく、例えば図６の右に示されているように２以上の階層差でもかまわない。これらのつなぎセルには２つの目的がある（１）異なる階層間での隙間や穴をなくすため、と（２）階層差の影響の伝播を最小限におさえるため、である。
【００５６】
「頑健性条件」のために、Ｋｉｔｔａ  Ｃｕｂｅはベースボクセルから八分木的（多重分解能条件）にｍ回分割されると、各セルの稜線では２の（ｎ−ｍ）乗＋１個の切断点位置に減る。ここで、ｎ、ｍは１以上の整数であり、ｎ−ｍは１以上の整数である。これにより異なる階層差でも切断点位置がディジタルに厳密に一致するようにしている。
【００５７】
図４は階層のないベースボクセルのみからなるＫｉｔｔａ  Ｃｕｂｅを示している。図の左上はひとつのＫｉｔｔａ  Ｃｕｂｅを表しており、Ｍａｒｃｈｉｎｇ  Ｃｕｂｅが２の８乗の頂点ベースのデータ構造であることから、表現できないような切断点配置が、Ｋｉｔｔａ  Ｃｕｂｅではそれより多い２の１２乗の稜線ベースのデータ構造であることから、初めて表現できることを示している。
実際には、この２の１２乗の状態は１つのセルに１つの切断点しかないようなあまり意味のないような配置も含んでいるが、逆にどの配置が重要で実効性があるかを判定する問題は離散数学において、十分に難しくまた面白い問題となっている。これに対する１つの回答として、群論による冗長性をへらす研究は共同発明者である手嶋によって別途報告されている。
【００５８】
図４に示すＫｉｔｔａＣｕｂｅ独特の配置は、両端の頂点が同じ符号（面の側）または所属空間（材料）に属する稜線上の切断点を許さないＭａｒｃｈｉｎｇ  ｃｕｂｅやその他の頂点ベースの方法では決して表現することが出来ないものである。
また双対法でも同様な配置が本発明と同様に多媒質を表現する目的で表現可能だが、表現力は増すものの、双対法では許される１つのセル内に自由に配置できる頂点（自由点）の位置の数値的な精度の保証の艱難さにつながり、あらたに頑健性条件をみたすためのセル内での自由点位置の離散化が必要となる。
【００５９】
４．Ｋｉｔｔａ  Ｃｕｂｅ（ボリュームセル）による曲面の簡略化
符号付１-サイクル（１-輪体）は、順番がある巡回型の互いに隣り合う切断線分（１-胞体＝開線分）のリスト（列）として定義される。符号なし１-サイクルは、同じ曲面に際して互いに表裏の関係にある２つの逆向きの符号付１-サイクルの対として定義される（符号なし１-サイクルは符号付１-サイクルの商群である）。
この符号なし１-サイクル（１‐輪体）は（４．１）と（４．２）で述べるように、もとの曲面からＫｉｔｔａ  Ｃｕｂｅの代数的表現に置き換えることに用いられる。本発明において、符号なし１‐サイクルを単に「サイクル」と呼ぶ。
Ｋｉｔｔａ  Ｃｕｂｅは、直方体セル内の詳細を考慮しなくてよいことからさまざまな計算アルゴリズムを簡略する利点を有するとともに、離散的、代数的な表現による頑健性ももたらしてくれる。
【００６０】
ＣＷ複体（セル複合体）の定義から、この変換過程は球面Ｓ２（直方体セルの６つの面のモデル）とパラメトリック曲面Ｐ（ｕ，ｖ）との交線計算ととらえることができる。結果として求まる交線は符号なし１-サイクル（代数的情報、すなわち文字の列）として、断片的なデータ（どのセルのどの面とパラメトリック曲面の境界曲線やトリム曲線との交点、そのパラメータ値など）とともに保存される。
これら符号なし１-サイクル（サイクル）は２-胞体（セルによって切りとられたパラメトリック曲面Ｐ（ｕ，ｖ）の一部で円盤Ｄ２と同相）に相当し、その（１‐サイクルの）内部は、上記の断片的なデータ（交線計算結果として記録されたパラメータ値）によって実現される胞体写像によって埋められている。
つまり１-サイクルは金魚すくいの枠だけを表しているが、実際の計算にともない断片的データが紙の役目を果たしている。
この符号なし１-サイクルに置き換えて三角形分割してゆく過程で、微妙な曲率の変化やピン角、コーナー部などの局所的な幾何学的な詳細形状は線形近似され面取りされてゆく。この段階でまだ境界セルの各稜線において複数の符号なし１-サイクルが残っている場合は、Ｋｉｔｔａ  Ｃｕｂｅの「１稜１切断ルール」（１稜線または頂点に１切断点のみのルール）に則り併合される。
例えば、薄い（しかし厚みを持っている）構造は切り取られ、１枚の面、あるいは周囲の領域から見れば１枚の亀裂として簡略化される。この併合プロセスは（４．２）で詳説される。全体の変換アルゴリズムは（４．１）で示す。
【００６１】
４．１  アルゴリズム
このアルゴリズムは完全に各直方体セルで独立した（自律していて他との関連がない、すなわち並列に計算可能な）プロセスである。この簡略化アルゴリズムは［非特許文献５］を拡張したものである。
【００６２】
４．１．１  ＫｉｔｔａＣｕｂｅの変換アルゴリズム
各境界セルに対して、以下のステップ１からステップ４を実行する。
ステップ１：切断点計算（交点は切断点として量子化され指標（何番目）として（パラメータｕ，ｖなどの）断片的データとともに記録される。）
ステップ２：境界セルの表面と入力の曲面との交線の区分的線形補間（符号なし１-サイクルと断片的データの記録）
ステップ３：符号なし１‐サイクルの三角形分割（単体分割による切断三角形が生成され記録）
ステップ４：セルの各稜線における複数の切断点の１点化と切断三角形のセルへの登録（簡略化）
【００６３】
ステップ１で、切断点は境界セルの１２本の稜線と入力となる元曲面との交点が計算され、さらに３．２説で説明した「頑健性条件」に従ってその位置が離散化（２ｍに等分した位置に量子化）される。［非特許文献５］の方法に対して、新たに境界セルの８頂点が切断点位置として導入された。
この拡張により、可能な符号なし１-サイクルの数は組み合わせ的に増え、ステップ２において元曲面とセルの各面との交線である切り取られた曲線が計算され直線補間される。これは実際には、上述の断片的データを用いて、切断点間でそれを結ぶ交線があるかをｕ-ｖ平面でチェックし、実際に連結しているもののみを結ぶことにより、切断線分として計算される。
【００６４】
ステップ３の結果求められた三角形が切断三角形となる。Ｐｉｅｇｌ(非特許文献６)のトリムされた曲面であるＮＵＲＢＳの三角形分割を１つの符号なし１-サイクル内で適用することにより実現される。
ステップ４での簡略化手法は次の（４．２）で述べる。
このアルゴリズムの実行後、符号なし１-サイクルとして認識されない孤立した切断点やひげのようにぶら下がっている切断線分はそのまま残る。これらを自動的に検索して削除することは境界セルの周辺のみの局所的な処理によって簡単に効率的にできる。
【００６５】
４．２  切断点の１点化と切断三角形の登録
（４．１）のステップ４において、複数の切断三角形は同一のセル稜線上にある複数の切断点の１点化により併合されるかつぶされるかされる。
この曲面の簡略化では以下の切断三角形に対する２つの操作で十分である。
「つぶし操作」：切断点およびそれにつながっている切断線分、それを含む切断三角形が１点化により取り除かれる。
「併合処理」：２つの切断三角形が（１点化によって）１つの切断線分を共有しながら連結した仕切り面となる。この操作は時々分岐した仕切り面を生じることがある、すなわち非多様体曲面である。
【００６６】
ステップ４の簡略化アルゴリズムは以下のようになる。
ある境界セルの各稜線に対して以下の（１）〜（３）を行う。
（１）もしその稜線上に複数の切断点があれば、それらを原点に近いほうの切断点に統一（一点化）する。
（２）もし、一点化された切断点が同じ切断三角形内にあればつぶし操作をおこなう（その切断三角形をつぶす）。
（３）もし、そうでないなら（一点化された切断点が違う切断三角形に所属しているのであれば）以下を実行する。
全ての（その境界セル内にある）切断三角形の対の１つ１つに対して、すべての対がなくなるまで併合操作をおこなう。
【００６７】
図７は４．１）のＫｉｔｔａＣｕｂｅの変換アルゴリズムの全ステップを示している。
この図は、Ｋｉｔｔａ  Ｃｕｂｅ変換を示しおり、左上は、入力の曲面（サイクライド）、右上は切断点計算と符号なし１-サイクルへの線形近似、および切断三角形への分割である（ステップ１からステップ３）。
また左下は、ステップ４で切断三角形がつぶされる（円と矢印）。右下は、最終的に変換された非多様体的な（円でしめす点における面の分岐）Ｋｉｔｔａ  Ｃｕｂｅである。
【００６８】
この例では、つぶし操作のみが実行されている。図７の左上は入力のＮＵＲＢＳ曲面（サイクライド）である。同図の右上は１つの境界セルにおいてステップ１からステップ３が実行された結果を示している。ステップ１によって１つのセル稜線上に２つの切断点が算出され（図７で円で囲まれている部分）ている。１つの符号付１-サイクルがステップ２で該当する切断点を結んでゆくことにより区分線形補間され、ステップ３によって三角形分割されている。これら２つの切断点とそれらを含む切断三角形は図７の左下に示すように、ステップ４でのつぶし操作によってつぶされている。同図の右下は最終的に生成された点における分岐（円）がある非多様体的なＫｉｔｔａ  Ｃｕｂｅを示している。
【００６９】
上記本発明の方法およびプログラムによれば、切断点計算ステップにおいて、境界データが直方体セルの稜線又は頂点を切断する切断点を計算するので、頑強かつ確実に、すべての切断点を求めることができる。
また、サイクル形成ステップにおいて、セル表面と境界データとの切断線分を求め、前記切断点と切断線分を交互に順に結んで閉じた切断線分サイクルを形成するので、頑強かつ確実に、切断線分サイクルが形成できる。
さらに、サイクル内分割ステップにおいて、前記切断線分サイクルの内側を隣接する辺を共有するサイクル内三角形に分割するので、頑強かつ確実に、サイクル内三角形が形成できる。
また、簡略化ステップにおいて、各稜線における複数の切断点の１点化とサイクル内三角形のセルへの登録を行うので、全体のデータを低減し、計算負荷を軽減できる。
更に、前記サイクル形成ステップ、サイクル内分割ステップ及び簡略化ステップを、境界セル毎に実行するので、大規模データを扱う必要がなく計算負荷を軽減できる。
【図面の簡単な説明】
【００７０】
【図１】本発明の方法を実行するための装置構成図である。
【図２】本発明の方法を示すフロー図である。
【図３】サイクル形成とサイクル内分割の説明図である。
【図４】Ｋｉｔｔａ  Ｃｕｂｅの例を示す図である。
【図５】１つのベースボクセルから開始した２次元の場合のＫｉｔｔａ  Ｃｕｂｅの例を示している。
【図６】階層の異なるＫｉｔｔａ  Ｃｕｂｅの例を示している。
【図７】ＫｉｔｔａＣｕｂｅの変換アルゴリズムの全ステップを示している。
【図８】［特許文献１］の「形状と物性を統合した実体データの記憶方法」の模式図である。
【符号の説明】
【００７１】
２  外部データ入力手段、３  外部記憶装置、
４  内部記憶装置、５  中央処理装置、６  出力装置、
７  境界三角形、８  面上交点、９  稜上交点、
１０  連続する切断線分、１１  単一の切断線分、
１２  切断線分サイクル、１２ａ  サイクル内三角形、
１３ａ  非境界セル、１３ｂ  境界セル、１５  切断点
【図１】
0004783100.tif 000003
【図２】
0004783100.tif 000004
【図３】
0004783100.tif 000005
【図４】
0004783100.tif 000006
【図５】
0004783100.tif 000007
【図６】
0004783100.tif 000008
【図７】
0004783100.tif 000009
【図８】
0004783100.tif 000010