THE GENESIS of 3-Dimensional Graphics

Easy to understand concepts for serious programmers.

Polygon-Clipping algorithm in screen/rasterized coordinates.



                                          E
   One way to clip a triangle            / 
   against a rectangle                  /   
                                       /     
                                      /       
                                     /         
a-----------------------------------y--------d  
|                                  /      _/ |   
|                                 /    _/    |    
|                                /  _/       |     
|                               / /          |      
|                              F-------------x-------G
|                                            |
|                                            |
|                 640 x 480                  |
|                                            |
b--------------------------------------------c

We want to clip out the invisible parts of a rasterized triangle that isn't fully visible on the screen. We will split this triangle in two triangles if we have to as shown in the example above. Note that in absolutely any case, we are going to split the triangle into a maximum of 3 triangles; THE GOLDEN RULE is that an arbitrary triangle clipped against a rectangle will always result in either 1, 2 or 3 new triangles, per 2, 4 or 6 intersections respectively.

The only SHARED SPLITTING POINT in the example above is point d, because it is located inside the polygon. If point d were lying outside the polygon, we would not consider it as a splitting point. We may have multiple shared splitting points depending on each case.

Following the example demonstrated above, to clip a polygon against an arbitrary rectangle such as the screen coordinates, we are going to start at the upper-left point "a" on the rectangle (0,0) and progress counter-clockwise, testing each of the four possible screen bounds (ab, bc, cd and da) for intersection with line spans of the triangle (EF, FG and GE).

We are going to test all 3 sides of the triangle (simultaneously) for intersection with each individual span of the clipping rectangle and are going to store a list of rectangle vs. triangle intersections as we move along in counter-clockwise fasion. We are always going to get 2, 4 or 6 intersections on the list, depending on the case.

SPLITTING POINTS are the corners of the rectangle and are always located inside the triangle. There may be 0 splitting points in special cases (look at diagram at the bottom of this page).

As shown on the diagram above, if ANY of the three triangle spans (EF,FG and GE):

1) Intersect with the currently tested span (da) on the rectangle, and also
2) Intersect with the span on the rectangle that was tested before the current one (cd)

...we are then going to split the resulting quadrilateral (x,d,y,F) into two polygons by adding a new splitting point (d) because:

a) Point d connects the currently tested span (da) and the span that was tested before the current one (cd), and
b) Point d is inside the polygon being tested

If the point d were outside the polygon (this will happen in some cases), we would not consider it as a splitting point!

The idea of this algorithm is that it is important to keep traversing the screen bound spans in either a clockwise or counter-clockwise order, as long as the order is consistent. Here, we chose counter-clockwise order, but it is not necessary.

--- Pseudocode: --------------------------------------------------------------------------

numberOfIntersections = 0
arrayIntersections = array[]

for (ab, bc, cd, da   as   rectSpan) {
  for (EF, FG, GE   as   triSpan) {
    if (triSpan intersects with rectSpan at XY) {
      arrayIntersections[ numberOfIntersections++ ] = XY
    }
  }
}

--- Something to think about -------------------------------------------------------------
       
                          
                        /////////////////
                       /                                  
                  a---N------------------------------------M---d
                  |  /                                        |
                  | /                                         |
                  |/           An interesting case #1         |
                  I            none of the rectangle points    L
                 /|            (a,b,c or d) are splitting      |
                / |            points because they are outside | 
               /  |            the triangle itself!            |  
              /   |                                            |   
             /    |                                            |    
            /     |                                            |     
           x------J--------------------------------------------K------x
                  |                                            |
                  b--------------------------------------------c

                        /////////////////
                       /                                  
                      /     a------------------------------M---d
                     /      |                                 |
                    /       |                                 |
                   /        |  An interesting case #2         |
                  /         |  point a becomes the new         L
                 /          |  splitting point because it's    |
                /           |  inside the triangle!            | 
               /            |                                  |  
              /             |                                  |   
             /              |                                  |    
            /               |                                  |     
           x----------------x----------------------------------K------x
                            |                                  |
                            b----------------------------------c

Please log in or register new account to post your opinion on this page

Other articles you might like: