Szybka procedura PLOT by Kaz 2009-03-16 18:00:53

Ostatnio niespożyty w siłach i entuzjaźmie do Atari Tomasz "TDC" Cieślewicz uraczył nas historią o "Bajtku" i niedoszłym konkursie w języku "Action!", a już za chwilę kolejna opowieść ze starych czasów. I o dziwo, również związana z tym językiem, wywodzącym się z filozofii Algola (jak wszystkie C-podobne i Pascalo-podobne). Mikrofon oddaję Tomkowi:

1. Kawałek historii

"Podsyłam szybką procedurę PLOT napisaną przez Arkadiusza Łukszo oraz Jakuba Husaka. Myślę, że autorzy pisali na tej procedurze swoje programy w trybie GR8, między innymi "Ortrografię".

Procedurkę otrzymałem w firmie "Mirage" na wypadek, gdybyśmy potrzebowali coś zrobić w trybie graficznym GR8. Było to raczej na wyrost, bo nic takiego nie planowaliśmy. Jednak był to miły gest, którym Arek Łukszo chciał nam okazać swoje zaangażowanie we wspólne tworzenie nowego oprogramowania. Niestety był to już ostatni taki gest z jego strony, bo szybko przeskoczył na inne pole działań - DTP - i nawet udało mu się tam znaleźć atrakcyjną posadę.




2. Szybka procedura PLOT

Przekazanie tego kodu było dość poufne, nie pamiętam szczegółów, ale pewnie Arek prosił, aby nikt poza "Mirage" tego kodu nie widział. Tyle lat minęło, a kod stracił swoją "wartość rynkową", więc mam nadzieję, że Arek i Kuba nie będą mieli nam za złe, że ich kod został opublikowany ;). Można go potraktować jak coś w rodzaju biblioteki (z jedną procedurką):


; PLOT in 8 gr. 13 RAZY SZYBSZY
; (C) 1989 by Mirage Software Ltd.
; programmed by Arkadiusz Lukszo
; & Jakub Husak

PROC _XPOSM=*()
[ $7F $BF $DF $EF $F7 $FB $FD $FE ]
PROC _XPOM=*()
[ $80 $40 $20 $10 $08 $04 $02 $01 ]
PROC _PL_2=*() [
$8A ; TXA
$A2 $00 ; LDX #0
$86 $CC ; STX ADRP+1
$85 $CB ; STA ADRP
$0A ; ASL A
$26 $CC ; ROL ADRP+1
$0A ; ASL A
$26 $CC ; ROL ADRP+1
$18 ; CLC
$65 $CB ; ADC ADRP
$90 $02 ; BCC S1
$E6 $CC ; INC ADRP+1
;S1
$0A ; ASL A
$26 $CC ; ROL ADRP+1
$0A ; ASL A
$26 $CC ; ROL ADRP+1
$0A ; ASL A
$26 $CC ; ROL ADRP+1
$18 ; CLC
$65 $58 ; ADC 88
$85 $CB ; STA ADRP
$A5 $CC ; LDA ADRP+1
$65 $59 ; ADC 89
$85 $CC ; STA ADRP+1
$98 ; TYA
$29 $07 ; AND #7
$AA ; TAX
$98 ; TYA
$46 $A3 ; LSR $A3
$6A ; ROR A
$4A ; LSR A
$4A ; LSR A
$A8 ] ; TAY
PROC _SL=*() [
$A9 $00 ;COL LDA #0
$C9 $01 ; CMP #1
$F0 $08 ; BEQ UNPL
$B1 $CB ; LDA (ADRP),Y
$3D _XPOSM ; AND XPOSM,X
$91 $CB ; STA (ADRP),Y
$60 ; RTS
$B1 $CB ;UNPL LDA (ADRP),Y
$1D _XPOM ; ORA XPOM,X
$91 $CB ; STA (ADRP),Y
$60 ] ; RTS

PROC FPLOT=*(BYTE COL,Y CARD X)
[ $8D _SL+1 ; STA COL+1
$4C _PL_2 ] ; JMP _PL_2


