Zadanie 2: Rysowanie linii

Data ogłoszenia: 10.11.2020

Termin oddania: 08.12.2020

Szablon rozwiązania i testy: 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)