Tag: algorithms

Entries for tag "algorithms", ordered from most recent. Entry count: 68.

Uwaga! Informacje na tej stronie mają ponad 6 lat. Nadal je udostępniam, ale prawdopodobnie nie odzwierciedlają one mojej aktualnej wiedzy ani przekonań.

Pages: 1 ... 5 6 7 8 9

# Szarpanie gry

Fri
07
Dec 2007

Szarpanie gry to wredny błąd. Długo nie wierzyłem w ogóle w jego istnienie - dopóki sam go nie doświadczyłem w swoim kodzie, najpierw na laptopie, a potem również na blaszaku. Chodzi o sytuację, kiedy FPS-ów jest dużo, ale mimo tego animacja "szarpie". Powiązany z tym może być jest błąd opóźniania się obrazu za wejściem z myszki, doświadczany przy pisaniu GUI. Rozwiązania są różnorodne:

Przesuwać obiekty nie o stałą odległość w każdej klatce, ale o prędkość pomnożoną przez różnicę czasu, jaki upłynął od poprzedniej klatki do bieżącej. Innymi słowy, chodzi o szkolny wzór s += v * dt. To jedna z podstawowych zasad w programowaniu gier, każdy powinien ją znać.
Można spróbować włączyć pionową synchronizację (VSync). W Direct3D odpowiada za to flaga D3DPRESENT_INTERVAL_DEFAULT. To ogranicza liczbę FPS do częstotliwości odświeżania ekranu, ale niweluje sytuację, kiedy połowa ekranu pokazuje starą klatkę, a połowa nową. Podobno kiedyś na starych kartach graficznych pomagało też na jakieś migotanie, ale sam nigdy niczego takiego nie widziałem.
Można wywołać na początku programu funkcję WinAPI: SetThreadAffinityMask(GetCurrentThread(), 1); To sugestia dla systemu, żeby wątek główny przywiązać na stałe do pierwszego procesora, co powinno naprawić problemy z pomiarem czasu za pomocą Query Performance Counter na procesorach wielordzeniowych. Choć są i tacy, którzy twierdzą, że to nie pomaga. Mnie pomogło. (O tej metodzie powiedział mi mINA87.)
Utworzyć obiekt IDirect3DQuery9 typu D3DQUERYTYPE_EVENT, a przed wywołaniem metody urządzenia Present wywoływać dla tego Query metodę Issue(D3DISSUE_END). To powoduje zaczekanie z zakończeniem klatki na wszelkie renderowanie wykonywane asynchronicznie przez kartę graficzną. Dzięki temu nie "zbiera się" wiele klatek, co niweluje szarpanie, daje lepszą synchronizację myszki z obrazem oraz naprawia błąd w sterowniku nVidia, na który kiedyś natrafiłem, a który powodował nierenderowanie części geometrii. (O tej metodzie powiedział mi ayufan.)
Podobno są tacy, którym powyższy sposób nie pomaga. Wówczas pozostaje jeszcze brutalne wymuszenie zaczekania na kartę za pomocą sztuczki z blokowaniem powierzchni. Opisana jest tutaj: Input Lag. (O tej metodzie powiedział mi Krzysiek K.)

Comments | #directx #rendering #algorithms Share

# Quady zwrócone w stronę kamery

Fri
23
Nov 2007

Berg zadał wczoraj na forum pytanie o to, jak napisać w DirectX quady zwrócone zawsze w stronę kamery w celu zrobienia efektu cząsteczkowego (particle system). Naszła mnie ochota, żeby w odpowiedzi opisać to dokładnie i tak powstała długa wiadomość, która może się komuś przydać. Dlatego postanowiłem tutaj również ją zareklamować :) Odp: Quady zwrócone w stronę kamery

Comments | #rendering #math #algorithms Share

# Dlaczego FPS jest do bani

Tue
02
Oct 2007

