JPH0412875B2 - - Google Patents

Description

【発明の詳細な説明】 Ａ 産業上の利用分野 この発明は情報処理システムに関するものであ
り、より詳細にいえば表示装置上に図形の線を描
くための方法に関するものである。

Ｂ 従来の技術 従来の技術において、グラフイツク表示システ
ムに太い線を描くには、ブレセンハム
（Bresenham）生成線をスタツクしていた。

Ｃ 発明が解決しようとする問題点 しかしながら、この従来技術の方法には、次の
ような難点がある。

スタツクした線の始点のＸ値が前に描いた線か
らずれると、太い線に穴が生じる。この従来技術
の手法で線を追加して引く場合、これらの穴を確
実にカバーするには、線を反復して引く必要があ
るため、性能が劣化する。さらに、ブレセンハム
の手法で線を追加して引くことは一般に、幾つか
の画素を複数回描くことを生じ、これは描かれて
いる太い線が背景に重なつているのか、あるいは
他の線や塗り漬された領域などの背景でない部分
に重なつているのかを決定することを、さらに困
難とする。

したがつて、この発明の目的は、グラフイツク
表示システムにおいて太い線を効率よく描くこと
にある。

Ｄ 問題点を解決するための手段 本発明は、Ｘ座標値またはＹ座標値の何れか一
方（以下、この一方の座標値を第１座標値と呼
ぶ）は単純に１ずつ変化するけれども、他方の座
標値（以下、第２座標値と呼ぶ）は等しくなるよ
うに配置された複数の画素をもつて画素サブパタ
ーンを構成し、該画素サブパターンを、画素の第
１座標値は単純に１ずつ変化し、かつ隣り合う画
素サブパターンの第２座標値の差は１となるよう
に反復して画素パターンを構成し、該画素パター
ンをもつて１本の線を描き、さらに該画素パター
ンの各画素の位置を等しくＸ座標値またはＹ座標
値にに関してプラスまたはマイナス１だけ異なら
せて線を描くことを繰り返すことによつて、１本
の太い線をグラフイツク表示装置に描く線描画方
法において、 上記繰り返しにおいてこれから描こうとする新
しい線が、上記画素パターンの各画素の第１座標
値を直前に描き終わつた古い線のそれとはプラス
またはマイナス１だけ変化させて描かれるもので
あるか否かを判断し、 上記判断結果が肯定的であるならば、上記画素
パターンを上記新しい線を描くための位置に配す
るだけでなく、上記画素パターンを構成する画素
サブパターンを上記第１座標値の変化分の符号に
相当する向きとは逆の向きに１画素分延長した位
置に画素を追加して、上記新しい線を描くことを
特徴とする。

Ｅ 実施例 この発明の実施例は、第１座標値がＸ軸に沿つ
ており、生成される付加的な画素値が位置Ｘ＋
１、Ｙにある、太い線をグラフイツク表示システ
ムに描くものである。

この発明の実施例は、描かれる最初の線が太い
線の底部の線または最も小さいＹの値の線であ
り、次の線が太い線を生成するために描かれた以
前の線よりも大きなＹ値を持つている太い線を上
述のようにして、グラフイツク表示システムに描
くものである。

この発明の実施例は、描かれる最初の線が太い
線の頂部の線または最も大きいＹの値の線であ
り、描かれる次の線が次の線の始点に関して少な
いＹの値を有している太い線を上述のようにし
て、グラフイツク表示システムに描くものであ
る。

グラフイツク表示システムにおいては、単一の
画素よりも幅が広い線（太い線）をラスタ・グラ
フイツク表示装置に描くことができる機能が必要
である。一般に、太い線はこれまで、ブレセンハ
ム線生成アルゴリズムによつて生成された線をス
タツクして、描かれている。第４図に示したこの
従来技術の方法は、スタツク線の起点のＸ値が以
前に描かれた線から左へずれた場合に、一般に、
太い線に穴を生じるものである。図中描かれた最
初の線はｘで、太い線の第２の線は．で、第３の
線は＋で、第４の線はｏで示されており、また太
い線内の穴は＊で示されている。これらの穴をカ
バーしなければならない場合には、追加の線を描
かなければならないので、システムの性能が低下
する。

