17 March 2021

2D Shapes

Welcome back to Exploring FPGA Graphics. Building on our designs in lines and triangles, we’ll draw rectangles, filled triangles and circles. We’ll finish off this part by drawing a castle with our shapes.

In this series, we explore graphics at the hardware level and get a feel for the power of FPGAs. We’ll learn how displays work, race the beam with Pong, animate starfields and sprites, paint Michelangelo’s David, simulate life with bitmaps, draw lines and shapes, and create smooth animation with double buffering. New to the series? Start with FPGA Graphics.

You can watch an FPGA Graphics demo reel with designs from across this series.

Updated 2021-09-01. Get in touch with @WillFlux or open an issue on GitHub.

Series Outline

  • FPGA Graphics - learn how displays work and draw your first graphics
  • Pong - race the beam to create the arcade classic
  • Hardware Sprites - fast, colourful, graphics with minimal logic
  • Ad Astra - graphics demo with starfields and hardware sprites
  • Framebuffers - driving the display from a bitmap in memory
  • Life on Screen - the screen comes alive with Conway’s Game of Life
  • Lines and Triangles - drawing lines and triangles with a framebuffer
  • 2D Shapes (this post) - filling shapes and drawing pictures
  • Animated Shapes - animation and double-buffering

Requirements

For this series, you need an FPGA board with video output. We’ll be working at 640x480, so pretty much any video output will do. It helps to be comfortable with programming your FPGA board and reasonably familiar with Verilog.

We’ll be demoing with these boards:

Source

The SystemVerilog designs featured in this series are available from the projf-explore git repo under the open-source MIT licence: build on them to your heart’s content. The rest of the blog content is subject to standard copyright restrictions: don’t republish it without permission.

The Rectangle

Let’s kick things off by creating a module for rectangle drawing; this is similar to the triangle and provides a helpful stepping stone to drawing filled shapes.

Create module [draw_rectangle.sv]:

module draw_rectangle #(parameter CORDW=16) (  // signed coordinate width
    input  wire logic clk,             // clock
    input  wire logic rst,             // reset
    input  wire logic start,           // start rectangle drawing
    input  wire logic oe,              // output enable
    input  wire logic signed [CORDW-1:0] x0, y0,  // vertex 0
    input  wire logic signed [CORDW-1:0] x1, y1,  // vertex 2
    output      logic signed [CORDW-1:0] x,  y,   // drawing position
    output      logic drawing,         // actively drawing
    output      logic busy,            // drawing request in progress
    output      logic done             // drawing is complete (high for one tick)
    );

    logic [1:0] line_id;  // current line (0, 1, 2, or 3)
    logic line_start;     // start drawing line
    logic line_done;      // finished drawing current line?

    // current line coordinates
    logic signed [CORDW-1:0] lx0, ly0;  // point 0 position
    logic signed [CORDW-1:0] lx1, ly1;  // point 1 position

    // draw state machine
    enum {IDLE, INIT, DRAW} state;
    always_ff @(posedge clk) begin
        case (state)
            INIT: begin  // register coordinates
                state <= DRAW;
                line_start <= 1;
                if (line_id == 2'd0) begin  // (x0,y0) (x1,y0)
                    lx0 <= x0; ly0 <= y0;
                    lx1 <= x1; ly1 <= y0;
                end else if (line_id == 2'd1) begin  // (x1,y0) (x1,y1)
                    lx0 <= x1; ly0 <= y0;
                    lx1 <= x1; ly1 <= y1;
                end else if (line_id == 2'd2) begin  // (x1,y1) (x0,y1)
                    lx0 <= x1; ly0 <= y1;
                    lx1 <= x0; ly1 <= y1;
                end else begin  // (x0,y1) (x0,y0)
                    lx0 <= x0; ly0 <= y1;
                    lx1 <= x0; ly1 <= y0;
                end
            end
            DRAW: begin
                line_start <= 0;
                if (line_done) begin
                    if (line_id == 3) begin  // final line
                        state <= IDLE;
                        busy <= 0;
                        done <= 1;
                    end else begin
                        state <= INIT;
                        line_id <= line_id + 1;
                    end
                end
            end
            default: begin  // IDLE
                done <= 0;
                if (start) begin
                    state <= INIT;
                    line_id <= 0;
                    busy <= 1;
                end
            end
        endcase

        if (rst) begin
            state <= IDLE;
            line_id <= 0;
            line_start <= 0;
            busy <= 0;
            done <= 0;
        end
    end

    draw_line #(.CORDW(CORDW)) draw_line_inst (
        .clk,
        .rst,
        .start(line_start),
        .oe,
        .x0(lx0),
        .y0(ly0),
        .x1(lx1),
        .y1(ly1),
        .x,
        .y,
        .drawing,
        .busy(),
        .done(line_done)
    );
endmodule

This module has similar I/O and state machine to draw_triangle, but a rectangle only needs two pairs of coordinates to define it.

To demo our rectangle drawing, we will draw a series of rectangles inside each other using each colour in the 16-colour palette.

Building the Designs
In the 2D Shapes section of the git repo, you’ll find the design files, a makefile for iCEBreaker, a Vivado project for Arty, and instructions for building the designs for both boards.

The Arty version of top_rectangles looks like this:

module top_rectangles (
    input  wire logic clk_100m,     // 100 MHz clock
    input  wire logic btn_rst,      // reset button (active low)
    output      logic vga_hsync,    // horizontal sync
    output      logic vga_vsync,    // vertical sync
    output      logic [3:0] vga_r,  // 4-bit VGA red
    output      logic [3:0] vga_g,  // 4-bit VGA green
    output      logic [3:0] vga_b   // 4-bit VGA blue
    );

    // generate pixel clock
    logic clk_pix;
    logic clk_locked;
    clock_gen_480p clock_pix_inst (
       .clk(clk_100m),
       .rst(!btn_rst),  // reset button is active low
       .clk_pix,
       .clk_locked
    );

    // display timings
    localparam CORDW = 16;
    logic signed [CORDW-1:0] sx, sy;
    logic hsync, vsync;
    logic frame, line;
    display_timings_480p #(.CORDW(CORDW)) display_timings_inst (
        .clk_pix,
        .rst(!clk_locked),  // wait for pixel clock lock
        .sx,
        .sy,
        .hsync,
        .vsync,
        .de(),
        .frame,
        .line
    );

    logic frame_sys;  // start of new frame in system clock domain
    xd xd_frame (.clk_i(clk_pix), .clk_o(clk_100m),
                 .rst_i(1'b0), .rst_o(1'b0), .i(frame), .o(frame_sys));

    // framebuffer (FB)
    localparam FB_WIDTH   = 320;
    localparam FB_HEIGHT  = 180;
    localparam FB_CIDXW   = 4;
    localparam FB_CHANW   = 4;
    localparam FB_SCALE   = 2;
    localparam FB_IMAGE   = "";
    localparam FB_PALETTE = "16_colr_4bit_palette.mem";

    logic fb_we;  // write enable
    logic signed [CORDW-1:0] fbx, fby;  // draw coordinates
    logic [FB_CIDXW-1:0] fb_cidx;  // draw colour index
    logic fb_busy;  // when framebuffer is busy it cannot accept writes
    logic [FB_CHANW-1:0] fb_red, fb_green, fb_blue;  // colours for display output

    framebuffer_bram #(
        .WIDTH(FB_WIDTH),
        .HEIGHT(FB_HEIGHT),
        .CIDXW(FB_CIDXW),
        .CHANW(FB_CHANW),
        .SCALE(FB_SCALE),
        .F_IMAGE(FB_IMAGE),
        .F_PALETTE(FB_PALETTE)
    ) fb_inst (
        .clk_sys(clk_100m),
        .clk_pix,
        .rst_sys(1'b0),
        .rst_pix(1'b0),
        .de(sy >= 60 && sy < 420 && sx >= 0),  // 16:9 letterbox
        .frame,
        .line,
        .we(fb_we),
        .x(fbx),
        .y(fby),
        .cidx(fb_cidx),
        .clip(),
        .busy(fb_busy),
        .red(fb_red),
        .green(fb_green),
        .blue(fb_blue)
    );

    // draw rectangles in framebuffer
    localparam SHAPE_CNT=64;  // number of shapes to draw
    logic [$clog2(SHAPE_CNT):0] shape_id;  // shape identifier
    logic signed [CORDW-1:0] vx0, vy0, vx1, vy1;  // shape coords
    logic draw_start, drawing, draw_done;  // drawing signals

    // draw state machine
    enum {IDLE, INIT, DRAW, DONE} state;
    always_ff @(posedge clk_100m) begin
        case (state)
            INIT: begin  // register coordinates and colour
                draw_start <= 1;
                state <= DRAW;
                vx0 <=  60 + shape_id;
                vy0 <=  15 + shape_id;
                vx1 <= 260 - shape_id;
                vy1 <= 165 - shape_id;
                fb_cidx <= shape_id[3:0];  // use lowest four bits for colour
            end
            DRAW: begin
                draw_start <= 0;
                if (draw_done) begin
                    if (shape_id == SHAPE_CNT-1) begin
                        state <= DONE;
                    end else begin
                        shape_id <= shape_id + 1;
                        state <= INIT;
                    end
                end
            end
            DONE: state <= DONE;
            default: if (frame_sys) state <= INIT;  // IDLE
        endcase
    end

    // control drawing speed with output enable
    localparam FRAME_WAIT = 300;  // wait this many frames to start drawing
    localparam PIX_FRAME  = 200;  // draw this many pixels per frame
    logic [$clog2(FRAME_WAIT)-1:0] cnt_frame_wait;
    logic [$clog2(PIX_FRAME)-1:0] cnt_pix_frame;
    logic draw_req;
    always_ff @(posedge clk_100m) begin
        draw_req <= 0;
        if (frame_sys) begin
            if (cnt_frame_wait != FRAME_WAIT-1) cnt_frame_wait <= cnt_frame_wait + 1;
            cnt_pix_frame <= 0;  // reset pixel counter every frame
        end
        if (!fb_busy) begin
            if (cnt_frame_wait == FRAME_WAIT-1 && cnt_pix_frame != PIX_FRAME-1) begin
                draw_req <= 1;
                cnt_pix_frame <= cnt_pix_frame + 1;
            end
        end
    end

    draw_rectangle #(.CORDW(CORDW)) draw_rectangle_inst (
        .clk(clk_100m),
        .rst(1'b0),
        .start(draw_start),
        .oe(draw_req && !fb_busy),  // draw if requested when framebuffer is available
        .x0(vx0),
        .y0(vy0),
        .x1(vx1),
        .y1(vy1),
        .x(fbx),
        .y(fby),
        .drawing,
        .busy(),
        .done(draw_done)
    );

    // write to framebuffer when drawing
    always_comb fb_we = drawing;

    // reading from FB takes one cycle: delay display signals to match
    logic hsync_p1, vsync_p1;
    always_ff @(posedge clk_pix) begin
        hsync_p1 <= hsync;
        vsync_p1 <= vsync;
    end

    // VGA output
    always_ff @(posedge clk_pix) begin
        vga_hsync <= hsync_p1;
        vga_vsync <= vsync_p1;
        vga_r <= fb_red;
        vga_g <= fb_green;
        vga_b <= fb_blue;
    end
endmodule

We control the drawing speed with output enable to make it visible. I’ve chosen to wait for 300 frames (5 seconds) to start drawing, then draw 200 pixels per frame. You can adjust these parameters with FRAME_WAIT and PIX_FRAME.

Rectangles

Filled Rectangle

A rectangle is the simplest shape to fill: we draw a series of horizontal lines of the same length. We could use our regular draw_line.sv module to do this, but a simpler module, draw_line_1d will do the trick. By restricting line drawing to one dimension and left-to-right, we can take advantage of sequential memory access, which is important for dynamic (SDRAM, DDR, PSRAM) memory performance.

Create module [draw_line_1d.sv]:

module draw_line_1d #(parameter CORDW=16) (  // signed coordinate width
    input  wire logic clk,             // clock
    input  wire logic rst,             // reset
    input  wire logic start,           // start line drawing
    input  wire logic oe,              // output enable
    input  wire logic signed [CORDW-1:0] x0,  // point 0
    input  wire logic signed [CORDW-1:0] x1,  // point 1
    output      logic signed [CORDW-1:0] x,   // drawing position
    output      logic drawing,         // actively drawing
    output      logic busy,            // drawing request in progress
    output      logic done             // drawing is complete (high for one tick)
    );

    // draw state machine
    enum {IDLE, DRAW} state;
    always_comb drawing = (state == DRAW && oe);

    always_ff @(posedge clk) begin
        case (state)
            DRAW: begin
                if (oe) begin
                    if (x == x1) begin
                        state <= IDLE;
                        busy <= 0;
                        done <= 1;
                    end else begin
                        x <= x + 1;
                    end
                end
            end
            default: begin  // IDLE
                done <= 0;
                if (start) begin
                    state <= DRAW;
                    x <= x0;
                    busy <= 1;
                end
            end
        endcase

        if (rst) begin
            state <= IDLE;
            busy <= 0;
            done <= 0;
        end
    end
endmodule

This module retains the interface of draw_line but simplifies the implementation to one dimension. There’s a test bench you can use to exercise the module with Vivado: [xc7/draw_line_1d_tb.sv].

Next, create module [draw_rectangle_fill.sv]:

module draw_rectangle_fill #(parameter CORDW=16) (  // signed coordinate width
    input  wire logic clk,             // clock
    input  wire logic rst,             // reset
    input  wire logic start,           // start rectangle drawing
    input  wire logic oe,              // output enable
    input  wire logic signed [CORDW-1:0] x0, y0,  // vertex 0
    input  wire logic signed [CORDW-1:0] x1, y1,  // vertex 2
    output      logic signed [CORDW-1:0] x,  y,   // drawing position
    output      logic drawing,         // actively drawing
    output      logic busy,            // drawing request in progress
    output      logic done             // drawing is complete (high for one tick)
    );

    // filled rectangle has as many lines as it is tall abs(y1-y0)
    logic signed [CORDW-1:0] line_id;  // current line
    logic line_start;  // start drawing line
    logic line_done;   // finished drawing current line?

    // sort input Y coordinates so we always draw top-to-bottom
    logic signed [CORDW-1:0] y0s, y1s;  // vertex 0 - ordered
    always_comb begin
        y0s = (y0 > y1) ? y1 : y0;
        y1s = (y0 > y1) ? y0 : y1;  // last line
    end

    // horizontal line coordinates
    logic signed [CORDW-1:0] lx0, lx1;

    // draw state machine
    enum {IDLE, INIT, DRAW} state;
    always_ff @(posedge clk) begin
        case (state)
            INIT: begin  // register coordinates
                state <= DRAW;
                line_start <= 1;
                // x-coordinates don't change for a given filled rectangle
                lx0 <= (x0 > x1) ? x1 : x0;  // draw left-to-right
                lx1 <= (x0 > x1) ? x0 : x1;
                y <= y0s + line_id;  // vertical position
            end
            DRAW: begin
                line_start <= 0;
                if (line_done) begin
                    if (y == y1s) begin
                        state <= IDLE;
                        busy <= 0;
                        done <= 1;
                    end else begin
                        state <= INIT;
                        line_id <= line_id + 1;
                    end
                end
            end
            default: begin  // IDLE
                done <= 0;
                if (start) begin
                    state <= INIT;
                    line_id <= 0;
                    busy <= 1;
                end
            end
        endcase

        if (rst) begin
            state <= IDLE;
            line_id <= 0;
            line_start <= 0;
            busy <= 0;
            done <= 0;
        end
    end

    draw_line_1d #(.CORDW(CORDW)) draw_line_1d_inst (
        .clk,
        .rst,
        .start(line_start),
        .oe,
        .x0(lx0),
        .x1(lx1),
        .x(x),
        .drawing,
        .busy(),
        .done(line_done)
    );
