Sparse Voxel Octrees

Demonstration of sparse voxel octree implementation for my computational geometry course.
(0:00) Description of sample data sets
(0:23) Octree
(2:11) Raytracing
(3:35) Raytracing the sphere
(5:15) Tracking a ray casted by the camera
(6:43) Looking down a diagonal of the regular grid

[@mattizzle81]

This is one of the best explanations/demonstrations of what voxel octrees are that I've seen. I fully understand it now. I don't think all that traversal of trees is the most efficient for GPUs though. GPUs want to work with uniform data, not branching structures like this. I prefer the concept of voxel hashing, because it seems much more straightforward on GPU.

[@OghmaNano]

That's really nice.

[@tranceemerson8325]

"the child of this voxel's parent" umm.. okay so.. this voxel.

[@Paulo_Dirac]

Do you have any data relating the total number of points, the time to generate the octree, the time to sort closest point to the camera, intersecting the ray??

[@williamlohry9938]

For the datapoints in the video, it can run realtime, so

[@Paulo_Dirac]

That's impressive, i've been implementing a way of hit-testing facets without octree, which is in some way efficient, but far less than that... Is there any way to get any release or code to test (mine is in C#)?

[@williamlohry9938]

@@Paulo_Dirac unfortunately I can't provide source code at this point, but I can give some implementation details of a version that may be helpful. Each voxel octet is stored as two bytes, where the first byte represents the occupancy and the second byte represents a pointer to the next octet. For the first byte, each bit of that byte represents the occupancy (1 = some sub-voxel is occupied, 0 = no sub-voxels are occupied). This helps avoid traversing down empty voxels. For the second byte, if the index of the next voxel is within 254 spaces, the byte stores the next index. That is, if the voxels are in an array V, and the current voxel is located at V[i], then the byte stores j= 255, the stored byte is 255 and the index of the next voxel can be looked up in a table. (All voxels are stored in an array where each element is 2 bytes). This allows the scene to be stored very compactly. I found that the key to speed on the CPU is how compactly the memory can be stored. Once the size of the data exceeds the L2 cache size, the code slows down dramatically.

[@vitarka1811]

Could you please let me know the which is this visualization tool?

[@williamlohry9938]

The code was written in C++ using Cinder / OpenGL. See libcinder.org/
To vary the color with intensity, I used HSV with saturation/value set to max and the hue varying with intensity. Then the color was converted to RGB for display

[@linovermac]

*_Please, source code github link_*

[@linovermac]

@championchap *_:(_*