JPH01166181A - 多角形の塗潰し処理装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［目次］ 概要 産業上の利用分野 従来の技術 発明が解決しようとする問題点 問題点を解決するための手段 作用 実施例 発明の効果 ［概要］ 本発明は、。

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

［産業上の利用分野］ 本発明は、ベクトル表現された多角形の塗潰し処理を行
なう装置に関するものである。

コンピュータ処理による文書中に図形を挿入することに
より、その文書内容の理解を高めることが可能となる。

そしてそれらの図形では多角形が多用されており、しば
しばそれらの多角形を塗潰すことが必要となる。

［従来の技術］ 第６図には塗潰し処理の対象となる多角形が示されてお
り、その多角形は辺ｅｌ、ｅ２．ｅ３．ｅ４により構成
される。

そしてこの多角形はｘｙ座標の第１象限に配置されてお
り、スキャンラインｃ１がｙ座標値の増加方向へ歩進移
動される。

この歩進移動により多角形の読み取りが行なわれ、その
結果、第７図の辺テーブルが作成される。

辺テーブルには多角形構成辺ｅ２．ｅ３．ｅ４を各々示
しｙ軸成分が同方向となるベクトルがベクトル基端のｙ
座標（ここではスキャンラインｃ１の歩進レベル）と対
応してベクトル基端のＸ座標昇順で登録される。

この第７図では辺の最大ｙ座標ｙｍａｘ　、ベクトル基
端のＸ座標ｘｍｉｎ、スキャンラインｃ１の歩進量＝１
に対するＸ座標の増加量１７ｍ、パケット連結情報Ｊか
らなる辺データが登録され、値λによりデータのないこ
とが示される。

第８図には従来における塗潰し処理が示されており、第
９図にはその処理で使用されるアクティブ辺テーブルが
説明されている。

そして、第１０図では多角形の色塗作用が説明されてお
り、第１１図ではアクティブ辺テーブルの内容変化作用
が説明されている。

第９図から理解されるように、アクティブ辺テーブルは
第７図の辺テーブルと略同様な構成とされており、値ｘ
ｍｉｎのみが値Ｘ′に変更されている。

この値Ｘ−によりスキャンラインｃ１と辺ｅ２゜ｅ３．
ｅ４との交点におけるＸ座標が示され、値Ｘ−は値１７
ｍにスキャンラインＣ１の歩進量＝１を乗じたものを値
ｘｍｉｎに加算することで求められる。

第８図の処理では辺テーブルとアクティブ辺テーブルの
双方が空の状態となっていないスキャンラインの歩進レ
ベルが最初にサーチされ、その後それらの双方が空とな
った歩進レベルにスキャンラインが達すると処理が終了
される。

ここでは上記のサーチがスキャンライン歩進方向で行な
われ、スキャンラインの歩進レベルｙ＝３が先ずサーチ
される（ステップ８１でＮｏ＞。

このサーチが行なわれると辺テーブルに登録された辺ｅ
２．ｅ３のデータ（辺ｅ１のベクトルは他のベクトルの
ようにｙ軸成分を有しておらず、このためそのデータは
第７図のように登録されない）は第７図及び第９図から
理解されるようにアクティブ辺テーブルへそのまま転送
される（ステップ８２）。

その作用が第１１図（Ａ＞に示されており、この処理（
ステップ８２）が行なわれると、アクティブ辺テーブル
にあける辺ｅ２のＸ座標Ｘ′から辺ｅ３のＸ座標Ｘ′へ
向かってＸ座標昇順（すなわち情報Ｊで示される連結順
）で塗潰し画素のピクセルが配列され、これによりそれ
ら間が直線状に色塗りされる（ステップ８３）。

次いで辺ｅ２については値ｙｍａｘ　−１＝９−１＝８
が、辺ｅ３については値ｙｍａｘ−’Ｉ＝’１１−１＝
１０が、各々求められてスキャンラインの現在歩進レベ
ルｙ＝３とそれらが比較され、値ｙｍａｘ−１と現在の
歩進レベルとが一致する辺データを削除する処理が行な
われる（ステップ８４）。

