(57)【要約】【課題】本発明は、直線描画方法、直線描画プログラム及び直線描画装置に関し、製造コストを低減でき、処理性能を向上できる直線描画装置、直線描画方法及び直線描画プログラムを提供することを目的とする。【解決手段】フレーム画定直線ａ〜ｄにより画定される描画フレーム１０１の外側に双方が位置し、かつフレーム画定直線ａ〜ｄのいずれに対しても少なくとも一方が描画フレーム１０１側に位置する両端点Ａ、Ｂを有する直線Ｌ５を描画する際に、直線Ｌ５の両端点Ａ、Ｂ間の中間点Ｃ０を求め、中間点Ｃ０が描画フレーム１０１外に位置し、かつフレーム画定直線ａ〜ｄのいずれに対しても端点Ｂ及び中間点Ｃ０の少なくとも一方が描画フレーム１０１側に位置していれば、直線Ｌ５のうち端点Ａ及び中間点Ｃ０間を描画対象から除外し、端点Ｂ及び中間点Ｃ０を新たな描画対象直線Ｌ５’の両端点とする。【選択図】図１
2008009719.tif 000002
【特許請求の範囲】
【請求項１】
複数のフレーム画定直線により画定される描画フレームの外側に双方が位置し、かつ前記複数のフレーム画定直線のいずれに対しても少なくとも一方が前記描画フレーム側に位置する第１及び第２の点を両端点として有する描画対象直線を描画する際に、
前記描画フレーム内に位置する前記描画対象直線上の第３の点を求め、
前記第３の点が存在すれば、前記描画フレーム内の前記描画対象直線を描画すること
を特徴とする直線描画方法。
【請求項２】
請求項１記載の直線描画方法において、
前記描画対象直線上の前記第１及び第２の点間の中間点を求め、
前記中間点が前記描画フレーム内に位置していれば、前記中間点を前記第３の点とすること
を特徴とする直線描画方法。
【請求項３】
請求項２記載の直線描画方法において、
前記中間点が前記描画フレーム外に位置し、かつ前記複数のフレーム画定直線のいずれに対しても前記第１の点及び前記中間点の少なくとも一方が前記描画フレーム側に位置していれば、
前記描画対象直線のうち前記第２の点及び前記中間点間を描画対象から除外し、前記第１の点及び前記中間点を新たな描画対象直線の両端点とすること
を特徴とする直線描画方法。
【請求項４】
複数のフレーム画定直線により画定される描画フレームの外側に双方が位置し、かつ前記複数のフレーム画定直線のいずれに対しても少なくとも一方が前記描画フレーム側に位置する第１及び第２の点を両端点として有する描画対象直線を描画する際に、前記描画フレーム内に位置する前記描画対象直線上の第３の点を求める手順と、
前記第３の点が存在すれば、前記描画フレーム内の前記描画対象直線を描画する手順とをコンピュータに実行させること
を特徴とする直線描画プログラム。
【請求項５】
複数のフレーム画定直線により画定される描画フレームの外側に双方が位置し、かつ前記複数のフレーム画定直線のいずれに対しても少なくとも一方が前記描画フレーム側に位置する第１及び第２の点を両端点として有する描画対象直線を描画する際に、前記描画フレーム内に位置する前記描画対象直線上の第３の点を求める演算回路と、
前記第３の点が存在すれば、前記描画フレーム内の前記描画対象直線を描画する直線描画回路と
を有することを特徴とする直線描画装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、直線を描画フレーム内に描画する際に用いられる直線描画方法、直線描画プログラム及び直線描画装置に関する。
【背景技術】
【０００２】
直線等を描画する図形描画装置には、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）やＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）等がある。図５は、図形描画装置の描画フレーム（クリップフレーム）と描画対象の直線との位置関係を示している。図５に示すように、長方形状の描画フレーム１０１に囲まれた領域は、直線等が描画される描画領域になっている。描画領域のＸ座標の最小値Ｘｍｉｎ及び最大値ＸｍａｘとＹ座標の最小値Ｙｍｉｎ及び最大値Ｙｍａｘとを用いると、描画フレーム１０１は、各座標（Ｘｍｉｎ，Ｙｍｉｎ）、（Ｘｍａｘ，Ｙｍｉｎ）、（Ｘｍｉｎ，Ｙｍａｘ）及び（Ｘｍａｘ，Ｙｍａｘ）で表される４点を４つの角に含んでいる。各直線Ｌ１１〜Ｌ１４は、描画フレーム１０１内に存在する部分のみが描画され、描画フレーム１０１外に存在する部分は描画されない。すなわち、直線Ｌ１１の全部、直線Ｌ１３のＡ’Ｂ間及び直線Ｌ１４のＡ’Ｂ’間は、描画フレーム１０１内に存在するため描画される。一方、直線Ｌ１２の全部、直線Ｌ１３のＡＡ’間、直線Ｌ１４のＡＡ’間及びＢ’Ｂ間は、描画フレーム１０１外に存在するため描画されない。
【０００３】
図６は、従来の直線描画方法の例を示している。図６に示すように、平面領域は、描画フレーム１０１を画定する４本の直線ａ（Ｘ＝Ｘｍｉｎ）、ｂ（Ｘ＝Ｘｍａｘ）、ｃ（Ｙ＝Ｙｍｉｎ）及びｄ（Ｙ＝Ｙｍａｘ）により９領域に分割される。各領域には、以下の基準により４ビットの領域コードが対応付けられる。すなわち、領域コードの最上位ビットＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）は、位置座標において、Ｘ＜Ｘｍｉｎの場合に１とし、Ｘ≧Ｘｍｉｎの場合に０とする。左から２番目のビットは、Ｘ＞Ｘｍａｘの場合に１とし、Ｘ≦Ｘｍａｘの場合に０とする。左から３番目のビットは、Ｙ＜Ｙｍｉｎの場合に１とし、Ｙ≧Ｙｍｉｎの場合に０とする。最下位ビットＬＳＢ（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）は、Ｙ＞Ｙｍａｘの場合に１とし、Ｙ≦Ｙｍａｘの場合に０とする。領域コード（００００）は描画フレーム１０１内であることを表し、（００００）以外の領域コードは描画フレーム１０１外であることを表している。
【０００４】
直線を描画するときには、まず上記基準を用いて、直線の始点Ａと終点Ｂの領域コードをそれぞれ求める。図６に示す直線Ｌ２１、Ｌ２２のように始点Ａの領域コードが（００００）である場合には、始点Ａから終点Ｂへの直線の描画を始める。直線Ｌ２１は、終点Ｂの領域コードも（００００）であり、終点Ｂが描画フレーム１０１内にあるので、ＡＢ間の全部が描画される。直線Ｌ２２は、終点Ｂの領域コードが（０００１）であり、終点Ｂが描画フレーム１０１外（＋Ｙ側）にあるので、Ｙ座標がＹｍａｘである点Ａ’までしか描画されない。
【０００５】
直線Ｌ２３〜Ｌ２５のように始点Ａの領域コードが（００００）でない場合には、両端点Ａ、Ｂの領域コードの論理積を求める。直線Ｌ２３のように、両端点Ａ、Ｂの領域コードの論理積がゼロでなければ、端点Ａ、Ｂが描画フレーム１０１外の同じ側にあるため、その直線は描画されない。直線Ｌ２４、Ｌ２５のように、両端点Ａ、Ｂの領域コードの論理積がゼロであれば、直線Ｌ２４、Ｌ２５と直線ａ〜ｄとの交点の座標を求める。
【０００６】
例えば直線Ｌ２４の場合には、端点ＡのＸ座標がＸｍａｘより大きいので、次式（１）により直線ｂ（Ｘ＝Ｘｍａｘ）との交点Ａ’の座標（ＸＡ’，ＹＡ’）を求める。ここで、ｄｙｄｘは直線Ｌ２４の傾き値である。
ＸＡ’＝Ｘｍａｘ；
ＹＡ’＝ＹＡ＋（Ｘｍａｘ−ＸＡ）×（ｄｙｄｘ）    ・・・（１）
【０００７】
直線Ｌ２４のＡＡ’間は、描画フレーム１０１外の＋Ｘ側にあるので描画されない。また交点Ａ’の領域コードは（０００１）であり、端点Ｂの領域コード（０００１）との論理積がゼロでないので、直線Ｌ２４のＡ’Ｂ間も描画されない。
【０００８】
直線Ｌ２５の場合には、始点Ａが描画フレーム１０１外の−Ｘ側かつ＋Ｙ側にあるので、上記と同様に交点Ａ’や交点Ａ’’を求める。交点Ａ’’を求めた場合、交点Ａ’’の領域コードが（１０００）であり、まだ描画フレーム１０１外の領域にあるので、さらに交点Ａ’を求める必要がある。交点Ａ’の領域コードは（００００）であるので、直線Ｌ２５のＡ’Ｂ’間を描画する。
【特許文献１】特許第３０６６５９９号公報
【特許文献２】特開２００１−１７５２４３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら従来の直線描画方法では、直線Ｌ２４、Ｌ２５のように端点Ａが描画フレーム１０１外の領域にあり、かつ両端点Ａ、Ｂの領域コードの論理積がゼロである場合に、交点Ａ’や交点Ａ’’を求める必要がある。これらの交点を求める際には式（１）のように除算や乗算が必要になるため、演算回路が加減算器だけでなく除算器と乗算器を備える必要がある。大規模で複雑な除算器や乗算器は直線描画装置のコストを増加させ、また回路処理性能のボトルネックになる。したがって、従来の直線描画装置は、製造コストが増加し、処理性能が低下してしまうという問題を有している。
【００１０】
本発明の目的は、製造コストを低減でき、処理性能を向上できる直線描画装置、直線描画方法及び直線描画プログラムを提供することにある。
【課題を解決するための手段】
【００１１】
上記目的は、複数のフレーム画定直線により画定される描画フレームの外側に双方が位置し、かつ前記複数のフレーム画定直線のいずれに対しても少なくとも一方が前記描画フレーム側に位置する第１及び第２の点を両端点として有する描画対象直線を描画する際に、前記描画フレーム内に位置する前記描画対象直線上の第３の点を求め、前記第３の点が存在すれば、前記描画フレーム内の前記描画対象直線を描画することを特徴とする直線描画方法によって達成される。
【００１２】
また上記目的は、複数のフレーム画定直線により画定される描画フレームの外側に双方が位置し、かつ前記複数のフレーム画定直線のいずれに対しても少なくとも一方が前記描画フレーム側に位置する第１及び第２の点を両端点として有する描画対象直線を描画する際に、前記描画フレーム内に位置する前記描画対象直線上の第３の点を求める手順と、前記第３の点が存在すれば、前記描画フレーム内の前記描画対象直線を描画する手順とをコンピュータに実行させることを特徴とする直線描画プログラムによって達成される。
【００１３】
さらに上記目的は、複数のフレーム画定直線により画定される描画フレームの外側に双方が位置し、かつ前記複数のフレーム画定直線のいずれに対しても少なくとも一方が前記描画フレーム側に位置する第１及び第２の点を両端点として有する描画対象直線を描画する際に、前記描画フレーム内に位置する前記描画対象直線上の第３の点を求める演算回路と、前記第３の点が存在すれば、前記描画フレーム内の前記描画対象直線を描画する直線描画回路とを有することを特徴とする直線描画装置によって達成される。
【発明の効果】
【００１４】
本発明によれば、製造コストを低減でき、処理性能を向上できる直線描画装置、直線描画方法及び直線描画プログラムを実現できる。
【発明を実施するための最良の形態】
【００１５】
本発明の一実施の形態による直線描画方法、直線描画プログラム及び直線描画装置について図１乃至図４を用いて説明する。図１は、本実施の形態による直線描画方法の例を示している。図１に示すように、長方形状の描画フレーム１０１に囲まれた領域は、直線等が描画される描画領域である。描画領域のＸ座標の最小値Ｘｍｉｎ及び最大値ＸｍａｘとＹ座標の最小値Ｙｍｉｎ及び最大値Ｙｍａｘとを用いると、描画フレーム１０１は、点ｅ（Ｘｍｉｎ，Ｙｍｉｎ）、点ｆ（Ｘｍａｘ，Ｙｍｉｎ）、点ｇ（Ｘｍｉｎ，Ｙｍａｘ）及び点ｈ（Ｘｍａｘ，Ｙｍａｘ）の４点を４つの角に含んでいる。
【００１６】
平面領域は、描画フレーム１０１を画定する４本のフレーム画定直線ａ（Ｘ＝Ｘｍｉｎ）、ｂ（Ｘ＝Ｘｍａｘ）、ｃ（Ｙ＝Ｙｍｉｎ）及びｄ（Ｙ＝Ｙｍａｘ）により９領域に分割される。各領域には、以下の基準で４ビットの領域コードが対応付けられる。すなわち、領域コードの最上位ビットＭＳＢは、位置座標において、Ｘ＜Ｘｍｉｎの場合に１とし、Ｘ≧Ｘｍｉｎの場合に０とする。左から２番目のビットは、Ｘ＞Ｘｍａｘの場合に１とし、Ｘ≦Ｘｍａｘの場合に０とする。左から３番目のビットは、Ｙ＜Ｙｍｉｎの場合に１とし、Ｙ≧Ｙｍｉｎの場合に０とする。最下位ビットＬＳＢは、Ｙ＞Ｙｍａｘの場合に１とし、Ｙ≦Ｙｍａｘの場合に０とする。領域コード（００００）は描画フレーム１０１の内側（フレーム上を含む）であることを表し、（００００）以外の領域コードは描画フレーム１０１の外側であることを表している。
【００１７】
描画対象の直線Ｌ１〜Ｌ５を描画するときには、まず上記基準を用いて、直線の端点（始点）Ａと端点（終点）Ｂの領域コードをそれぞれ求める。図１に示す例では、直線Ｌ１の始点Ａ及び終点Ｂの領域コードは共に（００００）である。直線Ｌ２の始点Ａの領域コードは（００００）であり、終点Ｂの領域コードは（０００１）である。直線Ｌ３の始点Ａの領域コードは（１００１）であり、終点Ｂの領域コードは（０００１）である。直線Ｌ４の始点Ａの領域コードは（０１００）であり、終点Ｂの領域コードは（０００１）である。直線Ｌ５の始点Ａの領域コードは（１００１）であり、終点Ｂの領域コードは（００１０）である。
【００１８】
直線Ｌ１、Ｌ２のように始点Ａの領域コードが（００００）である場合には、始点Ａから終点Ｂに向かって直線の描画を始める。直線Ｌ１については、終点Ｂの領域コードも（００００）であり、終点Ｂが描画フレーム１０１内に位置するので、始点Ａ及び終点Ｂ間の全部が描画される。直線Ｌ２については、終点Ｂの領域コードが（０００１）であり、終点Ｂが描画フレーム１０１外の＋Ｙ側に位置するので、Ｙ座標がＹｍａｘである点Ａ’までしか描画されない。
【００１９】
直線Ｌ３〜Ｌ５のように両端点Ａ、Ｂの領域コードがいずれも（００００）でない場合には、両端点Ａ、Ｂの領域コードの論理積を求める。描画対象直線の両端点Ａ、Ｂの領域コードの論理積を求めることによって、描画対象直線の両端点Ａ、Ｂと各フレーム画定直線ａ〜ｄとの位置関係が分かる。両端点Ａ、Ｂの領域コードの論理積がゼロであれば、フレーム画定直線ａ〜ｄのいずれに対しても、端点Ａ、Ｂの少なくとも一方が描画フレーム１０１側に位置する。したがって、その描画対象直線の一部は描画フレーム１０１内を通っている可能性がある。一方、両端点Ａ、Ｂの領域コードの論理積がゼロでなければ、フレーム画定直線ａ〜ｄの少なくともいずれか１つに対して、端点Ａ、Ｂの双方が描画フレーム１０１の反対側に位置する。したがって、その描画対象直線が描画フレーム１０１内を通っている可能性はなく、描画対象直線上の描画フレーム１０１内の点は存在しない。
【００２０】
直線Ｌ３は、両端点Ａ、Ｂの領域コードがいずれも（００００）ではなく、かつ両端点Ａ、Ｂの領域コードの論理積がゼロでない。したがって、直線Ｌ３が描画フレーム１０１内を通っている可能性はないため、直線Ｌ３の描画を終了する。
【００２１】
直線Ｌ４、Ｌ５は、両端点Ａ、Ｂの領域コードがいずれも（００００）ではなく、両端点Ａ、Ｂの領域コードの論理積がゼロである。したがって、直線Ｌ４、Ｌ５は、それぞれの一部が描画フレーム１０１内を通っている可能性がある。本実施の形態は以下に説明するように、直線Ｌ４、Ｌ５のように両端点Ａ、Ｂの領域コードがいずれも（００００）でなく、両端点Ａ、Ｂの領域コードの論理積がゼロである直線を容易に描画できる点に主な特徴を有している。
【００２２】
本実施の形態では、直線Ｌ４について、下記の式（２）により両端点Ａ、Ｂ間の中間点Ｃ０を求める。中間点Ｃ０のＸ座標ＸＣは、端点ＡのＸ座標ＸＡと端点ＢのＸ座標ＸＢとを加算して２で除することにより求められ、中間点Ｃ０のＹ座標ＹＣは、端点ＡのＹ座標ＹＡと端点ＢのＹ座標ＹＢとを加算して２で除することにより求められる。ここで、２進数で表された数値Ｘは、最下位の１ビットを捨てる右シフト演算によりＸ／２となる。このため、加算器があれば式（２）の演算が可能である。本実施の形態では、描画対象直線とフレーム画定直線との交点を求めないため、従来必要であった乗算器や除算器が不要になる。
ＸＣ＝（ＸＡ＋ＸＢ）／２；
ＹＣ＝（ＹＡ＋ＹＢ）／２    ・・・（２）
【００２３】
直線Ｌ４の中間点Ｃ０の領域コードは（０１０１）であり、端点Ａの領域コードとの論理積及び端点Ｂの領域コードとの論理積はいずれもゼロでない。これにより、直線Ｌ４の端点Ａ及び中間点Ｃ０の間と端点Ｂ及び中間点Ｃ０の間は、いずれも描画フレーム１０１外の領域にあることが分かる。したがって、直線Ｌ４の描画を終了する。
【００２４】
直線Ｌ５について、同様に式（２）により両端点Ａ、Ｂ間の中間点Ｃ０を求める。直線Ｌ５の中間点Ｃ０の領域コードは（１０００）であり、中間点Ｃ０は描画フレーム１０１外の領域にある。また、直線Ｌ５の中間点Ｃ０の領域コードと端点Ａの領域コードとの論理積はゼロでなく、フレーム画定直線ａに対して端点Ａ及び中間点Ｃ０の双方が描画フレーム１０１の反対側に位置している。これにより、直線Ｌ５のうち端点Ａ及び中間点Ｃ０の間は、描画フレーム１０１外の領域にあることが分かる。
【００２５】
一方、直線Ｌ５の中間点Ｃ０の領域コードと端点Ｂの領域コードとの論理積はゼロであるので、フレーム画定直線ａ〜ｄのいずれに対しても中間点Ｃ０及び端点Ｂの少なくとも一方が描画フレーム１０１側に位置している。したがって、直線Ｌ５のうち端点Ａ及び中間点Ｃ０の間を描画対象から除外する。さらに、中間点Ｃ０の座標を端点Ａの座標に代入して中間点Ｃ０を新たな端点とし、端点Ｃ０及び端点Ｂを新たな描画対象直線Ｌ５’の両端点とする。なお、中間点が描画フレーム１０１外に位置する直線では、中間点の領域コードと両端点の領域コードとの論理積がいずれもゼロになることはない。このため、中間点の領域コードと一方の端点の領域コードとの論理積がゼロであることが分かれば、中間点の領域コードと他方の端点の領域コードとの論理積を求める必要は必ずしもない。
【００２６】
新たな直線Ｌ５’について、同様に式（２）により両端点Ｃ０、Ｂ間の新たな中間点Ｃ１を求める。直線Ｌ５’の中間点Ｃ１の領域コードは（００００）であり、中間点Ｃ１は描画フレーム１０１内に位置する。したがって、中間点Ｃ１から端点Ｃ０に向かって直線の描画を始める。端点Ｃ０は描画フレーム１０１外の−Ｘ側に位置するので、Ｘ座標がＸｍｉｎである点Ａ’まで直線が描画される。また、中間点Ｃ１から端点Ｂに向かって直線の描画を始める。端点Ｂは描画フレーム１０１外の−Ｙ側に位置するので、Ｙ座標がＹｍｉｎである点Ｂ’まで直線が描画される。
【００２７】
このように、直線Ｌ４、Ｌ５のように両端点Ａ、Ｂの領域コードがいずれも（００００）でなく、両端点Ａ、Ｂの領域コードの論理積がゼロである直線については、中間点の領域コードが（００００）であること、又は、中間点の領域コードと両端点の領域コードとの論理積がいずれもゼロでないことが分かるまで、新たな中間点Ｃ０、Ｃ１、・・・を求め続ける。直線の両端点Ａ、Ｂ間の距離をＡＢとすると、中間点を最大ｌｏｇ２（ＡＢ）回求めることになる。
【００２８】
以下、本実施の形態による直線描画方法の各手順をコンピュータに実行させるためのＣ言語によるアルゴリズムの一例を示す。
typedef struct {
// Ｘ座標（整数も可能）;
float  X;
// Ｙ座標（整数も可能）;
float  Y;
} PCoord;
// 領域コードを求める関数;
int   RegionCoding();
// 描画フレームに直線を描画する関数;
void  DrawLine();
// 中間点Ｃの座標を求める;
PCoord  MiddlePoint(PCoord A; PCoord B) {
PointCoord  C;
C.X = (A.X + B.X)/2;
C.Y = (A.Y + B.Y)/2;
return C;
}
// 論理積を求める関数;
int  LogicOR(int A; int B) {
int  C;
C = A | B;
return C;
}
void main() {
PCoord A, B, C;
PCoord LeftTop, RightBottom;
int  CodeA, CodeB, CodeC;
// 両端点Ａ、Ｂの領域コードを求める;
CodeA = RegionCoding(A);
CodeB = RegionCoding(B);
if (CodeA == 0) {
// 端点Ａが描画フレーム内にある場合に、端点Ａから端点Ｂへ直線を描画する;
DrawLine(A, B);
} else if (CodeB == 0) {
// 端点Ｂが描画フレーム内にある場合に、端点Ｂから端点Ａへ直線を描画する;
DrawLine(B, A);
} else if (LogicOR(A,B) != 0) {
// 直線の全体が描画フレーム外にある場合に描画終了;
return 0;
} else {
while (1) {
// 中間点Ｃの座標と領域コードを求める;
C = MiddlePoint(A, B);
CodeC = RegionCoding(C);
if (CodeC == 0) {
// 中間点Ｃが描画フレーム内にある場合、ＣからＡ及びＣからＢへそれぞれ直線を描画して、終了する;
DrawLine(C, A);
DrawLine(C, B);
return 1;
} else if (LogicOR(C, A) == 0) {
// 直線のＣＢ間が描画フレーム外にある場合に、中間点Ｃで端点Ｂを置換して、新たな中間点Ｃを求める;
B = C;
} else if (LogicOR(C, B) == 0) {
// 直線のＣＡ間が描画フレーム外にある場合に、中間点Ｃで端点Ａを置換して、新たな中間点Ｃを求める;
A = C;
} else {
// 直線のＣＡ間とＣＢ間が両方描画フレーム外にある場合に、終了する;
return 0;
}
}
}
}
【００２９】
次に、本実施の形態による直線描画方法をハードウェアにより実現する直線描画装置の構成の例について説明する。図２は、本実施の形態による直線描画装置の基本構成を示すブロック図である。図２において、制御部４００から出力されるＲｅａｄｙ信号は、新たな描画対象直線の描画が可能であることを表す。直線を描画する前には、描画領域のＸ座標の最大値Ｘｍａｘ及び最小値Ｘｍｉｎと、Ｙ座標の最大値Ｙｍａｘ及び最小値Ｙｍｉｎとが、領域コーディング回路４１２が備えるレジスタに書き込まれる。描画対象直線の端点Ａの座標（ＸＡ，ＹＡ）と端点Ｂの座標（ＸＢ，ＹＢ）は、選択器４０２、４０３、４０４及び４０５によりそれぞれ選択される。端点ＡのＸ座標ＸＡはレジスタＸＡ４０６に書き込まれ、端点ＡのＹ座標ＹＡはレジスタＹＡ４０７に書き込まれる。端点ＢのＸ座標ＸＢはレジスタＸＢ４１０に書き込まれ、端点ＢのＹ座標ＹＢはレジスタＹＢ４１１に書き込まれる。制御部４００に入力されたＳｔａｒｔ信号がＨｉｇｈとなると、次のサイクルから制御部４００の制御により描画対象直線の描画を開始する。
【００３０】
レジスタＸＡ４０６、レジスタＹＡ４０７、レジスタＸＢ４１０及びレジスタＹＢ４１１から出力された端点Ａの座標（ＸＡ，ＹＡ）及び端点Ｂの座標（ＸＢ，ＹＢ）は、領域コーディング回路４１２に入力される。領域コーディング回路４１２は、端点Ａ、Ｂの各座標から端点Ａ、Ｂの領域コードＣＡ、ＣＢをそれぞれ計算する。端点Ａの領域コードＣＡは領域コードレジスタＣＡ４１３に書き込まれ、端点Ｂの領域コードＣＢは領域コードレジスタＣＢ４１４に書き込まれる。また、レジスタＸＡ４０６、レジスタＹＡ４０７、レジスタＸＢ４１０及びレジスタＹＢ４１１から出力された端点Ａの座標（ＸＡ，ＹＡ）と端点Ｂの座標（ＸＢ，ＹＢ）は、中間点演算回路４０１にも入力される。中間点演算回路４０１は、端点Ａ、Ｂの各座標から中間点Ｃの座標（ＸＣ，ＹＣ）を計算する。中間点ＣのＸ座標ＸＣはレジスタＸＣ４０８に書き込まれ、中間点ＣのＹ座標ＹＣはレジスタＹＣ４０９に書き込まれる。
【００３１】
図３は、中間点演算回路４０１の構成の例を示すブロック図である。図３に示すように、中間点演算回路４０１は、加算器４２７と、加算器４２７の後段に設けられたシフト演算器４３１とを有している。加算器４２７は、端点ＡのＸ座標ＸＡと端点ＢのＸ座標ＸＢとを入力し、これらを加算した（ＸＡ＋ＸＢ）をシフト演算器４３１に出力する。ＸＡ、ＸＢ及び（ＸＡ＋ＸＢ）は、いずれも（ｎ＋１）ビット（例えば３２ビット）のデータである。シフト演算器４３１は、入力した（ＸＡ＋ＸＢ）の最下位の１ビットを捨てて、端点Ａ、Ｂ間の中間点ＣのＸ座標となるＸＣを出力する。ＸＣはｎビットのデータであり、（ＸＡ＋ＸＢ）／２にほぼ等しい。
【００３２】
また中間点演算回路４０１は、加算器４２８と、加算器４２８の後段に設けられたシフト演算器４３２とを有している。加算器４２８は、端点ＡのＹ座標ＹＡと端点ＢのＹ座標ＹＢとを入力し、これらを加算した（ＹＡ＋ＹＢ）をシフト演算器４３２に出力する。ＹＡ、ＹＢ及び（ＹＡ＋ＹＢ）は、いずれも（ｎ＋１）ビット（例えば３２ビット）のデータである。シフト演算器４３２は、入力した（ＹＡ＋ＹＢ）の最下位の１ビットを捨てて、端点Ａ、Ｂ間の中間点ＣのＹ座標となるＹＣを出力する。ＹＣはｎビットのデータであり、（ＹＡ＋ＹＢ）／２にほぼ等しい。
【００３３】
図２に戻り、領域コードレジスタＣＡ４１３から出力された端点Ａの領域コードＣＡは、選択器４１６により選択され、比較器４１８によって描画フレーム内の領域コード（００００）と比較される。領域コードレジスタＣＢ４１４から出力された端点Ｂの領域コードＣＢは、比較器４１９によって描画フレーム内の領域コード（００００）と比較される。また、領域コードレジスタＣＢ４１４から出力された端点Ｂの領域コードＣＢは、選択器４１７により選択され、論理積回路４２０に入力される。論理積回路４２０は、端点Ｂの領域コードＣＢと、領域コードレジスタＣＡ４１３から出力された端点Ａの領域コードＣＡとの論理積を求め、求めた論理積を制御部４００に出力する。また、レジスタＸＣ４０８から出力された中間点ＣのＸ座標ＸＣと、レジスタＹＣ４０９から出力された中間点ＣのＹ座標ＹＣは、領域コーディング回路４１２に入力される。領域コーディング回路４１２は、中間点Ｃの座標から中間点Ｃの領域コードＣＣを計算する。中間点Ｃの領域コードＣＣは、中間点領域コードレジスタＣＣ４１５に書き込まれる。
【００３４】
制御部４００には、端点Ａの領域コードＣＡが（００００）であるか否かを表す信号が比較器４１８から入力され、端点Ｂの領域コードＣＢが（００００）であるか否かを表す信号が比較器４１９から入力される。端点Ａの領域コードＣＡが（００００）である場合には端点Ａが描画フレーム内にあるので、制御部４００は、レジスタＸＡ４０６から出力された端点ＡのＸ座標ＸＡとレジスタＹＡ４０７から出力された端点ＡのＹ座標ＹＡとを選択器４２２、４２３にそれぞれ選択させ、直線描画回路４２６に出力させる。また制御部４００は、レジスタＸＢ４１０から出力された端点ＢのＸ座標ＸＢとレジスタＹＢ４１１から出力された端点ＢのＹ座標ＹＢとを選択器４２４、４２５にそれぞれ選択させ、直線描画回路４２６に出力させる。次のサイクルから、直線描画回路４２６により端点Ａから端点Ｂへ直線が描画される。
【００３５】
端点Ａの領域コードＣＡが（００００）でなく、かつ端点Ｂの領域コードＣＢが（００００）である場合には、端点Ａが描画フレーム外にあり端点Ｂが描画フレーム内にある。したがって制御部４００は、レジスタＸＢ４１０から出力された端点ＢのＸ座標ＸＢとレジスタＹＢ４１１から出力された端点ＢのＹ座標ＹＢとを選択器４２２、４２３に選択させ、直線描画回路４２６に出力させる。またレジスタＸＡ４０６から出力された端点ＡのＸ座標ＸＡとレジスタＹＡ４０７から出力された端点ＡのＹ座標ＹＡとを選択器４２４、４２５に選択させ、直線描画回路４２６に出力させる。次のサイクルから、直線描画回路４２６により端点Ｂから端点Ａへ直線が描画される。
【００３６】
端点Ａ、Ｂの領域コードＣＡ、ＣＢが共に（００００）でなく、かつ端点Ａ、Ｂの領域コードＣＡ、ＣＢの論理積がゼロではない場合には、端点Ａ、Ｂが共に描画フレーム外の同じ側にあるので、直線を描画せずに終了する。
【００３７】
端点Ａ、Ｂの領域コードＣＡ、ＣＢが共に（００００）でなく、かつ端点Ａ、Ｂの領域コードＣＡ、ＣＢの論理積がゼロである場合には、次のサイクルから中間点Ｃを用いて描画判定を行う。領域コードレジスタＣＣ４１５から出力された中間点Ｃの領域コードＣＣが選択器４１６により選択され、比較器４１８によって描画フレーム内の領域コード（００００）と比較される。また、領域コードレジスタＣＣ４１５から出力された中間点Ｃの領域コードＣＣが選択器４１７により選択され、論理積回路４２０に入力される。論理積回路４２０は、入力した領域コードＣＣと、領域コードレジスタＣＡ４１３から出力された端点Ａの領域コードＣＡとの論理積を求め、求めた論理積を制御部４００に出力する。論理積回路４２１は、領域コードレジスタＣＣ４１５から出力された中間点Ｃの領域コードＣＣと、領域コードレジスタＣＢ４１４から出力された端点Ｂの領域コードＣＢとの論理積を求め、制御部４００に出力する。
【００３８】
制御部４００には、中間点Ｃの領域コードＣＣが（００００）であるか否かを表す信号が比較器４１８から入力される。中間点Ｃの領域コードＣＣが（００００）である場合には中間点Ｃが描画フレーム内にあるので、制御部４００は、レジスタＸＣ４０８から出力された中間点ＣのＸ座標ＸＣとレジスタＹＣ４０９から出力された中間点ＣのＹ座標ＹＣとを選択器４２２、４２３に選択させ、直線描画回路４２６に出力させる。また制御部４００は、レジスタＸＡ４０６から出力された端点ＡのＸ座標ＸＡとレジスタＹＡ４０７から出力された端点ＡのＹ座標ＹＡとを選択器４２４、４２５に選択させ、直線描画回路４２６に出力させる。次のサイクルから、直線描画回路４２６により中間点Ｃから端点Ａへ直線が描画される。直線の描画が完了したら、制御部４００は、レジスタＸＢ４１０から出力された端点ＢのＸ座標ＸＢとレジスタＹＢ４１１から出力された端点ＢのＹ座標ＹＢとを選択器４２４、４２５に選択させ、直線描画回路４２６に出力させる。次のサイクルから、直線描画回路４２６により中間点Ｃから端点Ｂへ直線が描画される。直線の描画が完了したら終了する。
【００３９】
中間点Ｃの領域コードＣＣが（００００）でなく、かつ中間点Ｃの領域コードＣＣ及び端点Ａの領域コードＣＡの論理積と、中間点Ｃの領域コードＣＣ及び端点Ｂの領域コードＣＢの論理積とがいずれもゼロでない場合には、直線の中間点Ｃ及び端点Ａの間と中間点Ｃ及び端点Ｂの間とが共に描画フレーム外の領域にあるため、直線を描画せずに終了する。
【００４０】
中間点Ｃの領域コードＣＣが（００００）ではなく、かつ中間点Ｃの領域コードＣＣと端点Ａの領域コードＣＡとの論理積がゼロである場合には、制御部４００は、レジスタＸＣ４０８から出力された中間点ＣのＸ座標ＸＣとレジスタＹＣ４０９から出力された中間点ＣのＹ座標ＹＣとを選択器４０４、４０５にそれぞれ選択させる。中間点ＣのＸ座標ＸＣは、端点ＢのＸ座標ＸＢに代えてレジスタＸＢ４１０に書き込まれ、中間点ＣのＹ座標ＹＣは、端点ＢのＹ座標ＹＢに代えてレジスタＹＢ４１１に書き込まれる。次のサイクルから、新たな両端点の座標（ＸＡ，ＹＡ）、（ＸＢ，ＹＢ）を用いて新たな中間点Ｃを求める。その後、中間点Ｃの領域コードＣＣが（００００）であること、又は、中間点Ｃの領域コードＣＣと両端点Ａ、Ｂの領域コードＣＡ、ＣＢとの論理積がいずれもゼロでないことが分かるまで、上記と同様に新たな中間点Ｃを用いた描画判定を行い続ける。
【００４１】
中間点Ｃの領域コードＣＣが（００００）ではなく、かつ中間点Ｃの領域コードＣＣと端点Ｂの領域コードＣＢとの論理積がゼロである場合には、制御部４００は、レジスタＸＣ４０８から出力された中間点ＣのＸ座標ＸＣとレジスタＹＣ４０９から出力された中間点ＣのＹ座標ＹＣとを選択器４０２、４０３にそれぞれ選択させる。中間点ＣのＸ座標ＸＣは、端点ＡのＸ座標ＸＡに代えてレジスタＸＡ４０６に書き込まれ、中間点ＣのＹ座標ＹＣは、端点ＡのＹ座標ＹＡに代えてレジスタＹＡ４０７に書き込まれる。次のサイクルから、新たな両端点の座標（ＸＡ，ＹＡ）、（ＸＢ，ＹＢ）を用いて新たな中間点Ｃを求める。その後、中間点Ｃの領域コードＣＣが（００００）であること、又は、中間点Ｃの領域コードＣＣと両端点Ａ、Ｂの領域コードＣＡ、ＣＢとの論理積がいずれもゼロでないことが分かるまで、上記と同様に新たな中間点Ｃを用いた描画判定を行い続ける。
【００４２】
図４は、直線描画装置の制御部４００等の状態の遷移を示す図である。制御部４００の状態には、図４に示すように９つのステートＳ０〜Ｓ８がある。ステートＳ０〜Ｓ５に掛かる期間はそれぞれ１サイクルであり、ステートＳ６〜Ｓ８に掛かる期間は一般にそれぞれ数サイクルである。
【００４３】
ステートＳ０では、直線描画装置がアイドル状態にある。ステートＳ０では、描画フレームを構成するＸ座標の最大値Ｘｍａｘ及び最小値Ｘｍｉｎと、Ｙ座標の最大値Ｙｍａｘ及び最小値Ｙｍｉｎとが、領域コーディング回路４１２内のレジスタに書き込まれる。また、描画対象直線の端点Ａの座標（ＸＡ，ＹＡ）と端点Ｂの座標（ＸＢ，ＹＢ）とが、レジスタＸＡ４０６、レジスタＹＡ４０７、レジスタＸＢ４１０及びレジスタＹＢ４１１にそれぞれ書き込まれる。制御部４００に入力されるＳｔａｒｔ信号がＨｉｇｈになれば、次のサイクルでステートＳ１になり、直線描画処理を開始する。制御部４００に入力されるＳｔａｒｔ信号がＬｏｗであれば、次のサイクルもステートＳ０になる。
【００４４】
ステートＳ１では、描画対象直線の端点Ａの座標（ＸＡ，ＹＡ）と端点Ｂの座標（ＸＢ，ＹＢ）とを用いて、端点Ａの領域コードＣＡ、端点Ｂの領域コードＣＢ及び中間点Ｃの座標（ＸＣ，ＹＣ）を求める。次のサイクルはステートＳ２になる。
【００４５】
ステートＳ２では、両端点Ａ、Ｂの領域コードＣＡ、ＣＢを用いて描画判定を行い、中間点Ｃの座標（ＸＣ，ＹＣ）を用いて中間点Ｃの領域コードＣＣを求める。端点Ａの領域コードＣＡが（００００）である場合には、次のサイクルでステートＳ８になり、端点Ａから端点Ｂへ直線描画を行う。端点Ａの領域コードＣＡが（００００）ではなく、かつ端点Ｂの領域コードＣＢが（００００）である場合には、次のサイクルでステートＳ８になり、端点Ｂから端点Ａへ直線描画を行う。端点Ａ、Ｂの領域コードＣＡ、ＣＢが共に（００００）ではなく、かつ領域コードＣＡ、ＣＢの論理積がゼロでない場合には、直線を描画せずに描画処理を終了し、次のサイクルはステートＳ０になる。端点Ａ、Ｂの領域コードＣＡ、ＣＢが共に（００００）でなく、かつ領域コードＣＡ、ＣＢの論理積がゼロである場合には、次のサイクルでステートＳ３になり、中間点Ｃの領域コードＣＣを用いて描画判定を行う。
【００４６】
ステートＳ３では、中間点Ｃの領域コードＣＣが（００００）である場合に、次のサイクルでステートＳ６になり、中間点Ｃから端点Ａへ直線描画を行う。中間点Ｃの領域コードＣＣが（００００）ではなく、かつ中間点Ｃの領域コードＣＣと両端点Ａ、Ｂの領域コードＣＡ、ＣＢとの論理積がいずれもゼロでない場合には、直線描画を終了して、次のサイクルはステートＳ０になる。中間点Ｃの領域コードＣＣが（００００）でなく、かつ中間点Ｃの領域コードＣＣと端点Ａの領域コードＣＡとの論理積がゼロである場合には、中間点Ｃの座標を端点Ｂの座標に代入する。中間点Ｃの領域コードＣＣが（００００）でなく、かつ中間点Ｃの領域コードＣＣと端点Ｂの領域コードＣＢとの論理積がゼロである場合には、中間点Ｃの座標を端点Ａの座標に代入する。次のサイクルでステートＳ４になり、新たな端点Ａ、Ｂを用いて新たな中間点Ｃを求める。
【００４７】
ステートＳ４では、新たな端点Ａ、Ｂを用いて新たな中間点Ｃを求める。次のサイクルはステートＳ５になる。
【００４８】
ステートＳ５では、新たな中間点Ｃの領域コードＣＣを求める。次のサイクルはステートＳ３に戻り、新たな中間点Ｃに対して描画判定を行う。
【００４９】
ステートＳ６では、中間点Ｃから端点Ａへ直線を描画する。直線描画が完了したら、次のサイクルはステートＳ７になる。
【００５０】
ステートＳ７では、中間点Ｃから端点Ｂへ直線を描画する。直線描画が完了したら、次のサイクルはステートＳ０になる。
【００５１】
ステートＳ８では、端点Ａから端点Ｂへ（又は端点Ｂから端点Ａへ）直線を描画する。直線描画が完了したら、次のサイクルはステートＳ０になる。
【００５２】
以上のように本実施の形態では、描画対象直線の両端点Ａ、Ｂが描画フレーム外の領域にあり、かつ両端点Ａ、Ｂの領域コードＣＡ、ＣＢの論理積がゼロである場合に、描画対象直線とフレーム画定直線（描画フレーム）との交点を求めるのではなく、描画フレーム内（領域コード（００００））に位置する描画対象直線上の点を求める。描画フレーム内に位置する点は、両端点間の中間点を繰り返し求めることによって加算器を用いて求められる。したがって本実施の形態によれば、演算回路の回路構成を簡素化でき、直線描画装置の製造コストを低減できる。また、演算回路が除算器と乗算器を備える必要がないので、回路処理性能を向上できる。
【００５３】
以上説明した実施の形態による直線描画方法、直線描画プログラム及び直線描画装置は、以下のようにまとめられる。
（付記１）
複数のフレーム画定直線により画定される描画フレームの外側に双方が位置し、かつ前記複数のフレーム画定直線のいずれに対しても少なくとも一方が前記描画フレーム側に位置する第１及び第２の点を両端点として有する描画対象直線を描画する際に、
前記描画フレーム内に位置する前記描画対象直線上の第３の点を求め、
前記第３の点が存在すれば、前記描画フレーム内の前記描画対象直線を描画すること
を特徴とする直線描画方法。
（付記２）
付記１記載の直線描画方法において、
前記描画対象直線は、前記第３の点から前記第１及び第２の点に向かってそれぞれ描画すること
を特徴とする直線描画方法。
（付記３）
付記１又は２に記載の直線描画方法において、
前記第３の点が存在しなければ、前記描画対象直線の描画を終了すること
を特徴とする直線描画方法。
（付記４）
付記１乃至３のいずれか１項に記載の直線描画方法において、
前記描画対象直線上の前記第１及び第２の点間の中間点を求め、
前記中間点が前記描画フレーム内に位置していれば、前記中間点を前記第３の点とすること
を特徴とする直線描画方法。
（付記５）
付記４記載の直線描画方法において、
前記中間点が前記描画フレーム外に位置し、前記複数のフレーム画定直線の少なくともいずれか１つに対して前記第１の点及び前記中間点の双方が前記描画フレームの反対側に位置し、かつ前記複数のフレーム画定直線の少なくともいずれか１つに対して前記第２の点及び前記中間点の双方が前記描画フレームの反対側に位置していれば、
前記第３の点が存在しないと判断すること
を特徴とする直線描画方法。
（付記６）
付記４又は５に記載の直線描画方法において、
前記中間点が前記描画フレーム外に位置し、かつ前記複数のフレーム画定直線のいずれに対しても前記第１の点及び前記中間点の少なくとも一方が前記描画フレーム側に位置していれば、
前記描画対象直線のうち前記第２の点及び前記中間点間を描画対象から除外し、前記第１の点及び前記中間点を新たな描画対象直線の両端点とすること
を特徴とする直線描画方法。
（付記７）
付記４乃至６のいずれか１項に記載の直線描画方法において、
前記中間点の座標データは、前記第１及び第２の点の座標データの加算及び右シフト演算により求めること
を特徴とする直線描画方法。
（付記８）
複数のフレーム画定直線により画定される描画フレームの外側に双方が位置し、かつ前記複数のフレーム画定直線のいずれに対しても少なくとも一方が前記描画フレーム側に位置する第１及び第２の点を両端点として有する描画対象直線を描画する際に、前記描画フレーム内に位置する前記描画対象直線上の第３の点を求める手順と、
前記第３の点が存在すれば、前記描画フレーム内の前記描画対象直線を描画する手順とをコンピュータに実行させること
を特徴とする直線描画プログラム。
（付記９）
複数のフレーム画定直線により画定される描画フレームの外側に双方が位置し、かつ前記複数のフレーム画定直線のいずれに対しても少なくとも一方が前記描画フレーム側に位置する第１及び第２の点を両端点として有する描画対象直線を描画する際に、前記描画フレーム内に位置する前記描画対象直線上の第３の点を求める演算回路と、
前記第３の点が存在すれば、前記描画フレーム内の前記描画対象直線を描画する直線描画回路と
を有することを特徴とする直線描画装置。
（付記１０）
付記９記載の直線描画装置において、
前記演算回路は、前記描画対象直線上の前記第１及び第２の点間の中間点を求め、前記中間点が前記描画フレーム内に位置していれば、前記中間点を前記第３の点とすること
を特徴とする直線描画装置。
（付記１１）
付記１０記載の直線描画装置において、
前記演算回路は、前記第１及び第２の点の座標データを加算する加算器と、加算した前記座標データを右シフト演算するシフト演算器とを有すること
を特徴とする直線描画装置。
【図面の簡単な説明】
【００５４】
【図１】本発明の一実施の形態による直線描画方法の例を示す図である。
【図２】本発明の一実施の形態による直線描画装置の基本構成を示すブロック図である。
【図３】中間点演算回路の構成の例を示すブロック図である。
【図４】本発明の一実施の形態による直線描画装置の制御部の状態の遷移を示す図である。
【図５】描画フレームと描画対象の直線との関係を示す図である。
【図６】従来の直線描画方法の例を示す図である。
【符号の説明】
【００５５】
１０１  描画フレーム
４００  制御部
４０１  中間点演算回路
４０２、４０３、４０４、４０５、４１６、４１７、４２２、４２３、４２４、４２５  選択器
４０６  レジスタＸＡ
４０７  レジスタＹＡ
４０８  レジスタＸＣ
４０９  レジスタＹＣ
４１０  レジスタＸＢ
４１１  レジスタＹＢ
４１２  領域コーディング回路
４１３  領域コードレジスタＣＡ
４１４  領域コードレジスタＣＢ
４１５  領域コードレジスタＣＣ
４１８、４１９  比較器
４２０、４２１  論理積回路
４２６  直線描画回路
４２７、４２８  加算器
４３１、４３２  シフト演算器
【図１】
2008009719.tif 000003
【図２】
2008009719.tif 000004
【図３】
2008009719.tif 000005
【図４】
2008009719.tif 000006
【図５】
2008009719.tif 000007
【図６】
2008009719.tif 000008