JPH0675977B2 - 線分発生方法 - Google Patents

Description

【発明の詳細な説明】 本発明は、ラスタ点が幾本かの平行線を成して配置され
た均一なラスタ上に太さＤの線分を発生する方法に係
り、この方法では線分のビット表現を、ワード指向型の
ビットマップメモリに多数の像点もしくは画素の形態で
記憶させる。

この種の方法は、形成されるべき線分に関するデータが
例えば接続されたワークステーションによって入力され
得、かつワード指向型のビットマップメモリを含むフロ
ントエンドシステムを介してラスタ出力スキャナに付与
され得る電子印刷システムに用いられ得る。

上記ラスタ出力スキャナは、直列に与えられるデータに
よって完全なページを線毎に印刷するべく構成されてい
る。

この種のラスタ出力スキャナの一典型例はレーザプリン
タで、レーザプリンタでは光ビームが像に従って変調さ
れ、この変調された光ビームを多角形ミラーが、可撓性
のベルト上に形成された酸化亜鉛−結合剤層のような感
光面上へと線状に偏向させる。公知のようにして、変調
された光ビームにより上記感光面上に潜像が記録され得
る。この潜像は公知方法によって現像され得、かつ紙の
ような受像材料上に転写され得る。

ワークステーションによって、やはりページに印刷され
るべきテキストも入力され得る。

入力された上記（符号化済みの）テキストはフロントエ
ンドにおいて、メモリに記憶されたフォントデータで拡
大され、拡大されたテキストはやはりビットマップメモ
リに書き込まれる。更に、スキャナによって得られた例
えばオリジナルの図形データがワークステーション及び
ビットマップメモリに付与され得る。

ワークステーションはディスプレイを具備し、このディ
スプレイによって、印刷されるべきページが組み立てら
れ得る。ワークステーションを介して、ページのレイア
ウトは所望のように変更され得る。ワークステーション
を介して入力される特別のコマンドによって、フロント
エンドは直線線分、円あるいは円弧といったあらゆる種
類の線を発生して、ビットマップメモリに記憶させるこ
とができる。

ラスタ出力スキャナは解像度の改善により、次第に付け
情報の印刷に適するようになってきている。図形情報
（線分等）は、ラスタ出力スキャナのラスタ上にその像
が形成される。像形成過程には、能動化されるべきラス
タ点の選定が含まれる。能動化されたラスタ点はワード
指向型のビットマップメモリに書き込まれる。発生され
るべきラスタ点は多数であるので、急速に処理すること
が重要である。

従って本発明は、高解像度での高速印刷に対応する線分
発生方法の提供を目的とする。

この目的は冒頭に述べたような方法において、特許請求
の範囲第１項に記載した本発明の諸特徴により達成され
る。即ち、単純な、従って高速のアルゴリズムで線分発
生が実現され得、その祭必要なメモリアクセスサイクル
は最短となる。

本発明の上記及びその他の利点を、添付図面を参照しつ
つ以下に詳述する。

第１図に、フロントエンドシステムを概略的に示す。図
中、フンロントエンドコントローラ（FEC）10は操作コ
ンソール19と接続され、またプリンタ20の制御システム
とも接続されている。プリンタ20はラスタ出力スキャナ
であり、このスキャナにおいては光ビームが像に従って
変調され、かつ感光素子の表面上への線状に偏向させら
れる。感光素子は、該素子に完全な像がラスタの形態で
記録され得るように、光ビームの偏向方向に対して垂直
に駆動される。ラスタ出力スキャナの一例はレーザプリ
ンタで、レーザプリンタでは変調されたレーザビームが
回転する多面ミラーによって、電荷を付与された光導電
体の表面上へと向けられる。光導電体が上記のようにし
て像に従って露光され、得られる帯電像はトナーで公知
のように現像されて受像シートに転写され、かつ熱によ
り定着を実現され得る。フロントエンドコントローラ10
はモトローラ68000マイクロプロセッサを具備した16ビ
ットマイクロプロセッサシステムを含み、局所的ROM並
びにランダムアクセスメモリ（RAM）12の一部との組み
合わせにおいてフロントエンドの制御システとして機能
する。フォント読み出しメモリ13には、幾つかの印刷字
体のビットパターンが記憶されている。フロントエンド
は、やはりモトローラ68000マイクロプロセッサを具備
した16ビットマイクロプロセッサシステムを含むI/Oプ
ロセッサ11を介して、ディスクメモリ、ワークステーシ
ョン、コンピュータ及び／またはクラスタコントローラ
と接続され得る。FEC10、I/Oプロセッサ11、RAM12及び
フォントメモリ13は、標準的なVMEバス14を介して互い
に接続されている。フォントメモリ13は、RAMとして構
成され、あるいはRAM12の一部から成ることも可能であ
る。その場合フォントのビットパターンは、フロッピデ
ィスク記憶装置のディスクメモリから上記RAMにロード
される。

ラスタイメージプロセッサ（RIP）15もVMEバス14と接続
されている。ラスタイメージプロセッサ15は更にラスタ
イメージバス（RIバス）17を介して、ラスタイメージメ
モリ（RIM）とも呼称されるベージ大ビットマップメモ
リ16と接続されている。RIP15はフォントメモリ13から
読み出した字体文字のその像に基づいてビットマップメ
モリ（RIM）16に書き込むべく機能し、前記字体文字は
ビットマップメモリ16内の適正な記憶場所に配置され
る。RIP15は更に、メモリ12から図形情報を読み出し
て、やはりビットマップメモリ16内の所望の記憶場所に
書き込むこともできる。ビットマップメモリ16がデータ
で満たされた後、書き込まれたデータはRIP15を介して
再び読み出され得、読み出されたデータは直列画素ビッ
トストリームとして、ライン18を介してレーザプリンタ
の変調器に送られる。

光導電体上に記録される像は0.05×0.05mmの画素から成
り、従ってA4判の白黒像を印刷するには約4,000×6,000
個の画素が必要である。この結果、ビットマップメモリ
16は約24メガビットもしくは３メガバイトの容量を有す
る。ビットマップメモリ16からの読み出しの間ライン18
を介してレーザプリンタの変調器に送られる画素ビット
の伝送速度は約25メガビット／秒であり、その結果A4判
のページは約１秒で印刷され得る。

例えばワークステーションからI/Oプロセッサ11を経て
送られてくる、印刷されるべきページに関するあらゆる
データは、FEC10の制御下にRAM12に記憶される。そのた
めに様々なオプションが有効である。例えばA4判ページ
を”ポートレイモード”で印刷しなければならない場
合、ページの記録に必要な約4,000本の走査線に対応す
る約4,000個のサブテーブルが設けられる。各サブテー
ブルには、ある１本の走査線上に始点が位置する字体文
字あるいは図形文字のタイプコードが蓄積される。各タ
イプコードはある１個の文字の、該文字が走査線上に占
めるＸ方向位置に関するデータ、フォントの種類に関す
るデータ、並びに高さ及び幅に関するデータを含む。タ
イプコードはフォントメモリ13内の基底アドレスに関す
るデータをも含み、前記メモリ13には文字のビット表現
が16ビットワードで記憶されている。このように形成さ
れる１組のリストを、原データのリストと呼称する。

こうして、印刷されるべきページに関するデータがRAM1
2に蓄積されると、ビットマップメモリ16への書き込み
が開始され得る。そのためにタイプコードはRIP15によ
ってRAM12から１個ずつ読み出され、フォントメモリ13
からの関連ビット表現と共に拡大されてビットマップメ
モリ16内の、Ｘ方向及びＹ方向において適正な記憶場所
に配置される。このようにして総ての文字が１個ずつ完
成され、その結果ビットマップメモリ16は印刷されるべ
きページの画素ビット表現で完全に満たされる。

上述のようなサブリストは、必ずしも形成される必要は
無い。印刷されるべきページに関するデータはRAM12
に、ランダムシーケンスの形態でも記憶され得る。ビッ
トマップメモリ16への書き込みの際、RAM12にランダム
シーケンスの形態で記憶された原データは連続的に読み
出され、拡大され、ビットマップメモリ16内にそれぞれ
の記憶場所に配置される。更に別のオプションによれ
ば、あるページ上に認められる文字はどの種類も１度し
か記憶されず、その際前記各種の文字は自身が当該ペー
ジ上に占める様々な位置に関するデータを具える。この
ようにして、例えば文字ｅのような頻繁に出現する文字
に関するデータがRAM12に１度しか記憶されず、該文字
がページ上に占める全位置は別のテーブルに挿入され
る。

普通、RAM12あるいはフォントメモリ13に記憶された文
字のうちまず図形文字がビットマップメモリ16に書き込
まれ、字体文字はその後にのみ書き込まれる。

ラスタイメージプロセッサ 第２図に、RIP15の実施し得る処理を示す。システム起
動（ステップ24）後、RIP15はフロントエンドコントロ
ーラ10からのシステムリセット信号もしくはINITコマン
ドによって初期化され（ステップ25）、その後”自己試
験”処理（ステップ26）が開始される。この”自己試
験”には、様々なRIP機構及びビットマップメモリ（RI
M）機能の試験が含まれる。RIP15は自己試験手続きの間
VMEバス14にアクセスしてはならず、なぜならFEC10がRA
M12及びフォントメモリ13の試験にVMEバス14を必要とす
るからである。RIP15が”自己試験”プログラムを問題
無く終えた場合、割り込み信号がFEC10に送られ、RIP15
は待ちモードとなる（ステップ27）。自己試験プログラ
ムが故障を検出した場合はRIP15はやはり待ちモードと
なる（ステップ27）が、FEC10への割り込み信号は発生
されない。それによってフロントエンドコントローラ10
は、RIP15の”自己試験”において故障が発見されたこ
とを知る。故障はオペレータにもLEDの点燈によって告
知される。

