JPH0736146B2

JPH0736146B2 - ランダムベクター処理方法

Info

Publication number: JPH0736146B2
Application number: JP60023967A
Authority: JP
Inventors: 継夫新浜
Original assignee: Toyo Electric Manufacturing Ltd
Current assignee: Toyo Electric Manufacturing Ltd
Priority date: 1985-02-08
Filing date: 1985-02-08
Publication date: 1995-04-19
Anticipated expiration: 2010-04-19
Also published as: JPS61183782A

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、静電式，レーザ式，感熱式などのラスタ走査
型出力装置に関するもので、出図すべき図形要素データ
列が各々の出図位置に関して全く配置されていない順序
で入力される時の処理方法に関する。

〔従来の技術〕

最近のコンピュータ利用図形処理システム（例えばCAD
など）の普及および高性能化に伴って、コンピュータシ
ステムの出図装置の高速化，低価格化が必要になり、そ
の一つの手段として従来のペン式xyプロッタ（機械駆動
ベクタ走査型自動製図機）に代えて、出図時間が出図デ
ータに依存せず、且つ比較的短い各種ラスタ走査型出図
装置が開発され知られている。

普通、このようなラスタ走査型出図装置の場合ラスタ走
査式グラフィックディスプレイと同様の考え方に基づ
き、全出図領域に対応するラスタイメージの記憶装置
（以下フレームメモリと称す）を置き、入力された図形
要素データについて逐次ベクターラスタ変換処理を施し
て、フレームメモリ上に展開して行き、図形要素データ
の終了を検出した後、フレームメモリをラスタ出力モー
ドに切り換え、一度に出図してしまうという方法がとら
れる。

しかしながら、このような出図装置のうち従来のペン方
式のxyプロッタとの置換を可能にするラスタ分解能を有
する装置においては、全出図領域をフレームメモリに記
憶するためには、その容量は大規模化して実用的ではな
い。

また、大容量外部記憶装置（例えば固定ディスク）をフ
レームメモリとして置く方法もあるが、ベクターラスタ
変換時のランダムアクセスのために高速化は実現できな
い。

それらを回避する手段として、描画装置の走査速度が比
較的遅く出図時間を要することに着目して、２個以上の
比較的小さいフレームメモリを置き、出図時にその小さ
いフレームメモリについてのみベクターラスタ変換処理
を施し、描画装置の出図時間に同期させてその時点で対
応するフレームメモリ内容をラスタ出力する方法が用い
られている。

しかしながら、装置に入力される図形要素データは当然
ペン式のxyプロッタを想定しており、そのデータの並び
の順序は出図される位置に関する配慮が全く払われない
のが普通である。従って、この方法の場合は何らかの手
段により、これからベクターラスタ変換処理を施そうと
するフレームメモリに対応する出図位置に存在する図形
要素データを抽出し、出図順に処理をする必要がある。

だが、一般に均質且つ大量な図形要素データを、出図さ
れる位置に関して「並びかえ」（以下ソートと称す）或
いは「小さい領域に割り付け」（以下マッピングと称
す）することは、全図形要素データについてこれらの処
理をする必要上、やはり大きい記憶容量および計算機時
間を要するので、本来の目的である大量高速出図を必ず
しも実現する方法とはいえず、より高速且つ簡便なラン
ダムベクター処理方法が望まれていた。

〔発明が解決しようとする問題点〕

以下、これまでに採られていたソートとマッピングの内
容について説明する。

先ず、ソート（sort）とはランダムベクターデータを出
力順に並び替えることであり、第６図および第７図を用
いて説明する。

第６図はベクター式プロッタによる出力図形例を示す図
で、第７図はラスタ式プロッタによる出力図形例を示す
図であり、両者同じＡ字形の図形を出力した場合を示し
ている。ｘ軸は垂直方向（用紙搬送方向）を、ｙ軸は水
平方向（用紙搬送と直角方向）を示す。

第６図に示したベクター式（ペン式）プロッタによる場
合には、データとして；点P1→点P2の線分；点P2→点P3の線分；点P4→点P5の線分が与えられ、図形出力としては与えられたデータ，
，の順に、点P1から点P2へ、点P2から点P3へ、点P4
から点P5へと描画する。このようにベクター式プロッタ
は入力順に逐次処理をすればよいが、ラスタ式プロッタ
では用紙搬送方向に従った順に処理をしなければならな
い。すなわち、この例ではデータよりもデータの方
を先に処理し、データでは点P4→点P5の線分としてで
はなく点P5→点P4の線分として処理しなければならな
い。

