Pass EvaluationContext argument everywhere
[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_add_effector_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(struct EvaluationContext *eval_ctx, 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(eval_ctx, 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, struct EvaluationContext *eval_ctx, 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                 BKE_cloth_solver_set_positions(clmd);
461                 cloth_to_object (ob, clmd, vertexCos);
462
463                 BKE_ptcache_validate(cache, framenr);
464
465                 if (cache_result == PTCACHE_READ_INTERPOLATED && cache->flag & PTCACHE_REDO_NEEDED)
466                         BKE_ptcache_write(&pid, framenr);
467
468                 clmd->clothObject->last_frame= framenr;
469
470                 return;
471         }
472         else if (cache_result==PTCACHE_READ_OLD) {
473                 BKE_cloth_solver_set_positions(clmd);
474         }
475         else if ( /*ob->id.lib ||*/ (cache->flag & PTCACHE_BAKED)) { /* 2.4x disabled lib, but this can be used in some cases, testing further - campbell */
476                 /* if baked and nothing in cache, do nothing */
477                 BKE_ptcache_invalidate(cache);
478                 return;
479         }
480
481                 return;
482
483         /* if on second frame, write cache for first frame */
484         if (cache->simframe == startframe && (cache->flag & PTCACHE_OUTDATED || cache->last_exact==0))
485                 BKE_ptcache_write(&pid, startframe);
486
487         clmd->sim_parms->timescale *= framenr - cache->simframe;
488
489         /* do simulation */
490         BKE_ptcache_validate(cache, framenr);
491
492         if (!do_step_cloth(eval_ctx, ob, clmd, dm, framenr)) {
493                 BKE_ptcache_invalidate(cache);
494         }
495         else
496                 BKE_ptcache_write(&pid, framenr);
497
498         cloth_to_object (ob, clmd, vertexCos);
499         clmd->clothObject->last_frame= framenr;
500 }
501
502 /* frees all */
503 void cloth_free_modifier(ClothModifierData *clmd )
504 {
505         Cloth   *cloth = NULL;
506         
507         if ( !clmd )
508                 return;
509
510         cloth = clmd->clothObject;
511
512         
513         if ( cloth ) {
514                 BPH_cloth_solver_free(clmd);
515
516                 // Free the verts.
517                 if ( cloth->verts != NULL )
518                         MEM_freeN ( cloth->verts );
519
520                 cloth->verts = NULL;
521                 cloth->mvert_num = 0;
522
523                 // Free the springs.
524                 if ( cloth->springs != NULL ) {
525                         LinkNode *search = cloth->springs;
526                         while (search) {
527                                 ClothSpring *spring = search->link;
528                                                 
529                                 MEM_freeN ( spring );
530                                 search = search->next;
531                         }
532                         BLI_linklist_free(cloth->springs, NULL);
533                 
534                         cloth->springs = NULL;
535                 }
536
537                 cloth->springs = NULL;
538                 cloth->numsprings = 0;
539
540                 // free BVH collision tree
541                 if ( cloth->bvhtree )
542                         BLI_bvhtree_free ( cloth->bvhtree );
543                 
544                 if ( cloth->bvhselftree )
545                         BLI_bvhtree_free ( cloth->bvhselftree );
546
547                 // we save our faces for collision objects
548                 if (cloth->tri)
549                         MEM_freeN(cloth->tri);
550
551                 if (cloth->edgeset)
552                         BLI_edgeset_free(cloth->edgeset);
553                 
554                 
555                 /*
556                 if (clmd->clothObject->facemarks)
557                 MEM_freeN(clmd->clothObject->facemarks);
558                 */
559                 MEM_freeN ( cloth );
560                 clmd->clothObject = NULL;
561         }
562 }
563
564 /* frees all */
565 void cloth_free_modifier_extern(ClothModifierData *clmd )
566 {
567         Cloth   *cloth = NULL;
568         if (G.debug_value > 0)
569                 printf("cloth_free_modifier_extern\n");
570         
571         if ( !clmd )
572                 return;
573
574         cloth = clmd->clothObject;
575         
576         if ( cloth ) {
577                 if (G.debug_value > 0)
578                         printf("cloth_free_modifier_extern in\n");
579
580                 BPH_cloth_solver_free(clmd);
581
582                 // Free the verts.
583                 if ( cloth->verts != NULL )
584                         MEM_freeN ( cloth->verts );
585
586                 cloth->verts = NULL;
587                 cloth->mvert_num = 0;
588
589                 // Free the springs.
590                 if ( cloth->springs != NULL ) {
591                         LinkNode *search = cloth->springs;
592                         while (search) {
593                                 ClothSpring *spring = search->link;
594
595                                 MEM_freeN ( spring );
596                                 search = search->next;
597                         }
598                         BLI_linklist_free(cloth->springs, NULL);
599
600                         cloth->springs = NULL;
601                 }
602
603                 cloth->springs = NULL;
604                 cloth->numsprings = 0;
605
606                 // free BVH collision tree
607                 if ( cloth->bvhtree )
608                         BLI_bvhtree_free ( cloth->bvhtree );
609                 
610                 if ( cloth->bvhselftree )
611                         BLI_bvhtree_free ( cloth->bvhselftree );
612
613                 // we save our faces for collision objects
614                 if (cloth->tri)
615                         MEM_freeN(cloth->tri);
616
617                 if (cloth->edgeset)
618                         BLI_edgeset_free(cloth->edgeset);
619
620
621                 /*
622                 if (clmd->clothObject->facemarks)
623                 MEM_freeN(clmd->clothObject->facemarks);
624                 */
625                 MEM_freeN ( cloth );
626                 clmd->clothObject = NULL;
627         }
628 }
629
630 /******************************************************************************
631  *
632  * Internal functions.
633  *
634  ******************************************************************************/
635
636 /**
637  * cloth_to_object - copies the deformed vertices to the object.
638  *
639  **/
640 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, float (*vertexCos)[3])
641 {
642         unsigned int    i = 0;
643         Cloth *cloth = clmd->clothObject;
644
645         if (clmd->clothObject) {
646                 /* inverse matrix is not uptodate... */
647                 invert_m4_m4(ob->imat, ob->obmat);
648
649                 for (i = 0; i < cloth->mvert_num; i++) {
650                         copy_v3_v3 (vertexCos[i], cloth->verts[i].x);
651                         mul_m4_v3(ob->imat, vertexCos[i]);      /* cloth is in global coords */
652                 }
653         }
654 }
655
656
657 int cloth_uses_vgroup(ClothModifierData *clmd)
658 {
659         return (((clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING ) || 
660                 (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL ) ||
661                 (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW) ||
662                 (clmd->coll_parms->flags & CLOTH_COLLSETTINGS_FLAG_SELF)) && 
663                 ((clmd->sim_parms->vgroup_mass>0) || 
664                 (clmd->sim_parms->vgroup_struct>0)||
665                 (clmd->sim_parms->vgroup_bend>0)  ||
666                 (clmd->sim_parms->vgroup_shrink>0) ||
667                 (clmd->coll_parms->vgroup_selfcol>0)));
668 }
669
670 /**
671  * cloth_apply_vgroup - applies a vertex group as specified by type
672  *
673  **/
674 /* can be optimized to do all groups in one loop */
675 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm )
676 {
677         int i = 0;
678         int j = 0;
679         MDeformVert *dvert = NULL;
680         Cloth *clothObj = NULL;
681         int mvert_num;
682         /* float goalfac = 0; */ /* UNUSED */
683         ClothVertex *verts = NULL;
684
685         if (!clmd || !dm) return;
686
687         clothObj = clmd->clothObject;
688
689         mvert_num = dm->getNumVerts(dm);
690
691         verts = clothObj->verts;
692         
693         if (cloth_uses_vgroup(clmd)) {
694                 for (i = 0; i < mvert_num; i++, verts++) {
695
696                         /* Reset Goal values to standard */
697                         if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )
698                                 verts->goal= clmd->sim_parms->defgoal;
699                         else
700                                 verts->goal= 0.0f;
701
702                         /* Compute base cloth shrink weight */
703                         verts->shrink_factor = 0.0f;
704
705                         /* Reset vertex flags */
706                         verts->flags &= ~CLOTH_VERT_FLAG_PINNED;
707                         verts->flags &= ~CLOTH_VERT_FLAG_NOSELFCOLL;
708
709                         dvert = dm->getVertData ( dm, i, CD_MDEFORMVERT );
710                         if ( dvert ) {
711                                 for ( j = 0; j < dvert->totweight; j++ ) {
712                                         if (( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_mass-1)) && (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )) {
713                                                 verts->goal = dvert->dw [j].weight;
714
715                                                 /* goalfac= 1.0f; */ /* UNUSED */
716                                                 
717                                                 // Kicking goal factor to simplify things...who uses that anyway?
718                                                 // ABS ( clmd->sim_parms->maxgoal - clmd->sim_parms->mingoal );
719                                                 
720                                                 verts->goal  = pow4f(verts->goal);
721                                                 if ( verts->goal >= SOFTGOALSNAP )
722                                                         verts->flags |= CLOTH_VERT_FLAG_PINNED;
723                                         }
724                                         
725                                         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING ) {
726                                                 if ( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_struct-1)) {
727                                                         verts->struct_stiff = dvert->dw [j].weight;
728                                                         verts->shear_stiff = dvert->dw [j].weight;
729                                                 }
730                                                 
731                                                 if ( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_bend-1)) {
732                                                         verts->bend_stiff = dvert->dw [j].weight;
733                                                 }
734                                         }
735
736                                         if (clmd->coll_parms->flags & CLOTH_COLLSETTINGS_FLAG_SELF ) {
737                                                 if ( dvert->dw[j].def_nr == (clmd->coll_parms->vgroup_selfcol-1)) {
738                                                         if (dvert->dw [j].weight > 0.0f) {
739                                                                 verts->flags |= CLOTH_VERT_FLAG_NOSELFCOLL;
740                                                         }
741                                                 }
742                                         }
743                                         if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW ) {
744                                                 if (clmd->sim_parms->vgroup_shrink > 0) {
745                                                         if (dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_shrink - 1)) {
746                                                                 /* used for linear interpolation between min and max shrink factor based on weight */
747                                                                 verts->shrink_factor = dvert->dw[j].weight;
748                                                         }
749                                                 }
750                                         }
751                                 }
752                         }
753                 }
754         }
755 }
756
757 static float cloth_shrink_factor(ClothModifierData *clmd, ClothVertex *verts, int i1, int i2)
758 {
759         if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW ) {
760                 /* linear interpolation between min and max shrink factor based on weight */
761                 float base = 1.0f - clmd->sim_parms->shrink_min;
762                 float delta = clmd->sim_parms->shrink_min - clmd->sim_parms->shrink_max;
763
764                 float k1 = base + delta * verts[i1].shrink_factor;
765                 float k2 = base + delta * verts[i2].shrink_factor;
766
767                 /* Use geometrical mean to average two factors since it behaves better
768                    for diagonals when a rectangle transforms into a trapezoid. */
769                 return sqrtf(k1 * k2);
770         }
771         else
772                 return 1.0f;
773 }
774
775 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float UNUSED(framenr), int first)
776 {
777         int i = 0;
778         MVert *mvert = NULL;
779         ClothVertex *verts = NULL;
780         float (*shapekey_rest)[3] = NULL;
781         float tnull[3] = {0, 0, 0};
782         Cloth *cloth = NULL;
783         float maxdist = 0;
784
785         // If we have a clothObject, free it. 
786         if ( clmd->clothObject != NULL ) {
787                 cloth_free_modifier ( clmd );
788                 if (G.debug_value > 0)
789                         printf("cloth_free_modifier cloth_from_object\n");
790         }
791
792         // Allocate a new cloth object.
793         clmd->clothObject = MEM_callocN ( sizeof ( Cloth ), "cloth" );
794         if ( clmd->clothObject ) {
795                 clmd->clothObject->old_solver_type = 255;
796                 // clmd->clothObject->old_collision_type = 255;
797                 cloth = clmd->clothObject;
798                 clmd->clothObject->edgeset = NULL;
799         }
800         else if (!clmd->clothObject) {
801                 modifier_setError(&(clmd->modifier), "Out of memory on allocating clmd->clothObject");
802                 return 0;
803         }
804
805         // mesh input objects need DerivedMesh
806         if ( !dm )
807                 return 0;
808
809         DM_ensure_looptri(dm);
810         cloth_from_mesh ( clmd, dm );
811
812         // create springs
813         clmd->clothObject->springs = NULL;
814         clmd->clothObject->numsprings = -1;
815
816         if ( clmd->sim_parms->shapekey_rest && !(clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_DYNAMIC_BASEMESH ) )
817                 shapekey_rest = dm->getVertDataArray ( dm, CD_CLOTH_ORCO );
818
819         mvert = dm->getVertArray (dm);
820
821         verts = clmd->clothObject->verts;
822
823         // set initial values
824         for ( i = 0; i < dm->getNumVerts(dm); i++, verts++ ) {
825                 if (first) {
826                         copy_v3_v3(verts->x, mvert[i].co);
827
828                         mul_m4_v3(ob->obmat, verts->x);
829
830                         if ( shapekey_rest ) {
831                                 copy_v3_v3(verts->xrest, shapekey_rest[i]);
832                                 mul_m4_v3(ob->obmat, verts->xrest);
833                         }
834                         else
835                                 copy_v3_v3(verts->xrest, verts->x);
836                 }
837                 
838                 /* no GUI interface yet */
839                 verts->mass = clmd->sim_parms->mass; 
840                 verts->impulse_count = 0;
841
842                 if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )
843                         verts->goal= clmd->sim_parms->defgoal;
844                 else
845                         verts->goal= 0.0f;
846
847                 verts->shrink_factor = 0.0f;
848
849                 verts->flags = 0;
850                 copy_v3_v3 ( verts->xold, verts->x );
851                 copy_v3_v3 ( verts->xconst, verts->x );
852                 copy_v3_v3 ( verts->txold, verts->x );
853                 copy_v3_v3 ( verts->tx, verts->x );
854                 mul_v3_fl(verts->v, 0.0f);
855
856                 verts->impulse_count = 0;
857                 copy_v3_v3 ( verts->impulse, tnull );
858         }
859         
860         // apply / set vertex groups
861         // has to be happen before springs are build!
862         cloth_apply_vgroup (clmd, dm);
863
864         if ( !cloth_build_springs ( clmd, dm ) ) {
865                 cloth_free_modifier ( clmd );
866                 modifier_setError(&(clmd->modifier), "Cannot build springs");
867                 printf("cloth_free_modifier cloth_build_springs\n");
868                 return 0;
869         }
870         
871         // init our solver
872         BPH_cloth_solver_init(ob, clmd);
873         
874         if (!first)
875                 BKE_cloth_solver_set_positions(clmd);
876
877         clmd->clothObject->bvhtree = bvhtree_build_from_cloth ( clmd, MAX2(clmd->coll_parms->epsilon, clmd->coll_parms->distance_repel) );
878         
879         for (i = 0; i < dm->getNumVerts(dm); i++) {
880                 maxdist = MAX2(maxdist, clmd->coll_parms->selfepsilon* ( cloth->verts[i].avg_spring_len*2.0f));
881         }
882         
883         clmd->clothObject->bvhselftree = bvhselftree_build_from_cloth ( clmd, maxdist );
884
885         return 1;
886 }
887
888 static void cloth_from_mesh ( ClothModifierData *clmd, DerivedMesh *dm )
889 {
890         const MLoop *mloop = dm->getLoopArray(dm);
891         const MLoopTri *looptri = dm->getLoopTriArray(dm);
892         const unsigned int mvert_num = dm->getNumVerts(dm);
893         const unsigned int looptri_num = dm->getNumLoopTri(dm);
894
895         /* Allocate our vertices. */
896         clmd->clothObject->mvert_num = mvert_num;
897         clmd->clothObject->verts = MEM_callocN(sizeof(ClothVertex) * clmd->clothObject->mvert_num, "clothVertex");
898         if (clmd->clothObject->verts == NULL) {
899                 cloth_free_modifier(clmd);
900                 modifier_setError(&(clmd->modifier), "Out of memory on allocating clmd->clothObject->verts");
901                 printf("cloth_free_modifier clmd->clothObject->verts\n");
902                 return;
903         }
904
905         /* save face information */
906         clmd->clothObject->tri_num = looptri_num;
907         clmd->clothObject->tri = MEM_mallocN(sizeof(MVertTri) * looptri_num, "clothLoopTris");
908         if (clmd->clothObject->tri == NULL) {
909                 cloth_free_modifier(clmd);
910                 modifier_setError(&(clmd->modifier), "Out of memory on allocating clmd->clothObject->looptri");
911                 printf("cloth_free_modifier clmd->clothObject->looptri\n");
912                 return;
913         }
914         DM_verttri_from_looptri(clmd->clothObject->tri, mloop, looptri, looptri_num);
915
916         /* Free the springs since they can't be correct if the vertices
917          * changed.
918          */
919         if ( clmd->clothObject->springs != NULL )
920                 MEM_freeN ( clmd->clothObject->springs );
921
922 }
923
924 /***************************************************************************************
925  * SPRING NETWORK GWN_BATCH_BUILDING IMPLEMENTATION BEGIN
926  ***************************************************************************************/
927
928 BLI_INLINE void spring_verts_ordered_set(ClothSpring *spring, int v0, int v1)
929 {
930         if (v0 < v1) {
931                 spring->ij = v0;
932                 spring->kl = v1;
933         }
934         else {
935                 spring->ij = v1;
936                 spring->kl = v0;
937         }
938 }
939
940 static void cloth_free_edgelist(LinkNodePair *edgelist, unsigned int mvert_num)
941 {
942         if (edgelist) {
943                 unsigned int i;
944                 for (i = 0; i < mvert_num; i++) {
945                         BLI_linklist_free(edgelist[i].list, NULL);
946                 }
947
948                 MEM_freeN(edgelist);
949         }
950 }
951
952 static void cloth_free_errorsprings(Cloth *cloth, LinkNodePair *edgelist)
953 {
954         if ( cloth->springs != NULL ) {
955                 LinkNode *search = cloth->springs;
956                 while (search) {
957                         ClothSpring *spring = search->link;
958                                                 
959                         MEM_freeN ( spring );
960                         search = search->next;
961                 }
962                 BLI_linklist_free(cloth->springs, NULL);
963                 
964                 cloth->springs = NULL;
965         }
966
967         cloth_free_edgelist(edgelist, cloth->mvert_num);
968         
969         if (cloth->edgeset) {
970                 BLI_edgeset_free(cloth->edgeset);
971                 cloth->edgeset = NULL;
972         }
973 }
974
975 static void cloth_hair_update_bending_targets(ClothModifierData *clmd)
976 {
977         Cloth *cloth = clmd->clothObject;
978         LinkNode *search = NULL;
979         float hair_frame[3][3], dir_old[3], dir_new[3];
980         int prev_mn; /* to find hair chains */
981         
982         if (!clmd->hairdata)
983                 return;
984         
985         /* XXX Note: we need to propagate frames from the root up,
986          * but structural hair springs are stored in reverse order.
987          * The bending springs however are then inserted in the same
988          * order as vertices again ...
989          * This messy situation can be resolved when solver data is
990          * generated directly from a dedicated hair system.
991          */
992         
993         prev_mn = -1;
994         for (search = cloth->springs; search; search = search->next) {
995                 ClothSpring *spring = search->link;
996                 ClothHairData *hair_ij, *hair_kl;
997                 bool is_root = spring->kl != prev_mn;
998                 
999                 if (spring->type != CLOTH_SPRING_TYPE_BENDING_ANG) {
1000                         continue;
1001                 }
1002                 
1003                 hair_ij = &clmd->hairdata[spring->ij];
1004                 hair_kl = &clmd->hairdata[spring->kl];
1005                 if (is_root) {
1006                         /* initial hair frame from root orientation */
1007                         copy_m3_m3(hair_frame, hair_ij->rot);
1008                         /* surface normal is the initial direction,
1009                          * parallel transport then keeps it aligned to the hair direction
1010                          */
1011                         copy_v3_v3(dir_new, hair_frame[2]);
1012                 }
1013                 
1014                 copy_v3_v3(dir_old, dir_new);
1015                 sub_v3_v3v3(dir_new, cloth->verts[spring->mn].x, cloth->verts[spring->kl].x);
1016                 normalize_v3(dir_new);
1017                 
1018 #if 0
1019                 if (clmd->debug_data && (spring->ij == 0 || spring->ij == 1)) {
1020                         float a[3], b[3];
1021                         
1022                         copy_v3_v3(a, cloth->verts[spring->kl].x);
1023 //                      BKE_sim_debug_data_add_dot(clmd->debug_data, cloth_vert ? cloth_vert->x : key->co, 1, 1, 0, "frames", 8246, p, k);
1024                         
1025                         mul_v3_v3fl(b, hair_frame[0], clmd->sim_parms->avg_spring_len);
1026                         BKE_sim_debug_data_add_vector(clmd->debug_data, a, b, 1, 0, 0, "frames", 8247, spring->kl, spring->mn);
1027                         
1028                         mul_v3_v3fl(b, hair_frame[1], clmd->sim_parms->avg_spring_len);
1029                         BKE_sim_debug_data_add_vector(clmd->debug_data, a, b, 0, 1, 0, "frames", 8248, spring->kl, spring->mn);
1030                         
1031                         mul_v3_v3fl(b, hair_frame[2], clmd->sim_parms->avg_spring_len);
1032                         BKE_sim_debug_data_add_vector(clmd->debug_data, a, b, 0, 0, 1, "frames", 8249, spring->kl, spring->mn);
1033                 }
1034 #endif
1035                 
1036                 /* get local targets for kl/mn vertices by putting rest targets into the current frame,
1037                  * then multiply with the rest length to get the actual goals
1038                  */
1039                 
1040                 mul_v3_m3v3(spring->target, hair_frame, hair_kl->rest_target);
1041                 mul_v3_fl(spring->target, spring->restlen);
1042                 
1043                 /* move frame to next hair segment */
1044                 cloth_parallel_transport_hair_frame(hair_frame, dir_old, dir_new);
1045                 
1046                 prev_mn = spring->mn;
1047         }
1048 }
1049
1050 static void cloth_hair_update_bending_rest_targets(ClothModifierData *clmd)
1051 {
1052         Cloth *cloth = clmd->clothObject;
1053         LinkNode *search = NULL;
1054         float hair_frame[3][3], dir_old[3], dir_new[3];
1055         int prev_mn; /* to find hair roots */
1056         
1057         if (!clmd->hairdata)
1058                 return;
1059         
1060         /* XXX Note: we need to propagate frames from the root up,
1061          * but structural hair springs are stored in reverse order.
1062          * The bending springs however are then inserted in the same
1063          * order as vertices again ...
1064          * This messy situation can be resolved when solver data is
1065          * generated directly from a dedicated hair system.
1066          */
1067         
1068         prev_mn = -1;
1069         for (search = cloth->springs; search; search = search->next) {
1070                 ClothSpring *spring = search->link;
1071                 ClothHairData *hair_ij, *hair_kl;
1072                 bool is_root = spring->kl != prev_mn;
1073                 
1074                 if (spring->type != CLOTH_SPRING_TYPE_BENDING_ANG) {
1075                         continue;
1076                 }
1077                 
1078                 hair_ij = &clmd->hairdata[spring->ij];
1079                 hair_kl = &clmd->hairdata[spring->kl];
1080                 if (is_root) {
1081                         /* initial hair frame from root orientation */
1082                         copy_m3_m3(hair_frame, hair_ij->rot);
1083                         /* surface normal is the initial direction,
1084                          * parallel transport then keeps it aligned to the hair direction
1085                          */
1086                         copy_v3_v3(dir_new, hair_frame[2]);
1087                 }
1088                 
1089                 copy_v3_v3(dir_old, dir_new);
1090                 sub_v3_v3v3(dir_new, cloth->verts[spring->mn].xrest, cloth->verts[spring->kl].xrest);
1091                 normalize_v3(dir_new);
1092                 
1093                 /* dir expressed in the hair frame defines the rest target direction */
1094                 copy_v3_v3(hair_kl->rest_target, dir_new);
1095                 mul_transposed_m3_v3(hair_frame, hair_kl->rest_target);
1096                 
1097                 /* move frame to next hair segment */
1098                 cloth_parallel_transport_hair_frame(hair_frame, dir_old, dir_new);
1099                 
1100                 prev_mn = spring->mn;
1101         }
1102 }
1103
1104 /* update stiffness if vertex group values are changing from frame to frame */
1105 static void cloth_update_springs( ClothModifierData *clmd )
1106 {
1107         Cloth *cloth = clmd->clothObject;
1108         LinkNode *search = NULL;
1109
1110         search = cloth->springs;
1111         while (search) {
1112                 ClothSpring *spring = search->link;
1113
1114                 spring->stiffness = 0.0f;
1115
1116                 if (spring->type == CLOTH_SPRING_TYPE_STRUCTURAL) {
1117                         spring->stiffness = (cloth->verts[spring->kl].struct_stiff + cloth->verts[spring->ij].struct_stiff) / 2.0f;
1118                 }
1119                 else if (spring->type == CLOTH_SPRING_TYPE_SHEAR) {
1120                         spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0f;
1121                 }
1122                 else if (spring->type == CLOTH_SPRING_TYPE_BENDING) {
1123                         spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0f;
1124                 }
1125                 else if (spring->type == CLOTH_SPRING_TYPE_BENDING_ANG) {
1126                         ClothVertex *v1 = &cloth->verts[spring->ij];
1127                         ClothVertex *v2 = &cloth->verts[spring->kl];
1128                         if (clmd->hairdata) {
1129                                 /* copy extra hair data to generic cloth vertices */
1130                                 v1->bend_stiff = clmd->hairdata[spring->ij].bending_stiffness;
1131                                 v2->bend_stiff = clmd->hairdata[spring->kl].bending_stiffness;
1132                         }
1133                         spring->stiffness = (v1->bend_stiff + v2->bend_stiff) / 2.0f;
1134                 }
1135                 else if (spring->type == CLOTH_SPRING_TYPE_GOAL) {
1136                         /* Warning: Appending NEW goal springs does not work because implicit solver would need reset! */
1137
1138                         /* Activate / Deactivate existing springs */
1139                         if ((!(cloth->verts[spring->ij].flags & CLOTH_VERT_FLAG_PINNED)) &&
1140                             (cloth->verts[spring->ij].goal > ALMOST_ZERO))
1141                         {
1142                                 spring->flags &= ~CLOTH_SPRING_FLAG_DEACTIVATE;
1143                         }
1144                         else {
1145                                 spring->flags |= CLOTH_SPRING_FLAG_DEACTIVATE;
1146                         }
1147                 }
1148                 
1149                 search = search->next;
1150         }
1151         
1152         cloth_hair_update_bending_targets(clmd);
1153 }
1154
1155 /* Update rest verts, for dynamically deformable cloth */
1156 static void cloth_update_verts( Object *ob, ClothModifierData *clmd, DerivedMesh *dm )
1157 {
1158         unsigned int i = 0;
1159         MVert *mvert = dm->getVertArray (dm);
1160         ClothVertex *verts = clmd->clothObject->verts;
1161
1162         /* vertex count is already ensured to match */
1163         for ( i = 0; i < dm->getNumVerts(dm); i++, verts++ ) {
1164                 copy_v3_v3(verts->xrest, mvert[i].co);
1165                 mul_m4_v3(ob->obmat, verts->xrest);
1166         }
1167 }
1168
1169 /* Update spring rest lenght, for dynamically deformable cloth */
1170 static void cloth_update_spring_lengths( ClothModifierData *clmd, DerivedMesh *dm )
1171 {
1172         Cloth *cloth = clmd->clothObject;
1173         LinkNode *search = cloth->springs;
1174         unsigned int struct_springs = 0;
1175         unsigned int i = 0;
1176         unsigned int mvert_num = (unsigned int)dm->getNumVerts(dm);
1177         float shrink_factor;
1178
1179         clmd->sim_parms->avg_spring_len = 0.0f;
1180
1181         for (i = 0; i < mvert_num; i++) {
1182                 cloth->verts[i].avg_spring_len = 0.0f;
1183         }
1184
1185         while (search) {
1186                 ClothSpring *spring = search->link;
1187
1188                 if ( spring->type != CLOTH_SPRING_TYPE_SEWING ) {
1189                         if ( spring->type & (CLOTH_SPRING_TYPE_STRUCTURAL | CLOTH_SPRING_TYPE_SHEAR | CLOTH_SPRING_TYPE_BENDING) )
1190                                 shrink_factor = cloth_shrink_factor(clmd, cloth->verts, spring->ij, spring->kl);
1191                         else
1192                                 shrink_factor = 1.0f;
1193
1194                         spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest) * shrink_factor;
1195                 }
1196
1197                 if ( spring->type == CLOTH_SPRING_TYPE_STRUCTURAL ) {
1198                         clmd->sim_parms->avg_spring_len += spring->restlen;
1199                         cloth->verts[spring->ij].avg_spring_len += spring->restlen;
1200                         cloth->verts[spring->kl].avg_spring_len += spring->restlen;
1201                         struct_springs++;
1202                 }
1203
1204                 search = search->next;
1205         }
1206
1207         if (struct_springs > 0)
1208                 clmd->sim_parms->avg_spring_len /= struct_springs;
1209
1210         for (i = 0; i < mvert_num; i++) {
1211                 if (cloth->verts[i].spring_count > 0)
1212                         cloth->verts[i].avg_spring_len = cloth->verts[i].avg_spring_len * 0.49f / ((float)cloth->verts[i].spring_count);
1213         }
1214 }
1215
1216 BLI_INLINE void cross_identity_v3(float r[3][3], const float v[3])
1217 {
1218         zero_m3(r);
1219         r[0][1] = v[2];
1220         r[0][2] = -v[1];
1221         r[1][0] = -v[2];
1222         r[1][2] = v[0];
1223         r[2][0] = v[1];
1224         r[2][1] = -v[0];
1225 }
1226
1227 BLI_INLINE void madd_m3_m3fl(float r[3][3], float m[3][3], float f)
1228 {
1229         r[0][0] += m[0][0] * f;
1230         r[0][1] += m[0][1] * f;
1231         r[0][2] += m[0][2] * f;
1232         r[1][0] += m[1][0] * f;
1233         r[1][1] += m[1][1] * f;
1234         r[1][2] += m[1][2] * f;
1235         r[2][0] += m[2][0] * f;
1236         r[2][1] += m[2][1] * f;
1237         r[2][2] += m[2][2] * f;
1238 }
1239
1240 void cloth_parallel_transport_hair_frame(float mat[3][3], const float dir_old[3], const float dir_new[3])
1241 {
1242         float rot[3][3];
1243         
1244         /* rotation between segments */
1245         rotation_between_vecs_to_mat3(rot, dir_old, dir_new);
1246         
1247         /* rotate the frame */
1248         mul_m3_m3m3(mat, rot, mat);
1249 }
1250
1251 static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm )
1252 {
1253         Cloth *cloth = clmd->clothObject;
1254         ClothSpring *spring = NULL, *tspring = NULL, *tspring2 = NULL;
1255         unsigned int struct_springs = 0, shear_springs=0, bend_springs = 0, struct_springs_real = 0;
1256         unsigned int i = 0;
1257         unsigned int mvert_num = (unsigned int)dm->getNumVerts(dm);
1258         unsigned int numedges = (unsigned int)dm->getNumEdges (dm);
1259         unsigned int numpolys = (unsigned int)dm->getNumPolys(dm);
1260         float shrink_factor;
1261         const MEdge *medge = dm->getEdgeArray(dm);
1262         const MPoly *mpoly = dm->getPolyArray(dm);
1263         const MLoop *mloop = dm->getLoopArray(dm);
1264         int index2 = 0; // our second vertex index
1265         LinkNodePair *edgelist;
1266         EdgeSet *edgeset = NULL;
1267         LinkNode *search = NULL, *search2 = NULL;
1268         
1269         // error handling
1270         if ( numedges==0 )
1271                 return 0;
1272
1273         /* NOTE: handling ownership of springs and edgeset is quite sloppy
1274          * currently they are never initialized but assert just to be sure */
1275         BLI_assert(cloth->springs == NULL);
1276         BLI_assert(cloth->edgeset == NULL);
1277
1278         cloth->springs = NULL;
1279         cloth->edgeset = NULL;
1280
1281         edgelist = MEM_callocN(sizeof(*edgelist) * mvert_num, "cloth_edgelist_alloc" );
1282         
1283         if (!edgelist)
1284                 return 0;
1285
1286         // structural springs
1287         for ( i = 0; i < numedges; i++ ) {
1288                 spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1289
1290                 if ( spring ) {
1291                         spring_verts_ordered_set(spring, medge[i].v1, medge[i].v2);
1292                         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW && medge[i].flag & ME_LOOSEEDGE) {
1293                                 // handle sewing (loose edges will be pulled together)
1294                                 spring->restlen = 0.0f;
1295                                 spring->stiffness = 1.0f;
1296                                 spring->type = CLOTH_SPRING_TYPE_SEWING;
1297                         }
1298                         else {
1299                                 shrink_factor = cloth_shrink_factor(clmd, cloth->verts, spring->ij, spring->kl);
1300                                 spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest) * shrink_factor;
1301                                 spring->stiffness = (cloth->verts[spring->kl].struct_stiff + cloth->verts[spring->ij].struct_stiff) / 2.0f;
1302                                 spring->type = CLOTH_SPRING_TYPE_STRUCTURAL;
1303
1304                                 clmd->sim_parms->avg_spring_len += spring->restlen;
1305                                 cloth->verts[spring->ij].avg_spring_len += spring->restlen;
1306                                 cloth->verts[spring->kl].avg_spring_len += spring->restlen;
1307                                 cloth->verts[spring->ij].spring_count++;
1308                                 cloth->verts[spring->kl].spring_count++;
1309                                 struct_springs_real++;
1310                         }
1311
1312                         spring->flags = 0;
1313                         struct_springs++;
1314                         
1315                         BLI_linklist_prepend ( &cloth->springs, spring );
1316                 }
1317                 else {
1318                         cloth_free_errorsprings(cloth, edgelist);
1319                         return 0;
1320                 }
1321         }
1322
1323         if (struct_springs_real > 0)
1324                 clmd->sim_parms->avg_spring_len /= struct_springs_real;
1325         
1326         for (i = 0; i < mvert_num; i++) {
1327                 if (cloth->verts[i].spring_count > 0)
1328                         cloth->verts[i].avg_spring_len = cloth->verts[i].avg_spring_len * 0.49f / ((float)cloth->verts[i].spring_count);
1329         }
1330
1331         // shear springs
1332         for (i = 0; i < numpolys; i++) {
1333                 /* triangle faces already have shear springs due to structural geometry */
1334                 if (mpoly[i].totloop == 4) {
1335                         int j;
1336
1337                         for (j = 0; j != 2; j++) {
1338                                 spring = (ClothSpring *)MEM_callocN(sizeof(ClothSpring), "cloth spring");
1339
1340                                 if (!spring) {
1341                                         cloth_free_errorsprings(cloth, edgelist);
1342                                         return 0;
1343                                 }
1344
1345                                 spring_verts_ordered_set(
1346                                         spring,
1347                                         mloop[mpoly[i].loopstart + (j + 0)].v,
1348                                         mloop[mpoly[i].loopstart + (j + 2)].v);
1349
1350                                 shrink_factor = cloth_shrink_factor(clmd, cloth->verts, spring->ij, spring->kl);
1351                                 spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest) * shrink_factor;
1352                                 spring->type = CLOTH_SPRING_TYPE_SHEAR;
1353                                 spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0f;
1354
1355                                 BLI_linklist_append(&edgelist[spring->ij], spring);
1356                                 BLI_linklist_append(&edgelist[spring->kl], spring);
1357
1358                                 shear_springs++;
1359
1360                                 BLI_linklist_prepend(&cloth->springs, spring);
1361                         }
1362                 }
1363         }
1364
1365         edgeset = BLI_edgeset_new_ex(__func__, numedges);
1366         cloth->edgeset = edgeset;
1367
1368         if (numpolys) {
1369                 // bending springs
1370                 search2 = cloth->springs;
1371                 for ( i = struct_springs; i < struct_springs+shear_springs; i++ ) {
1372                         if ( !search2 )
1373                                 break;
1374
1375                         tspring2 = search2->link;
1376                         search = edgelist[tspring2->kl].list;
1377                         while ( search ) {
1378                                 tspring = search->link;
1379                                 index2 = ( ( tspring->ij==tspring2->kl ) ? ( tspring->kl ) : ( tspring->ij ) );
1380
1381                                 // check for existing spring
1382                                 // check also if startpoint is equal to endpoint
1383                                 if ((index2 != tspring2->ij) &&
1384                                     !BLI_edgeset_haskey(edgeset, tspring2->ij, index2))
1385                                 {
1386                                         spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1387
1388                                         if (!spring) {
1389                                                 cloth_free_errorsprings(cloth, edgelist);
1390                                                 return 0;
1391                                         }
1392
1393                                         spring_verts_ordered_set(spring, tspring2->ij, index2);
1394                                         shrink_factor = cloth_shrink_factor(clmd, cloth->verts, spring->ij, spring->kl);
1395                                         spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest) * shrink_factor;
1396                                         spring->type = CLOTH_SPRING_TYPE_BENDING;
1397                                         spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0f;
1398                                         BLI_edgeset_insert(edgeset, spring->ij, spring->kl);
1399                                         bend_springs++;
1400
1401                                         BLI_linklist_prepend ( &cloth->springs, spring );
1402                                 }
1403                                 search = search->next;
1404                         }
1405                         search2 = search2->next;
1406                 }
1407         }
1408         else if (struct_springs > 2) {
1409                 if (G.debug_value != 1112) {
1410                         search = cloth->springs;
1411                         search2 = search->next;
1412                         while (search && search2) {
1413                                 tspring = search->link;
1414                                 tspring2 = search2->link;
1415                                 
1416                                 if (tspring->ij == tspring2->kl) {
1417                                         spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1418                                         
1419                                         if (!spring) {
1420                                                 cloth_free_errorsprings(cloth, edgelist);
1421                                                 return 0;
1422                                         }
1423                                         
1424                                         spring->ij = tspring2->ij;
1425                                         spring->kl = tspring->ij;
1426                                         spring->mn = tspring->kl;
1427                                         spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1428                                         spring->type = CLOTH_SPRING_TYPE_BENDING_ANG;
1429                                         spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0f;
1430                                         bend_springs++;
1431                                         
1432                                         BLI_linklist_prepend ( &cloth->springs, spring );
1433                                 }
1434                                 
1435                                 search = search->next;
1436                                 search2 = search2->next;
1437                         }
1438                 }
1439                 else {
1440                         /* bending springs for hair strands */
1441                         /* The current algorightm only goes through the edges in order of the mesh edges list   */
1442                         /* and makes springs between the outer vert of edges sharing a vertice. This works just */
1443                         /* fine for hair, but not for user generated string meshes. This could/should be later  */
1444                         /* extended to work with non-ordered edges so that it can be used for general "rope             */
1445                         /* dynamics" without the need for the vertices or edges to be ordered through the length*/
1446                         /* of the strands. -jahka */
1447                         search = cloth->springs;
1448                         search2 = search->next;
1449                         while (search && search2) {
1450                                 tspring = search->link;
1451                                 tspring2 = search2->link;
1452                                 
1453                                 if (tspring->ij == tspring2->kl) {
1454                                         spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1455                                         
1456                                         if (!spring) {
1457                                                 cloth_free_errorsprings(cloth, edgelist);
1458                                                 return 0;
1459                                         }
1460                                         
1461                                         spring->ij = tspring2->ij;
1462                                         spring->kl = tspring->kl;
1463                                         spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1464                                         spring->type = CLOTH_SPRING_TYPE_BENDING;
1465                                         spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0f;
1466                                         bend_springs++;
1467                                         
1468                                         BLI_linklist_prepend ( &cloth->springs, spring );
1469                                 }
1470                                 
1471                                 search = search->next;
1472                                 search2 = search2->next;
1473                         }
1474                 }
1475                 
1476                 cloth_hair_update_bending_rest_targets(clmd);
1477         }
1478         
1479         /* note: the edges may already exist so run reinsert */
1480
1481         /* insert other near springs in edgeset AFTER bending springs are calculated (for selfcolls) */
1482         for (i = 0; i < numedges; i++) { /* struct springs */
1483                 BLI_edgeset_add(edgeset, medge[i].v1, medge[i].v2);
1484         }
1485
1486         for (i = 0; i < numpolys; i++) { /* edge springs */
1487                 if (mpoly[i].totloop == 4) {
1488                         BLI_edgeset_add(edgeset, mloop[mpoly[i].loopstart + 0].v, mloop[mpoly[i].loopstart + 2].v);
1489                         BLI_edgeset_add(edgeset, mloop[mpoly[i].loopstart + 1].v, mloop[mpoly[i].loopstart + 3].v);
1490                 }
1491         }
1492         
1493         
1494         cloth->numsprings = struct_springs + shear_springs + bend_springs;
1495         
1496         cloth_free_edgelist(edgelist, mvert_num);
1497
1498 #if 0
1499         if (G.debug_value > 0)
1500                 printf("avg_len: %f\n", clmd->sim_parms->avg_spring_len);
1501 #endif
1502
1503         return 1;
1504
1505 } /* cloth_build_springs */
1506 /***************************************************************************************
1507  * SPRING NETWORK GWN_BATCH_BUILDING IMPLEMENTATION END
1508  ***************************************************************************************/
1509