FEC10からRIP15への"RIP診断”コマンドによって、RIP1
5診断処理30が開始する。RIP15は幾つかの内部試験を行
ない、かつRIM16についても幾つかの試験を行なう。こ
れらの試験の結果はRAM12に記憶され、また操作コンソ
ール19に送られて視覚化され得る。RIP診断処理は、VME
インタフェースも試験する。RIP診断処理は、自己試験
処理がより機能的なハードウェア試験を行なうのに比
べ、より発展的な性格を有する。RIP診断処理終了後、R
IP15は状態情報をRAM12に記憶させ、FEC10への割り込み
信号を発生し、VMEバス14を解放する。

FEC10から”ビットマップ書き込み”コマンドを受け取
ると、RIP15はVMEバス14上でのデータ転送をチェックす
る。即ちRIP15は、印刷されるべきページの原データを
持つRAM12にアクセスする。

RIP15は原データのリストをフォントの画素ビット表現
によって拡大し、ビットマップメモリ（RIM）16内に配
置する。RIP15はRIM16に、RIバス17を介してアクセスす
る。RIM16は、該ビットマップメモリ16のためのデータ
に関する、例えばAND、OR及びINVERT演算のような様々
な算術演算の実行においてRIP15を補助する偏向理論回
路を含む。ビットマップが満たされた（ステップ28）
後、RIP15はRAM12に状態情報を記憶させ、FEC10へと割
り込み信号を発し、VMEバス14を解放する。

続いてFEC10が”ビットマップ読み出し”コマンドを発
生し、RIP15はレーザプリンタから制御インタフェース
を介して送られてくるページ同期化信号を待つ。上記ペ
ージ同期化信号の受信後、RIP15はRIM16からの読み出し
（ステップ29）によって始動して、直列画素ビットスト
リームを発し、このビットストリームはビデオインタフ
ェースを介してレーザプリンタの変調器に送られる。ビ
ットマップ読み出し処理（ステップ29）の終了後、RIP1
5は再びRAM12に状態データを記憶させ、FEC10へと割り
込み信号を発し、VMEバス14を解放する。

RIP15（第３図）は内部バスシステム、即ちラスタイメ
ージプロセッサバス（RIPバス）46の周囲に構成されて
おり、前記バス46は、16ビットワードを排他的に伝送す
るべく設計された同期バスである。RIPバス46はデータ
ライン47と、アドレス及び制御ライン48と、条件ライン
49とを含む。このRIPバス46は、VMEバスインタフェース
41を介してVMEバス14と、またRIバスインタフェース45
を介してRIバス17と接続されている。RIバス17は特にデ
ータ及びアドレスライン58と、ビジーライン57と、RIバ
スアドレス有効ライン56と、クロックライン54と、複数
本の変更ラインとを含む。RIPバス46は更に、レーザ走
査モジュールインタフェース（LSMインタフェース）44
並びにRIP15固有の中央処理装置（CPU）43とも接続され
ている。レーザ走査モジュールLSMインタフェース44
は、印刷されるべき線の始まりを知らせる同期化信号を
もたらす”走査開始（SOS）”ライン52、所望の画素周
波数に対応する信号をもたらすバーストライン53、ビッ
トマップメモリ16からの読み出しの際直列画素ビットス
トリームをレーザプリンタの変調器に送るビデオライン
18といった諸ラインを介してレーザプリンタと接続され
ている。アドレス及び制御ライン48並びに条件ライン49
は、ページ同期化インタフェース42とも接続されてい
る。ライン50を介して、”ページ−アベイラブル（PA
V）”信号がプリンタの制御デバイスに送られ、この信
号はページ全体のデータがビットマップメモリ16に書き
込まれたこと、及びRIP15はプリンタの制御デバイスに
よって発せられた”ページ開始（SOP）”信号をライン5
1を介して受信すればビットマップメモリ16からの読み
出しを開始得ることを知らせる。

VMEバスインタフェース 第４図、VMEバスインタフェース41の細部を概略的に示
す。マスタインタフェース100、スレーブインタフェー1
01及びインタラプタ102がVMEバス14と接続されている。
RIPバス46からのデータライン47が、マスタインタフェ
ース100と接続されている。RIPバス46からのアドレス及
び制御ライン48並びに条件ライン49は、マスタインタフ
ェース100、スレーブインタフェース101及びインタラプ
タ102と接続されている。VMEバスインタフェース41の仕
事は、RIP15を非同期式のVMEバス14からシールドするこ
とである。VMEマスタインタフェース（VME-MI）100は存
在するバッファ及びレジスタを制御する内部制御システ
ムを含み、このインタフェース100を介してVMEバス14上
でのアクセスサイクルが実行され得る。上記制御システ
ムにはプログラマブルな論理回路が用いられている。ス
レーブインタフェース101及びインタラプタ102の制御用
としても、プログラマブルな論理回路が設置されてい
る。

VME-MI100（第８図）または、データベースマスタ（DTB
マスタ）及びデータベースリクエスタ（DTBリクエス
タ）のようなデータ転送機能を有する。所望のデータ転
送速度を得るために、VME-MI100には幾つかの機能が付
加されている。

第一の機能は、アドレス‐ハイカウンタ132及びアドレ
ス‐ローカウンタ133によって構成されるアドレスアッ
プ／ダウンカウンタである。各々フォントメモリ13ある
いはRAM12の連続的なアドレスに蓄積された様々な字体
文字あるいは図形文字のビット表現のRIM16へのロード
の際、カウンタ132及び133は個々の文字毎に、当該文字
の例えばRAM12内での基底アドレスにプリセットされ
る。バッファ134並びにVMEバス14のVMEアドレスバス14
を介して、上記基底アドレスはRAM12に送られ、当該記
憶場所に蓄積された第一の16ビットワードがVMEバス14
のVMEデータバス142を介して両方向バッファ135にもた
らされた後、RIM16内の適正な記憶場所に配置される。
カウンタ133に１を加えることによってRAM12の次のアド
レスが発せられ、第二の16ビットワードがVME-MI100を
介してRIM16に与えられる。同様にして所与の文字に関
連する総てのアドレスが発せられ、文字はRIM16内に完
全に書き込まれる。

こうして、CPU43は基底アドレスを１文字につき１回し
か発しなくてよく、その結果RIM16へのロードの間、例
えば画素処理演算、RIMアドレス決定等他の機能が果た
され得るという成果が得られる。

ある文字が完成されると、次の文字の基底アドレスが新
たにカウンタ132及び133に与えられ、上述のサイクルが
繰り返される。

第二の機能、即ちミラー機能は、FPLA及びPALのような
プログラマブルな論理回路で構成されたミラー回路136
によって果たされ、この回路136は文字がRIM16内に180
゜回転して書き込まなければならない場合に用いられ得
る。ミラー回路136は16ビットワードの各ビットを、ビ
ット位置０のものをビット位置15ものと、ビット位置１
のものをビット位置14のものと、ビット位置２のものを
ビット位置13のものと、というように交換する。

今やCPU43は基底アドレスは発せず、所与の文字の高さ
から及び幅に関するデータ並びに基底アドレスからRAM1
2の、該文字に関連する最大アドレスを計算する。計算
された最大アドレスはカウンタ132及び133にロードさ
れ、これらのカウンタ132、133はVME-MIコントローラ13
0によってダウンカウンタに切り替えられる。RAM12の記
憶場所への各アクセス毎にカウンタ133の内容から１引
かれ、RAM12からの16ビットワードはミラー回路136で鏡
像状に反転され、データ‐インレジスタ137を介してRIM
16内に書き込まれる。このようなサイクルは、当該文字
の本来の基底アドレスに端するまで続けられる。VME-MI
100においてはまた、上述のようにして得られるデータ
を例えばFEC10あるいはRAM12に送るべく、データ‐アウ
トレジスタ138がデータライン47を介してRIPバス46と接
続されている。

VME-MIコントローラ130は、制御ライン48及び条件ライ
ン49を介してRIPバス46と接続されており、またバッフ
ァ131を介してVMEバス14の、アドレス、データ及び制御
ライン139並びにバス調整ライン140とも接続されてい
る。

CPU43はVME-MI100に、”バス解放”、”マルチプルアク
セス”、”シングルアクセス”及び”変更”といった様
々なモードを呼び出し得る。VME-MI100がシングルある
いはマルチプルアクセスモードに切り替わり得る前に、
次のデータ、即ち読み出しか書き込みかのデータ、ビッ
ト配列が正常か鏡像反転かのデータ、所望アドレスのデ
ータ、並びに処理されるべきデータがまず特定されなけ
ればならない。このような特定は、”バス解放”モード
及び”変更”モードの間にのみ変えることができる。た
だ、処理されるべきデータだけは常に変更可能である。
このことは、”変更肯定（CHANGE ACKNOWLEDGE）”ラ
インによって指示される。VMEバス14を介して送られて
くる読み出しデータを収容するレジスタは、”レジスタ
‐フル（REGISTER FULL）”ラインが動作状態にあれば
いつでも読み出され得る。

