×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。

 007-08  前へ←  ホームへ  →次へ  007-09(2)

No.007 - 09-1  円描画(1)


ミッチェナー(Michener)、Bresenham(ブレゼンハム)等のアルゴリズムを用いた円描画の紹介と解説です。
古くからあるアルゴリズムらしいのですが、あんまり解説してるサイトがないので当サイトで一通りやります。


1.円の基本

円の一般的な公式は

ですが、
ミッチェナー(Michener)のアルゴリズムでは

の状態にして使います。
ピタゴラスって天才だな〜と思う今日この頃。


2.デジタル円の描画を行う前に

最初に言っておきますが
デジタル円はアスペクト比の関係上、真円には近づきません。どうあがいても。

ピクセル自体が縦長なので円もちょっと縦長です。
アスペクト比の修正は各アプリケーションで行うほうがいいので、
今回はR * R ピクセルの正方形と考えてアルゴリズムを組みます。
ご了承ください。


3.いろいろなデジタル円の描画

デジタル円の描画のアルゴリズムは2、3種類があります。

ブレゼンハム(Bresenham)、ミッチェナー(Michener)が一般的です。
OpenFMIというサイトの中のページで
"Comparing Circle Drawing Algorithms"という C のソース
http://openfmi.net/snippet/detail.php?type=snippet&id=8
が紹介されています。
同一コード内にブレゼンハム、ミッチェナー等の関数も用意されており、ソースとしては完璧です。

ちなみにこのソースの中にダブル・サブストラクション(2重減算)というアルゴリズムもありますが、
これは、ブレゼンハムの中点を用いた円描画のようです。
("second-order differences"や"midpoint circle algorithm"といった名前で洋サイト検索すると吉です。)


4.基本的なデジタル円の描画の考え方

描画時にひとつひとつ
x = cosθ
y = sinθ

としても正確な値がでますが、
デジタル円では1ピクセル単位で整数値が得られればいいので

「ある一点から描き始めて、
 1ピクセルずつ移動判定しながら描いていこう」

というのが考え方の基本です。

高速なデジタル円描画のアルゴリズムではすべてこの考え方が使われます

ではどのようにして移動判定するのか、ということですが、

一度数学の実数グラフに戻って考えます。
右図を見て下さい。

真円の場合、x が整数値のとき y は整数にはほとんどなりません。
デジタル円では xy も整数でなければならないので
右図で yPQどちらかの点を選択する事になります。

ではPQどちらの点が近いのでしょうか。
単純に y 座標をそれぞれの r までの距離(==sinθ) と比較しても求められますが、
sinθを使っては意味がありませんので別の方法をとります。


線分OPOQr を比較するには
Py座標を=nQのy座標を=n-1、としたと き
OP 2 = x 2 + n 2
OQ 2 = x 2 + (n-1) 2
と、 r 2  を比較します。
PQどちらのほうがより近いか調べるだけなので
2乗した状態で比較しても結果でます。

OP 2 > r 2
OQ 2 < r 2
なので
D = ( OP 2 - r 2 ) - ( r 2 - OQ 2 )
                    == OP 2 + OQ 2 - 2r 2
としてD>=0、D<0で判定します。

これが考え方の基本です。
ただホントに毎回2乗して比較してたら高速演算にならないので各アルゴリズムで工夫がなされています。




5.旧版のブレゼンハム(Bresenham)の円描画


円の4分の1を考えてください。
わかりやすく0〜90度の範囲で見てみましょう。

まず開始点を決めます。
一番カンタンな座標(0, r)にします。
とりあえずこの座標を描画することは確定なのでこの1点を描画します。

次に描画するのは
範囲が0〜90度なので
1つ上のピクセルか、1つ左上のピクセルか、1つ左のピクセル
になります。
どのピクセルを描画すると円に近くなるか考えます。
x 2 + y 2 -r 2 =0
から、それぞれ
a = (x+1) 2 + y 2 -r 2
b = (x+1) 2 + (y-1) 2 -r 2
c = x 2 + (y-1) 2 -r 2

となるので、このa, b, c中で一番0に近い値の座標を選びます。




ここで全部計算すると大変なので
それぞれの絶対値差を計算して比較します。

ここで各a, b, c の値を
T = x 2 + y 2 -r 2
と置き換えてやれば

a = T + 2x+1
b = T + 2x- 2y+2
c = T - 2y+1