endmodule

For a simple demo of overlapping squares using the filled rectangle module, create a new top module:

Drawing filled rectangles looks like this in the iCE40 version (note how we have to initialize the SPRAM framebuffer before use):

    // draw filled rectangles in framebuffer
    localparam SHAPE_CNT=15;  // number of shapes to draw
    logic [$clog2(SHAPE_CNT)-1:0] shape_id;  // shape identifier
    logic signed [CORDW-1:0] vx0, vy0, vx1, vy1;  // shape coords
    logic draw_start, drawing, draw_done;  // drawing signals

    // clear FB before use (contents are not initialized)
    logic signed [CORDW-1:0] fbx_clear, fby_clear;  // framebuffer clearing coordinates
    logic clearing;  // high when we're clearing

    // draw state machine
    enum {IDLE, CLEAR, INIT, DRAW, DONE} state;
    always_ff @(posedge clk_pix) begin
        case (state)
            CLEAR: begin  // we need to initialize SPRAM values to zero
                fb_cidx <= 4'h0;  // black
                if (!fb_busy) begin
                    if (fby_clear == FB_HEIGHT-1 && fbx_clear == FB_WIDTH-1) begin
                        clearing <= 0;
                        state <= INIT;
                    end else begin  // iterate over all pixels
                        if (clearing == 1) begin
                            if (fbx_clear == FB_WIDTH-1) begin
                                fbx_clear <= 0;
                                fby_clear <= fby_clear + 1;
                            end else begin
                                fbx_clear <= fbx_clear + 1;
                            end
                        end else clearing <= 1;
                    end
                end
            end
            INIT: begin  // register coordinates and colour
                draw_start <= 1;
                state <= DRAW;
                vx0 <=  80 + 4 * shape_id;
                vy0 <=  20 + 4 * shape_id;
                vx1 <= 160 + 4 * shape_id;
                vy1 <= 100 + 4 * shape_id;
                fb_cidx <= shape_id + 1;  // skip 1st colour (black)
            end
            DRAW: begin
                draw_start <= 0;
                if (draw_done) begin
                    if (shape_id == SHAPE_CNT-1) begin
                        state <= DONE;
                    end else begin
                        shape_id <= shape_id + 1;
                        state <= INIT;
                    end
                end
            end
            DONE: state <= DONE;
            default: if (frame) state <= CLEAR;  // IDLE
        endcase
        if (!clk_locked) state <= IDLE;
    end

    // control drawing speed with output enable
    localparam FRAME_WAIT = 300;  // wait this many frames to start drawing
    localparam PIX_FRAME  = 200;  // draw this many pixels per frame
    logic [$clog2(FRAME_WAIT)-1:0] cnt_frame_wait;
    logic [$clog2(PIX_FRAME)-1:0] cnt_pix_frame;
    logic draw_req;
    always_ff @(posedge clk_pix) begin
        draw_req <= 0;
        if (frame) begin
            if (cnt_frame_wait != FRAME_WAIT-1) cnt_frame_wait <= cnt_frame_wait + 1;
            cnt_pix_frame <= 0;  // reset pixel counter every frame
        end
        if (!fb_busy) begin
            if (cnt_frame_wait == FRAME_WAIT-1 && cnt_pix_frame != PIX_FRAME-1) begin
                draw_req <= 1;
                cnt_pix_frame <= cnt_pix_frame + 1;
            end
        end
    end

    logic signed [CORDW-1:0] fbx_draw, fby_draw;  // framebuffer drawing coordinates
    draw_rectangle_fill #(.CORDW(CORDW)) draw_rectangle_inst (
        .clk(clk_pix),
        .rst(!clk_locked),  // must be reset for draw with Yosys
        .start(draw_start),
        .oe(draw_req && !fb_busy),  // draw if requested when framebuffer is available
        .x0(vx0),
        .y0(vy0),
        .x1(vx1),
        .y1(vy1),
        .x(fbx_draw),
        .y(fby_draw),
        .drawing,
        .busy(),
        .done(draw_done)
    );