”バス解放”モードの読み出し後VME-MI100はVMEバス14
を解放する。このことは、VMEバスドライバが動作不能
とされ、VMEバス14のBBSY信号が無効となることを意味
する。VMEバス14の解放は、最後のアクセスサイクルが
完全に終了している場合にのみ実現し得る。”変更肯
定”信号が、”バス解放”モードが確立されたことを指
示する。インタフェース100のこのモードでは、VMEバス
14へのアクセスは実現し得ない。”変更”要求後、VME-
MI100は、VMEバス14を未だ捉えていない場合そうするよ
うに命令される。このことはバス調整ライン140によっ
て達成される。”変更”モードの獲得が”変更肯定”ラ
インを介して示され、VMEバス14へのアクセスが可能と
なる。”変更”モードでは、アドレス及びデータレジス
タの内容も変更され得る。”変更”モードは、VMEバス1
4を解放せずに該バス14へのアクセスを一時的に停止す
ることを可能にする。VMEバス14へのシングルアクセス
は、”シングルアクセス”モードを呼び出すことによっ
て開始され得る。前のモードが”バス解放”モードであ
った場合、VMEバス14は、調整理論回路からの対応する
有効信号を介してのみ捕捉され得る。この捕捉の後にの
み、VMEバス14へのワードアクセスが可能となる。

読み出し／書き込みインジケータが、読み出しサイクル
と書き込みサイクルとのいずれが実行されるべきである
かを決定する。

読み出しサイクルでは、VMEバス14からのデータがミラ
ー回路136を介してデータ‐インレジスタ137にクロック
に従って書き込まれ、その際ミラー回路136は正常／鏡
像反転インジケータによって能動化され得る。データが
データ−インレジスタ137にクロックに従って書き込ま
れると、データ転送が完了したこと、及びデータがレジ
スタ137に与えられたことをCPU43に指示するREGISTER−
FULLフラグが設定される。REGISTER-FULLフラグはデー
タがデータ‐インレジスタ137に読み込まれた瞬間に設
定され、このアクセスの後アドレスカウンタの内容が１
だけ増加される。ミラー機能が用いられた場合は、アド
レスカウンタの内容は１だけ減少される。REGISTER−FU
LLフラグがなお有効で、かつデータがVMEバス14から読
み込まれる時、通常のVMEサイクルはデータ‐インレジ
スタ137が完全に読み出され、かつ該レジスタ137に新し
いデータが読み込まれてしまうまで延期される。

書き込みサイクルは原理的には読み出しサイクルと同じ
で、唯一の相違点はデータストリームの方向である。書
き込みサイクルでは、データ‐アウトレジスタ138内の
データがVMEバス14へ転送される。ミラー回路136は、書
き込まれたデータを何等変更しない。データ‐インレジ
スタ137は、REGISTER-FULLフラグをクリアし得るように
既に読み出されていなければならない。

”マルチプルアクセス”モードは、”シングルアクセ
ス”モードと多くの点で類似する。”シングルアクセ
ス”モードはFEC10からのコマンド読み出し、並びに該F
EC10への状態情報書き込み用である。”マルチプルアク
セス”モードは主として図形及びフォントデータの読み
出し用で、後続アクセスはVME-MI100によって自動的に
開始される。新しいアドレスはアドレスカウンタによっ
て発せられる。この場合に行なわれなければならない唯
一の動作は、データ−、ンレジスタ137からの読み出し
である。

上述の様々なモードは、CPU43の信号ラインの何本かと
接続されたVME-MODEラインで選択される。読み出し／書
き込みセレクタ及び正常／鏡像反転セレクタも、上記の
ような信号ラインと接続されている。CHANGE ACKNOWLE
DGE信号及びVME"レジスタ−フル”信号は、CPU43の"WAI
T"ラインによってもたらされる。VMEアドレスは24ビッ
トカウンタ132及び133に記憶され、入力及び出力データ
は２個の16ビットレジスタ137及び138に記憶される。”
アドレス‐ハイ”及び“アドレス‐ロー”カンウンタ13
2及び133並びにデータ‐アウトレジスタ138は、レジス
タクロックラインによってロードされる。データ‐イン
レジスタ137からの読み出しは、CPU43と接続されたレジ
スタネーブルラインによって行なわれ得る。

LSMインタフェース 第５図に、LSMインタフェース44の細部を概略的に示
す。RIM16読み出しの際、RIP15はメモリ16から16ビット
ワードを取り出し、RIPバス46のデータライン47を介し
てレジスタ111に転送する。制御ブロック110がライン11
5を介してシフトレジスタ112に”ロード”信号を送り、
レジスタ111の内容がシフトレジスタ112に並列にロード
される。レーザプリンタは約24MHzの周波数でバースト
パルスを発生し、このパルスはライン53及びI/Oバッフ
ァ113を介して、シフトレジスタ112及び制御ブロック11
0に送られる。シフトレジスタ112の内容は上記パルスに
よって直列にシフトし、読み出され、I/Oバッファ113及
びライン18を介してROSの変調器に送られる。

バーストパルスは制御ブロック110内の16ビットカウン
タに送られ、15個のパルスがカウントされると、もしく
は16番目のパルスがカウントされる間に、今やレジスタ
111に新たに読み込まれているワードがシフトレジスタ1
12に並列に転送され、このワードもシフトして読み出さ
れる。前記16ビットワードのシフト−読み出し動作が始
まる。前に、レジスタ111には新しい16ビットワードが
ロードされる。データがシフトレジスタ112に読み込ま
れるや”エンプティ”フラグが設定され、レジスタ111
への新データの書き込みが可能となる。”エンプティ”
フラグは、RIP15のCPU43の”待ち”ラインに与えられ
る。このようにして、１本の走査線に関する全データが
逐次ROSに転送される。制御ブロック110はRIPバス46の
条件ライン49を介して、CPU43に条件信号を送る。１本
の走査線についての作業が完了した後、ライン52を介し
てROSから制御ブロック110にSOS信号が送られる前に、R
IM16からのデータ取り出しはRIP15によって暫く控えら
れる（待ち条件）。この間に、レジスタ111はライン114
を介してクリアされる。SOS信号に応答して上述のよう
な、データをレジスタ111に読み込み、シフトレジスタ1
12に転送し、シフトして読み出すといったサイクルが次
の走査線に関して再び繰り返される。レジスタ111にワ
ードがロードされると”フル”状態も条件ライン49を介
してCPU43に送られ、CPU43はレジスタ111の内容が再び
シフトレジスタ112にロードされてしまうまで新しいワ
ードの取り出しを遅らせる。PAV信号発生後、SOSパルス
の数がCPU43内のカウンタによってカウントされ、この
カウンタによって、当該ページに関する全データのROS
への転送終了時点が確認され得る。

中央処理装置 第６図に、RIP15のCPU43の細部を概略的に示す。CPU43
は、いずれもAdvanced Micro Devicesの製品であるマ
イクロプログラマブルなマイクロプロセッサ74（Am2911
6型）並びに関連するアドレスシーケンサ70（2910A型）
の周囲に構成されている。

各クロックサイクルに応答して、実行されるべきマイク
ロ命令がマイクロ命令レジスタ72に読み込まれる。上記
マイクロ命令はマイクロPROM71からもたらされ、マイク
ロPROM71はアドレスシーケンサ70によって再びアドレス
される。プロセッサ74においては、あらゆる機能がマイ
クロ命令ビットの幾つかによって制御される。マイクロ
命令は、アドレスシーケンサ70、プロセッサ74、ブラン
チアドレス制御ユニット79、条件セレクタ75、待ちセレ
クタ77及びイネーブルブロック78のためにビットに分割
され得る。

マイクロPROM71に記憶されたマイクロ命令が実行される
順序も、アドレスシーケンサ70によって制御される。ア
ドレスへの連続アクセスの可能性に加え、マイクロPROM
71の容量4096ビットのマイクロワードエリア内の個々の
マイクロ命令に対する条件付きブランチ命令が実行され
得る。LIFOスタックが、マイクロサブルーチンにおける
リターン結合及びループ‐インの可能性をもたらす。上
記スタックは、９段の深さを有する。各マイクロ命令の
ためにアドレスシーケンサ70は12ビットアドレスを発
し、このアドレスは次の四つの発生源のうちの一つに由
来する。

−マイクロプログラムアドレスレジスタ（PC）。

このレジスタは普通、目下アクセスされているアドレス
より１だけ大きいアドレスを指示する。しかし、”待
ち”モードが待ちセレクト77によって発生されるとPCは
増分されない。

−ブランチアドレス制御ユニット79からデータを取得す
るライン92と接続された外部入力。

−一つ前のマイクロ命令の間にマイクロプログラムアド
レスレジスタ（PC）の内容をロードされる深さ９段のLI
FOスタック。

−一つ前のマイクロ命令の間に外部入力からロードされ
たデータを保持するレジスタ／カウンタ。

プロセッサ74はマイクロプログラマブルな16ビットマイ
クロプロセッサ（Am29116型）で、図形に関する用途に
最適な命令セットを伴う。プロセッサ74のための上記命
令セットには、特にシングル及びダブルオペランド、"n
ビット回転”並びに”回転及び併合が”が含まれる。

プロセッサ74は演算実行のための命令をマイクロ命令レ
ジスタ72から、バス83及び命令変更回路73を介して受け
取る。

