(57)【特許請求の範囲】
【請求項１】
３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを圧縮する形状データ圧縮装置であって、
３次元座標点列または２次元座標点列として与えられる形状データをコード化する際のコード数と量子化精度の入力と、前記３次元座標点列データまたは２次元座標点列データの読み込みとを行なうデータ入力手段と、
前記３次元座標点列データまたは２次元座標点列データを変換パラメータに基づいて１次元正規空間［a,b ］における変換点列に写像するデータ写像手段と、
前記量子化精度に基づいて前記１次元正規空間に対する初期空間分割幅を算出し、該初期空間分割幅で前記１次元正規空間を部分空間に分割し、前記各部分空間に対する前記変換座標点列の分布を解析し、適応的に分割幅を変更することで分布数が０でない部分空間の個数が前記コード数に近似的に等しくなるように決定し、決定された分割幅の時の部分空間に対する前記変換点列の分布を算出し、前記分布数が０でない部分空間に対して、各部分空間に分布する点列の座標値の平均値を求め、この値をコード化してコードブックとする量子化手段と、
前記コードブックに従って前記変換点列をコード変換し、コード変換列を生成するコード変換手段と、
前記データ写像手段によるデータ写像時の変換パラメータと、前記コードブックとコード変換列とからなる圧縮データを出力するデータ出力手段とを備えたことを特徴とする形状データ圧縮装置。
【請求項２】
請求項１記載の形状データ圧縮装置において、
上記コード変換手段の出力であるコード変換列をランレングス圧縮するランレングス圧縮手段を備えたことを特徴とする形状データ圧縮装置。
【請求項３】
３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを圧縮する形状データ圧縮装置であって、
３次元ベクトル列として与えられる形状データをコード化する際のコード数と量子化精度の入力と、前記３次元ベクトル列データの読み込みとを行なうデータ入力手段と、
前記３次元ベクトル列データを極座標表現した場合の２つの角度のデータ列に変換する極座標変換手段と、
前記角度のデータ列を変換パラメータに基づいて１次元正規空間［a,b ］における変換点列に写像するデータ写像手段と、
前記量子化精度に基づいて前記１次元正規空間に対する初期空間分割幅を算出し、該初期空間分割幅で前記１次元正規空間を部分空間に分割し、前記各部分空間に対する前記変換座標点列の分布を解析し、適応的に分割幅を変更することで分布数が０でない部分空間の個数が前記コード数に近似的に等しくなるように決定し、決定された分割幅の時の部分空間に対する前記変換点列の分布を算出し、前記分布数が０でない部分空間に対して、各部分空間に分布する点列の座標値の平均値を求め、この値をコード化してコードブックとする量子化手段と、
前記コードブックに従って前記変換点列をコード変換し、コード変換列を生成するコード変換手段と、
前記データ写像手段によるデータ写像時の変換パラメータと、前記コードブックとコード変換列とからなる圧縮データを出力するデータ出力手段とを備えたことを特徴とする形状データ圧縮装置。
【請求項４】
請求項３記載の形状データ圧縮装置において、
上記コード変換手段の出力であるコード変換列をランレングス圧縮するランレングス圧縮手段を備えたことを特徴とする形状データ圧縮装置。
【請求項５】
３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを圧縮する形状データ圧縮装置であって、
３次元座標点列または２次元座標点列として与えられる形状データをコード化する際のコード数または量子化精度の入力と、前記３次元座標点列データまたは２次元座標点列データの読み込みとを行なうデータ入力手段と、
前記３次元座標点列データまたは２次元座標点列データを変換パラメータに基づいて１次元正規空間［a,b ］における変換点列に写像するデータ写像手段と、
前記コード数が入力された場合には前記１次元正規空間に対する初期空間分割幅を算出し、前記量子化精度が与えられた場合には、この量子化精度で前記１次元正規空間を分割し、分割された部分空間に属する前記変換点列の点を算術式によりコード変換し、コード変換列を生成する量子化手段と、
前記データ写像手段によるデータ写像時の変換パラメータと、前記コード変換時の算術式のパラメータと、コード変換列とからなる圧縮データを出力するデータ出力手段とを備えたことを特徴とする形状データ圧縮装置。
【請求項６】
請求項５記載の形状データ圧縮装置において、
上記量子化手段の出力であるコード変換列をランレングス圧縮すランレングス圧縮手段を備えたことを特徴とする形状データ圧縮装置。
【請求項７】
３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを圧縮する形状データ圧縮装置であって、
３次元ベクトル列として与えられる形状データをコード化する際のコード数または量子化精度の入力と、前記３次元ベクトル列データの読み込みとを行なうデータ入力手段と、
前記３次元ベクトル列データを極座標表現した場合の２つの角度のデータ列に変換する極座標変換手段と、
前記角度のデータ列を変換パラメータに基づいて１次元正規空間［a,b ］における変換点列に写像するデータ写像手段と、
前記コード数が入力された場合には前記１次元正規空間に対する初期空間分割幅を算出し、前記量子化精度が与えられた場合には、この量子化精度で前記１次元正規空間を分割し、分割された部分空間に属する前記変換点列の点を算術式によりコード変換し、コード変換列を生成する量子化手段と、
前記データ写像手段によるデータ写像時の変換パラメータと、前記コード変換時の算術式のパラメータと、コード変換列とからなる圧縮データを出力するデータ出力手段とを備えたことを特徴とする形状データ圧縮装置。
【請求項８】
請求項７記載の形状データ圧縮装置において、
上記量子化手段の出力であるコード変換列をランレングス圧縮するランレングス圧縮手段を備えたことを特徴とする形状データ圧縮装置。
【請求項９】
３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを圧縮する装置であって、
３次元座標点列として与えられる形状データをコード化する際のコード数または量子化精度の入力と、前記３次元座標点列データの読み込みとを行なうデータ入力手段と、
前記３次元座標点列データを変換パラメータに基づいて３次元正規空間［a,b］×［c,d ］×［e,f ］における変換座標点列に写像するデータ写像手段と、
前記コード数が入力された場合には前記３次元正規空間に対する初期空間分割幅を算出し、前記量子化精度が与えられた場合には、この量子化精度で前記３次元正規空間を分割し、分割された部分空間に属する前記変換点列の点を算術式によりコード変換し、コード変換列を生成する量子化手段と、
前記データ写像手段によるデータ写像時の変換パラメータと、前記コード変換時の算術式のパラメータと、コード変換列とからなる圧縮データを出力するデータ出力手段とを備えたことを特徴とする形状データ圧縮装置。
【請求項１０】
請求項９記載の形状データ圧縮装置において、
上記量子化手段の出力であるコード変換列をランレングス圧縮するランレングス圧縮手段を備えたことを特徴とする形状データ圧縮装置。
【請求項１１】
３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを圧縮する形状データ圧縮装置であって、
２次元座標点列として与えられる形状データをコード化する際のコード数または量子化精度の入力と、前記２次元座標点列データの読み込みとを行なうデータ入力手段と、
前記２次元座標点列データを変換パラメータに基づいて２次元正規空間［a,b］×［c,d ］における変換座標点列に写像するデータ写像手段と、
前記コード数が入力された場合には前記２次元正規空間に対する初期空間分割幅を算出し、前記量子化精度が与えられた場合には、この量子化精度で前記２次元正規空間を分割し、分割された部分空間に属する前記変換点列の点を算術式によりコード変換し、コード変換列を生成する量子化手段と、
前記データ写像手段によるデータ写像時の変換パラメータと、前記コード変換時の算術式のパラメータと、コード変換列とからなる圧縮データを出力するデータ出力手段とを備えたことを特徴とする形状データ圧縮装置。
【請求項１２】
請求項１１記載の形状データ圧縮装置において、
上記量子化手段の出力であるコード変換列をランレングス圧縮するランレングス圧縮手段を備えたことを特徴とする形状データ圧縮装置。
【請求項１３】
３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを圧縮する形状データ圧縮装置であって、
３次元ベクトル列として与えられる形状データをコード化する際のコード数または量子化精度の入力と、前記３次元ベクトル列データの読み込みとを行なうデータ入力手段と、
前記３次元ベクトル列データを極座標表現した場合の２つの角度のデータ列に変換する極座標変換手段と、
前記角度のデータ列を変換パラメータに基づいて２次元正規空間［a,b ］×［c,d ］における変換点列に写像するデータ写像手段と、
前記コード数が入力された場合には前記２次元正規空間に対する初期空間分割幅を算出し、前記量子化精度が与えられた場合には、この量子化精度で前記２次元正規空間を分割し、分割された部分空間に属する前記変換点列の点を算術式によりコード変換し、コード変換列を生成する量子化手段と、
前記データ写像手段によるデータ写像時の変換パラメータと、前記コード変換時の算術式のパラメータと、コード変換列とからなる圧縮データを出力するデータ出力手段とを備えたことを特徴とする形状データ圧縮装置。
【請求項１４】
請求項１３記載の形状データ圧縮装置において、
上記量子化手段の出力であるコード変換列をランレングス圧縮するランレングス圧縮手段を備えたことを特徴とする形状データ圧縮装置。
【請求項１５】
３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを伸長する形状データ伸長装置であって、
圧縮された物体形状データを入力とするデータ入力手段と、
上記入力された圧縮された物体形状データのコード変換列を変換時に用いたコードブックを用いて逆変換する逆変換手段と、
上記逆変換して得られた、１次元正規空間［a,b ］に写像された変換点列を逆写像して３次元座標点列データまたは２次元座標点列データを出力する逆量子化手段とを備えたことを特徴とする物体形状データ伸長装置。
【請求項１６】
請求項１５記載の物体形状データ伸長装置において、
上記圧縮された物体形状データはランレングス圧縮されたものであり、
上記逆変換手段は、上記逆変換手段により圧縮された物体形状データを上記コードブックを用いて逆変換する前に、上記ランレングス圧縮された物体形状データを伸長してランレングス圧縮前の圧縮された物体形状データに復元するランレングス圧縮解除部を有することを特徴とする物体形状データ伸長装置。
【請求項１７】
３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを伸長する形状データ伸長装置であって、
圧縮された物体形状データは、圧縮時に、コード化する際のコード数または量子化精度によって決められた分割幅を有する１次元正規空間の部分空間の変換点列の点が算術式によりコード変換されたものであり、
圧縮された物体形状データのコード変換列を上記算術式の逆の算術を行う算術式を用いて逆変換する逆変換手段と、
上記逆変換して得られた、１次元正規空間［a,b ］に写像された変換点列を逆写像して３次元座標点列データまたは２次元座標点列データを出力する逆量子化手段とを備えたことを特徴とする物体形状データ伸長装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、３次元コンピュータグラフィックスによる画像生成で使用される、３次元座標点列，２次元座標点列，３次元ベクトル列などで与えられる形状データの圧縮方法に関するものである。
【０００２】
【従来の技術】
人間や動物などの生き物や自動車、飛行機などの人工物のように、様々な曲面が複雑に組み合わされたような物体を３次元コンピュータグラフィックスで扱う場合、これらの形状のモデリングは、実物もしくは模型の３次元計測によって行なわれることが一般である。但し、最近では自由曲面の扱えるCAD が発達してきたので、自動車や飛行機などの人工物で、設計時からCAD を使用している場合には、CAD の設計データを使用してモデリングすることも増えてきている。いずれにしろ、このような形状データは、通常、その物体の表面上の点のインデックス付き３次元座標点列、物体表面における法線ベクトルのインデックス付き３次元ベクトル点列、物体表面上にテクスチャをマッピングする際に使用する３次元または２次元のテクスチャ座標のインデックス付きの３次元または２次元の座標点列と、それらのインデックスによるインデックス列によって与えられる。これらの点列やベクトル列の規模は、物体の形状に依存するが、概形だけのものでも数百、詳細にモデリングされたものでは数千から数万の規模になる。そこで、このようなデータを圧縮する技術が必要となる。
【０００３】
第１の従来例としては、物体形状を多角形パッチやパラメトリック曲面で近似することで、形状データ量の削減を行なう方法がある。これについては、例えば、特願平４−２０２１５１号公報に示された「３次元形状入力装置」に記載されている。この方法では、形状データ量を削減していくためには、多角形パッチの頂点、もしくはパラメトリック曲面の制御点を削減していく必要がある。
【０００４】
しかしながら、この第１の従来例では、多角形頂点もしくはパラメトリック曲面の制御点を間引くわけであるが、そもそもが点列で表現されているので、パラメトリック曲面の制御点を間引くことはできない。従って、可能なのは、多角形の頂点を間引くことに対応する操作、すなわち表面上の点を間引くことである。しかし、膨大な点列の点の中からどの点を間引けばいいか、その判定方法が示されていないため、その選別が行なえない。仮に、形状を全く無視して選別を行なうと、形状が変形されてデータとして全く使用することができなくなる。また、間引いた点に対する法線ベクトルやテクスチャ座標も対応して間引く必要もあり、更に、インデックス列の変更も必要となる。先に述べたように、形状データは膨大なため、それらの操作は困難を究めることになる。
【０００５】
これに代わる第２の従来例として提案されたものでは、例えば、特願平５−３３３８５９号公報に示された「形状データ圧縮方法および形状データ伸長方法」がある。この方法では、まず、部品に階層化された物体形状を用いることを前提とする、もしくは階層化されていない物体形状の場合にはこれを一旦を部品形状に分割して階層化するということを前提としている。そして、圧縮は各部品毎に行なわれ、圧縮の方法は、各部品形状の頂点座標と量子化された座標との間の変換式によって行なわれる。
【０００６】
しかしながら、この方法では、まずその前提として、階層化されている、もしくは階層化する必要があるが、これらの形状データは一般には階層化されていないことが多い。従って、部品階層化を行なう必要があるが、第２の従来例では、「頂点間の接続を考慮しつつ、頂点の分布範囲を分割することで階層部品化する」と記述されており、この操作を行なうためには、操作者がまず点列における点の間の接続関係を知る必要があるが、膨大な点列データに対してそのような接続関係を考慮することは不可能である。従って、実質的に行なえる分割は点列の分布範囲によって行なう分割だけであり、この操作では実態に則した部品階層化はできない。仮に、部品階層化されたデータがあったとしても、各部品、例えば、人間ならば上肢や下肢、胴体などは対称性などは全く保証されていない複雑な形状である。
【０００７】
前述のように、圧縮は各部品毎に行なわれ、圧縮の方法は、各部品形状の頂点座標と量子化された座標との間の変換式によって行なわれる。これに対応する操作としては、部品形状を定義する部分点列に対して量子化された座標点列との間の変換式によって行なうことになる。第２の従来例によれば、この変換式を算出するためには、まず主軸変換を見い出さなければならないが、直方体等の単純な形状の物体には適用可能であるが、上述のような複雑な形状に対する主軸変換の算出方法は考慮されていないため、結局は、様々な曲面が複雑に組み合わされたような形状データをの圧縮を行なうことはできない。
【０００８】
【発明が解決しようとする課題】
従来の形状データ圧縮方法は以上のようにして行われており、部品形状は直方体等の、対称性などが保証された、単純で特殊な形状データの組合せでできているものしかその圧縮対象として示されておらず、曲面などが多用された複雑な形状に対する圧縮についてはこれに対応することができず、結局、データ圧縮を行うことができないという問題点があった。
【０００９】
本発明は、上記のような問題点に鑑てみなされたもので、人間や動物などの生き物や自動車、飛行機など人工物のように、様々な曲面が複雑に組み合わされたような形状データを圧縮することのできる形状データ圧縮方法、及びこれを実現する形状データ圧縮装置、さらには上記形状データ圧縮方法、及び形状データ圧縮装置にて圧縮された形状データを復元化するための形状データ伸長方法、及び伸長装置を提供することを目的とする。
【００３３】
【課題を解決するための手段】
本発明の請求項１にかかる形状データ圧縮装置は、３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを圧縮する形状データ圧縮装置であって、３次元座標点列または２次元座標点列として与えられる形状データをコード化する際のコード数と量子化精度の入力と、前記３次元座標点列データまたは２次元座標点列データの読み込みとを行なうデータ入力手段と、前記３次元座標点列データまたは２次元座標点列データを変換パラメータに基づいて１次元正規空間［a,b ］にお  ける変換点列に写像するデータ写像手段と、前記量子化精度に基づいて前記１次元正規空間に対する初期空間分割幅を算出し、該初期空間分割幅で前記１次元正規空間を部分空間に分割し、前記各部分空間に対する前記変換座標点列の分布を解析し、適応的に分割幅を変更することで分布数が０でない部分空間の個数が前記コード数に近似的に等しくなるように決定し、決定された分割幅の時の部分空間に対する前記変換点列の分布を算出し、前記分布数が０でない部分空間に対して、各部分空間に分布する点列の座標値の平均値を求め、この値をコード化してコードブックとする量子化手段と、前記コードブックに従って前記変換点列をコード変換し、コード変換列を生成するコード変換手段と、前記データ写像手段によるデータ写像時の変換パラメータと、前記コードブックとコード変換列とからなる圧縮データを出力するデータ出力手段とを備えたものである。
【００３４】
また、この発明の請求項２にかかる形状データ圧縮装置は、上記請求項１記載の形状データ圧縮装置において、上記コード変換手段の出力であるコード変換列をランレングス圧縮するランレングス圧縮手段を備えたものである。
【００３５】
また、この発明の請求項３にかかる形状データ圧縮装置は、３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを圧縮する形状データ圧縮装置であって、３次元ベクトル列として与えられる形状データをコード化する際のコード数と量子化精度の入力と、前記３次元ベクトル列データの読み込みとを行なうデータ入力手段と、前記３次元ベクトル列データを極座標表現した場合の２つの角度のデータ列に変換する極座標変換手段と、前記角度のデータ列を変換パラメータに基づいて１次元正規空間［a,b ］における変換点列に写像するデータ写像手段と、前記量子化精度に基づいて前記１次元正規空間に対する初期空間分割幅を算出し、該初期空間分割幅で前記１次元正規空間を部分空間に分割し、前記各部分空間に対する前記変換座標点列の分布を解析し、適応的に分割幅を変更することで分布数が０でない部分空間の個数が前記コード数に近似的に等しくなるように決定し、決定された分割幅の時の部分空間に対する前記変換点列の分布を算出し、前記分布数が０でない部分空間に対して、各部分空間に分布する点列の座標値の平均値を求め、この値をコード化してコードブックとする量子化手段と、前記コードブックに従って前記変換点列をコード変換し、コード変換列を生成するコード変換手段と、前記データ写像手段によるデータ写像時の変換パラメータと、前記コードブックとコード変換列とからなる圧縮データを出力するデータ出力手段とを備えたものである。
【００３６】
また、この発明の請求項４にかかる形状データ圧縮装置は、上記請求項３記載の形状データ圧縮装置において、上記コード変換手段の出力であるコード変換列をランレングス圧縮するランレングス圧縮手段を備えたものである。
【００３７】
また、この発明の請求項５にかかる形状データ圧縮装置は、３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを圧縮する形状データ圧縮装置であって、３次元座標点列または２次元座標点列として与えられる形状データをコード化する際のコード数または量子化精度の入力と、前記３次元座標点列データまたは２次元座標点列データの読み込みとを行なうデータ入力手段と、前記３次元座標点列データまたは２次元座標点列データを変換パラメータに基づいて１次元正規空間［a,b ］における変換点列に写像するデータ写像手段と、前記コード数が入力された場合には前記１次元正規空間に対する初期空間分割幅を算出し、前記量子化精度が与えられた場合には、この量子化精度で前記１次元正規空間を分割し、分割された部分空間に属する前記変換点列の点を算術式によりコード変換し、コード変換列を生成する量子化手段と、前記データ写像手段によるデータ写像時の変換パラメータと、前記コード変換時の算術式のパラメータと、コード変換列とからなる圧縮データを出力するデータ出力手段とを備えたものである。
【００３８】
また、この発明の請求項６にかかる形状データ圧縮装置は、上記請求項５記載の形状データ圧縮装置において、上記量子化手段の出力であるコード変換列をランレングス圧縮すランレングス圧縮手段を備えたものである。
【００３９】
また、この発明の請求項７にかかる形状データ圧縮装置は、３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを圧縮する形状データ圧縮装置であって、３次元ベクトル列として与えられる形状データをコード化する際のコード数または量子化精度の入力と、前記３次元ベクトル列データの読み込みとを行なうデータ入力手段と、前記３次元ベクトル列データを極座標表現した場合の２つの角度のデータ列に変換する極座標変換手段と、前記角度のデータ列を変換パラメータに基づいて１次元正規空間［a,b ］における変換点列に写像するデータ写像手段と、前記コード数が入力された場合には前記１次元正規空間に対する初期空間分割幅を算出し、前記量子化精度が与えられた場合には、この量子化精度で前記１次元正規空間を分割し、分割された部分空間に属する前記変換点列の点を算術式によりコード変換し、コード変換列を生成する量子化手段と、前記データ写像手段によるデータ写像時の変換パラメータと、前記コード変換時の算術式のパラメータと、コード変換列とからなる圧縮データを出力するデータ出力手段とを備えたものである。
【００４０】
また、この発明の請求項８にかかる形状データ圧縮装置は、上記請求項７記載の形状データ圧縮装置において、上記量子化手段の出力であるコード変換列をランレングス圧縮するランレングス圧縮手段を備えたものである。
【００４１】
また、この発明の請求項９にかかる形状データ圧縮装置は、３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを圧縮する形状データ装置であって、３次元座標点列として与えられる形状データをコード化する際のコード数または量子化精度の入力と、前記３次元座標点列データの読み込みとを行なうデータ入力手段と、前記３次元座標点列データを変換パラメータに基づいて３次元正規空間［a,b ］×［c,d ］×［e,f ］における変換座標点列に写像するデータ写像手段と、前記コード数が入力された場合には前記３次元正規空間に対する初期空間分割幅を算出し、前記量子化精度が与えられた場合には、この量子化精度で前記３次元正規空間を分割し、分割された部分空間に属する前記変換点列の点を算術式によりコード変換し、コード変換列を生成する量子化手段と、前記データ写像手段によるデータ写像時の変換パラメータと、前記コード変換時の算術式のパラメータと、コード変換列とからなる圧縮データを出力するデータ出力手段とを備えたものである。
【００４２】
また、この発明の請求項１０にかかる形状データ圧縮装置は、上記請求項９記載の形状データ圧縮装置において、上記量子化手段の出力であるコード変換列をランレングス圧縮するランレングス圧縮手段を備えたものである。
【００４３】
また、この発明の請求項１１にかかる形状データ圧縮装置は、３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを圧縮する形状データ圧縮装置であって、２次元座標点列として与えられる形状データをコード化する際のコード数または量子化精度の入力と、前記２次元座標点列データの読み込みとを行なうデータ入力手段と、前記２次元座標点列データを変換パラメータに基づいて２次元正規空間［a,b ］×［c,d ］における変換座標点列に写像するデータ写像手段と、前記コード数が入力された場合には前記２次元正規空間に対する初期空間分割幅を算出し、前記量子化精度が与えられた場合には、この量子化精度で前記２次元正規空間を分割し、分割された部分空間に属する前記変換点列の点を算術式によりコード変換し、コード変換列を生成する量子化手段と、前記データ写像手段によるデータ写像時の変換パラメータと、前記コード変換時の算術式のパラメータと、コード変換列とからなる圧縮データを出力するデータ出力手段とを備えたものである。
【００４４】
また、この発明の請求項１２にかかる形状データ圧縮装置は、上記請求項１１記載の形状データ圧縮装置において、上記量子化手段の出力であるコード変換列をランレングス圧縮するランレングス圧縮手段を備えたものである。
【００４５】
また、この発明の請求項１３にかかる形状データ圧縮装置は、３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを圧縮する形状データ圧縮装置であって、３次元ベクトル列として与えられる形状データをコード化する際のコード数または量子化精度の入力と、前記３次元ベクトル列データの読み込みとを行なうデータ入力手段と、前記３次元ベクトル列データを極座標表現した場合の２つの角度のデータ列に変換する極座標変換手段と、前記角度のデータ列を変換パラメータに基づいて２次元正規空間［a,b ］×［c,d ］における変換点列に写像するデータ写像手段と、前記コード数が入力された場合には前記２次元正規空間に対する初期空間分割幅を算出し、前記量子化精度が与えられた場合には、この量子化精度で前記２次元正規空間を分割し、分割された部分空間に属する前記変換点列の点を算術式によりコード変換し、コード変換列を生成する量子化手段と、前記データ写像手段によるデータ写像時の変換パラメータと、前記コード変換時の算術式のパラメータと、コード変換列とからなる圧縮データを出力するデータ出力手段とを備えたものである。
【００４６】
また、この発明の請求項１４にかかる形状データ圧縮装置は、上記請求項１３記載の形状データ圧縮装置において、上記量子化手段の出力であるコード変換列をランレングス圧縮するランレングス圧縮手段を備えたものである。
【００４７】
また、この発明の請求項１５にかかる形状データ伸長装置は、３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを伸長する形状データ伸長装置であって、圧縮された物体形状データを入力とするデータ入力手段と、上記入力された圧縮された物体形状データのコード変換列を変換時に用いたコードブックを用いて逆変換する逆変換手段と、上記逆変換して得られた、１次元正規空間［a,b ］に写像された変換点列を逆写像して３次元座標点列データまたは２次元座標点列データを出力する逆量子化手段とを備えたものである。
【００４８】
また、この発明の請求項１６にかかる形状データ伸長装置は、上記請求項１５記載の物体形状データ伸長装置において、上記圧縮された物体形状データはランレングス圧縮されたものとなっており、上記逆変換手段は、上記逆変換手段により圧縮された物体形状データを上記コードブックを用いて逆変換する前に、上記ランレングス圧縮された物体形状データを伸長してランレングス圧縮前の圧縮された物体形状データに復元するランレングス圧縮解除部を有するものである。
【００４９】
また、この発明の請求項１７にかかる形状データ伸長装置は、３次元コンピュータグラフィックスによる画像生成で使用される物体形状データを伸長する形状データ伸長装置であって、圧縮された物体形状データは、圧縮時に、コード化する際のコード数または量子化精度によって決められた分割幅を有する１次元正規空間の部分空間の変換点列の点が算術式によりコード変換されたものとなっており、圧縮された物体形状データのコード変換列を上記算術式の逆の算術を行う算術式を用いて逆変換する逆変換手段と、上記逆変換して得られた、１次元正規空間［a,b ］に写像された変換点列を逆写像して３次元座標点列データまたは２次元座標点列データを出力する逆量子化手段とを備えたものである。
【００５０】
【発明の実施の形態】
実施の形態１
図１は本発明の形状データ圧縮装置の全体的な構成を示すブロック図であり、１は形状データ圧縮装置を示し、圧縮処理に用いられるプログラムを格納したプログラム格納メモリ１０と、演算処理結果を格納するＲＡＭ１１と上記プログラム格納メモリ１０，ＲＡＭ１１を制御する中央演算処理装置（ＣＰＵ）１２とがそれぞれデータバス１３によって接続されており、またＲＡＭ１１の内容を外部に取り出したり、外部よりプログラム等の情報を読み込んだりするための外部記憶装置１４が接続されたものとなっている。
【００５１】
図２は、上記形状データ圧縮装置の処理レベルでのブロック構成図であり、Ｍ１はデータ入力手段、Ｍ２はデータ変換手段、Ｍ３は量子化手段、Ｍ４はコード変換手段、Ｍ５はデータ出力手段である。
【００５２】
次に図３は本実施の形態１における形状データ圧縮方法によるデータ処理の流れを示すフローチャート図である。図３に示すように、全体の処理は、第１段階から第６段階で実行される。そして、第１段階は処理１と処理２で構成され、第２段階は処理３と処理４で構成され、第３段階は処理５から処理８で構成され、第４段階は処理９と処理１０で構成され、第５段階は処理１１で構成され、第６段階は処理１２で構成されている。
【００５３】
以上のように構成された各処理について詳細に説明する。
処理１では、形状データとコード数と量子化精度の入力処理を行なうものである。本発明で対象とする形状データは、図１２に示した形式で与えられ、物体表面上の点の点列，法線ベクトル列，テクスチャ座標点列，インデックス列がある。但し、図１２では各列がきっちりと分離された形になっているが、列を構成する各データの種類、すなわち点列，法線ベクトル，テクスチャ座標等であることを示す識別子が付加されている場合には、各データが混在した列の形式でもよい。列のインデックスについては明示的に示されていることは少なく、通常は、「形状データの上方から順番に各列のインデックスが付いているものとする」という規約によることが多い。
【００５４】
処理２では、形状データから３次元座標点列または２次元座標点列を、各座標値の列として読み込む処理を行なう。つまり、形状データの中、物体表面上の点の３次元座標点列とテクスチャ座標点列とを処理対象とし、それらの座標点列を座標値毎の列に分離した形で読み込みを行なう。但し、各データが混在した形で与えられた形状データの場合は、各角形状データに付与された識別子によって区別しながら読み込みを行なうことになる。
【００５５】
処理３では、処理２で読み込んだ各座標値の列を１次元正規空間［a,b ］へ変換するためのパラメータの算出を行なう。このパラメータは、平行移動量とスケール変換量で構成される。上記平行移動量については、各座標値の列毎の平均値を求め、各座標値の列毎に、（平均値）−(a+b)/2 を平行移動量とする。スケール変換量については、各座標列毎の絶対値の最大値m を求め、各座標値毎に個別のスケール変換量を用いる場合には、(b−a)/2m をスケール変換量とする。また、共通のスケール変換量を用いる場合には、更に各座標列毎の絶対値の最大値のうちの最大値M を求め、(b−a)/2M をスケール変換量とする。
【００５６】
処理４では、各座標点列を１次元正規空間へ変換し、変換点列を生成する処理を行なう。変換式は、変換する座標値をx としたとき、( スケール変換量) × x−( 平行移動量) によって与えられる。但し、ここでのスケール変換量と平行移動量は、処理３で求めたものを用いる。これを各座標値列の座標値に適用して変換列を求める。但し、座標値列の順序は保存する。
【００５７】
図４は上記処理２で読み込んだ各座標値列を１次元正規空間へ変換する際の処理のイメージを示す図であり、処理２で読み込まれた同じ座標軸の座標値が紙面縦方向に配置され、各座標軸ごとに紙面縦方向に並んだ０からｎまでの座標値が１つの座標値列として取り扱われ、各座標値列の座標値を上記変換式に基づいて変換して変換点列とすることで１次元正規空間に変換される。
【００５８】
処理５では、１次元正規空間を部分空間（小区間）へ分割する処理を行なう。上記処理５から処理８に至るループにおいて、最初の分割幅は、（量子化精度）× (スケール変換量) とし、２回目以降の分割については、後述する処理８で決定される分割幅を用いる。
【００５９】
処理６では、変換点列の各部分空間に対する分布を調べる。つまり、各部分空間に属する変換点列の個数を求める。このとき、分布が０でない部分空間と０となっている部分空間を見分けるための識別子を各部分空間に与える。
【００６０】
処理７では、処理６で各部分空間に与えられた識別子により、分布が０でない部分空間の個数をカウントし、処理１で入力されたコード数との比較判定を行なう。分布が０でない部分空間の個数が最初に入力したコード数よりも大きい場合には、処理８へ遷移し、そうでない場合には処理９へ移る。
【００６１】
分布が０でない部分空間の個数が最初に入力したコード数よりも大きい場合、処理８による処理が行われるが、ここでは、元の分割幅に微小量を加えることで分割幅を変更するようにしている。ここで微小量は、最初の分割幅を基準にして決定する。例えば、最初の分割幅の５％を微小量とするというような形で与えることができる。
【００６２】
分布が０でない部分空間の個数が最初に入力したコード数よりも小さい場合、処理９による処理が行われるが、ここでは、分布が０でない部分空間毎に、その分布の平均値が求められる。
【００６３】
処理１０では、上記処理９で求めた各部分空間の平均値をその部分空間の代表値とし、それをコード化する。コード化の方法には、例えば、以下のような方法がある。
（１）(a+b)/2 に最も近い分布が０でない部分空間にコード０を与え、それ以外の分布が０でない部分空間に対しては、それを挟んで前後に交互の順で１から（分布が０でない部分空間数）−１までのコードを与える。
（２）分布が０でない部分空間に対して、a に近い方からb に向かって、順に０から（分布が０でない部分空間数）−１までのコードを与える。
（３）分布が０でない部分空間に対して、b に近い方からa に向かって、順に０から（分布が０でない部分空間数）−１までのコードを与える。
以上の操作を行なった結果をコードブックとして保存する。但し、（１）における近さの距離判定は、部分空間の全ての要素と、(a+b)/2 の絶対値との差のうち、最小値となるものを基準として判定を行なう。
【００６４】
次に、処理１１では、各部分空間の分布している変換点列に対して、処理１０で割り振ったコードを与え、座標値毎のコード変換列を生成する。但し、処理４で保存していた座標値列の順序に従って変換列は生成する。
【００６５】
処理１２では、処理３の変換パラメータと処理１０のコードブック、および処理１１で生成したコード変換列からなる圧縮データを出力する。
【００６６】
以上のように、本実施の形態１によれば、物体形状を表す３次元座標点列または２次元座標点列を１次元正規空間における点列（変換点列）へ変換し、この１次元正規空間を部分空間（小区間）に分割して、各区間ごとの変換点列の分布を調べ、上記小区間の分割幅を適宜変更し、決定された分割幅の時の、各小区間の点列の座標値の平均値をコード化し、該コードを基にして前記各変換点列をコード変換するようにしたから、１座標をコードブックのコード数分のビットで表現することができ、一般に、浮動小数点、または倍精度の浮動小数点として与えられ、１つの座標または要素毎に３２ビットもしくは６４ビットのデータ領域が必要である形状データを、例えば、座標値が３２ビットで与えられている３次元座標の場合、１点当たり９６ビットが必要であところを、本発明の形状データ圧縮を行なった場合、１座標値はコード数分のビット数ですむようになり、コード数を３２ビットより小さくすれば圧縮することができ、複雑な表面形状を有する物体等を表す形状データを効率的に圧縮することができる。
【００６７】
実測では、物体表面上の点の個数が１３２１９個の形状データ（人間）を用いた場合では、１座標あたり９ビットのコード数（つまりコード数は５１２）で、視認上、元の形状と遜色のない結果を得ることができた。数値データとしても最大誤差は小数点以下第２位に現れる程度であった。この場合のこのデータに対する圧縮率は、大体、２７／９６となる。
【００６８】
実施の形態２
次に本発明実施の形態２による形状データ圧縮方法について、図面を参照しながら説明する。図５は本実施の形態２による形状データ圧縮方法によるデータ処理の流れを示すフローチャートである。図５に示したように、全体の処理は、第１段階から第７段階で実行される。第１段階は処理１と処理２で構成され、第２段階は処理３と処理４で構成され、第３段階は処理５から処理８で構成され、第４段階は処理９と処理１０で構成され、第５段階は処理１１で構成され、第６段階は処理１３で構成され、第７段階は処理１２ａで構成される。
【００６９】
以上のように構成された各処理について詳細に説明する。なお、処理１から処理１１までについては上記実施の形態１と同様にして行なわれるため、ここではそれ以降の処理について説明を行う。
【００７０】
処理１３では、処理１１で生成された座標値毎のコード変換列に対して、座標値毎にランレングス圧縮を行ない、圧縮されたコード変換列を生成する。
【００７１】
処理１２ａでは、処理３の変換パラメータと処理１０のコードブック、および処理１３で生成した圧縮されたコード変換列からなる圧縮データを出力する。
【００７２】
以上のように、本実施の形態２によれば、処理１１で選られたコード変換列をランレングス圧縮し、第２段階における変換パラメータと、第４段階で得られたコードブックと、上記ランレングス圧縮されたコード変換列からなる圧縮データを出力するようにしたので、さらなる高圧縮化を図ることができるようになる。
【００７３】
実施の形態３
次に本発明の実施の形態３による形状データ圧縮方法について、図面を参照しながら説明する。図６は本発明の第３の実施例における形状データ圧縮方法によるデータ処理の流れを示すフローチャートである。図６に示したように、全体の処理は、第１段階から第７段階で構成されている。さらに、第１段階は処理１と処理２ａで構成され、第２段階は処理６０で構成され、第３段階は処理３と処理４で構成され、第４段階は処理５から処理８で構成され、第５段階は処理９と処理１０で構成され、第６段階は処理１１で構成され、第７段階は処理１２ｂで構成される。
【００７４】
以上のように構成された各処理について詳細に説明する。
処理１は、上記実施の形態１における処理１と同様に行なう。
処理２ａでは、形状データから図１２に示した法線ベクトル列（３次元ベクトル列）を読み込む処理を行なう。但し、各データが混在した形で与えられた形状データの場合は、各データに付与された識別子によって区別しながら読み込みを行なうことになる。
【００７５】
処理６０では、３次元ベクトル列の各ベクトルを長さ１に正規化し、正規化したベクトルを極座標変換し、これによって求まるx 軸及びz 軸となす角からなる２つの角度のデータ列を生成する。但し、元の順序は保存する。
【００７６】
処理３では、処理６０で生成した２つの角度データの列を１次元正規空間［a,b ］へ変換するためのパラメータの算出を行なう。このパラメータは、平行移動量とスケール変換量で構成される。平行移動量については、各角度データの列毎の平均値を求め、各角度データの列毎に、（平均値) −(a+b)/2 を平行移動量とする。スケール変換量については、各角度データの列におけるの絶対値の最大値m を求め、角度データ毎に個別のスケール変換量を用いる場合には、(b−a)/2m をスケール変換量とする。また、共通のスケール変換量を用いる場合には、更に各角度データ列毎の絶対値の最大値のうちの最大値M を求め、(b−a)/2M をスケール変換量とする。
【００７７】
処理４では、各角度データの列を１次元正規空間へ変換し、変換点列を生成する処理を行なう。変換式は、変換する角度をx としたとき、( スケール変換量) × x− (平行移動量) によって与えられる。但し、スケール変換量と平行移動量は処理３で求めたものを用いる。これを各座標値列に適用して変換列を求める。但し、角度データ列の順序は保存する。
【００７８】
処理５は上記第１の実施例の処理５と同様にして行なわれる。但し、処理５から処理８に至るループにおいて、最初の分割幅は、（量子化精度) ×( スケール変換量) とし、２回目以降の分割については、処理８で決定される分割幅を用いる。
【００７９】
処理６は本発明の第１の実施例の処理６と同様にして行なわれる。
処理７は本発明の第１の実施例の処理７と同様にして行なわれる。但し、分布が０でない部分空間の個数が最初に入力したコード数よりも大きい場合には、処理８へ遷移し、そうでない場合には処理９へ移る。
【００８０】
処理８から処理１０は本発明の第１の実施例の処理８から処理１０と同様にして行なわれる。
処理１１は本発明の第１の実施例の処理１１と同様に行なわれるが、処理４で保存していた角度データ列の順序に従って変換列を生成する。
【００８１】
処理１２ｂでは、処理３の変換パラメータと処理１０のコードブック、および処理１１で生成したコード変換列からなる圧縮データを出力する。
【００８２】
以上のように、本実施の形態３によれば、処理２ａにて読み込んだ３次元ベクトル列を処理６０にて極座標変換して２次元のデータ（２つの角度データの列）とし、これを１次元正規空間における点列へ変換し、この１次元正規空間を部分空間（小区間）に分割して、各区間ごとの変換点列の分布を調べ、上記小区間の分割幅を適宜変更し、決定された分割幅の時の、各小区間の点列の座標値の平均値をコード化し、該コードを基にして前記各変換点列をコード変換するようにしたから、法線ベクトルの場合、極座標変換によってデータ量が２／３に圧縮されこととなり、複雑な表面形状を有する物体等を表す形状データをより効率的に圧縮することができる。
【００８３】
実測では、本発明の方法で法線ベクトル数が１４７１２のデータに対して実験を行なったところ、１つの角度データ当たり７ビットのコード数（つまりコード数は１２８）で、視認上、元の形状と遜色のない結果を得た。数値データとしても最大誤差は小数点以下第２位に現れる程度であった。この場合のこのデータに対する圧縮率は、大体、１４／９６となる。
【００８４】
実施の形態４
次に本発明の実施の形態４による形状データ圧縮方法について、図面を参照しながら説明する。図７は、本発明の実施の形態４による形状データ圧縮方法によるデータ処理の流れを示すフローチャートである。図７に示したように、全体の処理は、第１段階から第４段階で構成される。さらに、上記第１段階は処理１と処理２で構成され、第２段階は処理３と処理４で構成され、第３段階は処理５と処理７０で構成され、第４段階は処理１２ｃで構成される。
【００８５】
以上のように構成された各処理について詳細に説明する。なお、処理１から処理４については、本発明の実施の形態１で説明したものと同様であるので、ここでは、それ以降の処理について説明する。
【００８６】
処理５では、１次元正規空間の分割を行なう。処理１で量子化精度が与えられた場合は、この量子化精度を処理３で算出したスケール変換量で変換した値を用いて等分割を行なう。
【００８７】
ここで、例として、コード数n+1 が与えられた場合の分割の方法を図１４に基づき説明する。まず、横軸をコード数で等分割する。この時、各等分割された区間にはコード値を割り振る。この割り振り方には、例えば、次のような方法がある。
【００８８】
（１）a に近い方からb に向かって、順に０からn までのコードを与える。
（２）b に近い方からa に向かって、順に０からn までのコードを与える。
但し、コード番号から等分割区間の算出が簡単な式で算出できるように割り振り、コードの割り振り方は予め一意に決めておくものとする。
【００８９】
次に、以下の条件を満たす、関数p(x)を空間分割関数と呼ぶ。
（１）単調増加（２）p(a)=aかつp(b)=b
この空間分割関数p に対して、先の横軸の等分割境界の値を代入した値が、１次元正規空間の分割境界となる。
【００９０】
例えば、図１４の１次式を用いた場合は、等分割と同値になる。また、上に凸な関数f を用いた場合は、a からb に向かって、分割幅が小さくなるような分割が行なえる。逆に、下に凸な関数g を用いた場合は、a からb に向かって、分割幅が大きくなる。また、h のように途中で凸性の向きが変わる場合は、凸性が変化する付近で分割幅が小さく、両端で分割幅大きな分割を実現できる。さらに図１４に示したh とは、その凸性の変化の仕方が逆の関数の場合は、両端で分割幅が小さく、凸性が変化する付近で、分割幅が大きくなるような分割ができる。このように、空間分割関数を入力されるデータに合わせて適当に選択することにより、様々な形での分割が行なえる。以上のようにして、１次元正規空間を部分空間に分割する。但し、本実施の形態では、予め明示的に空間分割関数は決定されているものとする。
【００９１】
処理７０では、等分割を行なった場合には、変換点列の各要素に対して、まずそれが含まれる区間を求め、次にその区間に割り振られたコード値を与えて、各座標値列毎にコード変換列を生成する。空間分割関数p を用いた場合は、p には、先の性質から、必ずp の逆関数が存在するのでそれを求める。すなわち、変換列の各要素を、p の逆関数で変換し、その変換値が含まれる等分割区間に割り振られたコード値を与えることで、各座標値列毎にコード変換列を生成する。
【００９２】
処理１２ｃでは、上記処理３で算出した変換パラメータと、空間分割関数p を規定する算術式パラメータと、コード変換列とからなる圧縮データを出力する。
【００９３】
なお、複数の形状データを圧縮する場合には、全ての形状に対して、１次元正規空間と、算術式パラメータとを共通なものとし、算術式パラメータを記述したデータを１つ保存することで、各形状の圧縮データに算術式パラメータを付加する必要はない。
【００９４】
以上のように、本実施の形態４によれば、処理１で入力されたコード数または量子化精度値を用いて、１次元正規空間の分割を行うようにしたから、コードブックを作成する必要がなくなり、データごとにコードブックが変わるような場合においても高い圧縮率を達成でき、また演算も高速化することができる。
【００９５】
実施の形態５
次に本発明の実施の形態５による形状データ圧縮方法について、図面を参照しながら説明する。図８は本発明の実施の形態５における形状データ圧縮方法によるデータ処理の流れを示すフローチャートである。図８に示したように、全体の処理は、第１段階から第５段階で実行される。さらに、上記第１段階は処理１と処理２ａで構成され、第２段階は処理６０で構成され、第３段階は処理３と処理４で構成され、第４段階は処理５と処理７０で構成され、第５段階は処理１２ｄで構成される。
【００９６】
以上のように構成された各処理について詳細に説明する。なお、処理１から処理５については、本発明の実施の形態３で説明したのと同様であるので、ここでは以降の動作について説明する。
【００９７】
処理７０では、等分割を行なった場合には、変換点列の各要素に対して、まずそれが含まれる区間を求め、次にその区間に割り振られたコード値を与えて、各角度データ列毎にコード変換列を生成する。空間分割関数p を用いた場合は、p には先の性質から、必ずp の逆関数が存在するのでそれを求める。変換列の各要素を、p の逆関数で変換し、その変換値が含まれる等分割区間に割り振られたコード値を与えることで、各角度データ列毎にコード変換列を生成する。
【００９８】
処理１２ｄでは、処理３で算出した変換パラメータと、空間分割関数（算術式）、と、コード変換列とからなる圧縮データとを出力する。
【００９９】
以上のように、本実施の形態５によれば、上記実施の形態４において、３次元ベクトル列を読み込んだ後に、実施の形態３の処理６０と同様にして、これを極座標変換するようにしたので、コードブックを作成する必要がなくなり、データごとにコードブックが変わるような場合においても高い圧縮率を達成でき、また演算も高速化することができるのに加えて、法線ベクトルの場合、極座標変換によってデータ量が２／３に圧縮されこととなり、複雑な表面形状を有する物体等を表す形状データをより効率的に圧縮することができる。
【０１００】
実施の形態６
次に本発明の第６の実施例の形状データ圧縮方法について、図面を参照しながら説明する。図９は本発明の実施の形態６における形状データ圧縮方法によるデータ処理の流れを示すフローチャートである。図９に示したように、全体の処理は、第１段階から第４段階で実行される。さらに、上記第１段階は処理１と処理２ｂで構成され、第２段階は処理９０と処理９１で構成され、第３段階は処理９２と処理７０で構成され、第４段階は処理１２ｅで構成される。
【０１０１】
処理１については、本発明の実施の形態１で示した処理１と同様にして行なわれる。但し、コード数や量子化誤差は、座標毎に独立に与えることもできる。
処理２ｂでは、形状データから３次元座標点列を、各座標値の列として読み込む処理を行なう。つまり、形状データのうち、物体表面上の点の３次元座標点列と３次元のテクスチャ座標点列を処理対象とし、それらの座標点列を座標値毎の列に分離した形で読み込みを行なう。但し、各データが混在した形で与えられた形状データの場合は、データに付与された識別子によってデータの種類を区別しながら読み込みを行なう。
【０１０２】
処理９０では、処理２ｂで読み込んだ３次元座標点列を３次元正規空間［a,b ］×［c,d ］×［e,f ］へ変換するためのパラメータの算出を行なう。このパラメータは、平行移動量とスケール変換量とで構成される。平行移動量については、各座標値の列毎の平均値を求め、各座標値の列毎に、( 第１座標の平均値) −(a+b)/2 ，( 第２座標の平均値) −(c+d)/2 ，( 第３座標の平均値) −(e+f)/2 ，を平行移動量とする。スケール変換量については、各座標列毎の絶対値の最大値m を求め、各座標値毎に個別のスケール変換量を用いる。
【０１０３】
処理９１では、各座標点列を３次元正規空間へ変換し、変換点列を生成する処理を行なう。変換式は、変換する座標値をx としたとき、( スケール変換量) × x−( 平行移動量) によって与えられる。但し、スケール変換量と平行移動量は処理９０で求めたものを用いる。これを各座標値列に適用して変換列を求める。
【０１０４】
但し、各座標値列の順序は保存する。
【０１０５】
処理９２では、各変換列毎に、本発明の実施の形態４における処理５の方法を順次適用する。従って、量子化精度による等分割を用いない場合、空間分割関数は最大で３つ必要である。
【０１０６】
処理７０は、各変換列毎に、本発明の実施の形態４における処理７０と同様の処理を、上記処理９２の空間分割関数の逆行列関数を用いてコード変換列の生成を行なう（量子化誤差を用いた等分割の場合も同様である）。その際、コード変換列の順序は元の座標値列同じにする。
【０１０７】
処理１２ｅでは、処理９０で算出した各座標毎の変換パラメータと、空間分割関数ｐを規定する算術式パラメータ、及びコード変換列とからなる圧縮データを出力する。
【０１０８】
以上のように、本発実施の形態６によれば、処理２ｂにおいて読み込まれた３次元座標点列を処理９０，９１において３次元正規空間における点列へ変換し、この３次元正規空間を部分空間（小区間）に分割して、算術式を用いて各座標値列毎にコード変換列を生成するようにしたから、複雑な表面形状を有する物体等を表す形状データを効率的に圧縮することができる。
【０１０９】
実施の形態７
次に本発明の実施の形態７による形状データ圧縮方法について、図面を参照しながら説明する。図１０は本実施の形態７における形状データ圧縮方法によるデータ処理の流れを示すフローチャートである。図１０に示したように、全体の処理は、第１段階から第４段階で実行される。さらに、第１段階は処理１と処理２ｃで構成され、第２段階は処理１００と処理１０１で構成され、第３段階は処理１０２と処理７０で構成され、第４段階は処理１２ｆで構成される。
【０１１０】
処理１については、本発明の実施の形態１の処理１と同様に行なう。但し、コード数や量子化誤差は、座標毎に独立に与えることもできる。
処理２ｃでは、形状データから２次元座標点列を、各座標値の列として読み込む処理を行なう。つまり、形状データのうち、２次元のテクスチャ座標点列を処理対象とし、それらの座標点列を座標値毎の列に分離した形で読み込みを行なう。但し、各データが混在した形で与えられた形状データの場合は、各データに付与された識別子によって区別しながら読み込みを行なうことになる。
【０１１１】
処理１００では、処理２ｃで読み込んだ２次元座標点列を２次元正規空間［a,b ］×［c,d ］へ変換するためのパラメータの算出を行なう。このパラメータは、平行移動量とスケール変換量で構成される。平行移動量については、各座標値の列毎の平均値を求め、各座標値の列毎に、( 第１座標の平均値) −(a+b)/2 ，( 第２座標の平均値) −(c+d)/2 を平行移動量とする。スケール変換量については、各座標列毎の絶対値の最大値m を求め、各座標値毎に個別のスケール変換量を用いる。
【０１１２】
処理１０１では、各座標点列を２次元正規空間へ変換し、変換点列を生成する処理を行なう。変換式は、変換する座標値をx としたとき、( スケール変換量) × x−( 平行移動量) によって与えられる。但し、スケール変換量と平行移動量は処理１００で求めたものを用いる。これを各座標値列に適用して変換列を求める。但し、各座標値列の順序は保存する。
【０１１３】
処理１０２では、各変換列毎に、本発明の実施の形態４における処理５の方法を順次適用する。従って、量子化精度による等分割を用いない場合、空間分割関数は最大で２つ必要である。
【０１１４】
処理７０では、各変換列毎に、本発明の実施の形態４における処理７０と同様の処理を、処理１０２の空間分割関数の逆行列関数を用いてコード変換列の生成を行なう（量子化誤差を用いた等分割の場合も同様である）。その際、コード変換列の順序は元の座標値列同じにする。
【０１１５】
処理１２ｆでは、処理１００で算出した各座標毎の変換パラメータと空間分割関数p を規定する算術式パラメータ、及びコード変換列からなる圧縮データを出力する。
【０１１６】
以上のように、本実施の形態７によれば、処理２ｃにおいて読み込まれた２次元座標点列を処理１００，１０１において２次元正規空間における点列へ変換し、この２次元正規空間を部分空間（小区間）に分割して、算術式を用いて各座標値列毎にコード変換列を生成するようにしたから、複雑な表面形状を有する物体等を表す形状データを効率的に圧縮することができる。
【０１１７】
実施の形態８
次に本発明の実施の形態８による形状データ圧縮方法について、図面を参照しながら説明する。図１１は本実施の形態８における形状データ圧縮方法によるデータ処理の流れを示すフローチャートである。図１１に示したように、全体の処理は、第１段階から第５段階で実行される。さらに、上記第１段階は処理１と処理２ａで構成され、第２段階は処理６０で構成され、第３段階は処理１００と処理１０１で構成され、第４段階は処理１０２と処理７０で構成され、第５段階は処理１２ｆで構成されている。
【０１１８】
上記処理１から処理６０については、本発明の実施の形態３の処理１から処理６０と同様に行なわれるために、ここでは、それ以降の処理について説明する。
処理１００では、処理６０で生成した２つの角度データ列を２次元正規空間［a,b ］×［c,d ］へ変換するためのパラメータの算出を行なう。このパラメータは、平行移動量とスケール変換量で構成される。平行移動量については、各角度データ列毎の平均値を求め、各角度データ列毎に、( 第１の角度データ列の平均値) −(a+b)/2 ，( 第２の角度データ列の平均値) −(c+d)/2 を平行移動量とする。スケール変換量については、各角度データ列毎の絶対値の最大値m を求め、各角度データ列毎に個別のスケール変換量を用いる。
【０１１９】
処理１０１では、各角度データ列を２次元正規空間へ変換し、変換点列を生成する処理を行なう。変換式は、変換する角度データ値をx としたとき、( スケール変換量) × x−( 平行移動量) によって与えられる。但し、スケール変換量と平行移動量は処理１００で求めたものを用いる。これを各角度データ列に適用して変換列を求める。但し、各角度データ列の順序は保存する。
処理１０２から処理１２ｆは、本発明の第７の実施例における処理１０１から処理１２ｆに示したのと同様にして行なう。
【０１２０】
以上のように、本実施の形態８によれば、処理２ａにおいて読み込まれた３次元ベクトル列を処理６０において極座標変換し、これを処理１００，１０１にて２次元正規空間における点列へ変換し、この２次元正規空間を部分空間（小区間）に分割して、算術式を用いて各座標値列毎にコード変換列を生成するようにしたから、複雑な表面形状を有する物体等を表す形状データを効率的に圧縮することができる。
【０１２１】
本実施の形態８による圧縮を適当に組み合わせると、図１２における形状データは、物体表面上の３次元座標点列，法線ベクトル列，テクスチャ座標点列を各々圧縮することができる。従って、１つの形状データに対して、図１３の（ａ）の形式や、図１３の（ｂ）の形式の圧縮形状データを出力することができる。また、複数の形状データに対して適用する場合には、これらの圧縮形状データが複数できる。但し、共通の正規空間と算術式を用いる場合には、図１３の（ｂ）における、算術式パラメータは、別途に１つ保存しておけば、形状圧縮データから省略できる。
【０１２２】
コードブックを用いた形状圧縮の場合は、コードブックに従ってデコードを掛ける。算術式による場合は、前述のようにコード番号から対応する等分割区間の算出は可能なので、それを算出し、その等分割区間の代表点（例えば中点）を空間分割関数（算術式パラメータか導出可能）で変換した値を求めることでデコードができる。但し、ランレングス圧縮も掛かっている場合には、まず、ランレングス圧縮の通常のデコードを行なってから上記処理を行なう。
【０１２３】
実施の形態９
次に本実施の形態９による形状データ伸長装置について、図面を参照しながら説明する。図１５は本実施の形態９における形状データ伸長装置の概略的な構成を示す図であり、図１５において、Ｍ６は圧縮されたデータを入力するデータ入力手段、Ｍ７は入力された圧縮データを、圧縮時に使用したコードブックまたは算術式を用いて逆量子化する逆量子化手段、Ｍ８は逆量子化されたデータを圧縮時に行ったデータ変換と逆の処理をすることにより、元の３次元座標点列または２次元座標点列、あるいは３次元ベクトル列に変換する逆変換手段である。
【０１２４】
以上のような構成を有する形状データ伸長装置を用いて、上記実施の形態１から８に示されたような構成を有する形状データ圧縮装置（方法）により圧縮された形状データを復号化することができる。
【０１２５】
なお、上記本実施の形態９では、実施の形態２のようにランレングス圧縮を行なったデータを復号化する場合に、逆量子化を行う前にランレングス圧縮を伸長する処理を行う必要がある。
【０１２６】
なお、以上の説明では、バイナリーデータ出力の場合を想定して圧縮率の計算を行っているが、アスキー形式でのデータ出力の場合でも、そのデータが実数に対して、コード数分の整数として出力することが可能なので、先の１座標あたり９ビットで表したコードは、最大で３桁の数として表されることとなるので、元の数字が有効数字が８桁で与えられていた場合、やはり３／８程度の圧縮が行なえる。
【０１２７】
また、再生後の形状データが精度的にもっと荒くてもよい場合には、コード数を減らすことでき、圧縮率をさらに上げることができる。つまり、本発明の方法によれば、圧縮率をコード数（または量子化精度）でコントロールすることが可能であり、優れた利点でもある。
【０１２８】
【発明の効果】
以上のように、この発明によれば、物体形状を表す３次元座標点列または２次元座標点列を１次元正規空間における点列（変換点列）へ変換し、この１次元正規空間を部分空間（小区間）に分割して、各区間ごとの変換点列の分布を調べ、上記小区間の分割幅を適宜変更し、決定された分割幅の時の、各小区間の点列の座標値の平均値をコード化し、該コードを基にして前記各変換点列をコード変換するようにしたから、１座標をコードブックのコード数分のビットで表現することができ、一般に、浮動小数点、または倍精度の浮動小数点として与えられ、１つの座標または要素毎に３２ビットもしくは６４ビットのデータ領域が必要である形状データを、例えば、座標値が３２ビットで与えられている３次元座標の場合、１点当たり９６ビットが必要であところを、本発明の形状データ圧縮を行なった場合、１座標値はコード数分のビット数ですむようになり、複雑な表面形状を有する物体等を表す形状データを効率的に圧縮することができるという効果がある。
【０１２９】
また、３次元ベクトル列を極座標変換して２次元のデータ（２つの角度データの列）とし、これを１次元正規空間における点列（変換点列）へ変換し、この１次元正規空間を部分空間（小区間）に分割して、各区間ごとの変換点列の分布を調べ、上記小区間の分割幅を適宜変更し、決定された分割幅の時の、各小区間の点列の座標値の平均値をコード化し、該コードを基にして前記各変換点列をコード変換するようにしたので、複雑な表面形状を有する物体等を表す形状データをより効率的に圧縮することができる。
【０１３０】
さらに、
【図面の簡単な説明】
【図１】  本発明の形状データ圧縮装置の全体的な構成を示すブロック図である。
【図２】  形状データ圧縮装置の処理レベルでのブロック構成図である。
【図３】  本発明の実施の形態１における形状データ圧縮方法のフローチャートを示す図である。
【図４】  各座標値の列を１次元正規空間へ変換する際の処理のイメージを示す図である。
【図５】  本発明の実施の形態２における形状データ圧縮方法のフローチャートを示す図である。
【図６】  本発明の実施の形態３における形状データ圧縮方法のフローチャートを示す図である。
【図７】  本発明の実施の形態４における形状データ圧縮方法のフローチャートを示す図である。
【図８】  本発明の実施の形態５における形状データ圧縮方法のフローチャートを示す図である。
【図９】  本発明の実施の形態６における形状データ圧縮方法のフローチャートを示す図である。
【図１０】  本発明の実施の形態７における形状データ圧縮方法のフローチャートを示す図である。
【図１１】本発明の実施の形態８における形状データ圧縮方法のフローチャートを示す図である。
【図１２】  入力形状データの構成図である。
【図１３】  圧縮形状データの構成図である。
【図１４】  正規空間を部分空間に分割するための空間分割関数を説明するための図である。
【図１５】  本実施の形態９における形状データ伸長装置の概略的な構成を示す図である。
【符号の説明】
１    形状データ圧縮装置
１０  プログラム格納メモリ
１１  ＲＡＭ
１２  ＣＰＵ
１３  データバス
Ｍ１  データ入力手段
Ｍ２  データ変換手段
Ｍ３  量子化手段
Ｍ４  コード変換手段
Ｍ５  データ出力手段
Ｍ６  データ入力手段
Ｍ７  逆量子化手段
Ｍ８  額変換手段
【図１】
0004005180.tif 000002
【図２】
0004005180.tif 000003
【図３】
0004005180.tif 000004
【図４】
0004005180.tif 000005
【図５】
0004005180.tif 000006
【図６】
0004005180.tif 000007
【図７】
0004005180.tif 000008
【図８】
0004005180.tif 000009
【図９】
0004005180.tif 000010
【図１０】
0004005180.tif 000011
【図１１】
0004005180.tif 000012
【図１２】
0004005180.tif 000013
【図１３】
0004005180.tif 000014
【図１４】
0004005180.tif 000015
【図１５】
0004005180.tif 000016