VHACD.h

Go to the documentation of this file.

/* Copyright (c) 2011 Khaled Mamou (kmamou at gmail dot com)
 All rights reserved.
 
 
 Redistribution and use in source and binary forms, with or without modification, are permitted provided that the
 following conditions are met:
 
 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following
 disclaimer.
 
 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following
 disclaimer in the documentation and/or other materials provided with the distribution.
 
 3. The names of the contributors may not be used to endorse or promote products derived from this software without
 specific prior written permission.
 
 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
#pragma once
#ifndef VHACD_H
#define VHACD_H
 
// Please view this slide deck which describes usage and how the algorithm works.
// https://docs.google.com/presentation/d/1OZ4mtZYrGEC8qffqb8F7Le2xzufiqvaPpRbLHKKgTIM/edit?usp=sharing
 
// VHACD is now a header only library.
// In just *one* of your CPP files *before* you include 'VHACD.h' you must declare
// #define ENABLE_VHACD_IMPLEMENTATION 1
// This will compile the implementation code into your project. If you don't
// have this define, you will get link errors since the implementation code will
// not be present. If you define it more than once in your code base, you will get
// link errors due to a duplicate implementation. This is the same pattern used by
// ImGui and StbLib and other popular open source libraries.
 
#define VHACD_VERSION_MAJOR 4
#define VHACD_VERSION_MINOR 1
 
// Changes for version 4.1
//
// Various minor tweaks mostly to the test application and some default values.
 
// Changes for version 4.0
//
// * The code has been significantly refactored to be cleaner and easier to maintain
//      * All OpenCL related code removed
//      * All Bullet code removed
//      * All SIMD code removed
//      * Old plane splitting code removed
//
// * The code is now delivered as a single header file 'VHACD.h' which has both the API
// * declaration as well as the implementation.  Simply add '#define ENABLE_VHACD_IMPLEMENTATION 1'
// * to any CPP in your application prior to including 'VHACD.h'. Only do this in one CPP though.
// * If you do not have this define once, you will get link errors since the implementation code
// * will not be compiled in. If you have this define more than once, you are likely to get
// * duplicate symbol link errors.
//
// * Since the library is now delivered as a single header file, we do not provide binaries
// * or build scripts as these are not needed.
//
// * The old DebugView and test code has all been removed and replaced with a much smaller and
// * simpler test console application with some test meshes to work with.
//
// * The convex hull generation code has changed. The previous version came from Bullet.
// * However, the new version is courtesy of Julio Jerez, the author of the Newton
// * physics engine. His new version is faster and more numerically stable.
//
// * The code can now detect if the input mesh is, itself, already a convex object and
// * can early out.
//
// * Significant performance improvements have been made to the code and it is now much
// * faster, stable, and is easier to tune than previous versions.
//
// * A bug was fixed with the shrink wrapping code (project hull vertices) that could
// * sometime produce artifacts in the results. The new version uses a 'closest point'
// * algorithm that is more reliable.
//
// * You can now select which 'fill mode' to use. For perfectly closed meshes, the default
// * behavior using a flood fill generally works fine. However, some meshes have small
// * holes in them and therefore the flood fill will fail, treating the mesh as being
// * hollow. In these cases, you can use the 'raycast' fill option to determine which
// * parts of the voxelized mesh are 'inside' versus being 'outside'. Finally, there
// * are some rare instances where a user might actually want the mesh to be treated as
// * hollow, in which case you can pass in 'surface' only.
// *
// * A new optional virtual interface called 'IUserProfiler' was provided.
// * This allows the user to provide an optional profiling callback interface to assist in
// * diagnosing performance issues. This change was made by Danny Couture at Epic for the UE4 integration.
// * Some profiling macros were also declared in support of this feature.
// *
// * Another new optional virtual interface called 'IUserTaskRunner' was provided.
// * This interface is used to run logical 'tasks' in a background thread. If none is provided
// * then a default implementation using std::thread will be executed.
// * This change was made by Danny Couture at Epic to speed up the voxelization step.
// *
 
// The history of V-HACD:
//
// The initial version was written by John W. Ratcliff and was called 'ACD'
// This version did not perform CSG operations on the source mesh, so if you
// recursed too deeply it would produce hollow results.
//
// The next version was written by Khaled Mamou and was called 'HACD'
// In this version Khaled tried to perform a CSG operation on the source
// mesh to produce more robust results. However, Khaled learned that the
// CSG library he was using had licensing issues so he started work on the
// next version.
//
// The next version was called 'V-HACD' because Khaled made the observation
// that plane splitting would be far easier to implement working in voxel space.
//
// V-HACD has been integrated into UE4, Blender, and a number of other projects.
// This new release, version4, is a significant refactor of the code to fix
// some bugs, improve performance, and to make the codebase easier to maintain
// going forward.
#include <tesseract_common/macros.h>
TESSERACT_COMMON_IGNORE_WARNINGS_PUSH
 
#include <stdint.h>
#include <functional>
 
#include <vector>
#include <array>
#include <cmath>
#include <algorithm>
 
namespace VHACD
{
struct Vertex
{
  double mX;
  double mY;
  double mZ;
 
  Vertex() = default;
  Vertex(double x, double y, double z) : mX(x), mY(y), mZ(z) {}
 
  const double& operator[](size_t idx) const
  {
    switch (idx)
    {
      case 0:
        return mX;
      case 1:
        return mY;
      case 2:
        return mZ;
    };
    return mX;
  }
};
 
struct Triangle
{
  uint32_t mI0;
  uint32_t mI1;
  uint32_t mI2;
 
  Triangle() = default;
  Triangle(uint32_t i0, uint32_t i1, uint32_t i2) : mI0(i0), mI1(i1), mI2(i2) {}
};
 
template <typename T>
class Vector3
{
public:
  /*
   * Getters
   */
  T& operator[](size_t i);
  const T& operator[](size_t i) const;
  T& GetX();
  T& GetY();
  T& GetZ();
  const T& GetX() const;
  const T& GetY() const;
  const T& GetZ() const;
 
  /*
   * Normalize and norming
   */
  T Normalize();
  Vector3 Normalized();
  T GetNorm() const;
  T GetNormSquared() const;
  int LongestAxis() const;
 
  /*
   * Vector-vector operations
   */
  Vector3& operator=(const Vector3& rhs);
  Vector3& operator+=(const Vector3& rhs);
  Vector3& operator-=(const Vector3& rhs);
 
  Vector3 CWiseMul(const Vector3& rhs) const;
  Vector3 Cross(const Vector3& rhs) const;
  T Dot(const Vector3& rhs) const;
  Vector3 operator+(const Vector3& rhs) const;
  Vector3 operator-(const Vector3& rhs) const;
 
  /*
   * Vector-scalar operations
   */
  Vector3& operator-=(T a);
  Vector3& operator+=(T a);
  Vector3& operator/=(T a);
  Vector3& operator*=(T a);
 
  Vector3 operator*(T rhs) const;
  Vector3 operator/(T rhs) const;
 
  /*
   * Unary operations
   */
  Vector3 operator-() const;
 
  /*
   * Comparison operators
   */
  bool operator<(const Vector3& rhs) const;
  bool operator>(const Vector3& rhs) const;
 
  /*
   * Returns true if all elements of *this are greater than or equal to all elements of rhs, coefficient wise
   * LE is less than or equal
   */
  bool CWiseAllGE(const Vector3<T>& rhs) const;
  bool CWiseAllLE(const Vector3<T>& rhs) const;
 
  Vector3 CWiseMin(const Vector3& rhs) const;
  Vector3 CWiseMax(const Vector3& rhs) const;
  T MinCoeff() const;
  T MaxCoeff() const;
 
  T MinCoeff(uint32_t& idx) const;
  T MaxCoeff(uint32_t& idx) const;
 
  /*
   * Constructors
   */
  Vector3() = default;
  Vector3(T a);
  Vector3(T x, T y, T z);
  Vector3(const Vector3& rhs);
  ~Vector3() = default;
 
  template <typename U>
  Vector3(const Vector3<U>& rhs);
 
  Vector3(const VHACD::Vertex&);
  Vector3(const VHACD::Triangle&);
 
  operator VHACD::Vertex() const;
 
private:
  std::array<T, 3> m_data{ T(0.0) };
};
 
typedef VHACD::Vector3<double> Vect3;
 
struct BoundsAABB
{
  BoundsAABB() = default;
  BoundsAABB(const std::vector<VHACD::Vertex>& points);
  BoundsAABB(const Vect3& min, const Vect3& max);
 
  BoundsAABB Union(const BoundsAABB& b);
 
  bool Intersects(const BoundsAABB& b) const;
 
  double SurfaceArea() const;
  double Volume() const;
 
  BoundsAABB Inflate(double ratio) const;
 
  VHACD::Vect3 ClosestPoint(const VHACD::Vect3& p) const;
 
  VHACD::Vect3& GetMin();
  VHACD::Vect3& GetMax();
  const VHACD::Vect3& GetMin() const;
  const VHACD::Vect3& GetMax() const;
 
  VHACD::Vect3 GetSize() const;
  VHACD::Vect3 GetCenter() const;
 
  VHACD::Vect3 m_min{ double(0.0) };
  VHACD::Vect3 m_max{ double(0.0) };
};
 
enum class FillMode
{
  FLOOD_FILL,    // This is the default behavior, after the voxelization step it uses a flood fill to determine 'inside'
                 // from 'outside'. However, meshes with holes can fail and create hollow results.
  SURFACE_ONLY,  // Only consider the 'surface', will create 'skins' with hollow centers.
  RAYCAST_FILL,  // Uses raycasting to determine inside from outside.
};
 
class IVHACD
{
public:
  class IUserCallback
  {
  public:
    virtual ~IUserCallback(){};
 
    virtual void Update(const double overallProgress,
                        const double stageProgress,
                        const char* const stage,
                        const char* operation) = 0;
 
    // This is an optional user callback which is only called when running V-HACD asynchronously.
    // This is a callback performed to notify the user that the
    // convex decomposition background process is completed. This call back will occur from
    // a different thread so the user should take that into account.
    virtual void NotifyVHACDComplete() {}
  };
 
  class IUserLogger
  {
  public:
    virtual ~IUserLogger(){};
    virtual void Log(const char* const msg) = 0;
  };
 
  class IUserTaskRunner
  {
  public:
    virtual ~IUserTaskRunner(){};
    virtual void* StartTask(std::function<void()> func) = 0;
    virtual void JoinTask(void* Task) = 0;
  };
 
  class ConvexHull
  {
  public:
    std::vector<VHACD::Vertex> m_points;
    std::vector<VHACD::Triangle> m_triangles;
 
    double m_volume{ 0 };              // The volume of the convex hull
    VHACD::Vect3 m_center{ 0, 0, 0 };  // The centroid of the convex hull
    uint32_t m_meshId{ 0 };            // A unique id for this convex hull
    VHACD::Vect3 mBmin;                // Bounding box minimum of the AABB
    VHACD::Vect3 mBmax;                // Bounding box maximum of the AABB
  };
 
  class Parameters
  {
  public:
    IUserCallback* m_callback{ nullptr };            // Optional user provided callback interface for progress
    IUserLogger* m_logger{ nullptr };                // Optional user provided callback interface for log messages
    IUserTaskRunner* m_taskRunner{ nullptr };        // Optional user provided interface for creating tasks
    uint32_t m_maxConvexHulls{ 64 };                 // The maximum number of convex hulls to produce
    uint32_t m_resolution{ 400000 };                 // The voxel resolution to use
    double m_minimumVolumePercentErrorAllowed{ 1 };  // if the voxels are within 1% of the volume of the hull, we
                                                     // consider this a close enough approximation
    uint32_t m_maxRecursionDepth{ 10 };              // The maximum recursion depth
    bool m_shrinkWrap{ true };  // Whether or not to shrinkwrap the voxel positions to the source mesh on output
    FillMode m_fillMode{ FillMode::FLOOD_FILL };  // How to fill the interior of the voxelized mesh
    uint32_t m_maxNumVerticesPerCH{ 64 };         // The maximum number of vertices allowed in any output convex hull
    bool m_asyncACD{ true };        // Whether or not to run asynchronously, taking advantage of additional cores
    uint32_t m_minEdgeLength{ 2 };  // Once a voxel patch has an edge length of less than 4 on all 3 sides, we don't
                                    // keep recursing
    bool m_findBestPlane{ false };  // Whether or not to attempt to split planes along the best location. Experimental
                                    // feature. False by default.
  };
 
  virtual void Cancel() = 0;
 
  virtual bool Compute(const float* const points,
                       const uint32_t countPoints,
                       const uint32_t* const triangles,
                       const uint32_t countTriangles,
                       const Parameters& params) = 0;
 
  virtual bool Compute(const double* const points,
                       const uint32_t countPoints,
                       const uint32_t* const triangles,
                       const uint32_t countTriangles,
                       const Parameters& params) = 0;
 
  virtual uint32_t GetNConvexHulls() const = 0;
 
  virtual bool GetConvexHull(const uint32_t index, ConvexHull& ch) const = 0;
 
  virtual void Clean() = 0;  // release internally allocated memory
 
  virtual void Release() = 0;  // release IVHACD
 
  // Will compute the center of mass of the convex hull decomposition results and return it
  // in 'centerOfMass'.  Returns false if the center of mass could not be computed.
  virtual bool ComputeCenterOfMass(double centerOfMass[3]) const = 0;
 
  // In synchronous mode (non-multi-threaded) the state is always 'ready'
  // In asynchronous mode, this returns true if the background thread is not still actively computing
  // a new solution.  In an asynchronous config the 'IsReady' call will report any update or log
  // messages in the caller's current thread.
  virtual bool IsReady() const { return true; }
 
  virtual uint32_t findNearestConvexHull(const double pos[3], double& distanceToHull) = 0;
 
protected:
  virtual ~IVHACD() {}
};
/*
 * Out of line definitions
 */
 
template <typename T>
T clamp(const T& v, const T& lo, const T& hi)
{
  if (v < lo)
  {
    return lo;
  }
  if (v > hi)
  {
    return hi;
  }
  return v;
}
 
/*
 * Getters
 */
template <typename T>
inline T& Vector3<T>::operator[](size_t i)
{
  return m_data[i];
}
 
template <typename T>
inline const T& Vector3<T>::operator[](size_t i) const
{
  return m_data[i];
}
 
template <typename T>
inline T& Vector3<T>::GetX()
{
  return m_data[0];
}
 
template <typename T>
inline T& Vector3<T>::GetY()
{
  return m_data[1];
}
 
template <typename T>
inline T& Vector3<T>::GetZ()
{
  return m_data[2];
}
 
template <typename T>
inline const T& Vector3<T>::GetX() const
{
  return m_data[0];
}
 
template <typename T>
inline const T& Vector3<T>::GetY() const
{
  return m_data[1];
}
 
template <typename T>
inline const T& Vector3<T>::GetZ() const
{
  return m_data[2];
}
 
/*
 * Normalize and norming
 */
template <typename T>
inline T Vector3<T>::Normalize()
{
  T n = GetNorm();
  if (n != T(0.0))
    (*this) /= n;
  return n;
}
 
template <typename T>
inline Vector3<T> Vector3<T>::Normalized()
{
  Vector3<T> ret = *this;
  T n = GetNorm();
  if (n != T(0.0))
    ret /= n;
  return ret;
}
 
template <typename T>
inline T Vector3<T>::GetNorm() const
{
  return std::sqrt(GetNormSquared());
}
 
template <typename T>
inline T Vector3<T>::GetNormSquared() const
{
  return this->Dot(*this);
}
 
template <typename T>
inline int Vector3<T>::LongestAxis() const
{
  auto it = std::max_element(m_data.begin(), m_data.end());
  return int(std::distance(m_data.begin(), it));
}
 
/*
 * Vector-vector operations
 */
template <typename T>
inline Vector3<T>& Vector3<T>::operator=(const Vector3<T>& rhs)
{
  GetX() = rhs.GetX();
  GetY() = rhs.GetY();
  GetZ() = rhs.GetZ();
  return *this;
}
 
template <typename T>
inline Vector3<T>& Vector3<T>::operator+=(const Vector3<T>& rhs)
{
  GetX() += rhs.GetX();
  GetY() += rhs.GetY();
  GetZ() += rhs.GetZ();
  return *this;
}
 
template <typename T>
inline Vector3<T>& Vector3<T>::operator-=(const Vector3<T>& rhs)
{
  GetX() -= rhs.GetX();
  GetY() -= rhs.GetY();
  GetZ() -= rhs.GetZ();
  return *this;
}
 
template <typename T>
inline Vector3<T> Vector3<T>::CWiseMul(const Vector3<T>& rhs) const
{
  return Vector3<T>(GetX() * rhs.GetX(), GetY() * rhs.GetY(), GetZ() * rhs.GetZ());
}
 
template <typename T>
inline Vector3<T> Vector3<T>::Cross(const Vector3<T>& rhs) const
{
  return Vector3<T>(GetY() * rhs.GetZ() - GetZ() * rhs.GetY(),
                    GetZ() * rhs.GetX() - GetX() * rhs.GetZ(),
                    GetX() * rhs.GetY() - GetY() * rhs.GetX());
}
 
template <typename T>
inline T Vector3<T>::Dot(const Vector3<T>& rhs) const
{
  return GetX() * rhs.GetX() + GetY() * rhs.GetY() + GetZ() * rhs.GetZ();
}
 
template <typename T>
inline Vector3<T> Vector3<T>::operator+(const Vector3<T>& rhs) const
{
  return Vector3<T>(GetX() + rhs.GetX(), GetY() + rhs.GetY(), GetZ() + rhs.GetZ());
}
 
template <typename T>
inline Vector3<T> Vector3<T>::operator-(const Vector3<T>& rhs) const
{
  return Vector3<T>(GetX() - rhs.GetX(), GetY() - rhs.GetY(), GetZ() - rhs.GetZ());
}
 
template <typename T>
inline Vector3<T> operator*(T lhs, const Vector3<T>& rhs)
{
  return Vector3<T>(lhs * rhs.GetX(), lhs * rhs.GetY(), lhs * rhs.GetZ());
}
 
/*
 * Vector-scalar operations
 */
template <typename T>
inline Vector3<T>& Vector3<T>::operator-=(T a)
{
  GetX() -= a;
  GetY() -= a;
  GetZ() -= a;
  return *this;
}
 
template <typename T>
inline Vector3<T>& Vector3<T>::operator+=(T a)
{
  GetX() += a;
  GetY() += a;
  GetZ() += a;
  return *this;
}
 
template <typename T>
inline Vector3<T>& Vector3<T>::operator/=(T a)
{
  GetX() /= a;
  GetY() /= a;
  GetZ() /= a;
  return *this;
}
 
template <typename T>
inline Vector3<T>& Vector3<T>::operator*=(T a)
{
  GetX() *= a;
  GetY() *= a;
  GetZ() *= a;
  return *this;
}
 
template <typename T>
inline Vector3<T> Vector3<T>::operator*(T rhs) const
{
  return Vector3<T>(GetX() * rhs, GetY() * rhs, GetZ() * rhs);
}
 
template <typename T>
inline Vector3<T> Vector3<T>::operator/(T rhs) const
{
  return Vector3<T>(GetX() / rhs, GetY() / rhs, GetZ() / rhs);
}
 
/*
 * Unary operations
 */
template <typename T>
inline Vector3<T> Vector3<T>::operator-() const
{
  return Vector3<T>(-GetX(), -GetY(), -GetZ());
}
 
/*
 * Comparison operators
 */
template <typename T>
inline bool Vector3<T>::operator<(const Vector3<T>& rhs) const
{
  if (GetX() == rhs.GetX())
  {
    if (GetY() == rhs.GetY())
    {
      return (GetZ() < rhs.GetZ());
    }
    return (GetY() < rhs.GetY());
  }
  return (GetX() < rhs.GetX());
}
 
template <typename T>
inline bool Vector3<T>::operator>(const Vector3<T>& rhs) const
{
  if (GetX() == rhs.GetX())
  {
    if (GetY() == rhs.GetY())
    {
      return (GetZ() > rhs.GetZ());
    }
    return (GetY() > rhs.GetY());
  }
  return (GetX() > rhs.GetZ());
}
 
template <typename T>
inline bool Vector3<T>::CWiseAllGE(const Vector3<T>& rhs) const
{
  return GetX() >= rhs.GetX() && GetY() >= rhs.GetY() && GetZ() >= rhs.GetZ();
}
 
template <typename T>
inline bool Vector3<T>::CWiseAllLE(const Vector3<T>& rhs) const
{
  return GetX() <= rhs.GetX() && GetY() <= rhs.GetY() && GetZ() <= rhs.GetZ();
}
 
template <typename T>
inline Vector3<T> Vector3<T>::CWiseMin(const Vector3<T>& rhs) const
{
  return Vector3<T>(std::min(GetX(), rhs.GetX()), std::min(GetY(), rhs.GetY()), std::min(GetZ(), rhs.GetZ()));
}
 
template <typename T>
inline Vector3<T> Vector3<T>::CWiseMax(const Vector3<T>& rhs) const
{
  return Vector3<T>(std::max(GetX(), rhs.GetX()), std::max(GetY(), rhs.GetY()), std::max(GetZ(), rhs.GetZ()));
}
 
template <typename T>
inline T Vector3<T>::MinCoeff() const
{
  return *std::min_element(m_data.begin(), m_data.end());
}
 
template <typename T>
inline T Vector3<T>::MaxCoeff() const
{
  return *std::max_element(m_data.begin(), m_data.end());
}
 
template <typename T>
inline T Vector3<T>::MinCoeff(uint32_t& idx) const
{
  auto it = std::min_element(m_data.begin(), m_data.end());
  idx = uint32_t(std::distance(m_data.begin(), it));
  return *it;
}
 
template <typename T>
inline T Vector3<T>::MaxCoeff(uint32_t& idx) const
{
  auto it = std::max_element(m_data.begin(), m_data.end());
  idx = uint32_t(std::distance(m_data.begin(), it));
  return *it;
}
 
/*
 * Constructors
 */
template <typename T>
inline Vector3<T>::Vector3(T a) : m_data{ a, a, a }
{
}
 
template <typename T>
inline Vector3<T>::Vector3(T x, T y, T z) : m_data{ x, y, z }
{
}
 
template <typename T>
inline Vector3<T>::Vector3(const Vector3& rhs) : m_data{ rhs.m_data }
{
}
 
template <typename T>
template <typename U>
inline Vector3<T>::Vector3(const Vector3<U>& rhs) : m_data{ T(rhs.GetX()), T(rhs.GetY()), T(rhs.GetZ()) }
{
}
 
template <typename T>
inline Vector3<T>::Vector3(const VHACD::Vertex& rhs) : Vector3<T>(rhs.mX, rhs.mY, rhs.mZ)
{
  static_assert(std::is_same<T, double>::value, "Vertex to Vector3 constructor only enabled for double");
}
 
template <typename T>
inline Vector3<T>::Vector3(const VHACD::Triangle& rhs) : Vector3<T>(rhs.mI0, rhs.mI1, rhs.mI2)
{
  static_assert(std::is_same<T, uint32_t>::value, "Triangle to Vector3 constructor only enabled for uint32_t");
}
 
template <typename T>
inline Vector3<T>::operator VHACD::Vertex() const
{
  static_assert(std::is_same<T, double>::value, "Vector3 to Vertex conversion only enable for double");
  return ::VHACD::Vertex(GetX(), GetY(), GetZ());
}
 
IVHACD* CreateVHACD();        // Create a synchronous (blocking) implementation of V-HACD
IVHACD* CreateVHACD_ASYNC();  // Create an asynchronous (non-blocking) implementation of V-HACD
 
}  // namespace VHACD
 
#if ENABLE_VHACD_IMPLEMENTATION
#include <assert.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <float.h>
#include <limits.h>
 
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <deque>
#include <future>
#include <iostream>
#include <list>
#include <memory>
#include <mutex>
#include <queue>
#include <thread>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
 
#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable : 4100 4127 4189 4244 4456 4701 4702 4996)
#endif  // _MSC_VER
 
#ifdef __GNUC__
#pragma GCC diagnostic push
// Minimum set of warnings used for cleanup
// #pragma GCC diagnostic warning "-Wall"
// #pragma GCC diagnostic warning "-Wextra"
// #pragma GCC diagnostic warning "-Wpedantic"
// #pragma GCC diagnostic warning "-Wold-style-cast"
// #pragma GCC diagnostic warning "-Wnon-virtual-dtor"
// #pragma GCC diagnostic warning "-Wshadow"
#endif  // __GNUC__
 
// Scoped Timer
namespace VHACD
{
class Timer
{
public:
  Timer() : m_startTime(std::chrono::high_resolution_clock::now()) {}
 
  void Reset() { m_startTime = std::chrono::high_resolution_clock::now(); }
 
  double GetElapsedSeconds()
  {
    auto s = PeekElapsedSeconds();
    Reset();
    return s;
  }
 
  double PeekElapsedSeconds()
  {
    auto now = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> diff = now - m_startTime;
    return diff.count();
  }
 
private:
  std::chrono::time_point<std::chrono::high_resolution_clock> m_startTime;
};
 
class ScopedTime
{
public:
  ScopedTime(const char* action, VHACD::IVHACD::IUserLogger* logger) : m_action(action), m_logger(logger)
  {
    m_timer.Reset();
  }
 
  ~ScopedTime()
  {
    double dtime = m_timer.GetElapsedSeconds();
    if (m_logger)
    {
      char scratch[512];
      snprintf(scratch, sizeof(scratch), "%s took %0.5f seconds", m_action, dtime);
      m_logger->Log(scratch);
    }
  }
 
  const char* m_action{ nullptr };
  Timer m_timer;
  VHACD::IVHACD::IUserLogger* m_logger{ nullptr };
};
BoundsAABB::BoundsAABB(const std::vector<VHACD::Vertex>& points) : m_min(points[0]), m_max(points[0])
{
  for (uint32_t i = 1; i < points.size(); ++i)
  {
    const VHACD::Vertex& p = points[i];
    m_min = m_min.CWiseMin(p);
    m_max = m_max.CWiseMax(p);
  }
}
 
BoundsAABB::BoundsAABB(const VHACD::Vect3& min, const VHACD::Vect3& max) : m_min(min), m_max(max) {}
 
BoundsAABB BoundsAABB::Union(const BoundsAABB& b)
{
  return BoundsAABB(GetMin().CWiseMin(b.GetMin()), GetMax().CWiseMax(b.GetMax()));
}
 
bool VHACD::BoundsAABB::Intersects(const VHACD::BoundsAABB& b) const
{
  if ((GetMin().GetX() > b.GetMax().GetX()) || (b.GetMin().GetX() > GetMax().GetX()))
    return false;
  if ((GetMin().GetY() > b.GetMax().GetY()) || (b.GetMin().GetY() > GetMax().GetY()))
    return false;
  if ((GetMin().GetZ() > b.GetMax().GetZ()) || (b.GetMin().GetZ() > GetMax().GetZ()))
    return false;
  return true;
}
 
double BoundsAABB::SurfaceArea() const
{
  VHACD::Vect3 d = GetMax() - GetMin();
  return double(2.0) * (d.GetX() * d.GetY() + d.GetX() * d.GetZ() + d.GetY() * d.GetZ());
}
 
double VHACD::BoundsAABB::Volume() const
{
  VHACD::Vect3 d = GetMax() - GetMin();
  return d.GetX() * d.GetY() * d.GetZ();
}
 
BoundsAABB VHACD::BoundsAABB::Inflate(double ratio) const
{
  double inflate = (GetMin() - GetMax()).GetNorm() * double(0.5) * ratio;
  return BoundsAABB(GetMin() - inflate, GetMax() + inflate);
}
 
VHACD::Vect3 VHACD::BoundsAABB::ClosestPoint(const VHACD::Vect3& p) const
{
  return p.CWiseMax(GetMin()).CWiseMin(GetMax());
}
 
VHACD::Vect3& VHACD::BoundsAABB::GetMin() { return m_min; }
 
VHACD::Vect3& VHACD::BoundsAABB::GetMax() { return m_max; }
 
inline const VHACD::Vect3& VHACD::BoundsAABB::GetMin() const { return m_min; }
 
const VHACD::Vect3& VHACD::BoundsAABB::GetMax() const { return m_max; }
 
VHACD::Vect3 VHACD::BoundsAABB::GetSize() const { return GetMax() - GetMin(); }
 
VHACD::Vect3 VHACD::BoundsAABB::GetCenter() const { return (GetMin() + GetMax()) * double(0.5); }
 
/*
 * Relies on three way comparison, which std::sort doesn't use
 */
template <class T, class dCompareKey>
void Sort(T* const array, int elements)
{
  const int batchSize = 8;
  int stack[1024][2];
 
  stack[0][0] = 0;
  stack[0][1] = elements - 1;
  int stackIndex = 1;
  const dCompareKey comparator;
  while (stackIndex)
  {
    stackIndex--;
    int lo = stack[stackIndex][0];
    int hi = stack[stackIndex][1];
    if ((hi - lo) > batchSize)
    {
      int mid = (lo + hi) >> 1;
      if (comparator.Compare(array[lo], array[mid]) > 0)
      {
        std::swap(array[lo], array[mid]);
      }
      if (comparator.Compare(array[mid], array[hi]) > 0)
      {
        std::swap(array[mid], array[hi]);
      }
      if (comparator.Compare(array[lo], array[mid]) > 0)
      {
        std::swap(array[lo], array[mid]);
      }
      int i = lo + 1;
      int j = hi - 1;
      const T pivot(array[mid]);
      do
      {
        while (comparator.Compare(array[i], pivot) < 0)
        {
          i++;
        }
        while (comparator.Compare(array[j], pivot) > 0)
        {
          j--;
        }
 
        if (i <= j)
        {
          std::swap(array[i], array[j]);
          i++;
          j--;
        }
      } while (i <= j);
 
      if (i < hi)
      {
        stack[stackIndex][0] = i;
        stack[stackIndex][1] = hi;
        stackIndex++;
      }
      if (lo < j)
      {
        stack[stackIndex][0] = lo;
        stack[stackIndex][1] = j;
        stackIndex++;
      }
      assert(stackIndex < int(sizeof(stack) / (2 * sizeof(stack[0][0]))));
    }
  }
 
  int stride = batchSize + 1;
  if (elements < stride)
  {
    stride = elements;
  }
  for (int i = 1; i < stride; ++i)
  {
    if (comparator.Compare(array[0], array[i]) > 0)
    {
      std::swap(array[0], array[i]);
    }
  }
 
  for (int i = 1; i < elements; ++i)
  {
    int j = i;
    const T tmp(array[i]);
    for (; comparator.Compare(array[j - 1], tmp) > 0; --j)
    {
      assert(j > 0);
      array[j] = array[j - 1];
    }
    array[j] = tmp;
  }
}
 
/*
Maintaining comment due to attribution
Purpose:
 
TRIANGLE_AREA_3D computes the area of a triangle in 3D.
 
Modified:
 
22 April 1999
 
Author:
 
John Burkardt
 
Parameters:
 
Input, double X1, Y1, Z1, X2, Y2, Z2, X3, Y3, Z3, the (getX,getY,getZ)
coordinates of the corners of the triangle.
 
Output, double TRIANGLE_AREA_3D, the area of the triangle.
*/
double ComputeArea(const VHACD::Vect3& p1, const VHACD::Vect3& p2, const VHACD::Vect3& p3)
{
  /*
  Find the projection of (P3-P1) onto (P2-P1).
  */
  double base = (p2 - p1).GetNorm();
  /*
  The height of the triangle is the length of (P3-P1) after its
  projection onto (P2-P1) has been subtracted.
  */
  double height;
  if (base == double(0.0))
  {
    height = double(0.0);
  }
  else
  {
    double dot = (p3 - p1).Dot(p2 - p1);
    double alpha = dot / (base * base);
 
    VHACD::Vect3 a = p3 - p1 - alpha * (p2 - p1);
    height = a.GetNorm();
  }
 
  return double(0.5) * base * height;
}
 
bool ComputeCentroid(const std::vector<VHACD::Vertex>& points,
                     const std::vector<VHACD::Triangle>& indices,
                     VHACD::Vect3& center)
 
{
  bool ret = false;
  if (points.size())
  {
    center = VHACD::Vect3(0);
 
    VHACD::Vect3 numerator(0);
    double denominator = 0;
 
    for (uint32_t i = 0; i < indices.size(); i++)
    {
      uint32_t i1 = indices[i].mI0;
      uint32_t i2 = indices[i].mI1;
      uint32_t i3 = indices[i].mI2;
 
      const VHACD::Vect3& p1 = points[i1];
      const VHACD::Vect3& p2 = points[i2];
      const VHACD::Vect3& p3 = points[i3];
 
      // Compute the average of the sum of the three positions
      VHACD::Vect3 sum = (p1 + p2 + p3) / 3;
 
      // Compute the area of this triangle
      double area = ComputeArea(p1, p2, p3);
 
      numerator += (sum * area);
 
      denominator += area;
    }
    double recip = 1 / denominator;
    center = numerator * recip;
    ret = true;
  }
  return ret;
}
 
double Determinant3x3(const std::array<VHACD::Vect3, 3>& matrix, double& error)
{
  double det = double(0.0);
  error = double(0.0);
 
  double a01xa12 = matrix[0].GetY() * matrix[1].GetZ();
  double a02xa11 = matrix[0].GetZ() * matrix[1].GetY();
  error += (std::abs(a01xa12) + std::abs(a02xa11)) * std::abs(matrix[2].GetX());
  det += (a01xa12 - a02xa11) * matrix[2].GetX();
 
  double a00xa12 = matrix[0].GetX() * matrix[1].GetZ();
  double a02xa10 = matrix[0].GetZ() * matrix[1].GetX();
  error += (std::abs(a00xa12) + std::abs(a02xa10)) * std::abs(matrix[2].GetY());
  det -= (a00xa12 - a02xa10) * matrix[2].GetY();
 
  double a00xa11 = matrix[0].GetX() * matrix[1].GetY();
  double a01xa10 = matrix[0].GetY() * matrix[1].GetX();
  error += (std::abs(a00xa11) + std::abs(a01xa10)) * std::abs(matrix[2].GetZ());
  det += (a00xa11 - a01xa10) * matrix[2].GetZ();
 
  return det;
}
 
double ComputeMeshVolume(const std::vector<VHACD::Vertex>& vertices, const std::vector<VHACD::Triangle>& indices)
{
  double volume = 0;
  for (uint32_t i = 0; i < indices.size(); i++)
  {
    const std::array<VHACD::Vect3, 3> m = { vertices[indices[i].mI0],
                                            vertices[indices[i].mI1],
                                            vertices[indices[i].mI2] };
    double placeholder;
    volume += Determinant3x3(m, placeholder);
  }
 
  volume *= (double(1.0) / double(6.0));
  if (volume < 0)
    volume *= -1;
  return volume;
}
 
/*
 * To minimize memory allocations while maintaining pointer stability.
 * Used in KdTreeNode and ConvexHull, as both use tree data structures that rely on pointer stability
 * Neither rely on random access or iteration
 * They just dump elements into a memory pool, then refer to pointers to the elements
 * All elements are default constructed in NodeStorage's m_nodes array
 */
template <typename T, std::size_t MaxBundleSize = 1024>
class NodeBundle
{
  struct NodeStorage
  {
    bool IsFull() const;
 
