JPH0652329A - 直線描画及び多角形塗潰し装置 - Google Patents

Abstract

(57)【要約】 【目的】直線の描画或いは多角形の塗潰しを行うときの
処理の高速化を図る。 【構成】直線描画の辺データ管理を示すステータスを辺
データ管理テーブルにセットし、与えられた座標列から
二組の座標を取出し描画に必要な情報を求め、辺データ
に始点のＸ座標、終点のＸ、Ｙ座標、描画に必要な情報
をセットし、バケットにその辺データのアドレスをセッ
トする。そして一本目の直線であれば辺データのアドレ
スを辺データ管理テーブルにセットし、一本目でなけれ
ば辺データのアドレスを前の辺データの順序リンクポイ
ンタにセットする。座標組が最後の直線でなければ同様
の処理を繰返し、また最後の直線であれば辺データの順
序リンクポインタに一本目の直線の辺データポインタを
セットする。最後にリンクしている辺データリストのポ
インタとＹ座標、辺データへのポインタの組数を辺デー
タ管理テーブルにセットする。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ディスプレイやプリン
タに直線を描画したり、多角形塗潰しを行う装置に関す
る。

【０００２】

【従来の技術】従来、直線の描画装置としては特開平３
−１４４８６７号公報のものが知られており、また多角
形塗潰し装置としては特開平１−１６６１８１号公報の
ものが知られている。

【０００３】前者のものは、ドット発生点のマトリック
スの一辺に平行なスキャンラインを、そのスキャンライ
ンに垂直な方向に順次シフトさせて直線パターンを形成
し、その際、形成すべき理想直線のスキャンラインに対
する傾きに基づいて、１つのスキャンライン上に発生さ
せる基本のドット数を求め、発生させたドットの位置と
理想直線との間の誤差をスキャンラインのシフト毎に累
積し、その累積結果から、次のスキャンライン上に発生
させるべきドットの数ｎがＮとＮ＋１とのいずれである
か、又はＮとＮ−１とのいずれであるかを判定し、この
判定結果に応じた数のドットを、所定のワード幅に対応
して設けられたバッファレジスタに発生させ、このバッ
ファレジスタの内容を、ドット発生点のマトリックスに
対応して設けられたビットマップメモリに転送して直線
を描画するものである。

【０００４】また後者のものは、ベクトル表現された多
角形の塗潰し処理を、各ベクトルがベクトル基端のＹ座
標と対応して該基端のＸ座標昇降順で連結登録される手
段と、Ｙ軸方向へ歩進移動するＸ軸と平行なスキャンラ
インのベクトル基端到達をベクトル基端の登録Ｙ座標の
利用により検知する手段と、該検知が行われる毎に検知
基端のベクトルに関する登録内容を読出して登録内容連
結順で蓄積する手段と、次の歩進位置でスキャンライン
と交差しない多角形構成辺の蓄積内容を削除する手段
と、次歩進位置のスキャンラインと多角形構成辺とが交
差する点のＸ座標にベクトル基端のＸ座標を更新する手
段と、更新済みの各Ｘ座標を大小比較して登録内容連結
順で登録内容が蓄積されているか否かを判断する手段
と、登録内容連結順で蓄積されていない旨の判断が行わ
れたときのみ蓄積内容を該連結順でソートする手段と、
前回のスキャンライン歩進位置で更新されたＸ座標間に
登録内容連結順方向へ塗潰し画素を配列する手段とで行
うものである。

【０００５】

【発明が解決しようとする課題】このような従来装置で
は、与えられた座標列から直線を描画する処理、或いは
座標列が構成する多角形の塗潰しの処理を行い、その後
同じ座標を与えて直線を描画する処理、或いは座標列が
構成する多角形の塗潰し処理を行う場合、同じ座標列で
あるにもかかわらず、処理のたびに同じ直線の情報を求
めるため、計算の重複が行われ処理の高速化を図ること
ができなかった。

【０００６】そこで本発明は、直線の描画処理或いは多
角形の塗潰しに利用した情報を保存し、その保存した情
報の座標列と同一の座標列が与えられたとき保存情報を
利用して直線の描画処理或いは多角形の塗潰しを行うこ
とにより処理の高速化を図る直線描画及び多角形塗潰し
装置を提供しようとするものである。

【０００７】