従って、第７図に示すラスタ式プロッタによる場合に
は、ソート処理を行いデータの順序を入れ替えると共
に、その内容も次のように変更する。

；点P1→点P2の線分；点P5→点P4の線分；点P2→点P3の線分このような処理の後ラスタ式プロッタでは用紙搬送方向
の順に描画を行なう。

この方式における問題点として、通常の大量な作図デー
タについてこの並べ替え処理を行うには、出力用として
入力と同じ容量の記憶を要するばかりでなく、他に比較
的大きい作業用の記憶容量を必要とし、また、全データ
の比較チェックを行うため、計算時間も膨大なものとな
る。従って、計算機資源の点からも、規模，価格の点か
らも、通常装置側でこの処理を行うのは現実的ではな
い。

次に、マッピング（mapping）とは、出力用の比較的小
さいフレームメモリに対応する矩形領域ごとに、そこに
存在するデータを切り出してグループ化することであ
り、第６図および第７図を用いて説明する。

第６図に示したベクター式プロッタによる図形をラスタ
式プロッタにより出図する場合には、第７図に示すよう
に全体の出力領域を小さいフレームメモリに対応する矩
形領域I,II,IIIに分割し、各々の入力データについて小
さいフレームメモリに対応するどの矩形領域に入るかを
チェックして各矩形領域に分割して記憶する。

その際、複数の矩形領域にわたるデータについては、本
例ではデータおよびデータがそれぞれ矩形領域I,II
およびII,IIIにわたっているが、その境界点Q1およびQ2
によりデータを分割しデータを加工して次のように各矩
形領域ごとにグループ分けをする。

グループI;データ；点P1→点Q1の線分グループII;テータ；点Q1→点P2の線分データ；点P2→点Q2の線分データ；点P4→点P5の線分グループIII;データ；点Q2→点P3の線分このような処理により全データについて「切り出し」と
「グループ化」が終了すると、用紙搬送方向順にその矩
形領域をベクターラスタ変換しながら出図すればよい。

この方式における問題点として、通常の大量の作図デー
タ全てについてこの交点処理計算を行うには、やはり膨
大な計算時間を要する。また、グループ分けされた形式
のデータは、入力用の記憶より当然大きい容量が要求さ
れる。従って、計算機資源の点からも、規模，価格の点
からも、通常装置側でこの処理を行うのは現実的ではな
い。

本発明は、上記従来の欠点に鑑み、ベクター式プロッタ
用として作成されたランダムベクターデータ列を入力す
るに当り、全データについての並べ替えや交点計算等の
負担の大きい処理を必要とせず、且つ小規模なハードウ
エアで、装置側にて高速にラスタ描画を可能とするため
の処理方法を提供することを目的とするものである。

〔発明の概要〕

本発明のランダムベクター処理方法は、ラスタ走査式描
画装置と制御用マイクロプロセッサと記憶装置とを有す
るラスタ走査形出図装置において、ラスタ走査式描画装
置に出力する時の処理順序に全てのラスタに対応するチ
ェインポインタを格納し得るチェインポインタテーブル
領域（2b）と、各図形要素ごとにチェインポインタ（2c
1）を持ちランダムベクター全ての図形要素データ（2c
2）を格納する図形要素格納領域（2c）とを確保してお
く。

図形要素データ（2c2）を順次図形要素格納領域（2c）
に格納するが、格納に際してチェインポインタテーブル
領域（2b）と、図形要素格納領域（2c）に格納された各
図形要素データ（2c2）に付したチェインポインタ（2c
1）とを結合し、処理順序に反映させる図形要素データ
格納手段による。

これを具体的に説明すると、制御用マイクロプロセッサ
（１）からの図形要素データの読み込みを開始するに先
立ち、チェインポインタテーブル領域（2b）の各記憶番
地の内容を＃Ｎとし、その番地の値を＃Ｎとしておく。
続いて、図形要素データを図形要素格納領域（2c）に順
次格納するが、その図形要素の最初のｘ軸位置に対応す
るチェインポインタテーブル領域（2b）の番地の内容
を、その図形要素データのチェインポインタとして付す
と共に、その図形要素データの格納番地をそのチェイン
ポインタテーブル領域（2b）の記憶番地に格納する。こ
の作業をチェイン手段の実施と称する。

