Mouse clicking in 3D space?

[zFollette]

Hey, so I want to get a basic understanding of how to click on things in a 3D space, in my case cubes. From what I am reading, Ray Picking is what I am looking for. I can't find a tutorial on it at all. So if anyone can point me to one, or teach me themselves, that would be wonderful.



I assume something like that would just be simple, calculating when I am hitting that cube.

[opiop65]

It's far from simple...
http://www.java-gaming.org/topics/raycasting-explained-source-samples-included/31446/view.html
I still barely understand it myself, and I've been trying to figure it out for about a month now.

[zFollette]

I can't thank you enough for the quick reply. Especially with content that I haven't seen before. I'll take a look at it.

Games published by our own members! Check 'em out!

[lcass]

I would personally use a vector from the camera to the mouse (with a 1 delta in z) with this when I click I would check what was the first object on the vector path and do the function onto that object.

[opiop65]

Well... Yes that's how it works. The issue is actually implementing all the math.

[lcass]

well in simplistic terms basically the vector path increments (x+ y+ z+) are just the difference between the mouse and player then just adding these on each time is fairly simple. However the mouse position would have to be 1 / mousex 1/mousey and rotxyz(1);

[pixelprime]

Based on the way I accomplish this very task, and similar to the responses above, you can follow this sort of code...

