Posts from 2007

Szare shadery

2007-11-19 19:58

Dawno, dawno temu – co w dziedzinie programowania grafiki oznacza perspektywę kilkuletnią – większość przetwarzania odbywała się we wbudowanym, stałym potoku graficznym. Shadery wprawdzie były, ale oferowane przez nie możliwości były dosyć ubogie (zwłaszcza jeśli chodzi o te do pikseli), a poza tym należało kodować je w niezbyt przyjaznym języku podobnym do asemblera. Pewnie dlatego, a dodatkowo także z powodu małego wsparcia kart graficznych, większość efektów realizowano przy pomocy odpowiednich tekstur, stanów ich faz i tym podobnych wynalazków. Bardzo często tak było po prostu łatwiej.
Zadziwiające jest to, że teraz nierzadko bywa dokładnie odwrotnie :) Chociaż na początku można jeszcze uważać, że ustawianie przeróżnych stanów stałego potoku i poleganie wbudowanie jest łatwiejsze, a shadery dają “tylko” większe możliwości, to jednak z czasem to myślenie zawsze powinno się zmienić. W końcu przecież napisanie algorytmu określającego dokładnie krok po kroku, co się dzieje z wierzchołkiem lub pikselem, dla programisty z założenia musi być łatwiejsze niż ustawianie jakichś dziwnych flag, będącymi swoistymi wytrychami do standardowego sposobu przetwarzania.

Zresztą nie wszystko można tymi wytrychami łatwo osiągnąć. Weźmy niezwykle prosty efekt wyświetlania w skali szarości, jak na czarno-białym zdjęciu. Jeżeli chodzi o realizację tego efektu na fixed pipeline, to chwilowo nie mam na to żadnego sensownego pomysłu – oczywiście poza podmianą wszystkich tekstur na ich ‘szare’ wersje.
A wystarczyłoby tylko użyć prostego pixel shadera, który jawnie implementuje wzór na obliczenie natężenia koloru:

  1. float3 PS(float4 cl : COLOR0, /* itd */)
  2. {
  3.    float gray = 0.3f * cl.r + 0.59f * cl.g + 0.11f * cl.b;
  4.    return float3(gray, gray, gray);
  5. }

I już, efekt gotowy. Nietrudno byłoby też połączyć go z jakimkolwiek innym. W ogólności jest jednak ‘trochę’ trudniej – ale to już temat na inną okazję ;P

Tags: , ,
Author: Xion, posted under Programming » 6 comments

Nietypowe licencje

2007-11-17 13:27

