JPH10326352A - 多角形塗り潰し方法及び記録媒体 - Google Patents

多角形塗り潰し方法及び記録媒体

Info

Publication number
JPH10326352A
JPH10326352A JP9136693A JP13669397A JPH10326352A JP H10326352 A JPH10326352 A JP H10326352A JP 9136693 A JP9136693 A JP 9136693A JP 13669397 A JP13669397 A JP 13669397A JP H10326352 A JPH10326352 A JP H10326352A
Authority
JP
Japan
Prior art keywords
polygon
line segment
outline
bits
memory
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP9136693A
Other languages
English (en)
Inventor
Hiroki Takita
浩樹 瀧田
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Mitsubishi Electric Corp
Original Assignee
Mitsubishi Electric Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Mitsubishi Electric Corp filed Critical Mitsubishi Electric Corp
Priority to JP9136693A priority Critical patent/JPH10326352A/ja
Priority to US08/946,195 priority patent/US6301259B1/en
Priority to US08/947,017 priority patent/US6215501B1/en
Priority to DE69721736T priority patent/DE69721736T2/de
Priority to EP97117786A priority patent/EP0881598B1/en
Publication of JPH10326352A publication Critical patent/JPH10326352A/ja
Pending legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/10—Packet switching elements characterised by the switching fabric construction
    • H04L49/104—Asynchronous transfer mode [ATM] switching fabrics
    • H04L49/105—ATM switching elements
    • H04L49/108—ATM switching elements using shared central buffer
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T11/00—Two-dimensional [2D] image generation
    • G06T11/40—Filling planar surfaces by adding surface attributes, e.g. adding colours or textures
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/35—Switches specially adapted for specific applications
    • H04L49/351—Switches specially adapted for specific applications for local area network [LAN], e.g. Ethernet switches
    • G—PHYSICS
    • G09—EDUCATION; CRYPTOGRAPHY; DISPLAY; ADVERTISING; SEALS
    • G09G—ARRANGEMENTS OR CIRCUITS FOR CONTROL OF INDICATING DEVICES USING STATIC MEANS TO PRESENT VARIABLE INFORMATION
    • G09G5/00—Control arrangements or circuits for visual indicators common to cathode-ray tube indicators and other visual indicators
    • G09G5/36—Control arrangements or circuits for visual indicators common to cathode-ray tube indicators and other visual indicators characterised by the display of a graphic pattern, e.g. using an all-points-addressable [APA] memory
    • G09G5/39—Control of the bit-mapped memory
    • G09G5/393—Arrangements for updating the contents of the bit-mapped memory

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Image Generation (AREA)

Abstract

