VOXEL: add lod support

[mgerhardy]

https://0fps.net/2018/03/03/a-level-of-detail-method-for-blocky-voxels/

[mgerhardy]

#define MAX_LOD 4

/**
 * @brief computes the level of detail for a quad.
 * @return the coarsest level of detail where a quad is non-degenerate.
 *
 * @note If each quad is an integer unit square (i.e.
 * not the output from a greedy mesh), then we can take the smallest corner and compute the quad LOD in constant time
 * using a call to count-trailing zeroes. For general quads, the situation is a bit more involved. For a general
 * axis-aligned quad, we can compute the level of detail by taking the minimum level of detail along each axis. So it
 * then suffices to consider the case of one interval, where the level of detail can be computed by brute force using
 * the following algorithm
 */
static int quadLOD(const Mesh* mesh, const Quad& quad) {
	const int lo = 0; // TODO
	const int hi = 0;
	return SDL_MostSignificantBitIndex32(lo ^ hi);
}

/**
 * @brief To construct the POP buffer, we need to sort the quads and count how many quads are in each LOD.  This is an
 * ideal place to use counting sort, which we can do in-place in O(n) time
 *
 * @link https://0fps.net/2018/03/03/a-level-of-detail-method-for-blocky-voxels/
 */
static core::Array<int, MAX_LOD> buildPopBuffers(const Mesh* mesh, QuadListVector& vecListQuads) {
	core::Array<int, MAX_LOD> buckets {};
	buckets.fill(0);

	// count number of quads in each LOD
	for (const QuadList &list : vecListQuads) {
		for (const Quad& quad : list) {
			buckets[quadLOD(mesh, quad)] += 1;
		}
	}

	// compute prefix sum
	int t = 0;
	for (int i = 0; i < MAX_LOD; ++i) {
		const int b = buckets[i];
		buckets[i] = t;
		t += b;
	}
	// partition quads across each LOD
	for (int n = (int)vecListQuads.size() - 1; n >= 0; --n) {
		for (auto outerIter = vecListQuads[n].rbegin(); outerIter != vecListQuads[n].rend(); ++outerIter) {
			QuadList::reverse_iterator innerIter = outerIter;
			++innerIter;
			while (innerIter != vecListQuads[n].rend()) {
				const Quad& q = *quaditer;
				const int lod = quadLOD(mesh, q);
				const int ptr = buckets[lod];
				if (i < ptr) {
					break;
				}
				quads[i] = quads[ptr];
				quads[ptr] = q;
				buckets[lod] += 1;
			}
		}
	}
	// buckets now contains the prefixes for each LOD
	return buckets;
}

void meshify(Mesh* result, bool mergeQuads, QuadListVector& vecListQuads) {
	core_trace_scoped(GenerateMeshify);
	if (mergeQuads) {
		core_trace_scoped(MergeQuads);
		for (QuadList& listQuads : vecListQuads) {
			// Repeatedly call this function until it returns
			// false to indicate nothing more can be done.
			while (performQuadMerging(listQuads, result)) {
			}
		}
	}

	buildPopBuffers(result, vecListQuads);

	for (QuadList& listQuads : vecListQuads) {
		for (const Quad& quad : listQuads) {
			const IndexType i0 = quad.vertices[0];
			const IndexType i1 = quad.vertices[1];
			const IndexType i2 = quad.vertices[2];
			const IndexType i3 = quad.vertices[3];
			const VoxelVertex& v00 = result->getVertex(i3);
			const VoxelVertex& v01 = result->getVertex(i0);
			const VoxelVertex& v10 = result->getVertex(i2);
			const VoxelVertex& v11 = result->getVertex(i1);

			if (isQuadFlipped(v00, v01, v10, v11)) {
				result->addTriangle(i1, i2, i3);
				result->addTriangle(i1, i3, i0);
			} else {
				result->addTriangle(i0, i1, i2);
				result->addTriangle(i0, i2, i3);
			}
		}
	}
}