Filled Triangle

A filled triangle requires more thought than a rectangle. There are several quite different approaches, for example barycentric coordinates can be used to render many pixels in parallel. We’re going to stick with Bresenham’s algorithm, as it’s light on FPGA resources and can still draw over a million small triangles per second (based on 100 MHz Arty drawing clock and a 36-pixel triangle taking 97 clock cycles).

We use Bresenham to determine the triangle edges, then join them with a horizontal line. First we sort the vertices, so we always draw down, then we split the triangle into two flat triangles. More details to follow.

Create module [draw_triangle_fill.sv]:

module draw_triangle_fill #(parameter CORDW=16) (  // signed coordinate width
    input  wire logic clk,             // clock
    input  wire logic rst,             // reset
    input  wire logic start,           // start triangle drawing
    input  wire logic oe,              // output enable
    input  wire logic signed [CORDW-1:0] x0, y0,  // vertex 0
    input  wire logic signed [CORDW-1:0] x1, y1,  // vertex 1
    input  wire logic signed [CORDW-1:0] x2, y2,  // vertex 2
    output      logic signed [CORDW-1:0] x,  y,   // drawing position
    output      logic drawing,         // actively drawing
    output      logic busy,            // drawing request in progress
    output      logic done             // drawing is complete (high for one tick)
    );

    // sorted input vertices
    logic signed [CORDW-1:0] x0s, y0s, x1s, y1s, x2s, y2s;

    // line coordinates
    logic signed [CORDW-1:0] x0a, y0a, x1a, y1a, xa, ya;
    logic signed [CORDW-1:0] x0b, y0b, x1b, y1b, xb, yb;
    logic signed [CORDW-1:0] x0h, x1h, xh;

    // previous y-value for edges
    logic signed [CORDW-1:0] prev_y;

    // previous x-values for horizontal line
    logic signed [CORDW-1:0] prev_xa;
    logic signed [CORDW-1:0] prev_xb;

    // line control signals
    logic oe_a, oe_b, oe_h;
    logic drawing_h;
    logic busy_a, busy_b, busy_h;
    logic b_edge;  // which B edge are we drawing?

    // pipeline completion signals to match coordinates
    logic busy_p1, done_p1;

    // draw state machine
    enum {IDLE, SORT_0, SORT_1, SORT_2, INIT_A, INIT_B0, INIT_B1, INIT_H,
            START_A, START_B, START_H, EDGE, H_LINE, DONE} state;
    always_ff @(posedge clk) begin
        case (state)
            SORT_0: begin
                state <= SORT_1;
                if (y0 > y2) begin
                    x0s <= x2;
                    y0s <= y2;
                    x2s <= x0;
                    y2s <= y0;
                end else begin
                    x0s <= x0;
                    y0s <= y0;
                    x2s <= x2;
                    y2s <= y2;
                end
            end
            SORT_1: begin
                state <= SORT_2;
                if (y0s > y1) begin
                    x0s <= x1;
                    y0s <= y1;
                    x1s <= x0s;
                    y1s <= y0s;
                end else begin
                    x1s <= x1;
                    y1s <= y1;
                end
            end
            SORT_2: begin
                state <= INIT_A;
                if (y1s > y2s) begin
                    x1s <= x2;
                    y1s <= y2;
                    x2s <= x1s;
                    y2s <= y1s;
                end
            end
            INIT_A: begin
                state <= INIT_B0;
                x0a <= x0s;
                y0a <= y0s;
                x1a <= x2s;
                y1a <= y2s;
                prev_xa <= x0s;
                prev_xb <= x0s;
            end
            INIT_B0: begin
                state <= START_A;
                b_edge <= 0;
                x0b <= x0s;
                y0b <= y0s;
                x1b <= x1s;
                y1b <= y1s;
                prev_y <= y0s;
            end
            INIT_B1: begin
                state <= START_B;  // we don't need to start A again
                b_edge <= 1;
                x0b <= x1s;
                y0b <= y1s;
                x1b <= x2s;
                y1b <= y2s;
                prev_y <= y1s;
            end
            START_A: state <= START_B;
            START_B: state <= EDGE;
            EDGE: begin
                if ((ya != prev_y || !busy_a) && (yb != prev_y || !busy_b)) begin
                    state <= START_H;
                    x0h <= (prev_xa > prev_xb) ? prev_xb : prev_xa;  // always draw...
                    x1h <= (prev_xa > prev_xb) ? prev_xa : prev_xb;  // left to right
                end
            end
            START_H: state <= H_LINE;
            H_LINE: begin
                if (!busy_h) begin
                    prev_y <= yb;  // safe to update previous values once h-line done
                    prev_xa <= xa;
                    prev_xb <= xb;
                    if (!busy_b) begin
                        state <= (busy_a && b_edge == 0) ? INIT_B1 : DONE;
                    end else state <= EDGE;
                end
            end
            DONE: begin
                state <= IDLE;
                done_p1 <= 1;
                busy_p1 <= 0;
            end
            default: begin  // IDLE
                if (start) begin
                    state <= SORT_0;
                    busy_p1 <= 1;
                end
                done_p1 <= 0;
            end
        endcase

        if (rst) begin
            state <= IDLE;
            busy_p1 <= 0;
            done_p1 <= 0;
            b_edge <= 0;
        end
    end

    always_comb begin
        oe_a = (state == EDGE && ya == prev_y);
        oe_b = (state == EDGE && yb == prev_y);
        oe_h = oe;
    end

    // register output
    always_ff @(posedge clk) begin
        x <= xh;
        y <= prev_y;
        drawing <= drawing_h;
        busy <= busy_p1;
        done <= done_p1;
    end

    draw_line #(.CORDW(CORDW)) draw_edge_a (
        .clk,
        .rst,
        .start(state == START_A),
        .oe(oe_a),
        .x0(x0a),
        .y0(y0a),
        .x1(x1a),
        .y1(y1a),
        .x(xa),
        .y(ya),
        .drawing(),
        .busy(busy_a),
        .done()
    );

    draw_line #(.CORDW(CORDW)) draw_edge_b (
        .clk,
        .rst,
        .start(state == START_B),
        .oe(oe_b),
        .x0(x0b),
        .y0(y0b),
        .x1(x1b),
        .y1(y1b),
        .x(xb),
        .y(yb),
        .drawing(),
        .busy(busy_b),
        .done()
    );

    draw_line_1d #(.CORDW(CORDW)) draw_h_line (
        .clk,
        .rst,
        .start(state == START_H),
        .oe(oe_h),
        .x0(x0h),
        .x1(x1h),
        .x(xh),
        .drawing(drawing_h),
        .busy(busy_h),
        .done()
    );
