5.Clipping
[prev][next]
-- ############## Start of file ############## ----

Before clipping


After clipping



Point Clipping

Display P = (x, y) if

  • xwmin <= x <= xwmax
  • ywmin <= y <= ywmax

Point Clipping

Display P = (x, y) if

  • xwmin <= x <= xwmax
  • ywmin <= y <= ywmax

Line Clipping

If both points lie inside the window

  • display segment


Point Clipping

Display P = (x, y) if

  • xwmin <= x <= xwmax
  • ywmin <= y <= ywmax

Line Clipping

If both points lie inside the window

  • display segment

If both points lie outside the same boundary

  • discard segment


Point Clipping

Display P = (x, y) if

  • xwmin <= x <= xwmax
  • ywmin <= y <= ywmax

If both points lie inside the window

  • display segment

If both points lie outside the same boundary

  • discard segment

If segment crosses one or more boundaries

  • calculate intersections with boundaries
        x = x1 + u(x2 - x1)
    y = y1 + u(y2 - y1)
    if 0 <= u <= 1 display section within boundary else discard segment


Cohen - Sutherland Line Clipping

4 bit clip code:
A B R L

Cohen - Sutherland Line Clipping

4 bit clip code:
A B R L
A = y > ywmax
B = y < ywmin
R = x > xwmax
L = x < xwmin

Cohen - Sutherland Line Clipping

4 bit clip code:
A B R L
A = y > ywmax
B = y < ywmin
R = x > xwmax
L = x < xwmin
Calculate clip code

P1 = 0 0 0 0
P2 = 0 0 0 0

