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