この発明の実施例は改善されたベクトル生成装
置を用いるものであつて、このベクトル生成装置
はＸまたはＹなどの起点座標値が、太い線の以前
の線の起点座標値よりも少なくなつた（第１オク
タントで）場合に、画素を追加して描いて、穴を
埋める必要があると判断するものである。

第３図は、この発明による方法によつて描かれ
た太い線を示すものであつて、図中ｘは太い線の
最初の線として描かれた画素を表し、．は第２の
線として描かれたピクセルを表し、＋は第３の線
として描かれた画素を表し、ｏは第４の線として
描かれたピクセルを表す。

ベクトル生成装置は第１図の状態図に示した他
の状態を有しており、線Ｙの値がＹ＋１に増加
し、位置Ｘ＋１、Ｙにある穴をカバーする場合
に、点Ｘ＋１、ＹおよびＸ＋１、Ｙ＋１をプロツ
トする。

第２図には、この発明を実施するのに使用する
ベクトル生成装置が示されている。

第２図に示したベクトル生成装置１００の中心
には、マルチプレクサ１１２および１１４のそれ
ぞれに対するバス入力１０６（左）および１０８
（右）が設けられ、かつ出力１１６および作動時
に和＜０をしめすＮにおける符号ビツト120を有
するALU１１０が設けられている。

△Ｘおよび△Ｙという値はベクトル生成装置へ
のバス１０２における入力であり、このバス１０
２はマルチプレクサ１２２に第１入力を与える。
最初の時間間隔において、マルチプレクサ１２２
はIBM５０８０などの表示制御装置（図示せず）
の順序論理によつて、割込可能となされるので、
バス１０２上のデータが絶対値論理装置１２４を
介して、供給される。絶対値論理装置１２４は任
意の時期にバス１０２に現われる△Ｘまたは△Ｙ
のいずれかの絶対値を決定する。マルチプレクサ
１２２の符号ビツト出力も、Ｘ符号フリツプ・フ
ロツプ１２６およびＹ符号フリツプ・フロツプ１
２８の入力へ供給される。マルチプレクサ１２２
からの符号ビツト出力によつて付勢される適切な
符号フリツプ・フロツプが、図示されていないシ
ーケンサによつて割込可能にされる。絶対値論理
装置１２４の出力は、バス１３０によつて△Ｘレ
ジスタ１３２、△Ｙレジスタ１３４および左側の
ALUマルチプレクサ１１２の入力に送られる。

次に、△Ｙの値がバス１０２に置かれ、マルチ
プレクサ１２２を介して送られる。マルチプレク
サ１２２において、符号ビツトが識別され、Ｙ符
号フリツプ・フロツプ１２８を付勢するのに使用
される。次いで、△Ｙの大きさが絶対値論理１２
４によつて決定され、△Ｙの絶対値がＹレジスタ
１３４にロードされる。

△Ｘレジスタ１３２からの△Ｘの出力は、バス
１３６によつてマルチプレクサ１４０に送られ、
ハードウエア的に配線されている２倍乗算器１４
４へ送られる。△Ｙレジスタ１３４の△Ｙ出力の
大きさは、バス１３８によつてマルチプレクサ１
４０の第２の入力へ送られ、ハードウエア的に配
線された２倍乗算器１４４へ送られる。

最初のバスの間、乗算器１４２の出力は２△Ｘ
を表し、乗算器１４４の出力は２△Ｙを表す。

