3D Coding TAT - Trapezoidal Decomposition


This is another term which I have recently learnt and it sounds like a painful booby-trap to me. It is thankfully rather easy to code and understand. We take a n-sided polygon and break it down into either triangles (3 sided) or trapezoids which are 4 sided shapes with 2 parallel sides to them, which in this case are the top and bottom lines of the shape. It's easier to explain with a diagram (except with a really naff ASCII one), so here goes...


                                /\                      0  scan line
                               /  \                     1
                              /    \                    2
                             /      \   (x2,y2)         3
                            /        |                  4
                  (x5,y5)  /         |                  5
                           \         |                  6
                            \        |                  7
                             \       |                  8
                              \______|                  9
                      (x4,y4)          (x3,y3)

If we take one ASCII line as one scan line then the above polygon can be broken down into 3 parts like this:

                             new  new
                                /\       0
                               /XX\      1
        part 1                /XXXX\     2      a triangle
                             /XXXXXX\    3

        part 2              /XXXXXXXX|   4      a trapezoid
                           /XXXXXXXXX|   5

        part 3             \XXXXXXXXX|   6      a trapezoid
                            \XXXXXXXX|   7
                             \XXXXXXX|   8
                              \XXXXXX|   9
                             new     new

The points marked 'new' indicate where a new vertex is encountered and so requires a new slope to be calculated. The bottom 2 'new' point are not used, they simply indicate that the bottom of the polygon has been found (the Y length of the slope is either 0 or -ve).

NOTE: The below pseudo-code is for reference only, it has NOT been tested and no doubt does not fully work.

                topper  is the topmost vertex index
                        (in this case is vertex 1)

                sides   is the number of polygon sides
                        (in this case 5 sides)

                X[0], X[1] ... X[n]     = polygon X coords
                Y[0], Y[1] ... Y[n]     = polygon Y coords


                index1 = topper         <--- left edge index
                index2 = topper         <--- right edge index

                height1 = 0             <--- force new left slope
                height2 = 0             <--- force new right slope

                V = Y[topper]           <--- topmost Y coordinate
                                             (the current scan line)
                WHILE height1 = 0
                                   x1 = X[index1]
                                   index1 - 1
                                   if index1 < 0 then index1 + sides
                                   height1 = Y[index1] - V
                                   if height1 < 0 then goto Done
                                   inc1 = (X[index1] - x1 ) / height1

                WHILE height2 = 0
                                   x2 = X[index2]
                                   index2 + 1
                                   if index2 >= sides then index2 - sides
                                   height2 = Y[index2] - V
                                   if height2 < 0 then goto Done
                                   inc2 = (X[index2] - x2 ) / height2

                i = height1
                if height2 < i then i = height2   <-- the MINIMUM height

                height1 - i
                height2 - i

                        Draw_Horz_line (x1,V) to (x2,V)
                        V + 1
                        x1 = x1 + inc1
                        x2 = x2 + inc2
                i - 1
                if i > 0 then goto Trapezoid

                goto PolygonLoop


1: Problems

The above code does NOT clip any out of bounds lines.

It will also lock up if the entire polygon is on the same Y line, due to the WHILE and WEND loops. One solution is to include a side counter and decrease that for each time around the WHILE loops. Or you could put an invalid Y coordinate marker to cause the height1 and height2 to become negative.

You need to use fixed-point (best) or floating-point numbers for the x1, x2, inc1 and inc2 variables as a fraction is possible (e.g. 1.5).

2: Improvements

The Trapezoid loop could be replaced with custom code for pure rectangles (with purely vertical sides) or for trapezoids with only one sloped edge and for skewed rectangles where both the inc1 and inc2 values are indentical.

Also a Bresenham type line drawing method could be used for certain slopes where the Y length is >= to the X length. This would remove the divide instruction but would require a little more code and introduce conditional jumps and more variables which could in the end make a slower polygon filler.

The divide is NOT always needed for calculating the inc1 and inc2 values (in the case of vertical lines these increments will always be zero, because 0/n is 0).

You may also wish to build a clipping algorithm into the polygon drawer itself based on the 'letterbox' method described elsewhere in this document. And you might wanna have a pure 'no-clipping-needed' polygon drawing routine.

TAD #:o)