(57)【特許請求の範囲】
【請求項１】
ポリゴンの集合として表現されたポリゴンモデルのデータを、立体物の造形のために削減する装置であって、
前記ポリゴンモデル内で複数のポリゴン間で共有する共有頂点の頂点ＩＤを、前記ポリゴンを識別するポリゴンＩＤと前記ポリゴンにおける各頂点の頂点順とに対応付けて記録した頂点構成テーブルと、前記頂点ＩＤと、前記ポリゴンモデル内における前記頂点の座標値と、を対応付けて記録した頂点座標テーブルを備えており、
前記各ポリゴンの各頂点を対象頂点とし、前記頂点構成テーブルにおいて、当該対象頂点と前記頂点ＩＤが同一となる前記ポリゴンモデル内で当該対象頂点をもつポリゴンまたは先頭のポリゴンより後続のポリゴンの頂点を探索し、最初に探索された単一のポリゴンの頂点と前記対象頂点を対応付け、それぞれポリゴンおよび頂点順を識別可能な形式で記録した頂点リンクテーブルを作成する頂点リンクテーブル作成手段と、
前記ポリゴンモデルを構成する各ポリゴンに対して面積と周長を算出し、面積と周長の積が最小となるポリゴンを、削除するべきポリゴンである削除対象ポリゴンとして選定し、前記削除対象ポリゴンより補正するべき頂点を補正対象頂点として少なくとも２つ選定する削除対象ポリゴン選定手段と、
前記補正対象頂点の各々に対して、前記頂点リンクテーブルを参照し、前記補正対象頂点の各々と同一の頂点ＩＤをもつ共有頂点を順次探索する共有頂点探索手段と、
前記探索された共有頂点を２つ以上含むポリゴンを、前記削除対象ポリゴンとともに削除し、前記共有頂点を１つのみ含むポリゴンに対して、当該共有頂点を前記選定された全ての補正対象頂点の平均点の座標に補正することによって前記ポリゴンモデルを更新するポリゴンモデル更新手段と、
を有することを特徴とする立体物造形用データ削減装置。
【請求項２】
前記頂点リンクテーブル作成手段は、ポリゴンおよび前記ポリゴン内の頂点順を識別するポリゴン別頂点ＩＤを前記頂点ＩＤごとに１つ記録できる更新頂点テーブルを用い、前記頂点構成テーブルの先頭のポリゴンから頂点ＩＤを順次抽出し、前記更新頂点テーブルの当該頂点ＩＤに対応付けて、当該ポリゴンおよび頂点順を識別するポリゴン別頂点ＩＤを上書きしながら前記更新頂点テーブルを作成し、上書き前に他のポリゴン別頂点ＩＤがあらかじめ書き込まれている場合、前記他のポリゴン別頂点ＩＤに対応付けて、前記上書きしたポリゴン別頂点ＩＤを、前記頂点リンクテーブルに書き込むことにより、前記頂点リンクテーブルを作成するようにしていることを特徴とする請求項１に記載の立体物造形用データ削減装置。
【請求項３】
前記頂点リンクテーブル作成手段は、ポリゴンおよび前記ポリゴン内の頂点順を識別するポリゴン別頂点ＩＤを前記頂点ＩＤごとに１つ記録できる起点頂点テーブルを更に備え、前記頂点構成テーブルの先頭のポリゴンから頂点ＩＤを順次抽出し、前記起点頂点テーブルの当該頂点ＩＤに対応付けて、当該ポリゴンおよび頂点順を識別するポリゴン別頂点ＩＤを上書きしないように書き込みながら前記起点頂点テーブルを作成し、前記更新頂点テーブルを用いて作成された前記頂点リンクテーブルの空欄に、頂点ＩＤで対応付けた前記更新頂点テーブルと前記起点頂点テーブルの関係に基づき、前記起点頂点テーブルのポリゴン別頂点ＩＤを書き込むことにより、前記頂点リンクテーブルを作成するようにしていることを特徴とする請求項２に記載の立体物造形用データ削減装置。
【請求項４】
前記削除対象ポリゴン選定手段は、
前記削除対象ポリゴンを選定した後、
前記削除対象ポリゴンを構成する辺の長さに基づいて、削除するべき辺を削除対象辺として選定し、前記削除対象辺の２頂点を前記補正対象頂点として選定するようにしていることを特徴とする請求項１から請求項３のいずれか一項に記載の立体物造形用データ削減装置。
【請求項５】
前記削除対象ポリゴン選定手段は、前記削除対象ポリゴンの各辺の長さを算出し、最も短い辺を前記削除対象辺として選定することを特徴とする請求項４に記載の立体物造形用データ削減装置。
【請求項６】
前記ポリゴンモデル更新手段は、更に、
前記削除対象ポリゴンにおける前記補正対象頂点を頂点αおよび頂点βとすると、
前記頂点リンクテーブルにおいて、前記削除対象ポリゴンの前記頂点αに対してリンク先を設定している他のポリゴンの頂点に対して、リンク先を前記削除対象ポリゴンの頂点βに補正し、前記削除対象ポリゴンの前記頂点βに対してリンク先を設定している他のポリゴンの頂点に対して、リンク先を前記削除対象ポリゴンの頂点αに補正し、前記削除対象ポリゴンの頂点αおよび頂点βを含む２つのリンクのループを１つのループに統合するように、前記頂点リンクテーブルを更新するようにしていることを特徴とする請求項４または請求項５に記載の立体物造形用データ削減装置。
【請求項７】
前記ポリゴンモデル更新手段は、更に、
前記頂点リンクテーブルにおいて、
前記ポリゴンモデル更新手段により削除されたポリゴンの各頂点をリンク先として設定されているリンク元の他のポリゴンの頂点のリンク先を、前記削除されたポリゴンの各頂点に設定されている前記他のポリゴンとは異なる別のポリゴンのリンク先の頂点に変更し、前記削除されたポリゴンをバイパスするように、前記頂点リンクテーブルを更新するようにしていることを特徴とする請求項６に記載の立体物造形用データ削減装置。
【請求項８】
前記ポリゴンモデル更新手段により更新されたポリゴンモデルを構成するポリゴン数が目標値より大きい場合、前記削除対象ポリゴン選定手段、前記共有頂点探索手段、ポリゴンモデル更新手段に対して繰り返して処理を実行させる制御を行う制御手段をさらに有することを特徴とする請求項１から請求項７のいずれか一項に記載の立体物造形用データ削減装置。
【請求項９】
前記ポリゴンモデルが複数の領域に分割されたボクセル形式の３Ｄ医療画像データに対応して複数セット存在しており、
前記制御手段は、各ポリゴンモデルに対して、前記頂点リンクテーブル作成手段、前記削除対象ポリゴン選定手段、前記共有頂点探索手段、ポリゴンモデル更新手段に対して処理を実行させ、複数セットの更新されたポリゴンモデルを作成させるものであって、
前記複数セットの更新されたポリゴンモデルを単一のポリゴンモデルに合成するポリゴンモデル合成手段を、
更に有することを特徴とする請求項８に記載の立体物造形用データ削減装置。
【請求項１０】
前記削除対象ポリゴン選定手段を実行させる対象のポリゴンモデルに対して、各グループに属するポリゴンが当該グループ内の他のいずれかのポリゴンと、ポリゴンを構成する辺を共有するようにグループに分類するポリゴンモデルのグループ分類手段と、
前記分類された各グループに対する前記頂点リンクテーブル作成手段、前記削除対象ポリゴン選定手段、前記共有頂点探索手段、ポリゴンモデル更新手段による処理の実行により得られた複数のグループの更新されたポリゴンモデルに対して、単一のポリゴンモデルに合成するグループ合成手段と、
を更に有することを特徴とする請求項１から請求項９のいずれか一項に記載の立体物造形用データ削減装置。
【請求項１１】
前記グループ合成手段は、前記複数のグループの更新されたポリゴンモデルに対して、
外接直方体の体積を算出し、算出された体積が所定のしきい値未満である場合、当該グループのポリゴンモデルを合成の対象から除外することを特徴とする請求項１０に記載の立体物造形用データ削減装置。
【請求項１２】
請求項１から請求項１１のいずれか一項に記載の立体物造形用データ削減装置と、
前記立体物造形用データ削減装置から出力されたポリゴンモデルを用いて立体物を造形する立体物造形装置と、
を有することを特徴とする立体物造形システム。
【請求項１３】
コンピュータを、請求項１から請求項１１のいずれか一項に記載の立体物造形用データ削減装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、立体物を表すデータを基に、樹脂等を加工して立体物を造形する３Ｄプリンタ等の立体物造形装置の利用に際して、立体物造形装置への出力用データを削減するための技術に関する。
【背景技術】
【０００２】
近年、立体物を表すデータをもとに、樹脂や石膏等を加工して造形する３Ｄプリンタが立体物造形装置として普及してきている。３Ｄプリンタの医療応用として、医療診断で撮影される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は、図６の上部に示したものと同一である。前処理の後は、図７に示したような領域別ポリゴンモデルが領域別ポリゴンモデル記憶手段９０に記憶される。
【００５５】
＜２．２．処理概要＞
次に、図１、図２に示した立体物造形用データ削減装置の処理動作について説明する。図９は、本発明の一実施形態に係る立体物造形用データ削減装置の処理概要を示すフローチャートである。まず、グループ分類手段２０が、領域別ポリゴンモデル記憶手段９０から、１つの領域についての領域別ポリゴンモデルを読み込み、複数のグループに分類する（ステップＳ１０）。次に、各グループのポリゴンモデルに対して、頂点リンクテーブル作成手段３０、削除対象ポリゴン選定手段４０、共有頂点探索手段５０、ポリゴンモデル更新手段６０が、ポリゴン削減処理を実行する（ステップＳ２０）。制御手段１０が、全グループについてポリゴン削減処理が終了したか否かを判定し（ステップＳ３０）、全グループについて終了していない場合は、未処理のグループに対してステップＳ２０のポリゴン削減処理を実行する。全グループに対するポリゴン削減処理が終了した場合は、グループ合成手段７０が、隔離された小体積グループの削除を行う（ステップＳ４０）。続いて、グループ合成手段７０は、全グループのポリゴンモデルの合成を行う（ステップＳ５０）。制御手段１０が、全領域について処理が終了したか否かを判定し（ステップＳ６０）、全領域について終了していない場合は、未処理の領域に対してステップＳ１０〜Ｓ５０の処理を実行する。全領域に対する処理が終了した場合は、ポリゴンモデル合成手段８０が、全領域の領域別ポリゴンモデルの合成を行う（ステップＳ７０）。
【００５６】
＜２．３．グループ分類処理＞
まず、ステップＳ１０において、グループ分類手段２０がグループ分類処理を行う。具体的には、領域別ポリゴンモデルに対して、各グループに属するポリゴンが当該グループ内の他のいずれかのポリゴンと、ポリゴンを構成する辺を共有するようにグループ分類する。グループ分類処理の具体的な手法としては、公知の様々な手法を用いることができる。
【００５７】
＜２．４．ポリゴン削減処理＞
次に、ステップＳ２０における頂点リンクテーブル作成手段３０、削除対象ポリゴン選定手段４０、共有頂点探索手段５０、ポリゴンモデル更新手段６０によるポリゴン削減処理について説明する。ポリゴン削減処理におけるポリゴンの削除の手法として、ポリゴンを構成する稜線を特定し、その稜線を削除することによりポリゴンを削除する手法を用いる。ここで、稜線とは、ポリゴンの辺を意味する。図１０は、稜線単位削除によるポリゴン削減の基本原理を示す図である。ポリゴンモデルは、図１２に示されるように空間における三次元の値をもつポリゴン群であるが、図１０の例では、紙面上での説明の便宜上、二次元空間に投影したポリゴン群を示している。図１０（ａ）の例では、削減前、１８個のポリゴンからなるポリゴン群を示している。図１０（ａ）において、大文字のアルファベットＡ〜Ｎは特定のポリゴンに属する形式でなく、座標が異なる頂点を識別するために示している。大文字のアルファベットＡ〜Ｎは、ポリゴン群全体において頂点を識別するために、便宜上付されたものであり、後述する頂点座標配列データや、頂点リンクテーブル、頂点構成テーブル、頂点座標テーブルには記録されていない（一部記載されているものは、理解を容易にするために便宜上用いられている。）。
【００５８】
図１１は、図１０（ａ）に示したポリゴン群の詳細を示す図である。図１１においては、図１０（ａ）に示した頂点Ａ〜Ｎだけでなく、ポリゴンＩＤＰ１〜Ｐ１８、頂点Ａ〜Ｎを各ポリゴンＩＤに対応付けて表現されたポリゴン別頂点ＩＤＶ１ａ〜Ｖ１８ｃが記載されている。ポリゴン別頂点ＩＤＶ１ａ〜Ｖ１８ｃは、頂点座標配列データ、頂点構成テーブル、頂点座標テーブルには記録されておらず、頂点リンクテーブルにのみ記録される。
【００５９】
図１２は、図１１に示したポリゴン群を実現するための頂点座標配列データを示す図である。頂点座標配列データは、ポリゴンモデルを規定するデータであり、ポリゴンの集合体であるポリゴンモデルを座標値の配列構造で定義している。すなわち、図１２は、ＳＴＬデータより法線ベクトルの情報を削除した構造を示している。図１２に示すように、頂点座標配列データは、ポリゴンを識別する識別情報であるポリゴンＩＤＰ１〜Ｐ１８に対応付けて、ポリゴンを構成する第１頂点、第２頂点、第３頂点の３つの頂点順に各座標値が記録されている。図１２の頂点座標配列データにおいては、ポリゴンＰ１が先頭であり、ポリゴンＩＤが増える側を後方とする。すなわち、ポリゴンＰ１から見て、ポリゴンＰ２〜Ｐ１８は、後続のポリゴンとなる。
【００６０】
ポリゴン別頂点ＩＤは、その頂点が属するポリゴンと当該ポリゴンにおける頂点順の２種を識別する識別情報である。すなわち、ポリゴンＩＤと頂点順の形式で記録するためのものである。具体的には、図１１に示すように、頂点を示すＶの後に、対応するポリゴンＩＤに含まれる数字、そして第１頂点、第２頂点、第３頂点のいずれかの頂点順を識別するため、ａ〜ｃのいずれかのアルファベットで表現する。例えば、図１２の１行目に示すように、ポリゴンＩＤ“Ｐ１”のポリゴン（ポリゴンＰ１）の第１頂点は、“Ｖ１ａ”と表現される。ポリゴン別頂点ＩＤ“Ｖ１ａ”に数字“１”が入っているため、ポリゴンＰ１の頂点であることが明確になっている。図１２においては、図１１との対応関係、および後述する頂点リンクテーブルとの対応関係を示すため、便宜上“Ｖ１ａ”等のポリゴン別頂点ＩＤを示しているが、実際には、ポリゴン別頂点ＩＤは、頂点座標配列データには上記の形式で記録されているわけではないが、ポリゴン別頂点ＩＤをシリアル番号化した順序で各頂点の座標値が配列されている。また、図１２の頂点座標配列データにおいて、各頂点は、図１０で示した共有頂点Ａ〜Ｎのいずれかに対応するため、説明の便宜上、各頂点の座標データには共有頂点Ａ〜Ｎを識別するアルファベットの小文字を添えて表現している。例えば、図１２の１行目に示すように、ポリゴンＰ１の第１頂点Ｖ１ａの座標値は、図１１において共有頂点“Ｄ”に対応するので、“（Ｘｄ，Ｙｄ，Ｚｄ）”と表現される。各ポリゴンごとに、構成される３つの頂点の頂点順に３つの頂点の座標値が記録されている。
【００６１】
上記のような規則に従って作成されるため、頂点座標配列データにおいては、同一座標の共有頂点が複数箇所に重複して記録されることになる。例えば、図１０、図１１に示した共有頂点Ｄは、６つのポリゴンＰ１，Ｐ２，Ｐ４，Ｐ５，Ｐ６，Ｐ７の各々に含まれる１つの頂点に共有されるため、座標値“（Ｘｄ，Ｙｄ，Ｚｄ）”は、Ｖ１ａ，Ｖ２ａ，Ｖ４ｂ，Ｖ５ｃ，Ｖ６ｃ，Ｖ７ｃなるポリゴン別頂点ＩＤの６箇所に記録される。
【００６２】
図１３は、ポリゴン削減処理の詳細を示すフローチャートである。まず、頂点リンクテーブル作成手段３０が、頂点リンクテーブルを作成する（ステップＳ２１）。頂点リンクテーブルは、ポリゴンの各頂点について、その頂点と同一座標となる他のポリゴンの頂点を１つ対応付けて記録したテーブルである。
【００６３】
図１４は、ステップＳ２１の頂点リンクテーブル作成処理の詳細を示すフローチャートである。頂点リンクテーブルの作成に当たり、まず、頂点構成テーブル、頂点座標テーブルを用意する（ステップＳ５１）。ステップＳ５１においては、頂点構成テーブル、頂点座標テーブルを用意することができれば、どのような手法を用いてもよいが、ポリゴンモデルの構造化を行って作成することもできる。ポリゴンモデルの構造化とは、ポリゴンモデルを実現するデータである頂点座標配列データを、頂点構成テーブルおよび頂点座標テーブルで構成される構造に変換することにより、ポリゴンモデルにおける頂点関係（トポロジー・位相情報）が座標値（数値データ）から分離され、あるポリゴンの頂点の修正により影響を受ける周辺のポリゴンの頂点の探索が容易になり、編集し易い構造に組み替えることを意味する。
【００６４】
図１５は、ステップＳ５１のポリゴンモデルの構造化の詳細を示すフローチャートである。ステップＳ５１のポリゴンモデルの構造化は、頂点リンクテーブル作成手段３０により行われる。頂点リンクテーブル作成手段３０は、ポリゴンモデル構造化手段としての機能も備え、さらに、ポリゴンモデル構造化手段は、ハッシュ値算出手段、座標値照合手段、頂点構成テーブル処理手段、頂点座標テーブル処理手段としての機能を備えている。図１５に示したポリゴンモデルの構造化処理は、これらの手段が連携することにより実現される。
【００６５】
まず、頂点構成テーブル、頂点座標テーブル、頂点ＩＤの初期化を行う（Ｓ１０１）。頂点構成テーブルは、各ポリゴンに含まれる各頂点を、同一座標の頂点を同一値とする共有頂点の頂点ＩＤで表現し、ポリゴンを構成する各頂点を頂点順に頂点ＩＤで表現してポリゴンと対応付けて記録したテーブルである。頂点ＩＤは、共有頂点を識別するための頂点識別情報であり、共有頂点を一意に特定することができれば、どのようなものを用いてもよいが、演算処理の効率化のため、本実施形態では、０から始まるシリアルな整数値を用いている。頂点座標テーブルは、頂点構成テーブルに付与された頂点ＩＤと座標値を対応付けて記録したテーブルである。頂点構成テーブル、頂点座標テーブルの初期化は、各項目が記録されていない状態にすることを意味する。また、頂点ＩＤの初期化として現在の頂点ＩＤ＝０に設定する。さらに、ハッシュ値とリンク先頂点ＩＤを対応付けた先頭位置テーブルも初期化する。先頭位置テーブルの初期化は、リンク先頂点ＩＤを全て“−１”に設定することにより行われる。頂点座標テーブルと先頭位置テーブルの２つのテーブルによりハッシュ値別頂点座標テーブルを実現する。また、Ｓ１０１では、頂点座標配列データより頂点座標値を抽出するアドレス情報としてポリゴンＩＤと頂点順を定義し、ポリゴンＩＤは“Ｐ１”、頂点順は“０”に初期化する。頂点座標配列データにはポリゴンＩＤに対応付けて３つの頂点ＩＤが記録されているが、頂点順は、左から０，１，２となっており、図１２に示した第１頂点、第２頂点、第３頂点に対応している。
【００６６】
次に、頂点座標配列データよりポリゴンＩＤと、そのポリゴンＩＤにおいて頂点順に対応する１つの頂点座標値を抽出する（Ｓ１０２）。例えば、図１２に示した頂点座標配列データからは、ポリゴンＩＤ“Ｐ１”と頂点順“０”に対応する第１頂点の頂点座標値（Ｘｄ，Ｙｄ，Ｚｄ）が抽出される。
【００６７】
続いて、抽出された頂点座標値（Ｘｄ，Ｙｄ，Ｚｄ）よりハッシュ値を算出する（Ｓ１０３）。具体的には、まず、ポリゴンモデル内の全てのポリゴンの３次元座標値ｘ，ｙ，ｚの最大値Ｘｍａｘ，Ｙｍａｘ，Ｚｍａｘ、最小値Ｘｍｉｎ，Ｙｍｉｎ，Ｚｍｉｎを求める。これは、図１２に示したような頂点座標配列データの座標ごとの最大値、最小値を求めることになる。そして、座標値ｘ，ｙ，ｚの値を均等なＳ段階に分類し、整数値ｈｘ，ｈｙ，ｈｚ（０≦ｈｘ，ｈｙ，ｈｚ≦Ｓ−１）に変換する。整数Ｓとしては、例えばＳ＝３２を設定することができる。具体的には、以下の〔数式１〕に従った処理を実行することにより、ｈｘ，ｈｙ，ｈｚを算出する。ただし、〔数式１〕に従った処理の後、小数点以下を切り捨てた値を、整数値ｈｘ，ｈｙ，ｈｚとして得るものとする。
【００６８】
〔数式１〕
ｈｘ＝（ｘ−Ｘｍｉｎ）・Ｓ／（Ｘｍａｘ−Ｘｍｉｎ）
ｈｙ＝（ｙ−Ｙｍｉｎ）・Ｓ／（Ｙｍａｘ−Ｙｍｉｎ）
ｈｚ＝（ｚ−Ｚｍｉｎ）・Ｓ／（Ｚｍａｘ−Ｚｍｉｎ）
【００６９】
そして、以下の〔数式２〕に従った処理を実行することにより、ハッシュ値ｈを算出する。
【００７０】
〔数式２〕
ｈ＝ｈｘ＋ｈｙ・Ｓ＋ｈｚ・Ｓ2（０≦ｈ≦Ｓ3−１）
【００７１】
次に、算出されたハッシュ値を用いて先頭位置テーブルを参照する（Ｓ１０４）。そして、そのハッシュ値に対応するリンク先頂点ＩＤが先頭位置テーブルに登録されているか否かを判定する（Ｓ１０５）。ハッシュ値に対応するリンク先頂点ＩＤ（図中“リンク頂点ＩＤ”と表示）が“−１”、すなわち初期状態である場合は、そのハッシュ値に対応するリンク先頂点ＩＤが未登録、すなわち既登録でないことを意味する。
【００７２】
この場合、先頭位置テーブルに頂点ＩＤの記録を行う（Ｓ１０６）。具体的には、先頭位置テーブルのハッシュ値に対応するリンク先頂点ＩＤに、現在の頂点ＩＤ（初期状態では“０”）を書き込む。続いて、頂点座標テーブルの現在の頂点ＩＤの位置にステップＳ１０２で抽出した座標値を書き込む。この時、頂点座標テーブルにもリンク先頂点ＩＤを書き込む欄があるが、初期状態の“−１”のままにする。また、頂点構成テーブルにステップＳ１０２で抽出したポリゴンＩＤと、現在の頂点ＩＤを書き込む。ここでは、新規な頂点ＩＤとして記録されることになる。そして、現在の頂点ＩＤをインクリメントする（Ｓ１０７）。
【００７３】
一方、ステップＳ１０５において、ハッシュ値に対応するリンク先頂点ＩＤが“−１”でない場合は、そのハッシュ値に対応するリンク先頂点ＩＤが既登録であることを意味する。この場合、ステップＳ１０２で抽出した座標値と、頂点座標テーブルにおける既登録のリンク先頂点ＩＤに対応する座標値が一致するか否かを判定する（Ｓ１０８）。判定の結果、両座標値が一致する場合は、頂点構成テーブルのポリゴンＩＤ、頂点順の位置に、現在の頂点ＩＤを記録する（Ｓ１０９）。ステップＳ１０８における判定の結果、両座標値が異なる場合は、頂点座標テーブルのリンク先頂点ＩＤを参照し、リンク先頂点ＩＤが０以上であるか否かを判定する（Ｓ１１０）。判定の結果、リンク先頂点ＩＤが０以上である場合は、その値を頂点ＩＤとし、ステップＳ１０８に戻って、その頂点ＩＤに対応する座標値とステップＳ１０２で抽出した座標値を照合する。ステップＳ１１０における判定の結果、リンク先頂点ＩＤが負値（例えば“−１”）である場合は、頂点座標テーブルのその頂点ＩＤに対応するリンク先頂点ＩＤに現在の頂点ＩＤを記録し、ステップＳ１０７に戻って、頂点座標テーブルの現在の頂点ＩＤの位置にステップＳ１０２で抽出した座標値を記録する。この時、頂点座標テーブルの現在の頂点ＩＤにおけるリンク先頂点ＩＤについては、初期状態の“−１”のままにする。また、頂点構成テーブルにステップＳ１０２で抽出したポリゴンＩＤと頂点ＩＤを記録する。そして、頂点ＩＤをインクリメントする。
【００７４】
ステップＳ１０７またはＳ１０９の処理を終えたら、全ポリゴンに対して処理を終えたか否かを判定する（Ｓ１１１）。具体的には、まず、頂点順をインクリメントし、頂点順が“２”を超えたら、ポリゴンＩＤをインクリメントして頂点順を“０”にする。例えば、ポリゴンＩＤ“Ｐ１”の状態で、ポリゴンＩＤをインクリメントすると、ポリゴンＩＤ“Ｐ２”になる。ポリゴンＩＤがポリゴン総数を超えていなければ、ステップＳ１０２に戻って処理を繰り返す。ポリゴンＩＤがポリゴン総数を超えていれば、全ポリゴンに対して処理を終えたと判定して処理を終了する。
【００７５】
図１５に示したステップＳ５１のポリゴンモデルの構造化処理の具体例について説明する。図１０に示したポリゴン群が、その頂点の座標値により図１６に示すようなハッシュ値をとる場合を例にとって説明する。図１６の例では、説明の都合上２次元で表現し、上記〔数式２〕においてＳ＝２とすると、ｈ＝ｈｘ＋ｈｙ・２となり、頂点Ａ，Ｂ，Ｄ，Ｅのハッシュ値がｈ＝０、頂点Ｃ，Ｆのハッシュ値がｈ＝１、頂点Ｇ，Ｈ，Ｊ，Ｌ，Ｍのハッシュ値がｈ＝２、頂点Ｉ，Ｋ，Ｎのハッシュ値がｈ＝３であることを示している。実際には上記〔数式２〕において、Ｓ＝３２に設定し、ｈ＝ｈｘ＋ｈｙ・３２＋ｈｚ・１０２４となり、ハッシュ値ｈは、０〜３２７６７の値をとるが、以下では、説明を簡略化するため、ハッシュ値は前述の０〜３の値をとるものとして説明していく。
【００７６】
図１７は、Ｓ１０１における初期化時の各テーブルの状態を示す図である。図１７（ａ）は頂点構成テーブル、図１７（ｂ）は先頭位置テーブル、図１７（ｃ）は頂点座標テーブルを示している。先頭位置テーブルには、ハッシュ値に頂点ＩＤが対応付けられてリンク先頂点ＩＤとして記録されている。ここでは、図１６に示したようにハッシュ値が０〜３の値をとるため、先頭位置テーブルには、全てのハッシュ値０〜３に対応付けてリンク先頂点ＩＤとして“−１”が記録されている。頂点座標テーブルには、頂点ＩＤに対応付けられて頂点座標が記録されるとともに、リンク先頂点ＩＤが記録されている。
【００７７】
図１７（ａ）に示すように、頂点構成テーブルは、ポリゴンＩＤに対応付けて３つの頂点ＩＤが記録されるようになっているが、頂点順は、左から０，１，２となっており、図１２に示した第１頂点、第２頂点、第３頂点に対応している。ステップＳ１０１における初期化の際、頂点順＝０に初期化される。ステップＳ１０２において、頂点座標配列データより、ポリゴンＰ１の第１頂点の座標値（Ｘｄ，Ｙｄ，Ｚｄ）を抽出して、ステップＳ１０３において、ハッシュ値“０”が算出されたものとする。ステップＳ１０４において、ハッシュ値“０”で先頭位置テーブルを参照すると、ステップＳ１０５において、リンク先の頂点ＩＤが登録されていないため、先頭位置テーブルのハッシュ値“０”に対応付けて、ステップＳ１０６において、現在の頂点ＩＤ“０”をリンク先として記録する。
【００７８】
そして、ステップＳ１０７において、頂点座標テーブルにおける現在の頂点ＩＤ“０”の位置に、ステップＳ１０２において抽出した座標値（Ｘｄ，Ｙｄ，Ｚｄ）を記録し、リンク先頂点ＩＤとして“−１”を記録する。さらに、ステップＳ１０７において、現在のポリゴンＩＤ“Ｐ１”の現在の頂点順“０”の位置に、現在の頂点ＩＤ“０”を記録する。この結果、各テーブルは、図１８に示すような状態となる。そして、頂点ＩＤをインクリメントして現在の頂点ＩＤを“０”→“１”とする。また、頂点順をインクリメントして現在の頂点順を“０”→“１” とする。現在のポリゴンＩＤは“Ｐ１”であり、“Ｐ１３”を超えていないため、ステップＳ１１１において、全ポリゴンに対して処理終了していないと判断され、ステップＳ１０２に戻る。
【００７９】
ステップＳ１０２において、頂点座標配列データより、現在のポリゴンＩＤ“Ｐ１”、現在の頂点順“１”に基づき、ポリゴンＰ１の第２頂点の座標値（Ｘｂ，Ｙｂ，Ｚｂ）を抽出する。そして、ステップＳ１０３において、座標値（Ｘｂ，Ｙｂ，Ｚｂ）に対してハッシュ値“０”が算出されたものとする。ステップＳ１０４において、ハッシュ値“０”で先頭位置テーブルを参照すると、ステップＳ１０５において、リンク先の頂点ＩＤとして“０”が既登録であるため、ステップＳ１０８において、既登録の頂点ＩＤ“０”に対応する頂点座標テーブルの座標値（Ｘｄ，Ｙｄ，Ｚｄ）と、ステップＳ１０２で抽出した座標値（Ｘｂ，Ｙｂ，Ｚｂ）を照合する。照合の結果、不一致であるので、ステップＳ１１０において、頂点座標テーブルのリンク先の頂点ＩＤが０以上であるか負の値であるかを判定する。
【００８０】
図１８に示すように、リンク先の頂点ＩＤが“−１”であるので、ステップＳ１０７において、頂点座標テーブルの現在の頂点ＩＤ“１”の位置に、ステップＳ１０２において抽出した座標値（Ｘｂ，Ｙｂ，Ｚｂ）を記録し、リンク先頂点ＩＤとして“−１”を記録する。さらに、ステップＳ１０７において、頂点構成テーブルの、現在のポリゴンＩＤ“Ｐ１”の現在の頂点順“１”の位置に、現在の頂点ＩＤ“１”を記録する。この結果、各テーブルは、図１９に示すような状態となる。そして、頂点ＩＤをインクリメントして現在の頂点ＩＤを“１”→“２”とする。また、頂点順をインクリメントして現在の頂点順を“１”→“２” とする。現在のポリゴンＩＤは“Ｐ１”であり、“Ｐ１３”を超えていないため、ステップＳ１１１において、全ポリゴンに対して処理終了していないと判断され、ステップＳ１０２に戻る。
【００８１】
ポリゴンＩＤ“Ｐ１”、頂点ＩＤ“２”、頂点順“２”の場合は、ポリゴンＩＤ“Ｐ１”、頂点ＩＤ“１”、頂点順“１”の場合と同様に処理され、各テーブルは、図２０に示すような状態となる。そして、頂点ＩＤをインクリメントして現在の頂点ＩＤを“２”→“３”とする。また、頂点順は、１つのポリゴンについて“０”“１”“２”の３つの値のみをとるため、ポリゴンＩＤをインクリメントして“Ｐ１”→“Ｐ２”とし、頂点順をリセットして現在の頂点順を“２”→“０” とする。現在のポリゴンＩＤは“Ｐ２”となり、“Ｐ１８”を超えていないため、ステップＳ１１１において、全ポリゴンに対して処理終了していないと判断され、ステップＳ１０２に戻る。
【００８２】
ステップＳ１０２において、頂点座標配列データより、現在のポリゴンＩＤ“Ｐ２”、現在の頂点順“０”に基づき、ポリゴンＰ２の第１頂点の座標値（Ｘｄ，Ｙｄ，Ｚｄ）を抽出する。そして、ステップＳ１０３において、座標値（Ｘｄ，Ｙｄ，Ｚｄ）に対してハッシュ値“０”が算出されたものとする。ステップＳ１０４において、ハッシュ値“０”で先頭位置テーブルを参照すると、ステップＳ１０５において、リンク先の頂点ＩＤとして“０”が既登録であるため、ステップＳ１０８において、既登録の頂点ＩＤ“０”に対応する頂点座標テーブルの座標値（Ｘｄ，Ｙｄ，Ｚｄ）と、ステップＳ１０２で抽出した座標値（Ｘｄ，Ｙｄ，Ｚｄ）を照合する。照合の結果、一致するので、ステップＳ１０９において、頂点座標テーブルの座標値が一致した頂点ＩＤ“０”を、頂点構成テーブルの、現在のポリゴンＩＤ“Ｐ２”の現在の頂点順“０”の位置に記録する。この結果、各テーブルは、図２１に示すような状態となる。
【００８３】
上記のようにして、ポリゴンＰ１８まで処理を行ってステップＳ１１１の判定により処理を終了する。このとき、各テーブルは、図２２に示すような状態となる。すなわち、ハッシュ値が同一の他の座標値を頂点ＩＤより最近傍に記録した単一の頂点ＩＤがリンク先として対応付けられているものとなる。上記説明のように、ポリゴンモデルの構造化処理においては、ステップＳ１０８において座標値の照合を行い、不一致であれば頂点座標テーブルに登録するが、一致している場合は、次々に照合を繰り返していく。この処理は、頂点座標テーブルが大きくなり、既登録の座標値が多くなる程、負荷が高くなることになる。本実施形態では、ハッシュ値を用いてハッシュ値別頂点座標テーブルを参照することにより、頂点座標テーブルの全ての座標値の照合を行うことなく、ハッシュ値が異なる座標値とは一致しないことが自明なため照合対象から除外することができ、同一ハッシュ値の頂点座標テーブルのみを参照すればよいことになる。頂点座標テーブルの中で同一ハッシュ値をもつ座標値は、本実施形態では高々１／４程度であるが、前述の通り実際には上記〔数式２〕において、Ｓ＝３２に設定することが多く、そうすると頂点座標テーブルの中で同一ハッシュ値をもつ座標値は１／３２７６７程度に削減され、全件と照合する場合に比べ照合時間も１／３２７６７程度に短縮されることになる。このため、ポリゴンモデルの構造化処理を桁違いに高速に行うことが可能となる。
【００８４】
図２２の例で、ハッシュ値が“０”の場合、図２２（ｃ）の頂点座標テーブルでは、リンク先頂点ＩＤに従って、頂点ＩＤ“０”“１”“２”“６”のものだけ照合すれば、頂点座標の登録が可能となる。図２２（ｂ）に示した先頭位置テーブルを削除し、図２２（ｃ）に示した頂点座標テーブルよりリンク先頂点ＩＤの欄を削除することにより、図２３に示したような頂点構成テーブルと頂点座標テーブルを得ることができ、ポリゴンモデルの構造化は完了する。
【００８５】
図２３は、ステップＳ５１において用意された頂点構成テーブルと頂点座標テーブルを示す図である。図２３（ａ）に示す頂点構成テーブルは、ポリゴンの共有頂点をポリゴンモデル内で一意に識別する頂点識別情報である頂点ＩＤと、ポリゴンを識別するポリゴン識別情報であるポリゴンＩＤが対応付けて頂点順に記録されたテーブルである。ポリゴンが三角形であるため、図２３（ａ）の例では、１つのポリゴンＩＤに３つの頂点ＩＤが対応付けられている。図２３（ｂ）に示す頂点座標テーブルは、頂点識別情報である頂点ＩＤと、ポリゴンモデル内における頂点のｘｙｚ座標値である頂点座標が対応付けて記録されたテーブルである。
【００８６】
頂点構成テーブル、頂点座標テーブルが用意されたら、次に、頂点構成テーブルを用いて、起点頂点テーブルを作成する（ステップＳ５２）。図２４は、ステップＳ５２における起点頂点テーブルの変化の様子を示す図である。起点頂点テーブルは、図２４（ａ）〜図２４（ｄ）に示すように、頂点ＩＤと、ポリゴン別頂点ＩＤ（図中「ポリゴン別頂点」と表記）が対応付けて記録されたテーブルである。ポリゴン別頂点ＩＤとは、三角形のポリゴンと当該ポリゴン内における３つのいずれかの頂点順を特定する形式のものであり、ポリゴンＩＤに連続して３種の数字のうち１つを付加して構成される。起点頂点テーブルは、頂点座標テーブルと同サイズ、すなわち頂点座標テーブルに記録されている頂点ＩＤと同数の頂点ＩＤに対応してポリゴン別頂点ＩＤを１つずつ記録するサイズのテーブルとして用意される。
【００８７】
ステップＳ５２においては、まず、ポリゴンＩＤを“Ｐ１”に初期化した上で、頂点構成テーブルに記録されたポリゴン単位に、ポリゴンＩＤに対応する全ての（３つの）頂点ＩＤを取得し、その頂点ＩＤに対応付けて当該ポリゴンＩＤと各頂点順に対応する３つのポリゴン別頂点ＩＤを起点頂点テーブルに記録する。図２３（ａ）の頂点構成テーブルの先頭には、ポリゴンＰ１（ポリゴンＩＤが“Ｐ１”であるポリゴン）が記録されており、このポリゴンＰ１には、頂点順“０”“１”“２”に対応して頂点ＩＤ“０”“１”“２”が記録されているので、起点頂点テーブルの頂点ＩＤ“０”“１”“２”に対応付けて、ポリゴン別頂点ＩＤ“Ｐ１，０” “Ｐ１，１” “Ｐ１，２”を記録する。この結果、起点頂点テーブルは、図２４（ａ）に示すような状態となる。なお、ポリゴン別頂点ＩＤ“Ｐ１，０” “Ｐ１，１” “Ｐ１，２”の右端の数字は、頂点構成テーブルにおける頂点順を示しており、左端のものが“０”、中央のものが“１”、右端のものが“２”として記録される。なお、ポリゴン別頂点ＩＤ“Ｐ１，０” “Ｐ１，１” “Ｐ１，２”は、図１１に示される“Ｖ１ａ” “Ｖ１ｂ” “Ｖ１ｃ”と同一のものであるが、説明の便宜上、起点頂点テーブル、更新頂点テーブルにおいては、ポリゴンＩＤに頂点順を付加した形態としている。
【００８８】
続いてポリゴンＩＤをインクリメントすると、図２３（ａ）の頂点構成テーブルの例では、二番目のポリゴンＰ２（ポリゴンＩＤが“Ｐ２”であるポリゴン）が得られ、このポリゴンＰ２には、頂点順“０”“１”“２”に対応して頂点ＩＤ“０”“３”“１”が記録されている。頂点ＩＤ“０”“１”については、図２４（ａ）に示すように、既に起点頂点テーブルに記録されているので上書きしないようにし、起点頂点テーブルに記録されていない頂点ＩＤ“３”のみ に対応付けて、ポリゴン別頂点ＩＤ“Ｐ２，１”を起点頂点テーブルに記録する。この結果、起点頂点テーブルは、図２４（ｂ）に示すような状態となる。
【００８９】
更にポリゴンＩＤをインクリメントすると、図２３（ａ）の頂点構成テーブルの例では、三番目のポリゴンＰ３（ポリゴンＩＤが“Ｐ３”であるポリゴン）が得られ、このポリゴンＰ３には、頂点順“０”“１”“２”に対応して頂点ＩＤ“４”“５”“２”が記録されている。頂点ＩＤ“２”については、図２４（ｂ）に示すように、既に起点頂点テーブルに記録されているので上書きしないようにし、起点頂点テーブルに記録されていない頂点ＩＤ“４” “５”に対応付けて、ポリゴン別頂点ＩＤ“Ｐ３，０” “Ｐ３，１”を起点頂点テーブルに記録する。この結果、起点頂点テーブルは、図２４（ｃ）に示すような状態となる。
【００９０】
図２３（ａ）の頂点構成テーブルについて、ポリゴンＩＤをインクリメントし同様な処理を行って行くと、１５番目のポリゴンＰ１５（ポリゴンＩＤが“Ｐ１５”であるポリゴン）の頂点順“１”に対応する頂点ＩＤ“１３”に対応付けて、ポリゴン別頂点ＩＤ“Ｐ１５，１”を起点頂点テーブルに記録した時点で、全ての頂点ＩＤに対応するポリゴン別頂点ＩＤが記録される。この結果、起点頂点テーブルは、図２４（ｄ）に示すような状態となり、完成する。頂点構成テーブルにはまだ参照していない３つのポリゴンＩＤ“Ｐ１６”“Ｐ１７”“Ｐ１８”が存在するが、ポリゴンＩＤ“Ｐ１５”を参照した時点で起点頂点テーブルは完成したため、本処理は打ち切りとする。
【００９１】
起点頂点テーブルと並行して、更新頂点テーブルを作成する（ステップＳ５３）。図２５は、ステップＳ５３における更新頂点テーブルの変化の様子を示す図である。更新頂点テーブルは、図２５（ａ）〜図２５（ｄ）に示すように、起点頂点テーブルと同様、頂点ＩＤと、ポリゴン別頂点ＩＤが対応付けて記録されたテーブルである。更新頂点テーブルは、起点頂点テーブルと同仕様かつ同サイズのテーブルとして用意される。
【００９２】
ステップＳ５３においては、まず、頂点構成テーブルに記録されたポリゴン単位に、ポリゴンＩＤに対応する全ての（３つの）頂点ＩＤを取得し、その頂点ＩＤに対応付けて当該ポリゴンＩＤと各頂点順に対応する３つのポリゴン別頂点ＩＤを更新頂点テーブルに記録する。始めにポリゴンＩＤを“Ｐ１”に初期化すると、図２３（ａ）の頂点構成テーブルの先頭より、ポリゴンＰ１が取得され、このポリゴンＰ１には、頂点順“０”“１”“２”に対応して頂点ＩＤ“０”“１”“２”が記録されているので、更新頂点テーブルの頂点ＩＤ“０”“１”“２”に対応付けて、ポリゴン別頂点ＩＤ“Ｐ１，０” “Ｐ１，１” “Ｐ１，２”を記録する。この結果、更新頂点テーブルは、図２５（ａ）に示すような状態となる。この段階では、図２４（ａ）に示した起点頂点テーブルと同一内容である。
【００９３】
続いてポリゴンＩＤをインクリメントすると、図２３（ａ）の頂点構成テーブルの例では、二番目のポリゴンＰ２が得られ、このポリゴンＰ２には、頂点順“０”“１”“２”に対応して頂点ＩＤ“０”“３”“１”が記録されている。更新頂点テーブルにおいては、起点頂点テーブルの場合と異なり、既に所定の頂点ＩＤに対応してポリゴン別頂点ＩＤが記録されているか否かにかかわらず、当該ポリゴンＩＤの全ての頂点順“０”“１”“２”に対応する頂点ＩＤ“０”“３”“１”の各々に３つのポリゴン別頂点ＩＤ“Ｐ２，０”“Ｐ２，１” “Ｐ２，２”を上書き記録する。従って、頂点ＩＤ“３”に対応してポリゴン別頂点ＩＤ“Ｐ２，１”が新たに記録されるとともに、既に更新頂点テーブルに記録されている頂点ＩＤ“０”“１”については、ポリゴン別頂点ＩＤ“Ｐ２，０” “Ｐ２，２”が上書きされる。すなわち、これら２つのポリゴン別頂点ＩＤについては、最初のポリゴンＰ１の頂点としてではなく、新たなポリゴンＰ２の頂点として記録する。この結果、起点頂点テーブルは、図２５（ｂ）に示すような状態となる。
【００９４】
更にポリゴンＩＤをインクリメントすると、図２３（ａ）の頂点構成テーブルの例では、三番目のポリゴンＰ３が得られ、このポリゴンＰ３には、頂点順“０”“１”“２”に対応して頂点ＩＤ“４”“５”“２”が記録されている。更新頂点テーブルにおいては、新たな頂点ＩＤ“４”“５”については、前述のポリゴンＰ２の場合と同様、ポリゴン別頂点ＩＤ“Ｐ３，０”“Ｐ３，１”を新たに記録し、既に更新頂点テーブルに記録されている頂点ＩＤ“２”については、ポリゴン別頂点ＩＤ“Ｐ３，２”を上書き記録する。すなわち、ポリゴン別頂点ＩＤについては、最初のポリゴンＰ１の頂点としてではなく、新たなポリゴンＰ３の頂点として記録する。この結果、更新頂点テーブルは、図２５（ｃ）に示すような状態となる。
【００９５】
図２３（ａ）の頂点構成テーブルについて、ポリゴンＩＤをインクリメントし最後のポリゴンＩＤであるポリゴン１８まで同様な処理を行って行った場合、１８番目のポリゴンＰ１８の全ての頂点順“０”“１”“２”に対応する頂点ＩＤ“７”“１３”“８”に対応付けて、ポリゴン別頂点ＩＤ“Ｐ１８，０”“Ｐ１８，１”“Ｐ１８，２”を更新頂点テーブルに記録した時点で、全ての頂点ＩＤに対応するポリゴン別頂点ＩＤが更新記録される。この結果、更新頂点テーブルは、図２５（ｄ）に示すような状態となり、完成する。
【００９６】
ステップＳ５３においては、更新頂点テーブルの更新と並行して、頂点リンクテーブルへの記録を行う。これは、更新頂点テーブルの所定の頂点ＩＤに記録されているポリゴン別頂点ＩＤを上書きする際、上書き前のポリゴン別頂点ＩＤＰと上書きするポリゴン別頂点ＩＤＮとの間にリンクを設定し、頂点リンクテーブルに記録するもので、言い換えれば、ポリゴン別頂点ＩＤＰで特定されるポリゴンＰの頂点と同じ頂点ＩＤを共有し、頂点構成テーブルにおいて前記ポリゴンＰより後続に位置する最初のポリゴン別頂点ＩＤＮで特定されるポリゴンＮの頂点との間にリンクを設定することを意味する。図２６は、ポリゴンＰ２を更新頂点テーブルに記録した際における頂点リンクテーブルへの記録の様子を示す図である。図２６（ａ）（ｂ）は、それぞれ図２５（ａ）（ｂ）と同一のものである。ポリゴンＰ２について記録を行う場合、更新頂点テーブルでは、図２６（ａ）（ｂ）に示すように、頂点ＩＤ“０”“１”に対応するポリゴン別頂点ＩＤが上書き更新される。このときの頂点ＩＤ“０”“１”に対応する更新後におけるポリゴン別頂点ＩＤ“Ｐ２，０”“Ｐ２，２”をリンク先ポリゴン別頂点ＩＤとして、頂点ＩＤ“０”“１”に対応する更新前のポリゴン別頂点“Ｐ１，０”“Ｐ１，１”であるポリゴンＩＤ“Ｐ１”の頂点順“０”“１”に対応付けて頂点リンクテーブルに記録する。この結果、頂点リンクテーブルは、図２６（ｃ）に示すような状態となる。
【００９７】
図２７は、ポリゴンＰ３を更新頂点テーブルに記録した際における頂点リンクテーブルへの記録の様子を示す図である。図２７（ａ）（ｂ）は、それぞれ図２５（ｂ）（ｃ）と同一のものである。ポリゴンＰ３について記録を行う場合、更新頂点テーブルでは、図２７（ａ）（ｂ）に示すように、頂点ＩＤ“２”に対応するポリゴン別頂点ＩＤが上書き更新される。このときの頂点ＩＤ“２”に対応する更新後におけるポリゴン別頂点ＩＤ“Ｐ３，２”をリンク先ポリゴン別頂点ＩＤとして、頂点ＩＤ“２”に対応する更新前のポリゴン別頂点ＩＤ“Ｐ１，２”であるポリゴンＩＤ“Ｐ１”の頂点順“２”に対応付けて頂点リンクテーブルに記録する。この結果、頂点リンクテーブルは、図２７（ｃ）に示すような状態となる。
【００９８】
図２８は、ポリゴンＰ１８を更新頂点テーブルに記録した際における頂点リンクテーブルへの記録の様子を示す図である。図２８（ｂ）は、図２５（ｄ）と同一のものである。ポリゴンＰ１８について記録を行う場合、更新頂点テーブルでは、図２８（ａ）（ｂ）に示すように、頂点ＩＤ“７”“８”“１３”に対応するポリゴン別頂点ＩＤが上書き更新される。このときの頂点ＩＤ“７”“８”“１３”に対応する更新後におけるポリゴン別頂点ＩＤ“Ｐ１８，０”“Ｐ１８，２” “Ｐ１８，１”をリンク先ポリゴン別頂点ＩＤとして、頂点ＩＤ“７”“８”“１３”に対応する更新前のポリゴン別頂点ＩＤ“Ｐ１７，２”“Ｐ８，１” “Ｐ１７，１”であるポリゴンＩＤ“Ｐ８”の頂点順“１”および“Ｐ１７”の頂点順“１”“２”に対応付けて頂点リンクテーブルに記録する。この結果、頂点リンクテーブルは、図２８（ｃ）に示すような状態となる。同図の（０）から（１３）で示される１４個の欄はポリゴン別頂点ＩＤが記録されていない空欄で、頂点ＩＤ“０”から“１３”に対応する。
【００９９】
更新頂点テーブルの更新が完了し、それに伴う頂点リンクテーブルへの記録を終えたら、更新頂点テーブルと起点頂点テーブルを対応付けて頂点リンクテーブルを完成させる（ステップＳ５４）。これは、前記頂点リンクテーブルにおける空欄（図２８（ｃ）の例では１４個）を埋める処理で、空欄が残る理由は、更新頂点テーブルの最終形態で、各頂点ＩＤに記録されているポリゴン別頂点ＩＤＰで特定されるポリゴンＰより、後続に位置する同じ頂点ＩＤを共有するポリゴンが存在しないためである。そこで、更新頂点テーブルの最終形態で各頂点ＩＤに記録されているポリゴン別頂点ＩＤＰで特定されるポリゴンＰの頂点と同じ頂点ＩＤを共有し、頂点構成テーブルにおいて先頭より最初のポリゴン別頂点ＩＤＮで特定されるポリゴンＮの頂点との間にリンクを設定することを意味する。図２９は、頂点リンクテーブル完成時の様子を示す図である。図２９（ａ）の更新頂点テーブルは、ポリゴンＰ１８について記録を行った後の状態であり、図２８（ｂ）と同一のものである。図２９（ｂ）の起点頂点テーブルは、ポリゴンＰ１５について記録を行った後の状態であり、図２４（ｄ）と同一のものである。図２９（ａ）の更新頂点テーブル、図２９（ｂ）の起点頂点テーブルは、いずれも最終的な状態となっている。図２９（ａ）の更新頂点テーブルと図２９（ｂ）の起点頂点テーブルを頂点ＩＤごとに対応付けて、対応するポリゴン別頂点ＩＤで頂点リンクテーブルの空欄を埋めて行く。例えば、頂点ＩＤ“０”に対応する更新頂点テーブルのポリゴン別頂点ＩＤ“Ｐ７，２”であるポリゴンＩＤ“Ｐ７”の頂点順“２”の欄に、同頂点ＩＤに対応する起点頂点テーブルのポリゴン別頂点ＩＤ“Ｐ１，０”を記録する。この結果、頂点リンクテーブルは、図２９（ｃ）に示すような状態となる。
【０１００】
図３０は、以降の説明の都合上、図２９（ｃ）で最終的に得られた頂点リンクテーブルを書き直した図で内容的には図２９（ｃ）と同一である。図３０に示すように、頂点リンクテーブルはポリゴン単位で記録されている。各ポリゴン単位で記録された３つの頂点のうち上段がリンク元、下段がリンク先を示しており、３つの頂点はリンク元の頂点順に並んでいる。また、ポリゴン別頂点ＩＤの表記を図１１に示される形式に変えている。例えば、ポリゴンＰ１については、リンク元の３つのポリゴン別頂点ＩＤは頂点順に“Ｐ１，０”“Ｐ１，１”“Ｐ１，２”となるが、各々頂点Ｖ１ａ，Ｖ１ｂ，Ｖ１ｃと表記し直しており、リンク先の３つのポリゴン別頂点ＩＤは頂点順に“Ｐ２，０”“Ｐ２，２”“Ｐ３，２”となるが、それぞれ頂点Ｖ２ａ，Ｖ２ｃ，Ｖ３ｃと表記し直している。図１１に示したように、頂点Ｖ１ａ（図１１では“Ｄ”とも表記）と同一座標には、頂点Ｖ２ａ以外にも、Ｖ４ｂ，Ｖ５ｃ，Ｖ６ｃ，Ｖ７ｃが存在しているが、頂点リンクテーブルには１つだけ記録されるため図３０では、頂点Ｖ１ａを含むポリゴンＰ１に、頂点座標配列データ上で最も近いポリゴンＰ２に含まれる頂点Ｖ２ａのみとなっている。ただし、頂点Ｖ７ｃを含むポリゴンＰ７に、頂点座標配列データ上で最も近いポリゴンは、後続には存在しないため、先頭に戻ってポリゴンＰ１に含まれる頂点Ｖ１ａとする。
【０１０１】
結局、ステップＳ２１においては、対象頂点（例えば“Ｖ１ａ”）と頂点ＩＤ（例えば“０”）が同一となる後続のポリゴンの頂点（例えば“Ｖ２ａ，Ｖ４ｂ，Ｖ５ｃ，Ｖ６ｃ，Ｖ７ｃ”）を探索し、最初に探索された単一のポリゴンの頂点（例えば“Ｖ２ａ”）と対象頂点（例えば“Ｖ１ａ”）を対応付けて、頂点リンクテーブルを作成し、対象頂点（例えば“Ｖ７ｃ”）のように頂点ＩＤ（例えば“０”）が同一となる後続のポリゴンが存在しない場合、先頭に戻って最初のポリゴンの頂点（例えば“Ｖ１ａ”）を対応付けて、頂点リンクテーブルを作成している。末端において例外処理を伴うものの、基本的に前方ではなく後続のポリゴンの頂点を探索するため、データを昇順で処理することができ、効率的な処理を行うことが可能となる。
【０１０２】
頂点リンクテーブルが作成されたら、削除対象ポリゴン選定手段４０が、ポリゴンモデルを構成する全ポリゴンを対象として、各ポリゴンの面積および周長を算出する（ステップＳ２２）。次に、削除対象ポリゴン選定手段４０は、算出された面積と周長を乗じた値が最小となるポリゴンを削除対象ポリゴンとして選定する（ステップＳ２３）。図１０の例では、図１０（ｂ）に示すように、３個の頂点Ｅ、Ｊ、Ｋで構成されるポリゴンＥＪＫ（ポリゴンＰ１０）が削除対象ポリゴンとして選定される。
【０１０３】
続いて、削除対象ポリゴン選定手段４０が削除対象ポリゴンの３辺のうち最短の１辺を削除対象辺として選定し、選定した削除対象辺の中点を算出する（ステップＳ２４）。図１０の例では、図１０（ｃ）に示すように、削除対象ポリゴンＥＪＫの辺ＪＫが削除対象辺として選定される。削除対象辺ＪＫの２点Ｊ，Ｋはともに補正対象頂点となる。さらに、辺ＪＫの中点Ｏの座標を算出する。当然ながら、中点Ｏの座標は、頂点Ｊと頂点Ｋの２頂点の座標の平均値として算出される。
【０１０４】
次に、共有頂点探索手段５０が、選定された削除対象辺の両端である２つの補正対象頂点を起点に頂点リンクテーブルを用いて共有頂点を順次探索する（ステップＳ２５）。共有頂点とは、補正対象頂点と同一座標を共有する頂点である。上述の例では、削除対象辺ＪＫの２頂点Ｊ（Ｖ１０ａ）、Ｋ（Ｖ１０ｂ）を起点に図３０の頂点リンクテーブルを参照すると、ポリゴンＰ１０の２頂点のリンク先として、それぞれリンク先として頂点Ｖ１４ｂ，Ｖ１１ａがそれぞれ検出される。検出された頂点が存在するポリゴンを探すと、図３１に示すように、頂点Ｖ１４ｂはポリゴンＰ１４の頂点として存在し、頂点Ｖ１１ａはポリゴンＰ１１の頂点として存在する。ポリゴンＰ１４では、頂点Ｖ１４ｂのリンク先として頂点Ｖ１５ｃが記録され、ポリゴンＰ１１では、頂点Ｖ１１ａのリンク先として頂点Ｖ１６ｃが記録されている。このようにして、順次リンクされた頂点を探索していく。すると、図３１において矢印で結んだように、頂点Ｖ１０ａについては、Ｖ１４ｂ，Ｖ１５ｃ，Ｖ１６ａ，Ｖ９ａ，Ｖ１０ａと探索されて、頂点Ｖ１０ａ自身に戻る。また、頂点Ｖ１０ｂについては、Ｖ１１ａ，Ｖ１６ｃ，Ｖ１７ａ，Ｖ１０ｂと探索されて、頂点Ｖ１０ｂ自身に戻る。すなわち、共有頂点として、Ｖ１４ｂ，Ｖ１５ｃ，Ｖ１６ａ，Ｖ９ａ，Ｖ１１ａ，Ｖ１６ｃ，Ｖ１７ａが検出されることになる。
【０１０５】
そして、ポリゴンモデル更新手段６０が、順次探索されて検出された共有頂点の座標を、全て算出された中点の座標に変更し、頂点リンクテーブルの更新を行う（ステップＳ２６）。上記の例では、頂点Ｖ１０ａ、および頂点Ｖ１０ａと同一座標のＶ１４ｂ，Ｖ１５ｃ，Ｖ１６ａ，Ｖ９ａと、頂点Ｖ１０ｂ、および頂点Ｖ１０ｂと同一座標のＶ１１ａ，Ｖ１６ｃ，Ｖ１７ａを全て中点Ｏの座標値（Ｘｏ，Ｙｏ，Ｚｏ）に変更する。この結果、頂点座標配列データは、図３２に示すように変更される。図３２に示すように、ポリゴンＰ１０では、２つの頂点Ｖ１０ａ，Ｖ１０ｂの座標値がともに（Ｘｏ，Ｙｏ，Ｚｏ）となって同一になるため、ポリゴンＰ１０は存在できなくなり、削除されたことになる。同様に、ポリゴンＰ１６では、２つの頂点Ｖ１６ａ，Ｖ１６ｃの座標値がともに（Ｘｏ，Ｙｏ，Ｚｏ）となって同一になるため、ポリゴンＰ１６は存在できなくなり、削除されたことになる。
【０１０６】
検出された全ての共有頂点の座標値を中点の座標値に変更したら、頂点リンクテーブルの更新を行う。具体的には、削除対象ポリゴン（上記の例ではポリゴンＰ１０とポリゴンＰ１６）の２つの補正対象頂点をそれぞれ頂点α（上記の例では頂点Ｖ１０ａとＶ１６ａ）および頂点β（上記の例では頂点Ｖ１０ｂとＶ１６ｃ）とすると、削除対象ポリゴンの頂点αに対してリンク先を設定している他のポリゴンの頂点に対して、リンク先を削除対象ポリゴンの頂点βに補正し、削除対象ポリゴンの頂点βに対してリンク先を設定している他のポリゴンの頂点に対して、リンク先を削除対象ポリゴンの頂点αに補正する。すなわち、頂点リンクテーブルにおいて、リンク先として設定されている２つの補正対象頂点を互いに入れ替える処理を行う。これにより、削除対象ポリゴンの頂点αおよび頂点βを含む２つのリンクのループが１つのループに統合される。
【０１０７】
図３３の例では、ポリゴンＰ９に記録されていた頂点Ｖ１０ａと、ポリゴンＰ１７に記録されていた頂点Ｖ１０ｂを入れ替えている。この結果、ポリゴンＰ１０の頂点Ｖ１０ａを起点として探索すると、頂点Ｖ１０ｂを経由してポリゴンＰ１０の頂点Ｖ１０ａに戻ってくる。これを矢印で示すと、図３３に示すように全体が１つのループになる。座標の変更前は、図３１に示すように、頂点Ｖ１０ａを起点として探索すると、実線の矢印で示すように、頂点Ｖ１０ｂを経由せずポリゴンＰ１０の頂点Ｖ１０ａに戻っていた。また、頂点Ｖ１０ｂを起点として探索すると、破線の矢印で示すように、頂点Ｖ１０ａを経由せずポリゴンＰ１０の頂点Ｖ１０ｂに戻っていた。すなわち、図３１に示すように、実線のループと破線のループの２つのループになっていた。一方、図３３に示すように、削除対象辺の２つの頂点が１つのループで結ばれることにより、以降の処理において、本ループを通るいずれかの頂点が削除対象頂点に選定され所定の座標値に更新されると、本ループを通る全ての頂点の座標値が一斉に同一の座標値に更新されるようになり、更に本ループはもう一方の削除対象頂点を通るループと１つのループに統合することになる。
【０１０８】
頂点リンクテーブルの更新は、図３３に示した状態に留めておいてもよいが、さらに進めて削除されたポリゴンを構成する頂点がリンクから外れるように、削除されたポリゴン内の頂点に対するリンク先を前記頂点に設定されている他のポリゴンの頂点へのリンク先に変更するようにしてもよい。すなわち、ループ内の一部のリンクが削除されるポリゴンの各頂点をバイパスするようにリンク先の変更を行う。具体的には、ポリゴンモデル更新手段６０により削除されたポリゴンの各頂点をリンク先として設定されているリンク元の他のポリゴンの頂点のリンク先を、前記削除されたポリゴンの各頂点に設定されている前記他のポリゴンとは異なる別のポリゴンのリンク先の頂点に変更する。図１１の例では、ポリゴンモデル更新手段６０により削除されたポリゴンとして、削除対象ポリゴンであるポリゴンＰ１０、削除対象辺の中点に座標が変更された共有頂点を２つ以上含むことにより削除対象ポリゴンとともに削除されたポリゴンＰ１６がある。したがって、図３４の例では、下線を付したように、ポリゴンＰ９の頂点Ｖ９ａ，Ｖ９ｂのリンク先をそれぞれＶ１０ｂ，Ｖ１０ｃよりＶ１１ａ，Ｖ１１ｃに変更し、ポリゴンＰ１１の頂点Ｖ１１ａのリンク先をＶ１６ｃよりＶ１７ａに変更し、ポリゴンＰ１５の頂点Ｖ１５ｂ，Ｖ１５ｃのリンク先をそれぞれＶ１６ｂ，Ｖ１６ａよりＶ１７ｂ，Ｖ９ａに変更し、ポリゴンＰ１７の頂点Ｖ１７ａのリンク先をＶ１０ａよりＶ１４ｂに変更する。
【０１０９】
頂点リンクテーブルの更新が行われたら、頂点座標配列データの更新を行う（ステップＳ２７）。具体的には、まず、２つの頂点の座標値が同一となったポリゴンを頂点座標配列データから削除する。したがって、図３２に示した頂点座標配列データでは、ポリゴンＰ１０とポリゴンＰ１６が削除される。さらに、１頂点が更新されたポリゴンについては、面積および周長の再計算を行う。
【０１１０】
図１０の例では、図１０（ｃ）と図１０（ｄ）を比較するとわかるように、ポリゴンＥＨＪ→ポリゴンＥＨＯ、ポリゴンＥＦＫ→ポリゴンＥＦＯ、ポリゴンＨＪＭ→ポリゴンＨＯＭ、ポリゴンＪＭＮ→ポリゴンＯＭＮ、ポリゴンＦＫＮ→ポリゴンＦＯＮに変更される。この結果、図１０の例では、図１０（ａ）の時点では、１８個あったポリゴンが、図１０（ｄ）の時点では、１６個に削減される。
【０１１１】
ステップＳ２７の処理を終えたら、制御手段１０が、削減後の全ポリゴン数が、設定された目標値以下となっているか否かを判定する（ステップＳ２８）。目標値としては、事前に任意の値を設定することができる。判定の結果、全ポリゴン数が目標値以下となっていない場合は、ステップＳ２３に戻って、削除対象ポリゴン選定手段４０が、残っているポリゴンの中から、面積と周長を乗じた値が最小となるポリゴンを削除対象ポリゴンとして選定する。ステップＳ２８における判定の結果、全ポリゴン数が目標値以下である場合は、ポリゴン削減処理を終了する。図１３のフローチャートに従った処理を実行することにより、各グループについて設定された目標値以下になるように、ポリゴン数が削減されることになる。頂点リンクテーブルが作成されていなければ、削除対象ポリゴンの削除対象辺の２頂点と同一座標となる共有頂点の探索に大きな処理負荷を要することになる。頂点リンクテーブルを作成することにより、処理負荷を大幅に削減することが可能となる。
【０１１２】
＜２．５．小体積グループ削除処理＞
次に、ステップＳ４０におけるグループ合成手段７０による隔離された小体積グループの削除処理について説明する。ここで、隔離された小体積グループの削除処理の説明に先立ち、隔離された小体積グループの削除処理を行う理由について説明しておく。図３５は、ポリゴン削減処理により生じる問題を説明するための図である。図３５（ａ）は、ステップＳ１０のグループ分類処理を終えた直後の２グループのポリゴン群を示している。図３５（ａ）の例では、頂点Ｄ、Ｅ、Ｋを含む左側のグループと、頂点Ｄ’、Ｅ’、Ｋ’を含む右側のグループが存在する。頂点ＤとＤ’、頂点ＥとＥ’、頂点ＫとＫ’がそれぞれ３Ｄプリンタの解像度以下である場合、この２グループのポリゴン群を３Ｄプリンタで出力すると、頂点ＤとＤ’、頂点ＥとＥ’、頂点ＫとＫ’は樹脂等により連結され、２グループは連結した物体として出力される。すなわち、２グループは物理的には接着されている。
【０１１３】
図３５（ａ）に示した右側のグループのポリゴン群に対して、ステップＳ２０におけるポリゴン削減処理を実行すると、図３５（ｂ）に示すように、ポリゴンＥ’ＦＫ’が削除対象ポリゴンとして選定される。さらに、図３５（ｃ）に示すように、削除対象ポリゴンＥ’ＦＫ’の最短辺Ｅ’Ｆが削除対象辺として選定され、辺Ｅ’Ｆの中点Ｏが算出される。そして、図３５（ｄ）に示すように、削除対象ポリゴンＥ’ＦＫ’と、削除頂点共有ポリゴンＤ’Ｅ’Ｆが削除される。
【０１１４】
図３５（ａ）と図３５（ｄ）を比較するとわかるように、左右の２つのグループは、ポリゴン削減処理前に比べて、ポリゴン削減処理後には、より離れてしまっている。図３５（ｄ）に示した２グループの距離が、３Ｄプリンタの解像度を超えると、２グループのポリゴン群を３Ｄプリンタで出力した場合、２グループは別の物体として出力される。２つのグループがともに大きな物体となれば、問題はない。しかし、一つが非常に小さな物体となる場合、例えば、一方のグループが本体であって、他方のグループが本体に付属するヒゲのようなものである場合、本体と別に出力されたヒゲは、３Ｄプリンタ内に紛れ込み、機械詰まり等の問題を引き起こす恐れがある。このような問題を除去するため、上述のヒゲのような隔離された小体積グループの削除処理を行うのである。
【０１１５】
図３６は、グループ合成手段７０による隔離された小体積グループの削除処理（Ｓ４０）の詳細を示すフローチャートである。グループ合成手段７０は、まず、グループごとに全ポリゴンの全頂点を対象として、Ｘ、Ｙ、Ｚぞれぞれの方向の最大値および最小値を算出する（ステップＳ４１）。この結果、グループｇに対して、最小値Ｘｍｉｎ（ｇ）、最大値Ｘｍａｘ（ｇ）、最小値Ｙｍｉｎ（ｇ）、最大値Ｙｍａｘ（ｇ）、最小値Ｚｍｉｎ（ｇ）、最大値Ｚｍａｘ（ｇ）が得られる。次に、グループ合成手段７０は、グループごとに外接直方体の体積を算出する（ステップＳ４２）。具体的には、以下の〔数式３〕に従った処理を実行することにより、グループｇの外接直方体の体積Ｖ（ｇ）を算出する。
【０１１６】
〔数式３〕
Ｖ（ｇ）＝（Ｘｍａｘ（ｇ）−Ｘｍｉｎ（ｇ））×（Ｙｍａｘ（ｇ）−Ｙｍｉｎ（ｇ））×（Ｚｍａｘ（ｇ）−Ｚｍｉｎ（ｇ））
【０１１７】
グループ合成手段７０は、全グループに対してステップＳ４１、Ｓ４２の処理を実行する。これにより、全グループについて、外接直方体の体積が得られる。次に、グループ合成手段７０は、全グループの中で外接直方体の体積が最小となるグループを特定する（ステップＳ４３）。そして、グループ合成手段７０は、特定したグループと他の全てのグループとの最小間隔を算出する（ステップＳ４４）。ステップＳ４４における最小間隔の算出処理の詳細については後述する。
【０１１８】
続いて、グループ合成手段７０は、ステップＳ４４において算出された最小間隔が所定のしきい値以上か否かを判定する（ステップＳ４５）。最小間隔と比較するための所定のしきい値としては、３Ｄプリンタ出力時に０．２ｍｍに相当する数値とすることが好ましい。判定の結果、最小間隔が所定のしきい値以上である場合は、体積最小のグループが、最も近いグループとも所定の距離以上離れていることになるので、グループ合成手段７０は、体積最小のグループを削除する処理を行う（ステップＳ４６）。ステップＳ４５における判定の結果、最小間隔が所定のしきい値未満である場合は、体積最小のグループが、最も近いグループと３Ｄプリンタの解像度以下に近接していることになるので、グループ合成手段７０は、体積最小のグループを削除する処理を行わない。
【０１１９】
ステップＳ４６におけるグループの削除を行った場合、削除を行わなかった場合のいずれにおいても、そのグループについては処理済みとする。そして、ステップＳ４３に戻って、未処理のグループの中で外接直方体の体積が最小となるグループを特定する。ステップＳ４３〜ステップＳ４６の処理を繰り返し、全てのグループに対する処理を終えたら、隔離された小体積グループの削除処理を終了する。
【０１２０】
ステップＳ４４における最小間隔の算出処理の詳細について説明する。図３７は、図３６のステップＳ４４における最小間隔の算出処理の詳細を示すフローチャートである。グループ合成手段７０は、初期値として、最小間隔を示す変数ｄｍｉｎに所定以上の値を設定する。ｄｍｉｎに与える初期値としては、グループ間の最小間隔としてあり得ない大きな値を設定しておけばよい。そして、グループ合成手段７０は、全グループの中から、グループｇより体積が大きい１つのグループｈを抽出する（ステップＳ４７）。この結果、グループｈについて、最小値Ｘｍｉｎ（ｈ）、最大値Ｘｍａｘ（ｈ）、最小値Ｙｍｉｎ（ｈ）、最大値Ｙｍａｘ（ｈ）、最小値Ｚｍｉｎ（ｈ）、最大値Ｚｍａｘ（ｈ）が得られる。次に、グループ合成手段７０は、Ｘ、Ｙ、Ｚの各方向別に２グループ間の差分の最小値を算出する（ステップＳ４８）。具体的には、以下の〔数式４〕に従った処理を実行することにより、Ｘ方向の差分の最小値ｄｘ、Ｙ方向の差分の最小値ｄｙ、Ｚ方向の差分の最小値ｄｚを算出する。
【０１２１】
〔数式４〕
ｄｘ＝Ｍｉｎ｛｜Ｘｍａｘ（ｇ）−Ｘｍｉｎ（ｈ）｜，｜Ｘｍｉｎ（ｇ）−Ｘｍａｘ（ｈ）｜｝
ｄｙ＝Ｍｉｎ｛｜Ｙｍａｘ（ｇ）−Ｙｍｉｎ（ｈ）｜，｜Ｙｍｉｎ（ｇ）−Ｙｍａｘ（ｈ）｜｝
ｄｚ＝Ｍｉｎ｛｜Ｚｍａｘ（ｇ）−Ｚｍｉｎ（ｈ）｜，｜Ｚｍｉｎ（ｇ）−Ｚｍａｘ（ｈ）｜｝
【０１２２】
続いて、グループ合成手段７０は、算出された方向別最小値のうち最大のものをグループ間最小値とし、グループ間最小値を、既に処理済みの他のグループ間における全グループ間最小値と比較し、小さい方を全グループ間最小値とする処理を行う（ステップＳ４９）。具体的には、ステップＳ４８において算出された３つの方向別最小値ｄｘ、ｄｙ、ｄｚのうち、最大の値をとるグループ間最小値Ｍａｘ（ｄｘ、ｄｙ、ｄｚ）とｄｍｉｎを比較し、Ｍａｘ（ｄｘ、ｄｙ、ｄｚ）＜ｄｍｉｎの場合、ｄｍｉｎ＝Ｍａｘ（ｄｘ、ｄｙ、ｄｚ）とする。これにより、ｄｍｉｎには、グループ間最小値の中で最小の値となる全グループ間最小値が記録されることになる。
【０１２３】
ステップＳ４７、Ｓ４８、Ｓ４９の処理を繰り返して実行し、グループｇより体積が大きい全てのグループに対する処理を終えたら、図３７に示した最小間隔の算出処理を終了し、図３６のステップＳ４５に進んで、最小間隔ｄｍｉｎとしきい値との比較を行うことになる。
【０１２４】
＜２．６．ポリゴンモデルの合成＞
図９の処理概要に示したように、ステップＳ５０においては、グループ合成手段７０が、全グループのポリゴンモデルの合成を行って更新された領域別ポリゴンモデルを得る。また、ステップＳ７０においては、ポリゴンモデル合成手段８０が、全領域の領域別ポリゴンモデルの合成を行って合成ポリゴンモデルを得る。いずれの合成処理も、ヘッダ部を除く領域別ポリゴンモデルを単純に結合し、ヘッダ部に合算されたポリゴン数を記録することにより行われる（ただし、これはバイナリ形式のSTLフォーマットの場合で、ASCII形式の場合はヘッダ部にポリゴン数を記録しないため、ヘッダ部を除く領域別ポリゴンモデルを単純に結合するだけでよい）。合成ポリゴンモデル記憶手段１００に記憶された合成ポリゴンモデルを３Ｄプリンタ７に出力することにより、３Ｄプリンタ７は効率的に立体物を造形することができる。造形された立体物については、ほとんど劣化は見られなかった。
【０１２５】
＜３．変形例等＞
以上、本発明の好適な実施形態について説明したが、本発明は上記実施形態に限定されず、種々の変形が可能である。例えば、上記実施形態では、処理対象のポリゴンを三角形としたが、四角形以上の多角形であってもよい。
【０１２６】
また、上記実施形態では、ポリゴンに対して面積と周長を算出し、面積と周長の積が最小となるポリゴンを削除対象ポリゴンとして選定するようにしたが、周長を用いず面積のみを用いるようにしてもよい。
【０１２７】
また、上記実施形態では、複数のグループの更新されたポリゴンモデルに対して、外接直方体の体積が所定のしきい値未満であるものを削除するようにしたが、削除しないようにすることも可能である。
【符号の説明】
【０１２８】
１・・・ＣＰＵ（Central Processing Unit）
２・・・ＲＡＭ（Random Access Memory）
３・・・記憶装置
４・・・キー入力Ｉ／Ｆ
５・・・データ入出力Ｉ／Ｆ
６・・・表示部
７・・・３Ｄプリンタ（立体物造形装置）
７ａ・・・データ処理部
７ｂ・・・出力部
１０・・・制御手段
２０・・・グループ分類手段
３０・・・頂点リンクテーブル作成手段
４０・・・削除対象ポリゴン選定手段
５０・・・共有頂点探索手段
６０・・・ポリゴンモデル更新手段
７０・・・グループ合成手段
８０・・・ポリゴンモデル合成手段
９０・・・領域別ポリゴンモデル記憶手段
１００・・・合成ポリゴンモデル記憶手段
２００・・・立体物造形用データ削減装置
【図１】
0006613727.tif 000002
【図２】
0006613727.tif 000003
【図３】
0006613727.tif 000004
【図４】
0006613727.tif 000005
【図５】
0006613727.tif 000006
【図６】
0006613727.tif 000007
【図７】
0006613727.tif 000008
【図８】
0006613727.tif 000009
【図９】
0006613727.tif 000010
【図１０】
0006613727.tif 000011
【図１１】
0006613727.tif 000012
【図１２】
0006613727.tif 000013
【図１３】
0006613727.tif 000014
【図１４】
0006613727.tif 000015
【図１５】
0006613727.tif 000016
【図１６】
0006613727.tif 000017
【図１７】
0006613727.tif 000018
【図１８】
0006613727.tif 000019
【図１９】
0006613727.tif 000020
【図２０】
0006613727.tif 000021
【図２１】
0006613727.tif 000022
【図２２】
0006613727.tif 000023
【図２３】
0006613727.tif 000024
【図２４】
0006613727.tif 000025
【図２５】
0006613727.tif 000026
【図２６】
0006613727.tif 000027
【図２７】
0006613727.tif 000028
【図２８】
0006613727.tif 000029
【図２９】
0006613727.tif 000030
【図３０】
0006613727.tif 000031
【図３１】
0006613727.tif 000032
【図３２】
0006613727.tif 000033
【図３３】
0006613727.tif 000034
【図３４】
0006613727.tif 000035
【図３５】
0006613727.tif 000036
【図３６】
0006613727.tif 000037
【図３７】
0006613727.tif 000038