Eine Woche Programmierwettbewerb: Rechtecke

Ponto

tja, am ende hast du selbst zugegeben dass du das nutzen moechtest (nutzen!=copy&paste), andere zahlen mir mein gehalt damit ich sowas fluessig auf dem schirm zaubere, da kann ich das ja nicht gratis hier machen (zumal das mein arbeitsvertrag auch verbietet, wie vielleicht von einigen anderen auch).

Wie gesagt habe ich Verständnis dafür, dass du deine Ideen für dich behalten möchtest oder gar musst. Andererseits wäre es dumm, nicht mit den anderen Ideen den eigenen Horizont zu erweitern. Das gilt für diesen und für alle folgenden Wettbewerbe. Es tut mir auch leid, dass du Zeit in diese Sache gesteckt hast, ohne etwas einsenden zu dürfen.

Ich denke jedoch, dass es nichts zuzugeben gab. Ich habe auf jede Frage zu der Aufgabe bereitwillig geantwortet. Wofür man eine Lösung der Aufgabe nutzen kann, ist auch nicht schwer zu erraten. Dann muss man sich von Anfang an fragen, ob man eine Lösung beisteuern kann oder nicht. Hättest du die Aufgabe anders bewertet, wenn ich gesagt hätte, dass mir kein praktischer Nutzen einfällt? Oder wenn keiner nach dem Ursprung gefragt hätte? Ich denke also, dass sich durch meine späteren Aussagen grundsätzlich nichts geändert hat.

jenz

okay, wenn die caches gemeinsam genutzt werden, dann kann ich mich darauf einlassen, dass es schief gehen kann. auch wenn die threads ja so ziemlich auf den gleichen daten arbeiten.
lesend auf den rechtecken, schreibend auf der plane. lesen muss man nicht kontrollieren, das schreiben in die plane bei meinem verfahren auch nicht.

jeder thread hätte dann noch eine eigene "verwaltugsstruktur", die könnte natürlich den cache durcheianderbringen...

bei getrennten caches sollte die geschwinigkeitssteigerung aber ziemlich deutlich sein. eben fast verdoppelt, wenn man 2 nimmt.

jenz

rapso

Ponto schrieb:

tja, am ende hast du selbst zugegeben dass du das nutzen moechtest (nutzen!=copy&paste), andere zahlen mir mein gehalt damit ich sowas fluessig auf dem schirm zaubere, da kann ich das ja nicht gratis hier machen (zumal das mein arbeitsvertrag auch verbietet, wie vielleicht von einigen anderen auch).

Wie gesagt habe ich Verständnis dafür, dass du deine Ideen für dich behalten möchtest oder gar musst. Andererseits wäre es dumm, nicht mit den anderen Ideen den eigenen Horizont zu erweitern. Das gilt für diesen und für alle folgenden Wettbewerbe. Es tut mir auch leid, dass du Zeit in diese Sache gesteckt hast, ohne etwas einsenden zu dürfen.

keine sorge, ich kann das ja nach dem release der resultate usw. mit meiner version vergleichen. Bisher hab ich nicht viel zeit reingesteckt, leidglich das framework gesetzt und jesters version umgestellt mit trivialoptimierungen. (da sind nichtmal deine generatoren integriert).
wobei es mich auch mehr reizt dann das ganze fluessig darzustellen (was du ja als eigentliche anwendung genannt hast) als punkte in nem vector<vector<>> zu setzen *hehe*.

Ich denke jedoch, dass es nichts zuzugeben gab. Ich habe auf jede Frage zu der Aufgabe bereitwillig geantwortet. Wofür man eine Lösung der Aufgabe nutzen kann, ist auch nicht schwer zu erraten. Dann muss man sich von Anfang an fragen, ob man eine Lösung beisteuern kann oder nicht. Hättest du die Aufgabe anders bewertet, wenn ich gesagt hätte, dass mir kein praktischer Nutzen einfällt?

wenn ich gesehen haette dass es keinen nutzen gibt, haette ich eventuell code eingesand, aber da ich die benches auch alleine fuer mich machen kann wenn die sources und resultate freigegeben sind...

Oder wenn keiner nach dem Ursprung gefragt hätte? Ich denke also, dass sich durch meine späteren Aussagen grundsätzlich nichts geändert hat.

