# Random point inside 3d voxel volume?

This topic is 3030 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Currently making particle system, where emitors shape can be 3d texture.

But generating one point inside volume efficiently gives gray hairs.

Pseudo code:
class VoxelVolume {  private float[,,] volume = new float[32, 32, 32];  public Vector3 OneRandomPointInVolume() {    // total can be pre-calcultated (optimization)    float total = 0.0f;    foreach(voxel in volume) total += voxel;    // now, each points chance is     // (voxel.value) / total    // but what kind of "dice" is neaded to get the result!!!    return result;  }}

Any ideas on how to get one positive that
has chance of points value divided by sum of volume?
(no random shooting algorithms! (bad performance!))

/Tyrian

##### Share on other sites
You should be able to use a random value in the range [0, 1] and a binary search to get the results you want.

Take the simple example of three voxels with volumes 2, 10, 8. The 'selection probability' for each is .1, .5, and .4, respectively.

Arrange these in any array as follows, where each entry is the probability for that voxel plus the sum of the probabilities of the previous voxels, e.g.:

.1, .6, 1

Generate a random value in the range 0, 1. If it's lower than the first value in the array, the first voxel is selected; else if it's lower than the second value in the array, the second voxel is selected; else the last value is selected (in our example, that is).

You can of course determine which voxel is selected with a linear search, but if you have a lot of voxels you may want to use a binary search for efficiency.

(This is assuming that I understand your question correctly. Also, there may be a faster and/or better solution to the problem than what I described above; if so, I imagine someone will suggest it.)

##### Share on other sites

Thank You.

I was stack in thing of data as 3d space. And did forget that in the end
volume data is just 1D line twisted to fill volume of box :D

And if it´s one line, then binary search in summed array gives correct result.

O(N) pre-calcultation + O(logN) runtime is probably best that I can get.

// Tyrian

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633705
• Total Posts
3013463
×