CODEWITHSUNDEEP
c++algorithmplotgraphicsrasterizing
user1329019
user1329019

Reputation: 11

Draw filled circle by pixels from center in C++?

I want to draw circle line by line (e.g. in clockwise direction), pixel by pixel from the center of circle. But avoid to redrawing pixels (this is slow).

Imagine this is like "radar" that updates only once each turn.

There is no RAM to hold array of all filled pixels (maximum previous line points) and no GPU or hi-level libraries (drawing by function DrawPoint(x,y)).

I have functions to draw line and point:

void DrawLineFromCenterXYToAngle(int centerX, int centerY, float angle)
{
 .... instead of angle it is possible to find points of the circle and iterate it
 .... find line points by Bresenham's line algorithm
 {
  DrawPoint(int x, int y);
 }
}

void DrawPoint(int x, int y)
{
  PixelDraw_Slow(x,y)=GetColor_VerySlow(x,y);  
}

Now I iterate angle and very slowly got circle, because of pixels in center redrawing many times. And need optimization.

The shape may not be perfect circle if this make it faster.

Upvotes: 1

Views: 4554

Answers (2)

samgak
samgak

Reputation: 24417

There is no RAM to hold array of all filled pixels (maximum previous line points) and no GPU or hi-level libraries (drawing by function DrawPoint(x,y)).

If you can store one line of points then you have enough memory to keep track of all the filled pixels, if you represent it efficiently.

Assuming that your radar sweep begins from the 12 o'clock or 6 o'clock position (it doesn't matter if it sweeps clockwise or anti-clockwise) then at any time during the rendering of the circle, a vertical line will only intersect the block of filled pixels once (i.e. enter once and exit once). So you can keep track of them just by storing the vertical min and max filled pixel y co-ordinate for each column of pixels. If you are starting from the 3 o'clock or 9 o'clock positions then you can store the min and max x for each row.

You can just do it with a couple of arrays:

int minY[X_RANGE];
int maxY[X_RANGE];

X_RANGE is the maximum number of columns of pixels. This only needs to be as large as your circle, not the entire screen, because you can offset it based on the left X of the circle bounding box. Similarly, Y_RANGE is the max number of rows.

When you start rendering, initialize the arrays to represent empty columns:

void InitColumnArrays()
{
    for(int x = 0; x < X_RANGE; x++)
    {
        minY[x] = Y_RANGE - 1;
        maxY[x] = 0;
    }
}

Then when you render a pixel, just check if it has already been rendered by checking the array:

void DrawPointCheckingRanges(int x, int y)
{
    // TODO: range check values

    // check if point has already been drawn and draw it and extend ranges if not:
    if((y < minY[x]) || (y > maxY[x]))
    {
        DrawPoint(x + offsetX, y + offsetX); 
        if(y < minY[x])
            minY[x] = y;
        if(y > maxY[x])
            maxY[x] = y;
    }
}

offsetX and offsetY are optional offsets as discussed above.

You can use this in conjunction with the Bresenham circle drawing algorithm from the other answer which will give efficiently you the end-points for your lines.

The above code assumes that DrawPoint is slow compared to these bounds checks and array reads and writes.

Upvotes: 0

MBo
MBo

Reputation: 80052

There is Bresenham drawing algorithm for circles.

Example with code

int r = 200, ymax, x, y, yp, xp, d;
ymax = r / sqrt(2);
x = r; /* start at the bottom of the first octant */
/* d measures whether the midpoint of two pixel locations
is inside or outside the ideal circle. positive means outside */
d = -1*r; /* to be precise, this should be r^2 - (r - 0.5)^2 */
xp = r; yp = -1; /* these hold the old values across iterations */
for(y=0; y<=ymax; y++) {
  plot_8_ways(x,y);
  if (d > 0) { /* midpoint is outside circle, go NW */
    x--;
    d += (2*yp - 2*xp + 3);
  }
  else { /* midpoint is inside circle, go N */
    d += (2*yp + 1);
  }
  yp = y;
  xp = x;
}

Upvotes: 0

Related Questions