【課題を解決するための手段】本発明は、座標列が与え
られて行われる直線の描画処理の際に作成した直線の情
報又は直線が構成する多角形を塗潰す処理の際に作成し
た直線の情報を持つ辺データを、順序リンクポインタで
直線が発生する順番にリンクさせる手段と、与えられた
座標列が発生する直線の一本目の辺データへのポイン
タ、Ｙ座標値、このＹ座標値にリンクする辺データへの
ポインタ及びその組数、管理する辺が直線の描画の辺デ
ータか多角形を塗潰す処理で多角形を台形分割して得ら
れた辺データかを示すステータスを管理する辺データ管
理テーブルと、この辺データ管理テーブルが管理する情
報を処理に応じて段階的に作成し変更する管理情報変更
手段を設け、辺データ管理テーブルの管理情報を利用し
て直線描画及び多角形塗潰しの処理を行うものである。

【０００８】

【作用】このような構成の本発明においては、座標列が
与えられて直線の描画の処理、或いは直線が構成する多
角形を塗潰す処理の際作成した直線の情報を持つ辺デー
タを、順序リンクポインタにより直線が発生する順番に
リンクさせる。また与えられた座標列が発生する直線の
一本目の辺データへのポインタ、Ｙ座標値とそのＹ座標
値からリンクする辺データへのポインタ、それらの組数
をそれぞれ辺データ管理テーブルで管理するとともに辺
データ管理テーブルが管理する辺が直線の描画の辺デー
タか多角形を塗潰す処理で多角形を台形分割して得られ
た辺データかを示すステータスも辺データ管理テーブル
で管理する。

【０００９】そして同じ座標列が与えられ再び同じ直線
の描画或いは多角形の塗潰しが行われるときには辺デー
タ管理テーブルが管理する情報を利用して直線描画及び
多角形塗潰しの処理を行う。また辺データ管理テーブル
が管理する情報を処理に応じて段階的に作成し変更す
る。すなわち最初に直線描画の処理をした場合は、直線
の辺データを作成して管理しておき、後の直線描画の処
理、或いは多角形の塗潰しに必要な台形の辺データ作成
に利用する。最初に多角形を塗潰した場合は直線の辺デ
ータを作成し、多角形の塗潰しに必要な台形の辺データ
作成処理を順次行い、後の直線描画の処理、或いは多角
形の塗潰しに利用する。

【００１０】

【実施例】以下、本発明の実施例を図面を参照して説明
する。

【００１１】図１はブロック図で、１は座標入力部、２
は辺データ管理テーブル作成部、３は交差処理部、４は
直線描画部、５は多角形塗潰し部、６は辺データ分割
部、７はフレームメモリ、８はワークメモリである。こ
れらはバスライン９を介して接続されている。前記辺デ
ータ管理テーブル作成部２、交差処理部３、直線描画部
４、多角形塗潰し部５、辺データ分割部６はＣＰＵ（中
央処理装置）及びＲＯＭ（リード・オンリー・メモリ）
により構成され、フレームメモリ７及びワークメモリ８
はＲＡＭ（ランダム・アクセス・メモリ）により構成さ
れている。

【００１２】前記フレームメモリ７には図５の(a) に示
す構成の辺データ管理テーブル１０や図８に示すアクテ
ィブ辺テーブル１３を形成するとともに図５の(b) に示
す構成の辺データ１１や図６に示す構成のバケット１２
等を格納するようになっている。また前記ワークメモリ
８はデータ作成時等におけるデータ処理に使用されるよ
うになっている。

【００１３】図１に示すブロックは図２に示す流れ図に
基づく処理を行うようになっている。先ずＳ1 にて辺デ
ータ管理テーブル１０の状態を示すステータスｎ1 にnu
llをセットしておく。この状態で座標入力部１により座
標列が与えられると、Ｓ2 にて前記辺データ管理テーブ
ル作成部２は辺データ管理テーブル１０がすでに作成さ
れているか否かをチェックし、辺データ管理テーブル１
０が作成されていなければ、Ｓ3 にて直線描画の辺デー
タを作成し辺データ管理テーブル１０に登録する。すな
わち辺データ管理テーブル１０の作成処理を行う。そし
てＳ4 にて直線を描画する処理か否かをチェックし、直
線描画の処理であればＳ5 にて前記直線描画部４は辺デ
ータ管理テーブル１０から直線の情報を得て描画する。

【００１４】また直線描画の辺データ管理テーブル１０
がすでに作成され、直線描画の処理であれば前記直線描
画部４は直ちにＳ5 にて辺データ管理テーブル１０から
直線の情報を得て描画する。

