ugrás a tartalomhoz

Sprite készítő algoritmusok

inf3rno · 2011. Nov. 9. (Sze), 22.34
Elég sűrűn előfordul egy weblapnál, hogy a sok képfájl miatt nyitott sok HTTP kapcsolat lelassítja az oldal betöltődését. Ezen sprite-okkal szoktak segíteni. Ezt úgy kell elképzelni, hogy fogunk egy nagy (jobb szó híján) vásznat, amire feltesszük az összes kis képet, amit az adott oldal be akar tölteni. Ezek után lementjük ezt a vásznat egy képfájlba, az oldal pedig egyetlen HTTP kapcsolattal ezt a fájlt szedi le, és darabolja fel ismét a megadott koordináták szerint css segítségével. A sprite készítést természetesen érdemes automatizálni. Én is ebbe kezdtem bele.

A sprite-ok készítésénél a lényegi kérdés, hogy hogyan helyezzük el egymás mellé a kis képeinket. A matematika nyelvére lefordítva ez annyit tesz, hogy vannak különböző méretű téglalapjaink, és ezeket szeretnénk elrendezni egymás mellett úgy, hogy az eredmény a lehető legközelebb legyen egy téglalaphoz. Tegyük fel, hogy mondjuk nem téglalap alakban rendezzük el a képeinket, hanem mondjuk kör alakban. Az eredmény kicsit kisarkítva, vagy inkább kerekítve valami ilyesmi lesz:



Ez egy 100x100-as kép, szóval az átmérő az 100px. Tehát a kör által a vásznon foglalt terület: d^2*pi/4, ami 7854 px^2. A teljes vászon területe viszont 10 000 px^2. Szóval rengeteg kihasználatlan terület található a sprite-ban, amiben átküldenénk a kör alakban összerendezett képeinket. Emiatt kell, hogy a képek összerendezésével kapott alakzat téglalapra hasonlítson, mert ugye minél jobban hasonlít egy téglalapra, annál kisebb rajta a kihasználatlan terület, és annál kevesebb felesleges adatot küldünk át a sprite-unkkal.

Nyilván nem rakhatunk össze minden egyes sprite-ot kézzel, mert az rengeteg időt elvinne, ezért valamilyen csomagoló algoritmust kell használnunk, ami elvégzi helyettünk a munkát.

Milyen adatokat használhat egy ilyen algoritmus?

A képek, a képcsoportok és a vászon tulajdonságai:
  • szélesség: w {px}
  • magasság: h {px}
  • átmérő: d=sqrt(w^2+h^2) {px}
  • képarány: r=w/h {}
  • terület: A=w*h {px^2}

Vannak egyszer a téglalapok tulajdonságai, amelyeket ugye a képekre és a vászonra is meghatározhatunk. A szélesség, a magasság és az átmérő elég egyértelmű, ahogy a terület is.

A képarány, ami egy kicsi többletinformációval bír, hiszen abból meg lehet mondani a téglalap alakját. Ha r<1 (w<h), akkor álló téglalapról, ha r>1, akkor fekvő téglalapról, ha r=1, akkor pedig négyzetről van szó. További érdekesség ezzel kapcsolatban, hogyha olyan csoportokat alkotunk a képekből, amelyek szintén téglalap alakúak, akkor ezekre ugyanúgy használhatóak a fenti tulajdonságok. Így mondjuk négy egyforma nagyságú négyzetet lehet úgy kombinálni, hogy a csoport fekvő vagy álló téglalapot, de akár négyzetet is alkothat.

A csoportok és a vászon tulajdonságai
  • hézag: g=A(csoport)-sum(A(képek)) {px^2}

A hézag a csoport területe és a benne található képek területe közötti különbség, amit százalékban is megadhatjuk a képek összterületéhez viszonyítva. A vászon pedig az a csoport, aminek a minimális hézag méretét keressük. Ezt nem biztos, hogy úgy érjük el, hogy az egyes csoportok hézagmérete a lehető legkisebb. Nagyon sokat számít az, hogy ezeket a csoportokat hogyan tudjuk összeilleszteni. Ez körülbelül ugyanaz, mint amit a tetrisznél is csináltunk.

A legegyszerűbb algoritmus

Csoportokban gondolkodó algoritmust elég nehéz leprogramozni, vannak azonban ennél jóval egyszerűbb megoldások is.

Szinte mindig onnan indulunk, hogy csoportosítjuk az építőelemeinket. Ezt megtehetjük a fenti tulajdonságok szerint.

