Projekt: Samochód Autonomiczny

Obecnie na blogu panuje cisza, więc przerwę ją na chwilę :)

Obecnie zbliża się ciężki okres - sesja, nawał projektów itd. Nie mniej jedną z rzeczy jakimi chciałbym się pochwalić, a zajmowałem się nimi ostatnio, to samochód autonomiczny "Jurek".

Dołączyłem do zespołu 2 tygodnie przed terminem pokazu i musiałem razem z Maćkiem (pzdr!) umożliwić autonomiczną jazdę - ze względu czasowych i technicznych (jedna kamerka internetowa na dachu i mój laptop + elektronika pojazdu) musieliśmy się ograniczyć do jazdy między dwoma zielonymi pasami (normalnie działa to na białych, ale spadł śnieg więc trzeba było zmienić oprogramowanie (: )

Z ciekawostek, soft jest oparty o C# (dev && dbg time!) i ku zaskoczeniu wszystkich zadziałało od razu na danych tzw. "z (_!_)", a co lepsze - okazał się działać lepiej niż przypuszczałem jeszcze kilka godzin wcześniej, w nocy - gdy kończyłem klepać i głośno przeklinałem :P
A tak to wyglądało:

Oczywiście telewizja swoje powiedziała, czym trochę nas ubawiła :)

Obecnie nie mam tymczasowo czasu rozwijać projekt, ale po sesji zamierzam ostro się zabrać za niego. Przyjmując model "progresywny" na liście TODO znajduje się zrobienie tego porządnie w C++ (i pewnie Qt?) oraz umożliwienie parkowania. O ile się uda - na razie jedyny sensor to jedna kamera internetowa, myślimy nad kupnem kilku ale nie wiem na ile realnie praktyczne to będzie.
Do tego szukam osób w miarę ogarniających temat CV, SLAM, pisania dokładnych symulacji oraz innych "ogarniaczy" do pomocy. Przy czym naprawdę zależy mi na konkretnych ludziach, którzy mogą pokazać, że coś faktycznie potrafią. Jeśli tak jest i jesteś we Wrocławiu, to skontaktuj się ze mną :)

I to tyle, jeszcze na koniec screen projektu który właśnie mam otwarty w IDE i kończę pisać - powierzchnie Coonsa I rodzaju:

Technika "Generic Macro"

Ostatnio w pracy pojawił się problem - mamy pewną funkcjonalność opartą na identyfikację zasobu poprzez c-string, co wygląda mniej więcej tak:

Resource->Get("Something_Foo");

Przy czym filozofia była taka, aby nigdy nie zwracać błędy tylko coś w miarę sensownego (wartości domyślne). Takie podejście do identyfikacji ma zasadnicze wady:

• porównywanie stringów w run time
• łatwo o błędy - literówki, niezgodność wielkości liter

Zaleto-wadą jest też fakt, że nie trzeba definiować wcześniej tych napisów ale nie ma żadnej jednej, długiej listy.

Dlatego też w ramach refaktoryzacji postanowiliśmy zamienić napisy na typ wyliczeniowy (oraz użyć ich do szablonowych wytycznych, ale o tym napiszę w następnym poście).
W ten sposób nie będzie dość kosztownego porównywania napisów, a także możliwa jest weryfikacja poprawności nazwy w czasie kompilacji jak i wygoda dla programisty w postaci podpowiedzi.

Ale tutaj jest pewien problem - potrzebna jest dalej reprezentacja tekstowa wartości typu wyliczeniowego - zarówno do zapisywania w logu ("Foo" mówi więcej niż 12) jak i API z którego korzystaliśmy również potrzebowało napisu... czyli chcemy mieć coś takiego:

enum res_id { Something_Foo, Something_Bar, Something_Foo_Foo };
const* char res_name[] = { "Something_Foo", "Something_Bar", "Something_Foo_Foo" };

Wypisanie tego w ten sposób i utrzymywanie w synchronizacji (biorąc pod uwagę tego, że osoby trzecie mogą zechcieć coś dopisać) nie wchodzi oczywiście w grę.

