Temat: Algorytm obcinania wielokątów

Uff.. znalazłem w końcu trochę (dużo :P) wolnego czasu i zaimplementowałem wspomniany przeze mnie wcześniej algorytm obcinania wielokątów. O ile sam algorytm (Sutherland-Hodgman) nie jest zbyt skomplikowany, to już odpowiednia implementacja w assemblerze nie była zupełnie banalna (chociaż ilościowo kodu nie jest dużo). Implementacja obcina wielokąt do zadanego parametrycznie okna, wykorzystując strategię "dziel i zwyciężaj" - czyli skomplikowany problem dzieli na kilka mniejszych  - w tym wypadku obcinanie następuje dla każdej krawędzi okna osobno. Dzięki takiemu rozwiązaniu można obcinać np. tylko po krawędziach poziomych lub pionowych :). Procedurę clippingu przeniosłem do osobnego pliku, w programie głównym jest tylko kilka zmian w stosunku do procedury rysowania wielokątów wypukłych bez obcinania. Mam pomysł (chyba), jak zmniejszyć dosyć kosztowne czasowo liczenie przecięcia krawędzi z oknem obcinającym (teraz jest między innymi jedno mnożenie i jedno dzielenie), ale zostawiam to sobie na później (tablica nie wchodzi raczej w grę ze względu na jej rozmiar). Jak zwykle komentarze mile widziane :P Myślę, że kolejnym krokiem będzie jakiś obracający się sześcian, a później może obiecany wcześniej glenz :D

Post's attachments

TriangFi.zip 14.49 kb, liczba pobrań: 8 (od 2015-04-05) 

Tylko zalogowani mogą pobierać załączniki.

2

Odp: Algorytm obcinania wielokątów

Super, widzę że sprawy idą w słusznym kierunku. Wprowadziłeś kawał niezłego kodu, jutro siadam do studiowania :)

Ja niestety dopiero dzisiaj miałem okazję znowu siąść do kodu.
Bazuję teraz na ostatnim BT4PC_C. Dodałem nową procedurę BLiTTERa - inicjalizacja i generowanie nowej tablicy leftEdge/rightEdge/leftMask/rightMask oraz nową wersję poly_fill_line bazującą na tej tablicy. Pierwszy etap - generowani tablicy działa poprawnie, niestety drugi - poly_fill_line już nie. Dziś już nie dam rady, ale może jutro wieczorem uda mi się siąść do debuggera i przejść przez poly_fill_line.

Co do clippingu to czy on zawsze jest on potrzebny? Np. dla glenz nie wychodzącego poza ramki ekranu?

Lynx I / Mega ST 1 / 7800 / Portfolio / Lynx II / Jaguar / TT030 / Mega STe / 800 XL / 1040 STe / Falcon030 / 65 XE / 520 STm / SM124 / SC1435
DDD HDD / AT Speed C16 / TF536 / SDrive / PAK68/3 / Lynx Multi Card / LDW Super 2000 / XCA12 / SkunkBoard / CosmosEx / SatanDisk / UltraSatan / USB Floppy Drive Emulator / Eiffel / SIO2PC / Crazy Dots / PAM Net
http://260ste.atari.org

Odp: Algorytm obcinania wielokątów

No ciekawy jestem, co z twojego pomysłu wyjdzie. Clipping oczywiście nie jest zawsze potrzebny, ale biorąc pod uwagę szybkość działania wypełniania warto było się i nad tym problemem pochylić :) - tym bardziej, że pomysłowe użycie pozwoli uzyskać ciekawe "demkowe" efekty :D

4

Odp: Algorytm obcinania wielokątów

Nie miałem czasu zerknąć jeszcze do Twojego clippingu. Mógłbyś ogólnie napisąć jak to wygląda wydajnościowo. Powiedzmy mam jakiś trójkąt ustalonego rozmiaru wystający w połowie za ekran. Ile procentowo czasu zajmie mi clipping a ile samo wypełnianie? Jaki jest narzut dla trójkątów których nie trzeba clippować? (pewnie prawie zerowy, nie?)
PS. ja clipping odpuszczałem na razie sobie z powodów które opisał Cyprian. Bardziej przydaję się on przy renderowaniu całych scen a nie pojedyńczych obiektów. I am not there yet;)

