(Diese Seite steht in keinerlei Weise offiziell in Verbindung mit der Fachhochschule Bingen)

Inhalt

  1. Computergrafik
  2. Algorithmen und Datenstrukturen

Computergrafik

Im Rahmen des Studiums wird das Lehrfach Computergrafik (Grafische Datenverarbeitung) angeboten. Der praktische Schwerpunkt liegt in der Verwendung der OpenGL (Open Graphics Library) API.

Ein Thema wenn es um Texturen geht, ist das Einlesen von Bilddateien um diese als Texturen zu verwenden. Da es da keinerlei Unterstützung von der OpenGL API dafür gibt muss man diese Funktionalitäten selber programmieren. Da das Windows Bitmap Format ein weit verbreitetes und einfaches Format ist, habe ich eine C++ Klasse erstellt welche Bitmaps laden kann und diese als RAW Bitmap im 32 Bit RGBA Format speichert die dann direkt von OpenGL verwendet werden kann.

Bitmaploader Klasse (CBitmap)

Unterstützt werden Bitmaps mit folgenden Formaten: 1 Bit, 4 Bit, 8 Bit (auch RLE kodiert), 16 Bit, 24 Bit sowie 32 Bit mit Alphakanal. Letzteres wird zwar offiziell von der extern Spezifikation nicht unterstützt und es gibt somit fast kein Grafikprogramm welches 32 Bit Bitmaps mit Alphakanal erzeugen kann, jedoch gibt es 2 Anhaltspunkte dass dies doch gültig ist. Zum einen unterstützt das .NET Framework 2.0 das Laden und Speichern von 32 Bit Bitmaps mit Alphakanal. Zum anderen enthält die Spezifikation auch eine AlphaMask in der angegeben wird, wie viele Bits als Alphakanal verwendet werden.

Dies Masken sind gültig für 16 Bit und für 32 Bit Bitmaps in Kombination mit dem Kompressionstyp BI_BITFIELDS. Die Masken sehen dann beispielsweise wie folgt aus:

Für 32 Bit Bilder:
	
Red Mask     = 0x000000FF
Green Mask   = 0x0000FF00
Blue Mask    = 0x00FF0000
Alpha Mask   = 0xFF000000

Für 16 Bit Bilder:

Red Mask     = 0x000F
Green Mask   = 0x00F0
Blue Mask    = 0x0F00
Alpha Mask   = 0xF000

Da laut Spezifikation das oberste Byte in 32 Bit Bitmaps nicht verwendet wird, kann man dieses ebenfalls als Alphakanal verwenden. Unterstützt werden von mir beide Alphakanal-Varianten.

Die Verwendung der Klasse ist einfach. Geladen wird eine Datei indem dem Konstruktor der Name der zu ladenden Bitmapdatei übergeben wird, bzw. in dem diese manuel mit der Methode Load() geladen wird.

#include "bitmap.h"
...
CBitmap Bmp = CBitmap("test.bmp");
glGenTextures(1, &FirstTexture);
glBindTexture(GL_TEXTURE_2D, FirstTexture);

...	

glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, Bmp.GetWidth(), Bmp.GetHeight(), 0, GL_RGBA, GL_UNSIGNED_BYTE, Bmp.GetBits());

Über die Methode SetBits() lassen sich die Bilddaten auch ändern. Übergeben wird eine Maske der jeweiligen Farbkomponenten welche zum einen angibt, wie viele Bits jeder Farbkanal benötigt und wie dieser kodiert ist. Intern wird dieser wieder in 32 Bit RGBA Daten umgewandelt.

unsigned short int Bits[128][128] = {0};
for (int x = 0; x < 128; x++) {
	for (int y = 0; y < 128; y++) {
		unsigned int r, g, b;
		HsvToRgb((y * 360.0) / 128.0, 1.0, (float) x / 128.0, r, g, b);
		Bits[x][y] = r & 0x000f | (g << 4) & 0x00f0 | (b << 8) & 0x0f00 | (0xf << 12) & 0xf000;
	}
}
Bmp.SetBits(Bits, 128, 128, 0x000f, 0x00f0, 0x0f00, 0xf000);
Bmp.Save("test.bmp");

Es wird ein 128 x 128 Pixel Bild erzeugt und gemäß obiger Formel mit Daten gefüllt. Im obigen Beispiel werden 4 Bit pro Farbkanal verwendet, also 16 Bit insgesamt. Diese werden intern auf 32 Bit hochgerechnet.

Wird ein Bitmap mit einer anderen Fartiefe als 32 Bit benötigt, kann diese mit GetBits() und GetBitsWithPalette() in ein anderes Format konvertiert werden. Ersteres unterstützt das 16, 24 und 32 Bit Format, letzteres unterstützt die palettenbasierenden Formate mit 4 und 8 Bit Farbtiefe. Es wird weder Dithering verwendet noch werden optimierte Paletten verwendet.

