Highest speed graphic functions in a Spartan 6 XC6SLX9

[ElEctric_EyE]

An issue I'm having on paper is I have to test for a negative slope for X, in order to know when to decrease the horizontal pixel counter

Code: Select all

If ( X1 - X0 ) < 0

and let's say X0, X1 are 9 bit registers. I think in Verilog for this to work, I have to have a separate 10 bit register to store the result and test the 10th bit for '1'. Can anyone comment on my suspicion?

[White Flame]

ElEctric_EyE wrote:

Hi WF, I have read you first post more than once and it is packed with info. And thanks for responding again. I need to do more research, but I figured I could get any line drawing algorithm, get the outputted X and Y coordinates into a BRAM, then sort them by Y. This is probably not the most efficient method though. Have you ever done something similar?

I've done a kabillion different software renderers, both commercially and for hobby use. I understand a lot of the hardware design issues, but I'm not technically a hardware guy. What you describe will work, but obviously you'll be very limited in terms of how many lines you can store per frame. I think the idea of the scanline buffer and drawing lines in parallel as the screen is scanned is a really cool and very doable idea.

In your prerendered list-of-points approach, you don't actually need to sort the list of points by Y: Draw from point A to point B. If A's y-coordinate is greater than B's y-coordinate, then swap the 2 points before you even begin. Then the natural loop ordering from A to B will always be in increasing Y order. (well, technically non-decreasing order)

Regarding the comparison, can you access the carry output of the subtraction? If not, then yes you need the result to be wide enough that a set MSB unambiguously indicates a negative number. Given two 9-bit unsigned input values, the output must be at least 10 bits. Not sure about the Verilog specifics, though.

[ElEctric_EyE]

White Flame wrote:

I've done a kabillion different software renderers, both commercially and for hobby use...

Excellent, glad to have your input!

I'm pretty sure about detecting the negative numbers as Arlet uses the same detector in his H/VSync generator on a count down circuit, I was just wondering if there was a better way to do it in my situation...

One more question for Verilog experts. Can I do something like this to either increase or decrease a counter, depending on whether sx = 0 or 1?

Code: Select all

x0 = sx ? x0 + 1 : 
			 x0 - 1;

[MichaelM]

Quote:

One more question for Verilog experts. Can I do something like this to either increase or decrease a counter, depending on whether sx = 0 or 1?

Code: Select all

x0 = sx ? x0 + 1 : 
          x0 - 1;

Yes, but as code I expect that it will be a combinatorial logic loop since it is an asynchronous logic construction that you're using, and the output variable is also an input variable. If x0 is registered, then the operation will synthesize to a single add/sub primitive.

[Arlet]

It's probably easier to say:

Code: Select all

if( x1 < x0 )

But if you want to get access to the carry, just do temp <= x1 - x0, where temp has 1 bit more than x0 and x1. The MSB of temp will contain the carry out.

[ElEctric_EyE]

Thanks for the tip and confirmation...

I think I finally get it. I haven't been able to throw alot of time at this and so I'm making small steps. But I think of the problem often and I've come to the conclusion that I'm going to have to use division. At least for the first step, until I can comprehend a different way. For a more horizontal line (i.e. dx>dy) I will have to use dx/dy in order to know when to perform y=y+1. For a more vertical line (dy>dx) I'll have to use dy/dx in order to know when to perform x=x+1 or x=x-1, depending on sx, the slope of the line.

I have 3 days off this week, so I'll be able to focus on completing the code and seeing the results. Because Verilog doesn't do fractions, the division is going to present a rounding error. How to properly and accurately deal with this fact is where I am conceptually at right now.

[Arlet]

Bresenham's method doesn't use division. For vector based drawing where you draw the lines top-down during a scan I recommend replacing the division by a multiplication.

By the way, verilog supports the division operator, but ISE won't synthesize it.

[ElEctric_EyE]

Multiplication? What is your concept?

[Arlet]

For each scanline, we know the Y coordinate, but the problem is figuring out the X coordinate. If the line starts at (x0, y0) and goes to (x0+dx, y0+dy), we can determine x = x0 + y * dx/dy. The dx/dy fraction is constant and we can calculate it in advance, and store it in the block RAM with the other line parameters. The advance calculation could be done by the CPU using a software division algorithm, or maybe in hardware during vertical sync.

Note that I've simplified the problem somewhat. For flat lines (dx > dy), you need both a starting X and a stopping X for each Y, and draw a short horizontal line between them. Also,the case dy=0 needs to be handled properly.

Another method is to use a Bresenham algorithm. It avoids the multiplication/division, but requires keeping track of the 'err' values in a memory, as well as the current X coordinate. If you don't care about the memory consumption, it is probably an easier method overall.

[ElEctric_EyE]

Arlet wrote:

...Note that I've simplified the problem somewhat. For flat lines (dx > dy), you need both a starting X and a stopping X for each Y...

This is the part I am wrestling with. For lines dx>dy, this amount is dx/dy before going on to the next scanline. A similar situation for lines dy>dx... Maybe I will go back to Bresenham formula and figure something out for