I tutaj pojawia się technika, którą nazywam "Generic Macro" (może jest na to jakaś inna nazwa?).

Otóż tworzymy plik o przykładowej nazwie resources.def w którym wpisujemy nasze dane wewnątrz jakiegoś w miarę sensownie nazwanego makra:

GENERIC_RESOURCE(Something_Foo)
GENERIC_RESOURCE(Something_Bar)
GENERIC_RESOURCE(SOmething_Foo_Foo)

następnie wystarczy stworzyć plik res_id.hpp w którym zdefiniujemy makro tak jak chcemy a potem dołączymy nasz plik .def :

#ifndef RES_ID_HPP__
#define RES_ID_HPP__

// this will be defined in cpp file
extern const char* res_name[];

// include resource.def by using macro to transform it to enum type
enum res_id {
    #define GENERIC_RESOURCE(X) X,
    #include "resources.def"
    #undef GENERIC_RESOURCE
    MaxResId
};

#endif //RES_ID_HPP__

I teraz w pliku res_names.cpp:

#include "res_id.hpp"

const char* res_names[] = {
    #define GENERIC_RESOURCE(X) (#X),
    #include "resources.def"
    #undef GENERIC_RESOURCE
    "\0"
};

I w ten sposób wystarczy modyfikować tylko plik resources.def a zarówno lista napisów jak i typ wyliczeniowy zostaną wygenerowane i będą zsynchronizowane.
Jak widać czasem sprytnie użyte makra mogą przełożyć się na lepszą jakość kodu dzięki zmniejszeniu ryzyka popełnienia błędu :)
Może znajdziesz jakieś inne ciekawe zastosowanie tej techniki?

(Bezsensowne) Przeładowania operatorów w C++

Przy pomocy przeładowania operatorów w C++ można robić bezsensowne rzeczy, które jednych zachwycą a u innych wywołają wrogość :) Jedną z takich rzeczy jest stworzenie obsługi list (np: zakupów, TODO, aliasów) czy też listy wad i zalet w taki "naturalny" sposób:

Aliases aliasList;
aliasList.add_for("number")
    * "one" 
    * "two" 
    * "three";

aliasList.add_for("moo")
    - "foo"
    - "bar"
    - "jaj";

aliasList.add_for("no_alias"); // identity

std::cout << "three stands for " << aliasList["three"] << '\n';

List list;

list.prons_and_cons_for("headphones X")
    + "price"
    + "quality"
    + "bass"
    - "too short cable"
    - "no volume control";

list.print_info_about("headphones X"); // or list.get_cons() etc

Implementacja polega na rozbiciu na dwie klasy.
Pierwsza, najważniejsza klasa polega na tym, że akumuluje argumenty (albo w moim przypadku - posiada referencje do kontenera drugiej klasy) w zadany sposób poprzez przeładowanie operatorów zwracających referencję - tak jak przeładowuje się zwykle operatory ">>" oraz "<<", przy czym trzeba również pamiętać o priorytetach i kierunku łączenia.
Druga klasa (Aliases, List w przykładach) zajmuje się tworzeniem pierwszej klasy i zawiera kontenery i właściwą logikę.

Jeśli nie jest to jeszcze jasne, to wystarczy spojrzeć na kod (drafty):

Analogowe literały w C++

Ostatnio w pracy troszkę się nudziło (bywa ;)), co spowodowało, że następujący kod zaczął się kompilować:

for (uint worm = I-------------I; worm >= II; worm -= I-I ) {
   cout << '*';
}

uint monsterHP =  I-----------------------I;       // 12 HP
uint monBossHP = (I-----------------------I) * 10; // 120 HP

cout <<( I-------I
         |       !
         !       !
         I-------I ).area(); 

To nie jest mój pomysł - kiedyś natrafiłem na blogu Paczesiowej ciekawy wpis gdzie znalazłem link opisujący w C++ literały analogowe - czyli zamiast podawać wartości naturalne można było narysować sobie linie, prostokąt albo sześcian w ASCII, co następnie było zamieniane na wartość liczbową.

