Optimale Sprite-Größe für Rotationen

8

Ich mache ein Sprite-basiertes Spiel und habe eine Reihe von Bildern, die ich in einer lächerlich großen Auflösung bekomme. Ich skaliere sie auf die gewünschte Sprite-Größe (zum Beispiel 64x64 Pixel), bevor ich sie in eine Spielressource konvertiere Sprite im Spiel, ich muss es nicht skalieren.

Wenn ich dieses kleine Sprite jedoch innerhalb des Spiels drehe (motorunabhängig), werden einige Zielpixel interpoliert und das Sprite sieht verschmiert aus.

Dies hängt natürlich sowohl vom Drehwinkel als auch vom Interpolationsalgorithmus ab, aber unabhängig davon gibt es nicht genügend Daten, um ein bestimmtes Zielpixel korrekt abzutasten.

Ich kann mir also zwei Lösungen vorstellen. Das erste besteht darin, das riesige Originalbild zu verwenden, es in die gewünschten Winkel zu drehen und dann alle resultierenden Variationen zu verkleinern und sie in einen Atlas zu legen, der den Vorteil hat, dass er recht einfach zu implementieren ist, aber naiv doppelt so viel Sprite verbraucht Platz für jede Umdrehung (jede Umdrehung muss in einen Kreis eingeschrieben sein, dessen Durchmesser die Diagonale des Rechtecks ​​des ursprünglichen Sprites ist, dessen Fläche doppelt so groß ist wie die des ursprünglichen Rechtecks, vorausgesetzt, es handelt sich um quadratische Sprites).

Es hat auch den Nachteil, dass nur ein vordefinierter Satz von Rotationen verfügbar ist, was je nach Spiel in Ordnung sein kann oder nicht.

Die andere Möglichkeit wäre also, ein größeres Bild zu speichern und es beim Rendern zu drehen und zu verkleinern, was zu meiner Frage führt.

Was ist die optimale Größe für dieses Sprite? Optimale Bedeutung, dass ein größeres Bild keine Auswirkungen auf das resultierende Bild hat.

Dies hängt definitiv von der Bildgröße ab, der Anzahl der gewünschten Umdrehungen ohne Datenverlust bis zu 1/256, was der minimal darstellbare Farbunterschied ist.

Ich suche nach einer theoretischen allgemeinen Antwort auf dieses Problem, da das Ausprobieren einer Reihe von Größen zwar in Ordnung ist, aber alles andere als optimal ist.

Panda Pyjama
quelle
3
Dies ist keine hilfreiche Antwort, aber ich las die Frage durch, sagte "Oh, das ist einfach!", Schrieb eine Antwort, runzelte die Stirn, las sie noch einmal und dachte dann ein paar Minuten lang gründlich darüber nach, bevor ich zu dem Schluss kam es ist in der Tat nicht einfach. Das heißt, mein Bauchgefühl ist "die doppelte Auflösung auf jeder Achse ist entweder perfekt oder definitiv gut genug", aber ich habe keine Beweise dafür. Schließlich vermute ich, dass dies dramatisch von dem Downscaling-Kernel abhängt, mit dem Sie vergleichen - ein einfacher Kernel mit Pixelmittelung ist möglicherweise leicht zu analysieren und zu replizieren, ein Lanczos-Kernel kann sich jedoch als unmöglich erweisen.
ZorbaTHut
Ich denke, Ihre Annahme, dass 1/256 die Grenze des akzeptablen Farbdifferenzdeltas ist, ist falsch, weil der traditionelle Farbraum (sRGB) nicht linear ist.
Sam Hocevar
@sam Es ist möglicherweise nicht linear, wenn es mit dem tatsächlichen Lichtspektrum berechnet wird, aber die Quantisierung ist linear. Es hängt jedoch wirklich vom Interpolationsalgorithmus ab, und die Ergebnisse können für lineare und beispielsweise bikubische Interpolation sehr unterschiedlich sein. Aber auch ohne Interpolation sollte es eine Möglichkeit geben, die optimale Größe zu berechnen.
Panda Pyjama
@zorbathut Die Antwort ist je nach Downsampling-Algorithmus definitiv unterschiedlich. Es sollte jedoch relativ einfach sein, eine allgemeine Lösung für die Interpolation zum nächsten Nachbarn oder zur linearen Interpolation zu finden. Ich arbeite noch daran, aber ich denke, dass für 8 Richtungen, sqrt (2) die Fläche optimal ist. Lassen Sie mich wissen, wo Sie ankommen
Panda Pyjama

Antworten:

7

Ich denke, was Sie versuchen, ist der 2D-Bildraum, der einer doppelten Rundung entspricht . Ich kann einen losen Beweis dafür konstruieren, dass es unmöglich ist , eine solche Zwischengröße zu finden, zumindest bei einfachen Downscaling-Algorithmen wie der linearen Interpolation.

Angenommen, wir haben festgestellt N, dass das Zwischenbild eine Größe hat N×N, die größer als ist 64×64. Angenommen, wir wenden noch nicht einmal eine Drehung an (Winkel ist Null).

Lassen Sie uns nun ein Bild erstellen, das nicht funktioniert.

Erstellen des Zwischenbilds

