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
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
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.