es wirkte von anfang an sehr auf einen speziellen context bezogen, deine aufgabenstellung implizirte das (vielleicht deine wortwahl )

Ich finde es ja gut dass du nen contest hier machst, raetsel loesen macht ja auch spass selbst wenn man sich nicht oeffentlich mit anderen misst oder es grossartige preise gibt.

Ponto

jenz schrieb:

okay, wenn die caches gemeinsam genutzt werden, dann kann ich mich darauf einlassen, dass es schief gehen kann. auch wenn die threads ja so ziemlich auf den gleichen daten arbeiten.
lesend auf den rechtecken, schreibend auf der plane. lesen muss man nicht kontrollieren, das schreiben in die plane bei meinem verfahren auch nicht.

jeder thread hätte dann noch eine eigene "verwaltugsstruktur", die könnte natürlich den cache durcheianderbringen...

bei getrennten caches sollte die geschwinigkeitssteigerung aber ziemlich deutlich sein. eben fast verdoppelt, wenn man 2 nimmt.

Nehmen wir mal an, dass du folgendermaßen parallelisierst:

Jeder Thread bekommt einen Teil der plane. Dann geht er durch die Rechteckliste und aktualisiert seinen Planeanteil, wenn das Rechteck darin liegt.

Wir können leicht dafür sorgen, dass die Planeteile, in die die Threads schreiben sich Cachemässig nicht in die Quere kommen. Dennoch wird man keinen Faktor 2 bei 2 Threads erhalten, denn wir machen jetzt manche Arbeit doppelt.

Nehmen wir an die Gesamtarbeit ist GA und der Anteil für das Schreiben in die Plane ist x*GA. Dann haben wir noch (1-x)*GA an Arbeit, die für das Durchlaufen der Rechteckliste und für die Bestimmung, ob die Rechecke in die Plane passen, draufgehen. Den ersten Teil kann man parallelisieren, den zweiten macht man jedoch doppelt.

Damit steigt die Arbeit im Falle zweier Threads auf x*GA + 2*(1-x)*GA und mit perfekter parallelisierung macht dann jeder Thread: 0.5*x* GA + (1-x)*GA

Der Speedupfaktor gegenüber der seriellen Lösung ist dann GA/(0.5*x* GA + (1-x)*GA) = 1 /(0.5*x + (1-x)) = 1/(1 - 0.5x).

Je näher also das x an 1 ist, desto näher ist der Speedup bei 2. Aber wenn x klein ist, können wir nur ganz geringe Speedups erwarten.

rapso

jenz schrieb:

okay, wenn die caches gemeinsam genutzt werden, dann kann ich mich darauf einlassen, dass es schief gehen kann. auch wenn die threads ja so ziemlich auf den gleichen daten arbeiten.

du kannst pech haben und jeder thread hat seine daten so, dass sie sich im cache ueberlagern, sodass sich die threads gegenseitig die daten "wegschmeissen" aus dem cache.

lesend auf den rechtecken, schreibend auf der plane. lesen muss man nicht kontrollieren, das schreiben in die plane bei meinem verfahren auch nicht.

das ist dem cache relativ egal beim mappen von cache-adress-space auf den echten addressspace.

jeder thread hätte dann noch eine eigene "verwaltugsstruktur", die könnte natürlich den cache durcheianderbringen...

koennte, koennte auch ein gewinn sein, je nach architektur.

bei getrennten caches sollte die geschwinigkeitssteigerung aber ziemlich deutlich sein. eben fast verdoppelt, wenn man 2 nimmt.

koennte aber auch doppelte belastung des rams sein, was wenn das ram das limitierende in dem fall ist? dann zerschiessen sich die threads die sequential reads?

was ist bei nem intel quadcore, 2cores teilen sich jeweils den cache, greifen die cores in der falschen combination auf die daten zu, muessen die daten aus dem einen cache ueber den FSB ins ram geschrieben werden und dann in den anderen cache....

klar, am ende hat man irgend ne beschleunigung, einer hat eventuell ne arschkarte und die ergebnisse sehen auf jeder maschine aus wie anders ausgewuerfelt

mag sein dass ich hier zu sehr schwarzmale, aber ich hab schon erlebt, dass je besser eine optimierung fuer threads ist, desto anfaelliger ist sie auf anderen architekturen.

