points in a triangle
lo all - im in the process of making a particle system and would like my particles to ''hover'' over a triangle in 3d space. but im having some problems in finding a fast method to get a random point on the triangles surface.
the random particles are created inside of a quad that totally covers the triangle [random x and y of particle generated]. im currently checking the location of the particle [x and y] to be created against the edges of the triangle to see if they are indeed inside the triangle. however i feel this is a sloppy way to go about this :/
any help would be much appreciated :D
cheers, Fusi0n
"We are what we repeatedly do. Excellence, then, is not an act, but a habit." - Aristotle
Off the top of my head (not thought this through or ever tested it & its late , but optimal solutions would probably be along the same lines...)
1) a triangle is made of 3 lines AB, BC, CA.
2) if you take the mid position of each of those lines you get ab, bc, ca.
3) if you then draw lines perpendicular to the main lines from those points, they all meet up in the centre of the triangle.
4) you could look at finding the midpoints as being an interpolation between the two end points with 0.5 as the blend amount. As an example for AB, a 0.5 blend would give you ab, a 0.0 blend would give A, 1.0 would give B, 0.25 would give halfway between A and ab.
5) Now to the idea: generate 3 random values between 0 and 1, plug those in as the blend amounts for each side of the poly, then find where the perpendiculars from those points meet. Result should always (AFAICT) be inside the triangle.
Finding the intersection of 3 perpendiculars in a fast way is the bit I'll leave to you. However there are also other ways of finding the centres (there's more than one centre...) and other points in the triangle and the same kind of ideas should work.
If I think of/test a better way, I'll post.
--
Simon O'Connor
Creative Asylum Ltd
www.creative-asylum.com
[edited by - s1ca on November 21, 2002 8:28:22 PM]
[edited by - s1ca on November 21, 2002 8:31:12 PM]
A / ac/ \ab /\_ _/ / | C---bc----B
1) a triangle is made of 3 lines AB, BC, CA.
2) if you take the mid position of each of those lines you get ab, bc, ca.
3) if you then draw lines perpendicular to the main lines from those points, they all meet up in the centre of the triangle.
4) you could look at finding the midpoints as being an interpolation between the two end points with 0.5 as the blend amount. As an example for AB, a 0.5 blend would give you ab, a 0.0 blend would give A, 1.0 would give B, 0.25 would give halfway between A and ab.
5) Now to the idea: generate 3 random values between 0 and 1, plug those in as the blend amounts for each side of the poly, then find where the perpendiculars from those points meet. Result should always (AFAICT) be inside the triangle.
Finding the intersection of 3 perpendiculars in a fast way is the bit I'll leave to you. However there are also other ways of finding the centres (there's more than one centre...) and other points in the triangle and the same kind of ideas should work.
If I think of/test a better way, I'll post.
--
Simon O'Connor
Creative Asylum Ltd
www.creative-asylum.com
[edited by - s1ca on November 21, 2002 8:28:22 PM]
[edited by - s1ca on November 21, 2002 8:31:12 PM]
Actually, thinking about it, another of the centres of a triangle is simply the average of the vertices (A+B+C/3).
So changing to a weighted average:
P = A*w1 + B*w2 + C*w3
Then randomising the weights in such a way that w1+w2+w3=1
(the true centre would be w1=w2=w3=1/3)
Should work... I think.
You can do some nice stuff with the fact you only really need this in 2D too (such as the swap x and y, negate one of them to get a perpendicular).
--
Simon O''Connor
Creative Asylum Ltd
www.creative-asylum.com
So changing to a weighted average:
P = A*w1 + B*w2 + C*w3
Then randomising the weights in such a way that w1+w2+w3=1
(the true centre would be w1=w2=w3=1/3)
Should work... I think.
You can do some nice stuff with the fact you only really need this in 2D too (such as the swap x and y, negate one of them to get a perpendicular).
--
Simon O''Connor
Creative Asylum Ltd
www.creative-asylum.com
quote:Original post by S1CA
Actually, thinking about it, another of the centres of a triangle is simply the average of the vertices (A+B+C/3).
So changing to a weighted average:
P = A*w1 + B*w2 + C*w3
Then randomising the weights in such a way that w1+w2+w3=1
(the true centre would be w1=w2=w3=1/3)
Should work... I think.
It does, as long as w1,2,3 are all between 0 and 1, and the sum equals 1.
You actually just described barycentric coordinates
barycentric coords... they are the coords of a position in "triangle space"...
sort of
google for it
sort of
google for it
Ah yes. Barycentric coordinates, knew I''d seen similar before somewhere.
As you''ll see from my first post I was originally thinking trilinear to obtain the (random) centre. The second idea was directly expanding on the first, I totally missed the fact that it was actually normalised Barycentrics I was thinking of.
Cheers,
--
Simon O''Connor
Creative Asylum Ltd
www.creative-asylum.com
As you''ll see from my first post I was originally thinking trilinear to obtain the (random) centre. The second idea was directly expanding on the first, I totally missed the fact that it was actually normalised Barycentrics I was thinking of.
Cheers,
--
Simon O''Connor
Creative Asylum Ltd
www.creative-asylum.com
wow thanks for the response :D fantastic stuff :D although, if we ended up using the perpendicular intersection approach, wouldnt we need to find out where only two of the perpendicular lines would intersect?
but i feel barycentric co-ordinates is the way to go, as with this method we can just slap in the 3d verts of the tri instead of converting from 3d-2d-3d (less proc time used too i would think). mebbeh im wrong
thanks again
Fusi0n
"We are what we repeatedly do. Excellence, then, is not an act, but a habit." - Aristotle
but i feel barycentric co-ordinates is the way to go, as with this method we can just slap in the 3d verts of the tri instead of converting from 3d-2d-3d (less proc time used too i would think). mebbeh im wrong
thanks again
Fusi0n
"We are what we repeatedly do. Excellence, then, is not an act, but a habit." - Aristotle
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement