Archive for the ‘ Random Points ’ Category

## Random Point In a Triangle – Barycentric Coordinates

A real quick lesson on Barycentric Coordinates.  No diagrams right now.  Maybe I’ll come back later and elaborate.  I’m really going to gloss over the details here – just explain how to accomplish the task in a straightforward manner.

So, you want to find the coordinates of a random point in space that exists on the surface of a predefined triangle.  Sounds complicated, but it’s actually not that bad.  We start off like this:

Consider a triangle with points ABC.  Pick any point and then calculate the vectors from that point to the other two points in the triangle.  So, we get vectors AB and ACAB = [Bx - Ax, By - Ay, Bz - Az] and AC = [Cx - Ax, Cy - Ay, Cz - Az].

So we now have two vectors that tell how how to get from point A to the other two points in the triangle.  They tell us what direction to go in and how far.

So, what if we start at point A, go a random percentage along the AB vector, then go another random percentage along the AC vector?  Sounds pretty good, but how do we make sure we stay inside the triangle and don’t exceed our bounds?  This is where Barycentric Coordinates come into play.

Barycentric coordinates are three numbers that add up to one.  Each number stands for a weighting of each point of the triangle.  You can think of 1 as a percentage of the triangle. 1 = 100%.  So, if we say point R weights the triangle 30% and S 50% then T is 20%.  Well, knowing all this doesn’t help us that much right now, except for the concept that R + S + T = 1.  Going over 1 means we are outside the bounds of our triangle.  And, a value of R = 1/3, S = 1/3, T=1/3 means each point has equal weighting, something called the barycenter of our triangle.

Consider a unit triangle in two dimensions.  The point coordinates would be [0,0,], [0, 1], [1,0].  Imagine this as the perfect triangle.  We can also think of this triangle in relation to our 3D triangle, with [0,0] representing our point A.  In other words we can remap the values of one triangle to another, or use these barycentric weightings to weight our distance vectors accordingly.

We’ll simply start by choosing two numbers at random between 0 and 1.  Each number should be seeded differently to make sure we don’t end up with the same number.

Now, we need to check if they are larger than one, since we still need to account for the third number and want to make sure we stay inside our triangle.  If they are, all we have to do is subtract them from one.  Something like this:

R = random.Get01(); //Generate a random number called R between 0-1

S = random.Get01(); //Generate a random number called S between 0-1

if(R + S >=1)
{
R = 1 – R;
S = 1 – S;
}

Great, we have our barycentric coordinates. Now, let’s apply them.

Starting at point A, we want to go a random percentage along vector AB, then go another random percentage along vector AC. Our math will look something like this:

RandomPointPosition = A + R*AB + S*AC

Done!