    T& GetNextNode();
 
    std::size_t m_index;
    std::array<T, MaxBundleSize> m_nodes;
  };
 
  std::list<NodeStorage> m_list;
  typename std::list<NodeStorage>::iterator m_head{ m_list.end() };
 
public:
  T& GetNextNode();
 
  T& GetFirstNode();
 
  void Clear();
};
 
template <typename T, std::size_t MaxBundleSize>
bool NodeBundle<T, MaxBundleSize>::NodeStorage::IsFull() const
{
  return m_index == MaxBundleSize;
}
 
template <typename T, std::size_t MaxBundleSize>
T& NodeBundle<T, MaxBundleSize>::NodeStorage::GetNextNode()
{
  assert(m_index < MaxBundleSize);
  T& ret = m_nodes[m_index];
  m_index++;
  return ret;
}
 
template <typename T, std::size_t MaxBundleSize>
T& NodeBundle<T, MaxBundleSize>::GetNextNode()
{
  /*
   * || short circuits, so doesn't dereference if m_bundle == m_bundleHead.end()
   */
  if (m_head == m_list.end() || m_head->IsFull())
  {
    m_head = m_list.emplace(m_list.end());
  }
 
  return m_head->GetNextNode();
}
 
template <typename T, std::size_t MaxBundleSize>
T& NodeBundle<T, MaxBundleSize>::GetFirstNode()
{
  assert(m_head != m_list.end());
  return m_list.front().m_nodes[0];
}
 
template <typename T, std::size_t MaxBundleSize>
void NodeBundle<T, MaxBundleSize>::Clear()
{
  m_list.clear();
}
 
/*
 * Returns index of highest set bit in x
 */
inline int dExp2(int x)
{
  int exp;
  for (exp = -1; x; x >>= 1)
  {
    exp++;
  }
  return exp;
}
 
/*
 * Reverses the order of the bits in v and returns the result
 * Does not put fill any of the bits higher than the highest bit in v
 * Only used to calculate index of ndNormalMap::m_normal when tessellating a triangle
 */
inline int dBitReversal(int v, int base)
{
  int x = 0;
  int power = dExp2(base) - 1;
  do
  {
    x += (v & 1) << power;
    v >>= 1;
    power--;
  } while (v);
  return x;
}
 
class Googol
{
#define VHACD_GOOGOL_SIZE 4
public:
  Googol() = default;
  Googol(double value);
 
  operator double() const;
  Googol operator+(const Googol& A) const;
  Googol operator-(const Googol& A) const;
  Googol operator*(const Googol& A) const;
  Googol operator/(const Googol& A) const;
 
  Googol& operator+=(const Googol& A);
  Googol& operator-=(const Googol& A);
 
  bool operator>(const Googol& A) const;
  bool operator>=(const Googol& A) const;
  bool operator<(const Googol& A) const;
  bool operator<=(const Googol& A) const;
  bool operator==(const Googol& A) const;
  bool operator!=(const Googol& A) const;
 
  Googol Abs() const;
  Googol Floor() const;
  Googol InvSqrt() const;
  Googol Sqrt() const;
 
  void ToString(char* const string) const;
 
private:
  void NegateMantissa(std::array<uint64_t, VHACD_GOOGOL_SIZE>& mantissa) const;
  void CopySignedMantissa(std::array<uint64_t, VHACD_GOOGOL_SIZE>& mantissa) const;
  int NormalizeMantissa(std::array<uint64_t, VHACD_GOOGOL_SIZE>& mantissa) const;
  void ShiftRightMantissa(std::array<uint64_t, VHACD_GOOGOL_SIZE>& mantissa, int bits) const;
  uint64_t CheckCarrier(uint64_t a, uint64_t b) const;
 
  int LeadingZeros(uint64_t a) const;
  void ExtendedMultiply(uint64_t a, uint64_t b, uint64_t& high, uint64_t& low) const;
  void ScaleMantissa(uint64_t* out, uint64_t scale) const;
 
  int m_sign{ 0 };
  int m_exponent{ 0 };
  std::array<uint64_t, VHACD_GOOGOL_SIZE> m_mantissa{ 0 };
 
public:
  static Googol m_zero;
  static Googol m_one;
  static Googol m_two;
  static Googol m_three;
  static Googol m_half;
};
 
Googol Googol::m_zero(double(0.0));
Googol Googol::m_one(double(1.0));
Googol Googol::m_two(double(2.0));
Googol Googol::m_three(double(3.0));
Googol Googol::m_half(double(0.5));
 
Googol::Googol(double value)
{
  int exp;
  double mantissa = fabs(frexp(value, &exp));
 
  m_exponent = exp;
  m_sign = (value >= 0) ? 0 : 1;
 
  m_mantissa[0] = uint64_t(double(uint64_t(1) << 62) * mantissa);
}
 
Googol::operator double() const
{
  double mantissa = (double(1.0) / double(uint64_t(1) << 62)) * double(m_mantissa[0]);
  mantissa = ldexp(mantissa, m_exponent) * (m_sign ? double(-1.0) : double(1.0));
  return mantissa;
}
 
Googol Googol::operator+(const Googol& A) const
{
  Googol tmp;
  if (m_mantissa[0] && A.m_mantissa[0])
  {
    std::array<uint64_t, VHACD_GOOGOL_SIZE> mantissa0;
    std::array<uint64_t, VHACD_GOOGOL_SIZE> mantissa1;
    std::array<uint64_t, VHACD_GOOGOL_SIZE> mantissa;
 
    CopySignedMantissa(mantissa0);
    A.CopySignedMantissa(mantissa1);
 
    int exponentDiff = m_exponent - A.m_exponent;
    int exponent = m_exponent;
    if (exponentDiff > 0)
    {
      ShiftRightMantissa(mantissa1, exponentDiff);
    }
    else if (exponentDiff < 0)
    {
      exponent = A.m_exponent;
      ShiftRightMantissa(mantissa0, -exponentDiff);
    }
 
    uint64_t carrier = 0;
    for (int i = VHACD_GOOGOL_SIZE - 1; i >= 0; i--)
    {
      uint64_t m0 = mantissa0[i];
      uint64_t m1 = mantissa1[i];
      mantissa[i] = m0 + m1 + carrier;
      carrier = CheckCarrier(m0, m1) | CheckCarrier(m0 + m1, carrier);
    }
 
    int sign = 0;
    if (int64_t(mantissa[0]) < 0)
    {
      sign = 1;
      NegateMantissa(mantissa);
    }
 
    int bits = NormalizeMantissa(mantissa);
    if (bits <= (-64 * VHACD_GOOGOL_SIZE))
    {
      tmp.m_sign = 0;
      tmp.m_exponent = 0;
    }
    else
    {
      tmp.m_sign = sign;
      tmp.m_exponent = int(exponent + bits);
    }
 
    tmp.m_mantissa = mantissa;
  }
  else if (A.m_mantissa[0])
  {
    tmp = A;
  }
  else
  {
    tmp = *this;
  }
 
  return tmp;
}
 
Googol Googol::operator-(const Googol& A) const
{
  Googol tmp(A);
  tmp.m_sign = !tmp.m_sign;
  return *this + tmp;
}
 
Googol Googol::operator*(const Googol& A) const
{
  if (m_mantissa[0] && A.m_mantissa[0])
  {
    std::array<uint64_t, VHACD_GOOGOL_SIZE * 2> mantissaAcc{ 0 };
    for (int i = VHACD_GOOGOL_SIZE - 1; i >= 0; i--)
    {
      uint64_t a = m_mantissa[i];
      if (a)
      {
        uint64_t mantissaScale[2 * VHACD_GOOGOL_SIZE] = { 0 };
        A.ScaleMantissa(&mantissaScale[i], a);
 
        uint64_t carrier = 0;
        for (int j = 0; j < 2 * VHACD_GOOGOL_SIZE; j++)
        {
          const int k = 2 * VHACD_GOOGOL_SIZE - 1 - j;
          uint64_t m0 = mantissaAcc[k];
          uint64_t m1 = mantissaScale[k];
          mantissaAcc[k] = m0 + m1 + carrier;
          carrier = CheckCarrier(m0, m1) | CheckCarrier(m0 + m1, carrier);
        }
      }
    }
 
    uint64_t carrier = 0;
    int bits = LeadingZeros(mantissaAcc[0]) - 2;
    for (int i = 0; i < 2 * VHACD_GOOGOL_SIZE; i++)
    {
      const int k = 2 * VHACD_GOOGOL_SIZE - 1 - i;
      uint64_t a = mantissaAcc[k];
      mantissaAcc[k] = (a << uint64_t(bits)) | carrier;
      carrier = a >> uint64_t(64 - bits);
    }
 
    int exp = m_exponent + A.m_exponent - (bits - 2);
 
    Googol tmp;
    tmp.m_sign = m_sign ^ A.m_sign;
    tmp.m_exponent = exp;
    for (std::size_t i = 0; i < tmp.m_mantissa.size(); ++i)
    {
      tmp.m_mantissa[i] = mantissaAcc[i];
    }
 
    return tmp;
  }
  return Googol(double(0.0));
}
 
Googol Googol::operator/(const Googol& A) const
{
  Googol tmp(double(1.0) / A);
  tmp = tmp * (m_two - A * tmp);
  tmp = tmp * (m_two - A * tmp);
  bool test = false;
  int passes = 0;
  do
  {
    passes++;
    Googol tmp0(tmp);
    tmp = tmp * (m_two - A * tmp);
    test = tmp0 == tmp;
  } while (test && (passes < (2 * VHACD_GOOGOL_SIZE)));
  return (*this) * tmp;
}
 
Googol& Googol::operator+=(const Googol& A)
{
  *this = *this + A;
  return *this;
}
 
Googol& Googol::operator-=(const Googol& A)
{
  *this = *this - A;
  return *this;
}
 
bool Googol::operator>(const Googol& A) const
{
  Googol tmp(*this - A);
  return double(tmp) > double(0.0);
}
 
bool Googol::operator>=(const Googol& A) const
{
  Googol tmp(*this - A);
  return double(tmp) >= double(0.0);
}
 
bool Googol::operator<(const Googol& A) const
{
  Googol tmp(*this - A);
  return double(tmp) < double(0.0);
}
 
bool Googol::operator<=(const Googol& A) const
{
  Googol tmp(*this - A);
  return double(tmp) <= double(0.0);
}
 
bool Googol::operator==(const Googol& A) const
{
  return m_sign == A.m_sign && m_exponent == A.m_exponent && m_mantissa == A.m_mantissa;
}
 
bool Googol::operator!=(const Googol& A) const { return !(*this == A); }
 
Googol Googol::Abs() const
{
  Googol tmp(*this);
  tmp.m_sign = 0;
  return tmp;
}
 
Googol Googol::Floor() const
{
  if (m_exponent < 1)
  {
    return Googol(double(0.0));
  }
  int bits = m_exponent + 2;
  int start = 0;
  while (bits >= 64)
  {
    bits -= 64;
    start++;
  }
 
  Googol tmp(*this);
  for (int i = VHACD_GOOGOL_SIZE - 1; i > start; i--)
  {
    tmp.m_mantissa[i] = 0;
  }
  // some compilers do no like this and I do not know why is that
  // uint64_t mask = (-1LL) << (64 - bits);
  uint64_t mask(~0ULL);
  mask <<= (64 - bits);
  tmp.m_mantissa[start] &= mask;
  return tmp;
}
 
Googol Googol::InvSqrt() const
{
  const Googol& me = *this;
  Googol x(double(1.0) / sqrt(me));
 
  int test = 0;
  int passes = 0;
  do
  {
    passes++;
    Googol tmp(x);
    x = m_half * x * (m_three - me * x * x);
    test = (x != tmp);
  } while (test && (passes < (2 * VHACD_GOOGOL_SIZE)));
  return x;
}
 
Googol Googol::Sqrt() const { return *this * InvSqrt(); }
 
void Googol::ToString(char* const string) const
{
  Googol tmp(*this);
  Googol base(double(10.0));
  while (double(tmp) > double(1.0))
  {
    tmp = tmp / base;
  }
 
  int index = 0;
  while (tmp.m_mantissa[0])
  {
    tmp = tmp * base;
    Googol digit(tmp.Floor());
    tmp -= digit;
    double val = digit;
    string[index] = char(val) + '0';
    index++;
  }
  string[index] = 0;
}
 
void Googol::NegateMantissa(std::array<uint64_t, VHACD_GOOGOL_SIZE>& mantissa) const
{
  uint64_t carrier = 1;
  for (size_t i = mantissa.size() - 1; i < mantissa.size(); i--)
  {
    uint64_t a = ~mantissa[i] + carrier;
    if (a)
    {
      carrier = 0;
    }
    mantissa[i] = a;
  }
}
 
void Googol::CopySignedMantissa(std::array<uint64_t, VHACD_GOOGOL_SIZE>& mantissa) const
{
  mantissa = m_mantissa;
  if (m_sign)
  {
    NegateMantissa(mantissa);
  }
}
 
int Googol::NormalizeMantissa(std::array<uint64_t, VHACD_GOOGOL_SIZE>& mantissa) const
{
  int bits = 0;
  if (int64_t(mantissa[0] * 2) < 0)
  {
    bits = 1;
    ShiftRightMantissa(mantissa, 1);
  }
  else
  {
    while (!mantissa[0] && bits > (-64 * VHACD_GOOGOL_SIZE))
    {
      bits -= 64;
      for (int i = 1; i < VHACD_GOOGOL_SIZE; i++)
      {
        mantissa[i - 1] = mantissa[i];
      }
      mantissa[VHACD_GOOGOL_SIZE - 1] = 0;
    }
 
    if (bits > (-64 * VHACD_GOOGOL_SIZE))
    {
      int n = LeadingZeros(mantissa[0]) - 2;
      if (n > 0)
      {
        uint64_t carrier = 0;
        for (int i = VHACD_GOOGOL_SIZE - 1; i >= 0; i--)
        {
          uint64_t a = mantissa[i];
          mantissa[i] = (a << n) | carrier;
          carrier = a >> (64 - n);
        }
        bits -= n;
      }
      else if (n < 0)
      {
        // this is very rare but it does happens, whee the leading zeros of the mantissa is an exact multiple of 64
        uint64_t carrier = 0;
        int shift = -n;
        for (int i = 0; i < VHACD_GOOGOL_SIZE; i++)
        {
          uint64_t a = mantissa[i];
          mantissa[i] = (a >> shift) | carrier;
          carrier = a << (64 - shift);
        }
        bits -= n;
      }
    }
  }
  return bits;
}
 
void Googol::ShiftRightMantissa(std::array<uint64_t, VHACD_GOOGOL_SIZE>& mantissa, int bits) const
{
  uint64_t carrier = 0;
  if (int64_t(mantissa[0]) < int64_t(0))
  {
    carrier = uint64_t(-1);
  }
 
  while (bits >= 64)
  {
    for (int i = VHACD_GOOGOL_SIZE - 2; i >= 0; i--)
    {
      mantissa[i + 1] = mantissa[i];
    }
    mantissa[0] = carrier;
    bits -= 64;
  }
 
  if (bits > 0)
  {
    carrier <<= (64 - bits);
    for (int i = 0; i < VHACD_GOOGOL_SIZE; i++)
    {
      uint64_t a = mantissa[i];
      mantissa[i] = (a >> bits) | carrier;
      carrier = a << (64 - bits);
    }
  }
}
 
uint64_t Googol::CheckCarrier(uint64_t a, uint64_t b) const { return ((uint64_t(-1) - b) < a) ? uint64_t(1) : 0; }
 
int Googol::LeadingZeros(uint64_t a) const
{
#define VHACD_COUNTBIT(mask, add)                                                                                      \
  do                                                                                                                   \
  {                                                                                                                    \
    uint64_t test = a & mask;                                                                                          \
    n += test ? 0 : add;                                                                                               \
    a = test ? test : (a & ~mask);                                                                                     \
  } while (false)
 
  int n = 0;
  VHACD_COUNTBIT(0xffffffff00000000LL, 32);
  VHACD_COUNTBIT(0xffff0000ffff0000LL, 16);
  VHACD_COUNTBIT(0xff00ff00ff00ff00LL, 8);
  VHACD_COUNTBIT(0xf0f0f0f0f0f0f0f0LL, 4);
  VHACD_COUNTBIT(0xccccccccccccccccLL, 2);
  VHACD_COUNTBIT(0xaaaaaaaaaaaaaaaaLL, 1);
 
  return n;
}
 
void Googol::ExtendedMultiply(uint64_t a, uint64_t b, uint64_t& high, uint64_t& low) const
{
  uint64_t bLow = b & 0xffffffff;
  uint64_t bHigh = b >> 32;
  uint64_t aLow = a & 0xffffffff;
  uint64_t aHigh = a >> 32;
 
  uint64_t l = bLow * aLow;
 
  uint64_t c1 = bHigh * aLow;
  uint64_t c2 = bLow * aHigh;
  uint64_t m = c1 + c2;
  uint64_t carrier = CheckCarrier(c1, c2) << 32;
 
  uint64_t h = bHigh * aHigh + carrier;
 
  uint64_t ml = m << 32;
  uint64_t ll = l + ml;
  uint64_t mh = (m >> 32) + CheckCarrier(l, ml);
  uint64_t hh = h + mh;
 
  low = ll;
  high = hh;
}
 
void Googol::ScaleMantissa(uint64_t* dst, uint64_t scale) const
{
  uint64_t carrier = 0;
  for (int i = VHACD_GOOGOL_SIZE - 1; i >= 0; i--)
  {
    if (m_mantissa[i])
    {
      uint64_t low;
      uint64_t high;
      ExtendedMultiply(scale, m_mantissa[i], high, low);
      uint64_t acc = low + carrier;
      carrier = CheckCarrier(low, carrier);
      carrier += high;
      dst[i + 1] = acc;
    }
    else
    {
      dst[i + 1] = carrier;
      carrier = 0;
    }
  }
  dst[0] = carrier;
}
 
Googol Determinant3x3(const std::array<VHACD::Vector3<Googol>, 3>& matrix)
{
  Googol det = double(0.0);
 
  Googol a01xa12 = matrix[0].GetY() * matrix[1].GetZ();
  Googol a02xa11 = matrix[0].GetZ() * matrix[1].GetY();
  det += (a01xa12 - a02xa11) * matrix[2].GetX();
 
  Googol a00xa12 = matrix[0].GetX() * matrix[1].GetZ();
  Googol a02xa10 = matrix[0].GetZ() * matrix[1].GetX();
  det -= (a00xa12 - a02xa10) * matrix[2].GetY();
 
  Googol a00xa11 = matrix[0].GetX() * matrix[1].GetY();
  Googol a01xa10 = matrix[0].GetY() * matrix[1].GetX();
  det += (a00xa11 - a01xa10) * matrix[2].GetZ();
  return det;
}
 
class HullPlane : public VHACD::Vect3
{
public:
  HullPlane(const HullPlane&) = default;
  HullPlane(double x, double y, double z, double w);
 
  HullPlane(const VHACD::Vect3& p, double w);
 
  HullPlane(const VHACD::Vect3& p0, const VHACD::Vect3& p1, const VHACD::Vect3& p2);
 
  HullPlane Scale(double s) const;
 
  HullPlane& operator=(const HullPlane& rhs);
 
  double Evalue(const VHACD::Vect3& point) const;
 
  double& GetW();
  const double& GetW() const;
 
private:
  double m_w;
};
 
HullPlane::HullPlane(double x, double y, double z, double w) : VHACD::Vect3(x, y, z), m_w(w) {}
 
HullPlane::HullPlane(const VHACD::Vect3& p, double w) : VHACD::Vect3(p), m_w(w) {}
 
HullPlane::HullPlane(const VHACD::Vect3& p0, const VHACD::Vect3& p1, const VHACD::Vect3& p2)
  : VHACD::Vect3((p1 - p0).Cross(p2 - p0)), m_w(-Dot(p0))
{
}
 
HullPlane HullPlane::Scale(double s) const { return HullPlane(*this * s, m_w * s); }
 
HullPlane& HullPlane::operator=(const HullPlane& rhs)
{
  GetX() = rhs.GetX();
  GetY() = rhs.GetY();
  GetZ() = rhs.GetZ();
  m_w = rhs.m_w;
  return *this;
}
 
double HullPlane::Evalue(const VHACD::Vect3& point) const { return Dot(point) + m_w; }
 
double& HullPlane::GetW() { return m_w; }
 
const double& HullPlane::GetW() const { return m_w; }
 
class ConvexHullFace
{
public:
  ConvexHullFace() = default;
  double Evalue(const std::vector<VHACD::Vect3>& pointArray, const VHACD::Vect3& point) const;
  HullPlane GetPlaneEquation(const std::vector<VHACD::Vect3>& pointArray, bool& isValid) const;
 
  std::array<int, 3> m_index;
 
private:
  int m_mark{ 0 };
  std::array<std::list<ConvexHullFace>::iterator, 3> m_twin;
 
  friend class ConvexHull;
};
 
double ConvexHullFace::Evalue(const std::vector<VHACD::Vect3>& pointArray, const VHACD::Vect3& point) const
{
  const VHACD::Vect3& p0 = pointArray[m_index[0]];
  const VHACD::Vect3& p1 = pointArray[m_index[1]];
  const VHACD::Vect3& p2 = pointArray[m_index[2]];
 
  std::array<VHACD::Vect3, 3> matrix = { p2 - p0, p1 - p0, point - p0 };
  double error;
  double det = Determinant3x3(matrix, error);
 
  // the code use double, however the threshold for accuracy test is the machine precision of a float.
  // by changing this to a smaller number, the code should run faster since many small test will be considered valid
  // the precision must be a power of two no smaller than the machine precision of a double, (1<<48)
  // float64(1<<30) can be a good value
 
  // double precision   = double (1.0f) / double (1<<30);
  double precision = double(1.0) / double(1 << 24);
  double errbound = error * precision;
  if (fabs(det) > errbound)
  {
    return det;
  }
 
  const VHACD::Vector3<Googol> p0g = pointArray[m_index[0]];
  const VHACD::Vector3<Googol> p1g = pointArray[m_index[1]];
  const VHACD::Vector3<Googol> p2g = pointArray[m_index[2]];
  const VHACD::Vector3<Googol> pointg = point;
  std::array<VHACD::Vector3<Googol>, 3> exactMatrix = { p2g - p0g, p1g - p0g, pointg - p0g };
  return Determinant3x3(exactMatrix);
}
 
HullPlane ConvexHullFace::GetPlaneEquation(const std::vector<VHACD::Vect3>& pointArray, bool& isvalid) const
{
  const VHACD::Vect3& p0 = pointArray[m_index[0]];
  const VHACD::Vect3& p1 = pointArray[m_index[1]];
  const VHACD::Vect3& p2 = pointArray[m_index[2]];
  HullPlane plane(p0, p1, p2);
 
  isvalid = false;
  double mag2 = plane.Dot(plane);
  if (mag2 > double(1.0e-16))
  {
    isvalid = true;
    plane = plane.Scale(double(1.0) / sqrt(mag2));
  }
  return plane;
}
 
class ConvexHullVertex : public VHACD::Vect3
{
public:
  ConvexHullVertex() = default;
  ConvexHullVertex(const ConvexHullVertex&) = default;
  ConvexHullVertex& operator=(const ConvexHullVertex& rhs) = default;
  using VHACD::Vect3::operator=;
 
  int m_mark{ 0 };
};
 
class ConvexHullAABBTreeNode
{
#define VHACD_CONVEXHULL_3D_VERTEX_CLUSTER_SIZE 8
public:
  ConvexHullAABBTreeNode() = default;
  ConvexHullAABBTreeNode(ConvexHullAABBTreeNode* parent);
 
  VHACD::Vect3 m_box[2];
  ConvexHullAABBTreeNode* m_left{ nullptr };
  ConvexHullAABBTreeNode* m_right{ nullptr };
  ConvexHullAABBTreeNode* m_parent{ nullptr };
 
  size_t m_count;
  std::array<size_t, VHACD_CONVEXHULL_3D_VERTEX_CLUSTER_SIZE> m_indices;
};
 
ConvexHullAABBTreeNode::ConvexHullAABBTreeNode(ConvexHullAABBTreeNode* parent) : m_parent(parent) {}
 
class ConvexHull
{
  class ndNormalMap;
 
public:
  ConvexHull(const ConvexHull& source);
  ConvexHull(const std::vector<::VHACD::Vertex>& vertexCloud, double distTol, int maxVertexCount = 0x7fffffff);
  ~ConvexHull() = default;
 
  const std::vector<VHACD::Vect3>& GetVertexPool() const;
 
  const std::list<ConvexHullFace>& GetList() const { return m_list; }
 
private:
  void BuildHull(const std::vector<::VHACD::Vertex>& vertexCloud, double distTol, int maxVertexCount);
 
  void GetUniquePoints(std::vector<ConvexHullVertex>& points);
  int InitVertexArray(std::vector<ConvexHullVertex>& points, NodeBundle<ConvexHullAABBTreeNode>& memoryPool);
 
  ConvexHullAABBTreeNode* BuildTreeNew(std::vector<ConvexHullVertex>& points,
                                       std::vector<ConvexHullAABBTreeNode>& memoryPool) const;
  ConvexHullAABBTreeNode* BuildTreeOld(std::vector<ConvexHullVertex>& points,
                                       NodeBundle<ConvexHullAABBTreeNode>& memoryPool);
  ConvexHullAABBTreeNode* BuildTreeRecurse(ConvexHullAABBTreeNode* const parent,
                                           ConvexHullVertex* const points,
                                           int count,
                                           int baseIndex,
                                           NodeBundle<ConvexHullAABBTreeNode>& memoryPool) const;
 
  std::list<ConvexHullFace>::iterator AddFace(int i0, int i1, int i2);
 
  void CalculateConvexHull3D(ConvexHullAABBTreeNode* vertexTree,
                             std::vector<ConvexHullVertex>& points,
                             int count,
                             double distTol,
                             int maxVertexCount);
 
