(57)【特許請求の範囲】
【請求項１】
それぞれ異なる設定値が付与された少なくともＮ（Ｎは２以上の整数）個のプロセッサエレメントと、
ベジェ曲線を示す曲線情報を外部から受け取る受取手段と、
前記曲線情報を初期の入力情報とし、当該入力情報で示される曲線を２分割して２つの分割曲線を生成し、前記設定値に基づいて２つの分割曲線のうち一の分割曲線を選択して当該分割曲線を示す入力情報を定め、前記Ｎ個のプロセッサエレメントが互いに異なる分割曲線を選択するまで当該２分割を繰り返す分割アルゴリズムを、前記Ｎ個のプロセッサエレメントのそれぞれに実行させる第１実行手段と、
前記分割アルゴリズムにより最後に選択された分割曲線に近似するよう構成する１つ以上の線分を決定する決定アルゴリズムを、前記Ｎ個のプロセッサエレメントのそれぞれに実行させる第２実行手段とを備える
ことを特徴とする曲線分割装置。
【請求項２】
前記第１実行手段及び前記第２実行手段それぞれは、前記少なくともＮ個のプロセッサエレメントに、ＳＩＭＤ型プログラムを並列に実行させることで、前記分割アルゴリズム及び前記決定アルゴリズムそれぞれを実行させる
ことを特徴とする請求項１に記載の曲線分割装置。
【請求項３】
前記Ｎは、２のｎ乗（ｎは１以上の整数）であり、
前記分割アルゴリズムにおける繰り返しの回数はｎである
ことを特徴とする請求項２に記載の曲線分割装置。
【請求項４】
各プロセッサエレメントに付与された前記設定値は、当該プロセッサエレメントを一意に識別するためのｎビット長のデータであり、
前記分割アルゴリズムは、
前記設定値を示すデータの特定位ビットの値に応じて、一の分割曲線を選択し、選択後において前記設定値を示す値からなるビット列をシフトした新たなビット列を、次回の選択に用いる値とする
ことを特徴とする請求項３に記載の曲線分割装置。
【請求項５】
前記入力情報は、曲線の始点Ａ、制御点Ｂ及び終点Ｃからなり、
前記分割アルゴリズムは、
線分ＡＢとの中点Ｄ、及び線分ＢＣとの中点Ｅを算出し、
算出した前記点Ｄと前記点Ｅとからなる線分ＤＥの中点Ｆを算出することで、
前記点Ａ、Ｂ、Ｃから定まる曲線を、前記点Ａを始点、前記点Ｆを終点及び前記点Ｄを制御点とする分割曲線と、前記点Ｆを始点、前記点Ｃを終点及び前記点Ｅを制御点とする分割曲線とに２分割する
ことを特徴とする請求項２に記載の曲線分割装置。
【請求項６】
前記第１実行手段は、さらに、
前記ベジェ曲線とは別のベジェ曲線を示す、前記曲線情報とは別の曲線情報を初期の入力情報として、前記分割アルゴリズムを、前記Ｎ個のプロセッサエレメントとは異なるＭ（Ｍは２以上の整数）個のプロセッサエレメントのそれぞれに実行させ、
前記第２実行手段は、さらに、
前記決定アルゴリズムを、前記Ｍ個のプロセッサエレメントのそれぞれに実行させる
ことを特徴とする請求項１に記載の曲線分割装置。
【請求項７】
前記分割アルゴリズムは、選択した分割曲線を示す情報を格納するレジスタをＬ個必要とし、
前記Ｎ個のプロセッサエレメントのそれぞれは、
レジスタを、Ｌ×２n（ｎは１以上の整数）個以上有しており、
前記第２実行手段は、
前記決定アルゴリズムを、前記Ｎ個のプロセッサエレメントに実行させるに先立って、
前記Ｎ個のプロセッサエレメントのそれぞれに、前記最後に選択された分割曲線を示す曲線情報を初期の入力情報とし、２分割をｎ回繰り返す再分割アルゴリズムを実行させ、
前記決定アルゴリズムは、
前記再度に選択された分割曲線に前記再分割アルゴリズムを施すことで得られた１つ以上の曲線毎に、当該曲線に近似するよう１つ以上の線分を決定する
ことを特徴とする請求項１に記載の曲線分割装置。
【請求項８】
前記決定アルゴリズムは、
前記最後に選択された分割曲線を示す分割曲線情報に基づいて、当該分割曲線における曲率に応じて当該分割曲線を分割して得られる個数である分割数を算出し、
算出した前記分割数に応じて前記分割曲線を分割し、分割した曲線毎に当該曲線に近似する線分を決定する
ことを特徴とする請求項１に記載の曲線分割装置。
【請求項９】
前記分割数の算出の結果により分割が必要ない一のプロセッサエレメントが、分割が必要である他のプロセッサエレメントを特定した場合には、前記第２実行手段は、当該一のプロセッサエレメント及び当該他のプロセッサエレメントに対して、当該他のプロセッサエレメントが最後に選択した分割曲線について当該他のプロセッサエレメントで決定された分割数に応じて分割を行うように指示する
ことを特徴とする請求項８に記載の曲線分割装置。
【請求項１０】
前記第２実行手段は、
前記分割数の算出の結果により分割が必要ない分割曲線を示す曲線情報については外部へ出力し、
前記分割数の算出の結果により分割が必要な分割曲線を示す曲線情報については、算出した前記分割数に応じた分割に先立って、前記Ｎ個のプロセッサエレメントのそれぞれに、当該曲線情報を初期の入力情報とし、２分割をｎ回繰り返す再分割アルゴリズムを実行させ、当該再分割アルゴリズムの実行後、再度前記決定アルゴリズムを実行させる
ことを特徴とする請求項８に記載の曲線分割装置。
【請求項１１】
それぞれ異なる設定値が付与された少なくともＮ（Ｎは２以上の整数）個のプロセッサエレメントを備える曲線分割装置で用いられる曲線分割方法であって、
ベジェ曲線を示す曲線情報を外部から受け取る受取ステップと、
前記曲線情報を初期の入力情報とし、当該入力情報で示される曲線を２分割して２つの分割曲線を生成し、前記設定値に基づいて２つの分割曲線のうち一の分割曲線を選択して当該分割曲線を示す入力情報を定め、前記Ｎ個のプロセッサエレメントが互いに異なる分割曲線を選択するまで当該２分割を繰り返す分割アルゴリズムを、前記Ｎ個のプロセッサエレメントのそれぞれに実行させる第１実行ステップと、
前記分割アルゴリズムにより最後に選択された分割曲線に近似するよう構成する１つ以上の線分を決定する決定アルゴリズムを、前記Ｎ個のプロセッサエレメントのそれぞれに実行させる第２実行ステップとを含む
ことを特徴とする曲線分割方法。
【請求項１２】
それぞれ異なる設定値が付与された少なくともＮ（Ｎは２以上の整数）個のプロセッサエレメントを備える曲線分割装置に実行させる曲線分割プログラムであって、
ベジェ曲線を示す曲線情報を外部から受け取る受取ステップと、
前記曲線情報を初期の入力情報とし、当該入力情報で示される曲線を２分割して２つの分割曲線を生成し、前記設定値に基づいて２つの分割曲線のうち一の分割曲線を選択して当該分割曲線を示す入力情報を定め、前記Ｎ個のプロセッサエレメントが互いに異なる分割曲線を選択するまで当該２分割を繰り返す分割アルゴリズムを、前記Ｎ個のプロセッサエレメントのそれぞれに実行させる第１実行ステップと、
前記分割アルゴリズムにより最後に選択された分割曲線に近似するよう構成する１つ以上の線分を決定する決定アルゴリズムを、前記Ｎ個のプロセッサエレメントのそれぞれに実行させる第２実行ステップとを含む
ことを特徴とする曲線分割プログラム。
【請求項１３】
それぞれ異なる設定値が付与された少なくともＮ（Ｎは２以上の整数）個のプロセッサエレメントと、
ベジェ曲線を示す曲線情報を外部から受け取る受取手段と、
前記曲線情報を初期の入力情報とし、当該入力情報で示される曲線を２分割して２つの分割曲線を生成し、前記設定値に基づいて２つの分割曲線のうち一の分割曲線を選択して当該分割曲線を示す入力情報を定め、前記Ｎ個のプロセッサエレメントが互いに異なる分割曲線を選択するまで当該２分割を繰り返す分割アルゴリズムを、前記Ｎ個のプロセッサエレメントのそれぞれに実行させる第１実行手段と、
前記分割アルゴリズムにより最後に選択された分割曲線に近似するよう構成する１つ以上の線分を決定する決定アルゴリズムを、前記Ｎ個のプロセッサエレメントのそれぞれに実行させる第２実行手段とを備える
ことを特徴とする集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチプロセッサシステムにおいてベジェ曲線を分割して、直線に近似する技術に関する。
【背景技術】
【０００２】
コンピュータグラフィックスにおいて、アウトラインフォントなどのベクターコンテンツを表示するには曲線描画機能が必須である。従来の組み込み機器ではあらかじめ作成した固定サイズのビットマップを並べて表示していた文字表示機能が、今日のＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）やグラフィックＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）の進化に伴いアウトラインフォントから任意のサイズのフォントビットマップをリアルタイムに作成できるようになっている。アウトラインフォントは、文字の形状を、基準となる点の座標と輪郭線の集まりとして表現する形式であり、フォントの形状を定義するグリフデータを含んでいる。グリフデータは、２次元の「点座標列」と、点列をどのように結んでいくかを定義する「コマンド」から構成される。フォントの描画とは、グリフデータをラスタ化することである。ラスタ化とは、直線や曲線を表す数値データであるベクターデータをビットマップに変換する処理である。【０００３】
ここで、アウトラインフォントの代表例であるＴｒｕｅＴｙｐｅフォントでは、「コマンド」の代わりに、輪郭線上の点であるのか、輪郭線を構成する曲線の制御点であるのかを示すビットが各点に付加されており、それぞれ線分と２次ベジェ曲線とに代替できる。すなわち、制御点がフォント形状上に存在すれば当該輪郭線を「線分」として解釈し、フォント形状上に存在しなければ当該輪郭線を「２次ベジェ曲線」として解釈する。よって、フォントを描画するには、線分と２次ベジェ曲線のラスタライズを行えばよい。ラスタライズとは、コンピュータが扱う文字や画像を、プリンタで印刷したりディスプレイに表示できるように、色付きの小さな点の集まりで表現することである。ここで、２次ベジェ曲線をラスタライズする一つの方法として、曲線コマンドを複数の線分に近似しすべてのコマンドを線分で処理する方法がある。【０００４】
ここで、ベジェ曲線について説明する。２次ベジェ曲線は始点Ｐ０、制御点Ｐ１、終点Ｐ２の３点から構成され、パラメータｔを用いたパラメトリック曲線として数式１のように表現できる。また、３次ベジェ曲線は始点Ｐ０、制御点Ｐ１、Ｐ２、終点Ｐ３の４点から構成され、同様に数式２のように表現できる。【０００５】
【数１】
0005877381.tif 000002
【０００６】
【数２】
0005877381.tif 000003
【０００７】
点Ａ、Ｂ、Ｃから定まるベジェ曲線は、図１９に示すように、線分ＡＢの中点Ｄ、線分ＢＣの中点Ｅと、線分ＤＥ４の中点Ｆと、点Ａ、Ｂ、Ｃとから、点Ａ、Ｄ、Ｆから定まるベジェ曲線（左側２次ベジェ曲線）と、点Ｆ、Ｅ、Ｃから定まるベジェ曲線（右側２次ベジェ曲線）に分割することができる。【０００８】
さらに、左側２次ベジェ曲線を、図１９に示すように、点Ａ、Ｇ、Ｉから定まるベジェ曲線、点Ｉ、Ｈ、Ｆから定まるベジェ曲線とに分割することができる。また、右側２次ベジェ曲線についても同様に、点Ｆ、Ｊ、Ｌから定まるベジェ曲線、点Ｌ、Ｋ、Ｃから定まるベジェ曲線とに分割することができる。【０００９】
このように分割数を増やし深さ方向に再帰的に分割を行い、ある段階まで分割したら構成点を直線で結んでいけば直線に近似した曲線を描画することができる。再帰的に分割するか否かの判定は１回の分割毎に行われ、曲線の曲率に応じて判断される。曲率は１回の分割毎に小さくなっていく。したがって、直線に近い曲率の小さい部分は殆ど分割されず、曲率が大きい部分は何度も分割されることで曲率が小さくなり、描画結果として滑らかな曲線描画を実現できる。このような従来の再帰的曲線分割方式を使用した例として、スタックメモリを用いて逐次的に再帰的曲線分割を行う曲線分割装置がある（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開平８−３２９２６１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
特許文献１では、ＣＰＵにて、ベジェ曲線の再帰的曲線分割を行っている。そのため、再帰的曲線分割をＣＰＵで実行する場合には、ＣＰＵは他の処理をも実行する必要があるので、再帰的曲線分割の処理がＣＰＵを占有することはできない。【００１２】
そこで、再帰的曲線分割の処理を、ＣＰＵとは別のマルチプロセッサシステム、例えばマルチプロセッサ構成のコプロセッサやグラフィックプロセッサ、若しくはグラフィックス
ＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉ  Ｄａｔａ）プロセッサで行うことが考えられる。【００１３】
この場合、マルチプロセッサを構成する複数のプロセッサエレメントそれぞれにおいて、異なるベジェ曲線の再帰的曲線分割の処理を行うことが可能となるが、各プロセッサエレメントでの処理負荷にバラつきが生じ、マルチプロセッサシステム全体としての処理効率が悪くなるという問題が生じる。なぜなら、複数のプロセッサエレメントそれぞれにおいて、異なるベジェ曲線を扱うので、これらベジェ曲線の曲率が異なると、再帰的曲線分割の分割回数が異なるからである。【００１４】
そこで、本発明は、マルチプロセッサシステムにおいてベジェ曲線の分割処理を効率良く行うことのできる曲線分割装置、曲線分割方法、曲線分割プログラム及び集積回路を提供することを目的とする。
【課題を解決するための手段】
【００１５】
上記目的を達成するために、本発明は、曲線分割装置であって、それぞれ異なる設定値が付与された少なくともＮ（Ｎは２以上の整数）個のプロセッサエレメントと、ベジェ曲線を示す曲線情報を外部から受け取る受取手段と、前記曲線情報を初期の入力情報とし、当該入力情報で示される曲線を２分割して２つの分割曲線を生成し、前記設定値に基づいて２つの分割曲線のうち一の分割曲線を選択して当該分割曲線を示す入力情報を定め、前記Ｎ個のプロセッサエレメントが互いに異なる分割曲線を選択するまで当該２分割を繰り返す分割アルゴリズムを、前記Ｎ個のプロセッサエレメントに実行させる第１実行手段と、前記分割アルゴリズムにより最後に選択された分割曲線に近似するよう構成する１つ以上の線分を決定する決定アルゴリズムを、前記Ｎ個のプロセッサエレメントに実行させる第２実行手段とを備えることを特徴とする。
【発明の効果】
【００１６】
上記に示す構成によると、曲線分割装置は、Ｎ個のプロセッサエレメントに、互いに異なる分割曲線を選択するまで分割アルゴリズムを実行させるので、実行終了後には各プロセッサエレメントは初期入力されたベジェ曲線の曲率よりも小さい曲率である分割曲線を選択していることになる。そのため、各プロセッサエレメントは、曲率の小さい分割曲線に近似するよう構成する１つ以上の線分を決定するので、プロセッサエレメント間での処理負荷にバラつきを抑えることができる。これにより、曲線分割装置は、マルチプロセッサシステムにおいてベジェ曲線の分割処理を効率良く行うことができる。
【図面の簡単な説明】
【００１７】
【図１】情報処理装置１の構成を示すブロック図である。
【図２】分割回路２１の構成を示す図である。
【図３】プロセッサエレメント２２ａの構成を示す図である。
【図４】入力メモリ２０１ａ〜２０１ｄの具体例を説明する図である。
【図５】粗粒度分割処理の動作を示す流れ図である。
【図６】粗粒度分割処理の具体例、特に分割前の初期状態を示す図である。
【図７】粗粒度分割処理の具体例、特に１回目の分割後において一の分割曲線を選択した場合の状態を示す図である。
【図８】粗粒度分割処理の具体例、特に２回目の分割前の状態を示す図である。
【図９】粗粒度分割処理の具体例、特に２回目の分割後において一の分割曲線を選択した場合の状態を示す図である。
【図１０】細粒度分割処理の動作を示す流れ図である。
【図１１】細粒度分割曲線を分割数２で分割した場合の近似線分の決定を説明する図である。
【図１２】細粒度分割曲線を分割数３で分割した場合の近似線分の決定を説明する図である。
【図１３】情報処理装置１０００の構成を示すブロック図である。
【図１４】第１曲線情報と第２曲線情報との振り分けを示す図である。
【図１５】入力メモリ２０１ａ〜２０１ｈの具体例を説明する図である。
【図１６】情報処理装置２０００の構成を示すブロック図である。
【図１７】プロセッサエレメント２０２２ａの構成を示す図である。
【図１８】３次ベジェ曲線を２分割する具体例を示す図である。
【図１９】２次ベジェ曲線を２分割する従来の手順を示す図である。
【図２０】曲線分割装置３０００の構成を示すブロック図である。
【図２１】曲線分割装置４０００の構成を示すブロック図である。
【図２２】分割回路５０００の構成を示す図である。
【発明を実施するための形態】
【００１８】
１．第１の実施の形態
以下、本発明に係る第１の実施の形態について、図面を参照しながら説明する。以下、２次ベジェ曲線（単に「ベジェ曲線」という。）を用いて説明する。
【００１９】
１．１  概要
図１は、第１の実施の形態における情報処理装置１の構成を示すブロック図である。
【００２０】
情報処理装置１は、曲線分割装置１０、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１１、ラスタライズ回路１２、フレームバッファ１３及び表示装置１４から構成されている。
【００２１】
ＣＰＵ１１は、表示対象がベジェ曲線であるか線分であるかを示すコマンド、及び当該コマンドに応じた曲線情報及び線分情報の何れかを曲線分割装置１０へ出力する。ここで、曲線情報とは、ベジェ曲線を特定するための始点、終点及び制御点からなるものである。また、線分情報とは、線分を特定するための始点及び終点からなるものである。
【００２２】
曲線分割装置１０は、ＣＰＵ１１から曲線情報を受け取ると、当該曲線情報が示すベジェ曲線に近似する、１つ以上の線分からなる組を決定する。
【００２３】
ラスタライズ回路１２は、決定された１つ以上の線分を描画するための描画情報を生成し、フレームバッファ１３へ格納する。
【００２４】
表示装置は、フレームバッファ１３に格納された描画情報を基に、１つ以上の線分を表示する。これにより、ＣＰＵ１１から出力された曲線情報が示すベジェ曲線に近似する図が表示されることとなる。
【００２５】
１．２  構成
以下、本発明に係る曲線分割装置１０の構成について説明する。
【００２６】
曲線分割装置１０は、図１に示すように、分割回路２１とプロセッサエレメント（ＰＥ）２２ａ〜２２ｄを有するマルチプロセッサシステムである。
【００２７】
なお、本実施の形態では、曲線分割装置１０は、ＳＩＭＤ構成をとるものとする。ＳＩＭＤ構成によるマルチプロセッサにおいては、全てのプロセッサエレメントが同一μコード（各ＰＥが実行するプログラム）の同一プログラムカウンタを参照する。
【００２８】
（１）分割回路２１
分割回路２１は、図２に示すように、プログラム記憶部１００、受付部１０１、プログラム実行制御部１０２、入出力部１０３を有している。
【００２９】
（１−１）プログラム記憶部１００
プログラム記憶部１００は、粗粒度分割プログラム１１０と、線分決定プログラム１１１とを有している。粗粒度分割プログラム１１０と、線分決定プログラム１１１とは、ＰＥ２２ａ〜２２ｄで実行されるものである。
【００３０】
（粗粒度分割プログラム）
粗粒度分割プログラム１１０は、ＣＰＵ１１から受け取った曲線情報を初期の入力情報とし、当該入力情報で示される曲線を２分割して２つの分割曲線を生成し、所定の情報に基づいて２つの分割曲線のうち一の分割曲線を選択して当該分割曲線を示す入力情報を定め、プロセッサエレメント２２ａ〜２２ｄが互いに異なる分割曲線を選択するまで当該２分割を繰り返すプログラムである。ここで、所定の情報とは、各ＰＥに割り当てられた、当該ＰＥを識別するための識別子の値である。
【００３１】
なお、粗粒度分割プログラムが実行された場合の機能動作の詳細については、後述する。
【００３２】
（線分決定プログラム１１１）
線分決定プログラム１１１は、粗粒度分割プログラム１１０が実行されたことにより、最後に選択された分割曲線それぞれについて、当該分割曲線に近似するよう構成する１つ以上の線分を決定するプログラムであり、図２に示すように分割数決定プログラム１１２と細粒度分割プログラム１１３とから構成される。
【００３３】
分割数決定プログラム１１２は、分割曲線の曲率に応じて当該分割曲線の分割数を決定するプログラムである。
【００３４】
細粒度分割プログラム１１３は、分割曲線の曲率に応じて決定された分割数に基づいて当該分割曲線を分割し、分割した曲線毎に当該曲線に近似する線分を決定するプログラムである。
【００３５】
なお、分割数決定プログラム及び細粒度分割プログラムが実行された場合の機能動作の詳細については、後述する。
【００３６】
（１−２）受付部１０１
受付部１０１は、ＣＰＵ１１からベジェ曲線を示す曲線情報を受け付けると、当該曲線情報をＰＥ２２ａ〜２２ｄへ出力する。
【００３７】
（１−３）プログラム実行制御部１０２
プログラム実行制御部１０２は、粗粒度分割プログラム１１０で実現される粗粒度分割アルゴリズム、及び線分決定プログラム１１１で実現される線分決定アルゴリズムをＰＥ２２ａ〜２２ｄに実行させるものである。ここで、プログラム実行制御部１０２は、粗粒度分割プログラム１１０、線分決定プログラム１１１の順序でＰＥ２２ａ〜２２ｄに実行させる。また、線分決定プログラム１１１においては、分割数決定プログラム１１２、細粒度分割プログラム１１３の順序でＰＥ２２ａ〜２２ｄに実行させる。
【００３８】
具体的には、プログラム実行制御部１０２は、ＰＥ２２ａ〜２２ｄに粗粒度分割アルゴリズムを実行させる際には、粗粒度分割プログラム１１０を構成する各命令を、ＰＥ２２ａ〜２２ｄに出力する。また、プログラム実行制御部１０２は、ＰＥ２２ａ〜２２ｄに線分決定アルゴリズムを実行させる際には、分割数決定プログラム１１２及び細粒度分割プログラムそれぞれを構成する各命令を、ＰＥ２２ａ〜２２ｄに出力する。
【００３９】
（１−４）入出力部１０３
入出力部１０３は、ＰＥ２２ａ〜２２ｄから、線分決定プログラム１１１の実行により得られた１つ以上の線分を受け取ると、ラスタライズ回路１２へ出力する。
【００４０】
（２）ＰＥ２２ａ〜２２ｄ
ここでは、ＰＥ２２ａ〜２２ｄについて説明する。なお、ＰＥ２２ａ〜２２ｄは同一の構成であるので、以下、ＰＥ２２ａの構成について説明する。
【００４１】
図３は、ＰＥ２２ａの構成を示す図であり、ＰＥ２２ａは、入力メモリ２０１ａ、処理部２０２ａ及び出力メモリ２０３ａを有している。
【００４２】
（２−１）入力メモリ２０１ａ
入力メモリ２０１ａは、当該ＰＥ２２ａを識別するための識別子２１０ａを記憶する領域と、μコードを処理するのに必要な入力データを記憶する領域とを有するレジスタである。
【００４３】
例えば、入力メモリ２０１ａは、分割回路２１の受付部１０１から出力された曲線情報を記憶する。また、入力メモリ２０１ａにおいて、曲線情報を記憶するレジスタには、粗粒度分割プログラムの実行により選択された分割曲線を示す曲線情報（上記の入力情報と同一）が上書きされる。
【００４４】
なお、本実施の形態では、入力メモリ２０１ａは、受付部１０１やＰＥ２２ａ自身が参照できるメモリであるが、自分以外のＰＥ２２ｂ〜２２ｄは参照及び出力をすることができない領域であるものとする。すなわち、本実施の形態では、プロセッサエレメント間でのデータの授受は行わないものとする。
【００４５】
（２−２）処理部２０２ａ
処理部２０２ａは、プログラム実行制御部１０２から出力された各プログラムの命令を実行するものである。
【００４６】
具体的には、処理部２０２ａは、機能的な構成要素である粗粒度分割部２１１ａ、分割数決定部２１２ａ及び細粒度分割部２１３ａから構成される。
【００４７】
（粗粒度分割部２１１ａ）
粗粒度分割部２１１ａは、プログラム実行制御部１０２から出力される粗粒度分割プログラム１１０の命令を実行するため機能要素である。
【００４８】
以下、粗粒度分割プログラム１１０が実行された場合の機能動作について説明する。
【００４９】
粗粒度分割部２１１ａは、粗粒度分割プログラム１１０を実行することにより、１つの入力曲線を２つの曲線に分割するたびに当該ＰＥ２２ａの識別子に応じて２つの曲線の一方を新たな入力曲線として選択し、当該新たな入力曲線を示す新たな曲線情報を、先に保持されていている曲線情報に上書きする処理を複数回再帰的に行った後、最後に選択された曲線を粗粒度分割曲線（以下、単に「分割曲線」ともいう。）として、当該粗粒度分割曲線を示す曲線情報を、分割数決定部２１２ａ及び細粒度分割部２１３ａへ出力する。
【００５０】
（分割数決定部２１２ａ）
分割数決定部２１２ａは、プログラム実行制御部１０２から出力される分割数決定プログラム１１２の命令を実行するための機能要素である。分割数決定部２１２ａは、分割数決定プログラム１１２を実行することにより、粗粒度分割部２１１ａから受け取った粗粒度分割曲線に対して、固定値及び曲線を構成する点の座標値の少なくともいずれかに応じた分割数を決定する。
【００５１】
以下、分割数決定プログラム１１２が実行された場合の機能動作について説明する。
【００５２】
分割数決定部２１２ａは、粗粒度分割曲線の始点と終点を結ぶ線分を粗粒度分割曲線の近似線分としたときに十分近似できているかの判断を行うものである。本実施の形態では、ベジェ曲線の始点、制御点、終点の座標を使って分割数ＤＩＶを決定する。
【００５３】
具体的には、分割数決定部２１２ａは、下記の数式３で求めたＤＩＶＦの値を整数値に変換した値を分割数ＤＩＶとしてもかまわない。
【００５４】
【数３】
0005877381.tif 000004
【００５５】
ここで、整数値への変換は小数点以下を切り捨ててもよいし切り上げてもよいし四捨五入してもよい。また、分割数決定プログラム１１２には、数式３、及びＤＩＶＦの値を整数値に変換した値を分割数ＤＩＶとする命令が含まれている。
【００５６】
分割数決定部２１２ａは、算出した分割数ＤＩＶを細粒度分割部２１３ａへ転送する。つまり、細粒度分割プログラム１１３へ引き渡す。
【００５７】
（細粒度分割部２１３ａ）
細粒度分割部２１３ａは、プログラム実行制御部１０２から出力される細粒度分割プログラム１１３の命令を実行するための機能要素である。細粒度分割部２１３ａは、分割数決定部２１２ａで決定された分割数に基づいて、粗粒度分割曲線を近似線分に分割する。
【００５８】
以下、細粒度分割プログラム１１３が実行された場合の機能動作について説明する。
【００５９】
細粒度分割部２１３ａは、粗粒度分割部２１１ａで生成した粗粒度分割曲線と、分割数決定部２１２ａで算出した当該粗粒度分割曲線に対応する分割数とを用いて、当該粗粒度分割曲線を分割数と等しい数の近似線分に分割する。本実施の形態では、近似線分への分割を粗粒度分割曲線上にある点を分割数個生成し生成した点を結ぶ線分を生成することで行うものとする。
【００６０】
一般的に、２次ベジェ曲線上の点座標はパラメータｔ（ｔは０以上１以下の数）を用いて、上述した数式１のようなパラメトリック式で表現することができる。ここで、始点座標Ｐ０（Ｘ０，Ｙ０）、制御点座標Ｐ１（Ｘ１，Ｙ１）、終点座標Ｐ２（Ｘ２，Ｙ２）で構成される２次ベジェ曲線上の点座標をＰ（ｔ）とする。
【００６１】
数式１をｔの多項式に変形すると、数式４のようになる。
【００６２】
【数４】
0005877381.tif 000005
【００６３】
細粒度分割部２１３ａではこの式を利用する。
【００６４】
例えば、ｎを分割数とした場合、細粒度分割部２１３ａは、始点座標Ｐ０と点Ｐ（１／ｎ）とからなる線分、点Ｐ（１／ｎ）と点Ｐ（２／ｎ）とからなる線分、・・・、点Ｐ（（ｎ−１）／ｎ）と点Ｐ（１）とからなる線分を生成する。
【００６５】
（２−３）出力メモリ２０３ａ
出力メモリ２０３ａは、分割回路２１の入出力部１０３へ出力すべき情報を格納する領域を有している。
【００６６】
具体的には、細粒度分割部２１３ａにより細粒度分割プログラム１１３が実行された後、出力メモリ２０３ａには、当該実行により得られた１つ以上の線分の情報（例えば、始点と終点からなる情報）が格納される。
【００６７】
（３）入力メモリの具体例
ここでは、ＰＥ２２ａ〜２２ｄそれぞれが有する入力メモリ２０１ａ〜２０１ｄの具体例について、図４を用いて説明する。
【００６８】
ＰＥ２２ａ〜２２ｄそれぞれが有する入力メモリ２０１ａ〜２０１ｄは、上述したように当該ＰＥを識別するための識別子を記憶する領域を有している。ここでは、図４に示すように、入力メモリ２０１ａ〜２０１ｄには、順に“００”、“０１”、“１０”、“１１”が格納されているものとする。
【００６９】
また、粗粒度分割プログラム１１０が実行される前には、ＣＰＵ１１から出力された曲線情報を分割回路２１の受付部１０１から受け取り、格納する。つまり、粗粒度分割プログラムの実行開始時には、図４に示すように、入力メモリ２０１ａ〜２０１ｄには同一の曲線情報が記憶されていることとなる。
【００７０】
１．３  動作
ここでは、曲線分割装置１０の動作について説明する。
【００７１】
（１）粗粒度分割処理の動作について
ここでは、各プロセッサエレメント（ＰＥ）２２ａ〜２２ｄにおいて、入力された２次ベジェ曲線を分割するμコード（粗粒度分割プログラム１１０）が実行されることによる粗粒度分割処理の動作について、図５に示す流れ図を用いて説明する。なお、ここでは、記載の便宜上、座標を示すレジスタは２次元ベクトルを扱えるものとする。
【００７２】
また、ＰＥ２２ａ〜２２ｄの動作は同一であるので、ここでは、ＰＥ２２ａを用いて説明する。
【００７３】
ＰＥ２２ａの粗粒度分割部２１１ａは、分割回路２１の受付部１０１より受け取った曲線情報に基づいて、曲線情報が示すベジェ曲線の始点、制御点及び終点をそれぞれ、レジスタＡ、Ｂ、Ｃにコピーし、さらに２分割処理を行う回数をカウントするレジスタＣＯＵＮＴを１に初期化する（ステップＳ５）。
【００７４】
粗粒度分割部２１１ａは、２分割の繰り返し回数をレジスタＣＭＡＸに設定する（ステップＳ１０）。プロセッサエレメント毎に異なる粗粒度分割曲線を割り当てる場合には、プロセッサエレメント数の２の対数を繰り返し回数とすればよい。本実施の形態では、プロセッサエレメント数が４であるので、レジスタＣＭＡＸには２が設定される。
【００７５】
粗粒度分割部２１１ａは、レジスタＡ（始点）とレジスタＢ（制御点）とから定まる線分ＡＢの中点を計算してレジスタＤに設定し、レジスタＢ（制御点）とレジスタＣ（終点）とから定まる線分ＢＣの中点を計算してレジスタＥに設定する（ステップＳ１５）。
【００７６】
粗粒度分割部２１１ａは、レジスタＤが示す点とレジスタＥが示す点とから定まる線分ＤＥの中点を計算し、レジスタＦに設定する（ステップＳ２０）。
【００７７】
粗粒度分割部２１１ａは、ＰＥ２２ａの識別子の最下位ビットが１であるか否かを判断する（ステップＳ２５）。１であると判断する場合には（ステップＳ２５における「Ｙｅｓ」）、粗粒度分割部２１１ａは、レジスタＦの値をレジスタＡに上書きする（ステップＳ３０）。０であると判断する場合には（ステップＳ２５における「Ｎｏ」）、粗粒度分割部２１１ａは、レジスタＦの値をレジスタＣに上書きする（ステップＳ３５）。
【００７８】
さらに、粗粒度分割部２１１ａは、ＰＥ２２ａの識別子の最下位ビットが１であるか否かを判断する（ステップＳ４０）。１であると判断する場合には（ステップＳ４０における「Ｙｅｓ」）、粗粒度分割部２１１ａは、レジスタＥの値をレジスタＢに上書きする（ステップＳ４５）。０であると判断する場合には（ステップＳ４０における「Ｎｏ」）、粗粒度分割部２１１ａは、レジスタＤの値をレジスタＢに上書きする（ステップＳ５０）。
【００７９】
粗粒度分割部２１１ａは、レジスタＣＯＵＮＴの値がレジスタＣＭＡＸの値未満かどうかを判定する（ステップＳ５５）。
【００８０】
ＣＯＵＮＴの値がレジスタＣＭＡＸ未満であると判断する場合（ステップＳ５５における「Ｙｅｓ」）、粗粒度分割部２１１ａは、ＣＯＵＮＴの値をインクリメントし、識別子の値を右に１ビットシフトする（ステップＳ６０）。識別子を右に１ビットシフトするのは、レジスタＡ、Ｂ、Ｃの内容、すなわちベジェ曲線を構成する始点、制御点、終点がすべてのプロセッサエレメントにおいて異なるように分配するためである。レジスタＣＭＡＸの値がプロセッサエレメント数の２の対数と等しければ、２分割するたびに識別子を１ビット右にシフトすることで、再度ステップＳ２５からステップＳ５０までの処理を実行するときに使用する識別子の最下位ビットが変化することになり、結果的に各ＰＥのレジスタＡ、Ｂ、Ｃにはすべて異なる点が割り当てられることとなる。ここでは識別子を右に１ビットシフトする例を挙げているが、ビットシフト量やシフト方向は識別子をプロセッサエレメントの判別に使用する方法に依存することは自明である。
【００８１】
（２）粗粒度分割処理の具体例
ここでは、各ＰＥ２２ａ〜２２ｄにおいて粗粒度分割処理が行われた場合について、具体例を用いて説明する。
【００８２】
（ＣＯＵＮＴの値が１の場合）
ＰＥ２２ａ〜２２ｄは、図５に示すステップＳ５を実行することで、分割回路２１の受付部１０１から受け取った、図６に示すベジェ曲線５００を示す曲線情報に含まれる始点Ａ、制御点Ｂ、及び終点Ｃを対応する各レジスタへ設定する。
【００８３】
ＰＥ２２ａ〜２２ｄは、ステップＳ１５、Ｓ２０を実行することで、図６に示す点Ｄ、Ｅ、Ｆを算出する。
【００８４】
ＰＥ２２ａ〜２２ｄは、点Ｄ、Ｅ、Ｆの算出後、ステップＳ５０までを実行する。この場合、ＰＥ２２ａの識別子は００であるので、ステップＳ２５の判断後においてステップＳ３５が実行されることになり、また、ステップＳ４０の判断後においてステップＳ５０が実行されることになる。そのため、図６に示す点Ｄが点Ｂに、点Ｆが点Ｃにそれぞれ変更される。その結果を図７（ａ）に示す。
【００８５】
また、ＰＥ２２ｂの識別子は０１であるので、ステップＳ２５の判断後においてステップＳ３０が実行されることになり、また、ステップＳ４０の判断後においてステップＳ４５が実行されることになる。そのため、図６に示す点Ｅが点Ｂに、点Ｆが点Ａにそれぞれ変更される。その結果を図７（ｂ）に示す。
【００８６】
ＰＥ２２ｃの識別子は１０であり、最下位ビットは０である。そのため、ＰＥ２２ｃの動作については、ＰＥ２２ａの動作と同様に、図６に示す点Ｄが点Ｂに、点Ｆが点Ｃにそれぞれ変更される。その結果を図７（ｃ）に示す。
【００８７】
ＰＥ２２ｄの識別子は１１であり、最下位ビットは１である。そのため、ＰＥ２２ｄの動作については、ＰＥ２２ｂの動作と同様に、図６に示す点Ｅが点Ｂに、点Ｆが点Ａにそれぞれ変更される。その結果を図７（ｄ）に示す。
【００８８】
その後、ＰＥ２２ａ〜２２ｄは、ステップＳ５５、Ｓ６０を実行し、ＣＯＵＮＴの値が２となり、そして識別子のビットが右にシフトされる。
【００８９】
（ＣＯＵＮＴの値が２の場合）
ＰＥ２２ａ〜２２ｄは、ステップＳ１５、Ｓ２０を実行することで、ＣＯＵＮＴの値が１のときに選択した分割曲線に対して、図８（ａ）、（ｂ）に示す点Ｄ、Ｅ、Ｆを算出する。ここで、図８（ａ）はＰＥ２２ａ、２２ｃに対するものであり、図８（ｂ）はＰＥ２２ｂ、２２ｄに対するものである。
【００９０】
ＰＥ２２ａ〜２２ｄは、点Ｄ、Ｅ、Ｆの算出後、ステップＳ５０までを実行する。
【００９１】
ＰＥ２２ａについて右シフト後の識別子の最下位ビットは０であるので、ステップＳ２５の判断後においてステップＳ３５が実行されることになり、また、ステップＳ４０の判断後においてステップＳ５０が実行されることになる。そのため、図８（ａ）に示す点Ｄが点Ｂに、点Ｆが点Ｃにそれぞれ変更される。その結果を図９（ａ）に示す。
【００９２】
また、ＰＥ２２ｃについて右シフト後の識別子の最下位ビットは１であるので、ステップＳ２５の判断後においてステップＳ３０が実行されることになり、また、ステップＳ４０の判断後においてステップＳ４５が実行されることになる。そのため、図８（ａ）に示す点Ｅが点Ｂに、点Ｆが点Ａにそれぞれ変更される。その結果を図９（ｂ）に示す。
【００９３】
ＰＥ２２ｂについて右シフト後の識別子の最下位ビットは０であるので、ステップＳ２５の判断後においてステップＳ３５が実行されることになり、また、ステップＳ４０の判断後においてステップＳ５０が実行されることになる。そのため、図８（ｂ）に示す点Ｄが点Ｂに、点Ｆが点Ｃにそれぞれ変更される。その結果を図９（ｃ）に示す。
【００９４】
また、ＰＥ２２ｄについて右シフト後の識別子の最下位ビットは１であるので、ステップＳ２５の判断後においてステップＳ３０が実行されることになり、また、ステップＳ４０の判断後においてステップＳ４５が実行されることになる。そのため、図８（ｂ）に示す点Ｅが点Ｂに、点Ｆが点Ａにそれぞれ変更される。その結果を図９（ｄ）に示す。
【００９５】
その後、ＰＥ２２ａ〜２２ｄは、ステップＳ５５を実行し、処理を終了する。
【００９６】
以上により、ＰＥ２２ａ〜２２ｄは、図９に示すように、それぞれ異なる分割曲線を選択することができる。具体的には、ＰＥ２２ａ〜２２ｄは、それぞれ異なる分割曲線を示す曲線情報を選択することができる。
【００９７】
また、ＰＥ２２ａ〜２２ｄそれぞれの粗粒度分割部は、ベジェ曲線の再帰分割可能な性質とＳＩＭＤプロセッサの同時処理可能な性質とを利用して、２分割時に当該粗粒度分割部を有するＰＥの識別子を用いることで、各ＰＥ２２ａ〜２２ｄのＣＰＵ１１から出力されたベジェ曲線を初期の入力曲線として分割しながら同時に各プロセッサエレメントに対して異なる分割曲線の領域を割り当てていくことができる。
【００９８】
（３）細粒度分割処理の動作について
ここでは、各プロセッサエレメント（ＰＥ）２２ａ〜２２ｄにおいて、線分を決定するμコード（線分決定プログラム１１１）、特に細粒度分割プログラムが実行されることによる細粒度分割処理の動作について、図１０に示す流れ図を用いて説明する。なお、ここでは、記載の便宜上、座標を示すレジスタは２次元ベクトルを扱えるものとする。
【００９９】
なお、ＰＥ２２ａ〜２２ｄの動作は同一であるので、ここでは、ＰＥ２２ａを用いて説明する。また、ここでは、分割数決定部２１２ａによる分割数決定プログラム１１２の実行により、分割数ＤＩＶの値が決められているものとする。
【０１００】
細粒度分割部２１３ａは、数式４で示すパラメータｔの増分値を保持するレジスタＤＴに１／ＤＩＶを、パラメータｔを保持するレジスタＰＴに初期値０を、レジスタＡ、Ｂ、Ｃを用いてパラメトリック式表現の係数であるＬ、Ｍ、Ｎを計算し、それぞれレジスタＬ、Ｍ、Ｎに、それぞれ設定する（ステップＳ１００）。
【０１０１】
細粒度分割部２１３ａは、レジスタＰＴ２にｔ＊ｔ、つまりＰＴ＊ＰＴの値を保持し、レジスタＰＴ、ＰＴ２、Ｌ、Ｍ、Ｎの値を用いて、Ｌ＊ＰＴ２＋Ｍ＊ＰＴ＋Ｎを計算しレジスタＣに設定する（ステップＳ１０５）。
【０１０２】
細粒度分割部２１３ａは、レジスタＰＴの値が０であるか否かを判断する（ステップＳ１１０）。
【０１０３】
レジスタＰＴの値が０でないと判断する場合（ステップＳ１１０における「Ｎｏ」）、細粒度分割部２１３ａは、レジスタＰで示される点座標を始点、レジスタＣで示される点座標を終点とする線分を生成する（ステップＳ１１５）。
【０１０４】
細粒度分割部２１３ａは、レジスタＰにレジスタＣの値を設定し、パラメータＰＴにｔの増分値ＤＴを加算する（ステップＳ１２０）。
【０１０５】
細粒度分割部２１３ａは、加算後のパラメータＰＴが１以下であるか否かを判断する（ステップＳ１２５）。１以下であると判断する場合（ステップＳ１２５における「Ｙｅｓ」）、処理はステップＳ１０５に戻る。１より大きいと判断する場合（ステップＳ１２５における「Ｎｏ」）、処理は終了する。
【０１０６】
レジスタＰＴの値が０であると判断する場合（ステップＳ１１０における「Ｙｅｓ」）、細粒度分割部２１３ａによる処理は、ステップＳ１２０へ移行し、その後の処理を続行する。
【０１０７】
（４）細粒度分割処理の具体例
ここでは、ＰＥ２２ａにおいて粗粒度分割処理が行われた場合にについて、具体例を用いて説明する。
【０１０８】
ＰＥ２２ａは、上記にて示す粗粒度分割部２１１ａの機能動作により、図９（ａ）に示すベジェ曲線（粗粒度分割曲線）を選択している。
【０１０９】
ベジェ曲線における有効なパラメータｔの値は０から１の区間なので、当該区間を分割数で分割すればよい。たとえば分割数が２であれば、図１１のように、０から０．５（＝１／２）の区間、０．５から１（＝２／２）の区間の２つの区間に分割することができる。すなわち０から０．５の区間の線分は、点Ｐ（０）と点Ｐ（０．５）を結ぶ線分であり、０．５から１の区間の線分は、点Ｐ（０．５）と点Ｐ（１）を結ぶ線分であり、この２つの線分が図９（ａ）に示すベジェ曲線の近似線分となる。
【０１１０】
なお、上記の動作は、分割数が２以上であるとしているが、分割数が１の場合は０から１の区間を結ぶ線分、すなわちベジェ曲線（粗粒度分割曲線）の始点と終点を結ぶ線分を生成することと同義であるため、図１１の流れ図を用いることなく、単に始点と終点を結ぶ線分を１つ生成するようにしても問題ないことは自明である。
【０１１１】
また、図１１の流れ図において、ステップＳ１００でレジスタＤＴへは分割数ＤＩＶの逆数値を設定しているが、逆数値が逆数演算の有効ビット内で割り切れない場合には、ステップＳ１２０レジスタＰＴへレジスタＤＴの値を分割数回足しこんでいってもＰＴが１にならない。この場合には、分割数＋１個の線分が生成されることになる。例えば、分割数が３の場合、パラメータｔの増分値である３の逆数値は０．３３３と割り切れない値になり、レジスタＰＴへレジスタＤＴを分割数（＝３）回加算しても０から０．３３３の区間、０．３３３から０．６６６の区間、０．６６６から０．９９９の区間となり、０．９９９から１の区間の近似線分が生成されない。そこで、逆数値が有効ビット内で割り切れない場合には、分割数よりも1多い区間の数の近似線分を生成することになる。具体的には０から０．３３３の区間、０．３３３から０．６６６の区間、０．６６６から０．９９９の区間、０．９９９から１の区間の4つの区間の近似線分を生成する（図１２参照）。ただし、分割数の逆数計算が逆数演算の有効ビット内で割り切れない場合でも、最後の区間を計算するときにレジスタＰＴの加算結果を使うのではなく、強制的にＰＴ＝１としてもよい。すなわち分割数が３の場合の例では、図１０に示す流れ図に従って処理すると最後の区間を計算するときにＰＴ＝０．６６６に対してＤＴ＝０．３３３を加算した結果ＰＴ＝０．９９９になるが、図１０で示すステップＳ１１０、Ｓ１１５で生成した近似線分の数をカウントしておきカウント値が分割数ＤＩＶ−１に等しくかつ分割数が逆数演算の有効ビット内で割り切れないときにはＰＴ＝１にする、という処理に変更してもよい。
【０１１２】
１．４  まとめ
以上、説明したように、本実施の形態では、入力されたベジェ曲線（ＣＰＵ１１から初期入力として出力されたベジェ曲線）を粗粒度分割部２１１ａでＰＥの個数分に分割し、その後、分割数決定部２１２ａで対応する分割曲線について分割数を決定している。
【０１１３】
これにより、以下の効果を得る。
【０１１４】
ベジェ曲線を構成する始点、制御点、終点を結んでできる三角形の領域が大きいほど、また曲率が大きい箇所ほど、ベジェ曲線を多くの微小線分に分割しなければ滑らかな曲線を生成することができない。そこで分割数決定部２１２ａは、ＣＰＵ１１から出力されたベジェ曲線に対してではなく、粗粒度分割部２１１ａで既に粗く分割された粗粒度分割曲線を扱う。ＰＥの数が多いほど分割数決定部２１２ａが扱う粗粒度分割曲線は粗粒度分割部２１１ａで多くの曲率の小さい曲線に分割されており、そのため始点と終点を結ぶ線分は十分粗粒度分割曲線を近似できている可能性が高くなり後段の細粒度分割部２１３ａで更なる分割を行う可能性は低くなる。
【０１１５】
また、本実施の形態のよる構成によれば、粗粒度分割部２１１ａで曲線を曲率の小さい複数の粗粒度分割曲線に分割しながら各プロセッサエレメントに処理単位である曲線を割り当てておき、以降は粗粒度分割曲線に対してさらに分割すべきかどうかを判断し細粒度分割を行うことにより、粗粒度分割のときにはマルチプロセッサの並列性を生かして曲線を分割すると同時にプロセッサエレメントへ処理対象曲線の割り当てを行うことができ、マルチプロセッサ向け処理ではない細粒度分割の処理はできるだけ少なくなり、高速にベジェ曲線を微小線分で近似することができる。
【０１１６】
２．第２の実施の形態
以下、本発明に係る第２の実施の形態について、図面を参照しながら、第１の実施の形態と異なる点を中心に説明する。
【０１１７】
なお、第１の実施の形態と同一の装置、回路及び構成要素については、同一の符号を付するものとする。
【０１１８】
２．１  構成
図１３は、第２の実施の形態における情報処理装置１０００の構成を示すブロック図である。
【０１１９】
情報処理装置１０００は、曲線分割装置１０１０、ＣＰＵ１１、ラスタライズ回路１２、フレームバッファ１３及び表示装置１４から構成されている。なお、本実施の形態においても、曲線分割装置１０は、第１の実施の形態と同様にＳＩＭＤ構成をとるものとする。
【０１２０】
第１の実施の形態と異なる点は、曲線分割装置１０１０の機能動作である。
【０１２１】
以下、曲線分割装置１０１０について説明する。
【０１２２】
曲線分割装置１０１０において、第１の実施の形態で示す曲線分割装置１０と構成要素は同じ構成要素を有しているが、曲線分割装置１０と異なる点は、ＰＥの個数と、受付部の動作である。他の構成要素については、第１の実施の形態と同様であり、説明する上で、必要があれば、第１の実施の形態で示す符号を用いて説明する。
【０１２３】
曲線分割装置１０１０は、図１３に示すように、合計２ｎ＋２ｍ個のＰＥ（ＰＥ２２ａ、２２ｂ、２２ｃ、２２ｄ、・・・、２２ｄ’、２２ｅ、・・・、２２ｈ）を有している。
【０１２４】
各ＰＥの構成及び機能動作は、第１の実施の形態で示す構成及び機能動作と同様であるので、ここでの説明は省略する。なお、以下の説明において、ｎ＝ｍ＝２、つまりＰＥの個数を８個とする。
【０１２５】
第２の実施の形態における受付部１１０１は、図１４に示すように、ＣＰＵ１１から２つのベジェ曲線それぞれを示す第１曲線情報と第２曲線情報とを受け取ると、８個のＰＥのうち４個のＰＥ（ＰＥ２２ａ〜２２ｄ）に第１曲線情報を出力し、残り４個のＰＥ（ＰＥ２２ｅ〜２２ｈ）に第２曲線情報を出力する。
【０１２６】
以降、ＰＥ２２ａ〜２２ｄは、第１の実施の形態と同様の動作により、第１曲線情報で示される第１ベジェ曲線を初期の入力として、ＰＥ２２ａ〜２２ｄ毎に異なる分割曲線を選択する。また、ＰＥ２２ｅ〜２２ｈは、第１の実施の形態と同様の動作により、第２曲線情報で示される第２ベジェ曲線を初期の入力として、ＰＥ２２ｅ〜２２ｈ毎に異なる分割曲線を選択する。
【０１２７】
ここで、入力メモリ２０１ａ〜２０１ｈの具体例について、図１５を用いて説明する。
【０１２８】
ＰＥ２２ａ〜２２ｈそれぞれが有する入力メモリ２０１ａ〜２０１ｈは、第１の実施の形態と同様に当該ＰＥを識別するための識別子を記憶する領域を有している。ここでは、図１５に示すように、入力メモリ２０１ａ〜２０１ｈには、順に“０００”、“００１”、“０１０”、“０１１”、“１００”、“１０１”、“１１０”、“１１１”が格納されているものとする。
【０１２９】
また、粗粒度分割プログラム１１０が実行される前には、入力メモリ２０１ａ〜２０１ｄについてはＣＰＵ１１から出力された第１曲線情報が、入力メモリ２０１ｅ〜２０１ｈについてはＣＰＵ１１から出力された第２曲線情報が、それぞれ格納される。
【０１３０】
このような構成をとることで、ＰＥ２２ａ〜２２ｄを第１プロセッサ群とし、ＰＥ２２ｅ〜２２ｈを第２プロセッサ群として、それぞれ個別のベジェ曲線に対する分割を行うことができる。
【０１３１】
かかる構成によれば、プロセッサエレメントの数が多い場合で過度な曲線分割が不要な場合において、複数のプロセッサエレメントを１つのプロセッサエレメント群として複数のプロセッサエレメント群を構成した場合、受付部１１０１がプロセッサエレメント群毎に異なる曲線情報を入力することにより、プロセッサエレメント群内のプロセッサエレメントは同一のベジェ曲線をマルチプロセッサの並列性を生かして処理することができるとともに１回のプロセッサ実行で複数のベジェ曲線を処理することができる利点を得ることができ、高速に複数のベジェ曲線を微小線分で近似することができる。
【０１３２】
３．第３の実施の形態
以下、本発明に係る第３の実施の形態について、図面を参照しながら、第１の実施の形態と異なる点を中心に説明する。
【０１３３】
なお、第１の実施の形態と同一の装置、回路及び構成要素については、同一の符号を付するものとする。
【０１３４】
３．１  構成
図１６は、第３の実施の形態における情報処理装置２０００の構成を示すブロック図である。
【０１３５】
情報処理装置２０００は、曲線分割装置２０１０、ＣＰＵ１１、ラスタライズ回路１２、フレームバッファ１３及び表示装置１４から構成されている。なお、本実施の形態においても、曲線分割装置２０１０は、第１の実施の形態と同様にＳＩＭＤ構成をとるものとする。
【０１３６】
曲線分割装置２０１０は、図１６に示すように、分割回路２０２１、ＰＥ２０２２ａ〜２０２２ｄを有している。
【０１３７】
（１）分割回路２０２１
分割回路２０２１は、プログラム記憶部２１００、受付部２１０１、プログラム実行制御部２１０２、入出力部２１０３から構成されている。
【０１３８】
受付部２１０１、プログラム実行制御部２１０２及び入出力部２１０３は、第１の実施の形態で示す受付部１０１、プログラム実行制御部１０２及び入出力部１０３と同様であるのでここでの説明は省略する。
【０１３９】
（１−１）プログラム記憶部２１００
プログラム記憶部２１００は、図１６に示すように、粗粒度分割プログラム２１１０、線分決定プログラム２１１１及び中粒度分割プログラム２１１４を有しており、
粗粒度分割プログラム２１１０、中粒度分割プログラム２１１４、線分決定プログラム２１１１の順に実行される。
【０１４０】
粗粒度分割プログラム２１１０は、第１の実施の形態で示す粗粒度分割プログラム１１０と同様であるので、ここでの説明は省略する。
【０１４１】
（中粒度分割プログラム２１１４）
中粒度分割プログラム２１１４は、粗粒度分割プログラム２１１０が実行されることで生成された粗粒度分割曲線に対してＰＥ内のレジスタの数に応じた回数だけ当該ＰＥが最後に選択した１つの粗粒度分割曲線を２つの曲線に再帰的に分割し分割後の複数の曲線を中粒度分割曲線とし、当該複数の中粒度分割曲線それぞれに対する曲線情報を線分決定プログラム２１１１に引き渡す。
【０１４２】
（線分決定プログラム２１１１）
線分決定プログラム２１１１は、図１６に示すように、分割数決定プログラム２１１２及び細粒度分割プログラム２１１３から構成され、分割数決定プログラム２１１２及び細粒度分割プログラム２１１３の順に実行される。
【０１４３】
分割数決定プログラム２１１２は、中粒度分割プログラム２１１４の実行により生成された複数の中粒度分割曲線それぞれについて、当該中粒度分割曲線の分割数を決定する。なお、分割数の決定方法については、第１の実施の形態と同様であるので、ここでの説明は省略する。
【０１４４】
細粒度分割プログラム２１１３は、中粒度分割プログラム２１１４の実行により生成された複数の中粒度分割曲線それぞれについて、分割数決定プログラム２１１２の実行により決定された分割数に基づいて、近似線分に分割する。なお、近似線分への分割方法は、第１の実施の形態と同様であるので、ここでの説明は省略する。
【０１４５】
（２）ＰＥ２０２２ａ〜２０２２ｄ
ここでは、ＰＥ２０２２ａ〜２０２２ｄについて説明する。なお、ＰＥ２０２２ａ〜２０２２ｄは同一の構成であるので、以下、ＰＥ２０２２ａの構成について説明する。
【０１４６】
図１７は、ＰＥ２０２２ａの構成を示す図であり、ＰＥ２０２２ａは、入力メモリ２２０１ａ、処理部２２０２ａ及び出力メモリ２２０３ａを有している。
【０１４７】
（２−１）入力メモリ２２０１ａ及び出力メモリ２２０３ａ
入力メモリ２２０１ａ及び出力メモリ２２０３ａは、第１の実施の形態で示す入力メモリ２０１ａ及び出力メモリ２０３ａと同様であるので、ここでの説明は省略する。
【０１４８】
（２−２）処理部２２０２ａ
処理部２２０２ａは、プログラム実行制御部２１０２から出力された各プログラムの命令を実行するものである。
【０１４９】
具体的には、処理部２２０２ａは、機能的な構成要素である粗粒度分割部２２１１ａ、分割数決定部２２１２ａ、細粒度分割部２２１３ａ及び中粒度分割部２２１４ａから構成される。
【０１５０】
（粗粒度分割部２２１１ａ）
粗粒度分割部２２１１ａは、第１の実施の形態で示す粗粒度分割部２１１ａと同様であるので、ここでの説明は省略する。
【０１５１】
（中粒度分割部２２１４ａ）
中粒度分割部２２１４ａは、プログラム実行制御部２１０２から出力される中粒度分割プログラム２１１４の命令を実行するための機能要素である。
【０１５２】
通常、ベジェ曲線を２分割するに当たり、分割した曲線の曲線情報を格納するためには、少なくとも始点、終点及び制御点の３点それぞれを格納する３つの領域が必要である。
【０１５３】
そこで、中粒度分割部２２１４ａは、ＰＥ２０２２ａが３×２ｎ個以上のレジスタを有している場合には、当該個数から粗粒度分割曲線を分割する回数を算出する。具体的には、中粒度分割部２２１４ａは、２ｎの２の対数を繰り返し回数とする。
【０１５４】
中粒度分割部２２１４ａは、繰り返し回数を決定すると、粗粒度分割曲線を初期入力として、決定した回数分２分割を繰り返し、２ｎ個の分割曲線を生成する。
【０１５５】
（分割数決定部２２１２ａ）
分割数決定部２２１２ａは、プログラム実行制御部２１０２から出力される分割数決定プログラム２１１２の命令を実行するための機能要素である。分割数決定部２２１２ａは、分割数決定プログラム２１１２を実行することにより、中粒度分割部２２１４ａで生成された２ｎ個の分割曲線それぞれに対して、固定値及び曲線を構成する点の座標値の少なくともいずれかに応じた分割数ＤＩＶを決定する。
【０１５６】
分割数決定部２２１２ａは、算出した分割数ＤＩＶを細粒度分割部２２１３ａへ転送する。つまり、細粒度分割プログラム２１１３へ引き渡す。
【０１５７】
なお、分割数の決定方法は、第１の実施の形態と同様であるので、ここでの説明は省略する。
【０１５８】
（細粒度分割部２２１３ａ）
細粒度分割部２２１３ａは、プログラム実行制御部２１０２から出力される細粒度分割プログラム２１１３の命令を実行するための機能要素である。細粒度分割部２２１３ａは、分割数決定部２２１２ａで決定された、各分割曲線の分割数に基づいて、各分割曲線を近似線分に分割する。
【０１５９】
近似線分への分割方法は、第１の実施の形態と同様であるので、ここでの説明は省略する。
【０１６０】
３．２  動作
ここでは、曲線分割装置２０１０の動作について説明する。
【０１６１】
（１）粗粒度分割処理の動作について
本実施の形態における粗粒度分割処理の動作は、図５で示す流れ図で実現できるので、ここでの説明は省略する。
【０１６２】
（２）中粒度分割処理の動作について
ここでは、各ＰＥ２０２２ａ〜２０２２ｄにおいて、粗粒度分割処理で最後に選択された分割曲線を分割するμコード（中粒度分割プログラム２１１４）が実行されることによる中粒度分割処理の動作について説明する。
【０１６３】
中粒度分割処理では、粗粒度分割処理と同様の分割手順（図５のステップＳ１５、Ｓ２０参照）で、入力された曲線を２分割する。
【０１６４】
粗粒度分割処理では２分割した分割曲線のうち識別子の最下位ビットに応じて一の分割曲線を選択するが、中粒度分割処理では分割して２つの分割曲線とも再度２分割する点が異なる。つまり、２つの分割曲線それぞれについて、当該分割曲線を示す曲線情報（特に、始点、終点、制御点）をレジスタに設定する。そして、双方の分割曲線とも再度の分割する。この動作をレジスタの個数に応じて決定された回数繰り返す。例えば、上述したように、レジスタの個数が、３×２ｎ個以上である場合には、繰り返し回数は、ｎ回となる。
【０１６５】
（３）中粒度分割処理の具体例
ここでは、中粒度分割処理について、具体例を用いて説明する。
【０１６６】
中粒度分割処理、つまり当該処理を実現する中粒度分割プログラム２１１４を実行する中粒度分割部２２１４ａは、粗粒度分割部２２１１ａで選択された１つの粗粒度分割曲線を、レジスタの個数に応じた繰り返し回数分、再帰的に分割して、複数の中粒度分割曲線を生成する。
【０１６７】
例えば、粗粒度分割部２２１１ａで生成された粗粒度分割曲線を示す曲線情報（始点、制御点、終点）がレジスタＡ、Ｂ、Ｃに格納されているとすると、中粒度分割部２２１４ａでは、さらに１回２分割する場合には、レジスタＤ０（＝Ａ）、Ｅ０（＝Ｂ）、Ｆ０（＝Ｃ）、Ｄ１、Ｅ１、Ｆ１の計６個必要となる。すなわち必要なレジスタの数は２分割を行う前の２倍必要となる。使用可能なレジスタが１６個ある場合には、そのうちの１２個のレジスタを用いて２回の再帰分割を行うことができる（１回目の再帰分割で６個のレジスタ、２回目の再帰分割で１２個のレジスタが必要になるため）。２回の再帰分割を行うと、１つのプロセッサエレメントは４つの中粒度分割曲線を生成する。
【０１６８】
（４）線分決定処理について
ここでは、各ＰＥ２０２２ａ〜２０２２ｄにおいて、中粒度分割処理で最後に選択された分割曲線を分割するμコード（線分決定プログラム２１１１）が実行されることによる分割数決定処理の動作について説明する。
【０１６９】
線分決定処理に含まれる分割数決定処理、つまり当該分割数決定処理を実現する分割数決定プログラム２１１２を実行する分割数決定部２２１２ａは、中粒度分割部２２１４ａで生成された複数の中粒度分割曲線のそれぞれについて、当該中粒度分割曲線の分割数を決定する。なお、分割数の決定方法は、第１の実施の形態で示す数式３を、複数の中粒度分割曲線のそれぞれについて適用することで実現できる。
【０１７０】
線分決定処理に含まれる細粒度分割処理、つまり当該細粒度分割処理を実現する細粒度分割プログラム２１１３を実行する細粒度分割部２２１３ａは、複数の中粒度分割曲線のそれぞれについて、分割数決定部２２１２ａで決定された当該中粒度分割曲線の分割数に基づいて当該中粒度分割曲線を近似線分に分割する。なお、近似線分の生成方法については、第１の実施の形態と同様であるので、ここでの説明は省略する。
【０１７１】
３．３  まとめ
かかる構成によれば、プロセッサエレメント内の使用可能なレジスタの個数が多い場合には粗粒度分割曲線をさらに再帰分割しておくことにより、１つの入力曲線を複数の曲率の小さい曲線に分割できるためマルチプロセッサ向け処理ではない細粒度分割の処理をできるだけ少なくすることができ、高速にベジェ曲線を微小線分で近似することができる。
【０１７２】
４．変形例
以上、各実施の形態に基づいて説明したが、本発明は上記の各実施の形態に限られない。例えば、以下のような変形例が考えられる。
【０１７３】
（１）上記各実施の形態において、ＰＥには、識別子が予め保持されているものとしたが、これに限定されない。
【０１７４】
ＰＥに割り当てられる識別子は、ＣＰＵ１１が受付部を介して、入力データとして出力してもよい。
【０１７５】
（２）上記各実施の形態において、分割数決定プログラムによる分割数の決定は数式３を用いるものとしたが、これに限定されない。
【０１７６】
以下のように方法で、分割数を決定してもよい。
【０１７７】
始点座標（Ｘ０，Ｙ０）、制御点座標（Ｘ１，Ｙ１）、終点座標（Ｘ２，Ｙ２）で構成される２次ベジェ曲線の場合、曲線の中間点Ｍと始点と終点を結ぶ線分の中点Ｓを結ぶ線分の長さに係数をかけて分割数ＤＩＶの指標としてもよい。
【０１７８】
また、始点と制御点を結ぶ線分と終点と制御点を結ぶ線分の擬似的な長さの最大値を分割数ＤＩＶの指標としてもかまわない。例えば、数式５で求めたＤＩＶＦの値を整数値に変換した値を分割数ＤＩＶとしてもかまわない。
【０１７９】
【数５】
0005877381.tif 000006
【０１８０】
また、計算コストも削るためにＤＩＶに固定値を設定してもよい。例えば、曲線を構成する点の座標最小最大値がわかっている場合には、曲線の最大、最小座標値から構成される矩形（バウンダリボックス）の領域を表す値を計算し、当該値が固定値（閾値）よりも小さい場合にはＤＩＶ＝１（すなわちそれ以上の分割はしない）、固定値以上であればＤＩＶ＝固定分割数、とすればＤＩＶを計算するコストは小さくなる。
なお、ここにあげたＤＩＶの計算例はほんの一例であり、曲線を構成する座標値を示すパラメータ、あるいは固定値を用いて分割数ＤＩＶを計算していれば以上の例に限定したものではない。
【０１８１】
（３）上記各実施の形態において、各ＰＥはＳＩＭＤ構成であるとしが、これに限定されない。各ＰＥは、ＭＩＭＤ構成であってもよい。
【０１８２】
（４）上記第２の実施の形態において、各ＰＥの識別子は互いに異なるものとしたが、これに限定されない。
【０１８３】
各ＰＥの識別子は、プロセッサエレメント群内で識別できれば、異なるプロセッサエレメント群の間で重複していてもかまわない。例えば、同一のプロセッサエレメント群に属するＰＥ２２ａとＰＥ２２ｂそれぞれの識別子は重複しない識別子である必要があるが、
同一のプロセッサエレメント群に属さないＰＥ２２ａとＰＥ２２ｅそれぞれの識別子は同一の識別子であってもよい。
【０１８４】
また、繰り返し回数ｎに基づいて、識別子の下位ｎビットだけ有効なビットとすることも可能である。
【０１８５】
（５）上記実施の形態において、粗粒度分割時では識別子であるビット列を右シフトするものとしたが、これに限定されない。
【０１８６】
例えば、最上位ビットを参照する場合には、左シフトするとしてもよい。
【０１８７】
また、最上位ビット、最下位ビットに限らず、ビット列に含まれる特定位ビットを参照する場合には、右回りにローテーションするとしてもよいし、左回りにローテーションするとしてもよい。
【０１８８】
（６）上記各実施の形態において、曲線分割装置は、２次ベジェ曲線の分割に用いるものとしたが、これに限定されない。
【０１８９】
曲線分割装置は、３次ベジェ曲線の分割に用いてもよい。
【０１９０】
この場合、各ＰＥは、以下の手順で３次ベジェ曲線を複数の粗粒度分割曲線に分割する。なお、ここでは、図１８に示す、始点Ａ、制御点Ｂ、Ｃ、終点Ｄの４点が先ず与えられているものとする。
【０１９１】
（手順１）線分ＡＢ、ＢＣ、ＣＤの中点Ｅ、Ｆ、Ｇを求める。
【０１９２】
（手順２）線分ＥＦ、ＦＧの中点Ｈ、Ｉを求める。
【０１９３】
（手順３）線分ＨＩの中点Ｊを求める。
【０１９４】
（手順４）識別子の最下位ビットの値に応じて、点Ａ、Ｅ、Ｈ、Ｊの４点からなる３次ベジェ曲線、及び点Ｊ、Ｉ、Ｇ、Ｄの４点からなる３次ベジェ曲線の何れかを選択する。
【０１９５】
（手順５）上記手順１から４を、プロセッサエレメント数の２の対数分繰り返す。
【０１９６】
こうような手順により、各ＰＥには異なる粗粒度分割曲線（３次ベジェ曲線）が保持されることとなる。
【０１９７】
以降の手順は、上記第１の実施の形態と同様の手順で近似線分を求めることができる。
【０１９８】
（７）上記各実施の形態において、各プロセッサエレメント２２ａ〜２２ｄは、細粒度分割を行う際には割り当てられた曲線の分割のみを行ったが、これに限定されない。
【０１９９】
各プロセッサエレメント間でデータ通信を行い、細粒度分割を行う際には２以上のプロセッサエレメントで１つの曲線の分割を行ってもよい。
【０２００】
以下、その具体例について、図面を参照しながら、第１の実施の形態と異なる点を中心に説明する。なお、第１の実施の形態と同一の回路及び構成要素については、同一の符号を付し、その説明は省略する。
【０２０１】
（７−１）図２０は、本変形例に係る曲線分割装置３０００の構成を示す図である。なお、曲線分割装置３０００は、図示していないが、第１の実施の形態と同様に、受付部１０１を含む分割回路を有している。なお、本変形例においても第１の実施の形態と同様にＳＩＭＤ構成をとるものとする。
【０２０２】
第１の実施の形態と異なる点は、負荷分散部３３００が追加されていることである。また、負荷分散部３３００の追加により、ＰＥ３０２２ａは、第１の実施の形態とはその動作が異なる分割決定部３２１２ａ、細粒度分割部３２１３ａを有している。なお、ＰＥ３０２２ａ〜３０２２ｄにおいても、ＰＥ３０２２ａが有する分割決定部３２１２ａ、細粒度分割部３２１３ａと同様の機能要素を有している。
【０２０３】
（負荷分散部３３００）
負荷分散部３３００は、ＰＥ３０２２ａ〜３０２２ｄそれぞれのうち、細粒度分割処理を行わないＰＥを特定し、特指定したＰＥに対して、細粒度分割処理を行うＰＥとともに分割対象である粗粒度分割曲線の分割を行うよう指示をするものである。
【０２０４】
具体的には、負荷分散部３３００は、ＰＥ３０２２ａ〜３０２２ｄそれぞれから、当該ＰＥで算出された算出された分割数と、当該ＰＥの分割対象である粗粒度分割曲線を示す曲線情報と、当該ＰＥを示す識別子とからなる分割情報を受け取る。
【０２０５】
負荷分散部３３００は、受け取った各分割情報に基づいて、分割数１以下であるＰＥを１つ特定する。そして、分割数が最も多いＰＥで処理される粗粒度分割曲線を示す曲線情報と、対応する分割数を、特定したＰＥへ送信する。
【０２０６】
なお、ここでは、分割数１以下であるＰＥを１つ特定するとしたが、２つ以上特定してもよい。この場合、特定した２以上のＰＥに対して、一のＰＥで処理される粗粒度分割曲線を示す曲線情報と、対応する分割数を送信してもよい。または、特定した２以上のＰＥそれぞれに、互いに異なるＰＥで処理される粗粒度分割曲線を示す曲線情報と、対応する分割数を送信してもよい。
【０２０７】
このように、本変形例では、すべてのプロセッサエレメントの分割数を監視できるため、ＳＩＭＤプロセッサの並列性を最大生かすような細粒度分割の負荷分散を行うことができる。
【０２０８】
（分割数決定部３２１２ａ）
分割数決定部３２１２ａは、第１の実施の形態で示す分割数決定部２１２ａが有する処理機能に加えて、算出した分割数（ＤＩＶ）と、分割対象である粗粒度分割曲線を示す曲線情報と、入力メモリ２０１ａで記憶している識別子とからなる分割情報を負荷分散部３３００へ出力する。
（細粒度分割部３２１３ａ）
細粒度分割部３２１３ａは、ＰＥ３０２２ａの分割数決定部３２１２ａで算出された分割数が２以上であれば、第１の実施の形態で示す細粒度分割部２１３ａと同様の処理を行う。
【０２０９】
細粒度分割部３２１３ａは、負荷分散部３３００から他のＰＥで算出された分割数と曲線情報を受け取ると、受け取った分割数に基づいて、受け取った曲線情報で示される粗粒度分割曲線の分割を行う。
【０２１０】
これにより、ＰＥごとの粗粒度分割を行ってもまだ曲率が大きい場合に、細粒度分割の必要なＰＥの細粒度分割処理を、細粒度分割の必要がないＰＥを用いて分散して処理させることにより、さらにマルチプロセッサの並列性を生かして処理することができる利点を得ることができ、高速に複数のベジェ曲線を微小線分で近似することができる。
【０２１１】
（７−２）上記の変形例では、全てのＰＥについて１つの負荷分散部３３００が監視したが、ここでは、別の変形例について説明する。
【０２１２】
図２１は、本変形例に係る曲線分割装置４０００の構成を示す図である。なお、曲線分割装置４０００は、図示していないが、第１の実施の形態と同様に、受付部１０１を含む分割回路を有している。なお、本変形例においても第１の実施の形態と同様にＳＩＭＤ構成をとるものとする。
【０２１３】
第１の実施の形態と異なる点は、各ＰＥに負荷分散部４３００が追加されていることである。また、負荷分散部４３００の追加により、ＰＥ４０２２ａは、第１の実施の形態とはその動作が異なる細粒度分割部４２１３ａを有している。なお、ＰＥ４０２２ａ〜４０２２ｄにおいても、ＰＥ４０２２ａが有する細粒度分割部４２１３ａと同様の機能要素を有している。
【０２１４】
（負荷分散部４３００）
負荷分散部４３００は、隣接するＰＥの処理負荷を監視し、当該負荷分散部４３００が属するＰＥにおいて細粒度分割処理を行わず、且つ監視対象のＰＥが細粒度分割処理を行う場合に、監視対象のＰＥとともに当該監視対象のＰＥの分割対象である粗粒度分割曲線の分割を行うよう細粒度分割部４２１３に指示をするものである。
【０２１５】
具体的には、負荷分散部４３００は、プロセッサエレメント自身が隣接するプロセッサエレメントの分割数を監視する。ここでは、ＰＥ４０２２ａはＰＥ４０２２ｄを、ＰＥ４０２２ｂはＰＥ４０２２ａを、ＰＥ４０２２ｃはＰＥ４０２２ｂを、ＰＥ４０２２ｄはＰＥ４０２２ｃを、それぞれ監視する。
【０２１６】
負荷分散部４３００は、分割決定部２１２ａで算出された分割数が２以上である場合には、当該分割数と、分割対象である粗粒度分割曲線を示す曲線情報と、自身が属するＰＥを識別する識別子とからなる分割情報を、自身が属するＰＥを監視するＰＥの負荷分散部へ送信する。例えば、ＰＥ４０２２ａの負荷分散部４３００は、ＰＥ４０２２ａを監視するＰＥ４０２２ｂの負荷分散部へ分割情報を送信する。
【０２１７】
負荷分散部４３００は、他のＰＥ（ここでは、ＰＥ４０２２ｄ）から分割情報を受け取ると、分割決定部２１２ａで算出された分割数が１以下であるか否かを判断する。１以下であると判断する場合には、粗粒度分割部２１１ａで得られた曲線情報を出力メモリ２０３ａへ出力するとともに、他のＰＥから受け取った分割情報を細粒度分割部４２１３ａへ出力する。分割決定部２１２ａで算出された分割数が１以下でない、つまり２以上である場合には受け取った分割情報を破棄する。
【０２１８】
例えば、ＰＥ４０２２ａの分割数が８である場合には、隣接プロセッサエレメント（ＰＥ４０２２ｂ）へ分割情報を送信し、ＰＥ４０２２ｂの分割数が１であれば、ＰＥ４０２２ａとＰＥ４０２２ｂとで１つの曲線分割（ＰＥ４０２２ａの分割対象である粗粒度分割曲線の分割）を分散して処理することができる。また、ＰＥ４０２２ａの分割数が１の場合にのみ隣接プロセッサエレメント（ＰＥ４０２２ｄ）の細粒度分割処理の一部を行うことができる。
【０２１９】
なお、上記の監視対象の割り当ては、一例であり、これに限定されることではない。例えば、隣接する両方のＰＥを監視対象としてもよい。
（細粒度分割部４２１３ａ）
細粒度分割部４２１３ａは、ＰＥ４０２２ａの分割数決定部４２１２ａで算出された分割数が２以上であれば、第１の実施の形態で示す細粒度分割部２１３ａと同様の処理を行う。
【０２２０】
細粒度分割部４２１３ａは、負荷分散部４３００から他のＰＥで算出された分割数と曲線情報を受け取ると、受け取った分割数に基づいて、受け取った曲線情報で示される粗粒度分割曲線の分割を行う。
【０２２１】
（８）上記第１の実施の形態において、分割回路２１を、図２２に示す分割回路５０００に置き換えてもよい。
【０２２２】
以下、分割回路５０００を用いた場合について説明する。  本実施の形態においても第１の実施の形態と同様にＳＩＭＤ構成をとるものとする。
【０２２３】
図２２は、本変形例に係る分割回路５０００の構成を示す図である。
【０２２４】
分割回路５０００は、図２２に示すように、第１分割回路５００１、第２分割回路５００２及び分割数判定部５００３を有している。
【０２２５】
（第１分割回路５００１）
第１分割回路５００１は、プログラム記憶部５１００、受付部５１０１、プログラム実行制御部５１０２及び入出力部５１０３を有しており、上記第１の実施の形態で示す粗粒度分割と分割数決定とをＰＥ２２ａ〜ＰＥ２２ｄに実行させる。つまり、第１分割回路５００１は、入力された１つの曲線に対し粗粒度分割と分割数決定終えた時点で一度プログラムを終了する。
【０２２６】
プログラム記憶部５１００は、粗粒度分割プログラム５１１０及び分割数決定プログラム５１１２を記憶している。粗粒度分割プログラム５１１０及び分割数決定プログラム５１１２それぞれは、粗粒度分割プログラム１１０及び分割数決定プログラム１１２と同様であるので、ここでの説明は省略する。
【０２２７】
受付部５１０１は、第１の実施の形態で示す受付部１０１と同様であるので、ここでの説明は省略する。
【０２２８】
プログラム実行制御部５１０２は、粗粒度分割プログラム５１１０及び分割数決定プログラム５１１２をＰＥ２２ａ〜ＰＥ２２ｄに実行させるものである。
【０２２９】
入出力部５１０３は、ＰＥ２２ａ〜ＰＥ２２ｄそれぞれから、粗粒度分割プログラム５１１０及び分割数決定プログラム５１１２の実行結果として、当該ＰＥで算出された分割数と、分割対象の粗粒度分割曲線を示す曲線情報とからなる分割結果情報を受け取り、分割数判定部５００３へ出力する。
【０２３０】
（分割数判定部５００３）
分割数判定部５００３は、各ＰＥ２２ａ〜２２ｄから出力された分割結果情報をもとに、分割数が１以下の粗粒度分割された曲線の曲線情報を、ラスタライズ回路１２へ転送する。分割数が１より大きい粗粒度分割された曲線の曲線情報を第２分割回路５００２へ転送する。
【０２３１】
（第２分割回路５００２）
第２分割回路５００２は、プログラム記憶部５２００、受付部５２０１、プログラム実行制御部５２０２及び入出力部５２０３を有しており、上記第１の実施の形態で示す粗粒度分割、分割数決定及び細粒度分割をＰＥ２２ａ〜ＰＥ２２ｄに実行させる。つまり、第２分割回路５００２は、第１の実施の形態の分割回路２１と同様の機能を有している。第１の実施の形態と異なる点は、第２分割回路５００２は、第１分割回路５００１で分割された曲線を扱うことである。
【０２３２】
受付部５２０１は、分割判定部５００３から受け取った曲線情報をＰＥ２２ａ〜２２ｄへ出力する。このとき、受付部５２０１は、分割判定部５００３から受け取った曲線情報が複数ある場合には、各々の曲線情報を順次出力する。出力するタイミングは、先の曲線情報について処理が終わった時点である。
【０２３３】
プログラム記憶部５２００は、粗粒度分割プログラム５２１０、及び分割数決定プログラム５２１２と細粒度分割プログラム５２１３からなる線分決定プログラム５２１１を記憶している。粗粒度分割プログラム５２１０、分割数決定プログラム５２１２及び粗粒度分割プログラム５２１３それぞれは、粗粒度分割プログラム１１０、分割数決定プログラム１１２及び粗粒度分割プログラム１１３と同様であるので、ここでの説明は省略する。
【０２３４】
プログラム実行制御部５２０２は、粗粒度分割プログラム５２１０、分割数決定プログラム５２１２及び細粒度分割プログラム５２１３を用いて、プログラム実行制御部１０２と同様の動作を行う。
【０２３５】
入出力部５２０３は、入出力部１０３と同様であるので、ここでの説明は省略する。
【０２３６】
かかる構成によれば、分割数決定の時点で細粒度分割の必要がない曲線をラスタライズ回路１２に出力し、さらなる分割が必要な曲線のみを再び分割することにより、プロセッサエレメントが処理する曲線はより曲率が小さいものとなるためマルチプロセッサの並列性を生かして処理することができる利点を得ることができ、高速に複数のベジェ曲線を微小線分で近似することができる。
【０２３７】
（９）上記各実施の形態において、受付部は典型的には集積回路であるＬＳＩとして実現される。また、上述したように、粗粒度分割部、分割数決定部、細粒度分割部及び中粒度分割部は、典型的には集積回路であるＬＳＩの一部であるプロセッサエレメント上で動作するμコードとして実現される。
【０２３８】
受付部及びプロセッサエレメントは個別に１チップ化されてもよいし、一部またはすべてを含むように１チップ化されてもよい。ここではＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。
また、集積回路化の手法はＬＳＩに限るものではなく、専用回路または汎用ＳＩＭＤプロセッサで実現してもよい。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサを利用してもよい。
さらには、半導体技術の進歩または派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。バイオ技術の適応などが可能性としてありえる。
【０２３９】
（１０）上記の実施の形態で説明した手法の手順を記述したプログラムをメモリに記憶しておき、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）などがメモリからプログラムを読み出して、読み出したプログラムを実行することによって、上記の手法が実現されるようにしてもよい。
【０２４０】
また、当該手法の手順を記述したプログラムを記録媒体に格納して、頒布するようにしてもよい。
【０２４１】
（９）上記実施の形態及び変形例を組み合わせるとしてもよい。
【０２４２】
５．補足
（１）本発明の一実施態様である、曲線分割装置は、それぞれ異なる設定値が付与された少なくともＮ（Ｎは２以上の整数）個のプロセッサエレメントと、ベジェ曲線を示す曲線情報を外部から受け取る受取手段と、前記曲線情報を初期の入力情報とし、当該入力情報で示される曲線を２分割して２つの分割曲線を生成し、前記設定値に基づいて２つの分割曲線のうち一の分割曲線を選択して当該分割曲線を示す入力情報を定め、前記Ｎ個のプロセッサエレメントが互いに異なる分割曲線を選択するまで当該２分割を繰り返す分割アルゴリズムを、前記Ｎ個のプロセッサエレメントに実行させる第１実行手段と、前記分割アルゴリズムにより最後に選択された分割曲線に近似するよう構成する１つ以上の線分を決定する決定アルゴリズムを、前記Ｎ個のプロセッサエレメントに実行させる第２実行手段とを備えることを特徴とする。
【０２４３】
上記に示す構成によると、曲線分割装置は、Ｎ個のプロセッサエレメントに、互いに異なる分割曲線を選択するまで分割アルゴリズムを実行させるので、実行終了後には各プロセッサエレメントは初期入力されたベジェ曲線の曲率よりも小さい曲率である分割曲線を選択していることになる。そのため、各プロセッサエレメントは、曲率の小さい分割曲線に近似するよう構成する１つ以上の線分を決定するので、プロセッサエレメント間での処理負荷にバラつきを抑えることができる。これにより、曲線分割装置は、マルチプロセッサシステムにおいてベジェ曲線の分割処理を効率良く行うことができる。
【０２４４】
（２）ここで、前記第１実行手段及び前記第２実行手段それぞれは、前記少なくともＮ個のプロセッサエレメントに、ＳＩＭＤ型プログラムを並列に実行させることで、前記分割アルゴリズム及び前記決定アルゴリズムそれぞれを実行させるとしてもよい。
【０２４５】
この構成によると、曲線分割装置における第１実行手段及び第２実行手段それぞれは、Ｎ個のプロセッサエレメントにＳＩＭＤ型プログラムを並列に実行させるので、各プロセッサエレメントに同一のアルゴリズムを同時に実行させることができ、ベジェ曲線の分割処理を効率良く行うことができる。
【０２４６】
（３）ここで、前記Ｎは、２のｎ乗（ｎは１以上の整数）であり、前記分割アルゴリズムにおける繰り返しの回数はｎであるとしてもよい。
【０２４７】
この構成によると、曲線分割装置の第１実行手段は、２のｎ乗個のプロセッサエレメントに分割アルゴリズムの繰り返しをｎ回実行させるので、互いに異なる分割曲線を確実に選択することができる。
【０２４８】
（４）ここで、各プロセッサエレメントに付与された前記設定値は、当該プロセッサエレメントを一意に識別するためのｎビット長のデータであり、前記分割アルゴリズムは、前記設定値を示すデータの特定位ビットの値に応じて、一の分割曲線を選択し、選択後において前記設定値を示す値からなるビット列をシフトした新たなビット列を、次回の選択に用いる値とするとしてもよい。
【０２４９】
この構成によると、曲線分割装置の第１実行手段は、各プロセッサエレメントにｎビット長のデータ列をシフトしながら特定位ビットの値を分割曲線の選択に用いることで、ｎ回の繰り返し後には確実に互いに異なる分割曲線を選択させることができる。
【０２５０】
（５）ここで、前記入力情報は、曲線の始点Ａ、制御点Ｂ及び終点Ｃからなり、前記分割アルゴリズムは、線分ＡＢとの中点Ｄ、及び線分ＢＣとの中点Ｅを算出し、算出した前記点Ｄと前記点Ｅとからなる線分ＤＥの中点Ｆを算出することで、前記点Ａ、Ｂ、Ｃから定まる曲線を、前記点Ａを始点、前記点Ｅを終点及び前記点Ｄを制御点とする分割曲線と、前記点Ｆを始点、前記点Ｃを終点及び前記点Ｅを制御点とする分割曲線とに２分割するとしてもよい。
【０２５１】
この構成によると、第１実行手段は、各プロセッサエレメントに曲線の始点、制御点及び終点の３点を用いて容易に当該曲線を２分割させることができる。
【０２５２】
（６）ここで、前記第１実行手段は、さらに、前記ベジェ曲線とは別のベジェ曲線を示す、前記曲線情報とは別の曲線情報を初期の入力情報として、前記分割アルゴリズムを、前記Ｎ個のプロセッサエレメントとは異なるＭ（Ｍは２以上の整数）個のプロセッサエレメントに実行させ、前記第２実行手段は、さらに、前記決定アルゴリズムを、前記Ｍ個のプロセッサエレメントに実行させるとしてもよい。
【０２５３】
この構成によると、曲線分割装置は、初期入力として与えられた、異なるベジェ曲線を、Ｎ個のプロセッサエレメントの組と、Ｍ個のプロセッサエレメントの組とで、並列に分割を行うことができる。
【０２５４】
（７）ここで、前記分割アルゴリズムは、選択した分割曲線を示す情報を格納するレジスタをＬ個必要とし、前記Ｎ個のプロセッサエレメントそれぞれは、レジスタを、Ｌ×２ｎ（ｎは１以上の整数）個以上有しており、前記第２実行手段は、前記決定アルゴリズムを、前記Ｎ個のプロセッサエレメントに実行させるに先立って、前記Ｎ個のプロセッサエレメントに、前記最後に選択された分割曲線を示す曲線情報を初期の入力情報とし、２分割をｎ回繰り返す再分割アルゴリズムを実行させ、前記決定アルゴリズムは、前記再度に選択された分割曲線に前記再分割アルゴリズムを施すことで得られた１つ以上の曲線毎に、当該曲線に近似するよう１つ以上の線分を決定するとしてもよい。
【０２５５】
この構成によると、曲線分割装置の第２実行手段は、各プロセッサエレメントに、分割アルゴリズムで分割された各分割曲線について、決定アルゴリズムを用いる前に再分割アルゴリズムを実行させることで、より細かな分割曲線を得ることができるので、決定アルゴリズムの実行時には効率良く線分を決定することができる。
【０２５６】
（８）ここで、前記決定アルゴリズムは、前記最後に選択された分割曲線を示す分割曲線情報に基づいて、当該分割曲線における曲率に応じて当該分割曲線を分割する分割数を算出し、算出した前記分割数に応じて前記分割曲線を分割し、分割した曲線毎に当該曲線に近似する線分を決定するとしてもよい。
【０２５７】
この構成によると、曲線分割装置は、分割曲線の曲率に応じて当該分割曲線を１つ以上の曲線に分割し、分割した曲線について近似する線分を決定するので、決定された線分を用いることで、分割曲線に近似するものを確実に構成することができる。
【０２５８】
（９）ここで、前記分割数の算出の結果により分割が必要ない一のプロセッサエレメントが、分割が必要である他のプロセッサエレメントを特定した場合には、前記第２実行手段は、当該一のプロセッサエレメント及び当該他のプロセッサエレメントに対して、当該他のプロセッサエレメントが最後に選択した分割曲線について当該他のプロセッサエレメントで決定された分割数に応じて分割を行うとしてもよい。
【０２５９】
この構成によると、曲線分割装置は、第１実行手段によりプロセッサエレメント毎に、分割を行ってもまだ曲率が大きい場合に、分割を必要としない一のプロセッサエレメントは、分割を必要とする他のプロセッサエレメントとともに当該他のプロセッサエレメントでの分割対象となる分割曲線を分割する。これにより、曲線分割装置は、複数のプロセッサエレメントの並列性を生かし、高速にベジェ曲線を微小線分で近似することができる。
【０２６０】
（１０）ここで、前記第２実行手段は、前記分割数の算出の結果により分割が必要ない分割曲線を示す曲線情報については外部へ出力し、前記分割数の算出の結果により分割が必要な分割曲線を示す曲線情報については、算出した前記分割数に応じた分割に先立って、前記Ｎ個のプロセッサエレメントに、当該曲線情報を初期の入力情報とし、２分割をｎ回繰り返す再分割アルゴリズムを実行させ、当該再分割アルゴリズムの実行後、再度前記決定アルゴリズムを実行させるとしてもよい。
【０２６１】
この構成によると、曲線分割装置は、第２実行手段により線分の近似を行うに先立って、さらなる分割が必要な分割曲線のみを再び分割することにより、プロセッサエレメントが第２実行手段で線分の近似を行う際には処理対象となる曲線はより曲率が小さいものとなるので、高速にベジェ曲線を微小線分で近似することができる。
【産業上の利用可能性】
【０２６２】
本発明にかかる曲線分割装置は、マルチプロセッサシステム構成を持つ携帯電話やテレビといった組み込み機器上でのアウトラインフォントをはじめとするベクターグラフィックス表示方式として有用である。
【符号の説明】
【０２６３】
１    情報処理装置
１０    曲線分割装置
１１    ＣＰＵ
１２    ラスタライズ回路
１３    フレームバッファ
１４    表示装置
２１    分割回路
２２ａ〜２２ｄ  プロセッサエレメント（ＰＥ）
１００    プログラム記憶部
１０１    受付部
１０２    プログラム実行制御部
１０３    入出力部
１１０    粗粒度分割プログラム
１１１    線分決定プログラム
１１２    分割数決定プログラム
１１３    細粒度分割プログラム
２０１ａ〜２０１ｄ  入力メモリ
２０２ａ  処理部
２０３ａ  出力メモリ
２１１ａ  粗粒度分割部
２１２ａ  分割数決定部
２１３ａ  細粒度分割部
【図１】
0005877381.tif 000007
【図２】
0005877381.tif 000008
【図３】
0005877381.tif 000009
【図４】
0005877381.tif 000010
【図５】
0005877381.tif 000011
【図６】
0005877381.tif 000012
【図７】
0005877381.tif 000013
【図８】
0005877381.tif 000014
【図９】
0005877381.tif 000015
【図１０】
0005877381.tif 000016
【図１１】
0005877381.tif 000017
【図１２】
0005877381.tif 000018
【図１３】
0005877381.tif 000019
【図１４】
0005877381.tif 000020
【図１５】
0005877381.tif 000021
【図１６】
0005877381.tif 000022
【図１７】
0005877381.tif 000023
【図１８】
0005877381.tif 000024
【図１９】
0005877381.tif 000025
【図２０】
0005877381.tif 000026
【図２１】
0005877381.tif 000027
【図２２】
0005877381.tif 000028