このようにして全図形要素データの格納を終了した後、
全出図領域を小さいフレームメモリ領域（2d）に対応す
る矩形領域（I,II,III）ごとに区分して、図形要素格納
領域中の図形要素データをフレームメモリ領域（2d）に
記憶させる。フレームメモリ領域（2d）は２個以上あれ
ばよい。

すなわち、出図処理時にはチェインポインタテーブル領
域（2b）のアドレス情報に応答して所定の順序処理を実
現するようにした出力手段による。

これを具体的に説明すると、チェインポインタテーブル
領域（2b）のうち、現在処理中の矩形領域の最初のｘ軸
から順に対応する図形要素格納領域（2c）のチェインポ
インタ（2c1）の番地の内容が、そのデータの番地を指
しているかどうかをチェックし、その番地を指していれ
ば次の番地に進む。その内容がそのデータの番地を指し
ていない場合は、その番地に格納されている図形要素デ
ータ（2c2）は、今処理しているｘ軸位置を始点とする
図形要素のものであるから、その図形要素データをベク
ターラスタ変換して、フレームメモリ領域（2d）内に記
憶する。

フレームメモリ領域（2d）内への記憶を終了したなら
ば、チェインポインタ（2c1）の示す番地へ進む。チェ
インポインタ（2c1）の示す番地が図形要素格納領域（2
c）のものであれば、前記のようにしてフレームメモリ
領域（2d）内へ記憶する。チェインポインタ（2c1）の
示す番地がチェインポインタテーブル領域（2b）のもの
の場合は、その番地の値をそのチェインポインタテーブ
ル領域（2b）に格納した後、その処理を行う。すなわ
ち、そのデータの番地の内容がその番地の値を指してい
るので、チェインポインタテーブル領域（2b）の次の番
地に進む訳である。

矩形領域（I,II,III）は小さいので、大きい図形要素は
複数のフレームメモリにわたってしまう。しかしなが
ら、フレームメモリ領域（2d）に記憶するためのベクタ
ーラスタ変換は、通常DDA（ディジタル微分解析器）等
で行うので、途中座標が実行中に認識できるため、もし
実行中にフレームメモリ領域（2d）に対応する矩形領域
のｘ軸値を超える場合には、次のフレームメモリにデー
タを渡すために図形要素格納手段を実行する。すなわち
チェイン手段を実施する訳で、次の矩形領域の最初のｘ
軸位置に対応するチェインポインタテーブル領域（2b）
の番地の内容をチェインポインタとして付すと共に、そ
の図形要素データの格納番地をそのチェインポインタテ
ーブル領域（2b）の番地に格納した上で、図形要素デー
タ次のフレームメモリ以下のデータに変更して記憶させ
る。

これらの作業を繰り返し、現在処理中の矩形領域の最後
のｘ軸位置に対応するチェインポインタテーブル領域
（2b）の処理が終ると、そのフレームメモリの処理は終
了したことになり、ラスタ走査式描画装置への出力が可
能となる。

従って、ラスタ走査式描画装置により、処理終了後のフ
レームメモリ出力を描画しながら、次の矩形領域につい
て前記の出力手段を実行して、別のフレームメモリに対
して図形要素データをベクターラスタ変換の上、記憶さ
せることを繰り返し全出図領域を描画することができ
る。

〔実施例〕

以下、本発明にかかるランダムベクター処理方法をプロ
グラム制御により実施した場合の実施例につき図面を用
いて説明する。

第１図は本発明を実施するためのラスタ走査型出図装置
の全体構成を示すブロック図、第２図は第１図の図形要
素格納領域内の詳細図であり、第１図，第２図におい
て、本発明の処理方法は、制御用マイクロプロセッサ
（以下CPUという）（１），制御プログラムと二つのメ
モリ領域と二つ以上のフレームメモリを有する記憶装置
（２），ラスタ走査式描画装置（３）および出力装置用
インターフェイス（４）から構成されており、記憶装置
（２）内には制御用プログラムを記憶した制御用プログ
ラム領域（2a）の他に、作業用メモリ領域として、二つ
のメモリ領域の内の一つとしてチェインポインタテーブ
ル領域（以下CTという）（2b），他の一つである図形要
素格納領域（以下SEGという）（2c）と、フレームメモ
リ領域（以下FMという）（2d）が確保されている。