(EDIT: I'm hastily typing this out at work, so apologies if the code is a bit sloppy)

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60   61   62

public static Block pickBlockAtCursor() {    // grab a reference to your camera's current world position   float camX = camera.x;    float camY = camera.y;    float camZ = camera.z;    // you'll need your camera's orientation in space too. We'll assume your   // camera angles are in degrees.   float camYaw = camera.yaw;    float camPitch = camera.pitch;    // now decide what kind of resolution you want:   // a longer test distance will allow you to pick blocks   // further away, while the test iteration distance will   // improve the accuracy of the picking algorithm.   // Balance this how you see fit, but the iteration distance   // should really be around 1/3 of your block's actual size   float maxDist = 50;    float iterationDist = 0.5f;    // now work out how many iterations along the camera vector   // we'll be testing with   int iterations = (int)Math.floor(maxDist / iterationDist);    // now we'll loop through and get each test point in 3D space   // along the test vector   for (int i = 0; i < iterations; i++)    {       // how far in front of the camera will this iteration take us?      float currentDist = iterationDist * i;       // get the current delta point in space for this iteration      float f = (float)Math.cos(Math.toRadians(camPitch));       float addX = currentDist  * f * (float)Math.sin(Math.toRadians(camYaw));       float addZ = currentDist  * f * (float)Math.cos(Math.toRadians(camYaw));       float addY = currentDist  * (float)Math.sin(Math.toRadians(camPitch));       // now finish up by converting this to an actual world coordinate      Vector3f pointInWorld = new Vector3f();       pointInWorld.x = camX + addX;       pointInWorld.y = camY + addY;       pointInWorld.z = camZ + addZ;       // let's assume you have an array of objects in your world that you're picking      for (Block block : blockList)       {          // create a method like 'isPointInside' on your Block object that         // just tests whether or not a Vector3f coordinate is 'inside' the         // block's bounds         if (block.isPointInside(pointInWorld))          {             // we've found our block!            return block;          }       }    }    // we couldn't find anything in this test   return null; }

This code isn't perfect, but should give you the general idea.

Note that the 'blockList' array should be a list of logical blocks that are likely to be within the viewer's camera frustum - so you'd obviously not be looping through the entire world's block list, but rather your optimised list of blocks within the viewing cone.

Picking blocks using the mouse cursor (rather than with the camera's line of sight, a-la Minecraft) can be accomplished using a technique known as unprojecting, but this is more complex and I'd recommend getting to grips with this method first.

[Danny02]

Just use the inverse of the view-projection matrix.

Create two 4D vectors by using the mouse position as the XY part the projected near and far clipping plane values (-1, 1) as Z and 1 as W.
Then multiply them with the inverse, get the difference for the direction and either the camera position or the near-vector as the start.

Also don't use iterations to select what you picked. Calculate the ray intersection point for every entity you are interested in and then select the one which intersection point is the most near to the origin(eye/camera).

[zFollette]

Well I just had an idea and I want to share it before I look at any code given to me. I will have 2 vector3fs calculated with the fov angle of the camera, then I will iterate over every point in between them and see if that point happens to fall into an object.

[Danny02]

Do not iterate over points lying on the pick ray. It is slower and incorrect compared to normal line intersection tests.

Games published by our own members! Check 'em out!

[zFollette]

Ok

[opiop65]

As a side note, this forum isn't for chatting. Simply replying with a one word answer is annoying and a waste of server space.

[pixelprime]

Danny, I'm glad that you've pointed out that line iteration is not perhaps the best way to do this type of object picking - but could you elaborate more on the concept you're discussing as the right way to do this?

I think that both I and the OP (along with anybody else interested in this particular topic) would benefit from some insight into the correct methodology to achieving this. I'd like to improve my own attempts at this.

I took the time to write up some code to illustrate one possible method of tackling this problem, and while I'm not suggesting that you need to do the same, I'd be interested to see a more explained version of your concept, as I had some difficulty understanding it.

Thanks.

[Varkas]

Data gloves were made for manipulation obects in virtual (3D) space:

http://en.wikipedia.org/wiki/Wired_glove

Computer mice are 2D devices, as noted before the mapping of a 2D location into 3D space is ambiguos and you'll need some tricks to get it working well in your game.

[pixelprime]

Could something like this work?

So you know where your near clipping plane is (based off of your camera's current position). You can therefore map the user's XY mouse position to its relative 3D world coordinates (the red dot).



Then, using information known about your far clipping plane (the end of your camera's view frustum) you can accurately map a point in the relative position on that far clipping plane (the blue dot).

The vector between these two points would effectively become the current picking ray (the dotted, red line) - and either using iterations OR line-intersection you could work out what this ray hits first in the scene, and pick that.

If none of this is right, I would appreciate some input so that the theory behind this is correct. I'm basing this off of my own interpretation of line picking that correctly observes the camera's FOV.

Thanks.

[Danny02]

Pixelprime's picture shows quite well the idea behind mouse picking in a 3D world. One can define that the mouse cursor is lying on the near clipping plane of the view frustum and defines a ray in addition to the camera origin.

This ray/line is unlimited in each direction. So to only "pick" stuff we can actually can see (stuff in the view frustum) we restrict our further search to the line-segment of this ray which lies in the frustum. You see this line segment in the illustration in the post above.

Further on I will describe the two task which are needed.

Calculating the line segment

Create two 4D vectors by using the mouse position as the XY part, the projected near and far clipping plane values (-1, 1) as Z and 1 as W.
Then multiply them with the inverse view-projection matrix, get the difference for the direction and either the camera position or the near-vector as the start.

Now a more indepth explanation, but first some minor stuff about vector matrix multiplication:

• A 4x4 matrix can be seen as another coordinate-system or space. You probably already heard about object-, world-, eye-space in OpenGL.
• To multiply a vector with a matrix can be seen as to project that vector to the space the matrix is representing
• To undo such a projection one can use the inverse of the previously used matrix

Two calculate the two points we need (blue/red dots in the picture) we will use the OpenGL projection-space(we get there with the Projection-Matrix, glOrtho ...) to our advantage. The projection space is defined, so that every point in the view-frustum is in the range [-1, 1] for all dimensions.

i.e. a point with XY == (-1, -1) will be rendered to the left bottom pixel of the canvas, (0,0) to the center ...

Perhaps now it is already clear for some how we can easily calculate the positions of the red and blue points.
Both points share the same X,Y coordinates in the projection space, because both are covered by the mouse cursor. To calculate these coordinates we can simply divide the mouse position by the canvas size and do a little multiply and add:

1   2

float relativeX = mouseX / width; float projectedX = relativeX * 2 - 1;

The Z coordinate is even more simple to derive. We just take -1 for the red and 1 for the blue point, see projection-space definition.

Now as a final step, we will need the inverse of the view-projection matrix. This is because we have the coordinates for both points in the projection-space, but need them in world-coordinates for our actual picking calculations.

The view-projection matrix projects points from world to projection space, so multiplying our calculated two points by the inverse gives us our solution of this chapter.

Doing the line intersection test
As said in the introduction we want to do some picking with the line-segment defined by the red and blue points. The first thing to do is to define what we actually try to achieve. What we want to do is to find all objects which intersect with the line-segment and then select the object which intersection point is the most near to the camera origin.

How to do these two steps can vary greatly for each application. It totally depends on the organisation of the objects you want to pick, but let us take a quick look at the most common case with just a simple list of objects to test.

Say you have some game entities, like units in a RTS, you want to pick. The first thing you need to do is to define the physical boundaries of the entity somehow. You can do this by using some simple shapes like a sphere, AABB, OOBB or a capsule. Further more you can use some hierarchy of such shapes(like hitboxes for a character in a FPS. sphere for the head and boxes for the limbs) or just test against a polygon mesh. Depending on what you use, you will need some function which can calculate intersection point(s) between a line/ray and such shapes. Just use google("line AABB intersection") or ask/search in this forum.

The only difference between a line intersection test and one for a line-segment is that you have to check if the calculated intersection point lies between the two points of the segment.

As a little bonus a little thinking incentive for all the block-world lovers: Like you can calculate the pixels of a line you draw on a 2D canvas very easily, you can do the same with a 3D line in a 3D picture like a voxel-block-world is.

[pixelprime]

A very thorough and detailed explanation, thank you for taking the time to draft it out. This should answer the OP's question nicely, and will allow me to correct the method I'm using to do this to something more appropriate.

Thanks.