ここではそれらの位置は確認されず、第９図のようにア
クティブ辺テーブルの内容はそのままとされる。

ざらに次の歩進レベルＶ＝４となったときにスキャンラ
インＣ１と辺ｅ２．ｅ３が交わる点のＸ座標Ｘ−が求め
られてその更新が第１１図（Ｂ）のように行なわれる（
ステップ８５）。

そして値Ｘ′の更新で実際の多角形図形と辺ｅ２、ｅ３
の昇順が逆となるおそれが生ずるので、値Ｘ′の昇順で
アクティブ辺テーブルのソートが行なわれる（ステップ
８６）。

このスキャンライン歩進レベルｙ＝３ではｅ２゜ｅ３の
値Ｘ′がそれぞれ値２と値５．５となっているので、第
９図から理解されるようにソート処理にもかかわらず昇
順がそのままとされる。

最後にスキャンライン歩進レベルがインクリメントされ
ると（ステップ８７）、アクティブ辺テーブルの方が空
となっていないので（ステップ８１でＮｏ）、同様な９
８理（ステラ’７８２，８３゜８４．８５，８６．８７
＞が繰り返される。

そしてスキャンラインの歩進レベルがＶ＝６に達すると
、次の歩進レベルＶ＝７で辺ｅ２．ｅ３が入れ替わるの
で、ソート処理（ステップ８６）により第９図のように
それらのデータが入れ替えられる。

さらにスキャンラインの歩進レベルがｙ−８に達すると
、次の歩進レベルｙ＝９では辺ｅ３．ｅ４のみとなって
辺ｅ２が不要となるので、そのデータが第９図のように
アクティブ辺テーブルから削除される（ステップ８４）
。

またスキャンラインの歩進レベルがＶ＝１０に達すると
、次の歩進レベルｙ＝１１で図形が終了するので、辺ｅ
３．ｅ４のデータがともに削除され（ステップ８４）、
歩進レベルがｙ＝１１となると、辺テーブル及びアクテ
ィブ辺テーブルが空となって第８図の処理が終了する。

以上の処理が行なわれることにより、第６図において左
側から右側へ向かうピクセル線で同図の多角形が下側か
ら上側へ順次色塗りされ、この色塗り結果は第１０図か
ら理解される。

なお、レベル８での辺ｅ２に関する辺データ削除は第１
１図（Ｃ）で、値Ｘ−の置換は第１１図（Ｄ＞で、また
レベル９での辺ｅ４に関するデータの追加は第１１図（
Ｅ）で、そしてレベル１０でのアクティブ辺テーブルの
内容は第１１図（Ｆ）で、各々説明されている。

［発明が解決しようとする問題点］ 例えば第９図におけるスキャンラインの歩進レベルｙ＝
３〜Ｖ＝５のように、実際にはアクティブ辺テーブルの
ソートが不要であるにもかかわらず、第８図のようにそ
のソートはスキャンラインの各歩進レベルで行なわれる
。

このソート処理に要する負荷は処理装置にとって大きな
ものとなり、このため、従来においては多角形の塗潰し
に長い時間を必要とするという問題があった。

本発明は上記従来の課題に鑑みてなされたものであり、
その目的は、多角形の塗潰し速度を大幅に高めることが
可能となる多角形の塗潰し処理装置を提供することにあ
る。

［問題点を解決するための手段］ 上記目的を連成するために、本発明に係る装置は第１図
のように構成されている。

同図の手段１１には多角形構成辺を各々示しｙ軸成分が
同方向となる複数のベクトルがベクトル基端のＸ座標と
対応して該基端のＸ座標昇降順で連結登録される。

そして手段１２はｙ軸と平行な姿勢で前記方向へｙ軸に
沿って歩進移動するスキャンラインのベクトル基端の到
達を登録内容のベクトル基端Ｘ座標の利用により検知す
る。

さらに手段１３は前記検知が行なわれる毎に検知基端の
ベクトルに関する登録内容を読み出して登録内容連結順
で蓄積する。

