Add main Reuleaux triangle geometry code for task 4

Extra pixels still need to be handled in the future.

Signed-off-by: Warrick Lo <wlo@warricklo.net>

1 files changed, 174 insertions, 7 deletions

diff --git a/task4/reuleaux.sv b/task4/reuleaux.sv
index abcde5e..0b08225 100644
--- a/task4/reuleaux.sv
+++ b/task4/reuleaux.sv
@@ -1,8 +1,175 @@
-module reuleaux(input logic clk, input logic rst_n, input logic [2:0] colour,
-                input logic [7:0] centre_x, input logic [6:0] centre_y, input logic [7:0] diameter,
-                input logic start, output logic done,
-                output logic [7:0] vga_x, output logic [6:0] vga_y,
-                output logic [2:0] vga_colour, output logic vga_plot);
-     // draw the Reuleaux triangle
-endmodule
+`define VGA_W 160
+`define VGA_H 120
 
+module reuleaux(clk, rst_n, colour, centre_x, centre_y, diameter, start, done,
+	vga_x, vga_y, vga_colour, vga_plot);
+
+	input logic clk, rst_n, start;
+	input logic [2:0] colour;
+	input logic [6:0] centre_y;
+	input logic [7:0] centre_x, diameter;
+
+	output logic done, vga_plot;
+	output logic [2:0] vga_colour;
+	output logic [6:0] vga_y;
+	output logic [7:0] vga_x;
+
+	logic clear, ready, vga_plot_next;
+	logic [2:0] octant;
+	logic [7:0] offset_x, offset_y, offset_x_next, offset_y_next;
+	/* One bit larger since these are signed. */
+	logic signed [7:0] vga_y_next;
+	logic signed [8:0] vga_x_next, crit, crit_next;
+
+	logic [6:0] centre_y1, centre_y2, centre_y3;
+	logic [7:0] centre_x1, centre_x2, centre_x3, radius;
+	/* Auxiliary value for calculations. */
+	logic [19:0] y_offset;
+
+	assign vga_colour = clear ? 3'b000 : colour;
+	/* Circle radius is the same as the Reuleaux triangle diameter. */
+	assign radius = diameter;
+
+	/* sqrt(3)/3 * 2^12 = 2364.826...
+	 * Add 2^(N-1) before shifting by N to round
+	 * to the nearest integer. */
+	assign y_offset = diameter * 2365;
+	assign centre_x1 = centre_x;
+	assign centre_y1 = centre_y - ((y_offset + (1 << 11)) >> 12);
+	assign centre_x2 = centre_x + (diameter >> 1);
+	assign centre_y2 = centre_y + ((y_offset + (1 << 12)) >> 13);
+	assign centre_x3 = centre_x - (diameter >> 1);
+	assign centre_y3 = centre_y + ((y_offset + (1 << 12)) >> 13);
+
+	/* Draw only the octants that are needed for each circle:
+	 * - circle 1: octants 2 & 3;
+	 * - circle 2: octants 5 & 6;
+	 * - circle 3: octants 7 & 8.
+	 * Extra pixels will be taken care further below (not implemented). */
+	always_comb case (octant)
+		3'd0: begin
+			vga_plot_next = 1'b0;
+			vga_x_next = centre_x + offset_x;
+			vga_y_next = centre_y + offset_y;
+		end
+		3'd1: begin
+			vga_plot_next = 1'b1;
+			vga_x_next = centre_x1 + offset_y;
+			vga_y_next = centre_y1 + offset_x;
+		end
+		3'd2: begin
+			vga_plot_next = 1'b1;
+			vga_x_next = centre_x1 - offset_y;
+			vga_y_next = centre_y1 + offset_x;
+		end
+		3'd3: begin
+			vga_plot_next = 1'b0;
+			vga_x_next = centre_x - offset_x;
+			vga_y_next = centre_y + offset_y;
+		end
+		3'd4: begin
+			vga_plot_next = 1'b1;
+			vga_x_next = centre_x2 - offset_x;
+			vga_y_next = centre_y2 - offset_y;
+		end
+		3'd5: begin
+			vga_plot_next = 1'b1;
+			vga_x_next = centre_x2 - offset_y;
+			vga_y_next = centre_y2 - offset_x;
+		end
+		3'd6: begin
+			vga_plot_next = 1'b1;
+			vga_x_next = centre_x3 + offset_y;
+			vga_y_next = centre_y3 - offset_x;
+		end
+		3'd7: begin
+			vga_plot_next = 1'b1;
+			vga_x_next = centre_x3 + offset_x;
+			vga_y_next = centre_y3 - offset_y;
+		end
+	endcase
+
+	always_comb begin
+		offset_x_next = offset_x;
+		offset_y_next = offset_y + 1;
+
+		if (crit <= 0)
+			crit_next = crit + 2 * offset_y_next + 1;
+		else begin
+			offset_x_next = offset_x - 1;
+			crit_next = crit
+				+ 2 * (offset_y_next - offset_x_next) + 1;
+		end
+	end
+
+	always_ff @(posedge clk) begin
+		if (~rst_n) begin
+			done <= 1'b0;
+			ready <= 1'b0;
+
+			/* Start clearing the screen. */
+			clear <= 1'b1;
+			vga_x <= 8'b0;
+			vga_y <= 7'b0;
+			vga_plot <= 1'b1;
+		end
+
+		/* Clear the screen. */
+		if (clear) begin
+			if (vga_y < 120) begin
+				/* Check for one column less since it takes
+				 * one clock cycle to reset and increment. */
+				if (vga_x < 159)
+					vga_x <= vga_x + 1;
+				else begin
+					vga_x <= 8'b0;
+					vga_y <= vga_y + 1;
+				end
+			end else begin
+				clear <= 1'b0;
+				ready <= 1'b1;
+				vga_x <= 8'b0;
+				vga_y <= 7'b0;
+				vga_plot <= 1'b0;
+			end
+		/* Initialise the registers for the circle algorithm. */
+		end else if (ready && start && ~done) begin
+			ready <= 1'b0;
+			octant <= 3'b0;
+			offset_y <= 8'b0;
+			offset_x <= radius;
+			crit <= 1 - radius;
+		/* Draw the circle using the Bresenham circle algorithm. */
+		end else if (start && ~done) begin
+			if (offset_y <= offset_x) begin
+				if ((vga_x_next >= 0) && (vga_x_next <= `VGA_W))
+					vga_x <= vga_x_next;
+				if ((vga_y_next >= 0) && (vga_y_next <= `VGA_H))
+					vga_y <= vga_y_next;
+
+				/* Plot only within the monitor's geometry. */
+				vga_plot <= (vga_plot_next
+					&& (vga_x_next >= 0)
+					&& (vga_x_next <= `VGA_W)
+					&& (vga_y_next >= 0)
+					&& (vga_y_next <= `VGA_H));
+
+				octant <= octant + 1;
+
+				/* The last octant. */
+				if (octant == 7) begin
+					offset_x <= offset_x_next;
+					offset_y <= offset_y_next;
+					crit <= crit_next;
+				end
+			/* Finished. */
+			end else begin
+				done <= 1'b1;
+				ready <= 1'b1;
+				vga_plot <= 1'b0;
+			end
+		/* Wait for start to be deasserted. */
+		end else if (~start && done)
+			done <= 1'b0;
+	end
+endmodule: reuleaux