Algorithm for cutting into sprites
Moderator: BigEvilCorporation
Algorithm for cutting into sprites
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.
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.
-
- Very interested
- Posts: 3131
- Joined: Thu Nov 30, 2006 9:46 pm
- Location: France - Sevres
- Contact:
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 :-/
-
- Very interested
- Posts: 710
- Joined: Sat Feb 18, 2012 2:44 am
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.
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.
-
- Very interested
- Posts: 710
- Joined: Sat Feb 18, 2012 2:44 am
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.
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.
I don't see any optimization step.djcouchycouch wrote:In my Pingouin Bleu project, the gale2c (Graphics Gale to .c) tool has a similar 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)
-
- Very interested
- Posts: 710
- Joined: Sat Feb 18, 2012 2:44 am
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.r57shell wrote:I don't see any optimization step.djcouchycouch wrote:In my Pingouin Bleu project, the gale2c (Graphics Gale to .c) tool has a similar optimization step.
This should be the correct one.
https://dl.dropboxusercontent.com/u/17303735/gale2c.cpp
Thanks for pointing that out.
I've left a copy here https://dl.dropboxusercontent.com/u/173 ... lefile.dllAlso, gale dll link broken So I can't test. (Can't run gale2c)
but SHHHH don't tell anyone
-
- Very interested
- Posts: 710
- Joined: Sat Feb 18, 2012 2:44 am
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. (*)KanedaFr wrote: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.
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
Thanks for answers
and same image with 2nd algorithm (here, it performs worse) :
I didn't understand completely your code, but it starts like my 2nd algorithm.
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.
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).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.
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) :Didn't understand any of algorythms noted above Confused
Also check this threed: viewtopic.php?t=1371
and same image with 2nd algorithm (here, it performs worse) :
I didn't understand completely your code, but it starts like my 2nd algorithm.
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.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 ?
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.
i don't use Stef one eitherMy 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 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.
-
- Very interested
- Posts: 710
- Joined: Sat Feb 18, 2012 2:44 am
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.KanedaFr wrote: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.The only problem ? Too much code per sprite (anim, move, collide, behavior) which slow down everything
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)
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