ConvexHull.h

#pragma once
 
#include <Core/CoreDLL.h>
#include <Foundation/Containers/Deque.h>
#include <Foundation/Containers/DynamicArray.h>
#include <Foundation/Math/Vec3.h>
 
class PL_CORE_DLL plConvexHullGenerator
{
public:
  struct Face
  {
    PL_DECLARE_POD_TYPE();
 
    plUInt16 m_uiVertexIdx[3];
  };
 
  plConvexHullGenerator();
  ~plConvexHullGenerator();
 
  void SetSimplificationMinTriangleAngle(plAngle angle) { m_MinTriangleAngle = angle; }
 
  void SetSimplificationFlatVertexNormalThreshold(plAngle angle) { m_FlatVertexNormalThreshold = angle; }
 
  void SetSimplificationMinTriangleEdgeLength(double fLen) { m_fMinTriangleEdgeLength = fLen; }
 
  plResult Build(const plArrayPtr<const plVec3> vertices);
 
  void Retrieve(plDynamicArray<plVec3>& out_vertices, plDynamicArray<Face>& out_faces);
 
  void RetrieveVertices(plDynamicArray<plVec3>& out_vertices);
 
private:
  plResult ComputeCenterAndScale(const plArrayPtr<const plVec3> vertices);
  plResult StoreNormalizedVertices(const plArrayPtr<const plVec3> vertices);
  void StoreTriangle(plUInt16 i, plUInt16 j, plUInt16 k);
  plResult InitializeHull();
  plResult ComputeHull();
  bool IsInside(plUInt32 vtxId) const;
  void RemoveVisibleFaces(plUInt32 vtxId);
  void PatchHole(plUInt32 vtxId);
  bool PruneFlatVertices(double fNormalThreshold);
  bool PruneDegenerateTriangles(double fMaxCosAngle);
  bool PruneSmallTriangles(double fMaxEdgeLen);
  plResult ProcessVertices(const plArrayPtr<const plVec3> vertices);
 
  struct TwoSet
  {
    PL_ALWAYS_INLINE TwoSet()
    {
      a = 0xFFFF;
      b = 0xFFFF;
    }
    PL_ALWAYS_INLINE void Add(plUInt16 x) { (a == 0xFFFF ? a : b) = x; }
    PL_ALWAYS_INLINE bool Contains(plUInt16 x) { return a == x || b == x; }
    PL_ALWAYS_INLINE void Remove(plUInt16 x) { (a == x ? a : b) = 0xFFFF; }
    PL_ALWAYS_INLINE int GetSize() { return (a != 0xFFFF) + (b != 0xFFFF); }
 
    plUInt16 a, b;
  };
 
  struct Triangle
  {
    plVec3d m_vNormal;
    double m_fPlaneDistance;
    plUInt16 m_uiVertexIdx[3];
    bool m_bFlip;
    bool m_bIsDegenerate;
  };
 
  // used for mesh simplification
  plAngle m_MinTriangleAngle = plAngle::MakeFromDegree(22.0f);
  plAngle m_FlatVertexNormalThreshold = plAngle::MakeFromDegree(5);
  double m_fMinTriangleEdgeLength = 0.05;
 
  plVec3d m_vCenter;
  double m_fScale;
 
  plVec3d m_vInside;
 
  // all the 'good' vertices (no duplicates)
  // normalized to be within a unit-cube
  plDynamicArray<plVec3d> m_Vertices;
 
  // Will be resized to Square(m_Vertices.GetCount())
  // Index [i * m_Vertices.GetCount() + j] indicates which (up to two) other points
  // combine with the edge i and j to make a triangle in the hull.  Only defined when i < j.
  plDynamicArray<TwoSet> m_Edges;
 
  plDeque<Triangle> m_Triangles;
};