Thinking aloud on polygon filling

I've not actually done any coding on my Sam 3d experiments in a while,  
but I have been thinking a lot about the best way to implement polygon  
filling. I had a polygon filler working in a much earlier version of  
my code (see, e.g. http://uk.youtube.com/watch?v=kr_Lz98qVjE from  
about 0:39) but it only did triangles, didn't clip and generally  
wasn't really up to snuff in several ways that hit the frame rate.

Anyway, I've been playing around with a few ideas and was wondering if  
someone with a more instinctive grasp for this sort of thing might  
help out.

I previously tried using a span buffer. Each pixel span (i.e. a  
horizontal line of pixels) was inserted into a linear list of existing  
spans for that scan line, by clipping it against the spans that were  
already there then shuffling things around in memory. So there was a  
binary search and then often a small LDIR. The entire frame was drawn  
at the end. I even tried a system whereby each span list was compared  
with the previous span list and only the differences were plotted.  
That was much faster than just dumbly drawing the whole list, but  
slower than just plotting the spans to the screen and not doing the  
list search and insert. Furthermore, as you add more polygons to the  
scene, the insert gets more expensive very quickly.

Idea 1 is to divide the screen into 8×8 blocks, keep an overview that  
tags each as either block filled with a certain colour or messy. The  
polygon filler tags as many blocks as possible as completely filled,  
and consults & modifies a 1 bit mask for each run of 8 pixels in a  
messy block. So searching the existing structures for each individual  
container is faster because it's O(1), and you're doing exactly as  
much searching as you were for a 64×64 rectangle, then maybe less or