Betrachten Sie ein vollständig schwarzes Zwischenbild. Natürlich wird auch das endgültige Bild vollständig schwarz sein. Fügen Sie dann ein graues Pixel mit minimaler Intensität hinzu (R¸G, B = 1,1,1). Das endgültige Bild sollte immer noch vollständig schwarz sein. Fügen Sie ein weiteres graues Pixel hinzu, das das erste berührt. Erstellen Sie einen Kreis, bis das endgültige Bild nicht mehr vollständig schwarz ist.

Zwischenbild aufbauen Bild 1

Jetzt ist ein Pixel im endgültigen Bild grau (wenn wir für immer fortfahren würden, wäre das resultierende Bild vollständig grau, sodass offensichtlich irgendwann ein Pixel grau wird), und wenn wir das letzte Pixel entfernen, ist es wieder vollständig schwarz.

Erstellen des Originalbildes

Betrachten Sie das hypothetische Originalbild, das zu unserem Zwischenbild geführt hat. Ich kann nicht beweisen, dass es existiert, aber ich habe das starke Gefühl, dass es existiert. Wenn das Originalbild beispielsweise eine Größe hat 2N×2N, kann dies sein:

Original Bild Bild 2

Wenn Sie Bild 2 auf die mittlere Größe verkleinern, erhalten Sie Bild 1.

Und nach der Hypothese erhalten 64×64wir beim Herunterskalieren auf einen grauen Punkt im endgültigen Bild.

Lassen Sie uns nun das letzte Pixel, das wir hinzugefügt haben, auseinander brechen und im ursprünglichen Cluster verteilen:

nicht funktionierendes BildBild 3

Dies ist unser Gegenbeispiel.

Wenn dieses Bild auf die endgültige Größe verkleinert wird, sollte es ein graues Pixel ergeben, da die von uns gestreuten Pixel noch näher am Cluster liegen und die globale Intensität mindestens genauso hoch ist.

Wenn dieses Bild auf die mittlere Größe verkleinert wird, sollte das spezielle Pixel fehlen, da es verstreut ist, sodass wir bei der zweistufigen Größenänderung ein vollständig schwarzes Bild erhalten.

Schlussfolgerung und zukünftige Gedanken

Ich hoffe, das überzeugt Sie davon, dass das, was Sie erreichen wollen, im allgemeinen Fall nicht funktioniert.

Mein Ansatz für Ihr Problem wäre, die beste Größe pro Bild zu berechnen : Beginnen Sie mit dem Originalbild und z. N = 128Versuchen Sie dann alle möglichen Winkel und berechnen Sie den maximalen Fehler. Wenn der maximale Fehler nicht zufriedenstellend ist, versuchen Sie es N = 256 usw., bis Sie die richtige Größe erhalten.

Sam Hocevar
quelle
Dieses Problem als doppelte Rundung zu betrachten, ist ein ziemlich interessanter Ansatz, aber ich möchte Ihrer Hypothese nicht zustimmen, dass dies unmöglich ist, da Sie dies numerisch und nicht als Signalproblem betrachten. Betrachten wir ein eindimensionales Signal. Durch Abtasten an n Punkten behalten wir alle Informationen mit Frequenzen bis zu 1 / 2n bei . Mit dem Satz von Nyquist ist es möglich, das Signal an m> n Punkten abzutasten und es dann an n Punkten erneut abzutasten und zu demselben Ergebnis zu gelangen, als hätten wir es ursprünglich an n Punkten abgetastet . Dies kann leicht auf n-Dimensionen erweitert werden.
Panda Pyjama
1
@PandaPajama Wenn Sie Nyquist aufrufen, gehen Sie leider davon aus, dass das Signal streng bandbegrenzt sein kann, was nicht der Fall ist, wenn sich unsere Samples über einer diskreten Domäne befinden. Dies ist, was mein Gegenbeispiel ausnutzt und warum es mit Rundung zusammenhängt.
Sam Hocevar
Wenn das Originalbild beliebig groß ist, kann es jedoch als kontinuierlich betrachtet werden. In einer praktischeren Diskussion ist Ihr Argument jedoch gültig, wenn Sie einen sehr spezifischen Algorithmus für das Downscaling mit einer ganz bestimmten Größe (2x) in Betracht ziehen. Bilineare und bikubische Interpolationen in der Nähe des Nachbarn ergeben unterschiedliche Ergebnisse. Speziell für den nächsten Nachbarn glaube ich, dass es möglich ist, geometrisch eine allgemeine Lösung zu konstruieren, aber das muss auf das Wochenende warten.
Panda Pyjama
1
@PandaPajama Sie sind wieder richtig, sehr große Bilder können als kontinuierlich betrachtet werden, aber das Problem ist, dass sich das Zwischenbild immer noch in einer diskreten Domäne befindet. Auch der nächste Nachbar leidet per Definition nicht unter dem Rundungsproblem, aber abgesehen von trivialen Fällen leidet er unter 1) Problemen im Zusammenhang mit dem Gleichverteilungssatz , der die Mindestgröße nahe an 6400 × 6400 bringt, d. H. ziemlich unpraktisch und 2) schwerwiegende Aliasing-Probleme.
Sam Hocevar