douglas i've been watching your game dev videos for awhile now and since you don't have an email or a discord i'll ask here i want to work with you on a game i have planned if you are curious lemme know afterall you where to find me, just reply to this message

Thanks! I intend to do so!

Eyooo hello

Ohh I get it, so that the cache isn't wasted on data segments that may not even be used as the ray may skip the voxel brick, and also the bitmask data of the surrounding voxel bricks are loaded ahead of time to be used spontaneously, and reducing updating the cache frequently. Determining the neighbouring 15 voxel brick bitmask data to store could be determined using 2x2x4, 1x2x8, 1x4x4 and 1x1x16 bounding boxes that can be offset and rotated based on the ray general direction and position. The ray's position in the bounding box would prob be in the far corner, and the shape of the bounding box (1x1x16, 2x2x4, etc) is determined whether the ray is moving closely axis aligned, or sharply in two axis, etc. You would prob need to take into account the relative hierarchical voxel size that the ray is currently at. But that approach sound complicated, and you could prob just pack 64 bricks' bitmasks together into 4 128 bytes aligned cache line (but idk how cache works so i may be wrong).

Thanks for the suggestions! I'll be sure to check out the OpenVDB implementation. As for cache lines, that's a very good point. I'll have to experiment with alternate data layouts in the future. But there's one nuance that I didn't mention - data segments are variable length. So if a brick has a single non-empty child, then the data segment will only be 4 bytes. But coming up with a way to pack the bitmasks (maybe I could store the bitmasks inline alongside each child pointer) might also help with cache coherency! That said, I don't really think that I'm memory bound right now :)

This is some crazy low level thinking i aspire to be like this

@@DouglasDwyer You can be limited by memory bandwidth separately from being limited by memory capacity. :)

Thanks for watching! I do the same thing in my engine that you describe. What you call reinitializing DDA is what I'm referring to as a ray-cube intersection test, since you use the cube and ray position data to determine the side of closest hit :) Edit: speaking of your engine, can't wait to see your next video!

@@DouglasDwyer Ah I see, makes sense. I avoid the ray-cube intersection by subtracting position within the node and multiplying by 2 when descending. I keep a stack of node positions to ascend. It would be slightly more complicated for a 64-tree like you have though.

You are so right!

Good suggestion. I was curious to see how it would turn out, but perhaps KZfaq's compression butchers it...

@@DouglasDwyerI actually was going to say I liked it!

@@DouglasDwyerI really liked it. Thought that it was a really nice detail, even with compression.

I am not planning to reduce quality for discrete graphics cards. The lower quality will just be an option for the engine to run on iGPUs

i meant on the videos :p

@@linksword7110 Oh gotcha haha. I'm glad to hear you thought the quality is still good. This video only took 8 hours total to produce!

Will do!

Thank you :)

Maybe I could draw a picture if you wanted 😆 it might make more sense then.

kind of like palette compression?

@@sti3167 more like grid compression? I do not know what exactly is pallete compression :D. Imagine grid 256x256x256 and each voxel has size 1.0. So to compress it and traverse faster I take some number by which is 256 divisible. Lets say 8. So I create new grid with dimensions 32x32x32 ( 256 / 8 ) and voxel size 1.0 * 8. Now I go through original grid by checking 8x8x8 subgrids. If that subgrid has uniform voxel I copy in top compressed grid just single voxel instead all of them. If they are not uniform I copy all of the voxels. When raymarching I raymarch compressed grid as if it was regular voxel grid. But once I get inside voxel (cell) which has more voxels inside, I switch to traversing that subgrid with dimensions 8x8x8.

So in the end it is grid of smaller grids. Which I create from denser grid.

@@simongido565 Sounds like you are generating and using LoDs/mips for voxels on multilevel grid(or nested grid, sometimes called brick-map) depending on distance/required details. I would love to see some code of how you generate it/store/traverse, but its up to you : ) P.S Afaik palette compression is about compressing data that belongs to voxels instead of storing it in voxels themselves - for example unique colors or normals etc in a chunk of voxels is being written to a lookup-table(or something like that) and then every voxel indexes into this table instead of directly defining it, that way you can minimize memory overheads using less bits, even without doing quantization/lossy compression. This might improve performance too, because that way you can ensure you are not memory bound and there are less cache misses because it can fit into shared memory, cache lines etc

Well, I would love to "pull a John Lin" by dropping the most gorgeous voxel world renderer. But I don't intend to disappear!

Thank you!

