Bitmap Paletting

Reverse engineering LEGO Island's primary asset packaging format
Post Reply
User avatar
MattKC
Site Admin
Posts: 323
Joined: Mon Aug 22, 2022 1:05 am
Contact:

Bitmap Paletting

Post by MattKC »

LEGO Island's bitmaps are paletted in a specific way. The bitmaps must be 256-colors (or else the game will crash loading them), and the first 10 and last 10 colors of the palette are forced to the same colors, as well as 2 colors in the middle, regardless of what they may be in the original bitmap. This must be accounted for when creating replacement bitmaps, otherwise certain palette entries will be forcibly changed and cause the following artifacts:
vlcsnap-2022-07-29-00h39m09s409.png
The forced palette can be seen most clearly when inserting this image, which is paletted so that each color corresponds to a palette entry in order. Regardless of the original palette, 22 of the colors are forced, and the first as a rule becomes transparency:
unknown.png
unknown (1).png
Finally, here is a palette from an original in-game bitmap. As you can see, it has those forced colors already in the palette so it can take advantage of the fact those colors need to be there:
unknown (2).png
For reference, these are the forced colors:

Code: Select all

0 - ff00ff (mapped to something else in-game)
1 - bf0000
2 - 00bf00
3 - bfbf00
4 - 0000bf
5 - bf00bf
6 - 00bfbf
7 - c0c0c0
8 - c0dcc0
9 - a6caf0

140 - ff00ff (mapped to sky color)
141 - 39a3d9 (mapped to sky color)

246 - fffbf0
247 - a0a0a4
248 - 808080
249 - ff0000
250 - 00ff00
251 - ffff00
252 - 0000ff
253 - ff00ff
254 - 00ffff
255 - ffffff
User avatar
MattKC
Site Admin
Posts: 323
Joined: Mon Aug 22, 2022 1:05 am
Contact:

Re: Bitmap Paletting

Post by MattKC »

I've spent some time reverse engineering the class MxPalette. For the most part it tells us things we already know - when an MxBitmap is loaded, it uses an MxPalette function that reads all of its entries, except the first and last 10 which are retrieved from the Win32 API GetSystemPaletteEntries(). This means these entries aren't even specific to the game, they're all from Windows' global system palette. It's still not really clear why the game uses these, are there bitmaps that need those system colors? And if so, why wouldn't the bitmaps themselves just be paletted with those entries? Most of the bitmaps actually do have those entries so forcing them doesn't make any sense...

It's almost certainly possible to disable the system palette overriding. That could give us about 9.4% more color precision in our palettes, though it's unclear if it will have any adverse effects. It may be worth experimenting with and I'll post back here if I find anything interesting.

The entries at 140 and 141 are also confirmed to be "special" entries, especially 141. 141 seems to be specifically "settable", presumably to the sky color, and 140 is sometimes just set to the same color. This too is very unclear if I'm being honest and requires more investigation to see why this is set up this way.

Something worth noting is that each palette entry has a "flags" member (probably actually to just pad the 24-bits of 8-bit RGB out to 32-bits) and these flags are set differently depending on the above:
  • The first and last 10 entries (from the system palette) are given the flags 0x80.
  • Entry 141 (presumably the sky color) is given the flags 0x44.
  • The remaining entries (custom file-specific) are given the flags 0x84.
It's hard to say how these flags are used just yet, but it's interesting that they correspond exactly to the different types of entries we've found so far. Also the fact that entry 140 has different flags from entry 141 could be a clue as to the differences in the way they're used.
User avatar
MattKC
Site Admin
Posts: 323
Joined: Mon Aug 22, 2022 1:05 am
Contact:

Re: Bitmap Paletting

Post by MattKC »

I'm a little embarrassed I didn't know this before, but those 20 reserved entries are actually a Windows thing. Right here it says that when Windows is running in 256 color mode, the first 10 and last 10 entries are reserved by the system, leaving the middle 236 configurable by the application.

I'm still not sure why the game itself has to enforce this - if a bitmap palette got it wrong, wouldn't those entries be forced by the system anyway? Or maybe the system doesn't enforce it and it just causes Undefined Behavior if the entries aren't what's expected...

It also means the game forces palette entries unnecessarily when the game is running in 16-bit mode because Windows doesn't have that restriction in that mode. I have a strong suspicion 16-bit mode was added late in development (we already know hardware 3D mode was added late, so 16-bit might have been added alongside it). The code suggests that most functionality was written with 256 color in mind, and then they throw in some 16-bit upconversion functionality at the end for forward compatibility.
Post Reply