JPH06348855A

JPH06348855A - 描画プロセッサとその直線発生並列処理方法及びグラフィックボード，ｃａｄシステム

Info

Publication number: JPH06348855A
Application number: JP13755193A
Authority: JP
Inventors: Makoto Fujita; 良藤田; Kazuhisa Takami; 和久高見; Mitsuru Soga; 満曽我; Koji Ozawa; 幸次小沢; Takaharu Morishige; 隆春森重
Original assignee: Hitachi Microcomputer System Ltd; Hitachi Ltd
Current assignee: Hitachi Microcomputer System Ltd; Hitachi Ltd
Priority date: 1993-06-08
Filing date: 1993-06-08
Publication date: 1994-12-22

Abstract

(57)【要約】【目的】複数の描画プロセッサによって並列に直線を
描画する際に、直線を始点と終点で与え、内部に除算器
を設けないで処理し、直線描画の高速化を図る。【構成】直線の始点と終点の座標から、傾きを分数の
形で求め、始点から傾きを順次加算しながら、直線上の
画素の座標を求める。この時、傾きの分子の値を２倍，
４倍，８倍等して加算器８２で加算し、加算器８３で分
母の値を引き算し、２画素先，４画素先，、８画素先の
座標を求める。直線を始点と終点で与えるので、上位プ
ロセッサの負担が少なくなる。また、複数の描画プロセ
ッサで並列に画素を生成するために高速処理ができ、描
画プロセッサの内部に除算器を設ける必要がないためハ
ードウェア量も小さくなる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はワークステーションのデ
ィスプレイ画面上に直線図形を生成する方法に係り、特
に、複数のプロセッサを備える描画プロセッサにより直
線の描画処理を並列処理で高速に行うのに好適な直線発
生並列処理方法等に関する。

【０００２】

【従来の技術】従来の直線を描画する装置は、大きく２
種類に分けられる。１つは、例えば特公平２−４１７９
０号公報に記載されているように、真の直線と、画像メ
モリにおける整数格子の座標系とのずれを分数で表し、
分数計算のみで与えられた直線に最も近い画像メモリ上
の画素を生成する方式（ブレゼンハムのアルゴリズム）
である。２つ目は、例えば特開平３−３６６７６号公報
に記載されているように、直線の傾きを小数で与え、始
点座標にその傾きの値を繰返し加算していくことで、直
線上の画素を発生する方式である。

【０００３】一方、複数のプロセッサにより直線上の画
素を並列に生成するの方式としては、特開平１−２０７
８８６号がある。この従来技術では、プロセッサの数だ
け直線の傾きを整数倍し、その値を直線の始点に加算す
ることで必要な画素だけを生成している。

【０００４】

【発明が解決しようとする課題】上記の複数のプロセッ
サによって並列に直線発生を行わせようとする従来技術
は、直線上の画素の座標と輝度を同時に求めるためには
有効であるが、輝度が一定である場合においても直線の
傾きを求める除算が必要となる。このため、ブレゼンハ
ムのアルゴリズムを使用する方式に比べ上位プロセッサ
の負荷が大きくなるという問題がある。具体的には、ブ
レゼンハムのアルゴリズムを使用すれば、与えるデータ
が始点の座標データと終点の座標データだけで済むのに
対し、傾きを小数で表す方式の場合には、始点と終点の
ｘ，ｙ座標の他に、十分な精度の傾きの値と、直線の長
さとを与える必要があり、更に、その直線の傾きを求め
るために除算を行わなければならず、上位プロセッサの
負荷が増大してしまう。

【０００５】本発明の目的は、ブレゼンハムのアルゴリ
ズムを改良し、複数のプロセッサによって並列に直線発
生を行わせる時、上位プロセッサの負荷を軽減すること
ができる直線発生並列処理方法や描画プロセッサ並びに
これを利用したＣＡＤシステム等を提供することにあ
る。

【０００６】本発明の他の目的は、ブレゼンハムのアル
ゴリズムを改良するときに、膨大なハ−ドウェアの増大
を伴わないようにする直線発生並列処理方法等を提供す
ることにある。

【０００７】

【課題を解決するための手段】上記目的は、複数の描画
プロセッサを有し直線描画を並列処理するに際し、描画
対象の直線を始点座標及び終点座標にて指定する入力手
段と、画像メモリ上の画素を周期配列毎の画素集団に分
割し各画素集団の各々に１つの描画プロセッサを割り当
てる手段と、各描画プロセッサが自己の担当する画素集
団でブレゼンハムのアルゴリズムを実行して前記直線に
該当する画素を求めるに当り画素の座標と真の直線との
ずれを示す誤差項が仮分数となった時に分子から分母を
繰返し引き算して帯分数に変換しこの帯分数の整数部を
画素の座標に加えることで直線に該当する画素を次々と
求める手段と、各描画プロセッサが求めた画素を画面上
に描画する手段とを設けることで、達成される。

【０００８】

【作用】ブレゼンハムのアルゴリズムは簡単にいうと、
直線の傾きを分数（真分数）で表し、始点の座標に順次
傾きを加算して直線上の画素を求める方式である。傾き
を表す分数の分母としては、与えられた直線の始点と終
点のｘ，ｙ座標の差ｄｘ，ｄｙの絶対値が大きい方の値
が、分子としては小さい方の値が設定される。前者を長
軸成分Ｌとし、後者を短軸成分Ｓとする。Ｌは発生する
画素の数でもある。さて、直線は、簡単のために、第１
象限内の４５度以下の傾きであるとして説明する。直線
の始点座標に対して傾きＳ／Ｌを加算すればその直線上
の次の画素を求めることができる。しかし、直線に最も
近い画素を求めるためには求めた結果を四捨五入する必
要がある。そこで、予め始点のｙ座標（短軸成分側）の
値に＋０．５を加算しておく必要があるが、座標を分数
で表しているため、傾きを表す分数の分母を２Ｌ，分子
を２Ｓとそれぞれ２倍して、始点のｙ座標の小数部はＬ
／２Ｌとおくことにする。実際のハ−ドウェアにおいて
は、まず、真の直線と整数格子（画素の座標）とのずれ
である誤差項ＥをＬと置き、それに傾きの分子２Ｓを加
算する。これによって始点の次の画素の座標が分数で求
められる。このとき誤差項Ｅが２Ｌよりも大きければ仮
分数であるため、これを帯分数に直す必要があり、分子
から２Ｌを引き、始点ｙ座標の整数部を１更新する。長
軸成分であるｘ座標はＥの値にかわらず１更新する。こ
の処理を繰り返すことで、直線上の画素を加減算だけで
求めることができるようになる。

【０００９】さて、このような直線発生方法を複数のプ
ロセッサによって並列に処理させるには、例えばｘ座標
が奇数の画素と偶数の画素を扱う２個のプロセッサで処
理する場合について考えると、プロセッサはある画素の
ｘ，ｙ座標が求められている時、次の次の画素を求める
ようにすればよい。隣の画素はもう一方のプロセッサが
並列に求めているため処理時間を半分にすることができ
る。そのためには、誤差項Ｅに対して傾きを２画素分
（４Ｓ）加える必要がある。また、その結果が仮分数で
ある場合にｙ座標の整数部を１または２更新する必要が
ある。もし、プロセッサの個数が増加した場合には、誤
差項Ｅに加える傾きを２Ｓのプロセッサ個数倍した値と
し、ｙ座標の更新する値の範囲を０からプロセッサの個
数まで対応できるようにすればよい。

【００１０】さて、このような処理を行うプロセッサは
１個である時に比べ、誤差項Ｅに加算する傾きのビット
長が長くなり、またｙ座標をいくら更新するかを求める
ための判定回路も必要である。このなかで、後者は誤差
項の分子から分母の値を引き算する回路を複数個持つ必
要がある。ここで、直線が水平に近い場合にはｙ座標を
更新する値が０か１であることに着目し、ハ−ドウェア
量を削減した。即ち、ｙ座標をいくら更新したら良いか
を求める判定回路として誤差項Ｅから分母２Ｌを引く回
路を１個だけもち、誤差項Ｅが２Ｌ以下になるまで繰返
し引き算を行うようにする。これによってこの判定回路
の物量を減少させることができる。

【００１１】また、複数のプロセッサが並列に自分の受
け持つ画素を生成するため高速に直線上の画素を発生す
ることができ、誤差項Ｅが仮分数となったかどうかの判
定回路を分母より大きいかどうかの回路１個にした場合
でも傾きが小さい場合には、１回で判定できるため高速
性を維持することができる。

