JPH01304588A - クリッピング処理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 「産業上の利用分野」 本発明は、任意形状の閉じたクリップ領域境界によって
図形・画像等の被クリップ対象の一部を取り出すクリッ
ピング処理方式に関し、各種の図形・画像処理システム
に適用できるものである。

［従来の技術］ 従来、この種のクリッピング処理方式として、文献「コ
ンピュータ・グラフィックス」　（Ｊ、Ｄ。

ＦＯＬＩ兄Ｙ（フォリー）／Ａ、ＶＡＮ　　ＤＡＭ（ヴ
アンダム）共著、今宮淳美訳、１９８４年、１１本コン
ピュータ協会発行）に開示されているものがある。

これには、サザランｌへ等の方式やウエイラー等の方式
によるクリッピング処理方式が記載されている。これら
は、被クリップ対象としての図形要素の境界と、クリッ
プ領域の境界との交点を計算し、得られた交点、図形要
素の境界及びクリップ領域の境界から、クリップ領域内
に存在する図形要素の部分境界を再構成するものであり
、サザランＩへの方式及びウェイシーの方式は再構成す
る処理が異なっている。

クリップされた図形要素部分は、画素に展開されて描画
用メモリに格納され、その後、プリンタ装置や陰極線管
（ＣＲＴ）表示装置等のラスタ状出力装置に与えられて
出力される。

なお、かかる処理において、必要に応じて座標系の変換
がなされる。

［発明が解決しようどする課題］ しかしながら、上述の従来方式によれば、クリップ領域
の境界と、図形要素の境界との交点を計算することを要
するので、少なくとも一方の境界が、例えばコンピュー
タグラフィックスの分野で多く用いられているベジェ曲
線やスプライン曲線等の複雑な曲線で規定されている場
合、高次代数方程式を解いて交点を求めることになり、
クリップ処理に多大な時間を要し、また、クリッピング
処理部を専用ハードウェア化する場合の妨げとなってい
た。

そこで、境界がベジ飄曲線やスプライン曲線等の場合に
、これら曲線を線分列で近似させて交点をｔｌ算するこ
とも考えられるが、一方の境界の全ての線分と、他方の
境界の全ての線分（又は境界自体）との全ての組み合わ
せについて交点の有無及び交点座標を演算しなければな
らず、近似線分の長さを短くした場合には、演算すべき
線分の組み合わせが非常に多くなり、このように近似さ
せてもクリッピング処理時間の短縮を期待できない。

近似線分の長さをある程度長くすると演算すべき線分の
組み合わせが少なくなり、多少処理時間を短縮すること
ができるが、長さを長くした分近似性が劣り、出力され
た図形要素の両肩が劣化してしまう。

また、上述の方式によれば、クリップ領域として、境界
の凹凸がはげしいものや、内部にクリップしない穴領域
を有するものを適用した場合には、交点が多くなり、そ
れら交点をはさんだクリップ領域の内外判定処理等を含
めた再構成処理が複雑になり、処理時間の長時間化等処
理性能が劣化する。

さらに、上述の従来方式によれば、クリッピング処理を
他の処理と無関係に行なっており、クリップされた部分
図形要素をラスタ状に展開したり、又は及び画素に展開
して描画用メモリに格納させる処理にも時間がかかる等
の問題があった。

本発明は、以上の点を考慮してなされたもので、簡易な
演算によって短時間のうちに被クリップ対象をクリップ
することができると共に、かかるクリップ処理が被クリ
ップ対象をラスタ状に変換する処理と親和性が高く、出
力処理を含めた処理性能に優れたクリッピング処理方式
を提供しようとするものである。

［課題を解決するための手段］ かかる課題を解決するため、本発明においては、境界が
任意形状のクリップ領域によって、２次元的な被クリッ
プ対象のクリップ領域内に存在する部分情報を取り出し
、その取り出した被クリップ対象の部分情報をラスタ状
出力装置に引渡して出力させるクリッピング処理方式に
おいて、クリップ領域を、ラスタ状出力装置の走査線方
向に沿ったセグメントに分解し、分解されたセグメント
の情報でクリップ領域を規定して被クリップ対象の部分
情報を取り出すようにした。

［作用コ クリップ領域を走査線方向に沿ったセグメントに分解し
てセグメント情報に変換する。この場合、走査線方向と
クリップ領域境界との交点とを求めれば良く、被クリッ
プ対象境界とクリップ領域境界との交点を求めるような
複雑な演算処理を行なう必要はなく、簡易な演算によっ
て七グメンｌ−に分解できる。

また、走査線方向に沿ったセグメントでクリップしたの
で、クリップ後の被クリップ対象を再構成することなく
、そのセグメント毎に被クリップ対象のクリッピングを
実行でき、これによって被クリップ対象の全体のクリッ
ピングを実行する。

［実施例］ 以下、本発明を図形要素をクリップする場合に適用した
一実施例を図面を参照しながら詳述する。