CT（2b）は全出図領域のｘ軸の走査線数分の要素数を有
し、最初の走査線から最後の走査線に至る順に、各アド
レス（番地）の内容が対応している。

SEG（2c）はランダムベクターとしての図形要素データ
を記憶する部分であり、一つずつの図形要素データを格
納する格納アドレス（番地）を以降＠Ａで表すこととす
る。一つの図形要素の格納構造は第２図に示した概念図
のごとくであり、ランダムベクタの格納アドレス＠Ａの
記憶部分には、データのチェーン状態を書いておく部分
としてのチェインポインタ（以下CPTRという）（2c1）
と、図形要素データ（以下DATAという）（2c2）を格納
する部分とがある。

CT（2b）は、Ｘ軸の座標とSEG（2c）に格納された図形
要素とを結合させるために設けたもので、SEG（2c）内
に記憶されたCPTR（2c1）は、対応する図形要素とその
最初のｘ軸およびそのｘ軸に関係付けられる他の図形要
素とを結合するためのものである。

次にFM（2d）について説明する。

全出図領域をＸ軸方向に多数の小さい矩形領域（I,II,I
II）に等分し、この小さい矩形領域一つの中の全てのラ
スタ情報に対応する大きさを有するフレームメモリを複
数個確保する。本実施例ではFM（2d）内には、３個の矩
形領域（I,II,III）を確保している。

次に、第１図，第２図を参照しながら図形要素データの
入力処理について、第３図のフローチャートと第４図
（ａ）のメモリ内容図および第４図（ｂ）の図形要素図
によって説明する。

入力処理前の初期状態では、CT（2b）の全ての要素、つ
まり総てのアドレスの内容にそのアドレスを記憶させて
おく。（第３図のイ）第４図（ａ）では、＃0,＃1,……でもって示している。

次に、第１図に示すように、CPU（１）から図形要素デ
ータを順次データの続く限り読み込んでいく。（第３図
のロ） CT（2b）では、第４図（ｂ）に示すように、点P1（10,1
0）→点P2（40,70）の直線が図形要素データ＠として読
み込まれた場合、その図形要素データＡのＸ軸の最小値
X_MINを求め、第４図（ａ）に示すように、X_MIN＝10を知
る。（第３図のハ）その後、この値を印字単位の数値Ｎとする。（第３図の
ニ）なお、印字単位を例えば１とすると、Ｎ＝１×10＝
10となる。

ここで、CT（2b）の各アドレス（番地）の値を＃Ｎで表
す。

次にSEG（2c）内の空きエリアを探し、そのアドレス＠
Ａが、第４図（ａ）に示すように、＠０であったとす
る。（第３図のホ）なお、ここではSEG（2c）の空エリ
アを見付ける操作を行っているが、この操作を行わず順
番にSEG（2c）に入力する場合もある。

ここでCT（2b）とSEG（2c）とのチェイン手段を実施す
る。

X_MIN（＝10）に対応するチェインポインタテーブル領域
（2b）内のアドレス（＃10,これは第４図（ｂ）の図形
データから第11番目の走査線に対応するアドレスであ
る）の記憶内容（＃10,初期状態では総てのアドレスの
内容を記憶したそのときのアドレスと同じである）を、
図形要素データを格納すべきアドレス＠０のCPTR（2c
1）格納部分に格納する共に、記憶内容をそのアドレス
（＠０）に変更する。すなわち、CT（2b）内のアドレス
＃10の記憶内容が＃10から＠０に変更される。同時に、
SEG（2c）内のアドレス＠０のDATA（2c2）格納部分に図
形データ（P1→P2の直線のデータ）記憶する。（第３図
のへ）更に、前述したように、その図形要素データの格納番地
をそのCT（2b）の記憶番地を格納する。（第３図のト）次に、点P2（40,70）→点P3（70,10）の直線がデータ
として読み込まれると、X_MIN＝40であるから、CT（2b）
内のアドレス＃40の記憶内容を＃40から＠１に変更する
と共に、SEG（2c）内のアドレス＠１のCPTR（2c1）部に
＃40を、DATA（2c2）部に図形データ（P2→P3の直線の
データ）を記憶して、第３図のトと同じ操作となる。

