Drawing Rotated Ellipses
Disclaimer: All of the algorithms here are not original with me. I have collected them from various internet web sites several years ago.
For those of you that have played my game "Polygon War" may have noticed that some of the objects use rotating ellipses. Anyone that is familiar with programming windows and the GDI realize there's no function to draw a rotated ellipse. That is unfortunate because drawing an ellipse oriented at any angle is really awesome but the solution is to create our own function. Instead of jumping right into it, let's start by drawing a line.
There's two different kind of computer graphics that I know about which is vector graphics and raster graphics. Back in the 80's there were a few arcade games that used vector graphics, such as asteroids, star wars, battle zone, etc..... The graphics were composed entirely of straight lines; just like the lines that you draw on paper using a pen and ruler. I've seen some computer systems in industrial companies use vector graphics and I think ocillascopes use vector graphics. But the vast majority of computers use raster graphics.
Raster graphics is just like graph paper. The image or picture is composed of rows and columns of individual squares called pixels. Each pixel represents a single unit of the image which has its own unique color. And each pixel represents a byte, or up to four bytes of computer memory called a double word, depending on the color depth of the image.
Of course the advantage of raster graphics is being able to draw solid detailed objects but it makes it tricky to program. Since raster graphics are composed of rows and columns of squares you can't draw an exact line or a curve shown in the following picture.
As you can see, a line in raster graphics is composed of many short line segments and squares which approximates a line. In low resolutions it looks very obvious but in high resolution a raster line will more closely resemble a real line. So how do you program a computer to draw lines in raster graphics? A college professor back in the early 60's came up with a slick algorithm called the Bresenham line drawing algorithm, named after him.
Here it is coded in PowerBasic.
SUB DrawLine (dl AS lines)
LOCAL a AS LONG, b AS LONG
LOCAL g AS LONG
LOCAL delt1 AS LONG, delt2 AS LONG
LOCAL nxt AS LONG, nyt AS LONG
LOCAL lp AS LONG
LOCAL adr AS LONG
LOCAL x AS LONG,y AS LONG,enx AS LONG,eny AS LONG,color AS DWORD
x=dl.x 'Prepare the line
y=dl.y
enx=dl.enx
eny=dl.eny
color=dl.color
IF eny<y THEN
a=y-eny
ELSE
a=eny-y
END IF
IF enx<x THEN
b=x-enx
ELSE
b=enx-x
END IF
IF a<=b THEN
g=2*a-b
delt1=2*(a-b)
delt2=2*a
ELSE
g=2*b-a
delt1=2*(b-a)
delt2=2*b
END IF
IF enx<x THEN
nxt=-1
ELSE
nxt=1
END IF
IF eny<y THEN
nyt=-1
ELSE
nyt=1
END IF
IF a<b THEN 'Draw the line.
FOR lp=0 TO b-1
IF g>0 THEN
g=g+delt1
x=x+nxt
y=y+nyt
ELSE
g=g+delt2
x=x+nxt
END IF
CALL pixel(x,y,color) 'Draw single pixel of the line.
NEXT lp
ELSE
FOR lp=0 TO a-1
IF g>0 THEN
g=g+delt1
y=y+nyt
x=x+nxt
ELSE
g=g+delt2
y=y+nyt
END IF
CALL pixel(x,y,color) 'Draw single pixel of the line.
NEXT lp
END IF
END SUB
As you can see, the line drawing Bresenham algorithm uses only integer addition and subtraction making it very fast. Now on to circles.
As with drawing lines using raster graphics, raster circles are represented as a number of short line segments and squares producing just an approximation of a true circle. Of course the bigger the circle, the better it represents a true circle. A very small circle will look more like a diamond.
In raster graphics the circle consists of eight symmetrical arcs (each arc is 45 degrees). So we need to only calculate the pixels for 1/8th of the circle which is 45 degrees which is done in the following program which makes the circle come out better anyway in raster graphics.
If you were to calculate all the pixels for the circle (which I tried), the circle wouldn't look perfectly symmetrical which is due to the finite resolution of raster graphics.
Here is the Bresenham algorithm for a circle coded in PowerBasic.
SUB circle (BYVAL cx AS LONG,BYVAL cy AS LONG,BYVAL radius AS DWORD, color AS DWORD)
LOCAL x AS LONG, y AS LONG, p AS LONG
LOCAL lp AS LONG
x=-1
y=radius
p=(5-radius*4)/4
WHILE x<=y
INCR x
IF p<0 THEN
p=p+2*x+1
ELSE
DECR y
p=p+2*(x-y)+1
END IF
SELECT CASE x
CASE 0
CALL pixel(cx,cy+y,color)
CALL pixel(cx,cy-y,color)
CALL pixel(cx+y,cy,color)
CALL pixel(cx-y,cy,color)
EXIT SELECT
CASE y
CALL pixel(cx+x,cy+y,color)
CALL pixel(cx-x,cy+y,color)
CALL pixel(cx+x,cy-y,color)
CALL pixel(cx-x,cy-y,color)
EXIT SELECT
CASE <y
CALL pixel(cx+x,cy+y,color)
CALL pixel(cx-x,cy+y,color)
CALL pixel(cx+x,cy-y,color)
CALL pixel(cx-x,cy-y,color)
CALL pixel(cx+y,cy+x,color)
CALL pixel(cx-y,cy+x,color)
CALL pixel(cx+y,cy-x,color)
CALL pixel(cx-y,cy-x,color)
END SELECT
WEND
END SUB
Moving on, next is drawing an axis aligned ellipse.
The axis aligned ellipse looks like a circle that has been streched or flattened, however you look at it. This makes it a bit more complicated to draw since the X-axis is longer or shorter than the Y-axis. But using the Bresenham algorithm, we can avoid using any slow, high level math functions and stick with integer addition, subtraction and mutliplication.
The axis aligned ellipse consists of four symmetrical arcs so the following algorithm coded in PowerBasic only computes one quarter of the ellipse and uses symmetry (mirror images or reflection) to draw the remaining three arcs.
SUB Ellipse1(BYVAL xc AS LONG,BYVAL yc AS LONG,_
BYVAL a AS LONG,BYVAL b AS LONG,BYVAL color AS DWORD)
LOCAL a2 AS DWORD, b2 AS DWORD
LOCAL x AS LONG,y AS LONG
LOCAL S AS LONG,T AS LONG
a2=a*a
b2=b*b
x=0
y=b
s=a2*(1-2*b)+2*b2
t=b2-2*a2*(2*b-1)
CALL pixel(xc+x,yc+y,color)
CALL pixel(xc-x,yc+y,color)
CALL pixel(xc-x,yc-y,color)
CALL pixel(xc+x,yc-y,color)
DO
IF s<0 THEN
s=s+2*b2*(2*x+3)
t=t+4*b2*(x+1)
INCR x
ELSE
IF t<0 THEN
s=s+2*b2*(2*x+3)-4*a2*(y-1)
t=t+4*b2*(x+1)-2*a2*(2*y-3)
INCR x
DECR y
ELSE
s=s-4*a2*(y-1)
t=t-2*a2*(2*y-3)
DECR y
END IF
END IF
CALL pixel(xc+x,yc+y,color)
CALL pixel(xc-x,yc+y,color)
CALL pixel(xc-x,yc-y,color)
CALL pixel(xc+x,yc-y,color)
LOOP UNTIL y=0
END SUB
Now onto what you've been waiting for; drawing ellipses oriented at any angle!
This is an ellipse rotated twenty degrees from the X-axis or 0.34 radians. Looking at the source code you'll notice it uses four trig functions but only once. These aren't used to draw the actual ellipse but just to find the two points where the major and minor axis of the ellipse ends which of course determines the shape of the ellipse as in an axis aligned ellipse.
This ellipse algorithm was originally coded to use 64 bit integers. The numbers involded in drawing a rotated ellipse get too big for 32 bit integers to hold. Well, I quickly found out that 64 bit intergers isn't sufficient either if you're drawing fairly large ellipses in high resolution graphic modes. I switched to 32 bit floating point or in PowerBasic it's called single precision. A 32bit CPU handles 32 bit floating point numbers much faster than 64 bit integers anyway and can hold huge numbers due to an exponent.
This algorithm will draw a circle or an axis aligned ellipse. Circles and axis aligned ellipses are just special cases of a general ellipse but since this algorithm is more mathematically intensive, it will take a little longer. Plus, a rotated ellipse drawn in raster graphics has only two symmetrical arcs, so half of the points in the ellipse have to be calculated.
So here it is. The rotated ellipse algorithm coded in PowerBasic. Just a note here.... these programs will only draw an outline of a circle, ellipse, and a rotated ellipse. In my Polygon War source code near the end, there is code that draws solid circles & ellipses. The source code is included in the download.
SUB GeneralEllipse (BYVAL iXC AS LONG,BYVAL iYC AS LONG,_
BYVAL A AS LONG,BYVAL B AS LONG,_
BYVAL angle AS SINGLE,BYVAL color AS DWORD)
LOCAL ixa AS SINGLE, iya AS SINGLE
LOCAL ixb AS SINGLE, iyb AS SINGLE
LOCAL ixa2 AS SINGLE, iya2 AS SINGLE
LOCAL ixb2 AS SINGLE, iyb2 AS SINGLE
LOCAL ixaya AS SINGLE, ixbyb AS SINGLE
LOCAL ila2 AS SINGLE, ila4 AS SINGLE
LOCAL ilb2 AS SINGLE, ilb4 AS SINGLE
LOCAL ia AS SINGLE, ib AS SINGLE, ic AS SINGLE, id AS SINGLE
LOCAL idx AS SINGLE, idy AS SINGLE, isigma AS SINGLE
LOCAL ixp1 AS SINGLE
LOCAL temp AS SINGLE
LOCAL xflag AS DWORD
LOCAL pi AS SINGLE
pi=3.1415926
IF angle <pi/2 THEN
xflag=1
ELSEIF angle>pi/2 AND angle<pi THEN
temp=angle-pi/2
angle=pi/2-temp
xflag=-1
ELSEIF angle>=pi AND angle<pi*1.5 THEN
angle=angle-pi
xflag=1
ELSEIF angle>=pi*1.5 AND angle<pi*2 THEN
angle=angle-pi
temp=angle-pi/2
angle=pi/2-temp
xflag=-1
END IF
ixa=COS(angle)*A
iya=SIN(angle)*A
ixb=COS(angle+(pi/2))*B
iyb=SIN(angle+(pi/2))*B
ixa2=ixa*ixa
iya2=iya*iya
ixb2=ixb*ixb
iyb2=iyb*iyb
ixaya=ixa*iya
ixbyb=ixb*iyb
ila2=ixa2+iya2
ila4=ila2*ila2
ilb2=ixb2+iyb2
ilb4=ilb2*ilb2
ia=ixa2*ilb4+ixb2*ila4
ib=ixaya*ilb4+ixbyb*ila4
ic=iya2*ilb4+iyb2*ila4
id=ila4*ilb4
LOCAL ix AS LONG,iy AS LONG, iym1 AS LONG,iyp1 AS LONG
IF ( iYA <= iXA ) THEN
' start AT (-xA,-yA)
iX = -iXA
iY = -iYA
iDx = -(iB*iXA+iC*iYA)
iDy = iA*iXA+iB*iYA
' arc FROM (-xA,-yA) TO point (x0,y0) where dx/dy = 0
WHILE ( iDx <= 0 )
CALL pixel(iXC+iX*xflag,iYC+iY,color)
CALL pixel(iXC-iX*xflag,iYC-iY,color)
INCR iY
iSigma = iA*iX*iX+2*iB*iX*iY+iC*iY*iY-iD
IF ( iSigma < 0 ) THEN
iDx=iDx - iB
iDy=iDy + iA
DECR iX
END IF
iDx=iDx + iC
iDy=iDy - iB
WEND
' arc FROM (x0,y0) TO point (x1,y1) where dy/dx = 1
WHILE ( iDx <= iDy )
CALL pixel(iXC+iX*xflag,iYC+iY,color)
CALL pixel(iXC-iX*xflag,iYC-iY,color)
INCR iY
iXp1 = iX+1
iSigma = iA*iXp1*iXp1+2*iB*iXp1*iY+iC*iY*iY-iD
IF ( iSigma >= 0 ) THEN
iDx=iDx + iB
iDy=iDy - iA
iX = iXp1
END IF
iDx=iDx + iC
iDy=iDy - iB
WEND
' arc FROM (x1,y1) TO point (x2,y2) where dy/dx = 0
WHILE ( iDy >= 0 )
CALL pixel(iXC+iX*xflag,iYC+iY,color)
CALL pixel(iXC-iX*xflag,iYC-iY,color)
INCR iX
iSigma = iA*iX*iX+2*iB*iX*iY+iC*iY*iY-iD
IF ( iSigma < 0 ) THEN
iDx=iDx + iC
iDy=iDy - iB
INCR iY
END IF
iDx=iDx + iB
iDy=iDy - iA
WEND
' arc FROM (x2,y2) TO point (x3,y3) where dy/dx = -1
WHILE ( iDy >= -iDx )
CALL pixel(iXC+iX*xflag,iYC+iY,color)
CALL pixel(iXC-iX*xflag,iYC-iY,color)
INCR iX
iYm1 = iY-1
iSigma = iA*iX*iX+2*iB*iX*iYm1+iC*iYm1*iYm1-iD
IF ( iSigma >= 0 ) THEN
iDx=iDx - iC
iDy=iDy + iB
iY = iYm1
END IF
iDx=iDx + iB
iDy=iDy - iA
WEND
' arc FROM (x3,y3) TO (xa,ya)
WHILE ( iY >= iYA )
CALL pixel(iXC+iX*xflag,iYC+iY,color)
CALL pixel(iXC-iX*xflag,iYC-iY,color)
DECR iY
iSigma = iA*iX*iX+2*iB*iX*iY+iC*iY*iY-iD
IF ( iSigma < 0 ) THEN
iDx=iDx + iB
iDy=iDy - iA
INCR iX
END IF
iDx=iDx - iC
iDy=iDy + iB
WEND
ELSE
' start AT (-xa,-ya)
iX = -iXA
iY = -iYA
iDx = -(iB*iXA+iC*iYA)
iDy = iA*iXA+iB*iYA
' arc FROM (-xa,-ya) TO point (x0,y0) where dy/dx = -1
WHILE ( -iDx >= iDy )
CALL pixel(iXC+iX*xflag,iYC+iY,color)
CALL pixel(iXC-iX*xflag,iYC-iY,color)
DECR iX
iYp1 = iY+1
iSigma = iA*iX*iX+2*iB*iX*iYp1+iC*iYp1*iYp1-iD
IF ( iSigma >= 0 ) THEN
iDx=iDx + iC
iDy=iDy - iB
iY = iYp1
END IF
iDx=IDx - iB
iDy=Idy +iA
WEND
' arc FROM (x0,y0) TO point (x1,y1) where dx/dy = 0
WHILE ( iDx <= 0 )
CALL pixel(iXC+iX*xflag,iYC+iY,color)
CALL pixel(iXC-iX*xflag,iYC-iY,color)
INCR iY
iSigma = iA*iX*iX+2*iB*iX*iY+iC*iY*iY-iD
IF ( iSigma < 0 ) THEN
iDx=iDx - iB
iDy=iDy + iA
DECR iX
END IF
iDx=iDx + iC
iDy=iDy - iB
WEND
' arc FROM (x1,y1) TO point (x2,y2) where dy/dx = 1
WHILE ( iDx <= iDy )
CALL pixel(iXC+iX*xflag,iYC+iY,color)
CALL pixel(iXC-iX*xflag,iYC-iY,color)
INCR iY
iXp1 = iX+1
iSigma = iA*iXp1*iXp1+2*iB*iXp1*iY+iC*iY*iY-iD
IF ( iSigma >= 0 ) THEN
iDx=IDx + iB
iDy=Idy - iA
iX = iXp1
END IF
iDx=iDx + iC
iDy=iDy - iB
WEND
' arc FROM (x2,y2) TO point (x3,y3) where dy/dx = 0
WHILE ( iDy >= 0 )
CALL pixel(iXC+iX*xflag,iYC+iY,color)
CALL pixel(iXC-iX*xflag,iYC-iY,color)
INCR iX
iSigma = iA*iX*iX+2*iB*iX*iY+iC*iY*iY-iD
IF ( iSigma < 0 ) THEN
iDx=iDx + iC
iDy=iDy - iB
INCR iY
END IF
iDx=iDx + iB
iDy=iDy - iA
WEND
' arc FROM (x3,y3) TO (xa,ya)
WHILE ( iX <= iXA )
CALL pixel(iXC+iX*xflag,iYC+iY,color)
CALL pixel(iXC-iX*xflag,iYC-iY,color)
INCR iX
iYm1 = iY-1
iSigma = iA*iX*iX+2*iB*iX*iYm1+iC*iYm1*iYm1-iD
IF ( iSigma >= 0 ) THEN
iDx=iDx - iC
iDy=iDy + iB
iY = iYm1
END IF
iDx=iDx + iB
iDy=iDy - iA
WEND
END IF
END SUB
