(57)【要約】【課題】  複数の正多角形の穴を有する平面領域の三角形メッシュデータのサイズを三角形メッシュ数に比例しないように圧縮すると共に、圧縮済データの伸長時間を短縮する。【解決手段】  平面領域Ｐの外部境界線L0〜L3上の頂点D0〜D3の座標データと、３つの正多角形C0〜C2の重心座標データ、半径値データ、及び頂点数データとを格納することにより、データサイズを三角形メッシュ数に比例しないように圧縮する。伸長するときは、頂点D0〜D3の座標データを読み込んで外部境界線L0〜L3を生成し、正多角形の重心座標データ、半径値データ、及び頂点数データを読み込んで正多角形C0〜C2を生成し、外部境界線L0〜L3及び正多角形C0〜C2の全ての辺を利用して平面領域Ｐを複数の三角形に分割する。【選択図】  図８
2006302188.tif 000002
【特許請求の範囲】
【請求項１】
３次元形状モデルの表面を構成する複数の正多角形の穴を有する平面領域を表示するための三角形メッシュデータを圧縮する装置であって、
三角形メッシュデータ源から前記平面領域の外部境界線上の頂点座標データを読み込む手段と、前記三角形メッシュデータ源から前記正多角形の頂点座標データ及び頂点数データを読み込む手段と、前記正多角形の頂点座標データに基づいて、前記正多角形の重心座標データ及び半径データを算出する手段と、前記外部境界線上の頂点座標データ、並びに前記正多角形の重心座標データ、半径データ及び頂点数データを圧縮済データ記憶装置に格納する手段とを備えたことを特徴とする三角形メッシュデータ圧縮装置。
【請求項２】
３次元形状モデルの表面を構成する複数の正多角形の穴を有する平面領域を表示するための三角形メッシュデータのデータ構造であって、
前記平面領域の外部境界線上の頂点座標データが配列される境界座標配列と、前記正多角形の重心座標データが配列される重心座標配列と、前記正多角形の半径値データが配列される半径値配列と、前記正多角形の頂点数データが配列される頂点数配列とを備えたことを特徴とする三角形メッシュデータのデータ構造。
【請求項３】
３次元形状モデルの表面を構成する複数の正多角形の穴を有する平面領域を表示するための圧縮済三角形メッシュデータを伸長する装置であって、
前記圧縮済データ中の前記平面領域の外部境界線上の頂点座標データを読み込み、前記外部境界線を生成する手段と、前記圧縮済データ中の前記正多角形の重心座標データ、半径値データ、及び頂点数データを読み込み、前記正多角形を生成する手段と、前記外部境界線及び正多角形の全ての辺を利用して前記平面領域を複数の三角形に分割する手段とを備えたことを特徴とする三角形メッシュデータ伸長装置。
【請求項４】
３次元形状モデルの表面を構成する複数の正多角形の穴を有する平面領域を三角形に分割する装置であって、
前記平面領域の外部境界線上の頂点と前記正多角形の重心とを直線で結ぶことで前記平面領域を複数の外部三角形に分割する手段と、該複数の外部三角形の各々の内部に、前記正多角形の頂点を少なくとも一つの頂点とし、前記平面領域の境界線上の頂点を残りの頂点とする内部三角形を生成する手段と、前記外部三角形、内部三角形及び正多角形のそれぞれの辺により区画される矩形状領域をその対角線により２つの三角形状領域に分割する手段と、該三角形状領域を複数の三角形に分割する手段とを有することを特徴とする三角形分割装置。
【請求項５】
コンピュータを請求項１記載の三角形メッシュデータ圧縮装置の各手段、又は請求項３記載の三角形メッシュデータ伸長装置の各手段、又は請求項４記載の三角形分割装置の各手段として機能させるためのプログラム。
【請求項６】
コンピュータを請求項１記載の三角形メッシュデータ圧縮装置の各手段、又は請求項３記載の三角形メッシュデータ伸長装置の各手段、又は請求項４記載の三角形分割装置の各手段として機能させるためのプログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元形状モデルを表示するために用いられる三角形メッシュデータの圧縮装置及び伸長装置に関し、詳細には、３次元形状モデルの表面を構成する複数の正多角形の穴を有する平面領域を表示するための三角形メッシュデータを効率的に圧縮及び伸長することが可能な圧縮装置及び伸長装置に関する。
【背景技術】
【０００２】
自由曲面は３次元形状モデルを表現する手段として、ＣＡＤ（Computer Aided Design）等で広く利用されている。３次元形状モデルを表示するためには、自由曲面をパーソナルコンピュータ等の標準グラフィックスライブラリであるＯｐｅｎＧＬで表示可能な三角形メッシュ形式のデータ（以下、三角形メッシュデータ）に変換することが一般的である。この変換処理には時間がかかるため、予め３次元形状モデルを三角形メッシュデータに変換したものを自由曲面データと共に保持することが広く行われている。
【０００３】
また、近年は、カタログや部品の配置が目的で、変形のできない３次元形状モデルの専用ビューワ（３Ｄビューワ）も普及し始めている。このビューワは、自由曲面を三角形メッシュデータに変換して、ビューワ専用ファイルに格納しており、一旦ＣＡＤファイルからビューワ専用ファイルに変換しておくことで、毎回の変換プロセスを省略でき、ＣＡＤよりも高速な表示を実現している。
【０００４】
このような三角形メッシュデータのデータサイズが大きいと、ファイルからメモリにダウンロードする際、或いはネットワークへ転送する際に時間がかかるため、三角形メッシュデータのデータサイズを圧縮することが提案されている（特許文献１〜７参照）。
【０００５】
特許文献１には、三角形メッシュの頂点位置における座標を表す頂点座標テーブルと、三角形メッシュ上の領域ごとの曲面情報を表す曲面情報テーブルと、境界ポリラインを表す頂点座標インデックス配列と、三角形メッシュを表す頂点座標インデックス配列とを含み、ｎ次元空間の曲面から生成された三角形メッシュデータを格納するようにすることで、データサイズが増大してもハードディスク等の保存装置のスペース効率、表示速度および転送速度を低下させることなく、ｎ次元空間の三角形メッシュデータの圧縮、保存、転送、伸張の処理を施すことができるデータ構造が開示されている。
【０００６】
また、特許文献２には、三角形メッシュのデータ構造を、頂点座標テーブルと法線ベクトルテーブルと曲面情報テーブルと頂点座標インデックステーブルと法線ベクトルインデックステーブルとから構成すると共に、頂点座標テーブルは三角形メッシュの頂点位置における座標の情報から、法線ベクトルテーブルは三角形メッシュの頂点位置における法線ベクトルの情報から、曲面情報テーブルは三角形メッシュ上の領域ごとの曲面情報（曲面が所定の曲面かを判定する情報を含む）からなり、頂点座標インデックステーブルは頂点座標のインデックスを、法線ベクトルインデックステーブルは法線ベクトルのインデックスを格納してなる、非対称な位相又は非一様な密度の三角形メッシュのデータを圧縮・伸長した際の法線ベクトルの誤差を小さくするデータ構造が開示されている。
【０００７】
さらに、特許文献３には、ｎ次元空間の頂点座標を表す座標テーブルと、三角形メッシュ（ポリゴン・メッシュ）を表す三角形メッシュテーブルと、領域に割り当てられたワイヤフレーム及び独立したワイヤフレームを区別して表すワイヤフレームテーブルとから構成され、データサイズが増大した場合でも、保存装置のスペース効率、表示速度、及び転送速度を低下させずに、ワイヤフレームを含んだ三角形メッシュデータに圧縮，保存，転送，伸長等の処理を施せるデータ構造が開示されている。
【０００８】
また、特許文献４には、物体の網目（メッシュ）表示を圧縮及び再構成する方法として、選択された頂点及び関連される辺が網目（メッシュ）から除去され、生じた孔が三角形でパッチされ、各パッチについて、除去された頂点の座標の近似値が計算され、除去された頂点の座標とその近似値との間の差がセーブされ、パッチ三角形は着色符号化されるようにした圧縮アルゴリズムが必要により繰り返される圧縮方法と、オリジナル網目（メッシュ）表示を再構成するために、各パッチについて、除去された頂点の座標の近似値が計算され、その近似値と除去された頂点の座標との間の差が計算されて頂点を再構成し、再構成された頂点をパッチの頂点に接続して除去された辺を再構成する再構成方法とが開示されている。
【０００９】
さらに、特許文献５には、立体の表面形状を複数ポリゴンからなるポリゴン・メッシュで近似したデータをメモリに取り込み、前記ポリゴン・メッシュに関する所定の情報から任意形状適合ウエーブレット変換器、及び適応的算術符号化器による効率的な圧縮、復元が可能な２次元構造化データを形成する構造化ポリゴン・メッシュ・データの形成装置において実行する構造化ポリゴン・メッシュ・データの形成方法は、前記メモリに取り込んだデータを読み出し、前記ポリゴン・メッシュの頂点であるポリゴン頂点の各々と２次元座標上の格子点であるノードの各々とを、前記任意形状適合ウエーブレット変換器、及び適応的算術符号化器が処理可能なデータとして、対応付ける連結性マップを作成するステップと、前記連結性マップのデータを読み出して、当該連結性マップにおいて対応付けされた、各ポリゴン頂点と各ノードとの関係に基き、前記各ポリゴン頂点に関する所定の情報を、前記２次元座標上の前記各ノードに対応させた前記２次元構造化データとして、前記任意形状適合ウエーブレット変換器、及び適応的算術符号化器が処理可能なデータ配列を形成するステップと、を有し、前記対応付けのステップは所定のポリゴン頂点と前記２次元座標上の複数ノードとを、前記任意形状適合ウエーブレット変換器、及び適応的算術符号化器が処理可能なデータとして対応付ける複数対応付けができるステップである構成とすることで、視覚情報の通信において、十分な品質を持った画像や映像をストレスを伴わない時間内に伝送すること、及び利用者の意図に沿った視点移動や奥行きの把握が可能なシステムの開発など利便性の向上を可能にしたものが開示されている。
【００１０】
また、特許文献６には、ソリッド・モデル及びサーフェス・モデルを含む３次元形状モデルの無損失のデータ圧縮を実現、及びより多様な形状モデルの位相構造に対応できるデータ圧縮方法が開示されている。このデータ圧縮方法では、最初に圧縮対象の３次元形状モデルに位相変形操作を施し、三角形メッシュを生成する。このように三角形メッシュを生成することで、従来既知の三角形メッシュ・モデルを圧縮する手法を用いることができる。また、位相変形操作の逆操作を実施するために必要な操作関連データを作成する。これにて３次元形状モデルの位相データの圧縮が実行できる。必要に応じて、圧縮された三角形メッシュのデータと操作関連データとを送信する。また、３次元形状モデルの幾何データについても、必要な処理を施し（例えば圧縮処理）、記憶又は送信する。一方、圧縮を解凍する際には、圧縮された三角形メッシュを、圧縮した際に用いた方法に従い解凍し、三角形メッシュを生成する。操作関連データを用いて、この三角形メッシュに対して位相変形操作の逆操作を実施し、元の３次元形状モデルの位相データを復元する。幾何データも圧縮してあるのであれば解凍処理を実施し、位相データと共に、３次元形状モデル全体を復元する。
【００１１】
さらに、特許文献７には、表面が（i）位置、（ii）ノーマル、（iii）カラー、（iv）テクスチャ・マップ座標、及び（v）該オブジェクトの材料表面特性からなるグループから選択された少なくとも一つの特性を含んでいる表面特性を画定する、３次元オブジェクトは、頂点を有している複数の三角形を画定している３次元三角形データとして表現可能であるような圧縮の方法であって、（ａ）三角形データを線形フォーマットに変換し、（ｂ）表面特性の個々のものを量子化し、（ｃ）表面特性のシーケンシャルなものの間の相違に可変長圧縮を適用し、かつ（ｄ）段階（ａ）、段階（ｂ）及び段階（ｃ）で生成されたデータの収集として３次元オブジェクトを表しているデータ・ストリームを供給する段階を具備する方法が開示されている。
【特許文献１】特開２００４−１０２８３４号公報
【特許文献２】特開２００４−５４７３６号公報
【特許文献３】特開２００４−５４７２３号公報
【特許文献４】特表２００２−５３５７９１号公報
【特許文献５】特許第３５３０１２５号公報
【特許文献６】特許第３１８４７８５号公報
【特許文献７】特許３２１２８８５号 公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、特許文献１〜７に開示されている三角形メッシュデータの圧縮方法を、機構部品として広く使用される板金パネル（図１７参照）のような多くの穴（円形状）を持つ平面で構成された３次元形状モデルを表現する三角形メッシュデータの圧縮に適用する場合には以下の問題点がある。
【００１３】
特許文献１に記載の圧縮方法では、曲面情報が平面の場合は平面領域に存在する穴が０個又は１個の場合のみしか適用できない。また、特許文献２〜４に記載の圧縮方法の場合は、三角形メッシュの位相情報と頂点座標とをすべて保存する必要があるため、三角形数、頂点数に比例してデータサイズが増大してしまう。さらに、特許文献５に記載の圧縮方法は、幾何データ及びテクスチャデータの圧縮を目的としたものであり、三角形の連結性を表す位相データに関しては従来手法を用いている。従って、三角形メッシュの位相情報と頂点座標とをすべて保存する必要があるため、三角形数、頂点数に比例してデータサイズが増大してしまう。また、特許文献６に記載の圧縮方法は、対象が曲面モデルであり、三角形の連結性を表す位相データに関しては従来手法を用いている。従って、三角形メッシュの位相情報と頂点座標とをすべて保存する必要があるため、三角形数、頂点数に比例してデータサイズが増大してしまう。さらに、特許文献７に記載の圧縮方法は、三角形ストリップ方式により、三角形メッシュの位相データを圧縮しているため、データサイズはほぼ頂点数に依存する。従って、三角形数、頂点数に比例してデータサイズが増大してしまう。つまり、特許文献２〜７に記載の圧縮方法の場合は、何れも三角形メッシュ数に比例してデータサイズが増加してしまう。このため、三角形メッシュ数に比例して、圧縮データを伸長する時間も必要になることから、板金パネルのような非常に多くの三角形を必要とするケースでは、非常に長い伸張時間を要する。
【００１４】
本発明は、このような問題点に鑑みてなされたものであり、その第１の目的は、複数の正多角形の穴を有する平面領域の三角形メッシュデータを三角形メッシュ数に比例しないように圧縮することであり、第２の目的は、その圧縮された三角形メッシュデータの伸長時間を短縮することである。
【課題を解決するための手段】
【００１５】
請求項１に係る発明は、３次元形状モデルの表面を構成する複数の正多角形の穴を有する平面領域を表示するための三角形メッシュデータを圧縮する装置であって、三角形メッシュデータ源から前記平面領域の外部境界線上の頂点座標データを読み込む手段と、前記三角形メッシュデータ源から前記正多角形の頂点座標データを読み込む手段と、前記正多角形の頂点座標データに基づいて、前記正多角形の重心座標データ、半径データ及び頂点数データを算出する手段と、前記外部境界線上の頂点座標データ、並びに前記正多角形の重心座標データ、半径データ及び頂点数データを圧縮済データ記憶装置に格納する手段とを備えたことを特徴とする三角形メッシュデータ圧縮装置である。
請求項２に係る発明は、３次元形状モデルの表面を構成する複数の正多角形の穴を有する平面領域を表示するための三角形メッシュデータのデータ構造であって、前記平面領域の外部境界線上の頂点座標データが配列される境界座標配列と、前記正多角形の重心座標データが配列される重心座標配列と、前記正多角形の半径値データが配列される半径値配列と、前記正多角形の頂点数データが配列される頂点数配列とを備えたことを特徴とする三角形メッシュデータのデータ構造である。
請求項３に係る発明は、３次元形状モデルの表面を構成する複数の正多角形の穴を有する平面領域を表示するための圧縮済三角形メッシュデータを伸長する装置であって、前記圧縮済データ中の前記平面領域の外部境界線上の頂点座標データを読み込み、前記外部境界線を生成する手段と、前記圧縮済データ中の前記正多角形の重心座標データ、半径値データ、及び頂点数データを読み込み、前記正多角形を生成する手段と、前記外部境界線及び正多角形の全ての辺を利用して前記平面領域を複数の三角形に分割する手段とを備えたことを特徴とする三角形メッシュデータ伸長装置である。
請求項４に係る発明は、３次元形状モデルの表面を構成する複数の正多角形の穴を有する平面領域を三角形に分割する装置であって、前記平面領域の外部境界線上の頂点と前記正多角形の重心とを直線で結ぶことで前記平面領域を複数の外部三角形に分割する手段と、該複数の外部三角形の各々の内部に、前記正多角形の頂点を少なくとも一つの頂点とし、前記平面領域の境界線上の頂点を残りの頂点とする内部三角形を生成する手段と、前記外部三角形、内部三角形及び正多角形のそれぞれの辺により区画される矩形状領域をその対角線により２つの三角形状領域に分割する手段と、該三角形状領域を複数の三角形に分割する手段とを有することを特徴とする三角形分割装置である。
請求項５に係る発明は、コンピュータを請求項１記載の三角形メッシュデータ圧縮装置の各手段、又は請求項３記載の三角形メッシュデータ伸長装置の各手段、又は請求項４記載の三角形分割装置の各手段として機能させるためのプログラムである。
請求項６に係る発明は、コンピュータを請求項１記載の三角形メッシュデータ圧縮装置の各手段、又は請求項３記載の三角形メッシュデータ伸長装置の各手段、又は請求項４記載の三角形分割装置の各手段として機能させるためのプログラムを記録したコンピュータ読取可能な記録媒体である。
【００１６】
（作用）
請求項１、２、５、６に係る発明は、３次元形状モデルの表面を構成する複数の正多角形の穴を有する平面領域の外部境界線上の頂点座標データ、並びに正多角形の重心座標データ、半径値データ、及び頂点数データを三角形メッシュデータとして格納する。このため、格納されるデータサイズは、平面領域の外部境界線の頂点数、及び平面領域内の穴の数に比例しており、三角形メッシュ数には比例しない。従って、板金パネルのような多数の正多角形の穴を有する平面領域を表示するための三角形メッシュについては、従来手法よりデータサイズが小さくなる。
請求項３、５、６に係る発明は、３次元形状モデルの表面を構成する複数の正多角形の穴を有する平面領域の外部境界線上の頂点座標データを読み込んで外部境界線（ポリライン）を生成し、正多角形の重心座標データ、半径値データ、及び頂点数データを読み込んで、正多角形を生成し、外部境界線（ポリライン）及び正多角形の全ての辺を利用して平面領域を複数の三角形に分割して三角形メッシュを生成する。このため、板金パネルのような多数の正多角形の穴を有する平面領域を表示するための三角形メッシュについては、読み込む圧縮済データのサイズが小さいため、伸長時間が短縮される。
請求項４、５、６に係る発明は、３次元形状をモデルを構成する複数の正多角形の穴を有する平面領域の外部境界線上の頂点と前記正多角形の重心とを直線で結ぶことで平面領域を複数の外部三角形に分割し、外部三角形の各々の内部に、正多角形の頂点を少なくとも一つの頂点とし、平面領域の境界線上の頂点を残りの頂点とする内部三角形を生成し、外部三角形、内部三角形及び正多角形のそれぞれの辺により区画される矩形状の領域を対角線により２つの三角形状領域に分割し、三角形状領域を複数の三角形に分割することで三角形メッシュを形成する。このため、３次元形状をモデルを構成する複数の正多角形の穴を有する平面領域の外部境界の頂点座標、並びに正多角形の重心座標及び頂点座標とから三角形メッシュを生成することができる。
【発明の効果】
【００１７】
本発明によれば、３次元形状モデルの表面を構成する複数の正多角形の穴を有する平面領域を表示するための三角形メッシュデータを三角形メッシュ数に比例しないように圧縮でき、かつ圧縮された三角形メッシュデータの伸長時間を短縮できる。
【発明を実施するための最良の形態】
【００１８】
以下、本発明の実施形態について図面を参照して説明する。
図１は本発明の実施形態に係る三角形メッシュデータの圧縮及び伸長を行う装置の構成を示す図である。この装置は、ＣＰＵからなる処理装置１と、それぞれ処理装置１に接続された、処理装置１の動作時に使用される各種プログラムが予め記憶されたＲＯＭ２、処理装置１の動作時に各種データを一時的に記憶するＲＡＭ３、マウス、キーボード等の操作装置４、ＣＲＴ、ＬＣＤ等の表示装置５、各種３次元形状モデルの表面を構成する三角形メッシュデータが予め格納された三角形メッシュデータベース６、及び圧縮された三角形メッシュデータを格納するための圧縮済データ記憶装置７とから構成されている。
【００１９】
処理装置１は圧縮装置11と伸長装置12とを備えている。圧縮装置11は三角形メッシュデータベース６から読み込まれた３次元形状モデルの表面形状を表すデータから、三角形メッシュを表示するために必要な圧縮されたデータ（圧縮済三角形メッシュデータ）を生成する。この圧縮済三角形メッシュデータは圧縮済データ記憶装置７に記憶される。伸長装置12は圧縮済データ記憶装置７から読み込まれた圧縮済三角形メッシュデータを伸長し、三角形メッシュデータを生成する。本実施形態では、圧縮装置11及び伸長装置12は、処理装置１がＲＯＭ２に格納されているコンピュータプログラムを用いて実現する機能（機能ブロック）である。伸長装置12で生成された三角形メッシュデータは表示装置５に供給され、その画面上に表面が三角形メッシュで表された３次元形状モデルが表示される。
【００２０】
以下、データ圧縮及びデータ伸長の手順について詳細に説明する。
本実施形態において三角形メッシュで表現する対象となる３次元形状モデルの表面は下記（１）、（２）の条件を全て満たすものである。
（１）表面の外部境界線上の全ての頂点が同一平面上に存在する。
（２）外部境界内に形成されている穴はすべて正多角形である。正多角形なので円を近似でき、正多角形の重心は円の中心に等しく、重心から正多角形の頂点までの距離は円の半径に等しい。
ここで、三角形メッシュ内の三角形、辺、頂点の隣接関係、及び、それらの要素が外部境界上にあるか否かの情報は、一般的なＣＡＤなどの形状作成ツールが提供している機能やＡＰＩ（Application Programming Interface）により容易に取得できるものである。
【００２１】
図２は上記（１）及び（２）の条件を満たす平面領域Ｐを示す。この平面領域Ｐの外部境界線（輪郭）の形状は矩形であって、外部境界線はラインL0〜L3からなるポリライン（折れ線を表す連結された線分）により構成されている。また、外部境界線上には４つの頂点D0〜D3が存在する。これらの頂点D0〜D3は、ラインL0〜L3の接続点である。さらに、平面領域Ｐ内（外部境界線の内側）には各々正多角形（図示は円）C0〜C2で表される３個の穴が開けられている。穴の中心、即ち正多角形（図示は円）C0〜C2の重心は図示されている円の中心O0〜O2と一致し、重心から正多角形の頂点までの距離は円の半径Ｒ0〜Ｒ2に等しい。
【００２２】
図２に示す平面領域Ｐに対して、圧縮装置11は、図３のフローチャートに示す処理により、図４に示すデータフォーマット（データ構造）のデータを生成する。
まず、図４のデータフォーマットについて説明する。このデータフォーマットは、境界座標配列、重心座標配列、半径値配列、及び頂点数配列からなる。境界座標配列には、平面領域Ｐの外部境界線上に存在するｍ個の頂点の座標データが外部境界線上を回るように所定の順（時計回り又は反時計回り）に配置される。重心座標配列、半径値配列、及び頂点数配列には、平面領域Ｐ内に存在するｎ個の正多角形の重心の座標座標データ、半径値データ、及び頂点数データが互いに同一の所定の順に配置される。
圧縮装置11は三角形メッシュデータベース６から平面領域Ｐの三角形メッシュデータをＲＡＭ３に読み込み、平面領域Ｐの外部境界をなすポリラインを形成する頂点Ｄ0〜Ｄ3の座標（Xbo，Ybo，Zbo）〜（Xb3，Yb3，Zb3）を境界座標配列として、圧縮済データ記憶装置７に格納する（ステップＳ１）。次いで、平面領域Ｐの穴をなす正多角形C0〜C2の重心O0〜O2の座標（Xo，Yo，Zo）〜（X2，Y2，Z2）、半径R0〜R2、頂点数（辺数）N0〜N2をそれぞれ図４における重心座標配列、半径値配列、頂点数配列として、圧縮済データ記憶装置７に格納する（ステップＳ２）。
ここで、重心座標はＲＡＭ３に読み込んだ三角形メッシュデータにおける正多角形の頂点座標データの平均値を計算することにより求めることができる。また、半径値は重心座標データから正多角形のある頂点までの距離を計算することにより求めることができる。さらに、頂点数データは三角形メッシュデータと共に三角形メッシュデータベース６からＲＡＭ３に読み込むことができる。
以上で平面領域Ｐを表示するための三角形メッシュを生成するために必要なデータの格納が終了する。なお、以上の説明では、境界座標配列を圧縮済データ記憶装置７に格納した後に重心座標配列、半径値配列、頂点数配列を圧縮済データ記憶装置７に格納するものとしたが、境界座標配列、重心座標配列、半径値配列、頂点数配列をＲＡＭ３に記憶し、つまりＲＡＭ３上で図４のデータを構成した後にまとめて圧縮済データ記憶装置７に格納するように構成してもよい。
【００２３】
次に、圧縮済データ記憶装置７に格納された圧縮済データを伸長して三角形メッシュデータを作成する手順について、前述した図２、及び図５に示すフローチャートを参照しながら説明する。
まず、圧縮済データ記憶装置７から境界座標配列の頂点座標データを読み込み、平面領域Ｐの外部境界をなすポリラインL0〜L3を生成する（ステップＳ３）。
次いで、重心座標配列(Xc,Yc,Zc)、半径値配列(R)、頂点数配列(N)から、それぞれのデータを順に読み込み、穴をなす正多角形C0〜C2を生成する（ステップＳ４）。正多角形C0〜C2の頂点座標(Xi,Yi,Zi)は、以下の計算式による求められる。
Xi=Xc＋R*cos(θ)*Xxp+R*sin(θ)*Xyp
Yi=Yc＋R*cos(θ)*Yxp+R*sin(θ)*Yyp
Zi=Zc＋R*cos(θ)*Zxp+R*sin(θ)*Zyp
θ=i*360°/N
i=0,1, ..., N-1
(Xxp,Yxp,Zxp),(Xyp,Yyp,Zyp)は、それぞれ、平面領域Ｐを表す座標系のX軸方向、Y軸方向とする。
次に、ポリラインL0〜L3と正多角形C0〜C2の辺の情報及びそれらを構成する頂点等の座標値に基づいて図２に示す平面領域Ｐを三角形メッシュに分割する（ステップＳ４）。
【００２４】
ステップＳ４については、図６に示すフローチャート及び図７〜１６に示す分割手順の図を参照しながら以下に詳しく説明する。
まず、平面領域Ｐの境界線（ポリラインL0〜L3）上の頂点D0〜D3と正多角形C0〜C2の重心O0〜O2に対し三角形分割を行う（ステップＳ11、図７）。三角形分割はＣＤＴ(Constraint Delauney Triangulation)手法などの公知の手法を用いて行う。これにより、図７に示すような８個の三角形A0〜A7が形成される。
【００２５】
次に、ステップＳ11で生成した８個の三角形A0〜A7の各々の内部に三角形を一つずつ生成する（ステップＳ12、図８）。以下の説明では、８個の三角形を外部三角形、その内部の三角形を内部三角形と呼ぶ。外部三角形の内心から正多角形C0〜C2の重心O0〜O2まで引いた線と正多角形C0〜C2との交点を求め、その交点に最も近い正多角形C0〜C2の頂点を内部三角形の頂点とする。この処理により、図８に白べたで示す８個の内部三角形E0〜E7が生成される。ここで、内部三角形E0は全ての頂点が正多角形の頂点上に存在し、内部三角形E2、E4、E7は２個の頂点が正多角形の頂点上、１個の頂点が外部境界線の頂点上に存在し、内部三角形E1、E3、E5、E6は１個の頂点が正多角形の頂点上、２個の頂点が外部境界線の頂点上に存在する。
【００２６】
次いで、正多角形と内部三角形及び外部三角形の交差状況に基づいて、以下の判定を順に行い以降の処理を実行する。即ち、正多角形と内部三角形とが交差しなければ（ステップＳ13でNO）ステップＳ14へ移行し、正多角形と内部三角形とが交差し（ステップＳ13でYES）、正多角形と外部三角形とが交差しなければ（ステップＳ16でNO）ステップＳ17へ移行し、正多角形が内部三角形と交差し（ステップＳ13でYES）、かつ外部三角形とも交差する場合（ステップＳ16でYES）、換言すれば、正多角形が、自身が属する外部三角形以外の外部三角形と交差すればステップＳ20へ移行する。
【００２７】
図８では正多角形C0〜C2と内部三角形E0〜E7とが交差していないので、ステップＳ14へ移行し、外部三角形、内部三角形及び正多角形の辺に囲まれて区画された矩形状領域F0〜F5の各々を、図９に示すように対角線H0〜H5により２つずつの三角形状領域F0A,F0B、F1A,F1B、F2A,F2B、F3A,F3B、F4A,F4B、F5A,F5Bに分割する（ステップＳ14）。次いで、図１０に示すように、図９における三角形状領域F0A,F0B、F1A,F1B、F2A,F2B、F3A,F3B、F4A,F4B、F5A,F5B、及び図８において外部三角形、内部三角形及び正多角形の辺に囲まれて区画された三角形状領域G0〜G13の各々を、正多角形C0〜C2の頂点間、及び正多角形C0〜C2の頂点と平面領域Ｐの頂点D0〜D3との間を線分で結び、三角形に分割して（ステップＳ15）処理を終了する。
【００２８】
図１１に示すように、正多角形C4と、正多角形C4〜C6の重心O4〜O6を頂点とする外部三角形に対する内部三角形（図示せず）とが交差する場合はステップＳ17へ移行し、正多角形C4の重心O4から外部三角形の対辺に垂線I1を下ろし、正多角形C4と垂線I1との交点J1を求め、その交点J1と対辺とにより三角形K1を生成する。次いで、図１１における三角形K1の２つの斜辺と外部三角形の斜辺と正多角形C4〜C6とに囲まれて区画された２つの矩形状領域（図１１の網掛け部分）をそれぞれ対角線H11,H12により、２つずつの三角形状領域M1,M2、M3,M4に分割する（ステップＳ18）。次に、三角形状領域M1,M2、M3,M4を図１０の場合と同様な手順で三角形に分割する（ステップＳ19）。
【００２９】
図１２に示すように、正多角形C7と、正多角形C7〜C9の重心O7〜O9を頂点とする外部三角形とが交差する場合はステップＳ20へ移行し、外部三角形の辺と正多角形C7〜C9とに囲まれて区画された２つの矩形状領域（図１２の網掛け部分）をそれぞれ対角線H13,H14により、２つずつの三角形状領域M5,M6、M7,M8に分割する。次いで、４つの三角形状領域M5,M6、M7,M8を図１０と同様な方法で三角形に分割する（ステップＳ21）。これで正多角形自身が属する外部三角形領域が三角形に分割できた。
【００３０】
正多角形と交差する他の外部三角形（自身が属するものは除く）について以下の場合に分けて分割処理を行う。図１３に示すように他の外部三角形の１辺と正多角形とが交差すればステップＳ23へ移行し、図１４に示すように他の外部三角形の２辺と正多角形とが交差すればステップＳ27へ移行し、図１５に示すように他の外部三角形の３辺と正多角形とが交差すればステップＳ30へ移行する。
【００３１】
図１３においては、正多角形C10〜C12の重心O10〜O12を頂点とする外部三角形の一辺（O10とO11とを結ぶ辺）と正多角形C13とが交差している。ステップＳ23では、正多角形C13の重心O13から、上記外部三角形の正多角形C13と交差しない辺（O11とO12とを結ぶ辺）に垂線I2を下ろし、垂線I2と正多角形C13との交点J2と、上記交差しない辺と正多角形C11、C12との交点J3,J4を頂点とする三角形K2を生成する。このとき、２本ある正多角形と交差しない辺の内、１本にはその辺の有効領域に必ず垂線を下ろすことができる。
次いで、正多角形C13と正多角形C13と交差する辺との交点J5と重心O13とを結ぶ線分と、前記交点J2と重心O13とを結ぶ線分とのなす角度の二等分線と正多角形C13との交点J6を第１の頂点とし、外部三角形のO10,O11の位置に存在する角の二等分線と正多角形C10,C11の交点J7,J8を第２、第３の頂点とする三角形K3を生成する（ステップＳ24）。
次に、４つの矩形状領域（図１３の網掛け部分）を、それぞれ対角線により２つずつ、合計８つの三角形状領域M9〜M16に分割する（ステップＳ25）。次いで、８つの三角形状領域M9〜M16の各々を図１０の場合と同様な手順で三角形に分割する（ステップＳ26）。
【００３２】
図１４においては、正多角形C14〜C16の重心O14〜O16を頂点とする外部三角形の二辺と正多角形C17とが交差している。ステップＳ27では、正多角形C17と上記外部三角形の正多角形C17と交差する辺との交点J9,J10と正多角形C17の重心O17とを結ぶ２本の線のなす角度を二等分した線と正多角形C17の交点Ｊ11を第１の頂点とし、正多角形C14,C15の重心O14,O15から外部三角形のO14,O15の位置に存在する角の二等分線と正多角形C14,C15との交点J12,J13を第２、第３の頂点とする三角形K4を生成する。次いで、４つの矩形状領域（図１４の網掛け部分）をそれぞれ対角線により２つずつ、合計８つの三角形状領域M17〜M24に分割する（ステップＳ28）。次に、８つの三角形状領域M17〜M24の各々を図１０の場合と同様な手順で三角形に分割する（ステップＳ29）。
【００３３】
図１５においては、正多角形C18〜C20の重心O18〜O20を頂点とする外部三角形の三辺と正多角形C21とが交差している。ステップＳ30では、外部三角形の辺のうち、正多角形C21の重心O21に最も近い辺を含む２つの矩形状領域（図１５の網掛け部分）をそれぞれ対角線により４つの三角形状領域M25〜M28に分割する。次いで、４つの三角形状領域M25〜M28のそれぞれを図１０と同様の方法で三角形に分割する（ステップＳ31）。残った一つの矩形状領域F10については対角線で分割できないので、矩形状領域F10の境界線をなす２つの正多角形C19,C21の最も近い２頂点を結んで辺を生成し（図１６（ａ））、その辺から両側に隣接する頂点を三角形ストリップで結びながら三角形を生成していく（図１６（ｂ），（ｃ），（ｄ）、ステップＳ32）。何れかの正多角形の頂点を全て結んだ場合は、残りの三角形領域について三角形に分割する。なお、図１６（ｂ）〜（ｄ）では便宜上、辺の右側の領域のみについて三角形を生成する様子を示している。
【００３４】
以上、詳細に説明したように、本実施形態によれば、３次元形状モデルの表面を構成する複数の正多角形の穴を有する平面領域Ｐの外部境界線上の頂点D0〜D3の座標データ、並びに正多角形の重心座標データ、半径値データ、及び頂点数データを三角形メッシュデータとして格納するため、格納されるデータサイズは、平面領域Ｐの外部境界線の頂点数、及び平面領域内の穴の数に比例しており、三角形メッシュ数には比例しない。従って、板金パネルのような多数の正多角形の穴を有する平面領域を表示するための三角形メッシュについては、従来手法よりデータサイズが小さくなる。
また、複数の正多角形の穴を有する平面領域Ｐの外部境界線上の頂点D0〜D3の座標データを読み込んで外部境界線（ポリライン）L0〜L3を生成し、正多角形の重心座標データ、半径値データ、及び頂点数データを読み込んで、正多角形を生成し、外部境界線（ポリライン）L0〜L3及び正多角形の全ての辺を利用して平面領域を複数の三角形に分割して三角形メッシュを生成するため、板金パネルのような多数の正多角形の穴を有する平面領域を表示するための三角形メッシュについては、読み込む圧縮済データのサイズが小さいため、伸長時間が短縮される。
【００３５】
なお、以上の実施形態では、圧縮装置11と伸長装置12とを同一の処理装置１に設けたが、それらをネットワーク等で接続可能な別の処理装置に設けてもよい。
【図面の簡単な説明】
【００３６】
【図１】本発明の実施形態に係る三角形メッシュデータの圧縮及び伸長を行う装置の構成を示す図である。
【図２】本発明の実施形態における平面領域を示す図である。
【図３】本発明の実施形態におけるデータ圧縮処理のフローチャートである。
【図４】本発明の実施形態における圧縮データフォーマットを示す図である。
【図５】本発明の実施形態におけるデータ伸長処理のフローチャートである。
【図６】本発明の実施形態における三角形分割処理のフローチャートである。
【図７】本発明の実施形態における外部三角形の生成処理を説明するための図である。
【図８】本発明の実施形態における内部三角形の生成処理を説明するための図である。
【図９】本発明の実施形態における矩形状領域を三角形状領域に分割する処理を説明するための図である。
【図１０】本発明の実施形態における三角形状領域を三角形に分割する処理を説明するための図である。
【図１１】本発明の実施形態において正多角形が内部三角形と交差する場合の三角形分割処理を説明するための図である。
【図１２】本発明の実施形態において正多角形と自身が属する外部三角形とが交差する場合の三角形分割処理を説明するための図である。
【図１３】本発明の実施形態において正多角形が他の外部三角形の一辺と交差する場合の三角形分割処理を説明するための図である。
【図１４】本発明の実施形態において正多角形が他の外部三角形の二辺と交差する場合の三角形分割処理を説明するための図である。
【図１５】本発明の実施形態において正多角形が他の外部三角形の三辺と交差する場合の三角形分割処理を説明するための図である。
【図１６】図１５の処理の一部の詳細を説明するための図である。
【図１７】板金パネルの３次元形状モデルを示す図である。
【符号の説明】
【００３７】
２・・・ＲＯＭ、６・・・三角形メッシュデータベース、７・・・圧縮済データ記憶装置、11・・・圧縮装置、11・・・伸長装置。
【図１】
2006302188.tif 000003
【図２】
2006302188.tif 000004
【図３】
2006302188.tif 000005
【図４】
2006302188.tif 000006
【図５】
2006302188.tif 000007
【図６】
2006302188.tif 000008
【図７】
2006302188.tif 000009
【図８】
2006302188.tif 000010
【図９】
2006302188.tif 000011
【図１０】
2006302188.tif 000012
【図１１】
2006302188.tif 000013
【図１２】
2006302188.tif 000014
【図１３】
2006302188.tif 000015
【図１４】
2006302188.tif 000016
【図１５】
2006302188.tif 000017
【図１６】
2006302188.tif 000018
【図１７】
2006302188.tif 000019