Board index » delphi » Random 3d point inside a 3d triangle

Random 3d point inside a 3d triangle

Paul:

Quote
"Paul Nicholls" <phan...@southcom.com.au> wrote in message news:3990dd19_2@dnews...
> Hi all, lets say I have a 3d triangle defined by three 3d points anywhere in
> 3d space: (x1,y1,z1), (x2,y2,z2), (x3,y3,z3)  for example.
> Is there any "easy" way of selecting random points within the 3d triangle
> which are also lying on the plane defined by triangle the same time.

Take a look at this post from late last year from Dave Eberly in comp.graphics.algorithms:
http://www.deja.com/getdoc.xp?AN=544184485:

"Let the points be (x0,y0,z0), (x1,y1,z1), (x2,y2,z2).  Given (x,y), solve for s and t in (x,y) =
(x0,y0)+s*(x1-x0,y1-y0)+t*(x2-x0,y2-y0). The point is inside the triangle if s >= 0, t >= 0, and s+t
<= 1. Then choose z = (1-s-t)*z0+s*z1+t*z2."

So it looks like you could get a random point in this triangle by defining
s := Random;   // returns value from 0.0 to 1.0

followed by

t := (1-s)*Random;

and then applying the above definitions to compute (x,y) from s and t, and
the separate formula for z, to get the (x,y,z).

--
efg

Earl F. Glynn     E-mail:  EarlGl...@att.net
Overland Park, KS  USA

efg's Computer Lab:  http://www.efg2.com/Lab

 

Re:Random 3d point inside a 3d triangle


Thanks Earl, I can see where the z value comes from after getting the random
s value and using that to find t:

    z = (1-s-t)*z0+s*z1+t*z2

but I am confused how to use the below formula to find x and y as it is a
"multiple result" function to start with

    (x,y) = (x0,y0)+s*(x1-x0,y1-y0)+t*(x2-x0,y2-y0)
Sorry if it seems I am trying to get out of doing the work myself, but I
haven't a clue :(

Paul Nicholls (Delphi 3 Standard),
Live long and optimise!

 Home Page: www.southcom.com.au/~phantom
 Email         : phan...@southcom.com.au

< IF YOU WANT TO EARN MONEY WHILE YOU SURF ON THE NET GO HERE: >
< http://www.alladvantage.com/go.asp?refid=BEM-274 >

Re:Random 3d point inside a 3d triangle


Quote
"Paul Nicholls" <phan...@southcom.com.au> wrote in message news:3990ec21_1@dnews...
> Thanks Earl, I can see where the z value comes from after getting the random
> s value and using that to find t:

Both s and t are formed from two different calls to Random.

Quote

>     z = (1-s-t)*z0+s*z1+t*z2

> but I am confused how to use the below formula to find x and y as it is a
> "multiple result" function to start with

>     (x,y) = (x0,y0)+s*(x1-x0,y1-y0)+t*(x2-x0,y2-y0)

Is this a bit clearer:

   x = x0 + s*(x1-x0) + t*(x2-x0)

   y = y0 + s*(y1-y0) + t*(y2-y0)

where the initial three points are
(x0, y0, z0)
(x1, y1, z1)
(x2, y2, z2)

Does this help?

--
efg

Earl F. Glynn     E-mail:  EarlGl...@att.net
Overland Park, KS  USA

efg's Computer Lab:  http://www.efg2.com/Lab

Re:Random 3d point inside a 3d triangle


Quote
>Is this a bit clearer:

>   x = x0 + s*(x1-x0) + t*(x2-x0)

>   y = y0 + s*(y1-y0) + t*(y2-y0)

DUH! Silly me, I should have realised <g>  Thanks heaps Earl and salutations
:)
--
Paul Nicholls (Delphi 3 Standard),
Live long and optimise!
 Home Page: www.southcom.com.au/~phantom
 Email         : phan...@southcom.com.au

< IF YOU WANT TO EARN MONEY WHILE YOU SURF ON THE NET GO HERE: >
< http://www.alladvantage.com/go.asp?refid=BEM-274 >

Re:Random 3d point inside a 3d triangle


Quote
Earl F. Glynn wrote:
> So it looks like you could get a random point in this triangle by defining
> s := Random;   // returns value from 0.0 to 1.0

> followed by

> t := (1-s)*Random;

The phrase "random point" is open to interpretation. Perhaps Paul wants
the point to be chosen uniformly in the original triangle. If so, this
method doesn't work because it will be more likely to choose points near
one vertex. If Paul doesn't care what the distribution of points is, but
simply wants a way to choose points so that he gets a different point
each time, then this method will do that.