  int SupportVertex(ConvexHullAABBTreeNode** const tree,
                    const std::vector<ConvexHullVertex>& points,
                    const VHACD::Vect3& dir,
                    const bool removeEntry = true) const;
  double TetrahedrumVolume(const VHACD::Vect3& p0,
                           const VHACD::Vect3& p1,
                           const VHACD::Vect3& p2,
                           const VHACD::Vect3& p3) const;
 
  std::list<ConvexHullFace> m_list;
  VHACD::Vect3 m_aabbP0{ 0 };
  VHACD::Vect3 m_aabbP1{ 0 };
  double m_diag{ 0.0 };
  std::vector<VHACD::Vect3> m_points;
};
 
class ConvexHull::ndNormalMap
{
public:
  ndNormalMap();
 
  static const ndNormalMap& GetNormalMap();
 
  void
  TessellateTriangle(int level, const VHACD::Vect3& p0, const VHACD::Vect3& p1, const VHACD::Vect3& p2, int& count);
 
  std::array<VHACD::Vect3, 128> m_normal;
  int m_count{ 128 };
};
 
const ConvexHull::ndNormalMap& ConvexHull::ndNormalMap::GetNormalMap()
{
  static ndNormalMap normalMap;
  return normalMap;
}
 
void ConvexHull::ndNormalMap::TessellateTriangle(int level,
                                                 const VHACD::Vect3& p0,
                                                 const VHACD::Vect3& p1,
                                                 const VHACD::Vect3& p2,
                                                 int& count)
{
  if (level)
  {
    assert(fabs(p0.Dot(p0) - double(1.0)) < double(1.0e-4));
    assert(fabs(p1.Dot(p1) - double(1.0)) < double(1.0e-4));
    assert(fabs(p2.Dot(p2) - double(1.0)) < double(1.0e-4));
    VHACD::Vect3 p01(p0 + p1);
    VHACD::Vect3 p12(p1 + p2);
    VHACD::Vect3 p20(p2 + p0);
 
    p01 = p01 * (double(1.0) / p01.GetNorm());
    p12 = p12 * (double(1.0) / p12.GetNorm());
    p20 = p20 * (double(1.0) / p20.GetNorm());
 
    assert(fabs(p01.GetNormSquared() - double(1.0)) < double(1.0e-4));
    assert(fabs(p12.GetNormSquared() - double(1.0)) < double(1.0e-4));
    assert(fabs(p20.GetNormSquared() - double(1.0)) < double(1.0e-4));
 
    TessellateTriangle(level - 1, p0, p01, p20, count);
    TessellateTriangle(level - 1, p1, p12, p01, count);
    TessellateTriangle(level - 1, p2, p20, p12, count);
    TessellateTriangle(level - 1, p01, p12, p20, count);
  }
  else
  {
    /*
     * This is just m_normal[index] = n.Normalized(), but due to tiny floating point errors, causes
     * different outputs, so I'm leaving it
     */
    HullPlane n(p0, p1, p2);
    n = n.Scale(double(1.0) / n.GetNorm());
    n.GetW() = double(0.0);
    int index = dBitReversal(count, int(m_normal.size()));
    m_normal[index] = n;
    count++;
    assert(count <= int(m_normal.size()));
  }
}
 
ConvexHull::ndNormalMap::ndNormalMap()
{
  VHACD::Vect3 p0(double(1.0), double(0.0), double(0.0));
  VHACD::Vect3 p1(double(-1.0), double(0.0), double(0.0));
  VHACD::Vect3 p2(double(0.0), double(1.0), double(0.0));
  VHACD::Vect3 p3(double(0.0), double(-1.0), double(0.0));
  VHACD::Vect3 p4(double(0.0), double(0.0), double(1.0));
  VHACD::Vect3 p5(double(0.0), double(0.0), double(-1.0));
 
  int count = 0;
  int subdivisions = 2;
  TessellateTriangle(subdivisions, p4, p0, p2, count);
  TessellateTriangle(subdivisions, p0, p5, p2, count);
  TessellateTriangle(subdivisions, p5, p1, p2, count);
  TessellateTriangle(subdivisions, p1, p4, p2, count);
  TessellateTriangle(subdivisions, p0, p4, p3, count);
  TessellateTriangle(subdivisions, p5, p0, p3, count);
  TessellateTriangle(subdivisions, p1, p5, p3, count);
  TessellateTriangle(subdivisions, p4, p1, p3, count);
}
 
ConvexHull::ConvexHull(const std::vector<::VHACD::Vertex>& vertexCloud, double distTol, int maxVertexCount)
{
  if (vertexCloud.size() >= 4)
  {
    BuildHull(vertexCloud, distTol, maxVertexCount);
  }
}
 
const std::vector<VHACD::Vect3>& ConvexHull::GetVertexPool() const { return m_points; }
 
void ConvexHull::BuildHull(const std::vector<::VHACD::Vertex>& vertexCloud, double distTol, int maxVertexCount)
{
  size_t treeCount = vertexCloud.size() / (VHACD_CONVEXHULL_3D_VERTEX_CLUSTER_SIZE >> 1);
  treeCount = std::max(treeCount, size_t(4)) * 2;
 
  std::vector<ConvexHullVertex> points(vertexCloud.size());
  /*
   * treePool provides a memory pool for the AABB tree
   * Each node is either a leaf or non-leaf node
   * Non-leaf nodes have up to 8 vertices
   * Vertices are specified by the m_indices array and are accessed via the points array
   *
   * Later on in ConvexHull::SupportVertex, the tree is used directly
   * It differentiates between ConvexHullAABBTreeNode and ConvexHull3DPointCluster by whether the m_left and m_right
   * pointers are null or not
   *
   * Pointers have to be stable
   */
  NodeBundle<ConvexHullAABBTreeNode> treePool;
  for (size_t i = 0; i < vertexCloud.size(); ++i)
  {
    points[i] = VHACD::Vect3(vertexCloud[i]);
  }
  int count = InitVertexArray(points, treePool);
 
  if (m_points.size() >= 4)
  {
    CalculateConvexHull3D(&treePool.GetFirstNode(), points, count, distTol, maxVertexCount);
  }
}
 
void ConvexHull::GetUniquePoints(std::vector<ConvexHullVertex>& points)
{
  class CompareVertex
  {
  public:
    int Compare(const ConvexHullVertex& elementA, const ConvexHullVertex& elementB) const
    {
      for (int i = 0; i < 3; i++)
      {
        if (elementA[i] < elementB[i])
        {
          return -1;
        }
        else if (elementA[i] > elementB[i])
        {
          return 1;
        }
      }
      return 0;
    }
  };
 
  int count = int(points.size());
  Sort<ConvexHullVertex, CompareVertex>(points.data(), count);
 
  int indexCount = 0;
  CompareVertex compareVertex;
  for (int i = 1; i < count; ++i)
  {
    for (; i < count; ++i)
    {
      if (compareVertex.Compare(points[indexCount], points[i]))
      {
        indexCount++;
        points[indexCount] = points[i];
        break;
      }
    }
  }
  points.resize(indexCount + 1);
}
 
ConvexHullAABBTreeNode* ConvexHull::BuildTreeRecurse(ConvexHullAABBTreeNode* const parent,
                                                     ConvexHullVertex* const points,
                                                     int count,
                                                     int baseIndex,
                                                     NodeBundle<ConvexHullAABBTreeNode>& memoryPool) const
{
  ConvexHullAABBTreeNode* tree = nullptr;
 
  assert(count);
  VHACD::Vect3 minP(double(1.0e15));
  VHACD::Vect3 maxP(-double(1.0e15));
  if (count <= VHACD_CONVEXHULL_3D_VERTEX_CLUSTER_SIZE)
  {
    ConvexHullAABBTreeNode& clump = memoryPool.GetNextNode();
 
    clump.m_count = count;
    for (int i = 0; i < count; ++i)
    {
      clump.m_indices[i] = i + baseIndex;
 
      const VHACD::Vect3& p = points[i];
      minP = minP.CWiseMin(p);
      maxP = maxP.CWiseMax(p);
    }
 
    clump.m_left = nullptr;
    clump.m_right = nullptr;
    tree = &clump;
  }
  else
  {
    VHACD::Vect3 median(0);
    VHACD::Vect3 varian(0);
    for (int i = 0; i < count; ++i)
    {
      const VHACD::Vect3& p = points[i];
      minP = minP.CWiseMin(p);
      maxP = maxP.CWiseMax(p);
      median += p;
      varian += p.CWiseMul(p);
    }
 
    varian = varian * double(count) - median.CWiseMul(median);
    int index = 0;
    double maxVarian = double(-1.0e10);
    for (int i = 0; i < 3; ++i)
    {
      if (varian[i] > maxVarian)
      {
        index = i;
        maxVarian = varian[i];
      }
    }
    VHACD::Vect3 center(median * (double(1.0) / double(count)));
 
    double test = center[index];
 
    int i0 = 0;
    int i1 = count - 1;
    do
    {
      for (; i0 <= i1; i0++)
      {
        double val = points[i0][index];
        if (val > test)
        {
          break;
        }
      }
 
      for (; i1 >= i0; i1--)
      {
        double val = points[i1][index];
        if (val < test)
        {
          break;
        }
      }
 
      if (i0 < i1)
      {
        std::swap(points[i0], points[i1]);
        i0++;
        i1--;
      }
    } while (i0 <= i1);
 
    if (i0 == 0)
    {
      i0 = count / 2;
    }
    if (i0 >= (count - 1))
    {
      i0 = count / 2;
    }
 
    tree = &memoryPool.GetNextNode();
 
    assert(i0);
    assert(count - i0);
 
    tree->m_left = BuildTreeRecurse(tree, points, i0, baseIndex, memoryPool);
    tree->m_right = BuildTreeRecurse(tree, &points[i0], count - i0, i0 + baseIndex, memoryPool);
  }
 
  assert(tree);
  tree->m_parent = parent;
  /*
   * WARNING: Changing the compiler conversion of 1.0e-3f changes the results of the convex decomposition
   * Inflate the tree's bounding box slightly
   */
  tree->m_box[0] = minP - VHACD::Vect3(double(1.0e-3f));
  tree->m_box[1] = maxP + VHACD::Vect3(double(1.0e-3f));
  return tree;
}
 
ConvexHullAABBTreeNode* ConvexHull::BuildTreeOld(std::vector<ConvexHullVertex>& points,
                                                 NodeBundle<ConvexHullAABBTreeNode>& memoryPool)
{
  GetUniquePoints(points);
  int count = int(points.size());
  if (count < 4)
  {
    return nullptr;
  }
  return BuildTreeRecurse(nullptr, points.data(), count, 0, memoryPool);
}
 
ConvexHullAABBTreeNode* ConvexHull::BuildTreeNew(std::vector<ConvexHullVertex>& points,
                                                 std::vector<ConvexHullAABBTreeNode>& memoryPool) const
{
  class dCluster
  {
  public:
    VHACD::Vect3 m_sum{ double(0.0) };
    VHACD::Vect3 m_sum2{ double(0.0) };
    int m_start{ 0 };
    int m_count{ 0 };
  };
 
  dCluster firstCluster;
  firstCluster.m_count = int(points.size());
 
  for (int i = 0; i < firstCluster.m_count; ++i)
  {
    const VHACD::Vect3& p = points[i];
    firstCluster.m_sum += p;
    firstCluster.m_sum2 += p.CWiseMul(p);
  }
 
  int baseCount = 0;
  const int clusterSize = 16;
 
  if (firstCluster.m_count > clusterSize)
  {
    dCluster spliteStack[128];
    spliteStack[0] = firstCluster;
    size_t stack = 1;
 
    while (stack)
    {
      stack--;
      dCluster cluster(spliteStack[stack]);
 
      const VHACD::Vect3 origin(cluster.m_sum * (double(1.0) / cluster.m_count));
      const VHACD::Vect3 variance2(cluster.m_sum2 * (double(1.0) / cluster.m_count) - origin.CWiseMul(origin));
      double maxVariance2 = variance2.MaxCoeff();
 
      if ((cluster.m_count <= clusterSize) || (stack > (sizeof(spliteStack) / sizeof(spliteStack[0]) - 4)) ||
          (maxVariance2 < 1.e-4f))
      {
        // no sure if this is beneficial,
        // the array is so small that seem too much overhead
        // int maxIndex = 0;
        // double min_x = 1.0e20f;
        // for (int i = 0; i < cluster.m_count; ++i)
        //{
        //      if (points[cluster.m_start + i].getX() < min_x)
        //      {
        //              maxIndex = i;
        //              min_x = points[cluster.m_start + i].getX();
        //      }
        //}
        // Swap(points[cluster.m_start], points[cluster.m_start + maxIndex]);
        //
        // for (int i = 2; i < cluster.m_count; ++i)
        //{
        //      int j = i;
        //      ConvexHullVertex tmp(points[cluster.m_start + i]);
        //      for (; points[cluster.m_start + j - 1].getX() > tmp.getX(); --j)
        //      {
        //              assert(j > 0);
        //              points[cluster.m_start + j] = points[cluster.m_start + j - 1];
        //      }
        //      points[cluster.m_start + j] = tmp;
        //}
 
        int count = cluster.m_count;
        for (int i = cluster.m_count - 1; i > 0; --i)
        {
          for (int j = i - 1; j >= 0; --j)
          {
            VHACD::Vect3 error(points[cluster.m_start + j] - points[cluster.m_start + i]);
            double mag2 = error.Dot(error);
            if (mag2 < double(1.0e-6))
            {
              points[cluster.m_start + j] = points[cluster.m_start + i];
              count--;
              break;
            }
          }
        }
 
        assert(baseCount <= cluster.m_start);
        for (int i = 0; i < count; ++i)
        {
          points[baseCount] = points[cluster.m_start + i];
          baseCount++;
        }
      }
      else
      {
        const int firstSortAxis = variance2.LongestAxis();
        double axisVal = origin[firstSortAxis];
 
        int i0 = 0;
        int i1 = cluster.m_count - 1;
 
        const int start = cluster.m_start;
        while (i0 < i1)
        {
          while ((points[start + i0][firstSortAxis] <= axisVal) && (i0 < i1))
          {
            ++i0;
          };
 
          while ((points[start + i1][firstSortAxis] > axisVal) && (i0 < i1))
          {
            --i1;
          }
 
          assert(i0 <= i1);
          if (i0 < i1)
          {
            std::swap(points[start + i0], points[start + i1]);
            ++i0;
            --i1;
          }
        }
 
        while ((points[start + i0][firstSortAxis] <= axisVal) && (i0 < cluster.m_count))
        {
          ++i0;
        };
 
#ifdef _DEBUG
        for (int i = 0; i < i0; ++i)
        {
          assert(points[start + i][firstSortAxis] <= axisVal);
        }
 
        for (int i = i0; i < cluster.m_count; ++i)
        {
          assert(points[start + i][firstSortAxis] > axisVal);
        }
#endif
 
        VHACD::Vect3 xc(0);
        VHACD::Vect3 x2c(0);
        for (int i = 0; i < i0; ++i)
        {
          const VHACD::Vect3& x = points[start + i];
          xc += x;
          x2c += x.CWiseMul(x);
        }
 
        dCluster cluster_i1(cluster);
        cluster_i1.m_start = start + i0;
        cluster_i1.m_count = cluster.m_count - i0;
        cluster_i1.m_sum -= xc;
        cluster_i1.m_sum2 -= x2c;
        spliteStack[stack] = cluster_i1;
        assert(cluster_i1.m_count > 0);
        stack++;
 
        dCluster cluster_i0(cluster);
        cluster_i0.m_start = start;
        cluster_i0.m_count = i0;
        cluster_i0.m_sum = xc;
        cluster_i0.m_sum2 = x2c;
        assert(cluster_i0.m_count > 0);
        spliteStack[stack] = cluster_i0;
        stack++;
      }
    }
  }
 
  points.resize(baseCount);
  if (baseCount < 4)
  {
    return nullptr;
  }
 
  VHACD::Vect3 sum(0);
  VHACD::Vect3 sum2(0);
  VHACD::Vect3 minP(double(1.0e15));
  VHACD::Vect3 maxP(double(-1.0e15));
  class dTreeBox
  {
  public:
    VHACD::Vect3 m_min;
    VHACD::Vect3 m_max;
    VHACD::Vect3 m_sum;
    VHACD::Vect3 m_sum2;
    ConvexHullAABBTreeNode* m_parent;
    ConvexHullAABBTreeNode** m_child;
    int m_start;
    int m_count;
  };
 
  for (int i = 0; i < baseCount; ++i)
  {
    const VHACD::Vect3& p = points[i];
    sum += p;
    sum2 += p.CWiseMul(p);
    minP = minP.CWiseMin(p);
    maxP = maxP.CWiseMax(p);
  }
 
  dTreeBox treeBoxStack[128];
  treeBoxStack[0].m_start = 0;
  treeBoxStack[0].m_count = baseCount;
  treeBoxStack[0].m_sum = sum;
  treeBoxStack[0].m_sum2 = sum2;
  treeBoxStack[0].m_min = minP;
  treeBoxStack[0].m_max = maxP;
  treeBoxStack[0].m_child = nullptr;
  treeBoxStack[0].m_parent = nullptr;
 
  int stack = 1;
  ConvexHullAABBTreeNode* root = nullptr;
  while (stack)
  {
    stack--;
    dTreeBox box(treeBoxStack[stack]);
    if (box.m_count <= VHACD_CONVEXHULL_3D_VERTEX_CLUSTER_SIZE)
    {
      assert(memoryPool.size() != memoryPool.capacity() && "memoryPool is going to be reallocated, pointers will be "
                                                           "invalid");
      memoryPool.emplace_back();
      ConvexHullAABBTreeNode& clump = memoryPool.back();
 
      clump.m_count = box.m_count;
      for (int i = 0; i < box.m_count; ++i)
      {
        clump.m_indices[i] = i + box.m_start;
      }
      clump.m_box[0] = box.m_min;
      clump.m_box[1] = box.m_max;
 
      if (box.m_child)
      {
        *box.m_child = &clump;
      }
 
      if (!root)
      {
        root = &clump;
      }
    }
    else
    {
      const VHACD::Vect3 origin(box.m_sum * (double(1.0) / box.m_count));
      const VHACD::Vect3 variance2(box.m_sum2 * (double(1.0) / box.m_count) - origin.CWiseMul(origin));
 
      int firstSortAxis = 0;
      if ((variance2.GetY() >= variance2.GetX()) && (variance2.GetY() >= variance2.GetZ()))
      {
        firstSortAxis = 1;
      }
      else if ((variance2.GetZ() >= variance2.GetX()) && (variance2.GetZ() >= variance2.GetY()))
      {
        firstSortAxis = 2;
      }
      double axisVal = origin[firstSortAxis];
 
      int i0 = 0;
      int i1 = box.m_count - 1;
 
      const int start = box.m_start;
      while (i0 < i1)
      {
        while ((points[start + i0][firstSortAxis] <= axisVal) && (i0 < i1))
        {
          ++i0;
        };
 
        while ((points[start + i1][firstSortAxis] > axisVal) && (i0 < i1))
        {
          --i1;
        }
 
        assert(i0 <= i1);
        if (i0 < i1)
        {
          std::swap(points[start + i0], points[start + i1]);
          ++i0;
          --i1;
        }
      }
 
      while ((points[start + i0][firstSortAxis] <= axisVal) && (i0 < box.m_count))
      {
        ++i0;
      };
 
#ifdef _DEBUG
      for (int i = 0; i < i0; ++i)
      {
        assert(points[start + i][firstSortAxis] <= axisVal);
      }
 
      for (int i = i0; i < box.m_count; ++i)
      {
        assert(points[start + i][firstSortAxis] > axisVal);
      }
#endif
 
      assert(memoryPool.size() != memoryPool.capacity() && "memoryPool is going to be reallocated, pointers will be "
                                                           "invalid");
      memoryPool.emplace_back();
      ConvexHullAABBTreeNode& node = memoryPool.back();
 
      node.m_box[0] = box.m_min;
      node.m_box[1] = box.m_max;
      if (box.m_child)
      {
        *box.m_child = &node;
      }
 
      if (!root)
      {
        root = &node;
      }
 
      {
        VHACD::Vect3 xc(0);
        VHACD::Vect3 x2c(0);
        VHACD::Vect3 p0(double(1.0e15));
        VHACD::Vect3 p1(double(-1.0e15));
        for (int i = i0; i < box.m_count; ++i)
        {
          const VHACD::Vect3& p = points[start + i];
          xc += p;
          x2c += p.CWiseMul(p);
          p0 = p0.CWiseMin(p);
          p1 = p1.CWiseMax(p);
        }
 
        dTreeBox cluster_i1(box);
        cluster_i1.m_start = start + i0;
        cluster_i1.m_count = box.m_count - i0;
        cluster_i1.m_sum = xc;
        cluster_i1.m_sum2 = x2c;
        cluster_i1.m_min = p0;
        cluster_i1.m_max = p1;
        cluster_i1.m_parent = &node;
        cluster_i1.m_child = &node.m_right;
        treeBoxStack[stack] = cluster_i1;
        assert(cluster_i1.m_count > 0);
        stack++;
      }
 
      {
        VHACD::Vect3 xc(0);
        VHACD::Vect3 x2c(0);
        VHACD::Vect3 p0(double(1.0e15));
        VHACD::Vect3 p1(double(-1.0e15));
        for (int i = 0; i < i0; ++i)
        {
          const VHACD::Vect3& p = points[start + i];
          xc += p;
          x2c += p.CWiseMul(p);
          p0 = p0.CWiseMin(p);
          p1 = p1.CWiseMax(p);
        }
 
        dTreeBox cluster_i0(box);
        cluster_i0.m_start = start;
        cluster_i0.m_count = i0;
        cluster_i0.m_min = p0;
        cluster_i0.m_max = p1;
        cluster_i0.m_sum = xc;
        cluster_i0.m_sum2 = x2c;
        cluster_i0.m_parent = &node;
        cluster_i0.m_child = &node.m_left;
        assert(cluster_i0.m_count > 0);
        treeBoxStack[stack] = cluster_i0;
        stack++;
      }
    }
  }
 
  return root;
}
 
int ConvexHull::SupportVertex(ConvexHullAABBTreeNode** const treePointer,
                              const std::vector<ConvexHullVertex>& points,
                              const VHACD::Vect3& dirPlane,
                              const bool removeEntry) const
{
#define VHACD_STACK_DEPTH_3D 64
  double aabbProjection[VHACD_STACK_DEPTH_3D];
  ConvexHullAABBTreeNode* stackPool[VHACD_STACK_DEPTH_3D];
 
  VHACD::Vect3 dir(dirPlane);
 
  int index = -1;
  int stack = 1;
  stackPool[0] = *treePointer;
  aabbProjection[0] = double(1.0e20);
  double maxProj = double(-1.0e20);
  int ix = (dir[0] > double(0.0)) ? 1 : 0;
  int iy = (dir[1] > double(0.0)) ? 1 : 0;
  int iz = (dir[2] > double(0.0)) ? 1 : 0;
  while (stack)
  {
    stack--;
    double boxSupportValue = aabbProjection[stack];
    if (boxSupportValue > maxProj)
    {
      ConvexHullAABBTreeNode* me = stackPool[stack];
 
      /*
       * If the node is not a leaf node...
       */
      if (me->m_left && me->m_right)
      {
        const VHACD::Vect3 leftSupportPoint(
            me->m_left->m_box[ix].GetX(), me->m_left->m_box[iy].GetY(), me->m_left->m_box[iz].GetZ());
        double leftSupportDist = leftSupportPoint.Dot(dir);
 
        const VHACD::Vect3 rightSupportPoint(
            me->m_right->m_box[ix].GetX(), me->m_right->m_box[iy].GetY(), me->m_right->m_box[iz].GetZ());
        double rightSupportDist = rightSupportPoint.Dot(dir);
 
        /*
         * ...push the shorter side first
         * So we can explore the tree in the larger side first
         */
        if (rightSupportDist >= leftSupportDist)
        {
          aabbProjection[stack] = leftSupportDist;
          stackPool[stack] = me->m_left;
          stack++;
          assert(stack < VHACD_STACK_DEPTH_3D);
          aabbProjection[stack] = rightSupportDist;
          stackPool[stack] = me->m_right;
          stack++;
          assert(stack < VHACD_STACK_DEPTH_3D);
        }
        else
        {
          aabbProjection[stack] = rightSupportDist;
          stackPool[stack] = me->m_right;
          stack++;
          assert(stack < VHACD_STACK_DEPTH_3D);
          aabbProjection[stack] = leftSupportDist;
          stackPool[stack] = me->m_left;
          stack++;
          assert(stack < VHACD_STACK_DEPTH_3D);
        }
      }
      /*
       * If it is a node...
       */
      else
      {
        ConvexHullAABBTreeNode* cluster = me;
        for (size_t i = 0; i < cluster->m_count; ++i)
        {
          const ConvexHullVertex& p = points[cluster->m_indices[i]];
          assert(p.GetX() >= cluster->m_box[0].GetX());
          assert(p.GetX() <= cluster->m_box[1].GetX());
          assert(p.GetY() >= cluster->m_box[0].GetY());
          assert(p.GetY() <= cluster->m_box[1].GetY());
          assert(p.GetZ() >= cluster->m_box[0].GetZ());
          assert(p.GetZ() <= cluster->m_box[1].GetZ());
          if (!p.m_mark)
          {
            // assert(p.m_w == double(0.0f));
            double dist = p.Dot(dir);
            if (dist > maxProj)
            {
              maxProj = dist;
              index = cluster->m_indices[i];
            }
          }
          else if (removeEntry)
          {
            cluster->m_indices[i] = cluster->m_indices[cluster->m_count - 1];
            cluster->m_count = cluster->m_count - 1;
            i--;
          }
        }
 
        if (cluster->m_count == 0)
        {
          ConvexHullAABBTreeNode* const parent = cluster->m_parent;
          if (parent)
          {
            ConvexHullAABBTreeNode* const sibling = (parent->m_left != cluster) ? parent->m_left : parent->m_right;
            assert(sibling != cluster);
            ConvexHullAABBTreeNode* const grandParent = parent->m_parent;
            if (grandParent)
            {
              sibling->m_parent = grandParent;
              if (grandParent->m_right == parent)
              {
                grandParent->m_right = sibling;
              }
              else
              {
                grandParent->m_left = sibling;
              }
            }
            else
            {
              sibling->m_parent = nullptr;
              *treePointer = sibling;
            }
          }
        }
      }
    }
  }
 
  assert(index != -1);
  return index;
}
 
double ConvexHull::TetrahedrumVolume(const VHACD::Vect3& p0,
                                     const VHACD::Vect3& p1,
                                     const VHACD::Vect3& p2,
                                     const VHACD::Vect3& p3) const
{
  const VHACD::Vect3 p1p0(p1 - p0);
  const VHACD::Vect3 p2p0(p2 - p0);
  const VHACD::Vect3 p3p0(p3 - p0);
  return p3p0.Dot(p1p0.Cross(p2p0));
}
 
int ConvexHull::InitVertexArray(std::vector<ConvexHullVertex>& points, NodeBundle<ConvexHullAABBTreeNode>& memoryPool)
//                                 std::vector<ConvexHullAABBTreeNode>& memoryPool)
{
#if 1
  ConvexHullAABBTreeNode* tree = BuildTreeOld(points, memoryPool);
#else
  ConvexHullAABBTreeNode* tree = BuildTreeNew(points, (char**)&memoryPool, maxMemSize);
#endif
  int count = int(points.size());
  if (count < 4)
  {
    m_points.resize(0);
    return 0;
  }
 
  m_points.resize(count);
  m_aabbP0 = tree->m_box[0];
  m_aabbP1 = tree->m_box[1];
 
  VHACD::Vect3 boxSize(tree->m_box[1] - tree->m_box[0]);
  m_diag = boxSize.GetNorm();
  const ndNormalMap& normalMap = ndNormalMap::GetNormalMap();
 
  int index0 = SupportVertex(&tree, points, normalMap.m_normal[0]);
  m_points[0] = points[index0];
  points[index0].m_mark = 1;
 
  bool validTetrahedrum = false;
  VHACD::Vect3 e1(double(0.0));
  for (int i = 1; i < normalMap.m_count; ++i)
  {
    int index = SupportVertex(&tree, points, normalMap.m_normal[i]);
    assert(index >= 0);
 
    e1 = points[index] - m_points[0];
    double error2 = e1.GetNormSquared();
    if (error2 > (double(1.0e-4) * m_diag * m_diag))
    {
      m_points[1] = points[index];
      points[index].m_mark = 1;
      validTetrahedrum = true;
      break;
    }
  }
  if (!validTetrahedrum)
  {
    m_points.resize(0);
    assert(0);
    return count;
  }
 
  validTetrahedrum = false;
  VHACD::Vect3 e2(double(0.0));
  VHACD::Vect3 normal(double(0.0));
  for (int i = 2; i < normalMap.m_count; ++i)
  {
    int index = SupportVertex(&tree, points, normalMap.m_normal[i]);
    assert(index >= 0);
    e2 = points[index] - m_points[0];
    normal = e1.Cross(e2);
    double error2 = normal.GetNorm();
    if (error2 > (double(1.0e-4) * m_diag * m_diag))
    {
      m_points[2] = points[index];
      points[index].m_mark = 1;
      validTetrahedrum = true;
      break;
    }
  }
 
  if (!validTetrahedrum)
  {
    m_points.resize(0);
    assert(0);
    return count;
  }
 
  // find the largest possible tetrahedron
  validTetrahedrum = false;
  VHACD::Vect3 e3(double(0.0));
 
  index0 = SupportVertex(&tree, points, normal);
  e3 = points[index0] - m_points[0];
  double err2 = normal.Dot(e3);
  if (fabs(err2) > (double(1.0e-6) * m_diag * m_diag))
  {
    // we found a valid tetrahedral, about and start build the hull by adding the rest of the points
    m_points[3] = points[index0];
    points[index0].m_mark = 1;
    validTetrahedrum = true;
  }
  if (!validTetrahedrum)
  {
    VHACD::Vect3 n(-normal);
    int index = SupportVertex(&tree, points, n);
    e3 = points[index] - m_points[0];
    double error2 = normal.Dot(e3);
    if (fabs(error2) > (double(1.0e-6) * m_diag * m_diag))
    {
      // we found a valid tetrahedral, about and start build the hull by adding the rest of the points
      m_points[3] = points[index];
      points[index].m_mark = 1;
      validTetrahedrum = true;
    }
  }
  if (!validTetrahedrum)
  {
    for (int i = 3; i < normalMap.m_count; ++i)
    {
      int index = SupportVertex(&tree, points, normalMap.m_normal[i]);
      assert(index >= 0);
 
      // make sure the volume of the fist tetrahedral is no negative
      e3 = points[index] - m_points[0];
      double error2 = normal.Dot(e3);
      if (fabs(error2) > (double(1.0e-6) * m_diag * m_diag))
      {
        // we found a valid tetrahedral, about and start build the hull by adding the rest of the points
        m_points[3] = points[index];
        points[index].m_mark = 1;
        validTetrahedrum = true;
        break;
      }
    }
  }
  if (!validTetrahedrum)
  {
    // the points do not form a convex hull
    m_points.resize(0);
    return count;
  }
 
  m_points.resize(4);
  double volume = TetrahedrumVolume(m_points[0], m_points[1], m_points[2], m_points[3]);
  if (volume > double(0.0))
  {
    std::swap(m_points[2], m_points[3]);
  }
  assert(TetrahedrumVolume(m_points[0], m_points[1], m_points[2], m_points[3]) < double(0.0));
  return count;
}
 
std::list<ConvexHullFace>::iterator ConvexHull::AddFace(int i0, int i1, int i2)
{
  ConvexHullFace face;
  face.m_index[0] = i0;
  face.m_index[1] = i1;
  face.m_index[2] = i2;
 
  std::list<ConvexHullFace>::iterator node = m_list.emplace(m_list.end(), face);
  return node;
}
 
void ConvexHull::CalculateConvexHull3D(ConvexHullAABBTreeNode* vertexTree,
                                       std::vector<ConvexHullVertex>& points,
                                       int count,
                                       double distTol,
                                       int maxVertexCount)
{
  distTol = fabs(distTol) * m_diag;
  std::list<ConvexHullFace>::iterator f0Node = AddFace(0, 1, 2);
  std::list<ConvexHullFace>::iterator f1Node = AddFace(0, 2, 3);
  std::list<ConvexHullFace>::iterator f2Node = AddFace(2, 1, 3);
  std::list<ConvexHullFace>::iterator f3Node = AddFace(1, 0, 3);
 
  ConvexHullFace& f0 = *f0Node;
  ConvexHullFace& f1 = *f1Node;
  ConvexHullFace& f2 = *f2Node;
  ConvexHullFace& f3 = *f3Node;
 
  f0.m_twin[0] = f3Node;
  f0.m_twin[1] = f2Node;
  f0.m_twin[2] = f1Node;
 
  f1.m_twin[0] = f0Node;
  f1.m_twin[1] = f2Node;
  f1.m_twin[2] = f3Node;
 
  f2.m_twin[0] = f0Node;
  f2.m_twin[1] = f3Node;
  f2.m_twin[2] = f1Node;
 
  f3.m_twin[0] = f0Node;
  f3.m_twin[1] = f1Node;
  f3.m_twin[2] = f2Node;
 
  std::list<std::list<ConvexHullFace>::iterator> boundaryFaces;
  boundaryFaces.push_back(f0Node);
  boundaryFaces.push_back(f1Node);
  boundaryFaces.push_back(f2Node);
  boundaryFaces.push_back(f3Node);
 
  m_points.resize(count);
 
  count -= 4;
  maxVertexCount -= 4;
  int currentIndex = 4;
 
  /*
   * Some are iterators into boundaryFaces, others into m_list
   */
  std::vector<std::list<ConvexHullFace>::iterator> stack;
  std::vector<std::list<ConvexHullFace>::iterator> coneList;
  std::vector<std::list<ConvexHullFace>::iterator> deleteList;
 
  stack.reserve(1024 + count);
  coneList.reserve(1024 + count);
  deleteList.reserve(1024 + count);
 
  while (boundaryFaces.size() && count && (maxVertexCount > 0))
  {
    // my definition of the optimal convex hull of a given vertex count,
    // is the convex hull formed by a subset of the input vertex that minimizes the volume difference
    // between the perfect hull formed from all input vertex and the hull of the sub set of vertex.
    // When using a priority heap this algorithms will generate the an optimal of a fix vertex count.
    // Since all Newton's tools do not have a limit on the point count of a convex hull, I can use either a stack or a
    // queue. a stack maximize construction speed, a Queue tend to maximize the volume of the generated Hull approaching
    // a perfect Hull. For now we use a queue. For general hulls it does not make a difference if we use a stack, queue,
    // or a priority heap. perfect optimal hull only apply for when build hull of a limited vertex count.
    //
    // Also when building Hulls of a limited vertex count, this function runs in constant time.
    // yes that is correct, it does not makes a difference if you build a N point hull from 100 vertex
    // or from 100000 vertex input array.
 
    // using a queue (some what slower by better hull when reduced vertex count is desired)
    bool isvalid;
    std::list<ConvexHullFace>::iterator faceNode = boundaryFaces.back();
    ConvexHullFace& face = *faceNode;
    HullPlane planeEquation(face.GetPlaneEquation(m_points, isvalid));
 
    int index = 0;
    double dist = 0;
    VHACD::Vect3 p;
    if (isvalid)
    {
      index = SupportVertex(&vertexTree, points, planeEquation);
      p = points[index];
      dist = planeEquation.Evalue(p);
    }
 
    if (isvalid && (dist >= distTol) && (face.Evalue(m_points, p) < double(0.0)))
    {
      stack.push_back(faceNode);
 
      deleteList.clear();
      while (stack.size())
      {
        std::list<ConvexHullFace>::iterator node1 = stack.back();
        ConvexHullFace& face1 = *node1;
 
        stack.pop_back();
 
        if (!face1.m_mark && (face1.Evalue(m_points, p) < double(0.0)))
        {
#ifdef _DEBUG
          for (const auto node : deleteList)
          {
            assert(node != node1);
          }
#endif
 
          deleteList.push_back(node1);
          face1.m_mark = 1;
          for (std::list<ConvexHullFace>::iterator& twinNode : face1.m_twin)
          {
            ConvexHullFace& twinFace = *twinNode;
            if (!twinFace.m_mark)
            {
              stack.push_back(twinNode);
            }
          }
        }
      }
 
      m_points[currentIndex] = points[index];
      points[index].m_mark = 1;
 
      coneList.clear();
      for (std::list<ConvexHullFace>::iterator node1 : deleteList)
      {
        ConvexHullFace& face1 = *node1;
        assert(face1.m_mark == 1);
        for (std::size_t j0 = 0; j0 < face1.m_twin.size(); ++j0)
        {
          std::list<ConvexHullFace>::iterator twinNode = face1.m_twin[j0];
          ConvexHullFace& twinFace = *twinNode;
          if (!twinFace.m_mark)
          {
            std::size_t j1 = (j0 == 2) ? 0 : j0 + 1;
            std::list<ConvexHullFace>::iterator newNode = AddFace(currentIndex, face1.m_index[j0], face1.m_index[j1]);
            boundaryFaces.push_front(newNode);
            ConvexHullFace& newFace = *newNode;
 
            newFace.m_twin[1] = twinNode;
            for (std::size_t k = 0; k < twinFace.m_twin.size(); ++k)
            {
              if (twinFace.m_twin[k] == node1)
              {
                twinFace.m_twin[k] = newNode;
              }
            }
            coneList.push_back(newNode);
          }
        }
      }
 
      for (std::size_t i = 0; i < coneList.size() - 1; ++i)
      {
        std::list<ConvexHullFace>::iterator nodeA = coneList[i];
        ConvexHullFace& faceA = *nodeA;
        assert(faceA.m_mark == 0);
        for (std::size_t j = i + 1; j < coneList.size(); j++)
        {
          std::list<ConvexHullFace>::iterator nodeB = coneList[j];
          ConvexHullFace& faceB = *nodeB;
          assert(faceB.m_mark == 0);
          if (faceA.m_index[2] == faceB.m_index[1])
          {
            faceA.m_twin[2] = nodeB;
            faceB.m_twin[0] = nodeA;
            break;
          }
        }
 
        for (std::size_t j = i + 1; j < coneList.size(); j++)
        {
          std::list<ConvexHullFace>::iterator nodeB = coneList[j];
          ConvexHullFace& faceB = *nodeB;
          assert(faceB.m_mark == 0);
          if (faceA.m_index[1] == faceB.m_index[2])
          {
            faceA.m_twin[0] = nodeB;
            faceB.m_twin[2] = nodeA;
            break;
          }
        }
      }
 
      for (std::list<ConvexHullFace>::iterator node : deleteList)
      {
        auto it = std::find(boundaryFaces.begin(), boundaryFaces.end(), node);
        if (it != boundaryFaces.end())
        {
          boundaryFaces.erase(it);
        }
        m_list.erase(node);
      }
 
      maxVertexCount--;
      currentIndex++;
      count--;
    }
    else
    {
      auto it = std::find(boundaryFaces.begin(), boundaryFaces.end(), faceNode);
      if (it != boundaryFaces.end())
      {
        boundaryFaces.erase(it);
      }
    }
  }
  m_points.resize(currentIndex);
}
 
//***********************************************************************************************
// End of ConvexHull generation code by Julio Jerez <jerezjulio0@gmail.com>
//***********************************************************************************************
 
class KdTreeNode;
 
enum Axes
{
  X_AXIS = 0,
  Y_AXIS = 1,
  Z_AXIS = 2
};
 
class KdTreeFindNode
{
public:
  KdTreeFindNode() = default;
 
