Method deleteVisibleFaces

src/utils/quickhull/QuickHull.cpp:277–319

Delete all the faces visible from the vertex to be added

// Delete all the faces visible from the vertex to be added
void QuickHull::deleteVisibleFaces(const Array<QHHalfEdgeStructure::Face*>& visibleFaces,
                                   QHHalfEdgeStructure& convexHull,
                                   Array<uint32>& orphanPoints,
                                   const Array<QHHalfEdgeStructure::Vertex*>& horizonVertices,
                                   MemoryAllocator& allocator) {

    const uint32 nbFaces = visibleFaces.size();

    Set<QHHalfEdgeStructure::Vertex*> verticesToRemove(allocator);

    // For each visible face
    for (uint32 i=0; i < nbFaces; i++) {

        // Add all the remaining points associated with this face to the array of orphan points
        orphanPoints.addRange(visibleFaces[i]->conflictPoints);

        // For each vertex of the face to remove
        const QHHalfEdgeStructure::Edge* firstFaceEdge = visibleFaces[i]->edge;
        const QHHalfEdgeStructure::Edge* faceEdge = firstFaceEdge;
        do {

           QHHalfEdgeStructure::Vertex* vertex = faceEdge->startVertex;

           // If the vertex is not part of the horizon
           if (!testIsVertexInHorizon(vertex, horizonVertices)) {

               // Add the vertex to the set of vertices to be removed
               verticesToRemove.add(vertex);
           }

           faceEdge = faceEdge->nextFaceEdge;

        } while(faceEdge != firstFaceEdge);

        // Remove the face from the current convex hull
        convexHull.removeFace(visibleFaces[i]);
    }

    // Remove the vertices to be removed
    for (auto it = verticesToRemove.begin(); it != verticesToRemove.end(); ++it) {
        convexHull.removeVertex(*it);
    }
}

// Return true if the vertex is part of horizon edges
bool QuickHull::testIsVertexInHorizon(QHHalfEdgeStructure::Vertex* vertex, const Array<QHHalfEdgeStructure::Vertex*>& horizonVertices) {