1 /*
2 * Software License Agreement (BSD License)
3 *
4 * Copyright (c) 2012-, Open Perception, Inc.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
17 * * Neither the name of the copyright holder(s) nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
33 *
34 *
35 *
36 */
37
38 #include <suitesparse/cholmod.h>
39 #include <suitesparse/umfpack.h>
40 #include <iostream>
41 #include <stdio.h>
42 #include <time.h> // for clock, clock_t
43 #include <stdexcept>
44
45 #include <pcl/surface/on_nurbs/nurbs_solve.h>
46
47 using namespace pcl;
48 using namespace on_nurbs;
49
50 void
assign(unsigned rows,unsigned cols,unsigned dims)51 NurbsSolve::assign (unsigned rows, unsigned cols, unsigned dims)
52 {
53 m_Ksparse.clear ();
54 m_xeig = Eigen::MatrixXd::Zero (cols, dims);
55 m_feig = Eigen::MatrixXd::Zero (rows, dims);
56 }
57
58 void
K(unsigned i,unsigned j,double v)59 NurbsSolve::K (unsigned i, unsigned j, double v)
60 {
61 m_Ksparse.set (i, j, v);
62 }
63 void
x(unsigned i,unsigned j,double v)64 NurbsSolve::x (unsigned i, unsigned j, double v)
65 {
66 m_xeig (i, j) = v;
67 }
68 void
f(unsigned i,unsigned j,double v)69 NurbsSolve::f (unsigned i, unsigned j, double v)
70 {
71 m_feig (i, j) = v;
72 }
73
74 double
K(unsigned i,unsigned j)75 NurbsSolve::K (unsigned i, unsigned j)
76 {
77 return m_Ksparse.get (i, j);
78 }
79 double
x(unsigned i,unsigned j)80 NurbsSolve::x (unsigned i, unsigned j)
81 {
82 return m_xeig (i, j);
83 }
84 double
f(unsigned i,unsigned j)85 NurbsSolve::f (unsigned i, unsigned j)
86 {
87 return m_feig (i, j);
88 }
89
90 void
resize(unsigned rows)91 NurbsSolve::resize (unsigned rows)
92 {
93 m_feig.conservativeResize (rows, m_feig.cols ());
94 }
95
96 void
printK()97 NurbsSolve::printK ()
98 {
99 m_Ksparse.printLong ();
100 }
101
102 void
printX()103 NurbsSolve::printX ()
104 {
105 for (unsigned r = 0; r < m_xeig.rows (); r++)
106 {
107 for (unsigned c = 0; c < m_xeig.cols (); c++)
108 {
109 printf (" %f", m_xeig (r, c));
110 }
111 printf ("\n");
112 }
113 }
114
115 void
printF()116 NurbsSolve::printF ()
117 {
118 for (unsigned r = 0; r < m_feig.rows (); r++)
119 {
120 for (unsigned c = 0; c < m_feig.cols (); c++)
121 {
122 printf (" %f", m_feig (r, c));
123 }
124 printf ("\n");
125 }
126 }
127
128 namespace pcl
129 {
130 namespace on_nurbs
131 {
132 bool
solveSparseLinearSystem(cholmod_sparse * A,cholmod_dense * b,cholmod_dense * x,bool transpose)133 solveSparseLinearSystem (cholmod_sparse* A, cholmod_dense* b, cholmod_dense* x, bool transpose)
134 {
135 double* vals = (double*)A->x;
136 int* cols = (int*)A->p;
137 int* rows = (int*)A->i;
138 double* rhs = (double*)b->x;
139 double* sol = (double*)x->x;
140
141 int noOfVerts = b->nrow;
142 int noOfCols = b->ncol;
143
144 double* tempRhs = new double[noOfVerts];
145 double* tempSol = new double[noOfVerts];
146
147 double* null = (double*)NULL;
148 void *Symbolic, *Numeric;
149
150 if (umfpack_di_symbolic (A->nrow, A->ncol, cols, rows, vals, &Symbolic, null, null) != 0)
151 {
152 std::cout << "[NurbsSolve[UMFPACK]::solveSparseLinearSystem] Warning: something is wrong with input matrix!"
153 << std::endl;
154 delete [] tempRhs;
155 delete [] tempSol;
156 return false;
157
158 }
159
160 if (umfpack_di_numeric (cols, rows, vals, Symbolic, &Numeric, null, null) != 0)
161 {
162 std::cout
163 << "[NurbsSolve[UMFPACK]::solveSparseLinearSystem] Warning: ordering was ok but factorization failed!"
164 << std::endl;
165 delete [] tempRhs;
166 delete [] tempSol;
167 return false;
168 }
169
170 umfpack_di_free_symbolic (&Symbolic);
171
172 for (int i = 0; i < noOfCols; i++)
173 {
174 for (int k = 0; k < noOfVerts; k++)
175 tempRhs[k] = rhs[i * noOfVerts + k];
176
177 // At or A?
178 if (transpose)
179 umfpack_di_solve (UMFPACK_At, cols, rows, vals, tempSol, tempRhs, Numeric, null, null);
180 else
181 umfpack_di_solve (UMFPACK_A, cols, rows, vals, tempSol, tempRhs, Numeric, null, null);
182
183 for (int k = 0; k < noOfVerts; k++)
184 sol[i * noOfVerts + k] = tempSol[k];
185 }
186
187 // clean up
188 umfpack_di_free_numeric (&Numeric);
189 delete [] tempRhs;
190 delete [] tempSol;
191 return true;
192 }
193
194 bool
solveSparseLinearSystemLQ(cholmod_sparse * A,cholmod_dense * b,cholmod_dense * x)195 solveSparseLinearSystemLQ (cholmod_sparse* A, cholmod_dense* b, cholmod_dense* x)
196 {
197 cholmod_common c;
198 cholmod_start (&c);
199 c.print = 4;
200
201 cholmod_sparse* At = cholmod_allocate_sparse (A->ncol, A->nrow, A->ncol * A->nrow, 0, 1, 0, CHOLMOD_REAL, &c);
202 // cholmod_dense* Atb = cholmod_allocate_dense(b->nrow, b->ncol, b->nrow, CHOLMOD_REAL, &c);
203 cholmod_dense* Atb = cholmod_allocate_dense (A->ncol, b->ncol, A->ncol, CHOLMOD_REAL, &c);
204
205 double one[2] = {1, 0};
206 double zero[2] = {0, 0};
207 cholmod_sdmult (A, 1, one, zero, b, Atb, &c);
208
209 unsigned trials (20);
210 unsigned i (0);
211 while (!cholmod_transpose_unsym (A, 1, NULL, NULL, A->ncol, At, &c) && i < trials)
212 {
213 printf (
214 "[NurbsSolveUmfpack::solveSparseLinearSystemLQ] Warning allocated memory to low, trying to increase %dx\n",
215 (i + 2));
216
217 cholmod_free_sparse (&At, &c);
218 cholmod_free_dense (&Atb, &c);
219
220 At = cholmod_allocate_sparse (A->ncol, A->nrow, (i + 2) * A->ncol * A->nrow, 0, 1, 0, CHOLMOD_REAL, &c);
221 Atb = cholmod_allocate_dense (A->ncol, b->ncol, A->ncol, CHOLMOD_REAL, &c);
222
223 double one[2] = {1, 0};
224 double zero[2] = {0, 0};
225 cholmod_sdmult (A, 1, one, zero, b, Atb, &c);
226 i++;
227 }
228
229 if (i == trials)
230 {
231 printf ("[NurbsSolveUmfpack::solveSparseLinearSystemLQ] Not enough memory for system to solve. (%d trials)\n",
232 trials);
233 cholmod_free_sparse (&At, &c);
234 cholmod_free_dense (&Atb, &c);
235 return false;
236 }
237
238 cholmod_sparse* AtA = cholmod_ssmult (At, A, 0, 1, 1, &c);
239
240 // cholmod_print_sparse(AtA,"A: ", &c);
241
242 bool success = solveSparseLinearSystem (AtA, Atb, x, false);
243
244 cholmod_free_sparse (&At, &c);
245 cholmod_free_sparse (&AtA, &c);
246 cholmod_free_dense (&Atb, &c);
247
248 cholmod_finish (&c);
249
250 return success;
251 }
252 }
253 }
254
255 bool
solve()256 NurbsSolve::solve ()
257 {
258 clock_t time_start, time_end;
259 time_start = clock ();
260
261 cholmod_common c;
262 cholmod_start (&c);
263
264 int n_rows, n_cols, n_dims, n_nz;
265 m_Ksparse.size (n_rows, n_cols);
266 n_nz = m_Ksparse.nonzeros ();
267 n_dims = m_feig.cols ();
268
269 // m_Ksparse.printLong();
270
271 cholmod_sparse* K = cholmod_allocate_sparse (n_rows, n_cols, n_rows * n_cols, 0, 1, 0, CHOLMOD_REAL, &c);
272 cholmod_dense* f = cholmod_allocate_dense (n_rows, n_dims, n_rows, CHOLMOD_REAL, &c);
273 cholmod_dense* d = cholmod_allocate_dense (n_cols, n_dims, n_cols, CHOLMOD_REAL, &c);
274
275 std::vector<int> rowinds;
276 std::vector<int> colinds;
277 std::vector<double> values;
278 m_Ksparse.get (rowinds, colinds, values);
279
280 double* vals = (double*)K->x;
281 int* cols = (int*)K->p;
282 int* rows = (int*)K->i;
283
284 umfpack_di_triplet_to_col (n_rows, n_cols, n_nz, &rowinds[0], &colinds[0], &values[0], cols, rows, vals, NULL);
285
286 double* temp = (double*)f->x;
287
288 for (int j = 0; j < n_dims; j++)
289 {
290 for (int i = 0; i < n_rows; i++)
291 {
292
293 temp[j * n_rows + i] = m_feig (i, j);
294
295 }
296 }
297
298 bool success = solveSparseLinearSystemLQ (K, f, d);
299
300 temp = (double*)d->x;
301
302 for (int j = 0; j < n_dims; j++)
303 {
304 for (int i = 0; i < n_cols; i++)
305 {
306
307 m_xeig (i, j) = temp[j * n_cols + i];
308
309 }
310 }
311
312 cholmod_free_sparse (&K, &c);
313 cholmod_free_dense (&f, &c);
314 cholmod_free_dense (&d, &c);
315
316 cholmod_finish (&c);
317
318 time_end = clock ();
319
320 if (success)
321 {
322 if (!m_quiet)
323 {
324 double solve_time = (double)(time_end - time_start) / (double)(CLOCKS_PER_SEC);
325 printf ("[NurbsSolve[UMFPACK]::solve()] solution found! (%f sec)\n", solve_time);
326 }
327 }
328 else
329 {
330 printf ("[NurbsSolve[UMFPACK]::solve()] Error: solution NOT found\n");
331 }
332
333 return success;
334 }
335
336 Eigen::MatrixXd
diff()337 NurbsSolve::diff ()
338 {
339
340 int n_rows, n_cols, n_dims;
341 m_Ksparse.size (n_rows, n_cols);
342 n_dims = m_feig.cols ();
343
344 if (n_rows != m_feig.rows ())
345 {
346 printf ("[NurbsSolve::diff] K.rows: %d f.rows: %d\n", n_rows, (int)m_feig.rows ());
347 throw std::runtime_error ("[NurbsSolve::diff] Rows of equation do not match\n");
348 }
349
350 Eigen::MatrixXd f = Eigen::MatrixXd::Zero (n_rows, n_dims);
351
352 for (int r = 0; r < n_rows; r++)
353 {
354 for (int c = 0; c < n_cols; c++)
355 {
356 f.row (r) = f.row (r) + m_xeig.row (c) * m_Ksparse.get (r, c);
357 }
358 }
359
360 return (f - m_feig);
361 }
362
363