  KdTreeNode* m_node{ nullptr };
  double m_distance{ 0.0 };
};
 
class KdTree
{
public:
  KdTree() = default;
 
  const VHACD::Vertex& GetPosition(uint32_t index) const;
 
  uint32_t Search(const VHACD::Vect3& pos, double radius, uint32_t maxObjects, KdTreeFindNode* found) const;
 
  uint32_t Add(const VHACD::Vertex& v);
 
  KdTreeNode& GetNewNode(uint32_t index);
 
  uint32_t GetNearest(const VHACD::Vect3& pos,
                      double radius,
                      bool& _found) const;  // returns the nearest possible neighbor's index.
 
  const std::vector<VHACD::Vertex>& GetVertices() const;
  std::vector<VHACD::Vertex>&& TakeVertices();
 
  uint32_t GetVCount() const;
 
private:
  KdTreeNode* m_root{ nullptr };
  NodeBundle<KdTreeNode> m_bundle;
 
  std::vector<VHACD::Vertex> m_vertices;
};
 
class KdTreeNode
{
public:
  KdTreeNode() = default;
  KdTreeNode(uint32_t index);
 
  void Add(KdTreeNode& node, Axes dim, const KdTree& iface);
 
  uint32_t GetIndex() const;
 
  void Search(Axes axis,
              const VHACD::Vect3& pos,
              double radius,
              uint32_t& count,
              uint32_t maxObjects,
              KdTreeFindNode* found,
              const KdTree& iface);
 
private:
  uint32_t m_index = 0;
  KdTreeNode* m_left = nullptr;
  KdTreeNode* m_right = nullptr;
};
 
const VHACD::Vertex& KdTree::GetPosition(uint32_t index) const
{
  assert(index < m_vertices.size());
  return m_vertices[index];
}
 
uint32_t KdTree::Search(const VHACD::Vect3& pos, double radius, uint32_t maxObjects, KdTreeFindNode* found) const
{
  if (!m_root)
    return 0;
  uint32_t count = 0;
  m_root->Search(X_AXIS, pos, radius, count, maxObjects, found, *this);
  return count;
}
 
uint32_t KdTree::Add(const VHACD::Vertex& v)
{
  uint32_t ret = uint32_t(m_vertices.size());
  m_vertices.emplace_back(v);
  KdTreeNode& node = GetNewNode(ret);
  if (m_root)
  {
    m_root->Add(node, X_AXIS, *this);
  }
  else
  {
    m_root = &node;
  }
  return ret;
}
 
KdTreeNode& KdTree::GetNewNode(uint32_t index)
{
  KdTreeNode& node = m_bundle.GetNextNode();
  node = KdTreeNode(index);
  return node;
}
 
uint32_t KdTree::GetNearest(const VHACD::Vect3& pos,
                            double radius,
                            bool& _found) const  // returns the nearest possible neighbor's index.
{
  uint32_t ret = 0;
 
  _found = false;
  KdTreeFindNode found;
  uint32_t count = Search(pos, radius, 1, &found);
  if (count)
  {
    KdTreeNode* node = found.m_node;
    ret = node->GetIndex();
    _found = true;
  }
  return ret;
}
 
const std::vector<VHACD::Vertex>& KdTree::GetVertices() const { return m_vertices; }
 
std::vector<VHACD::Vertex>&& KdTree::TakeVertices() { return std::move(m_vertices); }
 
uint32_t KdTree::GetVCount() const { return uint32_t(m_vertices.size()); }
 
KdTreeNode::KdTreeNode(uint32_t index) : m_index(index) {}
 
void KdTreeNode::Add(KdTreeNode& node, Axes dim, const KdTree& tree)
{
  Axes axis = X_AXIS;
  uint32_t idx = 0;
  switch (dim)
  {
    case X_AXIS:
      idx = 0;
      axis = Y_AXIS;
      break;
    case Y_AXIS:
      idx = 1;
      axis = Z_AXIS;
      break;
    case Z_AXIS:
      idx = 2;
      axis = X_AXIS;
      break;
  }
 
  const VHACD::Vertex& nodePosition = tree.GetPosition(node.m_index);
  const VHACD::Vertex& position = tree.GetPosition(m_index);
  if (nodePosition[idx] <= position[idx])
  {
    if (m_left)
      m_left->Add(node, axis, tree);
    else
      m_left = &node;
  }
  else
  {
    if (m_right)
      m_right->Add(node, axis, tree);
    else
      m_right = &node;
  }
}
 
uint32_t KdTreeNode::GetIndex() const { return m_index; }
 
void KdTreeNode::Search(Axes axis,
                        const VHACD::Vect3& pos,
                        double radius,
                        uint32_t& count,
                        uint32_t maxObjects,
                        KdTreeFindNode* found,
                        const KdTree& iface)
{
  const VHACD::Vect3 position = iface.GetPosition(m_index);
 
  const VHACD::Vect3 d = pos - position;
 
  KdTreeNode* search1 = 0;
  KdTreeNode* search2 = 0;
 
  uint32_t idx = 0;
  switch (axis)
  {
    case X_AXIS:
      idx = 0;
      axis = Y_AXIS;
      break;
    case Y_AXIS:
      idx = 1;
      axis = Z_AXIS;
      break;
    case Z_AXIS:
      idx = 2;
      axis = X_AXIS;
      break;
  }
 
  if (d[idx] <= 0)  // JWR  if we are to the left
  {
    search1 = m_left;      // JWR  then search to the left
    if (-d[idx] < radius)  // JWR  if distance to the right is less than our search radius, continue on the right
                           // as well.
      search2 = m_right;
  }
  else
  {
    search1 = m_right;    // JWR  ok, we go down the left tree
    if (d[idx] < radius)  // JWR  if the distance from the right is less than our search radius
      search2 = m_left;
  }
 
  double r2 = radius * radius;
  double m = d.GetNormSquared();
 
  if (m < r2)
  {
    switch (count)
    {
      case 0:
      {
        found[count].m_node = this;
        found[count].m_distance = m;
        break;
      }
      case 1:
      {
        if (m < found[0].m_distance)
        {
          if (maxObjects == 1)
          {
            found[0].m_node = this;
            found[0].m_distance = m;
          }
          else
          {
            found[1] = found[0];
            found[0].m_node = this;
            found[0].m_distance = m;
          }
        }
        else if (maxObjects > 1)
        {
          found[1].m_node = this;
          found[1].m_distance = m;
        }
        break;
      }
      default:
      {
        bool inserted = false;
 
        for (uint32_t i = 0; i < count; i++)
        {
          if (m < found[i].m_distance)  // if this one is closer than a pre-existing one...
          {
            // insertion sort...
            uint32_t scan = count;
            if (scan >= maxObjects)
              scan = maxObjects - 1;
            for (uint32_t j = scan; j > i; j--)
            {
              found[j] = found[j - 1];
            }
            found[i].m_node = this;
            found[i].m_distance = m;
            inserted = true;
            break;
          }
        }
 
        if (!inserted && count < maxObjects)
        {
          found[count].m_node = this;
          found[count].m_distance = m;
        }
      }
      break;
    }
 
    count++;
 
    if (count > maxObjects)
    {
      count = maxObjects;
    }
  }
 
  if (search1)
    search1->Search(axis, pos, radius, count, maxObjects, found, iface);
 
  if (search2)
    search2->Search(axis, pos, radius, count, maxObjects, found, iface);
}
 
class VertexIndex
{
public:
  VertexIndex(double granularity, bool snapToGrid);
 
  VHACD::Vect3 SnapToGrid(VHACD::Vect3 p);
 
  uint32_t GetIndex(VHACD::Vect3 p, bool& newPos);
 
  const std::vector<VHACD::Vertex>& GetVertices() const;
 
  std::vector<VHACD::Vertex>&& TakeVertices();
 
  uint32_t GetVCount() const;
 
  bool SaveAsObj(const char* fname, uint32_t tcount, uint32_t* indices)
  {
    bool ret = false;
 
    FILE* fph = fopen(fname, "wb");
    if (fph)
    {
      ret = true;
 
      const std::vector<VHACD::Vertex>& v = GetVertices();
      for (uint32_t i = 0; i < v.size(); ++i)
      {
        fprintf(fph, "v %0.9f %0.9f %0.9f\r\n", v[i].mX, v[i].mY, v[i].mZ);
      }
 
      for (uint32_t i = 0; i < tcount; i++)
      {
        uint32_t i1 = *indices++;
        uint32_t i2 = *indices++;
        uint32_t i3 = *indices++;
        fprintf(fph, "f %d %d %d\r\n", i1 + 1, i2 + 1, i3 + 1);
      }
      fclose(fph);
    }
 
    return ret;
  }
 
private:
  bool m_snapToGrid : 1;
  double m_granularity;
  KdTree m_KdTree;
};
 
VertexIndex::VertexIndex(double granularity, bool snapToGrid) : m_snapToGrid(snapToGrid), m_granularity(granularity) {}
 
VHACD::Vect3 VertexIndex::SnapToGrid(VHACD::Vect3 p)
{
  for (int i = 0; i < 3; ++i)
  {
    double m = fmod(p[i], m_granularity);
    p[i] -= m;
  }
  return p;
}
 
uint32_t VertexIndex::GetIndex(VHACD::Vect3 p, bool& newPos)
{
  uint32_t ret;
 
  newPos = false;
 
  if (m_snapToGrid)
  {
    p = SnapToGrid(p);
  }
 
  bool found;
  ret = m_KdTree.GetNearest(p, m_granularity, found);
  if (!found)
  {
    newPos = true;
    ret = m_KdTree.Add(VHACD::Vertex(p.GetX(), p.GetY(), p.GetZ()));
  }
 
  return ret;
}
 
const std::vector<VHACD::Vertex>& VertexIndex::GetVertices() const { return m_KdTree.GetVertices(); }
 
std::vector<VHACD::Vertex>&& VertexIndex::TakeVertices() { return std::move(m_KdTree.TakeVertices()); }
 
uint32_t VertexIndex::GetVCount() const { return m_KdTree.GetVCount(); }
 
/*
 * A wrapper class for 3 10 bit integers packed into a 32 bit integer
 * Layout is [PAD][X][Y][Z]
 * Pad is bits 31-30, X is 29-20, Y is 19-10, and Z is 9-0
 */
class Voxel
{
  /*
   * Specify all of them for consistency
   */
  static constexpr int VoxelBitsZStart = 0;
  static constexpr int VoxelBitsYStart = 10;
  static constexpr int VoxelBitsXStart = 20;
  static constexpr int VoxelBitMask = 0x03FF;  // bits 0 through 9 inclusive
public:
  Voxel() = default;
 
  Voxel(uint32_t index);
 
  Voxel(uint32_t x, uint32_t y, uint32_t z);
 
  bool operator==(const Voxel& v) const;
 
  VHACD::Vector3<uint32_t> GetVoxel() const;
 
  uint32_t GetX() const;
  uint32_t GetY() const;
  uint32_t GetZ() const;
 
  uint32_t GetVoxelAddress() const;
 
private:
  uint32_t m_voxel{ 0 };
};
 
Voxel::Voxel(uint32_t index) : m_voxel(index) {}
 
Voxel::Voxel(uint32_t x, uint32_t y, uint32_t z)
  : m_voxel((x << VoxelBitsXStart) | (y << VoxelBitsYStart) | (z << VoxelBitsZStart))
{
  assert(x < 1024 && "Voxel constructed with X outside of range");
  assert(y < 1024 && "Voxel constructed with Y outside of range");
  assert(z < 1024 && "Voxel constructed with Z outside of range");
}
 
bool Voxel::operator==(const Voxel& v) const { return m_voxel == v.m_voxel; }
 
VHACD::Vector3<uint32_t> Voxel::GetVoxel() const { return VHACD::Vector3<uint32_t>(GetX(), GetY(), GetZ()); }
 
uint32_t Voxel::GetX() const { return (m_voxel >> VoxelBitsXStart) & VoxelBitMask; }
 
uint32_t Voxel::GetY() const { return (m_voxel >> VoxelBitsYStart) & VoxelBitMask; }
 
uint32_t Voxel::GetZ() const { return (m_voxel >> VoxelBitsZStart) & VoxelBitMask; }
 
uint32_t Voxel::GetVoxelAddress() const { return m_voxel; }
 
struct SimpleMesh
{
  std::vector<VHACD::Vertex> m_vertices;
  std::vector<VHACD::Triangle> m_indices;
};
 
/*======================== 0-tests ========================*/
inline bool
IntersectRayAABB(const VHACD::Vect3& start, const VHACD::Vect3& dir, const VHACD::BoundsAABB& bounds, double& t)
{
  bool inside = true;
  VHACD::Vect3 ta(double(-1.0));
 
  for (uint32_t i = 0; i < 3; ++i)
  {
    if (start[i] < bounds.GetMin()[i])
    {
      if (dir[i] != double(0.0))
        ta[i] = (bounds.GetMin()[i] - start[i]) / dir[i];
      inside = false;
    }
    else if (start[i] > bounds.GetMax()[i])
    {
      if (dir[i] != double(0.0))
        ta[i] = (bounds.GetMax()[i] - start[i]) / dir[i];
      inside = false;
    }
  }
 
  if (inside)
  {
    t = double(0.0);
    return true;
  }
 
  uint32_t taxis;
  double tmax = ta.MaxCoeff(taxis);
 
  if (tmax < double(0.0))
    return false;
 
 
  double eps = double(0.0);
 
  VHACD::Vect3 hit = start + dir * tmax;
 
  if ((hit.GetX() < bounds.GetMin().GetX() - eps || hit.GetX() > bounds.GetMax().GetX() + eps) && taxis != 0)
    return false;
  if ((hit.GetY() < bounds.GetMin().GetY() - eps || hit.GetY() > bounds.GetMax().GetY() + eps) && taxis != 1)
    return false;
  if ((hit.GetZ() < bounds.GetMin().GetZ() - eps || hit.GetZ() > bounds.GetMax().GetZ() + eps) && taxis != 2)
    return false;
 
  t = tmax;
 
  return true;
}
 
// Moller and Trumbore's method
inline bool IntersectRayTriTwoSided(const VHACD::Vect3& p,
                                    const VHACD::Vect3& dir,
                                    const VHACD::Vect3& a,
                                    const VHACD::Vect3& b,
                                    const VHACD::Vect3& c,
                                    double& t,
                                    double& u,
                                    double& v,
                                    double& w,
                                    double& sign,
                                    VHACD::Vect3* normal)
{
  VHACD::Vect3 ab = b - a;
  VHACD::Vect3 ac = c - a;
  VHACD::Vect3 n = ab.Cross(ac);
 
  double d = -dir.Dot(n);
  double ood = double(1.0) / d;  // No need to check for division by zero here as infinity arithmetic will save us...
  VHACD::Vect3 ap = p - a;
 
  t = ap.Dot(n) * ood;
  if (t < double(0.0))
  {
    return false;
  }
 
  VHACD::Vect3 e = -dir.Cross(ap);
  v = ac.Dot(e) * ood;
  if (v < double(0.0) || v > double(1.0))  // ...here...
  {
    return false;
  }
  w = -ab.Dot(e) * ood;
  if (w < double(0.0) || v + w > double(1.0))  // ...and here
  {
    return false;
  }
 
  u = double(1.0) - v - w;
  if (normal)
  {
    *normal = n;
  }
 
  sign = d;
 
  return true;
}
 
// RTCD 5.1.5, page 142
inline VHACD::Vect3 ClosestPointOnTriangle(const VHACD::Vect3& a,
                                           const VHACD::Vect3& b,
                                           const VHACD::Vect3& c,
                                           const VHACD::Vect3& p,
                                           double& v,
                                           double& w)
{
  VHACD::Vect3 ab = b - a;
  VHACD::Vect3 ac = c - a;
  VHACD::Vect3 ap = p - a;
 
  double d1 = ab.Dot(ap);
  double d2 = ac.Dot(ap);
  if (d1 <= double(0.0) && d2 <= double(0.0))
  {
    v = double(0.0);
    w = double(0.0);
    return a;
  }
 
  VHACD::Vect3 bp = p - b;
  double d3 = ab.Dot(bp);
  double d4 = ac.Dot(bp);
  if (d3 >= double(0.0) && d4 <= d3)
  {
    v = double(1.0);
    w = double(0.0);
    return b;
  }
 
  double vc = d1 * d4 - d3 * d2;
  if (vc <= double(0.0) && d1 >= double(0.0) && d3 <= double(0.0))
  {
    v = d1 / (d1 - d3);
    w = double(0.0);
    return a + v * ab;
  }
 
  VHACD::Vect3 cp = p - c;
  double d5 = ab.Dot(cp);
  double d6 = ac.Dot(cp);
  if (d6 >= double(0.0) && d5 <= d6)
  {
    v = double(0.0);
    w = double(1.0);
    return c;
  }
 
  double vb = d5 * d2 - d1 * d6;
  if (vb <= double(0.0) && d2 >= double(0.0) && d6 <= double(0.0))
  {
    v = double(0.0);
    w = d2 / (d2 - d6);
    return a + w * ac;
  }
 
  double va = d3 * d6 - d5 * d4;
  if (va <= double(0.0) && (d4 - d3) >= double(0.0) && (d5 - d6) >= double(0.0))
  {
    w = (d4 - d3) / ((d4 - d3) + (d5 - d6));
    v = double(1.0) - w;
    return b + w * (c - b);
  }
 
  double denom = double(1.0) / (va + vb + vc);
  v = vb * denom;
  w = vc * denom;
  return a + ab * v + ac * w;
}
 
class AABBTree
{
public:
  AABBTree() = default;
  AABBTree(AABBTree&&) = default;
  AABBTree& operator=(AABBTree&&) = default;
 
  AABBTree(const std::vector<VHACD::Vertex>& vertices, const std::vector<VHACD::Triangle>& indices);
 
  bool TraceRay(const VHACD::Vect3& start,
                const VHACD::Vect3& to,
                double& outT,
                double& faceSign,
                VHACD::Vect3& hitLocation) const;
 
  bool
  TraceRay(const VHACD::Vect3& start, const VHACD::Vect3& dir, uint32_t& insideCount, uint32_t& outsideCount) const;
 
  bool TraceRay(const VHACD::Vect3& start,
                const VHACD::Vect3& dir,
                double& outT,
                double& u,
                double& v,
                double& w,
                double& faceSign,
                uint32_t& faceIndex) const;
 
  VHACD::Vect3 GetCenter() const;
  VHACD::Vect3 GetMinExtents() const;
  VHACD::Vect3 GetMaxExtents() const;
 
  bool GetClosestPointWithinDistance(const VHACD::Vect3& point, double maxDistance, VHACD::Vect3& closestPoint) const;
 
private:
  struct Node
  {
    union
    {
      uint32_t m_children;
      uint32_t m_numFaces{ 0 };
    };
 
    uint32_t* m_faces{ nullptr };
    VHACD::BoundsAABB m_extents;
  };
 
  struct FaceSorter
  {
    FaceSorter(const std::vector<VHACD::Vertex>& positions, const std::vector<VHACD::Triangle>& indices, uint32_t axis);
 
    bool operator()(uint32_t lhs, uint32_t rhs) const;
 
    double GetCentroid(uint32_t face) const;
 
    const std::vector<VHACD::Vertex>& m_vertices;
    const std::vector<VHACD::Triangle>& m_indices;
    uint32_t m_axis;
  };
 
  // partition the objects and return the number of objects in the lower partition
  uint32_t PartitionMedian(Node& n, uint32_t* faces, uint32_t numFaces);
  uint32_t PartitionSAH(Node& n, uint32_t* faces, uint32_t numFaces);
 
  void Build();
 
  void BuildRecursive(uint32_t nodeIndex, uint32_t* faces, uint32_t numFaces);
 
  void TraceRecursive(uint32_t nodeIndex,
                      const VHACD::Vect3& start,
                      const VHACD::Vect3& dir,
                      double& outT,
                      double& u,
                      double& v,
                      double& w,
                      double& faceSign,
                      uint32_t& faceIndex) const;
 
  bool GetClosestPointWithinDistance(const VHACD::Vect3& point,
                                     const double maxDis,
                                     double& dis,
                                     double& v,
                                     double& w,
                                     uint32_t& faceIndex,
                                     VHACD::Vect3& closest) const;
 
  void GetClosestPointWithinDistanceSqRecursive(uint32_t nodeIndex,
                                                const VHACD::Vect3& point,
                                                double& outDisSq,
                                                double& outV,
                                                double& outW,
                                                uint32_t& outFaceIndex,
                                                VHACD::Vect3& closest) const;
 
  VHACD::BoundsAABB CalculateFaceBounds(uint32_t* faces, uint32_t numFaces);
 
  // track the next free node
  uint32_t m_freeNode;
 
  const std::vector<VHACD::Vertex>* m_vertices{ nullptr };
  const std::vector<VHACD::Triangle>* m_indices{ nullptr };
 
  std::vector<uint32_t> m_faces;
  std::vector<Node> m_nodes;
  std::vector<VHACD::BoundsAABB> m_faceBounds;
 
  // stats
  uint32_t m_treeDepth{ 0 };
  uint32_t m_innerNodes{ 0 };
  uint32_t m_leafNodes{ 0 };
 