【００１２】

【実施例】以下、本発明の一実施例を図１〜図１０を参
照して説明する。図１は、直線描画を並列に処理して表
示させるＣＡＤシステムの要部構成図である。ＣＰＵ３
はメインメモリ４上に格納されているプログラムを実行
する上位のプロセッサであり、直線を生成する複数のプ
ロセッサである描画プロセッサ１，描画プロセッサ２に
対して直線の始点座標と終点座標を与える処理を行う。
描画プロセッサ１は、表示画面上のｘ座標が偶数の画素
だけを保存しているフレ−ムメモリ５に対して、上位プ
ロセッサ３から与えられた直線上の画素を発生する。描
画プロセッサ２は、物理的には描画プロセッサ１と同じ
ものであり、表示画面上のｘ座標が奇数の画素だけを保
存しているフレ−ムメモリ６に対して直線を発生する。

【００１３】これらの描画プロセッサ１，２が、どちら
のフレ−ムメモリに接続されているかを指定するための
識別信号がPiD信号であり、ここでは、描画プロセッサ
１に対し“０”を、描画プロセッサ２に対し“１”を設
定する。フレ−ムメモリ５とフレ−ムメモリ６に格納さ
れている画素は常時座標の順に読み出され、色の変換テ
−ブルとＤＡコンバ−タからなるＲＡＭＤＡＣ７に送ら
れ、ＲＧＢのビデオ信号に変換してＣＲＴモニタ（図示
省略）に表示される。このフレ−ムメモリの内容をＣＲ
Ｔに表示させる技術に関しては広く公知であるため、こ
こでは詳細は省力する。

【００１４】描画プロセッサ１が取り扱う画素、即ちフ
レ−ムメモリ５が保存している画素の状態を図２（ａ）
に示す。図中の丸印が１画素を示している。このように
描画プロセッサを２個用いるときは、図２（ａ）の様
に、ｘ軸方向に一画素飛びに処理対象の画素を配置す
る。描画プロセッサを４個用いるときは、図２（ｂ）に
示す様に、ｘ，ｙ座標ともに１画素飛びに処理したり、
あるいはｘ座標に対して３画素飛びに処理対象の画素を
割り当てる。この場合、描画プロセッサの識別信号PiD
は、ｘ座標に４個まで描画プロセッサを割り当てられる
様に２ビット、ｙ座標にも４個の描画プロセッサを割り
当てられるように２ビット、計４ビットの信号から構成
する。従って、１６個まで描画プロセッサを拡張するこ
とができる。

【００１５】図３は、描画プロセッサ１の内部構成図で
ある。描画プロセッサ１は、パラメータ算出部１１と、
画素発生部１２と、フレームメモリ（ＦＭ）書き込み部
１３と、制御部１４からなる。このパラメータ算出部１
１は、ＣＰＵ３（図１）がシステムバスを介して設定し
た直線の始点（ｘs，ｙs），終点（ｘe，ｙe），傾き
（ｘe／ｄｘ，ｙe／ｄｙ），直線の長さ（len），直線
が始点と終点で与えられるか始点と傾き長さで与えられ
るかを示すコマンド（COM）を保持するレジスタを持
ち、これらの値から様々なパラメ−タを生成する。そし
て、パラメ−タ算出部１１が生成したパラメ−タに従っ
て画素発生部１２が識別信号PiDで示された画素の座標
を発生し、ＦＭ書き込み部１３は、画素発生部１２が生
成した画素の座標に従ってフレ−ムメモリ５（図１）に
対して画素の書き込みを行う。制御部１４は、ＣＰＵ３
によってコマンドが起動されたことを判定し、起動され
た直線の長さ分の画素を生成、書き込みするように画素
発生部１２とＦＭ書き込み部１３に制御信号を送る。

