Reading RFID tags on Android

As promised some time ago, this post will be about Android.

About half year ago I bought Samsung Galaxy Nexus as my first Android phone and I found one thing interesting – the Near Field Communication (NFC).

Near field communication (NFC) is a set of standards for smartphones and similar devices to establish radio communication with each other by touching them together or bringing them into close proximity, usually no more than a few centimeters.[1]

In short, this is a technology based on RFID[2] tags that allows smartphone to do 3 things:

  • read and write RFID tags,
  • emulate RFID tag,
  • send small amount of data between devices in small proximity.

The first one can be used to read tags that matches MIME types on the device to activate some functionality, configure the device or just to read cards that uses the RFID technology. It’s also possible to write to those tags. The second enables the device to behave as RFID tag for another devices. And the third is used for communication between two devices, mostly to setup another, more powerful connection type such as Bluetooth or WiFi.

In this post I will show how to read data from the RFID tags since I don’t have any available card to write to. Fortunately this task is quite well covered by Android SDK[3] documentation so I will just write a quick setup of the basic project. I assume that an empty project is created with basic implementation provided by Eclipse or Android tool from SDK.

Enabling NFC in the project

First of all, to enable NFC in the project the modification of the AndroidManifest.xml file is required. The NFC is available since version 10 and requires special permission – android.permission.NFC. To enable it just add following code to the manifest node:

1
2
3
4
5
6
7
8
9
10
11
12
13
<uses-sdk 
   android:minSdkVersion="10" 
   android:targetSdkVersion="15" 
   />
 
<uses-permission 
   android:name="android.permission.NFC"
   />
 
<uses-feature 
   android:name="android.hardware.nfc" 
   android:required="true" 
   />

uses-feature entry means here that the application requires NFC and won’t work without it.

Since RFID tags are read and dispatched by the Android, application must register an Intent filter and a Techlist to get them. To do this add following code to activity node in manifest file:

1
2
3
4
5
6
7
<intent-filter>
   <action android:name="android.nfc.action.TECH_DISCOVERED"/>
</intent-filter>
<meta-data
   android:name="android.nfc.action.TECH_DISCOVERED"
   android:resource="@xml/techlist"
   />

There are free types of actions that can be used with NFC – android.nfc.action.NDEF_DISCOVERED, android.nfc.action.TECH_DISCOVERED and android.nfc.action.TAG_DISCOVERED. I chose the android.nfc.action.TECH_DISCOVERED because none of my RFID chips had NDEF messages and TAG, as the documentation says, is too general. Also TECH just worked.
As you can see the code also specifies the techlist xml file. This file contains a list of NFC technologies supported by the application. @xml/techlist means that this file has name techlist.xml and lies in res/xml/ directory. Following code shows an example of my file:

1
2
3
4
5
6
<resources xmlns:xliff="urn:oasis:names:tc:xliff:document:1.2">
   <tech-list>
      <tech>android.nfc.tech.MifareClassic</tech>
      <tech>android.nfc.tech.NfcA</tech> 
   </tech-list>
</resources>

This covers basic setup of NFC but requires the user to specify the application which will handle the Tag everytime it is read by Android. It is quite annoying so Android allows to register an Activity in the foreground to be the default one for handling Tag intents. To do that add following code to your Activity class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
private NfcAdapter mAdapter = null;
private PendingIntent mPendingIntent = null;
private IntentFilter[] mIntentFilters = null;
private String[][] mTechLists = null;
 
public void onCreate(Bundle savedInstanceState) {
   /* ... */
 
   mAdapter = (NfcAdapter)NfcAdapter.getDefaultAdapter(this);
 
   // Creating PendingIndent for foreground dispatching
   mPendingIntent = PendingIntent.getActivity(
         this, 
         0, 
         new Intent(this, this.getClass()).addFlags(Intent.FLAG_ACTIVITY_SINGLE_TOP), 
         0);
 
   IntentFilter tech = new IntentFilter(NfcAdapter.ACTION_TECH_DISCOVERED);
   try {
      ndef.addDataType("*/*");
   } catch(MalformedMimeTypeException e) {
      throw new RuntimeException("fail", e);
   }
 
   mIntentFilters = new IntentFilter[] { tech };
   mTechLists = new String[][] { getTechList(this.getResources()) };
 
   /* ... */
}
 
public void onResume() {
   /* ... */
 
   mAdapter.enableForegroundDispatch(this, mPendingIntent, mIntentFilters, mTechLists);
 
   /* ... */
}
 
public void onPause() {
   /* ... */
 
   mAdapter.disableForegroundDispatch(this);
 
   /* ... */
}
 
private static String[] getTechList(Resources resources) {
   ArrayList<String> list = new ArrayList<String>();
   XmlResourceParser xml = resources.getXml(R.xml.techlist);
 
   // Assumed simple parsing because of simple file structure
   for(;;) {
      int eventType = XmlPullParser.END_DOCUMENT;
      try {
         eventType = xml.next();
      } catch (XmlPullParserException e) {
         // TODO Auto-generated catch block
         e.printStackTrace();
      } catch (IOException e) {
         // TODO Auto-generated catch block
         e.printStackTrace();
      }
 
      if(eventType == XmlPullParser.TEXT) {
         list.add(xml.getText());
      } else if(eventType == XmlPullParser.END_DOCUMENT) {
         break;
      }
   }
 
   return list.toArray(new String[list.size()]);
}

In short, this code creates an instance of PendingIntent, IntentFilter for TECH_DISCOVERED action and all MIME types (see */*), and loads list of supported technologies from file specified earlier. Those objects are then used in onResume and onPause methods to enable and disable foreground dispatching so the application could handle the Intent before others.

Handling NFC intent

Reading NFC tags is easy. Android provides classes to read tags from some technologies such as those specified earlier in techlist.xml. In this post I will also show an example that utilizes the MifareClassic class. MIFARE Classic[4] is a standard that defines tags with blocks of data that can be written to. The one that is commonly used is a MIFARE Classic 1K which can hold 1 KB in 16 sectors with 4 blocks each. Each sector is secured by pair of 48-bit keys – first for read access and second for write access. There are 3 commonly used keys that by default protect all sectors and allow the access to them if hadn’t been changed – KEY_DEFAULT, KEY_MIFARE_APPLICATION_DIRECTORY and KEY_NFC_FORUM.

Ok, lets try now to handle an Intent with RFID tag. First of all, there are two moments when Activity can handle an Intent. First is when Activity is registered as a handler for this type of intents and second is when Activity is already on the screen. To handle both situations add following code to your Activity class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Override
public void onCreate(Bundle savedInstanceState) {
   super.onCreate(savedInstanceState);
 
   /* ... */
 
   // Passing intent
   Intent intent = getIntent();
   resolveIntent(intent);                 // This handles first situation
}
 
