Dynamicze tablice w C

Czasem życie zmusza do pisania w sławetnym i na szczęście zanikającym już języku C. A tam nie ma chociażby takich luksusów jak STL z niezastąpionymi pojemnikami. O wszelkie struktury danych trzeba zatroszczyć się samemu, co obejmuje także tak podstawowe jak dynamiczne tablice.
Jak wiadomo, takie tablice należy samodzielnie alokować, zmieniać ich rozmiar (z kopiowaniem zawartości) oraz zwalniać, gdy nie są już potrzebne. Najwyraźniej więc wybitnie przydatne są tu funkcje malloc i free, prawda? Otóż nieprawda :)

O wiele wygodniej jest bowiem używać funkcji realloc:

Jej nazwa wskazuje, że jej głównym przeznaczeniem jest zmiana rozmiaru już zaalokowanego kawałka pamięci. Zazwyczaj sprowadza się to zresztą do przydzielenia nowego, skopiowania tam zawartości starej porcji i zwolnienia jej. Jednakże w dwóch szczególnych przypadkach realloc zachowuje się inaczej – zależy to od parametrów, jakie jej podamy:

• jeżeli pierwszym parametrem będzie wskaźnik pusty (NULL), funkcja przydzieli pamięć w ilości bajtów wyrażonej drugim parametrem – czyli zachowa się jak malloc
• jeśli zaś drugim parametrem będzie zero, to funkcja spróbuje zwolnić kawałek pamięci, na który pokazuje wskaźnik będący pierwszym parametrem – czyli zachowa się jak free

To sprawia, że możemy używać funkcji realloc w postaci wywołania podobnego jak powyżej zawsze wtedy, gdy musimy zmienić rozmiar tablicy. Można na przykład dodać do niej element w taki oto sposób:

Nie musimy się martwić, czy tablica została wcześniej zaalokowana czy nie. Analogicznie wygląda usuwanie elementów z końca lub początku tablicy – wówczas nie trzeba przejmować się tym, czy z tablicy coś zostanie. Tak naprawdę opakowywanie obu tych operacji w funkcje nie jest nawet specjalnie potrzebne.

Jedynym warunkiem, aby to wszystko działało, jest odpowiednie zainicjowanie wskaźnika na tablicę oraz zmiennej przechowującej jej rozmiar – co jest aczkolwiek dość oczywiste:

I to właściwie wszystko. W sumie więc nie jest to może std::vector, ale w C nie ma co wybrzydzać :)

Vista i Eksplorator gier

Oprócz wsparcia dla wielkiej i wspaniałej wersji 10 biblioteki DirectX, system Windows Vista ma przynajmniej jeszcze jeden feature związany z programowaniem gier (i przy okazji z graniem w nie). Nie jest on aczkolwiek aż tak szeroko znany, chociaż wszystkie niezbędne narzędzia potrzebne do korzystania z niego są zawarte – nomen omen – w DirectX SDK.

Eksplorator gier z zaznaczoną
najciekawszą pozycją ;-)

To Eksplorator gier – małe, dosyć niepozorne, ale w gruncie rzeczy całkiem potężne narzędzie – w tym sensie, że potrafi ono czasami… zablokować dostęp do niektórych plików na dysku :) To aczkolwiek robota kontroli rodzicielskiej, czyli funkcji bardzo ściśle z wspomnianym Eksploratorem związanej. Ale po kolei.
Eksplorator gier (dostępny przez Start > Gry) to program, za pomocą którego możemy przeglądać gry zainstalowane na naszym komputerze. Prezentuje on nam ich nazwy, loga, gatunki, wymagania sprzętowe (w postaci Indeksu wydajności Windows), klasyfikację treści (wymagany wiek, zawartość przemocy, wulgaryzmów, itp.) i oczywiście pozwala także rzeczone gry uruchamiać – o ile nie zabrania tego ewentualna kontrola rodzicielska. Niby proste, chociaż na pierwszy rzut oka można by przypuszczać, że aplikacja ta dysponuje jakąś sztuczną inteligencją lub zdolnościami paranormalnymi. No bo skąd właściwie bierze ona te wszystkie informacje?…

Edytor plików GDF
zawarty w DXSDK

Prawda jest naturalnie taka, że wszystkie te dane muszą być podane przez twórców gier. W tym celu należy stworzyć tzw. Game Definition File (GDF), który jest plikiem XML opisującym różne parametry gry. Do niego możemy też dołączyć kilka grafik, a następnie całość należy zlinkować jako zasoby (resources) do jakiegoś pliku wykonywalnego – .exe lub .dll. Część tych czynności jest wspomagana przez Game Definition File Editor – niewielkie narzędzie dostarczane wraz z DirectX SDK począwszy od zeszłego roku. Potrafi ono mianowicie wyprodukować skrypt zasobów (plik .rc), który możemy dołączyć np. do projektu w Visual C++, skompilować do .res i z linkować z naszą grą.

Klasyfikacji treści wymaga
niestety (albo raczej stety)
cyfrowego podpisania gry

