JPS62184576A - クリツピング回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明はグラフィックφディスプレイ装置のクリッピン
グ回路に関し、特にクリッピング境界と交差する線分の
クリッピング境界の外部にある部分をクリッピングする
ようなりリッピング回路に関する。

従来の技術 グラフィック・ディスプレイ装置において対象物を表示
する際、ピユーポートを超えて図形が現われる場合が生
じうる。この場合表示図形がビュ３ページ 一ポート内に収まるように対象物のはみ出した部分を切
りとる必要がある。この処理は一般にクリッピング（ま
たはクリップ）と呼ばれ、切りとるための境界はクリッ
ピング境界と呼ばれている。

表示対象物が２次元物体であるときはクリッピング境界
は複数（一般には４つ）の２次元直線で構成され、表示
対象物が３次元物体であるときはクリッピング境界は複
数（一般には４つないし６つ）の３次元子面で構成され
る。一方、表示対象物は２次元物体の場合でも３次元物
体の場合でも多角形によって近似されることが多い。従
ってクリッピング処理は多角形の不要な部分を複数のク
リッピング境界線または境界面に対して切りとるという
処理であると考えられる。この処理に対する有力な解法
として、アイ・イー・サザーランドとジー　ｅ　タフリ
：Ｌ　　＠　ホック−ｒ　７　（Ｉ＠Ｅ＠５ｕｔｈｅｒ
ｌａｎｄａｎｄ　Ｇ＠ＷＩＩＨｏｄｇｍａｎ）による「
リエントラント・ポリゴン・クリッピング」、コミュニ
ケーションズ・オプ・ジ・ニー・シー・エム、第１７巻
、第１号（Ｒｅｅｎｔｒａｎｔ　Ｐｏｌｙｇｏｎ　ＣＣ
１１ｐｐｉｎ”　。

ＣＡＣＭ　、Ｖｏｌ−１７，＠１　）、ｐｐ３２−４２
．１９７４で述べられているアルゴリズムが挙げられる
。このアルゴリズムでは、多角形を頂点の列として入力
し、クリッピング境界を構成する直線または平面で順次
クリッピングを行う。１つの直線または平面についての
クリッピングが終わると、その処理結果として出力され
る頂点の列で構成される多角形を入力として次の直線ま
たは平面についてクリッピングを行っていく。このアル
ゴリズムの特徴は前記の１つ１つのクリッピング境界ご
とに順次クリッピングを行って行くことに加えて、多角
形を頂点の列と考えて隣接する２つの頂点を結ぶ線分に
対してクリッピングを行うということである。

ある１つのクリッピング境界（平面でも直線でもよい）
と、多角形を構成する隣接する２つの頂点の関係を第２
図に示す。第２図ａ　％　ｃにおいて２０１はクリッピ
ング境界を、２０２はクリッピング境界２０１に対する
内部を、２０３はクリッピング境界２０１に対する外部
を示す。但し、クリッピング境界２０１上は内部に含ま
れるものと５ページ する。第２図ａは２つの頂点Ｐ１及びＰｉがともに内部
２０２にある場合を示す。この場合、線分ＰｉＰｊ　２
０４もまた内部２０２にある。第２図すは２つの頂点ｐ
ｉ及びＰ５がともに外部２０３にある場合を示す。この
場合、線分ＰｉＰｊ２０４もまた外部にある。第２図Ｃ
は２つの頂点Ｐｉ、Ｐｊ　　のうち一方（本例ではＰｉ
）が内部２０２にあり、他方（本例ではＰｊ）が外部２
０３にある場合を示す。

この場合、線分ＰｉＰｉ　２０４の一部のみが内部２０
２にある。線分ＰｉＰｊ２ｏ４とクリッピング境界２０
１の交点をＰｋ　　とすると線分ＰｉＰｋ２０５が内部
にある。従って前記第２図の各々の場合に応じて不要な
部分を切りとって行くことにより、入力された多角形の
頂点の列に対するクリッピングされた多角形の頂点の列
が生成される。

第３図にこのアルゴリズムを用いて２次元のクリッピン
グを行う場合の例を示す。第３図ａにおいて、３０１は
クリッピングの対象となる多角形Ｐｏ、Ｐｌ、Ｐ２を、
３０２はクリッピング境界ｘ＝ｘ１を、３０３はクリッ
ピング境界！＝ｘ２を、３０４６ベ啼 はクリッピング境界ｙ　＝　ｙｌ　　を、３ｏ６はクリ
ッピング境界ｙ　＝　ｙ２　を示す。３０６は多角形３
０１をクリッピング境界３０２〜３０６でクリッピング
した結果の多角形を示す。まずクリッピング境界３０２
に対して多角形３０１’ｉクリツピングする場合を例に
とって、１つのクリッピング境界に対するクリッピング
の手順を説明する。