@Override
public void onNewIntent(Intent intent) {
   resolveIntent(intent);                 // This handles second situation
}

When Activity is created because of the NFC Intent it can be retrived in onCreate, but when Activity is already on the screen and handles this type of Intent you must override the onNewIntent method to handle it.

Ok, but how to exactly handle the tag Intent? Following function does that for MIFARE Classic tag:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
private void resolveIntent(Intent intent) {
 
   if(NfcAdapter.ACTION_TECH_DISCOVERED.equals(intent.getAction())) {
 
      Tag tag = intent.getParcelableExtra(NfcAdapter.EXTRA_TAG);
      MifareClassic mfc = MifareClassic.get(tag);
 
      try {
         mfc.connect();
 
         mLogger.pushStatus("");
         mLogger.pushStatus("== MifareClassic Info == ");
         mLogger.pushStatus("Size: " + mfc.getSize());
         mLogger.pushStatus("Timeout: " + mfc.getTimeout());
         mLogger.pushStatus("Type: " + mfc.getType());
         mLogger.pushStatus("BlockCount: " + mfc.getBlockCount());
         mLogger.pushStatus("MaxTransceiveLength: " + mfc.getMaxTransceiveLength());
         mLogger.pushStatus("SectorCount: " + mfc.getSectorCount());
 
         mStatus.setStatus("Reading sectors...");
 
         for(int i = 0; i < mfc.getSectorCount(); ++i) {
 
            if(mfc.authenticateSectorWithKeyA(i, MifareClassic.KEY_MIFARE_APPLICATION_DIRECTORY)){
               mLogger.pushStatus("Authorization granted to sector " + i + " with MAD key");
            } else if(mfc.authenticateSectorWithKeyA(i, MifareClassic.KEY_DEFAULT)) {
               mLogger.pushStatus("Authorization granted to sector " + i + " with DEFAULT key");
            } else if(mfc.authenticateSectorWithKeyA(i, MifareClassic.KEY_NFC_FORUM)) {
               mLogger.pushStatus("Authorization granted to sector " + i + " with NFC_FORUM key");
            } else {
               mLogger.pushStatus("Authorization denied to sector " + i);
               continue;
            }            
 
            for(int k = 0; k < mfc.getBlockCountInSector(i); ++k)
            {
               int block = mfc.sectorToBlock(i) + k;
               byte[] data = null;
 
               try {
 
                  data = mfc.readBlock(block);
               } catch (IOException e) {
                  mLogger.pushStatus("Block " + block + " data: " + e.getMessage());
                  continue;
               }
 
               String blockData = Common.getHexString(data);
               mLogger.pushStatus("Block " + block + " data: " + blockData);
            }
         }
         mfc.close();
 
      } catch (IOException e) {
         mLogger.pushStatus(e.getMessage());
      } finally {
         try {
            mfc.close();
         } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
         }
      }
   }
}

At first the tag is retrived from the Intent by method getParcelableExtra with argument of NfcAdapter.EXTRA_TAG. Then using static function from MifareClassic the object of this class is created from tag. The next step is to use connect method to establish the connection. At the time of connection the card must be close to the reader till the end of this method.
To actually read the data of any block the sector that this block belongs to must be authenticated with matching key. This is done with method authenticateSectorWithKeyA which expects an index of the sector and 6-byte authentication key. After authentication it is possible to read all 4 blocks from this sector which is done by method readBlock that expects an absolute index of the block (not relative to sector). Finally after doing all operations the close method should be invoked, even if an Exception occurs because it doesn’t close the connection by default and may cause a problem when trying to read the same tag with other technology.

Summary

Reading an RFID tag is pretty easy on Android devices as the SDK provides some high level API to do that. As I read the Android Beam is also supported with nice easy to use class. Unfortunately there is a problem with emulation of RFID tags because there’s no official API to for this kinds of operations as some people say[5]. On the other hand the device supports that and it is possible to build an Android with some support of this[6]. I shall try it when I would move to CyanogenMod.

The actual code of what I am doing with my phone and NFC can be found on GitHub here.

References

  1. http://en.wikipedia.org/wiki/Near_field_communication] []
  2. http://en.wikipedia.org/wiki/Radio-frequency_identification []
  3. http://developer.android.com/guide/topics/connectivity/nfc/nfc.html []
  4. http://en.wikipedia.org/wiki/MIFARE []
  5. http://forum.xda-developers.com/showthread.php?t=1368907 []
  6. http://forum.xda-developers.com/showthread.php?t=1281946 []

Let’s try English – short summary of last year.

Hello again.

It’s been a long time since the last post and a lot has changed, e.g. language in which I’m writing this post. Yes, the main change is the language that I want to gradually introduce into my blog. The explanation is simple and the same as always – wider audience. Since English is the second language that programmer is born with, anyone should be able to read it sooner or later. I’ve been asked once why I don’t write in English and my answer was that there will be time for that, and I think this is it. Practice in writing texts is a good way to improve yourself, writing in foreign language is even better so why not start now?

There were also changes in my life. In July 2011 I started working for Gigaset Communications as Junior Software Developer (or C++ Programmer it’s hard to tell ;)), hired by Power Media. I’m working on an outsourced project (almost since the beginning) codenamed Tomato. I must say that it’s very interesting project because it touches embedded system development with GUI on small screen, as well as webdev (it’s accessible by a website).

Apart from that I have also graduated as an Engineer of Computer Science from Wroclaw University of Technology and started second degree on the same faculty.

I must say that my interests have changed a little. I slightly moved away from computer graphics to general software development and embedded system development – it’s pretty on time, but I plan to get back to computer graphics because my master thesis involves it.

Future? I experimented a little with Android so some of upcoming posts should be about it.

Raytracer

Jak zwykle po długiej nieobecności w końcu pojawia się kolejna notka. Tym razem chciałbym zaprezentować Raytracer, który napisałem w ramach laboratorium z Zaawansowanej grafiki komputerowej. Program oprócz standardowego śledzenia promieni potrafi również generować teksturę proceduralną cegły dla podanego atrybutu (tę część napisałem z kolegą Adamem Jordankiem) oraz prowadzić obliczenia na wielu komputerach wykorzystując model klient-serwer.

Aplikacja do renderowania grafiki wykorzystuje między innymi moją własną biblioteczkę matematyczną, proste kontenery, a oprócz tego – do obsługi klienta i serwera –  sockety i wątki (w zależności od systemu ich odpowiednie implementacje).  Implementacja Raytracera wykorzystuje algorytm przecięcia promienia z trójkątem oraz implementację kd-tree znalezioną na tej stronie, które według mojego przekonania są na tyle wydajne i stabilne, że nie było sensu tego modyfikować. Wykorzystywany model oświetlenia jest efektem prób i błędów, ale myślę że wygląda całkiem znośnie. Zaimplementowane są wszystkie podstawowe elementy takie jak cienie, odbicia czy refrakcja.