Lecz niestety nie jest to koniec zabawy :) Cały ten system, dzięki któremu Eksplorator posiada informacje o zainstalowanych grach, działa częściowo w oparciu o COM, a sama gra wymaga rejestracji w systemie w dość specjalny sposób, zanim będzie ona widoczna w programie. Ten sposób spokojnie można nazwać “ręcznym”, bo obejmuje on:

1. Stworzenie instancji interfejsu COM IGameExplorer.
2. Wywołanie jego metody VerifyAccess z podaniem pliku GDF.
3. Wywołanie metody AddGame z kilkoma parametrami, m.in. wspomnianym plikiem i ścieżką do katalogu instalacyjnego gry.
4. Stworzeniu przynajmniej jednego skrótu (w ściśle określonym miejscu), który pozwoli np. uruchomić grę przy pomocy Eksploratora.

Urocze, prawda? ;-) Żeby było śmieszniej, wszystkie te czynności powinny być wykonane w trakcie instalacji gry (a dokładniej: na sam jej koniec), co wymaga intensywnej grzebaniny w używanym programie instalacyjnym (w celu wywołania funkcji z pomocniczej biblioteki DLL) lub po prostu napisania małego programiku, który zostanie odpalony na końcu setupu i wszystkim się zajmie. O ile mi wiadomo, ani InstallShield, ani Windows Installer, ani freeware’owy Inno Setup nie wspierają natywnie procesu rejestracji gier w podobny sposób jak chociażby instalacji czcionek w systemie.

“A więc po co to wszystko?”, można zapytać. Ano chociażby po to, żeby nasza cudna produkcja jakoś się wyróżniała :] Obecnie gry retailowe w większości rejestrują się Eksploratorze, lecz z pewnością czyni tak mniejszość gier typu casual czy share/freeware. Możemy więc choć trochę zabłysnąć w oczach przyszłego użytkownika (chociaż zasadniczo zalecam świecenie innymi zaletami).
Na koniec – jeśli zdecydujemy pobawić się całym tym mechanizmem – warto pamiętać o tym, że Eksplorator gier to rzecz istniejąca jedynie na Viście, więc tylko na tym systemie powinniśmy przeprowadzać proces rejestracji.

Troska o baterię laptopa

Chociaż współcześnie gadżety są coraz mniejsze i coraz zmyślniejsze, to jednym z ich słabszych punktów jest zawsze zasilanie. Jest tak zapewne dlatego, że baterie działają w oparciu przede wszystkim o reakcje chemiczne. A ponieważ jak dotąd nie zanosi się, aby w najbliższej przyszłości upowszechniło się zasilanie bezprzewodowe, warto wiedzieć, jak właściwie postępować z bateriami, by zapewnić ich maksymalną możliwą wydajność. Jest ona szczególnie ważna w przypadku laptopów i palmtopów, które zużywają największe ilości energii.

Co za szczęście, że laptopy
nie potrzebują aż takich
dużych baterii :)

Obecnie najpopularniejsze są baterie litowo-jonowe (Li-Ion), głównie ze względu na stosunek ceny do jakości i wygody użytkowania. Przy korzystaniu z takich baterii warto pamiętać o takich oto prostych regułach:

• W przeciwieństwie np. do starszych baterii niklowo-wodorkowych (Ni-MH), akumulatory Li-Ion nie wymagają tzw. formowania, czyli kilkukrotnego ładowania i rozładowania na początku użytkowania. Tak naprawdę baterie litowe nigdy nie powinny być całkowicie rozładowywane, gdyż szkodzi to ich pojemności i żywotności. Dlatego właśnie systemy operacyjne zwykle wykrywają stan baterii laptopów i “w ostatniej chwili” przełączają się w stan hibernacji.
• Zupełnie odwrotnie niż akumulatory Ni-MH, baterie Li-Ion powinny być doładowywane kiedy tylko to możliwe. Znów jest to bardzo praktyczne zwłaszcza w przypadku komputerów przenośnych, które często są podłączane do prądu.
• Tym, co skraca żywotność baterii jonowych, jest przede wszystkim temperatura. Jeśli jest ona zbyt wysoka przez dłuższy czas – co, niestety, jest powszechne w przypadku laptopów, które generalnie mają problemy z chłodzeniem podzespołów – pojemność baterii ulega zmniejszeniu. Dlatego też w przypadku dłuższej pracy na zasilaniu sieciowym, dobrze jest wyjąć z komputera baterię, by się nie nagrzewała.

W ten sposób możemy przedłużyć życie baterii Li-Ion, ale trzeba pamiętać, że i tak nie jest on zbyt duży i wynosi mniej więcej 3 lata. Co więcej, jest on zdeterminowany w chwili produkcji i właściwie tylko od szczęścia zależy, czy trafi się nam model krótko- czy (względnie) długożyjący.

Najwyraźniej więc – mimo coraz dalej postępującej bezprzewodowości – kable zasilające będą nam ciągle towarzyszyć jeszcze przez całkiem długi czas…

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

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:

Ł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:

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

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

Kolega 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:

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(n³), 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?

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:

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ę:

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

Fragmenty a piksele

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.