Archive for Programming

Nie tylko alpha blending

2009-03-18 10:31

Uaktywnienie łączenia alfa w DirectX na pierwszy rzut oka wydaje się dość skomplikowana. Niby występuje tam oczywiste ustawienie stanu renderowania D3DRS_ALPHABLENDENABLE na true, jednak to nie wszystko. Potem zwykle od razu występują przynajmniej dwa inne stany: D3DRS_SRCBLEND i D3DRS_DESTBLEND, ustawiane na równie tajemnicze wartości. Wyjaśnimy sobie dzisiaj, co one oznaczają i jak można je wykorzystać.

Należy zacząć od tego, że ten zagadkowy alpha blending to nic innego, jak zwykła suma ważona:

SourceBlend * SourceColor + DestBlend * DestColor

(z dokładnością do tego, że dodawanie można zastąpić innym działaniem przy pomocy D3DRS_BLENDOP, ale tę możliwość zostawimy w spokoju ;]). To, co jest tutaj sumowane, to dwa kolory: źródłowy – pochodzący od właśnie mającego się narysować piksela, oraz docelowy – będący już w danym miejscu bufora ramki (ekranu). Normalnie ten pierwszy zwyczajnie zastąpiłby ten drugi, ale dzięki łączeniu alfa można zamiast tego uzyskać jakąś kombinację ich obu – czyli na przykład symulację półprzezroczystości. Wagami dla sumy są SourceBlend i DestBlend, i to właśnie je ustawiamy przy pomocy stanów renderowania.

Możliwych wartości jest kilka i obejmują one zarówno tak proste jak zero czy jeden aż po same kolory: źródłowe i docelowe (podobnie jak one, współczynniki te są 4-elementowymi wektorami), wartości ich kanału alfa, specjalny globalny współczynnik blend factor – jak również negacje tych wszystkich wartości. Sporo tego, prawda? :) Zobaczmy więc kilka typowych kombinacji:

  • SourceBlend = SourceAlpha; DestBlend = InvSourceAlpha

    To najbardziej typowy sposób osiągania przezroczystości. Używamy tutaj źródłowej wartości alfa, by określić, jak bardzo kolor źródłowy ma wpływać na wynikowy oraz jak bardzo ma być pominięty wpływ koloru docelowego – że tak spróbuje się “intuicyjnie” wyrazić :) Ostatecznie mamy wtedy równanie typu:

    SourceAlpha * SourceColor + (1 – SourceAlpha) * DestColor

    czyli tzw. kombinację liniową obu kolorów, która w wyniku daje wrażenie półprzezroczystości.

  • SourceBlend = One; DestBlend = One

    Ustawienie obu wag na 1 sprawia, że nasza suma ważona stają się zwykłą sumą, więc kolory są po prostu dodawane. Taka konfiguracja jest stosowana na przykład do łączenia ze sobą efektów oświetlania sceny kilkoma różnymi światłami i nazywa się blendingiem addytywnym.

  • SourceBlend = DestColor; DestBlend = Zero

    Takie dziwne ustawienie wag sprawia z kolei, że zamiast dodawania otrzymujemy w istocie mnożenie przez siebie kolorów – czyli blending multiplikatywny. Istnieje oczywiście jeszcze jedna konfiguracja współczynników dająca ten sam efekt, która jest symetryczna do powyższej.

Powyższe warianty nie są naturalnie wszystkimi możliwymi ani nawet wszystkimi praktycznie wykorzystywanymi. Widać z nich jednak, że tak zwany alpha blending nie służy tylko do przezroczystości i nierzadko wykorzystujemy go również wtedy, gdy wszystkie obiekty naszej sceny nie są ani trochę prześwitujące.

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

Kwantowanie kierunku

2009-03-13 17:20

Wszyscy wiedzą jak, mając dane dwa punkty, wyznaczyć wektor kierunkowy od pierwszego punktu do drugiego. Niekiedy jednak nie chcemy, aby możliwe było uzyskanie dowolnego kierunku. Może tak być np. przy poruszaniu jednostkami na mapie, gdy z jakiegoś powodu chcemy dopuścić, powiedzmy, tylko 8 czy 16 podstawowych kierunków. W jaki sposób należy wtedy “zaokrąglić” nasz dowolny wektor, uzyskany jako różnica aktualnej pozycji jednostki i np. miejsca kliknięcia myszką przez gracza?

