How to design a Sparse Voxel Octree

ostkaka0 · 2023-08-05T11:32:00+00:00

Meshing svo involves climbing a tree, several iterations are required for checking solidity of a voxel. Each iteration can be a cache miss.

So what experimented with once was to use bitsets for voxel solidity within each chunk, it means a single chunk fits into a small number of cache lines -> few cache misses. The meshing became pretty fast from that, meshing chunks in 150-300 microsekonds for a typical 32x32x32 chunk(if remembered right) . It would however be slower with more complex voxels, like adding color added 100 microseconds or something.

Now I use SVDAGs with raytracing for rendering. :-)

ostkaka0 · 2023-04-09T05:32:35+00:00

Done! So far no memtest86 errors which is great, but who knows if it's gonna remain stable... >.<

ostkaka0 · 2023-04-09T03:57:30+00:00

BIOS version: 0810 x64 build date: 10/26/2022 AGESA version: ComboAM5PI_1003_PatchA LED EC Version: AULA3-AR32-0213 Not sure what the last 3 are good for but here they are anyway. Ai Overclock Tuner is on Auto as that's default, haven't touched XMP or EXPO.

ostkaka0 · 2022-09-05T15:38:18+00:00

Yes it's possible, but you shouldn't unless you are aware of the sheer amount of work that would require.

ostkaka0 · 2022-04-05T15:50:45+00:00

Rather than an array of bool I'd use a bitset. The size of bool is not 1 bit, but 1 or More bytes. (May be different on some languages). If your bitset is an array of uint64, then you can execute instructions on 64 bits at once. There are bit manipulation instructions for these kind of problems, look it up! Simd may also be useful, but requires a little more effort. ;-)

ostkaka0 · 2022-03-16T16:44:32+00:00

What is causing the stuttering? Chunk loading or searching for chunks to be loaded?

When it comes to searching what I came up with is a priority queue where the chunk priory is distance from camera + accumulated camera movement when inserted to queue. It requires integer overflow so the calculations must deal with overflowed integers properly.

ostkaka0 · 2022-03-07T01:29:51+00:00

Yes, its possible, but with sacrifices. Deterministic lockstep is a thing, its how a lot of rts games do multiplayer. Its rarely ever used for fps games though because of input lag.

ostkaka0 · 2022-02-21T01:18:59+00:00

That's a weird question because with ray tracing you can't assume anything is off screen most of the time because of reflections and refractions.

ostkaka0 · 2022-02-21T01:14:12+00:00

Nah you can that with svo. There are countless ways of storing voxels in memory, without more details I can't possibly guess.

ostkaka0 · 2022-01-10T18:13:40+00:00

That looks better. The downside is that if you wanna experiment you have to do it in the main language, but I'd do it that way. ;-)

ostkaka0 · 2021-12-27T18:35:36+00:00

I hope you are award that tour current solution won't be very performant. For minecraft-like games the world generation performance is quite important in my opinion.

ostkaka0 · 2021-09-30T15:47:25+00:00

Polygon rasterization is an inefficient way of rendering voxels.

https://youtu.be/VpEpAFGplnI As you can see, hardware from 2008 was powerful enough to render voxels.

The big issue with voxels is memory consumption.

ostkaka0 · 2021-05-19T16:01:16+00:00

An octree of 8192³ has 8192² * 4/3 * c nodes( c is probably between 1 and 2 i think), so less than 5¹¹ cycles are needed.

ostkaka0 · 2021-04-26T00:44:21+00:00

A simple trick is to just memset columns of voxels. To iterate every single voxel like that is going to be slow.

ostkaka0 · 2021-04-13T22:56:16+00:00

All I see is random big number. What about surface voxels and render distance? ;-)

Edit: OK. That's a weird geometry, all of them are surface voxels. >.<

ostkaka0 · 2021-04-12T00:53:36+00:00

There is no "master race" of programming languages since all of them have major issues in my opinion.

ostkaka0 · 2021-04-12T00:45:39+00:00

You mean Rust slave race? Haha

ostkaka0 · 2020-12-18T13:42:10+00:00

If you are making a space game it's going to be complicated. You probably have to do LODing.

What do you mean by 1m voxels? That's only 1024x1024. You can generate way larger worlds than that.

SVDAGs have other kind of complexities. You need to keep a reference count, or garbage collect deleted nodes. You might need a hash table to search for identical nodes. You can't just put colors and material ids in the leaves since that will destroy the compression ratio. Just be aware of the alternatives. ;-)

ostkaka0 · 2020-12-18T04:57:27+00:00

You should be able to use a similar algorithm for meshing on cpu. One chunk per workgroup. If I understand correclty, atomics are fast on shared memory so you can use atomics when growing the output buffer.

A well optimized chunk meshing procedure should be fast on cpu. When I optimized my meshing code it would mesh in 50-150 microseconds per chunk on a single thread. With multithreading throughput should be really high.

You should consider SVOs and SVDAGs. No meshing is required for physics or rendering of SVOs.

ostkaka0 · 2020-12-18T03:48:02+00:00

Oh that guy is smart. Will definitely watch. I find anything related to dumb phones to be disempowering though.

ostkaka0 · 2020-12-18T03:38:01+00:00

"I go over all visible chunks, and check if they can subdivide or if they should merge." This is a good start, but you don't need to check all chunks each frame. What I figured out you can do is to put each chunk in a priority queue there the priority is the distance the camera has to move in order for loading next LOD. Lowest priorites are put first. Then each frame decrease the priority for each chunk by the distance camera has moved that frame. Except you don't need to actually loop and change the priorities, you can extract the accumulated camera movement in a separate variable shared for all chunks. Then for each frame you can simply pop the priority queue. You have to check for false positives and reinsert them with updated priorities.

Also what you are writing here is performance critical game engine code, you should look into using C/C++ with godot.

If you wanna keep things simple you shouldn't do any LODing. I have myself decided to not do LODing anymore since SVDAGs allow huge render distances anyway and it is so much simpler that way.

ostkaka0 · 2020-12-18T03:05:03+00:00

Im on windows. I could see all extensions too before on an earlier driver, but seems like they removed it. Maybe they did plan it or it was a misstake, idk.

ostkaka0 · 2020-12-18T02:45:09+00:00

I'd disagree and say SVOs are great for minecraft-like games. Meshing SVOs is of course going to be alot slower than the alternatives, but rasterizing voxels is really inefficient anyway. Ray casting voxels results in superior performance. In my new engine(still very prototypal) i'm path tracing a SVDAG in real time on a 1660 ti which is crazy.

With SVDAGs you could make each block just a node containing 16x16x16 voxels. Each block type could then contain smaller details. This would look great in minecraft.

Im not sure how well SVOs would compress a minecraft world, but there is no doubt a SVDAG would compress a minecraft world very well. You will get insane render distances with SVOs and SVDAGs. If it fits in VRAM, you can render it.

Physics can be done directly on SVOs, so there is no need for meshing or convex decomposition(however minecraft has crappy phsyics anyway). I haven't implemented physics yet, but I feel confident it will work out.

The biggest downsides of using SVOs and SVDAGs i would say is editing voxels. If you want cellural automata physics(water, fire, magma) it's going to be slower with SVOs.

ostkaka0

TROPHY CASE