(57)【要約】 【課題】 プロセッサ負荷の低減を図りながら正確に塗
り潰し処理が行える多角形塗り潰し方法を得る。 【解決手段】 自己交差をしない多角形に対し、左回り
で多角形の外形を構成する線分を選択しながら、選択し
た線分自身を含んで水平座標上の右方向に該当するワー
クメモリの平面作業領域上の全てのビットを反転させて
多角形の塗り潰し描画を行い（ステップＳ２２）、続い
て、多角形の外形を構成する線分のうちその線分のベク
トルが上向き（垂直方向座標変化が上方向）の線分のみ
をワークメモリ２Ａ上にさらに描画した（ステップＳ２
３）後、ワークメモリから表示メモリに伸長転送する
（ステップＳ２４）。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】この発明は、コンピュータ図
形処理において表示メモリの記憶内容に基づき表示され
る多角形の塗り潰し方法に関する。
【０００２】
【従来の技術】コンピュータ図形処理における多角形の
塗り潰しは、従来、スキャンライン法等により描画され
ていた。この方法は、スキャンラインという水平な直線
で多角形を上から下へスキャンしながら、以下の方式に
より描画を行っていく方法である。
【０００３】１．スキャンラインを多角形の最上段に取
る。 ２．スキャンラインが最下段に来る間以下を繰り返す。 ２．１ スキャンラインと交差する辺を求める。 ２．２ スキャンラインとこれらの辺との交点を求め
る。 ２．３ 求めた交点をｘ座標でソートする。 ２．４ 交点をｘ座標の小さい順に二つずつペアにし
て、その間を塗り潰す。 ２．５ 一段下のスキャンラインに移動する。 ３．終了 ただし、「２．２スキャンラインとこれらの辺との交点
を求める。」で、交点が多角形の頂点でかつ２辺のベク
トルの向きが上と下向きの時は、頂点に２交点あるもの
と見なして例外処理を行う。この例外処理に該当するの
が、図５９で示した図形では、（Ｓｌ，Ｈ４）、（Ｓ
２，Ｈｌｌ）、（Ｓ５，Ｈ８）、（Ｓ６，Ｈ７）、（Ｓ
８，Ｈ５）、（Ｓｌ０，Ｈｌｌ）の座標上の点である。
【０００４】例えば、図５９で示した図形を、図６０に
示すように左回りで各線分を選択した場合、線分ベクト
ルＡ１（Ｈ４−Ｈ８，Ｓ１−Ｓ５）は上向き（垂直方向
座標変化が上方向）、線分ベクトルＡ２（Ｈ１−Ｈ４，
Ｓ４−Ｓ１）は下向き（垂直方向座標変化が下向き）と
なるため、これらベクトルＡ１，Ａ２を両辺にもつ座標
（Ｈ４，Ｓ１）に２交点あるものとみなす。
【０００５】一方、他に描画用の１bit/pixelのワーク
メモリを用いたアウトラインフォント方式により多角形
の塗り潰しを行う方法がある。この方法は、描画領域を
囲む最小長方形のワークメモリ（１bit/pixel）を使用
して、多角形の各線分の右側を線分自身を含んでビット
反転させることにより、１bit/pixelの描画領域を作成
し、そのワークメモリの描画情報を表示メモリ上に伸長
転送して描画する方法である。
【０００６】アウトラインフォント方式は、塗り潰し対
象の多角形の外形を構成する線分を規定した外形情報に
基づき、多角形の外形を構成する各線分を所定回りに選
択しながら、各線分に対して、線分自体を含んで水平座
標上の右方向に該当するワークメモリ上の全てのビット
を反転させてワークメモリ上に描画する。この際、以下
のＡ）〜Ｇ）の条件に従う。
【０００７】Ａ）これからｂｉｔ反転を行う線分のベク
トルと次に反転描画を行う線分ベクトルが共に上向きベ
クトル（垂直方向座標変化が上方向のベクトル）の場
合、始点は含め、終点を含めない線分の右側のｂｉｔ反
転を行う。
【０００８】⊃Ｂ）これからｂｉｔ反転を行う線分のベ
クトルと次に反転描画を行う線分のベクトルが共に下向
きベクトル（垂直方向座標変化が下方向のベクトル）の
場合、始点は含め、終点を含めない線分の右側のｂｉｔ
反転を行う。
【０００９】Ｃ）これからｂｉｔ反転を行う線分のベク
トルが上向きで、次に反転描画を行う線分のベクトルが
下向きベクトルの場合、始点と終点を含めた線分の右側
のｂｉｔ反転を行う。
【００１０】Ｄ）これからｂｉｔ反転を行う線分のベク
トルが下向きで、次に反転描画を行う線分のベクトルが
上向きベクトルの場合、始点と終点を含めた線分の右側
のｂｉｔ反転を行う。
【００１１】Ｅ）これからｂｉｔ反転を行う線分のベク
トルが下向きで、次に反転描画を行う線分のベクトルが
水平ベクトル（垂直方向座標変化がないベクトル）の場
合、始点は含め、終点を含めない線分の右側のｂｉｔ反
転を行う。
【００１２】Ｆ）これからｂｉｔ反転を行う線分のベク
トルが上向きで、次に反転描画を行う線分のベクトルが
水平ベクトルの場合、始点は含め、終点を含めない線分
の右側のｂｉｔ反転を行う。
【００１３】Ｇ）これからｂｉｔ反転を行う線分のベク
トルが水平で、次に反転描画を行う線分のベクトルが下
向きベクトルの場合、始点は含め、終点を含めない線分
の右側のｂｉｔ反転を行う。
【００１４】Ｈ）これからｂｉｔ反転を行う線分のベク
トルが水平で、次に反転描画を行う線分のベクトルが上
向きベクトルの場合、始点は含め、終点を含めない線分
の右側のｂｉｔ反転を行う。
【００１５】以下、図６１に示すような外形を有する塗
り潰し対象の三角形を例に挙げてアウトラインフォント
方式の説明をする。まず、この三角形の外形情報として
３頂点の座標｛Ｐ１（Ｈ８，Ｓ２）、Ｐ２（Ｈ２，Ｓ１
５）、Ｐ３（Ｈ１６，Ｓ１１）｝を得る。
【００１６】ここで、図６２に示すように、塗り潰し対
象の三角形に対して頂点Ｐ１〜Ｐ３の順で左回りに、線
分ベクトルＬ１（Ｈ２−Ｈ８，Ｓ１５−Ｓ２）、Ｌ２
（Ｈ１６−Ｈ２，Ｓ１１−Ｓ１５）、Ｌ３（Ｈ８−Ｈ１
６，Ｓ２−Ｓ１１）の順に選択して行くものとする。ま
た、ワークメモリ上の平面作業領域は初期状態時に白紙
状態（全く描画されていない状態）であるとする。
【００１７】まず、図６３及び図６４に示すように、外
形情報より得られる頂点Ｐ１，Ｐ２の座標から、Bresen
ham等の既存の直線アルゴリズムを用いて線分Ｌ１を求
め、線分Ｌ１に対して水平座標上の右方向に該当するワ
ークメモリの平面作業領域（１bit/pixel）上の全ての
ビットを反転させて描画する。
【００１８】なお、図６３は線分Ｌ１の途中の反転処理
経過を示し、図６４は最終反転処理結果を示している。
このとき、線分Ｌ１は下向きで線分Ｌ２は上向きであり
条件Ｄ）に該当するため、始点と終点を含めた線分Ｌ１
の右側のｂｉｔ反転を行う。
【００１９】次に、図６５に示すように、外形情報より
得られる頂点Ｐ２，Ｐ３の座標から、Bresenham等の既
存の直線アルゴリズムを用いて線分Ｌ２を求め、線分Ｌ
２に対して、線分Ｌ２自身を含んで水平座標上の右方向
に該当するワークメモリの平面作業領域上の全てのビッ
トを反転させる。その結果、図６４で示したステップで
既に描画されたビットがもう一度反転されて一部白紙状
態に戻る。
【００２０】なお、図６５は線分Ｌ２の途中の反転処理
経過を示している。このとき、線分Ｌ２及びＬ３は共に
上向きであり条件Ａ）が該当するため、始点は含め、終
点を含めない線分Ｌ２の右側のｂｉｔ反転を行う。
【００２１】以降、同様にして、外形情報に基づき線分
Ｌ３を求め、線分Ｌ３に対して水平座標上の右方向に該
当するワークメモリの平面作業領域上の全てのビットを
反転させると、図６６に示すように、内部が塗り潰され
た三角形が完成する。なお、線分Ｌ３が上向きで線分Ｌ
１が下向きであり条件Ｃ）に該当するため、始点と終点
を含めた線分Ｌ３の右側のｂｉｔ反転を行う。
【００２２】その後、ワークメモリの平面作業領域上の
描画情報を表示メモリ上の平面表示領域に伸長転送し、
表示メモリの記憶内容に基づき内部が塗りつぶされた三
角形が表示される。なお、伸長とはカラー情報等の付加
情報を加味することを意味する。
【００２３】なお、上記したアウトラインフォント方式
は、「多角形の各線分の右側をビット反転させる」とし
ているが、これを、「多角形の各線分の左側をビット反
転させる」としても、同様な原理で可能である。
【００２４】本方法で大きな図形を描画するときは、多
角形をワークメモリの平面作業領域に適合するように分
割して、分割した多角形の一部をそれぞれのワークメモ
リの平面作業領域上に塗り潰し描画した後、順次表示メ
モリに転送することにより、平面作業領域が小さいワー
クメモリを用いても大きな多角形を塗り潰し描画するこ
とが出来る。
【００２５】
【発明が解決しようとする課題】従来のコンピュータに
よる図形処理は、以上のようにスキャンライン法あるい
はアウトラインフォント方式により行われていた。
【００２６】スキャンライン法では、ラスター毎（１ス
キャンライン毎）に求めた交点のソート処理を行う必要
があり、さらに各線分の情報（始点、終点、線分の傾き
を示す情報など）を保持するための比較的大容量なメモ
リが必要である。
【００２７】したがって、頂点数が増えれば、線分の情
報を保持するためのメモリが頂点数分必要であること、
ソート量が増えるため、プロセッサの負荷が増大する等
の問題点があった。
【００２８】一方、アウトラインフォント方式は、上記
した問題点は生じにくいが、上述した条件Ａ）〜Ｈ）に
従って１（bit/pixel）のワークメモリの平面作業領域
に多角形の描画を行うが、このままでは図形の右側が１
ビット（１ピクセル）欠けてしまう（左側を反転された
場合は左側が１ビット欠けてしまう）ため、正確に塗り
潰しできないという問題点があった。
【００２９】この発明は上記問題点を解決するためにな
されたもので、プロセッサ負荷の低減を図りながら正確
に塗り潰し処理が行える多角形塗り潰し方法を得ること
を目的とする。
【００３０】
【課題を解決するための手段】この発明に係る請求項１
記載の多角形塗り潰し方法は、複数ビットからなる矩形
状の格納領域を有し１画素の情報をｎ（ｎ≧１）ビット
で格納する作業メモリと、複数ビットからなる矩形状の
格納領域を有し１画素の情報をｍ（ｍ＞ｎ）ビットで格
納する表示メモリとを有し、前記表示メモリの記憶内容
に基づき画像表示を行う画像処理システムを用いて多角
形の内部の塗り潰し処理を行う方法であって、前記作業
メモリの初期状態は何も描画されていない白紙状態であ
り、(a)塗り潰し対象の多角形の外形を構成する線分を
規定した外形情報を得るステップと、(b)前記外形情報
に基づき前記塗り潰し対象の多角形の外形を構成する各
線分を所定回りに選択しながら、各線分に対して水平座
標上の所定の水平方向に該当する前記作業メモリ上の全
てのビットを反転させることによりビット反転処理を行
い多角形の塗り潰し描画を行うステップと、(c)前記多
角形の塗り潰し描画がなされた前記作業メモリ上に、前
記外形情報に基づき前記塗り潰し対象の多角形の外形を
構成する線分をさらに描画するステップと、(d)前記ス
テップ(c)の後、前記作業メモリの格納情報を前記表示
メモリに転送するステップとを備えて構成される。
【００３１】請求項２記載の多角形塗り潰し方法の前記
ステップ(c)は、前記所定回りで選択された前記塗り潰
し対象の多角形の外形を構成する線分を全て描画するス
テップを含んでいる。
【００３２】請求項３記載の多角形塗り潰し方法におい
て、前記塗り潰し対象の多角形は、自己交差をしない多
角形を含み、前記ステップ(b)の前記ビット反転処理
は、線分自身に該当する前記作業メモリ上のビットをも
反転させる第１の反転モード及び線分自身を含まないで
ビット反転を行う第２の反転モードにうち一方のモード
を含み、前記ステップ(c)は、前記所定回りで選択され
た前記塗り潰し対象の多角形の外形を構成する線分のう
ち、そのベクトルの垂直方向変化が所定の垂直方向とな
る線分のみを描画するステップを含み、前記所定の垂直
方向は、前記ビット反転処理、前記所定回り及び前記所
定の水平方向の内容に基づき決定され、前記ステップ
(b)の前記ビット反転処理で描画されずに欠落した線分
が有する垂直方向変化である。
【００３３】この発明に係る請求項４記載の多角形塗り
潰し方法は、複数ビットからなる矩形状の格納領域を有
し１画素の情報をｎ（ｎ≧１）ビットで格納する作業メ
モリと、複数ビットからなる矩形状の格納領域を有し１
画素の情報をｍ（ｍ＞ｎ）ビットで格納する表示メモリ
とを有し、前記表示メモリの記憶内容に基づき画像表示
を行う画像処理システムを用いて多角形の内部の塗り潰
し処理を行う方法であって、前記作業メモリの初期状態
は何も描画されていない白紙状態であり、(a)自己交差
をしない塗り潰し対象の多角形の外形を構成する線分を
規定した外形情報を得るステップと、(b)前記外形情報
に基づき前記塗り潰し対象の多角形の外形を構成する線
分を所定回りに選択しながら、各線分に対して水平座標
上の所定の水平方向に該当する前記作業メモリ上の全て
のビットを反転させることによりビット反転処理を行い
前記作業メモリ上に多角形の塗り潰し描画を行うステッ
プとを備え、前記ビット反転処理は、線分自身に該当す
る前記作業メモリ上のビットをも反転させる第１の反転
モードあるいは線分自身を含まないでビット反転を行う
第２の反転モードを含み、(c)前記ステップ(b)の後、前
記作業メモリ上の情報を前記表示メモリに転送するステ
ップと、(d)前記ステップ(c)の後、前記表示メモリ上
に、前記外形情報に基づき、前記所定回りで選択された
前記塗り潰し対象の多角形の外形を構成する線分のう
ち、そのベクトルの垂直方向変化が所定の垂直方向とな
る線分のみを描画するステップとをさらに備え、前記所
定の垂直方向は、前記ビット反転処理、前記所定回り及
び前記所定の水平方向の内容に基づき決定され、前記ス
テップ(b)の前記ビット反転処理で描画されずに欠落し
た線分が有する垂直方向変化である。
【００３４】請求項５記載の多角形塗り潰し方法におい
て、前記ビット反転処理は前記第１の反転モードを含
み、前記所定回りは左回りを含み、前記所定の水平方向
は右方向を含み、前記所定の垂直方向は上方向を含んで
いる。
【００３５】請求項６記載の多角形塗り潰し方法におい
て、前記ビット反転処理は前記第１の反転モードを含
み、前記所定回りは右回りを含み、前記所定の水平方向
は右方向を含み、前記所定の垂直方向は下方向を含んで
いる。
【００３６】請求項７記載の多角形塗り潰し方法におい
て、前記ビット反転処理は前記第２の反転モードを含
み、前記所定回りは左回りを含み、前記所定の水平方向
は右方向を含み、前記所定の垂直方向は下方向を含んで
いる。
【００３７】請求項８記載の多角形塗り潰し方法におい
て、前記ビット反転処理は前記第２の反転モードを含
み、前記所定回りは右回りを含み、前記所定の水平方向
は右方向を含み、前記所定の垂直方向は上方向を含んで
いる。
【００３８】この発明に係る請求項９記載の多角形塗り
潰し方法は、複数ビットからなる矩形状の格納領域を有
し１画素の情報をｎ（ｎ≧１）ビットで格納する作業メ
モリと、複数ビットからなる矩形状の格納領域を有し１
画素の情報をｍ（ｍ＞ｎ）ビットで格納する表示メモリ
とを有し、前記表示メモリの記憶内容に基づき画像表示
を行う画像処理システムを用いて多角形の内部の塗り潰
し処理を行う方法であって、前記作業メモリの初期状態
は何も描画されていない白紙状態であり、(a)自己交差
しない塗り潰し対象の多角形の外形を構成する線分を規
定した外形情報を得るステップと、(b)前記外形情報に
基づき前記塗り潰し対象の多角形の外形を構成する線分
を所定回りに選択しながら、各線分に対して水平座標上
の所定の水平方向に該当する前記作業メモリ上の全ての
ビットを反転させることにより前記ビット反転処理を行
い前記作業メモリ上に多角形の塗り潰し描画を行うステ
ップと、(c)ステップ(b)の後、前記作業メモリ上の情報
を前記表示メモリに転送するステップとを備え、前記ス
テップ(b)の前記ビット反転処理は、線分自身に該当す
る前記作業メモリ上のビットをも反転させる第１の反転
モード及び線分自身を含まないでビット反転を行う第２
の反転モードを含み、前記所定回りで選択された前記塗
り潰し対象の多角形の外形を構成する線分のうち、その
ベクトルの垂直方向変化が第１の垂直方向となる線分は
前記第１の反転モードで前記ビット反転処理を行い、そ
のベクトルの垂直方向変化が第２の垂直方向となる線分
は前記第２の反転モードで前記ビット反転処理を行い、
前記第１及び第２の垂直方向は、前記所定の回り及び所
定の水平方向の内容に基づき、前記塗り潰し対象の多角
形の外形を構成する線分のうち、そのベクトルが前記１
の垂直方向の線分は前記第１の反転モードで前記ビット
反転処理を行うと欠落なく描画され、そのベクトルが前
記２の垂直方向の線分は前記第２の反転モードで前記ビ
ット反転処理を行うと欠落なく描画されるように決定さ
れる。
【００３９】請求項１０記載の多角形塗り潰し方法にお
いて、前記所定回りは左回りを含み、前記所定の水平方
向は右方向を含み、前記第１の垂直方向は下方向を含
み、前記第２の垂直方向は上方向を含んでいる。
【００４０】請求項１１記載の多角形塗り潰し方法にお
いて、前記所定回りは右回りを含み、前記所定の水平方
向は右方向を含み、前記第１の垂直方向は上方向を含
み、前記第２の垂直方向は下方向を含んでいる。
【００４１】この発明に係る請求項１２記載の記録媒体
は、複数ビットからなる矩形状の格納領域を有し１画素
の情報をｎ（ｎ≧１）ビットで格納する作業メモリと、
複数ビットからなる矩形状の格納領域を有し１画素の情
報をｍ（ｍ＞ｎ）ビットで格納する表示メモリとを有
し、前記表示メモリの記憶内容に基づき画像表示を行う
画像処理システムを用いて、コンピュータの制御下で多
角形の内部の塗り潰し処理を行う多角形塗り潰し方法を
記録した媒体であって、前記作業メモリの初期状態は何
も描画されていない白紙状態であり、(a)塗り潰し対象
の多角形の外形を構成する線分を規定した外形情報を得
るステップ、(b)前記外形情報に基づき前記塗り潰し対
象の多角形の外形を構成する各線分を所定回りに選択し
ながら、各線分に対して水平座標上の所定の水平方向に
該当する前記作業メモリ上の全てのビットを反転させる
ことによりビット反転処理を行い多角形の塗り潰し描画
を行うステップ、(c)前記多角形の塗り潰し描画がなさ
れた前記作業メモリ上に、前記外形情報に基づき前記塗
り潰し対象の多角形の外形を構成する線分をさらに描画
するステップ、及び(d)前記ステップ(c)の後、前記作業
メモリの格納情報を前記表示メモリに転送するステップ
を実行させるためのプログラムを記録している。
【００４２】この発明に係る請求項１３記載の記録媒体
は、複数ビットからなる矩形状の格納領域を有し１画素
の情報をｎ（ｎ≧１）ビットで格納する作業メモリと、
複数ビットからなる矩形状の格納領域を有し１画素の情
報をｍ（ｍ＞ｎ）ビットで格納する表示メモリとを有
し、前記表示メモリの記憶内容に基づき画像表示を行う
画像処理システムを用いて、コンピュータの制御下で多
角形の内部の塗り潰し処理を行う多角形塗り潰し方法を
記録した媒体であって、前記作業メモリの初期状態は何
も描画されていない白紙状態であり、(a)自己交差をし
ない塗り潰し対象の多角形の外形を構成する線分を規定
した外形情報を得るステップ、(b)前記外形情報に基づ
き前記塗り潰し対象の多角形の外形を構成する線分を所
定回りに選択しながら、各線分に対して水平座標上の所
定の水平方向に該当する前記作業メモリ上の全てのビッ
トを反転させることによりビット反転処理を行い前記作
業メモリ上に多角形の塗り潰し描画を行うステップ、こ
こで前記ビット反転処理は、線分自身に該当する前記作
業メモリ上のビットをも反転させる第１の反転モードあ
るいは線分自身を含まないでビット反転を行う第２の反
転モードを含み、(c)前記ステップ(b)の後、前記作業メ
モリ上の情報を前記表示メモリに転送するステップ、及
び(d)前記ステップ(c)の後、前記表示メモリ上に、前記
外形情報に基づき、前記所定回りで選択された前記塗り
潰し対象の多角形の外形を構成する線分のうち、そのベ
クトルの垂直方向変化が所定の垂直方向となる線分のみ
を描画するステップ、ここで前記所定の垂直方向は、前
記ビット反転処理、前記所定回り及び前記所定の水平方
向の内容に基づき決定され、前記ステップ(b)のビット
反転処理で欠落した線分が有する垂直方向変化であり、
前記ステップ(a)〜(d)を実行させるためのプログラムを
記録している。
【００４３】この発明に係る請求項１４記載の記録媒体
は、複数ビットからなる矩形状の格納領域を有し１画素
の情報をｎ（ｎ≧１）ビットで格納する作業メモリと、
複数ビットからなる矩形状の格納領域を有し１画素の情
報をｍ（ｍ＞ｎ）ビットで格納する表示メモリとを有
し、前記表示メモリの記憶内容に基づき画像表示を行う
画像処理システムを用いて、コンピュータの制御下で多
角形の内部の塗り潰し処理を行う多角形塗り潰し方法を
記録した記憶媒体であって、前記作業メモリの初期状態
は何も描画されていない白紙状態であり、(a)自己交差
しない塗り潰し対象の多角形の外形を構成する線分を規
定した外形情報を得るステップ、(b)前記外形情報に基
づき前記塗り潰し対象の多角形の外形を構成する線分を
所定回りに選択しながら、各線分に対して水平座標上の
所定の水平方向に該当する前記作業メモリ上の全てのビ
ットを反転させることにより前記ビット反転処理を行い
前記作業メモリ上に多角形の塗り潰し描画を行うステッ
プ、ここで前記ステップ(b)の前記ビット反転処理は、
線分自身に該当する前記作業メモリ上のビットをも反転
させる第１の反転モード及び線分自身を含まないで行う
第２の反転モードを含み、前記所定回りで選択された前
記塗り潰し対象の多角形の外形を構成する線分のうち、
そのベクトルの垂直方向変化が第１の垂直方向となる線
分は前記第１の反転モードで前記ビット反転処理を行
い、そのベクトルの垂直方向変化が第２の垂直方向とな
る線分は前記第２の反転モードで前記ビット反転処理を
行い、前記第１及び第２の垂直方向は、前記所定の回り
及び所定の水平方向の内容に基づき、前記塗り潰し対象
の多角形の外形を構成する線分のうち、そのベクトルが
前記１の垂直方向の線分は前記第１の反転モードで前記
ビット反転処理を行うと欠落なく線分描画がされ、その
ベクトルが前記２の垂直方向の線分は前記第２の反転モ
ードで前記ビット反転処理を行うと欠落なく線分描画さ
れるように決定される、及び(c)ステップ(b)の後、前記
作業メモリ上の情報を前記表示メモリに転送するステッ
プを実行させるためのプログラムを記録している。
【００４４】
【発明の実施の形態】
＜ハードウェア構成＞図１はこの発明の実施の形態１〜
７の各多角形塗り潰し方法を行う画像処理システムのハ
ードウェア構成を示すブロック図である。同図に示すよ
うに、ＣＰＵ１、メモリ２、表示回路３、表示メモリ
４、ＣＲＴ５及びＣＤ−ＲＯＭ６から構成され、ＣＰＵ
１、メモリ２、表示回路３及びＣＤ−ＲＯＭ６はバス１
０を介してデータの授受を行うことができる。
【００４５】ＣＰＵ１はＣＤ−ＲＯＭ６より後に詳述す
る多角形塗り潰し方法の処理手順を記録したプログラム
を読み込み、このプログラムに従い、メモリ２中に割り
当てられたワークメモリ２Ａの長方形の平面作業領域を
利用した多角形塗り潰し処理を実行し、最終的に、メモ
リ２内のワークメモリ２Ａに格納された描画情報をバス
１０及び表示回路３を介して表示メモリ４の長方形の平
面表示領域上に伸長転送する。表示回路３は表示メモリ
４の描画情報に基づきＣＲＴ５に画像を表示する。
【００４６】ワークメモリ２Ａは１(bit/pixel)で記憶
しているが、表示メモリ４は４(bit/pixel)（１６色表
示の場合）、８(bit/pixel)（２５６色表示場合）等、
多ビット／ピクセルで記憶することが一般的である。そ
こで、ワークメモリ２Ａの１ビットを伸長して、４(bit
/pixel)あるいは８(bit/pixel)にしてカラー情報を加味
して表示メモリ４に転送する必要がある。
【００４７】そこで、ＣＰＵ１はワークメモリ２Ａ上の
描画情報にカラー情報等の付加情報を加味して表示メモ
リ４に伸長転送する。なお、カラー情報はメモリ２内の
所定の領域に格納されたり、表示回路３内に格納された
りする。
【００４８】なお、図２に示すように構成して、メモリ
２と表示メモリ４とのデータ授受をバス１０のみを介し
て行えるように構成してもよい。
【００４９】また、図３及び図４に示すように、１つの
共用メモリ７内にワークメモリ７Ａ及び表示メモリ７Ｂ
を内蔵するように構成してもよい。図３で示した構成は
共用メモリ７が表示回路３に直接接続されている場合で
あり、図４で示した構成は共用メモリ７がバス１０に接
続されている場合である。なお、図３で示した構成の場
合、共用メモリ７内のワークメモリ７Ａから表示メモリ
７Ｂへの伸長転送処理は表示回路３の制御下で行うよう
にしてもよい。
【００５０】＜各実施の形態の原理＞描画用の１bit/pi
xelのワークメモリを用いたアウトラインフォント方式
により、図１〜図４で示した構成の画像処理システム
は、以下のステップを順次実行することにより多角形の
塗り潰し処理を行う。
【００５１】［実施の形態１］ 図５に示すように、塗
り潰し対象の多角形の外形を構成する線分を規定した外
形情報（頂点座標）を得た（ステップＳ１１）後、従来
技術の欄で述べた条件Ａ）〜Ｈ）により１bit/pixelの
ワークメモリにビット反転処理による多角形の塗り潰し
描画を行い（ステップＳ１２）、さらに多角形の枠（外
形を構成する線分全て）を描画した（ステップＳ１３）
後、ワークメモリから表示メモリに伸長転送する（ステ
ップＳ１４）。
【００５２】［実施の形態２］ 図６に示すように、外
形情報を得た（ステップＳ２１）後、自己交差をしない
多角形に対し、左回り（所定回りに該当）で線分を選択
しながら条件Ａ）〜Ｈ）により１bit/pixelのワークメ
モリにビット反転処理による多角形の塗り潰し描画を行
い（ステップＳ２２）、続いて、多角形の外形を構成す
る線分のうちその線分のベクトルが上向き（垂直方向座
標変化が上方向；所定の垂直方向に該当）の線分のみを
ワークメモリ上にさらに描画した（ステップＳ２３）
後、ワークメモリから表示メモリに伸長転送する（ステ
ップＳ２４）。
【００５３】なお、自己交差しない多角形とは頂点以外
に交点をもたない形状の多角形を意味し、図１２に示す
頂点Ｐ１１〜Ｐ１５からなる星型形状のように、頂点以
外交点Ｃ１〜Ｃ５を有する自己交差する形状はそれに含
まない。
【００５４】［実施の形態３］ 図７に示すように、外
形情報を得た（ステップＳ３１）後、自己交差をしない
多角形に対し、左回り（所定回りに該当）で線分を選択
しながら条件Ａ）〜Ｈ）により１bit/pixelのワークメ
モリにビット反転処理による多角形の塗り潰し描画を行
い（ステップＳ３２）、次にワークメモリから表示メモ
リに伸長転送した（ステップＳ３３）後、多角形の外形
を構成する線分のうち、その線分のベクトルが上向き
（所定の垂直方向に該当）の線分のみを表示メモリ上に
さらに描画する（ステップＳ３４）。
【００５５】［実施の形態４］ 図８に示すように、外
形情報を得た（ステップＳ４１）後、自己交差をしない
多角形に対し、右回り（所定回りに該当）で線分を選択
しながら条件Ａ）〜Ｈ）によりｌbit/pixelのワークメ
モリにビット反転処理による多角形の塗り潰し描画を行
い（ステップＳ４２）、続いて、多角形の外形を構成す
る線分のうちその線分のベクトルが下向き（垂直方向座
標変化が下方向；所定の垂直方向に該当）の線分のみを
ワークメモリ上にさらに描画した（ステップＳ４３）
後、ワークメモリから表示メモリに伸長転送する（ステ
ップＳ４４）。
【００５６】［実施の形態５］ 図９に示すように、外
形情報を得た（ステップＳ５１）後、自己交差をしない
多角形に対し、右回り（所定回りに該当）で線分を選択
しながら条件Ａ）〜Ｈ）により１bit/pixelのワークメ
モリにビット反転処理による多角形の塗り潰し描画を行
い（ステップＳ５２）、ワークメモリから表示メモリに
伸長転送した（ステップＳ５３）後、多角形の外形を構
成する線分のうち、その線分のベクトルが上向きの線分
のみを表示メモリ上にさらに描画する（ステップＳ５
４）。
【００５７】［実施の形態６］ 図１０に示すように、
外形情報を得た（ステップＳ６１）後、自己交差をしな
い多角形に対し、左回りで線分に関連した線分を選択を
選択しながら条件Ａ）〜Ｈ）により１bit/pixelのワー
クメモリにビット反転処理を行う（ステップＳ６２）。
このとき、線分（ベクトル）が上向き（第２の垂直方向
に該当）の線分についてはその線分を含まずにビット反
転処理を行い、それ以外の方向（第１の垂直方向に該
当）の線分については線分自身を含んでビット反転処理
を行う。その後、ワークメモリから表示メモリに伸長転
送する（ステップＳ６３）。
【００５８】［実施の形態７］ 図１１に示すように、
外形情報を得た（ステップＳ７１）後、自己交差をしな
い多角形に対し、右回りで線分に関連した線分を選択し
ながら条件Ａ）〜Ｈ）により１bit/pixelのワークメモ
リにビット反転処理を行う（ステップＳ７２）。このと
き、線分（ベクトル）が下向き（第２の垂直方向に該
当）の線分についてはその線分を含まずにビット反転処
理を行い、それ以外の方向（第１の垂直方向に該当）線
分については線分自身を含んでビット反転処理を行う。
その後、ワークメモリから表示メモリに伸長転送する
（ステップＳ７３）。
【００５９】＜実施の形態１＞図１３〜図１９はこの発
明の実施の形態１である多角形塗り潰し方法を説明する
ための説明図である。実施の形態１の多角形塗り潰し方
法を実行するハードウェア構成は図１〜図４のいずれの
構成であってもよい。以降、説明の都合上、図１のハー
ドウェア構成であるとする。
【００６０】まず、ＣＰＵ１はバス１０を介してＣＤ−
ＲＯＭ６より実施の形態１の多角形塗り潰し方法の処理
手順を記録したプログラムを読み込む。
【００６１】そして、図１３に示す外形をもつ塗り潰し
対象の三角形の外形情報として３頂点の座標｛Ｐ１（Ｈ
８，Ｓ２）、Ｐ２（Ｈ２，Ｓ１５）、Ｐ３（Ｈ１６，Ｓ
１１）｝を外部より得てメモリ２の所定領域に格納する
（図５のステップＳ１１）。また、メモリ２内のワーク
メモリ２Ａ上の平面作業領域の初期状態は白紙状態（全
く描画されていない状態）である。以降、図１３等の描
画の説明図において、白四角は無描画状態を意味し、黒
四角は描画状態を示している。
【００６２】なお、実施の形態１の多角形塗り潰し方法
は、図１４に示すように、塗り潰し対象の三角形に対し
て頂点Ｐ１〜Ｐ３の順で左回りに、線分ベクトルＬ１
（Ｈ２−Ｈ８，Ｓ１５−Ｓ２）、Ｌ２（Ｈ１６−Ｈ２，
Ｓ１１−Ｓ１５）、Ｌ３（Ｈ８−Ｈ１６，Ｓ２−Ｓ１
１）の順に選択して行く方法である。以下の動作は、Ｃ
Ｄ−ＲＯＭ６より読み込んだプログラムに基づくＣＰＵ
１の制御下で行われる。
【００６３】次に、図１５〜図１７に示すように、ワー
クメモリ２Ａ上でビット反転処理を実行する（図５のス
テップＳ１２）。以下、ビット反転処理について詳述す
る。
【００６４】まず、図１５に示すように、外形情報とし
て得られる頂点Ｐ１，Ｐ２の座標から、Bresenham等の
既存の直線アルゴリズムを用いて線分Ｌ１を求め、線分
Ｌ１に対して、線分Ｌ１自身を含み水平座標上の右方向
（所定の水平方向に該当）に該当するワークメモリ２Ａ
の平面作業領域（１bit/pixel）上の全てのビットを反
転させて描画する。このとき、線分（ベクトル）Ｌ１は
下向き（垂直方向座標変化が下方向）で線分（ベクト
ル）Ｌ２は上向き（垂直方向座標変化が上方向）であり
条件Ｄ）に該当するため、始点と終点を含めた線分Ｌ１
の右側のｂｉｔ反転を行う。
【００６５】次に、図１６に示すように、外形情報より
得られる頂点Ｐ２，Ｐ３の座標から、Bresenham等の既
存の直線アルゴリズムを用いて線分Ｌ２を求め、線分Ｌ
２に対して、線分Ｌ２自身を含んで水平座標上の右方向
に該当するワークメモリ２Ａの平面作業領域上の全ての
ビットを反転させる。その結果、図１５で示したステッ
プで既に描画されたビットがもう一度反転されて一部白
紙状態に戻る。
【００６６】なお、図１６は線分Ｌ２の途中の反転処理
経過を示している。このとき、線分Ｌ２及びＬ３は共に
上向きであり、条件Ａ）が該当するため、始点は含め、
終点を含めない線分Ｌ２の右側のｂｉｔ反転を行う。
【００６７】以降、同様にして、外形情報に基づき線分
Ｌ３を求め、線分Ｌ３に対して、線分Ｌ３自身を含み水
平座標上の右方向に該当するワークメモリ２Ａの平面作
業領域上の全てのビットを反転させる。なお、線分Ｌ３
が上向きで線分Ｌ１が下向きであり条件Ｃ）に該当する
ため、始点と終点を含めた線分Ｌ３の右側のｂｉｔ反転
を行う。その結果、ビット反転処理終了時には、図１７
に示すように、内部が塗り潰された三角形が完成する。
ただし、右側が１ビット（ピクセル）欠落した状態であ
り、不完全塗り潰し三角形となっている。
【００６８】次に、図１８に示すように、外形情報に基
づき求められた線分Ｌ１〜Ｌ３からなる三角形の枠（図
１８上の白四角内に縞模様のハッチングを付した部分）
を、ワークメモリ２Ａ上の不完全塗り潰し三角形上にさ
らに描画して、正確に塗り潰された三角形を完成する
（図５のステップＳ１３）。
【００６９】その後、図１９に示すように、ワークメモ
リ２Ａの平面作業領域上の描画情報をバス１０及び表示
回路３を介して表示メモリ４上の平面表示領域に伸長転
送する（図５のステップＳ１４）。
【００７０】その結果、表示回路３によって、表示メモ
リ３の記憶内容に基づき、内部が正確に塗り潰された三
角形がＣＲＴ５上に表示される。
【００７１】このように、実施の形態１の多角形塗り潰
し方法は、不完全塗り潰し多角形が描画されたワークメ
モリ上に当該多角形の枠を描画して正確な多角形塗り潰
しを行った後、ワークメモリから表示メモリに伸長転送
している。
【００７２】前述したように、カラー表示を行うため、
表示メモリのピクセルビット（１ピクセルを構成するビ
ット数）が４bit/pixelや８bit/pixel等であり、ワーク
メモリのピクセルビット（１bit/pixel）よりも多い。
【００７３】したがって、表示メモリよりもワークメモ
リの方が１ピクセルを構成するメモリ量が少なくなるた
め、実施の形態１のようにワークメモリ上で多角形の枠
描画を行うことにより、メモリアクセス数が減り、ＣＰ
Ｕにかかる負荷も抑えてより高速に多角形塗り潰し描画
処理を実現できる。
【００７４】なお、上記した実施の形態１の多角形塗り
潰し方法は、左回りで多角形を構成する線分を選択した
が、右回りで線分を選択しても同様に実現できる。実施
の形態１では、左回りあるいは右回りで選択された塗り
潰し対象の多角形の外形を構成する線分を全て描画する
ため、ビット反転処理終了後に得られた外形を構成する
任意の線分が欠落した不完全塗り潰し多角形から正確に
塗り潰した多角形を確実に得ることができる。
【００７５】また、上記した実施の形態１の多角形塗り
潰し方法は、ビット反転処理を線分自身を含んで反転さ
せたが、線分自身を含まずに反転させてもよい。
【００７６】また、上記した実施の形態１の多角形塗り
潰し方法は、「多角形の各線分の右方向をビット反転さ
せる」としているが、これを、「多角形の各線分の左方
向をビット反転させる」としても、同様な原理で可能で
ある。この場合、左側が１ビット（ピクセル）欠落した
状態の不完全塗り潰し多角形を枠の描画により正確な塗
り潰し多角形にすることができる。
【００７７】＜実施の形態２＞図２０〜図２５はこの発
明の実施の形態２である多角形塗り潰し方法を説明する
ための説明図である。実施の形態２の多角形塗り潰し方
法を実行するハードウェア構成は図１〜図４のいずれの
構成であってもよい。以降、説明の都合上、図１のハー
ドウェア構成であるとする。
【００７８】まず、ＣＰＵ１はバス１０を介してＣＤ−
ＲＯＭ６より実施の形態２の多角形塗り潰し方法の処理
手順を記録したプログラムを読み込む。なお、実施の形
態２の多角形塗り潰し方法は自己交差をしない多角形を
対象としている。
【００７９】そして、図２０に示す外形をもつ塗り潰し
対象の三角形の外形情報として３頂点の座標｛Ｐ１（Ｈ
８，Ｓ２）、Ｐ２（Ｈ２，Ｓ１５）、Ｐ３（Ｈ１６，Ｓ
１１）｝を外部より得てメモリ２の所定領域に格納する
（図６のステップＳ２１）。また、メモリ２内のワーク
メモリ２Ａ上の平面作業領域の初期状態は白紙状態であ
る。
【００８０】なお、実施の形態２の多角形塗り潰し方法
は、実施の形態１と同様、図１４に示すように、塗り潰
し対象の三角形に対して頂点Ｐ１〜Ｐ３の順で左回り
に、線分ベクトルＬ１、Ｌ２、Ｌ３の順に選択して行く
方法である。以下の動作は、ＣＤ−ＲＯＭ６より読み込
んだプログラムに基づくＣＰＵ１の制御下で行われる。
【００８１】次に、図２１〜図２３に示すように、ワー
クメモリ２Ａ上でビット反転処理を実行する（図６のス
テップＳ２２）。以下、ビット反転処理について詳述す
る。
【００８２】まず、図２１に示すように、外形情報とし
て得られる頂点Ｐ１，Ｐ２の座標から、Bresenham等の
既存の直線アルゴリズムを用いて線分Ｌ１を求め、線分
Ｌ１に対して、線分Ｌ１自身を含んで水平座標上の右方
向（所定の水平方向に該当）に該当するワークメモリ２
Ａの平面作業領域（１bit/pixel）上の全てのビットを
反転させて描画する。
【００８３】次に、図２２に示すように、外形情報より
得られる頂点Ｐ２，Ｐ３の座標から線分Ｌ２を求め、線
分Ｌ２に対して、線分Ｌ２自身を含んで水平座標上の右
方向に該当するワークメモリ２Ａの平面作業領域上の全
てのビットを反転させる。その結果、図２１で示したス
テップで既に描画されたビットがもう一度反転されて一
部白紙状態に戻る。
【００８４】以降、同様にして、外形情報に基づき線分
Ｌ３を求め、線分Ｌ３に対して、線分Ｌ３自身を含んで
水平座標上の右方向に該当するワークメモリ２Ａの平面
作業領域上の全てのビットを反転させる。その結果、ビ
ット反転処理終了時には、図２３に示すように、内部が
塗り潰された三角形が完成する。ただし、右側が１ビッ
ト（ピクセル）欠落した状態であり、不完全塗り潰し三
角形となっている。
【００８５】次に、図２４に示すように、外形情報に基
づき求められた線分Ｌ１〜Ｌ３のうち、そのベクトルが
上向き（垂直方向座標変化が上方向）の線分Ｌ２，Ｌ３
（図２４上の白四角内に縞模様のハッチングを付した部
分）のみをワークメモリ２Ａ上にさらに描画して、正確
に塗り潰された三角形を完成する（図６のステップＳ２
３）。
【００８６】その後、図２５に示すように、ワークメモ
リ２Ａの平面作業領域上の描画情報をバス１０及び表示
回路３を介して表示メモリ４上の平面表示領域に伸長転
送する（図６のステップＳ２４）。
【００８７】その結果、表示回路３によって、表示メモ
リ３の記憶内容に基づき、内部が正確に塗り潰された三
角形がＣＲＴ５上に表示される。
【００８８】このように、実施の形態２の多角形塗り潰
し方法は、自己交差しない多角形に対し、当該多角形の
外形を構成する線分を左回りで選択して多角形を塗り潰
して不完全塗り潰し多角形を描画したワークメモリ上
に、多角形の外形を構成する線分のうちその線分のベク
トルが上向き（垂直方向座標変化が上方向）の線分のみ
をさらに描画して正確な多角形塗り潰しを行った後、ワ
ークメモリから表示メモリに伸長転送している。
【００８９】したがって、表示メモリよりもワークメモ
リの方が１ピクセルを構成するメモリ量が少なくなるた
め、実施の形態２のようにワークメモリ上でベクトルが
上向きの線分の描画を行うことにより、メモリアクセス
数が減り、ＣＰＵ１にかかる負荷も抑えてより高速に多
角形塗り潰し描画処理を実現できる。
【００９０】加えて、多角形の外形を構成するすべての
線分を描画するのでなく、正確な多角形塗り潰しに必要
となる、多角形の右側の線分（そのベクトルが上向きの
線分）のみを効率的に描画することにより、より高速な
多角形塗り潰し描画処理が実現できる。
【００９１】なお、上記した実施の形態２の多角形塗り
潰し方法は、ビット反転処理を線分自身を含んで反転
（第１の反転モード）させたが、線分自身を含まずに反
転（第２の反転モード）させてもよい。線分自身を含ま
ずにビット反転処理を行うと、多角形の左側の線分が欠
落することになる。したがって、ビット反転処理の後、
多角形の左側の線分（そのベクトルが下向きの線分）の
みを描画するようにすればよい。
【００９２】また、上記した実施の形態２の多角形塗り
潰し方法は、「多角形の各線分の右方向をビット反転さ
せる」としているが、これを、「多角形の各線分の左方
向をビット反転させる」としても、同様な原理で可能で
ある。この場合、左側が１ビット（ピクセル）欠落した
状態の不完全塗り潰し多角形に対し、多角形の外形を構
成する成分のうちそのベクトルが下向きの線分の描画に
より正確な塗り潰し多角形にすることができる。
【００９３】＜実施の形態３＞図２６〜図３１はこの発
明の実施の形態３である多角形塗り潰し方法を説明する
ための説明図である。実施の形態３の多角形塗り潰し方
法を実行するハードウェア構成は図１〜図４のいずれの
構成であってもよい。以降、説明の都合上、図１のハー
ドウェア構成であるとする。
【００９４】まず、ＣＰＵ１はバス１０を介してＣＤ−
ＲＯＭ６より実施の形態３の多角形塗り潰し方法の処理
手順を記録したプログラムを読み込む。なお、実施の形
態３の多角形塗り潰し方法は自己交差をしない多角形を
対象としている。
【００９５】そして、図２６に示す外形をもつ塗り潰し
対象の三角形の外形情報として３頂点の座標｛Ｐ１（Ｈ
８，Ｓ２）、Ｐ２（Ｈ２，Ｓ１５）、Ｐ３（Ｈ１６，Ｓ
１１）｝を外部より得てメモリ２の所定領域に格納する
（図７のステップＳ３１）。また、メモリ２内のワーク
メモリ２Ａ上の平面作業領域の初期状態は白紙状態であ
る。
【００９６】なお、実施の形態３の多角形塗り潰し方法
は、実施の形態１及び実施の形態２と同様、図１４に示
すように、塗り潰し対象の三角形に対して頂点Ｐ１〜Ｐ
３の順で左回りに、線分ベクトルＬ１、Ｌ２、Ｌ３の順
に選択して行く方法である。以下の動作は、ＣＤ−ＲＯ
Ｍ６より読み込んだプログラムに基づくＣＰＵ１の制御
下で行われる。
【００９７】次に、図２７〜図２９に示すように、ワー
クメモリ２Ａ上でビット反転処理を実行する（図７のス
テップＳ３２）。以下、ビット反転処理について詳述す
る。
【００９８】まず、図２７に示すように、外形情報とし
て得られる頂点Ｐ１，Ｐ２の座標から、Bresenham等の
既存の直線アルゴリズムを用いて線分Ｌ１を求め、線分
Ｌ１に対して、線分Ｌ１自身を含んで水平座標上の右方
向（所定の水平方向に該当）に該当するワークメモリ２
Ａの平面作業領域（１bit/pixel）上の全てのビットを
反転させて描画する。
【００９９】次に、図２８に示すように、外形情報より
得られる頂点Ｐ２，Ｐ３の座標から線分Ｌ２を求め、線
分Ｌ２に対して、線分Ｌ２自身を含んで水平座標上の右
方向に該当するワークメモリ２Ａの平面作業領域上の全
てのビットを反転させる。その結果、図２７で示したス
テップで既に描画されたビットがもう一度反転されて一
部白紙状態に戻る。
【０１００】以降、同様にして、外形情報に基づき線分
Ｌ３を求め、線分Ｌ３に対して、線分Ｌ３自身を含んで
水平座標上の右方向に該当するワークメモリ２Ａの平面
作業領域上の全てのビットを反転させる。その結果、図
２９に示すように、内部が塗り潰された三角形が完成す
る。ただし、右側が１ビット（ピクセル）欠落した状態
であり、不完全塗り潰し三角形となっている。
【０１０１】その後、図３０に示すように、ワークメモ
リ２Ａの平面作業領域上の描画情報をバス１０及び表示
回路３を介して表示メモリ４上の平面表示領域に伸長転
送する（図７のステップＳＳ３）。
【０１０２】次に、図３１に示すように、外形情報に基
づき求められた線分Ｌ１〜Ｌ３のうち、そのベクトルが
上向き（垂直方向座標変化が上方向）の線分Ｌ２，Ｌ３
（図３１上の白四角内に縞模様のハッチングを付した部
分）のみを表示メモリ４上にさらに描画して、正確に塗
り潰された三角形を完成する（図７のステップＳ３
４）。
【０１０３】その結果、表示回路３によって、表示メモ
リ３の記憶内容に基づき内部が正確に塗り潰された三角
形がＣＲＴ５上に表示される。
【０１０４】このように、実施の形態３の多角形塗り潰
し方法は、自己交差しない多角形に対し、当該多角形の
外形を構成する線分を左回りで選択して多角形を塗り潰
して不完全塗り潰し多角形を描画した表示メモリ４上
に、多角形の外形を構成する線分のうちその線分のベク
トルが上向き（垂直方向座標変化が上方向）の線分のみ
をさらに描画して正確な多角形塗り潰しを行っている。
【０１０５】したがって、実施の形態２と同様、多角形
の外形を構成するすべての線分を描画するのでなく、正
確な多角形塗り潰しに必要となる、多角形の右側の線分
（そのベクトルが上向きの線分）のみを効率的に描画す
ることにより、より高速な多角形塗り潰し描画処理が実
現できる。
【０１０６】なお、上記した実施の形態３の多角形塗り
潰し方法は、ビット反転処理を線分自身を含んで反転さ
せた（第１の反転モード）が、線分自身を含まずに反転
させてもよい（第２の反転モード）。線分自身を含まず
にビット反転処理を行うと、多角形の左側の線分が欠落
することになる。したがって、ビット反転処理の後、多
角形の左側の線分（そのベクトルが下向きの線分）のみ
を描画するようにすればよい。
【０１０７】また、上記した実施の形態３の多角形塗り
潰し方法は、「多角形の各線分の右方向をビット反転さ
せる」としているが、これを、「多角形の各線分の左方
向をビット反転させる」としても、同様な原理で可能で
ある。この場合、左側が１ビット（ピクセル）欠落した
状態の不完全塗り潰し多角形に対し、多角形の外形を構
成する成分のうちそのベクトルが下向きの線分の描画に
より正確な塗り潰し多角形にすることができる。
【０１０８】＜実施の形態４＞図３２〜図３８はこの発
明の実施の形態４である多角形塗り潰し方法を説明する
ための説明図である。実施の形態４の多角形塗り潰し方
法を実行するハードウェア構成は図１〜図４のいずれの
構成であってもよい。以降、説明の都合上、図１のハー
ドウェア構成であるとする。
【０１０９】まず、ＣＰＵ１はバス１０を介してＣＤ−
ＲＯＭ６より実施の形態４の多角形塗り潰し方法の処理
手順を記録したプログラムを読み込む。なお、実施の形
態４の多角形塗り潰し方法は自己交差をしない多角形を
対象としている。
【０１１０】そして、図３２に示す外形をもつ塗り潰し
対象の三角形の外形情報として３頂点の座標｛Ｐ１（Ｈ
８，Ｓ２）、Ｐ２（Ｈ２，Ｓ１５）、Ｐ３（Ｈ１６，Ｓ
１１）｝を外部より得てメモリ２の所定領域に格納する
（図８のステップＳ４１）。また、メモリ２内のワーク
メモリ２Ａ上の平面作業領域の初期状態は白紙状態であ
る。
【０１１１】なお、実施の形態４の多角形塗り潰し方法
は、図３３に示すように、塗り潰し対象の三角形に対し
て頂点Ｐ１，Ｐ３，Ｐ２の順で右回りに、線分ベクトル
Ｌ１１（Ｈ１６−Ｈ８，Ｓ１１−Ｓ２）、Ｌ１２（Ｈ２
−Ｈ１６，Ｓ１５−Ｓ１１）、Ｌ１３（Ｈ８−Ｈ２，Ｓ
２−Ｓ１５）の順に選択して行く方法である。以下の動
作は、ＣＤ−ＲＯＭ６より読み込んだプログラムに基づ
くＣＰＵ１の制御下で行われる。
【０１１２】次に、図３４〜図３６に示すように、ワー
クメモリ２Ａ上でビット反転処理を実行する（図８のス
テップＳ４２）。以下、ビット反転処理について詳述す
る。まず、図３４に示すように、外形情報として得られ
る頂点Ｐ１，Ｐ３の座標から、Bresenham等の既存の直
線アルゴリズムを用いて線分Ｌ１１を求め、線分Ｌ１１
に対して、線分Ｌ１１自身を含んで水平座標上の右方向
（所定の水平方向に該当）に該当するワークメモリ２Ａ
の平面作業領域（１bit/pixel）上の全てのビットを反
転させて描画する。なお、図３４は線分Ｌ１１の途中の
反転処理経過を示している。
【０１１３】次に、外形情報より得られる頂点Ｐ２，Ｐ
３の座標から線分Ｌ１２を求め、線分Ｌ１２に対して、
線分Ｌ１２を含んで水平座標上の右方向に該当するワー
クメモリ２Ａの平面作業領域上の全てのビットを反転さ
せる。
【０１１４】そして、図３５に示すように、外形情報に
基づき線分Ｌ１３を求め、線分Ｌ１３に対して、線分Ｌ
１３を含んで水平座標上の右方向に該当するワークメモ
リ２Ａの平面作業領域上の全てのビットを反転させる。
この際、線分Ｌ１１及びＬ１２に基づくビット反転処理
で既に描画されたビットがもう一度反転されて一部白紙
状態に戻る。なお、図３５は線分Ｌ１３の途中の反転処
理経過を示している。
【０１１５】そして、ビット反転処理終了後には、図３
６に示すように、内部が塗り潰された三角形が完成す
る。ただし、右側が１ビット（ピクセル）欠落した状態
であり、不完全塗り潰し三角形となっている。
【０１１６】次に、図３７に示すように、外形情報に基
づき求められた線分Ｌ１１〜Ｌ１３のうち、そのベクト
ルが下向き（垂直方向座標変化が下方向）の線分Ｌ１
１，Ｌ１２（図３７上の白四角内に縞模様のハッチング
を付した部分）のみをワークメモリ２Ａ上にさらに描画
して、正確に塗り潰された三角形を完成する（図８のス
テップＳ４３）。
【０１１７】その後、図３８に示すように、ワークメモ
リ２Ａの平面作業領域上の描画情報をバス１０及び表示
回路３を介して表示メモリ４上の平面表示領域に伸長転
送する（図８のステップＳ４４）。
【０１１８】その結果、表示回路３によって、表示メモ
リ３の記憶内容に基づき、内部が正確に塗り潰された三
角形がＣＲＴ５上に表示される。
【０１１９】このように、実施の形態４の多角形塗り潰
し方法は、自己交差しない多角形に対し、当該多角形の
外形を構成する線分を右回りで選択して多角形を塗り潰
して不完全塗り潰し多角形を描画したワークメモリ上
に、多角形の外形を構成する線分のうちその線分のベク
トルが下向き（垂直方向座標変化が下方向）の線分のみ
をさらに描画して正確な多角形塗り潰しを行った後、ワ
ークメモリから表示メモリに伸長転送している。
【０１２０】したがって、表示メモリよりもワークメモ
リの方が１ピクセルを構成するメモリ量が少なくなるた
め、実施の形態４のようにワークメモリ上でベクトルが
下向きの線分の描画を行うことにより、メモリアクセス
数が減り、ＣＰＵにかかる負荷も抑えてより高速に多角
形塗り潰し描画処理を実現できる。
【０１２１】加えて、多角形の外形を構成するすべての
線分を描画するのでなく、正確な多角形塗り潰しに必要
となる、多角形の右側の線分（そのベクトルが下向きの
線分）のみを効率的に描画することにより、より高速な
多角形塗り潰し描画処理が実現できる。
【０１２２】なお、上記した実施の形態４の多角形塗り
潰し方法は、ビット反転処理を線分自身を含んで反転さ
せた（第１の反転モード）が、線分自身を含まずに反転
させてもよい（第２の反転モード）。線分自身を含まず
にビット反転処理を行うと、多角形の左側の線分が欠落
することになる。したがって、ビット反転処理の後、多
角形の左側の線分（そのベクトルが上向きの線分）のみ
を描画するようにすればよい。
【０１２３】また、上記した実施の形態４の多角形塗り
潰し方法は、「多角形の各線分の右方向をビット反転さ
せる」としているが、これを、「多角形の各線分の左方
向をビット反転させる」としても、同様な原理で可能で
ある。この場合、左側が１ビット（ピクセル）欠落した
状態の不完全塗り潰し多角形に対し、多角形の外形を構
成する成分のうちそのベクトルが上向きの線分の描画に
より正確な塗り潰し多角形にすることができる。
【０１２４】＜実施の形態５＞図３９〜図４４はこの発
明の実施の形態５である多角形塗り潰し方法を説明する
ための説明図である。実施の形態５の多角形塗り潰し方
法を実行するハードウェア構成は図１〜図４のいずれの
構成であってもよい。以降、説明の都合上、図１のハー
ドウェア構成であるとする。
【０１２５】まず、ＣＰＵ１はバス１０を介してＣＤ−
ＲＯＭ６より実施の形態５の多角形塗り潰し方法の処理
手順を記録したプログラムを読み込む。なお、実施の形
態５の多角形塗り潰し方法は自己交差をしない多角形を
対象としている。
【０１２６】そして、図３９に示す外形をもつ塗り潰し
対象の三角形の外形情報として３頂点の座標｛Ｐ１（Ｈ
８，Ｓ２）、Ｐ２（Ｈ２，Ｓ１５）、Ｐ３（Ｈ１６，Ｓ
１１）｝を外部より得てメモリ２の所定領域に格納する
（図９のステップＳ５１）。また、メモリ２内のワーク
メモリ２Ａ上の平面作業領域の初期状態は白紙状態であ
る。
【０１２７】なお、実施の形態５の多角形塗り潰し方法
は、実施の形態４と同様、図３３に示すように、塗り潰
し対象の三角形に対して頂点Ｐ１，Ｐ３，Ｐ２の順で右
回りに、線分ベクトルＬ１１、Ｌ１２、Ｌ１３の順に選
択して行く方法である。以下の動作は、ＣＤ−ＲＯＭ６
より読み込んだプログラムに基づくＣＰＵ１の制御下で
行われる。
【０１２８】次に、図４０〜図４２に示すように、ワー
クメモリ２Ａ上でビット反転処理を実行する（図９のス
テップＳ５２）。以下、ビット反転処理について詳述す
る。
【０１２９】まず、図４０に示すように、外形情報とし
て得られる頂点Ｐ１，Ｐ３の座標から、Bresenham等の
既存の直線アルゴリズムを用いて線分Ｌ１１を求め、線
分Ｌ１１に対して、線分Ｌ１１自身を含んで水平座標上
の右方向（所定の水平方向に該当）に該当するワークメ
モリ２Ａの平面作業領域（１bit/pixel）上の全てのビ
ットを反転させて描画する。なお、図４０は線分Ｌ１１
の途中の反転処理経過を示している。
【０１３０】次に、外形情報より得られる頂点Ｐ２，Ｐ
３の座標から線分Ｌ１２を求め、線分Ｌ１２に対して、
線分Ｌ１２を含んで水平座標上の右方向に該当するワー
クメモリ２Ａの平面作業領域上の全てのビットを反転さ
せる。
【０１３１】そして、図４１に示すように、外形情報に
基づき線分Ｌ１３を求め、線分Ｌ１３に対して、線分Ｌ
１３を含んで水平座標上の右方向に該当するワークメモ
リ２Ａの平面作業領域上の全てのビットを反転させる。
この際、線分Ｌ１１及びＬ１２に基づくビット反転処理
で既に描画されたビットがもう一度反転されて一部白紙
状態に戻る。なお、図４１は線分Ｌ１３の途中の反転処
理経過を示している。
【０１３２】そして、ビット反転処理終了時には、図４
２に示すように、内部が塗り潰された三角形が完成す
る。ただし、右側が１ビット（ピクセル）欠落した状態
であり、不完全塗り潰し三角形となっている。
【０１３３】その後、図４３に示すように、ワークメモ
リ２Ａの平面作業領域上の描画情報をバス１０及び表示
回路３を介して表示メモリ４上の平面表示領域に伸長転
送する（図９のステップＳ５３）。
【０１３４】次に、図４４に示すように、外形情報に基
づき求められた線分Ｌ１１〜Ｌ１３のうち、そのベクト
ルが下向き（垂直方向座標変化が下方向）の線分Ｌ１
１，Ｌ１２（図４３上の白四角内に縞模様のハッチング
を付した部分）のみを表示メモリ４上にさらに描画し
て、正確に塗り潰された三角形を完成する（図９のステ
ップＳ５４）。
【０１３５】その結果、表示回路３によって、表示メモ
リ３の記憶内容に基づき、内部が正確に塗り潰された三
角形がＣＲＴ５上に表示される。
【０１３６】このように、実施の形態５の多角形塗り潰
し方法は、自己交差しない多角形に対し、当該多角形の
外形を構成する線分を右回りで選択して多角形を塗り潰
して不完全塗り潰し多角形を描画した表示メモリ上に、
多角形の外形を構成する線分のうちその線分のベクトル
が下向き（垂直方向座標変化が下方向）の線分のみをさ
らに描画して正確な多角形塗り潰しを行っている。
【０１３７】したがって、多角形の外形を構成するすべ
ての線分を描画するのでなく、正確な多角形塗り潰しに
必要となる、多角形の右側の線分（そのベクトルが下向
きの線分）のみを効率的に描画することにより、より高
速な多角形塗り潰し描画処理が実現できる。
【０１３８】なお、上記した実施の形態５の多角形塗り
潰し方法は、ビット反転処理を線分自身を含んで反転さ
せた（第１の反転モード）が、線分自身を含まずに反転
させてもよい（第２の反転モード）。線分自身を含まず
にビット反転処理を行うと、多角形の左側の線分が欠落
することになる。したがって、ビット反転処理の後、多
角形の左側の線分（そのベクトルが上向きの線分）のみ
を描画するようにすればよい。
【０１３９】また、上記した実施の形態５の多角形塗り
潰し方法は、「多角形の各線分の右方向をビット反転さ
せる」としているが、これを、「多角形の各線分の左方
向をビット反転させる」としても、同様な原理で可能で
ある。この場合、左側が１ビット（ピクセル）欠落した
状態の不完全塗り潰し多角形に対し、多角形の外形を構
成する成分のうちそのベクトルが上向きの線分の描画に
より正確な塗り潰し多角形にすることができる。
【０１４０】＜実施の形態６＞図４５〜図５１はこの発
明の実施の形態６である多角形塗り潰し方法を説明する
ための説明図である。実施の形態６の多角形塗り潰し方
法を実行するハードウェア構成は図１〜図４のいずれの
構成であってもよい。以降、説明の都合上、図１のハー
ドウェア構成であるとする。
【０１４１】まず、ＣＰＵ１はバス１０を介してＣＤ−
ＲＯＭ６より実施の形態６の多角形塗り潰し方法の処理
手順を記録したプログラムを読み込む。なお、実施の形
態６の多角形塗り潰し方法は自己交差をしない多角形を
対象としている。
【０１４２】そして、図４５に示す外形をもつ塗り潰し
対象の三角形の外形情報として３頂点の座標｛Ｐ１（Ｈ
８，Ｓ２）、Ｐ２（Ｈ２，Ｓ１５）、Ｐ３（Ｈ１６，Ｓ
１１）｝を外部より得てメモリ２の所定領域に格納する
（図１０のステップＳ６１）。また、メモリ２内のワー
クメモリ２Ａ上の平面作業領域の初期状態は白紙状態で
ある。
【０１４３】なお、実施の形態６の多角形塗り潰し方法
は、実施の形態１〜３と同様、図１４に示すように、塗
り潰し対象の三角形に対して頂点Ｐ１〜Ｐ３の順で左回
りに、線分ベクトルＬ１、Ｌ２、Ｌ３の順に選択して行
く方法である。以下の動作は、ＣＤ−ＲＯＭ６より読み
込んだプログラムに基づくＣＰＵ１の制御下で行われ
る。
【０１４４】次に、図４６〜図５０に示すように、ワー
クメモリ２Ａ上でビット反転処理を実行する（図１０の
ステップＳ６２）。以下、ビット反転処理について詳述
する。
【０１４５】まず、外形情報として得られる頂点Ｐ１，
Ｐ２の座標から、Bresenham等の既存の直線アルゴリズ
ムを用いて線分Ｌ１を求め、線分Ｌ１は下向きであるた
め、図４６に示すように、線分Ｌ１に対して、線分Ｌ１
自身を含んで水平座標上の右方向（所定の水平方向に該
当）に該当するワークメモリ２Ａの平面作業領域（１bi
t/pixel）上の全てのビットを反転させて描画する（第
１の反転モードによるビット反転処理）。
【０１４６】次に、外形情報より得られる頂点Ｐ２，Ｐ
３の座標から線分Ｌ２を求め、線分Ｌ２は上向きである
ため、図４７に示すように、線分Ｌ２に対して、線分Ｌ
２を自身を含まずに水平座標上の右方向に該当するワー
クメモリ２Ａの平面作業領域上の全てのビットを反転さ
せる（第２の反転モードによるビット反転処理，図４８
で示す黒四角の領域ＡＲ１がビット反転対象領域とな
る）。その結果、図４６で示したステップで既に描画さ
れたビットがもう一度反転されて一部白紙状態に戻る。
【０１４７】以降、同様にして、外形情報に基づき線分
Ｌ３を求め、線分Ｌ３は上向きであるため線分Ｌ３に対
して、線分Ｌ３自身を含まずに水平座標上の右方向に該
当するワークメモリ２Ａの平面作業領域上の全てのビッ
トを反転させる（第２の反転モードによるビット反転処
理，図４９で示す黒四角の領域ＡＲ２がビット反転対象
領域となる）。その結果、ビット反転処理終了後は、図
５０に示すように、内部が正確に塗り潰された完全塗り
潰し三角形が完成する。
【０１４８】その後、図５１に示すように、ワークメモ
リ２Ａの平面作業領域上の描画情報をバス１０及び表示
回路３を介して表示メモリ４上の平面表示領域に伸長転
送する（図１０のステップＳ６３）。
【０１４９】その結果、表示回路３によって、表示メモ
リ３の記憶内容に基づき、内部が正確に塗り潰された三
角形がＣＲＴ５上に表示される。
【０１５０】このように、実施の形態６の多角形塗り潰
し方法は、自己交差しない多角形に対し、当該多角形の
外形を構成する線分に関連した選択線分を左回りで選択
して多角形を塗り潰して塗り潰し多角形をワークメモリ
上に描画する。この際、線分のベクトルが上向きの線分
の場合、線分自身を含まずに第２の反転モードによるビ
ット反転処理を行い、それ以外の線分（ベクトルが下向
き、ゼロ）の場合に線分自身を含んだ第１の反転モード
によるビット反転処理を行う。
【０１５１】したがって、表示メモリよりもワークメモ
リの方が１ピクセルを構成するメモリ量が少なくなるた
め、実施の形態６のようにワークメモリ上で全ての多角
形塗り潰し描画処理を行うことにより、メモリアクセス
数が減り、ＣＰＵにかかる負荷も抑えてより高速に多角
形塗り潰し描画処理を実現できる。
【０１５２】加えて、第１の反転モードあるいは第２の
反転モードによるビット反転処理のみによって一括して
完全な多角形の塗り潰しを行うことができるため、より
高速な多角形塗り潰し描画処理を実現できる。
【０１５３】なお、上記した実施の形態６の多角形塗り
潰し方法は、「多角形の各選択線分の右方向をビット反
転させる」としているが、これを、「多角形の各選択線
分の左方向をビット反転させる」としても、同様な原理
で可能である。この場合、多角形の外形を構成する成分
のうちそのベクトルが下向きの線分を水平座標上で左方
向に１ビットずらして選択線分とし、それ以外の線分は
線分自体を選択線分とする。
【０１５４】＜実施の形態７＞図５２〜図５８はこの発
明の実施の形態７である多角形塗り潰し方法を説明する
ための説明図である。実施の形態７の多角形塗り潰し方
法を実行するハードウェア構成は図１〜図４のいずれの
構成であってもよい。以降、説明の都合上、図１のハー
ドウェア構成であるとする。
【０１５５】まず、ＣＰＵ１はバス１０を介してＣＤ−
ＲＯＭ６より実施の形態７の多角形塗り潰し方法の処理
手順を記録したプログラムを読み込む。なお、実施の形
態７の多角形塗り潰し方法は自己交差をしない多角形を
対象としている。
【０１５６】そして、図５２に示す外形をもつ塗り潰し
対象の三角形の外形情報として３頂点の座標｛Ｐ１（Ｈ
８，Ｓ２）、Ｐ２（Ｈ２，Ｓ１５）、Ｐ３（Ｈ１６，Ｓ
１１）｝を外部より得てメモリ２の所定領域に格納する
（図１１のステップＳ７１）。また、メモリ２内のワー
クメモリ２Ａ上の平面作業領域の初期状態は白紙状態で
ある。
【０１５７】なお、実施の形態７の多角形塗り潰し方法
は、実施の形態４及び実施の形態５と同様、図３３に示
すように、塗り潰し対象の三角形に対して頂点Ｐ１，Ｐ
３，Ｐ２の順で右回りに、線分ベクトルＬ１１、Ｌ１
２、Ｌ１３の順に選択して行く方法である。以下の動作
は、ＣＤ−ＲＯＭ６より読み込んだプログラムに基づく
ＣＰＵ１の制御下で行われる。
【０１５８】次に、図５３〜図５７に示すように、ワー
クメモリ２Ａ上でビット反転処理を実行する（図１１の
ステップＳ７２）。以下、ビット反転処理について詳述
する。
【０１５９】まず、外形情報として得られる頂点Ｐ１，
Ｐ３の座標から、Bresenham等の既存の直線アルゴリズ
ムを用いて線分Ｌ１１を求め、線分Ｌ１１は下向きであ
るため、図５３に示すように、線分Ｌ１１に対して、線
分Ｌ１１を含まずに水平座標上の右方向（所定の水平方
向に該当）に該当するワークメモリ２Ａの平面作業領域
（１bit/pixel）上の全てのビットを反転させて描画す
る（第２の反転モードによるビット反転処理，図５４で
示す黒四角の領域ＡＲ３がビット反転対象領域とな
る）。
【０１６０】次に、外形情報より得られる頂点Ｐ２，Ｐ
３の座標から線分Ｌ１２を求め、線分Ｌ１２は下向きで
あるため線、線分Ｌ１２に対して、線分Ｌ１２を含まず
に水平座標上の右方向に該当するワークメモリ２Ａの平
面作業領域上の全てのビットを反転させる（第２の反転
モードによるビット反転処理，図５５で示す黒四角の領
域領域ＡＲ４がビット反転対象領域となる）。その結
果、図５３で示したステップで既に描画されたビットが
もう一度反転されて一部白紙状態に戻る。
【０１６１】以降、同様にして、外形情報に基づき線分
Ｌ１３を求め、線分Ｌ１３は上向きであるため、図５６
に示すように、線分Ｌ１３に対して、線分Ｌ１３を含ん
で水平座標上の右方向に該当するワークメモリ２Ａの平
面作業領域上の全てのビットを反転させる（第１の反転
モードによるビット反転処理）。なお、図５６は線分Ｌ
１３の選択線分の途中の反転処理経過を示している。
【０１６２】その結果、ビット反転処理終了時には、図
５７に示すように、内部が正確に塗り潰された完全塗り
潰し三角形が完成する。
【０１６３】その後、図５８に示すように、ワークメモ
リ２Ａの平面作業領域上の描画情報をバス１０及び表示
回路３を介して表示メモリ４上の平面表示領域に伸長転
送する（図１１のステップＳ７３）。
【０１６４】その結果、表示回路３によって、表示メモ
リ３の記憶内容に基づき、内部が正確に塗り潰された三
角形がＣＲＴ５上に表示される。
【０１６５】このように、実施の形態７の多角形塗り潰
し方法は、自己交差しない多角形に対し、当該多角形の
外形を構成する線分に関連した選択線分を右回りで選択
して多角形を塗り潰して塗り潰し多角形をワークメモリ
上に描画する。この際、線分のベクトルが下向きの線分
の場合、線分自身を含まずに第２の反転モードによるビ
ット反転処理を行い、それ以外の線分（ベクトルが上向
き、ゼロ）の場合に線分自身を含んだ第１の反転モード
によるビット反転処理を行う。
【０１６６】したがって、表示メモリよりもワークメモ
リの方が１ピクセルを構成するメモリ量が少なくなるた
め、実施の形態７のようにワークメモリ上で全ての多角
形塗り潰し描画処理を行うことにより、メモリアクセス
数が減り、ＣＰＵにかかる負荷も抑えてより高速に多角
形塗り潰し描画処理を実現できる。
【０１６７】加えて、第１の反転モードあるいは第２の
反転モードによるビット反転処理のみによって一括して
完全な多角形の塗り潰しを行うことができるため、より
高速な多角形塗り潰し描画処理を実現できる。
【０１６８】なお、上記した実施の形態７の多角形塗り
潰し方法は、「多角形の各選択線分の右方向をビット反
転させる」としているが、これを、「多角形の各選択線
分の左方向をビット反転させる」としても、同様な原理
で可能である。この場合、多角形の外形を構成する成分
のうちそのベクトルが上向きの線分を水平座標上で左方
向に１ビットずらして選択線分とし、それ以外の線分は
線分自体を選択線分とする。
【０１６９】
【発明の効果】以上説明したように、この発明における
請求項１記載の多角形塗り潰し方法は、ステップ(c)
で、多角形の塗り潰し描画がなされた作業メモリ上に、
外形情報に基づき塗り潰し対象の多角形の外形を構成す
る線分をさらに描画するため、ステップ(b)で外形を構
成する線分の一部が描画されていない不完全塗り潰し多
角形が描画されても正確に塗り潰した多角形を得ること
ができる。
【０１７０】そして、表示メモリよりも作業メモリの方
が１画素を構成するビット数が少ないため、作業メモリ
上で上記ステップ(c)の処理を行うことにより、メモリ
アクセス数が減り、ＣＰＵにかかる負荷も抑えてより高
速に多角形塗り潰し描画処理を実現できる。
【０１７１】請求項２記載の多角形塗り潰し方法のステ
ップ(c)は、所定回りで選択された塗り潰し対象の多角
形の外形を構成する線分を全て描画するため、外形を構
成する任意の線分が欠落した不完全塗り潰し多角形から
正確に塗り潰した多角形を確実に得ることができる。
【０１７２】請求項３記載の多角形塗り潰し方法のステ
ップ(c)は、所定回りで選択された塗り潰し対象の多角
形の外形を構成する線分のうち、そのベクトルの垂直方
向変化が第２の方向となる線分のみを描画する。この第
２の方向はステップ(b)のビット反転処理で描画されず
に欠落した線分が有する垂直方向変化である。
【０１７３】したがって、ステップ(c)において多角形
の外形を構成するすべての線分を描画するのでなく、正
確な多角形塗り潰しに必要となる、そのベクトルが第２
の方向の線分のみを効率的に描画することにより、より
高速な多角形塗り潰し描画処理が実現できる。
【０１７４】この発明における請求項４記載の多角形塗
り潰し方法のステップ(d)は、所定回りで選択された塗
り潰し対象の多角形の外形を構成する線分のうち、その
ベクトルの垂直方向変化が第２の方向となる線分のみを
描画する。この第２の方向はステップ(b)のビット反転
処理で描画されずに欠落した線分が有する垂直方向変化
である。
【０１７５】したがって、ステップ(d)において多角形
の外形を構成するすべての線分を描画するのでなく、正
確な多角形塗り潰しに必要となる、そのベクトルが第２
の方向の線分のみを効率的に描画することにより、より
高速な多角形塗り潰し描画処理が実現できる。
【０１７６】請求項５記載の多角形塗り潰し方法のよう
に、ビット反転処理が線分自身に該当する作業メモリ上
のビットをも反転させる第１の反転モードであり、所定
回りは左回りであり、所定の水平方向は右方向である場
合、第２の方向は上方向に一意に決定する。
【０１７７】請求項６記載の多角形塗り潰し方法のよう
に、ビット反転処理が線分自身に該当する作業メモリ上
のビットをも反転させる第１の反転モードであり、所定
回りは右回りであり、所定の水平方向は右方向である場
合、第２の方向は下方向に一意に決定する。
【０１７８】請求項７記載の多角形塗り潰し方法のよう
に、ビット反転処理が線分自身を含まないで行う第２の
反転モードであり、所定回りは左回りであり、所定の水
平方向は右方向である場合、第２の方向は下方向に一意
に決定する。
【０１７９】請求項８記載の多角形塗り潰し方法のよう
に、ビット反転処理が線分自身を含まないで行う第２の
反転モードであり、所定回りは右回りであり、所定の水
平方向は右方向である場合、第２の方向は上方向に一意
に決定する。
【０１８０】この発明における請求項９記載の多角形塗
り潰し方法におけるステップ(b)のビット反転処理は、
線分自身に該当する作業メモリ上のビットをも反転させ
る第１の反転モード及び線分自身を含まないでビット反
転を行う第２の反転モードを含み、所定回りで選択され
た塗り潰し対象の多角形の外形を構成する線分のうち、
そのベクトルの垂直方向変化が第１の垂直方向となる線
分は第１の反転モードでビット反転処理を行い、そのベ
クトルの垂直方向変化が第２の垂直方向となる線分は第
２の反転モードでビット反転処理を行う。
【０１８１】そして、塗り潰し対象の多角形の外形を構
成する線分のうち、そのベクトルが１の垂直方向の線分
は第１の反転モードでビット反転処理を行うと欠落なく
線分描画がされ、そのベクトルが２の垂直方向の線分は
第２の反転モードでビット反転処理を行うと欠落なく線
分描画されるように第１及び第２の垂直方向が決定され
る。
【０１８２】その結果、ステップ(b)の処理で、塗り潰
し対象の多角形の正確な塗り潰し処理描画を一括して行
うことができるため、より高速な多角形塗り潰し描画処
理を実現できる。
【０１８３】加えて、表示メモリよりも作業メモリの方
が１画素を構成するビット数が少ないため、作業メモリ
上で上記ステップ(b)の処理を行うことにより、メモリ
アクセス数が減り、ＣＰＵにかかる負荷も抑えてより高
速に多角形塗り潰し描画処理を実現できる。
【０１８４】請求項１０記載の多角形塗り潰し方法のよ
うに、所定回りは左回りであり、所定の水平方向は右方
向である場合、第１の垂直方向は下方向、第２の垂直方
向は上方向でそれぞれ一意に決定する。
【０１８５】請求項１１記載の多角形塗り潰し方法のよ
うに、所定回りは右回りであり、所定の水平方向は右方
向である場合、第１の垂直方向は上方向、第２の垂直方
向は下方向にそれぞれ一意に決定する。
【０１８６】この発明における請求項１２記載の記憶媒
体で記録されたプログラムによって実行されるステップ
(c)で、多角形の塗り潰し描画がなされた作業メモリ上
に、外形情報に基づき塗り潰し対象の多角形の外形を構
成する線分をさらに描画するため、ステップ(b)で外形
を構成する線分の一部が描画されていない不完全塗り潰
し多角形が描画されても正確に塗り潰した多角形を得る
ことができる。
【０１８７】この発明における請求項１３記載の記録媒
体で記録されたプログラムによって実行されるステップ
(d)は、所定回りで選択された塗り潰し対象の多角形の
外形を構成する線分のうち、そのベクトルの垂直方向変
化が第２の方向となる線分のみを描画する。この第２の
方向はステップ(b)のビット反転処理で描画されずに欠
落した線分が有する垂直方向変化である。
【０１８８】したがって、多角形の外形を構成するすべ
ての線分を描画するのでなく、正確な多角形塗り潰しに
必要となる、そのベクトルが第２の方向の線分のみを効
率的に描画することにより、より高速な多角形塗り潰し
描画処理が実現できる。
【０１８９】この発明における請求項１４記載の記録媒
体で記録されたプログラムによって実行されるステップ
(b)のビット反転処理は、線分自身に該当する作業メモ
リ上のビットをも反転させる第１の反転モード及び線分
自身を含まないで行う第２の反転モードを含み、所定回
りで選択された塗り潰し対象の多角形の外形を構成する
線分のうち、そのベクトルの垂直方向変化が第１の垂直
方向となる線分は第１の反転モードでビット反転処理を
行い、そのベクトルの垂直方向変化が第２の垂直方向と
なる線分は第２の反転モードでビット反転処理を行う。
【０１９０】そして、塗り潰し対象の多角形の外形を構
成する線分のうち、そのベクトルが１の垂直方向の線分
は第１の反転モードでビット反転処理を行うと欠落なく
線分描画が行え、そのベクトルが２の垂直方向の線分は
第２の反転モードでビット反転処理を行うと欠落なく線
分描画が行えるように第１及び第２の垂直方向が決定さ
れる。
【０１９１】その結果、請求項１４記載の記録媒体で記
録されたプログラムによって実行されるステップ(b)の
処理で、塗り潰し対象の多角形の正確な塗り潰し処理描
画を一括して行うことができるため、より高速な多角形
塗り潰し描画処理を実現できる。
【０１９２】加えて、表示メモリよりも作業メモリの方
が１画素を構成するビット数が少ないため、作業メモリ
上で上記ステップ(b)の処理を行うことにより、メモリ
アクセス数が減り、ＣＰＵにかかる負荷も抑えてより高
速に多角形塗り潰し描画処理を実現できる。
【図面の簡単な説明】
【図１】 この発明の全実施の形態で用いるハードウェ
ア構成を示すブロック図である。
【図２】 他のハードウェア構成を示すブロック図であ
る。
【図３】 他のハードウェア構成を示すブロック図であ
る。
【図４】 他のハードウェア構成を示すブロック図であ
る。
【図５】 実施の形態１の多角形塗り潰し方法の処理手
順を示すフローチャートである。
【図６】 実施の形態２の多角形塗り潰し方法の処理手
順を示すフローチャートである。
【図７】 実施の形態３の多角形塗り潰し方法の処理手
順を示すフローチャートである。
【図８】 実施の形態４の多角形塗り潰し方法の処理手
順を示すフローチャートである。
【図９】 実施の形態５の多角形塗り潰し方法の処理手
順を示すフローチャートである。
【図１０】 実施の形態６の多角形塗り潰し方法の処理
手順を示すフローチャートである。
【図１１】 実施の形態７の多角形塗り潰し方法の処理
手順を示すフローチャートである。
【図１２】 自己交差する多角形を示す説明図である。
【図１３】 この発明の実施の形態１である多角形塗り
潰し方法の説明用の説明図である。
【図１４】 実施の形態１の多角形塗り潰し方法を示す
概略図である。
【図１５】 実施の形態１の多角形塗り潰し方法を示す
説明図である。
【図１６】 実施の形態１の多角形塗り潰し方法を示す
説明図である。
【図１７】 実施の形態１の多角形塗り潰し方法を示す
説明図である。
【図１８】 実施の形態１の多角形塗り潰し方法を示す
説明図である。
【図１９】 実施の形態１の多角形塗り潰し方法を示す
説明図である。
【図２０】 この発明の実施の形態２である多角形塗り
潰し方法を示す説明図である。
【図２１】 実施の形態２の多角形塗り潰し方法を示す
説明図である。
【図２２】 実施の形態２の多角形塗り潰し方法を示す
説明図である。
【図２３】 実施の形態２の多角形塗り潰し方法を示す
説明図である。
【図２４】 実施の形態２の多角形塗り潰し方法を示す
説明図である。
【図２５】 実施の形態２の多角形塗り潰し方法を示す
説明図である。
【図２６】 この発明の実施の形態３である多角形塗り
潰し方法を示す説明図である。
【図２７】 実施の形態３の多角形塗り潰し方法を示す
説明図である。
【図２８】 実施の形態３の多角形塗り潰し方法を示す
説明図である。
【図２９】 実施の形態３の多角形塗り潰し方法を示す
説明図である。
【図３０】 実施の形態３の多角形塗り潰し方法を示す
説明図である。
【図３１】 実施の形態３の多角形塗り潰し方法を示す
説明図である。
【図３２】 この発明の実施の形態４である多角形塗り
潰し方法を示す説明図である。
【図３３】 実施の形態４の多角形塗り潰し方法を示す
概略図である。
【図３４】 実施の形態４の多角形塗り潰し方法を示す
説明図である。
【図３５】 実施の形態４の多角形塗り潰し方法を示す
説明図である。
【図３６】 実施の形態４の多角形塗り潰し方法を示す
説明図である。
【図３７】 実施の形態４の多角形塗り潰し方法を示す
説明図である。
【図３８】 実施の形態４の多角形塗り潰し方法を示す
説明図である。
【図３９】 この発明の実施の形態５である多角形塗り
潰し方法を示す説明図である。
【図４０】 実施の形態５の多角形塗り潰し方法を示す
説明図である。
【図４１】 実施の形態５の多角形塗り潰し方法を示す
説明図である。
【図４２】 実施の形態５の多角形塗り潰し方法を示す
説明図である。
【図４３】 実施の形態５の多角形塗り潰し方法を示す
説明図である。
【図４４】 実施の形態５の多角形塗り潰し方法を示す
説明図である。
【図４５】 この発明の実施の形態６である多角形塗り
潰し方法を示す説明図である。
【図４６】 実施の形態６の多角形塗り潰し方法を示す
説明図である。
【図４７】 実施の形態６の多角形塗り潰し方法を示す
説明図である。
【図４８】 第２の反転モードによる反転対象領域を示
す説明図である。
【図４９】 第２の反転モードによる反転対象領域を示
す説明図である。
【図５０】 実施の形態６の多角形塗り潰し方法を示す
説明図である。
【図５１】 実施の形態６の多角形塗り潰し方法を示す
説明図である。
【図５２】 この発明の実施の形態７である多角形塗り
潰し方法を示す説明図である。
【図５３】 実施の形態７の多角形塗り潰し方法を示す
説明図である。
【図５４】 第２の反転モードによる反転対象領域を示
す説明図である。
【図５５】 第２の反転モードによる反転対象領域を示
す説明図である。
【図５６】 実施の形態７の多角形塗り潰し方法を示す
説明図である。
【図５７】 実施の形態７の多角形塗り潰し方法を示す
説明図である。
【図５８】 実施の形態７の多角形塗り潰し方法を示す
説明図である。
【図５９】 従来のスキャンライン法を示す説明図であ
る。
【図６０】 従来のスキャンライン法を示す概略図であ
る。
【図６１】 従来のアウトラインフォント方式を示す説
明図である。
【図６２】 従来のアウトラインフォント方式を示す概
略図である。
【図６３】 従来のアウトラインフォント方式を示す説
明図である。
【図６４】 従来のアウトラインフォント方式を示す説
明図である。
【図６５】 従来のアウトラインフォント方式を示す説
明図である。
【図６６】 従来のアウトラインフォント方式を示す説
明図である。
【符号の説明】
１ ＣＰＵ、２ メモリ、３ 表示回路、４ 表示メモ
リ、５ ＣＲＴ、６ＣＤ−ＲＯＭ、７ 共用メモリ、１
０ バス。

