(57)【特許請求の範囲】
【請求項１】
３次元形状データと属性データとからなる３次元形状データベースを有する３次元形状処理装置において、圧縮対象となる３次元形状データ値と属性データ値とを前記３次元形状データベースから取得し、前記３次元形状データ値と前記属性データ値とを記憶領域に記憶し、前記３次元形状データ値と前記属性データ値の精度の範囲内で同じ値であれば、精度の高い値を残してその他は前記記憶領域から削除してデータの共有化をはかる共有化手段と、前記精度を実現するために必要な最小の記憶容量を前記記憶領域のデータ値ごとに計算し、そのデータ値を前記記憶容量に格納できる数値へ変換して置き換え、前記記憶領域を再構成するデータ値変換手段と、前記記憶領域のデータ値を先頭から順に読み込んで得られる数列を、前記数列の規則性により予め定められた複数のパターンに分類し、前記分類された数列に対応する前記記憶領域のデータ値をその該当するパターンについて予め定められた圧縮方法により圧縮するパターン解析手段とを備えたことを特徴とする３次元形状処理装置。
【請求項２】
請求項１に記載の３次元形状処理装置において、前記パターン解析手段は、前記数列の規則性が同じ値が連続して繰り返される場合には、前記規則性を持つ数列に対してランレングス圧縮を行うことを特徴とする３次元形状処理装置。
【請求項３】
請求項１に記載の３次元形状処理装置において、前記パターン解析手段は、前記数列の規則性が周期を持った数列である場合には、前記規則性を持つ数列に対してランレングス圧縮を行うことを特徴とする３次元形状処理装置。
【請求項４】
請求項１に記載の３次元形状処理装置において、前記パターン解析手段は、前記数列の規則性が一定の差分値で変化する場合には、前記規則性を持つ数列に対してランレングス圧縮を行うことを特徴とする３次元形状処理装置。
【請求項５】
請求項１に記載の３次元形状処理装置において、前記パターン解析手段は、前記数列の規則性が一定の変化率で変化する場合には、前記規則性を持つ数列に対してランレングス圧縮を行うことを特徴とする３次元形状処理装置。
【請求項６】
請求項１に記載の３次元形状処理装置において、前記パターン解析手段は、前記数列の規則性が１つおきに一定の差分値で変化する場合には、前記規則性を持つ数列に対してランレングス圧縮を行うことを特徴とする３次元形状処理装置。
【請求項７】
請求項１に記載の３次元形状処理装置において、前記パターン解析手段は、前記数列に規則性がない場合には、前記規則性のない数列自身とし、圧縮を行わないようにしたことを特徴とする３次元形状処理装置。
【請求項８】
請求項２乃至７のいずれか１に記載の３次元形状処理装置において、前記データ値変換手段は、前記精度を実現するために必要な最小の記憶容量のビット数が奇数の場合には、１ビット追加して偶数のビット数に変更することを特徴とする３次元形状処理装置。
【請求項９】
３次元形状データと属性データとからなる３次元形状データベースを有する３次元形状処理装置の３次元形状処理方法において、共有化手段が、圧縮対象となる３次元形状データ値と属性データ値とを前記３次元形状データベースから取得し、前記３次元形状データ値と前記属性データ値とを記憶領域に記憶し、前記３次元形状データ値と前記属性データ値の精度の範囲内で同じ値であれば、精度の高い値を残してその他は前記記憶領域から削除してデータの共有化をはかるステップと、データ値変換手段が、前記精度を実現するために必要な最小の記憶容量を、前記共有化手段が記憶領域に記憶したデータ値ごとに計算し、そのデータ値を前記記憶容量に格納できる数値へ変換して置き換え、前記記憶領域を再構成するステップと、パターン解析手段が、前記データ値変換手段が再構成した前記記憶領域のデータ値を先頭から順に読み込んで得られる数列を、前記数列の規則性により予め定められた複数のパターンに分類し、前記分類された数列に対応する前記記憶領域のデータ値をその該当するパターンについて予め定められた圧縮方法により圧縮するステップとを備えることを特徴とする３次元形状処理方法。
【請求項１０】
コンピュータを、請求項１乃至８のいずれか１に記載の３次元形状処理装置の各手段として機能させるためのプログラム。
【請求項１１】
請求項１０に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、３次元形状処理装置、３次元形状処理方法、プログラムおよび記録媒体に関し、具体的には、３次元ＣＡＤ／ＣＡＭ／ＣＡＥ／ＣＧシステムなど３次元形状データとそれを補助する属性データを合わせたデータについてデータ量を削減する技術に関する。
【０００２】
【従来の技術】
３次元ＣＡＤ／ＣＡＭシステムなど３次元形状処理システムの普及により３次元形状データの利用者層が拡大しており、ネットワーク環境において快適な操作性を得るために、高速なデータ転送などを求めるニーズが高まっている。
その実現のために、３次元形状データおよびその属性データなどのデータ量を削減する必要性がある。
【０００３】
そのため、例えば、３次元形状を複数の多角形で近似表現する多角形パッチ手法の一つで、３次元形状を３角形メッシュで近似表現する３角形メッシュモデルでは、隣接する３角形が稜線を共有して複数の３角形が連なる形状の連続領域（３角形ストリップ）、または、隣接する３角形が稜線を共有するとともにその隣接３角形を含む複数の３角形が同一の頂点を共有しながら連なる扇状の連続領域（３角形ファン）を形成することに着目し、１個の３角形を３個の頂点の組で定義する際、３角形メッシュを３角形ストリップの集合（３角形ストリップセット）と３角形ファンの集合（３角形ファンセット）との組み合わせとして表現することにより、共有される頂点データの重複をやめてデータ量を削減している。
【０００４】
また、３次元形状を多角形パッチやパラメトリック曲面で近似する場合、頂点または特徴点の数を減らすことにより３次元形状データを削減することができるが、その場合、曲面の滑らかさが失われたり、近似誤差が大きくなるという問題がある。
【０００５】
そこで、特開平７−１９２１４６号公報の「形状データ圧縮方法および形状データ伸長方法」では、形状データの各座標値の分布範囲を狭めた後、部品データ量が多く、階層化されていない場合、頂点の分布範囲を分割、階層部品化し、各部品について、部品圧縮処理を再帰的に実行後、各部品のデータについて共有部分を探し、共有化する。さらに、この部品階層における部品の逆量子化座標変換パラメータの分布を調べ、量子化によってデータ量を削減できる逆量子化座標変換パラメータを量子化し、データを圧縮する。
【０００６】
【発明が解決しようとする課題】
しかしながら、上述した従来の技術においては、言及しているのは３次元形状データの圧縮方法のみで、実際にアプリケーションに組み込む際に必要な属性データを含む圧縮方法については言及していない。
この問題点に関して、本出願人の出願した特願２００１−３０５５２５号の「３次元形状処理装置および属性データ付き３次元形状データの圧縮方法」は、３次元形状データを補助する属性データも含めて効率的に圧縮し、データ量を小さくしている。
しかし、共有化された幾何情報単体を効率的に圧縮するものではない。
【０００７】
本発明は、上述した実情を考慮してなされたものであって、３次元形状データと属性データを共有化した幾何情報を無駄なく効率的に圧縮できる３次元形状処理システムにおけるデータ圧縮装置、そのデータ圧縮方法、３次元形状処理システムにおけるデータ圧縮装置の機能を実行するためのプログラムおよびそのプログラムを記録したコンピュータ読み取り可能な記録媒体を提供することを目的とする。
【０００８】
【課題を解決するための手段】
上記の課題を解決するために、本発明の請求項１の３次元形状処理装置は、３次元形状データと属性データとからなる３次元形状データベースを有する３次元形状処理装置において、圧縮対象となる３次元形状データ値と属性データ値とを前記３次元形状データベースから取得し、前記３次元形状データ値と前記属性データ値とを記憶領域に記憶し、前記３次元形状データ値と前記属性データ値の精度の範囲内で同じ値であれば、精度の高い値を残してその他は前記記憶領域から削除してデータの共有化をはかる共有化手段と、前記精度を実現するために必要な最小の記憶容量を前記記憶領域のデータ値ごとに計算し、そのデータ値を前記記憶容量に格納できる数値へ変換して置き換え、前記記憶領域を再構成するデータ値変換手段と、前記記憶領域のデータ値を先頭から順に読み込んで得られる数列を、前記数列の規則性により予め定められた複数のパターンに分類し、前記分類された数列に対応する前記記憶領域のデータ値をその該当するパターンについて予め定められた圧縮方法により圧縮するパターン解析手段とを備えたことを特徴とする。
【０００９】
また、本発明の請求項２は、請求項１に記載の３次元形状処理装置において、前記パターン解析手段は、前記数列の規則性が同じ値が連続して繰り返される場合には、前記規則性を持つ数列に対してランレングス圧縮を行うことを特徴とする。
また、本発明の請求項３は、請求項１に記載の３次元形状処理装置において、前記パターン解析手段は、前記数列の規則性が周期を持った数列である場合には、前記規則性を持つ数列に対してランレングス圧縮を行うことを特徴とする。
また、本発明の請求項４は、請求項１に記載の３次元形状処理装置において、前記パターン解析手段は、前記数列の規則性が一定の差分値で変化する場合には、前記規則性を持つ数列に対してランレングス圧縮を行うことを特徴とする。
【００１０】
また、本発明の請求項５は、請求項１に記載の３次元形状処理装置において、前記パターン解析手段は、前記数列の規則性が一定の変化率で変化する場合には、前記規則性を持つ数列に対してランレングス圧縮を行うことを特徴とする。
また、本発明の請求項６は、請求項１に記載の３次元形状処理装置において、前記パターン解析手段は、前記数列の規則性が１つおきに一定の差分値で変化する場合には、前記規則性を持つ数列に対してランレングス圧縮を行うことを特徴とする。
【００１１】
また、本発明の請求項７は、請求項１に記載の３次元形状処理装置において、前記パターン解析手段は、前記数列に規則性がない場合には、前記規則性のない数列自身とし、圧縮を行わないようにしたことを特徴とする。
また、本発明の請求項８は、請求項２乃至７のいずれか１に記載の３次元形状処理装置において、前記データ値変換手段は、前記精度を実現するために必要な最小の記憶容量のビット数が奇数の場合には、１ビット追加して偶数のビット数に変更することを特徴とする。
【００１２】
また、本発明の請求項９の３次元形状データと属性データとからなる３次元形状データベースを有する３次元形状処理装置の３次元形状処理方法において、共有化手段が、圧縮対象となる３次元形状データ値と属性データ値とを前記３次元形状データベースから取得し、前記３次元形状データ値と前記属性データ値とを記憶領域に記憶し、前記３次元形状データ値と前記属性データ値の精度の範囲内で同じ値であれば、精度の高い値を残してその他は前記記憶領域から削除してデータの共有化をはかるステップと、データ値変換手段が、前記精度を実現するために必要な最小の記憶容量を、前記共有化手段が記憶領域に記憶したデータ値ごとに計算し、そのデータ値を前記記憶容量に格納できる数値へ変換して置き換え、前記記憶領域を再構成するステップと、パターン解析手段が、前記データ値変換手段が再構成した前記記憶領域のデータ値を先頭から順に読み込んで得られる数列を、前記数列の規則性により予め定められた複数のパターンに分類し、前記分類された数列に対応する前記記憶領域のデータ値をその該当するパターンについて予め定められた圧縮方法により圧縮するステップとを備えることを特徴とする。
【００１３】
また、本発明の請求項１０のプログラムは、コンピュータを、請求項１乃至８のいずれか１に記載の３次元形状処理装置の各手段として機能させるためのプログラムである。
また、本発明の請求項１１の記録媒体は、請求項１０に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【００１４】
したがって、３次元形状データと属性データを共有化した幾何情報を無駄なく効率的に圧縮できる。
【００１５】
【発明の実施の形態】
以下、図面を参照して、本発明の３次元形状処理装置の一実施形態を説明する。
図１は、本発明の３次元形状処理装置（以下、本装置という）の要部の機能構成図である。
図１において、本装置は、精度取得手段１０、共有化手段２０、データ値変換手段３０、パターン解析手段４０および圧縮データ保存手段５０を少なくとも含んでいる。
【００１６】
まず、本装置でデータを圧縮するときに使うデータ構造を図２によって説明する。
図２において、最初のブロック（ブロック１）は、３次元形状データおよび属性データを種類ごとに精度の高い種類から順に座標値等の値を連続して並べる。したがって、このブロック１は、幾何情報を格納することになる。
ここで、属性データとは、３次元形状データの補助データであり、例えば、曲線情報（球面であれば中心点の座標値や半径値）、注記のための引き出し線のデータ（両端点の座標値など）、寸法線（例えば、線を構成するための座標値）などを表現するデータである。ここで、種類とは、例えば、計測用とか描画用ということであり、描画用である引き出し線などは精度が低くてよい。
【００１７】
次のブロック（ブロック２）は、３次元形状データがブロック１のどの領域から始まるかを示すインデックスを格納する。
３番目のブロック（ブロック３）は、１つの属性データタイプにいくつの属性データが存在するかを示す個数を、属性データのタイプ順に並べる。ここで、属性データタイプは、例えば、引き出し線や寸法線等を意味している。
４番目のブロック（ブロック４）は、属性データタイプごとに、そのタイプに属する属性データがブロック１のどの領域から始まるかを示すインデックスを格納する。
【００１８】
精度取得手段１０は、ユーザに対してメッセージを表示し、データを圧縮するために必要な、用途により異なる種類別のデータの精度を指定してもらう。
【００１９】
共有化手段２０は、圧縮処理対象となる３次元形状データおよび属性データ等（幾何情報）を３次元形状データベース等から取得し、図２で示したデータ構造へ格納する。
次に、ブロック１の３次元形状データおよび属性データと、それを示すインデックスとの関係を保ちながら、属性データを指定された精度の高い種類順に、種類別に並び替える。この並び替えのとき、複数の属性データ値が指定された精度の範囲内で同じ値であるならば、精度の高い方の属性データ値を残し、一方、他の同じ属性データ値とみなされた方を削除することによって、属性データ値の共有化を行う。
【００２０】
データ値変換手段３０は、図２に格納されたブロック１の座標値について、指示された精度を実現する最低の記憶容量を各座標（ｘ，ｙ，ｚ）別に算出し、浮動小数点で表現していた座標値を固定小数点の値に変換して置き換える。
【００２１】
パターン解析手段４０は、データ値変換手段３０で作成された、図２のブロック１にある幾何情報を表す座標値部分を次のようにして圧縮する。
幾何情報（ブロック１）を１ｂｙｔｅ単位に順に調べて、次のような９つのパターンになるように解析する（図４および図５参照）。
【００２２】
（１）同じ値が連続する数列の場合（タイプＡ）
例えば、０，０，．．．．．，０などのように、同じ値「ゼロ」が連続している場合には、３ｂｙｔｅ（タグ、繰り返し回数、繰り返される値）で表現して圧縮する。
「１」が１０個連続している場合、（Ａ，１０，１）のように表現される。
【００２３】
（２）周期をもった数列の場合（タイプＢ）
例えば、「０，１，２，３」という数列を１周期のパターンとして繰り返される場合、３ｂｙｔｅ（タグ、繰り返し回数、１周期分の数列の長さ）と数列自身で表現して圧縮する。
「０，１，２，３」という数列が１６回繰り返される場合には、
（Ｂ，１６，４，｛０，１，２，３｝）のように表現される。
【００２４】
（３）一定の差分値で増加していく数列の場合（タイプＣ）
例えば、「０，２，４，６，８，１０」のように、スタート値（０）からある一定の差分値（２）で増加している場合、４ｂｙｔｅ（タグ、繰り返し回数、スタート値、差分値）で表現して圧縮する。上例の場合には、（Ｃ，６，０，２）のように表現される。
【００２５】
（４）一定の差分値で減少していく数列の場合（タイプＤ）
例えば、「１２，１０，８，６，４，２，０」のように、スタート値（１２）からある一定の差分値（２）で減少している場合、４ｂｙｔｅ（タグ、繰り返し回数、スタート値、差分値）で表現して圧縮する。上例の場合には、（Ｄ，７，１２，２）のように表現される。
【００２６】
（５）数列に規則性が見つけられない場合（タイプＥ）
例えば、「２，３，９，１，６，３，８，３」のように規則性のない場合、２ｂｙｔｅ（タグ、数列の長さ）と規則性のない数列自身で表現して圧縮する。上例の場合には、（Ｅ，８，｛２，３，９，１，６，３，８，３｝）のように表現される。
【００２７】
（６）一定の増加率で増加していく数列の場合（タイプＦ）
例えば、「１，２，４，８，１６，３２」のように、スタート値（１）からある一定の増加率（２）で増加している場合、４ｂｙｔｅ（タグ、繰り返し回数、スタート値、増加率）で表現して圧縮する。上例の場合には、（Ｆ，６，１，２）のように表現される。
【００２８】
（７）一定の減少率で減少していく数列の場合（タイプＧ）
例えば、「７２９，２４３，８１，２７，９，３，１」のように、スタート値（７２９）からある一定の減少率（３）で減少している場合、４ｂｙｔｅ（タグ、繰り返し回数、スタート値、減少率）で表現して圧縮する。上例の場合には、（Ｇ，７，７２９，３）のように表現される。
【００２９】
（８）１つおきに一定の差分値で増加していく数列の場合（タイプＨ）
例えば、「１，０，２，０，３，０，４，０，５，０」のように、一定値（０）をはさんで１つおきに、スタート値（１）からある一定の差分値（１）で増加している場合、５ｂｙｔｅ（タグ、繰り返し回数、スタート値、差分値、一定値）で表現して圧縮する。上例の場合には、（Ｈ，５，１，１，０）のように表現される。
また、「１５，２５６，２５，２５６，３５，２５６，４５，２５６，５５，２５６」の場合には、（Ｈ，５，１５，１０，２５６）のように表現する。
【００３０】
（９）１つおきに一定の差分値で減少していく数列の場合（タイプＩ）
例えば、「１７，８，１３，８，９，８，５，８，１，８」のように一定値（８）をはさんで１つおきに、スタート値（１７）からある一定の差分値（４）で減少している場合、５ｂｙｔｅ（タグ、繰り返し回数、スタート値、差分値、一定値）で表現して圧縮する。上例の場合には、（Ｉ，５，１７，４，８）のように表現される。
【００３１】
パターン解析手段４０は、ブロック１の幾何情報領域を先頭から１ｂｙｔｅづつ読み込み、９つのパターンのいずれに合致するかを解析して、先に示したような５つのパターンに圧縮する。
例えば、パターンごとに９つのフラグを設け、１ｂｙｔｅごとに調べていくとき、可能性がなくなったものに対して、対応するフラグを落としていく。最後にフラグが落ちたものをパターンのタイプとして圧縮処理を行う。
また、その手法で圧縮した場合、元のサイズより大きいときには、規則性のないパターンとする。
このパターン解析は、すべての幾何情報に対して終了するまで繰り返す。
【００３２】
例えば、データ値変換手段３０で作成された幾何情報が図３に示すものとすると、このパターン解析手段４０実行後は、図６に示したようなデータ圧縮が行われる。
【００３３】
圧縮データ保存手段５０は、パターン解析手段４０で圧縮したブロック１とデータ値変換手段３０で作成されたブロック２乃至４とをあわせて、ファイル化して外部記憶装置等へ保存する。
【００３４】
図７は、本装置によりデータを圧縮するときの動作を示すフローチャートである。
まず、ユーザに対してメッセージを表示し、データを圧縮するために必要な、用途により異なる種類別のデータの精度を指定してもらう（ステップＳ０１）。
【００３５】
圧縮処理対象となる３次元形状データおよび属性データ等を３次元形状データベース等から取得し、図２で示したデータ構造へ格納し、ブロック１の３次元形状データおよび属性データと、それを示すインデックスとの関係を保ちながら、属性データを指定された精度の高い種類順に、種類別に並び替える（ステップＳ０２）。この並び替えのとき、複数の属性データ値が指定された精度の範囲内で同じ値であるならば、精度の高い方の属性データ値を残し、他の同じ属性データ値とみなされた方を削除することによって、属性データ値の共有化を行う。
【００３６】
図２に格納されたブロック１の座標値について、指示された精度を実現する最低の記憶容量を各座標（ｘ，ｙ，ｚ）別に算出し、浮動小数点で表現していた座標値を固定小数点の値に変換して、置き換える（ステップＳ０３）。
【００３７】
ｂｙｔｅ単位でパターン化しやすくするために、指定された精度内に値を圧縮するときに必要なビット数が奇数のビット数となる場合は、１ｂｉｔ追加して偶数のビット数に変更して、パターンを生成しやすくする（ステップＳ０４）。
【００３８】
ブロック１の幾何情報領域を先頭から１ｂｙｔｅづつ読み込み、９つのパターンのいずれに合致するかを解析して、先に示したような９つのパターンに変換してデータ圧縮する（ステップＳ０５）。
例えば、パターンごとに９つのフラグを設け、１ｂｙｔｅごとに調べていくとき、可能性がなくなったものに対して、対応するフラグを落としていく。最後にフラグが落ちたものをパターンのタイプとして圧縮処理を行う。また、その手法で圧縮した場合、元のサイズより大きいときには、規則性のないパターンとする。
このパターン解析がすべての幾何情報に対して終了するまで繰り返す。
【００３９】
パターン解析で圧縮したブロック１と先に作成されたブロック２乃至４とをあわせて、ファイル化して外部記憶装置等へ保存する（ステップＳ０６）。
【００４０】
さらに、本発明は上記の実施形態のみに限定されたものではない。
図８は、本装置を実施するためのコンピュータシステムの構成を示すブロック図である。図８において、中央演算処理装置（ＣＰＵ）１と、媒体読取装置２と、キーボード、マウスまたはタッチパネル等の入力装置３と、ディスプレイ等の表示装置４と、ハードディスク等の記憶装置５およびメモリ６とがデータバス７によって接続されている。
【００４１】
上述した実施形態のサーバごとにその機能を実行するプログラムコードを記録媒体に記録し、その記録媒体に記録されたプログラムコードを媒体読取装置２や記憶装置５から読み取って、図８に示したコンピュータへインストールし、そのプログラムをＣＰＵ１で実行することにより容易に本発明を実施できる。
この場合、記録媒体から読出されたプログラムコード自体も上述した実施形態の機能を実現することになり、そのプログラムコードおよびそのコードを記憶した記録媒体は本発明を構成することになる。
【００４２】
なお、記録媒体としては半導体媒体（例えば、ＲＯＭ、不揮発性メモリカード等）、光媒体（例えば、ＤＶＤ、ＭＯ、ＭＤ、ＣＤ−Ｒ等）、磁気媒体（例えば、磁気テープ、フレキシブルディスク等）等のいずれであってもよい。
【００４３】
また、ロードしたプログラムを実行することにより上述した実施形態の機能が実現されるだけでなく、そのプログラムの指示に基づき、オペレーティングシステム等が実際の処理の一部または全部を行い、その処理によって上述した実施形態の機能が実現される場合も含まれる。
【００４４】
【発明の効果】
以上説明したように本発明によれば、３次元形状データと属性データを共有化した幾何情報を無駄なく効率的に圧縮できる。
【図面の簡単な説明】
【図１】  本発明の３次元形状処理装置の要部の機能構成図である。
【図２】  ３次元形状処理装置でデータを圧縮するときに使うデータ構造図である。
【図３】  パターン解析する前の幾何情報を示す図である。
【図４】  パターン解析で解析される５つのパターンを示す図である。
【図５】  パターン解析で解析される４つのパターンを示す図である。
【図６】  パターン解析した後の図３に対する幾何情報を示す図である。
【図７】  ３次元形状処理装置によりデータを圧縮するときの動作を示すフローチャートである。
【図８】  ３次元形状処理装置を実施するためのコンピュータシステムの構成を示すブロック図である。
【符号の説明】
１…中央演算処理装置（ＣＰＵ）、２…媒体読取装置、３…入力装置、４…表示装置、５…記憶装置、６…メモリ、７…データバス、１０…精度取得手段、２０…共有化手段、３０…データ値変換手段、４０…パターン解析手段、５０…圧縮データ保存手段。
【図１】
0003949013.tif 000002
【図２】
0003949013.tif 000003
【図３】
0003949013.tif 000004
【図４】
0003949013.tif 000005
【図５】
0003949013.tif 000006
【図６】
0003949013.tif 000007
【図７】
0003949013.tif 000008
【図８】
0003949013.tif 000009