getHeightAtCoordinates alternative

[jerome]

et voilà : http://www.babylonjs-playground.com/#1QC4YQ#0    60 fps on my fast laptop

[EDIT : 60 fps also on my old laptop !]

the same with the legacy method getHeightAtCoordinates() : http://www.babylonjs-playground.com/#1QC4YQ#1 less than 1 fps !

 

Here there are 400 balls in a SPS. You can change this number at the line 131

You can also change the size and the number of map subdivisions at the line 108-110. This shouldn't alter the speed of altitude computation, only the the time needed to precompute the array.

 

Under the hood, an array of quads (sized subdivisions * subdivisions) is created.

It is populated with  some quad elements.

 

Remember this schema :

a quad is two triangular facets.

We know the 2d coordinates (x,z) of the point P(x,z) and we want to know its y

 

V1 ----- V2

|  \          |

|   \         |

|    \        |

|     \       |

|      \      |

|       \     |

|        \    |

V3----- V4

So a quad element of the array is :

- a vector2 (c, h) : the slope (V1V4) 2D line equation cx + h = z, used to check if P(x,z) in the facet 1 or in the facet 2, or, in other words, if P is under or above the line V1V4 in the plane xOz.

- two vector4 (a,b,c,d) defining the two facet 3D plane equations : ax + by + cz + d = 0, simply computed from their respective normal vectors.

 

So when you pass the (x,z) coordinates, the algo retrieves directly by its index the related quad in the array, checks what facet the point P(x,z) belongs to and then just apply the facet plane equation to (x, z) to compute y.

 

No iteration at all once the array is populated. Just a comparison and an operation... very very fast ! 

 

ex : http://www.babylonjs-playground.com/#1QC4YQ#2

600 balls still run at 60 fps on my recent laptop (50 fps on the old one)

 

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

800 balls, 200 subdivisions => 60 fps  (33 fps on the old one)

 

Actually, I guess the limitation is more due to the big sps rendering than to the altitude computation

[jerome]

Note : there's no physics engine in the former example.

The balls just roll until the map bounds and go in the other way (bounce ?) when they reach them.

Obviously they follow the map relief also... what was the goal of the exercice 

 

 

[EDIT] can't stop playing

2000 balls

60 fps

 

http://www.babylonjs-playground.com/#1QC4YQ#4

[RaananW]

Yo! Math-meister J! this is totally awesome

[GameMonetize]

SPS is REALLY powerful!!

[jerome]

Actually, the SPS does nothing more than usually : animating solid particles.

The new stuff here is the way the altitude from the map is computed without using any ray intersection, but just the facet plane equations instead.

[GameMonetize]

You are too modest

[MarianG]

Wonderfull 

[jerome]

"modesty" ? I don't even know the word 

 

No, what I meant is that the gain was got in this example by both local methods computeHeightMapQuads() / getAltitudeAt() used instead the legacy getHeightAtCoordinates().

Under the hood : knowledge of the map geometry + plane equation precomputation vs 3D ray intersection

 

You would have got the same gain by using standard meshes, instances or clones instead of the SPS.

I used the SPS only to deal with a big amount of balls in order to stress the altitude computation.

 

 

same with just a little big balls on a big map to understand better how they roll : http://www.babylonjs-playground.com/#1QC4YQ#5

[edit] more didactic example with wireframe and only 20 subdivisions so the facets are well visible : http://www.babylonjs-playground.com/#1QC4YQ#6

[GameMonetize]

It could be interesting to add these functions to GroundMesh

[jerome]

I'm thinking about it.

The method getAltitudeAt() has to know about the ground geometry because it links the quad array indexes to the x,z coordinates to be ultra-fast and do no iteration at all.

All the magic is here :

BJS groundMap (x, z) geometry : https://github.com/BabylonJS/Babylon.js/blob/master/src/Mesh/babylon.mesh.vertexData.ts#L1316

quad retriever : 

    var col = Math.floor((x + options.width / 2) * options.subdivisions / options.width);    var row = Math.floor(-(z + options.height / 2) * options.subdivisions / options.height + options.subdivisions);    var quad = quads[row * options.subdivisions + col];

