Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in - nap
CSDb User Forums


Forums > C64 Coding > Unrestricted hires colour mode! (albeit just a *tiny* bit letterboxed..)
2015-01-23 07:59
ChristopherJam

Registered: Aug 2004
Posts: 1409
Unrestricted hires colour mode! (albeit just a *tiny* bit letterboxed..)

I've been spending a few weeks on and off experimenting with how sequences of hires pixels behave, and as something of a side effect I've reached a startling conclusion.

If you layer seven hires sprites over a multicolour sprite over a multicolour bitmap, with the just that final sprite set to a lower priority than the bitmap foreground colours, I'm pretty sure you can have a 24x1 pixel area of any pixel any colour.

It's easily done for a palette of 11 colours as so:
BBbbbbbbbbbbbbbbbbbbBBbb # background layer: two pixels from $d800 & $d802, rest from $d021
 00112233445566778899    # MCM sprite layer. Note odd x-position -> half pixels peek out from under fg
  ff  ff  ff  ff  ff  ff # bitmap fg layer
  s   s   s   s   s   s  # hires sprite layer. 's' where layer's always opaque, space where it is optional


So, any of the pixels whose x%4 is 0 or 1 can be any of the 7 hires colours or any of the three MCM sprite colours, or $d021
any pixels where x%4==2 can be any one of the 7 hires sprite colours (so ensure those 7 include the up to six represented here)
any pixels where x%4==3 are unrestricted

For 16 colours it's more complex. I have a algorithm that will deal with any sequence for which all sixteen colours are present in the first 16 pixels (ie the first 16 are just a permutation), which chooses from about 50 different layouts depending on the last 8 colours and where they can be found in the first 16.

I've yet to generalise to all 16^24 possibilities, but have also yet to find a sequence that cannot be represented. lp_solve and gprolog have both failed me, as they grind to a halt if I try to describe the general problem.

Would anyone care to prove me right or wrong about the general case being solvable (preferably with either an algorithm or a counter example)? I'm having trouble concentrating on anything else while this is still an open question.


Not sure whether this belongs in Coding or Pixeling; posting here because it's pretty impractical for artwork. Still, it's trivially stretchable to full screen height, so perhaps it would be good for a narrow area of vertical 'raster bars' :D
2015-01-23 08:39
ChristopherJam

Registered: Aug 2004
Posts: 1409
Oh, and here's an example layout for the 'arbitrary first 16, distinct final eight' case:

|00'  '  '  |  '  'dd'ff|  '  '33'  |  # MCM bmp bg layer
| 1'14'45'5 |  '  '  '  |  '  '  '  |  # MCM mob layer
|  '33'  '77|88'aa'  '  |22'55'  '  |  # MCM bmp fg layer
|  '2 '  '6 | 9' b'c 'e |b '6 '9 'ac|  # hires mob layer

|01 23 45 67 89 ab cd ef b2 65 93 ac|  # displayed colours
2015-01-23 11:14
Oswald

Registered: Apr 2002
Posts: 5094
nice find, something for HCL :)
2015-01-23 11:58
HCL

Registered: Feb 2003
Posts: 728
Me!? :)
2015-01-23 13:18
ChristopherJam

Registered: Aug 2004
Posts: 1409
Thanks, @Oswald.
Help me, @HCL, you're my only hope :D
2015-01-23 14:18
Dane

Registered: May 2002
Posts: 423
But when would 16col unrestricted in such a small area be useful?

Fiddling with bitmap, sprites and priority to get unusual graphic modes is usually my cup of tea. :)
2015-01-23 14:28
Joe

Registered: Apr 2002
Posts: 229
I'd still prefer someone would make editors of the underlay/overlay sprites+bitmap mode Algorithm introduced some years back. Could be really useful in ordinary demos (loading time etc).

But.. I support all and every attempt in breaking the boundaries as long as the final result doesn't become interlaced or too small...
2015-01-23 14:29
Oswald

Registered: Apr 2002
Posts: 5094
I mean it could make a loaderpart or something if Y stretched :)
2015-01-23 14:37
Jammer

Registered: Nov 2002
Posts: 1335
This thing loosely reminded me of my idea for Lemmings port for C64, this time without reversed background/sprite use and narrow playfield ;) Mostly about writing more Lemmings into single sprites and distributing sprites wisely around with multiplexing. Maybe even a bitmap background could be possible in this case? :D Of course there would be some flickering on characters, but NES games also suffered similar problems and they passed anyway :D
2015-01-23 14:59
ChristopherJam

