decimate.cpp 5.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213
  1. // This file is part of libigl, a simple c++ geometry processing library.
  2. //
  3. // Copyright (C) 2016 Alec Jacobson <alecjacobson@gmail.com>
  4. //
  5. // This Source Code Form is subject to the terms of the Mozilla Public License
  6. // v. 2.0. If a copy of the MPL was not distributed with this file, You can
  7. // obtain one at http://mozilla.org/MPL/2.0/.
  8. #include "decimate.h"
  9. #include "collapse_edge.h"
  10. #include "edge_flaps.h"
  11. #include "remove_unreferenced.h"
  12. #include "slice_mask.h"
  13. #include "slice.h"
  14. #include "connect_boundary_to_infinity.h"
  15. #include <iostream>
  16. IGL_INLINE bool igl::decimate(
  17. const Eigen::MatrixXd & V,
  18. const Eigen::MatrixXi & F,
  19. const size_t max_m,
  20. Eigen::MatrixXd & U,
  21. Eigen::MatrixXi & G,
  22. Eigen::VectorXi & J,
  23. Eigen::VectorXi & I)
  24. {
  25. // Original number of faces
  26. const int orig_m = F.rows();
  27. // Tracking number of faces
  28. int m = F.rows();
  29. const auto & shortest_edge_and_midpoint = [](
  30. const int e,
  31. const Eigen::MatrixXd & V,
  32. const Eigen::MatrixXi & /*F*/,
  33. const Eigen::MatrixXi & E,
  34. const Eigen::VectorXi & /*EMAP*/,
  35. const Eigen::MatrixXi & /*EF*/,
  36. const Eigen::MatrixXi & /*EI*/,
  37. double & cost,
  38. Eigen::RowVectorXd & p)
  39. {
  40. cost = (V.row(E(e,0))-V.row(E(e,1))).norm();
  41. p = 0.5*(V.row(E(e,0))+V.row(E(e,1)));
  42. };
  43. typedef Eigen::MatrixXd DerivedV;
  44. typedef Eigen::MatrixXi DerivedF;
  45. DerivedV VO;
  46. DerivedF FO;
  47. igl::connect_boundary_to_infinity(V,F,VO,FO);
  48. const auto & max_non_infinite_faces_stopping_condition =
  49. [max_m,orig_m,&m](
  50. const Eigen::MatrixXd &,
  51. const Eigen::MatrixXi &,
  52. const Eigen::MatrixXi &,
  53. const Eigen::VectorXi &,
  54. const Eigen::MatrixXi &,
  55. const Eigen::MatrixXi &,
  56. const std::set<std::pair<double,int> > &,
  57. const std::vector<std::set<std::pair<double,int> >::iterator > &,
  58. const Eigen::MatrixXd &,
  59. const int,
  60. const int,
  61. const int,
  62. const int f1,
  63. const int f2) -> bool
  64. {
  65. // Only subtract if we're collapsing a real face
  66. if(f1 < orig_m) m-=1;
  67. if(f2 < orig_m) m-=1;
  68. return m<=(int)max_m;
  69. };
  70. bool ret = decimate(
  71. VO,
  72. FO,
  73. shortest_edge_and_midpoint,
  74. max_non_infinite_faces_stopping_condition,
  75. U,
  76. G,
  77. J,
  78. I);
  79. const Eigen::Array<bool,Eigen::Dynamic,1> keep = (J.array()<orig_m);
  80. igl::slice_mask(Eigen::MatrixXi(G),keep,1,G);
  81. igl::slice_mask(Eigen::VectorXi(J),keep,1,J);
  82. Eigen::VectorXi _1,I2;
  83. igl::remove_unreferenced(Eigen::MatrixXd(U),Eigen::MatrixXi(G),U,G,_1,I2);
  84. igl::slice(Eigen::VectorXi(I),I2,1,I);
  85. return ret;
  86. }
  87. IGL_INLINE bool igl::decimate(
  88. const Eigen::MatrixXd & V,
  89. const Eigen::MatrixXi & F,
  90. const size_t max_m,
  91. Eigen::MatrixXd & U,
  92. Eigen::MatrixXi & G,
  93. Eigen::VectorXi & J)
  94. {
  95. Eigen::VectorXi I;
  96. return igl::decimate(V,F,max_m,U,G,J,I);
  97. }
  98. IGL_INLINE bool igl::decimate(
  99. const Eigen::MatrixXd & OV,
  100. const Eigen::MatrixXi & OF,
  101. const std::function<void(
  102. const int,
  103. const Eigen::MatrixXd &,
  104. const Eigen::MatrixXi &,
  105. const Eigen::MatrixXi &,
  106. const Eigen::VectorXi &,
  107. const Eigen::MatrixXi &,
  108. const Eigen::MatrixXi &,
  109. double &,
  110. Eigen::RowVectorXd &)> & cost_and_placement,
  111. const std::function<bool(
  112. const Eigen::MatrixXd &,
  113. const Eigen::MatrixXi &,
  114. const Eigen::MatrixXi &,
  115. const Eigen::VectorXi &,
  116. const Eigen::MatrixXi &,
  117. const Eigen::MatrixXi &,
  118. const std::set<std::pair<double,int> > &,
  119. const std::vector<std::set<std::pair<double,int> >::iterator > &,
  120. const Eigen::MatrixXd &,
  121. const int,
  122. const int,
  123. const int,
  124. const int,
  125. const int)> & stopping_condition,
  126. Eigen::MatrixXd & U,
  127. Eigen::MatrixXi & G,
  128. Eigen::VectorXi & J,
  129. Eigen::VectorXi & I
  130. )
  131. {
  132. using namespace Eigen;
  133. using namespace std;
  134. // Working copies
  135. Eigen::MatrixXd V = OV;
  136. Eigen::MatrixXi F = OF;
  137. VectorXi EMAP;
  138. MatrixXi E,EF,EI;
  139. typedef std::set<std::pair<double,int> > PriorityQueue;
  140. PriorityQueue Q;
  141. std::vector<PriorityQueue::iterator > Qit;
  142. edge_flaps(F,E,EMAP,EF,EI);
  143. Qit.resize(E.rows());
  144. // If an edge were collapsed, we'd collapse it to these points:
  145. MatrixXd C(E.rows(),V.cols());
  146. for(int e = 0;e<E.rows();e++)
  147. {
  148. double cost = e;
  149. RowVectorXd p(1,3);
  150. cost_and_placement(e,V,F,E,EMAP,EF,EI,cost,p);
  151. C.row(e) = p;
  152. Qit[e] = Q.insert(std::pair<double,int>(cost,e)).first;
  153. }
  154. int prev_e = -1;
  155. bool clean_finish = false;
  156. while(true)
  157. {
  158. if(Q.empty())
  159. {
  160. break;
  161. }
  162. if(Q.begin()->first == std::numeric_limits<double>::infinity())
  163. {
  164. // min cost edge is infinite cost
  165. break;
  166. }
  167. int e,e1,e2,f1,f2;
  168. if(collapse_edge(cost_and_placement,V,F,E,EMAP,EF,EI,Q,Qit,C,e,e1,e2,f1,f2))
  169. {
  170. if(stopping_condition(V,F,E,EMAP,EF,EI,Q,Qit,C,e,e1,e2,f1,f2))
  171. {
  172. clean_finish = true;
  173. break;
  174. }
  175. }else
  176. {
  177. if(prev_e == e)
  178. {
  179. assert(false && "Edge collapse no progress... bad stopping condition?");
  180. break;
  181. }
  182. // Edge was not collapsed... must have been invalid. collapse_edge should
  183. // have updated its cost to inf... continue
  184. }
  185. prev_e = e;
  186. }
  187. // remove all IGL_COLLAPSE_EDGE_NULL faces
  188. MatrixXi F2(F.rows(),3);
  189. J.resize(F.rows());
  190. int m = 0;
  191. for(int f = 0;f<F.rows();f++)
  192. {
  193. if(
  194. F(f,0) != IGL_COLLAPSE_EDGE_NULL ||
  195. F(f,1) != IGL_COLLAPSE_EDGE_NULL ||
  196. F(f,2) != IGL_COLLAPSE_EDGE_NULL)
  197. {
  198. F2.row(m) = F.row(f);
  199. J(m) = f;
  200. m++;
  201. }
  202. }
  203. F2.conservativeResize(m,F2.cols());
  204. J.conservativeResize(m);
  205. VectorXi _1;
  206. remove_unreferenced(V,F2,U,G,_1,I);
  207. return clean_finish;
  208. }