ベクトル生成装置のセツトアツプに、フリツ
プ・フロツプ１５０のＹよりも小さいＸが初期設
定されるので、Ｙ出力ライン１５８未満のＸはゼ
ロであり、これは△Ｘが△Ｙ以上であるとみなし
たものである。Ｙライン１５８未満のＸはスワツ
プ論理装置１４６およびマルチプレクサ１４０を
制御する。初期状態において、ライン１５８がゼ
ロに等しいと、スワツプは何ら行われず、それ
故、乗算器１４２の出力は、ALU１１０の右側
のマルチプレクサであるマルチプレクサ１１４の
最も左側の入力に送られ、乗算器１４４の出力は
スワツプ論理装置１４６を介して、ALU１１０
の左側のマルチプレクサであるマルチプレクサ１
１２の右側の入力へ送られる。

同様に、△Ｘの絶対値をこの時点で表す、バス
１５２上のマルチプレクサ１４０の出力は、マル
チプレクサ１１４の第２の入力へ、および繰返し
カウンタ１５４の入力へ送られる。ALU１１０
が行う最初の計算は、２△Ｙ−２△Ｘという演算
である。この減算はグラフイツク処理装置シーケ
ンサからの、ALU制御ライン１０４によつて制
御される。出力バス１１６上のALUの出力は、
RBレジスタ１５６に入力され、このレジスタは
これで２△Ｙ−２△Ｘという量を記憶する。

また、この計算の結果として、ライン１２０に
現われる結果のサイン・ビツトがＸ＜Ｙフリツ
プ・フロツプ１５０に記憶され、このフリツプ・
フロツプは活動している制御ライン１５８を、ス
ワツプ論理装置１４６およびマルチプレクサ１４
０に与える。

ライン１５８はマルチプレクサ１１２および１
１４のそれぞれへの入力を制御するので、ライン
１５８が活動している場合に、２△Ｘがマルチプ
レクサ１１２へ、２△Ｙがマルチプレクサ１１４
へ送られ、２△Ｙ−２△Ｘではなく、２△Ｘ−２
△Ｙという実際の計算が行われる。

もちろん、ALUはライン１０６上に存在する
入力から、ライン１０８上に存在する入力を引
き、希望する結果を得るだけである。

次のサイクルにおいて、ライン１０６に現われ
る２△ＹがALU１１０の左側に送られ、またマ
ルチプレクサ１１４を介してマルチプレクサ１４
０から送られてきた△Ｘが、グラフイツク処理装
置シーケンサの制御により、ライン１０８上を
ALU１１０の右側へ送られるので、バス１１６
上の出力は２△Ｙ−△Ｘという量になる。

この量はRCレジスタ１６２に送られ、記憶さ
れる。

RCレジスタ１６２の出力１６４はマルチプレ
クサ１１４の３番目の入力であつて、ALU１１
０の右側へ送られる。

ベクトル生成装置のセツトアツプがこの時点で
完了する。ベクトル生成装置のセツトアツプ時
に、ALU１１０は設定の２つのサイクルの各々
において、減算のみを行う。

動 作 第１図および第２図を参照して、スタツクに穴
のない太い線を生成し、表示することを説明す
る。

システムは状態０、すなわちアイドル状態から
スタートする。

セツトアツプの完了後、システムは第１図の右
側の円によつて表される状態１に復帰する。状態
１において、RCレジスタ１６２には量２△Ｙ−
△Ｘが記憶されており、これはエラー項と呼ばれ
る。

太い線を描く場合、数本の構成線が「正規」モ
ードまたはブレセンハム・モード（すなわち、点
Ｘ＋１、Ｙに画素を追加しないモード）で、描か
れる。第３図に示した第１、第２、および第４の
線が「正規モード」で描かれる。正規モードにお
いて、太線モード信号WLは不作動、すなわち０
である。