Registered: Aug 2004
Posts: 1409
@Dane - I'm mostly posting here rather than in the pixeling forum because it doesn't seem like a very practical result at all :)

Could perhaps have multiple rows separated by black lines or stretch, but it would still only be three chars wide.
2015-01-23 16:19
Ninja

Registered: Jan 2002
Posts: 411
This calls for Copyfault as the problem should please his interest in GFX modes and mathmatical problems :)
2015-01-24 03:00
chatGPZ

Registered: Dec 2001
Posts: 11386
you forgot "practically useless" =)
2015-01-24 03:21
ChristopherJam

Registered: Aug 2004
Posts: 1409
@Groepaz - I got as far as "pretty impractical" in the OP, but concur that that was something of an understatement :D
2015-01-24 03:39
ChristopherJam

Registered: Aug 2004
Posts: 1409
@Jammer I've had related thoughts myself.. The reversal in the official port's still a brilliant idea, mind.
2015-01-25 20:26
Digger

Registered: Mar 2005
Posts: 437
I can imagine having restrictionless twister upscroller using this mode if combined with FLI. Should be enough rastertime to push all the pixels, providing you'll somehow solve your LUTs ChristopherJam :)
2015-01-26 20:54
ChristopherJam

Registered: Aug 2004
Posts: 1409
@DGGR, pushing the pixels should be fine, however the palette is a different issue.

I've just implemented a solution finder, and I've discovered that while it's almost certainly safe to have a constant background colour and four constant hires sprite colours, I would still need to be able to change three hires sprite colours and all three sprite multicolours every line for complete freedom, and probably some $d800 colours as well - a minimum of 36 cycles, probably more like 42 or 48. Seeing as the sprite DMA alone would be taking 19 cycles per line, I can't see that working.

Enough 'difficult' colours in common between all the candidate lines for the upscroller and perhaps something could be done - it's getting a little far away from the original unrestricted concept, but would certainly make for a more interesting effect :)

ps - python 3's "yield from" is magical!
2015-01-27 00:22
Copyfault

Registered: Dec 2001
Posts: 478
What a nice thread ;)) @Ninja: thanks for pointing me to this one!

I think it's possible to "proof" that 24x1 unrestricted hires mode is possible - i.e. that any of the 16^24 pixel combination can be displayed. Maybe even more width is possible, but I don't have a complete reasoning for that atm. But first of all let's see if the basic idea works.

The 24x1 pixels can be divided into twelve 2x1-cells (with the same width as a usual multicolour pixel). Four of these cells sum up to a 8x1 pixel row each of which belonging to a char. If we denote the three chars by C1, C2, C3, the cells by 01,...,04 for each char and the colours in each cell by f1,f2 we have the following picture:
|         C1        |         C2        |         C3        |
| 01 | 02 | 03 | 04 | 01 | 02 | 03 | 04 | 01 | 02 | 03 | 04 |
|f1f2|f1f2|f1f2|f1f2|f1f2|f1f2|f1f2|f1f2|f1f2|f1f2|f1f2|f1f2|

Assume we have (a priori) virtual layers: l0 as "background layer" and l1 as "foreground layer". In a first step, the occuring colours will be assigned to a certain layer; in a second step, both layer types will be constructed by means of what the vic is capable of.

Now let's assign the colours by the following rules:
1. for each cell check if f1=f2
-->> if this is true, assign f1 and f2 to l0
-->> the appropriate cell will not be considered in further checks
2. a) Sort the remaining cells by amount of occuring colours
2. b) Most often colour will be assigned to l1
2. c) all cells carrying this colours will not be considered in further checks
2. d) As long as there are remaining cells with same colours, repeat from 2.a)
3. For the remaining cells: arbitrarily assign colours to l0, l1

Worst case scenario is: all cells have different colours and there are exactly eight colours each of which occuring exactly 2 times.

In this case, check 1 doesn't do anything. Check 2 will find a maximum 2 -> two cells done
Now repeapt check 2 for the remaining 20 pixels:
least max >= no.of pixels/no.of colours = 20/15 = 1 + 5/20
-->> least max = 2 -> two cells done
etc.
Counting like this, the worst case would be that both cells that are "done" in each step have both colours f1 and f2 equal. In this case check 2 will end after looping 4 times and the remaining 4 cells will carry 8 different colours, i.e. every remaining pixel is individually coloured. By Rule 3 we arbitrarily assign them to l0 and l1.

