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!

Sortieralgorithmus für Elemente im Scenegraphen

Werbeanzeige

Sylence

Community-Fossil

  • »Sylence« ist der Autor dieses Themas

Beiträge: 1 663

Beruf: Softwareentwickler

  • Private Nachricht senden

1

08.01.2012, 19:50

Sortieralgorithmus für Elemente im Scenegraphen

Ich wollte einfach mal weiter Meinungen zu meinem Gedankengang einholen.
Und zwar geht es um die Sortierung der Liste der Objekte in einem Spiel, die gerendert werden sollen.

Da ich ja davon ausgehen kann, dass diese Liste in den meisten Fällen (annähernd) komplett sortiert ist fällt QuickSort mit O(n²) ja weg, also habe ich mich für MergeSort mit O(n*log(n)) entschieden.

Hab ich da irgendwelche Denkfehler, oder seht ihr das Ähnlich? Oder habt ihr vielleicht sogar einen effizienteren Algo für den fall einer fast sortierten liste parat?

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

2

08.01.2012, 19:53

Für welche Anwendung willst du denn die Objekte sortieren und vorallem nach welchen Kriterium? Geht es um die Renderreihenfolge oder Sichtbarkeit? Und vorallem warum willst du sie sortieren? Willst du "manuell" rendern oder bestimmte Objekte ausschließen?
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

Sylence

Community-Fossil

  • »Sylence« ist der Autor dieses Themas

Beiträge: 1 663

Beruf: Softwareentwickler

  • Private Nachricht senden

3

08.01.2012, 19:55

Ja genau es geht um die Renderreihenfolge. Die Anwendung ist ein 3D-Spiel in XNA.
Das Kriterium ist ein einfacher Integer, der angibt in welcher Reihenfolge gerendert (und upgedatet) werden soll.

Warum ich sortieren will? Naja ich brauch ja schon ne Reihenfolge in der ich meine Objekte render. Alles wild durcheinander ist ja nicht unbedingt performant (Stichwort Textureswitches, etc. )

drakon

Supermoderator

Beiträge: 6 513

Wohnort: Schweiz

Beruf: Entrepreneur

  • Private Nachricht senden

4

08.01.2012, 19:58

Wenn eine Liste bereits vorsortiert ist kommt es nicht so sehr auf die Laufzeit drauf an, sondern eher auf die Konstanten und da eignet sich Bubblesort oder Insertionsort z.B auch sehr gut. Ich würde sagen, dass das in dem Fall effizienter sein kann als Quicksort oder Mergesort, da die doch einigen anderen Overhead mitbringen.

Ob das wirklich so ist lässt sich allerdings nur durch testen heraus finden.
http://www.drakon.ch | Weltweit 31. Bester Solitär Spieler (Standard XP)

Sylence

Community-Fossil

  • »Sylence« ist der Autor dieses Themas

Beiträge: 1 663

Beruf: Softwareentwickler

  • Private Nachricht senden

5

08.01.2012, 20:00

Zitat von »drakon«

Wenn eine Liste bereits vorsortiert ist kommt es nicht so sehr auf die Laufzeit drauf an, sondern eher auf die Konstanten


Von der Seite hab ich das noch gar nicht betrachtet... Manchmal sieht man vor lauten Bäumen den Wald einfach nicht.

Werbeanzeige

Ähnliche Themen