AuthorTopic: I'm making a paint program, so useful tools, ideas and features required please  (Read 156486 times)

Offline Ai

  • 0100
  • ***
  • Posts: 1057
  • Karma: +2/-0
  • finti
    • http://pixeljoint.com/pixels/profile.asp?id=1996
    • finticemo
    • View Profile
Ah! That's much clearer. Sounds very interesting, not sure how users would go about selecting the ramp 'values' though.
If you mean priorities, in the example, the user didn't need to assign any, they were automatically assigned by a variant of a plasma algorithm.
The way the algorithm works is IMO demonstrated completely by the pattern of colors becoming available as priority raises

Of course, to get full benefit of the power provided, the user might need to do such adjustments. One way, inspired by the way my Pixlab library allows extra channels, is to treat these values as extra channels, and allow the user to switch from RGB selection to HSV selection to P??  * selection. P channel could also optionally be used to determine the importance of colors in color reduction (with 0 being most important)

(presumably ? ? would be letters representing other channels, i'm sure there are some)

OTOH, if you mean adjusting the current active priority, I envisioned that bound to shift+{] or ctrl-[].
« Last Edit: December 31, 2008, 06:06:32 am by Ai »
If you insist on being pessimistic about your own abilities, consider also being pessimistic about the accuracy of that pessimistic judgement.

Offline Ai

  • 0100
  • ***
  • Posts: 1057
  • Karma: +2/-0
  • finti
    • http://pixeljoint.com/pixels/profile.asp?id=1996
    • finticemo
    • View Profile
Ai's ramp stuff inspired this idea: a palette-tool/colour-select-mode which extracts all possible/practical ramps from the palette within given thresholds. Could also be a handy tool for testing the development of generic palettes.
This is possible -- I've tried it! It's quite demanding in terms of making a system that does it well.
Some things it needs:

 * sane color system (standard sRGB is right out. so is linear RGB, probably, and of course so is HSV/HSL/HWB/what-have-you-variant of hue-something-something. XYZ might be possible, I know LAB works, and LCH might work even better, YCbCr or YiQ might have some value (I haven't really played with them much))

 * graph algorithms. Essentially, we are building a graph with colors as nodes, and each node connected (directionally) to every other node which satisfies the threshold. We then need to iterate through the graph with the constraint that we move monotonically (ie. either always brighter, or always darker). The iteration is like iterating over multiple trees, and each subtree produces multiple output ramps.

EDIT: actually, we only ever need to move in one direction (say brighter). We can just store the output in reversed order if the user wants that.

 * a reasonable display method. Even for quite small numbers of source colors, the number of output ramps can become quite large.
    Might be helpful to partition the ramps (eg ramps including color1, ramps including color2, ramps 3..5 entries long, ramps 4..8 entries long..)
   
For example, supposing you have a simple single ramp of length 4. the number of ramps of length >=2  equals 2**4 - (4  + 1) = 11 including the original ramp. Supposing instead that you have 4 ramps of length 4 in which every color in a given position is similar enough to the neighbouring colors that it can be between any two colors, this is (calculated through brute-force with my function iterate_ordered_permutations:) 608 ramps totalling 1996 entries, with 256 of those ramps having the full 4 colors per ramp (also 256 of the ramps have 3 colors, and the remaining ramps of length 2 number 96).

This is actually close to an best-case. I've calculated some statistics using a graphing library, and with a set of 16 colors randomly assigned intensities 0..32,  the total number of entries in the result ranges from 10000 to 26623 entries (65535 being the maximum for an input set of 16 colors -- (2**16) - 1) with about 120 edges in the graph on average.

With a threshold of 2 (that amounts to 1/16th of total intensity, which implicitly limits ramp length to <= 16) we get from 3167 ... 13823 entries,  with average 111 edges.(There are more possible ramps as the ramps become longer, btw.. so the largest ramps occupy most of that space.). doubling it to 4 (1/8th of total intensity, limiting ramp length to <= 8) produces 539 .. 1439 with average 96 edges

threshold = 6 (effective max ramp length == 5) produces 259...923 entries with average 82 edges. This is approaching the realm of reasonableness.

Now, lets see what happens when I increase the number of source colors by 1.    384..881 entries, avg 88 edges
If I double the number of source 'color's to 32 (and double the threshold to compensate),    2552... 4979 entries, avg 330 edges
If I reduce threshold to 4 (4/64 intensity step, max ramp len = 16), we get : 354815 ... 1892735 entries, avg 450 edges.
With threshold = 5 (5/64 intensity step, max ramp len = 13), we get : 148031 ... 602111 entries, avg 440 edges.


We should divide these figures by about 3, since the threshold would most likely be expressed in units of delta-E
http://www.colorwiki.com/wiki/Delta_E:_The_Color_Difference#Delta-E_1976 which will involve three criteria (each of the LAB color channels)

and these figures are still fairly ludicrously large after that. You're only safe from being overwhelmed if you're looking for a short ramp (<= 6 colors), since for each increment of ramp length, number of possible ramps balloons hugely.
One good point is that it's computationally undemanding for typical numbers of input colors: we must compare all colors with all other colors to create the graph; with 256 input colors this is only 32640 color comparisons. then we must iterate through all nodes recursively, rejecting paths that are only one point long, and storing paths as they terminate (or as we finish processing a branch node, we store the path leading up to it but no further). This may require 2 * sum_of_path_lengths (the often huge number I've calculated several times above, eg. 148031..602111) bytes of memory.

EDIT:
I have an algorithm to do this. It does everything except actually store the results -- currently it just counts tree sum_of_path_lengths by accumulating the lengths of all subpaths.
The color comparison/thresholding and building the graph is trivial.
the current implementation of path length calculation looks like:

Code: [Select]
def lengths (graph, node):
    """Return the lengths of the paths originating at node.
   
    Graph must not be circular.
    """
    successors = graph.successors (node)
    count = 1
    if len (successors) == 0:
        return 1 # just ourself
    for succ in successors:
        count += lengths (graph, succ)
    return count
Then the overall counting code just sums the result of calling this on every node (omitting nodes that have no successors, ie. length = 1).
with a slight change of parameters, this could be readily adapted to store results.



This idea needs more work. Perhaps by specifying colors that must be in the output ramp, you could reduce the number of outputs sufficiently.


One other thing -- a sample colorization would be essential for previewing ramps. Using some carefully-picked grayscale images to demonstrate what the ramp will look like.

Quote
  • Having to box select each tile to copy, even aided by grid snapping, was annoyingly inefficient. The simplest of mockup tools would be two hot-key invoked commands: copy-grid-box-under-cursor, paste-to-grid-box-under-cursor. Maybe also with a size option to work with multiple tile features.
Thanks for mentioning this!!!
It inspired this idea for tile reorganization, where you can click on a number of tiles to copy them collectively.
(sort of like a tilemap-chunk brush)
« Last Edit: December 31, 2008, 09:33:19 am by Ai »
If you insist on being pessimistic about your own abilities, consider also being pessimistic about the accuracy of that pessimistic judgement.

Offline happymonster

  • 0010
  • *
  • Posts: 455
  • Karma: +0/-0
    • View Profile
Thanks guys! Some good ideas here which sadly I haven't got time to respond to (off to work today). I already had planned to do something like a tile copy mode which would be VERY useful I think.

As for the saturation, I'm still trying to find a balance, and I'm sure things will change. But I think it is looking better every time I do a visual redesign (compared to the earlier screenshots). :)

Offline surt

  • 0011
  • **
  • Posts: 570
  • Karma: +0/-0
  • Meat by-product
    • not_surt
    • http://pixeljoint.com/p/2254.htm
    • View Profile
    • Uninhabitant
My insufficently thought out and untested (so almost certianly fubar) very-high-level algorithm for ramp extraction:
  • Use the user specified thresholds to perform similarity clustering (should have this already anyways for the clustered palette view).
  • Build a tree rooted on each cluster.
  • Then for each node create children based on thresholds and curve-fitting (probably just within a error of linear should be fine for most purposes) using cluster bounds. Guts go here.
  • Then from any/all cluster sequence construct a ramp or ramps fitting the user selected criteria (most even distribution, smoothest sequence, best fit per cluster, etc.).
  • For more complex ramp curves (think piecewise linear splines) construct them in a seperate pass or interactively with bidirectional construction trees.
  • Option for fixed-width or linearized ramp display (dithering optional).
  • For practical operation would probably be far to slow to be usable in real-time, so it'd probably need to be maintained in a parallel process, marking as dirty and partially rebuilding on each palette change.

Idea: if you've got a massive list of ramps to wade through something nice to have could be a "scratch palette" to which the user can dump ramps/colours they are currently working with for easy access.

Thanks for mentioning this!!!
It inspired this idea for tile reorganization, where you can click on a number of tiles to copy them collectively.
(sort of like a tilemap-chunk brush)
Thanks for mentioning this!!!
It inspired this idea for tile reorganization, where you have a "smart" tileset reordering tool.
It acts like any standard list view widget, allowing drag-and-drop reordering and cutting-and-pasting of individual ranges tiles and ranges of tiles within the tileset image.
Add tile flow direction options to grid settings and your just about done with the gui for it.
Also add an option to let you maintain tile indices when resizing the tileset image would make the tool more complete.

Ai's recursive ramp subdivision idea and my morphological interface painting idea could work nicely together, so that on each stroke auto pick the mid-point colour in the ramp between the two interfacing colours (interface nearest to cursor position, only search within brush bounds).

A matter of taste: square swatches in the palette (option would be nice).

Another small idea: in tile editing mode, option to filter palette by colours in the tile (and get colour count for tile).
« Last Edit: December 31, 2008, 09:12:54 am by surt »

Offline Ai

  • 0100
  • ***
  • Posts: 1057
  • Karma: +2/-0
  • finti
    • http://pixeljoint.com/pixels/profile.asp?id=1996
    • finticemo
    • View Profile
My insufficently thought out and untested (so almost certianly fubar) very-high-level algorithm for ramp extraction:
  • Use the user specified thresholds to perform similarity clustering (should have this already anyways for the clustered palette view).
  • Build a tree rooted on each cluster.
  • Then for each node create children based on thresholds and curve-fitting (probably just within a error of linear should be fine for most purposes) using cluster bounds. Guts go here.
  • Then from any/all cluster sequence construct a ramp or ramps fitting the user selected criteria (most even distribution, smoothest sequence, best fit per cluster, etc.).
  • For more complex ramp curves (think piecewise linear splines) construct them in a seperate pass or interactively with bidirectional construction trees.
  • Option for fixed-width or linearized ramp display (dithering optional).
  • For practical operation would probably be far to slow to be usable in real-time, so it'd probably need to be maintained in a parallel process, marking as dirty and partially rebuilding on each palette change.
That certainly cuts down the amount of ramps to sort through. OTOH, you've traded visual quantity for user interface complexity,
which is something I'm fairly leery of. After I wrote my post before, I thought it would be better to offer iterative revision... that is, start out offering the user 2-color ramps; if they like one, they can click on it and progress to seeing 3-color ramps related to it.. then 5-color,...
(and I guess right-click to back up if they think they made a bad choice)
IMO this avoids both issues by offering the user only a meaningful amount of choice, and iterative-revision interfaces in my experience are very fast and obvious to use. It also exploits the fact that short ramps are the least numerous in any possible set of ramps.

GIMP 'filter pack' plugin has a good example of the kind of UI I mean.
http://docs.gimp.org/en/plug-in-filter-pack.html  (see figure 15.202)


Also, your algorithm is sort of like a bastardized octree quantization implementation in it's basis :),  so you might want to check out
http://en.wikipedia.org/wiki/Octree
(SciPy (www.scipy.org) also has clustering and vector-quantization tools which are good for prototyping this kind of algorithm, including a K-d tree implementation which is a generalization of an octree.)

Using octrees can make this kind of quantization very fast, actually. A majority of color reduction algorithms use octrees.
Quote
Idea: if you've got a massive list of ramps to wade through something nice to have could be a "scratch palette" to which the user can dump ramps/colours they are currently working with for easy access.
Thanks for mentioning this!!!
It inspired this idea for tile reorganization, where you can click on a number of tiles to copy them collectively.
(sort of like a tilemap-chunk brush)
Thanks for mentioning this!!!
It inspired this idea for tile reorganization, where you have a "smart" tileset reordering tool.
It acts like any standard list view widget, allowing drag-and-drop reordering and cutting-and-pasting of individual ranges tiles and ranges of tiles within the tileset image.
Add tile flow direction options to grid settings and your just about done with the gui for it.
actually that's weird, cause I thought of that and then I thought .. 'but how would you get it to not f*** up the order of the existing tiles?'
The flow options address that nicely (you'd need two, I think.. one for x axis flow and one for y axis flow? not completely clear here)
Quote
Also add an option to let you maintain tile indices when resizing the tileset image would make the tool more complete.

Ai's recursive ramp subdivision idea and my morphological interface painting idea could work nicely together, so that on each stroke auto pick the mid-point colour in the ramp between the two interfacing colours (interface nearest to cursor position, only search within brush bounds).

A matter of taste: square swatches in the palette (option would be nice).

Another small idea: in tile editing mode, option to filter palette by colours in the tile (and get colour count for tile).
« Last Edit: December 31, 2008, 10:43:27 pm by Ai »
If you insist on being pessimistic about your own abilities, consider also being pessimistic about the accuracy of that pessimistic judgement.

Offline happymonster

  • 0010
  • *
  • Posts: 455
  • Karma: +0/-0
    • View Profile
Interesting discussion, even if it's over my head! :P But have fun guys, rock the world! ;)

I looked at the screenshot of Pixe at work and it seems very dark on that monitor. Looks like that Gamma was different than on my machine. Does it appear too dark for everyone else? (I know that's rather subjective!)

BTW: Have a great New Year! :D

Offline surt

  • 0011
  • **
  • Posts: 570
  • Karma: +0/-0
  • Meat by-product
    • not_surt
    • http://pixeljoint.com/p/2254.htm
    • View Profile
    • Uninhabitant
That certainly cuts down the amount of ramps to sort through. OTOH, you've traded visual quantity for user interface complexity,
which is something I'm fairly leery of. After I wrote my post before, I thought it would be better to offer iterative revision... that is, start out offering the user 2-color ramps; if they like one, they can click on it and progress to seeing 3-color ramps related to it.. then 5-color,...
(and I guess right-click to back up if they think they made a bad choice)
IMO this avoids both issues by offering the user only a meaningful amount of choice, and iterative-revision interfaces in my experience are very fast and obvious to use. It also exploits the fact that short ramps are the least numerous in any possible set of ramps.
I don't see why the interface need be any more complex than a few selection criteria and a list to scroll through. While I don't personally like the idea of an iterative refinement interface for this (I just want a palette of ramps) theres no reason you couldn't use one to refine the thresholds.

actually that's weird, cause I thought of that and then I thought .. 'but how would you get it to not f*** up the order of the existing tiles?'
The flow options address that nicely (you'd need two, I think.. one for x axis flow and one for y axis flow? not completely clear here)
Well flow direction for each axis as well as axis priority so that's three options to be complete.

I looked at the screenshot of Pixe at work and it seems very dark on that monitor. Looks like that Gamma was different than on my machine. Does it appear too dark for everyone else? (I know that's rather subjective!)
Intensity looks fine to me, but then I'm a darkness-fancier. Just the saturation AFAIC.

Offline happymonster

  • 0010
  • *
  • Posts: 455
  • Karma: +0/-0
    • View Profile
Quote
Intensity looks fine to me, but then I'm a darkness-fancier. Just the saturation AFAIC.

Actually I've refined the design somewhat, and altered the saturation slightly. Unfortunately my stupid webhost is down, else I'd post a screenshot.
Suffice it to say I think I've improved things and I've incorporated your suggestion Surt for a row of Layer 'icons' above the canvas. I can fit 20 - 32 x 32 icons in there and 4-5 layer tool icons in a 1024 width window/screen mode. So that's quite nice.. :)

If my webhost comes back online I'll post a pic.

Offline happymonster

  • 0010
  • *
  • Posts: 455
  • Karma: +0/-0
    • View Profile
Here's Pixe (my version, not uploaded yet), running in maximum windowed size in a screenmode of 1280 x 1024:
http://www.funkemunke.com/Pixe_12.png

I think it's taking shape. :)
« Last Edit: January 01, 2009, 04:51:28 pm by happymonster »

Offline surt

  • 0011
  • **
  • Posts: 570
  • Karma: +0/-0
  • Meat by-product
    • not_surt
    • http://pixeljoint.com/p/2254.htm
    • View Profile
    • Uninhabitant
Saturation level is better, but I still think it could be turned up just a touch.

Palette tools above the palette is an improvement and more consistent with the rest of the gui.

I'm curious to see how the layer bar will pan out, and also have an idea for an animation interface to go with it (I'll post a mockup once I've got a more fully featured screen to hack up as I probably can't explain it very well textually).

Good stuff.

EDIT:
Talking about specialized tilemap tools earlier, this might be another good use to put the secondary pane to.
Have the standard image view in one pane (or better yet a dedicated tile list view/mode/tool/whatever) with the ability to select a tile from the image which is then displayed/edited in the other pane as though a discrete image (with of course options for tiled view and wrapped editing).
Could also be used for irregularly sized sprites (using the usual methods of extraction: from regions bounded by a key colour or defined in an external text file or, better yet, defined in app).
« Last Edit: January 02, 2009, 05:11:21 am by surt »