JPH0821085B2 - クリッピング回路 - Google Patents

Description

【発明の詳細な説明】 産業上の利用分野 本発明はグラフィック・ディスプレイ装置のクリッピ
ング回路に関し、特に多角形を表す頂点の座標系列を入
力とし、クリッピング領域外部に存在する部分を除去
し、内部に存在する部分のみからなる新たな多角形を構
成する頂点の座標系列を出力するクリッピング回路に関
する。

従来の技術 グラフィック・ディスプレイ装置において物体を表示
する際、ビューポートを越えて図形が現れる場合が生じ
うる。この場合表示図形がビューポート内に収まるよう
に物体のはみ出した部分を切り取る必要がある。この処
理はクリッピングと呼ばれ、切り取るための境界はクリ
ッピング境界と呼ばれ、一般に、表示物体が２次元物体
であるときはクリッピング境界は複数の２次元直線で構
成され、表示物体が３次元物体であるときはクリッピン
グ境界は複数の３次元平面で構成される。一方、表示物
体は２次元物体の場合でも３次元物体の場合でも多角形
の集合として近似的に表現されることが多い。従って、
クリッピングの処理は物体を構成する各々の多角形の不
要な部分を複数のクリッピング境界面または境界線に対
して切り取るという処理であると考えられる。（以後、
クリッピング境界面とクリッピング境界線をまとめて
「クリッピング境界」と呼ぶものとする）。このクリッ
ピング処理に対する有力な解法としては、アイ・イー・
サザーランドとジー・ダブリュー・ホッジマン（I.E.Su
ther−land and G.W.Hod geman）による「リエントラン
トポリゴンクリッピング」コミュニケーションズ・オブ
・ジ・エイ・シー・エム、第17巻、第１号（″Reentran
t Pol ygon Clipping,″CACM.Vol.17,No.1）、pp32−4
2、1974年、で示されている方法が挙げられる。この方
法では、クリッピングの対象となる多角形を頂点の列と
して入力し、クリッピング境界を構成する直線または平
面の１つの境界についてクリッピング処理を行い、１つ
の境界についての処理が終わると、その処理結果として
出力される頂点の列で構成される多角形を新たな入力と
して次の境界についてのクリッピング処理を行う。この
方法の特徴は前記の１つ１つのクリッピング境界ごとに
順次処理を行うことに加えて、多角形を頂点の系列と考
えて２つの隣接する頂点を結ぶ線分に対してクリッピン
グ処理を行うということである。ある１つのクリッピン
グ境界と多角形を構成する２つの隣接する頂点の位置関
係を第８図に示す。第８図の（ａ）〜（ｄ）において80
1はクリッピング境界を、802はクリッピング境界801に
対する内側を、803はクリッピング境界801に対する外側
を示す。なお、クリッピング境界801そのものは、内側8
02または外側803のいずれか一方に含まれるものとす
る。頂点P804と頂点Q805は、先に頂点P804が入力されそ
の次に頂点Q805が入力されたものとする。第８図の
（ａ）は、２つの頂点P804とQ805がともに内側802にあ
る場合を示している。この場合、線分PQ806もまた内側8
02にある。第８図の（ｂ）は、２つの頂点P804とQ805が
ともに外側803にある場合を示している。この場合、線
分PQ806もまた外側にある。第８図の（Ｃ）は、頂点P80
4が内側802にありQ805が外側803にある場合を示してい
る。この場合、線分PQ806とクリッピング境界801との交
点をR807とすると線分PR808が内側にある。第８図の
（ｄ）は、頂点Q805が内側802にありP804が外側803にあ
る場合を示している。この場合、線分PQ806とクリッピ
ング境界801との交点をR807とすると線分RQ809が内側に
ある。従って第８図の各々の場合に応じて不要な部分を
切り取ることにより、入力された多角形の頂点の系列に
対するクリッピングされた多角形の頂点の系列が生成さ
れる。第９図に、第８図の（ａ）〜（ｄ）の各々の場合
に応じて出力すべき頂点を示す。順次入力されたすべて
の頂点について、隣接する２つの頂点とクリッピング境
界との位置関係を判定し、第９図に従って入力された頂
点および／または交点の座標を出力することにより、そ
のクリッピング境界に対する１つの多角形のクリッピン
グ処理が完了する。第10図に示した多角形ABCD1001につ
いて前記の方法を適用した場合の具体的な処理の流れを
以下に説明する。第10図において、1001はクリッピング
の対象となる多角形ABCDを、1002はクリッピング境界
を、1003はクリッピング境界1002に対する内側を、1004
はクリッピング境界1002に対する外側を示す。なお、多
角形1001の頂点はA,B,C,Dの順に入力されるものとす
る。まず最初に頂点A1005が入力される。頂点A1005は内
側1003にある。次に頂点B1006が入力される。頂点B1006
もまた内側1003にあることから、線分AB1007には前記の
第８図または第９図の（ａ）の場合が適用され、頂点B1
006が出力される。次に頂点C1008が入力される。頂点C1
008は外側1004にあることから、線分BC1009には前記の
第８図または第９図の（Ｃ）の場合が適用され、線分BC
1009とクリッピング境界1002との交点E1010が出力され
る。次に頂点D1011が入力される。頂点D1011は外側1004
にあることから、線分CD1012には前記の第８図または第
９図の（ｂ）の場合が適用され、頂点は出力されない。
最後に、再度頂点A1005が入力されるか、または最初に
頂点A1005が入力されたときに保持していたクリッピン
グ境界1002に対する頂点A1005の内外判定結果を参照す
ると、頂点A1005は内側1003にあることから、線分DA101
3には前記の第８図または第９図の（ｄ）の場合が適用
され、線分DA1013とクリッピング境界1002との交点F101
4がまず出力され、その後に頂点A1005が出力される。以
上の結果、入力された多角形1001に対してクリッピング
境界1002の外側1004にある部分を取り除いた多角形の頂
点の列として、４つの頂点B,E,F,Aが出力される。な
お、第11図に以上の処理の流れを一覧にして示す。第11
図において「位置関係」の欄は、「１つ前に入力された
頂点」と「（今、）入力された頂点」でできる線分とク
リッピング境界1002との位置関係に対して、前記の第８
図または第９図の４通りのいずれの場合が適用されたか
を示している。

