[gelöst] Das größte Rechteck

[Zudomon]

Erstmal wollte ich jetzt in jede Achse einen Chunk durchgehen und schauen, dass ich diese Ebene dann durch möglichst wenig Rechtecke annähern kann.
Diese dürfen sich dabei gerne überlappen, sollten es sogar, zumindest an den Rändern, da ich beim Occlusiontest die einzelnen Occluder nicht mergen kann und die Patches, die dann auf den Kanten liegen nicht weg gecullt würden.
Aber soweit bin ich noch lange nicht, denn ich scheitere eigentlich schon an der Verteilung.

So sieht eine ausgewählte Ebene im Querschnitt aus. Jedes Quadrat ist ein gefüllter Voxel.

Mein erster Ansatz war nun, das ganze in Streifen zu betrachten und dann die Streifen, die gleich lang sind und nebeneinander liegen, zu mergen. Dabei kommt das hier raus:

Ich denke, das geht aber sicher noch besser. Dachte nun, dass man die Nachbarn wieder zersplitten könnte beim mergen, also z.B. die beiden Streifen ganz Links, die könnte man durch 2 Rechtecke darstellen, wobei dann eins sehr groß ist und das andere nur ein einzelnes kleines Quadrat oben. Aber eigentlich kommt mir das alles etwas schwierig vor. Eigentlich sollte es doch möglich sein, direkt das beste (falls es das überhaupt gibt) Ergebnis zu bekommen, wenn man zunächst das größtmögliche Rechteck sucht, dann dies herausnimmt und bei dem Rest wieder das größtmöglichste sucht.
Doch auch hier weiß ich irgendwie nicht, wie man das geschickt angehen kann? Selbst wenn man erstmal nur ein Rechteck herauspickt und es solange erweitert, bis es an die "Grenzen" stößt, gibt es da ja auch schon wieder mehrere Ergebnisse, je nachdem in welche Achsen man wie lange erweitert. Also meine Frage, gibt es da einen schlauen und einfachen Ansatz, wie man nun da das größte Rechteck finden kann?


EDIT:
Hier noch ein bemaltes Bild, wie es eigentlich am Ende aussehen sollte...

EDIT2:
Also allein wenn man sich wahllos ein Quadrat rausfischt und dazu mal schaut, welche größten Rechtecke dieses beinhalten, kommt man auf allerhand Lösungen.

[Krishty]

Sry; nicht alles gelesen & in Eile, aber von den Bildern her:

1. Signed Distance Field aufbauen – allerdings Distanzen nur entlang der Achsen berechnen, nicht diagonal! [damit tauschst du Entscheidungszeit gegen Speicherplatz; aber in deinem Fall reicht wohl ein Feld von 8-Bit signed ints aus]
2. Maximalwert suchen – seine Position ist der Mittelpunkt des größtmöglichen Rechtecks, und der Wert selber ist die kleinste Seite des größtmöglichen Rechtecks [so lange es kein Quadrat ist, wird das Maximum entlang einer Geraden verteilt sein – macht aber nichts]
3. die anderen Seiten Schritt für Schritt vergrößern, bis du an eine Kontur stößt
4. das ist dein neues größtes Rechteck
5. dieses Rechteck aus den Konturen löschen
6. mit dem Rest wiederholen bis nichts mehr da ist

3–5 können parallelisiert werden, falls du bei 2. mehr als ein zusammenhängendes Maximum findest

[Zudomon]

Sry; nicht alles gelesen & in Eile, aber von den Bildern her:

Kein Problem

Zu 1 und 2 noch:
1. Also ich hätte dann 2 x SDF, eine für den Maximalwert in der X und eine in der Y Achse, wenn ich das jetzt richtig verstanden habe.
2. Das größtmögliche Rechteck müsste doch das sein, wo dann X * Y den Maximalwert bildet (also die größte Fläche des Rechtecks). Wobei vielleicht wichtiger als maximale Fläche, eine quadratische Form ist. Ich weiß gerade nicht, ob man das wirklich beachten muss. Aber mal für später im Hinterkopf behalten.

Jedenfalls danke Krishty!
Ich hatte die Tage auch mal kurz an SDF gedacht, aber direkt verworfen, weil ich nicht wusste, ob in einzelnen Achsen zu splitten was bringt. Aber ja, irgendwie macht das Sinn. :D

[Krishty]

Nur EIN sdf, und zwar aus min(x, y) :)

[Zudomon]

Da habe ich dann heute Nacht euphorisch mit dem SDF begonnen, aber dann kamen mir doch nach und nach Zweifel.
Also erstmal weiß ich nicht genau, ob ich es richtig erstellt habe. Ich habe in jeder Achse dann quasi die maximale Kästchenzahl bis zum Rand. Egal ob X*Y für die Fläche oder min(X, Y), bekomme ich dadurch ja auch nur eine Position raus. Aber wie bei meinem EDIT2 zu sehen, gibt es zu jeder Position eine ganze Menge an möglichen Rechtecken. Entweder habe ich das Verfahren nicht verstanden, was ich nicht ausschließen würde, oder es funktioniert nicht so wie gedacht.

Ich hatte aber dann doch noch eine Idee, wie man es machen kann... ohne SDF allerdings. Für diesen Testfall braucht das weniger als 5 ms. Ist noch etwas langsam, weil ich ja das ganze 32 x 3 mal durchführen möchte pro Chunk.

[dot]

[youtube]VNbkzsnllsU[/youtube]

[Zudomon]

Danke dot, aber soweit ich das beurteilen kann, verfehlt es das Problem. Bei mir liegen die Quads ja kreuz und quer und sind nicht an einer Achse ausgerichtet wie beim Histogramm