Efficient collision with a big mesh


I’m currently working on a space exploration game ( https://m.youtube.com/watch?v=ho4uUd2QaVE ) and I’d like to add collisions with terrain.
I’m new to 3D game development and I’m probably missing some important and obvious solutions to problems so here is what I’m going to do: I’m going to transform my Plane geometries in order to have them as a regular plane (not rotated) to be able to “hash” the coordinates of the player to get the closest vertices and do the collision with them.

But I’m sure there is a more efficient way to do that. I just don’t know it. Something using shaders ? A thing based on octrees or a related data structure ? Something else ?

What would be the most efficient way for me to get the ground distance in real time ?

Thanks !

1 Like

You need a spatial index. Something like an octree or a bvh or kd-tree. Those are special data structures for efficient spatial queries. With those you should have no issue when it comes to collision detection.

About collision detection in general. This is related to “ray casting”, you have a point in space and some direction, that forms a way, and then you want to query your geometry (mesh) to find out which triangles are intersected by the ray, you also find the collision points. You can then sort the collision points by distance from the ray “origin” to find out which point is the closest. It sounds convoluted, but it’s actually pretty fast and efficient. It’s state of the art, meaning that all major game engines work this way.

three.js already has ray casting tools, you can find out more in the documentation and examples.

Your game looks quite neat, by the way, congratulations!


Thanks a lot, so, the octrees are the best for my scenario ? Great ! I wanted to make sure that I was not going to miss something more powerful/faster ! And regarding the raycasting, thanks again, I was planning to use it with the smaller things I would have found using whatever I would have used :slight_smile: My initial concern was that Three.js raycaster went through all the triangles in a geometry and it was too slow to be used directly in my case (20ms for a raycast against a planet using bounding boxes).
And thanks for your kind comment about my game :slight_smile:

1 Like

All of the ones I mentioned have pros and cons. I suggest octree as it’s the most straight-forward one to work with, especially in the dynamic environment. Speed and memory usage will have little relevance to you, i think. Since all of these will be so fast that you’ll probably never have an issue with this part in the future. For the most part it’s a judgement call.