<commit_before>#include "accelerator/qbvh.h"

//#pragma optimize( "", off)

namespace aten
{
	void qbvh::build(
		hitable** list,
		uint32_t num)
	{
		m_bvh.build(list, num);

		setBoundingBox(m_bvh.getBoundingbox());

		// Gather local-world matrix.
		transformable::gatherAllTransformMatrixAndSetMtxIdx(m_mtxs);

		std::vector<accelerator*> listBvh;
		std::map<hitable*, std::vector<accelerator*>> nestedBvhMap;

		std::vector<std::vector<BvhNode>> listBvhNode;

		// Register to linear list to traverse bvhnode easily.
		auto root = m_bvh.getRoot();
		listBvhNode.push_back(std::vector<BvhNode>());
		registerBvhNodeToLinearList(root, nullptr, nullptr, aten::mat4::Identity, listBvhNode[0], listBvh, nestedBvhMap);

		for (int i = 0; i < listBvh.size(); i++) {
			// TODO
			auto bvh = (aten::bvh*)listBvh[i];

			root = bvh->getRoot();

			hitable* parent = nullptr;

			// TODO
			// Find parent.
			for (auto it : nestedBvhMap) {
				auto& list = it.second;
				auto found = std::find(list.begin(), list.end(), bvh);

				if (found != list.end()) {
					// Found nested bvh.
					parent = it.first;
					break;
				}
			}

			listBvhNode.push_back(std::vector<BvhNode>());
			std::vector<accelerator*> dummy;

			registerBvhNodeToLinearList(root, nullptr, parent, aten::mat4::Identity, listBvhNode[i + 1], dummy, nestedBvhMap);
			AT_ASSERT(dummy.empty());
		}

		m_listQbvhNode.resize(listBvhNode.size());

		// Convert to QBVH.
		for (int i = 0; i < listBvhNode.size(); i++) {
			bool isPrimitiveLeafBvh = (i > 0);

			auto numNodes = convertFromBvh(
				isPrimitiveLeafBvh,
				listBvhNode[i],
				m_listQbvhNode[i]);

			// TODO
			// listQbvhNodȅk.
		}
	}

	void qbvh::registerBvhNodeToLinearList(
		bvhnode* root,
		bvhnode* parentNode,
		hitable* nestParent,
		const aten::mat4& mtxL2W,
		std::vector<BvhNode>& listBvhNode,
		std::vector<accelerator*>& listBvh,
		std::map<hitable*, std::vector<accelerator*>>& nestedBvhMap)
	{
		bvh::registerBvhNodeToLinearList<BvhNode>(
			root,
			parentNode,
			nestParent,
			mtxL2W,
			listBvhNode,
			listBvh,
			nestedBvhMap,
			[this](std::vector<BvhNode>& list, bvhnode* node, hitable* obj, const aten::mat4& mtx)
		{
			list.push_back(BvhNode(node, obj, mtx));
		},
			[this](bvhnode* node)
		{
			if (node->isLeaf()) {
				node->setExternalId(m_exid);
				m_exid++;
			}
		});
	}

	uint32_t qbvh::convertFromBvh(
		bool isPrimitiveLeaf,
		std::vector<BvhNode>& listBvhNode,
		std::vector<QbvhNode>& listQbvhNode)
	{
		struct QbvhStackEntry {
			uint32_t qbvhNodeIdx;
			uint32_t bvhNodeIdx;

			QbvhStackEntry(uint32_t qbvh, uint32_t bvh)
				: qbvhNodeIdx(qbvh), bvhNodeIdx(bvh)
			{}
			QbvhStackEntry() {}
		};

		listQbvhNode.resize(listBvhNode.size());

		QbvhStackEntry stack[256];
		stack[0] = QbvhStackEntry(0, 0);

		int stackPos = 1;
		uint32_t numNodes = 1;

		int children[4];

		while (stackPos > 0) {
			auto top = stack[--stackPos];

			auto& qbvhNode = listQbvhNode[top.qbvhNodeIdx];
			const auto& bvhNode = listBvhNode[top.bvhNodeIdx];

			int numChildren = getChildren(listBvhNode, top.bvhNodeIdx, children);

			if (numChildren == 0) {
				// No children, so it is a leaf.
				setQbvhNodeLeafParams(isPrimitiveLeaf, bvhNode, qbvhNode);
				continue;
			}

			// Fill node.
			fillQbvhNode(
				qbvhNode,
				listBvhNode,
				children,
				numChildren);

			qbvhNode.children[0] = (children[0] >= 0 ? numNodes + 0 : -1);
			qbvhNode.children[1] = (children[1] >= 0 ? numNodes + 1 : -1);
			qbvhNode.children[2] = (children[2] >= 0 ? numNodes + 2 : -1);
			qbvhNode.children[3] = (children[3] >= 0 ? numNodes + 3 : -1);

			qbvhNode.numChildren = numChildren;

			// push all children to the stack
			for (int i = 0; i < numChildren; i++) {
				stack[stackPos++] = QbvhStackEntry(numNodes, children[i]);
				++numNodes;
			}
		}

		return numNodes;
	}

