I want to make a concept that can be linked with ray-tracing, here applied to Minecraft.
It it's a 3D world, so there is X/Y/Z, with decimal value.
I have 2 vectors:
- The begin position
- Direction of line which is between -1 and 1 (so for example 0.5/-0.3/0.5).
In this 3D world, there is a block which have a size of 1 (1x, 1y, 1z).
I have to see what is the next block in the vector direction, limited to 10 blocks.
I tried something like that:
- Divide the vector to make more iteration (i.e. 0.5/0.2/0.5 become 0.25/0.1/0.25)
- Add the vector to the location to "walk" to the next point
Here is an example where red point at all point and green line are blocks.
The issue here is that the yellow block isn't count. Such as the next point is too far (and the last was not enough) it pass through but don't detect it.
I tried to divide the vector but I will always have false positive, and it also take more time...
How can I do ?
This is a basic raycasting algorithm that tracks the ray intersections with integer coordinates along each axis, i.e. its intersections with the $yz$ plane at each integer $x$ coordinate, intersections with the $xz$ plane at each integer $y$ coordinate, and intersections with the $xy$ plane at each integer $z$ coordinate, along the ray.
Start with the ray starting position vector $\vec{s} = (s_x, s_y, s_z)$ and the ray unit direction vector $\hat{d} = (d_x, d_y, d_z)$, $\lVert\hat{d}\rVert = \sqrt{d_x^2 + d_y^2 + d_z^2} = 1$.
Using a vector-valued function, points $\vec{p}$ along the ray using distance parameter $t$, $t \ge 0$, are $\vec{p}(t) = \vec{s} + t \hat{d}$. This means we only really need to know the distances $t$ for the abovementioned intersections, in the order they occur starting at $t = 0$ –– and this is obviously in order of increasing $t$.
If we measure the distance between consecutive intersections with the $yz$ plane along the direction vector, we'll find it is exactly $1/d_x$; and similarly $1/d_y$ for $x_z$ plane, and $1/d_z$ for the $y_z$ plane.
Initial values of $t$ for each coordinate axis –– let's call them $t_x$, $t_y$, and $t_z$ –– depend on the fractional part of the starting position coordinates. Because the fractional part describes directly how much of the inter-integer-coordinate distance is left to the next smaller integer coordinate value, calculating the initial distances is trivial:
If starting position coordinate is an integer, then the corresponding $t$ is either zero or the full inter-integer-coordinate distance along that axis. It is up to you, whether you wish to consider the plane that would intersect the eye or lens of the observer, or only the following ones.
If starting position coordinate is not an integer, and the corresponding direction vector component is negative, then the corresponding $t$ is the fractional part of the starting position coordinate divided by the (absolute value, or negated) direction vector component.
If starting position coordinate is not an integer, and the corresponding direction vector component is positive, then the corresponding $t$ is the fractional part of the starting position coordinate subtracted from 1 (to get the fractional distance to the next higher integer), divided by the corresponding direction vector component.
When the above are known, we start with the smallest known $t$, check that intersection, and add the distance to the next intersection along that particular axis to that value for the next comparison, and repeat until we exceed the visible distance.
Let's say $\vec{s} = (1.0, 4.5, 2.3)$ and $\hat{d} = (2/7, -3/7, 6/7)$.
The integer distances along each axis are then $T_x = 7/2 = 3.5$, $T_y = 7/3 \approx 2.333$, and $T_z = 7/6 \approx 1.667$.
Because $s_x$ is an integer, $t_x = 0$ or $t_x = 7/2 = 3.5$; I pick the latter, because I don't think I'd see a plane intersecting my eye.
Because fractional part of $s_y = 0.5$ and $d_y \lt 0$, $t_y = 0.5 T_y = 7/6 \approx 1.667$.
Because fractional part of $s_z = 0.3$ and $d_z \gt 0$, $t_z = (1-0.3) T_z = 0.7 T_z = 49/60 \approx 0.817$.
Initial cell (integer) coordinates are obtained by rounding down the starting point coordinates, so $(1,4,2)$. (If you use unsigned integer coordinates, then you can truncate; otherwise you need to use
floor(), andc - floor(c)to get the fractional part. The convention is that each cubic cell is identified by the smallest integer coordinates of its vertices.)Note that if you consider cells "boxes", each integer coordinate plane belongs to two "boxes". If you forget this, you'll see "boxes" that only have three sides, instead of six.
So, the raycasting loop starts with $t_x = 3.5$, $t_y \approx 1.667$, and $t_z \approx 0.817$, with $T_x = 3.5$, $T_y \approx 2.333$, and $T_z \approx 1.667$, in cell $(1, 4, 2)$.
Since $t_z$ is the smallest, the first possible intersection occurs at $t = t_z \approx 0.817$, at the upper $z$ wall (because $d_z \gt 0$) of cell $(1, 4, 2)$, entering cell $(1, 4, 3)$. $t_z$ will be incremented by $T_z$, to $t_z \approx 1.983$.
Since $t_y$ is now smallest, the next possible intersection occurs at $t = t_y \approx 1.667$, at the lower $y$ wall (because $d_y \lt 0$) of cell $(1, 4, 3)$, entering cell $(1, 3, 3)$. $t_y$ will be incremented by $T_y$, to $t_y = 3.5$.
Since $t_z$ is again smallest, the next possible intersection occurs at $t = t_z \approx 1.983$, at the upper $z$ wall of cell $(1,3,3)$, entering cell $(1,3,4)$. $t_z$ is incremented by $T_z$, to $3.150$.
$t_z$ is again smallest, so the next possible intersection occurs at $t = t_z \approx 3.150$, at the upper $z$ wall of cell $(1,3,4)$, entering cell $(1,3,5)$. $t_z$ is incremented by $T_z$, to $4.317$.
Next, $t_x$ and $t_y$ are the smallest, so the next possible intersection occurs at $t = t_x = t_y = 3.5$, at the edge where upper $x$ wall (because $d_x \gt 0$) and lower $y$ wall (because $d_y \lt 0$) of cell $(1, 3, 5)$, entering cell $(2, 2, 5)$. $t_x$ is incremented by $T_x$, becoming $7$, and $t_y$ by $T_y$, becoming $5.833$.
This is repeated until $t$ exceeds the visible distance. Note that $t$ is also the distance between the observer and the surface the ray hits, so you can add distance-dependent haze/blending very easily.
There are many programmatic tricks to make the inner loop as fast as possible (for example, you could do all 26 direction variants), but that's obviously a separate matter.
Mathematically, one could track a pair or quad of rays (spanning an area of the display), and split them (doubling the number of rays if still visually useful) whenever they diverge enough (not in the same or neighboring cells), to avoid recomputing the same ray path repeatedly. This, however, is a raycasting algorith optimization, and again not math, and therefore unsuitable to elaborate in this answer.