Jump to content
  • Advertisement
Sign in to follow this  

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.

If you intended to correct an error in the post then please contact us.

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!))


Share this post

Link to post
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 this post

Link to post
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

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!