Niestety - strona przestała działać a w cache znalazłem jedynie podgląd jak to wyglądało... więc nie miałem innego wyjścia jak spróbować zaimplementować to samemu ;)

Na razie odpuściłem sobie implementację literałów 3D - zaimplementowałem tylko linie oraz prostokąty co okazało się zaskakująco proste, przy czym nie nakładałem zbyt wysokich wymagań co do poprawności i obsługi sytuacji brzegowych :)

Cała sztuczka polega na odpowiednim przeładowaniu operatorów. Zauważ, że tak naprawdę linię można ograniczyć dwoma obiektami (I), których wartość ulega zmianie poprzez użycie operatora "--" oraz połączenie ich przez binarny operator "-".

Analogicznie jest dla 2D - to po prostu 2 linie z tym, że jedna jest modyfikowana przez "!" (zwiększa wysokość) a potem linia + linia z wysokością są scalane przez operator binarny "|".

Myślę, że rozjaśni się wszystko jak pokażę kod (testowany na VC2k5 i ideone).

Pierwsze proceduralne gfx w < 2kB

Ostatnio na Warsztacie odbyło się compo procedural gfx 4kB w którym postanowiłem wziąć udział, mimo, że nie mogłem poświęcić dużo czasu.

W ~1,75kB zmieściłem renderowanie takiego oto obrazka zatytułowanego "Hi Hydra":

Niestety - pierwszy shader napisałem tydzień temu więc okazało się, że mój kod jest syfiasty i nie działa niektórym - a czasem potrafi nawet wywalić sterowniki! Nie mniej i tak miło, że udało mi się coś osiągnąć.

Nitro namawia mnie do dopracowania i wysłania jej na jakieś party... pewnie tak zrobię ;)

Paczka (uruchamiać na własne ryzyko! duże prawdopodobieństwo, że nie zadziała i może mieć straszne skutki uboczne!) do pobrania jest tutaj

Wrzucam też kilka ujęć WIP jak eksperymentowałem :)

Sesja ;)

Nic dodać, nic ująć - koniec semestru zawsze wiąże się z brakiem czasu. Nie mniej po zakończeniu tego najcięższego okresu mam zamiar napisać posty związane z programami nad którymi ostatnio pracuję:

1. Software'owy ray marcher w C++ - dorobiłem do niego GUI i muszę powiedzieć, że Qt jest naprawdę niezłe. Obecnie podpinam swój "język" opisu sceny - na zdjęciu, w programie po lewej jest kod, co 1,5 s jest parsowany i jest generowany mały podgląd. Można oczywiście wyrenderować w większym rozmiarze i zapisać. Obecnie podpinam światło i materiały a potem zamierzam dodać jeszcze kilka drobiazgów i program będzie się chyba nadawał na zaliczenie i będę mógł się zająć ciekawszymi rzeczami, czyli GPU :)

Tak program póki co wygląda :)

Drobny eksperyment z modyfikacją uzyskanych odległości

2. Ten program już oddałem - jest to program równoległy w C#, korzystający z algorytmu mrówkowego do rozwiązania jednomaszynowego problemu szeregowania zadań z wagami kar. Zamierzam poświęcić mu osobny wpis bo okazał się naprawdę ciekawy w implementacji.

Rozwiązanie optymalne: 917, program znalazł coś bliskiego dla problemu rozmiaru 40!

Koniec (?) projektu z blendera ;)

Oto i sam Pan Raptor ;)

W końcu skończyłem swój projekt na kurs Blendera (jeden z dwóch więksszych) :)