Counting the total no. of colours in each layer, we find that for both the sum is 8. Adding the layers to the picture we now get
|         C1        |         C2        |         C3        |
| 01 | 02 | 03 | 04 | 01 | 02 | 03 | 04 | 01 | 02 | 03 | 04 |
|f1f2|f1f2|f1f2|f1f2|f1f2|f1f2|f1f2|f1f2|f1f2|f1f2|f1f2|f1f2|
|f1     f2 f1   f1     f2   f2 f1   f1   f1     f2   f2   f2| layer 0
|  f2 f1     f2   f2 f1   f1     f2   f2   f2 f1   f1   f1  | layer 1


Now we have to construct the layers with the vic.
Layer 0 can be done using the Multicolour GFX-Mode:
|         c1        |         c2        |         c3        |
| v1 | v0 | d8 |spr0| v1 | v0 | d8 |spr1| v1 | v0 | d8 | 00 |

00 is bgr colour, v1,v0 are the vram cols, d8 comes from colour ram and spr0, spr1 are the corresponding sprite colours of sprite0(=lowest priority) which will be set to multicolour mode. This way, each cell can have a unique "layer0"-colour.

For layer 1 we use all remaining sprites as hires sprites. As shown in the first step of the proof, we need eight different colours at most but there are only 7 sprites left. Now the shift trick of the OP comes into play: if we shift the multicolour sprite and utilize the sprite/bgr/gfx-priority handling of the vic, the third mc-colour can be misused to form a hires pixel "above" the v0-colour.
For example, a hires pixel done with this trick at pixel position c2,02,f1 would look like this:
|         c1        |         c2        |         c3        |
| v1 | v0 | d8 |spr0| v1 | v0 | d8 |spr1| v1 | v0 | d8 | 00 | pure gfx data
|             ssssssss  ssss      ssssssss                  | sprite0 data
|ss     ss ss     ss   ss      ss   ss   ss   ss     ss ss  | data sprite1-7

This completes the proof; an algorithm should be easy to do based on this.

Am I forgetting something? Maybe the assumed "worst case" is not "worse enough"?

By some clever shifting of the "foreground layer" l1 and maybe by using x-expanded sprites throughout it should be possible to get some wider range. Do I smell a "Hardcore Coding Compo for senseless gfx modes" here ;)?
2015-01-27 09:04
ChristopherJam

Registered: Aug 2004
Posts: 1409
@Copyfault - I like your approach, and the reasoning seems pretty sound, from what I can follow. Only issue I can see is that the worst case scenario for your two layer abstraction actually needs nine colours for foreground layer. Cf
01 12 20 34 45 56 67 73 89 ab cd ef

The colours 0 to 2 form a ring of three, that need two foreground colours between them
The colours 3 to 7 form a ring of five, that need three foreground colours between them
The remaining eight colours need four foreground colours between them

I suspect this means your proof now falls down, as we now need all seven hires sprites and two of the MCM sprite colours just for the foreground colours, which doesn't leave enough MCM sprite colours to cover the two cells in the background layer that might not be coverable by d800, d021, and VM


The good news is, further randomised testing seems to indicate that only six hires sprites are needed for the frontmost layer, even in the scenario above. For example:
|   ,   ,   ,   |   ,   ,   ,   |   ,   ,   ,f f| palette : f
|   ,   ,   ,   |   ,   ,7 7,7 7|   ,b b,   ,   | palettes: -,7,b
|   ,   ,   ,   |   ,  6,6  ,   |  a,a  ,  e,e  | palette : 6ae
|   ,2 2,2 2,4 4|4 4,6 6,   ,   |9 9,   ,d d,   | palettes: 24,46,9d
|0 1,1  ,  0,3  |  5,5  ,   ,  3|8  ,   ,c  ,   | palette : 01358c

Alternately, if I hold $d021 constant at zero, I can colour thousands of randomised pixmaps (with either completely random pixels, or a permutation of arange(24)%16) without fail, as long as I allocate 7 hires sprites

As for wider ranges, I'm wondering how wide an area could be covered if the hires sprites were staggered. After all, even as is we could position each at the first x-position their colour is used. On top of that, it's starting to look like the seventh is currently unused.

Start the 'image' halfway through a character cell, and the first two and last two 2x1 cells have free range for their background, too. Could 32x1 be within our grasp? Who knows, or dares to dream..

Compo sounds hilarious :D
2015-01-27 14:18
Oswald

Registered: Apr 2002
Posts: 5094
the twister scroller idea is pretty good for this one, altho complicated, static lines can be precalculated into simple lda/sta code.

