#### Archived

This topic is now archived and is closed to further replies.

# Heightmapping and Tile Selection

This topic is 5866 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello, I have an isometric engine that uses Direct3D to render the tiles. Originally, all tiles were at the same elevation so I didn''t have too horribly much trouble writing an algorithm that will allow tile selection with the mouse. What I did was find the square 32x32 region that the cursor was in, and then I just found which of the five tiles within that region were under the cursor by doing some tests against the tiles'' diagonal bounding lines. But, alas, a few days later I added heightmapping to the picture and my selection code is now moot (such is the way of the unplanned programmer). But I found that with heightmapping, tile selection is pretty darn near impossible. After some thought, a little light shown though in that I realized the x coordinate is not modified, so it still remains accurate. But the y coordinate is now a screwy mess. Since the tiles above or below 0 elevation have no definite shape, and its hard to tell where one ends and the other begins, I don''t know how the heck I am supposed to approach this beast. I''m sure someone else has hit this wall before, but unfortunately the search feature seems to be down. Any suggestions out there? Thank You.

##### Share on other sites
You can generate a pick-ray. Travel along it. Your xz coordinates are coordinates for your heightmap. Check to see if the y coordinate of your heightmap is greater to or equal to the y value of your current position along the ray. If it is, stop traveling along the ray; you''ve found the tile.

If your map contains faces which are not perfect quadrilaterals, you''ll need to add an extra step to this method to individually test the two triangles of each tile individually.

##### Share on other sites
Thanks-

I''ll try this out. I had considered travelling down from the top of the map, but the odd shape was what really had me.

##### Share on other sites
Personally, I use barycentric coordinates for isometric tile picking. The x coordinate is, as you say, no problem, then I compute all tiles that could possibly be at that y position (you have a min and max height) and then check if the point lies in the tile - I split the tile into two triangles, take two sides of the triangle and get their vectors, as well as their origin vertex and then transform the screen coordinates into a parametric form.

p0...p2 are 2D vectors and define the corners of the triangle
m is a 2D vector with the mouse coordinates

vectors of triangle edges:
v0 = p1 - p0
v1 = p2 - p0

Every point on the screen can also be represented as
X = p0 + v0 * s + v1 * t
where s and t are the (scalar!) parameters. If 0 <= s <= 1 AND 0 <= t <= 1 AND (s + t) <= 1, the mouse click point is inside the triangle.

Now, we just have to calculate s and t:

m = p0 + v0 * s + v1 * t

split it into equations for each coordinate:

m.x = p0.x + v0.x * s + v1.x * tm.y = p0.y + v0.y * s + v1.y * tv1.y * m.x = v1.y * p0.x + v1.y * v0.x * s) + v1.x * v1.y * tv1.x * m.y = v1.x * p0.y + v1.x * v0.y * s) + v1.x * v1.y * tv1.y * m.x - v1.x * m.y = v1.y * p0.x - v1.x * p0.y + (v1.y * v0.x - v1.x * v0.y) * s
therefore:
s = (v1.y * m.x - v1.x * m.y - v1.y * p0.x + v1.x * p0.y) / (v1.y * v0.x - v1.x * v0.y)
...which you can use in your code, after some clean-up.
Do the same for t = ? and then perform the check on s and t I mentioned above.

That's the fastest method I've been able to come up with, and I doubt there's anything faster that's not a derivative of this method.

- JQ
Full Speed Games. Period.

[edited by - JonnyQuest on September 12, 2002 6:20:22 AM]

##### Share on other sites
Great! Thanks! This is just what I was looking for.

##### Share on other sites
One more question... does it matter which points on the triangle I use for p0, p1, and p2? For triangle one I have the left, top, and bottom vertices (respectively) and for triangle two I have each point set to the the right, top, and bottom vertices.

Also, is this the correct calculation for t?:

t = (v1.x * mouse.y - v1.y * mouse.x - v1.x * p0.y * p0.x) / (v1.x * v0.y * v0.x)

Thanks again...

##### Share on other sites
I''m pretty sure the points only need to be in the right winding order.

