Untitled

#include "Chunk.h"

#include <vector>
#include <intrin.h>

#include "Engine.h"
#include "Config.h"

inline const int getBitPos(uint64_t& x) {
	unsigned long index;
	_BitScanForward64(&index, x);
	return (int) index;
}

inline const int getAxisIndex(int axis, int a, int b, int c) {
	if (axis == 0) return a * CS_P2 + c * CS_P + b;
	if (axis == 1) return c * CS_P2 + a * CS_P + b;
	return a * CS_P2 + b * CS_P + c;
}

inline const uint32_t getQuad(uint8_t x, uint8_t y, uint8_t z, uint8_t w, uint8_t l) {
	return x | y << 6 | z << 12 | w << 18 | l << 24;
}

inline void updateBounds(uint8_t* bounds, uint8_t x, uint8_t y, uint8_t z, uint8_t xW, uint8_t yW, uint8_t zW) {
	bounds[0] = x < bounds[0] ? x : bounds[0];
	bounds[3] = x + xW > bounds[3] ? x + xW : bounds[3];

	bounds[2] = y < bounds[2] ? y : bounds[2];
	bounds[5] = y + yW > bounds[5] ? y + yW : bounds[5];

	bounds[1] = z < bounds[1] ? z : bounds[1];
	bounds[4] = z + zW > bounds[4] ? z + zW : bounds[4];
}

struct TranslucentQuad {
	uint32_t data1;
	uint32_t data2;

	TranslucentQuad(uint32_t data1, uint32_t data2) : data1(data1), data2(data2) {}
};

struct MeshData {
	std::vector<uint32_t> allQuadData;
	int opaqueFaceSize[6] { 0 };

	std::vector<TranslucentQuad> translucentData;
	uint64_t translucentSplits[3] { 0 };
	int visibleTranslucentQuads = 0;

	std::vector<uint32_t> paletteData;

	uint8_t bounds[6] { CS, CS, CS, 0, 0, 0 };
};

inline uint8_t getQuadDepth(uint32_t data, glm::ivec3 cameraPos) {
	uint8_t axis = (data >> 9) & 3;
	uint8_t face = (data >> 8) & 1;

	int depths[3] {
		((data >> 11) & 63) - cameraPos.x,
		((data >> 23) & 63) - cameraPos.z,
		((data >> 17) & 63) - cameraPos.y
	};

	uint8_t totalDepth = abs(depths[0]) + abs(depths[1]) + abs(depths[2]) + 1;
	if (depths[axis] * ((1 - face) * 2 - 1) < 0) totalDepth = 0;

	return totalDepth;
}

void sortTranslucentQuads(MeshData& mesh, glm::ivec3 cameraPos) {
	int depthCounts[191] { 0 };

	for (int i = 0; i < mesh.translucentData.size(); i++) {
		uint8_t depth = getQuadDepth(mesh.translucentData[i].data2, cameraPos);
		depthCounts[depth]++;
	}

	for (int i = 189; i >= 0; i--) {
		depthCounts[i] += depthCounts[i + 1];
	}
	mesh.visibleTranslucentQuads = depthCounts[1];

	int baseIndex = mesh.allQuadData.size();
	mesh.allQuadData.resize(mesh.allQuadData.size() + mesh.translucentData.size() * 2);

	for (int i = 0; i < mesh.translucentData.size(); i++) {
		uint8_t depth = getQuadDepth(mesh.translucentData[i].data2, cameraPos);
		int relIndex = --depthCounts[depth];

		mesh.allQuadData[baseIndex + relIndex * 2] = mesh.translucentData[i].data1;
		mesh.allQuadData[baseIndex + relIndex * 2 + 1] = mesh.translucentData[i].data2;
	}
}

