JP4381743B2 - 境界表現データからボリュームデータを生成する方法及びそのプログラム - Google Patents

Description

本発明は、形状と物性を統合したボリュームデータを小さい記憶容量で記憶し、ＣＡＤとシミュレーションを一元化することできるボリュームデータ生成方法に係り、更に詳しくは、入力の表面形状として多用される三角形パッチを指定されたサイズのセルに適合させる方法とそのプログラムに関する。

先端的な研究開発・技術開発の現場では、その高度化・複雑化に伴い、膨大な試行錯誤が不可欠となっており、開発途中でのリスクが高まっている。科学技術立国を目指す我が国として、これらのリスクを極力排し、開発過程の革新的な高度化・効率化を図ることが極めて重要である。

現在、研究開発・技術開発の現場において、ＣＡＤ（Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｄｅｓｉｇｎ）、ＣＡＭ（Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇ）、ＣＡＥ（Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｅｎｇｉｎｅｅｒｉｎｇ）、ＣＡＴ（Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｔｅｓｔｉｎｇ）などが、それぞれ設計、加工、解析、試験のシミュレーション手段として用いられている。
また、本発明によって、連続的なシミュレーションであるＣ−Ｓｉｍｕｌａｔｉｏｎ（Ｃｏｏｒｐｏｒａｔｉｖｅ Ｓｉｍｕｌａｔｉｏｎ）、加工プロセスも考慮したＡ−ＣＡＭ（Ａｄｖａｎｃｅｄ ＣＡＭ）、究極の精度が出せるＤ−ｆａｂｒｉｃａｔｉｏｎ（Ｄｅｔｅｒｍｉｎｉｓｔｉｃ ｆａｂｒｉｃａｔｉｏｎ）なども、これから広く普及するはずである。

上述した従来のシミュレーション手段では、対象物を、ＣＳＧ（Ｃｏｎｓｔｒｕｃｔｉｖｅ Ｓｏｌｉｄ Ｇｅｏｍｅｔｒｙ）やＢ−ｒｅｐ（Ｂｏｕｎｄａｒｙ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ）でデータを記憶している。

しかし、ＣＳＧでは、対象物全体を微細なソリッドモデルの集合体として記憶するため、データが重くシミュレーション手段（ソフトウェア等）を実装する場合、膨大なデータを扱うこととなり、大型コンピュータを用いた場合でも解析に時間がかかる問題点があった。

また、Ｂ−ｒｅｐでは、対象物を境界で表現するため、データは軽く、データ量は小さくなるが、境界面の内部に関する情報が直接的にはないため、そのままでは変形解析等には適さない問題点があった。

更に、これらの従来のデータ記憶手段では、熱・流体解析、固体の大変形解析、これらの連成解析等でその都度、解析に適したメッシュ等に分割して、有限要素法等を適用するため、その解析結果を表示等はできるが、ＣＡＤとシミュレーションを一元化することが困難であり、設計・解析・加工・組立・試験等の各工程を同じデータで管理することができない問題点があった。

言い換えれば、現状のＳｏｌｉｄ／Ｓｕｒｆａｃｅ-ＣＡＤ（以下Ｓ-ＣＡＤと呼ぶ）には、以下の問題点があった。
（１）デ-タが渡らない、内部での変換操作に弱い（数値誤差と処理方法の問題）。
（２）シミュレーションに直接使えない（内部情報をもっていないのでメッシュを生成しなくてはいけない）。
（３）ＣＡＭによる加工の検討ができない（最終形状しかもっていない）。

また加工においても以下の問題点があった。
（１）加工プロセスの表現ができない（荒加工や工程設計の支援が不十分）。
（２）レーザー加工や超先端加工など新しい加工法に対応できていない（切削しかない、数値精度が足りない）。
（３）加工法自体の選択ができない（複合体で内部に異なる材料特性を有する）。

上述した問題点を解決するために、本発明の発明者等は、「形状と物性を統合した実体データの記憶方法」を創案し出願した［特許文献１］。

この発明は、図１に模式的に示すように、対象物の境界データからなる外部データを八分木分割により境界平面が直交する立方体のセルに分割し、分割された各セルを対象物の内側に位置する内部セル１３ａと境界面を含む境界セル１３ｂとに区分するものである。なおこの図で１５は切断点である。

この発明により、各セル毎に種々の物性値を記憶することにより、形状と物性を統合した実体データを小さい記憶容量で記憶することができ、これにより、物体の形状・構造・物性情報・履歴を一元的に管理し、設計から加工、組立、試験、評価など一連の工程に関わるデータを同じデータで管理することができ、ＣＡＤとシミュレーションを一元化することできる。

さらに、本発明の発明者等は、「３次元形状データのセル内部データへの変換方法及び変換プログラム」を創案し出願した［特許文献２］。

この発明により、ボリュームＣＡＤにおいて、隣接するセルとの連続性を保ち、隙間や精度的に望ましくない三角形を形成することなく、曲率の大きい曲面にも精度よく近似した表面を三角形メッシュに分割することができるセル内部データを外部データから形成することができる。

特開２００２−２３００５４号、「形状と物性を統合した実体データの記憶方法」 特願２００１-３７００４０号、「３次元形状データのセル内部データへの変換方法及び変換プログラム」、未公開 特開２００３-４４５２８号公報、「物体の表面格子生成方法」 特願２００３-１３１３１３号、「多媒質データの識別方法とそのプログラム」、未公開