As you can see, it's just the inverse computation : (row, col) => (x, z) vs (x,z) => (row, col)

 

I need to check if all the ground types in the GroundMesh (in particular, tiledGround) share the same way to build their geometries or else if there's a way to generalize this kind of access.

If not, this method would work only for heightmap-like ground : heightmap, ground, ribbon ... successive quads with vertex reuse.

 

As a side note, this feature creates an array sized subdivisions * subdivisions. So it can be a big array and I want the user to explicitly ask for this creation when creating the ground because of the RAM used.

This could be an option :

createGroundHeightMap(name, url, {withAltitudeArray: true}, scene);

In brief, if the user needs to get the height only for one mesh or only sometimes and wants to spare memory, he would use the legagy method getHeightAtCoordinates() emitting a ray.

 

But if he needs a permanent usage of the map altitudes (many meshes, many access or performance) but with the related spent memory, he would then use getAltitudeAt()  using the quad array.

[jerome]

Like Raanan suggested, another lead would be :

 

- to keep a reference to the image buffer with the height map ground object

- to convert the coordinates (x, z) of the point P to 2d coordinates into the canvas image and to get the pixel color values

- to reconvert these pixel values to y value

 

pro : no need for an extra array, not that much computation so maybe barely slower than the former process

con : works only for image based grounds, need for keeping the buffer (to be compared in term of memory used by the array) that won't be garbage collected

 

note : I can't see that the 2d canvas is deleted in the current code, so I guess the buffer memory stays allocated anyway after the 3d ground is created

 

note2 : The array of the former process is sized subdivisions * subdivisions

So the memory used is directly a function of the number of subdivisions = subdivisions * subdivisions * (sizeof_Vector2 + sizeof_Vector4 + sizeof_Vector4)

Then, if the size of a js float is 4 bytes, the array memory should be =

sub * sub * (2 * 4 + 2 * 4 * 4) = sub * sub * 40 bytes

 

The size of the buffer is, I guess, its number of pixels times four = 4 * width * height bytes

 

So in term of memory, the array process is always worth it roughly as soon as width * height > 10 * subdivisions *subdivisions

If the image is squared : width = height = side pixels

this means that we need subdivisions =<  side / 10  to ever get a smaller array than the image memory.

 

example : if the image is a square of 300 pixels per side, and if you set 30 subdivisions, the array size is smaller than the image size.

 

Just to understand what quantities we are talking about :

If you set 100 subdivisions, the array will be sized : 100 * 100 * 40 = 400 000 bytes, so 390 Kb

If you set 50 subdivisions, the array is : 50 * 50 * 40 = 100 000 bytes, so 97 Kb

It's easy to compare to the image size then.

[jerome]

Just a question :

 

is the current method getHeightAtCoordinates() pertinent for the other mesh types than height map grounds ?

[jerome]

After reading the code of the different ground types, it seems that :

 

the height map ground and the standard ground share exactly the same geometry so the method getAltitude should work out of the box for both

the tiled ground has a different geometry (more internal subdivisions)

only the heightmap ground has a height, it is to say y values different from zero

 

So, as far as I understand, the current method getHeightAtCoordinates() makes sense only for the height map ground. 

Then I could add the method getAltitudeAt() in the class GroundMesh at the same level and usage than getHeightAtCoordinates(), knowing that the results could be weird for a tiled map because they aren't that pertinent.

 

As a side note, the method getAltitudeAt() should work also for a ribbon out of the box, if this ribbon is built like a map (stripes along x and z with an altitude along y).

But as it is a only for a specific case of ribbon, I don't guess it's worth it to implement it at the Ribbon level. 

Instead, I think I will provide also the function in vanilla js as it is in the Userfunctions extension so people will be able to use it for their own needs on something else than a heightmap.

[jerome]

@DK : unless you prefer that I change the current getHeightAtCoordinates() directly by this algo ? knowing it won't be pertinent for tiled grounds ...

[jerome]

continued here : http://www.html5gamedevs.com/topic/19615-getaltitudeat/?p=111174