altho even if colorful I dont think it would look spectacular at 24x200, 3 chars wide at best.
2015-01-27 17:58
algorithm

Registered: May 2002
Posts: 705
Regardless of small width, it is still nice proof of concept. However, I feel that even with some restrictions in place, the difference in output at a wider width would be negligible dependant on how the converter creates the image and sprite definitions.

Have a look at the mucsu-fli mode for example, having full width FLI with sprites over 240 pixel range (albeit blocky) but underlaid with hires masking. Copyfault I believe updated the routine to work at full 200 vertical lines.
2015-01-27 21:14
Copyfault

Registered: Dec 2001
Posts: 478
Quoting ChristopherJam
@Copyfault - I like your approach, and the reasoning seems pretty sound, from what I can follow. Only issue I can see is that the worst case scenario for your two layer abstraction actually needs nine colours for foreground layer. Cf
01 12 20 34 45 56 67 73 89 ab cd ef

The colours 0 to 2 form a ring of three, that need two foreground colours between them
The colours 3 to 7 form a ring of five, that need three foreground colours between them
The remaining eight colours need four foreground colours between them

I suspect this means your proof now falls down, as we now need all seven hires sprites and two of the MCM sprite colours just for the foreground colours, which doesn't leave enough MCM sprite colours to cover the two cells in the background layer that might not be coverable by d800, d021, and VM


Damn, processing your new worst case pixel sequence by the rules I suggested gives 9 necessary foreground colours just like you said.

But, the proof can be "repaired" (in a way;)). Instead of aligning the foreground layer with exactly three chars we move the layer 4 hires pixels to the right. As picture says more than 1000 words I'll put it into a table:
|     C1    |     C2    |     C3    |     C4    | chars
|--,--,v0,v1|v0,v1,bg,d8|v0,v1,bg,d8|v0,v1,--,--| l0: gfx
       |  ,  ,  ,  ,  ,  ,  ,s0,s0,  ,  ,  |      l0: spr0
      |v0,v1,v0,v1,bg,d8,v0,v1,sp,d8,v0,v1|       l0
       |  ,s1,  ,  ,  ,  ,  ,  ,  ,  ,s2,  |      l1: spr0
      | s, s,  ,s , s, s, s,s , s,s ,  , s|       l1: sp1-7
      | s, s,1 ,s , s, s, s,s , s,s , 2, s|       l1

The colours of spr0 are numbered s0,s1,s2 in order to show where the corresponding l1-colours reoccur. In the outer chars C1 and C4 the '--'-pixels can be coloured by $d800 (e.g. to create a frame or whatever design is wanted).

This way, we have 7 hires sprites (=7 l1-colours) + 2 mc-colours (=2 further l1-colours) = the needed 9 colours.

Hope there's no other worst case pixel sequence.


From a mathmatical point of view, it would be interesting to find out the minimum of needed l1-colours. When starting the proof, I first had the feeling that 6 colours would suffice, but up to now I still don't have the faintest idea for a formal argument.
2015-01-28 06:37
Monte Carlos

Registered: Jun 2004
Posts: 359
Counting gives:

7 hires sprites = 7 colors
1 MC Srpite = 3 colors
1 MC bitmap = 3 colors
1 background = 1 color

gives total:
14 colors not 16
2015-01-28 07:53
AmiDog

Registered: Mar 2003
Posts: 97
Quoting Monte Carlos
Counting gives:

7 hires sprites = 7 colors
1 MC Srpite = 3 colors
1 MC bitmap = 3 colors
1 background = 1 color

gives total:
14 colors not 16

Yes, but you can have three new bitmap colors for each char (8 pixels), which is what makes this problem interesting. Thus for a 16 pixel wide area, you could use 17 colors (if there were that many available). The question is thus how wide you can make the area by carefully positioning the sprites, taking advantage of masking etc.
2015-01-28 14:02
Isildur

Registered: Sep 2006
Posts: 275
As a gfx man I dream of 5 colors unrestricted hires mode.
16 col isn't necessary. Give me 5 but 320x200 with decent editor or converter :)
2015-01-28 14:04
Oswald

Registered: Apr 2002
Posts: 5094
Quote: As a gfx man I dream of 5 colors unrestricted hires mode.
16 col isn't necessary. Give me 5 but 320x200 with decent editor or converter :)


nufli will do 5 for you... but there's even ufli..
2015-01-28 16:08
Monte Carlos