  uint32_t s_depth{ 0 };
};
 
AABBTree::FaceSorter::FaceSorter(const std::vector<VHACD::Vertex>& positions,
                                 const std::vector<VHACD::Triangle>& indices,
                                 uint32_t axis)
  : m_vertices(positions), m_indices(indices), m_axis(axis)
{
}
 
inline bool AABBTree::FaceSorter::operator()(uint32_t lhs, uint32_t rhs) const
{
  double a = GetCentroid(lhs);
  double b = GetCentroid(rhs);
 
  if (a == b)
  {
    return lhs < rhs;
  }
  else
  {
    return a < b;
  }
}
 
inline double AABBTree::FaceSorter::GetCentroid(uint32_t face) const
{
  const VHACD::Vect3& a = m_vertices[m_indices[face].mI0];
  const VHACD::Vect3& b = m_vertices[m_indices[face].mI1];
  const VHACD::Vect3& c = m_vertices[m_indices[face].mI2];
 
  return (a[m_axis] + b[m_axis] + c[m_axis]) / double(3.0);
}
 
AABBTree::AABBTree(const std::vector<VHACD::Vertex>& vertices, const std::vector<VHACD::Triangle>& indices)
  : m_vertices(&vertices), m_indices(&indices)
{
  Build();
}
 
bool AABBTree::TraceRay(const VHACD::Vect3& start,
                        const VHACD::Vect3& to,
                        double& outT,
                        double& faceSign,
                        VHACD::Vect3& hitLocation) const
{
  VHACD::Vect3 dir = to - start;
  double distance = dir.Normalize();
  double u, v, w;
  uint32_t faceIndex;
  bool hit = TraceRay(start, dir, outT, u, v, w, faceSign, faceIndex);
  if (hit)
  {
    hitLocation = start + dir * outT;
  }
 
  if (hit && outT > distance)
  {
    hit = false;
  }
  return hit;
}
 
bool AABBTree::TraceRay(const VHACD::Vect3& start,
                        const VHACD::Vect3& dir,
                        uint32_t& insideCount,
                        uint32_t& outsideCount) const
{
  double outT, u, v, w, faceSign;
  uint32_t faceIndex;
  bool hit = TraceRay(start, dir, outT, u, v, w, faceSign, faceIndex);
  if (hit)
  {
    if (faceSign >= 0)
    {
      insideCount++;
    }
    else
    {
      outsideCount++;
    }
  }
  return hit;
}
 
bool AABBTree::TraceRay(const VHACD::Vect3& start,
                        const VHACD::Vect3& dir,
                        double& outT,
                        double& u,
                        double& v,
                        double& w,
                        double& faceSign,
                        uint32_t& faceIndex) const
{
  outT = FLT_MAX;
  TraceRecursive(0, start, dir, outT, u, v, w, faceSign, faceIndex);
  return (outT != FLT_MAX);
}
 
VHACD::Vect3 AABBTree::GetCenter() const { return m_nodes[0].m_extents.GetCenter(); }
 
VHACD::Vect3 AABBTree::GetMinExtents() const { return m_nodes[0].m_extents.GetMin(); }
 
VHACD::Vect3 AABBTree::GetMaxExtents() const { return m_nodes[0].m_extents.GetMax(); }
 
bool AABBTree::GetClosestPointWithinDistance(const VHACD::Vect3& point,
                                             double maxDistance,
                                             VHACD::Vect3& closestPoint) const
{
  double dis, v, w;
  uint32_t faceIndex;
  bool hit = GetClosestPointWithinDistance(point, maxDistance, dis, v, w, faceIndex, closestPoint);
  return hit;
}
 
// partition faces around the median face
uint32_t AABBTree::PartitionMedian(Node& n, uint32_t* faces, uint32_t numFaces)
{
  FaceSorter predicate(*m_vertices, *m_indices, n.m_extents.GetSize().LongestAxis());
  std::nth_element(faces, faces + numFaces / 2, faces + numFaces, predicate);
 
  return numFaces / 2;
}
 
// partition faces based on the surface area heuristic
uint32_t AABBTree::PartitionSAH(Node&, uint32_t* faces, uint32_t numFaces)
{
  uint32_t bestAxis = 0;
  uint32_t bestIndex = 0;
  double bestCost = FLT_MAX;
 
  for (uint32_t a = 0; a < 3; ++a)
  {
    // sort faces by centroids
    FaceSorter predicate(*m_vertices, *m_indices, a);
    std::sort(faces, faces + numFaces, predicate);
 
    // two passes over data to calculate upper and lower bounds
    std::vector<double> cumulativeLower(numFaces);
    std::vector<double> cumulativeUpper(numFaces);
 
    VHACD::BoundsAABB lower;
    VHACD::BoundsAABB upper;
 
    for (uint32_t i = 0; i < numFaces; ++i)
    {
      lower.Union(m_faceBounds[faces[i]]);
      upper.Union(m_faceBounds[faces[numFaces - i - 1]]);
 
      cumulativeLower[i] = lower.SurfaceArea();
      cumulativeUpper[numFaces - i - 1] = upper.SurfaceArea();
    }
 
    double invTotalSA = double(1.0) / cumulativeUpper[0];
 
    // test all split positions
    for (uint32_t i = 0; i < numFaces - 1; ++i)
    {
      double pBelow = cumulativeLower[i] * invTotalSA;
      double pAbove = cumulativeUpper[i] * invTotalSA;
 
      double cost = double(0.125) + (pBelow * i + pAbove * (numFaces - i));
      if (cost <= bestCost)
      {
        bestCost = cost;
        bestIndex = i;
        bestAxis = a;
      }
    }
  }
 
  // re-sort by best axis
  FaceSorter predicate(*m_vertices, *m_indices, bestAxis);
  std::sort(faces, faces + numFaces, predicate);
 
  return bestIndex + 1;
}
 
void AABBTree::Build()
{
  const uint32_t numFaces = uint32_t(m_indices->size());
 
  // build initial list of faces
  m_faces.reserve(numFaces);
 
  // calculate bounds of each face and store
  m_faceBounds.reserve(numFaces);
 
  std::vector<VHACD::BoundsAABB> stack;
  for (uint32_t i = 0; i < numFaces; ++i)
  {
    VHACD::BoundsAABB top = CalculateFaceBounds(&i, 1);
 
    m_faces.push_back(i);
    m_faceBounds.push_back(top);
  }
 
  m_nodes.reserve(uint32_t(numFaces * double(1.5)));
 
  // allocate space for all the nodes
  m_freeNode = 1;
 
  // start building
  BuildRecursive(0, m_faces.data(), numFaces);
 
  assert(s_depth == 0);
}
 
void AABBTree::BuildRecursive(uint32_t nodeIndex, uint32_t* faces, uint32_t numFaces)
{
  const uint32_t kMaxFacesPerLeaf = 6;
 
  // if we've run out of nodes allocate some more
  if (nodeIndex >= m_nodes.size())
  {
    uint32_t s = std::max(uint32_t(double(1.5) * m_nodes.size()), 512U);
    m_nodes.resize(s);
  }
 
  // a reference to the current node, need to be careful here as this reference may become invalid if array is resized
  Node& n = m_nodes[nodeIndex];
 
  // track max tree depth
  ++s_depth;
  m_treeDepth = std::max(m_treeDepth, s_depth);
 
  n.m_extents = CalculateFaceBounds(faces, numFaces);
 
  // calculate bounds of faces and add node
  if (numFaces <= kMaxFacesPerLeaf)
  {
    n.m_faces = faces;
    n.m_numFaces = numFaces;
 
    ++m_leafNodes;
  }
  else
  {
    ++m_innerNodes;
 
    // face counts for each branch
    const uint32_t leftCount = PartitionMedian(n, faces, numFaces);
    // const uint32_t leftCount = PartitionSAH(n, faces, numFaces);
    const uint32_t rightCount = numFaces - leftCount;
 
    // alloc 2 nodes
    m_nodes[nodeIndex].m_children = m_freeNode;
 
    // allocate two nodes
    m_freeNode += 2;
 
    // split faces in half and build each side recursively
    BuildRecursive(m_nodes[nodeIndex].m_children + 0, faces, leftCount);
    BuildRecursive(m_nodes[nodeIndex].m_children + 1, faces + leftCount, rightCount);
  }
 
  --s_depth;
}
 
void AABBTree::TraceRecursive(uint32_t nodeIndex,
                              const VHACD::Vect3& start,
                              const VHACD::Vect3& dir,
                              double& outT,
                              double& outU,
                              double& outV,
                              double& outW,
                              double& faceSign,
                              uint32_t& faceIndex) const
{
  const Node& node = m_nodes[nodeIndex];
 
  if (node.m_faces == NULL)
  {
    // find closest node
    const Node& leftChild = m_nodes[node.m_children + 0];
    const Node& rightChild = m_nodes[node.m_children + 1];
 
    double dist[2] = { FLT_MAX, FLT_MAX };
 
    IntersectRayAABB(start, dir, leftChild.m_extents, dist[0]);
    IntersectRayAABB(start, dir, rightChild.m_extents, dist[1]);
 
    uint32_t closest = 0;
    uint32_t furthest = 1;
 
    if (dist[1] < dist[0])
    {
      closest = 1;
      furthest = 0;
    }
 
    if (dist[closest] < outT)
    {
      TraceRecursive(node.m_children + closest, start, dir, outT, outU, outV, outW, faceSign, faceIndex);
    }
 
    if (dist[furthest] < outT)
    {
      TraceRecursive(node.m_children + furthest, start, dir, outT, outU, outV, outW, faceSign, faceIndex);
    }
  }
  else
  {
    double t, u, v, w, s;
 
    for (uint32_t i = 0; i < node.m_numFaces; ++i)
    {
      uint32_t indexStart = node.m_faces[i];
 
      const VHACD::Vect3& a = (*m_vertices)[(*m_indices)[indexStart].mI0];
      const VHACD::Vect3& b = (*m_vertices)[(*m_indices)[indexStart].mI1];
      const VHACD::Vect3& c = (*m_vertices)[(*m_indices)[indexStart].mI2];
      if (IntersectRayTriTwoSided(start, dir, a, b, c, t, u, v, w, s, NULL))
      {
        if (t < outT)
        {
          outT = t;
          outU = u;
          outV = v;
          outW = w;
          faceSign = s;
          faceIndex = node.m_faces[i];
        }
      }
    }
  }
}
 
bool AABBTree::GetClosestPointWithinDistance(const VHACD::Vect3& point,
                                             const double maxDis,
                                             double& dis,
                                             double& v,
                                             double& w,
                                             uint32_t& faceIndex,
                                             VHACD::Vect3& closest) const
{
  dis = maxDis;
  faceIndex = uint32_t(~0);
  double disSq = dis * dis;
 
  GetClosestPointWithinDistanceSqRecursive(0, point, disSq, v, w, faceIndex, closest);
  dis = sqrt(disSq);
 
  return (faceIndex < (~(static_cast<unsigned int>(0))));
}
 
void AABBTree::GetClosestPointWithinDistanceSqRecursive(uint32_t nodeIndex,
                                                        const VHACD::Vect3& point,
                                                        double& outDisSq,
                                                        double& outV,
                                                        double& outW,
                                                        uint32_t& outFaceIndex,
                                                        VHACD::Vect3& closestPoint) const
{
  const Node& node = m_nodes[nodeIndex];
 
  if (node.m_faces == nullptr)
  {
    // find closest node
    const Node& leftChild = m_nodes[node.m_children + 0];
    const Node& rightChild = m_nodes[node.m_children + 1];
 
    // double dist[2] = { FLT_MAX, FLT_MAX };
    VHACD::Vect3 lp = leftChild.m_extents.ClosestPoint(point);
    VHACD::Vect3 rp = rightChild.m_extents.ClosestPoint(point);
 
    uint32_t closest = 0;
    uint32_t furthest = 1;
    double dcSq = (point - lp).GetNormSquared();
    double dfSq = (point - rp).GetNormSquared();
    if (dfSq < dcSq)
    {
      closest = 1;
      furthest = 0;
      std::swap(dfSq, dcSq);
    }
 
    if (dcSq < outDisSq)
    {
      GetClosestPointWithinDistanceSqRecursive(
          node.m_children + closest, point, outDisSq, outV, outW, outFaceIndex, closestPoint);
    }
 
    if (dfSq < outDisSq)
    {
      GetClosestPointWithinDistanceSqRecursive(
          node.m_children + furthest, point, outDisSq, outV, outW, outFaceIndex, closestPoint);
    }
  }
  else
  {
    double v, w;
    for (uint32_t i = 0; i < node.m_numFaces; ++i)
    {
      uint32_t indexStart = node.m_faces[i];
 
      const VHACD::Vect3& a = (*m_vertices)[(*m_indices)[indexStart].mI0];
      const VHACD::Vect3& b = (*m_vertices)[(*m_indices)[indexStart].mI1];
      const VHACD::Vect3& c = (*m_vertices)[(*m_indices)[indexStart].mI2];
 
      VHACD::Vect3 cp = ClosestPointOnTriangle(a, b, c, point, v, w);
      double disSq = (cp - point).GetNormSquared();
 
      if (disSq < outDisSq)
      {
        closestPoint = cp;
        outDisSq = disSq;
        outV = v;
        outW = w;
        outFaceIndex = node.m_faces[i];
      }
    }
  }
}
 
VHACD::BoundsAABB AABBTree::CalculateFaceBounds(uint32_t* faces, uint32_t numFaces)
{
  VHACD::Vect3 minExtents(FLT_MAX);
  VHACD::Vect3 maxExtents(-FLT_MAX);
 
  // calculate face bounds
  for (uint32_t i = 0; i < numFaces; ++i)
  {
    VHACD::Vect3 a = (*m_vertices)[(*m_indices)[faces[i]].mI0];
    VHACD::Vect3 b = (*m_vertices)[(*m_indices)[faces[i]].mI1];
    VHACD::Vect3 c = (*m_vertices)[(*m_indices)[faces[i]].mI2];
 
    minExtents = a.CWiseMin(minExtents);
    maxExtents = a.CWiseMax(maxExtents);
 
    minExtents = b.CWiseMin(minExtents);
    maxExtents = b.CWiseMax(maxExtents);
 
    minExtents = c.CWiseMin(minExtents);
    maxExtents = c.CWiseMax(maxExtents);
  }
 
  return VHACD::BoundsAABB(minExtents, maxExtents);
}
 
enum class VoxelValue : uint8_t
{
  PRIMITIVE_UNDEFINED = 0,
  PRIMITIVE_OUTSIDE_SURFACE_TOWALK = 1,
  PRIMITIVE_OUTSIDE_SURFACE = 2,
  PRIMITIVE_INSIDE_SURFACE = 3,
  PRIMITIVE_ON_SURFACE = 4
};
 
class Volume
{
public:
  void Voxelize(const std::vector<VHACD::Vertex>& points,
                const std::vector<VHACD::Triangle>& triangles,
                const size_t dim,
                FillMode fillMode,
                const AABBTree& aabbTree);
 
  void RaycastFill(const AABBTree& aabbTree);
 
  void SetVoxel(const size_t i, const size_t j, const size_t k, VoxelValue value);
 
  VoxelValue& GetVoxel(const size_t i, const size_t j, const size_t k);
 
  const VoxelValue& GetVoxel(const size_t i, const size_t j, const size_t k) const;
 
  const std::vector<Voxel>& GetSurfaceVoxels() const;
  const std::vector<Voxel>& GetInteriorVoxels() const;
 
  double GetScale() const;
  const VHACD::BoundsAABB& GetBounds() const;
  const VHACD::Vector3<uint32_t>& GetDimensions() const;
 
  VHACD::BoundsAABB m_bounds;
  double m_scale{ 1.0 };
  VHACD::Vector3<uint32_t> m_dim{ 0 };
  size_t m_numVoxelsOnSurface{ 0 };
  size_t m_numVoxelsInsideSurface{ 0 };
  size_t m_numVoxelsOutsideSurface{ 0 };
  std::vector<VoxelValue> m_data;
 
private:
  void MarkOutsideSurface(const size_t i0,
                          const size_t j0,
                          const size_t k0,
                          const size_t i1,
                          const size_t j1,
                          const size_t k1);
  void FillOutsideSurface();
 
  void FillInsideSurface();
 
  std::vector<VHACD::Voxel> m_surfaceVoxels;
  std::vector<VHACD::Voxel> m_interiorVoxels;
};
 
bool PlaneBoxOverlap(const VHACD::Vect3& normal, const VHACD::Vect3& vert, const VHACD::Vect3& maxbox)
{
  int32_t q;
  VHACD::Vect3 vmin;
  VHACD::Vect3 vmax;
  double v;
  for (q = 0; q < 3; q++)
  {
    v = vert[q];
    if (normal[q] > double(0.0))
    {
      vmin[q] = -maxbox[q] - v;
      vmax[q] = maxbox[q] - v;
    }
    else
    {
      vmin[q] = maxbox[q] - v;
      vmax[q] = -maxbox[q] - v;
    }
  }
  if (normal.Dot(vmin) > double(0.0))
    return false;
  if (normal.Dot(vmax) >= double(0.0))
    return true;
  return false;
}
 
bool AxisTest(double a,
              double b,
              double fa,
              double fb,
              double v0,
              double v1,
              double v2,
              double v3,
              double boxHalfSize1,
              double boxHalfSize2)
{
  double p0 = a * v0 + b * v1;
  double p1 = a * v2 + b * v3;
 
  double min = std::min(p0, p1);
  double max = std::max(p0, p1);
 
  double rad = fa * boxHalfSize1 + fb * boxHalfSize2;
  if (min > rad || max < -rad)
  {
    return false;
  }
 
  return true;
}
 
bool TriBoxOverlap(const VHACD::Vect3& boxCenter,
                   const VHACD::Vect3& boxHalfSize,
                   const VHACD::Vect3& triVer0,
                   const VHACD::Vect3& triVer1,
                   const VHACD::Vect3& triVer2)
{
  /*    use separating axis theorem to test overlap between triangle and box */
  /*    need to test for overlap in these directions: */
  /*    1) the {x,y,z}-directions (actually, since we use the AABB of the triangle */
  /*       we do not even need to test these) */
  /*    2) normal of the triangle */
  /*    3) crossproduct(edge from tri, {x,y,z}-direction) */
  /*       this gives 3x3=9 more tests */
 
  VHACD::Vect3 v0 = triVer0 - boxCenter;
  VHACD::Vect3 v1 = triVer1 - boxCenter;
  VHACD::Vect3 v2 = triVer2 - boxCenter;
  VHACD::Vect3 e0 = v1 - v0;
  VHACD::Vect3 e1 = v2 - v1;
  VHACD::Vect3 e2 = v0 - v2;
 
  /* This is the fastest branch on Sun */
  /* move everything so that the boxcenter is in (0,0,0) */
 
  /* Bullet 3:  */
  /*  test the 9 tests first (this was faster) */
  double fex = fabs(e0[0]);
  double fey = fabs(e0[1]);
  double fez = fabs(e0[2]);
 
  /*
   * These should use Get*() instead of subscript for consistency, but the function calls are long enough already
   */
  if (!AxisTest(e0[2], -e0[1], fez, fey, v0[1], v0[2], v2[1], v2[2], boxHalfSize[1], boxHalfSize[2]))
    return 0;  // X01
  if (!AxisTest(-e0[2], e0[0], fez, fex, v0[0], v0[2], v2[0], v2[2], boxHalfSize[0], boxHalfSize[2]))
    return 0;  // Y02
  if (!AxisTest(e0[1], -e0[0], fey, fex, v1[0], v1[1], v2[0], v2[1], boxHalfSize[0], boxHalfSize[1]))
    return 0;  // Z12
 
  fex = fabs(e1[0]);
  fey = fabs(e1[1]);
  fez = fabs(e1[2]);
 
  if (!AxisTest(e1[2], -e1[1], fez, fey, v0[1], v0[2], v2[1], v2[2], boxHalfSize[1], boxHalfSize[2]))
    return 0;  // X01
  if (!AxisTest(-e1[2], e1[0], fez, fex, v0[0], v0[2], v2[0], v2[2], boxHalfSize[0], boxHalfSize[2]))
    return 0;  // Y02
  if (!AxisTest(e1[1], -e1[0], fey, fex, v0[0], v0[1], v1[0], v1[1], boxHalfSize[0], boxHalfSize[2]))
    return 0;  // Z0
 
  fex = fabs(e2[0]);
  fey = fabs(e2[1]);
  fez = fabs(e2[2]);
 
  if (!AxisTest(e2[2], -e2[1], fez, fey, v0[1], v0[2], v1[1], v1[2], boxHalfSize[1], boxHalfSize[2]))
    return 0;  // X2
  if (!AxisTest(-e2[2], e2[0], fez, fex, v0[0], v0[2], v1[0], v1[2], boxHalfSize[0], boxHalfSize[2]))
    return 0;  // Y1
  if (!AxisTest(e2[1], -e2[0], fey, fex, v1[0], v1[1], v2[0], v2[1], boxHalfSize[0], boxHalfSize[1]))
    return 0;  // Z12
 
  /* Bullet 1: */
  /*  first test overlap in the {x,y,z}-directions */
  /*  find min, max of the triangle each direction, and test for overlap in */
  /*  that direction -- this is equivalent to testing a minimal AABB around */
  /*  the triangle against the AABB */
 
  /* test in 0-direction */
  double min = std::min({ v0.GetX(), v1.GetX(), v2.GetX() });
  double max = std::max({ v0.GetX(), v1.GetX(), v2.GetX() });
  if (min > boxHalfSize[0] || max < -boxHalfSize[0])
    return false;
 
  /* test in 1-direction */
  min = std::min({ v0.GetY(), v1.GetY(), v2.GetY() });
  max = std::max({ v0.GetY(), v1.GetY(), v2.GetY() });
  if (min > boxHalfSize[1] || max < -boxHalfSize[1])
    return false;
 
  /* test in getZ-direction */
  min = std::min({ v0.GetZ(), v1.GetZ(), v2.GetZ() });
  max = std::max({ v0.GetZ(), v1.GetZ(), v2.GetZ() });
  if (min > boxHalfSize[2] || max < -boxHalfSize[2])
    return false;
 
  /* Bullet 2: */
  /*  test if the box intersects the plane of the triangle */
  /*  compute plane equation of triangle: normal*x+d=0 */
  VHACD::Vect3 normal = e0.Cross(e1);
 
  if (!PlaneBoxOverlap(normal, v0, boxHalfSize))
    return false;
  return true; /* box and triangle overlaps */
}
 
void Volume::Voxelize(const std::vector<VHACD::Vertex>& points,
                      const std::vector<VHACD::Triangle>& indices,
                      const size_t dimensions,
                      FillMode fillMode,
                      const AABBTree& aabbTree)
{
  double a = std::pow(dimensions, 0.33);
  size_t dim = a * double(1.5);
  dim = std::max(dim, size_t(32));
 
  if (points.size() == 0)
  {
    return;
  }
 
  m_bounds = BoundsAABB(points);
 
  VHACD::Vect3 d = m_bounds.GetSize();
  double r;
  // Equal comparison is important here to avoid taking the last branch when d[0] == d[1] with d[2] being the smallest
  // dimension. That would lead to dimensions in i and j to be a lot bigger than expected and make the amount of
  // voxels in the volume totally unmanageable.
  if (d[0] >= d[1] && d[0] >= d[2])
  {
    r = d[0];
    m_dim[0] = uint32_t(dim);
    m_dim[1] = uint32_t(2 + static_cast<size_t>(dim * d[1] / d[0]));
    m_dim[2] = uint32_t(2 + static_cast<size_t>(dim * d[2] / d[0]));
  }
  else if (d[1] >= d[0] && d[1] >= d[2])
  {
    r = d[1];
    m_dim[1] = uint32_t(dim);
    m_dim[0] = uint32_t(2 + static_cast<size_t>(dim * d[0] / d[1]));
    m_dim[2] = uint32_t(2 + static_cast<size_t>(dim * d[2] / d[1]));
  }
  else
  {
    r = d[2];
    m_dim[2] = uint32_t(dim);
    m_dim[0] = uint32_t(2 + static_cast<size_t>(dim * d[0] / d[2]));
    m_dim[1] = uint32_t(2 + static_cast<size_t>(dim * d[1] / d[2]));
  }
 
  m_scale = r / (dim - 1);
  double invScale = (dim - 1) / r;
 
  m_data = std::vector<VoxelValue>(m_dim[0] * m_dim[1] * m_dim[2], VoxelValue::PRIMITIVE_UNDEFINED);
  m_numVoxelsOnSurface = 0;
  m_numVoxelsInsideSurface = 0;
  m_numVoxelsOutsideSurface = 0;
 
  VHACD::Vect3 p[3];
  VHACD::Vect3 boxcenter;
  VHACD::Vect3 pt;
  const VHACD::Vect3 boxhalfsize(double(0.5));
  for (size_t t = 0; t < indices.size(); ++t)
  {
    size_t i0, j0, k0;
    size_t i1, j1, k1;
    VHACD::Vector3<uint32_t> tri = indices[t];
    for (int32_t c = 0; c < 3; ++c)
    {
      pt = points[tri[c]];
 
      p[c] = (pt - m_bounds.GetMin()) * invScale;
 
      size_t i = static_cast<size_t>(p[c][0] + double(0.5));
      size_t j = static_cast<size_t>(p[c][1] + double(0.5));
      size_t k = static_cast<size_t>(p[c][2] + double(0.5));
 
      assert(i < m_dim[0] && j < m_dim[1] && k < m_dim[2]);
 
      if (c == 0)
      {
        i0 = i1 = i;
        j0 = j1 = j;
        k0 = k1 = k;
      }
      else
      {
        i0 = std::min(i0, i);
        j0 = std::min(j0, j);
        k0 = std::min(k0, k);
 
        i1 = std::max(i1, i);
        j1 = std::max(j1, j);
        k1 = std::max(k1, k);
      }
    }
    if (i0 > 0)
      --i0;
    if (j0 > 0)
      --j0;
    if (k0 > 0)
      --k0;
    if (i1 < m_dim[0])
      ++i1;
    if (j1 < m_dim[1])
      ++j1;
    if (k1 < m_dim[2])
      ++k1;
    for (size_t i_id = i0; i_id < i1; ++i_id)
    {
      boxcenter[0] = uint32_t(i_id);
      for (size_t j_id = j0; j_id < j1; ++j_id)
      {
        boxcenter[1] = uint32_t(j_id);
        for (size_t k_id = k0; k_id < k1; ++k_id)
        {
          boxcenter[2] = uint32_t(k_id);
          bool res = TriBoxOverlap(boxcenter, boxhalfsize, p[0], p[1], p[2]);
          VoxelValue& value = GetVoxel(i_id, j_id, k_id);
          if (res && value == VoxelValue::PRIMITIVE_UNDEFINED)
          {
            value = VoxelValue::PRIMITIVE_ON_SURFACE;
            ++m_numVoxelsOnSurface;
            m_surfaceVoxels.emplace_back(uint32_t(i_id), uint32_t(j_id), uint32_t(k_id));
          }
        }
      }
    }
  }
 
  if (fillMode == FillMode::SURFACE_ONLY)
  {
    const size_t i0_local = m_dim[0];
    const size_t j0_local = m_dim[1];
    const size_t k0_local = m_dim[2];
    for (size_t i_id = 0; i_id < i0_local; ++i_id)
    {
      for (size_t j_id = 0; j_id < j0_local; ++j_id)
      {
        for (size_t k_id = 0; k_id < k0_local; ++k_id)
        {
          const VoxelValue& voxel = GetVoxel(i_id, j_id, k_id);
          if (voxel != VoxelValue::PRIMITIVE_ON_SURFACE)
          {
            SetVoxel(i_id, j_id, k_id, VoxelValue::PRIMITIVE_OUTSIDE_SURFACE);
          }
        }
      }
    }
  }
  else if (fillMode == FillMode::FLOOD_FILL)
  {
    /*
     * Marking the outside edges of the voxel cube to be outside surfaces to walk
     */
    MarkOutsideSurface(0, 0, 0, m_dim[0], m_dim[1], 1);
    MarkOutsideSurface(0, 0, m_dim[2] - 1, m_dim[0], m_dim[1], m_dim[2]);
    MarkOutsideSurface(0, 0, 0, m_dim[0], 1, m_dim[2]);
    MarkOutsideSurface(0, m_dim[1] - 1, 0, m_dim[0], m_dim[1], m_dim[2]);
    MarkOutsideSurface(0, 0, 0, 1, m_dim[1], m_dim[2]);
    MarkOutsideSurface(m_dim[0] - 1, 0, 0, m_dim[0], m_dim[1], m_dim[2]);
    FillOutsideSurface();
    FillInsideSurface();
  }
  else if (fillMode == FillMode::RAYCAST_FILL)
  {
    RaycastFill(aabbTree);
  }
}
 
void Volume::RaycastFill(const AABBTree& aabbTree)
{
  const uint32_t i0 = m_dim[0];
  const uint32_t j0 = m_dim[1];
  const uint32_t k0 = m_dim[2];
 
  size_t maxSize = i0 * j0 * k0;
 
  std::vector<Voxel> temp;
  temp.reserve(maxSize);
  uint32_t count{ 0 };
  m_numVoxelsInsideSurface = 0;
  for (uint32_t i = 0; i < i0; ++i)
  {
    for (uint32_t j = 0; j < j0; ++j)
    {
      for (uint32_t k = 0; k < k0; ++k)
      {
        VoxelValue& voxel = GetVoxel(i, j, k);
        if (voxel != VoxelValue::PRIMITIVE_ON_SURFACE)
        {
          VHACD::Vect3 start = VHACD::Vect3(i, j, k) * m_scale + m_bounds.GetMin();
 
          uint32_t insideCount = 0;
          uint32_t outsideCount = 0;
 
          VHACD::Vect3 directions[6] = {
            VHACD::Vect3(1, 0, 0), VHACD::Vect3(-1, 0, 0),  // this was 1, 0, 0 in the original code, but looks wrong
            VHACD::Vect3(0, 1, 0), VHACD::Vect3(0, -1, 0), VHACD::Vect3(0, 0, 1), VHACD::Vect3(0, 0, -1)
          };
 
          for (uint32_t r = 0; r < 6; r++)
          {
            aabbTree.TraceRay(start, directions[r], insideCount, outsideCount);
            // Early out if we hit the outside of the mesh
            if (outsideCount)
            {
              break;
            }
            // Early out if we accumulated 3 inside hits
            if (insideCount >= 3)
            {
              break;
            }
          }
 
          if (outsideCount == 0 && insideCount >= 3)
          {
            voxel = VoxelValue::PRIMITIVE_INSIDE_SURFACE;
            temp.emplace_back(i, j, k);
            count++;
            m_numVoxelsInsideSurface++;
          }
          else
          {
            voxel = VoxelValue::PRIMITIVE_OUTSIDE_SURFACE;
          }
        }
      }
    }
  }
 
  if (count)
  {
    m_interiorVoxels = std::move(temp);
  }
}
 
void Volume::SetVoxel(const size_t i, const size_t j, const size_t k, VoxelValue value)
{
  assert(i < m_dim[0]);
  assert(j < m_dim[1]);
  assert(k < m_dim[2]);
 
  m_data[k + j * m_dim[2] + i * m_dim[1] * m_dim[2]] = value;
}
 
VoxelValue& Volume::GetVoxel(const size_t i, const size_t j, const size_t k)
{
  assert(i < m_dim[0]);
  assert(j < m_dim[1]);
  assert(k < m_dim[2]);
  return m_data[k + j * m_dim[2] + i * m_dim[1] * m_dim[2]];
}
 
const VoxelValue& Volume::GetVoxel(const size_t i, const size_t j, const size_t k) const
{
  assert(i < m_dim[0]);
  assert(j < m_dim[1]);
  assert(k < m_dim[2]);
  return m_data[k + j * m_dim[2] + i * m_dim[1] * m_dim[2]];
}
 
const std::vector<Voxel>& Volume::GetSurfaceVoxels() const { return m_surfaceVoxels; }
 
const std::vector<Voxel>& Volume::GetInteriorVoxels() const { return m_interiorVoxels; }
 
double Volume::GetScale() const { return m_scale; }
 
const VHACD::BoundsAABB& Volume::GetBounds() const { return m_bounds; }
 
const VHACD::Vector3<uint32_t>& Volume::GetDimensions() const { return m_dim; }
 
void Volume::MarkOutsideSurface(const size_t i0,
                                const size_t j0,
                                const size_t k0,
                                const size_t i1,
                                const size_t j1,
                                const size_t k1)
{
  for (size_t i = i0; i < i1; ++i)
  {
    for (size_t j = j0; j < j1; ++j)
    {
      for (size_t k = k0; k < k1; ++k)
      {
        VoxelValue& v = GetVoxel(i, j, k);
        if (v == VoxelValue::PRIMITIVE_UNDEFINED)
        {
          v = VoxelValue::PRIMITIVE_OUTSIDE_SURFACE_TOWALK;
        }
      }
    }
  }
}
 
inline void WalkForward(int64_t start, int64_t end, VoxelValue* ptr, int64_t stride, int64_t maxDistance)
{
  for (int64_t i = start, count = 0; count < maxDistance && i < end && *ptr == VoxelValue::PRIMITIVE_UNDEFINED;
       ++i, ptr += stride, ++count)
  {
    *ptr = VoxelValue::PRIMITIVE_OUTSIDE_SURFACE_TOWALK;
  }
}
 
inline void WalkBackward(int64_t start, int64_t end, VoxelValue* ptr, int64_t stride, int64_t maxDistance)
{
  for (int64_t i = start, count = 0; count < maxDistance && i >= end && *ptr == VoxelValue::PRIMITIVE_UNDEFINED;
       --i, ptr -= stride, ++count)
  {
    *ptr = VoxelValue::PRIMITIVE_OUTSIDE_SURFACE_TOWALK;
  }
}
 
void Volume::FillOutsideSurface()
{
  size_t voxelsWalked = 0;
  const int64_t i0 = m_dim[0];
  const int64_t j0 = m_dim[1];
  const int64_t k0 = m_dim[2];
 
  // Avoid striding too far in each direction to stay in L1 cache as much as possible.
  // The cache size required for the walk is roughly (4 * walkDistance * 64) since
  // the k direction doesn't count as it's walking byte per byte directly in a cache lines.
  // ~16k is required for a walk distance of 64 in each directions.
  const size_t walkDistance = 64;
 
  // using the stride directly instead of calling GetVoxel for each iterations saves
  // a lot of multiplications and pipeline stalls due to data dependencies on imul.
  const size_t istride = &GetVoxel(1, 0, 0) - &GetVoxel(0, 0, 0);
  const size_t jstride = &GetVoxel(0, 1, 0) - &GetVoxel(0, 0, 0);
  const size_t kstride = &GetVoxel(0, 0, 1) - &GetVoxel(0, 0, 0);
 
  // It might seem counter intuitive to go over the whole voxel range multiple times
  // but since we do the run in memory order, it leaves us with far fewer cache misses
  // than a BFS algorithm and it has the additional benefit of not requiring us to
  // store and manipulate a fifo for recursion that might become huge when the number
  // of voxels is large.
  // This will outperform the BFS algorithm by several orders of magnitude in practice.
  do
  {
    voxelsWalked = 0;
    for (int64_t i = 0; i < i0; ++i)
    {
      for (int64_t j = 0; j < j0; ++j)
      {
        for (int64_t k = 0; k < k0; ++k)
        {
          VoxelValue& voxel = GetVoxel(i, j, k);
          if (voxel == VoxelValue::PRIMITIVE_OUTSIDE_SURFACE_TOWALK)
          {
            voxelsWalked++;
            voxel = VoxelValue::PRIMITIVE_OUTSIDE_SURFACE;
 
            // walk in each direction to mark other voxel that should be walked.
            // this will generate a 3d pattern that will help the overall
            // algorithm converge faster while remaining cache friendly.
            WalkForward(k + 1, k0, &voxel + kstride, kstride, walkDistance);
            WalkBackward(k - 1, 0, &voxel - kstride, kstride, walkDistance);
 
            WalkForward(j + 1, j0, &voxel + jstride, jstride, walkDistance);
            WalkBackward(j - 1, 0, &voxel - jstride, jstride, walkDistance);
 
            WalkForward(i + 1, i0, &voxel + istride, istride, walkDistance);
            WalkBackward(i - 1, 0, &voxel - istride, istride, walkDistance);
          }
        }
      }
    }
 
    m_numVoxelsOutsideSurface += voxelsWalked;
  } while (voxelsWalked != 0);
}
 
void Volume::FillInsideSurface()
{
  const uint32_t i0 = uint32_t(m_dim[0]);
  const uint32_t j0 = uint32_t(m_dim[1]);
  const uint32_t k0 = uint32_t(m_dim[2]);
 
  size_t maxSize = i0 * j0 * k0;
 
  std::vector<Voxel> temp;
  temp.reserve(maxSize);
  uint32_t count{ 0 };
 
  for (uint32_t i = 0; i < i0; ++i)
  {
    for (uint32_t j = 0; j < j0; ++j)
    {
      for (uint32_t k = 0; k < k0; ++k)
      {
        VoxelValue& v = GetVoxel(i, j, k);
        if (v == VoxelValue::PRIMITIVE_UNDEFINED)
        {
          v = VoxelValue::PRIMITIVE_INSIDE_SURFACE;
          temp.emplace_back(i, j, k);
          count++;
          ++m_numVoxelsInsideSurface;
        }
      }
    }
  }
 
  if (count)
  {
    m_interiorVoxels = std::move(temp);
  }
}
 
//******************************************************************************************
//  ShrinkWrap helper class
//******************************************************************************************
// This is a code snippet which 'shrinkwraps' a convex hull
// to a source mesh.
//
// It is a somewhat complicated algorithm. It works as follows:
//
// * Step #1 : Compute the mean unit normal vector for each vertex in the convex hull
// * Step #2 : For each vertex in the conex hull we project is slightly outwards along the mean normal vector
// * Step #3 : We then raycast from this slightly extruded point back into the opposite direction of the mean normal
// vector
//             resulting in a raycast from slightly beyond the vertex in the hull into the source mesh we are trying
//             to 'shrink wrap' against
// * Step #4 : If the raycast fails we leave the original vertex alone
// * Step #5 : If the raycast hits a backface we leave the original vertex alone
// * Step #6 : If the raycast hits too far away (no more than a certain threshold distance) we live it alone
// * Step #7 : If the point we hit on the source mesh is not still within the convex hull, we reject it.
// * Step #8 : If all of the previous conditions are met, then we take the raycast hit location as the 'new position'
// * Step #9 : Once all points have been projected, if possible, we need to recompute the convex hull again based on
// these shrinkwrapped points
// * Step #10 : In theory that should work.. let's see...
 
//***********************************************************************************************
// QuickHull implementation
//***********************************************************************************************
 
// Quickhull base class holding the hull during construction
class QuickHull
{
public:
  uint32_t ComputeConvexHull(const std::vector<VHACD::Vertex>& vertices, uint32_t maxHullVertices);
 