bを使ってa, c を表すと
a = b +2y-1
c = b -2x-1
・・・@



範囲が0〜90度なので
if (abs(a) >  abs(b)) y--;
if (abs(c) >= abs(b)) x++;

比較演算 >>= の差はなるべく円の外側のピクセルを選択するように
使い分けています。

またa, b, c は円の内側なら負値、外側なら正値となるので
曲線がa とbの間を通るときa>0、b<0、c<0
曲線がb とcの間を通るときa>0、b>0、c<0

従って
if ( a > -b) y--;   // 曲線が b とcの間を通るときも成り立つ
if (-c >= b) x++;   // 曲線がa とbの間を通るときも成り立つ

これを@の式とあわせて
if ( (b +2y-1) > -b) y--; ・・・A
if (-(b -2x-1) >= b) x++; ・・・B

計算すると
A = b+2y-1>-b
    = 2b>-2y+1
    = b>y-1/2


B =  -(b -2x-1) >= b
     =  -b +2x+1>= b
     =  -2b >= -2x-1
     =  2b <= 2x+1
     = b <= x +1/2


A、B、ともにb, x, y は整数値なので1/2の加減算は
比較に影響しないので

A→ if ( b>y) y--; ・・・C
B→ if ( b<=x ) x++;


b初期値は、スタート地点が(0, r) なので
b0 = (x+1) 2 + (y-1) 2 -r 2
   = (0+1) 2 + (r-1) 2 -r 2
    = 1 + r 2 -2r+1-r 2
      = 2 -2r

です。

曲線がa とbの間を通るとき
a>0
b<0
c<0
曲線がb とcの間を通るとき
a>0
b>0
c<0




ブレゼンハム(Bresenham) 円描画のアルゴリズム (旧版)
void BresenhamCircle (HDC hdc, LONG radius, POINT center, COLORREF col){
    LONG cx, cy, d;

    cx = 0;
    cy = radius;
    d = 2 - 2 * radius;

    // 開始点の描画
    SetPixel (hdc, cx + center.x, cy + center.y, col);  //  (0, R);
    SetPixel (hdc, cx + center.x, -cy + center.y, col); //  (0, -R);
    SetPixel (hdc, cy + center.x, cx + center.y, col);  //  (R, 0);
    SetPixel (hdc, -cy + center.x, cx + center.y, col); //  (-R, 0);

    while (1) {
        if (d > -cy) {
            --cy;
            d += 1 - 2 * cy;
        }

        if (d <= cx) {
            ++cx;
            d += 1 + 2 * cx;
        }

        if (!cy) return;    // 描画終了

        // 描画
        SetPixel (hdc, cx + center.x, cy + center.y, col);      // 0〜90度の間
        SetPixel (hdc, -cx + center.x, cy + center.y, col);     // 90〜180度の間
        SetPixel (hdc, -cx + center.x, -cy + center.y, col);    // 180〜270度の間
        SetPixel (hdc, cx + center.x, -cy + center.y, col);     // 270〜360度の間
    }
}





6.ミッチェナー(Michener)の円描画

海外のサイトではこの「ミッチェナー」のアルゴリズムが「ブレゼンハム」として紹介しているところがあります。
筆者も「信頼のできる文献」をもってないので詳細は不明です。
仕方が無いので、とりあえずここは「ミッチェナー」で通します。


ミッチェナーの円描画は
45〜90度の8分円を基軸に描画します。

0〜45、90〜360度は
それぞれ水平線、垂直線、45度線を軸にした
「鏡像」で描きます。

まず開始点を(0 ,r) と決めて、
先に描画します。

次に描画する位置は
座標が45〜90度の間なので
右図でいうと a か b になります。
a = (x+1) 2 + y 2 -r 2
b = (x+1) 2 + (y-1) 2 -r 2
から各a, b, の値を
T = x 2 + y 2 -r 2
と置き換えて計算します。
a = T + 2x+1
b = T + 2x- 2y+2


a+b は上述
D = ( OP 2 - r 2 ) - ( r 2 - OQ 2 )
になるので

D = a + b = 2T + 4x - 2y +3
として
D <0 なら   a の方が小さく真円に近いの でピクセル a を描画、
D >=0 なら b の方が小さく真円に近いのでピクセル b を描画します

右図を見て下さい。
ここで次に判定するピクセルですが、
D <0 なら c+d を判定し、
D >=0 なら d+e を判定することになります。







