Как использовать алгоритм рисования линии Брешенема с смещением подпикселя?

Question

Bresenham's line drawing algorithm хорошо известен и довольно прост в реализации.

Хотя существуют более продвинутые способы рисования антиайлированных линий, Im заинтересован в написании функции, которая рисует одну ширину пикселя без сглаженной линии, основанной на координатах с плавающей запятой.

Это означает, что в то время как первый и последний пиксели будут оставаться неизменными, пиксели между ними будут иметь смещение, основанное на позиции субпикселя обоих конечных точек.

В принципе, это не должно быть сложным, поскольку я предполагаю, что он может использовать смещения субпикселей для вычисления начального значения error, используемого при построении линии, а все остальные части алгоритма остаются теми же ,

Нет субпиксель компенсировали:

X### 
    ###X 

Предполагая правильную точку стороны, имеет место субпиксельное близко к вершине, линия может выглядеть следующим образом:

С субпиксельное смещение, например:

X###### 
     X 

Есть ли опробованный метод & true для рисования линии, учитывающей подпиксельные координаты?

---

Примечание:

• Это кажется общей операции, я видел OpenGL драйверов принимать это во внимание, например - с помощью GL_LINE, хотя из быстрого поиска я не нашел никаких ответов онлайн - возможно, используются неправильные условия поиска?
• На первый взгляд этот вопрос выглядит как дубликат:
  Precise subpixel line drawing algorithm (rasterization algorithm)
  Однако это вопрос о том, как рисовать широкую линию, это спрашивает о смещении одной пиксельной строки.
• Если нет стандартного метода, я постараюсь написать это для публикации в качестве ответа.

Answer 1

Давайте предположим, что вы хотите, чтобы нарисовать линию от P1 = (x1, y1) до P2 = (x2, y2), где все числа с плавающей точкой пиксельные координаты.

1. Вычислить истинные координаты в пикселях P1 и P2 и покрасить их: P* = (round(x), round(y)).

2. Если abs(x1* - x2*) <= 1 && abs(y1* - y2*) <= 1, то вы готовы.

3. Определите, является ли это горизонтальной (истинной) или вертикальной линией (false): abs(x1 - x2) >= abs(y1 - y2).

4. Если это горизонтальная линия и x1 > x2 или, если это является вертикальной линии и y1 > y2: своп P1 с P2 (а также P1* с P2*).

5. Если это горизонтальная линии вы можете получить у-координату для всех х-координат между x1* и x2* со следующей формулой:

   y(x) = round(y1 + (x - x1)/(x2 - x1) * (y2 - y1)) 
   

   Если у вас есть вертикальной линия вы можете получить координаты х для всех у-координат между y1* и y2* с этой формулой:

   x(y) = round(x1 + (y - y1)/(y2 - y1) * (x2 - x1)) 
   

Here is a demo вы можете играть с, вы можете попробовать различные точки на линии 12.

Answer 2

Только что столкнулся с той же проблемой, я могу подтвердить, что это возможно, как вы ожидали.

Во-первых, вернуться к простейшей форме алгоритма: (игнорируемых фракции, они исчезнут позже)

x = x0 
y = y0 
dx = x1 - x0 
dy = y1 - y0 
error = -0.5 
while x < x1: 
    if error > 0: 
     y += 1 
     error -= 1 
    paint(x, y) 
    x += 1 
    error += dy/dx 

Это означает, что для целыми координатами, мы начинаем половину пикселя над границей пикселя (error = -0.5), и для каждого пикселя мы продвигаемся в x, мы увеличиваем идеальную координату y (и, следовательно, ток error) на dy/dx.

Во-первых, давайте посмотрим, что произойдет, если мы перестанем принуждая x0, y0, x1 и y1 быть целыми числами: (это также будет предполагать, что вместо использования пиксельных центров, координаты относительно верхней левой части каждого пикселя, так как как только вы поддерживаете позиции Субпиксельных вы можете просто добавить половину ширину пикселя к й и у, чтобы вернуться к пиксельному центру логике)

x = x0 
y = y0 
dx = x1 - x0 
dy = y1 - y0 
error = (0.5 - (x0 % 1)) * dy/dx + (y0 % 1) - 1 
while x < x1: 
    if error > 0: 
     y += 1 
     error -= 1 
    paint(x, y) 
    x += 1 
    error += dy/dx 

Единственного изменение был расчетом начальной ошибки. Новое значение происходит от простого триггера для вычисления координаты y, когда x находится в центре пикселя. Стоит отметить, что вы можете использовать ту же самую идею, чтобы скопировать начальную позицию линии в пределах некоторой границы, что является еще одной проблемой, с которой вам, вероятно, придется столкнуться, когда вы хотите начать оптимизацию.

Теперь нам просто нужно преобразовать это в арифметику с целым числом. Нам понадобится фиксированный множитель для дробных входов (scale), и деления можно обработать путем их умножения, как это делает стандартный алгоритм.

# assumes x0, y0, x1 and y1 are pre-multiplied by scale 
x = x0 
y = y0 
dx = x1 - x0 
dy = y1 - y0 
error = (scale - 2 * (x0 % scale)) * dy + 2 * (y0 % scale) * dx - 2 * dx * scale 
while x < x1: 
    if error > 0: 
     y += scale 
     error -= 2 * dx * scale 
    paint(x/scale, y/scale) 
    x += scale 
    error += 2 * dy * scale 

Обратите внимание, что x, y, dx и dy сохранить тот же коэффициент масштабирования в качестве входных переменных (scale), тогда как error имеет более сложный коэффициент масштабирования: 2 * dx * scale. Это позволяет ему поглощать деление и фракцию в своей первоначальной формулировке, но означает, что мы должны применять один и тот же масштаб везде, где мы его используем.

Очевидно, что здесь есть много возможностей для оптимизации, но это основной алгоритм. Если предположить, масштаб сила двоих детей (2^n), мы можем начать, чтобы сделать вещи немного более эффективным:

dx = x1 - x0 
dy = y1 - y0 
mask = (1 << n) - 1 
error = (2 * (y0 & mask) - (2 << n)) * dx - (2 * (x0 & mask) - (1 << n)) * dy 
x = x0 >> n 
y = y0 >> n 
while x < (x1 >> n): 
    if error > 0: 
     y += 1 
     error -= 2 * dx << n 
    paint(x, y) 
    x += 1 
    error += 2 * dy << n 

Как и в оригинале, это работает только в (х> = у, х > 0, y> = 0) октант. Обычные правила применяются для его распространения во всех случаях, но обратите внимание, что есть несколько дополнительных gotchyas из-за того, что координаты больше не центрируются в пикселе (т. Е. Отражения становятся более сложными).

Вам также необходимо следить за целыми переполнениями: error имеет в два раза точность входных переменных и диапазон до удвоенной длины строки. Планируйте свои входы, точность и переменные типы соответственно!