続いて、点P4（60,30）→点P5（20,30）の直線がデータ
として読み込まれると、X_MIN＝20であるから、CT（2
b）内のアドレス＃20の記憶内容＃20から＠２に変更す
ると共に、SEG（2c）内のアドレス＠２のCPTR（2c1）部
に＃20を、DATA（2c2）に図形要素データ（P5→P4の直
線のデータ）を記憶して、第３図のトと同じ操作とな
る。

次に、点P6（80,10）→点P7（80,70）の直線データと
して読み込まれると、X_MIN＝80であるからCT（2b）内の
アドレス＃80の記憶内容を＃80から＠３に変更すると共
に、SEG（2c）内のアドレス＠３のCPTR（2c1）部に＃80
（第４図（ａ）のα）を、DATA（2c2）部に図形データ
（P6→P7の直線のデータ）を記憶して、第３図のトと同
じ操作となる。

続いて、点P7（80,70）→点P8（120,70）の直線がデー
タとして読み込まれると、X_MIN＝80であるから、CT
（2b）内のアドレス＃80の先に変更されている内容＠３
を皿に＠４に変更すると共に、SEG（2c）内のアドレス
＠４のCPTR（2c1）部に＠３（第４図（ａ）のβ）を、D
ATA（2c2）部に図形データ（P7→P8の直線のデータ）を
記憶して、第３図のトと同じ操作となる。

すなわち、データとデータは共にX_MIN＝80であり、
両図形要素のＸ軸の最小値が同じであるため、CPTR（2c
1）により、＃80→＠４→＠３（第４図（ａ）のγ）と
チェインされている様子を示している。このようにして
全ての図形要素データの読み込みを終り、入力データが
無くなると出図制御へと進む。本段階では、CT（2b）内
のアドレス＃100の内容は、当然＃100となっている。な
お、第３図のフローチャート中で、＠Ａは、図形データ
Ａの格納アドレスを、（）は、アドレスの内容を示し
ている。

次に出図制御について説明する。本実施例では全出図領
域を走査線100本で構成される小矩形領域（第１図のI,I
I,III）に分割し、FM（2d）を３個確保しているので、
I,II,IIIの順で描画が完了したフレームメモリに対し
て、図形データのベクターラスタ変換結果を記憶させる
ようになっている。

第５図は出図制御に関するフローチャートである。

第５図において、出図時はｘ軸が０から最大値に至るま
での全ての走査線について順に制御する必要があり、CT
（2b）のアドレス順つまり（ａ）の＃０からその内容を
チェックし、その値Ｎが現在チェックしているアドレス
と等しいか或いはそうでないかのチェックを行う。
（ｂ）等しい場合は、そのアドレス処理は完了とし次のアドレ
ス（ｃ）に進む。

その内容にSEG（2c）のアドレス（＠Ａ）が書かれてい
た場合（ｄ）は、その内容が処理すべき図形要素データ
である。

そこで、チェインをほどく手段（アンチェイン手段）を
実行する。アンチェイン手段は、SEG（2c）内のアドレ
ス＠ＡのCPTR（2c1）部の内容を、CT（2b）内の現在の
アドレスの内容として格納することによって行われる。

すなわち、第１にCT（2b）の内容を前記SEG（2c）のCPT
R（2c1）の内容（ｅ）とし、第２にSEG（2c）のDATA（2c2）をベクターラスタ変換
（ｆ）とする。

次に、このラスタデータ矩形領域（Ｉ）を越えていない
かどうかのチェックを行う。（ｇ）フレームメモリの矩形領域（Ｉ）を越えない場合は、矩
形領域（Ｉ）に記憶させる。（ｈ）フレームメモリの領域を越える場合には、フレームメモ
リのＸ座標の領域境界値を新たにそのデータとする。
（ｉ）なお、詳細な説明は後述する第4,5図で説明する。

そのデータのCT（2b）のアドレス（＠Ａ）の内容を前述
した入力処理に従ってSEG（2c）のCPTR（2c1）に、入力
データの印字位置の値に対応するCT（2b）のアドレスの
内容を、SEG（2c）のCPTR（2c1）に記憶させ、且つその
CT（2b）のアドレス（＠Ａ）を前記のCT（2b）に記憶さ
せた後、領域境界値内と新たに設けた境界値とのラスタ
データをFM（Ｉ）に記憶させる。