命令入力は、即値命令のためのデータ入力としても用い
られる。プロセッサ74の”命令イネーブル（IEN）”に
入力がライン94を介して能動化されると、実行された命
令の結果はプロセッサ74のアキュムレータ及び状態レジ
スタに保持される。ライン95を介して”出力イネーブル
（OE）”が能動化されると、CPU43のデータバスは出力
として切り替えられ、該バスはプロセッサ74のALUの内
容を持つ。これに対して、”出力イネーブル”がライン
95を介して動作不能にされると、CPU43のデータバスは1
6ビット入力として機能し、RIPバス上に存在するデータ
がデータライン47を介してプロセッサ74に付与され得
る。プロセッサ74に付与された上記データは内部レジス
タに保持され得る。プロセッサ74のデータバスはRIPバ
スのデータライン47と直接接続されている。

ALUの状態（例えば桁上げ、負、ゼロ、オーバフロー）
は、各サイクルの間プロセッサ74の”状態”バス87にお
いて得られる。命令変更回路73によって、マイクロPROM
71に記録された命令は、例えば"nビット回転”のような
命令の場合回転の行なわれるべきビットの数を指示する
ように変更され得る。指示された上記ビット数は、プロ
セッサデータライン47からの幾本かのライン（91）を介
して特定される。

ライン94上のIEN信号がプロセセッサ74の命令入力動作
不能にすると、バス83上をプロセッサ74へと送られるの
と同じプロセッサ命令ビットがバス84を介してブランチ
アドレス制御ユニット79にも送られて、アドレスシーケ
ンサ70をランダムに異なるアドレスに分岐させるのに用
いられ得る。通常、ユニット79はブランチアドレスを、
データライン47からバス90を介して送られてくるデータ
で満たされたレジスタの内容から受け取る。

条件セレクタ75は８段マルチプレクサを含み、該セレク
タ75の出力はライン89を介してアドレスシーケンサ70に
接続されている。RIPバスの条件ライン49あるいはプロ
セッサ状態ライン87から状態バッファ76及びライン88を
介して条件セレクタ75の入力に付与される８個の可能な
条件のうちの１個が選択され得る。選択された条件はア
ドレスシーケンサ70によって、所望の条件付き命令の実
行に用いられる。ライン85を介して状態バッファ76に選
択イネーブル（SLE）信号を付与すれば、状態バッファ7
6には任意の新条件をロードすることができる。

”待ち”セレクタ77も８段マルチプレクサを含み、この
マルチプレクサは作動モードにおいて、８本の”待ち”
ライン97のうちの１本をライン93を介してアドレスシー
ケンサ70に接続する。待ちライン上のゼロレベルは、プ
ログラムアドレスレジスタのプログラムカウンタを停止
する。待ちラインは、RIPバスの条件ラインと接続され
ている。

イネーブルブロック78は様々な機能を有する上に、RIP
バスの制御ラインのために必要な全信号を発生する。イ
ネーブルブロック78は三つの異なる機能を果たす。

a.イネーブル信号の発生。

イネーブル信号は、その出力がRIPバスに接続されてい
る複数個のデータレジスタのうちのいずれが能動化され
るべきであるかを決定する。各レジスタについて１本の
イネーブルラインが存在する。

b.レジスタクロックの発生。

クロックラインは、その入力がRIPバスと接続されてい
る複数個のデータレジスタのうちのいずれかがデータを
クロックに従い読み込むべきかを決定する。各レジスタ
について１本のクロックラインが存在する。

c.他の信号の発生。

信号ライン上の信号は、RIPバスと接続されたインタフ
ェースモジュールにおいてフラグ及び機能セレクタとし
て用いられる。

ラスタイメージバスインタフェース RIPバス46とRIバス17との接続は、RIバスインタフェー
ス45によって構成されている（第７図）。インタフェー
ス45は、両方向データ、呼び出しされるべきアドレス並
びに変更コードを緩衝する。この緩衝はレジスタによっ
て実施される。”データ‐アウト”レジスタ120、”ア
ドレス‐ロー”レジスタ122、”アドレス‐ハイ”レジ
スタ123及び変更レジスタ124はRIPバス46からロードさ
れ得る。ロードは、CPU43のイネーブルブロック78によ
るアドレス及び制御ライン48制御の下に行なわれる。”
データ‐イン”レジスタ121からの読み出しは、イネー
ブルブロック78のイネーブルラインによる制御に導かれ
て実施され得る。”アドレス‐ハイ”レジスタ123は、
アドレスの上位桁のビットを記憶する。”アドレス‐ロ
ー”レジスタ122は下位桁のビットを記憶する。”アド
レス‐ハイ”レジスタ123へのロード後、RIバス読み出
し／書き込みサイクルが自動的に開始される。このこと
は、コントローラ125によって次の処理が実施されるこ
とを意味する。

サイクル１−RIバス上にアドレスを設定し、RAV（Ｒバ
スアドレス有効）を有効にする。

サイクル２−RIバス上に”データ‐アウト”を設定し、
RAVを無効にする。

サイクル３−RIバス上のデータを”データ‐イン”レジ
スタ121に読み込む。

RIバスサイクルの開始前に、CPU43はRIバスビジーライ
ン57が非動作状態にあるかどうかを試験しなければなら
ない。ビジーライン57は、CPU43の待ちラインの１本と
接続されている。

ラスタイメージバス（RIバス） RIバス17はRIP15をビットマップメモリ（RIM）16と接続
し、このバス17は64本のラインによって構成されてい
る。RIバス17は、ビット幅32の多重アドレス／データバ
スを含む。RIP15はRIバス17上でマスタとして動作す
る。１個以上のRIMボートを含むRIM16はそれ自体、バス
17上で主導権を一切取らない。RIバス17には、該バス17
の制御権をRIP15に要求し得るRIバスDMAデバイスも接続
され得る。

RIバス17は同期バスである。クロック信号（BCLK）は、
RIP15によってRIバス17に与えられる。バス17上でのあ
らゆる動作は二相クロックのエッジにおいて実行され
る。即ち、クロック信号（BCLK）の立ち上がりエッジで
はRIP15の全動作が、また立ち下がりエッジではRIM16の
全動作が実現する。RIバス17上でのその他のモードは、
高、低及び高インピーダンスの三つの信号レベル（トラ
イステート）によって説明され得る。信号レベルの変化
は総て、二相クロックの有効エッジによって開始されて
実現する。このように、クロック信号と、アドレス／デ
ータ信号と、その他の信号との３種の信号群が存在す
る。

バス17上に出現する諸信号は次のように規定される。

−BCLK:RIP15によってRIバス17に与えられる対称なクロ
ックパルス。

−RAD（RIPアドレス／データ）：この信号を伝送するラ
インRAD00〜RAD31は、トライステートドライバを具備し
たあらゆるデバイスによって駆動される多重アドレス／
データ転送路を構成する。”高レベル”の時、ラインRA
D00〜RAD31の総てが活動する。

−RMC（RIM変更コード）：ラインRMC0〜RMC3上をRIP15
あるいはDMAデバイスからRIMボードへと送られるこのコ
ードは、アドレスされた記憶ワードの内容についてRIM
ボードで行なわれる論理演算の間に働く”変更”機能を
特定する。この信号もトライステート型である。

−RROFF（RIバス‐リフレッシュオフ）：この信号は、R
IMボードが最短サイクル時間を達成するべくリフレッシ
ュを中断し得ることを指示する。データ損失を防ぐため
に、RIMボートとRIP15との間で特別のアドレス指定順序
が維持される。

−RBR0、RBR1（RIバス‐バス要求）：これらのオープン
コレクタ信号によって、２個のDMAデバイスはバスオー
ビタにバス17へのアクセス権を要求し得る。上記２個の
デバイスは異なる優先権を有する。

−RBG（RIバス‐バス許可）：この信号によってバスオ
ービタは、バス17が使用可能であることを最高優先権を
有する要求デバイスに指示する。

−RBUSY（RIバス‐バスビジー）：このオープンコレク
タ信号によって、アドレスされたRIMボードは自身が暫
くの間新たなバスサイクルを実行し得ないことを指示し
得る。

−RAV（RIバス‐アドレス有効）:"低レベル”の時有効
であるこのトライステート信号は、RIバス17上に有効な
アドレスが存在することを指示する。

RIバス17はビット幅32のデータ及びアドレス転送路によ
って構成され、この転送路はその32本のアドレス及びデ
ータラインRAD00〜RAD31に関して多重化されている。ラ
インRAD00〜RAD31の割り当ては、次のようになされる。

A24−D16の場合：アドレスラインRAとしてラインRAD00
〜DAD23が用いられる。その際ラインRAD24〜RAD31は”
アクセス不可”モードを取る。データラインとしてはラ
インRAD00〜RAD15が用いられ、その際にはラインRAD16
〜RAD31が”アクセス不可”モードを取る。即ち、デー
タ転送は16ビットワードに基づいて行なわれ、アドレス
指定はビット幅24で実施される。

A24−D16−D16の場合：アドレスラインに関してはA24−
D16の場合と同様である。バス17のラインRAD00〜RAD15
からのデータが付与されるボードが設定されているのと
同一のアドレス空間にラインRAD16〜RAD31からのデータ
が付与される第二のボードをも設定することによって、
各々ビット幅16である２個のボードとして機能するビッ
ト幅16のボードのためのビット幅32のデータバスが創出
され得る。アドレス／データバスのどの部分がデータを
転送するかはRIMボードにおいて選択され得る。