  const std::vector<VHACD::Vertex>& GetVertices() const;
  const std::vector<VHACD::Triangle>& GetIndices() const;
 
private:
  std::vector<VHACD::Vertex> m_vertices;
  std::vector<VHACD::Triangle> m_indices;
};
 
uint32_t QuickHull::ComputeConvexHull(const std::vector<VHACD::Vertex>& vertices, uint32_t maxHullVertices)
{
  m_indices.clear();
 
  VHACD::ConvexHull ch(vertices, double(0.0001), maxHullVertices);
 
  auto& vlist = ch.GetVertexPool();
  if (!vlist.empty())
  {
    size_t vcount = vlist.size();
    m_vertices.resize(vcount);
    std::copy(vlist.begin(), vlist.end(), m_vertices.begin());
  }
 
  for (std::list<ConvexHullFace>::const_iterator node = ch.GetList().begin(); node != ch.GetList().end(); ++node)
  {
    const VHACD::ConvexHullFace& face = *node;
    m_indices.emplace_back(face.m_index[0], face.m_index[1], face.m_index[2]);
  }
 
  return uint32_t(m_indices.size());
}
 
const std::vector<VHACD::Vertex>& QuickHull::GetVertices() const { return m_vertices; }
 
const std::vector<VHACD::Triangle>& QuickHull::GetIndices() const { return m_indices; }
 
//******************************************************************************************
// Implementation of the ShrinkWrap function
//******************************************************************************************
 
void ShrinkWrap(SimpleMesh& sourceConvexHull,
                const AABBTree& aabbTree,
                uint32_t maxHullVertexCount,
                double distanceThreshold,
                bool doShrinkWrap)
{
  std::vector<VHACD::Vertex> verts;  // New verts for the new convex hull
  verts.reserve(sourceConvexHull.m_vertices.size());
  // Examine each vertex and see if it is within the voxel distance.
  // If it is, then replace the point with the shrinkwrapped / projected point
  for (uint32_t j = 0; j < sourceConvexHull.m_vertices.size(); j++)
  {
    VHACD::Vertex& p = sourceConvexHull.m_vertices[j];
    if (doShrinkWrap)
    {
      VHACD::Vect3 closest;
      if (aabbTree.GetClosestPointWithinDistance(p, distanceThreshold, closest))
      {
        p = closest;
      }
    }
    verts.emplace_back(p);
  }
  // Final step is to recompute the convex hull
  VHACD::QuickHull qh;
  uint32_t tcount = qh.ComputeConvexHull(verts, maxHullVertexCount);
  if (tcount)
  {
    sourceConvexHull.m_vertices = qh.GetVertices();
    sourceConvexHull.m_indices = qh.GetIndices();
  }
}
 
//********************************************************************************************************************
 
#if !VHACD_DISABLE_THREADING
 
//********************************************************************************************************************
// Definition of the ThreadPool
//********************************************************************************************************************
 
class ThreadPool
{
public:
  ThreadPool();
  ThreadPool(int worker);
  ~ThreadPool();
  template <typename F, typename... Args>
  auto enqueue(F&& f, Args&&... args)
#ifndef __cpp_lib_is_invocable
      -> std::future<typename std::result_of<F(Args...)>::type>;
#else
      -> std::future<typename std::invoke_result_t<F, Args...>>;
#endif
private:
  std::vector<std::thread> workers;
  std::deque<std::function<void()>> tasks;
  std::mutex task_mutex;
  std::condition_variable cv;
  bool closed;
  int count;
};
 
ThreadPool::ThreadPool() : ThreadPool(1) {}
 
ThreadPool::ThreadPool(int worker) : closed(false), count(0)
{
  workers.reserve(worker);
  for (int i = 0; i < worker; i++)
  {
    workers.emplace_back([this] {
      std::unique_lock<std::mutex> lock(this->task_mutex);
      while (true)
      {
        while (this->tasks.empty())
        {
          if (this->closed)
          {
            return;
          }
          this->cv.wait(lock);
        }
        auto task = this->tasks.front();
        this->tasks.pop_front();
        lock.unlock();
        task();
        lock.lock();
      }
    });
  }
}
 
template <typename F, typename... Args>
auto ThreadPool::enqueue(F&& f, Args&&... args)
#ifndef __cpp_lib_is_invocable
    -> std::future<typename std::result_of<F(Args...)>::type>
#else
    -> std::future<typename std::invoke_result_t<F, Args...>>
#endif
{
#ifndef __cpp_lib_is_invocable
  using return_type = typename std::result_of<F(Args...)>::type;
#else
  using return_type = typename std::invoke_result_t<F, Args...>;
#endif
  auto task =
      std::make_shared<std::packaged_task<return_type()>>(std::bind(std::forward<F>(f), std::forward<Args>(args)...));
  auto result = task->get_future();
 
  {
    std::unique_lock<std::mutex> lock(task_mutex);
    if (!closed)
    {
      tasks.emplace_back([task] { (*task)(); });
      cv.notify_one();
    }
  }
 
  return result;
}
 
ThreadPool::~ThreadPool()
{
  {
    std::unique_lock<std::mutex> lock(task_mutex);
    closed = true;
  }
  cv.notify_all();
  for (auto&& worker : workers)
  {
    worker.join();
  }
}
#endif
 
enum class Stages
{
  COMPUTE_BOUNDS_OF_INPUT_MESH,
  REINDEXING_INPUT_MESH,
  CREATE_RAYCAST_MESH,
  VOXELIZING_INPUT_MESH,
  BUILD_INITIAL_CONVEX_HULL,
  PERFORMING_DECOMPOSITION,
  INITIALIZING_CONVEX_HULLS_FOR_MERGING,
  COMPUTING_COST_MATRIX,
  MERGING_CONVEX_HULLS,
  FINALIZING_RESULTS,
  NUM_STAGES
};
 
class VHACDCallbacks
{
public:
  virtual void ProgressUpdate(Stages stage, double stageProgress, const char* operation) = 0;
  virtual bool IsCanceled() const = 0;
 
  virtual ~VHACDCallbacks() = default;
};
 
enum class SplitAxis
{
  X_AXIS_NEGATIVE,
  X_AXIS_POSITIVE,
  Y_AXIS_NEGATIVE,
  Y_AXIS_POSITIVE,
  Z_AXIS_NEGATIVE,
  Z_AXIS_POSITIVE,
};
 
// This class represents a collection of voxels, the convex hull
// which surrounds them, and a triangle mesh representation of those voxels
class VoxelHull
{
public:
  // This method constructs a new VoxelHull based on a plane split of the parent
  // convex hull
  VoxelHull(const VoxelHull& parent, SplitAxis axis, uint32_t splitLoc);
 
  // Here we construct the initial convex hull around the
  // entire voxel set
  VoxelHull(Volume& voxels, const IVHACD::Parameters& params, VHACDCallbacks* callbacks);
 
  ~VoxelHull() = default;
 
  // Helper method to refresh the min/max voxel bounding region
  void MinMaxVoxelRegion(const Voxel& v);
 
  void BuildRaycastMesh();
 
  // We now compute the convex hull relative to a triangle mesh generated
  // from the voxels
  void ComputeConvexHull();
 
  // Returns true if this convex hull should be considered done
  bool IsComplete();
 
  // Convert a voxel position into it's correct double precision location
  VHACD::Vect3
  GetPoint(const int32_t x, const int32_t y, const int32_t z, const double scale, const VHACD::Vect3& bmin) const;
 
  // Sees if we have already got an index for this voxel position.
  // If the voxel position has already been indexed, we just return
  // that index value.
  // If not, then we convert it into the floating point position and
  // add it to the index map
  uint32_t GetVertexIndex(const VHACD::Vector3<uint32_t>& p);
 
  // This method will convert the voxels into an actual indexed triangle mesh of boxes
  // This serves two purposes.
  // The primary purpose is so that when we compute a convex hull it considered all of the points
  // for each voxel, not just the center point. If you don't do this, then the hulls don't fit the
  // mesh accurately enough.
  // The second reason we convert it into a triangle mesh is so that we can do raycasting against it
  // to search for the best splitting plane fairly quickly. That algorithm will be discussed in the
  // method which computes the best splitting plane.
  void BuildVoxelMesh();
 
  // Convert a single voxel position into an actual 3d box mesh comprised
  // of 12 triangles
  void AddVoxelBox(const Voxel& v);
 
  // Add the triangle represented by these 3 indices into the 'box' set of vertices
  // to the output mesh
  void AddTri(const std::array<VHACD::Vector3<uint32_t>, 8>& box, uint32_t i1, uint32_t i2, uint32_t i3);
 
  // Here we convert from voxel space to a 3d position, index it, and add
  // the triangle positions and indices for the output mesh
  void AddTriangle(const VHACD::Vector3<uint32_t>& p1,
                   const VHACD::Vector3<uint32_t>& p2,
                   const VHACD::Vector3<uint32_t>& p3);
 
  // When computing the split plane, we start by simply
  // taking the midpoint of the longest side. However,
  // we can also search the surface and look for the greatest
  // spot of concavity and use that as the split location.
  // This will make the convex decomposition more efficient
  // as it will tend to cut across the greatest point of
  // concavity on the surface.
  SplitAxis ComputeSplitPlane(uint32_t& location);
 
  VHACD::Vect3 GetPosition(const VHACD::Vector3<int32_t>& ip) const;
 
  double Raycast(const VHACD::Vector3<int32_t>& p1, const VHACD::Vector3<int32_t>& p2) const;
 
  bool FindConcavity(uint32_t idx, uint32_t& splitLoc);
 
  // Finding the greatest area of concavity..
  bool FindConcavityX(uint32_t& splitLoc);
 
  // Finding the greatest area of concavity..
  bool FindConcavityY(uint32_t& splitLoc);
 
  // Finding the greatest area of concavity..
  bool FindConcavityZ(uint32_t& splitLoc);
 
  // This operation is performed in a background thread.
  // It splits the voxels by a plane
  void PerformPlaneSplit();
 
  // Used only for debugging. Saves the voxelized mesh to disk
  // Optionally saves the original source mesh as well for comparison
  void SaveVoxelMesh(const SimpleMesh& inputMesh, bool saveVoxelMesh, bool saveSourceMesh);
 
  void SaveOBJ(const char* fname, const VoxelHull* h);
 
  void SaveOBJ(const char* fname);
 
private:
  void WriteOBJ(FILE* fph,
                const std::vector<VHACD::Vertex>& vertices,
                const std::vector<VHACD::Triangle>& indices,
                uint32_t baseIndex);
 
public:
  SplitAxis m_axis{ SplitAxis::X_AXIS_NEGATIVE };
  Volume* m_voxels{ nullptr };   // The voxelized data set
  double m_voxelScale{ 0 };      // Size of a single voxel
  double m_voxelScaleHalf{ 0 };  // 1/2 of the size of a single voxel
  VHACD::BoundsAABB m_voxelBounds;
  VHACD::Vect3 m_voxelAdjust;  // Minimum coordinates of the voxel space, with adjustment
  uint32_t m_depth{ 0 };       // How deep in the recursion of the binary tree this hull is
  uint32_t m_index{ 0 };       // Each convex hull is given a unique id to distinguish it from the others
  double m_volumeError{ 0 };   // The percentage error from the convex hull volume vs. the voxel volume
  double m_voxelVolume{ 0 };   // The volume of the voxels
  double m_hullVolume{ 0 };    // The volume of the enclosing convex hull
 
  std::unique_ptr<IVHACD::ConvexHull> m_convexHull{ nullptr };  // The convex hull which encloses this set of voxels.
  std::vector<Voxel> m_surfaceVoxels;     // The voxels which are on the surface of the source mesh.
  std::vector<Voxel> m_newSurfaceVoxels;  // Voxels which are on the surface as a result of a plane split
  std::vector<Voxel> m_interiorVoxels;    // Voxels which are part of the interior of the hull
 
  std::unique_ptr<VoxelHull> m_hullA{ nullptr };  // hull resulting from one side of the plane split
  std::unique_ptr<VoxelHull> m_hullB{ nullptr };  // hull resulting from the other side of the plane split
 
