Improve the Image chopping algorithm for sprite import.

[audinowho]

skytemple-files/skytemple_files/graphics/chara_wan/writer.py

Line 1357 in fae2647

def chopImgToPieceLocs(img, transparent):

When a Pokemon sprite wan file is imported, every frame gets chopped up into pieces such that it can be assembled by metaframe data.
The method responsible for this is called chopImgToPieceLocs.
Pieces can be 8x8, 16x8, 8x16, etc.

Currently, the function just returns one piece containing the whole sprite if it's small enough (it usually is), or a collection of pieces that divide the sprite into as few pieces as possible.

This approach does not take advantage of the ability for one piece to be referenced in multiple parts of a sprite. For example: the symmetrical legs of a large Pokemon can be chopped into their own pieces and then collapsed into a single leg texture that is drawn normally for the left side, and then flipped for the right side. This can spell the difference between a sprite being too big to import, or being just small enough to import.

[audinowho]

A potential (naive) method would be as follows:

Iterate through every possible position by which you can put an 8x8 tile on the image, including partial outside positions.
This means (imgWidth + (8 - 1) * 2) * (imgHeight + (8 - 1) * 2) positions.

For each possible position, iterate through the entire thing a second time to see if any other positions have pixels that match the first position.
This means another (imgWidth + (8 - 1) * 2) * (imgHeight + (8 - 1) * 2) positions.

And you will need to compare flipW, flipH, and flipW+H versions of the image too.
So multiply it by 4.

Once all matching images for a given first position have been gathered, store them in a variable collection.
It is possible to optimize out repeat first-images by keeping them in a dictionary that maps position to position-copies.

It may also be possible to apply this to all frames instead of just this frame, but doing so will require refactoring outside of this function call. It will greatly increase optimization but also increase time by a factor of n^2 where n is the number of images.

After this mass iteration, you will have a list of image similarity data.
Pick the combination of image groups that compresses the most pixels, in which overlaps cannot occur. Greedy algorithm or whatever else you can think of.
You can opt to remove overlaps by marking them when choosing images.

A frame collection of 64x64 pixels will require this many comparisons:
(64 + (8 - 1) * 2) * (64 + (8 - 1) * 2) * (64 + (8 - 1) * 2) * (64 + (8 - 1) * 2) * 4
(64 + 14) * (64 + 14) * (64 + 14) * (64 + 14) * 4
87^4*4
37,015,056

That's a lot, but the question is how long does it take in python?

[marius851000]

Hmmm... That could be the reason why I can't seems to reliably predict the value of what I call the "image_alloc_counter" (which, for each metaframe, increase by what seems to be the allocated memory by this metaframe). And I don't check for duplicated piece in a metaframe.

Well... This should be quite complicated to properly implement. I spent quite some time trying to figure out how I could optimise those stuff without relying on brute force -- I tend to underestimate CPU's capacity. I finally went back to a simple "divide the image into 64x64 pixels, then rescale each area to the minimum possible space (by memory allocated), and that's all". No multi-meta-frame optimisation.

But indeed, seeing that most sprite tend to have some identical part with others, finding identical part with all the meta-frames instead of only one might be a good idea (and a source of additional comparaison).

Then there is the problem of how to fill hole that isn't filled.

(also, memory consumption may be something we may want to look for)

[marius851000]

I’ve started to work on this in pmd_wan. For now, I was able to fill this data structure:

#[derive(PartialEq, Debug)]
pub struct FragmentUse {
    pub x: i32,
    pub y: i32,
    pub image_id: u16,
    pub flip: FragmentFlip,
}

/// The output of [`find_fragments_in_images`].
/// The fragment (here) are 8×8 pixel of size.
/// A tile may be Flip on either or both axis (or not at all). Only the smallest of the 4 possible flip is added in this collection (based on the comparaison of the resulting pixels, as Rust compare u8 arrays).
/// The key is the pixels of the fragment (image are stored line by line, from top-left to bottom-right)
/// The key is where they are used. The x or y may be negative.
pub struct FragmentFinderData {
    pub collected: HashMap<[u8; 64], Vec<FragmentUse>>,
}

I now need to find what I should do with this.

[marius851000]

Just an long overdue update: I finished implmementing the algorithm, with a good improvement, but it is still condierably more than 64kiB with Reshiram (around 200 to 300 kiB if I remember correctly).

I’ll try to add this to SkyTemple in the following days.

[Frostbyte0x70]

It has been brought to my attention that this wasn't actually added to SkyTemple (see https://discord.com/channels/710190644152369162/990722852200284180/1242188845592608898), so I'm reopening the issue.