Pesymiści narzekają, że od narysowania kilku trójkątów liczba FPS (klatek na sekudnę) spadła im z 1000 do 300. Optymiści cieszą się, że po podwojeniu liczby rysowanych obiektów ich FPS nie spadł o połowę, tylko na przykład z 60 do 50. Gdzie tkwi tajemnica?

Prawda jest taka, że FPS jako miara wydajności jest do bani. Nie żeby była nieadekwatna, ale czym właściwie jest FPS? Wyrażony w klatkach na sekundę - 1/s, czyli w Hz, to jest tak naprawdę częstotliwość wyświetlania klatek - odwrotność czasu renderowania jednej klatki. Jeśli założymy, że każdy dodatkowy obiekt wydłuża czas renderowania o 3 ms, to wraz ze wzrostem liczby obiektów liniowo wzrasta czas renderowania klatki, natomiast liczba FPS jest z nimi związana funkcją y=3/x. Oto dlaczego tak nieintuicyjne wyniki daje. Z resztą zobaczcie sami:

Comments | #math #algorithms Share

# Kuriozalny filtr graficzny

Sat
29
Sep 2007

Zadanie jest takie: Daną mamy teksturę, która w jednym z kanałów (tutaj: czerwony) ma pewne dowolne informacje. Trzeba je skopiować do pozostałych kanałów tak, żeby powstała tekstura w odcieniach szarości. Jak to zrobić? Zmiana na teksturę czarno-białą poleceniem Desaturate odpada, bo uśrednia wartości RGB powodując przyciemnienie tekstury, a po dostosowaniu poziomów pewną utratę informacji.

Choć to zaskakujące, takiej prostej funkcji nie posiada żaden z programów graficznych, które mam zainstalowane w swoim komputerze! Ani ACDSee 5.0, ani Paint, ani GIMP, ani też DirectX Texture Tool czy nawet IrfanView, który potrafi przynajmniej zamieniać miejscami kanały. Przepisanie koloru do kanału alfa jest wykonalne w GIMP-ie (chociaż dużym wysiłkiem).

Czy ktoś wie, jak to zrobić? Nie czekając na odpowiedź zaczynam pisanie swojego programu do przetwarzania tekstur :P

NOWE: Kolejny potrzebny mi filtr, którego nie mogę zlokalizować: rozmycie (Blur) z zawinięciem na granicach, żeby tekstura pozostała bezszwowa (Seamless). Ale wiem już jak to wykombinować w GIMP-ie.

Comments | #algorithms #rendering #graphics #tools Share

# Równomierne losowanie punktów z okręgu

Sun
26
Aug 2007

Jak losować punkty należące do okręgu, rozłożone równomiernie? W programowaniu mamy najczęściej dostępny generator liczb o rozkładzie równomiernym. Losowanie punktów z kwadratu jest z jego użyciem napisać prosto. Jak losować punkty z okregu?

Pierwszy pomysł polega na normalnym losowaniu punktów we współrzędnych kartezjańskich z kwadratu opisanego na tym okręgu i odrzucaniu tych, które leżą poza okręgiem. To niefajny pomysł - za dużo niepotrzebnego liczenia.

Drugi pomysł polega na losowaniu punktów we współrzędnych biegunowych - odległości od środka i kąta. To lepsze, ale pojawia się tu jeden kruczek. Losowane w ten sposób punkty mają tendencję do skupiania się w środku, bo dla małych wartości promienia punkty leżą blisko siebie niezależnie, jaki wylosował się kąt - tym bliżej, im mniejszy promień. Jak temu zaradzić?

Prawdopodobieństwo wylosowania danego promienia powinno być nie równomierne, ale propocjonalne do pola koła, które on wyznacza. Ponieważ pole jest zależne od promienia kwadratowo, wystarczy wylosowany promień (w zakresie 0..1, jeszcze przed przeskalowaniem) SPIERWIASTKOWAĆ.

Dla punktów 3D należących do kuli powinno być analogicznie.

Comments | #math #algorithms #rendering Share