【００１６】図４は、パラメータ算出部１１の詳細構成
図である。パラメ−タ算出部１１は、直線の始点の
（ｘ，ｙ）座標を保持するレジスタｘs，レジスタｙs
と、直線を始点と終点で与える場合には直線の終点の
（ｘ，ｙ）座標として扱われるレジスタｘe，レジスタ
ｙeと、実体は同一であるが、直線を始点と傾き，長さ
で与える場合に直線のｘ軸とｙ軸の傾き成分として扱わ
れるレジスタｄｘ，レジスタｄｙと、直線を始点と傾
き，長さで与える場合に直線の長さを保持するレジスタ
lenと、直線を始点と終点で与えるか直線を始点と傾
き，長さで与えるかを指示し、描画プロセッサ１に対し
直線発生の起動を行うレジスタCOMの６個のレジスタが
あり、その内容に従って、始点のｘ，ｙ座標を示す信号
線ｘs，ｙs、直線の方向が４つの象限の内どれかを示す
サイン信号sgnＸ，sgnＹ、直線の傾きがｘ軸に対して４
５度以下か，４５度以上かを示す信号longＸ、直線の始
点と終点のｘ，ｙ座標の差、または、直線の傾きｄｘ，
ｄｙの絶対値の短い方の値を示す信号shortと長い方の
値を示す信号length，レジスタCOMの内容が出力されて
いる信号COMを出力する。

【００１７】引算器１１１と引算器１１２は始点と終点
のｘ，ｙ座標の差を求める。セレクタ１１３とセレクタ
１１４は信号COMの内容に従って引算器１１１と引算器
１１２の出力と、レジスタｄｘ，レジスタｄｙに保持さ
れている直線の傾きの値を選択する。

【００１８】絶対値演算器１１５と絶対値演算器１１６
は、セレクタ１１３とセレクタ１１４の出力の絶対値を
とり、絶対値演算器１１５と絶対値演算器１１６の出力
を比較器１１７で比較し、比較器１１７の比較結果によ
ってセレクタ１１８は絶対値演算器１１５と絶対値演算
器１１６の出力の小さい方の値を選択出力し、セレクタ
１１９は大きい方を選択し、信号COMが直線を始点と終
点で与えていることを示しているときにはそのまま出力
し、そうでなければレジスタlenに格納されている値を
出力する。

【００１９】図５は、画素発生部１２の詳細構成図であ
る。画素発生部１２はパラメ−タ発生部１１の出力する
信号群と、制御部１４の発生する制御信号に従って、フ
レ−ムメモリ５に書き込む画素のｘ，ｙ座標、信号px，
pyとそれが有効でないことを示す信号ajustと、次の座
標更新後にｘ，ｙ座標が識別信号PiDによって指定され
た画素（自分の持っている画素）に一致するかどうかを
示す信号next_sameＸ，next_sameＹを出力する座標発生
部１２１と、信号px，pyの示す座標が識別信号PiDによ
って指定された画素に一致するかどうかを示す信号same
Ｘ，sameＹを求め出力する比較器１２２，比較器１２３
と、ＣＰＵ３によってシステムバスを介し設定される直
線の色を示すＲＧＢレジスタ１２４とから構成される。

【００２０】ＦＭ書き込み部１３は、制御部１４の出力
する画素書き込み信号PIXEL_OUTが出たとき、画素発生
部１２の出力するフレームメモリ５の座標px，pyに、Ｒ
ＧＢレジスタの出力する画素の値を書き込む。フレ−ム
メモリ５は、制御部１４に対して、書き込みを行って良
いかどうかを示すため許可信号FM_acceptを出力する。

【００２１】図６は、制御部１４の詳細構成図である。
本実施例に係る制御部１４は、シ−ケンス部１４１と、
カウンタ部１４２から構成されている。シ−ケンス部１
４１は、パラメータ算出部１１のCOMレジスタに対する
書き込み信号COM_WRITEによってコマンドが起動された
ことを認識し、信号FM_accept，sameＸ，sameＹ，long
Ｘ，ajustの各信号線の値と、カウンタ部１４２の出力
線endに従って、画素発生部１２の動作開始信号load，
１画素更新信号up１，２画素更新信号up２と、ＦＭ書き
込み部１３に対する画素書き込み信号PIXEL_OUTと、描
画プロセッサ１がコマンドの起動を受け付けられるかど
うかを示すコマンド許可信号COM_acceptを出力する。

【００２２】ここで、書き込み信号COM_WRITEとコマン
ド許可信号COM_acceptは、描画プロセッサ内部のレジス
タに対する書き込み制御を行うシステムバスインタフェ
ース部（図示省略）に接続されている。

