Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Небольшой рассказ о том, как впихнуть невпихуемое и отобразить в реальном времени трехмерную графику при помощи контроллера, у которого недостаточно ни скорости, ни памяти для этого.
В далеком 2017 году (судя по дате модификации файла) решил перейти я с контроллеров AVR на более мощные STM32. Естественно, первым контроллером был выбран широко распиаренный F103. Не менее естественно, что использование готовых отладочных плат было отвергнуто в пользу изготовления своей с нуля согласно своим требованиям. Как ни странно, обошлось почти без косяков (разве что UART1 стоило бы вывести на нормальный разъем, а не костылить на проводках).
По сравнению с AVR характеристики камня довольно приличные: 72 МГц тактовой (на практике можно разогнать до 100 МГц, а то и больше, но только на свой страх и риск!), 20 кБ оперативки и 64 кБ флеша. Плюс тонна периферии, при использовании которой главная проблема — не испугаться этого изобилия и осознать, что для запуска не нужно лопатить все десять регистров, достаточно выставить три бита в нужных. По крайней мере до тех пор, пока не захотите странного.
Когда прошла первая эйфория от обладания такой мощью, возникло желание прощупать ее пределы. В качестве эффектного примера я выбрал расчет трехмерной графики со всеми этими матрицами, освещением, полигональными моделями и Z-буфером с выводом на дисплей 320х240 на контроллере ili9341. Две самые очевидные проблемы, которые предстоит решить — скорость и объем. Размер экрана 320х240 при 16 битах на цвет дает 150 кБ на один кадр. А всего оперативки у нас всего 20 кБ… И эти 150 кБ надо передавать на дисплей хотя бы 10 раз в секунду, то есть скорость обмена должна составлять хотя бы 1.5 МБ/с или 12 Мб/с, что уже выглядит существенной нагрузкой на ядро. К счастью, в данном контроллере присутствует модуль ПДП (прямой доступ к памяти, он же Direct Memory Access, DMA), который позволяет не нагружать ядро операциями переливания из пустого в порожнее. То есть можно подготовить буфер, сказать модулю «вот тебе буфер данных, работай!», а в это время готовить данные для следующей передачи. А если учесть способность дисплея принимать данные потоком, вырисовывается следующий алгоритм: выделяется передний буфер, из которого DMA передает данные на дисплей, задний буфер, в который происходит рендеринг, и Z-буфер, используемый для отсечения по глубине. Буферы представляют собой одну строку (или столбец, неважно) дисплея. И вот вместо 150 кБ нам требуется всего 1920 байт (320 пикселей на строку * 3 буфера * 2 байта на точку), что отлично помещается в память. Второй хак основан на том, что расчет матриц преобразования и координат вершин нельзя проводить для каждой строки, иначе изображение будет искажаться самыми причудливыми способами, да и по скорости это невыгодно. Вместо этого «внешние» расчеты, то есть перемножение матриц трансформации и их применение к вершинам пересчитываются на каждом кадре, после чего преобразуются в промежуточное представление, которое оптимизировано для рендеринга в картинку 320х1.
Из хулиганских соображений снаружи библиотека будет напоминать OpenGL. Как и в оригинальной OpenGL отрисовка начинается с формирования матрицы преобразования — очистка glLoadIdentity() делает текущую матрицу единичной, потом набор преобразований glRotateXY(...), glTranslate(…), каждое из которых умножается на текущую матрицу. Поскольку эти расчеты будут проводиться только один раз за кадр, особых требований к скорости нет, можно обойтись простыми float, без извращений с числами с фиксированной точкой. Сама матрица представляет собой массив float[4][4], отображенный на одномерный массив float[16] — вообще-то этот способ обычно применяется для динамических массивов, но и из статических можно извлечь немного выгоды. Еще один стандартный хак: вместо постоянного вычисления синусов и косинусов, которых в матрицах поворота немало, посчитаем их заранее и запишем в табличку. Для этого поделим полный круг на 256 частей, вычислим значение синуса для каждой и свалим его в массив sin_table[]. Ну а получить из синуса косинус сможет любой, кто учился в школе. Стоит отметить, что функции поворота принимают угол не в радианах, а в долях от полного оборота, после приведения к диапазону [0… 255]. Впрочем, реализованы и «честные» функции, выполняющие преобразование из угла в доли под капотом.
Когда матрица готова, можно приступить к отрисовке примитивов. Вообще, в трехмерной графике есть три типа примитивов — точка, линия и треугольник. Но если нас интересуют полигональные модели, внимание следует уделить только треугольнику. Его «отрисовка» происходит в функции glDrawTriangle() или glDrawTriangleV(). Слово «отрисовка» поставлено в кавычки потому что никакой отрисовки на данном этапе не происходит. Мы всего лишь умножаем все точки примитива на матрицу трансформации, после чего выковыриваем из них аналитические формулы ребер y = ky*x + by, которые позволяют найти пересечения всех трех ребер треугольника с текущей выводимой строкой. Одну из них отбросим, поскольку она лежит не на отрезке между вершин, а на его продолжении. То есть для отрисовки кадра нужно всего лишь пройти по всем строкам и для каждой закрасить область между точками пересечения. Но если применить этот алгоритм «в лоб», каждый примитив будет перекрывать те, что были нарисованы раньше. Нам же нужно учитывать Z-координату (глубину), чтобы треугольники пересекались красиво. Вместо простого вывода точки за точкой будем считать ее Z-координату и по сравнению с Z-координатой, хранимой в буфере глубины, либо выводить (обновляя Z-буфер), либо игнорировать. А для расчета Z-координаты каждой точки интересующей нас строки воспользуемся той же формулой прямой линии z = kz*y + bz, вычисленной по тем самым двум точкам пересечения с ребрами. В результате объект «полуфабрикатного» треугольника struct glTriangle состоит из трех X-координат вершин (хранить Y и Z-координаты смысла нет, они будут вычисляться) и k, b коэффициентов прямых, ну и цвет до кучи. Вот здесь, в отличие от расчета матриц преобразования, скорость критична, поэтому уже используем числа с фиксированной точкой. Причем если для слагаемого b достаточно той же точности, что для координат (2 байта), то точность множителя k чем больше, тем лучше, поэтому берем 4 байта. Но не float, поскольку работа с целыми числами все равно быстрее, даже при одинаковом размере.
Итак, вызвав кучу glDrawTriangle() мы подготовили массив полуфабрикатных треугольников. В моей реализации треугольники выводятся по одному явными вызовами функции. На самом деле было бы логично завести массив треугольников с адресами вершин, но здесь я решил не усложнять. Все равно функция отрисовки пишется роботами, а им без разницы, заполнять ли константный массив или писать триста одинаковых вызовов. Пришло время перевести полуфабрикаты треугольников в красивую картинку на экране. Для этого вызывается функция glSwapBuffers(). Как и было описано выше, она проходит по строкам дисплея, ищет для каждой точки пересечения со всеми треугольниками и рисует отрезки в соответствии с фильтрацией по глубине. После рендеринга каждой строки нужно эту строку отправить на дисплей. Для этого запускается DMA, которому указывается адрес строки и ее размер. А пока DMA работает, можно переключиться на другой буфер и рендерить уже следующую строку. Главное не забыть дождаться окончания передачи если вдруг закончили отрисовку раньше. Для визуализации соотношения скоростей я добавил включение красного светодиода после окончания рендеринга и выключение после завершения ожидания DMA. Получается что-то вроде ШИМ, который регулирует яркость в зависимости от времени ожидания. Теоретически вместо «тупого» ожидания можно было бы использовать прерывания DMA, но тогда я не умел ими пользоваться, да и алгоритм существенно бы усложнился. Для демонстрационной программы это излишне.
Результатом описанных выше процедур явилась вращающаяся картинка трех пересекающихся плоскостей разных цветов, причем с довольно приличной скоростью: яркость красного светодиода довольно велика, что говорит о большом запасе по производительности ядра.
Что ж, если ядро простаивает, надо его нагрузить. А нагружать его будем более качественными моделями. Правда, не стоит забывать, что память все-таки сильно ограничена, так что слишком много полигонов контроллер не потянет физически. Простейший расчет показал, что после вычитания памяти на буфер строки и тому подобное, осталось место на 378 треугольников. Как показала практика, под этот размер отлично подходят модели из старой, но интересной игры Gothic. Собственно, оттуда были выдернуты модельки шныга и кровавой мухи (а уже при написании этой статьи и мракориса, красующегося на КДПВ), после чего у контроллера кончилась флеш-память. Но игровые модельки не предназначены для использования микроконтроллером.
Скажем, они содержат анимацию, текстуры и тому подобное, что нам не пригодится, да и не поместится в память. К счастью, blender позволяет не только пересохранить их в *.obj, более поддающийся парсингу, но и уменьшить количество полигонов если нужно. Дальше при помощи простенькой самописной программы obj2arr *.obj файлы разбираются на координаты, из которых впоследствии формируется *.h файл для непосредственного включения в прошивку.
Но пока что модельки выглядят просто как одноцветные фигурные кляксы. На тестовой модели это нас не волновало, поскольку все грани были раскрашены в свои цвета, но не прописывать же цвета каждому полигону модельки. Нет, можно, конечно и муху раскрасить в рандомные цвета, но смотреться это будет довольно вырвиглазно, я проверял. Особенно когда цвета еще и меняются на каждом кадре… Вместо этого применим еще капельку векторной магии и добавим освещение.
Расчет освещения в его примитивном варианте заключается в расчете скалярного произведения нормали и направления на источник света с последующим умножением на «родной» цвет грани.
Моделек у нас теперь три — две из игры и одна тестовая, с которой начинали. Для их переключения воспользуемся одной из двух кнопок, распаянных на плате. Заодно можно добавить контроль загруженности процессора. Один контроль у нас уже есть — красный светодиод, связанный с временем ожидания DMA. А вторым, зеленым, светодиодом, будем мигать при каждом обновлении кадра — так мы сможем оценить частоту кадров. Для невооруженного глаза она составила что-то около 15 fps.
В общем-то, я полученным результатом удовлетворен: приятно реализовать что-то, что принципиально невозможно решить в лоб. Конечно, тут еще есть куда оптимизировать и улучшать, но смысла в этом немного. Объективно контроллер для трехмерной графики слаб, причем речь даже не про скорость, а скорее про оперативную память. Впрочем, как и любой образец демосцены, этот проект ценен не результатом, а процессом.
Если вдруг кому-то будет интересно, исходный код доступен тут.
