How do I generate random points in 3D space?

Question

The biggest problem I am having is that I do not have the vocabulary to describe what I am after so if nothing else, some help with that would be much appreciated.

From what I understand, Perlin noise can give you a random value for a point in 3D space and in addition any nearby points will have values that are similar. I have this working in a program to generate 3D blobs floating in space when the random value passes a certain threshold. This works well because I can pick any point, and without worrying about what points were calculated before, determine its value (could thread the blob generation if I wanted).

I now want to do something similar except, I want to change the color of that point on the blob if the random value passes a certain threshold. However I want this to be random and unrelated to its neighbors (unlike Perlin noise).

What kind of algorithm am I looking for to accomplish this?

The key criteria:

1. The function takes a 3D vector as a parameter.
2. The values are totally unrelated from point to point.
3. The order examining points does not affect the results of the function.
4. The function returns the same result if the same point is passed to it.

Outcome

So I decided to use an approach similar to the answer by Kahler with some very small tweaks. I didn't want to use all the redirection and operations used by repeatedly instantiating or even just repeatedly seeding a random number generator. I ended up copying the random number generator used in the UE4 RandomStream class and making it fit my needs. I'm sure this generator is not theirs alone, as the numbers used seem to appear in other places, but that is where I found it.

float WhiteNoise::GetNoise3D(const FVector& vector) const
{
    int32 s1 = seed;
    int32 s2 = ((s1 + FMath::TruncToInt(vector.X)) * 196314165) + 907633515;
    int32 s3 = ((s2 + FMath::TruncToInt(vector.Y)) * 196314165) + 907633515;
    int32 s4 = ((s3 + FMath::TruncToInt(vector.Z)) * 196314165) + 907633515;

    const float tmp = 1.0f;

    float result;

    *(int32*)&result = (*(int32*)&tmp & 0xff800000) | (s4 & 0x007fffff);

     return FMath::Fractional(result);
}

There are some obvious issues with the above code. One being that the numbers are not very random and the other being the truncation causing a granularity issue. Both of those are totally acceptable in my situation so this works reasonably well.

Answer 1

If the function returns the same number each time the same parameter is passed in, it's not a random function. To get an apparently random pattern without saving the exact result of each point, you can use a random generator with seed dependent on position.

Something like

value_t get_value(coord_t x, coord_t  y, coord_t z)
{
    seed_t seed = some_equation(x,y,z);
    return generate_random_with_seed(seed);
}

C++ now has the <random> library, you will have to tune the equation to give satisfactory results.And they will be repeated each time the seed repeats, with apparent random pattern, every call. One possible seed generator is spreading all possible discrete possibilities over the type of the seed, as equals seeds means equal results.

(so a 256x256x256 grid could use the seed (x*256*256 + y*256 + z)

This strategy actually maps an ordered set to an apparently unordered set. The output will be related to the position by the random generator operation on the seed.

As the requirements for unique seeds can become quite cumbersome, you can also get repeatable results by spliting your volume on smaller ones, each consisted of N-points, and the whole chunk share the same unique seed, the random value of the i-th element is the i-th run of the random generator with the chunk seed.

This will reduce the requirement of unique seeds by a factor of N, but increase the average retrieve operations by a factor of (N-1)/2.

A while ago, I've tried several of the <random> distributions, here's some code that shows ~graphical~ output (the comments are in portuguese, but the code is simple).

You probably will want an uniformly random variable for the threshold, here's an online reference to uniform_int_distribution.

Answer 2

Taking a slightly different approach than the excellent answer above by Kahler, i wonder if you simply search for a way to change numeric space.

In this context, one could say that a random number exists in a one-dimensional numeric space. ie. integer values from 0 upwards and downwards are available.

A randomly generated 32-bit integer has to be between 0 and 4294967295, ie. you have 4294967296 possible unique numbers. However, if you "consume" that random number in for example a 2-dimensional space (a "grid", as we say), then your grid size will be the 2nd root of 4294967296, which is 65536. Meaning you have 65536 by 65536 possible "slots" that can randomly be either 0 or 1 (but the random number distribution will match that grid fully).

If you consume the random integer in a 3D space, you face the 3rd root of 4294967296, which is ca 1625. Ie. grid size is ca 1625x1625x1625 slots (could also say "cells").

As you see here, 1625 is not much, and the implication being this: IF you happen to maintain a space using 32-bit floats for XYZ-positions (maybe a space game? You don't mention), then you address the space using 96 bits - or even worse, 192 bits if addressing with doubles - while you generate the random number in only 32-bit space. This means that there will either be a repetition or a roughness (a "bad granularity") in the mapping between the numeric spaces. It's hard to predict exactly how you will experience this. You will however only have 1625 possible x-positions.

(Nevertheless, it IS possible to change a random number from 1-dimensional space to 3-dimensional. It's simple, in fact. Generate the number, grab it's boolean representation (binary, the bits). Then simply take the first 11 bits and construct an integer from those; use it for position.x. Then do the same with next 11 bits and use for position.y. The z-position gets only 10 bits... hm - oh well :-).)

Using seed is unrelated to this. The seed makes the random generation repeatable, and that's still fully possible by Kahlers description.

Now to the potential problem:

• If you "isolate" this things to blobs (with internal 3D-postion addressing, from which you inherit the seed), then there is a fear that your random generation will be repeating from blob to blob. All blobs will get identical appearance.

• If you, on the other hand, use a global, huge coordinate addressing for your seed, then you may get bad granularity among the random numbers in the individual blobs (eg. only 1625 possible positions along one direction, kind of).

Hard to say, but you might end up with visually unsatisfactory results. I'd propose generating not one random number at time, but 3, one for each direction. You can still determine if it was a hit or not (your "threshold") - but just process the check using the triplets of individual random numbers AND use your world (global) positioning system for each of the individual seeds.