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