peal_outer_hull_layers.cpp 2.4 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
  1. #include "peal_outer_hull_layers.h"
  2. #include "outer_hull.h"
  3. #include <vector>
  4. template <
  5. typename DerivedV,
  6. typename DerivedF,
  7. typename Derivedodd,
  8. typename Derivedflip>
  9. IGL_INLINE void igl::peal_outer_hull_layers(
  10. const Eigen::PlainObjectBase<DerivedV > & V,
  11. const Eigen::PlainObjectBase<DerivedF > & F,
  12. Eigen::PlainObjectBase<Derivedodd > & odd,
  13. Eigen::PlainObjectBase<Derivedflip > & flip)
  14. {
  15. using namespace Eigen;
  16. using namespace std;
  17. typedef typename DerivedF::Index Index;
  18. typedef Matrix<typename DerivedF::Scalar,Dynamic,DerivedF::ColsAtCompileTime> MatrixXF;
  19. typedef Matrix<Index,Dynamic,1> MatrixXI;
  20. typedef Matrix<typename Derivedflip::Scalar,Dynamic,Derivedflip::ColsAtCompileTime> MatrixXflip;
  21. const Index m = F.rows();
  22. // keep track of iteration parity and whether flipped in hull
  23. MatrixXF Fr = F;
  24. odd.resize(m,1);
  25. flip.resize(m,1);
  26. // Keep track of index map
  27. MatrixXI IM = MatrixXI::LinSpaced(m,0,m-1);
  28. // This is O(n * layers)
  29. bool odd_iter = true;
  30. MatrixXI P(m,1);
  31. Index iter = 0;
  32. while(Fr.size() > 0)
  33. {
  34. assert(Fr.rows() == IM.rows());
  35. // Compute outer hull of current Fr
  36. MatrixXF Fo;
  37. MatrixXI Jo;
  38. MatrixXflip flipr;
  39. outer_hull(V,Fr,Fo,Jo,flipr);
  40. assert(Fo.rows() == Jo.rows());
  41. // all faces in Fo of Fr
  42. vector<bool> in_outer(Fr.rows(),false);
  43. for(Index g = 0;g<Jo.rows();g++)
  44. {
  45. odd(IM(Jo(g))) = odd_iter;
  46. P(IM(Jo(g))) = iter;
  47. in_outer[Jo(g)] = true;
  48. flip(IM(Jo(g))) = flipr(Jo(g));
  49. }
  50. // Fr = Fr - Fo
  51. // update IM
  52. MatrixXF prev_Fr = Fr;
  53. MatrixXI prev_IM = IM;
  54. Fr.resize(prev_Fr.rows() - Fo.rows(),F.cols());
  55. IM.resize(Fr.rows());
  56. {
  57. Index g = 0;
  58. for(Index f = 0;f<prev_Fr.rows();f++)
  59. {
  60. if(!in_outer[f])
  61. {
  62. Fr.row(g) = prev_Fr.row(f);
  63. IM(g) = prev_IM(f);
  64. g++;
  65. }
  66. }
  67. }
  68. odd_iter = !odd_iter;
  69. iter++;
  70. }
  71. }
  72. #ifdef IGL_STATIC_LIBRARY
  73. // Explicit template specialization
  74. template void igl::peal_outer_hull_layers<Eigen::Matrix<double, -1, 3, 0, -1, 3>, Eigen::Matrix<int, -1, 3, 0, -1, 3>, Eigen::Matrix<bool, -1, 1, 0, -1, 1>, Eigen::Matrix<bool, -1, 1, 0, -1, 1> >(Eigen::PlainObjectBase<Eigen::Matrix<double, -1, 3, 0, -1, 3> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 3, 0, -1, 3> > const&, Eigen::PlainObjectBase<Eigen::Matrix<bool, -1, 1, 0, -1, 1> >&, Eigen::PlainObjectBase<Eigen::Matrix<bool, -1, 1, 0, -1, 1> >&);
  75. #endif