Programmieren - alles kontrollieren 4.941 Themen, 20.708 Beiträge

Verfolgung starten Optionen

Performant sortieren

Yves3 / 8 Antworten / Baumansicht Nickles

Hallo

Ich habe ein eindimmensionales WORD-Array.
Immer 6 Werte in diesem Array gehören zusammen und ihnen ist ein Wert aus einem zweidimmensionalen Int-Array zugeordnet.

Dabei geht es um eine TileEngine.. Den 6 Word-Indices ist je eine Textur zugeordnet.

Ich muss jetzt die Indices nach den Texturen sortieren, denen sie zugeordnet sind und je in einem separaten Array der Reihe nach festhalten, (1) um welche Textur es sich handelt und (2) wie viele Indices zu dieser Textur passen.

Am Schluss würde ich dann also 3 Arrays verwenden:
1. Array mit allen Indices sortiert nach dazugehörigen Texturen
2. Array, in dem gespeichert ist, welche Textur jeweils zu den Indices gehört
3. Array das angibt, wieviele Indices jeweils zur gleichen Textur gehören

Ich rufe dann die Zeichenfunktion für jede Textur einmal auf, so nach dem Stil:

int StartIndex=0;
for(int i=0; i {
SetTexture(Textur[Array2[i]])
Draw(Array1, StartIndex, StartIndex+Array3[i]);
StartIndex += Array3[i];
}

Der Witz an dem ganzen ist, dass das Sortieren und das Erstellen der 3 Arrays in jedem Frame gemacht werden musss und es daher schon verdammt schnell sein müsste.
Meine bisherigen Lösungsideen scheinen mir alle ein bisschen umständlich.

Ich hoffe ihr hab verstanden, wie ich das meine und könnt mir eventuel l helfen :)

Danke!





[Diese Nachricht wurde nachträglich bearbeitet.]

bei Antwort benachrichtigen
mr.escape Yves3 „Performant sortieren“
Optionen
Ich hoffe ihr hab verstanden, wie ich das meine
Nicht die bohne!
Ist den sechs verbundenen WORD werten gemeinsam ein wert oder jeweils ein wert (d.h. sechs) aus dem "zweidimensionalen Int-Array" zugewiesen oder verweist das "zweidimensionale Int-Array" auf die sechsergruppe?

Wie hängen WORD werte, indices, texturen und "zweidimensionales Int-Array" zusammen (was ist was)?

Meine bisherigen Lösungsideen scheinen mir alle ein bisschen umständlich.
Und die wären?

mr.escape
"The man who trades freedom for security does not deserve nor will he ever receive either." - Benjamin Franklin"Wer seine Freiheit aufgibt, um Sicherheit zu erreichen, wird beides verlieren." - Georg Christoph Lichtenberg
bei Antwort benachrichtigen
Yves3 mr.escape „ Nicht die bohne! Ist den sechs verbundenen WORD werten gemeinsam ein wert oder...“
Optionen

Hmm ist schwer zu erklären.
Diese 6 Indices stellen sozusagen ein Tile dar (2 Dreiecke mit gesamthaft 6 Punkten).
Diesem Quadrätchen ist ein Texturset zugeordnet.
Das mache ich mit dem zweidimmensionalen Int-Array.
Dieses Array stellt die Karte dar. In etwa so (natürlich viel grösser)

1 1 1 1 1 1
2 2 2 2 2 2
33 45 34 34 45 44
12 22 22 23 24 11

In den ersten beiden Reihen würde Texturset1 verwendet, in der dritten Reihe Texturset 2 und in der letzten Reihe wieder Texturset 1 (Da in einem Texturset 32 Texturen gespeichert sind)
Weleche Textur aus dem Set verwendet wird, ist mit den Texturkoordinaten des Vertex definiert... nicht weiter wichtig im Bezug auf mein Problem.
Ich muss jetzt, immer wenn gescrollt wird, die momentan auf dem Bildschirm sichtbaren Indexdaten(im WORD-ARRAY) sortiert nach den dazugehörigen Texturen in ein zweites WORD-Array kopieren.

Ein Lösungsansatz von mir:

Struktogramm

Der Nachteil ist eben, dass für jedes sichtbare Tile die ganze Liste der schon gefundenen Textursets durchlaufen und überprüft werden muss.
Beim eigentlichen Sortieren muss dann auch pro Texturset jedes Tile einmal überprüft werden.

Ich hoffe das war jetzt verständlich beschrieben, das ist wirklich schwer zu erklären...

[Diese Nachricht wurde nachträglich bearbeitet.]

bei Antwort benachrichtigen
Andreas42 Yves3 „Hmm ist schwer zu erklären. Diese 6 Indices stellen sozusagen ein Tile dar 2...“
Optionen

Hi!

