1 // This file is part of libigl, a simple c++ geometry processing library. 2 // 3 // Copyright (C) 2017 Amir Vaxman <avaxman@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 #ifndef IGL_SHAPEUP_H 9 #define IGL_SHAPEUP_H 10 11 #include <igl/min_quad_with_fixed.h> 12 #include <igl/igl_inline.h> 13 #include <igl/setdiff.h> 14 #include <igl/cat.h> 15 #include <Eigen/Core> 16 #include <vector> 17 #include <igl/PI.h> 18 19 20 //This file implements the following algorithm: 21 22 //Boaziz et al. 23 //Shape-Up: Shaping Discrete Geometry with Projections 24 //Computer Graphics Forum (Proc. SGP) 31(5), 2012 25 26 namespace igl 27 { 28 struct ShapeupData{ 29 //input data 30 Eigen::MatrixXd P; 31 Eigen::VectorXi SC; 32 Eigen::MatrixXi S; 33 Eigen::VectorXi b; 34 int maxIterations; //referring to number of local-global pairs. 35 double pTolerance; //algorithm stops when max(|P_k-P_{k-1}|)<pTolerance. 36 double shapeCoeff, closeCoeff, smoothCoeff; 37 38 //Internally-used matrices 39 Eigen::SparseMatrix<double> DShape, DClose, DSmooth, Q, A, At, W; 40 41 min_quad_with_fixed_data<double> solver_data; 42 ShapeupDataShapeupData43 ShapeupData(): 44 maxIterations(50), 45 pTolerance(10e-6), 46 shapeCoeff(1.0), 47 closeCoeff(100.0), 48 smoothCoeff(0.0){} 49 }; 50 51 //Every function here defines a local projection for ShapeUp, and must have the following structure to qualify: 52 //Input: 53 // P #P by 3 the set of points, either the initial solution, or from previous iteration. 54 // SC #Set by 1 cardinalities of sets in S 55 // S #Sets by max(SC) independent sets where the local projection applies. Values beyond column SC(i)-1 in row S(i,:) are "don't care" 56 //Output: 57 // projP #S by 3*max(SC) in format xyzxyzxyz, where the projected points correspond to each set in S in the same order. 58 typedef std::function<bool(const Eigen::PlainObjectBase<Eigen::MatrixXd>&, const Eigen::PlainObjectBase<Eigen::VectorXi>&, const Eigen::PlainObjectBase<Eigen::MatrixXi>&, Eigen::PlainObjectBase<Eigen::MatrixXd>&)> shapeup_projection_function; 59 60 61 //This projection does nothing but render points into projP. Mostly used for "echoing" the global step 62 IGL_INLINE bool shapeup_identity_projection(const Eigen::PlainObjectBase<Eigen::MatrixXd>& P, const Eigen::PlainObjectBase<Eigen::VectorXi>& SC, const Eigen::PlainObjectBase<Eigen::MatrixXi>& S, Eigen::PlainObjectBase<Eigen::MatrixXd>& projP); 63 64 //the projection assumes that the sets are vertices of polygons in cyclic order 65 IGL_INLINE bool shapeup_regular_face_projection(const Eigen::PlainObjectBase<Eigen::MatrixXd>& P, const Eigen::PlainObjectBase<Eigen::VectorXi>& SC, const Eigen::PlainObjectBase<Eigen::MatrixXi>& S, Eigen::PlainObjectBase<Eigen::MatrixXd>& projP); 66 67 68 //This function precomputation the necessary matrices for the ShapeUp process, and prefactorizes them. 69 70 //input: 71 // P #P by 3 point positions 72 // SC #Set by 1 cardinalities of sets in S 73 // S #Sets by max(SC) independent sets where the local projection applies. Values beyond column SC(i)-1 in row S(i,:) are "don't care" 74 // E #E by 2 the "edges" of the set P; used for the smoothness energy. 75 // b #b by 1 boundary (fixed) vertices from P. 76 // wShape, #Set by 1 77 // wSmooth #b by 1 weights for constraints from S and positional constraints (used in the global step) 78 79 // Output: 80 // sudata struct ShapeupData the data necessary to solve the system in shapeup_solve 81 82 template < 83 typename DerivedP, 84 typename DerivedSC, 85 typename DerivedS, 86 typename Derivedw> 87 IGL_INLINE bool shapeup_precomputation(const Eigen::PlainObjectBase<DerivedP>& P, 88 const Eigen::PlainObjectBase<DerivedSC>& SC, 89 const Eigen::PlainObjectBase<DerivedS>& S, 90 const Eigen::PlainObjectBase<DerivedS>& E, 91 const Eigen::PlainObjectBase<DerivedSC>& b, 92 const Eigen::PlainObjectBase<Derivedw>& wShape, 93 const Eigen::PlainObjectBase<Derivedw>& wSmooth, 94 ShapeupData & sudata); 95 96 97 98 //This function solve the shapeup project optimization. shapeup_precompute must be called before with the same sudata, or results are unpredictable 99 100 //Input: 101 //bc #b by 3 fixed point values corresonding to "b" in sudata 102 //local_projection function pointer taking (P,SC,S,projP), 103 // where the first three parameters are as defined, and "projP" is the output, as a #S by 3*max(SC) function in format xyzxyzxyz, and where it returns the projected points corresponding to each set in S in the same order. 104 //NOTE: the input values in P0 don't need to correspond to prescribed values in bc; the iterations will project them automatically (by design). 105 //P0 #P by 3 initial solution (point positions) 106 //sudata the ShapeUpData structure computed in shapeup_precomputation() 107 //quietIterations flagging if to output iteration information. 108 109 //Output: 110 //P the solution to the problem, indices corresponding to P0. 111 template < 112 typename DerivedP, 113 typename DerivedSC, 114 typename DerivedS> 115 IGL_INLINE bool shapeup_solve(const Eigen::PlainObjectBase<DerivedP>& bc, 116 const std::function<bool(const Eigen::PlainObjectBase<DerivedP>&, const Eigen::PlainObjectBase<DerivedSC>&, const Eigen::PlainObjectBase<DerivedS>&, Eigen::PlainObjectBase<DerivedP>&)>& local_projection, 117 const Eigen::PlainObjectBase<DerivedP>& P0, 118 const ShapeupData & sudata, 119 const bool quietIterations, 120 Eigen::PlainObjectBase<DerivedP>& P); 121 122 } 123 124 #ifndef IGL_STATIC_LIBRARY 125 #include "shapeup.cpp" 126 #endif 127 128 #endif 129