Monthly archive for April, 2008

Jak nie należy używać operatorów

2008-04-30 22:23

W wielu API funkcje mają bardzo prosty sposób powiadamiania o tym, czy ich wykonanie zakończyło się sukcesem czy porażką. Albo więc wykorzystują typ bool bezpośrednio, albo wpasowują się w konwencję, iż niezerowa wartość liczbowa jest tożsama z prawdą, a zero z fałszem. To sprawia, że możliwe jest pisanie warunków podobnych do poniższego:

  1. if (!RegisterClassEx(&wc))    Error("Can't register window class.");

Ładne to i opisowe – wręcz samodokumentujące się. Ale czasami tak się zrobić nie da, bo wartości zwracane nie chcą współpracować z tym modelem.

Przykład? To większość biblioteki runtime języka C oraz API systemów uniksowych. O ile tylko rezultatem funkcji należącej do któregoś z tych dwóch zbiorów nie jest wskaźnik, konwencja informowania o powodzeniu lub niepowodzeniu jest zwykle dość osobliwa. Według niej zero oznacza sukces, natomiast porażka wykonania jest sygnalizowana przez wartość mniejszą od zera – zazwyczaj -1. Oczywiście nijak nie pasuje to sposobu interpretowania liczb jako wartości logicznych. Sprawia to, że sprawdzanie rezultatu takich funkcji może wyglądać cokolwiek enigmatycznie:

  1. if (close(fd) < 0)    perror("closing file");&#91;/cpp]
  2. Ale nie wszystko stracone :) W przypadku funkcji typu boolowskiego możemy posłużyć się operatorem logicznej negacji (<code>!</code>), dzięki czemu zawierające je <code>if</code>y są całkiem przejrzyste. Okazuje się, że z powodu pewnego zbiegu okoliczności także te wspomniane przed chwilą funkcje można potraktować tak samo... o ile dodamy jeszcze jeden operator. A dokładniej - jeśli oprócz negacji logicznej dodamy też bitową (<code>~</code>):
  3. [cpp]if (!~close(fd))    perror("closing file");

Powód, dla którego to działa, jest dość prosty. W standardowym sposobie zapisu liczb całkowitych, stosowanym na zdecydowanej większości typowych i nietypowych maszyn (zwanym uzupełnieniem do 2 – U2), wartość -1 to w zapisie binarnym same jedynki. Negując je bitowo, otrzymujemy same zera – czyli zero, a więc logiczny fałsz. A odwrotnością fałszu jest oczywiście prawda i wszystko działa poprawnie. Wygląda więc tak, jakby skromna tylda zdołała “naprawić” funkcję, by zachowywała się zgodnie z oczekiwaniami…

Tylko czy aby na pewno nowy zapis jest bardziej sugestywny? Mam nadzieję, że każdy potrafi poprawnie odpowiedzieć na to pytanie we własnym zakresie :) Na koniec jednak muszę – dla spokoju sumienia – ostrzec wszystkich: zdecydowanie nie róbcie tego w domu :D

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

Podział wielokątów na trójkąty

2008-04-27 21:39

Podział wypukłego wielokąta na trójkątyKolega rr- rzucił dzisiaj na kanale #warsztat ciekawy problem rysowania dowolnych wielokątów za pomocą samych trójkątów. Jak wiadomo, karty graficzne posługują się właśnie trójkątami, zatem w celu wyświetlenia wielokąta należy go odpowiednio podzielić. Matematycy dowodzą, że jest to zawsze możliwe, i podają prosty sposób dla wielokątów wypukłych: należy po prostu narysować wszystkie przekątne wychodzące z jednego wierzchołka. Nie jest trudno przełożyć ten przepis na kod.