c = (x+2) 2 + y 2 -r 2
      = T + 4x+4

d = (x+2) 2 + (y-1) 2 -r 2
      = T + 4x +4 - 2y +1
     = T + 4x -2y +5


e = (x+2) 2 + (y-2) 2 -r 2
    = T + 4x +4 - 4y +4
     = T + 4x -2y +8


なので、
DH = c+dDL=d+e と置くと

DH = c+d = 2T + 8x -2y +9
DL = d+e = 2T + 8x -6y +13


a>0
b<0です



ここでDH、DLのそれぞれのDとの差分を考えます。
DH = D + 〜
DL = D + 〜
とすれば演算が高速になるからです。

DH - D  = 4x +6
DL - D = 4x - 4y +10

1.
2.
3.
4.
D (== a+b)
判定する
D<0 のとき D に DHを代入する
   (DH== c+d == D+4x+6)
D+=4x+6
1にもどる
D>=0 のとき D に DLを代入して、y--;
   (DL== d+e == D+4x-4y+10)
D+=4x-4y+10
こういう流れになります。

D初期値は、スタート地点が(0, r) なので
T0 = x 2 + y 2 -r 2
   = 0 2 + r 2 -r 2
   = 0

より、
D0 = a+b
    = 2T + 4x - 2y +3
    = 0 + 4*0 -2*r +3
    = 3 -2*r

です。



ミッチェナー (Michener) の 円描画
void MiechenerCircle (HDC hdc, LONG radius, POINT center, COLORREF col){
    LONG cx, cy, d;

    d = 3 - 2 * radius;
    cy = radius;

    // 開始点の描画
    SetPixel (hdc, center.x, radius + center.y, col);   // point (0, R);
    SetPixel (hdc, center.x, -radius + center.y, col);  // point (0, -R);
    SetPixel (hdc, radius + center.x, center.y, col);   // point (R, 0);
    SetPixel (hdc, -radius + center.x, center.y, col);  // point (-R, 0);

    for (cx = 0; cx <= cy; cx++) {
        if (d < 0)  d += 6  + 4 * cx;
        else        d += 10 + 4 * cx - 4 * cy--;

        // 描画
        SetPixel (hdc,  cy + center.x,  cx + center.y, col);        // 0-45     度の間
        SetPixel (hdc,  cx + center.x,  cy + center.y, col);        // 45-90    度の間
        SetPixel (hdc, -cx + center.x,  cy + center.y, col);        // 90-135   度の間
        SetPixel (hdc, -cy + center.x,  cx + center.y, col);        // 135-180  度の間
        SetPixel (hdc, -cy + center.x, -cx + center.y, col);        // 180-225  度の間
        SetPixel (hdc, -cx + center.x, -cy + center.y, col);        // 225-270  度の間
        SetPixel (hdc,  cx + center.x, -cy + center.y, col);        // 270-315  度の間
        SetPixel (hdc,  cy + center.x, -cx + center.y, col);        // 315-360  度の間
    }
}







7.ブレゼンハム(Bresenham)の中点分岐を用いた円描画


上述の P と Q の間の中点が、
r より大きければ、P点を選択します。
r より小さければ、Q点を選択します。

中点の2乗は
M 2 = (x+1) 2 + (y-1/2) 2
なので

判定する基準値は
D = M 2 -r 2
です。

拡大

D <0 なら、M<rr真ん中(==M)より高 い位置にあるので、P点を選択、
D >=0  なら M>=<rr真ん中(= =M)より低い位置にあるので、Q点を選択します


T = x 2 + y 2 -r 2
と置き換えて計算すると

D = M 2  - r 2
    = (x+1) 2 + (y-1/2) 2 -r 2
    = x 2 +2x+1+ y 2 -y +1/4-r 2
      = T +2x -y +1+/4

です。

D <0 のときの次の判定値を DH
D >=0  のときの次の判定値を DL とします
するとそれぞれ
DH = MH 2  - r 2
    = (x+2) 2 + (y-1/2) 2 -r 2
    = x 2 +4x+4+ y 2 -y +1/4-r 2
      = T +4x -y +4 +1/4

DL = ML 2  - r 2
    = (x+2) 2 + (y-3/2) 2 -r 2
    = x 2 +4x+4+ y 2 -y +9/4-r 2
      = T +4x -y +6 +1/4


