0

Let's say there is a grid terrain for a game composed of tiles made of two triangles - made from four vertices. How would we find the Y (up) position of a point between the four vertices?

Terrain

I have tried this:

float diffZ1    = lerp(heights[0], heights[2], zOffset);
float diffZ2    = lerp(heights[1], heights[3], zOffset);
float yPosition = lerp(diffZ1, diffZ2, xOffset);

Where z/yOffset is the z/y offset from the first vertex of the tile in percent / 100. This works for flat surfaces but not so well on bumpy terrain.

I expect this has something to do with the terrain being made from triangles where the above may work on flat planes. I'm not sure, but does anybody know what's going wrong?

This may better explain what's going on here:

enter image description here

In the code above "heights[]" is an array of the Y coordinate of surrounding vertices v0-3. Triangle 1 is made of vertex 0, 2 and 1. Triangle 2 is made of vertex 1, 2 and 3.

I wish to find coordinate Y of p1 when its x,y coordinates lay between v0-3.

So I have tried determining which triangle the point is between through this function:

bool PointInTriangle(float3 pt, float3 pa, float3 pb, float3 pc)
{
  // Compute vectors        
  float2 v0 = pc.xz - pa.xz;
  float2 v1 = pb.xz - pa.xz;
  float2 v2 = pt.xz - pa.xz;

  // Compute dot products
  float dot00 = dot(v0, v0);
  float dot01 = dot(v0, v1);
  float dot02 = dot(v0, v2);
  float dot11 = dot(v1, v1);
  float dot12 = dot(v1, v2);

  // Compute barycentric coordinates
  float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);
  float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
  float v = (dot00 * dot12 - dot01 * dot02) * invDenom;

  // Check if point is in triangle
  return (u >= 0.0f) && (v >= 0.0f) && (u + v <= 1.0f);
}

This isn't giving me the results I expected

I am then trying to find the y coordinate of point p1 inside each triangle:

// Position of point p1
float3 pos = input[0].PosI;

// Calculate point and normal for triangles
float3 p1 = tile[0];
float3 n1 = (tile[2] - p1) * (tile[1] - p1); // <-- Error, cross needed
       // = cross(tile[2] - p1, tile[1] - p1);
float3 p2 = tile[3];
float3 n2 = (tile[2] - p2) * (tile[1] - p2);  // <-- Error
       // = cross(tile[2] - p2, tile[1] - p2); 
float newY = 0.0f;

// Determine triangle & get y coordinate inside correct triangle
if(PointInTriangle(pos, tile[0], tile[1], tile[2]))
{
    newY = p1.y - ((pos.x - p1.x) * n1.x + (pos.z - p1.z) * n1.z) / n1.y;
}
else if(PointInTriangle(input[0].PosI, tile[3], tile[2], tile[1]))
{
    newY = p2.y - ((pos.x - p2.x) * n2.x + (pos.z - p2.z) * n2.z) / n2.y;
}

Using the following to find the correct triangle:

if((1.0f - xOffset) <= zOffset)
    inTri1 = true;

And correcting the code above to use the correct cross function seems to have solved the problem.

enter image description here

4

1 回答 1

4

因为您的 4 个顶点可能不在一个平面上，所以您应该分别考虑每个三角形。首先找到该点所在的三角形，然后使用下面的 StackOverflow 讨论求解 Z 值（注意轴的不同命名）。我个人更喜欢 DanielKO 的答案，但接受的答案也应该有效：

3D 空间中三个 3D 点的线性插值

编辑：对于问题的第二部分（找到该点所在的三角形）： 因为您的瓷砖在 xz 平面上的投影（当您定义坐标时）是完美的正方形，所以找到该点所在的三角形是一个非常简单的操作。在这里，我将使用术语 left-right 来指代 x 轴（从较低的 x 值到较高的 x 值）和 bottom-top 来指代 z 轴（从较低的 z 值到较高的值）。

每个图块只能以两种方式之一进行拆分。(A) 通过从左下角到右上角的对角线，或 (B) 通过从右下角到左上角的对角线。

  • 对于任何拆分为 A 的图块：检查 x' > z'，其中 x' 是图块左边缘到点的距离，z' 是图块底部边缘到点的距离。如果 x' > z' 则您的点位于右下三角形；否则它在左上角的三角形中。

  • 对于任何分割为 B 的图块：检查 x" > z'，其中 x" 是图块右边缘到点的距离，z' 是图块底部边缘到点的距离。如果 x" > z' 那么你的点在左下三角；否则它在右上三角。

（小注：以上我假设您的瓷砖没有在 xz 平面中旋转；即它们与轴对齐。如果这不正确，只需在进行上述检查之前旋转它们以将它们与轴对齐。）

于 2014-08-31T23:13:53.430 回答