# rectangle fill routine for graphics 2 mode?

## Recommended Posts

Hey guys,

Do any of you have, given an X,Y (256,192) pixel position in bitmap II mode, a routine which clears the area? I currently have this being done as a series of line draws, but this is very slow.

-Thom

##### Share on other sites

You can do a fair bit to speed up line draws in bitmap. If you're treating it as a pixel-addressable space, that will be much slower than remembering it's really a character based display. I haven't published my code yet, I don't think, but there are some examples here:

If you're interested in trying to adapt them, I can post. But Rasmus also has a fast line draw that's nearly as fast as my fastest, but doesn't require you to set up and use all the registers, which can be difficult for some (most) programs to swallow. It was actually his that I was planning to put in my library.

##### Share on other sites

Ok. Cool. Right now, I have:

```/**
* screen_block_draw(Coord1, Coord2) - Perform a block fill from Coord1 to Coord2
*/
{
int y;
int mode;
int x1=min(scalex(Coord1->x),scalex(Coord2->x));
int x2=max(scalex(Coord1->x),scalex(Coord2->x));
int y1=min(scaley(Coord1->y),scaley(Coord2->y));
int y2=max(scaley(Coord1->y),scaley(Coord2->y));

screen_set_pen_mode();

if (CurMode==ModeErase)
mode=0;
else
mode=1;

for (y=y1;y<y2;y++)
{
bm_drawline(x1,y,x2,y,0);
}
}
```

-Thom

##### Share on other sites

A fast rectangle fill would deal with the edges (1-4 and 6-9 in the figure below) as special cases and use a fast, unrolled loop to fill the interior full characters (5).

122222222222223

455555555555556

455555555555556

455555555555556

455555555555556

788888888888889
I don't think I have written a routine like that before, but I imagine it would be a lot faster than drawing a number of vertical lines, which are probably plotted one pixel at a time.
Edited by Asmusr

##### Share on other sites

Filling an arbitrary area, delimited by a line, is more tricky. But also more useful.

##### Share on other sites

Filling an arbitrary area, delimited by a line, is more tricky. But also more useful.

But probably even slower than what Thom has now.

##### Share on other sites

Rasmus, what's the high-level algorithm used with your fast line drawing routine?

##### Share on other sites

But probably even slower than what Thom has now.

Yes, since in that case you don't know the boundary of the area beforehand. The idea is that you give what he actually wrote in the first post, a pixel position, not two pixels spanning a rectangle. Then, from that single position, you scout for the lines delimiting the area to fill.

Not very difficult to implement as long as the area is a box, but when the algorithm should be able to handle an arbitrary shape, then it becomes a lot more tricky. You will of course also have to check that you don't start filling outside the screen, or outside a viewport, if you implement a viewport concept.

Even if it will perform slower, the time saved when writing programs that use such a function is tremendous, if the areas you want to fill are complex.

When I wrote my line drawing algorithm, it got pretty fast when implemented in assembly language. Then I learned about Bresenham's algorithm, and tried that. It was a bit faster, since it uses a somewhat simpler math to do the same thing as I did.

##### Share on other sites

Yes, since in that case you don't know the boundary of the area beforehand. The idea is that you give what he actually wrote in the first post, a pixel position, not two pixels spanning a rectangle. Then, from that single position, you scout for the lines delimiting the area to fill.

Not very difficult to implement as long as the area is a box, but when the algorithm should be able to handle an arbitrary shape, then it becomes a lot more tricky. You will of course also have to check that you don't start filling outside the screen, or outside a viewport, if you implement a viewport concept.

Even if it will perform slower, the time saved when writing programs that use such a function is tremendous, if the areas you want to fill are complex.

When I wrote my line drawing algorithm, it got pretty fast when implemented in assembly language. Then I learned about Bresenham's algorithm, and tried that. It was a bit faster, since it uses a somewhat simpler math to do the same thing as I did.

Well it's not even a fill routine but a clear routine that Thom needs.

##### Share on other sites

Rasmus, what's the high-level algorithm used with your fast line drawing routine?

http://www.rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#C

```void line(int x0, int y0, int x1, int y1) {

int dx = abs(x1-x0), sx = x0<x1 ? 1 : -1;
int dy = abs(y1-y0), sy = y0<y1 ? 1 : -1;
int err = (dx>dy ? dx : -dy)/2, e2;

for(;{
setPixel(x0,y0);
if (x0==x1 && y0==y1) break;
e2 = err;
if (e2 >-dx) { err -= dy; x0 += sx; }
if (e2 < dy) { err += dx; y0 += sy; }
}
}
```

The trick is that setPixel should only write to the VDP when the byte is changing - not for every pixel.

##### Share on other sites

yup, nice little modify for bresenham.

-Thom

##### Share on other sites

