Wieso sind Sprites 16x16 Pixel groß?

[hustbaer]

@rapso
Um ein Sprite zu zeichnen indiziert man normalerweise nicht in ein 2D Array (abgesehen von der Startposition am Bildschirm, die man bei 16x16 Sprites genau so berechnen muss). Man schnappt sich den Zeiger auf's erste Pixel und verschiebt den dann bloss.

Nur wenn das Sprite nicht komplett auf den Bildschirm passt müsste man multiplizieren. Aber auch nur ein paar wenige male pro Sprite, die "pro Pixel" Sachen bestehen wieder bloss aus einfachen Befehlen.

Und spätestens zu Pentium Zeiten konnte man sich ein paar Multiplikationen pro Sprite ganz locker leisten.

BTW: viele DOS Grafik-Engines haben Sprites RLE-komprimiert. Da kann man dann nichtmal mehr mit nem Shift reinadressieren. Schneller war es trotzdem, weil man halt meistens vollständig sichtbare Sprites zeichnet, und die Zeit die man bei den vollständig sichtbaren Sprites mit dem überspringen der durchsichtigen Pixel spart wiegt den Overhead auf den man sich mit teilweise sichtbaren Sprites dabei einhandelt.

----

Warum Sprites früher mal mit 2er Potenzen gemacht wurden ist ja (hoffentlich) jebem klar. Die Frage war aber warum sich das so lange gehalten hat.

[blard]

Das mit den Multiklikationen ist Quatsch. Man kann einen nicht rotierten Sprite mit einer Multiplikation malen, egal wie groß er ist.

const size_t wsx = window.size.x;
const size_t wsy = window.size.y;
const size_t px = sprite.pos.x;
const size_t yp = sprite.pos.y;
const size_t x = sprite.size.x;
const size_t y = sprite.size.y;

uint32_t *out = window.buffer+px+py*wsx;
const size_t line_jump = wsx-x;

uint32_t *in = sprite.buffer;

for(size_t i = 0; i != y; i++)
{
  const uint32_t *line_end = out+x;
  while(out != line_end)
  {
    *in = *out;
    in++;
    out++;
  }
  out += line_jump;
}

(Sollten 5 instructions im inneren Loop sein, wenn ich mich grade nicht irre; dürfte wahrscheinlich noch schneller gehen)

(Könnte jetzt ein off-by-1 Fehler drin sein.)

Wenn der Sprite nur Teilweise auf dem Bildschirm ist, wird es etwas ekelig (lowlevel high performance code halt), geht aber vom Konzept gleich.

Das einzige was 2^n Sprites möglich machen ist das triviale Unrollen des loops. Ob es das Wert ist halte ich für fragwürdig.

Wobei man das heute sowieso alles auf der GPU machen sollte und man sich da ganz gut anstrengen muss um mit seinen Sprite malen ersthaft Zeit zu verbrauchen.

[hellihjb]

Es ist sogar so, dass aktuelle Nvidia-Karten noch alle Non-Power-Of-Two Texturen auf die naechste Zweierpotenz erweitern um die genannten Adressierungsvorteile nutzen zu koennen.

[hustbaer]

blard schrieb:

Wenn der Sprite nur Teilweise auf dem Bildschirm ist, wird es etwas ekelig (lowlevel high performance code halt), geht aber vom Konzept gleich.

Im Prinzip funktioniert das gleich, ja. Ich kenne aber keine Möglichkeit dann mit nur einer Multiplikation pro Sprite auszukommen.
Wenn das Sprite den oberen Bildschirm-Rand schneidet muss man ja irgendwie die nicht sichtbaren Zeilen in der Sprite-Grafik überspringen.

Das bedeutet entweder eine 2. Multiplikation. Oder man muss die Zeilen-Schleife ab Sprite-Zeile 0 laufen lassen, und bei Zeilen ausserhalb des Bildschirms dann die Pixel-Schleife überspringen. Was im Prinzip auch nix anderes ist als eine Multiplikation, nur halt ausgeführt als wiederholte Addition.

[rapso]

hustbaer schrieb:

