Notes:Pick function

This page was written to respond to a question - the site didn't support math-markup, so it was written here instead

Set up

Let [ilmath]P[/ilmath] denote the [ilmath]4\times 4[/ilmath] (projection AND view operator) you are using (that is for a point [ilmath]x[/ilmath], [ilmath]Px[/ilmath] is the complete transformation to clip coordinates)

Given a point in the world, [ilmath]x[/ilmath] this matrix applies the camera position/angle transformation, then the projection operation all at once. Thus [ilmath]P[/ilmath] represents the camera.

Calculations

Let [ilmath]c[/ilmath] be a [ilmath]4[/ilmath]-vector in clip-space, let [ilmath]\text{Ndc}:\text{clip}\rightarrow\text{Normalised device coordinates} [/ilmath], this function is given by:

• [ilmath]\left[\begin{array}{c}c_x\\ c_y \\ c_z \\ c_w\end{array}\right]\mapsto\frac{1}{c_w}\left[\begin{array}{c}c_x\\c_y\\c_z\end{array}\right][/ilmath]

The pick line

Let the screen have width [ilmath]S_w[/ilmath] and height [ilmath]S_h[/ilmath], we must first convert the "point" clicked on the screen, call it [ilmath]q[/ilmath] to NDC.

To go from NDC to screen coordinates we use the following function:

• [ilmath]:a\in[-1,1]\mapsto S_w\frac{a+1}{2}[/ilmath]

It follows from this that to go back we must:

• [ilmath]:q_x\mapsto 2\frac{q_x}{S_w}-1\in[-1,1][/ilmath]

So our pick line (in NDC) is the line given by:

• [ilmath]p=\left[\begin{array}{c}2\frac{q_x}{S_w}-1\\ 2\frac{q_y}{S_h}-1 \\ -1\end{array}\right]+\lambda\left[\begin{array}{c}0 \\ 0 \\ 2\end{array}\right][/ilmath] for [ilmath]\lambda\in[0,1][/ilmath]

We can write this more compactly as:

• [ilmath]p=\left[\begin{array}{c}2\frac{q_x}{S_w}-1\\ 2\frac{q_y}{S_h}-1 \\ 2\lambda -1\end{array}\right][/ilmath]

Going to clip coordinates

The map Ndc looses a dimension, we only know the ratios of x,y,z compared to w, we do not know w. Template:TODO We just assume [ilmath]w=1[/ilmath] for this, so in clip coordinates:

• [ilmath]p=\left[\begin{array}{c}2\frac{q_x}{S_w}-1\\ 2\frac{q_y}{S_h}-1 \\ 2\lambda -1 \\ 1\end{array}\right][/ilmath]

Going to world coordinates

We know that [ilmath]P[/ilmath] takes a world coordinate, moves it about (depending on the camera location/rotation) and then projects it.

From this, [ilmath]P^{-1} [/ilmath] does the opposite, and "unprojects" a clip coordinate, then undoes the moving about. So to get a world coordinate we simply do:

[ilmath]w=P^{-1}p[/ilmath] (remember that [ilmath]p[/ilmath] moves from near to far as [ilmath]\lambda[/ilmath] goes from [ilmath]0[/ilmath] to [ilmath]1[/ilmath]

Final notes

This is the "easy" part of ray-casting. How to find out what "object" it hit depends very much on the engine's notion of object.

Starting points

Bounding boxes are great. However suppose you take [ilmath]\lambda[/ilmath] up in steps of [ilmath]0.1[/ilmath] - the depth isn't linear (as you should already know) and this could miss thin objects. What is usually done is to take portions of the line, for example [ilmath]\lambda=0[/ilmath] to [ilmath]\lambda=0.1[/ilmath] and see what that hits, then take the next chunk and so forth.

Bounding boxes should be your first call.

Remember that your line could be moving in ANY direction. So don't assume the near point has a lower [ilmath]x[/ilmath] coordinate than the far point, say.

1. Treat the bounding box as 3 intervals, for example [ilmath][a,b][/ilmath] Take and end point of the line segment, [ilmath]u[/ilmath].
   1. • Assign a value 1 if [ilmath]u< a[/ilmath]
      • Assign a value 0 if [ilmath]u\in[a,b][/ilmath]
      • Assign a value -1 if [ilmath]u > b[/ilmath]
   2. Do the same for the other end point.
   3. Add these values. If the sum is [ilmath]-2[/ilmath] or [ilmath]2[/ilmath] then there is no intersection on the axis (you know there is no intersection as a result)
   4. Do this for the next axis.
   5. Do this for the next axis. (you now know there is a possible intersection)
   6. Do a detailed analaysis

(this isn't code but I'm rushing this. You should get the gist)