(57)【要約】【課題】  出力造形物の品質の劣化を抑えながら、ポリゴンで構成されたポリゴンモデルから、少ない処理負荷で効率的にポリゴンを削減して立体物造形用データを得る立体物造形用データ削減装置を提供する。【解決手段】  共有頂点ＩＤと各頂点を含むポリゴンを対応付けた頂点構成テーブル、共有頂点ＩＤと座標値を対応付けた頂点座標テーブルを作成し、頂点座標テーブル内の頂点と重複先頂点の対応を示す頂点重複テーブルを定義し、削除対象ポリゴンを設定する削除し、削除対象ポリゴンの削除対象頂点を基に頂点座標テーブルを更新し、代表頂点以外の削除対象頂点の重複先を代表頂点に設定し、共有頂点ＩＤが重複するポリゴンを頂点構成テーブルより削除し、頂点構成テーブルの各共有頂点ＩＤを座標値に置換してポリゴンモデルを更新する。【選択図】  図２
2016099841.tif 000002
【特許請求の範囲】
【請求項１】
ポリゴンの集合として表現されたポリゴンモデルのデータを、立体物の造形のために削減する装置であって、
前記ポリゴンモデルを構成する各ポリゴンの各頂点に対して、同一の座標値をもつ異なるポリゴンの頂点を探索し、取得された一連の頂点に対して同一の共有頂点ＩＤを付与することにより、各ポリゴンに含まれる各頂点を、同一座標の頂点を同一値とする共有頂点ＩＤで表現し、各頂点を含むポリゴンと対応付けて記録した頂点構成テーブルと、前記頂点構成テーブルに付与された共有頂点ＩＤと座標値を対応付けて記録した頂点座標テーブルとを作成するポリゴンモデル構造化手段と、
前記頂点座標テーブルに記録されている頂点と同一座標となる重複先の頂点との対応関係を記録する頂点重複テーブルを定義する頂点重複テーブル定義手段と、
前記頂点構成テーブルに記録されているポリゴンに対して所定の間隔で一部のポリゴンを削除対象ポリゴンとして設定する削除対象ポリゴン設定手段と、
前記頂点構成テーブルを参照して前記削除対象ポリゴンに対応する頂点を削除対象頂点として特定し、前記削除対象頂点を基に前記頂点座標テーブルを参照して複数の前記削除対象頂点の平均点を求め、前記削除対象頂点の１つを代表頂点とし、前記代表頂点以外の前記削除対象頂点の情報を頂点座標テーブルから削除するとともに、前記代表頂点の共有頂点ＩＤに、前記平均点の座標値を対応付けて記録する頂点座標テーブル更新手段と、
前記頂点重複テーブルにおいて、前記代表頂点以外の前記削除対象頂点の重複先を前記代表頂点に設定する頂点重複テーブル更新手段と、
前記頂点構成テーブルの各共有頂点ＩＤの値を、前記更新された頂点重複テーブルに設定された重複先に変更し、変更された結果、同一ポリゴンに対応する共有頂点ＩＤが２つ以上重複する場合、当該ポリゴンを前記頂点構成テーブルより削除する頂点構成テーブル更新手段と、
前記頂点構成テーブル更新手段により更新された頂点構成テーブルの各共有頂点ＩＤを前記頂点座標テーブル更新手段により更新された頂点座標テーブルを参照しながら座標値に置換することにより、ポリゴンモデルを更新するポリゴンモデル更新手段と、
を有することを特徴とする立体物造形用データ削減装置。
【請求項２】
前記ポリゴンの集合体は配列構造で定義されており、
前記ポリゴンモデル構造化手段は、
前記ポリゴンモデルを構成する各ポリゴンの各頂点を対象頂点とし、前記配列上で前記対象頂点より後方に位置し、当該対象頂点に最も近接し、当該対象頂点と同一座標となる他のポリゴンの頂点を１つ検出し、他のポリゴンの頂点と前記対象頂点を対応付け、それぞれポリゴンを識別可能な形式で記録した頂点リンクテーブルを作成し、前記ポリゴンモデルを構成する各ポリゴンの各頂点を起点に、前記作成された頂点リンクテーブルを参照し、一連の共有頂点を取得することを特徴とする請求項１に記載の立体物造形用データ削減装置。
【請求項３】
前記頂点座標テーブル更新手段は、
前記削除対象ポリゴンに含まれる３つの削除対象の頂点の共有頂点ＩＤをもとに前記頂点座標テーブルを参照し、前記３つの削除対象の頂点の平均点座標を算出し、前記削除対象の頂点のうちの１つを代表頂点とし、前記頂点座標テーブルに記録されている前記代表頂点の共有頂点ＩＤの座標値を、前記平均点座標に置換することを特徴とする請求項１または請求項２に記載の立体物造形用データ削減装置。
【請求項４】
前記頂点座標テーブル更新手段は、
前記削除対象ポリゴンに含まれる３つの削除対象の頂点より辺の長さが最も短い２頂点を選定し、選定された２つの頂点の共有頂点ＩＤをもとに前記頂点座標テーブルを参照し、前記２つの削除対象の頂点の中点座標を算出し、前記削除対象の頂点のうちの１つを代表頂点とし、前記頂点座標テーブルに記録されている前記代表頂点の共有頂点ＩＤの座標値を、前記中点座標に置換することを特徴とする請求項１または請求項２に記載の立体物造形用データ削減装置。
【請求項５】
前記ポリゴンモデル更新手段により更新されたポリゴンモデルを構成するポリゴン数が所定の目標値より大きい場合、前記削除対象ポリゴン設定手段、前記頂点座標テーブル更新手段、前記頂点重複テーブル更新手段、前記頂点構成テーブル更新手段、前記ポリゴンモデル更新手段に対して繰り返して処理を実行させる制御を行う制御手段と、
を更に備えることを特徴とする請求項１から請求項４のいずれか一項に記載の立体物造形用データ削減装置。
【請求項６】
ポリゴンの集合として表現されたポリゴンモデルのデータを、立体物の造形のために削減する装置であって、
前記ポリゴンモデル更新手段により削減されたポリゴンモデルである削減ポリゴンモデルを構成する各ポリゴンの面積を基に、追加削除するべきポリゴンを追加削除対象ポリゴンとして選定する追加削除対象ポリゴン選定手段と、
前記追加削除対象ポリゴンを構成する辺の長さに基づいて、追加削除するべき辺を追加削除対象辺として選定する追加削除対象辺選定手段と、
前記追加削除対象ポリゴン以外のポリゴンから、前記追加削除対象辺の２頂点のいずれか１頂点を共有するポリゴンである追加削除頂点共有ポリゴンを探索する追加削除頂点共有ポリゴン探索手段と、
前記追加削除対象辺の２頂点の双方を共有する追加削除頂点共有ポリゴンを、前記追加削除対象ポリゴンとともに削除し、前記探索された追加削除対象辺のいずれか１頂点のみを共有する追加削除頂点共有ポリゴンに対して、前記共有する１頂点を前記追加削除対象辺の２頂点の中点の位置に補正するポリゴンモデル追加更新手段と、
を更に備えることを特徴とする請求項１から請求項５のいずれか一項に記載の立体物造形用データ削減装置。
【請求項７】
請求項１から請求項６のいずれか一項に記載の立体物造形用データ削減装置と、
前記立体物造形用データ削減装置から出力されたポリゴンモデルを用いて立体物を造形する立体物造形装置と、
を有することを特徴とする立体物造形システム。
【請求項８】
コンピュータを、請求項１から請求項６のいずれか一項に記載の立体物造形用データ削減装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、立体物を表すデータを基に、樹脂等を加工して立体物を造形する３Ｄプリンタ等の立体物造形装置の利用に際して、立体物造形装置への出力用データを削減するための技術に関する。
【背景技術】
【０００２】
近年、立体物を表すデータをもとに、樹脂や石膏等を加工して造形する３Ｄプリンタが立体物造形装置として普及してきている。３Ｄプリンタの医療応用として、医療診断で撮影されるCT/MRI画像（DICOM形式３次元ボクセルデータ）を基に３Ｄプリンタ出力用モデリングデータを作成し、手術シミュレーション・医学教育・インフォームドコンセント向けの臓器模型を出力したり、体内埋め込み用の人工臓器（血管、骨、関節など）を作成したりする試みが始まっている。
【０００３】
立体物造形用データである３Ｄプリンタ出力用モデリングデータは、ポリゴンの集合体で表現されたポリゴンモデルである。CT/MRI画像から臓器模型の３Ｄプリンタ出力用モデリングデータを作成する方法としては、特許文献１、特許文献２に示されるように、対象とする臓器領域のボクセルを抽出し、Marching Cube法（特許文献３など）により臓器領域の境界面を多面体（三角形の集合）で近似したサーフェースに変換して表面形状を表現したサーフェースデータを得る手法が一般的である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第３６９０５０１号公報
【特許文献２】特開２０１２−２１６１０２号公報
【特許文献３】米国特許第７２０９１３６号公報
【特許文献４】特開平８−１５３２１１号公報
【特許文献５】特許第３３５０４７３号公報
【特許文献６】特許第４４６３５９７号公報
【特許文献７】特許第５０１８７２１号公報
【特許文献８】特開平１１−２３２４８９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記のサーフェース変換手法では５１２の３乗程度のボクセルを基に、３次元的に三角形を生成する方法をとるため、三角形ポリゴンが膨大になり、ＣＧ分野においては、画面描画の際に時間がかかり対話操作の応答性が悪くなるという問題が指摘されている。これは３Ｄプリンタ出力においても問題を起こし、プリンタ出力前処理（ポリゴンから積層造形用のデータに変換する処理）に時間がかかり、場合によりワークメモリーオーバーフローを引き起こして出力不能になる。
【０００６】
これに対してＣＧ分野においては、画面の解像度に合せてポリゴン分割を粗くして曲面を表現したり、可視化に供しないポリゴンを事前に削除したりする方法がとられる。例えば、平板オブジェクトでは、単一面だけで表現し裏面を構成するポリゴンを省略したり、特許文献４のように、視点方向から隠面にあたり可視化に供しないポリゴンを事前に削除したり、特許文献５のように、他のポリゴンによって隠される内側のポリゴンを判定して事前に削除し、描画対象ポリゴンを削減する方法が提案されている。また、特許文献６のように、微細な凹凸表現に対してポリゴンを用いず、テクスチャやバンプマッピングで代用する方法が提案されている。
【０００７】
しかし、３Ｄプリンタ出力においては、画面より細かい解像度が要求され、ポリゴンにより閉空間を構成する必要があるため、平板オブジェクトにおいて、裏面を構成するポリゴンを省略することはできない。また、造形物は種々のアングルから鑑賞されるため基本的に隠面は存在せず、造形物内部にも別の形状を造形可能なため、ＣＧ分野で提案されているオクルージョンカリングという手法は意味をもたない。微細な凹凸に対しても陰影などで視覚的に擬似表現することはできず、ポリゴン形状で表現せざるを得ない。特許文献７のように、建築模型においては極端にポリゴンを削減したデフォルメされた表現が要望される場合もあるが、医療応用ではそれなりにリアリティが要求される。そのため、特許文献８のように、造形物の外観を損なわない程度に、三角形ポリゴン自体を削減する手法をとらざるを得ない。
【０００８】
三角形ポリゴンの削減にあたっては、特許文献８の手法が基本になる。これは、(1)与えられたポリゴンから削減しても全体形状にあまり影響を与えない三角形および稜線を探索する処理と、(2)対象稜線を削減するとともにそれと頂点を共有する隣接三角形を探索し補正を行う処理との２種の探索処理を所望のデータ量に削減されるまで繰り返す。特許文献８の手法では、双方の処理において削除候補とする稜線と頂点を共有する隣接三角形を探索する処理を必要とし、与えられたポリゴン数の２乗に比例して処理負荷が増大するという問題を抱えていた。
【０００９】
処理負荷を削減する方法として、削減対象の入力ポリゴンモデルのデータ量を少なくすれば良いため、入力ポリゴンモデルを分割して処理をすればよい。特許文献１では、ポリゴンに変換前のボクセル画像の段階で分割を行い、分割されたボクセルデータごとにサーフェース変換を行ってポリゴンを削減する手法を提案している。これにより確かに高速化は実現できるが、ボクセル分割された境界部にサーフェースが形成されてしまうため、ポリゴンデータを統合させると、造形物上において分割境界部に対応する不連続な亀裂が発生してしまうという問題がある（ただし、ＣＧ用途においては、レンダリングにより境界部は目立たない。）。
【００１０】
また、見かけ上は単一の閉空間にまとまって見えても、データ的には複数の閉空間に分離されている場合がある。例えば、主たる閉空間に接触した小空間が存在する場合、そのままプリンタ出力すれば支障無いが、特許文献８等によりポリゴン削減を施すと、小空間が削られて主たる閉空間からの距離が長くなり、完全に遊離した状態になることがある。この状態でプリンタ出力すると、プリンタ出力前処理でエラー停止したり、空中に浮遊するよう造形指示された小空間が出力途上で落下し出力トラブルを発生させたりする可能性がある（ただし、ＣＧ用途においては、特に問題を生じない。）。
【００１１】
特に、ポリゴンモデルのデータ量の削減には、大きな処理負荷を要することが多いため、出力される立体物が精密さを問わないものである場合には、画像データの間引きのように、一定間隔でポリゴンを削除するという手法も考えられる。しかし、二次元の画像データの間引きと異なり、３次元構造を表現したポリゴンモデルの場合、削除したポリゴンに隣接するポリゴンの補正を行わなければ、削除した部分が空白になってしまい、意図した立体物を出力することができない。
【００１２】
例えば、図４２（ａ）に示すような２Ｄ画像データと、図４２（ｂ）に示すような３Ｄポリゴンモデルを比較してみる。図４２の２Ｄ画像データと３Ｄポリゴンモデルを、１／４程度に間引くと、それぞれ図４３（ａ）に示すような２Ｄ画像データ、３Ｄポリゴンモデルが得られる。図４３に示した２Ｄ画像データと３Ｄポリゴンモデルは、そのままでは空白が生じるため、図４４に示すように補間することになる。２Ｄ画像データを補間した場合、図４４（ａ）に示すように、画素間を補間するだけでよい。しかし、３Ｄポリゴンモデルの場合は、削除したポリゴンと頂点を共有するポリゴンを探索し、図４４（ｂ）に示すように、ポリゴン形状の補正をすることが必要となる。しかしながら、削除したポリゴンと頂点を共有するポリゴンを探索するには大きな処理負荷を要するという問題があった。
【００１３】
そこで、本発明は、出力造形物の品質の劣化を抑えながら、ポリゴンで構成されたポリゴンモデルから、少ない処理負荷で、効率的にポリゴンを削減して立体物造形用データを得ることが可能な立体物造形用データ削減装置を提供することを課題とする。
【課題を解決するための手段】
【００１４】
上記課題を解決するため、本発明第１の態様では、
ポリゴンの集合として表現されたポリゴンモデルのデータを、立体物の造形のために削減する装置であって、
前記ポリゴンモデルを構成する各ポリゴンの各頂点に対して、同一の座標値をもつ異なるポリゴンの頂点を探索し、取得された一連の頂点に対して同一の共有頂点ＩＤを付与することにより、各ポリゴンに含まれる各頂点を、同一座標の頂点を同一値とする共有頂点ＩＤで表現し、各頂点を含むポリゴンと対応付けて記録した頂点構成テーブルと、前記頂点構成テーブルに付与された共有頂点ＩＤと座標値を対応付けて記録した頂点座標テーブルとを作成するポリゴンモデル構造化手段と、
前記頂点座標テーブルに記録されている頂点と同一座標となる重複先の頂点との対応関係を記録する頂点重複テーブルを定義する頂点重複テーブル定義手段と、
前記頂点構成テーブルに記録されているポリゴンに対して所定の間隔で一部のポリゴンを削除対象ポリゴンとして設定する削除対象ポリゴン設定手段と、
前記頂点構成テーブルを参照して前記削除対象ポリゴンに対応する頂点を削除対象頂点として特定し、前記削除対象頂点を基に前記頂点座標テーブルを参照して複数の前記削除対象頂点の平均点を求め、前記削除対象頂点の１つを代表頂点とし、前記代表頂点以外の前記削除対象頂点の情報を頂点座標テーブルから削除するとともに、前記代表頂点の共有頂点ＩＤに、前記平均点の座標値を対応付けて記録する頂点座標テーブル更新手段と、
前記頂点重複テーブルにおいて、前記代表頂点以外の前記削除対象頂点の重複先を前記代表頂点に設定する頂点重複テーブル更新手段と、
前記頂点構成テーブルの各共有頂点ＩＤの値を、前記更新された頂点重複テーブルに設定された重複先に変更し、変更された結果、同一ポリゴンに対応する共有頂点ＩＤが２つ以上重複する場合、当該ポリゴンを前記頂点構成テーブルより削除する頂点構成テーブル更新手段と、
前記頂点構成テーブル更新手段により更新された頂点構成テーブルの各共有頂点ＩＤを前記頂点座標テーブル更新手段により更新された頂点座標テーブルを参照しながら座標値に置換することにより、ポリゴンモデルを更新するポリゴンモデル更新手段と、
を有することを特徴とする立体物造形用データ削減装置を提供する。
【００１５】
本発明第１の態様によれば、ポリゴンモデルを構成する各ポリゴンの各頂点に対して、同一の座標値をもつ異なるポリゴンの頂点を探索し、取得された一連の頂点に対して同一の共有頂点ＩＤを付与することにより、各ポリゴンに含まれる各頂点を、同一座標の頂点を同一値とする共有頂点ＩＤで表現し、各頂点を含むポリゴンと対応付けて記録した頂点構成テーブルと、頂点構成テーブルに付与された共有頂点ＩＤと座標値を対応付けて記録した頂点座標テーブルとを作成し、頂点座標テーブルに記録されている頂点と同一座標となる重複先の頂点との対応関係を記録する頂点重複テーブルを定義し、頂点構成テーブルに記録されているポリゴンに対して所定の間隔で一部のポリゴンを削除対象ポリゴンとして設定し、頂点構成テーブルを参照して削除対象ポリゴンに対応する頂点を削除対象頂点として特定し、削除対象頂点を基に頂点座標テーブルを参照して複数の削除対象頂点の平均点を求め、削除対象頂点の１つを代表頂点とし、代表頂点以外の削除対象頂点の情報を頂点座標テーブルから削除するとともに、代表頂点の共有頂点ＩＤに、平均点の座標値を対応付けて記録するようにし、頂点重複テーブルにおいて、代表頂点以外の削除対象頂点の重複先を代表頂点に設定するようにし、頂点構成テーブルの各共有頂点ＩＤの値を、更新された頂点重複テーブルに設定された重複先に変更し、変更された結果、同一ポリゴンに対応する共有頂点ＩＤが２つ以上重複する場合、そのポリゴンを頂点構成テーブルより削除するようにし、更新された頂点構成テーブルの各共有頂点ＩＤを、更新された頂点座標テーブルを参照しながら座標値に置換することにより、ポリゴンモデルを更新するようにしたので、設定された削除対象ポリゴンに隣接するポリゴンの探索負荷を減少させることができる。このため、出力造形物の品質の劣化を抑えながら、ポリゴンで構成されたポリゴンモデルから、少ない処理負荷で、効率的にポリゴンを削減して立体物造形用データを得ることが可能となる。特に、医療用のCT/MRI画像をもとに生成されたサーフェースデータ等のポリゴンモデルを効率良く３Ｄプリンタ等の立体物造形装置に出力することが可能となる。
【００１６】
また、本発明第２の態様では、前記ポリゴンの集合体は配列構造で定義されており、前記ポリゴンモデル構造化手段は、前記ポリゴンモデルを構成する各ポリゴンの各頂点を対象頂点とし、前記配列上で前記対象頂点より後方に位置し、当該対象頂点に最も近接し、当該対象頂点と同一座標となる他のポリゴンの頂点を１つ検出し、他のポリゴンの頂点と前記対象頂点を対応付け、それぞれポリゴンを識別可能な形式で記録した頂点リンクテーブルを作成し、前記ポリゴンモデルを構成する各ポリゴンの各頂点を起点に、前記作成された頂点リンクテーブルを参照し、一連の共有頂点を取得することを特徴とする。
【００１７】
本発明第２の態様によれば、ポリゴンの集合体を配列構造で定義し、ポリゴンモデルを構成する各ポリゴンの各頂点を対象頂点とし、配列上で対象頂点より後方に位置し、対象頂点が属するポリゴンに最も近接し、対象頂点と同一座標となる他のポリゴンの頂点を１つ検出し、他のポリゴンの頂点と対象頂点を対応付け、それぞれポリゴンを識別可能な形式で記録した頂点リンクテーブルを作成し、ポリゴンモデルを構成する各ポリゴンの各頂点を起点に、作成された頂点リンクテーブルを参照し、一連の共有頂点を取得するようにしたので、本来Ｎ個のポリゴンを１／１０に減らそうとすると、Ｎの２乗に比例して増える処理負荷を、Ｎに比例した処理負荷に減らすことが可能となる。
【００１８】
また、本発明第３の態様では、
前記頂点座標テーブル更新手段は、
前記削除対象ポリゴンに含まれる３つの削除対象の頂点の共有頂点ＩＤをもとに前記頂点座標テーブルを参照し、前記３つの削除対象の頂点の平均点座標を算出し、前記削除対象の頂点のうちの１つを代表頂点とし、前記頂点座標テーブルに記録されている前記代表頂点の共有頂点ＩＤの座標値を、前記平均点座標に置換することを特徴とする。
【００１９】
本発明第３の態様によれば、削除対象ポリゴンに含まれる３つの削除対象の頂点の共有頂点ＩＤをもとに頂点座標テーブルを参照し、３つの削除対象の頂点の平均点座標を算出し、削除対象の頂点のうちの１つを代表頂点とし、頂点座標テーブルに記述されている代表頂点の共有頂点ＩＤの座標値を、平均点座標に置換するようにしたので、削除対象ポリゴンと隣接するポリゴンを含めて効率的にポリゴンの削除を行うことが可能となる。
【００２０】
また、本発明第４の態様では、前記頂点座標テーブル更新手段は、前記削除対象ポリゴンに含まれる３つの削除対象の頂点より辺の長さが最も短い２頂点を選定し、選定された２つの頂点の共有頂点ＩＤをもとに前記頂点座標テーブルを参照し、前記２つの削除対象の頂点の中点座標を算出し、前記削除対象の頂点のうちの１つを代表頂点とし、前記頂点座標テーブルに記録されている前記代表頂点の共有頂点ＩＤの座標値を、前記中点座標に置換することを特徴とする。
【００２１】
本発明第４の態様によれば、削除対象ポリゴンに含まれる３つの削除対象の頂点より辺の長さが最も短い２頂点を選定し、選定された２つの頂点の共有頂点ＩＤをもとに頂点座標テーブルを参照し、２つの削除対象の頂点の中点座標を算出し、削除対象の共有頂点のうちの１つを代表頂点とし、頂点座標テーブルに記録されている代表頂点の共有頂点ＩＤの座標値を、中点座標に置換することを特徴とするようにしたので、ポリゴンモデルの全体形状に歪をあまり与えずにポリゴンの削除を行うことが可能となる。
【００２２】
また、本発明第５の態様では、前記ポリゴンモデル更新手段により更新されたポリゴンモデルを構成するポリゴン数が所定の目標値より大きい場合、前記削除対象ポリゴン設定手段、前記頂点座標テーブル更新手段、前記頂点重複テーブル更新手段、前記頂点構成テーブル更新手段、前記ポリゴンモデル更新手段に対して繰り返して処理を実行させる制御を行う制御手段と、を更に備えることを特徴とする。
【００２３】
本発明第５の態様によれば、更新されたポリゴンモデルを構成するポリゴン数が目標値より大きい場合、削除対象ポリゴンの設定、頂点座標テーブルの更新、頂点重複テーブルの更新、頂点構成テーブルの更新、ポリゴンモデルの更新を繰り返して行うようにしたので、ポリゴンモデルを構成するポリゴン数を目標値まで削減することが可能となる。
【００２４】
また、本発明第６の態様では、
ポリゴンの集合として表現されたポリゴンモデルのデータを、立体物の造形のために削減する装置であって、
前記ポリゴンモデル更新手段により削減されたポリゴンモデルである削減ポリゴンモデルを構成する各ポリゴンの面積を基に、追加削除するべきポリゴンを追加削除対象ポリゴンとして選定する追加削除対象ポリゴン選定手段と、
前記追加削除対象ポリゴンを構成する辺の長さに基づいて、追加削除するべき辺を追加削除対象辺として選定する追加削除対象辺選定手段と、
前記追加削除対象ポリゴン以外のポリゴンから、前記追加削除対象辺の２頂点のいずれか１頂点を共有するポリゴンである追加削除頂点共有ポリゴンを探索する追加削除頂点共有ポリゴン探索手段と、
前記追加削除対象辺の２頂点の双方を共有する追加削除頂点共有ポリゴンを、前記追加削除対象ポリゴンとともに削除し、前記探索された追加削除対象辺のいずれか１頂点のみを共有する追加削除頂点共有ポリゴンに対して、前記共有する１頂点を前記追加削除対象辺の２頂点の中点の位置に補正するポリゴンモデル追加更新手段と、
を更に備えることを特徴とする。
【００２５】
本発明第６の態様によれば、
削減されたポリゴンモデルである削減ポリゴンモデルを構成する各ポリゴンの面積を基に、追加削除するべきポリゴンを追加削除対象ポリゴンとして選定し、追加削除対象ポリゴンを構成する辺の長さに基づいて、追加削除するべき辺を追加削除対象辺として選定し、追加削除対象ポリゴン以外のポリゴンから、追加削除対象辺の２頂点のいずれか１頂点を共有するポリゴンである追加削除頂点共有ポリゴンを探索し、追加削除対象辺の２頂点の双方を共有する追加削除頂点共有ポリゴンを、追加削除対象ポリゴンとともに削除し、探索された追加削除対象辺のいずれか１頂点のみを共有する追加削除頂点共有ポリゴンに対して、共有する１頂点を追加削除対象辺の２頂点の中点の位置に補正するようにしたので、削減されたポリゴンモデルに対して、大きな歪を加えることなく追加削減することが可能となる。
【００２６】
また、本発明第７の態様では、
前記立体物造形用データ削減装置と、
前記立体物造形用データ削減装置から出力されたポリゴンモデルを用いて立体物を造形する立体物造形装置と、
を有することを特徴とする立体物造形システム
を有することを特徴とする立体物造形システムを提供する。
【００２７】
本発明第７の態様によれば、立体物造形用データ削減装置と、立体物造形用データ削減装置から出力されたポリゴンモデルを用いて立体物を造形する立体物造形装置により立体物造形システムを実現するようにしたので、ボードコンピュータを組み込んだ３Ｄプリンタ等の形態で、立体物造形システムを提供することが可能となる。
【発明の効果】
【００２８】
本発明によれば、出力造形物の品質の劣化を抑えながら、ポリゴンで構成されたポリゴンモデルから、少ない処理負荷で、効率的にポリゴンを削減して立体物造形用データを得ることが可能となる。
【図面の簡単な説明】
【００２９】
【図１】本発明の一実施形態に係る立体物造形用データ削減装置のハードウェア構成図である。
【図２】本発明の一実施形態に係る立体物造形用データ削減装置の構成を示す機能ブロック図である。
【図３】DICOM形式ボクセルデータからポリゴンモデルへの変換の様子を示す図である。
【図４】DICOM形式ボクセルデータを、複数のスライス画像として示した図である。
【図５】DICOM形式ボクセルデータを、４つの形態で表示した例である。
【図６】図５に示したDICOM形式ボクセルデータを「3D-Slicer」により変換して得られたＳＴＬデータを示す図である。
【図７】領域別ポリゴンモデル（ＳＴＬデータ）を示す図である。
【図８】領域別ＳＴＬデータを合成したポリゴンモデル（ＳＴＬデータ）のレンダリング像を示す図である。
【図９】本発明の一実施形態に係る立体物造形用データ削減装置の処理概要を示すフローチャートである。
【図１０】グループ分類手段２０によるグループ分類処理の詳細を示すフローチャートである。
【図１１】処理対象とするポリゴン群の一例を示す図である。
【図１２】図１１に示したポリゴン群を実現するための頂点座標配列データを示す図である。
【図１３】ステップＳ２０におけるポリゴン削減処理の詳細を示すフローチャートである。
【図１４】頂点リンクテーブルの一例を示す図である。
【図１５】最初の共有頂点ＩＤが付与された状態の頂点リンクテーブル、頂点座標テーブルを示す図である。
【図１６】リンク元の全ての頂点について、共有頂点ＩＤが付与された状態の頂点リンクテーブル、頂点座標テーブルを示す図である。
【図１７】頂点重複テーブルの初期化時における頂点構成テーブル、頂点座標テーブル、頂点重複テーブルを示す図である。
【図１８】Ｐ６とＰ１６の２つの削除対象ポリゴンが設定された状態のポリゴン群を示す図である。
【図１９】ポリゴンＰ６が削除された状態の頂点構成テーブル、頂点座標テーブル、頂点重複テーブルを示す図である。
【図２０】ポリゴンＰ１６が削除された状態の頂点構成テーブル、頂点座標テーブル、頂点重複テーブルを示す図である。
【図２１】頂点重複テーブルを用いた頂点構成テーブル更新の例を示す図である。
【図２２】削除対象ポリゴンに隣接するポリゴンに関する、頂点構成テーブル更新の例を示す図である。
【図２３】ポリゴン削除処理後の頂点座標配列データを示す図である。
【図２４】ポリゴン削除処理後のポリゴン群の状態を示す図である。
【図２５】Ｐ６とＰ１６の２つの削除対象ポリゴンの一辺が削除対象辺として設定された状態のポリゴン群を示す図である。
【図２６】削除対象辺ＤＥが削除された状態の頂点構成テーブル、頂点座標テーブル、頂点重複テーブルを示す図である。
【図２７】削除対象辺ＪＫが削除された状態の頂点構成テーブル、頂点座標テーブル、頂点重複テーブルを示す図である。
【図２８】頂点重複テーブルを用いた頂点構成テーブル更新の例を示す図である。
【図２９】削除対象ポリゴンに隣接するポリゴンに関する、頂点構成テーブル更新の例を示す図である。
【図３０】ポリゴン削除処理後の頂点座標配列データを示す図である。
【図３１】ポリゴン削除処理後のポリゴン群の状態を示す図である。
【図３２】ポリゴン削減処理により生じる問題を説明するための図である。
【図３３】隔離された小体積グループの削除処理の詳細を示すフローチャートである。
【図３４】図３３のステップＳ４４における最小間隔の算出処理の詳細を示すフローチャートである。
【図３５】ポリゴン削減の第１の比較事例を示す図である。
【図３６】ポリゴン削減の第１の事例を示す図である。
【図３７】ポリゴン削減の第２の比較事例を示す図である。
【図３８】ポリゴン削減の第２の事例を示す図である。
【図３９】本発明第２の実施形態に係る立体物造形用データ削減装置を示す機能ブロック図である。
【図４０】ポリゴン追加削減の基本原理を示す図である。
【図４１】ポリゴン追加削減処理の詳細を示すフローチャートである。
【図４２】２Ｄ画像データと３Ｄポリゴンモデルを示す図である。
【図４３】２Ｄ画像データと３Ｄポリゴンモデルに対して間引き削除を行った状態を示す図である。
【図４４】間引き削除された２Ｄ画像データと３Ｄポリゴンモデルに対して補間処理を行った状態を示す図である。
【発明を実施するための形態】
【００３０】
以下、本発明の好適な実施形態について図面を参照して詳細に説明する。
＜１．装置構成＞
図１は、本発明の一実施形態に係る立体物造形用データ削減装置２００を含む立体物造形システムのハードウェア構成図である。本実施形態に係る立体物造形用データ削減装置２００は、汎用のコンピュータで実現することができ、図１に示すように、ＣＰＵ（Central Processing Unit）１と、コンピュータのメインメモリであるＲＡＭ（Random Access Memory）２と、ＣＰＵ１が実行するプログラムやデータを記憶するためのハードディスク、フラッシュメモリ等の大容量の記憶装置３と、キーボード、マウス等のキー入力Ｉ／Ｆ（インターフェース）４と、３Ｄプリンタやデータ記憶媒体等の外部装置とデータ通信するためのデータ入出力Ｉ／Ｆ（インターフェース）５と、液晶ディスプレイ等の表示デバイスである表示部６と、を備え、互いにバスを介して接続されている。
【００３１】
３Ｄプリンタ７は、汎用の３Ｄプリンタであり、立体物の三次元形状をポリゴンの集合で表現したポリゴンモデルである立体物造形用データを基に樹脂、石膏等の素材を加工して立体物を造形する立体物造形装置である。３Ｄプリンタ７は、データ処理部７ａと出力部７ｂを有している。３Ｄプリンタ７のデータ処理部７ａは、データ入出力Ｉ／Ｆ５に接続されており、データ入出力Ｉ／Ｆ５から受け取った削減された立体物造形用データを基に、出力部７ｂが立体物を造形するようになっている。
【００３２】
図１では、立体物造形用データ削減装置２００と３Ｄプリンタ７は分離した形態で示されているが、現在市販されている殆どの３Ｄプリンタ製品には立体物造形用データ削減装置２００の構成要素である、ＣＰＵ１、ＲＡＭ２、記憶装置３、キー入力Ｉ／Ｆ４（汎用コンピュータ向けキーボード・マウスではなく、テンキーレベルの数種のボタン）、データ入出力Ｉ／Ｆ５、表示部６（数行の文字を表示可能な小型液晶パネル、タッチパネルを重畳させキー入力Ｉ／Ｆ４を兼ねることも多い）も小規模ながら重複して備えている。従って、３Ｄプリンタ７自体が外部記憶媒体経由で立体物造形用データを直接受け取り、単独で立体物を造形する運用も可能になっている（特に民生用の３Ｄプリンタではこちらの形態の方が多い）。すなわち、図１に示した立体物造形システムを１つの筐体に収めて、“３Ｄプリンタ”という製品として流通することも多い。
【００３３】
図２は、本実施形態に係る立体物造形用データ削減装置の構成を示す機能ブロック図である。図２において、１０は制御手段、２０はグループ分類手段、３０はポリゴンモデル構造化手段、４０は頂点重複テーブル定義手段、５０は削除対象ポリゴン設定手段、６０は頂点座標テーブル更新手段、７０は頂点重複テーブル更新手段、８０は頂点構成テーブル更新手段、９０はポリゴンモデル更新手段、１００はグループ合成手段、１１０はポリゴンモデル合成手段、１２０は領域別ポリゴンモデル記憶手段、１３０は合成ポリゴンモデル記憶手段である。
【００３４】
制御手段１０は、立体物造形用データ削減装置全体の制御を行う。グループ分類手段２０は、削除対象ポリゴンの選定対象のポリゴンモデルに対して、各グループに属するポリゴンがそのグループ内の他のいずれかのポリゴンと、ポリゴンを構成する辺（２頂点）を共有するようにグループ分類する。ポリゴンモデル構造化手段３０は、ポリゴンモデルから、各ポリゴンに含まれる各頂点を、同一座標の頂点を同一値とする共有頂点ＩＤで表現し、ポリゴンを構成する各頂点を共有頂点ＩＤで表現してポリゴンと対応付けて記録した頂点構成テーブルと、頂点構成テーブルに付与された共有頂点ＩＤと座標値を対応付けて記録した頂点座標テーブルを作成する。頂点重複テーブル定義手段４０は、頂点座標テーブルに記録されている共有頂点ＩＤと同一座標となる重複先の共有頂点ＩＤとの対応関係を記録する頂点重複テーブルを定義する。削除対象ポリゴン設定手段５０は、頂点構成テーブルに記録されているポリゴンに対して所定の間隔で一部のポリゴンを削除対象ポリゴンとして設定する。
【００３５】
頂点座標テーブル更新手段６０は、頂点構成テーブルを参照して削除対象ポリゴンを構成する複数の共有頂点ＩＤを削除対象頂点として特定し、削除対象頂点を基に頂点座標テーブルを参照して複数の削除対象頂点の平均点を求め、削除対象頂点の１つを代表頂点とし、代表頂点以外の削除対象頂点の情報を頂点座標テーブルから削除するとともに、代表頂点の共有頂点ＩＤに、平均点の座標値を対応付けて記録する。頂点重複テーブル更新手段７０は、頂点重複テーブルにおいて、代表頂点以外の全ての削除対象頂点の重複先を代表頂点に設定する。頂点構成テーブル更新手段８０は、頂点構成テーブルの中で、更新された頂点重複テーブルにおいて更新された共有頂点ＩＤの値を、更新された重複先に変更し、変更された結果、ポリゴンを構成する同一の値をもつ共有頂点ＩＤが２つ以上重複する場合、当該ポリゴンを頂点構成テーブルより削除する。ポリゴンモデル更新手段９０は、更新された頂点構成テーブルの各共有頂点ＩＤを、更新された頂点座標テーブルを参照しながら座標値に置換することにより、間引かれたポリゴンの配列で表現されたポリゴンモデルを作成する。
【００３６】
グループ合成手段１００は、分類された各グループに対するポリゴンモデル構造化手段３０、頂点重複テーブル定義手段４０、削除対象ポリゴン設定手段５０、頂点座標テーブル更新手段６０、頂点重複テーブル更新手段７０、頂点構成テーブル更新手段８０、ポリゴンモデル更新手段９０による一連の処理の実行により作成された複数のグループの更新されたポリゴンモデルを、領域別に単一の領域別ポリゴンモデルに合成する。ポリゴンモデル合成手段１１０は、複数セットの更新された領域別ポリゴンモデルを単一の合成ポリゴンモデルに合成する。制御手段１０、グループ分類手段２０、ポリゴンモデル構造化手段３０、頂点重複テーブル定義手段４０、削除対象ポリゴン設定手段５０、頂点座標テーブル更新手段６０、頂点重複テーブル更新手段７０、頂点構成テーブル更新手段８０、ポリゴンモデル更新手段９０、グループ合成手段１００、ポリゴンモデル合成手段１１０は、ＣＰＵ１が、記憶装置３に記憶されているプログラムを実行することにより実現される。
【００３７】
領域別ポリゴンモデル記憶手段１２０は、領域別ポリゴンモデルを記憶した記憶手段であり、記憶装置３により実現される。領域別ポリゴンモデルとは、１つの領域を１セットとして構成されたポリゴンモデルである。合成ポリゴンモデル記憶手段１３０は、複数セットの領域別ポリゴンモデルを合成した単一のポリゴンモデルである合成ポリゴンモデルを記憶する記憶手段であり、記憶装置３により実現される。合成ポリゴンモデル記憶手段１３０に記憶される合成ポリゴンモデルは、３Ｄプリンタ７への出力に削減された立体物造形用データとなる。領域別ポリゴンモデル記憶手段１２０に記憶された領域別ポリゴンモデル、合成ポリゴンモデル記憶手段１３０に記憶される合成ポリゴンモデルは、いずれもポリゴンの集合体であり、ポリゴン単位で各ポリゴンが有する頂点を記録した形式となっている。
【００３８】
図２に示した各構成手段は、現実には図１に示したように、コンピュータおよびその周辺機器等のハードウェアに専用のプログラムを搭載することにより実現される。すなわち、コンピュータが、専用のプログラムに従って各手段の内容を実行することになる。なお、本明細書において、コンピュータとは、ＣＰＵ等の演算処理部を有し、データ処理が可能な装置を意味し、パーソナルコンピュータなどの汎用コンピュータだけでなく、製品としての“３Ｄプリンタ”に組み込まれたボードコンピュータも含む。
【００３９】
図１に示した記憶装置３には、ＣＰＵ１を動作させ、コンピュータを、立体物造形用データ削減装置として機能させるための専用のプログラムが実装されている。この専用のプログラムを実行することにより、ＣＰＵ１は、制御手段１０、グループ分類手段２０、ポリゴンモデル構造化手段３０、頂点重複テーブル定義手段４０、削除対象ポリゴン設定手段５０、頂点座標テーブル更新手段６０、頂点重複テーブル更新手段７０、頂点構成テーブル更新手段８０、ポリゴンモデル更新手段９０、グループ合成手段１００、ポリゴンモデル合成手段１１０としての機能を実現することになる。また、記憶装置３は、領域別ポリゴンモデル記憶手段１２０、合成ポリゴンモデル記憶手段１３０として機能するだけでなく、立体物造形用データ削減装置としての処理に必要な様々なデータを記憶する。
【００４０】
＜２．処理動作＞
＜２．１．前処理＞
次に、図１、図２に示した立体物造形用データ削減装置の処理動作について説明する。まず、医療用ボクセルデータからサーフェースデータである領域別ポリゴンモデルを作成する前処理について説明する。サーフェースデータとは、サーフェースモデリングにより立体構造を表面形状として表現したデータであり、多角形のデータであるポリゴンにより構成されるポリゴンモデルである。前処理は、コンピュータが公知のプログラムを実行することにより行われる。ここでは、公知のプログラムとして、米国ハーバード大学が中心に開発したオープンソースソフトウェアである「3D-Slicer」を用いた場合を例にとって説明する。まず、コンピュータが、全体ボクセルデータから、特定臓器領域のボクセルデータを抽出する。次に、コンピュータが、特定臓器領域のボクセルデータをポリゴンモデルであるサーフェースデータに変換する。このようにして得られた領域別ポリゴンモデルは、領域別ポリゴンモデル記憶手段１２０に格納される。前処理は、図１に示した立体物造形用データ削減装置を実現するコンピュータに、上記プログラムを実行させることにより行ってもよいし、図１に示した立体物造形用データ削減装置を実現するコンピュータとは別のコンピュータにより実行し、得られた領域別ポリゴンモデルを記憶装置３により実現される領域別ポリゴンモデル記憶手段１２０に格納するようにしてもよい。
【００４１】
本実施形態では、医療用ボクセルデータとして医用画像データ交換に関する国際標準規格であるDICOM形式のボクセルデータを用いる。また、ポリゴンモデルであるサーフェースデータとしてＳＴＬ（Standard Triangulated Language）データを用いる。ＳＴＬデータとは、元来３Ｄグラフィックス分野におけるモデリングデータ交換に関する業界標準で、最近では３Ｄプリンタでも標準的に使用されるようになったもので、三次元形状を三角形のポリゴンの集合体で表現したデータである。そして、コンピュータが上記「3D-Slicer」を実行することにより、図３（ａ）に示すようなDICOM形式ボクセルデータから、図３（ｂ）に示すような領域別のボクセルデータを抽出し、サーフェースモデル変換を行って図３（ｃ）に示すようなポリゴンモデル（ＳＴＬデータ）が得られる。領域別のボクセルデータの抽出、サーフェースモデル変換には、特許文献３等に記載されたMarching Cube法が用いられている。
【００４２】
図４〜図８に、「3D-Slicer」による処理画面の一例を示す。図４は、「3D-Slicer」の処理対象となるDICOM形式ボクセルデータを、複数のスライス画像として示した図である。図４の例では、人体頭部のサジタル像を２５６個のスライス画像で示している。各スライス画像は、５１２×５１２画素で構成されている。
【００４３】
図５は、DICOM形式ボクセルデータを、４つの形態で表示した例である。図５において、上部に表示されているのは、ボリュームレンダリング像である。下部に表示されているのは、左側から順にアキシャル像、サジタル像、コロナル像である。
【００４４】
図６は、図５に示したDICOM形式ボクセルデータを「3D-Slicer」により変換して得られたＳＴＬデータを示す図である。図６において、上部に表示されているのは、ＳＴＬデータのレンダリング像である。図６の例では、眼球・脳領域しきい値：626.75以上（MRI撮影でボクセル値10bits幅の場合）、眼球結合組織Ｌしきい値：298.36-458.74、眼球結合組織Ｒしきい値：298.36-431.32を設定することにより、領域（組織）別に分類された領域別ＳＴＬデータをレンダリングしたものを示している。
【００４５】
図７は、「3D-Slicer」により得られた領域別ＳＴＬデータをシェーディングにより陰影表現した図である。図８は、領域別ＳＴＬデータを合成したポリゴンモデル（ＳＴＬデータ）のレンダリング像を示す図である。図８に示すFront Viewは、図６の上部に示したものと同一である。前処理の後は、図７に示したような領域別ポリゴンモデルが領域別ポリゴンモデル記憶手段１２０に記憶される。
【００４６】
＜２．２．処理概要＞
次に、図１、図２に示した立体物造形用データ削減装置の処理動作について説明する。図９は、本発明の一実施形態に係る立体物造形用データ削減装置の処理概要を示すフローチャートである。まず、グループ分類手段２０が、領域別ポリゴンモデル記憶手段１２０から、１つの領域についての領域別ポリゴンモデルを読み込み、複数のグループに分類する（ステップＳ１０）。次に、各グループのポリゴンモデルに対して、ポリゴンモデル構造化手段３０、頂点重複テーブル定義手段４０、削除対象ポリゴン設定手段５０、頂点座標テーブル更新手段６０、頂点重複テーブル更新手段７０、頂点構成テーブル更新手段８０、ポリゴンモデル更新手段９０が、ポリゴン削減処理を実行する（ステップＳ２０）。制御手段１０が、全グループについてポリゴン削減処理が終了したか否かを判定し（ステップＳ３０）、全グループについて終了していない場合は、未処理のグループに対してステップＳ２０のポリゴン削減処理を実行する。全グループに対するポリゴン削減処理が終了した場合は、グループ合成手段１００が、隔離された小体積グループの削除を行う（ステップＳ４０）。続いて、グループ合成手段１００は、全グループのポリゴンモデルの合成を行う（ステップＳ５０）。制御手段１０が、全領域について処理が終了したか否かを判定し（ステップＳ６０）、全領域について終了していない場合は、未処理の領域に対してステップＳ１０〜Ｓ５０の処理を実行する。全領域に対する処理が終了した場合は、ポリゴンモデル合成手段１１０が、全領域の領域別ポリゴンモデルの合成を行う（ステップＳ７０）。
【００４７】
＜２．３．グループ分類処理＞
まず、ステップＳ１０におけるグループ分類手段２０によるグループ分類処理について説明する。図１０は、グループ分類手段２０によるグループ分類処理の詳細を示すフローチャートである。グループ分類手段２０は、まず、初期設定を行う（ステップＳ１１）。具体的には、読み込んだ領域別ポリゴンモデルを構成するポリゴン数Ｐ、ポリゴンを特定する変数ｐ（ｐ＝０，・・・，Ｐ−１）、探索ステータスＳ（ｐ）、グループ属性Ｇ（ｐ）、グループを特定する変数ｇを設定する。探索ステータスＳ（ｐ）は、０、１、２のいずれかの値をとる。Ｓ（ｐ）＝０はグループに未分類の状態、Ｓ（ｐ）＝１はグループに分類された状態、Ｓ（ｐ）＝２は、そのポリゴンに隣接するポリゴンである隣接ポリゴンがグループに分類された状態を示す。さらに、ステップＳ１１においては、ｐ＝０，・・・，Ｐ−１の全てのｐについてＳ（ｐ）＝Ｇ（ｐ）＝０、ｇ＝１と初期設定する。
【００４８】
次に、全ポリゴンより、Ｓ（ｐ）＝Ｇ（ｐ）＝０となるポリゴンｐを１つ抽出する（ステップＳ１２）。初期状態では、全てＳ（ｐ）＝Ｇ（ｐ）＝０であるので、初回は必ず抽出が行われる。Ｓ（ｐ）＝Ｇ（ｐ）＝０となるポリゴンｐが複数存在する場合は、例えばｐの値が最も小さいものを抽出する。ステップＳ１２において、Ｓ（ｐ）＝Ｇ（ｐ）＝０となるポリゴンｐが存在しない場合、すなわち、全てのｐ＝０，・・・，Ｐ−１について、Ｓ（ｐ）＝２である場合、ｇ−１個のグループに分離できたものとしてグループ分類処理を終了する。なお、ステップＳ１２において、Ｓ（ｐ）＝１である状態は存在しないため、Ｓ（ｐ）は“０”か“２”のいずれかの状態である。Ｓ（ｐ）＝Ｇ（ｐ）＝０となるポリゴンｐが抽出できた場合は、抽出したポリゴンｐに対応する探索ステータスＳ（ｐ）＝１、グループ属性Ｇ（ｐ）＝ｇに設定する。
【００４９】
ステップＳ１２において、Ｓ（ｐ）＝Ｇ（ｐ）＝０となるポリゴンｐを１つ抽出し、抽出したポリゴンｐに対応する探索ステータスＳ（ｐ）＝１、グループ属性Ｇ（ｐ）＝ｇに設定した場合は、全ポリゴンより、Ｓ（ｑ）＝１となるポリゴンｑを１つ抽出する（ステップＳ１３）。ｑはポリゴンを特定する変数であり、ポリゴンｐと同様、ｑ＝０，・・・，Ｐ−１内のいずれかの整数値をとる。Ｓ（ｑ）＝１となるポリゴンｑが複数存在する場合は、例えばｑの値が最も小さいものを抽出する。ステップＳ１３において、Ｓ（ｑ）＝１となるポリゴンｑが存在しない場合、すなわち、全てのＳ（ｑ）＝０または２である場合、グループを特定する変数ｇを１インクリメント（ｇ←ｇ＋１）する（ステップＳ１４）。そしてステップＳ１２に戻り、次のグループへの分類を行う。
【００５０】
ステップＳ１３において、Ｓ（ｑ）＝１となるポリゴンｑを１つ抽出した場合、全ポリゴンより、Ｓ（ｒ）＝Ｇ（ｒ）＝０であって、抽出されたポリゴンｑと２頂点を共有する隣接ポリゴンｒを全て抽出する（ステップＳ１５）。ｒはポリゴンを特定する変数であり、ポリゴンｐ、ｑと同様、ｒ＝０，・・・，Ｐ−１内のいずれかの整数値をとる。“ポリゴンｑと２頂点を共有する”とは、ポリゴンｑと一つの辺を共有することを意味する。すなわち、隣接ポリゴンｒは一つの辺を共有することによりポリゴンｑと隣接するポリゴンである。抽出された隣接ポリゴンについては、それぞれ探索ステータスＳ（ｒ）＝１、グループ属性Ｇ（ｒ）＝ｇに設定する。
【００５１】
次に、ポリゴンｑの探索ステータスＳ（ｑ）＝２に設定する（ステップＳ１６）。すなわち、ポリゴンｑについては、隣接ポリゴンを設定した後の状態とする。そして、ステップＳ１３に戻って、全ポリゴンの中から、Ｓ（ｑ）＝１となるポリゴンｑを１つ抽出する。
【００５２】
図１０に示したフローチャートでは、ステップＳ１２、Ｓ１３、Ｓ１４で構成されるループと、ステップＳ１３、Ｓ１５、Ｓ１６で構成されるループの２つのループ処理が存在する。ステップＳ１２、Ｓ１３、Ｓ１４で構成されるループでは、グループに未分類のポリゴンを抽出してグループに分類し（ステップＳ１２）、グループに分類済みのポリゴンの中から１つを隣接ポリゴン探索用のポリゴンとして抽出できない場合（ステップＳ１３）は、そのグループに分類すべきポリゴンは、存在しないものとして、次のグループに移行（ｇ←ｇ＋１）する（ステップＳ１４）。ステップＳ１２、Ｓ１３、Ｓ１４で構成されるループでは、連続する一塊のポリゴン群を一つのグループとして分類する。したがって、ステップＳ１３において、Ｓ（ｑ）＝１となるポリゴンが存在しない場合には、グループに分類済みのいずれかのポリゴンに隣接するポリゴンが存在しないことになるので、グループｇへの分類を終え、グループｇ＋１への分類に移行するのである。
【００５３】
ステップＳ１３、Ｓ１５、Ｓ１６で構成されるループでは、グループに分類済みのポリゴンの中から１つを隣接ポリゴン探索用のポリゴンｑとして抽出し（ステップＳ１３）、全ポリゴンの中からポリゴンｑと２頂点を共有するポリゴンを隣接ポリゴンｒとして抽出し（ステップＳ１５）、抽出できた場合も抽出できない場合も、探索用のポリゴンｑの探索ステータスＳ（ｑ）を、ポリゴンｑに隣接するポリゴンの探索を終えた状態であるＳ（ｑ）＝２に設定する。
【００５４】
ステップＳ１２、Ｓ１３、Ｓ１４で構成されるループと、ステップＳ１３、Ｓ１５、Ｓ１６で構成されるループの２つのループ処理を用いることにより、全Ｐ個のポリゴンが、２頂点を共有して連続するポリゴン群ごとにグループに分類される。１頂点しか共有しないポリゴンのみで隣接している場合は、別のグループとして分類されることになる。図１０に従った処理を実行することにより領域別ポリゴンモデルを構成するポリゴンは複数のグループに分類されることになる。
【００５５】
＜２．４．ポリゴン削減処理＞
＜２．４．１．ポリゴン単位削除＞
次に、ステップＳ２０におけるポリゴンモデル構造化手段３０、頂点重複テーブル定義手段４０、削除対象ポリゴン設定手段５０、頂点座標テーブル更新手段６０、頂点重複テーブル更新手段７０、頂点構成テーブル更新手段８０、ポリゴンモデル更新手段９０によるポリゴン削減処理について説明する。ポリゴン削減処理におけるポリゴンの削除の手法として、ポリゴン単位削除と稜線単位削除の２方式が存在する。まず、ポリゴン単位削除について説明する。
【００５６】
図１１は、処理対象とするポリゴン群の一例を示す図である。ポリゴンモデルは、図１２に示されるように空間における三次元の値をもつポリゴン群であるが、図１１の例では、紙面上での説明の便宜上、二次元空間に投影したポリゴン群を示している。図１１の例では、削減前、１８個の三角形のポリゴンからなるポリゴン群を示している。図１１において、Ａ〜Ｎは特定のポリゴンに属する形式でなく、座標が異なる頂点を識別するために示している。頂点Ａ〜Ｎは、ポリゴン群全体において頂点を識別するために、便宜上付されたものであり、後述する頂点座標配列データや、頂点リンクテーブル、頂点構成テーブル、頂点座標テーブル、頂点重複テーブルには記録されていない（一部記載されているものは、理解を容易にするために用いられている。）。また、ポリゴン番号Ｐ１〜Ｐ１８、頂点Ａ〜Ｎを各ポリゴン番号に対応付けて表現された頂点番号Ｖ１ａ〜Ｖ１８ｃが記載されている。後述する頂点座標配列データ、頂点リンクテーブル、頂点構成テーブルには、このポリゴン番号や頂点番号の形式で記録されている。
【００５７】
図１２は、図１１に示したポリゴン群を実現するための頂点座標配列データを示す図である。頂点座標配列データは、ポリゴンモデルを規定するデータであり、ポリゴンの集合体であるポリゴンモデルを配列構造で定義している。図１２に示すように、頂点座標配列データは、ポリゴンを識別する識別情報であるポリゴン番号Ｐ１〜Ｐ１８に対応付けて、ポリゴンを構成する第１頂点、第２頂点、第３頂点の３つの頂点の頂点番号別に各座標値が記録されている。頂点番号は、その頂点が属するポリゴンの番号が特定される形式で頂点を識別する識別情報である。具体的には、図１１に示すように、頂点を示すＶの後に、対応するポリゴン番号に含まれる数字、そして第１頂点、第２頂点、第３頂点の別を示すａ〜ｃのいずれかのアルファベットで表現する。例えば、図１２の１行目に示すように、ポリゴンＰ１の第１頂点は、“Ｖ１ａ”と表現される。頂点番号“Ｖ１ａ”に数字“１”が入っているため、ポリゴンＰ１の頂点であることが明確になっている。また、図１２の頂点座標配列データにおいて、各頂点の座標は、図１１で示した頂点Ａ〜Ｎのいずれかに対応するため、各頂点の座標値に頂点Ａ〜Ｎを識別するアルファベットの小文字を添えて表現している。例えば、図１２の１行目に示すように、ポリゴンＰ１の第１頂点Ｖ１ａの座標値は、“（Ｘｄ，Ｙｄ，Ｚｄ）”と表現される。各ポリゴンごとに、構成される３つの頂点に対応付けて３つの頂点の座標値が記録されている。
【００５８】
上記のような規則に従って作成されるため、頂点座標配列データにおいては、同一座標の頂点が複数箇所に重複して記録されることになる。例えば、図１１に示した頂点Ｄは、６つのポリゴンＰ１，Ｐ２，Ｐ４，Ｐ５，Ｐ６，Ｐ７に共有されるため、座標値“（Ｘｄ，Ｙｄ，Ｚｄ）”は、頂点Ｖ１ａ，Ｖ２ａ，Ｖ４ｂ，Ｖ５ｃ，Ｖ６ｃ，Ｖ７ｃとして６箇所に記録される。
【００５９】
図１３は、稜線単位削除の場合におけるポリゴン削減処理の詳細を示すフローチャートである。まず、ポリゴンモデル構造化手段３０が、頂点リンクテーブルを作成する（ステップＳ２１）。頂点リンクテーブルは、ポリゴンの各頂点について、その頂点と同一座標となる他のポリゴンの頂点を１つ対応付けて記録したテーブルである。
【００６０】
頂点リンクテーブルの作成は、ポリゴンデータ構造化手段３０が、頂点座標配列データを参照し、各ポリゴンの各頂点について、同一座標となる他のポリゴンの頂点を１つ検出して対応付けて記録することにより作成する。各ポリゴンの各頂点について、同一座標となる頂点が２つ以上存在する場合であっても、当該頂点に属するポリゴンに最も近いポリゴンの頂点の１つだけ検出して記録すればよい。これは同一座標となる頂点の探索の負荷を最小化するためである。同一座標となる頂点の探索順序としては、自身よりも後方側を探索する。頂点座標配列データの最終となるポリゴンまで探索して見つからなかった場合は、同一座標となる頂点が存在しないことを示す“−１”を設定する。同一座標となる頂点が存在しないことを示すことができれば、“−１”以外を設定してもよい。図１２の例では、後方側とはポリゴン番号が増える側を意味する。
【００６１】
図１４は、図１２に示した頂点座標配列データを基に作成された頂点リンクテーブルを示す図である。図１４に示すように、頂点リンクテーブルはポリゴン単位で記録されている。各ポリゴン単位で記録された頂点のうち上段がリンク元、下段がリンク先を示している。例えば、ポリゴンＰ１の３つの頂点Ｖ１ａ，Ｖ１ｂ，Ｖ１ｃをリンク元として、それぞれ頂点Ｖ２ａ，Ｖ２ｃ，Ｖ３ｃがリンク先として対応付けられている。図１１に示したように、頂点Ｖ１ａ（図１１では“Ｄ”とも表記）と同一座標には、頂点Ｖ２ａ以外にも、Ｖ４ｂ，Ｖ５ｃ，Ｖ６ｃ，Ｖ７ｃが存在しているが、頂点リンクテーブルには１つだけ記録されるため図１４では、頂点Ｖ１ａを含むポリゴンＰ１に最も近いポリゴンＰ２に含まれる頂点Ｖ２ａのみとなっている。また、頂点Ｖ２ｃ（図１１では“Ｂ”とも表記）と同一座標には、頂点Ｖ１ｂが存在しているが、頂点Ｖ２ｃ自身よりも後方側であるため、探索では検出されず、“−１”が記録されている。
【００６２】
頂点リンクテーブルを作成せず、ポリゴンモデルの頂点座標配列データを用いて直接ステップＳ２２以降の処理を行うことも可能であるが、Ｎ個のポリゴンを１／１０に減らそうとすると、削除対象となるポリゴンの探索には、Ｎの２乗に比例して処理負荷が増える。本実施形態のように、頂点リンクテーブルを用いることによりＮに比例した処理負荷に減らすことができる。
【００６３】
頂点リンクテーブルが作成されたら、ポリゴンモデル構造化手段３０が、ポリゴンモデルのデータの構造化を行う（ステップＳ２２）。ポリゴンモデルの構造化とは、頂点リンクテーブルを用いて、頂点構成テーブルおよび頂点座標テーブルを作成することにより、ポリゴンモデルをより扱い易い構造に組み替えることを意味する。まず、頂点リンクテーブルの各頂点について、同一座標を共有する頂点である共有頂点を探索する。そして、リンク先が“−１”になる頂点に到達したら、先頭の頂点に共有頂点ＩＤを付与して頂点座標テーブルに記録するとともに、頂点リンクテーブルの各共有頂点の頂点番号に代えて共有頂点ＩＤを記録する。共有頂点ＩＤとは、同一座標値の頂点に対して同一値となる識別情報である。
【００６４】
図１４に示した頂点リンクテーブルにおいてポリゴンＰ１の頂点Ｖ１ａから共有頂点を探索する場合、頂点Ｖ１ａのリンク先が頂点Ｖ２ａとなっているので、ポリゴンＰ２の欄を参照する。すると、頂点Ｖ２ａのリンク先が頂点Ｖ４ｂとなっているので、ポリゴンＰ４の欄を参照する。さらに、頂点Ｖ４ｂのリンク先が頂点Ｖ５ｃとなっているので、ポリゴンＰ５の欄を参照する。また、頂点Ｖ５ｃのリンク先が頂点Ｖ６ｃとなっているので、ポリゴンＰ６の欄を参照する。また、頂点Ｖ６ｃのリンク先が頂点Ｖ７ｃとなっているので、ポリゴンＰ７の欄を参照する。頂点Ｖ７ｃのリンク先が“−１”となっているので、頂点Ｖ１ａの共有頂点の探索はここで終了となる。
【００６５】
探索の結果、頂点Ｖ１ａの共有頂点は、頂点Ｖ２ａ，Ｖ４ｂ，Ｖ５ｃ，Ｖ６ｃ，Ｖ７ｃであるので、リンク元として各共有頂点が記録されている箇所に共有頂点を識別する識別情報である共有頂点ＩＤを記録する。これにより頂点リンクテーブルが更新される。さらに、共有頂点ＩＤと頂点Ｖ１ａの座標値を対応付けて頂点座標テーブルに記録する。更新された頂点リンクテーブル、および得られた頂点座標テーブルを図１５に示す。図１５の例では、共有頂点ＩＤとして“０”が付与され、更新された頂点リンクテーブルにおいては、探索元の頂点Ｖ１ａと探索により検出された頂点Ｖ２ａ，Ｖ４ｂ，Ｖ５ｃ，Ｖ６ｃ，Ｖ７ｃのリンク元としての箇所に共有頂点ＩＤとして“０”が記録される。そして、頂点座標テーブルにおいては、共有頂点ＩＤである“０”に対応付けて探索起点の頂点Ｖ１ａの座標値が記録される。
【００６６】
他の各頂点についても同様にして、同一座標を共有する頂点である共有頂点を探索していく。全ての頂点について、探索を行った結果、図１６に示すような更新された頂点リンクテーブル、頂点座標テーブルが得られる。
【００６７】
次に、頂点重複テーブル定義手段４０が、頂点重複テーブルを初期化する（ステップＳ２３）。頂点重複テーブルは、共有頂点ＩＤと重複先を対応付けたテーブルであり、初期値として、重複先がないことを示す“−１”が設定される。重複先がないことを示すことができれば、初期値として、“−１”以外を設定してもよい。図１７に、頂点重複テーブルの初期化時点における頂点構成テーブル、頂点座標テーブル、頂点重複テーブルを示す。頂点構成テーブルは、更新された頂点リンクテーブルの各ポリゴンにおけるリンク元のみを抽出したテーブルである。
【００６８】
頂点重複テーブルの初期化が行われたら、削除対象ポリゴンを設定し、頂点座標テーブルおよび頂点重複テーブルの更新を行う（ステップＳ２４）。まず、削除対象ポリゴン設定手段５０が、削除対象ポリゴンを設定する。削除対象ポリゴンの設定は、様々な手法で行うことができる。例えば、頂点構成テーブルに記録されたポリゴンから所定の間隔で間引くように設定することができる。例えば、４個ごとに間引く指定がなされている場合、４つの間隔で１つ間引く。すなわち３つ間を空けて１つ削除する設定を行う。ここでは、図１８に示すように、削除対象ポリゴン設定手段５０が、ポリゴンＰ６とポリゴンＰ１６の２つのポリゴンを削除対象ポリゴンとして設定した場合を例にとって説明する。この例は、１０個ごとに間引く指定がなされている場合に対応する。この場合、削除対象ポリゴン設定手段５０は、ポリゴンＰ６から９個間を空けてポリゴンＰ１６を削除する設定を行う。図１８において、Ｏ、ＰはそれぞれポリゴンＰ６、ポリゴンＰ１６の３頂点の平均座標を有する平均点を示している。削除対象ポリゴン設定手段５０は、設定された削除対象ポリゴンを頂点構成テーブルから削除する。具体的には、図１９に示すように、頂点構成テーブルからポリゴンＰ６の頂点構成を削除する。
【００６９】
続いて、頂点座標テーブル更新手段６０が、削除された頂点構成に含まれていた共有頂点ＩＤの内容を変更することにより頂点座標テーブルを更新する。具体的には、削除された頂点構成に含まれていた全ての共有頂点ＩＤの平均座標を算出し、平均座標をもつ平均点を求める。そして、削除された頂点構成に含まれていた共有頂点のうち１つを代表頂点とし、代表頂点の共有頂点ＩＤの座標値を平均座標の値で更新する。代表頂点は、削除された頂点構成に含まれていた共有頂点のいずれとしてもよいが、共有頂点ＩＤが最小の値とすることが好ましい。特に、共有頂点ＩＤが数字のみの場合、効率的に処理を行うことが可能となる。そして、他の共有頂点ＩＤの頂点座標を頂点座標テーブルから削除する。この結果、図１９に示すように、頂点座標テーブルの共有頂点ＩＤ“０”の頂点座標として、平均点Ｏを示す平均座標値（Ｘｏ，Ｙｏ，Ｚｏ）が記録され、共有頂点ＩＤ“６”“７”の頂点座標としてＮＵＬＬ値（図では空白）が記録される。
【００７０】
次に、頂点重複テーブル更新手段７０が、代表頂点以外の共有頂点ＩＤの重複先を代表頂点の共有頂点ＩＤに設定する。代表頂点の共有頂点ＩＤが“０”で、他の共有頂点の共有頂点ＩＤが“６”“７”である場合、図１９に示すように、頂点重複テーブルの共有頂点ＩＤ“６”“７”の重複先として、それぞれ“０”が記録される。
【００７１】
図２０〜図２２を用いて、２つ目の削除対象ポリゴンであるポリゴンＰ１６を削除する場合について説明する。ポリゴンＰ６の場合と同様に、まず、削除対象ポリゴン設定手段５０が、頂点構成テーブルから削除対象ポリゴンＰ１６を削除する。具体的には、図２０に示すように、頂点構成テーブルからポリゴンＰ１６の頂点構成を削除する。
【００７２】
続いて、頂点座標テーブル更新手段６０が、削除されたポリゴンＰ１６の頂点構成に含まれていた全ての共有頂点ＩＤの平均座標を算出し、平均座標をもつ平均点を求める。そして、削除された頂点構成に含まれていた共有頂点ＩＤのうち１つの共有頂点ＩＤを代表頂点の共有頂点ＩＤとして“９”の座標値を平均座標の値で更新する。そして、他の共有頂点ＩＤ“１０”“１３”の頂点座標を頂点座標テーブルから削除する。この結果、図２０に示すように、頂点座標テーブルの共有頂点ＩＤ“９”の頂点座標として、平均点Ｐを示す共有頂点ＩＤの平均座標値（Ｘｐ，Ｙｐ，Ｚｐ）が記録され、共有頂点ＩＤ“１０”“１３”の頂点座標としてＮＵＬＬ値（図では空白）が記録される。
【００７３】
次に、頂点重複テーブル更新手段７０が、代表頂点以外の共有頂点ＩＤの重複先を代表頂点の共有頂点ＩＤに設定する。代表頂点の共有頂点ＩＤが“９”で、他の共有頂点の共有頂点ＩＤが“１０”“１３”である場合、図２０に示すように、頂点重複テーブルの共有頂点ＩＤ“１０”“１３”の重複先として、それぞれ“９”が記録される。
【００７４】
２つの削除対象ポリゴンが頂点構成テーブルから削除されたら、頂点構成テーブル更新手段８０が、頂点重複テーブルを参照し、頂点構成テーブルの頂点構成の中で頂点重複テーブルにおいて重複先が設定されている共有頂点ＩＤを変更する（ステップＳ２５）。具体的には、頂点重複テーブルの重複先が初期値“−１”以外であるものについて、頂点構成テーブル上の共有頂点ＩＤを、重複先の共有頂点ＩＤに変更する。この結果、図２１に示すように、ポリゴンＰ５，Ｐ７，Ｐ８，Ｐ９，Ｐ１０，Ｐ１１，Ｐ１５，Ｐ１７，Ｐ１８に対応する共有頂点ＩＤが変更される。
【００７５】
共有頂点ＩＤの変更後、頂点構成テーブル更新手段８０は、頂点構成に同一の値をもつ共有頂点ＩＤが複数含まれるポリゴンを頂点構成テーブルから削除する。これは、ポリゴンが三角形である場合、３つの頂点中２つ以上の頂点が同一であれば、ポリゴンとして成り立たないためである。図２１の例では、頂点構成テーブルにおいて、ポリゴンＰ５，Ｐ７，Ｐ１０，Ｐ１１，Ｐ１５，Ｐ１７の頂点構成に同一共有頂点ＩＤが含まれている。例えば、ポリゴンＰ５の頂点構成には、共有頂点ＩＤ“０”が２つ含まれている。頂点構成に同一共有頂点ＩＤが複数含まれるポリゴンを頂点構成テーブルから削除した結果、頂点構成テーブルは図２２に示すような状態に更新される。図２２に示すように、当初の頂点構成テーブルからはポリゴンＰ５，Ｐ６，Ｐ７，Ｐ１０，Ｐ１１，Ｐ１５，Ｐ１６，Ｐ１７が削除されている。
【００７６】
頂点構成テーブルが更新されたら、ポリゴンモデル更新手段９０が、頂点座標配列データを更新する（ステップＳ２６）。具体的には、頂点座標テーブルを参照して、頂点構成テーブルの各共有頂点ＩＤを頂点座標に置き換える。図２２に示した頂点構成テーブル、図２２に示した頂点座標テーブルからは図２３に示したような頂点座標配列データが得られることになる。これを図１２に示した元の頂点座標配列データと置き換える。この結果、図１８に示したポリゴン群は、図２４に示すようなポリゴン群に変更されることになる。図１８に示したポリゴン群において設定された削除対象ポリゴンＰ６，Ｐ１６だけでなく、ポリゴンＰ５，Ｐ７，Ｐ１１，Ｐ１５，Ｐ１６，Ｐ１７が削除されていることがわかる。
【００７７】
頂点座標配列データが更新されたら、制御手段１０が、削減後の全ポリゴン数が、設定された目標値以下となっているか否かを判定する（ステップＳ２７）。目標値としては、事前に任意の値を設定することができる。判定の結果、全ポリゴン数が目標値以下となっていない場合は、ステップＳ２４に戻って、削除対象ポリゴン設定手段５０が、残っているポリゴンの中から、他のポリゴンを削除対象ポリゴンとして設定する。ステップＳ２７における判定の結果、全ポリゴン数が目標値以下である場合は、ポリゴン削減処理を終了する。図１３のフローチャートに従った処理を実行することにより、各グループについて設定された目標値以下になるように、ポリゴン数が削減されることになる。ポリゴンモデルの構造化処理が行われていなければ、削除対象ポリゴンの３つの補正対象頂点と同一座標となる共有頂点の探索に大きな処理負荷を要することになる。ポリゴンモデルの構造化処理を行うことにより、処理負荷を大幅に削減することが可能となる。
【００７８】
＜２．４．２．稜線単位削除＞
次に、稜線単位削除について説明する。ここで、稜線とは、ポリゴンの辺を意味する。図２５は、処理対象とするポリゴン群の一例を示す図である。図２５に示したポリゴン群は、図１８に示したものと同一のポリゴン構成となっており、ポリゴンを構成する全ての頂点の平均点でなく、削除対象辺の中点をＯ，Ｐとしている点のみが異なっている。稜線単位削除の場合も、ポリゴン単位削除の場合と同様、頂点座標配列データは、図１２に示したようなものとなっている。
【００７９】
上記のような規則に従って作成されるため、頂点座標配列データにおいては、同一座標の頂点が複数箇所に記録されることになる。例えば、図１１、図１２に示した頂点Ｄは、６つのポリゴンＰ１，Ｐ２，Ｐ４，Ｐ５，Ｐ６，Ｐ７に共有されるため、座標“（Ｘｄ，Ｙｄ，Ｚｄ）”は、頂点Ｖ１ａ，Ｖ２ａ，Ｖ４ｂ，Ｖ５ｃ，Ｖ６ｃ，Ｖ７ｃとして６箇所に記録される。
【００８０】
稜線単位削除の場合におけるポリゴン削減処理の概要は、図１３に示したフローチャートと同様であり、ポリゴン単位削除の場合と比較して、ステップＳ２４の処理が大きく異なるだけである。まず、ポリゴン単位削除の場合と同様に、ポリゴンモデル構造化手段３０が、頂点リンクテーブルを作成する（ステップＳ２１）。
【００８１】
図１３に示したポリゴン座標配列データから図１４に示したような頂点リンクテーブルが得られることになる。頂点リンクテーブルが作成されたら、ポリゴンモデル構造化手段３０が、ポリゴン構造化テーブルの作成を行う（ステップＳ２２）。具体的には、ポリゴン単位削除の場合と同様にして、頂点リンクテーブルを用いて、頂点構成テーブルおよび頂点座標テーブルを作成する。
【００８２】
さらに、頂点重複テーブル定義手段４０が、ポリゴン単位削除の場合と同様にして頂点重複テーブルを初期化する（ステップＳ２３）。この結果。図１７に示したような、頂点構成テーブル、頂点座標テーブル、頂点重複テーブルが得られる。
【００８３】
頂点重複テーブルの初期化が行われたら、削除対象ポリゴンを設定し、頂点座標テーブルおよび頂点重複テーブルの更新を行う（ステップＳ２４）。まず、削除対象ポリゴン設定手段５０が、ポリゴン単位削除の場合と同様にして削除対象ポリゴンを設定する。ここでは、図２５に示すように、ポリゴンＰ６とポリゴンＰ１６の２つのポリゴンが削除対象ポリゴンとして設定されている場合を例にとって説明する。ここからは、ポリゴン単位削除の場合と異なる処理が行われる。削除対象ポリゴンが設定されると、さらに、削除対象ポリゴン設定手段５０は、削除対象ポリゴンの１辺を削除対象辺として選定する。削除対象辺の選定は、様々な手法により行うことができるが、本実施形態では、削除対象ポリゴンを構成する全ての辺のうち最短のものを選定している。図２５において、Ｏ、ＰはそれぞれポリゴンＰ６、ポリゴンＰ１６の削除対象辺の両端２頂点の平均座標を有する平均点（削除対象辺の中点）を示している。次に、削除対象ポリゴン設定手段５０は、頂点構成テーブルから削除対象ポリゴンを削除する。具体的には、図２６に示すように、頂点構成テーブルからポリゴンＰ６の頂点構成を削除する。
【００８４】
続いて、頂点座標テーブル更新手段６０が、削除された頂点構成に含まれていた共有頂点ＩＤのうち、削除対象辺の両端の２頂点の共有頂点ＩＤの内容を変更することにより頂点座標テーブルを更新する。具体的には、削除された頂点構成に含まれていた共有頂点ＩＤの平均座標を算出し、平均座標をもつ平均点を求める。削除対象辺の２頂点の平均点は、削除対象辺の中点でもある。そして、削除された頂点構成に含まれていた共有頂点ＩＤのうち１つの共有頂点ＩＤを代表頂点として、代表頂点の共有頂点ＩＤの座標値を平均座標の値で更新する。そして、他の共有頂点ＩＤの頂点座標を頂点座標テーブルから削除する。この結果、図２６に示すように、頂点座標テーブルにおいて代表頂点である共有頂点ＩＤ“０”の頂点座標として、平均点Ｏを示す平均座標値（Ｘｏ，Ｙｏ，Ｚｏ）が記録され、もう一方の共有頂点ＩＤ“６”の頂点座標としてＮＵＬＬ値（図では空白）が記録される。
【００８５】
次に、頂点重複テーブル更新手段７０が、代表頂点以外の共有頂点ＩＤの重複先を代表頂点の共有頂点ＩＤに設定する。代表頂点の頂点ＩＤが“０”で、他の共有頂点の共有頂点ＩＤが“６”である場合、図２６に示すように、頂点重複テーブルの共有頂点ＩＤ“６”の重複先として“０”が記録される。
【００８６】
図２７〜図２９を用いて、２つ目の削除対象ポリゴンであるポリゴンＰ１６を削除する場合について説明する。ポリゴンＰ６の場合と同様に、まず、削除対象ポリゴン設定手段５０が、頂点構成テーブルから削除対象ポリゴンＰ１６を削除する。具体的には、図２７に示すように、頂点構成テーブルからポリゴンＰ１６の頂点構成を削除する。
【００８７】
続いて、頂点座標テーブル更新手段６０が、削除されたポリゴンＰ１６の頂点構成に含まれていた共有頂点ＩＤのうち、削除対象辺の両端の２頂点の共有頂点ＩＤの平均座標を算出し、平均座標をもつ平均点を求める。そして、削除された頂点構成に含まれていた共有頂点ＩＤのうち、削除対象辺の１つの頂点を代表頂点として代表頂点である共有頂点ＩＤ“９”の座標値を平均座標の値で更新する。そして、他の共有頂点ＩＤ“１０”の頂点座標を頂点座標テーブルから削除する。この結果、図２７に示すように、頂点座標テーブルの共有頂点ＩＤ“９”の頂点座標として、平均点Ｐを示す共有頂点ＩＤの平均座標値（Ｘｐ，Ｙｐ，Ｚｐ）が記録され、共有頂点ＩＤ“１０”の頂点座標としてＮＵＬＬ値（図では空白）が記録される。
【００８８】
次に、頂点重複テーブル更新手段７０が、代表頂点以外の共有頂点ＩＤの重複先を代表頂点の共有頂点ＩＤに設定する。代表頂点の頂点ＩＤが“９”で、他の共有頂点の共有頂点ＩＤが“１０”である場合、図２７に示すように、頂点重複テーブルの共有頂点ＩＤ“１０”の重複先として“９”が記録される。
【００８９】
２つの削除対象ポリゴンが頂点構成テーブルから削除されたら、頂点構成テーブル更新手段８０が、頂点重複テーブルを参照し、頂点構成テーブルの頂点構成の中で、頂点重複テーブルに重複先が設定されている各共有頂点ＩＤを変更する（ステップＳ２５）。具体的には、頂点重複テーブルの重複先が初期値“−１”以外であるものについて、頂点構成テーブル上の共有頂点ＩＤを、重複先の共有頂点ＩＤに変更する。この結果、図２８に示すように、ポリゴンＰ５，Ｐ９，Ｐ１０，Ｐ１１，Ｐ１７に対応する共有頂点ＩＤが変更される。
【００９０】
共有頂点ＩＤの変更後、頂点構成テーブル更新手段は、頂点構成に同一の値をもつ共有頂点ＩＤが複数含まれるポリゴンを頂点構成テーブルから削除する。これは、ポリゴンが三角形である場合、３つの頂点中２つ以上の頂点が同一であれば、ポリゴンとして成り立たないためである。図２８の例では、頂点構成テーブルにおいて、ポリゴンＰ５，Ｐ１０の頂点構成に同一の値をもつ共有頂点ＩＤが含まれている。例えば、ポリゴンＰ５の頂点構成には、共有頂点ＩＤ“０”が２つ含まれている。頂点構成に同一の値をもつ共有頂点ＩＤが複数含まれるポリゴンを頂点構成テーブルから削除した結果、頂点構成テーブルは図２９に示すような状態に更新される。図２９に示すように、当初の頂点構成テーブルからはポリゴンＰ５，Ｐ６，Ｐ１０，Ｐ１６が削除されている。
【００９１】
頂点構成テーブルが更新されたら、ポリゴンモデル更新手段９０が、頂点座標配列データを更新する（ステップＳ２６）。具体的には、頂点座標テーブルを参照して、頂点構成テーブルの各共有頂点ＩＤを頂点座標に置き換える。図２９に示した頂点構成テーブル、図２９に示した頂点座標テーブルからは図３０に示したような頂点座標配列データが得られることになる。これを図１２に示した元の頂点座標配列データと置き換える。この結果、図２５に示したポリゴン群は、図３１に示すようなポリゴン群に変更されることになる。図２５に示したポリゴン群において設定された削除対象ポリゴンＰ６，Ｐ１６だけでなく、ポリゴンＰ５，Ｐ１６が削除されていることがわかる。
【００９２】
頂点座標配列データが更新されたら、制御手段１０が、削減後の全ポリゴン数が、設定された目標値以下となっているか否かを判定する（ステップＳ２７）。目標値としては、事前に任意の値を設定することができる。判定の結果、全ポリゴン数が目標値以下となっていない場合は、ステップＳ２４に戻って、削除対象ポリゴン設定手段５０が、残っているポリゴンの中から、他のポリゴンを削除対象ポリゴンとして選定する。ステップＳ２７における判定の結果、全ポリゴン数が目標値以下である場合は、ポリゴン削減処理を終了する。図１３のフローチャートに従った処理を実行することにより、各グループについて設定された目標値以下になるように、ポリゴン数が削減されることになる。ポリゴンモデルの構造化処理が行われていなければ、削除対象ポリゴンの削除対象辺の２つの補正対象頂点と同一座標となる共有頂点の探索に大きな処理負荷を要することになる。ポリゴンモデルの構造化処理を行うことにより、処理負荷を大幅に削減することが可能となる。
【００９３】
＜２．５．小体積グループ削除処理＞
次に、ステップＳ４０におけるグループ合成手段１００による隔離された小体積グループの削除処理について説明する。ここで、隔離された小体積グループの削除処理の説明に先立ち、隔離された小体積グループの削除処理を行う理由について説明しておく。図３２は、ポリゴン削減処理により生じる問題を説明するための図である。図３２（ａ）は、ステップＳ１０のグループ分類処理を終えた直後の２グループのポリゴン群を示している。図３２（ａ）の例では、頂点Ｄ、Ｅ、Ｋを含む左側のグループと、頂点Ｄ’、Ｅ’、Ｋ’を含む右側のグループが存在する。頂点ＤとＤ’、頂点ＥとＥ’、頂点ＫとＫ’がそれぞれ３Ｄプリンタの解像度以下である場合、この２グループのポリゴン群を３Ｄプリンタで出力すると、頂点ＤとＤ’、頂点ＥとＥ’、頂点ＫとＫ’は樹脂等により連結され、２グループは連結した物体として出力される。すなわち、２グループは物理的には接着されている。
【００９４】
図３２（ａ）に示した右側のグループのポリゴン群に対して、ステップＳ２０におけるポリゴン削減処理を実行すると、図３２（ｂ）に示すように、ポリゴンＥ’ＦＫ’が削除対象ポリゴンとして選定される。さらに、図３２（ｃ）に示すように、削除対象ポリゴンＥ’ＦＫ’の最短辺Ｅ’Ｆが削除対象辺として選定され、辺Ｅ’Ｆの中点Ｏが算出される。そして、図３２（ｄ）に示すように、削除対象ポリゴンＥ’ＦＫ’と、削除頂点共有ポリゴンＤ’Ｅ’Ｆが削除される。
【００９５】
図３２（ａ）と図３２（ｄ）を比較するとわかるように、左右の２つのグループは、ポリゴン削減処理前に比べて、ポリゴン削減処理後には、より離れてしまっている。図３２（ｄ）に示した２グループの距離が、３Ｄプリンタの解像度を超えると、２グループのポリゴン群を３Ｄプリンタで出力した場合、２グループは別の物体として出力される。２つのグループがともに大きな物体となれば、問題はない。しかし、一つが非常に小さな物体となる場合、例えば、一方のグループが本体であって、他方のグループが本体に付属するヒゲのようなものである場合、本体と別に出力されたヒゲは、３Ｄプリンタ内に紛れ込み、機械詰まり等の問題を引き起こす恐れがある。このような問題を除去するため、上述のヒゲのような隔離された小体積グループの削除処理を行うのである。
【００９６】
図３３は、グループ合成手段１００による隔離された小体積グループの削除処理（ステップＳ４０）の詳細を示すフローチャートである。グループ合成手段１００は、まず、グループごとに全ポリゴンの全頂点を対象として、Ｘ、Ｙ、Ｚぞれぞれの方向の最大値および最小値を算出する（ステップＳ４１）。この結果、グループｇに対して、最小値Ｘｍｉｎ（ｇ）、最大値Ｘｍａｘ（ｇ）、最小値Ｙｍｉｎ（ｇ）、最大値Ｙｍａｘ（ｇ）、最小値Ｚｍｉｎ（ｇ）、最大値Ｚｍａｘ（ｇ）が得られる。次に、グループ合成手段１００は、グループごとに外接直方体の体積を算出する（ステップＳ４２）。具体的には、以下の〔数式１〕に従った処理を実行することにより、グループｇの外接直方体の体積Ｖ（ｇ）を算出する。
【００９７】
〔数式１〕
Ｖ（ｇ）＝（Ｘｍａｘ（ｇ）−Ｘｍｉｎ（ｇ））×（Ｙｍａｘ（ｇ）−Ｙｍｉｎ（ｇ））×（Ｚｍａｘ（ｇ）−Ｚｍｉｎ（ｇ））
【００９８】
グループ合成手段１００は、全グループに対してステップＳ４１、Ｓ４２の処理を実行する。これにより、全グループについて、外接直方体の体積が得られる。次に、グループ合成手段１００は、全グループの中で外接直方体の体積が最小となるグループを特定する（ステップＳ４３）。そして、グループ合成手段１００は、特定したグループと他の全てのグループとの最小間隔を算出する（ステップＳ４４）。ステップＳ４４における最小間隔の算出処理の詳細については後述する。
【００９９】
続いて、グループ合成手段１００は、ステップＳ４４において算出された最小間隔が所定のしきい値以上か否かを判定する（ステップＳ４５）。最小間隔と比較するための所定のしきい値としては、３Ｄプリンタ出力時に０．２ｍｍに相当する数値とすることが好ましい。判定の結果、最小間隔が所定のしきい値以上である場合は、体積最小のグループが、最も近いグループとも所定の距離以上離れていることになるので、グループ合成手段１００は、体積最小のグループを削除する処理を行う（ステップＳ４６）。ステップＳ４５における判定の結果、最小間隔が所定のしきい値未満である場合は、体積最小のグループが、最も近いグループと３Ｄプリンタの解像度以下に近接していることになるので、グループ合成手段１００は、体積最小のグループを削除する処理を行わない。
【０１００】
ステップＳ４６におけるグループの削除を行った場合、削除を行わなかった場合のいずれにおいても、そのグループについては処理済みとする。そして、ステップＳ４３に戻って、未処理のグループの中で外接直方体の体積が最小となるグループを特定する。ステップＳ４３〜ステップＳ４６の処理を繰り返し、全てのグループに対する処理を終えたら、隔離された小体積グループの削除処理を終了する。
【０１０１】
ステップＳ４４における最小間隔の算出処理の詳細について説明する。図３４は、図３３のステップＳ４４における最小間隔の算出処理の詳細を示すフローチャートである。グループ合成手段１００は、初期値として、最小間隔を示す変数ｄｍｉｎに所定以上の値を設定する。ｄｍｉｎに与える初期値としては、グループ間の最小間隔としてあり得ない大きな値を設定しておけばよい。そして、グループ合成手段１００は、全グループの中から、グループｇより体積が大きい１つのグループｈを抽出する（ステップＳ４７）。この結果、グループｈについて、最小値Ｘｍｉｎ（ｈ）、最大値Ｘｍａｘ（ｈ）、最小値Ｙｍｉｎ（ｈ）、最大値Ｙｍａｘ（ｈ）、最小値Ｚｍｉｎ（ｈ）、最大値Ｚｍａｘ（ｈ）が得られる。次に、グループ合成手段１００は、Ｘ、Ｙ、Ｚの各方向別に２グループ間の差分の最小値を算出する（ステップＳ４８）。具体的には、以下の〔数式２〕に従った処理を実行することにより、Ｘ方向の差分の最小値ｄｘ、Ｙ方向の差分の最小値ｄｙ、Ｚ方向の差分の最小値ｄｚを算出する。
【０１０２】
〔数式２〕
ｄｘ＝Ｍｉｎ｛｜Ｘｍａｘ（ｇ）−Ｘｍｉｎ（ｈ）｜，｜Ｘｍｉｎ（ｇ）−Ｘｍａｘ（ｈ）｜｝
ｄｙ＝Ｍｉｎ｛｜Ｙｍａｘ（ｇ）−Ｙｍｉｎ（ｈ）｜，｜Ｙｍｉｎ（ｇ）−Ｙｍａｘ（ｈ）｜｝
ｄｚ＝Ｍｉｎ｛｜Ｚｍａｘ（ｇ）−Ｚｍｉｎ（ｈ）｜，｜Ｚｍｉｎ（ｇ）−Ｚｍａｘ（ｈ）｜｝
【０１０３】
続いて、グループ合成手段１００は、算出された方向別最小値のうち最大のものをグループ間最小値とし、グループ間最小値を、既に処理済みの他のグループ間における全グループ間最小値と比較し、小さい方を全グループ間最小値とする処理を行う（ステップＳ４９）。具体的には、ステップＳ４８において算出された３つの方向別最小値ｄｘ、ｄｙ、ｄｚのうち、最大の値をとるグループ間最小値Ｍａｘ（ｄｘ、ｄｙ、ｄｚ）とｄｍｉｎを比較し、Ｍａｘ（ｄｘ、ｄｙ、ｄｚ）＜ｄｍｉｎの場合、ｄｍｉｎ＝Ｍａｘ（ｄｘ、ｄｙ、ｄｚ）とする。これにより、ｄｍｉｎには、グループ間最小値の中で最小の値となる全グループ間最小値が記録されることになる。
【０１０４】
ステップＳ４７、Ｓ４８、Ｓ４９の処理を繰り返して実行し、グループｇより体積が大きい全てのグループに対する処理を終えたら、図３４に示した最小間隔の算出処理を終了し、図３３のステップＳ４５に進んで、最小間隔ｄｍｉｎとしきい値との比較を行うことになる。
【０１０５】
＜２．６．ポリゴンモデルの合成＞
図９の処理概要に示したように、ステップＳ５０においては、グループ合成手段１００が、全グループのポリゴンモデルの合成を行って更新された領域別ポリゴンモデルを得る。また、ステップＳ７０においては、ポリゴンモデル合成手段１１０が、全領域の領域別ポリゴンモデルの合成を行って合成ポリゴンモデルを得る。いずれの合成処理も、ヘッダ部を除く領域別ポリゴンモデルを単純に結合し、ヘッダ部に合算されたポリゴン数を記録することにより行われる（ただし、これはバイナリ形式のＳＴＬフォーマットの場合で、ＡＳＣＩＩ形式のＳＴＬフォーマットではヘッダ部を除く領域別ポリゴンモデルを単純に結合するだけである）。合成ポリゴンモデル記憶手段１３０に記憶された合成ポリゴンモデルを３Ｄプリンタ７に出力することにより、３Ｄプリンタ７は効率的に立体物を造形することができる。造形された立体物については、ほとんど劣化は見られなかった。
【０１０６】
＜３．ポリゴン削減事例＞
ポリゴン削減について、ポリゴンモデルの構造化を行わない従来方式と比較した２つの事例について説明する。ポリゴンモデルの構造化を行わない場合、Ｎ個のポリゴンを１／２に減らそうとすると、Ｎ／２×Ｎ回の探索を行う必要があり、Ｎの２乗に比例して処理負荷が増える。本発明では、ポリゴンモデルの構造化を行うことによりＮに比例した処理負荷に減らすことができる。図３５、図３６は第１の事例を示している。図３５（ａ）は、オリジナル（ポリゴン削減前）のポリゴンモデルのレンダリング像であり、図３５（ｂ）は、従来方式によるポリゴン削減後のポリゴンモデルのレンダリング像である。また、図３６（ａ）は、上記実施形態におけるポリゴン単位削除方式によるポリゴン削減後のポリゴンモデルのレンダリング像であり、図３６（ｂ）は、参考までにポリゴンを削除したのみで隣接するポリゴンの補正を行わない場合、すなわち、削除されたポリゴンが存在した箇所に対する補間を行わなかった場合のポリゴンモデルのレンダリング像である（この状態で３Ｄプリンタ出力を行うとエラーになる）。
【０１０７】
図３５（ａ）に示したオリジナルのポリゴンモデルは、２４９８５４ポリゴンであり、図３５（ｂ）、図３６（ａ）に示したポリゴン削減後のポリゴンモデルはいずれも７８３２０ポリゴンであり、１／３に削減されている。また、図３６（ｂ）に示したポリゴン削減後のポリゴンモデルはいずれも８３２８４ポリゴンであり、１／３に削減されている。同一機種のコンピュータ（汎用Windows（登録商標）パソコン(Intel Core i7-4700MQ 2.4GHz, Memory:8Gbytes）をハードウェアとして、各プログラムを組み込んだ立体物造形用データ削減装置による処理の結果、図３５（ｂ）に示した従来方式は、所要時間２分５１秒であったのに対して、図３６（ａ）に示したポリゴン単位削除方式は、所要時間１分７秒であり、図３６（ｂ）に示したポリゴンを削除したのみで隣接するポリゴンの補正を行わない場合は、所要時間１秒未満であった。
【０１０８】
図３７、図３８は第２の事例を示している。図３７（ａ）は、オリジナル（ポリゴン削減前）のポリゴンモデルのレンダリング像であり、図３７（ｂ）は、従来方式によるポリゴン削減後のポリゴンモデルのレンダリング像である。また、図３８（ａ）は、上記実施形態におけるポリゴン単位削除方式によるポリゴン削減後のポリゴンモデルのレンダリング像であり、図３８（ｂ）は、参考までにポリゴンを削除したのみで隣接するポリゴンの補正を行わない場合、すなわち、削除されたポリゴンが存在した箇所に対する補間を行わなかった場合のポリゴンモデルのレンダリング像である（同様に、この状態で３Ｄプリンタ出力を行うとエラーになる）。
【０１０９】
図３７（ａ）に示したオリジナルのポリゴンモデルは、３４４４５８２ポリゴンであり、図３７（ｂ）、図３８（ａ）に示したポリゴン削減後のポリゴンモデルはいずれも１０８４２５８ポリゴンであり、１／３に削減されている。また、図３８（ｂ）に示したポリゴン削減後のポリゴンモデルはいずれも１１４８１９４ポリゴンであり、１／３に削減されている。同一機種のコンピュータ（Intel Core i7-4700MQ 2.4GHz,  Memory:8Gbytes）をハードウェアとして、各プログラムを組み込んだ立体物造形用データ削減装置による処理の結果、図３７（ｂ）に示した従来方式は、所要時間９時間５１分であったのに対して、図３８（ａ）に示したポリゴン単位削除方式は、所要時間３時間４０分であり、図３８（ｂ）に示したポリゴンを削除したのみで隣接するポリゴンの補正を行わない場合は、所要時間４秒であった。
【０１１０】
＜４．第２の実施形態＞
上記実施形態に係る立体物造形用データ削減装置により、所定間隔で間引くようにしてポリゴンを削減することができる。さらに、ポリゴンモデルの具体的な構造に合わせて更なる削除を行うこと、即ち追加削除を行うことにより、品質の劣化を抑えながらデータ量をさらに削減することが可能となる。次に、このような追加削除を行う場合の第２の実施形態について説明する。
【０１１１】
＜４．１．装置構成＞
図３９は、本発明第２の実施形態に係る立体物造形用データ削減装置を示す機能ブロック図である。第２の実施形態に係る立体物造形用データ削減装置のハードウェア構成は、図１に示したものと同様である。図３９において、図２に示した構成と同様の機能をもつものについては、同一符号を付して説明を省略する。追加削除対象ポリゴン選定手段１４０は、ポリゴンモデルを構成する全てのポリゴンに対して、面積と周長を算出し、面積と周長の積が最小となるポリゴンを追加削除対象ポリゴンとして選定する。追加削除対象辺選定手段１５０は、追加削除対象ポリゴンの各辺の長さを算出し、最も短い辺を追加削除対象辺として選定する。追加削除頂点共有ポリゴン探索手段１６０は、ポリゴンモデルを構成する追加削除対象ポリゴン以外の全てのポリゴンから、追加削除対象辺の２頂点（辺の端点）のいずれか１頂点を共有する追加削除頂点共有ポリゴンを探索する。ポリゴンモデル追加更新手段１７０は、追加削除対象辺の２頂点の双方を共有する追加削除頂点共有ポリゴンを、追加削除対象ポリゴンとともに削除し、追加削除対象辺のいずれか１頂点のみを共有する追加削除頂点共有ポリゴンに対して、共有する１頂点を追加削除対象辺の２頂点の中点の位置に補正する。
【０１１２】
図３９に示した各構成手段は、現実には図１に示したように、コンピュータおよびその周辺機器等のハードウェアに専用のプログラムを搭載することにより実現される。すなわち、コンピュータが、専用のプログラムに従って各手段の内容を実行することになる。なお、本明細書において、コンピュータとは、ＣＰＵ等の演算処理部を有し、データ処理が可能な装置を意味する。
【０１１３】
図１に示した記憶装置３には、ＣＰＵ１を動作させ、コンピュータを、立体物造形用データ最適化装置として機能させるための専用のプログラムが実装されている。この専用のプログラムを実行することにより、ＣＰＵ１は、制御手段１０、グループ分類手段２０、ポリゴンモデル構造化手段３０、頂点重複テーブル定義手段４０、削除対象ポリゴン設定手段５０、頂点座標テーブル更新手段６０、頂点重複テーブル更新手段７０、頂点構成テーブル更新手段８０、ポリゴンモデル更新手段９０、グループ合成手段１００、ポリゴンモデル合成手段１１０、追加削除対象ポリゴン選定手段１４０、追加削除対象辺選定手段１５０、追加削除頂点共有ポリゴン探索手段１６０、ポリゴンモデル追加更新手段１７０、としての機能を実現することになる。また、記憶装置３は、領域別ポリゴンモデル記憶手段１２０、合成ポリゴンモデル記憶手段１３０として機能するだけでなく、立体物造形用データ最適化装置としての処理に必要な様々なデータを記憶する。
【０１１４】
＜４．２．処理動作＞
第２の実施形態に係る立体物造形用データ削減装置では、ポリゴンモデル構造化手段３０〜ポリゴンモデル更新手段９０の処理により、図１３に示したステップＳ２０のポリゴン削減処理を行う。そして、ポリゴンが削減されたポリゴンモデルに対して、追加削除対象ポリゴン選定手段１４０〜ポリゴンモデル追加更新手段１７０が、ポリゴンの追加削除を行う。追加削除対象ポリゴン選定手段１４０〜ポリゴンモデル追加更新手段１７０によるポリゴンの追加削除は、図９に示したステップＳ２０とステップＳ３０の間で行われることになる。
【０１１５】
＜４．３．ポリゴン追加削減処理＞
次に、追加削除対象ポリゴン選定手段１４０、追加削除対象辺選定手段１５０、追加削除頂点共有ポリゴン探索手段１６０、ポリゴンモデル追加更新手段１７０によるポリゴン追加削減処理について説明する。図４０は、ポリゴン追加削減の基本原理を示す図である。ポリゴンモデルは、上述のように、図１２に示されるような空間における三次元の値をもつポリゴン群であるが、図４０の例では、紙面上での説明の便宜上、二次元空間に投影したポリゴン群を示している。図４０（ａ）は、図１８、図２５と同一のポリゴン構成であり、頂点Ａ〜Ｎのみ示したものである。
【０１１６】
図４１は、追加削除対象ポリゴン選定手段１４０、追加削除対象辺選定手段１５０、追加削除頂点共有ポリゴン探索手段１６０、ポリゴンモデル追加更新手段１７０によるポリゴン追加削減処理の詳細を示すフローチャートである。まず、追加削除対象ポリゴン選定手段３０が、ポリゴンモデルを構成する全ポリゴンを対象として、各ポリゴンの面積および周長を算出する（ステップＳ５１）。次に、追加削除対象ポリゴン選定手段３０は、算出された面積と周長を乗じた値が最小となるポリゴンを追加削除対象ポリゴンとして選定する（ステップＳ５２）。図４０の例では、図４０（ｂ）に示すように、３個の頂点Ｅ、Ｊ、Ｋで構成されるポリゴンＥＪＫが追加削除対象ポリゴンとして選定される。
【０１１７】
続いて、追加削除対象辺選定手段４０が追加削除対象ポリゴンの３辺のうち最短の１辺を追加削除対象辺として選定し、選定した追加削除対象辺の中点を算出する（ステップＳ５３）。図４０の例では、図４０（ｃ）に示すように、追加削除対象ポリゴンＥＪＫの辺ＪＫが追加削除対象辺として選定される。さらに、辺ＪＫの中点Ｏが算出される。
【０１１８】
次に、ポリゴンモデル追加更新手段１７０が、追加削除対象ポリゴンを削除する（ステップＳ５４）。これによりポリゴン数が１つ削減されることになる。次に、追加削除頂点共有ポリゴン探索手段１６０が、追加削除対象ポリゴンの追加削除対象辺と頂点を共有していた追加削除頂点共有ポリゴンを順次選定する（ステップＳ５５）。追加削除対象ポリゴンの追加削除対象辺と２頂点を共有（すなわち辺を共有）している追加削除頂点共有ポリゴンが選定された場合には、ポリゴンモデル追加更新手段１７０が、その追加削除頂点共有ポリゴンを削除する（ステップＳ５６）。図４０の例では、３個の頂点Ｊ、Ｋ、Ｎで構成されるポリゴンＪＫＮが削除される。これによりさらにポリゴン数が１つ削減されることになる。追加削除対象ポリゴンの追加削除対象辺と１頂点を共有している追加削除頂点共有ポリゴンが選定された場合には、ポリゴンモデル追加更新手段１７０が、共有される頂点をステップＳ５３で算出された中点に補正し、面積および周長を再算出する（ステップＳ５７）。図４０の例では、図４０（ｃ）と図４０（ｄ）を比較するとわかるように、ポリゴンＥＨＪ→ポリゴンＥＨＯ、ポリゴンＥＦＫ→ポリゴンＥＦＯ、ポリゴンＨＪＭ→ポリゴンＨＯＭ、ポリゴンＪＭＮ→ポリゴンＯＭＮ、ポリゴンＦＫＮ→ポリゴンＦＯＮに変更される。この結果、図４０の例では、図４０（ａ）の時点では、１８個あったポリゴンが、図４０（ｄ）の時点では、１６個に削減される。
【０１１９】
ステップＳ５５〜ステップＳ５７の処理を終えたら、制御手段１０が、削減後の全ポリゴン数が、設定された目標値以下となっているか否かを判定する（ステップＳ５８）。目標値としては、事前に任意の値を設定することができる。判定の結果、全ポリゴン数が目標値以下となっていない場合は、ステップＳ５２に戻って、追加削除対象ポリゴン選定手段３０が、残っているポリゴンの中から、面積と周長を乗じた値が最小となるポリゴンを追加削除対象ポリゴンとして選定する。ステップＳ５８における判定の結果、全ポリゴン数が目標値以下である場合は、ポリゴン追加削減処理を終了する。図４１のフローチャートに従った処理を実行することにより、各グループについて設定された目標値以下になるように、ポリゴン数が削減されることになる。
【０１２０】
追加削除対象ポリゴン選定手段１４０、追加削除対象辺選定手段１５０、追加削除頂点共有ポリゴン探索手段１６０、ポリゴンモデル追加更新手段１７０によるポリゴン追加削減処理を終えたら、図９に示したステップＳ３０に進んで、制御手段１０が、全グループについてポリゴン削減処理が終了したか否かを判定し、以降、第１の実施形態と同様の処理が行われる。
【０１２１】
＜５．変形例等＞
以上、本発明の好適な実施形態について説明したが、本発明は上記実施形態に限定されず、種々の変形が可能である。例えば、上記実施形態では、処理対象のポリゴンを三角形としたが、四角形以上の多角形であってもよい。
【０１２２】
また、上記実施形態では、ポリゴンに対して面積と周長を算出し、面積と周長の積が最小となるポリゴンを削除対象ポリゴンとして選定するようにしたが、周長を用いず面積のみを用いるようにしてもよい。
【０１２３】
また、上記実施形態では、複数のグループの更新されたポリゴンモデルに対して、外接直方体の体積が所定のしきい値未満であるものを削除するようにしたが、削除しないようにすることも可能である。
【０１２４】
また、上記実施形態では、事前に頂点リンクテーブルを作成し、各ポリゴンの各頂点を起点に、頂点リンクテーブルを順次参照しながら、一連の共有頂点を取得するようにしたが、事前に頂点リンクテーブルを作成しないようにすることも可能である。頂点リンクテーブルを作成せず、ポリゴンモデルの頂点座標配列データを用いて直接頂点構成テーブル、頂点座標テーブルを作成するようにしてもよい。
【符号の説明】
【０１２５】
１・・・ＣＰＵ（Central Processing Unit）
２・・・ＲＡＭ（Random Access Memory）
３・・・記憶装置
４・・・キー入力Ｉ／Ｆ
５・・・データ入出力Ｉ／Ｆ
６・・・表示部
７・・・３Ｄプリンタ（立体物造形装置）
７ａ・・・データ処理部
７ｂ・・・出力部
１０・・・制御手段
２０・・・グループ分類手段
３０・・・ポリゴンモデル構造化手段
４０・・・頂点重複テーブル定義手段
５０・・・削除対象ポリゴン設定手段
６０・・・頂点座標テーブル更新手段
７０・・・頂点重複テーブル更新手段
８０・・・頂点構成テーブル更新手段
９０・・・ポリゴンモデル更新手段
１００・・・グループ合成手段
１１０・・・ポリゴンモデル合成手段
１２０・・・領域別ポリゴンモデル記憶手段
１３０・・・合成ポリゴンモデル記憶手段
１４０・・・追加削除対象ポリゴン選定手段
１５０・・・追加削除対象辺選定手段
１６０・・・追加削除頂点共有ポリゴン探索手段
１７０・・・  ポリゴンモデル追加更新手段
２００・・・立体物造形用データ削減装置
【図１】
2016099841.tif 000003
【図２】
2016099841.tif 000004
【図９】
2016099841.tif 000005
【図１０】
2016099841.tif 000006
【図１１】
2016099841.tif 000007
【図１２】
2016099841.tif 000008
【図１３】
2016099841.tif 000009
【図１４】
2016099841.tif 000010
【図１５】
2016099841.tif 000011
【図１６】
2016099841.tif 000012
【図１７】
2016099841.tif 000013
【図１８】
2016099841.tif 000014
【図１９】
2016099841.tif 000015
【図２０】
2016099841.tif 000016
【図２１】
2016099841.tif 000017
【図２２】
2016099841.tif 000018
【図２３】
2016099841.tif 000019
【図２４】
2016099841.tif 000020
【図２５】
2016099841.tif 000021
【図２６】
2016099841.tif 000022
【図２７】
2016099841.tif 000023
【図２８】
2016099841.tif 000024
【図２９】
2016099841.tif 000025
【図３０】
2016099841.tif 000026
【図３１】
2016099841.tif 000027
【図３２】
2016099841.tif 000028
【図３３】
2016099841.tif 000029
【図３４】
2016099841.tif 000030
【図３９】
2016099841.tif 000031
【図４０】
2016099841.tif 000032
【図４１】
2016099841.tif 000033
【図４２】
2016099841.tif 000034
【図４３】
2016099841.tif 000035
【図４４】
2016099841.tif 000036
【図３】
2016099841.tif 000037
【図４】
2016099841.tif 000038
【図５】
2016099841.tif 000039
【図６】
2016099841.tif 000040
【図７】
2016099841.tif 000041
【図８】
2016099841.tif 000042
【図３５】
2016099841.tif 000043
【図３６】
2016099841.tif 000044
【図３７】
2016099841.tif 000045
【図３８】
2016099841.tif 000046