Method fixTopologicalIssues

src/utils/quickhull/QuickHull.cpp:629–668

Fix topological issues (if any) that might have been created during faces merge

// Fix topological issues (if any) that might have been created during faces merge
void QuickHull::fixTopologicalIssues(QHHalfEdgeStructure& convexHull, QHHalfEdgeStructure::Face* face, const Array<Vector3>& points,
                                     Set<QHHalfEdgeStructure::Face*>& deletedFaces) {

    // Here we want to make sure that each vertex of the convex hull has at least
    // three adjacent faces

    QHHalfEdgeStructure::Edge* edgeError;

    // While we can find an edge with an error (a redundant vertex) in the face
    do {

        edgeError = nullptr;

        // For each vertex of the face we check if the incoming and outgoing edge have
        // the same face on the opposite side
        QHHalfEdgeStructure::Edge* firstInEdge = face->edge;
        QHHalfEdgeStructure::Edge* inEdge = firstInEdge;
        do {

            assert(inEdge != nullptr);

            QHHalfEdgeStructure::Edge* outEdge = inEdge->nextFaceEdge;

            if (inEdge->twinEdge->face == outEdge->twinEdge->face) {
                edgeError = inEdge;
                break;
            }

            // Move to the next edge of the face
            inEdge = outEdge;
        }
        while (inEdge != firstInEdge);

        // If we have found an edge with error (redundant vertex)
        if (edgeError != nullptr) {
           fixTopologicalIssueAtEdge(convexHull, face, edgeError, points, deletedFaces);
        }

    } while (edgeError != nullptr);
}

// Fix topological issue at a given edge
void QuickHull::fixTopologicalIssueAtEdge(QHHalfEdgeStructure& convexHull, QHHalfEdgeStructure::Face* face,