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