ライン１２０、すなわちALU１１０からの
（合計＜０）信号がテストされる。和が０未満で
あり、信号が作動していると、システムは第１図
の中央の状態２に移行する。RCレジスタ１６２
の内容、すなわち２△Ｙ−△Ｘが、２△Ｙに加え
られ、RCレジスタ１６２に再度記憶される。Ｘ
の値が増加し、次の画素位置に移動し、繰返しカ
ウンタ１５４は１減少する。現行位置へのピクセ
ル書込信号WPIXが発生し、画素を現在のＸ、Ｙ
座標位置に描く。

「正規」モードで線を描くには、ブレセンハ
ム・アルゴリズムを使用するが、このアルゴリズ
ムはフオリイおよびバン・ダム（Foley and
VanDam）の「対話式コンピユータ・グラフイ
ツクの基礎（Fudamentals of Interactive
Computer Graphics）」、アデイソン・ウエスレ
ー出版社（Addison、Wesely Publishing
Company）、1982年、p.435に記載されている。
「和＜０」信号はＹ軸方向の増分なしに描かれる
線に沿つたＸ軸方向の増分を物理的に表す。それ
故、第３図および第４図において、文字Ｘで表さ
れる最初の線を描く場合、システムは状態１から
状態２に変り、最初のＸが描かれる。

繰返しカウンタが０でなく、ライン１２０の
「合計＜０」が作動していて、Ｘ軸に沿つて線を
描くことを示している限り、システムは状態２を
ループする。第３図および第４図に示した例にお
いて、システムが状態２を維持している間に、Ｘ
軸に沿つて２個のピクセルが描かれてから、Ｙ方
向への増分が生じる。

次の画素位置を検討する場合、Ｙ軸に沿つた増
分を物理的に表す「和＜０」信号がオフにされ
る。第３図の一番下の線が「正規」のブレセンハ
ム・モードで描かれ、かつ繰返しカウンタが０に
等しくないのであるから、Ｘに増分のある増分Ｙ
が、システムを状態２から状態４に変え、この状
態でＸが増加し、Ｙが増加し、繰返しカウンタが
１減少し、かつ信号WPIXが発生することによつ
て、画素が描かれる。また、RCレジスタ１６２
に記憶されているエラー項が、量２△Ｙ−２△Ｘ
の新しい値を加えることによつて更新される。描
かれる次の画素がＸ軸での変化だけを表し、Ｙ軸
での変化を表すものではないので、「和＜０」信
号がオンとなり、システムは状態４から状態２へ
戻る（繰返しカウンタが依然０以上であると仮定
した場合）。状態２において、次のＸ軸ピクセル
が描かれ、システムは上述のように、状態２にな
つたり、状態４になつたりすることを継続し、太
い線の特徴を持つていない線を、正規のブレセン
ハム・モードで描く。すなわち、これらの線は位
置Ｘ＋１、Ｙで画素を追加して描き、正規のブレ
センハム・アルゴリズムで線に残る穴を埋めなけ
ればならないような線ではない。

正規モードで描かれる２番目以降のすべての線
は、最初の線と同じ状態の順序で描かれることに
なる。

＋を付けた線３などの「太線モードの線」を描
く場合、システムは活動している信号WLが存在
し、かつ合計＜０信号が不作動であることによつ
てＹ座標に増分が存在することによつて太線モー
ドと判断し、繰返しカウンタが０以上であると仮
定して、状態３に変り、この状態において、Ｘの
値が増加し、信号WPIXが発生して、正規モード
で穴が生じる可能性のある位置、Ｘ＋１、Ｙに画
素を描く。システムは常に状態３から状態５に変
り、この状態において、RCレジスタ１６２に記
憶されているエラー項が量２△Ｘ−２△Ｙによつ
て更新され、Ｙ座標値が増加し、繰返しカウンタ
が減少し、かつ信号WPIXが発生することによつ
て、他の画素が描かれる。システムが状態５にあ
る間に、Ｙ座標値がさらに増加すると、制御が状
態３に戻され、この状態において、Ｘの値が増加
して、他の画素が描かれる。次の移動がＸ軸に沿
つて行われ、Ｙに増分がない場合、合計＜０信号
が活動状態となり、システムは制御を状態２に戻
す。システムは正規モードにおいては状態２から
状態５へのループを続け、また「太線モード」に
おいては、太い線の構成線がすべて描かれるま
で、状態２、３、５をループし、構成線がすべて
描かれた辞典で、繰返しカウンタは０となり、シ
ステムは状態０、すなわちアイドル状態に変わ
る。