Pierwszym możliwym sposobem jest zamiana jego reprezentacji ze współrzędnych prostokątnych (x, y) na biegunowe (r – długość, theta – kąt między dodatnią półosią X a wektorem). Jest to możliwe przy pomocy obecnej w wielu językach funkcji atan2(y, x). Wystarczy potem sprawdzić, któremu wzorcowemu wektorowi jest najbliższy otrzymany kąt.

Swego czasu znalazłem jednak nieco inny sposób, który daje się zastosować bez zmiany reprezentacji wektora. Oryginalnie służył on do wyboru jednego z ośmiu podstawowych kierunków, ale nietrudno było zauważyć, że da się go trochę uogólnić:

  1. VEC2 Quantize(const VEC2 v, int k)
  2. {
  3.     v.Normalize();
  4.     v *= k;
  5.     return VEC2((int)Round(v.x), (int)Round(v.y));
  6. }

Użyta tutaj funkcja Round(t) oznacza zaokrąglenie w stronę najbliższej liczby całkowitej, czyli floor(t + 0.5). Współczynnik k kontroluje natomiast, ile wektorów wzorcowych znajduje się w naszej “róży wiatrów”. Powyższa funkcja dzieli bowiem kąt pełny na dokładnie 2k+2 wycinków, dając tyle też możliwych wektorów wynikowych. Osiem kierunków otrzymamy więc dla k = 1, szesnaście dla k = 2, itd. Teoretycznie możliwe są też ułamkowe wartości współczynnika, co najprawdopodobniej pozwałoby kontrolować “czułość dopasowania” wektora do wzorca. Nie podjąłem się jednak opracowania jakiejś ścisłej zależności :) Jedyne co udało mi się zaobserwować to to, że dla k = 2/3 otrzymujemy dopasowanie do czterech podstawowych kierunków (N, S, W, E).
Ogólnie więc nie jest to może epokowe odkrycie w dziedzinie wektorologii stosowanej, ale istnieje szansa, że komuś do czegoś się przyda ;]

Tags: , ,
Author: Xion, posted under Programming » Comments Off on Kwantowanie kierunku

volatile?…

2009-02-23 13:18

Modyfikator volatile nie należy do często używanych elementów języka C(++). Jeśli więc gdzieś się go napotka, ma się sporą szansę nie odgadnąć od razu, dlaczego został użyty. Można też samemu przeoczyć sytuacje, gdy należałoby z niego korzystać.
Teoretycznie to słowo kluczowe nie powinno w ogóle istnieć; jest ono “techniczną” częścią języka, związaną ze sposobem jego kompilacji – trochę tak, jak klauzula checked z C# jest ściśle związana z metodami wykonywania obliczeń przez (ko)procesor. Wiemy jednak doskonale, że C++ wysokim poziomem abstrakcji nie grzeszy (już o C nie wspominając), więc obecność takich elementów nie powinna specjalnie dziwić.

volatile jako modyfikator zastosowany do (typu) zmiennej sprawia, że będzie ona traktowana tak, jakby jej zawartość mogła się w każdej chwili zmienić. Inaczej mówiąc, kompilator nie powinien nigdy czynić jakichkolwiek założeń co do wartości takiej zmiennej, bo jej wartość może być w dowolnym momencie przez coś zmodyfikowana.
Tak to wygląda od strony specyfikacji. W praktyce volatile stosuje się głównie w dwóch przypadkach:

  • Po pierwsze, używamy tego słowa jeśli rzeczywiście wartość naszej zmiennej może być zmodyfikowana przez jakiś ‘czynnik zewnętrzny’. Na niektórych maszynach tak na przykład działają urządzenia wejściowe: akcja w rodzaju wciśnięcia klawisza przez użytkownika powoduje zmianę zawartości jakiejś komórki pamięci. Chcąc na nią zareagować, należy więc cały czas monitorować to miejsce, bo może ono zmienić swoją zawartość zupełnie niespodziewanie. Oczywiście teraz takich rozwiązań się już nie stosuje, bo urządzenia wejściowe generują po prostu przerwania (interrupts), które są potem przerabiane przez system operacyjny na odpowiednie zdarzenia.
    Z globalnymi zmiennymi volatile można jednak często się spotkać w programach uniksowych, które funkcjonują w oparciu o sygnały. Typowym przykładem są serwery sieciowe, działające w pętli aż do momentu, gdy im się przerwie:

    1. while (!interrupted) do_work();

    Zmienna z warunku jest wtedy deklarowana jako:

    1. volatile sig_atomic_t interrupted = 0;

    zaś w procedurze obsługi sygnału – która może być wywołana w dowolnym momencie w odpowiedzi na przyjście żądanego sygnału (zwykle SIGINT) – jest ona ustawiana na 1. Gdyby nie była volatile, kompilator uznałby, że zawsze ma ona wartość zerową i “zoptymalizował” powyższą pętlę, zamieniając ją na nieskończoną.

  • Po drugie, z volatile korzysta się wtedy, chcemy w sposób zamierzony zapobiec pewnym optymalizacjom kodu. Zwykle chodzi tutaj o jakieś testowanie szybkości pewnych operacji, np. arytmetycznych. Powinno się wtedy wykonywać je na zmiennych opatrzonych modyfikatorem volatile, żeby mieć pewność, że wszystkie działania się wykonają i żadne nie zostanie wyeliminowane w procesie kompilacji. Można oczywiście wątpić w zdolności optymalizacyjne kompilatora, ale jest całkiem możliwe, że – zgodnie ze sprawdzonym po wielokroć prawem Murphy’ego – włączą się one właśnie tam, gdzie akurat byśmy ich sobie nie życzyli :)

