В конце сентября – в начале октября в Барнауле прошел кейс-чемпионат «Код успеха». О чемпионате можно прочитать здесь. Один из кейсов “Retro Game Console” и подразумевал разработку на ПЛИС. Частью кейса было задание разработать векторную каркасную картинку-чертёж. Это в свою очередь потребовало реализовать модуль который будет отрисовывать линии. Вспомнив по алгоритм Брезенхэма я взялся за работу. Реализация заняла значительно больше времени чем я планировал, был момент когда я думал, что задача не решаема при данных условиях. Надо сказать, что в видео-контроллере не было фреймбуффера, изображение нужно было формировать «на лету» в процессе развертки кадра.
Для тех кто забыл в чем суть алгоритма Брезенхэма напомню в двух словах.
Скрытый текст
Рассмотрим построение линии в диапазоне углов 0-45⁰. У нас есть точки начала(Х1,Y1) и конца отрезка(X2,Y). Для начала вспомним уравнение прямой из школьного учебника
Не трудно заметить что значение y увеличивается на k при изменении x на 1. Перепишем эту формулу в итерационном виде.
Значение y на каждом шаге отклоняется от первоначального на значение k и в какой‑то момент отклонение превышает 1.
Введем промежуточную переменную error и будем добавлять к ней на каждом шаге коэффициент k. В момент, когда error превысит 1, перенесем 1 из error в y, то есть добавим 1 к y, а из error 1 вычтем. Это позволит использовать целочисленную переменную y. Но для накопления отклонения пока все еще используется переменная error с плавающей запятой. Для перехода к целочисленной арифметике нам нужно избавится от дробного коэффициента k. Это возможно умножив k на Δx. В этом случае k превращается в Δy. А сравнение переменной error нужно делать не с 1 а с Δx. .
Тогда формула координат новой точки принимает вид
В этом случае все переменные целочисленные.
В общем, реализовать алгоритм Брезенхэма для прямых с наклоном 0⁰-45⁰ не сложно. Нам надо хранить информацию о координатах текущей точки и вычислять координаты следующей. Для реализации я использовал блок always_comb для вычисления координат новой точки и блок always_ff для сохранения полученных значений.
always_comb begin
new_y = dot_y;
if ((error + dy) > dx) begin
new_error = error + dy - dx;
new_y = dot_y + 1;
end
else
new_error = error + dy;
end
always_ff @(posedge clk)
if (start_frame) begin
dot_x <= in_x1;
dot_y <= in_y1;
error <= '0;
end
else
if (en) begin
dot_x <= dot_x + 1;
dot_y <= new_y;
error <= new_error;
end
Работа блока always_comb прозрачна не содержит ни каких хитростей. Про блок always_ff нужно сказать пару слов. Так как, точки мы формируем «на лету», то в начале каждого кадра нужно провести сброс переменных в начальное состояние. Это мы делаем по сигналу start_frame. В остальное время сохраняем значения координат и ошибки в регистрах. Кроме вычисления значений координат нужно синхронизировать вычисление новых точек с их отображением. В моем случае частота тактирования в два раза превышает частоту вывода пикселей. То есть схема может посчитать координаты двух точек за время отоб��ажения одной. Для синхронизации процессов вычисления и отображения ввел сигнал en.
assign en = (y == dot_y) & (x == dot_x) & (x <= in_x2); Сигнал en обеспечивает расчет одной следующей точки за время отображения текущей. Точки подсвечиваем, если координаты отображаемой точки совпадают с рассчитанными координатами.
assign out = (x == dot_x) & (y == dot_y);После синтеза проекта на экране я увидел такую картинку.
Линия как будто есть и в тоже время как будто нет. Линия получилась очень бледной. Поиск причин показал, что дело в строке формирования выходного сигнала.
assign out = (x == dot_x) & (y == dot_y);Сигнал формируется пока не вычисляться координаты следующей точки. В моем случае это половина времени отображения точки, соответственно яркость линии получается низкой. Для повышения яркости сигнал выхода пришлось сохранять сигнал в триггере и обновлять значение один раз за время отображения пикселя. Для этого я добавил два блока always_ff.
always_ff @(posedge clk)
pred_x <= x[0];
assign strobe_x = x ^ pred_x;
always_ff @(posedge clk)
if (strobe_x) line_out <= (x == dot_x) & (y == dot_y);
assign out = line_out;
В первом always блоке выделяем момент изменения координаты x во втором блоке собственно сохраняем значение выходного сигнала.
Как видно не вооруженным глазом яркость линии повысилась.
Следующим этапом разработки была задача отображения линий в секторе 45⁰-90⁰. Очевидно что описанный выше алгоритм не может корректно отображать линии секторе 45⁰-90⁰. Вопрос решается достаточно просто, нужно провести замену осей x и y. То есть на каждом шаге увеличивать y, а x изменять в зависимости от накопленной ошибки. И естественно нужно добавить сигнал выбора режима. Код стал значительно сложнее.
assign s1 = ((x2 - x1) >= (y2 - y1))? 1'b1: 1'b0; // sertor 0-45
assign s2 = ((x2 - x1) < (y2 - y1))? 1'b1: 1'b0;
assign s1 = ((x2 - x1) >= (y2 - y1))? 1'b1: 1'b0; // sector 45-90
assign s2 = ((x2 - x1) < (y2 - y1))? 1'b1: 1'b0;
always_comb begin
new_y = dot_y;
new_x = dot_x;
new_error = error;
case ({s2,s1})
2'b01: if ((error + dy) > dx) begin
new_error = error + dy - dx;
new_y = dot_y + 1;
end
else
new_error = error + dy;
2'b10: if ((error + dx) > dy) begin
new_error = error + dx - dy;
new_x = dot_x + 1;
end
else
new_error = error + dx;
endcase
end
always_ff @(posedge clk)
if (start_frame) begin
dot_x <= in_x1;
dot_y <= in_y1;
error <= '0;
end
else begin
// sector 1
if (en1) begin
dot_x <= dot_x + 1;
dot_y <= new_y;
error <= new_error;
end
// sector 2
if (en2) begin
dot_x <= new_x;
dot_y <= dot_y + 1 ;
error <= new_error;
end
end
Построение линии в секторе 45⁰-90⁰ выполняется аналогично построению в секторе 45⁰-90⁰, с той разницей, что x нужно не увеличивать, а уменьшать при накоплении ошибки. При реализации алгоритма для секторов 45⁰-90⁰ и 90⁰-135⁰ особых проблем не возникло.
А вот построение линии в секторе 135⁰-180⁰ меня сильно озадачило. Я даже думал, что при данных условиях построить линию в диапазоне 135⁰-180⁰. Я не понимал как отображать точки время отображения которых уже прошло.
Даже появилось желание создать машину времени. Было бы замечательно в момент ti вычислять координату следующей точки, переносится в момент ti-1 и ее отображать. Потом вычислять координаты следующей точки переносится в момент ti-2 и так далее. Потихоньку в своих мечтах я дошел до начала строки и тут я испытал чувство которое испытывал Архимед бегая голым по городу и крича "Эврика". Я понял, что мне не нужна машина времени, мне нужны координаты начала и конца горизонтального отрезка который подсветить в текущей строке. А рассчитать эти координаты я могу находясь в предшествующей строке.
Алгоритм такой - введем две переменные x_st и x_end для хранения координат начала и конца отрезка, в начале кадра переменным dot_x и x_st присваиваем значение x1. В строке предшествующей первой строке линии начинаем вычислять error пока не превысим dx при этом не забываем уменьшать dot_x при каждом вычислении. В конце строки значение x_st записываем в x_end, а dot_x в x_st, error уменьшаем на значение dx. Продолжаем пока не дойдем до y2. Реализация алгоритма рисования линий в диапазоне 0⁰-180⁰ на systemverilog выглядит так:
// calculate error and new dot
always_comb begin
new_y = dot_y;
new_x = dot_x;
new_error = error;
case ({s4,s3,s2,s1})
4'b0001: if ((error + dy) > dx) begin // sector 1
new_error = error + dy - dx;
new_y = dot_y + 1;
end
else
new_error = error + dy;
4'b0010,
4'b0100: if ((error + dx) > dy) begin // sectors 2, 3
new_error = error + dx - dy ;
if(s2)
new_x = dot_x + 1;
else
new_x = dot_x - 1;
end
else
new_error = error + dx;
4'b1000: new_error = error + dy; // sector 4
endcase
end
always_ff @(posedge clk)
if (start_frame) begin
dot_x <= in_x1;
dot_y <= in_y1;
error <= '0;
x_end <= in_x1; // for 4 sector
end
else begin
// sector 1
if (en1) begin
dot_x <= dot_x + 1;
dot_y <= new_y;
error <= new_error;
end
// sectors 2,3
if (en2 | en3) begin
dot_x <= new_x;
dot_y <= dot_y + 1 ;
error <= new_error;
end
// sector 4
if (en4) begin
if (error <= dx ) begin
dot_x <= dot_x - 1;
error <= new_error;
end
else if (x == screen_width) begin
x_st <= dot_x;
if (y + 1 == y1 )
x_end <= x1;
else
x_end <= x_st;
error <= error - dx ;
end
end
end
always @(posedge clk)
if (strobe_x) line_out <= (x == dot_x) & (y == dot_y);
Для отображения линий в диапазоне 180⁰-360⁰ достаточно поменять местами начало и конец отрезка и использовать алгоритм. приведенный выше. Код замены приводить не буду, дабы не засорять заметку.
Теперь мы можем рисовать линии в любом направлении, можем нарисовать любую фигуру. например пирамиду.
В место заключения:
Приведенная реализация алгоритма просто демонстрация возможности и безусловно может быть улучшена.
Простые алгоритмы, типа алгоритма Брезенхэма прекрасно подходят для обучения/ конкурсных заданий, так как могут дать неожиданные ограничения при реализации на FPGA.
Я хотел бы поблагодарить организаторов кейс-чемпионат «Код успеха» за проведение мероприятия, за интересные задачи. Надеюсь на повторение.
PS: За рамками заметки остались некоторые технические детали, если есть интерес то код модуля можно взять в моем репозитории .