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

Description

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

従来の技術 グラフィック・ディスプレイ装置において対象物を表示
する際、ビューポートを超えて図形が現われる場合が生
じうる。この場合表示図形がビューポート内に収まるよ
うに対象物のはみ出した部分を切りとる必要がある。こ
の処理は一般にクリッピング（またはクリップ）と呼ば
れ、切りとるための境界はクリッピング境界と呼ばれて
いる。表示対象物が２次元物体であるときはクリッピン
グ境界は複数（一般に４つ）の２次元直線で構成され、
表示対象物が３次元物体であるときはクリッピング境界
は複数（一般には４つないし６つ）の３次元平面で構成
される。一方、表示対象物は２次元物体の場合でも３次
元物体の場合でも多角形によって近似されることが多
い。従ってクリッピング処理は多角形の不要な部分を複
数のクリッピング境界線または境界面に対して切りとる
という処理であると考えられる。この処理に対する有力
な解法として、アイ・イー・サザーランドとジー・ダブ
リュー・ホッジマン（Ｉ・Ｅ・Sutherland and Ｇ・
Ｗ・Hodgman）による「リエントラント・ポリゴン・ク
リッピング」，コミュニケーションズ・オブ・ジ・エー
・シー・エム、第17巻、第１号（“Reentrant Polygon
Clipping",CACM,Vol.17,No.１）,pp32−42,1974で述
べられているアルゴリズムが挙げられる。このアルゴリ
ズムでは、多角形を頂点の列として入力し、クリッピン
グ境界を構成する直線または平面で順次クリッピングを
行う。１つの直線または平面についてのクリッピングが
終わると、その処理結果として出力される頂点の列で構
成される多角形を入力として次の直線または平面につい
てクリッピングを行っていく。このアルゴリズムの特徴
は前記の１つ１つのクリッピング境界ごとに順次クリッ
ピングを行って行くことに加えて、多角形を頂点の列と
考えて隣接する２つの頂点を結ぶ線分に対してクリッピ
ングを行うということである。ある１つのクリッピング
境界（片面でも直線でもよい）と、多角形を構成する隣
接する２つの頂点の関係を第２図に示す。第２図ａ〜ｃ
において201はクリッピング境界を、202はクリッピング
境界201に対する内部を、203はクリッピング境界201に
対する外部を示す。但し、クリッピング境界201上は内
部に含まれるものとする。第２図ａは２つの頂点Pi及び
Pjがともに内部202にある場合を示す。この場合、線分P
iPj204もまた内部202にある。第２図ｂは２つの頂点Pi
及びPjがともに外部203にある場合を示す。この場合、
線分PiPj204もまた外部にある。第２図ｃは２つの頂点P
i，Pjのうち一方（本例ではPi）が内部202にあり、他方
（本例ではPj）が外部203にある場合を示す。この場
合、線分PiPj204の一部のみが内部202にある。線分PiPj
204とクリッピング境界201の交点をPkとすると線分PiPj
205が内部にある。従って前記第２図の各々の場合に応
じて不要な部分を切りとって行くことにより、入力され
た多角形の頂点の列に対するクリッピングされた多角形
の頂点の列が生成される。

第３図にこのアルゴリズムを用いて２次元のクリッピン
グを行う場合の例を示す。第３図ａにおいて、301はク
リッピングの対象となる多角形Ｐ_０,P_１,P_２を、302は
クリッピング境界ｘ＝ｘ_１を、303はクリッピング境界
ｘ＝ｘ_２を、304はクリッピング境界ｙ＝ｙ_１を、305は
クリッピング境界ｙ＝ｙ_２を示す。306は多角形301をク
リッピング境界302〜305でクリッピングした結果の多角
形を示す。まずクリッピング境界302に対して多角形301
をクリッピングする場合を例にとって、１つのクリッピ
ング境界に対するクリッピングの手順を説明する。

多角形301は頂点の列Ｐ_０,P_１,P_２として入力される。
まず２点Ｐ_０,P_１はクリッピング境界302に対してとも
に内部308にあるので２点Ｐ_０,P_１はそのままクリッピ
ング結果の多角形309の頂点として出力される。

次に２点Ｐ_１,P_２のうちＰ_２は外部307にあるので、線
分 とクリッピング境界302の交点Ｐ_３が出力される。最後
にＰ_２,P_０のうちＰ_２は外部307に、Ｐ_０は内部308にあ
るので線分 とクリッピング境界302の交点Ｐ_４が出力される。以上
の結果、頂点の列Ｐ_０,P_１,P_３,P_４で示される多角形30
9がクリッピング境界302に対するクリッピング結果とな
る。以下同様に、順次クリッピング境界303に対するク
リッピング結果を第３図ｃに、クリッピング境界304に
対するクリッピング結果を第３図ｄに、クリッピング境
界305に対するクリッピング結果を第３図ｅにそれぞれ
示す。第３図ｅの306が最終的に得られた多角形Ｐ_９,P
_５,P_７,P_８,P_３,P_４,P₁₀を示す。

