# 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 !

• An octree is great for arbitrary meshes, but for a heightfield terrain it's more general than you need, since you don't have to contend with overhangs, floating geometry, etc. Your case is almost "2.5D" — you can imagine your ray drawn across the 2D ground plane. In each square drawn on this plane, your line achieves some minimum and some maximum height, as does the terrain in that square. You can quickly skip over any squares where these ranges are disjoint, and zoom in closer only where the ranges intersect, until you've narrowed down to a single mesh quad. May 8, 2020 at 13:41
• @DMGregory If I understand you correctly, I should in a way project the ray vector onto this plane and get the intersected cells ? And then for each cell check, as you've said, max and min distance from the ray and max and min height in the cell (rect) and if one of these heights is higher than the ray distance then it intersects it ? A bit hard to tell without a picture. :) May 8, 2020 at 19:07