Maciek
--------
Atari 65XE + Ultimate 1MB + Stereo + SIO2SD | Atari 520STE + 4MB + UltraSatan | Atari Falcon 030 + CT60e + 14MB ST + 256MB TT + 68882  + CF + Netusbee | Amiga 500 + 1MB + Gotek | Amiga 600 + 2MB Chip + 8MB Fast + CF

Odp: Algorytm obcinania wielokątów

Trudno określić w procentach, ile czasu będzie zajmował clipping, ale dla każdej krawędzi wykonywane jest kilka porównań i zapis do tablicy krawędzi - więc nie są to wartości porażające. W razie konieczności wyliczenia przecięcia krawędzi z oknem obcinającym dodatkowo wykonywane jest jedno dzielenie, jedno mnożenie, 3 move'y, 3 sub'y i jeden add. Ogólnie nie jest źle - a mam pomysł, jak pozbyć się mnożenia i dzielenia :) (i to bez tablicy). Oczywiście, jeśli okno jest malutkie (albo trójkąt bardzo duży) może zdarzyć się, że obcinanie będzie robione dla każdej krawędzi, czyli 4 razy.

6

Odp: Algorytm obcinania wielokątów

Wczoraj w nocy udało mi się dodać optymalizację w której BLiTTER generuje nową tablicę leftEdge address/rightEdge address/leftMask/rightMask. Skraca ona czas całości o trzy linie skaningowe. Nie jest to powalający wynik, ale nowy kod daje miejsce na dalsze optymalizacje.

.poly_fill_line wygląda teraz tak:

.poly_fill_line:
    movem.w  (A0)+,D0-D3        ; D0 - left; D1 - right; D2 - left mask; D3 - right mask
    movea.l  a5,a4
    lea      logLine(a5),a5     ;next y offset line
    lea      (a4,d0.w),a4       ;add line x offset
    sub.w     d0,d1              ;line width
    
    asr.w    #3,D1
    bgt.s    .multi_words

Kod jest brudny, wieczorem siądę by go oczyścić i jutro wrzucę go na forum.

Lynx I / Mega ST 1 / 7800 / Portfolio / Lynx II / Jaguar / TT030 / Mega STe / 800 XL / 1040 STe / Falcon030 / 65 XE / 520 STm / SM124 / SC1435
DDD HDD / AT Speed C16 / TF536 / SDrive / PAK68/3 / Lynx Multi Card / LDW Super 2000 / XCA12 / SkunkBoard / CosmosEx / SatanDisk / UltraSatan / USB Floppy Drive Emulator / Eiffel / SIO2PC / Crazy Dots / PAM Net
http://260ste.atari.org

Odp: Algorytm obcinania wielokątów

W najbardziej krytycznej czasowo części kodu dużo miejsca na optymalizację już nie było, a zawsze będzie 3 linie mniej :)

8

Odp: Algorytm obcinania wielokątów

mały OT. Tutaj nowość od konkurencji :)
https://youtu.be/ZQ3-nnoXGng?t=49
Sprawdziłem w debuggerze winuae no i jeden obiekt generowany jest w cztery ramki

Lynx I / Mega ST 1 / 7800 / Portfolio / Lynx II / Jaguar / TT030 / Mega STe / 800 XL / 1040 STe / Falcon030 / 65 XE / 520 STm / SM124 / SC1435
DDD HDD / AT Speed C16 / TF536 / SDrive / PAK68/3 / Lynx Multi Card / LDW Super 2000 / XCA12 / SkunkBoard / CosmosEx / SatanDisk / UltraSatan / USB Floppy Drive Emulator / Eiffel / SIO2PC / Crazy Dots / PAM Net
http://260ste.atari.org

Odp: Algorytm obcinania wielokątów

Ładne. :D , ale te vectory na początku szacuję na jakieś 2 ramki przy naszych prockach :P

Odp: Algorytm obcinania wielokątów

Aaa właśnie. Czy "Takeover" (grupa Lamers) nie jest między innymi autorstwa naszego szanownego kolegi MKMa? :)

11

Odp: Algorytm obcinania wielokątów

jest jest ;)