ここでDH、DLのそれぞれのDとの差分を考えます。
DH = D + 〜
DL = D + 〜
とすれば演算が高速になるからです。

DH - D  = 2x +3
DL - D = 2x -2y +5

ここのポイントは1/4がきれい消えている点です。

1.
2.
3.
4.
D (== M 2  - r 2 )
を判定する
D<0 のとき D に DHを代入する
   (DH== D+2x +3)
D+=2x +3
1にもどる
D>=0 のとき D に DLを代入して、y--;
   (DL== D+2x - 2y +5)
D+=2x -2y +5
こういう流れになります。
このへんのやり方はミッチェナーと同じです。

D初期値は、スタート地点が(0, r) なので
T0 = x 2 + y 2 -r 2
   = 0 2 + r 2 -r 2
   = 0

より、
D0 = T +2x -y +1+/4
    = 0 + 2*0 -r +1+1/4
    = 1 -r +1/4

です。

ルーチン上、x, y, r は全て整数で、
比較演算、代入演算においても全て整数で間に合っており
初期値 D0 の小数部分である 1/4 は結果にまったく影響しないので、
1/4 は切り捨ててしまいます。

したがって 初期値 D0
D0 = 1 -r


さてこれで一応メインループの完成です。
中点分岐を用いた円描画のメインループ (第一段階)
   d   = 1 - radius;
    for (x = 0; x <= y; x++) {
        if (d < 0)  {
             d += 2x +3;
        }
        else {
             d += 2x -2y +5;
             y--;
        }
    }
ですが、まだ終わりではありません


今度はD の増分に注目です。
D<0 のとき DH・・・ D+=2x +3
D>=0 のとき DL・・・   D+=2x -2y +5

それぞれの増分を囘h、囘l とすると
囘h = 2x +3
囘l  = 2x -2y +5
D<0 のとき DH・・・ D+=囘h
D>=0 のとき DL・・・ D+=囘l



囘h は x が1増えると 2増えます。y の増減は関係しません。
囘h = 2(x+1) +3 // ・・・x が1増えたとき


囘l  は x が1増えると 2増えます。y が1減っても 2増えます。
囘l  = 2(x+1) -2(y-1) +5 // ・・・x が1増えて、y が1減ったとき
       = 2x +2 -2y +2 +5
       = 2x -2y +9


また、囘h、囘l それぞれの初期値は、スタート地点(0, r) より、

囘h = 2x +3
       = 3

囘l  = 2x -2y +5
       = 5 -2r



