GU_ConvexHull3D.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * NAME:        GU_ConvexHull3D.h ( GU Library, C++)
 *
 */

#ifndef __GU_ConvexHull3D_h__
#define __GU_ConvexHull3D_h__

#include "GU_API.h"

#include <GEO/GEO_PolyCounts.h>

#include <UT/UT_Array.h>
#include <UT/UT_BoundingBox.h>
#include <UT/UT_Format.h>
#include <UT/UT_Plane.h>
#include <UT/UT_StringStream.h>
#include <UT/UT_ValArray.h>

class GA_PointGroup;
class GA_Range;
class GU_Detail;

/// Utility for computing (and optionally expanding or shrinking) convex hulls.
/// This uses Bullet's convex hull algorithm (btConvexHullComputer).
class GU_API GU_ConvexHull3D
{
public:
    /// Computes the convex hull of the given point cloud.
    /// @param shrink_amount If greater than zero, each face will be moved
    /// towards the center along its normal by this amount. The value will be
    /// clamped to not exceed the minimum distance of any face to the center of
    /// the convex hull.
    void computeAndShrink(fpreal shrink_amount, const UT_Vector3D *points,
                          int npoints, bool remove_inline);
    void computeAndShrink(fpreal shrink_amount, const UT_Vector3DArray &points, 
                          bool remove_inline)
    { computeAndShrink(shrink_amount, points.data(), points.entries(), remove_inline); }

    /// Calls computeAndShrink() with the point positions from the given
    /// detail.
    void computeAndShrink(
        fpreal shrink_amount, const GU_Detail &src_gdp,
        const GA_PointGroup *src_grp, bool remove_inline);

    /// Calls computeAndShrink() with the point positions from the point or
    /// primitive range in the detail.
    void computeAndShrink(
            fpreal shrink_amount,
            const GU_Detail &src_gdp,
            const GA_Range &src_range,
            bool remove_inline);

    /// Expands the convex hull outwards by the given amount.
    void expand(fpreal expand_amount);

    /// Transforms the convex hull points.
    void transform(const UT_Matrix4D &xform);

    /// Appends the convex hull's geometry to the given detail, optionally
    /// copying attributes from the corresponding points in the source detail.
    void getGeometry(GU_Detail &gdp, const GU_Detail *src_gdp = nullptr,
                     const GA_PointGroup *src_grp = nullptr) const;

    /// Returns a list of the points in the convex hull.
    const UT_Array<UT_Vector3D> &getPoints() const { return myPoints; }

    /// Returns the source point index for each point in the convex hull.
    const UT_Array<int> &getPointSources() const { return myPointSources; }

    /// Returns a list of the polygons in the convex hull.
    const GEO_PolyCounts &getPolygonSizes() const { return myPolygonSizes; }

    /// Returns a list of the vertices. Use getPolygonSizes() to iterate over
    /// the polygons.
    const UT_Array<int> &getVertices() const { return myVertices; }

private:
    SYS_FORCE_INLINE const UT_Vector3D &vertexPoint(exint vtx) const
    {
        return myPoints(myVertices(vtx));
    }

    UT_Array<UT_Vector3D> myPoints;
    UT_Array<int> myPointSources;
    GEO_PolyCounts myPolygonSizes;
    UT_Array<int> myVertices;
};

/// Utility for working with a convex hull defined as a set of half
/// planes.
template <typename T>
class GU_ConvexHullHalfPlanesT
{
public:
    /// Directly build from a set of directed half planes
    GU_ConvexHullHalfPlanesT(const UT_Array<UT_PlaneT<T>> &planes)
        : myPlanes(planes)
    {
    }

    /// Build from a cloud of points.
    GU_ConvexHullHalfPlanesT(const UT_Vector3DArray &pts)
    {
        // Trivially full world if no points.
        if (!pts.entries())
            return;

        GU_ConvexHull3D         convexer;

        // Note removing inline can result in folded half planes.
        convexer.computeAndShrink(0.0, pts, /*removeinline*/false);

        // Compute a center so we can validate our planes.
        UT_Vector3D             hullcenter;
        hullcenter = 0;
        for (auto && pt : pts)
        {
            hullcenter += pt;
        }
        hullcenter /= pts.entries();

        UT_Vector3DArray        polyposes;
        UT_Array<UT_PlaneT<T>>     planes;
        for (auto && poly : convexer.getPolygonSizes())
        {
            // Ignore degenerate polys, which likely shouldn't
            // be output anyways.
            if (poly.nvertices() < 3)
                continue;

            // Compute this plane.
            polyposes.clear();
            for (exint vtx = 0; vtx < poly.nvertices(); vtx++)
            {
                exint pt = convexer.getVertices()(vtx+poly.start());
                polyposes.append(convexer.getPoints()(pt));
            }

            UT_Vector3D p2 = polyposes.last();
            UT_Vector3D nml(0,0,0);
            UT_Vector3D center(0,0,0);
            for (exint vtx = 0; vtx < poly.nvertices(); vtx++)
            {
                UT_Vector3D p1 = p2;
                p2 = polyposes(vtx);
                center += p2;
                // Newell's method.
                nml.normal(p1, p2);
            }

            center /= polyposes.entries();
            nml.normalize();

            UT_PlaneT<T> plane(center, nml);
            // Verify our hull center is on the correct side.
            UT_ASSERT(plane.distance(hullcenter) <= 0);
            if (plane.distance(hullcenter) > 0)
            {
                // Skip this plane, something went horribly wrong,
                // might be a mis-wound polygon.  It likely is somethin
                // degenerate so ignoring likely is the right thing.
                continue;
            }

            myPlanes.append(plane);
        }
    }

