How do I fill in an FPGA generated circle in verilog for synthesis and VGA output?

Question

I want to output a moving red circle of radius 100 pixels on a 640x480 VGA display. I'm stuck on how to make and fill in the actual circle. Now I've taken a look at the mind numbing Bresenham algorithms but I'm unable to make them suit my verilog code.

I've theorized what I could be able to do but I'm not entirely sure it's possible. I know that the equation of a circle is (x-a)(x-a)+(y-b)(y-b)=r*r where (a,b) is the origin. So I want to fill in this circle with an RGB colour and move it from top to bottom i.e from b= 0 to 480 at a=640/2

Since the VGA outputs pixels from left to right, iterating downwards, I'm guessing I have to use nested loops. I know the first loop for the vertical movement goes from 0 to 480. It's the second loop I have a problem with. It goes from 0 to 640 but I want the pixels to change colour when they get to (x,y) (a point along the circle), retain that colour, then change back once they pass (x+k) (where k is a horizontal chord).

Essentially if this below is a horizontal chord of my circle:

_black .(x,y)___red(k pixels)_.(x+k,y)_black

reg [8:0] bally;//y coordinate of the center of circle
reg [8:0] rad;//radius 

always @ (posedge clk)
begin
for(VCount=0;VCount<=480;VCount++)
  for(HCount=0;HCount<=640;HCount++)
     if((HCount*HCount>=rad*rad-((VCount-bally)*(VCount-bally)) && HCount*HCount<=((10000-((VCount-bally)*(VCount-bally)))+k)))
        R<=1;
        G<=0;
        B<=0;
     end

My question is, how do I represent k in my if-condition in terms of variables I already have? I realize this may not be a verilog problem but may be me failing at basic trigonometry but my mind is really blocked on this. And please, if I'm extremely off (code-wise,logic-wise, synthesis-wise)in my attempt to make this circle, do tell. Any help would be greatly appreciated.

Answer 1

You don't want for loops like that. If you want to generate a circle on the fly (rather than using a bitmap), keep track of your current coordinate in a separate process (always block). Each always block will run on every tick of the VGA clock, so you have a new pixel position every time the block executes.

Then have another always block which looks at those x and y coordinates and decides if the current point is in the circle or not. Based on that decision, you can choose a foreground or background colour. Again, this operates once for every pixel, in order.

The tricky part is the decision as to whether the current point is in the circle or not.

If this seems a bit too hard to start with, draw a square instead as the equations for that are very straightforward. Once you got that down and understand exactly how and why it works, you can graduate to circles (and other parametrically defined shapes). To find methods of rendering these shapes on the fly, as you scan the image, you might find the term "scanline render" or "incremental render" helpful.

---

On thinking some more about this, is it not the case that the standard equation for a circle:

x^2 + y^2 = r^2

can be rendered as an inequality to return points inside a circle:

x^2 + y^2 < r^2

Extending to allow variation in the centre point:

(x-xc)^2 + (y-yc)^2 < r^2

That would mean that for every pixel, you subtract the centre point from the x and y, square them and compare to r^2. If it's less-than r^2, plot the pixel.

That would have been a lot of logic in an old-fashioned FPGA, but 3 subtractors and 2 multipliers is nothing these days (or if you operate at a multiple of the pixel clock, you could share the multiplier at the expense of a mux on the inputs)

Answer 2

I'm not sure a nested for loop will behave like you think it does, at least for a synthetized design.

My suggestion is not to generate the circle based upon its parametrical equations, which is what I think you want to do. Instead, if the circle is always the same (i.e. it always has a radius of 100 pixels or less), pregenerate a bitmap of your circle and store it in FPGA (block RAM) memory as a large sprite. It won't take you much space. A 0-bit in your sprite will translate as "transparent" while a 1-bit will mean to plot this dot using the color associated with your sprite (circle).

This way, your code for drawing the screen (the active part of the screen actually) would be something like this:

`define SPRLEN 256  // how many pixels in width and heigh the sprite will have.
`define SPRITECOLOR 3'b100;  // RED ball. (RGB, 1-bit per channel)
`define BGCOLOR 3'010;       // GREEN background

reg ballsprite[0:`SPRLEN*`SPRLEN-1]; // A matrix to hold your sprite.
reg [9:0] hcont, vcont; // horizontal and vertical counters for scanning a VGA picture
reg [8:0] ballx, bally; //coordinates of the left-top corner of the ball sprite
reg [7:0] coorx,coory;  //X,Y coordinates of the current sprite position to draw

initial begin  // read your sprite definition into memory. FPGA synthetizable.
  $readmemb ("mysprite.bin", ballsprite);
end

// process to obtain relative coordinates of the current screen position within the sprite 
always @* begin
  coorx = hcont+1-ballx;
  coory = vcont+1-bally;
end

// process to get the next dot from the sprite. We begin at ballx-1,bally-1 because
// there's one clock delay in getting the current sprite dot value.
always @(posedge clk) begin
  if (hcont>=ballx-1 && hcont<=ballx-1+`SPRLEN && vcont>=bally-1 && vcont<=bally-1+`SPRLEN)
    dot_from_ball <= ballsprite[{coory,coorx}];  // i.e. coory*256+coorx
  else
    dot_from_ball <= 1'b0;  // if scan trace is not under the boundaries of the sprite,
                            // then it's transparent color
end

// multiplexer to actually put an RGB value on screen
always @* begin
  if (hcont>=0 && hcont<640 && vcont>=0 && vcont<480) begin
    if (dot_from_ball)
      {R,G,B} = `SPRITECOLOR;
    else
      {R,G,B} = `BGCOLOR;
  end
  else
    {R,G,B} = 3'b000;  //if not into active area, mute RGB
end

It's up to you to generate proper values for hcont and vcont, and to infer sync signals depending on when certain values are reached by these counters.

Some time ago, I did something similar: drawing a moving sprite into a VGA screen. I did it using Handel C, but the logic is the same. You can see it here: http://www.youtube.com/watch?v=wgDSzC-vGZ0