English Amiga Board


Go Back   English Amiga Board > Coders > Coders. General

 
 
Thread Tools
Old 07 October 2021, 19:25   #1
deimos
Registered User

 
Join Date: Jul 2018
Location: Switzerland
Posts: 653
Blitter filling multiple polygons at once?

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?
deimos is offline  
Old 07 October 2021, 19:33   #2
Samurai_Crow
Total Chaos forever!

Samurai_Crow's Avatar
 
Join Date: Aug 2007
Location: Waterville, MN, USA
Age: 47
Posts: 1,810
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.
Samurai_Crow is offline  
Old 07 October 2021, 19:43   #3
deimos
Registered User

 
Join Date: Jul 2018
Location: Switzerland
Posts: 653
Quote:
Originally Posted by Samurai_Crow View Post
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.
deimos is offline  
Old 07 October 2021, 20:18   #4
a/b
Registered User

 
Join Date: Jun 2016
Location: europe
Posts: 534
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.
a/b is offline  
Old 07 October 2021, 20:27   #5
deimos
Registered User

 
Join Date: Jul 2018
Location: Switzerland
Posts: 653
Quote:
Originally Posted by a/b View Post
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?
deimos is offline  
Old 07 October 2021, 20:48   #6
a/b
Registered User

 
Join Date: Jun 2016
Location: europe
Posts: 534
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...
a/b is offline  
Old 07 October 2021, 21:07   #7
deimos
Registered User

 
Join Date: Jul 2018
Location: Switzerland
Posts: 653
Quote:
Originally Posted by a/b View Post
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.
deimos is offline  
Old 07 October 2021, 22:55   #8
Jobbo
Registered User

Jobbo's Avatar
 
Join Date: Jun 2020
Location: Druidia
Posts: 233
Quote:
Originally Posted by a/b View Post
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.
Jobbo is offline  
Old 08 October 2021, 15:38   #9
deimos
Registered User

 
Join Date: Jul 2018
Location: Switzerland
Posts: 653
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)?

Last edited by deimos; 08 October 2021 at 15:53.
deimos is offline  
Old 08 October 2021, 22:24   #10
a/b
Registered User

 
Join Date: Jun 2016
Location: europe
Posts: 534
Quote:
Originally Posted by Jobbo View Post
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.

Quote:
Originally Posted by deimos View Post
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.
a/b is offline  
Old 09 October 2021, 11:54   #11
deimos
Registered User

 
Join Date: Jul 2018
Location: Switzerland
Posts: 653
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.

Last edited by deimos; 09 October 2021 at 17:58.
deimos is offline  
Old 16 October 2021, 16:31   #12
deimos
Registered User

 
Join Date: Jul 2018
Location: Switzerland
Posts: 653
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.

Last edited by deimos; 21 November 2021 at 13:01.
deimos is offline  
Old 16 October 2021, 16:38   #13
Samurai_Crow
Total Chaos forever!

Samurai_Crow's Avatar
 
Join Date: Aug 2007
Location: Waterville, MN, USA
Age: 47
Posts: 1,810
Quote:
Originally Posted by deimos View Post
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.
Samurai_Crow is offline  
Old 22 October 2021, 14:21   #14
deimos
Registered User

 
Join Date: Jul 2018
Location: Switzerland
Posts: 653
Is there an easy formula to work out, approximately, how long a blitter operation will take?
deimos is offline  
Old 22 October 2021, 21:46   #15
paraj
Registered User

 
Join Date: Feb 2017
Location: Denmark
Posts: 118
Quote:
Originally Posted by deimos View Post
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.
paraj is offline  
Old 23 October 2021, 06:43   #16
sandruzzo
Registered User
 
Join Date: Feb 2011
Location: Italy/Rome
Posts: 2,039
@Samurai_Crow

Actually, blitter is clocked at 7.09mhz or 7.16 mhz, according to hw manual
sandruzzo is offline  
Old 23 October 2021, 11:53   #17
deimos
Registered User

 
Join Date: Jul 2018
Location: Switzerland
Posts: 653
Quote:
Originally Posted by paraj View Post
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:

Code:
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,

Code:
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?
deimos is offline  
Old 23 October 2021, 12:57   #18
a/b
Registered User

 
Join Date: Jun 2016
Location: europe
Posts: 534
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.
a/b is offline  
Old 23 October 2021, 13:06   #19
paraj
Registered User

 
Join Date: Feb 2017
Location: Denmark
Posts: 118
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.
paraj is offline  
Old 23 October 2021, 19:32   #20
deimos
Registered User

 
Join Date: Jul 2018
Location: Switzerland
Posts: 653
Thanks guys, that all makes sense. Hopefully I can do something worthwhile with the CPU while the blitter is blitting.
deimos is offline  
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Is the A500 Blitter Any Good For Drawing Polygons? Gilbert Amiga scene 14 11 December 2020 18:23
68000 vs Blitter on filling sandruzzo Coders. Asm / Hardware 44 29 September 2018 23:14
Using blitter for filling 3D polygons kovacm Amiga scene 34 25 January 2018 16:30
CPU Filling vs. Blitter Filling Routine victim Coders. General 18 26 January 2014 03:15
Filling with the blitter... Lonewolf10 Coders. Tutorials 7 13 September 2011 15:30

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 14:34.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, vBulletin Solutions Inc.
Page generated in 0.10371 seconds with 15 queries