(57)【要約】【課題】非対称な位相又は非一様な密度の三角形メッシュのデータを圧縮・伸長した際の法線ベクトルの誤差を小さくするデータ構造を提供する。【解決手段】三角形メッシュのデータ構造１は、頂点座標テーブル１０と法線ベクトルテーブル２０と曲面情報テーブル３０と頂点座標インデックステーブル４０と法線ベクトルインデックステーブル５０とから構成される。テーブル１０は三角形メッシュの頂点位置における座標の情報から、テーブル２０は三角形メッシュの頂点位置における法線ベクトルの情報から、テーブル３０は三角形メッシュ上の領域ごとの曲面情報（曲面が所定の曲面かを判定する情報を含む）からなり、テーブル４０は頂点座標のインデックスを、テーブル５０は法線ベクトルのインデックスを格納してなる。【選択図】　　　　図３
2004054736.tif 000002
【特許請求の範囲】
【請求項１】
ｎ次元空間の三角形メッシュを表す、三角形メッシュのデータ構造であって、三角形メッシュの頂点位置における座標を表す頂点座標テーブルと、三角形メッシュの頂点位置における法線ベクトルを表す法線ベクトルテーブルと、三角形メッシュ上の領域ごとの曲面情報を表す曲面情報テーブルと、頂点座標インデックス配列と、法線ベクトルインデックス配列と、を含んでなることを特徴とする三角形メッシュのデータ構造。
【請求項２】
前記頂点座標テーブル及び／又は法線ベクトルテーブルは、浮動小数点表現或いはベクトル量子化圧縮がなされていることを特徴とする請求項１記載の三角形メッシュのデータ構造。
【請求項３】
前記曲面情報テーブルは、三角形メッシュの領域の数と、該領域ごとの曲面のタイプを表す曲面タイプフラグ配列と、前記領域ごとに前記頂点座標インデックス配列のインデックスを格納した配列と、前記曲面のタイプが所定の複数種類のタイプである所定曲面を示す領域ごとの、曲面に対する三角形メッシュの向きを表す向きフラグ配列と、前記所定曲面を表す所定曲面配列と、を含んでなることを特徴とする請求項１又は２記載の三角形メッシュのデータ構造。
【請求項４】
前記所定曲面は、平面，球面，円柱面，円錐面とし、前記所定曲面配列は、平面を表す平面配列と、球面を表す球面配列と、円柱面を表す円柱面配列と、円錐面を表す円錐面配列とからなり、前記平面配列は原点座標と法線ベクトルを持ち、球面配列は中心座標と半径値を持ち、円柱面配列は中心座標と軸ベクトルと半径値とを持ち、円錐面配列は頂点座標と軸ベクトルと軸方向に１進んだ場所での半径値とを持つことを特徴とする請求項３記載の三角形メッシュのデータ構造。
【請求項５】
前記頂点座標インデックス配列及び法線ベクトルインデックス配列は、三角形インデックスセット形式、三角形インデックスストリップ形式、三角形インデックスファン４形式、のいずれかであることを特徴とする請求項１乃至４のいずれか１記載の三角形メッシュのデータ構造。
【請求項６】
三角形メッシュをコンピュータの記憶装置に保存するために用いられることを特徴とする請求項１乃至５のいずれか１記載の三角形メッシュのデータ構造。
【請求項７】
コンピュータから通信リンクを通して送信されることを特徴とする請求項１乃至６のいずれか１記載の三角形メッシュのデータ構造。
【請求項８】
コンピュータから通信リンクを通して受信されることを特徴とする請求項１乃至６のいずれか１記載の三角形メッシュのデータ構造。
【請求項９】
三角形メッシュのデータを圧縮する三角形メッシュデータ圧縮方法において、
三角形メッシュの頂点位置における座標の情報からなる頂点座標テーブルを保存し、
三角形メッシュの頂点位置における法線ベクトルの情報からなる法線ベクトルテーブルを保存し、
三角形メッシュ上の領域ごとの曲面タイプを保存し、
該曲面タイプが所定の複数種類のタイプである所定曲面を示す領域に対し、曲面に対する三角形メッシュの向きを表す向きフラグを保存し、
前記曲面タイプが前記所定曲面以外の曲面を示す領域に対し、三角形の頂点ごとの法線ベクトルインデックス配列を保存し、
三角形メッシュ上の領域ごとに分けて三角形を構成する頂点座標インデックス配列を保存し、
前記領域ごとに前記頂点座標インデックス配列の最終インデックスを保存することを特徴とする三角形メッシュデータ圧縮方法。
【請求項１０】
曲面上の点における法線ベクトルを計算するステップと、前記曲面上における法線ベクトルと三角形メッシュ上における法線ベクトルの内積を計算するステップと、該内積の結果により曲面情報に対する三角形メッシュの向きを判定するステップとを含む、曲面に対する三角形メッシュの向きの判定に基づいて、前記向きフラグを求めることを特徴とする請求項９記載の三角形メッシュデータ圧縮方法。
【請求項１１】
三角形メッシュのデータを伸長する三角形メッシュデータ伸長方法において、
三角形メッシュの頂点位置における座標の情報からなる頂点座標テーブルを読み込み、
三角形メッシュの頂点位置における法線ベクトルの情報からなる法線ベクトルテーブルを読み込み、
三角形メッシュ上の領域ごとの曲面タイプを読み込み、
該曲面タイプが所定の複数種類のタイプである所定曲面を示す領域に対し、三角形メッシュ上の領域ごとの曲面の情報と、該領域ごとに曲面に対する三角形メッシュの向きフラグを読み込み、
三角形メッシュ上の領域ごとに頂点座標インデックス配列の最終インデックスを読み込み、
前記領域ごとに分けて三角形を構成する頂点座標インデックスの配列を読み込み、
前記曲面タイプが所定曲面を示す領域に対し、前記曲面の情報、前記向きフラグ、前記頂点座標インデックス、頂点座標から法線ベクトルを計算し、
前記曲面タイプが前記所定曲面以外の曲面を示す領域に対し、三角形の頂点ごとの法線ベクトルインデックス配列を読み込むことを特徴とする三角形メッシュデータ伸長方法。
【請求項１２】
前記法線ベクトルの計算は、前記頂点座標インデックスを用いて前記頂点座標テーブルから頂点座標を取得するステップと、曲面上の点における法線ベクトルを計算するステップと、曲面に対する三角形メッシュの向きフラグが真ならば前記法線ベクトルの逆方向の法線ベクトルに修正するステップと、を含んでなること特徴とする請求項１１記載の三角形メッシュデータ伸長方法。
【請求項１３】
コンピュータに、請求項９又は請求項１０記載の三角形メッシュデータ圧縮方法を実行させるためのプログラム。
【請求項１４】
コンピュータに、請求項１１又は請求項１２記載の三角形メッシュデータ伸長方法を実行させるためのプログラム。
【請求項１５】
ｎ次元空間の三角形メッシュのデータを圧縮及び／又は伸長する１つ以上のコンピュータシステムであって、各コンピュータシステムは、プロセスを実行する中央処理装置と、記憶装置と、該記憶装置に格納された請求項１３記載のプログラムと、前記記憶装置に格納された請求項１４記載のプログラムと、前記記憶装置に格納された請求項１乃至６のいずれか１記載の三角形メッシュのデータ構造を持つ三角形メッシュデータと、を有することを特徴とするシステム。
【請求項１６】
２つ以上のコンピュータシステムが通信リンクで接続されていることを特徴とする請求項１５記載のシステム。
【請求項１７】
前記通信リンクは、インターネット、イントラネット、広域ネットワーク、ローカルエリアネットワーク、無線周波数リンク、赤外線リンク、シリアル通信リンクのいずれかを含むことを特徴とする請求項１６記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、三角形メッシュを表すデータ構造、三角形メッシュデータの圧縮方法及び伸長方法、プログラム、及び三角形メッシュデータ圧縮及び／又は伸長システムに関し、より詳細には、３次元形状モデル生成装置や３次元形状モデル表示装置等に利用可能な、法線ベクトル付の三角形メッシュを表すデータ構造、三角形メッシュデータの圧縮方法及び伸長方法、プログラム、及び三角形メッシュデータ圧縮及び／又は伸長システムに関する。本発明の応用分野としては、例えば形状計測装置や仮想現実感装置などが挙げられる。
【０００２】
【従来の技術】
自由曲面は、３次元形状モデルを表現する手段としてＣＡＤで広く利用されている。３次元形状モデルを表示するためには、自由曲面を三角形メッシュ形式のデータに変換する必要がある。この変換作業には時間がかかるため、予め三角形メッシュに変換したデータを自由曲面データとともに保持することが広く行われている。また、カタログや部品の配置が目的で、変形のできない３次元形状モデル専用ビューワも普及しはじめている。このため、自由曲面を三角形メッシュに変換した際のデータサイズを圧縮する技術の研究がさかんである。この技術の参考文献としては、例えば、「Ｔａｕｂｉｎ　Ｇ　ａｎｄ　Ｒｏｓｓｉｇｎａｃ　Ｊ：　Ｇｅｏｍｅｔｒｙ　ｃｏｍｐｒｅｓｓｉｏｎｔｈｒｏｕｇｈ　ｔｏｐｏｌｏｇｉｃａｌ　ｓｕｒｇｅｒｙ，　ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｇｒａｐｈｉｃｓ，　Ｖｏｌ．１７，　Ｎｏ．２，　１９９８．」が挙げられる。
【０００３】
一方、これらの手法により生成された三角形メッシュをレンダリング表示する際には、メッシュを構成する各三角形の頂点ごとの法線ベクトルデータが必要になる。フォンシェーディングなどのレンダリング表示のアルゴリズムでは、法線ベクトルも用いることによりリアリスティックな光沢のある質感の表現を可能にするからである。
【０００４】
なお、フォンシェーディングとは、三角形メッシュの頂点の法線ベクトルから、三角形内部の点の法線ベクトルを補間することにより求め、シェーディングを行う手法である。シェーディングとは、ライトの方向や強さ、物体表面の反射の性質、視線の方向などから、物体表面の明るさ（色）を計算する手法である。
【０００５】
図１６は三角形メッシュの例を示す図で、図１６（Ａ）は元の円柱面形状の例、図１６（Ｂ）はその三角形メッシュによる近似の例、図１６（Ｃ）は他の三角形メッシュとして非一様な三角形メッシュの例を、夫々示す図である。図１７は三角形メッシュの位相の違いを説明するための図で、図１７（Ａ）は中心の頂点に対して非対称な場合、図１７（Ｂ）は中心の頂点に対して対称な場合の例を示す図である。図１８は三角形メッシュの密度の違いを説明するための図で、図１８（Ａ）は非一様な場合（図１６（Ｃ））の断面、図１８（Ｂ）は一様な場合（１６（Ｂ））の断面の例を示す図である。
【０００６】
一般に自由曲面から生成した三角形メッシュの場合、頂点に隣接する三角形のベクトルの平均を計算することにより法線ベクトルを推定することができるので、法線ベクトルの保存を省略することによりデータサイズを小さくすることが可能である。
【０００７】
しかしながら、法線ベクトルを求めようとする頂点における三角形の配置により、誤差が生じてしまう場合がある。まず、図１６（Ａ）に示す円柱面の三角形メッシュ（図１６（Ｂ））を考えると、図１７（Ａ）に示すような非対称な三角形配置の場合には、法線ベクトルは面数の多い左下方向に傾いてしまう。
【０００８】
一方、図１７（Ｂ）のような対称的な三角形の配置の場合は、前述の問題は起きないが、図１６（Ｃ）のように非一様な三角形メッシュの場合は、図１８（Ａ）に示すように三角形の配置が対称的かどうかにかかわらず、法線ベクトルのずれの問題が発生する。
【０００９】
【発明が解決しようとする課題】
本発明は、上述のごとき実情に鑑みてなされたものであり、非対称な位相の三角形メッシュのデータを圧縮・伸長した際にも法線ベクトルに大きな誤差を生じず、且つ、非一様な密度の三角形メッシュのデータを圧縮・伸長した際にも法線ベクトルに大きな誤差を生じずに、自由曲面から生成した法線ベクトル付き三角形メッシュデータに圧縮，保存，転送，伸長等の処理を施すことが可能な、法線ベクトル付の三角形メッシュを表すデータ構造、三角形メッシュデータの圧縮方法及び伸長方法、プログラム、及び三角形メッシュデータ圧縮及び／又は伸長システムを提供することをその目的とする。
【００１０】
【課題を解決するための手段】
請求項１の発明は、ｎ次元空間の三角形メッシュを表す、三角形メッシュのデータ構造であって、三角形メッシュの頂点位置における座標を表す頂点座標テーブルと、三角形メッシュの頂点位置における法線ベクトルを表す法線ベクトルテーブルと、三角形メッシュ上の領域ごとの曲面情報を表す曲面情報テーブルと、頂点座標インデックス配列と、法線ベクトルインデックス配列と、を含んでなることを特徴としたものである。
【００１１】
請求項２の発明は、請求項１の発明において、前記頂点座標テーブル及び／又は法線ベクトルテーブルは、浮動小数点表現或いはベクトル量子化圧縮がなされていることを特徴としたものである。
【００１２】
請求項３の発明は、請求項１又は２の発明において、前記曲面情報テーブルは、三角形メッシュの領域の数と、該領域ごとの曲面のタイプを表す曲面タイプフラグ配列と、前記領域ごとに前記頂点座標インデックス配列のインデックスを格納した配列と、前記曲面のタイプが所定の複数種類のタイプである所定曲面を示す領域ごとの、曲面に対する三角形メッシュの向きを表す向きフラグ配列と、前記所定曲面を表す所定曲面配列と、を含んでなることを特徴としたものである。
【００１３】
請求項４の発明は、請求項３の発明において、前記所定曲面は、平面，球面，円柱面，円錐面とし、前記所定曲面配列は、平面を表す平面配列と、球面を表す球面配列と、円柱面を表す円柱面配列と、円錐面を表す円錐面配列とからなり、前記平面配列は原点座標と法線ベクトルを持ち、球面配列は中心座標と半径値を持ち、円柱面配列は中心座標と軸ベクトルと半径値とを持ち、円錐面配列は頂点座標と軸ベクトルと軸方向に１進んだ場所での半径値とを持つことを特徴としたものである。
【００１４】
請求項５の発明は、請求項１乃至４のいずれか１の発明において、前記頂点座標インデックス配列及び法線ベクトルインデックス配列は、三角形インデックスセット形式、三角形インデックスストリップ形式、三角形インデックスファン形式、のいずれかであることを特徴としたものである。
【００１５】
請求項６の発明は、請求項１乃至５のいずれか１の発明において、三角形メッシュをコンピュータの記憶装置に保存するために用いられることを特徴としたものである。
【００１６】
請求項７の発明は、請求項１乃至６のいずれか１の発明において、コンピュータから通信リンクを通して送信されることを特徴としたものである。
【００１７】
請求項８の発明は、請求項１乃至６のいずれか１の発明において、コンピュータから通信リンクを通して受信されることを特徴としたものである。
【００１８】
請求項９の発明は、三角形メッシュのデータを圧縮する三角形メッシュデータ圧縮方法において、
三角形メッシュの頂点位置における座標の情報からなる頂点座標テーブルを保存し、
三角形メッシュの頂点位置における法線ベクトルの情報からなる法線ベクトルテーブルを保存し、
三角形メッシュ上の領域ごとの曲面タイプを保存し、
該曲面タイプが所定の複数種類のタイプである所定曲面を示す領域に対し、曲面に対する三角形メッシュの向きを表す向きフラグを保存し、
前記曲面タイプが前記所定曲面以外の曲面を示す領域に対し、三角形の頂点ごとの法線ベクトルインデックス配列を保存し、
三角形メッシュ上の領域ごとに分けて三角形を構成する頂点座標インデックス配列を保存し、
前記領域ごとに前記頂点座標インデックス配列の最終インデックスを保存することを特徴としたものである。
【００１９】
請求項１０の発明は、請求項９の発明において、曲面上の点における法線ベクトルを計算するステップと、前記曲面上における法線ベクトルと三角形メッシュ上における法線ベクトルの内積を計算するステップと、該内積の結果により曲面情報に対する三角形メッシュの向きを判定するステップとを含む、曲面に対する三角形メッシュの向きの判定に基づいて、前記向きフラグを求めることを特徴としたものである。
【００２０】
請求項１１の発明は、三角形メッシュのデータを伸長する三角形メッシュデータ伸長方法において、
三角形メッシュの頂点位置における座標の情報からなる頂点座標テーブルを読み込み、
三角形メッシュの頂点位置における法線ベクトルの情報からなる法線ベクトルテーブルを読み込み、
三角形メッシュ上の領域ごとの曲面タイプを読み込み、
該曲面タイプが所定の複数種類のタイプである所定曲面を示す領域に対し、三角形メッシュ上の領域ごとの曲面の情報と、該領域ごとに曲面に対する三角形メッシュの向きフラグを読み込み、
三角形メッシュ上の領域ごとに頂点座標インデックス配列の最終インデックスを読み込み、
前記領域ごとに分けて三角形を構成する頂点座標インデックスの配列を読み込み、
前記曲面タイプが所定曲面を示す領域に対し、前記曲面の情報、前記向きフラグ、前記頂点座標インデックス、頂点座標から法線ベクトルを計算し、
前記曲面タイプが前記所定曲面以外の曲面を示す領域に対し、三角形の頂点ごとの法線ベクトルインデックス配列を読み込むことを特徴としたものである。
【００２１】
請求項１２の発明は、請求項１１の発明において、前記法線ベクトルの計算は、前記頂点座標インデックスを用いて前記頂点座標テーブルから頂点座標を取得するステップと、曲面上の点における法線ベクトルを計算するステップと、曲面に対する三角形メッシュの向きフラグが真ならば前記法線ベクトルの逆方向の法線ベクトルに修正するステップと、を含んでなること特徴としたものである。
【００２２】
請求項１３の発明は、コンピュータに、請求項９又は請求項１０記載の三角形メッシュデータ圧縮方法を実行させるためのプログラムである。
【００２３】
請求項１４の発明は、コンピュータに、請求項１１又は請求項１２記載の三角形メッシュデータ伸長方法を実行させるためのプログラムである。
【００２４】
請求項１５の発明は、ｎ次元空間の三角形メッシュのデータを圧縮及び／又は伸長する１つ以上のコンピュータシステムであって、各コンピュータシステムは、プロセスを実行する中央処理装置と、記憶装置と、該記憶装置に格納された請求項１３記載のプログラムと、前記記憶装置に格納された請求項１４記載のプログラムと、前記記憶装置に格納された記載の三角形メッシュのデータ構造を持つ三角形メッシュデータと、を有することを特徴としたものである。
【００２５】
請求項１６の発明は、請求項１５の発明において、２つ以上のコンピュータシステムが通信リンクで接続されていることを特徴としたものである。
【００２６】
請求項１７の発明は、請求項１６の発明において、前記通信リンクは、インターネット、イントラネット、広域ネットワーク、ローカルエリアネットワーク、無線周波数リンク、赤外線リンク、シリアル通信リンクのいずれかを含むことを特徴としたものである。
【００２７】
【発明の実施の形態】
以下の（イ），（ロ），（ハ），（ニ）の前提に基づき、本発明の構成・動作を説明する。
（イ）　本発明で扱う自由曲面はパラメトリック曲面と解析的曲面がある。
（ロ）　本発明で所定の曲面として扱う解析的曲面としては、平面，球面，円柱面，円錐面があり、夫々次のように定義されているものとする。すなわち、平面は原点座標［ｏｐｌ］及び法線ベクトル［ｎｐｌ］で、球面は中心座標［ｃｓｐ］及び半径値ｒｓｐで、円柱面は中心座標［ｃｃｙ］，軸ベクトル［ａｃｙ］，半径値ｒｃｙで、円錐面は頂点座標［ｑｃｏ］，軸ベクトル［ａｃｏ］，軸方向に１進んだ点における半径値ｒｃｏで定義されている。ただし、本明細書中、任意のＡのベクトル表示を［Ａ］とも表記する。図１に解析的曲面の例を示す。図１（Ａ）は平面、図１（Ｂ）は球面、図１（Ｃ）は円柱面、図１（Ｄ）は円錐面、の一例である。
【００２８】
（ハ）　本発明で扱うパラメトリック曲面上の点はパラメータｕ，ｖにより次のように表す。
［Ｓ（ｕ，ｖ）］　　（０≦ｕ，ｖ≦１）
【００２９】
代表的なパラメトリック曲面であるＢｅｚｉｅｒ曲面を紹介しておく。ｎ×ｍ次のＢｅｚｉｅｒ曲面［Ｓ（ｕ，ｖ）］は、（ｎ＋１）×（ｍ＋１）個の制御点［Ｐｉｊ］により構成され、曲面上の点は次式で表される。なお、Ｂｉｎ（ｕ），Ｂｊｍ（ｖ）は、Ｂｅｒｎｓｔｅｉｎ基底関数と呼ばれる関数である。
【００３０】
【式１】
2004054736.tif 000003
【００３１】
図２にＢｅｚｉｅｒ曲面の一例として双３次のＢｅｚｉｅｒ曲面を示す。双３次のＢｅｚｉｅｒ曲面は、図２に示すように１６個の制御点［Ｐｉｊ］（ｉ＝０，１，２，３；ｊ＝０，１，２，３）で表現される。
【００３２】
（ニ）　本発明で扱う三角形メッシュの表現形式には、三角形インデックスセット形式，三角形インデックスストリップ形式，三角形インデックスファン形式があり、夫々、参考文献「三浦憲二郎：ＯｐｅｎＧＬ　３Ｄ　グラフィックス入門，朝倉書店，１９９５．」の１９頁にある、ＧＬ＿ＴＲＩＡＮＧＬＥＳ，ＧＬ＿ＴＲＩＡＮＧＬＥ＿ＳＴＲＩＰ，ＧＬ＿ＴＲＩＡＮＧＬＥ＿ＦＡＮの各プリミティブに対応している。これらのインデックス付きの形式は、別途座標テーブルを配列形式で保持し、配列のインデックスを指定することで座標を表している形式である。
【００３３】
図３は、本発明の一実施形態に係る、ｎ次元空間の三角形メッシュのデータ構造を説明するための図である。
本発明の一実施形態に係る、ｎ次元空間の三角形メッシュのデータ構造１は、頂点座標テーブル１０と、法線ベクトルテーブル２０と、曲面情報テーブル３０と、頂点座標インデックス配列（ここでは頂点座標インデックステーブル４０として図示）と、法線ベクトルインデックス配列（ここでは法線ベクトルインデックステーブル５０として図示）とから構成される。頂点座標テーブル１０は、三角形メッシュの頂点位置における座標の情報からなる。法線ベクトルテーブル２０は、三角形メッシュの頂点位置における法線ベクトルの情報からなる。曲面情報テーブル３０は、三角形メッシュ上の領域ごとの曲面情報からなる。頂点座標インデックステーブル（ＶＩＴ）４０は頂点座標のインデックスを格納してなり、法線ベクトルインデックステーブル５０は法線ベクトルのインデックスを格納してなる。
【００３４】
図４は、図３の三角形メッシュのデータ構造における頂点座標テーブルのデータ構造を説明するための図である。
図４で例示する頂点座標テーブル１０には、頂点座標の数（＝ｎ）１１と、頂点座標１から頂点座標ｎ−１までのｘ成分，ｙ成分，ｚ成分１２０，１２１，．．．，１２ｎ−１が、頂点座標０（ｘ），頂点座標０（ｙ），頂点座標０（ｚ），頂点座標１（ｘ），頂点座標１（ｙ），頂点座標１（ｚ），．．．，頂点座標ｎ−１（ｘ），頂点座標ｎ−１（ｙ），頂点座標ｎ−１（ｚ）の順に格納されている。各成分は、浮動小数点表現がなされているか、或いはベクトル量子化圧縮が行われている。
【００３５】
図５は、図３の三角形メッシュのデータ構造における法線ベクトルテーブルのデータ構造を説明するための図である。
図５で例示する法線ベクトルテーブル２０には、法線ベクトルの数（＝ｍ）２１と、法線ベクトル１から法線ベクトルｍ−１までのｘ成分，ｙ成分，ｚ成分２２０，２２１，．．．，２２ｍ−１が順に格納されている。各成分は、浮動小数点表現がなされているか、或いはベクトル量子化圧縮が行われている。
【００３６】
図６は、図３の三角形メッシュのデータ構造における曲面情報テーブルのデータ構造を説明するための図である。
図６で例示する曲面情報テーブル３０には、三角形メッシュの領域数（＝ｎａ）３１と、曲面タイプ０から曲面タイプｎａ−１までの曲面タイプフラグ配列３２と、曲面の向き０から曲面の向きｎｓｆ−１までの向きフラグ配列３３と、ＶＩＴインデックス０からＶＩＴインデックスｎａ−１までの頂点座標インデックス配列（ＶＩＴ）のインデックス配列３４と、平面０から平面ｎｐｌ−１までの平面配列３５と、球面０から球面ｎｓｐ−１までの球面配列３６と、円柱面０から円柱面ｎｃｙ−１までの円柱面配列３７と、円錐面０から円錐面ｎｃｏ−１までの円錐面配列３８とが順に格納されている。
【００３７】
曲面タイプフラグ配列３２（要素数＝ｎａ）は、三角形メッシュの領域ごとの曲面タイプを示すフラグの配列である。曲面タイプとしては、平面，球面，円柱面，円錐面，その他曲面を表す５種類の整数値のいずれかとする。向きフラグ配列３３（要素数＝ｎｓｆ）は、曲面タイプがその他曲面以外（すなわち平面，球面，円柱面，円錐面のいずれか）である領域に対し、領域ごとの曲面情報に対する三角形メッシュの向きを示すフラグの配列である。曲面（曲面情報）に対する三角形メッシュの向きフラグは、メッシュの向きと曲面の向きが一致するか否かを表した論理値を表す整数である。ＶＩＴインデックス配列３４（要素数＝ｎａ）は、頂点座標インデックス配列のインデックスを領域ごとに格納した配列である。また、平面配列の要素数をｎｐｌ、球面配列の要素数をｎｓｐ、円柱面配列の要素数をｎｃｙ、円錐面配列の要素数をｎｃｏとしている。なお、ｎｓｆ＝ｎｐｌ＋ｎｓｐ＋ｎｃｙ＋ｎｃｏとなる。
【００３８】
図７は、図６の曲面情報テーブルのデータ構造における、平面配列，球面配列，円柱面配列，円錐面配列の各データ構造を説明するための図である。
平面を表す平面配列３５は、原点座標のｘ，ｙ，ｚ成分と法線ベクトルのｘ，ｙ，ｚ成分から構成される。球面配列３６は、中心座標のｘ，ｙ，ｚ成分と半径値から構成される。円柱面配列３７は、中心座標のｘ，ｙ，ｚ成分、軸ベクトルのｘ，ｙ，ｚ成分、半径値から構成される。円錐面配列３８は、頂点座標のｘ，ｙ，ｚ成分、軸ベクトルのｘ，ｙ，ｚ成分、軸ベクトル方向に１進んだ場所での半径値から構成される。各値は、全て浮動小数点形式で格納される。
【００３９】
図８は、図３の三角形メッシュのデータ構造における頂点座標インデックステーブルのデータ構造を説明するための図である。
頂点座標インデックステーブル（ＶＩＴ）４０には、頂点座標インデックスの数４１（＝ｎｖ）と、頂点座標インデックス０から頂点座標インデックスｎｖ−１までの頂点座標インデックス４２０〜４２ｎｖ−１が整数値で格納されている。ＶＩＴ４０では、三角形メッシュの各三角形を、三角形インデックスセット形式，三角形インデックスストリップ形式，三角形インデックスファン形式のいずれかの形式で表している。三角形インデックスセット形式の場合は、各三角形の頂点を表す、頂点座標テーブル１０の頂点座標配列へのインデックスが格納されている。三角形インデックスストリップ形式又は三角形インデックスファン形式の場合は、三角形の頂点を表すインデックス（頂点座標テーブル１０の頂点座標配列へのインデックス＋１）、或いはストリップ，ファンの最後を表すデリミタ（＝０）が格納されている。三角形はメッシュ上の領域ごとにまとまって格納されている。
【００４０】
図９は、図３の三角形メッシュのデータ構造における法線ベクトルインデックステーブルのデータ構造を説明するための図である。
法線ベクトルインデックステーブル５０には、法線ベクトルインデックス数５１（＝ｎｎ）と、法線ベクトルインデックス０から法線ベクトルインデックスｎｎ−１までの法線ベクトルインデックス５２０〜５２ｎｎ−１が整数値で格納されている。法線ベクトルインデックステーブル５０では、三角形メッシュの各三角形を、三角形インデックスセット形式，三角形インデックスストリップ形式，三角形インデックスファン形式のいずれかの形式で表している。三角形インデックスセット形式の場合は、各三角形の法線ベクトルを表す、法線ベクトルテーブル２０の法線ベクトル配列へのインデックスが格納されている。三角形インデックスストリップ形式又は三角形インデックスファン形式の場合は、三角形の法線ベクトルを表すインデックス（法線ベクトルテーブル２０の法線ベクトル配列へのインデックス＋１）、或いはストリップ，ファンの最後を表すデリミタ（＝０）が格納されている。三角形はメッシュ上の領域ごとにまとまって格納されているが、その他曲面の曲面情報を持つ領域についてのみ法線ベクトルインデックスを格納し、その他曲面以外（すなわち平面，球面，円柱面，円錐面のいずれか）の曲面情報を持つ領域については法線ベクトルインデックスは格納しない。
【００４１】
上述した三角形メッシュのデータ構造を用いることで、法線ベクトルを含んだ三角形メッシュデータの圧縮，伸長が可能となる。図３乃至図９を再度参照し、以下に三角形メッシュデータの圧縮，伸長方法を説明する。
【００４２】
図１０は、本発明の一実施形態に係る、法線ベクトルを含んだ三角形メッシュデータの圧縮方法を説明するためのフロー図である。
まず、三角形メッシュの頂点位置における座標からなる頂点座標テーブルを図４（頂点座標テーブル１０）の形式に保存する（ステップＳ１）。次いで、三角形メッシュの頂点位置における法線ベクトルからなる法線ベクトルテーブルを図５（法線ベクトルテーブル２０）の形式に保存する（ステップＳ２）。次いで、三角形メッシュ上の領域ごとの曲面タイプ（曲面タイプ＝平面，球面，円柱面，円錐面，その他曲面のいずれか）を、図６の曲面タイプ０から曲面タイプｎａ−１（曲面タイプフラグ配列３２）の形式に保存する（ステップＳ３）。
【００４３】
次いで、所定の曲面タイプ（平面，球面，円柱面，円錐面のいずれか）を持つかを判定し（ステップＳ４）、所定の曲面タイプを持つ領域に対し、すなわち領域が所定の曲面情報を持つ場合、それらの領域ごとに曲面情報を図７の形式で平面配列３５，球面配列３６，円柱面配列３７，円錐面配列３８のいずれかに保存し（ステップＳ５）、さらにそれらの領域ごとに曲面に対する三角形メッシュの向きフラグを図６の曲面の向き（曲面の向きフラグ配列３３）の形式で保存する（ステップＳ６）。一方、領域が所定の曲面情報を持たない場合（曲面タイプ＝その他曲面）、それらの領域ごとに三角形の法線ベクトルインデックス配列を図９（法線ベクトルインデックス配列５０）の形式で保存する（ステップＳ７）。
【００４４】
次いで、三角形メッシュの全ての領域に対し、領域ごとに、三角形を構成する頂点座標インデックス配列を図８（ＶＩＴ４０）の形式で保存する（ステップＳ８）。次いで、それらの領域ごとに三角形を構成する頂点座標インデックス配列の最終インデックスを図６におけるＶＩＴインデックス（ＶＩＴインデックス配列３４）の形式で保存する（ステップＳ９）。
以上により、法線ベクトルを含んだ三角形メッシュを圧縮することができる。
【００４５】
図１１は、本発明の一実施形態に係る、曲面情報に対する三角形メッシュの向きの判定方法を説明するためのフロー図である。
図１０のステップＳ６において曲面の向きを判定する必要があるが、そのためには、まず、曲面上の点［ｐ］における法線ベクトル［ｎ（［ｐ］）］を計算する（ステップＳ１１）。ここでの計算方法は、曲面のタイプごとに異なり、次の計算式に基づいて計算する。
【００４６】
【式２】
2004054736.tif 000004
【００４７】
ここで、×はベクトルの外積ベクトル計算を表している。ここで求まるベクトルは正規化されていないので、最後にベクトルの正規化計算を行う（下式参照）。
【００４８】
【式３】
2004054736.tif 000005
【００４９】
次いで、三角形メッシュの一頂点について、その曲面上における法線ベクトルと三角形メッシュ上における法線ベクトルの内積を計算する（ステップＳ１２）。次いで、この内積の結果により曲面情報に対する三角形メッシュの向きを判定する（ステップＳ１３）。内積結果が正以上ならば同じ向きで、そうでなければ反対の向きと判定する。
以上により、曲面情報に対する三角形メッシュの向きの判定することができる。
【００５０】
図１２は、本発明の一実施形態に係る、法線ベクトルを含んだ三角形メッシュデータの伸長方法を説明するためのフロー図である。
まず、図４の形式の頂点座標テーブル１０を読み込む（ステップＳ２１）。次いで、図５の形式の法線ベクトルテーブル２０を読み込む（ステップＳ２２）。次いで、図６における曲面タイプフラグ配列３２から三角形メッシュ上の領域ごとの曲面タイプを読み込む（ステップＳ２３）。
【００５１】
次いで、所定の曲面タイプ（平面，球面，円柱面，円錐面のいずれか）を持つかを判定し（ステップＳ２４）、所定の曲面タイプを持つ領域に対し、すなわち領域が所定の曲面情報を持つ場合、図７の各形式でそれらの領域ごとに三角形メッシュ上の曲面情報を読み込み（ステップＳ２５）、図６の向きフラグ配列３３の形式でそれらの領域ごとに曲面情報に対する三角形メッシュの向きフラグを読み込む（ステップＳ２６）。一方、領域が所定の曲面情報を持たない場合には、ステップＳ２５，Ｓ２６の処理は実行しない。
【００５２】
次いで、図６におけるＶＩＴインデックス配列３４から、三角形を構成する頂点座標インデックス配列の最終インデックスを領域ごとに読み込み（ステップＳ２７）、図８の形式のＶＩＴ４０において、それらの領域ごとに分けて、三角形を構成する頂点座標インデックス配列を読み込む（ステップＳ２８）。
【００５３】
次いで、所定の曲面タイプ（平面，球面，円柱面，円錐面のいずれか）を持つかを判定し（ステップＳ２９）、或いはステップＳ２４での判定結果に基づいて、領域が所定の曲面情報を持つ場合には、曲面情報，向きフラグ，頂点座標インデックス，頂点座標配列から法線ベクトルを計算する（ステップＳ３０）。一方、領域が所定の曲面情報を持たない場合、三角形の頂点ごとの法線ベクトルインデックス配列を読み込む（ステップＳ３１）。
以上により、法線ベクトルを含んだ三角形メッシュを伸長することができる。
【００５４】
図１３は、本発明の一実施形態に係る、法線ベクトルの計算方法を説明するためのフロー図である。
図１２のステップＳ３０において法線ベクトルを計算する必要があるが、そのためには、まず、ＶＩＴ４０の頂点座標インデックスを用いて頂点座標テーブル１０から頂点座標を取得する（ステップＳ４１）。次いで、その頂点座標を曲面上の点として、曲面上の点における法線ベクトルを計算する（ステップＳ４２）。ここでの計算は、図１１のステップＳ１１と同じ方法で行う。曲面情報に対する三角形メッシュの向きフラグが違う向きを示しているならば、その法線ベクトルの逆方向の法線ベクトルに修正する（ステップＳ４３）。
以上により、法線ベクトルが計算できる。
【００５５】
本発明は、上述した法線ベクトル付三角形メッシュデータの圧縮及び／又は伸長方法や、法線ベクトルの計算方法、三角形メッシュの向きの判定方法を、コンピュータに実行させるためのプログラムとしての形態も、そのプログラム又はプログラム及びデータを記憶した記録媒体としての形態も採り得る。記録媒体としては、具体的には、ＣＤ−ＲＯＭ，光磁気ディスク，ＤＶＤ−ＲＯＭ，ＦＤ，フラッシュメモリ，メモリスティック及びその他各種ＲＯＭやＲＡＭ等が想定でき、これら記録媒体にプログラム又はプログラム及びデータを記録し流通させることにより、法線ベクトル付三角形メッシュの圧縮及び／又は伸長の機能の実現を容易にする。そしてコンピュータ等の情報処理装置に記録媒体を装着してそのプログラムを読み出すか、若しくは情報処理装置が備えている記録媒体に当プログラムを記憶させておき、必要に応じて読み出すことにより、本発明に関わる機能を実行することができる。
【００５６】
図１４は、法線ベクトルを含んだ三角形メッシュデータを圧縮し伸長する１つ以上のコンピュータシステムの構成例を示す図である。
図１４で例示する、情報処理装置としての各コンピュータシステムは、プロセスを実行するＣＰＵ７２等の中央処理装置と、ＲＡＭ７１，データ記憶装置（データ保存装置）７５等のメモリと、そのメモリに格納された（存在する）アプリケーションプログラム６１及び圧縮データ構造とを備える。さらに、各コンピュータシステムは、Ｉ／Ｏインタフェース７３を介して各種端末機器（キーボード，マウス，ディスプレイ等）７４により入出力され、プリンタ７６へも出力可能な構成になっている。
【００５７】
アプリケーションプログラム６１としては、本発明に係る圧縮プログラム６２及び／又は伸長プログラム６３を備え、それらがマイクロ命令コード６７に基づくオペレーティングシステム（ＯＳ）６６上で、コンパイラ６４及びオプティマイザ６５により実行可能となっている。
【００５８】
図１５は、図１４に示した２つ以上のコンピュータシステムが通信リンクで接続された圧縮伸長システムの構成例を示す図である。
図１５で例示する圧縮伸長システムは、本発明に係る圧縮のアルゴリズム８２を備えた図１４のごときコンピュータ８１と、本発明に係る伸長のアルゴリズム８５を備えた図１４のごときコンピュータ８４とが、通信リンクにより接続されている。ここでの通信リンクとしては、例えばインターネット，イントラネット，広域ネットワーク，ローカルエリアネットワーク，無線周波数リンク，赤外線リンク，シリアル通信リンクのいずれかを含めばよい。圧縮アルゴリズム８２により圧縮された法線ベクトル付三角形メッシュデータ（圧縮モデル８３）が、通信リンクを介してコンピュータ８１で送信され、コンピュータ８４で受信され、伸長アルゴリズム８５により伸長されて表示等が可能となる。
【００５９】
【発明の効果】
本発明によれば、非対称な位相の三角形メッシュのデータを圧縮・伸長した際の法線ベクトルの誤差を小さくすることができる。本発明によれば、さらに非一様な密度の三角形メッシュのデータを圧縮・伸長した際にも、法線ベクトルの誤差を小さくすることができる。本発明を３次元ＣＡＤシステムなどに実現することによって、コンパクトな３次元データを実現することができる。
【図面の簡単な説明】
【図１】解析的曲面の例を示す図である。
【図２】Ｂｅｚｉｅｒ曲面の一例を示す図である。
【図３】本発明の一実施形態に係る、ｎ次元空間の三角形メッシュのデータ構造を説明するための図である。
【図４】図３の三角形メッシュのデータ構造における頂点座標テーブルのデータ構造を説明するための図である。
【図５】図３の三角形メッシュのデータ構造における法線ベクトルテーブルのデータ構造を説明するための図である。
【図６】図３の三角形メッシュのデータ構造における曲面情報テーブルのデータ構造を説明するための図である。
【図７】図６の曲面情報テーブルのデータ構造における、平面配列，球面配列，円柱面配列，円錐面配列の各データ構造を説明するための図である。
【図８】図３の三角形メッシュのデータ構造における頂点座標インデックステーブルのデータ構造を説明するための図である。
【図９】図３の三角形メッシュのデータ構造における法線ベクトルインデックステーブルのデータ構造を説明するための図である。
【図１０】本発明の一実施形態に係る、法線ベクトルを含んだ三角形メッシュデータの圧縮方法を説明するためのフロー図である。
【図１１】本発明の一実施形態に係る、曲面情報に対する三角形メッシュの向きの判定方法を説明するためのフロー図である。
【図１２】本発明の一実施形態に係る、法線ベクトルを含んだ三角形メッシュデータの伸長方法を説明するためのフロー図である。
【図１３】本発明の一実施形態に係る、法線ベクトルの計算方法を説明するためのフロー図である。
【図１４】法線ベクトルを含んだ三角形メッシュデータを圧縮し伸長する１つ以上のコンピュータシステムの構成例を示す図である。
【図１５】図１４に示した２つ以上のコンピュータシステムが通信リンクで接続された圧縮伸長システムの構成例を示す図である。
【図１６】三角形メッシュの例を示す図である。
【図１７】三角形メッシュの位相の違いを説明するための図である。
【図１８】三角形メッシュの密度の違いを説明するための図である。
【符号の説明】
１…三角形メッシュのデータ構造、１０…頂点座標テーブル、１１…頂点座標の数、１２０，１２１，１２ｎ−１…頂点座標の各成分、２０…法線ベクトルテーブル、２１…法線ベクトルの数、２２０，２２１，２２ｍ−１…法線ベクトルの各成分、３０…曲面情報テーブル、３１…三角形メッシュの領域数、３２…曲面タイプフラグ配列、３３…向きフラグ配列、３４…ＶＩＴのインデックス配列、３５…平面配列、３６…球面配列、３７…円柱面配列、３８…円錐面配列、４０…頂点座標インデックステーブル、４１…頂点座標インデックス数、４２０，４２１，４２ｎｖ−１…頂点座標インデックス、５０…法線ベクトルインデックステーブル、５１…法線ベクトルインデックスの数、５２０，５２１，５２ｎｎ−１…法線ベクトルインデックス、６１…アプリケーションプログラム、６２…圧縮プログラム、６３…伸長プログラム、６４…コンパイラ、６５…オプティマイザ、６６…オペレーティングシステム、６７…マイクロ命令コード、７１…ＲＡＭ、７２…ＣＰＵ、７３…Ｉ／Ｏインタフェース、７４…端末機器、７５…データ記憶装置、７６…プリンタ、８１，８４…コンピュータ、８２…圧縮のアルゴリズム、８３…圧縮モデル。
【図１】
2004054736.tif 000006
【図２】
2004054736.tif 000007
【図３】
2004054736.tif 000008
【図４】
2004054736.tif 000009
【図５】
2004054736.tif 000010
【図６】
2004054736.tif 000011
【図７】
2004054736.tif 000012
【図８】
2004054736.tif 000013
【図９】
2004054736.tif 000014
【図１０】
2004054736.tif 000015
【図１１】
2004054736.tif 000016
【図１２】
2004054736.tif 000017
【図１３】
2004054736.tif 000018
【図１４】
2004054736.tif 000019
【図１５】
2004054736.tif 000020
【図１６】
2004054736.tif 000021
【図１７】
2004054736.tif 000022
【図１８】
2004054736.tif 000023