多角形３０１は頂点の列Ｐ０．Ｐ１．Ｐ２として入力さ
れる。まず２点Ｐ。、Ｐｌはクリッピング境界３０２に
対してともに内部３０８にあるので２点Ｐ０．Ｐ１はそ
のままクリッピング結果の多角形３０９の頂点として出
力される。

次に２点Ｐ１．Ｐ２のうちＰ２は外部３０７にあるので
、線分Ｐ１Ｐ２とクリッピング境界３０２の交点Ｐ３が
出力される。最後にＰ２．ＰｏのうちＰ２は外部３０７
に、Ｐｏは内部３０８にあるので線分Ｐ２Ｐｏとクリッ
ピング境界３０２の交点Ｐ４が出力される。以上の結果
、頂点の列Ｐ０．Ｐ１．Ｐ３．Ｐ４で示される多角形３
０９がクリッピング境界３０２に対するクリッピング結
果となる。以下同様に、７ペーノ 順次クリッピング境界３０３に対するクリッピング結果
を第３図Ｃに、クリッピング境界３０４に対するクリッ
ピング結果を第３図ｄに、クリッピング境界３０６に対
するクリッピング結果を第３図ｅにそれぞれ示す。第３
図ｅの３０６が最終的に得られた多角形Ｐ９９Ｐ６ＳＰ
７９Ｐ８９Ｐ３？Ｐ４ｇＰ１ｏを示す。

発明が解決しようとする問題点 しかしながら、以上で説明したアルゴリズムのハードウ
ェア化を考える場合、ある点がクリッピング境界に対し
て内部にあるか外部にあるかを判定するには、その点の
座標値とクリッピング境界を表わす何らかの値との大小
比較々どの簡単表処理でよいが、クリッピングの対象と
なる多角形の隣接する２点のうち一方がクリッピング境
界内部に、他方が外部にあるときのクリッピング境界と
２点を結ぶ線分の交点を求めるためには、乗算や除算が
必要でありハードウェア化には不利である。

壕だ、直接的に交点を計算する代わりに、２点の中点を
求め、漸近的に交点を探索して行く［中点分割法」が、
アール・エフ・スプロールとアイ・イー拳すザーランド
（Ｒ，Ｆ、　５ｐｒｏｕｌ　ｌ　ａｎｄ　１．　Ｅ。

５ｕｔｈｅｒｌａｎｄ）による「ア・クリッピング・デ
ィバイダ」、エフ・ジエー拳シー・シー、トンプソンブ
ックス発行（”ＣＣ１１ｐｐｉｎ　Ｄｉｖｉｄｅｒ”、
ＦＩＣＣ。

Ｔｈｏｍｐｓｏｎ　Ｂｏｏｋｓ）　ｐｐ７６５〜７７５
，１９６８において提案されている。「中点分割法」は
通常座標系で表わされている２点の中点の算出は加算と
シフト演算という簡単なハードウェアで実現できるため
有力な方法であるといえる。しかしながら、クリッピン
グに先立つ座標変換処理においては、変換の表現が容易
であり、変換の合成が変換行列の積で記述できるなどの
理由から、一般に通常座標系ではなく同次座標系での座
標表現が用いられている。また、演算の精度の問題（前
記「リエントラント・ポリゴン・クリッピング」による
）などから、同次座標系においてクリッピングを行うこ
とが望ましい。ところが後記の発明の実施例の項におい
て説明するように、同次座標系における座標値で与えら
れる２点の中点は単純な加算では求９　ページ まらないため、ハードウェア化における前記の「中点分
割法」の利点がなく々るという問題があった０ 本発明はかかる点に鑑み、簡単な加減算やシフト演算の
みを用いて、同次座標系で表わされた２つの点を結ぶ線
分とクリッピング境界との交点を求めるようなりリッピ
ング回路を提供することを目的とする。

