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