Showing results for 
Search instead for 
Did you mean: 
Honored Contributor I

How to use framebuffer when implementing line drawing algorithm in FPGA

I need to implement the Bresenham's integer line drawing algorithm onto the DE2-115 board. The algorithm is quite simple, we give the xy coordinates from start point to end point, the algorithm then simply calculates for the given curret pixel (x,y) does the next pixel which has x coordinate x+1 have same y coordinate or y+1 or y-1. 


As I calculate the results I need to store them into a memory. Provided that I am implementing this as a monochrome system and there are 8 pixels stored per byte in memory, it seems difficult task to write these bits into memory. Provided that SRAM is used as frame buffer. At start of frame, I shall have to clear all bytes in the SRAM. Then, I find which byte a pixel belongs to, I read that byte from memory, AND the bit which represents the line pixel and then write it back. 

I shall therefore, need a FIFO with line coordinates, these put into a FIFO, multiple pipelines take data from this FIFO and continuosly output pixel coordinate which must be "colored" since line passes through it and fill these into another FIFO. Then a dispatcher shall read these coordinates, figure out how to write them to memory, wait until memory is free and then read the memory, set the bit and write it back. 

Is there a better way to fill in the frame buffer?
0 Kudos
2 Replies
Honored Contributor I

Is this part of a homework and you are required to implement it this way? If so, if you only need to draw the one line, it seems like a framebuffer is overkill: your block could just receive a stream of pixels, overwrite pixels hit by the line, and passing through the unmodified pixels if not. 


As far as your frame buffer approach in general: it sounds like read-modify-write and initializing the entire buffer to zero at the beginning of frame are not necessary. You should be able to write the framebuffer contents in one pass (pixels in the line are '1' and everything else is '0'). 

Depending on your frame rate / performance requirements, a FIFO may not be necessary: you can simply compute directly the address of the memory from the (x,y) coordinate of the pixel you are considering, issue the read, wait until it completes, modify it, issue the write, wait for it to complete, etc. 


If you're doing this all as a part of a product development, Altera VIP IP suite has blocks for performing the mixing/overlay function, and you can either generate the line overlay from VHDL in a stream, or have it come from a buffer in RAM that you initialized with e.g. NIOS software. 


If this block is the first of possibly many that you are creating, what you may want to consider is implementing a row buffer (cache) where your algorithms can directly address pixels in a given region (e.g. 8 or 16 lines) and a separate block manages the read/write of buffer contents between onchip M9K and off-chip SRAM/SDRAM.
Honored Contributor I

thanks for the reply ted, this is for a "personal project for fun learning". The idea is to have a system that renders 3D polygons but only the lines, does not fill them (at this stage of the project). These polygons can be rotated, scaled and shifted. 


I have also felt that the buffer is perhaps an overkill. However, the idea is that later I shall be filling in these polygons and thus if I learnt how to fill in frame buffer now, it shall help me in later stages of the project. On the other hand, since I am going to be using the bresenham's line drawing algorithm, I cannot find out if a the given pixel occurs in all of the line in real time since this algorithm does not do that, even though this solution is certainly less complex than the one I have imagined.  


Since most likely an external memory shall be used, I shall have to clear it as well since every frame may be different from the previous frame due to the polygons having been transformed. Depending on the refresh rate and the resolution of the display, external memory of specific speed shall be required.