Z ciekawszych rzeczy, które można znaleźć w kodzie to:

  • obsługa linii poleceń, która opiera się przede wszystkim na liście poleceń, gdzie każde polecenie zawiera nazwę i opis parametru oraz wskaźnik do funkcji, która implementuje jego obsługę.
  • implementacja klienta i serwera w oparciu o stany oraz przydział zadań do poszczególnych klientów
  • wczytywanie plików oparte o stany (łatwość dodawania nowych elementów)

Więcej informacji i paczkę można znaleźć tutaj.

Optymalizacja aplikacji C++ z wykorzystaniem AMD CodeAnalyst

W tej notce opiszę moją pierwszą porządną styczność z programem CodeAnalyst i przy okazji pokażę, w jaki sposób udało mi się nieco zoptymalizować napisaną przeze mnie aplikację implementującą rozwiązywanie problemu kolorowania grafu za pomocą algorytmu genetycznego.

CodeAnalyst - Okno główne programuCodeAnalyst jest programem służącym do profilowania aplikacji. Jego zadaniem jest zbieranie różnego rodzaju próbek w trakcie działania testowanej aplikacji, które są następnie przedstawiane w formie wykresu lub tabeli. Dzięki temu widać od razu, które miejsca aplikacji mają największy wpływ na badany parametr z dokładnością do wykonywanych instrukcji Assemblera. Program ten można znaleźć na stronie producenta. Jego główne okienko jest przedstawione na obrazku obok.

Jak już wspomniałem badaną aplikacją jest moja implementacja algorytmu ewolucyjnego użytego do rozwiązania problemu kolorowania grafu. Kod tej aplikacji wraz z przykładowym grafem znajduje się tutaj. Jest to kod, od którego wychodzę w tej notce, zatem nie uwzględnia on żadnych poprawek. Poniższa tabela zawiera średnie wyniki pomiaru cykli i czasu jakie zabiera główna pętla programu na dwóch maszynach:

Procesor System Kompilator Częstotliwość zegara Liczba cykli Czas
AMD Turion64 2 GHz MS Windows 7 msvc 25 MHz (QPF) 4111926149 cykli (QPC) 164,48 s
Intel Pentium 4 2,66 GHz Linux g++ 2659,98 MHz (cpuinfo) 268359191768 cykli (__rdtsc()) 100,89 s

Optymalizacja będzie dotyczyć głównie tej pierwszej platformy, ale postanowiłem z ciekawości sprawdzić jak zmiany będą wpływać na czas wykonywania się kodu również na drugiej platformie.

Analiza programu będzie polegać na szukaniu miejsc, w których spędza on najwięcej czasu. Zatem na początek należy uruchomić program CodeAnalyst, a następnie utworzyć projekt wybierając profil Time-based profile. Według mnie dobrze jest również zaznaczyć opcje Stop data collection when app exits oraz Profile the duration of the app execution. Dzięki temu CodeAnalyst poczeka z analizą wyników aż badana aplikacja skończy działanie. Po utworzeniu projektu można przystąpić do testów. Zatem po wyciszeniu/wyłączeniu niepotrzebnych aplikacji można wybrać z menu Profile -> Start lub kliknąć zieloną strzałkę.

Po zakończeniu działania aplikacji zostanie wyświetlone podsumowanie, które wygląda mniej więcej tak:
CodeAnalyst - System dataCodeAnalyst - System graph

Obie te zakładki przedstawiają dokładnie to samo, czyli procentowy udział próbek w każdej aplikacji/bibliotece/module, różnica występuje tylko w formie przedstawienia danych. Co w tym podsumowaniu jest interesującego? W tym widoku jeszcze nic, ale CodeAnalyst umożliwia podgląd szczegółów każdego z wymienionych wcześniej bytów, nawet dowolnego procesu wybranego z zakładki Processes. Jednak ponieważ ta notka obejmuje tylko jedną aplikacje, w dodatku tę, która zebrała najwięcej próbek, zatem przejdę teraz do niej. Oto co pokazuje się po dwukrotnym kliknięciu na jej proces:
CodeAnalyst - Testowana aplikacja

W tym widoku widać już nieco więcej. Są tu pokazane funkcje, które zabierały najwięcej czasu. Na samej górze widać jedną, która zabiera aż 40% próbek, jest to funkcja EvaluateConflicts(), która zlicza konflikty dla każdego osobnika w całej populacji. Warto się jej przyjrzeć z bliska:
CodeAnalysy - Podgląd funkcji EvaluateConflicts()

CodeAnalyst, wykorzystując dane zawarte w pliku .pdb, który powinien znajdować się obok pliku wykonywalnego, potrafi wyświetlić i dopasować próbki do odpowiedniego miejsca w kodzie. Można również podejrzeć wykonywany w tym miejscu kod Assemblera, co jest bardzo przydatne (żeby nie powiedzieć kluczowe) przy profilowaniu aplikacji. Co zatem widać na powyższym screenie? Jest tam coś co tak naprawdę powinno znajdować się tylko i wyłącznie w aplikacji kompilowanej w trybie Debug. To sprawdzanie poprawności odwołania się do elementu tablicy w klasie std::vector. Jest to nieco dziwne, ponieważ jest tam używany operator[], a standardowo ta wersja odwołania nie powinna być sprawdzana, w przeciwieństwie do funkcji at().
Okazuje się jednak, że implementacja STL dostarczana z kompilatorem msvc ma zaimplementowane takie sprawdzenie, które można co prawda wyłączyć flagą _SECURE_SCL ustawioną na 0, ale domyślnie ta opcja jest włączona. Więcej informacji można znaleźć tu lub bezpośrednio tutaj.

Poniższa tabela zawiera wyniki pomiarów cykli i czasu z wyłączeniem tego sprawdzania:

Procesor System Kompilator Częstotliwość zegara Liczba cykli Czas Zysk
AMD Turion64 2 GHz MS Windows 7 msvc 25 MHz (QPF) 3191994350 cykli (QPC) 127,68 s 22,37%
Intel Pentium 4 2,66 GHz Linux g++ 2659,98 MHz (cpuinfo) 269220460226 cykli (__rdtsc()) 101,21 s -0.32%

W przypadku msvc widać, że jest już lepiej, a przypadek gcc został praktycznie nietknięty, zatem nie posiada on domyślnie tego typu sprawdzania. Na poniższych screenach widnieją wyniki ponownego próbkowania aplikacji.
CodeAnalysy - Próbki w programie po pierwszej poprawceCodeAnalyst - Funkcja EvaluateConflicts po wprowadzeniu pierwszych poprawek