【００２３】次に、本実施例の特徴である画素発生部１
２について更に詳細に説明する。図７は座標発生部１２
１の構成図である。座標発生部１２１は、ｘ座標を保持
するｘカウンタ１２５と、ｙ座標を保持するｙカウンタ
１２６と、これらのカウンタに対して更新させるかどう
かの情報を与える誤差計算部８とから構成されている。

【００２４】ｘカウンタ１２５は、信号loadが出力され
たとき信号ｘsの値を内部に取り込み、信号pxとして出
力する。信号sgnＸはアップダウン信号として扱われ、
“１”のときｘカウンタ１２５はダウンカウントされ、
“０”の時はアップカウントされる。longＸが“１”の
ときは、Ｘ軸に対して直線が４５度以下の傾きであるの
で、ｘカウンタ１２５は誤差計算部８の出力する３ビッ
トのキャリー信号carry（２：０）に依存せずカウンタ
の内容を更新する。このとき信号up１が“１”であれば
“１”だけ更新し、信号up２が“１”であれば“２”更
新する。但し、信号ajustが“１”の時には、ｙカウン
タ１２６だけが更新され、ｘカウンタ１２５は変化しな
い。

【００２５】一方、longＸが“０”のときには、Ｘ軸に
対して直線は４５度以上の傾きを持っているため、ｘ座
標は信号up１，up２のどちらかが“u１”のとき、誤差
計算部８の出力する、３ビットのキャリー信号carry
（２：０）の値だけｙカウンタ１２６を更新する。さら
に、ｘカウンタ１２５は、次に更新した場合のｘ座標が
与えられた識別信号PiDに一致するかどうかを示すnext_
sameＸを出力する。

【００２６】ｙカウンタ１２６は、基本的にｘカウンタ
１２５と同じ機能を有している。但し、load信号によっ
て取り込む値が信号ｙsであること、longＸに対する動
作がｘカウンタ１２５と逆であることが異なるだけであ
る。

【００２７】誤差計算部８は、初期化信号err_initによ
って誤差項Ｅが初期化され信号up１，up２によって更新
される。その結果を、キャリー信号carry（２：０）と
信号ajustとして出力する。

【００２８】図８は、誤差計算部８の構成図である。こ
の誤差計算部８は、大きく分けて２種類の動作を行う。
即ち、信号COMが示す直線を、始点と傾き，長さで与え
た場合の動作と、始点と終点で与えた場合の動作を行
う。ここでは、まず前者の動作について説明する。

【００２９】直線発生のコマンドが起動された後、制御
部１４は、誤差計算部８に対し初期化信号err_initを送
出する。その時、セレクタ８１は“０．５”を選択し、
加算器８２は更新信号up１が“１”の時は傾きの値を示
している信号short（Ｓ）を加え、更新信号up２が
“１”の時は信号shortの２倍または４倍を加え、加算
器８３は何も加えず、その結果の整数部をキャリーレジ
スタ８４に、小数部を誤差レジスタ８５に格納する。

【００３０】始点の座標が与えられた識別信号PiDと一
致していない場合、即ちsameＸとsameＹの両方が“１”
とならない時、制御部１４から更新信号up１が出力さ
れ、両方とも“１”の時には信号up２が制御部１４から
出力される。信号up２が“１”の時に、加算器８２が信
号shortの何倍の値を加算するかは、直線の描画装置が
何個のプロセッサから構成されているかに依存してい
る。これを示すのが信号configであり、外部ピン（図示
省略）によって設定される。信号configが示す描画プロ
セッサの数が画素を１個飛ばしにする場合には２倍、３
個飛ばしにする場合には４倍の値を加算する。

【００３１】次に、始点と終点を与えて起動した場合の
動作について説明する。直線を始点と終点で与えるコマ
ンドを与え起動した場合、セレクタ８１は誤差レジスタ
８５の出力と信号lengthを符号反転した値を選択する。
加算器８２は傾きの値、信号short（Ｓ）の２倍または
４倍，８倍を加算する。この加算器８２は、次に求めよ
うとしている画素の短軸側座標の小数部と桁あげの整数
部を分数で表したときの分子の値を示している。

【００３２】加算器８３は、加算器８２の演算結果err
０が負の時、即ち、小数部が真分数で表されるときは何
もしない。正の時には、仮分数の状態にあるため、分母
の値を示す２倍のlengthを引き算する。加算器８２の演
算結果の符号ビットがキャリーレジスタ８４の最下位ビ
ットに格納され、加算器８３の演算結果が誤差レジスタ
８５に格納する。また、誤差レジスタ８５の符号ビット
はレジスタ８６に無条件に格納され、座標出力が有効で
ないことを示す信号ajustを出力する。