Code: Select all

if e2 > -dy then 

. This is really the only part holding me up, from that angle of attack, which is why I started down the path of my previous post.

[Arlet]

ElEctric_EyE wrote:

For lines dx>dy, this amount is dx/dy before going on to the next scanline.

Yes, but if you precalculate dx/dy, this value is already available. If you're willing to use some memory, a simple method is just to add dx/dy to the old x coordinate, to produce the new one. Then draw a horizontal line segment between old x and new x.

[ElEctric_EyE]

Ok, I see. So if I understand correct, the length of this dx/dy table would be 1/2 total horizontal resolution? And I could use the same table for dy/dx?

[Arlet]

Since we've discussed several ways to draw lines, there may be some confusion here. I'm talking about the "vector type" display, where lines are generated on the fly, based on a table with line info (x0, y0, dx/dy). For every line currently on the screen, there would be an entry in this table, containing a dx/dy value. So if you have 1000 lines on the screen, there would be 1000 precalculated dx/dy values. Since all lines are drawn during a scan, the Y coordinate is known, so there's only a need for a dx/dy value to calculate the corresponding X, We don't need a dy/dx.

For a line drawing method where you store the pixels (either in a table or in a bitmap), the Bresenham method is much easier, since it avoids the division altogether.

[White Flame]

Note that you also need to store x1 and y1 in the line info, so you know where to stop. I agree that adding a fixed-point delta is probably going to be the most straightforward approach, but it might be more memory hungry than Bresenham (doubling of register sizes due to fixed-point calculations), and needs to perform all those divisions before it can start working.

EE: He's not talking about a lookup table to calculate dx/dy, but a table which holds the info for every active line you'll be drawing. Each line will have to have its slope delta calculated via a fixed-point-result division operation once per frame.

Regarding lines where dx>dy (ie, multiple pixels per scanline), the logic remains this for when you're using fixed-point deltas:

You need to remember both the old x and the new x' = x + dx/dy:

• If x' is still the same as x, then just draw the 1 pixel. This is a vertical portion of the line.
• If x' changed, then draw all the pixels between x and x', not including x.

If you're using Bresenham, then each pass of the 'error' accumulation loop will plot 1 pixel in your horizontal span of the line.

But yeah, there are a number of approaches being batted around. Focusing on learning one that you don't already know, or focusing on implementing one which you do know would be good.

[ElEctric_EyE]

I think I bit off more than I can chew with this goal of line drawing project in pure Verilog, but I will stick with Bresenham...
I found a line drawing module on github within the orsoc project I had looked into before. I had missed it the first time. At the very least, it gave me clues to the structure needed of a line drawing state machine in Verilog. The prep_state is the only one that appears correct. The other 2 'state's are incomplete at this point and nothing is tested. Currently, I manually set the internal x0,x1,y0,y1 variables. When it's functional, these 4 will be inputs.
Critique's of the code are most welcome, even flaming critiques.

Code: Select all

module LineGen( input clk108,
					 input countflag,				//flag, plot inside borders
					 input vblank,
					 input vsync,
					 output reg [9:0] X,			//H component of pixel to BRAM
					 output reg [8:0] Y			//V component of pixel to BRAM
					);
					
reg [9:0] x0 = 0;
reg [9:0] x1 = 639;			
reg [8:0] y0 = 0;
reg [8:0] y1 = 479;
reg [9:0] dx;
reg [8:0] dy;
reg [9:0] err;
reg [10:0] e2;
reg [0:0] sx;

reg [2:0] state;
parameter prep_state = 0, errcalc_state = 1, draw_state = 2;

//state machine for plotting a line
always @(posedge clk108)
	if ( vblank & vsync )
		state <= prep_state;
			else
				case (state)

					prep_state:							//calculate dx/dy and slope of X
						state <= errcalc_state;
				
					errcalc_state:						//calculate error
						state <= draw_state;
					
					draw_state:
						if ( !countflag )
							state <= prep_state;

				endcase
				
always @(posedge clk108) begin
	case (state)
		prep_state:							
			begin
				if ( x1 > x0 ) begin			//negative "\" slope
					dx <= x1 - x0;
					sx <= 0;
				end
					else begin					//positive "/" slope
						dx <= x0 - x1;
						sx <= 1;
					end
		
				if ( y1 > y0)
					dy <= y1 - y0;
					else 
						dy <= y0 - y1;
			end
	
		errcalc_state:							
			begin
				if ( dx > dy )
					err <= dx - dy;
					else
						err <= dy - dx;
			end
	
		draw_state:
			begin
				e2 <= err + err;		
				X <= x0;
				Y <= y0;							//output origin
				if ( e2 < dy ) begin
					err <= err + dy;
					x0 <= sx ? x0 + 1 :
								  x0 - 1;
					X <= x0;
				end
					else if (( x0 = err ) | ( y0 != y1 )) begin
						y0 <= y0 + 1;
						Y <= y0;
					end
			end
	endcase
end

endmodule