Programy – zwłaszcza te do znalezienia w Internecie – są dostępne na wielu różnych rodzajach licencji. Do tych najbardziej znanych należą chociażby wszelakie licencje typu open source (na czele ze znaną i (nie)lubianą GNU GPL), freeware i shareware. Ale hakerska wyobraźnia nie zna granic i nawet w tak “poważnym” temacie pojawiły się żartobliwe wynalazki.
Wśród takich zdecydowanie nieszablonowych licencji mamy na przykład:

  • postcardware, wedle której użytkownik może korzystać z programu pod warunkiem, że prześle autorowi kartkę pocztową ze swojego miasta. W innych wariantach może to być też e-mail, chociaż osobiście uważam, że możliwość pochwalenia się imponującą kolekcją pocztówek jest o wiele bardziej zachęcająca niż perspektywa zapychającej się skrzynki mailowej :)
  • guiltware, charakteryzująca się tym, że program co jakiś czas wyświetla komunikat o tym, jak wiele wysiłku autor włożył w tworzenie danej aplikacji. Rzeczony komunikat ma wywołać w użytkowniku poczucie winy (stąd nazwa) i spowodować przesłanie autorowi drobnej sumy pieniędzy. To oczywiście dość drastyczna forma donationware i wydaje mi się, że skutek, jaki by odniosła, byłby raczej odwrotny do zamierzonego ;]
  • linkware, zakładającą że użytkownicy powinni w widocznym miejscu zamieścić link do strony internetowej autora. Jak nietrudno się domyślić, ten typ licencji stosuje się głównie do bibliotek programistycznych lub do treści możliwych do zamieszczenia na stronach WWW (np. obrazków), i generalnie nie wydaje się specjalnie dolegliwy.
  • beerware, która jest prawdopodobnie najlepsza z nich wszystkich :) Otóż według niej użytkownik w zasadzie może bez ograniczeń korzystać z programu – pod jednym warunkiem. Jeśli mianowicie kiedyś zdarzy mu się spotkać jego autora, ma kategoryczny obowiązek… postawić mu piwo :D Inne wersje zakładają wręcz wysłanie autorowi skrzynki chmielowego napoju lub tylko wypicie za jego zdrowie. No cóż, na pewno jest to praktyczniejsze niż wysyłanie pocztówek, a przy odrobinie szczęścia też może zostać pamiątka w postaci podstawki lub w ostateczności butelki ;]
  • otherware to z kolei cała masa różnych rodzajów “licencji” (cudzysłów jest tu już chyba uzasadniony), które proszą użytkownika o różne rzeczy nieprzynoszące żadnych bezpośrednich korzyści autorowi. Są to przykładowo:
    • careware (charityware) – użytkownik powinien wpłacić drobną (lub niekoniecznie drobną) sumę pieniędzy na konto wskazanej organizacji charytatywnej. Przykładem programu, który o to prosi, jest edytor vim.
    • greenware – tutaj w zamian za możliwość korzystania z programu, user jest zobowiązany zadbać jakoś o środowisko naturalne, a więc np. zacząć segregować śmieci, przestać używać jednorazowych opakowań, korzystać ze środku transportu publicznego, itd.
    • Garfield!

    • catware -w tym wariancie możliwe jest bezpłatne korzystanie z programu, o ile jego użytkownik poświęci przynajmniej jedną godzinę na… zabawę z jednym lub kilkoma kotami, niekoniecznie własnymi. Zapewne gdyby ta licencja była powszechnie stosowana, spowodowałoby to protesty właścicieli psów i chomików :)

Wniosek z tej listy jest taki, że określanie swoich programów jako po prostu freeware to marnotrawienie wielkiej okazji, aby zrobić coś dobrego. Nie mówię już nawet o wspomaganiu pożytecznych organizacji czy propagowaniu ekologii. Pomyślmy raczej o kotach! ;))

Tags: , ,
Author: Xion, posted under Applications » 6 comments

Sprzątanie śmieci

2007-11-15 23:22

Pamięcią operacyjną można w programowaniu zarządzać na dwa sposoby. Pierwszy to ręczne tworzenie obiektów i niszczenie ich, gdy nie są już potrzebne. Daje to kontrolę nad czasem ich życia, ale dopuszcza też możliwość powstawania błędów, jak wycieki pamięci czy próby podwójnego jej zwalniania. Aby im zapobiec, każdy obiekt musi mieć ściśle określonego właściciela, odpowiedzialnego za jego zniszczenie.
Drugi sposób to użycie mechanizmu odśmiecania pamięci (garbage collecting), które powinien sam wykrywać “porzucone” obiekty i je zwalniać, kiedy zachodzi ku temu potrzeba. Pozwala to oczywiście przestać martwić się o ich niszczenie. Zwykle nie oznacza to jednak, że wszystkie wyciekające fragmenty pamięci zostaną zwolnione natychmiast. Tracimy więc kontrolę nad czasem życia obiektów.

Nie da się jednak ukryć, że od kiedy komputery mają dość mocy obliczeniowej, aby wyświetlać miękkie cienie pod okienkami, mogą też z powodzeniem zajmować się automatycznym porządkowaniem sterty w swoim wolnym czasie. Dlatego zdecydowana większość nowych języków programowania jest wyposażona w odśmiecacze, które na dodatek są zawsze włączone i zwykle nie da się z nich zrezygnować. Najlepiej byłoby naturalnie mieć tutaj wybór, lecz rzadko jest on nam dany.
Nie inaczej jest w C++, tyle że tutaj mamy chyba jednak tę gorszą opcję – czyli konieczność ręcznego zarządzania alokacją i zwalnianiem. Można aczkolwiek to zmienić, lecz nie odbędzie się to w sposób przezroczysty dla programisty.