【００３３】誤差計算部８の動作を明解にするため、図
９，図１０を用いて具体例を説明する。図９（ａ）に示
す直線line１が起動されたときの、奇数のｘ座標を担当
する描画プロセッサ２の動作を説明する。始点座標
（ｘ，ｙ）は（０，０）で、終点座標が（７，５）で与
えられている。この時のタイムチャ−トを図１０の左半
分の時刻Ｔ０〜Ｔ８に示す。

【００３４】まず、ＣＰＵ３により、レジスタCOMに対
して書き込みが行われると、信号COM_EXECが“１”とな
る。この信号COM_EXECはシステムバスインタフェ−ス部
より出力され、制御部１４はこの信号COM_EXECによりコ
マンドの起動を知ることができる。制御部１４は信号CO
M_EXECが“１”となると、次に信号loadを出力し、パラ
メ−タ算出部１１の出力をｘカウンタ１２５，ｙカウン
タ１２６，カウンタ部１３２に取り込むことを指示す
る。

【００３５】次に、制御部１４は、誤差計算部８を初期
化するために信号err_initを出力する。この時点でＸ座
標は偶数であり、識別信号PiDと一致しないため、信号s
ameＸは“１”ではない。ところで、パラメ−タ算出部
１１が出力する短軸成分shortは“５”、長軸成分lengt
hは“７”であるため、このとき加算器８２の出力する
値は（−７）＋２（５）＝３となり、これが正の数であ
るため、加算器８３は２倍のlengthを引き算し、誤差レ
ジスタ８５には“−１１”が格納される。また、キャリ
ーレジスタ８４には、加算器８２の演算結果が正である
ため、“１”が格納される。

【００３６】制御部１４は信号err_initの次に、ｘ，ｙ
座標を更新するため更新信号を発生するが、時刻Ｔ２の
時点で座標（px，py）が識別信号PiDに一致していない
ため、一致するまで１画素ずつ更新させるように信号up
１を出力する。時刻Ｔ３になると、キャリー信号carry
（２：０）が確定するため、ｘカウンタ１２５とｙカウ
ンタ１２６は次の画素の座標を求めることが可能とな
り、この場合、長軸であるｘ座標は必ず“＋１”され、
短軸であるｙ座標は、キャリ−信号が“１”のため“＋
１”されることが判り、次の画素の座標が識別信号PiD
と一致し、信号Next_sameＸ，Next_sameＹがいずれも
“１”となる。このことから、まず、誤差計算部８は、
次から１画素飛びに座標を求めることが判り、セレクタ
８１は誤差レジスタ８５の出力を選択し、加算器８２は
信号shortの４倍を加算し、その結果が（−１１）＋４
（５）＝９と正であるため加算器８３で信号lengthの２
倍を引き“−５”を誤差レジスタ８５に格納する。

【００３７】また、制御部１４は、次の画素が識別信号
PiDと一致していることによって更新信号up１を“０”
とし、代わりに更新信号up２を出力する。時刻Ｔ４で、
更新信号up２が出ているとき、長軸であるｘ座標は２画
素更新され、残り画素数を求めているカウンタ１３２も
“２”ずつ引かれる。但し、短軸であるｙ座標は“１”
ずつ更新するようにする。もし、時刻Ｔ５の時のように
誤差レジスタ８５の符号が正になったときは、小数部を
表す分数が未だ仮分数であるということで、もう１回短
軸であるｙカウンタの更新と、誤差レジスタ８５の更新
を負になるまで行う。この時刻Ｔ６のときは座標が無効
であること示す信号ajustが“１”となっていることで
判定することができる。

