A Ray-Box Intersection Algorithm and Efficient Dynamic Voxel

For people working on the C++ code.
New member
Posts: 2
Joined: Thu Sep 20, 2018 22:08
GitHub: ray-mccord

A Ray-Box Intersection Algorithm and Efficient Dynamic Voxel

by kodemanic » Thu Sep 20, 2018 22:24

Ran across a paper that I thought might have something to offer.


We introduce a novel and efficient method for rendering large models composed of individually-oriented voxels. The core of this method is a new algorithm for computing the intersection point and normal of a 3D ray with an arbitrarily-oriented 3D box, which also has non-rendering applications in GPU physics, such as ray casting and particle collision detection. We measured throughput improvements of 2× to 10× for the intersection operation versus previous ray-box intersection algorithms on GPUs. Applying this to primary rays increases throughput 20× for direct voxel ray tracing with our method versus rasterization of optimal meshes computed from voxels, due to the combined reduction in both computation and bandwidth. Because this method uses no precomputation or spatial data structure, it is suitable for fully dynamic scenes in which every voxel potentially changes every frame. These improvements can enable a dramatic increase in dynamism, view distance, and scene density for visualization applications and voxel games such as LEGO® Worlds and Minecraft. We provide GLSL code for both our algorithm and previous alternative optimized ray-box algorithms, and an Unreal Engine 4 modification for the entire rendering method.

Source: http://www.jcgt.org/published/0007/03/04/

User avatar
Posts: 10
Joined: Tue Mar 28, 2017 18:36
Location: Russia
GitHub: weqqr
IRC: weqqr
In-game: weqqr

Re: A Ray-Box Intersection Algorithm and Efficient Dynamic V

by weqqr » Thu Oct 18, 2018 18:54

So I went ahead and implemented this paper as a standalone map renderer. It is kinda basic, simplistic, and has terrible code, but it shows that the method is indeed workable and is worth trying. I'll post the source code when I clean it up a little.

Here's a screenshot of it rendering an approximately 900x200x900 piece of map (17 million voxels, about 20 FPS on GTX 1050Ti). Every node is grass because I haven't implemented NodeDefs yet.

Here are some problems I found:
  • The method requires modifying depth in fragment shader, making GPU's depth-based fragment culling absolutely useless. This decreased performance significantly in my tests.
  • Because of the problem above, rendering voxels close to the camera is inefficient.
  • "Dramatic increase in dynamism" without sacrificing view range is only achievable on high-end GPUs.
  • Texture mapping is tricky and I'm not sure if I implemented it right.
  • Voxels that are very close to the camera disappear. I think this can be fixed by artificially increasing point size for nearby voxels.
  • Minetest has quite a lot drawtypes that aren't composed of cuboids. These have to be rendered separately.
  • The method is unsuitable for mobiles, laptops, or anything that doesn't have a decent GPU.
Most of these problems are either solvable or irrelevant for Minetest, but the last one is why it will never be used as a primary rendering method. However, this technique is surprisingly good for far map rendering, and it is better than the current solutions because it actually produces correct results instead of a crude approximation.

User avatar
Posts: 3063
Joined: Sat Sep 29, 2012 01:14
IRC: Inocudom
In-game: Inocudom

Re: A Ray-Box Intersection Algorithm and Efficient Dynamic V

by Inocudom » Sat Oct 27, 2018 18:36

Keep at it, I say. We need geniuses like you around here.
The comedic value of my videos is how abysmal they are: https://www.youtube.com/channel/UC5cyeM ... YTfYFlih_A

Return to Partly official engine development

Who is online

Users browsing this forum: No registered users and 1 guest