@rapso
Um ein Sprite zu zeichnen indiziert man normalerweise nicht in ein 2D Array (abgesehen von der Startposition am Bildschirm, die man bei 16x16 Sprites genau so berechnen muss). Man schnappt sich den Zeiger auf's erste Pixel und verschiebt den dann bloss.

das klappt nur im sonderfall dass du pixel zu pixel mappst, das ist eher uninteresant und nicht performance kritisch wenn auch damit das meiste an pixeln gefuellt wird. kritisch wird es wenn du skalierung, rotation und sherung hast. bei shumps wird das bei allen einheiten und schuessen gemacht, nur der background hat die 1:1 optimierung. bei RTS sind es die ganzen units die bewegt werden und wie ich oben sagte, den hintergrund zeichnet man nicht neu (auch wenn das der schnelle teil waere), sondern maskiert die pixel aus pro einheit, zeichnet die einheit und im naechsten frame setzt man die ausmaskierten pixel wieder zurueck. entsprechend ist das zeichnen der einheiten der meiste aufwand.

Nur wenn das Sprite nicht komplett auf den Bildschirm passt müsste man multiplizieren. Aber auch nur ein paar wenige male pro Sprite, die "pro Pixel" Sachen bestehen wieder bloss aus einfachen Befehlen.

nein, du brauchst nicht zu multiplizieren, du addierst einfach pitch pro zeile, du zeichnest diese art von sprites eh zeilenweise, da sie eine andere breite als der bildschirm haben (normalerweise).

Und spätestens zu Pentium Zeiten konnte man sich ein paar Multiplikationen pro Sprite ganz locker leisten.

er sprach von dos spielen, das ist fuer mich alles ab 80x86, nicht nur die letzte generation, auch heute macht man spiele nicht nur fuer GTX680.

BTW: viele DOS Grafik-Engines haben Sprites RLE-komprimiert. Da kann man dann nichtmal mehr mit nem Shift reinadressieren. Schneller war es trotzdem, weil man halt meistens vollständig sichtbare Sprites zeichnet, und die Zeit die man bei den vollständig sichtbaren Sprites mit dem überspringen der durchsichtigen Pixel spart wiegt den Overhead auf den man sich mit teilweise sichtbaren Sprites dabei einhandelt.

RLE war eine moeglichkeit, eine andere war z.B. VQ, beide male hat man durch weniger memory traffic performance gewonnen, VQ erlaubte es jedoch es auch fuer beliebige sprites und sogar texturen zu nutzen.

[hustbaer]

rapso schrieb:

hustbaer schrieb:

@rapso
Um ein Sprite zu zeichnen indiziert man normalerweise nicht in ein 2D Array (abgesehen von der Startposition am Bildschirm, die man bei 16x16 Sprites genau so berechnen muss). Man schnappt sich den Zeiger auf's erste Pixel und verschiebt den dann bloss.

das klappt nur im sonderfall dass du pixel zu pixel mappst, das ist eher uninteresant und nicht performance kritisch wenn auch damit das meiste an pixeln gefuellt wird. kritisch wird es wenn du skalierung, rotation und sherung hast. bei shumps wird das bei allen einheiten und schuessen gemacht, nur der background hat die 1:1 optimierung. (...)

also die klassischen DOS shumps die ich so kenne haben überall 1:1 pixel-mapping verwendet, rotation etc. gab es da nicht. wenn etwas rotiert wurde, dann hatte man dafür einen haufen eigene grafiken. live rotation/skalierung war damals den automaten (bzw. einigen konsolen) vorbehalten, die das mit eigener hardware gemacht haben.

rapso schrieb:

Nur wenn das Sprite nicht komplett auf den Bildschirm passt müsste man multiplizieren. Aber auch nur ein paar wenige male pro Sprite, die "pro Pixel" Sachen bestehen wieder bloss aus einfachen Befehlen.

nein, du brauchst nicht zu multiplizieren, du addierst einfach pitch pro zeile, du zeichnest diese art von sprites eh zeilenweise, da sie eine andere breite als der bildschirm haben (normalerweise).

