cpu_side_raytracer.cpp

struct ParametricOctreeTraverser {
	Octree& octree;
	
	// An Efficient Parametric Algorithm for Octree Traversal
	// J. Revelles, C.Ure ̃na, M.Lastra
	// http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=F6810427A1DC4136D615FBD178C1669C?doi=10.1.1.29.987&rep=rep1&type=pdf

	static constexpr int3 child_offset_lut[8] = {
		int3(0,0,0),
		int3(1,0,0),
		int3(0,1,0),
		int3(1,1,0),
		int3(0,0,1),
		int3(1,0,1),
		int3(0,1,1),
		int3(1,1,1),
	};
	struct OctreeNode {
		int level;
		int3 pos; // 3d index (scaled to octree level cell size so that one increment is always as step to the next cell on that level)
		float3 min;
		float3 mid;
		float3 max;

		OctreeNode get_child (int index, bool3 mask) {
			OctreeNode ret;

			ret.level = level - 1;
			ret.pos = pos * 2 + child_offset_lut[index];
			ret.min = select(mask, mid, min);
			ret.max = select(mask, max, mid);
			ret.mid = 0.5f * (ret.max + ret.min);

			return ret;
		}
	};

	int mirror_mask_int; // algo assumes ray.dir x,y,z >= 0, x,y,z < 0 cause the ray to be mirrored, to make all components positive, this mask is used to also mirror the octree nodes to make iteration work
	bool3 mirror_mask; // algo assumes ray.dir x,y,z >= 0, x,y,z < 0 cause the ray to be mirrored, to make all components positive, this mask is used to also mirror the octree nodes to make iteration work
	
	Ray ray;
	
	void traverse_octree (OctreeNode root, Ray ray) {
		this->ray = ray;
		mirror_mask_int = 0;
		mirror_mask = false;

		for (int i=0; i<3; ++i) {
			if (ray.dir[i] < 0) {
				ray.pos[i] = root.mid[i] * 2 - ray.pos[i];
				ray.dir[i] = -ray.dir[i];
				mirror_mask_int |= 1 << i;
				mirror_mask[i] = true;
			}
		}

		float3 rdir_inv = 1.0f / ray.dir;

		float3 t0 = (root.min - ray.pos) * rdir_inv;
		float3 t1 = (root.max - ray.pos) * rdir_inv;

		if (max_component(t0) < min_component(t1))
			traverse_subtree(root, t0, t1);

		debug_graphics->push_point(t0.x * ray.dir + ray.pos, 0.2f, lrgba(1,0,0,1));
		debug_graphics->push_point(t0.y * ray.dir + ray.pos, 0.2f, lrgba(0,1,0,1));
		debug_graphics->push_point(t0.z * ray.dir + ray.pos, 0.2f, lrgba(0,0,1,1));

		debug_graphics->push_point(t1.x * ray.dir + ray.pos, 0.2f, lrgba(1,0,0,1));
		debug_graphics->push_point(t1.y * ray.dir + ray.pos, 0.2f, lrgba(0,1,0,1));
		debug_graphics->push_point(t1.z * ray.dir + ray.pos, 0.2f, lrgba(0,0,1,1));
	}

	int first_node (float3 t0, float3 tm) {
		int max_comp;
		max_component(t0, &max_comp);

		static constexpr int lut_a[] = { 1, 0, 0 };
		static constexpr int lut_b[] = { 2, 2, 1 };

		int a = lut_a[max_comp];
		int b = lut_b[max_comp];

		float cond = t0[max_comp];

		int ret = 0;
		ret |= (tm[a] < cond) ? (1 << a) : 0;
		ret |= (tm[b] < cond) ? (1 << b) : 0;
		return ret;
	}
	int next_node (float3 t1, const int indices[3]) {
		int min_comp;
		min_component(t1, &min_comp);

		return indices[min_comp];
	}

	static constexpr int node_seq_lut[8][3] = {
		{ 1, 2, 4 }, // 001 010 100
		{ 8, 3, 5 }, //   - 011 101
		{ 3, 8, 6 }, // 011   - 110
		{ 8, 8, 7 }, //   -   - 111
		{ 5, 6, 8 }, // 101 110   -
		{ 8, 7, 8 }, //   - 111   -
		{ 7, 8, 8 }, // 111   -   -
		{ 8, 8, 8 }, //   -   -   -
	};

	bool traverse_subtree (OctreeNode node, float3 t0, float3 t1) {

		if (any(t1 < 0))
			return false;

		bool stop;
		bool decend = eval_octree_cell(node, t0, t1, &stop);
		if (decend) {
			assert(!stop);

			float3 tm = select(ray.dir != 0, 0.5f * (t0 + t1), select(ray.pos < node.mid, float3(+INF), float3(-INF)));

			int cur_node = first_node(t0, tm);

			do {
				bool3 mask = bool3(cur_node & 1, (cur_node >> 1) & 1, (cur_node >> 2) & 1);

				stop = traverse_subtree(node.get_child(cur_node ^ mirror_mask_int, mask != mirror_mask), select(mask, tm, t0), select(mask, t1, tm));
				if (stop)
					return true;

				cur_node = next_node(select(mask, t1, tm), node_seq_lut[cur_node]);
			} while (cur_node < 8);
		}

		return stop;
	}

	bool eval_octree_cell (OctreeNode node, float3 t0, float3 t1, bool* stop_traversal) {
		float3 size = node.max - node.min;
		{
			int voxel_count = CHUNK_DIM_X >> node.level;
			int voxel_size = 1 << node.level;

			debug_graphics->push_wire_cube((float3)node.pos*(float)voxel_size + (float)voxel_size/2, (float)voxel_size, cols[node.level]);

			auto get = [&] (int3 xyz) {
				return octree.octree_levels[node.level][xyz.z * voxel_count*voxel_count + xyz.y * voxel_count + xyz.x];
			};

			auto b = get(node.pos);
			*stop_traversal = b != B_AIR;
			return b == B_NULL; // true == need to drill further down into octree
		}
	}
};