• Advertisement

Archived

This topic is now archived and is closed to further replies.

how to count the point value in the 3d triangle

This topic is 5064 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

if I have known the triangle''s three vertexs value in 3d axis, how can I get the point''z axis value that I have known the point is inside the triangle surface and knew the point''s x and y value?

Share this post


Link to post
Share on other sites
Advertisement
If I understand you correctly, what you need to do is calculate the equation of the plane upon which the triangle lies, then plug the x and y values of the unknown point into the equation and solve for z.

Given 3 points (p1,p2,p3) which form a triangle, you can calculate the normal vector of the plane as the cross-product of two of the triangle's sides, normalized to unit length:

Vector v1=p3-p1;
Vector v2=p2-p1;
Vector normal=v1.CrossProduct(v2);
normal.normalize();

Now, the equation of a plane is expressed as:

Ax + By + Cz + D = 0
or
normal.x * x + normal.y * y + normal.z * z + D = 0

where A,B and C are the components of the normal vector, and D is a constant. Take one of the points of the triangle (say, p1) and plug it into the equation, along with the normal components, and solve for D:

D = -( (normal.x * p1.x) + (normal.y * p1.y) + (normal.z * p1.z) )

Now, for p4 you know the x and y values and wish to calculate p4.z. To do so, plug p4.x and p4.y into the plane equation, and solve for p4.z:

-( (normal.x * p4.x) + (normal.y * p4.y) + D )
p4.z = ----------------------------------------------
normal.z


Remember to check for the special case where normal.z==0 , in which case the value of p4.z will also always be 0. If you try to solve this case using the equation, you will of course get a divide-by-zero exception.





Now, if you need to determine whether or not this calculated point (p4) is within the triangle, you can do it in this fashion:

First, calculate a few dot products based on the edge of the triangle:

c00 = v1.dotproduct(v1);
c01 = v1.dotproduct(v2);
c11 = v2.dotproduct(v2);

Now, calculate some vectors and dot products based on the intersection point:

Vector Q = p4 - p1;
q0 = v1.dotproduct(Q);
q1 = v2.dotproduct(Q);

delta = (c00 * c11) - (c01 * c01);
s0=(c11*q0 - c01*q1) / delta;
s1=(c00*q1 - c01*q0) / delta;

If s0>=0 and s1>=0 and s0+s1<=1.0, the point lies within the triangle.


Golem
Blender--The Gimp--Python--Lua--SDL
Nethack--Crawl--ADOM--Angband--Dungeondweller


[edited by - VertexNormal on April 12, 2004 8:30:51 PM]

Share this post


Link to post
Share on other sites
Triangle vertices = 'p1', 'p2', 'p3'
point of interest = 'p'
direction 'v' = (0, 0, -1) (down the z axis)
resulting point on triangle plane = 'q'


// triangle plane

Vector v1=p3-p1; // edge 3

Vector v2=p2-p1; // edge 1

Vector n = v1.CrossProduct(v2); // normal of plane

float d = normal.Dot(p1); // distance of plane from origin


// intersection of ray (p, v) with triangle plane

t = (d - p.Dot(n)) / v.Dot(n);

// intersection point on plane

q = p + v * t;


you don't need to normalise the plane normal, but you can if you want.

edit : it's exactly what vertex normal said. damn IE.


[edited by - oliii on April 13, 2004 4:25:01 AM]

Share this post


Link to post
Share on other sites
Thank you for reply , VertexNormal

but I don''t know why use v1 vector and v1 vector to calculate the dot product, what is the result value?

Share this post


Link to post
Share on other sites
quote:
Original post by juwen_chao
Thank you for reply , VertexNormal

but I don't know why use v1 vector and v1 vector to calculate the dot product, what is the result value?


The second part of my earlier post (where I make use of v1.dotproduct(v1) ) is an algorithm to test a point to see if it is within the boundary of a triangle. The algorithm depends on the parametric form of a plane equation, which is expressed as:

P(s,t) = p1 + s(p2-p1) + t(p3-p1)

or

P(s,t) = p1 + s*v1 + t*v2

Any point on the plane can be represented as an (s,t) coordinate pair (in my earlier post, I used s0 and s1 rather than s and t, but they are the same values) which, when plugged into the parametric equation, yields the Cartesian (x,y,z) point. The set of points for which s>=0 && t>=0 && s+t<=1 are all points within the triangle or on the triangle edges. So if you can find the (s,t) pair for a given point and test it, if the (s,t) pair meets the criteria, then the corresponding point lies within the triangle.

The (s,t) coordinates for your original triangle points--p1, p2 and p3--are:
p1: s=0, t=0
p2: s=1, t=0
p3: s=0, t=1

The derivation of the equations to calculate s and t (of which, the v1.dotproduct(v1) computation is a part) is a little complicated, but you can find an explanation of it here (which details an algorithim for testing for linesegment/triangle intersection; the relevant section for here comes after the diagram).



Golem
Blender--The Gimp--Python--Lua--SDL
Nethack--Crawl--ADOM--Angband--Dungeondweller


[edited by - VertexNormal on April 13, 2004 1:10:37 PM]

Share this post


Link to post
Share on other sites
if calculate the normal vector of one triangle ,
the result is two of normal vector value x y z are zero,
x = 0, y = 0, z = 1, for example.

then use the equation of a plane:
Ax + By + Cz + D = 0;
to calculate one point whether into the triangle will wrong, any x y value will ok,

what can i do?

Share this post


Link to post
Share on other sites
quote:
Original post by juwen_chao
if calculate the normal vector of one triangle ,
the result is two of normal vector value x y z are zero,
x = 0, y = 0, z = 1, for example.

then use the equation of a plane:
Ax + By + Cz + D = 0;
to calculate one point whether into the triangle will wrong, any x y value will ok,

what can i do?



I don''t really understand what you are asking here. What''s the problem?

With a normal vector of (0,0,1), the plane defined is all points (x,y,-D). In such a case, any point (x,y) plugged into the equation will have the same z value when solving for z, since the equation reduces down to x+D=0:

Ax + By + Cz + D = 0
0x + 0y + 1z + D = 0
z + D = 0
z=-D

So no matter what the value of x and y, as long as z==-D the equation is satisfied and the point lies on the plane.




Golem
Blender--The Gimp--Python--Lua--SDL
Nethack--Crawl--ADOM--Angband--Dungeondweller

Share this post


Link to post
Share on other sites

  • Advertisement