(57)【特許請求の範囲】
【請求項１】
一連の曲線セグメントで構成されるオブジェクトのグラフィックアウトラインを定義するデータを記憶するデータ記憶装置であって、
曲線セグメントを定義するデータを受け取る受信手段と、
直線セグメントからなる曲線セグメントを前記データから決定する決定手段と、
直線セグメントでない前記曲線セグメントの各々に対応する第１の数の制御点を記述するデータを記憶する第１記憶手段と、
直線セグメントからなる前記曲線セグメントの各々に対応する縮退された数の制御点を記述するデータを記憶する第２記憶手段とを備え、
前記制御点は一連の値を形成し、前記第１及び第２記憶手段は、前記一連の制御点の１つ前の要素からの距離が予め決められた距離よりも小さい制御点は、第１の相対記憶フォーマットで記憶し、前記一連の制御点の１つ前の要素からの距離が予め決められた距離よりも大きい制御点は、第２の絶対記憶フォーマットで記憶することを特徴とするデータ記憶装置。
【請求項２】
前記曲線セグメントは４つの制御点を記述するデータを有するスプラインからなり、制御点の前記縮退された数は２であることを特徴とする請求項１記載のデータ記憶装置。
【請求項３】
前記各オブジェクトにおいて、前記曲線セグメントは他の少なくとも１つの前記曲線セグメントと端点で接続されており、
前記曲線セグメントは４つの制御点を有するスプラインで構成され、制御点の前記第１の数は３で、制御点の前記縮退された数は１であることを特徴とする請求項１記載のデータ記憶装置。
【請求項４】
更に、前記第１及び第２記憶手段は、前記曲線セグメントを一連のブロックとして記憶し、前記各ブロックは前記ブロック内に記憶される曲線の種類を示すヘッダを有することを特徴とする請求項１に記載のデータ記憶装置。
【請求項５】
前記ブロックは斜線，垂直線，水平線，通常スプラインの各々に対して別々の記憶フォーマットを有することを特徴とする請求項４記載のデータ記憶装置。
【請求項６】
前記第２記憶手段は、前記直線セグメントの接線制御点を切り捨てる手段を含むことを特徴とする請求項１記載のデータ記憶装置。
【請求項７】
コンピュータグラフィックス装置のホストプロセッサを含むことを特徴とする請求項１記載のデータ記憶装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータグラフィックスオブジェクトのためのデータ記憶フォーマットによるデータ記憶装置に関し、より詳しくは、コンピュータグラフィックスオブジェクトのエッジを効率的に記憶するデータ記憶装置に関するものである。
【０００２】
【従来の技術】
近年のコンピュータグラフィックス画像処理システムにおいては、作成されるイメージは、そのアウトラインとアウトライン内部の色情報とを記憶する方法によって、コンピュータシステム内に記憶されることが多い。例えば、ディスプレイやプリント装置に展開される「Ａ」という文字は、文字のアウトラインを記憶することにより、装置に依存しないフォーマットで記憶されるのが普通であり、文字のアウトラインは、文字の輪郭を定義するスプライン系列と内部色の表現とから成る。違った輪郭構造を有するその他のより一般的なオブジェクトについても、スプライン形式でアウトラインを記憶する方法により記憶される。
【０００３】
【発明が解決しようとする課題】
そして、多くのイメージがあり、各イメージの多くがスプラインアウトラインフォーマットで記憶される場合に、記憶に要する領域を最小にしつつ同時にスプラインデータ構成に対する迅速なアクセスを可能とする、スプラインの効率的かつ効果的な記憶方法を求める一般的な要求がある。
【０００４】
本発明の目的は、スプライン或いはそれと類似のもので構成されたグラフィックスオブジェクトのための有効なデータ記憶装置を提供することにある。
【０００５】
【課題を解決するための手段】
この課題を解決するために、本発明のデータ記憶装置は、一連の曲線セグメントで構成されるオブジェクトのグラフィックアウトラインを定義するデータを記憶するデータ記憶装置であって、曲線セグメントを定義するデータを受け取る受信手段と、直線セグメントからなる曲線セグメントを前記データから決定する決定手段と、直線セグメントでない前記曲線セグメントの各々に対応する第１の数の制御点を記述するデータを記憶する第１記憶手段と、直線セグメントからなる前記曲線セグメントの各々に対応する縮退された数の制御点を記述するデータを記憶する第２記憶手段とを備え、前記制御点は一連の値を形成し、前記第１及び第２記憶手段は、前記一連の制御点の１つ前の要素からの距離が予め決められた距離よりも小さい制御点は、第１の相対記憶フォーマットで記憶し、前記一連の制御点の１つ前の要素からの距離が予め決められた距離よりも大きい制御点は、第２の絶対記憶フォーマットで記憶することを特徴とする。
【０００６】
ここで、前記曲線セグメントは４つの制御点を記述するデータを有するスプラインからなり、制御点の前記縮退された数は２である。また、前記各オブジェクトにおいて、前記曲線セグメントは他の少なくとも１つの前記曲線セグメントと端点で接続されており、前記曲線セグメントは４つの制御点を有するスプラインで構成され、制御点の前記第１の数は３で、制御点の前記縮退された数は１である。また更に、前記第１及び第２記憶手段は、前記曲線セグメントを一連のブロックとして記憶し、前記各ブロックは前記ブロック内に記憶される曲線の種類を示すヘッダを有する。また、前記ブロックは斜線，垂直線，水平線，通常スプラインの各々に対して別々の記憶フォーマットを有する。
【０００８】
また、前記第２記憶手段は、前記直線セグメントの接線制御点を切り捨てる手段を含む。また、前記データ記憶装置はコンピュータグラフィックス装置のホストプロセッサを含む。
【００１０】
【発明の実施の形態】
以下、本発明の好適な実施例を、以下の添付図面に関連して説明する。本実施例では、スプラインの記憶に関連して説明するが、本発明はこれに限定されない。
スプラインは、従来例にも記したように、図形のアウトラインを記憶する伝統的な方式である。３次元ベジエスプラインは、普通４つのデータあるいは４つの制御点によって定義される。４つのデータあるいは４つの制御点は、スプラインの２つの端点と２つの接線制御点とから成る。例として、図１は２つのスプライン１と２とを表している。最初のスプライン１には、端点３と４、それに接線制御点５と６とがある。同様に、もうひとつのスプライン２は、端点７と８、それに接線制御点９と１０とを有する。スプライン形式の性質とその種類とに関するさらに詳しい情報は、"Computer Graphics, Principles and Practice" Foley他, 1990, Addison Wesley Publishing Company,Reading, MA 、より詳しくは、第１１章を参照してもらいたい。
【００１１】
出願者によってなされた統計的な研究の結果、コンピュータグラフィックスシステムに記憶されたスプラインの性質が通常ある種の特徴を有することが、既に分かっている。例えば、通常大多数のスプラインは、制御点が線の一部に乗っている直線セグメントに等化である。例えば、図２を参照すれば、そこには端点１３と１４、それに接線制御点１５と１６とを有するスプライン１２が描かれている。スプライン１２は、制御点１５と１６とがスプライン１２上に乗っている直線セグメントに縮退しているということが分かる。
【００１２】
ほかの特徴として、普通は各スプラインは別のスプラインと結合され、結合後のスプラインはさらに別のスプラインと結合されて、さまざまなオブジェクトのアウトラインを作り上げているということが挙げられる。
図３には、スプライン系列２０〜２８でできたオブジェクト１８が描かれている。スプライン２０，２３，２４，２５，２８は直線セグメントに縮退しており、接線制御点を記憶する必要はない。これは、記憶領域を相当節約できることを明示している。オブジェクト１８のアウトラインは、記憶される情報内容を極大化するような「直線認識（Straight Line Aware ：以下ＳＬＡ）」のデータ構造あるいはブロックという形式で、記憶装置に記憶される。
【００１３】
図３のオブジェクト１８は、図４のデータ構造３０の形式で記憶される。このデータ構造は、オブジェクト１８上の開始点である固定点３１を示す開始座標Ｘの値と開始座標Ｙの値とを含む。これに続いて、曲線またはスプラインの数を示す曲線数と明記された変数がある。図３のオブジェクト１８の場合は“９”に等しい。その後に、ＳＬＡブロック３２の系列がデータ構造３０内に記憶される。各ＳＬＡブロック３２はスプライン系列を記憶している。各ＳＬＡブロック内に記憶される曲線あるいはスプラインの数は通常“４”で、最後のＳＬＡブロック３２は残った数の曲線だけを記憶する。
【００１４】
図５には、ＳＬＡ制御バイトと４つの曲線に対応するデータ３３の系列とから成る、１つのＳＬＡブロック３２を示してある。ＳＬＡ制御バイトは１バイト（８ビット）の情報から成り、その中の連続する２ビットの各々が、ＳＬＡ制御バイトに続く曲線に対応している。曲線の種類を指示する２ビットの表示は、次の表１の通りである。
【００１５】
【表１】
0003774494.tif 000002
図３のオブジェクト１８では、先頭のＳＬＡブロックのデータ構造３０が、最初の４つの曲線２０から２３までを記憶する。２番目のＳＬＡブロックのデータ構造３０は、オブジェクト１８の続く４曲線２４から２７までを記憶し、最後のＳＬＡブロックは斜線２８を記憶する。
【００１６】
ここで図６と図７とを参照すると、図４にあるデータ構造３０の先頭ＳＬＡブロック３２に記憶された、図３のオブジェクト１８の一部が図６に示されており、図７がそれに対応する先頭のＳＬＡブロック３２を示している。
ＳＬＡブロック３２はＳＬＡ制御ブロック３５を含む。ＳＬＡ制御ブロック３５は、ＳＬＡブロック３２の曲線データを構成する曲線群である斜線，通常スプライン，通常スプライン，垂直線の順に、これらの曲線に対応するビットパターン（００１１１１１０）を記憶している。
【００１７】
続く記憶領域３６は、図６の斜線２０に対応している。斜線２０に対しては、斜線２０の端点３１の値が、開始座標Ｘと開始座標Ｙとして図４のデータ構造３０内に記憶されているので、端点４０の値だけを記憶しておけば良い。コンピュータグラフィックスシステムに記憶したり画像処理に使用されたりする典型的なオブジェクトを出願者が統計的に調査した結果からわかったことは、スプラインの多くは長さがごく短い、例えばＡ３で出力した場合では３２ピクセル未満の場合が多いということである。それゆえ、あらゆる制御点を絶対座標値よりも相対座標値で記憶する方が望ましい。斜線２０を表現するために記憶される２つの値は、点４０を表現する“＋１０”と“−１０”とである。
【００１８】
この特別な記憶フォーマットは図８に示す相対値記憶フォーマットである。これは、データの７ビットと、記憶データが相対値記憶フォーマットであることを示すために“０”に設定された最下位ビットとから構成されている。相対記憶フォーマットのデータ部は７ビット長なので、相対記憶フォーマットでは“−６４”から“＋６３”までの値を記憶できる。記憶する値がこの範囲を越えたら、図８に示す絶対値記憶フォーマットで値を記憶する。これは２バイト記憶フォーマットであり、先頭バイトの最下位ビットは“１”である。したがって、絶対値記憶フォーマットのデータ部は１５ビット長であり、値の範囲は“０”から“３２７６７”なので、ほとんどの出力装置には充分である。
【００１９】
斜線２０の記憶領域３６に続いて、図７の記憶領域３７に制御点４２から４４を記憶することで、図６の通常スプライン２１が記憶されている。通常スプライン２１に続いて、通常スプライン２２が、図７の記憶領域３８に制御点４５から４７を記憶することで記憶されている。最後に図６の垂直線２３が、図７の記憶領域３９にｙの変化だけを記憶することで記憶されている。これは、ＳＬＡ制御ブロック３５によって垂直線であることがわかっているからである。
【００２０】
図３のオブジェクト１８のその他の曲線も、後続するＳＬＡブロックに記憶することで、オブジェクト１８のアウトライン全体が符号化されている。
以上に述べた方法でデータを記憶する方法は、本来、図９に示す通り、オブジェクトの図形的アウトラインを受け取るという第１処理５０を必要とする。すなわち、曲線セグメントの系列を定義するデータで構成されるオブジェクトの図形的アウトラインを受け取る手段、またある場合には図形的アウトラインの生成をも含む手段を必要とする。次に、直線セグメントからなる曲線セグメントをデータから決定する処理５１がくる。決定の結果に従って、データは２つのうちのどちらか一方に属する。一方のグループに対しては、直線セグメントでない曲線セグメントの各々に対する第１の数の制御点を記憶することを含む処理５２を行う。これには一般に、曲線の端点と全ての中間制御点とを記憶することも含む。もう一方のグループに対しては、直線セグメントからなる曲線セグメントの各々に対する縮退した数の制御点を記憶することを含む処理５３を行う。通常、曲線セグメントの端点のみを記憶する。
【００２１】
図１０に、上に述べた好適な方法を実行するように構成されたシステム６０を図式的に示す。システムにはコンピュータ装置６１があり、これは通常、ディスプレイ６２に接続されている。ディスプレイ６２は、例えばビデオディスプレイ装置やプリンタが一般的である。コンピュータ装置６１には、システムバス６５を介してコンピュータ装置６１の他の構成装置に接続されたホストプロセッサ６４がある。
【００２２】
ホストプロセッサ６４は、読み出し専用メモリ（ＲＯＭ）及び／又は固定ディスク装置（ＨＤＤ）７１に保持された、ディスプレイ上に再現するための像再生を目的としたグラフィックオブジェクトの生成または操作のための処理を行なう制御プログラムによって動作する。通常、ホストプロセッサ６４はグラフィックスプロセッサ６６を介してディスプレイに接続されている。グラフィックスプロセッサ６６は、ホストプロセッサ６４で生成されたグラフィックオブジェクトのディスプレイリストに対して、グラフィックス処理を行なうように特別に形成されたものである。ある場合には、具体的なアプリケーションに依存するが、オブジェクトベースあるいはピクセルベースのイメージデータの一時記憶用の専用グラフィックメモリ６８に、グラフィックスプロセッサ６６が接続されることもある。さらに、コンピュータ装置６１とディスプレイ６２間のデータバッファ用に出力装置（Ｏ／Ｐ）６７が設けられる。アプリケーションによっては、展開されるグラフィックオブジェクトの色塗をするため出力装置６７が用意される。
【００２３】
好適な実施例に従って動作するために、ホストプロセッサ６４はさまざまな情報源からグラフィックオブジェクトを受け取る。すなわち、ＨＤＤ７１，ＲＯＭ６９，フロッピーディスク装置７２，ＰＣＭＣＩＡメモリカードソケット７３または通信モジュール７４を介して通信ネットワークから、あるいは入力モジュール７５を介してバス６５に接続されたキーボード７６やマウス７７といったユーザによって生成される情報源から、グラフィックオブジェクトを受け取る。
【００２４】
一旦受け取ると、好適な実施例に従って配置されたプログラムがホストプロセッサ６４により起動され、各グラフィックオブジェクトの曲線セグメントの各々が分類される。直線オブジェクトに対しては制御点が捨てられて、オブジェクトが前述のフォーマットに従って、例えば半導体ランダムアクセスメモリ（ＲＡＭ）７０やＨＤＤ７１に記憶される。続いてホストプロセッサ６４は、展開と表示のためにグラフィックスプロセッサ６６に渡すオブジェクトのディスプレイリストを用意する。好適な実施例を適用した結果として、ＲＡＭ７０やＨＤＤ７１の使用可能な容量を、そこに記憶する必要のある生データの量を減らすことによって、効果的に増加させることができる。
【００２５】
実際問題としては、上記の記憶フォーマットを用いる結果、アウトラインベースのオブジェクトの記憶の際に記憶容量のかなりの節約になり、これにより与えられた記憶容量内に実質上より多くのオブジェクトを記憶することができるということがわかる。
上述の例は本発明のひとつの実施例に過ぎない。そして応用に関しても、技術に明るい人たちには明らかなことだと思うが、本発明の範囲を越えない範囲で行なうことが可能である。
【００２６】
尚、本発明は、複数の機器から構成されるシステムに適用しても１つの機器から成る装置に適用しても良い。また、本発明は、システム或は装置にプログラムを供給することによって達成される場合にも適用できることはいうまでもない。この場合、本発明に係るプログラムを格納した記憶媒体が本発明を構成することになる。そして、該記憶媒体からそのプログラムをシステム或は装置に読み出すことによって、そのシステム或は装置が、予め定められた仕方で動作する。
【００２７】
【発明の効果】
本発明により、スプライン或いはそれと類似のもので構成されたグラフィックスオブジェクトのための有効なデータ記憶装置を提供できる。
【図面の簡単な説明】
【図１】２つのスプラインとそれらに対応する制御点の例を示す図である。
【図２】スプラインの直線形式の例を示す図である。
【図３】グラフィックオブジェクトの例を示す図である。
【図４】本実施例のグラフィックオブジェクトの記憶に使用されるデータ構造の例を示す図である。
【図５】本実施例の直線認識ブロックの例を示す図である。
【図６】図３のオブジェクトの一部を詳細に示す図である。
【図７】図６の断片の記憶のためのデータ構造の例を示す図である。
【図８】本実施例のデータ点の記憶に使用される相対値記憶フォーマットおよび絶対値記憶フォーマットを示す図である。
【図９】本実施例の概略の処理手順例を示す流れ図である。
【図１０】本実施例に従って動作するシステムのブロック図である。
【図１】
0003774494.tif 000003
【図２】
0003774494.tif 000004
【図３】
0003774494.tif 000005
【図４】
0003774494.tif 000006
【図５】
0003774494.tif 000007
【図６】
0003774494.tif 000008
【図７】
0003774494.tif 000009
【図８】
0003774494.tif 000010
【図９】
0003774494.tif 000011
【図１０】
0003774494.tif 000012