Bmp.GetBitsWithPalette(0, BufferSize, Palette, PaletteSize, 8); // Puffergröße ermitteln
unsigned char* Buffer = new unsigned char[BufferSize];

if (Bmp.GetBitsWithPalette(Buffer, BufferSize, Palette, PaletteSize, 8)) {
	Bmp.Save("test.bmp");
}

Konvertiert das Bitmap in ein 8 Bit palettenbasiertes Bitmap ohne Verwendung von Dithering. Verwendet wird eine automatisch erzeugte Standardpalette mit der Farbgewichtung 3-3-2.

Sonstige Methoden der CBitmap Klasse sind GetWidth(), GetHeight(), SetAlphaBits(). Letztere setzt alle Alphawerte auf einen bestimmten vorgegebenen Wert.

Experimentell habe ich eine kleine Klasse erstellt, welche die Floyd-Steinberg Dithering realisiert. Übergeben wird eine 32 Bit RGBA Bitmap und eine beliebig große zu verwendende Palette welche die Qualität des Ditherings bestimmt.

#include "bitmap.h"
#include "dither.h"
...
BGRA *Palette = 0;
unsigned int PaletteSize = 0;
	
char *Buffer = 0;
unsigned int Size = 0;

if (Bmp.GetBitsWithPalette(0, Size, 8, Palette, PaletteSize)) {
	Buffer = new char[Size];
	if (Bmp.GetBitsWithPalette(Buffer, Size, 8, Palette, PaletteSize)) {
		CDither::DitherFloydSteinberg((RGBA*) Bmp.GetBits(), Bmp.GetWidth(), Bmp.GetHeight(), Palette, PaletteSize);
		delete [] Palette;
	}
	delete [] Buffer;
}

Wer die Klassen verändern oder erweitern möchte kann dies natürlich tun. Auf jeden Fall wäre es schön wenn ihr mir die Änderungen zu Verfügung stellen würdet.

Herunterladen

  • Bitmap-Klasse herunterladen
  • Dither-Klasse herunterladen

Algorithmen und Datenstrukturen

Implementierungen von verketteten Listen sind einer der oft benötigten Datenstrukturen in der Anwendungsprogrammierung. Um nicht von irgendwelchen Frameworks wie diversen Templates Libraries abhängig zu sein, habe ich eine eigene C++ Template basierte Klasse erstellt welche als eine doppelt verkettete Liste realisiert ist. Die Liste kann sowohl als Queue wie auch als Stack verwendet werden. Die Klasse ist natürlich offen für Erweiterungen. Zum Beispiel ist die Sortiermethode als SelectionSort implementiert welche man duch Mergesort oder Quicksort ersetzen könnte um eine höhere Suchlesitung zu erzielen. Ebenso könnte man diese Liste als Basis für eine CTree- oder CHash-Implementierung verwenden.

#include "Linkedlist.h"

...

struct CData {
	int a;
	int b;
	int c;
	...
};

CLinkedList<CData> List = new CLinkedList<CData>();

Erstellt eine verkettete Liste welche ihre Daten in CData speichert.

Das Hinzufügen von neuen Knoten kann z.B. mittels der Push() Methode geschehen. Bei den Methoden der Grundoperationen gibt es grundsätzlich immer 2 Überladungen. Die eine akzeptiert CData als Parameter, die andere ein CLinkedListItem<CData>

CData Test = {1, 2, 3, ...};
List->Push(Test);

...
CLinkedListItem<CData> Item = List->Push(new CLinkedListItem<CData>(List, Test));
Item->GetData();

Weitere Operationen von CLinkedListItem sind Pop(), Enqueue(), Dequeue(), Remove(), Insert(), Swap() sowie die Grundmethoden GetData(), Clone(), GetPrev() und GetNext()

Die meisten Methoden zum Einfügen und Entfernen gibt es sowohl in der CLinkedList wie als auch in der CLinkedListItem Klasse. Erstere beinhaltet natürlich weitere Methoden z.B. zum Suchen von Knoten. Dabei wir auf die interne Vergleichsmethode Compare() der Comperator-Klasse zurückgegriffen welche als zweiter Templateparameter übergeben wird

template <class T> class CMyComperator {
public:	
	static int Compare(T &a, T &b) {
		if (a < b) {
			return -1;
		} else if (a > b) {
			return 1;
		} else {
			return 0;
		}
	}
};


CLinkedList<CData> List = new CLinkedList<CData, CMyComperator>();

...

CLinkedListItem<CData> Item = List->Search(new CData(1, 2, 3, ...));

Eigene Vergleichsmethode definieren welche beispielsweise von der Such- oder Sortiermethode aufgerufen wird.

Herunterladen

  • Verkettete Liste herunterladen
  • Weitere Variante einer Implementierung für verkettete Listen herunterladen