(57)【要約】【課題】  ｎ次元形状モデルのデータサイズが増大してもハードディスク等の保存装置のスペース効率、表示速度および転送速度を低下させることのなく、ｎ次元空間の三角形メッシュの圧縮、保存、転送、伸張の処理を施すことができるデータ圧縮装置を提供する。【解決手段】  このデータ圧縮装置は、ｎ次元空間の形状モデルを三角形メッシュで表した形状データを圧縮する際、同一の平面上の複数の頂点に対し、複数の頂点座標を連続して頂点座標テーブルに格納し、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを法線ベクトルテーブルに格納し、該頂点に対しては真を、また該平面上の他の頂点には偽を平面フラグテーブルに格納するようにして、ｎ次元形状モデルのデータから圧縮した形状データを生成する。【選択図】  図５
2005084780.tif 000002
【特許請求の範囲】
【請求項１】
ｎ次元空間の形状モデルを三角形メッシュで表した形状データを格納するデータ構造であって、ｎ次元の頂点座標が格納された頂点座標テーブルと、ｎ次元の法線ベクトルが格納された法線ベクトルテーブルと、頂点ごとに真・偽を示す平面フラグテーブルとからなることを特徴とする列挙型三角形メッシュを用いたデータ構造。
【請求項２】
請求項１に記載のデータ構造において、前記頂点座標テーブルおよび前記平面フラグテーブルは、三角形セット形式または三角形ストリップ形式のいずれかであることを特徴とするデータ構造。
【請求項３】
ｎ次元空間の形状モデルを三角形メッシュで表した形状データを圧縮するデータ圧縮装置において、同一の平面上の複数の頂点に対し、複数の頂点座標を連続して頂点座標テーブルに格納する頂点座標圧縮手段と、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを法線ベクトルテーブルに格納し、該頂点に対しては真を、また該平面上の他の頂点には偽を平面フラグテーブルに格納する法線ベクトル圧縮手段を備えることを特徴とするデータ圧縮装置。
【請求項４】
ｎ次元空間の形状モデルを三角形メッシュで表した形状データを圧縮するデータ圧縮方法において、同一の平面上の複数の頂点に対し、複数の頂点座標を連続して頂点座標テーブルに格納し、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを法線ベクトルテーブルに格納し、該頂点に対しては真を、また該平面上の他の頂点には偽を平面フラグテーブルに格納することを特徴とするデータ圧縮方法。
【請求項５】
請求項３に記載のデータ圧縮装置で圧縮された形状データを伸張するデータ伸張装置であって、前記頂点座標テーブルに連続して格納されたすべての頂点座標を読み出すことによって頂点座標を伸張する頂点座標伸張手段と、前記平面フラグテーブルから真を読み出した場合に、前記頂点座標テーブルに連続して格納された複数の頂点座標を同一の平面上の複数頂点の頂点座標とみなし、前記法線ベクトルテーブルに格納された単一の法線ベクトルを同一の平面上の複数頂点の法線ベクトルとして割り当てることにより法線ベクトルを伸張する法線ベクトル伸張手段とを備えることを特徴とするデータ伸張装置。
【請求項６】
請求項４に記載のデータ圧縮方法で圧縮された形状データを伸張するデータ伸張方法であって、前記頂点座標テーブルに連続して格納されたすべての頂点座標を読み出すことによって頂点座標を伸張し、前記平面フラグテーブルから真を読み出した場合に、前記頂点座標テーブルに連続して格納された複数の頂点座標を同一の平面上の複数頂点の頂点座標とみなし、前記法線ベクトルテーブルに格納された単一の法線ベクトルを同一の平面上の複数頂点の法線ベクトルとして割り当てることにより法線ベクトルを伸張することを特徴とするデータ伸張方法。
【請求項７】
ｎ次元空間の形状モデルを三角形メッシュで表した形状データを格納するデータ構造であって、ｎ次元の頂点座標が格納された頂点座標テーブルと、ｎ次元の法線ベクトルが格納された法線ベクトルテーブルと、頂点座標テーブルへのインデックスが格納された頂点座標インデックステーブルと、法線ベクトルテーブルへのインデックスが格納された法線ベクトルインデックステーブルと、頂点ごとに真・偽を示す平面フラグテーブルとからなることを特徴とするインデックス型三角形メッシュを用いたデータ構造。
【請求項８】
請求項７に記載のデータ構造において、前記頂点座標インデックステーブルおよび前記平面フラグテーブルは、三角形セット形式または三角形ストリップ形式のいずれかであることを特徴とするデータ構造。
【請求項９】
ｎ次元空間の形状モデルを三角形メッシュで表した形状データを圧縮するデータ圧縮装置において、同一の平面上の複数頂点に対し、重複することなく頂点座標テーブルに格納し、その複数の頂点座標インデックスを連続して頂点座標インデックステーブルに格納する頂点座標圧縮手段と、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを重複することなく法線ベクトルテーブルに格納し、その法線ベクトルインデックスを法線ベクトルインデックステーブルに格納し、該頂点に対しては真を、また該平面上の他の頂点には偽を平面フラグテーブルに格納する法線ベクトル圧縮手段を備えることを特徴とするデータ圧縮装置。
【請求項１０】
ｎ次元空間の形状モデルを三角形メッシュで表した形状データを圧縮するデータ圧縮方法において、重複することなく頂点座標テーブルに格納し、その複数の頂点座標インデックスを連続して頂点座標インデックステーブルに格納し、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを重複することなく法線ベクトルテーブルに格納し、その法線ベクトルインデックスを法線ベクトルインデックステーブルに格納し、該頂点に対しては真を、また該平面上の他の頂点には偽を平面フラグテーブルに格納することを特徴とするデータ圧縮方法。
【請求項１１】
請求項９に記載のデータ圧縮装置で圧縮された形状データを伸張するデータ伸張装置であって、前記頂点座標インデックステーブルに連続して格納されたすべての頂点座標を、頂点に対する頂点座標インデックスによって前記頂点座標テーブルから頂点座標を求めて読み出して頂点座標を伸張する頂点座標伸張手段と、前記平面フラグテーブルから真を読み出した場合に、前記頂点座標インデックステーブルに連続して格納された複数の頂点座標を同一の平面上の複数頂点の頂点座標とみなし、前記法線ベクトルインデックステーブルに格納された単一の法線ベクトルインデックスを同一の平面上の複数頂点の法線ベクトルインデックスとして割り当てて、この法線ベクトルインデックスによって前記法線ベクトルテーブルから法線ベクトルを取り出すことにより法線ベクトルを伸張する法線ベクトル伸張手段とを備えることを特徴とするデータ伸張装置。
【請求項１２】
請求項１０に記載のデータ圧縮方法で圧縮された形状データを伸張するデータ伸張方法であって、前記頂点座標インデックステーブルに連続して格納されたすべての頂点座標を、頂点に対する頂点座標インデックスによって前記頂点座標テーブルから頂点座標を求めて読み出して頂点座標を伸張し、前記平面フラグテーブルから真を読み出した場合に、前記頂点座標インデックステーブルに連続して格納された複数の頂点座標を同一の平面上の複数頂点の頂点座標とみなし、前記法線ベクトルインデックステーブルに格納された単一の法線ベクトルインデックスを同一の平面上の複数頂点の法線ベクトルインデックスとして割り当てて、この法線ベクトルインデックスによって前記法線ベクトルテーブルから法線ベクトルを取り出すことにより法線ベクトルを伸張することを特徴とするデータ伸張方法。
【請求項１３】
ｎ次元空間の形状モデルを三角形メッシュで表した形状データを格納するデータ構造であって、ｎ次元の頂点座標が格納された頂点座標テーブルと、ｎ次元の法線ベクトルが格納された法線ベクトルテーブルと、頂点座標テーブルへのインデックスが格納された頂点座標インデックステーブルと、法線ベクトルテーブルへのインデックスが格納された法線ベクトルインデックステーブルと、頂点ごとに真・偽を示す頂点座標参照フラグテーブルと、頂点ごとに真・偽を示す法線ベクトル参照フラグテーブルと、頂点ごとに真・偽を示す平面フラグテーブルとからなることを特徴とする参照型三角形メッシュを用いたデータ構造。
【請求項１４】
請求項１３に記載のデータ構造において、前記頂点座標参照テーブル、前記法線ベクトル参照フラグテーブルおよび前記平面フラグテーブルは、三角形セット形式または三角形ストリップ形式のいずれかであることを特徴とするデータ構造。
【請求項１５】
ｎ次元空間の形状モデルを三角形メッシュで表した形状データを圧縮するデータ圧縮装置において、同一の平面上の複数の頂点に対し、初めて参照される頂点座標については、頂点座標を頂点座標テーブルに格納し、該複数の頂点に対応する頂点座標参照フラグテーブルに真を格納し、２回目以降参照される頂点座標については、頂点座標インデックスを頂点座標インデックステーブルに格納し、該複数の頂点に対応する頂点座標参照フラグテーブルに偽を格納する頂点座標圧縮手段と、初めて参照される法線ベクトルについては、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを法線ベクトルテーブルに格納し、該頂点に対応する法線ベクトル参照フラグテーブルに真を格納し、２回目以降に参照される法線ベクトルについては、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを法線ベクトルテーブルに格納して、その法線ベクトルインデックスを法線ベクトルインデックステーブルに格納し、該頂点に対応する法線ベクトル参照フラグテーブルに偽を格納し、該単一の法線ベクトルに対応する頂点に対しては真を平面フラグテーブルに格納する法線ベクトル圧縮手段を備えることを特徴とするデータ圧縮装置。
【請求項１６】
ｎ次元空間の形状モデルを三角形メッシュで表した形状データを圧縮するデータ圧縮方法において、同一の平面上の複数の頂点に対し、初めて参照される頂点座標については、頂点座標を頂点座標テーブルに格納し、該複数の頂点に対応する頂点座標参照フラグテーブルに真を格納し、２回目以降参照される頂点座標については、頂点座標インデックスを頂点座標インデックステーブルに格納し、該複数の頂点に対応する頂点座標参照フラグテーブルに偽を格納し、初めて参照される法線ベクトルについては、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを法線ベクトルテーブルに格納し、該頂点に対応する法線ベクトル参照フラグテーブルに真を格納し、２回目以降に参照される法線ベクトルについては、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを法線ベクトルテーブルに格納して、その法線ベクトルインデックスを法線ベクトルインデックステーブルに格納し、該頂点に対応する法線ベクトル参照フラグテーブルに偽を格納し、該単一の法線ベクトルに対応する頂点に対しては真を平面フラグテーブルに格納することを特徴とするデータ圧縮方法。
【請求項１７】
請求項１５に記載のデータ圧縮装置で圧縮された形状データを伸張するデータ伸張装置であって、処理中の頂点に対応する前記頂点座標参照フラグテーブルのフラグが真の場合は、該頂点の頂点座標を前記頂点座標テーブルから読み出し、該頂点に対応する頂点座標参照フラグテーブルのフラグが偽の場合は、該頂点に対応する前記頂点座標インデックステーブルの頂点座標インデックスが指す座標値を前記頂点座標テーブルから読み出すことによって頂点座標を伸張する頂点座標伸張手段と、平面上の頂点の法線ベクトル参照フラグテーブルのフラグが真の場合は、該頂点に対応する法線ベクトルを法線ベクトルテーブルから読み出し、該頂点の法線ベクトル参照フラグテーブルのフラグが偽の場合は、該頂点に対応する法線ベクトルを法線ベクトルインデックステーブルの法線ベクトルインデックスが指す法線ベクトルテーブルから読み出すことで、同一の平面上の複数頂点に対して法線ベクトルを割り当てることにより法線ベクトルを伸張する法線ベクトル伸張手段とを備えることを特徴とするデータ伸張装置。
【請求項１８】
請求項１６に記載のデータ圧縮方法で圧縮された形状データを伸張するデータ伸張方法であって、処理中の頂点に対応する前記頂点座標参照フラグテーブルのフラグが真の場合は、該頂点の頂点座標を前記頂点座標テーブルから読み出し、該頂点に対応する頂点座標参照フラグテーブルのフラグが偽の場合は、該頂点に対応する前記頂点座標インデックステーブルの頂点座標インデックスが指す座標値を前記頂点座標テーブルから読み出すことによって頂点座標を伸張し、平面上の頂点の法線ベクトル参照フラグテーブルのフラグが真の場合は、該頂点に対応する法線ベクトルを法線ベクトルテーブルから読み出し、該頂点の法線ベクトル参照フラグテーブルのフラグが偽の場合は、該頂点に対応する法線ベクトルを法線ベクトルインデックステーブルの法線ベクトルインデックスが指す法線ベクトルテーブルから読み出すことで、同一の平面上の複数頂点に対して法線ベクトルを割り当てることにより法線ベクトルを伸張することを特徴とするデータ伸張方法。
【請求項１９】
請求項１、７または１３に記載のデータ構造において、前記頂点座標テーブルおよび前記法線ベクトルテーブルは、浮動小数点表現またはベクトル量子化圧縮がなされていることを特徴とするデータ構造。
【請求項２０】
ｎ次元空間の形状モデルを処理するｎ次元形状モデル処理装置において、請求項３、９または１５に記載のデータ圧縮装置と、請求項５、１１または１７に記載のデータ伸張装置の少なくともいずれかを備え、前記データ圧縮装置は、ｎ次元形状モデルを圧縮した形状データを生成して送信し、前記データ伸張装置は、受信した該形状データを伸張して、ｎ次元形状モデルを生成するようにしたことを特徴とするｎ次元形状モデル処理装置。
【請求項２１】
コンピュータに、請求項３、９または１５に記載のデータ圧縮装置の機能、請求項５、１１または１７に記載のデータ伸張装置の機能、または、請求項２０に記載のｎ次元形状モデル処理装置の機能を実行させるためのプログラム。
【請求項２２】
請求項２１に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ圧縮装置、その方法、データ伸張装置、その方法、データ構造、３次元形状処理装置並びにプログラムおよび記録媒体に関し、具体的には、３次元形状モデル生成装置、３次元形状モデル表示装置、形状計測装置や仮想現実感装置に適用され、形状モデルの面を三角形メッシュで表現したときの形状データをコンパクトに格納できるデータ構造と、そのデータ構造によって形状データを圧縮・伸張する技術に関し、このデータ構造によってネットワークを利用して高速に転送できるようにする技術に関する。
【背景技術】
【０００２】
曲面および曲線は、３次元形状モデルを表現する手段として、ＣＡＤ（Computer Aided Design）で広く利用されている（非特許文献１参照）。３次元形状モデルを表示するためには、曲面を三角形メッシュ形式のデータに変換して行うのが一般的である。
一方、近年、設計部門以外での利用も視野に入れたＣＡＤデータ専用ビューワ（３Ｄビューワ）も登場している。
このビューワは、面を三角形メッシュ形式で表現した形状データへ変換して、ビューワ専用ファイルに格納しており、一旦、ＣＡＤファイルからこの専用ファイルに変換しておけば、毎回の変換プロセスを省略でき、ＣＡＤよりも高速な表示を実現している。この３Ｄビューワでは、表示に必要のないデータを省略し、さらに圧縮を行うことにより、表示の高速化およびデータの軽量化を実現しているものもある。
【非特許文献１】鳥谷浩志・千代倉弘明著：３次元ＣＡＤの基礎と応用、共立出版、１９９１年
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、３次元形状モデルの利用が高まり、大規模で複雑な３次元形状モデルを扱うにしたがってデータ量が増加する傾向にあり、より一層データを圧縮することが必要となっている。具体的には、次のことが問題となっている。
（１）データサイズ増大によるハードディスク等保存装置のスペース効率低下、
（２）データサイズ増大による表示速度の低下、
（３）データサイズ増大による転送速度の低下。
本発明は、上述した実情を考慮してなされたものであって、ｎ次元形状モデルのデータサイズが増大してもハードディスク等の保存装置のスペース効率、表示速度および転送速度を低下させることのなく、ｎ次元空間の三角形メッシュの圧縮、保存、転送、伸張の処理を施すことができるデータ圧縮装置、その方法、データ伸張装置、その方法、データ構造、３次元形状処理装置並びにプログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００４】
上記の課題を解決するために、本発明の請求項１は、ｎ次元空間の形状モデルを三角形メッシュで表した形状データを格納するデータ構造であって、ｎ次元の頂点座標が格納された頂点座標テーブルと、ｎ次元の法線ベクトルが格納された法線ベクトルテーブルと、頂点ごとに真・偽を示す平面フラグテーブルとからなることを特徴とする列挙型三角形メッシュを用いたデータ構造である。
また、本発明の請求項２は、請求項１に記載のデータ構造において、前記頂点座標テーブルおよび前記平面フラグテーブルは、三角形セット形式または三角形ストリップ形式のいずれかであることを特徴とするデータ構造である。
また、本発明の請求項３は、ｎ次元空間の形状モデルを三角形メッシュで表した形状データを圧縮するデータ圧縮装置において、同一の平面上の複数の頂点に対し、複数の頂点座標を連続して頂点座標テーブルに格納する頂点座標圧縮手段と、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを法線ベクトルテーブルに格納し、該頂点に対しては真を、また該平面上の他の頂点には偽を平面フラグテーブルに格納する法線ベクトル圧縮手段を備えることを特徴とする。
また、本発明の請求項４は、ｎ次元空間の形状モデルを三角形メッシュで表した形状データを圧縮するデータ圧縮方法において、同一の平面上の複数の頂点に対し、複数の頂点座標を連続して頂点座標テーブルに格納し、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを法線ベクトルテーブルに格納し、該頂点に対しては真を、また該平面上の他の頂点には偽を平面フラグテーブルに格納することを特徴とする。
また、本発明の請求項５は、請求項３に記載のデータ圧縮装置で圧縮された形状データを伸張するデータ伸張装置であって、前記頂点座標テーブルに連続して格納されたすべての頂点座標を読み出すことによって頂点座標を伸張する頂点座標伸張手段と、前記平面フラグテーブルから真を読み出した場合に、前記頂点座標テーブルに連続して格納された複数の頂点座標を同一の平面上の複数頂点の頂点座標とみなし、前記法線ベクトルテーブルに格納された単一の法線ベクトルを同一の平面上の複数頂点の法線ベクトルとして割り当てることにより法線ベクトルを伸張する法線ベクトル伸張手段とを備えることを特徴とする。
【０００５】
また、本発明の請求項６は、請求項４に記載のデータ圧縮方法で圧縮された形状データを伸張するデータ伸張方法であって、前記頂点座標テーブルに連続して格納されたすべての頂点座標を読み出すことによって頂点座標を伸張し、前記平面フラグテーブルから真を読み出した場合に、前記頂点座標テーブルに連続して格納された複数の頂点座標を同一の平面上の複数頂点の頂点座標とみなし、前記法線ベクトルテーブルに格納された単一の法線ベクトルを同一の平面上の複数頂点の法線ベクトルとして割り当てることにより法線ベクトルを伸張することを特徴とする。
また、本発明の請求項７は、ｎ次元空間の形状モデルを三角形メッシュで表した形状データを格納するデータ構造であって、ｎ次元の頂点座標が格納された頂点座標テーブルと、ｎ次元の法線ベクトルが格納された法線ベクトルテーブルと、頂点座標テーブルへのインデックスが格納された頂点座標インデックステーブルと、法線ベクトルテーブルへのインデックスが格納された法線ベクトルインデックステーブルと、頂点ごとに真・偽を示す平面フラグテーブルとからなることを特徴とするインデックス型三角形メッシュを用いたデータ構造である。
また、本発明の請求項８は、請求項７に記載のデータ構造において、前記頂点座標インデックステーブルおよび前記平面フラグテーブルは、三角形セット形式または三角形ストリップ形式のいずれかであることを特徴とするデータ構造である。
また、本発明の請求項９は、ｎ次元空間の形状モデルを三角形メッシュで表した形状データを圧縮するデータ圧縮装置において、同一の平面上の複数頂点に対し、重複することなく頂点座標テーブルに格納し、その複数の頂点座標インデックスを連続して頂点座標インデックステーブルに格納する頂点座標圧縮手段と、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを重複することなく法線ベクトルテーブルに格納し、その法線ベクトルインデックスを法線ベクトルインデックステーブルに格納し、該頂点に対しては真を、また該平面上の他の頂点には偽を平面フラグテーブルに格納する法線ベクトル圧縮手段を備えることを特徴とする。
【０００６】
また、本発明の請求項１０は、ｎ次元空間の形状モデルを三角形メッシュで表した形状データを圧縮するデータ圧縮方法において、重複することなく頂点座標テーブルに格納し、その複数の頂点座標インデックスを連続して頂点座標インデックステーブルに格納し、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを重複することなく法線ベクトルテーブルに格納し、その法線ベクトルインデックスを法線ベクトルインデックステーブルに格納し、該頂点に対しては真を、また該平面上の他の頂点には偽を平面フラグテーブルに格納することを特徴とする。
また、本発明の請求項１１は、請求項９に記載のデータ圧縮装置で圧縮された形状データを伸張するデータ伸張装置であって、前記頂点座標インデックステーブルに連続して格納されたすべての頂点座標を、頂点に対する頂点座標インデックスによって前記頂点座標テーブルから頂点座標を求めて読み出して頂点座標を伸張する頂点座標伸張手段と、前記平面フラグテーブルから真を読み出した場合に、前記頂点座標インデックステーブルに連続して格納された複数の頂点座標を同一の平面上の複数頂点の頂点座標とみなし、前記法線ベクトルインデックステーブルに格納された単一の法線ベクトルインデックスを同一の平面上の複数頂点の法線ベクトルインデックスとして割り当てて、この法線ベクトルインデックスによって前記法線ベクトルテーブルから法線ベクトルを取り出すことにより法線ベクトルを伸張する法線ベクトル伸張手段とを備えることを特徴とする。
【０００７】
また、本発明の請求項１２は、請求項１０に記載のデータ圧縮方法で圧縮された形状データを伸張するデータ伸張方法であって、前記頂点座標インデックステーブルに連続して格納されたすべての頂点座標を、頂点に対する頂点座標インデックスによって前記頂点座標テーブルから頂点座標を求めて読み出して頂点座標を伸張し、前記平面フラグテーブルから真を読み出した場合に、前記頂点座標インデックステーブルに連続して格納された複数の頂点座標を同一の平面上の複数頂点の頂点座標とみなし、前記法線ベクトルインデックステーブルに格納された単一の法線ベクトルインデックスを同一の平面上の複数頂点の法線ベクトルインデックスとして割り当てて、この法線ベクトルインデックスによって前記法線ベクトルテーブルから法線ベクトルを取り出すことにより法線ベクトルを伸張することを特徴とする。
また、本発明の請求項１３は、ｎ次元空間の形状モデルを三角形メッシュで表した形状データを格納するデータ構造であって、ｎ次元の頂点座標が格納された頂点座標テーブルと、ｎ次元の法線ベクトルが格納された法線ベクトルテーブルと、頂点座標テーブルへのインデックスが格納された頂点座標インデックステーブルと、法線ベクトルテーブルへのインデックスが格納された法線ベクトルインデックステーブルと、頂点ごとに真・偽を示す頂点座標参照フラグテーブルと、頂点ごとに真・偽を示す法線ベクトル参照フラグテーブルと、頂点ごとに真・偽を示す平面フラグテーブルとからなることを特徴とする参照型三角形メッシュを用いたデータ構造である。
また、本発明の請求項１４は、請求項１３に記載のデータ構造において、前記頂点座標参照テーブル、前記法線ベクトル参照フラグテーブルおよび前記平面フラグテーブルは、三角形セット形式または三角形ストリップ形式のいずれかであることを特徴とするデータ構造である。
【０００８】
また、本発明の請求項１５は、ｎ次元空間の形状モデルを三角形メッシュで表した形状データを圧縮するデータ圧縮装置において、同一の平面上の複数の頂点に対し、初めて参照される頂点座標については、頂点座標を頂点座標テーブルに格納し、該複数の頂点に対応する頂点座標参照フラグテーブルに真を格納し、２回目以降参照される頂点座標については、頂点座標インデックスを頂点座標インデックステーブルに格納し、該複数の頂点に対応する頂点座標参照フラグテーブルに偽を格納する頂点座標圧縮手段と、初めて参照される法線ベクトルについては、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを法線ベクトルテーブルに格納し、該頂点に対応する法線ベクトル参照フラグテーブルに真を格納し、２回目以降に参照される法線ベクトルについては、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを法線ベクトルテーブルに格納して、その法線ベクトルインデックスを法線ベクトルインデックステーブルに格納し、該頂点に対応する法線ベクトル参照フラグテーブルに偽を格納し、該単一の法線ベクトルに対応する頂点に対しては真を平面フラグテーブルに格納する法線ベクトル圧縮手段を備えることを特徴とする。
また、本発明の請求項１６は、ｎ次元空間の形状モデルを三角形メッシュで表した形状データを圧縮するデータ圧縮方法において、同一の平面上の複数の頂点に対し、初めて参照される頂点座標については、頂点座標を頂点座標テーブルに格納し、該複数の頂点に対応する頂点座標参照フラグテーブルに真を格納し、２回目以降参照される頂点座標については、頂点座標インデックスを頂点座標インデックステーブルに格納し、該複数の頂点に対応する頂点座標参照フラグテーブルに偽を格納し、初めて参照される法線ベクトルについては、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを法線ベクトルテーブルに格納し、該頂点に対応する法線ベクトル参照フラグテーブルに真を格納し、２回目以降に参照される法線ベクトルについては、同一の平面上の頂点のうち単一の頂点に対してのみ、その頂点における法線ベクトルを法線ベクトルテーブルに格納して、その法線ベクトルインデックスを法線ベクトルインデックステーブルに格納し、該頂点に対応する法線ベクトル参照フラグテーブルに偽を格納し、該単一の法線ベクトルに対応する頂点に対しては真を平面フラグテーブルに格納することを特徴とする。
【０００９】
また、本発明の請求項１７は、請求項１５に記載のデータ圧縮装置で圧縮された形状データを伸張するデータ伸張装置であって、処理中の頂点に対応する前記頂点座標参照フラグテーブルのフラグが真の場合は、該頂点の頂点座標を前記頂点座標テーブルから読み出し、該頂点に対応する頂点座標参照フラグテーブルのフラグが偽の場合は、該頂点に対応する前記頂点座標インデックステーブルの頂点座標インデックスが指す座標値を前記頂点座標テーブルから読み出すことによって頂点座標を伸張する頂点座標伸張手段と、平面上の頂点の法線ベクトル参照フラグテーブルのフラグが真の場合は、該頂点に対応する法線ベクトルを法線ベクトルテーブルから読み出し、該頂点の法線ベクトル参照フラグテーブルのフラグが偽の場合は、該頂点に対応する法線ベクトルを法線ベクトルインデックステーブルの法線ベクトルインデックスが指す法線ベクトルテーブルから読み出すことで、同一の平面上の複数頂点に対して法線ベクトルを割り当てることにより法線ベクトルを伸張する法線ベクトル伸張手段とを備えることを特徴とする。
また、本発明の請求項１８は、請求項１６に記載のデータ圧縮装置で圧縮された形状データを伸張するデータ伸張方法であって、処理中の頂点に対応する前記頂点座標参照フラグテーブルのフラグが真の場合は、該頂点の頂点座標を前記頂点座標テーブルから読み出し、該頂点に対応する頂点座標参照フラグテーブルのフラグが偽の場合は、該頂点に対応する前記頂点座標インデックステーブルの頂点座標インデックスが指す座標値を前記頂点座標テーブルから読み出すことによって頂点座標を伸張し、平面上の頂点の法線ベクトル参照フラグテーブルのフラグが真の場合は、該頂点に対応する法線ベクトルを法線ベクトルテーブルから読み出し、該頂点の法線ベクトル参照フラグテーブルのフラグが偽の場合は、該頂点に対応する法線ベクトルを法線ベクトルインデックステーブルの法線ベクトルインデックスが指す法線ベクトルテーブルから読み出すことで、同一の平面上の複数頂点に対して法線ベクトルを割り当てることにより法線ベクトルを伸張することを特徴とする。
また、本発明の請求項１９は、請求項１、７または１３に記載のデータ構造において、前記頂点座標テーブルおよび前記法線ベクトルテーブルは、浮動小数点表現またはベクトル量子化圧縮がなされていることを特徴とするデータ構造である。
【００１０】
また、本発明の請求項２０は、ｎ次元空間の形状モデルを処理するｎ次元形状モデル処理装置において、請求項３、９または１５に記載のデータ圧縮装置と、請求項５、１１または１７に記載のデータ伸張装置の少なくともいずれかを備え、前記データ圧縮装置は、ｎ次元形状モデルを圧縮した形状データを生成して送信し、前記データ伸張装置は、受信した該形状データを伸張して、ｎ次元形状モデルを生成するようにしたことを特徴とする。
また、本発明の請求項２１は、コンピュータに、請求項３、９または１５に記載のデータ圧縮装置の機能、請求項５、１１または１７に記載のデータ伸張装置の機能、または、請求項２０に記載のｎ次元形状モデル処理装置の機能を実行させるためのプログラムである。
また、本発明の請求項２２は、請求項２１に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【００１１】
本発明によれば、ｎ次元空間における三角形メッシュの圧縮および伸張を行うことができる。
このデータ構造を使用すると、データサイズが減少し、ハードディスク等保存装置のスペース効率が向上する。
また、データサイズが減少するため、表示速度および転送速度が向上する。
さらに、３次元形状処理装置にこのデータ構造を使用することによって、コンパクトな３次元形状モデルデータを実現できる。
【発明を実施するための最良の形態】
【００１２】
以下、図面を参照して、本発明の好適な実施形態を詳細に説明する。
また、下記の（１）〜（３）の前提に基づき、本発明の構成および動作を説明する。
（１）本発明で扱う三角形メッシュは、一般的な３次元形状処理システムで生成された曲面をもととして生成されたものであり、三角形メッシュの各頂点がどの面（曲面や平面）に対応しているかを形状モデルデータとして保持しているものとする。
（２）面には、平面とそれ以外の曲面があり、平面については平面上のすべての点に対して共通な法線ベクトル（ｘ成分、ｙ成分、ｚ成分）の情報が取得できるものとする。
例えば、図１に示す平面の場合、５つの三角形メッシュからなり、それらの５つの三角形メッシュが共通の法線ベクトルを持っている。すなわち、この平面の７つの頂点における法線ベクトルは、図１に示した共通の法線ベクトルを持っている。
（３）三角形の表現形式としては、三角形セット形式のものと三角形ストリップ形式のものとがある。
このうち、三角形セット形式は、各三角形の３つの頂点座標を順次並べて格納する形式である。例えば、図２は、３つの三角形（Ａ，Ｂ，Ｃ）に対して、その３つの頂点座標を順に格納している。三角形Ａの３つの頂点の座標は（ｔｊ，ｔｊ＋１，ｔｊ＋２）であるから、データ構造にはこの順に頂点座標を格納することになる。
したがって、三角形セット形式の場合には、３つずつ取り出せば１つの三角形を表現することができるので、取り扱いには便利であるが、データの圧縮ということには三角形ストリップ形式より劣っている。
一方、三角形ストリップ形式は、三角形の１つの辺をはさんで隣接した三角形の各頂点座標を順次並べた形式をしており、最後の２つの頂点が次の隣接する三角形の最初の辺の頂点となるように配置する。三角形ストリップ形式の最後は頂点座標値に現れないような値もしくは最後を示すフラグで区切り識別子を与えるようになっている。
例えば、図３は、３つの三角形（Ａ，Ｂ，Ｃ）に対して、その３つの頂点座標をストリップ形式で格納している。この場合、三角形Ａの３つの頂点の座標は上から３つと取り出した（ｔｊ，ｔｊ＋１，ｔｊ＋２）であり、また、三角形Ｂの３つの頂点の座標は２番目以降の３つを取り出した（ｔｊ＋１，ｔｊ＋２，ｔｊ＋３）である。また、頂点の最後には、区切り識別子を置いてある。
したがって、三角形ストリップ形式の場合には、三角形セット形式の場合よりも取り扱いが面倒ではあるが、連続的に三角形を取り出す場合には便利であり、また、データの圧縮ということでは三角形セット形式より勝っている。
【００１３】
次に、本発明で扱う三角形メッシュのデータ格納形式である３つの型（列挙型、インデックス型、参照型）について説明する。
（１）列挙型三角形メッシュ：
列挙型三角形メッシュは、頂点座標テーブルと法線ベクトルテーブルから構成される。
頂点座標テーブルには、三角形メッシュの各頂点座標の（ｘ，ｙ，ｚ）値が三角形セット形式または三角形ストリップ形式のいずれかで格納される。同様に、法線ベクトルテーブルには、各頂点における法線ベクトルの（ｘ成分，ｙ成分，ｚ成分）値が格納される。
（２）インデックス型三角形メッシュ：
インデックス型三角形メッシュは、頂点座標テーブル、法線ベクトルテーブルと、頂点座標テーブルのインデックスを格納した頂点座標インデックステーブル、法線ベクトルテーブルのインデックスを格納した法線ベクトルインデックステーブルから構成される。
頂点座標テーブルは、三角形メッシュの各頂点座標のうち重複する値を持つ頂点座標を１つに統一して、重複のない頂点座標値（ｘ，ｙ，ｚ）値が格納される。
頂点座標インデックステーブルは、三角形メッシュの各頂点座標値が格納された頂点座標テーブルへのインデックスを三角形セット形式または三角形ストリップ形式のいずれかで格納する。
同様に、法線ベクトルテーブルには、各頂点における法線ベクトルのうち重複する値を持つ法線ベクトルを１つに統一して、重複のない法線ベクトル（ｘ成分，ｙ成分，ｚ成分）値が格納される。
法線ベクトルインデックステーブルには、三角形メッシュの各頂点における法線ベクトル値が格納された法線ベクトルテーブルへのインデックスが格納される。
【００１４】
（３）参照型三角形メッシュ：
参照型三角形メッシュは、頂点座標テーブル、法線ベクトルテーブル、頂点座標テーブルへのインデックスを格納した頂点座標インデックステーブル、法線ベクトルテーブルへのインデックスを格納した法線ベクトルインデックステーブル、頂点座標参照フラグテーブル、法線ベクトル参照フラグテーブルとから構成される。
頂点座標テーブルは、まだこのテーブルに登録されていない頂点座標値を登録し、頂点に対応する頂点座標参照フラグテーブルには真のフラグ値が格納される。
また、すでに頂点座標テーブルに登録されている頂点の場合には、そのすでに登録されている頂点座標値へのインデックスを頂点座標インデックステーブルに登録し、その頂点に対応する頂点座標参照フラグテーブルには偽のフラグ値が格納される。
このように格納される頂点座標参照フラグテーブルは、これらのフラグ値を三角形セット形式または三角形ストリップ形式のいずれかで格納する。
頂点座標テーブルから頂点座標値を見つける場合には、頂点座標参照フラグテーブルの真のフラグ値をテーブルの先頭から求める頂点の位置に対応する場所までカウントし、このカウント値を頂点座標テーブルへのインデックスとすることによって求められる。
また、頂点座標インデックステーブルから頂点座標インデックスを見つける場合には、頂点座標参照フラグテーブルの偽のフラグ値をテーブルの先頭から求める頂点の位置に対応する場所までカウントし、このカウント値を頂点座標インデックステーブルへのインデックスとすることによって求められる。
【００１５】
法線ベクトルテーブルは、まだこのテーブルに登録されていない法線ベクトル値を登録する。また、すでに法線ベクトルテーブルに登録されている法線ベクトルの場合には、そのすでに登録されている法線ベクトル値へのインデックスを法線ベクトルインデックステーブルに登録する。
法線ベクトル参照フラグテーブルは、頂点ごとに対応して、法線ベクトルテーブルまたは法線ベクトルインデックステーブルのいずれのテーブルに法線ベクトルを格納したかを示すフラグ値を三角形セット形式または三角形ストリップ形式のいずれかで格納する。
この法線ベクトル参照フラグテーブルのフラグ値が真の場合には、法線ベクトルを法線ベクトルテーブルに格納したことを示し、フラグ値が偽の場合には、法線ベクトルを法線ベクトルインデックステーブルを介して格納したことを示している。
ここで、ある平面に属する三角メッシュの頂点の法線ベクトルは共通するので、１つの法線ベクトルだけを法線ベクトルテーブルまたは法線ベクトルインデックステーブルのいずれかに登録するようにする。この場合、法線ベクトルを登録した平面上の他の頂点のフラグ値は真・偽以外の値として登録する。
法線ベクトルテーブルから法線ベクトル値を見つける場合には、法線ベクトル参照フラグテーブルの真のフラグ値をテーブルの先頭から求める頂点の位置に対応する場所までカウントし、このカウント値を法線ベクトルテーブルへのインデックスとすることによって求められる。
また、法線ベクトルインデックステーブルから法線ベクトルインデックスを見つける場合には、法線ベクトル参照フラグテーブルの偽のフラグ値をテーブルの先頭から求める頂点の位置に対応する場所までカウントし、このカウント値を法線ベクトルインデックステーブルへのインデックスとすることによって求められる。
この参照型を使用して格納すると、インデックス型よりさらにデータ格納領域を縮小することができる。
【００１６】
＜実施形態１＞
（１）列挙型三角形メッシュを用いた形状データのデータ構造：
図４は、本発明の列挙型三角形メッシュのデータ構造を用いて、ｎ次元（２乃至４次元）形状モデルを格納するためのデータ構造を示している。
ｎ次元形状モデルを格納するためのデータ構造は、ｎ次元の頂点座標が格納された頂点座標テーブルＶ、ｎ次元の法線ベクトルが格納された法線ベクトルテーブルＵ、頂点ごとに真・偽を示す平面フラグテーブルＰから構成される。
頂点座標テーブルＶには、頂点座標の数（＝ｎｖ）とｎｖ個の頂点座標が頂点座標Ｖ１から頂点座標Ｖｎｖの順に、三角形セット形式または三角形ストリップ形式のいずれかの形式で格納されている。また、これらの頂点座標は、それぞれ（ｘ，ｙ，ｚ）の３座標値から構成され、各座標値は浮動小数点あるいはベクトル量子化圧縮が行われる。
平面フラグテーブルＰには、頂点座標テーブルＶに登録された頂点の順序と同じに、その頂点が平面上の点かまたは曲面上の点かによってそれぞれ真と偽とを格納する。したがって、曲面フラグテーブルのサイズは、頂点座標の数と同じになっている。
法線ベクトルテーブルＵには、法線ベクトルの数（＝ｎｕ）とｎｕ個の法線ベクトルが法線ベクトルＵ１から法線ベクトルＵｎｕの順に格納されている。また、これらの法線ベクトルは、それぞれ（ｘ成分，ｙ成分，ｚ成分）の３成分から構成され、各座標値は浮動小数点あるいはベクトル量子化圧縮が行われる。
さらに、１つ乃至それ以上の三角形メッシュが同一平面上にある場合には、共通した法線ベクトルを使用するため、法線ベクトルテーブルＵには１つの法線ベクトルのみを登録する。
【００１７】
（２）形状データの圧縮：
次に、本実施形態１で示したデータ構造（図４）を用いて、所定のｎ次元形状データを格納する方法について説明する。
はじめに、ｎ次元形状を表すデータは、すでにｎ次元形状処理装置によってデータベース化（形状ＤＢ）されているものとする。
図５は、本実施形態１のデータ圧縮装置の構成を示すブロック図である。同図において、データ圧縮装置は、頂点座標圧縮手段２０、法線ベクトル圧縮手段３０、生成したテーブル（頂点座標テーブル、法線ベクトルテーブル、平面フラグテーブル）および形状ＤＢを格納するデータ保持手段４０と、これらの手段を制御する制御手段１０とから構成される。
図６は、形状ＤＢの中の指定された形状データを図４のデータ構造の形式で格納するときの処理手順を示すフローチャートである。
形状ＤＢ中の指定された形状データに含まれるすべての頂点の頂点座標を連続して格納した頂点座標テーブルをデータ保持手段４０へ書き込む（ステップＳ１０）。ステップＳ１０で頂点座標圧縮手段２０を構成する。
指定された形状データに含まれる面が平面であるか否かを判定し、平面である場合には（ステップＳ１１のＹＥＳ）、この平面に属する三角メッシュの共通の法線ベクトルを１つの法線ベクトルとして法線ベクトルテーブルに格納する（ステップＳ１２）。
平面フラグテーブルには、この平面に属する三角メッシュの頂点数分の真のフラグを格納し（ステップＳ１３）、ステップＳ１６へ進む。このとき、平面フラグテーブルへフラグ値を格納する順序は、頂点座標テーブルへ頂点座標を登録したときと同じ順序となっている。
一方、平面でない場合は（ステップＳ１１のＮＯ）、同一曲面上のすべての頂点に対応付けて法線ベクトルを連続して法線ベクトルテーブルに格納する（ステップＳ１４）。
さらに、同一曲面上のすべての頂点に対応付けて平面フラグテーブルに偽のフラグを格納し（ステップＳ１５）、ステップＳ１６へ進む。
上記のステップＳ１１からステップＳ１５をすべての面に対して行なって（ステップＳ１６）、作成された平面フラグテーブルと法線ベクトルテーブルとをデータ保持手段４０へ書き込む。これらステップＳ１１からステップＳ１６により、法線ベクトル圧縮手段３０を構成する。
【００１８】
（３）データの伸張：
図７は、実施形態１のデータ構造で圧縮して格納された形状データを伸張するデータ伸張装置の構成を示すブロック図である。同図において、データ伸張装置は、頂点座標伸張手段１１０、法線ベクトル伸張手段１２０、形状データ（頂点座標テーブル、平面フラグテーブル、法線ベクトルテーブル）の保持および伸張された形状モデルデータを形状ＤＢへ格納するデータ保持手段１３０と、これらの手段を制御する制御手段１００とから構成される。
図８は、本実施形態１のデータ伸張装置で伸張された形状データを形状ＤＢへ格納するときの処理手順を示すフローチャートである。
データ保持手段１３０から頂点座標テーブルに連続して格納されたすべての頂点座標を読み出し、形状ＤＢへ書き出す（ステップＳ２０）。このステップＳ２０により、頂点座標伸張手段１１０を構成する。
法線ベクトルテーブルから単一の法線ベクトルを読み出し（ステップＳ２１）、読み出した法線ベクトルを平面フラグに対応する頂点の法線ベクトルとして割り当てて、形状ＤＢを更新する（ステップＳ２２）。
次に、未処理の平面フラグの有無をチェックし、未処理の平面フラグがない場合（ステップＳ２３のＮＯ）、処理を終了する。
一方、未処理の平面フラグがあって（ステップＳ２３のＹＥＳ）、その平面フラグが真のとき（ステップＳ２４のＹＥＳ）、再度ステップＳ２２以降の処理を行なって、真のフラグが連続している場合の平面フラグに対応した頂点の法線ベクトルとして割り当てて、形状ＤＢを更新する。
また、平面フラグが偽のときには（ステップＳ２４のＮＯ）、再度ステップＳ２１以降の処理を行なって、新たな面に対する頂点の法線ベクトルを割り当てて、形状ＤＢを更新する。
ステップＳ２１からＳ２４までにより、法線ベクトル伸張手段１２０を構成する。
【００１９】
図９は、列挙型三角形メッシュを用いたときのデータ格納例である。図９は、頂点［０］から頂点［６］までの頂点座標７組を格納した頂点座標テーブル、法線ベクトル５組を格納した法線ベクトルテーブルを示している。
頂点［３］と頂点［４］と頂点［５］が平面上の頂点である場合、平面フラグテーブルのフラグ［３］、フラグ［４］、フラグ［５］に真が格納される。この平面上の頂点［３］と頂点［４］と頂点［５］の法線ベクトルは共通であるので、頂点［３］での法線ベクトルであるＸ成分［３］とＹ成分［３］とＺ成分［３］だけを法線ベクトルテーブルに格納し、他の頂点［４］と頂点［５］の法線ベクトルは、法線ベクトルテーブルに格納しない。
上記のように圧縮された形状データを伸張する場合には、平面フラグテーブルを参照したとき、フラグ［３］、フラグ［４］、フラグ［５］が真であるから、頂点［３］の法線ベクトルであるＸ成分［３］とＹ成分［３］とＺ成分［３］だけを読み込み、頂点［４］と頂点［５］については、Ｘ成分［３］とＹ成分［３］とＺ成分［３］を用いる。
以上のようにデータ圧縮装置およびデータ伸張装置を構成することによって、ｎ次元空間における三角形メッシュの圧縮および伸張を行なうことができる。
また、このデータ構造を使用すると、真・偽を表すのみである平面フラグテーブルのサイズは、Ｘ成分、Ｙ成分、Ｚ成分を表す法線ベクトルテーブルのサイズに比較してかなり小さく、平面フラグテーブルの追加によるデータの増加よりも、法線ベクトルテーブルの圧縮によるデータの減少の方の割合が大きいので、全体のデータサイズが減少し、ハードディスク等保存装置のスペース効率が向上する。
【００２０】
＜実施形態２＞
（１）インデックス型三角形メッシュを用いた形状データのデータ構造：
図１０は、本発明のインデックス型三角形メッシュのデータ構造を用いて、ｎ次元（２乃至４次元）形状モデルを格納するためのデータ構造を示している。
ｎ次元形状モデルを格納するためのデータ構造は、ｎ次元の頂点座標が格納された頂点座標テーブルＶ、ｎ次元の法線ベクトルが格納された法線ベクトルテーブルＵ、頂点座標テーブルＶへのインデックスが格納された頂点座標インデックステーブルＳと、法線ベクトルテーブルＵへのインデックスが格納された法線ベクトルインデックステーブルＴと、頂点ごとに真・偽を示す平面フラグテーブルＰから構成される。
頂点座標テーブルＶには、テーブルに登録された頂点座標の数（＝ｎｖ）とｎｖ個の頂点座標が頂点座標Ｖ１から頂点座標Ｖｎｖの順に重複なしの座標値として格納され、これらの頂点座標は、それぞれ（ｘ，ｙ，ｚ）の３座標値から構成され、各座標値は浮動小数点あるいはベクトル量子化圧縮が行われる。
頂点座標インデックステーブルＳには、頂点座標インデックスの数（＝ｎｖｉ）とｎｖｉ個の頂点座標インデックス（頂点の座標値を格納した頂点座標テーブルＶへのインデックス）がＳ１からＳｎｖｉの順に三角形セット形式または三角形ストリップ形式のいずれかの形式で格納される。頂点座標インデックステーブルのサイズは、すべての頂点の個数と同じになっている。
平面フラグテーブルＰには、頂点座標インデックステーブルＳに登録された頂点の順序と同じに、その頂点が平面上の点かまたは曲面上の点かによってそれぞれ真と偽とを格納する。したがって、曲面フラグテーブルのサイズは、頂点座標インデックスの数と同じになっている。
法線ベクトルテーブルＵには、法線ベクトルの数（＝ｎｕ）とｎｕ個の法線ベクトルが法線ベクトルＵ１から法線ベクトルＵｎｕの順に重複なしの値として格納され、これらの法線ベクトルは、それぞれ（ｘ成分，ｙ成分，ｚ成分）の３成分から構成され、各座標値は浮動小数点あるいはベクトル量子化圧縮が行われる。
法線ベクトルインデックステーブルＴには、法線ベクトルインデックスの数（＝ｎｕｉ）とｎｕｉ個の法線ベクトルインデックス（法線ベクトルの値を格納した法線ベクトルテーブルＵへのインデックス）がＴ１からＴｎｕｉの順に格納される。
さらに、１つ乃至それ以上の三角形メッシュが同一平面上にある場合には、共通した法線ベクトルを使用するため、法線ベクトルテーブルＴには１つの法線ベクトルへのインデックスのみを登録する。
【００２１】
（２）形状データの圧縮：
次に、本実施形態２で示したデータ構造（図１０）を用いて、所定のｎ次元形状データを格納する方法について説明する。
はじめに、ｎ次元形状を表すデータは、すでにｎ次元形状処理装置によってデータベース化（形状ＤＢ）されているものとする。
本実施形態２のデータ圧縮装置の構成は、実施形態１と同様であるから説明を省略する（図５参照）。
図１１は、形状ＤＢの中の指定された形状データを図１０のデータ構造の形式で格納するときの処理手順を示すフローチャートである。
形状ＤＢ中の指定された形状データに含まれるすべての頂点の頂点座標を重複することなく頂点座標テーブルへ書き込む。次に、この頂点座標テーブルを参照して、すべての頂点座標への頂点座標インデックスを求め、この頂点座標インデックスを連続して格納した頂点座標インデックステーブルを作成して、これらの頂点座標テーブルおよび頂点座標インデックステーブルをデータ保持手段４０へ書き込む（ステップＳ３０）。ステップＳ３０で頂点座標圧縮手段２０を構成する。
指定された形状データに含まれる面が平面であるか否かを判定し、平面である場合には（ステップＳ３１のＹＥＳ）、この平面に属する三角メッシュの共通の法線ベクトルを１つの法線ベクトルインデックスとして法線ベクトルインデックステーブルに格納する（ステップＳ３２）。この法線ベクトルインデックスは、重複しない法線ベクトルを法線ベクトルテーブルへ登録し、その登録したときのテーブルインデックスを用いる。
【００２２】
平面フラグテーブルには、この平面に属する三角メッシュの頂点数分の真のフラグを格納し（ステップＳ３３）、ステップＳ３６へ進む。このとき、平面フラグテーブルへフラグ値を格納する順序は、頂点座標インデックステーブルへ頂点座標インデックスを登録したときと同じ順序となっている。
一方、平面でない場合は（ステップＳ３１のＮＯ）、同一曲面上のすべての頂点に対応付けて法線ベクトルインデックスを連続して法線ベクトルインデックステーブルに格納する（ステップＳ３４）。この法線ベクトルインデックスは、重複しない法線ベクトルを法線ベクトルテーブルへ登録し、その登録したときのテーブルインデックスを用いる。
さらに、同一曲面上のすべての頂点に対応付けて平面フラグテーブルに偽のフラグを格納し（ステップＳ３５）、ステップＳ３６へ進む。
上記のステップＳ３１からステップＳ３５をすべての面に対して行なって（ステップＳ３６）、作成された平面フラグテーブル、法線ベクトルテーブルと法線ベクトルインデックステーブルをデータ保持手段４０へ書き込む。これらステップＳ３１からステップＳ３６により、法線ベクトル圧縮手段３０を構成する。
【００２３】
（３）データの伸張：
本実施形態２のデータ構造で圧縮して格納された形状データを伸張するデータ伸張装置の構成は、実施形態１と同様であるから説明を省略する（図７参照）。
図１２は、本実施形態２のデータ伸張装置で伸張された形状データを形状ＤＢへ格納するときの処理手順を示すフローチャートである。
データ保持手段１３０から頂点座標インデックステーブルに連続して格納されたすべての頂点座標インデックスを読み出し、頂点座標テーブルを参照して、この頂点座標インデックスに対応する位置に格納されている頂点座標値を取り出し形状ＤＢへ書き出す（ステップＳ４０）。このステップＳ４０により、頂点座標伸張手段１１０を構成する。
法線ベクトルインデックステーブルから単一の法線ベクトルインデックスを読み出し、法線ベクトルテーブルを参照して、この法線ベクトルインデックスに対応する位置に格納されている法線ベクトル値を取り出し（ステップＳ４１）、取り出した法線ベクトルを平面フラグに対応する頂点の法線ベクトルとして割り当てて、形状ＤＢを更新する（ステップＳ４２）。
次に、未処理の平面フラグの有無をチェックし、未処理の平面フラグがない場合（ステップＳ４３のＮＯ）、処理を終了する。
一方、未処理の平面フラグがあって（ステップＳ４３のＹＥＳ）、その未処理の平面フラグが真のとき（ステップＳ４４のＹＥＳ）、再度ステップＳ４２以降の処理を行なって、真のフラグが連続している場合の平面フラグに対応した頂点の法線ベクトルとして割り当てて、形状ＤＢを更新する。
また、その未処理の平面フラグが偽のときには（ステップＳ４４のＮＯ）、再度ステップＳ４１以降の処理を行なって、新たな面に対する頂点の法線ベクトルを割り当てて、形状ＤＢを更新する。
ステップＳ４１からＳ４４までにより、法線ベクトル伸張手段１２０を構成する。
以上のようにデータ圧縮装置およびデータ伸張装置を構成することによって、ｎ次元空間における三角形メッシュの圧縮および伸張を行なうことができる。
また、このデータ構造を使用すると、データサイズが減少し、ハードディスク等保存装置のスペース効率が向上する。
【００２４】
＜実施形態３＞
（１）参照型三角形メッシュを用いた形状データのデータ構造：
図１３は、本発明の参照型三角形メッシュのデータ構造を用いて、ｎ次元（２乃至４次元）形状モデルを格納するためのデータ構造を示している。
ｎ次元形状モデルを格納するためのデータ構造は、ｎ次元の頂点座標が格納された頂点座標テーブルＶ、ｎ次元の法線ベクトルが格納された法線ベクトルテーブルＵ、頂点座標テーブルＶへのインデックスが格納された頂点座標インデックステーブルＳと、法線ベクトルテーブルＵへのインデックスが格納された法線ベクトルインデックステーブルＴと、頂点ごとに真・偽を示す頂点座標参照フラグテーブルＦＶと、頂点ごとに真・偽を示す法線ベクトル参照フラグテーブルＦＵと、頂点ごとに真・偽を示す平面フラグテーブルＰから構成される。
頂点座標テーブルＶには、テーブルに登録された頂点座標の数（＝ｎｖ）とｎｖ個の頂点座標が頂点座標Ｖ１から頂点座標Ｖｎｖの順に重複なしの座標値として格納され、これらの頂点座標は、それぞれ（ｘ，ｙ，ｚ）の３座標値から構成され、各座標値は浮動小数点あるいはベクトル量子化圧縮が行われる。
頂点座標インデックステーブルＳには、頂点座標インデックスの数（＝ｎｖｉ）とｎｖｉ個の頂点座標インデックス（頂点の座標値を格納した頂点座標テーブルＶへのインデックス）がＳ１からＳｎｖｉの順に格納される。この頂点座標インデックステーブルＳへは、すでに頂点座標テーブルへ登録された頂点に対してのみ作成される。
頂点座標参照フラグテーブルＦＶは、参照フラグの個数（ｎｖｒ）とｎｖｒ個の頂点座標参照フラグがＦＶ１からＦＶｎｖｒの順に、頂点ごとに三角形セット形式または三角形ストリップ形式のいずれかの形式で格納される。この頂点座標参照フラグの個数（ｎｖｒ）は、すべての頂点の個数と同じである。
【００２５】
三角形メッシュの各頂点の座標は、次のようにして求める。
まず、求める頂点の位置が頂点座標参照フラグテーブルのどこに位置するかを探す。
次に、この参照フラグテーブルの先頭から見つけた頂点位置までの真のフラグの個数をカウントし、このカウント値の位置に対応する頂点座標テーブルの座標値を求める。
一方、この参照フラグテーブルの先頭から見つけた頂点位置までの偽のフラグの個数をカウントし、このカウント値の位置に対応する頂点座標インデックステーブルの頂点座標インデックスを求め、このインデックスに対応する頂点座標テーブルの座標値を求める。
平面フラグテーブルＰには、頂点座標インデックステーブルＳに登録された頂点の順序と同じに、その頂点が平面上の点かまたは曲面上の点かによってそれぞれ真と偽とを格納する。したがって、曲面フラグテーブルのサイズは、頂点座標参照フラグの数と同じになっている。
法線ベクトルテーブルＵには、法線ベクトルの数（＝ｎｕ）とｎｕ個の法線ベクトルが法線ベクトルＵ１から法線ベクトルＵｎｕの順に重複なしの値として格納され、これらの法線ベクトルは、それぞれ（ｘ成分，ｙ成分，ｚ成分）の３成分から構成され、各座標値は浮動小数点あるいはベクトル量子化圧縮が行われる。
【００２６】
法線ベクトルインデックステーブルＴには、法線ベクトルインデックスの数（＝ｎｕｉ）とｎｕｉ個の法線ベクトルインデックス（法線ベクトルの値を格納した法線ベクトルテーブルＵへのインデックス）がＴ１からＴｎｕｉの順に格納される。この法線ベクトルインデックステーブルＴへは、すでに法線ベクトルテーブルへ登録された法線ベクトルに対してのみ作成される。
法線ベクトル参照フラグテーブルＦＵは、参照フラグの個数（ｎｕｒ）とｎｕｒ個の法線ベクトル参照フラグがＦＵ１からＦＵｎｕｒの順に、頂点ごとに三角形セット形式または三角形ストリップ形式のいずれかの形式で格納される。この法線ベクトル参照フラグの個数（ｎｕｒ）は、すべての頂点の個数と同じである。
この法線ベクトル参照フラグのフラグ値が真の場合には、法線ベクトルを法線ベクトルテーブルに格納したことを示し、フラグ値が偽の場合には、法線ベクトルを法線ベクトルインデックステーブルを使って格納したことを示している。
ここで、平面上の三角メッシュの頂点の法線ベクトルは共通するので、１つの法線ベクトルだけを法線ベクトルテーブルまたは法線ベクトルインデックステーブルのいずれかに登録するようにする。この場合、法線ベクトルを登録した平面上の他の頂点のフラグ値は真・偽以外の値として登録する。
法線ベクトルテーブルから法線ベクトル値を見つける場合には、法線ベクトル参照フラグテーブルの真のフラグ値をテーブルの先頭から求める頂点の位置に対応する場所までカウントし、このカウント値を法線ベクトルテーブルへのインデックスとすることによって求められる。
また、法線ベクトルインデックステーブルから法線ベクトルインデックスを見つける場合には、法線ベクトル参照フラグテーブルの偽のフラグ値をテーブルの先頭から求める頂点の位置に対応する場所までカウントし、このカウント値を法線ベクトルインデックステーブルへのインデックスとすることによって求められる。
【００２７】
（２）形状データの圧縮：
次に、本実施形態３で示したデータ構造（図１３）を用いて、所定のｎ次元形状データを格納する方法について説明する。
はじめに、ｎ次元形状を表すデータは、すでにｎ次元形状処理装置によってデータベース化（形状ＤＢ）されているものとする。
本実施形態３のデータ圧縮装置の構成は、実施形態１と同様であるから構成の説明を省略する（図５参照）。
図１４、図１５および図１６は、形状ＤＢの中の指定された形状データを図１３のデータ構造の形式で格納するときの処理手順を示すフローチャートである。
形状ＤＢ中の指定された形状データに含まれる面上の頂点座標が初めて参照される頂点座標か否かを判定し、初めて参照される頂点座標の場合は（ステップＳ５０のＹＥＳ）、頂点の頂点座標を頂点座標テーブルに格納し（ステップＳ５１）、その頂点に対応する頂点座標参照フラグテーブルに真のフラグを格納し（ステップＳ５２）、ステップＳ５５へ進む。
一方、２回目以降に参照される頂点座標の場合は（ステップＳ５０のＮＯ）、すでに格納された頂点座標への頂点座標インデックスを求め、この頂点座標インデックスを頂点座標インデックステーブルに格納し（ステップＳ５３）、その頂点に対応する頂点座標参照フラグテーブルに偽のフラグを格納し（ステップＳ５４）、ステップＳ５５へ進む。
ステップＳ５０からステップＳ５５をその面のすべての頂点に対して行って、作成された頂点座標テーブル、頂点座標インデックステーブルおよび頂点座標参照フラグテーブルをデータ保持手段４０へ書き込む。ステップＳ５０からＳ５５で頂点座標圧縮手段２０を構成する。
指定された形状データに含まれる面が平面であるか否かを判定し、平面である場合には（ステップＳ５６のＹＥＳ）、この平面に含まれる頂点の法線ベクトルが法線ベクトルテーブルに登録されているかを調べ、登録されていないときには（ステップＳ５７のＹＥＳ）、この法線ベクトルを法線ベクトルテーブルに登録し（ステップＳ５８）、この法線ベクトルに対する頂点と対応した法線ベクトル参照フラグテーブルに真を格納し、同一の平面上の他の頂点に対応した法線ベクトル参照フラグテーブルには真・偽以外の値を格納し（ステップＳ５９）、ステップＳ６２へ進む。
一方、登録されているときには（ステップＳ５７のＮＯ）、この法線ベクトルと同じ法線ベクトルの値を格納した法線ベクトルインデックスを法線ベクトルインデックステーブルに登録し（ステップＳ６０）、この法線ベクトルに対する頂点と対応した法線ベクトル参照フラグテーブルに偽を格納し、同一の平面上の他の頂点に対応した法線ベクトル参照フラグテーブルには真・偽以外の値を格納し（ステップＳ６１）、ステップＳ６２へ進む。
【００２８】
平面フラグテーブルには、この平面に属する三角メッシュの頂点数分の真のフラグを格納し（ステップＳ６２）、まだ未処理の面があれば（ステップＳ６３のＹＥＳ）、ステップＳ５０へ戻って他の面についての法線ベクトルの処理を行う。
他方、処理中の面が平面でない場合は（ステップＳ５６のＮＯ）、同一曲面上の頂点の法線ベクトルがまだ法線ベクトルテーブルに登録されていなければ（ステップＳ６４のＹＥＳ）、この法線ベクトルを法線ベクトルテーブルに登録し（ステップＳ６５）、この法線ベクトルに対する頂点と対応した法線ベクトル参照フラグテーブルに真を格納し（ステップＳ６６）、ステップＳ６９へ進む。
また、登録されているときには（ステップＳ６４のＮＯ）、この法線ベクトルと同じ法線ベクトルの値を格納した法線ベクトルインデックスを法線ベクトルインデックステーブルに登録し（ステップＳ６７）、この法線ベクトルに対する頂点と対応した法線ベクトル参照フラグテーブルに偽を格納し（ステップＳ６８）、ステップＳ６９へ進む。
さらに、平面フラグテーブルには偽のフラグを格納し（ステップＳ６９）、ステップＳ６４からステップＳ７０をその面のすべての頂点に対して行なって、ステップＳ６３へ戻り、作成された平面フラグテーブル、法線ベクトルテーブル、法線ベクトルインデックステーブルおよび法線ベクトル参照フラグテーブルをデータ保持手段４０へ書き込む。これらステップＳ５６からステップＳ７０により、法線ベクトル圧縮手段３０を構成する。
【００２９】
（３）データの伸張：
本実施形態３のデータ構造で圧縮して格納された形状データを伸張するデータ伸張装置の構成は実施形態１と同様であるから説明を省略する（図７参照）。
図１７および図１８は、本実施形態３のデータ伸張装置で伸張された形状データを形状ＤＢへ格納するときの処理手順を示すフローチャートである。
データ保持手段１３０中の頂点座標参照フラグテーブルの処理中の頂点のフラグが真である場合（ステップＳ８０のＹＥＳ）、処理中の頂点の頂点座標テーブルでの位置を求め、その位置における座標値を読み出して形状ＤＢへ書き出し（ステップＳ８１）、ステップＳ８３へ進む。ここで、処理中の頂点の頂点座標テーブルでの位置は、頂点座標参照フラグテーブルの先頭から処理中の頂点までの真フラグの個数である。
一方、処理中の頂点のフラグが偽の場合（ステップＳ８０のＮＯ）、処理中の頂点の頂点座標インデックステーブルでの位置を求め、その位置の頂点座標インデックスが指す頂点座標テーブルにおける座標値を読み出して形状ＤＢへ書き出し（ステップＳ８２）、ステップＳ８３へ進む。ここで、処理中の頂点の頂点座標テーブルでの位置は、頂点座標参照フラグテーブルの先頭から処理中の頂点までの偽フラグの個数である。
以上、ステップ８０からＳ８２までを未処理の頂点座標参照フラグに対して処理を行う（ステップＳ８３）。
このステップＳ８０からＳ８３により、頂点座標伸張手段１１０を構成する。
【００３０】
次に、データ保持手段１３０中の法線ベクトル参照フラグテーブルの処理中の頂点のフラグが真である場合（ステップＳ８５のＹＥＳ）、処理中の頂点に対する法線ベクトルを保持する法線ベクトルテーブルでの位置を求め、その位置における法線ベクトル値を読み出し（ステップＳ８５）、ステップＳ８７へ進む。ここで、処理中の頂点に対する法線ベクトルを保持する法線ベクトルテーブルでの位置は、法線ベクトル参照フラグテーブルの先頭から処理中の頂点までの真フラグの個数である。
一方、処理中の頂点のフラグが偽の場合（ステップＳ８４のＮＯ）、処理中の頂点に対する法線ベクトルを保持する法線ベクトルインデックステーブルでの位置を求め、その位置の法線ベクトルインデックスが指す法線ベクトルテーブルにおける法線ベクトル値を読み出し（ステップＳ８６）、ステップＳ８７へ進む。ここで、処理中の頂点に対する法線ベクトルを保持する法線ベクトルインデックステーブルでの位置は、法線ベクトル参照フラグテーブルの先頭から処理中の頂点までの偽フラグの個数である。
読み出した法線ベクトルを処理中の頂点に対する法線ベクトルとして割り当てて、形状ＤＢへ書き出す（ステップＳ８７）。
未処理の平面フラグがない場合（ステップＳ８８のＮＯ）、処理を終了する。
一方、未処理の平面フラグがあって（ステップＳ８８のＹＥＳ）、処理中の頂点の平面フラグが真で且つ次の頂点の平面フラグも真の場合（ステップ８９のＹＥＳ）、同一平面上の他の頂点に読み出した法線ベクトルを割り当てるために、処理中の頂点を次に進めてステップＳ８７へ戻る。
しかし、処理中の頂点の平面フラグが偽または次の頂点の平面フラグが偽の場合（ステップ８９のＮＯ）、次の頂点に法線ベクトルを割り当てるために、処理中の頂点を次に進めてステップＳ８４へ戻る。
このステップＳ８４からＳ８９までにより、法線ベクトル伸張手段１２０を構成する。
以上のようにデータ圧縮装置およびデータ伸張装置を構成することによって、ｎ次元空間における三角形メッシュの圧縮および伸張を行なうことができる。
また、このデータ構造を使用すると、データサイズが減少し、ハードディスク等保存装置のスペース効率が向上する。
【００３１】
＜実施形態４＞
また、上述したデータ圧縮装置やデータ伸張装置を通信リンクで接続して、ｎ次元形状モデルを圧縮した形状データをデータ圧縮装置からデータ伸張装置へ転送するように構成してもよい。
ここで、通信リンクの例として、シリアルリンク（ＲＳ−２３２）、パラレルリンク、無線リンク、赤外線リンク、ネットワーク（ローカルエリアネットワーク、広域ネットワーク、イントラネット、インターネット）がある。
例えば、上述したデータ圧縮装置またはその機能を含むｎ次元形状処理装置と、データ伸張装置またはその機能を含むｎ次元形状処理装置を通信リンクで接続し、データ圧縮装置またはその機能を含むｎ次元形状処理装置で、ｎ次元形状モデルから図４、図１０または図１３に示したデータ構造の形状データを作成してデータ保持手段に格納し、その形状データを通信リンクによって送る。
データ伸張装置またはその機能を含むｎ次元形状処理装置では、受信した形状データを伸張して得たｎ次元形状モデルをディスプレイ等の表示装置へ表示したり、そのモデルを形状処理することができる（図１９参照）。
【００３２】
＜実施形態５＞
さらに、本発明は、上述した実施形態のみに限定されたものではなく、上述した実施形態の各装置の機能をそれぞれプログラム化し、あらかじめＣＤ−ＲＯＭ等の記録媒体に書き込んでおき、コンピュータに搭載したＣＤ−ＲＯＭドライブのような媒体駆動装置にこのＣＤ−ＲＯＭ等を装着して、これらのプログラムをインストールして、実行することによっても、本発明の目的が達成されることは言うまでもない。
この場合、記録媒体から読出されたプログラム自体が上述した実施形態を実現することになり、そのプログラムおよびそのプログラムを記録した記録媒体も本発明を構成することになる。
なお、記録媒体としては半導体媒体（例えば、ＲＯＭ、不揮発性メモリカード等）、光媒体（例えば、ＤＶＤ、ＭＯ、ＭＤ、ＣＤ−Ｒ等）、磁気媒体（例えば、磁気テープ、フレキシブルディスク等）のいずれであってもよい。
あるいは、インターネット等の通信網を介して記憶装置に格納されたプログラムをサーバコンピュータから直接供給を受けるようにしてもよい。この場合、このサーバコンピュータの記憶装置も本発明の記録媒体に含まれる。
また、ロードしたプログラムを実行することにより上述した実施形態が実現されるだけでなく、そのプログラムの指示に基づき、オペレーティングシステム等が実際の処理の一部または全部を行い、その処理によって上述した実施形態が実現される場合も含まれる。
また、上述したプログラムをサーバコンピュータの磁気ディスク等の記憶装置に格納しておき、インターネット等の通信網で接続された利用者のコンピュータから実行指示を受信して、当該プログラムを実行し、その結果を利用者のコンピュータへ返信するようなＡＳＰ（Application Service Provider）による利用を提供する場合、このサーバコンピュータの記憶装置およびそのプログラムも本発明に含まれる。
尚、本発明は上述した実施形態に限定されることなく、本発明の要旨を逸脱しない範囲内で各種の変形、修正が可能であるのは勿論である。
【図面の簡単な説明】
【００３３】
【図１】平面を構成する三角形メッシュと法線ベクトルを説明するための図である。
【図２】三角形メッシュの表現形式である三角形セット形式を説明するための図である。
【図３】三角形メッシュの表現形式である三角形ストリップ形式を説明するための図である。
【図４】列挙型三角形メッシュを用いた形状データのデータ構造を説明するための図である。
【図５】データ圧縮装置の機能構成を示すブロック図である。
【図６】図４のデータ構造を用いて形状モデルデータを圧縮する処理手順を示すフローチャートである。
【図７】データ伸張装置の機能構成を示すブロック図である。
【図８】図４のデータ構造を用いて圧縮された形状データを伸張する処理手順を示すフローチャートである。
【図９】図４のデータ構造を用いて表現した形状データ例を示す図である。
【図１０】インデックス型三角形メッシュを用いた形状データのデータ構造を説明するための図である。
【図１１】図１０のデータ構造を用いて形状モデルデータを圧縮する処理手順を示すフローチャートである。
【図１２】図１０のデータ構造を用いて圧縮された形状データを伸張する処理手順を示すフローチャートである。
【図１３】参照型三角形メッシュを用いた形状データのデータ構造を説明するための図である。
【図１４】図１３のデータ構造を用いて形状モデルデータを圧縮する処理手順を示すフローチャート（その１）である。
【図１５】図１３のデータ構造を用いて形状モデルデータを圧縮する処理手順を示すフローチャート（その２）である。
【図１６】図１３のデータ構造を用いて形状モデルデータを圧縮する処理手順を示すフローチャート（その３）である。
【図１７】図１３のデータ構造を用いて圧縮された形状データを伸張する処理手順を示すフローチャート（その１）である。
【図１８】図１３のデータ構造を用いて圧縮された形状データを伸張する処理手順を示すフローチャート（その２）である。
【図１９】本発明のデータ圧縮装置およびデータ伸張装置の機能を使ったｎ次元形状処理装置の使用例を説明するための図である。
【符号の説明】
【００３４】
１０…制御手段、２０…頂点座標圧縮手段、３０…法線ベクトル圧縮手段、４０…データ保持手段、１００…制御手段、１１０…頂点座標伸張手段、１２０…法線ベクトル伸張手段、１３０…データ保持手段。
【図１】
2005084780.tif 000003
【図２】
2005084780.tif 000004
【図３】
2005084780.tif 000005
【図４】
2005084780.tif 000006
【図５】
2005084780.tif 000007
【図６】
2005084780.tif 000008
【図７】
2005084780.tif 000009
【図８】
2005084780.tif 000010
【図９】
2005084780.tif 000011
【図１０】
2005084780.tif 000012
【図１１】
2005084780.tif 000013
【図１２】
2005084780.tif 000014
【図１３】
2005084780.tif 000015
【図１４】
2005084780.tif 000016
【図１５】
2005084780.tif 000017
【図１６】
2005084780.tif 000018
【図１７】
2005084780.tif 000019
【図１８】
2005084780.tif 000020
【図１９】
2005084780.tif 000021