発明が解決しようとする課題 しかしながら、以上に述べたクリッピング処理の方法
に基づくクリッピング回路においては、クリッピング境
界上に存在するような頂点を含んだ多角形を入力したと
きに、クリッピング境界上の頂点が重複して出力される
という問題があった。第12図に示す多角形ABCD1201を用
いて具体的に説明する。第12図において、1202はクリッ
ピング境界を、1203はクリッピング境界1202に対する内
側を、1204はクリッピング境界1202に対する外側を示
す。なお、クリッピング境界1202そのものは内側1203に
含まれるものとする。また頂点B1206およびD1210はクリ
ッピング境界1202上にあるものとする。なお、多角形12
01の頂点はA,B,C,Dの順に入力されるものとする。まず
最初に頂点A1205が入力される。頂点A1205は内側1203に
ある。次に頂点B1206が入力される。頂点B1206はクリッ
ピング境界1202上の頂点である。従って、先の仮定から
頂点B1206もまた内側1203にあることから、線分AB1207
には前記の第８図または第９図の（ａ）の場合が適用さ
れ、頂点B1206が出力される。次に頂点C1208が入力され
る。頂点C1208は外側1204にあることから、線分BC1209
には前記の第８図または第９図の（Ｃ）の場合が適用さ
れ、線分BC1209とクリッピング境界1202との交点が出力
されるが、この交点は頂点B1206に等しく、再度頂点B12
06が出力されることになる。次に頂点D1210が入力され
る。頂点D1210はクリッピング境界1202上の頂点であ
る。従って、先の仮定から頂点D1210もまた内側1203に
あることから、線分CD1211には前記の第８図または第９
図の（ｄ）の場合が適用され、線分CD1211とクリッピン
グ境界1202との交点がまず出力され、その後に頂点D121
0が出力されるが、この交点は頂点D1210に等しい。従っ
て、頂点D1210が２つ続けて出力される。最後に、再度
頂点A1205が入力されるか、または最初に頂点A1205が入
力されたときに保持していたクリッピング境界1202に対
する頂点A1205の内外判定結果を参照すると、頂点A1205
は内側1203にあることから、線分DA1212には前記の第８
図または第９図の（ａ）の場合が適用され、頂点A1205
が出力される。以上の結果、入力された多角形1201に対
してクリッピング境界1202の外側1204にある部分を取り
除いた多角形の頂点の列として、５つの頂点B,B,D,D,A
が出力される。従って、クリッピング境界1202上の頂点
B1206および頂点D1210が各々２度ずつ出力されたことに
なる。第13図に以上の処理の流れを一覧にして示す。以
上の例では、クリッピング境界そのものを内側に含まれ
るものとしていた。逆にクリッピング境界そのものが外
側に含まれるものとした場合を考える。この場合には、
第12図に示した多角形1201を入力したとき、途中の経過
を省略するが、同様に前記の第８図または第９図の各々
の場合を適用して行くと、第14図に示したようになり、
クリッピングの結果として３つの頂点の列B,D,Aが重複
することなく出力され、前記の問題点がないかのように
思われる。しかし、クリッピング境界そのものが外側に
含まれるとした場合にも、やはりクリッピング境界上の
頂点を含む多角形を入力したときに、クリッピング境界
上にある頂点が重複して出力される例を第15図に示す。
第15図において、1501はクリッピングの対象となる多角
形ABCDを、1502はクリッピング境界を、1503はクリッピ
ング境界1502に対する内側を、1504はクリッピング境界
1502に対する外側を示し、頂点C1505がクリッピング境
界1502上にあるものとする。この場合には、多角形1501
を入力したとき、途中の経過を省略するが、同様に前記
の第８図または第９図の各々の場合を適用して行くと、
第16図に示したようになり、クリッピングの結果として
５つの頂点の列B,C,C,D,Aが出力され、頂点C1505が重複
して出力される。以上のように、クリッピング境界その
ものが内側または外側のいずれの方に含まれるとして
も、クリッピング境界上にある頂点を含む多角形を入力
したとき、この従来のクリッピング方法に基づくクリッ
ピング回路では、クリッピング境界上にある頂点が重複
して出力されることは避けられなかった。一般に、クリ
ッピングの処理は複数のクリッピング境界に対して行わ
れるため、１つのクリッピング境界に対して処理され出
力された多角形の頂点の列を、次のクリッピング境界に
対する処理の入力として用いる。従って、途中のクリッ
ピングの処理において重複して出力された頂点に対する
処理は、全く無駄な処理となる。このように、従来のク
リッピング回路では、クリッピング境界上にある頂点を
含む多角形が入力された場合に処理量が増加するという
問題点があった。本発明はかかる点に鑑み、クリッピン
グ境界上にある頂点を含む多角形に対しても、同一の頂
点を重複して出力せず、無駄な処理の増加を招かないよ
うなクリッピング回路を提供することを目的とする。