    void addPlane(const UT_PlaneT<T> &plane)
    {
        myPlanes.append(plane);
    }

    void applyOffset(T offset)
    {
        for (auto && plane : myPlanes)
        {
            plane.shiftOffset(offset);
        }
    }

    /// Return signed distance for the convex hull.
    template <typename S>
    T 
    distance(UT_Vector3T<S> pos) const
    {
        T           dist = -FLT_MAX;
        // If any plane excludes it, it is excluded.
        for (auto && plane : myPlanes)
        {
            dist = SYSmax(dist, plane.distance(pos));
        }
        return dist;
    }

    /// Return signed distance for the convex hull.
    /// Early exits when maxdist is reached.
    template <typename S>
    T 
    distance(UT_Vector3T<S> pos, T maxdist) const
    {
        T           dist = -FLT_MAX;
        // If any plane excludes it, it is excluded.
        for (auto && plane : myPlanes)
        {
            dist = SYSmax(dist, plane.distance(pos));
            if (dist > maxdist)
                return dist;
        }
        return dist;
    }

    /// Return signed distance for the convex hull.
    /// Restricts tests to a set of active planes.
    /// Early exits when maxdist is reached.
    template <typename IDX, typename S>
    T 
    distance(const UT_Array<IDX> &activeplanes, UT_Vector3T<S> pos, T maxdist) const
    {
        T           dist = -FLT_MAX;
        // If any plane excludes it, it is excluded.
        for (auto && idx : activeplanes)
        {
            dist = SYSmax(dist, myPlanes(idx).distance(pos));
            if (dist > maxdist)
                return dist;
        }
        return dist;
    }


    /// Constructs a list of planes that are active for the given
    /// sphere.  These will be any planes that intersect the sphere.
    /// The idea being that if one has already culled by this sphere,
    /// only these planes have to be tested to if we are in or out.
    /// If no active planes are found, the return result will be true
    /// if entirely inside the planes, or false if entirely out.
    template <typename IDX, typename S>
    bool
    findActivePlanes(UT_Array<IDX> &activeplanes, UT_Vector3T<S> pos, T rad) const
    {
        IDX             idx = 0;
        bool            allinside = true;

        activeplanes.clear();
        for (auto && plane : myPlanes)
        {
            T dist = plane.distance(pos);
            if (dist >= -rad && dist < rad)
            {
                activeplanes.append(idx);
            }
            else if (dist >= rad)
            {
                // A plane fully excludes us, so thus all planes will.
                // We can clear any previous planes and return outside.
                activeplanes.clear();
                return false;
            }
            if (dist > 0)
                allinside = false;
            idx++;
        }
        return allinside;
    }


    template <typename S>
    bool 
    contains(const UT_BoundingBoxT<S> &bbox) const
    {
        UT_Vector3T<T>     bmin(bbox.minvec());
        UT_Vector3T<T>     bmax(bbox.maxvec());

        UT_Vector3T<T>     center = (bmax + bmin) / 2;
        T                  bboxrad = (bmax - bmin).length() / 2;

        T                  centerdist = distance(center, bboxrad);

        // Check if bounding sphere is fully inside the hull.
        if (centerdist <= -bboxrad)
        {
            return true;
        }
        // Check if it is fully outside of the hull.
        if (centerdist >= bboxrad)
        {
            return false;
        }

        // Also check the 8 corners to see if all
        // are contained.  Specifically, if any corner is excluded
        // we know we fail, otherwise we pass.
        for (int i = 0; i < 8; i++)
        {
            UT_Vector3T<T>  pt( i & 1 ? bmin.x() : bmax.x(),
                            i & 2 ? bmin.y() : bmax.y(),
                            i & 4 ? bmin.z() : bmax.z() );
            if (excludes(pt))
                return false;
        }
        return true;
    }

    template <typename S>
    bool 
    excludes(UT_Vector3T<S> pos, T radius = 0) const
    {
        // If any plane excludes it, it is excluded.
        T dist = distance(pos, radius);
        if (dist >= radius)
            return true;
        // Nothing excludes, so must partially overlap.
        return false;
    }

    template <typename S>
    bool 
    excludes(const UT_BoundingBoxT<S> &bbox) const
    {
        UT_Vector3T<T> bmin(bbox.minvec());
        UT_Vector3T<T> bmax(bbox.maxvec());
        UT_Vector3T<T> center = (bmax + bmin) / 2;

        // Check the bounding sphere is outside the box.
        if (excludes(center, (bmax - bmin).length()/2))
        {
            return true;
        }

        return false;
    }

    size_t      format(char *buffer, size_t bufsize) const
    {
        UT_OStringStream tmp;
        bool first = true;
        for (auto &&item : myPlanes)
        {
            if (!first)
                tmp << ", ";
            first = false;
            UTformat(tmp, "{}", item);
        }

        UT::Format::Writer writer(buffer, bufsize);
        UT::Format::Formatter f;
        return f.format(writer, "[{}]", {tmp.str()});
    }

protected:
    UT_Array<UT_PlaneT<T>>         myPlanes;
};

template <typename T>
size_t format(char *buffer, size_t bufsize, const GU_ConvexHullHalfPlanesT<T> &h)
{
    return h.format(buffer, bufsize);
}

using GU_ConvexHullHalfPlanesR = GU_ConvexHullHalfPlanesT<fpreal>;
using GU_ConvexHullHalfPlanesF = GU_ConvexHullHalfPlanesT<fpreal32>;
using GU_ConvexHullHalfPlanesD = GU_ConvexHullHalfPlanesT<fpreal64>;

#endif