Terrain

[b333n]

Hey there,

what you think, is there actually a performant way to have collisions with a heightfield aka terrain? Would you implement that with the convex hull thingy? What if that terrain has 20-40k vertices (eg 200*200)? Would be very slow, right? Did anybody did that already once, if yes, gimme some inputs, pls :)

Cheers, Ben

BTW: i love that cannon.js thanx for makin it :) <3

[schteppe]

In the current implementation I don't think there is performant way of doing it... Using convex bodies would work but that would not perform very well. The convex limitation forces you to make a LOT of convex bodies, and you will get enormous amounts of duplicate corners and edges. The worst thing is that you'd have to use the naive broadphase algorithm too, since the new GridBroadphase only supports spheres and planes at the moment. You could use a sphere for each pixel and get an okay performance, but that is probably not the kind of ground surface you need I guess?

A heightfield implementation is what is needed.

Stefan

[b333n]

You have any future plans to actually included heightfields? For practical use inside a game it could potentially be very important to have that i suppose. If you have plans, can you provide some timeframe about when you guess that it could be here? Would be very very happy to have that ;)

If there is no such plan, id dig into it then on my own once i find some time. you have some good other sources where i kinda could scope a bit how they have did it, i mean, to what other engine cannon.js is similar, internally? You based the code on some kind of port of any other engine?

Cheers, Ben

[schteppe]

I have no time frame to give you. New features are added sporadically when I'm curious about a new feature implementation and when I some time over.

Guess it would be quite straight forward to support at least sphere/heightfield and particle/heightfield collision in Cannon. For other shapes, I guess triangle/hull intersection could be borrowed from the ConvexPolyhedron class.

It would be pretty awesome to have it in the engine. It opens a lot of doors to new game implementations.

I did not base the code on anything else, the API is mostly inspired by Three.js if anything. The ConvexPolyhedron intersection code was manually ported from Bullet. If you want to learn about the theory behind Cannon.js, read the SPOOK-notes.

Bullet physics could be a good starting point, check out the btHeightfieldTerrainShape. I guess there are other good implementations out there though.

If you want to get started on the implementation, I could give you some hints, or even make you code stubs. Just shout :) The easiest way of doing it would probably be to copy everything that has to do with one of the Cannon.js shapes, rename it, and then implement heightfield-specific stuff.

Stefan

[RCPowers]

Add me to the list of folks hoping for heightfield implementation.

[treeform]

And me too.

[erichlof]

Me three! :)

Stefan, you have created an awesome physics library, and the addition of terrain collision would make it even more awesome! Especially for outdoor adventures RPGs, offroad racing games, Tribes-combat like games, etc.

To all, I think Stefan has all the prerequisite math and functions in place to handle such terrain collisions. IMO the issue is pruning collision tests for speed. A sweeping overview for basic terrain collision would be:

1. Get player/bot position X,Y, and Z
2. Extend a 'feeler' ray from the player's head down through the feet, and keep going until negative infinity or really big number. Basically a long vector pointing in the -Y (downward) direction below the player. You are now guaranteed a collision every frame.
3. Find intersect point inside the polygon.
4. Do the normal physics magic such as bouncing or rolling or sliding with friction that this library already performs so well.

However what is lacking is a way to prune possible intersection tests to speed up the framerate. Like b333n said earlier, if you have a bunch of vertices or triangles to test, the framerate will slow to a crawl in a huge outdoor environment. So again, here's a sweeping overview of a quadtree implementation:

1. Divide the entire terrain into 4 quadrants. Then divide each of those 4 quadrants into 4 quadrants, and so on. You stop when you get to maybe 20 or so triangles in a quadrant. This number '20' could be a global variable for fine tuning on a per-application basis.
2. The initial large 4 quadrants are the 'parents', each quadrant inside them is a 'child' to that parent. So you could have parent(0).child(0), parent(0).child(1), parent(n).child(n).child(2), etc.. or whatever naming scheme you like.
3. When starting the collision testing, get the player X and Z (doesn't matter what the Y is for the moment).
4. Compare that X and Z pair to the bounds of the large 2D parent boxes that you initially created. In other words, there's no sense checking the ocean area of the map when you are in the desert part of the map. :)
5. One of those parents will return a hit. Then search its 'first-born' children. One if those will return a hit. Then check the grandchildren. Each time one of the 4 quadrants will return a hit. Stop when you find the youngest child, maybe the great, great, great-grandchild.
6. Now you have to implement some brute-force checking of ALL the triangles in that last grandchild - there's no other way around it. But hopefully, if your number is 20 or less as stated in the global variable triangle limit, you will check on an average of 20 triangles a frame. I could see 60fps still happening here no problem.
7. Finally you go to number 2 in my generalized basic math list above (extend the ray, find intersection, do the physics that CANNON already does).

I hope I didn't come off as preaching (because believe me the math that Stafan uses is way over my head) but I would like to see a solution to the terrain problem implemented in CANNON (as others have expressed interest also). I haven't combed through all your code, so you might even have a useful pruning function already, with a little future tweaking to fit this solution.

Great library Stefan. All the best to you!

[treeform]

I don't think you even need to do any division. All you need is where in the hight map the ray lands. Specifically in which "grid" does it land. From then you can find from which two triangles of the grid it landed. Find normal and you are done. Its better to just have a single heightmap and no intermediate triangles for speed and memory purposes.

[erichlof]

treeform, you are right. See I don't know exactly how CANNON currently does its intersection tests, but what you are saying makes sense. If there is already a grid object or structure in CANNON and that object can somehow be linked to each of the plane normals in question (because each plane is slanting at a different angle), then we'd be good to go. Does anyone else have thoughts or ideas how this might most easily be implemented?

[Doidel]

Heightfield implementation nr. 4 looking forward to it! :)

[schteppe]

I've started implementing a Heightfield in dev branch. See initial implementation here: https://github.com/schteppe/cannon.js/blob/dev/src/shapes/Heightfield.js Still got some local fixes but stand by, will push them soon.

Currently, I use a temporary convex shape to make intersection tests. But it's still fast.