Claims (14)

    【特許請求の範囲】
  1. 【請求項１】 複数ビットからなる矩形状の格納領域を
    有し１画素の情報をｎ（ｎ≧１）ビットで格納する作業
    メモリと、複数ビットからなる矩形状の格納領域を有し
    １画素の情報をｍ（ｍ＞ｎ）ビットで格納する表示メモ
    リとを有し、前記表示メモリの記憶内容に基づき画像表
    示を行う画像処理システムを用いて多角形の内部の塗り
    潰し処理を行う多角形塗り潰し方法であって、前記作業
    メモリの初期状態は何も描画されていない白紙状態であ
    り、 (a)塗り潰し対象の多角形の外形を構成する線分を規定
    した外形情報を得るステップと、 (b)前記外形情報に基づき前記塗り潰し対象の多角形の
    外形を構成する各線分を所定回りに選択しながら、各線
    分に対して水平座標上の所定の水平方向に該当する前記
    作業メモリ上の全てのビットを反転させることによりビ
    ット反転処理を行い多角形の塗り潰し描画を行うステッ
    プと、 (c)前記多角形の塗り潰し描画がなされた前記作業メモ
    リ上に、前記外形情報に基づき前記塗り潰し対象の多角
    形の外形を構成する線分をさらに描画するステップと、 (d)前記ステップ(c)の後、前記作業メモリの格納情報を
    前記表示メモリに転送するステップと、を備える多角形
    塗り潰し方法。
  2. 【請求項２】 前記ステップ(c)は、前記所定回りで選
    択された前記塗り潰し対象の多角形の外形を構成する線
    分を全て描画するステップを含む、請求項１記載の多角
    形塗り潰し方法。
  3. 【請求項３】 前記塗り潰し対象の多角形は、自己交差
    をしない多角形を含み、 前記ステップ(b)の前記ビット反転処理は、線分自身に
    該当する前記作業メモリ上のビットをも反転させる第１
    の反転モード及び線分自身を含まないでビット反転を行
    う第２の反転モードにうち一方のモードを含み、 前記ステップ(c)は、前記所定回りで選択された前記塗
    り潰し対象の多角形の外形を構成する線分のうち、その
    ベクトルの垂直方向変化が所定の垂直方向となる線分の
    みを描画するステップを含み、前記所定の垂直方向は、
    前記ビット反転処理、前記所定回り及び前記所定の水平
    方向の内容に基づき決定され、前記ステップ(b)の前記
    ビット反転処理で描画されずに欠落した線分が有する垂
    直方向変化である、請求項１記載の多角形塗り潰し方
    法。
  4. 【請求項４】 複数ビットからなる矩形状の格納領域を
    有し１画素の情報をｎ（ｎ≧１）ビットで格納する作業
    メモリと、複数ビットからなる矩形状の格納領域を有し
    １画素の情報をｍ（ｍ＞ｎ）ビットで格納する表示メモ
    リとを有し、前記表示メモリの記憶内容に基づき画像表
    示を行う画像処理システムを用いて多角形の内部の塗り
    潰し処理を行う多角形塗り潰し方法であって、前記作業
    メモリの初期状態は何も描画されていない白紙状態であ
    り、 (a)自己交差をしない塗り潰し対象の多角形の外形を構
    成する線分を規定した外形情報を得るステップと、 (b)前記外形情報に基づき前記塗り潰し対象の多角形の
    外形を構成する線分を所定回りに選択しながら、各線分
    に対して水平座標上の所定の水平方向に該当する前記作
    業メモリ上の全てのビットを反転させることによりビッ
    ト反転処理を行い前記作業メモリ上に多角形の塗り潰し
    描画を行うステップとを備え、前記ビット反転処理は、
    線分自身に該当する前記作業メモリ上のビットをも反転
    させる第１の反転モードあるいは線分自身を含まないで
    ビット反転を行う第２の反転モードを含み、 (c)前記ステップ(b)の後、前記作業メモリ上の情報を前
    記表示メモリに転送するステップと、 (d)前記ステップ(c)の後、前記表示メモリ上に、前記外
    形情報に基づき、前記所定回りで選択された前記塗り潰
    し対象の多角形の外形を構成する線分のうち、そのベク
    トルの垂直方向変化が所定の垂直方向となる線分のみを
    描画するステップとをさらに備え、前記所定の垂直方向
    は、前記ビット反転処理、前記所定回り及び前記所定の
    水平方向の内容に基づき決定され、前記ステップ(b)の
    前記ビット反転処理で描画されずに欠落した線分が有す
    る垂直方向変化である、多角形塗り潰し方法。
  5. 【請求項５】 前記ビット反転処理は前記第１の反転モ
    ードを含み、 前記所定回りは左回りを含み、 前記所定の水平方向は右方向を含み、 前記所定の垂直方向は上方向を含む、請求項３あるいは
    請求項４記載の多角形塗り潰し方法。
  6. 【請求項６】 前記ビット反転処理は前記第１の反転モ
    ードを含み、 前記所定回りは右回りを含み、 前記所定の水平方向は右方向を含み、 前記所定の垂直方向は下方向を含む、請求項３あるいは
    請求項４記載の多角形塗り潰し方法。
  7. 【請求項７】 前記ビット反転処理は前記第２の反転モ
    ードを含み、 前記所定回りは左回りを含み、 前記所定の水平方向は右方向を含み、 前記所定の垂直方向は下方向を含む、請求項３あるいは
    請求項４記載の多角形塗り潰し方法。
  8. 【請求項８】 前記ビット反転処理は前記第２の反転モ
    ードを含み、 前記所定回りは右回りを含み、 前記所定の水平方向は右方向を含み、 前記所定の垂直方向は上方向を含む、請求項３あるいは
    請求項４記載の多角形塗り潰し方法。
  9. 【請求項９】 複数ビットからなる矩形状の格納領域を
    有し１画素の情報をｎ（ｎ≧１）ビットで格納する作業
    メモリと、複数ビットからなる矩形状の格納領域を有し
    １画素の情報をｍ（ｍ＞ｎ）ビットで格納する表示メモ
    リとを有し、前記表示メモリの記憶内容に基づき画像表
    示を行う画像処理システムを用いて多角形の内部の塗り
    潰し処理を行う多角形塗り潰し方法であって、前記作業
    メモリの初期状態は何も描画されていない白紙状態であ
    り、 (a)自己交差しない塗り潰し対象の多角形の外形を構成
    する線分を規定した外形情報を得るステップと、 (b)前記外形情報に基づき前記塗り潰し対象の多角形の
    外形を構成する線分を所定回りに選択しながら、各線分
    に対して水平座標上の所定の水平方向に該当する前記作
    業メモリ上の全てのビットを反転させることにより前記
    ビット反転処理を行い前記作業メモリ上に多角形の塗り
    潰し描画を行うステップと、 (c)ステップ(b)の後、前記作業メモリ上の情報を前記表
    示メモリに転送するステップとを備え、 前記ステップ(b)の前記ビット反転処理は、線分自身に
    該当する前記作業メモリ上のビットをも反転させる第１
    の反転モード及び線分自身を含まないでビット反転を行
    う第２の反転モードを含み、前記所定回りで選択された
    前記塗り潰し対象の多角形の外形を構成する線分のう
    ち、そのベクトルの垂直方向変化が第１の垂直方向とな
    る線分は前記第１の反転モードで前記ビット反転処理を
    行い、そのベクトルの垂直方向変化が第２の垂直方向と
    なる線分は前記第２の反転モードで前記ビット反転処理
    を行い、 前記第１及び第２の垂直方向は、前記所定の回り及び所
    定の水平方向の内容に基づき、前記塗り潰し対象の多角
    形の外形を構成する線分のうち、そのベクトルが前記１
    の垂直方向の線分は前記第１の反転モードで前記ビット
    反転処理を行うと欠落なく描画され、そのベクトルが前
    記２の垂直方向の線分は前記第２の反転モードで前記ビ
    ット反転処理を行うと欠落なく描画されるように決定さ
    れる、多角形塗り潰し方法。
  10. 【請求項１０】 前記所定回りは左回りを含み、 前記所定の水平方向は右方向を含み、 前記第１の垂直方向は下方向を含み、 前記第２の垂直方向は上方向を含む、請求項９記載の多
    角形塗り潰し方法。
  11. 【請求項１１】 前記所定回りは右回りを含み、 前記所定の水平方向は右方向を含み、 前記第１の垂直方向は上方向を含み、 前記第２の垂直方向は下方向を含む、請求項９記載の多
    角形塗り潰し方法。
  12. 【請求項１２】 複数ビットからなる矩形状の格納領域
    を有し１画素の情報をｎ（ｎ≧１）ビットで格納する作
    業メモリと、複数ビットからなる矩形状の格納領域を有
    し１画素の情報をｍ（ｍ＞ｎ）ビットで格納する表示メ
    モリとを有し、前記表示メモリの記憶内容に基づき画像
    表示を行う画像処理システムを用いて、コンピュータの
    制御下で多角形の内部の塗り潰し処理を行う多角形塗り
    潰し方法を記録した記憶媒体であって、前記作業メモリ
    の初期状態は何も描画されていない白紙状態であり、 (a)塗り潰し対象の多角形の外形を構成する線分を規定
    した外形情報を得るステップ、 (b)前記外形情報に基づき前記塗り潰し対象の多角形の
    外形を構成する各線分を所定回りに選択しながら、各線
    分に対して水平座標上の所定の水平方向に該当する前記
    作業メモリ上の全てのビットを反転させることによりビ
    ット反転処理を行い多角形の塗り潰し描画を行うステッ
    プ、 (c)前記多角形の塗り潰し描画がなされた前記作業メモ
    リ上に、前記外形情報に基づき前記塗り潰し対象の多角
    形の外形を構成する線分をさらに描画するステップ、及
    び (d)前記ステップ(c)の後、前記作業メモリの格納情報を
    前記表示メモリに転送するステップ、を実行させるため
    のプログラムを記録したコンピュータ読み取り可能な記
    録媒体。
  13. 【請求項１３】 複数ビットからなる矩形状の格納領域
    を有し１画素の情報をｎ（ｎ≧１）ビットで格納する作
    業メモリと、複数ビットからなる矩形状の格納領域を有
    し１画素の情報をｍ（ｍ＞ｎ）ビットで格納する表示メ
    モリとを有し、前記表示メモリの記憶内容に基づき画像
    表示を行う画像処理システムを用いて、コンピュータの
    制御下で多角形の内部の塗り潰し処理を行う多角形塗り
    潰し方法を記録した記憶媒体であって、前記作業メモリ
    の初期状態は何も描画されていない白紙状態であり、 (a)自己交差をしない塗り潰し対象の多角形の外形を構
    成する線分を規定した外形情報を得るステップ、 (b)前記外形情報に基づき前記塗り潰し対象の多角形の
    外形を構成する線分を所定回りに選択しながら、各線分
    に対して水平座標上の所定の水平方向に該当する前記作
    業メモリ上の全てのビットを反転させることによりビッ
    ト反転処理を行い前記作業メモリ上に多角形の塗り潰し
    描画を行うステップ、ここで前記ビット反転処理は、線
    分自身に該当する前記作業メモリ上のビットをも反転さ
    せる第１の反転モードあるいは線分自身を含まないでビ
    ット反転を行う第２の反転モードを含み、 (c)前記ステップ(b)の後、前記作業メモリ上の情報を前
    記表示メモリに転送するステップ、及び (d)前記ステップ(c)の後、前記表示メモリ上に、前記外
    形情報に基づき、前記所定回りで選択された前記塗り潰
    し対象の多角形の外形を構成する線分のうち、そのベク
    トルの垂直方向変化が所定の垂直方向となる線分のみを
    描画するステップ、ここで前記所定の垂直方向は、前記
    ビット反転処理、前記所定回り及び前記所定の水平方向
    の内容に基づき決定され、前記ステップ(b)のビット反
    転処理で欠落した線分が有する垂直方向変化である、を
    実行させるためのプログラムを記録したコンピュータ読
    み取り可能な記録媒体。
  14. 【請求項１４】 複数ビットからなる矩形状の格納領域
    を有し１画素の情報をｎ（ｎ≧１）ビットで格納する作
    業メモリと、複数ビットからなる矩形状の格納領域を有
    し１画素の情報をｍ（ｍ＞ｎ）ビットで格納する表示メ
    モリとを有し、前記表示メモリの記憶内容に基づき画像
    表示を行う画像処理システムを用いて、コンピュータの
    制御下で多角形の内部の塗り潰し処理を行う多角形塗り
    潰し方法を記録した記憶媒体であって、前記作業メモリ
    の初期状態は何も描画されていない白紙状態であり、 (a)自己交差しない塗り潰し対象の多角形の外形を構成
    する線分を規定した外形情報を得るステップ、 (b)前記外形情報に基づき前記塗り潰し対象の多角形の
    外形を構成する線分を所定回りに選択しながら、各線分
    に対して水平座標上の所定の水平方向に該当する前記作
    業メモリ上の全てのビットを反転させることにより前記
    ビット反転処理を行い前記作業メモリ上に多角形の塗り
    潰し描画を行うステップ、ここで前記ステップ(b)の前
    記ビット反転処理は、線分自身に該当する前記作業メモ
    リ上のビットをも反転させる第１の反転モード及び線分
    自身を含まないで行う第２の反転モードを含み、前記所
    定回りで選択された前記塗り潰し対象の多角形の外形を
    構成する線分のうち、そのベクトルの垂直方向変化が第
    １の垂直方向となる線分は前記第１の反転モードで前記
    ビット反転処理を行い、そのベクトルの垂直方向変化が
    第２の垂直方向となる線分は前記第２の反転モードで前
    記ビット反転処理を行い、前記第１及び第２の垂直方向
    は、前記所定の回り及び所定の水平方向の内容に基づ
    き、前記塗り潰し対象の多角形の外形を構成する線分の
    うち、そのベクトルが前記１の垂直方向の線分は前記第
    １の反転モードで前記ビット反転処理を行うと欠落なく
    線分描画がされ、そのベクトルが前記２の垂直方向の線
    分は前記第２の反転モードで前記ビット反転処理を行う
    と欠落なく線分描画されるように決定される、及び (c)ステップ(b)の後、前記作業メモリ上の情報を前記表
    示メモリに転送するステップ、を実行させるためのプロ
    グラムを記録したコンピュータ読み取り可能な記録媒
    体。
