曲線分割装置、曲線分割方法、曲線分割プログラム、曲線分割プログラムを記録した記録媒体、曲線分割集積回路
【課題】曲線を直線に近似するときに、スタックを用いて再帰的に分割していく方法があるが、ＳＩＭＤプロセッサのような並列処理システムでは応用しにくく、スタックを使用せず出力された曲線を再帰的に並列分割させようとすると出力曲線数が多くなりすぎ大量のメモリ領域が必要となる。
【解決手段】入力タスクを時分割処理するＳＩＭＤプロセッサは１曲線を２曲線に分割する曲線分割処理を行い、プロセッサ終了信号を受けたときに分割対象曲線がある場合にプロセッサの実行状態に依存せず曲線出力領域の曲線を再分割する水平方向分割と、分割対象曲線がある場合でもプロセッサの実行完了を待ち新たに分割された曲線を優先して再分割対象とする垂直方向分割とを動的に切り替える分割方向切替手段を具備することで高い並列性と省メモリを実現する。
【解決手段】入力タスクを時分割処理するＳＩＭＤプロセッサは１曲線を２曲線に分割する曲線分割処理を行い、プロセッサ終了信号を受けたときに分割対象曲線がある場合にプロセッサの実行状態に依存せず曲線出力領域の曲線を再分割する水平方向分割と、分割対象曲線がある場合でもプロセッサの実行完了を待ち新たに分割された曲線を優先して再分割対象とする垂直方向分割とを動的に切り替える分割方向切替手段を具備することで高い並列性と省メモリを実現する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アウトラインフォントなどのベクターデータに含まれるベジェ曲線を直線に近似する曲線分割方法に関するもので、ＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ Ｍｕｔｌｉｐｌｅ Ｄａｔａ）プロセッサを用いて入力された曲線分割タスクを時分割で行う際に並列性を生かした直線近似を行う曲線分割装置、曲線分割方法、曲線分割プログラム、曲線分割プログラムを記録した記録媒体、曲線分割集積回路に関するものである。
【背景技術】
【０００２】
コンピュータグラフィックスにおいて、アウトラインフォントなどのベクターコンテンツを表示するには曲線描画機能が必須である。従来の組み込み機器ではあらかじめ作成した固定サイズのビットマップを並べて表示していた文字表示機能が、今日のＣＰＵやグラフィックＬＳＩの進化に伴いアウトラインフォントから任意のサイズのフォントビットマップをリアルタイムに作成できるようになっている。アウトラインフォントは、文字の形状を、基準となる点の座標と輪郭線の集まりとして表現する形式であり、フォントの形状を定義するグリフデータを含んでいる。グリフデータは、２次元の「点座標列」と、点列をどのように結んでいくかを定義する「コマンド」から構成される。フォントの描画とは、グリフデータをラスタ化することである。ラスタ化とは、直線や曲線を表す数値データであるベクターデータをビットマップに変換する処理である。
【０００３】
ここで、アウトラインフォントの代表例であるＴｒｕｅＴｙｐｅフォントでは、「コマンド」の代わりに、輪郭線上の点であるのか、輪郭線を構成する曲線の制御点であるのかを示すビットが各点に付加されており、それぞれ直線と２次ベジェ曲線に代替できる。すなわち、フォント形状上の点であれば「直線」として解釈し、フォント形状上の点でなければ当該点は「２次ベジェ曲線」として解釈できる。よって、フォントを描画するには、直線と２次ベジェ曲線のラスタライズを行えばよい。ラスタライズとは、コンピュータが扱う文字や画像を、プリンタで印刷したりディスプレイに表示できるように、色付きの小さな点の集まりで表現することである。ここで、２次ベジェ曲線をラスタライズする一つの方法として、曲線コマンドを複数の直線に近似し、すべてのコマンドを直線で処理する方法がある。
【０００４】
ここで、ベジェ曲線について説明する。２次ベジェ曲線は３点Ｐ０、Ｐ１、Ｐ２から構成され、パラメータｔを用いたパラメトリック曲線として数式１のように表現できる。また、３次ベジェ曲線は４点Ｐ０、Ｐ１、Ｐ２、Ｐ３から構成され、同様に数式２のように表現できる。
【０００５】
【数１】
【０００６】
【数２】
【０００７】
曲線コマンドを複数の直線で近似するには図２のようにベジェ曲線のパラメータｔに０．０から１．０の値を等間隔で入れて曲線上の点を求めていくことができる。しかし、曲率によっては、ほぼ直線にもかかわらず過度な分割が行われる。さらに、曲率が大きい場合には逆に分割が少なく、がたつきが生じるという課題が発生する。図２では、ｔを０．１間隔でずらしていく様子を表したものだが、ｔ＝０．７〜ｔ＝１．０のような曲率が小さいにもかかわらず分割されてしまう現象が発生する。このような課題を解決する方式として、ベジェ曲線の特徴を利用した再帰的曲線分割方式がある。図３のような２次ベジェ曲線を用いて説明する。ベジェ曲線には、ベジェ曲線を構成する点３０１、３０２、３０３の点３０１と３０２を結ぶ線分の中点３０４、点３０２と３０３を結ぶ線分の中点３０５、点３０４と３０５を結ぶ線分の中点３０６を用いて、２つのベジェ曲線３０１、３０４、３０６（左側ベジェ曲線）と３０６、３０５、３０３（右側ベジェ曲線）に分割することができるという特徴がある。さらに左側ベジェ曲線３０１、３０４、３０６は、２つのベジェ曲線３０１、３０７、３０９と３０９、３０８、３０６に、右側ベジェ曲線３０６、３０５、３０３は、２つのベジェ曲線３０６、３１０、３１２と３１２、３１１、３０３に分割できる。このように分割回数を増やし深さ方向に再帰的に分割を行い、ある段階まで分割したら構成点を直線で結んでいけば直線に近似した曲線を描画することができる。再帰的に分割するか否かの判定は１回の分割毎に行われ、曲線の曲率に応じて判断される。したがって、直線に近い部分は殆ど分割されず、曲率が大きい部分は細かく分割されるので、描画結果として滑らかな曲線描画を実現できる。
【０００８】
このような従来の再帰的曲線分割方式を使用した例として、スタックメモリを用いて逐次的に再帰的曲線分割を行う曲線分割装置があった（例えば、特許文献１参照）。図４は特許文献１に記載された従来の曲線分割装置の構成の一例を示すブロック図である。
【０００９】
図４において、曲線の制御点の各座標値を格納する第１のレジスタ４０１と、レジスタで保持されている制御点を２分割し、２組の曲線の各制御点を形成する２分割回路４０２と、２分割回路によって生成された２組の曲線の各制御点を格納する第２のレジスタ４０３と、複数組の各制御点を順次格納するスタックメモリ４０４と、第１、第２のレジスタとスタックメモリとの間に位置し、１組の各制御点を格納する第３のレジスタ４０５と、第２のレジスタで格納される制御点に基づき、２分割回路で制御点の２分割を行わせるか否かを決定する判定回路４０６とを備えている。
【特許文献１】特開平８−３２９２６１号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、上記従来の構成を、入力タスクを時分割で処理できるＳＩＭＤプロセッサシステムに適用した場合、スタックメモリを用いた逐次処理を行うことになりマルチプロセッサの利点をまったく得ることができない。図５における点線は、スタックメモリを用いた逐次処理を行った場合の処理の流れである。曲線の上下関係は、それぞれの依存関係を示している。図５のように、曲線の分割は深さ方向に行われる。そして、従来例のような再帰的分割は、一つ前に分割された曲線を使う。そのため、再帰的分割でＳＩＭＤプロセッサの並列性を活かすのは難しい。さらに、同様の理由で、入力データを異なるタスクに割り付ける時分割処理も難しい（一つ前に分割された曲線をさらに細かい２つの曲線に分割している）。
【００１１】
そこで、再帰的分割処理を複数のＳＩＭＤプロセッサで並列に動作させようとした場合は、図６のように動作させるのが好ましい。そうすると、１つの曲線が２つの曲線に同時に分割され、２つの曲線は４つの曲線に同時に分割され、・・・・Ｎ個の曲線は２×Ｎ個の曲線に・・・・と、並列処理が可能になる。なお、図６に記載の番号は、実行順序を示している。そして、さらに依存関係のない曲線データを異なるタスクに割り付ける時分割処理が可能になる。しかしながら、上記方法の場合、曲線が十分直線に近似されていると判断されるまで分割した曲線を保持しておかなければならず、メモリが増大してしまうという課題が新たに発生してしまう。
【００１２】
本発明は、上記従来の課題を解決するもので、ＳＩＭＤプロセッサの利点である並列性を活かしながらも、少ないメモリで滑らかな直線近似を実現する曲線分割装置を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記従来の課題を解決するために、本発明の曲線分割装置は、各プロセッサが入力タスクを時分割処理するＳＩＭＤプロセッサシステムにおいて、Ｎ個の曲線を構成する点と評価値をＮ個のＳＩＭＤプロセッサに入力する曲線入力手段と、前記評価値をもとに曲線分割処理を行うか近似直線出力処理を行うかを判断し、曲線分割処理を行う場合には左側曲線と右側曲線の２つの曲線に分割し２曲線を構成する点と評価値を曲線出力領域に出力し、近似直線出力処理を行う場合には入力曲線を構成する点から求めた直線を直線出力領域に出力する曲線処理手段と、入力タスクに割り当てられた前記曲線処理手段の実行制御を行い、処理終了時に終了信号を発行する前記ＳＩＭＤプロセッサと、前記ＳＩＭＤプロセッサから終了信号を受けたときに、前記曲線出力領域に曲線が存在する場合前記曲線処理手段の実行状態に依存せずに前記曲線出力領域の曲線を前記曲線入力手段に再入力する水平方向分割と、前記曲線出力領域に曲線が存在する場合でも前記ＳＩＭＤプロセッサからの終了信号を待ち新たに出力された曲線を優先してＮ＝１として前記曲線入力手段に再入力する垂直方向分割とを動的に切り替える分割方向切替手段とを具備し、はじめに設定された１個の曲線を構成する点と評価値に対して再帰的に行うことで所望の曲線近似直線を生成するので、ＳＩＭＤプロセッサの利点である並列性を活かしながらも、少ないメモリ容量で滑らかな直線近似を実現することができる。
【発明の効果】
【００１４】
本発明によれば、入力曲線に対しての曲線分割を終えて再分割の必要がある場合に、並列性を生かし他の曲線分割処理の完了を待たずにすでに分割済みの曲線を順に曲線入力手段に再入力する水平方向分割と、曲線分割処理の完了を待って新たに出力された曲線を優先して曲線入力手段に再入力する垂直方向分割とを動的に切り替える分割方向切替手段を設けることで、ＳＩＭＤプロセッサの利点である並列性を活かしながらも、少ないメモリ容量で滑らかな直線近似を実現することができる。
【発明を実施するための最良の形態】
【００１５】
以下本発明の実施の形態について、図面を参照しながら説明する。
【００１６】
（実施の形態１）
図１は、本発明の実施の形態１における曲線分割装置の構成を示すブロック図である。曲線分割装置は、曲線入力手段１０１と、ＳＩＭＤプロセッサ１０２と、曲線処理手段１０３と、曲線出力領域１０４と、直線出力領域１０５と、分割方向切替手段１０６と、で構成される。
【００１７】
曲線入力手段１０１は、Ｎ個の曲線を構成する点と評価値とを、それぞれＮ個のＳＩＭＤプロセッサ１０２に入力する。Ｎ個の曲線を構成する点とは、例えば、２次ベジェ曲線の場合には、図７に示すように、７０１、７０２、７０３を表す点である。また、３次ベジェの場合には、図７に示すように、７０７、７０８、７０９、７１０を表す点である。そして、Ｎ個の曲線を構成する点は、少なくとも始点と終点、そして曲率を制御する制御点で構成される。さらに、点の位置は２次元座標で表現できる。
【００１８】
評価値とは、入力された曲線がすでに十分直線に近似できているかを判断するための値である。評価値は、曲線処理手段１０３内で１つの曲線を２つの曲線に分割するときに計算される。評価値を計算するための評価式は本特許では特に限定しないが、点の位置座標に依存したものが望ましい。たとえば評価式の一例としては、点のうち曲線の始点と終点を示す座標値Ｓ（ＳＸ、ＳＹ）、Ｅ（ＥＸ、ＥＹ）の各座標成分の差分の絶対値の和（｜ＳＸ−ＥＸ｜＋｜ＳＹ−ＥＹ｜）としたものが挙げられる。また、評価式は、曲線を囲むようなバウンダリ領域の大きさを評価式としてもかまわない。さらに、分割対象となる曲線をはじめに入力するときに、あえて必ず再分割されるような評価値を初期値として設定しておいてもかまわない。また、Ｎの最大値はＳＩＭＤプロセッサの個数であり、分割方向切替手段１０６で決まる水平方向分割と垂直方向分割により切り替わる。分割対象となる曲線をはじめに入力するときはＮ＝１で行う。
【００１９】
そして、曲線入力手段１０１は、曲線を構成する点と評価値を各ＳＩＭＤプロセッサ１０２に転送する。
【００２０】
ＳＩＭＤプロセッサ１０２は、複数のＳＩＭＤプロセッサから構成される。各ＳＩＭＤプロセッサは、曲線入力手段から転送された曲線を構成する点と評価値を受け取り、曲線処理手段１０３の処理プログラムの入力データとして投入したのち、曲線処理手段１０３の処理プログラム（再分割判定及び分割曲線出力、又は再分割判定及び近似直線出力）を実行制御し、曲線処理手段１０３の終了時に分割方向切替手段１０６に終了信号を発行する。各ＳＩＭＤプロセッサは、異なる入力曲線に対して、曲線処理手段１０３による処理を行う。さらに、ＳＩＭＤプロセッサは、入力タスクを時分割で処理する特徴を持つ。すなわち、プロセッサごとに異なる入力データを同じ処理プログラムで処理することが可能であるとともに（ＳＩＭＤプロセッサの特徴）、各プロセッサにおいても異なる入力データ（別の入力タスク）を時分割で処理することが可能である（入力タスクの時分割処理）。ＳＩＭＤプロセッサなので、ある入力タスクに対しての曲線処理手段１０３の処理は同時に終了する。
【００２１】
曲線処理手段１０３は、評価値と判定のための閾値と比較し、入力された曲線が、十分に直線近似されているかどうかを判断する。入力された曲線が直線近似されていると判断したら、入力曲線を近似直線と見立てて直線出力領域１０５に出力する。入力された曲線が直線近似されていないと判断したら、再分割が必要だと判断し、曲線分割を行う。そして、曲線分割によって生成された２曲線を曲線出力領域１０４に出力する。曲線処理手段１０３は、典型的にはＳＩＭＤプロセッサ１０２上で動作するプログラムとして実現される。
【００２２】
各ＳＩＭＤプロセッサは、入力曲線の点と評価値に対して前述のような曲線処理を行うことになり、結果としてプロセッサごとに直線出力を行うか、曲線分割して曲線出力を行うかが異なる可能性がある。ある曲線に対して十分直線に近似できていると判断した場合、入力曲線の点をもとに近似直線を作り直線出力領域１０５へ出力する。どのような直線を生成するかは具体的には限定しないが、曲線を構成する点を通るような直線であることが望ましい。例えば始点と終点を結んだ線分を出力してもかまわない。また、入力曲線のうちすべての点を結んだ複数の線分を出力してもかまわない。
【００２３】
上記曲線分割は、１つの曲線を２つに分割する再帰分割処理で行われる。再帰分割処理は、分割後でも同じ特徴を持つ曲線に分割する処理である。再帰分割処理される曲線は、分割後でも同じ特徴を持つ曲線である。ベジェ曲線などは代表的な再帰分割可能な曲線の一つである。図７のように、１つの２次ベジェ曲線７０１、７０２、７０３は、７０１と７０２の中点である７０４、７０２と７０３の中点である７０５を結ぶ線分７０４、７０５のさらに中点７０６を用いて、２つの２次ベジェ曲線７０１、７０４、７０６と７０６、７０５、７０３に分割することができる。また、１つの３次ベジェ曲線７０７、７０８、７０９、７１０も同様に、７０７と７０８の中点である７１１、７０８と７０９の中点である７１２、７０９と７１０の中点である７１３、７１１と７１２の中点である７１４、７１２と７１３の中点である７１５、７１４と７１５の中点である７１６を用いて、２つの３次ベジェ曲線７０７、７１１、７１４、７１６と７１６、７１５、７１３、７１０に分割することができる。分割されたベジェ曲線の点を用いて、それぞれ新たに評価式を適用し評価値を計算しベジェ曲線を構成する点とともに曲線出力領域１０４に出力する。
【００２４】
曲線出力領域１０４は、曲線処理手段１０３でまだ十分に直線に近似されていないと判断し出力された曲線を格納する。ＳＩＭＤプロセッサからアクセス可能なメモリであれば、レジスタファイルで構成されていてもよいし、ＳＲＡＭのような容量の大きいメモリで構成されていても良い。曲線出力領域１０４に出力された曲線は、直線近似のために曲線入力手段１０１で再入力されさらなる曲線分割処理が行われる。
【００２５】
直線出力領域１０５は、曲線処理手段１０３で入力された曲線が直線近似されていると判断された場合に、上記近似直線を格納する。一例として、上記近似直線は、近似直線の開始点座標と終了点座標、及び直線の傾き値と切片値の組として保持する。ＳＩＭＤプロセッサからアクセス可能なメモリであれば、レジスタファイルで構成されていてもよいしＳＲＡＭのような容量の大きいメモリで構成されていても良い。直線出力領域１０５に出力された直線は、十分近似できているものとして扱われ、例えば線を描画するラスタライザで処理される。
【００２６】
分割方向切替手段１０６は、曲線入力手段１０１に再入力する水平方向分割と、曲線入力手段１０１に再入力する垂直方向分割と、を動的に切り替えるものである。
【００２７】
水平方向分割とは、再分割すべき１つ以上の曲線を同時に曲線入力手段１０１に再入力するモードである。例えばＭ個（ＭはＳＩＭＤプロセッサ数）のベジェ曲線を曲線入力手段１０１に同時に入力し、曲線処理手段１０３がすべて再分割必要と判断した場合、２×Ｍ個の曲線が同時に曲線出力領域に出力されることになる。しかし、同時出力された２×Ｍ個の曲線は、すべて分割の深さ（分割回数）が同じであるため、これらの曲線間には依存関係は発生しない。そのため、曲線出力領域に出力された２×Ｍ個の曲線のうち、ＳＩＭＤプロセッサ数であるＭ個の曲線を曲線入力手段１０１に再入力することができる。さらに続けて残りのＭ個の曲線も曲線処理手段１０３の実行状態を待たずに曲線入力手段１０１に別のタスクとして再入力することができる。すなわち、水平方向分割では、図８の８０１のように、同じ分割回数の曲線間には依存関係がないため、異なる入力タスクとして曲線処理手段１０３の完了を待つことなく並列に曲線再帰分割を行うことができる。水平方向分割を行うときの曲線出力領域の管理はＦＩＦＯ（Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）で実現するのが望ましい。
【００２８】
これに対し、垂直方向分割とは、図８における８０２のように、１つの曲線に対して曲線分割を行い、分割結果である２つの出力曲線のうちどちらか一方の曲線に対してさらに曲線分割を行い、もう一方の曲線は片側の曲線を完全に直線近似し終わるまで曲線分割処理を行わずスタックメモリに保持しておくものである。すなわち、垂直方向分割では、一方の曲線を曲線入力手段１０１に再入力し曲線分割処理１０３が曲線出力領域１０４にさらに分割された２曲線を出力するのを確認した後でないと、もう一方の曲線を曲線入力手段１０１へ入力することができない。１つの曲線を深さ方向に分割していくため、常に入力対象の曲線と、出力され再入力される曲線とで依存関係が発生してしまう。垂直方向分割の利点として、ＳＩＭＤプロセッサの並列性は生かせないが、曲線出力領域に必要なメモリ容量を低減することができる。
【００２９】
分割方向切替手段１０６は、水平方向分割を行うと判断した場合には、曲線出力領域に出力された（Ｆｉｒｓｔ Ｉｎ）曲線のうち、最初に出力された曲線から順にリード（Ｆｉｒｓｔ Ｏｕｔ）する。そして、プロセッサ個数の曲線を１つの入力タスク単位として曲線入力手段１０１に再入力する。ただし、Ｍが大きくなるにつれ、従来課題でも述べたように、保持しておくのに必要な曲線出力領域が大きくなり、省メモリ組み込みシステムで実現するのは困難である。
【００３０】
分割方向切替手段１０６は、垂直方向分割を行うと判断した場合には、垂直方向分割を行うときの曲線出力領域の管理を行う。そして、この管理は、スタックメモリで実現できる。分割の深さが増加するたびに２つの曲線分の領域を使用する。そして、そのうち１つの曲線を曲線入力手段１０１に再入力し、もう１つの曲線の情報をスタックメモリに保持しておく。スタックしておく曲線の情報は格納されている曲線出力領域のアドレス、あるいは曲線データそのものなど、特に制限するものではない。垂直方向分割では、曲線出力領域に曲線が出力されない場合、すなわち当該曲線がすべて近似曲線と判断された場合には、当該曲線の再分割は行わず、スタックメモリに保持している曲線があればそれを取り出して、曲線入力手段１０１に再入力する。これをスタックが空になるまで行えば曲線を直線近似することができる。
【００３１】
本特許のポイントは、水平方向分割と垂直方向分割とを動的に切り替えることができる点である。水平方向分割を行うか垂直方向分割を行うかの判断基準は、曲線出力領域に一定以上の空きサイズがあるかを基準としてもかまわない。すなわち、もし曲線出力領域の空きサイズがＱ個分の曲線しかないにもかかわらず、水平方向分割による最大曲線出力数がＱを超えてしまう場合には、垂直方向分割に切り替える。例として図９、図１０を用いる。
【００３２】
図９、図１０は、ＳＩＭＤプロセッサが４個の場合の、入力曲線データの処理の流れを示した図である。例えば図９のように、曲線１２〜１５を４つのＳＩＭＤプロセッサで処理させるためには、曲線出力領域９０２の空きサイズは曲線８個分以上の空きサイズが必要である。しかし、曲線出力領域９０２の空きサイズが足りない場合には、垂直方向分割によるスタック処理に切り替え、空き領域をスタック管理に置き換える。逆に、図１０のように、曲線出力領域１００２に空きサイズが十分あれば、曲線１２〜１５を、曲線分割処理に入力することができる。曲線８〜１１の分割処理完了を待たずに曲線分割処理に入力することができるので、高い並列性を活かすことができる。
【００３３】
水平方向分割に必要な曲線出力領域のメモリ容量は、分割の深さＮまでを行う場合には、最大２のＮ乗個分の曲線を保持できる容量である。垂直方向分割に必要なメモリ容量は、２×Ｎ＋Ｎ個分の曲線を保持できる容量である。ここでいう水平方向分割における必要容量は、分割の深さＮまで分割しても、それらのすべての曲線が直線近似できていないと判断された場合の最悪ケースである。曲線の一部が直線近似されていると判断される場合には、そのときの出力は直線出力領域に出力され、曲線出力領域には出力されない。そのため、分割の最大の深さがＮであっても、実際には２のＮ乗個分の曲線が曲線出力領域に出力されるわけではない。したがって、空き領域（２のＮ乗からそれまでに出力された直線数×２）が生じる。その空き領域を有効利用することにより、深さＮよりも細かい（深い）分割のときに水平方向分割が可能となる。少なくとも１つのプロセッサに割り付けられた曲線処理手段１０３が直線近似と判断された場合、曲線出力領域の空き領域に余裕が生まれ、水平方向分割が選択されやすくなる。
【００３４】
図１１は、曲線出力領域の空き領域のサイズに応じて水平方向分割を行うか、垂直方向分割を行うかを決定するためのフローチャートを示した図である。分割方向切替手段１０６は、曲線処理手段で再分割が必要と判断された場合に、１１０１で分割した２曲線を曲線出力領域に出力する。ここで、曲線出力領域は、図１２のように管理しておく。曲線出力先アドレス１２０１は、曲線処理手段で再分割が必要だと判断された場合に、曲線を出力する曲線出力領域内のアドレスであり、出力のたびに更新される（図１１のフローチャートにおける１１０２で更新する）。
【００３５】
再投入済アドレス１２０２は、入力処理手段に再投入される曲線が記憶されている曲線出力領域内のアドレスであり、曲線入力手段に入力されるたびに更新される（図１１のフローチャートにおける１１１０、１１１３で更新する）。曲線出力先アドレスと再投入済アドレスの差に存在する領域は、未処理の曲線領域１２０３ということになる。そして、曲線出力領域全体から、未処理の曲線領域１２０３を引いた領域が空き領域１２０４である。
【００３６】
曲線処理手段の１１０２で曲線出力先アドレスを更新し、１回目の分割が終了したら分割方向切替手段は終了信号を受信し（１１０３）、空き領域サイズを前述のように計算する（１１０４）。曲線処理手段が処理していた曲線の分割回数（深さ）をＭ、スタック処理で必要な領域をＳとすると、空き領域サイズが２の（Ｍ＋１）乗＋Ｓ以下であれば垂直方向分割に切り替え、そうでなければ水平方向分割に切り替える（１１０５、１１０６、１１１１）。
【００３７】
垂直方向分割に切り替えた場合に曲線出力領域に未処理曲線があれば曲線入力手段に曲線の１つを再投入し、他の未処理曲線をすべてスタックに保持する（１１０８）。未処理曲線がなければスタックに積まれている１曲線を取得し、曲線入力手段に再投入する（１１０９）。
【００３８】
水平方向分割に切り替えた場合には、プロセッサ数の曲線を曲線入力手段に再投入する（１１１１）。未処理曲線の数がプロセッサ数以下であれば、未処理曲線の数だけ曲線入力手段に再投入する。再投入してもまだ未処理曲線が残っているあいだは、曲線処理手段の実行状態に依存せずに曲線入力手段に再投入する（１１１４）。
【００３９】
なお、水平方向分割を行うか垂直方向分割を行うかの判断は、曲線出力領域に出力されている曲線の分割深さを基準としてもかまわない。すなわち、曲線出力領域に出力された曲線分割の深さが閾値以上であれば、それ以上の分割は垂直方向分割に切り替える。この場合、分割方向切替手段１０６が水平方向分割に切り替えたときに曲線出力領域に曲線がなければ、はじめの曲線は直線に近似されたものとして曲線近似直線の生成を終了する。そして、分割方向切替手段１０６が垂直方向分割に切り替えたときに曲線出力領域に曲線が存在するときは、右側曲線をスタックメモリに積み、左側曲線を曲線入力手段１０１に再入力する。さらに、直線出力領域にだけ近似直線が出力されているときは、スタックメモリに積まれた曲線を取り出し曲線入力手段１０１に再入力する。さらに、そして、スタックメモリが空になったら曲線近似直線の生成を終了する。分割方向切替手段１０６は、再分割するべき複数の曲線を曲線入力手段１０１へ転送し、曲線近似直線の生成を終了するまで再帰的に行う。
【００４０】
なお、曲線入力手段、ＳＩＭＤプロセッサ、分割方向切替手段などの各機能ブロックは、典型的には集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されてもよいし、一部またはすべてを含むように１チップ化されても良い。ここではＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。
【００４１】
また、集積回路化の手法はＬＳＩに限るものではなく、専用回路または汎用プロセサで実現しても良い。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサーを利用しても良い。
【００４２】
さらには、半導体技術の進歩または派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行っても良い。バイオ技術の適応などが可能性としてありうる。
【産業上の利用可能性】
【００４３】
本発明にかかる曲線分割装置は、図１において、各プロセッサが入力タスクを時分割処理するＳＩＭＤプロセッサシステムにおいて、Ｎ個の曲線を構成する点と評価値をＮ個のＳＩＭＤプロセッサに入力する曲線入力手段と、評価値をもとに曲線分割処理を行うか近似直線出力処理を行うかを判断し、曲線分割処理を行う場合には左側曲線と右側曲線の２つの曲線に分割し２曲線を構成する点と評価値を曲線出力領域に出力し、近似直線出力処理を行う場合には入力曲線を構成する点から求めた直線を直線出力領域に出力する曲線処理手段と、入力タスクに割り当てられた曲線処理手段の実行制御を行い、処理終了時に終了信号を発行するＳＩＭＤプロセッサと、ＳＩＭＤプロセッサから終了信号を受けたときに、曲線出力領域に曲線が存在する場合曲線処理手段の実行状態に依存せずに曲線出力領域に出力されている曲線を曲線入力手段に再入力する水平方向分割と、曲線出力領域に曲線が存在する場合でもＳＩＭＤプロセッサからの終了信号を待ち新たに出力された曲線を優先してＮ＝１として曲線入力手段に再入力する垂直方向分割とを動的に切り替える分割方向切替手段とを具備し、はじめに設定された１個のベジェ曲線を構成する点と評価値に対して再帰的に行うことで所望の曲線近似直線を生成するので、省メモリかつ並列性を活かした、美麗な曲線描画を実現することができ、ＳＩＭＤプロセッサシステム構成を持つ携帯電話やテレビといった組み込み機器上でのアウトラインフォント表示方式として有用である。
【図面の簡単な説明】
【００４４】
【図１】本発明の実施の形態による曲線分割装置の構成を示すブロック図
【図２】曲線分割方法のうち、ベジェ曲線のパラメータを用いて分割可能であることを説明する図
【図３】曲線分割方法のうち、ベジェ曲線を再帰的に分割可能であることを説明する図
【図４】従来の曲線分割装置における構成の一例を示す図
【図５】従来の曲線分割装置の曲線分割の処理順序を示す図
【図６】ＳＩＭＤプロセッサによる曲線分割装置の曲線分割の処理順序を示す図
【図７】本発明の実施の形態による曲線分割装置における曲線処理手段を説明する図
【図８】本発明の実施の形態による曲線分割装置における水平分割処理と垂直分割処理の判断方法の一例を示す図
【図９】本発明の実施の形態による曲線分割装置における分割方向切替手段の一例を説明する図
【図１０】本発明の実施の形態による曲線分割装置における分割方向切替手段の一例を説明する図
【図１１】本発明の実施の形態による曲線分割装置における分割方向切替手段の一例のフローチャート
【図１２】本発明の実施の形態による曲線分割装置における分割方向切替手段の一例を実現するための曲線出力領域を説明する図
【符号の説明】
【００４５】
１０１ 曲線入力手段
１０２ 複数のＳＩＭＤプロセッサ
１０３ 曲線処理手段
１０４ 曲線出力領域
１０５ 直線出力領域
１０６ 分割方向切替手段
３０１ 最初の２次ベジェ曲線の始点
３０２ 最初の２次ベジェ曲線の制御点
３０３ 最初の２次ベジェ曲線の終点
３０４，３０５ 分割１回目で生成された２次ベジェ曲線の制御点
３０６ 分割１回目で生成された２次ベジェ曲線が通る点
３０７，３０８，３１０，３１１ 分割２回目で生成された２次ベジェ曲線の制御点
３０９，３１２ 分割２回目で生成された２次ベジェ曲線が通る点
４０１ 第１のレジスタ
４０２ ２分割回路
４０３ 第２のレジスタ
４０４ スタックメモリ
４０５ 第３のレジスタ
４０６ 判定回路
７０１ ２次ベジェ曲線の始点
７０２ ２次ベジェ曲線の制御点
７０３ ２次ベジェ曲線の終点
７０４，７０５，７０６ ２次ベジェ曲線の再帰的分割で必要な点
７０７ ３次ベジェ曲線の始点
７０８，７０９ ３次ベジェ曲線の制御点
７１０ ３次ベジェ曲線の終点
７１１〜７１６ ３次ベジェ曲線の再帰的分割で必要な点
８０１ 水平分割処理が行われるときの曲線・直線出力の様子
８０２ 垂直分割処理が行われるときの曲線・直線出力の様子
９０１ 曲線入力手段による入力データ
９０２ 曲線出力領域
１００１ 曲線入力手段による入力データ
１００２ 曲線出力領域
１１０１〜１１１４ フローチャートのブロック
１２０１ 曲線出力先アドレス
１２０２ 再投入済アドレス
１２０３ 未処理の曲線領域
１２０４ 曲線出力領域の空き領域
【技術分野】
【０００１】
本発明は、アウトラインフォントなどのベクターデータに含まれるベジェ曲線を直線に近似する曲線分割方法に関するもので、ＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ Ｍｕｔｌｉｐｌｅ Ｄａｔａ）プロセッサを用いて入力された曲線分割タスクを時分割で行う際に並列性を生かした直線近似を行う曲線分割装置、曲線分割方法、曲線分割プログラム、曲線分割プログラムを記録した記録媒体、曲線分割集積回路に関するものである。
【背景技術】
【０００２】
コンピュータグラフィックスにおいて、アウトラインフォントなどのベクターコンテンツを表示するには曲線描画機能が必須である。従来の組み込み機器ではあらかじめ作成した固定サイズのビットマップを並べて表示していた文字表示機能が、今日のＣＰＵやグラフィックＬＳＩの進化に伴いアウトラインフォントから任意のサイズのフォントビットマップをリアルタイムに作成できるようになっている。アウトラインフォントは、文字の形状を、基準となる点の座標と輪郭線の集まりとして表現する形式であり、フォントの形状を定義するグリフデータを含んでいる。グリフデータは、２次元の「点座標列」と、点列をどのように結んでいくかを定義する「コマンド」から構成される。フォントの描画とは、グリフデータをラスタ化することである。ラスタ化とは、直線や曲線を表す数値データであるベクターデータをビットマップに変換する処理である。
【０００３】
ここで、アウトラインフォントの代表例であるＴｒｕｅＴｙｐｅフォントでは、「コマンド」の代わりに、輪郭線上の点であるのか、輪郭線を構成する曲線の制御点であるのかを示すビットが各点に付加されており、それぞれ直線と２次ベジェ曲線に代替できる。すなわち、フォント形状上の点であれば「直線」として解釈し、フォント形状上の点でなければ当該点は「２次ベジェ曲線」として解釈できる。よって、フォントを描画するには、直線と２次ベジェ曲線のラスタライズを行えばよい。ラスタライズとは、コンピュータが扱う文字や画像を、プリンタで印刷したりディスプレイに表示できるように、色付きの小さな点の集まりで表現することである。ここで、２次ベジェ曲線をラスタライズする一つの方法として、曲線コマンドを複数の直線に近似し、すべてのコマンドを直線で処理する方法がある。
【０００４】
ここで、ベジェ曲線について説明する。２次ベジェ曲線は３点Ｐ０、Ｐ１、Ｐ２から構成され、パラメータｔを用いたパラメトリック曲線として数式１のように表現できる。また、３次ベジェ曲線は４点Ｐ０、Ｐ１、Ｐ２、Ｐ３から構成され、同様に数式２のように表現できる。
【０００５】
【数１】
【０００６】
【数２】
【０００７】
曲線コマンドを複数の直線で近似するには図２のようにベジェ曲線のパラメータｔに０．０から１．０の値を等間隔で入れて曲線上の点を求めていくことができる。しかし、曲率によっては、ほぼ直線にもかかわらず過度な分割が行われる。さらに、曲率が大きい場合には逆に分割が少なく、がたつきが生じるという課題が発生する。図２では、ｔを０．１間隔でずらしていく様子を表したものだが、ｔ＝０．７〜ｔ＝１．０のような曲率が小さいにもかかわらず分割されてしまう現象が発生する。このような課題を解決する方式として、ベジェ曲線の特徴を利用した再帰的曲線分割方式がある。図３のような２次ベジェ曲線を用いて説明する。ベジェ曲線には、ベジェ曲線を構成する点３０１、３０２、３０３の点３０１と３０２を結ぶ線分の中点３０４、点３０２と３０３を結ぶ線分の中点３０５、点３０４と３０５を結ぶ線分の中点３０６を用いて、２つのベジェ曲線３０１、３０４、３０６（左側ベジェ曲線）と３０６、３０５、３０３（右側ベジェ曲線）に分割することができるという特徴がある。さらに左側ベジェ曲線３０１、３０４、３０６は、２つのベジェ曲線３０１、３０７、３０９と３０９、３０８、３０６に、右側ベジェ曲線３０６、３０５、３０３は、２つのベジェ曲線３０６、３１０、３１２と３１２、３１１、３０３に分割できる。このように分割回数を増やし深さ方向に再帰的に分割を行い、ある段階まで分割したら構成点を直線で結んでいけば直線に近似した曲線を描画することができる。再帰的に分割するか否かの判定は１回の分割毎に行われ、曲線の曲率に応じて判断される。したがって、直線に近い部分は殆ど分割されず、曲率が大きい部分は細かく分割されるので、描画結果として滑らかな曲線描画を実現できる。
【０００８】
このような従来の再帰的曲線分割方式を使用した例として、スタックメモリを用いて逐次的に再帰的曲線分割を行う曲線分割装置があった（例えば、特許文献１参照）。図４は特許文献１に記載された従来の曲線分割装置の構成の一例を示すブロック図である。
【０００９】
図４において、曲線の制御点の各座標値を格納する第１のレジスタ４０１と、レジスタで保持されている制御点を２分割し、２組の曲線の各制御点を形成する２分割回路４０２と、２分割回路によって生成された２組の曲線の各制御点を格納する第２のレジスタ４０３と、複数組の各制御点を順次格納するスタックメモリ４０４と、第１、第２のレジスタとスタックメモリとの間に位置し、１組の各制御点を格納する第３のレジスタ４０５と、第２のレジスタで格納される制御点に基づき、２分割回路で制御点の２分割を行わせるか否かを決定する判定回路４０６とを備えている。
【特許文献１】特開平８−３２９２６１号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、上記従来の構成を、入力タスクを時分割で処理できるＳＩＭＤプロセッサシステムに適用した場合、スタックメモリを用いた逐次処理を行うことになりマルチプロセッサの利点をまったく得ることができない。図５における点線は、スタックメモリを用いた逐次処理を行った場合の処理の流れである。曲線の上下関係は、それぞれの依存関係を示している。図５のように、曲線の分割は深さ方向に行われる。そして、従来例のような再帰的分割は、一つ前に分割された曲線を使う。そのため、再帰的分割でＳＩＭＤプロセッサの並列性を活かすのは難しい。さらに、同様の理由で、入力データを異なるタスクに割り付ける時分割処理も難しい（一つ前に分割された曲線をさらに細かい２つの曲線に分割している）。
【００１１】
そこで、再帰的分割処理を複数のＳＩＭＤプロセッサで並列に動作させようとした場合は、図６のように動作させるのが好ましい。そうすると、１つの曲線が２つの曲線に同時に分割され、２つの曲線は４つの曲線に同時に分割され、・・・・Ｎ個の曲線は２×Ｎ個の曲線に・・・・と、並列処理が可能になる。なお、図６に記載の番号は、実行順序を示している。そして、さらに依存関係のない曲線データを異なるタスクに割り付ける時分割処理が可能になる。しかしながら、上記方法の場合、曲線が十分直線に近似されていると判断されるまで分割した曲線を保持しておかなければならず、メモリが増大してしまうという課題が新たに発生してしまう。
【００１２】
本発明は、上記従来の課題を解決するもので、ＳＩＭＤプロセッサの利点である並列性を活かしながらも、少ないメモリで滑らかな直線近似を実現する曲線分割装置を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記従来の課題を解決するために、本発明の曲線分割装置は、各プロセッサが入力タスクを時分割処理するＳＩＭＤプロセッサシステムにおいて、Ｎ個の曲線を構成する点と評価値をＮ個のＳＩＭＤプロセッサに入力する曲線入力手段と、前記評価値をもとに曲線分割処理を行うか近似直線出力処理を行うかを判断し、曲線分割処理を行う場合には左側曲線と右側曲線の２つの曲線に分割し２曲線を構成する点と評価値を曲線出力領域に出力し、近似直線出力処理を行う場合には入力曲線を構成する点から求めた直線を直線出力領域に出力する曲線処理手段と、入力タスクに割り当てられた前記曲線処理手段の実行制御を行い、処理終了時に終了信号を発行する前記ＳＩＭＤプロセッサと、前記ＳＩＭＤプロセッサから終了信号を受けたときに、前記曲線出力領域に曲線が存在する場合前記曲線処理手段の実行状態に依存せずに前記曲線出力領域の曲線を前記曲線入力手段に再入力する水平方向分割と、前記曲線出力領域に曲線が存在する場合でも前記ＳＩＭＤプロセッサからの終了信号を待ち新たに出力された曲線を優先してＮ＝１として前記曲線入力手段に再入力する垂直方向分割とを動的に切り替える分割方向切替手段とを具備し、はじめに設定された１個の曲線を構成する点と評価値に対して再帰的に行うことで所望の曲線近似直線を生成するので、ＳＩＭＤプロセッサの利点である並列性を活かしながらも、少ないメモリ容量で滑らかな直線近似を実現することができる。
【発明の効果】
【００１４】
本発明によれば、入力曲線に対しての曲線分割を終えて再分割の必要がある場合に、並列性を生かし他の曲線分割処理の完了を待たずにすでに分割済みの曲線を順に曲線入力手段に再入力する水平方向分割と、曲線分割処理の完了を待って新たに出力された曲線を優先して曲線入力手段に再入力する垂直方向分割とを動的に切り替える分割方向切替手段を設けることで、ＳＩＭＤプロセッサの利点である並列性を活かしながらも、少ないメモリ容量で滑らかな直線近似を実現することができる。
【発明を実施するための最良の形態】
【００１５】
以下本発明の実施の形態について、図面を参照しながら説明する。
【００１６】
（実施の形態１）
図１は、本発明の実施の形態１における曲線分割装置の構成を示すブロック図である。曲線分割装置は、曲線入力手段１０１と、ＳＩＭＤプロセッサ１０２と、曲線処理手段１０３と、曲線出力領域１０４と、直線出力領域１０５と、分割方向切替手段１０６と、で構成される。
【００１７】
曲線入力手段１０１は、Ｎ個の曲線を構成する点と評価値とを、それぞれＮ個のＳＩＭＤプロセッサ１０２に入力する。Ｎ個の曲線を構成する点とは、例えば、２次ベジェ曲線の場合には、図７に示すように、７０１、７０２、７０３を表す点である。また、３次ベジェの場合には、図７に示すように、７０７、７０８、７０９、７１０を表す点である。そして、Ｎ個の曲線を構成する点は、少なくとも始点と終点、そして曲率を制御する制御点で構成される。さらに、点の位置は２次元座標で表現できる。
【００１８】
評価値とは、入力された曲線がすでに十分直線に近似できているかを判断するための値である。評価値は、曲線処理手段１０３内で１つの曲線を２つの曲線に分割するときに計算される。評価値を計算するための評価式は本特許では特に限定しないが、点の位置座標に依存したものが望ましい。たとえば評価式の一例としては、点のうち曲線の始点と終点を示す座標値Ｓ（ＳＸ、ＳＹ）、Ｅ（ＥＸ、ＥＹ）の各座標成分の差分の絶対値の和（｜ＳＸ−ＥＸ｜＋｜ＳＹ−ＥＹ｜）としたものが挙げられる。また、評価式は、曲線を囲むようなバウンダリ領域の大きさを評価式としてもかまわない。さらに、分割対象となる曲線をはじめに入力するときに、あえて必ず再分割されるような評価値を初期値として設定しておいてもかまわない。また、Ｎの最大値はＳＩＭＤプロセッサの個数であり、分割方向切替手段１０６で決まる水平方向分割と垂直方向分割により切り替わる。分割対象となる曲線をはじめに入力するときはＮ＝１で行う。
【００１９】
そして、曲線入力手段１０１は、曲線を構成する点と評価値を各ＳＩＭＤプロセッサ１０２に転送する。
【００２０】
ＳＩＭＤプロセッサ１０２は、複数のＳＩＭＤプロセッサから構成される。各ＳＩＭＤプロセッサは、曲線入力手段から転送された曲線を構成する点と評価値を受け取り、曲線処理手段１０３の処理プログラムの入力データとして投入したのち、曲線処理手段１０３の処理プログラム（再分割判定及び分割曲線出力、又は再分割判定及び近似直線出力）を実行制御し、曲線処理手段１０３の終了時に分割方向切替手段１０６に終了信号を発行する。各ＳＩＭＤプロセッサは、異なる入力曲線に対して、曲線処理手段１０３による処理を行う。さらに、ＳＩＭＤプロセッサは、入力タスクを時分割で処理する特徴を持つ。すなわち、プロセッサごとに異なる入力データを同じ処理プログラムで処理することが可能であるとともに（ＳＩＭＤプロセッサの特徴）、各プロセッサにおいても異なる入力データ（別の入力タスク）を時分割で処理することが可能である（入力タスクの時分割処理）。ＳＩＭＤプロセッサなので、ある入力タスクに対しての曲線処理手段１０３の処理は同時に終了する。
【００２１】
曲線処理手段１０３は、評価値と判定のための閾値と比較し、入力された曲線が、十分に直線近似されているかどうかを判断する。入力された曲線が直線近似されていると判断したら、入力曲線を近似直線と見立てて直線出力領域１０５に出力する。入力された曲線が直線近似されていないと判断したら、再分割が必要だと判断し、曲線分割を行う。そして、曲線分割によって生成された２曲線を曲線出力領域１０４に出力する。曲線処理手段１０３は、典型的にはＳＩＭＤプロセッサ１０２上で動作するプログラムとして実現される。
【００２２】
各ＳＩＭＤプロセッサは、入力曲線の点と評価値に対して前述のような曲線処理を行うことになり、結果としてプロセッサごとに直線出力を行うか、曲線分割して曲線出力を行うかが異なる可能性がある。ある曲線に対して十分直線に近似できていると判断した場合、入力曲線の点をもとに近似直線を作り直線出力領域１０５へ出力する。どのような直線を生成するかは具体的には限定しないが、曲線を構成する点を通るような直線であることが望ましい。例えば始点と終点を結んだ線分を出力してもかまわない。また、入力曲線のうちすべての点を結んだ複数の線分を出力してもかまわない。
【００２３】
上記曲線分割は、１つの曲線を２つに分割する再帰分割処理で行われる。再帰分割処理は、分割後でも同じ特徴を持つ曲線に分割する処理である。再帰分割処理される曲線は、分割後でも同じ特徴を持つ曲線である。ベジェ曲線などは代表的な再帰分割可能な曲線の一つである。図７のように、１つの２次ベジェ曲線７０１、７０２、７０３は、７０１と７０２の中点である７０４、７０２と７０３の中点である７０５を結ぶ線分７０４、７０５のさらに中点７０６を用いて、２つの２次ベジェ曲線７０１、７０４、７０６と７０６、７０５、７０３に分割することができる。また、１つの３次ベジェ曲線７０７、７０８、７０９、７１０も同様に、７０７と７０８の中点である７１１、７０８と７０９の中点である７１２、７０９と７１０の中点である７１３、７１１と７１２の中点である７１４、７１２と７１３の中点である７１５、７１４と７１５の中点である７１６を用いて、２つの３次ベジェ曲線７０７、７１１、７１４、７１６と７１６、７１５、７１３、７１０に分割することができる。分割されたベジェ曲線の点を用いて、それぞれ新たに評価式を適用し評価値を計算しベジェ曲線を構成する点とともに曲線出力領域１０４に出力する。
【００２４】
曲線出力領域１０４は、曲線処理手段１０３でまだ十分に直線に近似されていないと判断し出力された曲線を格納する。ＳＩＭＤプロセッサからアクセス可能なメモリであれば、レジスタファイルで構成されていてもよいし、ＳＲＡＭのような容量の大きいメモリで構成されていても良い。曲線出力領域１０４に出力された曲線は、直線近似のために曲線入力手段１０１で再入力されさらなる曲線分割処理が行われる。
【００２５】
直線出力領域１０５は、曲線処理手段１０３で入力された曲線が直線近似されていると判断された場合に、上記近似直線を格納する。一例として、上記近似直線は、近似直線の開始点座標と終了点座標、及び直線の傾き値と切片値の組として保持する。ＳＩＭＤプロセッサからアクセス可能なメモリであれば、レジスタファイルで構成されていてもよいしＳＲＡＭのような容量の大きいメモリで構成されていても良い。直線出力領域１０５に出力された直線は、十分近似できているものとして扱われ、例えば線を描画するラスタライザで処理される。
【００２６】
分割方向切替手段１０６は、曲線入力手段１０１に再入力する水平方向分割と、曲線入力手段１０１に再入力する垂直方向分割と、を動的に切り替えるものである。
【００２７】
水平方向分割とは、再分割すべき１つ以上の曲線を同時に曲線入力手段１０１に再入力するモードである。例えばＭ個（ＭはＳＩＭＤプロセッサ数）のベジェ曲線を曲線入力手段１０１に同時に入力し、曲線処理手段１０３がすべて再分割必要と判断した場合、２×Ｍ個の曲線が同時に曲線出力領域に出力されることになる。しかし、同時出力された２×Ｍ個の曲線は、すべて分割の深さ（分割回数）が同じであるため、これらの曲線間には依存関係は発生しない。そのため、曲線出力領域に出力された２×Ｍ個の曲線のうち、ＳＩＭＤプロセッサ数であるＭ個の曲線を曲線入力手段１０１に再入力することができる。さらに続けて残りのＭ個の曲線も曲線処理手段１０３の実行状態を待たずに曲線入力手段１０１に別のタスクとして再入力することができる。すなわち、水平方向分割では、図８の８０１のように、同じ分割回数の曲線間には依存関係がないため、異なる入力タスクとして曲線処理手段１０３の完了を待つことなく並列に曲線再帰分割を行うことができる。水平方向分割を行うときの曲線出力領域の管理はＦＩＦＯ（Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）で実現するのが望ましい。
【００２８】
これに対し、垂直方向分割とは、図８における８０２のように、１つの曲線に対して曲線分割を行い、分割結果である２つの出力曲線のうちどちらか一方の曲線に対してさらに曲線分割を行い、もう一方の曲線は片側の曲線を完全に直線近似し終わるまで曲線分割処理を行わずスタックメモリに保持しておくものである。すなわち、垂直方向分割では、一方の曲線を曲線入力手段１０１に再入力し曲線分割処理１０３が曲線出力領域１０４にさらに分割された２曲線を出力するのを確認した後でないと、もう一方の曲線を曲線入力手段１０１へ入力することができない。１つの曲線を深さ方向に分割していくため、常に入力対象の曲線と、出力され再入力される曲線とで依存関係が発生してしまう。垂直方向分割の利点として、ＳＩＭＤプロセッサの並列性は生かせないが、曲線出力領域に必要なメモリ容量を低減することができる。
【００２９】
分割方向切替手段１０６は、水平方向分割を行うと判断した場合には、曲線出力領域に出力された（Ｆｉｒｓｔ Ｉｎ）曲線のうち、最初に出力された曲線から順にリード（Ｆｉｒｓｔ Ｏｕｔ）する。そして、プロセッサ個数の曲線を１つの入力タスク単位として曲線入力手段１０１に再入力する。ただし、Ｍが大きくなるにつれ、従来課題でも述べたように、保持しておくのに必要な曲線出力領域が大きくなり、省メモリ組み込みシステムで実現するのは困難である。
【００３０】
分割方向切替手段１０６は、垂直方向分割を行うと判断した場合には、垂直方向分割を行うときの曲線出力領域の管理を行う。そして、この管理は、スタックメモリで実現できる。分割の深さが増加するたびに２つの曲線分の領域を使用する。そして、そのうち１つの曲線を曲線入力手段１０１に再入力し、もう１つの曲線の情報をスタックメモリに保持しておく。スタックしておく曲線の情報は格納されている曲線出力領域のアドレス、あるいは曲線データそのものなど、特に制限するものではない。垂直方向分割では、曲線出力領域に曲線が出力されない場合、すなわち当該曲線がすべて近似曲線と判断された場合には、当該曲線の再分割は行わず、スタックメモリに保持している曲線があればそれを取り出して、曲線入力手段１０１に再入力する。これをスタックが空になるまで行えば曲線を直線近似することができる。
【００３１】
本特許のポイントは、水平方向分割と垂直方向分割とを動的に切り替えることができる点である。水平方向分割を行うか垂直方向分割を行うかの判断基準は、曲線出力領域に一定以上の空きサイズがあるかを基準としてもかまわない。すなわち、もし曲線出力領域の空きサイズがＱ個分の曲線しかないにもかかわらず、水平方向分割による最大曲線出力数がＱを超えてしまう場合には、垂直方向分割に切り替える。例として図９、図１０を用いる。
【００３２】
図９、図１０は、ＳＩＭＤプロセッサが４個の場合の、入力曲線データの処理の流れを示した図である。例えば図９のように、曲線１２〜１５を４つのＳＩＭＤプロセッサで処理させるためには、曲線出力領域９０２の空きサイズは曲線８個分以上の空きサイズが必要である。しかし、曲線出力領域９０２の空きサイズが足りない場合には、垂直方向分割によるスタック処理に切り替え、空き領域をスタック管理に置き換える。逆に、図１０のように、曲線出力領域１００２に空きサイズが十分あれば、曲線１２〜１５を、曲線分割処理に入力することができる。曲線８〜１１の分割処理完了を待たずに曲線分割処理に入力することができるので、高い並列性を活かすことができる。
【００３３】
水平方向分割に必要な曲線出力領域のメモリ容量は、分割の深さＮまでを行う場合には、最大２のＮ乗個分の曲線を保持できる容量である。垂直方向分割に必要なメモリ容量は、２×Ｎ＋Ｎ個分の曲線を保持できる容量である。ここでいう水平方向分割における必要容量は、分割の深さＮまで分割しても、それらのすべての曲線が直線近似できていないと判断された場合の最悪ケースである。曲線の一部が直線近似されていると判断される場合には、そのときの出力は直線出力領域に出力され、曲線出力領域には出力されない。そのため、分割の最大の深さがＮであっても、実際には２のＮ乗個分の曲線が曲線出力領域に出力されるわけではない。したがって、空き領域（２のＮ乗からそれまでに出力された直線数×２）が生じる。その空き領域を有効利用することにより、深さＮよりも細かい（深い）分割のときに水平方向分割が可能となる。少なくとも１つのプロセッサに割り付けられた曲線処理手段１０３が直線近似と判断された場合、曲線出力領域の空き領域に余裕が生まれ、水平方向分割が選択されやすくなる。
【００３４】
図１１は、曲線出力領域の空き領域のサイズに応じて水平方向分割を行うか、垂直方向分割を行うかを決定するためのフローチャートを示した図である。分割方向切替手段１０６は、曲線処理手段で再分割が必要と判断された場合に、１１０１で分割した２曲線を曲線出力領域に出力する。ここで、曲線出力領域は、図１２のように管理しておく。曲線出力先アドレス１２０１は、曲線処理手段で再分割が必要だと判断された場合に、曲線を出力する曲線出力領域内のアドレスであり、出力のたびに更新される（図１１のフローチャートにおける１１０２で更新する）。
【００３５】
再投入済アドレス１２０２は、入力処理手段に再投入される曲線が記憶されている曲線出力領域内のアドレスであり、曲線入力手段に入力されるたびに更新される（図１１のフローチャートにおける１１１０、１１１３で更新する）。曲線出力先アドレスと再投入済アドレスの差に存在する領域は、未処理の曲線領域１２０３ということになる。そして、曲線出力領域全体から、未処理の曲線領域１２０３を引いた領域が空き領域１２０４である。
【００３６】
曲線処理手段の１１０２で曲線出力先アドレスを更新し、１回目の分割が終了したら分割方向切替手段は終了信号を受信し（１１０３）、空き領域サイズを前述のように計算する（１１０４）。曲線処理手段が処理していた曲線の分割回数（深さ）をＭ、スタック処理で必要な領域をＳとすると、空き領域サイズが２の（Ｍ＋１）乗＋Ｓ以下であれば垂直方向分割に切り替え、そうでなければ水平方向分割に切り替える（１１０５、１１０６、１１１１）。
【００３７】
垂直方向分割に切り替えた場合に曲線出力領域に未処理曲線があれば曲線入力手段に曲線の１つを再投入し、他の未処理曲線をすべてスタックに保持する（１１０８）。未処理曲線がなければスタックに積まれている１曲線を取得し、曲線入力手段に再投入する（１１０９）。
【００３８】
水平方向分割に切り替えた場合には、プロセッサ数の曲線を曲線入力手段に再投入する（１１１１）。未処理曲線の数がプロセッサ数以下であれば、未処理曲線の数だけ曲線入力手段に再投入する。再投入してもまだ未処理曲線が残っているあいだは、曲線処理手段の実行状態に依存せずに曲線入力手段に再投入する（１１１４）。
【００３９】
なお、水平方向分割を行うか垂直方向分割を行うかの判断は、曲線出力領域に出力されている曲線の分割深さを基準としてもかまわない。すなわち、曲線出力領域に出力された曲線分割の深さが閾値以上であれば、それ以上の分割は垂直方向分割に切り替える。この場合、分割方向切替手段１０６が水平方向分割に切り替えたときに曲線出力領域に曲線がなければ、はじめの曲線は直線に近似されたものとして曲線近似直線の生成を終了する。そして、分割方向切替手段１０６が垂直方向分割に切り替えたときに曲線出力領域に曲線が存在するときは、右側曲線をスタックメモリに積み、左側曲線を曲線入力手段１０１に再入力する。さらに、直線出力領域にだけ近似直線が出力されているときは、スタックメモリに積まれた曲線を取り出し曲線入力手段１０１に再入力する。さらに、そして、スタックメモリが空になったら曲線近似直線の生成を終了する。分割方向切替手段１０６は、再分割するべき複数の曲線を曲線入力手段１０１へ転送し、曲線近似直線の生成を終了するまで再帰的に行う。
【００４０】
なお、曲線入力手段、ＳＩＭＤプロセッサ、分割方向切替手段などの各機能ブロックは、典型的には集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されてもよいし、一部またはすべてを含むように１チップ化されても良い。ここではＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。
【００４１】
また、集積回路化の手法はＬＳＩに限るものではなく、専用回路または汎用プロセサで実現しても良い。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサーを利用しても良い。
【００４２】
さらには、半導体技術の進歩または派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行っても良い。バイオ技術の適応などが可能性としてありうる。
【産業上の利用可能性】
【００４３】
本発明にかかる曲線分割装置は、図１において、各プロセッサが入力タスクを時分割処理するＳＩＭＤプロセッサシステムにおいて、Ｎ個の曲線を構成する点と評価値をＮ個のＳＩＭＤプロセッサに入力する曲線入力手段と、評価値をもとに曲線分割処理を行うか近似直線出力処理を行うかを判断し、曲線分割処理を行う場合には左側曲線と右側曲線の２つの曲線に分割し２曲線を構成する点と評価値を曲線出力領域に出力し、近似直線出力処理を行う場合には入力曲線を構成する点から求めた直線を直線出力領域に出力する曲線処理手段と、入力タスクに割り当てられた曲線処理手段の実行制御を行い、処理終了時に終了信号を発行するＳＩＭＤプロセッサと、ＳＩＭＤプロセッサから終了信号を受けたときに、曲線出力領域に曲線が存在する場合曲線処理手段の実行状態に依存せずに曲線出力領域に出力されている曲線を曲線入力手段に再入力する水平方向分割と、曲線出力領域に曲線が存在する場合でもＳＩＭＤプロセッサからの終了信号を待ち新たに出力された曲線を優先してＮ＝１として曲線入力手段に再入力する垂直方向分割とを動的に切り替える分割方向切替手段とを具備し、はじめに設定された１個のベジェ曲線を構成する点と評価値に対して再帰的に行うことで所望の曲線近似直線を生成するので、省メモリかつ並列性を活かした、美麗な曲線描画を実現することができ、ＳＩＭＤプロセッサシステム構成を持つ携帯電話やテレビといった組み込み機器上でのアウトラインフォント表示方式として有用である。
【図面の簡単な説明】
【００４４】
【図１】本発明の実施の形態による曲線分割装置の構成を示すブロック図
【図２】曲線分割方法のうち、ベジェ曲線のパラメータを用いて分割可能であることを説明する図
【図３】曲線分割方法のうち、ベジェ曲線を再帰的に分割可能であることを説明する図
【図４】従来の曲線分割装置における構成の一例を示す図
【図５】従来の曲線分割装置の曲線分割の処理順序を示す図
【図６】ＳＩＭＤプロセッサによる曲線分割装置の曲線分割の処理順序を示す図
【図７】本発明の実施の形態による曲線分割装置における曲線処理手段を説明する図
【図８】本発明の実施の形態による曲線分割装置における水平分割処理と垂直分割処理の判断方法の一例を示す図
【図９】本発明の実施の形態による曲線分割装置における分割方向切替手段の一例を説明する図
【図１０】本発明の実施の形態による曲線分割装置における分割方向切替手段の一例を説明する図
【図１１】本発明の実施の形態による曲線分割装置における分割方向切替手段の一例のフローチャート
【図１２】本発明の実施の形態による曲線分割装置における分割方向切替手段の一例を実現するための曲線出力領域を説明する図
【符号の説明】
【００４５】
１０１ 曲線入力手段
１０２ 複数のＳＩＭＤプロセッサ
１０３ 曲線処理手段
１０４ 曲線出力領域
１０５ 直線出力領域
１０６ 分割方向切替手段
３０１ 最初の２次ベジェ曲線の始点
３０２ 最初の２次ベジェ曲線の制御点
３０３ 最初の２次ベジェ曲線の終点
３０４，３０５ 分割１回目で生成された２次ベジェ曲線の制御点
３０６ 分割１回目で生成された２次ベジェ曲線が通る点
３０７，３０８，３１０，３１１ 分割２回目で生成された２次ベジェ曲線の制御点
３０９，３１２ 分割２回目で生成された２次ベジェ曲線が通る点
４０１ 第１のレジスタ
４０２ ２分割回路
４０３ 第２のレジスタ
４０４ スタックメモリ
４０５ 第３のレジスタ
４０６ 判定回路
７０１ ２次ベジェ曲線の始点
７０２ ２次ベジェ曲線の制御点
７０３ ２次ベジェ曲線の終点
７０４，７０５，７０６ ２次ベジェ曲線の再帰的分割で必要な点
７０７ ３次ベジェ曲線の始点
７０８，７０９ ３次ベジェ曲線の制御点
７１０ ３次ベジェ曲線の終点
７１１〜７１６ ３次ベジェ曲線の再帰的分割で必要な点
８０１ 水平分割処理が行われるときの曲線・直線出力の様子
８０２ 垂直分割処理が行われるときの曲線・直線出力の様子
９０１ 曲線入力手段による入力データ
９０２ 曲線出力領域
１００１ 曲線入力手段による入力データ
１００２ 曲線出力領域
１１０１〜１１１４ フローチャートのブロック
１２０１ 曲線出力先アドレス
１２０２ 再投入済アドレス
１２０３ 未処理の曲線領域
１２０４ 曲線出力領域の空き領域
【特許請求の範囲】
【請求項１】
各プロセッサが入力タスクを時分割処理するＳＩＭＤプロセッサシステムにおいて、
Ｎ個の曲線を構成する点と評価値をＮ個のＳＩＭＤプロセッサに入力する曲線入力手段と、
前記評価値をもとに曲線分割処理を行うか近似直線出力処理を行うかを判断し、曲線分割処理を行う場合には左側曲線と右側曲線の２つの曲線に分割し２曲線を構成する点と評価値を曲線出力領域に出力し、近似直線出力処理を行う場合には入力曲線を構成する点から求めた直線を直線出力領域に出力する曲線処理手段と、
入力タスクに割り当てられた前記曲線処理手段の実行制御を行い、処理終了時に終了信号を発行する前記ＳＩＭＤプロセッサと、
前記ＳＩＭＤプロセッサから終了信号を受けたときに、前記曲線出力領域に曲線が存在する場合前記曲線処理手段の実行状態に依存せずに前記曲線出力領域に出力されている曲線を構成する点と評価値を前記曲線入力手段に別の入力タスクとして再入力する水平方向分割と、前記曲線出力領域に曲線が存在する場合でも前記ＳＩＭＤプロセッサからの終了信号を待ち新たに出力された曲線を優先してＮ＝１として前記曲線入力手段に再入力する垂直方向分割とを動的に切り替える分割方向切替手段と、
を具備し、
はじめに設定された１個の曲線を構成する点と評価値に対して再帰的に行うことで所望の曲線近似直線を生成する、
ことを特徴とする曲線分割装置。
【請求項２】
前記曲線は、分割後でも同じ特徴を持つ曲線に分割可能な曲線であることを特徴とする請求項１に記載の曲線分割装置。
【請求項３】
前記曲線は、ベジェ曲線であることを特徴とする、請求項２に記載の曲線分割装置。
【請求項４】
前記Ｎの最大値は、ＳＩＭＤプロセッサシステムにおけるプロセッサ数であり、Ｎが２以上であることを特徴とする請求項１に記載の曲線分割装置。
【請求項５】
前記曲線出力領域は、前記分割方向切替手段により水平方向分割に切り替えた場合はＦＩＦＯ（Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）で構成されている領域であり、垂直方向分割に切り替えた場合にはスタックで構成されている領域であることを特徴とする請求項１に記載の曲線分割装置。
【請求項６】
前記分割方向切替手段は、曲線出力領域の空き領域サイズを判断基準として、空きサイズが閾値以下になった場合に垂直方向分割に切り替え、閾値より大きい場合に水平方向分割に切り替えることを特徴とする請求項１に記載の曲線分割装置。
【請求項７】
前記分割方向切替手段は、曲線の分割回数を判断基準として、曲線の分割回数が閾値以上になった場合に垂直方向分割に切り替え、閾値より小さい場合に水平方向分割に切り替えることを特徴とする請求項１に記載の曲線分割装置。
【請求項８】
前記分割方向切替手段が水平方向分割に切り替えた場合に、曲線出力領域に曲線が存在しないときは曲線近似直線の生成を終了することを特徴とする請求項６又は請求項７に記載の曲線分割装置。
【請求項９】
前記分割方向切替手段が垂直方向分割に切り替えた場合に、曲線出力領域に曲線が存在するときは右側曲線をスタックに積み左側曲線を前記曲線入力手段に再入力し、近似直線出力領域にだけ近似直線が出力されるときは前記スタックに積まれた曲線を取り出し前記曲線入力手段に再入力し、スタックが空になったら曲線近似直線の生成を終了することを特徴とする請求項６又は請求項７に記載の曲線分割装置。
【請求項１０】
前記曲線の評価値は、前記曲線処理手段における曲線分割処理で分割したあとの曲線を構成する点の座標値から計算することを特徴とする請求項１に記載の曲線分割装置。
【請求項１１】
はじめに分割対象となる曲線を処理する際には水平方向分割で処理することを特徴とする請求項１に記載の曲線分割装置。
【請求項１２】
各プロセッサが入力タスクを時分割処理するＳＩＭＤプロセッサシステムを用いた曲線分割装置の集積回路であって、
評価値をもとに曲線分割処理を行うか近似直線出力処理を行うかを判断し、曲線分割処理を行う場合には左側曲線と右側曲線の２つの曲線に分割し２曲線を構成する点と評価値を曲線出力領域に出力し、近似直線出力処理を行う場合には入力曲線を構成する点から求めた直線を直線出力領域に出力する曲線処理手段と、
Ｎ個の曲線を構成する点と評価値をＮ個のＳＩＭＤプロセッサに入力する曲線入力手段と、入力タスクに割り当てられた前記曲線処理手段の実行制御を行い、処理終了時に終了信号を発行する前記ＳＩＭＤプロセッサと、
前記ＳＩＭＤプロセッサから終了信号を受けたときに、前記曲線出力領域に曲線が存在する場合前記曲線処理手段の実行状態に依存せずに前記曲線出力領域の曲線を前記曲線入力手段に別の入力タスクとして再入力する水平方向分割と、前記曲線出力領域に曲線が存在する場合でも前記ＳＩＭＤプロセッサからの終了信号を待ち新たに出力された曲線を優先してＮ＝１として前記曲線入力手段に再入力する垂直方向分割とを動的に切り替える分割方向切替手段と、
を具備し、
はじめに設定された１個の曲線を構成する点と評価値に対して再帰的に行うことで所望の曲線近似直線を生成する、
ことを特徴とする集積回路。
【請求項１】
各プロセッサが入力タスクを時分割処理するＳＩＭＤプロセッサシステムにおいて、
Ｎ個の曲線を構成する点と評価値をＮ個のＳＩＭＤプロセッサに入力する曲線入力手段と、
前記評価値をもとに曲線分割処理を行うか近似直線出力処理を行うかを判断し、曲線分割処理を行う場合には左側曲線と右側曲線の２つの曲線に分割し２曲線を構成する点と評価値を曲線出力領域に出力し、近似直線出力処理を行う場合には入力曲線を構成する点から求めた直線を直線出力領域に出力する曲線処理手段と、
入力タスクに割り当てられた前記曲線処理手段の実行制御を行い、処理終了時に終了信号を発行する前記ＳＩＭＤプロセッサと、
前記ＳＩＭＤプロセッサから終了信号を受けたときに、前記曲線出力領域に曲線が存在する場合前記曲線処理手段の実行状態に依存せずに前記曲線出力領域に出力されている曲線を構成する点と評価値を前記曲線入力手段に別の入力タスクとして再入力する水平方向分割と、前記曲線出力領域に曲線が存在する場合でも前記ＳＩＭＤプロセッサからの終了信号を待ち新たに出力された曲線を優先してＮ＝１として前記曲線入力手段に再入力する垂直方向分割とを動的に切り替える分割方向切替手段と、
を具備し、
はじめに設定された１個の曲線を構成する点と評価値に対して再帰的に行うことで所望の曲線近似直線を生成する、
ことを特徴とする曲線分割装置。
【請求項２】
前記曲線は、分割後でも同じ特徴を持つ曲線に分割可能な曲線であることを特徴とする請求項１に記載の曲線分割装置。
【請求項３】
前記曲線は、ベジェ曲線であることを特徴とする、請求項２に記載の曲線分割装置。
【請求項４】
前記Ｎの最大値は、ＳＩＭＤプロセッサシステムにおけるプロセッサ数であり、Ｎが２以上であることを特徴とする請求項１に記載の曲線分割装置。
【請求項５】
前記曲線出力領域は、前記分割方向切替手段により水平方向分割に切り替えた場合はＦＩＦＯ（Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）で構成されている領域であり、垂直方向分割に切り替えた場合にはスタックで構成されている領域であることを特徴とする請求項１に記載の曲線分割装置。
【請求項６】
前記分割方向切替手段は、曲線出力領域の空き領域サイズを判断基準として、空きサイズが閾値以下になった場合に垂直方向分割に切り替え、閾値より大きい場合に水平方向分割に切り替えることを特徴とする請求項１に記載の曲線分割装置。
【請求項７】
前記分割方向切替手段は、曲線の分割回数を判断基準として、曲線の分割回数が閾値以上になった場合に垂直方向分割に切り替え、閾値より小さい場合に水平方向分割に切り替えることを特徴とする請求項１に記載の曲線分割装置。
【請求項８】
前記分割方向切替手段が水平方向分割に切り替えた場合に、曲線出力領域に曲線が存在しないときは曲線近似直線の生成を終了することを特徴とする請求項６又は請求項７に記載の曲線分割装置。
【請求項９】
前記分割方向切替手段が垂直方向分割に切り替えた場合に、曲線出力領域に曲線が存在するときは右側曲線をスタックに積み左側曲線を前記曲線入力手段に再入力し、近似直線出力領域にだけ近似直線が出力されるときは前記スタックに積まれた曲線を取り出し前記曲線入力手段に再入力し、スタックが空になったら曲線近似直線の生成を終了することを特徴とする請求項６又は請求項７に記載の曲線分割装置。
【請求項１０】
前記曲線の評価値は、前記曲線処理手段における曲線分割処理で分割したあとの曲線を構成する点の座標値から計算することを特徴とする請求項１に記載の曲線分割装置。
【請求項１１】
はじめに分割対象となる曲線を処理する際には水平方向分割で処理することを特徴とする請求項１に記載の曲線分割装置。
【請求項１２】
各プロセッサが入力タスクを時分割処理するＳＩＭＤプロセッサシステムを用いた曲線分割装置の集積回路であって、
評価値をもとに曲線分割処理を行うか近似直線出力処理を行うかを判断し、曲線分割処理を行う場合には左側曲線と右側曲線の２つの曲線に分割し２曲線を構成する点と評価値を曲線出力領域に出力し、近似直線出力処理を行う場合には入力曲線を構成する点から求めた直線を直線出力領域に出力する曲線処理手段と、
Ｎ個の曲線を構成する点と評価値をＮ個のＳＩＭＤプロセッサに入力する曲線入力手段と、入力タスクに割り当てられた前記曲線処理手段の実行制御を行い、処理終了時に終了信号を発行する前記ＳＩＭＤプロセッサと、
前記ＳＩＭＤプロセッサから終了信号を受けたときに、前記曲線出力領域に曲線が存在する場合前記曲線処理手段の実行状態に依存せずに前記曲線出力領域の曲線を前記曲線入力手段に別の入力タスクとして再入力する水平方向分割と、前記曲線出力領域に曲線が存在する場合でも前記ＳＩＭＤプロセッサからの終了信号を待ち新たに出力された曲線を優先してＮ＝１として前記曲線入力手段に再入力する垂直方向分割とを動的に切り替える分割方向切替手段と、
を具備し、
はじめに設定された１個の曲線を構成する点と評価値に対して再帰的に行うことで所望の曲線近似直線を生成する、
ことを特徴とする集積回路。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１０−１４６２５０（Ｐ２０１０−１４６２５０Ａ）
【公開日】平成２２年７月１日（２０１０．７．１）
【国際特許分類】
【出願番号】特願２００８−３２２１３７（Ｐ２００８−３２２１３７）
【出願日】平成２０年１２月１８日（２００８．１２．１８）
【出願人】（０００００５８２１）パナソニック株式会社 (73,050)
【Ｆターム（参考）】
【公開日】平成２２年７月１日（２０１０．７．１）
【国際特許分類】
【出願日】平成２０年１２月１８日（２００８．１２．１８）
【出願人】（０００００５８２１）パナソニック株式会社 (73,050)
【Ｆターム（参考）】
[ Back to top ]