JLI Spieleprogrammierung Foren-Übersicht JLI Spieleprogrammierung

 
 FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   BenutzergruppenBenutzergruppen 
 medals.php?sid=f53049cdbc8bd45a35d778693183f873Medaillen   RegistrierenRegistrieren   ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin 

[Softwareredering] Zeichnen eines Dreiecks
Gehe zu Seite 1, 2  Weiter
 
Neues Thema eröffnen   Neue Antwort erstellen    JLI Spieleprogrammierung Foren-Übersicht -> Tutorials
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
Otscho
Super JLI'ler


Alter: 35
Anmeldedatum: 31.08.2006
Beiträge: 338
Wohnort: Gummibären-Gasse
Medaillen: Keine

BeitragVerfasst am: 07.06.2008, 13:01    Titel: [Softwareredering] Zeichnen eines Dreiecks Antworten mit Zitat

Letzte Woche hat mich jemand gefragt, wie man am einfachsten Objekte, die aus lauter Dreiecken bestehen, in eine Collision-Map eintragen könnte.
Die Collision-Map war ein dynamisches Array vom Typ char mit der trivialen Größe width*height. Ich hab dann ein bisschen nachgedacht und mir sind schon bald drei verschieden Varianten eingefallen, mit denen man ein Dreieck auf die Map zeichnen könnte. Auf eine Weitere kam jemand Anderer.

In dem folgenden Tutorial werde ich ein Programm erstellen welches ohne Hilfe von fremden SDKs über die Konsole den Benutzer zur Eingabe der Daten für die das Erstellen der map und das Zeichnen des Dreiecks bittet, dieses Dreieck auf die vom Benutzer gewollte Art und Weise zeichnet und zum Schluss das Ergebnis in eine Bild-Datei namens Bitmap.bmp abspeichert. Der Code ist bewusst sehr einfach gehalten: Es gibt wenig einzellne Funktionen und da das meist in der main(..) stattfindet wird auch noch ein relativ linearer Code gewährleistet. Natürlich bin ich mir bewusst, dass dieses Programm nicht dem Standart des OOP erfüllt, aber dafür ist er leicht zu verstehen und auch Programmierneulinge die gerade erst Christians Buch gelesen haben, sollten damit nicht allzu viele Probleme haben. Wer also Klassendefinitionen oder Templates sucht, der sucht vergebens.
Den gesamten Quellcode findet man in der main.cpp.

Insgesamt brauchen wir nur zwei Headerdateien, welche in der C++ Standart Library enthalten sein sollten:

CPP:
#include <iostream>               // Für die Comunication mit dem Benutzer per Console
#include <fstream>               // Für das Abspeichern der Bitmap

using namespace std;            // Da hier viele Funktionen liegen (cout , cin, fstream)


Um Farbwerte und Vektoren speichern zu können benötigen wir noch ein paar Strukturen:

CPP:
// In diese Struktur werden unsere 2-dimensionalen Vektoren gespeichert
struct Vector2f{
   float x,y;
};

// Das selbe mit Integertypen (erspart uns an manchen stellen den nervigen "static_cast<int>")
struct Vector2i{
   int x, y;
};

// Und in die hier für unsere 24bit Farben (jeder Kanal bekommt ein char(=byte))
struct Color{
   char blue, green, red;
};

Bemerkung : Beim späteren Abspeichern als bmp-file werden die Farbkanäle in umgekehrter Reihenfolge in die Datei geschrieben.

Um uns den Code ewtwas zu erleichtern definieren wir noch 4 kleine Funktionen, die zwei Werte annimmt und uns einmal den kleineren zurück gibt und das andere Mal den Größerern. Durch überladen schreiben wir jeweils eine für Integer-Werte und eine für Floats:

CPP:
// Diese Funktionen liefern den kleineren Wert zweier Zahlen zurück
int min(int i1, int i2) {
   if(i1 < i2) return i1;
   return i2;
}

float min(float i1, float i2) {
   if(i1 < i2) return i1;
   return i2;
}

// Diese Funktionen liefern den größeren Wert zweier Zahlen zurück
int max(int i1, int i2) {
   if(i1 > i2) return i1;
   return i2;
}

float max(float f1, float f2) {
   if(f1 > f2) return f1;
   return f2;
}


Mit dieser Funktion können wir zwei Color-Strukturen testen, ob sie die gleiche Farbe enthalten. Ist das der Fall, wird true zurück gegeben:

CPP:
bool CompareColors(Color Color1, Color Color2) {
   return (Color1.red == Color2.red && Color1.green == Color2.green && Color1.blue == Color2.blue);
}


Die eigentlichen Zeichenoperationen werden in eigenen Funktionen zusammengefasst. Dazu aber später mehr. Hier müssen wir nur deren Prototypen angeben:
CPP:
// Diese Funktion zeichnet eine Linie zwischen "Point1" und "Point2" auf die bitMap "pcMap"
void DrawLine(Color* pcMap, int* pWidth, int* pHeigth, Vector2f Point1, Vector2f Point2, Color PenColor);

// Diese Funktion füllt den schon gezeichneten Rahmen eines Dreiecks (auch jede andere Figur mit einem geschlossenen Rahmen) 
void FillDrawenTriangleLineToLine(Color* pcMap, int* pWidth, int* pHeigth, Color cBorderColor, Color cFillColor);

// Diese Funktion macht das selbe wie die vorrige nur verwendetet diese eine andere Stategie und benötigt dazu einen Punkt innerhalb des Dreiecks
// (Funktioniert dafür viel besser als die Obrige ;) )
void FillDrawenTrianglePerPathfinding(Color* pcMap, int* pWidth, int* pHeigth, Color cBorderColor, Color cFillColor, Vector2i vCurrentPosition);

// Diese Funktion zeichnet ein ausgefülltes Dreieck, indem es jeden Pixel der sich innerhalb der 3 Geraden (AB, BC und CA) mit der Füllfarbe füllte
void DrawSolidTriangle(Color* pcMap, int* pWidth, int* pHeigth, Color cFillColor, Vector2f vA, Vector2f vB, Vector2f vC);

// Diese Funktion zeichnet ebenfalls ein ausgefülltes Dreieck. Bei wird das Dreieck von 2 Vektoren aufgespannt
void DrawSolidTriangleEx(Color* pcMap, int* pWidth, int* pHeigth, Color cFillColor, Vector2f vA, Vector2f vB, Vector2f vC);


Damit beim Speicher ein short auch wirklich 2 Bytes groß ist und nicht auf 4 Bytes gestreckt wird setzen wir noch das #pragma pack(2) an den Anfang unserers Codes.


Damit diese Tutorial nicht zu groß wird, poste ich jetzt einfach mal den ersten Teil der main(). Hier werden variablen Angelegt und per Konsole vom Benutzer folgende Eingaben verlangt:

1. Größe der Map (Breite und Höhe) ?
2. Koordinaten der drei Eckpunkte ?
3. Füllvariante ?
4. Gegebenenfalls fragen ob ein Rahmen um das Dreieck gewünscht wird, oder nicht ?