Tekstura sux i jeszcze mógłbym trochę rzeczy dorobić ale mi się już nie chce i czasu też nie mam za bardzo (hmm ale może jeszcze kiedyś mnie najdzie wena - chętnie bym w sumie urozmaicił środowisko.

Po lewej - sam dinozaur, a poniżej - w środowisku naturalnym z lekkim postprocessingiem w Photoshopie (Compositor z Blendera niestety nie dał rady bo nie mogłem pozbyć się białej otoczki z kanału alpha).

Oto i efekt końcowy - welociraptor w środowisku w którym go w ogóle nie powinno być :P

Projekt: Sphere Marching

Pierwszy test - kolorowanie po z oraz ilości kroków

Na kurs języka C++ piszę sobie projekcik - renderer oparty o ray marching, a dokładniej o technikę sphere tracing i distance fields. Technika to umożliwia m.in. proste renderowanie fraktali i CSG oraz niezwykle tanie do policzenia Ambient Occlusion.

Póki co dopiero zaczynam eksperymenty i muszę powiedzieć, że jest to bardzo rozwijające, tym bardziej, że wszystko piszę od zera sam (łącznie z operacjami wektorowymi) więc dużo się uczę.

Obecnie zaimplementowałem prymitywy: kulę, sześcian oraz torus, wraz z możliwością ich dodawania/usuwania/znajdowania części wspólnej. Mam też liczenie normalnych i teoretyczną obsługę AO oraz eksperymentuje z cieniowaniem Phonga.

Jak dogłębniej zapoznam się z tematem na pewno opiszę tą technikę od zera. Póki co - kilka ujęć WIP:

Oświetlenie Blinn-Phong + małe AO

CSG i normalne

Blender - projekt

Model Welociraptora WIP

Test trawki :)

Obecnie pracuję nad swoim pierwszym, większym projektem w Blenderze w związku z tym, że mam na studiach taki kurs - postanowiłem wymodelować welociraptora (aczkolwiek w niepoprawnej wersji "klasycznej" - tj. bez piór) w jakiejś ładnej (również niepoprawnej - bo z trawką) scenerii, a docelowo jak starczy mi czasu to będą dwa raptory polujące na hadrozaura (a powinien być protoceratops...).

Wrzucam więc kilka obrazków WIP :)

A to stan (prawie) najnowszy - chcę dodać coś w tle, zrobić lepszy blending nieba i dodać inne szczegóły (drzewka, paprotki etc)

Programowanie na żywo i podróże w czasie

...and when I change the code I change his future!

Ostatnio zainteresował mnie parę kwestii związanych z wytwarzaniem oprogramowania, głównie gier i innych wizualnych aplikacji - a mianowicie możliwość zmieniania kodu w locie i obserwowanie jego wyników w czasie rzeczywistym a także - móc podróżować w czasie by łatwiej było debugować i eksperymentować (back-in-time debugging) - chyba każdy marzył by móc cofnąć wykonanie programu i podejrzeć zawartość zmiennych zanim nastąpił crash.

Jeśli myślisz, że to nierealne to obejrzyj ten niesamowity wykład Bret Victora - coś genialnego! Zastanawiam się czy byłbym w stanie stworzyć coś podobnego, ale nie w JS...

W każdym razie wydaje mi się to niezwykle interesujący kierunek rozwoju oferujący niesamowite możliwości i nie mogę się doczekać by rozwinął się w coś większego i wspanialszego - byłoby to z korzyścią dla wydajności jak i zwiększenia przyjemności z tworzenia.

Polecam zajrzeć również na stronę Breta Victora http://worrydream.com/ (fajne i ciekawe rzeczy!).

Przy okazji, m.in. Google pracuje nad Back-in-Time debugger

2 ciekawe kursy online

Oprócz kursów ze Stanforda (o których tutaj pisałem) pojawiły się dwa - moim zdaniem bardzo ciekawe - kursy online trwające 7 tygodni:

CS 373: PROGRAMMING A ROBOTIC CAR
CS 101: BUILDING A SEARCH ENGINE

Prowadzi je Sebastian Thrun oraz David Evans, i chyba będą darmowe więc warto się zapisać ;)
Zapisy na kurs odbywają się tutaj.

Atraktory, czyli chaos na ekranie

Atraktor De Jong

