Method computeConvexHull

src/utils/quickhull/QuickHull.cpp:44–132

Compute the convex hull of a set of points and return the resulting convex mesh

// Compute the convex hull of a set of points and return the resulting convex mesh
bool QuickHull::computeConvexHull(const VertexArray& vertexArray, PolygonVertexArray& outPolygonVertexArray,
                                  Array<float>& outVertices, Array<unsigned int>& outIndices,
                                  Array<PolygonVertexArray::PolygonFace>& outFaces, MemoryAllocator& allocator,
                                  std::vector<Message>& errors) {

    bool isValid = true;

    // Extract the points from the array
    Array<Vector3> points(allocator);
    extractPoints(vertexArray, points);

    // Remove the duplicated vertices from the points
    removeDuplicatedVertices(points, allocator);

    // If there are less than four vertices in the vertex array
    if (points.size() < 4) {

       errors.push_back(Message("The VertexArray must contain at least 4 vertices to create a convex mesh"));
       return false;
    }

    Array<uint32> orphanPointsIndices(allocator, points.size());
    decimal maxAbsX = 0;
    decimal maxAbsY = 0;
    decimal maxAbsZ = 0;
    for (uint32 i=0 ; i < points.size(); i++) {
        orphanPointsIndices.add(i);

        decimal absX = std::abs(points[i].x);
        decimal absY = std::abs(points[i].y);
        decimal absZ = std::abs(points[i].z);

        if (absX > maxAbsX) {
            maxAbsX = absX;
        }
        if (absY > maxAbsY) {
            maxAbsY = absY;
        }
        if (absZ > maxAbsZ) {
            maxAbsZ = absZ;
        }
    }

    // Compute the 'epsilon' value for this set of points
    const decimal epsilon = 3 * (maxAbsX + maxAbsY + maxAbsZ) * MACHINE_EPSILON;

    QHHalfEdgeStructure convexHull(allocator);

    Array<QHHalfEdgeStructure::Face*> initialFaces(allocator);

    // Compute the initial convex hull
    isValid &= computeInitialHull(points, convexHull, initialFaces, orphanPointsIndices, allocator, errors);
    if (!isValid) {
        return false;
    }

    assert(convexHull.getNbVertices() == 4);
    assert(convexHull.getNbFaces() == 4);