また手段１４は次の歩進位置でスキャンラインと交差し
ない多角形構成辺を蓄積内容から特定して該特定辺の蓄
積内容を削除する。

そして手段１５はスキャンラインの現在歩進位置と各ベ
クトルの蓄積内容とに基づいて次歩進位置のスキャンラ
インと多角形構成辺とが交差する点のＸ座標を推定する
とともに、蓄積内容のベクトル基端Ｘ座標を推定のＸ座
標に更新する。

さらに手段１６は登録内容連結順で各登録内容が蓄積さ
れているか否かを更新された各Ｘ座標の大小比較により
判断し、蓄積されていない旨の判断が行なわれると、こ
のときにのみ手段１７は更新された各Ｘ座標により蓄積
内容を該登録内容連結順でソートする。

また手段１８はスキャンラインの前回歩進位置で更新さ
れたＸ座標間に登録内容連結順と対応した方向へ塗潰し
画素を配列する。

［作用］ 本発明では、次のスキャンライン歩進位置でそのスキャ
ンラインと交差する辺の交点Ｘ座標を大小比較して昇順
が狂う場合にのみ、蓄積内容（前述の例ではアクティブ
辺テーブル）のソートが行なわれる。

［実施例］ 以下、図面に基づいて本発明に係る装置の好適な実施例
を説明する。

第２図にはページプリンタ用の制御装置が示されており
、その装置はＭＰＵ２１．制御プログラム格納ＲＯＭ２
２．フォントメモリ２３．ホストインターフェイス２４
．操作パネルインターフェイス２５，１ペ一ジ分のペー
ジメモリ２６．ワークメモリ２７．プリンタインターフ
ェイス２８により構成されている。

そしてページメモリ２６上の多角形がＭＰＵ　２１によ
り制御プログラム格納ＲＯＭ２２の内容に従いワークメ
モリ２７を用いて塗潰しされており、その結果、塗潰し
多角形が挿入された文書のバーｔ′コピーが得られる。

第３図には本実施例の作用がフローチャートで説明され
ており、同図においては第８図と対応したステップには
同一符号が付されている。

さらに第４図では本実施例におけるアクティブ辺テーブ
ルが説明されており、この例では第６図の多角形が塗潰
される。

またアクティブ辺テーブルにはフラグデータ部が追加さ
れており、そのデータ部にはＸ座標値Ｘ′を更新した辺
の本数２辺の総数、Ｘ座標値ｘ′。

ソートフラグが記憶される。

そして第５図にはアクティブ辺テーブルの内容辺か作用
が説明されており、以下第３図、第４図。

第５図を用いて本実施例の作用を説明する。

スキャンラインの歩進レベルがｙ＝３に達して辺テーブ
ルのデータのうち現在レベルのものがアクティブ辺テー
ブルへ転送されると、第５図（Ａ）のように現在レベル
のスキャンラインと交差する辺の本数＝２がアクティブ
辺テーブルに書き込まれる。

その後に辺ｅ２についてのＸ座標Ｘ′が更新されると、
第５図（’Ｂ　）のように更新済みの辺本数＝１がアク
ティブ辺テーブルに書き込まれる（ステップ８５）。

同様の更新処理が辺ｅ３に対しても行なわれると、第５
図（Ｃ）のように現在本数＝２２辺本数＝２．Ｘ座標ｘ
′＝５．５がアクティブ辺テーブルに書き込まれ、その
ときのＸ座標ｘ′＝５．５と前回のｘｉ標ｘ′＝２との
大小比較が行なわれる（ステップ３３）。

ここでは前回の値Ｘ−が今回の値Ｘ−より小さいので、
ソートフラグのセット（ステップ３４）は行なわれず、
更新の終了が確認される（ステップ３１でＹＥＳ）。

次いでソートフラグのセット、リセットが判定され（ス
テップ３５）、ソートフラグがセットされていないので
（ステップ３５でＮｏ＞　、フラグデータ部のみがクリ
アされてスキャンライン歩進レベルのインクリメントが
行なわれ（ステップ８７）、このことは第５図（Ｄ＞か
らも理解される。

