Algorithm for cutting into sprites

[tryphon]

I'm confronted to the problem of having an arbitrary large image, and wanting to cut it into sprites, i.e covering it with rects whose dims go from 8x8 to 32x32, and whose position isn't necessarily aligned on multiples of 8.

Seems to me the problem is complex : trying all possible cut is too long (considering I have some hundredth of images), and I don't see a simple algorithm that could give the best result, best being the one that minimizes the size in VRAM (so 32*nb_of_patterns + 8*nb_of_sprites).

I wrote two algorithms :

1) slice picture horizontally (find all the way to write height_of_picture as sums of 8, 16, 24, 32) and in each of these slices, find the minimal surrounding rectangle (can be improved : generate more rects per slices to avoid blank patterns) ; this algo gives weird cut, but has the side-effect of avoiding too much sprites on the same row (I believe there is a hardware limit to this)

2) Cut the image in 8x8 contiguous blocks, then find the biggest groupment of blocks, store it, and recursively regroup until there's no more groupments. This is done 64 times, by shifting the initial grid by 0 to 7 pixels horizontally and vertically.

Both algo give correct results (similar but different, algo 1 is better, sometimes worse), but seem pretty naive to me.

If you have another idea, or know about this problem, I'd be interested.

[Stef]

Actually that is definitely a complex problem. I meet it when i developed rescomp to but big sprite in several smaller sprites. I did it the very naive and simplest method but it would worth having a good algorithm to optimize the number of sprite to use. Right now i did not yet took the time to think about a good algorithm for that :-/

[djcouchycouch]

In my Pingouin Bleu project, the gale2c (Graphics Gale to .c) tool has a similar optimization step.

You can find it as part of the project here https://dl.dropboxusercontent.com/u/173 ... .1.0.0.zip in tools/gale2c

From what I can remember, it first cuts the sprite into rows of 32 pixels high, then finds the smallest sprites that fit for that row. It's not the most optimized thing in the world, but it was straightforward to do and still removes a lot of empty space.

I thought it had a duplicate and mirrored sprite step, but looking at the code it doesn't look like it.

You'll need the graphics gale dll for it to run.

[KanedaFr]

I think i use the same method as Stef on GenRes...
Get the sprites count with 32 then 24 then 16 then 8, take the smaller result
for horizontal and vertical, so I could define a 16x24 if needed

[r57shell]

Didn't understand any of algorythms noted above

Also check this threed: viewtopic.php?t=1371

[djcouchycouch]

Yeah, if you look at those two drawings and how they were split, the method I mimicked is the mortal kombat one.

[KanedaFr]

while I understood the MK method limits the number of sprites needed, isn't a pain to handle ?
I mean, every frame use differents sprites at different position at differents size ?!
to win what ? use 40 of 80 sprites available ?
more code vs more sprite ?

It's only to understand the pro and con of this method, of course.

[r57shell]

In my Pingouin Bleu project, the gale2c (Graphics Gale to .c) tool has a similar optimization step.

I don't see any optimization step.
It should be in function OutputSprites(int frameNumber)
but it just split incoming bitmap in rects of 4x4 tiles.
And output all of them! Only one check is inside: if image width not divisable by 32 or image hieght not divisable by 32, then it outputs smaller one reminding sprites.
Also it looks like it will output bad result if image width/height not divisable by 8.

Don't see any optimisations there done.
It's so obvious because it never check pixel for transparency.

Also, gale dll link broken So I can't test. (Can't run gale2c)

[djcouchycouch]

In my Pingouin Bleu project, the gale2c (Graphics Gale to .c) tool has a similar optimization step.

I don't see any optimization step.

You're right! The version I have is different than the one I released. I never noticed! Very odd considering I used it extensively in Pingouin Bleu to cut up the bigger enemies and the background tree.

This should be the correct one.

https://dl.dropboxusercontent.com/u/17303735/gale2c.cpp

Thanks for pointing that out.

Also, gale dll link broken So I can't test. (Can't run gale2c)

I've left a copy here https://dl.dropboxusercontent.com/u/173 ... lefile.dll
but SHHHH don't tell anyone

[djcouchycouch]

while I understood the MK method limits the number of sprites needed, isn't a pain to handle ?
I mean, every frame use differents sprites at different position at differents size ?!
to win what ? use 40 of 80 sprites available ?
more code vs more sprite ?

It's only to understand the pro and con of this method, of course.