RBR0信号、RBR1信号及びRBG信号によって、RIバス17へ
のアクセスはRIPと選択的なDMAデバイスとの間で調整さ
れる。この調整は、全くRIM16外で行なわれる。

バス17上での各サイクルは、WRITE/READサイクから成
る。バス17がフリーである（RBUSYが有効でない）場
合、RIPはアドレス（ADR［ｎ］）をバス17のライン（RA
D00〜RAD23）上に設定し得る。この設定が行なわれると
RAV信号が発せられ、またラインRMC0〜RMC3を介してRIM
変更コード（RMコード）が送られる。アドレス指定後、
RIPはそのデータ（DATAO［ｎ］）をバス17のライン（RA
D00〜RAD15）に与える。

ADR［ｎ］によってアドレスされたRIMボードはRBUSY信
号を有効にする。そこでRIPはRIバス17を放して、ADR
［ｎ−１］によってアドレスされたRIMボードにDATAI
［ｎ−１］をバス17上に設定する機会を与え、それによ
ってRIPは上記データを読み込み得る。この結果、連続
する二つのWRITE/READサイクルは、言わば互いの中に押
し込まれる。このことは、RBUSYが無効になったかどう
かを決定するのにRIPが必要とする時間を当該サイクル
においてADR［ｎ］によってアドレスされたRIMボードの
最後の処理段階に一致させることによりなお更に最適化
される。このような手続きは、RIMボードが、該RIMボー
ド自体が完全にレディ状態となる以前にRBUSYを無効に
することによって達成されるが、このことはRBUSYがRIM
ボードにより無効にされたことをRIPが確認し得た時に
は既にRIMボードはレディ状態となっていることがきわ
めて確実である場合に実現する。即ち、第一のサイクル
は無効データを含み、またRIM16から最後のデータを取
り出すには付加的なサイクルも必要である。

先に述べたように、最短サイクル時間がバス17上で達成
される。”最短サイクル時間”とは、バス17上で最高転
送速度が達成されるバスモードのタイミングシーケンス
を意味する。

RIMのリフレッシュの結果として、RIMボードが最短サイ
クル時間を達成し得ない事態が生じ得る。RIMボードは
上記事態を、RBUSY信号によって指示する。このRBUSY信
号を所定数のクロックサイクル（BCLK）で延長すること
により、RIPは自身によるメモリ16への次のアクセスを
整数個数のクロックサイクル分だけ遅らせる。

上記と同様の状況は、RIPがある一定のタスクを未だ終
了していない場合にも生じ得る。RIPはタスクが未完で
あることを、RAV信号を整数個数のクロックサイクル分
だけ遅らせることによってバス17に指示する。

ラスタイメージメモリ RIM16（第11図）は、16ビットワードに対応して構成さ
れた24メガビットダイナミックメモリ220を含み、ペー
ジ大ビットマップメモリとして用いられる。メモリ220
内の各記憶場所は、最終的な印刷完了ページ上の厳密な
一地点に対応する。RIM16はRIバス17を介してRIP15と接
続されており、このRIP15によって、拡大されたフォン
トデータ及び図形データを書き込まれる。RIM16内で行
なわれる重要な一処理は、アドレスされたワードに対し
て実施される変更処理である。変更処理は16種の異なる
論理演算を含み、これらの演算は所与のアドレスに書き
込まれるデータ並びに既に書き込まれているデータに適
用され得る。RIバス17のラインRMC0〜RMC3（221）にRIM
変更コードを付与することによって、一つの特別の変更
機能が選択される。

上記変更コードはRMCレジスタ22内にセットされ、プロ
グラマブルな論理回路によって構成された論理処理ユニ
ット（ALU）223に付与される。新しいデータ（ND）がDA
TAOレジスタ227及びデータライン225を介してALU223に
送られ、一方既にメモリ220内に存在する古いデータ（O
D）はデータ出力ライン226を介してALU223に送られる。
ALU223内での処理の結果（MD）はライン224を介してメ
モリ220に書き込まれる。

次に掲げる表Ｉに変更機能の一部を、関連するRAコード
並びに対応する論理関係と共に示す。

RIバス17は多重化されたバスであるので、別個のアドレ
ス並びにデータはクロックに従ってレジスタに書き込ま
れなければならない。このためにRIバス17はアドレス／
データバスバッファ228と接続されており、RIバス17に
アドレスが与えられると、該アドレスはアドレスレジス
タ229にバッファ228を介して送られる。（１クロックサ
イクル後に）データが与えられると、このデータはバッ
ファ228を介してDATAOレジスタ227に蓄積される。デー
タ‐インレジスタ230（RIPにとっては”イン”である
が、RIMにとっては”アウト”）は、メモリ220の前回指
定されたアドレスからのデータをRIバス17上にセットし
得るように増分される。

RIM16の制御はメモリ制御回路231によってなされる。メ
モリ制御回路231はRAV信号に応答して一連の動作を開始
させるバス状態シーケンサを含み、上記動作とはアドレ
スのクロックに従った書き込み、前記アドレスに関連す
るデータのクロックに従った書き込み、変更コードのク
ロックに従った書き込み、及び前回指定されたアドレス
に属するデータのRIバス17上へのセットである。メモリ
制御回路231は更に、バス状態シーケンサと同期化され
るメモリ状態シーケンサをも含む。メモリ状態シーケン
サはリフレッシュ要求によってか、あるいはモリアクセ
スのためのバイサイクルによって始動され得る。リフレ
ッシュサイクルが実行される場合、次のバスサイクルは
保留されなければならない。回路231には、プログラマ
ブルな論理回路が用いられる。

メモリ220は複数個の256Kダイナミックメモリチップか
ら成り、16ビットワードに関して256Kワードの”バン
ク"6個を構成している。バンクの選択は、アドレスマル
チプレクサ232においてアドレスラインA18、A19及びA20
を復号することによって実現する。１個のバンクの記憶
場所のアドレス指定は、アドレスラインA0〜A7及びA16
を介して制御回路231から行アドレスストローブ（RAS）
が送られ、次いでアドレスラインA8、A15及びA17がアド
レスマルチプレクサ232を介してメモリアドレスライン
と接続され、列アドレスストローブ（CAS）がやはり制
御回路231によって発生されることにより実現される。

ダイナミックメモリが用いられるため、メモリ220の総
ての記憶場所は少なくとも４ミリ秒に１回リフレッシュ
されなければならない。このリフレッシュは、"RAS単
独”サイクルを周期的に付加することによって実施され
る。"RAS単独”サイクルの間、行アドレスが総てのバン
クに与えられる。行中のリフレッシュアドレスは、各リ
フレッシュサイクル後に１が加えられる９ビットカウン
タによってもたらされる。

RIバス17のRROFFラインを能動化することによって正常
なリフレッシュサイクルは中断され、次のメモリアクセ
スサイクルの最短サイクル時間が達成されることをRIP1
5が保証する。その後メモリ220のアドレスされていない
バンクが、RIバス17上のアドレスをリフレッシュの実施
に使用する。アドレスされたバンクでは、リフレッシュ
は指定アドレスへのアクセスによって行なわれる。

ページの複写が１枚しか必要でない場合、RIM16の読み
出しの間RIバス17上に"CLEAR"変換コードがセットさ
れ、なぜなら読み出し後RLM16は完全にゼロで満たされ
ていなければならないからである。再度印刷されるべく
ページが保持されなければならない場合は、"NOP"変更
コードがRIバス17上にセットされる。

図形命令 ビットマップ書き込み器28（第２図）は、CHAR、MCHA
R、LINE及びCIRCLEといった、文字に関する様々な図形
命令を実行するように設計されている。

マイクロPROM71（第６図）に記憶されている上記命令は
総て、CPU43へのマイクロ命令として実行される。これ
らの命令のためのアルゴリズムは、ビットマップ書き込
み速度が可能な限り大きくなるように決定される。

CHAR:文字をビットマップメモリ16内の適正な記憶場所
に配置する命令。文字のワード境界は通常ビットマップ
メモリ16のワード境界に対応しないので、変位させるこ
とが必要である（第９図参照）。フォントメモリ13に
は、文字201のビットマップ表現200が16ビットワードで
記憶される。１文字は普通複数個の16ビットワードで表
され、それらのワードの幾つかを符合203、204及び205
で示す。ここで、文字201の隅の点202を一例として基準
点とし、最初の16ビットワード203の16個のビット位置
のうち最初のビット位置を"0"で、また最後のビット位
置を"F"で示す。最初のワードのビット表現は0000 0000
0001 1111である。

文字201がビットマップメモリ16内で、Ｙ方向において
所望の記憶場所に配置される場合、ビットマップメモリ
16のワード境界207は文字201のワード境界０′と概して
まれにしか一致しない。即ち実施されるべき操作は、文
字201のビットマップ表現が図中Δｙで示された幾つか
（ｎ個）のビットだけずれることに対応する。

上記操作のために、マイクロ命令レベルにおいて次の諸
ステップが実行されなければならない。

回転：ビット位置０からビット位置ＦまでΔｙにわたっ
て（n:＝Δｙ）。

併合：マスク＝１ 回転。

マスク＝０ 回転せず。

