Polygons

Convex Polygon
Concave Polygon
 Complex Polygon
Polygons which are neither convex nor
concave are called a complex polygon.
Complex polygons are self-intersecting or
overlapping.
Even-Odd Test
Inside Test
We can cdassify polygon in one of the
following categories :
• Convex polygon
• Concave polygon
• Complex polygon
Syllabus Topics:

+ Introduction to polygon, types: convex, concave and

complex. Inside test.
+ Polygon Filling: flood fill, seed fill, scan line fill.
+ Windowing and clipping: viewing transformations, 2-D
clipping: Cohen – Sutherland algorithm line Clipping
algorithm, Sutherland Hodgeman Polygon clipping
algorithm,Weiler Atherton Polygon Clipping algorithm.
Polyline

A polyline is chain of connected line segment

When Starting and ending point of any polyline is

same i.e. when polyline is closed then it is called
polygon
Types of polygon

+ Convex Polygon and

+ Concave Polygon
Convex Polygon

It is polygon in which the line segment joining any two

points within the polygon lies completely inside the
polygon.
Properties of a Convex Polygon

+ polygon with all its interior angles less than

180°. This means that all the vertices of the
polygon will point outwards, away from the
interior of the shape.
+ A line drawn through a convex polygon will
intersect the polygon exactly twice.
Convex Polygon
Properties of a Convex Polygon
+ All the diagonals of a convex polygon lie entirely
inside the polygon.
+ The area of an irregular convex polygon can be
found by dividing it into triangles and summing the
triangle's areas.
+ Regular Polygons are always convex by definition
Concave Polygon

It is polygon in which the line segment joining any two

points within the polygon not lie completely inside the
polygon.
Properties of a Concave Polygon

+ A polygon with one or more interior angles greater

than 180°. It looks sort of like a vertex has been
'pushed in' towards the inside of the polygon.
+ A line drawn through a concave polygon,
depending on exactly where you draw it, can
intersect the polygon in more than two places.
Concave Polygon
Properties of a Concave Polygon

+ Some of the diagonals of a concave polygon will

lie outside the polygon.
+ The area of a concave polygon can be found by
treating it as any other irregular polygon. Regular
Polygons are never concave by definition.
(Triangle never be a concave)
Complex Polygon

+ A polygon which is neither convex nor concave is

referred as complex polygons
+ Intersects itself or the polygon which overlaps
itself
Representation of polygon

+ Polygon Drawing primitive approach

+ Trapezoid primitive approach
+ Line and point approach
Polygon Drawing primitive approach

On some devices polygon saved as a unit so

directly draw polygon shapes such as
drawpoly(num_ver+1, array);
Trapezoid primitive approach:-

+ Trapezoid are formed from two scan line

segment
+ Trapezoid are drawn by stepping down the line
segment
Line and point approach:-

+ Most of the graphics devices to not provide any

polygon support at all.
+ In such cases, Polygon can be broken into lines
& points and stored the full polygon in the
display file
+ The display polygon is then done using line
commands.
Line and point approach:-
 Inside test
• Once the polygon is entered in the display file, we can draw the
outline of the polygon.
• To show polygon as a solid object (Filled object) we have to
set the pixel inside the polygon as well as pixels on the
boundary of it.
• Now the question is how to determine whether or not a point is
inside of a polygon.

• Inside Test determines whether a point which is to be tested is

inside or outside the polygon, by using following methods.
 Inside test –Even odd method

• One simple method of doing this is to construct a line

segment between the point in question and a point known to
be outside the polygon.

• In this method, number of intersection area counted, if there

are odd no. of intersection (1,3,5..), then point is inside the
polygon and if there are even number of intersection(2,4,6..)
then point is outside.

• This method is also known as counting number

method.
Inside test –Even odd method
Special Cases in Even odd method

• If the intersection point is vertex of the polygon then we

have to look at the other endpoints of the two segments
which meet at this vertex.

