Sign in to follow this  
Sneftel

Non-uniform random sampling over a triangle

Recommended Posts

I've been going over this in my head all morning, and haven't gotten very far. This is for a new sampling algorithm I'm writing. The basic idea is this: Given a triangle with vertices (x1, y1), (x2, y2), and (x3, y3), where the vertices have weights w1, w2, and w3, how can I randomly choose a point in that triangle, subject to that weighting? An equivalent problem: Given the geometric solid formed by sweeping the triangle (x1, y1, w1),(x2, y2, w2),(x3, y3, w3) to its projection on the XY-plane, how can I randomly choose a point uniformly distributed within that solid? I've gotten a little further with the second formulation. I had the idea of considering the solid as three separate solids, each an irregular tetrahedron consisting of (x1,y1,0),(x2,y2,0),(x3,y3,0), and (xn, yn, wn), where n is between 1 and 3. By skewing these tetrahedra and stacking them, you get the original solid of the reformulation of the problem. So then you could segment your probability by the volume of each tetrahedron, pick a random tetrahedron using that distribution, then pick a uniformly distributed point within the tetrahedron. That, however, requires randomly sampling a tetrahedron, which I don't know how to do, and also involves quite a few assumptions which might be wrong. Anyone feel like helping out?

Share this post


Link to post
Share on other sites
Stretch your triangle so that weight tells you how much further from the center to move the vertex. Now pick uniformly distributed random sample from this triangle and transform that point to the original triangle.

EDIT: Probably doesn't give what you wan't because... it was just a 15 second ad-hoc algo.. and those rarely work..

Share this post


Link to post
Share on other sites
Hmm... I think I understand what you're saying, but I'm a little confused. So given my points and weights, I generate (x1',y1')..(x3',y3'), and sample uniformly within that new triangle. But if I transform that point back into the space of the original triangle, don't I just have a uniform distribution? I would assume that the transformation of a uniform probability distribution from one triangle to another would still be uniform.

Share this post


Link to post
Share on other sites
You're probably right.. this is what I thinked of when writing that first post..

This triangle

*******
****
*

stretches into


*******
******
*****
****
***
**
*


Here distribution remains same in horizontal direction and vertical distribution gets stretched. Or.. it might be possible that i'm just too tired...

EDIT: Think that your stretched polygon is full of evenly spaced dots. Now if the stretching (or what ever operation) is not just scaling and/or rotating then when the polygon is destretched dots won't be evenly spaced.

New ascii art:

******
******
******
******

gets "destretched" into

******

******

******

******

here the weight was below one so the vertical direction is more sparse than in original.

EDIT2:

If you're looking for distribution that changes like brightness changes in gouraud shading (linearly interpolating the weights to obtain new distribution) then my algo won't work.

[Edited by - Winograd on December 1, 2004 2:41:19 PM]

Share this post


Link to post
Share on other sites
I'd do it so:
You need to generate random x and then random y that after mapping it to your triangle using
x1+x2*x+x3*y
y1+y2*x+y3*y

you get desired distribution.
So problem is 1D now , you need to find distribution for x, and then for known x, find distribution for y.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
I would assume that the transformation of a uniform probability distribution from one triangle to another would still be uniform.

As far as I can see this should work because the scaleing is non-uniform. Not bad for a 15 second brain storm Winograd.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
From http://www.faqs.org/faqs/graphics/algorithms-faq/
read "Subject 6.05: How can I generate a random point inside a triangle?".

The trick is getting a weighted random number. You have to build some function. Something like:

Function interval [a, b]

f(a) = weight 1
f(b) = weight 2

Integrate that function to find the area of the function between [a, b]. Then pick a number from [0, area] and use the inverse of the previous function to get back a number in [a, b].

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this