Computer Graphics - Output Primitive

Line, Circle, and Ellipse Drawing

1. Mr. Rupesh Mishra | [email protected]
Output Primitive
1
St. Francis Institute of Technology
Department of Computer Engineering
1
Subject Incharge
Rupesh Mishra
Asst. Professor 
Room No. 401
[email protected]
31 July 2020

2. Mr. Rupesh Mishra | [email protected]
2
Module II
Lecture 4
Computer Graphics: Output Primitive
St. Francis Institute of Technology
Department of Computer Engineering
1

3. Mr. Rupesh Mishra | [email protected]

4. Mr. Rupesh Mishra | [email protected]
Output Primitive
•Graphics programming packages
•Describe a scene in terms of basic geometric structures (Output Primitives)
• Group output primitives into more complex structures.
•Each output primitive is specified with
•Input coordinate data
•Information about object to be displayed.
•Point, Line, Circle, Conic Section, Spline curves, polygon and Character String.

5. Mr. Rupesh Mishra | [email protected]
Point

6. Mr. Rupesh Mishra | [email protected]
Point
•Point plotting is accomplished by converting a single coordinate position into
appropriate operations for the output device in use.
•Setting value in frame buffer
•Moving beam of electron at the selected location (CRT)
•Point plotting instruction in display list (Random Scan)
•Converted to deflection voltages to position the electron beam.
•Frame buffer is loaded with the color codes (RGB System)

7. Mr. Rupesh Mishra | [email protected]
Line

8. Mr. Rupesh Mishra | [email protected]
Line
•Collection of points over a path
•Plotting discrete points between the two endpoints.
•Calculated from the equation of the line
•Frame buffer loaded with intensity value at the corresponding pixel coordinates.
•Video Controller plots the screen pixels
•Approximation of actual points
•(10.4, 20.5) converted to (10, 21)
•Stair-step appearance in low resolution

9. Mr. Rupesh Mishra | [email protected]
Line Drawing
•The Cartesian slope-intercept equation
for a straight line
•
•
• intercept
•Given end point of line
•
•
y=m⋅x+c
m:Slope
c:y
(x
1
,y
1
),(x
2
,y
2
)
m=
(y
2
−y
1
)
(x
2−x
1)
c=y
1−m⋅x
1
Line Segment
Y intercept
x intercept
(x
1,y
1)
(x
2,y
2)
x axis
Y axis

10. Mr. Rupesh Mishra | [email protected]
•For any given interval along a line, we
can compute the corresponding y interval
•
•Similarly
•
x Δx
Δy
Δy=m.Δx
Δx=
Δy
m
Δy
Δx

11. Mr. Rupesh Mishra | [email protected]
Δy
Δx Δx
Δy
Δx
Δy
For angle more than 45
∘
Δy
Δx
>1
For angle less than 45
∘
Δy
Δx
<1
For angle equal 45
∘
Δy
Δx
=1

12. Mr. Rupesh Mishra | [email protected]
Digital Differential Analyser
•Scan-conversion line algorithm
•Calculating either or
•Sample the line at unit intervals in one coordinate
•Determine corresponding integer values nearest the line path for the other
coordinate.
•DDA algorithm works even if points are reversed
ΔxΔy
DDA

13. Mr. Rupesh Mishra | [email protected]
(1)Compute


(2)If then

else
Δx=x
2
−x
1
Δy=y
2−y
1
abs(Δx)>abs(Δy)
steps=abs(Δx)
steps=abs(Δy)
(3)
(4)
(5)repeat for all steps
x
inc
=
Δx
steps
y
inc=
Δy
steps

14. Mr. Rupesh Mishra | [email protected]
Limitation of DDA
•Time Consuming
•Floating Point Numbers
•Roundoff Error

15. Mr. Rupesh Mishra | [email protected]

16. Mr. Rupesh Mishra | [email protected]
Bresenham's Line Algorithm

17. Mr. Rupesh Mishra | [email protected]
•Accurate and efficient raster line-generating
algorithm
•Using only incremental integer calculations
•Sampling at unit intervals
•Decide possible pixel positions closer to
the line path at each sample step.
•Weather to plot pixel at position
in the next step
•Testing the sign of an integer parameter,
whose value is proportional to the
difference between the separations of the
two pixel positions from the actual line
path.
x
(11,11)or(11,12)
10
11
12
13
14
10 11 12 13
.
..
.