• If these points lie on the same side of the constructed

line, then the point in question counts as an Twice
(even number) of intersections.
• If they lie on opposite sides of the constructed line, then
the point is counted as a single intersection.
Special Cases in Even odd method
 Inside test –Winding Number
• The direction number is given to all polygon edges
which indicates the direction
• Givedirection number a follows.
(1) (-1)

• we have to take sum of these direction numbers of those

lines which crosses by construction line
i.e. is drawn from point in question.
• That sum is called winding number of that point.

• The point is said to be inside when the value of winding

number is nonzero.
Inside test –Winding Number
 Polygon Filling

• It is the process of coloring in a fixed area or region.

• It also means high lighting all the pixels which lie
inside the polygon with any color then other
background color.
 Polygon Filling
• There are two basic approaches used to fill the
polygon.
• One way to fill polygon is to start from a given “seed
“point known to be inside the polygon & highlight
outward from the point in neighboring pixels. Until we
encounter the boundary pixel. The approach is called
“seed fill.”
• Another approach to fill polygon is “scan line” in
which it is checked whether pixel is inside the
polygon or outside the polygon.
 Seed Fill

• The seed fill algorithm is further classified as

○ Boundary fill

○ Flood Fill
 Boundary Fill
• In this algorithm, one point which is surely
inside the polygon is taken(seed point)from
which filling process starts.
• Boundary defines region may be either 4-
connected or 8-connected.
• Check the color of pixel If boundary color i.e pixel
are reached, pixels are highlighted (by fill colored)
& the process is continued until boundary pixels are
reached.
Boundary Fill
Boundary Fill
4-connected (Example)

Start Position
 3
1 2
2 3 1
 4
1 4 2
2 1
 1 2
2 1
5 1 5
1
1

1
Some region remains unfilled
8-connected (Example)

Start Position
4 1 5
2 3
5
4
3
2
1
 6
4 1
2 3
6
4
3
2
1
 7 8

4 1 8
2 3 7
4
3
2
1
 1 1 12
9
1 2 11
1
7
0 10
9
4 1
7
2 3
4
3
2
1
 1
9
1
1 11
7
0
10

4 1 9

2 3 7
4
3
2
1
 9
7 1
0 10
4 1 9
2 3 7
4
3
2
1
 9
7

4 1 9
2 3 7
4
3
2
1
 7

4 1
2 3
7
4
3
2
1
4 1
2 3

4
3
2
1
 1
2 3

3
2
1
 1
2

2
1
1

1
 Boundary_fill(x,y,f_color,b_color)
{
if(getpixel(x,y)!=b_color &&getpixel(x,y)!=f_color)
{
putpixel(x,y,f_color)
Boundary_fill(x+1,y,f_color,b_color)
Boundary_fill(x,y,+1f_color,b_color)
Boundary_fill(x-1,y,f_color,b_color)
Boundary_fill(x,y-1,f_color,b_color)
}
}
 Flood Fill
• Some time it is required to fill the area which not bounded by
single color.

• In such case we can fill area by replacing a specified

interior color instead of searching a specified interior
boundary color.

• Here, instead of checking boundary color, whether pixels are

having polygons original color is checked.

• Using either 4-connected or 8-connected approach step

through pixel position until all interior point has been filled.
void floodfill(int x,int y,int fill_color,int old_color)
{
if(getpixel(x,y)==old_color)
{
putpixel(x,y,fill_color);
floodfill(x+1,y,fill_color,old_color);
floodfill(x-1,y, fill_color,old_color);
floodfill(x,y+1, fill_color,old_color);
floodfill(x,y-1, fill_color,old_color);
}
}
Difficulty in seed fill Algorithm

• If some inside pixels are already displayed in fill color then

recursive branch terminates leaving further internal pixel
unfilled.

• For large polygon require large stack space

 Scanline Fill Algorithm
