Unit-2 PPT.ppt

Computer graphics

1. Filled Area Primitives
Module 2
Display and Drawing of Graphics Primitives

2. SPLINE CURVE
In computer graphics, a spline isa curve that
connects two or more specific points, or
that is defined by two or more points.

4. Polygon
APolygonisaplanefigurethatisboundedbyfinite
chainofstraightlinesegmentstoformaclosed
chainorloop
There are two types of polygons
1.Convex
2. Concave

5. Convex:Aconvexpolygonisapolygonin
whichthelinesegmentjoininganytwopoints
withinthepolygonliescompletelyinside
polygon.
Concave:Aconcavepolygonisapolygonin
whichthelinesegmentjoininganytwopoints
withinthepolygonmaynotliecompletely
insidepolygon.

6. Filled Area Primitives:
Forfillingagivenpictureorobjectwithcolor’s,we
candoitintwowaysinCprogramming.Thetwo
waysaregivenbelow:
UsingfillingalgorithmssuchasFloodfillalgorithm,
Boundaryfillalgorithmandscanlinepolygonfill
algorithm,wecancolortheobjects.
Usinginbuiltgraphicsfunctionssuchas
floodfill(),setfillstyle()wecanfilltheobjectwith
color’sdirectlywithoutusinganyfillingalgorithm.
Herewewillseethefillingalgorithms

7. The Filling Algorithms
Three Algorithms for filling areas:
1) Boundary Fill Algorithm
2)Flood fill Algorithm
3) Scan Line Polygon Fill Algorithm

8. Boundary Fill Algorithm:
Startatapointinsidearegionandpaintthe
interioroutwardtowardtheboundary.
Iftheboundaryisspecifiedinasinglecolor,thefill
algorithmprocessedoutwardpixelbypixeluntil
theboundarycolorisencountered.
Aboundary-fillprocedureacceptsasinputthe
coordinateoftheinteriorpoint(x,y),afillcolor,
andaboundarycolor.

9. Algorithm:
Thefollowingstepsillustratetheideaofthe
recursiveboundary-fillalgorithm:
Startfromaninteriorpoint.
Ifthecurrentpixelisnotalreadyfilledandifitis
notanedgepoint,thensetthepixelwiththefill
color,andstoreitsneighboringpixels(4or8-
connected).Storeonlyneighboringpixelthatisnot
alreadyfilledandisnotanedgepoint.
Selectthenextpixelfromthestack,andcontinue
withstep2.

10. In 4 connected approach, we can fill an object in
only 4 directions. We have 4 possibilities for
proceeding to next pixel from current pixel.
In 8 connected approach, we can fill an object in 8
directions. We have 8 possibilities for proceeding
to next pixel from current pixel.

11. Function for 4 connected approach:
void boundary_fill(intx, inty, intfcolor, intbcolor)
{
if ((getpixel(x, y) != bcolor) && (getpixel(x, y) != fcolor))
{
putpixel(x, y, fcolor);
boundary_fill(x + 1, y, fcolor, bcolor);
boundary_fill(x -1, y, fcolor, bcolor);
boundary_fill(x, y + 1, fcolor, bcolor);
boundary_fill(x, y -1, fcolor, bcolor);
}
}

12. Function for 8 connected approach:
void boundary_fill(intx, inty, intfcolor, intbcolor)
{if ((getpixel(x, y) != bcolor) && (getpixel(x, y) != fcolor))
{putpixel(x, y, fcolor);
boundary_fill(x + 1, y, fcolor, bcolor);
boundary_fill(x , y+1, fcolor, bcolor);
boundary_fill(x+1, y + 1, fcolor, bcolor);
boundary_fill(x-1, y -1, fcolor, bcolor);
boundary_fill(x-1, y, fcolor, bcolor);
boundary_fill(x , y-1, fcolor, bcolor);
boundary_fill(x-1, y + 1, fcolor, bcolor);
boundary_fill(x+1, y -1, fcolor, bcolor);
}
}