【００３８】次に、図９（ｂ）の直線line２の描画起動
時の動作を示す。直線line２は、始点座標が（１，
１）、終点座標が（６，６）である。従って、長軸成分
length，短軸成分shortともに“５”である。始点座標
が識別信号PiDと一致しているため誤差計算部の初期化
時、加算器８２は２画素先の座標を求めるため最初から
信号shortの４倍を加算する。従って、その結果は、
（−５）＋４・（５）＝１５となり、誤差レジスタ８５
には（１５）−２・（５）＝５が格納される。従って、
信号ajustは“１”となるため、時刻Ｔ１３は、ｙカウ
ンタ１２６と誤差レジスタ８５とキャリーレジスタ８４
だけが更新される。以下同様の処理をカウンタ１３２が
“０”か負になるまで続けることで、自分の担当してい
るｘ座標が奇数の画素を発生することができる。

【００３９】本実施例によれば、２個のプロセッサが並
列に、始点と終点で与えられる直線上の画素を生成する
ので、水平または垂直に近い直線は従来の約２倍の高速
化が図れる。これは、単に並列処理による効果ばかりで
なく、上位のＣＰＵ３の計算する計算量が少なくなるた
め、直線の発生装置全体として高速化が可能となる。さ
らに、同一のハードウェアで、直線を始点と終点で与え
る場合と、始点と傾き，長さで表す両方の場合に対応可
能なため、機能が向上し、同時にハードウェア量の効率
的利用を図ることができる。

【００４０】一方、上記実施例では明確には示していな
いが、加算器８３の機能を長軸の長さlengthの２倍，４
倍，６倍，８倍をそれぞれ引き算するように変更すれ
ば、座標が計算中であるため無効であることを示す信号
ajustは必要なくなり、直線の傾きによらずプロセッサ
の数分だけの高速化を行うことができる。即ち、仮分数
を帯分数に変換したとき整数部の取り得る値の数だけ判
定回路を設ける。

【００４１】

【発明の効果】本発明によれば、画素毎に割り付けられ
た複数の描画プロセッサが並列に直線上の画素を生成す
る場合、傾きを分数で表し、与えられた真の直線と、発
生する画素のずれに、傾きの値を加えて順次直線に最も
近い画素を生成していき、ずれの値が仮分数となる場合
に、分子から分母を繰返し引き算するので、整数部が
“１”より大きな仮分数となる場合でも少ないハ−ドウ
ェアで、高速な直線描画が可能となる。

【００４２】また、分子から分母を引き算する手段を、
帯分数に変換したときに整数部の取りえる可能性のある
値すべてに対応する数、即ち並列に用意した描画プロセ
ッサの数だけ設けることによって、仮分数の値を帯分数
に変換する待ち時間なしで処理を行うことができ、さら
に一層の高速化を図ることができる。

【００４３】また、直線の傾きを小数値で与えることも
可能であり、ハ−ドウェアは分数計算の演算器と共通に
利用され、効率が良いという効果もある。

【図面の簡単な説明】

【図１】本発明の一実施例に係るＣＡＤシステムの要部
構成図である。

【図２】一個の描画プロセッサが担当するフレ−ムメモ
リ上の画素の配置例を示す図である。

【図３】描画プロセッサ１個の内部構成図である。

【図４】パラメ−タ算出部の内部構成図である。

【図５】画素発生部の内部構成図である。

【図６】制御部の内部構成図である。

【図７】画素発生部内の座標生成部の内部構成図であ
る。

【図８】画素発生部内の座標生成部内の誤差計算部の内
部構成図である。

【図９】２本の直線が与えられたとき１個の描画プロセ
ッサが発生する画素を示す図である。

【図１０】図９に示した２本の直線の描画動作を起動し
たときに描画プロセッサがどのように動作するかを説明
するタイムチャ−トである。

【符号の説明】

１…第１描画プロセッサ、２…第２描画プロセッサ、３
…ＣＰＵ、４…メインメモリ、５…第一のフレ−ムメモ
リ、６…第二のフレ−ムメモリ、１１…パラメ−タ算出
部、１２…画素発生部、１３…ＦＭ書き込み部、１４…
制御部、１２１…座標生成部、１３２…カウンタ、８…
誤差計算部、１２５…ｘカウンタ、１２６…ｙカウン
タ、８５…誤差レジスタ。

───────────────────────────────────────────────────── フロントページの続き (72)発明者曽我満茨城県日立市大みか町七丁目１番１号株式会社日立製作所日立研究所内 (72)発明者小沢幸次茨城県日立市大みか町五丁目２番１号株式会社日立製作所大みか工場内 (72)発明者森重隆春東京都小平市上水本町五丁目22番１号株式会社日立マイコンシステム内

Claims