jenz

nun gut, ich nehme das mal so hin...

@ponto:
eins aber noch
vielleicht kannst du ja in deinen vergleich die fläche der plane einfach mal ein paar mal verdoppeln, dann kann man den speedup vielleicht ein bisschen abschätzen.

ich habe das gerade auch ein bisschen gemacht und das ergebnis sieht wirklich nicht so erfolgversprechend aus...schade

jenz

rapso

jenz schrieb:

nun gut, ich nehme das mal so hin...

http://www.xbitlabs.com/articles/cpu/display/3dmax5-p4-ht.html

da sieht man ein wenig wie random die resultate sein koennen, einige benches bei denen singlethreaded 10% schneller ist, auf der zweiten seite ist dann der p4 mit HTT 5mal schneller...

jenz

schon interessant, aber da haben wir ja nicht wirklich getrennte rechner, sondern eben hyperthreading...

aber ich erkenne den punkt, dass es auch da schwankt.

gut, dann machen wir mal weiter unsere eigenen erfahrungen

@ponto:
wie sieht es denn mit den ergebnissen aus?

Badestrand

Und wäre auch interessant, wenn der Gewinner seine Herangehensweise schildern könnte; könnte man ja noch was von lernen
Muss ja nicht der Code sein, aber evtl das Prinzip, wie es gelöst wurde. Falls der Gewinner damit einverstanden ist, natürlich.

Ponto

Hier kommt meine Auswertung:

Es gab vier Einsendungen: otze, Jens, camper und TomasRiker

Jens hatte zwei Algorithmen abgegeben, die ich beide getestet habe, weil noch genug Kapazität da war.
Da aber jeder nur einen Algorithmus in den Contest schicken kann, gilt nur der, der hier als Jens-1 bezeichnet ist. Der andere läuft außer Konkurrenz.

Ebenso wird mein Algorithmus nicht berücksichtigt, der hier als Ponto bezeichnet wird. Zusätzlich taucht in den Tabellen noch der Algorithmus "TomasRiker Mod" auf. Diesen habe ich aufgenommen, weil TomasRiker in seiner Originallösung die Generatoren stark berücksichtigt.

Insgesamt tauchen hier also 7 Algorithmen auf.

Ich habe die Generatoren mit verschiedenen Parametern gefüttert und die Laufzeiten der Algorithmen aufsummiert. Damit denke ich den Algorithmus zu erhalten, der über einen breiten Anwendungsbereich am besten arbeitet.

Die Tests liefen auf einer Maschine mit 8 Prozessoren von AMD: "AMD Opteron(tm) Processor 852". Die Taktrate ist 2.6GHz. Die Testmaschine hat 64GB Hauptspeicher, welcher von keinem Programm ausgenutzt wurde.
Für jeden Test habe ich den Programmen 120 Sekunden CPU-Zeit gegeben. Testläufe, die länger benötigten wurden mit 130 Sekunden bewertet. Für die anderne Läufe gelten die tatsächlichen Sekunden.

Hier die Laufzeiten in Sekunden:

User:     camper  Jens-1  Jens-2   otze  TomasRiker  TomasRiker  Ponto
                                                        Mod
Dot:          86     783    2194   2507          38          42     61
Wiring:     1104    2392    1965   2686         114         924    757
Placement   1708    3566    5711   6906         255         516    986
Random:     2248    5107     884   5331          28        1472    771
           -----   -----   -----  -----       -----       -----  -----
Gesamt:     5146   11848   10754  17430         435        2954   2574

Damit ergibt sich die folgende Reihenfolge:

4. otze
3. Jens
2. camper
1. TomasRiker

Man sieht, dass TomasRiker auch ohne seine Optimierung auf die Generatoren hin gewonnen hätte.

Herzlichen Glückwunsch an den Gewinner.

Alle Testläufe sind in der folgenden Tabelle eingetragen: http://www.pontohonk.de/wpc/Contest.ods

Die Rohdaten sind in http://www.pontohonk.de/wpc/Contest.txt zu finden. Die Laufzeitspalten sind sortiert nach camper, Jens-1, Jens-2, otze, TomasRiker Mod, Ponto, TomasRiker, Ponto (mit TomasRiker optimierungen)

Ponto

Hier ist mein eigener Code:

Grob gesagt, wird hier ein Quadtree aufgebaut, der an jedem Knoten abspeichert, ob dieser und die gesamte
Fläche darunter schon belegt sind.

Der erste Knoten (layer0[0]) repräsentiert die gesamte Ebene. In jedem weiteren Layer werden die darüberliegenden Flächen in vier gleich große Quadrate aufgeteilt.

Der Algorithmus läuft dann rekursiv. Es wird das Rechteck in das kleinste Quadrat gelegt, in das das Rechteck passt. Dann wird Anhand der Viertelung aufgeschnitten und die nächste Ebene aufgerufen. Ist eine Ebene schon belegt, kann abgebrochen werden.

#include <cmath>
#include <vector>

#include "rectangle.hpp"

char layerC[4096*4096/8];
char layerB[2048*2048/8];
char layerA[1024*1024/8];
char layer9[512*512/8];
char layer8[256*256/8];
char layer7[128*128/8];
char layer6[64*64/8];
char layer5[32*32/8];
char layer4[16*16/8];
char layer3[8*8/8];
char layer2[4*4/8];
char layer1[1];
char layer0[1];

char * layer[] = { layer0, layer1, layer2, layer3, layer4, layer5, layer6,
                   layer7, layer8, layer9, layerA, layerB, layerC };

inline bool get(int l, int x, int y) {
   unsigned int pos = (x * (1 << l) + y);
   unsigned int byte = pos / 8;
   unsigned int bit = pos % 8;
   return (layer[l][byte]) & (1 << bit);
}

inline void set(int l, int x, int y) {
   unsigned int pos = (x * (1 << l) + y);
   unsigned int byte = pos / 8;
   unsigned int bit = pos % 8;
   layer[l][byte] |= (1 << bit);
}

static int pixel = 0;

static std::vector<std::vector<std::size_t> > * res;

inline unsigned int floor_log2_p1(unsigned int v)
{
   if (v <= 2) return v;

   unsigned int b = 17U;
   if (v <   1U<<16U)       b  = 1U;
   if (v >= (1U<< 7U) << b) b += 8U;
   if (v >= (1U<< 3U) << b) b += 4U;
   if (v >= (1U<< 1U) << b) b += 2U;
   return(b + (v >= (1U<<0U) << b));
}

inline void draw(int l, int x, int y, int minx, int maxx, int miny, int maxy, std::size_t idx) {
   if (minx >= maxx or miny >= maxy) return;
   if (get(l, x, y)) return;

   int size = (4096U >> l);

   if (size == 1) {
      ++pixel;
      set(l, x, y);
      (*res)[x][y] = idx;
      return;
   }

   int half = size/2;

   int startx = x * size;
   int midx = startx + half;
   int starty = y * size;
   int midy = starty + half;

   draw(l+1, 2*x,   2*y,   minx, std::min(maxx, midx), miny, std::min(maxy, midy), idx);
   draw(l+1, 2*x+1, 2*y,   std::max(minx, midx), maxx, miny, std::min(maxy, midy), idx);
   draw(l+1, 2*x,   2*y+1, minx, std::min(maxx, midx), std::max(miny, midy), maxy, idx);
   draw(l+1, 2*x+1, 2*y+1, std::max(minx, midx), maxx, std::max(miny, midy), maxy, idx);

   if (get(l+1, 2*x, 2*y) and get(l+1, 2*x+1, 2*y) and get(l+1, 2*x, 2*y+1) and get(l+1, 2*x+1, 2*y+1)) {
      set(l, x, y);
      return;
   }
}

void algorithm(Rectangle plane,
               std::vector<Rectangle> const & rectangles,
               std::vector<std::vector<std::size_t> > & result)
{
   res = &result;

   Coordinate width  = plane.maxx - plane.minx;
   Coordinate height = plane.maxy - plane.miny;

   for (std::size_t i = rectangles.size(); i > 0; --i) {

      Rectangle rect = {rectangles[i-1].minx - plane.minx,
                        rectangles[i-1].maxx - plane.minx,
                        rectangles[i-1].miny - plane.miny,
                        rectangles[i-1].maxy - plane.miny };

      rect.minx = std::max(Coordinate(0), rect.minx);
      rect.miny = std::max(Coordinate(0), rect.miny);

      rect.maxx = std::min(width, rect.maxx);
      rect.maxy = std::min(height, rect.maxy);

      if (rect.minx >= rect.maxx or rect.miny >= rect.maxy) continue;

      int layer = floor_log2_p1(std::max(((rect.maxy-1) ^ rect.miny), ((rect.maxx-1) ^ rect.minx)));

      draw(12 - layer, (rect.minx >> layer) , (rect.miny >> layer),
           rect.minx, rect.maxx, rect.miny, rect.maxy, i-1);
      if (pixel == width * height) break;
   }
}