ach rapso das ist mir auch klar
aber sag mir mal wie du den startpunkt in der sprite grafik ermitteln willst, wenn der opere rand abgeschnitten ist (die oberen N zeilen ausserhalb des bildschirms liegen), und das sprite nicht 2^n breit ist (wovon ich hier ja rede). dafür brauchst du pro sprite eine zusätzliche multiplikation. oder du lässt die zeilen-schleife immer komplett laufen, und überspringst bei zeilen die oberhalb des bildschirmrandes liegen die pixel-schleife -- was im endeffekt auch nix anderes ist als eine multiplikation, nur halt implementiert als eine additions-schleife.

BTW: viele DOS Grafik-Engines haben Sprites RLE-komprimiert. Da kann man dann nichtmal mehr mit nem Shift reinadressieren. Schneller war es trotzdem, weil man halt meistens vollständig sichtbare Sprites zeichnet, und die Zeit die man bei den vollständig sichtbaren Sprites mit dem überspringen der durchsichtigen Pixel spart wiegt den Overhead auf den man sich mit teilweise sichtbaren Sprites dabei einhandelt.

RLE war eine moeglichkeit, eine andere war z.B. VQ, beide male hat man durch weniger memory traffic performance gewonnen, VQ erlaubte es jedoch es auch fuer beliebige sprites und sogar texturen zu nutzen.

du willst mir jetzt erzählen dass man VQ dekomprimierung mit einem 386er oder 486er "live" machen kann, ohne dabei langsamer zu werden als unkomprimiert?
RLE wurde ja nicht nur verwendet um speicherbandbreite zu sparen, sondern damals auch hauptsächlich damit transparente bereiche in den sprites komplett übersprungen werden können (=rechenzeit sparen).

[rapso]

hustbaer schrieb:

rapso schrieb:

hustbaer schrieb:

@rapso
Um ein Sprite zu zeichnen indiziert man normalerweise nicht in ein 2D Array (abgesehen von der Startposition am Bildschirm, die man bei 16x16 Sprites genau so berechnen muss). Man schnappt sich den Zeiger auf's erste Pixel und verschiebt den dann bloss.

das klappt nur im sonderfall dass du pixel zu pixel mappst, das ist eher uninteresant und nicht performance kritisch wenn auch damit das meiste an pixeln gefuellt wird. kritisch wird es wenn du skalierung, rotation und sherung hast. bei shumps wird das bei allen einheiten und schuessen gemacht, nur der background hat die 1:1 optimierung. (...)

also die klassischen DOS shumps die ich so kenne haben überall 1:1 pixel-mapping verwendet, rotation etc. gab es da nicht. wenn etwas rotiert wurde, dann hatte man dafür einen haufen eigene grafiken. live rotation/skalierung war damals den automaten (bzw. einigen konsolen) vorbehalten, die das mit eigener hardware gemacht haben.

Das haengt immer von der zeit ab auf die du referenzierst, die graphik ist natuerlich nicht stehengeblieben. auf 8086 mit 4.77MHz hast du Po2 verwendet, weil indizieren in eine nicht Po2 palette von sprites schon zuviel der Muls waere. spaetere CPUs die das schnell genug konnten, hat man lieber zum rotieren von sprites verwendet als non-Po2 sprites einzubauen, es bringt visuel viel mehr.
Es gab einige shumps die portiert wurden von arcades und consoles und du konntest die rotation oder skalierung nicht einfrieren ohne das gameplay sehr zu aendern.

aber sag mir mal wie du den startpunkt in der sprite grafik ermitteln willst, wenn der opere rand abgeschnitten ist (die oberen N zeilen ausserhalb des bildschirms liegen), und das sprite nicht 2^n breit ist

wir haben fuer Mul und Div (sowie sin,cos, sqrt) LUTs verwendet. damals (<80x386 bzw 80x486) gab es kein cache etc. da war ein 16bit speicher zugriff billiger als jede multiplikation. Falls du dich also entschieden haettest 17x17 zu verwendet, haettest du ein

short Mul17[17]={...};

erstellt bzw haben wir sowas kritisches in assembler geschrieben, also

Mul17 dw 11h

woher soll einer wissen welche grundlagen du weisst und welche nicht?

