第四章 高速描画
4.2 直線のクリップ
4.2.1 従来のクリップ方式
２次元クリップ処理で最も有名な方法は, Cohen‑Sutherland(CS)の手法[ 1 , 1 2 ]である.
Xl Xr
Yb
Yt
line1 line2
line3
line4 line5
S1
E1
S2
E2
S3
E3
E4
E5
S4
S5
1001 1000 1010
0001
0101 0100 0110
0010 0000
図4-7 Cohen-Sutherlandのクリップ方法
CS 法では, 図 4‑7 に示すように２次元デバイス座標系において, クリップ枠を構成する４本の直線 をX = Xl, X = Xr, Y =Yb及びY =Ytとし, 直線の両端点（X,Y）に対して, それぞれ次の符号
（ABCD）を求める.
Yt
Y ≤ なら A=0, そうでなければ A=1 Yb
Y ≥ なら B=0, そうでなければ B=1 Xr
X ≤ なら C=0, そうでなければ C=1
すると, クリップ枠を構成する４本の直線により９つの領域に分割された２次元空間の各領域に対 し, 図 4‑7 に示す符号が得られる. 左端の符号Ａ＝１は対象となる点がY =Ytよりも上側にあること を, 次の符号Ｂ＝１は対象となる点がY =Ybよりも下側にあることを, その次の符号Ｃ＝１は対象と なる点がX = Xrよりも右側にあることを, 最後の符号Ｄ＝１は対象となる点がX = Xlよりも左側 にあることを示す. 図 4‑7 には様々な直線を示しているが, 例えば line1 の両端点S1及びE1に対す
る符号は共に(0000)となり, line2 のS2に対する符号は(1001), E2に対する符号は(0101)となる.
従って, 次のことが言える.
＜クリップ処理アルゴリズム＞
1) 直線の両端点に対する符号が共に(0000)であれば, その直線はクリップ枠内に存在する.
2) 直線の両端点に対する符号のビット毎の AND が(0000)でなければ, その直線はクリップ枠を構 成する４本の直線の内, いずれかの直線よりもクリップ枠の外側に存在する.
3) 上記いずれにも当てはまらない場合は, 直線を分割してさらに詳しく調べる.
上記アルゴリズムの 3)において, さらに詳しく調べるための分割には様々な方法がある. 一つは Clipping Divider[12]であり, 直線の両端点の平均を取ることにより, 直線の中点を求めて直線を二 分割する. 二分割された各直線に対し, 上記アルゴリズムを適用して 1)あるいは 2)により, 直線が クリップ枠内に存在するか, あるいはクリップ枠外に存在するかが判断されるまで繰り返す. 直線の 中点を求める手法は非常に単純であり, ハードウェア化が容易であることから高速処理が期待でき る. しかしながら, この中点分割方法では直線のクリップ処理を行うためには数回の中点計算が必要 となり, 最終的に得られた直線の端点には数回の中点計算による誤差が蓄積されている. 一方, 直線 がクリップ処理により切断される点は直線とクリップ枠との交点であるため, 直線の中点を求める のではなく, 直接, クリップ枠との交点計算を行う方法が提案されている[2]. アルゴリズムのフロー チャートを図 4‑8 に示す.
図 4‑8 に示すアルゴリズムを用いれば, 直線とクリップ枠との交点を直接計算することにより, 計 算誤差の蓄積を抑えた精度の高いクリップ処理が実行できる. しかしながら, 図 4‑8 のアルゴリズム にも短所は存在する. 図のアルゴリズムに従えば, 直線がクリップインでもクリップアウトでもない 場合, 必ず直線の端点のどちらかはクリップ枠の外にあるため, その点を対象として, 直線がどのク リップ枠と交わるのかを判断しているが, 不必要な交点計算を伴うことがある. 例えば, 図 4‑7 の line3 では最初のループでX = Xlとの, 次のループでX = Xrとの交点を計算するが, 最終的には クリップアウトと判断され, 非表示となる. また, line5 の場合, アルゴリズムに従うと, X = Xl,
Xr
X = 及びY =Ybに対して３回の交点計算を行うが, 図より判断すればX = Xr及びY =Ybに対
して２回の交点計算でよいことが分かる.
そこで, 直線を構成する両端点の２次元座標系上における位置を考慮しながら, 最小の交点計算で 行えるクリップ処理方法が, 二人の Nicholl と Lee によって考案されている[13]. この方法では, クリ ップ枠を構成する４本の直線とクリップ対象となる直線との交点計算を行う前に, クリップ対象と なる直線の始点とクリップ枠のコーナー点とを結ぶ直線を考え, この直線とクリップ対象となる直 線とを比較することにより, クリップ対象となる直線がクリップ枠を構成する直線の内、どの直線と 交差しているのかを判断して最小限の交点計算でクリップ処理を実行している.
Yes No
Yes No
End Start
を計算 の符号
及び
の符号 0 1 1
0 C P C
P
?
1 0000
0 =C =
C クリップイン
直線を表示
?
1 0000
0ANDC ≠
C クリップアウト
直線を非表示 を入力
及び 直線の両端点P0 P1
?
0 ≠0000 C
を交換 と
と 1 0 1
0 C ,P P
C
Yes No
? 0000
0AND 0001≠
C Yes
とする 計算し
との交点を ,P0
X X = l
No
? 0000
0AND 0010≠
C Yes
とする 計算し
との交点を ,P0
X X = r
? 0000
0AND 0100≠
C Yes
とする 計算し
との交点を ,P0
Y Y = b
No No
とする 計算し
との交点を ,P0
Y Y = t
を計算 の符号 0
0 C
P
図4-8 クリップ処理フローチャート
0
Xl
X
rYb
Yt
Ａ Ｂ Ｃ
Ｄ Ｅ Ｆ
Ｇ Ｈ Ｉ
TL TR
BL BR
X Y
Xl Xr
Yb
Yt
TL TR
BL BR
S
L1
L2 L3
M1
M2 M3
図4-9 クリップ領域の分類 図4-10 領域Ａのクリップ処理
Nicholl‑Lee‑Nicholl の方法(NLN 法)では, まずクリップ枠を構成する４本の直線により分割され る９つの領域を図 4‑9 に示すように区分し, 図形の対称性を考慮することにより, 領域Ａ, Ｄ及びＥ のみを検討対象とする. 例えば, 領域Ｂは TL と BR を結ぶ直線(y=‑x)に対して領域Ｄと対称となって いるため, この直線に対して折り返すことにより領域Ｄに帰着することができる. また, 領域Ｃは図 形を反時計回りに 90 度回転することにより, 領域Ａに帰着できる. 領域ＡあるいはＤに帰着してク リップ処理を行った後, 逆の手順を辿ることにより元の図形に戻すことができる.
直線の始点座標を(X0,Y0), 終点座標を(X1,Y1)とすると, クリップ処理アルゴリズムは次の様に なる.
＜NLN 法のクリップアルゴリズム＞
1) X0 < Xlなら, LeftColumn へ.
2) X0 > Xrなら, 図形を 180 度回転させて LeftColumn で処理後, 逆方向に 180 度回転させて元に 戻す.
3) 上記いずれでもなければ CenterColumn へ.
＜LeftColumn＞
1) X1 <Xlなら, 直線はクリップアウト.
2) Y0 >Ytなら, TopLeftCorner へ.
3) Y0 <Ybなら, Y =(Yt +Yb)/2で折り返して TopLeftCorner で処理後, 逆方向に折り返して元 に戻す.
4) 上記いずれでもなければ LeftEdge（領域Ｄの処理ルーチン）へ.
＜TopLeftCorner＞
1) Y1 >Ytなら, クリップアウト.
2) 始点(S(X0,Y0))とクリップ枠の左上コーナー点(TL)とを結ぶ直線(図 4‑10 の L1)を考え, クリ ップ対象となる直線が L1 より下にあれば, つまり, (Yt −Y0)(X1−X0)>(Xl −X0)(Y1−Y0) であれば, LeftBottomRegion へ.
3) クリップ対象となる直線が L1 よりも上にあれば, y=‑x で折り返して LeftBottomRegion で処理 後, 逆手順で元に戻す.
＜LeftBottomRegion＞
1) Y1 >Ybなら, 図 4‑10 の L1 と L3 に挟まれる直線(M1 あるいは M2)となり, X0< Xlであるから Xl
X = との交点計算を行う. さらに, X1 >Xrを満足していればX = Xrとの交点計算も行 い, 対象となる直線はクリップインとなる.
2) X1 ≤Xrの場合は, 始点(S)とクリップ枠の左下コーナー点(BL)とを結ぶ直線(図 4‑10 の L3)を 考え, クリップ対象となる直線が L3 より下にあれば, つまり,
) )(
( ) )(
(Yb−Y0 X1−X0 > Xl −X0 Y1−Y0 であれば, 直線はクリップアウトとなる. クリップ対 象となる直線が L3 の上にある場合はX = Xlとの交点計算を行っており, Y1 >Yb か つ
Xr
X1 ≤ であるから, 対象となる直線はクリップインとなる.
3) Y1 >Ybでない場合は, Y1 ≤Ybが成り立つ. 従って, X1 < Xrであれば, Y =Ybとの交点計算 を行う. X1 ≥ Xrの場合は, 始点(S)とクリップ枠の右下コーナー点(BR)とを結ぶ直線(図 4‑10 の L2)を考える. 直線が L2 の下, つまり, (Yb−Y0)(X1−X0)>(Xr −X0)(Y1−Y0)であれば
Yb
Y = と, そうでなければX = Xrとの交点計算を行う. いずれの場合にも, X0 < Xlである から, X = Xlとの交点計算を行い, 対象となる直線はクリップインとなる.
Xl
Xr
Yb
Yt
TL TR
BL BR
S
L1
M1 L2 M2
Xl
Xr
Yb
Yt
TL TR
BL BR
S
L1 M1
M2
図4-11 領域Ｄのクリップ処理 図4-12 領域Ｅのクリップ処理
＜LeftEdge＞
1) X1 <Xlなら, 直線はクリップアウト.
2) Y1 <Ybなら, P2Bottom へ.
3) Y1 >Ytなら, Y =(Yt +Yb)/2で折り返して P2Bottom で処理後, 逆方向に折り返して元に戻す.
4) 上記いずれでもなければ, Yb <Y1 <Ytとなり, 図 4‑11 の M2 となる. 従って, X0 < Xlである からX = Xlとの交点計算を行うと共に, X1> XrであればX = Xrとの交点計算も行い, 対 象となる直線はクリップインとなる.
＜P2Bottom＞
1) 始点(S)とクリップ枠の左下コーナー点(BL)とを結ぶ直線(図 4‑11 の L1)を考え, クリップ対象 となる直線が L1 より下にあれば, つまり, (Yb −Y0)(X1−X0)>(Xl −X0)(Y1−Y0)であれば, 直線はクリップアウトとなる.
2) クリップ対象となる直線が L1 より上にある場合, <LeftEdge>の 2)より, Y1 <Ybが成り立って いるから, X1 <XrならY =Ybとの交点計算を行う. X1 ≥Xrの場合, 始点(S)とクリップ枠 の右下コーナー点(BR)とを結ぶ直線(図 4‑11 の L2)を考える. クリップ対象となる直線が L2 の 下, つまり, (Yb −Y0)(X1− X0)>(Xr −X0)(Y1−Y0)であればY =Ybと, L2 の上にあれば
Xr
X = との交点計算を行う. 1), 2)いずれの場合にも, X0 < XlであるからX = Xlとの交点 計算を行い, 対象となる直線はクリップインとなる.
＜CenterColumn＞
1) Y0 >Ytなら, 図形を 90 度反時計回りに回転させて, LeftEdge で処理後, 逆方向に回転させて 元に戻す.
2) Y0 <Ybなら, 図形を 90度時計回りに回転させて, LeftEdge で処理後, 逆方向に回転させて元 に戻す.
3) 上記いずれでもなければ Inside へ.
＜Inside＞
1) X1 <Xlなら, P2Left へ.
2) X1 >Xrなら, 図形を 180 度回転させて P2Left で処理後, 再び 180 度回転させて元に戻す.
3) 上記いずれでもない場合, Xl < X1 <Xrとなる. 従って, Y1 >YtならY =Ytと, Y1 <Ybなら Yb
Y = と交点計算を行う. どちらにも当てはまらない場合はYb <Y1 <Ytとなり, 交点計算の必 要はなく, 対象となる直線はクリップインとなる.
＜P2Left＞
1) Y1 >Ytなら, P2LeftTop へ.
2) Y1 <Ybなら, 図形を90度時計回りに回転させて P2LeftTop で処理後, 逆方向に回転させて元に 戻す.
3) 本ルーチンでは<Inside>の 1)より, X1 < Xlが成立しているから, 上記いずれでもない場合は Xl
X = との交点計算を行い, 対象となる直線はクリップインとなる.
＜P2LeftTop＞
1) 始点(S)とクリップ枠の左上コーナー点(TL)とを結ぶ直線(図 4‑12 の L1)を考える. クリップ対 象となる直線が L1 の下, つまり, (Yt −Y0)(X1−X0)>(Xl −X0)(Y1−Y0)であればX = Xl と, L1 の上であればY =Ytとの交点計算を行い, 対象となる直線はクリップインとなる.