rectangle fill routine for graphics 2 mode?

[tschak909]

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

[Tursi]

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.

[tschak909]

Ok. Cool. Right now, I have:

/**
 * screen_block_draw(Coord1, Coord2) - Perform a block fill from Coord1 to Coord2
 */
void screen_block_draw(padPt* Coord1, padPt* 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

[Asmusr]

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 February 5, 2019 by Asmusr

[apersson850]

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

[Asmusr]

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

 

But probably even slower than what Thom has now.

[+Vorticon]

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

[apersson850]

 

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.

Edited February 6, 2019 by apersson850

[Asmusr]

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.

[Asmusr]

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.

[tschak909]

yup, nice little modify for bresenham.

 

-Thom

[apersson850]

 

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.

[tschak909]

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

[matthew180]

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?

[apersson850]

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.

Edited February 7, 2019 by apersson850

[tschak909]

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

[+FarmerPotato]

 

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

 

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?

[+FarmerPotato]

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

Calculate address of A

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 February 12, 2019 by FarmerPotato

[+FarmerPotato]

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 February 19, 2019 by FarmerPotato

[Asmusr]

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!