If you're ray-tracing voxels on a GPU, one technique is to use a single bit per voxel (so 32 voxels per uint32_t: a 0 bit means empty, a 1-bit means filled) and then put the whole voxel space into a Morton space-filling curve like this:
You can then cast rays through 3D space mapped onto 1D space, with one ray per GPU thread.
The space-filling curve gives you locality of reference (just like an octree), and the simple linear nature of the data means you can use a sparse bit vector to represent it. Huge regions without voxels are represented implicitly:
I’m not sure the linked app is ray tracing voxels per se, but can confirm the active bitmask and Morton tricks work really well. I’ve actually just built a renderer with some co-workers that does both of these things. We have not used the trick you show of stepping without de-interleaving Morton, that is very clever! I’m going to try it and see if it speeds things up.
BTW, on the GPU Morton is handy and convenient but not the absolute fastest. You can do simple tiling and get all the cache benefits in fewer instructions. It’s kind-of like one single Morton interleave step, say, for example, interleave the bottom 3 bits and then the top 7 bits. (But note you can’t blindly interleave any number of top bits anymore, it needs to be the exact number of bits you’re using, or a row-major indexing calculation using a multiply instead of bit shifting.)
I used this technique commercially (about 5 years ago) to build voxel representations of the world in real-time from lidar data (Velodyne VLP-32C).
Each lidar return (a 3D point) provides a line of empty voxels from the lidar origin to the location where the laser hit a surface. Because you know the light followed that line uninterrupted, you know all the voxels on the line are empty.
The lidar is giving you thousands of points per second and the lines (derived from the points) carve the voxel space. The voxel space is rendered continuously. It's very satisfying to watch the space being carved out.
I don't know of anyone else using this technique before me, and I don't know of anyone doing it now.
From a laymans point of view (aka knowing nothing about voxels), that sounds like a clever idea and I'm tempted to try this for my next gaming/visualization side project.
I read or saw a similar paper. I guess that they used (multiple) 3D cameras instead of a LiDAR to get the point cloud. But otherwise it was similar. They used a octree or similar data structure for speed up. What did you use?
They were talking about the concept of carving out empty space to leave a 3d representation of the thing you’re interested in, which was the primary method in your comment. This can be done with images using the background segmentation, and cutting with the edge/profile of the object, for each 2d view, and assisted with other 2d to 3d methods.
It can be used for live 3d models with single (tracked and moving) or multiple (known and fixed) cameras.
If it was the same that I read, it was a neat paper, but I’m having trouble finding it within a few searches. I don’t recall I’d they used a point cloud or voxels, but the difference between the storage of the 3d structure as a point cloud or voxel doesn’t seem to warrant your response. They’re trivially converted to one another, in this context.
Seems like it uses a WebGL feature that Firefox doesn't support? Whatever the boolean "isManualMipMappingSupported" refers to probably doesn't work in my browser (because EXT_color_buffer_float is supported by Firefox and so is normal WebGL and those are the three checks that make "WebGL is not available" appear). At least the detection is done based on feature detection rather than simple user agent filtering, so this demo should work when Firefox eventually adds whatever feature this site is relying on.
Of course, we're in the era where a browser is either chrome, or it's wrong. For pretty much exactly the same reasons that we used to have "this site requires IE" obnoxiousness.
Doesn't seem to work correctly for me on Firefox (on Windows, with an Nvidia 1060 ti), fine on Chrome. On firefox I get an orange triangle in the lower right corner, and that's about it. Moving around causes the texture to build up in that triangle.
Seems like they're using some features that are not available in all browsers, and failing with a single error message instead of explaining which feature is missing.
My Firefox is now stuck with a note at the top of the screen saying something like "voxelchain.app is controlling your mouse cursor. Please press ESC to take over."
I would love to see somebody code this up to run in the browser -- it's from 2003, so I bet it could now run really fast with lots of voxels. It will steal your face right off your head. Happy Halloween!
1,367 views Jul 31, 2009:
A prototype user interface for browsing volume data. Presented at IEEE VIS 2003 by Michael J. McGuffin, Liviu Tancau, and Ravin Balakrishnan. For more information, see
I really don't get why people munge very specific, detailed errors into something so generic as to be outright misleading.
WebGL is absolutely available in my browser. The issue, unlike what the site logs to console and does not tell the user (in this case), is:
> WebGL warning: readPixels: Format and type RGBA_INTEGER/UNSIGNED_BYTE incompatible with this RGBA8UI attachment. This framebuffer requires either RGBA_INTEGER/UNSIGNED_INT or getParameter(IMPLEMENTATION_COLOR_READ_FORMAT/_TYPE) RGBA_INTEGER/UNSIGNED_INT.
Which is gibberish to me, but in fact less confusing than the presented error.
Totally awesome rendering, but how do I keep from dropping through the floor? I’m on a laptop+Chrome. The shift keys seem to be the only way to change elevation and both go down. Would be nice if Q & E would go up down, since they’re in the locus of the WASD controls.
Is this really ray tracing the glass bits? The way it turns on & off when passing through the glass surface hints at some hybrid shader tricks, perhaps?
https://bugfix-66.com/e2d9aaf5b7f285b4d35c46e87fcf6f7e25d338...
You can then cast rays through 3D space mapped onto 1D space, with one ray per GPU thread.
The space-filling curve gives you locality of reference (just like an octree), and the simple linear nature of the data means you can use a sparse bit vector to represent it. Huge regions without voxels are represented implicitly:
https://bugfix-66.com/7256e0772dc3b02d72abf15b171731c933fd44...
Of course, you want a much larger branching factor (to get a shallower tree) for rendering.
You can step your ray through the space without deinterleaving the bits, like this:
https://bugfix-66.com/d6907b4d3eb6330241128ffbaeef6194ddeecc...
This technique allows extremely detailed (and real-time editable!) voxel worlds with tiny code.