Uwaga do tej procedury o nazwie FPLOT: ma ona zamienione współrzędne w stosunku do standardowej procedury bibliotecznej "Action!", dodatkowo w pierwszym parametrze określa się kolor punktu. Procedura znajduje sie w archiwum jako PLOT1.ACT. Poniżej znajduje się przykład, w jaki sposób można ją wykorzystać we własnych programach (nazwane tu procedurami testującymi), w archiwum zapisane jako PLOT2.ACT:

MODULE

BYTE Q

; PLOT in 8 gr. 13 RAZY SZYBSZY
; (C) 1989 by Mirage Software Ltd.
; programmed by Arkadiusz Lukszo
; & Jakub Husak

PROC _XPOSM=*()
[ $7F $BF $DF $EF $F7 $FB $FD $FE ]
PROC _XPOM=*()
[ $80 $40 $20 $10 $08 $04 $02 $01 ]
PROC _PL_2=*() [
$8A ; TXA
$A2 $00 ; LDX #0
$86 $CC ; STX ADRP+1
$85 $CB ; STA ADRP
$0A ; ASL A
$26 $CC ; ROL ADRP+1
$0A ; ASL A
$26 $CC ; ROL ADRP+1
$18 ; CLC
$65 $CB ; ADC ADRP
$90 $02 ; BCC S1
$E6 $CC ; INC ADRP+1
;S1
$0A ; ASL A
$26 $CC ; ROL ADRP+1
$0A ; ASL A
$26 $CC ; ROL ADRP+1
$0A ; ASL A
$26 $CC ; ROL ADRP+1
$18 ; CLC
$65 $58 ; ADC 88
$85 $CB ; STA ADRP
$A5 $CC ; LDA ADRP+1
$65 $59 ; ADC 89
$85 $CC ; STA ADRP+1
$98 ; TYA
$29 $07 ; AND #7
$AA ; TAX
$98 ; TYA
$46 $A3 ; LSR $A3
$6A ; ROR A
$4A ; LSR A
$4A ; LSR A
$A8 ] ; TAY
PROC _SL=*() [
$A9 $00 ;COL LDA #0
$C9 $01 ; CMP #1
$F0 $08 ; BEQ UNPL
$B1 $CB ; LDA (ADRP),Y
$3D _XPOSM ; AND XPOSM,X
$91 $CB ; STA (ADRP),Y
$60 ; RTS
$B1 $CB ;UNPL LDA (ADRP),Y
$1D _XPOM ; ORA XPOM,X
$91 $CB ; STA (ADRP),Y
$60 ] ; RTS

PROC FPLOT=*(BYTE COL,Y CARD X)
[ $8D _SL+1 ; STA COL+1
$4C _PL_2 ] ; JMP _PL_2

; -------- PROC TESTUJACE ---------

PROC TEST_NORMAL8()
GRAPHICS(8+16)

DO
[173 $D40B 201 20 208 249]
POKE(53274,5)
COLOR=1
FOR Q=0 TO 12 DO
PLOT(Q,70)
OD
POKE(53274,0)
OD
[96]

PROC TEST_FAST8()
GRAPHICS(8+16)

DO
[173 $D40B 201 20 208 249]
POKE(53274,5)
FOR Q=0 TO 146 DO
FPLOT(1,50,Q)
OD
POKE(53274,0)
OD
[96]

PROC MAIN()
;TEST_NORMAL8()
TEST_FAST8()
[96]


Powyższy program wymaga kilku wyjaśnień. Domyślnie uruchamiany jest test szybkiej procedury PLOT dla trybu graficznego GR8. Wystarczy jednak usunąć znacznik ";" oznaczający komentarz, sprzed procedury "TEST_NORMAL8()", aby najpierw uruchomił się drugi test - czyli zwykłej procedury bibliotecznej PLOT (dostępnej w "Action" dla każdego trybu graficznego). Po każdym uruchomieniu, czy to procedury standardowej czy szybkiej, wychodzi się z programu przez Reset. Dlatego, jeżeli chcemy testować drugą procedurę (TEST_NORMAL) nie trzeba wyłączać poprzez ";" tej pierwszej (TEST_FAST), ponieważ i tak nigdy się nie uruchomi.

3. No i jak z tą szybkością?

