整数演算のみで楕円を描く

前のエントリーでブレゼンハムのアルゴリズムを使って乗除を使わずに整数演算だけで円を描いてみたが、同じ原理を応用して、乗除を使わずに整数演算で楕円を描けないだろうか、と考えてみた。
・Javaのデモページへのリンク
・ソースコード

横幅が2a、縦幅が2bの楕円を考え、円の時と同様に、(a,0)や(0,b)から始めて、楕円の外側か内側かを判定してポインターを１ずつ縦横斜めに動かしながら、点を描いていく。第２象限～第４象限（90°～360°）はx,yの符号を変えながら第１象限（0°～90°）と同じ曲線を描けば良いので、第１象限だけを考える。

楕円の式は(x/a)2+(y/b)2=1であるが、整数演算のために割り算を避けて、b2x2+a2y2=a2b2とする。
まず、(x,y)=(a,0)からyを+1していって、xは(x,y)と(x-1,y)の中点が実際の楕円の外側になったら-1する（前のエントリー参照）。それを、xの動きがyの動きより大きくならない所、すなわち接線の傾きが135°になる所まで繰り返す。
次に、(x,y)=(0,b)からxを+1していって、同様に(x,y)と(x,y-1)の中点が楕円の外側になったら-1する、というのを、接線の傾きが135°になる所まで繰り返す。

式で書くと、(x,y)と(x-1,y)の中点は(x-1/2,y)なので、楕円の式に当てはめて、b2(x-1/2)2+a2y2 > a2b2なら中点が外側ということになる。E(x,y)を左辺－右辺とすると、E(a,0)=b2(-a+1/4)であり、E(x,y)はyが+1するとa2(2y+1)増え、xが-1するとb2(2x-2)減る。このE(x,y)の1回の増減分をそれぞれdEdy, dEdxと置くと、dEdyはyが+1すると2a2増え、dEdxはxが-1すると2b2減る。a2やb2は先に計算しておけばいいので、これで乗算を使わずに点を動かしていけることがわかる。
(x,y)と(x,y-1)の中点については、今の話のxとyを置き換えれば良い。

ということで書いたのが、サンプルコードのdraw1()である。コード上では上記のa,bはWx,Wyとしている。whileループの中では乗算は使っていない。
デモでは、赤線で描いているのがそれである。


さて、デモでは、比較のために青線でjava.awt.Graphics#drawArc()で楕円を描いて、その上にdraw1()で同じ大きさの楕円を赤線で描いているが、Java VMにも依るだろうが、青線と赤線が結構ずれている。原因として１つ間違いないのは、Ｘ軸、Ｙ軸をy=0, x=0に取って上下対象、左右対称にしているので、楕円の横幅や縦幅が偶数の時も奇数しか書いていないことだ。-1<=y<=1で書くと縦幅は3、-2<=y<=2で書くと縦幅は5である。実は前のエントリーのブレゼンハムの円描画のアルゴリズムでも偶数幅の円が描けないという同じ問題があるのだが、コードの簡潔さを重視して敢えて触れなかった（巷のサンプルコードでも大概無視してるし）。
今回はI/F仕様をjava.awt.Graphics#drawArc()に合わせて楕円のバウンディングボックス（外接矩形）のサイズを入力するようにしているので、それに見合った動作をさせたいものである。

横幅が偶数の場合、-a < x < a-1の範囲で描くとすると、横方向の対称軸はx=-0.5となる。x=0とx=-1とでY座標が同じになるのだが、対称軸がx=0の楕円のx=0.5, x=-0.5の時のyをX方向に-0.5ずらして描くと、yの最大点、最小点が無くなってしまう。実際、a,bをそのままにして(x,y)=(a-1/2,0)や(0,b-1/2)からプロットすると、楕円の上下左右の端が十分に膨らまず、少し四角に近くなってしまった。
そもそも、バウンディングボックスを中心に考えると、x=-a, x=a-1の点はそれぞれ必ずｘの最小点と最大点なのであり、中心軸がx=-0.5なので、X軸方向の半径がa-1/2の楕円を描かないといけないのであり、半径がaの円を平行移動する方針ではきれいな楕円にならないようだ。

そこで、曲線描画中は、楕円の横幅や縦幅が偶数の時は径を1/2減らして計算する方向で考えてみた。2aや2bが偶数の場合、楕円の式は(b-1/2)2(x-1/2)2+(a-1/2)2y2 = (a-1/2)2(b-1/2)2となり、(x,y)=(a-1,0)から始めてxを-1、yを+1していく時、(x-1,y)と(x,y)の中点が楕円の外側かどうかを判定する式は(b-1/2)2(x-1)2+(a-1/2)2y2-(a-1/2)2(b-1/2)2 > 0 となる。以下、左辺を４倍して考える。左辺の初期値はy=0なので(2b-1)2(-x+1/4)であり、yが+1すると(2a-1)2(2y+1)増え、xが-1すると(2b-1)2(2x-1)減る。以下略。結局、辛うじて乗算を使わずに点を動かしていける。

ということで書いたのが、サンプルコードのdraw2()である。コード上では上記の2a,2bがWx,Wyに対応する。
デモでは、比較のために青線でjava.awt.Graphics#drawArc()で楕円を描いて、その上にdraw2()で同じ大きさの楕円を緑色の線で描いている。JRE 6.0だと、緑線と青線はほとんど差が無い。

サンプルコードのdraw2()は上下左右端の丸さを重視してるので、小さな楕円ほど、drawArc()より丸くなる。

なお、前回と同様にソースコード中でBresenhamという名前を使っているが、もはやBresenhamとはほとんど関係がない。