Ponto

Hier ist der Siegercode:

// ************************************************************************************************
//
// Z-Buffer-ï¿½hnlicher Algorithmus		von David Scherfgen (TomasRiker)
// ______________________________  		David_Scherfgen@gmx.de
//										http://www.spieleprogrammierer.de/
//
// Dieser Algorithmus war ursprï¿½nglich nur einer von dreien, die je nach Verteilung und
// durchschnittlicher Grï¿½ï¿½e der Rechtecke dynamisch ausgewï¿½hlt werden sollten. Es war jedoch
// schwierig, die Kosten fï¿½r die verschiedenen Algorithmen abzuschï¿½tzen. Am Ende ist dieser
// hier ï¿½brig geblieben. Nachdem ich ihn weiter optimiert hatte, war er in fast allen Fï¿½llen
// schneller als die Alternativen.
//
// Der Algorithmus funktioniert wie folgt: Die Rechtecke werden rï¿½ckwï¿½rts durchlaufen und
// in den Ausgabevektor "gezeichnet". Ein Pixel wird aber nur dann gezeichnet, wenn an dieser
// Stelle noch kein anderer Pixel gesetzt wurde, so dass immer nur das Rechteck mit dem grï¿½ï¿½ten
// Index sichtbar ist.
// Die Anzahl der verbleibenden, ungesetzten Pixel, wird mitgezï¿½hlt. Sobald sie null erreicht,
// sind wir fertig, da alle Pixel gesetzt wurden und die nachfolgenden Rechtecke sowieso nicht
// sichtbar wï¿½ren. Wenn erkannt wird, dass ein Generator verwendet wurde, der einen bestimmten
// Pixel frei lï¿½sst, wird der Algorithmus bereits bei nur noch einem ungesetzten Pixel abgebrochen,
// da er sonst alle Rechtecke bis zum Letzten durchlaufen mï¿½sste.
// Um verdeckte Bereiche von Rechtecken effizient verwerfen zu kï¿½nnen, wird fï¿½r jede Zeile und
// jede Spalte des Bilds gezï¿½hlt, wie viele Pixel noch ungesetzt sind. Zeilen und Spalten von
// Rechtecken, die keine ungesetzten Pixel mehr enthalten, kï¿½nnen dann sofort ï¿½bersprungen werden.
// Im inneren Teil der Schleife wird Loop-Unrolling verwendet, um die fï¿½r die for-Schleifen
// notwendigen Vergleiche zu reduzieren.
// Das Loop-Unrolling wird jedoch nicht verwendet, wenn nur sehr kleine Rechtecke in der Stichprobe
// gefunden wurden, ebenso das Mitzï¿½hlen der verbleibenden Pixel in den Zeilen und Spalten.
// Die Implementierung spart viel Zeit, indem sie auf die Vektorzugriffe verzichtet und stattdessen
// direkt mit Speicheradressen arbeitet.
//
// ************************************************************************************************
#include <vector>
#include "rectangle.hpp"

// Hilfsfunktionen, da auf min und max nicht immer Verlass ist ...
namespace util
{
	template<typename T> static inline const T& min(const T& a, const T& b) { return a < b ? a : b; }
	template<typename T> static inline const T& max(const T& a, const T& b) { return a > b ? a : b; }
}

// Makro fï¿½r Loop-Unrolling mit Duff's Device, 4x
#define DUFFS_DEVICE_4(COUNT, CONDITION, CODE)	\
	{											\
		switch((COUNT) & 3)						\
		{										\
		case 0: do {	{ CODE; }				\
		case 3:			{ CODE; }				\
		case 2:			{ CODE; }				\
		case 1:			{ CODE; }				\
				} while((CONDITION));			\
		}										\
	}