18. Mr. Rupesh Mishra | [email protected]
d
u
d
l






Decisión parameter
y=mx+c
y=m(x
k+1)+c
d
l=y−y
k=[m(x
k+1)+c]−y
k
d
u
=y
k+1
−y=y
k+1
−[m(x
k
+1)+c]
if(d
l−d
u<0)−>y
k
if(d
l−d
u>0)−>y
k+1
x
k
y
k+1
y
k
x
k+1
y

19. Mr. Rupesh Mishra | [email protected]








d
l
−d
u
=[[m(x
k
+1)+c]−y
k
]−[y
k+1
−[m(x
k
+1)+c]]
d
l
−d
u
=m(x
k
+1)+c−y
k
−y
k+1
+m(x
k
+1)−c
d
l−d
u=2m(x
k+1)−2y
k+2c−1
m=
Δy
Δx
d
l
−d
u
=
2Δy
Δx
(x
k
+1)−2y
k
+2c−1
d
l−d
u=Δx[
2Δy
Δx
(x
k+1)−2y
k+2c−1]
Δx(d
l−d
u)=2Δy(x
k+1)−2Δxy
k+2Δxc−Δx
p
k=Δx(d
l−d
u)=2Δyx
k+2Δy−2Δxy
k+2Δxc−Δx
p
k=Δx(d
l−d
u)=2Δyx
k−2Δxy
k

20. Mr. Rupesh Mishra | [email protected]










p
k
=2Δyx
k
−2Δxy
k
p
knext
=2Δyx
knext
−2Δxy
knext
p
knext
−p
k
=2Δyx
knext
−2Δxy
knext
−2Δyx
k
+2Δxy
k
p
knext
−p
k
=2Δy(x
knext
−x
k
)−2Δx(y
knext
−y
k
)
p
knext−p
k=2Δy(x
knext−x
k)−2Δx(y
knext−y
k)
if(p
knext
−p
k
)<0
p
knext
=p
k
+2Δy(x
knext
−x
k
)−2Δx(y
knext
−y
k
)
p
knext
=p
k
+2Δy
if(p
knext
−p
k
)>=0
p
knext=p
k+2Δy(x
knext−x
k)−2Δx(y
knext−y
k)
p
knext=p
k+2Δy−2Δx

21. Mr. Rupesh Mishra | [email protected]
Initial Decision Parameter




p
0
=2Δyx
1
+2Δy−2Δxy
1
+2Δxc−Δx
c=y−
Δy
Δx
x
1
p
0
=2Δyx
1
+2Δy−2Δxy
1
+2Δx[y−
Δy
Δx
x
1
]−Δx
p
0=2Δyx
1+2Δy−2Δxy
1+2Δxy
1−2Δyx
1−Δx
p
0=2Δy−Δx

22. Mr. Rupesh Mishra | [email protected]
Algorithm breshanmsLine( )
______________________________________





x
1
,y
1
,x
2
,y
2
x=x
1
y=y
1
dx=x
2
−x
1
dy=y
2
−y
1
p=2dy−dx







while(x<=x
2
)
putpixel(x,y)
x++
if(p<0)
p=p+2dy
else
p=2dy−2dx+p
y++

23. Mr. Rupesh Mishra | [email protected]
x Y P
9 18 3
10 19 1
11 20 -1
12 20 7
13 21 5
14 22 3












x=x
1
y=y
1
dx=x
2−x
1
dy=y
2
−y
1
p=2dx−dy
while(x<=x
2)
putpixel(x,y)
x++
if(p<0)
p=p+2dy
else
p=2dy−dx+p
y++
(9,18) (14,22)
dx=14−9=5
dy=22−18=4
p=(2*4)−5=3
pnext=3+(2*4)−(2*5)=1

24. Mr. Rupesh Mishra | [email protected]
Y axis
15
16
17
18
19
20
21
22
23
24
25
X axis
678910111213141516

25. Mr. Rupesh Mishra | [email protected]
x Y P
20 10
21 11 6
22 12 2
23 12 -2
24 13 14
25 14 10
26 15 6
27 16 2
28 16 -2
29 17 14
30 18 10
dx= 10
dy= 8
p=6
2dy = 16
2dy-2dx=-4

