Продолжая тему вращения, перейдём к битмапам. Как их вращать, не привлекая внимания санита прибегая к всяким движкам и OpenGL?
Для начала очертим грубый алгоритм:
- Битмап это матрица, состоящая из пикселов
- Можно взять каждый пиксел и повернуть его координаты вокруг центра вращения, после чего нарисовать по новым координатам
Действительно, если мы знаем, как повернуть точку, то ничего не стоит повернуть и любое множество точек.
Но есть нюанс
Каждая операция поворота 2D-точки это 4 умножения и 2 сложения. При достаточно больших размерах битмапа, например, 256*256, операций получается многовато. Также пикселы по натуре имеют целочисленные координаты, и в результате поворота между ними будут образовываться разрывы. Эту проблему мы решим позже.
Будем отталкиваться от тех возможностей оптимизации, которые предоставляет сам битмап.
Вспомним, что битмап состоит из горизонтальных линий (строк). Имея координаты начала и конца линии, мы можем повернуть их, и получить новую линию, которая уже не горизонтальна. Далее можно нарисовать эту линию попиксельно, используя для цветов пикселов значения из битмапа (в битмапе мы по-прежнему будем двигаться горизонтально, так как он не поворачивается, поворачивается только его отображение).
Алгоритм Брезенхема для рисования линий
Он подробно описан здесь:
Я сделаю его адаптацию на C+SDL2:
Здесь рисуется линия с заданным цветом. Теперь добавим рисование не одним цветом, а данными из битмапа. Так как битмап имеет определённую ширину, она передаётся в виде параметра img_w.
Вместо color в адрес видеобуфера записывается содержимое указателя битмапа *img_data. Дальше нужно сдвинуть указатель img_data на следующий пиксел, однако просто так это сделать нельзя. Например, если ширина битмапа равна 256, в линии первый пиксел должен быть первый из битмапа, второй второй, третий третий, и т.д., а последний должен быть 256-й. Но это сработает только в том случае, если линия по координате x или по координате y содержит 256 пикселов. На деле же из-за поворота она будет содержать меньше чем 256 пикселов по каждому измерению. В линии по алгоритму Брезенхема столько шагов, и столько раздельных позиций пикселов, сколько есть в большей из дистанций (dist) по x или по y.
Если на каждом шаге просто увеличивать указатель битмапа на 1, это приведёт к тому, что получится неестественно растянутое изображение, которое целиком не помещается в линию. Мы должны пропускать какие-то позиции в битмапе, чтобы привести их в соответствие с шагами линии.
Поэтому здесь вводится дополнительный аккумулятор ошибки err_img, к которому каждый раз прибавляется ширина битмапа img_w. И пока этот аккумулятор больше dist, из него вычитается dist, а указатель битмапа двигается дальше, тем самым пропуская некоторые пикселы.
Как работают аккумуляторы ошибок, рассказано в вышеуказанном материале про алгоритм Брезенхема.
Теперь, имея метод рисования текстурированной линии, осталось масштабировать его до рисования всех линий в битмапе.
Можно брать их по очереди и поворачивать, но отметим, что так как все они поворачиваются одинаково, достаточно получить лишь повёрнутые координаты первой линии. А координаты остальных линий получать сдвигом первой.
Сдвиг нетривиален, так как происходит в определённом соотношении и по x, и по y. Здесь мы тоже применим алгоритм Брезенхема.
У битмапа берём координаты трёх точек:
- (x0, y0) – левый верхний угол
- (x1, y1) – правый верхний угол
- (x2, y2) – левый нижний угол
Эти три точки поворачиваем и получаем новые координаты (rx0, ry0), (rx1, ry1) и (rx2, ry2):
Теперь мы можем нарисовать линию (rx0, ry0) – (rx1, ry1) как первую строку битмапа. Чтобы нарисовать вторую и остальные строки, мы сдвигаем координаты этой линии вдоль перпендикулярной ей (rx0, ry0) – (rx2, ry2).
Первоначальные расчёты довольно громоздки, но выполняются один раз перед рисованием.
Здесь мы получили координаты центра вращения cx, cy и получили относительно них координаты (x0, y0), (x1, y1), (x2, y2).
Затем повернули координаты по формуле вращения и получили повёрнутые rx0, ry0 и т.д.
Для линии перпендикуляра (rx0, ry0) – (rx2, ry2), вдоль которой будет происходить смещение, рассчитываются параметры алгоритма Брезенхема:
После чего координаты rx0, ry0, rx1, ry1 возвращаются из относительных обратно в экранные:
И начинаем Брезенхем-движение по перпендикуляру с построчным рисованием:
Обратим внимание, что длина перпендикуляра по любому измерению также меньше высоты битмапа, так что в данном случае мы должны пропускать не просто пикселы битмапа, а целые строки.
Результат:
Работает, но есть артефакты. Они появляются из-за того, что линии, нарисованные с неравномерным сдвигом, не везде прилегают друг к другу плотно. В зависимости от угла поворота может получаться по-разному:
Чтобы быстро решить эту проблему, я просто буду рисовать дополнительный пиксел там, где в алгоритме Брезенхема происходит скачок по x:
На этот раз никаких разрывов нет:
Но можно заметить определённую грубость изображения. Это неудивительно, ведь в ходе рисования мы выбрасывали пикселы из линий и даже целые линии. Такова особенность целочисленных методов, и без дополнительного усложения с этим ничего не сделать.
Но это мы рассмотрим в следующий раз, когда попробуем более продвинутые методы.
В то же время именно такая манера изображения характерна для многих олдскульных игр, так что можно вполне воссоздать их атмосферу.
Полный код программы можно посмотреть здесь:
Компиляция в Windows:
gcc rotate.c -O5 -lSDL2main -lSDL2
Компиляция в Linux:
gcc rotate.c -O5 -LSDL2 -lm