【００１５】また多角形の塗潰し処理であればＳ6 にて
前記多角形塗潰し部５は台形辺の辺データ管理テーブル
１０がすでに作成されているか否かをチェックし、台形
辺の辺データ管理テーブル１０が作成されていなければ
Ｓ7 にて台形の辺データを作成し、辺データ管理テーブ
ル１０に登録する。そしてＳ8 にて台形辺の辺データ管
理テーブルを用いて多角形を塗潰す。

【００１６】また台形辺の辺データ管理テーブル１０が
すでに作成されていれば前記多角形塗潰し部５は直ちに
Ｓ8 にて台形辺の辺データ管理テーブルを用いて多角形
を塗潰す。

【００１７】図２におけるＳ3 の辺データ管理テーブル
の作成処理は図３に基づいて行われるようになってい
る。すなわちＳ11にて直線描画の辺データを管理するこ
とを示すステータス「１」を辺データ管理テーブル１０
のｎ1 にセットする。これにより辺データ管理テーブル
１０が直線の辺データを管理していることが示される。

【００１８】次にＳ12にて与えられた座標列から始点、
終点となる二組の座標を取出し描画に必要な情報を求め
る。続いてＳ13にて辺データに始点のＸ座標、終点の
Ｘ、Ｙ座標、描画に必要な情報をセットし、バケット１
２にその辺データのアドレスをセットする。

【００１９】続いてＳ14にて座標組が一本目の直線のも
のか否かをチェックし、一本目の直線のものであればＳ
15にて辺データのアドレスを辺データ管理テーブル１０
のｎ7 にセットする。また一本目の直線のものでなけれ
ばＳ16にて辺データのアドレスを前の辺データの直線の
順序リンクポインタエリアｎ18にセットし辺データリス
ト１１を作成する。

【００２０】続いてＳ17にて座標組が最後の直線のもの
であるか否かをチェックし、最後の直線のものでなけれ
ば処理をＳ12に戻し同様の処理を繰り返す。また最後の
直線のものであればＳ18にて辺データの直線の順序リン
クポインタエリアｎ18に一本目の直線の辺データポイン
タをセットする。

【００２１】そして最後にＳ19にてバケット１２の下か
ら順にリンクしている辺データリストのポインタとＹ座
標、辺データへのポインタの組数を辺データ管理テーブ
ル１０のｎ8 〜ｎ11、ｎ3 〜ｎ6 及びｎ2 にそれぞれセ
ットする。

【００２２】以上により直線描画処理時の辺データ管理
テーブル作成処理を終了する。

【００２３】図２におけるＳ7 の台形辺の辺データ管理
テーブルの作成処理は図４に基づいて行われるようにな
っている。すなわちＳ21にて多角形である台形の辺デー
タを管理することを示すステータス「２」を辺データ管
理テーブル１０のｎ1 にセットする。これにより辺デー
タ管理テーブル１０が台形の辺データを管理しているこ
とが示される。

【００２４】次にＳ22にて辺データ管理テーブル１０を
下からスキャンし辺データリストから辺データを順次取
り出す。

【００２５】そしてＳ23にて取り出した辺が一本目であ
るか或いは辺データの順序ポインタがnullであるか否か
をチェックする。取り出した辺が一本目であったり、辺
データの順序ポインタがnullであればＳ24にて取り出し
た辺データをアクティブ辺テーブル１３に登録する。そ
してＳ25にて辺データがリンクしているか否かをチェッ
クする。

【００２６】また取り出した辺が一本目でなかったり、
辺データの順序ポインタがnullでなければ続いてＳ26に
て前記交差処理部３は取り出した辺とアクティブ辺テー
ブル１３内の辺との交差を判定する。

【００２７】交差していればＳ27にて辺データ分割部６
は交点で二分割して新たな辺を生成し辺データリストに
追加して交点のＹ座標での辺データリストを辺データ管
理テーブル１０に追加する。そしてＳ28にて取出した辺
データをアクティブ辺テーブル１３に登録する。また交
差していなければ単にＳ28にて取出した辺データをアク
ティブ辺テーブル１３に登録する。そしてＳ25にて辺デ
ータがリンクしているか否かをチェックする。

【００２８】Ｓ25のチェックにおいて辺データがリンク
していればリンクしている辺データを取出し、処理をＳ
23の処理に戻す。またリンクしていなければＳ30にてア
クティブ辺テーブル１３をソートし、辺データ管理テー
ブル１０からの辺データのリンク順序をアクティブ辺テ
ーブル１３のソート順になるようにする。

