Hardware accelerated polygon fill using LMMM

Just to throw it in as an observation: PNG works by predicting each pixel and storing only how far wrong it was on each pixel. The objective is significantly to reduce entropy, such that the final deflate step works well. There are a small number of methods of prediction, with one being nominated per line.

One of those prediction methods is "this pixel will be the same colour as the one to its left".

If using that predictor, you'd end up with something a lot like the sparse-points image above, were you just to deflate and present without undoing the results of prediction.

I don't understand how that wasn't already achieved just by plotting colour transitions only and using Grauw's inspired XOR-along-the-horizontal final step. Anything beyond that seems to be aimed at reducing the eventual on-disk footprint of the image.

As an aside, the IIgs can do a similar thing as a hardware video mode, and it's just about the only way you might ever hope to get anywhere close to 60Hz output. The Amiga experience is also possibly interesting; its blitter has a similar (but deliberate and specific) mode, and HAM mode is another variant on the same thing.

What could be interesting would be to adapt any of the algorithms that can directly produce already-sorted lists of colour transitions and see what happens. A voxel heightfield is a very obvious one.

I can't speak for anybody else, but as I understood it the process would look like:

    while(true) {
        edges = calculate_edges();
        while(vdp_busy()) {
            for(edge in edges) {
                plot_boundary();
            }
            dispatch_fill();
        }
    }

i.e. the CPU could do the fills in a better way, but also it can instead be calculating geometry while the VDP slowly does the fills. So as long as your calculations take at least as long as the VDP takes for its length read-modify-write per-pixel XOR pass then you're saving time over having the CPU do the work.

That is, unless the cost of eliminating overdraw or of batching up the edges ends up costing more than a brute-force plot.