(57)【要約】【課題】ボクセルデータを実効的に少データ化すること。【解決手段】３次元データ管理装置１０は、上位ノードに対する下位ノードのモデル状態の組合せを組合せパターンとして記憶する組合せパターン記憶テーブル１２ａと、８分木ボクセルデータの階層ノードから、実在する組合せパターンを組合せパターン記憶テーブル１２ａに抽出する組合せパターン抽出部１３ｂと、組合せパターン記憶テーブル１２ａによって記憶された組合せパターンに基づいて、ボクセルデータをパターンデータを含むボクセルデータに変換するデータ変換処理部１３ｃとを備える。【選択図】        図１
2006277562.tif 000002
【特許請求の範囲】
【請求項１】
３次元データにボクセル分割処理がおこなわれたボクセルデータを階層ノードに割り当てて管理する３次元データ管理装置であって、
上位ノードに対する下位ノードのモデル状態の組合せを組合せパターンとして記憶する組合せパターン記憶手段と、
前記組合せパターン記憶手段によって記憶された組合せパターンに基づいて、前記ボクセルデータをパターンデータを含むボクセルデータに変換するデータ変換処理手段と、
を備えたことを特徴とする３次元データ管理装置。
【請求項２】
前記組合せパターン記憶手段は、前記組合せパターンとして、前記上位ノードに対する下位ノードのモデル状態の全組合せを所定深度の階層について記憶することを特徴とする請求項１に記載の３次元データ管理装置。
【請求項３】
前記階層ノードの中から、実在する組合せパターンを前記組合せパターン記憶手段に抽出する組合せパターン抽出手段をさらに備えたことを特徴とする請求項１に記載の３次元データ管理装置。
【請求項４】
前記組合せパターン抽出手段は、前記組合せパターンを回転および／または反転させた場合に、他の組合せパターンと同一の組合せパターンになるならば、前記回転および／または前記反転の変換属性をさらに前記組合せパターン記憶手段に抽出することを特徴とする請求項３に記載の３次元データ管理装置。
【請求項５】
３次元データにボクセル分割処理がおこなわれたボクセルデータに対して所望のデータ処理をおこなう３次元データ処理装置であって、
前記ボクセルデータに実在する上位ノードと下位ノードのモデル状態の組合せを組合せパターンとして組合せパターン記憶手段に抽出する組合せパターン抽出手段と、
前記組合せパターン記憶手段によって記憶された組合せパターンに対して所望のデータ処理をおこなうデータ処理手段と、
前記データ処理手段による組合せパターンのデータ処理結果が反映されたボクセルデータを生成するデータ生成手段と、
を備えたことを特徴とする３次元データ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元データにボクセル分割処理がおこなわれたボクセルデータを階層ノードに割り当てて管理する３次元データ管理装置、並びに３次元データにボクセル分割処理がおこなわれたボクセルデータに対して所望のデータ処理をおこなう３次元データ処理装置に関する。
【背景技術】
【０００２】
従来より、３次元ＣＡＤなどで作成された３次元形状のポリゴンモデル、解析用シミュレータによって出力される有限要素データ、ＣＴスキャンなどで測定される３次元ボリュームデータなどの３次元モデルをボクセル形式で管理する技術が知られている。
【０００３】
これらの３次元モデルをボクセル形式で表現するためには、一般的に、大量のメモリ容量が必要となる。例えば、ＣＴスキャンのボクセルデータの場合には、５１２×５１２×５１２のサイズでボクセル数が約１００Ｍ個となり、さらに、各ボクセルでは、物理量や座標、隣接関係などのデータが保持されるので、全体のメモリ使用量は、すぐに１ＧＢを超えることとなる。このため、一般的に普及しているＰＣ（パーソナルコンピュータ）などの情報処理装置では、あまり大きなサイズのボクセルデータを扱うことができない。
【０００４】
ところが、近年では、このような現状に反して、３次元モデルの適用範囲が製品の一部分から製品全体、さらに大規模な構造物へと拡大していることから、ボクセル数を効率良く削減する技術が求められている。
【０００５】
これらの要求を背景にして、３次元データにボクセル分割処理がおこなわれたボクセルデータを階層ノードに割り当てて管理する３次元データ管理装置が開発されている（例えば、特許文献１参照。）。
【０００６】
これを具体的に説明すると、この３次元データ管理装置は、全体空間をルートノードとして、このルートノードを８分木の階層ノードに分割し、分割領域の中に３次元モデルを含んでいれば、さらに８分割するボクセル分割処理をおこなう。なお、このボクセル分割処理は、分割領域内に３次元モデルが存在しないか、分割領域内に３次元モデルの中の平面部分だけを含むか、或いは所定深度の階層まで分割されるまで再帰的におこなわれる。
【０００７】
かかる３次元データ管理装置によれば、３次元モデルの曲率の大きい領域ほど細かいボクセルに分割し、モデル形状の変化の少ない領域を粗いボクセルとすることで、ボクセル数を削減することができる。
【０００８】
【特許文献１】特開２０００−１８２０８１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、上記した従来技術（特許文献１）では、一定のボクセル数を削減することはできるが、ボクセルデータを実効的に少データ化するには自ずから限界があるという問題点があった。特に、３次元モデルが大規模モデルである場合には、分割領域の中に３次元モデルも多く含まれ、ボクセルデータが膨大なデータサイズになってしまうこととなる。
【００１０】
また、上記した従来技術（特許文献１）で管理されるボクセルデータは、膨大なデータサイズであることから、このようなボクセルデータにデータ処理（例えば、描画処理や形状拡大処理、エッジ抽出処理など）をおこなった場合には、データ処理が著しく遅延するという問題点があった。
【００１１】
そこで、本発明は、上述した従来技術による課題（問題点）を解消するためになされたものであり、ボクセルデータを実効的に少データ化することができる３次元データ管理装置を提供することを目的とする。
【００１２】
また、本発明は、ボクセルデータに対するデータ処理を高速化することができる３次元データ処理装置を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上述した課題を解決し、目的を達成するために、本発明に係る３次元データ管理装置は、３次元データにボクセル分割処理がおこなわれたボクセルデータを階層ノードに割り当てて管理する３次元データ管理装置であって、上位ノードに対する下位ノードのモデル状態の組合せを組合せパターンとして記憶する組合せパターン記憶手段と、前記組合せパターン記憶手段によって記憶された組合せパターンに基づいて、前記ボクセルデータをパターンデータを含むボクセルデータに変換するデータ変換処理手段と、を備えたことを特徴とする。
【００１４】
また、本発明に係る３次元データ管理装置は、前記組合せパターン記憶手段は、前記組合せパターンとして、前記上位ノードに対する下位ノードのモデル状態の全組合せを所定深度の階層について記憶することを特徴とする。
【００１５】
また、本発明に係る３次元データ管理装置は、前記階層ノードの中から、実在する組合せパターンを前記組合せパターン記憶手段に抽出する組合せパターン抽出手段をさらに備えたことを特徴とする。
【００１６】
また、本発明に係る３次元データ管理装置は、前記組合せパターン抽出手段は、前記組合せパターンを回転および／または反転させた場合に、他の組合せパターンと同一の組合せパターンになるならば、前記回転および／または前記反転の変換属性をさらに前記組合せパターン記憶手段に抽出することを特徴とする。
【００１７】
また、本発明に係る３次元データ処理装置は、３次元データにボクセル分割処理がおこなわれたボクセルデータに対して所望のデータ処理をおこなう３次元データ処理装置であって、前記ボクセルデータに実在する上位ノードと下位ノードのモデル状態の組合せを組合せパターンとして組合せパターン記憶手段に抽出する組合せパターン抽出手段と、前記組合せパターン記憶手段によって記憶された組合せパターンに対して所望のデータ処理をおこなうデータ処理手段と、前記データ処理手段による組合せパターンのデータ処理結果が反映されたボクセルデータを生成するデータ生成手段と、を備えたことを特徴とする。
【発明の効果】
【００１８】
本発明によれば、上位ノードに対する下位ノードのモデル状態の組合せを組合せパターンとして記憶し、記憶された組合せパターンに基づいて、ボクセルデータをパターンデータを含むボクセルデータに変換することとしたので、同一の組合せパターンのノード間でノードデータを共有することができ、ボクセルデータを実効的に少データ化することが可能になる。
【００１９】
また、本発明によれば、組合せパターンとして、上位ノードに対する下位ノードのモデル状態の全組合せを所定深度の階層について記憶することとしたので、特別な前処理をおこなうことなく、同一の組合せパターンを有するボクセル群をパターンデータに変換することが可能になる。
【００２０】
また、本発明によれば、階層ノードの中から、実在する組合せパターンを抽出することとしたので、同一の組合せパターンを有するボクセル群を洩らすことなくパターンデータに変換することが可能になる。
【００２１】
また、本発明によれば、組合せパターンを回転および／または反転させた場合に、他の組合せパターンと同一の組合せパターンになるならば、回転および／または反転の変換属性をさらに抽出することとしたので、同一の組合せパターンを有するボクセル数を増加させつつ、組合せパターン数を削減することができ、ボクセルデータをより実効的に少データ化することが可能になる。さらに、これに関連して、組合せパターンを削減することにより、ボクセルデータに対するデータ処理をより高速化することが可能になる。
【００２２】
また、本発明によれば、ボクセルデータに実在する上位ノードと下位ノードのモデル状態の組合せを組合せパターンとして抽出し、組合せパターンに対して所望のデータ処理をおこない、組合せパターンのデータ処理結果が反映されたボクセルデータを生成することとしたので、重複する処理を回避することができ、ボクセルデータに対するデータ処理を高速化することが可能になる。
【発明を実施するための最良の形態】
【００２３】
以下に添付図面を参照して、本発明に係る３次元データ管理装置および３次元データ処理装置の好適な実施例を詳細に説明する。なお、以下では、本発明に係る３次元データ管理装置の概要および特徴を説明した後に、本実施例１に係る３次元データ管理装置を説明し、最後に、他の実施例として種々の変形例（実施例２）を説明することとする。
【００２４】
（概要および特徴）
まず最初に、本発明に係る３次元データ管理装置の概要および特徴を説明する。図１は、本実施例１に係る３次元データ管理装置の構成を示すブロック図である。この３次元データ管理装置１０は、３次元ＣＡＤなどで作成された３次元形状のポリゴンモデル、解析用シミュレータによって出力される有限要素データ、ＣＴスキャンなどで測定される３次元ボリュームデータなどの３次元データに「ボクセル分割処理」がおこなわれたボクセルデータを階層ノードに割り当てて管理するものである。
【００２５】
具体的に説明すると、この３次元データ管理装置は、全体空間をルートノードとして、このルートノードを８分木の階層ノードに分割し（図２参照）、分割領域の中に３次元モデルを含んでいれば、さらに８分割するボクセル分割処理をおこなう。なお、この「ボクセル分割処理」は、分割領域内に３次元モデルが存在しないか、３次元モデルの中の平面部分だけを含むか、或いは所定深度の階層まで分割するまで再帰的におこなわれる（図３参照）。
【００２６】
また、この３次元データ管理装置１０は、図３に示すように、分割領域に対応する各ノードにモデル状態（ホワイトノード、ブラックノードまたはグレイノード）をラベル付けする。なお、このモデル状態のうち「ホワイトノード」は、分割領域内に３次元モデルが存在しない状態を指し、「ブラックノード」は、分割領域内に３次元モデルの中の平面部分だけを含む状態を指し、「グレイノード」は、分割領域内に３次元モデルを含む状態を指す。
【００２７】
ここで、本発明に係る３次元データ管理装置１０は、上位ノードに対する下位ノードのモデル状態の組合せを組合せパターンとして記憶し、この組合せパターンに基づいて、ボクセルデータをパターンデータを含むボクセルデータに変換する「データ変換処理」に主たる特徴があり、かかる「データ変換処理」によって、ボクセルデータを実効的に少データ化することができるようにしている。
【００２８】
この主たる特徴を具体的に説明すると、上位ノードに対する下位ノードのモデル状態の組合せは、親ノードと子ノードの１階層の組合せパターンだけでも、ホワイトノード、ブラックノードおよびグレイノードの３つの状態が存在するので、８個のノードとモデル状態の組合せ、すなわち３の８乗パターンが存在するが、機械製品などの実際のモデルでは、平面、円筒面、直角の角などのある特定の形状が多く用いられていることから、数１０パターンに限られる。
【００２９】
また、２階層以上の組合せパターンであっても、同一の組合せパターンとなるボクセルが多数存在することから、同一の組合せパターンを有するボクセル群をパターンデータに変換することができれば、ボクセルデータを大幅に削減することができることとなる。
【００３０】
このため、３次元データ管理装置１０では、同一の組合せパターンを有するボクセル群をパターンデータに変換するために、親ノードに対する子ノードのモデル状態の組合せを１階層の組合せパターンとして記憶することとする。例えば、親ノードと子ノードの組合せパターンとして、８個のノードとモデル状態の組合せ、すなわち「３8」パターンの組合せパターンを全通り記憶したり、８分木ボクセルデータに実在する組合せパターンを記憶したりする。
【００３１】
さらに、この３次元データ管理装置１０は、Grandparentノードに対する子ノードと孫ノードのモデル状態の組合せを２階層の組合せパターンとして記憶している。例えば、Grandparentノードの８個の子ノードそれぞれに、ホワイトノード、ブラックノードおよびＮ通りのグレイノードが存在することとなるので、２階層の組合せパターンとして、（Ｎ＋２）8の組合せパターンを全通り記憶したり、８分木ボクセルデータに実在する組合せパターンを記憶したりする。
【００３２】
そして、３次元データ管理装置１０は、かかる組合せパターンに基づいて、「ボクセル分割処理」がおこなわれた８分木ボクセルデータをパターンデータを含むボクセルデータに変換する。具体的には、かかる１階層または２階層の組合せパターンと同一の組合せパターンとなるノード（Grandparentまたは親ノード）うち、いずれか一つのノードを当該組合せパターンのパターン化ノードとし、他のノードにパターン化ノードへのポインタのみを保持させることで８分木ボクセルデータをパターンデータを含むパターン化８分木ボクセルデータに変換する。
【００３３】
このように、「ボクセル分割処理」がおこなわれた８分木ボクセルデータをパターンデータを含むパターン化８分木ボクセルデータに変換することで、同一の組合せパターンのノード間でノードデータを共有することができるようにしている。
【００３４】
したがって、本発明に係る３次元データ管理装置１０によれば、上位ノードに対する下位ノードのモデル状態の組合せを組合せパターンとして記憶し、この組合せパターンに基づいて、ボクセルデータをパターンデータを含むボクセルデータに変換することとしたので、同一の組合せパターンのノード間でノードデータを共有することができ、上記した主たる特徴のように、ボクセルデータを実効的に少データ化することが可能になる。
【実施例１】
【００３５】
次に、本実施例１に係る３次元データ管理装置を説明する。なお、ここでは、本実施例１に係る３次元データ管理装置の構成を説明した後に、この３次元データ管理装置の各種処理の手順を説明することとする。
【００３６】
（３次元データ管理装置の構成）
図１は、本実施例１に係る３次元データ管理装置の構成を示すブロック図である。この３次元データ管理装置１０は、同図に示すように、３次元データに「ボクセル分割処理」がおこなわれたボクセルデータを階層ノードに割り当てて管理するものであり、ボクセルデータ入力部１１と、記憶部１２と、制御部１３とを備える。
【００３７】
このうち、ボクセルデータ入力部１１は、３次元ＣＡＤなどで作成された３次元形状のポリゴンモデル、解析用シミュレータによって出力される有限要素データ、ＣＴスキャンなどで測定される３次元ボリュームデータなどの３次元データをボクセルデータに変換してボクセル分割処理部１３ａに入力する処理部であり、具体的には、かかる３次元データをユーザ指定領域と最小サイズでボクセルデータに変換し、該変換したボクセルデータをボクセル分割処理部１３ａに入力する。
【００３８】
記憶部１２は、制御部１３による各種処理に必要なデータおよびプログラムを格納する格納手段（記憶手段）であり、本発明に密接に関連するものとしては、上位ノードに対する下位ノードのモデル状態の組合せを組合せパターンとして記憶する組合せパターン記憶テーブル１２ａを備える。
【００３９】
この組合せパターン記憶テーブル１２ａは、後述する組合せパターン抽出処理部１３ｂによって８分木ボクセルデータの階層ノードから抽出された組合せパターン（１階層および２階層の組合せパターン）を記憶している。例えば、図７に示すように、１階層の組合せパターン「００００００００」に、１階層のソート番号「１」およびパターン化ノードのアドレス「××××１」を対応付けて記憶し、さらに、図８に示すように、２階層の組合せパターン「ＬＬＬＬＬＬＬ１」に、２階層のソート番号「１」およびパターン化ノードのアドレスを対応付けて記憶している。
【００４０】
制御部１３は、ＯＳ（Operating System）などの制御プログラム、各種の処理手順などを規定したプログラムおよび所要データを格納するための内部メモリを有し、これらによって種々の処理を実行する処理部であり、特に本発明に密接に関連するものとしては、ボクセル分割処理部１３ａと、組合せパターン抽出部１３ｂと、データ変換処理部１３ｃとを備える。
【００４１】
このうち、ボクセル分割処理部１３ａは、ボクセルデータ入力部１１によって入力されたボクセルデータから８分木ボクセルデータを計算する処理部である。具体的には、全体空間をルートノードとして、このルートノードを８分木の階層ノードに分割し（図２参照）、分割領域の中に３次元モデルを含んでいれば、さらに８分割する。なお、この「ボクセル分割処理」は、分割領域内に３次元モデルが存在しないか、分割領域内に３次元モデルの中の平面部分だけを含むか、或いは所定深度の階層まで分割されるまで再帰的におこなわれる（図３参照）。
【００４２】
また、ボクセル分割処理部１３ａは、図３に示すように、分割領域に対応する各ノードにモデル状態（ホワイトノード、ブラックノードまたはグレイノード）をラベル付けする。このモデル状態のうち「ホワイトノード」は、分割領域内に３次元モデルが存在しない状態を指し、「ブラックノード」は、分割領域内に３次元モデルの中の平面部分だけを含む状態を指し、「グレイノード」は、分割領域内に３次元モデルを含む状態を指す。なお、ボクセル分割処理部１３ａは、３次元データから直接８分木ボクセルデータを作成するようにしても良い。
【００４３】
組合せパターン抽出部１３ｂは、ボクセル分割処理部１３ａによって計算された８分木ボクセルデータの階層ノードから、実在する組合せパターンを組合せパターン記憶テーブル１２ａに抽出する処理部である。
【００４４】
ここで、組合せパターンの抽出を具体的に説明する。組合せパターン抽出部１３ｂは、ボクセル分割処理部１３ａによって計算された８分木ボクセルデータが入力された場合に、全てのノードから親ノードを抽出し、該抽出した各親ノードに対する子ノードのモデル状態から組合せパターンのパターン番号を計算する。
【００４５】
例えば、８個の子ノードの領域位置を図４に示す位置関係とした場合に、ホワイトノードを「０」、ブラックノードを「１」、グレイノードを「２」で表現することとしたならば、親ノードのパターン番号は、図５に示すように、「００００００００」、「０００００００１」、・・・、「２２２２２２２２」と計算されることとなる。
【００４６】
そして、組合せパターン抽出部１３ｂは、このようにして計算した親ノードのパターン番号をソートし、このソート順に「ソート番号」を採番する。すなわち、図６に示すように、不連続なパターン番号をシリアルな「ソート番号」に変更する。
【００４７】
続いて、組合せパターン抽出部１３ｂは、全てのノードからGrandparentノードを抽出し、該抽出した各Grandparentノードに対する子ノードと孫ノードのモデル状態から組合せパターンのパターン番号を計算し、Grandparentノードのパターン番号をソートする。
【００４８】
例えば、Grandparentノードに対する子ノードと孫ノードのモデル状態の組合せを表現するために、子ノードがグレイノードである場合には、１階層のソート番号で「子ノード」を表現し、子ノードがホワイトノードである場合には、Ｎより大きいソート番号；Ｌ（＝Ｎ＋１）で「子ノード」を表現し、また、子ノードがブラックノードである場合には、Ｍより大きいソート番号；Ｍ（＝Ｎ＋２）で「子ノード」を表現することとしたならば、Grandparentノードのパターン番号は、図６に示すように、「ＬＬＬＬＬＬＬＬ」、・・・、「Ｌ６９Ｍ６Ｌ８１」、・・・、「ＮＮＮＮＮＮＮＮ」と計算されることとなる。
【００４９】
そして、組合せパターン抽出部１３ｂは、親ノードおよびGrandparentノードごとにソート番号が同一番号である上位ノード（親ノードまたはGrandparentノード）を抽出し、該抽出した上位ノードのうち、１つの上位ノードをパターン化ノードとして組合せパターン記憶テーブル１２ａに登録する（図７および図８参照）。
【００５０】
このように、８分木ボクセルデータの階層ノードの中から、実在する組合せパターンを組合せパターン記憶テーブル１２ａに抽出することとしたので、同一の組合せパターンを有するボクセル群を洩らすことなくパターンデータに変換することが可能になる。
【００５１】
データ変換処理部１３ｃは、組合せパターン記憶テーブル１２ａによって記憶された組合せパターンに基づいて、８分木ボクセルデータをパターンデータを含むパターン化８分木ボクセルデータに変換する処理部である。具体的には、かかる１階層または２階層の組合せパターンと同一の組合せパターンとなるノード（Grandparentまたは親ノード）うち、いずれか一つのノードを当該組合せパターンのパターン化ノードとし、他のノードにパターン化ノードへのポインタのみを保持させることで８分木ボクセルデータをパターンデータを含むパターン化８分木ボクセルデータに変換する。なお、このパターン化８分木ボクセルデータは、ボクセル内の面データを有するブラックノードと、８個の子ノードデータを有するパターン化ノード（グレイノード）と、パターン化ノードへのポインタを有するグレイノードとから構成される。
【００５２】
（各種処理の手順）
次に、本実施例１に３次元データ管理装置の各種処理の手順を説明する。図９は、データ変換処理の手順を示すフローチャートである。同図に示すように、ボクセルデータ入力部１１によってボクセルデータが入力された場合（ステップＳ９０１肯定）に、ボクセル分割処理部１３ａは、ボクセルデータにボクセル分割処理をおこなって８分木ボクセルデータに変換する（ステップＳ９０２）。
【００５３】
続いて、組合せパターン抽出部１３ｂは、ボクセル分割処理部１３ａによって変換された８分木ボクセルデータの階層ノードから、実在する組合せパターンを組合せパターン記憶テーブル１２ａに抽出する「組合せパターン抽出処理」をおこなう（ステップＳ９０３）。
【００５４】
ここで、図１０を用いて「組合せパターン抽出処理」を具体的に説明する。図１０は、組合せパターン抽出処理の手順を示すフローチャートである。この処理は、ボクセル分割処理部１３ａによって計算された８分木ボクセルデータが入力された場合（ステップＳ９０２終了後）に、開始されることとなる。
【００５５】
同図に示すように、組合せパターン抽出部１３ｂは、全てのノードから親ノードを抽出し（ステップＳ１００１）、該抽出した各親ノードに対する子ノードのモデル状態から組合せパターンのパターン番号を計算する（ステップＳ１００２）。
【００５６】
そして、組合せパターン抽出部１３ｂは、このようにして計算した親ノードのパターン番号をソートし（ステップＳ１００３）、このソート順に「ソート番号」を採番する（ステップＳ１００４）。
【００５７】
続いて、組合せパターン抽出部１３ｂは、全てのノードからGrandparentノードを抽出し（ステップＳ１００５）、該抽出した各Grandparentノードに対する子ノードと孫ノードのモデル状態から組合せパターンのパターン番号を計算し、Grandparentノードのパターン番号をソートする（ステップＳ１００６）。
【００５８】
そして、組合せパターン抽出部１３ｂは、親ノードおよびGrandparentノードごとにソート番号が同一番号である上位ノード（親ノードまたはGrandparentノード）を抽出し（ステップＳ１００７）、該抽出した上位ノードのうち、１つの上位ノードをパターン化ノードとして組合せパターン記憶テーブル１２ａに登録する（ステップＳ１００８）。
【００５９】
このように、８分木ボクセルデータの階層ノードの中から、実在する組合せパターンを組合せパターン記憶テーブル１２ａに抽出することで、同一の組合せパターンを有するボクセル群を洩らすことなくパターンデータに変換することができるようにしている。
【００６０】
図９の説明に戻り、データ変換処理部１３ｃは、組合せパターン記憶テーブル１２ａによって記憶された組合せパターンに基づいて、８分木ボクセルデータをパターンデータを含むパターン化８分木ボクセルデータに変換し（ステップＳ９０４）、該変換したパターン化８分木ボクセルデータを所望の出力先に出力する（ステップＳ９０５）。
【００６１】
上述してきたように、本実施例１に係る３次元データ管理装置１０によれば、上位ノードに対する下位ノードのモデル状態の組合せを組合せパターンとして記憶し、この組合せパターンに基づいて、ボクセルデータをパターンデータを含むボクセルデータに変換するよう構成したので、同一の組合せパターンのノード間でノードデータを共有することができ、ボクセルデータを実効的に少データ化することが可能になる。
【実施例２】
【００６２】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、上記特許請求の範囲に記載した技術的思想の範囲内において種々の異なる実施例にて実施されてもよいものである。
【００６３】
例えば、実施例１では、上位ノードに対する下位ノードのモデル状態の組合せとして、１階層の組合せパターンおよび２階層の組合せパターンに基づいて、データ変換処理をおこなう実施例について説明したが、本発明はこれに限定されるものではなく、任意階層の組合せパターンを単一或いは多段に組合せパターン記憶テーブル１２ａに記憶した場合でも同様に適用することができる。
【００６４】
また、実施例１では、８分木ボクセルデータの階層ノードから、実在する組合せパターンを組合せパターン記憶テーブル１２ａに抽出する実施例について説明したが、本発明はこれに限定されるものではなく、組合せパターンとして、上位ノードに対する下位ノードのモデル状態の全組合せを所定深度の階層について記憶するようにしても良い。すなわち、これによって、特別な前処理をおこなうことなく、同一の組合せパターンを有するボクセル群をパターンデータに変換することが可能になる。
【００６５】
なお、本発明では、ボクセルデータに実在する上位ノードと下位ノードのモデル状態の組合せを組合せパターンとして組合せパターン記憶テーブル１２ａに抽出し、組合せパターン記憶テーブル１２ａによって記憶された組合せパターンに対して所望のデータ処理をおこない、組合せパターンのデータ処理結果が反映されたボクセルデータを生成するようにしても良い。
【００６６】
すなわち、３次元データの描画処理、形状拡大処理、エッジ抽出処理など、局所的な処理をおこなう場合には、パターン化した領域に対しては、それぞれの領域で処理をおこなうのではなく、１つの領域だけ処理をおこない、他の領域はその処理結果を流用することで、重複する処理を回避することができ、ボクセルデータに対するデータ処理を高速化することができる。
【００６７】
例えば、描画処理では、ボクセル内の３角形ポリゴンを構成する必要があるが、そのポリゴン構成を同一パターン領域に対しては、１つの分割領域だけポリゴン形状を計算し、その他の領域ではこのポリゴンを移動変換するだけで使うことができる。なお、変換パターンに対しては、さらに回転または鏡像反転の変換をおこなえば良い。
【００６８】
さらに、本発明では、組合せパターンを回転および／または反転させた場合に、他の組合せパターンと同一の組合せパターンになるならば、回転および／または反転の変換属性をさらに組合せパターン記憶テーブル１２ａに抽出するようにしても良い。
【００６９】
例えば、同一の組合せパターンの抽出では、各親ノードごとに、基本パターン（実在する組合せパターン）に対する変換パターン（基本パターンを回転および／または反転させたパターン）とのマッチングを行い、一致した変換パターンの基本パターンの番号をパターン番号として用いる。なお、同一の組合せパターンの時のノードデータとしては、パターン化ノードへのポインタに加え、さらに変換属性（例えば、Ｚ軸周り９０度回転変換などを番号化したものなど）を保持させる必要がある。
【００７０】
すなわち、これによって、同一の組合せパターンを有するボクセル数を増加させつつ、組合せパターン数を削減することができ、ボクセルデータをより実効的に少データ化することが可能になる。さらに、これに関連して、組合せパターンを削減することにより、ボクセルデータに対するデータ処理をより高速化することが可能になる。
【００７１】
また、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００７２】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【産業上の利用可能性】
【００７３】
以上のように、本発明に係る３次元データ管理装置は、３次元データにボクセル分割処理がおこなわれたボクセルデータを階層ノードに割り当てて管理する３次元データ管理装置に有用であり、特に、ボクセルデータを実効的に少データ化することができる３次元データ管理装置に適している。
【図面の簡単な説明】
【００７４】
【図１】本実施例１に係る３次元データ管理装置の構成を示すブロック図である。
【図２】ボクセル分割処理を説明するための説明図である。
【図３】８分木階層構造の一例を示す図である。
【図４】親ノードと子ノードの関係を示す図である。
【図５】組合せパターンの一例を示す図である。
【図６】組合せパターンの一例を示す図である。
【図７】組合せパターン記憶テーブルに記憶される情報の構成例を示す図である。
【図８】組合せパターン記憶テーブルに記憶される情報の構成例を示す図である。
【図９】データ変換処理の手順を示すフローチャートである。
【図１０】組合せパターン抽出処理の手順を示すフローチャートである。
【符号の説明】
【００７５】
１０    ３次元データ管理装置
１１    ボクセルデータ入力部
１２    記憶部
１２ａ  組合せパターン記憶テーブル
１３    制御部
１３ａ  ボクセル分割処理部
１３ｂ  組合せパターン抽出部
１３ｃ  データ変換処理部
【図１】
2006277562.tif 000003
【図２】
2006277562.tif 000004
【図３】
2006277562.tif 000005
【図４】
2006277562.tif 000006
【図５】
2006277562.tif 000007
【図６】
2006277562.tif 000008
【図７】
2006277562.tif 000009
【図８】
2006277562.tif 000010
【図９】
2006277562.tif 000011
【図１０】
2006277562.tif 000012