Библиотека
Превращаем точки в линии
Когда научился ставить точки - самое время перейти к линиям. Линия состоит из точек, так ведь? Всё должно быть просто. Когда я приступал к этому, я даже не представлял себе, сколько сложности кроется за простой операцией рисования линии из отдельных точек.
Алгоритм Брезенхэма
Первое же гугление привело меня к описанию алгоритма Брезенхэма в Википедии. Я намеренно дал ссылку на английский раздел, там приведены более подходящие примеры программ. Они написаны на языке напоминающем Си, но это не Си. Думаю, это просто попытка дать код на этаком мета-языке программирования, чтобы его потом было просто перевести в любой другой язык программирования. Перевести наиболее понравившийся мне пример в Си и правда было несложно.
void plotBresenhamLine( UINT x0, UINT y0, UINT x1, UINT y1, BMP* bmp, int color)
{
int dx, sx, dy, sy, err, e2;
dx = abs(x1-x0);
sx = x0<x1 ? 1 : -1;
dy = -abs(y1-y0);
sy = y0<y1 ? 1 : -1;
err = dx+dy; /* error value e_xy */
while(x0 != x1 && y0 != y1) /* loop */
{
e2 = 2*err;
if (e2 >= dy) /* e_xy+e_x > 0 */
{
err += dy;
x0 += sx;
}
if (e2 <= dx) /* e_xy+e_y < 0 */
{
err += dx;
y0 += sy;
}
BMP_SetPixelIndex( bmp, x0, y0, color );
}
}
Пример немного модифицирован. Раница во вкусе. К сожалению, у алгоритма Брезенхэма оказалась неприятная особенность. Он отлично справляется с наклонными прямыми. Но чем ближе прямая к вертикали или горизонтали - тем хуже алгоритм работает. Наконец, он вовсе не умеет рисовать вертикальные и горизонтальные линии. Это можно было бы отрабатывать как особые случаи и чертить горизонтальные и вертикальные прямые простейшим циклом, но что делать с линиями, которые только приближаются к горизонтальным или вертикальным? Вот как это выглядит. Не обращайте внимания на психоделический фон, я эксперементировал с палитрой.
Хорошо видно, что чем ближе линия к горизонтальной, тем большая её часть не прорисовывается. К счастью, есть несколько реализаций алгоритма, плюс модификация Мёрфи для алгорима Брезенхэма, алгоритм DDA-линии и ещё несколько разных алгоритмов. Я попробую разные на различных примерах, сравню их скорости и выясню, что же имеет смысл использовать. Хотя, скорость меня волнует очень мало, если честно. Идеально быстрые алгоритмы рисования линий - это те, которые выполняются графическим ускорителем.
Есть довольно полезные статьи про алгоритм Брезенхэма:
- Алгоритм Брезенхема на CodeNet. Очень лаконичное описание, но приведена реализация алгоритма отличающаяся от большинства остальных.
- Алгоритм Брезенхема для рисования наклонных отрезков. Одна из немногих публикаций, где с самого начала пишут про ключевую особенность алгоритма. В Википедии про неё, например, вообще ничего не пишут.
- Алгоритм DDA-линии. Другой алгоритм рисования линий. Я попробую его следующим.
Ближайшие планы - написать программу интенсивно использующую линии, чтобы сравнить по времени исполнения разные реализации алгоритма. И сделать эти разные реализации, разумеется.
