| | ChristopherJam
Registered: Aug 2004
Posts: 1370 |
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 |
|
... 25 posts hidden. Click here to view all posts....
|
| | ChristopherJam
Registered: Aug 2004
Posts: 1370 |
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!) |
| | Dane
Account closed
Registered: May 2002
Posts: 421 |
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. |
| | Joe
Registered: Apr 2002
Posts: 224 |
"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... |
| | Copyfault
Registered: Dec 2001
Posts: 466 |
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 ChristopherJamNow, 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. |
| | ChristopherJam
Registered: Aug 2004
Posts: 1370 |
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.. |
| | ChristopherJam
Registered: Aug 2004
Posts: 1370 |
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 :) |
| | Copyfault
Registered: Dec 2001
Posts: 466 |
Quoting ChristopherJamExcellent, 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;) |
| | Copyfault
Registered: Dec 2001
Posts: 466 |
Quoting ChristopherJamDane, 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 ;) ? |
| | Copyfault
Registered: Dec 2001
Posts: 466 |
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. |
| | ChristopherJam
Registered: Aug 2004
Posts: 1370 |
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. |
| Previous - 1 | 2 | 3 | 4 - Next | |
