Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Größtmögliche Rechtecke in einem Gitter

Werbeanzeige

Helco

Frischling

  • »Helco« ist der Autor dieses Themas

Beiträge: 59

  • Private Nachricht senden

1

26.02.2013, 16:31

Größtmögliche Rechtecke in einem Gitter

Hi,ich arbeite gerade an einen recht Perfomance-lastigen Programm (2D-Metaballs), dessen Geschwindigkeit ich schon stark erhöht habe, indem ich den Bildschirm in ein regelmäßiges Gitter (32x24 Zellen) eingeteilt habe und nur die Zellen zeichne, in welchem sich eine Ausgabe befinden könnte.
Allerdings optimierungsfreudig wie ich gerade bin, würde ich gerne Zellen zu größeren rechteckigen Feldern zusammenfassen also statt jede Zeile einzeln zu zeichnen, 3x4 Zellen mithilfe eines Quad (ich benutze OpenGL) auf einmal zeichnen.
Leider habe ich keine Ahnung wie ich den gewünschten Algorithmus effizient aufsetzen soll...

Mfg
Helco

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

2

26.02.2013, 16:59

Metaballs im Shader berechnet dürften doch eigentlich schnell genug sein, als dass da keinerlei Optimierung notwendig ist. Oder nicht?
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Helco

Frischling

  • »Helco« ist der Autor dieses Themas

Beiträge: 59

  • Private Nachricht senden

3

26.02.2013, 17:29

Nun wenn ich größere Teile des Bildschirms berechnen lasse, brauche ich für eine Berechnung bis zu 17ms.
Da ich plane Metaballs in ein Spiel einzubauen, sodass sich diese bewegen, muss ich jeden Frame die Metaballs neu berechnen, wo diese Metaballs dann schon ein Slowdown bedeuten. Natürlich sind diese 17ms schon ein sehr extremer Fall, aber man muss ja auch bedenken dass das jetzige Programm nur die Metaballs berechnet. Das Spiel wird natürlich auch noch einiges brauchen und nicht jeder hat eine Geforce 630.
Bevor jemand fragt: Natürlich habe ich noch andere Optimierungen (z.B.: Potentialvorberechnung,2. Bereichsüberprüfung)
Und ein weiterer unabhängiger Grund: ich bin schon mal auf ein ähnliches Problem gestoßen (im Zusammenhang mit Wegfindung), wo ein solcher Algorithmus ganz nützlich wäre...

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

4

26.02.2013, 19:07

Wie genau renderst du die Zellen jetzt? Ich vermute mal, dass du für jede Zelle einen separaten Drawcall hast? Könntest du nicht alle Zellen auf einmal rendern, verwenden ja wohl sowieso alle den gleichen Shader!? Weil ob du jetzt 100 oder 300 Rechtecke malst, wird, zumindest auf aktueller PC Hardware, praktisch keinen Unterschied machen; ob du aber einen oder 300 Drawcalls hast, wird in dem Fall einen vergleichsweise gewaltigen Unterschied machen...
m4studios

Helco

Frischling

  • »Helco« ist der Autor dieses Themas

Beiträge: 59

  • Private Nachricht senden

5

26.02.2013, 19:23

Zitat von »dot«


Wie genau renderst du die Zellen jetzt?

so:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9

//gekürzt
glBegin(GL_QUADS);
for (auto it=gridsToCheck.begin ();it!=gridsToCheck.end();++it) {
    glTexCoord2f(0.0f,1.0f);glVertex2f(pos.x,pos.y);
    glTexCoord2f(1.0f,1.0f);glVertex2f(pos.x+pos.w,pos.y);
    glTexCoord2f(1.0f,0.0f);glVertex2f(pos.x+pos.w,pos.y+pos.h);
    glTexCoord2f(0.0f,0.0f);glVertex2f(pos.x,pos.y+pos.h);
}
glEnd();

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

6

26.02.2013, 19:30

Das ist quasi die langsamste Methode, die Du nehmen kannst.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

7

26.02.2013, 19:30

Ich würde wenn dann nicht versuchen, die Zellen nachträglich zusammenzufassen, sondern eher bereits beim Bestimmen der in Frage kommenden Zellen einen hierarchischen Ansatz verfolgen, vielleicht etwas in Richtung Warnock Subdivision...

Mich wundert aber ehrlich gesagt, dass das Zeichnen der Rechtecke 17ms dauern soll, selbst mit glBegin()/glEnd(). Bist du auch ganz sicher, dass das Zeichnen der Rechtecke das Bottleneck ist? Wie hast du das überprüft? Wieviele Rechtecke zeichnest du denn so im Schnitt und was ist da für ein Shader drauf?
m4studios

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »dot« (26.02.2013, 19:38)

Helco

Frischling

  • »Helco« ist der Autor dieses Themas

Beiträge: 59

  • Private Nachricht senden

8

27.02.2013, 07:15

Zitat von »dot«

Bist du auch ganz sicher, dass das Zeichnen der Rechtecke das Bottleneck ist?

Und damit hast du mich auf die richtige Spur gebracht, ich hab die Messung (mithilfe von SDL_GetTicks() ) verfeinert und gesehen dass tatsächlich weder das Übertragen der Parameter an den Shader (=Metaballs), noch das Rendern und auch nicht der Gaussian-Blur maßgeblich an der Dauer (jeweils meistens <1ms) sondern lediglich das auswählen die für das Rendern bestimmten Zellen.
Ich werde versuchen, den betreffenden Code nochmal zu überarbeiten um eine bessere Performance zu bekommen.

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

9

27.02.2013, 07:36

Was genau ist gridsToCheck für ein Ding und wie wird es befüllt? Mein erster Blick wär jedenfalls in diese Richtung...
m4studios

Helco

Frischling

  • »Helco« ist der Autor dieses Themas

Beiträge: 59

  • Private Nachricht senden

10

27.02.2013, 15:57

und diese Richtung war genau die richtige!
Da ich nicht genau nachgedacht habe, war ich gedanklich steckengeblieben in der Vorstellung eine Liste mit allen zu rendernden Zellen zu erstellen. Natürlich muss dann bei jeder Zelle die als "zu rendern" markiert wird, die gesamte Liste durchgegangen werden, um zu schauen ob sich die Zelle schon in der Liste befindet, damit sie nicht doppelt gerendert wird.
Da hilft auch keine binäre Suche wie es (hoffentlich) bei einem std::set (das ich für gridsToCheck benutzt habe) der Fall ist. Eine solche Datenstruktur würde sich vermutlich erst dann bewähren wenn man eine sehr große mögliche Anzahl an Elementen hat von der nur wenige gespeichert werden.
Sobald ich diese Liste ersetzt habe (durch ein einfaches byte-array) dauerte selbst der genannte Extremfall weniger als 1ms.
Auch wenn ich weiterhin an ein Algorithmus zur Zusammenfassung von Zellen in einem Gitter interessiert wäre, bin ich dankbar für eure Hilfe an diesem Problem und bin froh über diese Lösung, da sie sehr viel simpler (und vermutlich besser) ist als meine Idee.

Werbeanzeige

Ähnliche Themen