getHeightAtCoordinates alternative

[newbie]

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)

[jahow]

Hey,

 

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

[newbie]

Hi jahow. I actually already subdivided the ground mesh in chunks of 150x150 and the getHeightAtCoordinates still lags behind. I'll try your sugestion and see how it goes. Thank you!

[newbie]

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.

[jahow]

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

[newbie]

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.

[MarianG]

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 

m[i].refreshBoundingInfo();

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

I'll post a live demo soon...

[RaananW]

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?

[jerome]

nice idea !

[MarianG]

This is not a bad idea, but in this case I have another problem. 

 

Take a look in console. http://prntscr.com/9hkj9a

For almost the same pixel color, i get extremely different values. 

In this case the character will go in zigzag.

[MarianG]

And surprising, getHeightAtCoordonate function is faster than using Image pixel. 

[RaananW]

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.

[jerome]

actually these data already exist in the positions array of the mesh vertex data object : [ x1, y1, z1, x2, y2, z2, x3, y3, z3, ... xN, yN, zN ]

[RaananW]

Yes, you will have to calculate the position in the array. But it will work as well :-)

[jerome]

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

[jerome]

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.

[MarianG]

Hi.

Thank you both, for the good explanations. 

Unfortunatelly I haven't time now to implement, but I hope, next week I'll do.

 

I wish you happy holidays.

[jerome]

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

[jerome]

BTW,

 

is it possible to get back the positions array of a heightmap ground ?

it doesn't seem to have a PositionKind vertex data array ... 

 

[EDIT] here's a PG : http://www.babylonjs-playground.com/#3NEC1

See the lines 41-42 => positions is null

[jerome]

heeelp, I would like not to scan the image again  to re-compute the positions.

[MarianG]

Hi jerome.

Positions are there, but the ground is not ready yet. It happens...

 

I added a setTimeout function.

http://www.babylonjs-playground.com/#3NEC1#1

[jerome]

oops

 

I'm feeling dumb

I just forgot the image download time, tssss

[RaananW]

The last variable of the create heightmap function is a callback function that is called once the geometry was created. So no need to assume downloading time with getTimeout!

here - http://www.babylonjs-playground.com/#3NEC1#2

[jerome]

yep thank, that's the one I used for my proto of getAltitude

[jerome]

My algo works fine now, 

I'll do a PG soon