20:17 This is kind of a cool way to do voxel ray-tracing (or ray-marching I guess), but it has two main issues: - Performance - for a shadow ray in particular, hitting a voxel should be our early-exit condition that lets us stop ray-marching - we shouldn't keep ray-marching until we hit the light. - Inaccuracy - If you imagine a long solid wall of blocks with a light on the other side, if the wall is thinner at one point, then the shadow cast by this light will be less dim at that point, but that's not how it should work at all unless the surface is meant to be semitransparent. A more practical example is how blocks which are low to the ground get shaded with a gradient towards the top (on the faces facing away from the light) - this is (presumably) because the screen rays hitting that block are sending out shadow rays backwards towards the light, and the rays that are closer to the top of the block have these shadow rays travelling less far through the block. A possible way to speed this up AND make it more accurate without destroying the whole ray-marching thing is to have each ray remember the normal of the block-face it hits, and then any shadow rays it would have shot that are going backwards relative to that normal (which I think you can test for via dot-product) exit early and return a uniform "shadow" colour value.
Breakdown of how you might implement this: - As a one-time process when creating a screen ray, read the XYZ components of its direction vector, and create three vectors that are: 1: (1, 0, 0) if the ray direction vector X is negative, (-1, 0, 0) otherwise (set as None if ray direction X-component is exactly 0) 2: (0, 1, 0) if the ray direction vector Y is negative, (0, -1, 0) otherwise (set as None if ray direction Y-component is exactly 0) 3: (0, 0, 1) if the ray direction vector Z is negative, (0, 0, -1) otherwise (set as None if ray direction Z-component is exactly 0) (We can only safely do this because the walls of voxels, and of our blocks, are inherently axis-aligned) - As a one-time process when ray-marching and inside a block: For each of the previously created vectors that is not None, create an infinitely large plane where the origin is the block's position offset by this vector * the block's width Then, project the ray onto that plane, yielding a t value (distance from ray origin to point on plane where the ray hits). We can return None (or a crazily large value to prevent having to test for None later) for the t value if the point on this plane is outside the block's bounding box. (The idea is that since our ray-march is inside the box, we have to have hit at least one of the three planes, or the two planes in the case where the block has no valid top/bottom face.) Then, the smallest t value found out of these up-to-three tests must be the normal vector of the face on the block that we hit. So, the ray stores that, and when creating shadow rays, if the direction of the shadow ray would be opposite to the normal, we just skip that shadow ray. Of course, the added ray-plane intersections for each time a screen ray hits a block, and added dot-product test for each shadow ray we create might outweigh the early-exit potential that this gives us. So this might not solve any performance problems at all.
I'm also not saying you *should* have implemented this, since this video was clearly only meant to be a quick re-implementation of the original ray-tracer and was clearly only meant to show how its code could have been organised better, *not* how it could have produced a prettier result or ran faster.
A possible way to optimise the screen-ray intersections in my implementation breakdown is to have the map generator precompute which horizontal faces a block has that aren't perfectly flush with the horizontal face of another block, so we can avoid performing the ray-intersection test for a plane which is between two blocks and therefore shouldn't exist. This would make the scene take longer to load, though, and also increase memory usage.
My implementation also wouldn't actually solve the problem of shadow rays being blatantly able to penetrate solid walls that AREN'T part of the block their screen ray hit, unfortunately - it'd only solve the unnatural shading on block faces that are facing away from the light. There's no real way to solve this that doesn't involve rebuilding the entire system. With that in mind, the most natural idea in my mind is to use the same intersection system as the screen rays (ray-march, then nearest-plane-intersection) to also find the normal of the surface a shadow-ray hits, then iterate along the perpendicular axis of that normal: (suppose Z is the vertical axis, cause I don't know which axis is vertical in your implentation) if hit face normal is +X or -X, iterate over Y-axis if hit face normal is +Y or -Y, iterate over X-axis if hit face normal is +Z or -Z, iterate over both X and Y axes After the shadow-ray intersection tests, we test whether the hit point is positive or negative on the perpendicular axes relative to the halfway point (or plane origin) of the plane that we hit. So, supposing we hit a +X face of a block - if the (ray hit point y - plane origin y) delta is positive, then we're iterating over blocks in the +Y direction, otherwise we're iterating in the -Y direction. (We would, of course, calculate direction for both the X and Y axes if we hit a vertical block face). From there, we index into the some kind of block array with an offset of 1 in the direction we've decided: so, if the block array is a top-down 2D array, and we hit a block at [26, 30] and are iterating in the +Y direction, we're checking if there's a block at [26, 31]. If there is, we can safely assume that the wall we've hit continues, and we don't have to do soft-shadows. If there isn't, we can then inverse-lerp the (ray hit point y - plane origin y) delta we've calculated earlier in the range (0, half a block-width) to find how close the hit point is to the edge of the point. Based on that, we can lerp the ray colour between fully in shadow and fully in light, creating a soft shadow. (Side-note: You might want to take the result of the inverse-lerp calculation to the power of 0.5, so that instead of a gradient from fully bright at the edge of the block to fully dark at halfway, it's more biased towards darkness closer to the edge of the block.) (Also remember that this isn't what's showing on the SURFACE of the block we hit since these are shadow-rays - it's what's showing on the floor before that block) EDIT: There's another case where we shouldn't do soft-shadows on a wall - that being the case where it's part of an internal corner with another wall. In order to solve this, let's again use the case where we hit a +X face at [26, 30]: We have to test for a continuation of the wall at [26, 31], but we can also test for an internal corner by taking the parallel direction of the face (in this case +X) and testing for a block by adding that offset to the perpendicular offset - so, in this case, [+X, +Y]. So, if there's a block at [27, 31], we can also avoid doing soft-shadows and return early. This test should also be done *before* the wall-continuation test, since if our +X wall is part of an internal corner, we can implicitly assume that it cannot possibly be part of a continuous wall in the same direction, and skip doing the wall-continuation test. Another way of wording it: If we know there's a block at [26, 30] and one at [27, 31], the block at [26, 31] wouldn't be visible to our ray anyway, so we don't have to check if it's there.
🎉
20:17
This is kind of a cool way to do voxel ray-tracing (or ray-marching I guess), but it has two main issues:
- Performance - for a shadow ray in particular, hitting a voxel should be our early-exit condition that lets us stop ray-marching - we shouldn't keep ray-marching until we hit the light.
- Inaccuracy - If you imagine a long solid wall of blocks with a light on the other side, if the wall is thinner at one point, then the shadow cast by this light will be less dim at that point, but that's not how it should work at all unless the surface is meant to be semitransparent.
A more practical example is how blocks which are low to the ground get shaded with a gradient towards the top (on the faces facing away from the light) - this is (presumably) because the screen rays hitting that block are sending out shadow rays backwards towards the light, and the rays that are closer to the top of the block have these shadow rays travelling less far through the block.
A possible way to speed this up AND make it more accurate without destroying the whole ray-marching thing is to have each ray remember the normal of the block-face it hits, and then any shadow rays it would have shot that are going backwards relative to that normal (which I think you can test for via dot-product) exit early and return a uniform "shadow" colour value.
Breakdown of how you might implement this:
- As a one-time process when creating a screen ray, read the XYZ components of its direction vector, and create three vectors that are:
1: (1, 0, 0) if the ray direction vector X is negative, (-1, 0, 0) otherwise (set as None if ray direction X-component is exactly 0)
2: (0, 1, 0) if the ray direction vector Y is negative, (0, -1, 0) otherwise (set as None if ray direction Y-component is exactly 0)
3: (0, 0, 1) if the ray direction vector Z is negative, (0, 0, -1) otherwise (set as None if ray direction Z-component is exactly 0)
(We can only safely do this because the walls of voxels, and of our blocks, are inherently axis-aligned)
- As a one-time process when ray-marching and inside a block:
For each of the previously created vectors that is not None, create an infinitely large plane where the origin is the block's position offset by this vector * the block's width
Then, project the ray onto that plane, yielding a t value (distance from ray origin to point on plane where the ray hits).
We can return None (or a crazily large value to prevent having to test for None later) for the t value if the point on this plane is outside the block's bounding box.
(The idea is that since our ray-march is inside the box, we have to have hit at least one of the three planes, or the two planes in the case where the block has no valid top/bottom face.)
Then, the smallest t value found out of these up-to-three tests must be the normal vector of the face on the block that we hit.
So, the ray stores that, and when creating shadow rays, if the direction of the shadow ray would be opposite to the normal, we just skip that shadow ray.
Of course, the added ray-plane intersections for each time a screen ray hits a block, and added dot-product test for each shadow ray we create might outweigh the early-exit potential that this gives us. So this might not solve any performance problems at all.
I'm also not saying you *should* have implemented this, since this video was clearly only meant to be a quick re-implementation of the original ray-tracer and was clearly only meant to show how its code could have been organised better, *not* how it could have produced a prettier result or ran faster.
A possible way to optimise the screen-ray intersections in my implementation breakdown is to have the map generator precompute which horizontal faces a block has that aren't perfectly flush with the horizontal face of another block, so we can avoid performing the ray-intersection test for a plane which is between two blocks and therefore shouldn't exist.
This would make the scene take longer to load, though, and also increase memory usage.
My implementation also wouldn't actually solve the problem of shadow rays being blatantly able to penetrate solid walls that AREN'T part of the block their screen ray hit, unfortunately - it'd only solve the unnatural shading on block faces that are facing away from the light.
There's no real way to solve this that doesn't involve rebuilding the entire system.
With that in mind, the most natural idea in my mind is to use the same intersection system as the screen rays (ray-march, then nearest-plane-intersection) to also find the normal of the surface a shadow-ray hits, then iterate along the perpendicular axis of that normal:
(suppose Z is the vertical axis, cause I don't know which axis is vertical in your implentation)
if hit face normal is +X or -X, iterate over Y-axis
if hit face normal is +Y or -Y, iterate over X-axis
if hit face normal is +Z or -Z, iterate over both X and Y axes
After the shadow-ray intersection tests, we test whether the hit point is positive or negative on the perpendicular axes relative to the halfway point (or plane origin) of the plane that we hit.
So, supposing we hit a +X face of a block - if the (ray hit point y - plane origin y) delta is positive, then we're iterating over blocks in the +Y direction, otherwise we're iterating in the -Y direction.
(We would, of course, calculate direction for both the X and Y axes if we hit a vertical block face).
From there, we index into the some kind of block array with an offset of 1 in the direction we've decided: so, if the block array is a top-down 2D array, and we hit a block at [26, 30] and are iterating in the +Y direction, we're checking if there's a block at [26, 31].
If there is, we can safely assume that the wall we've hit continues, and we don't have to do soft-shadows.
If there isn't, we can then inverse-lerp the (ray hit point y - plane origin y) delta we've calculated earlier in the range (0, half a block-width) to find how close the hit point is to the edge of the point.
Based on that, we can lerp the ray colour between fully in shadow and fully in light, creating a soft shadow.
(Side-note: You might want to take the result of the inverse-lerp calculation to the power of 0.5, so that instead of a gradient from fully bright at the edge of the block to fully dark at halfway, it's more biased towards darkness closer to the edge of the block.)
(Also remember that this isn't what's showing on the SURFACE of the block we hit since these are shadow-rays - it's what's showing on the floor before that block)
EDIT: There's another case where we shouldn't do soft-shadows on a wall - that being the case where it's part of an internal corner with another wall.
In order to solve this, let's again use the case where we hit a +X face at [26, 30]:
We have to test for a continuation of the wall at [26, 31], but we can also test for an internal corner by taking the parallel direction of the face (in this case +X) and testing for a block by adding that offset to the perpendicular offset - so, in this case, [+X, +Y]. So, if there's a block at [27, 31], we can also avoid doing soft-shadows and return early.
This test should also be done *before* the wall-continuation test, since if our +X wall is part of an internal corner, we can implicitly assume that it cannot possibly be part of a continuous wall in the same direction, and skip doing the wall-continuation test.
Another way of wording it: If we know there's a block at [26, 30] and one at [27, 31], the block at [26, 31] wouldn't be visible to our ray anyway, so we don't have to check if it's there.
Thankyou for your very thorough notes. I’ve taken screenshots of everything and will review at my convenience 🙂
You mean documentation ?