18 replies to this topic

[Grasspuppet]

Hi,

Can someone please help? I want to be able to pick a random point within a triangle facet in 3-space. Selection is weighted for equal probability per unit area. The only thing that is given is the vertices and normal. I am stuck at this stage of my code and have no idea how to solve this problem. Any help is much appreciated.

Thanks

[Reedbeta]

Choose two random numbers between 0 and 1. They form a random point in the unit square. If the sum of the two numbers is greater than 1, discard them and choose another pair (and repeat until you get one with sum <= 1). You now have a uniformly distributed random point in the triangle (0,0), (1,0), (0,1) in 2D. Now just multiply the point by the edge vectors of your 3D triangle and add to them the vertex of the 3D triangle from which the edge vectors originate. Presto, you have a uniformly distributed random point on your triangle.

[anubis]

Sample the unit square ( two samples u,v in [0;1] ) and apply this to the samples :

   float tmp = sqrt(u);

   x = 1 - tmp;

   y = v * tmp;

x and y are now barycentric coordinates in your triangle.

If I find the time I will post an explanation later today. Have to go to work now

[hovermonkey]

Reedbeta: no need to discard your numbers if they sum to >1. If your numbers are x,y just do

 if (x+y > 1) { x = 1-x; y = 1-y; } 

[Reedbeta]

hovermonkey: yes, I am aware of that approach, but it makes the mapping discontinuous (since widely separated x,y points can map to close points on the triangle) and that can cause problems depending on the technique you use to generate your random numbers.

anubis, I haven't seen that mapping before. Nice one :yes:

[anubis]

Quote

anubis, I haven't seen that mapping before. Nice one

You arrive at that mapping if you compute one of the marginal densities p(u) or p(v) and the corresponding conditional density, knowing that p(u,v) = 1 / area

[Jare]

Reedbeta said:

hovermonkey: yes, I am aware of that approach, but it makes the mapping discontinuous (since widely separated x,y points can map to close points on the triangle) and that can cause problems depending on the technique you use to generate your random numbers.

I don't understand the problem, could you elaborate?

My only beef with that mapping is that the points where x+y = 1 has half the chances to appear in the triangle as any other point, therefore the distribution is not perfectly uniform.

[anubis]

With the rejection method you will probably also run into problems if you use stratified sampling

[Reedbeta]

Jare said:

I don't understand the problem, could you elaborate?

I'm not 100% sure of the details myself, but true random numbers tend to have a lot of "clumping", which tends to increase the variance in a Monte Carlo process. That's why it's common to use things like stratified sampling or low-discrepancy sequences which attempt to produce a "better than random" distribution, i.e. with no visible regularity, but not so much clumping either. The trouble is that discontinuous mappings spoil these attempts by reintroducing clumping, since two random samples with values far apart can map to values close together.

I think Pharr and Humphreys talk about this some more in the PBR book, if you're interested in finding out more.

Quote

My only beef with that mapping is that the points where x+y = 1 has half the chances to appear in the triangle as any other point, therefore the distribution is not perfectly uniform.

The points where x + y = 1 are a line, which technically should have probability 0 anyway...

[anubis]

Quote

I think Pharr and Humphreys talk about this some more in the PBR book, if you're interested in finding out more.

That is actually were I first learned about the mapping I gave :D

[tobeythorn]

The sum of the angles between the vectors from a point to the the points on a triangle and the respective triangle edges must equal pi radians. using this, and the plane of the triangle, you could pick 2 random angles between 0 and pi that add to not exceed 180. Basically, trilateration. No need to throw any numbers away! Reedbeta is right about random number generators not being random.

[Reedbeta]

tobeythorn said:

The sum of the angles between the vectors from a point to the the points on a triangle and the respective triangle edges must equal pi radians. using this, and the plane of the triangle, you could pick 2 random angles between 0 and pi that add to not exceed 180. Basically, trilateration. No need to throw any numbers away! Reedbeta is right about random number generators not being random.

That doesn't give a mapping with constant probability density with respect to area though...

[krafty]

you will need 2 random numbers
ranged bet [0-1] if both are one, 3rd vertex will be your point, and so on
then, get the point using parametric equation of the triangle.

cheers

[Kenneth Gorking]

// Note: Using rand() will cause points to bunch up in one of the corners.

// Can't remember which one though... You really should use a different random number generator.

inline float randf()

{

    return ( float(rand()) / float( RAND_MAX ) );

}


...


float b0 = randf();

float b1 = ( 1.0f - b0 ) * randf();

float b2 = 1 - b0 - b1;


position = vertex1 * b0

         + vertex2 * b1

         + vertex3 * b2;

[Grasspuppet]

Thanks a bunch!!!

[Kenneth Gorking]

Here is a link to a page describing the disadvantages concerning the use of rand(), and some solutions to it: Misconceptions about rand()

[rouncer]

I read that rand() page.

I think that guy is wrong and the C.L.C site was right,

Heres the CLC fix of the problem rewritten by me with a multiply,
and you should see it works->

(float)rand()/(float)rand_max*(float)range

it simply squishes the number scale, and there is the exact same
amount of random possible samples, but the C.L.C said that it only
works when rand_max is bigger than range (it only has to be 1 integer
lower and it still works) and that is correct but they wrote it like this->

x = rand() / (RAND_MAX / RANGE + 1)

because it works with integer division and it doesnt need a float convert
(its written that way as an optimization) and its the same just with the
inverted divide instead of the multiply.

Am i wrong?

But I didnt even consider that rand()%range didnt work, i just didnt think. :)

[rouncer]

Nah I thought more, and the problem is when
it converts back to integer (or when the integer divide happens)
and then it repeats some samples more than others
like an aliased line.

I guess he is right then, rerandomizing is the only way to
get exact results.

[.oisyn]

Indeed. The fundamental problem is that you can't evenly distribute x numbers over y values when x is not a multitude of y. No matter the calculation, rand() always produces x numbers, and there is no function that maps them to y values, other than throwing away certain numbers.