ここで、第１図は実施例のクリッピング処理方式の全体
処理手順を示すフローチャート、第２図はクリップ領域
のセグメント化の説明に供する路線図、第３図は実施例
の機能ブロック図、第４図はセグメントメモリ６の＋１
４造を示ず路線図、第５図はセグメントデータ管理メモ
リ７の構造を示す路線図、第６図はセグメントデータ管
理メモリ７に対するデータの詳細な作成処理手順を示す
フローチャート、第７図はセフメン１〜メモリ６に対す
るデータの詳細な作成処理手順を示すフローチャー　１
−１第８図はセグメントデータの読出し及びクリップ処
理の詳細手順を示すフローチャー１・、第９図はセグメ
ント単位のクリップ処理の説明に供する路線図、第１０
図はＤＤＡ法を用いた場合のセグメントデータの作成方
法の説明に供する路線図、第１１図はイーブンオツド法
の説明図、第１２図はノンゼロワインディング法の説明
図、第１３図はイーブンオツド法とノンゼロワインディ
ング法とによって作成されるセグメント数が異なる場合
を示ず路線図、第１４図は複数のクリップ領域を有する
場合のセグメントデータ管理メモリの構造を示ず路線図
、第１５図はセグメントメモリの領域に対する異なる格
納例を示す図である。

夾施凹座詩虱 先ず、実施例の特徴について第２図を用いて説明する。

この実施例は、第２図に示すようなりリップ領域ｃｐを
、ラスタ状出力装置（図示せず）の走査線上に沿ったセ
グメント１、Ｓ２、・・・に分解し、各セグメントＳ１
、Ｓ２、・・・の始点及び終点く又は始点及びセグメン
ト長）の情報にクリップ領域の情報を変換し、セグメン
トに変換後の情報を用いて図形要素をクリップすること
を特徴とするものである。

丈旌Ａｍ皿滅 次に、機能的にみた実施例の構成を第３図について説明
する。

第３図において、クリップ処理部１には、図形要素及び
クリップ領域が与えられ、クリップ処理部１は、図形要
素をクリップ領域によってクリップし、画素に展開した
後５．クリツプされた図形要素を描画用メモリ２に与え
て格納させるものである。描画用メモリ２に格納された
図形要素は、順次ラスタ状に読み出されてプリンタ装置
３に与えられ印字され、又はＣＲＴ表示装置４に与えら
れて表示される。

クリップ処理部１は、詳細には、走査変換部５、セグメ
ントメモリ６、セグメントデータ管理メモリ７、クリッ
プ処理本体部８、セグメント画素変換部９、演算処理（
ＡＬＵ）部１ｏ及び制御部１１がバス１２を介して接続
されて構成されている。

走査変換部５は、図形要素及びクリップ領域を走査線上
のセグメン１〜に分割してセグメントデータに変換する
ものである。

セグメントメモリ６は、第４図に示すデータ構造を有し
、走査変換部５によって得られたクリップ領域について
のセグメントータータを格納するものである。

セグメントデータ管理メモリ７は、第５図に示ずデータ
ｊＭ　Ｍを有し、セスメンｌ−メモリ６をアクセスする
際に必要となる各種データを格納するものである。

クリップ処理本体部８は、走査変換部５から与えられる
図形要素のセグメントデータと、セフメン１〜メモリ６
に格納されているクリップ領域についてのセグメントデ
ータとの各走査線について共通のセグメント部分を取り
出すもの、すなわち、クリップされた図形要素について
のセグメントデータを得るものである。

セグメント画素変換部９は、クリップされた図形要素の
セグメントデータを画素に展開して描画用メモリ２に与
えるものである。

制御部１１は、第１図、第６図〜第８図に示す処理プロ
グラムを格納するプログラムメモリを内蔵し、プログラ
ムメモリに内蔵されているプログラムに従い、上述した
各機能部の処理を制御するものである。なお、各機能部
がプログラムに従った処理を実行する際に演算が必要と
なったときには演算処理部１０がその演算を実行するよ
うになされている。

セグメントメモリ６の　遣 次に、セグメントメモリ６のデータ構造を第４図につい
て説明する。

第４図において、１個のアドレスに対するメモリエリア
は、そのメモリエリアにセグメントデータ（ワード）が
格納されているか否かを表わすフラグと、Ｘ方向を走査
線方向とし、Ｙ方向を走査線のインクリメント方向とし
た第２図に示すようなＸ−Ｙ座標系を考えた場合のセグ
メン１へ始点のＸ座標値及びセグメント終点のＸ座標値
でなるワードとを格納する。このような１個のセグメン
トに対するデータを、クリップ領域を分割した全てのセ
グメントについて格納するようになされている。

セグメントメモリ６は、進入頂点及び退出頂点の組数に
等しい数の領域Ｒｉ　（ｉは組数ｎ）に区分されており
、各領域Ｒｉには進入頂点のＹ座標値と退出頂点のＹ座
標値の差分より１だけ多い数ｈｉだけのセグメントデー
タが格納される。

ここで、進入頂点とは、走査線を順次インクリメンｌ−
していったとき処理中の走査線に進入してきた頂点であ
り、第２図の場合には頂点Ｐ１及び１）４が該当し、退
出頂点とは、走査線を順次インクリメントしていったと
き処理中の走査線から退出していった頂点であり、第２
図の場合には頂点１）　３及びＰ５が該当する。また、
クリップ領域の境界を、進入頂点から所定方向に稜線を
トレースして退出頂点に至るとき、これを進入頂点及び
退出頂点の組という。