BTW: viele DOS Grafik-Engines haben Sprites RLE-komprimiert. Da kann man dann nichtmal mehr mit nem Shift reinadressieren. Schneller war es trotzdem, weil man halt meistens vollständig sichtbare Sprites zeichnet, und die Zeit die man bei den vollständig sichtbaren Sprites mit dem überspringen der durchsichtigen Pixel spart wiegt den Overhead auf den man sich mit teilweise sichtbaren Sprites dabei einhandelt.

RLE war eine moeglichkeit, eine andere war z.B. VQ, beide male hat man durch weniger memory traffic performance gewonnen, VQ erlaubte es jedoch es auch fuer beliebige sprites und sogar texturen zu nutzen.

du willst mir jetzt erzählen dass man VQ dekomprimierung mit einem 386er oder 486er "live" machen kann, ohne dabei langsamer zu werden als unkomprimiert?
RLE wurde ja nicht nur verwendet um speicherbandbreite zu sparen, sondern damals auch hauptsächlich damit transparente bereiche in den sprites komplett übersprungen werden können (=rechenzeit sparen).

jap, VQ ist schneller als RAW sprites und texturen, wenn du transformationen hast auf CPUs die cache haben.
z.B. aus den worten einer externen quelle:

http://www.gamasutra.com/view/feature/131499/image_compression_with_vector_.php?page=2 schrieb:

When we put the VQ compression described above in our renderer, we expected to get slightly worse performance but were ready to live with it, because it took about 20MB off our memory footprint. However, profiles showed that rendering has actually gained about 15 to 20 percent performance, probably due to decreased memory traffic.

neben caches auf CPU musstest du auch segmente wechseln und mit der zeit auch sowas wie XMS, EMS etc. arbeiten. die renderreihenfolge war mehr oder weniger vorgegeben, sodass es ebenfalls gut war den speicher kompakt zu halten um moeglichst wenig switching zu haben.

[hustbaer]

Ja, an Lookup-Tables für Multiplikationen hab' ich jetzt nicht gedacht.

auf 8086 mit 4.77MHz hast du Po2 verwendet, weil indizieren in eine nicht Po2 palette von sprites schon zuviel der Muls waere.

Kann man allerdings auch über nen einfachen Lookup-Table machen.

Gerade zu DOS-Zeiten hatte man ja oft keine klassischen Sprite-Sheets, sondern einfach die Sprite-Grafiken irgendwo im Speicher liegen.
Statt einem Shift kann man dann genau so gut die Startadresse von Sprite N aus einem Table laden.

Bei Rotation etc. hast du natürlich recht - das geht mit beliebigen Grössen überhaupt nicht gut, weil man zu oft multiplizieren müsste. Wobei man natürlich auch hier wieder LUTs verwenden könnte - langsamer als mit power-of-two Grafiken wird das aber vermutlich auch sein.

[raps]

hustbaer schrieb:

Ja, an Lookup-Tables für Multiplikationen hab' ich jetzt nicht gedacht.

auf 8086 mit 4.77MHz hast du Po2 verwendet, weil indizieren in eine nicht Po2 palette von sprites schon zuviel der Muls waere.

Kann man allerdings auch über nen einfachen Lookup-Table machen.

problem ist nur dass deine LUT zur compile zeit nicht bekannt ist, muestest du also im 'level' ablegen. haettest also lookup zum lookup, dann lookup, dann erst zugriff auf das asset. waere in alten zeiten schon ein wenig aufwendig (zumal es vermutlich nicht mit 16bit getan waere, also 32bit reads (seg:offset) und das mehrmals.

Gerade zu DOS-Zeiten hatte man ja oft keine klassischen Sprite-Sheets, sondern einfach die Sprite-Grafiken irgendwo im Speicher liegen.
Statt einem Shift kann man dann genau so gut die Startadresse von Sprite N aus einem Table laden.

je nachdem wieviel cycles du dafuer verschwenden moechtest. irgendwie dachte man da frueher anders drueber. ich hatte neben jeder meiner c zeilen die anzahl der zyklen stehen und alles was ein wenig zeit brauchte, von simplen clear, ueber memcpy etc. wurde dann eh frueher oder spaeter in assembler gewandelt. pro sprite 10cycles oder so verschwenden haette einem programmiererherz wehgetan ;), heute schert sich die welt nichtmal bei pixelshadern so drum wie damals beim cpu code.

