从源头看Dust3d | （十）meshsplitter：网格分离

从源头看Dust3d | （十）meshsplitter：网格分离 一、MeshSplitterTriangle类 （一）概述

class MeshSplitterTriangle
{
public:
    int indices[3] = {0, 0, 0};
    
    bool operator<(const MeshSplitterTriangle &other) const
    {
        return std::make_tuple(indices[0], indices[1], indices[2]) <
            std::make_tuple(other.indices[0], other.indices[1], other.indices[2]);
    }
};

（二）具体函数

1.

bool operator<(const MeshSplitterTriangle &other) const
    {
        return std::make_tuple(indices[0], indices[1], indices[2]) <
            std::make_tuple(other.indices[0], other.indices[1], other.indices[2]);
    }

二、MeshSplitter类 （一）概述

class MeshSplitter
{
public:
    static bool split(const std::set &input,
        const std::vector, std::pair>> &trianglelinks,
        std::set &splitter,
        std::set &firstGroup,
        std::set &secondGroup,
        bool expandSplitter=false);
};

（二）函数

split函数：

bool MeshSplitter::split(const std::set &input,
    const std::vector, std::pair>> &trianglelinks,
    std::set &splitter,
    std::set &firstGroup,
    std::set &secondGroup,
    bool expandSplitter)
{
    firstGroup.clear();
    secondGroup.clear();
    
    // Make the edge to triangle map, this map will be used to find the neighbor triangles
    std::map, MeshSplitterTriangle> edgeToTriangleMap;
    for (const auto &triangle: input) {
        for (int i = 0; i < 3; i++) {
            int next = (i + 1) % 3;
            edgeToTriangleMap[std::make_pair(triangle.indices[i], triangle.indices[next])] = triangle;
        }
    }
    
    std::map, MeshSplitterTriangle> edgeTolinkedTriangleMap;
    for (const auto &it: trianglelinks) {
        auto firstEdge = std::make_pair((int)it.first.first, (int)it.first.second);
        auto secondEdge = std::make_pair((int)it.second.first, (int)it.second.second);
        auto findFirstTriangle = edgeToTriangleMap.find(firstEdge);
        auto findSecondTriangle = edgeToTriangleMap.find(secondEdge);
        if (findFirstTriangle == edgeToTriangleMap.end())
            continue;
        if (findSecondTriangle == edgeToTriangleMap.end())
            continue;
        edgeTolinkedTriangleMap[firstEdge] = findSecondTriangle->second;
        edgeTolinkedTriangleMap[std::make_pair(firstEdge.second, firstEdge.first)] = findSecondTriangle->second;
        edgeTolinkedTriangleMap[secondEdge] = findFirstTriangle->second;
        edgeTolinkedTriangleMap[std::make_pair(secondEdge.second, secondEdge.first)] = findFirstTriangle->second;
    }
    
    // Expand the splitter if needed
    if (expandSplitter) {
        std::vector expandedTriangles;
        for (const auto &triangle: splitter) {
            for (int i = 0; i < 3; i++) {
                int next = (i + 1) % 3;
                auto oppositeEdge = std::make_pair(triangle.indices[next], triangle.indices[i]);
                auto oppositeTriangle = edgeToTriangleMap.find(oppositeEdge);
                if (oppositeTriangle != edgeToTriangleMap.end()) {
                    if (splitter.find(oppositeTriangle->second) == splitter.end()) {
                        expandedTriangles.push_back(oppositeTriangle->second);
                    }
                }
            }
        }
        size_t addTriangles = 0;
        for (const auto &triangle: expandedTriangles) {
            auto insertResult = splitter.insert(triangle);
            if (insertResult.second)
                ++addTriangles;
        }
        if (0 == addTriangles) {
            qDebug() << "Expanded without new triangles added";
        } else {
            qDebug() << "Expanded with new triangles added:" << addTriangles;
        }
    }
    
    // Find one triangle which is direct neighbor of one splitter
    MeshSplitterTriangle startTriangle;
    bool foundStartTriangle = false;
    for (const auto &triangle: splitter) {
        for (int i = 0; i < 3; i++) {
            int next = (i + 1) % 3;
            auto oppositeEdge = std::make_pair(triangle.indices[next], triangle.indices[i]);
            auto oppositeTriangle = edgeToTriangleMap.find(oppositeEdge);
            if (oppositeTriangle == edgeToTriangleMap.end()) {
                qDebug() << "Find opposite edge failed:" << oppositeEdge.first << oppositeEdge.second;
                continue;
            }
            if (splitter.find(oppositeTriangle->second) == splitter.end()) {
                foundStartTriangle = true;
                startTriangle = oppositeTriangle->second;
                break;
            }
        }
    }
    if (!foundStartTriangle) {
        qDebug() << "Find start triangle for splitter failed";
        return false;
    }
    
    // Recursively join all the neighbors of the first found triangle to the first group
    std::set processedTriangles;
    for (const auto &triangle: splitter) {
        processedTriangles.insert(triangle);
    }
    std::queue waitQueue;
    waitQueue.push(startTriangle);
    while (!waitQueue.empty()) {
        MeshSplitterTriangle triangle = waitQueue.front();
        waitQueue.pop();
        firstGroup.insert(triangle);
        if (!processedTriangles.insert(triangle).second)
            continue;
        for (int i = 0; i < 3; i++) {
            int next = (i + 1) % 3;
            auto oppositeEdge = std::make_pair(triangle.indices[next], triangle.indices[i]);
            auto oppositeTriangle = edgeToTriangleMap.find(oppositeEdge);
            if (oppositeTriangle != edgeToTriangleMap.end()) {
                if (processedTriangles.find(oppositeTriangle->second) == processedTriangles.end()) {
                    waitQueue.push(oppositeTriangle->second);
                }
            }
            auto linkedTriangle = edgeTolinkedTriangleMap.find(oppositeEdge);
            if (linkedTriangle != edgeTolinkedTriangleMap.end()) {
                if (processedTriangles.find(linkedTriangle->second) == processedTriangles.end()) {
                    waitQueue.push(linkedTriangle->second);
                }
            }
        }
    }
    
    // Now, the remains should be put in the second group
    for (const auto &triangle: input) {
        if (processedTriangles.find(triangle) != processedTriangles.end())
            continue;
        secondGroup.insert(triangle);
    }
    
    // Any of these two groups is empty means split failed
    if (firstGroup.empty() || secondGroup.empty()) {
        qDebug() << "At lease one group is empty";
        return false;
    }

    return true;
}