3 ms·

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

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: https://bugfix-66.com/e2d9aaf5b7f285b4d35c46e87fcf6f7e25d338d7315b16ef2138022930129e2d 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/7256e0772dc3b02d72abf15b171731c933fd44d67de074d679f1e4cb7bb20f79 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/d6907b4d3eb6330241128ffbaeef6194ddeecc6e0d18f7e7057f7b58206e9f2e https://bugfix-66.com/d6907b4d3eb6330241128ffbaeef6194ddeecc... This technique allows extremely detailed (and real-time editable!) voxel worlds with tiny code.

gfodor 4y ago
Damn, thanks for this info
lwansbrough 4y ago
Do you have a demonstration of this or can you point to anyone using this method?
- bugfix-66 4y ago
  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.
  - lizen_one 4y ago
    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?
    - bugfix-66 4y ago
      I take it you didn't "read or see" anything I wrote above. But thanks for taking the time to post a comment!
      - nomel 4y ago
        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.
  - arlcode 4y ago
    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. Thanks for the inspiration
deleted 4y ago
[deleted]
dahart 4y ago
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.)
- bugfix-66 4y ago
  The fix for the noncontiguous addition puzzle is to change filled = to & mask to filled = to | ^mask In other words, to OR in 1-bits so the carry can travel across the irrelevant part of the register. Subtraction is similar: https://bugfix-66.com/adbc40fa7c8c838d8d34bcd35525313dc91dea0149647b701cfb8d99b5aa0f27 https://bugfix-66.com/adbc40fa7c8c838d8d34bcd35525313dc91dea... But for subtraction you want to AND in 0-bits so the borrow can travel.
jb1991 4y ago
I’m going to have to read this comment many times, but this part is totally confusing to me: > You can then cast rays through 3D space mapped onto 1D space, with one ray per GPU thread. I can’t figure out what this actually means, to map a 3D space onto a 1D space?
- orbital-decay 4y ago
  The Wikipedia page has a concise explanation for this particular sort of locality-preserving mapping: https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve It also gives a potentially better alternative.

gfodor 4y ago

Damn, thanks for this info

lwansbrough 4y ago

Do you have a demonstration of this or can you point to anyone using this method?

bugfix-66 4y ago
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.
- lizen_one 4y ago
  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?
  - bugfix-66 4y ago
    I take it you didn't "read or see" anything I wrote above. But thanks for taking the time to post a comment!
    - nomel 4y ago
      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.
- arlcode 4y ago
  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. Thanks for the inspiration

deleted 4y ago

[deleted]

dahart 4y ago

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.)

bugfix-66 4y ago
The fix for the noncontiguous addition puzzle is to change filled = to & mask to filled = to | ^mask In other words, to OR in 1-bits so the carry can travel across the irrelevant part of the register. Subtraction is similar: https://bugfix-66.com/adbc40fa7c8c838d8d34bcd35525313dc91dea0149647b701cfb8d99b5aa0f27 https://bugfix-66.com/adbc40fa7c8c838d8d34bcd35525313dc91dea... But for subtraction you want to AND in 0-bits so the borrow can travel.

jb1991 4y ago

I’m going to have to read this comment many times, but this part is totally confusing to me: > You can then cast rays through 3D space mapped onto 1D space, with one ray per GPU thread. I can’t figure out what this actually means, to map a 3D space onto a 1D space?

orbital-decay 4y ago
The Wikipedia page has a concise explanation for this particular sort of locality-preserving mapping: https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve It also gives a potentially better alternative.