Well it's not even a fill routine but a clear routine that Thom needs.

Sure. But a fill routine can easily be modified to clear as well as fill.

But I agree, what I referred to has nothing to do with what's asked for here. A high speed clear routine. I just thought about the closest thing I've done, in this field.

##### Share on other sites

yeah, this would essentially be a fill routine, as the color selected is either the background or foreground color (depending on the desired writing mode). If you run the current build of PLATOTerm off my server (TIPI version can be streamed), and float around in the menus, you'll see why I am trying to find a faster solution to what I have...

-Thom

##### Share on other sites

As mentioned, the GM2 (graphics mode 2, i.e. bitmap) is tile-based on the 9918A, so the fastest routines will be ones that manipulate the pixels in byte-size chunks (8 pixels at a time). Also, if you can guarantee that the blocks will be on 8-pixel boundaries, you will not have to deal with the special cases Rasmus pointed out and the routine would be simpler and faster. Also, using a buffer in 16-bit scratch pad RAM that holds one horizontal line would probably help, since the VDP address register would only need to be updated once per line.

Are you trying to do this 100% in C? Do you know any 9900 assembly and/or the details of the 9918A's memory use for GM2?

##### Share on other sites

If you are overwriting everything in the VDP memory anyway, you only need to reload the VDP write address once per row. It's only if you want to handle border cases you need to read, modify and write..

Here we're talking about drawing/erasing a line in a consecutive sequence of bytes. Using a buffer memory in such a case will only give you a redundant transfer from VDP memory to the buffer, a redundant modification to the buffer (it's mainly the same byte content that should be copied to multiple locations) and, finally, actually updating the VDP memory with the result.

You do need to go through all steps for the border cases, but they involve only a single byte per side of your area to clear.

You also have to think about that graphics 2 mode involves both a bitmap of pixels, as well as a "bytemap" of colors. Just erasing pixels doesn't necessarily say that you get to see the backdrop, as the background color for that byte of pixels may not be transparent.

##### Share on other sites

I just need a routine that works, whether it's in C, or calls assembler, doesn't matter. I am not versed in 9900 asm. I wish I could assume that I could wipe on 8 pixel boundaries, but I can't...

-Thom

##### Share on other sites

Hi Rasmus,

Thanks for sharing this link. I spent hours reading examples! I notice they don't have TMS9900 assembly, though they have Z80, 6502, PDP-11 as well as ARM and x86. And lots of 8-bit machine BASICs. I wonder if we could populate some examples?

##### Share on other sites

I just need a routine that works, whether it's in C, or calls assembler, doesn't matter. I am not versed in 9900 asm. I wish I could assume that I could wipe on 8 pixel boundaries, but I can't...

-Thom

I have started writing an optimized rectangle fill in assembly. I'll post what I have on Sunday.

The ideas above are all good;
ABC
DEF
GHI
I am covering the special case of erasing a rectangle that does not cross a tile boundary, that is A and C are within the same byte of the bitmap.
A further enhancement would check if the desired fill color is already the BG or FG color of the row.
I think Thom just needs a routine for mundane cases 1-3 though I imagine a smart case 4:
1. fill or clear, with every color byte set to one FG BG "pen" value
2. fill with just FG color written, BG unchanged
3. clear with just BG color written, FG unchanged
4. compare desired color to existing FG or BG, fill or clear accordingly, else act as FG

UPDATE: still working on this. It's going to be a big routine, around 512 bytes. I have all the "corner" (haha) cases written but not debugged. (eek, something is filling 100% of vdp ram).

pseudocode:

Process coordinates

Form bits for edge A (possibly AND with edge C)

Bitwise OR A,D,G

Find address of C relative to A

Bitwise OR C,F,I

Fill B

Fill E

Fill H

I might be able to flip the order so it goes left to right, but I have run out of temp registers!

Edited by FarmerPotato

##### Share on other sites

I have got the fast rectangle fill working. It's kind of spaghetti at this point and I am inspired to do a rewrite from the beginning.

g2 is the test driver and filare.a99 is the routine and subroutines. I did not test all the corner cases yet.

If the rewrite doesn't pan out I'll call this version 1 and get it under a C interface.

EDIT 2/19/2019: files replaced, with corner case bugs fixed. There are some logic errors where the right edge is +1 pixel, but no crashes. No color. Still needs a rewrite.

This is still just a first draft.

g2.a99

filare.a99

g2.obj

Edited by FarmerPotato

##### Share on other sites

I have got the fast rectangle fill working. It's kind of spaghetti at this point and I am inspired to do a rewrite from the beginning.

g2 is the test driver and filare.a99 is the routine and subroutines. I did not test all the corner cases yet.

If the rewrite doesn't pan out I'll call this version 1 and get it under a C interface.

Well done!

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.