第２図の場合には、反時計方向にトレースすると、進入
頂点Ｐ１及び退出頂点Ｐ３、並びに、進入頂点Ｐ４及び
退出頂点Ｐ５がそれぞれ組となり、また、時計方向にト
レースすると、進入頂点１〕１及び退出頂点Ｐ５、並び
に、進入頂点Ｐ４及び退出頂点Ｐ３がそれぞれ組となる
。

なお、後述する理論的根拠で説明するように、クリップ
領域をセグメントに変換した場合、各組について進入頂
点及び退出頂点のＹ座標値の差分）＋１ずつのセグメン
トがあり、これらの総和か総セグメント数であるので、
かかるデータ構造によって全てのセグメントを格納する
ことができる。

なお、同一走査線上に複数のセグメントが存在する場合
、それぞれ、各領域の走査線Ｙ座標値に対応するワード
位置に格納される。

タダメントデータ咬理メモ＋７の′？遣次に、セグメン
トデータ管理メモリ７のデータ構造について第５図を参
照しながら詳述する。

このセグメントデータ管理メモリ７は、セグメントメモ
リ６の各領域Ｒｉを管理するデータを格納するものであ
り、与えられた走査線Ｙ座標値に応じて、その走査線上
の全てのセグメントデータをセグメントメモリ６からア
クセスする際に、このメモリ７に格納されたデータが用
いられるものである。

格納されるデータとしては、ルートポインタｒｐ、進入
頂点ポインタｖｐｉ、進入頂点Ｙ座標値ｙｉ、領域のワ
ード数ｈｉ、セグメントメモリポインタｓｍｐｉがあり
、ルートポインタｒｐ以外のデータは、セグメントータ
モリ６の各領域Ｒ１海に１−ブロックのデータとして格
納される。　進入頂点ポインタｖｐｉは、進入頂点をＹ
座標値の小さい順に結ぶポインタであり、走査線Ｙ座標
値の増加に対して次に進入する進入頂点を知るに用いる
ものである。

進入頂点Ｙ座標値ｙｉは、進入頂点から順にＹ増加方向
に発生されているセグメントの座標値を計算するのに用
いるものである。

ワード数ｈｉは、セグメントメモリ６の領域Ｒ１の大き
さを知るのに用いるものである。

セグメントメモリポインタｓｍｐ　ｉは、セグメントメ
モリ６の各領域Ｒｉの最初のアドレスを知るのに用いる
ものである。

ルーＩ・ポインタｌ−ｐは、進入頂点ポインタｖｐｉの
始点を示すポインタである。

クリッピング　１里の全゛自＜ｔＪ几丁里；用■次に、
この実施例によるクリッピング処理の全体的な処理手順
を第１図を参照しながら詳述する。

先ず、入力されたクリップ領域からセグメントデータ管
理メモリ７に対するデータを作成してセグメン１へデー
タ管理メモリ７に格納する（ステップ１００）。なお、
かかる処理の詳細を第６図のフローチャートに示す。

次に、入力されたクリップ領域からクリップ領域に対す
るセグメントデータを作成してセグメン１へメモリ６に
格納する（ステップ１−０１）。なお、かかる処理の詳
細を第７図のフローチャートに示す。

このようにして、クリップ領域についてのセグメントデ
ータ及びそのデータをアクセスするために必要とする管
理データを作成して格納すると、走査線Ｙ座標値ｙｓを
最も値が小さい進入頂点のＹ座標値に初期化する（ステ
ップ１０２）。

その後、走査線Ｙ座標値ｙｓが指示する走査線上の入力
された図形要素のセグメントを求める（ステップ１０３
）。この段階でセフメン１〜メモリ６に格納されている
その走査線上のクリップ領域についてのセグメントデー
タをセグメントデータ管理メモリ７のデータを用いなが
ら読出し、第９図に示すように図形要素のセグメンｌ−
８Ｇ（第９図（Ａ）実線）とクリップ領域のセグメント
ＳＣ（第９図（Ａ）破線）とのＸ座標値の共通部分（第
９図（Ｂ））を取り出し、クリップした図形要素ＳＧＣ
をセグメント画素変換部９に出力するくステップ１０４
）。

なお、セグメントメモリ６からクリップ領域についての
セグメントデータを読出してクリップする処理の詳細フ
ローチャートを第８図に示す。

このようにして１つの走査線について図形要素セグメン
トのクリップ処理を終了すると、クリップ領域と交わる
全ての走査線についてセグメント単位のクリップ処理が
終了したか否かを判断し、終了していない場合、走査線
Ｙ座標値ｙｓを次の座標値に更新して上述のステップ１
０３に戻り、終了している場合には一連のクリップ処理
を終了させる（ステップ１０５．１０６）。

このようにしてクリップされた図形要素のセグメントデ
ータは、セグメント画素変換部９によって画素に展開さ
れて描画用メモリ２に格納され、このメモリ２から順次
ラスタ状に読み出されてプリンク装置３又はＣＲＴ表示
装置４に与えられて出力される。

