JPH01116889A - クリップ領域内における直線描画方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

［産業上の利用分野１ 本発明は、クリップ領域内に描画する図形の直線部分に
適用して好適な直線描画方式に関する。 〔従来の技術］・ 従来のクリップ領域内の直線描画方式として。 コーエン・サザーランドのクリップ領域描画アルゴリズ
ム（ｆｌ：ｏｈｅｎ−３ｕｔｈｅｒｌａｎｄ　［：Ｉｉ
ｐｐｉｎｇ　Ａｌｇｏｒｉｔｈｍ）か挙げられる。この
アルゴリズムは、特公昭５４−３３４９５号公報に記載
されたように、クリップ領域の描画開始点と終了点を２
分割法という方法で求め、その間を直線で結、ぶ描画処
理方式である。 このアルゴリズムては、まず、直線の始点と終点より直
線の中心点を求め、この中心点かクリップ領域の内か外
かを判定する。 １）、描画開始点を求める場合は、中心点が内ならば、
始点−中心点間の直線を次の２分割の対象直線とする。 外ならば、中心点を境にクリップ領域と交差する側の直
線を２分割の対象直線とする。 ２）、描画終了点を求める場合は、中心点か領域の内な
らば、中心点−終了点間の直線を次の２分割の対象直線
とする。外ならば、中心点を境にクリップ領域と交差す
る側の直線を２分割の対象直線とする。 次に、対象直線について、さらにその直線の中心点を求
め上記１）または２）の処理を繰り返して行い、最終的
に直線の２分割が不可能になった点を描画開始点または
終了点とする。そして、その２点間を結ぶことによって
クリップ領域内の直線描画を実現する。 このアルゴリズムについては、Ｊ−Ｄ・フオリー、Ａ・
ヴアン・タム共著「ファンダメンタルズ・才ブ・インタ
ラクティブ・コンピュータ・グラフィックス（Ｆｕｎｄ
ａｍｅｎｔａｌｓ　ｏｆ　Ｉｎｔｅｒａｃｔｉｖｅ　Ｃ
ｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ）　Ｊ第４章、第１４
６頁から第１５１頁においても論じられている。 ［発明か解決しようとする問題点１ 上記従来の方式でクリップ領域内に直線を描画する場合
、得られた描画開始点を始点に置き換え、また、終了点
を終点に置き換え、その間に発生する直線を描画するの
で、実際の始点から発生する直線とは誤差のために一致
しない。したかって、クリップ領域を拡大した場合には
、新たに拡大された領域の直線を付加しなければならな
いが、従来の方式で描画した場合は、連続したきれいな
直線にならないという問題があった。 本発明の目的は、クリップ領域外の無駄な計算処理を行
わず、描画開始点座標の算出および座標補正処理を行う
ことによって、クリップ領域内の直線描画速度を向上し
、連続性のあるきれいな直線を描画する方式を提供する
ことにある。 ［問題点を解決するための手段］ 上記目的を達成するために、本発明は、ラスタディスプ
レイの直線描画処理において。 直線の始終点および矩形クリップ領域に応じてクリップ
処理が発生するとき、 １記直線と上記クリップ領域との交点の１ピクセル外側
にある直前のピクセルの座標を算出し、該直前のピクセ
ル座標から直線描画アルゴリズムの誤差値計算を行い、 該誤差値および上記直前のピクセルの座標から上記クリ
ップ領域内の直線の座標点を算出するようにしたもので
ある。 本発明の一実施態様としては、上記直線描画アルゴリズ
ムとしてプレセンハム法を用い、与えられた直線がクリ
ップ領域の上側から進入する場合を考えると、直線の始
点座標を（ｘ、、ｙ、）として、上記直前ピクセルの座
標（Ｘｏ＋ｃｘｌ　、ｄｒａｗｙ−１）を、２・ｄｙ （ｄｘ、ｄｙはそれぞれ始終点間のＸ軸、Ｙ軸距離）に
基いて計算し、上記誤差値ｅを、 ｅ＋＝２・ｄｙ−ｄｘ＋（ｄｒａｗｙ−Ｙｏ−１）・２
・ｄｘ−ｃｘｌ・２・ｄｙで計算することができる。 本発明の他の実施態様としては、上記直線描画アルゴリ
ズムとしてプレセンハム法を用い、与えられた直線がク
リ・ンブ領域の左側から進入する場合を考えると、直線
の始点座標を（Ｘｏ、Ｙｏ）として、上記直前ピクセル
の座標（Ｙｏ＋ｃｙ１、ｄｒａｗｘ−１）を、 ２・ｄｘ （ｄｘ、ｄｙはそれぞれ始終点間のＸ軸、Ｙ軸距Ｉｔ）
に基いて計算し、上記誤差値ｅを、 ｅ−２−ｄｙ−ｄｘ＋（ｄｒａｗｘ−Ｘｏ−１）−２−
ｄｙ−ｃｙｌａ２−ｄｙで計算するものが考えられる。 その他、与えられた直線がクリップ領域の右側あるいは
下側から進入する場合についても、本発明は適用可能で
ある。