Ich bin mir noch nicht sicher, ob ich es richtig verstanden habe. Ich versuche es mal anders und mit eigenen Worten zu beschreiben:

Die 6 Word-Werte beschreiben ein aus zwei Dreiecken zusammengesetzes Viereck (kein Quadrat) - ein Tile.
Dein Programm kennt verschiedene Texturen.
Es wird festgelegt, welches Tile mit welcher Textur gezeichnet wird.

Im Programm muss für jedes Frame (=bei jedem Neuzeichnen des Bildes) bestimmt werden,w elche Tiles sichtbar sind.
Um das Zeichnen der Tiles zu beschleunigen, sollen die mit der gleichen Textur nacheinander gezeichnet werden (ich vermute, dass ein Umschalten der Textur zeitaufwendig ist).

Das Problem ist jetzt die Tiles möglichst zeiteffektiv nach ihrer zugeordneten Textur zu sortieren.

Hmm.

Ist da eigentlich wirklich eine Sortierung nötig? Recht es da nicht einfach ein Liste der Tiles anzulegen, die einer Textur zugeordnet sind und die dann abzuarbeiten? Wieviele Texturen verwendest du maximal? 10, 100 oder 1000? Bis 100 dürfte es doch machbar sein, die zu zeichneten Tiles einfach in einem Pufferarry einzusortieren, den man vorher mit fixer länge anlegt.

Bis dann
Andreas

Hier steht was ueber mein altes Hard- und Softwaregedoens.
bei Antwort benachrichtigen
Yves3 Andreas42 „Hi! Ich bin mir noch nicht sicher, ob ich es richtig verstanden habe. Ich...“
Optionen

Ja, genau so ist es.
Nur ein Punkt muss ich vielleicht noch mal genauer erklären:
Die Indices geben eigentlich nur an, welche Vertices(Punkte) in welcher Reihenfolge verwendet werden, um die Tiles zu zeichnen.
In meinem Fall spare ich dadurch 2 Vertices pro Tile.
Ein Index ist also nichts weiter als eine Zahl, die für den Vertex steht.

Zu deinem Tipp:
Die Zeichenfunktion von DirectX ist vorgegeben und verlangt als Parameter den Start- und Endindex.
Vorher wird eine Textur gewählt, was eben immer etwas Zeit braucht.

Auch die Zeichenfunktion braucht etwas Setupzeit... optimal wäre schon eine Sortierung.
Dein Tipp beinhaltet aber einen ziemlich interessanten Denkansatz.
Vielleicht sollten die Indices ja schon vor dem Aufrufen meiner Zeichnungsfunktion geordnet sein, oder wenigstens in einer Form, in der sie leichter geordnet werden können.
Wenn ich sie aber einfach nach Texturset geordnet abspeichere, wird es sehr schwer und wieder rechenaufwändig, herauszufinden, welche sichtbar sind.
Irgendwelche festen Grössen gibt es leider auch nicht, weil man ziemlich weit rauszoomen können sollte.

Das mit der Anzahl Texturen ist noch schwer vorauszusagen.
Wie schon erwähnt beinhaltet ein Texturset 32 Texturen... ich werde wahscheinlich ein Set pro Texturtyp verwenden.
Also beispielsweise eins für Gras mit verschiedenen Variationen und Übergängen zu Texturen von anderen Sets.
Also für jeden erdenklichen Bodentypen ein Set. Gras, Sand, Ödland, Marsboden, Mondboden, Asphalt, Schnee (wahrscheinlich mehrere Sets), Waldboden, Jungelboden, Eis, Sumpf, verseuchtes Gebiet... was mir dann noch einfällt.

[Diese Nachricht wurde nachträglich bearbeitet.]

bei Antwort benachrichtigen
Andreas42 Yves3 „Ja, genau so ist es. Nur ein Punkt muss ich vielleicht noch mal genauer...“
Optionen

Hi!

Jetzt verstehe ich (denke ich zumindest ;-) ) was du vorhast bzw. benötigst. An der Stelle wird es dann auch zeit zu schreiben, dass ich mich selbst noch nie mit 3D-Grafik (in der Programmierung) befasst habe, deshalb kann ich nur Vorschläge amchen, wie man die datensache angeht.

Da hab' ich noch eine Anmerkung: eigentlich hatte ich gedacht, dass man die geordnete Speicherung nur mit den Sichtbaren Tiles durchführt, das ganze dann also an die Routine hängt, die den sichbaren Bereich berechnet. (Ich gehe jetzt vom normalen Clipping aus).

Die nächste Idee/Frage ist dann natürlich, ob man die Sortierung des vorherigen Bildes mitnutzen kann, also im Prinzip die sortierten Tiles durhclaufen, die nicht sichtbarn entfernen und dann nur die neu hinzugekommen einsortieren.

Bis dann
Andreas