問題点を解決するための手段 本発明は前記問題点を解決するために、クリッピング境
界と交差する線分の２つの端点のうち前記クリッピング
境界に対して内部にある第１の端点の同次座標系におけ
る座標値を格納する第１のレジスタ群と、前記クリッピ
ング境界に対して外部にある第２の端点の同次座標系に
おける座標値を格納する第２のレジスタ群と、前記第１
のレジスタ群に格納されている第１の端点の座標値と前
記第２のレジスタ群に格納されている第２の端点の座標
値との桁合わせを行う桁合わせ回路と、前記桁合わせ回
路によって桁合わせされた前記第１１０ベー、 及び第２の端点の各々の座標値の対応する要素を加算す
る加算回路と、前記加算回路の出力値を同次座標系にお
ける座標値としてもつ第３の点が、前記クリッピング境
界に対して境界上にあるが、境界の内部にあるかまたは
境界の外部にあるかのいずれかを判定する判定回路と、
前記判定回路の出力に基づき、前記第３の点が前記クリ
ッピング境界に対して境界上にあるときには前記加算回
路の出力値をクリッピング境界と前記の線分との交点の
座標値として出力し、境界の内部にあるときには前記加
算回路の出力値を前記第１のレジスタ群に格納し、境界
の外部にあるときには前記加算回路の出力値を前記第２
のレジスタ群に格納する制御回路とを備えたクリッピン
グ回路である。

作　　　用 本発明は前記の構成により、クリッピング境界と交差す
る線分の２つの端点の同次座標系における座標値を入力
データとして受けとり第１及び第２のレジスタ群に格納
し、桁合わせ回路により各々のレジスタ群に格納された
座標値に適当な数を１１　ページ 乗じ（例えば加算またはシフト演算を行う）で各りのＷ
座標（２次元の場合には座標値の第３次元の要素、３次
元の場合には座標値の第４次元の要素）の絶対値の桁合
わせを行い、桁合わせした座標値を加算回路によって単
純に加算して得られた値を「擬似的な中点」の座標値と
見なし「中点分割法」と同様の処理を行う。すなわち、
前記の判定回路によって前記の点とクリッピング境界と
の位置関係を判定し、前記の制御回路は前記の点がクリ
ッピング境界の内部にあるときは加算回路の出力を前記
第１のレジスタ群に格納し、この値と既に前記第２のレ
ジスタ群に格納されている値とを新らたな線分の２つの
端点の座標値として前記の処理を繰り返し、また前記の
点がクリッピング境界の外部にあるときは加算回路の出
力を前記第２のレジスタ群に格納し、この値と既に前記
第１のレジスタ群に格納されている値とを新らたな線分
の２つの端点の座標値として前記の処理を繰シ返し、ま
た前記の点がクリッピング境界上にあるときには加算回
路の出力を求めている交点の座標値として出力し、１つ
の線分に対するクリッピング処理を終える。

実施例 本発明の実施例を図面を用いて説明する前に、本発明の
依るところの原理についての説明並らびに証明を行う。

以下の説明で用いる座標値はすべて３次元空間上の点を
示しているが、２次元子面上のクリッピングを考える場
合には座標値の次元を１つ減らせる（すなわち２座標を
省略する）ことにより容易に類推できる。なお座標値と
してアルファベット小文字を用いて表現されたもの〔例
えば（ｘｔｙｔｚ））を通常座標系の座標値とし、アル
ファベット大文字を用いて更に第４の座標Ｗを付加して
表現されたもの〔例えば（ｘ、Ｙ、Ｚ。

ｗ））を同次座標系の座標値とする。

クリッピング境界の条件は一般には次式で表現されるが
説明を簡単にするため次式１３　ページ で考える。通常座標系における点（”ｙＹ、ｚ）は同次
座標系において（ｘｙ　Ｙｐ　Ｚｐ　”　）と表現され
る。但し、Ｗは０でないものとし、なる関係を満足する
。従ってクリッピング境界の条件を示す式（功は同次座
標系では次のように表わされる。

または、 同次座標系における座標値に０でないスカラーを１４　
ページ 乗じても対応する通常座標は変化しないので式（４）の
場合のみを考えるものとする。式（→かられかるように
クリッピング境界は次式（＠に示す６つの平面からなる
。

いま、１つのクリッピング境界ｗ−Ｘ＝ｏに対して２点
Ｐ１（ｘｌ、Ｙｌ、Ｚｌ、Ｗｌ）とＰ２（Ｘ２．Ｙ２，
２２２ｗ２）を結ぶ線分をクリッピングを行う場合を考
える。

但し、Ｗｌ、Ｗ２〉０とする。

式（４よりｘ１≦ｗ１かつｘ２≦ｗ２のときは２点Ｐ１
とＰ２　はともにクリッピング境界の内部にあり、従っ
て線分Ｐ１Ｐ２もまたクリッピング境界の内部にある。