MeshData doMeshing(VoxelData* vData) {
	MeshData mesh;
	uint8_t paletteRedirect[256] { 0 };

	constexpr uint64_t P_MASK = ~(1ull << 63 | 1);
	for (int axis = 0; axis < 3; axis++) {
		for (int a = 0; a < CS; a++) {
			for (int b = 0; b < CS; b++) {
				uint64_t currOpaqueAxis = vData->opaqueAxis[(b + 1) + (a + 1) * CS_P + axis * CS_P2];

				vData->rowFaceMasks[b + a * CS + (axis * 2) * CS_2] = (currOpaqueAxis & ~vData->opaqueAxis[(b + 1) + a * CS_P + axis * CS_P2] & P_MASK) >> 1;
				uint64_t prevTranslucentRow = (vData->translucentAxis[(b + 1) + (a + 1) * CS_P + axis * CS_P2] & P_MASK) >> 1;
				while (prevTranslucentRow) {
					int c = getBitPos(prevTranslucentRow);
					prevTranslucentRow &= ~(1ULL << c);

					uint8_t type = vData->typeData[getAxisIndex(axis, b + 1, c + 1, a + 1)];
					bool typeIsOpaque = type == 0 || ((vData->palette.data[type] >> 24) & 0xFF) == 0xFF;
					if (typeIsOpaque) continue;

					uint8_t prevType = vData->typeData[getAxisIndex(axis, b + 1, c + 1, a)];
					bool prevTypeIsOpaque = ((vData->palette.data[prevType] >> 24) & 0xFF) == 0xFF;
					if (prevTypeIsOpaque) continue;

					if (type == prevType) continue;

					vData->rowFaceMasks[b + a * CS + (axis * 2) * CS_2] |= 1ull << c;
					mesh.translucentSplits[axis] |= 1ull << a;
				}

				vData->rowFaceMasks[b + a * CS + (axis * 2 + 1) * CS_2] = (currOpaqueAxis & ~vData->opaqueAxis[(b + 1) + (a + 2) * CS_P + axis * CS_P2] & P_MASK) >> 1;
				uint64_t currTranslucentRow = (vData->translucentAxis[(b + 1) + (a + 2) * CS_P + axis * CS_P2] & P_MASK) >> 1;
				while (currTranslucentRow) {
					int c = getBitPos(currTranslucentRow);
					currTranslucentRow &= ~(1ULL << c);

					uint8_t type = vData->typeData[getAxisIndex(axis, b + 1, c + 1, a + 1)];
					bool typeIsOpaque = type == 0 || ((vData->palette.data[type] >> 24) & 0xFF) == 0xFF;
					if (typeIsOpaque) continue;

					uint8_t nextType = vData->typeData[getAxisIndex(axis, b + 1, c + 1, a + 2)];
					bool nextTypeIsOpaque = ((vData->palette.data[nextType] >> 24) & 0xFF) == 0xFF;
					if (nextTypeIsOpaque) continue;

					if (type == nextType) continue;

					vData->rowFaceMasks[b + a * CS + (axis * 2 + 1) * CS_2] |= 1ull << c;
					mesh.translucentSplits[axis] |= 1ull << (a + 1);
				}
			}
		}
	}

	uint8_t forwardMerged[CS];
	memset(forwardMerged, 1, CS);
	for (int face = 0; face < 6; face++) {
		int axis = face / 2;

		mesh.opaqueFaceSize[face] = mesh.allQuadData.size();
		int opaqueFaceCount = 0;

		uint64_t translucentForward = mesh.translucentSplits[~axis & 1];
		uint64_t translucentRight = mesh.translucentSplits[~axis & 2];
		for (int layer = 0; layer < CS; layer++) {
			int bitsLocation = layer * CS + face * CS_2;
			for (int forward = 0; forward < CS; forward++) {
				uint64_t bitsHere = vData->rowFaceMasks[forward + bitsLocation];
				uint64_t bitsNext = forward + 1 < CS ? vData->rowFaceMasks[(forward + 1) + bitsLocation] : 0;

				uint8_t rightMerged = 1;
				while (bitsHere) {
					unsigned long bitPos;
					_BitScanForward64(&bitPos, bitsHere);

					uint8_t type = vData->typeData[getAxisIndex(axis, forward + 1, bitPos + 1, layer + 1)];
					bool isOpaque = ((vData->palette.data[type] >> 24) & 0xFF) == 0xFF;

					if ((bitsNext >> bitPos & 1) && !(!isOpaque && (translucentForward >> (forward + 1) & 1)) && type == vData->typeData[getAxisIndex(axis, forward + 2, bitPos + 1, layer + 1)]) {
						forwardMerged[bitPos]++;
						bitsHere &= ~(1ull << bitPos);
						continue;
					}

					for (int right = bitPos + 1; right < CS; right++) {
						if (!(bitsHere >> right & 1) || forwardMerged[bitPos] != forwardMerged[right] || (!isOpaque && (translucentRight >> right & 1)) || type != vData->typeData[getAxisIndex(axis, forward + 1, right + 1, layer + 1)]) break;
						forwardMerged[right] = 1;
						rightMerged++;
					}
					bitsHere &= ~((1ull << (bitPos + rightMerged)) - 1);

					uint8_t meshFront = forward - forwardMerged[bitPos] + 1;
					uint8_t meshLeft = bitPos;
					uint8_t meshUp = layer + (face & 1);

					uint8_t meshWidth = rightMerged;
					uint8_t meshLength = forwardMerged[bitPos];

					forwardMerged[bitPos] = 1;
					rightMerged = 1;

					uint32_t quad;
					switch (face) {
					case 0:
					case 1:
						quad = getQuad(meshUp, meshLeft, meshFront, meshWidth, meshLength);
						updateBounds(mesh.bounds, meshUp, meshLeft, meshFront, 0, meshWidth, meshLength);
						break;
					case 2:
					case 3:
						quad = getQuad(meshFront, meshLeft, meshUp, meshLength, meshWidth);
						updateBounds(mesh.bounds, meshFront, meshLeft, meshUp, meshLength, meshWidth, 0);
						break;
					case 4:
					case 5:
						quad = getQuad(meshLeft, meshUp, meshFront, meshLength, meshWidth);
						updateBounds(mesh.bounds, meshLeft, meshUp, meshFront, meshWidth, 0, meshLength);
						break;
					}

					if (paletteRedirect[type] == 0) {
						mesh.paletteData.push_back(vData->palette.data[type]);
						paletteRedirect[type] = mesh.paletteData.size();
					}
					type = paletteRedirect[type] - 1;

					if (isOpaque) {
						int sharedIndex = (opaqueFaceCount / 4) * 5 + mesh.opaqueFaceSize[face];
						if (mesh.allQuadData.size() <= sharedIndex) mesh.allQuadData.push_back(0);

						mesh.allQuadData[sharedIndex] |= type << ((opaqueFaceCount & 3) * 8);
						mesh.allQuadData.push_back(quad);
						opaqueFaceCount++;
					} else {
						uint8_t quadX = (face < 2 ? meshUp : (face < 4 ? meshFront : meshLeft)) + (face != 0);
						uint8_t quadZ = ((face >= 2 && face < 4) ? meshUp : meshFront) + (face != 2);
						uint8_t quadY = (face < 4 ? meshLeft : meshUp) + (face != 4);

						uint8_t quadMappedX = __popcnt64(mesh.translucentSplits[0] & ((1ULL << quadX) - 1));
						uint8_t quadMappedZ = __popcnt64(mesh.translucentSplits[1] & ((1ULL << quadZ) - 1));
						uint8_t quadMappedY = __popcnt64(mesh.translucentSplits[2] & ((1ULL << quadY) - 1));

						mesh.translucentData.emplace_back(quad, quadMappedZ << 23 | quadMappedY << 17 | quadMappedX << 11 | face << 8 | type);
					}
				}
			}
		}

		mesh.opaqueFaceSize[face] = mesh.allQuadData.size() - mesh.opaqueFaceSize[face];
	}

	mesh.bounds[3] -= mesh.bounds[0];
	mesh.bounds[4] -= mesh.bounds[1];
	mesh.bounds[5] -= mesh.bounds[2];

	return mesh;
}

