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