Method removeDuplicatedVertices

src/utils/quickhull/QuickHull.cpp:758–804

Remove duplicated vertices in the input array of points

// Remove duplicated vertices in the input array of points
void QuickHull::removeDuplicatedVertices(Array<Vector3>& points, MemoryAllocator& allocator) {

    const decimal distanceEpsilon = 0.00001f;
    Array<Vector3> pointsToKeep(allocator, points.size());

    // Compute the points cloud center
    Vector3 center(0, 0, 0);
    for (uint32 i=0; i < points.size(); i++) {
        center += points[i];
    }
    center /= points.size();

    // For each input point
    for (uint32 i=0; i < points.size(); i++) {

        // For each point to keep
        uint32 j;
        for (j=0; j < pointsToKeep.size(); j++) {

            decimal dx = std::abs(pointsToKeep[j].x - points[i].x);
            decimal dy = std::abs(pointsToKeep[j].y - points[i].y);
            decimal dz = std::abs(pointsToKeep[j].z - points[i].z);

            // If the points are nearly the same
            if (dx < distanceEpsilon && dy < distanceEpsilon && dz < distanceEpsilon) {

                // Between the two points, we keep the one that is the furthest away from the cloud points center
                if ((points[i] - center).lengthSquare() > (pointsToKeep[j] - center).lengthSquare()) {

                    pointsToKeep[j] = points[i];
                }

                break;
            }
        }

        // If the point is not already in the array of points to keep
        if (j == pointsToKeep.size()) {

            // We add it
            pointsToKeep.add(points[i]);
        }
    }

    points.clear();
    points.addRange(pointsToKeep);
}

// Return the index of the next vertex candidate to be added to the hull
// This method returns INVALID_VERTEX_INDEX if there is no more vertex candidate