(57)【要約】【課題】独立な三次元実体の再構成ができる三次元モデル分割装置及び三次元モデル分割方法を提供する。【解決手段】平面検出ステップは、入力された三角形メッシュで表現される三次元モデルに含まれる、三角形同士が接続し、且つ、該三角形の法線方向が共通または相反する三角形を集めた平面を検出する。輪郭図形抽出ステップは、前記平面検出ステップによって検出された平面から、該平面の各三角形の各辺のうち、１つの三角形のみに属する境界辺同士を接続して前記三次元モデルの輪郭である輪郭図形を抽出する。輪郭図形分離ステップは、前記輪郭図形抽出ステップによって抽出された輪郭図形を重ならない複数の子図形に分割する。三次元実体再構成ステップは、前記輪郭図形分割ステップによって分割された子図形毎に、それぞれが三角形メッシュで表現される三次元実体を再構成する。【選択図】図１Ｂ
2010186479.tif 000002
【特許請求の範囲】
【請求項１】
三次元モデル分割装置が、
入力された三角形メッシュで表現される三次元モデルに含まれる、三角形同士が接続し、且つ、該三角形の法線方向が共通または相反する三角形を集めた平面を検出する平面検出ステップと、
前記平面検出ステップによって検出された平面から、該平面の各三角形の各辺のうち、１つの三角形のみに属する境界辺同士を接続して前記三次元モデルの輪郭である輪郭図形を抽出する輪郭図形抽出ステップと、
前記輪郭図形抽出ステップによって抽出された輪郭図形を重ならない複数の子図形に分割する輪郭図形分割ステップと、
前記輪郭図形分割ステップによって分割された子図形毎に、それぞれが三角形メッシュで表現される三次元実体を再構成する三次元実体再構成ステップと
を実行することを特徴とする三次元モデル分割方法。
【請求項２】
前記三次元モデル分割装置が、
前記三次元実体再構成ステップによって再構成された三次元実体モデル又は前記各子図形の対応する三次元実体が穴であるか否かを、表面の外側に向かう平面の面積と内側に向かう平面の面積の大小から判定する穴判定ステップと、
前記穴判定ステップによって前記三次元実体再構成ステップで再構成されたいずれかの三次元実体モデルが穴であると判定されると、この再構成された三次元実体モデルの全ての三角形の法線方向を相反する方向に変更する、或いは、いずれかの子図形の対応する三次元実体が穴であると判定されると、子図形の対応する三次元実体の全ての三角形の法線方向を相反する方向に変更する穴モデル校正ステップと
を更に実行することを特徴とする請求項１に記載の三次元モデル分割方法。
【請求項３】
前記三次元モデル分割装置が、
前記三次元実体再構成ステップによって再構成された三次元実体モデルに切断面が含まれるか否かを、四角形の平面の２つの頂点の各々が該平面に属さない一つの頂点を持ち、且つ四角形の平面の異なる２つの頂点の各々が該平面に属さない一つの頂点を持ち、それらの該平面に属さない頂点の位置が該四角形の平面から相対する側にあるか否かで判定する、或いは、前記各子図形の対応する前記三次元実体に切断面が含まれるか否かを判定する切断面判定ステップと、
前記切断面判定ステップによって前記三次元実体再構成ステップで再構成されたいずれかの三次元実体モデルに切断面が含まれると判定されると、該切断面により該切断面を含む三次元実体モデルを２つ以上の子図形に分割する一方、前記切断面判定ステップでは、いずれかの子図形に切断面が含まれると判定されると、該切断面により該切断面を含む子図形を２つ以上の子図形に分割する輪郭図形再分割ステップと
を更に実行することを特徴とする請求項１に記載の三次元モデル分割方法。
【請求項４】
前記三次元モデル分割装置が、
前記輪郭図形再分割ステップによって分割された子図形が適正であるか否かを判定し、適正でなければ、該切断面を放棄する適正判定ステップを更に実行することを特徴とする請求項３に記載の三次元モデル分割方法。
【請求項５】
前記三次元モデル分割装置が、
前記輪郭図形再分割ステップによって分割された子図形が、頂点の数が４以上、平面の個数が４以上、かつ、各平面に少なくとも３つの非共線の頂点が含まれる、かつ、各輪郭線が少なくとも２つの異なる平面に属する、かつ、各平面上の頂点が首尾接続で一つの閉領域を構成しなければならない、という条件を全て満足した場合に、該子図形を適正と判定する請求項４に記載の三次元モデル分割方法。
【請求項６】
前記輪郭図形再分割ステップは、
切断面における頂点を第１向き頂点集合と第２向き頂点集合に割り当てて、前記第１向き頂点集合における頂点はそれを切断面以外の頂点と接続してなる接続線が第１方向にあるものであり、前記第２向き頂点集合における頂点はそれを切断面以外の頂点と接続してなる接続線が第２方向にあるものである切断面頂点割当ステップと、
切断面以外の頂点を第１向き側頂点集合と第２向き側頂点集合に割り当てて、前記第１向き側頂点集合における頂点は第１向き頂点集合における頂点と直接又は間接に接続するものであり、前記第２向き側頂点集合における頂点は第２向き頂点集合における頂点と直接又は間接に接続するものである切断面以外頂点割当ステップと、
第１向き頂点集合における頂点と直接接続しない前記第１向き側頂点集合における頂点と、第２向き頂点集合における頂点と直接接続しない前記第２向き側頂点集合における頂点との接続関係に基づき、前記第１向き側頂点集合と第２向き側頂点集合との間に切断面に亘る接続がないように前記切断面に頂点を追加する切断面頂点追加ステップと、
前記第１向き頂点集合と第２向き頂点集合及び前記第１向き側頂点集合と第２向き側頂点集合とに基づき、切断面を含む前記三次元実体モデル又は切断面を含む前記子図形を２つ以上の子図形に分割する子図形分割ステップと
を実行することを特徴とする請求項３に記載の三次元モデル分割方法。
【請求項７】
入力された三角形メッシュで表現される三次元モデルに含まれる、三角形同士が接続し、且つ、該三角形の法線方向が共通または相反する三角形を集めた平面を検出する平面検出部と、
前記平面検出部によって検出された平面から、該平面の各三角形の各辺のうち、１つの三角形のみに属する境界辺同士を接続して前記三次元モデルの輪郭である輪郭図形を抽出する輪郭図形抽出部と、
前記輪郭図形抽出部によって抽出された輪郭図形を重ならない複数の子図形に分割する輪郭図形分割部と、
前記輪郭図形分割部によって分割された子図形毎に、それぞれが三角形メッシュで表現される三次元実体を再構成する三次元実体再構成部と
を有することを特徴とする三次元モデル分割装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、三次元モデル分割装置及び三次元モデル分割方法に関する。
【背景技術】
【０００２】
従来、三次元モデルは、コンピュータグラフィック（CG）技術、仮想現実技術、ＣＡＤ（Computer-Aided Design：コンピュータ補助設計技術）、医用画像、地理情報システムなどの分野で利用される。また、三次元モデルは、科学技術の発展に伴い、さらに複雑化している。これら複雑化した三次元モデルのポリゴンは、万単位、さらには百万単位に達する場合があり、かかる場合には、コンピュータは、記憶容量・処理速度・レンダリング効率・伝送効率などが非常に要求される。また、ポリゴンの増加に伴い、ターゲット検出・局所マッチングなどの技術を利用することが難しくなる。
【０００３】
これら複雑な三次元モデルを比較的単純で、データ量の小さいモデルの集まりに分割できれば、コンピュータは、データ量の小さい、これらのモデルを個別に記憶・処理すればよい。したがって、コンピュータの記憶容量・処理速度・レンダリング効率などが大幅に向上し、ターゲット検出・局所マッチング・三次元検索などの動作に役立つ。この結果、コンピュータは、三次元モデルの管理・再利用が可能となる。
【０００４】
三次元モデル分割は、入力される三次元モデルを複数の部分に分割する技術であり、ターゲット検出・局所マッチング・三次元検索などの分野には、非常に有用である。三次元モデル分割技術は、概ね、入力されるモデルを近似する属性を有する一連のポリゴンに分割する純粋幾何学的分割と、入力されるモデルを一定の形状を有する一連の部分に分割する語義的分割の２種類に分けられる。純粋幾何学的分割は、有用な特徴を抽出する予備処理手段として利用される。一方、語義的分割は、広く注目されており、ターゲット検出などの分野に利用される。
【０００５】
純粋幾何学的分割は、曲率推定及び領域成長法により、入力されるモデルを一連の領域に分割し、各領域を一つのパラメータ化された曲面として抽出する技術が開示されている。かかる技術では、まず各頂点の曲率を算出し、頂点をシャープ頂点とシャープレス頂点に分類し、次にシャープレス頂点の曲率から一連の種領域を得て、種領域毎に一つのパラメータ化領域を対応させる。次に各種領域についてパラメータのフィッティングを行い、次に領域間のエッジを改善すると共に各領域のパラメータを更新し、最後にパラメータ化領域を出力する。かかる技術によれば、例えば、平面、円柱体、球、錐面などの簡単な曲面を検出可能とし、更にラウンド曲面などのレベルの高い曲面をも検出することが可能となる。
【０００６】
また、頂点の曲率を算出し、次に曲率の記号から種領域を生成し、次に領域成長アルゴリズムにより領域のパラメータを徐々に更新し、最後に自由パラメータ化曲面を出力する技術が開示されている。
【０００７】
また、例えば、watershed法を三次元分割に適用する技術が開示されている。かかる技術では、まず各頂点の情報、例えば曲率を算出し、次に局所極小点を見つけて始点とし、次に最急降下法により極小点付近の頂点をクラスタリングする。
【０００８】
また、例えば、入力されるモデルをまず粗く分割してから、徐々に正確な分割を求める技術が開示されている。かかる技術では、まず、測地距離と角度距離から三角形状のポリゴン間の距離を算出する。次に分割領域を初期化し、各三角形状のポリゴンが各領域に属する確率を算出し、繰り返し処理で各三角形状のポリゴンが各領域に属する確率を徐々に更新する。そして、最後に最少カットセット（ＭＣＳ）を用いて正確な境界を得る。
【０００９】
また、例えば、入力されるモデルをまず粗く分割してから、徐々に正確な分割を求める際に、多次元尺度構成法（ＭＤＳ）による変換を導入する技術が開示されている。かかる技術では、分割結果に空間位置不変性を有させ、ロバストな特徴点抽出方法を提案している。これによって三次元モデルを複数の部分に分割し、さらには、各部分の境界を改善するためのカットセット法が導入されている。
【００１０】
また、例えば、三次元モデルを構成する各ポリゴン間の類似度行列を算出し、ポリゴン間の類似度行列に、ポリゴン間の測地距離及び角度距離が含まれ、次にスペクトラルクラスタリング法で三次元モデルを分割する技術が開示されている。
【００１１】
また、例えば、各頂点の曲率を算出し、曲率からシャープネス化エッジ及び頂点を判定する技術が開示されている。かかる技術では、頂点をクラスタリングし、頂点に関するクラスタリング結果に基づき三角形状のポリゴンに対して領域を区分し、次に領域成長法により類似の領域を合併し、最後に区分された領域同士のエッジを改善する。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】米国特許出願公開第２００７/０１８８４９０号明細書
【非特許文献】
【００１３】
【非特許文献１】Vieira,  M.,  Shimada,  K.,  Surface  mesh  segmentation  and  smooth  surface  extraction  through  region growing.  Computer  Aided  Geometric  Design,  Vol.  ２２,  No.８，  ２００５年,  ｐ．７７１-７９２
【非特許文献２】Mangam,  A.P.,  Whitaker,  R.T.,  Partitioning  ３D  surface  meshes  using  watershed  segmentation,  IEEE  Transaction  on  Visualization  and  computer  graphics,  Vol.５,  No.４，  １９９９年,  ｐ．３０８-３２１
【非特許文献３】S.Katz,  A.  Tal,  Hierarchical  mesh  decomposition  using  fuzzy  clustering  and  cuts,  SIGGRAPH,  ２２(３)，  ２００３年，  ｐ．９５４-９６１
【非特許文献４】S.Katz,  G.leifman,  A.  Tal,  Mesh  segmentation  using  feature  point  and  core  extraction,  The  Visual  Computer,  ２１(８-１０)，  ２００５年，  ｐ．８６５-８７５
【非特許文献５】R.  Liu,  H.  Huang,  Segmentation  of  ３d  meshes  through  spectral  clustering,  Pacific  conference  on  Computer  graphics  and  applications,  ２００４年，  ｐ．２９８-３０５
【非特許文献６】G.  Lavoue,  F.  Dupont,  A.  Baskurt,  A new  CAD  mesh  segmentation  method  based  on  curvature  tensor  analysis,  Computer  aided  design,  Vol.３７,  ２００５年，  ｐ．９７５-９８７
【非特許文献７】Z.Q.  Wang,  L.J.  Xiao,  J.Z.  Hong,  Simplicity,  orientation and  inclusion  test  algorithms  for  polygons,  Chinese  J.  Computers,  Vol.２１,  No.２,  １９９８年，  ｐ．１８３-１８７
【非特許文献８】R.Seidel,  A  simple  and  fast  incremental  randomized  algorithm  for  computing  trapezoid  decompositions  and  for  triangulating  polygons,  Computational  Geometry:  Theory  and  Applications,  Vol.１,  No.１,  １９９１年，  ｐ．５１-６４
【非特許文献９】H.  Hoppe,  Surface  reconstruction  from  unorganized  points,  PhD  Thesis,  Dept.  of  Computer  Science  and  Engineering,  University  of  Washington,  １９９４年６月
【非特許文献１０】Joseph  O’Rourke,  Computational  Geometry  In  C  (Second  Edition),  Cambridge  University  Press,  １９９８年
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら上述した従来の技術では、以下の問題があった。例えば、曲率推定及び領域成長法により、入力されるモデルを一連の領域に分割し、各領域を一つのパラメータ化された曲面をもって抽出する技術は、パラメータ化曲面を出力するものであり、適用範囲が狭く、予備処理以外に適用できない。
【００１５】
また、頂点の曲率を算出し、次に曲率の記号から種領域を生成し、次に領域成長アルゴリズムにより領域のパラメータを徐々に更新し、最後に自由パラメータ化曲面を出力する技術は、パラメータ化曲面を出力するものであり、適用範囲が狭い。また、かかる技術は、予備処理以外には適用できない。
【００１６】
また、例えば、watershed法を三次元分割に適用する技術は、ノイズの干渉を受けやすい。また、入力されるモデルをまず粗く分割してから、徐々に正確な分割を求める技術は、理論的には優れる分割結果を得られるが、演算量が大きい。同様に、この方法にＭＤＳ変換を導入する技術は、理論的には優れる分割結果を得られるが、演算量が大きい。
【００１７】
また、スペクトラルクラスタリング法で三次元モデルを分割する技術は、自然な分割結果が得られないおそれがある。また、例えば、各頂点の曲率を算出し、曲率からシャープネス化エッジ及び頂点を判定する技術は、理論的には優れる分割結果を得られるが、演算量が大きい。
【００１８】
すなわち、従来の三次元モデル分割の主な問題には、下記のことが含まれる。
（１）パラメータ化曲面を抽出する方法は、パラメータ化曲面を出力するものであり、適用範囲が狭く、予備処理手段以外に適用できない。
（２）頂点の曲率がノイズからの干渉を受けやすいので、分割結果の正確率が高くなれない。
（３）理論的には優れる分割結果が得られるが、演算量が大きい。
（４）得られた分割結果は、通常ではポリゴンからなる又はポリゴンの組み合わせからなる領域であり、独立な三次元実体ではない。
【００１９】
開示技術は、上記に鑑みてなされたものであって、従来技術の一つ又は複数の課題を解決し、少なくとも一つの有益な選択案を提供することを目的とする。例えば、独立な三次元実体の再構成ができる三次元モデル分割装置及び三次元モデル分割方法を提供することを目的とする。
【課題を解決するための手段】
【００２０】
本願の開示する三次元モデル分割装置及び三次元モデル分割方法は、入力された三角形メッシュで表現される三次元モデルに含まれる、三角形同士が接続し、且つ、該三角形の法線方向が共通または相反する三角形を集めた平面を検出する。また、三次元モデル分割装置及び三次元モデル分割方法は、検出された平面から、該平面の各三角形の各辺のうち、１つの三角形のみに属する境界辺同士を接続して前記三次元モデルの輪郭である輪郭図形を抽出する。また、三次元モデル分割装置及び三次元モデル分割方法は、抽出された輪郭図形を重ならない複数の子図形に分割する。そして、三次元モデル分割装置及び三次元モデル分割方法は、分割された子図形毎に、それぞれが三角形メッシュで表現される三次元実体を再構成する。
【発明の効果】
【００２１】
本願の開示する三次元モデル分割装置及び三次元モデル分割方法の一つの態様によれば、従来技術の一つ又は複数の課題を解決し、少なくとも一つの有益な選択案を提供することができるという効果を奏する。例えば、独立な三次元実体の再構成ができる三次元モデル分割装置及び三次元モデル分割方法を提供する。
【図面の簡単な説明】
【００２２】
【図１Ａ】図１Ａは、開示技術の実施形態によるモデル分割方法の概要を示すフローチャートである。
【図１Ｂ】図１Ｂは、開示技術の実施形態によるモデル分割装置の概要を示す構成ブロック図である。
【図２】図２は、開示技術の実施形態による図１Ａの平面検出ステップＳ１０１の概要を示すフローチャートである。
【図３】図３は、開示技術の一実施形態による三角形状の平面の法線方向と面積の算出の概要を示す説明図である。
【図４】図４は、三次元モデルにおける三角形状の平面の隣接関係の概要を示す説明図である。
【図５】図５は、開示技術の実施形態による子平面の合併可能な条件の概要を示す説明図である。
【図６】図６は、開示技術の実施形態による子平面の合併可能な他の条件の概要を示す説明図である。
【図７】図７は、開示技術の実施形態による平面の内部辺と境界辺の概要を示す説明図である。
【図８】図８は、開示技術の実施形態による三次元モデルの輪郭図形の概要を示す説明図である。
【図９】図９は、輪郭図形を複数の分離する子図形に分割する一例を示す説明図である。
【図１０】図１０は、切断面判定条件を例示する説明図である。
【図１１】図１１は、輪郭図形再分割部による処理の概要を示すフローチャートである。
【図１２】図１２は、輪郭図形再分割部の分割部による動作の概要を示すフローチャートである。
【図１３】図１３は、残りの頂点を分類する処理の概要を示すフローチャートである。
【図１４】図１４は、図１３のステップＳ１３０５の処理をさらに詳しく示すフローチャートである。
【図１５】図１５は、頂点分類結果に基づき子図形を作成する手順を示すフローチャートである。
【図１６】図１６は、開示技術の実施形態による平面を三角化する処理の概要を示すフローチャートである。
【図１７】図１７は、開示技術の他の実施形態による輪郭図形分割方法の概要を示すフローチャートである。
【図１８】図１８は、入力される三次元モデルの例を示す図である。
【図１９】図１９は、入力されるモデルから検出された平面の構造を示す説明図である。
【図２０】図２０は、三次元モデルの輪郭図形を抽出する説明図である。
【図２１】図２１は、輪郭図形を複数の子図形に分割する結果を示す説明図である。
【図２２】図２２は、図２１の４つの子図形から再構成された三次元モデルの結果を示す説明図である。
【図２３】図２３は、切断面の頂点及び切断面と直接接続する頂点の分類結果を示す説明図である。
【図２４】図２４は、頂点分類及びその新規追加頂点を示す説明図である。
【図２５】図２５は、図２４のモデルの分割結果を示す説明図である。
【発明を実施するための形態】
【００２３】
以下、図面を参照して開示技術の具体的な実施形態を説明する。図１Ａは開示技術の実施形態によるモデル分割方法の概要を示すフローチャートで、図１Ｂは開示技術の実施形態によるモデル分割装置の概要を示す構成ブロック図である。
【００２４】
図１Ａに示すように、開示技術の三次元モデル分割装置は、平面検出ステップＳ１０１と、輪郭図形抽出ステップＳ１０２と、輪郭図形分割ステップＳ１０３とを含む三次元モデル分割方法を実行する。三次元モデル分割装置が実行する平面検出ステップＳ１０１は、入力されるモデルのデータに基づき、該三角形モデルを含む全ての平面に関する情報を検出する。三次元モデル分割装置が実行する輪郭図形抽出ステップＳ１０２は、検出された三角形状の平面に関する情報に基づき、入力されるモデルに対応する輪郭線を得る。例えば、輪郭図形抽出ステップＳ１０２は、多角形からなる有界平面内部の接続線を削除して各平面の輪郭線を得る。そして、三次元モデルの頂点をノード、輪郭線を辺として三次元モデルの輪郭情報を図の形式で表現する。三次元モデル分割装置が実行する輪郭図形分割ステップＳ１０３は、入力されるモデルの幾何情報に基づき、輪郭図形を複数の重ならない子図形に分割した後に、子図形毎にそれぞれの対応する三角形メッシュで表現される三次元実体を再構成する。
【００２５】
開示技術の実施形態によれば、入力されるモデルは三角形メッシュで表現される。ここで、提供される三次元モデルは、基本データの要素に頂点の座標及び各三角形を構成する頂点のインデックスを有してもよい。これは、スキャニングによる点群（Point-Clouds）モデルは、予め三角化処理により三角形メッシュで表現される三次元モデルに変換することができるからである。また、各種のモデリングツールによるパラメータ化モデル、又は三角形ではない多角形メッシュで表現されるモデルも同様に、予め三角化処理により三角形メッシュで表現される三次元モデルに変換することができる。
【００２６】
一方、図１Ｂに示すように、開示技術の一実施形態による三次元モデル分割装置は、平面検出部１０１、輪郭図形抽出部１０２及び輪郭図形分割部１０３を有する。ここで、平面検出部１０１は、例えば法線方向算出部１０１１、子平面取得部１０１２及び平面取得部１０１３を有してもよい。また、輪郭図形抽出部１０２は、辺取得部１０２１、辺分類部１０２２及び辺削除部１０２３を有してもよい。
【００２７】
一実施形態では、輪郭図形分割部１０３は子図形取得部１０３１と再構成部１０３４を有する。また、別の実施形態では、輪郭図形分割部１０３は子図形取得部１０３１、穴処理部１０３２及び再構成部１０３４を有する。また、別の実施形態では、輪郭図形分割部１０３は子図形取得部１０３１、切断面処理部１０３３及び再構成部１０３４を有する。また、別の実施形態では、輪郭図形分割部１０３は子図形取得部１０３１、穴処理部１０３２、切断面処理部１０３３及び再構成部１０３４を有する。以下、図面を参照して三次元モデル分割装置の構成及び三次元モデル分割方法の処理手順を説明する。
【００２８】
[平面検出]
図１Ａに示すように、開示技術の一実施形態では、まずステップＳ１０１で、平面検出部１０１は三次元モデルを構成する平面を検出する。平面検出部１０１に三角形メッシュで表現される三次元モデルが入力されると、該モデルから頂点の三次元座標及び各三角形の頂点のインデックスを含むデータを提供する。これらのデータから、三角形を含む全ての平面が検出される。ここでの平面は有界平面のことであり、単一の多角形又は複数の多角形からなるものであってもよい。
【００２９】
図２は開示技術の三次元モデル分割装置が実行する図１Ａの平面検出ステップＳ１０１の概要を示すフローチャートである。図２に示すように、まず三次元モデル分割装置は、ステップＳ２０１で、三角形毎に法線方向に関する情報を算出する。次に、三次元モデル分割装置は、ステップＳ２０２で、三角形同士の接続情報を取得すると共に、互いに接続されかつ方向が共通又は相反する三角形を集めることにより、一連の子平面を得る。最後に、三次元モデル分割装置は、ステップＳ２０３で、条件を満足する子平面を集めて、最終的な平面を得る。以下、本フローに係る各ステップを説明する。
【００３０】
説明の便宜上、まず入力モデルの幾何データを示すいくつかの変数を定義する。Ｖｉ＝（ｘｉ，ｙｉ，ｚｉ），（ｉ＝１，．．．，ｎｖ）は、モデルの頂点に関する情報を示す。ただし、ｎｖは、頂点の数を示し、Ｖｉは、ｉ番目の頂点を示し、（ｘｉ，ｙｉ，ｚｉ）は、頂点の三次元座標を示す。
【００３１】
Ｆｉ＝（ｖｉ１，ｖｉ２，ｖｉ３），（ｉ＝１，．．．，ｎｆ）は、モデルの三角形状の平面に関する情報を示す。ただし、ｎｆは、三角形状の平面の数を示し、Ｆｉは、ｉ番目の三角形を示し、（ｖｉ１，ｖｉ２，ｖｉ３）は、三角形の３つの頂点のインデックスを示す。
【００３２】
ＮＤｉ＝（ｎｉｘ，ｎｉｙ，ｎｉｚ），（ｉ＝１，．．．，ｎｆ）は、モデルの三角形状の平面の法線方向を示す。ただし、ＮＤｉは、ｉ番目の三角形状の法線方向を示し、（ｎｉｘ，ｎｉｙ，ｎｉｚ）は、三角形の法線方向の３つの成分を示す。
【００３３】
まず、三次元モデル分割装置が実行するステップＳ２０１の法線方向算出ステップを説明する。該ステップは各三角形状の平面の法線方向を算出する。現在、三角形状の平面の法線方向の算出には様々な算出方法が開示されている。本実施形態では、例えば、法線方向算出部１０１１は、次の手順に従って所定の三角形状の平面の法線方向と面積を算出する。図３は開示技術の一実施形態による三角形状の平面の法線方向と面積の算出の概要を示す説明図である。三角形の頂点の順番をＡ→Ｂ→Ｃと仮定する。まず、（式１）によりベクトルＡＢとベクトルＡＣを算出する。
【００３４】
【数１】
2010186479.tif 000003
【００３５】
続いて、ベクトルＡＢとベクトルＡＣとのベクトル積を（式２）より算出する。
【００３６】
【数２】
2010186479.tif 000004
【００３７】
三角形の面積を（式３）より算出する。ただし、｜ベクトルＰ｜はベクトルＰのノルムを示す。
【００３８】
【数３】
2010186479.tif 000005
【００３９】
三角形の法線方向を（式４）より算出する。
【００４０】
【数４】
2010186479.tif 000006
【００４１】
なお、三角形の面積は他の方法で算出してもよい。例えば、三角形の３つの辺の長さをｌａ、ｌｂ、ｌｃとすると、三角形の面積は（式５）で得られる。ただし、ｓ＝（ｌａ＋ｌｂ＋ｌｃ）／２である。
【００４２】
【数５】
2010186479.tif 000007
【００４３】
全ての三角形に対して上記処理を終了すると、三角形毎に法線方向と面積が得られる。ここで、各三角形の法線方向のベクトルは共に単位ベクトルである。
【００４４】
次に、三次元モデル分割装置が実行するステップＳ２０２の子平面取得ステップでは、子平面取得部１０１２は各三角形状の平面を対象とし、それと接続されかつ方向が相同又は相反する三角形状の平面を集めて一連の平面を取得する。本明細書では、方向が相同するとは、両方向の差が所定の閾値以下であることを意味する。方向がほぼ相反するとは、両方向の差とπとの差が所定の閾値以下であることを意味する。
【００４５】
まず、三角形状の平面毎に、それと接続される三角形状の平面を求める。本実施形態では、２つの三角形状の平面は１本の共通した辺を有し、かつ２つの三角形状の平面における辺の方向が全く相反する場合、それらの平面が互いに接続されると判定する。この原則に基づき、各三角形Ｆｉの場合、それと接続される三角形状の平面が３つある。ここでＬｉ＝｛ｌｉ１，ｌｉ２，ｌｉ３｝，｛ｉ＝１，２，．．．，ｎｆ｝で示す。
【００４６】
図４は三次元モデルにおける三角形状の平面の隣接関係を模式的に示す説明図である。図４では、三角形Ｆと接続される３つの三角形状の平面をＬ１、Ｌ２、Ｌ３とする。三角形同士の相互接続関係は、上述した方法以外にも他の方法で判定してもよい。例えば、２つの三角形状の平面は共通した点を有する場合には、かかる平面が互いに接続されると判定する。この方法によれば、最終的な結果は、上述した方法による平面に関するデータと同じである。しかしながら、かかる法を採用した場合には、三角形毎に接続される三角形の数が増えるので、以降の処理における演算量が増大する。
【００４７】
次に、各三角形状の平面Ｆｉについて、これと接続される三角形状の平面それぞれとＦｉとがなす角度Ａｎｇｉ＝｛Ａｎｇｉ１，Ａｎｇｉ２，Ａｎｇｉ３｝を（式６）により算出する。ここで、ベクトルａ・ベクトルｂはベクトルａとベクトルｂとの内積を表す。図４の場合では、三角形状の平面Ｆと三角形状の平面Ｌ１、Ｌ２、Ｌ３とがなす角度はそれぞれ０、０とπ／２であることがわかる。
【００４８】
【数６】
2010186479.tif 000008
【００４９】
次に、適正な閾値を設定し、Ｆｉと接続され、かつ以下の条件を満足する三角形を集めて、三角形状の平面Ｆｉを対象とする子平面を取得する。ここでいう条件とは、三角形状の平面Ｆｉの法線方向と相同又は相反することを意味する、すなわち、Ａｎｇ＜＝ａｔｈ１又はＡｎｇ＞＝ａｔｈ２、ただし、ａｔｈ１の数値が０に近く、ａｔｈ２の数値がπに近い。図４の場合では、三角形Ｆを対象として取得された子平面は、Ｆ自体、Ｌ１及びＬ２という３つの三角形を含む。
【００５０】
全ての三角形に対して上記処理を終了すると、三角形状の平面毎にこれを対象として集めて作成した子平面に関する情報が得られ、ＳｕｂＰｉ＝｛Ｆｉ，ｓｐｉ１，．．．，ｓｐｉｊ｝，（ｉ＝１，２，．．．，ｎｆ，０≦ｊ≦３）と示す。
【００５１】
最後に、三次元モデル分割装置が実行するステップＳ２０３の平面取得ステップでは、平面取得部１０１３は以下の条件を満足する子平面を集めることにより、最終的な平面に関するデータを得る。前のステップで得られた各子平面からなる集合の大きさが１ないし４の範囲内であるが、このステップでは、子平面を合併するに伴って、子平面は広げられなくなるまで徐々に広げる。
【００５２】
２つの子平面の法線方向は相同又は相反すると共に、以下の条件のいずれかを満足すると、２つの子平面が一つの新しい子平面に合併される。全ての子平面がさらに合併できなくなるまで、この処理が繰り返される。
【００５３】
２つの子平面における三角形状の平面からなる集合に、共通する三角形が存在する。子平面を合併可能と判定する条件を図５に示す。図５は、開示技術の実施形態による子平面の合併可能な条件の概要を示す説明図である。図５に示すように、Ｆ１とＦ２それぞれを対象として作成した子平面には、共通する三角形Ｆが存在している。
【００５４】
２つの子平面の頂点からなる集合には、それぞれが２つの子平面に属する頂点をつなげる辺が少なくとも１本あり、かつ該辺が子平面の法線ベクトルに直交している。図５は子平面を合併可能とするという条件も模式的に示している。図５のように、Ｆ３とＦ４を対象として作成した子平面の頂点の間に接続を存在し、例えば２つの中空でない四角形をつなげる線が存在している。
【００５５】
２つの子平面の三角形状の平面からなる集合には、それぞれが２つの異なる子平面に属し、かつ相互接続される三角形が少なくとも１対ある。図６は子平面を合併可能とするという他の条件を模式的に示している。図６のように、Ｆ１とＦ２それぞれを対象として作成した子平面に、２つの隣接する三角形状の平面であるＦ１１とＦ２１が存在している。このステップが終了すると、最終的な平面に関するデータを得る。最終的な平面に関するデータは、平面毎に、平面の面積、平面の法線方向、含まれる三角形からなる集合及び頂点からなる集合というデータを含む。
【００５６】
上記の平面検出方法は一例であり、他の平面検出方法であってもよい。例えば次の方法も適用できる。すなわち、全ての三角形状の平面に対する処理が終了するまで、以下の処理が繰り返される。まず、非共線の３つの頂点(或いは任意の三角形の３つの頂点)を選択して平面を作成する。次に、残りの頂点が該平面に入るか否かを判定する。そして、各三角形状の平面が該平面に入るか否かを判定する。この平面検出方法は前述した方法と比較すると、演算量が多くなる。
【００５７】
[輪郭図形抽出]
図１Ａに戻り、以下、三次元モデル分割装置が実行する輪郭図形抽出ステップＳ１０２を説明する。このステップでは、輪郭図形抽出部１０２は平面検出ステップＳ１０１で検出した平面に関するデータからモデルの輪郭情報を抽出する。このために、まず、平面毎の輪郭情報を抽出することにより、モデル全体の輪郭情報を得る。
【００５８】
各平面について、以下の処理を実行して平面の輪郭情報を得る。まず、辺取得部１０２１は平面における全ての辺からなる集合を取得する。ここで、辺からなる集合は平面における各三角形の３本の辺を含む。図７は開示技術の実施形態による平面の内部辺と境界辺を示す説明図である。図７に示す平面に、１３本の辺が含まれる。なお、１本の辺を取得する度に、下記の辺分類部１０２２で分類してもよい。
【００５９】
次に、辺分類部１０２２は辺の種類を分類する。ここで、有界平面における辺は、内部辺と境界辺との２種類に分けられる。本実施例では、簡単な方法で辺の分類を行う。ある辺が該平面における２つの三角形に共通しているなら、該辺を内部辺に分類し、そうでなければ、該辺を境界辺に分類する。例えば、図７の三角形Ｆ１とＦ２とが共通する辺は内部辺であり、同じ理由により、他の数本の細線（点線を含む）も内部辺である。一方、太い線で示す辺は平面における一つの三角形のみに属するので、それらの辺は境界辺である。
【００６０】
最後に、辺削除部１０２３は平面における全ての内部辺を削除し、境界辺を保留する。それら境界辺同士は首尾接続でクローズド領域を構成する。それら境界辺は平面の輪郭情報を表している。
【００６１】
全ての平面について上記処理を終了すると、全ての平面の境界辺に基づいてモデルの輪郭を構成する。図８は三次元モデルの輪郭図形を示す。本実施形態では、輪郭情報を図形の形式で記述し、モデルの頂点（黒い四角形で示す）を図形のノードとし、モデルの輪郭線を図形の辺とする。輪郭図形抽出方法として、類似する凸包(convex hull)を求める方法を用いて、平面における各三角形からなる領域のエッジを決定することもできる。この方法によれば、比較的に簡単なモデルでも正確な輪郭を得られる。
【００６２】
[輪郭図形分割]
図１Ａに戻り、三次元モデル分割装置が実行するステップＳ１０３で輪郭図形を分割する。一実施形態では、このステップは、子図形取得部１０３１が入力される輪郭図形を複数の重ならない子図形に分割する子図形取得ステップと、再構成部１０３４が各子図形の輪郭を再構成する、すなわち、子図形毎に相応する三次元実体を再構成する再構成ステップとを含む。すなわち、本実施形態では、輪郭図形分割部１０３は子図形取得部１０３１と再構成部１０３４で構成される。
【００６３】
本実施形態では、ステップＳ１０３で、まず、子図形取得部１０３１は、全ての頂点（輪郭図形の頂点と入力されるモデルの頂点とは一対一に対応しているので、特に区分する必要がない時に、それらを頂点と言う）を複数の子集合に割り当てる。ここで、一つの子集合における頂点と他の子集合における頂点とは繋がらない。言い換えれば、相互接続される頂点を一つの集合に割り当て、相互接続されない頂点を異なる集合に割り当てる。詳しくは、例えば、以下の手順１〜６を実行する。
【００６４】
手順１では、子集合の数をｎ＝０に初期化し、ノードの処理マークをＰｉ＝０（ｉ＝１，２．．．，ｎＶ）にする。ここで、ｎＶはノードの数を示し、各頂点の処理マークを全て０に初期化する。つまり、すべての頂点が処理されていない旨を示す。
【００６５】
手順２では、未処理のノードがあれば、子図形の数をｎ＝ｎ＋１に更新し、一つの未処理のノードＮｏｄｅｎを始点としてランダムに選択し、一つの集合Ｓｎ＝｛Ｎｏｄｅｎ｝を初期化する。
【００６６】
手順３では、集合Ｓｎにおけるノードと接続され、かつ集合に存在しない全てのノードを集合Ｓｎに合併する。手順４では、Ｓｎが変わらないまで上記の手順３を繰り返す。手順５では、ノードの処理マークを更新し、Ｓｎに含まれる全てのノードの処理マークを１に設定する。つまり、それらのノードが処理された旨を示す。手順６では、全てのノードが処理されると、上記手順を終了し、そうでなければ、上記の手順２に移行する。
【００６７】
次に、各子集合について、該子集合におけるノード及びノード同士の辺により新しい子図形を構成する。図９に示す輪郭図形は、３つの子図形に分割され、各ノードを菱形、星型、円形に示し、そのうち、黒い四角形で示すノードはそれらの子図形を作成する３つの始点である。次に、再構成部１０３４は子図形毎に相応する三次元実体を再構成する。三次元実体を再構成することは、三次元実体モデルを再構成することであり、本明細書ではこれらを区分しないことにする。
【００６８】
[第２の輪郭図形分割方法]
開示技術の三次元モデル分割装置が実行する別の輪郭図形分割方法では、前記ステップＳ１０３は更に穴処理部１０３２で行われる穴処理ステップを含む。開示技術の一実施形態では、穴処理部１０３２は例えば穴判定部と穴モデル校正部を有する。それに対応して、穴処理ステップは穴判定ステップと穴モデル校正ステップを含む。
【００６９】
具体的には、三次元モデル分割装置は、穴判定ステップでは、まず、再構成部１０３４で再構成された各子図形の対応する三次元実体モデルは最初の三次元物体において一つの穴に対応するか否かを判定する。本実施形態では、穴であれば、面の方向が物体の内部に向かい、穴でなければ、面の方向が物体の外部に向かうという基本的な判断ルールが適用される。
【００７０】
この判断ルールを適用し、以下の手順により、入力される三次元実体モデルが穴であるか否かを判定する。手順１では、それぞれが物体の表面の外側に向かう平面の面積及び物体の表面の内側に向かう平面の面積を表す２つの変数Ｃｎｔ１＝０，Ｃｎｔ２＝０を初期化する。手順２では、該輪郭図形におけるすべての平面に対して上記の手順１を実行し、Ｃｎｔ１とＣｎｔ２の数値を更新する。
【００７１】
各平面ｐｌに対して以下の処理を実行する。平面ｐｌにおける頂点と接続されかつ該平面に存在しない頂点は全て該平面の一側にあるか否かを判定する。該平面の一側にない場合には、Ｃｎｔ１とＣｎｔ２の数値を更新しない。全て該平面の一側にあると判断すれば、さらにそれらの点が該平面のプラス側にあるか又はマイナス側にあるかを判定する。本実施形態では、それらの点が平面に対する関係を（式７）により判定する。
【００７２】
【数７】
2010186479.tif 000009
【００７３】
（式７）では、ベクトルｎＰは該平面の法線方向を、ベクトルＰは該平面における一つの点を、ベクトルＬはベクトルＰと接続されるが該平面ｐｌに存在しない一つの点をそれぞれ示す。ｄ＞０であれば、該点が該平面のプラス側にある、すなわち、平面と直接接続される頂点が該平面のプラス側にあると判定される。該平面が物体の表面の外方に向かうと、Ｃｎｔ１＝Ｃｎｔ１＋αｐｌに更新する。ここで、αｐｌは平面ｐｌの面積を示す。
【００７４】
ｄ＜０であれば、該点が該平面のマイナス側にある、すなわち、平面と直接接続される頂点が該平面のマイナス側にあると判定される。該平面が物体の表面の内方に向かうと、Ｃｎｔ２＝Ｃｎｔ２＋αｐｌに更新する。ここで、αｐｌは平面ｐｌの面積を示す。
【００７５】
全ての平面について上記処理を終了すると、Ｃｎｔ１とＣｎｔ２の大きさにより、該図形の対応する物体は穴であるか否かを決定する。Ｃｎｔ１＞Ｃｎｔ２であれば、入力される図形の対応する物体は穴ではないと判定される。一方、Ｃｎｔ１＜Ｃｎｔ２であれば、穴であると判定される。
【００７６】
次に、該実体が穴と判定されると、穴モデル校正部によりＭ１及びＭ２（穴モデル校正部により該実体の全ての三角形の法線方向を変更する。すなわち、各三角形の場合、法線方向を相反する方向に変更する。）における全ての三角形の法線方向を変更する。それによって、モデルをレンダリング・表示しやすいようにモデルの表面の方向を外方に向かわせる。
【００７７】
[第３の輪郭図形分割方法]
開示技術の三次元モデル分割装置が実行する別の輪郭図形分割方法では、輪郭図形分割部は子図形取得部１０３１、切断面処理部１０３３、再構成部１０３４を有する。言い換えれば、本実施形態のステップＳ１０３は、子図形取得ステップと、再構成ステップと、切断面処理ステップとを含む。子図形取得ステップでは、子図形取得部１０３１が入力された輪郭図形を複数の重ならない子図形に分割する。再構成ステップでは、再構成部１０３４が各子図形の対応する三次元実体を再構成する、すなわち、子図形毎に相応する三次元実体を再構成する。切断面処理ステップでは、再構成部１０３４で再構成された各子図形の対応する三次元実体に切断面が含まれるか否かを判定し、切断面が含まれれば、切断面処理を行う。
【００７８】
本実施例では、切断面処理部１０３３は、入力される輪郭図形における全ての切断面を判定する切断面判定部と、切断面判定部で判定された切断面に基づき、該切断面を含む輪郭図形を分割し新しい子図形を得る輪郭図形再分割部とを有する。輪郭図形再分割部は分割部と、分割部で分割された子図形が適正であるか否かを判定する適正判定部とをさらに有する。
【００７９】
以下、まず切断面処理部１０３３による切断面判定基準を説明し、一実施例では、一つの平面を切断面と判定する最も重要な条件は、現在の平面上の頂点を除き、他の頂点が現在の平面の両側に分布されることである。ある平面において、平面上の頂点を除き、他の頂点が共に平面の同一の側にあれば、該平面を切断面ではないと判定する。
【００８０】
図１０は、切断面判定条件を例示する説明図である。図１０に示す輪郭図形の場合では、黒い平面を例にする。この平面には、円形で示す２つの頂点及び四角形で示す２つの頂点、合計４つの頂点がある。四角形で示す２つの頂点については、それぞれと接続されかつ黒い平面に属しない頂点が１つあり、この２つの頂点が黒い平面のプラス側にある。一方、円形で示す２つの頂点については、それぞれと接続されかつ黒い平面に属しない頂点が１つあり、この２つの頂点が黒い平面のマイナス側にある。以上が、該平面が切断面としての最も重要な条件である。
【００８１】
上述した最も重要な条件に加えて、以下（１）〜（３）という補助条件を設定してもよい。
（１）該平面の面積とモデル表面積との比がある設定される閾値を下回ってはいけない。閾値は一般的には１以下である。
（２）平面上のいかなる頂点も、それと接続される頂点同士の辺と平面とがなす角度は、ある設定される閾値を下回ってはいけない。閾値は一般的には０以上である。
（３）平面上のいかなる頂点も、これと接続される頂点同士の長さはある設定される閾値を下回ってはいけない。閾値は一般的には０を超える。更に、経験に基づき、新しい条件を選択又は設定してもよい。
【００８２】
以下、輪郭図形再分割部の処理を説明する。前述したように、輪郭図形再分割部は取得された切断面により、入力される輪郭図形を複数の子図形に分割する。入力される輪郭図形は、一般的に、一つの以上の切断面を有する。本実施例では、入力される輪郭図形を複数の子図形に分割しきるまで各切断面を順次に処理する。別の実施例では、全ての平面に対する処理が終了するまで処理する、すなわち、全ての切断面を処理したが、入力された輪郭図形がまだ分割されていない場合には、入力された輪郭図形を分割をしないまま処理を終了する。
【００８３】
図１１は輪郭図形再分割部による処理の概要を示すフローチャートである。図１１に示すように、本実施例では、輪郭図形再分割部による処理は主に、以下の２つの処理からなる。
（１）ある選定された切断面により、入力される輪郭図形を複数の子図形に分割する。
（２）分割結果が適正かどうかを判定する。
【００８４】
また、切断面の処理順序について、以下（１）〜（３）のルールを適用することができる。もちろん、処理中では、経験に基づきルールを選択する又は新しいルールを設定することができる。
（１）切断面の面積により順序付けて、面積が広い切断面の処理を優先する。
（２）切断面の頂点の数により順序付けて、頂点の数が多い切断面の処理を優先する。
（３）切断面の外部から切断面と直接接続される辺と切断面とがなす角度により順序付けて、角度が大きい平面の処理を優先する。
【００８５】
図１１に示すように、まず、三次元モデル分割装置は、ステップＳ１１０１で、変数ｉをｉ＝１に初期化し、最初に選定された切断面から処理を開始する。次に、三次元モデル分割装置は、ステップＳ１１０２で、ｉ番目の切断面候補により、入力される輪郭図形を分割する。次に、三次元モデル分割装置は、ステップＳ１１０３で、分割結果が適正かどうかを判定し、適正であれば（ステップＳ１１０４、Ｙｅｓ）、ステップＳ１１０６で分割結果を出力する。一方、三次元モデル分割装置は、分割結果が適正でなければ（ステップＳ１１０４、Ｎｏ）、ステップＳ１１０５で、次の切断面候補をｉで示す。すなわち、三次元モデル分割装置は、ｉ＝ｉ＋１とする。次に、三次元モデル分割装置は、ステップＳ１１０７で、全ての切断面が処理されたか否かを判定する。具体的には、三次元モデル分割装置は、ｉは切断面の数ｎより大きいか否かを判定する。全ての切断面が処理されたら（ステップＳ１１０７、Ｙｅｓ）、三次元モデル分割装置は、ステップＳ１１０８で分割が成功しない旨の通知や報告を出力する。例えば、三次元モデル分割装置は、通知や報告は、テキストや音声や映像の形態で出力される。まだ全ての切断面が処理されていなければ（ステップＳ１１０７、Ｎｏ）、三次元モデル分割装置は、ステップＳ１１０２に戻る。
【００８６】
開示技術の実施形態では、三次元モデル分割装置は、分割されるモデル又は子図形に複数の切断面が含まれる場合に、該モデルに対応する輪郭図形を複数の子図形に適正に分割するまでそれらの切断面を順次に処理する。適正判定を通して、全ての切断面候補による分割結果が共に適正ではなければ、分割されるモデルは、分割をあきらめ、そのまま最終的な分割結果の一部として出力する。また、ある切断面の場合では、分割結果が適正ではなければ、該切断面による分割結果を放棄すると共に、その他の切断面により入力される輪郭図形の分割を行う。
【００８７】
以下、選定された切断面により輪郭図形を分割する処理を説明する。図１２は輪郭図形再分割部における分割部による動作を示すフローチャートである。説明の便宜上、次のことを仮定する。切断面をＣｐｉ（ｉ＝１，２，．．．，ｎＣ）とする。ｎＣは検出された切断面の数を示し、該切断面には、切断面における頂点情報ＰＣｉ＝｛ｐｖｉ１，ｐｖｉ２，．．．，ｐｖｉｎ｝と切断面の法線方向ベクトルＮＣ、及び場合によって切断面の面積αＣｉなどのデータ情報が含まれる。また、Ｃ１とＣ２は、切断面にある２種類の頂点からなる集合を示す。また、Ｓ１とＳ２は、切断面の外部にある２種類の頂点からなる集合を示す。また、ｐｒｏデータ配列は、点の処理マークを示す。
【００８８】
本実施例では、まず、分割部は、切断面の左側（一側）にある点を探し、次に切断面の右側（他側）にある点を探す。分割部は、左側の点及び切断面にある点を複数の子図形にカプセル化し、右側の点及び切断面にある点を複数の子図形にカプセル化する。
【００８９】
別の実施例では、輪郭図形再分割部は、輪郭を複数の子図形に適正に分割するまで各切断面候補を順次に処理する。ある所定の切断面について、まず、切断面にある頂点及び切断面にある頂点と直接接続される頂点を含む切断面付近の頂点を、２つの子集合に割り当てる。次に、切断面付近の頂点以外の頂点について、それら頂点を２つの子集合に割り当てる。例えば、それらの頂点と２つの子集合における頂点との接続関係、及びそれらの頂点と切断面との位置関係に基づき、２つの子集合における頂点同士に切断面に亘る接続がないように割り当てる。
【００９０】
以下、図１２を参照し、本実施例による分割部の処理を詳しく説明する。図１２に示すように、まず、分割部は、ステップＳ１２０１で、頂点の処理マークをｐｒｏｋ＝ｆａｌｓｅ，ｋ＝１，２，．．．，ｎｋに初期化する。ここで、ｎｋは輪郭図形における頂点の数であり、全ての頂点がまだ処理されていないことを表す。
【００９１】
次に、分割部は、ステップＳ１２０２で、切断面にある頂点を分類する。分割部は、ステップＳ１２０２では、切断面にある各頂点と切断面以外の頂点との接続関係により、切断面にある頂点を第１向き頂点と第２向き頂点との２種類に分類し、それぞれをＣ１とＣ２で表す。Ｃ１＝｛ベクトルＣ１１，ベクトルＣ１２，．．．，ベクトルＣｎ１｝であり、Ｃ２＝｛ベクトルＣ２１，ベクトルＣ２２，．．．，ベクトルＣｎ２｝である。ここで、ｎ１、ｎ２は２つの集合の大きさを示す。このために、分割部は、次の３つの手順を実行する。
【００９２】
分割部は、手順１では、第１向き集合Ｃ１と第２向き集合Ｃ２という２つの空集合を初期化する。分割部は、手順２では、切断面にある各頂点を順次処理して分類する。切断面にある一つの頂点をベクトルＰとし、該頂点と直接接続されるが該切断面に入らない頂点からなる集合をＳ＝｛ベクトルＬ１，ベクトルＬ２，．．．，ベクトルＬｎｌ｝とする。ここで、ｎｌは点の数である。集合Ｓにおける各頂点ベクトルＬｊ（ここで、ｊ＝１，２，．．．，ｎｌ）について、辺ベクトルＰ→ベクトルＬｊと切断面の法線方向との内積ｄｊ＝（ベクトルＬｊ−ベクトルＰ）・ベクトルＮＣを算出する。ｄｊは０より大きければ、該頂点を第１向き集合Ｃ１に入れる一方、ｄｊは０より小さければ、該頂点を第２向き集合Ｃ２に入れる。すなわち、一部の頂点が２つの集合に包含される可能性がある。
【００９３】
分割部は、手順３では、切断面にある各頂点の処理マークをそれら頂点が処理された旨を示すｔｒｕｅに更新する。図１０に示すように、黒い切断面にある４つの頂点が２種類に分けられ、そのうち、Ｃ１は四角形で示す２つの頂点を、Ｃ２は円形で示す２つの頂点をそれぞれ含む。
【００９４】
次に、分割部は、ステップＳ１２０３で、切断面にある頂点と直接接続されるが該切断面に入らない頂点を、第１向き側頂点と第２向き側頂点に分類する。このステップでは、平面における頂点と直接接続されるが切断面に入らない頂点は２種類に分けられ、それぞれをＳ１とＳ２で表す。Ｓ１＝｛ベクトルｓ１１，ベクトルｓ１２，．．．，ベクトルｓｓｌ｝であり、Ｓ２＝｛ベクトルｓ２１，ベクトルｓ２２，．．．，ベクトルｓｓ２｝である。ここで、ｓ１、ｓ２はそれぞれ２つの集合の大きさを表す。分割部は、次の手順によりこの２つの頂点からなる集合を得られる。
【００９５】
分割部は、手順１では、第１向き側集合Ｓ１と第２向き側集合Ｓ２という２つの空集合を初期化する。分割部は、手順２では、集合Ｃ１における各頂点ベクトルｃ１ｉ（ここで、ｉ＝１，２，．．．，ｎｌ）を順次に処理する。例えば、分割部は、頂点ベクトルｃ１ｉについて、頂点ベクトルｃ１ｉと接続されるが該切断面に属しない頂点からなる集合をＴ１＝｛ベクトルｔ１１，ベクトルｔ１２，．．．，ベクトルｔｔｌ｝とする。ここで、ｔｌは、点の数を表す。Ｔ１の各頂点ベクトルｔ１ｊ（ここで、ｊ＝１，２，．．．，ｔｌ）を順次に処理し、辺ベクトルｃ１ｉ→ベクトルｔ１ｊと切断面の法線方向との内積がプラスであり、かつ集合Ｓ１にベクトルｔ１ｊが含まなければ、ノードベクトルｔ１ｊを集合Ｓ１に入れる。
【００９６】
分割部は、手順３では、集合Ｃ２における各頂点ベクトルｃ２ｉ（ここで、ｉ＝１，２，．．．，ｎ２）を順次に処理する。分割部は、頂点ベクトルｃ２ｉについて、頂点ベクトルｃ２ｉと接続されるが該切断面に属しない頂点からなる集合をＴ２＝｛ベクトルｔ２１，ベクトルｔ２２，．．．，ベクトルｔｔ２｝とする。ここで、ｔ２は、点の数を表す。Ｔ２の各頂点ベクトルｔ２ｊ（ここで、ｊ＝１，２，．．．，ｔｌ）を順次に処理し、辺ベクトルｃ２ｉ→ベクトルｔ２ｊと切断面の法線方向との内積がプラスであり、かつ集合Ｓ２にベクトルｔ２ｊが含まなければ、ノードベクトルｔ２ｊを集合Ｓ２に入れる。
【００９７】
分割部は、手順４では、集合Ｓ１と集合Ｓ２における各頂点の処理マークをそれらの頂点が処理された旨を示すｔｒｕｅに更新する。なお、上記４つの手順は必ずしも説明の順に実行されるものではなく、幾つかの手順は同時に実行されてもよく、また、順序通りに実行される場合でも、実行される順序を説明の順とは変更してもよい。
【００９８】
図１０に示すように、黒い切断面にある４つの頂点と直接接続される４つの頂点が２種類に分けられる。そのうち、集合Ｓ１は２つの頂点を含み、図１０に示すように、この２つの頂点は破線により円形で示す２つの頂点と接続される。一方、集合Ｓ２は２つの頂点を含み、この２つの頂点は実線により四角形で示す２つの頂点と接続される。次に、分割部は、ステップＳ１２０４で、残りの頂点を分類する。最後に、分割部は、ステップＳ１２０５で、分類の結果に基づき、輪郭図形を分割する。
【００９９】
分割部は、ステップＳ１２０４において、頂点がどの側にあるかに基づき、頂点を直接分類することで実施形態を簡略化することができる。この実施形態は構造の簡単なモデルに適用できる。以下、ステップＳ１２０４の簡略化した実施形態の処理手順を詳しく説明する。分割部は、ステップＳ１２０４では、残りの頂点を分類する。ここで残りの頂点は、未処理の頂点、すなわち、切断面の外部にあり、かつ切断面にある頂点と接続される辺がない部分の頂点を意味する。かかる処理には、三次元モデル分割装置は、図１３に示す各ステップを実行する。図１３は残りの頂点を分類する処理の概要を示すフローチャートである。
【０１００】
図１３に示すように、まず、三次元モデル分割装置は、ステップＳ１３０１で、全ての未処理頂点を２つの集合Ｘ１とＸ２に割り当てる。ここで、Ｘ１は集合Ｓ１の頂点を始点として展開して得られる点からなる集合を有する。また、Ｘ２は集合Ｓ２の頂点を始点として展開して得られる点からなる集合を有する。このような（Ｘ１とＸ２）２つの集合を得るために、下記の手順１〜４を実行する。手順１では、Ｘ１とＸ２という２つの空集合を初期化する。手順２では、集合Ｓ１の頂点と接続され、かつ処理されない頂点をすべて集合Ｘ１に分類し、集合Ｓ２の頂点と接続され、かつ処理されない頂点をすべて集合Ｘ２に分類する。手順３では、Ｘ１が変更しなくなるまで、Ｘ１の頂点を始点として展開し、Ｘ１の頂点と接続され、かつ処理されない頂点をすべてその内部に包含する。また、Ｘ２が変更しなくなるまで、Ｘ２の頂点を始点として展開し、Ｘ２の頂点と接続され、かつ処理されない頂点をすべてその内部に包含する。手順４では、Ｘ１とＸ２の各頂点が１回しか現れないようにＸ１とＸ２を処理する。
【０１０１】
次に、三次元モデル分割装置は、ステップＳ１３０２で、集合Ｘ１とＸ２との共通の点を求めて集合ＸＣ＝Ｘ１∩Ｘ２＝｛ベクトルｘｃ１，ベクトルｘｃ２，．．．，ベクトルｘｃｎｃ｝を構成する。ここで、ｎｃは共通の点の数を表す。
【０１０２】
次に、三次元モデル分割装置は、ステップＳ１３０３で、集合ＸＣは空であるか否かを判定する。具体的には、三次元モデル分割装置は、ｎｃは０であるか否かを判定する。ＸＣは空であると判定されると（ステップＳ１３０３、Ｙｅｓ）、三次元モデル分割装置は、ステップＳ１３０４に移行し、集合Ｘ１とＸ２それぞれを第１向き側集合Ｓ１と第２向き側集合Ｓ２に合併する。一方、ＸＣは空ではないと判定されると（ステップＳ１３０３、Ｎｏ）、三次元モデル分割装置は、ステップＳ１３０５に移行し、集合ＸＣから頂点候補を求めると共に、未処理頂点を分類してから、ステップＳ１３０１に移行する。三次元モデル分割装置は、全ての頂点について上記処理を終了するまで上記手順を繰り返す。
【０１０３】
三次元モデル分割装置が実行するステップＳ１３０５は、共通の点からなる集合ＸＣから適正の頂点を求め、未処理頂点を更に分類する。このために、本実施形態では、図１４に示す手順によって処理される。図１４は、図１３のステップＳ１３０５の処理を詳しく示す図である。図１４に示すように、まず、三次元モデル分割装置は、ステップＳ１５０１で集合ＸＣから全ての頂点候補からなる集合を求める。次に、三次元モデル分割装置は、ステップＳ１５０２で集合候補から最適な頂点を求め、最後にステップＳ１５０３で、ステップＳ１５０２で選定された頂点により適当な処理を実行し、未処理頂点を更に分類する。つまり、共通の頂点があれば、すなわち、ＸＣが空でなければ、集合Ｘ１と集合Ｘ２の頂点同士に切断面に亘る接続が存在することを意味する。したがって、三次元モデル分割装置は、それら頂点を求めると共に、新しい頂点を適当に追加し、残りの頂点を継続分類することにより、それら頂点を２つの子集合に割り当てる。
【０１０４】
以下、三次元モデル分割装置が実行する全ての頂点候補からなる集合ＣＶを求めるステップＳ１５０１の処理を詳しく説明する。三次元モデル分割装置が実行するこのステップは、以降の処理に備えるステップである。三次元モデル分割装置は、集合ＸＣから全ての頂点候補からなる集合を求め、求められた集合をＣＶ＝｛ベクトルｃｖ１，ベクトルｃｖ２，．．．，ベクトルｃｖｎｃ｝で表す。ここで、ｎｃは頂点候補の数を示す。本実施形態による方法では、三次元モデル分割装置は、ある特別な条件を満足する頂点のみを頂点候補とする。集合ＸＣにおけるいずれかの頂点ベクトルＰを例にし、それと接続される頂点からなる集合をＬ＝｛ベクトルＬ１，ベクトルＬ２，．．．，ベクトルＬｎｌ｝とする。該頂点がノード候補であるか否かを判定するために、三次元モデル分割装置は、切断面における頂点からいずれかの頂点ベクトルＣを補助ノードと選択する。次に、三次元モデル分割装置は、ｄとｄｋを（式８）より算出する。
【０１０５】
【数８】
2010186479.tif 000010
【０１０６】
ここで、｜ベクトルａ｜はベクトルａのノルムを示し、ベクトルａ・ベクトルｂは２つのベクトルの内積をそれぞれ示す。頂点ベクトルＰは、以下に示す３つの条件のうち、いずれか１つを満足した場合に、頂点候補だと考えられる。
【０１０７】
（条件１）｜ｄ｜≦εとし、εは０に近い値であり、かつ∋ｋ、ｄｋ＞０又はｄｋ＜０を満足する条件である。すなわち、条件１では、頂点ベクトルＰは切断面にあり、該点を境にし、それと接続されかつ切断面の両側にある各頂点を２つの集合に割り当てる。
【０１０８】
（条件２）｜ｄ｜＞λかつｄ＞０とし、λは０以上１以下の値であり、かつ∋ｋ、｜ｄｋ｜≦ε又はｄｋ＜０かつ｜ｄｋ｜＞λを満足する条件である。すなわち、条件２では、頂点ベクトルＰは切断面のプラス側にあり、該点と接続される頂点には切断面のマイナス側にある頂点が存在する。この場合、いくつかの頂点を追加して分類しなければならない。それら頂点は切断面に亘る接続線と切断面との交点であり、それら交点を境にし、ベクトルＰ及びベクトルＰと接続されかつ切断面のマイナス側にある頂点を２つの集合に割り当てる。
【０１０９】
（条件３）｜ｄ｜＞λかつｄ＜０とし、λは０以上１以下の値であり、かつ∋ｋ、｜ｄｋ｜≦ε又は｜ｄｋ｜＞λかつｄ＞０を満足する条件である。すなわち、条件３では、ベクトルＰは切断面のマイナス側にあり、該点と接続される頂点には切断面のプラス側にある頂点が存在する。この場合、いくつかの頂点を追加して分類しなければならない。それら頂点は切断面に亘る接続線と切断面との交点であり、それら交点を境にし、ベクトルＰ及びベクトルＰと接続されかつ切断面のプラス側にある頂点を２つの集合に割り当てる。
【０１１０】
以下、三次元モデル分割装置が実行する集合候補から最適な頂点を選択するステップＳ１５０２の処理を詳しく説明する。三次元モデル分割装置が実行するこのステップは集合候補から最適な一つの頂点を求め、以降の処理に備えるステップである。本実施形態では、Ｓ＝Ｓ１∪Ｓ２の頂点から最も距離が近い頂点ベクトルｓｐが最適な頂点とする。本実施形態では、三次元モデル分割装置は、輪郭図形の全ての辺の長さを１とし、頂点間の最も短い経路で２つの頂点間の距離を測定する。三次元モデル分割装置は、下記の手順により頂点ベクトルｓｐを決定する。
【０１１１】
三次元モデル分割装置は、ＣＶの各頂点ベクトルｃｖｋ（ここで、ｋ＝１，２，．．．，ｎｃ）から集合Ｓまでの距離を算出する。ここで、三次元モデル分割装置は、ベクトルｃｖｋからＳまでの距離を（式９）により算出する。ここで、ｄｉｓ（ベクトルｃｖｋ，ベクトルｓ）は頂点ベクトルｃｖｋからベクトルｓまでの最も短い距離を表す。
【０１１２】
【数９】
2010186479.tif 000011
【０１１３】
ベクトルｓｐを（式１０）により決定する。
【０１１４】
【数１０】
2010186479.tif 000012
【０１１５】
以下、三次元モデル分割装置が実行するステップ１５０３で選定された頂点について、未処理頂点の種類情報の決定を説明する。選定された頂点候補は上記の３つの条件のいずれかを満足する可能性がある。三次元モデル分割装置は、異なる条件を満足する頂点に対して異なる処理を実行する。処理手順の説明に先立って、選択された頂点をベクトルＰとし、それと接続される頂点からなる集合をＬ＝｛ベクトルＬ１，ベクトルＬ２，．．．，ベクトルＬｎｌ｝とする。次に、三次元モデル分割装置は、算出されたｄ及びｄｋ（ここで、ｋ＝１，２，．．．，ｎｌ）により下記の処理１〜３を実行する。
【０１１６】
（処理１）頂点が条件１を満足すれば、三次元モデル分割装置は、下記の動作をする。
（１）三次元モデル分割装置は、頂点ベクトルＰを集合Ｃ１とＣ２に追加し、該ノードの点処理マークをｔｒｕｅに更新する。
（２）三次元モデル分割装置は、これと接続される各頂点を分類する。ここで、ｋ＝１，２，．．．，ｎｌである。ｉｆ（｜ｄｋ｜≦ε）の場合には、三次元モデル分割装置は、頂点ベクトルｃｖｋを集合Ｃ１、Ｃ２に追加する。ｅｌｓｅｉｆ（ｄｋ＜０）の場合には、三次元モデル分割装置は、頂点ベクトルｃｖｋを集合Ｓ２に追加する。ｅｌｓｅの場合には、三次元モデル分割装置は、頂点ベクトルｃｖｋを集合Ｓ１に追加する。
（３）三次元モデル分割装置は、集合Ｌの各頂点の処理マークをｔｒｕｅに更新する。
【０１１７】
（処理２）頂点が条件２を満足すれば、三次元モデル分割装置は、下記の動作をする。
（１）三次元モデル分割装置は、頂点ベクトルＰを集合Ｓ１に追加し、該ノードの点処理マークをｔｒｕｅに更新する。
（２）三次元モデル分割装置は、これと接続される各頂点を分類する。ここで、ｋ＝１，２，．．．，ｎｌである。ｉｆ（｜ｄｋ｜≦ε）の場合には、三次元モデル分割装置は、頂点ベクトルｃｖｋを集合Ｃ１、Ｃ２に追加する。ｅｌｓｅｉｆ（ｄｋ＜０）の場合には、三次元モデル分割装置は、頂点ベクトルｃｖｋを集合Ｓ２に追加する。三次元モデル分割装置は、辺ベクトルＰ→ベクトルｃｖｋと切断面との交点ベクトルｃを算出する。三次元モデル分割装置は、ベクトルＰ、ベクトルｃｖｋ、ベクトルｃの間の接続関係及び関係する平面情報を更新する。三次元モデル分割装置は、ベクトルｃを集合Ｃ１、Ｃ２に追加する。
（３）三次元モデル分割装置は、集合Ｌの各頂点の処理マークをｔｒｕｅに更新する。
【０１１８】
（処理３）頂点が条件３を満足すれば、三次元モデル分割装置は、下記の動作をする。
（１）三次元モデル分割装置は、頂点ベクトルＰを集合Ｓ２に追加し、該ノードの点処理マークをｔｒｕｅに更新する。
（２）三次元モデル分割装置は、これと接続される各頂点を分類する。ここで、ｋ＝１，２，．．．，ｎｌである。ｉｆ（｜ｄｋ｜≦ε）の場合には、三次元モデル分割装置は、頂点ベクトルｃｖｋを集合Ｃ１、Ｃ２に追加する。ｅｌｓｅｉｆ（ｄｋ＞０）の場合には、三次元モデル分割装置は、頂点ベクトルｃｖｋを集合Ｓ１に追加する。三次元モデル分割装置は、辺ベクトルＰ→ベクトルｃｖｋと切断面との交点ベクトルｃを算出する。三次元モデル分割装置は、ベクトルＰ、ベクトルｃｖｋ、ベクトルｃの間の接続関係及び関係する平面情報を更新する。三次元モデル分割装置は、ベクトルｃを集合Ｃ１、Ｃ２に追加する。
（３）三次元モデル分割装置は、集合Ｌの各頂点の処理マークをｔｒｕｅに更新する。
【０１１９】
以上からわかるように、処理２と処理３で説明した処理手順は共に接続及び関係する平面情報を更新する必要がある。三次元モデル分割装置は、選定されたノード候補をベクトルＰとし、ベクトルＰと接続されるｋ番目の頂点をベクトルｃｖｋとし、ｄ、ｄｋの記号が相反であれば、辺ベクトルＰ→ベクトルｃｖｋと切断面との交点ベクトルｃを算出する。そして、三次元モデル分割装置は、交点を新規のノードとして輪郭図形に追加すると共に、接続情報及び関係する平面情報を更新する。
【０１２０】
まず、三次元モデル分割装置は、次の手順に従って接続情報を更新する。
（１）三次元モデル分割装置は、頂点ベクトルＰとベクトルｃｖｋの間のつながりをカットする。
（２）三次元モデル分割装置は、ベクトルＰとベクトルｃ，ベクトルｃｖｋとベクトルｃの間のつながりを加える。
（３）三次元モデル分割装置は、ベクトルＰとベクトルｃｖｋと共に接続される全ての頂点を求め、それら頂点とベクトルｃの間のつながりを加える。
【０１２１】
次に、三次元モデル分割装置は、以下の処理に従って関係する平面情報データを更新する。まず、三次元モデル分割装置は、新規追加された頂点ベクトルｃを切断面に追加する。次に、三次元モデル分割装置は、ベクトルＰ及びベクトルｃｖｋを共に含む全ての平面を求め、それら平面に頂点ベクトルｃを追加する。
【０１２２】
図１３と図１４に示す手順を併せて参照して、一つの頂点候補の処理が終了し、関係情報の更新が終了する度に、三次元モデル分割装置は、ステップＳ１３０１で集合Ｘ１とＸ２を取得し、Ｘ１とＸ２には共通の点があるか否かを判定する。共通の点があれば、三次元モデル分割装置は、ステップＳ１３０５で、全ての頂点の処理を終える又はＸ１とＸ２には共通の点がないまで分割を続行する。三次元モデル分割装置が実行する前記ステップＳ１２０４の処理により、平面上の頂点がＣ１とＣ２の２種類に分けられ、平面の外部にあるノードがＳ１とＳ２の２種類に分けられる。
【０１２３】
以下、三次元モデル分割装置が実行するステップＳ１２０５を詳しく説明する。図１５は頂点分類結果に基づき子図形を作成する手順の概要を示すフローチャートである。三次元モデル分割装置は、ステップＳ１２０５で、まずＣ１とＳ１を合併して第１分割部分の点集合ＣＳ１を得て、Ｃ２とＳ２を合併して第２分割部分の点集合ＣＳ２を得る。次に、三次元モデル分割装置は、図１５に示すステップに従って、２つの点集合ＣＳ１、ＣＳ２を個別に処理して、複数の新しい子図形を得る。図１５では、（Ｃ、Ｓ、ＣＳ）は（Ｃ１、Ｓ１、ＣＳ１）又は（Ｃ２、Ｓ２、ＣＳ２）のいずれかを示す。
【０１２４】
図１５に示すように、まず、三次元モデル分割装置は、ステップＳ１６０１で、ＣＳにおける頂点を複数の子集合に割り当てる。このステップで、まず、ＣＳの頂点をノードとし、切断面に属しない頂点同士のつながりにより、切断面における頂点と切断面の外部にある頂点との接続線を辺とし、一つの構造図Ｇを構成する。つまり、構造図Ｇには切断面における各頂点同士の接続線が含まれない。
【０１２５】
次に、子図形取得部１０３１によって、構造図Ｇを複数の分離する子図形に分割し、ＣＳの全ての頂点を複数の子集合に分割する。分割された子集合をＳｕｂＳｉ＝｛ベクトルｐｉ１，ベクトルｐｉ２，．．．，ベクトルｐｎｉ｝（ｉ＝１，２，．．．，ｎｓ）で表す。ここで、ｎｓは、子集合の数を示し、ｎｉはｉ番目の子集合の頂点の数を示す。これに伴って、ＳｕｂＣｉ＝｛ベクトルｐｃｉ１，ベクトルｐｃｉ２，．．．，ベクトルｐｃｎｉ｝、ＳｕｂＰＳｉ＝｛ベクトルｐｓｉ１，ベクトルｐｓｉ２，．．．，ベクトルｐｓｎｉ｝が得られる。ここで、ｃｉはｉ番目の子図形の切断面にある頂点の数を示し、ｓｉはｉ番目の子図形の切断面の外部にある頂点の数を示す。
【０１２６】
次に、三次元モデル分割装置は、ステップＳ１６０２及びステップＳ１６０３で、子集合毎に、切断面に属する頂点同士の接続関係を更新して、新しい子図形を構成する。所定の切断面によって、入力される輪郭図形の頂点はＣＳ１とＣＳ２の２種類に分けられ、各種頂点は共に複数の部分からなるので、その接続情報に基づき、更に複数の子図形に分割する必要がある。このような場合は、実際にも存在し、例えば、切断面の上方に２つ以上の直方体が存在する場合などが挙げられる。
【０１２７】
三次元モデル分割装置が実行するこのステップは、子集合ＳｕｂＳｉ（ｉ＝１，２，．．．，ｎｓ）毎に相応する図Ｇｉを作成する。このために、三次元モデル分割装置は、まず、ＳｕｂＳｉの各頂点をノードとしてＧｉに追加し、ＳｕｂＳｉの各頂点の間にある辺をＧｉに追加する。
【０１２８】
次に、三次元モデル分割装置は、下記の処理より、ＳｕｂＣｉの頂点の間に必要とする辺を追加することにより、有界な閉平面を構成する。まず、三次元モデル分割装置は、ＳｕｂＣｉと共通の頂点を有し、かつ、この数が２以上である全ての平面（切断面を含まない）を求め、求めた平面をｐｌｋ（ここで、ｋ＝１，２，．．．，ｎｋ）で表し、ｎｋはそのような平面の数を表す。
【０１２９】
次に、三次元モデル分割装置は、各平面ｐｌｋ（ここで、ｋ＝１，２，．．．，ｎｋ）について、該平面とＳｕｂＣｉと共通の点が２つあれば、それら点をベクトルｃ１とベクトルｃ２で表す。この対となる頂点の間にそれらをつなげる辺がなければ、三次元モデル分割装置は、その辺を構造図Ｇｉに追加する。
【０１３０】
適正判定部は図形を分割して得る一連の子図形が適正であるか否かを判定する。本実施形態では、各子図形が三次元実体を作成する条件を有するか否かを判定するルールを次のように設定する。ある子図形Ｇを例にして、該子図形の全ての頂点を含む平面をＰＬ＝｛ｐｌ１，ｐｌ２，．．．，ｐｌｋ｝（ここで、ｋ＝１，２，．．．，ｎｐ）とする。ここで、ｎｐは平面の数を示す。ＰＶ＝｛ｖ１，ｖ２，．．．，ｖｋ｝（ここで、ｋ＝１，２，．．．，ｎｖ）は頂点を示す。Ｇは下記の条件１〜４を全部満足して始めて、該子図形は三次元実体を作成する条件を有するようになる。
【０１３１】
（条件１）頂点の数は４以上、平面の数は４以上である。
（条件２）各平面に少なくとも３つの非共線の頂点が含まれる。
（条件３）各輪郭線は少なくとも２つの異なる平面に属する。
（条件４）各平面上の頂点は首尾接続で閉領域を構成しなければならない。
【０１３２】
前述したように切断面により分割されなかった子図形については、上記の判定を行わない。輪郭図形を複数の分離する子図形に分割する際に、一つ目の条件で判定してもよく、主に自由な点又は自由な平面を処理するためである。
【０１３３】
以下、再構成部及び再構成ステップを説明する。再構成部及び再構成ステップは、入力される輪郭図形について対応する三次元実体を再構成する。かかる処理は、主に２つのステップを有する。まず、再構成部は、図形分割中で変化を生じた平面に三角化処理を実施して新しい三角形を作成する。次に、再構成部は、三次元物体の表面の法線方向を一致させるように、新たに作成された三角形の法線方向を校正する。
【０１３４】
三次元モデルを再構成する方法は様々あり、例えば、序列画像、深さデータ、スケルトンや輪郭などに基づく再構成方法がある。好ましくは、実施例では、次の再構成方法が適用される。
【０１３５】
図形分割中では、各平面は変化有りの平面と変化無しの平面という２種類に分類される。三角化処理では、再構成部は、変化有りの平面のみに三角化アルゴリズムを適用して、新しい三角形状の平面を作成し、最終の三次元物体の完全性（閉合性）を確保する。一方、変化無しの平面について、再構成部は、本実施例では従来の三角形データを適用する。以下、変化有りの平面を三角化する方法を中心に説明する。図１６は開示技術の実施形態による平面を三角化する処理を示すフローチャートである。
【０１３６】
改めて三角化処理を行う平面をｐｌｉ（ここで、ｉ＝１，２，．．．，ｎｌ）と定義する。ここで、ｎｌは変化有りの平面の数を示し、ベクトルｖｉｋ，（ここで、ｋ＝１，２，．．．，ｎｋ）はｐｌｉ番目の平面上の点の数を示す。まず、三次元モデル分割装置が実行するステップＳ１６０１で、該平面にある全ての多角形を求める。平面上の各頂点は終始間違いなく接続されているので、三次元モデル分割装置は、次の手順に従って全ての多角形を検出し、検出された多角形をＬｉ＝｛ｌｉ１，ｌｉ２，．．．，ｌｉｉｎ｝（ここで、ｉ＝１，２，．．．，ｎ）で表す。ｎは多角形の数を示し、Ｌｉにおける頂点序列は各多角形の頂点序列を示す。
【０１３７】
三次元モデル分割装置は、多角形の数ｎを０に初期化し（ｎ＝０）、頂点の処理マークｐｋ＝ｆａｌｓｅ（ここで、ｋ＝１，２，．．．，ｎｋ）は全ての頂点がまだ処理されていない旨を示す。三次元モデル分割装置は、多角形の数をｎ＝ｎ＋１に更新し、未処理の頂点ベクトルｖｒを始点としてランダムに選択し、それと接続される頂点のうちのいずれかに沿って徐々に延出し、頂点ベクトルｖｒに戻るまで延出する。三次元モデル分割装置は、その得られた頂点序列をＬｎ＝｛ｌ１，ｌ２，．．．，ｌｎｎ｝とし、ｎ番目の多角形の頂点序列を表す。三次元モデル分割装置は、Ｌｎ＝｛ｌ１，ｌ２，．．．，ｌｎｎ｝の頂点処理マークをそれら頂点が処理された旨を示すｔｒｕｅに更新する。全ての頂点は共に処理されたら終了する。そうでなければ、三次元モデル分割装置は、上記手順の２に移行する。
【０１３８】
次に、三次元モデル分割装置が実行するステップＳ１６０２では、多角形同士の包含関係を決定し、多角形を改めて構成する。前述した三次元モデル分割装置が実行するステップにより、平面上の各多角形が検出され、検出されたｎ個の多角形をＬｉ＝｛ｌｉ１，ｌｉ２，．．．，ｌｉｉｎ｝（ここで、ｉ＝１，２，．．．，ｎ）とする。多角形の数が１の場合に、三次元モデル分割装置は、該多角形の頂点の順序が反時計方向か時計方向かを判定し、時計方向であれば反時計方向に変換する。
【０１３９】
多角形の数が１より大きければ、三次元モデル分割装置は、多角形同士の包含関係行列としてＩＮｉ，ｊ，ｉ，ｊ，．．．，ｎを算出する。ＩＮｉ，ｊ＝ｔｒｕｅであれば、ｉ番目の多角形にｊ番目の多角形が包含まれる。本実施例では、多角形Ｌｊの全ての頂点が、すべて別の多角形Ｌｉの内部にあれば、多角形Ｌｉは多角形Ｌｊを包含するという。以下、行列ＩＮｉ，ｊ，ｉ，ｊ，．．．，ｎに基づきそれら多角形を構成し直すことを説明する。
【０１４０】
まず、三次元モデル分割装置は、全ての簡単な多角形Ｐｏｌｙｉ（ここで、ｉ＝１，２，．．．，ｎｉ）を求める。ここでいう簡単な多角形とは、他の多角形を包含しない、かつ他の多角形に包含されない多角形である。外部多角形を求め、求めた多角形をＰｏｌｙｋ（ここで、ｋ＝１，２，．．．，ｎｋ）で表す。ｎｋは外部多角形の数を示す。ここでいう外部多角形とは、いかなる他の多角形にも包含されないが、他の多角形を包含する多角形である。
【０１４１】
三次元モデル分割装置は、各外部多角形を対象として一連の複雑な多角形を構成する。ここでいう各複雑な多角形は、一つの外部多角形及び該外部多角形に囲まれる多角形を含む。外部多角形Ｐｏｌｙｋ（ここで、ｋ＝１，２，．．．，ｎｋ）を例にし、該外部多角形に囲まれる多角形をＬＰｋ＝｛ｌｐｋ１，ｌｐｋ２，．．．ｌｐｋｎ｝とする。ｋｎはＰｏｌｙｋに囲まれる多角形の数を表し、そうすると、複雑な多角形をＣＰｏｌｙｋ＝｛Ｐｏｌｙｋ，ＬＰｋ｝（ここで、ｋ＝１，２，．．．，ｎｋ）で表す。
【０１４２】
三次元モデル分割装置は、各簡単な多角形の頂点序列を反時計方向で並べる。三次元モデル分割装置は、複雑な多角形毎に、外部多角形を反時計方向で並べ、内部多角形を時計方向で並べる。次に、三次元モデル分割装置は、ステップＳ１６０３で、多角形を三角化する。一つの多角形を一連の多角形に変換する方法は様々である。まず、三次元モデル分割装置は、入力される多角形から一連の台形を得て、次に台形に適当な対角線を追加して、入力される多角形を一連の簡単な多角形に変換する。最後に、三次元モデル分割装置は、簡単な多角形を三角化するアルゴリズムにより一連の重ならない三角形を得る。開示技術の実施形態では、前段のステップで説明した簡単な多角形（単一の凹多角形又は凸多角形）及び複雑な多角形（すなわち、穴のある場合）を処理する方法を用いる。この方法では、三次元モデル分割装置は、走査線方法によりまず多角形を一連の台形に変換し、次に、ある台形に対角線を追加する。そして、三次元モデル分割装置は、対角線により多角形を一連の簡単な多角形に変換し、最後に簡単な多角形を三角化して最終の三角形序列を得る。
【０１４３】
以下、三次元モデル分割装置が実行する方向校正ステップを説明する。三次元モデル分割装置が実行する該ステップは、三次元実体の表面の方向を一致するように新たに作成された三角形の方向を校正する。平面検出部の説明と同様に、三角形メッシュで表現される三次元モデルでは、各辺が２つの三角形に共通であり、かつ２つの三角形における方向が全く相反している。該ステップは上記制限条件に基づき新たに作成された多角形の法線方向を校正するものである。全ての三角形をＦｉ＝｛ベクトルｖｉ１，ベクトルｖｉ２，ベクトルｖｉ３｝（ここで、ｉ＝１，２，．．．，ｎＦ）とする。
【０１４４】
具体的な手順は次の通りとする。手順１では、三次元モデル分割装置は、三角形状の平面の処理マークをｐｒｏｉ＝ｔｒｕｅ（ここで、ｉ＝１，２，．．．，ｎＦ）に初期化する。手順２では、三次元モデル分割装置は、新たに作成された三角形状の平面の処理マークをｆａｌｓｅに設定する。手順３では、三次元モデル分割装置は、全ての未処理の三角形状の平面ＵＦ＝｛Ｆｕ１，Ｆｕ２，．．．，Ｆｕｎ｝を求めて、ｕｎは未処理の平面の数を表す。手順４では、三次元モデル分割装置は、集合ＵＦは空であれば終了し、そうでなければ次の手順５に移行する。手順５では、三次元モデル分割装置は、次の手順に従って、ＵＦの各三角形状の平面Ｆｕｋを順次処理する。処理が終了すると、三次元モデル分割装置は、上記の手順３に移行する。
【０１４５】
三次元モデル分割装置は、三角形状の平面Ｆｕｋと共通の辺を有しかつ処理済みの三角形状の面Ｆ＊を求める。Ｆ＊が求められなかったら、三次元モデル分割装置は、次の未処理の三角形を処理する。三角形Ｆｕｋ及びＦ＊において共通の辺の方向が同じであれば、三次元モデル分割装置は、この２つの三角形において共通の辺の方向を相反するようにＦｕｋの頂点の順位を変更し、該三角形状の平面の処理マークをｔｒｕｅに更新する。
【０１４６】
手順６では、三次元モデル分割装置は、全ての三角形状の平面の処理マークがｔｒｕｅになるまで上記の手順３に移行する。
【０１４７】
[第４の輪郭図形分割方法]
最後に、図１７を参照して、開示技術の三次元モデル分割装置が実行する他の実施形態による輪郭図形分割方法を説明する。三次元モデル分割装置が実行するこの実施形態による輪郭図形分割方法は、穴処理ステップだけでなく、切断面処理ステップも含む。しかし、図面では穴処理を実施した後に切断面処理を実施するが、二者の処理順序には特に制限がなく、同時に実行してもよく、また、切断面処理を実行した後に穴処理を実行してもよい。
【０１４８】
図１７に示すように、まず、ステップＳ１７０１で、輪郭図形をいくつかの分離する子図形に分割し、その詳しい処理は前述した子図形分離ステップを参照し説明を省略する。次に、ステップＳ１７０２で、子図形毎に対応する三次元実体を再構成する。次に、ステップＳ１７０３で、各子図形について、該子図形の対応する実体は穴であるか否かを判定し、穴であれば（ステップＳ１７０４、Ｙｅｓ）、ステップＳ１７１０でモデルの法線方向を変更し、該子図形の対応する三次元実体を出力する（ステップＳ１７１１）。穴でなければ（ステップＳ１７０４、Ｎｏ）、次に可能性のある全ての切断面（又は分割面という）を検出する（ステップＳ１７０５）。ステップＳ１７０３とS１７０４は穴処理ステップに対応し、その詳しい処理は前述した処理手順を参照し、説明を省略する。
【０１４９】
切断面が検出されると（ステップＳ１７０６、Ｎｏ）、ステップＳ１７０７で、切断面により子図形を複数のより小さい子図形に分割する。次に、ステップＳ１７０８で、適正判定を行う、すなわち、ステップＳ１７０７で行われた分割は成功したか否かを判定する。成功したと判定されると（ステップＳ１７０８、Ｙｅｓ）、ステップＳ１７０９で、新たに作成された子図形に対応する三次元実体を再構成する。また、ステップＳ１７０３に戻り、新しい三次元実体について穴処理及び切断面処理を継続実施する。一方、ステップＳ１７０８で分割は成功しなかったと判定されると、該三次元実体を出力し、それ以上分割しないようにする（ステップＳ１７１１）。
【０１５０】
もちろん、図１７に示すフローチャートでは、切断面処理を複数回実施してもよく、各切断面について順次実施し、一つの切断面は分割が成功しなかったと判定されると（ステップＳ１７０８、Ｎｏ）、該子図形の対応する三次元実体をそのまま出力せず、未処理の切断面がない又は分割が成功するまで、次の切断面により分割を続行する。
【０１５１】
しかし、図１７に示す実施形態では、子図形を分離すると、すなわち、ステップＳ１７０１が終了した次第、各子図形に三次元実体を構成する（ステップＳ１７０２）。しかし、まず各子図形に穴処理及び切断面処理を実施し、最後に各子図形に三次元実体をまとめて再構成することもできる。
【０１５２】
開示技術の三次元モデル分割装置が実行する実施形態では、モデル分割中では複雑な演算及び処理がないので、効率が高い。また、再構成ステップが導入され、再構成された各三次元実体モデルを三角形メッシュで表現するので、出力結果が三次元実体となっている。また、分割結果に適正判定を導入するので、耐ノイズ性が更に強化される。
【０１５３】
[適用例]
以下、一例を用いて、三次元モデル分割装置が実行する三次元モデルの分割処理を説明する。図１８は入力される三次元モデルの例を示す図である。該モデルは５２個の頂点と１０８個の三角形で物体の表面を構成する。この入力されるモデルには２つの穴がある。
【０１５４】
まず、三次元モデル分割装置は、モデルに関係するデータに基づき、各三角形状の平面の面積や法線方向などのデータを算出する。次に、三次元モデル分割装置は、互いに接続され、かつ方向が相同又は相反する三角形を組み合わせて、該モデルを構成する平面データを得る。本実施例では、２つの三角形の法線でなす角度は０．００１より小さければ、２つの三角形状の平面の方向が相同と判断される。一方、２つの三角形の法線でなす角度はπ-０．００１より大きければ、２つの三角形状の平面の方向が相反と判断される。
【０１５５】
図１９は入力されるモデルから検出された平面の構造を示す。図１８に示す入力されるモデルから合計２９個の平面が検出され、各平面には、平面上の頂点のインデックス、三角形状の平面のインデックス、平面の面積及び平面の法線方向に関係する情報が含まれる。最終に得られた平面データは次の表１に示す。検出された１２番目の平面を例にし、その平面に関係するデータを図１９に示す。１２番目の平面には、インデックスがそれぞれ５５と５８である三角形状の平面が２つ、インデックスがそれぞれ１９、２０、３３、３４である頂点が４つ含まれる。
【０１５６】
【表１】
2010186479.tif 000013
【０１５７】
次に、三次元モデル分割装置は、得られた平面データから、入力されるモデルの対応する輪郭図形を抽出する。各平面の内部の直線を削除し、図２０（ａ）に示す結果を得る。図２０（ｂ）は三次元モデルの頂点をノードとし、各平面の輪郭線を辺として構成する輪郭図形を示す。入力されるモデルの対応する輪郭図形に５２個のノードと７８本の辺が含まれる。
【０１５８】
（輪郭図形を分割する各ステップ）
次に、三次元モデル分割装置は、得られた輪郭図形に基づき、入力されたモデルを複数の部分に分割する。次に、三次元モデル分割装置が実行する輪郭図形を分割する各ステップを説明する。
【０１５９】
（ステップ１：輪郭図形を複数の分離する子図形に分割する）三次元モデル分割装置が実行するこのステップでは、相互接続されるノードを集めて複数の分離する子図形を得る。図２１に示すように、入力されるモデルの対応する輪郭図形は４つの分離する子図形に分割され、各子図形の頂点を菱形、五角の星型、円形、星型でそれぞれ示す。ここで、四角形で示す頂点は、各子図形を作成する時にランダムに選択された始点を表す。各子図形のノードからなる集合を以下に示す。各数字は三次元モデルの対応する頂点のインデックスを表す。Ｓ１＝｛７，８，９，１０，１１，１２，１３，１４｝、Ｓ２＝｛３９，４０，４１，４２，４３，４４，４５，４６｝、Ｓ３＝｛１，２，３，４，５，６，４７，４８，４９，５０，５１，５２｝、Ｓ４＝｛１５，１６，１７，１８，１９，２０，２１，２２，２３，２４，２５，２６，２７，２８，２９，３０，３１，３２，３３，３４，３５，３６，３７，３８｝。
【０１６０】
（ステップ２：各子図形の対応する三次元実体を再構成する）三次元モデル分割装置が実行するこのステップでは、各子図形の対応する三次元実体がそれぞれ再構成され、かつ再構成された三次元実体は三次元実体の形状を三角形メッシュで表現するものである。まず、各子図形について、それぞれの全ての頂点を含む平面を求め、これら平面に変化があるか否かを判定する。ある平面に２つ以上の子図形の頂点が含まれれば、該平面を変化有りの平面とする。結果を表２に示す。
【０１６１】
【表２】
2010186479.tif 000014
【０１６２】
次に、三次元モデル分割装置は、各子図形について、変化有りの全ての平面を三角化する。子図形１の場合では、平面｛２４，２５，２６，２７｝は三角化を必要としないので、そのまま従来の三角形で集合{８３，８４，８５，８６，８７，８８，８９，９０}を構成できる。しかし、平面｛４，７｝は新たに三角化される必要があり、新たに作成された三角形として（７，９，１３）と（７，１３，１０）と（８，１１，１４）と（８，１４，１２）とがある。したがって、子図形１の対応する三次元実体は８個の頂点及び１２個の三角形で構成される。
【０１６３】
子図形２の場合では、平面｛２０，２１，２２，２３｝は三角化を必要としないので、そのまま従来の三角形で集合{７５，７６，７７，７８，７９，８０，８１，８２}を構成できる。しかし、平面｛４，７｝は新たに三角化される必要があり、新たに作成された三角形として（３９，４１，４５）と（３９，４５，４２）と（４０，４３，４６）と（４０，４６，４４）とがある。したがって、子図形２の対応する三次元実体は８個の頂点及び１２個の三角形で構成される。
【０１６４】
子図形３の場合では、平面｛１，２，３，５，６，２８｝は三角化を必要としないので、従来の三角形状の平面をそのまま利用して、三角形からなる集合｛１，２，３，４，５，６，１２，１４，２１，２２，３０，３１，３５，３６，９１，９３｝を構成できる。しかし、平面｛４，７｝は新たに三角化され、三角形として（１，２，４８）と（１，４８，４７）と（５，６，５２）と（５，５２，５１）とを新たに得る必要がある。したがって、子図形３の対応する三次元実体は１２個の頂点及び２０個の三角形で構成される。
【０１６５】
子図形４の場合では、平面{８，９，１０，１１，１２，１３，１４，１５，１６，１７，１８，１９，２９}は三角化を必要としない。すなわち、そのまま従来の三角形で集合｛４６，４７，４８，５０，５１，５２，５４，５５，５６，５７，５８，５９，６０，６２，６３，６５，６６，６７，６９，７０，７１，７２，７３，７４｝を構成できる。しかし、平面４は新たに三角化される。そして、三角形として（１６，１８，２０）、（１６，２０，３４）、（１６，３４，３６）、（１６，３６，３８）、（１６，３８，３２）、（１６，３２，３０）、（１６，３０，２８）、（１６，２８，２６）、（１６，２６，２４）と（１６，２４，２２）を新たに作成する必要がある。したがって、子図形４の対応する三次元実体は２４個の頂点及び３４個の三角形で構成される。
【０１６６】
最後に、三次元モデル分割装置は、新たに作成された三角形の方向を校正する。子図形１の場合では、最初の三角形において、８３番目の三角形は（１０，１３,１４）であり、モデルの表面の方向の一致性を保証するために、新たに作成された三角形（７，１３，１０）の方向を変えない。同じ理由で、（７，９，１３）の方向も変えない。９０番目の三角形は（１１，９，８）であり、新たに作成された三角形（８，１１，１４）の方向を（８，１４，１１）に変える必要がある。同じ理由で、（８，１４，１２）の方向も（８，１２，１４）に変える必要がある。
【０１６７】
上記と同様な方法により、三次元モデル分割装置は、子図形２、子図形３と子図形４について新たに作成された三角形の方向を変える。図２２は図２１の４つの子図形から再構成された三次元モデルの結果を示す説明図である。図２２に再構成された三次元実体Ｍ１、Ｍ２、Ｍ３、Ｍ４を示す。
【０１６８】
（ステップ３：再構成された実体を分割できなくなるまで継続分割する）三次元モデル分割装置が実行するこのステップでは、再構成された三次元実体を全てのモデルが共に分割できなくなるまで継続分割する。まず、三次元モデル分割装置は、この４つのモデルは穴であるか否かを判定する。判定結果はＭ１とＭ２が穴であり、他の２つのモデルが穴ではないとする。Ｍ１とＭ２における全ての三角形の方向を変えることにより、モデルの表面の方向を外方に向かわせ、この２つのモデルを出力し、それ以上分割しないようにする。
【０１６９】
次に、三次元モデル分割装置は、モデルＭ３とモデルＭ４に切断面候補があるか否かを判定する。このステップでは、ある平面が切断面であるか否かを判定する際に、以下のルールを適用する。
（１）モデルの頂点が該切断面の両側にある、
（２）切断面の面積が表面積の百分の一より小さくない、
（３）切断面にある頂点と切断面の外部にある頂点をつなげてなる全ての辺と切断面とがなす角度は３０度以上である。
【０１７０】
三次元モデル分割装置は、上記条件に基づき判定を行うと、モデルＭ３に２つの切断面がある可能性があれば、続いて分割をする。一方、Ｍ４に切断面がないので、該モデルをそのまま出力し、それ以上分割しないようにする。
【０１７１】
次に、三次元モデル分割装置は、モデルＭ３を分割する。前段のステップで得られたモデルＭ３に含まれる頂点序列はＳ３＝｛１，２，３，４，５，６，４７，４８，４９，５０，５１，５２｝である。分割するに先立って、頂点、三角形の各頂点のインデックス及び平面データ情報を更新する。その結果、頂点序列はＳ１＝｛１，２，３，４，５，６，７，８，９，１０，１１，１２｝となり、三角形状の平面に関するデータは次に示す表３の通りとする。
【０１７２】
【表３】
2010186479.tif 000015
【０１７３】
平面に関するデータは次に示す表４の通りとする。
【０１７４】
【表４】
2010186479.tif 000016
【０１７５】
図２３は、切断面の頂点及び切断面と直接接続する頂点の分類結果を示す説明図である。図２３に示すように、Ｐ８とＰ３は切断面候補と検出される。本実施例では、面積の最も広い平面、すなわち、平面Ｐ８を優先に処理する。
【０１７６】
まず、三次元モデル分割装置は、１２個の頂点の処理マークをｆａｌｓｅに初期化する。ｐｒｏｋ＝ｆａｌｓｅ（ここで、ｋ＝１，２，．．．１２）は全ての頂点が処理されないことを表す。次に、三次元モデル分割装置は、切断面における４つの頂点をＣ１＝｛４，１０｝とＣ２＝｛５，１１｝との２種類に分ける。図２３に示すように、Ｃ１を四角形、Ｃ２を円形で示す。点の処理マークをｐｒｏｘ＝ｔｒｕｅ，ｘ∈Ｃ１∪Ｃ２に更新する。
【０１７７】
三次元モデル分割装置は、切断面における４つの頂点と直接接続され、かつ切断面に入らない頂点をＸ１＝｛３，９｝とＸ２＝｛６，１２｝との２種類に分ける。図２３に示すように、Ｘ１を星型、Ｘ２を菱形で示す。点の処理マークをｐｒｏｘ＝ｔｒｕｅ，ｘ∈Ｘ１∪Ｘ２に更新する。
【０１７８】
三次元モデル分割装置は、他の頂点を２種類に分ける。Ｘ１＝｛３，９｝の頂点を始点として延出し、未処理の頂点で集合ＰＸ１＝｛１，２，７，８｝を構成すると共に、Ｘ２＝｛６，１２｝の頂点を始点として延出し、未処理の頂点で集合ＰＸ２＝｛７，８，１，２｝を構成する。三次元モデル分割装置は、ＰＸ１∩ＰＸ２の結果としてＰＸ＝｛１，２，７，８｝を算出する。
【０１７９】
三次元モデル分割装置は、集合ＰＸから適当なノードを選択し、他の頂点を更に分類する。判定を通して、この４つの頂点が共に頂点候補とされてもよく、かつ各頂点からＸ１又はＸ２までの最も短い距離は共に１である。そこで、三次元モデル分割装置は、一つの頂点を任意に選択して処理することができる。本実施例では、１つ目の頂点である頂点１が選択され処理される。頂点１と接続される未処理頂点は２と７とがあり、直線１→２は切断面と交わり、直線１→７は切断面と平行する。三次元モデル分割装置は、直線１→２と切断面との交点を１３番目の頂点として算出する。図２４に示すように、頂点１、２を五角の星型で、交点を上方へ向かう三角形でそれぞれ示す。三次元モデル分割装置は、頂点の分類情報を更新することにより、頂点１を切断面のプラス側に位置させ、頂点１を集合Ｘ１に追加してＸ１＝｛１，３，９｝を得る。また、三次元モデル分割装置は、頂点２を集合Ｘ２に追加してＸ２＝｛２，６，１２｝を得る。また、三次元モデル分割装置は、新規追加された１３番目の頂点を集合Ｃ１とＣ２に追加した結果、Ｃ１＝｛４，１０，１３｝とＣ２＝｛５，１１，１３｝とを得る。頂点１、２と１３に関する点の処理マークがｔｒｕｅに更新される。三次元モデル分割装置は、頂点同士の接続関係及び平面データを次のように更新する。頂点１と２の間のつながりを削除し、頂点１と１３の間及び頂点２と１３の間のつながりを追加し、切断面である８番目の平面に頂点１３を追加し、平面２、４に頂点１３を追加する。
【０１８０】
三次元モデル分割装置は、Ｘ１＝｛１，３，９｝とＸ２＝｛２，６，１２｝に基づき延出し、未処理の頂点で集合ＰＸ１＝｛７，８｝とＰＸ２＝｛８，７｝構成し、ＰＸ１∩ＰＸ２の結果としてＰＸ＝｛７，８｝を算出する。三次元モデル分割装置は、判定を通して、この２つの頂点が共に頂点候補として次の処理をすることがわかる。本実施例では、頂点８を選択する。頂点８と直接接続される未処理頂点は７しかなく、直線８→７は平面の両側に亘る。三次元モデル分割装置は、直線８→７と切断面との交点を１４番目の頂点として算出する。図２４に示すように、頂点７、８を下方へ向かう三角形で、交点を上方へ向かう三角形でそれぞれ示す。次に、三次元モデル分割装置は、頂点７、８と１４の分類情報を更新することにより、８番目の頂点を切断面のマイナス側に位置させ、頂点８を集合Ｘ２に追加してＸ２＝｛２，６，８，１２｝を得る。また、三次元モデル分割装置は、７番目の頂点をＸ１に追加してＸ１＝｛１，３，９｝を得る。また、三次元モデル分割装置は、新規追加された１３番目の頂点を集合Ｃ１とＣ２に追加した結果、Ｃ１＝｛４，１０，１３，１４｝とＣ２＝｛５，１１，１３，１４｝とを得る。頂点７、８と１４に関する点の処理マークをｔｒｕｅに更新する。三次元モデル分割装置は、頂点同士の接続関係及び平面データを次のように更新する。頂点７と８の間のつながりを削除し、頂点７と１４の間及び頂点８と１４の間のつながりを追加する。切断面である８番目の平面に頂点１４を追加し、平面４、５に頂点１４を追加する。以上により、全ての頂点に関する点の処理マークがｔｒｕｅに更新される。この場合の平面データは次に示す表５の通りとする。
【０１８１】
【表５】
2010186479.tif 000017
【０１８２】
三次元モデル分割装置は、集合Ｃ１＝｛４，１０，１３，１４｝及びＣ２＝｛５，１１，１３，１４｝それぞれをＸ１＝｛１，３，７，９｝及びＸ２＝｛２，６，１２｝と合併する。三次元モデル分割装置は、平面Ｐ８を切断面として全ての頂点を分類した結果である集合ＣＸ１＝｛４，１０，１３，１４，１，３，７，９｝及びＣＸ２＝｛５，１１，１３，１４，２，６，８，１２｝を得る。
【０１８３】
次に、三次元モデル分割装置は、ＣＸ１＝｛４，１０，１３，１４，１，３，７，９｝とＣＸ２＝｛５，１１，１３，１４，２，６，８，１２｝に基づき、子図形を作成する。集合ＣＸ１の頂点４及び１３の場合、切断面と２番目の平面との交点が４及び１３しかないので、三次元モデル分割装置は、４と１３の間のつながりを追加する。同様に、三次元モデル分割装置は、頂点１３と１４の間、及び頂点１４と１０の間のつながりをそれぞれ追加する。三次元モデル分割装置は、子図形２について、頂点５と１３の間、頂点１３と１４の間及び頂点１１と１４の間のつながりをそれぞれ追加する。次に、三次元モデル分割装置は、各集合の頂点及び接続関係に基づき２つの子図形を作成する。ここで、各子図形に８個の頂点と１２本の辺が含まれる。
【０１８４】
次に、三次元モデル分割装置は、該分割結果が有効だと判定され、２つの三次元実体を再構成する。図２５に示すように、２つの三次元実体をそれぞれをＭ５とＭ６で表す。この２つの実体は共に８個の頂点と１２本の三角形状の平面を含むので、２つの直方体である。次に、三次元モデル分割装置は、Ｍ５とＭ６は共に切断面候補を有しないと判定で分かり、以上で入力されるモデルへの分割を終了する。結果、三次元モデル分割装置は、Ｍ１、Ｍ２、Ｍ４、Ｍ５、Ｍ６の計５つの部分を得る。
【０１８５】
当然、当業者は開示技術を下記のように理解すべきである。本明細書のフローチャート又は他の形態で記述される如何なる処理又は方法記述又はブロックは共に、単純なハードウエアで実現する部材、要素、装置、部等と理解できる。また該処理の具体的な論理機能又は手順が1つ以上の実行可能な指令を実現するコードモジュール、コードセグメント、コード部をも含む。すなわち、ソフトウエアで実現することもできる。また、ソフトウエアとハードウエアを組み合わせて実現することもできる。
【０１８６】
本明細書のフローチャート又は他の形態で記述されるロジック及び/又は手順は、例えば、ロジック機能を実現するための実行可能な指令の記載だと理解できる。指令実行システムや設備や装置に用いられる任意なコンピュータ読み取り可能な媒体によりそれらロジック及び/又は手順を実現することもできる。例えば、コンピュータ・システム、プロセッサーを備えるシステム、又は、指令実行システムや設備や装置から該指令を呼び出して実行する他のシステムである。
【０１８７】
本明細書の記載では、「コンピュータ読み取り可能な媒体」は、指令実行システムや設備や装置に用いられるプログラムを記憶・送信・伝送・配信することができるいずれかの装置である。コンピュータ読み取り可能な媒体は電気・磁気・光学・電磁気・赤外線又は半導体システム、設備、装置又は伝送媒体であってもよいが、それらに限らない。
【０１８８】
コンピュータ読み取り可能な媒体の具体的な実施例として、１本以上のリード線を有する電気的接続（電気）、フレキシブルディスク（磁気）、ランダムアクセスメモリ（RAM）（電気）、読出し専用メモリ（ROM）（電気）、消去可能なプログラミング読出し専用メモリ（EPROM又はフラッシュメモリ）（電気）、光ファイバー（光学）、携帯型光ディスク読出し専用メモリ（CD-ROM）（光学）などが挙げられる。
【０１８９】
コンピュータ読み取り可能な媒体はプログラムが印刷された紙材又は他の媒体であってもよい。なぜなら、例えば、紙材又は他の媒体を光学的に走査して該プログラムを取得してから、コンパイリング・解釈する或いは必要に応じて適当の形態で該プログラムに他の処理を実施することにより、該プログラムをコンピュータのメモリに記憶することができるからである。
【０１９０】
前述した明細書では、実施例を参照して開示技術を記載している。しかし、特許請求の範囲に限られる開示技術の範囲を逸脱しない前提で種々の変形や変更を実施できることが当業者は理解できる。
【０１９１】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１９２】
（付記１）三次元モデル分割装置が、
入力された三角形メッシュで表現される三次元モデルに含まれる、三角形同士が接続し、且つ、該三角形の法線方向が共通または相反する三角形を集めた平面を検出する平面検出ステップと、
前記平面検出ステップによって検出された平面から、該平面の各三角形の各辺のうち、１つの三角形のみに属する境界辺同士を接続して前記三次元モデルの輪郭である輪郭図形を抽出する輪郭図形抽出ステップと、
前記輪郭図形抽出ステップによって抽出された輪郭図形を重ならない複数の子図形に分割する輪郭図形分割ステップと、
前記輪郭図形分割ステップによって分割された子図形毎に、それぞれが三角形メッシュで表現される三次元実体を再構成する三次元実体再構成ステップと
を実行することを特徴とする三次元モデル分割方法。
【０１９３】
（付記２）前記三次元モデル分割装置が、
前記平面検出ステップで、前記三角形の法線方向が共通または相反する三角形を集めた平面同士が、少なくとも、共通する三角形を有する場合、または、頂点をつなげる辺が少なくとも１本有り且つ該辺が法線ベクトルに直交している場合、あるいは、異なる２平面に属し且つ相互接続される三角形が１対以上ある場合、のいずれかである場合に、該平面同士を合併することを特徴とする付記１に記載の三次元モデル分割方法。
【０１９４】
（付記３）前記三次元モデル分割装置が、
前記三次元実体再構成ステップによって再構成された三次元実体モデル又は前記各子図形の対応する三次元実体が穴であるか否かを、表面の外側に向かう平面の面積と内側に向かう平面の面積の大小から判定する穴判定ステップと、
前記穴判定ステップによって前記三次元実体再構成ステップで再構成されたいずれかの三次元実体モデルが穴であると判定されると、この再構成された三次元実体モデルの全ての三角形の法線方向を相反する方向に変更する、或いは、いずれかの子図形の対応する三次元実体が穴であると判定されると、子図形の対応する三次元実体の全ての三角形の法線方向を相反する方向に変更する穴モデル校正ステップと
を更に実行することを特徴とする付記１に記載の三次元モデル分割方法。
【０１９５】
（付記４）前記三次元モデル分割装置が、
前記三次元実体再構成ステップによって再構成された三次元実体モデルに切断面が含まれるか否かを、四角形の平面の２つの頂点の各々が該平面に属さない一つの頂点を持ち、且つ四角形の平面の異なる２つの頂点の各々が該平面に属さない一つの頂点を持ち、それらの該平面に属さない頂点の位置が該四角形の平面から相対する側にあるか否かで判定する、或いは、前記各子図形の対応する前記三次元実体に切断面が含まれるか否かを判定する切断面判定ステップと、
前記切断面判定ステップによって前記三次元実体再構成ステップで再構成されたいずれかの三次元実体モデルに切断面が含まれると判定されると、該切断面により該切断面を含む三次元実体モデルを２つ以上の子図形に分割する一方、前記切断面判定ステップでは、いずれかの子図形に切断面が含まれると判定されると、該切断面により該切断面を含む子図形を２つ以上の子図形に分割する輪郭図形再分割ステップと
を更に実行することを特徴とする付記１に記載の三次元モデル分割方法。
【０１９６】
（付記５）前記三次元モデル分割装置が、
前記輪郭図形再分割ステップによって分割された子図形が適正であるか否かを判定し、適正でなければ、該切断面を放棄する適正判定ステップを更に実行することを特徴とする付記４に記載の三次元モデル分割方法。
【０１９７】
（付記６）前記三次元モデル分割装置が、
前記輪郭図形再分割ステップによって分割された子図形が、頂点の数が４以上、平面の個数が４以上、かつ、各平面に少なくとも３つの非共線の頂点が含まれる、かつ、各輪郭線が少なくとも２つの異なる平面に属する、かつ、各平面上の頂点が首尾接続で一つの閉領域を構成しなければならない、という条件を全て満足した場合に、該子図形を適正と判定する付記５に記載の三次元モデル分割方法。
【０１９８】
（付記７）前記平面検出ステップは、
前記入力される三次元モデルにおける各三角形状の平面の法線方向を算出する法線方向算出ステップと、
前記法線方向算出ステップによって算出された各三角形状の平面の法線方向に基づき、互いに接続されかつ方向が相同又は相反する三角形状の平面を集めて子平面を取得する子平面取得ステップと、
前記子平面取得ステップによって取得された子平面を集めて平面を取得する平面取得ステップと
を含むことを特徴とする付記１に記載の三次元モデル分割方法。
【０１９９】
（付記８）前記平面取得ステップは、
前記２つの子平面の法線方向が相同又は相反し、かつ、前記２つの子平面の間には共通の三角形、又は共通の辺、又はこの２つの子平面のそれぞれに属する頂点を接続してなりかつ前記２つの子平面の法線方向に直交する直線が存在する、という条件を満足する２つの子平面を平面に合併する付記７に記載の三次元モデル分割方法。
【０２００】
（付記９）前記輪郭図形抽出ステップは、
各平面における全ての辺の集合を取得する辺取得ステップと、
前記辺取得ステップによって取得された各辺を内部辺又は境界辺に分類する辺分類ステップと、
前記辺分類ステップによって分類された境界辺を保留し、内部辺を削除する辺削除ステップと
を含むことを特徴とする付記１に記載の三次元モデル分割方法。
【０２０１】
（付記１０）前記切断面判定ステップは該平面上の頂点以外の頂点がそれぞれ該平面の両側にある平面を切断面と判定する付記４に記載の三次元モデル分割方法。
【０２０２】
（付記１１）前記輪郭図形再分割ステップは、
切断面における頂点を第１向き頂点集合と第２向き頂点集合に割り当てて、前記第１向き頂点集合における頂点はそれを切断面以外の頂点と接続してなる接続線が第１方向にあるものであり、前記第２向き頂点集合における頂点はそれを切断面以外の頂点と接続してなる接続線が第２方向にあるものである切断面頂点割当ステップと、
切断面以外の頂点を第１向き側頂点集合と第２向き側頂点集合に割り当てて、前記第１向き側頂点集合における頂点は第１向き頂点集合における頂点と直接又は間接に接続するものであり、前記第２向き側頂点集合における頂点は第２向き頂点集合における頂点と直接又は間接に接続するものである切断面以外頂点割当ステップと、
第１向き頂点集合における頂点と直接接続しない前記第１向き側頂点集合における頂点と、第２向き頂点集合における頂点と直接接続しない前記第２向き側頂点集合における頂点との接続関係に基づき、前記第１向き側頂点集合と第２向き側頂点集合との間に切断面に亘る接続がないように前記切断面に頂点を追加する切断面頂点追加ステップと、
前記第１向き頂点集合と第２向き頂点集合及び前記第１向き側頂点集合と第２向き側頂点集合とに基づき、切断面を含む前記三次元実体モデル又は切断面を含む前記子図形を２つ以上の子図形に分割する子図形分割ステップと
を含むことを特徴とする付記４に記載の三次元モデル分割方法。
【０２０３】
（付記１２）前記切断面頂点追加ステップは、前記第１向き側頂点集合の第１向き頂点集合における頂点と直接接続しない頂点と、前記第２向き側頂点集合の第２向き頂点集合における頂点と直接接続しない頂点との直接接続は前記切断面に交差するか否かを判定し、交差すれば、切断面に新規の頂点を追加すると共に、新規に追加された前記頂点を利用し、前記第１向き側頂点集合の第１向き頂点集合における頂点と直接接続しない頂点と、前記第２向き側頂点集合の第２向き頂点集合における頂点と直接接続しない頂点との間に直接接続する関係をなくすようにして、更に新規に追加された前記頂点それぞれを第１向き頂点集合と第２向き頂点集合に組み入れることを特徴とする付記１１に記載の三次元モデル分割方法。
【０２０４】
（付記１３）入力された三角形メッシュで表現される三次元モデルに含まれる、三角形同士が接続し、且つ、該三角形の法線方向が共通または相反する三角形を集めた平面を検出する平面検出部と、
前記平面検出部によって検出された平面から、該平面の各三角形の各辺のうち、１つの三角形のみに属する境界辺同士を接続して前記三次元モデルの輪郭である輪郭図形を抽出する輪郭図形抽出部と、
前記輪郭図形抽出部によって抽出された輪郭図形を重ならない複数の子図形に分割する輪郭図形分割部と、
前記輪郭図形分割部によって分割された子図形毎に、それぞれが三角形メッシュで表現される三次元実体を再構成する三次元実体再構成部と
を有することを特徴とする三次元モデル分割装置。
【符号の説明】
【０２０５】
１０１  平面検出部
１０１１  法線方向算出部
１０１２  子平面取得部
１０１３  平面取得部
１０２  輪郭図形抽出部
１０２１  辺取得部
１０２２  辺分類部
１０２３  辺削除部
１０３  輪郭図形分割部
１０３１  子図形取得部
１０３２  穴処理部
１０３３  切断面処理部
１０３４  再構成部
【図１Ａ】
2010186479.tif 000018
【図１Ｂ】
2010186479.tif 000019
【図２】
2010186479.tif 000020
【図３】
2010186479.tif 000021
【図４】
2010186479.tif 000022
【図５】
2010186479.tif 000023
【図６】
2010186479.tif 000024
【図７】
2010186479.tif 000025
【図８】
2010186479.tif 000026
【図９】
2010186479.tif 000027
【図１０】
2010186479.tif 000028
【図１１】
2010186479.tif 000029
【図１２】
2010186479.tif 000030
【図１３】
2010186479.tif 000031
【図１４】
2010186479.tif 000032
【図１５】
2010186479.tif 000033
【図１６】
2010186479.tif 000034
【図１７】
2010186479.tif 000035
【図１８】
2010186479.tif 000036
【図１９】
2010186479.tif 000037
【図２０】
2010186479.tif 000038
【図２１】
2010186479.tif 000039
【図２２】
2010186479.tif 000040
【図２３】
2010186479.tif 000041
【図２４】
2010186479.tif 000042
【図２５】
2010186479.tif 000043