Tetahexacontree 4x4x4 Occupancy Bitmasks Lookup Table


My voxel engine uses a tetahexacontree (or 64 way space partition tree) with occupancy bitmasks at each brick (or node which references up to 64 [4x4x4] other nodes or voxel volumes).  The bitmasks are used in optimization of ray marching by means of taking ray direction and location at each brick arrived at and determining if the brick (and possibly sub-bricks) should be traversed or skipped (leaped over) via a bitwise and'ing with an entry from lookup table of occupancy required bitmasks.

I became curious what my table looks like as an image to see if there is a pattern that could be computational cheap to calculate individual occupancy bitmasks on the fly instead of using the table lookup.  Here's what it looks like (each row is a uint64, least significant bit at right, binary ones are white and zeros are black) :


I see no way to cheaply calculate occupancy required bitmasks on the fly in my shader, but it was an interesting thing to explore none the less.

I also added a compile time option for enabling visualization of brick leaping with respect to occupancy requirement bitmask tests.  Pink indicates one or more leaps of voxel volume bricks, green indicates one or more leaps of node bricks, and yellow indicates both have occurred:

I've also explored ray marching the tree via as little integer to floating point data type conversation as possible to see if that would speed up performance.  That required (in the way I implemented it) using floating point coordinates between 1 and 2 (normalized tree coordinates offset by 1) for better floating point accuracy and less floating point epsilon values needed to make it work.  In the end, I discovered performance was only slightly faster, but there were visual artifacts at brick/node boundaries that I could not find a fix for.  So the ray marching is back to using a combination of integer and floating point data types with floating point epsilon values used to avoid visual artifacts.

Leave a comment

Log in with itch.io to leave a comment.