K.Kase, Y.Teshima, S.Usami, H.Ohmori, C.Teodosiu, and A.Makinouchi "Volume CAD" International Workshop on Volume Graphics (VG 03) ,2003, Tokyo. Japan.(to appear). Y.Teshima, S.Usami, and K. Kase"Shape Approximation, Cube Cutting and Enumeration", The Institute of Statistical Mathematics, Tokyo, Japan,Abstract pp9. Y.Teshima, S.Usami, and K.Kase, "Enumeration on Cube Cutting", Japan Conference on Discrete and Computational Geometry , 2002, Tokyo, Japan. pp. 87-88, C.M. Hoffmann, "The Problems of accuracy and robustness in geometric computation.", Computer, 22(3):pp31-41, 1989 T.Ju, F.Losasso, S.Shaefer, J.Warren, "Dual Contouring of Hermite Data", Siggraph2002, Italy, proc. pp339-346 W.J.Shroeder, "A Topology Modifying Progressive Decimation Algoritm", Proc. Visuallizatin97, pp205-212, Oct. 1997 W.J.Shroeder, J.A. Zarge and W.E. Lorensen, "Decimation of Triangle Meshes", Proc. Siggraph 92, pp65-70, July 1992 K.J. Renze and J.H. Oliver, "Generalized Surface and Volume Decimation for Unstructured Tessellated Domains", Proc. VRAIS96, pp111-121, Mar 1996 B.Hamman, "A Data Reduction Scheme for Triangulated Surfaces," CAGD, 11(2) I. Navazo, "Extended Octtree Representation of General Solids with Plane Faces : Model Structure and Algorithms", Computer and Graphics Vol.13, No. 1, pp5-16, 1989 H. Hoppe, T. DeRose, T.Duchamp, J.McDonald, and W.Stuetzle, "Mesh Optimization", Proc. Siggraph93, pp.19-26, Aug. 1993 H. Hoppe, "Progressive Meshes" Proc. Siggraph96 pp99-108, Aug 1996 P.Lindstrom and G.Turk, "Evaluation of Memoryless Simplification" IEEE tvcg, 5(2), pp98-115, April-June 1999, M. Garland and P.S. HEckbert, "Surface Simplification Using Quadric Error Metrics," Proc. SIGGRAPH 97, pp.209-216, Aug. 1997. C. M. Hoffmann. The problems of accuracy and robustness in geometric computation. Computer, 22(3):31-41, 1989. K. Sughihara and M. Iri. A solid modeling system free from topological inconsistency. Journal of Information Processing, 12:380-393, 1989. A. Kela. Hierarchical octree approximations for boundary representation-based geometric models, Computer-Aided Design, 21(6):355-362, 1989. I. Navazo, D. Ayala and P. Brunet. A geometric modeller based on the exact octtree representation of polyhedra, Computer Graphics Forum (Eurographics '86 Proc.):591-104, 1986. W. Lorensen and H. Cline. H. Marching cubes: high resolution 3D surface construction algorithm. ACM Computer Graphics (Proc. of ACM SIGGRAPH '87), 21(4):163-169, 1987. I. Navazo, D. Ayala, and P. Brunet "A Geometric Modeller Based on the Exact Octtree Representation of Polyhedra", Computer Graphics Forum 5 pp91-104, 1986 T. Hama, M. Asakawa, M. Takamura, A. Makinouchi, C.Teodosiu, "A stable and fast new contact search algorithm for FEM simulation of metal forming process", (to appear)

［非特許文献１］や［特許文献１］で提案されている、セルとセルに適合化する三角形パッチによる形状表現とそのデータの生成方法は、以下の３ステップで行っている。
（ステップ１）ユーザーにより定義されたセル空間と、入力形状としての三角形パッチの交点計算（セル切断点の計算）。
（ステップ２）各セル毎にセル切断点をセル面上で結んでできる閉ループを生成する。その際は、セル内のセル切断点の個数や隣接セルとの関係を元に、一意に定まるものから順に決定する。
（ステップ３）各セルで生成された閉ループ内を、入力形状との差異を元に三角形分割を行う。

しかし、この方法には以下の問題点があった。
（１）セルサイズと同程度の複雑さを持つ形状に対し、（ステップ２）の処理が終了しないケースがある。
（２）セルサイズより細かい形状から、徐々に大きな形状に変化する途中で、非多様体形状が発生するため、（ステップ２）の処理に失敗するケースがある。
（３）セルを階層化することを考慮した場合、（ステップ２）の処理において隣接関係の検索が著しく困難である。

これらの問題点を解決する手段として、入力形状の三角形パッチの位相情報をそのまま使用し、かつ必要に応じて形状の簡略化を行う手段が必要とされていた。
なお、三角形パッチをセルのサイズに分割して、セルで管理する方法も［特許文献３］に提案されているが、この方法においては、三角形パッチはセルに適合しておらず、セル対三角形パッチが一対一で管理できない方法であり、ＶＣＡＤの目的である、ものつくりにおける上流から下流工程までの一元化したデータ管理には適用し得ない。なお、ＶＣＡＤは（独）理化学研究所の登録商標です。

また、三角形パッチ単独での処理については、三角形パッチの細分化／統合を行うことにより、形状表現の詳細化／簡略化を行う方法は既にＨｏｐｐｅ［１１］等によって提案されており［非特許文献１２］、細分化のパラメータや分割方法、ならびに統合時の判断基準により様々な派生システムが存在している。但し、これらの方法では、元の形状の二多様体条件および位相条件をそのまま継承する変換方法となっており、微小な形状を意図的に簡略化するなどの操作には不向きである。［非特許文献６，７，８］

本発明は、上述した問題点を解決するために創案されたものである。すなわち、本発明の目的は、ボリュームＣＡＤにおいて、入力形状の三角形パッチの位相情報をそのまま使用し、かつ必要に応じて形状の簡略化を行うことができる、境界表現データからボリュームデータを生成する方法及びそのプログラムを提供することにある。

ＶＣＡＤ［非特許文献１］の形状表現方法として、直方体セルと各セルに適合化した三角形パッチを利用する手段を採用する。本発明は、三次元の形状表現方法として多用される三角形パッチ群から、セルに適合化した三角形パッチ群への変換を実現するものである。

この課題を達成する手段として、以下の２つの方法を創案した。
（１）元の三角形パッチ群の位相や二多様体条件を変えることなく三角形パッチの細分化／統合を行い、セルに適合化させる方法。
（２）セルのサイズ以下の構造について、二多様体条件を変えることなく位相構造の編集を行い、全体形状を近似的に表現する方法。
これらの方法およびプログラムの開発により、任意の形状データを任意のサイズのセルに適合させることができ、設計のみならず解析や製造、リバースエンジニアリング等、ものつくりの全工程に渡って利用可能なデジタルデータの形態を実現できる。
また、この形状表現方法の発明に伴い、従来の境界表現形式のデータで記述されていたＣＡＤでは実現の困難であった、お互いに接する形状での集合演算なども実現可能となっている。

本発明の方法およびプログラムは大きく分けて次の３ステップで構成される。
（ステップ１） 位相付き三角形パッチのセル面での分割。
（ステップ２） 位相付き三角形パッチの頂点のうち、セル稜線上にあるもの以外を他の頂点に統合。
（ステップ３） （ステップ２）の条件や、ＶＣＡＤのデータ構造の条件（一稜一切断点の条件）に反する部位の、近似処理による適正化。

これらのステップの中で、
（ステップ１）の処理中に、分割に利用したセル面の情報を三角形頂点に付与し、（ステップ２）の統合処理に利用する。

