This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Palette fading techniques

Palette fading techniques
by on (#94333)
A common trick in NES games is to fade a palette to black, and back, by progressively ANDing the correct palette values with a bitmask such as 3F, 2F, 1F and 0F.

An example of such game is Simon's Quest, as shown in the screenshot below.
This algorithm is cheap and easy to implement. However, it is restricted into fading through from/to black, which is why the game fades through black.

However, if one wants to fade between two arbitrary palettes, things are not so easy. Has anyone attempted it?
I can think of an algorithm, which is not cheap:
Precalculate a 64x64x4 array of values and place it in a vacant ROM page. It takes 16384 bytes (4000h). Key 1 is the source palette value, key 2 is the target palette value, and key 3 is the degree of interpolation (20%, 40%, 60%, 80%). An program populates the array by determining which NES color index most closely resembles the given mixture of NES colors.
Fading the palette is a matter of reprogramming the palette six times:
First, with the source palette (srccolor) (is optional).
Then four times with table[srccolor][dstcolor][i] for each color in the screen palette.
And finally with the target palette (dstcolor).
Resourcewise, it is not cheap.
It could be made smoother by including fewer degrees of interpolation (such as one: 50% or two: 33% and 67%): This would take 1000h or 2000h bytes respectively. Additional degrees of interpolation could be synthesized at runtime by flickering between the previous and the next value in the table. Such flickering might not look nice, though.

Are there other, perhaps better algorithms for arbitrary palette fades on NES?



Image
(Screenshot is from my Finnish translation, captured in my emulator in a three-way-fields-merge NTSC mode.)

by on (#94334)
How about a cheap hue/brightness fade? Move left or right along the hue, then move up or down along brightness.

by on (#94335)
I would simply attempt to do brightness fade with hue change in large steps into closest direction.

Edit: the same what Dwedit said, basically.

by on (#94339)
I think there is a problem if you use the AND-ing approach.

For example if you use color $20, then with your sequence it will become $20, $20, $00, $00, which is not what you want since you probably wanted sometihng like $20, $10, $00, $0f.

Personally I use the method to substract $10 every time, and if the result is negative I use $0f to get black. After 4 passes, all colors will be black.

If I were to fade between two arbitrary palettes, I would probably separate into hue and brightness and gradually decrease or increase each of them until you get the right value. It might be tricky to code, but you get the idea.

For example to fade from $13 to $3a you'd get something like :
$13, $12, $21, $2c, $3b, $3a

by on (#94342)
Could you just treat all the NES colors as a 2d array and "walk" the source color to the destination color? A 2D grid of 52 colors should take too much ROM space, right?

by on (#94343)
Bregalad wrote:
For example if you use color $20, then with your sequence it will become $20, $20, $00, $00, which is not what you want since you probably wanted sometihng like $20, $10, $00, $0f.

Actually Simon's Quest partially solves this problem by setting palette[x] into
min(origpalette[x], (origpalette[x] & 0x0F) | fadelevel) where fadelevel goes from 0x00 to 0x30 or from 0x30 to 0x00.
This gets $00,$10,$20,$20 instead of $00,$00,$20,$20. For $13, it gets $03,$13,$13,$13. For $34, it gets $04,$14,$24,$34...

by on (#94345)
The problem with angular palette fades suggested by many here is that fades between monochrome and colored do not work at all.

by on (#94348)
It will never work at all since the NES can only output completely monochrome or completely saturated colours.

by on (#94349)
I guess I don't understand why creating your own arranged 2d array of colors wont work.

If you pre-calculate the table then most of the math goes away, right?

UPDATE: Thank you Drag!

by on (#94351)
The most common method I've seen for fading in and out is just by adding or subtracting 10.

For instance, to fade out, you start with your normal colors, and just subtract 10 for each step, and underflow to 0F.

To fade in, start at brightness 0x (but with your hues filled in), and add 10 to each color that hasn't reached its target yet.

Alternatively, you can take advantage of the fact that the upper 2 bits of the palette are unused, so you could start out by subtracting 40 from your target palette, and add 10 each step, replacing values bigger than $40 with color $0F. This at least gets your fade-in to look the same as your fade-out.

Finally, take a look at the Tiny Toons cartoon maker thing for NES, it fades to blue, but it might be using a LUT for that.

You can't simply walk across the palette space like it's 2D, because complementary colors (like blue and orange) naturally cancel each other out when fading from one to the other, so they'd need to pass through a shade of gray in the process. However, you can do if if you're fading between two colors whose hues are close enough together.

by on (#94352)
slobu wrote:
I guess I don't understand why creating your own arranged 2d array of colors wont work.

If you pre-calculate the table then most of the math goes away, right?

Such precalculated arrays might require too much space for some purposes.

In any case, here's a little comparison between two algorithms.
On the left, angular fading. On the right, precalculated table using a search for smallest color difference against linearly interpolated RGB color.
Image
(Pay attention to the highlight in the ground pieces and the rock below it.)

In the angular fading, both the source and the target colors are split into level and color. If both colors are 1..12, the colors are translated into 0..11 range and linearly interpolated along nearest wrapping direction. Otherwise, the colors are just linearly interpolated. Levels are linearly interpolated. Then the level and color is merged back to form the resulting color.
In PHP,
Code:
        $level1 = $c1 >> 4; $color1 = $c1 & 0x0F;
        $level2 = $c2 >> 4; $color2 = $c2 & 0x0F;
       
        $level = (int)($level1 + ($level2-$level1) * $mix);
         
        if($color1 >= 1 && $color1 <= 13
        && $color2 >= 1 && $color2 <= 13)
        { 
          $angle1 = ($color1-1);
          $angle2 = ($color2-1);
         
          if(abs($angle2 - $angle1) > 6)
          {
            if($angle2 < $angle1) $angle2 += 12; else $angle1 += 12;
          }
          $angle = (int)($angle1 + ($angle2-$angle1) * $mix);
          $color = 1 + ($angle%12);
        }
        else
        {
          $color = (int)($color1 + ($color2-$color1) * $mix);
        }
       
        $c = $level*16 + $color;
        $rgb = get_nes_rgb_actual($c);

And the precalculated way was this:
Code:
      // Which color we want?
      $goal = Array( $a[0] + $power * ($b[0]-$a[0]),
                     $a[1] + $power * ($b[1]-$a[1]),
                     $a[2] + $power * ($b[2]-$a[2]) );

      // Figure out which color best represents this
      $best_diff = null;
      $best_color= null;
     
      foreach($nes_rgb as $m => $c)
      {
        $diff = ColorDifference($goal, $c);
        if($m == 0 || $diff < $best_diff)
          { $best_diff = $diff; $best_color = $m; }
      }

      $mixtable[$c1][$c2][$index] = $best_color;

I also tried the flickering method, but it did not look nearly as nice as I hoped...

EDIT: Actually, if I reduce the maximum difference between the two constituting colors in the pair that is flickered, it DOES begin to look quite nice: image...

by on (#94354)
Drag wrote:
Finally, take a look at the Tiny Toons cartoon maker thing for NES, it fades to blue, but it might be using a LUT for that.

I don't have that game, but I can tell you this: The fade code used for cut scenes in Thwaite is based on subtracting $10, $20, or $30. It reassigns $F0 (what you get when you subtract $10 from dark gray) to $02 (dark blue), $0D (sync-fooling black) to $0F, and any other "negative" value ($80-$FF) to $0F.

by on (#94524)
TL;DR: Walking across the palette as though it's 2D is close, when dealing with only hues (not grays), but there's still some funkiness with saturation that may be hard (not impossible!) to deal with on the NES.

Long version:
After giving it a bunch of thought, I basically figured out what's going on, in terms of the NTSC signal.

Let's say color 21 looks like this:
Code:
¯¯¯¯¯¯______¯¯¯¯¯¯______

...and color 25 looks like this:
Code:
____¯¯¯¯¯¯______¯¯¯¯¯¯__


50% of 21 combined with 50% of 25 should look something like this:
Code:
----¯¯----__----¯¯----__


It's still a wave that's oscillating at the colorburst frequency, so it'd be considered a valid color, however, it's much less saturated than either of the colors alone. As for which HUE this is, I'm not sure... it's probably hue 23 (half way between 21 and 25) or something, but again, It's at 1/3 the SATURATION of both 21 and 25.

Let's take color 21 again:
Code:
¯¯¯¯¯¯______¯¯¯¯¯¯______

...and color 27, its complement:
Code:
______¯¯¯¯¯¯______¯¯¯¯¯¯


Combine 50% of 21 with 50% of 27, and you get this:
Code:
------------------------


...which is a gray color, the same luminance as the two colors. On the NES, this isn't completely possible, because there isn't a shade of gray available that represents the half-way point between color 20 and 2D.


So, when fading between two hues of the same brightness (let's call them A and B), the halfway point is more and more desaturated, the closer B is to A's complement.

Ok, so that's how the hue and saturation works, fading between two colors of different brightnesses would simply be linear. For instance, fading between color 21 and color 17, the high nybble would act the same way as if you were fading between 21 and 11.

by on (#94719)
I looked into the Tiny Toons cartoon maker for NES, and there's a large lookup table at CPU$FEDB that the game uses to fade arbitrary colors to color $02 and back, in 1/3 increments.

When they generated this table, I wonder if they faded the colors in YIQ space, or if they interpolated to RGB and back.

by on (#94720)
Drag wrote:
When they generated this table, I wonder if they faded the colors in YIQ space, or if they interpolated to RGB and back.

It'd be the same thing, as the conversion from YIQ to device-RGB is linear.

by on (#94747)
tepples wrote:
Drag wrote:
When they generated this table, I wonder if they faded the colors in YIQ space, or if they interpolated to RGB and back.

It'd be the same thing, as the conversion from YIQ to device-RGB is linear.

You're right, I just confused myself because I was testing with arbitrary RGB colors instead of the NES's actual colors (in which the luminance of all colors in a row are the same).

by on (#94768)
Sorry for the huge wall of text, but I had no life today. :D

I "simulated" a hypothetical display system where the colorburst has 16 samples to it (giving 16 distinct colors), and added each possible color together to figure out the hue and saturation of the resulting midpoint between the two colors.
Code:
FEDA852101258ADE Hue 1; Sat 15
FEDA852101258ADE Hue 1; Sat 15
FEDA852101258ADE Hue 1; Sat 15
'-.           .- |
   -_       _-   |
     .     .     |
      -._.-      |
FEDA852101258ADE Hue 1; Sat 15
EFEDA852101258AD Hue 2; Sat 15
EEDB9631001369BD Hue 1.5; Sat 14
--.            . |
   '.        .'  |
     -      -    |
      '.__.'     |
FEDA852101258ADE Hue 1; Sat 15
DEFEDA852101258A Hue 3; Sat 15
EEECA753111357AC Hue 2; Sat 13
---_           _ |
    -         -  |
     '.     .'   |
       '...'     |
FEDA852101258ADE Hue 1; Sat 15
ADEFEDA852101258 Hue 4; Sat 15
CDDCB9642112469B Hue 2.5; Sat 12
_.._             |
    '.        .' |
      -_    _-   |
        -..-     |
FEDA852101258ADE Hue 1; Sat 15
8ADEFEDA85210125 Hue 5; Sat 15
BCDCB97543234579 Hue 3; Sat 11
 _._             |
'   '.         . |
      '._   _.'  |
         '-'     |
FEDA852101258ADE Hue 1; Sat 15
58ADEFEDA8521012 Hue 6; Sat 15
ABBBBA8754334578 Hue 3.5; Sat 8
                 |
-''''-_        _ |
       '._  _.'  |
          ''     |
FEDA852101258ADE Hue 1; Sat 15
258ADEFEDA852101 Hue 7; Sat 15
89AAA98765555567 Hue 4; Sat 5
                 |
_.---._          |
       '-.....-' |
                 |
FEDA852101258ADE Hue 1; Sat 15
1258ADEFEDA85210 Hue 8; Sat 15
8899998877666677 Hue 4.5; Sat 3
                 |
__....__         |
        ''----'' |
                 |
FEDA852101258ADE Hue 1; Sat 15
01258ADEFEDA8521 Hue 9; Sat 15
7777877777778777 Hue -; Sat 0
                 |
    _       _    |
'''' ''''''' ''''|
                 |
FEDA852101258ADE Hue 1; Sat 15
101258ADEFEDA852 Hue 10; Sat 15
8776666778899998 Hue 13.5; Sat 3
                 |
_        __...._ |
 ''----''        |
                 |
FEDA852101258ADE Hue 1; Sat 15
2101258ADEFEDA85 Hue 11; Sat 15
876555556789AAA9 Hue 14; Sat 5
                 |
_         _.---. |
 '-.....-'       |
                 |
FEDA852101258ADE Hue 1; Sat 15
52101258ADEFEDA8 Hue 12; Sat 15
A8754334578ABBBB Hue 14.5; Sat 8
                 |
-_        _-'''' |
  '._  _.'       |
     ''          |
FEDA852101258ADE Hue 1; Sat 15
852101258ADEFEDA Hue 13; Sat 15
B97543234579BCDC Hue 15; Sat 11
             _._ |
'.         .'    |
  '._   _.'      |
     '-'         |
FEDA852101258ADE Hue 1; Sat 15
A852101258ADEFED Hue 14; Sat 15
CB9642112469BCDD Hue 15.5; Sat 12
_            _.. |
 '.        .'    |
   -_    _-      |
     -..-        |
FEDA852101258ADE Hue 1; Sat 15
DA852101258ADEFE Hue 15; Sat 15
ECA753111357ACEE Hue 16; Sat 13
-_           _-- |
  -         -    |
   '.     .'     |
     '...'       |
FEDA852101258ADE Hue 1; Sat 15
EDA852101258ADEF Hue 1; Sat 15
EDB9631001369BDE Hue 16.5; Sat 14
-.            .- |
  '.        .'   |
    -      -     |
     '.__.'      |


I'm probably the only one that'll find this interesting, but there it is. :P
I hypothesize that colors with different luminances will behave the same way, hue and sat wise, but the luminance will be a linear fade. Different saturations, I don't know, but it's not important for the NES anyway.

Also, I calculated "hue" as the location of the highest point of the wave, and the saturation is just the difference between the highest and lowest points on the wave.

by on (#94850)
TL;DR: You basically can just walk between two colors, as though the palette is a 2D map, but you need to make some exceptions depending on how far apart two colors are, or when you're going from a color to a gray, or vice versa.

After playing around, I figured out an algorithm that seems to work when I play around in yychr. :P

Assume a 5 step fade; ColorA is the start color, and ColorB is the target color. ColorDiff is the shortest distance between ColorA and ColorB. (For example, if A was $12 and B was $1C, you'd go $12, $11, $1C, and ColorDiff would be 2.)

  • if ColorDiff < 5
    • Hue is a linear slide from A to B, moving along the shortest distance
  • if ColorDiff == 5
    • Hue follows these steps: (+ moves towards B, - moves towards A, both move along the shortest distance)
      • A
      • A+1
      • Gray
      • B-1
      • B
  • if ColorDiff == 6
    • Fade degenerates into a 3-step fade: (stretched out into 5 steps, that is)
      • A
      • Gray
      • B


ColorDiff == 6 is a degenerate case because there's no shortest distance between ColorA and ColorB. That means, ColorA and ColorB are complements, and a fade between them would have no hue slide; the saturation would slide to 0, the hue would flip from A to B, and the saturation would slide back up. However, the NES offers no saturation control, so flipping to gray is the best I can do.

ColorDiff == 5 doesn't immediately go to gray like this because even though the colors are close to being complements, they aren't, and there's still a shortest distance you can slide the hue along. However, the saturation would still get close to 0 in the middle of the fade, and coincidentally, this is the only case where you'd need to skip a hue to get from ColorA to ColorB, so I just stuck the skip in the middle and hid it with the gray. At the same time, step 2 is ColorA one hue closer to its complement (which isn't a bad approximation for desaturating a color), and step 4 is ColorB one hue closer to its complement. The result seems to work, anyway. :P

The specific gray you use is the $x0 gray that's on the previous row of the color. So the equivalent gray for $3x would be $20, $2x would be $10, $1x would be $00, and $0x would be $0F. Again, this seemed to look the best when I was playing around.

To fade from a color to a gray (or vice versa), treat the hue as though it's a 2-step fade where one step is color and the other step is gray.

In all cases, a fade between two different brightnesses would just be linear. To fade from a color on row 0 to a color on row 3, you'd pass through rows 1 and 2, no matter what the hue or saturation is doing. So basically, the upper nybble of the color is always a linear slide (but remember to use the gray from the previous row, when you need to display a gray)

Of course, you can make exceptions when you're fading to/from $0F or to/from $30; treat those as just adding or subtracting $10 from the color each step.