Bresenham’s Line Algorithm inHardwareStephen A. EdwardsColumbia UniversitySpring 2012Bresenham’s Line AlgorithmObjective:Draw a line...Bresenham’s Line Algorithm...with well-approximating pixels...Bresenham’s Line Algorithm...by maintaining error information..Error = −3/7Error = 1/7Bresenham’s Line Algorithm...encoded using integers36251403Error = −3/7Error = 1/7The Pseudocode from Wikipediafunction line(x0, y0, x1, y1)dx := abs(x1-x0)dy := abs(y1-y0)if x0 < x1 then sx := 1 else sx := -1if y0 < y1 then sy := 1 else sy := -1err := dx-dyloopsetPixel(x0,y0)if x0 = x1 and y0 = y1 exit loope2 := 2*errif e2 > -dy thenerr := err - dyx0 := x0 + sxend ifif e2 < dx thenerr := err + dxy0 := y0 + syend ifend loopMy C Codevoid line(Uint16 x0, Uint16 y0, Uint16 x1, Uint16 y1){Sint16 dx, dy; // Width and height of bounding boxUint16 x, y; // Current pointSint8 sx, sy; // -1 or 1Sint16 err; // Loop-carried valueSint16 e2; // Temporary variableint right, down;// Booleandx = x1 - x0; right = dx > 0; if (!right) dx = -dx;dy = y1 - y0; down = dy > 0; if (down) dy = -dy;err = dx + dy; x = x0; y = y0;for (;;) {plot(x, y);if (x == x1 && y == y1) break; // Reached the ende2 = err << 1; // err*2if (e2 > dy) { err += dy; if (right) x++; else x--;}if (e2 < dx) { err += dx; if (down) y++; else y--;}}}Datapath for dx, dy, right, and downvoid line(Uint16 x0, Uint16 y0,Uint16 x1, Uint16 y1){Sint16 dx; // Width of bounding boxSint16 dy; // Height of BB (neg)Uint16 x, y; // Current pointSint8 sx, sy;// -1 or 1Sint16 err; // Loop-carried valueSint16 e2; // Temporary variableint right; // Booleanint down; // Booleandx = x1 - x0;right = dx > 0;if (!right) dx = -dx;dy = y1 - y0;down = dy > 0;if (down) dy = -dy;err = dx + dy;x = x0; y = y0;for (;;) {plot(x, y);if (x == x1 && y == y1)break;e2 = err << 1;if (e2 > dy) {err += dy;if (right) x++;else x--;}if (e2 < dx) {err += dx;if (down) y++;else y--;}}Datapath for dx, dy, right, and downsubtract> 0?negate01x1x0rightx1 − x0dxsubtract> 0?negate01y1y0downy1 − y0dydx = x1 - x0;right = dx > 0;if (!right) dx = -dx;dy = y1 - y0;down = dy > 0;if (down) dy = -dy;err = dx + dy;x = x0; y = y0;for (;;) {plot(x, y);if (x == x1 && y == y1)break;e2 = err << 1;if (e2 > dy) {err += dy;if (right) x++;else x--;}if (e2 < dx) {err += dx;if (down) y++;else y--;}}Datapath for dx, dy, right, and downsubtract> 0?negate01x1x0rightx1 − x0dxsubtract> 0?negate01y1y0downy1 − y0dyx1x0 <= x1 - x0;y1y0 <= y1 - y0;right <= not x1x0(10);down <= not y1y0(10);dx <= x1x0 when right = ’1’else -x1x0;dy <= -y1y0 when down = ’1’else y1y0;Datapath for erradddxdyadddy01adddx0101<<1<>e2dye2_gt_dye2_lt_dxdxerrin_loopdx = x1 - x0;right = dx > 0;if (!right) dx = -dx;dy = y1 - y0;down = dy > 0;if (down) dy = -dy;err = dx + dy;x = x0; y = y0;for (;;) {plot(x, y);if (x == x1 && y == y1)break;e2 = err << 1;if (e2 > dy) {err += dy;if (right) x++;else x--;}if (e2 < dx) {err += dx;if (down) y++;else y--;}}Datapath for erradddxdyadddy01adddx0101<<1<>e2dye2_gt_dye2_lt_dxdxerrin_looperr_next <=("0" & dx) + ("0" & dy)when in_loop = ’0’else err2;err2 <= err1 + dxwhen e2_lt_dx = ’1’else err1;err1 <= err + dywhen e2_gt_dy = ’1’else err;e2 <=err(10 downto 0) & "0";e2_gt_dy <=’1’ when e2 > dyelse ’0’;e2_lt_dx <=’1’ when e2 < dxelse ’0’;Datapath for x and y+1−1==+1−1x01right01e2_gt_dy10x0in_loopy01down01e2_lt_dx10y0in_loopy1x1breakdx = x1 - x0;right = dx > 0;if (!right) dx = -dx;dy = y1 - y0;down = dy > 0;if (down) dy = -dy;err = dx + dy;x = x0; y = y0;for (;;) {plot(x, y);if (x == x1 && y == y1)break;e2 = err << 1;if (e2 > dy) {err += dy;if (right) x++;else x--;}if (e2 < dx) {err += dx;if (down) y++;else y--;}}Datapath for x and y+1−1==+1−1x01right01e2_gt_dy10x0in_loopy01down01e2_lt_dx10y0in_loopy1x1breakx_next <=x0 when in_loop = ’0’else xb;xb <= xa when e2_gt_dy = ’1’else x;xa <= x + 1 when right = ’1’else x - 1;y_next <=y0 when in_loop = ’0’else yb;yb <= ya when e2_lt_dx = ’1’else y;ya <= y + 1 when down = ’1’else y - 1;break <=’1’ when x = x1 and y = y1else ’0’;process (clk)beginif rising_edge(clk) thenerr <= err_next;x <= x_next;y <= y_next;end if;end process;Interface and Typeslibrary ieee;use ieee.std_logic_1164.all;use ieee.numeric_std.all;entity lines isport (clk : in std_logic;rst : in std_logic;x0, y0, x1, y1 : in signed(10 downto 0);x_p, y_p : out signed(10 downto 0);start : in std_logic;done, plot : out std_logic);end lines;architecture datapath of lines issignal x1x0, y1y0, dx, dy : signed(10 downto 0);signal down, right, e2_lt_dx, e2_gt_dy : std_logic;signal in_loop, break : std_logic;signal err, err1, err2, e2, err_next : signed(11 downto 0);signal x, y, x_next, y_next,xa, xb, ya, yb : signed(10 downto 0);Timingclk(x0,y0)(0,0) (5,3)(x1,y1)(7,4) (6,4)startdonein_loopbreakx01 2345 675 6y01 23434err3 6251 40 3 0dx, dy7, −4 1, −1Control FSMIDLERUNin_loop = 1DONEdone = 1startstartbreakbreakstartstartControl FSM in VHDLtype states is (IDLE_STATE, RUNNING_STATE, DONE_STATE);signal state : states;fsm : process (clk)beginif rising_edge(clk) thenif rst = ’1’ thenstate <= IDLE_STATE;elsecase state iswhen IDLE_STATE =>if start = ’1’ then state <= RUNNING_STATE; end if;when RUNNING_STATE =>if break = ’1’ then state <= DONE_STATE; end if;when DONE_STATE =>if start = ’1’ then state <= RUNNING_STATE;else state <= IDLE_STATE; end if;end case; end if; end if; end process;in_loop <= ’1’ when state = RUNNING_STATE else ’0’;done <= ’1’ when state = DONE_STATE else ’0’;plot <= in_loop;The Framebuffercomponent fbmem port (data : in std_logic_vector(0 downto 0);rdaddress : in std_logic_vector(18 downto 0);rdclock : in std_logic;wraddress : in std_logic_vector(18 downto 0);wrclock : in std_logic;wren : in std_logic;q : out std_logic_vector(0 downto 0));end component;frame_buffer_memory : fbmem port map (rdaddress => std_logic_vector(rdaddress(18 downto 0)),rdclock => VGA_CLK,q => q,data => data,wraddress => std_logic_vector(wraddress(18 downto 0)),wrclock => clk,wren => wren);read_data <= ’1’ when q(0) = ’1’ else ’0’;data <= "1" when write_data = ’1’ else "0";rdaddress <= ("0000000000" & VGA_X) +(VGA_Y & "0000000") + (VGA_Y & "000000000");wraddress <= ("0000000000" & VGA_XW) +(VGA_YW & "0000000") + (VGA_YW &
View Full Document