I''m sure this is elementary to most of you, but for those of us who suffer with the Math of 3D game programming, it can get frustrating. For my terrain system I''m having intermittent problems where I''m not correctly calculating the elevation of the player over the terrain. To keep it simple lets say I have 3 points in 3D space that represent my triangle. p1.x p1.y p1.z p2.x p2.y p2.z p3.x p3.y p3.z and my players X and Z position over the triangle. Actually, I''m using heightmaps, so I know what square section I''m in, but that section is made up of two triangles. I know I''m over one of the two, don''t know which one. Currently I pass in the first triangle of the square to my height check, and if I''m deemed not to be over the triangle specified, then I return an error and therefore must be over the other tri. Given the players location over the tri: pl.x pl.z I want a function that will return me the Y for the player based on the slope of the triangle and calculating what point of the triangle the player is over. This function should work even when the player is over the exact edge of the triangle (not necessarily within it but on the edge). This should also work if the triangle is at a VERY steep slope. The tri will never be at 90 degrees, and will always be something less than that. Can anyone provide me the function that will return the requested value? Like I said, I have a function now, but there seems to be a flaw in the math as it''s not reliable all the time. A documented function would be appreciated, but not absolutely necessary. Thanks so much, this would really mean a lot.

quote:

---

I want a function that will return me the Y for the player based on the slope of the triangle and calculating what point of the triangle the player is over.

---

Does it have to be using the slope? Because I have en excellent method that works with the other information you have!

What this method does is find the intersection between the triangle and a line going straight down, which should in effect return the point we are over, and since we will also have a vector, we can find its length to get the height.

First, we want to create a normal for the triangle:

  vecNormal = CrossProduct(vec1, vec2);  // This can actually be any two points on the triangle     

If you have this (top down view, player above):

               p1              /  \                          /    \                        /      \                  p2/--------\p3

Then you would create the vectors like so:

vec1 = (p3 - p2);
vec2 = (p1 - p2);

If the points go in the other order, then switch vec1 and vec2 in the function call to CrossProduct.

As expected, normalize the resultant vector.

What we need to do is find the DotProduct between the player's origin and the triangle normal. Given our normal, a point on the triangle, and the point we are checking, we can find the dotproduct using this formula:

result = DotProduct(player_origin, normal_vector) - DotProduct(normal_vector, point_on_triangle);

We also need to DP between this normal and a point on the opposite side of the triangle. For this, I would make it the player's origin minus a large bogus amount in the y direction (i.e if the player's origin was (78,34,99), then the other point would be (78,-234783,99) or something similar). Find the DotProduct between that and the normal.

We now have all the information we need to calculate the intersection using laws of similar triangles. Find the ratio between the magnitude of the first dot product and the sums of the magnitudes of both dot products:

// DP_BOGUS_POINT will be negative because it's behind the triangle
Ratio = DP_PLAYER / (DP_PLAYER + abs(DP_BOGUS_POINT));

Result_Vector = Ratio * Vector(DP_BOGUS_POINT - DP_PLAYER);
Point_Player_Is_Above = Result_Vector + player_origin;
Height = Length(Result_Vector);

Hope that wasn't too confusing. I'd be glad to elaborate on anything.

[edited by - Zipster on May 18, 2002 12:59:04 AM]

[edited by - Zipster on May 18, 2002 12:59:54 AM]

Thanks. It seems logical enough, but what if the player isn''t actually over that triangle? If you recall, I know what square section of the terrain I''m over. Therefore, I''ve narrowed myself down to which 2 triangles I''m over, but I''m not certain which of the two I''m over. How can I alter this to work in my situation?

thanks

One way to do that is to treat your grid squares as unit squares, work out the position of the player in terms of the x & y both in the interval [0,1], then if the player is in the first triangle

x + y < 1

Otherwise

x + y >= 1

This code takes pt to be the player position in world space. xScale,yScale are the size of one grid square and gridX,gridY are the integer coordinates of the square the player is over.

Hi there Sipster,



I have a question about the implementation of your technique, and was hoping you could explain the details. And as for slope, maybe that was a poor choice of words by me. What I need (and I think you understand this) is the Y value of the point where I collide with the triangle. Another wards, the players x and z are somewhere over a triangle, and I need the y value of that traingle that is directly below me.



I think I understood it all up to the third to last line::



.

.

.

Result_Vector = Ratio * Vector(DP_BOGUS_POINT - DP_PLAYER);
Point_Player_Is_Above = Result_Vector + player_origin;
Height = Length(Result_Vector);



DP_BOGUS_POINT and DP_PLAYER are both floats, right

So how do I use vector? Doesn’t vector require 3 values? I’m confused because you are subtracting the two and passing in just one.

Then you multiply it by ratio, but how do you multiply a vector by a float anyway?

If you can help me to better understand this and/or look at my implementation below and help me fix it, I’d really appreciate it.



Thanks so much!!



Larry



Here is my interpretation of your function:





//=================================================

// MU3DMATH_HeightAtTri

//

// determines where along the tri, the specified values fall,

// then returns the Y value at that point along the tri

//

// xp2 = players current x position

// zp2 = players current z position

// v1, v2, v3 = 3 points of the triangle in clockwise order (performing CCW culling)

//=================================================

double MU3DMATH_HeightAtTri( const double& xp2,const double& zp2, D3DXVECTOR3& v0,D3DXVECTOR3& v1, D3DXVECTOR3& v2)

{

D3DXVECTOR3 vec1;

D3DXVECTOR3 vec2;

D3DXVECTOR3 pl;

D3DXVECTOR3 bogus;

D3DXVECTOR3 norm;

float dotpl;

float dotbogus;

float ratio;

float result;



vec1 = (v2 - v0);

D3DXVec3Normalize(&vec1, &vec1);



vec2 = (v1 - v0);

D3DXVec3Normalize(&vec2, &vec2);



D3DXVec3Cross(&norm, &vec1, &vec2);



pl.x = xp2;

pl.y = 2000000000; // guaranteed to be above tri

pl.z = zp2;



bogus = pl;

bogus.y*=-1; // guaranteed to be below tri





dotpl = D3DXVec3Dot(&pl, &norm) - D3DXVec3Dot(&norm, &vec1);

dotbogus = D3DXVec3Dot(&bogus, &norm) - D3DXVec3Dot(&norm, &vec1);



dotpl = abs(dotpl);

ratio = dotpl / ( dotpl + abs( dotbogus ));



//Result_Vector = Ratio * Vector(DP_BOGUS_POINT - DP_PLAYER);

//Point_Player_Is_Above = Result_Vector + player_origin;

//Height = Length(Result_Vector);



// result = Vector( dotbogus - dotpl ) * ratio;



return result;



}

I had the exact same problem a while ago. It drove me NUTS for a week until I realized my cross product was wrong.

well first of all, to find what tri i''m on, I just say

my quad is divided like this:

----
| /|
|/ |
----

so my test is :
if ( x > z )

then I take the three corners of my triangle, a, b, and c, and use them to find the normal of the triangle.

normal = ( b - a ) cross ( c - a )

Do you know the plabne equation?
Ax + By + Cz = D

where A,B,C are the compenents of the normal, and D is the normal dot a point on the plane. Anyways you know x and z and you want to find y, so

y = ( D - Ax - Cz ) / B

and B will never be zero unless your plaen is straght up.. which you said it wasnt.

good luck!