Optimizing sprite use is more involved because it does indeed mean that for every frame, it's a list of sprite sizes and positions. But it also means that you're reducing the number of active sprites for much less flicker (useful for lots of objects or large objects, PBleu had both) and that there's less empty space in the sprites themselves you can fit more in VRAM. In the PBleu case, I fit everything into VRAM and didn't need to swap anything, even at the boss. (*)

So yeah, it's a trade off. It's "slower", but as you can see in PBleu, I managed to get it fast enough to get a decent amount of stuff going on screen.




(*) I know, I know, the boss wasn't that impressive

[tryphon]

Thanks for answers

From what I can remember, it first cuts the sprite into rows of 32 pixels high, then finds the smallest sprites that fit for that row.

The 1st algorithm does that, and even a little better since it tries different height and keeps the best result (and it could be enhanced, by cutting a row by more than a sprite if there's a large empty part between 2 blocks, like the space between feet of a char).

Didn't understand any of algorythms noted above Confused

Also check this threed: viewtopic.php?t=1371

Sorry, tried to be clear. To illustrate, here's output from 1st algorithm (some rects are partially visible because image output is restriced to effective pixels) :



and same image with 2nd algorithm (here, it performs worse) :



I didn't understand completely your code, but it starts like my 2nd algorithm.

while I understood the MK method limits the number of sprites needed, isn't a pain to handle ?
I mean, every frame use differents sprites at different position at differents size ?!
to win what ? use 40 of 80 sprites available ?
more code vs more sprite ?

My sprite engine (I don't use Stef's) uses 32 tiles per frames of an animation. I hope having 5 or 6 "sprites" simultaneously, so more tiles would cause much less VRAM.

The problem raised when some frames were cut in 33 tiles by my 1st algorithm. I tried to cut these frames by hand, and realized it was really difficult. So I wrote 2nd algorithm. It uses only 31 tiles for the same frame, but on others it performed worse than 1st, hence my question for an optimal answer.

[KanedaFr]

My sprite engine (I don't use Stef's) uses 32 tiles per frames of an animation. I hope having 5 or 6 "sprites" simultaneously, so more tiles would cause much less VRAM.

i don't use Stef one either
I can't use more than 10 sprites using 32 tiles per frame and I still have a lot of VRAM.
The only problem ? Too much code per sprite (anim, move, collide, behavior) which slow down everything
It's not a memory issue, it's a "tick count" issue.
It's why I ask why you need a "complex" way to handle multi-sprites.
If every sprite use the same number of tiles every frame, you could define its address on vram and DMA the frame tiles
if you change every frame, you have to compute everything (time), define the new address based on previous sprite (time), copy/DMA to VRAM, redefine sprites (time)

I just want to be sure you're aware of that point.
It's a balance between space in VRAM and time.
In my case, time is the issue, not VRAM.
And I suspect you'll meet the same issue soon when you'll add sprite behavior code

Perhaps MK used the algo to limit the size of the rom.
it's then a technical (too much rom needed and no SSF2 mapper-like available) or money (large rom was expensive) issue, not a VRAM issue.

[djcouchycouch]

The only problem ? Too much code per sprite (anim, move, collide, behavior) which slow down everything

You don't need to compute collisions for every sprite, just every object. One object, made up of several sprites, would have just one bounding box.

If every sprite use the same number of tiles every frame, you could define its address on vram and DMA the frame tiles
if you change every frame, you have to compute everything (time), define the new address based on previous sprite (time), copy/DMA to VRAM, redefine sprites
(time)

I've had animations that use different number of tiles every frame. And I had too many objects that I couldn't DMA all of them in time even if I wanted to.

But I guess it's a difference in strategy: I preload VRAM with as much stuff as possible, trying to fit everything. If multiple objects use the same animation, they point to the same VRAM address + a frame offset per object. Only the main player object gets its frames DMA into VRAM because it has many more frames.

I precompute everything as much as possible so that there's very little decision making to do. Every animation has an array of frames, with every frame containing an array of sprites. Every sprite contains a position offset relative to the origin of the animation and a relative offset into VRAM. When drawing, you just go through the list of frames, then the list of sprites. It's definitely slower than assuming everything has the same size, but the increased flexibility is a pretty good trade off. And as you can see from Pingouin Bleu, its performance is pretty acceptable. (multi-part player object, lots of bullets, lots of enemies, multiple background planes, etc)

The whole reason I had to explore building my sprites this way is because of the giant tree in the background in PBleu. Since it's basically an standing triangle in a rectangle, it had too many empty sprites and caused lots of flickering. I had to develop a way to trim it down a little. The rest came as a bonus