##### Share on other sites
The order is pretty much arbitrary, although I prefer p0 to be one of the vertices that is shared between the two triangles making up the tile, so I get sort of the same barycentric coordinate system for both. This is because you could send units to any location inside tiles, not just the centre, last time I used this algo. If you''re just worrying about getting the tile itself, don''t worry about it.

Your formula for t seems a bit screwy. it should be of the same form as the one for s, I think you might only even have to swap around v0 and v1, but if you''re having troubles I can work it out for you.

- JQ
Full Speed Games. Period.

##### Share on other sites
I tried inverting all the v0''s and v1''s in t, but it is still coming out as 0 everytime.

It''s entirely possible that I might be doing something wrong somewhere else. Here is the code where I do the containment test.

  // ptWorld is the world position of the mouse coordinate// ptTile is the tile that we want to do point test on// ptTilePos is the world pos of ptTile''s upper left corner// Do a point containment test on the tilePOINT ptLeftSide, ptTopSide, ptRightSide, ptBottomSide;POINT ptVector1, ptVector2;int nTileCenter = m_nTileSize >> 1;int nEdge1, nEdge2;// Find the corner points of the tileptLeftSide.x = ptTilePos.x;ptLeftSide.y = ptTilePos.y + nTileCenter;ptTopSide.x = ptTilePos.x + nTileCenter;ptTopSide.y = ptTilePos.y;ptBottomSide.x = ptTopSide.x;ptBottomSide.y = ptTilePos.y + m_nTileSize;ptRightSide.x = ptTilePos.x + m_nTileSize;ptRightSide.y = ptLeftSide.y;// Get the vectors of two of the sidesptVector1.x = ptTopSide.x - ptLeftSide.x;ptVector1.y = ptTopSide.y - ptLeftSide.y;ptVector2.x = ptBottomSide.x - ptLeftSide.x;ptVector2.y = ptBottomSide.y - ptLeftSide.y;// Test if point is within trianglenEdge1 = (ptVector2.y * ptWorld.x - ptVector2.x * ptWorld.y - ptVector2.y * ptLeftSide.x + ptVector2.x * ptLeftSide.y) / (ptVector2.y * ptVector1.x * ptVector1.y);nEdge2 = (ptVector1.x * ptWorld.y - ptVector1.y * ptWorld.x - ptVector1.x * ptLeftSide.y + ptVector1.y * ptLeftSide.x) / (ptVector1.x * ptVector2.y * ptVector2.x);// If point is not in this triangle, check the other oneif (nEdge1 < 0 && (nEdge1 + nEdge2) > 1){	// Get the vectors of two of the sides	ptVector1.x = ptTopSide.x - ptRightSide.x;	ptVector1.y = ptTopSide.y - ptRightSide.y;	ptVector2.x = ptBottomSide.x - ptRightSide.x;	ptVector2.y = ptBottomSide.y - ptRightSide.y;	// Test if point is within triangle	nEdge1 = (ptVector2.y * ptWorld.x - ptVector2.x * ptWorld.y - ptVector2.y * ptRightSide.x + ptVector2.x * ptRightSide.y) / (ptVector2.y * ptVector1.x * ptVector1.y);	nEdge2 = (ptVector1.x * ptWorld.y - ptVector1.y * ptWorld.x - ptVector1.x * ptRightSide.y + ptVector1.y * ptRightSide.x) / (ptVector1.x * ptVector2.y * ptVector2.x);	// If point is not within this tile, go in the proper direction	if (nEdge1 < 0 && (nEdge1 + nEdge2) > 1)	{                //.......	}

##### Share on other sites
Edge1 and 2 must not be integers! they''re in the range of 0 to 1 if the triangle was clicked. Do the division using floating-point variables.
To fix it, you''ll have to make the edge variables floats and put casts around both brackets in the formula.

Are you sure about the Edge2 formula?

In any case, your conditional isn''t right either.

- JQ
Full Speed Games. Period.

1. 1
2. 2
3. 3
Rutin
23
4. 4
5. 5

• 13
• 19
• 14
• 9
• 9
• ### Forum Statistics

• Total Topics
632931
• Total Posts
3009293
• ### Who's Online (See full list)

There are no registered users currently online

×