※このページは説明画像にAPNGを使っています。 APNGがアニメーションするブラウザ(Firefox、GoogleChromeなど)で見てください。
ラスタ画像処理で中心(cx,cy)、半径rの円を描くのが目的です。 cx、cy、rは整数値です。
アルゴリズムを考えるにあたって、中心座標は円を構成する点を打つときに足し算するだけでずらせるので、ここでは省略します。 つまり、(cx,cy) = (0,0)の場合について考えます。
円をN等分してできる円弧は全て合同です。 縦・横・斜め45度で8等分した8分円の場合、ラスタ画像的にも合同になります。 このアルゴリズムでは8分円を描いて、円弧を対称にコピーすることで円全体を描きます。 この説明では、(r,0)から時計回りに45度までの円弧について考えます。
後述のサンプルコードで描いた8分円を拡大すると、図2のようになります。 半径9ピクセルの円の1部です。 白地に黒の円を描いた場合の画像です。 青い円は実際の円弧を表しています。 グラフ上の罫線は1ピクセル毎に引いてあり、交わったところはピクセルの中心を表しています。 罫線で出来た四角形がピクセルではないので注意。
まず、半径rは整数値なので(r,0)に黒い点をそのまま打ちます。 最初のこの点にはアンチエイリアスをしません。 それ以降、y=1、2、3、…の点を描いていきます。 その点にはアンチエイリアスの処理が入り、左右2ピクセルが1セットになっています。 このピクセルの組は、ピクセルの中心座標が本来の円弧をまたぐように配置されます。
ピクセルの色は本来の円弧からピクセルの中心まで水平に線を引いたときの長さを元に決定します。
本来の円弧から右側のピクセルまでの長さ(図4で赤く点滅しているところ、実数型のℓとおく)と左側のピクセルまでの長さ(図4で緑で点滅しているところ)の比で色を決めます。 隣り合ったピクセル間の距離は1なので、右側の長さが分かれば、左側の長さは(1-ℓ)で計算できます。 色の値の決め方は色々ありますが、ここではRGBはそのままでアルファ値の調節でアンチエイリアスをかけることにします。 アルファ値の最大値をALPHA_MAX、右側のピクセルの透明度をd、左側のピクセルの透明度を~dとすると、
となります。 このdを、取りうるrとyについて前もって計算し、テーブルD[r][y]を作っておきます。 ちなみにdは整数型です。 RGBAが1バイトずつの画像形式なら、ALPHA_MAXの値は2の8乗-1で255になります。 dの値の範囲は0〜255です。
ℓを求めるには三平方の定理を使います。
yの値を1、2、3、…と増加させていってytになったときのxtの値は、
xt = sqrt(r * r - yt * yt)
です。 xtは実数型で計算します。 左右のピクセルのx座標は切り捨て(floor)、切り上げ(ceil)で求めることができます。
肝心のℓの値は
ℓ = ceil(xt) - xt
になります。
これで各ピクセルの色は決まりました。 次に求めるのはy=1、2、3、…の時のx座標です。 上に出てきた式ceil(xt)とfloor(xt)は使いません。 なぜなら、xtを求めるためにかけ算と平方根sqrtを使っているからです。 円を描くたびにceil(xt)としていたら、せっかくテーブルD[r][y]を作るとき重い計算をしてあるのに、2度手間になってしまいます。
では、どうするか? yが1つ増えたとき、xの値がどうなるか見てみると、次の2パターンであることが分かります。
8分円について考えている限り、2ピクセル以上左にずれることはありません。 これは接線が45度までであることから分かります。 つまり、この2パターンのうちどちらかが判断できれば円が描けるということになります。
もう1度ℓに注目してみましょう。
ひとつ上のピクセルの組と次のピクセルの組を見て、x座標がそのままのとき、ℓは長くなっているのが分かります。 x座標が左に1つずれているときはℓは短くなっています。 例に使ったのが半径9ピクセルしかない円なので、「全部そうなのか?」と疑問に思うかもしれませんが、全部そうなります。 数学的にも証明されているようです。 つまり、ℓを比べれば次のx座標が決定できます。
そこで、もう1度dの式を思い出しましょう。
dは固定値ALPHA_MAXとℓをかけたものです。 ℓを比較する代わりにdを比較に使っても同じ結果になるのです。 色を決めるために作ったテーブルD[r][y]はx座標を決めるためにも使えます。 つまり、d = D[r][yt]、d_old = D[r][yt-1]とすると、
これを踏まえて、アンチエイリアスがかかった8分円を高速描画するアルゴリズムをjavaっぽいというか、javascriptっぽい表現で書くと次のようになります。 テーブルD[r][y]の初期化は、
for(int r=1; r <= RADIUS_MAX; r++)
{
for(int y=1; y <= ceil(r / sqrt(2) ); y++)
{
float xt = sqrt(r * r - y * y);
D[r][y] = ALPHA_MAX * (ceil(xt) - xt);
}
}
8分円の描画は、
int x = r;
int y = 0;
int d = 0;
int d_old = 0;
setPixel(x, y, color, ALPHA_MAX); // 軸上のピクセル
while(y < x - 1) // 内側のピクセルと45度の線を比べる
{
y++;
d = D[r][y];
if(d < d_old)
{
x--;
}
setPixel(x , y, color, ALPHA_MAX - d); // 外側のピクセル
setPixel(x - 1, y, color, d); // 内側のピクセル
d_old = d;
}
D[r][y]に必要な配列のサイズは、sqrt(2) * RADIUS_MAX * RADIUS_MAX / 4 になります。 半径rの8分円を書くとき、ytは1から r / sqrt(2) まで動きます。 なので、その分のdの配列サイズは r / sqrt(2) です。 それを0〜RADIUS_MAXまで定積分して sqrt(2) * RADIUS_MAX * RADIUS_MAX / 4 です。
D[r][y]の初期化で、rは1〜RADIUS_MAXまで設定されています。 実装するにあたって、半径0の場合は点になるのでsetPixelを呼ぶなどしてもいいかもしれません。 半径1の円はこのアルゴリズムどおりだとアンチエイリアスがかかりません。 ここもひと工夫で ... というか、これも全部の点をsetPixelした方が早いかも。 RADIUS_MAX以上の円は描くことができません。 重くはなりますが、D[r][y]を使うのではなく、描画ループ内でdを計算すればRADIUS_MAX以上の円描画にも対応できるでしょう。
描画部分で、setPixelの第4引数はアルファ値という設定です。 dの値は透明度なので、それをアルファ値に直すために外側のピクセルの値は ALPHA_MAX - d になっています。