--
David Marcus

Re:Random 3d point inside a 3d triangle


In article <MPG.13fb3e35c5f58e77989...@newsgroups.inprise.com>, David

Quote
Marcus wrote:
> The phrase "random point" is open to interpretation. Perhaps Paul wants
> the point to be chosen uniformly in the original triangle. If so, this
> method doesn't work because it will be more likely to choose points near
> one vertex.

I think the following slight modification would result in a uniform
distribution:

sum := sqrt(random); // takes varying line length s+t = sum into account
t := random * sum;
s := sum - t;
r := 1 - s - t;

(x,y,z) := r*(x0,y0,z0) + s*(x1,y1,z1) + t*(x2,y2,z2); //pseudo code

Renate

Re:Random 3d point inside a 3d triangle


Thanks David and Renate :)  I was having just this exact "problem" when
using the code afterwards.  I will try the modifications.

--
Paul Nicholls (Delphi 3 Standard),
Live long and optimise!

 Home Page: www.southcom.com.au/~phantom
 Email         : phan...@southcom.com.au

< IF YOU WANT TO EARN MONEY WHILE YOU SURF ON THE NET GO HERE: >
< http://www.alladvantage.com/go.asp?refid=BEM-274 >

Re:Random 3d point inside a 3d triangle


WOOHO!! It now works perfectly!  for example if I choose 0.5 for both
'random' values, the resulting point is in the same position as the midpoint
of the triangle, and if I do x number of random points the distribution is
nice and 'even' now.

Thanks guys!
BTW here is my code I'm now using if anyone is interested :)

TTri3d = record
  x0,y0,z0: Double;
  x1,y1,z1: Double;
  x2,y2,z2: Double;
end;

procedure RandTriPoint(Tri:TTri3d;r1,r2:Double;var x,y,z:Double);
//    where     0 <= r1, r2 < 1
var
  s,t,r: Double;
begin
  s := Sqrt(r1);
  t := r2*s;
  s := s - t;
  r := 1 - s - t;
  x := r*Tri.x0 + s*Tri.x1 + t*Tri.x2;
  y := r*Tri.y0 + s*Tri.y1 + t*Tri.y2;
  z := r*Tri.z0 + s*Tri.z1 + t*Tri.z2;
end;

--
Paul Nicholls (Delphi 3 Standard),
Live long and optimise!

 Home Page: www.southcom.com.au/~phantom
 Email         : phan...@southcom.com.au

< IF YOU WANT TO EARN MONEY WHILE YOU SURF ON THE NET GO HERE: >
< http://www.alladvantage.com/go.asp?refid=BEM-274 >

Re:Random 3d point inside a 3d triangle


Quote
Renate Schaaf wrote:
> I think the following slight modification would result in a uniform
> distribution:

> sum := sqrt(random); // takes varying line length s+t = sum into account
> t := random * sum;
> s := sum - t;

That works, but I don't see how you came up with it. I was just going to
suggest

t := random;
s := random;

if s + t > 1 then begin
   s := 1 - s;
   t := 1 - t;
end;

--
David Marcus

Re:Random 3d point inside a 3d triangle


In article <MPG.13fc9a10edc12fb0989...@newsgroups.inprise.com>, David

Quote
Marcus wrote:
> t := random;
> s := random;

> if s + t > 1 then begin
>    s := 1 - s;
>    t := 1 - t;
> end;

This is much simpler!  Just fill the parallelogram uniformly and fold
it... The base of my suggestion was that the line length t+s=c is
proportional to c, so the probability density of c has to increase
linearly with c, which means that c^2 has to be unifomly distributed,
well forget it :)

Renate

Re:Random 3d point inside a 3d triangle


Thanks David :-)

--
Paul Nicholls (Delphi 3 Standard),
Live long and optimise!

 Home Page: www.southcom.com.au/~phantom
 Email         : phan...@southcom.com.au

< IF YOU WANT TO EARN MONEY WHILE YOU SURF ON THE NET GO HERE: >
< http://www.alladvantage.com/go.asp?refid=BEM-274 >

Re:Random 3d point inside a 3d triangle


Quote
Renate Schaaf wrote:
> The base of my suggestion was that the line length t+s=c is
> proportional to c, so the probability density of c has to increase
> linearly with c, which means that c^2 has to be unifomly distributed,

Oh, I get it. Thanks.

--
David Marcus

Other Threads