課題を解決するための手段 本発明は、前記の問題点を解決するために、入力され
た多角形の頂点の座標を保持する頂点レジスタと、クリ
ッピング領域を表す境界面または境界線の方程式を保持
する境界レジスタと、前記の境界レジスタの出力する境
界面または境界線の方程式と前記の入力された頂点の座
標とを入力としてその座標をもつ頂点が前記の境界面ま
たは境界線に対して内側に存在するか外側に存在するか
もしくは境界面または境界線の上に存在するかを判定す
る内外判定回路と、前記の頂点レジスタの保持する頂点
系列における１つ前の頂点に対して前記の内外判定回路
によって判定された結果を保持する内外判定結果レジス
タと、前記の内外判定回路の出力する第１の内外判定結
果と前記の内外判定結果レジスタに保持された第２の内
外判定結果を入力としクリッピングの結果として出力す
べき座標を判定するクリッピング判定回路と、前記の入
力された頂点の座標と前記の頂点レジスタの保持する座
標を２つの端点とする線分と前記の境界レジスタの出力
する境界面または境界線の方程式を入力として前記の線
分と前記の境界面または境界線との交点の座標を前記の
クリッピング判定回路の出力に応じて計算する交点計算
回路と、前記の入力された頂点の座標と前記の交点計算
回路の出力する交点の座標から０ないし２つの座標を前
記のクリッピング判定回路の出力に応じて選択し順序付
けて出力する頂点出力回路とを具備することを特徴とす
るクリッピング回路である。

作用 本発明は前記の構成により、入力された多角形の頂点
の座標と、クリッピング境界との位置関係を内外判定回
路によって、内側か外側かまたは境界上にあるかのいず
れであるか判定し、この判定結果と先に入力され頂点レ
ジスタに保持されている１つ前の頂点に対して得られ、
内外判定結果レジスタに保持されている内外判定結果と
を用いて、クリッピング判定回路によってこれら隣接す
る２つの頂点を結ぶ線分と前記のクリッピング境界との
位置関係を判定し、必要に応じて交点計算回路で算出さ
れた前記の線分とクリッピング境界との交点の座標と、
入力された頂点の座標を、それぞれの位置関係に応じて
頂点出力回路を介して出力することにより、クリッピン
グの処理を行う。