MCHAR:文字を180゜回転してビットマップメモリ16内に
配置する命令。文字のビットマップ表現はVMEバスイン
タフェースによって逆の順序で読み出される。文字のワ
ード境界のビットマップメモリ16内での変位は、CHARに
関して上述したのと同様に実現される。VMEバスインタ
フェースにはミラー回路も含まれている。

文字、線、円等のビットマップメモリ16内への書き込み
のために、フロントエンドは幾つかのオーバレイオプシ
ョンを有する（第10図）。これらのオプションは第10図
において、文字Ｖ（符合210）を用いて概略的に示され
ている。線影211はRIM16の内容が変更されないことを意
味する。RIM16内の"0"は”白色”を、また"1"は”黒
色”をもたらすものとする。

WRITE:RIM16の持っている内容が"0"にされ、文字のビッ
トマップ表現が"1"で書き込まれる（212）。

INVERT:RIM16の持っている内容が"1"にされ、文字のビ
ットマップ表現が"0"で書き込まれる（216）。

PAINT:RIM16の内容がデリートされず、文字データの"1"
はRIM16の内容との"OR"関係を取られる（213）。

MASK:RIM16の、文字のデータ"0"に対応する記憶場所の
内容が"0"にされ、文字のデータ"1"に対応する記憶場所
の内容は保持される（214）。

ERASE:RIM16の、文字のデータ"1"に対応する記憶場所の
内容が"0"にされ、文字のデータ"0"に対応する記憶場所
の内容は保持される（215）。

INVERTING PAINT:RIM16の、文字のデータ"0"に対応す
る記憶場所の内容が保持され、文字のデータ"1"に対応
する記憶場所の内容はインバートされる。

直線、円及び円弧を描くには、ブリーゼンハム（Bresen
ham）アルゴリズムに基づく測定及び調節方法が用いら
れる。この場合、始点は線の理論形状であり、該始点は
各走査線に関して、所望線に最も近く選択される。上記
公知アルゴリズムは、例えばRobert F.Sproullによっ
てACM Transaction on Graphics,Vol.1,No.4,Octobe
r 1972,pages 259−279に、”プログラム変形の線描
アルゴリズム誘導への利用（Using program transfor
mations to derive line-drawing algorithms）”
という標題の下に述べられている。

画素１個の太さの線の円を発生するには、例えばJ.Bres
enhamによる“円弧のインクリメンタルデジタル表示の
ための線形アルゴリズム（Ａ linear algorithm for
incremental digital display of circular arc
s）",Communications of the ACM,February 1977,v
olume 20,No.2,pages 100−106に述べられているよう
なアルゴリズムが用いられる。こうして、文字の試験、
加算及び減算といった単純で、従って迅速に実行される
命令のみを用いてラスタ型ディスプレイ上に円が描かれ
得る。

画素３個以上の太さの直線線分を発生する方法であっ
て、前記線分をワード指向型のビットマップメモリに記
憶させる方法を次に説明する。

線分は、特定の太さ（Ｄ）並びに丸い端部を有する。始
点及び終点はラスタ点に一致し、また太さはラスタ間隔
の奇数倍である。ラスタはワード指向型メモリ内のビッ
トマップに対応すると見做される。アルゴリズムの記述
において、Ｘ軸及びＹ軸から成る、時計回りに回転する
カルテシアン座標系が用いられる。メモリ組織は、メモ
リ内のワードがＹ軸に平行に位置するようなものであ
る。

始点251（Xbeg,Ybeg）の座標と、終点252（Xe,Ye）の座
標と、ラスタ間隔で規定される太さＤとによって線分25
0が得られる（第12図）。線分250の境界は、領域（Xl≦
Ｘ≦Xr,Ybot≦Ｙ≦Ytop）内に位置する閉じた線によっ
て与えられる。Ｘ（Xl≦Ｘ≦Xr）の各値に、線分の境界
上に位置する２点253（X,Yb）及び254（X,Yt）が関連す
る。Xl≦Ｘ≦Xrにおいて（X,Yb）から（X,Yt）に至る
（太さゼロ）垂直線分によって覆われる領域は、太さＤ
の線分の占める領域に一致する。即ち、太さＤの線分の
像形成は、Ｘの連続する値に関しYb及びYt間に伸長する
Ｙ方向線分の像を形成することにより変換され得る。Ｙ
方向線分は、メモリのワード方向に伸長する。太さＤの
線分の像を形成するには、上記Ｙ方向線分の始点及び終
点を決定しなければならない。これらの点は、太さＤの
線分の境界の像を決定することによって発生される。太
さＤの線分250の境界は、P1及びP2を通る直線と、P3及
びP4を通る直線と、P3及びP2を通る円弧と、P4及びP1を
通る円弧とによって規定されると見做され得る。先に述
べたように、線分の像はブリーゼンハムアルゴリズムに
よって形成され得る。そのためには、線分の始点及び終
点がラスタ点に一致しなければならない。しかし大抵の
場合、点P1、P2、P3及びP4はラスタ点には一致せずに、
各々４個のラスタ点Pi1、Pi2、Pi3及びPi4（ｉ＝１〜
４）によって囲まれる。

第13図は、点P1及びP2を通る直線の像を示す。点P1j
（ｊ＝１〜４）のうちの上記直線に最も近接した点が像
形成されるべく直線線分の始点として選択されなければ
ならず、従ってこと例では点P12が選択される。同様
に、像形成されるべき直線線分の終点として点P24が選
択される。ブリーゼンハムアルゴリズムは円の像を形成
するのにも用いられる。今や、像形成されるべき太さＤ
の線分の始点（Xbeg,Ybeg）及び終点（Xe,Ye）はラスタ
点に一致する。その結果、円の中心がラスタ点に一致し
なければならないというブリーゼンハムアルゴリズムの
要求が満たされる。円の像を形成するラスタ点の全てが
発生される必要は無く、直線線分の像と共に太さＤの線
分の境界の像を構成する円弧の像に属するラスタ点のみ
が発生されればよい。今やラスタ交点P1^＊、P2^＊、P3^＊
及びP4^＊の座標が、線分の始点及び終点並びに太さに関
するデータによって決定され得る。

第14図に、中心（Xc,Yc）及び半径Ｒの円261並びに始点
（Xbeg,Ybeg）を有する線分262を示す。線分の始点並び
に円の中心は点251に一致する。円261の半径Ｒは（Ｄ−
１）/2に等しい。円261と線分262とは、交点Ｓにおいて
交叉する。Ｓを囲む４個のラスタ点S1、S2、S3及びS4の
中から、Ｓを通る円261に接する接線263に最も近接した
ラスタ点が選択されなければならない。座標（Ｘ^＊,
Y^＊）を有する選択されたラスタ点Ｓ^＊は、ラスタ交点P
1^＊、P2^＊、P3^＊及びP4^＊の、即ち境界の２直線線分の
始点及び終点の座標決定のための情報を提供する。この
ような条件下に、点Ｓ^＊から円261の中心251（Xc,Yc）
までのカルテシアン座標上での距離が決定され、即ちHx
＝Ｘ^＊−Xc及びHy＝Ｙ^＊−Ycが得られる。このことか
ら、ラスタ交点の座標が次のように定まる。

P1^＊：（［Xbeg−Hy］，［Ybeg＋Hx］） P2^＊：（［Xe−Hy］，［Ye＋Hx］） P3^＊：（［Xe＋Hy］，［Ye−Hx］） P4^＊：（［Xbeg＋Hy］，［Ybeg−Hx］） 点P1^＊〜P4^＊は今や、ラスタ点に厳密に一致する。線分
262及び円261のラスタ上での像はブリーゼンハムアルゴ
リズムで決定される。

線分発生において、円の中心は座標系の原点に一致し、
また線分は第一の八分円内に位置するものとする。この
家庭は一般性を減じるものではなく、なぜならその他の
事例は、単純な並進によってこの例に変形され得るから
である。

線分のためのブリーゼンハムアルゴリズムは座標系の原
点において開始され、また円のためのブリーゼンハムア
ルゴリズムは点（R,0）において開始され、その際Ｒは
円の半径である。上記二つのアルゴリズムはフロントエ
ンドにおいて、準並列に実行される。発生されたラスタ
点は、等しいＹ値に同期化される。次のアルゴリズムに
よって、交点Ｓ^＊の座標（Ｘ^＊,Y^＊）が決定される。ア
ルゴリズムは交点Ｓの周囲の領域に収束する。この領域
内で、座標（Ｘ^＊,Y^＊）のＳ^＊が選択される。第15図
は、交点Ｓ^＊の決定をフローチャートにおいて示す。ア
ルゴリズム開始（300）後、まず線及び円の様々な変数
が初期化され、XL＝０、YL＝０、XC＝Ｒ及びYC＝０とさ
れる（301）。条件XL＜XC（302）が満足される場合、XL
の値は１だけ増加される（303）。次いで線のYLの値
が、ブリーゼンハムアルゴリズムで計算される（30
4）。条件YL＜YC（305）が満足されない場合、プログラ
ムはブロック302に戻る。依然XL＜XCであると、ブロッ
ク303及び304から成るプログラムループが再び実行さ
れ、ブロック305において再び値YLがYCと比較される。
条件YL＞YCが満足される場合はYCが１だけ増加され（30
6）、かつ円に関してXCがブリーゼンハムアルゴリズム
によって計算され（307）、その後プログラムは302に戻
る。こうして、ブロック302〜305及びブロック302〜307
から成る二つのプログラムループが、もはやXL＜XC（30
2）でなくなるまで実行される。次にプログラムは、ブ
ロック308にジャンプする。今やXL＝XCであれば、Ｘ^＊
はXLに、またＹ^＊はYLに等しくされる（309）。XL＞XC
（308）であれば、Ｘ^＊及びＹ^＊の値は次のように求め
られる（310）。