  // Defines the coordinates this convex hull comprises within the voxel volume
  // of the entire source
  VHACD::Vector3<uint32_t> m_1{ 0 };
  VHACD::Vector3<uint32_t> m_2{ 0 };
  AABBTree m_AABBTree;
  std::unordered_map<uint32_t, uint32_t> m_voxelIndexMap;  // Maps from a voxel coordinate space into a vertex index
                                                           // space
  std::vector<VHACD::Vertex> m_vertices;
  std::vector<VHACD::Triangle> m_indices;
  static uint32_t m_voxelHullCount;
  IVHACD::Parameters m_params;
  VHACDCallbacks* m_callbacks{ nullptr };
};
 
uint32_t VoxelHull::m_voxelHullCount = 0;
 
VoxelHull::VoxelHull(const VoxelHull& parent, SplitAxis axis, uint32_t splitLoc)
  : m_axis(axis)
  , m_voxels(parent.m_voxels)
  , m_voxelScale(m_voxels->GetScale())
  , m_voxelScaleHalf(m_voxelScale * double(0.5))
  , m_voxelBounds(m_voxels->GetBounds())
  , m_voxelAdjust(m_voxelBounds.GetMin() - m_voxelScaleHalf)
  , m_depth(parent.m_depth + 1)
  , m_index(++m_voxelHullCount)
  , m_1(parent.m_1)
  , m_2(parent.m_2)
  , m_params(parent.m_params)
{
  // Default copy the voxel region from the parent, but values will
  // be adjusted next based on the split axis and location
  switch (m_axis)
  {
    case SplitAxis::X_AXIS_NEGATIVE:
      m_2.GetX() = splitLoc;
      break;
    case SplitAxis::X_AXIS_POSITIVE:
      m_1.GetX() = splitLoc + 1;
      break;
    case SplitAxis::Y_AXIS_NEGATIVE:
      m_2.GetY() = splitLoc;
      break;
    case SplitAxis::Y_AXIS_POSITIVE:
      m_1.GetY() = splitLoc + 1;
      break;
    case SplitAxis::Z_AXIS_NEGATIVE:
      m_2.GetZ() = splitLoc;
      break;
    case SplitAxis::Z_AXIS_POSITIVE:
      m_1.GetZ() = splitLoc + 1;
      break;
  }
 
  // First, we copy all of the interior voxels from our parent
  // which intersect our region
  for (auto& i : parent.m_interiorVoxels)
  {
    VHACD::Vector3<uint32_t> v = i.GetVoxel();
    if (v.CWiseAllGE(m_1) && v.CWiseAllLE(m_2))
    {
      bool newSurface = false;
      switch (m_axis)
      {
        case SplitAxis::X_AXIS_NEGATIVE:
          if (v.GetX() == splitLoc)
          {
            newSurface = true;
          }
          break;
        case SplitAxis::X_AXIS_POSITIVE:
          if (v.GetX() == m_1.GetX())
          {
            newSurface = true;
          }
          break;
        case SplitAxis::Y_AXIS_NEGATIVE:
          if (v.GetY() == splitLoc)
          {
            newSurface = true;
          }
          break;
        case SplitAxis::Y_AXIS_POSITIVE:
          if (v.GetY() == m_1.GetY())
          {
            newSurface = true;
          }
          break;
        case SplitAxis::Z_AXIS_NEGATIVE:
          if (v.GetZ() == splitLoc)
          {
            newSurface = true;
          }
          break;
        case SplitAxis::Z_AXIS_POSITIVE:
          if (v.GetZ() == m_1.GetZ())
          {
            newSurface = true;
          }
          break;
      }
      // If his interior voxels lie directly on the split plane then
      // these become new surface voxels for our patch
      if (newSurface)
      {
        m_newSurfaceVoxels.push_back(i);
      }
      else
      {
        m_interiorVoxels.push_back(i);
      }
    }
  }
  // Next we copy all of the surface voxels which intersect our region
  for (auto& i : parent.m_surfaceVoxels)
  {
    VHACD::Vector3<uint32_t> v = i.GetVoxel();
    if (v.CWiseAllGE(m_1) && v.CWiseAllLE(m_2))
    {
      m_surfaceVoxels.push_back(i);
    }
  }
  // Our parent's new surface voxels become our new surface voxels so long as they intersect our region
  for (auto& i : parent.m_newSurfaceVoxels)
  {
    VHACD::Vector3<uint32_t> v = i.GetVoxel();
    if (v.CWiseAllGE(m_1) && v.CWiseAllLE(m_2))
    {
      m_newSurfaceVoxels.push_back(i);
    }
  }
 
  // Recompute the min-max bounding box which would be different after the split occurs
  m_1 = VHACD::Vector3<uint32_t>(0x7FFFFFFF);
  m_2 = VHACD::Vector3<uint32_t>(0);
  for (auto& i : m_surfaceVoxels)
  {
    MinMaxVoxelRegion(i);
  }
  for (auto& i : m_newSurfaceVoxels)
  {
    MinMaxVoxelRegion(i);
  }
  for (auto& i : m_interiorVoxels)
  {
    MinMaxVoxelRegion(i);
  }
 
  BuildVoxelMesh();
  BuildRaycastMesh();  // build a raycast mesh of the voxel mesh
  ComputeConvexHull();
}
 
VoxelHull::VoxelHull(Volume& voxels, const IVHACD::Parameters& params, VHACDCallbacks* callbacks)
  : m_voxels(&voxels)
  , m_voxelScale(m_voxels->GetScale())
  , m_voxelScaleHalf(m_voxelScale * double(0.5))
  , m_voxelBounds(m_voxels->GetBounds())
  , m_voxelAdjust(m_voxelBounds.GetMin() - m_voxelScaleHalf)
  , m_index(++m_voxelHullCount)
  // Here we get a copy of all voxels which lie on the surface mesh
  , m_surfaceVoxels(m_voxels->GetSurfaceVoxels())
  // Now we get a copy of all voxels which are considered part of the 'interior' of the source mesh
  , m_interiorVoxels(m_voxels->GetInteriorVoxels())
  , m_2(m_voxels->GetDimensions() - 1)
  , m_params(params)
  , m_callbacks(callbacks)
{
  BuildVoxelMesh();
  BuildRaycastMesh();  // build a raycast mesh of the voxel mesh
  ComputeConvexHull();
}
 
void VoxelHull::MinMaxVoxelRegion(const Voxel& v)
{
  VHACD::Vector3<uint32_t> x = v.GetVoxel();
  m_1 = m_1.CWiseMin(x);
  m_2 = m_2.CWiseMax(x);
}
 
void VoxelHull::BuildRaycastMesh()
{
  // Create a raycast mesh representation of the voxelized surface mesh
  if (!m_indices.empty())
  {
    m_AABBTree = AABBTree(m_vertices, m_indices);
  }
}
 
void VoxelHull::ComputeConvexHull()
{
  if (!m_vertices.empty())
  {
    // we compute the convex hull as follows...
    VHACD::QuickHull qh;
    uint32_t tcount = qh.ComputeConvexHull(m_vertices, uint32_t(m_vertices.size()));
    if (tcount)
    {
      m_convexHull = std::unique_ptr<IVHACD::ConvexHull>(new IVHACD::ConvexHull);
 
      m_convexHull->m_points = qh.GetVertices();
      m_convexHull->m_triangles = qh.GetIndices();
 
      VHACD::ComputeCentroid(m_convexHull->m_points, m_convexHull->m_triangles, m_convexHull->m_center);
      m_convexHull->m_volume = VHACD::ComputeMeshVolume(m_convexHull->m_points, m_convexHull->m_triangles);
    }
  }
  if (m_convexHull)
  {
    m_hullVolume = m_convexHull->m_volume;
  }
  // This is the volume of a single voxel
  double singleVoxelVolume = m_voxelScale * m_voxelScale * m_voxelScale;
  size_t voxelCount = m_interiorVoxels.size() + m_newSurfaceVoxels.size() + m_surfaceVoxels.size();
  m_voxelVolume = singleVoxelVolume * double(voxelCount);
  double diff = fabs(m_hullVolume - m_voxelVolume);
  m_volumeError = (diff * 100) / m_voxelVolume;
}
 
bool VoxelHull::IsComplete()
{
  bool ret = false;
  if (m_convexHull == nullptr)
  {
    ret = true;
  }
  else if (m_volumeError < m_params.m_minimumVolumePercentErrorAllowed)
  {
    ret = true;
  }
  else if (m_depth > m_params.m_maxRecursionDepth)
  {
    ret = true;
  }
  else
  {
    // We compute the voxel width on all 3 axes and see if they are below the min threshold size
    VHACD::Vector3<uint32_t> d = m_2 - m_1;
    if (d.GetX() <= m_params.m_minEdgeLength && d.GetY() <= m_params.m_minEdgeLength &&
        d.GetZ() <= m_params.m_minEdgeLength)
    {
      ret = true;
    }
  }
  return ret;
}
 
VHACD::Vect3 VoxelHull::GetPoint(const int32_t x,
                                 const int32_t y,
                                 const int32_t z,
                                 const double scale,
                                 const VHACD::Vect3& bmin) const
{
  return VHACD::Vect3(x * scale + bmin.GetX(), y * scale + bmin.GetY(), z * scale + bmin.GetZ());
}
 
uint32_t VoxelHull::GetVertexIndex(const VHACD::Vector3<uint32_t>& p)
{
  uint32_t ret = 0;
  uint32_t address = (p.GetX() << 20) | (p.GetY() << 10) | p.GetZ();
  auto found = m_voxelIndexMap.find(address);
  if (found != m_voxelIndexMap.end())
  {
    ret = found->second;
  }
  else
  {
    VHACD::Vect3 vertex = GetPoint(p.GetX(), p.GetY(), p.GetZ(), m_voxelScale, m_voxelAdjust);
    ret = uint32_t(m_voxelIndexMap.size());
    m_voxelIndexMap[address] = ret;
    m_vertices.emplace_back(vertex);
  }
  return ret;
}
 
void VoxelHull::BuildVoxelMesh()
{
  // When we build the triangle mesh we do *not* need the interior voxels, only the ones
  // which lie upon the logical surface of the mesh.
  // Each time we perform a plane split, voxels which are along the splitting plane become
  // 'new surface voxels'.
 
  for (auto& i : m_surfaceVoxels)
  {
    AddVoxelBox(i);
  }
  for (auto& i : m_newSurfaceVoxels)
  {
    AddVoxelBox(i);
  }
}
 
void VoxelHull::AddVoxelBox(const Voxel& v)
{
  // The voxel position of the upper left corner of the box
  VHACD::Vector3<uint32_t> bmin(v.GetX(), v.GetY(), v.GetZ());
  // The voxel position of the lower right corner of the box
  VHACD::Vector3<uint32_t> bmax(bmin.GetX() + 1, bmin.GetY() + 1, bmin.GetZ() + 1);
 
  // Build the set of 8 voxel positions representing
  // the coordinates of the box
  std::array<VHACD::Vector3<uint32_t>, 8> box{ { { bmin.GetX(), bmin.GetY(), bmin.GetZ() },
                                                 { bmax.GetX(), bmin.GetY(), bmin.GetZ() },
                                                 { bmax.GetX(), bmax.GetY(), bmin.GetZ() },
                                                 { bmin.GetX(), bmax.GetY(), bmin.GetZ() },
                                                 { bmin.GetX(), bmin.GetY(), bmax.GetZ() },
                                                 { bmax.GetX(), bmin.GetY(), bmax.GetZ() },
                                                 { bmax.GetX(), bmax.GetY(), bmax.GetZ() },
                                                 { bmin.GetX(), bmax.GetY(), bmax.GetZ() } } };
 
  // Now add the 12 triangles comprising the 3d box
  AddTri(box, 2, 1, 0);
  AddTri(box, 3, 2, 0);
 
  AddTri(box, 7, 2, 3);
  AddTri(box, 7, 6, 2);
 
  AddTri(box, 5, 1, 2);
  AddTri(box, 5, 2, 6);
 
  AddTri(box, 5, 4, 1);
  AddTri(box, 4, 0, 1);
 
  AddTri(box, 4, 6, 7);
  AddTri(box, 4, 5, 6);
 
  AddTri(box, 4, 7, 0);
  AddTri(box, 7, 3, 0);
}
 
void VoxelHull::AddTri(const std::array<VHACD::Vector3<uint32_t>, 8>& box, uint32_t i1, uint32_t i2, uint32_t i3)
{
  AddTriangle(box[i1], box[i2], box[i3]);
}
 
void VoxelHull::AddTriangle(const VHACD::Vector3<uint32_t>& p1,
                            const VHACD::Vector3<uint32_t>& p2,
                            const VHACD::Vector3<uint32_t>& p3)
{
  uint32_t i1 = GetVertexIndex(p1);
  uint32_t i2 = GetVertexIndex(p2);
  uint32_t i3 = GetVertexIndex(p3);
 
  m_indices.emplace_back(i1, i2, i3);
}
 
SplitAxis VoxelHull::ComputeSplitPlane(uint32_t& location)
{
  SplitAxis ret = SplitAxis::X_AXIS_NEGATIVE;
 
  VHACD::Vector3<uint32_t> d = m_2 - m_1;
 
  if (d.GetX() >= d.GetY() && d.GetX() >= d.GetZ())
  {
    ret = SplitAxis::X_AXIS_NEGATIVE;
    location = (m_2.GetX() + 1 + m_1.GetX()) / 2;
    uint32_t edgeLoc;
    if (m_params.m_findBestPlane && FindConcavityX(edgeLoc))
    {
      location = edgeLoc;
    }
  }
  else if (d.GetY() >= d.GetX() && d.GetY() >= d.GetZ())
  {
    ret = SplitAxis::Y_AXIS_NEGATIVE;
    location = (m_2.GetY() + 1 + m_1.GetY()) / 2;
    uint32_t edgeLoc;
    if (m_params.m_findBestPlane && FindConcavityY(edgeLoc))
    {
      location = edgeLoc;
    }
  }
  else
  {
    ret = SplitAxis::Z_AXIS_NEGATIVE;
    location = (m_2.GetZ() + 1 + m_1.GetZ()) / 2;
    uint32_t edgeLoc;
    if (m_params.m_findBestPlane && FindConcavityZ(edgeLoc))
    {
      location = edgeLoc;
    }
  }
 
  return ret;
}
 
VHACD::Vect3 VoxelHull::GetPosition(const VHACD::Vector3<int32_t>& ip) const
{
  return GetPoint(ip.GetX(), ip.GetY(), ip.GetZ(), m_voxelScale, m_voxelAdjust);
}
 
double VoxelHull::Raycast(const VHACD::Vector3<int32_t>& p1, const VHACD::Vector3<int32_t>& p2) const
{
  double ret;
  VHACD::Vect3 from = GetPosition(p1);
  VHACD::Vect3 to = GetPosition(p2);
 
  double outT;
  double faceSign;
  VHACD::Vect3 hitLocation;
  if (m_AABBTree.TraceRay(from, to, outT, faceSign, hitLocation))
  {
    ret = (from - hitLocation).GetNorm();
  }
  else
  {
    ret = 0;  // if it doesn't hit anything, just assign it to zero.
  }
 
  return ret;
}
 
bool VoxelHull::FindConcavity(uint32_t idx, uint32_t& splitLoc)
{
  bool ret = false;
 
  int32_t d = (m_2[idx] - m_1[idx]) + 1;  // The length of the getX axis in voxel space
 
  uint32_t idx1;
  uint32_t idx2;
  uint32_t idx3;
  switch (idx)
  {
    case 0:  // X
      idx1 = 0;
      idx2 = 1;
      idx3 = 2;
      break;
    case 1:  // Y
      idx1 = 1;
      idx2 = 0;
      idx3 = 2;
      break;
    case 2:
      idx1 = 2;
      idx2 = 1;
      idx3 = 0;
      break;
    default:
      /*
       * To silence uninitialized variable warnings
       */
      idx1 = 0;
      idx2 = 0;
      idx3 = 0;
      assert(0 && "findConcavity::idx must be 0, 1, or 2");
      break;
  }
 
  // We will compute the edge error on the XY plane and the XZ plane
  // searching for the greatest location of concavity
  std::vector<double> edgeError1 = std::vector<double>(d);
  std::vector<double> edgeError2 = std::vector<double>(d);
 
  // Counter of number of voxel samples on the XY plane we have accumulated
  uint32_t index1 = 0;
 
  // Compute Edge Error on the XY plane
  for (uint32_t i0 = m_1[idx1]; i0 <= m_2[idx1]; i0++)
  {
    double errorTotal = 0;
    // We now perform a raycast from the sides inward on the XY plane to
    // determine the total error (distance of the surface from the sides)
    // along this getX position.
    for (uint32_t i1 = m_1[idx2]; i1 <= m_2[idx2]; i1++)
    {
      VHACD::Vector3<int32_t> p1;
      VHACD::Vector3<int32_t> p2;
      switch (idx)
      {
        case 0:
        {
          p1 = VHACD::Vector3<int32_t>(i0, i1, m_1.GetZ() - 2);
          p2 = VHACD::Vector3<int32_t>(i0, i1, m_2.GetZ() + 2);
          break;
        }
        case 1:
        {
          p1 = VHACD::Vector3<int32_t>(i1, i0, m_1.GetZ() - 2);
          p2 = VHACD::Vector3<int32_t>(i1, i0, m_2.GetZ() + 2);
          break;
        }
        case 2:
        {
          p1 = VHACD::Vector3<int32_t>(m_1.GetX() - 2, i1, i0);
          p2 = VHACD::Vector3<int32_t>(m_2.GetX() + 2, i1, i0);
          break;
        }
      }
 
      double e1 = Raycast(p1, p2);
      double e2 = Raycast(p2, p1);
 
      errorTotal = errorTotal + e1 + e2;
    }
    // The total amount of edge error along this voxel location
    edgeError1[index1] = errorTotal;
    index1++;
  }
 
  // Compute edge error along the XZ plane
  uint32_t index2 = 0;
 
  for (uint32_t i0 = m_1[idx1]; i0 <= m_2[idx1]; i0++)
  {
    double errorTotal = 0;
 
    for (uint32_t i1 = m_1[idx3]; i1 <= m_2[idx3]; i1++)
    {
      VHACD::Vector3<int32_t> p1;
      VHACD::Vector3<int32_t> p2;
      switch (idx)
      {
        case 0:
        {
          p1 = VHACD::Vector3<int32_t>(i0, m_1.GetY() - 2, i1);
          p2 = VHACD::Vector3<int32_t>(i0, m_2.GetY() + 2, i1);
          break;
        }
        case 1:
        {
          p1 = VHACD::Vector3<int32_t>(m_1.GetX() - 2, i0, i1);
          p2 = VHACD::Vector3<int32_t>(m_2.GetX() + 2, i0, i1);
          break;
        }
        case 2:
        {
          p1 = VHACD::Vector3<int32_t>(i1, m_1.GetY() - 2, i0);
          p2 = VHACD::Vector3<int32_t>(i1, m_2.GetY() + 2, i0);
          break;
        }
      }
 
      double e1 = Raycast(p1, p2);  // raycast from one side to the interior
      double e2 = Raycast(p2, p1);  // raycast from the other side to the interior
 
      errorTotal = errorTotal + e1 + e2;
    }
    edgeError2[index2] = errorTotal;
    index2++;
  }
 
  // we now compute the first derivative to find the greatest spot of concavity on the XY plane
  double maxDiff = 0;
  uint32_t maxC = 0;
  for (uint32_t x = 1; x < index1; x++)
  {
    if (edgeError1[x] > 0 && edgeError1[x - 1] > 0)
    {
      double diff = abs(edgeError1[x] - edgeError1[x - 1]);
      if (diff > maxDiff)
      {
        maxDiff = diff;
        maxC = x - 1;
      }
    }
  }
 
  // Now see if there is a greater concavity on the XZ plane
  for (uint32_t x = 1; x < index2; x++)
  {
    if (edgeError2[x] > 0 && edgeError2[x - 1] > 0)
    {
      double diff = abs(edgeError2[x] - edgeError2[x - 1]);
      if (diff > maxDiff)
      {
        maxDiff = diff;
        maxC = x - 1;
      }
    }
  }
 
  splitLoc = maxC + m_1[idx1];
 
  // we do not allow an edge split if it is too close to the ends
  if (splitLoc > (m_1[idx1] + 4) && splitLoc < (m_2[idx1] - 4))
  {
    ret = true;
  }
 
  return ret;
}
 
// Finding the greatest area of concavity..
bool VoxelHull::FindConcavityX(uint32_t& splitLoc) { return FindConcavity(0, splitLoc); }
 
// Finding the greatest area of concavity..
bool VoxelHull::FindConcavityY(uint32_t& splitLoc) { return FindConcavity(1, splitLoc); }
 
// Finding the greatest area of concavity..
bool VoxelHull::FindConcavityZ(uint32_t& splitLoc) { return FindConcavity(2, splitLoc); }
 
void VoxelHull::PerformPlaneSplit()
{
  if (IsComplete())
  {
  }
  else
  {
    uint32_t splitLoc;
    SplitAxis axis = ComputeSplitPlane(splitLoc);
    switch (axis)
    {
      case SplitAxis::X_AXIS_NEGATIVE:
      case SplitAxis::X_AXIS_POSITIVE:
        // Split on the getX axis at this split location
        m_hullA = std::unique_ptr<VoxelHull>(new VoxelHull(*this, SplitAxis::X_AXIS_NEGATIVE, splitLoc));
        m_hullB = std::unique_ptr<VoxelHull>(new VoxelHull(*this, SplitAxis::X_AXIS_POSITIVE, splitLoc));
        break;
      case SplitAxis::Y_AXIS_NEGATIVE:
      case SplitAxis::Y_AXIS_POSITIVE:
        // Split on the 1 axis at this split location
        m_hullA = std::unique_ptr<VoxelHull>(new VoxelHull(*this, SplitAxis::Y_AXIS_NEGATIVE, splitLoc));
        m_hullB = std::unique_ptr<VoxelHull>(new VoxelHull(*this, SplitAxis::Y_AXIS_POSITIVE, splitLoc));
        break;
      case SplitAxis::Z_AXIS_NEGATIVE:
      case SplitAxis::Z_AXIS_POSITIVE:
        // Split on the getZ axis at this split location
        m_hullA = std::unique_ptr<VoxelHull>(new VoxelHull(*this, SplitAxis::Z_AXIS_NEGATIVE, splitLoc));
        m_hullB = std::unique_ptr<VoxelHull>(new VoxelHull(*this, SplitAxis::Z_AXIS_POSITIVE, splitLoc));
        break;
    }
  }
}
 
void VoxelHull::SaveVoxelMesh(const SimpleMesh& inputMesh, bool saveVoxelMesh, bool saveSourceMesh)
{
  char scratch[512];
  snprintf(scratch, sizeof(scratch), "voxel-mesh-%03d.obj", m_index);
  FILE* fph = fopen(scratch, "wb");
  if (fph)
  {
    uint32_t baseIndex = 1;
    if (saveVoxelMesh)
    {
      WriteOBJ(fph, m_vertices, m_indices, baseIndex);
      baseIndex += uint32_t(m_vertices.size());
    }
    if (saveSourceMesh)
    {
      WriteOBJ(fph, inputMesh.m_vertices, inputMesh.m_indices, baseIndex);
    }
    fclose(fph);
  }
}
 
void VoxelHull::SaveOBJ(const char* fname, const VoxelHull* h)
{
  FILE* fph = fopen(fname, "wb");
  if (fph)
  {
    uint32_t baseIndex = 1;
    WriteOBJ(fph, m_vertices, m_indices, baseIndex);
 
    baseIndex += uint32_t(m_vertices.size());
 
    WriteOBJ(fph, h->m_vertices, h->m_indices, baseIndex);
    fclose(fph);
  }
}
 
void VoxelHull::SaveOBJ(const char* fname)
{
  FILE* fph = fopen(fname, "wb");
  if (fph)
  {
    printf("Saving '%s' with %d vertices and %d triangles\n",
           fname,
           uint32_t(m_vertices.size()),
           uint32_t(m_indices.size()));
    WriteOBJ(fph, m_vertices, m_indices, 1);
    fclose(fph);
  }
}
 
void VoxelHull::WriteOBJ(FILE* fph,
                         const std::vector<VHACD::Vertex>& vertices,
                         const std::vector<VHACD::Triangle>& indices,
                         uint32_t baseIndex)
{
  if (!fph)
  {
    return;
  }
 
  for (size_t i = 0; i < vertices.size(); ++i)
  {
    const VHACD::Vertex& v = vertices[i];
    fprintf(fph, "v %0.9f %0.9f %0.9f\n", v.mX, v.mY, v.mZ);
  }
 
  for (size_t i = 0; i < indices.size(); ++i)
  {
    const VHACD::Triangle& t = indices[i];
    fprintf(fph, "f %d %d %d\n", t.mI0 + baseIndex, t.mI1 + baseIndex, t.mI2 + baseIndex);
  }
}
 
class VHACDImpl;
 
// This class represents a single task to compute the volume error
// of two convex hulls combined
class CostTask
{
public:
  VHACDImpl* m_this{ nullptr };
  IVHACD::ConvexHull* m_hullA{ nullptr };
  IVHACD::ConvexHull* m_hullB{ nullptr };
  double m_concavity{ 0 };  // concavity of the two combined
  std::future<void> m_future;
};
 
class HullPair
{
public:
  HullPair() = default;
  HullPair(uint32_t hullA, uint32_t hullB, double concavity);
 
  bool operator<(const HullPair& h) const;
 
  uint32_t m_hullA{ 0 };
  uint32_t m_hullB{ 0 };
  double m_concavity{ 0 };
};
 
HullPair::HullPair(uint32_t hullA, uint32_t hullB, double concavity)
  : m_hullA(hullA), m_hullB(hullB), m_concavity(concavity)
{
}
 
bool HullPair::operator<(const HullPair& h) const { return m_concavity > h.m_concavity ? true : false; }
 
// void jobCallback(void* userPtr);
 
class VHACDImpl : public IVHACD, public VHACDCallbacks
{
  // Don't consider more than 100,000 convex hulls.
  static constexpr uint32_t MaxConvexHullFragments{ 100000 };
 
public:
  VHACDImpl() = default;
 
  /*
   * Overrides VHACD::IVHACD
   */
  ~VHACDImpl() override { Clean(); }
 
  void Cancel() override final;
 
  bool Compute(const float* const points,
               const uint32_t countPoints,
               const uint32_t* const triangles,
               const uint32_t countTriangles,
               const Parameters& params) override final;
 
  bool Compute(const double* const points,
               const uint32_t countPoints,
               const uint32_t* const triangles,
               const uint32_t countTriangles,
               const Parameters& params) override final;
 
  uint32_t GetNConvexHulls() const override final;
 
  bool GetConvexHull(const uint32_t index, ConvexHull& ch) const override final;
 
  void Clean() override final;  // release internally allocated memory
 
  void Release() override final;
 
  // Will compute the center of mass of the convex hull decomposition results and return it
  // in 'centerOfMass'.  Returns false if the center of mass could not be computed.
  bool ComputeCenterOfMass(double centerOfMass[3]) const override final;
 
  // In synchronous mode (non-multi-threaded) the state is always 'ready'
  // In asynchronous mode, this returns true if the background thread is not still actively computing
  // a new solution.  In an asynchronous config the 'IsReady' call will report any update or log
  // messages in the caller's current thread.
  bool IsReady(void) const override final;
 
  uint32_t findNearestConvexHull(const double pos[3], double& distanceToHull) override final;
 
  // private:
  bool Compute(const std::vector<VHACD::Vertex>& points,
               const std::vector<VHACD::Triangle>& triangles,
               const Parameters& params);
 
  // Take the source position, normalize it, and then convert it into an index position
  uint32_t GetIndex(VHACD::VertexIndex& vi, const VHACD::Vertex& p);
 
  // This copies the input mesh while scaling the input positions
  // to fit into a normalized unit cube. It also re-indexes all of the
  // vertex positions in case they weren't clean coming in.
  void CopyInputMesh(const std::vector<VHACD::Vertex>& points, const std::vector<VHACD::Triangle>& triangles);
 
  void ScaleOutputConvexHull(ConvexHull& ch);
 
  void AddCostToPriorityQueue(CostTask& task);
 
  void ReleaseConvexHull(ConvexHull* ch);
 
  void PerformConvexDecomposition();
 
  double ComputeConvexHullVolume(const ConvexHull& sm);
 
  double ComputeVolume4(const VHACD::Vect3& a, const VHACD::Vect3& b, const VHACD::Vect3& c, const VHACD::Vect3& d);
 
  double ComputeConcavity(double volumeSeparate, double volumeCombined, double volumeMesh);
 
  // See if we can compute the cost without having to actually merge convex hulls.
  // If the axis aligned bounding boxes (slightly inflated) of the two convex hulls
  // do not intersect, then we don't need to actually compute the merged convex hull
  // volume.
  bool DoFastCost(CostTask& mt);
 
  void PerformMergeCostTask(CostTask& mt);
 
  ConvexHull* ComputeReducedConvexHull(const ConvexHull& ch, uint32_t maxVerts, bool projectHullVertices);
 
  // Take the points in convex hull A and the points in convex hull B and generate
  // a new convex hull on the combined set of points.
  // Once completed, we create a SimpleMesh instance to hold the triangle mesh
  // and we compute an inflated AABB for it.
  ConvexHull* ComputeCombinedConvexHull(const ConvexHull& sm1, const ConvexHull& sm2);
 
  ConvexHull* GetHull(uint32_t index);
 
  bool RemoveHull(uint32_t index);
 
  ConvexHull* CopyConvexHull(const ConvexHull& source);
 
  const char* GetStageName(Stages stage) const;
 
  /*
   * Overrides VHACD::VHACDCallbacks
   */
  void ProgressUpdate(Stages stage, double stageProgress, const char* operation) override final;
 
  bool IsCanceled() const override final;
 
  std::atomic<bool> m_canceled{ false };
  Parameters m_params;  // Convex decomposition parameters
 
  std::vector<IVHACD::ConvexHull*> m_convexHulls;        // Finalized convex hulls
  std::vector<std::unique_ptr<VoxelHull>> m_voxelHulls;  // completed voxel hulls
  std::vector<std::unique_ptr<VoxelHull>> m_pendingHulls;
 
  std::vector<std::unique_ptr<AABBTree>> m_trees;
  VHACD::AABBTree m_AABBTree;
  VHACD::Volume m_voxelize;
  VHACD::Vect3 m_center;
  double m_scale{ double(1.0) };
  double m_recipScale{ double(1.0) };
  SimpleMesh m_inputMesh;  // re-indexed and normalized input mesh
  std::vector<VHACD::Vertex> m_vertices;
  std::vector<VHACD::Triangle> m_indices;
 
  double m_overallHullVolume{ double(0.0) };
  double m_voxelScale{ double(0.0) };
  double m_voxelHalfScale{ double(0.0) };
  VHACD::Vect3 m_voxelBmin;
  VHACD::Vect3 m_voxelBmax;
  uint32_t m_meshId{ 0 };
  std::priority_queue<HullPair> m_hullPairQueue;
#if !VHACD_DISABLE_THREADING
  std::unique_ptr<ThreadPool> m_threadPool{ nullptr };
#endif
  std::unordered_map<uint32_t, IVHACD::ConvexHull*> m_hulls;
 
