JPH01166180A - 図形の塗潰し処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［目次］ 概要　　。

産業上の利用分野 従来の技術 発明が解決しようとする問題点 問題点を解決するための手段 作用 実施例 発明の効果 ［概要］ 本発明は、 図形の塗潰し処理を行なう装置に関するものであり、 複雑な図形の塗潰し処理に要する時間の短縮を目的とし
、 このため、 図形を構成する各閉経路のスキャンラインに対するルー
プ交差方向が示されるデータを記憶する手段と、各閉経
路間の塗潰し規則が予め登録された手段と、Ｘ軸と平行
な姿勢でｙ軸方向へ歩進移動するスキャンラインと各閉
経路とが交差する点のＸ座標間を対応のループ交差方向
に応じ該当の登録規則に従って塗潰し画素を配列する手
段と、が設けられたことを特徴とし、 また、各閉経路の属性を所定の順序で結合記憶する手段
と、スキャンラインの現在歩進位置及び記憶属性に基づ
いて次の歩進位置におけるスキャンラインと各閉路との
交差点Ｘ座標を求める手段と、各交差点Ｘ座標により記
憶属性の結合順序に対し適否の判定を行なう手段と、否
定的な判定時に交差点Ｘ座標により記憶属性をソートし
て再結合する手段と、前記ループ交差方向の記憶手段と
、前記塗潰し規則の登録手段と、現在の歩進移動位置に
あけるスキャンライン上の交差点Ｘ座標間を対応のルー
プ方向に応じ該当の登録規則に従い記憶属性の結合順方
向へ塗潰し画素を配列する手段と、が設けられたことを
特徴とする。

「産業上の利用分野」 本発明は、図形の塗潰し処理を行なう装置に関するもの
である。

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

そしてしばしばそれらの図形を塗潰すことが必要となる
。

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

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

また塗潰し処理１は第１３図で説明される辺テーブルと
第１４図で説明されるアクティブ辺テーブルとが使用さ
れ、第１３図及び第１４図においてデータｙｍａｘ、　
ｘ　ｍｉｎ、　１／ｍ　、λ、Ｘ′により図形構成辺の
最大ｙ座標、＠小Ｘ座標、スキャンラインの歩進量＝１
に対するＸ座標の増加量、前記各辺データで示される辺
属性のパケット結合のデータ無し、各歩進移動位置のレ
ベルでスキャンラインと交わる辺のＸ座標が各々示され
ている。

これらを用いて図形の塗潰しが第１５図のようにピクセ
ルの各レベルにおける直線配列で行なわれ、その塗潰し
のために第１６図の処理が行なわれる。

第１６図の処理は辺テーブルとアクティブ辺テーブルの
双方が空となっていない歩進レベル（ｙ＝３）のスキャ
ンラインで開始され、その後、それら辺テーブルとアク
ティブ辺テーブルの双方が空となったときに終了される
。

スキャンラインが歩進レベルｙ＝３に達すると（ステッ
プ１６１でＹＥＳ）　、該レベル（ｙ＝３）の辺テーブ
ル内容（第１３図参照）がアクティブ辺テーブルへその
まま転送される（ステップ１６２）。

そして値Ｘ”＝Ｘ１　（、Ｘｉ）にピクセルが配置され
、第１５図のように最も下側の辺交差点が色塗りされる
（ステップ１６３）。

ざらにスキャンラインと交差しない辺の属性データを削
除する処理が行なわれるとくこのレベルでは削除されな
い、ステップ１６４）、次の歩進レベルｙ＝４でスキャ
ンラインと交差する辺ｅｌ。

ｅ２の交差点Ｘ座標Ｘ′が求められる（ステップ１６５
）。

そしてこれらの値Ｘ′の昇順でアクティブ辺テーブルの
辺属性データがソートされると（ステップ１６６）、歩
進レベルがインクリメントされ（ステップ１６７）　、
以上の処理が辺テーブル及びアクティブ辺テーブルの空
となるまで繰り返される。

その結果、第１５図において、左側から右側へ向かうピ
クセル線で同図の長方形図形が下側から上側へ順次色塗
りされる。

［発明が解決しようとする問題点］ 第１７図（Ａ＞、（Ｂ）、（Ｃ）、（Ｄ＞に示されるよ
うに複雑な図形の塗潰しを行なう場合には、塗潰し処理
が繰り返され、従ってその処理速度が大幅に低下する。

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

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

第１図において、手段１はＸ軸と平行なスキャンライン
をｙ軸方向へ歩進移動させる。

また手段２は、各歩進移動位置でスキャンラインと図形
を構成する各閉経路とが交差する点のＸ座標を記憶する
。

ざらに手段３は前記各閉経路のスキャンラインに対する
ループ交差方向が示されるデータを記憶する。

そして手段４には各閉経路間の塗潰し規則が予め登録さ
れる。

また手段５は各歩進移動位置で現在のスキャンラインに
関する交差点のＸ座標間を対応のループ交差方向に応じ
該当の登録規則に従って塗潰し画素を配列する。

