(57)【特許請求の範囲】
【請求項１】
ベクターイメージを描画するためのベクター図形を囲む図形であるバウンディングボックスを生成する領域図形生成手段と、
前記領域図形生成手段で生成した前記バウンディングボックスの面積を算出する面積演算手段と、
前記ベクター図形の描画処理を実行するためのコマンドを待ち行列内に配置するとともに、前記待ち行列内で隣り合う２つの前記コマンド毎に、描画対象の前記ベクター図形を囲む前記バウンディングボックスの面積の差の絶対値を求めて、該絶対値の総和が最小になるように、前記待ち行列内の前記コマンドの順序を変更するドライバと、
前記待ち行列内に配置された前記コマンドを、先頭の前記コマンドから順に受け取って、前記ベクター図形の描画処理を行うアクセラレータと、
を備えることを特徴とするベクターイメージ描画装置。
【請求項２】
前記領域図形生成手段は、前記ベクター図形を囲む矩形をバウンディングボックスとして生成することを特徴とする請求項１に記載のベクターイメージ描画装置。
【請求項３】
前記バウンディングボックスを座標変換する座標変換手段を備え、
前記ベクター図形の描画処理には、前記ベクター図形の座標変換処理が含まれ、
前記面積演算手段は、前記座標変換手段で座標変換したのちのバウンディングボックスの面積を算出することを特徴とする請求項１または２に記載のベクターイメージ描画装置。
【請求項４】
前記領域図形生成手段は、座標変換する前の前記ベクター図形を囲む前記バウンディングボックスを算出し、
前記座標変換手段は、前記領域図形生成手段で生成したバウンディングボックスを座標変換することを特徴とする請求項３に記載のベクターイメージイメージ装置。
【請求項５】
前記ドライバは、前記待ち行列内に最後に配置された前記コマンドを含めて、前記待ち行列内で隣り合う２つの前記コマンド毎に、描画対象の前記ベクター図形を囲む前記バウンディングボックスの面積の差の絶対値を求めるとともに、該絶対値の総和が最小になるように、前記待ち行列内の前記コマンドの順序を変更することを特徴とする請求項１ないし４のいずれか１項に記載のベクターイメージ描画装置。
【請求項６】
ベクターイメージ描画装置がベクターイメージを描画するためにベクター図形の描画処理を行う描画方法であって、
領域図形生成手段が、ベクターイメージを描画するためのベクター図形を囲む図形であるバウンディングボックスを生成する領域図形生成ステップと、
面積演算手段が、前記領域図形生成ステップで生成した前記バウンディングボックスの面積を算出する面積演算ステップと、
ドライバが、前記ベクター図形の描画処理を実行するためのコマンドを待ち行列内に配置するとともに、前記待ち行列内で隣り合う２つの前記コマンド毎に、描画対象の前記ベクター図形を囲む前記バウンディングボックスの面積の差の絶対値を求めて、該絶対値の総和が最小になるように、前記待ち行列内の前記コマンドの順序を変更するコマンド配置ステップと、
アクセラレータが、前記待ち行列内に配置された前記コマンドを、先頭の前記コマンドから順に受け取って、前記ベクター図形の描画処理を行う描画ステップと、
を備えることを特徴とするベクターイメージ描画方法。
【請求項７】
前記領域図形生成ステップでは、前記領域図形生成手段は、前記ベクター図形を囲む矩形をバウンディングボックスとして生成することを特徴とする請求項６に記載のベクターイメージ描画方法。
【請求項８】
座標変換手段が、前記バウンディングボックスを座標変換する座標変換ステップを備え、
前記ベクター図形の描画処理には、前記ベクター図形の座標変換処理が含まれ、
前記面積演算ステップでは、前記面積演算手段は、前記座標変換ステップで座標変換したのちのバウンディングボックスの面積を算出することを特徴とする請求項６または７に記載のベクターイメージ描画方法。
【請求項９】
前記領域図形生成ステップでは、前記領域図形生成手段は、座標変換する前のベクター図形を囲むバウンディングボックスを算出し、
前記座標変換ステップでは、前記座標変換手段は、前記領域図形生成ステップで生成したバウンディングボックスを座標変換することを特徴とする請求項８に記載のベクターイメージ描画方法。
【請求項１０】
前記コマンド配置ステップでは、前記ドライバは、前記待ち行列内に最後に配置された前記コマンドを含めて、前記待ち行列内で隣り合う２つの前記コマンド毎に、描画対象の前記ベクター図形を囲む前記バウンディングボックスの面積の差の絶対値を求めて、該絶対値の総和が最小になるように、前記待ち行列内の前記コマンドの順序を変更することを特徴とする請求項６ないし９のいずれか１項に記載のベクターイメージ描画方法。
【請求項１１】
コンピュータを、
ベクターイメージを描画するためのベクター図形を囲む図形であるバウンディングボックスを生成する領域図形生成手段、
前記領域図形生成手段で生成した前記バウンディングボックスの面積を算出する面積演算手段、
前記ベクター図形の描画処理を実行するためのコマンドを待ち行列内に配置するとともに、前記待ち行列内で隣り合う２つの前記コマンド毎に、描画対象の前記ベクター図形を囲む前記バウンディングボックスの面積の差の絶対値を求めて、該絶対値の総和が最小になるように、前記待ち行列内の前記コマンドの順序を変更するドライバ、
前記待ち行列内に配置された前記コマンドを、先頭の前記コマンドから順に受け取って、前記ベクター図形の描画処理を行うアクセラレータ、
として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ベクターイメージを表示するためのベクターイメージ描画装置、ベクターイメージ描画方法およびプログラムに関する。
【背景技術】
【０００２】
データ化されたイメージに対して、ベクタースキャン（スクリーンにレーザなどで図形を描く処理）やラスタースキャン（走査線で順次画素を描く処理）などの処理を実行することでディスプレイ上に画像を表示することが行われており、前記データ化されたイメージを描画する手法として、ベクターグラフィックスがある。このベクターグラフィックスによれば、直線、ベジェ曲線、楕円弧といったベクター図形がデータ化されることで、ベクターイメージが描画されるようになっている。
ベクターイメージの描画を行う装置として、受け取った描画命令に対して複数のステージが一連の処理を行うパイプを備えた描画装置があり、特許文献１、２、３には、ベクター図形の色変換、ベクター図形の拡大・縮小処理、ベクター図形の回転などの処理を行うステージを備えたパイプが開示されている。
【０００３】
また、ベクターイメージの描画速度を向上させる技術として、以下の技術がある。
【０００４】
例えば特許文献４には、描画データをビットマップデータに展開する互いに並列処理可能な複数のラスタライザと、各ラスタライザに文字描画命令を渡す制御装置とを備えた画像処理装置が開示されている。この画像処理装置においては、制御装置が、文字の生成処理が終了したラスタライザに描画命令を送ることで、各ラスタライザで処理待ちが発生することを防止している。
【０００５】
また特許文献５には、互いに異なるオブジェクトの処理を行う複数のパイプと、各パイプのステージの順序をソートするトポロジーソータとが設けられた装置が開示されている。この装置においては、トポロジーソータは、各パイプの全てのステージで処理が実行されるように、各パイプのステージの順序をソートすることで、パイプの処理時間の短縮を図っている。
【特許文献１】特開２００６−２５１３１１号公報
【特許文献２】特開２００６−３３８５０４号公報
【特許文献３】特開平１１−３３９０２３号公報
【特許文献４】特開平１０−２２８２６９号公報
【特許文献５】特開２００１−１８４５００号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
参考文献１（Open VG Specification Version 1.01  2007年1月26日、pp.4-6）には、ベクターイメージの描画装置の一例が記載されており、この描画装置の構成は、図７に示すように解釈される。図７に示す描画装置６０は、ベクターグラフィックスアプリケーション６１、ベクターグラフィックスライブラリ６２、ドライバ６３、ベクターグラフィックスアクセラレータ６４で構成されている。ベクターグラフィックスライブラリ６２は、ＤＭＡ（Direct Memory Access）コマンド生成手段６５を含んでいる。この描画装置６０では、ベクターグラフィックスアプリケーション６１が、直線、ベジェ曲線、楕円弧といったベクター図形を形作る情報６（以下、パス６と記す）、座標変換行列７、属性８を、ベクターグラフィックスライブラリ６２に送る。
【０００７】
ベクターグラフィックスライブラリ６２のＤＭＡコマンド生成手段６５は、それらの情報から、ベクターグラフィックスアクセラレータ６４への命令方式のコマンドであるＤＭＡコマンドＡを作成する。そして、ベクターグラフィックスライブラリ６２は、ＤＭＡコマンドＡをドライバ６３に送る。ドライバ６３は、受け取ったＤＭＡコマンドＡを、シーケンシャルにベクターグラフィックスアクセラレータ６４に送る。
【０００８】
ベクターグラフィックスアクセラレータ６４は、受け取ったＤＭＡコマンドＡを順次処理して、ベクターイメージを描画するためのベクター図形の描画処理を行う。ベクターグラフィックスアクセラレータ６４は、ＤＭＡコマンドＡに対して一連の処理を行う複数のステージを備えたパイプであり、ＤＭＡコマンドＡが下位のステージへ移って初期ステージが待機状態になることに応じて、新たなＤＭＡコマンドＡが初期ステージに投入されるようになっている。
【０００９】
ここで、ベクター図形の描画を行うパイプにおいて、各ステージがＤＭＡコマンドを処理する時間は、該ＤＭＡコマンドの処理により描画されるベクター図形（以下、描画対象のベクター図形）の大きさに比例する。このため、描画対象のベクター図形の大きさが大きく異なるＤＭＡコマンドがパイプに連続して投入された場合には、先行のＤＭＡコマンドに対して上位のステージが処理を行う時間と、後行のＤＭＡコマンドに対して下位のステージが処理を行う時間との間で大きな差が生じる。これにより、下位のステージへのＤＭＡコマンドの移動が迅速に行われず、パイプにおける各ステージの待ち時間の総和が大きくなる。この結果、パイプ全体の処理時間が長くなるという問題が生じる。
【００１０】
本発明は上述のような状況に鑑みてなされたもので、パイプの描画処理時間を短縮させることが可能なベクターイメージ描画装置、ベクターイメージ描画方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記の目的を達成するために、本発明の第１の観点に係るベクターイメージ描画装置は、
ベクターイメージを描画するためのベクター図形を囲む図形であるバウンディングボックスを生成する領域図形生成手段と、
前記領域図形生成手段で生成した前記バウンディングボックスの面積を算出する面積演算手段と、
前記ベクター図形の描画処理を実行するためのコマンドを待ち行列内に配置するとともに、前記待ち行列内で隣り合う２つの前記コマンド毎に、描画対象の前記ベクター図形を囲む前記バウンディングボックスの面積の差の絶対値を求めて、該絶対値の総和が最小になるように、前記待ち行列内の前記コマンドの順序を変更するドライバと、
前記待ち行列内に配置された前記コマンドを、先頭の前記コマンドから順に受け取って、前記ベクター図形の描画処理を行うアクセラレータと、
を備えることを特徴とする。
【００１２】
本発明の第２の観点に係るベクターイメージ描画方法は、
ベクターイメージ描画装置がベクターイメージを描画するためにベクター図形の描画処理を行う描画方法であって、
領域図形生成手段が、ベクターイメージを描画するためのベクター図形を囲む図形であるバウンディングボックスを生成する領域図形生成ステップと、
面積演算手段が、前記領域図形生成ステップで生成した前記バウンディングボックスの面積を算出する面積演算ステップと、
ドライバが、前記ベクター図形の描画処理を実行するためのコマンドを待ち行列内に配置するとともに、前記待ち行列内で隣り合う２つの前記コマンド毎に、描画対象の前記ベクター図形を囲む前記バウンディングボックスの面積の差の絶対値を求めて、該絶対値の総和が最小になるように、前記待ち行列内の前記コマンドの順序を変更するコマンド配置ステップと、
アクセラレータが、前記待ち行列内に配置された前記コマンドを、先頭の前記コマンドから順に受け取って、前記ベクター図形の描画処理を行う描画ステップと、
を備えることを特徴とする。
【００１３】
本発明の第３の観点に係るプログラムは、コンピュータを、
ベクターイメージを描画するためのベクター図形を囲む図形であるバウンディングボックスを生成する領域図形生成手段、
前記領域図形生成手段で生成した前記バウンディングボックスの面積を算出する面積演算手段、
前記ベクター図形の描画処理を実行するためのコマンドを待ち行列内に配置するとともに、前記待ち行列内で隣り合う２つの前記コマンド毎に、描画対象の前記ベクター図形を囲む前記バウンディングボックスの面積の差の絶対値を求めて、該絶対値の総和が最小になるように、前記待ち行列内の前記コマンドの順序を変更するドライバ、
前記待ち行列内に配置された前記コマンドを、先頭の前記コマンドから順に受け取って、前記ベクター図形の描画処理を行うアクセラレータ、
として機能させることを特徴とする。
【発明の効果】
【００１４】
本発明のベクターイメージ描画装置によれば、待ち行列内の描画処理の順序は、隣り合う処理どうしのバウンディングボックスの面積の差の総和が最小となる順序に設定されるため、待ち行列内で隣り合う処理の間における描画対象のベクター図形の大きさの差は小さくなる。これにより、パイプが連続して処理するベクター図形の大きさの変化は小さく抑えられるため、パイプの各ステージにおける処理時間のばらつきが小さく抑えられて、上位のステージから下位のステージへ描画処理が迅速に移行して、パイプにおける各ステージの待ち時間の総和が小さくなる。この結果、パイプの描画処理時間が短くなる。
【発明を実施するための最良の形態】
【００１５】
以下、この発明の実施の形態について図面を参照しながら詳細に説明する。なお、図中同一または相当部分には同一符号を付し、その説明は繰り返さない。端瑞
【００１６】
図１は、本発明の実施の形態に係るベクターイメージ描画装置１の構成の一例を示すブロック図である。
【００１７】
ベクターイメージ描画装置１は、ベクターグラフィックス（以下、ＶＧという）アプリケーション２と、ＶＧライブラリ３と、ドライバ４と、ＶＧアクセラレータ５とを備える。
【００１８】
ＶＧライブラリ３は、バウンディングボックス計算部３１と、座標変換部３２と、ＤＭＡコマンド生成部３３とを含む。ドライバ４は、ＤＭＡコマンド並べ替え部４１を含む。
【００１９】
次に、図１を参照してベクターイメージ描画装置１の動作について説明する。
【００２０】
ＶＧアプリケーション２は、直線、ベジェ曲線、楕円弧といったベクター図形を形作る情報であるパス６、座標変換行列７、色や線幅などの属性８を生成して、ＶＧライブラリ３に送る。
【００２１】
ＶＧライブラリ３がパス６を受け取ると、バウンディングボックス計算部３１は、パス６を解析して、バウンディングボックス１０を生成する。図２は、バウンディングボックス１０の一例を示している。図２において、９はパス６によって形作られるベクター図形を示しており、該ベクター図形９を囲むようにバウンディングボックス１０が生成されている。
【００２２】
図１を参照して、座標変換部３２は、バウンディングボックス計算部３１によって生成されたバウンディングボックス１０の４隅の頂点１０ａ（図２参照）の座標それぞれに対して、座標変換行列７を掛けて、４隅の頂点１０ａの座標変換を行う。この座標変換により、バウンディングボックス１０の拡大縮小・回転・移動が行われる。座標変換行列７は、バウンディングボックス１０の拡大縮小を図る変換行列と、バウンディングボックス１０の回転を図る変換行列と、バウンディングボックス１０の移動を図る変換行列とが合成されたものになっている。
【００２３】
そして、座標変換部３２は、座標変換されたバウンディングボックスの４隅の頂点に基づき、座標変換されたバウンディングボックスの面積Ｓを算出する。
【００２４】
また、ＤＭＡコマンド生成部３３は、パス６、座標変換行列７、属性８を、ＶＧアクセラレータ５への命令形式のコマンドであるＤＭＡコマンドＡに変換する。
【００２５】
そして、ＶＧライブラリ３は、座標変換部３２によって座標変換されたバウンディングボックスの面積Ｓと、ＤＭＡコマンド生成部３３によって生成されたＤＭＡコマンドＡとを、ドライバ４に渡す。この際、ＶＧライブラリ３からドライバ４に渡されたＤＭＡコマンドＡは、ＶＧアクセラレータ５の処理順序を設定するための待ち行列Ｂに配置される。以下、特定のＤＭＡコマンドＡに対して、このＤＭＡコマンドＡと共にＶＧライブラリ３からドライバ４に送られたバウンディングボックスの面積Ｓを、ＤＭＡコマンドＡに対応するバウンディングボックスの面積Ｓと適宜記す。
【００２６】
そして、ＶＧアクセラレータ５は、待ち行列Ｂ内に配置されたＤＭＡコマンドＡを、先頭のＤＭＡコマンドＡから順に受け取ってベクター図形の描画処理を行う。
【００２７】
ここで、ＶＧアクセラレータ５は、ＤＭＡコマンドＡに対して一連の処理を行う複数のステージを備えたパイプとなっている。このパイプには、ＤＭＡコマンドＡの描画対象となるベクター図形の座標変換処理を行うステージが含まれており、これ以降のステージでは前記座標変換処理が行われたベクター図形に対して処理が実行されるようになっている。
【００２８】
そして座標変換部３２により４隅１０ａが座標変換されたバウンディングボックスは、前記座標変換処理が行われたベクター図形を囲むようになっている。これに基づき本実施形態では、前記座標変換されたバウンディングボックスの面積Ｓを、前記座標変換処理が行われたベクター図形の大きさを表す指標と位置づけ、ＶＧアクセラレータ５が連続して処理するベクター図形の大きさの変化を小さくすべく、待ち行列Ｂ内のＤＭＡコマンドＡの順序を、バウンディングボックスの面積Ｓに応じて並び替えるようになっている。具体的には、ドライバ４がバウンディングボックスの面積ＳとＤＭＡコマンドＡとを受け取ると、ＤＭＡコマンド並べ替え部４１は、ドライバ４が受け取ったバウンディングボックスの面積Ｓと、ＶＧアクセラレータ５が処理中のＤＭＡコマンドＡに対応するバウンディングボックスの面積Ｓと、待ち行列Ｂ内に既に配置されていたＤＭＡコマンドＡに対応するバウンディングボックスの面積Ｓとを基に、待ち行列Ｂ内のＤＭＡコマンドＡの順序を変更する。より具体的には、ＤＭＡコマンド並べ替え部４１は、ＶＧアクセラレータ５がドライバ４から最後に受け取ったＤＭＡコマンドＡを含めて、待ち行列Ｂ内で隣り合うＤＭＡコマンドＡどうしのバウンディングボックスの面積Ｓの差の総和が最小になるように、待ち行列Ｂ内のＤＭＡコマンドＡの順序を変更する。
【００２９】
図３は、本実施の形態に係るベクターイメージ描画装置１の物理的な構成の一例を示すブロック図である。本発明に係るベクターイメージ描画装置１は、一般的なコンピュータ装置と同様のハードウェア構成によって実現することができる。ベクターイメージ描画装置１は、図３に示すように、制御部５１、主記憶部５２、外部記憶部５３、操作部５４、表示装置５５および入出力部５６を備える。主記憶部５２、外部記憶部５３、操作部５４、表示装置５５および入出力部５６はいずれも内部バス５０を介して制御部５１に接続されている。
【００３０】
制御部５１は、ＣＰＵ（Central Processing Unit）等から構成され、外部記憶部５３に記憶されているプログラムに従って、ベクターイメージを描画するための処理を実行する。
【００３１】
主記憶部５２は、ＲＡＭ（Random-Access Memory）等から構成され、外部記憶部５３に記憶されているプログラムをロードし、制御部５１の作業領域として用いられる。図１に示したパス６、座標変換行列７、属性８、面積Ｓ、ＤＭＡコマンドＡは、主記憶部５２の中に記憶される。
【００３２】
外部記憶部５３は、フラッシュメモリ、ハードディスク、ＤＶＤ−ＲＡＭ（Digital Versatile Disc Random-Access Memory）、ＤＶＤ−ＲＷ（Digital Versatile Disc ReWritable）等の不揮発性メモリから構成され、前記の処理を制御部５１に行わせるためのプログラムを予め記憶し、また、制御部５１の指示に従って、このプログラムが記憶するデータを制御部５１に供給し、制御部５１から供給されたデータを記憶する。
【００３３】
操作部５４はキーボードおよびマウスなどのポインティングデバイス等と、キーボードおよびポインティングデバイス等を内部バス５０に接続するインターフェース装置から構成されている。操作部５４を介して、ベクターイメージの作成、入力、送受信などの指示、表示するベクターイメージの指定、描画領域の範囲、拡大率、描画領域の表示装置における位置などが入力され、制御部５１に供給される。
【００３４】
表示装置５５は、ＣＲＴ（Cathode Ray Tube）またはＬＣＤ（Liquid Crystal Display）などから構成され、描画されたベクターイメージを表示する。
【００３５】
入出力部５６は、無線送受信機、無線モデムまたは網終端装置、およびそれらと接続するシリアルインタフェースまたはＬＡＮ（Local Area Network）インタフェース等から構成されている。入出力部５６を介して、ベクターイメージを受信し、また送信できる。
【００３６】
本発明によるベクターイメージ描画装置１は、上記のベクターイメージを描画する機能を実現する回路を組み込んだＬＳＩ（Large Scale Integration）等のハードウェア部品から構成される回路を実装して、電子回路として構成することができる。
【００３７】
また本発明によるベクターイメージ描画装置１は、上記のベクターイメージを描画する機能をプログラミングにより実現することが可能なＬＳＩであるＦＰＧＡ（Field Programmable Gate Array）を実装していてもよい。
【００３８】
また、上記の各機能を行うベクターイメージ描画プログラムを、コンピュータ処理装置上の制御部５１で実行することにより、ソフトウェア的にベクターイメージ描画装置１を実現することができる。その場合、制御部５１のＣＰＵは、外部記憶部５３に格納されているベクターイメージ描画プログラムを、主記憶部５２にロードして実行し、各部の動作を制御して上記の各機能を行わせることによって、ベクターイメージ描画装置１をソフトウェア的に実現する。
【００３９】
次に、ドライバ４のＤＭＡコマンド並べ替え部４１が実行するＤＭＡコマンドＡの並べ替え処理のアルゴリズムを、具体的に説明する。なお、ＤＭＡコマンドＡの並べ替え処理は、ベクターイメージ描画プログラムが、主記憶部５２、外部記憶部５３、操作部５４、表示装置５５および入出力部５６を資源として用いて、制御部５１の上で動作することによって行う。
【００４０】
図４は、ＤＭＡコマンドＡの並べ替え処理の動作の一例を示すフローチャートであり、図５は、図４の処理による並べ替え操作を説明する図である。
【００４１】
図５は、ＶＧアクセラレータ５によって、ＤＭＡコマンドＡ１を処理しているときに、ＤＭＡコマンドＡ２、Ａ３、Ａ４が待ち行列Ｂに順次送られていく状態を示している。以下では、図４に示す並び替え処理について、図５に示すようにＤＭＡコマンドＡ２、Ａ３、Ａ４が待ち行列Ｂに送られる際に実行される処理を例に説明する。なお図５では、待ち行列Ｂの深さは３段（待ち行列Ｂ内に３つのＤＭＡコマンドＡが配置できる状態）になっている。また、ＤＭＡコマンドＡを示す四角の内部に表示された数字は、各ＤＭＡコマンドＡと同時にドライバ４に送られたバウンディングボックスの面積Ｓを示している。ＤＭＡコマンドＡ１、Ａ２、Ａ３、Ａ４に対応するバウンディングボックスの面積Ｓは、それぞれ５、１、３、２になっている。
【００４２】
まず、図５の３０１に示すように、ＤＭＡコマンドＡ２が待ち行列Ｂに送られると、すなわちドライバ４がＤＭＡコマンドＡ２を受け取ると（ステップＳ２０１）、ＤＭＡコマンド並べ替え部４１は、待ち行列Ｂが空であるか否かを判断する（ステップＳ２０２）。この際、ステップＳ２０２では、待ち行列Ｂが空であることからＹＥＳと判断して、待ち行列Ｂの先頭にＤＭＡコマンドＡ２を配置して（ステップＳ２０３）、図４に示す処理を終了する。  
【００４３】
次に図５に示す３０２のように、ＤＭＡコマンドＡ３が待ち行列Ｂに送られてくると、すなわちドライバ４がＤＭＡコマンドＡ３を受け取ると（ステップＳ２０１）、続くステップＳ２０２では、待ち行列ＢにＤＭＡコマンドＡ２が既に配置されていることから、ＮＯと判断して、ステップＳ２０４に移行する。
【００４４】
次に、ＤＭＡコマンド並べ替え部４１は、待ち行列Ｂ内で配置され得るＤＭＡコマンドＡの順序を全て抽出する（ステップＳ２０４）。図６に示すパターンＰ１は、この際に抽出されたＤＭＡコマンドＡの順序を示している。パターンＰ１の１行目Ｌ１に示す順序では、既に待ち行列Ｂに配置されていたＤＭＡコマンドＡ２が待ち行列Ｂの先頭に位置し、新たに待ち行列Ｂに送られてきたＤＭＡコマンドＡ３が待ち行列Ｂの２番目に位置している。またパターンＰ１の２行目Ｌ２に示す順序では、待ち行列Ｂ内の順序が、１行目Ｌ１に示す順序とは逆になっており、ＤＭＡコマンドＡ３が先頭に位置し、ＤＭＡコマンドＡ２が２番目に位置している。なお図６に示す（）内の数字は、各ＤＭＡコマンドＡが対応するバウンディングボックスの面積Ｓを示している。
【００４５】
図４を参照して、ステップＳ２０４が実行されると、ＤＭＡコマンド並べ替え部４１は、隣り合うＤＭＡコマンドＡどうしのバウンディングボックスの面積Ｓの差を算出する順序として、パターンＰ１の１行目Ｌ１に示す順序を選択する（ステップＳ２０５）。
【００４６】
次に、ＤＭＡコマンド並べ替え部４１は、ステップＳ２０５で選択した順序（パターンＰ１の１行目Ｌ１に示す順序）において、待ち行列Ｂの先頭に位置するＤＭＡコマンドＡ２を、隣り合うＤＭＡコマンドＡどうしのバウンディングボックスの面積差を算出する基準となるＤＭＡコマンド（以下、面積差算出基準のＤＭＡコマンド）として選択する（ステップＳ２０６）。
【００４７】
次に、ＤＭＡコマンド並べ替え部４１は、ステップＳ２０６で選択された面積差算出基準のＤＭＡコマンドＡ２が、待ち行列Ｂの先頭に位置しているか否かを判断する（ステップＳ２０７）。この際、パターンＰ１の１行目Ｌ１に示す順序で、ＤＭＡコマンドＡ２は待ち行列Ｂの先頭に位置しているため、ステップＳ２０７ではＹＥＳと判断して、ステップＳ２０８に移行する。
【００４８】
そして、ＤＭＡコマンド並べ替え部４１は、面積差算出基準のＤＭＡコマンドＡ２に対応するバウンディングボックスの面積Ｓ（１）と、ＶＧアクセラレータ５が処理中のＤＭＡコマンドＡ１に対応するバウンディングボックスの面積Ｓ（５）との面積差を算出する（ステップＳ２０８）。この際、｜５−１｜＝４の計算から、４の面積差が算出される。
【００４９】
次に、ＤＭＡコマンド並べ替え部４１は、バウンディングボックスの面積差を算出する順序（パターンＰ１の１行目Ｌ１に示す順序）において、隣り合うＤＭＡコマンドＡどうしのバウンディングボックスの面積Ｓの差をすべて計算したか否かを判断する（ステップＳ２０９）。この際、ＤＭＡコマンドＡ２に対応するバウンディングボックスの面積Ｓ（１）と、ＤＭＡコマンドＡ３に対応するバウンディングボックスの面積Ｓ（３）との差を計算していないので、ＤＭＡコマンド並べ替え部４１は、ＮＯと判断して、ステップＳ２１０に移行する。
【００５０】
そして、ＤＭＡコマンド並べ替え部４１は、面積差算出基準のＤＭＡコマンドＡを変更する（ステップＳ２１０）。具体的には、バウンディングボックスの面積差を算出する順序（パターンＰ１の１行目Ｌ１に示す順序）における待ち行列Ｂ内の並びで、ＤＭＡコマンドＡ２の１つ後に位置するＤＭＡコマンドＡ３に変更する。
【００５１】
次に、ＤＭＡコマンド並べ替え部４１は、再びステップＳ２０７の処理に移行する。この際、パターンＰ１の１行目Ｌ１に示す順序では、面積差算出基準のＤＭＡコマンドＡ３は、待ち行列Ｂの２番目に位置していることから、ＤＭＡコマンド並べ替え部４１は、ＮＯと判断して、ステップＳ２１１に移行する。
【００５２】
このステップＳ２１１において、ＤＭＡコマンド並べ替え部４１は、ＤＭＡコマンドＡ３に対応するバウンディングボックスの面積Ｓ（３）と、ＤＭＡコマンドＡの１つ前に位置するＤＭＡコマンドＡ２に対応するバウンディングボックスの面積Ｓ（１）との面積差を算出する。この際、｜３−１｜＝２の計算から、２の面積差が算出される。
【００５３】
次に、ＤＭＡコマンド並べ替え部４１は、ステップＳ２０９に移行する。この際には、パターンＰ１の１行目に示す順序では、隣り合うＤＭＡコマンドＡどうしのバウンディングボックスの面積Ｓの差がすべて計算済みであることから、ＤＭＡコマンド並べ替え部４１は、ＹＥＳと判断して、ステップＳ２１２に移行する。
【００５４】
そして、ＤＭＡコマンド並べ替え部４１は、ステップＳ２０４で抽出した全ての順序について、バウンディングボックスの面積差を計算したか否かを判断する（ステップＳ２１２）。この際、パターンＰ１の２行目Ｌ２に示す順序については、バウンディングボックスの面積差の算出を行っていないため、ＤＭＡコマンド並べ替え部４１は、ＮＯと判断して、ステップＳ２１３に移行する。
【００５５】
そして、ＤＭＡコマンド並べ替え部４１は、バウンディングボックスの面積差を算出する順序を変更する（ステップＳ２１３）。具体的には、ステップＳ２０３で抽出された全ての順序（パターンＰ１に示す順序）のうち、未だバウンディングボックスの面積差を算出する順序として選択されていない２行目Ｌ２に示す順序に変更する。
【００５６】
そして、ＤＭＡコマンド並べ替え部４１は、再びステップＳ２０６の処理に移行する。
【００５７】
これ以降、パターンＰ１の２行目Ｌ２に示す順序に対して、上述したＳ２０７（ＹＥＳ）→Ｓ２０８→Ｓ２０９（ＮＯ）→Ｓ２１０→Ｓ２０７（ＮＯ）→Ｓ２１１→Ｓ２０９（ＹＥＳ）→Ｓ２１２の処理が実行される。この処理により、ＤＭＡコマンドＡ３に対応するバウンディングボックスの面積Ｓ（３）と、ＤＭＡコマンドＡ１に対応するバウンディングボックスの面積Ｓ（５）との面積差として、｜３−５｜＝２の計算から、２が算出され、さらにＤＭＡコマンドＡ２に対応するバウンディングボックスの面積Ｓ（１）と、ＤＭＡコマンドＡ３に対応するバウンディングボックスの面積Ｓ（３）との面積差として、｜１−３｜＝２の計算から、２が算出される。
【００５８】
そして、ＤＭＡコマンド並べ替え部４１は、パターンＰ１の２行目Ｌ２に示す順序で、隣り合うＤＭＡコマンドＡどうしのバウンディングボックスの面積Ｓの差をすべて計算すると、ステップＳ２１２でＹＥＳと判断して、ステップＳ２１４に移行する。
【００５９】
このステップＳ２１４において、ＤＭＡコマンド並べ替え部４１は、ステップＳ２０４で抽出した全ての順序について、バウンディングボックスの面積差の合計を計算する(ステップＳ２１４)。この際、パターン１の１行目Ｌ１に示す順序における面積差の合計は、４＋２＝６の計算から６が算出され、２行目Ｌ２に示す順序における面積差の合計は、２＋２＝４の計算から４が算出される。
【００６０】
次に、ＤＭＡコマンド並べ替え部４１は、待ち行列ＢにおけるＤＭＡコマンドＡの順序を、ステップＳ２０４で抽出した順序のうちバウンディングボックスの面積差の合計が最も小さな順序に並び替える(ステップＳ２１５)。この際、図６のパターンＰ１に示す順序では、１行目Ｌ１に示す順序の面積差の合計は６であり、２行目Ｌ２に示す順序の面積差の合計は４であるため、ＤＭＡコマンド並べ替え部４１は、待ち行列ＢにおけるＤＭＡコマンドＡの順序を、２行目Ｌ２に示す順序に並び替える。この結果、待ち行列Ｂでは、ＤＭＡコマンドＡ３が先頭に位置し、ＤＭＡコマンドＡ２が２番目に位置するようになる。
【００６１】
この後、図５の３０３に示すように、対応するバウンディングボックスの面積が２であるＤＭＡコマンドＡ４が待ち行列Ｂに送られて来たときも、上記と同様の流れで図４に示す処理が実行される。図６に示すパターンＰ２は、この処理のステップＳ２０４で抽出されたＤＭＡコマンドＡの順序の全てと、ステップＳ２１４で計算された各順序における面積差の合計とを示している。パターンＰ２では、６行目Ｌ３に示す順序Ｌ３がバウンディングボックスの面積差の合計が最も小さくなっている。このため、ステップＳ２１５の処理により、待ち行列Ｂ内のＤＭＡコマンドの順序が、６行目Ｌ３に示す順序に変更される。図５の３０４は、待ち行列Ｂ内のＤＭＡコマンドの順序が、６行目Ｌ３に示す順序に並び替えられた状態を示している。
【００６２】
なお図４に示したステップＳ２０８、２１１では、バウンディングボックスの面積差は、ステップＳ２１５におけるＤＭＡコマンドＡの並べ替えを実行することが可能な程度の精度で求められればよい。例えば、ベクターアクセラレータによって描画処理が行われるベクター図形がベジェ曲線や楕円弧である場合には、該ベジェ曲線等を近似的に表現する分割直線の数を少なくすることで、バウンディングボックスの面積Ｓの算出は容易になる。
【００６３】
以上、本実施形態によれば、待ち行列Ｂ内のＤＭＡコマンドＡの順序は、隣り合うＤＭＡコマンドＡどうしのバウンディングボックスの面積Ｓの差の総和が最小となる順序に設定されるため、待ち行列Ｂ内で隣り合うＤＭＡコマンドＡの間における描画対象のベクター図形の大きさの差は小さくなる。このため、ＶＧアクセラレータ５が連続して処理するベクター図形の大きさの変化は小さくなるため、ＶＧアクセラレータ５における各ステージの処理時間のばらつきが小さく抑えられる。これにより、上位のステージから下位のステージにＤＭＡコマンドＡが迅速に移行して、ＶＧアクセラレータ５における各ステージの待ち時間の総和が小さくなる。この結果、ＶＧアクセラレータ５の描画処理時間が短くなる。
【００６４】
また、本実施形態では、ＶＧアクセラレータ５に最後に投入したＤＭＡコマンドＡを含めて、隣り合う処理どうしのバウンディングボックスの面積の差の総和が最小になるように、待ち行列内のＤＭＡコマンドＡの順序を変更するようにしている。このため、ベクターグラフィックスアクセラレータの処理中に、待ち行列Ｂに新たなＤＭＡコマンドＡが送られてきたときでも、ＶＧアクセラレータ５に連続して処理させるベクター図形の大きさの変化を小さく抑えることが出来る。
【００６５】
以上、好ましい実施の形態をあげて本発明を説明したが、本発明は必ずしも、上記実施の形態に限定されるものではなく、その技術的思想の範囲内において様々に変形して実施することができる。
【００６６】
例えば、上述した実施の形態では、バウンディングボックス計算部３１によって生成されたバウンディングボックスを座標変換することで、座標変換処理後のベクター図形を囲むバウンディングボックスを生成することとしたが、座標変換処理後のベクター図形を囲むバウンディングボックスをバウンディングボックス計算部３１に生成させるようにしてもよい。この場合、座標変換部３２によるバウンディングボックスの座標変換は省略され、座標変換部３２は、バウンディングボックス計算部３１に生成されたバウンディングボックスの面積を算出して、ドライバ４に送る。
【００６７】
本発明の好適な変形として、以下の構成が含まれる。
【００６８】
本発明の第１の観点に係るベクター画像描画装置について、好ましくは、
前記領域図形生成手段は、前記ベクター図形を囲む矩形をバウンディングボックスとして生成することを特徴とする。
【００６９】
さらに好ましくは、
前記バウンディングボックスを座標変換する座標変換手段を備え、
前記ベクター図形の描画処理には、前記ベクター図形の座標変換処理が含まれ、
前記面積演算手段は、前記座標変換手段で座標変換したのちのバウンディングボックスの面積を算出することを特徴とする。
【００７０】
さらに好ましくは、
前記領域図形生成手段は、座標変換する前の前記ベクター図形を囲む前記バウンディングボックスを算出し、
前記座標変換手段は、前記領域図形生成手段で生成したバウンディングボックスを座標変換することを特徴とする。
【００７１】
さらに好ましくは、
前記ドライバは、前記待ち行列内に最後に配置された前記コマンドを含めて、前記待ち行列内で隣り合う２つの前記コマンド毎に、描画対象の前記ベクター図形を囲む前記バウンディングボックスの面積の差の絶対値を求めて、該絶対値の総和が最小になるように、前記待ち行列内の前記コマンドの順序を変更することを特徴とする。
【００７２】
本発明の第２の観点に係るベクターイメージ描画方法について、好ましくは、
前記領域図形生成ステップでは、前記領域図形生成手段は、前記ベクター図形を囲む矩形をバウンディングボックスとして生成することを特徴とする。
【００７３】
さらに好ましくは、
座標変換手段が、前記バウンディングボックスを座標変換する座標変換ステップを備え、
前記ベクター図形の描画処理には、前記ベクター図形の座標変換処理が含まれ、
前記面積演算ステップでは、前記面積演算手段は、前記座標変換ステップで座標変換したのちのバウンディングボックスの面積を算出することを特徴とする。
【００７４】
さらに好ましくは、
前記領域図形生成ステップでは、前記領域図形生成手段は、座標変換する前のベクター図形を囲むバウンディングボックスを算出し、
前記座標変換ステップでは、前記座標変換手段は、前記領域図形生成ステップで生成したバウンディングボックスを座標変換することを特徴とする。
【００７５】
さらに好ましくは、
前記コマンド配置ステップでは、前記ドライバは、前記待ち行列内に最後に配置された前記コマンドを含めて、前記待ち行列内で隣り合う２つの前記コマンド毎に、描画対象の前記ベクター図形を囲む前記バウンディングボックスの面積の差の絶対値を求めて、該絶対値の総和が最小になるように、前記待ち行列内の前記コマンドの順序を変更することを特徴とする。
【００７６】
なお、前記のハードウェア構成やフローチャートは一例であり、任意に変更および修正が可能である。
【００７７】
また、制御部５１、主記憶部５２、外部記憶部５３、操作部５４、入出力部５６および内部バス５０などから構成されるベクターイメージ描画装置１の処理を行う中心となる部分は、専用のシステムによらず、通常のコンピュータシステムを用いて実現可能である。たとえば、前記の動作を実行するためのコンピュータプログラムを、コンピュータが読み取り可能な記録媒体（フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ等）に格納して配布し、当該コンピュータプログラムをコンピュータにインストールすることにより、前記の処理を実行するベクターイメージ描画装置１を構成してもよい。また、インターネット等の通信ネットワーク上のサーバ装置が有する記憶装置に当該コンピュータプログラムを格納しておき、通常のコンピュータシステムがダウンロード等することでベクターイメージ描画装置１を構成してもよい。
【００７８】
また、ベクターイメージ描画装置１の機能を、ＯＳ（オペレーティングシステム）とアプリケーションプログラムの分担、またはＯＳとアプリケーションプログラムとの協働により実現する場合などには、アプリケーションプログラム部分のみを記録媒体や記憶装置に格納してもよい。
【００７９】
また、搬送波にコンピュータプログラムを重畳し、通信ネットワークを介して配信することも可能である。たとえば、通信ネットワーク上の掲示板(BBS, Bulletin Board System)に前記コンピュータプログラムを掲示し、ネットワークを介して前記コンピュータプログラムを配信してもよい。そして、このコンピュータプログラムを起動し、ＯＳの制御下で、他のアプリケーションプログラムと同様に実行することにより、前記の処理を実行できるように構成してもよい。
【図面の簡単な説明】
【００８０】
【図１】本発明の実施の形態に係るベクターイメージ描画装置の構成の一例を示すブロック図である。
【図２】バウンディングボックスの例を示す図である。
【図３】本実施の形態に係るベクターイメージ描画装置の物理的な構成の一例を示すブロック図である。
【図４】本発明の実施の形態に係るＤＭＡコマンドの並べ替え処理の動作の一例を示すフローチャートである。
【図５】並べ替え操作を説明する図である。
【図６】待ち行列内で配置され得るＤＭＡコマンドの順序を示す図である。
【図７】本発明のベクターイメージ描画装置とは異なるベクターイメージ描画装置の構成の一例を示すブロック図である。
【符号の説明】
【００８１】
１  ベクターイメージ描画装置
５  ベクターグラフィックスアクセラレータ（パイプ）
３１  領域図形生成部（バウンディングボックス計算手段）
３２  座標変換部（面積演算手段、座標変換手段）
４１  ＤＭＡコマンド並べ替え部（並べ替え手段）
５１  制御部
５２  主記憶部
５３  外部記憶部
５６  入出力部
Ａ  ＤＭＡコマンド（描画処理）    
Ｂ  待ち行列
Ｓ  バウンディングボックスの面積
【図１】
0004863306.tif 000002
【図２】
0004863306.tif 000003
【図３】
0004863306.tif 000004
【図４】
0004863306.tif 000005
【図５】
0004863306.tif 000006
【図６】
0004863306.tif 000007
【図７】
0004863306.tif 000008