struct OctreeNode { uint data; // Basically an enum using the following constants uint[8] children; }; // Different materials are not implemented yet so full and empty are the only two states a voxel can be const uint EMPTY = 0; const uint FULL = 1; const uint PARTIAL = 2; // For parent nodes who have some full (or partial) children and some empty children struct Ray { bool hit; uvec3 position; ivec3 normal; float depth; }; layout(std430, binding = 1) buffer World { OctreeNode world[]; }; ... Ray castRay(vec3 rayOrigin, vec3 rayDirection) { ... // Ray box intersection on the size of the octree in case the ray starts outside the octree is omitted ray.position = uvec3(floor(rayOrigin)); ray.depth = 0; vec3 stepSize = vec3( sqrt(1 + (rayDirection.y*rayDirection.y + rayDirection.z*rayDirection.z) / (rayDirection.x*rayDirection.x)), sqrt(1 + (rayDirection.x*rayDirection.x + rayDirection.z*rayDirection.z) / (rayDirection.y*rayDirection.y)), sqrt(1 + (rayDirection.x*rayDirection.x + rayDirection.y*rayDirection.y) / (rayDirection.z*rayDirection.z)) ); ivec3 direction = ivec3(sign(rayDirection)); vec3 rayLength = mix(rayOrigin - ray.position, 1 - rayOrigin + ray.position, step(0.0, rayDirection)) * stepSize; // The stack is stored as an array indexed by currentLevel which is incremented every time we descend down the octree // It stores uints which are indices into the world array uint nodes[OCTREE_LEVELS + 1]; uint currentLevel = OCTREE_LEVELS; // Level 0 is an individual voxel nodes[currentLevel] = 0; // Root node is always index 0 uvec3 currentNodePosition = uvec3(0); while (ray.depth < RENDER_DISTANCE) { while (world[nodes[currentLevel]].data == PARTIAL) { currentLevel--; uint voxelWidth = uint(pow(2, currentLevel)); uvec3 center = currentNodePosition + uvec3(voxelWidth); uvec3 subnode = uvec3(greaterThanEqual(ray.position, center)); currentNodePosition += subnode * voxelWidth; nodes[currentLevel] = world[nodes[currentLevel + 1]].children[subnode.x + subnode.y * 2 + subnode.z * 4]; } if (world[nodes[currentLevel]].data == FULL) { ray.hit = true; return ray; } // DDA step + store hit info for if we hit something // Possible optimization: instead of taking one unit long steps, take steps proportional to the size of the current node. i.e. if the current node is empty and 4 voxels wide, step 4x the distance. I could not get that working at the moment, though, as it brings extra complications. :/ if (rayLength.x < rayLength.y && rayLength.x < rayLength.z) { ray.position.x += direction.x; ray.depth = rayLength.x; rayLength.x += stepSize.x; ray.normal = ivec3(1.0, 0.0, 0.0) * -ivec3(sign(rayDirection)); } else if (rayLength.y < rayLength.z) { ray.position.y += direction.y; ray.depth = rayLength.y; rayLength.y += stepSize.y; ray.normal = ivec3(0.0, 1.0, 0.0) * -ivec3(sign(rayDirection)); } else { ray.position.z += direction.z; ray.depth = rayLength.z; rayLength.z += stepSize.z; ray.normal = ivec3(0.0, 0.0, 1.0) * -ivec3(sign(rayDirection)); } // Bounds check if (ray.position.x < 0 || ray.position.y < 0 || ray.position.z < 0 || ray.position.x >= worldSize || ray.position.y >= worldSize || ray.position.z >= worldSize) { return ray; } // I was lazy and went all the way up to the root node every time and left only going up as far as necessary for "later" currentLevel = OCTREE_LEVELS; nodes[currentLevel] = 0; currentNodePosition = uvec3(0); } return ray; }

Thanks for watching! I prefer the look of smooth cubic voxels, so I'm not planning to integrate marching cubes at this time (it would also make ray traversal more complicated)

Interesting - I'll be sure to check it out :)

"Grid traversal" algorithms is the name that I learned for some of these.

Ray marching is just the process of stepping the ray forward by some amount instead of using analytical formulas, if you visit the wikipedia page it tells you the name of those two specific variations, sphere tracing for SDF-s and cube-assisted raymarching for voxel traversal, although I personally see that referred to more as "voxel tracing"

Thanks for watching! I think that most of Vericidium's optimizations are very good, but they mostly apply to rasterizing voxels. Since I'm ray marching, they don't apply.

I haven't studied fluid simulation yet, so unfortunately I probably won't get to it for a while. But I would love to have water like John Lin's!

While the renderer supports unaligned objects, I haven't re-added voxel entities on the game logic side. The functionality is there - hoping to take advantage of it in a future episode!

@@DouglasDwyer How do you ray trace the unaligned objects, or rather shoot rays through/past the unaligned obejcts? Do you trace them in separate passes and the composite them into a single image? I'm mostly trying to conceptualize how one would perform DDA while encountering things that are off grid.

Bresenham's algorithm is not conservative - it may miss voxels on the line that rays pass through. As such, using Bresenham using would result in gaps and artifacts appearing on objects.

I guess you could keep track of how many levels you are stepping between and do a bitshift of double the number of difference in levels of hierarchy, but it would probably be more computationally efficient just to do a double bitshift each time so you don't have to keep track of anything.

Unfortunately, I don't quite think that this works. With DDA, you store the distance along the ray to each plane of the current voxel. But if you move up/down tree levels, the planes may shift by non-uniform amounts. There are perhaps ways to update the plane positions based upon the initial and final voxel, but I don't know of any that are more efficient than just reinitializing DDA from scratch (which is equivalent to a ray-box intersection test).

@@DouglasDwyer I am willing to believe I made some kind of mistake.

​@@DouglasDwyer I don't know if this would necessarily be faster, but you could, if nothing else, theoretically update the plane positions in linear time. If the axes are aligned to the voxel grid (which could be done with a matrix multiplication for the camera and ray just once in the beginning), it would mostly just be addition, subtraction and bitshifts to move the planes around.

Yes, that's correct. The maximum distance that a ray can travel depends upon the size of the voxel (i.e. hierarchy depth) and the distance between adjacent rays. Adjacent rays "spread out" as they progress with a perspective camera, so that needs to be accounted for.

I am using a similar technique to the one described on this page: lodev.org/cgtutor/raycasting.html The problem is that when you step between grid levels, the distance from the ray to the current X/Y/Z planes changes in a non-uniform way. You need to update that distance somehow, and as far as I can tell updating the distance and recomputing it are pretty similar computationally. So every time I switch grid levels, I need to recompute the DDA variables. This is what I refer to as performing a box-intersection test, since it's the same thing mathematically.

@@DouglasDwyer you could attempt updating it each time the voxel size changes, and if it's not as performant as box intersection tests then you could just stick to box intersection tests. The algorithm I'm using for my voxel game is the Fast Voxel Traversal Algorithm, which doesn't use as much trig functions

Thanks for trying the demo! It sounds like your computer doesn't support Vulkan or WebGPU. I will add an error message in the future for unsupported devices.

The project is written entirely from scratch in Rust and uses WebGPU as the graphics API. The project is not open-source at present, but many components of it (like the event system are networking system) are open-source on my GitHub!

Thanks for watching! 1. The world is divided into 256³ chunks. Each chunk is its own tree. A pointer from each chunk to its tree structure is stored in a 3D array. 2. The masks are procedurally generated at compile-time. There are 64 possible positions within a brick and eight possible octants for the direction (determined by -x or +x, -y or +y, and -z or +z). Hence, there are 512 masks. I generate them by looping over every combination and testing all voxels to see which ones the mask should include.

@@DouglasDwyer Thank you for answering! I thought the rays were projected from a point behind the screen? How can their directions be so limited, then?

You're correct - the rays themselves can have virtually infinite directions. However, the masks don't need to be one-to-one. All rays that point toward the same octant are grouped. So a ray whose direction has a negative x-component, positive y-component, and negative z-component will be grouped with all other -x,+y,-z rays. The same goes for all other combinations of positive and negative cardinal axes. This way, we can eliminate all voxels that lay to the opposite side. If a direction has a negative x-component, then we know it cannot hit voxels that have a positive x-displacement from the ray, for example.

@@DouglasDwyer Oh, I get it now! What an awesome optimization.

There's already a demo playable online! But yes, I hope to turn this into an actual game someday.

This is being rendered on GPU using a custom shader so everything is inherently SIMD

Other optimizations in mine and your raymarcher are actually pretty simillar :) for bitmasks etc

