e928dfaab37817124fbab167f4df0f308acafcdc
[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 "DEG_depsgraph.h"
44
45 #include "BKE_cdderivedmesh.h"
46 #include "BKE_cloth.h"
47 #include "BKE_effect.h"
48 #include "BKE_global.h"
49 #include "BKE_modifier.h"
50 #include "BKE_pointcache.h"
51
52 #include "BPH_mass_spring.h"
53
54 // #include "PIL_time.h"  /* timing for debug prints */
55
56 /* ********** cloth engine ******* */
57 /* Prototypes for internal functions.
58  */
59 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, float (*vertexCos)[3]);
60 static void cloth_from_mesh ( ClothModifierData *clmd, DerivedMesh *dm );
61 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float framenr, int first);
62 static void cloth_update_springs( ClothModifierData *clmd );
63 static void cloth_update_verts( Object *ob, ClothModifierData *clmd, DerivedMesh *dm );
64 static void cloth_update_spring_lengths( ClothModifierData *clmd, DerivedMesh *dm );
65 static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm );
66 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm );
67
68 /******************************************************************************
69  *
70  * External interface called by modifier.c clothModifier functions.
71  *
72  ******************************************************************************/
73 /**
74  * cloth_init - creates a new cloth simulation.
75  *
76  * 1. create object
77  * 2. fill object with standard values or with the GUI settings if given
78  */
79 void cloth_init(ClothModifierData *clmd )
80 {       
81         /* Initialize our new data structure to reasonable values. */
82         clmd->sim_parms->gravity[0] = 0.0;
83         clmd->sim_parms->gravity[1] = 0.0;
84         clmd->sim_parms->gravity[2] = -9.81;
85         clmd->sim_parms->structural = 15.0;
86         clmd->sim_parms->max_struct = 15.0;
87         clmd->sim_parms->shear = 15.0;
88         clmd->sim_parms->bending = 0.5;
89         clmd->sim_parms->max_bend = 0.5;
90         clmd->sim_parms->bending_damping = 0.5;
91         clmd->sim_parms->Cdis = 5.0; 
92         clmd->sim_parms->Cvi = 1.0;
93         clmd->sim_parms->mass = 0.3f;
94         clmd->sim_parms->stepsPerFrame = 5;
95         clmd->sim_parms->flags = 0;
96         clmd->sim_parms->solver_type = 0;
97         clmd->sim_parms->maxspringlen = 10;
98         clmd->sim_parms->vgroup_mass = 0;
99         clmd->sim_parms->vgroup_shrink = 0;
100         clmd->sim_parms->shrink_min = 0.0f; /* min amount the fabric will shrink by 0.0 = no shrinking, 1.0 = shrink to nothing*/
101         clmd->sim_parms->avg_spring_len = 0.0;
102         clmd->sim_parms->presets = 2; /* cotton as start setting */
103         clmd->sim_parms->timescale = 1.0f; /* speed factor, describes how fast cloth moves */
104         clmd->sim_parms->time_scale = 1.0f; /* multiplies cloth speed */
105         clmd->sim_parms->reset = 0;
106         clmd->sim_parms->vel_damping = 1.0f; /* 1.0 = no damping, 0.0 = fully dampened */
107         
108         clmd->coll_parms->self_friction = 5.0;
109         clmd->coll_parms->friction = 5.0;
110         clmd->coll_parms->loop_count = 2;
111         clmd->coll_parms->epsilon = 0.015f;
112         clmd->coll_parms->flags = CLOTH_COLLSETTINGS_FLAG_ENABLED;
113         clmd->coll_parms->collision_list = NULL;
114         clmd->coll_parms->self_loop_count = 1.0;
115         clmd->coll_parms->selfepsilon = 0.75;
116         clmd->coll_parms->vgroup_selfcol = 0;
117
118         /* These defaults are copied from softbody.c's
119          * softbody_calc_forces() function.
120          */
121         clmd->sim_parms->eff_force_scale = 1000.0;
122         clmd->sim_parms->eff_wind_scale = 250.0;
123
124         // also from softbodies
125         clmd->sim_parms->maxgoal = 1.0f;
126         clmd->sim_parms->mingoal = 0.0f;
127         clmd->sim_parms->defgoal = 0.0f;
128         clmd->sim_parms->goalspring = 1.0f;
129         clmd->sim_parms->goalfrict = 0.0f;
130         clmd->sim_parms->velocity_smooth = 0.0f;
131
132         clmd->sim_parms->voxel_cell_size = 0.1f;
133
134         if (!clmd->sim_parms->effector_weights)
135                 clmd->sim_parms->effector_weights = BKE_add_effector_weights(NULL);
136
137         if (clmd->point_cache)
138                 clmd->point_cache->step = 1;
139 }
140
141 static BVHTree *bvhselftree_build_from_cloth (ClothModifierData *clmd, float epsilon)
142 {
143         unsigned int i;
144         BVHTree *bvhtree;
145         Cloth *cloth;
146         ClothVertex *verts;
147
148         if (!clmd)
149                 return NULL;
150
151         cloth = clmd->clothObject;
152
153         if (!cloth)
154                 return NULL;
155         
156         verts = cloth->verts;
157         
158         /* in the moment, return zero if no faces there */
159         if (!cloth->mvert_num)
160                 return NULL;
161         
162         /* create quadtree with k=26 */
163         bvhtree = BLI_bvhtree_new(cloth->mvert_num, epsilon, 4, 6);
164         
165         /* fill tree */
166         for (i = 0; i < cloth->mvert_num; i++, verts++) {
167                 const float *co;
168                 co = verts->xold;
169                 
170                 BLI_bvhtree_insert(bvhtree, i, co, 1);
171         }
172         
173         /* balance tree */
174         BLI_bvhtree_balance(bvhtree);
175         
176         return bvhtree;
177 }
178
179 static BVHTree *bvhtree_build_from_cloth (ClothModifierData *clmd, float epsilon)
180 {
181         unsigned int i;
182         BVHTree *bvhtree;
183         Cloth *cloth;
184         ClothVertex *verts;
185         const MVertTri *vt;
186
187         if (!clmd)
188                 return NULL;
189
190         cloth = clmd->clothObject;
191
192         if (!cloth)
193                 return NULL;
194         
195         verts = cloth->verts;
196         vt = cloth->tri;
197         
198         /* in the moment, return zero if no faces there */
199         if (!cloth->tri_num)
200                 return NULL;
201
202         /* create quadtree with k=26 */
203         bvhtree = BLI_bvhtree_new(cloth->tri_num, epsilon, 4, 26);
204
205         /* fill tree */
206         for (i = 0; i < cloth->tri_num; i++, vt++) {
207                 float co[3][3];
208
209                 copy_v3_v3(co[0], verts[vt->tri[0]].xold);
210                 copy_v3_v3(co[1], verts[vt->tri[1]].xold);
211                 copy_v3_v3(co[2], verts[vt->tri[2]].xold);
212
213                 BLI_bvhtree_insert(bvhtree, i, co[0], 3);
214         }
215
216         /* balance tree */
217         BLI_bvhtree_balance(bvhtree);
218         
219         return bvhtree;
220 }
221
222 void bvhtree_update_from_cloth(ClothModifierData *clmd, bool moving)
223 {       
224         unsigned int i = 0;
225         Cloth *cloth = clmd->clothObject;
226         BVHTree *bvhtree = cloth->bvhtree;
227         ClothVertex *verts = cloth->verts;
228         const MVertTri *vt;
229         
230         if (!bvhtree)
231                 return;
232         
233         vt = cloth->tri;
234         
235         /* update vertex position in bvh tree */
236         if (verts && vt) {
237                 for (i = 0; i < cloth->tri_num; i++, vt++) {
238                         float co[3][3], co_moving[3][3];
239                         bool ret;
240
241                         copy_v3_v3(co[0], verts[vt->tri[0]].txold);
242                         copy_v3_v3(co[1], verts[vt->tri[1]].txold);
243                         copy_v3_v3(co[2], verts[vt->tri[2]].txold);
244
245                         /* copy new locations into array */
246                         if (moving) {
247                                 /* update moving positions */
248                                 copy_v3_v3(co_moving[0], verts[vt->tri[0]].tx);
249                                 copy_v3_v3(co_moving[1], verts[vt->tri[1]].tx);
250                                 copy_v3_v3(co_moving[2], verts[vt->tri[2]].tx);
251
252                                 ret = BLI_bvhtree_update_node(bvhtree, i, co[0], co_moving[0], 3);
253                         }
254                         else {
255                                 ret = BLI_bvhtree_update_node(bvhtree, i, co[0], NULL, 3);
256                         }
257                         
258                         /* check if tree is already full */
259                         if (ret == false) {
260                                 break;
261                         }
262                 }
263                 
264                 BLI_bvhtree_update_tree(bvhtree);
265         }
266 }
267
268 void bvhselftree_update_from_cloth(ClothModifierData *clmd, bool moving)
269 {       
270         unsigned int i = 0;
271         Cloth *cloth = clmd->clothObject;
272         BVHTree *bvhtree = cloth->bvhselftree;
273         ClothVertex *verts = cloth->verts;
274         const MVertTri *vt;
275         
276         if (!bvhtree)
277                 return;
278
279         vt = cloth->tri;
280
281         /* update vertex position in bvh tree */
282         if (verts && vt) {
283                 for (i = 0; i < cloth->mvert_num; i++, verts++) {
284                         const float *co, *co_moving;
285                         bool ret;
286
287                         co = verts->txold;
288
289                         /* copy new locations into array */
290                         if (moving) {
291                                 /* update moving positions */
292                                 co_moving = verts->tx;
293                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, co_moving, 1);
294                         }
295                         else {
296                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, NULL, 1);
297                         }
298
299                         /* check if tree is already full */
300                         if (ret == false) {
301                                 break;
302                         }
303                 }
304                 
305                 BLI_bvhtree_update_tree(bvhtree);
306         }
307 }
308
309 void cloth_clear_cache(Object *ob, ClothModifierData *clmd, float framenr)
310 {
311         PTCacheID pid;
312         
313         BKE_ptcache_id_from_cloth(&pid, ob, clmd);
314
315         // don't do anything as long as we're in editmode!
316         if (pid.cache->edit && ob->mode & OB_MODE_PARTICLE_EDIT)
317                 return;
318         
319         BKE_ptcache_id_clear(&pid, PTCACHE_CLEAR_AFTER, framenr);
320 }
321
322 static int do_init_cloth(Object *ob, ClothModifierData *clmd, DerivedMesh *result, int framenr)
323 {
324         PointCache *cache;
325
326         cache= clmd->point_cache;
327
328         /* initialize simulation data if it didn't exist already */
329         if (clmd->clothObject == NULL) {
330                 if (!cloth_from_object(ob, clmd, result, framenr, 1)) {
331                         BKE_ptcache_invalidate(cache);
332                         modifier_setError(&(clmd->modifier), "Can't initialize cloth");
333                         return 0;
334                 }
335         
336                 if (clmd->clothObject == NULL) {
337                         BKE_ptcache_invalidate(cache);
338                         modifier_setError(&(clmd->modifier), "Null cloth object");
339                         return 0;
340                 }
341         
342                 BKE_cloth_solver_set_positions(clmd);
343
344                 clmd->clothObject->last_frame= MINFRAME-1;
345         }
346
347         return 1;
348 }
349
350 static int do_step_cloth(const struct EvaluationContext *eval_ctx, Object *ob, ClothModifierData *clmd, DerivedMesh *result, int framenr)
351 {
352         ClothVertex *verts = NULL;
353         Cloth *cloth;
354         ListBase *effectors = NULL;
355         MVert *mvert;
356         unsigned int i = 0;
357         int ret = 0;
358
359         /* simulate 1 frame forward */
360         cloth = clmd->clothObject;
361         verts = cloth->verts;
362         mvert = result->getVertArray(result);
363
364         /* force any pinned verts to their constrained location. */
365         for (i = 0; i < clmd->clothObject->mvert_num; i++, verts++) {
366                 /* save the previous position. */
367                 copy_v3_v3(verts->xold, verts->xconst);
368                 copy_v3_v3(verts->txold, verts->x);
369
370                 /* Get the current position. */
371                 copy_v3_v3(verts->xconst, mvert[i].co);
372                 mul_m4_v3(ob->obmat, verts->xconst);
373         }
374
375         effectors = pdInitEffectors(eval_ctx, clmd->scene, ob, NULL, clmd->sim_parms->effector_weights, true);
376
377         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_DYNAMIC_BASEMESH )
378                 cloth_update_verts ( ob, clmd, result );
379
380         /* Support for dynamic vertex groups, changing from frame to frame */
381         cloth_apply_vgroup ( clmd, result );
382
383         if ( clmd->sim_parms->flags & (CLOTH_SIMSETTINGS_FLAG_SEW | CLOTH_SIMSETTINGS_FLAG_DYNAMIC_BASEMESH) )
384                 cloth_update_spring_lengths ( clmd, result );
385
386         cloth_update_springs( clmd );
387         
388         // TIMEIT_START(cloth_step)
389
390         /* call the solver. */
391         ret = BPH_cloth_solve(ob, framenr, clmd, effectors);
392
393         // TIMEIT_END(cloth_step)
394
395         pdEndEffectors(&effectors);
396
397         // printf ( "%f\n", ( float ) tval() );
398         
399         return ret;
400 }
401
402 /************************************************
403  * clothModifier_do - main simulation function
404  ************************************************/
405 void clothModifier_do(ClothModifierData *clmd, const struct EvaluationContext *eval_ctx, Scene *scene, Object *ob, DerivedMesh *dm, float (*vertexCos)[3])
406 {
407         PointCache *cache;
408         PTCacheID pid;
409         float timescale;
410         int framenr, startframe, endframe;
411         int cache_result;
412
413         clmd->scene= scene;     /* nice to pass on later :) */
414         framenr= (int)scene->r.cfra;
415         cache= clmd->point_cache;
416
417         BKE_ptcache_id_from_cloth(&pid, ob, clmd);
418         BKE_ptcache_id_time(&pid, scene, framenr, &startframe, &endframe, &timescale);
419         clmd->sim_parms->timescale= timescale * clmd->sim_parms->time_scale;
420
421         if (clmd->sim_parms->reset || (clmd->clothObject && dm->getNumVerts(dm) != clmd->clothObject->mvert_num)) {
422                 clmd->sim_parms->reset = 0;
423                 cache->flag |= PTCACHE_OUTDATED;
424                 BKE_ptcache_id_reset(scene, &pid, PTCACHE_RESET_OUTDATED);
425                 BKE_ptcache_validate(cache, 0);
426                 cache->last_exact= 0;
427                 cache->flag &= ~PTCACHE_REDO_NEEDED;
428         }
429         
430         // unused in the moment, calculated separately in implicit.c
431         clmd->sim_parms->dt = clmd->sim_parms->timescale / clmd->sim_parms->stepsPerFrame;
432
433         /* simulation is only active during a specific period */
434         if (framenr < startframe) {
435                 BKE_ptcache_invalidate(cache);
436                 return;
437         }
438         else if (framenr > endframe) {
439                 framenr= endframe;
440         }
441
442         /* initialize simulation data if it didn't exist already */
443         if (!do_init_cloth(ob, clmd, dm, framenr))
444                 return;
445
446         if (framenr == startframe) {
447                 BKE_ptcache_id_reset(scene, &pid, PTCACHE_RESET_OUTDATED);
448                 do_init_cloth(ob, clmd, dm, framenr);
449                 BKE_ptcache_validate(cache, framenr);
450                 cache->flag &= ~PTCACHE_REDO_NEEDED;
451                 clmd->clothObject->last_frame= framenr;
452                 return;
453         }
454
455         /* try to read from cache */
456         bool can_simulate = (framenr == clmd->clothObject->last_frame+1) && !(cache->flag & PTCACHE_BAKED);
457
458         cache_result = BKE_ptcache_read(&pid, (float)framenr+scene->r.subframe, can_simulate);
459
460         if (cache_result == PTCACHE_READ_EXACT || cache_result == PTCACHE_READ_INTERPOLATED ||
461             (!can_simulate && cache_result == PTCACHE_READ_OLD))
462         {
463                 BKE_cloth_solver_set_positions(clmd);
464                 cloth_to_object (ob, clmd, vertexCos);
465
466                 BKE_ptcache_validate(cache, framenr);
467
468                 if (cache_result == PTCACHE_READ_INTERPOLATED && cache->flag & PTCACHE_REDO_NEEDED)
469                         BKE_ptcache_write(&pid, framenr);
470
471                 clmd->clothObject->last_frame= framenr;
472
473                 return;
474         }
475         else if (cache_result==PTCACHE_READ_OLD) {
476                 BKE_cloth_solver_set_positions(clmd);
477         }
478         else if ( /*ob->id.lib ||*/ (cache->flag & PTCACHE_BAKED)) { /* 2.4x disabled lib, but this can be used in some cases, testing further - campbell */
479                 /* if baked and nothing in cache, do nothing */
480                 BKE_ptcache_invalidate(cache);
481                 return;
482         }
483
484         /* if on second frame, write cache for first frame */
485         if (cache->simframe == startframe && (cache->flag & PTCACHE_OUTDATED || cache->last_exact==0))
486                 BKE_ptcache_write(&pid, startframe);
487
488         clmd->sim_parms->timescale *= framenr - cache->simframe;
489
490         /* do simulation */
491         BKE_ptcache_validate(cache, framenr);
492
493         if (!do_step_cloth(eval_ctx, ob, clmd, dm, framenr)) {
494                 BKE_ptcache_invalidate(cache);
495         }
496         else
497                 BKE_ptcache_write(&pid, framenr);
498
499         cloth_to_object (ob, clmd, vertexCos);
500         clmd->clothObject->last_frame= framenr;
501 }
502
503 /* frees all */
504 void cloth_free_modifier(ClothModifierData *clmd )
505 {
506         Cloth   *cloth = NULL;
507         
508         if ( !clmd )
509                 return;
510
511         cloth = clmd->clothObject;
512
513         
514         if ( cloth ) {
515                 BPH_cloth_solver_free(clmd);
516
517                 // Free the verts.
518                 if ( cloth->verts != NULL )
519                         MEM_freeN ( cloth->verts );
520
521                 cloth->verts = NULL;
522                 cloth->mvert_num = 0;
523
524                 // Free the springs.
525                 if ( cloth->springs != NULL ) {
526                         LinkNode *search = cloth->springs;
527                         while (search) {
528                                 ClothSpring *spring = search->link;
529                                                 
530                                 MEM_freeN ( spring );
531                                 search = search->next;
532                         }
533                         BLI_linklist_free(cloth->springs, NULL);
534                 
535                         cloth->springs = NULL;
536                 }
537
538                 cloth->springs = NULL;
539                 cloth->numsprings = 0;
540
541                 // free BVH collision tree
542                 if ( cloth->bvhtree )
543                         BLI_bvhtree_free ( cloth->bvhtree );
544                 
545                 if ( cloth->bvhselftree )
546                         BLI_bvhtree_free ( cloth->bvhselftree );
547
548                 // we save our faces for collision objects
549                 if (cloth->tri)
550                         MEM_freeN(cloth->tri);
551
552                 if (cloth->edgeset)
553                         BLI_edgeset_free(cloth->edgeset);
554                 
555                 
556                 /*
557                 if (clmd->clothObject->facemarks)
558                 MEM_freeN(clmd->clothObject->facemarks);
559                 */
560                 MEM_freeN ( cloth );
561                 clmd->clothObject = NULL;
562         }
563 }
564
565 /* frees all */
566 void cloth_free_modifier_extern(ClothModifierData *clmd )
567 {
568         Cloth   *cloth = NULL;
569         if (G.debug_value > 0)
570                 printf("cloth_free_modifier_extern\n");
571         
572         if ( !clmd )
573                 return;
574
575         cloth = clmd->clothObject;
576         
577         if ( cloth ) {
578                 if (G.debug_value > 0)
579                         printf("cloth_free_modifier_extern in\n");
580
581                 BPH_cloth_solver_free(clmd);
582
583                 // Free the verts.
584                 if ( cloth->verts != NULL )
585                         MEM_freeN ( cloth->verts );
586
587                 cloth->verts = NULL;
588                 cloth->mvert_num = 0;
589
590                 // Free the springs.
591                 if ( cloth->springs != NULL ) {
592                         LinkNode *search = cloth->springs;
593                         while (search) {
594                                 ClothSpring *spring = search->link;
595
596                                 MEM_freeN ( spring );
597                                 search = search->next;
598                         }
599                         BLI_linklist_free(cloth->springs, NULL);
600
601                         cloth->springs = NULL;
602                 }
603
604                 cloth->springs = NULL;
605                 cloth->numsprings = 0;
606
607                 // free BVH collision tree
608                 if ( cloth->bvhtree )
609                         BLI_bvhtree_free ( cloth->bvhtree );
610                 
611                 if ( cloth->bvhselftree )
612                         BLI_bvhtree_free ( cloth->bvhselftree );
613
614                 // we save our faces for collision objects
615                 if (cloth->tri)
616                         MEM_freeN(cloth->tri);
617
618                 if (cloth->edgeset)
619                         BLI_edgeset_free(cloth->edgeset);
620
621
622                 /*
623                 if (clmd->clothObject->facemarks)
624                 MEM_freeN(clmd->clothObject->facemarks);
625                 */
626                 MEM_freeN ( cloth );
627                 clmd->clothObject = NULL;
628         }
629 }
630
631 /******************************************************************************
632  *
633  * Internal functions.
634  *
635  ******************************************************************************/
636
637 /**
638  * cloth_to_object - copies the deformed vertices to the object.
639  *
640  **/
641 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, float (*vertexCos)[3])
642 {
643         unsigned int i = 0;
644         Cloth *cloth = clmd->clothObject;
645
646         if (clmd->clothObject) {
647                 /* inverse matrix is not uptodate... */
648                 invert_m4_m4(ob->imat, ob->obmat);
649
650                 for (i = 0; i < cloth->mvert_num; i++) {
651                         copy_v3_v3 (vertexCos[i], cloth->verts[i].x);
652                         mul_m4_v3(ob->imat, vertexCos[i]);      /* cloth is in global coords */
653                 }
654         }
655 }
656
657
658 int cloth_uses_vgroup(ClothModifierData *clmd)
659 {
660         return (((clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING ) || 
661                 (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL ) ||
662                 (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW) ||
663                 (clmd->coll_parms->flags & CLOTH_COLLSETTINGS_FLAG_SELF)) && 
664                 ((clmd->sim_parms->vgroup_mass>0) || 
665                 (clmd->sim_parms->vgroup_struct>0)||
666                 (clmd->sim_parms->vgroup_bend>0)  ||
667                 (clmd->sim_parms->vgroup_shrink>0) ||
668                 (clmd->coll_parms->vgroup_selfcol>0)));
669 }
670
671 /**
672  * cloth_apply_vgroup - applies a vertex group as specified by type
673  *
674  **/
675 /* can be optimized to do all groups in one loop */
676 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm )
677 {
678         int i = 0;
679         int j = 0;
680         MDeformVert *dvert = NULL;
681         Cloth *clothObj = NULL;
682         int mvert_num;
683         /* float goalfac = 0; */ /* UNUSED */
684         ClothVertex *verts = NULL;
685
686         if (!clmd || !dm) return;
687
688         clothObj = clmd->clothObject;
689
690         mvert_num = dm->getNumVerts(dm);
691
692         verts = clothObj->verts;
693         
694         if (cloth_uses_vgroup(clmd)) {
695                 for (i = 0; i < mvert_num; i++, verts++) {
696
697                         /* Reset Goal values to standard */
698                         if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )
699                                 verts->goal= clmd->sim_parms->defgoal;
700                         else
701                                 verts->goal= 0.0f;
702
703                         /* Compute base cloth shrink weight */
704                         verts->shrink_factor = 0.0f;
705
706                         /* Reset vertex flags */
707                         verts->flags &= ~CLOTH_VERT_FLAG_PINNED;
708                         verts->flags &= ~CLOTH_VERT_FLAG_NOSELFCOLL;
709
710                         dvert = dm->getVertData ( dm, i, CD_MDEFORMVERT );
711                         if ( dvert ) {
712                                 for ( j = 0; j < dvert->totweight; j++ ) {
713                                         if (( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_mass-1)) && (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )) {
714                                                 verts->goal = dvert->dw [j].weight;
715
716                                                 /* goalfac= 1.0f; */ /* UNUSED */
717                                                 
718                                                 // Kicking goal factor to simplify things...who uses that anyway?
719                                                 // ABS ( clmd->sim_parms->maxgoal - clmd->sim_parms->mingoal );
720                                                 
721                                                 verts->goal  = pow4f(verts->goal);
722                                                 if ( verts->goal >= SOFTGOALSNAP )
723                                                         verts->flags |= CLOTH_VERT_FLAG_PINNED;
724                                         }
725                                         
726                                         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING ) {
727                                                 if ( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_struct-1)) {
728                                                         verts->struct_stiff = dvert->dw [j].weight;
729                                                         verts->shear_stiff = dvert->dw [j].weight;
730                                                 }
731                                                 
732                                                 if ( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_bend-1)) {
733                                                         verts->bend_stiff = dvert->dw [j].weight;
734                                                 }
735                                         }
736
737                                         if (clmd->coll_parms->flags & CLOTH_COLLSETTINGS_FLAG_SELF ) {
738                                                 if ( dvert->dw[j].def_nr == (clmd->coll_parms->vgroup_selfcol-1)) {
739                                                         if (dvert->dw [j].weight > 0.0f) {
740                                                                 verts->flags |= CLOTH_VERT_FLAG_NOSELFCOLL;
741                                                         }
742                                                 }
743                                         }
744                                         if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW ) {
745                                                 if (clmd->sim_parms->vgroup_shrink > 0) {
746                                                         if (dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_shrink - 1)) {
747                                                                 /* used for linear interpolation between min and max shrink factor based on weight */
748                                                                 verts->shrink_factor = dvert->dw[j].weight;
749                                                         }
750                                                 }
751                                         }
752                                 }
753                         }
754                 }
755         }
756 }
757
758 static float cloth_shrink_factor(ClothModifierData *clmd, ClothVertex *verts, int i1, int i2)
759 {
760         if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW ) {
761                 /* linear interpolation between min and max shrink factor based on weight */
762                 float base = 1.0f - clmd->sim_parms->shrink_min;
763                 float delta = clmd->sim_parms->shrink_min - clmd->sim_parms->shrink_max;
764
765                 float k1 = base + delta * verts[i1].shrink_factor;
766                 float k2 = base + delta * verts[i2].shrink_factor;
767
768                 /* Use geometrical mean to average two factors since it behaves better
769                    for diagonals when a rectangle transforms into a trapezoid. */
770                 return sqrtf(k1 * k2);
771         }
772         else
773                 return 1.0f;
774 }
775
776 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float UNUSED(framenr), int first)
777 {
778         int i = 0;
779         MVert *mvert = NULL;
780         ClothVertex *verts = NULL;
781         float (*shapekey_rest)[3] = NULL;
782         float tnull[3] = {0, 0, 0};
783         Cloth *cloth = NULL;
784         float maxdist = 0;
785
786         // If we have a clothObject, free it. 
787         if ( clmd->clothObject != NULL ) {
788                 cloth_free_modifier ( clmd );
789                 if (G.debug_value > 0)
790                         printf("cloth_free_modifier cloth_from_object\n");
791         }
792
793         // Allocate a new cloth object.
794         clmd->clothObject = MEM_callocN ( sizeof ( Cloth ), "cloth" );
795         if ( clmd->clothObject ) {
796                 clmd->clothObject->old_solver_type = 255;
797                 // clmd->clothObject->old_collision_type = 255;
798                 cloth = clmd->clothObject;
799                 clmd->clothObject->edgeset = NULL;
800         }
801         else if (!clmd->clothObject) {
802                 modifier_setError(&(clmd->modifier), "Out of memory on allocating clmd->clothObject");
803                 return 0;
804         }
805
806         // mesh input objects need DerivedMesh
807         if ( !dm )
808                 return 0;
809
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