Atari Falcon 030 14MB+SD16GB; Atari TT 030 4MB ST-RAM, 64 MB TT-RAM; Atari 1040 STFM; Atari 1040 STE 4MB+NetUsbee+UltraSatan; Commodore 64+1541-II+XE1541; Atari 65 XE+CA-2001+Ultimate 1MB+Side2;  P166MMX+GUS.

12

Odp: Algorytm obcinania wielokątów

Potwierdzam:)

Maciek
--------
Atari 65XE + Ultimate 1MB + Stereo + SIO2SD | Atari 520STE + 4MB + UltraSatan | Atari Falcon 030 + CT60e + 14MB ST + 256MB TT + 68882  + CF + Netusbee | Amiga 500 + 1MB + Gotek | Amiga 600 + 2MB Chip + 8MB Fast + CF

13

Odp: Algorytm obcinania wielokątów

Tomasz Wachowiak napisał/a:

W najbardziej krytycznej czasowo części kodu dużo miejsca na optymalizację już nie było, a zawsze będzie 3 linie mniej :)

ok, na dzień dzisiejszy mamy 10 linii mniej dla tej figury (lewa strona BT4PC_C, prawa kod zoptymalizowany):
http://www.atari.org.pl/forum/misc.php?action=pun_attachment&item=2419

Figura ta wykorzystuje wyłącznie "multi_words", więc nie wiem jak optymalizacja wygląda w przypadku krótkich wektorów.

Widzę jeszcze miejsce na optymalizację, np. aktualnie generowanie nowej tablicy leftEdge/rightEdge/leftMask/rightMask wymaga inicjalizacji dla każdego wielokąta osobno. gdyż odbywa się ono pomiędzy "compute_triangle_dx" a "fill_triangle".

Można by spróbować wykonać tylko jedną inicjalizację dla wszystkich wielokątów. Czyli wykonać "compute_triangle_dx" dla wszystkich wielokątów, potem tylko jedna inicjalizacja BLiTTERa, a następnie dla każdego wielokąta generowanie nowej tablicy leftEdge/rightEdge/leftMask/rightMask. No i na koniec "fill_triangle" dla każdego wielokąta.

Ostatnio edytowany przez Cyprian (2015-04-13 22:58:05)

Post's attachments

BT4PCC.png 648 b, nikt jeszcze nie pobierał tego pliku. 

Tylko zalogowani mogą pobierać załączniki.
Lynx I / Mega ST 1 / 7800 / Portfolio / Lynx II / Jaguar / TT030 / Mega STe / 800 XL / 1040 STe / Falcon030 / 65 XE / 520 STm / SM124 / SC1435
DDD HDD / AT Speed C16 / TF536 / SDrive / PAK68/3 / Lynx Multi Card / LDW Super 2000 / XCA12 / SkunkBoard / CosmosEx / SatanDisk / UltraSatan / USB Floppy Drive Emulator / Eiffel / SIO2PC / Crazy Dots / PAM Net
http://260ste.atari.org

Odp: Algorytm obcinania wielokątów

@Cyprian - Jeszcze trochę, to sobie kod wydrukuję i zacznę się do niego modlić :P
@MKM - fajne pomysły, fajny design - ogólnie gratulacje :)

Odp: Algorytm obcinania wielokątów

Cyprian napisał/a:

Widzę jeszcze miejsce na optymalizację, np. aktualnie generowanie nowej tablicy leftEdge/rightEdge/leftMask/rightMask wymaga inicjalizacji dla każdego wielokąta osobno. gdyż odbywa się ono pomiędzy "compute_triangle_dx" a "fill_triangle".

Można by spróbować wykonać tylko jedną inicjalizację dla wszystkich wielokątów. Czyli wykonać "compute_triangle_dx" dla wszystkich wielokątów, potem tylko jedna inicjalizacja BLiTTERa, a następnie dla każdego wielokąta generowanie nowej tablicy leftEdge/rightEdge/leftMask/rightMask. No i na koniec "fill_triangle" dla każdego wielokąta.

Jak zaczniemy bawić się kostką, to będzie można wspomniane optymalizację do kodu dorzucić :)

Odp: Algorytm obcinania wielokątów

