Sign in to follow this  
paic

randomness question

Recommended Posts

Hi, I have a particle system with a few types of emitters. Amongst them, I have an emitter which is like a disc, and I have a problem to create the particles in an "homogeneous" manner on this surface. I use the following method :
float radius = rand(0.0f, maxRadius);
float angle  = rand(0.0f, 2 * PI);

D3DXVECTOR3 position(emitterPos.x + cos(angle) *  radius,
                     emitterPos.y,
                     emitterPos.z + sin(angle) * radius);
With this, I have more density at the center of the disc than at the borders. And I'd like to avoid that. Does anyone know how should I do ?? Thx in advance for any help.

Share this post


Link to post
Share on other sites
Hi,

It's not really a problem with the random function I'm using. I use this function with a quad emitter, and the distribution is good.
The problem comes from the radius / angle values. Let's say I generate half my particles in the range [0 , maxSize / 2] and the other half in [maxSize / 2 , maxSize] The particles in the first range will seem to be really dense, compared with the ones in the second range, simply because the area is smaller when we are close to the center. So I need to take that into account, and I don't know how to do it ^^

(I hope I was clear in my explanations :/)

Share this post


Link to post
Share on other sites
@Dearax - I don't think that that is what is causing his problem.

(please skip if you read the above post, it explains it)What's happening is that you're (obviously) setting the distance from the center and the angle at which the particle is at. But, a circle with radius 10 has a much bigger circumfrence(sp?) than a circle with a redius of 1. So the center has less space to possibly have particles than the outside, making it badly distributed.(stop skipping here)

How could you fix it? Try making radius more likely to be further away than closer. What might or might not work would be to do like so:

float radius = rand(0.0, 1.0);
radius = sqrt(radius);
radius = radius * maxRadius;




Try that. Basically, since sqrt(0) is 0 and sqrt(1) is 1, but sqrt is a bent line instead of a straight line, this makes it more likely to be closer to maxRadius than 0.0. However, its distribution is probably not going to be perfect, but it should at least be better. And this is obviously considerably slower than previously, but if its running on modern computers and there aren't *too* many particles, it should be fine.

Share this post


Link to post
Share on other sites
Yay !
It's so simple, yet it works perfectly fine ^^
rate ++ for you Ezbez, the distribution is now perfectly uniform (at least it looks like, which is what I wanted ^^)

Share this post


Link to post
Share on other sites
Daerax's answer is not the correct solution to this problem.
A mersenne twister will not help with this problem.

The best way I know of to get a uniformly distributed random vector is to generate points that are randomly distributed in a square. Then you simply eliminate those that are not within a circle touching the edges of your square.
This is a commonly used and accepted solution, which I assure you works. It may seem bad having a loop that retries until it get a point in the circle, but in practice it proves to be very very fast. Each iteration has somewhere around 75% chance that the point will be in the circle. I use a 3D version of this in my own particle generator with great success.
Vector2 RandomVector(double len) {
Vector2 result;
double lenSqr;
do {
result[0] = frand();
result[1] = frand();
lenSqr = result.lenSqr();
} while (lenSqr<EPSILON|| lenSqr>1);
result *= len/sqrt(lenSqr);
return result;
}
Adapt this to suit your needs, and please post your modified code when you're done, so that others may also learn from it.

btw, frand needs to be a function for generating a real random number between 0 and 1. It does not have to be any better than the standard linear-congruential generator to get decent results using this technique.

Edit: Crossed posted with the above two posts. Please consider using the above method, or if you are interested in the trig method, similiar to what you were originally using, take a look at section 6.08 of http://www.faqs.org/faqs/graphics/algorithms-faq/ as they show how to do it properly.

No offence intended to you other posters, you certainly tried to be helpful, but you happened to not have researched this exact problem before, like I have.

Edit 2: Okay fine, they say that the trig way is faster than the rejection method, but I found this way to be very fast too, and easier to understand.

