Fix T56595: Hair Dynamics stop working after saving new file
[blender.git] / source / blender / blenkernel / intern / cloth.c
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  * Contributor(s): Daniel Genrich
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 /** \file blender/blenkernel/intern/cloth.c
27  *  \ingroup bke
28  */
29
30
31 #include "MEM_guardedalloc.h"
32
33 #include "DNA_cloth_types.h"
34 #include "DNA_scene_types.h"
35 #include "DNA_object_types.h"
36 #include "DNA_meshdata_types.h"
37
38 #include "BLI_utildefines.h"
39 #include "BLI_math.h"
40 #include "BLI_edgehash.h"
41 #include "BLI_linklist.h"
42
43 #include "BKE_cdderivedmesh.h"
44 #include "BKE_cloth.h"
45 #include "BKE_effect.h"
46 #include "BKE_global.h"
47 #include "BKE_modifier.h"
48 #include "BKE_pointcache.h"
49
50 #include "BPH_mass_spring.h"
51
52 // #include "PIL_time.h"  /* timing for debug prints */
53
54 /* ********** cloth engine ******* */
55 /* Prototypes for internal functions.
56  */
57 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, float (*vertexCos)[3]);
58 static void cloth_from_mesh ( ClothModifierData *clmd, DerivedMesh *dm );
59 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float framenr, int first);
60 static void cloth_update_springs( ClothModifierData *clmd );
61 static void cloth_update_verts( Object *ob, ClothModifierData *clmd, DerivedMesh *dm );
62 static void cloth_update_spring_lengths( ClothModifierData *clmd, DerivedMesh *dm );
63 static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm );
64 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm );
65
66 /******************************************************************************
67  *
68  * External interface called by modifier.c clothModifier functions.
69  *
70  ******************************************************************************/
71 /**
72  * cloth_init - creates a new cloth simulation.
73  *
74  * 1. create object
75  * 2. fill object with standard values or with the GUI settings if given
76  */
77 void cloth_init(ClothModifierData *clmd )
78 {
79         /* Initialize our new data structure to reasonable values. */
80         clmd->sim_parms->gravity[0] = 0.0;
81         clmd->sim_parms->gravity[1] = 0.0;
82         clmd->sim_parms->gravity[2] = -9.81;
83         clmd->sim_parms->structural = 15.0;
84         clmd->sim_parms->max_struct = 15.0;
85         clmd->sim_parms->shear = 15.0;
86         clmd->sim_parms->bending = 0.5;
87         clmd->sim_parms->max_bend = 0.5;
88         clmd->sim_parms->bending_damping = 0.5;
89         clmd->sim_parms->Cdis = 5.0;
90         clmd->sim_parms->Cvi = 1.0;
91         clmd->sim_parms->mass = 0.3f;
92         clmd->sim_parms->stepsPerFrame = 5;
93         clmd->sim_parms->flags = 0;
94         clmd->sim_parms->solver_type = 0;
95         clmd->sim_parms->maxspringlen = 10;
96         clmd->sim_parms->vgroup_mass = 0;
97         clmd->sim_parms->vgroup_shrink = 0;
98         clmd->sim_parms->shrink_min = 0.0f; /* min amount the fabric will shrink by 0.0 = no shrinking, 1.0 = shrink to nothing*/
99         clmd->sim_parms->avg_spring_len = 0.0;
100         clmd->sim_parms->presets = 2; /* cotton as start setting */
101         clmd->sim_parms->timescale = 1.0f; /* speed factor, describes how fast cloth moves */
102         clmd->sim_parms->time_scale = 1.0f; /* multiplies cloth speed */
103         clmd->sim_parms->reset = 0;
104         clmd->sim_parms->vel_damping = 1.0f; /* 1.0 = no damping, 0.0 = fully dampened */
105
106         clmd->coll_parms->self_friction = 5.0;
107         clmd->coll_parms->friction = 5.0;
108         clmd->coll_parms->loop_count = 2;
109         clmd->coll_parms->epsilon = 0.015f;
110         clmd->coll_parms->flags = CLOTH_COLLSETTINGS_FLAG_ENABLED;
111         clmd->coll_parms->collision_list = NULL;
112         clmd->coll_parms->self_loop_count = 1.0;
113         clmd->coll_parms->selfepsilon = 0.75;
114         clmd->coll_parms->vgroup_selfcol = 0;
115
116         /* These defaults are copied from softbody.c's
117          * softbody_calc_forces() function.
118          */
119         clmd->sim_parms->eff_force_scale = 1000.0;
120         clmd->sim_parms->eff_wind_scale = 250.0;
121
122         // also from softbodies
123         clmd->sim_parms->maxgoal = 1.0f;
124         clmd->sim_parms->mingoal = 0.0f;
125         clmd->sim_parms->defgoal = 0.0f;
126         clmd->sim_parms->goalspring = 1.0f;
127         clmd->sim_parms->goalfrict = 0.0f;
128         clmd->sim_parms->velocity_smooth = 0.0f;
129
130         clmd->sim_parms->voxel_cell_size = 0.1f;
131
132         if (!clmd->sim_parms->effector_weights)
133                 clmd->sim_parms->effector_weights = BKE_effector_add_weights(NULL);
134
135         if (clmd->point_cache)
136                 clmd->point_cache->step = 1;
137 }
138
139 static BVHTree *bvhselftree_build_from_cloth (ClothModifierData *clmd, float epsilon)
140 {
141         unsigned int i;
142         BVHTree *bvhtree;
143         Cloth *cloth;
144         ClothVertex *verts;
145
146         if (!clmd)
147                 return NULL;
148
149         cloth = clmd->clothObject;
150
151         if (!cloth)
152                 return NULL;
153
154         verts = cloth->verts;
155
156         /* in the moment, return zero if no faces there */
157         if (!cloth->mvert_num)
158                 return NULL;
159
160         /* create quadtree with k=26 */
161         bvhtree = BLI_bvhtree_new(cloth->mvert_num, epsilon, 4, 6);
162
163         /* fill tree */
164         for (i = 0; i < cloth->mvert_num; i++, verts++) {
165                 const float *co;
166                 co = verts->xold;
167
168                 BLI_bvhtree_insert(bvhtree, i, co, 1);
169         }
170
171         /* balance tree */
172         BLI_bvhtree_balance(bvhtree);
173
174         return bvhtree;
175 }
176
177 static BVHTree *bvhtree_build_from_cloth (ClothModifierData *clmd, float epsilon)
178 {
179         unsigned int i;
180         BVHTree *bvhtree;
181         Cloth *cloth;
182         ClothVertex *verts;
183         const MVertTri *vt;
184
185         if (!clmd)
186                 return NULL;
187
188         cloth = clmd->clothObject;
189
190         if (!cloth)
191                 return NULL;
192
193         verts = cloth->verts;
194         vt = cloth->tri;
195
196         /* in the moment, return zero if no faces there */
197         if (!cloth->tri_num)
198                 return NULL;
199
200         /* create quadtree with k=26 */
201         bvhtree = BLI_bvhtree_new(cloth->tri_num, epsilon, 4, 26);
202
203         /* fill tree */
204         for (i = 0; i < cloth->tri_num; i++, vt++) {
205                 float co[3][3];
206
207                 copy_v3_v3(co[0], verts[vt->tri[0]].xold);
208                 copy_v3_v3(co[1], verts[vt->tri[1]].xold);
209                 copy_v3_v3(co[2], verts[vt->tri[2]].xold);
210
211                 BLI_bvhtree_insert(bvhtree, i, co[0], 3);
212         }
213
214         /* balance tree */
215         BLI_bvhtree_balance(bvhtree);
216
217         return bvhtree;
218 }
219
220 void bvhtree_update_from_cloth(ClothModifierData *clmd, bool moving)
221 {
222         unsigned int i = 0;
223         Cloth *cloth = clmd->clothObject;
224         BVHTree *bvhtree = cloth->bvhtree;
225         ClothVertex *verts = cloth->verts;
226         const MVertTri *vt;
227
228         if (!bvhtree)
229                 return;
230
231         vt = cloth->tri;
232
233         /* update vertex position in bvh tree */
234         if (verts && vt) {
235                 for (i = 0; i < cloth->tri_num; i++, vt++) {
236                         float co[3][3], co_moving[3][3];
237                         bool ret;
238
239                         copy_v3_v3(co[0], verts[vt->tri[0]].txold);
240                         copy_v3_v3(co[1], verts[vt->tri[1]].txold);
241                         copy_v3_v3(co[2], verts[vt->tri[2]].txold);
242
243                         /* copy new locations into array */
244                         if (moving) {
245                                 /* update moving positions */
246                                 copy_v3_v3(co_moving[0], verts[vt->tri[0]].tx);
247                                 copy_v3_v3(co_moving[1], verts[vt->tri[1]].tx);
248                                 copy_v3_v3(co_moving[2], verts[vt->tri[2]].tx);
249
250                                 ret = BLI_bvhtree_update_node(bvhtree, i, co[0], co_moving[0], 3);
251                         }
252                         else {
253                                 ret = BLI_bvhtree_update_node(bvhtree, i, co[0], NULL, 3);
254                         }
255
256                         /* check if tree is already full */
257                         if (ret == false) {
258                                 break;
259                         }
260                 }
261
262                 BLI_bvhtree_update_tree(bvhtree);
263         }
264 }
265
266 void bvhselftree_update_from_cloth(ClothModifierData *clmd, bool moving)
267 {
268         unsigned int i = 0;
269         Cloth *cloth = clmd->clothObject;
270         BVHTree *bvhtree = cloth->bvhselftree;
271         ClothVertex *verts = cloth->verts;
272         const MVertTri *vt;
273
274         if (!bvhtree)
275                 return;
276
277         vt = cloth->tri;
278
279         /* update vertex position in bvh tree */
280         if (verts && vt) {
281                 for (i = 0; i < cloth->mvert_num; i++, verts++) {
282                         const float *co, *co_moving;
283                         bool ret;
284
285                         co = verts->txold;
286
287                         /* copy new locations into array */
288                         if (moving) {
289                                 /* update moving positions */
290                                 co_moving = verts->tx;
291                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, co_moving, 1);
292                         }
293                         else {
294                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, NULL, 1);
295                         }
296
297                         /* check if tree is already full */
298                         if (ret == false) {
299                                 break;
300                         }
301                 }
302
303                 BLI_bvhtree_update_tree(bvhtree);
304         }
305 }
306
307 void cloth_clear_cache(Object *ob, ClothModifierData *clmd, float framenr)
308 {
309         PTCacheID pid;
310
311         BKE_ptcache_id_from_cloth(&pid, ob, clmd);
312
313         // don't do anything as long as we're in editmode!
314         if (pid.cache->edit && ob->mode & OB_MODE_PARTICLE_EDIT)
315                 return;
316
317         BKE_ptcache_id_clear(&pid, PTCACHE_CLEAR_AFTER, framenr);
318 }
319
320 static int do_init_cloth(Object *ob, ClothModifierData *clmd, DerivedMesh *result, int framenr)
321 {
322         PointCache *cache;
323
324         cache= clmd->point_cache;
325
326         /* initialize simulation data if it didn't exist already */
327         if (clmd->clothObject == NULL) {
328                 if (!cloth_from_object(ob, clmd, result, framenr, 1)) {
329                         BKE_ptcache_invalidate(cache);
330                         modifier_setError(&(clmd->modifier), "Can't initialize cloth");
331                         return 0;
332                 }
333
334                 if (clmd->clothObject == NULL) {
335                         BKE_ptcache_invalidate(cache);
336                         modifier_setError(&(clmd->modifier), "Null cloth object");
337                         return 0;
338                 }
339
340                 BKE_cloth_solver_set_positions(clmd);
341
342                 clmd->clothObject->last_frame= MINFRAME-1;
343         }
344
345         return 1;
346 }
347
348 static int do_step_cloth(Object *ob, ClothModifierData *clmd, DerivedMesh *result, int framenr)
349 {
350         ClothVertex *verts = NULL;
351         Cloth *cloth;
352         ListBase *effectors = NULL;
353         MVert *mvert;
354         unsigned int i = 0;
355         int ret = 0;
356
357         /* simulate 1 frame forward */
358         cloth = clmd->clothObject;
359         verts = cloth->verts;
360         mvert = result->getVertArray(result);
361
362         /* force any pinned verts to their constrained location. */
363         for (i = 0; i < clmd->clothObject->mvert_num; i++, verts++) {
364                 /* save the previous position. */
365                 copy_v3_v3(verts->xold, verts->xconst);
366                 copy_v3_v3(verts->txold, verts->x);
367
368                 /* Get the current position. */
369                 copy_v3_v3(verts->xconst, mvert[i].co);
370                 mul_m4_v3(ob->obmat, verts->xconst);
371         }
372
373         effectors = pdInitEffectors(clmd->scene, ob, NULL, clmd->sim_parms->effector_weights, true);
374
375         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_DYNAMIC_BASEMESH )
376                 cloth_update_verts ( ob, clmd, result );
377
378         /* Support for dynamic vertex groups, changing from frame to frame */
379         cloth_apply_vgroup ( clmd, result );
380
381         if ( clmd->sim_parms->flags & (CLOTH_SIMSETTINGS_FLAG_SEW | CLOTH_SIMSETTINGS_FLAG_DYNAMIC_BASEMESH) )
382                 cloth_update_spring_lengths ( clmd, result );
383
384         cloth_update_springs( clmd );
385
386         // TIMEIT_START(cloth_step)
387
388         /* call the solver. */
389         ret = BPH_cloth_solve(ob, framenr, clmd, effectors);
390
391         // TIMEIT_END(cloth_step)
392
393         pdEndEffectors(&effectors);
394
395         // printf ( "%f\n", ( float ) tval() );
396
397         return ret;
398 }
399
400 /************************************************
401  * clothModifier_do - main simulation function
402  ************************************************/
403 void clothModifier_do(ClothModifierData *clmd, Scene *scene, Object *ob, DerivedMesh *dm, float (*vertexCos)[3])
404 {
405         PointCache *cache;
406         PTCacheID pid;
407         float timescale;
408         int framenr, startframe, endframe;
409         int cache_result;
410
411         clmd->scene= scene;     /* nice to pass on later :) */
412         framenr= (int)scene->r.cfra;
413         cache= clmd->point_cache;
414
415         BKE_ptcache_id_from_cloth(&pid, ob, clmd);
416         BKE_ptcache_id_time(&pid, scene, framenr, &startframe, &endframe, &timescale);
417         clmd->sim_parms->timescale= timescale * clmd->sim_parms->time_scale;
418
419         if (clmd->sim_parms->reset || (clmd->clothObject && dm->getNumVerts(dm) != clmd->clothObject->mvert_num)) {
420                 clmd->sim_parms->reset = 0;
421                 cache->flag |= PTCACHE_OUTDATED;
422                 BKE_ptcache_id_reset(scene, &pid, PTCACHE_RESET_OUTDATED);
423                 BKE_ptcache_validate(cache, 0);
424                 cache->last_exact= 0;
425                 cache->flag &= ~PTCACHE_REDO_NEEDED;
426         }
427
428         // unused in the moment, calculated separately in implicit.c
429         clmd->sim_parms->dt = clmd->sim_parms->timescale / clmd->sim_parms->stepsPerFrame;
430
431         /* simulation is only active during a specific period */
432         if (framenr < startframe) {
433                 BKE_ptcache_invalidate(cache);
434                 return;
435         }
436         else if (framenr > endframe) {
437                 framenr= endframe;
438         }
439
440         /* initialize simulation data if it didn't exist already */
441         if (!do_init_cloth(ob, clmd, dm, framenr))
442                 return;
443
444         if (framenr == startframe) {
445                 BKE_ptcache_id_reset(scene, &pid, PTCACHE_RESET_OUTDATED);
446                 do_init_cloth(ob, clmd, dm, framenr);
447                 BKE_ptcache_validate(cache, framenr);
448                 cache->flag &= ~PTCACHE_REDO_NEEDED;
449                 clmd->clothObject->last_frame= framenr;
450                 return;
451         }
452
453         /* try to read from cache */
454         bool can_simulate = (framenr == clmd->clothObject->last_frame+1) && !(cache->flag & PTCACHE_BAKED);
455
456         cache_result = BKE_ptcache_read(&pid, (float)framenr+scene->r.subframe, can_simulate);
457
458         if (cache_result == PTCACHE_READ_EXACT || cache_result == PTCACHE_READ_INTERPOLATED ||
459             (!can_simulate && cache_result == PTCACHE_READ_OLD))
460         {
461                 BKE_cloth_solver_set_positions(clmd);
462                 cloth_to_object (ob, clmd, vertexCos);
463
464                 BKE_ptcache_validate(cache, framenr);
465
466                 if (cache_result == PTCACHE_READ_INTERPOLATED && cache->flag & PTCACHE_REDO_NEEDED)
467                         BKE_ptcache_write(&pid, framenr);
468
469                 clmd->clothObject->last_frame= framenr;
470
471                 return;
472         }
473         else if (cache_result==PTCACHE_READ_OLD) {
474                 BKE_cloth_solver_set_positions(clmd);
475         }
476         else if ( /*ob->id.lib ||*/ (cache->flag & PTCACHE_BAKED)) { /* 2.4x disabled lib, but this can be used in some cases, testing further - campbell */
477                 /* if baked and nothing in cache, do nothing */
478                 BKE_ptcache_invalidate(cache);
479                 return;
480         }
481
482         if (!can_simulate)
483                 return;
484
485         /* if on second frame, write cache for first frame */
486         if (cache->simframe == startframe && (cache->flag & PTCACHE_OUTDATED || cache->last_exact==0))
487                 BKE_ptcache_write(&pid, startframe);
488
489         clmd->sim_parms->timescale *= framenr - cache->simframe;
490
491         /* do simulation */
492         BKE_ptcache_validate(cache, framenr);
493
494         if (!do_step_cloth(ob, clmd, dm, framenr)) {
495                 BKE_ptcache_invalidate(cache);
496         }
497         else
498                 BKE_ptcache_write(&pid, framenr);
499
500         cloth_to_object (ob, clmd, vertexCos);
501         clmd->clothObject->last_frame= framenr;
502 }
503
504 /* frees all */
505 void cloth_free_modifier(ClothModifierData *clmd )
506 {
507         Cloth   *cloth = NULL;
508
509         if ( !clmd )
510                 return;
511
512         cloth = clmd->clothObject;
513
514
515         if ( cloth ) {
516                 BPH_cloth_solver_free(clmd);
517
518                 // Free the verts.
519                 if ( cloth->verts != NULL )
520                         MEM_freeN ( cloth->verts );
521
522                 cloth->verts = NULL;
523                 cloth->mvert_num = 0;
524
525                 // Free the springs.
526                 if ( cloth->springs != NULL ) {
527                         LinkNode *search = cloth->springs;
528                         while (search) {
529                                 ClothSpring *spring = search->link;
530
531                                 MEM_freeN ( spring );
532                                 search = search->next;
533                         }
534                         BLI_linklist_free(cloth->springs, NULL);
535
536                         cloth->springs = NULL;
537                 }
538
539                 cloth->springs = NULL;
540                 cloth->numsprings = 0;
541
542                 // free BVH collision tree
543                 if ( cloth->bvhtree )
544                         BLI_bvhtree_free ( cloth->bvhtree );
545
546                 if ( cloth->bvhselftree )
547                         BLI_bvhtree_free ( cloth->bvhselftree );
548
549                 // we save our faces for collision objects
550                 if (cloth->tri)
551                         MEM_freeN(cloth->tri);
552
553                 if (cloth->edgeset)
554                         BLI_edgeset_free(cloth->edgeset);
555
556 #if 0
557                 if (clmd->clothObject->facemarks) {
558                         MEM_freeN(clmd->clothObject->facemarks);
559                 }
560 #endif
561                 MEM_freeN ( cloth );
562                 clmd->clothObject = NULL;
563         }
564 }
565
566 /* frees all */
567 void cloth_free_modifier_extern(ClothModifierData *clmd )
568 {
569         Cloth   *cloth = NULL;
570         if (G.debug_value > 0)
571                 printf("cloth_free_modifier_extern\n");
572
573         if ( !clmd )
574                 return;
575
576         cloth = clmd->clothObject;
577
578         if ( cloth ) {
579                 if (G.debug_value > 0)
580                         printf("cloth_free_modifier_extern in\n");
581
582                 BPH_cloth_solver_free(clmd);
583
584                 // Free the verts.
585                 if ( cloth->verts != NULL )
586                         MEM_freeN ( cloth->verts );
587
588                 cloth->verts = NULL;
589                 cloth->mvert_num = 0;
590
591                 // Free the springs.
592                 if ( cloth->springs != NULL ) {
593                         LinkNode *search = cloth->springs;
594                         while (search) {
595                                 ClothSpring *spring = search->link;
596
597                                 MEM_freeN ( spring );
598                                 search = search->next;
599                         }
600                         BLI_linklist_free(cloth->springs, NULL);
601
602                         cloth->springs = NULL;
603                 }
604
605                 cloth->springs = NULL;
606                 cloth->numsprings = 0;
607
608                 // free BVH collision tree
609                 if ( cloth->bvhtree )
610                         BLI_bvhtree_free ( cloth->bvhtree );
611
612                 if ( cloth->bvhselftree )
613                         BLI_bvhtree_free ( cloth->bvhselftree );
614
615                 // we save our faces for collision objects
616                 if (cloth->tri)
617                         MEM_freeN(cloth->tri);
618
619                 if (cloth->edgeset)
620                         BLI_edgeset_free(cloth->edgeset);
621
622
623 #if 0
624                 if (clmd->clothObject->facemarks) {
625                         MEM_freeN(clmd->clothObject->facemarks);
626                 }
627 #endif
628                 MEM_freeN ( cloth );
629                 clmd->clothObject = NULL;
630         }
631 }
632
633 /******************************************************************************
634  *
635  * Internal functions.
636  *
637  ******************************************************************************/
638
639 /**
640  * cloth_to_object - copies the deformed vertices to the object.
641  *
642  **/
643 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, float (*vertexCos)[3])
644 {
645         unsigned int i = 0;
646         Cloth *cloth = clmd->clothObject;
647
648         if (clmd->clothObject) {
649                 /* inverse matrix is not uptodate... */
650                 invert_m4_m4(ob->imat, ob->obmat);
651
652                 for (i = 0; i < cloth->mvert_num; i++) {
653                         copy_v3_v3 (vertexCos[i], cloth->verts[i].x);
654                         mul_m4_v3(ob->imat, vertexCos[i]);      /* cloth is in global coords */
655                 }
656         }
657 }
658
659
660 int cloth_uses_vgroup(ClothModifierData *clmd)
661 {
662         return (((clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING ) ||
663                 (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL ) ||
664                 (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW) ||
665                 (clmd->coll_parms->flags & CLOTH_COLLSETTINGS_FLAG_SELF)) &&
666                 ((clmd->sim_parms->vgroup_mass>0) ||
667                 (clmd->sim_parms->vgroup_struct>0)||
668                 (clmd->sim_parms->vgroup_bend>0)  ||
669                 (clmd->sim_parms->vgroup_shrink>0) ||
670                 (clmd->coll_parms->vgroup_selfcol>0)));
671 }
672
673 /**
674  * cloth_apply_vgroup - applies a vertex group as specified by type
675  *
676  **/
677 /* can be optimized to do all groups in one loop */
678 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm )
679 {
680         int i = 0;
681         int j = 0;
682         MDeformVert *dvert = NULL;
683         Cloth *clothObj = NULL;
684         int mvert_num;
685         /* float goalfac = 0; */ /* UNUSED */
686         ClothVertex *verts = NULL;
687
688         if (!clmd || !dm) return;
689
690         clothObj = clmd->clothObject;
691
692         mvert_num = dm->getNumVerts(dm);
693
694         verts = clothObj->verts;
695
696         if (cloth_uses_vgroup(clmd)) {
697                 for (i = 0; i < mvert_num; i++, verts++) {
698
699                         /* Reset Goal values to standard */
700                         if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )
701                                 verts->goal= clmd->sim_parms->defgoal;
702                         else
703                                 verts->goal= 0.0f;
704
705                         /* Compute base cloth shrink weight */
706                         verts->shrink_factor = 0.0f;
707
708                         /* Reset vertex flags */
709                         verts->flags &= ~CLOTH_VERT_FLAG_PINNED;
710                         verts->flags &= ~CLOTH_VERT_FLAG_NOSELFCOLL;
711
712                         dvert = dm->getVertData ( dm, i, CD_MDEFORMVERT );
713                         if ( dvert ) {
714                                 for ( j = 0; j < dvert->totweight; j++ ) {
715                                         if (( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_mass-1)) && (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )) {
716                                                 verts->goal = dvert->dw [j].weight;
717
718                                                 /* goalfac= 1.0f; */ /* UNUSED */
719
720                                                 // Kicking goal factor to simplify things...who uses that anyway?
721                                                 // ABS ( clmd->sim_parms->maxgoal - clmd->sim_parms->mingoal );
722
723                                                 verts->goal  = pow4f(verts->goal);
724                                                 if ( verts->goal >= SOFTGOALSNAP )
725                                                         verts->flags |= CLOTH_VERT_FLAG_PINNED;
726                                         }
727
728                                         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING ) {
729                                                 if ( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_struct-1)) {
730                                                         verts->struct_stiff = dvert->dw [j].weight;
731                                                         verts->shear_stiff = dvert->dw [j].weight;
732                                                 }
733
734                                                 if ( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_bend-1)) {
735                                                         verts->bend_stiff = dvert->dw [j].weight;
736                                                 }
737                                         }
738
739                                         if (clmd->coll_parms->flags & CLOTH_COLLSETTINGS_FLAG_SELF ) {
740                                                 if ( dvert->dw[j].def_nr == (clmd->coll_parms->vgroup_selfcol-1)) {
741                                                         if (dvert->dw [j].weight > 0.0f) {
742                                                                 verts->flags |= CLOTH_VERT_FLAG_NOSELFCOLL;
743                                                         }
744                                                 }
745                                         }
746                                         if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW ) {
747                                                 if (clmd->sim_parms->vgroup_shrink > 0) {
748                                                         if (dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_shrink - 1)) {
749                                                                 /* used for linear interpolation between min and max shrink factor based on weight */
750                                                                 verts->shrink_factor = dvert->dw[j].weight;
751                                                         }
752                                                 }
753                                         }
754                                 }
755                         }
756                 }
757         }
758 }
759
760 static float cloth_shrink_factor(ClothModifierData *clmd, ClothVertex *verts, int i1, int i2)
761 {
762         if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW ) {
763                 /* linear interpolation between min and max shrink factor based on weight */
764                 float base = 1.0f - clmd->sim_parms->shrink_min;
765                 float delta = clmd->sim_parms->shrink_min - clmd->sim_parms->shrink_max;
766
767                 float k1 = base + delta * verts[i1].shrink_factor;
768                 float k2 = base + delta * verts[i2].shrink_factor;
769
770                 /* Use geometrical mean to average two factors since it behaves better
771                    for diagonals when a rectangle transforms into a trapezoid. */
772                 return sqrtf(k1 * k2);
773         }
774         else
775                 return 1.0f;
776 }
777
778 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float UNUSED(framenr), int first)
779 {
780         int i = 0;
781         MVert *mvert = NULL;
782         ClothVertex *verts = NULL;
783         float (*shapekey_rest)[3] = NULL;
784         float tnull[3] = {0, 0, 0};
785         Cloth *cloth = NULL;
786         float maxdist = 0;
787
788         // If we have a clothObject, free it.
789         if ( clmd->clothObject != NULL ) {
790                 cloth_free_modifier ( clmd );
791                 if (G.debug_value > 0)
792                         printf("cloth_free_modifier cloth_from_object\n");
793         }
794
795         // Allocate a new cloth object.
796         clmd->clothObject = MEM_callocN ( sizeof ( Cloth ), "cloth" );
797         if ( clmd->clothObject ) {
798                 clmd->clothObject->old_solver_type = 255;
799                 // clmd->clothObject->old_collision_type = 255;
800                 cloth = clmd->clothObject;
801                 clmd->clothObject->edgeset = NULL;
802         }
803         else if (!clmd->clothObject) {
804                 modifier_setError(&(clmd->modifier), "Out of memory on allocating clmd->clothObject");
805                 return 0;
806         }
807
808         // mesh input objects need DerivedMesh
809         if ( !dm )
810                 return 0;
811
812         cloth_from_mesh ( clmd, dm );
813
814         // create springs
815         clmd->clothObject->springs = NULL;
816         clmd->clothObject->numsprings = -1;
817
818         if ( clmd->sim_parms->shapekey_rest && !(clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_DYNAMIC_BASEMESH ) )
819                 shapekey_rest = dm->getVertDataArray ( dm, CD_CLOTH_ORCO );
820
821         mvert = dm->getVertArray (dm);
822
823         verts = clmd->clothObject->verts;
824
825         // set initial values
826         for ( i = 0; i < dm->getNumVerts(dm); i++, verts++ ) {
827                 if (first) {
828                         copy_v3_v3(verts->x, mvert[i].co);
829
830                         mul_m4_v3(ob->obmat, verts->x);
831
832                         if ( shapekey_rest ) {
833                                 copy_v3_v3(verts->xrest, shapekey_rest[i]);
834                                 mul_m4_v3(ob->obmat, verts->xrest);
835                         }
836                         else
837                                 copy_v3_v3(verts->xrest, verts->x);
838                 }
839
840                 /* no GUI interface yet */
841                 verts->mass = clmd->sim_parms->mass;
842                 verts->impulse_count = 0;
843
844                 if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )
845                         verts->goal= clmd->sim_parms->defgoal;
846                 else
847                         verts->goal= 0.0f;
848
849                 verts->shrink_factor = 0.0f;
850
851                 verts->flags = 0;
852                 copy_v3_v3 ( verts->xold, verts->x );
853                 copy_v3_v3 ( verts->xconst, verts->x );
854                 copy_v3_v3 ( verts->txold, verts->x );
855                 copy_v3_v3 ( verts->tx, verts->x );
856                 mul_v3_fl(verts->v, 0.0f);
857
858                 verts->impulse_count = 0;
859                 copy_v3_v3 ( verts->impulse, tnull );
860         }
861
862         // apply / set vertex groups
863         // has to be happen before springs are build!
864         cloth_apply_vgroup (clmd, dm);
865
866         if ( !cloth_build_springs ( clmd, dm ) ) {
867                 cloth_free_modifier ( clmd );
868                 modifier_setError(&(clmd->modifier), "Cannot build springs");
869                 printf("cloth_free_modifier cloth_build_springs\n");
870                 return 0;
871         }
872
873         // init our solver
874         BPH_cloth_solver_init(ob, clmd);
875
876         if (!first)
877                 BKE_cloth_solver_set_positions(clmd);
878
879         clmd->clothObject->bvhtree = bvhtree_build_from_cloth ( clmd, MAX2(clmd->coll_parms->epsilon, clmd->coll_parms->distance_repel) );
880
881         for (i = 0; i < dm->getNumVerts(dm); i++) {
882                 maxdist = MAX2(maxdist, clmd->coll_parms->selfepsilon* ( cloth->verts[i].avg_spring_len*2.0f));
883         }
884
885         clmd->clothObject->bvhselftree = bvhselftree_build_from_cloth ( clmd, maxdist );
886
887         return 1;
888 }
889
890 static void cloth_from_mesh ( ClothModifierData *clmd, DerivedMesh *dm )
891 {
892         const MLoop *mloop = dm->getLoopArray(dm);
893         const MLoopTri *looptri = dm->getLoopTriArray(dm);
894         const unsigned int mvert_num = dm->getNumVerts(dm);
895         const unsigned int looptri_num = dm->getNumLoopTri(dm);
896
897         /* Allocate our vertices. */
898         clmd->clothObject->mvert_num = mvert_num;
899         clmd->clothObject->verts = MEM_callocN(sizeof(ClothVertex) * clmd->clothObject->mvert_num, "clothVertex");
900         if (clmd->clothObject->verts == NULL) {
901                 cloth_free_modifier(clmd);
902                 modifier_setError(&(clmd->modifier), "Out of memory on allocating clmd->clothObject->verts");
903                 printf("cloth_free_modifier clmd->clothObject->verts\n");
904                 return;
905         }
906
907         /* save face information */
908         clmd->clothObject->tri_num = looptri_num;
909         clmd->clothObject->tri = MEM_mallocN(sizeof(MVertTri) * looptri_num, "clothLoopTris");
910         if (clmd->clothObject->tri == NULL) {
911                 cloth_free_modifier(clmd);
912                 modifier_setError(&(clmd->modifier), "Out of memory on allocating clmd->clothObject->looptri");
913                 printf("cloth_free_modifier clmd->clothObject->looptri\n");
914                 return;
915         }
916         DM_verttri_from_looptri(clmd->clothObject->tri, mloop, looptri, looptri_num);
917
918         /* Free the springs since they can't be correct if the vertices
919          * changed.
920          */
921         if ( clmd->clothObject->springs != NULL )
922                 MEM_freeN ( clmd->clothObject->springs );
923
924 }
925
926 /***************************************************************************************
927  * SPRING NETWORK BUILDING IMPLEMENTATION BEGIN
928  ***************************************************************************************/
929
930 BLI_INLINE void spring_verts_ordered_set(ClothSpring *spring, int v0, int v1)
931 {
932         if (v0 < v1) {
933                 spring->ij = v0;
934                 spring->kl = v1;
935         }
936         else {
937                 spring->ij = v1;
938                 spring->kl = v0;
939         }
940 }
941
942 static void cloth_free_edgelist(LinkNodePair *edgelist, unsigned int mvert_num)
943 {
944         if (edgelist) {
945                 unsigned int i;
946                 for (i = 0; i < mvert_num; i++) {
947                         BLI_linklist_free(edgelist[i].list, NULL);
948                 }
949
950                 MEM_freeN(edgelist);
951         }
952 }
953
954 static void cloth_free_errorsprings(Cloth *cloth, LinkNodePair *edgelist)
955 {
956         if ( cloth->springs != NULL ) {
957                 LinkNode *search = cloth->springs;
958                 while (search) {
959                         ClothSpring *spring = search->link;
960
961                         MEM_freeN ( spring );
962                         search = search->next;
963                 }
964                 BLI_linklist_free(cloth->springs, NULL);
965
966                 cloth->springs = NULL;
967         }
968
969         cloth_free_edgelist(edgelist, cloth->mvert_num);
970
971         if (cloth->edgeset) {
972                 BLI_edgeset_free(cloth->edgeset);
973                 cloth->edgeset = NULL;
974         }
975 }
976
977 static void cloth_hair_update_bending_targets(ClothModifierData *clmd)
978 {
979         Cloth *cloth = clmd->clothObject;
980         LinkNode *search = NULL;
981         float hair_frame[3][3], dir_old[3], dir_new[3];
982         int prev_mn; /* to find hair chains */
983
984         if (!clmd->hairdata)
985                 return;
986
987         /* XXX Note: we need to propagate frames from the root up,
988          * but structural hair springs are stored in reverse order.
989          * The bending springs however are then inserted in the same
990          * order as vertices again ...
991          * This messy situation can be resolved when solver data is
992          * generated directly from a dedicated hair system.
993          */
994
995         prev_mn = -1;
996         for (search = cloth->springs; search; search = search->next) {
997                 ClothSpring *spring = search->link;
998                 ClothHairData *hair_ij, *hair_kl;
999                 bool is_root = spring->kl != prev_mn;
1000
1001                 if (spring->type != CLOTH_SPRING_TYPE_BENDING_ANG) {
1002                         continue;
1003                 }
1004
1005                 hair_ij = &clmd->hairdata[spring->ij];
1006                 hair_kl = &clmd->hairdata[spring->kl];
1007                 if (is_root) {
1008                         /* initial hair frame from root orientation */
1009                         copy_m3_m3(hair_frame, hair_ij->rot);
1010                         /* surface normal is the initial direction,
1011                          * parallel transport then keeps it aligned to the hair direction
1012                          */
1013                         copy_v3_v3(dir_new, hair_frame[2]);
1014                 }
1015
1016                 copy_v3_v3(dir_old, dir_new);
1017                 sub_v3_v3v3(dir_new, cloth->verts[spring->mn].x, cloth->verts[spring->kl].x);
1018                 normalize_v3(dir_new);
1019
1020 #if 0
1021                 if (clmd->debug_data && (spring->ij == 0 || spring->ij == 1)) {
1022                         float a[3], b[3];
1023
1024                         copy_v3_v3(a, cloth->verts[spring->kl].x);
1025 //                      BKE_sim_debug_data_add_dot(clmd->debug_data, cloth_vert ? cloth_vert->x : key->co, 1, 1, 0, "frames", 8246, p, k);
1026
1027                         mul_v3_v3fl(b, hair_frame[0], clmd->sim_parms->avg_spring_len);
1028                         BKE_sim_debug_data_add_vector(clmd->debug_data, a, b, 1, 0, 0, "frames", 8247, spring->kl, spring->mn);
1029
1030                         mul_v3_v3fl(b, hair_frame[1], clmd->sim_parms->avg_spring_len);
1031                         BKE_sim_debug_data_add_vector(clmd->debug_data, a, b, 0, 1, 0, "frames", 8248, spring->kl, spring->mn);
1032
1033                         mul_v3_v3fl(b, hair_frame[2], clmd->sim_parms->avg_spring_len);
1034                         BKE_sim_debug_data_add_vector(clmd->debug_data, a, b, 0, 0, 1, "frames", 8249, spring->kl, spring->mn);
1035                 }
1036 #endif
1037
1038                 /* get local targets for kl/mn vertices by putting rest targets into the current frame,
1039                  * then multiply with the rest length to get the actual goals
1040                  */
1041
1042                 mul_v3_m3v3(spring->target, hair_frame, hair_kl->rest_target);
1043                 mul_v3_fl(spring->target, spring->restlen);
1044
1045                 /* move frame to next hair segment */
1046                 cloth_parallel_transport_hair_frame(hair_frame, dir_old, dir_new);
1047
1048                 prev_mn = spring->mn;
1049         }
1050 }
1051
1052 static void cloth_hair_update_bending_rest_targets(ClothModifierData *clmd)
1053 {
1054         Cloth *cloth = clmd->clothObject;
1055         LinkNode *search = NULL;
1056         float hair_frame[3][3], dir_old[3], dir_new[3];
1057         int prev_mn; /* to find hair roots */
1058
1059         if (!clmd->hairdata)
1060                 return;
1061
1062         /* XXX Note: we need to propagate frames from the root up,
1063          * but structural hair springs are stored in reverse order.
1064          * The bending springs however are then inserted in the same
1065          * order as vertices again ...
1066          * This messy situation can be resolved when solver data is
1067          * generated directly from a dedicated hair system.
1068          */
1069
1070         prev_mn = -1;
1071         for (search = cloth->springs; search; search = search->next) {
1072                 ClothSpring *spring = search->link;
1073                 ClothHairData *hair_ij, *hair_kl;
1074                 bool is_root = spring->kl != prev_mn;
1075
1076                 if (spring->type != CLOTH_SPRING_TYPE_BENDING_ANG) {
1077                         continue;
1078                 }
1079
1080                 hair_ij = &clmd->hairdata[spring->ij];
1081                 hair_kl = &clmd->hairdata[spring->kl];
1082                 if (is_root) {
1083                         /* initial hair frame from root orientation */
1084                         copy_m3_m3(hair_frame, hair_ij->rot);
1085                         /* surface normal is the initial direction,
1086                          * parallel transport then keeps it aligned to the hair direction
1087                          */
1088                         copy_v3_v3(dir_new, hair_frame[2]);
1089                 }
1090
1091                 copy_v3_v3(dir_old, dir_new);
1092                 sub_v3_v3v3(dir_new, cloth->verts[spring->mn].xrest, cloth->verts[spring->kl].xrest);
1093                 normalize_v3(dir_new);
1094
1095                 /* dir expressed in the hair frame defines the rest target direction */
1096                 copy_v3_v3(hair_kl->rest_target, dir_new);
1097                 mul_transposed_m3_v3(hair_frame, hair_kl->rest_target);
1098
1099                 /* move frame to next hair segment */
1100                 cloth_parallel_transport_hair_frame(hair_frame, dir_old, dir_new);
1101
1102                 prev_mn = spring->mn;
1103         }
1104 }
1105
1106 /* update stiffness if vertex group values are changing from frame to frame */
1107 static void cloth_update_springs( ClothModifierData *clmd )
1108 {
1109         Cloth *cloth = clmd->clothObject;
1110         LinkNode *search = NULL;
1111
1112         search = cloth->springs;
1113         while (search) {
1114                 ClothSpring *spring = search->link;
1115
1116                 spring->stiffness = 0.0f;
1117
1118                 if (spring->type == CLOTH_SPRING_TYPE_STRUCTURAL) {
1119                         spring->stiffness = (cloth->verts[spring->kl].struct_stiff + cloth->verts[spring->ij].struct_stiff) / 2.0f;
1120                 }
1121                 else if (spring->type == CLOTH_SPRING_TYPE_SHEAR) {
1122                         spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0f;
1123                 }
1124                 else if (spring->type == CLOTH_SPRING_TYPE_BENDING) {
1125                         spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0f;
1126                 }
1127                 else if (spring->type == CLOTH_SPRING_TYPE_BENDING_ANG) {
1128                         ClothVertex *v1 = &cloth->verts[spring->ij];
1129                         ClothVertex *v2 = &cloth->verts[spring->kl];
1130                         if (clmd->hairdata) {
1131                                 /* copy extra hair data to generic cloth vertices */
1132                                 v1->bend_stiff = clmd->hairdata[spring->ij].bending_stiffness;
1133                                 v2->bend_stiff = clmd->hairdata[spring->kl].bending_stiffness;
1134                         }
1135                         spring->stiffness = (v1->bend_stiff + v2->bend_stiff) / 2.0f;
1136                 }
1137                 else if (spring->type == CLOTH_SPRING_TYPE_GOAL) {
1138                         /* Warning: Appending NEW goal springs does not work because implicit solver would need reset! */
1139
1140                         /* Activate / Deactivate existing springs */
1141                         if ((!(cloth->verts[spring->ij].flags & CLOTH_VERT_FLAG_PINNED)) &&
1142                             (cloth->verts[spring->ij].goal > ALMOST_ZERO))
1143                         {
1144                                 spring->flags &= ~CLOTH_SPRING_FLAG_DEACTIVATE;
1145                         }
1146                         else {
1147                                 spring->flags |= CLOTH_SPRING_FLAG_DEACTIVATE;
1148                         }
1149                 }
1150
1151                 search = search->next;
1152         }
1153
1154         cloth_hair_update_bending_targets(clmd);
1155 }
1156
1157 /* Update rest verts, for dynamically deformable cloth */
1158 static void cloth_update_verts( Object *ob, ClothModifierData *clmd, DerivedMesh *dm )
1159 {
1160         unsigned int i = 0;
1161         MVert *mvert = dm->getVertArray (dm);
1162         ClothVertex *verts = clmd->clothObject->verts;
1163
1164         /* vertex count is already ensured to match */
1165         for ( i = 0; i < dm->getNumVerts(dm); i++, verts++ ) {
1166                 copy_v3_v3(verts->xrest, mvert[i].co);
1167                 mul_m4_v3(ob->obmat, verts->xrest);
1168         }
1169 }
1170
1171 /* Update spring rest lenght, for dynamically deformable cloth */
1172 static void cloth_update_spring_lengths( ClothModifierData *clmd, DerivedMesh *dm )
1173 {
1174         Cloth *cloth = clmd->clothObject;
1175         LinkNode *search = cloth->springs;
1176         unsigned int struct_springs = 0;
1177         unsigned int i = 0;
1178         unsigned int mvert_num = (unsigned int)dm->getNumVerts(dm);
1179         float shrink_factor;
1180
1181         clmd->sim_parms->avg_spring_len = 0.0f;
1182
1183         for (i = 0; i < mvert_num; i++) {
1184                 cloth->verts[i].avg_spring_len = 0.0f;
1185         }
1186
1187         while (search) {
1188                 ClothSpring *spring = search->link;
1189
1190                 if ( spring->type != CLOTH_SPRING_TYPE_SEWING ) {
1191                         if ( spring->type & (CLOTH_SPRING_TYPE_STRUCTURAL | CLOTH_SPRING_TYPE_SHEAR | CLOTH_SPRING_TYPE_BENDING) )
1192                                 shrink_factor = cloth_shrink_factor(clmd, cloth->verts, spring->ij, spring->kl);
1193                         else
1194                                 shrink_factor = 1.0f;
1195
1196                         spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest) * shrink_factor;
1197                 }
1198
1199                 if ( spring->type == CLOTH_SPRING_TYPE_STRUCTURAL ) {
1200                         clmd->sim_parms->avg_spring_len += spring->restlen;
1201                         cloth->verts[spring->ij].avg_spring_len += spring->restlen;
1202                         cloth->verts[spring->kl].avg_spring_len += spring->restlen;
1203                         struct_springs++;
1204                 }
1205
1206                 search = search->next;
1207         }
1208
1209         if (struct_springs > 0)
1210                 clmd->sim_parms->avg_spring_len /= struct_springs;
1211
1212         for (i = 0; i < mvert_num; i++) {
1213                 if (cloth->verts[i].spring_count > 0)
1214                         cloth->verts[i].avg_spring_len = cloth->verts[i].avg_spring_len * 0.49f / ((float)cloth->verts[i].spring_count);
1215         }
1216 }
1217
1218 BLI_INLINE void cross_identity_v3(float r[3][3], const float v[3])
1219 {
1220         zero_m3(r);
1221         r[0][1] = v[2];
1222         r[0][2] = -v[1];
1223         r[1][0] = -v[2];
1224         r[1][2] = v[0];
1225         r[2][0] = v[1];
1226         r[2][1] = -v[0];
1227 }
1228
1229 BLI_INLINE void madd_m3_m3fl(float r[3][3], float m[3][3], float f)
1230 {
1231         r[0][0] += m[0][0] * f;
1232         r[0][1] += m[0][1] * f;
1233         r[0][2] += m[0][2] * f;
1234         r[1][0] += m[1][0] * f;
1235         r[1][1] += m[1][1] * f;
1236         r[1][2] += m[1][2] * f;
1237         r[2][0] += m[2][0] * f;
1238         r[2][1] += m[2][1] * f;
1239         r[2][2] += m[2][2] * f;
1240 }
1241
1242 void cloth_parallel_transport_hair_frame(float mat[3][3], const float dir_old[3], const float dir_new[3])
1243 {
1244         float rot[3][3];
1245
1246         /* rotation between segments */
1247         rotation_between_vecs_to_mat3(rot, dir_old, dir_new);
1248
1249         /* rotate the frame */
1250         mul_m3_m3m3(mat, rot, mat);
1251 }
1252
1253 static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm )
1254 {
1255         Cloth *cloth = clmd->clothObject;
1256         ClothSpring *spring = NULL, *tspring = NULL, *tspring2 = NULL;
1257         unsigned int struct_springs = 0, shear_springs=0, bend_springs = 0, struct_springs_real = 0;
1258         unsigned int i = 0;
1259         unsigned int mvert_num = (unsigned int)dm->getNumVerts(dm);
1260         unsigned int numedges = (unsigned int)dm->getNumEdges (dm);
1261         unsigned int numpolys = (unsigned int)dm->getNumPolys(dm);
1262         float shrink_factor;
1263         const MEdge *medge = dm->getEdgeArray(dm);
1264         const MPoly *mpoly = dm->getPolyArray(dm);
1265         const MLoop *mloop = dm->getLoopArray(dm);
1266         int index2 = 0; // our second vertex index
1267         LinkNodePair *edgelist;
1268         EdgeSet *edgeset = NULL;
1269         LinkNode *search = NULL, *search2 = NULL;
1270
1271         // error handling
1272         if ( numedges==0 )
1273                 return 0;
1274
1275         /* NOTE: handling ownership of springs and edgeset is quite sloppy
1276          * currently they are never initialized but assert just to be sure */
1277         BLI_assert(cloth->springs == NULL);
1278         BLI_assert(cloth->edgeset == NULL);
1279
1280         cloth->springs = NULL;
1281         cloth->edgeset = NULL;
1282
1283         edgelist = MEM_callocN(sizeof(*edgelist) * mvert_num, "cloth_edgelist_alloc" );
1284
1285         if (!edgelist)
1286                 return 0;
1287
1288         clmd->sim_parms->avg_spring_len = 0.0f;
1289         for (i = 0; i < mvert_num; i++) {
1290                 cloth->verts[i].avg_spring_len = 0.0f;
1291         }
1292
1293         // structural springs
1294         for ( i = 0; i < numedges; i++ ) {
1295                 spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1296
1297                 if ( spring ) {
1298                         spring_verts_ordered_set(spring, medge[i].v1, medge[i].v2);
1299                         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW && medge[i].flag & ME_LOOSEEDGE) {
1300                                 // handle sewing (loose edges will be pulled together)
1301                                 spring->restlen = 0.0f;
1302                                 spring->stiffness = 1.0f;
1303                                 spring->type = CLOTH_SPRING_TYPE_SEWING;
1304                         }
1305                         else {
1306                                 shrink_factor = cloth_shrink_factor(clmd, cloth->verts, spring->ij, spring->kl);
1307                                 spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest) * shrink_factor;
1308                                 spring->stiffness = (cloth->verts[spring->kl].struct_stiff + cloth->verts[spring->ij].struct_stiff) / 2.0f;
1309                                 spring->type = CLOTH_SPRING_TYPE_STRUCTURAL;
1310
1311                                 clmd->sim_parms->avg_spring_len += spring->restlen;
1312                                 cloth->verts[spring->ij].avg_spring_len += spring->restlen;
1313                                 cloth->verts[spring->kl].avg_spring_len += spring->restlen;
1314                                 cloth->verts[spring->ij].spring_count++;
1315                                 cloth->verts[spring->kl].spring_count++;
1316                                 struct_springs_real++;
1317                         }
1318
1319                         spring->flags = 0;
1320                         struct_springs++;
1321
1322                         BLI_linklist_prepend ( &cloth->springs, spring );
1323                 }
1324                 else {
1325                         cloth_free_errorsprings(cloth, edgelist);
1326                         return 0;
1327                 }
1328         }
1329
1330         if (struct_springs_real > 0)
1331                 clmd->sim_parms->avg_spring_len /= struct_springs_real;
1332
1333         for (i = 0; i < mvert_num; i++) {
1334                 if (cloth->verts[i].spring_count > 0)
1335                         cloth->verts[i].avg_spring_len = cloth->verts[i].avg_spring_len * 0.49f / ((float)cloth->verts[i].spring_count);
1336         }
1337
1338         // shear springs
1339         for (i = 0; i < numpolys; i++) {
1340                 /* triangle faces already have shear springs due to structural geometry */
1341                 if (mpoly[i].totloop == 4) {
1342                         int j;
1343
1344                         for (j = 0; j != 2; j++) {
1345                                 spring = (ClothSpring *)MEM_callocN(sizeof(ClothSpring), "cloth spring");
1346
1347                                 if (!spring) {
1348                                         cloth_free_errorsprings(cloth, edgelist);
1349                                         return 0;
1350                                 }
1351
1352                                 spring_verts_ordered_set(
1353                                         spring,
1354                                         mloop[mpoly[i].loopstart + (j + 0)].v,
1355                                         mloop[mpoly[i].loopstart + (j + 2)].v);
1356
1357                                 shrink_factor = cloth_shrink_factor(clmd, cloth->verts, spring->ij, spring->kl);
1358                                 spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest) * shrink_factor;
1359                                 spring->type = CLOTH_SPRING_TYPE_SHEAR;
1360                                 spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0f;
1361
1362                                 BLI_linklist_append(&edgelist[spring->ij], spring);
1363                                 BLI_linklist_append(&edgelist[spring->kl], spring);
1364
1365                                 shear_springs++;
1366
1367                                 BLI_linklist_prepend(&cloth->springs, spring);
1368                         }
1369                 }
1370         }
1371
1372         edgeset = BLI_edgeset_new_ex(__func__, numedges);
1373         cloth->edgeset = edgeset;
1374
1375         if (numpolys) {
1376                 // bending springs
1377                 search2 = cloth->springs;
1378                 for ( i = struct_springs; i < struct_springs+shear_springs; i++ ) {
1379                         if ( !search2 )
1380                                 break;
1381
1382                         tspring2 = search2->link;
1383                         search = edgelist[tspring2->kl].list;
1384                         while ( search ) {
1385                                 tspring = search->link;
1386                                 index2 = ( ( tspring->ij==tspring2->kl ) ? ( tspring->kl ) : ( tspring->ij ) );
1387
1388                                 // check for existing spring
1389                                 // check also if startpoint is equal to endpoint
1390                                 if ((index2 != tspring2->ij) &&
1391                                     !BLI_edgeset_haskey(edgeset, tspring2->ij, index2))
1392                                 {
1393                                         spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1394
1395                                         if (!spring) {
1396                                                 cloth_free_errorsprings(cloth, edgelist);
1397                                                 return 0;
1398                                         }
1399
1400                                         spring_verts_ordered_set(spring, tspring2->ij, index2);
1401                                         shrink_factor = cloth_shrink_factor(clmd, cloth->verts, spring->ij, spring->kl);
1402                                         spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest) * shrink_factor;
1403                                         spring->type = CLOTH_SPRING_TYPE_BENDING;
1404                                         spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0f;
1405                                         BLI_edgeset_insert(edgeset, spring->ij, spring->kl);
1406                                         bend_springs++;
1407
1408                                         BLI_linklist_prepend ( &cloth->springs, spring );
1409                                 }
1410                                 search = search->next;
1411                         }
1412                         search2 = search2->next;
1413                 }
1414         }
1415         else if (struct_springs > 2) {
1416                 if (G.debug_value != 1112) {
1417                         search = cloth->springs;
1418                         search2 = search->next;
1419                         while (search && search2) {
1420                                 tspring = search->link;
1421                                 tspring2 = search2->link;
1422
1423                                 if (tspring->ij == tspring2->kl) {
1424                                         spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1425
1426                                         if (!spring) {
1427                                                 cloth_free_errorsprings(cloth, edgelist);
1428                                                 return 0;
1429                                         }
1430
1431                                         spring->ij = tspring2->ij;
1432                                         spring->kl = tspring->ij;
1433                                         spring->mn = tspring->kl;
1434                                         spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1435                                         spring->type = CLOTH_SPRING_TYPE_BENDING_ANG;
1436                                         spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0f;
1437                                         bend_springs++;
1438
1439                                         BLI_linklist_prepend ( &cloth->springs, spring );
1440                                 }
1441
1442                                 search = search->next;
1443                                 search2 = search2->next;
1444                         }
1445                 }
1446                 else {
1447                         /* bending springs for hair strands
1448                          * The current algorithm only goes through the edges in order of the mesh edges list
1449                          * and makes springs between the outer vert of edges sharing a vertice. This works just
1450                          * fine for hair, but not for user generated string meshes. This could/should be later
1451                          * extended to work with non-ordered edges so that it can be used for general "rope
1452                          * dynamics" without the need for the vertices or edges to be ordered through the length
1453                          * of the strands. -jahka */
1454                         search = cloth->springs;
1455                         search2 = search->next;
1456                         while (search && search2) {
1457                                 tspring = search->link;
1458                                 tspring2 = search2->link;
1459
1460                                 if (tspring->ij == tspring2->kl) {
1461                                         spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1462
1463                                         if (!spring) {
1464                                                 cloth_free_errorsprings(cloth, edgelist);
1465                                                 return 0;
1466                                         }
1467
1468                                         spring->ij = tspring2->ij;
1469                                         spring->kl = tspring->kl;
1470                                         spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1471                                         spring->type = CLOTH_SPRING_TYPE_BENDING;
1472                                         spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0f;
1473                                         bend_springs++;
1474
1475                                         BLI_linklist_prepend ( &cloth->springs, spring );
1476                                 }
1477
1478                                 search = search->next;
1479                                 search2 = search2->next;
1480                         }
1481                 }
1482
1483                 cloth_hair_update_bending_rest_targets(clmd);
1484         }
1485
1486         /* note: the edges may already exist so run reinsert */
1487
1488         /* insert other near springs in edgeset AFTER bending springs are calculated (for selfcolls) */
1489         for (i = 0; i < numedges; i++) { /* struct springs */
1490                 BLI_edgeset_add(edgeset, medge[i].v1, medge[i].v2);
1491         }
1492
1493         for (i = 0; i < numpolys; i++) { /* edge springs */
1494                 if (mpoly[i].totloop == 4) {
1495                         BLI_edgeset_add(edgeset, mloop[mpoly[i].loopstart + 0].v, mloop[mpoly[i].loopstart + 2].v);
1496                         BLI_edgeset_add(edgeset, mloop[mpoly[i].loopstart + 1].v, mloop[mpoly[i].loopstart + 3].v);
1497                 }
1498         }
1499
1500
1501         cloth->numsprings = struct_springs + shear_springs + bend_springs;
1502
1503         cloth_free_edgelist(edgelist, mvert_num);
1504
1505 #if 0
1506         if (G.debug_value > 0)
1507                 printf("avg_len: %f\n", clmd->sim_parms->avg_spring_len);
1508 #endif
1509
1510         return 1;
1511
1512 } /* cloth_build_springs */
1513 /***************************************************************************************
1514  * SPRING NETWORK BUILDING IMPLEMENTATION END
1515  ***************************************************************************************/