gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > Scan-Line Circle Fill Algorithm

#167048 - headspin - Fri Feb 27, 2009 7:47 pm

I need a scanline circle fill alg for creating a window effect. The only one I've found is the following.

Code:
void circleFill(int r)
{
   int x1, x2;
   for (int y=0; y<r*2; y++)
   {
      x1 = ROUND(r + sqrt(SQR(r) - SQR(y - r)));
      x2 = ROUND(r - sqrt(SQR(r) - SQR(y - r)));
      line(x1, y, x2, y);
   }
}


The accuracy is not as important as speed as it needs to be calculated during a HBLANK interrupt. I also need to eventually translate it to asm so is there a similar method that doesn't use the sqrt and would be easier to translate to ARM asm? It can be use a sin lut if necessary but needs to be calculated for each VCOUNT.
_________________
Warhawk DS | Manic Miner: The Lost Levels | The Detective Game

#167049 - Cearn - Fri Feb 27, 2009 8:09 pm

Tonc:dma demo.

For a circular window you don't need a fill algorithm, just the one for the circumference, like Midpoint circle algorithm. First create a buffer to contain the windowing coordinates for each scanline -- do NOT calculate everything inside the HBlank itself, prepare it beforehand. Run the circle algorithm to get the left and right boundaries for each scanline, clip them and fill the buffer. Use HDMA or an HBlank interrupt to update the windows. Because of the amount of branching involved, ARM code would be more efficient, but that's just an optimization detail.

#167068 - Miked0801 - Sat Feb 28, 2009 5:23 am

Breshenhiems <sp> circle algorithm. Integer math and very fast. Look it up.

#167084 - Kyoufu Kawa - Sat Feb 28, 2009 1:13 pm

Miked0801 wrote:
Breshenhiems <sp> circle algorithm. Integer math and very fast. Look it up.
Bresenham.

#167091 - headspin - Sat Feb 28, 2009 4:37 pm

Thanks guys I'm using Cearn's demo as a guide which uses Bresenham and dma.
_________________
Warhawk DS | Manic Miner: The Lost Levels | The Detective Game