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