# scanline filling a trapezoid

I have computed the four corners of the viewable bit of 2d map in my 3d view. So I know the trapezoid that is visible, and I want to 'visit' these tiles in my map.

So my algorithm is basically a convex polygon scanline fill, specifically with four points.

However, I have trouble finding simple sample code to borrow; all want to cope with the complexities of concave and complex polygons and apply winding and such, which is unnecessary in my case and cluttering.

I've contemplated sitting down and writing my own simple trapezoid scanline fill implementation from first principles but was wondering if anyone had a tried and tested version to share that I could copy instead?

Or maybe I've just been googling for the wrong terms and there are some on the net to point me at?

Since a trapezoid is made of two triangles you could just split it up and use some triangle drawing code, which I'm sure you can find plenty of examples of.

If you want to implement it yourself, all you need to do is iterate down the left and right sides of the trapezoid drawing horizontal lines between those points. Use a standard line drawing algorithm like Breshenam's for following the sides. You'll probably also need to clip off screen pixels.

• Why does he need Bresenham's to follow the sides when he filled the polygon with horizontal lines? – bummzack Aug 3 '11 at 7:06
• yes rotating it until the lowest y is at the top and then iterating down down the left and right sides is the basic approach I had in mind if I was to implement this myself... – Will Aug 3 '11 at 8:02
• @bummzack - the edges of the polygon aren't rendered by line-drawing, but they are still straight lines. You don't use Bresenhams to draw the horizontal lines, but you do use (two instances of, modified) Bresenhams to determine where those horizontal lines begin and end - where the edges of the polygon are for that cut through the polygon. – Steve314 Aug 5 '11 at 0:03

If you draw horizontal scanlines, convex polygons (including quads) divide vertically into sections as follows...

1. Possibly a triangle on the top, with a horizontal base.
2. A (possibly empty) sequence of quadrilaterals with horizontal edges top and bottom.
3. Possibly a triangle on the bottom, with a horizontal top edge.

The triangles can be viewed as quads where one of those horizontal edges just happens to have a zero length, so all you really need to worry about are quads with horizontal edges top and bottom.

There isn't a lot of simplification of this for the quads case - you'll have at most 3 parts to draw (each of the four corners on a different scanline), but that doesn't help much.

Anyway, as you scan from top to bottom, you always have a next-significant-scanline at which you'll change the left edge, the right edge, or both. Following these edges can be done with a variant of Bresenhams. Be aware, though, that it's valid for the edge to move over multiple pixels per scanline - it's not quite the standard Bresenhams algorithm you need for those edges.

You may need to clip off the top and bottom chunks with each scan-line, but the easiest way to clip stuff that's horizontally out of range is to individually clip the scanlines before drawing - without affecting the two (left and right edge) Bresenhams-algorithm states.

Often, the vertices of a polygon are stored in clockwise or counter-clockwise order to support visibility calculations. If that's the case here, it can also help with this "rendering". View the list of vertices as a circular array". Find the highest vertex/vertices and the lowest vertex/vertices. The left-edges vertices are in one span of that circular array, and the right-edges vertices in the another. One of those spans is in the correct order for rendering, the other is in the reverse order. It may be easier to make those lists of left-edge and right-edge vertices before you start, rather than work within the circular array, but it shouldn't be that difficult either way.

This kind of thing was explained well in 3D graphics books for the 16-bit era, but got more neglected when 3D graphics cards became the norm, for obvious reasons.

So I implemented my own; here's the python prototype:

class Pt:
def __init__(self,x,y):
self.x = x
self.y = y
def __repr__(self):
return "(%s,%s)"%(self.x,self.y)

class TrapeziumIterator:
def __init__(self,map,width,height,a,b,c,d):
# create an iterator over the cells in the map that are in the trapezium described by a,b,c,d corners
# a,b,c,d describes the CLOCKWISE perimeter of the trapezium, e.g. tl,tr,br,bl from screenspace
self.map = map
self.width = width
self.height = height
# we re-orientate the trapezium so the lowest y is topmost
t = [a,b,c,d]
start_y = min(pt.y for pt in t)
while t[0].y != start_y:
t.append(t[0])
del t[0]
self.t = t
# work out starting position
self.y = int(max(0,start_y)) # init y before x!
self.x = self._start_x(self.y)-1 # x is iterated in the first call to next()
# work out stopping positions
self.stop_x = self._stop_x(self.y)
self.stop_y = int(min(height,max(pt.y for pt in t)+1))
def next(self):
"return True if there is a square to be visited; then the x and y variables member are set; else return False"
self.x += 1
while self.x >= self.stop_x:
self.y += 1
if self.y >= self.stop_y:
return False # reached the end
self.x = self._start_x(self.y)
self.stop_x = self._stop_x(self.y)
assert self.x >= 0 and self.x < self.width, self.x
assert self.y >= 0 and self.y < self.height, self.y
return True # you can read the x and y member variables
def _start_x(self,y):
# go down the left side
return max(0,self._side(y,0,3))
def _stop_x(self,y):
# go down the right side
return min(self.width,self._side(y,3,0)+1)
def _side(self,y,start,stop):
inc = -1 if start < stop else 1
while self.t[stop].y < y:
start = stop
stop += inc
f = (y - self.t[start].y)
f /= (self.t[stop].y - self.t[start].y)
return int(self.t[start].x + (self.t[stop].x - self.t[start].x) * f)

def test(image,col,a,b,c,d):
w,h = image.size
it = TrapeziumIterator(image,w,h,a,b,c,d)
while it.next():
image.putpixel((it.x,it.y),col)

# test it
import Image
w,h = 100,100
image = Image.new("RGB",(w,h),(255,255,255))
test(image,(0,255,0),Pt(-60.3,-10.4),Pt(20.2,25.3),Pt(70,90.2),Pt(60,110))
test(image,(255,0,0),Pt(30.3,40.4),Pt(60.2,25.3),Pt(70,50.2),Pt(33,47.7))
# debug show it a bit larger
image = image.resize((w*6,h*6))
image.show()


The quad is described by its four corners in clockwise order. The algorithm finds the top-most corner, and then walks down the left and right sides.

• If you used the technique @Adam suggested, I believe you should accept his answer. Otherwise it would be nice if you explained what technique you used, and why. – Jonathan Connell Aug 3 '11 at 9:59
• I'd sooner accept this answer because for anyone searching for a solution to filling a trapezoid this answer will be much more useful. – Will Aug 3 '11 at 12:03
• A block of code is much less uselful than a short explanation, please at least explain what technique you used. – Jonathan Connell Aug 3 '11 at 12:05
• I was hoping for feedback along the lines of spotting off-by-one errors or a discussion of Bresenham's vs my lerp or if there was a better algorithm, or if a functor might have performance advantages in a c++ implementation? – Will Aug 3 '11 at 12:09
• codereview.stackexchange.com – Jonathan Connell Aug 3 '11 at 12:11