Bei Rotation etc. hast du natürlich recht - das geht mit beliebigen Grössen überhaupt nicht gut, weil man zu oft multiplizieren müsste. Wobei man natürlich auch hier wieder LUTs verwenden könnte - langsamer als mit power-of-two Grafiken wird das aber vermutlich auch sein.

fuer performance haette man damals alles getan, das ist heute irgendwie schwer rational zu erklaeren.

[hustbaer]

raps schrieb:

hustbaer schrieb:

Ja, an Lookup-Tables für Multiplikationen hab' ich jetzt nicht gedacht.

auf 8086 mit 4.77MHz hast du Po2 verwendet, weil indizieren in eine nicht Po2 palette von sprites schon zuviel der Muls waere.

Kann man allerdings auch über nen einfachen Lookup-Table machen.

problem ist nur dass deine LUT zur compile zeit nicht bekannt ist, muestest du also im 'level' ablegen. haettest also lookup zum lookup, dann lookup, dann erst zugriff auf das asset. waere in alten zeiten schon ein wenig aufwendig (zumal es vermutlich nicht mit 16bit getan waere, also 32bit reads (seg:offset) und das mehrmals.

verstehe ich grad nicht was du meinst. du kannst in jedem fall den shift durch einen einzigen lookup ersetzen. wenn die frame-anzahl bekannt ist, dann kann der table auch auf einer konstanten adresse sitzen, so dass kein load nötig ist um die table-startadresse zu laden. ob die werte bereits vom compiler/linker beim bauen reingeschrieben werden, oder erst beim laden des levels, spielt dabei ja keine rolle.
u.u. kann man sich sogar die addition der "base address" sparen - wenn man flat-mode verwendet bzw. sowieso alles in 64KB platz hat kann man ja fertige adressen in den table reinschreiben.

klar, es wäre etwas mehr aufwand, und so lange kein guter grund dafür spricht wird man es dann nicht machen. rein von der geschwindigkeit her sehe ich da aber kein echtes problem.

ich hatte neben jeder meiner c zeilen die anzahl der zyklen stehen und alles was ein wenig zeit brauchte, von simplen clear, ueber memcpy etc. wurde dann eh frueher oder spaeter in assembler gewandelt. pro sprite 10cycles oder so verschwenden haette einem programmiererherz wehgetan ;), heute schert sich die welt nichtmal bei pixelshadern so drum wie damals beim cpu code.

da hast du sicher auch recht. ich glaube nur dass damals z.T. auch sachen optimiert wurden, die schon damals egal waren. weil es damals einfach OK war dinge bis zum abwinken zu optimieren, und optimieren macht spass, also optimiert man einfach alles - egal ob es sinn macht oder nicht.
10 zyklen pro sprite sparen, wenn das zeichnen des sprites insgesamt 50-100 zyklen braucht ist ja noch OK. 10 zyklen sparen wenn das zeichnen >= 1000 zyklen braucht ist mMn. sinnfrei. bzw. war es auch damals schon.

Bei Rotation etc. hast du natürlich recht - das geht mit beliebigen Grössen überhaupt nicht gut, weil man zu oft multiplizieren müsste. Wobei man natürlich auch hier wieder LUTs verwenden könnte - langsamer als mit power-of-two Grafiken wird das aber vermutlich auch sein.

fuer performance haette man damals alles getan, das ist heute irgendwie schwer rational zu erklaeren.

ja... ich hab die zeit ja noch am rande miterlebt. ich hab' zwar damals keinen produktiven code geschrieben, aber ich hab' am amgia 500 zu programmieren angefangen (erst assembler, später dann C). waren zwar alles nur hobby-projekte, und kaum etwas ist wirklich fertig geworden. aber was man da alles machen konnte (und auch gemacht hat) um performance zu schinden ist mir zumindest nicht ganz fremd.