Hier steht was ueber mein altes Hard- und Softwaregedoens.
bei Antwort benachrichtigen
Yves3 Andreas42 „Hi! Jetzt verstehe ich denke ich zumindest - was du vorhast bzw. benötigst. An...“
Optionen

Bisher hatte ich ja auch vor, nur den sichtbaren Teil zu sortieren.
Das ist aber immer noch ne ganze Menge und ich habe dafür noch keinen wirklich guten Algorithmus.
Das Struktogramm in dem Beitrag weiter oben ist eine Lösung dafür, eben leider eine ziemlich lahme.

Den zweiten Punkt von dir hab ich mir auch schon durch den Kopf gehen lassen, da müssen aber ziemlich viele Eventuealitäten beachtet werden... man kann in alle Richtungen scrollen und auch zoomen.
Ich hab schon vor einiger Zeit mal versucht, ein Bild so ähnlich zu scrollen.
Also einfach ein gigantisches Bitmap und dann beim Scrollen streifenweise neue Teile laden.
Das ist verdammt komplex und jetzt in meinem Beispiel eher noch eine Stufe komlexer.
Beim Scrollen entsehen ja sozusagen Lücken im bisher durchgehend gefüllten WORD-ARRAY.
Diese Lücken müssen dann irgendwie wieder gestopft werden und gleichzeitig müssen neue Daten dazwischengequetsche werden. Ich denke das wird am Schluss langsamer als wenn ich alles neu mache.

bei Antwort benachrichtigen
mr.escape Yves3 „Bisher hatte ich ja auch vor, nur den sichtbaren Teil zu sortieren. Das ist aber...“
Optionen

Du könntest doch die sichtbare liste durchgehen und in ein n-faches array jeweils eine verkettete liste aufbauen.
Das n-fache array hätte für jede textur einen eintrag (den start der jeweiligen verketteten liste), also nur einmal allozieren und die elemente der verketteten liste kämen auch aus einem vorher allozierten array für die "tiles".
Z.b.:
class TileList;
class TileList {
    Tile tile;//oder auch *tile, was immer am besten passt bzw. bedeutet
    TileList *next;
};

class TextList {
    Texture texture;//oder auch *texture, was immer am besten passt bzw. bedeutet
    TileList *first;
    TextList(){first=NULL;}
}

//dann später im code

TileList tilelist[tilecount];//statisch oder dynamisch, jedenfalls ein array
TextList textlist[textcount];//dito

//und in jedem frame
for(int i=0;i<textcount;i++) tlist[i].first=NULL;//verkettete liste leeren
for(int i=0;i<tilecount;i++){//bzw. nur die sichtbaren!
    int acttext=GetTextNum(i);//gibt die texturnummer für tile i zurück
    //könnte auch ein tile[i].textnum sein o.ä.
    tilelist[i].next=textlist[acttext].first;
    textlist[acttext].first=tilelist+i;
}
//und dann beim zeichnen
for(int i=0;i<textcount;i++){
    TileList *acttile=textlist[acttext].first;
    if(acttile) SetTexture(i);
    else continue;//unbenutzte textur
    while(acttile){
        DrawTile(acttile->tile);
        acttile=acttile->next;
    }
}

"The man who trades freedom for security does not deserve nor will he ever receive either." - Benjamin Franklin"Wer seine Freiheit aufgibt, um Sicherheit zu erreichen, wird beides verlieren." - Georg Christoph Lichtenberg
bei Antwort benachrichtigen
Yves3 mr.escape „Du könntest doch die sichtbare liste durchgehen und in ein n-faches array...“
Optionen

Schon mal vielen Dank für die Hilfe euch beiden!

Ich kann zwar noch nicht sicher sagen ob ich mit dem Tipp von mr.escape eine gute Lösung finden werde, das sieht aber schon mal vielversprechend aus.
Ich weiss schon, warum ich die Frage hier und nicht in irgend einem DirectX-Forum gestellt habe... auch wenn es halt ein bisschen dauterte, bis man mich verstand. :)

Jetzt brauch ich erst mal eine Weile, bis ich das durch meine langen und weit verschlungenen Gehirnwindungen durchgelassen habe und sehe, ob was dabei rauskommt. Hab leider in den nächsten Tagen auch nicht besonders viel Zeit.
Also schaut bitte mal wieder vorbei, auch wenn es nur ist, um noch mal meinen Dank zu empfangen ;-)

EDIT: Ich hatte jetzt ein Bisschen Zeit mir das mal genauer anzuschauen.
Das ist einfach genial. Ich kann das zwar nicht direkt so übernehmen, das Grundprinzip werde ich aber beibehalten können.
Heute Abend habe ich mal wieder Zeit zum Coden :)

Gruss yves3



[Diese Nachricht wurde nachträglich bearbeitet.]

bei Antwort benachrichtigen