（ステップ３）の処理が必要な形状は下記６種類（ａ，ｂ，ｃ，ｄ１，ｄ２，ｄ３）に分類され、それぞれに対して、５種類の処理とその組み合わせを適用することで、形状の近似・適正化を行う。
（ａ） セル内で独立した多面体／三角形パッチ。
（ｂ） 隣接セル同士で、面上点を含んだ３点またはそれ以上で三角形パッチがつながっているケース。
（ｃ） 隣接セル同士で、同一稜上の点を含んだ３点またはそれ以上の点で三角形パッチがつながっているケース。
（ｄ） （ｃ）以外のケースで同一のセル稜上に２点以上の切断点が残っているケース。

更に（ｄ）のケースについては、個々の切断点につながる三角形パッチの状態によって、３つのパターン（ｄ１，ｄ２，ｄ３）に分割でき、それぞれの状態に応じた処理を行うことで、稜上の点を１点ずつ消去していき、最後に残る（ｄ３）のケースについては、２つの三角形群を一組として、稜上の切断点を消去する。その結果として、稜上の切断点が０点または１点となるまで処理を続ける。
（ｄ１） 該当の切断点が三角形パッチの境界になっているケース。
（ｄ２） 該当の切断点は三角形の内部点となっていて、その位置で折れ曲がっているケース。
（ｄ３） 該当の切断点は三角形パッチの内部点であり、その稜を横断しているケース。

（Ａ） セル内で独立した多面体／三角形パッチの削除。
（Ｂ） 細い筒／穴形状の分割。
（Ｃ） 微小距離離れた点で強制的に綾線分割。
（Ｄ） ２枚の板に穴を開け、筒状に繋げる。
（Ｅ） 切断点の属性のふりなおし。

これらの処理を導入することにより、ＣＡＤにおけるセルとセルで管理された三角形パッチの形状表現において、以下の利点が発生する。
（１）入力となる表面形状データの二多様体条件／位相条件を変更することなく、必要なサイズのセルに適合化することができる。
（２）指定したセルサイズ以下の微細な形状を、入力した表面形状データの二多様体条件を変更することなく、近似・簡略化を行うことができる。
（３）入力の三角形パッチデータを準備することで、任意の形状のモデリングを行うことができ、またＶＣＡＤのデータを再利用して、変形操作や集合演算（Ｂｏｏｌｅａｎ）操作などの処理を行うこともできる。特に、接している形状同士の集合演算操作は既存の境界表現ＣＡＤでは問題となることの多かった処理であるが、これを問題なく実現している。
（４）単一階層セルに対する処理に、数点の簡単な処理を加えることで、階層化セルへの対応が実現できる。

本発明により、入力形状の三角パッチの位相情報をそのまま使用し、かつ必要に応じて形状の簡素化を行うことができる。

以下、本発明の好ましい実施形態を図面を参照して説明する。

ボクセル（Ｖｏｘｅｌ）や八分木セル（Ｏｃｔａｎｔ）とセルに適合化された三角形パッチ群で形状を表現する方法について、既にいくつかの論文で提案されている。
本発明では境界表現データ（以下、Ｂ-ｒｅｐ．データ）から、位相付き三角形パッチ（Ｉｎｔｅｒｍｅｄｉａｔｅ-Ｔｒｉａｎｇｌｅ）を経由して、無限平面での切断による交点での稜線分割（Ｅｄｇｅ Ｓｐｌｉｔ）や、セルのインデックス情報を利用した稜線統合（Ｅｄｇｅ-Ｃｏｌｌａｐｓｅ）によりセルに適合化した三角形パッチを生成並びに編集する方法、及びこのようなデータを扱うシステムとしてのボリュームＣＡＤ（以下ＶＣＡＤ）を提案する。
またその際に、各三角形がセルで管理できることから、セルのサイズ以下の構造（細い穴や棒、薄い板や隙間）があるケースにおいては、位相構造の編集（穴の消滅や作成／微小シェルの削除）を伴う形状の近似処理を行う。
基本的な処理としてボクセル（単一の大きさのセル）をベースについて説明し、その後、八分木セルへの拡張を説明する。
これにより、従来パラメトリック曲面等を用いた境界表現ＣＡＤにおいて問題となっていた幾何演算の頑健化と並列化による高速化を目指し、統一されたデータを用いて構造解析や熱流体解析などのシミュレーション、及び様々な加工や内部構造物を持つ物体からの計測データとの比較における直接利用を目的としている。

図２は、本発明の方法を実行するための装置構成図である。この図に示すように、この装置１０は、外部データ入力手段２、外部記憶装置３、内部記憶装置４、中央処理装置５および出力装置６を備える。

外部データ入力手段２は、例えばキーボードであり、対象物の境界表現データからなる外部データを入力する。外部記憶装置３は、ハードディスク、フロピィーディスク、磁気テープ、コンパクトディスク等であり、形状と物理量を統合したボリュームデータとその生成プログラムを記憶する。内部記憶装置４は、例えばＲＡＭ，ＲＯＭ等であり、演算情報を保管する。中央処理装置５（ＣＰＵ）は、演算や入出力等を集中的に処理し、内部記憶装置４と共に、プログラムを実行する。出力装置６は、例えば表示装置とプリンタであり、記憶したボリュームデータとプログラムの実行結果を出力するようになっている。
中央処理装置５、内部記憶装置４及び外部記憶装置３は、共同して、後述するデータ変換手段、関連付け手段、分割配置手段、稜線統合手段、状態チェック手段、簡略化手段セル割振手段、およびラベリング手段として機能する。

外部から入力する外部データは、多面体を表すポリゴンデータ、有限要素法に用いる四面体又は六面体要素、３次元ＣＡＤ又はＣＧツールに用いる曲面データ、或いはその他の立体の表面を部分的な平面や曲面で構成された情報で表現するデータである。

外部データは、このようなデータ（Ｓ−ＣＡＤデータと呼ぶ）のほかに、（１）ＶＣＡＤ独自のインターフェース（Ｖ−ｉｎｔｅｒｆａｃｅ）により人間の入力により直接作成されたデータと、（２）測定機やセンサ、デジタイザなどの表面のデジタイズデータや、（３）ＣＴスキャンやＭＲＩ、および一般的にＶｏｌｕｍｅレンダリングに用いられているボクセルデータなどの内部情報ももつＶｏｌｕｍｅデータであってもよい。