Co jednak z dowolnymi wielokątami? Tu sprawa wydaje się bardziej skomplikowana, chociaż – jak się ukazuje – rysowanie przekątnych można na ten przypadek uogólnić. Wpadłem jednak na inny pomysł, polegający na odpowiednim “chodzeniu” po wierzchołkach naszego wielokąta i “odcinaniu” od niego kolejnych trójkątów brzegowych. Wygląda to mniej więcej tak:

  1. Startujemy od dowolnego wierzchołka wielokąta.
  2. Mając i-ty wierzchołek sprawdzamy, czy da się go połączyć z (i+2)-im (modulo liczba wierzchołków) tak, aby powstały przy tym odcinek mieścił się w wielokącie:
    • jeśli tak, to z wierzchołków: i-tego, (i+1)-ego i (i+2)-ego tworzymy nowy trójkąt, wierzchołek (i+1)-szy usuwamy z wielokąta i przechodzimy do (i+2)-ego
    • jeśli nie da się tak połączyć wierzchołków, przechodzimy do wierzchołka (i+1)-ego i próbujemy dalej
  3. Po wykonaniu pełnego cyklu kontynuujemy przechodzenie po wielokącie, usuwanie wierzchołków i tworzenie trójkątów – aż do momentu, gdy sam nasz wielokąt stanie się trójkątem. Będzie to oczywiście ostatni składający się na niego trójkąt.

Na tym rysunku można prześledzić, jak wyglądają kolejne cykle spaceru po krawędziach wielokąta – oznaczyłem je różnymi kolorami:

Podział dowolnego wielokąta na trójkąty

Z tym sposobem wiąże się oczywiście problem stwierdzenia, czy dany odcinek należy do wielokąta – co w ogólności nie musi być takie proste ani efektywne (może mieć złożoność liniową). Dodatkowo wielokąt może być “wredny” i niezbyt dobrze poddawać się operacji obcinania trójkątów. Na szczęście można udowodnić, że w każdym cyklu da się przynajmniej jeden taki trójkąt wyodrębnić. Te dwa fakty powodują, że cała operacja może mieć złożoność sięgającą nawet O(n3), chociaż pewnie da się ją zaimplementować lepiej.
Jest naturalnie bardzo możliwe, że algorytm ten jest znany od dawna, a ja po prostu nie przeczesałem Internetu dość dokładnie w poszukiwaniu już istniejącego opisu. Jednak biorąc pod uwagę to, co przed chwilą powiedziałem o jego możliwej “efektywności”, nie jest to znów takie pewne ;-) Istnieje aczkolwiek szansa, że może się on przydać komuś, kto implementuje bibliotekę graficzną 2D w oparciu o API w rodzaju DirectX czy OpenGL.

Czym jest NULL?

2008-04-24 21:42

Gdybym chciał byś złośliwy, to stwierdziłbym, że w C++ nawet ‘nic’ (czyli NULL) nie jest takie, jak być powinno. Ale ponieważ w rzeczywistości jestem wcieleniem łagodności (;]), napiszę raczej o tym, jak można zaradzić na niedogodności obecnej postaci wskaźnika pustego w C++.
Cały problem z NULL-em polega na tym, że nie jest on wartością odpowiedniego typu. Dwie klasyczne definicje tej stałej – jako 0 lub (void*)0 – mają zauważalne mankamenty. Pierwsza definiuje NULL jako liczbę, co sprawia, że dozwolone są bezsensowne podstawienia w rodzaju:

  1. int n = NULL;

Natomiast druga nie da się wprawdzie skonwertować na typ liczbowy, ale nie da się też niejawnie zmienić w wartość żadnego innego typu wskaźnikowego niż void*. A tego oczekiwalibyśmy po wskaźniku pustym. Dlatego z dwojga złego w standardzie przyjęto pierwszą definicję i NULL jest po prostu zerem.

To, czego naprawdę byśmy chcieli po NULL, to wartość 0, która:

  • może być podstawiona za dowolny typ wskaźnikowy
  • nie może być podstawiona za żaden inny typ, zwłaszcza liczbowy

