Могу ли я легко пропускать пиксели в линейном алгоритме Брешенема?

Question

У меня есть программа, которая использует Bresenham's line algorithm для сканирования пикселей в строке. Это чтение пикселей, а не их запись, и в моем конкретном случае их чтение является дорогостоящим.

Однако я могу определить, что некоторые промежутки пикселей не нужно читать. Это выглядит примерно так:

Normal scan of all pixels: 

*start 
\ 
    \ 
    \ 
    \ 
    \ 
     *end 

Scan without reading all pixels: 

*start 
\ 
    \ 
     - At this point I know I can skip (for example) the next 100 pixels 
      in the loop. Crucially, I can't know this until I reach the gap. 
    \ 
     *end 

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

Однако, могу ли я каким-либо образом изменить петлю, чтобы просто перепрыгнуть прямо вперед 100 пикселей внутри цикла, вычислив непосредственно требуемые значения на 100 шагов вперед в линейном алгоритме?

Answer 1

Bresenhams middlepoint алгоритм вычисляет 'расстояние' точки от теоретической линии, идущей из (Ax, Ay) -> (Bx, By) путем суммирования цифровые различия delta_x = (по-ау), delta_y = (ах -bx).

Таким образом, если вы хотите пропустить 7 пикселей, нужно добавить acc + = 7 * delta_x; то, делясь на delta_y, можно проверить, сколько пикселей должно было быть перемещено в направлении y и взятие остатка accum = accum% delta_y должно быть в состоянии продолжить в правильном положении.

Хорошая вещь в том, что алгоритм возникла из необходимости избежать разделения ...

Отказ от ответственности: все, что сказал, возможно, должны быть скорректированы на половину дельты.

Answer 2

Ваш главный цикл выглядит по существу что-то вроде:

while (cnt > 0) // cnt is 1 + the biggest of abs(x2-x1) and abs(y2-y1) 
    { 
    ReadOrWritePixel(x, y); 

    k += n; // n is the smallest of abs(x2-x1) and abs(y2-y1) 
    if (k < m) // m is the biggest of abs(x2-x1) and abs(y2-y1) 
    { 
     // continuing a horizontal/vertical segment 
     x += dx2; // dx2 = sgn(x2-x1) or 0 
     y += dy2; // dy2 = sgn(y2-y1) or 0 
    } 
    else 
    { 
     // beginning a new horizontal/vertical segment 
     k -= m; 
     x += dx1; // dx1 = sgn(x2-x1) 
     y += dy1; // dy1 = sgn(y2-y1) 
    } 

    cnt--; 
    } 

Таким образом, пропуская некоторые Q пикселей эквивалентно следующих регулировок (если я не сделал ошибку где-то):

• CNT _новый = cnt _старый - q
• k _новый = (k _{ol д} + п * д)% м
• х _новый = х _старый + ((к _старый + п * д)/м) * dx1 + (Q - ((к _старый + п * д)/м)) * дх2
• у _новый = у _старый + ((к _старый + п * д)/м) * dy1 + (Q - ((к _старый + п * q)/m)) * dy2

Заметим, что/и% являются целыми делениями и модульными операторами.