endmodule

Here are are a couple of designs using filled triangles:

For top_triangles_fill, we draw 50 pixels per frame so you can clearly see the algorithm working. For top_cube_fill we draw at full speed.

Filled Cube

Top & Left
Two triangles share an edge; we need a mechanism to determine which triangle gets drawn. The standard approach is for top and left edges to be drawn. We won’t be handling this just yet.

Circles

Circles are straightforward to draw: I’ve based on my design on the algorithm from The Beauty of Bresenham’s Algorithm.

Create module [draw_circle.sv]:

module draw_circle #(parameter CORDW=16) (  // signed coordinate width
    input  wire logic clk,             // clock
    input  wire logic rst,             // reset
    input  wire logic start,           // start line drawing
    input  wire logic oe,              // output enable
    input  wire logic signed [CORDW-1:0] x0, y0,  // centre point
    input  wire logic signed [CORDW-1:0] r0,      // radius
    output      logic signed [CORDW-1:0] x,  y,   // drawing position
    output      logic drawing,         // actively drawing
    output      logic busy,            // drawing request in progress
    output      logic done             // drawing is complete (high for one tick)
    );

    // internal variables
    logic signed [CORDW-1:0] xa, ya;  // position relative to circle centre point
    logic signed [CORDW+1:0] err, err_tmp;  // error values (4x as wide as coords)
    logic [1:0] quadrant;  // circle quadrant

    // draw state machine
    enum {IDLE, CALC_Y, CALC_X, DRAW} state;
    always_ff @(posedge clk) drawing <= (state == DRAW && oe);  // 1 cycle delay in draw

    always_ff @(posedge clk) begin
        case (state)
            CALC_Y: begin
                if (xa == 0) begin
                    state <= IDLE;
                    busy <= 0;
                    done <= 1;
                end else begin
                    state <= CALC_X;
                    err_tmp <= err;  // save existing error for next step
                    if (err <= ya) begin
                        ya <= ya + 1;
                        err <= err + 2 * (ya + 1) + 1;
                    end
                end
            end
            CALC_X: begin
                state <= DRAW;
                if (err_tmp > xa || err > ya) begin
                    xa <= xa + 1;
                    err <= err + 2 * (xa + 1) + 1;
                end
            end
            DRAW: begin
                if (oe) begin
                    case (quadrant)
                        2'b00: begin  //   I Quadrant (+x +y)
                            x <= x0 - xa;
                            y <= y0 + ya;
                        end
                        2'b01: begin  //  II Quadrant (-x +y)
                            x <= x0 - ya;
                            y <= y0 - xa;
                        end
                        2'b10: begin  // III Quadrant (-x -y)
                            x <= x0 + xa;
                            y <= y0 - ya;
                        end
                        2'b11: begin  //  IV Quadrant (+x -y)
                            state <= CALC_Y;
                            x <= x0 + ya;
                            y <= y0 + xa;
                        end
                    endcase
                    quadrant <= quadrant + 1;  // next quadrant
                end
            end
            default: begin  // IDLE
                done <= 0;
                if (start) begin
                    state <= CALC_Y;
                    busy <= 1;
                    xa <= -r0;
                    ya <= 0;
                    err <= 2 - (2 * r0);
                    quadrant <= 0;
                end
            end
        endcase

        if (rst) begin
            state <= IDLE;
            busy <= 0;
            done <= 0;
        end
    end