【００２９】続いてＳ31にて台形の左辺或いは右辺が辺
データ管理テーブル１０の次のＹ座標で終了するか否か
をチェックし、終了しなければＳ32にてＹ座標で辺を二
分割して新たな辺とその辺データを作成し、元の辺デー
タの情報を全て複写する。Ｙ座標とＹ座標におけるＸ座
標を始点座標にセットし、順序リンクポインタにnullを
セットする。そしてＳ33にて次のＹ座標で終了する辺を
アクティブ辺テーブル１３から取出し、処理をＳ22に戻
す。

【００３０】また台形の左辺或いは右辺が辺データ管理
テーブル１０の次のＹ座標で終了すればＳ33にて次のＹ
座標で終了する辺をアクティブ辺テーブル１３から取出
し、処理をＳ22に戻す。

【００３１】次にこのような構成の実施例の作用につい
て述べる。

【００３２】例えば図６に示すような座標列（ｘs1，ｙ
s1）（ｘs2，ｙs2）（ｘs3，ｙs3）（ｘs4，ｙs4）が座
標入力部１から与えられると、その座標列から始点、終
点となる二組の座標（ｘs1，ｙs1）（ｘs2，ｙs2）を取
出し描画に必要な情報を求める。そして辺データ１１に
直線の座標、描画に必要な情報をセットし、バケット１
２に辺データ１１のアドレスをセットして辺データＬ10
を得る。この辺データＬ10は与えられた座標列の一本目
の直線なので辺データＬ10のアドレスを辺データ管理テ
ーブル１０の一本目の直線の辺データポインタｎ7 にセ
ットする。また他の辺データＬ20，Ｌ30，Ｌ40のように
一本目の直線の辺データでない場合は、前の辺データの
アドレスを辺データ１１の順序リンクポインタｎ18にセ
ットして順序リンクを作成する。

【００３３】以上の処理を座標組が最後となる直線Ｌ40
まで繰り返し、最後の辺データＬ40の順序リンクポイン
タｎ18に辺データ管理テーブル１０から一本目の直線の
辺データＬ10へのポインタをセットする。こうして辺デ
ータＬ10〜Ｌ40からなる辺データリストが形成されるこ
とになる。

【００３４】そしてバケット１２の下から順にリンクし
ている辺データリストのポインタとそのＹ座標を辺デー
タ管理テーブル１０に複写する。またＹ座標と辺データ
へのポインタの組数「３」を辺データ管理テーブル１０
のエリアｎ2 にセットする。こうして図７に示すような
辺データ管理テーブル１０が作成される。

【００３５】このような辺データ管理テーブル１０が作
成されると、続いて直線の描画が行われる。この描画は
辺データ管理テーブル１０から一本目の直線の辺データ
Ｌ10へのポインタを取出し直線を描画する。続いて辺デ
ータＬ10から辺データＬ20への順序リンクポインタを取
出して直線を描画する。同様に辺データＬ20、Ｌ30から
辺データＬ30、Ｌ40への順序リンクポインタを取出して
それぞれ直線を描画する。

【００３６】続いて辺データ管理テーブル１０がこのよ
うな直線描画の辺データを管理している状態で、同じ座
標列が与えられて多角形の塗潰し処理が行われる場合
は、辺データ管理テーブル１０には多角形を分割した台
形の辺データが作成されていないので、先ず辺データ管
理テーブル１０に台形の辺データを管理することを示す
ステータス「２」をセットする。そして辺データ管理テ
ーブル１０を下からスキャンして辺データリストから辺
データＬ10を取出す。そしてこの辺データＬ10は一本目
なので図８に示すようにアクティブ辺テーブル１３に登
録する。

【００３７】次に辺データＬ10と同じＹ座標にリンクす
る辺データへのポインタ、すなわち辺データ１１のエリ
アｎ19のポインタから辺データＬ40を取出す。この辺デ
ータＬ40は一本目ではなく、また順序リンクポインタが
nullでないので、アクティブ辺テーブル１３内の辺との
交差を判定する。交点が存在しないので辺データＬ20を
アクティブ辺テーブル１３に格納し、また辺データＬ20
は同じＹ座標でリンクしていないので、アクティブ辺テ
ーブル１３を昇べきの順にソートしておき、辺データＬ
10は辺データ管理テーブル１０から、辺データＬ40は辺
データＬ10からリンクされるようにする。

【００３８】辺データＬ10は次のＹ座標ｙs2で終了する
ので、アクティブ辺テーブル１３から取出し、辺データ
Ｌ40は次のＹ座標ｙs2で終了しないので、辺データＬ40
をｙs2で二分割し、図８に示すような新たな辺データＬ
41を作成して辺データリストに加え、辺の始点（ｘs5，
ｙs5）を設定し、順序リンクポインタにはnullをセット
する。

