Есть у меня такой вот мешь:
В блендере это 1 мешь. Задача разделить его на не связанные друг с другом части. Таких в итоге, в данном случае, получается 7. Значит на выходе должно быть 7 мешей.
Для этого я написал вот такой код:
inline bool Collision::IsNeighbor(Triangle* current, Triangle* neighbor) {
//current Vert 1
if (current->Vert1 == neighbor->Vert1) {
return true;
}
else if (current->Vert1 == neighbor->Vert2)
{
return true;
}
else if (current->Vert1 == neighbor->Vert3)
{
return true;
}
//current Vert 2
else if (current->Vert2 == neighbor->Vert1)
{
return true;
}
else if (current->Vert2 == neighbor->Vert2)
{
return true;
}
else if (current->Vert2 == neighbor->Vert3)
{
return true;
}
//current Vert 3
else if (current->Vert3 == neighbor->Vert1)
{
return true;
}
else if (current->Vert3 == neighbor->Vert2)
{
return true;
}
else if (current->Vert3 == neighbor->Vert3)
{
return true;
}
return false;
}
inline bool Collision::SeparateCollider() {
Triangle currentTriangle;
Triangle neighborTriangle;
size_t countOfPrimitives;
while (Collision::GeneralCollider->Points.size() != 0)
{
Collision::PrimitivesCollider.push_back(new Collider);
countOfPrimitives = Collision::PrimitivesCollider.size() - 1;
currentTriangle.Vert1 = Collision::GeneralCollider->Points[0];
currentTriangle.Vert2 = Collision::GeneralCollider->Points[1];
currentTriangle.Vert3 = Collision::GeneralCollider->Points[2];
Collision::PrimitivesCollider[countOfPrimitives]->Points.push_back(currentTriangle.Vert1);
Collision::PrimitivesCollider[countOfPrimitives]->Points.push_back(currentTriangle.Vert2);
Collision::PrimitivesCollider[countOfPrimitives]->Points.push_back(currentTriangle.Vert3);
//Erease current triangle from general buffer
Collision::GeneralCollider->Points.erase(Collision::GeneralCollider->Points.begin(), Collision::GeneralCollider->Points.begin() + 3);
size_t it = 3;
do
{
for (size_t jt = 0; jt < Collision::GeneralCollider->Points.size(); jt += 3)
{
//Definition neighbor triangle
neighborTriangle.Vert1 = Collision::GeneralCollider->Points[jt];
neighborTriangle.Vert2 = Collision::GeneralCollider->Points[jt + 1];
neighborTriangle.Vert3 = Collision::GeneralCollider->Points[jt + 2];
//Check is neighbor triangle really neighbor for current triangle
if (IsNeighbor(¤tTriangle, &neighborTriangle)) {
Collision::PrimitivesCollider[countOfPrimitives]->Points.push_back(neighborTriangle.Vert1);
Collision::PrimitivesCollider[countOfPrimitives]->Points.push_back(neighborTriangle.Vert2);
Collision::PrimitivesCollider[countOfPrimitives]->Points.push_back(neighborTriangle.Vert3);
//Erease neighbor triangle from general buffer
Collision::GeneralCollider->Points.erase(Collision::GeneralCollider->Points.begin() + jt, Collision::GeneralCollider->Points.begin() + jt + 3);
//Set neighbor triangle as current triangle
currentTriangle.Vert1 = neighborTriangle.Vert1;
currentTriangle.Vert2 = neighborTriangle.Vert2;
currentTriangle.Vert3 = neighborTriangle.Vert3;
it += 3;
jt = -3;
}
}
it -= 3;
if (it != 0) {
//Add last triangle of part
currentTriangle.Vert1 = Collision::PrimitivesCollider[countOfPrimitives]->Points[it - 3];
currentTriangle.Vert2 = Collision::PrimitivesCollider[countOfPrimitives]->Points[it - 2];
currentTriangle.Vert3 = Collision::PrimitivesCollider[countOfPrimitives]->Points[it - 1];
}
} while (it != 0);
}
return true;
}
В целом как он работает:
Он берёт первый треугольник из общего буффера и ищет все возможные пути от него до тех пор, пока не переберёт все. После считается, что один несвязанные мешь найден. И так повторяет пока общий буффер не будет полностью опустошён.
По моим тестам этот код работает, но проблема в том, что он работает слишком медленно. Если на входе будет мешь, состоящий из сотни тысяч вершин, то его разделение займёт пару минут! В то время как разделение этого же меша в блендере соответсвующей функцией происходит моментально.
Вопрос, как можно ускорить данный алгоритм?