Ｘ^＊＝XC＋１ Ｙ^＊＝YC−１ 線分250（第16図）は、始点の座標（Xbeg,Ybeg）と、終
点の座標（Xe,Ye）と、ラスタ間隔で測定される太さＤ
とによって与えられる。ここで、Xe≧Xbeg及びYe≧Ybeg
と仮定する。即ち、線分250は正のＸ軸との間に０〜90
゜の角度を成す。Xe＜Xbegである場合は、Xe≧Xbegであ
るとの仮定は始点と終点とを交換することによって満足
され得る。Ye＜Ybegの場合は、Ye≧Ybegであるとの仮定
は線分の、水平な線ｙ＝Ybeg（Ye⁰＝２×Ybeg−Ye）に
関する鏡面対称像を形成することによって満足され得
る。しかしその場合、まず垂直線分の始点及び終点の線
ｙ＝Ybegに関する鏡面対称像が、これらの垂直線分の像
に属するラスタ点が（ビットマップ中で）能動化される
前に形成されなければならない。

Ｓ^＊の決定後、P1^＊、P2^＊、P3^＊及びP4^＊の座標（X
1^＊,Y1^＊）、（X2^＊,Y2^＊）、（X3^＊,Y3^＊）及び（X
4^＊,Y4^＊）が、Hx及びHyによって先に述べたように決定
される。こうして、四つの準並列アルゴリズム、即ち二
つの線アルゴリズム並びに二つの円アルゴリズムのため
のデータが入手可能となる。第16図において、円１は点
255からP1^＊へ、及びP2^＊から点256へと続き、また円２
は点255からP4^＊へ、及びP3^＊から点256へと続く。線１
はP1^＊からP2^＊に、または線２はP4^＊からP3^＊に伸長す
る。円アルゴリズム１及び２は半円を発生し、かつその
半円がP1^＊及びP4^＊それぞれ達すると中心251（Xbeg,Yb
eg）を中心252（Xe,Ye）に置き換える。線の発生は、領
域270〜274を連続的に横切って実現する。

用いるアルゴリズムを、第17a図〜第17c図にフローチャ
ートで示す。プログラムが始まり（320）、Ｒ＝（Ｄ−
１）/2、Xl＝Xbeg−Ｒ、XR＝Xe＋Ｒ、Xc1＝Xbeg、Yc1＝
Ybeg、Xc2＝Xbeg、Yc2＝Ybeg、Ｘ＝Xl、Yt＝Ybeg及びYb
＝Ybegといった幾つかの変数が初期化される（321）。
その際、Ｘ＝Xlに関して第一の垂直線が描かれる（32
1）。「このＸにおいてYb及びYt間に伸長する垂直線を
描き、その線をビットマップメモリ内の対応する記憶場
所に配置せよ」という命令を示すのに、コードDrln（X,
Yb,Yt）が用いられる。その後、領域270での垂直線の計
算及び発生が開始される（第16図）。Ｘ＜X1^＊が試験さ
れ（324）。Ｘ＜X1^＊であるとまずＸが１だけ増加され
（322）、得られたＸの値に関してブリーゼンハムアル
ゴリズムにより、円１上のＹ＝Ytの点並びに円２上のＹ
＝Ybの点が決定される（323）。再びDrln（X,Yb,Yt）に
よってYb及びYt間に垂直線が描かれ（323）、プログラ
ムは324に戻る。Ｘ＜X1^＊である間は常に、ブロック32
2、323及び324から成るループが実行される。

Ｘ＝X1^＊である場合は、プログラムはブロック325に進
む、このブロック325でX4^＊＜X2^＊であるかどうかの比
較が行なわれる。結果がnoであれば、後述するように、
プログラムはブロック350からブロック364へと実行され
る。このことは例えば、急傾斜の線、並びに太さに比し
て短い線に該当する。X4^＊＜X2^＊であり（325）、かつ
Ｘ＜X4^＊である（328）場合はＸが１だけ増加され（32
6）、得られたＸの値に関してブリーゼンハムアルゴリ
ズムにより線１上のＹ＝Ytの点並びに円２上のＹ＝Ybの
点が決定される（327）。上記Ｘの値に関してもDrln
（X,Yb,Yt）によってYb及びYt間に垂直線が描かれ（32
3）、かつメモリに記憶される。Ｘ＜X4^＊である（328）
間、即ち領域271（第16図）に関しては、プログラムは
ブロック326、327及び328から成るループが実行され
る。Ｘ＝X4^＊となるとＸ＜X2^＊であるかどうかが試験さ
れ（331）、yesである場合プログラムは次に、Ｘの値を
１だけ増し（329）、ブリーゼンハムアルゴリズムによ
って線１上のＹ＝Ytの点並びに線２上のＹ＝Ybの点を計
算し、再びDrln（X,Yb,Yt）によって垂直線を描く（32
9）ブロックが実行される。Ｘ＜X2^＊である（331）間、
即ち領域272（第16図）に関しては、ブロック329、330
及び331から成るプログラムループが実行される。Ｘ＝X
2^＊となるとまず、オリジナル変数Xc1及びYc1の値がブ
ロック332において線分の終点の座標に変更される。即
ち、Xc1＝Xe及びYc1＝Yeとなる。次いで、領域273（第1
6図）での発生が行なわれる。Ｘ＜X3^＊であるかどうか
が試験され（335）、そうであればＸの値が１だけ増加
され（333）、ブリーゼンハムアルゴリズムにより円１
上でのYtの値並びに線２上でのYbの値が決定される（33
4）。関連する垂直線がDrln（X,Yb,Yt）によって、ビッ
トマップメモリ内に配置される（334）。Ｘ＜X3^＊であ
る（335）間は、ブロック333、334及び335から成るプロ
グラムループが実行される。ＸがX3^＊の値に達するとオ
リジナル変数Xc2及びYc2が、Xc2＝Xe及びYc2＝Yeに変更
される（336）。

今や、線分の最後の両274に関して発生が行なわれる。
Ｘ＜XRであれば（339）、Ｘは再び１だけ増加され（33
7）、ブリーゼンハムアルゴリズムを用いて円１上でのY
tの値並びに円２上でのYbの値が決定され（338）、Drln
（X,Yb,Yt）により垂直線がビットマップメモリ内に配
置される。Ｘ＜XRである（339）間は、ブロック337、33
8及び339から成るプログラムループが実行される。Ｘが
値XRに達すると、線分の発生は完了し、プログラムはブ
ロック364で停止する。

線が急傾斜である場合（X4^＊＞X2^＊）は、プログラムは
ブロック325からブロック352にジャンプする。Ｘ＜X2^＊
である（352）場合Ｘの値は１だけ増加され（350）、ブ
リーゼンハムアルゴリズムを用いて線１上でのYtの値並
びに円２上でのYbの値が決定され（351）、Yt及びYb間
に伸長する垂直線がDrln（X,Yb,Yt）によりビットマッ
プメモリ内に書き込まれる（351）。Ｘ＜X2^＊である（3
52）間は、ブロック350、351及び352から成るプログラ
ムループが実行される。ブロック332でのように、Ｘ＝X
2^＊の時変数Xc1及びYc1はブロック353においてXc1＝Xe
及びYc1＝Yeに変更される。Ｘ＜X4^＊である（356）とＸ
は１だけ増加され（354）、ブリーゼンハムアルゴリズ
ムを用いて円１上でのYtの値並びに円２上でのYbの値が
決定され（355）、Yb及びYt間に伸長する線がビットマ
ップメモリ内の対応する記憶場所に配置される（35
5）。Ｘ＜X4^＊である（356）間は、ブロック354、355及
び356から成るプログラムループが実行される。Ｘ＝X4
^＊となるとＸ＜X3^＊であるかどうかが試験され（35
9）、そうであればＸが１だけ増され（357）、ブリーゼ
ンハムアルゴリズムを用いて円１上でのYtの値並びに線
２上でのYbの値が決定され、Yt及びYb間に伸長する線が
Drln（X,Yb,Yt）によってメモリに記憶される（358）。
Ｘ＜X3^＊であれば（359）、ブロック357、358及び359か
ら成るプログラムループが連続的に実行される。Ｘ＝X3
^＊の時変数が変更され、即ちXc2＝Xe及びYc2＝Yeとなる
（360）。Ｘ＜XRである（363）と、Ｘが１だけ増加され
（361）、ブリーゼンハムアルゴリズムを用いて円１上
でのYtの値並びに円２上でのYbの値が決定され（36
2）、Drln（X,Yb,Yt）によりメモリへの書き込みが行な
われる（362）。Ｘ＜XRである（363）間は、ブロック36
1、362及び363から成るプログラムループが実行され
る。Ｘが値XRに達すると線分発生は完了し、プログラム
は停止する（364）。