Ha! Po chwili (dłuższej :P) zastanowienia wiem już Cyprian, na czym polega twoja optymalizacja. :) Na razie jawi mi się w dwóch przejściach blittera nad wyliczonymi współrzędnymi. Kusi mnie, żeby zrobić swoją wersję... :P

17

Odp: Algorytm obcinania wielokątów

wrzuć mi na PM maila to wyślę ci "brudnopis"

Lynx I / Mega ST 1 / 7800 / Portfolio / Lynx II / Jaguar / TT030 / Mega STe / 800 XL / 1040 STe / Falcon030 / 65 XE / 520 STm / SM124 / SC1435
DDD HDD / AT Speed C16 / TF536 / SDrive / PAK68/3 / Lynx Multi Card / LDW Super 2000 / XCA12 / SkunkBoard / CosmosEx / SatanDisk / UltraSatan / USB Floppy Drive Emulator / Eiffel / SIO2PC / Crazy Dots / PAM Net
http://260ste.atari.org

Odp: Algorytm obcinania wielokątów

No i mam wersję, która generuje maski/offsety na blitterze. :) Tyle, że u mnie wychodzi... wolniej. :O (z wyliczeń wynika, że powinno być szybciej, a nie jest :( ). I teraz widzę dwa wytłumaczenia: pierwsze bardziej prawdopodobne, że Cyprian zrobił to inaczej, drugie mniej prawdopodobne, że pomylił zrzuty ekranów :P
W każdym razie u mnie generowanie tablicy przebiega w pięciu cyklach (być może Cyprian tutaj lepiej sobie to wymyślił):
1. Generowanie wyANDowanych wartości współrzędnych dla offsetów
2. Generowanie wyANDowanych wartości dla masek
3. Generowanie offsetów
4. i 5. Generowanie masek.
Przy okazji wpadłem na kolejną optymalizację :D (Przy dużych trójkątach zejdzie jakieś 5 scanlinii). Jak wszystko połączę w całość, zamieszczę odpowiedni kod.

19

Odp: Algorytm obcinania wielokątów

Z tego co widzę to wykonujesz pięć kroków, ja cztery.

może jutro się ogarnę i wrzucę mój kod.

Lynx I / Mega ST 1 / 7800 / Portfolio / Lynx II / Jaguar / TT030 / Mega STe / 800 XL / 1040 STe / Falcon030 / 65 XE / 520 STm / SM124 / SC1435
DDD HDD / AT Speed C16 / TF536 / SDrive / PAK68/3 / Lynx Multi Card / LDW Super 2000 / XCA12 / SkunkBoard / CosmosEx / SatanDisk / UltraSatan / USB Floppy Drive Emulator / Eiffel / SIO2PC / Crazy Dots / PAM Net
http://260ste.atari.org

Odp: Algorytm obcinania wielokątów

Jakie kroki wykonujesz? Przed implementacją byłem przekonany, że uda mi się właśnie w 4 krokach wszystko załatwić, ale skew dla offsetów wykonuje się przed maskami i jest dupa - musiałem rozdzielić offsety na 2 przejścia. A może udało ci się maski w jednym przejściu wygenerować?

21

Odp: Algorytm obcinania wielokątów

Co do przebiegów to robię inicjalizację i cztery:
- Inicjalizacja ładuje maski do Halftone.
- Pierwszy przebieg generuje maskę dla lewej strony linii na podstawie leftMask oraz Halftone.
- Drugi przebieg generuje maskę dla prawej strony linii na podstawie rightMask oraz NOT Halftone.
- Trzeci przebieg generuje adres pamięci dla lewej strony linii - (leftMask >>1) AND  $7FF8
- Czwarty przebieg generuje adres pamięci dla prawej strony linii - (rightMask >>1) AND  $7FF8

Dzięki temu mogłem skrócić "poly_fill_line" do:

    .poly_fill_line:
                    movem.w    (A0)+,D0-D3        ; D0 - left; D1 - right; D2 - left mask; D3 - right mask
                    movea.l    a5,a4
                    lea        logLine(a5),a5        ;next y offset line
                    lea        (a4,d0.w),a4        ;add line x offset
                    sub.w    d0,d1                ;line width
                    
                    asr.w    #3,D1
                    bgt.s    .multi_words

To uwolniło mi parę rejestrów które mogłem wykorzystać do programowania BLiTTERa.


---Edycja---


ok, gotowe. udało mi się z deka wygładzić kod.
wieczorem może uda mi się uzupełnić brakujący kod dla blitMode (nowa procedura sblit3).

Ostatnio edytowany przez Cyprian (2015-04-27 15:03:41)

Post's attachments

TriangFi_BT4PC_D.zip 11.11 kb, liczba pobrań: 1 (od 2015-04-27) 

Tylko zalogowani mogą pobierać załączniki.
Lynx I / Mega ST 1 / 7800 / Portfolio / Lynx II / Jaguar / TT030 / Mega STe / 800 XL / 1040 STe / Falcon030 / 65 XE / 520 STm / SM124 / SC1435
DDD HDD / AT Speed C16 / TF536 / SDrive / PAK68/3 / Lynx Multi Card / LDW Super 2000 / XCA12 / SkunkBoard / CosmosEx / SatanDisk / UltraSatan / USB Floppy Drive Emulator / Eiffel / SIO2PC / Crazy Dots / PAM Net
http://260ste.atari.org

Odp: Algorytm obcinania wielokątów

Kur...ka. ;) Wiem, gdzie popełniłem błąd w swoim kodzie. Założyłem, że smudge przyjmie wartości tylko z przedziału 0-15, a przecież większe zostaną po prostu obcięte (!!!) - jedno przejście mam nadmiarowe. Ale z tego co widzę, trochę inaczej podszedłem do tematu i (po połączeniu naszych optymalizacji) wydaje mi się, że całość uda się zamknąć w 3 przejściach! Jak znajdę siły, postaram się napisać odpowiednią poprawkę...