• Intersect scanline with polygon edges
• Fill between pairs of intersections
• Basic algorithm:
For y = ymin to ymax
1) intersect scanline y with each edge
2) sort intersections in increasing x [p0,p1,p2,p3]
3) fill pairwise (p0->p1, p2->p3, …)
• Advantage of scan-line fill: It fills in the same order
as rendering, and so can be pipelined.

11-07-202 66
0
 Scan Line Fill: What happens at edge end-point?

• Edge endpoint is duplicated.

• In other words, when a scan line intersects an edge
endpoint,
it intersects two edges.
• Two cases:
– Case A: edges are monotonically increasing or decreasing
– Case B: edges reverse direction at endpoint
• In Case A, we should consider this as only ONE
edge intersection
• In Case B, we should consider this as TWO edge intersections
Scan-line Scan-line

11-07-202 Case A Case B 67

0
 SPACIAL HANDLING (CONT.)

Case 1

Intersection points: (p0, p1, p2) ???

->(p0,p1,p1,p2) so we can still fill pairwise

->In fact, if we compute the intersection of the scanline with edge e1

and e2 separately, we will get the intersection point p1 twice. Keep both
68
of the p1.
SPACIAL HANDLING (CONT.)

Case 2

However, in this case we count p1 once (p0,p1,p2,p3),

Active Edge List
 Derive next
intersection
• Suppose that slope of the edge is
m = Dy/Dx

• Let xk be the x intercept of the current scan line, and

xk+1 be the x intercept of the next scan line, then
xk+1 = xk + Dx/Dy
xk+1 = xk + 1/m

11-07-202 71
0
 Active Edge
• Listedge table.
Start with the sorted
– In this table, there is an entry for each edge.
– Add only the non-horizontal edges into the table.
• For each edge entry, store
● (1) the x-intercept with the scan-line,
● (2) the two y-values of the edge, and
● (3) the inverse of the slope.(-1/m)
– Each scan-line entry thus contains a sorted list of
edges. The edges are sorted top to bottom (hence
-1/m).

11-07-202 Dr. Nuzhat F. Shaikh, Head, MESCoE 72

0 (Wadia)
 Active Edge
List
• Next, we process the scan lines from top to bottom.
– We maintain an active edge list for the current scan-line.
– The active edge list contains all the edges crossed by that
scan line. As we move down, update the active edge list
by the sorted edge table if necessary.
– Use iterative coherence calculations to obtain
edge intersections quickly.

73
Example is for Theory
Explanation
There are 3 steps to perform in order

– Find the intersections of the scanline with all edges of

the polygon

– Sort the intersections by increasing x coordinates, ie.

from left to right

– Make pairs of intersections and fill in colour within all

the pixels inside the pair

– List of intersection points --> 8,12,16,20
– Sorted order will be -->8,12,16,20
– Make pairs of intersection -->(8,12),(16,20)
– Fill in all the pixels with the given colour inside the
pixel
– Some scan line intersections at polygon vertices
requires special handling

– A scan line passing through vertex intersects two

polygon

– edges at that position adding two points to the list of

intersections for the scanline
2 cases

–If both lines intersecting at the vertex are on the same side
of the scanline , consider it as two points
–If lines intersecting at the vertex are on the opposite side
of the scan line consider it as a single point
Scan line y’ is intersecting with 4 edges and passing through
a vertex

•Here edges at vertex are on same side of the scanline . So

count the vertex twice
•The pairs of intersection points are (8,12),(12,14)
* Scanline y is intersecting with 5 edges and also passing
through a vertex
*The edges are on opposite side of the vertex. So count the
vertex as single intersection point
*The pairs of intersection points are (6,16),(20,22)
Example is for Understanding
Purpose for
Practical Implementation
11-07-202 82
0
 X1 Y1 X2 Y2
I 8 12 10 2
II 10 2 7 6
III 7 6 5 4
IV 5 4 3 9
11-07-202
V 3 9 8 12
0
 Is y1> y2?
Yes don’t do anything
No. Interchange x1,y1 and x2,y2