The project is written entirely in Rust and uses WebGPU as the graphics API.

Yep, the LOD generation isn't perfect. The LOD leaking shouldn't happen as much with procedurally generated terrain and other solid models. It happens because the church has a lot of thin surfaces and so the engine isn't sure which surface to put on top when generating the higher LODs.

My GTX 1060 can handle 1500x1500 resolution at 60fps (2.25 mega pixels (1080p is 2.0736MP), there is no performance difference between web/native

Speaking slowly and clearly is important for public speaking, so that's what I aim to do. But you are more than welcome to enjoy the video at 1.25x if you'd like!

Yep! As noted in the video, the benchmarks presented were on a very bad GPU (Intel UHD 750H). On any discrete card, the engine runs at a buttery-smooth 60 FPS - for example, the scenes in the video run at 4 ms (or 250 FPS) on my NVIDIA 1660 TI. It's possible to make the game run in realtime on the Intel GPU as well by lowering the resolution. But for benchmarking I wanted the frame times to be as big as possible, so I chose a worst case.

@@DouglasDwyer Too bad a discrete card is a requirement, as I'm afraid I only use integrated cards, but that is a whole lot of voxels there, so I guess it makes sense.

Discrete card is only a requirement for 1080p. If you play the game at a lower resolution, you can definitely hit 60 FPS on an iGPU. But don't take my word for it - try the demo and evaluate for yourself! There is an option in the settings menu to downscale the image resolution for better performance :)

@@DouglasDwyer can you please show in pseudo-code how you do ensure low res wont step too far 11:06 ? i didnt quite get it, also what it would be like to trace more coarse lods in pre-pass, for example on CPU side? still could avoid a lot of traversal iterations. How do you even make sure its done in conservative manner? wont it require supercover dda or smth, hard to imagine tbh

raymarching is raycasting in small steps

@@sjoerdev raymarching is raycasting based on minimum distance to objects?

@@shadow_blader192 thats sphere tracing which is a form of raymarching

@@sjoerdev oh those names

No idea, everyone seems to have their own names for these algorithms lol

So apparently commenting "First" in French earned me a heart... my studying is paying off!

​@@mohammadazad8350je suis là pour tester ton français 👀 voyons voir si ça paye tant que ça 😂

@@timmygilbert4102 "I am ??? for test your (familiar) French. Let's see see if that pays ??? that that" By interpolating, we get: "I am going to test your French, let's see if it paid off". I can't believe a KZfaq comment just gave an exam on something I do for fun :).

*gave me Also, I genuinely had to resist the urge to look up "tant" in the dictionary.

@@mohammadazad8350 good job 👍😁

Thanks for trying out the demo! If you'd like to help debug the issue, please open a ticket at github.com/DouglasDwyer/octo-release. Open the developer console in Chrome (Firefox is not supported) and copy-paste what you see :)

@@DouglasDwyer I'm too lazy so I do it here.. Uncaught (in promise) Error: Using exceptions for control flow, don't mind me. This isn't actually an error! at imports.wbg.__wbindgen_throw (web-1b9437e1ec3ce582.js:958:15) at web-1b9437e1ec3ce582_bg.wasm:0x5e1292 at web-1b9437e1ec3ce582_bg.wasm:0x2dc81b at web-1b9437e1ec3ce582_bg.wasm:0x56f919 at web-1b9437e1ec3ce582_bg.wasm:0x591e27 at __wbg_finalize_init (web-1b9437e1ec3ce582.js:1948:10) at __wbg_init (web-1b9437e1ec3ce582.js:1984:12) octo-release/:1 No available adapters. octo-release/:1 No available adapters. web-1b9437e1ec3ce582.js:618 panicked at game\hal\src\gpu.rs:242:51: Could not load GPU adapter. Stack: Error at imports.wbg.__wbg_new_abda76e883ba8a5f (douglasdwyer.github.io/octo-release/web-1b9437e1ec3ce582.js:602:21) at douglasdwyer.github.io/octo-release/web-1b9437e1ec3ce582_bg.wasm:wasm-function[4786]:0x5e5856 at douglasdwyer.github.io/octo-release/web-1b9437e1ec3ce582_bg.wasm:wasm-function[2553]:0x578261 at douglasdwyer.github.io/octo-release/web-1b9437e1ec3ce582_bg.wasm:wasm-function[3660]:0x5d775c at douglasdwyer.github.io/octo-release/web-1b9437e1ec3ce582_bg.wasm:wasm-function[3610]:0x5d6b19 at douglasdwyer.github.io/octo-release/web-1b9437e1ec3ce582_bg.wasm:wasm-function[3809]:0x5da3ca at douglasdwyer.github.io/octo-release/web-1b9437e1ec3ce582_bg.wasm:wasm-function[691]:0x38bb86 at douglasdwyer.github.io/octo-release/web-1b9437e1ec3ce582_bg.wasm:wasm-function[1936]:0x537364 at douglasdwyer.github.io/octo-release/web-1b9437e1ec3ce582_bg.wasm:wasm-function[1780]:0x52167d at douglasdwyer.github.io/octo-release/web-1b9437e1ec3ce582_bg.wasm:wasm-function[459]:0x229111

Thanks for doing this, I really appreciate it! For whatever reason, it looks like your web browser doesn't support WebGPU. Eventually, I'll get around to adding a proper error message for when devices aren't supported.

Since a voxel brick has 4^3 = 64 voxels, with one bit per voxel, each brick has 1 64-bit occupancy mask.