# ==Ray picking== through the rendering pipeline <p class="doc-sub">// status: seedling</p> Picking is the inverse of rendering. Rendering takes a world point, transforms it through model, view, and projection matrices, and lands on a pixel. Picking starts with a pixel and asks which world-space ray could have produced it. The maths is short; the coordinate conventions around it are where the bugs hide. This is the ray behind an editor reticle, an RTS selection click, and the brush in [[Raym - Interactive Terrain Generation with Marching Cubes|Raym]]. It is also the first step before querying a [[Spatial acceleration structures|BVH]], a mesh, or a scalar field from [[Marching Cubes]]. ## Keep the spaces named Do not call every vector a `position`. Write the space into the variable name while debugging. The common chain is: | Space | Typical representation | What it means | |---|---|---| | Window / pixel | `(x, y)` in pixels | mouse or framebuffer location | | NDC | `[-1, 1]²` plus API-specific z | after perspective divide | | Clip | homogeneous `vec4` | before divide by `w` | | View / eye | camera-relative 3D | camera at the origin | | World | scene coordinates | shared by objects and gameplay | | Local / object | mesh coordinates | useful for per-object intersection | The inverse path is: ```text mouse pixel → NDC near/far points → inverse view-projection → world ray world ray → inverse model → local ray → bounds / triangles / field query ``` The multiplication order follows the convention used by the rest of the renderer. With column vectors, a point is commonly `clip = projection * view * model * local`; the inverse is `local = inverse(model) * inverse(view) * inverse(projection) * clip`. With row vectors the order is reversed. A transposed matrix can still produce a believable ray in a symmetric scene, which is why I test against an asymmetric object first. ## Pixel to NDC Let `p` be a position in the actual framebuffer, and `viewport` be the rectangle being rendered. The x coordinate is straightforward: ```c float xNdc = 2.0f * (p.x - viewport.x) / viewport.width - 1.0f; ``` The y coordinate depends on the origin convention. For a top-left mouse coordinate mapped to an OpenGL-style bottom-left framebuffer, flip it explicitly: ```c float yFromBottom = framebufferHeight - 1.0f - mouseYTop; float yNdc = 2.0f * (yFromBottom - viewport.y) / viewport.height - 1.0f; ``` Do not bury this flip in a projection matrix and a texture upload at the same time. Pick one place and make the input contract clear. HiDPI windows add another scale: the mouse may be reported in logical points while the render target is in physical pixels. The depth endpoints differ: | API convention | Near NDC z | Far NDC z | |---|---:|---:| | OpenGL default | `-1` | `+1` | | Vulkan | `0` | `1` | Vulkan's `VkViewport` has an upper-left framebuffer origin, and a negative viewport height is commonly used when an application wants the opposite y orientation. The robust approach is to derive the ray with the same viewport state used by the draw, then verify the sign with a known point. The Vulkan spec's viewport and vertex-post-processing sections are the authority here; screenshots and tutorial conventions are not. ## Unproject the two endpoints Given NDC points `nearNdc` and `farNdc`, put them back in clip space with `w = 1` and multiply by the inverse view-projection: ```c struct Ray { vec3 origin; vec3 direction; }; vec3 unproject(vec3 ndc, mat4 inverseViewProjection) { vec4 h = inverseViewProjection * vec4(ndc, 1.0); return h.xyz / h.w; // homogeneous divide is not optional } Ray makePerspectiveRay(vec2 pixel, Viewport vp, mat4 inverseViewProjection, vec3 cameraPosition, bool topLeftInput) { vec2 q = pixel; if (topLeftInput) q.y = vp.framebufferHeight - q.y; vec2 ndcXY = vec2( 2.0 * (q.x - vp.x) / vp.width - 1.0, 2.0 * (q.y - vp.y) / vp.height - 1.0); vec3 nearWorld = unproject(vec3(ndcXY, vp.nearNdcZ), inverseViewProjection); vec3 farWorld = unproject(vec3(ndcXY, vp.farNdcZ), inverseViewProjection); return Ray{cameraPosition, normalize(farWorld - nearWorld)}; } ``` For a perspective camera, the camera position is a convenient ray origin. For an orthographic camera, use `nearWorld` as the origin; the direction is the same for every pixel. If the camera transform has a scale or the view matrix is not a rigid inverse, deriving the origin from the unprojected near point avoids assumptions. An easy test is to project a known world point, feed the resulting pixel back through `makePerspectiveRay`, and check that the point lies on the resulting line. Do this before intersecting a complicated mesh. ## Intersect the ray ### AABB first An axis-aligned bounding box is cheap rejection. The slab test computes the interval of `t` values for which the ray is inside each axis interval, then intersects the three intervals: ```c bool hitAabb(Ray r, vec3 bmin, vec3 bmax, out float tNear, out float tFar) { vec3 invDirection = 1.0 / r.direction; // zero components become ±infinity vec3 t0 = (bmin - r.origin) * invDirection; vec3 t1 = (bmax - r.origin) * invDirection; vec3 lo = min(t0, t1); vec3 hi = max(t0, t1); tNear = max(max(lo.x, lo.y), lo.z); tFar = min(min(hi.x, hi.y), hi.z); return tFar >= max(tNear, 0.0); } ``` For an object with a transform, transform the ray into local space with the inverse model matrix and test the local-space bounds. Direction vectors use `w = 0`, so translation must not affect them. Under non-uniform scale, the transformed direction is no longer unit length; that is fine as long as `t` is interpreted in local units or renormalised with the corresponding distance conversion. ### Triangles and acceleration structures After the box, traverse a BVH and test only the leaf triangles. The Möller–Trumbore intersection is a compact starting point: ```c bool hitTriangle(Ray r, vec3 a, vec3 b, vec3 c, out float t, out vec2 bary) { vec3 e1 = b - a; vec3 e2 = c - a; vec3 p = cross(r.direction, e2); float det = dot(e1, p); if (abs(det) < 1e-8) return false; float invDet = 1.0 / det; vec3 s = r.origin - a; float u = dot(s, p) * invDet; if (u < 0.0 || u > 1.0) return false; vec3 q = cross(s, e1); float v = dot(r.direction, q) * invDet; if (v < 0.0 || u + v > 1.0) return false; t = dot(e2, q) * invDet; bary = vec2(u, v); return t >= 0.0; } ``` For a handful of meshes, a linear loop is clearer and faster than building a tree. Once the scene has many objects or triangles, the hierarchy in [[Spatial acceleration structures]] pays for itself. Keep the closest positive hit, not the first leaf visited. ### Picking an implicit field Picking a Marching Cubes mesh means intersecting its generated triangles. Picking the underlying density field can be more useful for sculpting, because the hit remains stable while the mesh is rebuilding. Start by intersecting the ray with the chunk AABB, then sample along the interval: 1. For a true or conservative signed distance field, use sphere tracing as in [[Ray marching and SDFs]]. 2. For an arbitrary density field, use fixed or adaptive samples to find a sign change, then binary-search that bracket. 3. If the field has multiple crossings, keep the first valid bracket along the ray and cap the step count. Do not call an arbitrary noise density an SDF. Sphere tracing is only safe when the value is a conservative distance bound; otherwise it can jump over the surface. This distinction is the difference between a reliable brush reticle and a reticle that occasionally appears on the far side of a mountain. ## GPU picking and selection IDs CPU ray traversal is ideal when a click happens occasionally and the CPU already owns the scene bounds. A GPU path makes sense for a continuously updated cursor, thousands of rays, or a renderer that already has a visibility buffer. Two useful GPU designs: - **ID attachment:** render an integer object or primitive ID alongside the normal/depth targets, then read one pixel. This is trivial to integrate into a [[Deferred vs forward rendering|deferred]] or visibility pass, but it identifies the rasterized primitive rather than an arbitrary hidden object. - **Compute ray query:** upload a ray and traverse a GPU BVH or grid in compute. This avoids a graphics-pass readback and scales to many queries, but requires an explicit output buffer and synchronization. For one cursor click, `glReadPixels` or a mapped Vulkan staging buffer may be enough. For every-frame hover, an asynchronous pixel-pack/readback path prevents the CPU from waiting for the GPU that just rendered the answer. Hide the latency with a one-frame-late selection if the UI can tolerate it. ## Things that tripped me up - **Mouse y is not framebuffer y.** Account for top-left input, bottom-left OpenGL framebuffers, Vulkan viewport state, and HiDPI scaling exactly once. - **OpenGL and Vulkan do not share the same NDC z range.** `near = -1` is correct for default OpenGL and wrong for Vulkan. - **The homogeneous divide matters.** `inverseViewProjection * clip` is not a 3D point until divided by `w`. - **Perspective and orthographic origins differ.** A camera-position origin is correct for perspective, not for an orthographic ray. - **`inverse(model)` affects direction differently from position.** Use `w = 1` for the origin and `w = 0` for the direction. - **Depth is non-linear.** A value sampled from a depth attachment is not metres from the camera; reconstruct world position before comparing distances. - **Logical and physical viewport sizes diverge.** On a Retina display, a correct-looking ray can still be offset by exactly the backing-scale factor. - **The first hit is not necessarily the closest hit.** BVH traversal order is an implementation detail; compare `t` values and retain the minimum positive result. ## References - [OpenGL 4.6 Core Specification — coordinate transforms and viewport rules (Khronos)](https://registry.khronos.org/OpenGL/specs/gl/glspec46.core.pdf) - [Vulkan API Specification — vertex post-processing and viewport transform (Khronos)](https://registry.khronos.org/vulkan/specs/latest/html/) - [GLU `gluUnProject` reference (Khronos)](https://registry.khronos.org/OpenGL-Refpages/gl2.1/xhtml/gluUnProject.xml) - [Möller & Trumbore, “Fast, Minimum Storage Ray/Triangle Intersection” (University of Utah)](https://www.graphics.cornell.edu/pubs/1997/MT97.pdf) - [Amanatides & Woo, “A Fast Voxel Traversal Algorithm for Ray Tracing” (Eurographics)](https://www.cse.yorku.ca/~amana/research/grid.pdf) --- Back to [[Notes/Index|Notes]] · see also [[Raym - Interactive Terrain Generation with Marching Cubes|Raym]] · [[Spatial acceleration structures]] · [[Marching Cubes]] · [[Ray marching and SDFs]] · [[Deferred vs forward rendering]]