Computer Graphics
Chapter 3
Graphics Output Primitives
Andreas Savva
Basic Raster Algorithms
for 2D Primitives
Description of pictures
Specified by a set of intensities for the pixel positions.
Describe it as a set of complex objects, such as trees,
furniture and walls, positioned at specific coordinate
locations within the scene.
Graphics programming packages provide functions to
describe a scene in terms of basic geometric structures
referred to as output primitives.
• Points
• Straight lines
• Circles
• Splines curves and surfaces
• Polygon color areas
• Character strings
• Etc. 2
Implementing Application programs
Description of objects in terms of primitives and
attributes and converts them to the pixels on the
screen.
Primitives – what is to be generated
Attributes – how primitives are to be generated
3
(0,0)
Points CRT
(maxx,maxy)
The electron beam is turned on to illuminate the phosphor
at the selected location (x, y) where
0 ≤ x ≤ maxx
0 ≤ y ≤ maxy
setpixel(x, y, intensity) – loads an intensity value into the
frame-buffer at (x, y).
getpixel(x, y) – retrieves the current frame-buffer
intensity setting at position (x, y).
4
Lines
Analog devises, such as a random-scan display or a
vector plotter, display a straight line smoothly from one
endpoint to another. Linearly varying horizontal and
vertical deflection voltages are generated that are
proportional to the required changes in the x and y
directions to produce the smooth line.
5
Digital devices display a straight line by plotting discrete
coordinate points along the line path which are calculated
from the equation of the line.
Screen locations are referenced with integer values, so plotted
positions may only approximate actual line positions between two
specific endpoints.
A computed line position of (10.48, 20.51) will be converted to
pixel position (10, 21). This rounding of coordinate values to
integers causes lines to be displayed with a stairstep appearance
(the “jaggies”).
Particularly noticeable on systems with low resolution.
To smooth raster lines, pixel intensities along the line paths must
be adjusted.
6
Line Drawing Algorithms
Cartesian equation:
y = mx + c y2
where y1
m – slope x1 x2
c – y-intercept
y 2 y1 y
m
x2 x1 x
7
Slope
+ve -ve
if |m| = 1 45°
45°
= 45°
if |m| 1
-45° < < 45° °
°
if |m| 1
45° < < 90° or °
-90° < < -45° °
8
|m| = 1
y=x
m=1
c=0 y
x y 8
0 0 7
1 1 6
2 2 5
3 3 4
4 4 3
5 5
2
6 6 1
7 7
0
8 8
0 1 2 3 4 5 6 7 8 x
9
|m| 1
y=½x+1
m=½
y
c=1
8
x y round(y)
7
0 1 1
6
1 1.5 2
2 2 2 5
3 2.5 3 4
4 3 3 3
5 3.5 4 2
6 4 4 1
7 4.5 5 0
8 5 5 0 1 2 3 4 5 6 7 8 x
10
|m| 1
y = 3x - 2
m=3
y
c = -2
8
x y round(y)
7
0 -2 -2
1 1 1 6
2 4 4 5
3 7 7 4
4 10 10 3
5 13 13 2
6 16 16 1
7 19 19 0
8 22 22
0 1 2 3 4 5 6 7 8 x
outside
11
The Digital Differential Analyzer
(DDA) Algorithm
y
m means that for a unit (1) change in x there is
x m-change in y.
x y Do not use
i.e. y = 3x + 1 m=3 0 1
y = 3x + 1
to calculate y.
1 4 Use m
2 7
3 10
4 13
5 16
x 1
means that for a unit (1) change in y there is
y m 1/m change in x. 12
The DDA Method
Uses differential equation of the line : m
If slope |m| 1 then increment x in steps of 1 pixel
and find corresponding y-values.
If slope |m| 1 then increment y in steps of 1 pixel
and find corresponding x-values.
13
step through in x step through in y
The DDA Method
Desired line
(xi+1,round(yi+m))
(xi,yi) (xi+1,yi+m)
(xi,round(yi))
14
if slope m 0
if |m| 1 if |m| 1
xi+1 = xi + 1 yi+1 = yi + 1
yi+1 = yi + m xi+1 = xi + 1/m
Right
Right
Left
15
Left
Proceeding from right-endpoint to left-endpoint
if slope m 0
if |m| 1 if |m| 1
xi+1 = xi - 1 yi+1 = yi - 1
yi+1 = yi - m xi+1 = xi - 1/m
Right
Right
Left
16
Left
if slope m < 0
if |m| 1 if |m| 1
xi+1 = xi + 1 yi+1 = yi - 1
yi+1 = yi + m xi+1 = xi - 1/m
Left
Left
Right
17
Right
Proceeding from right-endpoint to left-endpoint
if slope m 0
if |m| 1 if |m| 1
xi+1 = xi - 1 yi+1 = yi + 1
yi+1 = yi - m xi+1 = xi + 1/m
Left
Left
Right
18
Right
Example (DDA)
0 m 1
y 13 x 1 xi 1 xi 1
yi 1 yi 13
x y round(y) y
0 1 1 8
1 4/3 1 7
2 5/3 2 6
5
3 2 2
4
4 7/3 2
3
5 8/3 3 2
6 3 3 1
7 10/3 3 0
8 11/3 4 0 1 2 3 4 5 6 7 8 x 19
Example (DDA)
m 1
y 3 x 8 yi 1 yi 1
xi 1 xi ( 13 )
y x round(x) y
8 0 0 8
7 1/3 0 7
6 2/3 1 6
5
5 1 1
4
4 4/3 1
3
3 5/3 2 2
2 2 2 1
1 7/3 2 0
0 8/3 3 0 1 2 3 4 5 6 7 8 x 20
void LineDDA(int x0, int y0, int x1, int y1)
{
int dx = x1 – x0, dy = y1 – y0, steps;
if (abs(dx)>abs(dy)) steps = abs(dx);
else steps = abs(dy);
// one of these will be 1 or -1
double xIncrement = (double)dx / (double )steps;
double yIncrement = (double)dy / (double )steps;
double x = x0;
double y = y0;
setPixel(round(x), round(y));
for (int i=0; i<steps; i++) {
{
x += xIncrement;
y += yIncrement;
setPixel(round(x), round(y));
}
}
Note: The DDA algorithm is faster than the direct use of y = mx + c.
It eliminates multiplication; only one addition. 21
Example
Draw a line from point (2,1) to (12,6)
Draw a line from point (1,6) to (11,0)
7
0 1 2 3 4 5 6 7 8 9 10 11 12
22
Advantages of DDA Algorithm
It is the simplest algorithm and it does not
require special skills for implementation.
It is a faster method for calculating pixel
positions than the direct use of equation y=mx +
b. It eliminates the multiplication in the equation
by making use of raster characteristics, so that
appropriate increments are applied in the x or y
direction to find the pixel positions along the line
path.
23
Disadvantages of DDA
Algorithm
Floating point arithmetic in DDA
algorithm is still time-consuming.
The algorithm is orientation dependent.
Hence end point accuracy is poor.
24
Special cases
Special cases can be handled separately
– Horizontal lines (y = 0)
– Vertical lines (x = 0)
– Diagonal lines (|x| = |y|)
directly into the frame-buffer without
processing them through the line-plotting
algorithms.
25
Parallel Line Algorithms
Take advantage of multiple processors.
Given np processors, subdivide the line path into np Bresenham
segments.
For a line with slope 0 m 1 and leftpoint (x0,y0) the distance to
the right endpoint (left endpoint for next segment) is
x n p 1
x p
np
where
x = width of the line
xp is computed using integer division
Numbering the segments, and the processors, as 0, 1, 2, …, np-1,
starting x-coordinate for the kth partition is 26
Parallel Line Algorithms (continue)
i.e. x = 15 , np = 4 processors
15 4 1 18
x p 4
4 4
Starting x-values at x0, x0 + 4, x0 + 8, x0 + 12
yp = mxp
At the kth segment, the starting y-coordinates is
yk = y0 + round(kyp)
Also, the initial decision parameter for Bresenham’s
algorithm at the start of the kth subinterval is:
pk = (kxp)(2y) – round(kyp)(2x) + 2y – x 27
Anti-aliasing for straight lines
Lines generated can have jagged or stair-step appearance,
one aspect of phenomenon called aliasing, caused by fact
that pixels are integer coordinate points.
Use anti-aliasing routines to smooth out display of a line
by adjusting pixels intensities along the line path
28
Another raster effect
Line B
Line A
Both lines plotted with the same number of pixels, but
the diagonal line is longer than the horizontal line
Visual effect is diagonal line appears less thick.
If the intensity of each pixel is I, then the intensity per unit
length of line A is I, whereas for line B it is only I/2; this
discrepancy is easily detected by the viewer.
29
Circle Generating Algorithms
Circles and ellipses are common components in
many pictures.
Circle generation routines are often included in
packages.
30
Circle Equations
Polar form
x = rCos
y = rSin (r = radius of circle)
y
P=(rCos, rSin)
r rSin)
x
rCos)
31
Drawing a circle
= 0°
while ( < 360°)
x = rCos
y = rSin
setPixel(x,y)
= + 1°
end while
Disadvantages
To find a complete circle varies from 0° to
360°
The calculation of trigonometric functions
is very slow. 32
Cartesian form
Use Pythagoras theorem
x2 + y2 = r2 r y
x
y
x
P 2
,r
2
x
r y
x x
33
Circle algorithms
Step through x-axis to determine y-values
Disadvantages:
– Not all pixel filled in 34
– Square root function is very slow
Circle Algorithms
Use 8-fold symmetry and only compute pixel
positions for the 45° sector.
(-x, y) (x, y)
(-y, x) 45° (y, x)
(-y, -x) (y, -x)
(-x, -y) (x, -y) 35
Bresenham’s Circle Algorithm
Consider only
45° ≤ ≤ 90°
General Principle
The circle function:
f circle ( x, y ) x 2 y 2 r 2
and
0 if (x,y) is inside the circle boundary
f circle ( x, y ) 0 if (x,y) is on the circle boundary
0 if (x,y) is outside the circle boundary
36
Bresenham’s Circle Algorithm
p1 p3
yi
D(si)
yi - 1 D(ti)
p2
xi xi + 1
After point p1, do we choose p2 or p3?
37
Bresenham’s Circle Algorithm
Define: D(si) = distance of p3 from circle
D(ti) = distance of p2 from circle
i.e. D(si) = (xi + 1)2 + yi2 – r2 [always +ve]
D(ti) = (xi + 1)2 + (yi – 1)2 – r2 [always -ve]
Decision Parameter pi = D(si) + D(ti)
so if pi < 0 then the circle is closer to p3 (point above)
if pi ≥ 0 then the circle is closer to p2 (point below)
38
Bresenham’s Circle Algorithm
pi = D(si) + D(ti)
pi = 2(xi+1)2 + yi2 + (yi-1)2 – 2r2
Calculating next decision parameter,
pi+1 = 2(xi+2)2 + yi+12 + (yi+1-1)2 – 2r2
pi+1 - pi = 2((xi+2)2-(xi+1)2) + (yi+12 – yi2) + ((yi+1-
1)2 + (yi-1)2)
pi+1 = pi + 2((xi+2+xi+1)(xi+2-xi-1)) + ((yi+1+yi)(yi+1-
yi)) + ((yi+1-1+yi-1)(yi+1-1-yi+1))
pi+1 = pi + 2(2xi+3) + ((yi+1+yi)(yi+1-yi)) + ((yi+1-1+yi- 39
if (pi<=0)
xi+1=xi+1 and yi+1=yi
so that pi+1 = pi + 2(2xi + 3) + ((yi+1+yi)( yi-yi)) +
((yi-1+yi-1)(yi-1-yi+1))
pi+1 = pi + 2(2xi + 3) +((yi+1+yi)(0)) + ((yi-1+yi-1)(0))
pi+1 = pi + 4xi + 6
Else
xi+1=xi+1 and yi+1=yi-1
pi+1 = pi + 2(2xi+3) + ((yi-1+yi)(yi-1-yi)) + ((yi-2+yi-1)
(yi-2-yi+1))
pi+1 = pi + 4xi+6 + ((2yi-1)(-1)) + ((2yi-3)(-1))
pi+1 = pi + 4xi+6 - 2yi - 2yi + 1 + 3
pi+1 = pi + 4(xi - yi) + 10 40
Calculate Initial value
The initial value of pi can be obtained by
replacing x=0 and y=r. Thus, we get,
po = 2 + r2 + (r - 1)2 -2r2
po = 2 + r2 + r2 + 1 -2r – 2r2
po = 3 – 2r
41
The Algorithm
x0 = 0
y0 = r
p0 = [12 + r2 – r2] + [12 + (r-1)2 – r2] = 3 – 2r
if pi < 0 then
yi+1 = yi
pi+1 = pi + 4xi + 6
xi+1 = xi + 1
else if pi ≥ 0 then
yi+1 = yi – 1
pi+1 = pi + 4(xi – yi) + 10
42
Stop when x ≥ y and determine symmetry
Example
r = 10
p0 = 3 – 2r = -17
Initial point (x0, y0) = (0, 10)
10
i pi xi, yi 9
0 -17 (0, 10) 8
7
1 -11 (1, 10)
6
2 -1 (2, 10)
5
3 13 (3, 10) 4
4 -5 (4, 9) 3
5 15 (5, 9) 2
1
6 9 (6, 8)
0
7 (7,7)
0 1 2 3 4 5 6 7 8 9 10
43
Exercises
Draw the circle with r = 12 using the
Bresenham algorithm.
Draw the circle with r = 14 and center at
(15, 10).
44
Decision Parameters
Prove that if pi < 0 and yi+1 = yi then
pi+1 = pi + 4xi + 6
Prove that if pi ≥ 0 and yi+1 = yi – 1 then
pi+1 = pi + 4(xi – yi) + 10
45
Advantages of Bresenham circle
Only involves integer addition, subtraction
and multiplication
There is no need for squares, square roots
and trigonometric functions
46
Midpoint Circle Algorithm
Midpoint
yi
yi-1
x 2 + y 2 – r2 = 0
xi xi+1 xi+2
Assuming that we have just plotted the pixels at (xi , yi).
Which is next? (xi+1, yi) OR (xi+1, yi – 1).
- The one that is closer to the circle.
47
Midpoint Circle Algorithm
The decision parameter is the circle at the midpoint
between the pixels yi and yi – 1.
pi f circle ( xi 1, yi 12 )
( xi 1) 2 ( yi 12 ) 2 r 2
If pi < 0, the midpoint is inside the circle and the pixel
yi is closer to the circle boundary.
If pi ≥ 0, the midpoint is outside the circle and the pixel
yi - 1 is closer to the circle boundary.
48
Decision Parameters
Decision Parameters are obtained using
incremental calculations
Note:
pi 1 f circle ( xi 1 1, yi 1 ) 1
2 xi+1 = xi +1
( xi 2) 2 ( yi 1 12 ) 2 r 2
OR
pi 1 pi 2( xi 1) 2 ( yi21 yi2 ) ( yi 1 yi ) 1
where yi+1 is either yi or yi-1 depending on the sign of pi
49
1. Initial values:- point(0,r) The Algorithm
x0 = 0
move circle origin at (0,0) by
y0 = r x = x – xc and y = y – yc
2. Initial decision parameter
p0 f circle (1, r 12 ) 1 (r 12 ) 2 r 2 54 r
3. At each xi position, starting at i = 0, perform the
following test: if pi < 0, the next point is (xi + 1, yi) and
pi+1 = pi + 2xi+1 + 1
If pi ≥ 0, the next point is (xi+1, yi-1) and
pi+1 = pi + 2xi+1 + 1 – 2yi+1
where 2xi+1 = 2xi + 2 and 2yi+1 = 2yi – 2
4. Determine symmetry points in the other octants
5. Move pixel positions (x,y) onto the circular path
centered on (xc, yc) and plot the coordinates: x = x + xc, y50
=y+y
Example
r = 10
p0 = 1 – r = -9 (if r is integer round p0 = 5/4 – r to integer)
Initial point (x0, y0) = (0, 10)
10
i pi xi+1, yi+1 2xi+1 2yi+1 9
0 -9 (1, 10) 2 20 8
7
1 -6 (2, 10) 4 20
6
2 -1 (3, 10) 6 20
5
3 6 (4, 9) 8 18 4
4 -3 (5, 9) 10 18 3
5 8 (6, 8) 12 16 2
1
6 5 (7, 7)
0
0 1 2 3 4 5 6 7 8 9 10
51
Exercises
Draw the circle with r = 12 using the
Midpoint-circle algorithm
Draw the circle with r = 14 and center at
(15, 10).
52
Exercises
Prove that if pi < 0 and yi+1 = yi then
pi+1 = pi + 2xi+1 + 1
Prove that if pi ≥ 0 and yi+1 = yi-1 then
pi+1 = pi + 2xi+1 + 1 – 2yi+1
53
Midpoint function
void plotpoints(int x, int y)
{
setpixel(xcenter+x, ycenter+y);
setpixel(xcenter-x, ycenter+y);
setpixel(xcenter+x, ycenter-y);
setpixel(xcenter-x, ycenter-y);
setpixel(xcenter+y, ycenter+x);
setpixel(xcenter-y, ycenter+x);
setpixel(xcenter+y, ycenter-x);
setpixel(xcenter-y, ycenter-x);
}
void circle(int r)
{
int x = 0, y = r;
plotpoints(x,y);
int p = 1 – r;
while (x<y) {
x++;
if (p<0) p += 2*x + 1;
else {
y--;
p += 2*(x-y) + 1;
}
plotpoints(x,y);
} 54
}
Ellipse-Generating Algorithms
Ellipse – A modified circle whose radius varies from a
maximum value in one direction (major axis) to a minimum
value in the perpendicular direction (minor axis).
d1
F1 P=(x,y)
d2
F2
The sum of the two distances d1 and d2, between the fixed
positions F1 and F2 (called the foci of the ellipse) to any
point P on the ellipse, is the same value, i.e.
d1 + d2 = constant 55
Ellipse Properties
Expressing distances d1 and d2 in terms of the focal
coordinates F1 = (x1, y1) and F2 = (x2, y2), we have:
( x x1 ) 2 ( y y1 ) 2 ( x x2 ) 2 ( y y2 ) 2 constant
ry
rx
2 2
x xc y yc
Cartesian coordinates: 1
rx ry
Polar coordinates: x xc rx cos
y yc ry sin 56
Ellipse Algorithms
Symmetry between quadrants
Not symmetric between the two octants of a quadrant
Thus, we must calculate pixel positions along the
elliptical arc through one quadrant and then we obtain
positions in the remaining 3 quadrants by symmetry
(-x, y) (x, y)
ry
rx
(-x, -y) (x, -y)
57
Ellipse Algorithms
f ellipse ( x, y ) ry2 x 2 rx2 y 2 rx2 ry2
Decision parameter:
0 if ( x, y ) is inside the ellipse
f ellipse ( x, y ) 0 if ( x, y ) is on the ellipse
0 if ( x, y ) is outside the ellipse
Slope = -1
ry
1
2 dy 2ry2 x
Slope 2
rx dx 2rx y
58
Ellipse Algorithms Slope = -1
ry 1 2
rx
Starting at (0, ry) we take unit steps in the x direction until
we reach the boundary between region 1 and region 2.
Then we take unit steps in the y direction over the
remainder of the curve in the first quadrant.
At the boundary
dy
1 2ry2 x 2rx2 y
dx
therefore, we move out of region 1 whenever
2ry2 x 2rx2 y
59
Midpoint Ellipse Algorithm
Midpoint
yi
yi-1
xi xi+1 xi+2
Assuming that we have just plotted the pixels at (xi , yi).
The next position is determined by:
p1i f ellipse ( xi 1, yi 12 )
ry2 ( xi 1)2 rx2 ( yi 12 ) 2 rx2 ry2
If p1i < 0 the midpoint is inside the ellipse yi is closer
60
If p1i ≥ 0 the midpoint is outside the ellipse yi – 1 is closer
Decision Parameter (Region 1)
At the next position [xi+1 + 1 = xi + 2]
p1i 1 f ellipse ( xi 1 1, yi 1 12 )
ry2 ( xi 2) 2 rx2 ( yi 1 12 ) 2 rx2 ry2
OR
p1i 1 p1i 2ry2 ( xi 1) 2 ry2 rx2 ( yi 1 12 ) 2 ( yi 12 ) 2
where yi+1 = yi
or yi+1 = yi – 1
61
Decision Parameter (Region 1)
Decision parameters are incremented by:
2ry2 xi 1 ry2 if p1i 0
increment 2
2 r x
y i 1 y r 2
2 r 2
x yi 1 if p1i 0
Use only addition and subtraction by obtaining
2ry2 x and 2rx2 y
At initial position (0, ry)
2ry2 x 0
2rx2 y 2rx2 ry
p10 f ellipse (1, ry 12 ) ry2 rx2 (ry 12 ) 2 rx2ry2
ry2 rx2 ry 14 rx2 62
Region 2
Over region 2, step in the negative y direction and midpoint is
taken between horizontal pixels at each step.
Midpoint
yi
yi-1
xi xi+1 xi+2
Decision parameter:
p 2i f ellipse ( xi 12 , yi 1)
ry2 ( xi 12 ) 2 rx2 ( yi 1) 2 rx2 ry2
If p2i > 0 the midpoint is outside the ellipse xi is closer
63
If p2i ≤ 0 the midpoint is inside the ellipse xi + 1 is closer
Decision Parameter (Region 2)
At the next position [yi+1 – 1 = yi – 2]
p 2i 1 f ellipse ( xi 1 12 , yi 1 1)
ry2 ( xi 1 12 ) 2 rx2 ( yi 2) 2 rx2 ry2
OR
p 2i 1 p 2i 2rx2 ( yi 1) rx2 ry2 ( xi 1 12 ) 2 ( xi 12 ) 2
where xi+1 = xi
or xi+1 = xi + 1
64
Decision Parameter (Region 2)
Decision parameters are incremented by:
2rx2 yi 1 rx2 if p 2i 0
increment 2
2 r x
y i 1 2 r 2
y
x i 1 rx
2
if p 2i 0
At initial position (x0, y0) is taken at the last position
selected in region 1
p 20 f ellipse ( x0 12 , y0 1)
ry2 ( x0 12 ) 2 rx2 ( y0 1)2 rx2 ry2
65
Midpoint Ellipse Algorithm
1. Input rx, ry, and ellipse center (xc, yc), and obtain the first
point on an ellipse centered on the origin as
(x0, y0) = (0, ry)
2. Calculate the initial parameter in region 1 as
p10 ry2 rx2 ry 14 rx2
3. At each xi position, starting at i = 0, if p1i < 0, the next
point along the ellipse centered on (0, 0) is (xi + 1, yi) and
p1i 1 p1i 2ry2 xi 1 ry2
otherwise, the next point is (xi + 1, yi – 1) and
p1i 1 p1i 2ry2 xi 1 2rx2 yi 1 ry2
2 2 66
2
and continue until yr x 2 rx y
Midpoint Ellipse Algorithm
4. (x0, y0) is the last position calculated in region 1. Calculate the
initial parameter in region 2 as
p 20 ry2 ( x0 12 )2 rx2 ( y0 1)2 rx2 ry2
5. At each yi position, starting at i = 0, if p2i > 0, the next point
along the ellipse centered on (0, 0) is (xi, yi – 1) and
p 2i 1 p 2i 2rx2 yi 1 rx2
otherwise, the next point is (xi + 1, yi – 1) and
p 2i 1 p 2i 2ry2 xi 1 2rx2 yi 1 rx2
Use the same incremental calculations as in region 1. Continue
until y = 0.
6. For both regions determine symmetry points in the other three
quadrants.
7. Move each calculated pixel position (x, y) onto the elliptical
path centered on (xc, yc) and plot the coordinate values
67
x = x + xc , y = y + yc
Example
r x = 8 , ry = 6
2ry2x = 0 (with increment 2ry2 = 72)
2rx2y = 2rx2ry (with increment -2rx2 = -128)
Region 1
(x0, y0) = (0, 6)
p10 ry2 rx2 ry 14 rx2 332
i pi xi+1, yi+1 2ry2xi+1 2rx2yi+1
0 -332 (1, 6) 72 768
1 -224 (2, 6) 144 768
2 -44 (3, 6) 216 768
3 208 (4, 5) 288 640
4 -108 (5, 5) 360 640
5 288 (6, 4) 432 512
6 244 (7, 3) 504 384
Move out of region 1 since
2ry2x > 2rx2y 68
Example
Region 2
(x0, y0) = (7, 3) (Last position in region 1)
p 20 f ellipse (7 12 , 2) 151
i pi xi+1, yi+1 2ry2xi+1 2rx2yi+1
0 -151 (8, 2) 576 256
1 233 (8, 1) 576 128
2 745 (8, 0) - - Stop at y = 0
6
5
4
3
2
1
0
69
0 1 2 3 4 5 6 7 8
Exercises
Draw the ellipse with rx = 6, ry = 8.
Draw the ellipse with rx = 10, ry = 14.
Draw the ellipse with rx = 14, ry = 10 and
center at (15, 10).
70
Midpoint Ellipse Function
void ellipse(int Rx, int Ry)
{
int Rx2 = Rx * Rx, Ry2 = Ry * Ry;
int twoRx2 = 2 * Rx2, twoRy2 = Ry2 * Ry2;
int p, x = 0, y = Ry;
int px = 0, py = twoRx2 * y;
ellisePlotPoints(xcenter, ycenter, x, y);
// Region 1
p = round(Ry2 – (Rx2 * Ry) + (0.25 * Rx2));
while (px < py) {
x++;
px += twoRy2;
if (p < 0) p += Ry2 + px;
else {
y--;
py -= twoRx2;
p += Ry2 + px – py;
}
ellisePlotPoints(xcenter, ycenter, x, y);
}
// Region 2
p = round(Ry2 * (x+0.5) * (x+0.5) + Rx2 * (y-1)*(y-1) – Rx2 * Ry2;
while (y > 0) {
y--;
py -= twoRx2;
if (p > 0) p += Rx2 – py;
else {
x++;
px += twoRy2;
p += Rx2 – py + px;
}
ellisePlotPoints(xcenter, ycenter, x, y); 71
}
}