次に、第１図に示す全体処理のステップ１００において
実行されるセグメントデータ管理メモリ７に対するデー
タの作成処理について第６図を参照しながら詳述する。

先ず、入力されたクリップ領域の境界データを後処理に
適合するような形に構造化して取込む（ステップ１２０
）。例えば、クリップ領域が線分でなり、頂点列で与え
られる場合、その頂点列の並びを後処理に適合する時計
方向回り又は反時計方向回りに並び換えたりしながら取
込む。

次いで、セグメントメモリ６の領域Ｒｉに対応した領域
パラメータｉを１に初期化すると共に、セグメントメモ
リポインタパラメータｓｍｐを０に初期化する（ステッ
プ１２１）。

次に、クリップ領域境界を、例えば反時計方向にたどり
、退出頂点でない頂点を処理対象の始点の頂点としてセ
ットする（ステップ１２２）。

このような初期化処理が終了すると、処理対象の頂点が
進入頂点か否かを判断する（ステップ１２３）。否定結
果を得ると、その頂点から境界を反時計方向にたどった
次の頂点を取り出し、取り出した頂点が始点の頂点でな
いことを確認してステップ１２３に戻る（ステップ１２
４．１２５）。

ステップ１２３〜１２５を実行することで、処理対象の
頂点とｉ〜で進入頂点が見つけ出され、ステップ１２３
において肯定結果が得られる。なお、ステップ１２５に
おいて肯定結果を得ると、後述するステップ１３５に進
む。

このようにして進入頂点が見つかると、その進入頂点の
Ｙ座標値を、ｉ番目の領域Ｒｉの進入頂点Ｙ座標値ｙｉ
としてセグメントデータ管理メモリ７に格納すると共に
、後述するワード数ｈｉの算出に供する始点Ｙ値パラメ
ータＶＩとして一旦格納し、また、そのときのセグメン
トメモリポインタパラメータＳ　ＩＴＩ　ｐを、領域Ｒ
ｉのセグメンＩ−）メモリポインタｓｍｐ　ｉとしてセ
グメンｌ〜データ管理メモリ７に格納する（ステップ１
２６）。

次に、処理対象の頂点が退出頂点か否かを判断する（ス
テップ１２７）。否定結果を得ると、この頂点から反時
計方向に境界をたどった次の１頁点を取り出し、ステッ
プ１２７に戻る（ステップ］２８）。このような処理を
繰り返すことにより、上述のステップ１２３で取り出さ
れた進入頂点と組をなす退出頂点が見つけ出され、ステ
ップ１２７において聞定結果が得られる。

このときには、先ず、その退出頂点のＹ座標値を、後述
するワード数ｈｉの算出に供する終点Ｙ値パラメータＶ
Ｏとして格納する（ステップ１２９）。その後、上述し
た始点Ｙ値パラメータＶＩ及びこの終点Ｙ値パラメータ
Ｖ○から次式％式％（１） に従い、ワード数ｈｉを算出してセグメントデータ管理
メモリ７に格納し、また、セグメントメモリポインタパ
ラメータｓｍｐにこのワード数ｈ　ｉを加算して、次の
進入頂点及び退出頂点の組用にセグメントメモリポイン
タパラメータｓｍｐの値を更新する（ステップ１３０）
。

このようにして、領域Ｒｉについて、進入頂点のＹ座標
値ｙｉ、ワード数ｈｉ、セグメントメモリポインタｓｍ
ｐ　ｉがセグメントデータ管理メモリ７に格納されると
、クリップ領域を反時計方向にたどった次の頂点を取出
し、処理対象の頂点が上述したステップ１２２において
セラ１−された始点を越えて一巡した頂点になっている
が否かを判断する（ステップ１３１．１３２）。

その結果、否定結果を得ると、領域パラメータｉをイン
クリメントしてステップ１２３に戻り、次の領域Ｒｉに
ついての進入頂点及び退出頂点を見つけ出してその領域
Ｒｉについての管理データをセグメントデータ管理メモ
リ７に格納する処理に戻る（ステップ１３３）。

これに対して、トレースがクリップ領域境界を一巡する
と、各領域Ｒｉについての進入頂点のＹ座標値を小さい
順に結ぶ進入頂点ポインタｖｐｌ〜ｖｐｎを形成し、同
時に最初の進入頂点ポインタｖｐｌのアドレスをルーＩ
・ポインタｒｐに格納してセグメントデータ管理メモリ
７に対するデータの作成を終了する（ステップ１３４）
。

セグメン［・メモリ６に差　−るデータの均゛次に、ク
リップ領域をセフメンｌ−データに分解して作成し、そ
のセグメントデータをセグメン（・メモリ６に格納する
処理（第１図ステップ１０１参照）を第７図に基づいて
詳述する。

先ず、走査線Ｙ座標値ｙｓを、セグメントデータ管理メ
モリ７内の進入頂点ポインタｖｐｌ及びそのＹ座標値ｙ
１に基づいて、クリップ領域の最小のＹ座標値にセット
する（ステップ１４０）。

次いで、領域パラメータｉを初期値１にする（ステップ
１４１）。