	void qbvh::setQbvhNodeLeafParams(
		bool isPrimitiveLeaf,
		const BvhNode& bvhNode,
		QbvhNode& qbvhNode)
	{
		auto node = bvhNode.node;
		auto nestParent = bvhNode.nestParent;

		auto bbox = node->getBoundingbox();
		bbox = aten::aabb::transform(bbox, bvhNode.mtxL2W);

#if 0<commit_msg>Optimize memory usage in building qbvh.<commit_after>#include "accelerator/qbvh.h"

//#pragma optimize( "", off)

namespace aten
{
	void qbvh::build(
		hitable** list,
		uint32_t num)
	{
		m_bvh.build(list, num);

		setBoundingBox(m_bvh.getBoundingbox());

		// Gather local-world matrix.
		transformable::gatherAllTransformMatrixAndSetMtxIdx(m_mtxs);

		std::vector<accelerator*> listBvh;
		std::map<hitable*, std::vector<accelerator*>> nestedBvhMap;

		std::vector<std::vector<BvhNode>> listBvhNode;

		// Register to linear list to traverse bvhnode easily.
		auto root = m_bvh.getRoot();
		listBvhNode.push_back(std::vector<BvhNode>());
		registerBvhNodeToLinearList(root, nullptr, nullptr, aten::mat4::Identity, listBvhNode[0], listBvh, nestedBvhMap);

		for (int i = 0; i < listBvh.size(); i++) {
			// TODO
			auto bvh = (aten::bvh*)listBvh[i];

			root = bvh->getRoot();

			hitable* parent = nullptr;

			// TODO
			// Find parent.
			for (auto it : nestedBvhMap) {
				auto& list = it.second;
				auto found = std::find(list.begin(), list.end(), bvh);

				if (found != list.end()) {
					// Found nested bvh.
					parent = it.first;
					break;
				}
			}

			listBvhNode.push_back(std::vector<BvhNode>());
			std::vector<accelerator*> dummy;

			registerBvhNodeToLinearList(root, nullptr, parent, aten::mat4::Identity, listBvhNode[i + 1], dummy, nestedBvhMap);
			AT_ASSERT(dummy.empty());
		}

		m_listQbvhNode.resize(listBvhNode.size());

		// Convert to QBVH.
		for (int i = 0; i < listBvhNode.size(); i++) {
			bool isPrimitiveLeafBvh = (i > 0);

			auto numNodes = convertFromBvh(
				isPrimitiveLeafBvh,
				listBvhNode[i],
				m_listQbvhNode[i]);
		}
	}

	void qbvh::registerBvhNodeToLinearList(
		bvhnode* root,
		bvhnode* parentNode,
		hitable* nestParent,
		const aten::mat4& mtxL2W,
		std::vector<BvhNode>& listBvhNode,
		std::vector<accelerator*>& listBvh,
		std::map<hitable*, std::vector<accelerator*>>& nestedBvhMap)
	{
		bvh::registerBvhNodeToLinearList<BvhNode>(
			root,
			parentNode,
			nestParent,
			mtxL2W,
			listBvhNode,
			listBvh,
			nestedBvhMap,
			[this](std::vector<BvhNode>& list, bvhnode* node, hitable* obj, const aten::mat4& mtx)
		{
			list.push_back(BvhNode(node, obj, mtx));
		},
			[this](bvhnode* node)
		{
			if (node->isLeaf()) {
				node->setExternalId(m_exid);
				m_exid++;
			}
		});
	}

	uint32_t qbvh::convertFromBvh(
		bool isPrimitiveLeaf,
		std::vector<BvhNode>& listBvhNode,
		std::vector<QbvhNode>& listQbvhNode)
	{
		struct QbvhStackEntry {
			uint32_t qbvhNodeIdx;
			uint32_t bvhNodeIdx;

			QbvhStackEntry(uint32_t qbvh, uint32_t bvh)
				: qbvhNodeIdx(qbvh), bvhNodeIdx(bvh)
			{}
			QbvhStackEntry() {}
		};

		listQbvhNode.reserve(listBvhNode.size());
		listQbvhNode.push_back(QbvhNode());

		QbvhStackEntry stack[256];
		stack[0] = QbvhStackEntry(0, 0);

		int stackPos = 1;
		uint32_t numNodes = 1;

		int children[4];

		while (stackPos > 0) {
			auto top = stack[--stackPos];

			auto& qbvhNode = listQbvhNode[top.qbvhNodeIdx];
			const auto& bvhNode = listBvhNode[top.bvhNodeIdx];

			int numChildren = getChildren(listBvhNode, top.bvhNodeIdx, children);

			if (numChildren == 0) {
				// No children, so it is a leaf.
				setQbvhNodeLeafParams(isPrimitiveLeaf, bvhNode, qbvhNode);
				continue;
			}

			// Fill node.
			fillQbvhNode(
				qbvhNode,
				listBvhNode,
				children,
				numChildren);

			qbvhNode.children[0] = (children[0] >= 0 ? numNodes + 0 : -1);
			qbvhNode.children[1] = (children[1] >= 0 ? numNodes + 1 : -1);
			qbvhNode.children[2] = (children[2] >= 0 ? numNodes + 2 : -1);
			qbvhNode.children[3] = (children[3] >= 0 ? numNodes + 3 : -1);

			qbvhNode.numChildren = numChildren;

			// push all children to the stack
			for (int i = 0; i < numChildren; i++) {
				stack[stackPos++] = QbvhStackEntry(numNodes, children[i]);

				listQbvhNode.push_back(QbvhNode());
				++numNodes;
			}
		}

		return numNodes;
	}

	void qbvh::setQbvhNodeLeafParams(
		bool isPrimitiveLeaf,
		const BvhNode& bvhNode,
		QbvhNode& qbvhNode)
	{
		auto node = bvhNode.node;
		auto nestParent = bvhNode.nestParent;

		auto bbox = node->getBoundingbox();
		bbox = aten::aabb::transform(bbox, bvhNode.mtxL2W);

#if 0
{'fraction_non_alphanumeric': 0.14761790182868142, 'fraction_numerical': 0.014196342637151107, 'mean_word_length': 3.761168384879725, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 55, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7227237', 'n_tokens_mistral': 4081, 'n_tokens_neox': 3294, 'n_words': 618}