それ故、２つの制御状態、状態３および状態５
を追加することにより、穴のない太い線を、表示
装置の他の要素との干渉のない効率的な態様で描
くことが可能となる。

Ｆ 発明の効果 本発明によれば、Ｘ座標値またはＹ座標値の何
れか一方（以下、この一方の座標値を第１座標値
と呼ぶ）は単純に１ずつ変化するけれども、他方
の座標値（以下、第２座標値と呼ぶ）は等しくな
るように配置された複数の画素をもつて画素サブ
パターンを構成し、該画素サブパターンを、画素
の第１座標値は単純に１ずつ変化し、かつ隣り合
う画素サブパターンの第２座標値の差は１となる
ように反復して画素パターンを構成し、該画素パ
ターンをもつて１本の線を描き、さらに該画素パ
ターンの各画素の位置を等しくＸ座標値またはＹ
座標値にに関してプラスまたはマイナス１だけ異
ならせて線を描くことを繰り返すことによつて、
１本の太い線をグラフイツク表示装置に描く線描
画方法において、処理ステツプの増加を最小限に
とどめつつ、従来生じていた穴をなくすことがで
きるという優れた効果が得られる。

【図面の簡単な説明】

第１図は、本発明による線描画方法をベクトル
生成装置を使用して実現する場合における該生装
置の動作状態を示す状態図、第２図は、本発明に
よる方法を実施するのに使用されるベクトル生成
装置の一例を示すブロツク図、第３図は、本発明
により描かれた太い線の一例を示す説明図、第４
図は、従来技術により描かれた太い線の一例を示
す説明図である。 １００……ベクトル生成装置、１１０……
ALU、１２４……絶対値論理装置、１２６……
Ｘ符号レジスタ、１２８……Ｙ符号レジスタ、１
３２……△Ｘレジスタ、１３４……△Ｙレジス
タ、１４２，１４４……２倍乗算器、１４６……
スワツプ論理装置。

Claims (1)

1. 【特許請求の範囲】 １ Ｘ座標値またはＹ座標値の何れか一方（以
   下、この一方の座標値を第１座標値と呼ぶ）は単
   純に１ずつ変化するけれども、他方の座標値（以
   下、第２座標値と呼ぶ）は等しくなるように配置
   された複数の画素をもつて画素サブパターンを構
   成し、該画素サブパターンを、画素の第１座標値
   は単純に１ずつ変化し、かつ隣り合う画素サブパ
   ターンの第２座標値の差は１となるように反復し
   て画素パターンを構成し、該画素パターンをもつ
   て１本の線を描き、さらに該画素パターンの各画
   素の位置を等しくＸ座標値またはＹ座標値にに関
   してプラスまたはマイナス１だけ異ならせて線を
   描くことを繰り返すことによつて、１本の太い線
   をグラフイツク表示装置に描く線描画方法におい
   て、 上記繰り返しにおいてこれから描こうとする新
   しい線が、上記画素パターンの各画素の第１座標
   値を直前に描き終わつた古い線のそれとはプラス
   またはマイナス１だけ変化させて描かれるもので
   あるか否かを判断し、 上記判断結果が肯定的であるならば、上記画素
   パターンを上記新しい線を描くための位置に配す
   るだけでなく、上記画素パターンを構成する画素
   サブパターンを上記第１座標値の変化分の符号に
   相当する向きとは逆の向きに１画素分延長した位
   置に画素を追加して、上記新しい線を描く ことを特徴とする線描画方法。