scanline filling a trapezoid

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.