Jump to content

getHeightAtCoordinates alternative


Recommended Posts

Hello again. So as stated in the topic title i want to know if there is any alternative for getHeightAtCoordinates function. Here is the solution i thought of:


I have a ground 3000x3000 loaded with createGroundFromHeightMap. The problem with getHeightAtCoordinates is that it is too slow.

For instance if i have a set of 200 points and if i try to find out the y coordinate for each one using a for loop, the y is set to 0. One solution i thought of(knowing that the ground is not going to change) is to remember in an array all the y coordinates of all points (i know there are 9 000 000 y coordinates for the whole map) - or for the active part of the map; the first time i load up the map.


My question would be, is there anyway i can compute the y coordinates, without relying on getHeightAtCoordinates?


Thank you in advance.


Note: I'm only interested in height where coordinates are whole numbers (ex: y where x=1.0 , z=2.0)

Link to comment
Share on other sites



I'd say that you could try breaking the ground mesh into several smaller parts, for example a hundred chunks of 300x300. Then the picking algorithm used by getHeightAtCoordinates will run much more smoothly. Actually you could also subdivide it into submeshes, which should have pretty much the same effect.


Although it's true that if you only need the height at the "nodes" (i.e. points on the grid), the getHeightAtCoordinates function is a waste of performance. In this case I'd say the simplest thing would be to read the Y component of the corresponding vertex. Something like:

var mesh = CreateGroundFromHeightMap(...);var positions_array = mesh.getVerticesData(BABYLON.VertexBuffer.PositionKind);// let's say I want to know the height at X = 100 and Z = 300 (assuming there are 3000 subdivisions)// I can compute the corresponding vertex position in the array this way:var pos_in_array = 100 + 3000 * 300;// the positions array is constituted like that:// [x1, y1, z1, x2, y2, z2, ..., xN, yN, zN] where N is the last of the vertices var height = positions_array[pos_in_array*3 + 1];  // the Y component is in second place, hence the +1

This is untested code but the principle should work out :)

Link to comment
Share on other sites

Your idea jahow works well i think only in the case where the number of subdivisions in the ground mesh matches the size of the ground mesh. (in that case we have information for all x,z coordinates which are nodes in the mesh ). In my case a 150x150 tile  is subdivided in 4x4 (25 subdivisions). So, from the  below line

var positions_array = mesh.getVerticesData(BABYLON.VertexBuffer.PositionKind);

i get only information about the 25 nodes as expected, but what i needed is the height for all 150*150 points (where coordinates are whole numbers). Also i can't afford making a tile with that many nodes (hurts performance). I guess i'll have to rely on getHeightAtCoordinates after all.

Link to comment
Share on other sites

If your meshes are of reasonable size, this function should work perfectly. My method of reading the Y component of vertices would have worked only if you had one single big mesh covering the whole ground.


A grid mesh with 9 million faces is probably too much anyway to be honest :)

Link to comment
Share on other sites

Every 150x150 tile is an actual ground mesh (i don't use the subMesh implementation from babylon). Each tile has a variable number of subdivisions (depending on the terrain type on that tile). I divided the main ground with the same idea in mind, to improve performance. I also thought that making the tile 150x150 would make the function getHeightAtCoordinates pretty fast.  It just means that i'm doing something wrong. I'll review my code and re-post.


Thank you very much for the clarifying thoughts. :D

Link to comment
Share on other sites

  • 5 months later...

Hi. I did something like that, but I uploaded a map as babylonjs file, . After that, I create a 9 ground meshes, I copy vertices, normals, uvs, from file imported to created mesh, .... all good, but ground.getHeightAtCoordonate function don't work too good. 


It work only for 3 midle tiles, others show, all the time 0. 


I call 


foreach mesh, but not work, and I can't explain. :( 

I'll post a live demo soon...

Link to comment
Share on other sites

Hi, just wondering out loud -


The createHeightMap function is using the image's colors to create a heightmap, using predefined variables (minimum height, maximum height, etc'). So, technically, you could calculate the height using the image's pixels, exactly like the createHeightMap function is doing. And this way you are not dealing with a long 3D calculation. This is a simple calculation that can be done every frame without a problem.


Is this a solution you might be able to use?

Link to comment
Share on other sites

I am not sure how you calculated this, but this is the way the function creates the mesh. So I would guess that the implementation is wrong rather than the function itself doesn't work.

Better - The createFromHeightMap function creates a single mesh in a second or two. Maybe 3. Which means it calculates ALL heights in 3 seconds. So... 

Are you reading the image each time you run the function?

Just create a array[height][width] with all of the heights and you have an O(1) operation to read them... As simple as that.

Link to comment
Share on other sites

This gives me an idea that I won't have time to implement for now infortunately :


if we want something like getAltitudeAtCoord(x, z) => returns y without sending a ray


we could get the positions array

knowing how much subdivisions there are on the map width and on the map height, it's quite simple to  find in the positions array the four vertices around the wanted (x, z) point by comparing x, z and x1, z1, xi, zi values