endmodule

You can see a simple demo of circle drawing in these modules:

The demo slows drawing to just 30 pixels per frame, so you can see how the circle is formed from four quadrants.

There’s a Vivado test bench for circle module: [xc7/draw_circle_tb.sv].

Filled circles and further explanation of circle drawing to follow.

Drawing a Scene

We can combine different shapes to draw simple scenes. I knocked up this castle on graph paper.

Arty version of castle drawing:

module top_castle (
    input  wire logic clk_100m,     // 100 MHz clock
    input  wire logic btn_rst,      // reset button (active low)
    output      logic vga_hsync,    // horizontal sync
    output      logic vga_vsync,    // vertical sync
    output      logic [3:0] vga_r,  // 4-bit VGA red
    output      logic [3:0] vga_g,  // 4-bit VGA green
    output      logic [3:0] vga_b   // 4-bit VGA blue
    );

    // generate pixel clock
    logic clk_pix;
    logic clk_locked;
    clock_gen_480p clock_pix_inst (
       .clk(clk_100m),
       .rst(!btn_rst),  // reset button is active low
       .clk_pix,
       .clk_locked
    );

    // display timings
    localparam CORDW = 16;
    logic signed [CORDW-1:0] sx, sy;
    logic hsync, vsync;
    logic de, frame, line;
    display_timings_480p #(.CORDW(CORDW)) display_timings_inst (
        .clk_pix,
        .rst(!clk_locked),  // wait for pixel clock lock
        .sx,
        .sy,
        .hsync,
        .vsync,
        .de,
        .frame,
        .line
    );

    logic frame_sys;  // start of new frame in system clock domain
    xd xd_frame (.clk_i(clk_pix), .clk_o(clk_100m),
                 .rst_i(1'b0), .rst_o(1'b0), .i(frame), .o(frame_sys));

    // framebuffer (FB)
    localparam FB_WIDTH   = 320;
    localparam FB_HEIGHT  = 180;
    localparam FB_CIDXW   = 4;
    localparam FB_CHANW   = 4;
    localparam FB_SCALE   = 2;
    localparam FB_IMAGE   = "";
    localparam FB_PALETTE = "16_colr_4bit_palette.mem";

    logic fb_we;  // write enable
    logic signed [CORDW-1:0] fbx, fby;  // draw coordinates
    logic [FB_CIDXW-1:0] fb_cidx;  // draw colour index
    logic fb_busy;  // when framebuffer is busy it cannot accept writes
    logic [FB_CHANW-1:0] fb_red, fb_green, fb_blue;  // colours for display output

    framebuffer_bram #(
        .WIDTH(FB_WIDTH),
        .HEIGHT(FB_HEIGHT),
        .CIDXW(FB_CIDXW),
        .CHANW(FB_CHANW),
        .SCALE(FB_SCALE),
        .F_IMAGE(FB_IMAGE),
        .F_PALETTE(FB_PALETTE)
    ) fb_inst (
        .clk_sys(clk_100m),
        .clk_pix,
        .rst_sys(1'b0),
        .rst_pix(1'b0),
        .de(sy >= 60 && sy < 420 && sx >= 0),  // 16:9 letterbox
        .frame,
        .line,
        .we(fb_we),
        .x(fbx),
        .y(fby),
        .cidx(fb_cidx),
        .clip(),
        .busy(fb_busy),
        .red(fb_red),
        .green(fb_green),
        .blue(fb_blue)
    );

    // draw shapes in framebuffer
    localparam SHAPE_CNT=19;  // number of shapes to draw
    logic [$clog2(SHAPE_CNT)-1:0] shape_id;  // shape identifier
    logic signed [CORDW-1:0] vx0, vy0, vx1, vy1, vx2, vy2;  // shape coords
    logic signed [CORDW-1:0] fbx_tri, fby_tri;    // tri framebuffer coordinates
    logic signed [CORDW-1:0] fbx_rect, fby_rect;  // rect framebuffer coordinates
    logic drawing, draw_done;  // combined drawing signals
    logic draw_start_tri, drawing_tri, draw_done_tri;  // drawing tri
    logic draw_start_rect, drawing_rect, draw_done_rect;  // drawing rect

    // draw state machine
    enum {IDLE, INIT, DRAW, DONE} state;
    always_ff @(posedge clk_100m) begin
        case (state)
            INIT: begin  // register coordinates and colour
                state <= DRAW;
                case (shape_id)
                    5'd0: begin  // main building
                        draw_start_rect <= 1;
                        vx0 <=  60; vy0 <=  70;
                        vx1 <= 190; vy1 <= 120;
                        fb_cidx <= 4'h5;  // dark grey
                    end
                    5'd1: begin  // drawbridge
                        draw_start_rect <= 1;
                        vx0 <= 110; vy0 <=  90;
                        vx1 <= 140; vy1 <= 120;
                        fb_cidx <= 4'h4;  // brown
                    end
                    5'd2: begin  // arch left
                        draw_start_tri <= 1;
                        vx0 <= 110; vy0 <=  90;
                        vx1 <= 120; vy1 <=  90;
                        vx2 <= 110; vy2 <= 100;
                        fb_cidx <= 4'h5;  // dark grey
                    end
                    5'd3: begin  // arch right
                        draw_start_tri <= 1;
                        vx0 <= 130; vy0 <=  90;
                        vx1 <= 140; vy1 <=  90;
                        vx2 <= 140; vy2 <= 100;
                        fb_cidx <= 4'h5;  // dark grey
                    end
                    5'd4: begin  // left tower
                        draw_start_rect <= 1;
                        vx0 <=  40; vy0 <=  45;
                        vx1 <=  60; vy1 <= 120;
                        fb_cidx <= 4'h5;  // dark grey
                    end
                    5'd5: begin  // middle tower
                        draw_start_rect <= 1;
                        vx0 <= 110; vy0 <=  40;
                        vx1 <= 140; vy1 <=  70;
                        fb_cidx <= 4'h5;  // dark grey
                    end
                    5'd6: begin  // right tower
                        draw_start_rect <= 1;
                        vx0 <= 190; vy0 <=  45;
                        vx1 <= 210; vy1 <= 120;
                        fb_cidx <= 4'h5;  // dark grey
                    end
                    5'd7: begin  // left roof
                        draw_start_tri <= 1;
                        vx0 <=  50; vy0 <=  30;
                        vx1 <=  65; vy1 <=  45;
                        vx2 <=  35; vy2 <=  45;
                        fb_cidx <= 4'h2;  // dark-purple
                    end
                    5'd8: begin  // middle roof
                        draw_start_tri <= 1;
                        vx0 <= 125; vy0 <=  20;
                        vx1 <= 145; vy1 <=  40;
                        vx2 <= 105; vy2 <=  40;
                        fb_cidx <= 4'h2;  // dark-purple
                    end
                    5'd9: begin  // right roof
                        draw_start_tri <= 1;
                        vx0 <= 200; vy0 <=  30;
                        vx1 <= 215; vy1 <=  45;
                        vx2 <= 185; vy2 <=  45;
                        fb_cidx <= 4'h2;  // dark-purple
                    end
                    5'd10: begin  // left window
                        draw_start_rect <= 1;
                        vx0 <=  46; vy0 <=  50;
                        vx1 <=  54; vy1 <=  65;
                        fb_cidx <= 4'h1;  // dark blue
                    end
                    5'd11: begin  // middle window
                        draw_start_rect <= 1;
                        vx0 <= 120; vy0 <=  45;
                        vx1 <= 130; vy1 <=  65;
                        fb_cidx <= 4'h1;  // dark blue
                    end
                    5'd12: begin  // right window
                        draw_start_rect <= 1;
                        vx0 <= 196; vy0 <=  50;
                        vx1 <= 204; vy1 <=  65;
                        fb_cidx <= 4'h1;  // dark blue
                    end
                    5'd13: begin  // battlement 1
                        draw_start_rect <= 1;
                        vx0 <=  63; vy0 <=  62;
                        vx1 <=  72; vy1 <=  70;
                        fb_cidx <= 4'h5;  // dark grey
                    end
                    5'd14: begin  // battlement 2
                        draw_start_rect <= 1;
                        vx0 <=   80; vy0 <=  62;
                        vx1 <=   89; vy1 <=  70;
                        fb_cidx <= 4'h5;  // dark grey
                    end
                    5'd15: begin  // battlement 3
                        draw_start_rect <= 1;
                        vx0 <=  97; vy0 <=  62;
                        vx1 <= 106; vy1 <=  70;
                        fb_cidx <= 4'h5;  // dark grey
                    end
                    5'd16: begin  // battlement 4
                        draw_start_rect <= 1;
                        vx0 <= 144; vy0 <=  62;
                        vx1 <= 153; vy1 <=  70;
                        fb_cidx <= 4'h5;  // dark grey
                    end
                    5'd17: begin  // battlement 5
                        draw_start_rect <= 1;
                        vx0 <= 161; vy0 <=  62;
                        vx1 <= 170; vy1 <=  70;
                        fb_cidx <= 4'h5;  // dark grey
                    end
                    5'd18: begin  // battlement 6
                        draw_start_rect <= 1;
                        vx0 <= 178; vy0 <=  62;
                        vx1 <= 187; vy1 <=  70;
                        fb_cidx <= 4'h5;  // dark grey
                    end
                    default: begin  // should never occur
                        draw_start_tri <= 1;
                        vx0 <=   10; vy0 <=   10;
                        vx1 <=   10; vy1 <=   30;
                        vx2 <=   20; vy2 <=   20;
                        fb_cidx <= 4'h7;  // white
                    end
                endcase
            end
            DRAW: begin
                draw_start_rect <= 0;
                draw_start_tri <= 0;
                if (draw_done) begin
                    if (shape_id == SHAPE_CNT-1) begin
                        state <= DONE;
                    end else begin
                        shape_id <= shape_id + 1;
                        state <= INIT;
                    end
                end
            end
            DONE: state <= DONE;
            default: if (frame_sys) state <= INIT;  // IDLE
        endcase
    end

    // drawing and done apply to all drawing types
    always_comb begin
        drawing = drawing_tri || drawing_rect;
        draw_done = draw_done_tri || draw_done_rect;
    end

    // control drawing speed with output enable
    localparam FRAME_WAIT = 300;  // wait this many frames to start drawing
    localparam PIX_FRAME  =  20;  // draw this many pixels per frame
    logic [$clog2(FRAME_WAIT)-1:0] cnt_frame_wait;
    logic [$clog2(PIX_FRAME)-1:0] cnt_pix_frame;
    logic draw_req;
    always_ff @(posedge clk_100m) begin
        draw_req <= 0;
        if (frame_sys) begin
            if (cnt_frame_wait != FRAME_WAIT-1) cnt_frame_wait <= cnt_frame_wait + 1;
            cnt_pix_frame <= 0;  // reset pixel counter every frame
        end
        if (!fb_busy) begin
            if (cnt_frame_wait == FRAME_WAIT-1 && cnt_pix_frame != PIX_FRAME-1) begin
                draw_req <= 1;
                cnt_pix_frame <= cnt_pix_frame + 1;
            end
        end
    end

    draw_triangle_fill #(.CORDW(CORDW)) draw_triangle_inst (
        .clk(clk_100m),
        .rst(1'b0),
        .start(draw_start_tri),
        .oe(draw_req && !fb_busy),  // draw if requested when framebuffer is available
        .x0(vx0),
        .y0(vy0),
        .x1(vx1),
        .y1(vy1),
        .x2(vx2),
        .y2(vy2),
        .x(fbx_tri),
        .y(fby_tri),
        .drawing(drawing_tri),
        .busy(),
        .done(draw_done_tri)
    );

    draw_rectangle_fill #(.CORDW(CORDW)) draw_rectangle_inst (
        .clk(clk_100m),
        .rst(1'b0),
        .start(draw_start_rect),
        .oe(draw_req && !fb_busy),  // draw if requested when framebuffer is available
        .x0(vx0),
        .y0(vy0),
        .x1(vx1),
        .y1(vy1),
        .x(fbx_rect),
        .y(fby_rect),
        .drawing(drawing_rect),
        .busy(),
        .done(draw_done_rect)
    );

    // write to framebuffer when drawing
    always_ff @(posedge clk_100m) begin
        fb_we <= drawing;
        fbx <= drawing_tri ? fbx_tri : fbx_rect;
        fby <= drawing_tri ? fby_tri : fby_rect;
    end

    // reading from FB takes one cycle: delay display signals to match
    logic hsync_p1, vsync_p1;
    always_ff @(posedge clk_pix) begin
        hsync_p1 <= hsync;
        vsync_p1 <= vsync;
    end

    // background colour (sy ignores 16:9 letterbox)
    logic [11:0] bg_colr;
    always_ff @(posedge clk_pix) begin
        if (line) begin
            if      (sy ==   0) bg_colr <= 12'h000;
            else if (sy ==  60) bg_colr <= 12'h239;
            else if (sy == 130) bg_colr <= 12'h24A;
            else if (sy == 175) bg_colr <= 12'h25B;
            else if (sy == 210) bg_colr <= 12'h26C;
            else if (sy == 240) bg_colr <= 12'h27D;
            else if (sy == 265) bg_colr <= 12'h29E;
            else if (sy == 285) bg_colr <= 12'h2BF;
            else if (sy == 302) bg_colr <= 12'h260;  // below castle (2x pix)
            else if (sy == 420) bg_colr <= 12'h000;
        end
    end

    logic show_bg;
    always_comb show_bg = (de && {fb_red,fb_green,fb_blue} == 0);

    // VGA output
    always_ff @(posedge clk_pix) begin
        vga_hsync <= hsync_p1;
        vga_vsync <= vsync_p1;
        vga_r <= show_bg ? bg_colr[11:8] : fb_red;
        vga_g <= show_bg ? bg_colr[7:4]  : fb_green;
        vga_b <= show_bg ? bg_colr[3:0]  : fb_blue;
    end
endmodule

The castle design switches between two drawing modules: for rectangles and triangles. You can see this as the start of a simple 2D graphics accelerator. Note how the background coordinate has to be one scaled unit below the castle because of how the coordinates work. More details to follow.

Castle

Explore

I hope you enjoyed this instalment of Exploring FPGA Graphics, but nothing beats creating your own designs. Here are a few suggestions to get you started:

Suggestions will be added soon.

Sponsor Project F
If you like what I do, consider sponsoring me on GitHub.
I’ll use contributions to spend more time creating open-source FPGA designs and tutorials.

Next Time

Next time, we’ll be moving around with Animated Shapes. See you there.

Constructive feedback is always welcome. Get in touch with @WillFlux or open an issue on GitHub.

©2021 Will Green, Project F