Tag: algorithms

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

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

Pages: > 1 ... 5 6 7 8 9 >

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

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

# Architektura całej gry

Fri
27
Jul 2007

Architektura całej gry, choć nie o nią mi w obecnej chwili chodzi, przewija się w literaturze którą obecnie analizują i też mnie interesuje. Szczególnie, że ilekroć staję przed tym zadaniem, zawsze mój kod zamienia się w jedną wielką kulę błota, w której wszystko korzysta ze wszystkiego beztrosko rzutując klasy w dół hierarchii dziedziczenia. Ciekawy wątek forum na ten temat jest TUTAJ.

Wyczytałem właśnie, że architekturę gry można podzielić na:

Wprowadzanie takich podziałów wydaje się trochę na siłę, szczególnie że można tu wymyślić jeszcze dużo innych opcji. Gdzieś kiedyś na forum pisali nawet o takiej, w której każdy obiekt gry posiadać ma swoje pod-obiekty odpowiedzialne za grafikę, dźwięk, fizykę itd. Tylko czy coraz większe komplikowanie rozwiązuje ten i tak skomplikowany problem? :)

Comments | #algorithms Share

# XNL2 do kosza

Thu
12
Jul 2007

Wymyśliłem kiedyś język opisu XNL2 i wiem, że kilku osobom nawet się spodobał. Teraz doszedłem do wniosku, że był oparty na błędnych założeniach i w związku z tym ogłaszam koniec "dorabiania ideologii do tokenizera", jak to jeden mój kolega kiedyś trafnie skwitował.

Zachęcam, by zamiast używać XNL2 czy innych takich wynalazków albo pisać coś w tym rodzaju samemu, skorzystać z modułu Tokenizer z mojej biblioteki CommonLib 6.1 (zobacz też online nagłówek i dokumentację). Jest dużo lepiej przemyślany, prostszy w użyciu, a co najważniejsze - parsuje język przypominający tokeny C/C++, a więc z takimi komentarzami i łańcuchami znaków, do jakich jesteśmy przyzwyczajeni. Taki tokenizer może być dobrą bazą do szybkiego zaprojektowania i zaimplementowania własnego języka opisu.

Comments | #libraries #productions #algorithms Share

Pages: > 1 ... 5 6 7 8 9 >

[Download] [Dropbox] [pub] [Mirror] [Privacy policy]
Copyright © 2004-2021