26. Mr. Rupesh Mishra | [email protected]
x Y P
2 3
3 4 7
4 5 11
5 6 15
6 7 19
dx= 3
dy= 5
p=7
2dy = 10
2dy-2dx=4
(2,3) and (5,8)

27. Mr. Rupesh Mishra | [email protected]
Circle

28. Mr. Rupesh Mishra | [email protected]
•Frequently used component in
image and graph
•Properties of Circles
•A Circle is defined as the set of
points that are all at a given
distance r from a centre position
•
•Distance Relationship
Center(x
c,y
c)
(x−x
c
)
2
+(y−y
c
)
2
=r
2
•Scan conversion
•Calculate the position of points
on a circle circumference by
stepping along the x axis in unit
step
•
•Calculate

•Not a best method
•Lot of computation
•Unequal spacing
(x
c
−r)to(x
c
+r)
y=y
c
±(r
2
−(x
c
−x)
2
r
x
y
(x
c
,y
c
)

29. Mr. Rupesh Mishra | [email protected]
•Calculate points along the circular boundary using polar
coordinates r and
•Circle equation in parametric polar form
•
•
•Generated with these equations using a fixed angular step size
•The step size chosen for 8 depends on the application and the
display device
•
Step size at
•Plots pixel positions that are approximately one unit apart.
θ
x=x
c
+r⋅cosθ
y=y
c
+r⋅sinθ
1
r
Uniform Spacing

30. Mr. Rupesh Mishra | [email protected]
•Symmetry of Circle
•Shape of the circle is similar in each quadrant
•Generate the circle section in the second quadrant
•The section of circle is symmetric across y axis
•Above section of circle to generate III and IV quadrant
•One step further
•Symmetry between octant
•A one-eighth circle sector is mapped to seven circle points
in the other octants of the plane
•Cartesian equation - multiplications and square root
•Parametric equations - Multiplications & Trigonometric
•Incremental calculation of decision parameters
xy
Computations
.
(x,y)
.
(x,−y)
.
(y,x)
.
(y,−x)
.
(−y,−x)
.
(−x,−y)
.
(−y,x)
.
(−x,y)

31. Mr. Rupesh Mishra | [email protected]
Midpoint Circle Algorithm

32. Mr. Rupesh Mishra | [email protected]
•Center
•
•
•For any pixel
•
•
(0,0)
x
2
+y
2
=r
2
x
2
+y
2
−r
2
=0
(x
1
,y
1
)
x
2
1
+y
2
1
−r
2
=?
res=?
•If
•Point Lies on the Circle
•If
•Point Lies inside the Circle
•If
•Point Lies outside the Circle
(res=0)
(res<0)
(res>0)
Circle Equation

33. Mr. Rupesh Mishra | [email protected]
.
.
(x
1
,y
1
)
r
.
<r
.
>r
(x
2
,y
2
)
(x
3
,y
3
)
•
•
•Point Lies on the Circle
•
•Point Lies inside the Circle
•
•Point Lies outside the Circle
x
2
+y
2
−r
2
=0
x
2
1
+y
2
1
=r
2
x
2
1
+y
2
1
<r
2
x
2
1
+y
2
1
>r
2
(0,0)

34. Mr. Rupesh Mishra | [email protected]
.
.
.
.
.
.
.
.
.
.
. South Pixel
South East Pixel
.Starting Pixel (0, r)
Point−>(x
k,y
k)
(x
k
+1,y
k
)
(x
k
+1,y
k
−1)
(x
k,y
k)(x
k+1,y
k)
(x
k
+1,y
k
−1)
X always increases
Midpoint ( Decision Parameter )
.
If Mid Point is inside the circle P < 0
Select South Pixel
If Mid Point is Outside the circle P > 0
Select South East Pixel
(x
k
+1,y
k
)
(x
k
+1,y
k
−1)

35. Mr. Rupesh Mishra | [email protected]
Midpoint




midpoint=[
x
k+1
+x
k+1
2
,
y
k
+y
k−1
2
]
midpoint=[
x
k+1+x
k+1
2
,
y
k+y
k−1
2
]
midpoint=[x
k+1,y
k−
1
2
]
midpoint=[x
k+1
,y
k−
1
2
]
midpoint=[x
m
,y
m
]
(x
k+1,y
k)
(x
k
+1,y
k
−1)
.
.

36. Mr. Rupesh Mishra | [email protected]

Decision Parameter





midpoint=[x
m
,y
m
]
(p
k)
p
k=x
2
m+y
2
m−r
2
p
k
=x
2
k+1
+y
2
k−
1
2
−r
2
p
k+1
=(x
k+1
+1)
2
+(y
k+1
−
1
2
)
2
−r
2
p
k+1
−p
k
=(x
k+1
+1)
2
+(y
k+1
−
1
2
)
2
−r
2
−x
2
k+1
−y
2
k−
1
2
+r
2
p
k+1−p
k=(x
k+1+1)
2
+(y
k+1−
1
2
)
2
−(x
k+1)
2
−y
2
k−
1
2
p
k+1
−p
k
=(x
k
+2)
2
+(y
k+1
−
1
2
)
2
−(x
k
+1)
2
−y
2
k−
1
2

37. Mr. Rupesh Mishra | [email protected]
•

•

•

•
•
•
•
•
p
k+1
−p
k
=(x
k
+2)
2
+(y
k+1
−
1
2
)
2
−(x
k
+1)
2
−y
2
k−
1
2
p
k+1
−p
k
=(x
2
k
+4+4x
k
)+(y
2
k+1
+
1
4
−y
k+1
)−(x
2
k
+1+2x
k
)−(y
2
k
+
1
4
−y
k
)
p
k+1−p
k=x
2
k
+4+4x
k+y
2
k+1
+
1
4
−y
k+1−x
2
k
−1−2x
k−y
2
k
−
1
4
+y
k
p
k+1
−p
k
=2x
k
+3+y
2
k+1
−y
k+1
−y
2
k
+y
k
p
k+1=p
k+2x
k+3+y
2
k+1
−y
2
k
−y
k+1+y
k
if(p
k>0)
y
k+1=?
y
k+1
=y
k
−1

38. Mr. Rupesh Mishra | [email protected]




p
k+1=p
k+2x
k+3+y
2
k+1
−y
2
k
−y
k+1+y
k
if(p
k
<0)
y
k+1
=y
k
p
k+1=p
k+2x
k+3+y
2
k
−y
2
k
−y
k+y
k
p
k+1
=p
k
+2x
k
+3




if(p
k>0)
y
k+1
=y
k
−1
p
k+1
=p
k
+2x
k
+3+(y
k
−1)
2
−y
2
k
−(y
k
−1)+y
k
p
k+1=p
k+2x
k+3+y
2
k
−2y
k+1−y
2
k
−y
k+1+y
k
p
k+1
=p
k
+2x
k
−2y
k
+5

39. Mr. Rupesh Mishra | [email protected]

Initial Point





p
0
=?
(0,r)
p
0=x
2
m+y
2
m−r
2
p
0
=(x
k
+1)
2
+(y
k
−
1
2
)
2
−r
2
p
0=(0+1)
2
+(r−
1
2
)
2
−r
2
p
0
=(0+1)
2
+(r
2
−r+
1
4
)−r
2
p
0=
5
4
−r

40. Mr. Rupesh Mishra | [email protected]
midpointCircle(r)
1. or
2. and project on
remaining Octant
3.Loop



p
0
=
5
4
−rp
0
=1−r
plot(x
i
,y
i
)
if(p
i
<0)then
p
i+1
=p
i
+2x
i
+3
y
i+1=y
i
x
i+1=x
i+1




project on remaining
Octant
Repeat until
if(p
i
>0)then
p
i+1=p
i+2(x
i−y
i)+5
y
i+1=y
i−1
x
i+1
=x
i
+1
plot(x
i+1
,y
i+1
)
(x>=y)

41. Mr. Rupesh Mishra | [email protected]
(1) or
(2)
(3)
(4)while






p=
5
4
−rp=1−r
x=0,y=r
plot(x,y)
(x>=y)
if(p<0)then
p=p+2x+3
if(p>0)then
p=p+2×(x−y)+5
y=y−1
x=x+1
plot(x,y)
midPointCircle(x
c,y
c,r)
p x Y
0 10
-9 1 10
-6 2 10
-1 3 10
6 4 9
-3 5 9
8 6 8
5 7 7
midPointCircle(0,0,10)
p=1−10=−9
p<0
p=(−9)+2×0+3=−6

42. Mr. Rupesh Mishra | [email protected]
(1) or
(2)
(3)
(4)while






p=
5
4
−rp=1−r
x=0,y=r
plot(x,y)
(x>=y)
if(p<0)then
p=p+2x+3
if(p>0)then
p=p+2(x−y)+5
y=y−1
x=x+1
plot(x,y)
midPointCircle(x
c,y
c,r)
p x Y
0 5
-4 1 5
-1 2 5
4 3 4
-3 4 4
midPointCircle(0,0,5)
p=1−5=−4
p<0
p=(−9)+2*0+3=−6

43. Mr. Rupesh Mishra | [email protected]
p x Y
0 10
-9 1 10
-6 2 10
-1 3 10
6 4 9
-3 5 9
8 6 8
5 7 7
midPointCircle(3,4,10)
p=1−10=−9
p<0
p=(−9)+2*0+3=−6
x Y
3 14
4 14
5 14
6 14
7 13
8 13
9 12
10 11

44. Mr. Rupesh Mishra | [email protected]
p x Y
0 8
-7 1 8
-4 2 8
1 3 7
-6 4 7
3 5 6
midPointCircle(5,5,8)
x Y
5 13
6 13
7 13
8 12
9 12
10 11

45. Mr. Rupesh Mishra | [email protected]
Ellipse
x
2
r
2
x
+
y
2
r
2
y
=1
(0,0) r
x
r
y
⋅
R1
R2
Sample x point
Sample y point
Slope = -1
Slope < -1
Slope > -1

46. Mr. Rupesh Mishra | [email protected]
•An ellipse is an elongated circle
•An ellipse is defined as the set of
points such that the sum of the
distances from two fixed positions
(foci) is the same for all points
•
•
•
•
P=(x,y)
d
1:DistancefromtheFirstfoci
d
2
:DistancefromtheSecondfoci
d
1+d
2=constant

47. Mr. Rupesh Mishra | [email protected]
•Focal Coordinates
•
•
•
•squaring this equation, isolating the remaining radical
•
•Evaluation of the coefficients
•Focal Coordinates
•Dimensions of the major and minor axes
•Ellipse equations are greatly simplified if the major and minor axes are oriented to
align with the coordinate axes.
F
1
=(x
1
,y
1
)
F
2
=(x
2
,y
2
)
(x−x
1)+(y−y
1)+(x−x
2)+(y−y
2)=constant
Ax
2
+By
2
+Cxy+Dx+Ey+F=0

48. Mr. Rupesh Mishra | [email protected]
•Ellipse in standard position
•Major and Minor axes oriented
parallel to the x and y axes
•
•
•The equation of the ellipse in terms
of the centre coordinates
and parameters and
•

•Center
•

•Using polar coordinates
•
•
•Symmetry considerations can be
used to further reduce computation
•Symmetric between quadrants
r
x
semimajoraxis
r
y
semiminoraxis
(x
c,y
c)
r
xr
y
(
x−x
c
r
x
)
2
+(
y−y
c
r
y
)
2
=1
(0,0)
(
x
r
x
)
2
+(
y
r
y
)
2
=1
x=x
c
+r
x
cosθ
y=y
c
+r
y
sinθ
calculate pixel positions along the elliptical arc throughout one quadrant,
then we obtain positions in the remaining three quadrants by symmetry

49. Mr. Rupesh Mishra | [email protected]
Mid Point Ellipse

50. Mr. Rupesh Mishra | [email protected]
•Similar to display raster circle
•Input
•Ellipse in standard position centred
on the origin
•Translate and Rotate to orient the
Major and Minor axes
•The midpoint ellipse method is
applied throughout the first
quadrant in two parts.
•Region I
•Region II
•r
x
,r
y
,(x
c
,y
c
)
(Slopeofcurve<−1)
(Slopeofcurve>−1)
r
y
r
x
Slope<−1
Slope>−1

51. Mr. Rupesh Mishra | [email protected]
•Region I
•Unit steps in the direction
•Slope of the curve less than -1
•
•Start position
•Step clockwise along the elliptical
path in the first quadrant
•Shifting from unit steps in to unit
steps in when the slope becomes
less than
•Region II
•Unit steps in the y direction
•Slop greater than -1
•
•Start position
•Step counter clockwise along the
elliptical path in the first quadrant
•Shifting from unit steps in to unit
steps in when the slope becomes
greater than
•Parallel processing
x
|slope|<1
(0,r
y)
x
y
−1
|slope|>1
(r
x,0)
y
x
−1
Calculate pixel positions in the two regions simultaneously

52. Mr. Rupesh Mishra | [email protected]
Sequential Implementation
•Start Point
•Step along the ellipse path in
clockwise order throughout the
first quadrant.
•
•For any point
•
•
•Decision Parameter
•
•Point lies inside the ellipse
•
•Point lies on the ellipse
•
•Point lies outside the ellipse
•At each position, the next pixel
along the ellipse path is selected
• Sign of the ellipse function
evaluated at the midpoint between
the two candidate pixels.
(0,r
y
)
r
2
yx
2
+r
2
xy
2
−r
2
xr
2
y=0
(x
k
,y
k
)
r
2
y
x
2
k
+r
2
x
y
2
k
−r
2
x
r
2
y
=?
res=?
if(res<0)
if(res=0)
if(res>0)

53. Mr. Rupesh Mishra | [email protected]
•Starting Point
•Take unit steps in the direction
•Continue till the boundary between
region 1 and region 2
•Then take unit steps in the
direction over the remainder of the
curve in the first quadrant.
•At each step, test the value of the
slope of the curve.
•

•

•On the boundary
•
•
•Out of region I
•
(0,r
y
)
x
y
d
dx
(r
2
y
x
2
+r
2
x
y
2
−r
2
x
r
2
y
)=0
dy
dx
=−
2r
2
y
x
2r
2
xy
dy/dx=−1
2r
2
y
x=2r
2
x
y
2r
2
yx>=2r
2
xy
Slope

54. Mr. Rupesh Mishra | [email protected]
[Region I]
•Previous position
•Sampling position
•Midpoint between the two
candidate pixels
•
•Evaluating the decision parameter at
midpoint
•

•

•
•Mid point is inside the ellipse
•
•
•Mid point is on the ellipse
•
•
•Mid point is outside the ellipse
•
(x
k
,y
k
)
x
k+1
(x
k+1,y
k)(x
k+1,y
k−1)
MidPoint(x
k
+1,y
k
−
1
2
)
p1
k=r
2
y(x
k+1)
2
+r
2
x(y
k−
1
2
)
2
−r
2
xr
2
y
if(p1
k
<0)
(x
k+1,y
k)
if(p1
k=0)
(x
k
+1,y
k
−1)
if(p1
k
>0)
(x
k+1,y
k−1)

55. Mr. Rupesh Mishra | [email protected]







p1
k
=r
2
y
(x
k
+1)
2
+r
2
x
(y
k
−
1
2
)
2
−r
2
x
r
2
y
p1
k+1=r
2
y(x
k+1+1)
2
+r
2
x(y
k+1−
1
2
)
2
−r
2
xr
2
y
p1
k+1=r
2
y(x
k+1+1)
2
+r
2
x(y
k+1−
1
2
)
2
−r
2
xr
2
y
p1
k+1
−p1
k
=r
2
y
(x
k
+1+1)
2
+r
2
x
(y
k+1
−
1
2
)
2
−r
2
x
r
2
y
−r
2
y
(x
k
+1)
2
−r
2
x
(y
k
−
1
2
)
2
+r
2
x
r
2
y
p1
k+1−p1
k=r
2
y((x
k+1)
2
+1+2(x
k+1)−r
2
y(x
2
k+1+2x
k)+r
2
x(y
2
k+1+
1
4
−y
k+1)−r
2
x(y
2
k+
1
4
−y
k)
p1
k+1−p1
k=r
2
y(x
2
k
+1+2x
k+1+2x
k+2−x
2
k
−1−2x
k)+r
2
x(y
2
k+1
+
1
4
−y
k+1−y
2
k
−
1
4
+y
k)
p1
k+1−p1
k=r
2
y{2(x
k+1)+1}+r
2
x(y
2
k+1
−y
2
k
−y
k+1+y
k)
p1
k+1=p1
k+r
2
y{2(x
k+1)+1}+r
2
x(y
2
k+1
−y
2
k
−y
k+1+y
k)

56. Mr. Rupesh Mishra | [email protected]
•
•
•
•
•
•
•
p1
k+1=p1
k+r
2
y{2(x
k+1)+1}+r
2
x(y
2
k+1
−y
2
k
−y
k+1+y
k)
if(p1
k
<0)
y
k+1=y
k
p1
k+1=p1
k+2r
2
yx
k+1+1+r
2
y
if(p1
k
>=0)
y
k+1=y
k−1
p1
k+1=p1
k+2r
2
yx
k+1+1+r
2
y−2r
2
xy
k+1

57. Mr. Rupesh Mishra | [email protected]
•Initial Point
•
•

•

•

•

•
(0,r
y)
p1
k
=r
2
y
(x
k
+1)
2
+r
2
x
(y
k
−
1
2
)
2
−r
2
x
r
2
y
p1
0=r
2
y(0+1)
2
+r
2
x(r
y−
1
2
)
2
−r
2
xr
2
y
p1
0
=r
2
y
+r
2
x
(r
2
y
+
1
4
−r
y
)−r
2
x
r
2
y
p1
0=r
2
y+r
2
xr
2
y+
r
2
x
4
−r
2
xr
y−r
2
xr
2
y
p1
0=r
2
y+
r
2
x
4
−r
2
xr
y
⋅
⋅
(0,r
y)
(0,0)
Ist Quadrant

58. Mr. Rupesh Mishra | [email protected]
(0,0) r
x
r
y
⋅
Sample x point
Sample y point
Slope = -1
Slope < -1
Slope > -1
⋅⋅⋅
⋅⋅⋅(x
k
+1,y
k
−1)(x
k
,y
k
−1)
(x
k
+1,y
k
)
(x
k
+1,y
k
−1)

59. Mr. Rupesh Mishra | [email protected]
[Region II]
•Previous position
•Sampling position
•Midpoint between the two
candidate pixels
•
•Evaluating the decision parameter
at midpoint
•

•

•
•Mid point is inside the ellipse
•
•
•Mid point is on the ellipse
•
•
•Mid point is outside the ellipse
•
(x
k
,y
k
)
y
k+1
(x
k,y
k−1)(x
k+1,y
k−1)
MidPoint(x
k
+
1
2
,y
k
−1)
p2
k=r
2
y(x
k+
1
2
)
2
+r
2
x(y
k−1)
2
−r
2
xr
2
y
if(p2
k
<0)
(x
k+1,y
k−1)
if(p2
k=0)
(x
k
,y
k
−1)
if(p2
k
>0)
(x
k,y
k−1)

60. Mr. Rupesh Mishra | [email protected]







p2
k
=r
2
y
(x
k
+
1
2
)
2
+r
2
x
(y
k
−1)
2
−r
2
x
r
2
y
p2
k+1=r
2
y(x
k+1+
1
2
)
2
+r
2
x(y
k+1−1)
2
−r
2
xr
2
y
p2
k+1=r
2
y(x
k+1+
1
2
)
2
+r
2
x(y
k−1−1)
2
−r
2
xr
2
y
p2
k+1
−p2
k
=r
2
y
(x
k+1
+
1
2
)
2
+r
2
x
(y
k
−1−1)
2
−r
2
x
r
2
y
−r
2
y
(x
k
+
1
2
)
2
−r
2
x
(y
k
−1)
2
−r
2
x
r
2
y
p2k+1−p2k=r
2
y(x
2
k+1+
1
4
+xk+1)−r
2
y(x
2
k+
1
4
+xk)+r
2
x((yk−1)
2
+1−2(yk−1))−r
2
x(y
2
k+1+2yk)
p2
k+1−p2
k=r
2
y(x
2
k+1
+
1
4
+x
k+1−x
2
k
−
1
4
−x
k)+r
2
x(y
2
k
+1−2y
k+1−2y
k+2−y
2
k
−1+2y
k)
p2
k+1
−p2
k
=r
2
y
(x
2
k+1
+x
k+1
−x
2
k
−x
k
)+r
2
x
(1−2(y
k
−1))
p2
k+1=p2
k+r
2
y(x
2
k+1
+x
k+1−x
2
k
−x
k)+r
2
x(1−2y
k+1)

61. Mr. Rupesh Mishra | [email protected]
•
•
•
•
•
•
•
p2
k+1=p2
k+r
2
y(x
2
k+1
+x
k+1−x
2
k
−x
k)+r
2
x(1−2y
k+1)
if(p2
k
>0)
x
k+1=x
k
p2
k+1=p2
k−2r
2
xy
k+1+r
2
x
if(p2
k
<=0)
x
k+1
=x
k
+1
p2
k+1=p2
k+2r
2
yx
k+1−2r
2
xy
k+1+r
2
x

62. Mr. Rupesh Mishra | [email protected]
Initial Point
•Last Point of [Region I]
•Let
•

•
(x,y)
p2
k
=r
2
y
(x
k
+
1
2
)
2
+r
2
x
(y
k
−1)
2
−r
2
x
r
2
y
p2
0=r
2
y(x+
1
2
)
2
+r
2
x(y−1)
2
−r
2
xr
2
y

63. Mr. Rupesh Mishra | [email protected]
Algorithm

64. Mr. Rupesh Mishra | [email protected]
midPointEllipse
(1)
(2)
(3) ,
(4)while











(5)
(6)










(r
x
,r
y
,x
c
,y
c
)
(x
0
,y
0
)=(0,r
y
)
p1
0
=r
2
y
+
r
2
x
4
−r
2
x
r
y
dx=2r
2
yxdy=2r
2
xy
(dx<=dy)
plot(x,y)
if(p
1<0)
x=x+1
dx=2r
2
y
x
p
1
=p
1
+2r
2
y
x+r
2
y
else
x=x+1
y=y−1
dx=2r
2
y
x
dy=2r
2
x
y
p
1=p
1+2r
2
yx−2r
2
xy+r
2
y
p2
0
=r
2
y
(x+
1
2
)
2
+r
2
x
(y−1)
2
−r
2
x
r
2
y
while(y>0)
plot(x,y)
if(p
2>0)
y=y−1
dy=2r
2
x
y
p
2=p
2−2r
2
xy+r
2
x
else
x=x+1
y=y−1
dx=2r
2
yx
dy=2r
2
x
y
p
2
=p
2
+2r
2
y
x−2r
2
x
y+r
2
x

65. Mr. Rupesh Mishra | [email protected]
(x_k,y_k) P (x_k+1, y_k+1) dx dy
(0,6) -332 (1,6) 72 764
(1,6) -224 (2,6) 114 768
(2,6) -44 (3,6) 216 768
(3,6) 208 (4,5) 288 640
(4,5) -108 (5,5) 360 640
(5,5) 288 (6,4) 432 512
(6,4) 244 (7,3) 504 384
End of Region 1
midPointEllipse(r
x
:8,r
y
:6)
p1
0
=r
2
y
−r
2
x
r
y
+
1
4
r
2
x
(6)
2
−(8)
2
⋅6+
1
4
⋅(8)
2
=−332
p1<0
dx=2r
2
y⋅x
k+1
dx=2(6)
2
(1)
dy=2r
2
x⋅y
k+1
dy=2(8)
2
(6)
p1=p1+2r
2
yx+r
2
y
p1=−332+72+(6)
2
p1
4=p1
3+2r
2
yx−2r
2
xy+r
2
y
p1
4=208+(2⋅(6)
2
⋅4)−(2⋅(8)
2
⋅5)+(6)
2
p1>0

66. Mr. Rupesh Mishra | [email protected]
(x_k,y_k) P (x_k+1, y_k+1) dx dy
(6,4) 244 (7,3) 504 384
Start of Region II
(7,3) -23 (8,2) 576 256
(8,2) 361 (8,1) 576 128
(8,1) 297 (8,0) - -
midPointEllipse(r
x
:8,r
y
:6)
p2
0=r
2
y(x+
1
2
)
2
+r
2
x(y−1)
2
−r
2
xr
2
y
(36)
2
(7+
1
2
)
2
+(6)
2
(3−1)
2
−(8)
2
(6)
2
p2<0
dx=2r
2
y⋅x
k+1
dx=2(6)
2
(8)
dy=2r
2
x⋅y
k+1
dy=2(8)
2
(2)
p2=p2+2r
2
yx−2r
2
xy+r
2
x
RegionII−StartPoint(7,3)
p2=−23+576−256+64
p2>0
p2=p2−2r
2
x
y+r
2
x
p2=361−128+64