次に、その走査線上の１一つのセグメントのデータ、す
なわち始点Ｘ座標値及び終点Ｘ座標値を生成する（ステ
ップ１４２）。

ここで、そのセグメントが点（頂点〉であれば、始点及
び終点Ｘ座標値として同゛−のものを生成し、また、直
線線分の稜線によって定まる有限長のセグメントであれ
ば、例えばその１つ上の走査線のセグメントデータ（ｘ
ｓ、ｘｅ）から第１０図に示すように増分△ｘｓ、△ｘ
ｅを加減算することでセフメン１ヘデータを作成する。

すなわち、デジタル微分解析機構（ＤＤＡ：　Ｄｉｇｉ
ｔａｌ　Ｄｉｆｆｅｒｅｎｔｉａｌ　Ａｎａｌｙｚｃｒ
）法によって生成する。稜線がベジェ曲線やスプライン
曲線に従う場合には、ＤＤＡ法の一種である前進増分（
Ｆｏｗｅｒｄ　Ｄｉｆｆｅｒｅｎｃｅ）法によって増分
を適宜変化させていくことで生成する。

なお、この際、必要となるクリップ領域についての内外
判定法としては、後述するイーブンオツド（［ｖｅｎ−
ｏｄｄ　）法又はノンゼロワインデインク（Ｎ　Ｏ＋１
−　ｚｅｒｏ　ｗｉｎｄｉｎｇ）法のいずれかを適用す
る。

その後、このときの領域パラメータｉによって規定され
る組の進入頂点のＹ座標値ｙｉより走査線Ｙ座標値ｙｓ
が小さくないこと、及びその領域Ｒｊについての退出頂
点のＹ座標値（ｙｉ＋ｈｉ）より走査線Ｙ座標値ｙｓが
大きくないこと、すなわち、そのセグメントメモリ６の
領域Ｒｉにセグメントデータを格納できるエリアを確保
できるか否かを判断しくステップ１４３）、否定結果を
得ると、領域パラメータｉをインクリメントシて再度ス
テップ１４３に戻り、格納できるエリアを確保できる領
域ｆｌｊを見つけ出す（ステップ１４４）このようにし
て確保できる領域Ｒｉを見つけ出すと、そのときの走査
線Ｙ座標値ｙｓ、その領域Ｒｉの進入頂点Ｙ座標値ｙｉ
、及びセグメン１〜メモリポインタｓｍｐ　ｉから次式 ％式％（２） に従い、定まるアドレスａｄを求め、そのアドレスａｄ
のメモリエリアにセグメン１へデータを格納し、同時に
そのエリアのフラグをセラ（へする（ステップ１４５）
。

次いで、領域パラメータｉをインクリメントした後、対
象となっている走査線上の全てのセグメンｌへに対して
上述の生成処理を実行したか否かを判断し、否定結果を
得た場合には、上述のステップ１４２に戻り、その走査
線上の次のセグメントについて上述と同様な処理を繰り
返すことになる）（ステップ１４６．１４７）。

このようにして対象となっている走査線上の全てのセグ
メントについてデータの生成及び格納処理が終了したと
判断すると、クリップ領域を横切る全ての走査線につい
て上述した処理を終了したか否かを判断し、終了してい
ない場合には、走査線Ｙ座標値ｙｓを次の値に更新して
上述のステップ１４１に戻り、次の走査線に対するセグ
メントの生成、格納処理に進む（ステップ１４８．１４
つ）。

このようにして全てのセグメントについて、そのセグメ
ントデータをセグメントメモリ６に格納すると、一連の
セグメントデータの生成、格納処理を終了する。

次に、クリップ領域を走査線方向に分解して得た全ての
セグメントデータを゛、上述の処理によってセグメント
メモリ６に格納できる理論的根拠を説明する。

先ず、進入頂点と退出頂点の数について考えて見る。ク
リップ領域境界を例えば反時計方向にたどっていくとす
る。ある点に進入頂点がある場合その後境界をたどって
いくと、境界が閉じた曲線になっていることにより、進
入頂点から下方に延びた稜線はやがて頂点を介して上方
に折曲されることになる。また、ある頂点を介して−Ｆ
方に折曲された場合であってその後の頂点を介して再度
下方に折曲された場合、曲線を閉じるためには、再度上
方に境界を折曲しなければならない。従って、進入頂点
の次に進入頂点がくることはなく、また、退出頂点の次
に退出頂点がくることはなく、進入頂点と退出頂点とは
境界を所定方向にたどった場合交互に現れる。

その結果、クリップ領域境界の進入頂点数及び退出頂点
数は等しいと言うことかでき、かつ交互に現れるので、
上述したような組として取り扱うことができる。

ところで、クリップ領域の内外判定の方式として、第１
１図に示すようなりリップ領域の絶対的に外部にある基
準点から半直線を引いたときクリップ領域の境界との交
点を基準点から数えてその値が奇数になった境界位置と
次の値の偶数になった境界位置との間がクリップ領域の
内部と判定するイーブンオツド法がある。