so that each edge is represented

as starting from higher y value
to lower y value

X1 Y1 X2 Y2
I 8 12 10 2
II 10 2 7 6
III 7 6 5 4
IV 5 4 3 9
11-07-202
0 V 3 9 8 12
 • All y1s are greater than
y2

X1 Y1 X2 Y2
I 8 12 10 2
II 7 6 10 2
III 7 6 5 4
IV 3 9 5 4
11-07-202
0
V 8 12 3 9
43
 • Sort on y1
• For ease of finding active edges

X1 Y1 X2 Y2
I 8 12 10 2
II 7 6 10 2
III 7 6 5 4
IV 3 9 5 4
V 8 12 3 9

11-07-202 Dr. Nuzhat F. Shaikh, Head, MESCoE 86

0 (Wadia)
 • Sorted on
y1

X1 Y1 X2 Y2
I 8 12 10 2
V 8 12 3 9
IV 3 9 5 4
II 7 6 10 2
III 7 6 5 4

11-07-202 87
0
 • Find slope and store -1/m

X1 Y1 Y2 -1/m
I 8 12 2 1/5
V 8 12 9 -5/3
IV 3 9 4 2/5
II 7 6 2 3/4
III 7 6 4 -1

11-07-202 88
0
 • Find slope and store -1/m

X1 Y1 Y2 -1/m
I 8 12 2 0.2
V 8 12 9 -1.66
IV 3 9 4 0.4
II 7 6 2 0.75
III 7 6 4 -1

11-07-202 89
0
 • Consider one scan line at a time from y(max) to y(min)
decrementing by 1 at each iteration
• y(max) = 12 and y(min) = 2
Iteration 1: y = 12
for all edges satisfying the condition (y>y2 &&
y<=y1) edge I and V
Find x2=x1+(-1/m) X1 Y1 Y2 -1/m
For I 8+0.2=8.2 (f) I 8 12 2 0.2
For V 8-1.66=6.34( c) V 8 12 9 -1.66
Pair up
IV 3 9 4 0.4
intersecting points
II 7 6 2 0.75
as
III 7 6 4 -1
(7,12) and (8,12)
11-07-202
0
11-07-202 91
0
• Iteration 2: y = 11
for all edges satisfying the condition (y>y2 && y<=y1)
edge I and V
Find x2=x1+1/m
For I 8.2+0.2=8.4 (f)
For V 6.34-1.66=4.68 (c)
Pair up intersecting
points as X1 Y1 Y2 -1/m
(5,11) and (8,11) I 8.2 12 2 0.2
V 6.34 12 9 -1.66
IV 3 9 4 0.4
II 7 6 2 0.75
11-07-202
0
III 7 6 4 -1
• Iteration 3: y = 10
for all edges satisfying the condition (y>y2 && y<=y1)
edge I and V
Find x2=x1+1/m
For I 8.4+0.2=8.6 (f)
For V 4.68-1.66=3.02 (c)
Pair up intersecting
points as X1 Y1 Y2 -1/m
(4,10) and (8,10) I 8.4 12 2 0.2
V 4.68 12 9 -1.66
IV 3 9 4 0.4
II 7 6 2 0.75
11-07-202
0
III 7 6 4 -1
• Iteration 4: y = 9
for all edges satisfying the condition (y>y2 &&
y<=y1) edge I and IV
Find x2=x1+1/m
For I 8.6+0.2=8.8 (f)
For IV 3+0.4=3.4 (c)
Pair up intersecting X1 Y1 Y2 -1/m
points as I 8.6 12 2 0.2
(4,9) and (8,9) V 3.02 12 9 -1.66
IV 3 9 4 0.4
II 7 6 2 0.75
11-07-202
0
III 7 6 4 -1
• Iteration 5: y = 8
for all edges satisfying the condition (y>y2 &&
y<=y1) edge I and IV
Find x2=x1+1/m
For I 8.8+0.2=9
For IV 3.4+0.4=3.8
Pair up
intersecting points
as
(4,8) and (9,8)