A legegyszerűbb algoritmus az, ha egymás mellé vagy alá rakjuk a képeinket magasság vagy szélesség szerint sorba rendezve.



Ennél már kicsit bonyolultabb az, ha fogjuk a fenti ábrán látható képeket, és elkezdjük egymásra pakolni úgy, hogy fokozatosan csökkentjük a szélességet, ahogy az az alábbi ábrákon látható.











Ilyen módon fokozatosan csökken a hézag területe egészen az összes kép területének 36%-áig. Ennél jelen esetben kézzel sem tudnánk jobb eredményt kihozni.

Vannak azonban olyan helyzetek, amikor ez az algoritmus nem a legjobb eredményt adja:









Mint látható, itt a normál algoritmussal nem tudunk elérni 17% hézagnál jobb eredményt, azonban kézzel könnyedén ki lehet rakni a hézagmentes változatot.



Az olyan algoritmusok, amelyek erre képesek nyilván már bonyolultabbak. Ha érdekel titeket a téma szívesen várom az ötleteket, hogy mi alapján lehetne ilyen algoritmust fejleszteni, illetve ha találtok neten ilyen algoritmusokat, akkor azok szintén gazdagítanák ennek a leírásnak az értékét.

Amit még lehet csinálni az ötletelésen kívül, hogy kézzel kirakunk egy csomó sprite-ot, lementjük a koordinátákat, illetve a csoportok jellemzőit. Ezek után meg lehet próbálni data mininggal kinyerni az adatokból, hogy az egyes esetekben milyen tulajdonságú csoportok a leghatásosabbak, majd az ebből készült adatbázis felhasználható a sprite-ok készítésére, esetleg új algoritmusok gyártására.
 
1

Ismétlődő grafika

Török Gábor · 2011. Nov. 9. (Sze), 22.36
Ha jól értem, a te esetedben a sprite-ra nem kerülnek olyan grafikai elemek, amelyek ismétlődőek.
5

Nem teljesen értem a kérdést.

inf3rno · 2011. Nov. 10. (Cs), 10.01
Nem teljesen értem a kérdést. Ha ismétlődik egy kép, akkor úgy logikus, hogy csak egy helyre kerüljön be a sprite-ba. Ugye itt két probléma szokott előfordulni, az egyik, hogy sok kicsi ismétlődő kép van, és sokáig tart betölteni őket, a másik meg, hogy szimplán csak sok kép van. A sprite a másodikban is nagyon sokkal tud javítani a betöltési időn. Talán még az is előnye, hogy egységesen szabályozható benne a képek tömörítésének a mértéke. Ami meg hátrány, hogy elég sok erőforrást igényel 1-1 sprite előállítása, szóval mindenképp kesselni kell őket.
7

background-repeat

tiku I tikaszvince · 2011. Nov. 10. (Cs), 10.13
Szerintem az ismétlődő kép kitétel az ismételt háttérképekre vonatkozik.

A tapasztalatom szerint a hagyományos háttérnek használt (background-repeat: repeat;) képeket egyszerűen nem lehet sprite-ra tenni. Különösen nem, ha az a doboz, aminek beállítod nem rendelkezik fix dimenziókkal.
8

Hmm ezzel még nem

inf3rno · 2011. Nov. 10. (Cs), 10.27
Hmm ezzel még nem találkoztam. http://www.phpied.com/background-repeat-and-css-sprites/ itt mintha megoldották volna.
14

tar, vagy background-crop...

Arnold Layne · 2011. Nov. 10. (Cs), 18.27
A tapasztalatom szerint a hagyományos háttérnek használt (background-repeat: repeat;) képeket egyszerűen nem lehet sprite-ra tenni.

Szerintem se. Az igazi megoldás az valami olyan lenne, hogy pl tar fájlba összepakolni a képeket, ekkor csak a képekre hivatkozás lesz szokatlan. A másik ami eszembejutott, hogy oké, vágjunk ki egy kis darabot a színátmenetből, pont ami kell, aztán találjuk ki a background-crop (mivel a crop már foglalt) tulajdonságot(?), majd az ezzel kivágott képpel már azt csinálunk, amit nem szégyellünk. A probléma ezzel csak az, hogy szerintem igen ronda lenne a css, szóval részemről maradnék az előző változatnál, de ha jól emlékszem a resource packages pont ezt csinálja.
15

Lehet