Registered: Jun 2004
Posts: 359
@AmiDog:
Yes, but the thread started with
"I'm pretty sure you can have a 24x1 pixel area of any pixel any colour"
and i do not see this from the preconditions.
2015-01-28 19:27
ChristopherJam

Registered: Aug 2004
Posts: 1409
Think I've got it, thanks to Copyfault's input, and some poking round graph theory papers (relevant concept is vertex covers - each pixel pair is the edge in a graph, foreground colours must be found to cover that graph).

The layout is pretty much fixed - might have to special case the instance where the first pixel requires an MCM multicolour, or alternately we can place a pair of black foreground pixels just to the left of the display area.

,   ,   |   ,   ,   ,   |   ,   ,i i,   |   ,   ,  d021
,a a,   |c c,   ,   ,   |g g,   ,   ,   |k k,   ,  cell backgrounds
,   ,   |   ,  e,e e,e  |   ,   ,   ,   |   ,   ,  MCM sprite 7, first colour
,   ,b b|   ,d d,   ,f f|   ,h h,   ,j j|   ,l l,  cell foregrounds
,   ,   |   ,   ,   ,   |   ,   ,   ,   |   ,   ,  hires sprites 0-6

 ^ ^     ^ ^     ^ ^     ^ ^     ^ ^     ^ ^       even pairs (hires or MCM sprite over bitmap BG or MCM sprite)
     ^ ^     ^ ^     ^ ^     ^ ^     ^ ^     ^ ^   odd pairs  (hires sprite over bitmap FG)


Assume all 12 cells contain 12 distinct pairs of colours (if there are fewer, then a similar proof
to this will result in a FG colour list no larger than that concluded below)

We now have 12 pixel-pairs that contain between them at most 16 colours
As we have fewer than 24 colours, at least one colour must appear in more than one pair.
Initialise the FG colour list to just that colour, and remove all pairs that contain it.

We now have at most ten pixel-pairs, that contain between them at most 15 colours
As we have fewer than 20 colours, at least one colour must appear in more than one pair.
Add that to the FG colour list, and remove all pairs that contain it.

We now have at most eight pixel-pairs, that contain between them at most 14 colours
As we have fewer than 16 colours, at least one colour must appear in more than one pair.
Add that to the FG colour list, and remove all pairs that contain it.

The FG colour list should now contain three colours

We now have at most six pixel-pairs left to cover. Take one colour from each of those
six, and add them to the FG colour list

The FG colour list now contains at most nine colours.

Now,
foreground pixels in odd pairs have free choice from seven colours (we just overlay them with a pixel from a hires sprite)
foreground pixels in even pairs have free choice from nine colours (we can either overlay with a hires sprite pixel, or set/modify an
MCM sprite 7 pixel)

Only six foreground pixels overlay odd pairs, so at most six of the foreground colours need to be allocated to hires sprites.
The remaining foreground colours can be distributed between any remaining hires sprites and the two remaining sprite multicolours.

Done!