１． 序論
従来のＢ-ｒｅｐ．データ（境界表現データ）を扱っていたＳｏｌｉｄ ＣＡＤ、またはＳｕｒｆａｃｅ ＣＡＤ（以下Ｓ-ＣＡＤと総称する）のデータは、非常に小さなデータサイズで様々な形状を表現することが出来る一方で、面の境界位置での精度などにより、データの再利用性が大きく低下するなど、その運用に細心の注意を払わなければいけない［非特許文献１５］［非特許文献１６］。
また、ＣＡＥやＣＡＭにおいてはそれら数値誤差に起因する処理の不安定さや収束計算による処理時間を嫌って、多くの場合三角形パッチやボクセルなどに変換して利用しているのが現状である。
また、特に集合演算などの幾何演算を高速化する目的で、八分木を用いたソリッドモデラ［非特許文献１７］や八分木セルと多面体を対応させた、拡張八分木（Ｅｘｔｅｎｄｅｄ Ｏｃｔｒｅｅ）などの研究［非特許文献１８］などもあるが、本発明のようにセルより小さい構造を後流の解析や加工において抑制する目的で、位相を超えて簡略化したり、八分木において隣接セル間で階層差が有る場合も隙間なく２多様体条件を維持する仕組みは無い。

本発明では、ボクセルないしは、八分木セル（Ｏｃｔａｎｔ）などの階層化セルとセル内の三角形群で構成するボリュームＣＡＤのデータ構造であるＫｉｔｔａ Ｃｕｂｅ［非特許文献１］［非特許文献２］［非特許文献３］を提示し、これにより、下流工程で利用する三角形パッチの精度やサイズのコントロールを行い、設計のみならず、解析や製造、内部構造も含めたリバースエンジニアリングに利用可能なデータ構造と、位相付き三角形パッチに対して基本的な操作で位相条件を保ちつつＫｉｔｔａ Ｃｕｂｅを構築する方法を提案する。
さらに、Ｋｉｔｔａ Ｃｕｂｅを利用すると、集合演算などがセル単位の局所的な演算処理のみで行うことが出来るため、Ｂ-ｒｅｐ．データを扱っているＳ-ＣＡＤとするのは困難であった、お互いに接する形状同士の集合演算［非特許文献４］も容易に実現している。なお、本発明において、ボリュームデータとは、ボリュームＣＡＤのデータ構造であるＫｉｔｔａ Ｃｕｂｅを意味する。

２． 背景
形状表現の方法として、三角形パッチを利用する方法は、データ構造の簡便性や計算処理の簡便性・処理速度の点からＣＧ、ＣＡＥ、ＣＡＭ、リバースエンジニアリングなどの幅広い分野で利用されている［非特許文献７］［非特許文献１２］［非特許文献１９］。その上で、ＣＡＥやＣＡＭで利用する際の接触判定など局所的な演算を多用するケースでは、ボクセル等を利用して空間上に浮かぶ三角形を管理する方法も多く用いられている［非特許文献１０］［非特許文献２０］［非特許文献２１］。
ＶＣＡＤにおいては、八分木セルと各セルで管理される三角形パッチを形状表現に用いている［非特許文献１］［非特許文献２］［非特許文献３］。さらに、三角形パッチ（以下Ｋｉｔｔａ Ｃｕｂｅで管理される三角形を「切断三角形」とする）を構成する頂点の位置は、各セルの頂点または稜線上に限定し、稜線上の頂点数を高々１個に限定することで、データ構造と処理の簡略化を図っている。
このようなデータ構造により、三角形パッチの精度やサイズをコントロールすることが出来るメリットがある一方で、セルのサイズよりも小さい形状に対してどのように処理を行うか、が課題となっている。その解決手段の一つにＭａｒｃｈｉｎｇ Ｃｕｂｅ（以下ＭＣ）法［非特許文献１９］があるが、幅広い表現力［非特許文献１］とＳ-ＣＡＤの情報をより直接取り扱える方法としてＫｉｔｔａ Ｃｕｂｅを用いた三角形を検討した。

３． 先行技術
３．１ ＶＣＡＤのデータ構造
ＫａｓｅらによるボリュームＣＡＤ［非特許文献１］などで提案されたＶＣＡＤデータはボクセルによる三角形パッチの管理を主眼に置いていた。データ構造は図３のようになっており、本発明の方法の目標もこのデータ構造である。
このデータ構造では、三角形パッチを管理するセルとしての境界セル、及び三角形パッチとは関連しない非境界セルの２種類があり、境界セルでは頂点毎、非境界セルではセルで１つの媒質値を保持している。

３．２ ＶＣＡＤの先行する方法とプログラム
ＶＣＡＤのデータ生成方法は、以下のステップで行われている。
（１）ステップ１ 切断点の計算
モザイク化（Ｔｅｓｓｅｌｌａｔｉｏｎ）した三角形パッチとセルの稜線との交点を計算をし、切断点を求める。その際に、セル稜上に複数の交点が求まった場合には、代表となる１点に統合する。
（２）ステップ２ ループの決定と切断三角形の設定
各セルの切断点の配置から、セル内での切断三角形の境界ループを、隣接するセルとの位相関係を利用して順に決定し、幾何形状と比較して切断三角形を設定する。
（３）ステップ３ セルの内外判定
最初に非境界セルの内外判定を行い、続いて、非境界セルの内外判定を行う。非境界セルの内外判定は任意のセルに初期値を与えた上で、隣接する非境界セル同士が同じ媒質値を持つようにする。境界セルの内外判定は、非境界セルと共有している頂点に非境界セルの媒質値を設定し、それで求まらない頂点については、切断点を含まないセル稜線、ならびに切断三角形と交差しないセルの対角線を辿って既知の媒質値を付加してゆく。なお、切断点がセル頂点上に存在するケースでは、該当のセル内での媒質値が占める方位角が大きい方の媒質値を採用する。

これらのステップ１〜３により、多彩な形状に対するＫｉｔｔａ Ｃｕｂｅの作成が可能であり、低品質なＳ-ＣＡＤのデータの入力に対しても適切な変換が可能である。その一方で、セルのサイズより小さい構造に対して適切な近似が困難であった。本発明の方法においてはこの点に対応する処理と、八分木（Ｏｃｔｒｅｅ）構造に対する取扱いの簡単な処理を検討した。

そこで、本発明で紹介するように、位相付き三角形パッチに対して、位相を保持する簡略化およびその逆操作としてＨｏｐｐｅ［非特許文献１１］［非特許文献１２］やＳｈｒｏｅｄｅｒ［非特許文献７］、Ｒｅｎｚｅ［非特許文献８］、Ｈａｍｍａｎ［非特許文献９］等によって提案された、稜線分割（Ｅｄｇｅ-Ｓｐｌｉｔ）処理と稜線統合（Ｅｄｇｅ-Ｃｏｌｌａｐｓｅ）処理によって、セルに適合化する方法を開発した。また、後流のシミュレーションや加工にそのまま使えるように、セルサイズよりも小さな構造を近似的に表現する目的で、三角形パッチの二多様体性を保持しつつ、位相構造の修正（穴の作成・消滅／シェルの分離・統合）を行える方法を新たに開発した。