[Edited by - iMalc on May 23, 2006 5:36:38 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by paic
Yay !
It's so simple, yet it works perfectly fine ^^
rate ++ for you Ezbez, the distribution is now perfectly uniform (at least it looks like, which is what I wanted ^^)


Technically speaking, your original distribution was perfectly uniform. Your new one is quadratic, which is what you want since the probability density needs to vary continuously with the square of the radius (the density is linear in pi-r-squared).

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalcNo offence intended to you other posters, you certainly tried to be helpful, but you happened to not have researched this exact problem before, like I have.


None taken. However, mine is a simplistic solution that provides better (looking) results than his current program, even if not as good as yours, and requires little mental thought on either my part or Paic's part. No thinking is good. ;)

Share this post


Link to post
Share on other sites
Quote:
Original post by Bregma
Quote:
Original post by paic
Yay !
It's so simple, yet it works perfectly fine ^^
rate ++ for you Ezbez, the distribution is now perfectly uniform (at least it looks like, which is what I wanted ^^)


Technically speaking, your original distribution was perfectly uniform. Your new one is quadratic, which is what you want since the probability density needs to vary continuously with the square of the radius (the density is linear in pi-r-squared).
The new solution is uniform over the area, while the old one had a uniform distribution for the radius and a uniform distribution for the angle. It's also just as uniform as picking points in a square and throwing away unwanted points, but (often) less computationally expensive (having a bound worst case is a good thing).

Share this post


Link to post
Share on other sites
Although the question has already been aswered here's some more info ;)

While ago I was faced with this same problem, though it was more general. I had to generate spherically symmetric data with arbitrary distribution in arbitrary dimensions. This is how I did it:

I generated uniformly distributed random vectors on the surface of unit sphere (or circle). Only easy way of doing this (to my knowledge) is to use N gaussianly distributed random variables and normalize the length to 1. Random variables _have_ to be gaussian as gaussian is the only separable spherically symmetric distrubution. Such random variables can be generated by box-muller transformation (you get two of them with one pair (a,b):

g0 = sqrt(-2*ln(a))*cos(2*pi*b)
g1 = sqrt(-2*ln(a))*sin(2*pi*b)

where a and b are from uniform distribution in (0,1] (thus they can be generated by e.g., rand()). Lets collect random gaussian random variables to a vector:

y = [g0, .. gN]^T, where gk is gaussianly distributed.

and normalize this vector to unit length

z = y / sqrt(y^T*y), now z is uniformly distributed on unit sphere

finally if this vector is multiplied by random variable r which is in range [0,inf)

x = r * z, where x is spherically symmetric with distribution determined
by the distribution of r.

If one operated in 2D (as the case was in this thread), then the uniform distribution is achieved when r = sqrt(l), where l is from uniform distribution. In general, any distribution can be formed. Let p(s) be the distrubution you want the N-dimensional distribution to follow (i.e., the profile of the spherically symmetric distribution).

Depending on the number of dimensions you have to weight p(s) to accomodate the drop in density as the radius gets larger. In 2D you have to weight p(s) with s

pr(s) = s*p(s).

From this one has to calculate the cumulative distribution Fr(l). That means that pr(s) has to be integrated from 0 to l (remember s goes from 0 to inf). Then any wanted distribution can be generated as

x = Fr(l)^-1 * z

where l is uniformly distributed. So in two dimension and uniform distribution

pr(s) = s

and

Fr(l) = int_{0}^l s ds = 0.5 l^2

and thus

x = 2*sqrt(l)*z

and if it is written open as scalars

x0 = 2*sqrt(l)*z0
x1 = 2*sqrt(l)*z1


where z0 and z1 can be calculated from gaussians, but also with sin and cos as the OP did (try this in higher dimensions ;))

All this may seem overly complicated and slow, but most of it is just mind work (i.e., working out the equations). And remember this works in general for any dimensions and is probably atleast equally fast than what iMalc suggested ;)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this