  double m_overallProgress{ double(0.0) };
  double m_stageProgress{ double(0.0) };
  double m_operationProgress{ double(0.0) };
};
 
void VHACDImpl::Cancel() { m_canceled = true; }
 
bool VHACDImpl::Compute(const float* const points,
                        const uint32_t countPoints,
                        const uint32_t* const triangles,
                        const uint32_t countTriangles,
                        const Parameters& params)
{
  std::vector<VHACD::Vertex> v;
  v.reserve(countPoints);
  for (uint32_t i = 0; i < countPoints; ++i)
  {
    v.emplace_back(points[i * 3 + 0], points[i * 3 + 1], points[i * 3 + 2]);
  }
 
  std::vector<VHACD::Triangle> t;
  t.reserve(countTriangles);
  for (uint32_t i = 0; i < countTriangles; ++i)
  {
    t.emplace_back(triangles[i * 3 + 0], triangles[i * 3 + 1], triangles[i * 3 + 2]);
  }
 
  return Compute(v, t, params);
}
 
bool VHACDImpl::Compute(const double* const points,
                        const uint32_t countPoints,
                        const uint32_t* const triangles,
                        const uint32_t countTriangles,
                        const Parameters& params)
{
  std::vector<VHACD::Vertex> v;
  v.reserve(countPoints);
  for (uint32_t i = 0; i < countPoints; ++i)
  {
    v.emplace_back(points[i * 3 + 0], points[i * 3 + 1], points[i * 3 + 2]);
  }
 
  std::vector<VHACD::Triangle> t;
  t.reserve(countTriangles);
  for (uint32_t i = 0; i < countTriangles; ++i)
  {
    t.emplace_back(triangles[i * 3 + 0], triangles[i * 3 + 1], triangles[i * 3 + 2]);
  }
 
  return Compute(v, t, params);
}
 
uint32_t VHACDImpl::GetNConvexHulls() const { return uint32_t(m_convexHulls.size()); }
 
bool VHACDImpl::GetConvexHull(const uint32_t index, ConvexHull& ch) const
{
  bool ret = false;
 
  if (index < uint32_t(m_convexHulls.size()))
  {
    ch = *m_convexHulls[index];
    ret = true;
  }
 
  return ret;
}
 
void VHACDImpl::Clean()
{
#if !VHACD_DISABLE_THREADING
  m_threadPool = nullptr;
#endif
 
  m_trees.clear();
 
  for (auto& ch : m_convexHulls)
  {
    ReleaseConvexHull(ch);
  }
  m_convexHulls.clear();
 
  for (auto& ch : m_hulls)
  {
    ReleaseConvexHull(ch.second);
  }
  m_hulls.clear();
 
  m_voxelHulls.clear();
 
  m_pendingHulls.clear();
 
  m_vertices.clear();
  m_indices.clear();
}
 
void VHACDImpl::Release() { delete this; }
 
bool VHACDImpl::ComputeCenterOfMass(double centerOfMass[3]) const
{
  bool ret = false;
 
  return ret;
}
 
bool VHACDImpl::IsReady() const { return true; }
 
uint32_t VHACDImpl::findNearestConvexHull(const double pos[3], double& distanceToHull)
{
  uint32_t ret = 0;  // The default return code is zero
 
  uint32_t hullCount = GetNConvexHulls();
  distanceToHull = 0;
  // First, make sure that we have valid and completed results
  if (hullCount)
  {
    // See if we already have AABB trees created for each convex hull
    if (m_trees.empty())
    {
      // For each convex hull, we generate an AABB tree for fast closest point queries
      for (uint32_t i = 0; i < hullCount; i++)
      {
        VHACD::IVHACD::ConvexHull ch;
        GetConvexHull(i, ch);
        // Pass the triangle mesh to create an AABB tree instance based on it.
        m_trees.emplace_back(new AABBTree(ch.m_points, ch.m_triangles));
      }
    }
    // We now compute the closest point to each convex hull and save the nearest one
    double closest = 1e99;
    for (uint32_t i = 0; i < hullCount; i++)
    {
      std::unique_ptr<AABBTree>& t = m_trees[i];
      if (t)
      {
        VHACD::Vect3 closestPoint;
        VHACD::Vect3 position(pos[0], pos[1], pos[2]);
        if (t->GetClosestPointWithinDistance(position, 1e99, closestPoint))
        {
          VHACD::Vect3 d = position - closestPoint;
          double distanceSquared = d.GetNormSquared();
          if (distanceSquared < closest)
          {
            closest = distanceSquared;
            ret = i;
          }
        }
      }
    }
    distanceToHull = sqrt(closest);  // compute the distance to the nearest convex hull
  }
 
  return ret;
}
 
bool VHACDImpl::Compute(const std::vector<VHACD::Vertex>& points,
                        const std::vector<VHACD::Triangle>& triangles,
                        const Parameters& params)
{
  bool ret = false;
 
  m_params = params;
  m_canceled = false;
 
  Clean();  // release any previous results
#if !VHACD_DISABLE_THREADING
  if (m_params.m_asyncACD)
  {
    m_threadPool = std::unique_ptr<ThreadPool>(new ThreadPool(8));
  }
#endif
  CopyInputMesh(points, triangles);
  if (!m_canceled)
  {
    // We now recursively perform convex decomposition until complete
    PerformConvexDecomposition();
  }
 
  if (m_canceled)
  {
    Clean();
    ret = false;
    if (m_params.m_logger)
    {
      m_params.m_logger->Log("VHACD operation canceled before it was complete.");
    }
  }
  else
  {
    ret = true;
  }
#if !VHACD_DISABLE_THREADING
  m_threadPool = nullptr;
#endif
  return ret;
}
 
uint32_t VHACDImpl::GetIndex(VHACD::VertexIndex& vi, const VHACD::Vertex& p)
{
  VHACD::Vect3 pos = (VHACD::Vect3(p) - m_center) * m_recipScale;
  bool newPos;
  uint32_t ret = vi.GetIndex(pos, newPos);
  return ret;
}
 
void VHACDImpl::CopyInputMesh(const std::vector<VHACD::Vertex>& points, const std::vector<VHACD::Triangle>& triangles)
{
  m_vertices.clear();
  m_indices.clear();
  m_indices.reserve(triangles.size());
 
  // First we must find the bounding box of this input vertices and normalize them into a unit-cube
  VHACD::Vect3 bmin(FLT_MAX);
  VHACD::Vect3 bmax(-FLT_MAX);
  ProgressUpdate(Stages::COMPUTE_BOUNDS_OF_INPUT_MESH, 0, "ComputingBounds");
  for (uint32_t i = 0; i < points.size(); i++)
  {
    const VHACD::Vertex& p = points[i];
 
    bmin = bmin.CWiseMin(p);
    bmax = bmax.CWiseMax(p);
  }
  ProgressUpdate(Stages::COMPUTE_BOUNDS_OF_INPUT_MESH, 100, "ComputingBounds");
 
  m_center = (bmax + bmin) * double(0.5);
 
  VHACD::Vect3 scale = bmax - bmin;
  m_scale = scale.MaxCoeff();
 
  m_recipScale = m_scale > double(0.0) ? double(1.0) / m_scale : double(0.0);
 
  {
    VHACD::VertexIndex vi = VHACD::VertexIndex(double(0.001), false);
 
    uint32_t dcount = 0;
 
    for (uint32_t i = 0; i < triangles.size() && !m_canceled; ++i)
    {
      const VHACD::Triangle& t = triangles[i];
      const VHACD::Vertex& p1 = points[t.mI0];
      const VHACD::Vertex& p2 = points[t.mI1];
      const VHACD::Vertex& p3 = points[t.mI2];
 
      uint32_t i1 = GetIndex(vi, p1);
      uint32_t i2 = GetIndex(vi, p2);
      uint32_t i3 = GetIndex(vi, p3);
 
      if (i1 == i2 || i1 == i3 || i2 == i3)
      {
        dcount++;
      }
      else
      {
        m_indices.emplace_back(i1, i2, i3);
      }
    }
 
    if (dcount)
    {
      if (m_params.m_logger)
      {
        char scratch[512];
        snprintf(scratch, sizeof(scratch), "Skipped %d degenerate triangles", dcount);
        m_params.m_logger->Log(scratch);
      }
    }
 
    m_vertices = vi.TakeVertices();
  }
 
  // Create the raycast mesh
  if (!m_canceled)
  {
    ProgressUpdate(Stages::CREATE_RAYCAST_MESH, 0, "Building RaycastMesh");
    m_AABBTree = VHACD::AABBTree(m_vertices, m_indices);
    ProgressUpdate(Stages::CREATE_RAYCAST_MESH, 100, "RaycastMesh completed");
  }
  if (!m_canceled)
  {
    ProgressUpdate(Stages::VOXELIZING_INPUT_MESH, 0, "Voxelizing Input Mesh");
    m_voxelize = VHACD::Volume();
    m_voxelize.Voxelize(m_vertices, m_indices, m_params.m_resolution, m_params.m_fillMode, m_AABBTree);
    m_voxelScale = m_voxelize.GetScale();
    m_voxelHalfScale = m_voxelScale * double(0.5);
    m_voxelBmin = m_voxelize.GetBounds().GetMin();
    m_voxelBmax = m_voxelize.GetBounds().GetMax();
    ProgressUpdate(Stages::VOXELIZING_INPUT_MESH, 100, "Voxelization complete");
  }
 
  m_inputMesh.m_vertices = m_vertices;
  m_inputMesh.m_indices = m_indices;
  if (!m_canceled)
  {
    ProgressUpdate(Stages::BUILD_INITIAL_CONVEX_HULL, 0, "Build initial ConvexHull");
    std::unique_ptr<VoxelHull> vh = std::unique_ptr<VoxelHull>(new VoxelHull(m_voxelize, m_params, this));
    if (vh->m_convexHull)
    {
      m_overallHullVolume = vh->m_convexHull->m_volume;
    }
    m_pendingHulls.push_back(std::move(vh));
    ProgressUpdate(Stages::BUILD_INITIAL_CONVEX_HULL, 100, "Initial ConvexHull complete");
  }
}
 
void VHACDImpl::ScaleOutputConvexHull(ConvexHull& ch)
{
  for (uint32_t i = 0; i < ch.m_points.size(); i++)
  {
    VHACD::Vect3 p = ch.m_points[i];
    p = (p * m_scale) + m_center;
    ch.m_points[i] = p;
  }
  ch.m_volume = ComputeConvexHullVolume(ch);  // get the combined volume
  VHACD::BoundsAABB b(ch.m_points);
  ch.mBmin = b.GetMin();
  ch.mBmax = b.GetMax();
  ComputeCentroid(ch.m_points, ch.m_triangles, ch.m_center);
}
 
void VHACDImpl::AddCostToPriorityQueue(CostTask& task)
{
  HullPair hp(task.m_hullA->m_meshId, task.m_hullB->m_meshId, task.m_concavity);
  m_hullPairQueue.push(hp);
}
 
void VHACDImpl::ReleaseConvexHull(ConvexHull* ch)
{
  if (ch)
  {
    delete ch;
  }
}
 
void jobCallback(std::unique_ptr<VoxelHull>& userPtr) { userPtr->PerformPlaneSplit(); }
 
void computeMergeCostTask(CostTask& ptr) { ptr.m_this->PerformMergeCostTask(ptr); }
 
void VHACDImpl::PerformConvexDecomposition()
{
  {
    ScopedTime st("Convex Decomposition", m_params.m_logger);
    double maxHulls = pow(2, m_params.m_maxRecursionDepth);
    // We recursively split convex hulls until we can
    // no longer recurse further.
    Timer t;
 
    while (!m_pendingHulls.empty() && !m_canceled)
    {
      size_t count = m_pendingHulls.size() + m_voxelHulls.size();
      double e = t.PeekElapsedSeconds();
      if (e >= double(0.1))
      {
        t.Reset();
        double stageProgress = (double(count) * double(100.0)) / maxHulls;
        ProgressUpdate(
            Stages::PERFORMING_DECOMPOSITION, stageProgress, "Performing recursive decomposition of convex hulls");
      }
      // First we make a copy of the hulls we are processing
      std::vector<std::unique_ptr<VoxelHull>> oldList = std::move(m_pendingHulls);
      // For each hull we want to split, we either
      // immediately perform the plane split or we post it as
      // a job to be performed in a background thread
      std::vector<std::future<void>> futures(oldList.size());
      uint32_t futureCount = 0;
      for (auto& i : oldList)
      {
        if (i->IsComplete() || count > MaxConvexHullFragments)
        {
        }
        else
        {
#if !VHACD_DISABLE_THREADING
          if (m_threadPool)
          {
            futures[futureCount] = m_threadPool->enqueue([&i] { jobCallback(i); });
            futureCount++;
          }
          else
#endif
          {
            i->PerformPlaneSplit();
          }
        }
      }
      // Wait for any outstanding jobs to complete in the background threads
      if (futureCount)
      {
        for (uint32_t i = 0; i < futureCount; i++)
        {
          futures[i].get();
        }
      }
      // Now, we rebuild the pending convex hulls list by
      // adding the two children to the output list if
      // we need to recurse them further
      for (auto& vh : oldList)
      {
        if (vh->IsComplete() || count > MaxConvexHullFragments)
        {
          if (vh->m_convexHull)
          {
            m_voxelHulls.push_back(std::move(vh));
          }
        }
        else
        {
          if (vh->m_hullA)
          {
            m_pendingHulls.push_back(std::move(vh->m_hullA));
          }
          if (vh->m_hullB)
          {
            m_pendingHulls.push_back(std::move(vh->m_hullB));
          }
        }
      }
    }
  }
 
  if (!m_canceled)
  {
    // Give each convex hull a unique guid
    m_meshId = 0;
    m_hulls.clear();
 
    // Build the convex hull id map
    std::vector<ConvexHull*> hulls;
 
    ProgressUpdate(Stages::INITIALIZING_CONVEX_HULLS_FOR_MERGING, 0, "Initializing ConvexHulls");
    for (auto& vh : m_voxelHulls)
    {
      if (m_canceled)
      {
        break;
      }
      ConvexHull* ch = CopyConvexHull(*vh->m_convexHull);
      m_meshId++;
      ch->m_meshId = m_meshId;
      m_hulls[m_meshId] = ch;
      // Compute the volume of the convex hull
      ch->m_volume = ComputeConvexHullVolume(*ch);
      // Compute the AABB of the convex hull
      VHACD::BoundsAABB b = VHACD::BoundsAABB(ch->m_points).Inflate(double(0.1));
      ch->mBmin = b.GetMin();
      ch->mBmax = b.GetMax();
 
      ComputeCentroid(ch->m_points, ch->m_triangles, ch->m_center);
 
      hulls.push_back(ch);
    }
    ProgressUpdate(Stages::INITIALIZING_CONVEX_HULLS_FOR_MERGING, 100, "ConvexHull initialization complete");
 
    m_voxelHulls.clear();
 
    // here we merge convex hulls as needed until the match the
    // desired maximum hull count.
    size_t hullCount = hulls.size();
 
    if (hullCount > m_params.m_maxConvexHulls && !m_canceled)
    {
      size_t costMatrixSize = ((hullCount * hullCount) - hullCount) >> 1;
      std::vector<CostTask> tasks;
      tasks.reserve(costMatrixSize);
 
      ScopedTime st("Computing the Cost Matrix", m_params.m_logger);
      // First thing we need to do is compute the cost matrix
      // This is computed as the volume error of any two convex hulls
      // combined
      ProgressUpdate(Stages::COMPUTING_COST_MATRIX, 0, "Computing Hull Merge Cost Matrix");
      for (size_t i = 1; i < hullCount && !m_canceled; i++)
      {
        ConvexHull* chA = hulls[i];
 
        for (size_t j = 0; j < i && !m_canceled; j++)
        {
          ConvexHull* chB = hulls[j];
 
          CostTask t;
          t.m_hullA = chA;
          t.m_hullB = chB;
          t.m_this = this;
 
          if (DoFastCost(t))
          {
          }
          else
          {
            tasks.push_back(std::move(t));
            CostTask* task = &tasks.back();
#if !VHACD_DISABLE_THREADING
            if (m_threadPool)
            {
              task->m_future = m_threadPool->enqueue([task] { computeMergeCostTask(*task); });
            }
#endif
          }
        }
      }
 
      if (!m_canceled)
      {
#if !VHACD_DISABLE_THREADING
        if (m_threadPool)
        {
          for (CostTask& task : tasks)
          {
            task.m_future.get();
          }
 
          for (CostTask& task : tasks)
          {
            AddCostToPriorityQueue(task);
          }
        }
        else
#endif
        {
          for (CostTask& task : tasks)
          {
            PerformMergeCostTask(task);
            AddCostToPriorityQueue(task);
          }
        }
        ProgressUpdate(Stages::COMPUTING_COST_MATRIX, 100, "Finished cost matrix");
      }
 
      if (!m_canceled)
      {
        ScopedTime stMerging("Merging Convex Hulls", m_params.m_logger);
        Timer t;
        // Now that we know the cost to merge each hull, we can begin merging them.
        bool cancel = false;
 
        uint32_t maxMergeCount = uint32_t(m_hulls.size()) - m_params.m_maxConvexHulls;
        uint32_t startCount = uint32_t(m_hulls.size());
 
        while (!cancel && m_hulls.size() > m_params.m_maxConvexHulls && !m_hullPairQueue.empty() && !m_canceled)
        {
          double e = t.PeekElapsedSeconds();
          if (e >= double(0.1))
          {
            t.Reset();
            uint32_t hullsProcessed = startCount - uint32_t(m_hulls.size());
            double stageProgress = double(hullsProcessed * 100) / double(maxMergeCount);
            ProgressUpdate(Stages::MERGING_CONVEX_HULLS, stageProgress, "Merging Convex Hulls");
          }
 
          HullPair hp = m_hullPairQueue.top();
          m_hullPairQueue.pop();
 
          // It is entirely possible that the hull pair queue can
          // have references to convex hulls that are no longer valid
          // because they were previously merged. So we check for this
          // and if either hull referenced in this pair no longer
          // exists, then we skip it.
 
          // Look up this pair of hulls by ID
          ConvexHull* ch1 = GetHull(hp.m_hullA);
          ConvexHull* ch2 = GetHull(hp.m_hullB);
 
          // If both hulls are still valid, then we merge them, delete the old
          // two hulls and recompute the cost matrix for the new combined hull
          // we have created
          if (ch1 && ch2)
          {
            // This is the convex hull which results from combining the
            // vertices in the two source hulls
            ConvexHull* combinedHull = ComputeCombinedConvexHull(*ch1, *ch2);
            // The two old convex hulls are going to get removed
            RemoveHull(hp.m_hullA);
            RemoveHull(hp.m_hullB);
 
            m_meshId++;
            combinedHull->m_meshId = m_meshId;
            tasks.clear();
            tasks.reserve(m_hulls.size());
 
            // Compute the cost between this new merged hull
            // and all existing convex hulls and then
            // add that to the priority queue
            for (auto& i : m_hulls)
            {
              if (m_canceled)
              {
                break;
              }
              ConvexHull* secondHull = i.second;
              CostTask ct;
              ct.m_hullA = combinedHull;
              ct.m_hullB = secondHull;
              ct.m_this = this;
              if (DoFastCost(ct))
              {
              }
              else
              {
                tasks.push_back(std::move(ct));
              }
            }
            m_hulls[combinedHull->m_meshId] = combinedHull;
            // See how many merge cost tasks were posted
            // If there are 8 or more and we are running asynchronously, then do them that way.
#if !VHACD_DISABLE_THREADING
            if (m_threadPool && tasks.size() >= 2)
            {
              for (CostTask& task : tasks)
              {
                task.m_future = m_threadPool->enqueue([&task] { computeMergeCostTask(task); });
              }
 
              for (CostTask& task : tasks)
              {
                task.m_future.get();
              }
            }
            else
#endif
            {
              for (CostTask& task : tasks)
              {
                PerformMergeCostTask(task);
              }
            }
 
            for (CostTask& task : tasks)
            {
              AddCostToPriorityQueue(task);
            }
          }
        }
        // Ok...once we are done, we copy the results!
        m_meshId -= 0;
        ProgressUpdate(Stages::FINALIZING_RESULTS, 0, "Finalizing results");
        for (auto& i : m_hulls)
        {
          if (m_canceled)
          {
            break;
          }
          ConvexHull* ch = i.second;
          // We now must reduce the convex hull
          if (ch->m_points.size() > m_params.m_maxNumVerticesPerCH || m_params.m_shrinkWrap)
          {
            ConvexHull* reduce = ComputeReducedConvexHull(*ch, m_params.m_maxNumVerticesPerCH, m_params.m_shrinkWrap);
            ReleaseConvexHull(ch);
            ch = reduce;
          }
          ScaleOutputConvexHull(*ch);
          ch->m_meshId = m_meshId;
          m_meshId++;
          m_convexHulls.push_back(ch);
        }
        m_hulls.clear();  // since the hulls were moved into the output list, we don't need to delete them from this
                          // container
        ProgressUpdate(Stages::FINALIZING_RESULTS, 100, "Finalized results complete");
      }
    }
    else
    {
      ProgressUpdate(Stages::FINALIZING_RESULTS, 0, "Finalizing results");
      m_meshId = 0;
      for (auto& ch : hulls)
      {
        // We now must reduce the convex hull
        if (ch->m_points.size() > m_params.m_maxNumVerticesPerCH || m_params.m_shrinkWrap)
        {
          ConvexHull* reduce = ComputeReducedConvexHull(*ch, m_params.m_maxNumVerticesPerCH, m_params.m_shrinkWrap);
          ReleaseConvexHull(ch);
          ch = reduce;
        }
        ScaleOutputConvexHull(*ch);
        ch->m_meshId = m_meshId;
        m_meshId++;
        m_convexHulls.push_back(ch);
      }
      m_hulls.clear();
      ProgressUpdate(Stages::FINALIZING_RESULTS, 100, "Finalized results");
    }
  }
}
 
double VHACDImpl::ComputeConvexHullVolume(const ConvexHull& sm)
{
  double totalVolume = 0;
  VHACD::Vect3 bary(0, 0, 0);
  for (uint32_t i = 0; i < sm.m_points.size(); i++)
  {
    VHACD::Vect3 p(sm.m_points[i]);
    bary += p;
  }
  bary /= double(sm.m_points.size());
 
  for (uint32_t i = 0; i < sm.m_triangles.size(); i++)
  {
    uint32_t i1 = sm.m_triangles[i].mI0;
    uint32_t i2 = sm.m_triangles[i].mI1;
    uint32_t i3 = sm.m_triangles[i].mI2;
 
    VHACD::Vect3 ver0(sm.m_points[i1]);
    VHACD::Vect3 ver1(sm.m_points[i2]);
    VHACD::Vect3 ver2(sm.m_points[i3]);
 
    totalVolume += ComputeVolume4(ver0, ver1, ver2, bary);
  }
  totalVolume = totalVolume / double(6.0);
  return totalVolume;
}
 
double
VHACDImpl::ComputeVolume4(const VHACD::Vect3& a, const VHACD::Vect3& b, const VHACD::Vect3& c, const VHACD::Vect3& d)
{
  VHACD::Vect3 ad = a - d;
  VHACD::Vect3 bd = b - d;
  VHACD::Vect3 cd = c - d;
  VHACD::Vect3 bcd = bd.Cross(cd);
  double dot = ad.Dot(bcd);
  return dot;
}
 
double VHACDImpl::ComputeConcavity(double volumeSeparate, double volumeCombined, double volumeMesh)
{
  return fabs(volumeSeparate - volumeCombined) / volumeMesh;
}
 
bool VHACDImpl::DoFastCost(CostTask& mt)
{
  bool ret = false;
 
  ConvexHull* ch1 = mt.m_hullA;
  ConvexHull* ch2 = mt.m_hullB;
 
  VHACD::BoundsAABB ch1b(ch1->mBmin, ch1->mBmax);
  VHACD::BoundsAABB ch2b(ch2->mBmin, ch2->mBmax);
  if (!ch1b.Intersects(ch2b))
  {
    VHACD::BoundsAABB b = ch1b.Union(ch2b);
 
    double combinedVolume = b.Volume();
    double concavity = ComputeConcavity(ch1->m_volume + ch2->m_volume, combinedVolume, m_overallHullVolume);
    HullPair hp(ch1->m_meshId, ch2->m_meshId, concavity);
    m_hullPairQueue.push(hp);
    ret = true;
  }
  return ret;
}
 
void VHACDImpl::PerformMergeCostTask(CostTask& mt)
{
  ConvexHull* ch1 = mt.m_hullA;
  ConvexHull* ch2 = mt.m_hullB;
 
  double volume1 = ch1->m_volume;
  double volume2 = ch2->m_volume;
 
  ConvexHull* combined = ComputeCombinedConvexHull(*ch1,
                                                   *ch2);      // Build the combined convex hull
  double combinedVolume = ComputeConvexHullVolume(*combined);  // get the combined volume
  mt.m_concavity = ComputeConcavity(volume1 + volume2, combinedVolume, m_overallHullVolume);
  ReleaseConvexHull(combined);
}
 
IVHACD::ConvexHull* VHACDImpl::ComputeReducedConvexHull(const ConvexHull& ch,
                                                        uint32_t maxVerts,
                                                        bool projectHullVertices)
{
  SimpleMesh sourceConvexHull;
 
  sourceConvexHull.m_vertices = ch.m_points;
  sourceConvexHull.m_indices = ch.m_triangles;
 
  ShrinkWrap(sourceConvexHull, m_AABBTree, maxVerts, m_voxelScale * 4, projectHullVertices);
 
  ConvexHull* ret = new ConvexHull;
 
  ret->m_points = sourceConvexHull.m_vertices;
  ret->m_triangles = sourceConvexHull.m_indices;
 
  VHACD::BoundsAABB b = VHACD::BoundsAABB(ret->m_points).Inflate(double(0.1));
  ret->mBmin = b.GetMin();
  ret->mBmax = b.GetMax();
  ComputeCentroid(ret->m_points, ret->m_triangles, ret->m_center);
 
  ret->m_volume = ComputeConvexHullVolume(*ret);
 
  // Return the convex hull
  return ret;
}
 
IVHACD::ConvexHull* VHACDImpl::ComputeCombinedConvexHull(const ConvexHull& sm1, const ConvexHull& sm2)
{
  uint32_t vcount = uint32_t(sm1.m_points.size() + sm2.m_points.size());  // Total vertices from both hulls
  std::vector<VHACD::Vertex> vertices(vcount);
  auto it = std::copy(sm1.m_points.begin(), sm1.m_points.end(), vertices.begin());
  std::copy(sm2.m_points.begin(), sm2.m_points.end(), it);
 
  VHACD::QuickHull qh;
  qh.ComputeConvexHull(vertices, vcount);
 
  ConvexHull* ret = new ConvexHull;
  ret->m_points = qh.GetVertices();
  ret->m_triangles = qh.GetIndices();
 
  ret->m_volume = ComputeConvexHullVolume(*ret);
 
  VHACD::BoundsAABB b = VHACD::BoundsAABB(qh.GetVertices()).Inflate(double(0.1));
  ret->mBmin = b.GetMin();
  ret->mBmax = b.GetMax();
  ComputeCentroid(ret->m_points, ret->m_triangles, ret->m_center);
 
  // Return the convex hull
  return ret;
}
 
IVHACD::ConvexHull* VHACDImpl::GetHull(uint32_t index)
{
  ConvexHull* ret = nullptr;
 
  auto found = m_hulls.find(index);
  if (found != m_hulls.end())
  {
    ret = found->second;
  }
 
  return ret;
}
 
bool VHACDImpl::RemoveHull(uint32_t index)
{
  bool ret = false;
  auto found = m_hulls.find(index);
  if (found != m_hulls.end())
  {
    ret = true;
    ReleaseConvexHull(found->second);
    m_hulls.erase(found);
  }
  return ret;
}
 
IVHACD::ConvexHull* VHACDImpl::CopyConvexHull(const ConvexHull& source)
{
  ConvexHull* ch = new ConvexHull;
  *ch = source;
 
  return ch;
}
 
const char* VHACDImpl::GetStageName(Stages stage) const
{
  const char* ret = "unknown";
  switch (stage)
  {
    case Stages::COMPUTE_BOUNDS_OF_INPUT_MESH:
      ret = "COMPUTE_BOUNDS_OF_INPUT_MESH";
      break;
    case Stages::REINDEXING_INPUT_MESH:
      ret = "REINDEXING_INPUT_MESH";
      break;
    case Stages::CREATE_RAYCAST_MESH:
      ret = "CREATE_RAYCAST_MESH";
      break;
    case Stages::VOXELIZING_INPUT_MESH:
      ret = "VOXELIZING_INPUT_MESH";
      break;
    case Stages::BUILD_INITIAL_CONVEX_HULL:
      ret = "BUILD_INITIAL_CONVEX_HULL";
      break;
    case Stages::PERFORMING_DECOMPOSITION:
      ret = "PERFORMING_DECOMPOSITION";
      break;
    case Stages::INITIALIZING_CONVEX_HULLS_FOR_MERGING:
      ret = "INITIALIZING_CONVEX_HULLS_FOR_MERGING";
      break;
    case Stages::COMPUTING_COST_MATRIX:
      ret = "COMPUTING_COST_MATRIX";
      break;
    case Stages::MERGING_CONVEX_HULLS:
      ret = "MERGING_CONVEX_HULLS";
      break;
    case Stages::FINALIZING_RESULTS:
      ret = "FINALIZING_RESULTS";
      break;
    case Stages::NUM_STAGES:
      // Should be unreachable, here to silence enumeration value not handled in switch warnings
      // GCC/Clang's -Wswitch
      break;
  }
  return ret;
}
 
void VHACDImpl::ProgressUpdate(Stages stage, double stageProgress, const char* operation)
{
  if (m_params.m_callback)
  {
    double overallProgress = (double(stage) * 100) / double(Stages::NUM_STAGES);
    const char* s = GetStageName(stage);
    m_params.m_callback->Update(overallProgress, stageProgress, s, operation);
  }
}
 
bool VHACDImpl::IsCanceled() const { return m_canceled; }
 
IVHACD* CreateVHACD(void)
{
  VHACDImpl* ret = new VHACDImpl;
  return static_cast<IVHACD*>(ret);
}
 
IVHACD* CreateVHACD(void);
 
#if !VHACD_DISABLE_THREADING
 
class LogMessage
{
public:
  double m_overallProgress{ double(-1.0) };
  double m_stageProgress{ double(-1.0) };
  std::string m_stage;
  std::string m_operation;
};
 
class VHACDAsyncImpl : public VHACD::IVHACD,
                       public VHACD::IVHACD::IUserCallback,
                       VHACD::IVHACD::IUserLogger,
                       VHACD::IVHACD::IUserTaskRunner
{
public:
  VHACDAsyncImpl() = default;
 
  ~VHACDAsyncImpl() override;
 
  void Cancel() override final;
 
  bool Compute(const float* const points,
               const uint32_t countPoints,
               const uint32_t* const triangles,
               const uint32_t countTriangles,
               const Parameters& params) override final;
 
  bool Compute(const double* const points,
               const uint32_t countPoints,
               const uint32_t* const triangles,
               const uint32_t countTriangles,
               const Parameters& params) override final;
 
  bool GetConvexHull(const uint32_t index, VHACD::IVHACD::ConvexHull& ch) const override final;
 
  uint32_t GetNConvexHulls() const override final;
 
  void Clean() override final;  // release internally allocated memory
 
  void Release() override final;  // release IVHACD
 
  // Will compute the center of mass of the convex hull decomposition results and return it
  // in 'centerOfMass'.  Returns false if the center of mass could not be computed.
  bool ComputeCenterOfMass(double centerOfMass[3]) const override;
 
  bool IsReady() const override final;
 
  uint32_t findNearestConvexHull(const double pos[3], double& distanceToHull) override final;
 
  void Update(const double overallProgress,
              const double stageProgress,
              const char* const stage,
              const char* operation) override final;
 
  void Log(const char* const msg) override final;
 
  void* StartTask(std::function<void()> func) override;
 
  void JoinTask(void* Task) override;
 
  bool Compute(const Parameters params);
 
  bool ComputeNow(const std::vector<VHACD::Vertex>& points,
                  const std::vector<VHACD::Triangle>& triangles,
                  const Parameters& _desc);
 
  // As a convenience for the calling application we only send it update and log messages from it's own main
  // thread.  This reduces the complexity burden on the caller by making sure it only has to deal with log
  // messages in it's main application thread.
  void ProcessPendingMessages() const;
 
private:
  VHACD::VHACDImpl m_VHACD;
  std::vector<VHACD::Vertex> m_vertices;
  std::vector<VHACD::Triangle> m_indices;
  VHACD::IVHACD::IUserCallback* m_callback{ nullptr };
  VHACD::IVHACD::IUserLogger* m_logger{ nullptr };
  VHACD::IVHACD::IUserTaskRunner* m_taskRunner{ nullptr };
  void* m_task{ nullptr };
  std::atomic<bool> m_running{ false };
  std::atomic<bool> m_cancel{ false };
 
  // Thread safe caching mechanism for messages and update status.
  // This is so that caller always gets messages in his own thread
  // Member variables are marked as 'mutable' since the message dispatch function
  // is called from const query methods.
  mutable std::mutex m_messageMutex;
  mutable std::vector<LogMessage> m_messages;
  mutable std::atomic<bool> m_haveMessages{ false };
};
 
VHACDAsyncImpl::~VHACDAsyncImpl() { Cancel(); }
 
void VHACDAsyncImpl::Cancel()
{
  m_cancel = true;
  m_VHACD.Cancel();
 
  if (m_task)
  {
    m_taskRunner->JoinTask(m_task);  // Wait for the thread to fully exit before we delete the instance
    m_task = nullptr;
  }
  m_cancel = false;  // clear the cancel semaphore
}
 
bool VHACDAsyncImpl::Compute(const float* const points,
                             const uint32_t countPoints,
                             const uint32_t* const triangles,
                             const uint32_t countTriangles,
                             const Parameters& params)
{
  m_vertices.reserve(countPoints);
  for (uint32_t i = 0; i < countPoints; ++i)
  {
    m_vertices.emplace_back(points[i * 3 + 0], points[i * 3 + 1], points[i * 3 + 2]);
  }
 
  m_indices.reserve(countTriangles);
  for (uint32_t i = 0; i < countTriangles; ++i)
  {
    m_indices.emplace_back(triangles[i * 3 + 0], triangles[i * 3 + 1], triangles[i * 3 + 2]);
  }
 
  return Compute(params);
}
 
bool VHACDAsyncImpl::Compute(const double* const points,
                             const uint32_t countPoints,
                             const uint32_t* const triangles,
                             const uint32_t countTriangles,
                             const Parameters& params)
{
  // We need to copy the input vertices and triangles into our own buffers so we can operate
  // on them safely from the background thread.
  // Can't be local variables due to being asynchronous
  m_vertices.reserve(countPoints);
  for (uint32_t i = 0; i < countPoints; ++i)
  {
    m_vertices.emplace_back(points[i * 3 + 0], points[i * 3 + 1], points[i * 3 + 2]);
  }
 
  m_indices.reserve(countTriangles);
  for (uint32_t i = 0; i < countTriangles; ++i)
  {
    m_indices.emplace_back(triangles[i * 3 + 0], triangles[i * 3 + 1], triangles[i * 3 + 2]);
  }
 
  return Compute(params);
}
 
bool VHACDAsyncImpl::GetConvexHull(const uint32_t index, VHACD::IVHACD::ConvexHull& ch) const
{
  return m_VHACD.GetConvexHull(index, ch);
}
 
uint32_t VHACDAsyncImpl::GetNConvexHulls() const
{
  ProcessPendingMessages();
  return m_VHACD.GetNConvexHulls();
}
 
void VHACDAsyncImpl::Clean()
{
  Cancel();
  m_VHACD.Clean();
}
 
void VHACDAsyncImpl::Release() { delete this; }
 
bool VHACDAsyncImpl::ComputeCenterOfMass(double centerOfMass[3]) const
{
  bool ret = false;
 
  centerOfMass[0] = 0;
  centerOfMass[1] = 0;
  centerOfMass[2] = 0;
 
  if (IsReady())
  {
    ret = m_VHACD.ComputeCenterOfMass(centerOfMass);
  }
  return ret;
}
 
bool VHACDAsyncImpl::IsReady() const
{
  ProcessPendingMessages();
  return !m_running;
}
 
uint32_t VHACDAsyncImpl::findNearestConvexHull(const double pos[3], double& distanceToHull)
{
  uint32_t ret = 0;  // The default return code is zero
 
  distanceToHull = 0;
  // First, make sure that we have valid and completed results
  if (IsReady())
  {
    ret = m_VHACD.findNearestConvexHull(pos, distanceToHull);
  }
 
  return ret;
}
 
void VHACDAsyncImpl::Update(const double overallProgress,
                            const double stageProgress,
                            const char* const stage,
                            const char* operation)
{
  m_messageMutex.lock();
  LogMessage m;
  m.m_operation = std::string(operation);
  m.m_overallProgress = overallProgress;
  m.m_stageProgress = stageProgress;
  m.m_stage = std::string(stage);
  m_messages.push_back(m);
  m_haveMessages = true;
  m_messageMutex.unlock();
}
 
void VHACDAsyncImpl::Log(const char* const msg)
{
  m_messageMutex.lock();
  LogMessage m;
  m.m_operation = std::string(msg);
  m_haveMessages = true;
  m_messages.push_back(m);
  m_messageMutex.unlock();
}
 
void* VHACDAsyncImpl::StartTask(std::function<void()> func) { return new std::thread(func); }
 
void VHACDAsyncImpl::JoinTask(void* Task)
{
  std::thread* t = static_cast<std::thread*>(Task);
  t->join();
  delete t;
}
 
bool VHACDAsyncImpl::Compute(Parameters params)
{
  Cancel();  // if we previously had a solution running; cancel it.
 
  m_taskRunner = params.m_taskRunner ? params.m_taskRunner : this;
  params.m_taskRunner = m_taskRunner;
 
  m_running = true;
  m_task = m_taskRunner->StartTask([this, params]() {
    ComputeNow(m_vertices, m_indices, params);
    // If we have a user provided callback and the user did *not* call 'cancel' we notify him that the
    // task is completed. However..if the user selected 'cancel' we do not send a completed notification event.
    if (params.m_callback && !m_cancel)
    {
      params.m_callback->NotifyVHACDComplete();
    }
    m_running = false;
  });
  return true;
}
 
bool VHACDAsyncImpl::ComputeNow(const std::vector<VHACD::Vertex>& points,
                                const std::vector<VHACD::Triangle>& triangles,
                                const Parameters& _desc)
{
  uint32_t ret = 0;
 
  Parameters desc;
  m_callback = _desc.m_callback;
  m_logger = _desc.m_logger;
 
  desc = _desc;
  // Set our intercepting callback interfaces if non-null
  desc.m_callback = _desc.m_callback ? this : nullptr;
  desc.m_logger = _desc.m_logger ? this : nullptr;
 
  // If not task runner provided, then use the default one
  if (desc.m_taskRunner == nullptr)
  {
    desc.m_taskRunner = this;
  }
 
  bool ok = m_VHACD.Compute(points, triangles, desc);
  if (ok)
  {
    ret = m_VHACD.GetNConvexHulls();
  }
 
  return ret ? true : false;
}
 
void VHACDAsyncImpl::ProcessPendingMessages() const
{
  if (m_cancel)
  {
    return;
  }
  if (m_haveMessages)
  {
    m_messageMutex.lock();
    for (auto& i : m_messages)
    {
      if (i.m_overallProgress == -1)
      {
        if (m_logger)
        {
          m_logger->Log(i.m_operation.c_str());
        }
      }
      else if (m_callback)
      {
        m_callback->Update(i.m_overallProgress, i.m_stageProgress, i.m_stage.c_str(), i.m_operation.c_str());
      }
    }
    m_messages.clear();
    m_haveMessages = false;
    m_messageMutex.unlock();
  }
}
 
IVHACD* CreateVHACD_ASYNC()
{
  VHACDAsyncImpl* m = new VHACDAsyncImpl;
  return static_cast<IVHACD*>(m);
}
#endif
 
}  // namespace VHACD
 
#ifdef _MSC_VER
#pragma warning(pop)
#endif  // _MSC_VER
 
#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif  // __GNUC__
 
#endif  // ENABLE_VHACD_IMPLEMENTATION
 
#endif  // VHACD_H
TESSERACT_COMMON_IGNORE_WARNINGS_PUSH