13. Flood Fill Algorithm
Sometimes we want to fill in (recolor) an area that
is not defined within a single color boundary. We
paint such areas by replacing a specified interior
color instead of searching for a boundary color
value. This approach is called a flood-fill
algorithm.
We start from a specified interior pixel (x, y) and
reassign all pixel values that are currently set to a
given interior color with the desired fill color.

14. If the area has more than one interior color, we can
first reassign pixel values so that all interior pixels
have the same color.
Using either 4-connected or 8-connected approach,
we then step through pixel positions until all
interior pixels have been repainted

16. 4 connected Flood Fill approach:
We can implement flood fill algorithm by using
recursion.
First all the pixels should be reassigned to common
color. here common color is black.
Start with a point inside given object, check the
following condition: if(getpixel(x,y)==old_col)---
old_col is common color
If above condition is satisfied, then following 4 steps
are followed in filling the object.

17. floodfill(x,y,fill_col,old_col)
{
if(getpixel(x,y)==old_col)
{
putpixel(x,y,fill_col);
flood(x+1,y,fill_col,old_col);
flood(x-1,y,fill_col,old_col);
flood(x,y+1,fill_col,old_col);
flood(x,y-1,fill_col,old_col);
}
}

18. 8 connected Flood fill approach:
We can implement flood fill algorithm by using
recursion.
First all the pixels should be reassigned to common
color. here common color is black.
Start with a point inside given object, check the
following condition: if(getpixel(x,y)==old_col)---
old_col is common color
If above condition is satisfied, then following 8 steps
are followed in filling the object.

19. floodfill(x,y,fill_col,old_col)
{if(getpixel(x,y)==old_col)
{putpixel(x,y,fill_col);
flood(x+1,y,fill_col,old_col);
flood(x-1,y,fill_col,old_col);
flood(x,y+1,fill_col,old_col);
flood(x,y-1,fill_col,old_col);
flood(x + 1, y -1, fill_col, old_col);
flood(x + 1, y + 1, fill_col, old_col);
flood(x -1, y -1, fill_col, old_col);
flood(x -1, y + 1, fill_col, old_col);
}
}

20. Scan Line Polygon Fill Algorithm
Thisalgorithmworksbyintersectingscanline
withpolygonedgesandfillsthepolygonbetween
pairsofintersections.
Algorithm:
1.Wewillprocessthepolygonedgeafteredge,and
storeintheedgeTable.
2.Storingisdonebystoringtheedgeinthesame
scanlineedgetupleas
thelowermostpoint'sy-coordinatevalueofthe
edge.

21. 3.Afteradditionofanyedgeinanedgetuple,
thetupleissortedusinginsertionsort,
accordingtoitsxofyminvalue.
4.Afterthewholepolygonisaddedtothe
edgetable,thefigureisnowfilled.
5.Fillingisstartedfromthefirstscanlineat
thebottom,andcontinuedtillthetop.
6.Nowtheactiveedgetableistakenandthe
followingthingsarerepeatedforeach
scanline:

22. i.Copyalledgebucketsofthedesignatedscanline
totheactiveedgetuple
ii.Performaninsertionsortaccordingtothexofyminvalues
iii.Removealledgebucketswhoseymaxisequal
orgreaterthanthescanline
iv.Filluppairsofedgesinactivetuple,ifanyvertexisgot,follow
theseinstructions:
oIfbothlinesintersectingatthevertexareonthesamesideof
thescanline,consideritastwopoints.
oIflinesintersectingatthevertexareatoppositesidesofthe
scanline,consideritasonlyonepoint.
v.Updatethexofyminbyaddingslopeinverseforeachbucket.

23. Inside-Outside test
Whenfillingpolygonsweshoulddecide
whetheraparticularpointisinterioror
exteriortoapolygon
Two approaches:
1. Even-odd Method
2. Winding Number Method
1. Even-odd Method:
Count=even->exterior pixel
Count=odd->interior pixel