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!

About these ads

5 thoughts on “Random Point In a Triangle – Barycentric Coordinates

  1. this is a really informative explanation. Although I’m still having trouble applying this to a problem I’m having.

    I want to be able to take any coordinate in uv space, and find it’s xyz position on whatever triangle, or part of the mesh,it corresponds too. Is this formula the way to go about that?

    It seems like it would be, but I suppose I would have to find out what triangle said point(not necessarily a uv or vert) was over first,then go from there?

    Thanks!

    Lucas

    • What program are you using, Lucas?

      In Houdini, for instance, it is very easy to access point UV data and use that information to extrapolate UV coordinates for a point on the surface of your geometry. (The point UV’s are easily available for lookup).

      For Cinema 4D, you have to dig into the SDK (I assume you are writing a plugin) to access that info. This link is relevant:

      http://www.plugincafe.com/forum/forum_posts.asp?TID=4885&KW=point+uvw&PID=19905#19905

      To go about selecting some arbitrary uv point and then finding out where it exists on geometry (rather than the reverse) is going to be a programmatically slow process. You would have to query EACH polygon, calculate its area and positionin uv space to see if that point falls within that area, and keep going until you have run out of polygons. And remember, one point in uv space can be shared by multiple polygons, so it is not enough to just stop at the first match you get.

      I may be able to advise further if you can share what you are attempting to achieve.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s