Jump to content

Photo

rectangle fill routine for graphics 2 mode?


19 replies to this topic

#1 tschak909 OFFLINE  

tschak909

    River Patroller

  • 3,088 posts
  • Location:USA

Posted Mon Feb 4, 2019 11:35 AM

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



#2 Tursi OFFLINE  

Tursi

    Quadrunner

  • 5,486 posts
  • HarmlessLion
  • Location:BUR

Posted Mon Feb 4, 2019 1:24 PM

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.

#3 tschak909 OFFLINE  

tschak909

    River Patroller

  • Topic Starter
  • 3,088 posts
  • Location:USA

Posted Mon Feb 4, 2019 1:41 PM

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



#4 Asmusr OFFLINE  

Asmusr

    River Patroller

  • 3,033 posts
  • Location:Denmark

Posted Mon Feb 4, 2019 11:18 PM

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, Tue Feb 5, 2019 9:47 AM.


#5 apersson850 OFFLINE  

apersson850

    Dragonstomper

  • 567 posts

Posted Tue Feb 5, 2019 12:17 PM

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

#6 Asmusr OFFLINE  

Asmusr

    River Patroller

  • 3,033 posts
  • Location:Denmark

Posted Tue Feb 5, 2019 12:41 PM

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

 

But probably even slower than what Thom has now.



#7 Vorticon OFFLINE  

Vorticon

    River Patroller

  • 3,535 posts
  • Location:Eagan, MN, USA

Posted Tue Feb 5, 2019 5:01 PM

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



#8 apersson850 OFFLINE  

apersson850

    Dragonstomper

  • 567 posts

Posted Wed Feb 6, 2019 5:04 AM

 

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 by apersson850, Wed Feb 6, 2019 5:09 AM.


#9 Asmusr OFFLINE  

Asmusr

    River Patroller

  • 3,033 posts
  • Location:Denmark

Posted Wed Feb 6, 2019 11:47 AM

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.



#10 Asmusr OFFLINE  

Asmusr

    River Patroller

  • 3,033 posts
  • Location:Denmark

Posted Wed Feb 6, 2019 11:52 AM

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

 

http://www.rosettaco...ine_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.



#11 tschak909 OFFLINE  

tschak909

    River Patroller

  • Topic Starter
  • 3,088 posts
  • Location:USA

Posted Wed Feb 6, 2019 11:52 AM

yup, nice little modify for bresenham. :)

 

-Thom



#12 apersson850 OFFLINE  

apersson850

    Dragonstomper

  • 567 posts

Posted Wed Feb 6, 2019 3:13 PM

 

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.



#13 tschak909 OFFLINE  

tschak909

    River Patroller

  • Topic Starter
  • 3,088 posts
  • Location:USA

Posted Wed Feb 6, 2019 3:40 PM

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



#14 matthew180 OFFLINE  

matthew180

    River Patroller

  • 2,605 posts
  • Location:Castaic, California

Posted Thu Feb 7, 2019 12:08 AM

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?



#15 apersson850 OFFLINE  

apersson850

    Dragonstomper

  • 567 posts

Posted Thu Feb 7, 2019 6:17 AM

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 by apersson850, Thu Feb 7, 2019 6:19 AM.


#16 tschak909 OFFLINE  

tschak909

    River Patroller

  • Topic Starter
  • 3,088 posts
  • Location:USA

Posted Thu Feb 7, 2019 9:37 AM

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



#17 FarmerPotato ONLINE  

FarmerPotato

    Moonsweeper

  • 257 posts
  • Location:Austin, TX

Posted Thu Feb 7, 2019 10:48 AM

 

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?



#18 FarmerPotato ONLINE  

FarmerPotato

    Moonsweeper

  • 257 posts
  • Location:Austin, TX

Posted Thu Feb 7, 2019 11:04 AM

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 by FarmerPotato, Tue Feb 12, 2019 9:40 AM.


#19 FarmerPotato ONLINE  

FarmerPotato

    Moonsweeper

  • 257 posts
  • Location:Austin, TX

Posted Thu Feb 14, 2019 7:56 PM

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.

 

 

 

 

 

 

Attached Files



#20 Asmusr OFFLINE  

Asmusr

    River Patroller

  • 3,033 posts
  • Location:Denmark

Posted Fri Feb 15, 2019 3:44 PM

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!






0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users