Odśmiecanie można przeprowadzić dwiema podstawowymi metodami, które mają naturalnie wiele wariantów. Są to:

    Referencje cykliczne

  • Śledzenie odwołań. Oznacza to posługiwanie się strukturą grafu w celu oznaczania elementów nieosiągalnych z bieżącego miejsca w programie, a następnie ich sukcesywnego zwalniania. Wymaga to wiedzy o tym, jak jeden obiekt może odwoływać się do drugiego i w C++ wymagałoby na przykład dziedziczenia po ustalonej klasie bazowej połączonego z kilkoma innymi wymaganiami.
  • Zliczanie referencji. Polega to na trzymaniu obok każdego obiektu licznika odwołań do tego właśnie obiektu. Każde kopiowanie i przypisywanie wskaźnika zmienia ten licznik i jeśli spadnie on do zera, obiekt kwalifikuje się do usunięcia. W C++ metodę tę można zaimplementować chociażby przy pomocy inteligentnych wskaźników.

W swoim pierwszym (działającym :)) ośmiecaczu dla C++ zastosowałem drugą metodę – oczywiście ze względu na jej prostotę. Jak wiadomo jednak nie jest ona doskonała, gdyż jej piętą achillesową są odwołania cykliczne. Można jej zaradzić na przykład poprzez tak zwane słabe referencje… Ale na szczęście póki co nie potrzebuję jeszcze takich “zakręconych” (dosłownie i przenośni) relacji między obiektami ;P

Tags:
Author: Xion, posted under Programming » Comments Off on Sprzątanie śmieci

Tablice bardzo dynamiczne

2007-11-15 10:32

W każdym poważnym języku programowania mamy do dyspozycji tablice o zmiennym rozmiarze, możliwym do ustalenia w czasie działania programu. Teoretycznie można by się bez nich obyć, jeżeli język posiada jakąś formę wskaźnika czy referencji, lecz konieczność ciągłego używania list na pewno nie byłaby przyjemna.
Z drugiej strony tablice mogą też być indeksowane więcej niż jednym indeksem, czyli być wielowymiarowe. Niekiedy wszystkie podtablice w danym wymiarze muszą mieć ten sam rozmiar (czyli całość być prostokątem, prostopadłościanem, itd.), ale np. C++ i C# pozwalają na dowolność i tworzenie chociażby macierzy trójkątnych zawierających tylko interesujące nas komórki.

To całkiem nieźle, lecz nie spotkałem jeszcze żadnego języka, który osiągnąłby zen w kwestii dynamicznych tablic, a mianowicie umożliwiał zmianę liczby wymiarów w trakcie działania programu. Być może powodem jest fakt, że w przypadku takich wybitnie elastycznych tablic nie da się już zapewnić dostępu do pojedynczego elementu w czasie stałym. Dla n wymiarów może on bowiem wynieść O(n2).
Jak więc można taką bardzo dynamiczną tablicę symulować? Ano trzeba samemu przeprowadzić jej linearyzację, czyli ponumerowanie wszystkich elementów tak, by można było obliczyć adres każdego w – liniowej przecież – pamięci operacyjnej. Przykładowo dla tablicy dwuwymiarowej element (x, y) będzie miał zlinearyzowany indeks równy zwykle x + y * width. Numerując z kolei trójwymiarową “kostkę”, otrzymalibyśmy formułę: x + y * width + z * height * width.

I tak dalej… W przypadku ogólnym aczkolwiek wzór może być trochę straszny :) Dla n-wymiarów o rozmiarach c1, …, cn, element opisany indeksami a1, …, an (liczonymi od zera) w wersji zlinearyzowanej znajdzie się na miejscu l:

Wzór na linearyzację tablicy wielowymiarowej

Formuła przekłada się oczywiście na dwie zagnieżdżone pętle – stąd więc jej oczekiwana złożoność. Można ją jednak łatwo zoptymalizować, przechowując wartość wewnętrznego iloczynu dla każdego z n wymiarów. Wtedy dostęp będzie już w czasie liniowym – oczywiście cały czas względem liczby wymiarów, a nie rozmiaru tablicy, więc nie jest aż tak źle :)
Taką dynamicznie wielowymiarową tablicę prawdopodobnie najłatwiej i najlepiej jest zaimplementować C++. I, co ciekawsze, nie będzie to wcale odkrywanie koła na nowo – czegoś takiego nie ma bowiem ani STL (daleko jej do tego), ani nawet boski boost ;]

Tags: ,
Author: Xion, posted under Programming » 3 comments

Mniejsze zło debugowania

2007-11-13 12:44

Banałem będzie stwierdzenie, że szukanie błędów w kodzie bywa wkurzające. Odpowiedź na proste pytanie – dlaczego coś nie działa? – to czasami długie godziny dłubania w programie, mało przyjemnych rendez-vous z debuggerem czy nawet stosowania bardziej drastycznych metod. Ale ponieważ w programowaniu nic nie dzieje się bez powodu (a przynajmniej chcemy w to wierzyć ;D) i przy założeniu, że dysponujemy odpowiednio dużymi zasobami: czasu, samozaparcia, a przede wszystkim umiejętności, w końcu uda się znaleźć tę upragnioną przyczynę błędu…

Bug :)A przyczyny mogą być trywialne. Pomyłka o jedynkę, nieopacznie wstawione x zamiast y, pomylenie plusa z minusem , i tak dalej. Takie błahostki zgodnie z prawem Murphy’ego mają wybitną skłonność do pojawiania się akurat w tych newralgicznych miejscach, które mają największy wpływ na działanie całego kodu – i oczywiście całkowicie je rozstrajają. A co gorsza, z bliżej niewiadomych przyczyn programistę uważnie oglądającego fragmenty z takimi “literówkami” ogarnia najczęściej chwilowa ślepota tudzież niewytłumaczalny zanik spostrzegawczości. Dopiero za n-tą inspekcją, przeprowadzoną najlepiej po długim odpoczynku od kodu, da się cokolwiek znaleźć.
Z drugiej strony poważne i trudne do znalezienia błędy mogą mieć poważne i trudne do usunięcia przyczyny. Inżynieria oprogramowania mówi, że im wcześniej w cyklu tworzenia programu błąd się pojawił, tym trudniej jest go potem wyeliminować. Jeżeli więc kruczek tkwił w założeniach projektowych, w modelu programu lub, co gorsza, w określeniu funkcjonalności, to nie będzie łatwo poradzić sobie z nim na etapie implementacji. Wyburzenie kilku ścian nie pomoże, jeśli fundamenty położono na niestabilnym gruncie.

Którego z tych dwóch rodzajów błędów oczekiwalibyśmy, jeżeli spędziliśmy już na debugowaniu dużo, naprawdę dużo czasu? Błąd drugiego typu to sprawa ciężkiego kalibru. Można wówczas powiedzieć, to oto odkryliśmy problem, który rzeczywiście jest adekwatny do tych godzin czy dni spędzonych na polowaniu na niego. Inaczej mówiąc, możemy uznać, że faktycznie zrobiliśmy wszystko, co w naszej mocy, i że cały ten wysiłek był naprawdę potrzebny, gdyż nie było innej drogi.
Z kolei pierwszy typ błędu to właściwie przeciwny biegun. Teoretycznie można było go załatwić w najwyżej kilkanaście minut, po prostu przeglądając jeszcze raz kod i dopisując ten zapomniany przecinek czy cokolwiek innego. Jak mogliśmy w ogóle spędzić nad tym tyle czasu, który przecież powinno się wykorzystać bardziej produktywnie?

