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