実施例 第１図は、本発明のクリッピング回路の一実施例の構
成を示すブロック図である。第１図において101は順次
に入力される多角形の頂点の座標を、102は頂点レジス
タを、103は境界レジスタを、104は境界レジスタ103の
出力するクリッピング境界の方程式を、105は内外判定
回路を、106は内外判定回路105の出力する内外判定結果
を、107は内外判定結果105を保持する内外判定結果レジ
スタを、108は内外判定結果レジスタ107に保持されてい
る、頂点系列における１つ前の頂点に対する内外判定結
果を、109はクリッピング判定回路を、110はクリッピン
グ判定回路109の出力する制御信号を、111は頂点レジス
タ102に保持されている。頂点系列における１つ前の頂
点の座標を、112は交点計算回路を、113は交点計算回路
112の出力する交点の座標を、114は頂点出力回路を、11
5はクリッピング処理の結果として出力される頂点の座
標を示している。以上のように構成された本発明のクリ
ッピング回路の動作を以下に説明する。まず、多角形を
構成する頂点の座標が図示しない外部回路から順次１座
標ずつ入力される。入力された頂点の座標は頂点レジス
タ102に格納されるとともに、内外判定回路105、交点計
算回路112および頂点出力回路114に供給される。境界レ
ジスタ103は少なくとも現在処理の対象となっているク
リッピング境界を含む複数のクリッピング境界の方程式
を保持しており、現在処理の対象となっているクリッピ
ング境界の方程式104を出力し内外判定回路105および交
点計算回路112に供給する。内外判定回路105は入力され
た頂点の座標101と、クリッピング境界の方程式から幾
何学における公知の技術を用いて、その頂点とクリッピ
ング境界との位置関係を判定する。位置関係には第２図
の（ａ）〜（Ｃ）に示す３通りの場合がある。第２図
で、201はクリッピング境界を、202はクリッピング境界
201に対する内側を、203はクリッピング境界201に対す
る外側を、204は入力された頂点をそれぞれ示してい
る。但し、クリッピング境界201は内側202およ外側203
のいずれにも含まれないものとする。第２図の（ａ）は
頂点204がクリッピング境界201に対して内側202にある
場合を、（ｂ）は頂点204がクリッピング境界201上にあ
る場合を、（Ｃ）は頂点204がクリッピング境界201に対
して外側203にある場合を、それぞれ示している。内外
判定回路105は前記の３通りのいずれであるかを示す信
号を判定結果106として出力し、内外判定結果レジスタ1
07に格納するとともに、クリッピング判定回路109に供
給する。クリッピング判定回路109は、入力された頂点1
01に対する内外判定結果106と、内外判定結果レジスタ1
07に保持されている。多角形の頂点系列において１つ前
の頂点に対する内外判定結果108を用いて、現在入力さ
れた頂点とその１つ前の頂点とを結ぶ線分と、クリッピ
ング境界との位置関係を判定し、クリッピング処理の結
果として出力すべき頂点の座標を決定し、頂点出力回路
114に対して制御信号110を供給する。このとき、前記の
線分とクリッピング境界との交点を出力すべきであると
判断した場合には、交点計算回路112に対しても交点113
の計算を指示する制御信号110を供給する。第３図の
（ａ）〜（ｉ）に前記の線分とクリッピング境界との９
通りのすべての位置関係を示す。第３図において、201
〜203は、第２図と同一のものである。301は１つ前に入
力された頂点Ｐを、302は現在入力されている頂点Ｑ
を、303は線分PQとクリッピング境界201との交点Ｒを、
それぞれ示している。第４図に、第３図の各々の場合に
対応して、入力された頂点の座標101に対する内外判定
結果106と、内外判定結果レジスタ107に保持されている
多角形の頂点系列において１つ前の頂点対する内外判定
結果108と、クリッピング判定回路109において出力すべ
きであると判定される頂点の関係を示す。第４図に示し
た関係は、前記の第９図に示した関係を完全に包含して
いるため、クリッピング境界上にない頂点については、
従来のクリッピング回路と同様に処理できることは保証
される。交点計算回路112は、入力された頂点の座標101
と、頂点レジスタ102に保持されている多角形の頂点系
列において１つ前の頂点の座標111と、境界レジスタ103
に保持されている。現在処理の対象となっているクリッ
ピング境界の方程式104を用いて、現在入力された頂点
とその１つ前の頂点とを結ぶ線分とクリッピング境界と
の交点の座標を、クリッピング判定回路109の判定結果
を示す制御信号110に応じて計算する。頂点出力回路114
は、クリッピング判定回路109の判定結果を示す制御信
号110に応じて（即ち第４図の関係に応じて）、交点計
算回路112で必要に応じて計算された交点の座標113と、
現在入力されている頂点の座標101から、０ないし２つ
の頂点の座標115を順序付けて出力する。前記の第10
図、第12図、および第15図の各々に示した多角形に対し
て、本発明のクリッピング回路を用いてクリッピング処
理を行った場合の処理の流れを一覧にして、それぞれ第
５図、第６図、および第７図に示す。前記の第10図の例
の多角形に対しては、４つの頂点の列B,E,F,Aが、第12
図の例の多角形に対しては３つの頂点の列B,D,Aが、第1
5図の例の多角形に対しては４つの頂点のB,C,D,Aが、そ
れぞれ頂点が重複することなく出力される。なお、本発
明の実施例の構成を示す際に用いた第１図では、各構成
要素（回路およびレジスタ）を独立したハードウエアと
して個別に表しているが、通常のCPU（中央処理装置）
を用いて、各回路の機能をソフトウエアによって実現し
てもよく、各レジスタを通常のメモリ装置やCPUのレジ
スタによって実現しても、本発明のクリッピング回路を
構成できることを付け加えておく。

