How is ray picking done?

Started by TechNick6425, August 29, 2013, 11:30:48

Previous topic - Next topic

TechNick6425

I understand what Ray Picking is, I'm just confused on how it would be calculated.

Daslee

QuoteOne way to generate a pick ray is to call gluUnProject() twice for the mouse location, first with winz of 0.0 (at the near plane), then with winz of 1.0 (at the far plane). Subtract the near plane call's results from the far plane call's results to obtain the XYZ direction vector of your ray. The ray origin is the view location, of course.

http://www.opengl.org/archives/resources/faq/technical/selection.htm

TechNick6425

I'm sorry, that made absolutely no sense. ???

quew8

Well that describes a way to calculate the forward direction of your view which you then test against your geometry. It might be best to describe a little more precisely what you are having problems with. Is it generating the ray to test or is it testing it? A little context wouldn't go amiss either.

TechNick6425

I'm sorry, apparently I have no knowledge of how it works, I just know what it does.

quew8

The two parts to ray picking are: choosing the ray and intersecting the geometry.

How you choose the ray, I feel, depends on the purpose and context. If you could elaborate a bit further. Mainly: is this Minecraft style picking the block you are looking at and if so I need to know how you create the viewing matrix and how you do any other model transforms, else is it AI visibility test or what?

As for intersecting with geometry, there are a very large number of methods. You you do it algebraically by doing plane-ray tests against all the faces. You could use one of the many algorithms like SAX or GJK. Personally I use the GJK algorithm but I would not recommend trying to implement that yourself if your maths is weak. Probably the simplest is by linear algebra (search: plane-ray intersection) but it is by no means the quickest (I think). You will need to go away and research these options and decide, then we can help you.

TechNick6425

I have done some thinking, and have determined for my cause, I need these.
- Minecraft style block picking
- Entity visibility test
- Possibly lighting

For the methods, I would like to use whatever is the best for these purposes.

RiverC

One way to do this is to get the ray's equation from the 'frustrum' of the camera, which is really just the line perpendicular to the plane of the camera. This is the ray that comes 'straight out' of the center of the field of view and AFAIK, is often used.

This is done by converting the camera's facing (however this is stored) into a normalized vector (x,y,z). For example if you store it in 'gimbal' coordinates, 'yaw', 'pitch', 'roll', you take the yaw and pitch, ignoring the roll since it is factored in last and will not alter the position of the center of the camera, and use a little trigonometry to convert those two radian values into a 3d line. If you use a quaternion it would be different, though I use quaternions I convert from the gimbal coords since they are more human-readable and can be reasonable placed in configuration files without the aid of a calculator.

Secondly, you need planar geometry to ray cast against. Let's say you have a bunch of boxes in a room. You need to do a test against each triangle or quad to see if the ray intersects it. The math is not simple, but it is all multiplications and such.

Furthermore, you can do certain optimizations to cut down the number of tests you need to perform per frame, or (in the case of AIs) only calculate this every so often. One obvious optimization is space partitioning; if you can first figure out if the ray intersects the bounding box for that space or not, you know whether or not it can intersect with anything bounded by that partition.

Would be cool if LWJGL did include a simple raycast/ray pick implementation.

TechNick6425

I was taking a peek at another post I had, in which I learned how to calculate the X, Y, and Z increase by pitch and yaw. I'm going to use those again, as I think I've found a solution.

I was wondering, if I get the X, Y, and Z increase by using direction, could I increase in small increments such as...
X1: 0.1
Y1: 0.2
Z1: 0.15

X1: 0.2
Y2: 0.4
Z2: 0.3

I was wondering if they are all proportional, will the line be straight? And if so, could I use this for ray picking?

quew8

If they are all proportional, then yes the line would be in the same direction. But what you have there is not proportional. You multiplied X1 and Y1 by a factor of 2 to get X1 (I presume you mean X2) and Y2, but Z1 stayed the same.

A little trigonometry crash course:

(The O with the horizontal line through it is the greek letter "Theta")

The word to remember is SOHCAHTOA as in SOH | CAH | TOA.

What it states is that, from the diagram:

sin(theta) = opposite / hypotenuse ( S = O / H )

cos(theta) = adjacent / hypotenuse ( C = A / H )

tan(theta) = opposite / adjacent ( T = O / A )

If you think about the hypotenuse as a vector, then the x component is adjacent, the y component is opposite and the magnitude (length) is the hypotenuse. And therefore:

X = Magnitude * sin(theta);
Y = Magnitude * cos(theta);


At the moment when you work out the Vector from the angle, you are assuming Magnitude = 1 which eliminates it from the equation but you can assume is is what ever you want.

TechNick6425

Silly me! I meant to double the Z value. Edited.