To zaś da się osiągnąć, pisząc odpowiednią… klasę:

  1. #undef NULL
  2. const
  3.     class Null
  4.     {
  5.         public:
  6.             // konwersja na dowolny typ wskaźnikowy (także pointer-to-member)
  7.             template <typename T> operator T* () const { return 0; }
  8.             template <class C, typename T> operator T C::*() { return 0; }
  9.         private:
  10.             // zablokowanie pobierania adresu
  11.             void operator & () const;
  12.     }
  13. NULL;

Sztuczką są tu oczywiście szablony operatorów konwersji. Zapewniają one możliwość traktowania naszego NULL-a jako wartości dowolnego typu wskaźnikowego – łącznie ze wskaźnikami do składowych klas. A ze względu na brak innych konwersji, nie jest możliwe automatycznie przypisanie naszego pustego wskaźnika do zmiennej liczbowej.

Taki NULL jest na tyle dobry, że działa nawet z uchwytami Windows API, gdyż wewnętrznie są one zdefiniowane jako specyficzne wskaźniki. Dziwi więc, dlaczego nadal nie ma go chociażby w bibliotece standardowej C++. Najwyraźniej nawet jeśli chcemy mieć ‘nic’, trzeba się trochę napracować ;P

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

Fragmenty a piksele

2008-04-22 22:25

W terminologii DirectX programowalny potok graficzny ma dwie ważne części: vertex shader i pixel shader. Nazwa tej drugiej jest zasadniczo trochę myląca. Sugeruje ona, że shader jest wykonywany dla każdego piksela na ekranie, co tak naprawdę jest dalekie od prawdy.
Tak naprawdę bowiem “piksele” te są dopiero kandydatami do zapisania w buforze tylnym. Po drodze mają bowiem wiele okazji na to, aby być całkowicie wyeliminowane z renderingu. Może to się stać z któregoś z poniższych powodów, które jednak nie wyczerpują wszystkich możliwości:

  • Test alfa. W przypadku włączenia tego rodzaju testu, możliwe jest odrzucenie “pikseli”, których wartość kanału alfa nie jest dostatecznie duża. Zwykle jako wartość porównawczą wykorzystuje się 127, 128 albo domyślnie 0. Nie zawsze można sobie oczywiście pozwolić na takie skwantowanie informacji o przezroczystości, ale ma ono niebagatelną przewagę wydajnością nad alpha-blendingiem.
  • Test głębi. To najbardziej oczywisty test, a związany jest z przesłanianiem obiektów. W wielu przypadkach możliwe jest wykonanie go przed pixel shaderem, lecz w określonych sytuacjach może być konieczne testowanie już przetworzonych “pikseli”. W zależności od powodzenia testu wartość głębi zapisana w buforze może być oczywiście uaktualniona, co wpływa na dalsze testy.
  • Test stencila. Test wykorzystujący stencil buffer jest sprzężony z testem głębi, wobec czego podlega podobnym ograniczeniom. W szczególności możliwe jest na przykład zapisanie innej wartości do wspomnianego bufora w zależności od tego, czy “piksel” wyłoży się na teście głębi czy stencila.

A zatem wyjście pixel shadera niekoniecznie musi bezpośrednio trafić na ekran. Nie powinniśmy więc brać liczby pikseli w buforze ekranu za średnią liczbę wywołań tego shadera, a już na pewno nie jako górną granicę.
Dlatego też trzeba przyznać, że używana w OpenGL nazwa ‘fragment program‘ jest o wiele lepsza niż ‘pixel shader’. Fragment (wyjście shadera) nie jest bowiem jeszcze pikselem, a jedynie kandydatem na niego, który może odpaść przy wielu okazjach.

Tags: , , , ,
Author: Xion, posted under Programming » 1 comment

Pomijanie klawiszy w C#

2008-04-21 19:50