Ｘ座標の領域境界値を越える場合と越えない場合の両者
の処理ののち、再度CT（2b）のアドレスの内容をチェッ
クし、その値がアドレス値に等しくなるまで前記処理を
繰り返し、フレーム境界のアドレス値になるまでCT（2
b）のアドレス処理を進め、フレーム境界アドレスに達
するまでこの操作を行う。（ｋ）そして、フレーム境界アドレスに達したのち、そのFMI
は出図可能（ｍ）とし、出図印字はフレームメモリ単位
に行い、他のフレームメモリ（II,III）に対しても同様
の操作を行う。

なお、出図限界まで本操作を行うが、出図限界はフレー
ムメモリ単位で行うため、その記述は省く。

次に、第５図に基づいて第４図（ａ），（ｂ）の実施例
を説明する。

第４図（ａ），（ｂ）において、CT（2b）の最初のアド
レス＃０（第５図のａ）から順にその内容をチェックし
て行く。（第５図のｂ）アドレス＃９まではその内容が現在チェックしているア
ドレスの値を指しているので、順に次のアドレス（第５
図のｃ）へ進んで行く。アドレス＃10の内容をチェック
すると、＃10と異なり、＠０（第５図のｄ）であるの
で、ここにｘ軸10を始点とする図形要素データが格納さ
れていることが判る。従ってアンチェイン手段を実行
し、アドレス＠０のCPTR（2c1）部の内容である＃10を
アドレス＃10（第５図のｅ）に格納する。これにより、
アドレス＃10の内容は現在チェックしているアドレスの
値を指しているものとなる。

アンチェイン手段を実行後、アドレス＠ＡのDATA（2c
2）部の図形データにつきベクターラスタ変換を行う。
（第５図のｆ）次に、図形データがフレームメモリの矩形領域を超える
かどうかをチェックする。（第５図のｇ）第４図（ｂ）のデータは、Ｘ軸の値が10〜40であり、
FM（Ｉ）は０〜99の範囲を超えないのでそのままベクタ
ーラスタ変換結果をFM（Ｉ）に記憶させる。（第５図の
ｈ）続いて、CT（2b）のアドレス＃10の内容をチェックする
と、今チェックしているデータの値を指しているので、
順に次のアドレス（第５図のｃ）へ進んで行く。そして
アドレス順にアドレスの内容をチェックくしていくと、
第４図（ａ）に示すように次のアドレス＃20であり、そ
の次はアドレス＃40であるが、前記と同様にしてベクタ
ラスタ交換を行い、その結果をフレームメモリに記憶さ
せながら次々に進み、点p1→点p2,点p5→点p4,点p2→点
p3の各直線を矩形領域（Ｉ）に記憶させる。

次に点P6→P7において、CT（2b）のアドレス＃80の内容
をチェックすると、＃80と異なり＠４であるからアンチ
ェイン手段を実行し、＠４のCPTR（2c1）部の内容であ
る＠３をアドレス＃80に格納（第４図のγ）したのち、
アドレス＠４のDATA（2c2）部の図形データにつきベク
ターラスタ変換を行う。（第５図のｈ）ベクターラスタ変換はDDA（ディジタル微分解析器）に
より実施され、漸化式手法を用いて行われるので、途中
座標は実行中に認識できる。

アドレス＠４のDATA（2c2）部の図形データは、点P7（8
0,70）→点P8（120,70）の直線のものであるので、FM
（Ｉ）は０〜99の範囲を超えている。（第５図のｇ）そこで、前述したように、フレームメモリの領域を越え
る場合（第５図のｋ）には、フレームメモリのＸ座標の
領域境界値を新たにそのデータとする（第５図のｉ）こ
とによって、フレームメモリに対応する現在の矩形領域
の境界線との交点P9から、後の図形データを次のフレー
ムメモリに渡す処理をする。

すなわち、ここで再びチェイン手段を実施（第５図の
ｊ）し、点P9でのCT（2b）のアドレス＃100の内容を＠
４とし、SEG（2c）のアドレス＠４のCPTR（2c1）部に＃
100を、DATA（2c2）部に点P9（100,70）→点P8（120,7
0）の直線の図形データを格納する。｛第４図（ｃ）｝
しかるのち、ベクターラスタ変換を終わった点P7→点P9
のデータを矩形領域（Ｉ）に記憶（第５図のｈ）させ、
元のアドレス＃80の内容をチェックする。