11-07-202 98
0
• Iteration 6: y = 7
for all edges satisfying the condition (y>y2 &&
y<=y1) edge I and IV
Find x2=x1+1/m
For I 9+0.2=9.2
For IV 3.8+0.4=4.2
Pair up
intersecting points
as
(5,7) and (9,7)

11-07-202 Dr. Nuzhat F. Shaikh, Head, MESCoE 10

0 (Wadia) 0
 • Iteration 7: y = 6
for all edges satisfying the condition (y>y2 && y<=y1)
edge I , IV, II and III
Find x2=x1+1/m
For I 9.2+0.2=9.4
For IV 4.2+0.4=4.6
For II 7+0.75=7.75 X1 Y1 Y2 -1/m
For III 7-1=6 I 9.2 12 2 0.2
Pair up V 3.02 12 9 -1.66
intersecting points
IV 4.2 9 4 0.4
as
II 7 6 2 0.75
(5,6) and (6,6)
(8,6) and (9,6) III 7 6 4 -1
11-07-202
0
 • Iteration 8: y = 5
for all edges satisfying the condition (y>y2 && y<=y1)
edge I , IV, II and III
Find x2=x1+1/m
For I 9.4+0.2=9.6
For IV 4.6+0.4=5
For II 7.75+0.75=8.50
For III 6-1=5 X1 Y1 Y2 -1/m
Pair up
I 9.6 12 2 0.2
intersecting points
V 3.02 12 9 -1.66
as
IV 5 9 4 0.4
(5,5) and (5,5)
(9,5) and (9,5) II 8.5 6 2 0.75
III
i
5 6 4 -1
• Iteration 9: y = 4
for all edges satisfying the condition (y>y2 &&
y<=y1) edge I and II
Find x2=x1+1/m
For I 9.6+0.2=9.8
For II 8.5+0.75=9.25
Pair up X1 Y1 Y2 -1/m
intersecting points I 9.8 12 2 0.2
as V 3.02 12 9 -1.66
IV 5 9 4 0.4
(9 ,4) and (10,4)
II 9.25 6 2 0.75
11-07-202
0 III
i
5 6 4 -1
• Iteration 10: y = 3
for all edges satisfying the condition (y>y2 &&
y<=y1) edge I and II
Find x2=x1+1/m
For I 9.8+0.2=10
For II 9.25+0.75=10
Pair up X1 Y1 Y2 -1/m
intersecting points I 10 12 2 0.2
as V 3.02 12 9 -1.66
IV 5 9 4 0.4
(10,3) and (10,3)
II 10 6 2 0.75
11-07-202
0
D r . Nuzhat F. kh , Head,
I II
Shai 5
MESCoE (
W
6
a
dia)
4 -1
57
 Clipping
● Clipping
● Line clipping
● Polygon clipping
CLIPPING
● Clipping refers to the removal of part of a scene.
● Any procedure which identifies that portion of a picture
which is either inside or outside a region is referred to as
a clipping algorithm or clipping.
● The region against which an object is to be clipped is
called clipping window. Usually it is rectangular in shape.
● Window : it is the selected area of the picture.
POINT CLIPPING

Display P = (x, y) if

xwmin <= x < = xwmax

ywmin < = y <= ywmax

Display P = (x, y) if

xwmin <= x < = xwmax

ywmin < = y <= ywmax

LINE CLIPPING

Before clipping

After clipping
LINE CLIPPING
 COHEN SUTHERLAND
LINE CLIPPING ALGORITHM
 COHEN-SUTHERLAND : WORLD
DIVISION
Space is divided into regions based on the window
boundaries
⚫ Each region has a unique four bit region code
⚫ Region codes indicate the position of the regions with
respect to the window

3 2 1 0 1001 1000 1010

above below right left
0000
Region Code Legend 0001 0010
Window

0101 0100 0110

COHEN-SUTHERLAND ALGORITHM
(Xmax,ymax)

(Xmin,ymin)

Region outcodes
COHEN-SUTHERLAND: LABELLING
Every end-point of the line is labelled with the appropriate
region code

Three cases :
Case1: Lines inside the window : not clipped

Case2: lines outside the window : Take AND operation of

the outcodes of the end points of the line. If answer of
AND operation is non zero means line is outside the
window and hence discard those lines.

Case3 : lines partially inside the window :Lines for which

the AND operation of the end coordinates is ZERO .
These are identified as partially visible lines.
Case3: Other Lines
These lines are processed as follows:
⚫ Find the intersection of those lines with the edges of window.

⚫ We can use the region codes to determine which window

boundaries should be considered for [Link]: region

code 1000 then line intersects with TOP boundary. Find
intersection with that boundary only.
⚫ Check other end of the line to get other intersection.

⚫ Draw line between calculated intersection.

Intersections are calculated as
y coordinate of the intersection point with a vertical boundary
can be calculated as

y = y1 + m(x – x1), x = xmin or xmax and

m = ( y2 – y1) / ( x2 – x1)

x coordinate of the intersection point with a horizontal

boundary can be calculated as
x = x1 + (y – y1) / m , y = ymin or ymax and
m = ( y2 – y1) / ( x2 – x1)
 COHEN-SUTHERLAND ALGORITHM
1. Read two endpoints of the line say P1 (x1,y1) and p2(x2,y2)
2. Read two corners of the window (left –top ) and (right-bottom)
say (Wx1,Wy1) and (Wx2, Wy2)
3. Assign the region codes to the end co-or of P1.
1. Set Bit 1 – if (x<xwmin)
2. Set Bit 2 – if (x >xwmax)
3. Set Bit 3 – if (y<ywmin)
4. Set Bit 4 – if (y>ywmax)

4. Apply visibility check on the line.

5. If line is partially visible then-
1. If region codes for the both end points are
non-zero , find intersection points p1’ and p2’
with boundary edges by checking the region
codes.
2. If region code for any one end point is non-zero
then find intersection point p1’ or p2’ with the
boundary edge.

6. Divide the line segments considering the intersection

points.
7. Draw the line segment
8. Stop.
POLYGON CLIPPING
Issues –
Edges of polygon need to be tested against clipping rectangle
May need to add new edges
Edges discarded or divided
Multiple polygons can result from a single polygon
Area Clipping Algorithm
+ An algorithm that clips a polygon must deal with many
different cases. The case is particularly noteworthy in
that the concave polygon is clipped into two separate
polygons. All in all, the task of clipping seems rather
complex.
+ Each edge of the polygon must be tested against each
edge of the clip rectangle; new edges must be added,
and existing edges must be discarded, retained, or
divided.
•
+ Multiple polygons may result from clipping a single
polygon. We need an organized way to deal with all
these cases.
+ Sutherland and Hodgeman developed a technique for
clipping the portions of a polygon within window. It is
used for clipping convex or concave polygon against
any convex polygon clipping windows.
SUTHERLAND-HODGMAN POLYGON
CLIPPING ALGORITHM
 SUTHERLAND-HODGMAN POLYGON
CLIPPING ALGORITHM
A technique for clipping areas developed by Sutherland &
Hodgman
Put simply the polygon is clipped by comparing it against
each boundary in turn.

Original Area Clip Left Clip Right Clip Top Clip Bottom
+ Sutherland and Hodgman's polygon-clipping algorithm
uses a divide-and-conquer strategy: It solves a series of
simple and identical problems that, when combined,
solve the overall problem.
+ The simple problem is to clip a polygon against a single
infinite clip edge. Four clip edges, each defining one
boundary of the clip rectangle, successively clip a
polygon against a clip rectangle.
+ Note the difference between this strategy for a polygon
and the Cohen-Sutherland algorithm for clipping a line:
The polygon clipper clips against four edges in
succession, whereas the line clipper tests the out-code
to see which edge is crossed, and clips only when
necessary.
 SUTHERLAND-HODGEMAN