Czasami dobrze jest reagować na wszystkie przychodzące do okna wciśnięcia klawiszy w jednym miejscu. W C# ustawia się wtedy właściwość KeyPreview dla formy. Sprawia to, że dostaje ona zdarzenia klawiatury niezależnie od tego, która z potomnych kontrolek ma aktualnie fokus. Dzięki temu można implementować polecenia aktywowane wciśnięciami określonych klawiszy lub ich kombinacji, których nie da się przypisać np. do skrótów klawiszowych w menu:

  1. private void MainForm_KeyDown(object sender, KeyEventArgs e)
  2. {
  3.     switch (e.KeyCode)
  4.     {
  5.         case Keys.Oemtile:
  6.             // tylda - pokaż/ukryj konsolkę
  7.             txtConsole.Visible = !txtConsole.Visible;
  8.             break;
  9.     }
  10. }

Jeśli jednak nic w tej kwestii nie zrobimy, zdarzenia klawiatury domyślnie i trafią do kontrolki aktywnej, co niekoniecznie musi nam się podobać. W powyższym przykładzie nasza prosta konsolka “złapałaby” na przykład wszystkie wciśnięcia klawisza tyldy jako znaki ~.
Jak temu zapobiec? Wystarczy wykorzystać właściwość SuppressKeyPress z klasy KeyEventArgs:

  1. e.SuppressKeyPress = true;

To sprawi, że zdarzenie wciśnięcia klawisza nie będzie przekazywane dalej i żadna kontrolka go nie otrzyma. To przydatne, jeśli mamy ręcznie zakodowane skróty klawiszowe, które pokrywają się ze standardowymi sekwencjami.

Tags:
Author: Xion, posted under Programming » Comments Off on Pomijanie klawiszy w C#

Nadmierne aspiracje

2008-04-19 16:54

Wygasła już chyba dyskusja w wątku na forum Warsztatu, w którym zwrócono uwagę na poziom pojawiających się w serwisie gamedev.pl projektów. Dotyczyło to zwłaszcza screenów, jakie to można niekiedy rotacyjne oglądać na stronie głównej. Dość często podnoszonym argumentem było to, iż marny ich poziom szkodzi wizerunkowi Warsztatu na zewnątrz. Proponowane przy okazji rozwiązania wahały się zwykle w przedziale między całkowitym usunięciem wszystkim tetrisów, pongów, projektów konsolowych i innych subiektywnie ocenianych “zaniżaczy poziomu”, a wysłaniem ich do specjalnie przygotowanego działu (nazywanego np. ‘żłobkiem’), z którego screeny nie wystawałaby na widoku publicznym na stronie głównej serwisu.

Screen z gry Game Producer
I konsolówki bywają niezłe
(Game Producer)

Troska o ów poziom Warsztatu jest doprawdy rozczulająca. Zastanawiam się tylko, jaka stoi za nią motywacja? Może to być chęć, by serwis oraz społeczność były postrzegane na zewnątrz jako bardziej profesjonalne (niż w rzeczywistości, chciałoby się dodać). Obecność screenów, które niekoniecznie powalają oglądających na kolana, ma w tym oczywiście przeszkadzać.
A ja pytam: jaki jest w tym cel oraz sens? Po pierwsze, na tle innych podobnych serwisów, Warsztat nie ma się czego wstydzić (dla porównania można obejrzeć jego odpowiedniki z innych krajów). Zaś po drugie, aspirowanie do “bardziej profesjonalnej” roli w przypadku serwisu nieanglojęzycznego nie ma większego sensu. W przeliczeniu na nadal skromny przemysł gier komputerowych w Polsce (jeden Wiedźmin wiosny nie czyni), obecna postać i poziom Warsztatu – zwłaszcza społeczności – są chyba nawet lekką nadwyżką.

Screen z techdema INQ
Screen, o którego poziom
nie trzeba się martwić :)
(INQ-Techdemo)