Jak można zauważyć, ta drobna poprawka pozwoliła kompilatorowi zinline’ować całą funkcję EvaluateConflicts(). Dzięki temu aplikacja wykonuje się szybciej o ok. 22 %. Kod tej wersji znajduje się pod tym linkiem.

Jednak na tym nie koniec poprawek, ponieważ jest jeszcze jedno miejsce, z którym da się coś zrobić. Otóż jeśli się przyjrzeć podsumowaniu całej aplikacji jeszcze raz, można zauważyć, że spędza ona dużo czasu w funkcji insert() drzewa std::_Tree, które jest implementacją zbioru (std::set) w bibliotece standardowej. Klasa ta jest używana w operatorze selekcji w celu wybrania losowych i niepowtarzających się osobników do turnieju. Co za tym idzie, funkcja insert() jest wywoływana minimum raz dla każdego wolnego miejsca w turnieju (w przypadku testowym jest 50 miejsc), aż do wypełnienia całej nowej populacji (tutaj 5000), czyli krótko mówiąc – dość często.

Rozwiązaniem, które przyjąłem w tym miejscu było całkowite pozbycie się klasy std::set na rzecz własnego sposobu wybierania losowych i różnych osobników do turnieju. Wynikiem tego jest taka oto klasa:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template<uint RANGE>
class RandomSet    // singleton
{
public:
    RandomSet()
    { 
        for(uint i = 0; i < RANGE; ++i)
        { m_aSet[i] = i; }
    }
 
    const uint* GetRandomSet(uint uCount, uint uInnerRange)
    {
        uint uTemp, uRand;
        for(uint i = 0; i < uCount; ++i)
        {
            uRand = rand() % (uInnerRange - i);
            uTemp = m_aSet[i];
            m_aSet[i] = m_aSet[i + uRand];
            m_aSet[i + uRand] = uTemp;
        }
        return m_aSet;
    }
 
private:
    uint m_aSet[RANGE];
};

Klasa ta wykorzystuje tablicę, w której zapisane są kolejno indeksy wszystkich osobników. Przy każdym wywołaniu funkcji GetRandomSet() tablica ta jest ponownie mieszana tak, by na jej początku znalazły się w miarę losowe wartości. Dzięki temu, że wybierane wartości są zamieniane z wartościami z początku tablicy, zbiór pozostaje pełny ale jest on stopniowo mieszany, przy czym największa różnorodność występuje zawsze na początku tablicy. To ostatnie nie ma tak naprawdę większego znaczenia, ponieważ najważniejsze jest to, żeby funkcja zwracała za każdym razem różne wartości.

Kolejna tabela zawiera wyniki testów po wprowadzeniu tych zmian:

Procesor System Kompilator Częstotliwość zegara Liczba cykli Czas Zysk
AMD Turion64 2 GHz MS Windows 7 msvc 25 MHz (QPF) 1144922576 cykli (QPC) 45,8 s 64,13 %
Intel Pentium 4 2,66 GHz Linux g++ 2659,98 MHz (cpuinfo) 105596054178 cykli (__rdtsc()) 39,7 s 60,78 %

W przypadku tej poprawki można już zaobserwować znaczny zysk i to na obu platformach (Windows – 64%, Linux – 61 %). Na poniższych obrazkach kolejne zrzuty z CodeAnalyst.
CodeAnalyst - Poprawka GetRandomSet - podsumowanie aplikacjiCodeAnalyst - Poprawka GetRandomSet - funkcja

Widać tutaj, że ilość próbkowanego kodu znacznie zmalała, a proporcje między funkcjami znów się zróżnicowały. Dzięki temu można zobaczyć, że funkcja GetRandomSet() zabiera znacznie mniej próbek niż EvaluateGeneration(). Kod tej wersji można pobrać stąd.

Pozostaje teraz ponownie zapytać, czy można coś tu jeszcze zoptymalizować? Może i można, ale prawdopodobnie zajmie to już trochę więcej czasu niż poprzednie poprawki. Jednym z oczywistych kroków jakie można tutaj wykonać to zastąpienie std::vector zwykłymi tablicami dynamicznymi, ale w tym przypadku zysk jest osiągalny tylko na Linuksie co pokazuje kolejna tabela:

Procesor System Kompilator Częstotliwość zegara Liczba cykli Czas Zysk
AMD Turion64 2 GHz MS Windows 7 msvc 25 MHz (QPF) 1144922576 cykli (QPC) 46,2 s -0.89 %
Intel Pentium 4 2,66 GHz Linux g++ 2659,98 MHz (cpuinfo) 105596054178 cykli (__rdtsc()) 37 s 6,78 %

Kod tego przypadku znajduje się tutaj.

I to właściwie tyle, wnioski? CodeAnalyst jest bardzo dobrym narzędziem do profilowania aplikacji, jest łatwy w obsłudze, a co najważniejsze jest za darmo. Oprócz tego warto zwracać uwagę na implementacje biblioteki standardowej w używanym kompilatorze, ponieważ można się nieco zdziwić, tak jak to miało miejsce w przypadku std::vector w tym przykładzie. Dodatkowo warto czasami poszukać innych rozwiązań dla niektórych problemów, ponieważ wyniki mogą okazać się całkiem zaskakujące.

Na koniec jeszcze taka małą dygresja odnośnie algorytmu ewolucyjnego – operator mutacji powinien testować prawdodpobieństwo dla każdego genu osobnika (czyli koloru węzła), a nie tak jak w tej implementacji, dla całego osobnika :).

Operacje na systemie plików w systemach Windows i Linux w C++

Tym razem notka o tym, w jaki sposób można wykonywać różne operacje w systemie plików w wymienionych w temacie systemach. Oczywiście każdy programista C/C++ zna funkcje wykonujące podstawowe operacje na plikach, takie jak:

  • odczyt, modyfikacja, zapis (funkcja fopen i poboczne oraz klasy fstream)
  • zmiana nazwy pliku lub katalogu (funkcja rename())
  • usunięcie pliku (funkcja remove())

Nieco więcej problemów sprawiają pozostałe operacje, takie jak np. pobranie pełnej ścieżki do pliku czy przeglądanie listy plików w katalogu, ponieważ w bibliotece standardowej nie ma do tego celu odpowiednich funkcji, zatem należy ich szukać w API systemu. Niestety co API to różne funkcje, ale zdarzają się i takie, które istnieją w obu systemach.

Na początek pobieranie pełnej ścieżki do bieżącego katalogu, czyli funkcja getcwd. Jej prototyp w systemie Windows jest następujący:

#include <direct.h>
char* _getcwd(char* _DstBuf, int _SizeInBytes);

a w systemie Linux:

#include <unistd.h>
char* getcwd(char* _DstBuf, int _SizeInBytes);

Jak widać prototyp obu funkcji jest identyczny, więc nic nie stoi na przeszkodzie utworzenia sobie odpowiedniego aliasu nazwy za pomocą typedef.