三角形パッチの位相を変更する再メッシュ化（Ｒｅｍｅｓｈｉｎｇ）については、Ｊｕ［非特許文献５］やＳｈｒｏｅｄｅｒ［非特許文献６］が提案しているが、Ｊｕの方法は、Ｈｅｒｍｉｔｅデータを作成する必要があるという点、Ｓｈｒｏｅｄｅｒの方法は、オイラー演算のうちのリング（またはループ）の消滅により三角形の簡略化を進めるものであり、小さな穴の除去には対応していない、という点で、目的では直接使えない。

４． 本発明の方法とプログラム
本発明の方法の概要を「あらまし」に、それぞれのステップにおける詳細を４．２-４．４、本方法を利用した集合演算（Ｂｏｏｌｅａｎ）の概要を４．５、さらに八分木（Ｏｃｔｒｅｅ）に拡張する際の変更点を４．６示す。

４．１ あらましと中間データ
Ｓ-ＣＡＤデータからＶＣＡＤデータを作成する途中で、中間データとして位相付き中間三角形（Ｉｎｔｅｒｍｅｄｉａｔｅ-Ｔｒｉａｎｇｌｅ）を利用している。位相付き中間三角形は位相付き中間稜線（Ｉｎｔｅｒｍｅｄｉａｔｅ-Ｅｄｇｅ）／位相付き中間頂点（Ｉｎｔｅｒｍｅｄｉａｔｅ-Ｖｅｒｔｅｘ）の階層構造のデータで構成され、位相付き中間頂点は、頂点が含まれるセルの索引データ（Ｉｎｄｅｘ）と、頂点のタイプ（セル内（ＢＯＤＹ）、セル面（ＦＡＣＥ＿ＹＺ，ＦＡＣＥ＿ＺＸ，ＦＡＣＥ＿ＸＹ，）、セル綾（ＥＤＧＥ＿Ｘ，ＥＤＧＥ＿Ｙ， ＥＤＧＥ＿Ｚ，）頂点（ＶＥＲＴＥＸ））を属性値として保持する。

このデータ構造を利用して、セル面を含む無限平面と、位相付き中間稜線の交点を計算して、位相付き中間三角形を細分化し、セルの稜線に合わせて稜線統合を行うことで、位相付き中間三角形のセル適合化を行う。
本発明の方法のフローチャートを図４に示す。これらのステップの中で、処理の概要と一般的な処理のステップをここで解説する。この図のＳ-ＣＡＤ Ｄａｔａ、すなわち境界表現データは、ステップ１に先行した予め外部データ入力手段２によりコンピュータの外部記憶装置３又は内部記憶装置４に入力される。

（１）ステップ１：モザイク化（データ変換）
中央処理装置５、内部記憶装置４及び外部記憶装置３が共同して、データ変換手段により、データ変換ステップを実施する。すなわちステップ１では、Ｂ-ｒｅｐデータをソリッド化（面の境界線のマージ）を行い、これを元に表面形状を位相付き三角形パッチに変換する。この時、元のＢ-ｒｅｐデータの精度が悪く、ソッリッド化が上手くいかないケースでは、位相付き三角形パッチへの変換時に上手く位相をつなぐことができず、三角形パッチに穴が空くケースが存在するが、これに対しては、指定した閾値以下の直径の隙間が空いている部分の多角形を三角形分割することで、穴埋めを行っている。
（２）ステップ２：セルマッピング（関連付け）
中央処理装置５、内部記憶装置４及び外部記憶装置３が共同して、関連付け手段により、関連付けステップを実施する。すなわちステップ２では、セル面による切断点計算を高速化するために、あらかじめどのセルにどの三角形が含まれているかの関連付けを三角形に外接する座標軸に沿った直方体（Ｂｏｕｎｄｉｎｇ Ｂｏｘ）を用いて行う。
（３）ステップ３：交点の計算と綾線分割（分割配置）
中央処理装置５、内部記憶装置４及び外部記憶装置３が共同して、分割配置手段により、分割配置ステップを実施する。
（４）ステップ４：稜線統合
中央処理装置５、内部記憶装置４及び外部記憶装置３が共同して、稜線統合手段により、稜線統合ステップを実施する。

（５）状態チェックステップ
中央処理装置５、内部記憶装置４及び外部記憶装置３が共同して、状態チェック手段により、状態チェックステップを実施する。このステップでは、データ量と処理時間の双方を管理するため、Ｋｉｔｔａ Ｃｕｂｅでは稜線統合（エッジコラプス）の終了時に以下の項目を満たしているかを判定する。（稜ベースの点管理）
ａ）セル体内、あるいはセル面上には三角形の頂点を持たない。
ｂ）セル稜上には三角形パッチの頂点は一つのみとする。
ｃ）切断点統合によって位相が変わる現象が発生しない。
これらの条件を満たさない頂点が見つかった場合、その周辺の形状を４．４の方法によって近似処理し、セル内の三角形パッチで表現できる形状とする。
（６）ステップ５：簡略化（Ｓｉｍｐｌｉｆｙ）
中央処理装置５、内部記憶装置４及び外部記憶装置３が共同して、簡略化手段により、簡略化ステップを実施する。

（７）ステップ６：三角形のセル適合（セル割振）
中央処理装置５、内部記憶装置４及び外部記憶装置３が共同して、セル割振手段により、セル割振ステップを実施する。すなわちステップ６では、頂点の索引データを参考に、各三角形とその頂点をセルに割り振る。ここで、図３に示したＫｉｔｔａ Ｃｕｂｅのデータ構造が生成される。
（８）ステップ７：セルの内外判定（ラベリング）
中央処理装置５、内部記憶装置４及び外部記憶装置３が共同して、ラベリング手段により、ラベリングステップを実施する。すなわちステップ７では、セル同士の隣接関係などを利用して、セルの属性値を設定する。このステップ７では、[特許文献４]の記載の方法を適用する。すなわち、各セルの各頂点を境界データで仕切られた複数の空間に区分する空間区分ステップ（Ｄ）を有する。この空間区分ステップ（Ｄ）は、境界データで仕切られた空間毎に異なる空間番号を全ての非境界セルに設定する非境界セル設定ステップ（Ｄ１）と、境界セルの各頂点を境界データで仕切られない隣接する非境界セルの空間番号に設定する境界セル設定ステップ（Ｄ２）とからなる。また、境界セル設定ステップ（Ｄ２）において、境界データと一致する頂点を隣接する２つ非境界セルの空間番号のいずれかに設定する。さらに非境界セル設定ステップ（Ｄ１）は、Ｘ，Ｙ，Ｚの３方向に対して順に繰返し、或いは再帰的な処理により、直方体セルの全てを順に走査する。
ステップ７でセルの属性値を設定したデータはＶＣＡＤ Ｄａｔａ（ボリュームデータ）として、外部記憶装置３および出力装置６に出力される。