Czas przetestować szybkość tej procedury. Metoda jest moja i nieco inna niż w poprzednim tekście o szybkości "Action!". Tam było sprawdzane, ile przebiegów pętli będzie miało miejsce przez 100 ramek. W tym wypadku mierzymy, ile maksymalnie da się wykonać wywołań procedur w czasie jednej ramki. Umyślnie w procedurach znajduje się pętla, która powoduje, że za każdym razem współrzędna x będzie inna, dzięki temu wyniki testu będą dawały bardziej rzetelne wyniki, bliższe faktycznym osiągom w typowych programach, które rysują lub animują.



W tym rozwiązaniu program w nieskończonej pętli, za każdym razem jest zatrzymywany do momentu, w którym procesor ANTIC będzie wyświetlał swoją dwudziestą linię (dzieje się to w tym krótkim kodzie maszynowym). Dzięki temu każda iteracja pętli jest synchronizowana z generowaniem obrazu przez ANTIC. Dopóki ilość wykonanych skoków do procedur (wraz z czasem wykonania) nie przekroczy czasu ramki - kolor tła (od 20 linii; zmieniany procedurą POKE) będzie stabilny. W momencie gdy ilość przekroczy czas trwania ramki - kolor ramki będzie migał ze względu na fakt, że owa synchronizacja nastąpi w następnej ramce generowanego obrazu.

Jak widać dla szybkiej procedury PLOT wynikiem jest 147 punktów na ramkę, a dla standardowej 13... Z prostej matematyki wychodzi, że autorzy nieco przereklamowali swoją procedurkę, gdyż oznajmili w źródle że jest szybsza 13 razy, a jest trochę ponad 11 razy szybsza. Jednak nie czepiajmy się, osiągnięty wynik i tak jest przytłaczający i zadowoli wielu programistów, którzy programują grafikę składającą się z punktów w GR8.

Warto jeszcze na chwilę zatrzymać się przy wyniku 13 punktów na ramkę dla standardowej procedury bibliotecznej, gdyż jest to i tak dość dobry wynik. Miłośnicy Basica domagają się podania przykładów, że "Action!" jest równie wygodny jak "Basic", a przy tym jest od niego szybszy. Tu widać wyraźnie, że zwykłe przepisanie kodu z Basic do "Action!" spowoduje znaczne przyspieszenie programu. Nie znam szczegółów wydajności PLOT w Basicu, ale mniemam, że w "Atari Basic" jeden PLOT trwa przez około 1 ramkę. Dodatkowo pozostały kod będzie również mało wydajny, z tego co wiemy pojedyncze instrukcje w tym języku trwają około 1 ramki. W "Action!" da się tu zaoszczędzić wiele czasu, o czym już była mowa wielokrotnie i pewnie jeszcze będzie w następnych tekstach.

Oczywiście ilość rysowanych punktów będzie w praktyce mniejsza, bo w prawdziwym programie potrzebujemy zrobić coś więcej niż wyświetlenie nieruchomych punktów. Jeśli na przykład zechcemy, aby punkty poruszały się po torze wyliczonym jakąś skomplikowaną funkcją trygonometryczną to oczywiście będzie to działać wolniej niż 147 punktów na ramkę, dodatkowo zwykle musimy stracić połowę wydajności na kasowanie punktów. Odtwarzanie muzyki w grze również zabierze nieco czasu procesora.

4. I co dalej?

Nie mam wątpliwości, że to samo można wykonać szybciej, nie tylko z poziomu asemblera, ale i z poziomu kodu "Action!". Druga sprawa, że procedurka należy do tych wygodniejszych i bardziej intuicyjnych, umożliwia przecież wybranie koloru, którym rysujemy punkty. W wielu programach jest to bardzo wygodne, jednak szybsze procedury to te, w których nie wybiera się koloru, lecz są one wybierane na przemian zgodnie z jakąś funkcją boolowską, na przykład XOR. Niewątpliwie można więc tę procedurę przyspieszyć.



Myślę, że współczynnik byłby dość dobry (można to porównać z procedurą rysującą w algorytmie Konrada "KMK" Kokoszkiewicza, ostatnio przypomnianym na atarionline.pl). Wtedy kiedy KMK pracował nad tym tekstem - przeprowadziliśmy szereg dyskusji. KMK zaproponował wtedy najszybszy możliwy algorytm rysujący, minimalizujący operacje na 16-bitowych adresach, ale który był wtedy jedynie teoretycznym rozwiązaniem. Jednak dziś można na jakimś mocno rozszerzonym komputerze Atari pokusić się o napisanie i przetestowanie tego pomysłu (inna sprawa, że te pomysły pewnie są już zaimplementowane w wielu najnowszych grach oraz demkach).