23

Odp: Algorytm obcinania wielokątów

Myślisz o tylko jednym przejściu dla leftEdge i rightEdge? Teraz widzę że powinno dać radę dzięki ujemnemu dstYinc.

Swoją drogą to dzięki bo zmobilizowałeś mnie do ruszenia szarymi komórkami :)


---Edycja---
ok, właśnie przeczytałem PMa :)
Więc miałeś na myśli leftEdge i rightEdge w jedym przebiegu. Dobry pomysł. Teraz wydaje mi się on oczywisty, no ale nie przyszło mi to wcześniej do głowy.

Ostatnio edytowany przez Cyprian (2015-04-27 16:42:10)

Lynx I / Mega ST 1 / 7800 / Portfolio / Lynx II / Jaguar / TT030 / Mega STe / 800 XL / 1040 STe / Falcon030 / 65 XE / 520 STm / SM124 / SC1435
DDD HDD / AT Speed C16 / TF536 / SDrive / PAK68/3 / Lynx Multi Card / LDW Super 2000 / XCA12 / SkunkBoard / CosmosEx / SatanDisk / UltraSatan / USB Floppy Drive Emulator / Eiffel / SIO2PC / Crazy Dots / PAM Net
http://260ste.atari.org

Odp: Algorytm obcinania wielokątów

Cyprian napisał/a:

Więc miałeś na myśli leftEdge i rightEdge w jedym przebiegu.

Dokładnie tak. :D Po tym, jak otworzyłeś mi oczy na odpowiednie wykorzystanie xCountów i yCountów pierwsze co robię, to zastanawiam się, czy nie da się tego odpowiednio wykorzystać :) W wolnej chwili połączę optymalizację i będziemy mieć BOSKIE wypełnianie. :D

Odp: Algorytm obcinania wielokątów

Yeah! Zbliżamy się do końca optymalizacji. Mam już 3-przebiegową wersję generowania masek na blitterze, a dodatkowo po mojej ostatniej optymalizacji kod wypełniania wygląda tak: :D

    movem.w    (a2)+,d0-d3            ;left x offset, right x offset, left mask, right mask
    sub.w    d0,d1                ;line width
    ext.l    d0
    add.l    (a5)+,d0
    asr.w    #3,d1
    bgt.s    .multi_words

Jak dodam pomniejsze optymalizację na tryby adresowania oczywiście wrzucę wersję ostateczną