# [C++,OpenGL] Optimizing space conversions for find-click-on-grid application

## Recommended Posts

I have a 2 dimensional grid of tiles affixed at some arbitrary orientation in 3D space (in OpenGL terms, I'm referring to the xz-plane and a gluLookAt camera). What I'm trying to achieve is a conversion from a screen click to some point on this grid. Now because the orientation is arbitrary, the conversion is difficult. Ultimately I used what amounts to the same code from the seperating-axis theorem tutorial on this site by converting the world coordinates (0,0,0), (n,0,0) and (0,0,n) where n is the width of the square tile to the 2D screen coordinates a,b, and c respectively. b-a gives me axis1 and c-a gives me axis2. I can use these axis for any tile, since they're all aligned on the same plane. I then projected the mouse's screen coordinates (I'll call it some vector m) onto these new axis vectors and then yielded a scalar for the first axis through m dot axis1 and the second through m dot axis2. Like I said, it's exactly the same as [url="http://www.gamedev.net/reference/programming/features/2dRotatedRectCollision/page2.asp"]this[/url] So far so good. The problem now is optimization. I know that if a dot axis1 < m dot axis1 < b dot axis1 AND a dot axis2 < m dot axis 2 < c dot axis2 then the click is within the tile with it's corner at the origin... but is there any way to quickly get the equivilant a, b and c values for the other tiles? I'm even thinking there's a simple trick that I'm overlooking to get the tile from just the scalar, so I wont have to check every tile once for each axis. The alternative, converting from world space for three points per tile, sets off all of my optimization alarm bells. And it's pretty big, considering there are at minimum 500x500 tiles. I have a fleeting suspicion that the two axis themselves have enough information for that. I'm drawing a blank when it comes to what scalar to multiply it by if that's the case.

##### Share on other sites
I may be misunderstanding something.

Couldn't you do a simple ray-plane intersection to get the point's coordinates on the xz plane? then if you have consistent indexing, it's easy to find the square.

The ray is the eye-mouse_pos ray, transformed with the inverse of the modelview matrix (or something like that, sorry, I'm a bit tired now, but maybe the idea is enough)

##### Share on other sites
My understanding is that you have a regular grid on a quad in 3-d space. You want to be able to 'mouse pick' this quad, and then find out which grid cell was clicked. (If I'm wrong about that, you can ignore the rest of this post, as it will be irrelevant :)

First you'll need a local coordinate system for the quad. There are a few different ways you could set this up, but it would probably be convenient to place the origin at one of the quad's corners. The basis vectors will then be two perpendicular edges of the quad, normalized (similar to what you have now) and their cross product. Take the origin and three basis vectors, combine them into a matrix, and then invert the matrix; you can then use this inverted matrix to transform points from world space into the local space of the quad.

The steps are then:

1. Intersect the mouse ray with the plane in which the quad lies.

2. Transform the intersection point into the local space of the quad.

3. One of the elements of the transformed point will be zero (or close to it), and can be ignored.

4. The other two elements can be used to determine whether the intersection point falls within the quad, and (through some simple arithmetic) can also be used to determine which cell was clicked.

It sounds like you're already doing most of this in some form or another, so maybe it's really only step 4 that you haven't quite put together yet.

##### Share on other sites
Yes, google searching another topic eventually linked me to a question about ray picking and I realized that it makes a heck of a lot more sense. Thank you very much for the help, I was over thinking it and headed in the absolute wrong direction.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628278
• Total Posts
2981785

• 10
• 11
• 17
• 13
• 9