CPP:
int main() {
   
   // Die drei Eckpunkte unseres Dreiecks   
   Vector2f vA, vB, vC;

   // Die Größe unserer Map
   int width, height;

   // Die einzellnen Farben (für Hintergrund, Rahmen und Füllung)
   Color cBackgroundColor = {255, 255, 255};         // Weiß
   Color cBorderColor = {0, 0, 0};                  // Schwarz
   Color cFillColor = {255, 0, 0};                  // Blau

   // Speichert die Auswahl der Füllvariante
   int Variante = 0;

   // Ist ein zusätlicher Rahmen erwünscht ?
   bool AdditionalBorder = false;


   // Mit dem Benutzer plaudern
   cout << "Hallo\n\n";
   cout << "Wie gross soll die Bitmap werden ?\n";
   cout << "Bitte Breite eingeben\n";
   cin >> width;
   cout << "Bitte Hoehe eingeben\n";
   cin >> height;
   
   // Jetzt Punkte abfragen
   // Erster Punkt
   cout << "\nWo soll denn der erste Punkt liegen?\n";
   while(true) {
      cout << "Bitte die X-Koordinate eingeben\n";
      cin >> vA.x;
      if(vA.x < 0.0f) cout << "Scherzkeks - der Wert ist zu klein\n";
      else if(vA.x > width - 1) cout << "Netter Versuch - der Punkt wuerde ausserhalb des Bildes liegen\n";
      else break;
   }

   while(true) {
      cout << "Bitte die Y-Koordinate eingeben\n";
      cin >> vA.y;
      if(vA.x < 0.0f) cout << "Scherzkeks - der Wert ist zu klein\n";
      else if(vA.y > height - 1) cout << "Netter Versuch - der Punkt wuerde ausserhalb des Bildes liegen\n";
      else break;
   }

   // Zweiter Punkt
   cout << "\nWo soll denn der naechste Punkt liegen?\n";
   while(true) {
      cout << "Bitte die X-Koordinate eingeben\n";
      cin >> vB.x;
      if(vB.x < 0.0f) cout << "Scherzkeks - der Wert ist zu klein\n";
      else if(vB.x > width - 1) cout << "Netter Versuch - der Punkt wuerde ausserhalb des Bildes liegen\n";
      else break;
   }

   while(true) {
      cout << "Bitte die Y-Koordinate eingeben\n";
      cin >> vB.y;
      if(vB.x < 0.0f) cout << "Scherzkeks - der Wert ist zu klein\n";
      else if(vB.y > height - 1) cout << "Netter Versuch - der Punkt wuerde ausserhalb des Bildes liegen\n";
      else break;
   }

   // Schließlich noch der letzte Punkt
   cout << "\nSodala. Wo soll jetzt noch der letzte Punkt sein?\n";
   while(true) {
      cout << "Bitte die X-Koordinate eingeben\n";
      cin >> vC.x;
      if(vC.x < 0.0f) cout << "Scherzkeks - der Wert ist zu klein\n";
      else if(vC.x > width - 1) cout << "Netter Versuch - der Punkt wuerde ausserhalb des Bildes liegen\n";
      else break;
   }

   while(true) {
      cout << "Bitte die Y-Koordinate eingeben\n";
      cin >> vC.y;
      if(vC.x < 0.0f) cout << "Scherzkeks - der Wert ist zu klein\n";
      else if(vC.y > height - 1) cout << "Netter Versuch - der Punkt wuerde ausserhalb des Bildes liegen\n";
      else break;
   }

   // Dann noch die Zeichenvariante auswählen
   cout << "\nWelche Zeichenvariante wollen Sie verwenden ?\n";
   cout << "1 fuer Rahmen ausfuellen Linie für Linie\n";
   cout << "2 fuer Rahmen ausfuellen per Pathfinding\n";
   cout << "3 fuer Zeichnen nach algebrarischen Ungleichungen\n";
   cout << "4 fuer Zeichnen nach geometrischen Ungleichungen\n";
   cout << "5 fuer Nur Rahmen zeichnen\n";
   cout << "Bitte jetzt waehlen \n";
   cin >> Variante;
   cout << endl;

   // Falls Variante 3 oder 4 ausgewählt wurde, optional einen Rahmen anbieten
   if(Variante == 3 || Variante == 4) {
      cout << "Soll das Dreieck noch einen Rahmen bekommen ?";
      cout << "\"1\" fuer ja - \"0\" fuer nein\n";
      cin >> AdditionalBorder;
   }


   // Zusammenfassung (Den Benuzer über seine Eingabe informieren)
   cout << "\nZusammenfassung\n";
   cout << "Groesse der Bitmap: " << width << "x" << height << endl;
   cout << "Erster  Punkt: (" << vA.x << "|" << vA.y << ")\n";
   cout << "Zeiter  Punkt: (" << vB.x << "|" << vB.y << ")\n";
   cout << "Dritter Punkt: (" << vC.x << "|" << vC.y << ")\n\n";


Bemerkung: Auf Grund der Programmstabilität werden nur Koordinaten von Punkten angenommen, die auch innherhalb der Map liegen. Somit können wir ausschließen, dass wir später einmal auf einen ungültigen Speicher zugreifen.

Zu Beginn der Arbeit erstellen wir das Array für die map (hier : pcBitMap24) mit der Größe der angebenen Breite * Höhe . Anschließend füllen wir jedes Element der map mit der Hintergrundfarbe, die am Anfang im Code bestimmt wurde:

CPP:
Color* pcBitMap24 = new Color[width * height];

   // Setzten der Pixel auf die Hintergrundfarbe
   for(int i = 0; i < width * height; i++) {
      pcBitMap24[i] = cBackgroundColor;
   }


Bei den Zeichenoperationen müssen zwischen den 4 Varianten unterschieden werden. Wir prüfen dazu den Wert
Variante mithilfe einer Switch
CPP:
   switch(Variante) {


Der erste case verbindet zu erst die drei Eckpunkte zu einer Linie mit der Farbe cBorderColor und füllt dan diesen geschaffenen Rahmen per FillDrawenTriangleLineToLine(...) mit der Farbe cFillColor. Auf die Funktionsweise der einzellnen Funktionen komme ich später ausführlich zurück:

CPP:
      case 1:
            
            DrawLine(pcBitMap24, &width, &height, vA, vB, cBorderColor);
            DrawLine(pcBitMap24, &width, &height, vB, vC, cBorderColor);
            DrawLine(pcBitMap24, &width, &height, vC, vA, cBorderColor);

            // Nun machen wir uns ans Füllen
            FillDrawenTriangleLineToLine(pcBitMap24, &width, &height, cBorderColor, cFillColor);
         break;


Auf eine ähnliche Art funktioniert auch die 2. Variante. Nur muss hier noch ein Punkt innerhalb des Dreiecks angegeben werden. Dazu berechnen wir einfach den Mittelpunkt iV:

CPP:
      case 2:
            // Als erstes verbinden wir die drei Punkte mit einer Linie
            // Dafür gibt haben wir die Funktion "DrawLine(...)" bereitgestellt
            DrawLine(pcBitMap24, &width, &height, vA, vB, cBorderColor);
            DrawLine(pcBitMap24, &width, &height, vB, vC, cBorderColor);
            DrawLine(pcBitMap24, &width, &height, vC, vA, cBorderColor);

            // 2. Variante  mit "FillDrawenTrianglePerPathfinding"
            
            // Mittelpunkt des Dreiecks
            Vector2i iV;
            iV.x = static_cast<int>((vA.x + vB.x + vC.x) / 3);
            iV.y = static_cast<int>((vA.y + vB.y + vC.y) / 3);
            
            FillDrawenTrianglePerPathfinding(pcBitMap24, &width, &height, cBorderColor, cFillColor, iV);
         break;


Bei der 3. Variante können sofort die Eckpunkte der Funktion übergeben werden. Ein vorgezeichneter Rahmen ist hier nicht notwendig. Er kann aber gegebenenfalls nach Wunsch danach noch gezeichnet werden:

CPP:
      case 3:
            DrawSolidTriangle(pcBitMap24, &width, &height, cFillColor, vA, vB, vC);

            // evt. noch einen Rahmen zeichen
            if(AdditionalBorder) {
               DrawLine(pcBitMap24, &width, &height, vA, vB, cBorderColor);
               DrawLine(pcBitMap24, &width, &height, vB, vC, cBorderColor);
               DrawLine(pcBitMap24, &width, &height, vC, vA, cBorderColor);
            }
         break;


Ähnlich läuft es bei der 4. Variante. Nur wird hier DrawSolidTriangleEx(...) aufgerufen:

CPP:
      case 4:
            DrawSolidTriangleEx(pcBitMap24, &width, &height, cFillColor, vA, vB, vC);

            // evt. noch einen Rahmen zeichen
            if(AdditionalBorder) {
               DrawLine(pcBitMap24, &width, &height, vA, vB, cBorderColor);
               DrawLine(pcBitMap24, &width, &height, vB, vC, cBorderColor);
               DrawLine(pcBitMap24, &width, &height, vC, vA, cBorderColor);
            }
         break;


Bei der letzten Variante wird nur der Rahmen gezeichnet ohne diesen zu füllen:

CPP:
      case 5:
            DrawLine(pcBitMap24, &width, &height, vA, vB, cBorderColor);
            DrawLine(pcBitMap24, &width, &height, vB, vC, cBorderColor);
            DrawLine(pcBitMap24, &width, &height, vC, vA, cBorderColor);
         break;


   }



Schluss endlich müssen wir das Color-Map nur noch als Bitmap abspeichern.
Legen wir dazu erst mal den FileHeader an
Da erfahren wir von http://de.wikipedia.org/wiki/Windows_Bitmap folgendes:
Zitat:

0 WORD 2 Byte bfType ASCII-Zeichenkette "BM" (Dezimalwert 19778).
2 DWORD 4 Byte bfSize Größe der BMP-Datei in Byte. (unzuverlässig)
6 DWORD 4 Byte bfReserved 0
10 DWORD 4 Byte bfOffBits Offset der Bilddaten in Byte vom Beginn der Datei an.


Also erstellen wir eine Struktur dafür:
CPP:
   struct FileHeader{
      short bfType;
      int bfSize;
      int bfReserved;
      int bfOffBits;
   };


Und füllen diese dann auch gleich:
CPP:
   FileHeader m_FileHeader;
   m_FileHeader.bfType = 19778;
   m_FileHeader.bfSize = 14 + 40 + 3 * width * height;
   m_FileHeader.bfReserved = 0;
   m_FileHeader.bfOffBits = 14 + 40;


Als nächstes brauchen wir noch einen BITMAPINFOHEADER
Hier hilft ebenfalls ein Blick auf die allwissende Internetseite, dort heißt es weiter:


Zitat:
14 DWORD 4 Byte biSize 40 (Größe der BITMAPINFOHEADER-Struktur in Byte)
18 LONG 4 Byte biWidth Breite der Bitmap in Pixel.
22 LONG 4 Byte biHeight Der Betrag gibt die Höhe der Bitmap in Pixel an.
Ist der Wert positiv, so ist die Bitmap eine sogenannte "bottom-up"-Bitmap (die Bilddaten beginnen mit der untersten und enden mit der obersten Bildzeile). Dies ist die gebräuchlichste Variante.
Ist der Wert negativ, so ist die Bitmap eine "top-down"-Bitmap (die Bilddaten beginnen mit der obersten und enden mit der untersten Bildzeile).
26 WORD 2 Byte biPlanes 1 (Stand in einigen älteren Formaten wie PCX für die Anzahl der Farbebenen, wird aber für BMP nicht verwendet)
28 WORD 2 Byte biBitCount Gibt die Farbtiefe der Bitmap in bpp an; muss einer der folgenden Werte sein: 1, 4, 8, 16, 24 oder 32. Bei 1, 4 und 8 bpp sind die Farben indiziert. 16 und 32 bpp sind ungebräuchlich.
30 DWORD 4 Byte biCompression Einer der folgenden Werte:
0 (BI_RGB): Bilddaten sind unkomprimiert.
1 (BI_RLE8): Bilddaten sind lauflängenkodiert für 8 bpp. Nur erlaubt wenn biBitCount=8 und biHeight positiv.
2 (BI_RLE4): Bilddaten sind lauflängenkodiert für 4 bpp. Nur erlaubt wenn biBitCount=4 und biHeight positiv.
3 (BI_BITFIELDS): Bilddaten sind unkomprimiert und benutzerdefiniert (mittels Farbmasken) kodiert. Nur erlaubt wenn biBitCount=16 oder 32; ungebräuchlich.
34 DWORD 4 Byte biSizeImage Wenn biCompression=BI_RGB: Entweder 0 oder die Größe der Bilddaten in Byte.
Ansonsten: Größe der Bilddaten in Byte.
38 LONG 4 Byte biXPelsPerMeter Horizontale Auflösung des Zielausgabegerätes in Pixel pro Meter; wird aber für BMP-Dateien meistens auf 0 gesetzt.
42 LONG 4 Byte biYPelsPerMeter Vertikale Auflösung des Zielausgabegerätes in Pixel pro Meter; wird aber für BMP-Dateien meistens auf 0 gesetzt.
46 DWORD 4 Byte biClrUsed Wenn biBitCount=1: 0.
Wenn biBitCount=4 oder 8: die Anzahl der Einträge der Farbtabelle; 0 bedeutet die maximale Anzahl (16 bzw. 256).
Ansonsten: Die Anzahl der Einträge der Farbtabelle (0=keine Farbtabelle). Auch wenn sie in diesem Fall nicht notwendig ist, kann dennoch eine für die Farbquantisierung empfohlene Farbtabelle angegeben werden.
50 DWORD 4 Byte biClrImportant Wenn biBitCount=1, 4 oder 8: Die Anzahl sämtlicher im Bild verwendeten Farben; 0 bedeutet alle Farben der Farbtabelle.
Ansonsten:
Wenn eine Farbtabelle vorhanden ist und diese sämtliche im Bild verwendeten Farben enthält: deren Anzahl.
Ansonsten: 0.



Auch hierfür erstellen wir eine Struktur :
CPP:
   struct InfoHeader {
      int biSize;
      int biWidth;
      int biHeight;
      short biPlanes;
      short biBitCount;
      int biCompression;
      int biSizeImage;
      int biXPelsPerMeter;
      int biYPelsPerMeter;
      int biClrUsed;
      int biClrImportant;
   }
;

Jetzt noch anlegen und füllen :
CPP:
   InfoHeader m_InfoHeader;

   m_InfoHeader.biSize = 40;
   m_InfoHeader.biWidth = width;
   m_InfoHeader.biHeight = height;
   m_InfoHeader.biPlanes = 1;
   m_InfoHeader.biBitCount = 24;
   m_InfoHeader.biCompression = 0;
   m_InfoHeader.biSizeImage = 0;            // oder 14 + 40 + 3 * width * height
   m_InfoHeader.biXPelsPerMeter = 0;
   m_InfoHeader.biYPelsPerMeter = 0;
   m_InfoHeader.biClrUsed = 0;
   m_InfoHeader.biClrImportant = 0;


Nun das Ergebiss als Datei abspeichern.
Dazu eine Datei namens "Bitmap.bmp" erstellen:
CPP:
   fstream file("Bitmap.bmp", ios::out | ios::binary);

In die Datei schreiben (Zuerst den FileHeader, dann den InfoHeader und zum Schluss die map):

CPP:
file.write(reinterpret_cast<const char*>(&m_FileHeader), sizeof(m_FileHeader));
   file.write(reinterpret_cast<const char*>(&m_InfoHeader), sizeof(m_InfoHeader));
   file.write(reinterpret_cast<const char*>(pcBitMap24), width * height * 3);


Die Datei wieder schließen;
CPP:
   file.close();


Wieder den Speicher der map freigeben
CPP:
   delete[] pcBitMap24;


Und wieder die Kontrolle an des Betriebssystem zurückgeben
CPP:
   return 0;


Soweit so gut. Der Inhalt der Zeichenfunktionen poste ich demnächst.
Die fertige exe-Datei gibt es derweilen bereits hier.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden
Otscho
Super JLI'ler


Alter: 35
Anmeldedatum: 31.08.2006
Beiträge: 338
Wohnort: Gummibären-Gasse
Medaillen: Keine

BeitragVerfasst am: 07.06.2008, 13:39    Titel: Die Funktion DrawLine(...); Antworten mit Zitat

Der Prototyp sieht, wie bereits erwähnt, folgendermaßen aus:
CPP:
void DrawLine(Color* pcMap, int* pWidth, int* pHeigth, Vector2f Point1, Vector2f Point2, Color PenColor)

    pcMap ist ein Zeiger auf ein Array des Typs Color mit der Größe vom Produkt der Breite und der Höhe.
    pWidth ist ein Zeiger auf ein Interger, der die Breite der map angibt.
    pHeigth ist ein Zeiger auf ein Interger, der die Höhe der map angibt.
    Point1 ist ein Float-Vektor, der den Startpunt der Linie angibt.
    Point2 ist ein Float-Vektor, der den Endpunt der Linie angibt.
    PenColor ist der Farbwert, mit dem die Linie gezeichnet werden soll.


Die Philosophie dieser Funktion, die versucht eine Linie zwischen Point1 und Point2 zu zeichnen ist recht simpel: Wir setzen unseren Fokus auf Point1 und gehen dann schrittweiße zu Point2. An jeder Stelle, an der wir dabei vorbei kommen, färben wie den dazugehörigen Pixel in der gewünschten Farbe.

Wir schauen, wie man am besten von Point1 zu Point2 kommt, indem wir Point1 von Point2 abziehen.
Das Ergebnis nennen wir vDelta:
CPP:
   Vector2f vDelta;
   vDelta.x = Point2.x - Point1.x;
   vDelta.y = Point2.y - Point1.y;


Nun teilen wir vDelta noch durch seine größte Komponente um in dieser immer um die Einheit ein Pixel weiterwandern zu können:
CPP:
   float fLengthOfvDelta = max(max(vDelta.x , -vDelta.x), max(vDelta.y , -vDelta.y));
   vDelta.x /= fLengthOfvDelta;
   vDelta.y /= fLengthOfvDelta;



Wir kommen nun von Point1 nach Point2 wenn wir uns mehrmals um vDelta-Schritte von Point1 wegbewegen
Wenn wir jetzt nach jedem Schritt das jeweilige Pixel füllen, erhalten wir eine Linie zwischen Point1 und Point2.

Dazu müssen wir aber zuerst 4 verschiedene while-Schleifen definieren
eine für jeden Fall.
Es es gibt vier Fälle:
    1. Fall : Point1.x > Point1.x und Point1.y > Point1.y
    2. Fall : Point1.x > Point1.x und Point1.y < Point1.y
    3. Fall : Point1.x < Point1.x und Point1.y > Point1.y
    4. Fall : Point1.x < Point1.x und Point1.y < Point1.y


Die aktuelle Position des Punktes, den wir schrittweise von Point1 nach Point2 verschieben, nennen wir vCurrentPoint.
Diesen setzten wir gleich an der Stelle von Point1 ins Leben.
CPP:
   Vector2f vCurrentPoint = Point1;


Um mir ein wenig Schreibarbeit zu ersparen, zeige ich hier nur exemplarisch die Schleife für den ersten Fall. Die anderen verhalten sich analog dazu.

Zuerst testen wir ob es sich hier auch wirklich um den ersten Fall handelt, indem wir die Lage von Point2 relativ zu Point1 untersuchen:

CPP:
   if(Point1.x > Point2.x) {
      if(Point1.y > Point2.y) {


Dann eröffnen wir eine while-schleife, die solange aktiv ist, wie die obere Bedingung zwischen vCurrentPoint und Point2 erfüllt ist:
CPP:
         while(vCurrentPoint.x > Point2.x || vCurrentPoint.y > Point2.y) {


Als erstes setzen wir den Pixel an der Stelle von vCurrentPoint auf die gewünschte Farbe:
CPP:
pcMap[static_cast<int>(vCurrentPoint.x) + static_cast<int>(vCurrentPoint.y) * *pWidth] = PenColor;


Anschließend wird der Punkt um vDelta weiter geschoben:
CPP:
            vCurrentPoint.x += vDelta.x;
            vCurrentPoint.y += vDelta.y;

Dann können wir die schleife auch schon wieder "verlassen".
Und das wars dann eigentlich schon.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden
Otscho
Super JLI'ler


Alter: 35
Anmeldedatum: 31.08.2006
Beiträge: 338
Wohnort: Gummibären-Gasse
Medaillen: Keine

BeitragVerfasst am: 07.06.2008, 14:09    Titel: Die Funktion FillDrawenTriangleLineToLine(...) Antworten mit Zitat

Der Prototyp sieht, wie bereits erwähnt, folgendermaßen aus:
CPP:
void FillDrawenTriangleLineToLine(Color* pcMap, int* pWidth, int* pHeigth, Color cBorderColor, Color cFillColor)

    pcMap ist ein Zeiger auf ein Array des Typs Color mit der Größe vom Produkt der Breite und der Höhe.
    pWidth ist ein Zeiger auf ein Interger, der die Breite der map angibt.
    pHeigth ist ein Zeiger auf ein Interger, der die Höhe der map angibt.
    cBorderColor gibt die Farbe des zuvor gezeichneten Rahmens an.
    cFillColor gibt die Farbe an, mit der das Dreieck gezeichnet werden soll


Auf die Vorgehensweise dieser Funktion kam ein Kumpel von mir. Sie geht die map Zeile für Zeile durch. Bei jeder Zeile iteriert sie von links nach rechts und sucht dabei die Farbe des Rahmens, um zu sehen ob sie hier quasi in das Deieck eintritt. Erkennt sie den Rahmen, werden alle darauf folgenden Pixel mit der angegebenen Farbe gefüllt, bis der Rahmen ein zeweites mal entdeckt wird. Dann nimmt sie sich die nächste Zeile vor.

Nun zum Code:

Diese Variable merkt sich ob die Linie schon gefunden wurde:
CPP:
   bool bBorderFound;


Zunächst gehen wir jede Spalte durch:
CPP:
   for(int i = 0 ; i < *pHeigth; i++) {
      bBorderFound = false;
            for(int j = 0; j < *pWidth; j++) {


Und suchen dort nach dem Rahmen in der angegebenen Farbe (=cBorderColor).
Falls wir den Rahmen das erste mal entdecken, merken wir uns das mithilfe von bBorderFound:
CPP:
if(!bBorderFound && CompareColors(cBorderColor, pcMap[j + i * *pWidth])) {
            bBorderFound = true;
         }


Falls wir den Rahmen ein zweites mal gefunden haben, verlassen wir die oberste for-Schleife und nehmen uns die nächste Zeile vor:
CPP:
else if(bBorderFound && CompareColors(cBorderColor, pcMap[j + i * *pWidth])) {
            break;
         }


Danach füllen wir die nachfolgend Pixel in der gewünschten Farbe:
CPP:
         else if(bBorderFound) {
            pcMap[j + i * *pWidth] = cFillColor;
         }


Leider arbeitet diese Funktion nicht bei jedem Dreieck so erfolgreich wie erhofft. Bei einem Testlauf bekam ich einmal folgendes Ergebnis:

Die Problemstellen:
1. Ganz oben: Wenn das Dreieck an einer Stelle nur ein Pixel breit ist, kann kein zweiter Rahmen gefunden werden. Das Resultat: Das Dreieck wird bis zum Rand der map gezeichnet.
2. Untere Hälfte: Ist die Linie des Rahmens einmal mehr als ein Pixel breit, so ist die Funktion im Irrglauben, dass es sich hier schon um den zweiten Rahmen handelt und beendet sofort die Füllaktion für diese Zeile. Das Resultat : Das Dreieck wird überhaupt nicht gezeichnet.

Wenn Interesse besteht, poste ich die anderen drei Varianten morgen noch. Diese haben einen mathematischen Ansatz und funktionieren daher auch wesentlich performanter und zuverlässiger.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden
Deviloper
Junior JLI'ler



Anmeldedatum: 31.05.2006
Beiträge: 77

Medaillen: Keine

BeitragVerfasst am: 08.06.2008, 16:43    Titel: Antworten mit Zitat

Hmm erstmal: Schön das mal wieder jemand ein Tutorial schreibt! Hab mir nicht alles durchgelesen ... nur schnell den Quellcode überflogen. Da kommen direkt Fragen auf:
1. Warum bei deiner Color-Struktur keinen Vergleichsoperator anstelle einer extra Funktion?
2. Schonmal Referenzen benutzt?
3. Wie sieht es mit const aus?
4. Warum schreibst du min und max neu? Vgl. Header: <algortihm> (C++-Standard)
5. Endlosschleifen sind unschön!
6. close von std::fstream wird im Destruktor automatisch aufgerufen.
7. return 0 in main kann weggelassen werden.
8. Guck mal nochmal die Formatierung durch. Haben sich ein paar Fehler eingeschlichen!

das wars erstmal Wink
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
DirectXer
Dark JLI'ler



Anmeldedatum: 05.02.2005
Beiträge: 1201
Wohnort: Köln
Medaillen: Keine

BeitragVerfasst am: 08.06.2008, 18:18    Titel: Antworten mit Zitat

also erstmal finde ich dass dir dieses tutorial sehr gut gelungen ist. Du erläuterst vor allem die Hintergrundinfos anstatt einfach die funktionen zu benutzen. Und man lernt nicht nur das eingentliche thema sondern auch viel zusatzinfos. weiter so! Smile

Deviloper hat Folgendes geschrieben:

1. Warum bei deiner Color-Struktur keinen Vergleichsoperator anstelle einer extra Funktion?
2. Schonmal Referenzen benutzt?
3. Wie sieht es mit const aus?
4. Warum schreibst du min und max neu? Vgl. Header: <algortihm> (C++-Standard)
5. Endlosschleifen sind unschön!
6. close von std::fstream wird im Destruktor automatisch aufgerufen.
7. return 0 in main kann weggelassen werden.
8. Guck mal nochmal die Formatierung durch. Haben sich ein paar Fehler eingeschlichen!

bei punkt 1-4 stimme ich dir zu; das in 5. kann man so nicht sagen, es gibt fälle in denen endlosschleifen durchaus gebräuchlich sind. Trotzdem kann man hier aber auch eleganter verfahren. zu 6: man sollte eine datei nicht unnötig offen lassen, deshalb ist der close aufruf hier angebracht. außerdem trägt er zum verständnis bei. zu 7: mit return 0; zeigst du allen, dass das programm fehlerlos zuende gegangen ist. Das Weglassen kann hier leicht zu Kompatitibilitätsproblemen führen, da main in seiner definition einen int-rückgabewert hat und es nicht im standard festgelegt ist, dass dies automatisch geschieht.

Gruß DXer
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden
Deviloper
Junior JLI'ler



Anmeldedatum: 31.05.2006
Beiträge: 77

Medaillen: Keine

BeitragVerfasst am: 08.06.2008, 18:27    Titel: Antworten mit Zitat

Dann solltest du evtl. mal im Standard nachschlagen! Es ist eben gesichert, das 0 (EXIT_SUCCESS) zurück gegeben wird, wenn nichts anderes angegeben ist. Bei jeder anderen Funktion wirst du vom Compiler eine Warnung bekommen (evtl. gar einen Fehler), das du keinen Rückgabewert angegeben hast.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
DirectXer
Dark JLI'ler



Anmeldedatum: 05.02.2005
Beiträge: 1201
Wohnort: Köln
Medaillen: Keine

BeitragVerfasst am: 08.06.2008, 21:03    Titel: Antworten mit Zitat

Deviloper hat Folgendes geschrieben:
Dann solltest du evtl. mal im Standard nachschlagen! Es ist eben gesichert, das 0 (EXIT_SUCCESS) zurück gegeben wird, wenn nichts anderes angegeben ist. Bei jeder anderen Funktion wirst du vom Compiler eine Warnung bekommen (evtl. gar einen Fehler), das du keinen Rückgabewert angegeben hast.
stimmt ich habs gerade nochmal nachgeschlagen, das was ich gelesen hatte galt für die WinMain, sorry. trotzdem bin ich der meinung dass es den code in so einem tutorial einfacher zu lesen macht, aber das ist dann geschmackssache.

Gruß DXer
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden
xardias
JLI Master


Alter: 37
Anmeldedatum: 28.12.2003
Beiträge: 804
Wohnort: Palo Alto, CA
Medaillen: Keine

BeitragVerfasst am: 09.06.2008, 05:04    Titel: Antworten mit Zitat

Habt ihr nichts besseres zu tun als über "return 0;" oder nicht zu diskutieren?

Aber schönes Tutorial, es ist sicher nicht verkehrt sich mal mit solchen Problemen zu beschäftigen.

Zum "Zeichnen" der Linien kann ich dir den Bresenham Algorithmus empfehlen. Der dürfte etwas schönere Ergebnisse bringen
http://de.wikipedia.org/wiki/Bresenham-Algorithmus
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Hazel
JLI MVP
JLI MVP


Alter: 39
Anmeldedatum: 19.07.2002
Beiträge: 1761

Medaillen: Keine

BeitragVerfasst am: 09.06.2008, 07:08    Titel: Antworten mit Zitat

Wenn du gefüllte Dreiecke zeichnen willst, gibt es da z.B. das Scanlining-Verfahren bei dem mit Hilfe des Bresenhams ein Dreieck Zeile für Zeile mit horizontalen Strichen gemalt wird.

Kann man sich so vorstellen: http://www.devmaster.net/articles/software-rendering/spannedtri.gif

Wenn man neben den Kanten auch noch die RGB-Werte linear Interpoliert hat man Software-Gouraud-Shading. ;) Das Ergebnis kann dann z.B. so aussehen:



Ein altes Uni-Projekt von mir. Kuh mit Mitessern.
_________________
*click* Dabuu!?
Twitter: http://twitter.com/Ollie_R
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Otscho
Super JLI'ler


Alter: 35
Anmeldedatum: 31.08.2006
Beiträge: 338
Wohnort: Gummibären-Gasse
Medaillen: Keine

BeitragVerfasst am: 09.06.2008, 09:42    Titel: Antworten mit Zitat

Deviloper hat Folgendes geschrieben:
1. Warum bei deiner Color-Struktur keinen Vergleichsoperator anstelle einer extra Funktion?
2. Schonmal Referenzen benutzt?
3. Wie sieht es mit const aus?
4. Warum schreibst du min und max neu? Vgl. Header: <algortihm> (C++-Standard)
5. Endlosschleifen sind unschön!
6. close von std::fstream wird im Destruktor automatisch aufgerufen.
7. return 0 in main kann weggelassen werden.
8. Guck mal nochmal die Formatierung durch. Haben sich ein paar Fehler eingeschlichen!


Zu 1. : Wie schon gesagt, soll dieses Tutorial nur auf Dinge aufbauen, die bereits in Christians Buch erklärt wurden. Die Definition von operatoren gehört afaik nicht dazu. Außerdem findet man das selbst in der STL immer wieder, dass globale Vergleichsfunktionen angeboten werden(siehe equal(...)).
Zu 2. Wo genau würdest du das empfehlen ?
Zu 3. Da muss ich dir recht geben. Sollte man evt mal verwenden.
Zu 4. Hey, ich wollte halt mal so gut als möglich ohne fremde Algos auskommen, weil das für Anfänger, die diese nicht kennen evt verwirrend werden kann(ok, jetzt nicht unbedingt bei max und min, aber bei anderen evt schon).
Zu 5. Geschmackssache.
Zu 6. -> DirectXer
Zu 7. Kann, muss man aber nicht. ^^
Zu 8. Danke für den Hinweis.

xardias hat Folgendes geschrieben:
Zum "Zeichnen" der Linien kann ich dir den Bresenham Algorithmus empfehlen. Der dürfte etwas schönere Ergebnisse bringen

Mein Algo bringt auch MS-Paint-Qualität. Hab nur ein falsches Bild hochgeladen als ich noch was anderes als :
CPP:
float fLengthOfvDelta = max(max(vDelta.x , -vDelta.x), max(vDelta.y , -vDelta.y));
verwendet hab.


PS. Hab mitlerweile den Code etwas verfeinert und erweitert(Color als Klasse definiert mit zahlreichen operatoren(unter anderem auch den Vergleichsoperator ==), genauso vector als Klasse und eine vertex-strukur um auch für jeden Punkt ne eigene Farbe angeben zu können; Antialiasing)


Hm, ich glaub, ich lass das lieber mit dem Antialiasing sein ...
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden
Fallen
JLI MVP
JLI MVP


Alter: 39
Anmeldedatum: 08.03.2003
Beiträge: 2860
Wohnort: Münster
Medaillen: 1 (mehr...)

BeitragVerfasst am: 09.06.2008, 17:55    Titel: Antworten mit Zitat

Deviloper hat Folgendes geschrieben:
Dann solltest du evtl. mal im Standard nachschlagen! Es ist eben gesichert, das 0 (EXIT_SUCCESS) zurück gegeben wird, wenn nichts anderes angegeben ist. Bei jeder anderen Funktion wirst du vom Compiler eine Warnung bekommen (evtl. gar einen Fehler), das du keinen Rückgabewert angegeben hast.


Bitte achte auf einen guten Umgangston.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen
David
Super JLI'ler


Alter: 38
Anmeldedatum: 13.10.2005
Beiträge: 315

Medaillen: Keine

BeitragVerfasst am: 13.06.2008, 11:42    Titel: Antworten mit Zitat

Hazel hat Folgendes geschrieben:

Wenn du gefüllte Dreiecke zeichnen willst, gibt es da z.B. das Scanlining-Verfahren bei dem mit Hilfe des Bresenhams ein Dreieck Zeile für Zeile mit horizontalen Strichen gemalt wird.


Für horizontale Linien brauchst du keinen Bresenham Algorithmus. Razz

@Tutorial:

Zuerstmal:
Ich finde es unnötig über 'Codestil', 'Codeparadigmen' und 'sauberen Code' zu diskutieren. Das Thema des Tutorials lautet schließlich nicht "Wie setzte ich Objektorientierung, verbunden mit sauberen Code, in einem Stil um, der jedem zusagt?".
Also: lieber das Thema des Tutorials diskutieren, der Rest ist eher uninteressant.

Ansonsten finde ich das Tutorial recht gut.
Mich würden jetzt aber noch die drei ausbleibenden Implementierungen interessieren. Das die Idee von deinem Kumpel in die Hose geht, hast du ja bereits erläutert.

Für das Zeichnen von Linien gibt es allerdings tatsächlich bessere Algorithmen (dein Algorithmus scheint z.T. über die Grenzpunkte hinaus zu zeichnen). Bresenhams Algorithmus wurde ja bereits erwähnt. Für 'antialiaste' Linien lohnt sich ein Blick auf Xiaolin Wu's Algorithmus. Der Algorithmus ist ziemlich schnell (nicht ganz so schnell wie Bresenhams) liefert aber viel schönere Ergebnisse.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Otscho
Super JLI'ler


Alter: 35
Anmeldedatum: 31.08.2006
Beiträge: 338
Wohnort: Gummibären-Gasse
Medaillen: Keine

BeitragVerfasst am: 13.06.2008, 18:41    Titel: Antworten mit Zitat

David hat Folgendes geschrieben:
Mich würden jetzt aber noch die drei ausbleibenden Implementierungen interessieren. Das die Idee von deinem Kumpel in die Hose geht, hast du ja bereits erläutert.


OK, dann kram ich mal wieder dan alten Code durch:

CPP:
void FillDrawenTrianglePerPathfinding(Color* pcMap, int* pWidth, int* pHeigth, Color cBorderColor, Color cFillColor, Vector2i vCurrentPosition);

    pcMap ist ein Zeiger auf ein Array des Typs Color mit der Größe vom Produkt der Breite und der Höhe.
    pWidth ist ein Zeiger auf ein Interger, der die Breite der map angibt.
    pHeigth ist ein Zeiger auf ein Interger, der die Höhe der map angibt.
    cBorderColor gibt die Farbe des zuvor gezeichneten Rahmens an.
    cFillColor gibt die Farbe an, mit der das Dreieck gezeichnet werden soll.
    vCurrentPosition ok der Name ist ein wenig unglücklich gewählt, aber dieser Vektor steht für einen Punkt, der innerhalb des Dreiecks liegt.
    Dieser Punkt lässt sich relativ leicht errechnen, indem man den Schwerpunkt der drei Eckpunkte berechnet. (Mittelpunkt = (Punkt1 + Punkt2 +Punkt3) / 3)


Diese Funktion behilft sich der einfachen Technik des Pathfindings. Wir gehen einfach von dem Mittelpunkt in alle Richtungen, schauen ob wir nicht auf den Rahmen gestoßen sind, füllen dann gegebenenfalls das Pixel mit der gewünschten Farbe und schauen uns schließlich mit der selben Funktion die Nachbarpixel an. Durch diese Rukursion hält sich der Funktionsrumpf relativ klein.
Dieser sieht wie folgt aus:

Da es ja sein kann, dass diese Funktion schon des öfteren aufgerufen worden ist, und mittlerweile an die Grenzen des Bildes gestoßen ist, sollten wir zuerst schauen, ob dies schon der Falls ist. Wenn ja dann gibt es für diesen Aufruf der Funktion nichts mehr zu tun und wir beenden diesen.
CPP:
if(vCurrentPosition.x < 0 || vCurrentPosition.x > *pWidth ||
      vCurrentPosition.y < 0 || vCurrentPosition.y > *pHeigth) return;

Dann schauen wir noch ob diese Funktion für den Pixel schon mal aufgerufen worden ist und der Pixel schon gefüllt ist:
CPP:
   if(CompareColors(pcMap[(vCurrentPosition.x) + (vCurrentPosition.y) * *pWidth], cFillColor)) return;

Sind wir schon an den gezeichneten Rahmen gestoßen ?
CPP:
   if(CompareColors(pcMap[(vCurrentPosition.x) + (vCurrentPosition.y) * *pWidth], cBorderColor)) return;

Wurden alle Tests bis jetzt mit nein beantwortet, dann befinden wir uns an einer neuen Stelle noch innerhalb des Dreiecks und können den Pixel befüllen:
CPP:
   pcMap[vCurrentPosition.x + vCurrentPosition.y * *pWidth] = cFillColor;

Dann rufen wir die Funktion noch für alle anliegenden Pixel auf:
Einmal für das rechte Feld:
CPP:
vCurrentPosition.x += 1;
   
   FillDrawenTrianglePerPathfinding(pcMap, pWidth, pHeigth, cBorderColor, cFillColor, vCurrentPosition);

Dann für das linke Feld:
CPP:
   vCurrentPosition.x -= 2;

   FillDrawenTrianglePerPathfinding(pcMap, pWidth, pHeigth, cBorderColor, cFillColor, vCurrentPosition);

Unten:
CPP:
   vCurrentPosition.x += 1;
   vCurrentPosition.y += 1;
   
   FillDrawenTrianglePerPathfinding(pcMap, pWidth, pHeigth, cBorderColor, cFillColor, vCurrentPosition);

Und zum Schluss Oben:
CPP:
   vCurrentPosition.y -= 2;
   
   FillDrawenTrianglePerPathfinding(pcMap, pWidth, pHeigth, cBorderColor, cFillColor, vCurrentPosition);


Dann können wir diese Funktion auch schon wieder verlassen.

Die Vorteile dieser Variante:
1. Es werden keine Pixel außerhalb des Dreiecks bepinselt. Zumindest ist das bei mir noch nie passiert.
2. Diese Funktion arbeitet für kleine Dreiecke (weniger als 10 000 zu füllende Pixel) recht schnell und stabil.

Die Nachteile Dieser Variante:
1. Es werden machmal Pixel in den Ecken nicht ausgefüllt, wenn sie keine seitlichen Nachbaren haben.
2. Bei zu großen Dreicken kam es bei mir immer wieder zu einem "stack overflow" und das Programm war im Jenseits.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden
Otscho
Super JLI'ler


Alter: 35
Anmeldedatum: 31.08.2006
Beiträge: 338
Wohnort: Gummibären-Gasse
Medaillen: Keine

BeitragVerfasst am: 13.06.2008, 19:02    Titel: Funktion: "DrawSolidTriangle(...)" Antworten mit Zitat

CPP:
void DrawSolidTriangle(Color* pcMap, int* pWidth, int* pHeigth, Color cFillColor, Vector2f vA, Vector2f vB, Vector2f vC);


    pcMap ist ein Zeiger auf ein Array des Typs Color mit der Größe vom Produkt der Breite und der Höhe.
    pWidth ist ein Zeiger auf ein Interger, der die Breite der map angibt.
    pHeigth ist ein Zeiger auf ein Interger, der die Höhe der map angibt.
    cFillColor gibt die Farbe an, mit der das Dreieck gezeichnet werden soll.
    vA, vBund vC sind die Eckpunkte des Dreiecks.

Für diese Zeichenwariante braucht man schon ein wenig Mathematik. Allerdings reicht die Schulmathematik der 8. Klasse schon völlig dafür aus.
Zunächst geben wir für jede Verbindungsgerade eine Gleichung an. In der Form: y(x) = mx + t
Wir haben also zwei Punkte einer Geraden(jeweils zwei Eckpunkte).
Die Steigung "m" errechnen wir ganz einfach mit der Formel : m = (y1 - y2) / (x1 - x2)
Und den Y-Abschnitt t erhalten wir indem wir irgendeinen Punkt einsetzen : y1 = m * x1 + t => t = y1 - m * x1
Alle Punkte, die diese Gleichung erfüllen liegen somit genau auf der Geraden, oder anderst gesagt auf der Grenze des Dreiecks.
Wenn wenn wir daraus eine Ungleichun machen y > mx + t bekommen wir alle Punkte die oberhalb der Geraden liegen, bzw. mit y < mx + t alle unterhalb der Geraden.
Somit können wir schon eine eindeutige Bedingung für die Punkte schaffen ob sie in der rchtigen "Halbebene" einer Dreickseite liegen oder nicht.
Kombiniert mit den anderen zwei Seiten lässt sich eine eindeutige Abfragerutine erstellen, die uns sagt, ob ein Punkt im Dreieck liegt oder nicht.
Natürlich müssen wir noch das richtige Ungleichheitszeichen wählen. Das erhalten wir indem wir es schlicht so wählen, dass der gegenüberliegenden Punkt der Ungleichung genüge tut.

Genug der Grauen Theorie - ans Werk !

Zunächst die Gleichung für die Gerade AB aufstellen:
CPP:
   float mAB = (vA.y - vB.y) / (vA.x - vB.x);
   float tAB = vA.y - mAB * vA.x;

Um das passende Ungleichheitszeichen zu bekommen testen wir einfach die Ungleichung mit ">" und multyplizieren sie gegebenefalls mit -1, was einer umkehrung des Ungleichheitszeichen gleichkommt.
CPP:
   int signeAB = 1;         // Der Vorfaktor 1 ändert nichts an der Ungleichung
   if(vC.y < mAB * vC.x + tAB) signeAB = -1;

Der Gleiche Vorgang mit den anderen Geraden:
CPP:
   float mBC = (vB.y - vC.y) / (vB.x - vC.x);
   float tBC = vB.y - mBC * vB.x;

   int signeBC = 1;
   if(vA.y < mBC * vA.x + tBC) signeBC = -1;


   float mCA = (vC.y - vA.y) / (vC.x - vA.x);
   float tCA = vC.y - mCA * vC.x;

   int signeCA = 1;
   if(vB.y < mCA * vB.x + tCA) signeCA = -1;

Um dem CPU unnötige Arbeit vom Hals zu schaffen begrenzen wir unseren Fokus auf das kleinste Rechteck, welches das Dreieck noch enthält:
CPP:
   //Untere X-Grenze
   int minX = static_cast<int>(min(vA.x, min(vB.x, vC.x)));

   //Obere X-Grenze
   int maxX = static_cast<int>(max(vA.x, max(vB.x, vC.x))) + 1;

   //Untere Y-Grenze
   int minY = static_cast<int>(min(vA.y, min(vB.y, vC.y)));

   //Obere Y-Grenze
   int maxY = static_cast<int>(max(vA.y, max(vB.y, vC.y))) + 1;

Nun gehen wir Zeile für Zeile jeden Punkt durch und testen ob er alle Bedingungen erfüllt:
CPP:
   for(int y = minY; y < maxY; y++) {
      for(int x = minX; x < maxX; x++) {
         if((signeAB*y > signeAB * (x * mAB + tAB)) &&
            (signeBC*y > signeBC * (x * mBC + tBC)) &&
            (signeCA*y > signeCA * (x * mCA + tCA))) {
            // Wenn ja, Pixel füllen
            pcMap[x + y * *pWidth] = cFillColor;
         }
      }
   }


Zur Auswertung:

Vorteile:
1. Man muss keinen Rahmen des Dreiecks vorher zeichnen.
2. Diese Funktion arbeitet schnell und zuverlässig. Pixel außerhalb des Dreiecks werden nie befüllt, die innerhalb fast immer.

Nachteil:
Kommt es wegen einer vertikalen Dreiecksseite dazu, dass folgender Ausdruck ungültig wird:
CPP:
float mAB = (vA.y - vB.y) / (vA.x - vB.x);
Dann können keine Pixel des Dreiecks gezeichnet werden.
Man könnte natürlich versuchen diese Fehlerquelle aufzuspüren und unschädlich zu machen, indem man schaut ob die Differenz "vA.x - vB.x" Null ergibt und dann gegebenenfalls dem Bruch nachträglich einen definierten Wert gibt. Der sollte allerdings recht groß sein.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden
Otscho
Super JLI'ler


Alter: 35
Anmeldedatum: 31.08.2006
Beiträge: 338
Wohnort: Gummibären-Gasse
Medaillen: Keine

BeitragVerfasst am: 13.06.2008, 19:21    Titel: Funktion: DrawSolidTriangleEx(...) Antworten mit Zitat

CPP:
void DrawSolidTriangleEx(Color* pcMap, int* pWidth, int* pHeigth, Color cFillColor, Vector2f vA, Vector2f vB, Vector2f vC);

Dieser Funktionsprototyp hat die selbe Argumentenliste wie die die Funktion DrawSolidTriangle(...)
Leider ist mir für diese Funktion kein guter Namen eingefallen, weil eigentlich ist diese Zeichenvariante mein Favorit, da man mit ihr später noch viele lustige Sachen machen kann. Z.B. wurde das bunte Dreieck von oben mit einer Erweiterung von ihr gerendert.

Diese Funktion enthält Schulmathematik der Analytischen Geometrie (12. Klasse (zumindest in Bayern))

Bei dieser Variante versuchen wir jeden Pixel durch die zwei Vektoren AB und AC mit dem Aufpunkt A anzugeben.
Wir werden also jeden Punkt so angeben: Point = vA + lambda * vAB + mü * vAC;
Das geht allerdings nur, wenn vAB und vAC nicht koliniear sind. Sprich nicht auf einer Linie liegen.
Unsere Arbeit wird es nun sein die Parameter "mü" und "lambda" herauszufinden.

Betrachten wir die einzellnen Komponenten, dann können wir schonmal zwei Gleichungen aufstellen mit den zwei Unbekannten:
----------------------------------------------------------------------
(I) Point.x - vA.x = lambda * vAB.x + mü * vAC.x
(II) Point.y - vA.y = lambda * vAB.y + mü * vAC.y
----------------------------------------------------------------------
(I) nach lambda aufgelöst: lambda = (Point.x - vA.x - mü * vAC.x) / vAB.x
(II) nach mü aufgelöst: mü = (Point.y - vA.y - lambda * vAB.y) / vAC.y
(II) in (I) : lambda = (Point.x - vA.x - ((Point.y - vA.y - lambda * vAB.y) / vAC.y) * vAC.x) / vAB.x
Vereinfacht: lambda = ((Point.x - vA.x - (Point.y - vA.y) * (vAC.x / vAC.y))) / (vAB.x - vAC.x * vAB.y / vAC.y)
Damit lässt sich dann aus (II) auch mü bestimmen
Über den Punkt können wir nun sagen, er befindet sich innerhalb des Dreiecks, wenn gilt:
1. mü > 0
2. lamda > 0
3. mü + lamda < 1
(Alle drei Bedingungen müssen erfüllt sein !)

Lasst uns zur Tat schreiten !

Die Vektoren vAB und vAC aufstellen:
CPP:
   Vector2f vAB = {vB.x - vA.x, vB.y - vA.y};
   Vector2f vAC = {vC.x - vA.x, vC.y - vA.y};

Diese also auf Koliniearität prüfen und gegebenenfalls die Aktion abblasen:
CPP:
   if(((vAB.x / vAB.y) == (vAC.x / vAC.y)) ||
      ((vAB.x / vAB.y) == -1 * (vAC.x / vAC.y))) {
      cout << "Die eingegebenen Punkte liegen auf einer Linie !\n";
      return;
   }

Dann legen wir noch die zwei Variablen "lambda" und "mu" (=mü) an:
CPP:
   float lambda, mu;

Begrenzen das Gebiet, welches wir bearbeiten wollen auf ein Minimum
CPP:
   //Untere X-Grenze
   int minX = static_cast<int>(min(vA.x, min(vB.x, vC.x)));

   //Obere X-Grenze
   int maxX = static_cast<int>(max(vA.x, max(vB.x, vC.x))) + 1;

   //Untere Y-Grenze
   int minY = static_cast<int>(min(vA.y, min(vB.y, vC.y)));

   //Obere Y-Grenze
   int maxY = static_cast<int>(max(vA.y, max(vB.y, vC.y))) + 1;

Dann gehen wir wieder jeden Punkt durch:
CPP:
   for(int y = minY; y < maxY; y++) {
      for(int x = minX; x < maxX; x++) {


Berechnen "lamda" und "mu" mit der obrigen Formel:
CPP:
         lambda = ((x - vA.x - (y - vA.y) * (vAC.x / vAC.y))) / (vAB.x - vAC.x * vAB.y / vAC.y);
         mu = (y - vA.y - lambda * vAB.y) / vAC.y;


Und bemalen gegebenfalls den Pixel:
CPP:
         if(mu > 0.0f && lambda > 0.0f && lambda + mu < 1.0f) {
            pcMap[x + y * *pWidth] = cFillColor;
         }


Die Vorteile:
1. Man muss keinen Rahmen des Dreiecks vorher zeichnen.
2. Diese Funktion arbeitet schnell und zuverlässig. Pixel außerhalb des Dreiecks werden nie befüllt, die innerhalb fast immer.
3. Man hat zwei Variablen(mu und lambda), die einem stets die relative Position im Dreieck angeben.

Der Nachteil:
Auch hier kann es zu einem NAN, also einem ungültigen Wert kommen, wenn vAC.y, vAB.y oder (vAB.x - vAC.x) Null ergeben. Aber auch hier kann man, wie bei der vorigen Variante bereits erwähnt, Abhilfe leisten.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden
Beiträge der letzten Zeit anzeigen:   
Neues Thema eröffnen   Neue Antwort erstellen    JLI Spieleprogrammierung Foren-Übersicht -> Tutorials Alle Zeiten sind GMT
Gehe zu Seite 1, 2  Weiter
Seite 1 von 2

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.


Powered by phpBB © 2001, 2005 phpBB Group
Deutsche Übersetzung von phpBB.de

Impressum