Jeśli więc któryś z tych dwóch powyższych przypadków pasuje do naszej sytuacji, zapewne powinniśmy posłużyć się słowem kluczowym volatile.

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

Nawet SQL ma pętle

2009-01-12 12:35

Stwierdzenie ‘programować w HTML’ jest rzecz jasna nadużyciem, ale istnieją przecież inne języki, dla których określenie ‘programistyczne’ (lub jego brak) nie jest wcale takie oczywiste. Weźmy choćby SQL, teoretycznie pretendujący do miana języków deklaratywnych. Charakteryzują się one tym, że pisząc w nich określamy tylko to, co ma zostać zrobione – nie zaś jak. Na pierwszy rzut oka ma to sens: w końcu pisząc proste lub nawet całkiem skomplikowane zapytanie SELECT w ogóle nas nie interesuje to, przy pomocy jakich struktur danych zostanie ono wykonane i jaka pętla będzie się za nim kryć.
Bo przecież SQL nie ma pętli, prawda? :)

Ano właśnie nieprawda. Ponadto czasami są one jedynym wyjściem, jeśli mamy do czynienia z nieco bardziej skomplikowanymi danymi – jak choćby z jakąś hierarchią drzewiastą. Zwykle zapisuje się ją w relacyjnej bazie danych tak, że każdy element zawiera informacje o identyfikatorze elementu do niego nadrzędnego. Jest to całkowicie wystarczającą informacją do odtworzenia ich hierarchii.
Do takiego drzewka łatwo dodawać nowego elementy, ale ich usuwanie może być już problemem. Wyrzucenie jednej pozycji powinno bowiem oznaczać odcięcie całego poddrzewa – zwłaszcza że na pozostawienie osieroconych potomków często nie pozwoli sam silnik bazy danych, jeśli sprawdza poprawność relacji. Musimy zatem usuwać od dołu, a następnie przesuwać się w górę… Tylko jak niby zapisać to w postaci zapytania SQL?
Okazuje się, że nic prostszego. No, a przynajmniej okazuje się, że da się to zrobić:

  1. CREATE PROCEDURE DeleteItem
  2.     @ID int
  3. AS
  4. BEGIN
  5.     DECLARE @cur CURSOR
  6.     DECLARE @ChildID int
  7.    
  8.     SET @cur = CURSOR FOR (SELECT ID FROM Items WHERE ParentID = @ID)
  9.     OPEN @cur
  10.     FETCH NEXT FROM @cur INTO @ChildID
  11.     WHILE @@FETCH_STATUS = 0
  12.     BEGIN
  13.         EXECUTE DeleteItem @ChildID
  14.         FETCH NEXT FROM @cur INTO @ChildID
  15.     END
  16.    
  17.     DELETE FROM Items WHERE ID = @ID
  18. END

Nawet bez specjalnej znajomości składni można się domyślić, co tutaj jest wykonywane. Oto używamy kursora (coś w stylu iteratora), żeby najpierw usunąć elementy podrzędne do tego, który zamierzamy wykasować. W tym celu dla każdego z nich wywołujemy po prostu tę samą procedurę. Na koniec dokonujemy usunięcia pierwotnego elementu, który teraz na pewno jest już liściem (nie ma żadnych potomków), więc może być wyrzucony bez przeszkód.

