Nearest Color in Palette finde

Für Fragen zu Grafik APIs wie DirectX und OpenGL sowie Shaderprogrammierung.
Antworten
Benutzeravatar
Zudomon
Establishment
Beiträge: 2253
Registriert: 25.03.2009, 07:20
Kontaktdaten:

Nearest Color in Palette finde

Beitrag von Zudomon »

Beim Devil Daggers spielen hab ich mir so gedacht, dass für den Retro look ja die Farben quantisiert werden.

Sowas hatte ich auch schonmal gemacht, indem ich einfach die Farbwerte gesnappt hatte.
Dann habe ich mich an Duke Nukem 3D erinnert. Da hatte man eine Palette und wurde eine Farbe dargestellt, wurde das mit der Farbe aus der Palette gemacht, die dem am nahesten gekommen ist. Also z.B. Schattierungen. Ich weiß allerdings nicht, ob das dynamisch war, oder irgendwie vor berechnet war.
Und da frage ich mich nun wie sowas eigentlich gemacht wird. Also wenn man eine Palette hat, kann man dann irgendwie für eine 32 Bit Farbe schnell und dynamisch die beste Farbe aus der Palette finden?
Das Einzige, was mir dafür in den Sinn käme, wäre da eine 32 Bit Lookup Table zu machen, die hätte natürlich 256³ Byte.

Eigentlich interessiert mich das nur so. Aber vielleicht könnte man es auch später nutzen, um nochmal irgendwie Texturspeicher zu sparen.
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Nearest Color in Palette finde

Beitrag von Krishty »

Intuitiv dürften die meisten Ansätze auf regelmäßigen und vorsortierten Paletteneinträgen basieren. Wenn man ein bestimmtes RGB annähern will, ergibt sich der Index recht schnell z.B. aus R÷32 + 8 · G÷32 + 64 · B÷32.

Flipcode hatte AFAIK einen Artikel über Alpha Blending mit Paletten; da würde ich zu suchen anfangen.

Was den Texturspeicher angeht: Seit fast 20 Jahren unterstützt PC-Hardware keine palettierten Texturen mehr (bzw. emuliert sie); für jeden anderen wäre also das K.O.-Kriterium, dass man dann seine eigene Texturfilterung braucht. Die hast du aber eh schon, glaube ich.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Nearest Color in Palette finde

Beitrag von Jonathan »

Das hängt natürlich auch von deiner Palette ab. Wenn du wirklich beliebige Farbeinträge hast, hast du im wesentlichen ein 3D Nearest-Neighbor Problem. Wozu es natürlich Standardalgorithmen gibt:

https://en.wikipedia.org/wiki/Nearest_neighbor_search

Und dann ist natürlich auch die Frage, was du mit 'beste Farbe' meinst. Man kann sich da ja prinzipiell verschiedene Metriken überlegen. Zum Beispiel einfach den euklidischen Abstand im RGB Raum. Oder eine Metrik die Unterschiede in Farb(Hue)-Unterschiede anders gewichtet als Helligkeitsunterschiede. Die dann natürlich auch wieder unterschiedlich teuer auszurechnen sind.

Soviel nur mal als grundsätzliche Überlegung, einen konkreten Tipp für eine besonders geeignete Kombination (auf bestimmte Art eingeschränkte Farbpalette + Farb-Metrik + Look-Up Algorithmus) habe ich jetzt leider nicht.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Nearest Color in Palette finde

Beitrag von Krishty »

Oder möchtest du gar keine nächste Farbe finden, sondern eine komplette optimale Palette erzeugen? Dafür gibt es viele Tools wie z.B. Gimp oder Pngquant, die auch Open Source sind.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Zudomon
Establishment
Beiträge: 2253
Registriert: 25.03.2009, 07:20
Kontaktdaten:

Re: Nearest Color in Palette finde

Beitrag von Zudomon »

Speziell einen Anwendungsfall hatte ich gar nicht im Sinn.
War nur neugierig, wie die das damals wohl gemacht haben.

Ich meinte darauf bezogen, dass die Texturen mit dem Licht multipliziert wurden und die Ergebnisfarbe entsprechend wieder mit der "besten" Farbe aus der Palette von 256 Farben, die auf dem Bildschirm dargestellt werden konnten, gewählt werden musste. Also das musste ja pro Pixel in Echtzeit passieren und ich frage mich halt, wie? Vielleicht eine Art Lookup Table für jede Farbe?
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Nearest Color in Palette finde

Beitrag von Krishty »

seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Antworten