.. _z2-bresenham:

==========================
Zadanie 2: Rysowanie linii
==========================

Data ogłoszenia: 10.11.2020

Termin oddania: 08.12.2020

Szablon rozwiązania i testy: :download:`bresenham_template.py`

Napisać moduł implementujący algorytm rysowania linii Bresenhama.

Moduł powinien mieć dwa interfejsy: interfejs wejściowy, na którym
odbiera współrzędne końców linii, oraz interfejs wyjściowy, na którym
wysyła współrzędne pikseli należących do linii oraz informację
o zakończeniu rysowania linii.

Moduł powinien być parametryzowany parametrem ``width``, określającym
rozmiar współrzędnych pikseli w bitach.

Interfejs wejściowy ma następujące sygnały:

- ``in_valid`` (wejście): oznacza, że dostępny jest pakiet danych
  wejściowych dla modułu
- ``in_ready`` (wyjście): oznacza, że moduł jest gotowy na przyjęcie
  pakietu danych wejściowych
- gdy oba powyższe sygnały są jednocześnie aktywne, następuje transfer
  pakietu wejściowego na następujących sygnałach:

  - ``in_type`` (wejście): typ pakietu, jeden z:

    - ``FIRST``: ustawia współrzędne pierwszego końca linii; powinien
      być wysłany przed wysłaniem pierwszego pakietu ``NEXT``
    - ``NEXT``: podaje współrzędne drugiego końca linii i rysuje linię,
      powodując emisję odpowiednich pakietów na interfejsie wyjściowym;
      pierwszy koniec linii był podany w poprzednim pakiecie wejściowym
      — w szczególności, można wysłać kilka poleceń ``NEXT`` po sobie,
      by narysować łamaną

  - ``in_x`` (wejście, ``width``-bitowe): współrzędna X
  - ``in_y`` (wejście, ``width``-bitowe): współrzędna Y

Interfejs wyjściowy ma następujące sygnały:

- ``out_valid`` (wyjście): oznacza, że moduł ma gotowy pakiet danych
  wyjściowych
- ``out_ready`` (wejście): oznacza, że odbiorca danych wyjściowych
  jest gotowy na przyjącie pakietu
- gdy oba powyższe sygnały są jednocześnie aktywne, następuje transfer
  pakietu wyjściowego na następujących sygnałach:

  - ``out_type`` (wejście): typ pakietu, jeden z:

    - ``PIXEL``: współrzędne jednego z pikseli należących do linii
    - ``LINE_END``: informacja, że rysowanie linii (w odpowiedzi na
      polecenie ``NEXT``) zostało zakończone

  - ``out_x`` (wyjście, ``width``-bitowe): współrzędna X piksela (nieużywane dla pakietu ``LINE_END``)
  - ``out_y`` (wyjście, ``width``-bitowe): współrzędna Y piksela (nieużywane dla pakietu ``LINE_END``)

Moduł powinien implementować następujący pseudokod::

    while True:
        (type, x, y) = in.recv()
        if type == FIRST:
            cur_x = x
            cur_y = y
        else: # type == NEXT
            dst_x = x
            dst_y = y
            # Algorytm Bresenhama.
            dx = abs(cur_x - dst_x)
            dy = abs(cur_y - dst_y)
            sx = 1 if dst_x > cur_x else -1
            sy = 1 if dst_y > cur_y else -1
            err = dx - dy
            while (cur_x, cur_y) != (dst_x, dst_y):
                out.send(PIXEL, cur_x, cur_y)
                e2 = err * 2
                if e2 >= -dy:
                    err -= dy
                    cur_x += sx
                if e2 <= dx:
                    err += dx
                    cur_y += sy
            out.send(LINE_END)