--- 0 0 0 0
=> accept segment P1 P2
(trivial accept since both end points are in the window

Cohen - Sutherland Line Clipping

4 bit clip code:
A B R L
A = y > ywmax
B = y < ywmin
R = x > xwmax
L = x < xwmin
Calculate clip code

P3 = 1 0 0 1
P4 = 1 0 0 0

--- 1 0 0 0
=> reject segment P3 P4

Cohen - Sutherland Line Clipping

4 bit clip code:
A B R L
A = y > ywmax
B = y < ywmin
R = x > xwmax
L = x < xwmin
P5 = 0 0 0 1
P6 = 1 0 0 0
--- 0 0 0 0
P7 = 0 0 0 1
P8 = 1 0 0 0
--- 0 0 0 0
(1) Calculate clip code

Cohen - Sutherland Line Clipping

4 bit clip code:
A B R L
A = y > ywmax
B = y < ywmin
R = x > xwmax
L = x < xwmin
P5 = 0 0 0 1
P6 = 1 0 0 0
--- 0 0 0 0
P7 = 0 0 0 1
P8 = 1 0 0 0
--- 0 0 0 0
(1) Calculate clip code
P'5 = (xwmin, y5 + m(xwmin - x5)) P'7 = (xwmin, y7 + m(xwmin - x7))

(2) Clip against left

Cohen - Sutherland Line Clipping

4 bit clip code:
A B R L
A = y > ywmax
B = y < ywmin
R = x > xwmax
L = x < xwmin
P5 = 0 0 0 1
P6 = 1 0 0 0
--- 0 0 0 0
P7 = 0 0 0 1
P8 = 1 0 0 0
--- 0 0 0 0
(1) Calculate clip code

P'5 = (xwmin, y5 + m(xwmin - x5)) P'7 = (xwmin, y7 + m(xwmin - x7)) (2) Clip against left

P'5 = 1 0 0 0
P6 = 1 0 0 0
--- 1 0 0 0
=> reject P'5 P6
P'7 = 0 0 0 0
P8 = 1 0 0 0
--- 0 0 0 0
(3) Update clip code

Cohen - Sutherland Line Clipping

4 bit clip code:
A B R L
A = y > ywmax
B = y < ywmin
R = x > xwmax
L = x < xwmin
P5 = 0 0 0 1
P6 = 1 0 0 0
--- 0 0 0 0
P7 = 0 0 0 1
P8 = 1 0 0 0
--- 0 0 0 0
(1) Calculate clip code

P'5 = (xwmin, y5 + m(xwmin - x5)) P'7 = (xwmin, y7 + m(xwmin - x7)) (2) Clip against left

P'5 = 1 0 0 0
P6 = 1 0 0 0
--- 1 0 0 0
=> reject P'5 P6
P'7 = 0 0 0 0
P8 = 1 0 0 0
--- 0 0 0 0
(3) Update clip code

(4) Clip against right
(5) Clip against bottom

Cohen - Sutherland Line Clipping

4 bit clip code:
A B R L
A = y > ywmax
B = y < ywmin
R = x > xwmax
L = x < xwmin
P5 = 0 0 0 1
P6 = 1 0 0 0
--- 0 0 0 0
P7 = 0 0 0 1
P8 = 1 0 0 0
--- 0 0 0 0
(1) Calculate clip code

P'5 = (xwmin, y5 + m(xwmin - x5)) P'7 = (xwmin, y7 + m(xwmin - x7)) (2) Clip against left

P'5 = 1 0 0 0
P6 = 1 0 0 0
--- 1 0 0 0
=> reject P'5 P6
P'7 = 0 0 0 0
P8 = 1 0 0 0
--- 0 0 0 0
(3) Update clip code

(4) Clip against right
(5) Clip against bottom

P'8 = (x7 + (ywmax - y7) / m, ywmax) (6) Clip against top

Cohen - Sutherland Line Clipping

4 bit clip code:
A B R L
A = y > ywmax
B = y < ywmin
R = x > xwmax
L = x < xwmin
P5 = 0 0 0 1
P6 = 1 0 0 0
--- 0 0 0 0
P7 = 0 0 0 1
P8 = 1 0 0 0
--- 0 0 0 0
(1) Calculate clip code

P'5 = (xwmin, y5 + m(xwmin - x5)) P'7 = (xwmin, y7 + m(xwmin - x7)) (2) Clip against left

P'5 = 1 0 0 0
P6 = 1 0 0 0
--- 1 0 0 0
=> reject P'5 P6
P'7 = 0 0 0 0
P8 = 1 0 0 0
--- 0 0 0 0
(3) Update clip code

(4) Clip against right
(5) Clip against bottom

P'8 = (x7 + (ywmax - y7)/m, ywmax) (6) Clip against top

P'7 = 0 0 0 0
P'8 = 0 0 0 0
--- 0 0 0 0
=> accept P'7 P'8
(7) Update clip code


Cohen - Sutherland Line Clipping: Algorithm

For each line segment
  (1) compute clip codes

  (2) if both are 0 0 0 0
         accept line segment

      else if c1 & c2 != 0
         discard line segment

      else /* c1 & c2 = 0 */
         clip against left
	 clip against right
	 clip against bottom
	 clip against top

	 if anything remains
	    accept clipped segment


Cohen - Sutherland: Multiple Intersections


Cohen - Sutherland: Multiple Intersections

Clip against left

Cohen - Sutherland: Multiple Intersections

Clip against right

Cohen - Sutherland: Multiple Intersections

Clip against bottom


Parametric Line Clipping (Cyrus - Beck)

Line:
  P(t) = P0 + t(P1 - P0)
         ...
   x = x0 + (x1 - x0)t
   y = y0 + (y1 - y0)t

Parametric Line Clipping (Cyrus - Beck)

Line:
  P(t) = P0 + t(P1 - P0)
         ...
   x = x0 + (x1 - x0)t
   y = y0 + (y1 - y0)t

Intersection [ P(t) ]
Ni . [P(t) - PEi] = 0
Ni . [P0 + t(P1 - P0) - PEi] = 0
t = (Ni.[P0-PEi])/(-Ni.(P1-P0))
  = (Ni.[P0-PEi])/(-Ni. D)

Parametric Line Clipping (Cyrus - Beck)

Line:
  P(t) = P0 + t(P1 - P0)
         ...
   x = x0 + (x1 - x0)t
   y = y0 + (y1 - y0)t

Intersection [ P(t) ]
Ni . [P(t) - PEi] = 0
Ni . [P0 + t(P1 - P0) - PEi] = 0
t = ( Ni . [P0 - PEi] ) / ( -Ni . (P1 - P0))
  = ( Ni . [P0 - PEi] ) / ( -Ni . D )

Compute t for each clip rectangle edge

Discard values of t outside [0, 1]
- they're not on line segment (tr, tB,tR)

Classify other candidates more carefully (tL)


Parametric Line Clipping (Cyrus - Beck)



Cyrus - Beck: Classifying Intersections


Cyrus - Beck: Classifying Intersections

Potentially entering Intersection (PE)
  Ni . D < 0 (angle > 90o) => tL

Potentially leaving Intersection (PL)
  Ni . D > 0 (angle < 90o) => tT

Cyrus - Beck: Classifying Intersections

Potentially entering Intersection (PE)
  Ni D < 0 (angle > 90o) => tL

Potentially leaving Intersection (PL)
  Ni D > 0 (angle < 90o) => tT

Cyrus - Beck: Classifying Intersections

Potentially entering Intersection (PE)
  Ni D < 0 (angle > 90o) => tL

Potentially leaving Intersection (PL)
  Ni D > 0 (angle < 90o) => tr

Clipped Segment Defined by:
  [PEmax, PLmin]
     where PEmax = MAX ( 0, all PEs )
	   PLmin = MIN ( 1, all PLs )
     if PLmin < PEmax reject line


Cyrus - Beck Line Clipping: Algorithm

Recalculate Ni and select a PEi for each edge

for ( each line segment to be clipped) {
  if ( P1 == P0 )
     line is degenerate so clip as a point;

  else {
     tE = 0;
     tL = 1;

     for ( each candidate intersection with a clip edge ) {
	 if ( Ni .D != 0 ) { /* ignore edges parallel to line */
	      calculate t;
	      
	      use sign of Ni . D to categorize as PE or PL;
	      if ( PE ) tE = max ( tE , t );
	      if ( PL ) tL = min ( tL , t );
	 }
     }
     if ( tE > tL )
	return null;

     else
        return P(tE) and P(tL) as true clip intersections;
  }
}


Polygon Clipping


Polygon clipping - disjoint polygons.


Polygon Clipping


Polygon clipping - disjoint polygons.


Polygon Clipping


Polygon clipping - open polygons.


Polygon Clipping


Polygon clipping - open polygons.


Polygon Clipping


Polygon clipping - open polygons.



Sutherland - Hodgeman: Polygon Clipping

Original polygon


Sutherland - Hodgeman: Polygon Clipping

Clip Left


Sutherland - Hodgeman: Polygon Clipping

Clip Right


Sutherland - Hodgeman: Polygon Clipping

Clip Bottom


Sutherland - Hodgeman: Polygon Clipping

Clip Top



Sutherland - Hodgeman Polygon Clipping: Algorithm





Sutherland - Hodgeman Polygon Clipping: Algorithm



For each boundary b in [ L, R, T, B ]
    if P1 outside and P2 inside
       output intersection
       output P2
       

Sutherland - Hodgeman Polygon Clipping: Algorithm



For each boundary b in [ L, R, T, B ]
    if P1 outside and P2 inside
       output intersection
       output P2
           
    if P1 inside and P2 inside
       output P2
       

Sutherland - Hodgeman Polygon Clipping: Algorithm



For each boundary b in [ L, R, T, B ]
    if P1 outside and P2 inside
       output intersection
       output P2
           
    if P1 inside and P2 inside
       output P2
              
    if P1 inside and P2 outside
       output intersection
       

Sutherland - Hodgeman Polygon Clipping: Algorithm



For each boundary b in [ L, R, T, B ]
    if P1 outside and P2 inside
       output intersection
       output P2
           
    if P1 inside and P2 inside
       output P2
              
    if P1 inside and P2 outside
       output intersection
       
    if P1 outside and P2 outside
       do nothing 
       

Sutherland - Hodgeman Polygon Clipping: Algorithm



For each boundary b in [ L, R, T, B ]
    if P1 outside and P2 inside
       output intersection
       output P2
           
    if P1 inside and P2 inside
       output P2
             
    if P1 inside and P2 outside
       output intersection
       
    if P1 outside and P2 outside
       do nothing 
           



Sutherland - Hodgeman : An Example


in ->
P1
P2
P3
P4

Sutherland - Hodgeman : An Example


in -> [clip left] ->
P1 - in to in -> P1
P2
P3
P4

Sutherland - Hodgeman : An Example


in -> [clip left] ->
P1 - in to in --> P1
P2 - in to out -> P'2
P3
P4

Sutherland - Hodgeman : An Example


in -> [clip left] ->
P1 - in to in --> P1
P2 - in to out -> P'2
P3 - out to out -> x
P4

Sutherland - Hodgeman : An Example


in -> [clip left] ->
P1 - in to in --> P1
P2 - in to out -> P'2
P3 - out to out -> x
P4 - out to in -> P'4
               -> P4

Sutherland - Hodgeman : An Example


in -> [clip left]  -> [clip right] ->
P1 - in to in --> P1  - in to in --> P1
P2 - in to out -> P'2 - in to in --> P'2
P3 - out to out -> x
P4 - out to in -> P'4 - in to in --> P'4
               -> P4  - in to in --> P4

Sutherland - Hodgeman : An Example


in -> [clip left]  -> [clip right]  -> [clip bottom] -> 
P1 - in to in --> P1  - in to in --> P1  - in to in --> P1
P2 - in to out -> P'2 - in to in --> P'2
P3 - out to out -> x
P4 - out to in -> P'4 - in to in --> P'4
               -> P4  - in to in --> P4

Sutherland - Hodgeman : An Example


in -> [clip left]  -> [clip right]  -> [clip bottom] -> 
P1 - in to in --> P1  - in to in --> P1  - in to in --> P1
P2 - in to out -> P'2 - in to in --> P'2 - in to out -> P''2
P3 - out to out -> x
P4 - out to in -> P'4 - in to in --> P'4
               -> P4  - in to in --> P4

Sutherland - Hodgeman : An Example


in -> [clip left]  -> [clip right]  -> [clip bottom] -> 
P1 - in to in --> P1  - in to in --> P1  - in to in --> P1
P2 - in to out -> P'2 - in to in --> P'2 - in to out -> P''2
P3 - out to out -> x
P4 - out to in -> P'4 - in to in --> P'4 - out to in -> P''4
                                                     -> P'4
               -> P4  - in to in --> P4

Sutherland - Hodgeman : An Example


in -> [clip left]  -> [clip right]  -> [clip bottom] -> 
P1 - in to in --> P1  - in to in --> P1  - in to in --> P1
P2 - in to out -> P'2 - in to in --> P'2 - in to out -> P''2
P3 - out to out -> x
P4 - out to in -> P'4 - in to in --> P'4 - out to in -> P''4
                                                     -> P'4
               -> P4  - in to in --> P4  - in to in --> P4

Sutherland - Hodgeman : An Example


in -> [clip left]  -> [clip right]   -> [clip bottom]    -> [clip top] -> out
P1 - in to in --> P1  - in to in --> P1  - in to in --> P1   - in to in --> P1
P2 - in to out -> P'2 - in to in --> P'2 - in to out -> P''2 - in to in --> P''2
P3 - out to out -> x
P4 - out to in -> P'4 - in to in --> P'4 - out to in -> P''4 - in to in --> P''4
                                                     -> P'4 - in to in --> P'4
               -> P4  - in to in --> P4  - in to in --> P4   - in to in --> P4



[prev][next]
Made by dynaPage 0.2