Następną procedurą w asemblerze do opracowania powinna być procedura rysująca szybkie duszki w trybie graficznym GR8 - wtedy będzie można popracować nad jakąś grą.
larek 2009-03-16 18:31:55

A ja muszę znowu trochę pomarudzić ;-)
Pisze się procedurę w 99,99% w asemblerze, a głośno się mówi - jaki to ten Action! jest szybki...
Wstawki w kodzie maszynowym w Basicu też można uruchamiać!

homek 2009-03-16 19:06:36

Dokładnie! Teraz tylko przepisać to na czysty ASM, a potem kickąć Action! w assa a TeDeCa w ... (hehe). I szlus! ;-]

Kaz 2009-03-17 02:39:14

To moze kolega homek oprocz mocnych slow zaprezentuje tez swoje programy w asemblerze na Atari? Chetnie popatrze...

bob_er 2009-03-17 06:45:45

jesli juz asm zostal wspomniany - szybkiego plota w gr.8 to soused teat w barymagu 1 opisal. z tym, ze tamten kilku tablic wymaga, ale dosyc szybki jest. no i na waski ekran tylko (bo szybciej).

tdc 2009-03-17 10:15:40

larek: ale ja nie miałem zamiaru tu udowadniać, że Action! jest szybki tylko dlatego że uruchamia się w nim procedurę w asm. To jedynie historyczne wspominki, część osób jest zainteresowana nauką tego języka więc jeśli ktoś planuje jakiś program w gr 8 to już ma do tego fajną procedurkę – do czasu jak np. Yosh napisze szybszą ;)

homek: te dwa teksty to dwa różne zagadnienia – testowanie wydajności Action! i testowanie wydajności procedury (której nie jestem autorem – ja jedynie testowałem szybkość). Tu opisujemy szybkie przydatne procedury, jak wspominam, następną przydatną będzie procedura szybkich duszków do tego trybu. Obie te procedury dają wygodę pisania dowolnych, wydajnych programów np. gier.

bob_er: tak, wersje z tablicami są znacznie szybsze, co prawda w tamtych czasach uznawało się że przesunięcia bitowe są wystarczającą optymalizacją, jednak w praktyce okazuje się że lepiej jest wszystko zaprojektować w oparciu o tablice (ale to jest późniejsze okrycie).
Jednak ten plot też ma swoje zalety (np. wspomniana wygoda), która w mojej ocenie powinna być zadowalająca dla osób przesiadających się z Basic.

Może ktoś się pokusi o zoptymalizowanie tego kodu w asm ? Tak aby można było w Action! demka pisać ? Jak rozumiem jedna osoba już się wyrywa do tego zadania ?? ;)

larek 2009-03-17 10:32:13

a nie, to spoko :)

Konop 2009-03-18 17:46:02

Wszystko zależy od założeń. Szybki plot?

sta adr+1
ldy Div8,x
lda (adr),y
ora Bits,x
sta (adr),y

...

dss 2009-03-20 21:40:16

A może jest ktoś, kto implementował w asm-ie procedurkę DRAWTO na własną rękę? Jeśli tak - niech się może pochwali swoją procedurką, bo tu już nie jest tak prosto jak w PLOT.

Zna ktoś coś szybszego od Bresenhama? Ale koniecznie z wyborem 8-mio kierunkowym - nie 4-ro kierunkowym.

Na mnie osobiście przed laty ogromne wrażenie zrobiło demko "What?" napisane zdaje się przez MSL-a. Pytanie tylko czy ono było przeliczane w real-time czy w całości stablicowane?

bob_er 2009-03-20 23:27:23

od bresenhama zdaje sie, ze nic szybszego nie ma. no i operuje tylko na liczbach calkowitych, co tez ma swoje zalety.
nie przesadzaj, ze bresenham jest taki ciezki do napisania. na sieci jest pelno opisow jak to zrobic: http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
garsc informacji w ujeciu maluchowym jest tez tu: http://atariarea.krap.pl/artykul/kurs-assemblera-cz.-8/31
rasowy bresenham jest 8-kierunkowy. 4 kierunki to prosta optymalizacja, polegajaca na tym, ze drawa od (0,0) do (10,5) moze zrobic ta sama procka co z (10,5) do (0,0). jak zrobisz kod samomodyfikujacy sie, to zejdziesz do 2 kierunkow (deltax>deltay oraz deltax<=deltay).