発明が解決しようとする問題点 しかしながら、以上で説明したアルゴリズムのハードウ
ェア化を考える場合、ある点がクリッピング境界に対し
て内部にあるか外部にあるかを判定するには、その点の
座標値とクリッピング境界を表わす何らかの値との大小
比較などの簡単な処理でよいが、クリッピングの対象と
なる多角形の隣接する２点のうち一方がクリッピング境
界内部に、他方が外部にあるときのクリッピング境界と
２点を結ぶ線分の交点を求めるためには、乗算や除算が
必要でありハードウェア化には不利である。また、直線
的に交点を計算する代わりに、２点の中点を求め、漸近
的に交点を探索して行く「中点分割法」が、アール・エ
フ・スプロールとアイ・イー・サザーランド（R.F.Spro
ull and I.E.Sutherland）による「ア・クリッピング
・ディバイダ」，エフ・ジェー・シー・シー，トンプソ
ンブックス発行（“Clipping Divider",FJCC,Thompson
Books）pp765〜775,1968において提案されている。
「中点分割法」は通常座標系で表わされている２点の中
点の算出は加算とシフト演算という簡単なハードウェア
で実現できるため有力な方法であるといえる。しかしな
がら、クリッピングに先立つ座標変換処理においては、
変換の表現が容易であり、変換の合成が変換行列の積で
記述できるなどの理由から、一般に通常座標系ではなく
同次座標系での座標表現が用いられている。また、演算
の精度の問題（前記「リエントラント・ポリゴン・クリ
ッピング」による）などから、同次座標系においてクリ
ッピングを行うことが望ましい。ところが後記の発明の
実施例の項において説明するように、同次座標系におけ
る座標値で与えられる２点の中点は単純な加算では求ま
らないため、ハードウェア化における前記の「中点分割
法」の利点がなくなるという問題があった。

本発明はかかる点に鑑み、簡単な加減算やシフト演算の
みを用いて、同次座標系で表わされた２つの点を結ぶ線
分とクリッピング境界との交点を求めるようなクリッピ
ング回路を提供することを目的とする。

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

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

実施例 本発明の実施例を図面を用いて説明する前に、本発明の
依るところの原理についての説明並らびに証明を行う。
以下の説明で用いる座標値はすべて３次元空間上の点を
示しているが、２次元平面上のクリッピングを考える場
合には座標値の次元を１つ減らせる（すなわちｚ座標を
省略する）ことにより容易に類推できる。なお座標値と
してアルファベット小文字を用いて表現されたもの〔例
えば（x,y,z）〕を通常座標系の座標値とし、アルファ
ベット大文字を用いて更に第４の座標ｗを付加して表現
されたもの〔例えば（x,y,z,w）〕を同次座標系の座標
値とする。

クリッピング境界の条件は一般に次式 で表現されるが説明を簡単にするため次式 で考える。通常座標系における点（x,y,z）は同次座標
系において（X,Y,Z,w）と表現される。但し、ｗは０で
ないものとし、 なる関係を満足する。従ってクリッピング境界の条件を
示す式(2)は同次座標系では次のように表わされる。

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

いま、１つのクリッピング境界ｗ−Ｘ＝０に対して２点
Ｐ_１（Ｘ_１,Y_１,Z_１,w_１）とＰ_２（Ｘ_２,Y_２,Z_２,w_２）
を結ぶ線分をクリッピングを行う場合を考える。但し、
ｗ_１,w_２＞０とする。

式(4)よりＸ_１ｗ_１かつＸ_２ｗ_２のときは２点Ｐ_１
とＰ_２はともにクリッピング境界の内部にあり、従って
線分 もまたクリッピング境界の内部にある。またｘ_１＞ｗ_１
かつＸ_２＞ｗ_２のときは２点Ｐ_１とＰ_２はともにクリッ
ピング境界の外部にあり、従って線分 もまたクリッピング境界の外部にある。またＸ_１＞ｗ_１
かつＸ_２ｗ_２のときまたはＸ_１ｗ_１かつＸ_２＞ｗ_２
のときは２点のうち一方がクリッピング境界の内部に、
他方が外部にあるので線分 のうちクリッピング境界の外部にある部分を切りとらな
ければならない。いま点Ｐ_１がクリッピング境界の内部
にあり、点Ｐ_２が外部にあるものとする。線分 とクリッピング境界ｗ−Ｘ＝０との交点をＰ_３（Ｘ_３,Y
_３,Z_３,w_３）とすると、点Ｐ_３は次式(7)で与えられ
る。

