Blitter filling multiple polygons at once?

[deimos]

I'm looking for a challenge, and having outgrown my current polygon filling code I thought I'd try and rewrite it to fill an entire scene's polygons in a single blit.

The approach I'm considering is to rasterise the possible concave polygons so that there is an array of lists, one list per scanline, with the list containing the entry and exit points for how the scanline intersects the polygon.

That I believe is pretty standard.

Then, for each additional polygon that needs to be rendered, I want to do the same thing, but then "merge" the results, properly handling overlaps, so that later polygons will be rendered over the top of earlier ones.

I believe that's been done before, probably many times, but I haven't yet found any existing code for it. Maybe I'm not using the right search terms.

Then, want to set the bits right in some pre-cleared bitmaps so that I can do a single blitter fill operation to draw them all at once. Since the lists contain all the information needed to draw the screen, it should be possible to work out which bitplane bits so set at which points to make the blitter "change colour" as it fills the screen.

I think the disadvantages of this approach will probably outweigh the advantages, but I still think it will be a fun challenge. Does anything spring to mind that might make it unachievable?

[Samurai_Crow]

It can work. The color of the pixel to the left XORed with the color to the right wil set the polygon fill color appropriately. Also note that there's a bug in the right border to left border transition in that the fill carry doesn't reset to zero so you'll have to add another XOR at the right border to transition to the first color of the next row of pixels.

[deimos]

Originally Posted by Samurai_Crow

note that there's a bug in the right border to left border transition in that the fill carry doesn't reset to zero so you'll have to add another XOR at the right border to transition to the first color of the next row of pixels.

I did not know that.

[a/b]

That's how my latest vector routine works, I call it deferred vectors. But I only support convex polygons, for speed (each scanline only has 2 points: left edge and rights edge). I traverse the edges of a polygon and populate its span buffer (left/right edge basically), then update the global span buffer and xor the edges into bitmap (I tried drawing in a separate pass afterwards, turned out to be slower in my case). Repeat for each polygon, using reverse painters (closest to farthest). 2-pass approach makes it easier on complexity and register usage, no stack needed. And then at the end fill everything with a single blit.
First version was using triangles in a single pass, too complicated when I wanted to switch to polygons, and the code was huge because it was entirely color dependent (I have one routine for each color, hardcoded xors, e.g 3 bitplanes = 7x code). 2-pass approach only has to duplicate the second pass, so the code is much shorter.
It's cpu heavy put it pays off if you have large overlapping polygons, beats the classic tmp buffer approach. It basically makes super slow vectors acceptably slow, so don't expect anything super fast :P.

[deimos]

Originally Posted by a/b

That's how my latest vector routine works, I call it deferred vectors. But I only support convex polygons, for speed (each scanline only has 2 points: left edge and rights edge). I traverse the edges of a polygon and populate its span buffer (left/right edge basically), then update the global span buffer and xor the edges into bitmap (I tried drawing in a separate pass afterwards, turned out to be slower in my case). Repeat for each polygon, using reverse painters (closest to farthest). 2-pass approach makes it easier on complexity and register usage, no stack needed. And then at the end fill everything with a single blit.

Processing from closest to furthest sounds like a solid tip.

I don't understand the 2-passes though, what's in each pass?

[a/b]

Pass 1 is traversing the polygon edges and populating its left/right edge buffer. This is color independent. Old version with triangles was doing top to bottom left+right edge simultaneously, new version starts at any point and follows the edge clockwise, much simpler.
Pass 2 is take the polygon's left/right edge buffer from min y to max y coord, and merge it into global span buffer, which is a list of segments for each scanline, so I know what has already been drawn and only fill in empty segments. Basically for each scanline compare left/right edge to what's there and trim out what's been drawn already:
- add a new segment if there's no overlap,
- extend existing segments with new polygon if there's overlap,
- merge segments if they get connected (a gap between polygons gets filled up) so you only have a bare minimum to check next time.
Just one way of doing it...

[deimos]

Originally Posted by a/b

Pass 1 is traversing the polygon edges...

Pass 2 is... merge it into global span buffer...

Ok, same as what I came up with. I can do the rasterising and span buffer merging for sure, I'll allow for concave polygons as that's the point for me, and I'll do it front to back as you've pointed out, to minimise changes when merging.

[Jobbo]

Originally Posted by a/b

That's how my latest vector routine works, ...

a/b do you have a demo? Would be curious to see how well it's working for you.


Pretty sure Quake1's software renderer did something similar. But a Pentium is obviously much faster than a 68000.



Anyway the technique was sometimes called a span-buffer. I'm sure there's details about it in the Abrash book chronicling the Quake1 development.

[deimos]

I'll need to use exclusive fill mode and move the left hand edges further left by one pixel?

i.e. if I have a pair of adjacent spans [12..56] and [57..97], I'll write out bits to control the blitter fill at columns 11 (off), 56 (colour change) and 97 (on)?

[a/b]

Originally Posted by Jobbo

a/b do you have a demo? Would be curious to see how well it's working for you.

Nope, at this point it's just a bunch of static 2d polygons to test various overlap scenarios and some benchmarking... still under evaluation. I could see it running at 17-12.5 fps (3-4 frames per image) in 256x256x8col (320 horizontally nukes too many optimizations, and being very cpu heavy I've downgraded in the second version) with not too complex scene.

Originally Posted by deimos

I'll need to use exclusive fill mode and move the left hand edges further left by one pixel?
i.e. if I have a pair of adjacent spans [12..56] and [57..97], I'll write out bits to control the blitter fill at columns 11 (off), 56 (colour change) and 97 (on)?