dss 2009-03-21 13:34:02

Jako wybór 8-mio kierunkowy miałem tutaj na myśli wybór kierunków: N,S,W,E i pośrednich: NE, NW, SE, SW. To o czym piszesz, że można rysować odcinek od końca to już optymalizacja algorytmu a nie sam algorytm. Różnica między 8-mio kierunkowym a 4-kierunkowym jest taka, że w 4-ro kierunkowym wybierasz tylko ruch w górę lub w bok, a w 8-mio kierunkowym masz jeszcze do dyspozycji ruch diagonalny.
W efekcie w 4-ro kierunkowym uzyskane linie są po prostu "grubsze", ale za to nadają się do antyaliasowania.

Co do innych algorytmów rysowania linii słyszałem też kiedyś o jakimś bardzo szybkim algorytmie bazującym na tablicach - tyle, że ten kto o nim mówił nie był w stanie podać nazwy tego algorytmu. Podobno wymagał bardzo dużej ilości pamięci. Słyszał ktoś coś o takim algorytmie?

bob_er 2009-03-21 18:00:51

hmm... nie wiem, na ile sie wglebiales w rysowanie drawa. bresenham tutaj jest absolutnym numerem 1. jesli nie, to chetnie poznam szybszy algorytm.
oczywiscie, ze redukowanie kierunkowosci, to jest optymalizacja implementacji - algorytm nadal jest bez zmian. tylko nie wiem, skad ci sie wziela rozna 'grubosc' drawa. bresenham ma tez ta wlasciwosc, ze drawa rysuje idealnie, jakby nie kombinowac, draw jest prosty, elegancki i powtarzalny.

co do antialiasingu, to masz go tutaj:
http://en.wikipedia.org/wiki/Xiaolin_Wu's_line_algorithm

jest jeszcze algorytm o nazwie 'Double-step incremental generation of lines and circles' - z tego co wiem, na maluchu nikt tego jeszcze nie zaimplementowal. tutaj stawiasz od razu 2 pixle. dostep do artykulu niestety jest platny. metoda ta jest tez wspomniana w 'wprowadzenie do grafiki komputerowej' (isbn 83-204-1840-2) - wiec jak ksiazke masz, mozesz go zaimplementowac.

nie wiem, jaki inny algorytm opisujesz, ale tablice sugeruja, ze to jednak implementacja cos nowego wniosla.

Konop 2009-03-21 22:04:21

Można zmodyfikować odpowiednio algorytm rysowania odcinka, aby uwzględniał zmienność jasności w funkcji nachylenia, oczywiście przy założeniu, że posiadamy więcej bitów na piksel aniżeli jeden. Po zastanowieniu dochodzę jednak do wniosku, że można wyobrazić sobie także wersję dla jednobitowego wariantu, modulując funkcję zapalenia poszczególnego piksela w f. kąta.

W wariancie 8'mio kierunkowym również - a raczej przede wszystkim w nim - można zastosować anty-aliasing. Najprostsza bowiem implementacja rysowania odcinka z uwzględnieniem anty-aliasingu oparta jest właśnie na algorytmie przyrostowym.

Wersja przyrostowa: http://en.wikipedia.org/wiki/Xiaolin_Wu's_line_algorithm

Ciekawa wersja z punktem środkowym: http://courses.ece.illinois.edu/ece390/archive/archive-f2000/mp/mp4/anti.html

Ta druga wersja jest jednak mało praktyczna, gdyż jest obciążona dzieleniem. Co prawda ta operacja występuje również w wariancie przyrostowym, ale jest on znacznie prostszy i dlatego tego pierwszego należy potraktować raczej jako ciekawostkę, aniżeli coś do praktycznego zastosowania.

