(57)【要約】【課題】  出力造形物の品質を劣化させることなく、ポリゴンで構成されたサーフェースデータから、効率的にポリゴンを削減して立体物造形用データを得ることが可能な立体物造形用データ最適化装置を提供する。【解決手段】  サーフェースデータを構成する各ポリゴンの面積と周長を算出し（Ｓ２１）、面積×周長が最小のポリゴンを削除対象ポリゴンとし（Ｓ２２）、削除対象ポリゴンの辺の長さを基に削除する辺を選定し（Ｓ２３）、削除対象ポリゴンを削除し（Ｓ２４）、削除する辺の頂点を共有するポリゴンを順次選出し（Ｓ２５）、２頂点を共有するポリゴンを削除し（Ｓ２６）、１頂点のみ共有するポリゴンは共有頂点を中点に補正し、そのポリゴンの面積と周長を再算出する（Ｓ２７）。頂点を共有するポリゴンの処理後、全ポリゴン数が目標値以下か否かを判定し（Ｓ２８）、目標値以下でない場合は、目標値以下となるまで繰り返してポリゴン削除処理を行う。【選択図】  図１２
2015158778.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は、図６の上部に示したものと同一である。前処理の後は、図７に示したような領域別サーフェースデータが領域別サーフェースデータ記憶手段９０に記憶される。
【００３９】
＜２．２．処理概要＞
次に、図１、図２に示した立体物造形用データ最適化装置の処理動作について説明する。図９は、本発明の一実施形態に係る立体物造形用データ最適化装置の処理概要を示すフローチャートである。まず、グループ分類手段２０が、領域別サーフェースデータ記憶手段９０から、１つの領域についての領域別サーフェースデータを読み込み、複数のグループに分類する（ステップＳ１０）。次に、各グループのサーフェースデータに対して、削除対象ポリゴン選定手段３０、削除対象辺選定手段４０、削除頂点共有ポリゴン探索手段５０、サーフェースデータ更新手段６０が、ポリゴン削減処理を実行する（ステップＳ２０）。制御手段１０が、全グループについてポリゴン削減処理が終了したか否かを判定し（ステップＳ３０）、全グループについて終了していない場合は、未処理のグループに対してステップＳ２０のポリゴン削減処理を実行する。全グループに対するポリゴン削減処理が終了した場合は、グループ合成手段７０が、隔離された小体積グループの削除を行う（ステップＳ４０）。続いて、グループ合成手段７０は、全グループのサーフェースデータの合成を行う（ステップＳ５０）。制御手段１０が、全領域について処理が終了したか否かを判定し（ステップＳ６０）、全領域について終了していない場合は、未処理の領域に対してステップＳ１０〜Ｓ５０の処理を実行する。全領域に対する処理が終了した場合は、サーフェースデータ合成手段８０が、全領域の領域別サーフェースデータの合成を行う（ステップＳ７０）。
【００４０】
＜２．３．グループ分類処理＞
まず、ステップＳ１０におけるグループ分類手段２０によるグループ分類処理について説明する。図１０は、グループ分類手段２０によるグループ分類処理の詳細を示すフローチャートである。グループ分類手段２０は、まず、初期設定を行う（ステップＳ１１）。具体的には、読み込んだ領域別サーフェースデータを構成するポリゴン数Ｐ、ポリゴンを特定する変数ｐ（ｐ＝０，・・・，Ｐ−１）、探索ステータスＳ（ｐ）、グループ属性Ｇ（ｐ）、グループを特定する変数ｇを設定する。探索ステータスＳ（ｐ）は、０、１、２のいずれかの値をとる。Ｓ（ｐ）＝０はグループに未分類の状態、Ｓ（ｐ）＝１はグループに分類された状態、Ｓ（ｐ）＝２は、そのポリゴンに隣接するポリゴンである隣接ポリゴンがグループに分類された状態を示す。さらに、ステップＳ１１においては、ｐ＝０，・・・，Ｐ−１の全てのｐについてＳ（ｐ）＝Ｇ（ｐ）＝０、ｇ＝１と初期設定する。
【００４１】
次に、全ポリゴンより、Ｓ（ｐ）＝Ｇ（ｐ）＝０となるポリゴンｐを１つ抽出する（ステップＳ１２）。初期状態では、全てＳ（ｐ）＝Ｇ（ｐ）＝０であるので、初回は必ず抽出が行われる。Ｓ（ｐ）＝Ｇ（ｐ）＝０となるポリゴンｐが複数存在する場合は、例えばｐの値が最も小さいものを抽出する。ステップＳ１２において、Ｓ（ｐ）＝Ｇ（ｐ）＝０となるポリゴンｐが存在しない場合、すなわち、全てのｐ＝０，・・・，Ｐ−１について、Ｓ（ｐ）＝２である場合、ｇ−１個のグループに分離できたものとしてグループ分類処理を終了する。なお、ステップＳ１２において、Ｓ（ｐ）＝１である状態は存在しないため、Ｓ（ｐ）は“０”か“２”のいずれかの状態である。Ｓ（ｐ）＝Ｇ（ｐ）＝０となるポリゴンｐが抽出できた場合は、抽出したポリゴンｐに対応する探索ステータスＳ（ｐ）＝１、グループ属性Ｇ（ｐ）＝ｇに設定する。
【００４２】
ステップＳ１２において、Ｓ（ｐ）＝Ｇ（ｐ）＝０となるポリゴンｐを１つ抽出し、抽出したポリゴンｐに対応する探索ステータスＳ（ｐ）＝１、グループ属性Ｇ（ｐ）＝ｇに設定した場合は、全ポリゴンより、Ｓ（ｑ）＝１となるポリゴンｑを１つ抽出する（ステップＳ１３）。ｑはポリゴンを特定する変数であり、ポリゴンｐと同様、ｑ＝０，・・・，Ｐ−１内のいずれかの整数値をとる。Ｓ（ｑ）＝１となるポリゴンｑが複数存在する場合は、例えばｑの値が最も小さいものを抽出する。ステップＳ１３において、Ｓ（ｑ）＝１となるポリゴンｑが存在しない場合、すなわち、全てのＳ（ｑ）＝０または２である場合、グループを特定する変数ｇを１インクリメント（ｇ←ｇ＋１）する（ステップＳ１４）。そしてステップＳ１２に戻り、次のグループへの分類を行う。
【００４３】
ステップＳ１３において、Ｓ（ｑ）＝１となるポリゴンｑを１つ抽出した場合、全ポリゴンより、Ｓ（ｒ）＝Ｇ（ｒ）＝０であって、抽出されたポリゴンｑと２頂点を共有する隣接ポリゴンｒを全て抽出する（ステップＳ１５）。ｒはポリゴンを特定する変数であり、ポリゴンｐ、ｑと同様、ｒ＝０，・・・，Ｐ−１内のいずれかの整数値をとる。“ポリゴンｑと２頂点を共有する”とは、ポリゴンｑと一つの辺を共有することを意味する。すなわち、隣接ポリゴンｒは一つの辺を共有することによりポリゴンｑと隣接するポリゴンである。抽出された隣接ポリゴンについては、それぞれ探索ステータスＳ（ｒ）＝１、グループ属性Ｇ（ｒ）＝ｇに設定する。
【００４４】
次に、ポリゴンｑの探索ステータスＳ（ｑ）＝２に設定する（ステップＳ１６）。すなわち、ポリゴンｑについては、隣接ポリゴンを設定した後の状態とする。そして、ステップＳ１３に戻って、全ポリゴンの中から、Ｓ（ｑ）＝１となるポリゴンｑを１つ抽出する。
【００４５】
図１０に示したフローチャートでは、ステップＳ１２、Ｓ１３、Ｓ１４で構成されるループと、ステップＳ１３、Ｓ１５、Ｓ１６で構成されるループの２つのループ処理が存在する。ステップＳ１２、Ｓ１３、Ｓ１４で構成されるループでは、グループに未分類のポリゴンを抽出してグループに分類し（ステップＳ１２）、グループに分類済みのポリゴンの中から１つを隣接ポリゴン探索用のポリゴンとして抽出できない場合（ステップＳ１３）は、そのグループに分類すべきポリゴンは、存在しないものとして、次のグループに移行（ｇ←ｇ＋１）する（ステップＳ１４）。ステップＳ１２、Ｓ１３、Ｓ１４で構成されるループでは、連続する一塊のポリゴン群を一つのグループとして分類する。したがって、ステップＳ１３において、Ｓ（ｑ）＝１となるポリゴンが存在しない場合には、グループに分類済みのいずれかのポリゴンに隣接するポリゴンが存在しないことになるので、グループｇへの分類を終え、グループｇ＋１への分類に移行するのである。
【００４６】
ステップＳ１３、Ｓ１５、Ｓ１６で構成されるループでは、グループに分類済みのポリゴンの中から１つを隣接ポリゴン探索用のポリゴンｑとして抽出し（ステップＳ１３）、全ポリゴンの中からポリゴンｑと２頂点を共有するポリゴンを隣接ポリゴンｒとして抽出し（ステップＳ１５）、抽出できた場合も抽出できない場合も、探索用のポリゴンｑの探索ステータスＳ（ｑ）を、ポリゴンｑに隣接するポリゴンの探索を終えた状態であるＳ（ｑ）＝２に設定する。
【００４７】
ステップＳ１２、Ｓ１３、Ｓ１４で構成されるループと、ステップＳ１３、Ｓ１５、Ｓ１６で構成されるループの２つのループ処理を用いることにより、全Ｐ個のポリゴンが、２頂点を共有して連続するポリゴン群ごとにグループに分類される。１頂点しか共有しないポリゴンのみで隣接している場合は、別のグループとして分類されることになる。図１０に従った処理を実行することにより領域別サーフェースデータを構成するポリゴンは複数のグループに分類されることになる。
【００４８】
＜２．４．ポリゴン削減処理＞
次に、ステップＳ２０における削除対象ポリゴン選定手段３０、削除対象辺選定手段４０、削除頂点共有ポリゴン探索手段５０、サーフェースデータ更新手段６０によるポリゴン削減処理について説明する。図１１は、ポリゴン削減の基本原理を示す図である。サーフェースデータは、現実には、空間における三次元の値をもつポリゴン群であるが、図１１の例では、説明の便宜上、二次元の値をもつポリゴン群を示している。図１１（ａ）の例では、削減前、１８個のポリゴンからなるポリゴン群を示している。
【００４９】
図１２は、削除対象ポリゴン選定手段３０、削除対象辺選定手段４０、削除頂点共有ポリゴン探索手段５０、サーフェースデータ更新手段６０によるポリゴン削減処理の詳細を示すフローチャートである。まず、削除対象ポリゴン選定手段３０が、サーフェースデータを構成する全ポリゴンを対象として、各ポリゴンの面積および周長を算出する（ステップＳ２１）。次に、削除対象ポリゴン選定手段３０は、算出された面積と周長を乗じた値が最小となるポリゴンを削除対象ポリゴンとして選定する（ステップＳ２２）。図１１の例では、図１１（ｂ）に示すように、３個の頂点Ｅ、Ｊ、Ｋで構成されるポリゴンＥＪＫが削除対象ポリゴンとして選定される。
【００５０】
続いて、削除対象辺選定手段４０が削除対象ポリゴンの３辺のうち最短の１辺を削除対象辺として選定し、選定した削除対象辺の中点を算出する（ステップＳ２３）。図１１の例では、図１１（ｃ）に示すように、削除対象ポリゴンＥＪＫの辺ＪＫが削除対象辺として選定される。さらに、辺ＪＫの中点Ｏが算出される。
【００５１】
次に、サーフェースデータ更新手段６０が、削除対象ポリゴンを削除する（ステップＳ２４）。これによりポリゴン数が１つ削減されることになる。次に、削除頂点共有ポリゴン探索手段５０が、削除対象ポリゴンの削除対象辺と頂点を共有していた削除頂点共有ポリゴンを順次選定する（ステップＳ２５）。削除対象ポリゴンの削除対象辺と２頂点を共有（すなわち辺を共有）している削除頂点共有ポリゴンが選定された場合には、サーフェースデータ更新手段６０が、その削除頂点共有ポリゴンを削除する（ステップＳ２６）。図１１の例では、３個の頂点Ｊ、Ｋ、Ｎで構成されるポリゴンＪＫＮが削除される。これによりさらにポリゴン数が１つ削減されることになる。削除対象ポリゴンの削除対象辺と１頂点を共有している削除頂点共有ポリゴンが選定された場合には、サーフェースデータ更新手段６０が、共有頂点をステップＳ２３で算出された中点に補正し、面積および周長を再算出する（ステップＳ２７）。図１１の例では、図１１（ｃ）と図１１（ｄ）を比較するとわかるように、ポリゴンＥＨＪ→ポリゴンＥＨＯ、ポリゴンＥＦＫ→ポリゴンＥＦＯ、ポリゴンＨＪＭ→ポリゴンＨＯＭ、ポリゴンＪＭＮ→ポリゴンＯＭＮ、ポリゴンＦＫＮ→ポリゴンＦＯＮに変更される。この結果、図１１の例では、図１１（ａ）の時点では、１８個あったポリゴンが、図１１（ｄ）の時点では、１６個に削減される。
【００５２】
ステップＳ２５〜ステップＳ２７の処理を終えたら、制御手段１０が、削減後の全ポリゴン数が、設定された目標値以下となっているか否かを判定する（ステップＳ２８）。目標値としては、事前に任意の値を設定することができる。判定の結果、全ポリゴン数が目標値以下となっていない場合は、ステップＳ２２に戻って、削除対象ポリゴン選定手段３０が、残っているポリゴンの中から、面積と周長を乗じた値が最小となるポリゴンを削除対象ポリゴンとして選定する。ステップＳ２８における判定の結果、全ポリゴン数が目標値以下である場合は、ポリゴン削減処理を終了する。図１２のフローチャートに従った処理を実行することにより、各グループについて設定された目標値以下になるように、ポリゴン数が削減されることになる。
【００５３】
＜２．５．小体積グループ削除処理＞
次に、ステップＳ４０におけるグループ合成手段７０による隔離された小体積グループの削除処理について説明する。ここで、隔離された小体積グループの削除処理の説明に先立ち、隔離された小体積グループの削除処理を行う理由について説明しておく。図１３は、ポリゴン削減処理により生じる問題を説明するための図である。図１３（ａ）は、ステップＳ１０のグループ分類処理を終えた直後の２グループのポリゴン群を示している。図１３（ａ）の例では、頂点Ｄ、Ｅ、Ｋを含む左側のグループと、頂点Ｄ’、Ｅ’、Ｋ’を含む右側のグループが存在する。頂点ＤとＤ’、頂点ＥとＥ’、頂点ＫとＫ’がそれぞれ３Ｄプリンタの解像度以下である場合、この２グループのポリゴン群を３Ｄプリンタで出力すると、頂点ＤとＤ’、頂点ＥとＥ’、頂点ＫとＫ’は樹脂等により連結され、２グループは連結した物体として出力される。すなわち、２グループは物理的には接着されている。
【００５４】
図１３（ａ）に示した右側のグループのポリゴン群に対して、ステップＳ２０における三角形ポリゴン削減処理を実行すると、図１３（ｂ）に示すように、ポリゴンＥ’ＦＫ’が削除対象ポリゴンとして選定される。さらに、図１３（ｃ）に示すように、削除対象ポリゴンＥ’ＦＫ’の最短辺Ｅ’Ｆが削除対象辺として選定され、辺Ｅ’Ｆの中点Ｏが算出される。そして、図１３（ｄ）に示すように、削除対象ポリゴンＥ’ＦＫ’と、削除頂点共有ポリゴンＤ’Ｅ’Ｆが削除される。
【００５５】
図１３（ａ）と図１３（ｄ）を比較するとわかるように、左右の２つのグループは、ポリゴン削減処理前に比べて、ポリゴン削減処理後には、より離れてしまっている。図１３（ｄ）に示した２グループの距離が、３Ｄプリンタの解像度を超えると、２グループのポリゴン群を３Ｄプリンタで出力した場合、２グループは別の物体として出力される。２つのグループがともに大きな物体となれば、問題はない。しかし、一つが非常に小さな物体となる場合、例えば、一方のグループが本体であって、他方のグループが本体に付属するヒゲのようなものである場合、本体と別に出力されたヒゲは、３Ｄプリンタ内に紛れ込み、機械詰まり等の問題を引き起こす恐れがある。このような問題を除去するため、上述のヒゲのような隔離された小体積グループの削除処理を行うのである。
【００５６】
図１４は、グループ合成手段７０による隔離された小体積グループの削除処理の詳細を示すフローチャートである。グループ合成手段７０は、まず、グループごとに全ポリゴンの全頂点を対象として、Ｘ、Ｙ、Ｚぞれぞれの方向の最大値および最小値を算出する（ステップＳ４１）。この結果、グループｇに対して、最小値Ｘｍｉｎ（ｇ）、最大値Ｘｍａｘ（ｇ）、最小値Ｙｍｉｎ（ｇ）、最大値Ｙｍａｘ（ｇ）、最小値Ｚｍｉｎ（ｇ）、最大値Ｚｍａｘ（ｇ）が得られる。次に、グループ合成手段７０は、グループごとに外接直方体の体積を算出する（ステップＳ４２）。具体的には、以下の〔数式１〕に従った処理を実行することにより、グループｇの外接直方体の体積Ｖ（ｇ）を算出する。
【００５７】
〔数式１〕
Ｖ（ｇ）＝（Ｘｍａｘ（ｇ）−Ｘｍｉｎ（ｇ））×（Ｙｍａｘ（ｇ）−Ｙｍｉｎ（ｇ））×（Ｚｍａｘ（ｇ）−Ｚｍｉｎ（ｇ））
【００５８】
グループ合成手段７０は、全グループに対してステップＳ４１、Ｓ４２の処理を実行する。これにより、全グループについて、外接直方体の体積が得られる。次に、グループ合成手段７０は、全グループの中で外接直方体の体積が最小となるグループを特定する（ステップＳ４３）。そして、グループ合成手段７０は、特定したグループと他の全てのグループとの最小間隔を算出する（ステップＳ４４）。ステップＳ４４における最小間隔の算出処理の詳細については後述する。
【００５９】
続いて、グループ合成手段７０は、ステップＳ４４において算出された最小間隔が所定のしきい値以上か否かを判定する（ステップＳ４５）。最小間隔と比較するための所定のしきい値としては、３Ｄプリンタ出力時に０．２ｍｍに相当する数値とすることが好ましい。判定の結果、最小間隔が所定のしきい値以上である場合は、体積最小のグループが、最も近いグループとも所定の距離以上離れていることになるので、グループ合成手段７０は、体積最小のグループを削除する処理を行う（ステップＳ４６）。ステップＳ４５における判定の結果、最小間隔が所定のしきい値未満である場合は、体積最小のグループが、最も近いグループと３Ｄプリンタの解像度以下に近接していることになるので、グループ合成手段７０は、体積最小のグループを削除する処理を行わない。
【００６０】
ステップＳ４６におけるグループの削除を行った場合、削除を行わなかった場合のいずれにおいても、そのグループについては処理済みとする。そして、ステップＳ４３に戻って、未処理のグループの中で外接直方体の体積が最小となるグループを特定する。ステップＳ４３〜ステップＳ４６の処理を繰り返し、全てのグループに対する処理を終えたら、隔離された小体積グループの削除処理を終了する。
【００６１】
ステップＳ４４における最小間隔の算出処理の詳細について説明する。図１５は、図１４のステップＳ４４における最小間隔の算出処理の詳細を示すフローチャートである。グループ合成手段７０は、初期値として、最小間隔を示す変数ｄｍｉｎに所定以上の値を設定する。ｄｍｉｎに与える初期値としては、グループ間の最小間隔としてあり得ない大きな値を設定しておけばよい。そして、グループ合成手段７０は、全グループの中から、グループｇより体積が大きい１つのグループｈを抽出する（ステップＳ４７）。この結果、グループｈについて、最小値Ｘｍｉｎ（ｈ）、最大値Ｘｍａｘ（ｈ）、最小値Ｙｍｉｎ（ｈ）、最大値Ｙｍａｘ（ｈ）、最小値Ｚｍｉｎ（ｈ）、最大値Ｚｍａｘ（ｈ）が得られる。次に、グループ合成手段７０は、Ｘ、Ｙ、Ｚの各方向別に２グループ間の差分の最小値を算出する（ステップＳ４８）。具体的には、以下の〔数式２〕に従った処理を実行することにより、Ｘ方向の差分の最小値ｄｘ、Ｙ方向の差分の最小値ｄｙ、Ｚ方向の差分の最小値ｄｚを算出する。
【００６２】
〔数式２〕
ｄｘ＝Ｍｉｎ｛｜Ｘｍａｘ（ｇ）−Ｘｍｉｎ（ｈ）｜，｜Ｘｍｉｎ（ｇ）−Ｘｍａｘ（ｈ）｜｝
ｄｙ＝Ｍｉｎ｛｜Ｙｍａｘ（ｇ）−Ｙｍｉｎ（ｈ）｜，｜Ｙｍｉｎ（ｇ）−Ｙｍａｘ（ｈ）｜｝
ｄｚ＝Ｍｉｎ｛｜Ｚｍａｘ（ｇ）−Ｚｍｉｎ（ｈ）｜，｜Ｚｍｉｎ（ｇ）−Ｚｍａｘ（ｈ）｜｝
【００６３】
続いて、グループ合成手段７０は、算出された方向別最小値のうち最大のものをグループ間最小値とし、グループ間最小値を、既に処理済みの他のグループ間における全グループ間最小値と比較し、小さい方を全グループ間最小値とする処理を行う（ステップＳ４９）。具体的には、ステップＳ４８において算出された３つの方向別最小値ｄｘ、ｄｙ、ｄｚのうち、最大の値をとるグループ間最小値Ｍａｘ（ｄｘ、ｄｙ、ｄｚ）とｄｍｉｎを比較し、Ｍａｘ（ｄｘ、ｄｙ、ｄｚ）＜ｄｍｉｎの場合、ｄｍｉｎ＝Ｍａｘ（ｄｘ、ｄｙ、ｄｚ）とする。これにより、ｄｍｉｎには、グループ間最小値の中で最小の値となる全グループ間最小値が記録されることになる。
【００６４】
ステップＳ４７、Ｓ４８、Ｓ４９の処理を繰り返して実行し、グループｇより体積が大きい全てのグループに対する処理を終えたら、図１５に示した最小間隔の算出処理を終了し、図１４のステップＳ４５に進んで、最小間隔ｄｍｉｎとしきい値との比較を行うことになる。
【００６５】
＜２．６．サーフェースデータの合成＞
図９の処理概要に示したように、ステップＳ５０においては、グループ合成手段７０が、全グループのサーフェースデータの合成を行って更新された領域別サーフェースデータを得る。また、ステップＳ７０においては、サーフェースデータ合成手段８０が、全領域の領域別サーフェースデータの合成を行って合成サーフェースデータを得る。いずれの合成処理も、ヘッダ部を除く領域別サーフェースデータを単純に結合し、ヘッダ部に合算されたポリゴン数を記録することにより行われる。合成サーフェースデータ記憶手段１００に記憶された合成サーフェースデータを３Ｄプリンタ７に出力することにより、３Ｄプリンタ７は効率的に立体物を造形することができる。造形された立体物については、ほとんど劣化は見られなかった。
【００６６】
＜３．ポリゴン削減事例＞
図１６〜図２６に、本実施形態に係る立体物造形用データ最適化装置によりポリゴンを削減したサーフェースデータの事例を示す。図１６は、図８に示したサーフェースデータ（ＳＴＬデータ）の正面からのレンダリング像を示す図である。図１６（ａ）は、削減前のサーフェースデータのレンダリング像、図１６（ｂ）は、削減後のサーフェースデータのレンダリング像である。図１６（ｂ）に示す削減後のデータは、図１６（ａ）の削減前のデータに比べてポリゴン数およびデータ量が１／１０程度に削減されているが、見た目に大きな変化はない。同様に、造形される立体物についても大きな変化はない。造形される立体物には、実質的に劣化はない。
【００６７】
図１７〜図１９は、図１６に示したレンダリング像の拡大図である。図１７が最も拡大率が小さく、図１９が最も拡大率が大きいものとなっている。図２０は、図１９に示したレンダリング像拡大図のワイヤーフレーム図である。図１９においては、削減前と削減後で大きな変化は見られないが、図２０のワイヤーフレーム図を比較すると、図２０（ｂ）においては、ポリゴン数が大きく削減されていることがわかる。
【００６８】
図２１〜図２３は、図７に示した領域別サーフェースデータ（ＳＴＬデータ）のうち、左眼球に対応する段階的削減事例を示す図である。図２１は、削減前および１／２に削減した状態、図２２は、１／４および１／８に削減した状態、図２３は、１／１０および１／２０に削減した状態、をそれぞれ示している。図２２（ａ）に示した１／４に削減した状態で、隔離小領域が発生し、図２２（ｂ）に示した１／８に削減した状態で、隔離小領域が消失している。図２４〜図２６は、図２１〜図２３に示したレンダリング像のワイヤーフレーム図である。
【００６９】
＜４．変形例等＞
以上、本発明の好適な実施形態について説明したが、本発明は上記実施形態に限定されず、種々の変形が可能である。例えば、上記実施形態では、処理対象のポリゴンを三角形としたが、四角形以上の多角形であってもよい。
【００７０】
また、上記実施形態では、ポリゴンに対して面積と周長を算出し、面積と周長の積が最小となるポリゴンを削除対象ポリゴンとして選定するようにしたが、周長を用いず面積のみを用いるようにしてもよい。
【００７１】
また、上記実施形態では、ポリゴンに対して面積と周長を算出し、面積と周長の積が最小となるポリゴンを削除対象ポリゴンとして選定するようにしたが、周長を用いず面積のみを用いるようにしてもよい。
【００７２】
また、上記実施形態では、複数のグループの更新されたサーフェースデータに対して、外接直方体の体積が所定のしきい値未満であるものを削除するようにしたが、削除しないようにすることも可能である。
【符号の説明】
【００７３】
１・・・ＣＰＵ（Central Processing Unit）
２・・・ＲＡＭ（Random Access Memory）
３・・・記憶装置
４・・・キー入力Ｉ／Ｆ
５・・・データ入出力Ｉ／Ｆ
６・・・表示部
７・・・３Ｄプリンタ（立体物造形装置）
１０・・・制御手段
２０・・・グループ分類手段
３０・・・削除対象ポリゴン選定手段
４０・・・削除対象辺選定手段
５０・・・削除頂点共有ポリゴン探索手段
６０・・・サーフェースデータ更新手段
７０・・・グループ合成手段
８０・・・サーフェースデータ合成手段
９０・・・領域別サーフェースデータ記憶手段
１００・・・合成サーフェースデータ記憶手段
【図１】
2015158778.tif 000003
【図２】
2015158778.tif 000004
【図９】
2015158778.tif 000005
【図１０】
2015158778.tif 000006
【図１１】
2015158778.tif 000007
【図１２】
2015158778.tif 000008
【図１３】
2015158778.tif 000009
【図１４】
2015158778.tif 000010
【図１５】
2015158778.tif 000011
【図３】
2015158778.tif 000012
【図４】
2015158778.tif 000013
【図５】
2015158778.tif 000014
【図６】
2015158778.tif 000015
【図７】
2015158778.tif 000016
【図８】
2015158778.tif 000017
【図１６】
2015158778.tif 000018
【図１７】
2015158778.tif 000019
【図１８】
2015158778.tif 000020
【図１９】
2015158778.tif 000021
【図２０】
2015158778.tif 000022
【図２１】
2015158778.tif 000023
【図２２】
2015158778.tif 000024
【図２３】
2015158778.tif 000025
【図２４】
2015158778.tif 000026
【図２５】
2015158778.tif 000027
【図２６】
2015158778.tif 000028