図形描画装置、図形描画方法、及びプログラム
【課題】 少ないリソースやメモリしか使用不可能な環境下にて、高速かつ安定的に動作することが可能な図形描画装置、手法を提供することを目的とする。
【解決手段】 入力となるベクトルデータ群に含まれる処理対象ベクトルの処理順序、データを管理し、管理情報に基づいて、前記ベクトルデータ群から処理対象ベクトルのデータの抽出を行い、抽出されたベクトルデータの処理順の算出を行い、算出された処理順序情報を用いて処理対象点の管理、対象ベクトルの処理の終了の通知を行い、処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出し、算出された塗りつぶし情報を用いて、図形の描画を行う。
【解決手段】 入力となるベクトルデータ群に含まれる処理対象ベクトルの処理順序、データを管理し、管理情報に基づいて、前記ベクトルデータ群から処理対象ベクトルのデータの抽出を行い、抽出されたベクトルデータの処理順の算出を行い、算出された処理順序情報を用いて処理対象点の管理、対象ベクトルの処理の終了の通知を行い、処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出し、算出された塗りつぶし情報を用いて、図形の描画を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は図形の描画装置、描画方法に関する。
【背景技術】
【０００２】
任意の多角形を描画する手法として様々な手法が開発されてきている。（１）ポイントベースの手法、（２）ラスターラインベースの手法、（３）トライアングルベースの手法、（４）ステンシルバッファベースの手法などである。
【０００３】
（１）は、描画領域に含まれる各点（ピクセル）に関して、描画の判定を行い、ポイント（ピクセル）単位で描画処理を行っていくものである。この際、描画処理の高速化のため、無駄な描画領域を削除したり、各点における描画判定を簡略化したりという様々な工夫が凝らされてきている。さらに、高速化のため、この機能をハードウェア化することも良く行われている。このハードウェア化された装置の１つとして、ラスタライザと呼ばれるものがある（例えば、非特許文献１を参照）。この手法は、シンプルな手法であるが故に非常に安定動作することが特徴であるが、各点毎に描画判定を行う必要があるため、非常に処理コストが大きいという問題点がある。このため、典型的には専用ハードウェア化されることがほとんどである。（２）は、（１）を改良したもので、各点毎、あるいは、それに相当する範囲で描画判定を行うところまでは似ているが、描画する際に、各点における描画部分をまとめ、これを描画したい画面のスキャンライン単位の線の描画に置き換えたものである。こうすることで、描画判定に関しては（１）と同様に処理コストが大きいが、描画処理のコストは小さくなるため、（１）よりも高速化が見込まれる。また、描画判定の部分は、高速なCPUを持つ処理系での処理や専用ハードウェア化などが必要とされるが、描画処理に関しては、汎用的なグラフィックスLSI（GPU）を用いることが可能である。なぜならば、グラフィックスLSIは、線、三角形を高速に描画する機能を持っているからである。このため、（１）よりも汎用性が上がっていると言える。（３）は、描画したい多角形を三角形群に分割し、三角形ベースで描画しようというものである（例えば、非特許文献２を参照）。これは、汎用のグラフィックスLSI、または、高速な三角形描画装置の使用を前提として高速化を図ろうという意図がある。（なぜならば、グラフィックスLSIは、線、三角形を高速に描画する機能を持っているからである。）このため、（１）、（２）の手法よりもより汎用性がある手法である。しかし、三角形分割のために複雑な処理が必要とされるため、この部分の安定性が問題となりうる。また、描画したい多角形が非常に複雑な形状を持っている場合には、三角形分割処理の計算コストが非常に大きくなるという問題もある。また、三角形群をグラフィックスLSIなどを用いて描画することを前提としているため、グラフィックスLSIに十分なリソースが無い場合、使用することができないという問題もある。多角形を三角形群に分割し、これをグラフィックスLSIに投入する必要があるため、比較的メモリなどの使用量が多くなるからである。（４）は、完全に汎用グラフィックスLSIの使用を前提とするもので、グラフィックスLSIの機能として存在しているステンシルバッファという機能を用いて多角形描画を実現するものである（例えば、非特許文献３）。これは、（１）〜（３）のどれよりも高速かつ安定的に多角形描画が可能な方法であるが、グラフィックスLSIの機能をフル活用するため、グラフィックスLSIの多くのリソースを必要とするという問題点が存在する。
【非特許文献１】Renate Kempf and Chris Frazier, “The OpenGL Processing Pipeline”, Chapter 2: Overview of Commands and Routines, OpenGL Reference Manual Second Edition, ISBN 0-201-46140-4, pp.8-16, 1997.
【非特許文献２】Ｍ.ドバーグ、Ｍ.ファン.クリベルド、M.オーバマーズ、O.シュワルツコップ, “コンピュータ・ジオメトリ”, ISBN 4-7649-0277-X, pp.55-75, 近代科学社, 2000.
【非特許文献３】Jackie Neider, Tom Davis, Mason Woo, “Drawing Filled, Concave Polygons Using the Stencil Buffer”, Chapter 13: Now That You Know, OpenGL Programming Guide, ISBN 0-201-63274-8, pp.398-399, 1993.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、上記のように、従来の様々な手法に存在していた安定動作、使用リソースの問題点を解消し、かつ、この条件下でなるべく高速動作が可能な図形描画を行う装置、および、手法を提供することを目的とする。
【０００５】
具体的には、グラフィックスLSIなどのハードウェアリソースの使用が困難な状況下で、なるべく安定動作が可能なシンプルな手法を用いて、なるべく高速化が可能な図形描画装置および手法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
この発明の図形描画装置は、入力となるベクトルデータ群を管理するベクトルデータ群管理手段と、前記ベクトルデータ群管理手段での管理情報に基づいて、入力となるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、前記ベクトルデータ抽出手段で抽出されたベクトルデータの処理順を算出する処理順序算出手段と、前記処理順序算出手段で算出された処理順序を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出するための塗りつぶし情報算出手段と、前記塗りつぶし情報算出手段によって得られた塗りつぶし情報を用いて、図形を描画するための描画手段を具備することを特徴とする。
【０００７】
また、この発明の図形描画方法は、入力となるベクトルデータ群に含まれる処理対象ベクトルの処理順序、データを管理するステップと、管理情報に基づいて、前記ベクトルデータ群から処理対象ベクトルのデータの抽出を行い、抽出されたベクトルデータの処理順の算出を行うステップと、算出された処理順序情報を用いて処理対象点の管理、及び対象ベクトルの処理の終了の通知を行うステップと、処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出するステップと、算出された塗りつぶし情報を用いて、図形の描画を行うステップを含むことを特徴とする。
【０００８】
更に、この発明の図形描画装置をコンピュータで機能させるプログラムは、入力となるベクトルデータ群に含まれる処理対象ベクトルの処理順序、データを管理する機能と、管理情報に基づいて、前記ベクトルデータ群から処理対象ベクトルのデータの抽出を行い、抽出されたベクトルデータの処理順の算出を行う機能と、算出された処理順序情報を用いて処理対象点の管理、及び対象ベクトルの処理の終了の通知を行う機能と、処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出する機能と、算出された塗りつぶし情報を用いて、図形の描画を行う機能を含むことを特徴とする。
【発明の効果】
【０００９】
本発明によれば、多角形図形の描画を低消費メモリで高速かつ安定的に行う装置、および、手法を提供することができる。
【発明を実施するための最良の形態】
【００１０】
以下、図面を参照しながら発明の実施の形態を説明する。
［第１の実施形態］
まず、本発明の第１の実施形態について説明する。
＜全体の構成＞
図１は、本発明の第１の実施形態に係る図形描画装置の全体構成図である。
本実施形態の図形描画装置は、入力されたベクトルデータ群を管理するためのベクトルデータ群管理部１と、ベクトルデータ群管理部１での管理情報に基づいて、入力されたベクトルデータ群から処理対象となるベクトルデータを取得するためのベクトルデータ抽出部２と、ベクトルデータ抽出部２で取得されたベクトルデータから、処理の開始点および終了点を算出するための開始点・終了点算出部３と、開始点・終了点算出部３で算出された開始点・終了点情報、または／および、塗りつぶし情報算出部７から得られる対象点の処理の終了の通知情報、を用いて処理対象点の決定を行ったり、ベクトルデータ群管理部１に対象ベクトルの処理の終了を通知したりするための対象点管理部４と、対象点管理部４で決定された処理対象点の情報をもとに、処理対象点のピクセル座標位置を算出するための対象点算出部５と、対象点算出部５で算出された処理対象点の座標位置の両脇のピクセルが塗りつぶし対象となるかどうかの判定を行うための対象点判定部６と、対象点判定部６での判定結果をもとに、対象点が、塗りつぶし開始点、塗りつぶし終了点、どちらでも無い点のいずれかであるかを判断するし、それを対象点の座標位置とともに所定の形式で塗りつぶし情報として算出するための塗りつぶし情報算出部７と、塗りつぶし情報算出部７で算出された塗りつぶし情報を塗りつぶし情報保存領域９に登録するための塗りつぶし情報登録部８と、ベクトルデータ抽出部２で取得されたベクトルデータをもとに、図形描画を行うために最小限必要な矩形領域の情報を算出・更新するための描画領域算出部１０と、描画領域算出部１０で算出された矩形領域を補正して、最終的に描画を行う領域を求めるための描画領域補正部１１と、塗りつぶし情報保存領域９に保存された塗りつぶし情報を描画するのに適正なデータとして補正するための描画データ補正部１２と、描画領域補正部１１で得られた描画領域情報、描画データ補正部１２で補正されたデータを用いて、図形を描画するための描画部１３から構成される。
【００１１】
＜ベクトルデータ群管理部＞
まず、ベクトルデータ群管理部１について説明する。
＜図形描画の説明＞
ここで、まず、本実施の形態で扱う図形描画について説明する。
本実施の形態で扱う図形描画とは、多角形を構成するベクトルデータ群、または、それに相当する点データ群で形成される入力データから、それで示される多角形で構成される図形を描画するものである。この際、所定の規則に従って、図形の内部の塗りつぶしを行う。
【００１２】
具体的には、図２に示されるような「ベクトル１」〜「ベクトル５」のような「（一筆書きで得られる）多角形」を構成するベクトルデータ群の入力があったとすると、図３，図４に示されるような図形を描画する。図３，図４の差は、多角形の内部の塗りつぶし規則の違いである。図３は、even-odd fillルールと呼ばれる規則に従って、多角形（この例の場合、星形）の内部を塗りつぶした例である。図４は、non-zero fillルールと呼ばれる規則に従って、同様の多角形を塗りつぶした例である。
【００１３】
ここで、even-odd fillルール、non-zero fillルールに関して簡単に説明する。Even-odd fillルールとは、領域（閉路）内部の任意の点から任意の方向に半直線を引き（rayを飛ばし）、その半直線を領域のエッジがまたぐ方向に応じてカウンタを増減させた結果、カウンタが奇数になる領域は塗りつぶし、偶数になる領域は塗りつぶさないという規則である。Non-zero fillルールは、同様のカウンタ増減の結果、カウンタが0でない部分は塗りつぶすという規則である。詳しくは、”www.w3.org/TR/SVG/”に説明されているので、そちらを参照して頂きたい。
【００１４】
なお、塗りつぶし規則の例として、even-odd fillルール、non-zero fillルールの２つに関して説明したが、これはあくまでも例であり、これに限定されるものではない。任意の塗りつぶし規則を用いることができる。
【００１５】
＜ベクトルデータ群の説明＞
次に、図形描画の入力となるベクトルデータ群、または、それに相当する点データ群について説明する。
本実施の形態で扱うベクトルデータ群とは、2次元（あるいは3次元）の座標値を持つ2つの点データP1（始点）,P2（終点）で構成されるベクトルデータV(n) = P2(n) − P1(n)の集合である。ここで、n= 1, ・・・, Nであり、Nはベクトルデータ群を構成するベクトルの個数を示している。また、V(n)は、n番目のベクトルデータ、P1(n),P2(n)は、n番目のベクトルを構成する始点、終点の点データである。本発明で扱うベクトルデータ群では、互いに連続するベクトル同士は、その端点を共有する。つまり、P1(n) = P2(n-1)の関係が成り立つ。このようにして得られるベクトルデータ群は、一筆書きによって得られる多角形図形を形成する（図５参照）。図５は、N=3の例であり、図形として、三角形が形成されている。
【００１６】
P2(N) = P1(1)でない場合には、形成される図形は閉じていないが、この場合、P1(N+1)=P2(N), P2(N+1)=P1(1)で表されるN+1番目の点が仮想的に存在するとして、閉図形として扱う（図６参照）。図６の場合、仮想的なV(4)があるとして、四角形の閉図形として扱う。
【００１７】
また、ベクトルデータ群によって形成される図形は、一般多角形で構成される任意の形状を取ることが可能で、凸形状だけではなく凹形状や自己交差形状を含んでも構わない（図７参照）。
【００１８】
また、点データ群も、ベクトルデータ群と同様に扱うことができる。今、点データ群が、P(n), n = 1 ・・・ Nで表されているとすると、
V(n) = P(n+1) − P(n) n = 1, ・・・, N-1 （１）
【００１９】
として得られるV(n)は、ベクトルデータ群となるからである。入力が点データ群であった場合、上記のような変換を行うことで、ベクトルデータ群として扱うことが可能である。
【００２０】
＜ベクトルデータ群管理部の説明＞
ベクトルデータ群管理部１は、上記で説明したような図形描画のための入力として得られるベクトルデータ群を管理するためのものである。
具体的には、ベクトルデータ群管理部１は、入力として得られるベクトルデータ群の中で、現在の処理対象となるベクトルデータがどれであるかの管理を行う。
処理開始時は、ベクトルデータ群の中の1番目のベクトルデータが処理対象として選択される。また、以降は、後述する対象点管理部４から、処理対象となる点データの処理の終了通知を受け、処理対象となるベクトルデータを２番目、３番目、・・・と逐次更新していく。また、処理対象となるベクトルデータが無くなったならば、処理完了の通知を後述する描画部１２に送る。
【００２１】
以下に詳細なベクトルデータ群管理部１の処理フローを示す（図８）。まず、処理対象ベクトル番号ｎを１にセットする（Ｓ１０１）。次に、管理対象となるベクトルデータをV(n)とする（Ｓ１０２）。後述するベクトルデータ抽出部２に処理対象となるベクトルデータV(n)を通知する（Ｓ１０３）。次に、後述する対象点管理部４からの終了通知を待ち、終了通知を受けたら、次のステップに進む（Ｓ１０４）。次にステップＳ１０５にて、全てのベクトルデータを処理したかの判定を行い、処理していない場合には、ステップＳ１０６に、処理した場合には、ステップＳ１０７に進む。ステップＳ１０６では、処理対象ベクトル番号ｎの更新を行う。典型的には、ｎを１つインクリメントし、ステップＳ１０２へ戻る。なお、更新は必ずしも連続的に行われる必要はない。何らかの規則に従って、所定のベクトルデータを管理対象とすることもできる。ステップＳ１０７では、後述する描画部１２に処理完了通知を送る。以上が、典型的な処理フローの内容である。
【００２２】
ただし、ベクトルデータ群管理部１は以降の処理で処理対象となるベクトルデータV(n)を管理するものであって、以上の処理フローは一例に過ぎない。任意の選択手法を用いて選択したV(n)を処理対象とすることができる。
【００２３】
＜ベクトルデータ抽出部＞
次に、ベクトルデータ抽出部２について説明する。
ベクトルデータ抽出部２は、ベクトルデータ群管理部１から通知された処理対象のベクトル番号情報を用いて、ベクトルの開始点P1の座標、終了点P2の座標、ベクトルの塗りつぶし色などの属性情報などで構成されるベクトルデータを、入力されたベクトルデータ群の中から取得するためのものである。
【００２４】
なお、ベクトルデータとして、座標や色属性の例を説明したが、これに限定されるものではなく、入力として得られるベクトルデータ群に含まれるデータ種別の全て、あるいは、一部を取得することが可能である。
【００２５】
取得したベクトルデータは、後述する開始点・終了点算出部３に渡される。
＜開始点・終了点算出部＞
次に、開始点・終了点算出部３について説明する。
開始点・終了点算出部３は、ベクトルデータ抽出部２から受け取った処理対象のベクトルのデータをもとに、以降の処理の開始点および終了点を算出するためのものである。
【００２６】
以降、本実施の形態における図形描画処理を、垂直方向（ｙ軸方向）を基準として行う場合を例として説明を進める。ただし、これはあくまでも一例であり、これに限定されるものではない。水平方向（ｘ軸方向）を基準として行うことも可能であるし、任意の方向を基準として行うことも可能である。任意の方向としては、描画したい図形の主軸方向（分散が最も小さい方向）などを考えることができる。また、方向は2次元に限定されるものではない。
【００２７】
開始点・終了点算出部３では、基本的には、ベクトルデータを構成する２点P1（ベクトルの始点）,P2（ベクトルの終点）のうち、ｙ座標が小さい方を開始点に、大きい方を終了点として開始点、終了点のｙ座標を算出する。以下に、詳細な処理フローを示す（図９）。
【００２８】
点P1の座標が(x1, y1)、点P2の座標が(x2,y2)であるとする。まず、点P1とP2のｙ座標の比較を行い、両者が等しいかどうか（y1 = y2かどうか）の判定をする（Ｓ２０１）。等しい場合には、ステップＳ２０５に進む。そうでない場合には、ステップＳ２０２へ進む。ステップＳ２０２では、y1 < y2かどうかの判定を行い、真の場合はステップＳ２０４へ、偽の場合は、ステップＳ２０３へ進む。
【００２９】
ステップＳ２０３では、開始点のｙ座標ys = y2 + 1, 終了点のｙ座標ye = y1に設定する。同様に、ステップＳ２０４では、ys = y1, ye = y2 − 1、ステップＳ２０５では、ys = y1, ye = y2と設定する。
【００３０】
この様子を模式的に表現したのが図１０である。点P1とP2のｙ座標が等しい場合（図（ａ））は図示した２通りの可能性があるが、何れもys = ye = y1 (=y2)となる。この場合、開始点と終了点とは同じｙ座標となる。
【００３１】
y1 < y2すなわち、P1のｙ座標が小さい場合は図中（ｂ）のように、P1のｙ座標y1を開始点、P2の１つ手前の点P2’のｙ座標y2 − 1を終了点とする。
【００３２】
単にP2を終了点として選ばないのは、P2は、次のベクトルの始点となるため、次のベクトルの処理の際に描画のための処理が行われるため、この段階で終了点に含めてしまうと、処理が2重となり処理コストを考えた際に、効率が低下するためである（図１１）。図において、P1(n+1) = P2(n)となるため、このようなことが起こる。
【００３３】
同様に、y1 > y2すなわち、P1のｙ座標が大きい場合は図中（ｃ）のように、P2の１つ手前の点P2’のｙ座標y2+1を開始点、P1のｙ座標y1を終了点とする。
【００３４】
なお、以上では、描画効率のため、２重に処理される点を終了点のｙ座標yeとして算出せず、１つ隣りの点を算出する例を示したが、これに限定されるものではない。単に終了点をｙ座標が大きい方の点のｙ座標として算出しても構わない。
【００３５】
以上で、開始点・終了点のそれぞれのｙ座標が算出された。開始点・終了点算出部３は、この結果を後述する対象点管理部４に送る。
なお、以上では、ｙ座標が小さい方を開始点、大きい方を終了点とする例を示したが、これに限定されるものではない。逆で、大きい方を開始点、小さい方を終了点としてもよい。
【００３６】
また、単純に、ベクトルの始点P1を開始点、終点P2を終了点としても良いし、逆に、P2を開始点、P1を終了点としても良い。
またこれ以外でも、ベクトルデータ全体を通して、開始点、終了点の選び方が同様であって、しかも、算出した開始点、終了点を用いて、後述する以降の処理を一意に行うことが出来る手法であれば何でもよい。また、ｙ座標を基準としているのは、本実施例では上述したように垂直方向を基準とした例を用いて説明しているからであって、これに限定される訳ではない。基準の方向に合わせて、同様の効果となるように適宜変化して構わない。
【００３７】
また、以上では、ベクトルデータが取得される例を示したが、上述（＜ベクトルデータ群の説明＞の項）した通り、入力は点群データでも同様である。入力が点群データであった場合、上述の通りの変換を本開始点・終了点算出部３で行い、ベクトルデータとして扱い、同様の処理を行う。
【００３８】
＜対象点管理部＞
次に、対象点管理部４について説明する。
対象点管理部４は、ベクトルデータ抽出部２で取得した処理対象のベクトルのデータ、および、開始点・終了点算出部３で算出された開始点・終了点データを受け取り、ベクトルデータを点（ピクセル）単位に分割し、処理対象とする点（ピクセル）のデータとして管理するためのものである。
【００３９】
具体的には、図１２に示す処理フローのように動作する。まず、開始点・終了点算出部３で算出された開始点を処理対象点（処理対象ピクセル）としてセットする（Ｓ３０１）。次に、処理対象点（ｙ座標の値が現在の対象点）を管理対象とする（Ｓ３０２）。次に、ステップＳ３０２で管理対象とした点のｙ座標などの情報を後述する対象点算出部５に通知する（Ｓ３０３）。次に、塗りつぶし情報算出部７からの処理完了の通知を待ち、通知を受けた後に、ステップＳ３０５へ進む。ステップＳ３０５では、開始点・終了点算出部３で算出された終了点の処理が完了したかどうかを判定し、完了していない場合は、ステップＳ３０６へ進む。完了していると判定された場合は、ステップＳ３０７へ進む。ステップＳ３０６では、管理対象点のｙ座標の更新を行い、ステップＳ３０２に戻る。ステップＳ３０７では、対象点管理部４での処理が完了した旨の通知をベクトルデータ群管理部１へ送信する。
【００４０】
＜対象点算出部＞
次に、対象点算出部５について説明する。
対象点算出部５は、ベクトルデータ抽出部２で取得した処理対象のベクトルのデータ、および、対象点管理部４から通知された管理対象点情報を受け取り、管理対象点の座標データを算出するためのものである。
【００４１】
ここで、ベクトルデータ抽出部２から得られたベクトルのデータに含まれるベクトルの始点P1および終点P2のデータから、この２点で張られる部分直線の方程式は、以下の式（２）で得ることができる。
【００４２】
【数１】
【００４３】
ただし、ｙは、min(y1,y2) <= y <= max(y1,y2)を満たす必要がある。ここで、min(a,b), max(a,b)は、それぞれ、a,bの内の小さな値、大きな値を返す関数である。
【００４４】
式（２）を用いることで、対象点管理部４から通知された管理対象点情報に含まれる管理対象点のｙ座標値をもとに、管理対象点のｘ座標値を算出することができる。
【００４５】
対象点算出部５は、上記で算出した管理対象点のｘ座標と、対象点管理部４で得られたｙ座標とを合わせて、管理対象点座標(x,y)として、後述する対象点判定部６に送る。
【００４６】
なお、以上では、式（２）を用いて、直線方程式からｘ座標を算出する手法に関して説明したが、これに限定されるものではない。Bresenhamの線分計算アルゴリズムなど、他の手法を用いて算出することも可能である。また、Bresenhamの線分計算アルゴリズムを使用する場合、先述した対象点管理部４にて、開始点での初期ｘ座標を予め計算しておき、本対象点算出部５にて差分情報のみを算出することで、計算を高速化することも可能である。また、これら以外の手法を用いてｘ座標の算出を行っても構わない。
【００４７】
＜対象点判定部＞
次に、対象点判定部６について説明する。
対象点判定部６は、対象点算出部５で算出された処理対象点の座標値、および、入力となるベクトル群データを用いて、その両脇の点（ピクセル）が塗りつぶし領域かどうかを判定し、処理対象点の座標値とともに両脇の判定情報を出力する。
【００４８】
具体的には、対象点算出部５で算出された処理対象点Pの座標が(x,y)であったとすると、その両脇の点Pleft = (x-1,y), Pright = (x+1,y)の２点に対して、以下で説明する塗りつぶし領域判定を行う。
【００４９】
＜塗りつぶし領域判定＞
塗りつぶし領域判定について説明する。塗りつぶし領域判定は、対象点が所定の規則に従って、塗りつぶし領域であるのか、そうでないのかを判定するものである。以降、塗りつぶし規則として、前述したnon-zero fillルールを例として説明する。
【００５０】
図１３に、塗りつぶし領域判定のフローチャートを示す。
ステップＳ４０１で、まず、カウンター値の初期化（cnt = 0）を行う。
ステップＳ４０２では、調査対象となるベクトル番号を初期化する（i = 0）。
ステップＳ４０３では、調査ベクトル情報の取得を行う。現在のベクトル番号iを用いて、調査ベクトルV(i)のデータを取得する。
ステップＳ４０４では、対象点が調査ベクトルV(i)に含まれるかどうかの判定を行う。判定方法としては、例えば、ベクトルV(i)によって貼られる部分直線に対象点の座標が含まれているか調べればよい。その他の手法を用いて判定しても構わない。含まれている場合には、対象点は塗りつぶし領域と判定され、ステップＳ４１５に進む。含まれていない場合には、Ｓ４０５へ進む。
【００５１】
ステップＳ４０５では、対象点が調査ベクトルに対して上にあるかどうかの判定を行う。上にある場合には、ステップＳ４０６へ進む。そうでない場合には、ステップＳ４０８へ進む。
【００５２】
ステップＳ４０６では、対象点に対して、調査ベクトルが左から右に変化するかどうかを判別し、変化する場合には、ステップＳ４１０へ、そうでない場合には、ステップＳ４０７へ進む。
【００５３】
ステップＳ４０７では、調査ベクトルが右から左に変化するかどうかを判別し、変化する場合には、ステップＳ４１１へ、そうでない場合には、ステップＳ４１２へ進む。
【００５４】
ステップＳ４０８では、対象点に対して、調査ベクトルが右から左に変化するかどうかを判別し、変化する場合には、ステップＳ４１０へ、そうでない場合には、ステップＳ４０９へ進む。
【００５５】
ステップＳ４０９では、調査ベクトルが左から右に変化するかどうかを判別し、変化する場合には、ステップＳ４１１へ、そうでない場合には、ステップＳ４１２へ進む。
【００５６】
ステップＳ４１０では、カウンターの値を１つ増加させる（cnt = cnt+1）。
ステップＳ４１１では、カウンターの値を１つ減少させる（cnt = cnt-1）。
ステップＳ４１２では、全てのベクトルに関して、以上の調査が終了したかの判定を行い、終了していない場合にはＳ４１３へ、終了した場合には、Ｓ４１４へ進む。
ステップＳ４１３では、調査ベクトル番号の更新を行い（i = i+1）、ステップＳ４０３へ戻る。
ステップＳ４１４では、カウンター値（cnt）から塗りつぶし判定を行う。具体的には、カウンター値が非ゼロならば、塗りつぶし領域として判定し、そうでない場合は、塗りつぶし領域ではないと判定する。
【００５７】
ステップＳ４１５では、以上で判定した塗りつぶし領域か否かの判定結果を通知して終了する。
以上は、non-zero fillルールにおける塗りつぶし判定処理の一例である。この例では、対象点の位置に立って、ベクトルデータ群から構成される多角形を各ベクトルデータ毎に順次眺めていって、自分の体が１回転するかどうかを調べている。１回転する部分では、上記のカウンター値が非ゼロ値となり、塗りつぶし領域として判定される。
【００５８】
なお、以上で説明した判定手法はあくまでも一例であり、これに限定されるものではない。対象点を通る直線を引いて、それがベクトルデータ群と何度横切るかを調べる方法など、これ以外の判定方法を用いることができる。
【００５９】
また、以上では、non-zero fillルールを例として説明したが、塗りつぶし規則はこれに限定されるものではない。Even-odd fillルールやその他の規則など使用することが可能である。規則が変わった場合には、塗りつぶし可否の判定方法も別途変わるが、それに対しても、上記に準じる方法でも、それ以外の方法でも用いることが可能である。
【００６０】
＜両脇点の判定結果の出力＞
対象点判定部６は、以上で説明した「塗りつぶし領域判定」を用いて、対象点の両脇の点Pleft = (x-1,y), Pright = (x+1,y)の２点に対する塗りつぶし判定結果が得られた。この結果を対象点座標情報とともに出力する。
【００６１】
＜塗りつぶし情報算出部＞
次に、塗りつぶし情報算出部７について説明する。
塗りつぶし情報算出部７は、対象点判定部６から得られた処理対象点の座標値、および、その両脇の点（ピクセル）の塗りつぶし判定情報をもとに、対象点がそのスキャンラインにおいて、塗りつぶしに関与する点であるかどうかの判定を行い、関与する点であった場合には、その情報を生成するためのものである。
【００６２】
ここで、スキャンラインとは、対象点が含まれる行、つまり対象点座標が(x1,y1)であった場合、y=y1で示される行であると定義する。
＜スキャンライン毎の図形描画処理＞
ここで、まず、スキャンライン毎の図形描画処理に関して説明しておく。スキャンライン毎の図形描画処理とは、描画をスキャンライン単位の処理として、スキャンライン毎に、図形の塗りつぶし領域を複数のラインの描画で行う処理である。
【００６３】
例えば、図１４のような多角形図形があったとする。この描画を考えた場合、図１５のように、スキャンライン毎のライン描画処理に分割して描画することが可能である。図１５は、説明のため、多少誇張して描いているし、各ラインの間も説明のために便宜的に空けてあるが、実際にはこれらは、ピクセル単位の精度で描かれるものである。
【００６４】
ここで、図１６に示されるあるｙ座標の１スキャンライン部分を考えてみる。すると、多角形図形の描画処理は、複数のラインの描画（図１６の場合、２つのラインの描画）処理に置き換えられることが分かる。ラインの描画には、ラインの描画開始点と終了点のみあれば十分であるため、つまり、図１６における点P1,P2,P3,P4のみの情報があれば、図形の描画が可能であることが分かる。
【００６５】
ここで、図１６のP1,P3は、ラインの描画開始点であるため、以降、ラインＩＮ点と呼ぶ。また、P2,P4は、ラインの描画終了点であるため、以降、ラインＯＵＴ点と呼ぶ。
【００６６】
スキャンライン単位での図形描画を考えた場合、このラインＩＮ点とラインＯＵＴ点の算出を行えば良いと言える。
＜両脇点の判定結果からの対象点のラインＩＮ点・ラインＯＵＴ点判定＞
対象点判定部６で判定された対象点(x,y)の両脇の点Pleft = (x-1,y), Pright = (x+1,y)の２点に対する塗りつぶし判定結果を用いて、対象点がラインＩＮ点であるか、ラインＯＵＴ点であるか、それ以外か、の判定を行う。
【００６７】
両脇の結果は以下の４通りとなる。
（１） 両脇とも偽。つまり、（空欄）※（空欄）
（２） 左が真、右が偽。つまり、（塗り）※（空欄）
（３） 左が偽、右が真。つまり、（空欄）※（塗り）
（４） 両脇とも真。つまり、（塗り）※（塗り）
ここで、※は、該当点(x,y)を示す。また、（空欄）は塗りつぶさない領域、（塗り）は塗りつぶし領域を示す。
今、多角形図形の塗りつぶし処理を対象点が含まれるスキャンライン単位で考える。
（１）の場合、両脇（Pleft,Pright双方）が塗りつぶさない領域であるため、対象点※は、そのラインでの塗りつぶしに関与しない点である。つまり、ラインＩＮ点でもラインＯＵＴ点でもない。
【００６８】
（２）の場合、対象点※の左側（Pleft）が塗りつぶし領域で、右側（Pright）が塗りつぶさない領域ということで、対象点※は、そのラインにおける塗りつぶし領域の終了点、すなわちラインＯＵＴ点とみなすことができる。つまり、対象点※の左側に存在するどこかの点から塗りつぶし領域が始まり、対象点※が塗りつぶし領域の終了位置となる訳である。
【００６９】
（３）の場合、対象点※の左側（Pleft）が塗りつぶさない領域で、右側（Pright）が塗りつぶす領域ということで、対象点※は、そのラインにおける塗りつぶし領域の開始点、すなわちラインＩＮ点とみなすことができる。つまり、対象点※から塗りつぶし領域が始まり、対象点※の右側に存在するどこかの点が塗りつぶし領域の終了位置となる訳である。
【００７０】
（４）の場合、対象点※は、両脇（Pleft,Pright双方）が塗りつぶし領域であることから、対象点※は、塗りつぶし領域に含まれる点であるとみなすことができる。つまり、対象点※の左側に存在するどこかの点から塗りつぶし領域が始まり、対象点※の右側に存在するどこかの点が塗りつぶし領域の終了位置となり、ラインＩＮ点でもラインＯＵＴ点でもない点であると言える。
【００７１】
＜算出した塗りつぶし情報の出力＞
以上で説明した通り、塗りつぶし情報算出部７では、対象点の塗りつぶし情報、つまり、対象点（座標(x1,y1)）があるスキャンライン（y=y1であるスキャンライン）において（１）ラインＩＮ点、（２）ラインＯＵＴ点、（３）どちらでもない、という情報が得られる。これを後述する塗りつぶし情報登録部８に出力する。
【００７２】
＜塗りつぶし情報登録部＞
次に、塗りつぶし情報登録部８について説明する。
塗りつぶし情報登録部８は、塗りつぶし情報算出部７で得られた処理対象点の塗りつぶし情報を塗りつぶし情報記憶領域９に登録するためのものである。
＜塗りつぶし情報記憶領域の説明＞
ここで、塗りつぶし情報記憶領域９は塗りつぶし情報を保持するための任意の記憶手段である。例えば、本実施例を実現する装置が保持している内部メモリなどで構成される。
【００７３】
ただし、これに限定されるものではなく、塗りつぶし情報を保持することができるものであれば、任意の手段を用いることが可能である。また、塗りつぶし情報記憶領域９は、本実施例を実現する装置の内部に存在することが限定されるものではなく、脱着可能なメモリ装置（ＵＳＢメモリ機器、ＳＤメモリカードなど）や磁気記憶メディア（ＣＤ−Ｒ，ＤＶＤ−Ｒなど）、任意の通信手段（有線ＬＡＮ、無線ＬＡＮ、Ｗ−ＣＤＭＡなどの携帯電話を用いた通信など）を通した先にある記憶装置（ＮＡＳ装置、他の機器に内蔵されたＨＤＤなど）などでも構わない。
【００７４】
塗りつぶし情報記憶領域９に登録する塗りつぶし情報としては、典型的には、対象点座標、それが（１）ラインＩＮ点（２）ラインＯＵＴ点（３）そちらでもない、のどれに相当するか、である。ただし、これに限定されるものではなく、最低限これを含む任意の情報を登録するようにして構わない。
【００７５】
塗りつぶし情報記憶領域９での記憶手法は様々な手法が考えられる。ここでは、以下でその一手法に関して説明するが、これはあくまでも一例であり、これに限定されるものではない。
【００７６】
図１７は塗りつぶし情報記憶領域９での記憶手法の一例を示す。図１７の場合、各スキャンラインに対して、ラインＩＮ点とラインＯＵＴ点の２つをそれぞれ記憶可能なスタック（可変領域）を用意し、それを全スキャンライン分（１０８０ライン分）用意する例を示している。
【００７７】
全スキャンライン分とは、最終的に描画したい領域のスキャンライン総数を示す。例えば、フルハイビジョンの描画領域の場合、解像度は１９２０×１０８０となるので、１０８０ライン分ということになる。
【００７８】
スタックには、それぞれラインＩＮ点とラインＯＵＴ点と判定された点のｘ座標が保存される。図１７で、xi##(n), xo##(n)は、それぞれ、保存されている、スキャンライン##でのラインＩＮ点、ラインＯＵＴ点と判定された点のｘ座標を示している。
【００７９】
＜塗りつぶし情報登録部の動作＞
例えば、塗りつぶし情報算出部７からスキャンライン番号が１０７８の対象点（対象点座標が(xs,1078)であるような点）に対して、ラインＩＮであるとの塗りつぶし情報を得た場合、塗りつぶし情報登録部８では、その情報を塗りつぶし情報記憶領域９に登録する。この際、図１７の例では、スキャンライン番号が１０７８のラインＩＮ点のスタックには、xi1078(n)までのn+1個の情報が既に登録されているため、この末尾のn+2番目の情報として、対象点のｘ座標であるxsの値を登録する。
【００８０】
なお、以上では、登録方法の一例を示したが、これに限定されるものではない。あくまでも実施の一形態であり、これ以外の登録方法でも構わない。例えば、上記では末尾に追加する例を示したが、先頭に追加してもよいし、任意の位置に任意の条件（例えば座標の昇順など）で登録を行っても構わない。
【００８１】
＜描画領域算出部＞
次に、描画領域算出部１０について説明する。
描画領域算出部１０は、ベクトルデータ抽出部２から得られる処理対象ベクトルのデータをもととして、図形描画を行うための領域情報を算出するためのものである。
【００８２】
例えば、描画した図形を表示する画面の範囲が１９２０×１０８０の解像度の場合、描画領域として、最大で１９２０×１０８０の領域が必要となる。しかし、通常の場合、実際に多角形図形が存在する領域は、１９２０×１０８０の領域の内の一部の領域である。例えば、図１８の例では、１９２０×１０８０の領域の中央部分にのみ図形が存在している。この場合、図１９に示すように、図形を包含する最小矩形領域（座標(x0,y0)から、高さh、幅wの領域）の部分のみ図形が存在しているため、この矩形領域部分のみを図形の描画領域とすればよい。このようにすることで、画面全体を描画領域とするよりも描画領域を限定することが可能となり、描画速度の向上が見込まれる。
【００８３】
描画領域算出部１０は、このような目的のために存在し、ベクトルデータ抽出部２から得られる処理対象ベクトルのデータが含まれる最小矩形領域の情報を算出し、それを基として、図形描画領域情報の更新を行う。
【００８４】
本実施の形態の以上で説明してきたように、垂直方向（ｙ軸方向）を基準とした場合、図形描画は、ｙ軸方向のスキャンライン単位で行うため、図形の含まれる最小矩形情報のうち、ｙ軸方向のデータのみが重要となる。すなわち、矩形領域のｙ軸方向の下限値（図１９におけるｙ０）と矩形領域のｙ軸方向の上限値（図１９におけるｙ０＋ｈ）の値のみが重要である訳である。そこで、描画領域算出部１０では、この下限値（以降y_minと呼ぶ）と上限値（以降y_maxと呼ぶ）を算出する（図２０）。
【００８５】
算出のフローチャートを図２１に示す。ステップＳ５０１で、まず、y_min, y_maxの初期値の設定を行う。次に、ステップＳ５０２で、ベクトルデータ抽出部２から得られたベクトルデータの取得を行う。次に、ステップＳ５０３で、ベクトルの始点のｙ座標をy0にセットする。ステップＳ５０４で、y_min > y0かどうかの判定を行い、真の場合は、ステップ５０５へ行き、ステップＳ５０５にてy_minにy0の値を設定してステップＳ５０６へ、偽の場合は、そのままＳ５０６へ進む。同様にステップＳ５０６にて、y_max < y0の判定を行い、真の場合は、ステップＳ５０７にてy_maxにy0を設定してステップＳ５０８へ、偽の場合はそのままステップＳ５０８へ進む。ステップＳ５０８にて、全てのベクトルに関して処理が終了したかの判定を行い、偽の場合は、ステップＳ５０２へ戻る。真の場合は、処理を終了する。これにより、y_min, y_maxの値を得ることができる。
【００８６】
なお、以上で説明したのは、あくまでも実施の一形態であり、これに限定されるものではない。他の手法を用いて描画図形のｙ座標の上限値・下限値を算出してもよい。
【００８７】
また、以上では、ｙ座標のみを算出しているが、これに限定されるものではなく、同様の手段にて、ｘ座標の情報を算出して、合わせて出力してもよい。また、上限値・下限値として出力するのではなく、下限値と領域の高さなど、情報量として同等の情報であれば、表現形態は問わない。
【００８８】
＜描画領域補正部＞
次に、描画領域補正部１１について説明する。
描画領域補正部１１は、描画領域算出部１０から得られる描画領域情報を補正するためのものである。入力となるベクトルデータ群によって構成される図形の全体が必ずしも描画領域に入っているとは限らない。
【００８９】
図２２にこの例を示す。図２２は、図形の一部が描画領域外にある例である。この場合、y_min < 0となっているため、図形のこの部分は描画されない。この際には、y_min = 0に補正する必要がある。描画領域補正部１１では、このような補正を行う。
【００９０】
具体的には、y_min < 0の場合に、y_min = 0とする。また、y_max >= 描画領域のｙ座標の上限（図２２の例の場合には、1080）の場合には、y_max = 描画領域のｙ座標の上限値と補正する。
【００９１】
＜描画データ補正部＞
次に、描画データ補正部１２について説明する。
描画データ補正部１２は、ベクトルデータ群管理部１からのベクトルデータ群の処理終了の通知を受けて、塗りつぶし情報記憶領域９に記憶された描画のための情報を読み込み、これを後述する描画部１３で描画するために適切なデータとなるように補正するためのものである。
【００９２】
図１７に示されるように、ベクトルデータ群管理部１からのベクトルデータ群の処理終了の通知を受けた時点では、描画したい図形を構成する全てのベクトルに含まれる点（ピクセル）に対して、ラインＩＮ点、ラインＯＵＴ点の塗りつぶし情報が得られている。
【００９３】
しかし、これらは、上記塗りつぶし情報登録部８で説明した手法を用いた場合、ベクトルの処理順にスタックの先頭から積まれていくため、この出現順序は様々である。これは、ラインの描画コストを考えた場合効率が悪い。
【００９４】
また、描画したい図形の一部が描画領域よりも外にある場合には、ラインＩＮ点あるいはラインＯＵＴ点が描画領域の外となることがある（図２３）。この場合、ラインＩＮ点から描画領域の左端までのラインの描画は実際の描画領域に反映されないため無駄である。これは、処理装置の速度の低下を招く。
【００９５】
また、図形の形状が複雑な場合、同じラインＩＮ点・ＯＵＴ点を複数のベクトルが通過することがあるため、データの重複が起こりうる。この場合、同じ直線を複数回描画することは無駄である。また、ラインＩＮ点・ＯＵＴ点の対で表現される直線の領域が交差することがある。この場合は、複数の直線を１つにまとめることが可能である。こうすることによって、直線の描画回数を減らすことができて速度上昇に繋がる。
【００９６】
描画データ補正部１２は、これらの問題を解消するためのもので、
１．ラインＩＮ点・ラインＯＵＴ点を昇順（あるいは降順）にソートする
２．描画範囲外のデータを描画範囲端に修正する。具体的には、ラインＩＮ点、ラインＯＵＴ点のｘ座標が負値の場合は０に、描画幅値を超えている場合には、描画幅値とする。好ましくは、対応するラインＩＮ点、ラインＯＵＴ点が両方とも描画範囲外であったならば、不要データとしてスタックから削除する。
【００９７】
３．冗長なラインＩＮ点、ラインＯＵＴ点データを削除する。具体的には、ラインＩＮ点、ラインＯＵＴ点データに重複がある場合には、それを削除する。また、好ましくは、対となるラインＩＮ点、ラインＯＵＴ点データによって構成される直線に包含関係のある複数の直線となるデータが存在した場合、包含される直線を構成するデータを削除する。
【００９８】
以上の処理により、補正されたデータでは、先頭から同じ位置にあるラインＩＮ点・ラインＯＵＴ点を対応点として、直線（ライン）描画を行っていくだけで、対象スキャンラインにおいて、描画したい図形のうち描画範囲内にある部分を構成する部分が、画面左側から順に描かれて行くことになる。
【００９９】
＜描画部＞
最後に、描画部１３について説明する。
描画部１３は、描画データ補正部１２から得られた描画データデータをスキャンライン毎に直線（ライン）描画によって描画していくものである。この際、描画領域補正部１１から得られた描画範囲（具体的には、描画開始スキャンラインと描画終了スキャンライン）の情報を用いて、描画処理範囲を限定することで、描画の高速化を行う。
【０１００】
図２４に描画部１３の処理フローチャートを示す。
スキャンライン番号mのn番目のラインＩＮデータをline_in(m,n)、ラインＯＵＴデータをline_out(m,n)とする。また、スキャンライン番号mに含まれるデータの要素数をn_elmtとする。また、描画領域補正部１１から得られた描画開始スキャンライン番号をm0、終了スキャンライン番号をm1とする。
【０１０１】
まず、ステップＳ６０１で、描画対象スキャンライン番号として、m0をセットする。次に、ステップＳ６０２で、処理対象データ番号nの初期化と、要素数n_elmtの算出を行う。次に、ステップＳ６０３で、L0 = line_in(m,n), L1 = line_out(m,n)の値の取得を行う。次に、ステップＳ６０４で、L0, L1で形成されるライン（直線）の実際の描画を行う。これにより、画面にL0,L1を両端とする直線が描画される。そして、ステップＳ６０５で、全ての要素について終了したかの判定を行い、終了していない場合には、ステップＳ６０６にて、処理点の更新（n=n+1）を行い、ステップＳ６０３に戻る。終了した場合には、ステップＳ６０７へ進む。ステップＳ６０７では、描画終了スキャンラインm1までの処理が完了したかの判定を行い、終了していない場合には、ステップＳ６０８にて、処理スキャンラインの更新（m=m+1）を行い、ステップＳ６０２へ戻る。終了している場合には、処理を終える。
【０１０２】
なお、ラインの実際の描画は、ライン描画専用のＨＷを用いてもよいし、汎用のグラフィックス処理ＬＳＩ（ＧＰＵ、Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）などを用いてもよいし、その他の手段を用いてソフトウェア的に処理しても構わない。
【０１０３】
以上により、図１５で示されたようにスキャンライン単位の描画が逐次行われ、最終的に、図１４で示されるような多角形図形の描画が完了する。
なお、以上で示した手法はあくまでも実施の一形態であり、これに限定されるものではない。
＜第１の実施形態による効果＞
以上で説明した本発明の第１の実施形態によれば、入力されるベクトルデータ群によって構成される図形の複雑さに依存して描画処理が複雑になることはない。例えば、三角形分割を用いた描画手法（非特許文献２参照）では、入力された図形に複雑な自己交差があった場合、これを１つの閉ループで構成される単純多角形群に分割して処理する必要がある。このため、図形の複雑さに依存して、分割処理が非常に多数回適用されることになり、以降の処理が複雑となる。これは、不具合（バグ）の大きな要因の１つとなりうる。入力図形が非常に複雑となった場合、予期しない形状の入力がありえ、この際に上記分割処理が上手く動作しない可能性が出てくるからである。つまり、図形の複雑さに比例して処理量が増加するような手法は安定度に欠けるといえる。一方、本発明の第１の実施形態によれば、処理はベクトルデータ単位で行っており、この処理内容は、図形の形状に依らない。このため、図形の複雑さに比例して処理量が増加するようなことはない。このため、本発明の第１の実施形態による手法は、非常に安定した手法と言うことができる。
【０１０４】
また、本発明の第１の実施形態による手法は、描画処理が実行される前段階に、ラインＩＮ、ラインＯＵＴのデータ群のみを記憶すれば良い。これは、非常に小さなデータ量しか必要としないものであり、メモリの使用量は少ない。一方、三角形分割の手法は、描画処理前に、様々な前処理を必要とする（詳細に関しては、非特許文献２などを参照のこと）ため、非常に多くの中間データを記憶しておく必要がある。描画処理に関しても、三角形単位で行うため、ライン単位である本発明の第１の実施形態による手法よりもメモリ使用量が多くなる。また、ステンシルバッファを用いた手法（非特許文献３など）は、描画処理のためにステンシルバッファという特殊なメモリ領域を必要とする。これは、基本的には、描画領域と同等の領域が必要となる。また、描画処理自体も画面単位で行うため、非常に多くのメモリを使用する必要がある。本発明の第１の実施形態による手法は、メモリ使用量の観点から、これらの手法に対するメリットが大きい。
【０１０５】
また、本発明の第１の実施形態による手法は、描画処理としてライン描画が可能な装置を用意すれば良いため、複雑な専用回路を必要とせず、簡単な回路または、汎用のグラフィックスＬＳＩを用いて実現可能であるという観点から、使用リソースに対するメリットも大きい。
【０１０６】
さらに、本発明の第１の実施形態による手法は、上述してきたような構成を取ることにより、ポイントベースの手法や従来のスキャンラインベースの手法と比べて、高速に図形描画が可能である。
【０１０７】
以上より、本発明の第１の実施形態による手法によれば、従来技術に存在していた少リソースでの使用が困難であったり、安定性に欠けたり、高速性に欠けたりする問題点を解消し、少ないリソースやメモリしか使用不可能な環境下にて、高速かつ安定的に動作することが可能な図形描画装置、および、手法を提供することが可能となる。
【０１０８】
［第１の実施形態の変形例１］
図２５に本発明の第１の実施形態の変形例１に係る図形描画装置の全体構成図を示す。本発明の第１の実施形態の変形例１は、第１の実施例に、ベクトルデータ群補正部１４が追加された形となっている。
【０１０９】
＜ベクトルデータ群補正部＞
ベクトルデータ群補正部１４について説明する。ベクトルデータ群補正部１４は、入力されたベクトルデータ群を補正するためのものである。
ベクトルデータ群に、ゼロベクトルのデータが含まれていた場合、このデータは除去することが可能である。
また、連続する２つ以上のベクトルの方向が同じ場合、つまり、
V(n) / |V(n)| = V(n+1) / |V(n+1)| = ・・・ = V(n+m) / |V(n+m)|
(m = 1, 2, ・・・)
という関係が成り立つ場合、これらのベクトルは、１つのベクトルとしてマージすることが可能となる。つまり、V(n)の終点を上記の関係におけるV(n+m)の終点に置き換え、V(n+1),・・・,V(n+m)のデータを削除することが可能である。
【０１１０】
さらに、連続するベクトルが逆の方向を持っている場合も同様にマージ可能であり、連続するベクトルで貼られるベクトルの新たな両端点を算出し、V(n)をそのベクトルに置き換え、マージされた残りのベクトルは削除することが可能である。
【０１１１】
ベクトルデータ群補正部１４は、このような冗長な表現となっているベクトル群データの補正を行う。この補正により、ベクトルデータ群の総数を削減することが可能となり、以降の処理のスピードアップに繋がる。
【０１１２】
なお、以上では、冗長な表現の一例を示したが、これに限定されるものではない。ベクトルデータ群によって構成される多角形図形の形状を変えることなく、ベクトルデータ群の総数を削減することが可能な変形は、全て用いることが可能である。
【０１１３】
本発明の第１の実施形態の変形例１の以降の処理に関しては、第１の実施形態において、入力であるベクトルデータ群として説明した部分を適宜、ベクトルデータ群補正部１４によって補正された後のベクトルデータ群と読み替えれば同様である。
【０１１４】
以上で説明した以外は、第１の実施形態と同様の動作である。
［第１の実施形態の変形例２］
図２６は、本発明の第１の実施形態の変形例２に係る図形描画装置の全体構成図である。
変形例２に係る図形描画装置は、第１の実施形態の図形描画装置における描画データ補正部１２の代わりに、塗りつぶし情報記憶領域９に記憶されているデータを用いて、塗りつぶし情報登録部８で得られた登録情報を逐次補正しながら、塗りつぶし情報記憶領域９のデータを更新するための新たな描画データ補正部１５が追加されている。また、第１の実施形態の図形描画装置における描画データ補正部１２に接続されていた部分は、直接描画部１３に接続されている。
【０１１５】
描画データ補正部１５の動作は、基本的には、第１の実施形態の図形描画装置における描画データ補正部１２と同様である。異なる部分は、第１の実施形態の図形描画装置における描画データ補正部１２では、塗りつぶし情報記憶領域９に蓄積されているデータに対して後から補正を行ったのに対し、描画データ補正部１５では、塗りつぶし情報記憶領域９のデータを参照しつつ、塗りつぶし情報登録部８で得られた登録情報を補正しながら塗りつぶし情報記憶領域９に蓄積していく、つまり、登録データを逐次補正しながら塗りつぶし情報記憶領域９に保存して行く（同時に、塗りつぶし情報記憶領域９に既に蓄積されたデータも更新される）という点である。
【０１１６】
描画部１３は、ベクトルデータ群管理部１からのベクトルデータ群の処理終了の通知を受けて処理を開始するという点以外は、第１の実施形態と全く同様である。
［第１の実施形態の変形例３］
図２７は、本発明の第１の実施形態の変形例３に係る図形描画装置の全体構成図である。
第１の実施形態との違いは、描画データ補正部１２が、塗りつぶし情報記憶領域９と描画部１３の間の存在するのではなく、描画部１３にのみ接続されているという点である。
【０１１７】
この場合、描画部１３での、各スキャンラインにおける処理の前処理として、描画データ補正部１２を呼び出し、描画データ補正部１２にて対象スキャンラインのデータの補正を行い、この結果を再び描画部１３で受け取り、処理を続ける。具体的には、図２４におけるステップＳ６０３の処理の前に、上記の処理を入れればよい。描画データ補正部１２にて行う補正手法は、第１の実施形態での説明と全く同様である。
【０１１８】
第１の実施形態との違いは、第１の実施形態では、「全てのデータの補正」→「全てのデータの描画」というシーケンシャルな処理であったのに対し、本変形例は、スキャンライン毎に、「データの補正」→「描画」を繰り返すという点である。
【０１１９】
［第１の実施形態の変形例４］
図２８は、本発明の第１の実施形態の変形例４に係る図形描画装置の全体構成図である。
図１で表される第１の実施形態の塗りつぶし情報算出部７と塗りつぶし情報登録部８の間に、新たに、塗りつぶし情報補正部１６が追加される形となっている。
塗りつぶし情報補正部１６は、塗りつぶし情報算出部７で得られた処理対象点の塗りつぶし情報を補正し、塗りつぶし情報登録部８に渡すためのものである。
具体的には、塗りつぶし情報補正部１６では、ラインＩＮ点・ラインＯＵＴ点の位置の補正を行う。例えば、あるベクトルに対して、図２９のようなラインＯＵＴ点が得られたとする。この場合、図３０に示したように、ラインＯＵＴ点までをそのスキャンラインにおける図形の塗りつぶし領域とするか、図３１に示したように、一つスキャンラインの上の点(n-1)におけるラインＯＵＴ点よりも一つ手前の点までを塗りつぶし領域にするか、などというような、複数の塗りつぶし手法が考えられる。
【０１２０】
これは、多角形図形を描画する際の、多角形の縁部分の描画のルールによって変化する。塗りつぶし情報補正部１６は、この描画ルールに従って、塗りつぶし情報算出部７で得られた処理対象点のラインＩＮ点・ラインＯＵＴ点の座標値の補正を行う。
【０１２１】
補正方法は描画ルールによって変化するが、図３０の例の場合、上下のスキャンラインの情報を用いて算出する。上下のどちらを使うかは、ベクトルの方向により決定する。
【０１２２】
塗りつぶし情報補正部１６は補正したラインＩＮ点、ラインＯＵＴ点のデータを塗りつぶし情報登録部８に渡し、塗りつぶし情報登録部８では、第１の実施形態のところで説明したのと同様に処理を継続する。
【０１２３】
なお、ここでは、補正方法の一例を示したが、これに限定されるものではない。描画ルールに合致するような任意の補正方法を用いて処理を行う。
以上の各実施形態やその変形例は、適宜組み合わせて実施することが可能である。
本願発明の実施例における処理をコンピュータで実行可能なプログラムで実現し、このプログラムをコンピュータで読みとり可能な記憶媒体として実現することも可能である。
【０１２４】
なお、本願発明における記憶媒体としては、磁気ディスク、フロッピー（登録商標）ディスク、ハードディスク、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＤＶＤ等）、光磁気ディスク（ＭＯ等）、半導体メモリ等、プログラムを記憶でき、かつコンピュータまたは組み込みシステムが読みとり可能な記憶媒体であれば、その記憶形式は何れの形態であってもよい。
【０１２５】
また、記憶媒体からコンピュータや組み込みシステムにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーションシステム）や、データベース管理ソフト、ネットワーク等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行してもよい。
【０１２６】
さらに、本願発明における記憶媒体は、コンピュータあるいは組み込みシステムと独立した媒体に限らず、ＬＡＮやインターネット等により伝達されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１２７】
また、記憶媒体は１つに限られず、複数の媒体から本実施形態における処理が実行される場合も、本発明における記憶媒体に含まれ、媒体の構成は何れの構成であってもよい。
【０１２８】
なお、本願発明におけるコンピュータまたは組み込みシステムは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するためのものであって、パソコン、マイコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であってもよい。
【０１２９】
また、本願発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本願発明の機能を実現することが可能な機器、装置を総称している。
【０１３０】
なお、本発明は、上記実施形態に限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。さらに、上記実施形態には種々の段階の発明は含まれており、開示される複数の構成要件における適宜な組み合わせにより、種々の発明が抽出され得る。例えば、実施形態に示される全構成要件からいくつかの構成要件が削除されても、発明が解決しようとする課題の欄で述べた課題（の少なくとも１つ）が解決でき、発明の効果の欄で述べられている効果（の少なくとも１つ）が得られる場合には、この構成要件が削除された構成が発明として抽出され得る。
【図面の簡単な説明】
【０１３１】
【図１】本発明の第１の実施形態に係る図形描画装置の構成例を概略的に示す図。
【図２】ベクトルデータ群を説明するための図。
【図３】図形描画に関して説明した図。
【図４】図形描画に関して説明した図。
【図５】多角形図形に関して説明した図。
【図６】閉じていない多角形図形に関して説明した図。
【図７】多角形図形に関して説明した図。
【図８】ベクトルデータ群管理部の処理フローを説明した図。
【図９】開始点・終了点算出部の処理フローを説明した図。
【図１０】開始点・終了点算出の様子を模式的に説明した図。
【図１１】連続するベクトルに共通する点が２重に処理される様子を説明した図。
【図１２】対象点管理部の処理フローを説明した図。
【図１３】塗りつぶし領域判定のフローチャート図。
【図１４】スキャンライン毎の図形描画処理を説明した図。
【図１５】スキャンライン毎の図形描画処理を説明した図。
【図１６】スキャンライン毎の図形描画処理を説明した図。
【図１７】塗りつぶし情報記憶領域を説明した図。
【図１８】描画領域に関して説明した図。
【図１９】描画領域に関して説明した図。
【図２０】描画領域に関して説明した図。
【図２１】描画領域算出のフローチャート図。
【図２２】描画領域の補正に関して説明した図。
【図２３】描画データの補正に関して説明した図。
【図２４】描画部の処理フローチャート図。
【図２５】本発明の第１の実施形態の変形例１に係る図形描画装置の構成例を概略的に示す図。
【図２６】本発明の第１の実施形態の変形例２に係る図形描画装置の構成例を概略的に示す図。
【図２７】本発明の第１の実施形態の変形例３に係る図形描画装置の構成例を概略的に示す図。
【図２８】本発明の第１の実施形態の変形例４に係る図形描画装置の構成例を概略的に示す図。
【図２９】塗りつぶし情報の補正に関して説明した図。
【図３０】塗りつぶし情報の補正に関して説明した図。
【図３１】塗りつぶし情報の補正に関して説明した図。
【符号の説明】
【０１３２】
１・・・ベクトルデータ群管理部
２・・・ベクトルデータ抽出部
３・・・開始点・終了点算出部
４・・・対象点管理部
５・・・対象点算出部
６・・・対象点判定部
７・・・塗りつぶし情報算出部
８・・・塗りつぶし情報登録部
９・・・塗りつぶし情報記憶領域
１０・・・描画領域算出部
１１・・・描画領域補正部
１２・・・描画データ補正部
１３・・・描画部
１４・・・ベクトルデータ群補正部
１５・・・描画データ補正部
１６・・・塗りつぶし情報補正部
【技術分野】
【０００１】
本発明は図形の描画装置、描画方法に関する。
【背景技術】
【０００２】
任意の多角形を描画する手法として様々な手法が開発されてきている。（１）ポイントベースの手法、（２）ラスターラインベースの手法、（３）トライアングルベースの手法、（４）ステンシルバッファベースの手法などである。
【０００３】
（１）は、描画領域に含まれる各点（ピクセル）に関して、描画の判定を行い、ポイント（ピクセル）単位で描画処理を行っていくものである。この際、描画処理の高速化のため、無駄な描画領域を削除したり、各点における描画判定を簡略化したりという様々な工夫が凝らされてきている。さらに、高速化のため、この機能をハードウェア化することも良く行われている。このハードウェア化された装置の１つとして、ラスタライザと呼ばれるものがある（例えば、非特許文献１を参照）。この手法は、シンプルな手法であるが故に非常に安定動作することが特徴であるが、各点毎に描画判定を行う必要があるため、非常に処理コストが大きいという問題点がある。このため、典型的には専用ハードウェア化されることがほとんどである。（２）は、（１）を改良したもので、各点毎、あるいは、それに相当する範囲で描画判定を行うところまでは似ているが、描画する際に、各点における描画部分をまとめ、これを描画したい画面のスキャンライン単位の線の描画に置き換えたものである。こうすることで、描画判定に関しては（１）と同様に処理コストが大きいが、描画処理のコストは小さくなるため、（１）よりも高速化が見込まれる。また、描画判定の部分は、高速なCPUを持つ処理系での処理や専用ハードウェア化などが必要とされるが、描画処理に関しては、汎用的なグラフィックスLSI（GPU）を用いることが可能である。なぜならば、グラフィックスLSIは、線、三角形を高速に描画する機能を持っているからである。このため、（１）よりも汎用性が上がっていると言える。（３）は、描画したい多角形を三角形群に分割し、三角形ベースで描画しようというものである（例えば、非特許文献２を参照）。これは、汎用のグラフィックスLSI、または、高速な三角形描画装置の使用を前提として高速化を図ろうという意図がある。（なぜならば、グラフィックスLSIは、線、三角形を高速に描画する機能を持っているからである。）このため、（１）、（２）の手法よりもより汎用性がある手法である。しかし、三角形分割のために複雑な処理が必要とされるため、この部分の安定性が問題となりうる。また、描画したい多角形が非常に複雑な形状を持っている場合には、三角形分割処理の計算コストが非常に大きくなるという問題もある。また、三角形群をグラフィックスLSIなどを用いて描画することを前提としているため、グラフィックスLSIに十分なリソースが無い場合、使用することができないという問題もある。多角形を三角形群に分割し、これをグラフィックスLSIに投入する必要があるため、比較的メモリなどの使用量が多くなるからである。（４）は、完全に汎用グラフィックスLSIの使用を前提とするもので、グラフィックスLSIの機能として存在しているステンシルバッファという機能を用いて多角形描画を実現するものである（例えば、非特許文献３）。これは、（１）〜（３）のどれよりも高速かつ安定的に多角形描画が可能な方法であるが、グラフィックスLSIの機能をフル活用するため、グラフィックスLSIの多くのリソースを必要とするという問題点が存在する。
【非特許文献１】Renate Kempf and Chris Frazier, “The OpenGL Processing Pipeline”, Chapter 2: Overview of Commands and Routines, OpenGL Reference Manual Second Edition, ISBN 0-201-46140-4, pp.8-16, 1997.
【非特許文献２】Ｍ.ドバーグ、Ｍ.ファン.クリベルド、M.オーバマーズ、O.シュワルツコップ, “コンピュータ・ジオメトリ”, ISBN 4-7649-0277-X, pp.55-75, 近代科学社, 2000.
【非特許文献３】Jackie Neider, Tom Davis, Mason Woo, “Drawing Filled, Concave Polygons Using the Stencil Buffer”, Chapter 13: Now That You Know, OpenGL Programming Guide, ISBN 0-201-63274-8, pp.398-399, 1993.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、上記のように、従来の様々な手法に存在していた安定動作、使用リソースの問題点を解消し、かつ、この条件下でなるべく高速動作が可能な図形描画を行う装置、および、手法を提供することを目的とする。
【０００５】
具体的には、グラフィックスLSIなどのハードウェアリソースの使用が困難な状況下で、なるべく安定動作が可能なシンプルな手法を用いて、なるべく高速化が可能な図形描画装置および手法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
この発明の図形描画装置は、入力となるベクトルデータ群を管理するベクトルデータ群管理手段と、前記ベクトルデータ群管理手段での管理情報に基づいて、入力となるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、前記ベクトルデータ抽出手段で抽出されたベクトルデータの処理順を算出する処理順序算出手段と、前記処理順序算出手段で算出された処理順序を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出するための塗りつぶし情報算出手段と、前記塗りつぶし情報算出手段によって得られた塗りつぶし情報を用いて、図形を描画するための描画手段を具備することを特徴とする。
【０００７】
また、この発明の図形描画方法は、入力となるベクトルデータ群に含まれる処理対象ベクトルの処理順序、データを管理するステップと、管理情報に基づいて、前記ベクトルデータ群から処理対象ベクトルのデータの抽出を行い、抽出されたベクトルデータの処理順の算出を行うステップと、算出された処理順序情報を用いて処理対象点の管理、及び対象ベクトルの処理の終了の通知を行うステップと、処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出するステップと、算出された塗りつぶし情報を用いて、図形の描画を行うステップを含むことを特徴とする。
【０００８】
更に、この発明の図形描画装置をコンピュータで機能させるプログラムは、入力となるベクトルデータ群に含まれる処理対象ベクトルの処理順序、データを管理する機能と、管理情報に基づいて、前記ベクトルデータ群から処理対象ベクトルのデータの抽出を行い、抽出されたベクトルデータの処理順の算出を行う機能と、算出された処理順序情報を用いて処理対象点の管理、及び対象ベクトルの処理の終了の通知を行う機能と、処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出する機能と、算出された塗りつぶし情報を用いて、図形の描画を行う機能を含むことを特徴とする。
【発明の効果】
【０００９】
本発明によれば、多角形図形の描画を低消費メモリで高速かつ安定的に行う装置、および、手法を提供することができる。
【発明を実施するための最良の形態】
【００１０】
以下、図面を参照しながら発明の実施の形態を説明する。
［第１の実施形態］
まず、本発明の第１の実施形態について説明する。
＜全体の構成＞
図１は、本発明の第１の実施形態に係る図形描画装置の全体構成図である。
本実施形態の図形描画装置は、入力されたベクトルデータ群を管理するためのベクトルデータ群管理部１と、ベクトルデータ群管理部１での管理情報に基づいて、入力されたベクトルデータ群から処理対象となるベクトルデータを取得するためのベクトルデータ抽出部２と、ベクトルデータ抽出部２で取得されたベクトルデータから、処理の開始点および終了点を算出するための開始点・終了点算出部３と、開始点・終了点算出部３で算出された開始点・終了点情報、または／および、塗りつぶし情報算出部７から得られる対象点の処理の終了の通知情報、を用いて処理対象点の決定を行ったり、ベクトルデータ群管理部１に対象ベクトルの処理の終了を通知したりするための対象点管理部４と、対象点管理部４で決定された処理対象点の情報をもとに、処理対象点のピクセル座標位置を算出するための対象点算出部５と、対象点算出部５で算出された処理対象点の座標位置の両脇のピクセルが塗りつぶし対象となるかどうかの判定を行うための対象点判定部６と、対象点判定部６での判定結果をもとに、対象点が、塗りつぶし開始点、塗りつぶし終了点、どちらでも無い点のいずれかであるかを判断するし、それを対象点の座標位置とともに所定の形式で塗りつぶし情報として算出するための塗りつぶし情報算出部７と、塗りつぶし情報算出部７で算出された塗りつぶし情報を塗りつぶし情報保存領域９に登録するための塗りつぶし情報登録部８と、ベクトルデータ抽出部２で取得されたベクトルデータをもとに、図形描画を行うために最小限必要な矩形領域の情報を算出・更新するための描画領域算出部１０と、描画領域算出部１０で算出された矩形領域を補正して、最終的に描画を行う領域を求めるための描画領域補正部１１と、塗りつぶし情報保存領域９に保存された塗りつぶし情報を描画するのに適正なデータとして補正するための描画データ補正部１２と、描画領域補正部１１で得られた描画領域情報、描画データ補正部１２で補正されたデータを用いて、図形を描画するための描画部１３から構成される。
【００１１】
＜ベクトルデータ群管理部＞
まず、ベクトルデータ群管理部１について説明する。
＜図形描画の説明＞
ここで、まず、本実施の形態で扱う図形描画について説明する。
本実施の形態で扱う図形描画とは、多角形を構成するベクトルデータ群、または、それに相当する点データ群で形成される入力データから、それで示される多角形で構成される図形を描画するものである。この際、所定の規則に従って、図形の内部の塗りつぶしを行う。
【００１２】
具体的には、図２に示されるような「ベクトル１」〜「ベクトル５」のような「（一筆書きで得られる）多角形」を構成するベクトルデータ群の入力があったとすると、図３，図４に示されるような図形を描画する。図３，図４の差は、多角形の内部の塗りつぶし規則の違いである。図３は、even-odd fillルールと呼ばれる規則に従って、多角形（この例の場合、星形）の内部を塗りつぶした例である。図４は、non-zero fillルールと呼ばれる規則に従って、同様の多角形を塗りつぶした例である。
【００１３】
ここで、even-odd fillルール、non-zero fillルールに関して簡単に説明する。Even-odd fillルールとは、領域（閉路）内部の任意の点から任意の方向に半直線を引き（rayを飛ばし）、その半直線を領域のエッジがまたぐ方向に応じてカウンタを増減させた結果、カウンタが奇数になる領域は塗りつぶし、偶数になる領域は塗りつぶさないという規則である。Non-zero fillルールは、同様のカウンタ増減の結果、カウンタが0でない部分は塗りつぶすという規則である。詳しくは、”www.w3.org/TR/SVG/”に説明されているので、そちらを参照して頂きたい。
【００１４】
なお、塗りつぶし規則の例として、even-odd fillルール、non-zero fillルールの２つに関して説明したが、これはあくまでも例であり、これに限定されるものではない。任意の塗りつぶし規則を用いることができる。
【００１５】
＜ベクトルデータ群の説明＞
次に、図形描画の入力となるベクトルデータ群、または、それに相当する点データ群について説明する。
本実施の形態で扱うベクトルデータ群とは、2次元（あるいは3次元）の座標値を持つ2つの点データP1（始点）,P2（終点）で構成されるベクトルデータV(n) = P2(n) − P1(n)の集合である。ここで、n= 1, ・・・, Nであり、Nはベクトルデータ群を構成するベクトルの個数を示している。また、V(n)は、n番目のベクトルデータ、P1(n),P2(n)は、n番目のベクトルを構成する始点、終点の点データである。本発明で扱うベクトルデータ群では、互いに連続するベクトル同士は、その端点を共有する。つまり、P1(n) = P2(n-1)の関係が成り立つ。このようにして得られるベクトルデータ群は、一筆書きによって得られる多角形図形を形成する（図５参照）。図５は、N=3の例であり、図形として、三角形が形成されている。
【００１６】
P2(N) = P1(1)でない場合には、形成される図形は閉じていないが、この場合、P1(N+1)=P2(N), P2(N+1)=P1(1)で表されるN+1番目の点が仮想的に存在するとして、閉図形として扱う（図６参照）。図６の場合、仮想的なV(4)があるとして、四角形の閉図形として扱う。
【００１７】
また、ベクトルデータ群によって形成される図形は、一般多角形で構成される任意の形状を取ることが可能で、凸形状だけではなく凹形状や自己交差形状を含んでも構わない（図７参照）。
【００１８】
また、点データ群も、ベクトルデータ群と同様に扱うことができる。今、点データ群が、P(n), n = 1 ・・・ Nで表されているとすると、
V(n) = P(n+1) − P(n) n = 1, ・・・, N-1 （１）
【００１９】
として得られるV(n)は、ベクトルデータ群となるからである。入力が点データ群であった場合、上記のような変換を行うことで、ベクトルデータ群として扱うことが可能である。
【００２０】
＜ベクトルデータ群管理部の説明＞
ベクトルデータ群管理部１は、上記で説明したような図形描画のための入力として得られるベクトルデータ群を管理するためのものである。
具体的には、ベクトルデータ群管理部１は、入力として得られるベクトルデータ群の中で、現在の処理対象となるベクトルデータがどれであるかの管理を行う。
処理開始時は、ベクトルデータ群の中の1番目のベクトルデータが処理対象として選択される。また、以降は、後述する対象点管理部４から、処理対象となる点データの処理の終了通知を受け、処理対象となるベクトルデータを２番目、３番目、・・・と逐次更新していく。また、処理対象となるベクトルデータが無くなったならば、処理完了の通知を後述する描画部１２に送る。
【００２１】
以下に詳細なベクトルデータ群管理部１の処理フローを示す（図８）。まず、処理対象ベクトル番号ｎを１にセットする（Ｓ１０１）。次に、管理対象となるベクトルデータをV(n)とする（Ｓ１０２）。後述するベクトルデータ抽出部２に処理対象となるベクトルデータV(n)を通知する（Ｓ１０３）。次に、後述する対象点管理部４からの終了通知を待ち、終了通知を受けたら、次のステップに進む（Ｓ１０４）。次にステップＳ１０５にて、全てのベクトルデータを処理したかの判定を行い、処理していない場合には、ステップＳ１０６に、処理した場合には、ステップＳ１０７に進む。ステップＳ１０６では、処理対象ベクトル番号ｎの更新を行う。典型的には、ｎを１つインクリメントし、ステップＳ１０２へ戻る。なお、更新は必ずしも連続的に行われる必要はない。何らかの規則に従って、所定のベクトルデータを管理対象とすることもできる。ステップＳ１０７では、後述する描画部１２に処理完了通知を送る。以上が、典型的な処理フローの内容である。
【００２２】
ただし、ベクトルデータ群管理部１は以降の処理で処理対象となるベクトルデータV(n)を管理するものであって、以上の処理フローは一例に過ぎない。任意の選択手法を用いて選択したV(n)を処理対象とすることができる。
【００２３】
＜ベクトルデータ抽出部＞
次に、ベクトルデータ抽出部２について説明する。
ベクトルデータ抽出部２は、ベクトルデータ群管理部１から通知された処理対象のベクトル番号情報を用いて、ベクトルの開始点P1の座標、終了点P2の座標、ベクトルの塗りつぶし色などの属性情報などで構成されるベクトルデータを、入力されたベクトルデータ群の中から取得するためのものである。
【００２４】
なお、ベクトルデータとして、座標や色属性の例を説明したが、これに限定されるものではなく、入力として得られるベクトルデータ群に含まれるデータ種別の全て、あるいは、一部を取得することが可能である。
【００２５】
取得したベクトルデータは、後述する開始点・終了点算出部３に渡される。
＜開始点・終了点算出部＞
次に、開始点・終了点算出部３について説明する。
開始点・終了点算出部３は、ベクトルデータ抽出部２から受け取った処理対象のベクトルのデータをもとに、以降の処理の開始点および終了点を算出するためのものである。
【００２６】
以降、本実施の形態における図形描画処理を、垂直方向（ｙ軸方向）を基準として行う場合を例として説明を進める。ただし、これはあくまでも一例であり、これに限定されるものではない。水平方向（ｘ軸方向）を基準として行うことも可能であるし、任意の方向を基準として行うことも可能である。任意の方向としては、描画したい図形の主軸方向（分散が最も小さい方向）などを考えることができる。また、方向は2次元に限定されるものではない。
【００２７】
開始点・終了点算出部３では、基本的には、ベクトルデータを構成する２点P1（ベクトルの始点）,P2（ベクトルの終点）のうち、ｙ座標が小さい方を開始点に、大きい方を終了点として開始点、終了点のｙ座標を算出する。以下に、詳細な処理フローを示す（図９）。
【００２８】
点P1の座標が(x1, y1)、点P2の座標が(x2,y2)であるとする。まず、点P1とP2のｙ座標の比較を行い、両者が等しいかどうか（y1 = y2かどうか）の判定をする（Ｓ２０１）。等しい場合には、ステップＳ２０５に進む。そうでない場合には、ステップＳ２０２へ進む。ステップＳ２０２では、y1 < y2かどうかの判定を行い、真の場合はステップＳ２０４へ、偽の場合は、ステップＳ２０３へ進む。
【００２９】
ステップＳ２０３では、開始点のｙ座標ys = y2 + 1, 終了点のｙ座標ye = y1に設定する。同様に、ステップＳ２０４では、ys = y1, ye = y2 − 1、ステップＳ２０５では、ys = y1, ye = y2と設定する。
【００３０】
この様子を模式的に表現したのが図１０である。点P1とP2のｙ座標が等しい場合（図（ａ））は図示した２通りの可能性があるが、何れもys = ye = y1 (=y2)となる。この場合、開始点と終了点とは同じｙ座標となる。
【００３１】
y1 < y2すなわち、P1のｙ座標が小さい場合は図中（ｂ）のように、P1のｙ座標y1を開始点、P2の１つ手前の点P2’のｙ座標y2 − 1を終了点とする。
【００３２】
単にP2を終了点として選ばないのは、P2は、次のベクトルの始点となるため、次のベクトルの処理の際に描画のための処理が行われるため、この段階で終了点に含めてしまうと、処理が2重となり処理コストを考えた際に、効率が低下するためである（図１１）。図において、P1(n+1) = P2(n)となるため、このようなことが起こる。
【００３３】
同様に、y1 > y2すなわち、P1のｙ座標が大きい場合は図中（ｃ）のように、P2の１つ手前の点P2’のｙ座標y2+1を開始点、P1のｙ座標y1を終了点とする。
【００３４】
なお、以上では、描画効率のため、２重に処理される点を終了点のｙ座標yeとして算出せず、１つ隣りの点を算出する例を示したが、これに限定されるものではない。単に終了点をｙ座標が大きい方の点のｙ座標として算出しても構わない。
【００３５】
以上で、開始点・終了点のそれぞれのｙ座標が算出された。開始点・終了点算出部３は、この結果を後述する対象点管理部４に送る。
なお、以上では、ｙ座標が小さい方を開始点、大きい方を終了点とする例を示したが、これに限定されるものではない。逆で、大きい方を開始点、小さい方を終了点としてもよい。
【００３６】
また、単純に、ベクトルの始点P1を開始点、終点P2を終了点としても良いし、逆に、P2を開始点、P1を終了点としても良い。
またこれ以外でも、ベクトルデータ全体を通して、開始点、終了点の選び方が同様であって、しかも、算出した開始点、終了点を用いて、後述する以降の処理を一意に行うことが出来る手法であれば何でもよい。また、ｙ座標を基準としているのは、本実施例では上述したように垂直方向を基準とした例を用いて説明しているからであって、これに限定される訳ではない。基準の方向に合わせて、同様の効果となるように適宜変化して構わない。
【００３７】
また、以上では、ベクトルデータが取得される例を示したが、上述（＜ベクトルデータ群の説明＞の項）した通り、入力は点群データでも同様である。入力が点群データであった場合、上述の通りの変換を本開始点・終了点算出部３で行い、ベクトルデータとして扱い、同様の処理を行う。
【００３８】
＜対象点管理部＞
次に、対象点管理部４について説明する。
対象点管理部４は、ベクトルデータ抽出部２で取得した処理対象のベクトルのデータ、および、開始点・終了点算出部３で算出された開始点・終了点データを受け取り、ベクトルデータを点（ピクセル）単位に分割し、処理対象とする点（ピクセル）のデータとして管理するためのものである。
【００３９】
具体的には、図１２に示す処理フローのように動作する。まず、開始点・終了点算出部３で算出された開始点を処理対象点（処理対象ピクセル）としてセットする（Ｓ３０１）。次に、処理対象点（ｙ座標の値が現在の対象点）を管理対象とする（Ｓ３０２）。次に、ステップＳ３０２で管理対象とした点のｙ座標などの情報を後述する対象点算出部５に通知する（Ｓ３０３）。次に、塗りつぶし情報算出部７からの処理完了の通知を待ち、通知を受けた後に、ステップＳ３０５へ進む。ステップＳ３０５では、開始点・終了点算出部３で算出された終了点の処理が完了したかどうかを判定し、完了していない場合は、ステップＳ３０６へ進む。完了していると判定された場合は、ステップＳ３０７へ進む。ステップＳ３０６では、管理対象点のｙ座標の更新を行い、ステップＳ３０２に戻る。ステップＳ３０７では、対象点管理部４での処理が完了した旨の通知をベクトルデータ群管理部１へ送信する。
【００４０】
＜対象点算出部＞
次に、対象点算出部５について説明する。
対象点算出部５は、ベクトルデータ抽出部２で取得した処理対象のベクトルのデータ、および、対象点管理部４から通知された管理対象点情報を受け取り、管理対象点の座標データを算出するためのものである。
【００４１】
ここで、ベクトルデータ抽出部２から得られたベクトルのデータに含まれるベクトルの始点P1および終点P2のデータから、この２点で張られる部分直線の方程式は、以下の式（２）で得ることができる。
【００４２】
【数１】
【００４３】
ただし、ｙは、min(y1,y2) <= y <= max(y1,y2)を満たす必要がある。ここで、min(a,b), max(a,b)は、それぞれ、a,bの内の小さな値、大きな値を返す関数である。
【００４４】
式（２）を用いることで、対象点管理部４から通知された管理対象点情報に含まれる管理対象点のｙ座標値をもとに、管理対象点のｘ座標値を算出することができる。
【００４５】
対象点算出部５は、上記で算出した管理対象点のｘ座標と、対象点管理部４で得られたｙ座標とを合わせて、管理対象点座標(x,y)として、後述する対象点判定部６に送る。
【００４６】
なお、以上では、式（２）を用いて、直線方程式からｘ座標を算出する手法に関して説明したが、これに限定されるものではない。Bresenhamの線分計算アルゴリズムなど、他の手法を用いて算出することも可能である。また、Bresenhamの線分計算アルゴリズムを使用する場合、先述した対象点管理部４にて、開始点での初期ｘ座標を予め計算しておき、本対象点算出部５にて差分情報のみを算出することで、計算を高速化することも可能である。また、これら以外の手法を用いてｘ座標の算出を行っても構わない。
【００４７】
＜対象点判定部＞
次に、対象点判定部６について説明する。
対象点判定部６は、対象点算出部５で算出された処理対象点の座標値、および、入力となるベクトル群データを用いて、その両脇の点（ピクセル）が塗りつぶし領域かどうかを判定し、処理対象点の座標値とともに両脇の判定情報を出力する。
【００４８】
具体的には、対象点算出部５で算出された処理対象点Pの座標が(x,y)であったとすると、その両脇の点Pleft = (x-1,y), Pright = (x+1,y)の２点に対して、以下で説明する塗りつぶし領域判定を行う。
【００４９】
＜塗りつぶし領域判定＞
塗りつぶし領域判定について説明する。塗りつぶし領域判定は、対象点が所定の規則に従って、塗りつぶし領域であるのか、そうでないのかを判定するものである。以降、塗りつぶし規則として、前述したnon-zero fillルールを例として説明する。
【００５０】
図１３に、塗りつぶし領域判定のフローチャートを示す。
ステップＳ４０１で、まず、カウンター値の初期化（cnt = 0）を行う。
ステップＳ４０２では、調査対象となるベクトル番号を初期化する（i = 0）。
ステップＳ４０３では、調査ベクトル情報の取得を行う。現在のベクトル番号iを用いて、調査ベクトルV(i)のデータを取得する。
ステップＳ４０４では、対象点が調査ベクトルV(i)に含まれるかどうかの判定を行う。判定方法としては、例えば、ベクトルV(i)によって貼られる部分直線に対象点の座標が含まれているか調べればよい。その他の手法を用いて判定しても構わない。含まれている場合には、対象点は塗りつぶし領域と判定され、ステップＳ４１５に進む。含まれていない場合には、Ｓ４０５へ進む。
【００５１】
ステップＳ４０５では、対象点が調査ベクトルに対して上にあるかどうかの判定を行う。上にある場合には、ステップＳ４０６へ進む。そうでない場合には、ステップＳ４０８へ進む。
【００５２】
ステップＳ４０６では、対象点に対して、調査ベクトルが左から右に変化するかどうかを判別し、変化する場合には、ステップＳ４１０へ、そうでない場合には、ステップＳ４０７へ進む。
【００５３】
ステップＳ４０７では、調査ベクトルが右から左に変化するかどうかを判別し、変化する場合には、ステップＳ４１１へ、そうでない場合には、ステップＳ４１２へ進む。
【００５４】
ステップＳ４０８では、対象点に対して、調査ベクトルが右から左に変化するかどうかを判別し、変化する場合には、ステップＳ４１０へ、そうでない場合には、ステップＳ４０９へ進む。
【００５５】
ステップＳ４０９では、調査ベクトルが左から右に変化するかどうかを判別し、変化する場合には、ステップＳ４１１へ、そうでない場合には、ステップＳ４１２へ進む。
【００５６】
ステップＳ４１０では、カウンターの値を１つ増加させる（cnt = cnt+1）。
ステップＳ４１１では、カウンターの値を１つ減少させる（cnt = cnt-1）。
ステップＳ４１２では、全てのベクトルに関して、以上の調査が終了したかの判定を行い、終了していない場合にはＳ４１３へ、終了した場合には、Ｓ４１４へ進む。
ステップＳ４１３では、調査ベクトル番号の更新を行い（i = i+1）、ステップＳ４０３へ戻る。
ステップＳ４１４では、カウンター値（cnt）から塗りつぶし判定を行う。具体的には、カウンター値が非ゼロならば、塗りつぶし領域として判定し、そうでない場合は、塗りつぶし領域ではないと判定する。
【００５７】
ステップＳ４１５では、以上で判定した塗りつぶし領域か否かの判定結果を通知して終了する。
以上は、non-zero fillルールにおける塗りつぶし判定処理の一例である。この例では、対象点の位置に立って、ベクトルデータ群から構成される多角形を各ベクトルデータ毎に順次眺めていって、自分の体が１回転するかどうかを調べている。１回転する部分では、上記のカウンター値が非ゼロ値となり、塗りつぶし領域として判定される。
【００５８】
なお、以上で説明した判定手法はあくまでも一例であり、これに限定されるものではない。対象点を通る直線を引いて、それがベクトルデータ群と何度横切るかを調べる方法など、これ以外の判定方法を用いることができる。
【００５９】
また、以上では、non-zero fillルールを例として説明したが、塗りつぶし規則はこれに限定されるものではない。Even-odd fillルールやその他の規則など使用することが可能である。規則が変わった場合には、塗りつぶし可否の判定方法も別途変わるが、それに対しても、上記に準じる方法でも、それ以外の方法でも用いることが可能である。
【００６０】
＜両脇点の判定結果の出力＞
対象点判定部６は、以上で説明した「塗りつぶし領域判定」を用いて、対象点の両脇の点Pleft = (x-1,y), Pright = (x+1,y)の２点に対する塗りつぶし判定結果が得られた。この結果を対象点座標情報とともに出力する。
【００６１】
＜塗りつぶし情報算出部＞
次に、塗りつぶし情報算出部７について説明する。
塗りつぶし情報算出部７は、対象点判定部６から得られた処理対象点の座標値、および、その両脇の点（ピクセル）の塗りつぶし判定情報をもとに、対象点がそのスキャンラインにおいて、塗りつぶしに関与する点であるかどうかの判定を行い、関与する点であった場合には、その情報を生成するためのものである。
【００６２】
ここで、スキャンラインとは、対象点が含まれる行、つまり対象点座標が(x1,y1)であった場合、y=y1で示される行であると定義する。
＜スキャンライン毎の図形描画処理＞
ここで、まず、スキャンライン毎の図形描画処理に関して説明しておく。スキャンライン毎の図形描画処理とは、描画をスキャンライン単位の処理として、スキャンライン毎に、図形の塗りつぶし領域を複数のラインの描画で行う処理である。
【００６３】
例えば、図１４のような多角形図形があったとする。この描画を考えた場合、図１５のように、スキャンライン毎のライン描画処理に分割して描画することが可能である。図１５は、説明のため、多少誇張して描いているし、各ラインの間も説明のために便宜的に空けてあるが、実際にはこれらは、ピクセル単位の精度で描かれるものである。
【００６４】
ここで、図１６に示されるあるｙ座標の１スキャンライン部分を考えてみる。すると、多角形図形の描画処理は、複数のラインの描画（図１６の場合、２つのラインの描画）処理に置き換えられることが分かる。ラインの描画には、ラインの描画開始点と終了点のみあれば十分であるため、つまり、図１６における点P1,P2,P3,P4のみの情報があれば、図形の描画が可能であることが分かる。
【００６５】
ここで、図１６のP1,P3は、ラインの描画開始点であるため、以降、ラインＩＮ点と呼ぶ。また、P2,P4は、ラインの描画終了点であるため、以降、ラインＯＵＴ点と呼ぶ。
【００６６】
スキャンライン単位での図形描画を考えた場合、このラインＩＮ点とラインＯＵＴ点の算出を行えば良いと言える。
＜両脇点の判定結果からの対象点のラインＩＮ点・ラインＯＵＴ点判定＞
対象点判定部６で判定された対象点(x,y)の両脇の点Pleft = (x-1,y), Pright = (x+1,y)の２点に対する塗りつぶし判定結果を用いて、対象点がラインＩＮ点であるか、ラインＯＵＴ点であるか、それ以外か、の判定を行う。
【００６７】
両脇の結果は以下の４通りとなる。
（１） 両脇とも偽。つまり、（空欄）※（空欄）
（２） 左が真、右が偽。つまり、（塗り）※（空欄）
（３） 左が偽、右が真。つまり、（空欄）※（塗り）
（４） 両脇とも真。つまり、（塗り）※（塗り）
ここで、※は、該当点(x,y)を示す。また、（空欄）は塗りつぶさない領域、（塗り）は塗りつぶし領域を示す。
今、多角形図形の塗りつぶし処理を対象点が含まれるスキャンライン単位で考える。
（１）の場合、両脇（Pleft,Pright双方）が塗りつぶさない領域であるため、対象点※は、そのラインでの塗りつぶしに関与しない点である。つまり、ラインＩＮ点でもラインＯＵＴ点でもない。
【００６８】
（２）の場合、対象点※の左側（Pleft）が塗りつぶし領域で、右側（Pright）が塗りつぶさない領域ということで、対象点※は、そのラインにおける塗りつぶし領域の終了点、すなわちラインＯＵＴ点とみなすことができる。つまり、対象点※の左側に存在するどこかの点から塗りつぶし領域が始まり、対象点※が塗りつぶし領域の終了位置となる訳である。
【００６９】
（３）の場合、対象点※の左側（Pleft）が塗りつぶさない領域で、右側（Pright）が塗りつぶす領域ということで、対象点※は、そのラインにおける塗りつぶし領域の開始点、すなわちラインＩＮ点とみなすことができる。つまり、対象点※から塗りつぶし領域が始まり、対象点※の右側に存在するどこかの点が塗りつぶし領域の終了位置となる訳である。
【００７０】
（４）の場合、対象点※は、両脇（Pleft,Pright双方）が塗りつぶし領域であることから、対象点※は、塗りつぶし領域に含まれる点であるとみなすことができる。つまり、対象点※の左側に存在するどこかの点から塗りつぶし領域が始まり、対象点※の右側に存在するどこかの点が塗りつぶし領域の終了位置となり、ラインＩＮ点でもラインＯＵＴ点でもない点であると言える。
【００７１】
＜算出した塗りつぶし情報の出力＞
以上で説明した通り、塗りつぶし情報算出部７では、対象点の塗りつぶし情報、つまり、対象点（座標(x1,y1)）があるスキャンライン（y=y1であるスキャンライン）において（１）ラインＩＮ点、（２）ラインＯＵＴ点、（３）どちらでもない、という情報が得られる。これを後述する塗りつぶし情報登録部８に出力する。
【００７２】
＜塗りつぶし情報登録部＞
次に、塗りつぶし情報登録部８について説明する。
塗りつぶし情報登録部８は、塗りつぶし情報算出部７で得られた処理対象点の塗りつぶし情報を塗りつぶし情報記憶領域９に登録するためのものである。
＜塗りつぶし情報記憶領域の説明＞
ここで、塗りつぶし情報記憶領域９は塗りつぶし情報を保持するための任意の記憶手段である。例えば、本実施例を実現する装置が保持している内部メモリなどで構成される。
【００７３】
ただし、これに限定されるものではなく、塗りつぶし情報を保持することができるものであれば、任意の手段を用いることが可能である。また、塗りつぶし情報記憶領域９は、本実施例を実現する装置の内部に存在することが限定されるものではなく、脱着可能なメモリ装置（ＵＳＢメモリ機器、ＳＤメモリカードなど）や磁気記憶メディア（ＣＤ−Ｒ，ＤＶＤ−Ｒなど）、任意の通信手段（有線ＬＡＮ、無線ＬＡＮ、Ｗ−ＣＤＭＡなどの携帯電話を用いた通信など）を通した先にある記憶装置（ＮＡＳ装置、他の機器に内蔵されたＨＤＤなど）などでも構わない。
【００７４】
塗りつぶし情報記憶領域９に登録する塗りつぶし情報としては、典型的には、対象点座標、それが（１）ラインＩＮ点（２）ラインＯＵＴ点（３）そちらでもない、のどれに相当するか、である。ただし、これに限定されるものではなく、最低限これを含む任意の情報を登録するようにして構わない。
【００７５】
塗りつぶし情報記憶領域９での記憶手法は様々な手法が考えられる。ここでは、以下でその一手法に関して説明するが、これはあくまでも一例であり、これに限定されるものではない。
【００７６】
図１７は塗りつぶし情報記憶領域９での記憶手法の一例を示す。図１７の場合、各スキャンラインに対して、ラインＩＮ点とラインＯＵＴ点の２つをそれぞれ記憶可能なスタック（可変領域）を用意し、それを全スキャンライン分（１０８０ライン分）用意する例を示している。
【００７７】
全スキャンライン分とは、最終的に描画したい領域のスキャンライン総数を示す。例えば、フルハイビジョンの描画領域の場合、解像度は１９２０×１０８０となるので、１０８０ライン分ということになる。
【００７８】
スタックには、それぞれラインＩＮ点とラインＯＵＴ点と判定された点のｘ座標が保存される。図１７で、xi##(n), xo##(n)は、それぞれ、保存されている、スキャンライン##でのラインＩＮ点、ラインＯＵＴ点と判定された点のｘ座標を示している。
【００７９】
＜塗りつぶし情報登録部の動作＞
例えば、塗りつぶし情報算出部７からスキャンライン番号が１０７８の対象点（対象点座標が(xs,1078)であるような点）に対して、ラインＩＮであるとの塗りつぶし情報を得た場合、塗りつぶし情報登録部８では、その情報を塗りつぶし情報記憶領域９に登録する。この際、図１７の例では、スキャンライン番号が１０７８のラインＩＮ点のスタックには、xi1078(n)までのn+1個の情報が既に登録されているため、この末尾のn+2番目の情報として、対象点のｘ座標であるxsの値を登録する。
【００８０】
なお、以上では、登録方法の一例を示したが、これに限定されるものではない。あくまでも実施の一形態であり、これ以外の登録方法でも構わない。例えば、上記では末尾に追加する例を示したが、先頭に追加してもよいし、任意の位置に任意の条件（例えば座標の昇順など）で登録を行っても構わない。
【００８１】
＜描画領域算出部＞
次に、描画領域算出部１０について説明する。
描画領域算出部１０は、ベクトルデータ抽出部２から得られる処理対象ベクトルのデータをもととして、図形描画を行うための領域情報を算出するためのものである。
【００８２】
例えば、描画した図形を表示する画面の範囲が１９２０×１０８０の解像度の場合、描画領域として、最大で１９２０×１０８０の領域が必要となる。しかし、通常の場合、実際に多角形図形が存在する領域は、１９２０×１０８０の領域の内の一部の領域である。例えば、図１８の例では、１９２０×１０８０の領域の中央部分にのみ図形が存在している。この場合、図１９に示すように、図形を包含する最小矩形領域（座標(x0,y0)から、高さh、幅wの領域）の部分のみ図形が存在しているため、この矩形領域部分のみを図形の描画領域とすればよい。このようにすることで、画面全体を描画領域とするよりも描画領域を限定することが可能となり、描画速度の向上が見込まれる。
【００８３】
描画領域算出部１０は、このような目的のために存在し、ベクトルデータ抽出部２から得られる処理対象ベクトルのデータが含まれる最小矩形領域の情報を算出し、それを基として、図形描画領域情報の更新を行う。
【００８４】
本実施の形態の以上で説明してきたように、垂直方向（ｙ軸方向）を基準とした場合、図形描画は、ｙ軸方向のスキャンライン単位で行うため、図形の含まれる最小矩形情報のうち、ｙ軸方向のデータのみが重要となる。すなわち、矩形領域のｙ軸方向の下限値（図１９におけるｙ０）と矩形領域のｙ軸方向の上限値（図１９におけるｙ０＋ｈ）の値のみが重要である訳である。そこで、描画領域算出部１０では、この下限値（以降y_minと呼ぶ）と上限値（以降y_maxと呼ぶ）を算出する（図２０）。
【００８５】
算出のフローチャートを図２１に示す。ステップＳ５０１で、まず、y_min, y_maxの初期値の設定を行う。次に、ステップＳ５０２で、ベクトルデータ抽出部２から得られたベクトルデータの取得を行う。次に、ステップＳ５０３で、ベクトルの始点のｙ座標をy0にセットする。ステップＳ５０４で、y_min > y0かどうかの判定を行い、真の場合は、ステップ５０５へ行き、ステップＳ５０５にてy_minにy0の値を設定してステップＳ５０６へ、偽の場合は、そのままＳ５０６へ進む。同様にステップＳ５０６にて、y_max < y0の判定を行い、真の場合は、ステップＳ５０７にてy_maxにy0を設定してステップＳ５０８へ、偽の場合はそのままステップＳ５０８へ進む。ステップＳ５０８にて、全てのベクトルに関して処理が終了したかの判定を行い、偽の場合は、ステップＳ５０２へ戻る。真の場合は、処理を終了する。これにより、y_min, y_maxの値を得ることができる。
【００８６】
なお、以上で説明したのは、あくまでも実施の一形態であり、これに限定されるものではない。他の手法を用いて描画図形のｙ座標の上限値・下限値を算出してもよい。
【００８７】
また、以上では、ｙ座標のみを算出しているが、これに限定されるものではなく、同様の手段にて、ｘ座標の情報を算出して、合わせて出力してもよい。また、上限値・下限値として出力するのではなく、下限値と領域の高さなど、情報量として同等の情報であれば、表現形態は問わない。
【００８８】
＜描画領域補正部＞
次に、描画領域補正部１１について説明する。
描画領域補正部１１は、描画領域算出部１０から得られる描画領域情報を補正するためのものである。入力となるベクトルデータ群によって構成される図形の全体が必ずしも描画領域に入っているとは限らない。
【００８９】
図２２にこの例を示す。図２２は、図形の一部が描画領域外にある例である。この場合、y_min < 0となっているため、図形のこの部分は描画されない。この際には、y_min = 0に補正する必要がある。描画領域補正部１１では、このような補正を行う。
【００９０】
具体的には、y_min < 0の場合に、y_min = 0とする。また、y_max >= 描画領域のｙ座標の上限（図２２の例の場合には、1080）の場合には、y_max = 描画領域のｙ座標の上限値と補正する。
【００９１】
＜描画データ補正部＞
次に、描画データ補正部１２について説明する。
描画データ補正部１２は、ベクトルデータ群管理部１からのベクトルデータ群の処理終了の通知を受けて、塗りつぶし情報記憶領域９に記憶された描画のための情報を読み込み、これを後述する描画部１３で描画するために適切なデータとなるように補正するためのものである。
【００９２】
図１７に示されるように、ベクトルデータ群管理部１からのベクトルデータ群の処理終了の通知を受けた時点では、描画したい図形を構成する全てのベクトルに含まれる点（ピクセル）に対して、ラインＩＮ点、ラインＯＵＴ点の塗りつぶし情報が得られている。
【００９３】
しかし、これらは、上記塗りつぶし情報登録部８で説明した手法を用いた場合、ベクトルの処理順にスタックの先頭から積まれていくため、この出現順序は様々である。これは、ラインの描画コストを考えた場合効率が悪い。
【００９４】
また、描画したい図形の一部が描画領域よりも外にある場合には、ラインＩＮ点あるいはラインＯＵＴ点が描画領域の外となることがある（図２３）。この場合、ラインＩＮ点から描画領域の左端までのラインの描画は実際の描画領域に反映されないため無駄である。これは、処理装置の速度の低下を招く。
【００９５】
また、図形の形状が複雑な場合、同じラインＩＮ点・ＯＵＴ点を複数のベクトルが通過することがあるため、データの重複が起こりうる。この場合、同じ直線を複数回描画することは無駄である。また、ラインＩＮ点・ＯＵＴ点の対で表現される直線の領域が交差することがある。この場合は、複数の直線を１つにまとめることが可能である。こうすることによって、直線の描画回数を減らすことができて速度上昇に繋がる。
【００９６】
描画データ補正部１２は、これらの問題を解消するためのもので、
１．ラインＩＮ点・ラインＯＵＴ点を昇順（あるいは降順）にソートする
２．描画範囲外のデータを描画範囲端に修正する。具体的には、ラインＩＮ点、ラインＯＵＴ点のｘ座標が負値の場合は０に、描画幅値を超えている場合には、描画幅値とする。好ましくは、対応するラインＩＮ点、ラインＯＵＴ点が両方とも描画範囲外であったならば、不要データとしてスタックから削除する。
【００９７】
３．冗長なラインＩＮ点、ラインＯＵＴ点データを削除する。具体的には、ラインＩＮ点、ラインＯＵＴ点データに重複がある場合には、それを削除する。また、好ましくは、対となるラインＩＮ点、ラインＯＵＴ点データによって構成される直線に包含関係のある複数の直線となるデータが存在した場合、包含される直線を構成するデータを削除する。
【００９８】
以上の処理により、補正されたデータでは、先頭から同じ位置にあるラインＩＮ点・ラインＯＵＴ点を対応点として、直線（ライン）描画を行っていくだけで、対象スキャンラインにおいて、描画したい図形のうち描画範囲内にある部分を構成する部分が、画面左側から順に描かれて行くことになる。
【００９９】
＜描画部＞
最後に、描画部１３について説明する。
描画部１３は、描画データ補正部１２から得られた描画データデータをスキャンライン毎に直線（ライン）描画によって描画していくものである。この際、描画領域補正部１１から得られた描画範囲（具体的には、描画開始スキャンラインと描画終了スキャンライン）の情報を用いて、描画処理範囲を限定することで、描画の高速化を行う。
【０１００】
図２４に描画部１３の処理フローチャートを示す。
スキャンライン番号mのn番目のラインＩＮデータをline_in(m,n)、ラインＯＵＴデータをline_out(m,n)とする。また、スキャンライン番号mに含まれるデータの要素数をn_elmtとする。また、描画領域補正部１１から得られた描画開始スキャンライン番号をm0、終了スキャンライン番号をm1とする。
【０１０１】
まず、ステップＳ６０１で、描画対象スキャンライン番号として、m0をセットする。次に、ステップＳ６０２で、処理対象データ番号nの初期化と、要素数n_elmtの算出を行う。次に、ステップＳ６０３で、L0 = line_in(m,n), L1 = line_out(m,n)の値の取得を行う。次に、ステップＳ６０４で、L0, L1で形成されるライン（直線）の実際の描画を行う。これにより、画面にL0,L1を両端とする直線が描画される。そして、ステップＳ６０５で、全ての要素について終了したかの判定を行い、終了していない場合には、ステップＳ６０６にて、処理点の更新（n=n+1）を行い、ステップＳ６０３に戻る。終了した場合には、ステップＳ６０７へ進む。ステップＳ６０７では、描画終了スキャンラインm1までの処理が完了したかの判定を行い、終了していない場合には、ステップＳ６０８にて、処理スキャンラインの更新（m=m+1）を行い、ステップＳ６０２へ戻る。終了している場合には、処理を終える。
【０１０２】
なお、ラインの実際の描画は、ライン描画専用のＨＷを用いてもよいし、汎用のグラフィックス処理ＬＳＩ（ＧＰＵ、Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）などを用いてもよいし、その他の手段を用いてソフトウェア的に処理しても構わない。
【０１０３】
以上により、図１５で示されたようにスキャンライン単位の描画が逐次行われ、最終的に、図１４で示されるような多角形図形の描画が完了する。
なお、以上で示した手法はあくまでも実施の一形態であり、これに限定されるものではない。
＜第１の実施形態による効果＞
以上で説明した本発明の第１の実施形態によれば、入力されるベクトルデータ群によって構成される図形の複雑さに依存して描画処理が複雑になることはない。例えば、三角形分割を用いた描画手法（非特許文献２参照）では、入力された図形に複雑な自己交差があった場合、これを１つの閉ループで構成される単純多角形群に分割して処理する必要がある。このため、図形の複雑さに依存して、分割処理が非常に多数回適用されることになり、以降の処理が複雑となる。これは、不具合（バグ）の大きな要因の１つとなりうる。入力図形が非常に複雑となった場合、予期しない形状の入力がありえ、この際に上記分割処理が上手く動作しない可能性が出てくるからである。つまり、図形の複雑さに比例して処理量が増加するような手法は安定度に欠けるといえる。一方、本発明の第１の実施形態によれば、処理はベクトルデータ単位で行っており、この処理内容は、図形の形状に依らない。このため、図形の複雑さに比例して処理量が増加するようなことはない。このため、本発明の第１の実施形態による手法は、非常に安定した手法と言うことができる。
【０１０４】
また、本発明の第１の実施形態による手法は、描画処理が実行される前段階に、ラインＩＮ、ラインＯＵＴのデータ群のみを記憶すれば良い。これは、非常に小さなデータ量しか必要としないものであり、メモリの使用量は少ない。一方、三角形分割の手法は、描画処理前に、様々な前処理を必要とする（詳細に関しては、非特許文献２などを参照のこと）ため、非常に多くの中間データを記憶しておく必要がある。描画処理に関しても、三角形単位で行うため、ライン単位である本発明の第１の実施形態による手法よりもメモリ使用量が多くなる。また、ステンシルバッファを用いた手法（非特許文献３など）は、描画処理のためにステンシルバッファという特殊なメモリ領域を必要とする。これは、基本的には、描画領域と同等の領域が必要となる。また、描画処理自体も画面単位で行うため、非常に多くのメモリを使用する必要がある。本発明の第１の実施形態による手法は、メモリ使用量の観点から、これらの手法に対するメリットが大きい。
【０１０５】
また、本発明の第１の実施形態による手法は、描画処理としてライン描画が可能な装置を用意すれば良いため、複雑な専用回路を必要とせず、簡単な回路または、汎用のグラフィックスＬＳＩを用いて実現可能であるという観点から、使用リソースに対するメリットも大きい。
【０１０６】
さらに、本発明の第１の実施形態による手法は、上述してきたような構成を取ることにより、ポイントベースの手法や従来のスキャンラインベースの手法と比べて、高速に図形描画が可能である。
【０１０７】
以上より、本発明の第１の実施形態による手法によれば、従来技術に存在していた少リソースでの使用が困難であったり、安定性に欠けたり、高速性に欠けたりする問題点を解消し、少ないリソースやメモリしか使用不可能な環境下にて、高速かつ安定的に動作することが可能な図形描画装置、および、手法を提供することが可能となる。
【０１０８】
［第１の実施形態の変形例１］
図２５に本発明の第１の実施形態の変形例１に係る図形描画装置の全体構成図を示す。本発明の第１の実施形態の変形例１は、第１の実施例に、ベクトルデータ群補正部１４が追加された形となっている。
【０１０９】
＜ベクトルデータ群補正部＞
ベクトルデータ群補正部１４について説明する。ベクトルデータ群補正部１４は、入力されたベクトルデータ群を補正するためのものである。
ベクトルデータ群に、ゼロベクトルのデータが含まれていた場合、このデータは除去することが可能である。
また、連続する２つ以上のベクトルの方向が同じ場合、つまり、
V(n) / |V(n)| = V(n+1) / |V(n+1)| = ・・・ = V(n+m) / |V(n+m)|
(m = 1, 2, ・・・)
という関係が成り立つ場合、これらのベクトルは、１つのベクトルとしてマージすることが可能となる。つまり、V(n)の終点を上記の関係におけるV(n+m)の終点に置き換え、V(n+1),・・・,V(n+m)のデータを削除することが可能である。
【０１１０】
さらに、連続するベクトルが逆の方向を持っている場合も同様にマージ可能であり、連続するベクトルで貼られるベクトルの新たな両端点を算出し、V(n)をそのベクトルに置き換え、マージされた残りのベクトルは削除することが可能である。
【０１１１】
ベクトルデータ群補正部１４は、このような冗長な表現となっているベクトル群データの補正を行う。この補正により、ベクトルデータ群の総数を削減することが可能となり、以降の処理のスピードアップに繋がる。
【０１１２】
なお、以上では、冗長な表現の一例を示したが、これに限定されるものではない。ベクトルデータ群によって構成される多角形図形の形状を変えることなく、ベクトルデータ群の総数を削減することが可能な変形は、全て用いることが可能である。
【０１１３】
本発明の第１の実施形態の変形例１の以降の処理に関しては、第１の実施形態において、入力であるベクトルデータ群として説明した部分を適宜、ベクトルデータ群補正部１４によって補正された後のベクトルデータ群と読み替えれば同様である。
【０１１４】
以上で説明した以外は、第１の実施形態と同様の動作である。
［第１の実施形態の変形例２］
図２６は、本発明の第１の実施形態の変形例２に係る図形描画装置の全体構成図である。
変形例２に係る図形描画装置は、第１の実施形態の図形描画装置における描画データ補正部１２の代わりに、塗りつぶし情報記憶領域９に記憶されているデータを用いて、塗りつぶし情報登録部８で得られた登録情報を逐次補正しながら、塗りつぶし情報記憶領域９のデータを更新するための新たな描画データ補正部１５が追加されている。また、第１の実施形態の図形描画装置における描画データ補正部１２に接続されていた部分は、直接描画部１３に接続されている。
【０１１５】
描画データ補正部１５の動作は、基本的には、第１の実施形態の図形描画装置における描画データ補正部１２と同様である。異なる部分は、第１の実施形態の図形描画装置における描画データ補正部１２では、塗りつぶし情報記憶領域９に蓄積されているデータに対して後から補正を行ったのに対し、描画データ補正部１５では、塗りつぶし情報記憶領域９のデータを参照しつつ、塗りつぶし情報登録部８で得られた登録情報を補正しながら塗りつぶし情報記憶領域９に蓄積していく、つまり、登録データを逐次補正しながら塗りつぶし情報記憶領域９に保存して行く（同時に、塗りつぶし情報記憶領域９に既に蓄積されたデータも更新される）という点である。
【０１１６】
描画部１３は、ベクトルデータ群管理部１からのベクトルデータ群の処理終了の通知を受けて処理を開始するという点以外は、第１の実施形態と全く同様である。
［第１の実施形態の変形例３］
図２７は、本発明の第１の実施形態の変形例３に係る図形描画装置の全体構成図である。
第１の実施形態との違いは、描画データ補正部１２が、塗りつぶし情報記憶領域９と描画部１３の間の存在するのではなく、描画部１３にのみ接続されているという点である。
【０１１７】
この場合、描画部１３での、各スキャンラインにおける処理の前処理として、描画データ補正部１２を呼び出し、描画データ補正部１２にて対象スキャンラインのデータの補正を行い、この結果を再び描画部１３で受け取り、処理を続ける。具体的には、図２４におけるステップＳ６０３の処理の前に、上記の処理を入れればよい。描画データ補正部１２にて行う補正手法は、第１の実施形態での説明と全く同様である。
【０１１８】
第１の実施形態との違いは、第１の実施形態では、「全てのデータの補正」→「全てのデータの描画」というシーケンシャルな処理であったのに対し、本変形例は、スキャンライン毎に、「データの補正」→「描画」を繰り返すという点である。
【０１１９】
［第１の実施形態の変形例４］
図２８は、本発明の第１の実施形態の変形例４に係る図形描画装置の全体構成図である。
図１で表される第１の実施形態の塗りつぶし情報算出部７と塗りつぶし情報登録部８の間に、新たに、塗りつぶし情報補正部１６が追加される形となっている。
塗りつぶし情報補正部１６は、塗りつぶし情報算出部７で得られた処理対象点の塗りつぶし情報を補正し、塗りつぶし情報登録部８に渡すためのものである。
具体的には、塗りつぶし情報補正部１６では、ラインＩＮ点・ラインＯＵＴ点の位置の補正を行う。例えば、あるベクトルに対して、図２９のようなラインＯＵＴ点が得られたとする。この場合、図３０に示したように、ラインＯＵＴ点までをそのスキャンラインにおける図形の塗りつぶし領域とするか、図３１に示したように、一つスキャンラインの上の点(n-1)におけるラインＯＵＴ点よりも一つ手前の点までを塗りつぶし領域にするか、などというような、複数の塗りつぶし手法が考えられる。
【０１２０】
これは、多角形図形を描画する際の、多角形の縁部分の描画のルールによって変化する。塗りつぶし情報補正部１６は、この描画ルールに従って、塗りつぶし情報算出部７で得られた処理対象点のラインＩＮ点・ラインＯＵＴ点の座標値の補正を行う。
【０１２１】
補正方法は描画ルールによって変化するが、図３０の例の場合、上下のスキャンラインの情報を用いて算出する。上下のどちらを使うかは、ベクトルの方向により決定する。
【０１２２】
塗りつぶし情報補正部１６は補正したラインＩＮ点、ラインＯＵＴ点のデータを塗りつぶし情報登録部８に渡し、塗りつぶし情報登録部８では、第１の実施形態のところで説明したのと同様に処理を継続する。
【０１２３】
なお、ここでは、補正方法の一例を示したが、これに限定されるものではない。描画ルールに合致するような任意の補正方法を用いて処理を行う。
以上の各実施形態やその変形例は、適宜組み合わせて実施することが可能である。
本願発明の実施例における処理をコンピュータで実行可能なプログラムで実現し、このプログラムをコンピュータで読みとり可能な記憶媒体として実現することも可能である。
【０１２４】
なお、本願発明における記憶媒体としては、磁気ディスク、フロッピー（登録商標）ディスク、ハードディスク、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＤＶＤ等）、光磁気ディスク（ＭＯ等）、半導体メモリ等、プログラムを記憶でき、かつコンピュータまたは組み込みシステムが読みとり可能な記憶媒体であれば、その記憶形式は何れの形態であってもよい。
【０１２５】
また、記憶媒体からコンピュータや組み込みシステムにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーションシステム）や、データベース管理ソフト、ネットワーク等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行してもよい。
【０１２６】
さらに、本願発明における記憶媒体は、コンピュータあるいは組み込みシステムと独立した媒体に限らず、ＬＡＮやインターネット等により伝達されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１２７】
また、記憶媒体は１つに限られず、複数の媒体から本実施形態における処理が実行される場合も、本発明における記憶媒体に含まれ、媒体の構成は何れの構成であってもよい。
【０１２８】
なお、本願発明におけるコンピュータまたは組み込みシステムは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するためのものであって、パソコン、マイコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であってもよい。
【０１２９】
また、本願発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本願発明の機能を実現することが可能な機器、装置を総称している。
【０１３０】
なお、本発明は、上記実施形態に限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。さらに、上記実施形態には種々の段階の発明は含まれており、開示される複数の構成要件における適宜な組み合わせにより、種々の発明が抽出され得る。例えば、実施形態に示される全構成要件からいくつかの構成要件が削除されても、発明が解決しようとする課題の欄で述べた課題（の少なくとも１つ）が解決でき、発明の効果の欄で述べられている効果（の少なくとも１つ）が得られる場合には、この構成要件が削除された構成が発明として抽出され得る。
【図面の簡単な説明】
【０１３１】
【図１】本発明の第１の実施形態に係る図形描画装置の構成例を概略的に示す図。
【図２】ベクトルデータ群を説明するための図。
【図３】図形描画に関して説明した図。
【図４】図形描画に関して説明した図。
【図５】多角形図形に関して説明した図。
【図６】閉じていない多角形図形に関して説明した図。
【図７】多角形図形に関して説明した図。
【図８】ベクトルデータ群管理部の処理フローを説明した図。
【図９】開始点・終了点算出部の処理フローを説明した図。
【図１０】開始点・終了点算出の様子を模式的に説明した図。
【図１１】連続するベクトルに共通する点が２重に処理される様子を説明した図。
【図１２】対象点管理部の処理フローを説明した図。
【図１３】塗りつぶし領域判定のフローチャート図。
【図１４】スキャンライン毎の図形描画処理を説明した図。
【図１５】スキャンライン毎の図形描画処理を説明した図。
【図１６】スキャンライン毎の図形描画処理を説明した図。
【図１７】塗りつぶし情報記憶領域を説明した図。
【図１８】描画領域に関して説明した図。
【図１９】描画領域に関して説明した図。
【図２０】描画領域に関して説明した図。
【図２１】描画領域算出のフローチャート図。
【図２２】描画領域の補正に関して説明した図。
【図２３】描画データの補正に関して説明した図。
【図２４】描画部の処理フローチャート図。
【図２５】本発明の第１の実施形態の変形例１に係る図形描画装置の構成例を概略的に示す図。
【図２６】本発明の第１の実施形態の変形例２に係る図形描画装置の構成例を概略的に示す図。
【図２７】本発明の第１の実施形態の変形例３に係る図形描画装置の構成例を概略的に示す図。
【図２８】本発明の第１の実施形態の変形例４に係る図形描画装置の構成例を概略的に示す図。
【図２９】塗りつぶし情報の補正に関して説明した図。
【図３０】塗りつぶし情報の補正に関して説明した図。
【図３１】塗りつぶし情報の補正に関して説明した図。
【符号の説明】
【０１３２】
１・・・ベクトルデータ群管理部
２・・・ベクトルデータ抽出部
３・・・開始点・終了点算出部
４・・・対象点管理部
５・・・対象点算出部
６・・・対象点判定部
７・・・塗りつぶし情報算出部
８・・・塗りつぶし情報登録部
９・・・塗りつぶし情報記憶領域
１０・・・描画領域算出部
１１・・・描画領域補正部
１２・・・描画データ補正部
１３・・・描画部
１４・・・ベクトルデータ群補正部
１５・・・描画データ補正部
１６・・・塗りつぶし情報補正部
【特許請求の範囲】
【請求項１】
入力となるベクトルデータ群を管理するベクトルデータ群管理手段と、
前記ベクトルデータ群管理手段での管理情報に基づいて、入力となるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータの処理順を算出する処理順序算出手段と、
前記処理順序算出手段で算出された処理順序を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、
前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出するための塗りつぶし情報算出手段と、
前記塗りつぶし情報算出手段によって得られた塗りつぶし情報を用いて、図形を描画するための描画手段を具備することを特徴とする図形描画装置。
【請求項２】
入力となるベクトルデータ群を管理するベクトルデータ群管理手段と、
前記ベクトルデータ群管理手段での管理情報に基づいて、入力となるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータの処理順を算出する処理順序算出手段と、
前記処理順序算出手段で算出された処理順序を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、
前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出するための塗りつぶし情報算出手段と、
対象点の塗りつぶし情報を保存するための塗りつぶし情報保存手段と、
前記塗りつぶし情報算出手段で算出された塗りつぶし情報を前記塗りつぶし情報保存手段に登録するための塗りつぶし情報登録手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータをもとに、最終的に描画を行う領域を求めるための描画領域算出手段と、
前記描画領域算出手段で得られた描画領域情報、および、前記塗りつぶし情報保存手段に保存された塗りつぶし情報を用いて、図形を描画するための描画手段を具備することを特徴とする図形描画装置。
【請求項３】
入力となるベクトルデータ群を管理するためのベクトルデータ群管理手段と、
前記ベクトルデータ群管理手段での管理情報に基づいて、入力となるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータから、処理の開始点および終了点を算出する開始点・終了点算出手段と、
前記開始点・終了点算出手段で算出された処理開始点・終了点情報を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、
前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点のピクセル座標位置を算出する対象点算出手段と、
前記対象点算出手段で算出された処理対象点の座標位置の両脇のピクセルの塗りつぶし判定を行う対象点判定手段と、
前記対象点判定手段での判定結果をもとに、対象点の塗りつぶし情報を算出する塗りつぶし情報算出手段と、
対象点の塗りつぶし情報を保存する塗りつぶし情報保存手段と、
前記塗りつぶし情報算出手段で算出された塗りつぶし情報を前記塗りつぶし情報保存手段に登録する塗りつぶし情報登録手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータをもとに、図形描画領域を算出・更新する描画領域算出手段と、
前記描画領域算出手段で算出された描画領域を補正して、最終的に描画を行う領域を求める描画領域補正手段と、
前記塗りつぶし情報保存手段に保存された塗りつぶし情報を描画するのに適正なデータとして補正する描画データ補正手段と、
前記描画領域補正手段で得られた描画領域情報、前記描画データ補正手段で補正されたデータを用いて、図形を描画する描画手段を具備することを特徴とする図形描画装置。
【請求項４】
入力となるベクトルデータ群のベクトルデータを補正し、冗長なベクトルデータのマージ、削除を行うベクトルデータ群補正手段と、
前記ベクトルデータ群補正手段から得られるベクトルデータ群を管理するベクトルデータ群管理手段と、
前記ベクトルデータ群管理手段での管理情報に基づいて、前記ベクトルデータ群補正手段から得られるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータから、処理の開始点および終了点を算出する開始点・終了点算出手段と、
前記開始点・終了点算出手段で算出された処理開始点・終了点情報を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、
前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点のピクセル座標位置を算出する対象点算出手段と、
前記対象点算出手段で算出された処理対象点の座標位置の両脇のピクセルの塗りつぶし判定を行う対象点判定手段と、
前記対象点判定手段での判定結果をもとに、対象点の塗りつぶし情報を算出する塗りつぶし情報算出手段と、
対象点の塗りつぶし情報を保存する塗りつぶし情報保存手段と、
前記塗りつぶし情報算出手段で算出された塗りつぶし情報を前記塗りつぶし情報保存手段に登録する塗りつぶし情報登録手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータをもとに、図形描画領域を算出・更新する描画領域算出手段と、
前記描画領域算出手段で算出された描画領域を補正して、最終的に描画を行う領域を求める描画領域補正手段と、
前記塗りつぶし情報保存手段に保存された塗りつぶし情報を描画するのに適正なデータとして補正する描画データ補正手段と、
前記描画領域補正手段で得られた描画領域情報、前記描画データ補正手段で補正されたデータを用いて、図形を描画する描画手段を具備することを特徴とする図形描画装置。
【請求項５】
入力となるベクトルデータ群を管理するベクトルデータ群管理手段と、
前記ベクトルデータ群管理手段での管理情報に基づいて、入力となるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータから、処理の開始点および終了点を算出する開始点・終了点算出手段と、
前記開始点・終了点算出手段で算出された処理開始点・終了点情報を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、
前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点のピクセル座標位置を算出する対象点算出手段と、
前記対象点算出手段で算出された処理対象点の座標位置の両脇のピクセルの塗りつぶし判定を行う対象点判定手段と、
前記対象点判定手段での判定結果をもとに、対象点の塗りつぶし情報を算出する塗りつぶし情報算出手段と、
対象点の塗りつぶし情報を保存する塗りつぶし情報保存手段と、
前記塗りつぶし情報算出手段で算出された塗りつぶし情報を前記塗りつぶし情報保存手段に登録する塗りつぶし情報登録手段と、
前記塗りつぶし情報保存手段に保存された塗りつぶし情報を用いて、前記塗りつぶし情報登録手段から得られる登録情報を、描画するのに適正なデータとして補正し、前記塗りつぶし情報保存手段に保存された塗りつぶし情報を更新する描画データ補正手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータをもとに、図形描画領域を算出・更新する描画領域算出手段と、
前記描画領域算出手段で算出された描画領域を補正して、最終的に描画を行う領域を求める描画領域補正手段と、
前記描画領域補正手段で得られた描画領域情報、前記塗りつぶし情報登録手段に保存されたデータを用いて、図形を描画する描画手段を具備することを特徴とする図形描画装置。
【請求項６】
入力となるベクトルデータ群を管理するベクトルデータ群管理手段と、
前記ベクトルデータ群管理手段での管理情報に基づいて、入力となるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータから、処理の開始点および終了点を算出する開始点・終了点算出手段と、
前記開始点・終了点算出手段で算出された処理開始点・終了点情報を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、
前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点のピクセル座標位置を算出する対象点算出手段と、
前記対象点算出手段で算出された処理対象点の座標位置の両脇のピクセルの塗りつぶし判定を行う対象点判定手段と、
前記対象点判定手段での判定結果をもとに、対象点の塗りつぶし情報を算出する塗りつぶし情報算出手段と、
対象点の塗りつぶし情報を保存する塗りつぶし情報保存手段と、
前記塗りつぶし情報算出手段で算出された塗りつぶし情報を前記塗りつぶし情報保存手段に登録する塗りつぶし情報登録手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータをもとに、図形描画領域を算出・更新する描画領域算出手段と、
前記描画領域算出手段で算出された描画領域を補正して、最終的に描画を行う領域を求める描画領域補正手段と、
前記描画領域補正手段で得られた描画領域情報、前記塗りつぶし情報保存手段に保存されたデータを用いて、図形を描画する描画手段と、
前記描画手段と連携して動作し、描画手段から取得した描画データを適正なデータとして補正した後、再び描画手段へ補正したデータを戻す描画データ補正手段を具備することを特徴とする図形描画装置。
【請求項７】
入力となるベクトルデータ群を管理するベクトルデータ群管理手段と、
前記ベクトルデータ群管理手段での管理情報に基づいて、入力となるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータから、処理の開始点および終了点を算出する開始点・終了点算出手段と、
前記開始点・終了点算出手段で算出された処理開始点・終了点情報を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、
前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点のピクセル座標位置を算出する対象点算出手段と、
前記対象点算出手段で算出された処理対象点の座標位置の両脇のピクセルの塗りつぶし判定を行う対象点判定手段と、
前記対象点判定手段での判定結果をもとに、対象点の塗りつぶし情報を算出する塗りつぶし情報算出手段と、
前記塗りつぶし情報算出手段で算出された塗りつぶし情報を所定の描画規則に従って補正する塗りつぶし情報補正手段と、
対象点の塗りつぶし情報を保存する塗りつぶし情報保存手段と、
前記塗りつぶし情報補正手段で補正された塗りつぶし情報を前記塗りつぶし情報保存手段に登録する塗りつぶし情報登録手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータをもとに、図形描画領域を算出・更新する描画領域算出手段と、
前記描画領域算出手段で算出された描画領域を補正して、最終的に描画を行う領域を求める描画領域補正手段と、
前記塗りつぶし情報保存手段に保存された塗りつぶし情報を描画するのに適正なデータとして補正する描画データ補正手段と、
前記描画領域補正手段で得られた描画領域情報、前記描画データ補正手段で補正されたデータを用いて、図形を描画する描画手段を具備することを特徴とする図形描画装置。
【請求項８】
前記対象点管理手段は、前記塗りつぶし情報算出手段から得られる対象点の処理の終了の通知情報を用いて処理対象点の決定を行うことを特徴とする請求項１乃至請求項７記載の図形描写装置。
【請求項９】
入力となるベクトルデータ群に含まれる処理対象ベクトルの処理順序、データを管理するステップと、
管理情報に基づいて、前記ベクトルデータ群から処理対象ベクトルのデータの抽出を行い、
抽出されたベクトルデータの処理順の算出を行うステップと、
算出された処理順序情報を用いて処理対象点の管理、及び対象ベクトルの処理の終了の通知を行うステップと、
処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出するステップと、
算出された塗りつぶし情報を用いて、図形の描画を行うステップを含むことを特徴とする図形描画方法。
【請求項１０】
前記通知を行うステップは、対象点の処理の終了通知情報を用いて処理対象点の管理、対象ベクトルの処理の終了の通知を行うことを特徴とする請求項９記載の図形描画方法。
【請求項１１】
コンピュータを図形描画装置として機能させるためのプログラムであって、
入力となるベクトルデータ群に含まれる処理対象ベクトルの処理順序、データを管理する機能と、
管理情報に基づいて、前記ベクトルデータ群から処理対象ベクトルのデータの抽出を行い、
抽出されたベクトルデータの処理順の算出を行う機能と、
算出された処理順序情報を用いて処理対象点の管理、及び対象ベクトルの処理の終了の通知を行う機能と、
処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出する機能と、
算出された塗りつぶし情報を用いて、図形の描画を行う機能を含みコンピュータに実現させるためのプログラム。
【請求項１２】
前記通知を行う機能は、対象点の処理の終了通知情報を用いて処理対象点の管理、対象ベクトルの処理の終了の通知を行うことを特徴とする請求項１１記載のプログラム。
【請求項１】
入力となるベクトルデータ群を管理するベクトルデータ群管理手段と、
前記ベクトルデータ群管理手段での管理情報に基づいて、入力となるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータの処理順を算出する処理順序算出手段と、
前記処理順序算出手段で算出された処理順序を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、
前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出するための塗りつぶし情報算出手段と、
前記塗りつぶし情報算出手段によって得られた塗りつぶし情報を用いて、図形を描画するための描画手段を具備することを特徴とする図形描画装置。
【請求項２】
入力となるベクトルデータ群を管理するベクトルデータ群管理手段と、
前記ベクトルデータ群管理手段での管理情報に基づいて、入力となるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータの処理順を算出する処理順序算出手段と、
前記処理順序算出手段で算出された処理順序を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、
前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出するための塗りつぶし情報算出手段と、
対象点の塗りつぶし情報を保存するための塗りつぶし情報保存手段と、
前記塗りつぶし情報算出手段で算出された塗りつぶし情報を前記塗りつぶし情報保存手段に登録するための塗りつぶし情報登録手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータをもとに、最終的に描画を行う領域を求めるための描画領域算出手段と、
前記描画領域算出手段で得られた描画領域情報、および、前記塗りつぶし情報保存手段に保存された塗りつぶし情報を用いて、図形を描画するための描画手段を具備することを特徴とする図形描画装置。
【請求項３】
入力となるベクトルデータ群を管理するためのベクトルデータ群管理手段と、
前記ベクトルデータ群管理手段での管理情報に基づいて、入力となるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータから、処理の開始点および終了点を算出する開始点・終了点算出手段と、
前記開始点・終了点算出手段で算出された処理開始点・終了点情報を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、
前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点のピクセル座標位置を算出する対象点算出手段と、
前記対象点算出手段で算出された処理対象点の座標位置の両脇のピクセルの塗りつぶし判定を行う対象点判定手段と、
前記対象点判定手段での判定結果をもとに、対象点の塗りつぶし情報を算出する塗りつぶし情報算出手段と、
対象点の塗りつぶし情報を保存する塗りつぶし情報保存手段と、
前記塗りつぶし情報算出手段で算出された塗りつぶし情報を前記塗りつぶし情報保存手段に登録する塗りつぶし情報登録手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータをもとに、図形描画領域を算出・更新する描画領域算出手段と、
前記描画領域算出手段で算出された描画領域を補正して、最終的に描画を行う領域を求める描画領域補正手段と、
前記塗りつぶし情報保存手段に保存された塗りつぶし情報を描画するのに適正なデータとして補正する描画データ補正手段と、
前記描画領域補正手段で得られた描画領域情報、前記描画データ補正手段で補正されたデータを用いて、図形を描画する描画手段を具備することを特徴とする図形描画装置。
【請求項４】
入力となるベクトルデータ群のベクトルデータを補正し、冗長なベクトルデータのマージ、削除を行うベクトルデータ群補正手段と、
前記ベクトルデータ群補正手段から得られるベクトルデータ群を管理するベクトルデータ群管理手段と、
前記ベクトルデータ群管理手段での管理情報に基づいて、前記ベクトルデータ群補正手段から得られるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータから、処理の開始点および終了点を算出する開始点・終了点算出手段と、
前記開始点・終了点算出手段で算出された処理開始点・終了点情報を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、
前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点のピクセル座標位置を算出する対象点算出手段と、
前記対象点算出手段で算出された処理対象点の座標位置の両脇のピクセルの塗りつぶし判定を行う対象点判定手段と、
前記対象点判定手段での判定結果をもとに、対象点の塗りつぶし情報を算出する塗りつぶし情報算出手段と、
対象点の塗りつぶし情報を保存する塗りつぶし情報保存手段と、
前記塗りつぶし情報算出手段で算出された塗りつぶし情報を前記塗りつぶし情報保存手段に登録する塗りつぶし情報登録手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータをもとに、図形描画領域を算出・更新する描画領域算出手段と、
前記描画領域算出手段で算出された描画領域を補正して、最終的に描画を行う領域を求める描画領域補正手段と、
前記塗りつぶし情報保存手段に保存された塗りつぶし情報を描画するのに適正なデータとして補正する描画データ補正手段と、
前記描画領域補正手段で得られた描画領域情報、前記描画データ補正手段で補正されたデータを用いて、図形を描画する描画手段を具備することを特徴とする図形描画装置。
【請求項５】
入力となるベクトルデータ群を管理するベクトルデータ群管理手段と、
前記ベクトルデータ群管理手段での管理情報に基づいて、入力となるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータから、処理の開始点および終了点を算出する開始点・終了点算出手段と、
前記開始点・終了点算出手段で算出された処理開始点・終了点情報を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、
前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点のピクセル座標位置を算出する対象点算出手段と、
前記対象点算出手段で算出された処理対象点の座標位置の両脇のピクセルの塗りつぶし判定を行う対象点判定手段と、
前記対象点判定手段での判定結果をもとに、対象点の塗りつぶし情報を算出する塗りつぶし情報算出手段と、
対象点の塗りつぶし情報を保存する塗りつぶし情報保存手段と、
前記塗りつぶし情報算出手段で算出された塗りつぶし情報を前記塗りつぶし情報保存手段に登録する塗りつぶし情報登録手段と、
前記塗りつぶし情報保存手段に保存された塗りつぶし情報を用いて、前記塗りつぶし情報登録手段から得られる登録情報を、描画するのに適正なデータとして補正し、前記塗りつぶし情報保存手段に保存された塗りつぶし情報を更新する描画データ補正手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータをもとに、図形描画領域を算出・更新する描画領域算出手段と、
前記描画領域算出手段で算出された描画領域を補正して、最終的に描画を行う領域を求める描画領域補正手段と、
前記描画領域補正手段で得られた描画領域情報、前記塗りつぶし情報登録手段に保存されたデータを用いて、図形を描画する描画手段を具備することを特徴とする図形描画装置。
【請求項６】
入力となるベクトルデータ群を管理するベクトルデータ群管理手段と、
前記ベクトルデータ群管理手段での管理情報に基づいて、入力となるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータから、処理の開始点および終了点を算出する開始点・終了点算出手段と、
前記開始点・終了点算出手段で算出された処理開始点・終了点情報を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、
前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点のピクセル座標位置を算出する対象点算出手段と、
前記対象点算出手段で算出された処理対象点の座標位置の両脇のピクセルの塗りつぶし判定を行う対象点判定手段と、
前記対象点判定手段での判定結果をもとに、対象点の塗りつぶし情報を算出する塗りつぶし情報算出手段と、
対象点の塗りつぶし情報を保存する塗りつぶし情報保存手段と、
前記塗りつぶし情報算出手段で算出された塗りつぶし情報を前記塗りつぶし情報保存手段に登録する塗りつぶし情報登録手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータをもとに、図形描画領域を算出・更新する描画領域算出手段と、
前記描画領域算出手段で算出された描画領域を補正して、最終的に描画を行う領域を求める描画領域補正手段と、
前記描画領域補正手段で得られた描画領域情報、前記塗りつぶし情報保存手段に保存されたデータを用いて、図形を描画する描画手段と、
前記描画手段と連携して動作し、描画手段から取得した描画データを適正なデータとして補正した後、再び描画手段へ補正したデータを戻す描画データ補正手段を具備することを特徴とする図形描画装置。
【請求項７】
入力となるベクトルデータ群を管理するベクトルデータ群管理手段と、
前記ベクトルデータ群管理手段での管理情報に基づいて、入力となるベクトルデータ群から処理対象ベクトルデータを抽出するベクトルデータ抽出手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータから、処理の開始点および終了点を算出する開始点・終了点算出手段と、
前記開始点・終了点算出手段で算出された処理開始点・終了点情報を用いて処理対象点の決定、及び前記ベクトルデータ群管理手段に対象ベクトルの処理の終了の通知を行う対象点管理手段と、
前記対象点管理手段で得られる処理対象点の管理情報をもとに、処理対象点のピクセル座標位置を算出する対象点算出手段と、
前記対象点算出手段で算出された処理対象点の座標位置の両脇のピクセルの塗りつぶし判定を行う対象点判定手段と、
前記対象点判定手段での判定結果をもとに、対象点の塗りつぶし情報を算出する塗りつぶし情報算出手段と、
前記塗りつぶし情報算出手段で算出された塗りつぶし情報を所定の描画規則に従って補正する塗りつぶし情報補正手段と、
対象点の塗りつぶし情報を保存する塗りつぶし情報保存手段と、
前記塗りつぶし情報補正手段で補正された塗りつぶし情報を前記塗りつぶし情報保存手段に登録する塗りつぶし情報登録手段と、
前記ベクトルデータ抽出手段で抽出されたベクトルデータをもとに、図形描画領域を算出・更新する描画領域算出手段と、
前記描画領域算出手段で算出された描画領域を補正して、最終的に描画を行う領域を求める描画領域補正手段と、
前記塗りつぶし情報保存手段に保存された塗りつぶし情報を描画するのに適正なデータとして補正する描画データ補正手段と、
前記描画領域補正手段で得られた描画領域情報、前記描画データ補正手段で補正されたデータを用いて、図形を描画する描画手段を具備することを特徴とする図形描画装置。
【請求項８】
前記対象点管理手段は、前記塗りつぶし情報算出手段から得られる対象点の処理の終了の通知情報を用いて処理対象点の決定を行うことを特徴とする請求項１乃至請求項７記載の図形描写装置。
【請求項９】
入力となるベクトルデータ群に含まれる処理対象ベクトルの処理順序、データを管理するステップと、
管理情報に基づいて、前記ベクトルデータ群から処理対象ベクトルのデータの抽出を行い、
抽出されたベクトルデータの処理順の算出を行うステップと、
算出された処理順序情報を用いて処理対象点の管理、及び対象ベクトルの処理の終了の通知を行うステップと、
処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出するステップと、
算出された塗りつぶし情報を用いて、図形の描画を行うステップを含むことを特徴とする図形描画方法。
【請求項１０】
前記通知を行うステップは、対象点の処理の終了通知情報を用いて処理対象点の管理、対象ベクトルの処理の終了の通知を行うことを特徴とする請求項９記載の図形描画方法。
【請求項１１】
コンピュータを図形描画装置として機能させるためのプログラムであって、
入力となるベクトルデータ群に含まれる処理対象ベクトルの処理順序、データを管理する機能と、
管理情報に基づいて、前記ベクトルデータ群から処理対象ベクトルのデータの抽出を行い、
抽出されたベクトルデータの処理順の算出を行う機能と、
算出された処理順序情報を用いて処理対象点の管理、及び対象ベクトルの処理の終了の通知を行う機能と、
処理対象点の管理情報をもとに、処理対象点の塗りつぶしの可否を判断し、塗りつぶし情報として算出する機能と、
算出された塗りつぶし情報を用いて、図形の描画を行う機能を含みコンピュータに実現させるためのプログラム。
【請求項１２】
前記通知を行う機能は、対象点の処理の終了通知情報を用いて処理対象点の管理、対象ベクトルの処理の終了の通知を行うことを特徴とする請求項１１記載のプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【公開番号】特開２００７−２６４９８８（Ｐ２００７−２６４９８８Ａ）
【公開日】平成１９年１０月１１日（２００７．１０．１１）
【国際特許分類】
【出願番号】特願２００６−８８７０４（Ｐ２００６−８８７０４）
【出願日】平成１８年３月２８日（２００６．３．２８）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成１９年１０月１１日（２００７．１０．１１）
【国際特許分類】
【出願日】平成１８年３月２８日（２００６．３．２８）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]