Co do algorytmu bazującego na tablicach... Wątpię, czy istnieje w ogóle dla niego jakaś konkretna nazwa, ponieważ byłoby to proste próbkowanie punktów na linii, przy użyciu dowolnego algorytmu wyjściowego. Dane tablic wyliczyć jest najprościej w oparciu o wariant przyrostowy. Algorytm jest banalny. Można sobie wyobrażać jego różne implementacje, w zależności od ograniczeń pamięciowych. Możemy np. stworzyć tablicę dla pełnej rozciągłości dziedziny współrzędnych, albo w alternatywnym podejściu dla pewnego stablicowanego podzbioru nachyleń dopasowując odpowiedni wycinek tablicy na podstawie bieżącej części ułamkowej współrzędnej podrzędnej (minor) oraz nachylenia. Co ciekawe, w tym ujęciu można/należy wykorzystać precyzję podpikslową.

Optymalną implementacją pod pewnymi warunkami wydaje się być wersja "Symmetric Double Step" autorstwa B. Wyvill'a, opublikowana w książce Graphics Gems, dostępna pod tym adresem: http://tog.acm.org/GraphicsGems/gems/DoubleLine.c . Wykorzystuje ona jednostkowe obliczanie decyzji dla dwóch kolejnych ruchów oraz symetrię. Ten algorytm nadaje się jednak wyłącznie dla wariantu całkowito-liczbowego. Nie uzyskamy nim dokładnych linii przy próbie kreślenia odcinków z precyzją podpikslową, a przynajmniej taka modyfikacja nie miałaby żadnego sensu z pkt. widzenia wydajności.

dss 2009-03-22 09:35:23

bob_er:
Odnosnie interpretacji 4-ro i 8-mio kierunkowego wyboru - podaję linka to obejrzenia przykładu:
http://lifc.univ-fcomte.fr/home/~ededu/projects/bresenham/diff.png
Zielony to Bresenham, niebieski to jakis inny algorytm - wyglądający jak 4-ro kierunkowy w dużym przybliżeniu (sorry - wiem, że to niezbyt dobry przykład ale tylko taki na szybko znalazłem). Zauważ, że Bresenham daje w wyniku cieńszą linię, bo może wykonywać ruchy diagonalne a niebieski widać, że może wykonywać tylko ruchy góra, dół, prawo, lewo - stąd ten odcinek jest grubszy, ale właśnie te nadmiarowe punkty są używane do uzyskiwania antyaliasingu - poprzez zmianę składowych koloru. To tyle odnośnie A-A, bo to nie było istotą mojego pytania - tylko wyszedł z tego taki dygresyjny wątek.

W kwestii algorytmów z wyborem 4-ro i 8-mio kierunkowym proponuję rzucić okiem do książki "Elementy grafiki komputerowej" Michała Jankowskiego - rozdz. 3.2. "rysowanie odcinka" - jest tam bardzo fajny przykład ilustrujący różnice między nimi.

Dla rozwiania wątpliwości - szukam czegoś szybszego od Bresenhama, z wyborem 8-kierunkowym, bez A-A, tryb 1-bitowego koloru.

Pytanie do tych, którzy na własną rękę implementowali algorytm rysowania linii - ile razy szybsze były wasze implementacje DRAWTO od systemowej z OS-a? Pochwalcie się :-)

dss 2009-03-22 09:54:16

Konop:
Co do algorytmu tablicowego - daaawno temu obiła mi się o uszy metoda z prekalkulowanymi danymi dotyczącymi pewnego wycinka płaszczyzny - na zasadzie zapisywania kolejnych ruchów typu: poziomo, góra, na ukos. Ale być może jest to po prostu stablicowany Bresenham... więc nic nowego.

A może jakiś konkursik na najszybsze DRAWTO? :-)

bob_er 2009-03-22 12:33:01