Poetro · 2011. Nov. 10. (Cs), 19.21
Kell a vízszintesen és a függőlegesen ismétlődő képeknek egy egy külön kép. Természetesen nem lehet minden esetben használni, de azért nagyon sokszor. Képeket természetesen bele lehet rakni a CSS fájlba data URI használatával, így kvázi egybe tudsz csomagolni sok képet. Természetesen valamennyit fog nőni a képek méretek (kb. másfél-szeresére.)
2

Optimális algoritmus

ntamas · 2011. Nov. 10. (Cs), 00.13
A probléma (ha jól tudom) NP-teljes, ezért nem várható, hogy hatékony és optimális megoldást lehet rá találni. Egy lehetséges branch & bound alapú optimális megoldást az alábbi cikk tartalmaz:

Optimal rectangle packing: Initial results

Ez pedig egy C# implementáció.

Mivel azonban a legtöbb esetben a sprite fennmaradó részeit egyszerűen kitölthetjük feketével, és ez simán tömöríthető PNG vagy JPG formátumban a fájlméret szignifikáns növekedése nélkül, ezért valószínűleg nem éri meg a bonyolultabb algoritmusok implementálása, hacsak nem könnyű téli esti ujjgyakorlat gyanánt ;)
3

Memória

Török Gábor · 2011. Nov. 10. (Cs), 08.52
A képek memóriában tárolásakor viszont érdekes lehet a sok "fehér folt", nem?
6

Ez olyan vita, amit talán

inf3rno · 2011. Nov. 10. (Cs), 10.03
Ez olyan vita, amit talán teszteléssel lenne a legcélszerűbb eldönteni.

Egyébként az algoritmusok kapcsán még eszembe jutott, hogy az ideális elrendezéseket megvizsgálom statisztikai módszerekkel, de a data mining még nem megy annyira, mint szeretném... :D Nem tudom más hogyan csinálja, de nekem egy nap fele annyi dologra sem elég, mint szeretném... :-)
9

De.

ntamas · 2011. Nov. 10. (Cs), 10.35
Igen, ez teljesen igaz. Én hallgatólagosan azzal a feltételezéssel éltem, hogy az elsődleges cél az, hogy spóroljunk a sávszélességgel, nem az, hogy a lokális memóriafogyasztással spóroljunk.
16

Szerintem az elsődleges cél

inf3rno · 2011. Nov. 10. (Cs), 20.03
Szerintem az elsődleges cél az, hogy gyorsan betöltődjön az oldal. A sávszélesség is számít ebben meg a memória fogyasztás is. De szerintem a memóriának nincs akkora súlya, a sávszélesség meg tömörítés esetében elhanyagolható.
19

Mobil eszközökön nagyon is

Hidvégi Gábor · 2011. Nov. 11. (P), 08.31
Mobil eszközökön nagyon is van súlya a memóriahasználatnak.
20

Ohh, hát erre nem gondoltam

inf3rno · 2011. Nov. 11. (P), 10.52
Ohh, hát erre nem gondoltam :-)
21

Sokáig én sem, de az idei web

Hidvégi Gábor · 2011. Nov. 11. (P), 12.17
Sokáig én sem, de az idei web konferencia felhasználói élmény kategóriájának első három előadása rávilágított, hogy a felhasználói mezőny szélesedik, most nem nem csak asztali számítógépeken, hanem korlátozott használhatóságú netbook-okon, táblákon, valamint drága és lassú mobilinternetes eszközökön is nézik oldalainkat, és figyelembe kell venni ezeket a tényezőket is, ha versenyképesek szeretnénk maradni.
4

Hát én is elgondolkodtam,

inf3rno · 2011. Nov. 10. (Cs), 09.55
Hát én is elgondolkodtam, hogy megérné e vagy sem, de mivel tömörített képekről van szó, ezért annyira talán nem.

Ezt a problémát egyébként nevezik bin packing problem-nek és pallet loading problem-nek is, és "combinatorial NP-hard"-nak írják wikipedián. Egyébként elég sok algoritmus van a témában, találtam én is egy párat, de még nem jutottam el odáig, hogy elolvassam a cikkeket, amiket róluk írtak.
10

Ikonok...

TeeCee · 2011. Nov. 10. (Cs), 11.17
Sziasztok,