Całkiem proste, czyż nie? Można powiedzieć, że w każdym języku programowania algorytm ten wyglądałby podobnie… Sęk w tym, że tu właśnie tkwi problem. Bo skoro w rzekomo deklaratywnym języku SQL można (a w tej sytuacji nawet trzeba) używać takich narzędzi jak pętle czy rekurencja, to przecież nie różni się on wtedy niczym od “normalnych” języków programowania. Jeśli całą operację trzeba zakodować krok po kroku, to nie mamy już żadnej korzyści z filozofii polegającej na określaniu ‘co’, a nie ‘jak’.
Może więc znaczy to, że inaczej programować po prostu się nie da? :)

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

Rok++ i co z tego wynika

2009-01-03 23:39

Jak trudno było nie zauważyć, przedwczoraj rozpoczął się kolejny rok kalendarzowy. Jeśli patrzeć na sam jego numer, to nie zapowiada się on nadzwyczajnie. 2009 nie jest bowiem żadną okrągła liczbą – i to nie tylko w naszym powszechnie używanym systemie dziesiętnym, ale też i w innych: szesnastkowym (7D9), czy ósemkowym (3731). Nawet wersja binarna (11111011001) nie prezentuje żadnego szczególnego ułożenia cyfr. A dodatkowo 2009 nie jest “nawet” liczbą pierwszą (rozkłada się na 7 * 7 * 41).
Jednym słowem, jest to liczba zupełnie nieciekawa, więc opatrzony nią rok też pewnie ma duże szanse być absolutnie przeciętny…

Jednak jest coś, co może to zmienić. Coś co musi wydarzyć się w tym właśnie roku. Dokładnie tak, musi – gdyż w przeciwnym wypadku nie wydarzy się wcale. Jest to przy tym coś wyjątkowo pożądanego i bardzo długo oczekiwanego…
Cóż to takiego? Ano oczywiście opublikowanie standardu C++0x :) To przecież ostatnia chwila, aby mógł on wystąpić pod tą nazwą. Zważywszy, że kiedyś oczekiwano, iż ‘x’ zostanie zastąpione raczej przez ‘2’ lub ‘3’, można powiedzieć z całą mocą: najwyższy czas :D


Author: Xion, posted under Life, Programming » 8 comments

Funkcje zagnieżdżone i C++

2008-12-30 20:19

Niekiedy przydatna okazuje się możliwość definiowania funkcji widocznych wyłącznie w obrębie innej funkcji – czyli procedur zagnieżdżonych. Używa się tego najczęściej do krótkich, pomocniczych funkcji; oto najprostszy przykład w języku, który to umożliwia (Delphi):
[delphi]// oblicza odległość między dwoma punktami
function Distance(p1, p2 : TPoint) : Double;
function Square(X : Double) : Double;
begin
Result := X * X;
end;
begin
Result := Sqrt(Square(p1.X – p2.X) + Square(p1.Y – p2.Y));
end;[/delphi]
Takim językiem nie jest jednak C++, więc pewnie istnieje ku temu jakiś bardzo ważny powód… Bo czyż nie jest tak z każdą przydatną funkcjonalnością, która została w nim pominięta? ;D
Ale żarty na bok. W C++ można – przy odrobinie pomysłowości – osiągnąć dość podobny efekt:

  1. double Distance(POINT p1, POINT p2)
  2. {
  3.     static class
  4.     {
  5.         public:
  6.             double operator() (double x) const { return x * x; }
  7.     } Square;
  8.  
  9.     return sqrt(Square(p1.X - p2.X) + Square(p1.Y - p2.Y));
  10. }

Nie tworzymy tutaj funkcji, tylko odpowiednio nazwany obiekt anonimowej klasy, któremu przeciążamy operator nawiasów (wywołania funkcji). Efekt na oko jest taki sam: mamy pewną nazwę (Square), którą możemy użyć jak funkcję, lecz nie jest ona widoczna poza macierzystą procedurą (czyli Distance). Nasz obiekt deklarujemy też jako statyczny, dzięki koszt jego tworzenia i niszczenia ponosimy tylko raz, a ponadto nie zajmuje on miejsca na stosie (gdyż w innym przypadku z pewnością zająłby je; standard C++ mówi, że nawet obiekty klas bez zadeklarowanych pól nie mają rozmiaru 0).

