Мы vkontakte.ru
Друзья
Словарь синонимов русского языка
Алгоритм DDA-линии
Прим. Название DDA расшифровывается как Digital Differential Analyzer (цифровой дифференциальный анализатор). Так назывались вычислительные устройства, в т.ч. применявшиеся для генерации векторов. Более подробно можно посмотреть по ссылке: Цифровой дифференциальный анализатор - Яндекс.Словари.
Несмотря на то, что сейчас этот алгоритм практически не применяется, он позволяет понять сложности, которые встречаются при растеризации отрезка и способы их решения.
На вход алгоритму подаются координаты точек p1(x1, y1) и p2(x2, y2). Причем координаты точек заданы в вещественном формате.
#define roundf(x) floor(x +
void line_DDA(HDC hdc, float x1, float y1, float x2, float y2)
{
// (1) Целочисленные значения координат начала и конца отрезка,
// округленные до ближайшего целого
int iX1 = roundf(x1);
int iY1 = roundf(y1);
int iX2 = roundf(x2);
int iY2 = roundf(y2);
// (2) Длина и высота линии
int deltaX = abs(iX1 - iX2);
int deltaY = abs(iY1 - iY2);
// (3) Считаем минимальное количество итераций, необходимое
// для отрисовки отрезка. Выбирая максимум из длины и высоты
// линии, обеспечиваем связность линии
int length = max(deltaX, deltaY);
// особый случай, на экране
закрашивается ровно один пиксел
if (length ==
0)
{
SetPixel(hdc, iX1, iY1, 0);
return;
}
// (4) Вычисляем приращения на каждом шаге по осям абсцисс
и ординат
double dX = (x2 -
x1) / length;
double dY
= (y2 - y1) / length;
// (5) Начальные
значения
double x = x1;
double y = y1;
// Основной цикл
length++;
while
(length--)
{
x += dX;
y += dY;
SetPixel(hdc, roundf(x), roundf(y),
0);
}
}
Прим. Выше приведен классический алгоритм DDA-линии без изменений.
Приведенный
алгоритм достаточно прост, но все же приведем краткие комментарии.
На первой стадии (1) вычисляются целочисленные координаты
концов отрезков. При этом из четырех возможных пикселов-кандидатов выбирается
ближайший. Это позволяет несколько повысить точность растеризации.
На (3)-ей стадии берется максимум из высоты и длины
отрезка. Тем самым получается минимальной количество итерации для растеризации.
Действительно, взяв меньшее количество, шаг по одной из осей будет больше
единицы, т.е. нарушится связность.
При этом на шаге (4) получаем одно из значение dX или dY примерно (в силу округления) равным единице, а
другое меньше или равным единице.
Целочисленный алгоритм DDA-линии
Модифицированный алгоритм выглядит следующим образом:
#include "fixed.h"
#define roundf(x) floor(x +
void line_DDA_fixed(HDC hdc, float x1, float y1, float x2, float y2)
{
// (1) Целочисленные значения координат начала и конца отрезка,
// округленные до ближайшего целого
int iX1 = roundf(x1);
int iY1 = roundf(y1);
int iX2 = roundf(x2);
int iY2 = roundf(y2);
// (2) Длина и высота линии
int deltaX = abs(iX1 - iX2);
int deltaY = abs(iY1 - iY2);
// (3) Считаем минимальное количество итераций, необходимое
// для отрисовки отрезка. Выбирая максимум из длины и высоты
// линии, обеспечиваем связность линии
int length = max(deltaX, deltaY);
// особый случай, на экране закрашивается ровно один пиксел
if (length == 0)
{
SetPixel(hdc, iX1, iY1, 0);
return;
}
// (4) Вычисляем приращения на каждом шаге по осям абсцисс и ординат
fixed dX = frac_to_fixed(x2 - x1, length);
fixed dY = frac_to_fixed(y2 - y1, length);
// (5) Начальные значения
fixed x = float_to_fixed(x1);
fixed y = float_to_fixed(y1);
// Основной цикл
length++;
while (length--)
{
SetPixel(hdc, round_fixed(x), round_fixed(y), 0);
x += dX;
y += dY;
}
}