0
\$\begingroup\$

I have a terrain which is a mesh. Given the x and z coordinates in which a character is placed, I would like a function that returns the y (so, the height) at that given point.

I am using Vulkan and I would like to know how can I implement it in C++.

Thanks

\$\endgroup\$
1
  • \$\begingroup\$ This sounds like a job for a raycast. Search that term, and you should find what you need. If you need more help, edit your question to show how you've tried to solve this problem based on your research thus far. \$\endgroup\$
    – DMGregory
    Jul 9, 2022 at 0:22

1 Answer 1

2
\$\begingroup\$

The height of an object relative to an underlying terrain is the distance from its position \${P}\$ (plus an optional offset \$C\$ of choice) and the position projection \$P'\$ onto the terrain:

enter image description here

Since a terrain mesh is usually made up of many (triangle) faces, it's more appropriate to use a ready-made physics library: this way, one could cast a ray from \$P\$ downwards, detect the collision on the terrain at position \$P'\$ and get the current height by computing \$P_y-P_y'\$. Implementing such functionalities from scratch is unsuitable since it's time-consuming and probably out of the scope of your assignment.

However, you can easily implement your own support functions and compute the height, provided that some assumptions on the terrain mesh shape are met. Here're some requirements for this solution to work:

  1. The mesh, when projected, resembles a regular square grid. This means all vertices are the same distance from their front, back and side neighbours when ignoring the vertical coordinate.

  2. The quads in the meshes are triangulated. This means each quad is made up of two triangles. Unlike generic polygons, triangles have many geometric properties we can take advantage of, as we'll do later.

enter image description here

Grid Mesh: finding \$P\$'s grid coordinates

Before computing height, we must first discover in what part of the terrain \$P\$ lies. We may check \$P\$ against all vertices and find the ones closest to it to compute height, but this is computationally expensive.

We could subdivide the terrain into cells, and find the cell containing \$P\$ instead. A grid-like mesh lets us identify each cell using row and column indices, and \$P\$ would be inside one of the cells. Moreover, if the grid is regular (like in the pictures), we can find out the correct cell by "snapping" \$P\$ to the grid and finding out the cell position in the grid coordinate system.

enter image description here

If the grid cells have size \$l\$ (assuming squares), and the grid origin has position \$D = (D_x, D_y, D_z)\$, the cell containing \$P\$ has indices:

$$ \begin{align} u &= \LARGE{\lfloor} \normalsize \frac{P_x-D_x}{l} \LARGE{\rfloor} \\ v &= \LARGE{\lfloor} \normalsize \frac{P_z-D_z}{l} \LARGE{\rfloor} \\ \end{align} $$

Once we get the indices, we can reference the four vertices belonging to that quad, if we have a convenient look-up table for storing such information. A similar approach can be used to find the indices of the grid vertices (which coincide with geometry vertices in the mesh) and use them to directly reference the geometry instead:

$$ \begin{align} (u, v)_{v_1} &= \LARGE{\lfloor} \normalsize \frac{P-D}{l} \LARGE{\rfloor} \\ (u, v)_{v_4} &= \LARGE{\lceil} \normalsize \frac{P-D}{l} \LARGE{\rceil} \\ (u, v)_{v_2} &= (u_{v_4}, v_{v_1}) \\ (u, v)_{v_3} &= (u_{v_1}, v_{v_4}) \\ \end{align} $$

Triangulated Quads: finding the actual triangle below \$P\$

Once we find the quad containing the position from which to sample the relative height to the terrain, we need to determine the actual projection \$P'\$. Since four points are hardly co-planar, we triangulate the quads so that every vertex triad lies on a flat surface.

Depending on the mesh triangulation, we may have one of the following cases:

enter image description here

We can easily discriminate which triangle contains \$P\$, for it can be either above or below the triangulation diagonal. We can discriminate between such cases by checking the sign of the cross product between \$P\$ and the end vertex of the diagonal, with respect to the start vertex of the diagonal:

  • On the left, \$\overrightarrow{V_3P}\times\overrightarrow{V_3V_2}\gt 0\$, so \$P\$ lies in the semi-plane above the oriented vector \$\overrightarrow{V_3V_2}\$, and the triangle to check for during the next step is \$\langle V_3V_2V_1\rangle\$.

  • On the right, \$\overrightarrow{V_1P}\times\overrightarrow{V_1V_4}\gt 0\$, so \$P\$ lies in the semi-plane above the oriented vector \$\overrightarrow{V_1V_4}\$, and the triangle to check for during the next step is \$\langle V_1V_4V_2\rangle\$.

Triangles: projecting \$P\$ and get \$P'\$

Once we know what triangle is directly below \$P\$, we must find the projection \$P'\$ so that we can compute the distance \$(P, P')\$, thus the height of \$P\$ relative to the terrain.

Setting \$P_x' = P_x\$ and \$P_z' = P_z\$ are conditions needed to find out the missing \$P_y'\$ that satisfies the barycentric coordinate relationship for the current triangle (a good, practical explanation of this topic can be found here). Barycentric coordinates are also the foundation of the ray-triangle intersection algorithm, which lets you find the actual coordinates for \$P'\$. An implementation has been provided in this past StackOverflow answer.


I acknowledge there's A LOT of room for optimisation and improvement on this method: take rotations into account, generalising to any equivalent terrain topology...

Also, I didn't test it beyond some pen-and-paper calculations, however, I believe the main idea behind is a good starting point to make things work in the first place, and maybe refine the procedure to get more fine-tuned results when working with complex terrain meshes.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .