Clipping & Viewing (1)

Download as ppt, pdf, or txt
Download as ppt, pdf, or txt
You are on page 1of 23

U 2-Windowing & Clipping

1
2D Viewing Transformation
Clipping Window
ywmax
World Coordinates

ywmin The clipping window is


mapped into a viewport.

xwmin xwmax
Viewing world has its own
Viewport
yvmax coordinates, which may be
a non-uniform scaling of
world coordinates.

yvmin
Viewport Coordinates

xvmin xvmax
2
Clipping Algorithms
p9
Before Clipping After Clipping

p4 p10
p2 p2
p1 p1
p8
p6 p6 p8
p3 p5 p5

p7 p7

Parametric equations of line segment from  x0 , y0  to  xend , yend 

x  x0  u  xend  x0 , y  y0  u  yend  y0 , 0 u 1.

Used to determine the parts contained in clipping window.


3
Cohen-Sutherland Line Clipping Algorithm

• Step 1: Find first lines completely inside or certainly

outside clipping window.

• Step 2: Apply intersection only to undecided lines.

4
Cohen-Sutherland Line Clipping Algorithm

• Step 1:

• Assign code to every endpoint of line segment.


– Borderlines of clipping window divide the plane into two halves.

– A point can be characterized by a 4-bit code according to its


location in half planes.
– Location bit is 0 if the point is in the positive half plane, 1 otherwise.

– Code assignment involves comparisons or subtractions.

• Completely inside / certainly outside tests involve only logic


operations of bits.

5
Top bit Bottom bit Right bit Left bit

x  xwmin xwmax  x

1 0 0 1 1 0 0 0 1 0 1 0

ywmax  y

0 0 0 1 0 0 0 0 0 0 1 0

y  ywmin

0 1 0 1 0 1 0 0 0 1 1 0

Endpoint codes are 0000 for both iff line is completely inside.
If endpoint codes has 1 in same bit, line is certainly outside.
6
• Step 2:
• The intersection points with a clipping boundary can be calculuted
using the slope-intercept form of the line equation.
• Eq. for line passing through points P1 (x1, y1) and P2 (x2, y2) is
• Intersections with the clipping boundaries of the window are given
as :

• Left: (XL , y) where y = m (XL – X1 ) + Y1

• Right: (XR , y) where y = m (XR – X1 ) + Y1

• Top: (YT , x) where x = X1 + ( 1 / m ) * (YT -Y1)

• Bottom: (YB , x) where x = X1 + ( 1 / m ) * (YB -Y1)


Algorithm
1. Read two end points of the line say P1 (x1, y1) and P2 (x2 , y2).
2. Read two corners (left-top and right-bottom) of the window, say (Wx1,
Wy1) and (Wx2 ,Wy2).
3. Assign the region codes for two endpoints P1 and P2 using following
steps:
Initialize code with bits 0000
–Set Bit 1 - if (x < Wx1)
–Set Bit 2 - if (x > Wx2)
–Set Bit 3 - if (y < Wy2)
–Set Bit 4 - if (y > Wy1)

4. Check for visibility of line P1-P2


a) If region codes for both endpoints P1 and P2 are zero then the line is
completely visible. Hence draw the line and go to step 9.
b) If region codes for endpoints are not zero and the logical ANDing of them is
also nonzero then the line is completely invisible, so reject the line &go to step 9.
c) If region codes for two endpoints do not satisfy the conditions in 4(a) and 4(b)
the line is partially visible.
Algorithm( Continued..)
5. Determine the intersecting edge of the clipping window by inspecting the
region codes of two endpoints.
a) If region codes for both the end points are non-zero, find
intersection points P1’ and P2’ with boundary edges of clipping
window with respect to point P1 and point P2 , respectively.
b) If region code for any one end point is non zero then find intersection
point P1’ or P2’ with the boundary edge of the clipping window with
respect to it.
6. Divide the line segments considering intersection points.
7. Reject the line segment if any one end point of it appears outsides the
clipping window.
8. Draw the remaining line segments.
9. Stop.
Midpoint Subdivision Algorithm
• The Sutherland Cohen line clipping algorithm requires the
calculation of the intersection of the line with the window edge.

• Avoided by repetitively subdividing the line at its midpoint.

• If line is completely visible it is drawn and if it is completely