前記の同次座標系の座標値の性質から式(7)は、 とも表わせる。しかしながら式(8)を用いても交点Ｐ_３
の算出には少なくとも６回の乗算が必要となる。一方、
前記の通常座標系における「中点分割法」を適用する場
合を考える。２点Ｐ_１及びＰ_２に対応する通常座標系に
おける座標値は各々（Ｘ_１／ｗ_１,Y_１／ｗ_１,Z_１／
ｗ_１）と（Ｘ_２／ｗ_２,Y_２／ｗ_２,Z_２／ｗ_２）であるこ
とから中点Ｐ_４（Ｘ_４,Y_４,Z_４,w_４）に対応する通常座
標系における座標値は、次式(9)で与えられる。

前記の同次座標系におる座標値の性質から式(9)は、 とも表わせる。しかしながら式(10)を用いても中点Ｐ_４
の算出には少なくとも７回の乗算が必要となり、式(8)
に従って直接的に交点Ｐ_３を求めるよりも処理が複雑と
なり、「中点分割法」を適用することは無意味となる。

そこで中点Ｐ_４に代わる点として次式(11)で表わされる
点Ｐ_Ｍ（Ｘ_Ｍ,Y_Ｍ,Z_Ｍ,w_Ｍ）を考える。

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

一方、２点Ｐ_１とＰ_２を結ぶベクトル は次式(13)で表わされる。

従って式(12)及び式(13)より、次式が導かれる。

いまｗ_１とｗ_２はともに正であるから、 なる関係が成立する。以上から点Ｐ_Ｍは線分 上の端点Ｐ_１及びＰ_２の間にある点となる。従って式(1
1)に従って点Ｐ_Ｍの座標値を求め、得られた座標値に対
して式(4)を用いてクリッピング境界との位置関係を判
定し点Ｐ_Ｍがクリッピング境界の内部にある（Ｘ_Ｍ＜ｗ
_Ｍ）ときは点Ｐ_１の座標値を点Ｐ_Ｍの座標値で置き換え
て線分 に対して前記と同様の処理を、また点Ｐ_Ｍがクリッピン
グ境界の外部にある（Ｘ_Ｍ＞ｗ_Ｍ）ときは点Ｐ_２の座標
値を点Ｐ_Ｍの座標値で置き換えて線分 に対して前記と同様の処理を点Ｐ_Ｍがクリッピング境界
上に来るまで繰り返す。

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

第１図において101はあるクリッピング境界と交差する
線分の２つの端点のうちクリッピング境界の内部にある
第１の端点の座標値データを、102は座標値データ101の
要素を格納する第１のレジスタ群を、103はクリッピン
グ境界の外部にある第２の端点の座標値データを、104
は座標値データ103の要素を格納する第２のレジスタ群
を、105はレジスタ群102とレジスタ群104に格納されて
いる座標値データのｗ座標の桁合わせを行う桁合わせ回
路を、106は桁合わせ回路105によって補正された座標値
データの対応する要素の加算を行う加算回路を、107は
加算回路106の出力を座標値にもつ点と与えられたクリ
ッピング境界との位置関係を判定する判定回路を、108
は判定回路107の結果に応じて加算回路106の出力を第１
のレジスタ群102に格納したり、第２のレジスタ群104に
格納したり、最終結果109として出力する制御回路を示
す。

加算回路106、判定回路107、制御回路108の働きについ
ては前記の説明と重複するため再度の説明は省略し、桁
合わせ回路105の働きについてのみ補足説明をする。

レジスタ群102及び104に格納されている座標値データの
ｗ座標の値の絶対値が非常に大きく異なる場合（例えば
ｗ_１≪ｗ_２のとき）、前記式(14)は、 となり、加算回路106から出力される点Ｐ_Ｍの座標値
は、もとの端点Ｐ_２の座標値に非常に近い値となる。従
って、点Ｐ_Ｍがなかなかクリッピング境界との交点に収
束しないという現象が生じる。極端な場合、加算回路10
6における加算の際に「情報落ち」が生じ、点Ｐ_Ｍが永
久に最初の２つの端点のいずれかに留まり処理が終了し
ないことも起りうる。そこで、前記の同次座標系におけ
る座標値の性質を利用して、桁合わせ回路105によりレ
ジスタ群102及び104に格納されている座標データのｗ座
標の絶対値を比較し、絶対値の桁がほぼ等しくなるよう
にいずれか一方または両方の座標値データに対して適当
な値を乗じて桁合わせを行う。これにより式(15)のｗ_２
／（ｗ_１＋ｗ_２）も1/2に近づき点Ｐ_Ｍも真の中点に近
くなる。この桁合わせ処理は、座標値データが固定小数
点数で表現されているときには座標値データのシフト演
算により、また座標値データが浮動小数点数で表現され
ているときには座標値データの指数部に対する加減算で
実現できるため、実際には乗算回路を必要としない。

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

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

【図面の簡単な説明】

第１図は本発明のクリッピング回路の実施例の構成を示
すブロック図、第２図はクリッピングのアルゴリズムの
説明図、第３図は２つの端点を結ぶ線分とクリッピング
境界との位置関係図である。 102,104…レジスタ群、105…桁合わせ回路、106…加算
回路、107…判定回路、108…制御回路。

Claims (1)

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