Ta sztuczka jest jednak daleka od rzeczywistych funkcji zagnieżdżonych. W “prawdziwym” wydaniu mają one bowiem jedną ważną właściwość: posiadają dostęp do zmiennych lokalnych funkcji, w których są zawarte. W naszym przykładzie “funkcja” Square powinna więc móc odwołać się do (ewentualnych) zmiennych lokalnych z funkcji Distance. A ponieważ Square jest tutaj tak naprawdę obiektem jakiejś klasy, która nic nie wie o Distance, nie jest to rzecz jasna możliwe.
Czy możliwe jest więc, aby pełnowymiarowe funkcje zagnieżdżone pojawiły się np. w przyszłych wersjach języka C++?… Tutaj odpowiedź jest prawie na pewno negatywna. Jest tak dlatego, że obecność takich funkcji ingeruje bardzo głęboko w sposób, w jaki kompilator postępuje ze wszystkimi funkcjami. Pośrednimi konsekwencjami dodania funkcji zagnieżdżonych byłyby: niemożność korzystania ze standardowej konwencji wywoływania cdecl oraz zmiana wewnętrznej struktury wszystkich wskaźników na funkcje (które nie mogłyby być już pojedynczymi adresami).

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

Znów o testach jednostkowych

2008-12-18 21:04

Poprzednia notka o “rootkitach i innych nieszczęściach” zdołała utrzymać się długo, więc mogła stworzyć wrażenie, że cały czas źle się u mnie dzieje :) Nieprawda to oczywiście, więc wypadałoby w końcu coś na tę dezinformację poradzić.
Ostatnio cierpię na niewielki brak czasu spowodowany koniecznością dokładania nieco poważniejszych wysiłków co do pewnego dzieła, które docelowo ma zapewnić mi otrzymanie tytułu inżyniera informatyki. Z pewnych względów nie zdradzę, czym ono jest, ale pozwolę sobie wspomnieć o pewnych wnioskach, które przy okazji mi się nasunęły.

Parę miesięcy temu wypowiadałem się pochlebnie na temat testów jednostkowych, mając wtedy raczej niezbyt duże doświadczenie w ich stosowaniu. Dzisiaj jest już ono zdecydowanie większe i w związku z tym stwierdzić muszę, że… Nie, nie chcę powiedzieć, że wtedy myliłem się całkowicie ;P Chodzi raczej o równowagę zalet i wad.
To prawda, że unittesty dobrze sprawdzają się jako narzędzie znajdowania błędów i zapobiegania im. Do pewnego stopnia pomagają też w poprawianiu interfejsu tworzonych klas, tak aby ich użycie było wygodniejsze i bardziej intuicyjne. Te korzyści mają jednak swoją cenę, którą jest przede wszystkim czas poświęcony na pisanie owych testów – zwłaszcza w niektórych metodykach wytwarzania oprogramowania, które kładą na nie ogromny nacisk. Całkiem normalna jest bowiem sytuacja, że kod testowy jest dłuższy niż testowany (czasem nawet kilkakrotnie). Dodatkowo nie mamy przecież znikąd żadnej gwarancji, że ów testowy kod sam nie zawiera jakichś błędów… W sumie więc dochodzi nam sporo dodatkowej pracy w zamian za większą niezawodność tworzonego oprogramowania.
Drugi wniosek jest bardziej – że tak powiem – filozoficzny :) Otóż programowanie wedle zasady:

  1. while (!ProgramGotowy())
  2. {
  3.     NapiszTest();
  4.     do
  5.     {
  6.          NapiszLubPoprawKod();
  7.          UruchomTest();
  8.     } while (!TestPrzeszedl());
  9. }

może i jest efektywne, ale na dłuższą metę zaczyna się robić nużące i trochę zniechęcające. Pomyślmy jak łatwo jest pisać kod “rozgrzebany”, którego nie planujemy od razu kompilować i poprawiać tych wszystkich pomyłek, których kompilator nam zasygnalizuje. Porównajmy to z pisaniem kodu, który nie tylko jak najczęściej kompilujemy, ale i regularnie przepuszczamy przez własnoręcznie napisane testy! Toż to straszne, tak samemu kręcić na siebie bat :) Gdzie tu koderska wolność artystyczna? :D
Ale nie ma rady, czasami trzeba zakasać rękawy i testować…

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


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