Scratchpad: naive encoding of the 3d bitfield array @neoshaman

Let me try a quick recap I told about storing a 2d array of bitfield, it's easy to write a way to access it like a normal array.

• The original idea was to basically do a bit operation with a rasterized array of the frustrum on gameboy
• but here as a demonstration we rastrize only one ray The idea is simple let's say you have a bitfield and you have bitmask, you can simply do an AND operation to isolate the maked part of the bitfield that is if you have 10101010 as a bitfield and 00111100 as a bit mask, the result will be 00101000, the idea is to use that property to get first hit in a bitfield with another bit trick called "leading zeroes count" google it basically there is an algorythm that let you know, how many leading/trailing zeroes there is in a bitfield -- so when rasterizing the ray into the bitfield, if the ray is acute to the bitfield direction it's likely to cover many bit in that field

imagine this is a stack of byte you can see it can be translated as 000000000 011000000 001100000 000111000 .... so basically by doing && to the bitfield array, we only isolate the part the ray intersect and other are discarded

• if we the overall byte(s) number is equal to zero we can skip immediatly as there is no intersection in that byte(s)
• if it's different of 0, then we find teh leading/trailzer zeroes (depending on direction) to find the first intsersection, as given a particular rasterization we can cover many bit, ie return multiple it, we just need the first or last 1, which then can translate to a hit position The problem seems that it mostly efficient in the bitfield direction, you still need to march the 2d array as usual but at least you have a compact (1 bit per voxel) method that is probably cache friendly
• I had considered using wavesurfing like in voxlap, but I thought it was overkill and less efficient -- that's the gist of it I was bothered by the bitfield direction stuff, so I moved to another representation, the byte cube, that is probably a less naive way to encode space, if the data is spatially coherent, it might be the most efficient way to skip space, as it preserve locality. -- does that make sense the bitfield intersection? ... the main idea comes from gameboy, I wanted to trace a a very small array, but that's still too slow on gb, so I thought if it's one bit per data I can use byte operation as an acceleration structure to process data 8 by 8! With modern computer that's 32 or 64 ... also it remind me a claim by euclidion, they say what if voxel were a database you could just query. I thought that if it's one bit and on a grid, we can effectively separate the representation from the data with a dictionary where the key is the xyz of the sampled bitfield. If bit then query color and stuff. Which rather compact and different than all people doing complex bit stuffinng where all the data are packed in byte, that mean data = "voxel grid * data length" instead of "number of voxel * data". Also compress much better with rle type encoding. ie starting index + length (only coding the 1, 0 being implicit)