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?

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

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.

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]

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.

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