Ray casting through terrain mesh + Octree ( Mesh collision )


I’m currently in development of a terrain editor which i will use for my game. One thing that is partially stopping my development is that I don’t have collision detection implemented between mouse ray cast and the terrain mesh.

The terrain is consisted of triangles and can be lowered and raised.Also the x and y values of the mesh don’t change. Of course what i need to do is ray cast through my mouse positions and get intersected triangle. I would get the point on the triangle using Barycentric coordinates. Just I’m not quite sure how does octree come into play here. As far as I understand it it works like a 3d quadtree, splitting the box into smaller box that the ray intersects. But which box do i choose ? How do i know which box is the closest one to the terrain, if either raised or lowered terrain ? How many subdivisions would i have? I was thinking on having as much as i have tiles( basically the last level of subdivisions would correspond to a x^3 box).

Right now i’m just doing collision with the 0 Z-value plane, and it works okay, but if the terrain is a bit raised then this can give faulty results.

Other two methods that i found is to iterate through the mesh, which of course is insanely inefficient; the other is to project the terrain in reverse and then i guess do some checking with the mouse coordinates (think it’s called z-buffer checking or something).

If anyone has any other ideas i’m all ears. Just note that the algorithm should be an efficient one (of course this depends on the implementation) and accurate.

Thanks !