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...
(x1,y1)
/\ 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
new
part 2 /XXXXXXXX| 4 a trapezoid
/XXXXXXXXX| 5
new
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
e.g.
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)
PolygonLoop:
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
WEND
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
WEND
i = height1
if height2 < i then i = height2 <-- the MINIMUM height
height1 - i
height2 - i
Trapezoid:
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
Done:
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.