# uniform random point inside a triangle

18 replies to this topic

### #1Grasspuppet

New Member

• Members
• 2 posts

Posted 25 July 2007 - 12:51 AM

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

### #2Reedbeta

DevMaster Staff

• 5340 posts
• LocationSanta Clara, CA

Posted 25 July 2007 - 06:18 AM

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.
reedbeta.com - developer blog, OpenGL demos, and other projects

### #3anubis

Senior Member

• Members
• 2225 posts

Posted 25 July 2007 - 07:12 AM

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
If Prolog is the answer, what is the question ?

### #4hovermonkey

Member

• Members
• 38 posts

Posted 25 July 2007 - 09:42 AM

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; }

### #5Reedbeta

DevMaster Staff

• 5340 posts
• LocationSanta Clara, CA

Posted 25 July 2007 - 04:37 PM

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:
reedbeta.com - developer blog, OpenGL demos, and other projects

### #6anubis

Senior Member

• Members
• 2225 posts

Posted 25 July 2007 - 06:10 PM

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
If Prolog is the answer, what is the question ?

### #7Jare

Valued Member

• Members
• 247 posts

Posted 26 July 2007 - 06:49 AM

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.

### #8anubis

Senior Member

• Members
• 2225 posts

Posted 26 July 2007 - 07:32 AM

With the rejection method you will probably also run into problems if you use stratified sampling
If Prolog is the answer, what is the question ?

### #9Reedbeta

DevMaster Staff

• 5340 posts
• LocationSanta Clara, CA

Posted 26 July 2007 - 04:41 PM

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...
reedbeta.com - developer blog, OpenGL demos, and other projects

### #10anubis

Senior Member

• Members
• 2225 posts

Posted 26 July 2007 - 11:16 PM

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
If Prolog is the answer, what is the question ?

### #11tobeythorn

Valued Member

• Members
• 189 posts

Posted 29 July 2007 - 07:23 PM

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.

### #12Reedbeta

DevMaster Staff

• 5340 posts
• LocationSanta Clara, CA

Posted 30 July 2007 - 02:12 AM

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...
reedbeta.com - developer blog, OpenGL demos, and other projects

### #13krafty

New Member

• Members
• 13 posts

Posted 01 August 2007 - 07:06 AM

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

### #14Kenneth Gorking

Senior Member

• Members
• 939 posts

Posted 01 August 2007 - 02:25 PM


// 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;



"Stupid bug! You go squish now!!" - Homer Simpson

### #15Grasspuppet

New Member

• Members
• 2 posts

Posted 07 August 2007 - 04:46 AM

Thanks a bunch!!!

### #16Kenneth Gorking

Senior Member

• Members
• 939 posts

Posted 07 August 2007 - 11:12 AM

Here is a link to a page describing the disadvantages concerning the use of rand(), and some solutions to it: Misconceptions about rand()
"Stupid bug! You go squish now!!" - Homer Simpson

### #17rouncer

Senior Member

• Members
• 2755 posts

Posted 08 October 2007 - 10:18 AM

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

### #18rouncer

Senior Member

• Members
• 2755 posts

Posted 08 October 2007 - 10:28 AM

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.

### #19.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 08 October 2007 - 11:09 AM

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.