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