(Not quite as "pure" as aligning the sprites with the character boundaries, but at this point I'm out. Thanks Copyfault, and Ninja for pointing him this way!)
2015-01-28 20:18
Dane

Registered: May 2002
Posts: 423
There is still some good stuff left to do with gfx and sprite priority. And though this particular idea doesn't seem that useful it got me thinking.

Iopop and I made a gfx format with 15 chars of 4-colour hires that didn't involve FLI. Apart from some gfx I made ages ago I don't know if it's ever been used again.

I've also had in mind to experiment a little with mcol bmp combined with mcol sprites shifted 1 pixel to create the illusion of hires using the right combinations. That has probably been done before.

And finally, some day it's time to make an XFLI picture where I make constant use of the option to move sprites in X-position, creating the illusion of a wider image area than 192 pixels.
2015-01-28 21:23
Joe

Registered: Apr 2002
Posts: 229
"I've also had in mind to experiment a little with mcol bmp combined with mcol sprites shifted 1 pixel to create the illusion of hires using the right combinations. That has probably been done before."

Dane: Yup, that's one way! I encourage you to try it for real, pinching Crimson in the side...
2015-01-28 23:03
Copyfault

Registered: Dec 2001
Posts: 478
Quoting ChristopherJam
...
We now have at most ten pixel-pairs, that contain between them at most 15 colours
As we have fewer than 20 colours, at least one colour must appear in more than one pair.
Add that to the FG colour list, and remove all pairs that contain it.

We now have at most eight pixel-pairs, that contain between them at most 14 colours
As we have fewer than 16 colours, at least one colour must appear in more than one pair.
Add that to the FG colour list, and remove all pairs that contain it.

The FG colour list should now contain three colours

We now have at most six pixel-pairs left to cover. Take one colour from each of those
six, and add them to the FG colour list

The FG colour list now contains at most nine colours.

This proves that there is no pixel sequence worse than the one you gave as example (modulo transpositions of 2x1-pixel-cells) and it proves that the maximum no.of colours in l1 (or in the FG colour list if you want to stick to this phrase) is nine. Using the 4-pixel-shifting of the sprite layers this fully completes the "weak form" of the proof; by "weak" I mean it's still unclear wether this upper bound for no.of colours in l1 is sharp or not.

The difficult version of the initial proposition would be as follows: find the minimal upper bound for the number of colours in l1.

Upon deeper thinking your FG-list-argument (taking into account the rigid definition of l1) already states that this minimal upper bound of the abstract layer 1 is indeed nine. So this leads us to the following more technical question: what is the minimal upper bound for the number of hires sprites that are necessary for constructing the abstract layer 1.

Quoting ChristopherJam
Now, foreground pixels in odd pairs have free choice from seven colours (we just overlay them with a pixel from a hires sprite)
foreground pixels in even pairs have free choice from nine colours (we can either overlay with a hires sprite pixel, or set/modify an
MCM sprite 7 pixel)

Only six foreground pixels overlay odd pairs, so at most six of the foreground colours need to be allocated to hires sprites.
The remaining foreground colours can be distributed between any remaining hires sprites and the two remaining sprite multicolours.

Done!

Great! Hope you can think of something else now ;)) But I'll try to keep you busy by sharing my thoughts on how to find an answer to the "technical strong version" of the initial question.

