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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
`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.
* 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 below the centre of 2 or 3. */
if ((octant == 3'd0) || (octant == 3'd1))
if (vga_y_next > centre_y2)
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;
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));
/* 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;
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
|
