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