В конце сентября – в начале октября в Барнауле прошел кейс-чемпионат «Код успеха». О чемпионате можно прочитать здесь. Один из кейсов “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
Построение линии в секторе 90⁰-135⁰ выполняется аналогично построению в секторе 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: За рамками заметки остались некоторые технические детали, если есть интерес то код модуля можно взять в моем репозитории .