A problémával én is találkoztam, egy webes alkalmazás kapcsán. Mivel egy napi 8 órában használt rendszerről van szó az elvárások a kinézettel kapcsolatban kb. 3 szóval leírhatók: 'handy', 'dizájnos', de ugyanakkor 'átlátható'. Namármost a gyakorlatban ez azt jelenti, hogy egyértelmű ikonok mindenhova... Sokáig kevés volt és IMG-ben, aztán persze CSS-be kerültek, de egyre több lett belőlük, ezért automatizálni kellett.

Én így csináltam:
- Az ikonok vízszintesen egymásmellé kerülnek. (egyszerűség a generálásban)
- Külön fájl készül a különböző ikonoknak: 16-22-32-48-64 (16-22 a leginkább használt, a 32-48 a még nem lett kigyomlálva teljesen, 64px-es a fejlécbe a modul ikonja). Azért jó, mert jelentős eltérés van az ikonok számában, illetve az egymásmellé pakolt méretben. (Vagyis a szélesség x darabszám eltér nagyon)
- Az ikonok megtalálása automatikusan történik a smink-könyvtárakból. Ahány smink, annyi összepakolt CSS-fájl készül, az 'alaprendszer' mindegyikben benne van, plussz még a modulok.
- Az számít ikonnak, amelyik PNG-fájl ÉS négyzet alakú. (Így az esetleges új méretet is automatikusan feldolgozza - bár ha lennének nem négyzet alakú képek, akkor lehetne méretlistából dolgoznia.)
- Az CSS-class elnevezése automatikus: [MODUL]_[FÁJLNÉV]_[MÉRET].

Igazából egy dolgot hiányolok még: sok helyen ugyanazt az ikont használjuk, ezzel a generáláskor most nem foglalkozom, viszont ha ezt is nézné a scriptecske, akkor még -30% lenne kicsi ikonok száma, mérete és ezzel együtt a CSS is :D

Azzal sosem foglalkoztam, hogy esetleg egyetlen fájlba bepakolni az összes ikont, vagy ezeket elrendezni, hogy nem széles, hanem lehetőleg minél inkább négyzet alakú téglalap legyen (darabszámból és az ismert, számítható képméretből ez könyen megoldható). Lenne ez utóbbinak valami előnye? Max. könnyebben átlátható, de méretben nem hiszem, hogy nyernék rajta annyit, amennyit a bele ölt idővel elszúrok...

Várom az észrevételeket :)
11

Másik probléma...

Jozso · 2011. Nov. 10. (Cs), 13.52
A CSS background-repeat már elhangzott, viszont ezen felül is van egy elég nagy probléma az automatikus sprite építéssel.

Egyszer elrendezi optimálisan és ezt használod az alkalmazásban.
Eddig minden ok.

Aztán jön egy új elem, ami mondjuk közepes méretű és berendezi a sprite közepébe.
Esetleg kompletten újrarendezi az algoritmus az egészet.
A régi CSS-sel az oldal szinte garantáltan széthullik vizuálisan.

Szvsz célszerű a sprite generáláshoz kapásból hozzávenni a CSS generálást is, ha az ember ilyenben gondolkozik.
12

timestamp

TeeCee · 2011. Nov. 10. (Cs), 14.16
Annyit kell tenni, hogy a CSS-behúzásakor a generált CSS dátumát hozzáírod és a böngésző újratölti...
src="generatedStyle?20111110140012"

Eddig nem volt vele problémám.
Ugyanez működik az aggregált JS-fájlokra.
(Legalábbis eddig ezt használtam és nem volt vele gond :D )

Ha 'normális' rendszered van, ezt két sor beleírni. Szerintem amúgy a CSS-generálást alapból belevettük, hiszen nincs értelme a képeket átpakolászni, aztán kézzel próbálkozni, mi hova került :)
13

Mindenképpen

Poetro · 2011. Nov. 10. (Cs), 14.16
A CSS generálása mindenképpen része a folyamatnak, mivel az algoritmus minden adatot ismer, azaz hogy melyik kép hol van, így egyszerű kiírni a background-position adatokat.
17

Persze, ez egyértelmű, én is

inf3rno · 2011. Nov. 10. (Cs), 20.05
Persze, ez egyértelmű, én is így csinálom, hogy sprite+css...
18

Kedvenc spritegenerátorom

jf · 2011. Nov. 10. (Cs), 23.50
Ez szerintem érdekelni fog. ;)
http://spritegenerator.codeplex.com/

Kár hogy nem fejlesztik tovább, mert még így is nagyságrendekkel jobb, mint bármelyik sprite készítő alkalmazéás.