４．２ 交点の計算と綾線分割（エッジスプリット）
空間上に浮かんだ位相付き三角形パッチをセル面で分割し、全ての三角形がセルの内部及び境界上に配置される状態とすることを目的としている。
最初に、既存の位相付き中間頂点の初期化処理として、各頂点がいずれかの面上にあるか否かにより、ＢＯＤＹ〜ＶＥＲＴＥＸまでの属性値、ならびに、その座標値から含まれるセルの索引データを付加しておく。
その後、セルマッピング情報ならびに、位相付き中間三角形の位相情報を利用して、位相付き中間稜線とセル面を含む平面との交点計算を行い、その交点を新たな位相付き中間頂点として登録し、４．１に記述した、属性値ならびにその点が属するセルの索引データを順に付加する。

４．３ 稜線統合（エッジコラプス）
このステップでは、［非特許文献７］［非特許文献８］［非特許文献９］［非特許文献１１］［非特許文献１２］等に示されるように、位相の変更を行わない稜線統合を行う。また、位相の保持の他に、三角形の頂点をセルの稜上、またはセル頂点に限定するために、稜線統合可能な条件として、以下の項目が付加される。
（１）体内点は任意の属性値の点に統合する。
（２）面上点は面上点、稜上点またはセル頂点に統合する。
（３）稜上点はそのまま残すか、稜上点又はセル頂点に統合する。
（４）セル頂点はそのまま残すかセル頂点に統合する。
（５）上記の条件で統合する際には、同一セル内の点にのみ統合する。
これらの条件を表１及び表２に示す。

表の縦軸に属性値ｔ１，横軸に属性値ｔ２を入れて得られた値をフラグとする。以下の表にある条件を満足する場合，属性値ｔ２を属性値ｔ１へ向かって統合する．

上記の統合可能な条件に該当する隣接位相付き中間頂点が複数存在するケースでは、［非特許文献１４］等で記述されているＱｕａｄｒｉｃ Ｅｒｒｏｒ Ｍｅｔｒｉｃ（ＱＥＭ）の値によって、体積変化が少ない順に優先順位を設定し、元の幾何形状に近い形に稜線統合がなされるようにしている。

４．４ 状態チェック
稜線統合の結果、減少した三角形群が、以下の条件を満たしているかどうかを確認する。
（１）面上点／体内点が残っていない。
（２）索引データと属性値が同一の点が残っていない。
これらの条件を更に詳細に分析すると、以下の条件が存在する。
（ａ） セル内で独立した多面体／三角形パッチ（図５）
（ｂ） 隣接セル同士で、面上点を含んだ３点またはそれ以上で三角形パッチがつながっているケース（図６）
（ｃ） 隣接セル同士で、同一稜上の点を含んだ３点またはそれ以上の点で三角形パッチがつながっているケース（図７）
（ｄ）（ｃ）以外のケースで同一のセル稜上に２点以上の位相付き中間頂点が残っているケース

更に（ｄ）のケースについては、個々の位相付き中間頂点につながる三角形パッチの状態によって、３つのパターンに分割でき、それぞれの状態に応じた処理を行うことで、稜上の点を１点ずつ消去していき、最後に残る（ｄ３）のケースについては、２つの三角形群を一組として、稜上の位相付き中間頂点を消去する。その結果として、稜上の位相付き中間頂点が０点または１点となるまで処理を続ける。

（ｄ１） 該当の位相付き中間頂点が三角形パッチの境界になっているケース（図８）
（ｄ２） 該当の位相付き中間頂点は三角形の内部点となっていて、その位置で折れ曲がっているケース（図９）
（ｄ３） 該当の位相付き中間頂点は三角形パッチの内部点であり、その稜を横断しているケース（図１０）
それぞれのケースに応じて、簡略化のステップでの処理を分岐する。

４．５ 簡略化
形状の近似については、以下の５種類の操作とその組み合わせで網羅している。
（１）セル内で独立した多面体／三角形パッチの削除
同一の索引データを持つ位相付き中間頂点による三角形が多面体（Ｈｏｐｐｅの規則に従うと基本的に四面体となるが、面上点から他の面上の点への統合が出来ないことから本方法においては他の多面体も考えられる）を構成しているものを、三角形の辺が全てセル内の三角形で共有されていることから検索する。
また、多角形が単独で浮いているものについては、どの辺も他のセルの三角形と共有していない三角形群を見つけることで、検索する。
こうして見つかった多面体または多角形に属する全ての三角形、位相付き中間頂点を削除する。

（２）細い筒／穴形状の分割
図６や図７に示すような細い筒型形状や穴形状があるケースでは、表１，表２に示す条件で稜線統合しようとすると、Ｈｏｐｐｅの条件に反して位相構造が変わってしまう状況が発生する。
このようなケースが発生した時に、稜線統合しようとして失敗した２点とそれに隣接する任意の１点で構成される３点（すなわち、図では面上の３点であるが、すべてセル稜上の点となるケースもある）で構成される三角形を境に形状を分割し、両側の開いた３辺をそれぞれの三角形で塞ぐ。このとき、分割した三角形の頂点は複製して別々の要素として扱う。

（３）微小距離離れた点で強制的に稜線分割（エッジスプリット）
図１３〜図１５に示すような、セル稜線上に複数の頂点があるケースに対応する前処理として行う。対象とする位相付き中間頂点に接続している三角形の辺をリストアップし、その微小距離離れた位置に位相付き中間頂点を作成して、この点で稜線分割を行う。

（４）２枚の板に穴を開け、筒状に繋げる。
（３）の処理に引きつづいて行うことを前提とする。したがって、対象とするセル稜上の２点は、既に近傍の点で稜線分割がされているものとする。
対象とするセル稜上にある２点とその点を利用している三角形を削除する。これにより、セル稜の周囲に小さな穴が発生する。
続いて、２枚の穴の間に筒状の三角形パッチを発生させる。その際には各セル毎に処理を進めることで、自己干渉の無い三角形パッチを構成する。（図１５）

