JPH05128272A - 直線描画処理における交点算出方法 - Google Patents

Abstract

(57)【要約】 【目的】 直線描画処理時間の高速化および描画品質の
向上を可能とする。 【構成】 描画する直線の始点および終点の差分を算出
し、描画する直線の描画開始ドットを算出する演算子の
値を設定すると共に境界線の近傍でかつ描画領域外の暫
定交点の座標を設定し、演算子の現在値が基準値を超え
たか否かを判定し、基準値を超えるまで暫定交点の座標
を変更してダミードットを形成すると共に演算子の現在
値を更新して新たな値を現在値とする行程を繰り返し、
演算子の現在値が所定値を超えたとき１の方向に直交す
る方向の座標を終点の方向に１ドット変更して描画開始
ドットとする構成となっている。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、レーザプリンタやワー
プロ等の描画処理装置における直線描画処理の交点算出
方法に関する。

【０００２】

【従来の技術】図５は一般的な描画処理装置におけるＸ
座標およびＹ座標でドットの位置を表す描画可能領域を
示すものである。図５において、Ａ、Ｂ、ＣおよびＤの
範囲で示される領域は、ユーザにより任意に設定される
描画領域であり、Ｘ軸方向の境界線ｃｌｉｐｘ０および
ｃｌｉｐｘ１、Ｙ軸方向の境界線ｃｌｉｐｙ０およびｃ
ｌｉｐｙ１によって囲まれた領域である。この描画領域
に直線を描画する際に、直線の描画点すなわちドットの
座標を始点から終点までダミードットを発生させて、交
点の座標を算出しつつ描画を行うと、直線と境界線との
交点を正確に算出できる反面、直線が長い場合には交点
を算出するのに処理ステップ数すなわち処理時間が必要
以上に要していた。そこで、従来の直線描画処理の交点
算出方法では、数１に示すような数式により、交点の座
標（ｘｐ，ｙｐ）を算出して、これを描画開始ドットと
して描画を行っていた。

【数１】

【０００３】

【発明が解決しようとする課題】しかしながら上記従来
の直線描画処理の交点算出方法では、描画領域内にあり
ながら描画されないドットが生じていた。例えば図６に
示すように、描画する直線と描画領域Ａ点の境界線ｃｌ
ｉｐｙ０との真の交点は、数１で算出した交点（ｘｐ，
ｙｐ）の１つ前のドットであるにも拘らず、真の交点が
描画されず描画品質が劣化するという問題があった。

【０００４】本発明は上記従来の問題を解決するもので
あり、数式による交点算出でありながら、真の交点を描
画できる描画品質の高い優れた直線描画処理の交点算出
方法を提供することを目的とする。

【０００５】

【課題を解決するための手段】本発明は、上記目的を達
成するために、描画する直線の始点および終点の差分を
算出し、描画する直線の描画開始ドットを算出する演算
子の値を設定し、Ｘ軸方向又はＹ軸方向の内１の方向の
境界線の近傍でかつ描画領域外の暫定交点の座標を設定
し、演算子の現在値が基準値を超えたか否かを判定し、
基準値を超えるまで暫定交点の１の方向の座標を終点の
方向に１ドット分変更してダミードットを形成すると共
に演算子の現在値を更新して新たな値を現在値とする行
程を繰り返し、演算子の現在値が所定値を超えたとき１
の方向に直交する方向の座標を終点の方向に１ドット変
更して描画開始ドットとする構成となっている。

【０００６】

【作用】したがって本発明は、描画する直線と交差する
描画領域外の境界線の近傍で暫定交点を算出し、この暫
定交点から後にダミードットを形成して描画始ドットを
算出するので、処理ステップ数の低減と、メモリアクセ
ス数の低減を図ることができ、処理の高速化が得られる
と共に、ダミードットの形成により正確な描画開始ドッ
トを算出できるので、高い描画品質が得られるという効
果がある。

【０００７】

【実施例】以下、本発明の直線描画処理における交点算
出方法の一実施例を図面を参照して詳細に説明する。図
１は，描画する直線が図６の場合と同様に、Ｘ軸方向の
境界線ｃｌｉｐｙ０と交差する場合に、描画処理装置内
におけるコントローラ（図示せず）によって実行される
交点算出ルーチンのフローチャートである。

【０００８】まず、図１のステップＳ１で、描画領域外
でかつ境界線ｃｌｉｐｙ０の近傍の暫定交点（ｘｐ，ｙ
ｐ）を数２によって算出する。また、描画する直線の描
画開始ドットを算出する変数である演算子Ｅの初期値
（Ｅ＝−｜ｄｘ｜）を設定する。したがって初期値は基
準値である０より小さくＥ＜０となる。

