Openspades: 3D coords to build from screen (placing blocks to a x,y,z pos from the screen) [Raymarching? investigating...] Algorithm? *Need Help*

[Edgamer63]

Hello, i was wondering how the pos to build a block (No, i dont mean the block building, i mean the block position in x,y,z to build) from screen (yaw and pitch, or whatever how it works with the mouse ever in the center of the screen) works.

Beforehand, thank you ;D .

[yvt]

Ray casting

It’s done by ray casting — an algorithm that calculates a set of objects in a scene intersecting with an input straight line (called a ray as analogy to light in a real world).

The specific detail of ray casting vastly varies depending on the requirements. For voxels, a naïve O(d) (where d is the length of a ray) algorithm like this works. When faster traversal is required, a mipmap could be used to skip large empty chunks, resulting in the best-case complexity O(log N) (where N is the domain size). Finally, here's the ray tracing implementation of OpenSpades, which is not very educative compared to the previous examples.

A ray is defined as a half-line (an infinitely-long straight line having one endpoint) x⃗ = p⃗ + d⃗t. The aforementioned naïve algorithm goes like this: You start at the voxel in which the starting point resides. At each step, the next voxel the ray enters is found. The ray enters one of the neighboring voxels through one of the faces of the current voxel. In the following diagram's case, there are two candidates: x = 2 and y = 2.

The ray intersects with x = 2 and y = 2 at the points x⃗₁ = p⃗ + d⃗t₁ and x⃗₂ = p⃗ + d⃗t₂, respectively. Some of the points are actually on the current voxel's border while the others are not. Since the voxel is convex-shaped, finding the former ones is easy: just solve t₁ and t₂ and choose the ones with the smallest t (i.e., closest to p⃗). In this case, t₂ < t₁, so we find that the ray exits through y = 2 and the next voxel is the one above the current one. The starting point point is advanced to the intersection x⃗₂ and this step is repeated until a solid voxel is encountered or there's no voxel to visit.

Ray picking

The use of ray tracing to find an intersection corresponding to a point on a screen is called ray picking. Every point on a screen corresponds to a straight line/half-line/line segment, which can be interpreted as a ray. For the point that is at the screen's center (like the hit scan of first-person shooter games), the ray usually coincides with the camera's optical axis (which in turn coincides with a player character's “orientation”). In more general cases, the inverse of a projection matrix can be used to construct rays.

Raymarching

From what I know the word raymarching refers to one of the following things:

1. Approximate ray tracing on an implicitly defined surface by evaluating the surface function on the points along a ray.
2. A specific variation of 1 that uses a function bounded by the signed distance function to conservatively estimate the step size.

The voxel ray tracing algorithms shown above are exact, thus do not match the definition of raymarching in a usual sense.