（５） 属性値の変更
各種の近似処理を行った後、再度稜線統合を行うために、セル稜上やセル面上にある点を面上点や体内点に変更する。その際、面上点に変更するケースでは、次のステップで統合される方向（隣接している頂点）の索引データを見て面のＩＤと索引データを設定する。

以下に、状態チェックの項に対応して、それぞれの処理を記述する。
（ａ）独立した多面体／三角形パッチ
処理（１） ：図１１
（ｂ）隣接セル同士の接続
処理（２）の後（５） ：図１２
（ｃ）隣接セル同士の接続（２）
処理（２）の後（５）
（ｄ１）三角形パッチ境界
処理（３）の後（５） ：図１３
（ｄ２）三角形パッチの折れ
処理（３）の後（５） ：図１５
（ｄ３）三角形パッチの通過
処理（３）の後（４） ：図１６
これらの処理を行った後、面上点／体内点が残っている、あるいは面上点や体内点を追加する処理を実行している場合には、稜線統合の処理に戻る。

４．６ 集合演算（Ｂｏｏｌｅａｎ）
本方法を利用することにより、セルと位相付き三角形パッチを準備すれば、自由にセル内面の構成が可能になった。また、境界となる三角形をセルで管理しているため、集合演算処理などの形状演算についても、Ｋｅｌａ［非特許文献１７］も指摘しているように１セル毎、あるいは１隣接近傍のみを参照するだけの局所的な演算を繰り返すだけで、処理が可能になっている。

さらに、例えば、以下のステップで集合演算演算が可能であり、ＮＵＲＢＳ曲面を利用したＳ-ＣＡＤの集合演算よりもはるかに頑健な計算が可能である。
（１）ステップ１：非境界セル同士の演算
ターゲットとする媒質を含んでいるか否かで判断できる。通常のボクセルのＢｏｏｌｅａｎと同じ処理である。

（２）ステップ２：非境界セル対境界セルの演算
演算の種類、どちらのセルが境界セルとなっているかにより、処理は分岐するが、どちらかのセルの情報がそのまま、あるいは境界面を反転するのみで引き継がれることになる。対応表を表３に示す。表中のＢａｓｅとは、Ｂｏｏｌｅａｎ演算の基準側のセルを指し、Ｔｏｏｌとは付け足す、或いは引き算するセルを示す。（実際には、ＢａｓｅとＴｏｏｌの差異はＳｕｂｔｒａｃｔｉｏｎの時のみ関係する。この場合はＯｂｊｅｃｔ＝Ｂａｓｅ-Ｔｏｏｌと考える）また、処理欄の文字について、Ｉｎｓｉｄｅ：目標とする形状の内側、Ｏｕｔｓｉｄｅ：目標とする形状の外側、Ｂｏｕｎｄａｒｙ：目標とする形状の境界であり、ＢａｓｅまたはＴｏｏｌのいずれか、境界セルの情報をそのまま引き継ぐ。また、（Ｎｅｇａｔｉｖｅ）とは、境界セルのセル内面を反転して引き継ぐことを示す。

このように処理した情報から、境界の三角形を引き継いだ情報を順に接続してゆく。

（３）ステップ３ 境界セル対境界セル
ここでは、同じセル領域で三角形同士が交差／共存／重複している状態になっている。これを目標とする形状に編集するために、以下の処理を行う。
（Ｓ１） 三角形同士の交差計算を行い、三角形パッチの交線部分でそれぞれの三角形が分割されている状態になるように稜線分割を行う。
（Ｓ２） 双方の三角形のうち、不要な領域にあるものを削除する。（表４）

（Ｓ３） 三角形同士をマージする。その際、Ｓｕｂｔｒａｃｔｉｏｎ演算のＴｏｏｌ側セルの境界面は表裏反転してマージする。
（Ｓ４） 三角形同士が同一平面上に存在しているケースでは、その三角形の表裏方向により、次のように処理を行う。
（ａ）同方向：一致している２枚の面の片方を残す
（ｂ）反対方向：一致している２枚の面を両方削除する
（Ｓ５）マージした三角形パッチを、順に位相付き三角形パッチに連結してゆく。
（４）ステップ４
このように接続した三角形を元に、改めて稜線統合処理以下を行うことで、集合演算が終了する。

４．７ 八分木への拡張
ここまで、均質な直方体セルを前提に検討を進めてきたが、八分木化した場合にも若干の変更点を加えることにより、簡単に同様の処理でセルの適合化が可能である。

変更点を以下に記す
（１） 隣接する境界セル間で階層差が存在する場合、サイズの大きい側のセルを“つなぎセル”とし、下記の条件を緩和する
・共有面上には面上点を許容する
・共有する稜線上には２個以上の切断点を許容する。（図１６）
（２） 稜線分割は最も細かいセルに合わせて切断平面群を準備し、各面をセル面として利用するセルの有無によって、実際の交点計算の是非を決定する。
（３） 稜線統合時には、該当位置でのセルのサイズにより、改めて位相付き中間頂点のＴｙｐｅを振りなおす。このとき、索引データは変更する必要がない。
（４） セルの内外判定の際に、セル稜でつながった頂点同士でのセルの内外判定が出来ない場合、対対角／面対角となる頂点がつなぎセルにおいては単一階層セルにくらべ、より多く存在するため、隣接関係の検索を変更する。
上記の変更により、ＶＣＡＤデータの階層化セルへの対応を実現している。

５． 結果
これらの処理を行って作成されたＶＣＡＤデータを図１７，図１８に添付する。
図１７は実際の工業製品の形状（自動車のバンパーの金型部品）を表示する。セルのサイズよりも細い穴形状がある部分を抜きすと、下段左図の様に、４．５で記述した簡略化また、この穴をＫｉｔｔａ Ｃｕｂｅで表現するためには、セルのサイズを一段階小さくする（下段右図）も可能であるが、この場合のデータ量の増大を考え、下段中図のように、必要なセルだけを階層化することで、データサイズを抑えながら必要とする形状表現を可能としている。なお、これらの形状表現間の変換／逆変換も可能である。