A mimo to zdaje się, że cierpimy od jakiegoś czasu na kompleks rozpaczliwego udowadniania światu, iż Warsztat to serwis jak najbardziej poważny i – powtórzmy jeszcze raz to kluczowe słowo – profesjonalny.
Otóż nie, to nieprawda i stanowczo przeciwko temu protestuję! Warsztat zawsze był i będzie serwisem i społecznością skupiającą amatorskich oraz zawodowych programistów gier – w tej właśnie kolejności. Wszelkie próby zmiany tego stanu rzeczy, polegające na składaniu różnorodności i walorów edukacyjnych Warsztatu na ołtarzu utrzymania ‘poziomu’ i poprawiania ‘wizerunku’ na pewno nie mogą skończyć się dobrze.

Tags:
Author: Xion, posted under Thoughts » 4 comments

Być albo nie być

2008-04-18 20:08

W programowaniu relacja ‘jest’ najczęściej oznacza możliwość potraktowania pewnej wartości (lub ogólniej: obiektu) jako należącego do określonego typu (klasy). Od kiedy wynaleziono dziedziczenie, obiekty mogą być polimorficzne – czyli być traktowane tak, jakby należały do kilku różnych typów danych. Dwa proste przypadki obejmują: zwykłe dziedziczenie publiczne, gdy obiekt klasy pochodnej jest też obiektem klasy bazowej, oraz implementowanie abstrakcyjnych interfejsów.

Czasami jednak to, co w związku ze słówkiem ‘jest’ bywa intuicyjne, nie zawsze sprawdza się w praktyce. Tak jest chociażby wtedy, gdy bierzemy pod uwagę:

  • Dziedziczenie prywatne. Ten rzadko spotykany typ dziedziczenia (obecny w C++) sprawia, że choć obiekt klasy pochodnej jest nadal obiektem klasy bazowej, to wie o tym tylko on sam. Dlatego nie jest możliwe bezproblemowe rzutowanie w górę, które dla dziedziczenia publicznego jest przeprowadzane automatycznie. Mimo tego nadal mamy do czynienia z normalnym dziedziczeniem i jeśli przy użyciu jakichś brzydkich sztuczek (czyli na przykład reinterpret_cast) skonwertujemy odwołanie do obiektu na odwołanie do klasy bazowej, będziemy mogli z niego poprawnie skorzystać.
  • Kolekcje obiektów.Teoretycznie zbiór obiektów typu B jest też zbiorem obiektów typu A, jeśli typ B jest rodzajem typu A (np. klasą pochodną). W praktyce jednak kolekcja może się zmieniać, a przy traktowaniu jej w sposób bardziej ogólny istnieje możliwość dodania do niej obiektów będących wprawdzie typu A, ale nie mających nic wspólnego z B.
    Stąd też wynika fakt, że w językach programowania nie można ot tak sobie rzutować pojemników na takie, które przechowują “bardziej ogólne” obiekty. Jeśli więc chcemy zmienić np. List<string> na List<object> w C#, musimy świadomie wykonać kopię pojemnika.
  • Niewirtualne wielodziedziczenie. W bardziej skomplikowanych przypadkach, gdy klasa ma więcej niż jedną klasę bazową, mogą się pojawiać problemy z niejednoznacznością. Jeżeli bowiem idziemy w górę więcej niż dwa pokolenia, może mieć znaczenie ścieżka w grafie dziedziczenia, którą przy okazji obieramy. Ten problem eliminuje dziedziczenie wirtualne, przy okazji wprowadzając jednak spory zestaw nowych kłopotów. I dlatego właśnie wielodziedziczenia powinno się nie unikać, o ile się nie wie dokładnie, co chce zrobić :)

Zatem proste, zdawałoby się, stwierdzenie “coś jest jakiegoś typu”, w programowaniu może wcale nie być takie oczywiste. Takie są aczkolwiek uroki naszego ulubionego OOP-u :]

Tags: , ,
Author: Xion, posted under Programming » Comments Off on Być albo nie być
 


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