【００３９】次にアクティブ辺テーブル１３内の辺デー
タＬ41と辺データＬ20で交点が存在するので、図９に示
すように交点（ｘs5，ｙs5）で辺データＬ20、辺データ
Ｌ41をそれぞれ二分割し、新しい辺としてＬ42を生成
し、辺データリストに追加する。またＹ座標と辺データ
テーブルへの組数を「４」にする。

【００４０】これらの処理を全ての辺に適用して行うこ
とにより辺データ管理テーブル１０及び辺データリスト
は図１０に示すようになる。

【００４１】こうして多角形を台形に分割した辺に関す
る辺データが作成されるので、辺データ管理テーブル１
０をしたから順にリンクされている辺を取出し、取出さ
れた順序でそれぞれ台形の左辺、右辺の組として塗潰
す。

【００４２】さらに同じ座標が与えられた場合にはすで
に辺データが作成されているので、直線描画の場合は辺
データ管理テーブル１０から一本目の辺データＬ10への
ポインタを取出し、順序リンクポインタを辿って辺デー
タにアクセスでき、また多角形の塗潰しの場合は辺デー
タ管理テーブル１０の下から順にリンクされている辺を
台形の左辺、右辺として塗潰す。

【００４３】このように辺データ管理テーブル１０に一
旦処理された直線の描画或いは多角形の塗潰しの処理の
ときの情報を管理し、同じ座標列が与えられ、再び直線
の描画或いは多角形の塗潰しの処理を行うときにはその
辺データ管理テーブル１０で管理されている情報を最大
限に利用して計算の重複を避けるようにしているので、
処理の高速化を図ることができる。

【００４４】

【発明の効果】以上、本発明によれば、直線の描画処理
或いは多角形の塗潰しに利用した情報を保存し、その保
存した情報の座標列と同一の座標列が与えられたとき保
存情報を利用して直線の描画処理或いは多角形の塗潰し
を行うことができるので、処理の高速化を図ることがで
きる。

【図面の簡単な説明】

【図１】本発明の実施例を示すブロック図。

【図２】同実施例の基本処理を示す流れ図。

【図３】図２における直線描画の辺データ作成及び辺デ
ータ管理テーブルへの登録処理を示す流れ図。

【図４】図２における台形の辺データ作成及び辺データ
管理テーブルへの登録処理を示す流れ図。

【図５】辺データ管理テーブル及び辺データの構成を示
す図。

【図６】同実施例における直線描画処理のときの辺デー
タ管理テーブル及び辺データリストの作成を説明するた
めの図。

【図７】同実施例における直線描画処理のときの辺デー
タ管理テーブル及び辺データリストの作成を説明するた
めの図。

【図８】同実施例における多角形を分割した台形の塗潰
し処理のときの辺データ管理テーブル及び辺データリス
トの作成を説明するための図。

【図９】同実施例における多角形を分割した台形の塗潰
し処理のときの辺データ管理テーブル及び辺データリス
トの作成を説明するための図。

【図１０】同実施例における多角形を分割した台形の塗
潰し処理のときの辺データ管理テーブル及び辺データリ
ストの作成を説明するための図。

【符号の説明】

１…座標入力部、 ２…辺データ管理テーブル作成部、 ４…直線描画部、 ５…多角形塗潰し部、 １０…辺データ管理テーブル。

Claims (1)

【特許請求の範囲】
1. 【請求項１】 座標列が与えられて行われる直線の描画
   処理の際に作成した直線の情報又は直線が構成する多角
   形を塗潰す処理の際に作成した直線の情報を持つ辺デー
   タを、順序リンクポインタで直線が発生する順番にリン
   クさせる手段と、与えられた座標列が発生する直線の一
   本目の辺データへのポインタ、Ｙ座標値、このＹ座標値
   にリンクする辺データへのポインタ及びその組数、管理
   する辺が直線の描画の辺データか多角形を塗潰す処理で
   多角形を台形分割して得られた辺データかを示すステー
   タスを管理する辺データ管理テーブルと、この辺データ
   管理テーブルが管理する情報を処理に応じて段階的に作
   成し変更する管理情報変更手段を設け、前記辺データ管
   理テーブルの管理情報を利用して直線描画及び多角形塗
   潰しの処理を行うことを特徴とする直線描画及び多角形
   塗潰し装置。