また、集合演算の結果についても、簡単な形状同士の演算結果を、図１８に記載する。ここでは、内接する２つの直方体同士のＳｕｂｔｒａｃｔｉｏｎを計算しているが、２つの形状が接する状態での集合演算は、現在のＳ-ＣＡＤでは失敗することが少なくない。そこで、各国のＣＡＤデータ作成の標準（Ｐｒｏｄｕｃｔ Ｄｅｓｉｇｎ Ｑｕａｌｉｔｙ）では、“モデリングの小技として”形状は必ず明確に交差した状態で集合演算するように推奨されている。これに対して、Ｋｉｔｔａ Ｃｕｂｅを採用したことにより、形状が離散化されていること、セルで管理されていることから、接している形状同士の集合演算も容易に実現している。
上述した実施形態によれば、これまでの方法では困難であった、八分木と八分木セルに適合化した三角形パッチによる形状表現、物性値表現を実現することが出来る。また、三角形パッチへのセル適合化方法の開発により、三角形パッチで表現された形状同士の集合演算などの変形処理が、既存のＢｒｅｐデータに比べて頑健に行えるようになる。結果として、ボリュームＣＡＤにおいて、入力形状の三角形パッチの位相情報をそのまま使用し、かつ必要に応じて形状の簡略化を行うことができ、ＣＡＥやＣＡＭなどとＣＡＤによる設計データとの双方向リンクが実現できる。

［特許文献１］の「形状と物性を統合した実体データの記憶方法」の模式図である。 本発明の方法を実行するための装置構成図である。 ボリュームデータのデータ構造図である。 本発明の方法のフロー図である。 孤立多面体の模式図である。 面上点連結の模式図である。 同一綾上連結の模式図である。 境界点の模式図である。 折れ形状の模式図である。 貫通形状の模式図である。 孤立した多面体（三角形パッチ）の処理の模式図である。 面上点等による連結パッチ処理の模式図である。 一綾複数切断点の境界点処理の模式図である。 一綾複数切断点の折れ点処理の模式図である。 一綾複数切断点の２枚の貫通面処理の模式図である。 面上切断点の模式図である。 実際の工業製品の形状（自動車のバンパーの金型部品）を表示する図である。 簡単な形状同士の集合演算の結果を示す図である。

符号の説明

２ 外部データ入力手段、３ 外部記憶装置、
４ 内部記憶装置、５ 中央処理装置、６ 出力装置、
１０ 装置、１３ａ 内部セル、１３ｂ 境界セル、１５ 切断点

Claims (6)

1. 外部データ入力手段により対象物の境界表現データをコンピュータに入力し、
   データ変換手段により境界表現データを位相付き三角形パッチに変換し、
   関連付け手段により空間を境界平面が直交する直方体セルに分割し、どの直方体セルにどの位相付き三角形パッチが含まれているかの関連付けを行い索引データとして保持し、
   分割配置手段により空間上に浮かんだ位相付き三角形パッチをセル面で分割し、この分割によって生成された全ての三角形パッチが直方体セルの内部及び境界上に配置される状態とし、
   稜線統合手段により、前記三角形パッチの稜線について、位相の変更を行わない稜線統合を行い、
   セル割振手段により、位相付き三角形パッチの頂点がどの直方体セルに含まれるかを示す索引データを参照し、各三角形パッチとその頂点を直方体セルに割り振り、
   ラベリング手段は直方体セルに割り振られた各三角形パッチとその頂点及び直方体セル同士の隣接関係を基に各直方体セルの属性値を設定し、
   前記稜線統合手段による稜線統合の後に、
   状態チェック手段により、稜線統合の結果、減少した三角形パッチ群が、所定の条件を満たしているかどうかをチェックし、
   所定の条件を満たしていない場合、簡略化手段により不具合箇所の簡略化を行い、その後、再度、稜線統合手段による稜線統合を行う、ことを特徴とする境界表現データからボリュームデータを生成する方法。
2. 準備手段が、ボリュームデータと位相付き三角形パッチを準備し、
   集合演算手段が、既存のボリュームデータに含まれる三角形群と、請求項１記載の方法によって生成したボリュームデータに含まれる三角形群との間で、非境界直方体セル同士、非境界直方体セル対境界直方体セル、及び境界直方体セル対境界直方体セルの集合演算を、接続した三角形パッチを基に行う、ことを特徴とする境界表現データからボリュームデータを生成する方法。
3. 請求項１に記載のボリュームデータを生成する方法において、
   前記所定の条件は
   ａ）直方体セル体内、あるいは直方体セル面上には三角形パッチの頂点がない
   ｂ）直方体セル稜上には三角形パッチの頂点は一つである
   ｃ）稜線統合によって位相が変わる現象が発生しない、ことを特徴とするボリュームデータを生成する方法。
4. コンピュータを、
   対象物の境界表現データをコンピュータに入力する外部データ入力手段、
   境界表現データを位相付き三角形パッチに変換するデータ変換手段、
   空間を境界平面が直交する直方体セルに分割し、どの直方体セルにどの三角形パッチが含まれているかの関連付けを行い索引データとして保持する関連付け手段、
   空間上に浮かんだ位相付き三角形パッチをセル面で分割し、この分割によって生成された全ての三角形パッチが直方体セルの内部及び境界上に配置される状態とする分割配置手段、
   位相の変更を行わない稜線統合を行う稜線統合手段、
   位相付き三角形パッチの頂点がどの直方体セルに含まれるかを示す索引データを参照し、各三角形パッチとその頂点を直方体セルに割り振るセル割振手段、
   直方体セルに割り振られた各三角形パッチとその頂点及び直方体セル同士の隣接関係を基に直方体セルの属性値を設定するラベリング手段、
   稜線統合手段による処理の後に、稜線統合の結果、減少した三角形パッチ群が、所定の条件を満たしているかどうかをチェックする状態チェック手段、および
   該状態チェック手段において所定の条件を満たしていない場合、不具合箇所の簡略化を行う簡略化手段、として機能させ、
   前記簡略化手段による処理の後、再度稜線統合手段による稜線統合を行わせるためのボリュームデータの生成プログラム。
5. コンピュータを、
   ボリュームデータと位相付き三角形パッチを準備する準備手段、および
   既存のボリュームデータに含まれる三角形群と、請求項４記載の生成プログラムによって生成したボリュームデータに含まれる三角形群との間で、非境界直方体セル同士、非境界直方体セル対境界直方体セル、及び境界直方体セル対境界直方体セルの集合演算を、接続した三角形パッチを基に行う集合演算手段として機能させるためのボリュームデータの生成プログラム。
6. 請求項４に記載のボリュームデータの生成プログラムにおいて、
   前記所定の条件は
   ａ）直方体セル体内、あるいは直方体セル面上には三角形パッチの頂点がない
   ｂ）直方体セル稜上には三角形パッチの頂点は一つである
   ｃ）稜線統合によって位相が変わる現象が発生しない、ことを特徴とするボリュームデータの生成プログラム。
   
   

Images