半直線の方向を走査線方向としてこのイーブンオツド法
に従い、セグメントを発生する場合、ある走査線上に対
する既存稜線が２ｎ個あった場合交点数が２ｎ個である
ので、セグメントはｎ個ある。この走査線位置より１個
の進入頂点を挾んで下方にある走査線を考えると、交差
する稜線は２木増えるのでその走査線位置のセグメント
数は１個増える。同様に考えると、走査線をインクリメ
ントして退出頂点を越えると、退出頂点より下側に位置
する走査線上のセグメント数は退出頂点より上方の走査
線上のセグメント数より１だけ減少する。

上述した進入頂点及び退出頂点数が等しいこと、並びに
進入頂点及び退出頂点前後の走査線上でのセグメント数
の変化を考慮すると、イーブンオツド法に従って内外判
定してセグメンｌ−を生成する場合、１組の進入頂点及
び退出頂点によってその進入頂点及び退出頂点のＹ座標
値の差分＋１藺のセグメントができ、総数は各組による
セグメント化数の総和になることが分る。

従って、上述のように各組に応じてセグメントメモリ６
を領域化するようなセグメントデータ管理メモリ７のデ
ータを作成し、そのデータによって領域化されたセグメ
ントメモリ６に進入頂点側からセグメントデータを格納
することによって全てのセグメントデータを格納できる
ことが判る。

ところで、クリップ領域の内外判定方式としては、イー
ブンオツド法の外にノンゼロワインディング法がある。

これは、第１２図に示すようにクリップ領域の絶対的な
外部の基準点から延びる半直線を考え、その基準点にお
ける判定パラメータを０とし、半直線とクリップ領域の
境界とが外債が負の方向に交わるとき判定パラメータを
例えば−１し、半直線とクリップ領域の境界との外債が
正の方向に交わるとき判定パラメータを例えば＋１し、
交点以外の半１ヴ線上では判定パラメータの値を変えな
いようにし、半直線上の各点における判定パラメータを
求め、その判定パラメータが０でない部分を内部と判定
し、０の部分を外部と判定するようにしたものである。

このノンゼロワインディング法によっても、以下のよう
な特殊な場合を除き、イーブンオツド方式と同様な判定
結果を得ることができ、上述のデータｔｊｌ　＝によっ
て全てのセグメントデータ管理メモリ７のデータによっ
て規定される全てのメモリエリアに対してセグメントデ
ータを格納することができる。

しかし、第１３図に示すような稜線が頂点以外で交差す
るようなりリップ領域内場合、例えば走査線Ｉ−Ｘに対
するセグメンｌへとしてノンゼロワインディング法の場
合には、点ｐ１〜ｐ４を一つのセグメントとして捕らえ
るが、イーブンオツド法の場合、このような例外的な場
合の処理の仕方によって異なるが点ｐ１〜ｐ３のセグメ
ン１とｐ２〜ｐ４のセグメントとの２個のセグメントと
してとらえる。従って、イーブンオツド法による場合、
ノンゼロワインディング法よりセグメント数が多くなる
ことはあるが、少なくなることはない。

上述のように、イーブンオツド法の場合、セグメントメ
モリ６に対して管理メモリ７のデータによって規定され
る全てのエリアにセグメントデータか格納されるが、ノ
ンゼロワイディング法の場合には、このような例外的な
りリップ境界に対してはセフメン１ヘメモリの幾つかの
エリアは空きエリアとなるが、上述の管理メモリ７のデ
ータ構造によって生成された全てのセグメントデータを
格納することができることに変りはない。

次に、セグメントメモリ６がらクリップ領域のセグメン
トデータ夕を読出して、このセグメントデータによって
図形要素のセグメントをクリップする処理（第１図ステ
ップ１０４参照）について、第８図を参照しながら詳述
する。

なお、かかる処理は、第１図について説明したように、
ある走査線の図形要素をセグメント化した後（ステップ
１０３）になされるものであり、第８図は一つの走査線
についての処理を示すものである。

先ず、セグメントデータ管理メモリ７がらルートポイン
タｒｐを取り出し、領域パラメータｉをそのルートポイ
ンタｒｐの値にする（ステップ１６０）。次いで、その
領域パラメータｉに一致する進入頂点ポインタｖｐｉを
有するセグメントデータ管理メモリ７のブロックから進
入頂点のＹ座標値ｙｉを取り出し、走査線Ｙ座標値ｙｓ
が進入頂点のＹ座標値ｙｉ以上であるが否かを判断する
（ステップ１６１）。否定結果を得ると、後述するステ
ップ１６７に進み、’＋５Ｆ定結果を得ると、セグメン
トデータ管理メモリ７に格納されているワード数ｈｉを
も用いてその領域Ｒｉに関する退出頂点のＹ座標値ｙ　
ｉ　十ｈ　ｉより走査線Ｙ座標値ｙＳが小さくなってい
るか否かを判断する（ステップ１６２）。この場合にも
、否定結果を得ると、後述するステップ１６７に進む。

ｆｆｅって、ステップ１６１及び１６２を実行すること
により、セグメントメモリ６の領域Ｒｉに、その走査線
Ｙ座標値ｙｓに等しいＹ座標値を有するセフメン１〜デ
ータのエリアがあるか否かを判断していることになり、
ステップ１６２において行定結果を得ることは走査線Ｙ
座標値ｙｓに等しいＹ座標値を有するセグメントデータ
のエリアがあることを表わす。

