ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
Hello,
I have a black screen and I have to fill with color pixel by pixel.
I would like to do in a pseudo random way, painting pixel after pixel
in a more or less uniform way. What algorithm or sort of code I could
use to get an index that could be from 0 to width * heigth and
that does not repeat (like dodecaphonic music) until it reaches all
values?
I hope I speak clearly :-),
Thanks,
tano
Hello,
I have a black screen and I have to fill with color pixel by pixel.
I would like to do in a pseudo random way, painting pixel after pixel
in a more or less uniform way. What algorithm or sort of code I could
use to get an index that could be from 0 to width * heigth and
that does not repeat (like dodecaphonic music) until it reaches all
values?
I hope I speak clearly :-),
Thanks,
tano
If you want function that takes x and y coordinates, and then returns you random color for pixel (so same pixel will have same color every time), then take a look at "Perlin Noise" or "Simplex noise".
If you want to fill screen in random order, so no pixel gets painted twice, it depends on how big your screen is. You can do this using following methods:
Method 1 (takes hour):
1) store ALL screen coordinates in linear array. Store array size. This will take at least screen_width*screen_height*4 additional bytes of RAM. Which isn't that much.
2) Until array_size is 0
2.1) For every pixel pick random element within 0..array_size-1 range, remeber index.
2.2) Paint this pixel
2.3) Replace element you've picked in 2.1 with last element of array.
2.4) Decrease array size.
2.5) go to 2).
Method 2 (might take day or two to implement):
Recursively partition screen in squares. Screen is divided in squares, where each square contains 4 squares, and for every square information available if square is empty, has empty pixels, or full. This takes 2 bits per square. Or use binary paritions. This will most likely take less additional RAM, but it'll be more difficult to implement, and might require more CPU time. When this tree is ready, keep filling it up using those rules:
1) if square is empty, fill any pixel, and update "fill/empty" information.
2) if square is partially filed, fill any empty pixel, update "fill/empty" information.
3) If square is filled, do not touch it.
create an array of colours (256*256*256 = 16,777,216)
create an array of screen pixels (width * height)
shuffle the array
assign the shuffled colours in order to the screen pixel array or until the pixel array is full
repeat from the shuffle until the screen pixel array is full
Shuffle
repeat for up to the number of elements selecting two at random and swapping them
- create a one-dimensional list of size 'W x H'
- sequence the list from 0 through 'W x H - 1'
- randomize the order of the list (several options, but my lib will do it for you very quickly)
- iterate through the list with 'x = i % W' and 'y = i / W'
- use rand() to come up with a random value each iteration for the color (might need rand() * rand() to get a large enough value)
ta0kira
PS Here's how easily it can be done with my lib (-O3 makes a huge difference with a screen-sized list):
Code:
#include <ta0kira/clist.hpp>void random_fill(unsigned int W, unsigned int H)
{
if (!W || !H) return;
data::clist <unsigned int> pixels(W * H);
data::clist_sequence(pixels);
pixels.random_order();
for (unsigned int I = 0; I < W * H; I++)
{
unsigned int x = pixels[I] % W;
unsigned int y = pixels[I] / W;
//set pixel at '(x, y)' ...
}
}
- create a one-dimensional list of size 'W x H'
- sequence the list from 0 through 'W x H - 1'
- randomize the order of the list (several options, but my lib will do it for you very quickly)
- iterate through the list with 'x = i % W' and 'y = i / W'
- use rand() to come up with a random value each iteration for the color (might need rand() * rand() to get a large enough value)
This is exactly what I meant, but randomizing order of elements will take more time than picking one random element every time.
This is exactly what I meant, but randomizing order of elements will take more time than picking one random element every time.
How do you expect to keep from picking the same one twice? Removal isn't an option unless you use a linked list, but then random access isn't an option. My lib will randomize with about O(N log N) complexity (i.e. merge sort,) which is the same as sorting. I tried it on my computer for a 1280x800 size compiled with -O3 and it took about 0.7s. Sure, some methods of randomizing will take a long time, but sorting-equivalency is pretty good, especially when compared to the complexity of either non-constant-time removal or non-constant-time access.
ta0kira
PS Picking random elements one at a time is randomizing the order, but without a target structure and much less efficient. Sure, it might work to do something like {get random} while (not used); set pixel; (O(N^2)? can't decide*) for the first half, but how long do you think it will take to get the last 10 or so pixels of a 1280x800 screen? 10 pixels is a 1 in 102,400 chance.
P3S I keep going between N log N and N^2 for statistically-likely case of *. For iteration x, I think it must take N/(N-x) + 1 tries, N/x + 1 when reversed (for simplicity,) making the total tries ∫[N/x + 1] dx, or N + N log N tries if statistics dictate truth. Because they don't, this isn't comparable to the O(N log N) complexity of sorting-equivalency, though it might be much better or might be much worse.
How do you expect to keep from picking the same one twice?
Easily. See below.
Quote:
Originally Posted by ta0kira
Removal isn't an option unless you use a linked list, but then random access isn't an option.
No linked lists. I've explained how elements can be removed in 1D array, you should read more carefully, before making assumptions about "trying to hit empty pixel randomly" and etc. Or you could think a bit about problem, because this stuff is really easy. Next time try to understand what people offer before posting reply, ok?
Here is 1D example. Store structs like "struct PixelCoord{int x; int y;};" instead of ints, and you'll make it 2D.
Code:
#include <stdio.h>
#include <stdlib.h>
int randRange(int range){
return rand() % range;
}
int main(int argc, char** argv){
const int initialSize = 256*256;
int *array = new int [initialSize];
int arraySize = initialSize;
for (int i = 0; i < initialSize; i++)
array[i] = i;
while(arraySize){
int index = randRange(arraySize);
printf("%d\n", array[index]);
arraySize--;
array[index] = array[arraySize];
}
delete[] array;
}
I used similar approach for generating labyrinths.
Notice that MAX_RAND might be something around 65536 on some systems (this won't break algorithm, but pixels won't be distributed uniformly), so it makes sense to use better random number generator. Like this one.
Quote:
Originally Posted by ta0kira
My lib will randomize with about O(N log N) complexity (i.e. merge sort,) which is the same as sorting. I tried it on my computer for a 1280x800 size compiled with -O3 and it took about 0.7s. Sure, some methods of randomizing will take a long time, but sorting-equivalency is pretty good, especially when compared to the complexity of either non-constant-time removal or non-constant-time access.
Method I offered required as many iterations, as there are pixels. O(N) complexity. The only thing that will eat time is "rand" function. This problem DOES NOT require advanced techniques like merge sort. By the way, if your lib was supposed only to randomize order of elements, you could do it the same way as I suggested here. Just remember to use better random number generator.
Quote:
Originally Posted by ta0kira
but how long do you think it will take to get the last 10 or so pixels of a 1280x800 screen?
As I said before, you should read more carefully. There are no random factors. Number of operations is fixed. Also I recommend to search for easy/elegant solution before actually trying to solve problem. Shuffling array is slow. Using merge sort to optimize shuffling might be better, but it is still wrong way to do things, because it is optimization of unelegant solution. It's like using handgrenade to kill a fly - it works, but there is another way.
But does not exists a mathematical function that loops through all indexes without repeating
until it walks all the elements? My purpose was that to avoid the construction of a large
array..
Since you wish to have a random allocation of data you'll need to reserve some memory to keep track of either the pixels or the colours that have been allocated.
But does not exists a mathematical function that loops through all indexes without repeating
until it walks all the elements? My purpose was that to avoid the construction of a large
array..
I don't know such function.
In any way, you'll have to construct array - one or another.
Notice that on modern machines memory is not a problem. Array of coordinates (in the way I offered) for 1280x1024 will take 5242880 bytes of ram (x and y coordinates are stored as 16-bit integers). On modern hardware this is small amount of memory. Screen itself takes similar amount of memory (in 32bit mode). If you really want to conserve memory, then you can use "bitset" - i.e. store bit array where each bit is empty if element wasn't returned and is set, and is set if such elements was returned. For 1280x1024 simplest implementation will take 163840 bytes of memory, but searching for empty pixel will be very slow (you'll have to iterate through all elements to find first that wasn't returned, so it'll be simply unusable). To make approach much faster (with somewhat constant time for finding empty pixel), you can add more bitsets which will form binary tree - i.e. top leaf node would indicate if array has bits set, is empty, or all elements we returned, so every leaf will take 2 bits. With "tree approach" all helper structures will take 327680 bytes for 1280*1024 screen, but writing/debugging this might take day or two (I could do it, but I wouldn't do it for free, since I don't need such function now and have no finished stuff with similar functionality). Or you can go further and partition screen as quad tree. This will save more memory (roughly 218453 bytes in simplest case for 1280x1024, or 174297 if quad covers 16 child nodes, not just 4), but will be a bit slower than binary tree and a bit more complicated. Notice that required CPU time increases as memory requirements decrease. So if you want to implement your effect quickly, without spending too much time on it, just use "make array of all coordinates, pull random elements" approach. If you have free time, and strict memory requirements, try partitioning and binary/quad trees.
--EDIT--
You can also lower memory requirements a bit if you'll store pixel index (x + y*screen_width) instead of plain coordinates, and array of initial values is stored as compressed stream of bits. I.e. "pixel index" for 1280*1024 takes 21 bits at most, so if you'll store initial array of screen coordinates as stream of 21-bit integers, not as array of 32bit integers, the whole thing will take only 3440640 bytes of ram, so you'll save 1802240 bytes. This will require writing your custom class/routines for "compressed bit array", because (AFAIK) c++ doesn't provide something like this in STL or standard library.
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.
Advertisement
Oracle Magazine contains technology strategy articles, sample code, tips, Oracle and partner news, how to articles for developers and DBAs, and more. Click Here to receive a complimentary subscription courtesy of LQ.
