Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Alright, I'm sure there has to be a simple way to do this but it eludes me at the moment.

I want to be able to generate random points on the surface of a quadrilateral in 3D space. (Defined simply as four points) What is the best way to go about doing this?

If the quad is a rectangle, this is trivial to do with random interpolation between points. However, this won't work for me since my quads aren't guaranteed to have rectangular properties.

share|improve this question

2 Answers 2

up vote 6 down vote accepted

Cut the quad into two trianles, get their area size, then first random-pick one of the triangles (based on their areas) and finally pick a random point in the triangle using your favourite standard algorithm for triangles.

share|improve this answer
    
Accepted but you think you could point me in the right direction for handling the triangles? –  KlashnikovKid Feb 19 '12 at 17:53
1  
stackoverflow.com/questions/4778147/… –  Imi Feb 19 '12 at 21:34

You can easily do this with a variant of bilinear interpolation. For example

Point randomInQuad(Point a, b, c, d) {
  double s = random(0.0,1.0);  // uniform in [0,1]
  Point e = s*a + (1-s)*b;
  Point f = s*c + (1-s)*d;
  double t = random(0.0,1.0);
  return t*e + (1-t)*f;
}

You can interpret this as putting each of the vertices of your quad at a corner of a unit square. Then, you randomly pick a point in the unit square. Finally, you use bilinear interpolation (which is a series of affine combinations) to interpolate a vertex at that point.

share|improve this answer
1  
This is not uniform picking. Consider what happens when two vertices are very close to each other: you get a lot more points in that area. –  Sam Hocevar Feb 20 '12 at 10:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.