Efficient collisions versus terrain

Recommended Posts

How do we improve performance for collisions versus a heightmap or mesh or just large numbers of floors+walls?

I'm not looking for true physics (or at least, I don't think that I am). I'm looking to be able to support a few hundred entities all of whom are in contact with a large terrain mesh. Somewhere in the realm of 30-120 players, and 50-1000 npcs or items that had been dropped on the ground would be the ballpark performance goal.

Here is a demo that shows the desired behavior more or less: http://www.babylon.actifgames.com/moveCharacter/  (use mouse look and and Z to walk around). Both this demo and my own attempts at something very similar use `moveWithCollisions` which seems to eat quite a bit of CPU. One to three players is enough to max out the cpu. I presume it results in a collision check between the moving meshes and every triangle of the terrain mesh (just guessing though, not sure how it actually works).

Left to my own devices I'd probably compare the entity positions against the heightmap value at their x,z and just always make sure the y of their feet never slips under the heightmap -- I imagine this optimization could scale to several hundreds or thousands of entities and wouldn't involve a true mesh collision. It also wouldn't work for overhangs or caves, but I don't have any of those yet.

As for collisions with walls or floors or large numbers of other objects that aren't part of the heightmap.. I'm not sure what I'd do. Maybe I'd partition the world up into large cubes and then dice up the existing collision code such that objects were only checked against their nearer spatial neighbors...(the other meshes that occupy the same cube as them)?

But before I go reinventing wheels, I'd figure I'd ask here.

Share this post

Link to post
Share on other sites


if you have a height number  per  camera point (x,y) you can control that full optimized

you need  have 3 point height and calculate normal of current state and calculate next step ( or move direction state) different

and choose be move or locked ( in good algorithm you don't locked just you correct last move state )

i think @jerome do it in terrain if you use that it is optimized 

a wired solution is available too you make scan full scene and make multi stage and calculate all in one time and keep it in array and just read that 

that is not so specific but worked for large scene as i see 


Share this post

Link to post
Share on other sites

Thank you NasimiAsl and jerome.

getHeightAtCoordinates is perfect. It can easily do many many objects on the terrain now.

I just had to turn my height map into a GroundMesh with the correct properties on it.. I was missing some things because I was using  custom vertexData.

I'm not too sure how to do movement, but the following seems to be working nicely:

// skipped: rotate mesh to where player camera is aimed
// unit vector of our movement
let unit = BABYLON.Vector3.Zero()
if (command.forward) { unit.z += 1 }
if (command.backward) { unit.z -= 1 }
if (command.left) { unit.x -= 1 }
if (command.right) { unit.x += 1 }

// rotating the unit vector to the context of this entity
let heading = this.mesh.getDirection(unit)

// full vector, movement and magnitude
let velocityCoef = this.speed * command.delta
let velocity = heading.multiplyByFloats(velocityCoef, velocityCoef, velocityCoef)

// try to move
//this.mesh.moveWithCollisions(velocity) // no more!
this.mesh.position.x += velocity.x
this.mesh.position.y += velocity.y
this.mesh.position.z += velocity.z

let y = this.scene.ground.getHeightAtCoordinates(this.mesh.position.x, this.mesh.position.z)    

// added a little padding to keep the mesh slightly off of the ground
if (this.mesh.position.y < y + 1) {
    this.mesh.position.y = y + 1

This is for a multiplayer game that I'm porting from 2D.

I don't understand how/when to use getNormalAtCoordinates. Is this for making the mesh to appear at the same slope as the terrain? Currently all I have are cubes that always face towards wherever the player controlling them has their camera aimed (like a first person shooter, but if everyone was just a magical cube that floats near the ground).



Share this post

Link to post
Share on other sites

You will need getNormalAtCoordinates in case you want your object to be rotated according to the normal it sits above. This normally isn't necessary with player and NPC meshes, but could be used for dropped items, pickups etc. It does add a bit of realism, in case you have uneven terrain.

Unfortunately I can't find my own benchmark project. I did some testing with CannonJS vs. moveWithCollisions vs. getXAt vs. my own simple physics implementation.


Edit: Quick test: http://playground.babylonjs.com/#BLAJPA

Without rendering the instances it can easily calculate the height of 8000 objects. Didn't try higher than that, but with 60 fps it shouldn't become an issue.

The real issue is if those objects have to collide with each other + walls, props etc. If they do, I guess you'll have to divide your world into a grid as you already mentioned, and only test every individual grid, to prevent massive calculations.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.