octree_raytracer.glsl

// WORLD_SIZE = POT size of 3d texture with voxel data for world  eg. #define WORLD_SIZE 512
// OCTREE_MIPS = number of mips of texture

const float WORLD_SIZEf = float(WORLD_SIZE);
const uint ROUNDMASK = -1;
const uint FLIPMASK = WORLD_SIZE-1;

//// pos is relative to world 3d texture
bool trace_ray (vec3 pos, vec3 dir, float max_dist, out Hit hit) {
	
	// flip coordinate space such that ray is always positive (simplifies stepping logic)
	// keep track of flip via flipmask
	bvec3 ray_neg = lessThan(dir, vec3(0.0));
	vec3 flippedf = mix(pos, WORLD_SIZEf - pos, ray_neg);

	uvec3 flipmask = mix(uvec3(0u), uvec3(FLIPMASK), ray_neg);

	// precompute part of plane projection equation
	// prefer  'pos * inv_dir + bias'  over  'inv_dir * (pos - ray_pos)'
	// due to mad instruction
	vec3 inv_dir = mix(1.0 / abs(dir), vec3(INF), equal(dir, vec3(0.0)));
	vec3 bias = inv_dir * -flippedf;

	float dist = 0.0;

	//// This is pretty much only needed to handle rays starting outside of the world texture gracefully
	#if 0 // allow ray to start outside ray for nice debugging views
	{
		// calculate entry and exit coords into whole world cube
		vec3 t0v = inv_dir * -flippedf;
		vec3 t1v = inv_dir * (vec3(WORLD_SIZEf) - flippedf);
		float t0 = max(max(t0v.x, t0v.y), t0v.z);
		float t1 = min(min(t1v.x, t1v.y), t1v.z);
		
		// only if ray not inside cube
		t0 = max(t0, 0.0);
		t1 = max(t1, 0.0);
		
		// ray misses world texture
		if (t1 <= t0)
			return false;
		
		// adjust ray to start where it hits cube initally
		dist = t0;
		flippedf += abs(dir) * dist;
		flippedf = max(flippedf, vec3(0.0));
	}
	#else
	// cull any rays starting outside of cube
	if ( any(lessThanEqual(flippedf, vec3(0.0))) ||
		 any(greaterThanEqual(flippedf, vec3(WORLD_SIZEf))))
		return false;
	#endif

	// start at some level of octree
	// -best to start at 0 if camera on surface
	// -best at higher levels if camera were in a large empty region
	uint mip = 0;
	//uint mip = uint(OCTREE_MIPS-1);

	// round down to start cell of octree
	uvec3 coord = uvec3(floor(flippedf));
	coord &= ROUNDMASK << mip;

	for (;;) {
		uvec3 flipped = (coord ^ flipmask) >> mip;
		
		// read octree cell
		uint voxel = texelFetch(octree, ivec3(flipped), int(mip)).r;
		
		if (voxel != AIR) {
			// non-air octree cell
			if (mip == 0u)
				break; // found solid leaf voxel
			
			// decend octree
			mip--;
			uvec3 next_coord = coord + (1u << mip);
			
			// upate coord by determining which child octant is entered first
			// by comparing ray hit against middle plane hits
			vec3 tmidv = inv_dir * vec3(next_coord) + bias;
			
			coord = mix(coord, next_coord, lessThan(tmidv, vec3(dist)));
			
		} else {
			// air octree cell, continue stepping
			uvec3 next_coord = coord + (1u << mip);
			
			// calculate exit distances of next octree cell
			vec3 t0v = inv_dir * vec3(next_coord) + bias;
			dist = min(min(t0v.x, t0v.y), t0v.z);
			
			// step on axis where exit distance is lowest
			uint stepcoord;
			if (t0v.x == dist) {
				coord.x = next_coord.x;
				stepcoord = coord.x;
			} else if (t0v.y == dist) {
				coord.y = next_coord.y;
				stepcoord = coord.y;
			} else {
				coord.z = next_coord.z;
				stepcoord = coord.z;
			}
			
			#if 0
			// step up to highest changed octree parent cell
			mip = findLSB(stepcoord);
			#else
			// step up one level
			// (does not work if lower mips cannot be safely read without reading higher levels)
			// also breaks  mip >= uint(OCTREE_MIPS-1)  as world exit condition
			
			//mip += min(findLSB(stepcoord >> mip) - mip, 1u);
			mip += bitfieldExtract(stepcoord, int(mip), 1) ^ 1; // extract lowest bit of coord 
			#endif
			
			// round down coord to lower corner of (potential) parent cell
			coord &= ROUNDMASK << mip;
			
			//// exit when either stepped out of world or max ray dist reached
			//if (mip >= uint(OCTREE_MIPS-1) || dist >= max_dist)
			if (stepcoord >= WORLD_SIZE || dist >= max_dist)
				return false;
		}
	}
	
	// handle hit
}