【作用］ 従来の方式における描画開始点座標の計算式で得られる
値は整数値ではない。また、何らかの方法で整数化して
も当然誤差が生じ、始点から発生した直線とは一致しな
い場合が考えられる。 そこで、計算式によって、実際の描画開始点の直前のピ
クセルの座標を求め、例えばプレゼンハムの直線発生ア
ルゴリズムの座標更新で用いる誤差値をその座標につい
て算出する。そして、この直前の座標から上記アルゴリ
ズムを起動し、描画開始点が求められた時点から、描画
処理を開始し、終了点まで描画処理を行う。プレゼンハ
ムの直線発生アルゴリズムの詳細については、前記文献
「ファンダメンタルズ・オブ・インタラクティブ・コン
ピュータ・グラフィックス」の第１１章を参照されたい
。 具体的には１本発明は、プレゼンハムの直線発生ノアル
ゴリズムを用いて、クリップ領域と直線との交点の直前
のピクセルの座標値を求めるための計算式と、その座標
値における座標更新方向を定めるための変数（誤差値）
を算出する手法を創案したものである。プレゼンハムの
直線発生のアルゴリズムにおける座標更新は誤差値（ｅ
）の値によって更新の方向を定める手法である。誤差値
（ｅ）の初期値をｅ　＝　２・ｄｙ−ｄｘとすると、ｅ
≦０ならば直線座標をＸ方向に１ピクセル更新し、ｅ値
をｅ　＝ｅ◆２・ｄｙに更新する。 ｅ）Ｏならば直線座標をＸおよびＸ方向に１ピクセル更
新し、ｅ値をｅ　＝　ｅ＊　２・ｄｙ−２・ｄｘに更新
し、この処理を終点まで繰り返すという手法である。 そこで、まず、発生した直線上の任意の座標点（Ｘｍ、
Ｙｎ）のｅ値はつぎのように計算できる。 ｅ　＝　２・ｄｙ−ｄｘ＋（Ｘｍ・２◆ｄｙ）−（Ｙｍ
・２・ｄｘ）　・・・（１）次に、クリップ領域との交
点座標を（Ｘｍ、Ｙｎ）とし、Ｙｎが与えられていると
き、（１）式は次のように変形することができる。 ｅｇＯとすると、 ２・ｄｙ この（２）式で得られた座標値は、Ｃ・０と仮定して算
出したものであり、実際のクリップ領域との交点、つま
り描画開始点である場合は少ない。しかし、算出した座
標値は必ず、プレゼンハムのアルゴリズムで発生した直
線上に存在する。 そこで、与えられたクリップ座標の（Ｙｎ−１）におけ
るＸ座標を（２）式によって算出することによりクリッ
プ座標の１ピクセル外側のピクセルの座標値とｅ値とが
求められる。そして、その座標値から実際に直線を発生
させ、Ｘ方向の座標かＹｎに代わった点を描画開始点と
することにより、クリップ領域の交点を求めることが実
現できる。 このようにして求めた交点はプレゼンハムのアルゴリズ
ムで発生した直線上に存在するので、クリップ領域を拡
大して直線を付加した場合にも連続したきれいな直線が
得られる。　　□〔実施例１ 以下、本発明の一実施例を添付図面に基き、詳細に説明
する。 第５図は、本発明を適用するシステムの構成図である。 ５０１はプリンタ、５０２はプリンタ・キーボード制御
部、５０３はワークメモリ、５０４はビットマツププロ
セッサ（ＢＭＰ：１２）、５０５はマイクロプログラム
用ＲＡＭ、５０６はビデオピクセル制御部、５０７はビ
デオＲＡＭ、５０８はＣＲＴデイスプレィである。。 本発明の方式は、線図形描画処理プログラムとして、ビ
ットマツププロセッサ５０４内のマイクロプログラムに
含まれる。 第１図は、本発明に係るクリップ領域内における直線描
画方式を実現するための処理のフローチャートである。 ステップ１０１ては、クリップ領域外の直線描画の計算
処理を除くために、クリップ領域の描画開始点の直前の
ピクセルの座標を計算する。計算方法は、クリップ領域
に進入する位置によって異なる。まず初めに、第２図に
示すような場合を例として説明する。 第２図は、（ｘ、　、ｙ、）を始点とする直線がクリッ
プ領域の上部から進入し、右側へ抜は出るような場合で
ある。 描画開始点を（×１．Ｙ、；）　、描画開始点の直前の
ピクセルの座標を（ｘ−＋　、ｙｎ−ｔ）とする。なお
、始点（Ｘｏ＝Ｙｏ）から上記直前のピクセルまでのＸ
距離をｃｘｌとする。（ｘ−ｉ、ｙ−ｔ）は次のように
求める。 ｙｎ−１−ｄｒａｗｙ　−１ ２φｄｙ （ｄｘ、ｄｙはそれぞれ始終点間のＸ軸、Ｙ軸距離）（
３）式の余りをＡとする。 ｃｘｌ≧０の場合、 Ａ−０ならばｃｘｌ　＝　ｃｘｌ Ａ）Ｏならばｃｘｌ　−ｃｘｌ　＋　１ｃｘｌ　（Ｏの
場合、　ＣＸＩ　！　０よって、次式よりＸ＋ａ−１が
求まる。 Ｘｓ−＋　＝　ＸＯ＋　（×１ 次に、ステップ１０２では、ステップ１０１で得られた
座標（Ｘ−ｔ、’／１１−＋）の誤差値ｅを次式を用い
て算出する。 ｅｓ２・ｄｙ−ｄｘ＋（ｄｒａｗｙ−Ｙ、−１）・２・
ｄｘ−ｃｘｌ・２・ｄｙ次に、ステップ１０３では、実
際の描画開始点座標を求めるために、誤差値ｅおよび描
画点座標の更新を行うもので、詳しくは第４図を用いて
説明する。 第４図のステップ４０１において、第１図のステップ１
０２で得られた誤差値の正負の判定を行う。 負の場合は、ステップ４０２においてＸ方向に座標を更
新し、ステップ４０３で誤差値ｅを更新する。 ステップ４０１．４０３を、誤差値ｅが０より大きくな
るまで繰り返し行う、すなわち、座標がｙ方向に更新さ
れるまで第４図の処理を行う、そして、ｙ方向に更新さ
れたときの座標が描画開始点座標となる。 描画ピクセル数ｓ　ｃｘｌ　＋ｄｒａｗｘ　−Ｘ。 ステップ１０５から１０９までは、プレゼンハムのアル
ゴリズムによる直線の描画処理である。ま゛ず、ステッ
プ１０５では、ステップ１０３で得られた描画開始点座
標に描画処理を行う、そして、ステップ１０６では、ス
テップ１０２で算出した誤差値を判断して誤差値：ｅ〉
０ならば、ステップ１０７において、×およびＸ座標を
１更新し、誤差値ｅを次のように更新する。 ｅ　＝　ｅ＋　２・ｄｙ−２・ｄｘ 一方、誤差値ｅ≦０ならば、ステップ１０８においてＸ
座標のみを１更新し、誤差値ｅを次のように更新する。 ｅ　ｍｅ　＋２１１ｄｙ 次にステップ１０９では、描画ピクセル数の判定を行い
、０でなければ再びステップ１０５へ戻り、更新された
誤差値および描画点座標を用いて、描画処理を行う、そ
して、ステップ１０５〜１０９の処理を描画ピクセル数
−ＩＯになるまで、繰り返すことによって、クリップ領
域内の描画処理を実現するものである。 以上、第２図を例にして説明したが、次に第３図のクリ
ップ領域の左側から進入する場合を例に、計算式だけを
挙げておく、尚、処理の流れは、前述と同様、第１図に
準するものである。 ステップ１０１における計算式は次のようになる。 Ｘ、、　ｍｄｒａｗｘ　−１ ＩＩｄｘ （４）式の余りをＢとする。 ｃｙｌ≧０の場合、 Ｂ−Ｑならばｃｙｌ　−ｃｙｌ Ｂ）Ｏならばｃｙｌ　−ｚｙｌ　＋　１ｃｙｌ　（０の
場合、ｃｙｌ　ｍ　Ｏ よって、次式よりＹｎ−１が求まる。 Ｙｎ−＋　−Ｙｏ　＋　ｃｙｌ 次に、ステップ１０２における計算式は次のようになる
。 ｅ＝２・ｄｙ−ｄｘ＋（ｄｒａｗｘ−Ｘｎ−１）・２・
ｄｙ−ｃｙｌ・２・ｄｘ【発明の効果】 以上、本発明によれば、クリップ領域内の描画処理につ
いては直線の座標値の計算処理を、クリップ領域内の座
標算出処理しか行わないので、従来の直線の始点から終
点までの全ての座標計算を行りていた描画処理に比べて
、処理速度が向上する。かつ、直線とクリップ領域との
交点の直前のピクセルから直線描画アルゴリズムの誤差
値計算を行ってクリップ領域内の直前の座標点を算出す
るようにしたので、クリップ領域を拡大した場合にも、
連続性のあるきれいな直線を描画することができる。