void uploadChunkRenderData(GenerationChunk* chunk, MeshData& mesh, glm::ivec3& prevCamPosition) {
	chunk->renderMemID = gEngine.graphics.chunkPool.allocate();
	uint32_t* chunkRenderMem = gEngine.graphics.chunkPool.getIDAddress(chunk->renderMemID);

	chunkRenderMem[0] = chunk->getX() * CS;
	chunkRenderMem[1] = chunk->getY() * CS;
	chunkRenderMem[2] = chunk->getZ() * CS;
	chunkRenderMem[3] = chunk->getLayer();

	chunkRenderMem[4] = chunk->bounds[0] | chunk->bounds[1] << 6 | chunk->bounds[2] << 12;
	chunkRenderMem[5] = chunk->bounds[3] | chunk->bounds[5] << 6 | chunk->bounds[4] << 12;

	chunkRenderMem[6] = -1;

	chunkRenderMem[7] = mesh.opaqueFaceSize[0] | mesh.opaqueFaceSize[1] << 16;
	chunkRenderMem[8] = mesh.opaqueFaceSize[2] | mesh.opaqueFaceSize[3] << 16;
	chunkRenderMem[9] = mesh.opaqueFaceSize[4] | mesh.opaqueFaceSize[5] << 16;

	chunkRenderMem[10] = mesh.allQuadData.size() - mesh.translucentData.size() * 2 - mesh.paletteData.size();
	chunkRenderMem[11] = mesh.visibleTranslucentQuads;
	chunkRenderMem[12] = mesh.translucentData.size();

	chunkRenderMem[13] = mesh.translucentSplits[0];
	chunkRenderMem[14] = mesh.translucentSplits[0] >> 32;
	chunkRenderMem[15] = mesh.translucentSplits[1];
	chunkRenderMem[16] = mesh.translucentSplits[1] >> 32;
	chunkRenderMem[17] = mesh.translucentSplits[2];
	chunkRenderMem[18] = mesh.translucentSplits[2] >> 32;

	chunkRenderMem[19] = prevCamPosition.x | (prevCamPosition.y << 6) | (prevCamPosition.z << 12);

	chunkRenderMem[20] = mesh.allQuadData.size() - mesh.paletteData.size();
}