CT（2b）のアドレス＃80の内容は、先に＠４から＠３に
置き換えられてはいるが、今のアドレスの値（第５図の
α）とは異なるので、アンチェイン手段を実行し、アド
レス＠３のCPTR（2c1）部の内容である＃80をアドレス
＃80に格納したのち、アドレス＠３のDATA（2c2）部の
図形データにつきベクターラスタ変換を行う。（第５図
のｆ）アドレス＠３の図形データは点P6→点P7の直線であるか
ら、ベクターラスタ変換に際してフレームメモリ範囲を
超えることはなく、変換結果をそのままフレームメモリ
に記憶させて後、元のアドレス＃80の内容をチェックす
ると、今度はそのアドレスの値を指しているので、この
走査線上から始まる図形データの処理は終わったことを
知り次のアドレス（第５図のｃ）に進む。そして、点P9
→P8に関しては、前述した同様な手段によって例えばFM
（II）に記憶させる。

このようにして順次CT（2b）のアドレスの内容をチェッ
クし、現在処理中の矩形領域の走査線に対応するアドレ
スのチェックを全て終わると、そのフレームメモリから
の出図を可能（第５図のｍ）とし、FMI,FMII,FMIIIのう
ちいずれか使用可能のフレームメモリを用いて次の矩形
領域についての処理に移行する。

〔発明の効果〕

ラスタイメージのメモリ効率は、より抽象度の高いベク
ターデータによるメモリ効率に比べると非常に劣るもの
である。特に、ペン式xyプロッタとの置換を可能にする
レベルのラスタ分解能を持つ装置の場合にはより顕著と
なる。

例えば、全出図領域がｘ軸方向2m,y軸方向1mのものを考
え、10dot/mmのラスタ走査型出図装置とした場合、全出
図領域をフレームメモリとして置くと、ｘ軸方向に2000
0ビット,y軸方向に10000ビットの記憶容量を要するので
全記憶容量として（10000×20000/8）＝25Mバイトを要する。

一方、ベクターイメージで一本の直線を記憶するとすれ
ば、せいぜい数バイトで済ませることができるので、例
えば８バイトを要するものとする。

前記の実施例では１つの矩形領域の走査線数を100とし
たが、400本程度としても１つのフレームメモリは0.5M
バイトあればよい。

全走査線数は20000本であるから、CT（2b）の要素数は2
0000であり、記憶内容を物理アドレスで持つとして４バ
イトを要するとすると、CT（2b）のために、20000×４
＝80000バイトを要する。

記憶しておくべき図形要素の数をＸとすると、SEG（2
c）の各要素にはCPTR（2c1）部に４バイト、DATA（2c
2）部に８バイトを要するので、合計12バイトを要し、
全図形要素格納領域（2c）には、Ｘ×12バイトを必要と
する。

今、全出図領域を１つのフレームメモリとした場合に必
要な25Mバイトの1/5である5Mバイトを本発明にかかる方
式の出図装置の記憶装置の容量とした場合、処理できる
図形要素データ数Ｘは、Ｘ＝｛（5000×10³−1500×10³−80×10³）/12｝＝285000 となり、1m×2mの出図領域中の図形要素として28万要素
もあれば十二分のものとなる。

先に発明が解決しようとする問題点の項で記載したsort
による方法やmappingによる方法によっても、記憶装置
の容量としてはほぼ同等のもので済むが、計算機時間が
膨大なものとなる。

すなわち、sortによる方法によれば、データ数の増大に
伴って並べ替えのための計算き時間が指数関数的に増大
することが一般に知られており、例えば、上記28万の図
形要素数を取り扱う場合には、本発明にかかる方法に比
べて少なくとも100倍以上の時間を要する。

また、mappingによる方法による場合には境界線との交
点処理計算に膨大な計算時間を要し、本発明にかかる方
法に比べて10〜100倍の時間を要する。

以上詳細に説明したように、本発明にかかるランダムベ
クター処理方法によれば、小容量の記憶装置を有効に利
用し、ベクター式プロッタ用として作成されたランダム
ベクターデータ列を入力するに当り、全データについて
の並べ替えや交点処理計算等の時間のかかる処理を必要
としないので、高速にラスタ描画を実施することができ
る。