invisible it is rejected.
• If line is partially visible then it is subdivided in two equal parts.
The visibility tests are then applied to each half.
– This subdivision process is repeated until we get completely visible and
completely invisible line segments.
This is illustrated in Figure [P.T.O.]
Generalized Clipping (by Cyrus-Beck)
• Previous algorithms assume that the
clipping window is a regular rectangle.
• not applicable for non rectangular clipping
windows.
• applicable to an arbitrary convex region.
• uses a parametric equation of a line
segment to find the intersection points of
a line with the clipping edges.
12
• parametric equation of a line segment from P1 to P2 is:

– Where t is parameter
• Consider convex clipping region R
• f is boundary point of the convex region R
• n is inner normal for one of its boundaries (See fig.)

• We can distinguish in which region a point lie by looking at the


value of the dot product n . [ P(t) - f ]

13
• If dot product is negative, i.e.
n . [ P(t) - f ] < 0
then the vector [P(t)-f ] is pointed away from the interior of R.
• If dot product is zero, i.e.
n . [ P(t) - f ] = 0
then the vector [P(t)-f ] perpendicular to normal n
• If dot product is positive, i.e.
n . [ P(t) - f ] > 0
then the vector [P(t)-f] is pointed towards the interior of R( See Fig)

14
Sutherland-Hodgman Polygon Clipping
1
1’’ 1’’
1’ 3’’ 1’ 3’’
Clipping
Clipping Window 3

3’ 3’
2’ 2’’ 2’ 2’’
2
• Efficient algorithm for clipping convex polygons.

• Edges are clipped against every border line of clipping window.

• Edges are processed successively.

15
The four possible outputs generated by the left clipper, depending on
the relative position of pair of edge endpoints.

out in in in
v2
output: v1v 2 output: v 2

v2 v1
v1
v1
out out
v1
v1 output: none
v2 v1
in out
output: v1
v2
16
2
2’

3 2”

1’
3’
1
Input Left Clipper Right Clipper Bottom Clipper Top Clipper

[1,2]: (in-in)>{2}

[2,3]: (in-out)>{2’} [2,2’]:(in-in)>{2’}


[3,1]: (out-in)>{3’,1} [2’,3’]:(in-in)>{3’} [2’,3’]:(in-out)>{2”}
[3’,1]:(in-in)>{1} [3’,1]:(out-out)>{}
[1,2]:(in-in)>{2} [1,2]:(out-in)>{1’,2} [2”,1’]:(in-in)>1’}
[2,2’]:(in-in)>{2’} [1’,2]:(in-in)>{2}
[2,2’]:(in-in)>{2’}
[2’,2”]:(in-in)>{2”}

17
• The four clippers can work in parallel.
– Once a pair of endpoints it output by the first clipper,
the second clipper can start working.
– The more edges in a polygon, the more effective
parallelism is.

• Processing of a new polygon can start once first


clipper finished processing.
– No need to wait for polygon completion.

18
3D Viewing Concepts

World Coordinate System Viewing Coordinate


System

May 2010 19
Clipping window: Selects what we want to see.
Viewport: Indicates where it is to be viewed on the output
device (still in world coordinates).
Display window: Setting into screen coordinates.

In 3D the clipping is displayed on the view plane, but


clipping of the scene takes place in the space by a clipping
volume.

3D transformation pipeline is similar to 2D with addition of


projection transformation.
May 2010 20
3D Viewing Transformation Pipeline
Modeling World Viewing
Coordinates Coordinates Coordinates

Construct World-
Coordinate Scene Convert World-
Coordinates to Projection
From Modeling-
Coordinate Viewing- Transformation
Transformations Coordinates

Projection Coordinates

Transform Projection- Normalized Device


Coordinates Map Normalized- Coordinates
Coordinates to
Coordinates to
Normalized-
Device-Coordinates
Coordinates

May 2010 21
Model is given in model (self) coordinates.
Conversion to world coordinates takes place.

Viewing coordinate system which defines the position and


orientation of the projection plane (film plane in camera) is
selected, to which scene is converted.

2D clipping window (lens of camera) is defined on the


projection plane (film plane) and a 3D clipping, called view
volume, is established.
May 2010 22
The shape and size of view volume is defined by the
dimensions of clipping window, the type of projection and
the limiting positions along the viewing direction.

Objects are mapped to normalized coordinated and all


parts of the scene out of the view volume are clipped off.
The clipping is applied after all device independent
transformation are completed, so efficient transformation
concatenation is possible.

Few other tasks such as hidden surface removal and


surface rendering take place along the pipeline.
May 2010 23

You might also like