【数２】

【０００９】次に、ステップＳ２において、暫定交点
（ｘｐ，ｙｐ）のＸ座標ｘｐを１ドット分Ｘ軸方向の終
点側に更新した座標（ｘｐ＋１，ｙｐ）にダミードット
を形成すると共に、演算子Ｅの現在値を数３により更新
した新たな値を現在値とする。

【数３】この演算子Ｅの現在値は、ステップＳ３で基準
値である「０」と比較され、演算子ＥがＥ≦０の場合に
は、ステップＳ２に移行して、ダミードットを形成する
と共に演算子Ｅの値を更新する。そして、ステップＳ３
において演算子ＥがＥ＞０となるまで、ステップＳ２お
よびステップＳ３の行程を繰り返し、Ｅ＞０となったと
きはステップＳ４に移行して、直前のダミードットのＹ
座標をＹ軸方向の終点側に１ドット分更新したダミード
ットを形成して、ステップＳ５でこの最新のダミードッ
トがｃｌｉｐｙ０内か、すなわち描画領域内か否かを判
定し、描画領域内でなければ、ステップＳ６において演
算子Ｅの現在値を数４により更新して、ステップＳ２に
移行してステップＳ５までの各ステップを実行する。そ
して、最新のダミードットが描画領域内であれば、交点
算出ルーチンを終了する。そして、この最新のダミード
ットを描画開始ドットとして直線の描画を開始する。

【数４】

【００１０】上記の例は、描画する直線がｃｌｉｐｙ０
と交差する場合の交点算出ルーチンであるが、ｃｌｉｐ
ｙ１又はｃｌｉｐｘ０若しくはｘ１と交差する場合に
は、数２は数５ないし数７となる。すなわち、数１ない
し数４における更新の方向等が異なるだけで、上記の例
と同様の交点算出方法で描画開始ドットを設定すること
が可能である。

【数５】

【数６】

【数７】

【００１１】次に、描画する直線の角度を算出して、こ
のような更新の方向を決定する一方法について図２およ
び図３を参照して説明する。図２は、描画する直線の始
点と終点のＸ軸方向の差分の絶対値｜ｄｘ｜が、Ｙ軸方
向の差分の絶対値｜ｄｙ｜よりも大きい場合、すなわち
直線とＸ軸とのなす角度の絶対値｜θ｜が４５度よりも
小さい場合を判定するものである。この場合には、描画
する直線はｃｌｉｐｙ０およびｃｌｉｐｙ１と交差する
ものとする。また、この場合には、始点から終点までＸ
座標の絶対ドット数は、Ｙ座標の絶対ドット数以上でな
ければならない。

【００１２】また、図３は、描画する直線の始点と終点
のＸ軸方向の差分の絶対値｜ｄｘ｜が、Ｙ軸方向の差分
の絶対値｜ｄｙ｜以下の場合、すなわち直線とＸ軸との
なす角度の絶対値｜θ｜が４５度以上の場合を判定する
ものである。この場合には、描画する直線はｃｌｉｐｘ
０およびｃｌｉｐｘ１と交差するものとする。また、こ
の場合には、始点から終点までＹ座標の絶対ドット数
は、Ｘ座標の絶対ドット数以上でなければならない。

【００１３】図４に、図１の交点算出ルーチンにより得
られた交点算出方法による直線の描画状態を示す。この
場合には、ｄｘ＝３４、ｄｙ＝６であるので、描画する
直線のＸ軸方向の絶対ドット数は、Ｙ軸方向の絶対ドッ
ト数よりも多く５倍のドット数となる。このドット数の
比は、ｄｘおよびｄｙのそれぞれの絶対値の比に基づい
て決定される。上記数２により算出された暫定交点の座
標（ｘｐ，ｙｐ）は、（ｘ０＋１７，ｃｌｉｐｙ０−
１）となり、演算子Ｅの初期値は−３４となる。

【００１４】次に、図１のステップＳ２で暫定交点の座
標からＸ軸方向に１ドット分更新した座標（ｘ０＋１
８，ｃｌｉｐｙ０−１）にダミードットを形成し、数３
により演算子Ｅを更新してＥ＝−２２とする。Ｅ＜０で
あるから、ステップＳ２に戻って再び座標（ｘ０＋１
９，ｃｌｉｐｙ０−１）にダミードットを形成し、更新
した演算子Ｅ＝−１０を算出する。ここではまだ演算子
Ｅが負であるので、座標（ｘ０＋２０，ｃｌｉｐｙ０−
１）にダミードットを形成して、演算子Ｅを更新してＥ
＝２とする。ここで初めて演算子Ｅが正となるので、ス
テップＳ４に移行してＹ軸方向に１ドット分更新した座
標（ｘｐ´，ｙｐ´）の点を求める。この点の座標（ｘ
０＋２０，ｃｌｉｐｙ０）は、ｃｌｉｐｙ０内すなわち
描画領域内にあるので、この点を真の交点すなわち描画
開ドットとする。

