Archived

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

Heightmapping and Tile Selection

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
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 * t
m.y = p0.y + v0.y * s + v1.y * t

v1.y * m.x = v1.y * p0.x + v1.y * v0.x * s) + v1.x * v1.y * t
v1.x * m.y = v1.x * p0.y + v1.x * v0.y * s) + v1.x * v1.y * t

v1.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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 tile

POINT ptLeftSide, ptTopSide, ptRightSide, ptBottomSide;
POINT ptVector1, ptVector2;
int nTileCenter = m_nTileSize >> 1;
int nEdge1, nEdge2;

// Find the corner points of the tile


ptLeftSide.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 sides

ptVector1.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 triangle

nEdge1 = (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 one

if (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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Changing nEdge1 and nEdge2 to floats was one of the first things I tried, but it still came out as 0 so I changed back to ints. The conditional checks to see if the number is between 0 and 1, I guess I wasn''t thinkin'' too straight

I''m not sure if the edge 2 (or t) equation is right or not.

I wrote the conditional hastily, but it should be:

if (nEdge1 < 0 || nEdge2 < 0 || (nEdge1 + nEdge2) > 1)
// Not contained

Share this post


Link to post
Share on other sites
Hmm, it shouldn''t be coming out as 0. You''re doing something very wrong then. Have you had a look through with a debugger, to see what values the variables have? Changing the edge variables to floats won''t fix it by the way, you have to make the division floating-point as well. If you leave it as integers, it''ll always do rounding.
Another thing: does it give you something other than 0 if you click outside the tile?


- JQ
Full Speed Games. Period.

Share this post


Link to post
Share on other sites
I tried putting parenthesis around the whole thing when casting to float, and s and t aren''t always 0 anymore. Just some of the expression was being converted to a float, I guess.

But now, the conditional is failing TOO much I tried clicking on tiles a few dozen times, and only a couple of times the containment check on the first triangle would succeed. The triangle 2 test always failed. I noticed that s is almost always negative. I tried changing the calculation for the vectors in the second check to:

ptVector1.x = ptRightSide.x - ptTopSide.x;
ptVector1.y = ptRightSide.y - ptTopSide.y;
ptVector2.x = ptRightSide.x - ptBottomSide.x;
ptVector2.y = ptRightSide.y - ptBottomSide.y;

Since the coordinates for the right side are greater then the top and bottom (at least for x) the vectors were always negative before. This change caused the second triangle test to succeed a lot more, and the tile clicking was more accurate. I''m going to try changing all vector calculations so the lower number is subtracted from the greater number (resulting in positive vectors) - maybe this will result in more accurate calculations:

Triangle 1:

ptVector1.x = ptTopSide.x - ptLeftSide.x;
ptVector1.y = ptLeftSide.y - ptTopSide.y;
ptVector2.x = ptBottomSide.x - ptLeftSide.x;
ptVector2.y = ptBottomSide.y - ptLeftSide.y;

Triangle 2:

ptVector1.x = ptRightSide.x - ptTopSide.x;
ptVector1.y = ptRightSide.y - ptTopSide.y;
ptVector2.x = ptRightSide.x - ptBottomSide.x;
ptVector2.y = ptBottomSide.y - ptRightSide.y;

I''ll tell you how this works.

Share this post


Link to post
Share on other sites
It took a while for me to get back here... my isp is having trouble.

Unfortunately, my idea didn''t work. I''m still not getting accurate results. Could you check the t calculation for me?

Thanks for hanging with me for so long

Share this post


Link to post
Share on other sites
Just a quickie, but:

I think t should be:
t = (v0.y * m.x - v0.x * m.y - v0.y * p0.x + v0.x * p0.y) / (v0.y * v1.x - v0.x * v1.y)

But I''ll check it later on.

Are you getting sensible values for s by the way?

- JQ
Full Speed Games. Period.

Share this post


Link to post
Share on other sites
Both s and t appears to be sensible values, although t tends to have more extreme numbers in both directions.

I''ll try you expression tonight.

Share this post


Link to post
Share on other sites
Glad you could finally get it working.

You know, if you align vector 0 and 1 to map coordinates (i.e. v0 is along map x, v1 is along map y or vice versa) you get sub-tile correct map coordinates. Just add s to the x map coordinate of the tile, and t to the y map coordinate, and you get map coordinates like (13.6, 6.26) - that can be very useful...

- JQ
Full Speed Games. Period.

Share this post


Link to post
Share on other sites