Quoting ChristopherJam
(Not quite as "pure" as aligning the sprites with the character boundaries, but at this point I'm out. Thanks Copyfault, and Ninja for pointing him this way!)

Thank you for entertaining!!

Speaking of aligning the sprites with the char boundaries, I think I have an idea how to argue why 6 hires sprites are enough even if you align the abstract layer 1 with the char boundaries.

First, assign the colours to l0 and l1 by the rules I gave in my former post.
Now do the following to optimize the colour distribution between l0 and l1:
4. if there are colours in l0 that are also in l1, move the pixels from l0 to l1
5. choose (one of) the most often occuring colour in l0 as bg colour; if possible, pick one of a char that still holds four different colours

I think this "frees" l0 from some colours that forced us to have four distinct colours in every char when constructing l0 by gfx- and spr0-pixels. Unfortunately I don't have a formal proof for that yet.

As an example, let's process the following pixel sequence (which is a transposition of your "worst case" sequence):
c d 8 9 2 0 3 4 1 2 6 5 a b 7 3 4 5 6 7 0 1 e f

No double pixel exists, so we continue with sorting colours by amount of occurance:
colours 0, 1, 2, 3, 4, 5, 6, 7 occur twice, the others 8, 9, a, b, c, d, e, f only once. The colours occuring twice are processed first, by the loop given as Rule 2:
c d,8 9,2 0,3 4|1 2,6 5,a b,7 3|4 5,6 7,0 1,e f|pix seq
   ,   ,  0,3  |   ,  5,   ,  3|  5,   ,0  ,   |l1
   ,   ,2  ,  4|   ,6  ,   ,7  |4  ,   ,  1,   |l0
c d,8 9,   ,   |1 2,   ,a b,   |   ,6 7,   ,e f|rem. cells

Now the loop quits because there is no colour to be found more than once among the remaing cells. So the remaining colours will be assigned arbitrarily to the layers.
c d,8 9,2 0,3 4|1 2,6 5,a b,7 3|4 5,6 7,0 1,e f|pix seq
c  ,8  ,  0,3  |1  ,  5,a  ,  3|  5,6  ,0  ,e  |l1
  d,  9,2  ,  4|  2,6  ,  b,7  |4  ,  7,  1,  f|l0

In l1 we find exactly nine colours: c, 8, 0, 3, 1, 5, a, 6, e. Now let's see how the new rule 4 affects the layer's contents: in l0 we have the colours d, 9, 2, 4, 6, b, 7, 1, f. Thus, 6 and 1 can be moved to l1:
c d,8 9,2 0,3 4|1 2,6 5,a b,7 3|4 5,6 7,0 1,e f|pix seq
c  ,8  ,  0,3  |1  ,6 5,a  ,  3|  5,6  ,0 1,e  |l1
  d,  9,2  ,  4|  2,   ,  b,7  |4  ,  7,   ,  f|l0

Last but not least, there are three colours occuring twice in l0: 2, 4, 7. As there are still four l0-colours in char1, we choose e.g. colour 2 as bg-colour. This gives:
c d,8 9,2 0,3 4|1 2,6 5,a b,7 3|4 5,6 7,0 1,e f|pix seq
c  ,8  ,  0,3  |1  ,6 5,a  ,  3|  5,6  ,0 1,e  |l1
  d,  9,2  ,  4|  2,   ,  b,7  |4  ,  7,   ,  f|l0
vr1,vr2,bgr,d8x|bgr,---,vr1,vr2|vr1,vr2,---,d8x|gfx data

Now the normal mc-gfx-mode suffices to construct l0 (for '---' it doesn't matter what gfx data is used as these pixels are fully covered by sprites)!!! For l1, the number of colours needed hasn't changed, it's still nine. Thus we can use one shifted mc-sprite together with the priority trick to create three hires pixels plus another six sprites for the remaining colours.

I think this kind of layer optimization will work in general but a full proof would be full of case distinctions.


Now that there is one sprite "left", we can go a step further and use this for the next line of gfx. With FLI and by wisely counting colours that can occur in y-direction it _could_ be possible to make some 24x200-pixel-window with unrestricted hires, but a proof or an algorithm for that is out of grasp atm.
2015-01-29 10:41
ChristopherJam

Registered: Aug 2004
Posts: 1409
Excellent, that works.

The seven l0 colours would have to have at least one duplicate across any pair of characters, but my one concern would be that it might be a different duplicate shared between a different pair. Perhaps this could be worked around by swapping a colour between l1 and l0? Six hires sprites certainly fits with my experimental results with a brute force allocator, but I've yet to prove it covers all bases.

And yes, the more flexibility there is in the colouring of any given line, the more likely it is that at least most of the palette can be kept the same between one 24x1 slice and another. Image coherency would help too; adjacent lines are likely to mostly use the same colours..
2015-01-29 10:45
ChristopherJam

Registered: Aug 2004
Posts: 1409
Dane, I did some experiments with an offset-by-one MCM sprite layer under the foreground of an MCM character mode layer a year or two ago. I was getting very nice results from a mode-aware dither routine, but all of my sources were photographs - I didn't really want to release anything that was just a conversion of someone else's 24 bit or greyscale artwork.

If I get my shit together I'll hopefully release some real artwork of my own later this year.

Glad this thread's provoked some thought, in any case :)
2015-02-22 23:38
Copyfault

Registered: Dec 2001
Posts: 478
Quoting ChristopherJam
Excellent, that works.
The seven l0 colours would have to have at least one duplicate across any pair of characters, but my one concern would be that it might be a different duplicate shared between a different pair. Perhaps this could be worked around by swapping a colour between l1 and l0? Six hires sprites certainly fits with my experimental results with a brute force allocator, but I've yet to prove it covers all bases.

...

I think I can prove the "hard version" now, i.e. that 24 pixels can be individually coloured by using max. 7 sprites; furhtermore, the sprite layers can be aligned with the char boundaries which gives room for furhter improvement of this "mode" ;)

The rules I already proposed seem to work quite well for showing this. I'll list the final version of them here for sake of completeness:
1. check all cells if both colours are identical
-> If they are, ignore the cell in step 2&3
2.a. Sort colours by occurance (in the remaining cells)
2.b. choose (one of) the most often occuring colour and move the corresponding pixels to l1
2.c. ignore the cells with this colour for step 2&3
2.d. as long as there are colours occuring more than once, repeat step 2
3. the remaining cells have different colours -> choose one in each cell and move it to l1
4. Check all cells (including the ones that were ignored in the steps before) for colours that are in l1 already and move the corresponding pixels to l1
5. in case of less than nine colours in l1, move pixels to l1 until there are nine colours in l1
6. move the remaining pixels to l0

That's it! Now note the following facts:
- every cell with two different colours has at least one colour in l1
- there are seven colours in l0

The first fact ensures that l1 suffices to create a real hires resolution. The second fact helps to argue why l0 can be constructed within normal multi-colour-gfx restrictions. How? For this, we distinguish between two situations:
1. assume that there is at least one cell with both colours in l1
-> in this case the l0-pixels of this very cell are hidden
-> thus, three colours (which can be handled by vram and d8xx) suffice for l0 in this char as there are always only four cells per char
-> the other two chars give eight cells in total; as there are only seven colours in l0, at least one of these colours MUST repeat
-> this colour can be handled by the bgr-colour

2. all cells (with different colours) have only one pixel in l1
-> the other pixel must be in l0
-> choose such a cell and move the l1-pixel to l0
-> move all pixels of the same colours to l0
-> move all pixels of another l1-colour to l0
-> now swap the roles of l0 and l1, i.e. let l0 be the new "foreground layer" and l1 the new "background layer"
-> after this, the new fg layer l0 has nine colours and there is at least one cell with both colours in l0
-> we now have the same situation as described under 1.


Next step would be implement a test code for this (or even for more fancy stuff like 200 lines of the mode;))