V1 ----- V2

|  \          |

|   \         |

|    \        |

|     \       |

|      \      |

|       \     |

|        \    |

V3----- V4


then it's quite easy to determine if the (x,z) point is in the facet(V1, V3, V4) or in the facet(V1, V2, V4), again with a simple comparison


at last, it's easy to compute (interpolation) the altitude y of (x,z) from the z values of the facet vertices.


et voilà

an iteration in the array

3 comparisons and an interpolation computation

and no ray emitted  :)


this should be really very very fast


not sure I'm very clear

Link to comment
Share on other sites

ok, let's try to explain

We have a heightmap mesh (or a ribbon), we know that this mesh has m subdivisions on its X axis and n subdivisions on its Z axis

We can get its positions array, containing all the mesh vertex coordinates [x1, y1, z1, x2, y2, z2 ...]


Now, we know the 2D coordinates (x, z) of a point P and we want to get its altitude y on the heighmap.


I guess we can find the y in less than m + n iterations and a calculation.


The algo could be like this :

// first, be sure (x, y) is in the heightmap surfaceif (x < positions[0] || x > positions[m] || z < positions[m -1] || z > positions[positions.length -1]) { return; // x or z are off the heightmap }// find xvar i = 0;var foundx = false;while ( !foundx && i < m) {  if (positions[i * 3] < x ) {    i ++;   } else {   foundx = true;}// now x is in the i-th subdivision on the X axis// find zvar j = 0;var foundz = false;var zidx;while (!foundz && j < n) {  zidx = (j * m) + (3 * i) + 2;  // index of current z coordinate in the array positions  if (positions[zdix] < z) {    j++;  } else {   foundz = true;}// now z is in the j-th subdivision on the Z-axis// So P is between V1, V2, V3 and V4 from the schema of the former post// and V1 coordinates are :// positions[(j * m) + (3 * i)]// positions[(j * m) + (3 * i) + 1]// positions[(j * m) + (3 * i) + 2]// V2 coordinates are : // positions[(j * m) + (3 * i) + 3]// positions[(j * m) + (3 * i) + 4]// positions[(j * m) + (3 * i) + 5]// V3 coordinates are : // positions[((j + 1) * m) + (3 * i)]// positions[((j + 1) * m) + (3 * i) + 1]// positions[((j + 1) * m) + (3 * i) + 2]

idem for V4  (V3 coords + 1) ...


Then it's easy to check wether P is above or under the V1-V2 line in order to determine what facet P belongs to  : V1V2V3 or V1V2V4 (slope of V1 - V4).

According to the facet found, then we just compute the cross product of V1V2 and V1V3 (if it's in the facet V1V2V3, for instance) to get an orthogonal vector to this facet (or we get it from the normals array at the same index).

This gives us this facet plane equation.


Finally we just compute, from this equation and from the given x and z values, the wanted y value.


That's all.


In brief :

- less than n + m iterations to find the vectors V1, V2, V3, V4 around the point P in the positions array 

- a slope computation (V1-V4) and a comparison to determine what facet P belongs to in the quad V1V2V3V4.

- a cross product to get the facet normal, so its plane equation

- a simple calculus to apply this equation to the given x and z to get y


So less then (n + m) iteration and 3 simple math operations.

This should be really faster than a ray intersection process.

Link to comment
Share on other sites

I had an idea of another lead merging the Raanan's pre-computed array approach and the per face altitude computation as explained in my former post.

This should be (I hope) really really fast and should be able to compute thousands of altitudes per frame.


The idea is :

Define a two dimension array, one for width subdivisions, the other for the length subdivisions : alt[j]

Each element of the array will depict a quad V1V2V3V4, so 2 facets

So we precompute from the mesh positions array once for each element as explained in the former post :

- the slope V1V4 in order to determine in what facer the point P(x,z), that want to get the altitude, is

- two vector4 (a,b, c, d) what will be each facet plane equation : ax + by + cz + d = 0

and populate the array with these values :

{slope: val_slope, facet1: vector4_1, facet2: vector4_2}

Given a point P(x,z), we want to get its y on the the heightmap sized (width, length) with m, n subdivisions.

It's easy then to access the relative quad in the array

var i = Math.floor(x * m / width);  // or modulo calculationvar j = Math.floor(z * n / length);  // or modulo calculationvar quad = alt[i][j];

Then with quad.slope compared to (x,z) and a tiny computation, we know if P belongs to the facet1 ou facet2

Once we know the facet, we just apply x, z values to the facet plane equation to get y


This algo has no iteration (expect the precomputation before) then at run time, only 3 simple math operations.


[EDIT] just reading the code of CreateGroundFromHeightmap, this seems to be even more simpler because there aren't two parameters m and n subdivisions, but only one parameter subdivisions used as well for the map width and length

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


  • Recently Browsing   0 members

    • No registered users viewing this page.
  • Create New...