Tile reduction

Discussion of hardware and software development for Super NES and Super Famicom. See the SNESdev wiki for more information.

Moderator: Moderators

Forum rules
  • For making cartridges of your Super NES games, see Reproduction.
Post Reply
giles
Posts: 10
Joined: Sun Jan 13, 2013 10:58 am

Tile reduction

Post by giles »

Are there any programs that do tile reduction of similar tiles? Even better if one could set a threshold for how aggressive the matching is.
djcouchycouch
Posts: 97
Joined: Sat May 28, 2011 10:30 am

Re: Tile reduction

Post by djcouchycouch »

I asked a similar question a while ago, so this thread might be useful to you.

viewtopic.php?f=21&t=9586
giles
Posts: 10
Joined: Sun Jan 13, 2013 10:58 am

Re: Tile reduction

Post by giles »

Yes, I saw that, and I use grit to remove duplicate tiles and for compression.

As a way to save further space I looked for tiles that were similar and removed them by hand. It didn't seem like it was taking a long time but of course a couple of hours went by.

This freed up a lot of space in the rom (21AC2) and the images look just as good as they did before.

This seems like something somebody would have done already. If not I'll add it to my todo list.
Shiru
Posts: 1161
Joined: Sat Jan 23, 2010 11:41 pm

Re: Tile reduction

Post by Shiru »

Sixpack?

I personally use my own custom tools, either writing them from scratch for a particular case, or modyfing old ones if they are close enough to requirements. Writing a tool from scratch is definitely faster than sorting out tiles manually.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Tile reduction

Post by tepples »

Define "similar tiles" and I'll get to work.
User avatar
mikejmoffitt
Posts: 1353
Joined: Sun May 27, 2012 8:43 pm

Re: Tile reduction

Post by mikejmoffitt »

Tepples, I have thought of a simple architecture for such a program:

Code: Select all

prompt user for difference tolerance, n (how many pixels must be mis-matched in an 8x8 tile to be considered different)
create new tile buffer for export
load tiles
for tile in tiles:
    store tile reference for comparison
    for tile in tiles:
        check for differences against stored tile reference ( in complete pixels )
        if there are equal to n or less differences:
            copy user's choice of one or the other to the new tile buffer
        else:
            copy to new buffer (this will also handle the comparison of a tile to itself without issues)
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Tile reduction

Post by tepples »

It's a bit harder when you consider that a similarity metric based on counting equal pixels isn't transitive. Consider the case where both A and B are similar to a later tile C, but A isn't similar to B. And even the algorithm you suggest is O(n^2), meaning it might work for a single 256-tile scene at a time but I'm not sure how tractable it stays for the 16384-tile banks of, say, MMC5 ExGrafix.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Tile reduction

Post by tokumaru »

tepples wrote:And even the algorithm you suggest is O(n^2), meaning it might work for a single 256-tile scene at a time but I'm not sure how tractable it stays for the 16384-tile banks of, say, MMC5 ExGrafix.
Well, this is the SNESdev forum, so he probably expects to use this on chunks larger than 256 tiles.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Tile reduction

Post by tepples »

On the one hand, that's a good thing, as 1024 tiles (Super NES limit per plane) is a lot closer to 256 (NES/GB limit) than to 16K (ExGrafix limit). But flipping would complicate things, as each tile would need to be compared to flipped versions of all other tiles.
User avatar
mikejmoffitt
Posts: 1353
Joined: Sun May 27, 2012 8:43 pm

Re: Tile reduction

Post by mikejmoffitt »

It wasn't a very deeply thought-out algorithm - that's why I wanted it to prompt the user to choose between tiles in question and to be able to adjust the threshold where it considers them different.

A better, more advanced algorithm would want to consider adjacency of different pixels.
giles
Posts: 10
Joined: Sun Jan 13, 2013 10:58 am

Re: Tile reduction

Post by giles »

The way sixpack handles color reduction to 16 colors looks better than the results from png-nq or gimp. I like the way it handles dithering too.

What I was thinking of was a program that would take an image (png/bmp/whatever) and just match similar tiles; anything like the attached image. Then it would just save it in the same format so that it could be used with grit/sixpack/gfx2snes. I use grit because I'm using sneskit. So in this case I'd just let grit deal with exact duplicate tiles and flipped tiles.

This is assuming that this is not massively more trouble than it's worth. Another route, I suppose, would be to use ExHiRom.
Attachments
tiles.png
tiles.png (265 Bytes) Viewed 4985 times
mic_
Posts: 922
Joined: Thu Oct 05, 2006 6:29 am

Re: Tile reduction

Post by mic_ »

The way sixpack handles color reduction to 16 colors looks better than the results from png-nq or gimp. I like the way it handles dithering too.
Sixpack uses the NeuQuant algorithm for color quantization. I've been thinking of integrating support for scolorq, since it supposedly performs better for very small number of colors (like 2bpp tiles). I also did some experiments with k-h-means quantization, but it was quite slow, and didn't yield any results worth writing home about.

The dithering algorithm is the simplest possible; select either a darker color or a lighter color based on (row ^ column) & 1.
giles
Posts: 10
Joined: Sun Jan 13, 2013 10:58 am

Re: Tile reduction

Post by giles »

I replaced 4 1/2 4bpp images with images processed with sixpack and it saved me ~1500 bytes. (The half image I used half of the image from sixpack and half from gimp.)

I still need to work on better tile reduction for 8bpp images.
Post Reply