Extras/HACD/hacdHACD.h

   1 /* Copyright (c) 2011 Khaled Mamou (kmamou at gmail dot com)\r
   2  All rights reserved.\r
   3  \r
   4  \r
   5  Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:\r
   6  \r
   7  1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.\r
   8  \r
   9  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.\r
  10  \r
  11  3. The names of the contributors may not be used to endorse or promote products derived from this software without specific prior written permission.\r
  12  \r
  13  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.\r
  14  */\r
  15 #pragma once\r
  16 #ifndef HACD_HACD_H\r
  17 #define HACD_HACD_H\r
  18 #include "hacdVersion.h"\r
  19 #include "hacdVector.h"\r
  20 #include "hacdGraph.h"\r
  21 #include "hacdICHull.h"\r
  22 #include <set>\r
  23 #include <vector>\r
  24 #include <queue>\r
  25 #include <functional>\r
  26 \r
  27 namespace HACD\r
  28 {\r
  29     const double                                    sc_pi = 3.14159265;\r
  30         class HACD;\r
  31 \r
  32         // just to be able to set the capcity of the container\r
  33         \r
  34         template<class _Ty, class _Container = std::vector<_Ty>, class _Pr = std::less<typename _Container::value_type> >\r
  35         class reservable_priority_queue: public std::priority_queue<_Ty, _Container, _Pr> \r
  36         {\r
  37         typedef typename std::priority_queue<_Ty, _Container, _Pr>::size_type size_type;\r
  38         public:\r
  39                                                     reservable_priority_queue(size_type capacity = 0) { reserve(capacity); };\r
  40                 void                                                                            reserve(size_type capacity) { this->c.reserve(capacity); } \r
  41         size_type                                                                       capacity() const { return this->c.capacity(); } \r
  42         };\r
  43         \r
  44         //! priority queque element\r
  45     class GraphEdgePriorityQueue\r
  46     {\r
  47                 public:\r
  48                         //! Constructor\r
  49                         //! @param name edge's id\r
  50                         //! @param priority edge's priority\r
  51                                                                                                         GraphEdgePriorityQueue(long name, Real priority)\r
  52                                                                                                         {\r
  53                                                                                                                 m_name = name;\r
  54                                                                                                                 m_priority = priority;\r
  55                                                                                                         }\r
  56                         //! Destructor\r
  57                                                                                                         ~GraphEdgePriorityQueue(void){}\r
  58                 private:\r
  59                         long                                                                    m_name;                                         //!< edge name\r
  60                         Real                                    m_priority;                                     //!< priority\r
  61                 //! Operator < for GraphEdgePQ\r
  62         friend bool                                 operator<(const GraphEdgePriorityQueue & lhs, const GraphEdgePriorityQueue & rhs);\r
  63                 //! Operator > for GraphEdgePQ\r
  64         friend bool                                 operator>(const GraphEdgePriorityQueue & lhs, const GraphEdgePriorityQueue & rhs);\r
  65                 friend class HACD;\r
  66     };\r
  67     inline bool                                                                         operator<(const GraphEdgePriorityQueue & lhs, const GraphEdgePriorityQueue & rhs)\r
  68                                                                                                         {\r
  69                                                                                                                 return lhs.m_priority<rhs.m_priority;\r
  70                                                                                                         }\r
  71     inline bool                                                                         operator>(const GraphEdgePriorityQueue & lhs, const GraphEdgePriorityQueue & rhs)\r
  72                                                                                                         {\r
  73                                                                                                                 return lhs.m_priority>rhs.m_priority;\r
  74                                                                                                         }\r
  75     typedef bool (*CallBackFunction)(const char *, double, double, size_t);\r
  76 \r
  77         //! Provides an implementation of the Hierarchical Approximate Convex Decomposition (HACD) technique described in "A Simple and Efficient Approach for 3D Mesh Approximate Convex Decomposition" Game Programming Gems 8 - Chapter 2.8, p.202. A short version of the chapter was published in ICIP09 and is available at ftp://ftp.elet.polimi.it/users/Stefano.Tubaro/ICIP_USB_Proceedings_v2/pdfs/0003501.pdf\r
  78     class HACD\r
  79         {            \r
  80     public:\r
  81 \r
  82                 //! Gives the triangles partitionas an array of size m_nTriangles where the i-th element specifies the cluster to which belong the i-th triangle\r
  83                 //! @return triangles partition\r
  84                 const long * const                                                      GetPartition() const { return m_partition;}\r
  85         //! Sets the scale factor\r
  86                 //! @param scale scale factor\r
  87                 void                                                                            SetScaleFactor(double  scale) { m_scale = scale;}\r
  88                 //! Gives the scale factor\r
  89                 //! @return scale factor\r
  90                 const double                                                            GetScaleFactor() const { return m_scale;}\r
  91                 //! Sets the call-back function\r
  92                 //! @param callBack pointer to the call-back function\r
  93                 void                                                                            SetCallBack(CallBackFunction  callBack) { m_callBack = callBack;}\r
  94                 //! Gives the call-back function\r
  95                 //! @return pointer to the call-back function\r
  96                 const CallBackFunction                      GetCallBack() const { return m_callBack;}\r
  97         \r
  98         //! Specifies whether faces points should be added when computing the concavity\r
  99                 //! @param addFacesPoints true = faces points should be added\r
 100                 void                                                                            SetAddFacesPoints(bool  addFacesPoints) { m_addFacesPoints = addFacesPoints;}\r
 101                 //! Specifies wheter faces points should be added when computing the concavity\r
 102                 //! @return true = faces points should be added\r
 103                 const bool                                                                      GetAddFacesPoints() const { return m_addFacesPoints;}\r
 104         //! Specifies whether extra points should be added when computing the concavity\r
 105                 //! @param addExteraDistPoints true = extra points should be added\r
 106                 void                                                                            SetAddExtraDistPoints(bool  addExtraDistPoints) { m_addExtraDistPoints = addExtraDistPoints;}\r
 107                 //! Specifies wheter extra points should be added when computing the concavity\r
 108                 //! @return true = extra points should be added\r
 109                 const bool                                                                      GetAddExtraDistPoints() const { return m_addExtraDistPoints;}\r
 110         //! Specifies whether extra points should be added when computing the concavity\r
 111                 //! @param addExteraDistPoints true = extra points should be added\r
 112                 void                                                                            SetAddNeighboursDistPoints(bool  addNeighboursDistPoints) { m_addNeighboursDistPoints = addNeighboursDistPoints;}\r
 113                 //! Specifies wheter extra points should be added when computing the concavity\r
 114                 //! @return true = extra points should be added\r
 115                 const bool                                                                      GetAddNeighboursDistPoints() const { return m_addNeighboursDistPoints;}\r
 116         //! Sets the points of the input mesh (Remark: the input points will be scaled and shifted. Use DenormalizeData() to invert those operations)\r
 117                 //! @param points pointer to the input points\r
 118                 void                                                                            SetPoints(Vec3<Real>  * points) { m_points = points;}\r
 119                 //! Gives the points of the input mesh (Remark: the input points will be scaled and shifted. Use DenormalizeData() to invert those operations)\r
 120                 //! @return pointer to the input points \r
 121                 const Vec3<Real> *                          GetPoints() const { return m_points;}\r
 122                 //! Sets the triangles of the input mesh.\r
 123                 //! @param triangles points pointer to the input points\r
 124                 void                                                                            SetTriangles(Vec3<long>  * triangles) { m_triangles = triangles;}\r
 125                 //! Gives the triangles in the input mesh \r
 126                 //! @return pointer to the input triangles \r
 127                 const Vec3<long>   *                                GetTriangles() const { return m_triangles;}\r
 128                 //! Sets the number of points in the input mesh.\r
 129                 //! @param nPoints number of points the input mesh\r
 130                 void                                                                            SetNPoints(size_t nPoints) { m_nPoints = nPoints;}\r
 131                 //! Gives the number of points in the input mesh.\r
 132                 //! @return number of points the input mesh\r
 133                 const size_t                                                            GetNPoints() const { return m_nPoints;}\r
 134                 //! Sets the number of triangles in the input mesh.\r
 135                 //! @param nTriangles number of triangles in the input mesh\r
 136                 void                                                                            SetNTriangles(size_t nTriangles) { m_nTriangles = nTriangles;}\r
 137                 //! Gives the number of triangles in the input mesh.\r
 138                 //! @return number of triangles the input mesh\r
 139                 const size_t                                                            GetNTriangles() const { return m_nTriangles;}\r
 140                 //! Sets the minimum number of clusters to be generated.\r
 141                 //! @param nClusters minimum number of clusters\r
 142                 void                                                                            SetNClusters(size_t nClusters) { m_nMinClusters = nClusters;}\r
 143                 //! Gives the number of generated clusters.\r
 144                 //! @return number of generated clusters\r
 145                 const size_t                                                            GetNClusters() const { return m_nClusters;}\r
 146                 //! Sets the maximum allowed concavity.\r
 147                 //! @param concavity maximum concavity\r
 148                 void                                                                            SetConcavity(double concavity) { m_concavity = concavity;}\r
 149                 //! Gives the maximum allowed concavity.\r
 150                 //! @return maximum concavity\r
 151                 double                                      GetConcavity() const { return m_concavity;}\r
 152                 //! Sets the maximum allowed distance to get CCs connected.\r
 153                 //! @param concavity maximum distance to get CCs connected\r
 154                 void                                                                            SetConnectDist(double ccConnectDist) { m_ccConnectDist = ccConnectDist;}\r
 155                 //! Gives the maximum allowed distance to get CCs connected.\r
 156                 //! @return maximum distance to get CCs connected\r
 157                 double                                      GetConnectDist() const { return m_ccConnectDist;}        \r
 158         //! Sets the volume weight.\r
 159                 //! @param beta volume weight\r
 160         void                                                                            SetVolumeWeight(double beta) { m_beta = beta;}\r
 161                 //! Gives the volume weight.\r
 162                 //! @return volume weight\r
 163         double                                      GetVolumeWeight() const { return m_beta;}   \r
 164                 //! Sets the compacity weight (i.e. parameter alpha in ftp://ftp.elet.polimi.it/users/Stefano.Tubaro/ICIP_USB_Proceedings_v2/pdfs/0003501.pdf).\r
 165                 //! @param alpha compacity weight\r
 166         void                                                                            SetCompacityWeight(double alpha) { m_alpha = alpha;}\r
 167                 //! Gives the compacity weight (i.e. parameter alpha in ftp://ftp.elet.polimi.it/users/Stefano.Tubaro/ICIP_USB_Proceedings_v2/pdfs/0003501.pdf).\r
 168                 //! @return compacity weight\r
 169         double                                      GetCompacityWeight() const { return m_alpha;}       \r
 170                 //! Sets the maximum number of vertices for each generated convex-hull.\r
 171                 //! @param nVerticesPerCH maximum # vertices per CH\r
 172         void                                                                            SetNVerticesPerCH(size_t nVerticesPerCH) { m_nVerticesPerCH = nVerticesPerCH;}\r
 173                 //! Gives the maximum number of vertices for each generated convex-hull.\r
 174                 //! @return maximum # vertices per CH\r
 175                 const size_t                                                            GetNVerticesPerCH() const { return m_nVerticesPerCH;}\r
 176                 //! Gives the number of vertices for the cluster number numCH.\r
 177                 //! @return number of vertices\r
 178                 size_t                                      GetNPointsCH(size_t numCH) const;\r
 179                 //! Gives the number of triangles for the cluster number numCH.\r
 180                 //! @param numCH cluster's number\r
 181                 //! @return number of triangles\r
 182         size_t                                      GetNTrianglesCH(size_t numCH) const;\r
 183                 //! Gives the vertices and the triangles of the cluster number numCH.\r
 184                 //! @param numCH cluster's number\r
 185                 //! @param points pointer to the vector of points to be filled\r
 186                 //! @param triangles pointer to the vector of triangles to be filled\r
 187                 //! @return true if sucess\r
 188         bool                                        GetCH(size_t numCH, Vec3<Real> * const points, Vec3<long> * const triangles);     \r
 189                 //! Computes the HACD decomposition.\r
 190                 //! @param fullCH specifies whether to generate convex-hulls with a full or limited (i.e. < m_nVerticesPerCH) number of vertices\r
 191         //! @param exportDistPoints specifies wheter distance points should ne exported or not (used only for debugging).\r
 192                 //! @return true if sucess\r
 193         bool                                                                            Compute(bool fullCH=false, bool exportDistPoints=false);\r
 194                 //! Saves the generated convex-hulls in a VRML 2.0 file.\r
 195                 //! @param fileName the output file name\r
 196                 //! @param uniColor specifies whether the different convex-hulls should have the same color or not\r
 197         //! @param numCluster specifies the cluster to be saved, if numCluster < 0 export all clusters\r
 198         //! @return true if sucess\r
 199                 bool                                                                            Save(const char * fileName, bool uniColor, long numCluster=-1) const;\r
 200                 //! Shifts and scales to the data to have all the coordinates between 0.0 and 1000.0.\r
 201                 void                                                                            NormalizeData();\r
 202                 //! Inverse the operations applied by NormalizeData().\r
 203                 void                                                                            DenormalizeData();\r
 204         //! Constructor.\r
 205                                                                                                         HACD(void);\r
 206                 //! Destructor.\r
 207                                                                                                         ~HACD(void);\r
 208 \r
 209         private:\r
 210                 //! Gives the edge index.\r
 211                 //! @param a first vertex id\r
 212                 //! @param b second vertex id\r
 213                 //! @return edge's index\r
 214                 static unsigned long long                                       GetEdgeIndex(unsigned long long a, unsigned long long b) \r
 215                                                                                                         { \r
 216                                                                                                                 if (a > b) return (a << 32) + b;\r
 217                                                                                                                 else       return (b << 32) + a;\r
 218                                                                                                         }\r
 219                 //! Computes the concavity of a cluster.\r
 220                 //! @param ch the cluster's convex-hull\r
 221                 //! @param distPoints the cluster's points \r
 222                 //! @return cluster's concavity\r
 223                 double                                                                          Concavity(ICHull & ch, std::map<long, DPoint> & distPoints);\r
 224                 //! Computes the perimeter of a cluster.\r
 225                 //! @param triIndices the cluster's triangles\r
 226                 //! @param distPoints the cluster's points \r
 227                 //! @return cluster's perimeter\r
 228         double                                                                          ComputePerimeter(const std::vector<long> & triIndices) const;\r
 229                 //! Creates the Graph by associating to each mesh triangle a vertex in the graph and to each couple of adjacent triangles an edge in the graph.\r
 230         void                                                                            CreateGraph();  \r
 231                 //! Initializes the graph costs and computes the vertices normals\r
 232         void                                                                            InitializeDualGraph();\r
 233                 //! Computes the cost of an edge\r
 234                 //! @param e edge's id\r
 235         void                                        ComputeEdgeCost(size_t e);\r
 236                 //! Initializes the priority queue\r
 237                 //! @param fast specifies whether fast mode is used\r
 238                 //! @return true if success\r
 239         bool                                        InitializePriorityQueue();\r
 240         //! Cleans the intersection between convex-hulls\r
 241         void                                        CleanClusters();\r
 242         //! Computes convex-hulls from partition information\r
 243         //! @param fullCH specifies whether to generate convex-hulls with a full or limited (i.e. < m_nVerticesPerCH) number of vertices\r
 244                 void                                                                            ComputeConvexHulls(bool fullCH);\r
 245                 //! Simplifies the graph\r
 246                 //! @param fast specifies whether fast mode is used\r
 247                 void                                                                            Simplify();\r
 248 \r
 249         private:\r
 250                 double                                                                          m_scale;                                        //>! scale factor used for NormalizeData() and DenormalizeData()\r
 251         Vec3<long> *                                                            m_triangles;                            //>! pointer the triangles array\r
 252         Vec3<Real> *                                m_points;                                   //>! pointer the points array\r
 253         Vec3<Real> *                                m_facePoints;               //>! pointer to the faces points array\r
 254         Vec3<Real> *                                m_faceNormals;              //>! pointer to the faces normals array\r
 255         Vec3<Real> *                                m_normals;                                  //>! pointer the normals array\r
 256         size_t                                                                          m_nTriangles;                           //>! number of triangles in the original mesh\r
 257         size_t                                                                          m_nPoints;                                      //>! number of vertices in the original mesh\r
 258         size_t                                                                          m_nClusters;                            //>! number of clusters\r
 259         size_t                                                                          m_nMinClusters;                         //>! minimum number of clusters\r
 260         double                                                                          m_ccConnectDist;                        //>! maximum allowed distance to connect CCs\r
 261         double                                                                          m_concavity;                            //>! maximum concavity\r
 262                 double                                                                          m_alpha;                                        //>! compacity weigth\r
 263         double                                      m_beta;                     //>! volume weigth\r
 264         double                                                                          m_diag;                                         //>! length of the BB diagonal\r
 265                 Vec3<Real>                                  m_barycenter;                               //>! barycenter of the mesh\r
 266         std::vector< long >                         m_cVertices;                                //>! array of vertices each belonging to a different cluster\r
 267         ICHull *                                    m_convexHulls;                              //>! convex-hulls associated with the final HACD clusters\r
 268                 Graph                                                                           m_graph;                                        //>! simplification graph\r
 269         size_t                                      m_nVerticesPerCH;                   //>! maximum number of vertices per convex-hull\r
 270                 reservable_priority_queue<GraphEdgePriorityQueue, \r
 271             std::vector<GraphEdgePriorityQueue>,\r
 272                         std::greater<std::vector<GraphEdgePriorityQueue>::value_type> > m_pqueue;               //!> priority queue\r
 273                                                                                                         HACD(const HACD & rhs);\r
 274                 CallBackFunction                                                        m_callBack;                                     //>! call-back function\r
 275                 long *                                                                          m_partition;                            //>! array of size m_nTriangles where the i-th element specifies the cluster to which belong the i-th triangle\r
 276         bool                                        m_addFacesPoints;           //>! specifies whether to add faces points or not\r
 277         bool                                        m_addExtraDistPoints;       //>! specifies whether to add extra points for concave shapes or not\r
 278                 bool                                                                            m_addNeighboursDistPoints;  //>! specifies whether to add extra points from adjacent clusters or not\r
 279 \r
 280         };\r
 281 }\r
 282 #endif\r