1. ten zielony, to jest modyfikacja bresenhama polegajaca na rysowaniu wszystkich pixli, mniej lub bardziej lezacych na prostej idealnej (to nawet pisze w 1szym zdaniu w linka przez ciebie podanego i dla niepoznaki tytul strony tez podobna mysl sugeruje).
2. w kwestii istoty sprawy: poki co skup sie na bresenhamie (o ktorym ciagle wspominasz, ale tego nie nazywasz). a jak znajdziesz cos szybszego, to sie pochwal.
3. konkurs. swego czasu na atariarea byl, ale po chwili padl dysk, i watek nie zdazyl sie zbackupowac :(.
moje przemyslenia: nie chce byc niegrzeczny/niemily, ale zeby sprawa nie wygladala jak 'kto mi napisze fajnego drawa', wypadalo by zaczac od siebie, i wlasnego drawa przedstawic. reszta koderow, w ten czy inny sposob swoje procki udostepnila (chocby w demach), wiec niczego udowadniac nie musza.
z mojej strony eot - zaczyna sie filozofowanie.

bob_er 2009-03-22 12:33:51

pomylilem kolory - w 1 powinno byc niebieski, nie zielony.

Konop 2009-03-22 13:37:09

dss: Z linku, który podałeś, możesz usunąć końcówkę i dzięki temu przekonać się, że wersja 4'ro kierunkowa to również Bresenham, tyle, że zmodyfikowany: http://lifc.univ-fcomte.fr/home/~ededu/projects/bresenham .

Co do prędkości... O implementacji Basic'owej nie warto w ogóle pisać - jest na bank dużo (wielokrotnie) wolniejsza od najszybszych implementacji demo-scenowców. Jedną z takowych jest moja - wcale nie optymalna - znajdująca się w pakiecie z asemblerem Mads (http://mads.atari8.info/). Zajrzyj do pliku examplesfast_draw.asm . Proponuję w pierwszej kolejności zapoznać się z tą implementacją, choć jak już wspominałem, nie jest ona optymalna pod względem prędkości działania. Dużo zależy od założeń. Dla przykładu - można znacznie przyspieszyć procedurę odpowiednio organizując ekran, ustawić modulo linii na 256 (takie podejście jest wyrzystane w demie Overmind/Slight). Można tę procedurę lekko przyspieszyć, ale na większe zyski można liczyć dopiero po rozszerzeniu w postaci rysowania od dwóch końców oraz z wyborem na dwa piksele w przód. Z tego co mi wiadomo, jak do tej pory nikt nie napisał takowego na maluszku. Być może to jest dobra okazja, abyś się wykazać.

Odnośnie prędkości działania. Nie sądzę, aby istniał żaden algorytm prostszy/szybszy od Bresenhama bądź przyrostowego. To, który z nich jest lepszy, zależy silnie od kontekstu, czyli docelowa platforma (procesor).

Konop 2009-03-22 13:40:38

W nawiązaniu do ostatniej mojej wypowiedzi... Oczywiście, można zaimplementować również wersję opierającą się na tablicach i taka implementacja byłaby optymalna, z tym, że wymagałaby dużej ilości pamięci, co znacznie ogranicza zakres jej zastosowań.

dss 2009-03-22 15:13:07

bob_er:
nie no - nie było moją intencją, żeby ktoś za mnie napisał DRAWTO, chodziło tylko o wskazanie najszybszego algorytmu. Implementacją sam chciałem się zająć - w tym cała zabawa właśnie.

Konop:
dzięki za linka do asm-a i sugestie.

Ok, dzięki wam obu za odpowiedzi.
EOT

Tdc 2009-03-28 02:43:49

Dzięki Konop za zaangażowanie, ja niestety obecnie nie mogę się włączyć np. w pisanie drawto (nie mam czasu nawet tu czytać i pisać - a szkoda !).

Natomiast jakiś czas temu zrobiłem dodatkowe testy:
fplot(1,0,0) daje 149
fplot(1,191,319) daje 145

Co potwierdza, że moje podejście z testowaniem zmieniających się parametrów badanej procedurki będzie dawało wyniki najbardziej wiarygodne, czyli najlepiej zbliżone do przeciętnych programów.

Warto tu dodać, że wielu producentów (np. procesorów) wykorzystuje wiedzę odnośnie budowy procesora czy cech algorytmu do preparowania takich testów (programów, danych), że przemawiają one NAD WYRAZ dobrze o osiągach - są one świetne na tle konkurencji, ale odległe od faktycznych osiągów w typowych zastosowaniach (np. wydajność CPU w przeciętym programie biurowym).

Wyniki te natomiast nie rozwiązują zagadnienia jak Arkowi i Kubie mogło wyjść owo 13 ? Wg mnie nie ma na to najmniejszych szans.

jhusak 2011-12-14 12:39:19

To było liczone, ile punktów na ramkę można narysować. I wyszło, że 13 razy więcej.