Dawno temu, na początku 2 klasy technikum zainteresowały mnie atraktory - w bardzo prosty sposób można było uzyskać nietrywialne i ładne chaotyczne kształty. Wystarczyło zaimplementować jakiś wzorek, ustawić punkt początkowy i parametry, a następnie iteracyjnie wyznaczać i rysować punkty :)
Nawet z przyjacielem zrobiliśmy program umożliwiający interakcje z fraktalami i atraktorami (obracanie, przesuwanie, animowanie itd).

Mam zamiar powrócić do tego tematu i podejść do tego z wiedzą, która od tamtej pory nabyłem a tymczasem wrzucam kilka wzorów skopiowane z mojej starej aplikacji ;)

Bezpośrednia konwersja wielomianu interpolacyjnego w postaci Newtona na postać Beziera

Jednym z zadań jakie miałem do zrobienia wraz z przyjacielem  na pracownię (a potem była na ćwiczeniach) z analizy numerycznej dotyczyła konwersji wielomianu w postaci Newtona na postać Beziera. Ciężko coś znaleźć na ten temat w internecie i trochę ciężko było, dlatego postanowiłem napisać tego posta ;)
Napisaliśmy konwersję bezpośrednią jak i pośrednią (z wykorzystaniem bazy potęgowej) - opiszę w tym poście tylko tą pierwszą. Ładnie sformatowany pdf (który zawiera również kod) można pobrać tutaj.

Opis problematyki

Niech dany będzie wielomian interpolacyjny w postaci Newtona $L_n$, przy czym $b_k$ oznacza stałe współczynniki a $p_k$ iloraz różnicowy. Poszukujemy jego zapisu w postaci Béziera $B_n$. Wprowadźmy oznaczenia:
\begin{align*}
L_n(x) = \sum_{k=0}^{n}b_k p_k(x) \\
B_n(x) = \sum^n_{k=0}c_kB^n_k(x)
\end{align*}
Chcemy by:
\begin{equation} \label{eq:rownosc}
L_n(x) = B_n(x)
\end{equation}
Zatem problem sprowadza się to do problemu dobrania takich stałych $c_k$, by ta równość zachodziła.

VIP: Inteligentne skalowanie

Obecnie implementuję w C# algorytm Seam Carving. Jest to zaskakująco prosty algorytm "inteligentnego" skalowania. Idea algorytmy polega na usuwaniu szwów o najmniejszej energii, gdzie energię szwu definiuje się ile krawędzi (wysokich częstotliwości) przecina dany szew.

Póki co mam zaimplementowane zmniejszanie i pracuję nad powiększaniem, później dodam możliwość maskowania. Docelowo chciałbym to później przepisać w C++ i Qt.

Stan aplikacji na dziś - po lewej obrazek wejściowy, po prawej - efekt działania programu

Stara gierka z gimnazjum

Dzisiaj znalazłem źródła mojej staarej gierki zrobionej w konsoli (C++ i WinAPI) w 2 klasie gimnazjum.
Dopiero uczyłem się programować obiektowo w C++ i alokować dynamicznie pamięć :)

Celem gry jest przejechanie jak największej ilości ludzików, omijając niebezpieczne płotki jadąc niezwykle wypasionym samochodem.
Grafika - ASCII art, migotająca bo nie ma podwójnego buforowania a sama rozgrywka jest za wolna - czego wtedy nie potrafiłem rozwiązać, a teraz mi się już nie chce ;)

Źródła do ściągnięcia tutaj, a jak ktoś chce pograć i nie chce mu się kompilować to plik wykonywalny jest tutaj.

Zagadka "Skarby" i jej rozwiązanie w prologu

Pierwszym zadaniem na pracownię z programowania było rozwiązanie zagadki "Skarby" z Wiedzy i Życia zaimplementowane w prologu, który idealnie nadaje się do takich zadań.

Treść zadania brzmi tak:

Mamy planszę n x m. Cyfra w danym polu oznacza, w ilu sąsiednich kratkach – stykających się z polem z cyfrą bokiem lub rogiem – znajdują się skarby. W kratkach z cyframi skarbów nie ma. Znajdź wszystkie miejsca gdzie mogą być zakopane skarby.