【図面の簡単な説明】

第１図は本発明にかかるランダムベクター処理方法を実
施するためのラスタ走査型出図装置のブロック図、第２
図は図形要素の格納構造を示す概念図、第３図はデータ
格納時の制御手段のフローチャート、第４図（ａ）はメ
モリ内容図、第４図（ｂ），（ｃ）は図形要素図、第５
図出図制御に関するフローチャートであり、第６図はベ
クター式プロッタによる出力図形例、第７図はラスタ式
プロッタによる出力図形例を示す図である。１……制御用マイクロプロセッサ、２……記憶装置、３
……ラスタ走査式描画装置、４……出力装置用インター
フェイス、2a……制御用プログラム領域、2b……チェイ
ンポインタテーブル領域（CT）、2c……図形要素格納領
域（SEG）、2c1……チェインポインタ（CPTR）、2c2…
…図形要素データ（DATA）、2d……フレームメモリ領域
（FM）I,II,III……矩形領域。

Claims

【特許請求の範囲】

【請求項１】図形要素の出力位置に関して、全く任意な
順序のデータ列を入力して出図するラスタ走査型出力方
法において、二つのメモリ領域と、二つ以上のフレームメモリ領域を
有し、メモリ領域の一つは、アドレスは用紙の出図方向のＸ座
標走査線の単位（印字単位）とするチェインポインタテ
ーブル領域（2b）であり、他のメモリ領域の一つは、チェインポインタ（2c1）
と、各図形要素データ（2c2）とを有する図形要素格納
領域（2c）であり、二つ以上のフレームメモリ領域（2d）は、出図図面に対
応したメモリで、全出図領域をＸ軸方向に複数の矩形領
域（I,II,III）に等分したものであり、入力処理として、データ入力前に、初期操作としてチェ
インポインタテーブル領域（2b）をそのアドレスとし、
その後制御用マイクロプロセッサ（１）で入力データ
を、始終点座標を含む図形要素データに分解し、その図
形要素データを印字単位の値に換算し、図形要素格納領
域（2c）にデータを記憶させると同時に、図形要素デー
タの印字位置の値に対応するチェインポインタテーブル
領域（2b）のアドレスの内容を、図形要素データのＸ軸
の最小値を求めて図形要素格納領域（2c）のチェインポ
インタ（2c1）に記憶させ、且つそのチェインポインタ
（2c1）のアドレスを前記のチェインポインタテーブル
領域（2b）に記憶させるよう全データに対してこれらの
処理を行い、出図処理として、チェインポインタテーブル領域（2b）
のアドレス順にその内容をチェックし、その値が現在チ
ェックしているアドレスと等しい場合は、そのアドレス
処理は完了とし、その内容に図形要素格納領域（2c）の
アドレスが書かれていた場合は、第１にチェインポインタテーブル領域（2b）の内容を前
記図形要素格納領域（2c）のチェインポインタ（2c1）
の内容とし、第２に図形要素格納領域（2c）の図形要素データ（2c
2）をベクターラスタ変換し、ラスタデータとしてフレ
ームメモリの領域を越えない場合はフレームメモリ領域
（2d）に記憶させ、フレームメモリの領域を越える場合
には、フレームメモリのＸ座標の領域境界値を新たにそ
のデータとし、そのデータのチェインポインタテーブル
領域（2b）のアドレスの内容を図形要素格納領域（2c）
のチェインポインタ（2c1）に、図形要素データの印字
位置の値に対応するチェインポインタテーブル領域（2
b）のアドレスの内容を、図形要素格納領域（2c）のチ
ェインポインタ（2c1）に記憶させ、フレームメモリ領
域（2d）内のラスタデータをフレームメモリに記憶さ
せ、Ｘ座標の領域境界値を越える場合と越えない場合の
両者の処理ののち、再度チェインポインタテーブル領域
（2b）のアドレスの内容をチェックし、その値がアドレ
ス値に等しくなるまで前記処理を繰り返し、フレーム境
界のアドレス値になるまでチェインポインタテーブル領
域（2b）のアドレス処理を進め、フレーム境界アドレス
に達したのち、そのフレームメモリは出図可能とし、出
図印字はフレームメモリ単位に行い、他のフレームメモ
リに対しても同様の操作を行うようにしたことを特徴と
するランダムベクター処理方法。