第２図において、手段１１はＸ軸と平行なスキャンライ
ンをｙ軸方向へ歩進移動させる。

また手段１２には図形を構成する各閉経路の属性を所定
の順序で結合して記憶し、手段１３はスキャンラインの
現在歩進位置と各閉経路の記憶属性とに基づいて次の歩
進位置でスキャンラインと各閉経路とが交差する点のＸ
座標を求める。

さらに手段１４は各交差点Ｘ座標の大小比較により記憶
属性の結合順序に対して適否の判定を行い、手段１５は
否定的な判定が行なわれたときに限り、各交差点Ｘ座標
の昇降順に従い記憶属性をソートして再結合する。

そして手段１６は各閉経路のループ方向が示されるデー
タを記憶し、手段１７には各閉経路間の塗潰し規則が予
め登録され、手段１８は、現在の歩進移動位置における
スキャンライン上の交差点Ｘ座標間を対応記憶のループ
交差方向に応じ該当の登録規則に従って記憶属性の結合
順方向へ塗潰し画素を配列する。

［作用］ 第１及び第２の発明では、スキャンラインと各閉経路と
が交差する点の間に塗潰し画素を直線配列するか否かが
交差の閉経路に関するループ交差方向と登録規則により
決定される。

そしてそれらのうち第２の発明では、前述した従来の有
力な処理を行なう際に各スキャンラインレベルにおける
ソート（ステップ１６６〉が不要なときくすなわちＸ軸
方向で辺の位置が交差により入れ替わらないとき）にこ
れが省かれる。

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

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

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

第４図には前述の第１２図と同様な図形が示されており
、この長方形図形は各辺ｅ１．ｅ２．ｅ３、ｅ４で閉じ
た１本の経路で形成できる。

また第５図、第６図には第４図に対応した内容の辺テー
ブル、アクティブ辺テーブルが各々示されており、それ
らには制御情報Ｃが付加されている。

ここで、塗潰し対象の図形を表わす閉じた経路の種類は
第７図のようにサブ経路とクリップ経路の２種類とされ
、サブ経路で塗潰し対象の元図形が表わされ、クリップ
経路で塗潰し範囲が決定される。

そして各経路についてはスキャンラインに対する交差方
向性が与えられており、本実施例では第８図のようにｙ
座標増加方向で正、減少方向で負とされる。

ざらに非ゼロ屈曲番号規則と奇偶規則の塗潰し規則が定
められている。

それらのうちの非ゼロ屈曲番号規則では、各スキャンラ
イン上で初期値が先ずＯとされ、スキャンラインと経路
との交点でループ方向が正のときに値１が加算され、負
のときには値−１が加算され、Ｏでない範囲が色塗され
る。

その結果、第９図（Ａ）、（Ｂ）、（Ｃ）の複雑な図形
が容易に色塗りされる。

また奇偶規則では上記の加算結果が奇数のときに色塗り
が行なわれ、偶数のときには色塗りは行なわれない。

その結果、第９図（Ｄ）、（Ｅ）の図形が色扱きされる
。

以上の経路種別、ループ方向、塗潰し規則に関するデー
タは前述の制御情報Ｃとしてテーブルに登録される。

ただし、Ｘ軸に平行な直線辺についてはスキャンライン
と同等として辺登録が行なわれない。

第１０図には本実施例の作用を説明するフローチャート
が示されており、前述した第１６図におけるものと対応
したステップには同一符号が付されている。

本実施例では各経路について（ステップ１０１）、制御
情報Ｃがチエツクされ（ステップ１０２）、その情報に
より色塗りすべき範囲であること及び色塗り経路である
ことが確認された交点Ｘ座標の値Ｘ−間が色塗りされる
（ステップ１６３）。

例えば第９図（Ｃ）の場合には、方向により値がＯとな
っていない範囲が非ゼロ屈曲番号規則に従って直線色塗
りされる。

また同図（Ｅ）の場合には方向により値が奇数となって
いる範囲が奇偶規則に従い直線色塗りされる。

以上説明したように本実施例によれば、複数の閉経路か
らなる複雑な図形を一度に塗潰しでき、個々に塗潰す必
要がないので、その塗潰し処理を極めて高速に行なうこ
とが可能となる。

以上の処理ではスキャンラインがレベル３とレベル４の
ときに、アクティブ辺テーブルの辺属性データと制御情
報Ｃが同一であるにもかかわらず、大きな処理負荷とな
るソート処理（ステップ１６６）が不要に繰り返される
。

そこで、第１０図におけるステップ１６２〜１６６を第
１１図のステップ１１１〜１２９に置き換えてソート処
理（ステップ１２５）を必要なときにのみ行ない、処理
速度をざらに高めることが好適である。

この第１１図の処理を行なうために狭義ソートフラグと
有効性フラグとが予め用意され、スキャンラインの制御
情報を保持しながら次のスキャンラインに進むと、交点
Ｘ座標Ｘ′が小さいものから制御情報が前のラインのも
のと比較され、全ての制御情報が同一でないときに有効
性フラグが立てられろくステップ１２０）。