【特許請求の範囲】

【請求項１】画像メモリ上の画素毎に割り付けられた
複数の描画プロセッサが並列に直線を生成する直線発生
並列処理方法において、直線の傾きを分数で表し、該傾
きの分数値を画素の座標に加算し更新を行う場合、発生
する画素の座標と真の直線とのずれを示す誤差項が仮分
数となった時に、分子から分母を繰返し引き算すること
で帯分数に変換し、その整数部を前記画素の座標に加え
ることを特徴とする直線発生並列処理方法。
【請求項２】画像メモリ上の画素毎に割り付けられた
複数の描画プロセッサが並列に直線を生成する直線発生
並列処理装置において、直線の傾きを分数で表し該傾き
の分数値を画素の座標に加算し更新を行う手段と、発生
する画素の座標と真の直線とのずれを示す誤差項が仮分
数となった時に分子から分母を繰返し引き算することで
帯分数に変換する手段と、その整数部を前記画素の座標
に加える手段とを備えることを特徴とする直線発生並列
処理装置。
【請求項３】請求項２において、前記誤差項が仮分数
となった時に、分子から分母の整数倍の値を引く手段を
複数個設けて帯分数に変換することを特徴とする直線発
生並列処理装置。
【請求項４】請求項２において、直線の傾きを小数で
表した場合に画素の座標に傾きの値を加算し更新する手
段を、前記傾きの分数値を画素の座標に加算する手段と
共通にして、傾きを小数で与える指定と、分数で与える
指定を選択するようにしたこを特徴とする直線発生並列
処理装置。
【請求項５】画像メモリ上の画素を周期配列毎の画素
集団に分割し各画素集団の各々に１つの描画プロセッサ
を割り当て、与えられた始点，終点を結ぶ直線に該当す
る画素を各描画プロセッサが自己の担当する画素集団の
中から演算により求めるＣＡＤシステムであって、直線
の傾きを分数で表す手段と、該傾きの分数値を前記画素
集団の周期配列された画素の座標に加算し更新を行う手
段と、発生する画素の座標と真の直線とのずれを示す誤
差項が仮分数となった時に分子から分母を繰返し引き算
して帯分数に変換する手段と、帯分数の整数部を前記画
素の座標に加えることで直線に該当する画素を求める手
段とを備えることを特徴とするＣＡＤシステム。
【請求項６】複数の描画プロセッサを有し直線描画を
並列処理するＣＡＤシステムにおいて、描画対象の直線
を始点座標及び終点座標にて指定する入力手段と、画像
メモリ上の画素を周期配列毎の画素集団に分割し各画素
集団の各々に１つの描画プロセッサを割り当てる手段
と、各描画プロセッサが自己の担当する画素集団でブレ
ゼンハムのアルゴリズムを実行して前記直線に該当する
画素を求めるに当り画素の座標と真の直線とのずれを示
す誤差項が仮分数となった時に分子から分母を繰返し引
き算して帯分数に変換しこの帯分数の整数部を画素の座
標に加えることで直線に該当する画素を次々と求める手
段と、各描画プロセッサが求めた画素を画面上に描画す
る手段とを備えることを特徴とするＣＡＤシステム。
【請求項７】直線描画処理を実行する描画プロセッサ
において、ブレゼンハムのアルゴリズムを実行して始点
と終点とを結ぶ直線の傾き上に該当する画素を求めるに
当り画素の座標と前記直線とのずれを示す誤差項が仮分
数となった時に分子から分母を繰返し引き算して帯分数
に変換しこの帯分数の整数部を画素の座標に加えること
で直線に該当する画素を次々と求める手段を備えること
を特徴とする描画プロセッサ。
【請求項８】１個または複数個の請求項７記載の描画
プロセッサと、描画プロセッサにより書き込まれるフレ
ームメモリと、フレームメモリ上のデータをＲＧＢ信号
に変換して出力する手段とを１ボードに搭載したことを
特徴とするグラフィックボード。
【請求項９】直線描画を複数の描画プロセッサで並列
処理するＣＡＤシステムにおいて、描画対象の直線の指
定を始点と終点の座標指定のみで行う手段と、指定され
た始点及び終点の位置と描画された直線の始点及び終点
位置が一致し誤差の無い描画を行う手段とを備えること
を特徴とするＣＡＤシステム。