またｘｌ〉Ｗｌかつｘ２〉Ｗ２のときは２点Ｐ１とＰ２
はともにクリッピング境界の外部にあり、従って線分Ｐ
１Ｐ２もまたクリッピング境界の外部にある。またＸｌ
　＞　’Ｖ１１かつｘ２りＷ２のときまたはＸｌ＜ｗｌ
かつｘ２〉Ｗ２のときは２点のうち一方がクリッピング
境界の内部に、他方が外部にあるので線分Ｐ１Ｐ２のう
ちクリッピング境界の外部にある部分を切りとらなけれ
ばならない。いま点Ｐ１がクリッピング境界の内部にあ
り、点Ｐ２が外部にあるものとする。線分Ｐ１Ｐ２とク
リッピング境界ｗ　−Ｘ　＝　Ｏとの交点ヲＰ３（Ｘ３
ｔＹ３ｔＺ３ｙ”３）とすると、点Ｐ３は次式（７）で
与えられる。

前記の同次座標系の座標値の性質から式（７）は、とも
表わせる。しかしながら式（＠を用いても交点Ｐ３の算
出には少なくとも６回の乗算が必要となる。一方、前記
の通常座標系における「中点分割法」を適用する場合を
考える。２点Ｐ１　　及びＰ２に対応する通常座標系に
おける座標値は各々（ｘ１／Ｗ１．Ｙ１／Ｗ１．Ｚ１／
Ｗ１）ト（ｘ２／Ｗ２．Ｙ２／Ｗ２゜Ｚ２／Ｗ２）テあ
ルコトカラ中点Ｐ４（ｘ４．Ｙ４．Ｚ４．Ｗ４）に対応
する通常座標系における座標値は、次式（９）％式％ 前記の同次座標系における座標値の性質から式（時は、 とも表わせる。しかしながら式（１ｏ）を用いても中点
Ｐ４の算出には少なくとも７回の乗算が必要となり、式
（Ｆ４に従って直接的に交点Ｐ３を求めるよりも処理が
複雑となり、「中点分割法」を適用することは無意味と
なる。

そこで中点Ｐ４に代わる点として次式（１１）で表わさ
れる点ＰＭ（ＸＭ、ＹＭ、ＺＭ９ｗＭ）を考える。

いま通常座標系において２点Ｐ１とＰＭを結ぶベクトル
Ｐ１ＰＭは次式（１２）で表わされる。

１８ベー、・ 一方、２点Ｐ１とＰ２を結ぶベクトルＰ１Ｐ２は次式（
１３）％式％ 従って式（１２）及び式（１３）より、次式が導がれる
。

いまＷ１〜２　はともに正であるから、なる関係が成立
する。以上から点ＰＭは線分Ｐ１Ｐ２上の端点Ｐ１　　
及びＰ２　の間にある点となる。

従って式（１１）に従って点ＰＭの座標？Ｗｋ求め、得
ら１９　ベー、゛ れた座標値に対して式（→を用いてクリッピング境界と
の位置関係を判定し点ＰＭがクリッピング境界の内部に
ある（ＸＭ＜ｗＭ）ときは点Ｐ１　　の座標値を点ＰＭ
の座標値で置き換えて線分ＰＭＰ２に対して前記と同様
の処理を、また点ＰＭがクリッピング境界の外部にある
（　ＸＭ＞”Ｍ）ときは点Ｐ２の座標値を点ＰＭの座標
値で置き換えて線分Ｐ１ＰＭに対して前記と同様の処理
を点ＰＭがクリッピング境界上に来るまで繰り返す。

第１図は以上に説明した本発明のクリッピング処理を行
うクリッピング回路の実施例を示す図である。

第１図において１０１はあるクリッピング境界と交差す
る線分の２つの端点のうちクリッピング境界の内部にあ
る第１の端点の座標値データを、１０２は座標値データ
１０１の要素を格納する第１のレジスタ群（（，１０３
はクリッピング境界の外部にある第２の端点の座標値デ
ータを、１ｏ４は座標値データ１０３の要素を格納する
第２のレジスタ群を、１ｏ５はレジスタ群１０２とレジ
スタ群１０４に格納されている座標値データのＷ座標の
桁合わせを行う桁合わせ回路’ｉ、１０６は桁合わせ回
路１０５によって補正された座標値データの対応する要
素の加算を行う加算回路を、１０７は加算回路１０６の
出力を座標値にもつ点と与えられたクリッピング境界と
の位置関係を判定する判定回路を、１０８は判定回路１
０７の結果に応じて加算回路１０６の出力を第１のレジ
スタ群１０２に格納したり、第２のレジスタ群１０４に
格納したり、最終結果１０９として出力する制御回路を
示す。

