三次元モデル分割方法、三次元モデル分割装置及び三次元モデル分割装置を含む画像処理システム
【課題】ノイズの影響を軽減し、少ない計算量で正確に三次元モデルを分割する。
【解決手段】入力された三次元モデルの三角形ポリゴンデータに基づいて、前記三次元モデルに含まれるすべての三角形を処理し、前記三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する有界平面生成ステップと、前記生成した有界平面を通して前記三次元モデルの輪郭図を抽出する輪郭図抽出ステップと、前記生成した有界平面の情報及び前記三次元モデルの頂点隣接グラフの情報に基づいて、前記抽出した輪郭図を所定の条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する輪郭図分割ステップとを含む三次元モデル分割方法を提供する。また三次元モデル分割装置及びその装置を有する画像処理システムを提供する。開示技術の方法、装置とシステムを通して、三次元モデル分割の正確性と効率を高めることができる。
【解決手段】入力された三次元モデルの三角形ポリゴンデータに基づいて、前記三次元モデルに含まれるすべての三角形を処理し、前記三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する有界平面生成ステップと、前記生成した有界平面を通して前記三次元モデルの輪郭図を抽出する輪郭図抽出ステップと、前記生成した有界平面の情報及び前記三次元モデルの頂点隣接グラフの情報に基づいて、前記抽出した輪郭図を所定の条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する輪郭図分割ステップとを含む三次元モデル分割方法を提供する。また三次元モデル分割装置及びその装置を有する画像処理システムを提供する。開示技術の方法、装置とシステムを通して、三次元モデル分割の正確性と効率を高めることができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、三次元モデル分割方法、三次元モデル分割装置及び三次元モデル分割装置を含む画像処理システムに関する。
【背景技術】
【０００２】
近年、コンピュータ技術とコンピュータ支援設計（ＣＡＤ：Computer-Aided Design）モデリングツールの発展に従って、三次元モデルは広範囲に使用されている。これと同時に、三次元モデルは、より複雑になりデータ量も多くなっている。これらのモデルを有効に保存、処理、レンダリング、伝送するために、三次元モデルを分割する技術が広く注目を集めている。三次元モデルを分割する技術は、複雑なモデルを比較的単純でデータ量の少ないモデルに分割することができる。さらに、これらの分割されたデータ量の少ないモデルを個別に処理することで、保存、処理、レンダリング作業などの効率が大幅に引き上げられる。同時に、分割結果は、入力されたモデルを構造化して記述するので、モデルの保存と複製の使用にも便利である。
【０００３】
今までに、すでに多くのモデル分割技術が開示されている。これらの技術は、分割結果に基づいて大きく二種類に分けられる。第一種類の技術は、パッチに基づく技術である。この技術は、三次元メッシュを一連の異なるパッチプリミティブ、例えば平面、柱面、球面などに分割する。この種の技術は、前処理の手段として使うことができ、モデルの特徴の抽出に役立つ。第二種類の技術は、立体コンポーネントに基づく技術である。この技術は、三次元メッシュを一連の立体的なプリミティブ、例えば直方体、球体などに分割する。この技術は入力されたモデルの構造を表現するので、物体検出、部分マッチングなどの分野で非常に高い応用価値を有する。
【０００４】
従来のモデル分割技術について説明する。上述の第一種類に属する技術として、領域拡張法で距離画像に対して分割を行う方法がある。この方法では、まず頂点ごとに対応する平均曲率とガウス曲率を算出し、算出した曲率によってシェード領域を構築して、二次多項式で表現する。続いて各シェード領域に対して、この領域周囲の頂点のシェード領域への従属度を計算し、計算した従属度に基づいて領域拡張するとともに、各シェード領域の拡張ができなくなるまでシェード領域を拡張する。
【０００５】
また、第一種類に属する別の技術として、三角形のクラスタリングを通じて分割する方法がある。この方法では、まず三角形同士の隣接関係を利用して双対グラフを作成し、双対グラフにおいて、各三角形を一つのノードとして、初期状態では、各三角形の面が独立するクラスタリングとする。そして、双対グラフの各辺の縮約指標を計算し、平面の度数、三角形間の方向の差異などの属性に基づいて、双対グラフのすべての辺が縮約できなくなるまで、双対グラフのある双対辺を縮約させる。すなわち、双対辺が連結する二つのノードを一つに合併させ、隣接している二つのクラスタリングを一つの大きなクラスタリングに合併させる。
【０００６】
上述の第二種類に属する技術として、ランダムに選択した境界ではない頂点を起点として、境界として判定された頂点に囲まれるまで、領域を拡張する方法がある。この方法では、まず各頂点に対応するガウス曲率を計算し、設定された閾値に基づいて、大きいマイナス曲率を持った頂点を境界点とする。
【０００７】
また、第二種類に属する別の技術として、入力されたモデルをまず粗く分割してから、徐々に正確な分割を求める方法がある。この方法は分割の結果が空間の位置の不変性を持つようにＭＤＳ(Multi Dimensional Sealing)変換を導入し、一種のロバストな特徴点を抽出する。これによって三次元モデルを複数の部分に分割し、且つカットセット方法を導入して各部分のエッジを更に改善させる。
【０００８】
さらに、前記の第二種類に属する別の技術として、三次元モデルの各パッチの類似性を記述する双対グラフを計算し、スペクトラルクラスタリング方法を採用して三次元モデルを分割する方法がある。ここで、パッチ間の類似性は、パッチ間の測地距離と角度距離を合わせたものである。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Besl P.J、Jain R，「Segmentation through Variable-Order Surface Fitting」，IEEE PAMI，１９９８，１０(２),ｐ．１６7-１９２
【非特許文献２】Garland M、Willmott A、Heckbert P.S，「Hierarchical Face Clustering on Polygonal Surfaces」、Proceeding of Symposium on Interactive 3D Graphics，２００１,p．２１４-２２３
【非特許文献３】Zhang Y、Paik J、Koschan A、Abidi M.A，「A Simple and Efficient Algorithm for Part Decomposition」，Proceeding of International Conference on Image Processing，２００２,p．２7３-２7６
【非特許文献４】S Katz、G leifman、A Tal，「Mesh segmentation using feature point and core extraction」，The Visual Computer，２００５，２１(８-１０)，p．８６５-８7５
【非特許文献５】R Liu、H Huang，「Segmentation of 3d meshes through spectral clustering」，Pacific conference on Computer graphics and applications，２００４，ｐ．２９８-３０５
【非特許文献６】R Seidel，「A simple and fast incremental randomized algorithm for computing trapezoid decompositions and for triangulating polygons」，Computational Geometry：Theory and Applications，１９９１，Vol.１，No.１,ｐ．５１-６４
【非特許文献７】Joseph O’ Rourke，「Computational geometry in C (second edition)」，Cambridge University Press,ｐ．１-４０
【非特許文献８】Nina Amenta、Marshall Bern、Manolis Kamvysselis，「A new voronoi-based surface reconstruction algorithm」，ACM SIGGRAPH，１９９８，ｐ．４１５-４２１
【非特許文献９】王志強、肖立瑾，「多角形の簡単性、方向及び内外点の判別算法」，計算機学報，１９９８，No.２,Vol.２１,ｐ．１８３-１８７
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述した従来の技術では、ノイズの影響を軽減し、少ない計算量で正確に三次元モデルを分割することができないという課題があった。
【００１１】
具体的には、領域拡張法で距離画像に対して分割を行う方法は、曲率が非常にノイズの影響を受けやすいので、ノイズを軽減する能力が低い。また、三角形のクラスタリングを通じて分割する方法は、容易に実施できるが、予め設定された閾値への依存性が非常に高い。
【００１２】
入力されたモデルをまず粗く分割してから、徐々に正確な分割を求める方法は、理論的には良い分割結果を得ることができるが、計算量が多いので実際の利用には不利である。また、スペクトラルクラスタリング方法を採用して三次元モデルを分割する方法は、クラスタリングの数を予め設定する必要があり、また滑らかなエッジを持つモデルについて、自然な分割結果が得られない可能性がある。
【００１３】
総合的に見れば、既存の三次元モデルの分割技術は、通常複数の複雑な特徴、例えば、曲率、三角形の面間の測地距離、突出関数（Protrusion function）などを用いる。これらの特徴の正確な算出は比較的に困難であり、また、ノイズの影響を受けやすい。既存の方法には、以下の主要課題が存在する。１、曲率のようなノイズの影響を受けやすい特徴の導入により、ノイズを軽減する能力が比較的低い。２、モデルの分割技術は、計算量が比較的に多く複雑であり、分割効率に影響を与える。３、既存の方法では分割して得られた結果は、通常、パッチまたはパッチの組み合わせで表現するので、独立な三次元実体ではない。４、早期のモデルの分割方法には通常過分割問題が存在する。
【００１４】
開示の技術は、上記に鑑みてなされたものであって、ノイズの影響を軽減し、少ない計算量で正確に三次元モデルを分割することができる三次元モデル分割方法、三次元モデル分割装置及び三次元モデル分割装置を含む画像処理システムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
本願の開示する三次元モデル分割方法は、一つの態様において、入力された前記三次元モデルの三角形ポリゴンデータに基づいて、前記三次元モデルに含まれるすべての三角形を処理し、三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する有界平面生成ステップと、前記生成した有界平面を通して前記三次元モデルの輪郭図を抽出する輪郭図抽出ステップと、前記生成した有界平面の情報及び前記三次元モデルの頂点隣接グラフの情報に基づいて、前記抽出した輪郭図を所定条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する輪郭図分割ステップとを含み、前記三次元モデルの三角形ポリゴンデータに基づいて、三次元モデルの頂点をノードとして、一つ或は複数の三角形に共有される二つの頂点の間ごとに一辺を追加して前記頂点隣接グラフを構築する。
【００１６】
また、本願の開示する三次元モデル分割装置は、他の態様において、入力された三次元モデルの三角形ポリゴンデータに基づいて、前記三次元モデルに含まれるすべての三角形を処理し、前記三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する有界平面生成部と、前記生成した有界平面を通して前記三次元モデルの輪郭図を抽出する輪郭図抽出部と、前記生成した有界平面の情報及び前記三次元モデルの頂点隣接グラフの情報に基づいて、前記抽出した輪郭図を所定条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する輪郭図分割部とを含み、前記三次元モデルの三角形ポリゴンデータに基づいて、三次元モデルの頂点をノードとし、一つ或は複数の三角形に共有される二つの頂点の間ごとに一辺を追加して前記頂点隣接グラフを構築する。
【００１７】
また、本願の開示する画像処理システムは、他の態様において、上述の三次元モデル分割装置を有し、例えば目標検査システム、部分マッチングシステム、モデル検索システムなどである。
【００１８】
また、本願の開示する三次元モデル分割プログラムは、他の態様において、機器の読取可能な指令コードを格納しているプログラムの製品を提供する。前記指令コードは機器により読み取って実行する時に、上述したような、開示技術による三次元モデルを分割する方法を実行することができる。
【発明の効果】
【００１９】
本願の開示する三次元モデル分割方法、三次元モデル分割装置及び三次元モデル分割装置を含む画像処理システムの一つの態様によれば、ノイズの影響を軽減し、少ない計算量で正確に三次元モデルを分割することができるという効果を奏する。
【００２０】
また、本願の開示する三次元モデル分割方法、三次元モデル分割装置及び三次元モデル分割装置を含む画像処理システムの一つの態様によれば、入力された三次元モデルに対して、有効な分割を行い、また、正確な分析及び再構築を行うことができるという効果を奏する。
【００２１】
また、本願の開示する三次元モデル分割方法、三次元モデル分割装置及び三次元モデル分割装置を含む画像処理システムの一つの態様によれば、入力された三次元モデルをまず粗く分割してから徐々に正確な分割を求め、分割できなくなるまで複数の部分に分割する。
【００２２】
また、本願の開示する三次元モデル分割方法、三次元モデル分割装置及び三次元モデル分割装置を含む画像処理システムの一つの態様によれば、分割された各部分は、それぞれ閉鎖される立体コンポーネントである。
【図面の簡単な説明】
【００２３】
【図１】図１は、開示技術の実施例による三次元モデル分割方法を示すフローチャートである。
【図２Ａ】図２Ａは、開示技術の実施例による三次元モデル分割方法において有界平面を抽出する一つの実施例を模式的に示す図である。
【図２Ｂ】図２Ｂは、開示技術の実施例による三次元モデル分割方法において有界平面を抽出する一つの実施例を模式的に示す図である。
【図２Ｃ】図２Ｃは、開示技術の実施例による三次元モデル分割方法において有界平面を抽出する一つの実施例を模式的に示す図である。
【図３Ａ】図３Ａは、開示技術の実施例による三次元モデル分割方法において輪郭図の抽出を行う一つの実施例を示す図である。
【図３Ｂ】図３Ｂは、開示技術の実施例による三次元モデル分割方法において輪郭図の抽出を行う一つの実施例を示す図である。
【図４】図４は、開示技術の実施例による三次元モデル分割方法において抽出された有界平面、輪郭図などの情報に基づいて、モデルの分割を行う一つの実施例を模式的に示すフローチャートである。
【図５】図５は、図４に示したフローチャートにおけるステップS４１０の処理の一つの実施例を模式的に示すフローチャートである。
【図６】図６は、図３の中で示した有界平面１を分割面にして、入力された三次元モデルに対して分割して得られた各サブグラフには何れも選定された分割面が含まれている一例を示す図である。
【図７Ａ】図７Ａは、開示技術の実施例による三次元モデル分割方法において選定された候補分割面に基づいて、入力された三次元モデルに対して分割を行って取得した結果に、選定された分割面側にあるが、選定された分割面を含んでいないサブグラフが存在する一例を示す図である。
【図７Ｂ】図７Ｂは、開示技術の実施例による三次元モデル分割方法において選定された候補分割面に基づいて、入力された三次元モデルに対して分割を行って取得した結果に、選定された分割面側にあるが、選定された分割面を含んでいないサブグラフが存在する一例を示す図である。
【図７Ｃ】図７Ｃは、開示技術の実施例による三次元モデル分割方法において選定された候補分割面に基づいて、入力された三次元モデルに対して分割を行って取得した結果に、選定された分割面側にあるが、選定された分割面を含んでいないサブグラフが存在する一例を示す図である。
【図７Ｄ】図７Ｄは、開示技術の実施例による三次元モデル分割方法において選定された候補分割面に基づいて、入力された三次元モデルに対して分割を行って取得した結果に、選定された分割面側にあるが、選定された分割面を含んでいないサブグラフが存在する一例を示す図である。
【図８Ａ】図８Ａは、開示技術の実施例による三次元モデル分割方法の中で選定された候補分割面に基づいて、入力された三次元モデルに対して分割を行って取得した結果に、選定された分割面を跨るサブグラフが存在する一例を示す図である。
【図８Ｂ】図８Ｂは、開示技術の実施例による三次元モデル分割方法の中で選定された候補分割面に基づいて、入力された三次元モデルに対して分割を行って取得した結果に、選定された分割面を跨るサブグラフが存在する一例を示す図である。
【図８Ｃ】図８Ｃは、開示技術の実施例による三次元モデル分割方法の中で選定された候補分割面に基づいて、入力された三次元モデルに対して分割を行って取得した結果に、選定された分割面を跨るサブグラフが存在する一例を示す図である。
【図９Ａ】図９Ａは、開示技術の実施例による三次元モデル分割方法の中で穴判別処理を行う一例を示す図である。
【図９Ｂ】図９Ｂは、開示技術の実施例による三次元モデル分割方法の中で穴判別処理を行う一例を示す図である。
【図９Ｃ】図９Ｃは、開示技術の実施例による三次元モデル分割方法の中で穴判別処理を行う一例を示す図である。
【図１０Ａ】図１０Ａは、開示技術の実施例による三次元モデル分割方法の中で穴判別処理を行う他の例を示す図である。
【図１０Ｂ】図１０Ｂは、開示技術の実施例による三次元モデル分割方法の中で穴判別処理を行う他の例を示す図である。
【図１１Ａ】図１１Ａは、開示技術の実施例による三次元モデル分割方法の中で、分割結果における各実体を再編成することを模式的に示す図である。
【図１１Ｂ】図１１Ｂは、開示技術の実施例による三次元モデル分割方法の中で、分割結果における各実体を再編成することを模式的に示す図である。
【図１２Ａ】図１２Ａは、開示技術の実施例による三次元モデル分割方法において分割する三次元モデルを予め複数の互いに分離するサブモデルに分割することを模式的に示す図である。
【図１２Ｂ】図１２Ｂは、開示技術の実施例による三次元モデル分割方法において分割する三次元モデルを予め複数の互いに分離するサブモデルに分割することを模式的に示す図である。
【図１２Ｃ】図１２Ｃは、開示技術の実施例による三次元モデル分割方法において分割する三次元モデルを予め複数の互いに分離するサブモデルに分割することを模式的に示す図である。
【図１３】図１３は、開示技術の実施例の三次元モデル分割に用いられる装置を模式的に示すブロック図である。
【発明を実施するための形態】
【００２４】
下記のように、図面を参照しながら開示技術の実施形態を説明する。開示技術の一つの図面或は一種の実施の形態で記述する要素と特徴は、一つ或はもっと多くのその他の図面或は実施の形態に示す要素と特徴に結合できる。注意すべきことは、明瞭且つ簡潔にするために、開示技術と関係のない、当業者にとって既知のコンポーネント及び処理の表示と記述は図面と説明から省略した。
【実施例】
【００２５】
図１は、開示技術の実施例による三次元モデル分割方法を示すフローチャートである。三次元モデル分割装置は、有界平面生成ステップＳ１１０で、入力された三次元モデルの三角形ポリゴンデータに基づいて当該三次元モデルに含まれるすべての三角形に対して処理を行い、当該三次元モデルの分割に適用する有界平面を少なくとも一つ生成する。三次元モデル分割装置は、輪郭図抽出ステップＳ１２０で、生成された有界平面を通して三次元モデルの輪郭図を抽出する。三次元モデル分割装置は、輪郭図分割ステップＳ１３０で、生成された有界平面の情報及び三次元モデルの頂点隣接グラフの情報により、抽出された輪郭図を一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する。ここで、頂点隣接グラフは、三次元モデルの三角形ポリゴンデータに基づいて、三次元モデルの頂点をノードにして、一つ或は複数の三角形に共有される二つの頂点の間ごとに一辺を追加して構築される。
【００２６】
以下では、図面を参考にして三次元モデル分割装置が実行する各ステップを詳しく説明する。
【００２７】
三次元モデル分割装置が実行する有界平面生成ステップＳ１１０は、モデルの表面を構成する三角形ポリゴンを合理的に編成し、一連（少なくとも一つ）の三次元モデルを分割するのに適用できる有界平面を生成する。開示技術の当該実施例により、入力された三次元モデルは、三角形ポリゴンで表現する必要があり、基本的なデータの構成要素には、モデルの頂点とモデル表面を構成する三角形ポリゴンを含む。分割対象である入力された三次元モデルは、様々な形式を持つことができる。例えば、スキャンによって生じるポイント雲モデル、各種のモデリングツールによって生じるバラメーター化のモデル、或は三角形ではないポリゴンで表示されるモデルなどである。開示技術の方法を利用する場合には、先ずこのような形式で表示される三次元モデルは、三角形ポリゴンの形式に変換されなければならない。既知の様々な方法を利用して、このような変換を実行することができる。例えば、もし入力されるのが三角形ではないポリゴンで表示される三次元モデルであれば、上述の「非特許文献７」で開示された方法を使用して各多角形を一連の三角形に変換することができる。もし入力されるのがポイント雲モデルであれば、上述した「非特許文献８」で開示された方法を使用してポイント雲モデルを三角形ポリゴンの形式に変換できる。有界平面は、一つ或は複数の閉鎖領域で構成される可能性がある。
【００２８】
三次元モデル分割装置が実行する有界平面生成ステップＳ１１０は、主に二つのサブステップで構成される。サブステップ１において、三次元モデル分割装置は、すべての三角形を組み合わせることによって、すべての広義の平面（general planes）を取得する。サブステップ２において、三次元モデル分割装置は、後続の輪郭図の抽出、分割、再編成などの処理に利用できるように、取得した広義の平面からすべての有界平面を検出する。
【００２９】
サブステップ１では、三次元モデル分割装置は、先ず、分割対象である、三角形ポリゴンで表示された三次元モデルのそれぞれの三角形を初期化する。すなわち、三次元モデル分割装置は、分割対象であるモデルの表面を構成するそれぞれの三角形を一つのサブ平面とする。すなわち、三角形の数だけのサブ平面が存在する。この中では、三次元モデル分割装置は、三角形の法線方向をサブ平面の法線方向とする。三次元モデル分割装置は、三角形の法線方向を公知の計算式で計算して取得することができ、ここで、法線方向とは、三角形の平面に垂直し且つ分割対象である三次元モデルの外部を指す方向である。続いて、三次元モデル分割装置は、すべてのサブ平面が合成できなくなるまで合成条件を満たすサブ平面を一つの新しいサブ平面に合成する（converge）。ここで、サブ平面の合成処理によって得られた平面を「広義の平面」と呼ぶ。ここで、三次元モデル分割装置がサブ平面を合成できる条件は、（１）法線の方向が同じ又は反対であり、（２）頂点が同一平面にあることである。
【００３０】
図２Ａ−図２Ｃは、開示技術の実施例による三次元モデル分割方法において有界平面を抽出する一つの実施例を模式的に示す図である。図２Ａは、三角形ポリゴンで表示される三次元モデルを示し、そのモデルは２０個の頂点と３６個の三角形を含んでいる。図２Ｂは、一つ目のサブステップの後に取得する広義の平面を示し、合計で１０個の広義の平面が検出された。なお、記述の簡潔且つ明瞭のために、図２Ｂには検出された１０個の広義の平面の中の三つの広義の平面しか示していない。すなわち、広義の平面１、広義の平面２、広義の平面３である。
【００３１】
サブステップ２では、三次元モデル分割装置は、平面自体の幾何学特徴及び平面の間の関係などの情報を使用して、ステップ１で取得した広義の平面に対して処理を行い、それによって一連の有界平面を生成する。平面自体の幾何学特徴及び平面の間の関係などの情報には、各平面上に含まれている頂点及びその座標、平面の間の接続関係、ある平面では当該平面上の頂点以外の他の頂点が当該平面との相対位置、各平面上の三角形データなどが含まれる。三次元モデル分割装置は、上述の方式で入力された三次元モデルに対して三角形ポリゴンでの表示を行った後に、これに対応して平面自体の幾何学特徴及び平面の間の関係などの情報を得る。三次元モデル分割装置は、二つの平面に少なくとも一つの共同点を有する時に、この二つの平面は相互接続されていると判定する。三次元モデル分割装置は、すべての広義の平面が処理される必要がなくなるまで、検出されたすべての広義の平面におけるそれぞれの平面に対して以下の処理を行う。
【００３２】
１）三次元モデル分割装置は、入力された三次元モデルの三角形ポリゴンデータに基づいて、当該広義の平面にある三角形に対して三角形隣接グラフを作成する。もし当該三角形隣接グラフが繋がっていない場合、三次元モデル分割装置は、当該広義の平面を処理する必要がある。すなわち、三次元モデル分割装置は、当該広義の平面を複数のサブ平面に分ける。ここで、三角形隣接グラフが繋がっていないとは、当該広義の平面上の三角形が複数の分離するサブ平面に分けられ、当該サブ平面ごとに一つ或は複数の互いに接続する三角形（これらの三角形は少なくとも一つの共通点を有している）を含んでいる場合である。例えば、図２Ｂにおける広義の平面１と広義の平面２はそれぞれ二つの繋がらないサブ平面に分けられるが、広義の平面３はこのように分ける必要がない。ここで、三角形隣接グラフは三角形の接続関係を表すグラフである。三角形隣接グラフを作成する場合、三次元モデル分割装置は、三角形ポリゴンデータに含まれる各三角形をノードとし、二つの三角形が共通点を持つ場合に、その二つの三角形が表すノードの間に一辺を追加して三角形隣接グラフを取得する。三次元モデル分割装置は、この二つの三角形における任意の点、例えば、二つの三角形の中点を繋ぐことによって、この辺を追加することができる。三角形隣接グラフにおける任意の一対ノード（つまり、二つの三角形）の間に接続パスが存在する場合に、三次元モデル分割装置は、当該三角形隣接グラフは繋がっていると判定する。ここでのパスは通常一辺か又は複数の辺で構成される。
【００３３】
２）上述の処理１）によって取得した複数のサブ平面が同時に他の同一の平面と接続する場合に、三次元モデル分割装置は、モデル分割の便宜を図るために、これらのサブ平面を一つの組み合わせの有界平面として組み合わせる必要がある。例えば、図２Ｂで、サブグラフ２-１とサブグラフ２-２は何れも有界平面３と接続しているから、この二つのサブグラフは組み合わされて一つの組み合わせの有界平面になる。またこの組み合わせの有界平面に沿って、三次元モデル分割装置は、図２Ａ−２Ｃに示される三次元モデルを二つの部分に分割することができる。具体的な実施過程では、三次元モデル分割装置は、反復的に有界平面の検出処理を行うことができる。すなわち、三次元モデル分割装置は、平面の数が変化しないようにサブステップ１で生じた広義の平面を更新する。したがって、始まる時に、ここの「他の同一の平面」とはサブステップ１で取得した広義の平面であり、その後、ここの「他の一つの平面」とは更新されて得られた有界平面の可能性がある。
【００３４】
３）上述の処理１）によって取得したサブ平面で、あるサブ平面について、頂点隣接グラフにおいて、当該サブ平面に繋がる頂点が当該サブ平面の同じ側にある場合に、当該サブ平面は「独立的」有界平面と称することができる。つまり、他の平面と組み合わせる必要がない有界平面である。例えば、図２Ｂで、サブ平面１-１と繋ぐ四つの頂点は当該サブ平面の同じ側にあるから、サブ平面１-１は独立的有界平面とすることができる。同じ原理で、サブ平面１-２も独立的有界平面と称すことができる。しかし、サブ平面２-１とサブ平面２-２は当該条件を満たさないので、これらは有界平面であるが、独立的有界平面ではない。また、図２Ｂにおける広義の平面３も他のサブ平面との組み合わせの処理をする必要がない有界平面と判定される（図２Ｃを参照）。ここで、頂点隣接グラフは入力された三次元モデルの三角形ポリゴンデータによって構築され、頂点の接続関係を記述する図である。三次元モデル分割装置は、三次元モデルの頂点をノードとし、二つのノードが一つ或は複数の三角形（すなわち、入力する三角形ポリゴンデータに含まれた三角形）に共有される場合に、その二つのノードの間に一辺を追加して頂点隣接グラフを構築する。
【００３５】
図２Ｃは、三次元モデル分割装置がサブステップ２の処理を行った後の結果を示し、有界平面の数は１１個である。この中で、広義の平面１は、二つの有界平面に分けられている。二つの有界平面は、図２Ｂにおけるサブ平面１-１に対応する有界平面１１及びサブ平面１-２に対応する有界平面１である。他の有界平面は、それぞれ前記サブステップ１で取得した広義の平面と対応する。すなわち、その他の平面は変わらないままである。注意すべきことは、明瞭且つ簡潔のために，図には全ての有界平面を表示していない。
【００３６】
上述のことから、三次元モデル分割装置は、上述の有界平面生成処理を反復的に行う。すなわち、三次元モデル分割装置は、平面の数が変わらなくなるまでサブステップ１で生じた広義の平面に対して更新を行い、それによって一つ或は複数の有界平面を生成する。そして、上述の記載から、「有界平面」は前記三次元モデルの分割に適用できる、すなわち、上述の相応する条件を満たす平面であることが分かる。有界平面には外の平面と組み合わせる必要がない有界平面（例えば図２Ｃでの有界平面１１、有界平面１及び有界平面３）、及び組み合わせる必要があるサブ平面に対して組み合わせの処理を行って取得した組み合わせの有界平面（例えば図２Ｃでの有界平面２）が含まれる。
【００３７】
当業者は、有界平面生成ステップＳ１１０で生じた有界平面の数は、分割対象である三次元モデルによって決められ、一つ或は複数であってもよいことを理解できる。
【００３８】
以下では、図１に示す輪郭図抽出ステップＳ１２０の詳細を記述する。三次元モデル分割装置が実行する当該ステップは、検出された有界平面のデータを利用して、三次元モデルの輪郭を抽出し、同時に図の方式でこれを表す。この過程で、三次元モデル分割装置は、有界平面の間の接続関係に応じて、互いに接続する二つの平面のエッジにある線分が輪郭線であるかどうかを判定する。最後に、三次元モデル分割装置は、モデルの頂点を頂点とし、抽出された輪郭線を辺とし、分割対象である入力されたモデルに対応する輪郭図を構築する。それぞれの有界平面のデータには、例えば、当該有界平面にある頂点、三角形、法線方向及び面積などに関する情報が含まれる。
【００３９】
三次元モデル分割装置が実行する当該ステップでは、主に以下の二つの基本規則を採用して輪郭線を確定する。１）内部の辺を輪郭線にしてはならない。一辺がただある有界平面の中にあり、或は同一の有界平面の二つか複数の三角形により共有される場合、その辺は内部の辺と判定される。２）各輪郭線は少なくとも二つの異なる有界平面に繋がらなければならず、またそれぞれの有界平面に、一つの三角形のある辺がその輪郭線を含むように当該一つの三角形が存在する。
【００４０】
以上の二つの規則に従って、輪郭の抽出過程で、三次元モデル分割装置は、先ず輪郭図を初期化させ、分割対象である入力された三次元モデルの頂点を輪郭図の頂点にし、頂点の間は接続しない。すなわち、図に頂点のみがあり、辺がない。それから入力された三次元モデルの輪郭図を取得するように、三次元モデル分割装置は、以下のステップを採用して相応する頂点の間に輪郭線を追加する。
【００４１】
１）三次元モデル分割装置は、各有界平面に対して、それと繋がる有界平面を探す。例えば、図３Ａで有界平面１と有界平面２には四つの共通点Ａ、Ｂ、ＣとＤが存在しているので、三次元モデル分割装置は、有界平面１と有界平面２は互いに接続していると判定する。
【００４２】
２）三次元モデル分割装置は、各有界平面に対して、以下の方式に従ってこれと繋がっている有界平面のそれぞれを順番に処理して輪郭を抽出する。
三次元モデル分割装置は、当該有界平面と接続する平面の境界にある頂点を取得し、これらの頂点の位置に基づいて、これらをソートする。例えば図３Ａで、有界平面１と２の境界にある頂点は四つあって、ソートされた後はＡ‐Ｂ‐Ｃ‐Ｄである。
三次元モデル分割装置は、ソートされた後の頂点を順番に繋ぐ。例えば図３Ａでは、三次元モデル分割装置は、有界平面１と２の境界にある四つの頂点：Ａ、Ｂ、ＣとＤを順番に繋ぐ三本の線分、つまりＡＢ、ＢＣ、ＣＤを取得する。
三次元モデル分割装置は、各線分に対して、それが輪郭線になる条件を満たすか否かを判定する。条件を満たす場合には、三次元モデル分割装置は、輪郭図における相応する二つの頂点の間に繋がる辺を加える。例えば図３Ａに示すように、線分ＢＣは有界平面２における三角形Ｔ２‐２とＴ２−３に共有されるから、それは内部の辺であり、輪郭線とすることができない。線分ＡＢは有界平面１の三角形Ｔ１‐１の一辺に含まれる同時に、有界平面２の三角形Ｔ２−１に含まれるから、当該線分は輪郭線の条件を満たしており、三次元モデル分割装置は、輪郭図におけるノードＡとＢの間に一辺を加える。同じ原理で線分ＣＤも輪郭線である。
【００４３】
上述の輪郭抽出の処理は、それぞれの有界平面に対して行うべきである。その他、前記の処理で、例えば、図３Ａに示すように有界平面１と２の境界にある頂点が四つあり、ソートすることによってＡ−Ｂ−Ｃ−Ｄの順番の組み合わせを取得する必要がある。ソートすることは、関連する処理の負荷を減らすためで、最適化案に属する。三次元モデル分割装置は、取得した頂点をソートしなくてもいい。例えば、図３Ａ―３Ｂに示す実施例の中で、取得した頂点Ａ、Ｂ、Ｃ、Ｄに対してソートしなければ、各頂点を任意に繋いで取得した線分の数は３より大きく、例えば、線分ＡＢ、ＢＣとＣＤのほかに、他の線分ＡＣ、ＢＡ、ＤＣなどが得られる。しかし、これら他の線分は、例えば線分ＡＣのように上述の輪郭線になる条件を満たせないことにより取り除かれるか、或は重複する線分なので取り除かれてしまう。例えば線分ＢＡ、ＤＣはそれぞれ線分ＡＢ、ＣＤと重複し、同一の辺に属する。よって、三次元モデル分割装置は、取得した頂点に対してソートしなくても、入力された三次元モデルの正確な輪郭図を得ることができる。
【００４４】
以下では、図１に示す輪郭図の分割ステップＳ１３０の詳細を記述する。
【００４５】
三次元モデル分割装置が実行する当該ステップの処理は前のステップの処理で取得した有界平面、頂点隣接グラフなどの情報に基づいて、輪郭図抽出ステップＳ１２０で入力された輪郭図をまず粗く分割してから徐々に正確に、各層ごとに分割し、一つのサブグラフ或は少なくとも二つの重複しないサブグラフに分割する。図４は開示技術の実施例による三次元モデル分割方法において抽出された有界平面、輪郭図などの情報に基づいて、モデルの分割を行う一つの実施例を模式的に示すフローチャートである。図４に示すように、候補分割面検出ステップＳ４００では、前の処理で検出された有界平面からすべての候補分割面を探す。任意の一つの候補分割面について、入力された三次元モデルの頂点が候補分割面の両側に分布する場合、三次元モデル分割装置は、当該候補分割面は入力された三次元モデルを複数の部分に分割可能であると判定する。モデル分割ステップＳ４１０では、入力された輪郭図が一つのサブグラフ或は少なくとも二つの独立したサブグラフに分割されるまで、或はすべての候補分割面の処理を終えるまで、探し出した候補分割面を一つずつ利用して入力された輪郭図に対して分割を行う。終了条件判定ステップＳ４２０では、分割して取得したサブグラフに対して、引続き分割する必要があるかどうかを判定する。分割する必要がなければ、三次元モデル分割装置は、直接、当該サブグラフを出力する（Ｓ４３０）。分割する必要があれば、三次元モデル分割装置は、当該サブグラフが含んでいる候補分割面を利用して、引き続き分割を行う（Ｓ４４０）。
【００４６】
以下では、具体的な実施例で図４に示す各ステップの処理を詳細に記述する。
【００４７】
三次元モデル分割装置が実行する候補分割面検出ステップＳ４００は、検出された有界平面から候補分割面として三次元モデルの分割に適用可能なすべての有界平面を探し出す。各候補分割面は二つの条件を満たさなければならない。１）当該候補分割面上の頂点の数は４より小さくならない。頂点の数が４より小さい場合に、当該候補分割面に沿ってモデルを分割する際に、更に頂点を追加する必要があるので、処理が比較的複雑になる。２）当該候補分割面自体が含んだ頂点を除いて、その他の頂点は、当該候補分割面の両側に分布している。ここでいう「その他の頂点」とは、分割対象である三次元モデルのすべての頂点において当該候補分割面自体が含んだ頂点を除いた頂点をさす。最適化実施の形態として、三次元モデル分割装置は、当該候補分割面と繋がる頂点だけをその他の頂点として選んでもいい。こうすると、得られた候補分割面が相対的に少なくなり、三次元モデル分割装置は、処理の複雑さを軽減することができる。
【００４８】
例えば、図３Ａ-３Ｂで示す三次元モデルは２０個の頂点、３６個の三角形を含み、有界平面生成ステップによって、三次元モデル分割装置は、１２個の平面（記述の明瞭且つ簡潔のために、図では全部を示してない）を取得する。この中で、有界平面１には８個の頂点があり、また４個の頂点が有界平面１の上方に位置しており、８個の頂点が有界平面１の下方にある。したがって、三次元モデル分割装置は、有界平面１が同時に候補分割面の二つの条件を満たしているので、有界平面１を一つの候補分割面であると判定する。しかし、有界平面２には８個の頂点があり、その他の１２個の頂点は全部有界平面２の後方にある。したがって、三次元モデル分割装置は、有界平面２を候補分割面ではないと判定する。このステップの処理によって、三次元モデル分割装置は、図３Ａ-３Ｂで示す三次元モデルに一つの候補分割面を検出する。具体的には、三次元モデル分割装置は、候補分割面として有界平面１を検出する。
【００４９】
三次元モデル分割装置が実行するモデル分割ステップＳ４１０は、候補分割面に基づいて、入力された輪郭図を複数の重複しないサブグラフに分割する。図５は、図４に示したフローチャートにおけるステップＳ４１０の処理の一つの実施例を模式的に示すフローチャートである。当該ステップの処理では、入力された輪郭図が少なくとも二つのサブグラフに分割されるまで、或はすべての候補分割面が処理済になるまで（すなわち、すべての候補分割面を利用して分割を行うのは三次元モデルを一つサブグラフに分割する状況の詳細は後述する）、各候補分割面は逐一に試されたことが分かる。図５に示すように、三次元モデル分割装置は、選定されたある候補分割面に対しては、先ず当該選定された候補分割面によって輪郭図を一つのサブグラフ或は少なくとも二つの分離するサブグラフに分割する。しかも、それぞれのサブグラフには当該選定された候補分割面（ステップＳ５１０）が含まれている。続いて、三次元モデル分割装置は、前のステップで取得したサブグラフに穴があるかどうかを判定する。続いて、穴がある場合に、三次元モデル分割装置は、穴が独立に存在できないように穴を処理する（ステップＳ５２０）。最後に、三次元モデル分割装置は、パラメーター化処理を採用して分割結果をコントロールする（ステップＳ５３０）。以下では順番に各ステップの処理を説明する。
【００５０】
前の処理を経て取得した、入力された三次元モデルの候補分割面の数がｎ個（n3１）であると仮定する。ステップＳ５１０の処理では、ｎ個の候補分割面における第ｉ個の選定候補分割面に対して、各サブグラフに第ｉ個の選定された候補分割面が含まれるように、入力された輪郭図を選定された第ｉ個の候補分割面に沿って一つのサブグラフか或は少なくとも二つの分離するサブグラフに分割する。このために、当該処理は主に以下の三つの過程によって完成される。
【００５１】
１）三次元モデル分割装置は、前の輪郭図抽出処理で取得した輪郭図に対して修正を行い、修正された輪郭図を得る。すなわち、モデルの分割の準備のために選定された候補分割面にある輪郭線を削除する。図３Ａ-３Ｂに示す三次元モデルの中で、有界平面１を選定される候補分割面に仮定した場合、当該候補分割面は八つの頂点を含む。この八つの頂点の間の辺を削除した後、輪郭図は、図６に示す輪郭図になる。図６では、塗りつぶしの正方形と塗りつぶしの菱形で当該選定された候補分割面に属する頂点を表記する。
【００５２】
２）三次元モデル分割装置は、修正された輪郭図の頂点の間の接続関係に基づいて、修正後の輪郭図を一つのサブグラフ或は少なくとも二つの繋がらない、すなわち、分離するサブグラフに分割する。ここで、三次元モデル分割装置は、一つのサブグラフにおける頂点に他のサブグラフへの任意パスがなければ、その二つのサブグラフは分離していると判定する。
【００５３】
図６に示すように、修正した輪郭図は二つの互いに繋がらないサブグラフで構成されているから、三次元モデル分割装置は、入力されたモデルの各頂点を頂点間の接続関係に応じて、当該二つのサブグラフに分けることができる。サブグラフ１は、選定される候補分割面にある四つの菱形頂点と選定される候補分割面の上方にある四つの円形頂点を含む。サブグラフ２は、選定される候補分割面にある四つの正方形頂点と選定される候補分割面の下方にある八つの星形頂点を含む。
【００５４】
図７Ａ−７Ｃに示す実施例では、修正した輪郭図は、三つの互いに繋がらないサブグラフで構成され、入力されたモデルの各頂点を三つのサブグラフに相応して分け、それぞれ菱形、円形、星形で表記する。
【００５５】
図８Ｂ−８Ｃに示す実施例中で、修正した輪郭図は、三つの互いに繋がらないサブグラフで構成され、入力されたモデルの各頂点は三つのサブグラフに相応して分け、それぞれ菱形、円形、星形で表記する。
【００５６】
図９Ｂに示す実施例中で、修正した候補分割面によって、入力された輪郭図を四つのサブグラフに分割することができ、サブグラフ１、２、３、４と表記する。
【００５７】
図１０Ｂに示す実施例中で、修正した候補分割面によって、入力された輪郭図を二つのサブグラフに分割し、サブグラフ１とサブグラフ２と表記する。
【００５８】
３）三次元モデル分割装置は、上述の過程、２）で取得した各サブグラフに対して、すべてのサブグラフが選定された分割面を含むように必要な再編成を行う。
【００５９】
三次元モデル分割装置は、選定された候補分割面を含むかどうかによって、前の過程、２）で取得した各サブグラフを二つの種類に分けることができる。第一種類は、選定された候補分割面を含み、第二種類は、選定された候補分割面を含まない。前のステップにおけるサブグラフが何れも第一種類に属する場合に、三次元モデル分割装置は、これらのサブグラフに対して新たに処理を実行する必要がない。
【００６０】
図６に示すように、サブグラフ１とサブグラフ２は、いずれも選定された分割面を含んでいるので、三次元モデル分割装置は、これらのサブグラフに対して更に処理する必要がない。図９Ｂと図１０Ｂに示す各サブグラフは、何れも選定された分割面を含んでいるから、三次元モデル分割装置は、これらのサブグラフも更なる処理をする必要がない。
【００６１】
図７Ｃで示す三次元モデルでは、三次元モデル分割装置は、選定された候補分割面に基づいて、サブグラフ１、サブグラフ２とサブグラフ３という三つのサブグラフを取得することができる。サブグラフ１とサブグラフ３は図７Ａで表記した候補分割面を含み、第一種類に属する。サブグラフ２は選定された候補分割面を含まないので、第二種類に属する。このため、三次元モデル分割装置は、当該分割結果を更に処理する必要がある。
【００６２】
図８Ａ−８Ｃで示すモデルでは、三次元モデル分割装置は、選定される候補分割面によってサブグラフ１、サブグラフ２とサブグラフ３という三つのサブグラフを得ることができる。その中でサブグラフ１とサブグラフ３は、図８Ａで表記した候補分割面を含み、第一種類に属する。しかし、サブグラフ２は、選定される候補分割面を含まないので、第二種類に属する。したがって、三次元モデル分割装置は、当該分割結果を更に処理する必要がある。
【００６３】
第二種類のサブグラフが存在する場合、三次元モデル分割装置は、これらのサブグラフを処理する必要がある。三次元モデル分割装置は、第二種類のサブグラフに対して以下の二種類の状況に応じてそれぞれ処理すべきである。
【００６４】
１）当該サブグラフの各頂点がすべて選定される分割面の同じ側にある。三次元モデル分割装置は、頂点隣接グラフ或は当該サブグラフを取得するように分割された輪郭図を通して、当該サブグラフをそれと繋がっており且つ同じ側にあるサブグラフと新たに組み合わせて一つの新しいサブグラフを得る。そして、三次元モデル分割装置は、当該サブグラフを第二種類のサブグラフから削除する。ここで、サブグラフとサブグラフが繋がるというのは、頂点隣接グラフ或は当該サブグラフを取得するように分割された元の輪郭図のこれらのサブグラフの頂点間に接続が存在することを示す。すなわち、少なくとも一つの共通点を持つ。
【００６５】
図７Ｃで示す実施例の中で、三つのサブグラフと選定される分割面それぞれとの関係は、サブグラフ１の各頂点は選定される分割面の上方にあり、サブグラフ２とサブグラフ３の各頂点は選定される分割面の下方にあることになる。これと同時に、頂点隣接グラフを通して、サブグラフ２とその他の二つのサブグラフの頂点の間には接続が存在する。したがって、三次元モデル分割装置は、サブグラフ２とサブグラフ３を合併させ、一つの新しいサブグラフを構成する。三次元モデル分割装置は、サブグラフ２とサブグラフ１は合併しない。これはサブグラフ２とサブグラフ１が同じ側にないからである。この時、三次元モデル分割装置は、図７Ｃで示すモデルを図７Ｄに示す二つの部分に分けることができる。また、この二つの部分は何れも選定される分割面を含み、図７Ｄにおけるサブグラフ１’が図７Ｃにおけるサブグラフ１に対応し、サブグラフ２’が図７Ｃにおけるサブグラフ２と３を組み合わせて取得したサブグラフに対応することが分かる。
【００６６】
２）当該サブグラフの頂点は、選定される候補分割面の両側に分布しており、かつ頂点隣接グラフ或は当該サブグラフを取得するように分割された輪郭図を通して、第一種類に属するサブグラフと繋がっている場合に、当該サブグラフと繋がる第一種類の各サブグラフを一つの新しいサブグラフに新たに組み合わせ、当該サブグラフを第二種類サブグラフから削除する。
【００６７】
図８Ｃに示す実施例では、三つのサブグラフと候補分割面の関係は、サブグラフ１の頂点は、選定される候補分割面の上方にあり、サブグラフ２の頂点は、選定される選定分割面の両側に分布し、サブグラフ３の頂点は、選定分割面の下方にある。同時に、サブグラフ２の頂点は、頂点隣接グラフを通してサブグラフ１とサブグラフ３の頂点と繋がる。したがって、三次元モデル分割装置は、サブグラフ２をサブグラフ１、３と合併し、一つの新しいサブグラフを構成する。すなわち、図８で示す三次元モデルは、選定される候補分割面を利用して分割を実行してから一つのサブグラフを得て、分割する入力された三次元モデルと対応するサブグラフである。当然ながら、三次元モデル分割装置は、他の方式を採用して図８Ａ-８Ｃで示すモデルを少なくとも二つのサブグラフに分割することができるが、これは開示技術の検討の範囲にないので、ここでは詳しく述べないことにする。
【００６８】
続いて、三次元モデル分割装置は、ステップＳ５２０において、ステップＳ５１０で取得した各サブグラフの間の関係及びこれらサブグラフと選定される候補分割面の位置関係に基づいて、各サブグラフが穴に対応しているかどうかを判定する。それから、三次元モデル分割装置は、入力されたモデルの形状が分割後も変化しないことを維持するように穴を処理する。穴がある場合に、三次元モデル分割装置は、分割結果の中に独立した穴がないように、穴と穴に一番近い実体とを結合させる。このために、ステップＳ５２０の処理は、三つのサブステップを含む。１）、三次元モデル分割装置は、各サブグラフに対して、その輪郭情報に基づいて、選定される分割面における対応する有界区域を取得する。２）、三次元モデル分割装置は、各サブグラフに対して、それが穴であるかどうかを判定する。３）、三次元モデル分割装置は、穴と判定されたサブグラフに対して処理を行う。以下では順番にこの三つのサブステップを説明する。
【００６９】
１）三次元モデル分割装置は、前のステップＳ５１０で取得した各サブグラフに対して、選定される分割面における各領域を取得する。
【００７０】
三次元モデル分割装置は、各サブグラフに対して、その選定される候補分割面における輪郭線の情報に基づいて、閉鎖領域、すなわち、輪郭線が閉鎖する領域を取得する。輪郭線が閉鎖してない状況について、例えば、開示技術では公知の頂点凸包方法を採用して近似な閉鎖領域を取得することができ、或は既存の他の方法を採用して相対的に正確な閉鎖領域を取得する。なお、具体的な説明はここで述べないことにする。
【００７１】
本ステップを通じて、三次元モデル分割装置は、例えば図９Ｂに示す四つのサブグラフに対して、図９Ｃに示す四つの閉鎖領域を取得することができる。
【００７２】
２）三次元モデル分割装置は、本サブステップは前のサブステップで取得したサブグラフの選定される候補分割面での各閉鎖領域間の関係、及び各サブグラフと選定される候補分割面間の関係を利用して、穴の判定を実行する。三次元モデル分割装置が実行するこのステップでは、各サブグラフの選定される候補分割面にある閉鎖領域の間の関係によって、外から内へと逐一に判定する。
【００７３】
三次元モデル分割装置は、先ず一番外側にある閉鎖領域に対応するサブグラフを実体と判定する。ここで、「実体」は「穴」と区別していうものである。この規則は実際状況に合うものである。この規則に基づいて、図９Ｂに示す実施例で、三次元モデル分割装置は、サブグラフ１が対応する部分を実体であると判定する。三次元モデル分割装置は、図１０Ｂで示す二つのサブグラフは、サブグラフ１の選定される候補分割面にある閉鎖領域がサブグラフ２の相応する閉鎖領域の外側にあるから、サブグラフ１が対応する部分を実体であると判定する。
【００７４】
以下では、一番外側にある閉鎖領域に対応するサブグラフを除いたその他のサブグラフの判定方法を説明する。説明の明瞭、簡潔のために、先ず、あるサブグラフに「一番近いサブグラフ」という概念を定義する。あるサブグラフＡについて、それに一番近いサブグラフＢは先ず一つの実体でなければならず、同時にサブグラフＢが対応する領域はサブグラフＡが対応する領域を含まなければならない上にすべてのサブグラフＡの対応領域を含む領域の中で一番小さいものである。図９Ｃに示すように、サブグラフ３について、サブグラフ１がそれと対応する一番近いサブグラフである。サブグラフ１の対応する領域はサブグラフ３の対応領域を含むすべての領域の中で一番小さく、且つサブグラフ１に対応する部分が実体であるからである。同様に、サブグラフ１はサブグラフ２と４に対応する一番近いサブグラフでもある。
【００７５】
あるサブグラフとそれと一番近いサブグラフの関係、及びそれらと選定される分割面の位置関係に基づいて、三次元モデル分割装置は、以下の原則に応じてそのサブグラフが一つの穴を代表するかどうかを判定する。
三次元モデル分割装置は、当該サブグラフとそれと一番近いサブグラフの各頂点が選定される候補分割面に対して完全に反対の位置にある場合に、当該サブグラフは実体であると判定する。図９Ｃに示すように、選定される候補分割面の上の各頂点を除いて、サブグラフ３の各頂点は、すべて選定される分割面の前方にあるが、サブグラフ１の各頂点はすべて選定される分割面の後方にある。したがって、三次元モデル分割装置は、サブグラフ３の対応する部分は実体であると判定する。
三次元モデル分割装置は、当該サブグラフとそれと一番近いサブグラフの各頂点が選定される分割面に対して同じ側にある場合に、当該サブグラフは穴があると判定する。図９Ｃに示すように、選定される分割面の上の各頂点を除いて、サブグラフ２の各頂点は選定される分割面の後方に位置し、同時にサブグラフ１の各頂点も選定される分割面の後方にある。したがって、三次元モデル分割装置は、サブグラフ２が対応する部分は穴と判定する。同様に、三次元モデル分割装置は、サブグラフ４が対応する部分も穴と判定する。
以上の二つの原則を全部満足しない場合には、以下の原則を使う。選定される候補分割面を基準とし、当該サブグラフの当該選定される分割面にある頂点から出発して他の有界平面に接続した方向性ある線分と当該選定される候補分割面の法線ベクトルが選定される候補分割面の両側にある場合、当該サブグラフが対応する部分は穴と判定する。そうではないときは、実体と判定する。ここでの接続は輪郭線を通してつながり、すなわち、当該サブグラフに属しかつ選定される候補分割面に位置している頂点から出発して、他の有界平面上の頂点までのつながり線を指す。ここでは有界平面の法線方向がモデルの表面の外側に指していることをデフォルトとしている。図１０Ｂに示すように、サブグラフ２の選定される分割面にある頂点から出発して、他の有界平面に接続した輪郭線（一点鎖線で表す）と選定される分割面の法線ベクトル（実線で表す）が当該選定される候補分割面の両側にある。すなわち、一つは当該選定される候補分割面の下側にあり、一つはその上側にあるから、三次元モデル分割装置は、サブグラフ２が対応する部分は穴であると判定する。
【００７６】
３）穴に対しての処理のサブステップでは、入力された三次元モデルの形状を保つために、各穴とそれと一番近いサブグラフを組み合わせ、分割の結果に独立の穴が存在しないようにしなければならない。図９Ｃに示すように、サブグラフ２とサブグラフ４はサブグラフの１に組み合わせられ、一つの新しい実体になる。図１０Ｂで示すサブグラフ２はサブグラフ１に組み合わせられ、一つの新しい実体になる。
【００７７】
それから、三次元モデル分割装置は、穴のみに含まれている有界平面を非候補分割面と設定する。これによって穴が切られることを防止できると同時に、モデルの分割の複雑さと処理負荷を減らすことができる。
【００７８】
図５のフローチャートにおけるステップＳ５３０で、三次元モデル分割装置は、パラメーター化コントロール処理を実行する。応用によって、このステップではパラメーターを設定することができ、分割結果に対してコントロールを行い、例えば小さい部分だけ或は大きい部分だけが入力された三次元モデルから切り離される。例えば、あるサブグラフＡが切り離されることができるかどうかを判定するために、サブグラフＡとそれと一番近いサブグラフが選定される候補分割面上にある相応する閉鎖領域の面積の比をパラメーターとする。この比が予め設定されるある閾値より小さい場合に、サブグラフＡは、切り離される。この比が予め設定されるある閾値より大きい場合に、サブグラフＡは、それと一番近いサブグラフと組み合わせて一つの新しいサブグラフになる必要があり、独立した部分として切り離されない。
【００７９】
以下では、一つの実施例をもって具体的に説明する。図１１に示すように、実体１の選定される候補分割面での対応する閉鎖領域の面積はＡｒｅａ１=３９２.９９４と算出され、実体２の分割面での対応する閉鎖領域の面積はＡｒｅａ２=１１９.５６であり、Ａｒｅａ２/Ａｒｅａ１=０.３になる。ユーザーが設定した閾値が０.３より小さい場合に、三次元モデル分割装置は、実体２を切り離さずに、実体１と一つの物体に組み合わせる。ユーザーが設定した閾値が０.３以上の場合に、三次元モデル分割装置は、実体２と実体１はそれぞれ二つの物体として切り離す。注意すべきことは、図１１でのモデルは、図９でのモデルに対応している。前記で言ったように、図９で、二つのサブグラフ２と４は、何れも穴と判定され、且つサブグラフ１と組み合わせられる。したがって、図１１での実体１というのは図９におけるサブグラフ１＋２＋４で構成される新しい実体をさす。
【００８０】
当業者は、また他のパラメーターを設定して三次元モデルの「大」と「小」を表すことができるのが分かる。例えば、三次元モデル分割装置は、サブグラフが対応している部分の体積の大きさの比を通して、相応する部分が入力された三次元モデルから分割されるか否かを判定することができる。
【００８１】
三次元モデル分割装置は、ステップＳ５３０でのパラメーター化コントロール処理を必ず実行しなければならないものではない。この処理はモデルの分割の実用性を高めるものであるから、一種の最適化方案に属する。例えば、三次元モデル分割装置は、関連するパラメーターと閾値を設定することによって、三次元モデルの分割の「粒度」、すなわち、三次元モデルから切り離されるサブモデルが少し多いかもしくは少し少ないかをコントロールすることができる。これは実際の必要にあわせて相応する調整を行うことができるということは明らかなことである。
【００８２】
続いて、図５のフローチャートでのステップＳ５４０では、三次元モデル分割装置は、第ｉ個の選定される候補分割面を利用して上述の分割処理を行ってから取得したサブグラフの数が「１」より大きいか否かを判定する。すなわち、三次元モデル分割装置は、入力された三次元モデルを少なくとも二つのサブグラフに分割するかどうかを判定する。ステップＳ５４０の判定結果が「Ｙｅｓ」であれば、三次元モデル分割装置は、ステップＳ５５０で分割して取得したサブグラフを出力して図４のステップＳ４２０に戻る。ステップＳ５４０の判定結果が「Ｎｏ」であれば、三次元モデル分割装置は、ｉ=ｉ＋１（ステップＳ５６０）にし、第（ｉ+１）個の選定される候補分割面を利用して、ステップＳ５１０からＳ５４０までの処理を繰り返す。ここで、ステップＳ５４０の判定結果が「Ｎｏ」であるとは、第ｉ個の選定される候補分割面を利用して上述の分割処理を行ってから取得したサブグラフの数が「１」より大きくない（もしくは、１と同じ）場合である。ｎ個の候補分割面におけるすべての分割面を利用して分割を行った結果、三次元モデルを少なくとも二つのサブグラフに分割することができない場合、フローは同様に図４におけるステップＳ４２０に戻る。ここで、三次元モデルを少なくとも二つのサブグラフに分割することができないとは、入力された三次元モデルを一つのサブグラフにしか分割しない場合（ステップＳ５８０）である。例えば、図９Ａ−９Ｃで示す状況が入力された三次元モデルを一つのサブグラフ、すなわち、その三次元モデル自体と対応するサブグラフに分割することである。図５から分かるように、ｎ個の候補分割面における任意の一つの分割面が三次元モデルを少なくとも二つの重複しないサブグラフに分割することができれば、図４におけるステップＳ４２０に入る。そして、これらのサブグラフの分割結果に対して分割を終わらせるかどうかを判定し、ｎ個の候補分割面における他の分割面を利用して三次元モデルを分割する処理をそれぞれ行わない。当業者は，別の選択方案として、ｎ個の候補分割面における各分割面を順番に利用して、上述のような入力された三次元モデルを分割する処理を行うこともできる。そして、当業者は、これによって取得した各候補分割面と対応する各種の分割結果を実際の必要に応じて選択して使うことができる。
【００８３】
その他、上述の候補分割面を利用して三次元モデルに対して分割を行う処理では、候補分割面を探さず、直接、前の処理で検出された全部の有界平面を分割面として利用して三次元モデルの輪郭図に対して分割を行ってもよい。その処理の方式は上述の候補分割面を利用する分割処理方式と似ているから、ここでは詳しく述べない。
【００８４】
図４のプロセスに戻る。ステップＳ４２０では図５のステップＳ５５０或はＳ５８０の処理で取得したサブグラフに対して終了条件の判定を行い、当該サブグラフが引き続きの分割を必要とするか否か、すなわち、分割を終了する条件を満たすかどうかを判定する。三次元モデル分割装置は、以下の原則を採用して判定を実行することができ、あるサブグラフが以下の原則の任意の一項目を満たす場合に、当該サブグラフは引き続きの分割を必要としないと判定する。
当該サブグラフの頂点の数が８より小さい。これは任意の三次元物体が少なくとも四つの面を共有しない頂点を持たなければならないからである。例えば三角錘は分割されない。ここで、数字「４」は、モデルが分割できるのに許容する最小の数字であり、この数字は実際の状況によって変更することができる。
当該サブグラフの面の数は６より小さい。これは任意の三次元物体が少なくとも四つの異なる平面を含まなければならないからである。例えば三角錘は分割されない。数字「４」は、モデルが分割できるのに許容する最小の数字であり、この数字は実際の状況によって修正変更することができる。
当該サブグラフのすべての有界平面には候補分割面が存在しない。例えば図６のサブグラフ１が含む六つの有界平面には候補分割面が存在しない。同様に、図６に示すサブグラフ２、図７に示すサブグラフ１は、何れも候補分割面を含んでいない。
当該サブグラフは候補分割面を含んでいるが、候補分割面はいずれも当該サブグラフを複数の部分に分割することができない。図１０のモデルに、サブグラフ１は候補分割面を含んでいるが、その分割面を通して当該サブグラフを複数の部分に分割することができないから、当該モデルは引き続き分割ができない。
【００８５】
ステップＳ４２０の判定で、あるサブグラフに対して引き続きの分割を必要とすると判定される場合に、三次元モデル分割装置は、当該サブグラフが含んでいる候補分割面を使ってこれに対して引き続き分割を行う（Ｓ４４０）。すなわち、三次元モデル分割装置は、当該サブグラフが含んでいる候補分割面を選定される候補分割面として、当該サブグラフと対応する輪郭図が少なくとも二つの互いに重複しないサブグラフに分割されるまで、当該サブグラフが対応する輪郭図に対して分割を行う。サブグラフに対する接続分割の具体的処理方式は上述の図４−５を参照しながら述べた分割処理と類似しているので、ここでは述べない。
【００８６】
以上では、各図面を参照して、開示技術の実施例による三次元モデルに対する分割の方法を詳しく記述した。代わりとして実施が可能な形態として、開示技術の実施例による三次元モデル分割方法のフローチャートの略図を示す図１において、有界平面生成ステップＳ１１０を実行する前に、三次元モデルの予分割ステップをさらに実行することもできる。三次元モデル分割装置が実行する予分割ステップは、入力された三角形ポリゴンで表現される前記三次元モデルを複数の独立した、互いに繋がらない部分に分割する。当該ステップの処理は、特に一つの情景に複数の独立した物体が置いてある状況に適用する。当該ステップの処理では、三次元モデル分割装置は、先ず、入力された三次元モデルの三角形ポリゴンデータに基づいて、頂点隣接グラフを構築する。それから、三次元モデル分割装置は、頂点隣接グラフがつながっているかどうかを判定する。三次元モデル分割装置は、頂点隣接グラフの任意の１対のノードの間に接続パスが存在する場合に、このグラフは繋がっていると判定し、そうでなければ，繋がっていないと判定する。ここでのパスは、普通、一辺か或は複数の辺で構成されているものである。頂点隣接グラフがつながっておらず、すなわち、隣接グラフが複数の互いにつながっていない、分離しているサブグラフで構成される場合には、これらのサブグラフに対応して、入力された三次元モデルは、複数の互いに繋がらないサブモデルに分割できる。頂点隣接グラフが繋がっている場合には、入力された分割対象である三次元モデルは、予分割のステップで分割されなく、まだ一つの三次元モデルである。
【００８７】
図１２Ａ−１２Ｃは、開示技術の実施例による三次元モデル分割方法において分割する三次元モデルを予め複数の互いに分離するサブモデルに分割することを模式的に示す図である。図１２Ａは入力された分割対象である三次元モデルを表し、図１２Ｂは構築した頂点隣接グラフであり、頂点隣接グラフが四つの互いに繋がらない、分離しているサブグラフで構成されているのが分かる。これに相応して、図１２Ａのモデルは、図１２Ｃに示す四つの独立したサブモデルに分割される。
【００８８】
別の方案として、三次元モデル分割装置は、三角形隣接グラフを採用して上述のモデル予分割の処理を実現することができる。三角形隣接グラフが繋がらない時、三次元モデル分割装置は、入力された三次元モデルを複数の独立したサブモデルに分割することができる。前記の開示技術の具体的実施例による記述から分かるように、分割対象である三次元モデルは二つの部分の基本データを含む。すなわち、モデル頂点及びモデル表面を構成する三角形である。三次元モデル分割装置は、三角形隣接グラフを複数の分離するサブグラフに分割し、すなわち三次元モデルの表面を構成している三角形を分けると、モデルの頂点を分けることができる。三次元モデル分割装置は、頂点隣接グラフを複数の分離しているサブグラフに分割し、すなわちモデルの頂点を分けると、入力されたモデルの表面を構成している三角形を分けることができる。したがって、三角形隣接グラフを採用してモデルの予分割処理を実行する処理は、上述の頂点隣接グラフを採用してモデルの予分割処理を実行することと類似しており、ここでは詳細を述べないことにする。
【００８９】
入力されたモデルが予分割により複数の三次元サブモデルに分割される場合に、分割で得られた三次元サブモデルのそれぞれに対して上述の処理を行う。この予分割処理は、後続の処理の計算量と複雑度を下げるのに役立つから、これは最適化の処理であるということは容易に理解できる。モデルの予分割処理を実行しなくても、開示技術による三次元モデルの分割の実行には影響しない。
【００９０】
もう一つの別の実施の形態として、図１のフローチャートのステップＳ１３０の後、三次元モデルの輪郭図の再構成処理を実行することもできる。三次元モデルの輪郭図の再構成処理で、ステップＳ１２０で取得した、入力された三次元モデルの輪郭図、及び当該輪郭図が含む有界平面の情報に基づいて、選定される候補分割面を利用して三次元モデルを分割することにより取得した各サブグラフに対して処理を行い、これによって分割対象である三次元モデルを構成する相応する立体コンポーネントを再構成し、三角形ポリゴンでそれを表現する。上述のように、選定される候補分割面を利用してモデルの分割を行う過程で、選定される候補分割面及びその他の一部の有界平面に変化が発生する可能性がある。これらの有界平面が新たに三角化されなければ、三次元モデルの閉鎖性を確保することができない。これと同時に、変化が起らなかった有界平面のデータは、そのまま使用することができ、それによって再構成の処理負荷を減らす。その他、入力された三次元モデルの元の三角形ポリゴンデータは、新しく生成された三角形の方向を補正するのに役立つ。
【００９１】
具体的に、三次元モデル分割装置は、分割の過程で変化が生じた有界平面に対して、上述の穴であると判定したサブグラフに対する処理に類似した処理方法を採用し、この有界平面上の閉鎖領域を取得して、それを多角形で表すことができる。三次元モデル分割装置は、既知の各種の多角形の三角化技術を採用して、多角形から一連の三角形を取得することができる。例えば、三次元モデル分割装置は、上述の「非特許文献６」に開示された方法を採用することができる。この方法は簡単な多角形（凹多角形と凸多角形を含む）と複雑な多角形（穴を含む多角形）の三角化を実現することができる。この方法を応用する前に、三次元モデル分割装置は、先ず、各多角形の方向及び多角形の間の含み関係を判定する必要がある。このため、三次元モデル分割装置は、一番外側にある多角形の方向が時計回りと逆方向で、内部の多角形の方向が時計回りの方向になるように各多角形を適宜に構成させる。例えば、三次元モデル分割装置は、上述の「非特許文献９」で公開した方法で多角形の方向を判定することができる。三次元モデル分割装置は、すべての変化が生じた有界平面に対して再構成処理が終わってから、三次元モデルの元の三角形ポリゴンデータに基づいて、すべての三角形の法線方向が三次元モデルの表面の外側に向くように、新しく生じた三角形の方向を補正する。
【００９２】
三次元モデル分割装置は、三次元モデルの輪郭図の再構成処理を経てから、入力された分割対象である三次元モデルを構成する、三角形ポリゴンデータで表現される一連の閉鎖した立体コンポーネントを取得することができる。
【００９３】
ここで、説明すべきことは、もっとはっきりと開示技術実施例に基づく三次元モデル分割方法を説明するために、各処理ステップは異なる図面における異なるモデルの実施例を参照しながらそれぞれ説明した。しかし、当業者は、上述の各図面で言及したモデルのそれぞれに対して、開示技術に基づくこのような三次元モデル分割方法で分割処理を行うことができることが分かる。詳細はここでは述べないことにする。
【００９４】
開示技術のほかの実施例に基づいて、三次元モデルを分割する装置も提供する。図１３は、開示技術の実施例の三次元モデル分割に用いられる装置を模式的に示すブロック図である。図１３に示すように、当該三次元モデルを分割する装置１０００は、有界平面生成部１２００と、輪郭図抽出部１３００と、輪郭図分割部１４００とを含む。有界平面生成部１２００は、入力された三次元モデルの三角形ポリゴンデータに基づいて、三次元モデルに含まれるすべての三角形を処理し、三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する。輪郭図抽出部１３００は、生成した有界平面を通して三次元モデルの輪郭図を抽出する。輪郭図分割部１４００は、生成した有界平面の情報及び三次元モデルの頂点隣接グラフの情報に基づいて、抽出した輪郭図を一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する。
【００９５】
別の実施の形態として、図１３での三次元モデルを分割する装置１０００は、予分割部１１００を更に含むことができる。予分割部１１００は、入力された三次元モデルの三角形ポリゴンデータに含む三角形データと頂点データに基づいて、入力された三次元モデルを一つのサブモデル或は少なくとも二つの互いに分離するサブモデルに予分割する。有界平面生成部１２００、輪郭図抽出部１３００と輪郭図分割部１４００は、サブモデルのそれぞれを一つのサブモデル或は少なくとも二つの互いに分離しているサブモデルに分割するように、予分割部１１００で生成された一つのサブモデル或は少なくとも二つの互いに分離しているサブモデルにおける各モデルに対して相応する処理を実行する。
【００９６】
もう一種の別の実施の形態として、図１３での三次元モデルを分割する装置１０００は、モデル再構成部１５００を更に含む。モデル再構成部１５００は、三次元モデルを構成する、三角形ポリゴンで表現される一連の立体コンポーネントを再構成するように、分割された一つサブグラフ或は少なくとも互いに重複しない二つのサブグラフ及び三次元モデルの三角形ポリゴンデータに基づいて三角化の処理を実行する。
【００９７】
当業者は、図１３で示す三次元モデル分割装置１０００が含む有界平面生成部１２００、輪郭抽出部１３００、輪郭図分割部１４００、予分割部１１００及びモデル再構成部１５００は、上述の図１、図４、図５を参照して説明した各種の処理、及びこれらの図面では示していないが既に上記の各種の具体的実施例で十分に説明した前記三次元モデル分割方法を実行するように配置されることが分かる。
【００９８】
開示技術の実施例に対して、図面と合わせて説明を参照することにより、開示技術の前述した内容及びその他の目的、特徴及び優れているところを更に理解しやすくなる。図面でのコンポーネントは実際の比率に照らして描かれたものではなく、ただ開示技術の原理を示すためである。なお、すべての図面において、同一或は類似した技術特徴またコンポーネントは、同一或は類似した記号で表示される。
【００９９】
以上の開示技術の具体的実施例に関する記述の中で、一種の実施の形態に対して記述及び/又は示した特徴は、同一或は類似の方式で一つ或はより多くの他の実施の形態で使用されることができる。
【０１００】
強調すべきことは、用語「含む/含まれる」が本文で使用される場合は、特徴、要素、ステップ或はコンポーネントの存在を指し、一つ或はより多くのその他の特徴、要素、ステップ或はコンポーネントの存在又は付加を排除しない。
【０１０１】
なお、開示技術の方法は明細書に述べた説明の順番で実行することに限らず、他の説明に従って順番に、並行的に或は独立的に実行してもよい。したがって、本明細書で述べた方法の実行順番は開示技術の技術範囲を限定しない。
【０１０２】
以上で、開示技術の具体的な実施例に関する記述を通して、開示技術を説明したが、理解するべきは、当業者は添付された請求項の技術的思想の範囲以内で、開示技術に対しての各種の修正、改良或は同等ものが設計できる。これらの修正、改良或は同等であるものは開示技術の保護範囲内に含まれるものと認められるべきである。
【０１０３】
上述の装置における各構成部は、ソフトウェア、ハードウェア或はこれらの組み合わせの方式で配置することができる。配置で使える具体的手段或は方式は、当業者の良く知っているものであるので、ここでは詳しく述べないことにする。
【０１０４】
また、開示技術の他の実施例は、画像処理システムを提供する。この画像処理システムは上述の図１３で示した開示技術の実施例による三次元モデル分割装置を備えるので、上述の開示技術の実施例による三次元モデル分割方法を実行するのに適用することができる。
【０１０５】
この画像処理システムは、例えば目標検査システム、部分マッチングシステム、モデル検索システムなどである。
【０１０６】
また、開示技術のその他の実施例による三次元モデルを分割する方法は、機器が読取り可能な指令コードが格納されているプログラムの製品を通して実現することができる。このような指令コードは、機器、例えばコンピュータ、に読み取られて実行される時に、上述の開示技術の実施例による三次元モデル分割方法の全部の操作過程とステップを実行することができる。そのプログラム製品は、任意の表現形式を持つことができ、例えば目標プログラム、インタプリターで実行するプログラム或は操作システムに提供したシナリオプログラムなどである。
【０１０７】
それに相応して、上述の機器が読取り可能な指令コードが格納されているプログラムの製品を載せている記憶媒体も開示技術の公開に含まれる。前記記憶媒体は、フロッピー（登録商標）ディスク、光ディスク、光磁気ディスク、メモリーカード、メモリースティックなどを含むがこれらに限定されない。
【０１０８】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１０９】
（付記１）三次元モデル分割装置が、
入力された三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルに含まれるすべての三角形を処理し、当該三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する有界平面生成ステップと、
前記生成した有界平面を通して前記三次元モデルの輪郭図を抽出する輪郭図抽出ステップと、
前記生成した有界平面の情報及び前記三次元モデルの頂点隣接グラフの情報に基づいて、前記抽出した輪郭図を所定条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する輪郭図分割ステップとを含み、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルの頂点をノードとして、一つ或は複数の三角形に共有される二つの頂点の間ごとに一辺を追加して前記頂点隣接グラフの構築をすること
を特徴とする三次元モデル分割方法。
【０１１０】
（付記２）三次元モデル分割装置が、
前記有界平面生成ステップの前に、入力された三次元モデルの三角形ポリゴンデータに含む三角形データと頂点データに基づいて、当該入力された三次元モデルを一つのサブモデル或は少なくとも二つの互いに分離するサブモデルに予分割する予分割ステップを更に含み、
前記サブモデルのそれぞれを所定の条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割するように、当該サブモデルそれぞれに対してそれぞれ前記有界平面生成ステップ、前記輪郭図抽出ステップ及び前記輪郭図分割ステップを実行すること
を特徴とする付記１に記載の三次元モデル分割方法。
【０１１１】
（付記３）前記予分割ステップは、
前記三次元モデルの三角形ポリゴンデータに基づいて頂点隣接グラフを構築し、
前記頂点隣接グラフが繋がっているかどうかを判定し、当該頂点隣接グラフにおける何れか１対の頂点の間に接続パスが存在すれば、当該頂点隣接グラフは繋がっていると判定し、当該頂点隣接グラフにおける何れか１対の頂点の間に接続パスが存在しなければ、繋がっていないと判定し、
前記頂点隣接グラフが繋がっていないと判定すれば、当該頂点隣接グラフに互いに繋がらないサブグラフに対応して前記三次元モデルを少なくとも二つの互いに分離するサブモデルに分割すること
を特徴とする付記２に記載の三次元モデル分割方法。
【０１１２】
（付記４）前記予分割ステップは、
前記三次元モデルの三角形ポリゴンデータに基づいて三角形隣接グラフを構築することと、
前記三角形隣接グラフが繋がっているかどうかを判定し、ここで、当該三角形隣接グラフにおける何れか１対の三角形の間に接続パスが存在すれば、当該三角形隣接グラフは繋がっていると判定し、当該三角形隣接グラフにおける何れか１対の三角形の間に接続パスが存在しなければ繋がっていないと判定することと、
前記三角形隣接グラフが繋がっていないと判定すれば、当該三角形隣接グラフに互いに繋がらないサブグラフに対応して前記三次元モデルを少なくとも二つの互いに分離するサブモデルに分割することを含み、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルにおける三角形をノードとして、共通点を有する二つの三角形の間ごとに辺を追加して前記三角形隣接グラフを構築すること
を特徴とする付記２に記載の三次元モデル分割方法。
【０１１３】
（付記５）三次元モデル分割装置が、
前記輪郭図分割ステップの後に、前記三次元モデルを構成する、三角形ポリゴンで表現される一連の立体コンポーネントを再構成するように、前記分割された一つのサブグラフ或は少なくとも互いに重複しない二つのサブグラフ及び当該三次元モデルの三角形ポリゴンデータに基づいて三角化の処理を実行するモデル再構成ステップを更に含むこと
を特徴とする付記１ないし４の何れか一項に記載の三次元モデル分割方法。
【０１１４】
（付記６）前記有界平面生成ステップは、
前記三次元モデルに含まれるすべての三角形それぞれを一つのサブ平面として、すべてのサブ平面を合成できなくなるまで、合成条件を満たすサブ平面を一つの新しいサブ平面に合成して広義の平面を生成し、
前記三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成するように、前記広義の平面のそれぞれに対して以下の処理を実行することを含み、
前記広義の平面にある三角形に対して三角形隣接グラフを作成し、
前記三角形隣接グラフで前記広義の平面の三角形が複数の分離するサブ平面に分けることができ、且つ当該サブ平面のそれぞれが複数の互いに接続する三角形を含む場合に、当該広義の平面を前記複数の分離するサブ平面に分け、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルにおける三角形をノードとして、共通点を有する二つの三角形の間に一辺を追加して前記三角形隣接グラフを構築し、
前記広義の平面を分けて得る前記複数の分離するサブ平面における複数のサブ平面を同時に他の同一の平面と繋がっている場合に、これらのサブ平面を一つの組み合わせる有界平面として組み合わせ、
前記組み合わせた有界平面及び前記広義の平面を分けて得る前記複数の分離するサブ平面における組み合わせる必要のない有界平面によって前記三次元モデルの分割に適用する前記有界平面を共同で構成し、
前記複数のサブ平面がそれぞれ前記他の同一の平面との間に少なくとも一つの共通点が存在する場合に、当該複数のサブ平面は同時に当該他の同一の平面と互いに繋がると判定し、
前記頂点隣接グラフにおいて、あるサブ平面に繋がる頂点が当該サブ平面の同じ側に位置する場合に、当該サブ平面は前記組み合わせる必要のない有界平面における独立する有界平面と判定すること
を特徴とする付記１ないし５の何れか一項に記載の三次元モデル分割方法。
【０１１５】
（付記７）前記有界平面生成ステップにおいて、サブ平面を合成できる条件は、
前記サブ平面の法線方向が同じ又は反対であることと、
前記サブ平面の頂点が同一の平面に位置することを含み、
前記サブ平面と関連する三角形の法線方向を当該サブ平面の法線方向とすること
を特徴とする付記６に記載の三次元モデル分割方法。
【０１１６】
（付記８）前記輪郭図抽出ステップは、
前記三次元モデルの頂点を輪郭図の頂点とし、各頂点の間には接続が存在せず、
前記有界平面生成ステップで生成したそれぞれの有界平面に対して、当該有界平面生成ステップで生成した有界平面から当該有界平面と繋がる有界平面を探し、
前記有界平面と当該有界平面と繋がっている有界平面の境界線に位置する頂点を取得し、複数の線分を取得するように各頂点を互いに繋ぎ、
前記三次元モデルの輪郭図を得るように、前記取得した複数の線分から互いに重複しない、有界平面の内部の辺と異なる線分を輪郭線として選択し、各輪郭線は少なくとも二つの異なる有界平面に接続し、且つその一辺が当該輪郭線を含むようにそれぞれの有界平面に一つの三角形が存在し、内部の辺は一つの有界平面内だけに位置し、或は同じ有界平面上の複数の三角形に共有される方式で前記三次元モデルの輪郭図を抽出すること
を特徴とする付記１ないし７の何れか一項に記載の三次元モデル分割方法。
【０１１７】
（付記９）前記輪郭図分割ステップは、
前記生成された有界平面から、頂点の数が４以上であり、且つ前記三次元モデルの頂点が両側に分布するような、候補分割面をすべて検出する候補分割面検出サブステップと、
前記検出された候補分割面の中から分割面として選定された候補分割面を用いて、前記輪郭図が一つ或は少なくとも二つの互いに重複しないサブグラフに分割されるまで、前記輪郭図を逐一に分割するモデル分割サブステップと、
前記モデル分割サブステップで分割された前記サブグラフそれぞれに対して引き続きの分割をする必要があるかどうかを判定し、必要であれば、当該サブグラフが含んでいる候補分割面を選定された候補分割面として、当該サブグラフの対応する輪郭図を少なくとも二つの互いに重複しないサブグラフに分割するまで、当該サブグラフの対応する輪郭図に対して分割を行う終了条件判定サブステップと
を含んだことを特徴とする付記１ないし８の何れか一項に記載の三次元モデル分割方法。
【０１１８】
（付記１０）前記モデル分割サブステップは、
選定される候補分割面により以下の処理を実行することが含まれ、
すべてのサブグラフが選定される当該候補分割面を含むように、当該選定される候補分割面により輪郭図を一つ或は少なくとも二つの互いに重複しないサブグラフに分割する処理と、
前記分割されたサブグラフにおける穴と判定されたサブグラフと、当該サブグラフと一番近い実体になるサブグラフとを結合させて新しい実体を取得する処理と、
前記取得した実体それぞれに対してどの実体を分割の結果とするのかを判定する処理と
を含んだことを特徴とする付記９に記載の三次元モデル分割方法。
【０１１９】
（付記１１）前記選定される候補分割面により輪郭図を一つ或は少なくとも二つの互いに重複しないサブグラフに分割する処理は、
前記選定される候補分割面上に位置している輪郭線を削除し、修正後の輪郭図を取得し、
前記修正後の輪郭図の頂点の間の接続関係によって、修正後の輪郭図を一つ或は少なくとも二つの互いに重複しないサブグラフに分割し、
すべての前記サブグラフが前記選定される候補分割面を含むように、取得した繋がらない当該サブグラフそれぞれに対して再構成を実行し、
前記サブグラフの中で、前記選定される候補分割面を含んでいないサブグラフについて、当該サブグラフの各頂点がいずれも選定される候補分割面の同じ側に位置している場合に、頂点隣接グラフ或は分割されて当該サブグラフを取得した輪郭図により、当該サブグラフとそれと繋がっており且つ同じ側に位置しているサブグラフを再構成させて一つの新しいサブグラフを取得し、前記サブグラフの中で、前記選定される候補分割面を含んでいないサブグラフについて、当該サブグラフの頂点が選定される候補分割面の両側に位置し、かつ頂点隣接グラフ或は分割されて当該サブグラフを取得した輪郭図により前記選定される候補分割面を含むサブグラフと接続する場合に、当該サブグラフとそれと接続するサブグラフを一つの新しいサブグラフに再構成させ、
前記再構成されないサブグラフ及び前記再構成して取得した新しいサブグラフによって輪郭図から分割されて取得した前記一つ或は少なくとも二つの互いに重複しないサブグラフを構成することを含むこと
を特徴とする付記１０に記載の三次元モデル分割方法。
【０１２０】
（付記１２）前記モデル分割サブステップは、
前記サブグラフそれぞれの輪郭の情報に基づいて、当該サブグラフが選定される候補分割面での対応する閉鎖領域を取得する処理と、
取得した当該サブグラフの選定される候補分割面での各閉鎖領域間の関係、及び当該サブグラフと選定される候補分割面の関係を利用して、穴であるかどうかを判定する処理と、
前記穴と判定された前記サブグラフに対して新しい実体を取得する処理と
を含むことを特徴とする付記１０に記載の三次元モデル分割方法。
【０１２１】
（付記１３）前記サブグラフが穴であるかどうかを判定する処理は、
一番外側に位置している閉鎖領域が対応するサブグラフを実体と判定し、
一番外側に位置している閉鎖領域が対応するサブグラフを除くその他のサブグラフと前記その他のサブグラフと一番近いサブグラフとの相互関係に基づいて、以下の原則に応じてその他のサブグラフが穴であるかどうかをそれぞれ判定し、
前記原則は、
前記サブグラフ及び当該サブグラフと一番近いサブグラフがいずれも選定される候補分割面の同じ側に位置している場合に、当該サブグラフサブグラフを穴と判定し、
前記サブグラフ及び当該サブグラフと一番近いサブグラフが選定される候補分割面の完全に反対の側に位置している場合に、当該サブグラフを実体と判定し、
選定される候補分割面を基準として、当該サブグラフに属し且つ当該選定される候補分割面にある頂点から出発してその他の有界平面に接続した方向性がある線分及び当該選定される候補分割面の法線ベクトルが当該選定される候補分割面の両側にある場合に、当該サブグラフを穴と判定し、
選定される候補分割面を基準として、当該サブグラフに属し且つ当該選定される候補分割面にある頂点から出発してその他の有界平面に接続した方向性がある線分及び当該選定される候補分割面の法線ベクトルが当該選定される候補分割面の両側にない場合に、当該サブグラフを実体と判定することを含み、
その中、あるサブグラフについて、当該サブグラフと一番近いサブグラフは一つの実体であり、同時に当該一番近いサブグラフの対応する閉鎖領域は当該サブグラフの相応する閉鎖領域を含み、且つ当該サブグラフの相応するすべての閉鎖領域の中では一番小さい領域を含むこと
を特徴とする付記１２に記載の三次元モデル分割方法。
【０１２２】
（付記１４）三次元モデル分割装置が、
前記分割して取得したサブグラフの中に独立した穴が存在しないように、前記穴と判定されたサブグラフ及び当該サブグラフと一番近いサブグラフとを組み合わせ、且つその穴の内部だけに含まれている有界平面を非候補分割面に設定する処理をさらに実行すること
を特徴とする付記１３に記載の三次元モデル分割方法。
【０１２３】
（付記１５）前記モデル分割サブステップは、
所定条件を満たす部分だけが三次元モデルから分割されるように、予め設定されたパラメーターにより分割結果に対してコントロールを実行すること
を特徴とする付記１０に記載の三次元モデル分割方法。
【０１２４】
（付記１６）前記予め設定されたパラメーターは、
前記サブグラフと当該サブグラフと一番近いサブグラフの選定される候補分割面での相応する領域面積の比であり、
前記領域面積の比が予め設定された閾値より小さい場合に、前記サブグラフは分割して出され、
前記領域面積の比が予め設定された前記閾値より大きい場合に、前記サブグラフと当該サブグラフに一番近いサブグラフとは新しいサブグラフに組み合わせられ、独立した部分として分割して出されないこと
を特徴とする付記１５に記載の三次元モデル分割方法。
【０１２５】
（付記１７）前記終了条件判定サブステップは、
前記サブグラフが以下の条件のうち任意の一つを満たす時に、当該サブグラフは引き続き分割を行う必要がないと判定し、
前記条件は、
前記サブグラフの頂点の数が所定の第一閾値より小さい、
前記サブグラフが含む有界平面の数が所定の第二閾値より小さい、
前記サブグラフが含むすべての有界平面において候補分割面が存在しない、
前記サブグラフに当該サブグラフと対応する輪郭図を少なくとも二つのサブグラフに分割することができる候補分割面が存在しない、
ことであること
を特徴とする付記９に記載の三次元モデル分割方法。
【０１２６】
（付記１８）前記第一閾値は８で、前記第二閾値は６であることを特徴とする付記１７に記載の三次元モデル分割方法。
【０１２７】
（付記１９）入力された三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルに含まれるすべての三角形を処理し、当該三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する有界平面生成部と、
前記生成した有界平面を通して前記三次元モデルの輪郭図を抽出する輪郭図抽出部と、
前記生成した有界平面の情報及び前記三次元モデルの頂点隣接グラフの情報に基づいて、前記抽出した輪郭図を所定条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する輪郭図分割部とを含み、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルの頂点をノードとして、一つ或は複数の三角形に共有される二つの頂点の間ごとに一辺を追加して前記頂点隣接グラフを構築すること
を特徴とする三次元モデル分割装置。
【０１２８】
（付記２０）入力された三次元モデルの三角形ポリゴンデータに含む三角形データと頂点データに基づいて、当該入力された三次元モデルを一つのサブモデル或は少なくとも二つの互いに分離するサブモデルに予分割する予分割部を更に含み、
前記有界平面生成部、前記輪郭図抽出部及び前記輪郭図分割部は、前記サブモデルのそれぞれを所定の条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割するように、当該サブモデルそれぞれに対して処理を実行すること
を特徴とする付記１９に記載の三次元モデル分割装置。
【０１２９】
（付記２１）前記三次元モデルを構成する、三角形ポリゴンで表現される一連の立体コンポーネントを再構成するように、前記分割された一つサブグラフ或は少なくとも互いに重複しない二つのサブグラフ及び当該三次元モデルの三角形ポリゴンデータに基づいて三角化の処理を実行するモデル再構成部を更に含むこと
を特徴とする付記１９又は２０に記載の三次元モデル分割装置。
【０１３０】
（付記２２）前記有界平面生成部は、
前記三次元モデルに含まれるすべての三角形それぞれを一つのサブ平面として、すべてのサブ平面を合成できなくなるまで、合成条件を満たすサブ平面を一つの新しいサブ平面に合成して広義の平面を生成し、
前記三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成するように、前記広義の平面のそれぞれに対して以下の処理を実行することを含み、
当該広義の平面にある三角形に対して三角形隣接グラフを作成し、
前記三角形隣接グラフで前記広義の平面の三角形が複数の分離するサブ平面中に分けることができ、且つ当該サブ平面のそれぞれが複数の互いに接続する三角形を含む場合に、当該広義の平面を前記複数の分離するサブ平面に分け、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルにおける三角形をノードとして、共通点を有する二つの三角形の間に一辺を追加して前記三角形隣接グラフを構築し、
前記広義の平面を分けて得る前記複数の分離するサブ平面における複数のサブ平面を同時に他の同一の平面と繋がっている場合に、これらのサブ平面を一つの組み合わせる有界平面として組み合わせ、
前記組み合わせた有界平面及び前記広義の平面を分けて得る前記複数の分離するサブ平面における組み合わせる必要のない有界平面によって前記三次元モデルの分割に適用する前記有界平面を共同で構成し、
前記複数のサブ平面がそれぞれ前記他の同一の平面との間に少なくとも一つの共通点が存在する場合に、当該複数のサブ平面は同時に当該他の同一の平面と互いに繋がると判定し、
前記頂点隣接グラフにおいて、あるサブ平面に繋がる頂点が当該サブ平面の同じ側に位置する場合に、当該サブ平面は前記組み合わせる必要のない有界平面における独立する有界平面と判定するように配置されること
を特徴とする付記１９ないし２１の何れか一項に記載の三次元モデル分割装置。
【０１３１】
（付記２３）前記輪郭図抽出部は、
前記三次元モデルの頂点を輪郭図の頂点とし、各頂点の間には接続が存在せず、
前記有界平面生成部で生成したそれぞれの有界平面に対して、当該有界平面生成部で生成した有界平面から当該有界平面と繋がる有界平面を探し、
前記有界平面と当該有界平面と繋がっている有界平面の境界線に位置する頂点を取得し、複数の線分を取得するように各頂点を互いに繋ぎ、
前記三次元モデルの輪郭図を得るように、前記取得した複数の線分から互いに重複しない、有界平面の内部の辺と異なる線分を輪郭線として選択し、各輪郭線は少なくとも二つの異なる有界平面に接続し、且つその一辺が当該輪郭線を含むようにそれぞれの有界平面に一つの三角形が存在し、内部の辺は一つの有界平面内だけに位置し、或は同じ有界平面上の複数の三角形に共有される方式で前記三次元モデルの輪郭図を抽出するように配置されること
を特徴とする付記１９ないし２２の何れか一項に記載の三次元モデル分割装置。
【０１３２】
（付記２４）前記輪郭図分割部は、
前記生成された有界平面から、頂点の数が４以上であり、且つ前記三次元モデルの頂点が両側に分布するような、候補分割面をすべて検出する候補分割面検出サブ部と、
前記検出された候補分割面の中から分割面として選定された候補分割面を用いて、前記輪郭図が一つ或は少なくとも二つの互いに重複しないサブグラフに分割されるまで、前記輪郭図を逐一に分割するモデル分割サブ部と、
前記モデル分割サブ部で分割された前記サブグラフそれぞれに対して引き続きの分割をする必要があるかどうかを判定し、必要であれば、当該サブグラフが含んでいる候補分割面を選定された候補分割面として、当該サブグラフの対応する輪郭図を少なくとも二つの互いに重複しないサブグラフに分割するまで、当該サブグラフの対応する輪郭図に対して分割を行う終了条件判定サブ部と
を特徴とする付記１９ないし２３の何れか一項に記載の三次元モデル分割装置。
【０１３３】
（付記２５）前記モデル分割サブ部は、
すべてのサブグラフが選定される当該候補分割面を含むように、当該選定される当該候補分割面により輪郭図を一つ或は少なくとも二つの互いに重複しないサブグラフに分割し、
前記分割されたサブグラフにおける穴と判定されたサブグラフと、当該サブグラフと一番近い実体になるサブグラフとを結合させて新しい実体を取得し、
前記取得した実体それぞれに対してどの実体を分割の結果とするのかを判定するように配置されること
を特徴とする付記２４に記載の三次元モデル分割装置。
【０１３４】
（付記２６）前記モデル分割サブ部は、
前記サブグラフそれぞれの輪郭線の情報に基づいて、当該サブグラフが選定される候補分割面での対応する閉鎖領域を取得し、
取得した当該サブグラフの選定される候補分割面での各閉鎖領域間の関係、及び当該サブグラフと選定される候補分割面の関係を利用して、穴であるかどうかを判定し、
前記穴と判定された前記サブグラフに対して新しい実体を取得すること
を特徴とする付記２５に記載の三次元モデル分割装置。
【０１３５】
（付記２７）前記モデル分割サブ部は、
以下の処理を通してサブグラフが穴であるかどうかを判定するように配置され、
一番外側に位置している閉鎖領域が対応するサブグラフを実体と判定し、
一番外側に位置している閉鎖領域が対応するサブグラフを除くその他のサブグラフと前記その他のサブグラフと一番近いサブグラフとの相互関係に基づいて、以下の原則に応じてその他のサブグラフが穴であるかどうかをそれぞれ判定し、
前記原則は、
前記サブグラフと当該サブグラフと一番近いサブグラフがいずれも選定される候補分割面の同じ側に位置している場合に、当該サブグラフを穴と判定し、
前記サブグラフと当該サブグラフと一番近いサブグラフが選定される候補分割面の完全に反対の側に位置している場合に、当該サブグラフを実体と判定し、
選定される候補分割面を基準として、当該サブグラフに属し且つ当該選定される候補分割面にある頂点から出発してその他の有界平面に接続した方向性がある線分及び当該選定される候補分割面の法線ベクトルが当該選定される候補分割面の両側にある場合に、当該サブグラフを穴と判定し、
選定される候補分割面を基準として、当該サブグラフに属し且つ当該選定される候補分割面にある頂点から出発してその他の有界平面に接続した方向性がある線分及び当該選定される候補分割面の法線ベクトルが当該選定される候補分割面の両側にない場合に、当該サブグラフを実体と判定し、
その中、あるサブグラフについて、当該サブグラフと一番近いサブグラフは一つの実体であり、同時に当該一番近いサブグラフの対応する閉鎖領域は当該サブグラフの相応する閉鎖領域を含み、かつ当該サブグラフの相応するすべての閉鎖領域の中では一番小さい領域を含むこと
を特徴とする付記２６に記載の三次元モデル分割装置。
【０１３６】
（付記２８）前記モデル分割サブ部は、
所定条件を満たす部分だけが三次元モデルから分割されるように、予め設定されたパラメーターにより分割結果に対してコントロールを実行するように配置されること
を特徴とする付記２５に記載の三次元モデル分割装置。
【０１３７】
（付記２９）前記予め設定されたパラメーターは、
前記サブグラフと当該サブグラフと一番近いサブグラフの選定される候補分割面での相応する領域面積の比であり、
前記領域面積の比が予め設定された閾値より小さい場合に、前記サブグラフは分割して出され、
前記領域面積の比が予め設定された前記閾値より大きい場合に、前記サブグラフと当該サブグラフに一番近いサブグラフとは新しいサブグラフに組み合わせられ、独立した部分として分割して出されないこと
を特徴とする付記２８に記載の三次元モデル分割装置。
【０１３８】
（付記３０）前記終了条件判定サブ部は、
前記サブグラフが以下の条件のうち任意の一つを満たすときに、当該サブグラフは引き続き分割を行う必要がないと判定するように配置され、
前記条件は、
前記サブグラフの頂点の数が所定の第一閾値より小さい、
前記サブグラフの含む有界平面の数が所定の第二閾値より小さい、
前記サブグラフが含むすべての有界平面の中に候補分割面が存在しない、
前記サブグラフの中に当該サブグラフと対応する輪郭図を少なくとも二つのサブグラフに分割することができる候補分割面が存在しない、
ことであること
を特徴とする付記２４に記載の三次元モデル分割装置。
【０１３９】
（付記３１）前記第一閾値は８で、前記第二閾値は６であることを特徴とする付記３０に記載の三次元モデル分割装置。
【０１４０】
（付記３２）付記１９ないし３１の何れか一項に記載の前記三次元モデル分割装置が含まれることを特徴とする画像処理システム。
【０１４１】
（付記３３）前記画像処理システムは、
目的検出システム、部分マッチングシステム、モデル検索システムであること
を特徴とする付記３２に記載の画像処理システム。
【０１４２】
（付記３４）機器によって読み取り可能な指令コードが格納されたプログラム製品であり、
前記指令コードが機器によって読み取られるときに、付記１ないし１８の何れか一項に記載の方法を実行させることを特徴とするプログラム製品。
【符号の説明】
【０１４３】
１０００ 三次元モデル分割装置
１１００ 予分割部
１２００ 有界平面生成部
１３００ 輪郭図抽出図
１４００ 輪郭図分割部
１５００ モデル再構成部
【技術分野】
【０００１】
本発明は、三次元モデル分割方法、三次元モデル分割装置及び三次元モデル分割装置を含む画像処理システムに関する。
【背景技術】
【０００２】
近年、コンピュータ技術とコンピュータ支援設計（ＣＡＤ：Computer-Aided Design）モデリングツールの発展に従って、三次元モデルは広範囲に使用されている。これと同時に、三次元モデルは、より複雑になりデータ量も多くなっている。これらのモデルを有効に保存、処理、レンダリング、伝送するために、三次元モデルを分割する技術が広く注目を集めている。三次元モデルを分割する技術は、複雑なモデルを比較的単純でデータ量の少ないモデルに分割することができる。さらに、これらの分割されたデータ量の少ないモデルを個別に処理することで、保存、処理、レンダリング作業などの効率が大幅に引き上げられる。同時に、分割結果は、入力されたモデルを構造化して記述するので、モデルの保存と複製の使用にも便利である。
【０００３】
今までに、すでに多くのモデル分割技術が開示されている。これらの技術は、分割結果に基づいて大きく二種類に分けられる。第一種類の技術は、パッチに基づく技術である。この技術は、三次元メッシュを一連の異なるパッチプリミティブ、例えば平面、柱面、球面などに分割する。この種の技術は、前処理の手段として使うことができ、モデルの特徴の抽出に役立つ。第二種類の技術は、立体コンポーネントに基づく技術である。この技術は、三次元メッシュを一連の立体的なプリミティブ、例えば直方体、球体などに分割する。この技術は入力されたモデルの構造を表現するので、物体検出、部分マッチングなどの分野で非常に高い応用価値を有する。
【０００４】
従来のモデル分割技術について説明する。上述の第一種類に属する技術として、領域拡張法で距離画像に対して分割を行う方法がある。この方法では、まず頂点ごとに対応する平均曲率とガウス曲率を算出し、算出した曲率によってシェード領域を構築して、二次多項式で表現する。続いて各シェード領域に対して、この領域周囲の頂点のシェード領域への従属度を計算し、計算した従属度に基づいて領域拡張するとともに、各シェード領域の拡張ができなくなるまでシェード領域を拡張する。
【０００５】
また、第一種類に属する別の技術として、三角形のクラスタリングを通じて分割する方法がある。この方法では、まず三角形同士の隣接関係を利用して双対グラフを作成し、双対グラフにおいて、各三角形を一つのノードとして、初期状態では、各三角形の面が独立するクラスタリングとする。そして、双対グラフの各辺の縮約指標を計算し、平面の度数、三角形間の方向の差異などの属性に基づいて、双対グラフのすべての辺が縮約できなくなるまで、双対グラフのある双対辺を縮約させる。すなわち、双対辺が連結する二つのノードを一つに合併させ、隣接している二つのクラスタリングを一つの大きなクラスタリングに合併させる。
【０００６】
上述の第二種類に属する技術として、ランダムに選択した境界ではない頂点を起点として、境界として判定された頂点に囲まれるまで、領域を拡張する方法がある。この方法では、まず各頂点に対応するガウス曲率を計算し、設定された閾値に基づいて、大きいマイナス曲率を持った頂点を境界点とする。
【０００７】
また、第二種類に属する別の技術として、入力されたモデルをまず粗く分割してから、徐々に正確な分割を求める方法がある。この方法は分割の結果が空間の位置の不変性を持つようにＭＤＳ(Multi Dimensional Sealing)変換を導入し、一種のロバストな特徴点を抽出する。これによって三次元モデルを複数の部分に分割し、且つカットセット方法を導入して各部分のエッジを更に改善させる。
【０００８】
さらに、前記の第二種類に属する別の技術として、三次元モデルの各パッチの類似性を記述する双対グラフを計算し、スペクトラルクラスタリング方法を採用して三次元モデルを分割する方法がある。ここで、パッチ間の類似性は、パッチ間の測地距離と角度距離を合わせたものである。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Besl P.J、Jain R，「Segmentation through Variable-Order Surface Fitting」，IEEE PAMI，１９９８，１０(２),ｐ．１６7-１９２
【非特許文献２】Garland M、Willmott A、Heckbert P.S，「Hierarchical Face Clustering on Polygonal Surfaces」、Proceeding of Symposium on Interactive 3D Graphics，２００１,p．２１４-２２３
【非特許文献３】Zhang Y、Paik J、Koschan A、Abidi M.A，「A Simple and Efficient Algorithm for Part Decomposition」，Proceeding of International Conference on Image Processing，２００２,p．２7３-２7６
【非特許文献４】S Katz、G leifman、A Tal，「Mesh segmentation using feature point and core extraction」，The Visual Computer，２００５，２１(８-１０)，p．８６５-８7５
【非特許文献５】R Liu、H Huang，「Segmentation of 3d meshes through spectral clustering」，Pacific conference on Computer graphics and applications，２００４，ｐ．２９８-３０５
【非特許文献６】R Seidel，「A simple and fast incremental randomized algorithm for computing trapezoid decompositions and for triangulating polygons」，Computational Geometry：Theory and Applications，１９９１，Vol.１，No.１,ｐ．５１-６４
【非特許文献７】Joseph O’ Rourke，「Computational geometry in C (second edition)」，Cambridge University Press,ｐ．１-４０
【非特許文献８】Nina Amenta、Marshall Bern、Manolis Kamvysselis，「A new voronoi-based surface reconstruction algorithm」，ACM SIGGRAPH，１９９８，ｐ．４１５-４２１
【非特許文献９】王志強、肖立瑾，「多角形の簡単性、方向及び内外点の判別算法」，計算機学報，１９９８，No.２,Vol.２１,ｐ．１８３-１８７
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述した従来の技術では、ノイズの影響を軽減し、少ない計算量で正確に三次元モデルを分割することができないという課題があった。
【００１１】
具体的には、領域拡張法で距離画像に対して分割を行う方法は、曲率が非常にノイズの影響を受けやすいので、ノイズを軽減する能力が低い。また、三角形のクラスタリングを通じて分割する方法は、容易に実施できるが、予め設定された閾値への依存性が非常に高い。
【００１２】
入力されたモデルをまず粗く分割してから、徐々に正確な分割を求める方法は、理論的には良い分割結果を得ることができるが、計算量が多いので実際の利用には不利である。また、スペクトラルクラスタリング方法を採用して三次元モデルを分割する方法は、クラスタリングの数を予め設定する必要があり、また滑らかなエッジを持つモデルについて、自然な分割結果が得られない可能性がある。
【００１３】
総合的に見れば、既存の三次元モデルの分割技術は、通常複数の複雑な特徴、例えば、曲率、三角形の面間の測地距離、突出関数（Protrusion function）などを用いる。これらの特徴の正確な算出は比較的に困難であり、また、ノイズの影響を受けやすい。既存の方法には、以下の主要課題が存在する。１、曲率のようなノイズの影響を受けやすい特徴の導入により、ノイズを軽減する能力が比較的低い。２、モデルの分割技術は、計算量が比較的に多く複雑であり、分割効率に影響を与える。３、既存の方法では分割して得られた結果は、通常、パッチまたはパッチの組み合わせで表現するので、独立な三次元実体ではない。４、早期のモデルの分割方法には通常過分割問題が存在する。
【００１４】
開示の技術は、上記に鑑みてなされたものであって、ノイズの影響を軽減し、少ない計算量で正確に三次元モデルを分割することができる三次元モデル分割方法、三次元モデル分割装置及び三次元モデル分割装置を含む画像処理システムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
本願の開示する三次元モデル分割方法は、一つの態様において、入力された前記三次元モデルの三角形ポリゴンデータに基づいて、前記三次元モデルに含まれるすべての三角形を処理し、三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する有界平面生成ステップと、前記生成した有界平面を通して前記三次元モデルの輪郭図を抽出する輪郭図抽出ステップと、前記生成した有界平面の情報及び前記三次元モデルの頂点隣接グラフの情報に基づいて、前記抽出した輪郭図を所定条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する輪郭図分割ステップとを含み、前記三次元モデルの三角形ポリゴンデータに基づいて、三次元モデルの頂点をノードとして、一つ或は複数の三角形に共有される二つの頂点の間ごとに一辺を追加して前記頂点隣接グラフを構築する。
【００１６】
また、本願の開示する三次元モデル分割装置は、他の態様において、入力された三次元モデルの三角形ポリゴンデータに基づいて、前記三次元モデルに含まれるすべての三角形を処理し、前記三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する有界平面生成部と、前記生成した有界平面を通して前記三次元モデルの輪郭図を抽出する輪郭図抽出部と、前記生成した有界平面の情報及び前記三次元モデルの頂点隣接グラフの情報に基づいて、前記抽出した輪郭図を所定条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する輪郭図分割部とを含み、前記三次元モデルの三角形ポリゴンデータに基づいて、三次元モデルの頂点をノードとし、一つ或は複数の三角形に共有される二つの頂点の間ごとに一辺を追加して前記頂点隣接グラフを構築する。
【００１７】
また、本願の開示する画像処理システムは、他の態様において、上述の三次元モデル分割装置を有し、例えば目標検査システム、部分マッチングシステム、モデル検索システムなどである。
【００１８】
また、本願の開示する三次元モデル分割プログラムは、他の態様において、機器の読取可能な指令コードを格納しているプログラムの製品を提供する。前記指令コードは機器により読み取って実行する時に、上述したような、開示技術による三次元モデルを分割する方法を実行することができる。
【発明の効果】
【００１９】
本願の開示する三次元モデル分割方法、三次元モデル分割装置及び三次元モデル分割装置を含む画像処理システムの一つの態様によれば、ノイズの影響を軽減し、少ない計算量で正確に三次元モデルを分割することができるという効果を奏する。
【００２０】
また、本願の開示する三次元モデル分割方法、三次元モデル分割装置及び三次元モデル分割装置を含む画像処理システムの一つの態様によれば、入力された三次元モデルに対して、有効な分割を行い、また、正確な分析及び再構築を行うことができるという効果を奏する。
【００２１】
また、本願の開示する三次元モデル分割方法、三次元モデル分割装置及び三次元モデル分割装置を含む画像処理システムの一つの態様によれば、入力された三次元モデルをまず粗く分割してから徐々に正確な分割を求め、分割できなくなるまで複数の部分に分割する。
【００２２】
また、本願の開示する三次元モデル分割方法、三次元モデル分割装置及び三次元モデル分割装置を含む画像処理システムの一つの態様によれば、分割された各部分は、それぞれ閉鎖される立体コンポーネントである。
【図面の簡単な説明】
【００２３】
【図１】図１は、開示技術の実施例による三次元モデル分割方法を示すフローチャートである。
【図２Ａ】図２Ａは、開示技術の実施例による三次元モデル分割方法において有界平面を抽出する一つの実施例を模式的に示す図である。
【図２Ｂ】図２Ｂは、開示技術の実施例による三次元モデル分割方法において有界平面を抽出する一つの実施例を模式的に示す図である。
【図２Ｃ】図２Ｃは、開示技術の実施例による三次元モデル分割方法において有界平面を抽出する一つの実施例を模式的に示す図である。
【図３Ａ】図３Ａは、開示技術の実施例による三次元モデル分割方法において輪郭図の抽出を行う一つの実施例を示す図である。
【図３Ｂ】図３Ｂは、開示技術の実施例による三次元モデル分割方法において輪郭図の抽出を行う一つの実施例を示す図である。
【図４】図４は、開示技術の実施例による三次元モデル分割方法において抽出された有界平面、輪郭図などの情報に基づいて、モデルの分割を行う一つの実施例を模式的に示すフローチャートである。
【図５】図５は、図４に示したフローチャートにおけるステップS４１０の処理の一つの実施例を模式的に示すフローチャートである。
【図６】図６は、図３の中で示した有界平面１を分割面にして、入力された三次元モデルに対して分割して得られた各サブグラフには何れも選定された分割面が含まれている一例を示す図である。
【図７Ａ】図７Ａは、開示技術の実施例による三次元モデル分割方法において選定された候補分割面に基づいて、入力された三次元モデルに対して分割を行って取得した結果に、選定された分割面側にあるが、選定された分割面を含んでいないサブグラフが存在する一例を示す図である。
【図７Ｂ】図７Ｂは、開示技術の実施例による三次元モデル分割方法において選定された候補分割面に基づいて、入力された三次元モデルに対して分割を行って取得した結果に、選定された分割面側にあるが、選定された分割面を含んでいないサブグラフが存在する一例を示す図である。
【図７Ｃ】図７Ｃは、開示技術の実施例による三次元モデル分割方法において選定された候補分割面に基づいて、入力された三次元モデルに対して分割を行って取得した結果に、選定された分割面側にあるが、選定された分割面を含んでいないサブグラフが存在する一例を示す図である。
【図７Ｄ】図７Ｄは、開示技術の実施例による三次元モデル分割方法において選定された候補分割面に基づいて、入力された三次元モデルに対して分割を行って取得した結果に、選定された分割面側にあるが、選定された分割面を含んでいないサブグラフが存在する一例を示す図である。
【図８Ａ】図８Ａは、開示技術の実施例による三次元モデル分割方法の中で選定された候補分割面に基づいて、入力された三次元モデルに対して分割を行って取得した結果に、選定された分割面を跨るサブグラフが存在する一例を示す図である。
【図８Ｂ】図８Ｂは、開示技術の実施例による三次元モデル分割方法の中で選定された候補分割面に基づいて、入力された三次元モデルに対して分割を行って取得した結果に、選定された分割面を跨るサブグラフが存在する一例を示す図である。
【図８Ｃ】図８Ｃは、開示技術の実施例による三次元モデル分割方法の中で選定された候補分割面に基づいて、入力された三次元モデルに対して分割を行って取得した結果に、選定された分割面を跨るサブグラフが存在する一例を示す図である。
【図９Ａ】図９Ａは、開示技術の実施例による三次元モデル分割方法の中で穴判別処理を行う一例を示す図である。
【図９Ｂ】図９Ｂは、開示技術の実施例による三次元モデル分割方法の中で穴判別処理を行う一例を示す図である。
【図９Ｃ】図９Ｃは、開示技術の実施例による三次元モデル分割方法の中で穴判別処理を行う一例を示す図である。
【図１０Ａ】図１０Ａは、開示技術の実施例による三次元モデル分割方法の中で穴判別処理を行う他の例を示す図である。
【図１０Ｂ】図１０Ｂは、開示技術の実施例による三次元モデル分割方法の中で穴判別処理を行う他の例を示す図である。
【図１１Ａ】図１１Ａは、開示技術の実施例による三次元モデル分割方法の中で、分割結果における各実体を再編成することを模式的に示す図である。
【図１１Ｂ】図１１Ｂは、開示技術の実施例による三次元モデル分割方法の中で、分割結果における各実体を再編成することを模式的に示す図である。
【図１２Ａ】図１２Ａは、開示技術の実施例による三次元モデル分割方法において分割する三次元モデルを予め複数の互いに分離するサブモデルに分割することを模式的に示す図である。
【図１２Ｂ】図１２Ｂは、開示技術の実施例による三次元モデル分割方法において分割する三次元モデルを予め複数の互いに分離するサブモデルに分割することを模式的に示す図である。
【図１２Ｃ】図１２Ｃは、開示技術の実施例による三次元モデル分割方法において分割する三次元モデルを予め複数の互いに分離するサブモデルに分割することを模式的に示す図である。
【図１３】図１３は、開示技術の実施例の三次元モデル分割に用いられる装置を模式的に示すブロック図である。
【発明を実施するための形態】
【００２４】
下記のように、図面を参照しながら開示技術の実施形態を説明する。開示技術の一つの図面或は一種の実施の形態で記述する要素と特徴は、一つ或はもっと多くのその他の図面或は実施の形態に示す要素と特徴に結合できる。注意すべきことは、明瞭且つ簡潔にするために、開示技術と関係のない、当業者にとって既知のコンポーネント及び処理の表示と記述は図面と説明から省略した。
【実施例】
【００２５】
図１は、開示技術の実施例による三次元モデル分割方法を示すフローチャートである。三次元モデル分割装置は、有界平面生成ステップＳ１１０で、入力された三次元モデルの三角形ポリゴンデータに基づいて当該三次元モデルに含まれるすべての三角形に対して処理を行い、当該三次元モデルの分割に適用する有界平面を少なくとも一つ生成する。三次元モデル分割装置は、輪郭図抽出ステップＳ１２０で、生成された有界平面を通して三次元モデルの輪郭図を抽出する。三次元モデル分割装置は、輪郭図分割ステップＳ１３０で、生成された有界平面の情報及び三次元モデルの頂点隣接グラフの情報により、抽出された輪郭図を一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する。ここで、頂点隣接グラフは、三次元モデルの三角形ポリゴンデータに基づいて、三次元モデルの頂点をノードにして、一つ或は複数の三角形に共有される二つの頂点の間ごとに一辺を追加して構築される。
【００２６】
以下では、図面を参考にして三次元モデル分割装置が実行する各ステップを詳しく説明する。
【００２７】
三次元モデル分割装置が実行する有界平面生成ステップＳ１１０は、モデルの表面を構成する三角形ポリゴンを合理的に編成し、一連（少なくとも一つ）の三次元モデルを分割するのに適用できる有界平面を生成する。開示技術の当該実施例により、入力された三次元モデルは、三角形ポリゴンで表現する必要があり、基本的なデータの構成要素には、モデルの頂点とモデル表面を構成する三角形ポリゴンを含む。分割対象である入力された三次元モデルは、様々な形式を持つことができる。例えば、スキャンによって生じるポイント雲モデル、各種のモデリングツールによって生じるバラメーター化のモデル、或は三角形ではないポリゴンで表示されるモデルなどである。開示技術の方法を利用する場合には、先ずこのような形式で表示される三次元モデルは、三角形ポリゴンの形式に変換されなければならない。既知の様々な方法を利用して、このような変換を実行することができる。例えば、もし入力されるのが三角形ではないポリゴンで表示される三次元モデルであれば、上述の「非特許文献７」で開示された方法を使用して各多角形を一連の三角形に変換することができる。もし入力されるのがポイント雲モデルであれば、上述した「非特許文献８」で開示された方法を使用してポイント雲モデルを三角形ポリゴンの形式に変換できる。有界平面は、一つ或は複数の閉鎖領域で構成される可能性がある。
【００２８】
三次元モデル分割装置が実行する有界平面生成ステップＳ１１０は、主に二つのサブステップで構成される。サブステップ１において、三次元モデル分割装置は、すべての三角形を組み合わせることによって、すべての広義の平面（general planes）を取得する。サブステップ２において、三次元モデル分割装置は、後続の輪郭図の抽出、分割、再編成などの処理に利用できるように、取得した広義の平面からすべての有界平面を検出する。
【００２９】
サブステップ１では、三次元モデル分割装置は、先ず、分割対象である、三角形ポリゴンで表示された三次元モデルのそれぞれの三角形を初期化する。すなわち、三次元モデル分割装置は、分割対象であるモデルの表面を構成するそれぞれの三角形を一つのサブ平面とする。すなわち、三角形の数だけのサブ平面が存在する。この中では、三次元モデル分割装置は、三角形の法線方向をサブ平面の法線方向とする。三次元モデル分割装置は、三角形の法線方向を公知の計算式で計算して取得することができ、ここで、法線方向とは、三角形の平面に垂直し且つ分割対象である三次元モデルの外部を指す方向である。続いて、三次元モデル分割装置は、すべてのサブ平面が合成できなくなるまで合成条件を満たすサブ平面を一つの新しいサブ平面に合成する（converge）。ここで、サブ平面の合成処理によって得られた平面を「広義の平面」と呼ぶ。ここで、三次元モデル分割装置がサブ平面を合成できる条件は、（１）法線の方向が同じ又は反対であり、（２）頂点が同一平面にあることである。
【００３０】
図２Ａ−図２Ｃは、開示技術の実施例による三次元モデル分割方法において有界平面を抽出する一つの実施例を模式的に示す図である。図２Ａは、三角形ポリゴンで表示される三次元モデルを示し、そのモデルは２０個の頂点と３６個の三角形を含んでいる。図２Ｂは、一つ目のサブステップの後に取得する広義の平面を示し、合計で１０個の広義の平面が検出された。なお、記述の簡潔且つ明瞭のために、図２Ｂには検出された１０個の広義の平面の中の三つの広義の平面しか示していない。すなわち、広義の平面１、広義の平面２、広義の平面３である。
【００３１】
サブステップ２では、三次元モデル分割装置は、平面自体の幾何学特徴及び平面の間の関係などの情報を使用して、ステップ１で取得した広義の平面に対して処理を行い、それによって一連の有界平面を生成する。平面自体の幾何学特徴及び平面の間の関係などの情報には、各平面上に含まれている頂点及びその座標、平面の間の接続関係、ある平面では当該平面上の頂点以外の他の頂点が当該平面との相対位置、各平面上の三角形データなどが含まれる。三次元モデル分割装置は、上述の方式で入力された三次元モデルに対して三角形ポリゴンでの表示を行った後に、これに対応して平面自体の幾何学特徴及び平面の間の関係などの情報を得る。三次元モデル分割装置は、二つの平面に少なくとも一つの共同点を有する時に、この二つの平面は相互接続されていると判定する。三次元モデル分割装置は、すべての広義の平面が処理される必要がなくなるまで、検出されたすべての広義の平面におけるそれぞれの平面に対して以下の処理を行う。
【００３２】
１）三次元モデル分割装置は、入力された三次元モデルの三角形ポリゴンデータに基づいて、当該広義の平面にある三角形に対して三角形隣接グラフを作成する。もし当該三角形隣接グラフが繋がっていない場合、三次元モデル分割装置は、当該広義の平面を処理する必要がある。すなわち、三次元モデル分割装置は、当該広義の平面を複数のサブ平面に分ける。ここで、三角形隣接グラフが繋がっていないとは、当該広義の平面上の三角形が複数の分離するサブ平面に分けられ、当該サブ平面ごとに一つ或は複数の互いに接続する三角形（これらの三角形は少なくとも一つの共通点を有している）を含んでいる場合である。例えば、図２Ｂにおける広義の平面１と広義の平面２はそれぞれ二つの繋がらないサブ平面に分けられるが、広義の平面３はこのように分ける必要がない。ここで、三角形隣接グラフは三角形の接続関係を表すグラフである。三角形隣接グラフを作成する場合、三次元モデル分割装置は、三角形ポリゴンデータに含まれる各三角形をノードとし、二つの三角形が共通点を持つ場合に、その二つの三角形が表すノードの間に一辺を追加して三角形隣接グラフを取得する。三次元モデル分割装置は、この二つの三角形における任意の点、例えば、二つの三角形の中点を繋ぐことによって、この辺を追加することができる。三角形隣接グラフにおける任意の一対ノード（つまり、二つの三角形）の間に接続パスが存在する場合に、三次元モデル分割装置は、当該三角形隣接グラフは繋がっていると判定する。ここでのパスは通常一辺か又は複数の辺で構成される。
【００３３】
２）上述の処理１）によって取得した複数のサブ平面が同時に他の同一の平面と接続する場合に、三次元モデル分割装置は、モデル分割の便宜を図るために、これらのサブ平面を一つの組み合わせの有界平面として組み合わせる必要がある。例えば、図２Ｂで、サブグラフ２-１とサブグラフ２-２は何れも有界平面３と接続しているから、この二つのサブグラフは組み合わされて一つの組み合わせの有界平面になる。またこの組み合わせの有界平面に沿って、三次元モデル分割装置は、図２Ａ−２Ｃに示される三次元モデルを二つの部分に分割することができる。具体的な実施過程では、三次元モデル分割装置は、反復的に有界平面の検出処理を行うことができる。すなわち、三次元モデル分割装置は、平面の数が変化しないようにサブステップ１で生じた広義の平面を更新する。したがって、始まる時に、ここの「他の同一の平面」とはサブステップ１で取得した広義の平面であり、その後、ここの「他の一つの平面」とは更新されて得られた有界平面の可能性がある。
【００３４】
３）上述の処理１）によって取得したサブ平面で、あるサブ平面について、頂点隣接グラフにおいて、当該サブ平面に繋がる頂点が当該サブ平面の同じ側にある場合に、当該サブ平面は「独立的」有界平面と称することができる。つまり、他の平面と組み合わせる必要がない有界平面である。例えば、図２Ｂで、サブ平面１-１と繋ぐ四つの頂点は当該サブ平面の同じ側にあるから、サブ平面１-１は独立的有界平面とすることができる。同じ原理で、サブ平面１-２も独立的有界平面と称すことができる。しかし、サブ平面２-１とサブ平面２-２は当該条件を満たさないので、これらは有界平面であるが、独立的有界平面ではない。また、図２Ｂにおける広義の平面３も他のサブ平面との組み合わせの処理をする必要がない有界平面と判定される（図２Ｃを参照）。ここで、頂点隣接グラフは入力された三次元モデルの三角形ポリゴンデータによって構築され、頂点の接続関係を記述する図である。三次元モデル分割装置は、三次元モデルの頂点をノードとし、二つのノードが一つ或は複数の三角形（すなわち、入力する三角形ポリゴンデータに含まれた三角形）に共有される場合に、その二つのノードの間に一辺を追加して頂点隣接グラフを構築する。
【００３５】
図２Ｃは、三次元モデル分割装置がサブステップ２の処理を行った後の結果を示し、有界平面の数は１１個である。この中で、広義の平面１は、二つの有界平面に分けられている。二つの有界平面は、図２Ｂにおけるサブ平面１-１に対応する有界平面１１及びサブ平面１-２に対応する有界平面１である。他の有界平面は、それぞれ前記サブステップ１で取得した広義の平面と対応する。すなわち、その他の平面は変わらないままである。注意すべきことは、明瞭且つ簡潔のために，図には全ての有界平面を表示していない。
【００３６】
上述のことから、三次元モデル分割装置は、上述の有界平面生成処理を反復的に行う。すなわち、三次元モデル分割装置は、平面の数が変わらなくなるまでサブステップ１で生じた広義の平面に対して更新を行い、それによって一つ或は複数の有界平面を生成する。そして、上述の記載から、「有界平面」は前記三次元モデルの分割に適用できる、すなわち、上述の相応する条件を満たす平面であることが分かる。有界平面には外の平面と組み合わせる必要がない有界平面（例えば図２Ｃでの有界平面１１、有界平面１及び有界平面３）、及び組み合わせる必要があるサブ平面に対して組み合わせの処理を行って取得した組み合わせの有界平面（例えば図２Ｃでの有界平面２）が含まれる。
【００３７】
当業者は、有界平面生成ステップＳ１１０で生じた有界平面の数は、分割対象である三次元モデルによって決められ、一つ或は複数であってもよいことを理解できる。
【００３８】
以下では、図１に示す輪郭図抽出ステップＳ１２０の詳細を記述する。三次元モデル分割装置が実行する当該ステップは、検出された有界平面のデータを利用して、三次元モデルの輪郭を抽出し、同時に図の方式でこれを表す。この過程で、三次元モデル分割装置は、有界平面の間の接続関係に応じて、互いに接続する二つの平面のエッジにある線分が輪郭線であるかどうかを判定する。最後に、三次元モデル分割装置は、モデルの頂点を頂点とし、抽出された輪郭線を辺とし、分割対象である入力されたモデルに対応する輪郭図を構築する。それぞれの有界平面のデータには、例えば、当該有界平面にある頂点、三角形、法線方向及び面積などに関する情報が含まれる。
【００３９】
三次元モデル分割装置が実行する当該ステップでは、主に以下の二つの基本規則を採用して輪郭線を確定する。１）内部の辺を輪郭線にしてはならない。一辺がただある有界平面の中にあり、或は同一の有界平面の二つか複数の三角形により共有される場合、その辺は内部の辺と判定される。２）各輪郭線は少なくとも二つの異なる有界平面に繋がらなければならず、またそれぞれの有界平面に、一つの三角形のある辺がその輪郭線を含むように当該一つの三角形が存在する。
【００４０】
以上の二つの規則に従って、輪郭の抽出過程で、三次元モデル分割装置は、先ず輪郭図を初期化させ、分割対象である入力された三次元モデルの頂点を輪郭図の頂点にし、頂点の間は接続しない。すなわち、図に頂点のみがあり、辺がない。それから入力された三次元モデルの輪郭図を取得するように、三次元モデル分割装置は、以下のステップを採用して相応する頂点の間に輪郭線を追加する。
【００４１】
１）三次元モデル分割装置は、各有界平面に対して、それと繋がる有界平面を探す。例えば、図３Ａで有界平面１と有界平面２には四つの共通点Ａ、Ｂ、ＣとＤが存在しているので、三次元モデル分割装置は、有界平面１と有界平面２は互いに接続していると判定する。
【００４２】
２）三次元モデル分割装置は、各有界平面に対して、以下の方式に従ってこれと繋がっている有界平面のそれぞれを順番に処理して輪郭を抽出する。
三次元モデル分割装置は、当該有界平面と接続する平面の境界にある頂点を取得し、これらの頂点の位置に基づいて、これらをソートする。例えば図３Ａで、有界平面１と２の境界にある頂点は四つあって、ソートされた後はＡ‐Ｂ‐Ｃ‐Ｄである。
三次元モデル分割装置は、ソートされた後の頂点を順番に繋ぐ。例えば図３Ａでは、三次元モデル分割装置は、有界平面１と２の境界にある四つの頂点：Ａ、Ｂ、ＣとＤを順番に繋ぐ三本の線分、つまりＡＢ、ＢＣ、ＣＤを取得する。
三次元モデル分割装置は、各線分に対して、それが輪郭線になる条件を満たすか否かを判定する。条件を満たす場合には、三次元モデル分割装置は、輪郭図における相応する二つの頂点の間に繋がる辺を加える。例えば図３Ａに示すように、線分ＢＣは有界平面２における三角形Ｔ２‐２とＴ２−３に共有されるから、それは内部の辺であり、輪郭線とすることができない。線分ＡＢは有界平面１の三角形Ｔ１‐１の一辺に含まれる同時に、有界平面２の三角形Ｔ２−１に含まれるから、当該線分は輪郭線の条件を満たしており、三次元モデル分割装置は、輪郭図におけるノードＡとＢの間に一辺を加える。同じ原理で線分ＣＤも輪郭線である。
【００４３】
上述の輪郭抽出の処理は、それぞれの有界平面に対して行うべきである。その他、前記の処理で、例えば、図３Ａに示すように有界平面１と２の境界にある頂点が四つあり、ソートすることによってＡ−Ｂ−Ｃ−Ｄの順番の組み合わせを取得する必要がある。ソートすることは、関連する処理の負荷を減らすためで、最適化案に属する。三次元モデル分割装置は、取得した頂点をソートしなくてもいい。例えば、図３Ａ―３Ｂに示す実施例の中で、取得した頂点Ａ、Ｂ、Ｃ、Ｄに対してソートしなければ、各頂点を任意に繋いで取得した線分の数は３より大きく、例えば、線分ＡＢ、ＢＣとＣＤのほかに、他の線分ＡＣ、ＢＡ、ＤＣなどが得られる。しかし、これら他の線分は、例えば線分ＡＣのように上述の輪郭線になる条件を満たせないことにより取り除かれるか、或は重複する線分なので取り除かれてしまう。例えば線分ＢＡ、ＤＣはそれぞれ線分ＡＢ、ＣＤと重複し、同一の辺に属する。よって、三次元モデル分割装置は、取得した頂点に対してソートしなくても、入力された三次元モデルの正確な輪郭図を得ることができる。
【００４４】
以下では、図１に示す輪郭図の分割ステップＳ１３０の詳細を記述する。
【００４５】
三次元モデル分割装置が実行する当該ステップの処理は前のステップの処理で取得した有界平面、頂点隣接グラフなどの情報に基づいて、輪郭図抽出ステップＳ１２０で入力された輪郭図をまず粗く分割してから徐々に正確に、各層ごとに分割し、一つのサブグラフ或は少なくとも二つの重複しないサブグラフに分割する。図４は開示技術の実施例による三次元モデル分割方法において抽出された有界平面、輪郭図などの情報に基づいて、モデルの分割を行う一つの実施例を模式的に示すフローチャートである。図４に示すように、候補分割面検出ステップＳ４００では、前の処理で検出された有界平面からすべての候補分割面を探す。任意の一つの候補分割面について、入力された三次元モデルの頂点が候補分割面の両側に分布する場合、三次元モデル分割装置は、当該候補分割面は入力された三次元モデルを複数の部分に分割可能であると判定する。モデル分割ステップＳ４１０では、入力された輪郭図が一つのサブグラフ或は少なくとも二つの独立したサブグラフに分割されるまで、或はすべての候補分割面の処理を終えるまで、探し出した候補分割面を一つずつ利用して入力された輪郭図に対して分割を行う。終了条件判定ステップＳ４２０では、分割して取得したサブグラフに対して、引続き分割する必要があるかどうかを判定する。分割する必要がなければ、三次元モデル分割装置は、直接、当該サブグラフを出力する（Ｓ４３０）。分割する必要があれば、三次元モデル分割装置は、当該サブグラフが含んでいる候補分割面を利用して、引き続き分割を行う（Ｓ４４０）。
【００４６】
以下では、具体的な実施例で図４に示す各ステップの処理を詳細に記述する。
【００４７】
三次元モデル分割装置が実行する候補分割面検出ステップＳ４００は、検出された有界平面から候補分割面として三次元モデルの分割に適用可能なすべての有界平面を探し出す。各候補分割面は二つの条件を満たさなければならない。１）当該候補分割面上の頂点の数は４より小さくならない。頂点の数が４より小さい場合に、当該候補分割面に沿ってモデルを分割する際に、更に頂点を追加する必要があるので、処理が比較的複雑になる。２）当該候補分割面自体が含んだ頂点を除いて、その他の頂点は、当該候補分割面の両側に分布している。ここでいう「その他の頂点」とは、分割対象である三次元モデルのすべての頂点において当該候補分割面自体が含んだ頂点を除いた頂点をさす。最適化実施の形態として、三次元モデル分割装置は、当該候補分割面と繋がる頂点だけをその他の頂点として選んでもいい。こうすると、得られた候補分割面が相対的に少なくなり、三次元モデル分割装置は、処理の複雑さを軽減することができる。
【００４８】
例えば、図３Ａ-３Ｂで示す三次元モデルは２０個の頂点、３６個の三角形を含み、有界平面生成ステップによって、三次元モデル分割装置は、１２個の平面（記述の明瞭且つ簡潔のために、図では全部を示してない）を取得する。この中で、有界平面１には８個の頂点があり、また４個の頂点が有界平面１の上方に位置しており、８個の頂点が有界平面１の下方にある。したがって、三次元モデル分割装置は、有界平面１が同時に候補分割面の二つの条件を満たしているので、有界平面１を一つの候補分割面であると判定する。しかし、有界平面２には８個の頂点があり、その他の１２個の頂点は全部有界平面２の後方にある。したがって、三次元モデル分割装置は、有界平面２を候補分割面ではないと判定する。このステップの処理によって、三次元モデル分割装置は、図３Ａ-３Ｂで示す三次元モデルに一つの候補分割面を検出する。具体的には、三次元モデル分割装置は、候補分割面として有界平面１を検出する。
【００４９】
三次元モデル分割装置が実行するモデル分割ステップＳ４１０は、候補分割面に基づいて、入力された輪郭図を複数の重複しないサブグラフに分割する。図５は、図４に示したフローチャートにおけるステップＳ４１０の処理の一つの実施例を模式的に示すフローチャートである。当該ステップの処理では、入力された輪郭図が少なくとも二つのサブグラフに分割されるまで、或はすべての候補分割面が処理済になるまで（すなわち、すべての候補分割面を利用して分割を行うのは三次元モデルを一つサブグラフに分割する状況の詳細は後述する）、各候補分割面は逐一に試されたことが分かる。図５に示すように、三次元モデル分割装置は、選定されたある候補分割面に対しては、先ず当該選定された候補分割面によって輪郭図を一つのサブグラフ或は少なくとも二つの分離するサブグラフに分割する。しかも、それぞれのサブグラフには当該選定された候補分割面（ステップＳ５１０）が含まれている。続いて、三次元モデル分割装置は、前のステップで取得したサブグラフに穴があるかどうかを判定する。続いて、穴がある場合に、三次元モデル分割装置は、穴が独立に存在できないように穴を処理する（ステップＳ５２０）。最後に、三次元モデル分割装置は、パラメーター化処理を採用して分割結果をコントロールする（ステップＳ５３０）。以下では順番に各ステップの処理を説明する。
【００５０】
前の処理を経て取得した、入力された三次元モデルの候補分割面の数がｎ個（n3１）であると仮定する。ステップＳ５１０の処理では、ｎ個の候補分割面における第ｉ個の選定候補分割面に対して、各サブグラフに第ｉ個の選定された候補分割面が含まれるように、入力された輪郭図を選定された第ｉ個の候補分割面に沿って一つのサブグラフか或は少なくとも二つの分離するサブグラフに分割する。このために、当該処理は主に以下の三つの過程によって完成される。
【００５１】
１）三次元モデル分割装置は、前の輪郭図抽出処理で取得した輪郭図に対して修正を行い、修正された輪郭図を得る。すなわち、モデルの分割の準備のために選定された候補分割面にある輪郭線を削除する。図３Ａ-３Ｂに示す三次元モデルの中で、有界平面１を選定される候補分割面に仮定した場合、当該候補分割面は八つの頂点を含む。この八つの頂点の間の辺を削除した後、輪郭図は、図６に示す輪郭図になる。図６では、塗りつぶしの正方形と塗りつぶしの菱形で当該選定された候補分割面に属する頂点を表記する。
【００５２】
２）三次元モデル分割装置は、修正された輪郭図の頂点の間の接続関係に基づいて、修正後の輪郭図を一つのサブグラフ或は少なくとも二つの繋がらない、すなわち、分離するサブグラフに分割する。ここで、三次元モデル分割装置は、一つのサブグラフにおける頂点に他のサブグラフへの任意パスがなければ、その二つのサブグラフは分離していると判定する。
【００５３】
図６に示すように、修正した輪郭図は二つの互いに繋がらないサブグラフで構成されているから、三次元モデル分割装置は、入力されたモデルの各頂点を頂点間の接続関係に応じて、当該二つのサブグラフに分けることができる。サブグラフ１は、選定される候補分割面にある四つの菱形頂点と選定される候補分割面の上方にある四つの円形頂点を含む。サブグラフ２は、選定される候補分割面にある四つの正方形頂点と選定される候補分割面の下方にある八つの星形頂点を含む。
【００５４】
図７Ａ−７Ｃに示す実施例では、修正した輪郭図は、三つの互いに繋がらないサブグラフで構成され、入力されたモデルの各頂点を三つのサブグラフに相応して分け、それぞれ菱形、円形、星形で表記する。
【００５５】
図８Ｂ−８Ｃに示す実施例中で、修正した輪郭図は、三つの互いに繋がらないサブグラフで構成され、入力されたモデルの各頂点は三つのサブグラフに相応して分け、それぞれ菱形、円形、星形で表記する。
【００５６】
図９Ｂに示す実施例中で、修正した候補分割面によって、入力された輪郭図を四つのサブグラフに分割することができ、サブグラフ１、２、３、４と表記する。
【００５７】
図１０Ｂに示す実施例中で、修正した候補分割面によって、入力された輪郭図を二つのサブグラフに分割し、サブグラフ１とサブグラフ２と表記する。
【００５８】
３）三次元モデル分割装置は、上述の過程、２）で取得した各サブグラフに対して、すべてのサブグラフが選定された分割面を含むように必要な再編成を行う。
【００５９】
三次元モデル分割装置は、選定された候補分割面を含むかどうかによって、前の過程、２）で取得した各サブグラフを二つの種類に分けることができる。第一種類は、選定された候補分割面を含み、第二種類は、選定された候補分割面を含まない。前のステップにおけるサブグラフが何れも第一種類に属する場合に、三次元モデル分割装置は、これらのサブグラフに対して新たに処理を実行する必要がない。
【００６０】
図６に示すように、サブグラフ１とサブグラフ２は、いずれも選定された分割面を含んでいるので、三次元モデル分割装置は、これらのサブグラフに対して更に処理する必要がない。図９Ｂと図１０Ｂに示す各サブグラフは、何れも選定された分割面を含んでいるから、三次元モデル分割装置は、これらのサブグラフも更なる処理をする必要がない。
【００６１】
図７Ｃで示す三次元モデルでは、三次元モデル分割装置は、選定された候補分割面に基づいて、サブグラフ１、サブグラフ２とサブグラフ３という三つのサブグラフを取得することができる。サブグラフ１とサブグラフ３は図７Ａで表記した候補分割面を含み、第一種類に属する。サブグラフ２は選定された候補分割面を含まないので、第二種類に属する。このため、三次元モデル分割装置は、当該分割結果を更に処理する必要がある。
【００６２】
図８Ａ−８Ｃで示すモデルでは、三次元モデル分割装置は、選定される候補分割面によってサブグラフ１、サブグラフ２とサブグラフ３という三つのサブグラフを得ることができる。その中でサブグラフ１とサブグラフ３は、図８Ａで表記した候補分割面を含み、第一種類に属する。しかし、サブグラフ２は、選定される候補分割面を含まないので、第二種類に属する。したがって、三次元モデル分割装置は、当該分割結果を更に処理する必要がある。
【００６３】
第二種類のサブグラフが存在する場合、三次元モデル分割装置は、これらのサブグラフを処理する必要がある。三次元モデル分割装置は、第二種類のサブグラフに対して以下の二種類の状況に応じてそれぞれ処理すべきである。
【００６４】
１）当該サブグラフの各頂点がすべて選定される分割面の同じ側にある。三次元モデル分割装置は、頂点隣接グラフ或は当該サブグラフを取得するように分割された輪郭図を通して、当該サブグラフをそれと繋がっており且つ同じ側にあるサブグラフと新たに組み合わせて一つの新しいサブグラフを得る。そして、三次元モデル分割装置は、当該サブグラフを第二種類のサブグラフから削除する。ここで、サブグラフとサブグラフが繋がるというのは、頂点隣接グラフ或は当該サブグラフを取得するように分割された元の輪郭図のこれらのサブグラフの頂点間に接続が存在することを示す。すなわち、少なくとも一つの共通点を持つ。
【００６５】
図７Ｃで示す実施例の中で、三つのサブグラフと選定される分割面それぞれとの関係は、サブグラフ１の各頂点は選定される分割面の上方にあり、サブグラフ２とサブグラフ３の各頂点は選定される分割面の下方にあることになる。これと同時に、頂点隣接グラフを通して、サブグラフ２とその他の二つのサブグラフの頂点の間には接続が存在する。したがって、三次元モデル分割装置は、サブグラフ２とサブグラフ３を合併させ、一つの新しいサブグラフを構成する。三次元モデル分割装置は、サブグラフ２とサブグラフ１は合併しない。これはサブグラフ２とサブグラフ１が同じ側にないからである。この時、三次元モデル分割装置は、図７Ｃで示すモデルを図７Ｄに示す二つの部分に分けることができる。また、この二つの部分は何れも選定される分割面を含み、図７Ｄにおけるサブグラフ１’が図７Ｃにおけるサブグラフ１に対応し、サブグラフ２’が図７Ｃにおけるサブグラフ２と３を組み合わせて取得したサブグラフに対応することが分かる。
【００６６】
２）当該サブグラフの頂点は、選定される候補分割面の両側に分布しており、かつ頂点隣接グラフ或は当該サブグラフを取得するように分割された輪郭図を通して、第一種類に属するサブグラフと繋がっている場合に、当該サブグラフと繋がる第一種類の各サブグラフを一つの新しいサブグラフに新たに組み合わせ、当該サブグラフを第二種類サブグラフから削除する。
【００６７】
図８Ｃに示す実施例では、三つのサブグラフと候補分割面の関係は、サブグラフ１の頂点は、選定される候補分割面の上方にあり、サブグラフ２の頂点は、選定される選定分割面の両側に分布し、サブグラフ３の頂点は、選定分割面の下方にある。同時に、サブグラフ２の頂点は、頂点隣接グラフを通してサブグラフ１とサブグラフ３の頂点と繋がる。したがって、三次元モデル分割装置は、サブグラフ２をサブグラフ１、３と合併し、一つの新しいサブグラフを構成する。すなわち、図８で示す三次元モデルは、選定される候補分割面を利用して分割を実行してから一つのサブグラフを得て、分割する入力された三次元モデルと対応するサブグラフである。当然ながら、三次元モデル分割装置は、他の方式を採用して図８Ａ-８Ｃで示すモデルを少なくとも二つのサブグラフに分割することができるが、これは開示技術の検討の範囲にないので、ここでは詳しく述べないことにする。
【００６８】
続いて、三次元モデル分割装置は、ステップＳ５２０において、ステップＳ５１０で取得した各サブグラフの間の関係及びこれらサブグラフと選定される候補分割面の位置関係に基づいて、各サブグラフが穴に対応しているかどうかを判定する。それから、三次元モデル分割装置は、入力されたモデルの形状が分割後も変化しないことを維持するように穴を処理する。穴がある場合に、三次元モデル分割装置は、分割結果の中に独立した穴がないように、穴と穴に一番近い実体とを結合させる。このために、ステップＳ５２０の処理は、三つのサブステップを含む。１）、三次元モデル分割装置は、各サブグラフに対して、その輪郭情報に基づいて、選定される分割面における対応する有界区域を取得する。２）、三次元モデル分割装置は、各サブグラフに対して、それが穴であるかどうかを判定する。３）、三次元モデル分割装置は、穴と判定されたサブグラフに対して処理を行う。以下では順番にこの三つのサブステップを説明する。
【００６９】
１）三次元モデル分割装置は、前のステップＳ５１０で取得した各サブグラフに対して、選定される分割面における各領域を取得する。
【００７０】
三次元モデル分割装置は、各サブグラフに対して、その選定される候補分割面における輪郭線の情報に基づいて、閉鎖領域、すなわち、輪郭線が閉鎖する領域を取得する。輪郭線が閉鎖してない状況について、例えば、開示技術では公知の頂点凸包方法を採用して近似な閉鎖領域を取得することができ、或は既存の他の方法を採用して相対的に正確な閉鎖領域を取得する。なお、具体的な説明はここで述べないことにする。
【００７１】
本ステップを通じて、三次元モデル分割装置は、例えば図９Ｂに示す四つのサブグラフに対して、図９Ｃに示す四つの閉鎖領域を取得することができる。
【００７２】
２）三次元モデル分割装置は、本サブステップは前のサブステップで取得したサブグラフの選定される候補分割面での各閉鎖領域間の関係、及び各サブグラフと選定される候補分割面間の関係を利用して、穴の判定を実行する。三次元モデル分割装置が実行するこのステップでは、各サブグラフの選定される候補分割面にある閉鎖領域の間の関係によって、外から内へと逐一に判定する。
【００７３】
三次元モデル分割装置は、先ず一番外側にある閉鎖領域に対応するサブグラフを実体と判定する。ここで、「実体」は「穴」と区別していうものである。この規則は実際状況に合うものである。この規則に基づいて、図９Ｂに示す実施例で、三次元モデル分割装置は、サブグラフ１が対応する部分を実体であると判定する。三次元モデル分割装置は、図１０Ｂで示す二つのサブグラフは、サブグラフ１の選定される候補分割面にある閉鎖領域がサブグラフ２の相応する閉鎖領域の外側にあるから、サブグラフ１が対応する部分を実体であると判定する。
【００７４】
以下では、一番外側にある閉鎖領域に対応するサブグラフを除いたその他のサブグラフの判定方法を説明する。説明の明瞭、簡潔のために、先ず、あるサブグラフに「一番近いサブグラフ」という概念を定義する。あるサブグラフＡについて、それに一番近いサブグラフＢは先ず一つの実体でなければならず、同時にサブグラフＢが対応する領域はサブグラフＡが対応する領域を含まなければならない上にすべてのサブグラフＡの対応領域を含む領域の中で一番小さいものである。図９Ｃに示すように、サブグラフ３について、サブグラフ１がそれと対応する一番近いサブグラフである。サブグラフ１の対応する領域はサブグラフ３の対応領域を含むすべての領域の中で一番小さく、且つサブグラフ１に対応する部分が実体であるからである。同様に、サブグラフ１はサブグラフ２と４に対応する一番近いサブグラフでもある。
【００７５】
あるサブグラフとそれと一番近いサブグラフの関係、及びそれらと選定される分割面の位置関係に基づいて、三次元モデル分割装置は、以下の原則に応じてそのサブグラフが一つの穴を代表するかどうかを判定する。
三次元モデル分割装置は、当該サブグラフとそれと一番近いサブグラフの各頂点が選定される候補分割面に対して完全に反対の位置にある場合に、当該サブグラフは実体であると判定する。図９Ｃに示すように、選定される候補分割面の上の各頂点を除いて、サブグラフ３の各頂点は、すべて選定される分割面の前方にあるが、サブグラフ１の各頂点はすべて選定される分割面の後方にある。したがって、三次元モデル分割装置は、サブグラフ３の対応する部分は実体であると判定する。
三次元モデル分割装置は、当該サブグラフとそれと一番近いサブグラフの各頂点が選定される分割面に対して同じ側にある場合に、当該サブグラフは穴があると判定する。図９Ｃに示すように、選定される分割面の上の各頂点を除いて、サブグラフ２の各頂点は選定される分割面の後方に位置し、同時にサブグラフ１の各頂点も選定される分割面の後方にある。したがって、三次元モデル分割装置は、サブグラフ２が対応する部分は穴と判定する。同様に、三次元モデル分割装置は、サブグラフ４が対応する部分も穴と判定する。
以上の二つの原則を全部満足しない場合には、以下の原則を使う。選定される候補分割面を基準とし、当該サブグラフの当該選定される分割面にある頂点から出発して他の有界平面に接続した方向性ある線分と当該選定される候補分割面の法線ベクトルが選定される候補分割面の両側にある場合、当該サブグラフが対応する部分は穴と判定する。そうではないときは、実体と判定する。ここでの接続は輪郭線を通してつながり、すなわち、当該サブグラフに属しかつ選定される候補分割面に位置している頂点から出発して、他の有界平面上の頂点までのつながり線を指す。ここでは有界平面の法線方向がモデルの表面の外側に指していることをデフォルトとしている。図１０Ｂに示すように、サブグラフ２の選定される分割面にある頂点から出発して、他の有界平面に接続した輪郭線（一点鎖線で表す）と選定される分割面の法線ベクトル（実線で表す）が当該選定される候補分割面の両側にある。すなわち、一つは当該選定される候補分割面の下側にあり、一つはその上側にあるから、三次元モデル分割装置は、サブグラフ２が対応する部分は穴であると判定する。
【００７６】
３）穴に対しての処理のサブステップでは、入力された三次元モデルの形状を保つために、各穴とそれと一番近いサブグラフを組み合わせ、分割の結果に独立の穴が存在しないようにしなければならない。図９Ｃに示すように、サブグラフ２とサブグラフ４はサブグラフの１に組み合わせられ、一つの新しい実体になる。図１０Ｂで示すサブグラフ２はサブグラフ１に組み合わせられ、一つの新しい実体になる。
【００７７】
それから、三次元モデル分割装置は、穴のみに含まれている有界平面を非候補分割面と設定する。これによって穴が切られることを防止できると同時に、モデルの分割の複雑さと処理負荷を減らすことができる。
【００７８】
図５のフローチャートにおけるステップＳ５３０で、三次元モデル分割装置は、パラメーター化コントロール処理を実行する。応用によって、このステップではパラメーターを設定することができ、分割結果に対してコントロールを行い、例えば小さい部分だけ或は大きい部分だけが入力された三次元モデルから切り離される。例えば、あるサブグラフＡが切り離されることができるかどうかを判定するために、サブグラフＡとそれと一番近いサブグラフが選定される候補分割面上にある相応する閉鎖領域の面積の比をパラメーターとする。この比が予め設定されるある閾値より小さい場合に、サブグラフＡは、切り離される。この比が予め設定されるある閾値より大きい場合に、サブグラフＡは、それと一番近いサブグラフと組み合わせて一つの新しいサブグラフになる必要があり、独立した部分として切り離されない。
【００７９】
以下では、一つの実施例をもって具体的に説明する。図１１に示すように、実体１の選定される候補分割面での対応する閉鎖領域の面積はＡｒｅａ１=３９２.９９４と算出され、実体２の分割面での対応する閉鎖領域の面積はＡｒｅａ２=１１９.５６であり、Ａｒｅａ２/Ａｒｅａ１=０.３になる。ユーザーが設定した閾値が０.３より小さい場合に、三次元モデル分割装置は、実体２を切り離さずに、実体１と一つの物体に組み合わせる。ユーザーが設定した閾値が０.３以上の場合に、三次元モデル分割装置は、実体２と実体１はそれぞれ二つの物体として切り離す。注意すべきことは、図１１でのモデルは、図９でのモデルに対応している。前記で言ったように、図９で、二つのサブグラフ２と４は、何れも穴と判定され、且つサブグラフ１と組み合わせられる。したがって、図１１での実体１というのは図９におけるサブグラフ１＋２＋４で構成される新しい実体をさす。
【００８０】
当業者は、また他のパラメーターを設定して三次元モデルの「大」と「小」を表すことができるのが分かる。例えば、三次元モデル分割装置は、サブグラフが対応している部分の体積の大きさの比を通して、相応する部分が入力された三次元モデルから分割されるか否かを判定することができる。
【００８１】
三次元モデル分割装置は、ステップＳ５３０でのパラメーター化コントロール処理を必ず実行しなければならないものではない。この処理はモデルの分割の実用性を高めるものであるから、一種の最適化方案に属する。例えば、三次元モデル分割装置は、関連するパラメーターと閾値を設定することによって、三次元モデルの分割の「粒度」、すなわち、三次元モデルから切り離されるサブモデルが少し多いかもしくは少し少ないかをコントロールすることができる。これは実際の必要にあわせて相応する調整を行うことができるということは明らかなことである。
【００８２】
続いて、図５のフローチャートでのステップＳ５４０では、三次元モデル分割装置は、第ｉ個の選定される候補分割面を利用して上述の分割処理を行ってから取得したサブグラフの数が「１」より大きいか否かを判定する。すなわち、三次元モデル分割装置は、入力された三次元モデルを少なくとも二つのサブグラフに分割するかどうかを判定する。ステップＳ５４０の判定結果が「Ｙｅｓ」であれば、三次元モデル分割装置は、ステップＳ５５０で分割して取得したサブグラフを出力して図４のステップＳ４２０に戻る。ステップＳ５４０の判定結果が「Ｎｏ」であれば、三次元モデル分割装置は、ｉ=ｉ＋１（ステップＳ５６０）にし、第（ｉ+１）個の選定される候補分割面を利用して、ステップＳ５１０からＳ５４０までの処理を繰り返す。ここで、ステップＳ５４０の判定結果が「Ｎｏ」であるとは、第ｉ個の選定される候補分割面を利用して上述の分割処理を行ってから取得したサブグラフの数が「１」より大きくない（もしくは、１と同じ）場合である。ｎ個の候補分割面におけるすべての分割面を利用して分割を行った結果、三次元モデルを少なくとも二つのサブグラフに分割することができない場合、フローは同様に図４におけるステップＳ４２０に戻る。ここで、三次元モデルを少なくとも二つのサブグラフに分割することができないとは、入力された三次元モデルを一つのサブグラフにしか分割しない場合（ステップＳ５８０）である。例えば、図９Ａ−９Ｃで示す状況が入力された三次元モデルを一つのサブグラフ、すなわち、その三次元モデル自体と対応するサブグラフに分割することである。図５から分かるように、ｎ個の候補分割面における任意の一つの分割面が三次元モデルを少なくとも二つの重複しないサブグラフに分割することができれば、図４におけるステップＳ４２０に入る。そして、これらのサブグラフの分割結果に対して分割を終わらせるかどうかを判定し、ｎ個の候補分割面における他の分割面を利用して三次元モデルを分割する処理をそれぞれ行わない。当業者は，別の選択方案として、ｎ個の候補分割面における各分割面を順番に利用して、上述のような入力された三次元モデルを分割する処理を行うこともできる。そして、当業者は、これによって取得した各候補分割面と対応する各種の分割結果を実際の必要に応じて選択して使うことができる。
【００８３】
その他、上述の候補分割面を利用して三次元モデルに対して分割を行う処理では、候補分割面を探さず、直接、前の処理で検出された全部の有界平面を分割面として利用して三次元モデルの輪郭図に対して分割を行ってもよい。その処理の方式は上述の候補分割面を利用する分割処理方式と似ているから、ここでは詳しく述べない。
【００８４】
図４のプロセスに戻る。ステップＳ４２０では図５のステップＳ５５０或はＳ５８０の処理で取得したサブグラフに対して終了条件の判定を行い、当該サブグラフが引き続きの分割を必要とするか否か、すなわち、分割を終了する条件を満たすかどうかを判定する。三次元モデル分割装置は、以下の原則を採用して判定を実行することができ、あるサブグラフが以下の原則の任意の一項目を満たす場合に、当該サブグラフは引き続きの分割を必要としないと判定する。
当該サブグラフの頂点の数が８より小さい。これは任意の三次元物体が少なくとも四つの面を共有しない頂点を持たなければならないからである。例えば三角錘は分割されない。ここで、数字「４」は、モデルが分割できるのに許容する最小の数字であり、この数字は実際の状況によって変更することができる。
当該サブグラフの面の数は６より小さい。これは任意の三次元物体が少なくとも四つの異なる平面を含まなければならないからである。例えば三角錘は分割されない。数字「４」は、モデルが分割できるのに許容する最小の数字であり、この数字は実際の状況によって修正変更することができる。
当該サブグラフのすべての有界平面には候補分割面が存在しない。例えば図６のサブグラフ１が含む六つの有界平面には候補分割面が存在しない。同様に、図６に示すサブグラフ２、図７に示すサブグラフ１は、何れも候補分割面を含んでいない。
当該サブグラフは候補分割面を含んでいるが、候補分割面はいずれも当該サブグラフを複数の部分に分割することができない。図１０のモデルに、サブグラフ１は候補分割面を含んでいるが、その分割面を通して当該サブグラフを複数の部分に分割することができないから、当該モデルは引き続き分割ができない。
【００８５】
ステップＳ４２０の判定で、あるサブグラフに対して引き続きの分割を必要とすると判定される場合に、三次元モデル分割装置は、当該サブグラフが含んでいる候補分割面を使ってこれに対して引き続き分割を行う（Ｓ４４０）。すなわち、三次元モデル分割装置は、当該サブグラフが含んでいる候補分割面を選定される候補分割面として、当該サブグラフと対応する輪郭図が少なくとも二つの互いに重複しないサブグラフに分割されるまで、当該サブグラフが対応する輪郭図に対して分割を行う。サブグラフに対する接続分割の具体的処理方式は上述の図４−５を参照しながら述べた分割処理と類似しているので、ここでは述べない。
【００８６】
以上では、各図面を参照して、開示技術の実施例による三次元モデルに対する分割の方法を詳しく記述した。代わりとして実施が可能な形態として、開示技術の実施例による三次元モデル分割方法のフローチャートの略図を示す図１において、有界平面生成ステップＳ１１０を実行する前に、三次元モデルの予分割ステップをさらに実行することもできる。三次元モデル分割装置が実行する予分割ステップは、入力された三角形ポリゴンで表現される前記三次元モデルを複数の独立した、互いに繋がらない部分に分割する。当該ステップの処理は、特に一つの情景に複数の独立した物体が置いてある状況に適用する。当該ステップの処理では、三次元モデル分割装置は、先ず、入力された三次元モデルの三角形ポリゴンデータに基づいて、頂点隣接グラフを構築する。それから、三次元モデル分割装置は、頂点隣接グラフがつながっているかどうかを判定する。三次元モデル分割装置は、頂点隣接グラフの任意の１対のノードの間に接続パスが存在する場合に、このグラフは繋がっていると判定し、そうでなければ，繋がっていないと判定する。ここでのパスは、普通、一辺か或は複数の辺で構成されているものである。頂点隣接グラフがつながっておらず、すなわち、隣接グラフが複数の互いにつながっていない、分離しているサブグラフで構成される場合には、これらのサブグラフに対応して、入力された三次元モデルは、複数の互いに繋がらないサブモデルに分割できる。頂点隣接グラフが繋がっている場合には、入力された分割対象である三次元モデルは、予分割のステップで分割されなく、まだ一つの三次元モデルである。
【００８７】
図１２Ａ−１２Ｃは、開示技術の実施例による三次元モデル分割方法において分割する三次元モデルを予め複数の互いに分離するサブモデルに分割することを模式的に示す図である。図１２Ａは入力された分割対象である三次元モデルを表し、図１２Ｂは構築した頂点隣接グラフであり、頂点隣接グラフが四つの互いに繋がらない、分離しているサブグラフで構成されているのが分かる。これに相応して、図１２Ａのモデルは、図１２Ｃに示す四つの独立したサブモデルに分割される。
【００８８】
別の方案として、三次元モデル分割装置は、三角形隣接グラフを採用して上述のモデル予分割の処理を実現することができる。三角形隣接グラフが繋がらない時、三次元モデル分割装置は、入力された三次元モデルを複数の独立したサブモデルに分割することができる。前記の開示技術の具体的実施例による記述から分かるように、分割対象である三次元モデルは二つの部分の基本データを含む。すなわち、モデル頂点及びモデル表面を構成する三角形である。三次元モデル分割装置は、三角形隣接グラフを複数の分離するサブグラフに分割し、すなわち三次元モデルの表面を構成している三角形を分けると、モデルの頂点を分けることができる。三次元モデル分割装置は、頂点隣接グラフを複数の分離しているサブグラフに分割し、すなわちモデルの頂点を分けると、入力されたモデルの表面を構成している三角形を分けることができる。したがって、三角形隣接グラフを採用してモデルの予分割処理を実行する処理は、上述の頂点隣接グラフを採用してモデルの予分割処理を実行することと類似しており、ここでは詳細を述べないことにする。
【００８９】
入力されたモデルが予分割により複数の三次元サブモデルに分割される場合に、分割で得られた三次元サブモデルのそれぞれに対して上述の処理を行う。この予分割処理は、後続の処理の計算量と複雑度を下げるのに役立つから、これは最適化の処理であるということは容易に理解できる。モデルの予分割処理を実行しなくても、開示技術による三次元モデルの分割の実行には影響しない。
【００９０】
もう一つの別の実施の形態として、図１のフローチャートのステップＳ１３０の後、三次元モデルの輪郭図の再構成処理を実行することもできる。三次元モデルの輪郭図の再構成処理で、ステップＳ１２０で取得した、入力された三次元モデルの輪郭図、及び当該輪郭図が含む有界平面の情報に基づいて、選定される候補分割面を利用して三次元モデルを分割することにより取得した各サブグラフに対して処理を行い、これによって分割対象である三次元モデルを構成する相応する立体コンポーネントを再構成し、三角形ポリゴンでそれを表現する。上述のように、選定される候補分割面を利用してモデルの分割を行う過程で、選定される候補分割面及びその他の一部の有界平面に変化が発生する可能性がある。これらの有界平面が新たに三角化されなければ、三次元モデルの閉鎖性を確保することができない。これと同時に、変化が起らなかった有界平面のデータは、そのまま使用することができ、それによって再構成の処理負荷を減らす。その他、入力された三次元モデルの元の三角形ポリゴンデータは、新しく生成された三角形の方向を補正するのに役立つ。
【００９１】
具体的に、三次元モデル分割装置は、分割の過程で変化が生じた有界平面に対して、上述の穴であると判定したサブグラフに対する処理に類似した処理方法を採用し、この有界平面上の閉鎖領域を取得して、それを多角形で表すことができる。三次元モデル分割装置は、既知の各種の多角形の三角化技術を採用して、多角形から一連の三角形を取得することができる。例えば、三次元モデル分割装置は、上述の「非特許文献６」に開示された方法を採用することができる。この方法は簡単な多角形（凹多角形と凸多角形を含む）と複雑な多角形（穴を含む多角形）の三角化を実現することができる。この方法を応用する前に、三次元モデル分割装置は、先ず、各多角形の方向及び多角形の間の含み関係を判定する必要がある。このため、三次元モデル分割装置は、一番外側にある多角形の方向が時計回りと逆方向で、内部の多角形の方向が時計回りの方向になるように各多角形を適宜に構成させる。例えば、三次元モデル分割装置は、上述の「非特許文献９」で公開した方法で多角形の方向を判定することができる。三次元モデル分割装置は、すべての変化が生じた有界平面に対して再構成処理が終わってから、三次元モデルの元の三角形ポリゴンデータに基づいて、すべての三角形の法線方向が三次元モデルの表面の外側に向くように、新しく生じた三角形の方向を補正する。
【００９２】
三次元モデル分割装置は、三次元モデルの輪郭図の再構成処理を経てから、入力された分割対象である三次元モデルを構成する、三角形ポリゴンデータで表現される一連の閉鎖した立体コンポーネントを取得することができる。
【００９３】
ここで、説明すべきことは、もっとはっきりと開示技術実施例に基づく三次元モデル分割方法を説明するために、各処理ステップは異なる図面における異なるモデルの実施例を参照しながらそれぞれ説明した。しかし、当業者は、上述の各図面で言及したモデルのそれぞれに対して、開示技術に基づくこのような三次元モデル分割方法で分割処理を行うことができることが分かる。詳細はここでは述べないことにする。
【００９４】
開示技術のほかの実施例に基づいて、三次元モデルを分割する装置も提供する。図１３は、開示技術の実施例の三次元モデル分割に用いられる装置を模式的に示すブロック図である。図１３に示すように、当該三次元モデルを分割する装置１０００は、有界平面生成部１２００と、輪郭図抽出部１３００と、輪郭図分割部１４００とを含む。有界平面生成部１２００は、入力された三次元モデルの三角形ポリゴンデータに基づいて、三次元モデルに含まれるすべての三角形を処理し、三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する。輪郭図抽出部１３００は、生成した有界平面を通して三次元モデルの輪郭図を抽出する。輪郭図分割部１４００は、生成した有界平面の情報及び三次元モデルの頂点隣接グラフの情報に基づいて、抽出した輪郭図を一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する。
【００９５】
別の実施の形態として、図１３での三次元モデルを分割する装置１０００は、予分割部１１００を更に含むことができる。予分割部１１００は、入力された三次元モデルの三角形ポリゴンデータに含む三角形データと頂点データに基づいて、入力された三次元モデルを一つのサブモデル或は少なくとも二つの互いに分離するサブモデルに予分割する。有界平面生成部１２００、輪郭図抽出部１３００と輪郭図分割部１４００は、サブモデルのそれぞれを一つのサブモデル或は少なくとも二つの互いに分離しているサブモデルに分割するように、予分割部１１００で生成された一つのサブモデル或は少なくとも二つの互いに分離しているサブモデルにおける各モデルに対して相応する処理を実行する。
【００９６】
もう一種の別の実施の形態として、図１３での三次元モデルを分割する装置１０００は、モデル再構成部１５００を更に含む。モデル再構成部１５００は、三次元モデルを構成する、三角形ポリゴンで表現される一連の立体コンポーネントを再構成するように、分割された一つサブグラフ或は少なくとも互いに重複しない二つのサブグラフ及び三次元モデルの三角形ポリゴンデータに基づいて三角化の処理を実行する。
【００９７】
当業者は、図１３で示す三次元モデル分割装置１０００が含む有界平面生成部１２００、輪郭抽出部１３００、輪郭図分割部１４００、予分割部１１００及びモデル再構成部１５００は、上述の図１、図４、図５を参照して説明した各種の処理、及びこれらの図面では示していないが既に上記の各種の具体的実施例で十分に説明した前記三次元モデル分割方法を実行するように配置されることが分かる。
【００９８】
開示技術の実施例に対して、図面と合わせて説明を参照することにより、開示技術の前述した内容及びその他の目的、特徴及び優れているところを更に理解しやすくなる。図面でのコンポーネントは実際の比率に照らして描かれたものではなく、ただ開示技術の原理を示すためである。なお、すべての図面において、同一或は類似した技術特徴またコンポーネントは、同一或は類似した記号で表示される。
【００９９】
以上の開示技術の具体的実施例に関する記述の中で、一種の実施の形態に対して記述及び/又は示した特徴は、同一或は類似の方式で一つ或はより多くの他の実施の形態で使用されることができる。
【０１００】
強調すべきことは、用語「含む/含まれる」が本文で使用される場合は、特徴、要素、ステップ或はコンポーネントの存在を指し、一つ或はより多くのその他の特徴、要素、ステップ或はコンポーネントの存在又は付加を排除しない。
【０１０１】
なお、開示技術の方法は明細書に述べた説明の順番で実行することに限らず、他の説明に従って順番に、並行的に或は独立的に実行してもよい。したがって、本明細書で述べた方法の実行順番は開示技術の技術範囲を限定しない。
【０１０２】
以上で、開示技術の具体的な実施例に関する記述を通して、開示技術を説明したが、理解するべきは、当業者は添付された請求項の技術的思想の範囲以内で、開示技術に対しての各種の修正、改良或は同等ものが設計できる。これらの修正、改良或は同等であるものは開示技術の保護範囲内に含まれるものと認められるべきである。
【０１０３】
上述の装置における各構成部は、ソフトウェア、ハードウェア或はこれらの組み合わせの方式で配置することができる。配置で使える具体的手段或は方式は、当業者の良く知っているものであるので、ここでは詳しく述べないことにする。
【０１０４】
また、開示技術の他の実施例は、画像処理システムを提供する。この画像処理システムは上述の図１３で示した開示技術の実施例による三次元モデル分割装置を備えるので、上述の開示技術の実施例による三次元モデル分割方法を実行するのに適用することができる。
【０１０５】
この画像処理システムは、例えば目標検査システム、部分マッチングシステム、モデル検索システムなどである。
【０１０６】
また、開示技術のその他の実施例による三次元モデルを分割する方法は、機器が読取り可能な指令コードが格納されているプログラムの製品を通して実現することができる。このような指令コードは、機器、例えばコンピュータ、に読み取られて実行される時に、上述の開示技術の実施例による三次元モデル分割方法の全部の操作過程とステップを実行することができる。そのプログラム製品は、任意の表現形式を持つことができ、例えば目標プログラム、インタプリターで実行するプログラム或は操作システムに提供したシナリオプログラムなどである。
【０１０７】
それに相応して、上述の機器が読取り可能な指令コードが格納されているプログラムの製品を載せている記憶媒体も開示技術の公開に含まれる。前記記憶媒体は、フロッピー（登録商標）ディスク、光ディスク、光磁気ディスク、メモリーカード、メモリースティックなどを含むがこれらに限定されない。
【０１０８】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１０９】
（付記１）三次元モデル分割装置が、
入力された三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルに含まれるすべての三角形を処理し、当該三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する有界平面生成ステップと、
前記生成した有界平面を通して前記三次元モデルの輪郭図を抽出する輪郭図抽出ステップと、
前記生成した有界平面の情報及び前記三次元モデルの頂点隣接グラフの情報に基づいて、前記抽出した輪郭図を所定条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する輪郭図分割ステップとを含み、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルの頂点をノードとして、一つ或は複数の三角形に共有される二つの頂点の間ごとに一辺を追加して前記頂点隣接グラフの構築をすること
を特徴とする三次元モデル分割方法。
【０１１０】
（付記２）三次元モデル分割装置が、
前記有界平面生成ステップの前に、入力された三次元モデルの三角形ポリゴンデータに含む三角形データと頂点データに基づいて、当該入力された三次元モデルを一つのサブモデル或は少なくとも二つの互いに分離するサブモデルに予分割する予分割ステップを更に含み、
前記サブモデルのそれぞれを所定の条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割するように、当該サブモデルそれぞれに対してそれぞれ前記有界平面生成ステップ、前記輪郭図抽出ステップ及び前記輪郭図分割ステップを実行すること
を特徴とする付記１に記載の三次元モデル分割方法。
【０１１１】
（付記３）前記予分割ステップは、
前記三次元モデルの三角形ポリゴンデータに基づいて頂点隣接グラフを構築し、
前記頂点隣接グラフが繋がっているかどうかを判定し、当該頂点隣接グラフにおける何れか１対の頂点の間に接続パスが存在すれば、当該頂点隣接グラフは繋がっていると判定し、当該頂点隣接グラフにおける何れか１対の頂点の間に接続パスが存在しなければ、繋がっていないと判定し、
前記頂点隣接グラフが繋がっていないと判定すれば、当該頂点隣接グラフに互いに繋がらないサブグラフに対応して前記三次元モデルを少なくとも二つの互いに分離するサブモデルに分割すること
を特徴とする付記２に記載の三次元モデル分割方法。
【０１１２】
（付記４）前記予分割ステップは、
前記三次元モデルの三角形ポリゴンデータに基づいて三角形隣接グラフを構築することと、
前記三角形隣接グラフが繋がっているかどうかを判定し、ここで、当該三角形隣接グラフにおける何れか１対の三角形の間に接続パスが存在すれば、当該三角形隣接グラフは繋がっていると判定し、当該三角形隣接グラフにおける何れか１対の三角形の間に接続パスが存在しなければ繋がっていないと判定することと、
前記三角形隣接グラフが繋がっていないと判定すれば、当該三角形隣接グラフに互いに繋がらないサブグラフに対応して前記三次元モデルを少なくとも二つの互いに分離するサブモデルに分割することを含み、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルにおける三角形をノードとして、共通点を有する二つの三角形の間ごとに辺を追加して前記三角形隣接グラフを構築すること
を特徴とする付記２に記載の三次元モデル分割方法。
【０１１３】
（付記５）三次元モデル分割装置が、
前記輪郭図分割ステップの後に、前記三次元モデルを構成する、三角形ポリゴンで表現される一連の立体コンポーネントを再構成するように、前記分割された一つのサブグラフ或は少なくとも互いに重複しない二つのサブグラフ及び当該三次元モデルの三角形ポリゴンデータに基づいて三角化の処理を実行するモデル再構成ステップを更に含むこと
を特徴とする付記１ないし４の何れか一項に記載の三次元モデル分割方法。
【０１１４】
（付記６）前記有界平面生成ステップは、
前記三次元モデルに含まれるすべての三角形それぞれを一つのサブ平面として、すべてのサブ平面を合成できなくなるまで、合成条件を満たすサブ平面を一つの新しいサブ平面に合成して広義の平面を生成し、
前記三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成するように、前記広義の平面のそれぞれに対して以下の処理を実行することを含み、
前記広義の平面にある三角形に対して三角形隣接グラフを作成し、
前記三角形隣接グラフで前記広義の平面の三角形が複数の分離するサブ平面に分けることができ、且つ当該サブ平面のそれぞれが複数の互いに接続する三角形を含む場合に、当該広義の平面を前記複数の分離するサブ平面に分け、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルにおける三角形をノードとして、共通点を有する二つの三角形の間に一辺を追加して前記三角形隣接グラフを構築し、
前記広義の平面を分けて得る前記複数の分離するサブ平面における複数のサブ平面を同時に他の同一の平面と繋がっている場合に、これらのサブ平面を一つの組み合わせる有界平面として組み合わせ、
前記組み合わせた有界平面及び前記広義の平面を分けて得る前記複数の分離するサブ平面における組み合わせる必要のない有界平面によって前記三次元モデルの分割に適用する前記有界平面を共同で構成し、
前記複数のサブ平面がそれぞれ前記他の同一の平面との間に少なくとも一つの共通点が存在する場合に、当該複数のサブ平面は同時に当該他の同一の平面と互いに繋がると判定し、
前記頂点隣接グラフにおいて、あるサブ平面に繋がる頂点が当該サブ平面の同じ側に位置する場合に、当該サブ平面は前記組み合わせる必要のない有界平面における独立する有界平面と判定すること
を特徴とする付記１ないし５の何れか一項に記載の三次元モデル分割方法。
【０１１５】
（付記７）前記有界平面生成ステップにおいて、サブ平面を合成できる条件は、
前記サブ平面の法線方向が同じ又は反対であることと、
前記サブ平面の頂点が同一の平面に位置することを含み、
前記サブ平面と関連する三角形の法線方向を当該サブ平面の法線方向とすること
を特徴とする付記６に記載の三次元モデル分割方法。
【０１１６】
（付記８）前記輪郭図抽出ステップは、
前記三次元モデルの頂点を輪郭図の頂点とし、各頂点の間には接続が存在せず、
前記有界平面生成ステップで生成したそれぞれの有界平面に対して、当該有界平面生成ステップで生成した有界平面から当該有界平面と繋がる有界平面を探し、
前記有界平面と当該有界平面と繋がっている有界平面の境界線に位置する頂点を取得し、複数の線分を取得するように各頂点を互いに繋ぎ、
前記三次元モデルの輪郭図を得るように、前記取得した複数の線分から互いに重複しない、有界平面の内部の辺と異なる線分を輪郭線として選択し、各輪郭線は少なくとも二つの異なる有界平面に接続し、且つその一辺が当該輪郭線を含むようにそれぞれの有界平面に一つの三角形が存在し、内部の辺は一つの有界平面内だけに位置し、或は同じ有界平面上の複数の三角形に共有される方式で前記三次元モデルの輪郭図を抽出すること
を特徴とする付記１ないし７の何れか一項に記載の三次元モデル分割方法。
【０１１７】
（付記９）前記輪郭図分割ステップは、
前記生成された有界平面から、頂点の数が４以上であり、且つ前記三次元モデルの頂点が両側に分布するような、候補分割面をすべて検出する候補分割面検出サブステップと、
前記検出された候補分割面の中から分割面として選定された候補分割面を用いて、前記輪郭図が一つ或は少なくとも二つの互いに重複しないサブグラフに分割されるまで、前記輪郭図を逐一に分割するモデル分割サブステップと、
前記モデル分割サブステップで分割された前記サブグラフそれぞれに対して引き続きの分割をする必要があるかどうかを判定し、必要であれば、当該サブグラフが含んでいる候補分割面を選定された候補分割面として、当該サブグラフの対応する輪郭図を少なくとも二つの互いに重複しないサブグラフに分割するまで、当該サブグラフの対応する輪郭図に対して分割を行う終了条件判定サブステップと
を含んだことを特徴とする付記１ないし８の何れか一項に記載の三次元モデル分割方法。
【０１１８】
（付記１０）前記モデル分割サブステップは、
選定される候補分割面により以下の処理を実行することが含まれ、
すべてのサブグラフが選定される当該候補分割面を含むように、当該選定される候補分割面により輪郭図を一つ或は少なくとも二つの互いに重複しないサブグラフに分割する処理と、
前記分割されたサブグラフにおける穴と判定されたサブグラフと、当該サブグラフと一番近い実体になるサブグラフとを結合させて新しい実体を取得する処理と、
前記取得した実体それぞれに対してどの実体を分割の結果とするのかを判定する処理と
を含んだことを特徴とする付記９に記載の三次元モデル分割方法。
【０１１９】
（付記１１）前記選定される候補分割面により輪郭図を一つ或は少なくとも二つの互いに重複しないサブグラフに分割する処理は、
前記選定される候補分割面上に位置している輪郭線を削除し、修正後の輪郭図を取得し、
前記修正後の輪郭図の頂点の間の接続関係によって、修正後の輪郭図を一つ或は少なくとも二つの互いに重複しないサブグラフに分割し、
すべての前記サブグラフが前記選定される候補分割面を含むように、取得した繋がらない当該サブグラフそれぞれに対して再構成を実行し、
前記サブグラフの中で、前記選定される候補分割面を含んでいないサブグラフについて、当該サブグラフの各頂点がいずれも選定される候補分割面の同じ側に位置している場合に、頂点隣接グラフ或は分割されて当該サブグラフを取得した輪郭図により、当該サブグラフとそれと繋がっており且つ同じ側に位置しているサブグラフを再構成させて一つの新しいサブグラフを取得し、前記サブグラフの中で、前記選定される候補分割面を含んでいないサブグラフについて、当該サブグラフの頂点が選定される候補分割面の両側に位置し、かつ頂点隣接グラフ或は分割されて当該サブグラフを取得した輪郭図により前記選定される候補分割面を含むサブグラフと接続する場合に、当該サブグラフとそれと接続するサブグラフを一つの新しいサブグラフに再構成させ、
前記再構成されないサブグラフ及び前記再構成して取得した新しいサブグラフによって輪郭図から分割されて取得した前記一つ或は少なくとも二つの互いに重複しないサブグラフを構成することを含むこと
を特徴とする付記１０に記載の三次元モデル分割方法。
【０１２０】
（付記１２）前記モデル分割サブステップは、
前記サブグラフそれぞれの輪郭の情報に基づいて、当該サブグラフが選定される候補分割面での対応する閉鎖領域を取得する処理と、
取得した当該サブグラフの選定される候補分割面での各閉鎖領域間の関係、及び当該サブグラフと選定される候補分割面の関係を利用して、穴であるかどうかを判定する処理と、
前記穴と判定された前記サブグラフに対して新しい実体を取得する処理と
を含むことを特徴とする付記１０に記載の三次元モデル分割方法。
【０１２１】
（付記１３）前記サブグラフが穴であるかどうかを判定する処理は、
一番外側に位置している閉鎖領域が対応するサブグラフを実体と判定し、
一番外側に位置している閉鎖領域が対応するサブグラフを除くその他のサブグラフと前記その他のサブグラフと一番近いサブグラフとの相互関係に基づいて、以下の原則に応じてその他のサブグラフが穴であるかどうかをそれぞれ判定し、
前記原則は、
前記サブグラフ及び当該サブグラフと一番近いサブグラフがいずれも選定される候補分割面の同じ側に位置している場合に、当該サブグラフサブグラフを穴と判定し、
前記サブグラフ及び当該サブグラフと一番近いサブグラフが選定される候補分割面の完全に反対の側に位置している場合に、当該サブグラフを実体と判定し、
選定される候補分割面を基準として、当該サブグラフに属し且つ当該選定される候補分割面にある頂点から出発してその他の有界平面に接続した方向性がある線分及び当該選定される候補分割面の法線ベクトルが当該選定される候補分割面の両側にある場合に、当該サブグラフを穴と判定し、
選定される候補分割面を基準として、当該サブグラフに属し且つ当該選定される候補分割面にある頂点から出発してその他の有界平面に接続した方向性がある線分及び当該選定される候補分割面の法線ベクトルが当該選定される候補分割面の両側にない場合に、当該サブグラフを実体と判定することを含み、
その中、あるサブグラフについて、当該サブグラフと一番近いサブグラフは一つの実体であり、同時に当該一番近いサブグラフの対応する閉鎖領域は当該サブグラフの相応する閉鎖領域を含み、且つ当該サブグラフの相応するすべての閉鎖領域の中では一番小さい領域を含むこと
を特徴とする付記１２に記載の三次元モデル分割方法。
【０１２２】
（付記１４）三次元モデル分割装置が、
前記分割して取得したサブグラフの中に独立した穴が存在しないように、前記穴と判定されたサブグラフ及び当該サブグラフと一番近いサブグラフとを組み合わせ、且つその穴の内部だけに含まれている有界平面を非候補分割面に設定する処理をさらに実行すること
を特徴とする付記１３に記載の三次元モデル分割方法。
【０１２３】
（付記１５）前記モデル分割サブステップは、
所定条件を満たす部分だけが三次元モデルから分割されるように、予め設定されたパラメーターにより分割結果に対してコントロールを実行すること
を特徴とする付記１０に記載の三次元モデル分割方法。
【０１２４】
（付記１６）前記予め設定されたパラメーターは、
前記サブグラフと当該サブグラフと一番近いサブグラフの選定される候補分割面での相応する領域面積の比であり、
前記領域面積の比が予め設定された閾値より小さい場合に、前記サブグラフは分割して出され、
前記領域面積の比が予め設定された前記閾値より大きい場合に、前記サブグラフと当該サブグラフに一番近いサブグラフとは新しいサブグラフに組み合わせられ、独立した部分として分割して出されないこと
を特徴とする付記１５に記載の三次元モデル分割方法。
【０１２５】
（付記１７）前記終了条件判定サブステップは、
前記サブグラフが以下の条件のうち任意の一つを満たす時に、当該サブグラフは引き続き分割を行う必要がないと判定し、
前記条件は、
前記サブグラフの頂点の数が所定の第一閾値より小さい、
前記サブグラフが含む有界平面の数が所定の第二閾値より小さい、
前記サブグラフが含むすべての有界平面において候補分割面が存在しない、
前記サブグラフに当該サブグラフと対応する輪郭図を少なくとも二つのサブグラフに分割することができる候補分割面が存在しない、
ことであること
を特徴とする付記９に記載の三次元モデル分割方法。
【０１２６】
（付記１８）前記第一閾値は８で、前記第二閾値は６であることを特徴とする付記１７に記載の三次元モデル分割方法。
【０１２７】
（付記１９）入力された三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルに含まれるすべての三角形を処理し、当該三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する有界平面生成部と、
前記生成した有界平面を通して前記三次元モデルの輪郭図を抽出する輪郭図抽出部と、
前記生成した有界平面の情報及び前記三次元モデルの頂点隣接グラフの情報に基づいて、前記抽出した輪郭図を所定条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する輪郭図分割部とを含み、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルの頂点をノードとして、一つ或は複数の三角形に共有される二つの頂点の間ごとに一辺を追加して前記頂点隣接グラフを構築すること
を特徴とする三次元モデル分割装置。
【０１２８】
（付記２０）入力された三次元モデルの三角形ポリゴンデータに含む三角形データと頂点データに基づいて、当該入力された三次元モデルを一つのサブモデル或は少なくとも二つの互いに分離するサブモデルに予分割する予分割部を更に含み、
前記有界平面生成部、前記輪郭図抽出部及び前記輪郭図分割部は、前記サブモデルのそれぞれを所定の条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割するように、当該サブモデルそれぞれに対して処理を実行すること
を特徴とする付記１９に記載の三次元モデル分割装置。
【０１２９】
（付記２１）前記三次元モデルを構成する、三角形ポリゴンで表現される一連の立体コンポーネントを再構成するように、前記分割された一つサブグラフ或は少なくとも互いに重複しない二つのサブグラフ及び当該三次元モデルの三角形ポリゴンデータに基づいて三角化の処理を実行するモデル再構成部を更に含むこと
を特徴とする付記１９又は２０に記載の三次元モデル分割装置。
【０１３０】
（付記２２）前記有界平面生成部は、
前記三次元モデルに含まれるすべての三角形それぞれを一つのサブ平面として、すべてのサブ平面を合成できなくなるまで、合成条件を満たすサブ平面を一つの新しいサブ平面に合成して広義の平面を生成し、
前記三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成するように、前記広義の平面のそれぞれに対して以下の処理を実行することを含み、
当該広義の平面にある三角形に対して三角形隣接グラフを作成し、
前記三角形隣接グラフで前記広義の平面の三角形が複数の分離するサブ平面中に分けることができ、且つ当該サブ平面のそれぞれが複数の互いに接続する三角形を含む場合に、当該広義の平面を前記複数の分離するサブ平面に分け、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルにおける三角形をノードとして、共通点を有する二つの三角形の間に一辺を追加して前記三角形隣接グラフを構築し、
前記広義の平面を分けて得る前記複数の分離するサブ平面における複数のサブ平面を同時に他の同一の平面と繋がっている場合に、これらのサブ平面を一つの組み合わせる有界平面として組み合わせ、
前記組み合わせた有界平面及び前記広義の平面を分けて得る前記複数の分離するサブ平面における組み合わせる必要のない有界平面によって前記三次元モデルの分割に適用する前記有界平面を共同で構成し、
前記複数のサブ平面がそれぞれ前記他の同一の平面との間に少なくとも一つの共通点が存在する場合に、当該複数のサブ平面は同時に当該他の同一の平面と互いに繋がると判定し、
前記頂点隣接グラフにおいて、あるサブ平面に繋がる頂点が当該サブ平面の同じ側に位置する場合に、当該サブ平面は前記組み合わせる必要のない有界平面における独立する有界平面と判定するように配置されること
を特徴とする付記１９ないし２１の何れか一項に記載の三次元モデル分割装置。
【０１３１】
（付記２３）前記輪郭図抽出部は、
前記三次元モデルの頂点を輪郭図の頂点とし、各頂点の間には接続が存在せず、
前記有界平面生成部で生成したそれぞれの有界平面に対して、当該有界平面生成部で生成した有界平面から当該有界平面と繋がる有界平面を探し、
前記有界平面と当該有界平面と繋がっている有界平面の境界線に位置する頂点を取得し、複数の線分を取得するように各頂点を互いに繋ぎ、
前記三次元モデルの輪郭図を得るように、前記取得した複数の線分から互いに重複しない、有界平面の内部の辺と異なる線分を輪郭線として選択し、各輪郭線は少なくとも二つの異なる有界平面に接続し、且つその一辺が当該輪郭線を含むようにそれぞれの有界平面に一つの三角形が存在し、内部の辺は一つの有界平面内だけに位置し、或は同じ有界平面上の複数の三角形に共有される方式で前記三次元モデルの輪郭図を抽出するように配置されること
を特徴とする付記１９ないし２２の何れか一項に記載の三次元モデル分割装置。
【０１３２】
（付記２４）前記輪郭図分割部は、
前記生成された有界平面から、頂点の数が４以上であり、且つ前記三次元モデルの頂点が両側に分布するような、候補分割面をすべて検出する候補分割面検出サブ部と、
前記検出された候補分割面の中から分割面として選定された候補分割面を用いて、前記輪郭図が一つ或は少なくとも二つの互いに重複しないサブグラフに分割されるまで、前記輪郭図を逐一に分割するモデル分割サブ部と、
前記モデル分割サブ部で分割された前記サブグラフそれぞれに対して引き続きの分割をする必要があるかどうかを判定し、必要であれば、当該サブグラフが含んでいる候補分割面を選定された候補分割面として、当該サブグラフの対応する輪郭図を少なくとも二つの互いに重複しないサブグラフに分割するまで、当該サブグラフの対応する輪郭図に対して分割を行う終了条件判定サブ部と
を特徴とする付記１９ないし２３の何れか一項に記載の三次元モデル分割装置。
【０１３３】
（付記２５）前記モデル分割サブ部は、
すべてのサブグラフが選定される当該候補分割面を含むように、当該選定される当該候補分割面により輪郭図を一つ或は少なくとも二つの互いに重複しないサブグラフに分割し、
前記分割されたサブグラフにおける穴と判定されたサブグラフと、当該サブグラフと一番近い実体になるサブグラフとを結合させて新しい実体を取得し、
前記取得した実体それぞれに対してどの実体を分割の結果とするのかを判定するように配置されること
を特徴とする付記２４に記載の三次元モデル分割装置。
【０１３４】
（付記２６）前記モデル分割サブ部は、
前記サブグラフそれぞれの輪郭線の情報に基づいて、当該サブグラフが選定される候補分割面での対応する閉鎖領域を取得し、
取得した当該サブグラフの選定される候補分割面での各閉鎖領域間の関係、及び当該サブグラフと選定される候補分割面の関係を利用して、穴であるかどうかを判定し、
前記穴と判定された前記サブグラフに対して新しい実体を取得すること
を特徴とする付記２５に記載の三次元モデル分割装置。
【０１３５】
（付記２７）前記モデル分割サブ部は、
以下の処理を通してサブグラフが穴であるかどうかを判定するように配置され、
一番外側に位置している閉鎖領域が対応するサブグラフを実体と判定し、
一番外側に位置している閉鎖領域が対応するサブグラフを除くその他のサブグラフと前記その他のサブグラフと一番近いサブグラフとの相互関係に基づいて、以下の原則に応じてその他のサブグラフが穴であるかどうかをそれぞれ判定し、
前記原則は、
前記サブグラフと当該サブグラフと一番近いサブグラフがいずれも選定される候補分割面の同じ側に位置している場合に、当該サブグラフを穴と判定し、
前記サブグラフと当該サブグラフと一番近いサブグラフが選定される候補分割面の完全に反対の側に位置している場合に、当該サブグラフを実体と判定し、
選定される候補分割面を基準として、当該サブグラフに属し且つ当該選定される候補分割面にある頂点から出発してその他の有界平面に接続した方向性がある線分及び当該選定される候補分割面の法線ベクトルが当該選定される候補分割面の両側にある場合に、当該サブグラフを穴と判定し、
選定される候補分割面を基準として、当該サブグラフに属し且つ当該選定される候補分割面にある頂点から出発してその他の有界平面に接続した方向性がある線分及び当該選定される候補分割面の法線ベクトルが当該選定される候補分割面の両側にない場合に、当該サブグラフを実体と判定し、
その中、あるサブグラフについて、当該サブグラフと一番近いサブグラフは一つの実体であり、同時に当該一番近いサブグラフの対応する閉鎖領域は当該サブグラフの相応する閉鎖領域を含み、かつ当該サブグラフの相応するすべての閉鎖領域の中では一番小さい領域を含むこと
を特徴とする付記２６に記載の三次元モデル分割装置。
【０１３６】
（付記２８）前記モデル分割サブ部は、
所定条件を満たす部分だけが三次元モデルから分割されるように、予め設定されたパラメーターにより分割結果に対してコントロールを実行するように配置されること
を特徴とする付記２５に記載の三次元モデル分割装置。
【０１３７】
（付記２９）前記予め設定されたパラメーターは、
前記サブグラフと当該サブグラフと一番近いサブグラフの選定される候補分割面での相応する領域面積の比であり、
前記領域面積の比が予め設定された閾値より小さい場合に、前記サブグラフは分割して出され、
前記領域面積の比が予め設定された前記閾値より大きい場合に、前記サブグラフと当該サブグラフに一番近いサブグラフとは新しいサブグラフに組み合わせられ、独立した部分として分割して出されないこと
を特徴とする付記２８に記載の三次元モデル分割装置。
【０１３８】
（付記３０）前記終了条件判定サブ部は、
前記サブグラフが以下の条件のうち任意の一つを満たすときに、当該サブグラフは引き続き分割を行う必要がないと判定するように配置され、
前記条件は、
前記サブグラフの頂点の数が所定の第一閾値より小さい、
前記サブグラフの含む有界平面の数が所定の第二閾値より小さい、
前記サブグラフが含むすべての有界平面の中に候補分割面が存在しない、
前記サブグラフの中に当該サブグラフと対応する輪郭図を少なくとも二つのサブグラフに分割することができる候補分割面が存在しない、
ことであること
を特徴とする付記２４に記載の三次元モデル分割装置。
【０１３９】
（付記３１）前記第一閾値は８で、前記第二閾値は６であることを特徴とする付記３０に記載の三次元モデル分割装置。
【０１４０】
（付記３２）付記１９ないし３１の何れか一項に記載の前記三次元モデル分割装置が含まれることを特徴とする画像処理システム。
【０１４１】
（付記３３）前記画像処理システムは、
目的検出システム、部分マッチングシステム、モデル検索システムであること
を特徴とする付記３２に記載の画像処理システム。
【０１４２】
（付記３４）機器によって読み取り可能な指令コードが格納されたプログラム製品であり、
前記指令コードが機器によって読み取られるときに、付記１ないし１８の何れか一項に記載の方法を実行させることを特徴とするプログラム製品。
【符号の説明】
【０１４３】
１０００ 三次元モデル分割装置
１１００ 予分割部
１２００ 有界平面生成部
１３００ 輪郭図抽出図
１４００ 輪郭図分割部
１５００ モデル再構成部
【特許請求の範囲】
【請求項１】
三次元モデル分割装置が、
入力された三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルに含まれるすべての三角形を処理し、当該三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する有界平面生成ステップと、
前記生成した有界平面を通して前記三次元モデルの輪郭図を抽出する輪郭図抽出ステップと、
前記生成した有界平面の情報及び前記三次元モデルの頂点隣接グラフの情報に基づいて、前記抽出した輪郭図を所定条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する輪郭図分割ステップとを含み、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルの頂点をノードとして、一つ或は複数の三角形に共有される二つの頂点の間ごとに一辺を追加して前記頂点隣接グラフの構築をすること
を特徴とする三次元モデル分割方法。
【請求項２】
三次元モデル分割装置が、
前記有界平面生成ステップの前に、入力された三次元モデルの三角形ポリゴンデータに含む三角形データと頂点データに基づいて、当該入力された三次元モデルを一つのサブモデル或は少なくとも二つの互いに分離するサブモデルに予分割する予分割ステップを更に含み、
前記サブモデルのそれぞれを所定の条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割するように、当該サブモデルそれぞれに対してそれぞれ前記有界平面生成ステップ、前記輪郭図抽出ステップ及び前記輪郭図分割ステップを実行すること
を特徴とする請求項１に記載の三次元モデル分割方法。
【請求項３】
前記予分割ステップは、
前記三次元モデルの三角形ポリゴンデータに基づいて頂点隣接グラフを構築し、
前記頂点隣接グラフが繋がっているかどうかを判定し、当該頂点隣接グラフにおける何れか１対の頂点の間に接続パスが存在すれば、当該頂点隣接グラフは繋がっていると判定し、当該頂点隣接グラフにおける何れか１対の頂点の間に接続パスが存在しなければ、繋がっていないと判定し、
前記頂点隣接グラフが繋がっていないと判定すれば、当該頂点隣接グラフに互いに繋がらないサブグラフに対応して前記三次元モデルを少なくとも二つの互いに分離するサブモデルに分割すること
を特徴とする請求項２に記載の三次元モデル分割方法。
【請求項４】
前記予分割ステップは、
前記三次元モデルの三角形ポリゴンデータに基づいて三角形隣接グラフを構築することと、
前記三角形隣接グラフが繋がっているかどうかを判定し、ここで、当該三角形隣接グラフにおける何れか１対の三角形の間に接続パスが存在すれば、当該三角形隣接グラフは繋がっていると判定し、当該三角形隣接グラフにおける何れか１対の三角形の間に接続パスが存在しなければ繋がっていないと判定することと、
前記三角形隣接グラフが繋がっていないと判定すれば、当該三角形隣接グラフに互いに繋がらないサブグラフに対応して前記三次元モデルを少なくとも二つの互いに分離するサブモデルに分割することを含み、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルにおける三角形をノードとして、共通点を有する二つの三角形の間ごとに辺を追加して前記三角形隣接グラフを構築すること
を特徴とする請求項２に記載の三次元モデル分割方法。
【請求項５】
三次元モデル分割装置が、
前記輪郭図分割ステップの後に、前記三次元モデルを構成する、三角形ポリゴンで表現される一連の立体コンポーネントを再構成するように、前記分割された一つのサブグラフ或は少なくとも互いに重複しない二つのサブグラフ及び当該三次元モデルの三角形ポリゴンデータに基づいて三角化の処理を実行するモデル再構成ステップを更に含むこと
を特徴とする請求項１ないし４の何れか一項に記載の三次元モデル分割方法。
【請求項６】
前記有界平面生成ステップは、
前記三次元モデルに含まれるすべての三角形それぞれを一つのサブ平面として、すべてのサブ平面を合成できなくなるまで、合成条件を満たすサブ平面を一つの新しいサブ平面に合成して広義の平面を生成し、
前記三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成するように、前記広義の平面のそれぞれに対して以下の処理を実行することを含み、
前記広義の平面にある三角形に対して三角形隣接グラフを作成し、
前記三角形隣接グラフで前記広義の平面の三角形が複数の分離するサブ平面に分けることができ、且つ当該サブ平面のそれぞれが複数の互いに接続する三角形を含む場合に、当該広義の平面を前記複数の分離するサブ平面に分け、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルにおける三角形をノードとして、共通点を有する二つの三角形の間に一辺を追加して前記三角形隣接グラフを構築し、
前記広義の平面を分けて得る前記複数の分離するサブ平面における複数のサブ平面を同時に他の同一の平面と繋がっている場合に、これらのサブ平面を一つの組み合わせる有界平面として組み合わせ、
前記組み合わせた有界平面及び前記広義の平面を分けて得る前記複数の分離するサブ平面における組み合わせる必要のない有界平面によって前記三次元モデルの分割に適用する前記有界平面を共同で構成し、
前記複数のサブ平面がそれぞれ前記他の同一の平面との間に少なくとも一つの共通点が存在する場合に、当該複数のサブ平面は同時に当該他の同一の平面と互いに繋がると判定し、
前記頂点隣接グラフにおいて、あるサブ平面に繋がる頂点が当該サブ平面の同じ側に位置する場合に、当該サブ平面は前記組み合わせる必要のない有界平面における独立する有界平面と判定すること
を特徴とする請求項１ないし５の何れか一項に記載の三次元モデル分割方法。
【請求項７】
前記有界平面生成ステップにおいて、サブ平面を合成できる条件は、
前記サブ平面の法線方向が同じ又は反対であることと、
前記サブ平面の頂点が同一の平面に位置することを含み、
前記サブ平面と関連する三角形の法線方向を当該サブ平面の法線方向とすること
を特徴とする請求項６に記載の三次元モデル分割方法。
【請求項８】
前記輪郭図抽出ステップは、
前記三次元モデルの頂点を輪郭図の頂点とし、各頂点の間には接続が存在せず、
前記有界平面生成ステップで生成したそれぞれの有界平面に対して、当該有界平面生成ステップで生成した有界平面から当該有界平面と繋がる有界平面を探し、
前記有界平面と当該有界平面と繋がっている有界平面の境界線に位置する頂点を取得し、複数の線分を取得するように各頂点を互いに繋ぎ、
前記三次元モデルの輪郭図を得るように、前記取得した複数の線分から互いに重複しない、有界平面の内部の辺と異なる線分を輪郭線として選択し、各輪郭線は少なくとも二つの異なる有界平面に接続し、且つその一辺が当該輪郭線を含むようにそれぞれの有界平面に一つの三角形が存在し、内部の辺は一つの有界平面内だけに位置し、或は同じ有界平面上の複数の三角形に共有される方式で前記三次元モデルの輪郭図を抽出すること
を特徴とする請求項１ないし７の何れか一項に記載の三次元モデル分割方法。
【請求項９】
入力された三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルに含まれるすべての三角形を処理し、当該三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する有界平面生成部と、
前記生成した有界平面を通して前記三次元モデルの輪郭図を抽出する輪郭図抽出部と、
前記生成した有界平面の情報及び前記三次元モデルの頂点隣接グラフの情報に基づいて、前記抽出した輪郭図を所定条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する輪郭図分割部とを含み、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルの頂点をノードとして、一つ或は複数の三角形に共有される二つの頂点の間ごとに一辺を追加して前記頂点隣接グラフを構築すること
を特徴とする三次元モデル分割装置。
【請求項１０】
請求項９に記載の前記三次元モデル分割装置が含まれることを特徴とする画像処理システム。
【請求項１】
三次元モデル分割装置が、
入力された三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルに含まれるすべての三角形を処理し、当該三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する有界平面生成ステップと、
前記生成した有界平面を通して前記三次元モデルの輪郭図を抽出する輪郭図抽出ステップと、
前記生成した有界平面の情報及び前記三次元モデルの頂点隣接グラフの情報に基づいて、前記抽出した輪郭図を所定条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する輪郭図分割ステップとを含み、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルの頂点をノードとして、一つ或は複数の三角形に共有される二つの頂点の間ごとに一辺を追加して前記頂点隣接グラフの構築をすること
を特徴とする三次元モデル分割方法。
【請求項２】
三次元モデル分割装置が、
前記有界平面生成ステップの前に、入力された三次元モデルの三角形ポリゴンデータに含む三角形データと頂点データに基づいて、当該入力された三次元モデルを一つのサブモデル或は少なくとも二つの互いに分離するサブモデルに予分割する予分割ステップを更に含み、
前記サブモデルのそれぞれを所定の条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割するように、当該サブモデルそれぞれに対してそれぞれ前記有界平面生成ステップ、前記輪郭図抽出ステップ及び前記輪郭図分割ステップを実行すること
を特徴とする請求項１に記載の三次元モデル分割方法。
【請求項３】
前記予分割ステップは、
前記三次元モデルの三角形ポリゴンデータに基づいて頂点隣接グラフを構築し、
前記頂点隣接グラフが繋がっているかどうかを判定し、当該頂点隣接グラフにおける何れか１対の頂点の間に接続パスが存在すれば、当該頂点隣接グラフは繋がっていると判定し、当該頂点隣接グラフにおける何れか１対の頂点の間に接続パスが存在しなければ、繋がっていないと判定し、
前記頂点隣接グラフが繋がっていないと判定すれば、当該頂点隣接グラフに互いに繋がらないサブグラフに対応して前記三次元モデルを少なくとも二つの互いに分離するサブモデルに分割すること
を特徴とする請求項２に記載の三次元モデル分割方法。
【請求項４】
前記予分割ステップは、
前記三次元モデルの三角形ポリゴンデータに基づいて三角形隣接グラフを構築することと、
前記三角形隣接グラフが繋がっているかどうかを判定し、ここで、当該三角形隣接グラフにおける何れか１対の三角形の間に接続パスが存在すれば、当該三角形隣接グラフは繋がっていると判定し、当該三角形隣接グラフにおける何れか１対の三角形の間に接続パスが存在しなければ繋がっていないと判定することと、
前記三角形隣接グラフが繋がっていないと判定すれば、当該三角形隣接グラフに互いに繋がらないサブグラフに対応して前記三次元モデルを少なくとも二つの互いに分離するサブモデルに分割することを含み、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルにおける三角形をノードとして、共通点を有する二つの三角形の間ごとに辺を追加して前記三角形隣接グラフを構築すること
を特徴とする請求項２に記載の三次元モデル分割方法。
【請求項５】
三次元モデル分割装置が、
前記輪郭図分割ステップの後に、前記三次元モデルを構成する、三角形ポリゴンで表現される一連の立体コンポーネントを再構成するように、前記分割された一つのサブグラフ或は少なくとも互いに重複しない二つのサブグラフ及び当該三次元モデルの三角形ポリゴンデータに基づいて三角化の処理を実行するモデル再構成ステップを更に含むこと
を特徴とする請求項１ないし４の何れか一項に記載の三次元モデル分割方法。
【請求項６】
前記有界平面生成ステップは、
前記三次元モデルに含まれるすべての三角形それぞれを一つのサブ平面として、すべてのサブ平面を合成できなくなるまで、合成条件を満たすサブ平面を一つの新しいサブ平面に合成して広義の平面を生成し、
前記三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成するように、前記広義の平面のそれぞれに対して以下の処理を実行することを含み、
前記広義の平面にある三角形に対して三角形隣接グラフを作成し、
前記三角形隣接グラフで前記広義の平面の三角形が複数の分離するサブ平面に分けることができ、且つ当該サブ平面のそれぞれが複数の互いに接続する三角形を含む場合に、当該広義の平面を前記複数の分離するサブ平面に分け、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルにおける三角形をノードとして、共通点を有する二つの三角形の間に一辺を追加して前記三角形隣接グラフを構築し、
前記広義の平面を分けて得る前記複数の分離するサブ平面における複数のサブ平面を同時に他の同一の平面と繋がっている場合に、これらのサブ平面を一つの組み合わせる有界平面として組み合わせ、
前記組み合わせた有界平面及び前記広義の平面を分けて得る前記複数の分離するサブ平面における組み合わせる必要のない有界平面によって前記三次元モデルの分割に適用する前記有界平面を共同で構成し、
前記複数のサブ平面がそれぞれ前記他の同一の平面との間に少なくとも一つの共通点が存在する場合に、当該複数のサブ平面は同時に当該他の同一の平面と互いに繋がると判定し、
前記頂点隣接グラフにおいて、あるサブ平面に繋がる頂点が当該サブ平面の同じ側に位置する場合に、当該サブ平面は前記組み合わせる必要のない有界平面における独立する有界平面と判定すること
を特徴とする請求項１ないし５の何れか一項に記載の三次元モデル分割方法。
【請求項７】
前記有界平面生成ステップにおいて、サブ平面を合成できる条件は、
前記サブ平面の法線方向が同じ又は反対であることと、
前記サブ平面の頂点が同一の平面に位置することを含み、
前記サブ平面と関連する三角形の法線方向を当該サブ平面の法線方向とすること
を特徴とする請求項６に記載の三次元モデル分割方法。
【請求項８】
前記輪郭図抽出ステップは、
前記三次元モデルの頂点を輪郭図の頂点とし、各頂点の間には接続が存在せず、
前記有界平面生成ステップで生成したそれぞれの有界平面に対して、当該有界平面生成ステップで生成した有界平面から当該有界平面と繋がる有界平面を探し、
前記有界平面と当該有界平面と繋がっている有界平面の境界線に位置する頂点を取得し、複数の線分を取得するように各頂点を互いに繋ぎ、
前記三次元モデルの輪郭図を得るように、前記取得した複数の線分から互いに重複しない、有界平面の内部の辺と異なる線分を輪郭線として選択し、各輪郭線は少なくとも二つの異なる有界平面に接続し、且つその一辺が当該輪郭線を含むようにそれぞれの有界平面に一つの三角形が存在し、内部の辺は一つの有界平面内だけに位置し、或は同じ有界平面上の複数の三角形に共有される方式で前記三次元モデルの輪郭図を抽出すること
を特徴とする請求項１ないし７の何れか一項に記載の三次元モデル分割方法。
【請求項９】
入力された三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルに含まれるすべての三角形を処理し、当該三次元モデルを分割するのに適用する少なくとも一つの有界平面を生成する有界平面生成部と、
前記生成した有界平面を通して前記三次元モデルの輪郭図を抽出する輪郭図抽出部と、
前記生成した有界平面の情報及び前記三次元モデルの頂点隣接グラフの情報に基づいて、前記抽出した輪郭図を所定条件を満たす一つのサブグラフ或は少なくとも二つの互いに重複しないサブグラフに分割する輪郭図分割部とを含み、
前記三次元モデルの三角形ポリゴンデータに基づいて、当該三次元モデルの頂点をノードとして、一つ或は複数の三角形に共有される二つの頂点の間ごとに一辺を追加して前記頂点隣接グラフを構築すること
を特徴とする三次元モデル分割装置。
【請求項１０】
請求項９に記載の前記三次元モデル分割装置が含まれることを特徴とする画像処理システム。
【図１】
【図４】
【図５】
【図６】
【図７Ｂ】
【図７Ｃ】
【図７Ｄ】
【図８Ｂ】
【図８Ｃ】
【図９Ｂ】
【図９Ｃ】
【図１０Ｂ】
【図１１Ａ】
【図１１Ｂ】
【図１３】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図３Ａ】
【図３Ｂ】
【図７Ａ】
【図８Ａ】
【図９Ａ】
【図１０Ａ】
【図１２Ａ】
【図１２Ｂ】
【図１２Ｃ】
【図４】
【図５】
【図６】
【図７Ｂ】
【図７Ｃ】
【図７Ｄ】
【図８Ｂ】
【図８Ｃ】
【図９Ｂ】
【図９Ｃ】
【図１０Ｂ】
【図１１Ａ】
【図１１Ｂ】
【図１３】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図３Ａ】
【図３Ｂ】
【図７Ａ】
【図８Ａ】
【図９Ａ】
【図１０Ａ】
【図１２Ａ】
【図１２Ｂ】
【図１２Ｃ】
【公開番号】特開２０１１−１８３２８（Ｐ２０１１−１８３２８Ａ）
【公開日】平成２３年１月２７日（２０１１．１．２７）
【国際特許分類】
【出願番号】特願２０１０−１５３１４７（Ｐ２０１０−１５３１４７）
【出願日】平成２２年７月５日（２０１０．７．５）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２３年１月２７日（２０１１．１．２７）
【国際特許分類】
【出願日】平成２２年７月５日（２０１０．７．５）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]