さあメインループの完成です。
中点分岐を用いた円描画のメインループ (最終段階)
    d   = 1 - radius;
    dH  = 3;
    dD  = 5 - 2 * radius;
    for (x = 0; x <= y; x++) {
        if (d < 0) {
            d   += dH;
            dH  += 2;
            dD  += 2;
        }
        else{
            d   += dD;
            dH  += 2;
            dD  += 4;
            y--;
    }




で実際の関数がこれ。
ブレゼンハム  中点分岐を用いた円描画アルゴリズム

void MidpointCircle (HDC hdc, LONG radius, POINT center, COLORREF col){
    LONG cx, cy, d, dH, dD;

    d   = 1 - radius;
    dH  = 3;
    dD  = 5 - 2 * radius;
    cy  = radius;

    for (cx = 0; cx <= cy; cx++) {
        if (d < 0) {
            d   += dH;
            dH  += 2;
            dD  += 2;
        }
        else{
            d   += dD;
            dH  += 2;
            dD  += 4;
            --cy;
        }

        // 描画
        SetPixel (hdc, cy + center.x, cx + center.y, col);      // 0-45     度の間
        SetPixel (hdc, cx + center.x, cy + center.y, col);      // 45-90    度の間
        SetPixel (hdc, -cx + center.x, cy + center.y, col);     // 90-135   度の間
        SetPixel (hdc, -cy + center.x, cx + center.y, col);     // 135-180  度の間
        SetPixel (hdc, -cy + center.x, -cx + center.y, col);    // 180-225  度の間
        SetPixel (hdc, -cx + center.x, -cy + center.y, col);    // 225-270  度の間
        SetPixel (hdc, cx + center.x, -cy + center.y, col);     // 270-315  度の間
        SetPixel (hdc, cy + center.x, -cx + center.y, col);     // 315-360  度の間
    }
}








8.まとめ


今回はアルゴリズムの紹介だけで終わりますが、
実は上記のブレゼンハム とミッチェナー、実は少し問題があります。

1.引数に半径を指定しているので、奇数の直径を指定出来ない。
    大きな円ならかまわないのですが、デジタル円は小さな円の場合が少なくないので。

2.実は精度が良くない。
    アルゴリズムの見かけ上は「完璧」なんですが、実際きちんと
      x 2 + y 2 -r 2 =0  に一番近い座標を選択するコードと比べると、ピッタリ重ならないのです。

続きは次回。





サンプル解説 

下記サンプルは "gt_img_09.cpp" ファ イル1つだけです。
単純に円描画アルゴリズムを比較するためのソースです。
OpenFMIというサイトの"Comparing Circle Drawing Algorithms"という C のソースを
参考にしています。
日本語訳後、修正して、さらにウチのオリジナル関数も加えています。


関数解説

1.ReallySimpleCircle() はシンプル円描画(小数切捨て)です。
2.ReallySimpleCircle2() はシンプル円描画(値のより近いピクセルを選択する方式)
3.Win32APIGDICircle() Win32API GDI 円描画
4.BresenhamCircle() はブレゼンハム(Bresenham)の円描画 (旧版)
5.MiechenerCircle() はミッチェナー(Miechener) の円描画
6.MidpointCircle() はブレゼンハム(Bresenham)の中点分岐の円描画


6つの関数のうち
1.ReallySimpleCircle() シンプル円描画(小数切捨て)
5.MiechenerCircle()  ミッチェナー
6.MidpointCircle()    ブレゼンハム(中点)
の3つの関数が同一円を描きます。
ミッチェナーやブレゼンハムがなぜ、小数切捨てのシンプル円になるのか筆者にはわかりません。

2.ReallySimpleCircle2() は当サイト・オリジナル関数です。
基本に忠実なので、他より少しだけ精度が高いんですが、実行速度の遅い関数です。







gt_img_09_1.cpp

#include <windows.h>
#include <math.h>

// シンプル円描画(小数切捨て方式)
void ReallySimpleCircle (HDC hdc, LONG radius, POINT center, COLORREF col){
    LONG    cx = 0, cy;
    double  xLimit = sqrt ((double) (radius * radius) / 2);     // r*r*√2 → 45°

    while (cx++ <= xLimit){
        cy = (LONG) floor (sqrt (radius * radius - cx * cx));
        SetPixel (hdc, cx + center.x, cy + center.y, col);      // 45-90    度の間
        SetPixel (hdc, cx + center.x, -cy + center.y, col);     // 270-315  度の間
        SetPixel (hdc, -cx + center.x, cy + center.y, col);     // 90-135   度の間
        SetPixel (hdc, -cx + center.x, -cy + center.y, col);    // 225-270  度の間
        SetPixel (hdc, cy + center.x, cx + center.y, col);      // 0-45     度の間
        SetPixel (hdc, cy + center.x, -cx + center.y, col);     // 315-360  度の間
        SetPixel (hdc, -cy + center.x, cx + center.y, col);     // 135-180  度の間
        SetPixel (hdc, -cy + center.x, -cx + center.y, col);    // 180-225  度の間
    }
}

// シンプル円描画2(値のより近いピクセルを選択する方式)
void ReallySimpleCircle2 (HDC hdc, LONG radius, POINT center, COLORREF col){
    LONG    cx = 0, cy=radius;
    double  xLimit =  sqrt ((double) (radius * radius) / 2);    // 45度→r*√2
    double d1, d2;

    for (cx=0; cx <= xLimit ; cx++)
    {
        d1 = (cx * cx+cy*cy) - radius * radius;
        d2 = (cx * cx+(cy-1)*(cy-1)) - radius * radius;
        if (abs(d1)>abs(d2)) cy--;
        SetPixel (hdc, cx + center.x, cy + center.y, col);      // 45-90    度の間
        SetPixel (hdc, cx + center.x, -cy + center.y, col);     // 270-315  度の間
        SetPixel (hdc, -cx + center.x, cy + center.y, col);     // 90-135   度の間
        SetPixel (hdc, -cx + center.x, -cy + center.y, col);    // 225-270  度の間
        SetPixel (hdc, cy + center.x, cx + center.y, col);      // 0-45     度の間
        SetPixel (hdc, cy + center.x, -cx + center.y, col);     // 315-360  度の間
        SetPixel (hdc, -cy + center.x, cx + center.y, col);     // 135-180  度の間
        SetPixel (hdc, -cy + center.x, -cx + center.y, col);    // 180-225  度の間
    }
}

// Win32API GDI 円描画
void Win32APIGDICircle (HDC hdc, LONG radius, POINT center){
    SelectObject (hdc, GetStockObject (NULL_BRUSH));
    Ellipse (hdc,
        center.x - radius,
        center.y + radius,
        center.x + radius,
        center.y - radius);
}

// ブレゼンハム(Bresenham)の円描画 (旧版)
void BresenhamCircle (HDC hdc, LONG radius, POINT center, COLORREF col){
    LONG cx, cy, d;

    cx = 0;
    cy = radius;
    d = 2 - 2 * radius;

    // 初期座標をあらかじめ描画する
    SetPixel (hdc, cx + center.x, cy + center.y, col);  // 座標 (0, R);
    SetPixel (hdc, cx + center.x, -cy + center.y, col); // 座標 (0, -R);
    SetPixel (hdc, cy + center.x, cx + center.y, col);  // 座標 (R, 0);
    SetPixel (hdc, -cy + center.x, cx + center.y, col); // 座標 (-R, 0);
   
    while (1){
        if (d > -cy){
            --cy;
            d += 1 - 2 * cy;
        }

        if (d <= cx){
            ++cx;
            d += 1 + 2 * cx;
        }

        if (!cy) return;    // 描画終了

        // 描画
        SetPixel (hdc, cx + center.x, cy + center.y, col);      // 0-90     度の間
        SetPixel (hdc, -cx + center.x, cy + center.y, col);     // 90-180   度の間
        SetPixel (hdc, -cx + center.x, -cy + center.y, col);    // 180-270  度の間
        SetPixel (hdc, cx + center.x, -cy + center.y, col);     // 270-360  度の間
    }
}

// ミッチェナー(Miechener) の円描画
void MiechenerCircle (HDC hdc, LONG radius, POINT center, COLORREF col){
    LONG cx, cy, d;

    d = 3 - 2 * radius;
    cy = radius;

    // 初期座標をあらかじめ描画する
    SetPixel (hdc, center.x, radius + center.y, col);   // 座標 (0, R);
    SetPixel (hdc, center.x, -radius + center.y, col);  // 座標 (0, -R);
    SetPixel (hdc, radius + center.x, center.y, col);   // 座標 (R, 0);
    SetPixel (hdc, -radius + center.x, center.y, col);  // 座標 (-R, 0);

    for (cx = 0; cx <= cy; cx++){
        if (d >= 0) {
            d += 10 + 4 * cx - 4 * cy;
            cy--;
        }
        else {
            d += 6 + 4 * cx;
        }

        // 描画
        SetPixel (hdc, cy + center.x, cx + center.y, col);      // 0-45     度の間
        SetPixel (hdc, cx + center.x, cy + center.y, col);      // 45-90    度の間
        SetPixel (hdc, -cx + center.x, cy + center.y, col);     // 90-135   度の間
        SetPixel (hdc, -cy + center.x, cx + center.y, col);     // 135-180  度の間
        SetPixel (hdc, -cy + center.x, -cx + center.y, col);    // 180-225  度の間
        SetPixel (hdc, -cx + center.x, -cy + center.y, col);    // 225-270  度の間
        SetPixel (hdc, cx + center.x, -cy + center.y, col);     // 270-315  度の間
        SetPixel (hdc, cy + center.x, -cx + center.y, col);     // 315-360  度の間
    }
}

// ブレゼンハム(Bresenham)の中点分岐の円描画
void MidpointCircle (HDC hdc, LONG radius, POINT center, COLORREF col){
    LONG cx, cy, d, dH, dD;

    d   = 1 - radius;
    dH  = 3;
    dD  = 5 - 2 * radius;
    cy  = radius;

    // drawing the circle:
    for (cx = 0; cx <= cy; cx++){
        if (d < 0){
            d   += dH;
            dH  += 2;
            dD  += 2;
        }
        else{
            d   += dD;
            dH  += 2;
            dD  += 4;
            --cy;
        }

        // 描画
        SetPixel (hdc, cy + center.x, cx + center.y, col);      // 0-45     度の間
        SetPixel (hdc, cx + center.x, cy + center.y, col);      // 45-90    度の間
        SetPixel (hdc, -cx + center.x, cy + center.y, col);     // 90-135   度の間
        SetPixel (hdc, -cy + center.x, cx + center.y, col);     // 135-180  度の間
        SetPixel (hdc, -cy + center.x, -cx + center.y, col);    // 180-225  度の間
        SetPixel (hdc, -cx + center.x, -cy + center.y, col);    // 225-270  度の間
        SetPixel (hdc, cx + center.x, -cy + center.y, col);     // 270-315  度の間
        SetPixel (hdc, cy + center.x, -cx + center.y, col);     // 315-360  度の間
    }
}

LRESULT CALLBACK WndProc (HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam){
    RECT rc;
    static POINT    center;
    HDC             hdc;
    PAINTSTRUCT     ps;

    int RADIUS = 100;

    switch (message){
    case WM_SIZE:
        InvalidateRect(hwnd, NULL, TRUE);
        break;

    case WM_PAINT:
        GetClientRect(hwnd, &rc);

        center.x = rc.right/ 2;
        center.y = rc.bottom/ 2;

        hdc = BeginPaint (hwnd, &ps);

        // 中心線描画(水平)
        MoveToEx (hdc, 0, center.y, NULL);
        LineTo (hdc, rc.right, center.y);

        // 中心線描画(垂直)
        MoveToEx (hdc, center.x, 0, NULL);
        LineTo (hdc, center.x, rc.bottom);

        // シンプル円描画(小数切捨て)
        ReallySimpleCircle (hdc, RADIUS, center, RGB(255, 0, 0));

        // シンプル円描画(値のより近いピクセルを選択する方式)
        center.x += 20;
        ReallySimpleCircle2 (hdc, RADIUS, center, RGB(0, 255, 0));

        // Win32API GDI 円描画
        center.x += 20;
        Win32APIGDICircle (hdc, RADIUS, center);

        // ブレゼンハム(Bresenham)の円描画 (旧版)
        center.x += 20;
        BresenhamCircle (hdc, RADIUS, center, RGB(255, 0, 255));

        // ミッチェナー(Miechener) の円描画
        center.x += 20;
        MiechenerCircle (hdc, RADIUS, center, RGB(0, 0, 255));

        // ブレゼンハム(Bresenham)の中点分岐の円描画
        center.x += 20;
        MidpointCircle (hdc, RADIUS, center, RGB(0, 100, 100));

        EndPaint (hwnd, &ps);

        break;

    case WM_DESTROY:
        PostQuitMessage (0);
        break;
    }

    return DefWindowProc (hwnd, message, wParam, lParam);
}

int WINAPI WinMain (HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int iCmdShow){
    static  TCHAR szAppName[] = TEXT ("CircleDemoApp");
    HWND        hwnd;
    MSG         msg;
    WNDCLASS    wndclass;

    wndclass.style          = CS_HREDRAW | CS_VREDRAW;
    wndclass.lpfnWndProc    = WndProc;
    wndclass.cbClsExtra     = 0;
    wndclass.cbWndExtra     = 0;
    wndclass.hInstance      = hInstance;
    wndclass.hIcon          = LoadIcon (NULL, IDI_APPLICATION);
    wndclass.hCursor        = LoadCursor (NULL, IDC_ARROW);
    wndclass.hbrBackground  = (HBRUSH) GetStockObject (WHITE_BRUSH);
    wndclass.lpszMenuName   = NULL;
    wndclass.lpszClassName  = szAppName;

    if (!RegisterClass (&wndclass)){
         MessageBox (NULL, TEXT ("This program requires Windows NT!"), szAppName, MB_ICONERROR) ;
         return 0 ;
    }

    hwnd = CreateWindow (szAppName, TEXT("円描画の比較(Comparing Circle Drawings)"),   
                 WS_OVERLAPPEDWINDOW,
                 CW_USEDEFAULT, CW_USEDEFAULT, 500, 300,   
                 NULL, NULL, hInstance, NULL);         

    ShowWindow (hwnd, iCmdShow);
    UpdateWindow (hwnd);

    while (GetMessage (&msg, NULL, 0, 0)){
        TranslateMessage (&msg);
        DispatchMessage (&msg);
    }

    return msg.wParam;
}



 007-08  前へ←  ホームへ  →次へ  007-09(2)