Yeah, I'm using exclusive fill mode ($040 = $09f0, $0042 = $0012).
For the shared edges you can either draw them twice with eor or bchg while drawing their parent polygon, in their respective colors, and call it a day (e.g. color 2=%0010 and color 6=%0110, you draw 3 bits even though the bits in the second bitplane will cancel themselves out), or if you can... Link each edge/line of a polygon with its neighbour polygon, and do a preprocessing pass: if neghbour polygons are visible you eor their colors together and draw their shared edge in the resulting color/bitplane. So instead of, example above, drawing 3 bits you draw only 1 in the third bitplane.

[deimos]

So far I have:

An array of linked lists of "available" spans and an array of linked lists of "filled" spans".

For each polygon:

I rasterise each edge, putting the scanline intersections into an array of linked lists.

Then I iterate through the used elements of this array, processing the linked lists of intersections, first by sorting them, then by taking them in pairs, calling that a span and attempting to add it to my "filled spans" list by comparing it to the "available spans", removing the same space from the available spans as I add to the filled spans. If the new filled span touches existing ones of the same colour I expand the new span to include them and throw the originals away.

Today, I'm going to delete all of that and start over with each scanline being represented by an array of integer pairs, each pair representing the start of a span and that span's colour, with -1 meaning available / the end of a span. I think I can make this much more efficient and it could be easier and smaller to code.

Tomorrow, I'll start talking to the blitter.

If filling with the blitter is supposed to be done in decrement mode, bottom to top, can I set the modulos for my interleaved bitmaps to change them to go from bottom to top in memory, start the blitter fill during a vertical blank, and have it keep ahead of the beam, avoiding the need to double buffer?

Tip of the day: Static initialisation of C++ flexible array members is broken in GCC versions < 11.3.

[deimos]

So, I finally got this to work. Am I right that it takes about one and a third frames, i.e. around 0.027 seconds, to blitter fill a 320x256 4bp screen? Seems a lot.

[Samurai_Crow]

Originally Posted by deimos

So, I finally got this to work. Am I right that it takes about one and a third frames, i.e. around 0.027 seconds, to blitter fill a 320x256 4bp screen? Seems a lot.

That sounds about right. The blitter is only clocked at 3.5 MHz with a 2-stage pipeline.

[deimos]

Is there an easy formula to work out, approximately, how long a blitter operation will take?

[paraj]

Originally Posted by deimos

Is there an easy formula to work out, approximately, how long a blitter operation will take?

The formula in the hardware reference manual is a decent approximation: http://amigadev.elowar.com/read/ADCD.../node012A.html. There are many caveats, but start from there.

[sandruzzo]

@Samurai_Crow

Actually, blitter is clocked at 7.09mhz or 7.16 mhz, according to hw manual

[deimos]

Originally Posted by paraj

The formula in the hardware reference manual is a decent approximation: http://amigadev.elowar.com/read/ADCD.../node012A.html. There are many caveats, but start from there.

Thanks.

The formula then is:

t = n * H * W
    ---------
      7.09

where t is time taken in microseconds, n is the cycles required per word, H is the height and W is the width in words.

I can't see anything about what n should be for fill mode, except for other posts here that suggests fills take 3 cycles, so I assume that means 6?

So,

t = 6 * (4 * 256) * 20
    ------------------
           7.09

 = 17,331us

 ~ 0.017s

Which is the right order of magnitude, but a bit lower than what I'm seeing. Maybe I've guessed the wrong value for n, or, as you said, caveats.

Another question I have is about setting the vertical size of the blit. I only noticed yesterday that the 10 bits I have in BLTSIZE for the vertical size won't hold the value, 1024, that I've been putting in. Does a vsize value of 0 get treated as 1024, or does my code only look like it's working?

[a/b]

Those numbers are "theoretical" and don't include the cycles stolen by other DMA and the CPU.

For BLTSIZE:
- horizontal size 0 => 64 words (width=1024)
- vertical size 0 => 1024 lines (height=1024)
That's because if either width or height is 0, there's no point in blitting.

[paraj]

Easy question first, yes 0 = 1024 (for both vertical and horizontal size).

There's more discussion about fill timing in this old thread: http://eab.abime.net/showthread.php?t=68708

The time the estimate gives is the absolute minimum it'll take, in practice it will always take longer. Sometimes much longer due to higher priority DMA usage.

The next page http://amigadev.elowar.com/read/ADCD.../node012B.html details it.

Each scanline has 226 DMA slots, 4 are used for RAM refresh and are never available meaning the blitter will at most get 222 even if display is turned off. That's why Toni makes this estimate in the linked thread: "320x256 single bitplane blitter fill takes about 70 scanlines if all DMA slots are free."

Blitter cycles needed: 3 * 256 * (320)/16 = 15360

Scalines: 15360 / 222 ~= 70

If you have bitplanes enabled that cuts into the number of available slots. In the visible area only 222-4*20 = 142 slots are available for the blitter (assuming 4BPL screen).

Probably easier to think of a full frame. Maximum available DMA slots: 222 slots/line * 313 lines = 69486. 4 BPL 320*256 screen needs 320*256*4/16=20480. Available for blitter (assuming no sound, copper, etc.): 49006.

Cycles needed to fill 4 BPL 320x256: 3 * 256 * (320)/16 * 4 = 61440.

So you need at least 61440/49006 ~= 1.26 frame. At 50Hz that gives ~0.025s. Pretty close to the actual time you observe. You probably have copper enabled and there's some setup time etc.

[deimos]

Thanks guys, that all makes sense. Hopefully I can do something worthwhile with the CPU while the blitter is blitting.