// Makro fï¿½r Loop-Unrolling mit Duff's Device, 8x
#define DUFFS_DEVICE_8(COUNT, CONDITION, CODE)	\
	{											\
		switch((COUNT) & 7)						\
		{										\
		case 0: do {	{ CODE; }				\
		case 7:			{ CODE; }				\
		case 6:			{ CODE; }				\
		case 5:			{ CODE; }				\
		case 4:			{ CODE; }				\
		case 3:			{ CODE; }				\
		case 2:			{ CODE; }				\
		case 1:			{ CODE; }				\
				} while((CONDITION));			\
		}										\
	}

// der Algorithmus
void algorithm(Rectangle plane,
			   std::vector<Rectangle> const& rectangles,
			   std::vector<std::vector<size_t> >& result)
{
	const size_t numRectangles = rectangles.size();
	if(numRectangles == 1)
	{
		// Da der Ausgabevektor netterweise schon mit Nullen gefï¿½llt ist,
		// muss hier nichts getan werden.
		return;
	}

	// ein paar Rechtecke ansehen (maximal 1024 Stï¿½ck) und die maximale Grï¿½ï¿½e ermitteln
	const Rectangle* const p_rectangles = &(rectangles[0]);
	const size_t numSamples = util::min(static_cast<size_t>(1024), numRectangles - 1);
	int maxRectSizeFound = 0;
	for(size_t sample = 0; sample < numSamples; sample++)
	{
		const size_t index = 1 + ((sample * 232792561) % (numRectangles - 1));
		const Rectangle& rect = p_rectangles[index];
		const int rectSize = (rect.maxx - rect.minx) * (rect.maxy - rect.miny);
		if(rectSize > maxRectSizeFound) maxRectSizeFound = rectSize;
	}

	// ein paar Werte vorberechnen
	const int planeW = plane.maxx - plane.minx;
	const int planeH = plane.maxy - plane.miny;
	const Rectangle* const p_start = &(rectangles[numRectangles - 1]);
	const Rectangle* const p_end = p_rectangles;
	const Rectangle* p_rectangle;
	size_t rectIndex = numRectangles - 1;

	// Startadressen der einzelnen Spalten speichern (das ist schneller als ein Vektorzugriff)
	size_t** const pp_cols = new size_t*[planeW];
	int x = 0;
	std::vector<size_t>* const p_colVectors = &result[0];
	DUFFS_DEVICE_4(planeW, x != planeW, { pp_cols[x] = &(p_colVectors[x][0]); ++x; })

	if(maxRectSizeFound == 1 &&
	   numRectangles == static_cast<size_t>(planeW * planeH + 1))
	{
		// Spezialfall fï¿½r Dot-Generator.
		// Die Rechtecke sind hï¿½chstwahrscheinlich alle nur 1x1 Pixel groï¿½.
		// Es ist daher nicht mï¿½glich, frï¿½her abzubrechen, wenn alle Bildpixel
		// gesetzt sind. Also mï¿½ssen die verbleibenden Pixel nicht gezï¿½hlt werden.
		for(p_rectangle = p_start; p_rectangle != p_end; --p_rectangle, --rectIndex)
		{
			// Clipping
			int sx = util::max(p_rectangle->minx - plane.minx, 0);
			int sy = util::max(p_rectangle->miny - plane.miny, 0);
			int ex = util::min(p_rectangle->maxx, plane.maxx) - plane.minx;
			int ey = util::min(p_rectangle->maxy, plane.maxy) - plane.miny;
			if(sx >= ex || sy >= ey) continue;

			// linken oberen Pixel setzen (wahrscheinlich der Einzige)
			size_t& r = pp_cols[sx][sy];
			if(!r) r = rectIndex;

			// ï¿½brige Pixel setzen, falls vorhanden
			if(ex > sx + 1 || ey > sy + 1)
			{
				for(int x = sx; x != ex; ++x)
				{
					size_t* const p_col = pp_cols[x];
					for(int y = sy; y != ey; ++y)
					{
						if(!p_col[y]) p_col[y] = rectIndex;
					}
				}
			}
		}
	}
	else if(maxRectSizeFound < 8)
	{
		// Spezialfall fï¿½r kleine Rechtecke.
		// Fï¿½r so kleine Rechtecke lohnt sich das Aufrollen der Schleifen nicht
		// und das Mitzï¿½hlen der verbliebenen Pixel in Zeilen und Spalten ebenfalls nicht.
		int left = planeW * planeH;
		if(maxRectSizeFound != 1) --left;
		for(p_rectangle = p_start; p_rectangle != p_end && left; --p_rectangle, --rectIndex)
		{
			// Clipping
			int sx = util::max(p_rectangle->minx - plane.minx, 0);
			int sy = util::max(p_rectangle->miny - plane.miny, 0);
			int ex = util::min(p_rectangle->maxx, plane.maxx) - plane.minx;
			int ey = util::min(p_rectangle->maxy, plane.maxy) - plane.miny;
			if(sx >= ex || sy >= ey) continue;

			// linken oberen Pixel setzen (wahrscheinlich der Einzige)
			size_t& r = pp_cols[sx][sy];
			if(!r) { r = rectIndex; --left; }

			// ï¿½brige Pixel setzen, falls vorhanden
			if(ex > sx + 1 || ey > sy + 1)
			{
				for(int x = sx; x != ex; ++x)
				{
					size_t* const p_col = pp_cols[x];
					for(int y = sy; y != ey; ++y)
					{
						if(!p_col[y]) { p_col[y] = rectIndex; --left; }
					}
				}
			}
		}
	}
	else
	{
		// Der Standardfall.
		// Es bleibt mindestens 1 Pixel frei.
		int left = planeW * planeH - 1;

		// Initialisierung der Arrays fï¿½r die verbleibenden Pixel in Zeilen und Spalten
		int* p_leftInCol = new int[planeW];
		int* p_leftInRow = new int[planeH];
		const int minDimension = util::min(planeW, planeH);
		int i = 0;
		DUFFS_DEVICE_8(minDimension, i != minDimension, { p_leftInCol[i] = planeH; p_leftInRow[i] = planeW; ++i; })
		if(planeW > minDimension) DUFFS_DEVICE_8(planeW - minDimension, i != planeW, { p_leftInCol[i++] = planeH; })
		else if(planeH > minDimension) DUFFS_DEVICE_8(planeH - minDimension, i != planeH, { p_leftInRow[i++] = planeW; })

		for(p_rectangle = p_start; p_rectangle != p_end && left; --p_rectangle, --rectIndex)
		{
			// Clipping
			int sx = util::max(p_rectangle->minx - plane.minx, 0);
			int sy = util::max(p_rectangle->miny - plane.miny, 0);
			int ex = util::min(p_rectangle->maxx, plane.maxx) - plane.minx;
			int ey = util::min(p_rectangle->maxy, plane.maxy) - plane.miny;
			if(sx >= ex || sy >= ey) continue;

			// Verdeckungstest, um ganze Zeilen und Spalten sofort auszuschlieï¿½en
			while(!p_leftInCol[sx] && sx != ex) ++sx;
			while(sx != ex && !p_leftInCol[ex - 1]) --ex;
			if(sx == ex) continue;
			while(!p_leftInRow[sy] && sy != ey) ++sy;
			while(sy != ey && !p_leftInRow[ey - 1]) --ey;
			if(sy == ey) continue;
			const int h = ey - sy;

			// Spalten durchlaufen
			for(int x = sx; x != ex; ++x)
			{
				// wenn die Spalte voll ist, sofort zur Nï¿½chsten gehen
				if(!p_leftInCol[x]) continue;

				// Pixel fï¿½llen
				size_t* const p_col = pp_cols[x];
				int y = sy;
				int hits = 0;
				DUFFS_DEVICE_4(h, y != ey, { if(!p_col[y]) { p_col[y] = rectIndex; ++hits; --p_leftInRow[y]; } ++y; })
				left -= hits;
				p_leftInCol[x] -= hits;
			}
		}

		delete[] p_leftInCol;
		delete[] p_leftInRow;
	}

	delete[] pp_cols;
}

C++ Forumbot

Leider ist der Thread beschädigt. Wird arbeiten gerade daran den Fehler zu beheben. Postet bitte so lange in dem Ersatz Thread

@Ponto
bitte kontaktiere mich (also rüdiger) per Mail oder im IRC, bevor du dein letzten Beitrag noch einmal postest. Danke