# Sortowanie wg typu

Fri
17
Aug 2007

Mamy wektor wskaźników na obiekty różnych typów dziedziczących ze wspólnej klasy bazowej. Jak posortować go wg typu? Właśnie wymyśliłem, że do porównywania elementów wektora można wtedy użyć takiego uniwersalnego funktora:

template <typename T>
struct TypeCompare
{
  bool operator () (const T *o1, const T *o2)
  {
    return &typeid(*o1) < &typeid(*o2);
  }
};

Przykładowy program: Sortowanie_wg_typu.cpp.

Comments | #c++ #algorithms Share

# Parsowanie parametrów wiersza poleceń

Thu
09
Aug 2007

Wiele programów, nie tylko konsolowych, akceptuje jakieś parametry wiersza poleceń. Wbrew pozorom zagadnienie nie jest banalnie proste. Zależnie od tego czy program jest konsolowy czy okienkowy, kod wyposażamy w funkcję main lub WinMain. Skutkiem ubocznym jest, że w pierwszym przypadku dostajemy wiersz polecenia już rozłożony na poszczególne parametry (argc, argv), a w drugim przypadku jeden łańcuch ze wszystkimi parametrami.

Ponadto przydatny jest swego rodzaju parser, rozkładający parametry na poszczególne przełączniki i ich ewentualne dane. W Linuksie załatwia to funkcja systemowa getopt, a jej możliwości są imponujące. Nikogo, kto używa tego systemu nie dziwią kombinacje takie jak łączenie opcji typu -cvz zamiast -c -v -z czy sklejanie opcji z danymi typu -lpthread zamiast -l pthread. W Windowsie polecenia systemowe używają opcji zapisywanych w formie /Opcja, ale nie ma w systemie mechanizmu do ich parsowania.

Dlatego chciałbym tu pozachwalać moją klasę CmdLineParser, która załatwia wszystkie powyższe problemy. Jej napisanie poprzedziłem dokładnymi badaniami, jak w Windows i w Linux zachowują się parametry wiersza poleceń. Klasa działa zarówno z parametrami funkcji main, jak i WinMain. Akceptuje opcje zarówno w formie Windowsa, jak i Linuksa, zarówno długie jak i krótkie. Jest przy tym prosta w użyciu i przenośna. Wchodzi w skład modułu Base mojej biblioteki CommonLib 6.1. Szczegóły:

Base.txt - dokumentacja
Base.hpp - plik nagłówkowy
Base.cpp - plik źródłowy

Comments | #productions #algorithms Share

# Swobodne drzewo ósemkowe

Tue
07
Aug 2007

Technik podziału przestrzeni jest wiele. Ostatecznie chyba zdecyduję się na drzewo ósemkowe (Octree) + Frustum Culling + Occlusion Query. To powinno wystarczyć do względnie szybkiego działania i być proste do napisania - dużo prostsze niż portale, które planowałem wcześniej.

W "Perełkach programowania gier", tom 1, znajduje się artykuł poświęcony swobodnym drzewom ósemkowym. To dobry sposób na pozbycie się problemu "lepkich płaszczyzn" i tym samym polepszenie działania całej techniki. Polega na rozszerzeniu obszarów obejmowanych przez poszczególne węzły drzewa tak, że nachodzą na siebie. To nachodzenie nie stanowi problemu, a dzięki niemu obiekty przecinające środek węzła mają szanse trafić w całości do jego podwęzłów.

Moją uwagę zwrócił w artykule jeden szczegół. Nie rozumiem otóż, po co zwiększać obszar w kierunku wystającym poza obszar węzła nadrzędnego? Przecież obiekty, które do niego trafiły i tak zawierają się w obszarze węzła nadrzędnego. Dlatego ja zrobiłem to trochę inaczej. Czyżbym się gdzieś pomylił w swoim myśleniu?

Comments | #rendering #algorithms Share

Pages: 1 ... 5 6 7 8 9