このようにして走査線Ｙ座標値ｙｓに等しいＹ座標値を
有するセグメントデータのエリア領域Ｒ１があると判断
すると、セグメントデータ管理メモリ７に格納されてい
るセグメンｌ−メモリポインタｓｍｐ　ｉを用いて、次
式 ％式％（３） に従い、セグメン１へメモリ６に対するＸ売出しアドレ
スａｃｊを形成し、そのアドレスのエリアのフラグかセ
ットされていることを確認してそのアドレスのエリアか
らセグメントデータ夕を取り出す（ステップ１６３〜１
６５）。なお、フラグがセットされていない場合には、
直ちに後述するステップ１６７に進む。

このようにしてセグメントメモリ６から、処理対象とな
っている走査線上のクリップ領域についての一つのセグ
メントータータを得ると、第１図のステップ１０３にお
いて得られた図形要素のセグメントデータ夕が表わすセ
グメントと読出されたクリップ領域についてのセグメン
トデータが表わずセグメントとの共通部分を取り出しく
第９図参照）、図形要素のセグメントをクリップしてセ
グメント画素変換部９に出力する（ステップ１６６）。

かかる処理を終了すると、また、上述したステップ１６
１．１．６２及び１６４において否定結果を得ると、い
ままで処理に供していた領域パラメータｉが示すブロッ
クのルートポインタＶｐｉの値が最後のブロックを示す
ものになっているか否かを判断し、否定結果を得ると、
そのブロックのルートポインタｖｐｉに格納されている
値に領域パラメータｉの値を更新して上述のステップ１
６１に戻り、処理対象となっている走査線上の次のセグ
メントに対する処理に移行する（ステップ１６７．１６
８）。

他方、ステップ１６７において肯定結果を得ると、現在
処理対象となっている走査線についての処理を終了し、
第１図におけるステップ１０５に進む。

このような処理を繰り返すことにより、各走査線につい
ての全てのセグメン１へデータを読出し、図形要素に対
するクリッピング処理を実行することができる。

叉旌倒久力釆 上述の実施例によれば、クリップ領域をセグメントに分
解してクリッピングするようにしたので、図形要素をセ
グメントに分解する処理との親和性が良く、図形要素を
セグメントに分解する処理部をほぼそのまま利用でき、
わずかな機能要素の追加によってクリップ処理を実現す
ることができる。

また、セスメンｌ−データを用いてクリッピングするよ
うにしたので、従来方法とは異なり、領域境界がベジェ
曲線やスプライン曲線であっても高次代数方程式を解＜
氾・要がない。その結果、構成を簡易なものとすること
ができ、専用ハードウェア化するのに好適なものとなっ
ている。また、処理速度も高速化することが期待できる
。

なお、セグメントータータにする場合、走査線とクリッ
プ領域との交点を１４）る必要があるが、境界稜線が直
線の場合には、一つ上のセグメントの始点又は終点に対
して所定の増分を加減算することで次の走査線のセフメ
ン１〜データを得ることができ、ＤＤＡ法を適用するこ
とができ、稜線がベジェ曲線やスプライン曲線であって
もＤＤＡ法の一種である前進増分法を適用でき、高次代
数方程式を解く場合に比べて格段的に簡易な計算方法を
適用できる。

また、上述の実施例によれば、セグメントデータとして
クリップ領域を規定するようにしたので、内部に穴領域
があるクリップ領域や凹凸が激しいクリップ領域に対し
ても容易にクリッピング処理することができ、この点か
と、も従来に比して処理の簡易化及び高速化を実現でき
、専用ハードウェア化するのに好適であるということが
できる。

さらに、１ユ述の実施例ＧＦよれば、クリ・ツブ領域は
、セメメン１〜データとして情報圧縮されていることに
なり、クリップ領域をピッ１へマツプ情報として持つ場
合に比較してメモリとして小容量のもので済む。

肱ム実施側 （１）上述の実施例においては、クリップ領域が１個の
ものについて説明したが、クリップ領域が２個以上ある
場合にも適用することができる。この場合において、２
個以上のクリップ領域が重複部分を有していても良い。

このときには、第１４図に示すようにセグメントデータ
管理メモリ７は、それぞれのクリップ領域に対応した複
数個のルーｌ−ポインタｒｐｌ、ｒｐ２、・・・を持つ
ようにし、かつ各クリップ領域毎に管理データの格納エ
リアをまとめることで容易に対応することができる。

（２）同一走査線上のセグメントデータをセグメントメ
モリ６に格納する順序は、第１５図のように入れ換えて
も良い。同一走査線上のセグメントの取出し順序をＸ座
標値の小さい方から行なう場合と、大きい方から行なう
場合とでこのように格納するメモリエリアが異なるが、
上述した理論的根拠から明らかなようにこの場合におい
ても全てのセグメントデータを格納することができる。

（３）上述の実施例においては、走査変換部が１個のも
のを示したので、クリップ領域のセグメントデータ変換
を最初に行なってセグメントメモリ６に格納した後、図
形要素をセグメントに変換し、クリッピングするものを
示したが、走査変換部を複数個設けてクリップ領域のセ
グメント化と、図形要素のセグメンｌへ化とを並行して
実行し、セグメントメモリを省略又は簡易化しても良い
。

