1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
`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, vga_plot_next;
logic [2:0] octant;
/* Auxiliary value for calculations. 21-bit number since we multiply
* 8-bit and 13-bit numbers together. */
logic [20:0] diameter_scaled;
/* Extra bits to fix incorrect geometry when drawing at large radii. */
logic signed [8:0] vga_y_next, offset_y, offset_y_next,
centre_y1, centre_y2, centre_y3;
logic signed [9:0] vga_x_next, offset_x, offset_x_next,
centre_x1, centre_x2, centre_x3, crit, crit_next, radius;
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 diameter_scaled = diameter * 2365;
assign centre_x1 = centre_x;
assign centre_y1 = centre_y - ((diameter_scaled + (1 << 11)) >> 12);
assign centre_x2 = centre_x + (diameter >> 1);
assign centre_y2 = centre_y + ((diameter_scaled + (1 << 12)) >> 13);
assign centre_x3 = centre_x - (diameter >> 1);
assign centre_y3 = centre_y + ((diameter_scaled + (1 << 12)) >> 13);
/* Draw only the octants that are needed for each circle.
* Extra pixels will be taken care further below. */
always_comb case (octant)
/* Circle 1: octants 2 and 3. */
3'd0: begin
vga_x_next = centre_x1 + offset_y;
vga_y_next = centre_y1 + offset_x;
end
3'd1: begin
vga_x_next = centre_x1 - offset_y;
vga_y_next = centre_y1 + offset_x;
end
/* Circle 2: octants 5 and 6. */
3'd2: begin
vga_x_next = centre_x2 - offset_x;
vga_y_next = centre_y2 - offset_y;
end
3'd3: begin
vga_x_next = centre_x2 - offset_y;
vga_y_next = centre_y2 - offset_x;
end
/* Circle 3: octants 7 and 8. */
3'd4: begin
vga_x_next = centre_x3 + offset_y;
vga_y_next = centre_y3 - offset_x;
end
3'd5: begin
vga_x_next = centre_x3 + offset_x;
vga_y_next = centre_y3 - offset_y;
end
default: begin
vga_x_next = 9'bx;
vga_y_next = 8'bx;
end
endcase
/* Only plot the pixels of the triangle. */
always_comb begin
vga_plot_next = 1'b0;
/* Pixels of circle 1 that are between the centres
* of circle 2 and 3. */
if (octant == 3'd0)
if (vga_x_next <= centre_x2)
vga_plot_next = 1'b1;
if (octant == 3'd1)
if (vga_x_next >= centre_x3)
vga_plot_next = 1'b1;
/* Pixels of circle 2 that are to the left of the centre. */
if ((octant == 3'd2) || (octant == 3'd3))
if (vga_x_next <= centre_x)
vga_plot_next = 1'b1;
/* Pixels of circle 3 that are to the right of the centre. */
if ((octant == 3'd4) || (octant == 3'd5))
if (vga_x_next >= centre_x)
vga_plot_next = 1'b1;
end
/* Main combinational logic for the Bresenham circle algorithm. */
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;
/* Initialise the registers for the circle algorithm. */
vga_x <= 8'b0;
vga_y <= 7'b0;
vga_plot <= 1'b0;
octant <= 3'b0;
offset_y <= 9'b0;
offset_x <= radius;
crit <= 1 - radius;
end
/* Draw the circle using the Bresenham circle algorithm. */
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));
/* The last octant. */
if (octant == 5) begin
offset_x <= offset_x_next;
offset_y <= offset_y_next;
crit <= crit_next;
octant <= 3'b0;
end else
octant <= octant + 1;
/* Finished. */
end else begin
done <= 1'b1;
vga_plot <= 1'b0;
end
/* Wait for start to be deasserted. */
end else if (~start && done)
done <= 1'b0;
end
endmodule: reuleaux
|