また現在のスキャンライン上で各交点Ｘ座標Ｘ−が大小
比較され、それらがＸ座標昇順となっておらず辺交差な
どにより交差値が入れ代わったときには、狭義ソートフ
ラグが立てられ、その狭義ソートフラグは経路が追加さ
れたり削除されていた場合にも立てられる（ステップ１
１９及び１１２、’１１４）。

この処理によれば、ソート処理（ステップ１２５）のみ
ならず、制御情報Ｃの判別処理（ステップ１２８も必要
に応じて省略でき、従ってより高速に色塗り処理を行な
える。

ただし、Ｘ座標方向で色塗り順が狂ってもよい場合で高
い速度が要求されないときには、常に制御情報Ｃを各レ
ベルで判別してもよい。

［発明の効果］ 以上説明したように本発明によれば、複数の閉経路で形
成される複雑な図形であっても、−度に色塗りが行なわ
れるので、その処理を極めて高速に行なうことが可能と
なる。

【図面の簡単な説明】

第１図は第１発明の原理説明図、 第２図は第２発明の原理説明図、 第３図は実施例の構成説明図、 第４図は実施例で塗潰し対象とされる図形の一例を示す
図、 第５図は実施例にあける辺テーブルの説明図、第６図は
実施例におけるアクティブ辺テーブルの説明図、 第７図は閉経路種別の説明図、 第８図は閉経路のループ方向性説明図、第９図は実施例
の塗潰し規則説明図、 第１０図は実施例の作用を説明するフローチャート、 第１１図は第１０図をより改善した処理の手順を示すフ
ローチャート、 第１２図は塗潰し対象の図形及びスキャンラインの説明
図、 第１３図は従来例における辺テーブルの説明図、第１４
図は従来例におけるアクティブ辺テーブルの説明図、 第１５図は塗潰し作用の説明図、 第１６図は従来の塗潰し処理を説明するフローチャート
、 第１７図は塗潰しの対象となる多角形の例を示す図であ
る。 ３１・・・ＭＰｔＪ、 ３２・・・制御プログラム格納ＲＯＭ、３３・・・フォ
ントメモリ、 ３４・・・ホストインターフェイス、 ３５・・・操作パネルインターフェイス、３６・・・ペ
ージメモリ、 ３７・・・ワークメモリ、 ３８・・・プリンタインターフェイス。 第１発明の原理説明図 第、１図 第２発明の原理説明図 第２図 塔へ 八） コへ 鰻ｉ 実施例で塗潰し対象となる図形の説明図　　　　　・閉
経路種別の説明図 第７図 閉経路のループ方向性説明図 第８図 塗潰し対象の図形及びスキャンラインの説明図第゛１２
図 従来における辺テーブル（Ｅ　Ｔ）の説明間第　　１３
　図 く　　　　国 塗潰し作用の説明図 第　　１５　図 従来の塗潰し処理を説明するフローチャート第　　１６
　　図 第　　１７　　図

Claims (2)

【特許請求の範囲】
1. （１）、 ｘ軸と平行なスキャンラインをｙ軸方向へ歩進移動させ
   る手段（１）と、 各歩進移動位置でスキャンラインと図形を構成する各閉
   経路とが交差する点のｘ座標を記憶する手段（２）と、 前記各閉経路のスキャンラインに対するループ交差方向
   が示されるデータを記憶する手段（３）と、 各閉経路間の塗潰し規則が予め登録された手段（４）と
   、 各歩進移動位置で現在のスキャンラインに関する交差点
   のｘ座標間を対応のループ交差方向に応じ該当の登録規
   則に従つて塗潰し画素を配列する手段（５）と、 を有する、ことを特徴とする図形の塗潰し装置。
2. （２）、 ｘ軸と平行なスキャンラインをｙ軸方向へ歩進移動させ
   る手段（１１）と、 図形を構成する各閉経路の属性を所定の順序で結合して
   記憶する手段（１２）と、 スキャンラインの現在歩進位置と各閉経路の記憶属性と
   に基づいて次の歩進位置でスキャンラインと各閉経路と
   が交差する点のｘ座標を求める手段（１３）と、 各交差点ｘ座標の大小比較により記憶属性の結合順序に
   対して適否の判定を行なう手段（１４）と、 否定的な判定が行なわれたときに限り、各交差点ｘ座標
   の昇降順に従い記憶属性をソートして再結合する手段（
   １５）と、 各閉経路のスキャンラインに対するループ交差方向が示
   されるデータを記憶する手段（１６）と、各閉経路間の
   塗潰し規則が予め登録された手段（１７）と、 現在の歩進移動位置におけるスキャンライン上の交差点
   ｘ座標間を対応記憶のループ交差方向に応じ該当の登録
   規則に従つて記憶属性の結合順対応の方向へ塗潰し画素
   を配列する手段（１８）と、を有する、ことを特徴とす
   る図形の塗潰し処理装置。