0
\$\begingroup\$

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 !

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – DMGregory May 8 at 13:41
  • \$\begingroup\$ @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. :) \$\endgroup\$ – Abovegame May 8 at 19:07
1
\$\begingroup\$

I've managed to implement the ray cast-terrain mesh collision detection.

First I take the origin of my ray and just "project" it onto a XY plane (basically just take X and Y coordinates of the origin vector). Then I calculate the end vector based on the distance I want and the direction (unit vector) from my ray struct.

When that's done, I use that newly formed line (origin->end) to intersect my terrain quad and only keep the line that is inside the quad; at the same time I am able to calculate my intersection points using the Line-Edge intersection (https://stackoverflow.com/a/1968345/9200518 - the one I used).

Since I've got the point I need, thus the start and end tile of my line, as a reference I've used this, which is similar to Bresenham's line algorithm.

Upon getting all the quads that my line intersects I just checked each triangle per quad if It intersects.

I haven't tested this as far as performance goes, but it might help out someone!

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.