bool GenerationChunk::setupRenderData() {
	MeshData mesh = doMeshing(vData);

	glm::ivec3 prevCamPosition = glm::ivec3(0, 0, 0);
	if (mesh.translucentData.size() > 0) {
		glm::ivec3 cameraPos = getBoundPos(gEngine.camera.getAtomicPos());

		prevCamPosition.x = __popcnt64(mesh.translucentSplits[0] & ((1ULL << (cameraPos.x + 1)) - 1));
		prevCamPosition.z = __popcnt64(mesh.translucentSplits[1] & ((1ULL << (cameraPos.z + 1)) - 1));
		prevCamPosition.y = __popcnt64(mesh.translucentSplits[2] & ((1ULL << (cameraPos.y + 1)) - 1));

		sortTranslucentQuads(mesh, prevCamPosition);
	}

	if (mesh.allQuadData.size() == 0) return false;

	mesh.allQuadData.insert(mesh.allQuadData.end(), mesh.paletteData.begin(), mesh.paletteData.end());

	for (int face = 0; face < 6; face++) {
		bounds[face] = mesh.bounds[face];
		renderFlags |= ((mesh.opaqueFaceSize[face] > 0) << face);
	}

	renderFlags |= (mesh.translucentData.size() > 0) << 6;
	quadCount = mesh.allQuadData.size();

	uploadChunkRenderData(this, mesh, prevCamPosition);

	gEngine.graphics.quadPool.allocate(renderMemID, mesh.allQuadData.data(), mesh.allQuadData.size());

	return true;
}