【００１５】このように、直線を描画する際に、暫定交
点を算出することにより、処理ステップ数およびメモリ
アクセス数を低減することができ、この暫定交点からダ
ミードットを形成することにより、描画領域の境界線と
直線との真の交点を算出して描画開始ドットとするの
で、描画品質を向上することができる。

【００１６】

【発明の効果】本発明によれば、上記実施例より明らか
なように、描画領域に直線を描画する際に、描画する直
線と交差する描画領域外の境界線の近傍で暫定交点を算
出し、この暫定交点から後にダミードットを生成して描
画開始ドットを算出するので、処理ステップ数の低減
と、メモリアクセス数の低減を図ることができ、処理の
高速化が得られると共に、ダミードットの生成により正
確な描画開始ドットを算出できるので、高い描画品質が
得られるという効果がある。

【図面の簡単な説明】

【図１】本発明の直線描画処理における交点算出方法の
一実施例の処理手順を示すフローチャートである。

【図２】本実施例の直線と描画領域の境界付近のＸ軸方
向の境界線との交差の特定条件の説明図である。

【図３】本実施例の直線と描画領域の境界付近のＹ軸方
向の境界線との交差の特定条件の説明図である。

【図４】 本実施例の描画領域のＸ軸方向の境界線と直
線が４５度以下の交点算出処理の説明図である。

【図５】描画処理装置におけるＸ座標およびＹ座標でド
ットの位置を表す描画可能領域を示す図である。

【図６】従来の描画領域のＸ軸方向の境界線と直線が４
５度以下の交点算出処理の説明図である。

【数１】 ｘｐ＝ｘ０＋ｄｘ／ｄｙ＊（ｃｌｉｐｙ０−ｙ０） ｙｐ＝ｃｌｉｐｙ０

【数２】ｘｐ＝ｘ０＋ｄｘ／ｄｙ＊｛（ｃｌｉｐｙ０−
ｙ０）−１｝ ｙｐ＝ｃｌｉｐｙ０−１

【数３】Ｅ＝Ｅ＋｜２＊ｄｙ｜

【数４】Ｅ＝Ｅ＋｜２＊ｄｘ｜

【数５】ｘｐ＝ｘ０＋ｄｘ／ｄｙ＊｛（ｃｌｉｐｙ１−
ｙ０）−１｝ ｙｐ＝ｃｌｉｐｙ１−１

【数６】ｘｐ＝ｃｌｉｐｘ０−１ ｙｐ＝ｘ０＋ｄｙ／ｄｘ＊｛（ｃｌｉｐｘ０−ｘ０）−
１｝

【数７】ｘｐ＝ｃｌｉｐｘ１−１ ｙｐ＝ｘ０＋ｄｙ／ｄｘ＊｛（ｃｌｉｐｘ１−ｘ０）−
１｝

Claims (2)

【特許請求の範囲】
1. 【請求項１】 Ｘ座標およびＹ座標でドットの位置を表
   す描画可能領域において、Ｘ軸およびＹ軸方向の境界線
   によって囲まれた描画領域に直線を描画する際に、前記
   境界線と描画する直線との交点を算出する方法であっ
   て、 描画する直線の始点および終点の差分を算出し、描画す
   る前記直線の描画開始ドットを算出する演算子の値を設
   定し、前記Ｘ軸方向又はＹ軸方向の内１の方向の境界線
   の近傍でかつ前記描画領域外の暫定交点の座標を設定
   し、前記演算子の現在値が基準値を超えたか否かを判定
   し、前記基準値を超えるまで前記暫定交点の前記１の方
   向の座標を前記終点の方向に１ドット分変更したダミー
   ドットを形成すると共に前記現在値を更新して新たな値
   を現在値とする行程を繰り返し、前記現在値が前記基準
   値を超えたとき前記１の方向に直交する方向の座標を前
   記終点の方向に１ドット変更して前記描画開始ドットと
   することを特徴とする直線描画処理における交点算出方
   法。
2. 【請求項２】 前記１の方向は、前記差分の前記Ｘ軸方
   向の絶対値が前記Ｙ軸方向の絶対値より大のときは前記
   Ｘ軸方向とし、前記Ｘ軸方向の絶対値が前記Ｙ軸方向の
   絶対値以下のときは前記Ｙ軸方向とすることを特徴とす
   る請求項１記載の直線描画処理における交点算出方法。