6.2 図形描画（グラフィックス）

計算の理論
6.2
59
図形描画（グラフィックス）
計算機の魅力のひとつにその詳細（高解像度）なグラフィックス描画機能がある．この節ではそ
の図形描画の一端に触れていこう．前半で直線描画のアルゴリズム、後半は自己再帰呼び出しを繰
り返してサイズを変えた相似図形の反復描画で表すフラクタル図形のアルゴリズムとそのアルゴリ
ズムで作り出される図形を鑑賞しよう．
6.2.1
グラフィックス描画のキャンバス
以下の解説においてはグラフィックス画像を表す画面を 2 次元の配列（plane[0..n-1][0..n-1]）
と見立てる．各要素は 1 画素（ピクセル）のデータを保持するとする．画像は簡単のためモノクロ
グレー階調（0∼255）とする．0 が黒、255 が白となりその中間階調を 1 から 254 で灰黒色から灰
白色の移り変わりを表現する．
int plane[xwidth][ywidth] ;
の 2 次元配列でサイズ xwidth × ywidth のグラフィック画面にイメージを記録していくことにする．
カラー階調にするには同サイズの 2 次元配列を 3 つ別名で用意しそれぞれに赤（R）、緑（G）、
それと青（B）の階調（やはりそれぞれ 0∼255）を対応するピクセルの色として保持させなければ
ならない．グレー表現に較べて 3 倍仕事量が増えたことになるがアルゴリズム的にはグレー階調で
のグラフィック操作を単に 3 原色それぞれに独立で行っているにすぎない．
ここではグレー階調のみを取り上げてアルゴリズムを議論していくことにする．さらにもうひと
つ座標軸が左向き x 軸に対して下向き y 軸となっていることに注意が必要である．グラフィック画
素ひとつひとつの値、画素を指定する x、y 座標などすべて整数値であることに注意．グラフィッ
クス計算は（途中の計算は除いて）すべて整数単位でアクセスされる．画素の概念、座標系などを
図 14 にまとめておいた．
x
ywidth
(0,0)
y
xwidth
図 14: グラフィックス画素の概念と座標系
計算の理論
60
直線描画；ブレーゼンハムのアルゴリズム
6.2.2
直線（始点 (x1,y1) から終点 (x2,y2) まで）が plane[][] 上に描かれる場合
1. 直線の式（y = αx + β ）を計算しそれをもとに x を x1 から x2 まで動かしながら対応する y
の値を計算する、
2. (x,y) が直線の要素となるので plane[x][y]=grey として描画する
というのが基本である．しかし 2 つの画素の中間領域に対応直線が通過したときどちらの画素の y
値を選ぶかという選択方法にアルゴリズムがある（ブレーゼンハム；Bresenham のアルゴリズム）．
直線の条件でいろいろ場合分けしていくのだがここでは ∆x = x2 − x1 > 0, ∆y = y2 − y1 > 0
として 0 < ∆y/∆x < 1 の場合を取り出してそのアルゴリズムを議論しよう．つまり直線は傾き 45
°以下で x と y の正方向に伸びている場合である．こう直線を限定してアルゴリズムを議論しても
一般性を失わない．α = ∆y/∆x より各 x1 + i での直線式の y の値と画素の y 座標の値と差 δi は
前 x1 + (i − 1) でのずれ δi−1 より計算できて図 15 からわかるように以下の関係式となっている；
δi = {
δi−1 + α
(δi−1 ≤ 0.5)
δi−1 + α − 1 (δi−1 > 0.5)
これで δi と 0.5 を比較し大きければ大きい y 値を持つ画素（図でいうと下側）が、また 0.5 より小
さければ小さい y 値を持つ画素（図中上側）が選択されることになる．この選択を整数のみで行う
ことにより高速化を計る．それにはこの式の両辺に 2∆x をかけて新たに δi′ = 2∆xδi としてやると
上式の関係式は以下の式となる．
δi′ = {
′
′
δi−1
+ 2∆y
(δi−1
≤ ∆x)
′
δi−1 + 2∆y − 2∆x (δi−1 > ∆x)
そこで δi′ ≤ ∆x なら大きい y、そうでなければ小さい y 値を持つ画素が直線の所属点として選ばれ
ることになる．ここでは δi′ の計算、比較ともに整数のみの計算となり高速化がはかられることに
なる．
(x1,y1)
x1+1
δ1
y1+1
x1+2
x1+3
x1+4
δ1
+ =δ
α 2
δ2
+ =δ3
α−1
δ3
+ =δ
α 4
y1+2
δ1<0.5 δ2>0.5 δ3<0.5
図 15: ブレーゼンハムの直線描画アルゴリズム：ここでは格子の交差点が 1 画素に対応している
計算の理論
61
以下に直線の向き、傾きのあらゆる場合を考慮した直線描画関数 drawline(x1,y1,x2,y2,grey)
をちょっと長いが完全形を載せる．始点が (x1,y1)、終点が (x2,y2) で色をグレイ階調 grey（0
∼255）で指定する．
int drawline(int x1,int y1,int x2,int y2,int grey) {
int frac ;
int xNext,yNext,xStep,yStep,xDelta,yDelta ;
int xself,yself,xEnd,yEnd ;
xself=x1 ;
yself=y1 ;
xEnd=x2 ;
yEnd=y2 ;
xNext=xself ;
yNext=yself ;
xDelta=xEnd-xself ;
yDelta=yEnd-yself ;
xStep=1 ;
yStep=1 ;
if(xDelta < 0) xStep =-1 ;
if(yDelta < 0) yStep =-1 ;
xDelta=xDelta*2 ;
yDelta=yDelta*2 ;
if(xDelta<0) xDelta =-xDelta ;
if(yDelta<0) yDelta =-yDelta ;
plane[xNext][yNext]=grey ;
// --A-if(xDelta > yDelta) {
frac=yDelta*2 -xDelta ;
while(xNext != xEnd) {
if(frac >= 0) {
yNext = yNext + yStep ;
frac = frac - xDelta ;
}
xNext = xNext + xStep ;
frac = frac + yDelta ;
plane[xNext][yNext] = grey ;
}
// --B-} else {
frac = xDelta*2-yDelta ;
while(yNext != yEnd) {
if(frac >= 0) {
xNext = xNext+xStep ;
frac = frac-yDelta ;
}
yNext = yNext + yStep ;
frac = frac+xDelta ;
plane[xNext][yNext] = grey ;
計算の理論
62
}
}
}
上のプログラムでは直線の傾きで場合わけしてあるがコメント--A--と--B--間を考えると上記
のアルゴリズムの議論が応用できる状況となる．
1. 変数 frac には δi′ − 2∆y の値が入る、初期値では δ1′ = 2∆y であるので最初は
frac=yDelta*2-xDelta、つまり frac=δ1′ − ∆x である、
2. そしてこの変数 frac と 0 との大小関係を比較する、これで x1 + 1 での y の適正値を判断し
ている、
3. もし frac>0 であれば y は大きい値をとり、そうでなければ y は小さい座標値をとることに
なる、frac>0 の場合、frac は −2∆y の修整を受けることになる（δi′ の 2 番目の式より）、
4. さらに 2 回以降（x1 + i, i > 1）は各回 frac は 2∆y （=yDelta）ごと足されていき項目 2
に戻り同様の比較を x1 + i が x2 になるまで受けていくことになる．
6.2.3
コッホ曲線
この節のコッホ曲線、次のドラゴン、それと枯れ枝はすべてプログラム的に同じほぼ同じ形を
とっている．線分をある一定のレシピで部分的に変形する．それらの関数呼び出しには線分の始
点、終点の座標とともに整数 n が伴う．n ≥ 1 であれば最初に与えられた線分からレシピにした
がった変形を n 回繰り返し（n が大きくなるほど変形が増えるので最終的に描画される図は複雑な
ものとなる）、その度に n − 1 で再び自己再帰の形で自分自身を呼び出す．このとき線分の始点、
終点は変形分割された線分のそれらが指定される．最終的に n = 0 となった時点で前節で述べた
drawline を用いた線描画がなされる．
コッホ曲線は線分を 3 等分し (端を点 1、点 2、3 等分した点を C,D とする）．図 16 を参照のこと.
そのうち中心の線分（CD）を長さ 2 倍で引き延ばしその中点 T を 1C、CT で角度 30 °の 2 等辺三
角形となすようにとり、折り曲げた形をつくることを基本変形とするものである（n = 0 での基本変
形）．さらにこの変形でできた 4 つの線分 1C,CT,TD,D2 も同じ変形を行う、ということを繰り返し
てできた曲線を一般的にコッホ（Koch）曲線と呼ぶ．図 17 から 20 までに n = 0, 1, 2, 4 のコッホ曲線
を載せた．このコッホ変形を行う基本関数を linepick(int n,int x1,int y1,int x2,int y2)
としてそのプログラムをその関数の呼び方とともに以下に掲げてある．始点 (x1,y1) から (x2,y2)
までの線分に対して上で述べた変形を n 回適用するものである．n = 0 で 1 回の適用で実際の描画
がなされる．n ≥ 1 で呼び出されると 1 回の呼び出しで線分は 4 本増加するのでその 4 本に同じ変
形、すなわち linepick を再帰的に呼び出し同じ変形が繰り返される．
このプログラムでは今まで扱わなかった数学関数（atan、cos．sin）を使用している．これら
は数学関数ライブラリに登録されているのでプログラマはいつでも自由に自分のプログラムで利
用できる．sqrt も同様である．atan は θ = arctan(t) の計算を、cos、sin はそれぞれ cos(theta)
および sin(θ) を計算するものである．ここで θ の単位はラディアンであることに注意（90 °=π/2
ラディアン）．
計算の理論
63
プログラム中 if (dx>0) とあり\verbdx—の正負によりつまみ出し角度の与え方が異なってい
る．これは新たに頂点 T をつまみ出す方向を常に反時計周りに統一させようとしての配慮である．
プログラム冒頭部にある#define は文字列の置き換えを定義するものである．PI6 が以後プログ
ラム部に現れた場合、その文字列は 0.52359878 つまり π/6 と置き換えることを意味する．次行
の SQRT3 も同じである．
この関数 linepick が
Δ
1
C
D
2
D
2
T
3
Δ/√
π/6
1
C
図 16: コッホ曲線の第 1 歩：線分のつまみ上げと引き伸ばし
#define PI6 0.52359878
#define SQRT3 1.73205081
int linepick(int n,int x1,int y1,int x2,int y2) {
int dx,dy ;
int xc,yc,xd,yd,xt,yt ;
float phi,r ;
xc=(2*x1+x2)/3
yc=(2*y1+y2)/3
xd=(x1+2*x2)/3
yd=(y1+2*y2)/3
;
;
;
;
dx= x2-x1;
dy=-y2+y1 ;
r=sqrt(dx*dx+dy*dy)/SQRT3 ;
if(dx>0) {
phi=atan((float)dy/(float)dx)+PI6 ;
xt=x1+(int)(r*cos(phi)) ;
yt=y1-(int)(r*sin(phi)) ;
} else {
phi=atan((float)dy/(float)dx)-PI6 ;
xt=x2+(int)(r*cos(phi)) ;
yt=y2-(int)(r*sin(phi)) ;
}
計算の理論
64
図 17: コッホ曲線 n=0
図 18: コッホ曲線 n=1
図 19: コッホ曲線 n=2
図 20: コッホ曲線 n=4
if(n==0) {
drawline(x1,y1,xc,yc,10) ;
drawline(xc,yc,xt,yt,10) ;
drawline(xt,yt,xd,yd,10) ;
drawline(xd,yd,x2,y2,10) ;
} else {
linepick(n-1,x1,y1,xc,yc) ;
linepick(n-1,xc,yc,xt,yt) ;
linepick(n-1,xt,yt,xd,yd) ;
linepick(n-1,xd,yd,x2,y2) ;
}
}
この関数の呼び出し例を以下に載せてある．始点（1）(100,200) と終点（2）(700,200)（水平
線）から n 回（この値はプログラム中、あるいは開始時に正の整数で指定しておく）のコッホ曲線
生成アルゴリズムを適用するものである．
//グラフィックライブラリの初期化
// n に適当な数指定
linepick(n,100,200,700,200) ;
//画像描出し
6.2.4
ドラゴン曲線
ドラゴン曲線は基本的に線分 12 の中点を始点 1 から 2 に向かって右方向に 90 °に折り曲げるも
のである．折り曲げると 2 本の線分 1M と 2M が出来る．どちらも 1 から M、2 から M に右方向
にそれらの線分を直角に折り曲げる．その繰り返しをするものである（図 21 参照）．その役割を
担う関数が以下にのせた linefold(int n,int x1,int y1,int x2,int y2) である．引き続いて
計算の理論
65
1
2
1
2
n=0
M
1
2
n=1
M
図 21: ドラゴン曲線の第 1 歩：線分の折り曲げ変形
やはりこの関数の呼び出しもリストしてある．この関数では n ≥ 1 で自分自身を呼び出す際、1 回
の変形で線は 2 本増殖するのみなので再帰は 2 回のみに止まっている．コッホ曲線のそれよりアル
ゴリズムが簡便な分、プログラムも短めになっている．
図 23 から図 25 で見るように n の値が小さいと単純な図形も大きくなるにしたがってとても複
雑なドラゴンの形に変形していくのがよく観察できる．
#define PI4 0.78539816
int linefold(int n,int x1,int y1,int x2,int y2) {
int xwidth,ywidth ;
int dx,dy ;
int xm,ym,rlx,rly ;
dx=x2-x1 ;
dy=-y2+y1 ;
xm=(dx+dy)/2+x1 ;
ym=(dx+dy)/2+y2 ;
if(n==0) {
drawline(x1,y1,xm,ym,10) ;
drawline(x2,y2,xm,ym,10) ;
} else {
linefold(n-1,x1,y1,xm,ym) ;
linefold(n-1,x2,y2,xm,ym) ;
}
}
//グラフィックライブラリの初期化
// n に適当な数指定
linefold(n,100,200,700,200) ;
//画像描出し
計算の理論
66
図 22: ドラゴン曲線 n=1
図 23: ドラゴン曲線 n=4
図 24: ドラゴン曲線 n=10
図 25: ドラゴン曲線 n=16
計算の理論
67
2
d
π/4
2
π/6
e
c
1
1
図 26: 枯れ枝の第 1 歩：線分の枝分かれ
6.2.5
枯れ枝
今までの例ではコッホ曲線ではアルゴリズム 1 回適用で 1 線分が 4 本に、ドラゴン曲線で 2 本に分
かれた．この枯れ枝では 1 本の線分から新たに 3 本の線分が生成されることになる．しかし図 26 か
ら分かるように 3 本のうち中心の線分はもともとあったものの部分である．新たに加わった線分は横
枝の 2 本だけであるが、オリジナルの線分は 2 つの部分、幹の部分（ここは変形を受けず）と枝の部
分に分割され、枝の部分はその後変形の対象となるのでやはり 3 本の線分が新たにこのアルゴリズム
で生成されると考えてよいだろう．枝が 3 分岐する仕方はこの図 26 を参考にしてほしい．このアル
ゴリズムを具体化した関数が以下に掲げた linebranch(int n,int x1,int y1,int x2,int y2)
である．
このアルゴリズムではいくつかの枝振りを表す指標となるパラメータをあらかじめ関数の中で指
定しておく．それらは
変数名
意味合い
設定値
STRATIO
中心線の幹の割合
0.25
BRARATIO
PI4
PI6
左右の枝の中心枝との長さ比
0.6
45 °
30 °
左枝と中心枝の角度
右枝と中心枝の角度
これらを適当に変更しながらよりリアルな枝振りを再現させると興味深いだろう．
#define PI4 0.78539816
#define PI6 0.52359878
#define SQRT3 1.73205081
int linebranch(int n,int x1,int y1,int x2,int y2) {
int dx,dy,sign ;
int xc,yc,xd,yd,xe,ye ;
float phi1,phi2,r,Lcenter,Lbranch,Lstem ;
float STRATIO=0.25,BRRATIO=0.6 ;
dx= x2-x1;
dy=-y2+y1 ;
r=sqrt(dx*dx+dy*dy) ;
phi1=atan((float)dy/(float)dx)+PI4 ;
phi2=atan((float)dy/(float)dx)-PI6 ;
計算の理論
Lcenter=r*(1.0-STRATIO) ;
Lbranch=BRRATIO*Lcenter ;
if(dx>=0) sign=1 ;
else sign=-1 ;
xc=x1+STRATIO*(float)dx ;
yc=y1-STRATIO*(float)dy ;
xd=xc+sign*(int)(Lbranch*cos(phi1))
yd=yc-sign*(int)(Lbranch*sin(phi1))
xe=xc+sign*(int)(Lbranch*cos(phi2))
ye=yc-sign*(int)(Lbranch*sin(phi2))
68
;
;
;
;
drawline(x1,y1,xc,yc,10) ;
if(n==0) {
drawline(xc,yc,x2,y2,10) ;
drawline(xc,yc,xd,yd,10) ;
drawline(xc,yc,xe,ye,10) ;
} else {
linebranch(n-1,xc,yc,x2,y2) ;
linebranch(n-1,xc,yc,xd,yd) ;
linebranch(n-1,xc,yc,xe,ye) ;
}
}
//グラフィックライブラリの初期化
// n に適当な数指定
linebranch(n,200,800,700,200) ;
//画像描出し
6.2.6
シェルピンスキー曲線
ここでのシェルピンスキー曲線はやや簡易版のものであることに注意．実際は四角を描く際各
コーナーの面取りがしてあり図形の構造としては複雑である．しかしトポロジーとしてはここで描
き出すものと結局同じものとなる．したがって図形描画の手数は増えるが本質的なアルゴリズムは
以下に示したもので十分であると考えられる．
この曲線を描く方法は今までの 3 つの方法とずいぶん異なるものとなっている．今までのものは
線分を与えそれをあるアルゴリズムで分割あるいは生成して n ≥ 1 であれば再びそのアルゴリズ
ムを呼び出し分割・生成を繰り返す、といったものであった．
ここでのアルゴリズムはそれとは違いまず基本線分単位の長さをあらかじめ与えておく（dist）.
また同時に現在の向かっている方向（東西南北）
（dir）から左に曲がって一歩進む、あるいは右に曲
がって一歩進めというのが基本的なアルゴリズムである．そのスッテプで自分の位置 (xnow,ynow)
が更新されていくものである．基本は以下に示した関数 right() と left() である．こえらの関
数は入力パラメータと出力値を明示されていない．関数の戻り値は void（何もない）であり入力
変数も () と空白である．実は right() や left() というアクションがとられるたびに向かう方向
（dir）、自分の現在位置 (xnow,ynow) が変化されそれらが更新されていくのがプログラムより明
計算の理論
69
図 27: 枯れ枝 n=0
図 28: 枯れ枝 n=1
図 29: 枯れ枝 n=4
図 30: 枯れ枝 n=7
計算の理論
70
らかなのだがそれらの入出力が明示されない．それらは関数定義の外で変数定義されている．この
領域は大局的領域という部分でこの領域で変数定義されたらこれらの変数はどの関数でも参照でき
書き換えも可能になるという大変便利なものである、と同時に大きな危険も伴う．この危険が故に
実は筆者はこの方法を極力避けようとプログラムするものである．しかしより安全な方法を採用し
ようとすると新たな枠組みを取り入れ、その解説も加えなければならないのでここではこの大局
（グローバル；global）変数の利用で甘んじておいたところである．閑話休題．以下にこれらの関
数を掲げた．
int dir,dist ;
int xnow,ynow ;
//dir= 0 -> +x, 1 -> -x, 2 -> +y, 3 -> -y
void right() {
if(dir==0) {
drawline(xnow,ynow,xnow,ynow+dist,10)
ynow=ynow+dist ;
dir=2 ;
} else if (dir==1) {
drawline(xnow,ynow,xnow,ynow-dist,10)
ynow=ynow-dist ;
dir=3 ;
} else if (dir==2) {
drawline(xnow,ynow,xnow-dist,ynow,10)
xnow=xnow-dist ;
dir=1 ;
} else if (dir==3) {
drawline(xnow,ynow,xnow+dist,ynow,10)
xnow=xnow+dist ;
dir=0 ;
}
return ;
}
void left() {
if(dir==0) {
drawline(xnow,ynow,xnow,ynow-dist,10)
ynow=ynow-dist ;
dir=3 ;
} else if(dir==1) {
drawline(xnow,ynow,xnow,ynow+dist,10)
ynow=ynow+dist ;
dir=2 ;
} else if(dir==2) {
drawline(xnow,ynow,xnow+dist,ynow,10)
xnow=xnow+dist ;
dir=0 ;
} else if(dir==3) {
drawline(xnow,ynow,xnow-dist,ynow,10)
xnow=xnow-dist ;
dir=1 ;
}
return ;
}
;
;
;
;
;
;
;
;
計算の理論
71
さてこの right() と left() を用いてさらなるアクションを定義する．それは以下の zig(int n)
と zag(int n) である．それらのアクションはどのようなものか以下を見て理解して欲しい．こ
こでも再帰呼び出しが行われていて n = 1 のとき実際のアクションがとられているが、それ以外
では zig(n/2) あるいは zag(n/2) が規則的、不規則的に呼び出されている．この下にある実際に
zig() 関数を呼び出しているところに注目してほしい．以下のプログラムリストの関数 main() で
ある．この zig(n) を 2 回続けることによってこのシェルピンスキー曲線が完成されるのである．
n = 4 と n = 16 の時のこの main() の描く曲線を図 31 および?? に示した．どうしてこのような
図形になるのか思いめぐらしてほしい．またこれらの図形は一筆書きによって描かれていることに
も注意してほしい．
void zig(int n) {
if(n==1) {
left() ;
left() ;
} else {
zig(n/2) ;
zag(n/2) ;
zig(n/2) ;
zag(n/2) ;
}
}
void zag(int n) {
if(n==1) {
right() ;
right() ;
left() ;
} else {
zag(n/2) ;
zag(n/2) ;
zig(n/2) ;
zag(n/2) ;
}
}
int main() {
//グラフィックライブラリの初期化
// n に適当な数指定
//初期設定（方向（dir）x の負方向、ステップ（dist）および初期位置）
dir= 1 ;
dist=32 ;
xnow=64 ;
ynow=64 ;
//続けて 2 回 zig(n) の呼び出し
zig(n) ;
zig(n) ;
//画像描出し
}
問題 5 今北に向いている（dir=2、つまり y の正方向）として zig(1) と zag(2) を続けて行った
場合の図形を描画せよ（dist の値は解答用紙に収まるよう適当に設定せよ）．
計算の理論
図 31: シェルピンスキー曲線 n=4
72
図 32: シェルピンスキー曲線 n=16
計算の理論
73
問題 6 zig(2)、zig(2) の場合図を描け．初期方向は東西南北どこでもよい．
6.2.7
参考文献
この節をまとめるにあたって以下の Web ページ、書籍にを参考にした．
1. 石立 喬著「再帰プログラムによるフラクタル図形の描画」http://codezine.jp/article/detail/73
（2005）
2. A.K. デュードニー、足立暁生訳、
「コンピュータサイエンスの旅 チューリングオムニバス」
電機大出版局（旧版）（1993）
計算の理論
74