真直な端部を有する線分のためのアルゴリズムも、対応
して作成され得る。第18図は上記のような線分を示す。
線分の境界は、点P1、P2、P3及びP4によって規定され
る。丸い端部を有する線分の発生の場合と同様に、上記
４点はラスタ点P1^＊、P2^＊、P3^＊及びP4^＊に一致しなけ
ればならない。従ってこれらの点は、丸い端部を有する
線分の発生の場合に対応して決定される。まずＳ^＊が、
第15図との関連で述べたアルゴリズムによって決定され
る。次いで補助関数Hx及びHyが、Hx＝Ｘ^＊−Xc及びHy＝
Ｙ^＊−Ycによって定義される。このことから、次のよう
に定まる。

P1^＊：（［Xbeg−Hy−Hx］，［Ybeg＋Hx−Hy］） P2^＊：（［Xe−Hy−Hx］，［Ye＋Hx−Hy］） P3^＊：（［Xe＋Hy−Hx］，［Ye−Hx−Hy］） P4^＊：（［Xbeg＋Hy−Hx］，［Ybeg−Hx−Hy］） 今や、それぞれ線１、線２、線３及び線４と呼称される
線分P1^＊P2^＊、P4^＊P3^＊、P1^＊P4^＊及びP2^＊P3^＊決定の
ためのあらゆるデータが得られる。（パスカル）プログ
ラムは次のようになる。

Xl:＝X1^＊； Xr:＝X3^＊； X:＝Xl; Yt＝Ybeg; Yb＝Ybeg; DrawVerticalLine（X,Yb,Yt）； IF（X4^＊＜X2^＊）THEN BEGIN WHILE（Ｘ＜X4^＊）D0 BEGIN X:＝Ｘ＋1; BRESENHAM_LINE1_STEP（Yt）； BRESENHAM_LINE3_STEP（Yb）； DrawVerticalLine（X,Yb,Yt） END; ［Ｘ＝X4^＊］ WHILE（Ｘ＜X2^＊）D0 BEGIN X:＝Ｘ＋1; BRESENHAM_LINE1_STEP（Yt）； BRESENHAM_LINE2_STEP（Yb）； DrawVerticalLine（X,Yb,Yt） END; ［Ｘ＝X2^＊］ WHILE（Ｘ＜Xr）D0 BEGIN X:＝Ｘ＋1; BRESENHAM_LINE4_STEP（Yt）； BRESENHAM_LINE2_STEP（Yb）； DrawVerticalLine（X,Yb,Yt） END; END ［Ｘ＝Xr］ ELSE BEGIN WHILE（Ｘ＜X2^＊）D0 BEGIN X:＝Ｘ＋1; BRESENHAM_LINE1_STEP（Yt）； BRESENHAM_LINE3_STEP（Yb）； DrawVerticalLine（X,Yb,Yt） END; ［Ｘ＝X2^＊］ WHILE（Ｘ＜X4^＊）D0 BEGIN X:＝Ｘ＋1; BRESENHAM_LINE4_STEP（Yt）； BRESENHAM_LINE3_STEP（Yb）； DrawVerticalLine（X,Yb,Yt） END; ［Ｘ＝X4^＊］ WHILE（Ｘ＜Xr）D0 BEGIN X:＝Ｘ＋1; BRESENHAM_LINE4_STEP（Yt）； BRESENHAM_LINE2_STEP（Yb）； DrawVerticalLine（X,Yb,Yt） END; END ［Ｘ＝Xr］ 上述のアルゴリズムはメモリのワード組織を活用し、メ
モリへのアクセス回数が最少となることを保証する。線
分の太さは普通、該線分の長さに比較して僅かである。
このことは、P1^＊からP4^＊までの座標決定に比較的短い
時間しか掛からず、その結果上述した“中実”型の線の
像がラスタ上にきわめて迅速に形成され得ることを意味
する。

本発明は、上述の諸具体例に限定されるものではない。
即ち、線分は相応の線分発生方法によって、直交座標ラ
スタ以外のラスタ上に発生され得る。しかし、本明細書
に説明した線分発生方法から当業者が容易に導き出し得
る上記その他の方法は総て、本明細書の特許請求の範囲
に含まれる。

【図面の簡単な説明】

第１図はフロントエンドシステムの概略的説明図、第２
図はラスタイメージプロセッサによって実行され得る処
理の説明図、第３図はラスタイメージプロセッサの概略
的説明図、第４図はVMEバスインタフェースの概略的説
明図、第５図はレーザ走査モジュールインタフェースの
概略的説明図、第６図はラスタイメージプロセッサの16
ビットプロセッサシステムの概略的説明図、第７図はラ
スタイメージバスインタフェースの概略的説明図、第８
図はVMEバスインタフェースのVMEマスタインタフェース
の概略的説明図、第９図はビットマップメモリ内での文
字の位置設定を示す説明図、第10図はビットマップメモ
リにおける幾つかの可能な操作の結果を示す説明図、第
11図はラスタイメージメモリの概略的説明図、第12図は
丸い端部を有する線分を示す説明図、第13図は点P1及び
P2を通る線を示す説明図、第14図は線と、該線の起点を
中心とする円との交点の決定を説明する細部説明図、第
15図は交点Ｓ^＊を決定する方法のフローチャート、第16
図はラスタ点上で像形成された線分を示す説明図、第17
a図、第17b図及び第17c図は丸い端部を有する線分を発
生する方法のフローチャート、第18図は真直な端部を有
する線分を示す説明図である。 10……フロントエンドコントローラ、11……I/Oプロセ
ッサ、12……ランダムアクセスメモリ、13……フォント
メモリ、14……VMEバス、15……ラスタイメージプロセ
ッサ、16……ラスタイメージメモリ、17……ラスタイメ
ージバス、18……ビデオライン、19……操作コンソー
ル、20……プリンタ、41……VMEバスインタフェース、4
2……ページ同期化インタフェース、43……中央処理装
置、44……レーザ走査モジュールインタフェース、45…
…RIバスインタフェース、46……ラスタイメージプロセ
ッサバス、47……データライン、48……アドレス及び制
御ライン、49……条件ライン、52……”走査開始”ライ
ン、53……バーストライン、54……クロックライン、56
……RIバスアドレス有効ライン、57……ビジーライン、
58……データ及びアドレスライン、70……アドレスシー
ケンサ、71……マイクロPROM、72……マイクロ命令レジ
スタ、73……命令変更回路、74……マイクロプロセッ
サ、75……条件セレクタ、76……状態バッファ、77……
待ちセレクタ、78……イネーブルブロック、79……ブラ
ンチアドレス制御ユニット、87……状態バス、97……”
待ち”ライン、100……マスタインタフェース、101……
スレーブインタフェース、102……インタラプタ、110…
…制御ブロック、111……レジスタ、112……シフトレジ
スタ、113……I/Oバッファ、120……”データ‐アウ
ト”レジスタ、121……”データ‐イン”レジスタ、122
……”アドレス‐ロー”レジスタ、123……”アドレス
‐ハイ”レジスタ、124……変更レジスタ、125……コン
トローラ、130……VME-MIコントローラ、131……バッフ
ァ、132……アドレス‐ハイカウンタ、133……アドレス
‐ローカウンタ、134……バッファ、135……両方向バッ
ファ、136……ミラー回路、137……データ‐インレジス
タ、138……データ‐アウトレジスタ、139……アドレ
ス、データ及び制御ライン、140……バス調整ライン、1
41……VMEアドレスバス、142……VMEデータバス、200…
…ビットマップ表現、201……文字、203,204,205……16
ビットワード、207……ワード境界、220……24メガビッ
トダイナミックメモリ、222……RMCレジスタ、223……
理論処理ユニット、225……データライン、226……デー
タ出力ライン、227……DATAOレジスタ、228……アドレ
ス／データバスバッファ、229……アドレスレジスタ、2
30……データ‐インレジスタ、231……メモリ制御回
路、232……アドレスマルチプレクサ、250,262……線
分、251……始点、252……終点、261……円、263……接
線、270〜274……領域。

Claims (4)

【特許請求の範囲】
1. 【請求項１】ラスタ点が幾本かの平行線を成して配置さ
   れた均一なラスタ上に太さＤの線分を発生する方法であ
   って、線分のビット表現をワード指向型のビットマップ
   メモリに多数の像点もしくは画素の形態で記憶させ、線
   分の輪郭を決定して該輪郭の像をラスタ点上で形成し、
   連続するラスタ線に関し線分を横切る横断線の長さを決
   定し、決定した長さのビット表現をビットマップメモリ
   内の対応する記憶場所に設置し、決定した前記長さの方
   向はビットマップメモリのワード方向に対応することを
   特徴とする方法。
2. 【請求項２】線分の始点及び終点の像をラスタ点上で決
   定し、前記線分の始点を中心とする、半径（Ｄ−１）/2
   の円を発生し、この円と線分の始点及び終点を通る線と
   の交点を囲む４個のラスタ点を決定し、前記交点のごく
   近傍に、該交点を通る前記円の接線に最も近いラスタ点
   を決定し、決定したこのラスタ点によって４個のラスタ
   交点を、像形成した輪郭上の点として決定することを特
   徴とする特許請求の範囲第１項に記載の方法。
3. 【請求項３】４個の前記ラスタ交点が線分の丸い端部輪
   郭線と真直輪郭線との接続点の像を構成することを特徴
   とする特許請求の範囲第２項に記載の、丸い端部を有す
   る線分を発生する方法。
4. 【請求項４】４個の前記ラスタ交点が線分の輪郭線の屈
   曲点の像を構成することを特徴とする特許請求の範囲第
   ２項に記載の真直な端部を有する線分を発生する方法。