加算回路１０６、判定回路１ｏ７、制御回路１０８の働
きについては前記の説明と重複するため再度の説明は省
略し、桁合わせ回路１０５の働きについてのみ補足説明
をする。

レジスタ群１０２及び１０４に格納されている座標値デ
ータのＷ座標の値の絶対値が非常に大きく異なる場合（
例えばＷｌ（Ｗ２のとき）、前記式、　（１４）　　は
、 ２１　ベー、゛ となり、加算回路１０６から出力される点ＰＭの座標値
は、もとの端点Ｐ２の座標値に非常に近い値となる。従
って、点ＰＭがなかなかクリッピング境界との交点に収
束しないという現象が生じる。

極端な場合、加算回路１０６における加算の際に「情報
落ち」が生じ、点ＰＭが永久に最初の２つの端点のいず
れかに留まり処理が終了しないことも起りうる。そこで
、前記の同次座標系における座標値の性質を利用して、
桁合わせ回路１０５によりレジスタ群１０２及び１０４
に格納されている座標値データの絶対値を比較し、絶対
値の桁がほぼ等しくなるようにいずれか一方または両方
の座標値データに対して適当な値を乗じて桁合わせを行
う。これにより式（１６）のＷ２／（Ｗ１＋Ｗ２）も％
に近づき点−も真の中点に近くなる。この桁合わせ処理
は、座標値データが固定小数点数で表現されているとき
には座標値データのシフト演算に＼、−５−−１．−−
−、−、、、、−１、−７−１−一、、、７．。

２２　ヘ−ノ れているときには座標値データの指数部に対する加減算
で実現できるため、実際には乗算回路を必要としない。

なお、実施例の説明においてはクリッピング境界として
ｗ　−Ｘ　＝　Ｏを用いたが、判定回路１０７における
判定条件を変えることにより他のクリッピング境界に対
しても容易に適用できることは言うまでもない。

発明の効果 以上のように本発明によれば、同次座標系におけるクリ
ッピング処理が乗除算回路を用いずに実現でき、ハード
ウェア化、特にＬＳＩ化に適しており、グラフィック・
ディスプレイ装置における画像生成の高速化並びにハー
ドウェア・コストの低減に対する寄与が犬である。

【図面の簡単な説明】

第１図は本発明のクリッピング回路の実施例の構成を示
すブロック図、第２図はクリッピングのアルゴリズムの
説明図、第３図は２つの端点を結ぶ線分とクリッピング
境界との位置関係図である。 ２３べ−７・ １０２．ＬＯ４・・・・・・レジスタ群、１０６・曲・
桁合わせ回路、１ｏ６・・・・・・加算回路、１０７・
・・・・・判定回路、１０８・・・・・・制御回路。 代理人の氏名　弁理士　中　尾　敏　男　ほか１名第１
図 第２図 （ｄ） （Ｃ） 第３図 ｔｔＬ） （ｄン （ど−ン

Claims (1)

【特許請求の範囲】
1. クリッピング境界と交差する線分の２つの端点のうち前
   記クリッピング境界に対して内部にある第１の端点の同
   次座標系における座標値を格納する第１のレジスタ群と
   、前記クリッピング境界に対して外部にある第２の端点
   の同次座標系における座標値を格納する第２のレジスタ
   群と、前記第１のレジスタ群に格納されている第１の端
   点の座標値と前記第２のレジスタ群に格納されている第
   ２の端点の座標値との桁合わせを行う桁合わせ回路と、
   前記桁合わせ回路によって桁合わせされた前記第１及び
   第２の端点の各々の座標値の対応する要素を加算する加
   算回路と、前記加算回路の出力値を同次座標系における
   座標値としてもつ第３の点が、前記クリッピング境界に
   対して境界上にあるか、境界の内部にあるかまたは境界
   の外部にあるかを判定する判定回路と、前記判定回路の
   判定に基づき前記第３の点が前記クリッピング境界に対
   して境界上にあるときには前記加算回路の出力値をクリ
   ッピング境界と前記の線分との交点の座標値として出力
   し、前記第３の点が境界の内部にあるときには前記加算
   回路の出力値を前記第１のレジスタ群に格納し、前記第
   ３の点が境界の外部にあるときには前記加算回路の出力
   値を前記第２のレジスタ群に格納する制御回路とを具備
   することを特徴とするクリッピング回路。