You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
247 lines
10 KiB
247 lines
10 KiB
#pragma once
|
|
#include <vector>
|
|
#include <cassert>
|
|
#include <iostream>
|
|
|
|
namespace algoim::organizer
|
|
{
|
|
const int NODE_IN_OUT_UNKNOWN = 0;
|
|
const int NODE_IN = 1;
|
|
const int NODE_OUT = 2;
|
|
|
|
const int OP_UNION = 0;
|
|
const int OP_INTERSECTION = 1;
|
|
const int OP_DIFFERENCE = 2;
|
|
|
|
// bitfield
|
|
struct Blob {
|
|
unsigned int isPrimitive : 1; // 1 for leaf
|
|
unsigned int nodeOp : 2; // 0 for union, 1 for intersection, 2 for difference
|
|
// unsigned int ignoreMod : 2; // 目前用不到
|
|
unsigned int inOut : 2; // 0 for unknown, 1 for in, 2 for out
|
|
unsigned int oneChildInOut : 2; // 0 for unknown, 1 for in, 2 for out
|
|
unsigned int isLeft : 1;
|
|
unsigned int ancestor : 24;
|
|
};
|
|
|
|
bool isPrimitive(Blob b) { return b.isPrimitive == 1; }
|
|
|
|
unsigned int type(Blob b) { return 0; }
|
|
|
|
bool isLeft(Blob b) { return b.isLeft == 1; }
|
|
|
|
class BlobTree
|
|
{
|
|
public:
|
|
std::vector<Blob> structure;
|
|
|
|
std::vector<int> primitiveNodeIdx; // 由primitive数组下标指向node中对应leaf的下标
|
|
|
|
BlobTree(const BlobTree& other)
|
|
{
|
|
structure = other.structure;
|
|
primitiveNodeIdx = other.primitiveNodeIdx;
|
|
}
|
|
|
|
BlobTree& operator=(const BlobTree& other)
|
|
{
|
|
if (this != &other) {
|
|
structure = other.structure;
|
|
primitiveNodeIdx = other.primitiveNodeIdx;
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
BlobTree() {}
|
|
|
|
void clear()
|
|
{
|
|
structure.clear();
|
|
primitiveNodeIdx.clear();
|
|
}
|
|
};
|
|
|
|
void propagate(BlobTree& tree, unsigned int nodeIdx, bool in)
|
|
{
|
|
const std::size_t rootIdx = tree.structure.size() - 1;
|
|
auto& node = tree.structure[nodeIdx];
|
|
if (nodeIdx == 4) {
|
|
int aaa = 1;
|
|
int bbb = 1;
|
|
}
|
|
if (node.inOut != NODE_IN_OUT_UNKNOWN) {
|
|
int aaa = 1;
|
|
int bb = 1;
|
|
}
|
|
// assert(node.inOut == NODE_IN_OUT_UNKNOWN);
|
|
node.inOut = in ? NODE_IN : NODE_OUT;
|
|
for (unsigned int nowIdx = nodeIdx; nowIdx != rootIdx;) {
|
|
const auto& nowNode = tree.structure[nowIdx];
|
|
unsigned int nextIdx = isLeft(nowNode) ? nowIdx + nowNode.ancestor : nowIdx + 1;
|
|
auto& nextNode = tree.structure[nextIdx]; // father
|
|
if (nextNode.inOut != 0) { return; }
|
|
if (nowNode.inOut == NODE_OUT) {
|
|
if (nextNode.nodeOp == OP_INTERSECTION) {
|
|
nextNode.inOut = NODE_OUT;
|
|
} else if (nextNode.nodeOp == OP_DIFFERENCE && isLeft(nowNode)) {
|
|
nextNode.inOut = NODE_OUT;
|
|
} else if (nextNode.oneChildInOut == NODE_IN) {
|
|
// 两种情况，Union: in, Difference: NowNode一定是right，in-out，还是in
|
|
nextNode.inOut = NODE_IN;
|
|
} else if (nextNode.oneChildInOut == NODE_OUT) {
|
|
// 两种情况，Union: out, Difference: out-out, 还是out
|
|
nextNode.inOut = NODE_OUT;
|
|
} else {
|
|
nextNode.oneChildInOut = NODE_OUT;
|
|
return;
|
|
}
|
|
} else if (nowNode.inOut == NODE_IN) {
|
|
if (nextNode.nodeOp == OP_UNION) {
|
|
nextNode.inOut = NODE_IN;
|
|
} else if (nextNode.nodeOp == OP_DIFFERENCE && !isLeft(nowNode)) {
|
|
// difference and right
|
|
nextNode.inOut = NODE_OUT;
|
|
} else if (nextNode.oneChildInOut == NODE_IN) {
|
|
// 两种情况，Intersection: in, Difference: in-in，out
|
|
nextNode.inOut = nextNode.nodeOp == OP_INTERSECTION ? NODE_IN : NODE_OUT;
|
|
} else if (nextNode.oneChildInOut == NODE_OUT) {
|
|
// 两种情况，Intersection: out, Difference: NowNode一定是left，in-out，in
|
|
nextNode.inOut = nextNode.nodeOp == OP_INTERSECTION ? NODE_OUT : NODE_IN;
|
|
} else {
|
|
nextNode.oneChildInOut = NODE_IN;
|
|
return;
|
|
}
|
|
}
|
|
nowIdx = nextIdx;
|
|
}
|
|
return;
|
|
}
|
|
|
|
// TODO: std::vector<char> 浪费内存，应实现动态大小的bitset
|
|
/**
|
|
* relatedPrimitives 是当次traversal需要care的primitives的索引，例如OcTree子问题中关联的Primitive
|
|
*/
|
|
int traverse(BlobTree& tree, const std::vector<int>& relatedPrimitives, const std::vector<char>& primitiveInout)
|
|
{
|
|
assert(relatedPrimitives.size() == primitiveInout.size());
|
|
for (int i = 0; i < relatedPrimitives.size(); ++i) {
|
|
propagate(tree, tree.primitiveNodeIdx[relatedPrimitives[i]], static_cast<bool>(primitiveInout[i]));
|
|
if (tree.structure.back().inOut != NODE_IN_OUT_UNKNOWN) { return tree.structure.back().inOut; }
|
|
}
|
|
return NODE_IN_OUT_UNKNOWN;
|
|
}
|
|
|
|
int traverse(BlobTree& tree, const int relatedPrimitive, const bool in)
|
|
{
|
|
int bbb = 1;
|
|
propagate(tree, tree.primitiveNodeIdx[relatedPrimitive], in);
|
|
if (tree.structure[tree.primitiveNodeIdx[relatedPrimitive]].inOut == NODE_IN_OUT_UNKNOWN) {
|
|
int aaa = 1;
|
|
int bbb = 1;
|
|
}
|
|
return tree.structure.back().inOut;
|
|
}
|
|
|
|
// void mergeSubtree2Leaf(BlobTree& blobTree, const std::vector<VisiblePrimitiveRep>& visiblePrimitiveReps)
|
|
// {
|
|
// std::vector<MinimalPrimitiveRep> minimalReps;
|
|
// std::vector<int> realLeafIndices;
|
|
// for (int i = 0; i < blobTree.structure.size(); ++i) {
|
|
// int oldAncestor = blobTree.structure[i].ancestor;
|
|
// for (int j = visiblePrimitiveReps.size() - 1; blobTree.primitiveNodeIdx[j] > i; --j) {
|
|
// if (blobTree.structure[i].isLeft && oldAncestor + i > blobTree.primitiveNodeIdx[j]) {
|
|
// blobTree.structure[i].ancestor += std::max(int(visiblePrimitiveReps[j].subBlobTree.structure.size()) - 1, 0);
|
|
// }
|
|
// }
|
|
// }
|
|
// for (int i = 0; i < visiblePrimitiveReps.size(); ++i) {
|
|
// int originLeafIdx = blobTree.primitiveNodeIdx[i];
|
|
// int subBlobTreeSize = visiblePrimitiveReps[i].subBlobTree.structure.size();
|
|
// if (visiblePrimitiveReps[i].tensors.size() != 1) {
|
|
// for (int j = i + 1; j < visiblePrimitiveReps.size(); ++j) {
|
|
// blobTree.primitiveNodeIdx[j] += std::max(int(subBlobTreeSize) - 1, 0);
|
|
// }
|
|
// blobTree.structure[originLeafIdx].isPrimitive = false;
|
|
// blobTree.structure[originLeafIdx].nodeOp = visiblePrimitiveReps[i].subBlobTree.structure.back().nodeOp;
|
|
// blobTree.structure.insert(blobTree.structure.begin() + originLeafIdx,
|
|
// visiblePrimitiveReps[i].subBlobTree.structure.begin(),
|
|
// visiblePrimitiveReps[i].subBlobTree.structure.end() - 1);
|
|
|
|
// realLeafIndices.reserve(realLeafIndices.size() + visiblePrimitiveReps[i].subBlobTree.primitiveNodeIdx.size());
|
|
// for (auto primitiveIdx : visiblePrimitiveReps[i].subBlobTree.primitiveNodeIdx) {
|
|
// realLeafIndices.push_back(primitiveIdx + originLeafIdx);
|
|
// }
|
|
// minimalReps.reserve(minimalReps.size() + visiblePrimitiveReps[i].tensors.size());
|
|
// const auto& aabb = visiblePrimitiveReps[i].aabb;
|
|
// for (const auto& tensor : visiblePrimitiveReps[i].tensors) {
|
|
// minimalReps.emplace_back(MinimalPrimitiveRep{tensor, aabb});
|
|
// }
|
|
// } else {
|
|
// blobTree.structure[originLeafIdx].isPrimitive = true;
|
|
// realLeafIndices.push_back(originLeafIdx);
|
|
// minimalReps.emplace_back(MinimalPrimitiveRep{visiblePrimitiveReps[i].tensors[0], visiblePrimitiveReps[i].aabb});
|
|
// }
|
|
// }
|
|
// blobTree.primitiveNodeIdx = realLeafIndices;
|
|
// }
|
|
|
|
void upwardGeneratingNodes(std::vector<int>& levelLeftBook,
|
|
organizer::BlobTree& tree,
|
|
int level,
|
|
int primitiveIdx,
|
|
bool isFinal)
|
|
{
|
|
assert(level <= levelLeftBook.size());
|
|
if (level == levelLeftBook.size()) { levelLeftBook.emplace_back(-1); }
|
|
if (levelLeftBook[level] != -1) {
|
|
// 右节点
|
|
if (level == 0) {
|
|
tree.primitiveNodeIdx[primitiveIdx] = tree.structure.size();
|
|
tree.structure.emplace_back(organizer::Blob{1, 0, 0, 0, 0, 0});
|
|
} else {
|
|
tree.structure.emplace_back(organizer::Blob{0, organizer::OP_INTERSECTION, 0, 0, 0, 0});
|
|
}
|
|
// upwards
|
|
tree.structure[levelLeftBook[level]].ancestor = tree.structure.size() - levelLeftBook[level];
|
|
levelLeftBook[level] = -1;
|
|
upwardGeneratingNodes(levelLeftBook, tree, level + 1, primitiveIdx, isFinal);
|
|
} else {
|
|
if (isFinal) {
|
|
// 不会再有同层的其它右节点了。因此该节点应作为右节点与更高层的左节点组合
|
|
if (level == 0) {
|
|
tree.primitiveNodeIdx[primitiveIdx] = tree.structure.size();
|
|
tree.structure.emplace_back(organizer::Blob{1, 0, 0, 0, 0, 0});
|
|
} else {
|
|
tree.structure.emplace_back(organizer::Blob{0, organizer::OP_INTERSECTION, 0, 0, 0, 0});
|
|
}
|
|
// upwards
|
|
// 向上寻找第一个有记录的左节点
|
|
int i = level + 1;
|
|
if (i == levelLeftBook.size()) return;
|
|
for (; i < levelLeftBook.size(); ++i) {
|
|
if (levelLeftBook[i] != -1) break;
|
|
}
|
|
assert(i < levelLeftBook.size());
|
|
tree.structure[levelLeftBook[i]].ancestor = tree.structure.size() - levelLeftBook[i];
|
|
levelLeftBook[level] = -1;
|
|
upwardGeneratingNodes(levelLeftBook, tree, i + 1, primitiveIdx, isFinal);
|
|
} else {
|
|
// 左节点
|
|
levelLeftBook[level] = tree.structure.size(); // 标记左节点的位置
|
|
if (level == 0) {
|
|
tree.primitiveNodeIdx[primitiveIdx] = tree.structure.size();
|
|
tree.structure.emplace_back(organizer::Blob{1, 0, 0, 0, 1, 0});
|
|
} else {
|
|
tree.structure.emplace_back(organizer::Blob{0, organizer::OP_INTERSECTION, 0, 0, 1, 0});
|
|
}
|
|
}
|
|
}
|
|
};
|
|
|
|
void buildNearBalancedBlobTree(organizer::BlobTree& tree, int leafSize)
|
|
{
|
|
std::vector<int> levelLeftBook;
|
|
tree.primitiveNodeIdx.resize(leafSize);
|
|
for (int i = 0; i < leafSize; ++i) { upwardGeneratingNodes(levelLeftBook, tree, 0, i, i == leafSize - 1); }
|
|
};
|
|
}; // namespace algoim::organizer
|
|
|