Holy hell ladies and gentlemen. I knew we needed to fix raycasting for a while, but the results are insane.
There are many ways we can do raycasting, but the way we chose is ray marching. Since we know the mesh data in each voxel of the world, we can march a ray through the chunk and pull all the block data and look for hits.
The problem is as you're marching through the ray, you need a certain step. Look at the step rate below.
Each blue circle is a point we're evaluating at a fixed step along the blue ray. If the blue circle is in a voxel, we'll color it green and analyze if there is a hit in that block. Note that the line passes through two blocks that are colored yellow. There was no circle in those blocks, so we ended up missing it. If there was a mesh in those locations, we would miss hitting it.
You can mitigate the problem by adding more steps, but you will always end up with some part of the ray clipping a corner of a block and getting missed due to a step limit. Plus, the more steps you take, the longer the raycast takes.
Note above, that the average time it takes to run the smallest step 100 times is 57ms. This would mean that the game would run at 16 FPS at that rate, not accounting for any other logic.
In the table above, there is a magical FVT row that nearly runs as fast as the 0.25 spacing. This stands for Fast Voxel Traveling. This eliminates the step methodology in lieu of stepping only at the voxel boundaries. If you know where the boundaries are, not only do you not have to worry about step size, but you won't miss any blocks.
In 2D, you can view this in action using this site: https://www.shadertoy.com/view/XddcWn
In 3D, it looks more like this:
It's critical you get the algorithm to line up right though, as errors tend to propagate. I spent hours trying to get the ray to line up completely inside the voxel boxes.
What this means is that our raycaster is finally pixel perfect, and it's very noticeable that you are finally selecting what you intend.
Check out the demo below, watch the tiny green dot, which represents the hit point on the world meshes. This finally selects the appropriate face without fail, despite many faces being mere pixels.
What this means is that we can finally build on nearly any surface. (There are still other bugs, so the following isn't yet perfect)
More updates to come!!
Written by your friendly Satus Developer: Elaixzar