Trochę lepiej jest z funkcją stat() i jej strukturą o tej samej nazwie (thx C…, typedef needed), która istnieje w obu systemach. Funkcja ta służy do pobierania pełnych informacji o pliku, czyli np. daty modyfikacji, typu czy rozmiaru. Jej przykładowe użycie wygląda następująco:

1
2
3
4
5
6
7
8
9
10
11
#include <sys/stat.h>
typedef struct stat FileStatus; // thx C
 
/*...*/
FileStatus fileStatus;
if(stat(szFullPath.c_str(), &fileStatus) < 0)
{
    return;
}
 
unsigned int uFileSize = fileStatus.st_size;	// Pobranie rozmiaru pliku

Nieco gorzej jest z wyciąganiem listy plików w katalogu, ponieważ w tym przypadku oba systemy mają do tego różne funkcje. W przypadku systemu Windows wygląda to tak:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <windows.h>
/*...*/
 
WIN32_FIND_DATA info;
HANDLE hFind = FindFirstFile(szDirPath, &info);
 
if(INVALID_HANDLE_VALUE == hFind)
{
    printf("Error");
    return;
}
 
do
{
    if((info.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) != 0)
    {
        printf("Directory: %s\n", info.cFileName);
    }
    else
    {
        printf("File: %s\n", info.cFileName);
    }
}
while(FindNextFile(hFind, &info) != 0);
 
FindClose(hFind);

A w systemie Linux tak:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <dirent.h>
#include <string.h> // c-string operations
typedef struct dirent DirEntry;
typedef struct stat DirEntryStat; // thx C again
 
DIR* pDir;
pDir = opendir(szDirPath);
if(pDir == null)
{
    printf("Error");
    return;
}
 
