octree_raytracer.glsl

// make ray relative to world texture
ray_pos += float(WORLD_SIZE/2 * CHUNK_SIZE);

// flip coordinate space for ray such that ray dir is all positive
// keep track of this flip via flipmask
ivec3 flipmask = mix(ivec3(0), ivec3(-1), lessThan(ray_dir, vec3(0.0)));
ray_pos       *= mix(vec3(1), vec3(-1), lessThan(ray_dir, vec3(0.0)));

ray_dir = abs(ray_dir);

// precompute part of plane projection equation
vec3 rdir = mix(1.0 / ray_dir, vec3(INF), equal(ray_dir, vec3(0.0)));

// starting cell is where ray is
ivec3 coord = ivec3(floor(ray_pos));

int axis = 0;
float t0;

// start at highest level of octree
int mip = CHUNK_OCTREE_LAYERS-1;

for (;;) {
	// get octree cell size of current octree level
	int size = 1 << mip;
	coord &= ~(size-1); // coord = bitfieldInsert(coord, ivec3(0), 0, mip);
	
	// calculate both entry and exit distances of current octree cell
	vec3 t0v = rdir * (vec3(coord       ) - ray_pos);
	vec3 t1v = rdir * (vec3(coord + size) - ray_pos);
	t0 = max(max(t0v.x, t0v.y), t0v.z);
	float t1 = min(min(t1v.x, t1v.y), t1v.z);
	
	// handle rays starting in a cell (hit at distance 0)
	t0 = max(t0, 0.0);
	
	bool vox;
	{
		// flip coord back into original coordinate space
		ivec3 flipped = (coord ^ flipmask);
		
		// handle both stepping out of 3d texture and reaching max ray distance
		if ( !all(lessThan(uvec3(flipped), uvec3(WORLD_SIZE * CHUNK_SIZE))) ||
			 t1 >= max_dist )
			return false;
		
		// read octree cell
		flipped >>= mip;
		uint childmask = texelFetch(octree, flipped >> 1, mip).r;
		
		// get uint8_t bit index from last bits of flipped coord
		int i = flipped.x & 1;
		i = bitfieldInsert(i, flipped.y, 1, 1);
		i = bitfieldInsert(i, flipped.z, 2, 1);
		
		vox = (childmask & (1u << i)) != 0;
	}
	
	if (vox) {
		// non-air octree cell
		if (mip == 0) 
			break; // found solid leaf voxel
		
		// decend octree
		mip--;
		ivec3 child_size = ivec3(1 << mip);
		
		// upate coord by determining which child octant is entered first
		// by comparing ray hit against middle plane hits
		vec3 tmidv = rdir * (vec3(coord + child_size) - ray_pos);
		
		coord = mix(coord, coord + child_size, lessThan(tmidv, vec3(t0)));
		
	} else {
		// air octree cell, continue stepping
		
	#if 1 // better performance
	
		// step into next cell via relevant axis
		int stepbit;
		if (t1v.x == t1) {
			axis = 0;
			
			int old = coord.x;
			coord.x += size;
			// determine which bit has changed during increment
			stepbit = coord.x ^ old;
			
		} else if (t1v.y == t1) {
			axis = 1;
			
			int old = coord.y;
			coord.y += size;
			stepbit = coord.y ^ old;
		} else {
			axis = 2;
			
			int old = coord.z;
			coord.z += size;
			stepbit = coord.z ^ old;
		}
	#else // this is slightly slower
		bvec3 axismask = equal(t1v, vec3(t1));
		
		ivec3 old = coord;
		coord = mix(coord, coord + size, axismask);
		
		ivec3 stepbits = old ^ coord;
		int stepbit = stepbits.x | stepbits.y | stepbits.z;
		
		ivec3 masked = mix(ivec3(0), ivec3(0,1,2), axismask);
		axis = masked.x + masked.y + masked.z;
	#endif
		
		// determine highest changed octree parent by scanning for MSB that was changed
		mip = min(findMSB(uint(stepbit)), CHUNK_OCTREE_LAYERS-1);
	}
}