（４）」−述の実施例においては、セグメントデータを
セグメントの始点と終点で規定したが、セグメントの始
点とその長さ等地の規定の方法を用いても良い。

（５）上述の実施例では、図形要素をクリッピングする
ものを示したが、他の被クリップ対象をクリッピングす
るものて′あっても良い。ピッｌ−マツプ展開された文
字フォントをクリッピングするものであっても良い。こ
の場合、クリップ領域のセグメントにあるピッＩ〜情報
を取り出して出力することになる。また、画像矩形領域
をクリッピングする場合にも適用でき、情報の存在を示
す仮想的な直線区間でなる領域をクリッピングする場合
にも適用できる。

（６）なお、上述の実施例においては、入力されてくる
クリップ領域及び図形要素の座標系がラスタ状出力装置
（３，４）の座原糸に従ったものを示したが、クリッピ
ング処理をユーザ座標系で行ない、描画用メモリ２に格
納する前段に座標系の変換処理を行なうようなものであ
っても良い。

［発明の効果］ 以上のように、本発明によればクリップ領域をラスタ状
出力装置の走査線方向に沿ったセグメン１〜に分解し、
そのセグメントデータに基づいて被クリップ対象をクリ
ッピングするようにしたので、簡易な演算処理によって
クリッピングすることができ、しかも、ラスタ状出力装
置への出力に対する親和性が高い、処理性能の優れたク
リッピング処理方式を得ることができる。

【図面の簡単な説明】

第１−図は本発明によるクリッピング処理方式の一実施
例の全体処理手順を示すフローチャー１−５第２図はク
リップ領域のセグメント化の説明に供する路線図、第３
図は上記実施例の機能的構成を示すブロック図、第４図
はセグメントメモリ６の横道を示ず路線図、第５図はセ
グメンｌへデータ管理メモリ７の構造を示す路線図、第
６図はセグメントデータ管理メモリ７に対するデータの
詳細な作成処理手順を示すフローチャート、第７図はセ
グメントータモリ６に対するデータの詳細な作成処理手
順を示すフローチャート、第８図はセグメントデータの
読出し及びクリップ処理の詳細手順を示すフローチャー
ト、第９図はセグメント単位のクリップ処理の説明に供
する路線図、第１０図はＤＤＡ法を用いた場合のセグメ
ントデータの作成方法の説明に供する路線図、第１１−
図はイーブンオツド法の説明図、第１２図はノンゼロワ
インディンク”法の説明図、第１３図はイーブンオツド
法とノンゼロワインディング法とによって作成されるセ
グメント数が異なる場合を示ず路線図、第１−４図は複
数のクリップ領域を有する場合のセグメントデータ管理
メモリの構造を示す路線図、第１−５図はセグメントメ
モリの領域に対する異なる格納例を示す図である。 １・・・クリップ処理部、２・・・描画用メモリ、３・
・・プリンタ装置、４・・・ＣＲＴ表示装置、５・・・
走査変換部、６・・・セグメントメモリ、７・・・セグ
メン１へデータ管理メモリ、８・・・クリップ処理本体
部、９・・・セグメント画素変換部、１０・・・演算処
理部、１１・・・制御部。 プと施例のクリフピンク゛処Ｊｌブｊデ（のメイノフト
チャート第１図 Ｒ１，Ｒ２・・・、領域 ｈｌ、ｈ２・・・、各領域の７一ト′敗七り゛メントメ
モリ６の構造を示す図 第４図 セグメントテ゛−タ管理メモリ７のテ゛−タ作ｌｉｔり
４理の７０−チキート七り゛メツトメモリ６のテ゛−タ
作成処理の７トチヤ一ト第７図 七り゛メカメモリ６からの読出し、及びクリブ７°処理
のフトｆｒト第８図 七り゛メントメモリ６ 複数のクリフッ°領域を示す場合の管理メモリ７の構造
第１４図 七り゛メントと七り゛メントメモリの格納場所との陸ト
玉性を示す図第１５図

Claims (2)

【特許請求の範囲】
1. （１）境界が任意形状のクリップ領域によって、２次元
   的な被クリップ対象の上記クリップ領域内に存在する部
   分情報を取り出し、その取り出した被クリップ対象の部
   分情報をラスタ状出力装置に引渡して出力させるクリッ
   ピング処理方式において上記クリップ領域を、上記ラス
   タ状出力装置の走査線方向に沿ったセグメントに分解し
   、分解されたセグメントの情報でクリップ領域を規定し
   て上記被クリップ対象の部分情報を取り出すようにした
   ことを特徴とするクリッピング処理方式。
2. （２）上記２次元的な被クリップ対象を走査線方向に沿
   った情報に分解し、この分解された被クリップ対象の情
   報のうち、走査線方向が同一の上記クリップ領域のセグ
   メント情報区間にある情報をそのまま取り出すことによ
   って被クリップ対象の部分情報を取り出すようにしたこ
   とを特徴とする特許請求の範囲第１項に記載のクリッピ
   ング処理方式。