How do I pick tiles from an isometric map with slopes?

Question

I'm looking for a way to convert mouse/screen coordinates to isometric map coordinates, with the addition that the world has slopes and cliffs, and I have to be able to tell which quadrant of the tile is being pointed at by the mouse. The textures are handled by OpenGL, so I can't (easily) pick directly based on the tile sprite.

I've found several similar solutions, (e.g. Isometric Tiles Math, XNA Resources & Mouse Maps for Isometric Height Maps with the latter looking most promising) but none of them seem to quite fit my requirements.

My tiles look like this:

What algorithm or technique could I use here?

Answer 1

It's not immediately obvious how you're using OpenGL. If you are just sorting your tiles on the CPU and rendering them from far to near the following method won't help. If you are using an actual isometric projection matrix and a depth buffer this may help, it's how I do picking with OpenGL and perspective projection.

Use the following code to read back the depth from the frame buffer at the given mouse coordinates.

GLfloat depth;
glReadPixels(mouse_x, mouse_y, 1, 1, GL_DEPTH_COMPONENT, GL_FLOAT, &depth);

Next you need to convert your mouse coords into clip space.

glm::vec4 clip;
clip.x = (mouse_x / screen_w) * 2.0f - 1.0f;
clip.y = (mouse_y / screen_h) * 2.0f - 1.0f;
clip.z = depth * 2.0f - 1.0f;
clip.w = 1.0;

You then need to multiply your clip space coords by the inverse view projection matrix.

glm::mat4 inverse_view_proj = glm::inverse(projection_matrix * view_matrix);
glm::vec4 pre_pers_div = inverse_view_proj * clip;
glm::vec3 world_position = pre_pers_div.xyz / pre_pers_div.w;

The world_position vector now contains the location of the mouse in three dimensional world coords. You can feed this into your collision detection code and see which object it is colliding with.

Answer 2

Summary: Make a 3d mesh exactly the size of your terrain. Then do a raytrace trough the mouse towards the terrain. This will give you the x and z coordinate of the tile. Now from the z coordinate you can calculate the y coordinate of the tile without elevation. Then you can use one of your links to calculate the tile at that position. Now some simple math will give you the quadrant.

Your terrain is probably created from a 1D or 2D array of height values. We can use this to create the 3d mesh. I am using Bullet here for some examples.

std::vector <unsigned char> heights; //This 1D vector contains the heights
width = 64;
height = 64;
//We make a shape for the terrain using the heights. We need to give bullet the width
//and height of the terrain, the heights, the scaling, the minimum height, the maximum
//height, the up axis (0:x,1:y,2:z), the data type and whether to flip quad edges.
btHeightfieldTerrainShape* terrainShape = new btHeightfieldTerrainShape(width, height, heights.data(), 1, 0, 255, 2, PHY_UCHAR, false);

//We make the Bullet rigidbody using the shape
body = new btRigidBody(0, new btDefaultMotionState(), terrainShape);
body->setFriction(0.8f);
body->setHitFraction(0.8f);
body->setRestitution(0.8f);

//Bullet automatically centers the body so we undo that
//Be sure to move and rotate the body in such a way that it matches your terrain
body->getWorldTransform().setOrigin(btVector3(width / 2 - 0.5f, height / 2 - 0.5f, 255/2.f));   
body->setCollisionFlags(body->getCollisionFlags() | btCollisionObject::CF_STATIC_OBJECT);

//And finally we add it to the world.
physics.dynamicsWorld->addRigidBody(body);

So our mesh is ready and positioned. We are ready to start raytracing. Now I am not familiar with ray tracing trough a mouse so I hope you are able to do that yourself with the help of the internet.

So once we have the coordinates we can calculate which tile is under the mouse.

Suppose the arrows in the image indicate positive directions.

Tile column under mouse = std::floor(raycast.x);
Tile row under mouse = raycast.y - raycast.z

And that's about it I believe.

Answer 3

The setup:

1. In the map data add an extra field for the render order.
2. As you render each tile is order increment the render order by one.
3. For each tile make a AABB in view coords (the same coordinate system as the mouse is in) which is the same size as the tile and place it into a quad tree for quick access.

To retrieve:

1. Find the AAAB at the current mouse location by searching the quad tree. If multiple tiles are found sort them according to the render order.
2. Once the correct tile is known find tile in the tile map (bitmap image) and covert the mouse coordinates to the local coordinates of the tile image.
3. Sample the pixel at the final location and if it's not transparent then assume a tile has been hit.

Now you know which tile was hit and you'll need to map that to the geometry of the slopes. This is very tedious as each tile will have it's own formula how how the x and y axis maps to which z value so it's best left to figure out on your own.