JP9136693A 1997-05-26 1997-05-27 多角形塗り潰し方法及び記録媒体 Pending JPH10326352A (ja)

Priority Applications (5)

Application Number Priority Date Filing Date Title
JP9136693A JPH10326352A (ja) 1997-05-27 1997-05-27 多角形塗り潰し方法及び記録媒体
US08/946,195 US6301259B1 (en) 1997-05-26 1997-10-07 Switch and switching method
US08/947,017 US6215501B1 (en) 1997-05-27 1997-10-08 Method and filling a polygon and recording medium
DE69721736T DE69721736T2 (de) 1997-05-27 1997-10-14 Verfahren zum Füllen einer Polygone und Bildverarbeitungssystem
EP97117786A EP0881598B1 (en) 1997-05-27 1997-10-14 Method for filling a polygon and image processing system

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP9136693A JPH10326352A (ja) 1997-05-27 1997-05-27 多角形塗り潰し方法及び記録媒体

Publications (1)

Publication Number Publication Date
JPH10326352A true JPH10326352A (ja) 1998-12-08

Family

ID=15181272

Family Applications (1)

Application Number Title Priority Date Filing Date
JP9136693A Pending JPH10326352A (ja) 1997-05-26 1997-05-27 多角形塗り潰し方法及び記録媒体