@Digger, Oswald: I doubt it will be possible to do some lookup-table stuff with a 24x200-windowed version of this mode; I'd be happy to see a logo done with it, though;)
2015-02-22 23:44
Copyfault

Registered: Dec 2001
Posts: 478
Quoting ChristopherJam
Dane, I did some experiments with an offset-by-one MCM sprite layer under the foreground of an MCM character mode layer a year or two ago. I was getting very nice results from a mode-aware dither routine, but all of my sources were photographs - I didn't really want to release anything that was just a conversion of someone else's 24 bit or greyscale artwork.

If I get my shit together I'll hopefully release some real artwork of my own later this year.

Glad this thread's provoked some thought, in any case :)


I'd sure like to see these experiments from both of you, Dane and Christopher Jam ;) Back in the days (when "IFLI-Convertors and friends" were new) a series of converted photos was a good reason to release a GFX Collection.

But it was all about this saying "good things come to those who wait", no ;) ?
2015-02-22 23:48
Copyfault

Registered: Dec 2001
Posts: 478
Quoting algorithm
...
However, I feel that even with some restrictions in place, the difference in output at a wider width would be negligible dependant on how the converter creates the image and sprite definitions.

Have a look at the mucsu-fli mode for example, having full width FLI with sprites over 240 pixel range (albeit blocky) but underlaid with hires masking. Copyfault I believe updated the routine to work at full 200 vertical lines.


Yes, thanks for advertising! It can be seen in The Other Lines.
2015-02-23 21:05
ChristopherJam

Registered: Aug 2004
Posts: 1409
Hi Copyfault.

I mostly follow.

Certainly that an L1 with nine colours over a MC res L0 follows from the first section of one of my earlier comments in this thread (#27)

And I can see that any pixel of L0 containing colours from L1 can be promoted to an L1 pixel, leaving only seven colours required for L0.

Your case 1 logic makes sense, assuming we can freely position the nine colours in L1.

However, there are some odd restrictions on L1 to allow it to contain nine colours, namely that two of them are sourced from a multicolour sprite - hence, those colours need to be paired either with another L1 colour, or with a FG colour from L0

I covered that in comment #27 by only using those colours in even pairs.

I think that the odd-pair exclusion might sometimes be broken if we apply your rule of always promoting l0 pixels to l1 if they are one of the nine l1 colours, so it looks like a different way of allocating the MC colours might be required.

As for case 2, I'm struggling to track the invariants across the layer inversion at the moment; will have to ponder that one further!

Definitely interested in test code for this one. My brute-force search has yet to fail, but it's probably too slow to use in a native editor.
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
csabanw
iAN CooG/HVSC
algorithm
Guests online: 108
Top Demos
1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.7)
4 Coma Light 13  (9.6)
5 Edge of Disgrace  (9.6)
6 What Is The Matrix 2  (9.6)
7 The Demo Coder  (9.6)
8 Uncensored  (9.6)
9 Comaland 100%  (9.6)
10 Wonderland XIV  (9.6)
Top onefile Demos
1 No Listen  (9.6)
2 Layers  (9.6)
3 Cubic Dream  (9.6)
4 Party Elk 2  (9.6)
5 Copper Booze  (9.6)
6 Dawnfall V1.1  (9.5)
7 Rainbow Connection  (9.5)
8 Onscreen 5k  (9.5)
9 Morph  (9.5)
10 Libertongo  (9.5)
Top Groups
1 Performers  (9.3)
2 Booze Design  (9.3)
3 Oxyron  (9.3)
4 Triad  (9.3)
5 Censor Design  (9.3)
Top Fullscreen Graphicians
1 Joe  (9.7)
2 Sulevi  (9.6)
3 The Sarge  (9.6)
4 Veto  (9.6)
5 Facet  (9.6)

Home - Disclaimer
Copyright © No Name 2001-2024
Page generated in: 0.109 sec.