Jeżeli kiedykolwiek ktoś odkryje przyczynę owej chwilowej ślepoty programistów na drobne omyłki, to osobiście uważam, że zasługuje przynajmniej na Ig Nobla :) Sądzę też jednak, że o wiele lepiej jednak paść jej ofiarą niż stwierdzić, że znaleziony błąd jest ową “ciężką sprawą”. Może i obniży to nieco naszą samoocenę, ale przynajmniej oszczędzi mnóstwa roboty.

Tags:
Author: Xion, posted under Programming, Thoughts » 7 comments

Wielokąty radarowe

2007-11-12 9:28

Dane liczbowe przedstawiać można na wiele sposobów. Najbardziej kompletnym jest zwykle tabelka, ale o wiele ładniejszą jest odpowiedni wykres. Czasem sztuką jest dobrać jego odpowiedni typ, gdyż rodzajów wykresów jest wbrew pozorom bardzo dużo. Jeżeli ktoś nie wierzy, niech sprawdzi w dowolnym arkuszu kalkulacyjnym :)

Radarowy wykres powierzchniowy w grze StepmaniaJednym z ciekawszych jest wykres radarowy. W nim ze środka wykresu na zewnątrz wypuszczone są osie (różna może być ich liczba), na których z kolei zaznaczone są wartości. W najprostszej wersji wygląda to jak pajęczyna z napaćkanymi punktami i w sumie nie jest specjalnie sugestywne.
Ciekawiej zaczyna się robić, jeżeli punkty na poszczególnych osiach połączymy ze sobą i zamalujemy wnętrze tak powstałego wielokąta. Jeżeli bowiem wartości na osiach przedstawiają pewne właściwości jednego obiektu lub zjawiska, to powstała figura niejako opisuje go w sposób całościowy. Weźmy na przykład taki wykres, w którym w subiektywny sposób ocenimy sobie różne charakterystyki jakiegoś hipotetycznego kawałka kodu źródłowego:

Radarowy wykres powierzchniowy cech kodu

Figura taka ma jeszcze jedną istotną cechę: powierzchnię. Na pierwszy rzut oka dość ciężko określić, w jaki sposób zależy od wartości na poszczególnych osiach. Czy na przykład gwałtowny wzrost jednej zmiennej przy identycznych wartościach pozostałych da ostatecznie większe pole wielokąta niż równomierny przyrost na wszystkich osiach?
Nie jest to oczywiste i dlatego wydaje się całkiem interesujące :) Naturalnie znając wszystkie wartości, rzeczone pole policzyć jest bardzo łatwo.

Dlaczego jednak wspominam o tym wszystkim? Otóż uważam, że gry w których przedstawia się graczowi bardzo dużo danych – a więc na przykład ekonomiczne, strategiczne czy RPG – są zwykle dość ubogie pod względem sposobów prezentacji tych danych. Prawie zawsze królują w nich nieśmiertelne tabelki i czasami tylko jakieś wykresy liniowe czy słupkowe.
A przecież można by nieco się wysilić i zafundować graczowi jakąś bardziej atrakcyjną formę. W końcu jeśli ktoś nie lubi odmóżdżających strzelanek to jeszcze nie znaczy, że uśmiecha mu się wpatrywanie się w rzędy numerków ;P

Tags: , ,
Author: Xion, posted under Games, Programming, Thoughts » 3 comments

ColorShop 2.2

2007-11-10 20:55

ColorShop 2.2Zgodnie z zapowiedzią, zamieszczam ukończoną kilka dni temu, nową wersję programu ColorShop. Nowości jest mnóstwo, cały program został oczywiście napisany od nowa (tym razem w C#) i naturalnie gorąco zachęcam do jego obejrzenia :) Powinien okazać się przydatny grafikom i webmasterom, ale także programistom grafiki.

File: ColorShop 2.2  ColorShop 2.2 (116.2 KiB, 3,338 downloads)

Tags:
Author: Xion, posted under Applications, Website » 14 comments
 


© 2018 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.