863c715a99b56d16b37b24800f5b755a665a9156
[blender.git] / source / blender / blenkernel / intern / implicit_eigen.cpp
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) Blender Foundation
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Lukas Toenne
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/implicit_eigen.cpp
29  *  \ingroup bke
30  */
31
32 #include "implicit.h"
33
34 #ifdef IMPLICIT_SOLVER_EIGEN
35
36 //#define USE_EIGEN_CORE
37 #define USE_EIGEN_CONSTRAINED_CG
38
39 #ifndef IMPLICIT_ENABLE_EIGEN_DEBUG
40 #ifdef NDEBUG
41 #define IMPLICIT_NDEBUG
42 #endif
43 #define NDEBUG
44 #endif
45
46 #include <Eigen/Sparse>
47 #include <Eigen/src/Core/util/DisableStupidWarnings.h>
48
49 #ifdef USE_EIGEN_CONSTRAINED_CG
50 #include <intern/ConstrainedConjugateGradient.h>
51 #endif
52
53 #ifndef IMPLICIT_ENABLE_EIGEN_DEBUG
54 #ifndef IMPLICIT_NDEBUG
55 #undef NDEBUG
56 #else
57 #undef IMPLICIT_NDEBUG
58 #endif
59 #endif
60
61 #include "MEM_guardedalloc.h"
62
63 extern "C" {
64 #include "DNA_scene_types.h"
65 #include "DNA_object_types.h"
66 #include "DNA_object_force.h"
67 #include "DNA_meshdata_types.h"
68 #include "DNA_texture_types.h"
69
70 #include "BLI_math.h"
71 #include "BLI_linklist.h"
72 #include "BLI_utildefines.h"
73
74 #include "BKE_cloth.h"
75 #include "BKE_collision.h"
76 #include "BKE_effect.h"
77 #include "BKE_global.h"
78 }
79
80 /* ==== hash functions for debugging ==== */
81 static unsigned int hash_int_2d(unsigned int kx, unsigned int ky)
82 {
83 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
84
85         unsigned int a, b, c;
86
87         a = b = c = 0xdeadbeef + (2 << 2) + 13;
88         a += kx;
89         b += ky;
90
91         c ^= b; c -= rot(b,14);
92         a ^= c; a -= rot(c,11);
93         b ^= a; b -= rot(a,25);
94         c ^= b; c -= rot(b,16);
95         a ^= c; a -= rot(c,4);
96         b ^= a; b -= rot(a,14);
97         c ^= b; c -= rot(b,24);
98
99         return c;
100
101 #undef rot
102 }
103
104 static int hash_vertex(int type, int vertex)
105 {
106         return hash_int_2d((unsigned int)type, (unsigned int)vertex);
107 }
108
109 static int hash_collpair(int type, CollPair *collpair)
110 {
111         return hash_int_2d((unsigned int)type, hash_int_2d((unsigned int)collpair->face1, (unsigned int)collpair->face2));
112 }
113 /* ================ */
114
115
116 typedef float Scalar;
117
118 typedef Eigen::SparseMatrix<Scalar> lMatrix;
119
120 typedef Eigen::VectorXf lVector;
121
122 typedef Eigen::Triplet<Scalar> Triplet;
123 typedef std::vector<Triplet> TripletList;
124
125 #ifdef USE_EIGEN_CORE
126 typedef Eigen::ConjugateGradient<lMatrix, Eigen::Lower, Eigen::DiagonalPreconditioner<Scalar> > ConjugateGradient;
127 #endif
128 #ifdef USE_EIGEN_CONSTRAINED_CG
129 typedef Eigen::ConstrainedConjugateGradient<lMatrix, Eigen::Lower, lMatrix,
130                                             Eigen::DiagonalPreconditioner<Scalar> >
131         ConstraintConjGrad;
132 #endif
133 using Eigen::ComputationInfo;
134
135 static void print_lvector(const lVector &v)
136 {
137         for (int i = 0; i < v.rows(); ++i) {
138                 if (i > 0 && i % 3 == 0)
139                         printf("\n");
140                 
141                 printf("%f,\n", v[i]);
142         }
143 }
144
145 static void print_lmatrix(const lMatrix &m)
146 {
147         for (int j = 0; j < m.rows(); ++j) {
148                 if (j > 0 && j % 3 == 0)
149                         printf("\n");
150                 
151                 for (int i = 0; i < m.cols(); ++i) {
152                         if (i > 0 && i % 3 == 0)
153                                 printf("  ");
154                         
155                         implicit_print_matrix_elem(m.coeff(j, i));
156                 }
157                 printf("\n");
158         }
159 }
160
161 static float I[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
162 static float ZERO[3][3] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
163
164 BLI_INLINE void lMatrix_reserve_elems(lMatrix &m, int num)
165 {
166         m.reserve(Eigen::VectorXi::Constant(m.cols(), num));
167 }
168
169 BLI_INLINE float *lVector_v3(lVector &v, int vertex)
170 {
171         return v.data() + 3 * vertex;
172 }
173
174 BLI_INLINE const float *lVector_v3(const lVector &v, int vertex)
175 {
176         return v.data() + 3 * vertex;
177 }
178
179 BLI_INLINE void triplets_m3(TripletList &tlist, float m[3][3], int i, int j)
180 {
181         i *= 3;
182         j *= 3;
183         for (int l = 0; l < 3; ++l) {
184                 for (int k = 0; k < 3; ++k) {
185                         tlist.push_back(Triplet(i + k, j + l, m[k][l]));
186                 }
187         }
188 }
189
190 BLI_INLINE void triplets_m3fl(TripletList &tlist, float m[3][3], int i, int j, float factor)
191 {
192         i *= 3;
193         j *= 3;
194         for (int l = 0; l < 3; ++l) {
195                 for (int k = 0; k < 3; ++k) {
196                         tlist.push_back(Triplet(i + k, j + l, m[k][l] * factor));
197                 }
198         }
199 }
200
201 BLI_INLINE void lMatrix_add_triplets(lMatrix &r, const TripletList &tlist)
202 {
203         lMatrix t(r.rows(), r.cols());
204         t.setFromTriplets(tlist.begin(), tlist.end());
205         r += t;
206 }
207
208 BLI_INLINE void lMatrix_madd_triplets(lMatrix &r, const TripletList &tlist, float f)
209 {
210         lMatrix t(r.rows(), r.cols());
211         t.setFromTriplets(tlist.begin(), tlist.end());
212         r += f * t;
213 }
214
215 BLI_INLINE void lMatrix_sub_triplets(lMatrix &r, const TripletList &tlist)
216 {
217         lMatrix t(r.rows(), r.cols());
218         t.setFromTriplets(tlist.begin(), tlist.end());
219         r -= t;
220 }
221
222 #if 0
223 BLI_INLINE void lMatrix_copy_m3(lMatrix &r, float m[3][3], int i, int j)
224 {
225         i *= 3;
226         j *= 3;
227         for (int l = 0; l < 3; ++l) {
228                 for (int k = 0; k < 3; ++k) {
229                         r.coeffRef(i + k, j + l) = m[k][l];
230                 }
231         }
232 }
233
234 BLI_INLINE void lMatrix_add_m3(lMatrix &r, float m[3][3], int i, int j)
235 {
236         lMatrix tmp(r.cols(), r.cols());
237         lMatrix_copy_m3(tmp, m, i, j);
238         r += tmp;
239 }
240
241 BLI_INLINE void lMatrix_sub_m3(lMatrix &r, float m[3][3], int i, int j)
242 {
243         lMatrix tmp(r.cols(), r.cols());
244         lMatrix_copy_m3(tmp, m, i, j);
245         r -= tmp;
246 }
247
248 BLI_INLINE void lMatrix_madd_m3(lMatrix &r, float m[3][3], float s, int i, int j)
249 {
250         lMatrix tmp(r.cols(), r.cols());
251         lMatrix_copy_m3(tmp, m, i, j);
252         r += s * tmp;
253 }
254 #endif
255
256 BLI_INLINE void outerproduct(float r[3][3], const float a[3], const float b[3])
257 {
258         mul_v3_v3fl(r[0], a, b[0]);
259         mul_v3_v3fl(r[1], a, b[1]);
260         mul_v3_v3fl(r[2], a, b[2]);
261 }
262
263 struct RootTransform {
264         float loc[3];
265         float rot[3][3];
266         
267         float vel[3];
268         float omega[3];
269         
270         float acc[3];
271         float domega_dt[3];
272 };
273
274 struct Implicit_Data {
275         typedef std::vector<RootTransform> RootTransforms;
276         
277         Implicit_Data(int numverts)
278         {
279                 resize(numverts);
280         }
281         
282         void resize(int numverts)
283         {
284                 this->numverts = numverts;
285                 int tot = 3 * numverts;
286                 
287                 M.resize(tot, tot);
288                 dFdV.resize(tot, tot);
289                 dFdX.resize(tot, tot);
290                 
291                 root.resize(numverts);
292                 
293                 X.resize(tot);
294                 Xnew.resize(tot);
295                 V.resize(tot);
296                 Vnew.resize(tot);
297                 F.resize(tot);
298                 
299                 B.resize(tot);
300                 A.resize(tot, tot);
301                 
302                 dV.resize(tot);
303                 z.resize(tot);
304                 S.resize(tot, tot);
305         }
306         
307         int numverts;
308         
309         /* inputs */
310         lMatrix M;                                      /* masses */
311         lVector F;                                      /* forces */
312         lMatrix dFdV, dFdX;                     /* force jacobians */
313         
314         RootTransforms root;            /* root transforms */
315         
316         /* motion state data */
317         lVector X, Xnew;                        /* positions */
318         lVector V, Vnew;                        /* velocities */
319         
320         /* internal solver data */
321         lVector B;                                      /* B for A*dV = B */
322         lMatrix A;                                      /* A for A*dV = B */
323         
324         lVector dV;                                     /* velocity change (solution of A*dV = B) */
325         lVector z;                                      /* target velocity in constrained directions */
326         lMatrix S;                                      /* filtering matrix for constraints */
327 };
328
329 /* ==== Transformation of Moving Reference Frame ====
330  *   x_world, v_world, f_world, a_world, dfdx_world, dfdv_world : state variables in world space
331  *   x_root, v_root, f_root, a_root, dfdx_root, dfdv_root       : state variables in root space
332  *   
333  *   x0 : translation of the root frame (hair root location)
334  *   v0 : linear velocity of the root frame
335  *   a0 : acceleration of the root frame
336  *   R : rotation matrix of the root frame
337  *   w : angular velocity of the root frame
338  *   dwdt : angular acceleration of the root frame
339  */
340
341 /* x_root = R^T * x_world */
342 BLI_INLINE void loc_world_to_root(float r[3], const float v[3], const RootTransform &root)
343 {
344         sub_v3_v3v3(r, v, root.loc);
345         mul_transposed_m3_v3((float (*)[3])root.rot, r);
346 }
347
348 /* x_world = R * x_root */
349 BLI_INLINE void loc_root_to_world(float r[3], const float v[3], const RootTransform &root)
350 {
351         copy_v3_v3(r, v);
352         mul_m3_v3((float (*)[3])root.rot, r);
353         add_v3_v3(r, root.loc);
354 }
355
356 /* v_root = cross(w, x_root) + R^T*(v_world - v0) */
357 BLI_INLINE void vel_world_to_root(float r[3], const float x_root[3], const float v[3], const RootTransform &root)
358 {
359         float angvel[3];
360         cross_v3_v3v3(angvel, root.omega, x_root);
361         
362         sub_v3_v3v3(r, v, root.vel);
363         mul_transposed_m3_v3((float (*)[3])root.rot, r);
364         add_v3_v3(r, angvel);
365 }
366
367 /* v_world = R*(v_root - cross(w, x_root)) + v0 */
368 BLI_INLINE void vel_root_to_world(float r[3], const float x_root[3], const float v[3], const RootTransform &root)
369 {
370         float angvel[3];
371         cross_v3_v3v3(angvel, root.omega, x_root);
372         
373         sub_v3_v3v3(r, v, angvel);
374         mul_m3_v3((float (*)[3])root.rot, r);
375         add_v3_v3(r, root.vel);
376 }
377
378 /* a_root = -cross(dwdt, x_root) - 2*cross(w, v_root) - cross(w, cross(w, x_root)) + R^T*(a_world - a0) */
379 BLI_INLINE void force_world_to_root(float r[3], const float x_root[3], const float v_root[3], const float force[3], float mass, const RootTransform &root)
380 {
381         float euler[3], coriolis[3], centrifugal[3], rotvel[3];
382         
383         cross_v3_v3v3(euler, root.domega_dt, x_root);
384         cross_v3_v3v3(coriolis, root.omega, v_root);
385         mul_v3_fl(coriolis, 2.0f);
386         cross_v3_v3v3(rotvel, root.omega, x_root);
387         cross_v3_v3v3(centrifugal, root.omega, rotvel);
388         
389         madd_v3_v3v3fl(r, force, root.acc, mass);
390         mul_transposed_m3_v3((float (*)[3])root.rot, r);
391         madd_v3_v3fl(r, euler, mass);
392         madd_v3_v3fl(r, coriolis, mass);
393         madd_v3_v3fl(r, centrifugal, mass);
394 }
395
396 /* a_world = R*[ a_root + cross(dwdt, x_root) + 2*cross(w, v_root) + cross(w, cross(w, x_root)) ] + a0 */
397 BLI_INLINE void force_root_to_world(float r[3], const float x_root[3], const float v_root[3], const float force[3], float mass, const RootTransform &root)
398 {
399         float euler[3], coriolis[3], centrifugal[3], rotvel[3];
400         
401         cross_v3_v3v3(euler, root.domega_dt, x_root);
402         cross_v3_v3v3(coriolis, root.omega, v_root);
403         mul_v3_fl(coriolis, 2.0f);
404         cross_v3_v3v3(rotvel, root.omega, x_root);
405         cross_v3_v3v3(centrifugal, root.omega, rotvel);
406         
407         madd_v3_v3v3fl(r, force, euler, mass);
408         madd_v3_v3fl(r, coriolis, mass);
409         madd_v3_v3fl(r, centrifugal, mass);
410         mul_m3_v3((float (*)[3])root.rot, r);
411         madd_v3_v3fl(r, root.acc, mass);
412 }
413
414 BLI_INLINE void acc_world_to_root(float r[3], const float x_root[3], const float v_root[3], const float acc[3], const RootTransform &root)
415 {
416         force_world_to_root(r, x_root, v_root, acc, 1.0f, root);
417 }
418
419 BLI_INLINE void acc_root_to_world(float r[3], const float x_root[3], const float v_root[3], const float acc[3], const RootTransform &root)
420 {
421         force_root_to_world(r, x_root, v_root, acc, 1.0f, root);
422 }
423
424 BLI_INLINE void cross_m3_v3m3(float r[3][3], const float v[3], float m[3][3])
425 {
426         cross_v3_v3v3(r[0], v, m[0]);
427         cross_v3_v3v3(r[1], v, m[1]);
428         cross_v3_v3v3(r[2], v, m[2]);
429 }
430
431 BLI_INLINE void cross_v3_identity(float r[3][3], const float v[3])
432 {
433         r[0][0] = 0.0f;         r[1][0] = v[2];         r[2][0] = -v[1];
434         r[0][1] = -v[2];        r[1][1] = 0.0f;         r[2][1] = v[0];
435         r[0][2] = v[1];         r[1][2] = -v[0];        r[2][2] = 0.0f;
436 }
437
438 /* dfdx_root = m*[ -cross(dwdt, I) - cross(w, cross(w, I)) ] + R^T*(dfdx_world) */
439 BLI_INLINE void dfdx_world_to_root(float m[3][3], float dfdx[3][3], float mass, const RootTransform &root)
440 {
441         float t[3][3], u[3][3];
442         
443         copy_m3_m3(t, (float (*)[3])root.rot);
444         transpose_m3(t);
445         mul_m3_m3m3(m, t, dfdx);
446         
447         cross_v3_identity(t, root.domega_dt);
448         mul_m3_fl(t, mass);
449         sub_m3_m3m3(m, m, t);
450         
451         cross_v3_identity(u, root.omega);
452         cross_m3_v3m3(t, root.omega, u);
453         mul_m3_fl(t, mass);
454         sub_m3_m3m3(m, m, t);
455 }
456
457 /* dfdx_world = R*(dfdx_root + m*[ cross(dwdt, I) + cross(w, cross(w, I)) ]) */
458 BLI_INLINE void dfdx_root_to_world(float m[3][3], float dfdx[3][3], float mass, const RootTransform &root)
459 {
460         float t[3][3];
461         
462         cross_v3_identity(t, root.domega_dt);
463         mul_m3_fl(t, mass);
464         add_m3_m3m3(m, dfdx, t);
465         
466         cross_v3_identity(u, root.omega);
467         cross_m3_v3m3(t, root.omega, u);
468         mul_m3_fl(t, mass);
469         add_m3_m3m3(m, m, t);
470         
471         mul_m3_m3m3(m, (float (*)[3])root.rot, m);
472 }
473
474 /* dfdv_root = -2*m*cross(w, I) + R^T*(dfdv_world) */
475 BLI_INLINE void dfdv_world_to_root(float m[3][3], float dfdv[3][3], float mass, const RootTransform &root)
476 {
477         float t[3][3];
478         
479         copy_m3_m3(t, (float (*)[3])root.rot);
480         transpose_m3(t);
481         mul_m3_m3m3(m, t, dfdv);
482         
483         cross_v3_identity(t, root.omega);
484         mul_m3_fl(t, 2.0f*mass);
485         sub_m3_m3m3(m, m, t);
486 }
487
488 /* dfdv_world = R*(dfdv_root + 2*m*cross(w, I)) */
489 BLI_INLINE void dfdv_root_to_world(float m[3][3], float dfdv[3][3], float mass, const RootTransform &root)
490 {
491         float t[3][3];
492         
493         cross_v3_identity(t, root.omega);
494         mul_m3_fl(t, 2.0f*mass);
495         add_m3_m3m3(m, dfdv, t);
496         
497         mul_m3_m3m3(m, (float (*)[3])root.rot, m);
498 }
499
500 /* ================================ */
501
502 static bool simulate_implicit_euler(Implicit_Data *id, float dt)
503 {
504 #ifdef USE_EIGEN_CORE
505         ConjugateGradient cg;
506         cg.setMaxIterations(100);
507         cg.setTolerance(0.01f);
508         
509         id->A = id->M - dt * id->dFdV - dt*dt * id->dFdX;
510         cg.compute(id->A);
511         
512         id->B = dt * id->F + dt*dt * id->dFdX * id->V;
513         id->dV = cg.solve(id->B);
514         
515         id->Vnew = id->V + id->dV;
516         
517         return cg.info() != Eigen::Success;
518 #endif
519
520 #ifdef USE_EIGEN_CONSTRAINED_CG
521         ConstraintConjGrad cg;
522         cg.setMaxIterations(100);
523         cg.setTolerance(0.01f);
524         
525         id->A = id->M - dt * id->dFdV - dt*dt * id->dFdX;
526         cg.compute(id->A);
527         cg.filter() = id->S;
528         
529         id->B = dt * id->F + dt*dt * id->dFdX * id->V;
530 #ifdef IMPLICIT_PRINT_SOLVER_INPUT_OUTPUT
531         printf("==== A ====\n");
532         print_lmatrix(id->A);
533         printf("==== z ====\n");
534         print_lvector(id->z);
535         printf("==== B ====\n");
536         print_lvector(id->B);
537         printf("==== S ====\n");
538         print_lmatrix(id->S);
539 #endif
540         id->dV = cg.solveWithGuess(id->B, id->z);
541 #ifdef IMPLICIT_PRINT_SOLVER_INPUT_OUTPUT
542         printf("==== dV ====\n");
543         print_lvector(id->dV);
544         printf("========\n");
545 #endif
546         
547         id->Vnew = id->V + id->dV;
548         
549         return cg.info() != Eigen::Success;
550 #endif
551 }
552
553 BLI_INLINE void dfdx_spring(float to[3][3], const float dir[3], float length, float L, float k)
554 {
555         // dir is unit length direction, rest is spring's restlength, k is spring constant.
556         //return  ( (I-outerprod(dir, dir))*Min(1.0f, rest/length) - I) * -k;
557         outerproduct(to, dir, dir);
558         sub_m3_m3m3(to, I, to);
559         
560         mul_m3_fl(to, (L/length)); 
561         sub_m3_m3m3(to, to, I);
562         mul_m3_fl(to, k);
563 }
564
565 /* unused */
566 #if 0
567 BLI_INLINE void dfdx_damp(float to[3][3], const float dir[3], float length, const float vel[3], float rest, float damping)
568 {
569         // inner spring damping   vel is the relative velocity  of the endpoints.  
570         //      return (I-outerprod(dir, dir)) * (-damping * -(dot(dir, vel)/Max(length, rest)));
571         mul_fvectorT_fvector(to, dir, dir);
572         sub_fmatrix_fmatrix(to, I, to);
573         mul_fmatrix_S(to,  (-damping * -(dot_v3v3(dir, vel)/MAX2(length, rest))));
574 }
575 #endif
576
577 BLI_INLINE void dfdv_damp(float to[3][3], const float dir[3], float damping)
578 {
579         // derivative of force wrt velocity
580         outerproduct(to, dir, dir);
581         mul_m3_fl(to, -damping);
582 }
583
584 BLI_INLINE float fb(float length, float L)
585 {
586         float x = length / L;
587         return (-11.541f * powf(x, 4) + 34.193f * powf(x, 3) - 39.083f * powf(x, 2) + 23.116f * x - 9.713f);
588 }
589
590 BLI_INLINE float fbderiv(float length, float L)
591 {
592         float x = length/L;
593
594         return (-46.164f * powf(x, 3) + 102.579f * powf(x, 2) - 78.166f * x + 23.116f);
595 }
596
597 BLI_INLINE float fbstar(float length, float L, float kb, float cb)
598 {
599         float tempfb_fl = kb * fb(length, L);
600         float fbstar_fl = cb * (length - L);
601         
602         if (tempfb_fl < fbstar_fl)
603                 return fbstar_fl;
604         else
605                 return tempfb_fl;
606 }
607
608 // function to calculae bending spring force (taken from Choi & Co)
609 BLI_INLINE float fbstar_jacobi(float length, float L, float kb, float cb)
610 {
611         float tempfb_fl = kb * fb(length, L);
612         float fbstar_fl = cb * (length - L);
613
614         if (tempfb_fl < fbstar_fl) {
615                 return cb;
616         }
617         else {
618                 return kb * fbderiv(length, L);
619         }
620 }
621
622 static void cloth_calc_spring_force(ClothModifierData *clmd, ClothSpring *s, const lVector &X, const lVector &V, float time)
623 {
624         Cloth *cloth = clmd->clothObject;
625         ClothVertex *verts = cloth->verts;
626         ClothVertex *v1 = &verts[s->ij]/*, *v2 = &verts[s->kl]*/;
627         float extent[3];
628         float length = 0, dot = 0;
629         float dir[3] = {0, 0, 0};
630         float vel[3];
631         float k = 0.0f;
632         float L = s->restlen;
633         float cb; /* = clmd->sim_parms->structural; */ /*UNUSED*/
634         
635         float scaling = 0.0;
636         
637         int no_compress = clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_NO_SPRING_COMPRESS;
638         
639         zero_v3(s->f);
640         zero_m3(s->dfdx);
641         zero_m3(s->dfdv);
642         
643         s->flags &= ~CLOTH_SPRING_FLAG_NEEDED;
644         
645         // calculate elonglation
646         sub_v3_v3v3(extent, lVector_v3(X, s->kl), lVector_v3(X, s->ij));
647         sub_v3_v3v3(vel, lVector_v3(V, s->kl), lVector_v3(V, s->ij));
648         dot = dot_v3v3(extent, extent);
649         length = sqrt(dot);
650         
651         if (length > ALMOST_ZERO) {
652                 /*
653                 if (length>L) {
654                         if ((clmd->sim_parms->flags & CSIMSETT_FLAG_TEARING_ENABLED) &&
655                             ( ((length-L)*100.0f/L) > clmd->sim_parms->maxspringlen )) {
656                                 // cut spring!
657                                 s->flags |= CSPRING_FLAG_DEACTIVATE;
658                                 return;
659                         }
660                 }
661                 */
662                 mul_v3_v3fl(dir, extent, 1.0f/length);
663         }
664         else {
665                 zero_v3(dir);
666         }
667         
668         // calculate force of structural + shear springs
669         if (ELEM(s->type, CLOTH_SPRING_TYPE_STRUCTURAL, CLOTH_SPRING_TYPE_SHEAR, CLOTH_SPRING_TYPE_SEWING)) {
670 #ifdef CLOTH_FORCE_SPRING_STRUCTURAL
671                 if (length > L || no_compress) {
672                         float stretch_force[3] = {0, 0, 0};
673                         
674                         s->flags |= CLOTH_SPRING_FLAG_NEEDED;
675                         
676                         k = clmd->sim_parms->structural;
677                         scaling = k + s->stiffness * fabsf(clmd->sim_parms->max_struct - k);
678                         
679                         k = scaling / (clmd->sim_parms->avg_spring_len + FLT_EPSILON);
680                         // TODO: verify, half verified (couldn't see error)
681                         if (s->type & CLOTH_SPRING_TYPE_SEWING) {
682                                 // sewing springs usually have a large distance at first so clamp the force so we don't get tunnelling through colission objects
683                                 float force = k*(length-L);
684                                 if (force > clmd->sim_parms->max_sewing) {
685                                         force = clmd->sim_parms->max_sewing;
686                                 }
687                                 mul_v3_v3fl(stretch_force, dir, force);
688                         }
689                         else {
690                                 mul_v3_v3fl(stretch_force, dir, k * (length - L));
691                         }
692                         
693                         add_v3_v3(s->f, stretch_force);
694                         
695                         // Ascher & Boxman, p.21: Damping only during elonglation
696                         // something wrong with it...
697                         madd_v3_v3fl(s->f, dir, clmd->sim_parms->Cdis * dot_v3v3(vel, dir));
698                         
699                         /* VERIFIED */
700                         dfdx_spring(s->dfdx, dir, length, L, k);
701                         
702                         /* VERIFIED */
703                         dfdv_damp(s->dfdv, dir, clmd->sim_parms->Cdis);
704                 }
705 #endif
706         }
707         else if (s->type & CLOTH_SPRING_TYPE_GOAL) {
708 #ifdef CLOTH_FORCE_SPRING_GOAL
709                 float target[3];
710                 
711                 s->flags |= CLOTH_SPRING_FLAG_NEEDED;
712                 
713                 // current_position = xold + t * (xnew - xold)
714                 interp_v3_v3v3(target, v1->xold, v1->xconst, time);
715                 sub_v3_v3v3(extent, lVector_v3(X, s->ij), target);
716                 BKE_sim_debug_data_add_line(clmd->debug_data, v1->xconst, v1->xold, 1,0,0, "springs", hash_vertex(7825, s->ij));
717                 
718                 // SEE MSG BELOW (these are UNUSED)
719                 // dot = dot_v3v3(extent, extent);
720                 // length = sqrt(dot);
721                 
722                 k = clmd->sim_parms->goalspring;
723                 scaling = k + s->stiffness * fabsf(clmd->sim_parms->max_struct - k);
724                         
725                 k = v1->goal * scaling / (clmd->sim_parms->avg_spring_len + FLT_EPSILON);
726                 madd_v3_v3fl(s->f, extent, -k);
727                 
728                 /* XXX this has no effect: dir is always null at this point! - lukas_t
729                 madd_v3_v3fl(s->f, dir, clmd->sim_parms->goalfrict * 0.01f * dot_v3v3(vel, dir));
730                 */
731                 
732                 // HERE IS THE PROBLEM!!!!
733                 // dfdx_spring(s->dfdx, dir, length, 0.0, k);
734                 // dfdv_damp(s->dfdv, dir, MIN2(1.0, (clmd->sim_parms->goalfrict/100.0)));
735 #endif
736         }
737         else {  /* calculate force of bending springs */
738 #ifdef CLOTH_FORCE_SPRING_BEND
739                 if (length < L) {
740                         s->flags |= CLOTH_SPRING_FLAG_NEEDED;
741                         
742                         k = clmd->sim_parms->bending;
743                         
744                         scaling = k + s->stiffness * fabsf(clmd->sim_parms->max_bend - k);
745                         cb = k = scaling / (20.0f * (clmd->sim_parms->avg_spring_len + FLT_EPSILON));
746                         
747                         madd_v3_v3fl(s->f, dir, fbstar(length, L, k, cb));
748                         
749                         outerproduct(s->dfdx, dir, dir);
750                         mul_m3_fl(s->dfdx, fbstar_jacobi(length, L, k, cb));
751                 }
752 #endif
753         }
754 }
755
756 static void cloth_apply_spring_force(ClothModifierData *clmd, ClothSpring *s, lVector &F, TripletList &tlist_dFdX, TripletList &tlist_dFdV)
757 {
758         /* XXX reserve elements in tmp? */
759         
760         /* ignore disabled springs */
761         if (!(s->flags & CLOTH_SPRING_FLAG_NEEDED))
762                 return;
763         
764         if (!(s->type & CLOTH_SPRING_TYPE_BENDING)) {
765                 triplets_m3fl(tlist_dFdV, s->dfdv, s->ij, s->ij, 1.0f);
766                 triplets_m3fl(tlist_dFdV, s->dfdv, s->kl, s->kl, 1.0f);
767                 triplets_m3fl(tlist_dFdV, s->dfdv, s->ij, s->kl, -1.0f);
768                 triplets_m3fl(tlist_dFdV, s->dfdv, s->kl, s->ij, -1.0f);
769         }
770         
771         add_v3_v3(lVector_v3(F, s->ij), s->f);
772         if (!(s->type & CLOTH_SPRING_TYPE_GOAL)) {
773                 sub_v3_v3(lVector_v3(F, s->kl), s->f);
774         }
775         
776         triplets_m3fl(tlist_dFdX, s->dfdx, s->ij, s->ij, 1.0f);
777         triplets_m3fl(tlist_dFdX, s->dfdx, s->kl, s->kl, 1.0f);
778         triplets_m3fl(tlist_dFdX, s->dfdx, s->ij, s->kl, -1.0f);
779         triplets_m3fl(tlist_dFdX, s->dfdx, s->kl, s->ij, -1.0f);
780 }
781
782 static float calc_nor_area_tri(float nor[3], const float v1[3], const float v2[3], const float v3[3])
783 {
784         float n1[3], n2[3];
785         
786         sub_v3_v3v3(n1, v1, v2);
787         sub_v3_v3v3(n2, v2, v3);
788         
789         cross_v3_v3v3(nor, n1, n2);
790         return normalize_v3(nor);
791 }
792
793 static float calc_nor_area_quad(float nor[3], const float v1[3], const float v2[3], const float v3[3], const float v4[3])
794 {
795         float n1[3], n2[3];
796         
797         sub_v3_v3v3(n1, v1, v3);
798         sub_v3_v3v3(n2, v2, v4);
799         
800         cross_v3_v3v3(nor, n1, n2);
801         return normalize_v3(nor);
802 }
803
804 static void cloth_calc_force(ClothModifierData *clmd, lVector &F, lMatrix &dFdX, lMatrix &dFdV, const lVector &X, const lVector &V, const lMatrix &M, ListBase *effectors, float time)
805 {
806         Cloth *cloth = clmd->clothObject;
807         Implicit_Data *id = cloth->implicit;
808         unsigned int numverts = cloth->numverts;
809         ClothVertex *verts = cloth->verts;
810         float drag = clmd->sim_parms->Cvi * 0.01f; /* viscosity of air scaled in percent */
811         float gravity[3] = {0,0,0};
812         float f[3], dfdx[3][3], dfdv[3][3];
813         
814         F.setZero();
815         dFdX.setZero();
816         dFdV.setZero();
817         
818         TripletList tlist_dFdV, tlist_dFdX;
819         
820 #ifdef CLOTH_FORCE_GRAVITY
821         /* global acceleration (gravitation) */
822         if (clmd->scene->physics_settings.flag & PHYS_GLOBAL_GRAVITY) {
823                 /* scale gravity force
824                  * XXX 0.001 factor looks totally arbitrary ... what is this? lukas_t
825                  */
826                 mul_v3_v3fl(gravity, clmd->scene->physics_settings.gravity, 0.001f * clmd->sim_parms->effector_weights->global_gravity);
827         }
828         for (int i = 0; i < numverts; ++i) {
829                 float acc[3];
830                 /* gravitational mass same as inertial mass */
831                 acc_world_to_root(acc, lVector_v3(X, i), lVector_v3(V, i), gravity, id->root[i]);
832                 madd_v3_v3fl(lVector_v3(F, i), acc, verts[i].mass);
833         }
834 #endif
835         
836 #ifdef CLOTH_FORCE_DRAG
837         /* air drag */
838         for (int i = 0; i < numverts; ++i) {
839 #if 1
840                 /* NB: uses root space velocity, no need to transform */
841                 mul_v3_v3fl(f, lVector_v3(V, i), -drag);
842                 add_v3_v3(lVector_v3(F, i), f);
843                 
844                 triplets_m3fl(tlist_dFdV, I, i, i, -drag);
845 #else
846                 float drag_dfdv[3][3], t[3];
847                 
848                 mul_v3_v3fl(f, lVector_v3(V, i), -drag);
849                 force_world_to_root(t, lVector_v3(X, i), lVector_v3(V, i), f, verts[i].mass, id->root[i]);
850                 add_v3_v3(lVector_v3(F, i), t);
851                 
852                 copy_m3_m3(drag_dfdv, I);
853                 mul_m3_fl(drag_dfdv, -drag);
854                 dfdv_world_to_root(dfdv, drag_dfdv, verts[i].mass, id->root[i]);
855                 triplets_m3(tlist_dFdV, dfdv, i, i);
856 #endif
857         }
858 #endif
859
860 //      hair_volume_forces(clmd, lF, lX, lV, numverts);
861
862 #ifdef CLOTH_FORCE_EFFECTORS
863         /* handle external forces like wind */
864         if (effectors) {
865                 const float effector_scale = 0.02f;
866                 MFace *mfaces = cloth->mfaces;
867                 EffectedPoint epoint;
868                 lVector winvec(F.rows());
869                 winvec.setZero();
870                 
871                 // precalculate wind forces
872                 for (int i = 0; i < cloth->numverts; i++) {
873                         pd_point_from_loc(clmd->scene, (float*)lVector_v3(X, i), (float*)lVector_v3(V, i), i, &epoint);
874                         pdDoEffectors(effectors, NULL, clmd->sim_parms->effector_weights, &epoint, lVector_v3(winvec, i), NULL);
875                 }
876                 
877                 for (int i = 0; i < cloth->numfaces; i++) {
878                         float nor[3], area;
879                         float factor;
880                         MFace *mf = &mfaces[i];
881                         
882                         // calculate face normal and area
883                         if (mf->v4) {
884                                 area = calc_nor_area_quad(nor, lVector_v3(X, mf->v1), lVector_v3(X, mf->v2), lVector_v3(X, mf->v3), lVector_v3(X, mf->v4));
885                                 factor = effector_scale * area * 0.25f;
886                         }
887                         else {
888                                 area = calc_nor_area_tri(nor, lVector_v3(X, mf->v1), lVector_v3(X, mf->v2), lVector_v3(X, mf->v3));
889                                 factor = effector_scale * area / 3.0f;
890                         }
891                         
892                         madd_v3_v3fl(lVector_v3(F, mf->v1), nor, factor * dot_v3v3(lVector_v3(winvec, mf->v1), nor));
893                         madd_v3_v3fl(lVector_v3(F, mf->v2), nor, factor * dot_v3v3(lVector_v3(winvec, mf->v2), nor));
894                         madd_v3_v3fl(lVector_v3(F, mf->v3), nor, factor * dot_v3v3(lVector_v3(winvec, mf->v3), nor));
895                         if (mf->v4)
896                                 madd_v3_v3fl(lVector_v3(F, mf->v4), nor, factor * dot_v3v3(lVector_v3(winvec, mf->v4), nor));
897                 }
898
899                 /* Hair has only edges */
900                 if (cloth->numfaces == 0) {
901                         ClothSpring *spring;
902                         float dir[3], length;
903                         float factor = 0.01;
904                         
905                         for (LinkNode *link = cloth->springs; link; link = link->next) {
906                                 spring = (ClothSpring *)link->link;
907                                 
908                                 /* structural springs represent hair strands,
909                                  * their length signifies surface area and mass
910                                  */
911                                 if (spring->type != CLOTH_SPRING_TYPE_STRUCTURAL)
912                                         continue;
913                                 
914                                 float *win_ij = lVector_v3(winvec, spring->ij);
915                                 float *win_kl = lVector_v3(winvec, spring->kl);
916                                 float win_ortho[3];
917                                 
918                                 sub_v3_v3v3(dir, (float*)lVector_v3(X, spring->ij), (float*)lVector_v3(X, spring->kl));
919                                 length = normalize_v3(dir);
920                                 
921                                 madd_v3_v3v3fl(win_ortho, win_ij, dir, -dot_v3v3(win_ij, dir));
922                                 madd_v3_v3fl(lVector_v3(F, spring->ij), win_ortho, factor * length);
923                                 
924                                 madd_v3_v3v3fl(win_ortho, win_kl, dir, -dot_v3v3(win_kl, dir));
925                                 madd_v3_v3fl(lVector_v3(F, spring->kl), win_ortho, factor * length);
926                         }
927                 }
928         }
929 #endif
930         
931         // calculate spring forces
932         for (LinkNode *link = cloth->springs; link; link = link->next) {
933                 // only handle active springs
934                 ClothSpring *spring = (ClothSpring *)link->link;
935                 if (!(spring->flags & CLOTH_SPRING_FLAG_DEACTIVATE))
936                         cloth_calc_spring_force(clmd, spring, X, V, time);
937         }
938         
939         // apply spring forces
940         for (LinkNode *link = cloth->springs; link; link = link->next) {
941                 // only handle active springs
942                 ClothSpring *spring = (ClothSpring *)link->link;
943                 if (!(spring->flags & CLOTH_SPRING_FLAG_DEACTIVATE))
944                         cloth_apply_spring_force(clmd, spring, F, tlist_dFdX, tlist_dFdV);
945         }
946         
947         lMatrix_add_triplets(dFdV, tlist_dFdV);
948         lMatrix_add_triplets(dFdX, tlist_dFdX);
949 }
950
951 /* Init constraint matrix
952  * This is part of the modified CG method suggested by Baraff/Witkin in
953  * "Large Steps in Cloth Simulation" (Siggraph 1998)
954  */
955 static void setup_constraint_matrix(ClothModifierData *clmd, ColliderContacts *contacts, int totcolliders, const lVector &V, lMatrix &S, lVector &z, float dt)
956 {
957         ClothVertex *verts = clmd->clothObject->verts;
958         int numverts = clmd->clothObject->numverts;
959         TripletList tlist_sub;
960         int i, j, v;
961         
962         S.setIdentity();
963         z.setZero();
964         
965         for (v = 0; v < numverts; v++) {
966                 if (verts[v].flags & CLOTH_VERT_FLAG_PINNED) {
967                         /* pinned vertex constraints */
968                         zero_v3(lVector_v3(z, v)); /* velocity is defined externally */
969                         triplets_m3(tlist_sub, I, v, v);
970                 }
971         }
972
973 #if 0 // TODO
974         for (i = 0; i < totcolliders; ++i) {
975                 ColliderContacts *ct = &contacts[i];
976                 for (j = 0; j < ct->totcollisions; ++j) {
977                         CollPair *collpair = &ct->collisions[j];
978                         int v = collpair->face1;
979                         float cmat[3][3];
980                         float impulse[3];
981                         
982                         /* pinned verts handled separately */
983                         if (verts[v].flags & CLOTH_VERT_FLAG_PINNED)
984                                 continue;
985                         
986                         /* calculate collision response */
987                         if (!cloth_points_collpair_response(clmd, ct->collmd, ct->ob->pd, collpair, dt, impulse))
988                                 continue;
989                         
990                         add_v3_v3(z[v], impulse);
991                         
992                         /* modify S to enforce velocity constraint in normal direction */
993                         mul_fvectorT_fvector(cmat, collpair->normal, collpair->normal);
994                         sub_m3_m3m3(S[v].m, I, cmat);
995                         
996                         BKE_sim_debug_data_add_dot(clmd->debug_data, collpair->pa, 0, 1, 0, "collision", hash_collpair(936, collpair));
997                         BKE_sim_debug_data_add_dot(clmd->debug_data, collpair->pb, 1, 0, 0, "collision", hash_collpair(937, collpair));
998                         BKE_sim_debug_data_add_line(clmd->debug_data, collpair->pa, collpair->pb, 0.7, 0.7, 0.7, "collision", hash_collpair(938, collpair));
999                         
1000                         { /* DEBUG */
1001 //                              float nor[3];
1002 //                              mul_v3_v3fl(nor, collpair->normal, collpair->distance);
1003 //                              BKE_sim_debug_data_add_vector(clmd->debug_data, collpair->pb, nor, 1, 1, 0, "collision", hash_collpair(939, collpair));
1004                                 BKE_sim_debug_data_add_vector(clmd->debug_data, collpair->pb, impulse, 1, 1, 0, "collision", hash_collpair(940, collpair));
1005 //                              BKE_sim_debug_data_add_vector(clmd->debug_data, collpair->pb, collpair->normal, 1, 1, 0, "collision", hash_collpair(941, collpair));
1006                         }
1007                 }
1008         }
1009 #endif
1010         
1011         lMatrix_sub_triplets(S, tlist_sub);
1012 }
1013
1014 int implicit_solver(Object *ob, float frame, ClothModifierData *clmd, ListBase *effectors)
1015 {
1016         float step=0.0f, tf=clmd->sim_parms->timescale;
1017         Cloth *cloth = clmd->clothObject;
1018         ClothVertex *verts = cloth->verts/*, *cv*/;
1019         unsigned int numverts = cloth->numverts;
1020         float dt = clmd->sim_parms->timescale / clmd->sim_parms->stepsPerFrame;
1021         float spf = (float)clmd->sim_parms->stepsPerFrame / clmd->sim_parms->timescale;
1022         Implicit_Data *id = cloth->implicit;
1023         ColliderContacts *contacts = NULL;
1024         int totcolliders = 0;
1025         
1026         BKE_sim_debug_data_clear_category(clmd->debug_data, "collision");
1027         
1028         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL) { /* do goal stuff */
1029                 for (int i = 0; i < numverts; i++) {
1030                         // update velocities with constrained velocities from pinned verts
1031                         if (verts[i].flags & CLOTH_VERT_FLAG_PINNED) {
1032                                 float v[3];
1033                                 sub_v3_v3v3(v, verts[i].xconst, verts[i].xold);
1034                                 // mul_v3_fl(id->V[i], clmd->sim_parms->stepsPerFrame);
1035                                 /* note: should be zero for root vertices, but other verts could be pinned as well */
1036                                 vel_world_to_root(lVector_v3(id->V, i), lVector_v3(id->X, i), v, id->root[i]);
1037                         }
1038                 }
1039         }
1040         
1041         if (clmd->debug_data) {
1042                 for (int i = 0; i < numverts; i++) {
1043                         BKE_sim_debug_data_add_dot(clmd->debug_data, verts[i].x, 1.0f, 0.1f, 1.0f, "points", hash_vertex(583, i));
1044                 }
1045         }
1046         
1047         while (step < tf) {
1048                 
1049                 /* copy velocities for collision */
1050                 for (int i = 0; i < numverts; i++) {
1051                         vel_root_to_world(verts[i].tv, lVector_v3(id->X, i), lVector_v3(id->V, i), id->root[i]);
1052                         copy_v3_v3(verts[i].v, verts[i].tv);
1053                 }
1054                 
1055                 /* determine contact points */
1056                 if (clmd->coll_parms->flags & CLOTH_COLLSETTINGS_FLAG_ENABLED) {
1057                         if (clmd->coll_parms->flags & CLOTH_COLLSETTINGS_FLAG_POINTS) {
1058                                 cloth_find_point_contacts(ob, clmd, 0.0f, tf, &contacts, &totcolliders);
1059                         }
1060                 }
1061                 
1062                 /* setup vertex constraints for pinned vertices and contacts */
1063                 setup_constraint_matrix(clmd, contacts, totcolliders, id->V, id->S, id->z, dt);
1064                 
1065                 // damping velocity for artistic reasons
1066 //              mul_lfvectorS(id->V, id->V, clmd->sim_parms->vel_damping, numverts);
1067
1068                 // calculate forces
1069                 cloth_calc_force(clmd, id->F, id->dFdX, id->dFdV, id->X, id->V, id->M, effectors, step);
1070                 
1071                 // calculate new velocity
1072                 simulate_implicit_euler(id, dt);
1073                 
1074                 // advance positions
1075                 id->Xnew = id->X + id->Vnew * dt;
1076                 
1077                 for (int i = 0; i < numverts; i++) {
1078                         /* move pinned verts to correct position */
1079                         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL) {
1080                                 if (verts[i].flags & CLOTH_VERT_FLAG_PINNED) {
1081                                         float x[3];
1082                                         interp_v3_v3v3(x, verts[i].xold, verts[i].xconst, step + dt);
1083                                         loc_world_to_root(lVector_v3(id->Xnew, i), x, id->root[i]);
1084                                 }
1085                         }
1086                         
1087                         loc_root_to_world(verts[i].txold, lVector_v3(id->X, i), id->root[i]);
1088                         
1089                         if (!(verts[i].flags & CLOTH_VERT_FLAG_PINNED) && i > 0) {
1090                                 BKE_sim_debug_data_add_line(clmd->debug_data, lVector_v3(id->X, i), lVector_v3(id->X, i-1), 0.6, 0.3, 0.3, "hair", hash_vertex(4892, i));
1091                                 BKE_sim_debug_data_add_line(clmd->debug_data, lVector_v3(id->Xnew, i), lVector_v3(id->Xnew, i-1), 1, 0.5, 0.5, "hair", hash_vertex(4893, i));
1092                                 BKE_sim_debug_data_add_line(clmd->debug_data, verts[i].xconst, verts[i-1].xconst, 0.25, 0.4, 0.25, "hair", hash_vertex(4873, i));
1093                         }
1094 //                      BKE_sim_debug_data_add_vector(clmd->debug_data, id->X[i], id->V[i], 0, 0, 1, "velocity", hash_vertex(3158, i));
1095                 }
1096                 
1097                 /* free contact points */
1098                 if (contacts) {
1099                         cloth_free_contacts(contacts, totcolliders);
1100                 }
1101
1102                 id->X = id->Xnew;
1103                 id->V = id->Vnew;
1104                 
1105                 step += dt;
1106         }
1107         
1108         for (int i = 0; i < numverts; i++) {
1109                 if ((clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL) && (verts [i].flags & CLOTH_VERT_FLAG_PINNED)) {
1110                         copy_v3_v3(verts[i].x, verts[i].xconst);
1111                         copy_v3_v3(verts[i].txold, verts[i].x);
1112                         
1113                         vel_root_to_world(verts[i].v, lVector_v3(id->X, i), lVector_v3(id->V, i), id->root[i]);
1114                 }
1115                 else {
1116                         loc_root_to_world(verts[i].x, lVector_v3(id->X, i), id->root[i]);
1117                         copy_v3_v3(verts[i].txold, verts[i].x);
1118                         
1119                         vel_root_to_world(verts[i].v, lVector_v3(id->X, i), lVector_v3(id->V, i), id->root[i]);
1120                 }
1121         }
1122         
1123         return 1;
1124 }
1125
1126 void implicit_set_positions(ClothModifierData *clmd)
1127 {
1128         Cloth *cloth = clmd->clothObject;
1129         ClothVertex *verts = cloth->verts;
1130         ClothHairRoot *cloth_roots = clmd->roots;
1131         unsigned int numverts = cloth->numverts, i;
1132         
1133         Implicit_Data::RootTransforms &root = cloth->implicit->root;
1134         lVector &X = cloth->implicit->X;
1135         lVector &V = cloth->implicit->V;
1136         
1137         for (i = 0; i < numverts; i++) {
1138                 copy_v3_v3(root[i].loc, cloth_roots[i].loc);
1139                 copy_m3_m3(root[i].rot, cloth_roots[i].rot);
1140                 
1141                 loc_world_to_root(lVector_v3(X, i), verts[i].x, root[i]);
1142                 vel_world_to_root(lVector_v3(V, i), lVector_v3(X, i), verts[i].v, root[i]);
1143         }
1144 }
1145
1146 static void implicit_set_mass(ClothModifierData *clmd)
1147 {
1148         Cloth *cloth = clmd->clothObject;
1149         ClothVertex *verts = cloth->verts;
1150         unsigned int numverts = cloth->numverts;
1151         
1152         lMatrix &M = cloth->implicit->M;
1153         
1154         lMatrix_reserve_elems(M, 1);
1155         for (int i = 0; i < numverts; ++i) {
1156                 M.insert(3*i+0, 3*i+0) = verts[i].mass;
1157                 M.insert(3*i+1, 3*i+1) = verts[i].mass;
1158                 M.insert(3*i+2, 3*i+2) = verts[i].mass;
1159         }
1160 }
1161
1162 int implicit_init(Object *UNUSED(ob), ClothModifierData *clmd)
1163 {
1164         Cloth *cloth = clmd->clothObject;
1165         
1166         cloth->implicit = new Implicit_Data(cloth->numverts);
1167         
1168         implicit_set_mass(clmd);
1169         implicit_set_positions(clmd);
1170         
1171 #if 0
1172         // init springs 
1173         search = cloth->springs;
1174         for (i = 0; i < cloth->numsprings; i++) {
1175                 spring = search->link;
1176                 
1177                 // dFdV_start[i].r = big_I[i].r = big_zero[i].r = 
1178                 id->A[i+cloth->numverts].r = id->dFdV[i+cloth->numverts].r = id->dFdX[i+cloth->numverts].r = 
1179                                 id->P[i+cloth->numverts].r = id->Pinv[i+cloth->numverts].r = id->bigI[i+cloth->numverts].r = id->M[i+cloth->numverts].r = spring->ij;
1180
1181                 // dFdV_start[i].c = big_I[i].c = big_zero[i].c = 
1182                 id->A[i+cloth->numverts].c = id->dFdV[i+cloth->numverts].c = id->dFdX[i+cloth->numverts].c = 
1183                                 id->P[i+cloth->numverts].c = id->Pinv[i+cloth->numverts].c = id->bigI[i+cloth->numverts].c = id->M[i+cloth->numverts].c = spring->kl;
1184
1185                 spring->matrix_index = i + cloth->numverts;
1186                 
1187                 search = search->next;
1188         }
1189 #endif
1190
1191         return 1;
1192 }
1193
1194 int     implicit_free(ClothModifierData *clmd)
1195 {
1196         Cloth *cloth = clmd->clothObject;
1197         
1198         if (cloth && cloth->implicit) {
1199                 delete cloth->implicit;
1200         }
1201         
1202         return 1;
1203 }
1204
1205 /* ================ Volumetric Hair Interaction ================
1206  * adapted from
1207  *      Volumetric Methods for Simulation and Rendering of Hair
1208  *      by Lena Petrovic, Mark Henne and John Anderson
1209  *      Pixar Technical Memo #06-08, Pixar Animation Studios
1210  */
1211
1212 /* Note about array indexing:
1213  * Generally the arrays here are one-dimensional.
1214  * The relation between 3D indices and the array offset is
1215  *   offset = x + res_x * y + res_y * z
1216  */
1217
1218 /* TODO: This is an initial implementation and should be made much better in due time.
1219  * What should at least be implemented is a grid size parameter and a smoothing kernel
1220  * for bigger grids.
1221  */
1222
1223 #if 0
1224 /* 10x10x10 grid gives nice initial results */
1225 static const int hair_grid_res = 10;
1226
1227 static int hair_grid_size(int res)
1228 {
1229         return res * res * res;
1230 }
1231
1232 BLI_INLINE void hair_grid_get_scale(int res, const float gmin[3], const float gmax[3], float scale[3])
1233 {
1234         sub_v3_v3v3(scale, gmax, gmin);
1235         mul_v3_fl(scale, 1.0f / (res-1));
1236 }
1237
1238 typedef struct HairGridVert {
1239         float velocity[3];
1240         float density;
1241 } HairGridVert;
1242
1243 #define HAIR_GRID_INDEX_AXIS(vec, res, gmin, scale, axis) ( min_ii( max_ii( (int)((vec[axis] - gmin[axis]) / scale[axis]), 0), res-2 ) )
1244
1245 BLI_INLINE int hair_grid_offset(const float vec[3], int res, const float gmin[3], const float scale[3])
1246 {
1247         int i, j, k;
1248         i = HAIR_GRID_INDEX_AXIS(vec, res, gmin, scale, 0);
1249         j = HAIR_GRID_INDEX_AXIS(vec, res, gmin, scale, 1);
1250         k = HAIR_GRID_INDEX_AXIS(vec, res, gmin, scale, 2);
1251         return i + (j + k*res)*res;
1252 }
1253
1254 BLI_INLINE int hair_grid_interp_weights(int res, const float gmin[3], const float scale[3], const float vec[3], float uvw[3])
1255 {
1256         int i, j, k, offset;
1257         
1258         i = HAIR_GRID_INDEX_AXIS(vec, res, gmin, scale, 0);
1259         j = HAIR_GRID_INDEX_AXIS(vec, res, gmin, scale, 1);
1260         k = HAIR_GRID_INDEX_AXIS(vec, res, gmin, scale, 2);
1261         offset = i + (j + k*res)*res;
1262         
1263         uvw[0] = (vec[0] - gmin[0]) / scale[0] - (float)i;
1264         uvw[1] = (vec[1] - gmin[1]) / scale[1] - (float)j;
1265         uvw[2] = (vec[2] - gmin[2]) / scale[2] - (float)k;
1266         
1267         return offset;
1268 }
1269
1270 BLI_INLINE void hair_grid_interpolate(const HairGridVert *grid, int res, const float gmin[3], const float scale[3], const float vec[3],
1271                                       float *density, float velocity[3], float density_gradient[3])
1272 {
1273         HairGridVert data[8];
1274         float uvw[3], muvw[3];
1275         int res2 = res * res;
1276         int offset;
1277         
1278         offset = hair_grid_interp_weights(res, gmin, scale, vec, uvw);
1279         muvw[0] = 1.0f - uvw[0];
1280         muvw[1] = 1.0f - uvw[1];
1281         muvw[2] = 1.0f - uvw[2];
1282         
1283         data[0] = grid[offset           ];
1284         data[1] = grid[offset         +1];
1285         data[2] = grid[offset     +res  ];
1286         data[3] = grid[offset     +res+1];
1287         data[4] = grid[offset+res2      ];
1288         data[5] = grid[offset+res2    +1];
1289         data[6] = grid[offset+res2+res  ];
1290         data[7] = grid[offset+res2+res+1];
1291         
1292         if (density) {
1293                 *density = muvw[2]*( muvw[1]*( muvw[0]*data[0].density + uvw[0]*data[1].density )   +
1294                                       uvw[1]*( muvw[0]*data[2].density + uvw[0]*data[3].density ) ) +
1295                             uvw[2]*( muvw[1]*( muvw[0]*data[4].density + uvw[0]*data[5].density )   +
1296                                       uvw[1]*( muvw[0]*data[6].density + uvw[0]*data[7].density ) );
1297         }
1298         if (velocity) {
1299                 int k;
1300                 for (k = 0; k < 3; ++k) {
1301                         velocity[k] = muvw[2]*( muvw[1]*( muvw[0]*data[0].velocity[k] + uvw[0]*data[1].velocity[k] )   +
1302                                                  uvw[1]*( muvw[0]*data[2].velocity[k] + uvw[0]*data[3].velocity[k] ) ) +
1303                                        uvw[2]*( muvw[1]*( muvw[0]*data[4].velocity[k] + uvw[0]*data[5].velocity[k] )   +
1304                                                  uvw[1]*( muvw[0]*data[6].velocity[k] + uvw[0]*data[7].velocity[k] ) );
1305                 }
1306         }
1307         if (density_gradient) {
1308                 density_gradient[0] = muvw[1] * muvw[2] * ( data[0].density - data[1].density ) +
1309                                        uvw[1] * muvw[2] * ( data[2].density - data[3].density ) +
1310                                       muvw[1] *  uvw[2] * ( data[4].density - data[5].density ) +
1311                                        uvw[1] *  uvw[2] * ( data[6].density - data[7].density );
1312                 
1313                 density_gradient[1] = muvw[2] * muvw[0] * ( data[0].density - data[2].density ) +
1314                                        uvw[2] * muvw[0] * ( data[4].density - data[6].density ) +
1315                                       muvw[2] *  uvw[0] * ( data[1].density - data[3].density ) +
1316                                        uvw[2] *  uvw[0] * ( data[5].density - data[7].density );
1317                 
1318                 density_gradient[2] = muvw[2] * muvw[0] * ( data[0].density - data[4].density ) +
1319                                        uvw[2] * muvw[0] * ( data[1].density - data[5].density ) +
1320                                       muvw[2] *  uvw[0] * ( data[2].density - data[6].density ) +
1321                                        uvw[2] *  uvw[0] * ( data[3].density - data[7].density );
1322         }
1323 }
1324
1325 static void hair_velocity_smoothing(const HairGridVert *hairgrid, const float gmin[3], const float scale[3], float smoothfac,
1326                                     lfVector *lF, lfVector *lX, lfVector *lV, unsigned int numverts)
1327 {
1328         int v;
1329         /* calculate forces */
1330         for (v = 0; v < numverts; v++) {
1331                 float density, velocity[3];
1332                 
1333                 hair_grid_interpolate(hairgrid, hair_grid_res, gmin, scale, lX[v], &density, velocity, NULL);
1334                 
1335                 sub_v3_v3(velocity, lV[v]);
1336                 madd_v3_v3fl(lF[v], velocity, smoothfac);
1337         }
1338 }
1339
1340 static void hair_velocity_collision(const HairGridVert *collgrid, const float gmin[3], const float scale[3], float collfac,
1341                                     lfVector *lF, lfVector *lX, lfVector *lV, unsigned int numverts)
1342 {
1343         int v;
1344         /* calculate forces */
1345         for (v = 0; v < numverts; v++) {
1346                 int offset = hair_grid_offset(lX[v], hair_grid_res, gmin, scale);
1347                 
1348                 if (collgrid[offset].density > 0.0f) {
1349                         lF[v][0] += collfac * (collgrid[offset].velocity[0] - lV[v][0]);
1350                         lF[v][1] += collfac * (collgrid[offset].velocity[1] - lV[v][1]);
1351                         lF[v][2] += collfac * (collgrid[offset].velocity[2] - lV[v][2]);
1352                 }
1353         }
1354 }
1355
1356 static void hair_pressure_force(const HairGridVert *hairgrid, const float gmin[3], const float scale[3], float pressurefac, float minpressure,
1357                                 lfVector *lF, lfVector *lX, unsigned int numverts)
1358 {
1359         int v;
1360         
1361         /* calculate forces */
1362         for (v = 0; v < numverts; v++) {
1363                 float density, gradient[3], gradlen;
1364                 
1365                 hair_grid_interpolate(hairgrid, hair_grid_res, gmin, scale, lX[v], &density, NULL, gradient);
1366                 
1367                 gradlen = normalize_v3(gradient) - minpressure;
1368                 if (gradlen < 0.0f)
1369                         continue;
1370                 mul_v3_fl(gradient, gradlen);
1371                 
1372                 madd_v3_v3fl(lF[v], gradient, pressurefac);
1373         }
1374 }
1375
1376 static void hair_volume_get_boundbox(lfVector *lX, unsigned int numverts, float gmin[3], float gmax[3])
1377 {
1378         int i;
1379         
1380         INIT_MINMAX(gmin, gmax);
1381         for (i = 0; i < numverts; i++)
1382                 DO_MINMAX(lX[i], gmin, gmax);
1383 }
1384
1385 BLI_INLINE bool hair_grid_point_valid(const float vec[3], float gmin[3], float gmax[3])
1386 {
1387         return !(vec[0] < gmin[0] || vec[1] < gmin[1] || vec[2] < gmin[2] ||
1388                  vec[0] > gmax[0] || vec[1] > gmax[1] || vec[2] > gmax[2]);
1389 }
1390
1391 BLI_INLINE float dist_tent_v3f3(const float a[3], float x, float y, float z)
1392 {
1393         float w = (1.0f - fabsf(a[0] - x)) * (1.0f - fabsf(a[1] - y)) * (1.0f - fabsf(a[2] - z));
1394         return w;
1395 }
1396
1397 /* returns the grid array offset as well to avoid redundant calculation */
1398 static int hair_grid_weights(int res, const float gmin[3], const float scale[3], const float vec[3], float weights[8])
1399 {
1400         int i, j, k, offset;
1401         float uvw[3];
1402         
1403         i = HAIR_GRID_INDEX_AXIS(vec, res, gmin, scale, 0);
1404         j = HAIR_GRID_INDEX_AXIS(vec, res, gmin, scale, 1);
1405         k = HAIR_GRID_INDEX_AXIS(vec, res, gmin, scale, 2);
1406         offset = i + (j + k*res)*res;
1407         
1408         uvw[0] = (vec[0] - gmin[0]) / scale[0];
1409         uvw[1] = (vec[1] - gmin[1]) / scale[1];
1410         uvw[2] = (vec[2] - gmin[2]) / scale[2];
1411         
1412         weights[0] = dist_tent_v3f3(uvw, (float)i    , (float)j    , (float)k    );
1413         weights[1] = dist_tent_v3f3(uvw, (float)(i+1), (float)j    , (float)k    );
1414         weights[2] = dist_tent_v3f3(uvw, (float)i    , (float)(j+1), (float)k    );
1415         weights[3] = dist_tent_v3f3(uvw, (float)(i+1), (float)(j+1), (float)k    );
1416         weights[4] = dist_tent_v3f3(uvw, (float)i    , (float)j    , (float)(k+1));
1417         weights[5] = dist_tent_v3f3(uvw, (float)(i+1), (float)j    , (float)(k+1));
1418         weights[6] = dist_tent_v3f3(uvw, (float)i    , (float)(j+1), (float)(k+1));
1419         weights[7] = dist_tent_v3f3(uvw, (float)(i+1), (float)(j+1), (float)(k+1));
1420         
1421         return offset;
1422 }
1423
1424 static HairGridVert *hair_volume_create_hair_grid(ClothModifierData *clmd, lfVector *lX, lfVector *lV, unsigned int numverts)
1425 {
1426         int res = hair_grid_res;
1427         int size = hair_grid_size(res);
1428         HairGridVert *hairgrid;
1429         float gmin[3], gmax[3], scale[3];
1430         /* 2.0f is an experimental value that seems to give good results */
1431         float smoothfac = 2.0f * clmd->sim_parms->velocity_smooth;
1432         unsigned int    v = 0;
1433         int                 i = 0;
1434
1435         hair_volume_get_boundbox(lX, numverts, gmin, gmax);
1436         hair_grid_get_scale(res, gmin, gmax, scale);
1437
1438         hairgrid = MEM_mallocN(sizeof(HairGridVert) * size, "hair voxel data");
1439
1440         /* initialize grid */
1441         for (i = 0; i < size; ++i) {
1442                 zero_v3(hairgrid[i].velocity);
1443                 hairgrid[i].density = 0.0f;
1444         }
1445
1446         /* gather velocities & density */
1447         if (smoothfac > 0.0f) {
1448                 for (v = 0; v < numverts; v++) {
1449                         float *V = lV[v];
1450                         float weights[8];
1451                         int di, dj, dk;
1452                         int offset;
1453                         
1454                         if (!hair_grid_point_valid(lX[v], gmin, gmax))
1455                                 continue;
1456                         
1457                         offset = hair_grid_weights(res, gmin, scale, lX[v], weights);
1458                         
1459                         for (di = 0; di < 2; ++di) {
1460                                 for (dj = 0; dj < 2; ++dj) {
1461                                         for (dk = 0; dk < 2; ++dk) {
1462                                                 int voffset = offset + di + (dj + dk*res)*res;
1463                                                 int iw = di + dj*2 + dk*4;
1464                                                 
1465                                                 hairgrid[voffset].density += weights[iw];
1466                                                 madd_v3_v3fl(hairgrid[voffset].velocity, V, weights[iw]);
1467                                         }
1468                                 }
1469                         }
1470                 }
1471         }
1472
1473         /* divide velocity with density */
1474         for (i = 0; i < size; i++) {
1475                 float density = hairgrid[i].density;
1476                 if (density > 0.0f)
1477                         mul_v3_fl(hairgrid[i].velocity, 1.0f/density);
1478         }
1479         
1480         return hairgrid;
1481 }
1482
1483
1484 static HairGridVert *hair_volume_create_collision_grid(ClothModifierData *clmd, lfVector *lX, unsigned int numverts)
1485 {
1486         int res = hair_grid_res;
1487         int size = hair_grid_size(res);
1488         HairGridVert *collgrid;
1489         ListBase *colliders;
1490         ColliderCache *col = NULL;
1491         float gmin[3], gmax[3], scale[3];
1492         /* 2.0f is an experimental value that seems to give good results */
1493         float collfac = 2.0f * clmd->sim_parms->collider_friction;
1494         unsigned int    v = 0;
1495         int                 i = 0;
1496
1497         hair_volume_get_boundbox(lX, numverts, gmin, gmax);
1498         hair_grid_get_scale(res, gmin, gmax, scale);
1499
1500         collgrid = MEM_mallocN(sizeof(HairGridVert) * size, "hair collider voxel data");
1501
1502         /* initialize grid */
1503         for (i = 0; i < size; ++i) {
1504                 zero_v3(collgrid[i].velocity);
1505                 collgrid[i].density = 0.0f;
1506         }
1507
1508         /* gather colliders */
1509         colliders = get_collider_cache(clmd->scene, NULL, NULL);
1510         if (colliders && collfac > 0.0f) {
1511                 for (col = colliders->first; col; col = col->next) {
1512                         MVert *loc0 = col->collmd->x;
1513                         MVert *loc1 = col->collmd->xnew;
1514                         float vel[3];
1515                         float weights[8];
1516                         int di, dj, dk;
1517                         
1518                         for (v=0; v < col->collmd->numverts; v++, loc0++, loc1++) {
1519                                 int offset;
1520                                 
1521                                 if (!hair_grid_point_valid(loc1->co, gmin, gmax))
1522                                         continue;
1523                                 
1524                                 offset = hair_grid_weights(res, gmin, scale, lX[v], weights);
1525                                 
1526                                 sub_v3_v3v3(vel, loc1->co, loc0->co);
1527                                 
1528                                 for (di = 0; di < 2; ++di) {
1529                                         for (dj = 0; dj < 2; ++dj) {
1530                                                 for (dk = 0; dk < 2; ++dk) {
1531                                                         int voffset = offset + di + (dj + dk*res)*res;
1532                                                         int iw = di + dj*2 + dk*4;
1533                                                         
1534                                                         collgrid[voffset].density += weights[iw];
1535                                                         madd_v3_v3fl(collgrid[voffset].velocity, vel, weights[iw]);
1536                                                 }
1537                                         }
1538                                 }
1539                         }
1540                 }
1541         }
1542         free_collider_cache(&colliders);
1543
1544         /* divide velocity with density */
1545         for (i = 0; i < size; i++) {
1546                 float density = collgrid[i].density;
1547                 if (density > 0.0f)
1548                         mul_v3_fl(collgrid[i].velocity, 1.0f/density);
1549         }
1550         
1551         return collgrid;
1552 }
1553
1554 static void hair_volume_forces(ClothModifierData *clmd, lfVector *lF, lfVector *lX, lfVector *lV, unsigned int numverts)
1555 {
1556         HairGridVert *hairgrid, *collgrid;
1557         float gmin[3], gmax[3], scale[3];
1558         /* 2.0f is an experimental value that seems to give good results */
1559         float smoothfac = 2.0f * clmd->sim_parms->velocity_smooth;
1560         float collfac = 2.0f * clmd->sim_parms->collider_friction;
1561         float pressfac = clmd->sim_parms->pressure;
1562         float minpress = clmd->sim_parms->pressure_threshold;
1563         
1564         if (smoothfac <= 0.0f && collfac <= 0.0f && pressfac <= 0.0f)
1565                 return;
1566         
1567         hair_volume_get_boundbox(lX, numverts, gmin, gmax);
1568         hair_grid_get_scale(hair_grid_res, gmin, gmax, scale);
1569         
1570         hairgrid = hair_volume_create_hair_grid(clmd, lX, lV, numverts);
1571         collgrid = hair_volume_create_collision_grid(clmd, lX, numverts);
1572         
1573         hair_velocity_smoothing(hairgrid, gmin, scale, smoothfac, lF, lX, lV, numverts);
1574         hair_velocity_collision(collgrid, gmin, scale, collfac, lF, lX, lV, numverts);
1575         hair_pressure_force(hairgrid, gmin, scale, pressfac, minpress, lF, lX, numverts);
1576         
1577         MEM_freeN(hairgrid);
1578         MEM_freeN(collgrid);
1579 }
1580 #endif
1581
1582 bool implicit_hair_volume_get_texture_data(Object *UNUSED(ob), ClothModifierData *clmd, ListBase *UNUSED(effectors), VoxelData *vd)
1583 {
1584 #if 0
1585         lfVector *lX, *lV;
1586         HairGridVert *hairgrid/*, *collgrid*/;
1587         int numverts;
1588         int totres, i;
1589         int depth;
1590
1591         if (!clmd->clothObject || !clmd->clothObject->implicit)
1592                 return false;
1593
1594         lX = clmd->clothObject->implicit->X;
1595         lV = clmd->clothObject->implicit->V;
1596         numverts = clmd->clothObject->numverts;
1597
1598         hairgrid = hair_volume_create_hair_grid(clmd, lX, lV, numverts);
1599 //      collgrid = hair_volume_create_collision_grid(clmd, lX, numverts);
1600
1601         vd->resol[0] = hair_grid_res;
1602         vd->resol[1] = hair_grid_res;
1603         vd->resol[2] = hair_grid_res;
1604         
1605         totres = hair_grid_size(hair_grid_res);
1606         
1607         if (vd->hair_type == TEX_VD_HAIRVELOCITY) {
1608                 depth = 4;
1609                 vd->data_type = TEX_VD_RGBA_PREMUL;
1610         }
1611         else {
1612                 depth = 1;
1613                 vd->data_type = TEX_VD_INTENSITY;
1614         }
1615         
1616         if (totres > 0) {
1617                 vd->dataset = (float *)MEM_mapallocN(sizeof(float) * depth * (totres), "hair volume texture data");
1618                 
1619                 for (i = 0; i < totres; ++i) {
1620                         switch (vd->hair_type) {
1621                                 case TEX_VD_HAIRDENSITY:
1622                                         vd->dataset[i] = hairgrid[i].density;
1623                                         break;
1624                                 
1625                                 case TEX_VD_HAIRRESTDENSITY:
1626                                         vd->dataset[i] = 0.0f; // TODO
1627                                         break;
1628                                 
1629                                 case TEX_VD_HAIRVELOCITY:
1630                                         vd->dataset[i + 0*totres] = hairgrid[i].velocity[0];
1631                                         vd->dataset[i + 1*totres] = hairgrid[i].velocity[1];
1632                                         vd->dataset[i + 2*totres] = hairgrid[i].velocity[2];
1633                                         vd->dataset[i + 3*totres] = len_v3(hairgrid[i].velocity);
1634                                         break;
1635                                 
1636                                 case TEX_VD_HAIRENERGY:
1637                                         vd->dataset[i] = 0.0f; // TODO
1638                                         break;
1639                         }
1640                 }
1641         }
1642         else {
1643                 vd->dataset = NULL;
1644         }
1645         
1646         MEM_freeN(hairgrid);
1647 //      MEM_freeN(collgrid);
1648         
1649         return true;
1650 #else
1651         return false; // XXX TODO
1652 #endif
1653 }
1654
1655 /* ================================ */
1656
1657 #endif /* IMPLICIT_SOLVER_EIGEN */