CLIPPING
Input/output for algorithm:
Input: list of polygon vertices in order.
Output: list of clipped polygon vertices consisting of old
vertices (maybe) and new vertices (maybe)
Sutherland-Hodgman does four tests on every edge of the
polygon:
Inside – Inside ( I-I)
Inside –Outside (I-O)
Outside –Outside (O-O)
Outside-Inside(O-I)
Output co-ordinate list is created by doing these tests on every edge
of poly.
 Edge from S to P takes one of four cases:

inside outside inside outside inside outside inside outside

p s
p
s

p s
p s I

Save p Save I Save nothing Save I

and P
SUTHERLAND-HODGEMAN CLIPPING
Four cases:
1. S inside plane and P inside plane
Save p in the output-List
2. S inside plane and P outside plane
Find intersection point i
Save i in the output-List
3. S outside plane and P outside plane
Save nothing
4. S outside plane and P inside plane
Find intersection point i
Save i in the output-List, followed by P
 ALGORITHM
1. Read polygon vertices
2. Read window coordinates
3. For every edge of window do
4. Check every edge of the polygon to do 4 tests
1. Save the resultant vertices and the intersections in
the output list.
2. The resultant set of vertices is then sent for
checking against next boundary.
5. Draw polygon using output-list.
6. Stop.
Sutherland-Hodgman Area Clipping
Problem:
Algorithm works fine for convex polygons, however
extraneous lines may be displayed when clipping
concave polygons
 WEILER-ATHERTON POLYGON CLIPPING
+ Weiler-Atherton (WA) is better suited to clipping concave
polygons and can clip concave polygons to concave polygon
shaped clipping windows.
+ Instead of following a path only along edges of concave
polygon, we allow path to also follow the clipping window
boundary, whenever a polygon edge crosses to the outside of
that boundary.
+ For an outside-to-inside pair of vertices, follow the
polygon boundary.
+ For an inside-to-outside pair of vertices, follow the
window boundary in a clockwise direction.
WEILER-ATHERTON POLYGON CLIPPING
Weiler-Atherton (WA) requires to know

whether vertex list is clock-wise (cw) or

counter-clockwise (ccw) so that we can be sure

to traverse the list in a known order.

Algorithm:

1. Process polygon edges

CCW until we find edge
that exits clipping
window.
2. Now instead of
following polygon
edge, follow the
clipping window edges
in CCW direction
starting at the exit
point.
Algorithm:

+ Continue following clipping

window boundary until you
encounter another polygon
edge intersection.
+ If this intersection is
previously visited goto 3.
+ If intersection point is new,
start following polygon
edges in CCW until a
previously processed vertex
is found.
Algorithm:

3. Create a vertex list from the

visited vertices in (1) and (2).
[Link] to the
exit-intersection
point in (1) and continue
following
polygons edges by using
steps 1-3.
Weiler-Atherton Polygon
Clipping
 Weiler-Atherton Clipping
Can also be used to clip area filled polygons
with
1. Hollow areas
2. Against a polygon-shaped clipping window
Viewing
Transformation
Viewing Transformations

+ The Viewing Pipeline

+ Viewing Coordinate Reference Frame
+ Window to Viewport Coordinate
Transformation
To draw this face on Window
Model Coordinates
World Coordinates
Viewing Transformations

+ The Viewing Pipeline

+ Viewing Coordinate Reference Frame
+ Window to Viewport Coordinate
Transformation
Viewing Pipeline
The Viewing Pipeline
1. Window: Area selected in world-coordinate for
display is called window. It defines what is to be
viewed.
2. Viewport: Area on a display device in which
window image is display (mapped) is called
viewport. It defines where to display.
 2D Viewing pipeline
World: Screen:
Clipping window Viewport
ywmax yvmax

