For linear polynomials, there's a bunch of algorithms for efficiently determining which voxels to test for collision (eg. A Fast Voxel Traversal Algorithm for Ray Tracing ). I'm having troubles though, searching for algorithms that work for any other case, such as a parabolic projectile arc under constant gravity.

Are there any algorithms for that case, or am I stuck just trying to sample at a high enough frequency that only rarely will a projectile travel though a wall without getting detected.


If your gravity vector is purely vertical (let's call this the Y axis) and there's no sideways wind to account for, then the projectile's XZ position follows a straight line. If you don't have air resistance, then it moves along this line at a constant rate - just like our nice friendly linear raycasts!

So we can cast a "shadow" of the projectile straight down onto the XZ plane. We can work out which squares of the grid on this plane this line passes through using your ordinary raycasting/marching algorithm in 2D (or another line rasterization algorithm like Bresenham's). I show an example of this type of raymarching in this answer.

With this, we can work out the time-of-flight when the shadow crosses into each new square along its path. This tells us when the 3D projectile itself enters a new column of voxels.

By computing the height at each column-entry timestamp, using:

$$\vec p(t) = \vec h_0 + \vec v_0 \cdot t + \frac {\vec a} 2 \cdot t^2$$

...then we can get the height at which the projectile enters and exits each column.

The one other height we need is the height at the apex of the parabola. This is the one point where the projectile might touch voxels in a column outside the range from its entry to exit height. We can find this point with:

$$t_* = \frac {-v_y} {a_y}$$

Now we can walk through each of these key timestamps in sequence, from the entry into a new column of voxels, and up/down that column to the next timestamp in sequence (be it the apex or the entry into the next column over). This ensures we visit every voxel touched by the parabola, with only a small amount of work beyond the basic 2D raycast.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.