uniform random point inside a triangle

Fdff7c9e8053e85a41f2d75d8828f8b3
0
Grasspuppet 101 Jul 25, 2007 at 00:51

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

18 Replies

Please log in or register to post a reply.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Jul 25, 2007 at 06:18

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.

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jul 25, 2007 at 07:12

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

64212d89ffc7e91ed54b96ebbe99bd05
0
hovermonkey 101 Jul 25, 2007 at 09:42

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; }
A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Jul 25, 2007 at 16:37

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:

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jul 25, 2007 at 18:10

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

6b7e1a4b42e4b47d92fdef8bf2bd8e2c
0
Jare 101 Jul 26, 2007 at 06:49

@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.

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.

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jul 26, 2007 at 07:32

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

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Jul 26, 2007 at 16:41

@Jare

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.

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…

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jul 26, 2007 at 23:16

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

A77e71b962cd6c7c3b885f0488452f1f
0
tobeythorn 101 Jul 29, 2007 at 19:23

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.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Jul 30, 2007 at 02:12

@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.

That doesn’t give a mapping with constant probability density with respect to area though…

9f9df1f665aee874559e067f73ca7879
0
krafty 101 Aug 01, 2007 at 07:06

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

46407cc1bdfbd2db4f6e8876d74f990a
0
Kenneth_Gorking 101 Aug 01, 2007 at 14:25
// 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;
Fdff7c9e8053e85a41f2d75d8828f8b3
0
Grasspuppet 101 Aug 07, 2007 at 04:46

Thanks a bunch!!! :)

46407cc1bdfbd2db4f6e8876d74f990a
0
Kenneth_Gorking 101 Aug 07, 2007 at 11:12

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

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 104 Oct 08, 2007 at 10:18

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. :)

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 104 Oct 08, 2007 at 10:28

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.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Oct 08, 2007 at 11:09

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.