ywmin yvmin

xwmin xwmax xvmin xvmax

Clipping window: Viewport:

What do we want to see? Where do we want to see it?
H&B 8-1:258-259
• In many case window and viewport are
rectangle, also other shape may be used as
window and viewport.
• In general finding device coordinates of
viewport from word coordinates of window is
called as viewing transformation.
• Sometimes we consider this viewing
transformation as window-to-viewport
transformation but in general it involves more
steps.
• first of all we construct world coordinate scene
using modeling coordinate transformation.
• After this we convert viewing coordinates from
world coordinates using window to viewport
transformation.
• Then we map viewing coordinate to normalized
viewing coordinate in which we obtain values
in between 0 to 1.
• At last we convert normalized viewing
coordinate to device coordinate using device
driver software which provide device
specification.
• Finally device coordinate is used to display
image on display screen.
• By changing the viewport position on screen
we can see image at different place on the
screen.
• By changing the size of the window and
viewport we can obtain zoom in and zoom out
effect as per
• requirement.
• Fixed size viewport and small size window
gives zoom in effect, and fixed size viewport
and larger window gives zoom out effect.
• View ports are generally defines with the unit
square so that graphics package are more
device independent which we call as
normalized viewing coordinate
 2D Viewing pipeline
World: Screen:
Clipping window Viewport
ywmax yvmax

ywmin yvmin

xwmin xwmax xvmin xvmax

Clipping window:
Panning…
H&B 8-2:259-261
 2D Viewing pipeline
World: Screen:
Clipping window Viewport
ywmax yvmax

ywmin yvmin

xwmin xwmax xvmin xvmax

Clipping window:
Panning…
H&B 8-2:259-261
 2D Viewing pipeline
World: Screen:
Viewport
ywmax yvmax

ywmin yvmin

xwmin xwmax xvmin xvmax

Clipping window:
Zooming…
H&B 8-2:259-261
 2D Viewing pipeline
World: Screen:
ywmax Viewport
yvmax

yvmin
ywmin
xwmin xwmax xvmin xvmax

Clipping window:
Zooming…
H&B 8-2:259-261
Viewing Transformations

+ The Viewing Pipeline

+ Viewing Coordinate Reference Frame
+ Window to Viewport Coordinate
Transformation
Viewing Coordinate
Reference Frame
• We can obtain reference frame in any
direction and at any position.
• For handling such condition first of all we
translate reference frame origin to standard
reference frame origin
• and then we rotate it to align it to standard
axis.
• In this way we can adjust window in any
reference frame.
• This is illustrate by following transformation
matrix:
1. Origin is selected at some world position:
2. Established the orientation. Specify a world vector V that
defines the viewing y direction.
3. Obtain the matrix for converting world to viewing
coordinates (Translate and rotate)
Viewing Transformations

+ The Viewing Pipeline

+ Viewing Coordinate Reference Frame
+ Window to Viewport Coordinate
Transformation
Window-To-Viewport
Coordinate Transformation
+ Mapping of window coordinate to viewport
is called window to viewport
transformation.
+ We do this using transformation that
maintains relative position of window
coordinate into viewport.
+ That means center coordinates in window
must be remains at center position in
viewport.
Solving by making viewport position as subject we obtain:
+ We can also map window to viewport with
the set of transformation, which include
following sequence of transformations:

1. Perform a scaling transformation using a

fixed-point position of (xWmin,ywmin) that
scales the window area to the size of the
viewport.
2. Translate the scaled window area to the
position of the viewport.
+ For maintaining relative proportions we take (sx = sy).
in case if both are not equal then we get stretched or
contracted in either the x or y direction when displayed
on the output device.
+ Characters are handle in two different way one way is
simply maintain relative position like other primitive
and other is to maintain standard character size even
though viewport size is enlarged or reduce.
+ Number of display device can be used in application
and for each we can use different window-to-viewport
transformation.
+ This mapping is called the workstation transformation.