DirEntry* pDirent;
DirEntryStat dirEntryStat;
while((pDirent = readdir(pDir)) != null)
{
    char buffer[255];
    strcpy(buffer, szDirPath);
    strcat(buffer, pDirent->d_name);	// Do ponizszej funkcji potrzebna jest sciezka z biezacego katalogu
 
    if(stat((buffer, &dirEntryStat) < 0)
    {
        printf("Error");
        continue;	// file corrupted... NEXT!
    }
 
    if((dirEntryStat.st_mode & S_IFDIR) != 0)	// Katalog
    {
        printf("Directory: %s\n", pDirent->d_name);
    }
    else if((dirEntryStat.st_mode & S_IFREG) != 0)	// Plik
    {
        printf("File: %s\n", info.pDirent->d_name);
    }
}
 
closedir(pDir);

Można zauważyć, że funkcja z WinAPI jest nieco przyjaźniejsza, ponieważ operuje na uchwycie do żądanego katalogu, w przeciwieństwie do funkcji Linuksowej, która po prostu zwraca nazwę tego co siedzi w katalogu i nic więcej.

Komunikacja za pomocą JSON z serwerem PHP w Javie

Jakiś czas temu pisałem pewną aplikację w Javie, która wykorzystywała format JSON do komunikacji z serwerem i wywoływania na nim pewnych procedur. Można rzec, że była to bardzo uboga wersja JSON-RPC czyli oficjalnego protokołu wywoływania procedur na zdalnej maszynie.

JSON, podobnie jak w XML, jest formatem przesyłu danych w postaci tekstu (czyli postaci odpowiedniej dla człowieka), ale w przeciwieństwie do niego jest lżejszy, co widać chociażby po tym, że sam jest opisywany za pomocą tylko kilku znaków. Pomimo tego, że format ten pochodzi z języka Java Script, istnieje masa bibliotek, które umożliwiają jego wykorzystanie w wielu językach, w tym właśnie w języku Java.

W przypadku aplikacji, którą pisałem, jednym z jej zadań było łączenie się z serwerem napisanym PHP i wywoływaniem odpowiednich procedur, które udostępniały jakieś dane. Format procedur był następujący:

“sessid”: “id”
”action”: “akcja”
”data”: “dane”

Przy czym dane również były zapisane w formacie JSON, ale były zorganizowane w odpowiednie struktury, które rozpoznawał serwer. Biblioteką, którą użyłem do wysyłania i odbierania danych była org.json, czyli pierwsza z dostępnych dla języka JAVA. W przypadku mojego kodu jej użycie ograniczyło się do użyciu tylko dwóch klas – JSONObject oraz JSONArray, z których za pomocą metody toString(), można wyciągnąć całą zapisaną hierarchię i następnie wysłać ją za pomocą odpowiedniego strumienia połączonego z serwerem.

Teraz przedstawię trochę kodu pokazującego w jaki sposób połączyć się z serwerem za pomocą HttpURLConnection oraz jak wykorzystać to połączenie do przesłania danych w formacie JSON. Na początek kod wysyłający zapytanie i odbierający odpowiedź serwera:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.io.*;		// BufferedReader, BufferedWriter, IOException, InputStreamReader, OutputStreamWriter
import.java.net.*;		// HttpURLConnection, URL
 
/*
...
*/
 
URL url = new URL(“http://mysweet.phpserver.com/”);
HttpURLConnection conn = (HttpURLConnection)url.openConnection();
 
conn.setDoOutput(true);			// Bo chcemy wysyłać
conn.setRequestMethod(“POST”);		// np. jako zapytanie POST
 
// Request
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(conn.getOutputStream()));
out.write(“Some post data/query”);
out.close();
 
// Response
BufferedReader in = new BufferedReader(new InputStreamReader(conn.getInputStream()));
 
String inputLine, answer = “”;
while((inputLine = in.readLine()) != null)
{
    answer += inputLine;
}
 
in.close();
conn.disconnect();

Jak widać nie ma tutaj zbyt dużo roboty, więcej zapewne dzieje się wewnątrz tych klas, ale przecież po to one są żeby się tym z grubsza nie przejmować. Kolejny kod przedstawia sposób tworzenia zapytań za pomocą wspomnianej biblioteki org.json:

1
2
3
4
5
6
7
8
9
10
11
12
import org.json.*;	//JSONArray, JSONException, JSONObject
 
/*
...
*/
 
JSONObject root = new JSONObject()
    .put(“sesid”, sesid)
    .put(“action”, action)
    .put(“data”, data);			 // data może być liczbą, stringiem lub obiektem JSONObject
 
string query = “json=+ root.toString();

Ostatecznie obiekt query zostanie przekazany jako zapytanie do wcześniej wspomnianego obiektu klasy BufferedWriter, dzięki któremu poleci do serwera. Odbieranie odpowiedzi jest równie proste:

1
2
3
4
5
6
7
8
9
10
11
string answer;
 
/* Odbieranie odpowiedzi
...
*/
 
JSONObject object = new JSONObject(answer);
int status = object.getInt(“status”);
string text = object.getString(“some_text”);
JSONObject node = object.getJSONObject(“some_struct”);
JSONArray array = object.getJSONArray(“some_array”);

I generalnie tak to wygląda, nie trzeba nic samemu parsować, ponieważ wszystko zapewnia kilka gotowych już klas – największa zaleta obiektowych języków programowania.

Visual Editor dla Eclipse

visual_editorSwego czasu do pisania aplikacji okienkowych w Javie (głównie z musu) korzystałem z NetBeans i jego edytora graficznego, jednak w przypadku ostatniego projektu na laboratoria postanowiłem przetestować pewną alternatywę, czyli Visual Editor dla Eclipse.

Visual Editor jest (jak większość dodatków do Eclipse) wtyczką, która ma na celu automatyczne generowanie kodu wykorzystującego bibliotekę okienek Swing. Niestety okazuje się, że mimo wersji 1.5 dla Eclipse Helios jest to raczej prototyp działający trochę na siłę niż poprawna wersja Release.

Jego największą wadą jest dość wysoka niestabilność, co potrafi owocować widokiem okienek jak na obrazku obok niemal co chwila (tak, korzystałem z wersji x64). Drugą rzeczą, która boli jest to, że zagnieżdżone ve_errorokienko zostawia swoja kotwiczkę jako osobny proces, który siedzi sobie jako zupełnie osobna aplikacja w pasku zadań i skutecznie blokuje możliwość użycia skrótu alt+tab, a w przypadku zmiany edytowanych okienek, powoduje wymienione crashe. Kolejną wadą, trochę drobniejszą, jest generowany kod, który, dla większej ilości komponentów i ich właściwości, niestety wygląda jak makaron  (chociaż organizacja na zasadzie statycznych wartości, tudzież singletonów jest dość fajnym rozwiązaniem.

Z zalet Visual Editora mogę wymienić chyba głównie to że jest, a co do samego wyglądu i integracji z Eclipse, to oprócz osobnego procesu dla okienka i crashów, komponuje się to w miarę wygodnie.

Tak przy okazji narzekania na tworzenie okienek w Javie – dlaczego nikt nie wymyślił obliczania minimalnego rozmiaru okna na podstawie minimalnych rozmiarów zawartych w nim komponentów, to naprawdę ułatwiłoby życie.

Własne repozytorium Gita na Linuksie

W tej notce postaram się opisać w jaki sposób, krok po kroku, postawić główne repozytorium Gita na własnym serwerze z zainstalowanym systemem linux (na przykładzie Slackware, z którego korzystam, ale myślę, że nie będzie problemów na innych dystrybucjach). Repozytorium nie będzie wykorzystywać interfejsu webowego i nie będzie uwzględniać podziału na konta, ale będzie wystarczającą alternatywą dla publicznego repozytorium w serwisie GitHub. Jednak zaczynając od początku wypadałoby powiedzieć kilka słów o tym czym jest Git.

Git jest jednym z kilku systemów kontroli wersji (SVN, Mercurial), czyli narzędzi służących do śledzenia zmian w kodzie źródłowym. Jego głównym zadaniem jest łączenie i modyfikacja zmian, a w razie błędu, umożliwienie przywrócenia poprzedniej, działającej wersji. Jedną z bardzo ważnych cech Gita jest to, że wszystkie zmiany są przechowywane lokalnie, dzięki czemu nie wymaga on do działania połączenia z głównym repozytorium. W porównaniu do Subversion, z którego do tej pory korzystałem, jest również szybszy i nie występują w nim problemy z łączeniem równoległych wersji (branchy).

Wracając jednak do tematu, na początek wypadałoby się upewnić czy na komputerze, na którym chcemy zainstalować Gita jest jedna z jego nowszych wersji. Ma to związek z przeniesieniem wewnętrznych plików wykonywalnych z katalogu /usr/bin/ do /usr/libexec/git-core/.

Instalacja Gita

Tak więc na początek pobieramy paczkę z git-core z tej strony, za pomocą polecenia:

wget http://kernel.org/pub/software/scm/git/git-1.7.4.1.tar.bz2

i ją rozpakowujemy:

tar –xvf git-1.7.4.1.tar.bz2

następnie przechodzimy do tego katalogu i (po przeczytaniu README oraz INSTALL), wykonujemy następujące polecenia:

./configure && make && make prefix=/usr install install-doc install-html install-info

Tutaj można napotkać problem przy instalowaniu dokumentacji, jak to miało miejsce u mnie. Rozwiązanie tego problemu znajduje się na tej stronie.

W tym momencie Git powinien być już zainstalowany, w przypadku gdy mieliśmy na dysku starą wersję, która pliki wykonywalne przechowuje w katalogu /usr/bin/, należy je ręcznie skasować, żeby nie sprawiały problemu. Jeśli jest to możliwe, można je rozpoznać po datach modyfikacji, po czym na koniec powinny zostać tam następujące pliki:

git
git-cvsserver
git-receive-pack
git-shell
git-upload-archive
git-upload-pack
gitk

Konto shellowe Git

Kolejnym krokiem jest utworzenie odpowiedniego konta shellowego, dzięki któremu będzie można połączyć się z repozytorium za pomocą protokołu ssh. Konto należy utworzyć z uid i gid równymi 9418 oraz git-shell jako programem startowym:

groupadd git –g 9418
useradd git –u 9418 –g git –c git –d /home/git –s /usr/libexec/git-core/git-shell
passwd –d git

Istotna jest ostatnia komenda, ponieważ bez niej nie uda się nam połączyć z repozytorium. Następnie tworzymy repozytorium i nadajemy prawa:

chown git:git /home/git/
chmod 700 /home/git/
mkdir /home/git/base/
chown git:git /home/git/base/
chmod 775 /home/git/base/

Kolejnym krokiem jest utworzenie właściwego repozytorium, robi się to za pomocą poleceń:

mkdir /home/git/base/repo.git
cd /home/git/base/repo.git
git init –-bare -–shared
sudo chmod -R g+ws *
sudo chgrp -R git *

Repozytorium jest już gotowe, niestety jeszcze nie można się z nim połączyć, ponieważ konto git nie posiada hasła. W celu umożliwienia łączenia się do repozytorium należy skorzystać mechanizmu autoryzacji sesji ssh za pomocą klucza prywatnego.

Autoryzacja za pomocą klucza prywatnego

W tym celu należy na każdej maszynie, z której będziemy się łączyć, utworzyć dwa klucze rsa, jeden publiczny drugi prywatny. Nie będę tego opisywał w tej notce, ponieważ jest to fajnie wyjaśnione na stronie GitHuba, w wersji dla systemu windows i linux. Opiszę natomiast w jaki sposób dodać te klucze do konta git na serwerze, umożliwiając tym autoryzację.

Na początek należy utworzyć w katalogu /home/git/ katalog .ssh, w nim plik authorized_keys i nadać im odpowiednie prawa:

mkdir /home/git/.ssh
chmod 700 /home/git/.ssh/
touch /home/git/.ssh/authorized_keys
chmod 600 /home/git/.ssh/authorized_keys
cat id_rsa.pub >> /home/git/.ssh/authorized_keys
chown –R git:git /home/git/.ssh/

Gdzie id_rsa.pub to klucz publiczny skopiowany z komputera klienckiego.

I to by było na tyle, w tym momencie można już wysyłać dane do repozytorium, którego adres jest następujący:

git@adres_serwera:base/repo.git

Źródła:
[1] http://forums.freebsd.org/showthread.php?t=10810
[2] http://stackoverflow.com/questions/897477/installing-git-on-os-x
[3] https://wincent.com/wiki/Updating_to_Git_1.6.0.1
[4] http://mapopa.blogspot.com/2009/10/git-insufficient-permission-for-adding.html

NIne 3 SceneGraph – paczka

Tym razem krótki wpis wraz z aplikacją przedstawiającą zaimplementowany SceneGraph. Różnica między tą a poprzednią wersją jest taka, że do obracającego modelu Tiny (postać) został podpięty model LandShark (statek) dzięki czemu zaczął on latać nad planszą zgodnie z obrotem Tiny. Dodatkowo pod ten ostatni można podpiąć kamerę, którą nie traci swobodnego ruchu, co pozwala poruszać się po nowym lokalnym układzie współrzędnych. Hierarchię modeli można zobaczyć na poniższym obrazku:

SceneGraphTree

Odnośnie sterowania odsyłam do ReadMe. Aplikację można pobrać stąd.

Data-Oriented-Design – SceneGraph proof of concept

Jakiś czas temu postanowiłem do swojego silnika dołączyć SceneGraph, którego zadaniem byłaby hierarchizacja modeli (w relacji rodzic-dzieci) występujących na scenie oraz aktualizacja ich macierzy świata. Generalnie taki graf zawiera nieco więcej informacji, takich jak na przykład bryły otaczające wraz z drzewem ósemkowym, na podstawie których można odrzucić modele niebędące w zasięgu kamery, jeszcze przed renderowaniem całej sceny. Jednak aktualnie zależało mi na zaimplementowaniu samej podstawy, czyli macierzy świata, ale w sposób zorientowany na dane, jak ma to miejsce w prezentacji Pitfalls of Object-Oriented Programming.

Hierarchizacja sceny polega na zebraniu wszystkich elementów sceny i połączeniu ich w drzewo, które składa się z korzenia oraz węzłów potomnych. W takim drzewie każdy rodzic oddziałuje bezpośrednio na swoje dziecko, czyli w tym przypadku transformacja, którą przechowuje rodzic ma wpływ na transformację przechowywaną przez dziecko, dla D3DX wygląda to tak:

D3DXMatrixMultiply(&childWorldMatrix, &childLocalMatrix, &parentWorldMatrix);

Istnieje kilka sposobów na powiązanie węzłów SceneGraph z elementami sceny. Najprostszym z nich jest struktura SGNode, której instancję można umieścić w klasie reprezentującej jakiś element sceny. Taka struktura wygląda następująco:

1
2
3
4
5
struct SGNode
{
   SGNode* pSibling, pChild;
   D3DXMATRIX localMatrix, worldMatrix;
};

Ponieważ sceny zwykle nie są statyczne, każdy taki węzeł powinien być aktualizowany co klatkę. Do tego celu powinna służyć odpowiednia funkcja klasy zarządzającej drzewem, której zadaniem będzie przejście rekursywnie po całym drzewie i zaktualizowanie danych. Oto przykład takiej funkcji:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void updateNodes(SGNode* pRoot)
{
   SGNode* pNode = pRoot->pChild;
 
   while(pNode != null)
   {
      D3DXMatrixMultiply(&pNode->worldMatrix, &pNode->localMatrix, &pRoot->worldMatrix);
      updateNodes(pNode);
      pNode->pSibling;
   }
}
 
// Wywołanie na korzeniu
updateNodes(m_pRoot);

Ten prosty przykład wystarczy by zauważyć problem, który został poruszony w wymienionej prezentacji. Chodzi przede wszystkim o skakanie po pamięci wskaźnikami, które są dość obficie używane w takiej implementacji. Powoduje to cache-missy, zwłaszcza w przypadku, gdy każdy węzeł jest alokowany osobno.

Rozwiązaniem tego, jak można się domyślić, jest umieszczenie tych danych w sposób liniowy, tak jak ma to miejsce w wymienionej prezentacji. Ważne jest również, aby dane były rozdzielone i uszeregowane w kolejności ich późniejszej aktualizacji.

W swoim silniku rozwiązałem to wykorzystując uchwyty, a węzły traktując jak każdy inny zasób, który można tworzyć i niszczyć. Wszystko to znajduje się w jednej klasie, która wygląda następująco:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class NSceneGraph
{
   struct NSceneGraphNode
   {
      NSize_t   uChild,
            uSibling;
      NSize_t uIndex;            // Indeks do tablic danych
      NSize_t uNext;             // Indeks następnego węzła
   };
 
public:
   NRESULT InitSceneGraph();
 
   void Release();
 
   NRESULT CreateNode(NHSceneGraphNode& hNode);
 
   void ReleaseNode(NHSceneGraphNode hNode);
 
   void ChangeParent(NHSceneGraphNode hNode);
 
   void ChangeParent(NHSceneGraphNode hNode, NHSceneGraphNode hParent);
 
   NMMatrixPP GetLocalMatrix(NHSceneGraphNode hNode);
 
   void SetLocalMatrix(NHSceneGraphNode hNode, NMMatrixPP matrix);
 
   NMMatrixPP GetWorldMatrix(NHSceneGraphNode hNode);
 
   const NMMatrix* GetWorldMatrixPtr(NHSceneGraphNode hNode);
 
   // Funkcja aktualizuje macierze world i inne dane
   void Update();
 
   // Funkcja porządkuje drzewo tak, by przechodzenie wszerz było liniowe i cache-friendly
   NRESULT ApplyChanges();
 
private:
   NRESULT ResizeArrays(NSize_t uSize);
 
   void AddSubtree(NSize_t uNode, NSize_t uNewParent);
 
   void RemoveSubtree(NSize_t uNode);
 
   void SetChildIndex(NSize_t uNode, NSize_t uChild)
   {
      m_aSceneNodes[uNode].uChild = uChild;
   }
 
   NSize_t GetChildIndex(NSize_t uNode)
   {
      return m_aSceneNodes[uNode].uChild;
   }
 
   void SetSiblingIndex(NSize_t uNode, NSize_t uSibling);
 
   NSize_t GetSiblingIndex(NSize_t uNode);
 
   void SetDataIndex(NSize_t uNode, NUint32 uIndex);
 
   NSize_t GetDataIndex(NSize_t uNode);
 
   void SetNextIndex(NSize_t uNode, NSize_t uNext);
 
   NSize_t GetNextIndex(NSize_t uNode);
 
   bool RemoveSubtree(NSize_t uRoot, NSize_t uNode);
 
private:
   NStableDataVector<NSceneGraphNode> m_aSceneNodes;
 
   bool m_bDirty;
   NSize_t m_uArraysSize;
   NAlignedDynamicTable<NMMatrix> m_aLocalMatrices;
   NAlignedDynamicTable<NMMatrix> m_aWorldMatrices;
};

Teraz przydałoby się wyjaśnienie co do tego kodu. Po pierwsze nie ma tutaj wskaźników, ponieważ jednym z założeń silnika jest wykorzystywanie większych obszarów pamięci zamiast pojedynczych alokacji. Z tego wynika założenie o uchwytach, co implikuje wykorzystanie w przedstawionym kodzie indeksów. NStableDataVector reprezentuje kontener, którego kluczowym założeniem jest niezmienność pozycji przechowywanych danych, dzięki czemu uchwyty pozostają ważne przez cały czas działania aplikacji. NAlignedDynamicTable jest natomiast klasą, która odpowiada za tworzenie i obsługę tablicy przechowującej różne dane (w tym przypadku macierze), które wymagają wyrównanego adresu.

Wracając jednak do samego drzewa sceny – ponieważ jego głównym założeniem jest implementacja rozwiązań z wymienionej prezentacji, dane zostały podzielone na kilka odpowiednich tablic, a indeksy do tych tablic zostały dodane do węzła. Wszystkie nowo utworzone węzły są potomkami węzła głównego, a zmiana rodzica jest transakcją, która usuwa podany węzeł i od razu dodaje go jako dziecko nowego rodzica (funkcja ChangeParent()).

Kluczową funkcją tej klasy jest ApplyChanges(), jej zadaniem ułożenie danych w taki sposób, aby zredukować liczbę cache-missów do minimum, wygląda ona tak:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
NRESULT NSceneGraph::ApplyChanges()
{
   NAssert(m_bDirty != false, "Needless call of this function");
 
   NRESULT result;
   // Temp arrays
   NDataQueue<NSize_t> tempQueue;
   NAlignedDynamicTable<NMMatrix> tempLocalMatrices;
   NAlignedDynamicTable<NMMatrix> tempWorldMatrices;
 
   if(NFAILED(result = tempLocalMatrices.Create(m_aLocalMatrices.GetSize(), MATRIX_ALIGNMENT))
   || NFAILED(result = tempWorldMatrices.Create(m_aWorldMatrices.GetSize(), MATRIX_ALIGNMENT))
   || NFAILED(result = tempQueue.Create(m_uArraysSize / 2, 0)))
   {
      tempLocalMatrices.Release();
      tempWorldMatrices.Release();
      tempQueue.Release();
      return result;
   }
 
   tempLocalMatrices[0] = m_aLocalMatrices[0];
   tempWorldMatrices[0] = m_aWorldMatrices[0];
 
   // Główny algorytm
   NSize_t uRootNode = 0;
   tempQueue.PushElement(GetChildIndex(uRootNode));
 
   SetNextIndex(uRootNode, GetChildIndex(uRootNode));
 
   NSize_t uNext = uRootNode;
   for(NUint32 i = 1; !tempQueue.IsEmpty(); )
   {
      NSize_t uNode = *tempQueue.GetFront();
      tempQueue.PopElement();
 
      for(; uNode != NMAX_SIZE_T; ++i)
      {
         SetNextIndex(uNext, uNode);
 
         tempLocalMatrices[i] = m_aLocalMatrices[GetDataIndex(uNode)];
         tempWorldMatrices[i] = m_aWorldMatrices[GetDataIndex(uNode)];
         SetDataIndex(uNode, i);
 
         if(GetChildIndex(uNode) != NMAX_SIZE_T)
         {
            tempQueue.PushElement(GetChildIndex(uNode));
         }
 
         uNext = GetNextIndex(uNext);
         uNode = GetSiblingIndex(uNode);
      }
   }
   SetNextIndex(uNext, NMAX_SIZE_T);
 
   m_aLocalMatrices.Release();
   m_aWorldMatrices.Release();
   tempQueue.Release();
 
   m_aLocalMatrices = tempLocalMatrices;
   m_aWorldMatrices = tempWorldMatrices;
   m_bDirty = false;
 
   Update();
 
   return NRV_SUCCESS;
}

Powyższa funkcja została wyrwana prosto z pliku źródłowego. Jak widać przechodzi ona całe drzewo wszerz porządkując dane (macierze) oraz aktualizując indeks danych i następnego węzła. Najważniejszym faktem dotyczącym tej funkcji jest to, że powinna być wywołana po wszystkich czynnościach związanych z dodawaniem, usuwaniem lub przenoszeniem węzłów. Dane uporządkowane można później wielokrotnie uaktualniać za pomocą funkcji Update(), która nie będzie posiadać narzutu związanego ze skakaniem po danych (pozostaje tylko skakanie po węzłach, które same w sobie nie są duże).

Funkcja ta wygląda w tym przypadku tak:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void NSceneGraph::Update()
{
   NAssert(m_bDirty == false, "Call this function before running updates");
 
   NSize_t uParentNode = 0;
 
   while(uParentNode != NMAX_SIZE_T)
   {
      NSize_t uNode = GetChildIndex(uParentNode);
 
      while(uNode != NMAX_SIZE_T)
      {
         NSize_t uDataIndex = GetDataIndex(uNode);
         // Macierze globalne
         m_aWorldMatrices[uDataIndex] = NMMatrixMul(m_aLocalMatrices[GetDataIndex(uNode)], m_aWorldMatrices[GetDataIndex(uParentNode)]);
 
         uNode = GetSiblingIndex(uNode);
      }
 
      uParentNode = GetNextIndex(uParentNode);
   }
}

Cały algorytm przechodzenia po tym drzewie polega na aktualizacji każdego dziecka dla bieżącego rodzica. Dzięki informacji o następnym węźle przechodzenie po drzewie odbywa się poziom po poziomie.

Jak widać cały problem podejścia zorientowanego na dane udało się umieścić w jednej klasie, co więcej funkcja porządkująca dane nie wymaga częstego wywoływania, ponieważ najprawdopodobniej będzie to miało miejsce w przypadku ładowania/usuwania sceny. Narzut związany z korzystaniem z uchwytów i indeksacją również można zredukować przed dodanie funkcji zwracających wskaźnik na żądane dane, które po każdym wywołaniu ApplyChanges() należy zaktualizować.