Country Status (4)

Country Link
US (1) US6215501B1 (ja)
EP (1) EP0881598B1 (ja)
JP (1) JPH10326352A (ja)
DE (1) DE69721736T2 (ja)

Families Citing this family (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
AUPP579098A0 (en) * 1998-09-09 1998-10-01 Canon Kabushiki Kaisha A method and apparatus for parametric variation of text
US6897869B1 (en) * 1999-10-25 2005-05-24 International Business Machines Corporation System and method for filling a polygon
KR100807601B1 (ko) * 2003-06-30 2008-03-03 엔이씨 일렉트로닉스 가부시키가이샤 평판 디스플레이용 메모리 제어기 및 데이터 드라이버
JP4621617B2 (ja) * 2006-03-28 2011-01-26 株式会社東芝 図形描画装置、図形描画方法、及びプログラム
JP4621618B2 (ja) * 2006-03-28 2011-01-26 株式会社東芝 図形描画装置、図形描画方法、およびプログラム
ATE456111T1 (de) * 2007-09-05 2010-02-15 Vidiom Sa Verfahren zum zeichnen von geometrischen formen
CN102184515B (zh) * 2011-04-13 2013-02-06 合肥芯硕半导体有限公司 一种在fpga中实现梯形图填充的方法
US9607414B2 (en) * 2015-01-27 2017-03-28 Splunk Inc. Three-dimensional point-in-polygon operation to facilitate displaying three-dimensional structures
US9836874B2 (en) 2015-01-27 2017-12-05 Splunk Inc. Efficient polygon-clipping technique to reduce data transfer requirements for a viewport
US9767122B2 (en) 2015-01-27 2017-09-19 Splunk Inc. Efficient point-in-polygon indexing technique to facilitate displaying geographic data
US9916326B2 (en) 2015-01-27 2018-03-13 Splunk, Inc. Efficient point-in-polygon indexing technique for facilitating geofencing operations
US10026204B2 (en) 2015-01-27 2018-07-17 Splunk Inc. Efficient point-in-polygon indexing technique for processing queries over geographic data sets

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4962468A (en) * 1987-12-09 1990-10-09 International Business Machines Corporation System and method for utilizing fast polygon fill routines in a graphics display system
US5553219A (en) 1991-05-10 1996-09-03 Fuji Xerox Co., Ltd. Font outline and bit map generator synthesizing filling data with selected outline data or duplicate outline data
US5461703A (en) 1992-10-13 1995-10-24 Hewlett-Packard Company Pixel image edge enhancement method and system
JP2637920B2 (ja) * 1994-08-11 1997-08-06 インターナショナル・ビジネス・マシーンズ・コーポレイション コンピュータ・グラフィック・システム及びフレーム・バッファ使用方法
US5668940A (en) * 1994-08-19 1997-09-16 Martin Marietta Corporation Method and apparatus for anti-aliasing polygon edges in a computer imaging system
US5847712A (en) * 1995-01-03 1998-12-08 University Of Washington Method and system for generating graphic illustrations according to a stroke texture and a tone
US5764243A (en) * 1995-03-24 1998-06-09 3Dlabs Inc. Ltd. Rendering architecture with selectable processing of multi-pixel spans
US5818456A (en) * 1996-04-30 1998-10-06 Evans & Sutherland Computer Corporation Computer graphics system with adaptive pixel multisampler
US5781197A (en) * 1996-07-26 1998-07-14 Hewlett-Packard Company Method for maintaining contiguous texture memory for cache coherency
US5828379A (en) * 1997-02-12 1998-10-27 Eastman Kodak Company Computer program product for generating a soft edge on a digital mask

Also Published As

Publication number Publication date
EP0881598A3 (en) 1999-10-06
EP0881598B1 (en) 2003-05-07
EP0881598A2 (en) 1998-12-02
US6215501B1 (en) 2001-04-10
DE69721736T2 (de) 2004-04-01
DE69721736D1 (de) 2003-06-12

Similar Documents

Publication Publication Date Title
US6292192B1 (en) System and method for the direct rendering of curve bounded objects
JPH0535913B2 (ja)
US6215501B1 (en) Method and filling a polygon and recording medium
JP3031825B2 (ja) 多角形を塗りつぶすための方法、システム及び装置
JP3089792B2 (ja) 画像データの隠面判別方式
JP3547250B2 (ja) 描画方法
JPH11126261A (ja) テクスチャマッピング方法及びその装置
JP3872056B2 (ja) 描画方法
JP2001134777A (ja) ３次元グラフィックスシステム、演算処理装置及び記録媒体
JP4214644B2 (ja) ２次元パターン生成装置
US5936635A (en) System and method of rendering polygons into a pixel grid
JP4320604B2 (ja) 画像処理方法および画像処理装置
US7667714B2 (en) Patterned polygon rendering apparatus
JP4214643B2 (ja) ２次元パターン生成方法及び装置
JP2011028641A (ja) 画像処理装置及び画像処理方法
JP3089906B2 (ja) 描画装置
JPH10187124A (ja) 描画装置および描画方法
JPH0350686A (ja) 図形処理方式
JPH0259871A (ja) 画像処理装置および画像処理方法
JPS6326773A (ja) 図形情報の表示処理方法
JP3799164B2 (ja) 画像処理方法および画像処理装置
JP2634906B2 (ja) 画像処理方法
JP4666480B2 (ja) 線描画装置
JP2000014932A (ja) ゲーム画像表示方法及び、これを用いたゲーム装置
JPH0636049A (ja) 図形のハイライト表示方法及びグラフィックス装置

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20040511

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20061226

A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20070424