Jak zatem rozwiązać taki problem w prologu? Standardowo: generuj-sprawdź-nawróć.

Amoeba - eksperymentalny wirus

Postanowiłem podzielić się opisem swojego eksperymentu, który miał miejsce kilka lat temu (~4).
W skrócie - stworzyłem prostego robaka polującego na inne ustrojstwa i wprowadziłem go w "ekosystem".
Udostępniam również kod do wglądu (róbta co chceta, ale nie biorę odpowiedzialności ;)) - kod źródłowy Amoeby (VS2k8, C++ oraz WinAPI).

Dla genezy i opisu eksperymentu zapraszam do czytania dalej.

Trochę zabawy z C++

Czasem gdy człowiekowi się nudzi, można zacząć wymyślać różne głupiutkie rzeczy. Poniżej poprawny kod w języku C++:

#define __ printf
#define guy int 
#define c(_) = { 0xBAD, 0xBAD, 0xBAD, 0xBAD} 
#define create 
#define with [4] 
#define and = 
#define ever ;;
guy x_X and 0xF00D; 

// ponizszy kod wypisuje w petli nieskonczonej BAD BAD F00D
while ("elvis is alive") // lub for(ever)
{ 
    long long ago = 2; 
    create guy o_O with c(_); 
    3[o_O] = x_X; 
    x_X =3 [o_O];
    o_O[ago--+--ago] = x_X; 
    while (x_X --> 0)__("%X ", (x_X%4)[o_O]);
};

Problem z iteratorem w szablonie

Załóżmy, że mamy kod jak poniżej:

template<typename T>
void foo()
{
  std::vector<t> vec;
  /// (...)
  for (std::vector<t>::iterator it = vec.begin(); it != vec.end(); ++it)
        bar(*it);
}

Jest to w miarę standardowy kod, który powinien działać od ręki. Teoretycznie. Dlaczego ten kod raz się skompiluje a raz nie i kompilator będzie miał problem z określeniem typu it?

Otóż nie wszystkie kompilatory są na tyle sprytne by określić co się tak naprawdę kryje pod szablonem. Wtedy musimy mu podpowiedzieć, że ma do czynienia z typem, czyli napisać:

typename std::vector<t>::iterator it

Wtedy zadowolimy kompilator :)

Na szczęście w C++11 można użyć przyjemnego słówka kluczowego auto, które powinno wybawić nas od takich problemów i uprzyjemnić życie, a jeśli nie możemy skorzystać z dobrodziejstw nowego standardu to lepiej mieć nawyk dopisywania typename.  Zwłaszcza jeśli spodziewamy się, że nasz kod będzie kompilowany na różnych kompilatorach (platformach).

Przy okazji będziemy mieć kolejny powód do narzekania czemu C++ jest fuj fuj :)

Klasy online ze Stanford

Pierwszy post poświęcę genialnej akcji jaką jest zorganizowane klas online przez Stanford.

Obecnie trwają klasy AI, Introduction to Databases oraz Machine Learning na który się zapisałem i muszę powiedzieć, że jest naprawdę bardzo fajnie prowadzony i gorąco polecam :)

Nie mniej okazuje się, że na semestr letni Stanford przygotował niespodziankę i przygotował niemało interesujących kursów!

Z dziedziny computer science można się zapisać na:
cryptography
computer science
machine learning
software as service
human-computer interaction
natural language processing
game theory
probabilistic graphical models
design and analysis of algorithms I
computer security

information theory
model thinking

Są też wykłady z przedsiębiorczości:
lean launchpad
technology entrepreneurship

medycyny:
anatomy
i inżynierii cywilnej:
making green buildings

Niektóre kursy są prowadzone przez naprawdę wspaniałe osoby i biorąc pod uwagę, że są prowadzone za darmo jest to niesamowita okazja nauczyć się czegoś nowego i ciekawego.

Dodatkowo prowadzący kurs mogą poświadczyć uczestnictwo na papierze, chociaż nie będzie to oficjalny papier ze Stanfordu to na pewno będzie to miła pamiątka jak i coś czym można się pochwalić :)