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. This post was last updated in January 2022.

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 Intro to FPGA Graphics.

Get in touch: GitHub Issues, 1BitSquared Discord, @WillFlux (Mastodon), @WillFlux (Twitter)

Series Outline

Sponsor My Work
If you like what I do, consider sponsoring me on GitHub.
I love FPGAs and want to help more people discover and use them in their projects.
My hardware designs are open source, and my blog is advert free.

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 sync signals and coordinates
    localparam CORDW = 16;
    logic signed [CORDW-1:0] sx, sy;
    logic hsync, vsync;
    logic frame, line;
    display_480p #(.CORDW(CORDW)) display_inst (
        .clk_pix,
        .rst(!clk_locked),
        .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

Shared Responsibility
When two triangles share an edge, we need to decide which triangle draws that edge. The standard approach is to draw the top and left edges, but we won’t be handling this just yet.

Circles

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

The outline version is shown below:

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 + xa;
                            y <= y0 + ya;
                        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 - xa;
                            y <= y0 - ya;
                        end
                    endcase
                    quadrant <= quadrant + 1;  // next quadrant
                end
            end
            default: begin  // IDLE
                done <= 0;
                if (start) begin
                    state <= DRAW;
                    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.

I’ve also drawn a rainbow with filled circles:

Rainbow

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

Further explanation of circle drawing to follow.

Making a Scene

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

The castle design switches between three filled drawing modules: triangles, rectangles, and circles. 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 Scene

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:

  • Add some clouds and trees to the castle scene

More suggestions will be added soon.

Next Time

Next time, we’ll be moving around with Animated Shapes. Check out the site map for more FPGA projects and tutorials.

Get in touch: GitHub Issues, 1BitSquared Discord, @WillFlux (Mastodon), @WillFlux (Twitter)

©2022 Will Green, Project F