その後、スキャンラインの歩進レベルがｙ＝６に達して
大小比較（ステップ３３）が行なわれると、第４図のよ
うにソートフラグがセットされ、その確認（ステップ３
５でＹＥＳ）によりソート処理（ステップ８６）が行な
われる。

なお、−旦ソートフラグがセットされると（ステップ３
２でＹＥＳ）　、値Ｘ′の更新のみが繰り返され、全て
の更新が完了したときにソート処理（ステップ８６）が
行なわれる。

以上説明したように本実施例によれば、ソート処理（ス
テップ８６）が昇順の狂う場合にのみ行なわれるので、
多角形の塗潰しを極めて高速に行なうことが可能となる
。

また本実施例によればソートフラグのセットにより値Ｘ
′の大小比較が省略されるので、さらに処理速度を高め
ることができる。

［発明の効果］ 以上説明したように本発明によれば、登録内容の蓄積順
が登録の連結順と対応したものとなっているときには蓄
積内容の昇降順ソートが省略されるので、塗潰しの処理
速度を大幅に高めることが可能となる。

【図面の簡単な説明】

第１図は発明の原理説明図、 第２図は実施例の構成説明図、 第３図は実施例の作用を説明するフローチャート、 第４図は実施例におけるアクティブ辺テーブルの説明図
、 第５図は実施例におけるアクティブ辺テーブルの変化作
用説明図、 第６図はスキャンラインの移動説明図、第７図は辺テー
ブル説明図、 第８図は従来例を説明するフローチャート、第９図は従
来におけるアクティブ辺テーブルの説明図、 第１０図は色塗り作用の説明図、 第１１図は従来におけるアクティブ辺テーブルの変化作
用説明図である。 ２１・・・ＭＰＵ。 ２２・・・制御プログラム格納メモリ、２３・・・フォ
ントメモリ、 ２４・・・ホストインターフェイス、 ２５・・・操作パネルインターフェイス、２６・◆・ペ
ージメモ１ハ ２７・・・ワークメモリ、 ２８・・・プリンタインターフェイス。 嘘　　　　　　わ　　　　　　■ 全へ 八） 実施例の作用を説明するフローチャート第３図 （Ｄ）　　ｅ２９２１　　ｅ３１１５．５−０．５　λ
７第５図 従来例を説明するフローチャーＦ 第８図 色塗り作用の説明図 第　　ｌＯ図

Claims (1)

1. 【特許請求の範囲】 多角形構成辺を各々示しｙ軸成分が同方向となる複数の
   ベクトルがベクトル基端のｙ座標と対応して該基端のｘ
   座標昇降順で連結登録される手段（１０）と、 ｘ軸と平行な姿勢で前記方向へｙ軸に沿って歩進移動す
   るスキャンラインのベクトル基端到達を登録内容のベク
   トル基端ｙ座標の利用により検知する手段（１２）と、 前記検知が行なわれる毎に、検知基端のベクトルに関す
   る登録内容を読み出して登録内容の連結順で蓄積する手
   段（１３）と、 次の歩進位置でスキャンラインと交差しない多角形構成
   辺を蓄積内容から特定して該特定辺の蓄積内容を削除す
   る手段（１４）と、 スキャンラインの現在歩進位置と各ベクトルの蓄積内容
   とに基づいて次歩進位置のスキャンラインと多角形構成
   辺とが交差する点のｘ座標を推定するとともに蓄積内容
   のベクトル基端ｘ座標を推定のｘ座標に更新する手段（
   １５）と、 登録内容連結順で各登録内容が蓄積されているか否かを
   更新された各ｘ座標の大小比較により判断する手段（１
   ６）と、 登録内容連結順で各登録内容が蓄積されていない旨の判
   断が行なわれたときにのみ更新された各ｘ座標により蓄
   積内容を該登録内容連結順でソートする手段（１７）と
   、 スキャンラインの前回歩進位置で更新されたｘ座標間に
   登録内容連結順と対応した方向へ塗潰し画素を配列する
   手段（１８）と、 を有する、ことを特徴とする多角形の塗潰し処理装置。