発明の効果 以上に説明してきたように、本発明によれば、クリッ
ピング境界上にある頂点を含むような多角形が入力され
たときでも、同一の頂点を重複して出力することがない
ようなクリッピング回路が実現でき、無駄な処理の増大
を防ぐことができ、処理速度の向上が図れる。

【図面の簡単な説明】

第１図は本発明のクリッピング回路の一実施例の構成を
示すブロック図、第２図は１つの頂点とクリッピング境
界の位置関係図、第３図は２つの頂点を結ぶ線分とクリ
ッピング境界の位置関係図、第４図は第３図に示す位置
関係と出力すべき頂点の関係を示す対応図、第５図は第
10図に示す多角形の例に対して本発明のクリッピング回
路を用いて処理した場合の処理の流れを示す図、第６図
は第12図に示す多角形の例に対して本発明のクリッピン
グ回路を用いて処理した場合の処理の流れを示す図、第
７図は第15図に示す多角形の例に対して本発明のクリッ
ピング回路を用いて処理した場合の処理の流れを示す
図、第８図は従来のクリッピング回路において用いてい
た線分とクリッピング境界の位置関係図、第９図は第８
図に示す位置関係と出力すべき頂点の関係を示す対応
図、第10図はクリッピングの対象となる多角形の例を示
す平面図、第11図は第10図に示す多角形の例に対して従
来のクリッピング回路を用いて処理した場合の処理の流
れを示す図、第12図はクリッピングの対象となる多角形
の例を示す平面図、第13図は第12図に示す多角形の例に
対して、クリッピング境界そのものが内側に含まれると
仮定した上で、従来のクリッピング回路を用いて処理し
た場合の処理の流れを示す図、第14図は第12図に示す多
角形の例に対して、クリッピング境界そのものが外側に
含まれると仮定した上で、従来のクリッピング回路を用
いて処理した場合の処理の流れを示す図、第15図はクリ
ッピングの対象となる多角形の例を示す平面図、第16図
は第15図に示す多角形の例に対して従来のクリッピング
回路を用いて処理した場合の処理の流れを示す図であ
る。 101……入力された頂点の座標、102……頂点レジスタ、
103……境界レジスタ、105……内外判定結果、107……
内外判定結果レジスタ、109……クリッピング判定回
路、112……交点計算回路、114……頂点出力回路。

Claims (1)

【特許請求の範囲】
1. 【請求項１】入力された多角形の頂点の座標を保持する
   頂点レジスタと、クリッピング領域を表す境界面または
   境界線の方程式を保持する境界レジスタと、前記の境界
   レジスタの出力する境界面または境界線の方程式と前記
   の入力された頂点の座標とを入力としてその座標をもつ
   頂点が前記の境界面または境界線に対して内側に存在す
   るか外側に存在するかもしくは境界面または境界線の上
   に存在するかを判定する内外判定回路と、前記の頂点レ
   ジスタの保持する頂点系列における１つ前の頂点に対し
   て前記の内外判定回路によって判定された結果を保持す
   る内外判定結果レジスタと、前記の内外判定回路の出力
   する第１の内外判定結果と前記の内外判定結果レジスタ
   に保持された第２の内外判定結果を入力としクリッピン
   グの結果として出力すべき座標を判定するクリッピング
   判定回路と、前記の入力された頂点の座標と前記の頂点
   レジスタの保持する座標を２つの端点とする線分と前記
   の境界レジスタの出力する境界面または境界線の方程式
   を入力として前記の線分と前記の境界面または境界線と
   の交点の座標を前記クリッピング判定回路の出力に応じ
   て計算する交点計算回路と、前記の入力された頂点の座
   標と前記の交点計算回路の出力する交点の座標から０な
   いし２つの座標を前記のクリッピング判定回路の出力に
   応じて選択し順序付けて出力する頂点出力回路とを具備
   することを特徴とするクリッピング回路。