【図面の簡単な説明】

第１図は本発明の方式を実現するための処理手順を示し
たフローチャート、第２図、第３図はクリップ領域内の
直線描画の例を示した説明図、第４図は第１図のステッ
プ１０３を詳しく示したフローチャート、第５図は本発
明を適用するシステムの構成を示すブロック図である。 出願人　株式会社　日　立製作所 株式会社　日立マイクロソフト ウェアシステムズ 代理人　弁理士　富　１）和　子 第１図 第４図 第５図

Claims (1)

1. 【特許請求の範囲】 １、ラスタディスプレイの直線描画処理において、直線
   の始終点および矩形クリップ領域に応じてクリップ処理
   が発生するとき、 上記直線と上記クリップ領域との交点の１ピクセル外側
   にある直前のピクセルの座標を算出し、 該直前のピクセル座標から直線描画アルゴリズムの誤差
   値計算を行い、 該誤差値および上記直前のピクセルの座標から上記クリ
   ップ領域内の直線の座標点を算出することを特徴とする
   クリップ領域内における直線描画方式。 ２、上記直線描画アルゴリズムとして、ブレゼンハム（
   Ｂｒｅｓｅｎｈａｍ）法を用い、与えられた直線がクリ
   ップ領域の上側から進入する場合の直線の始点座標を（
   Ｘｏ、Ｙｏ）として、上記直前ピクセルの座標（Ｘｏ＋
   ｃｘ１、ｄｒａｗｙ−１）を、ｃｘ１＝［２・ｄｙ−ｄ
   ｘ＋（ｄｒａｗｙ−Ｙｏ−１）・２・ｄｘ／２・ｄｙ］
   （ｄｘ、ｄｙはそれぞれ始終点間のＸ軸、Ｙ軸距離）に
   基いて計算し、上記誤差値ｅを、 ｅ＝２・ｄｙ−ｄｘ＋（ｄｒａｗｙ−Ｙｏ−１）・２・
   ｄｘ−ｃｘ１・２・ｄｙで計算する特許請求の範囲第１
   項記載のクリップ領域内における直線描画方式。 ３、上記直線描画アルゴリズムとして、ブレゼンハム法
   を用い、与えられた直線がクリップ領域の左側から進入
   する場合の直線の始点座標を（Ｘｏ、Ｙｏ）として、上
   記直前ピクセルの座標（ｄｒａｗｘ−１、Ｙｏ＋ｃｙ１
   ）を、 ｃｙ１＝［２・ｄｙ−ｄｘ＋（ｄｒａｗｘ−Ｘｏ−１）
   ・２・ｄｙ／２・ｄｘ］（ｄｘ、ｄｙはそれぞれ始終点
   間のＸ軸、Ｙ軸距離）に基いて計算し、上記誤差値ｅを
   、 ｅ＝２・ｄｙ−ｄｘ＋（ｄｒａｗｘ−Ｘｏ−１）・２・
   ｄｙ−ｃｙ１・２・ｄｘで計算する特許請求の範囲第１
   項記載のクリップ領域内における直線描画方式。