Moved the cloth solver code into a new subfolder/library inside Blender
[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_meshdata_types.h"
37
38 #include "BLI_utildefines.h"
39 #include "BLI_math.h"
40 #include "BLI_edgehash.h"
41 #include "BLI_linklist.h"
42
43 #include "BKE_cdderivedmesh.h"
44 #include "BKE_cloth.h"
45 #include "BKE_effect.h"
46 #include "BKE_global.h"
47 #include "BKE_modifier.h"
48 #include "BKE_pointcache.h"
49
50 #include "BPH_mass_spring.h"
51
52 // #include "PIL_time.h"  /* timing for debug prints */
53
54 /* Our available solvers. */
55 // 255 is the magic reserved number, so NEVER try to put 255 solvers in here!
56 // 254 = MAX!
57 static CM_SOLVER_DEF    solvers [] =
58 {
59         { "Implicit", CM_IMPLICIT, implicit_init, implicit_solver, implicit_free },
60                 // { "Implicit C++", CM_IMPLICITCPP, implicitcpp_init, implicitcpp_solver, implicitcpp_free },
61 };
62
63 /* ********** cloth engine ******* */
64 /* Prototypes for internal functions.
65  */
66 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, float (*vertexCos)[3]);
67 static void cloth_from_mesh ( ClothModifierData *clmd, DerivedMesh *dm );
68 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float framenr, int first);
69 static void cloth_update_springs( ClothModifierData *clmd );
70 static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm );
71 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm );
72
73
74 /******************************************************************************
75  *
76  * External interface called by modifier.c clothModifier functions.
77  *
78  ******************************************************************************/
79 /**
80  * cloth_init - creates a new cloth simulation.
81  *
82  * 1. create object
83  * 2. fill object with standard values or with the GUI settings if given
84  */
85 void cloth_init(ClothModifierData *clmd )
86 {       
87         /* Initialize our new data structure to reasonable values. */
88         clmd->sim_parms->gravity[0] = 0.0;
89         clmd->sim_parms->gravity[1] = 0.0;
90         clmd->sim_parms->gravity[2] = -9.81;
91         clmd->sim_parms->structural = 15.0;
92         clmd->sim_parms->shear = 15.0;
93         clmd->sim_parms->bending = 0.5;
94         clmd->sim_parms->Cdis = 5.0; 
95         clmd->sim_parms->Cvi = 1.0;
96         clmd->sim_parms->mass = 0.3f;
97         clmd->sim_parms->stepsPerFrame = 5;
98         clmd->sim_parms->flags = 0;
99         clmd->sim_parms->solver_type = 0;
100         clmd->sim_parms->preroll = 0;
101         clmd->sim_parms->maxspringlen = 10;
102         clmd->sim_parms->vgroup_mass = 0;
103         clmd->sim_parms->vgroup_shrink = 0;
104         clmd->sim_parms->shrink_min = 0.0f; /* min amount the fabric will shrink by 0.0 = no shrinking, 1.0 = shrink to nothing*/
105         clmd->sim_parms->avg_spring_len = 0.0;
106         clmd->sim_parms->presets = 2; /* cotton as start setting */
107         clmd->sim_parms->timescale = 1.0f; /* speed factor, describes how fast cloth moves */
108         clmd->sim_parms->reset = 0;
109         clmd->sim_parms->vel_damping = 1.0f; /* 1.0 = no damping, 0.0 = fully dampened */
110         
111         clmd->coll_parms->self_friction = 5.0;
112         clmd->coll_parms->friction = 5.0;
113         clmd->coll_parms->loop_count = 2;
114         clmd->coll_parms->epsilon = 0.015f;
115         clmd->coll_parms->flags = CLOTH_COLLSETTINGS_FLAG_ENABLED;
116         clmd->coll_parms->collision_list = NULL;
117         clmd->coll_parms->self_loop_count = 1.0;
118         clmd->coll_parms->selfepsilon = 0.75;
119         clmd->coll_parms->vgroup_selfcol = 0;
120
121         /* These defaults are copied from softbody.c's
122          * softbody_calc_forces() function.
123          */
124         clmd->sim_parms->eff_force_scale = 1000.0;
125         clmd->sim_parms->eff_wind_scale = 250.0;
126
127         // also from softbodies
128         clmd->sim_parms->maxgoal = 1.0f;
129         clmd->sim_parms->mingoal = 0.0f;
130         clmd->sim_parms->defgoal = 0.0f;
131         clmd->sim_parms->goalspring = 1.0f;
132         clmd->sim_parms->goalfrict = 0.0f;
133         clmd->sim_parms->velocity_smooth = 0.0f;
134
135         if (!clmd->sim_parms->effector_weights)
136                 clmd->sim_parms->effector_weights = BKE_add_effector_weights(NULL);
137
138         if (clmd->point_cache)
139                 clmd->point_cache->step = 1;
140 }
141
142 static BVHTree *bvhselftree_build_from_cloth (ClothModifierData *clmd, float epsilon)
143 {
144         unsigned int i;
145         BVHTree *bvhtree;
146         Cloth *cloth;
147         ClothVertex *verts;
148         float co[12];
149
150         if (!clmd)
151                 return NULL;
152
153         cloth = clmd->clothObject;
154
155         if (!cloth)
156                 return NULL;
157         
158         verts = cloth->verts;
159         
160         // in the moment, return zero if no faces there
161         if (!cloth->numverts)
162                 return NULL;
163         
164         // create quadtree with k=26
165         bvhtree = BLI_bvhtree_new(cloth->numverts, epsilon, 4, 6);
166         
167         // fill tree
168         for (i = 0; i < cloth->numverts; i++, verts++) {
169                 copy_v3_v3(&co[0*3], verts->xold);
170                 
171                 BLI_bvhtree_insert(bvhtree, i, co, 1);
172         }
173         
174         // balance tree
175         BLI_bvhtree_balance(bvhtree);
176         
177         return bvhtree;
178 }
179
180 static BVHTree *bvhtree_build_from_cloth (ClothModifierData *clmd, float epsilon)
181 {
182         unsigned int i;
183         BVHTree *bvhtree;
184         Cloth *cloth;
185         ClothVertex *verts;
186         MFace *mfaces;
187         float co[12];
188
189         if (!clmd)
190                 return NULL;
191
192         cloth = clmd->clothObject;
193
194         if (!cloth)
195                 return NULL;
196         
197         verts = cloth->verts;
198         mfaces = cloth->mfaces;
199         
200         /* in the moment, return zero if no faces there */
201         if (!cloth->numfaces)
202                 return NULL;
203
204         /* create quadtree with k=26 */
205         bvhtree = BLI_bvhtree_new(cloth->numfaces, epsilon, 4, 26);
206
207         /* fill tree */
208         for (i = 0; i < cloth->numfaces; i++, mfaces++) {
209                 copy_v3_v3(&co[0*3], verts[mfaces->v1].xold);
210                 copy_v3_v3(&co[1*3], verts[mfaces->v2].xold);
211                 copy_v3_v3(&co[2*3], verts[mfaces->v3].xold);
212
213                 if (mfaces->v4)
214                         copy_v3_v3(&co[3*3], verts[mfaces->v4].xold);
215
216                 BLI_bvhtree_insert(bvhtree, i, co, (mfaces->v4 ? 4 : 3));
217         }
218
219         /* balance tree */
220         BLI_bvhtree_balance(bvhtree);
221         
222         return bvhtree;
223 }
224
225 void bvhtree_update_from_cloth(ClothModifierData *clmd, int moving)
226 {       
227         unsigned int i = 0;
228         Cloth *cloth = clmd->clothObject;
229         BVHTree *bvhtree = cloth->bvhtree;
230         ClothVertex *verts = cloth->verts;
231         MFace *mfaces;
232         float co[12], co_moving[12];
233         bool ret = false;
234         
235         if (!bvhtree)
236                 return;
237         
238         mfaces = cloth->mfaces;
239         
240         // update vertex position in bvh tree
241         if (verts && mfaces) {
242                 for (i = 0; i < cloth->numfaces; i++, mfaces++) {
243                         copy_v3_v3(&co[0*3], verts[mfaces->v1].txold);
244                         copy_v3_v3(&co[1*3], verts[mfaces->v2].txold);
245                         copy_v3_v3(&co[2*3], verts[mfaces->v3].txold);
246                         
247                         if (mfaces->v4)
248                                 copy_v3_v3(&co[3*3], verts[mfaces->v4].txold);
249                 
250                         // copy new locations into array
251                         if (moving) {
252                                 // update moving positions
253                                 copy_v3_v3(&co_moving[0*3], verts[mfaces->v1].tx);
254                                 copy_v3_v3(&co_moving[1*3], verts[mfaces->v2].tx);
255                                 copy_v3_v3(&co_moving[2*3], verts[mfaces->v3].tx);
256                                 
257                                 if (mfaces->v4)
258                                         copy_v3_v3(&co_moving[3*3], verts[mfaces->v4].tx);
259                                 
260                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, co_moving, (mfaces->v4 ? 4 : 3));
261                         }
262                         else {
263                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, NULL, (mfaces->v4 ? 4 : 3));
264                         }
265                         
266                         // check if tree is already full
267                         if (!ret)
268                                 break;
269                 }
270                 
271                 BLI_bvhtree_update_tree(bvhtree);
272         }
273 }
274
275 void bvhselftree_update_from_cloth(ClothModifierData *clmd, int moving)
276 {       
277         unsigned int i = 0;
278         Cloth *cloth = clmd->clothObject;
279         BVHTree *bvhtree = cloth->bvhselftree;
280         ClothVertex *verts = cloth->verts;
281         MFace *mfaces;
282         float co[12], co_moving[12];
283         int ret = 0;
284         
285         if (!bvhtree)
286                 return;
287         
288         mfaces = cloth->mfaces;
289
290         // update vertex position in bvh tree
291         if (verts && mfaces) {
292                 for (i = 0; i < cloth->numverts; i++, verts++) {
293                         copy_v3_v3(&co[0*3], verts->txold);
294
295                         // copy new locations into array
296                         if (moving) {
297                                 // update moving positions
298                                 copy_v3_v3(&co_moving[0*3], verts->tx);
299
300                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, co_moving, 1);
301                         }
302                         else {
303                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, NULL, 1);
304                         }
305
306                         // check if tree is already full
307                         if (!ret)
308                                 break;
309                 }
310                 
311                 BLI_bvhtree_update_tree(bvhtree);
312         }
313 }
314
315 void cloth_clear_cache(Object *ob, ClothModifierData *clmd, float framenr)
316 {
317         PTCacheID pid;
318         
319         BKE_ptcache_id_from_cloth(&pid, ob, clmd);
320
321         // don't do anything as long as we're in editmode!
322         if (pid.cache->edit && ob->mode & OB_MODE_PARTICLE_EDIT)
323                 return;
324         
325         BKE_ptcache_id_clear(&pid, PTCACHE_CLEAR_AFTER, framenr);
326 }
327
328 static int do_init_cloth(Object *ob, ClothModifierData *clmd, DerivedMesh *result, int framenr)
329 {
330         PointCache *cache;
331
332         cache= clmd->point_cache;
333
334         /* initialize simulation data if it didn't exist already */
335         if (clmd->clothObject == NULL) {
336                 if (!cloth_from_object(ob, clmd, result, framenr, 1)) {
337                         BKE_ptcache_invalidate(cache);
338                         modifier_setError(&(clmd->modifier), "Can't initialize cloth");
339                         return 0;
340                 }
341         
342                 if (clmd->clothObject == NULL) {
343                         BKE_ptcache_invalidate(cache);
344                         modifier_setError(&(clmd->modifier), "Null cloth object");
345                         return 0;
346                 }
347         
348                 implicit_set_positions(clmd);
349
350                 clmd->clothObject->last_frame= MINFRAME-1;
351         }
352
353         return 1;
354 }
355
356 static int do_step_cloth(Object *ob, ClothModifierData *clmd, DerivedMesh *result, int framenr)
357 {
358         ClothVertex *verts = NULL;
359         Cloth *cloth;
360         ListBase *effectors = NULL;
361         MVert *mvert;
362         unsigned int i = 0;
363         int ret = 0;
364
365         /* simulate 1 frame forward */
366         cloth = clmd->clothObject;
367         verts = cloth->verts;
368         mvert = result->getVertArray(result);
369
370         /* force any pinned verts to their constrained location. */
371         for (i = 0; i < clmd->clothObject->numverts; i++, verts++) {
372                 /* save the previous position. */
373                 copy_v3_v3(verts->xold, verts->xconst);
374                 copy_v3_v3(verts->txold, verts->x);
375
376                 /* Get the current position. */
377                 copy_v3_v3(verts->xconst, mvert[i].co);
378                 mul_m4_v3(ob->obmat, verts->xconst);
379         }
380
381         effectors = pdInitEffectors(clmd->scene, ob, NULL, clmd->sim_parms->effector_weights, true);
382
383         /* Support for dynamic vertex groups, changing from frame to frame */
384         cloth_apply_vgroup ( clmd, result );
385         cloth_update_springs( clmd );
386         
387         // TIMEIT_START(cloth_step)
388
389         /* call the solver. */
390         if (solvers [clmd->sim_parms->solver_type].solver)
391                 ret = solvers[clmd->sim_parms->solver_type].solver(ob, framenr, clmd, effectors);
392
393         // TIMEIT_END(cloth_step)
394
395         pdEndEffectors(&effectors);
396
397         // printf ( "%f\n", ( float ) tval() );
398         
399         return ret;
400 }
401
402 #if 0
403 static DerivedMesh *cloth_to_triangles(DerivedMesh *dm)
404 {
405         DerivedMesh *result = NULL;
406         unsigned int i = 0, j = 0;
407         unsigned int quads = 0, numfaces = dm->getNumTessFaces(dm);
408         MFace *mface = dm->getTessFaceArray(dm);
409         MFace *mface2 = NULL;
410
411         /* calc faces */
412         for (i = 0; i < numfaces; i++) {
413                 if (mface[i].v4) {
414                         quads++;
415                 }
416         }
417                 
418         result = CDDM_from_template(dm, dm->getNumVerts(dm), 0, numfaces + quads, 0, 0);
419
420         DM_copy_vert_data(dm, result, 0, 0, dm->getNumVerts(dm));
421         DM_copy_tessface_data(dm, result, 0, 0, numfaces);
422
423         DM_ensure_tessface(result);
424         mface2 = result->getTessFaceArray(result);
425
426         for (i = 0, j = numfaces; i < numfaces; i++) {
427                 // DG TODO: is this necessary?
428                 mface2[i].v1 = mface[i].v1;
429                 mface2[i].v2 = mface[i].v2;
430                 mface2[i].v3 = mface[i].v3;
431
432                 mface2[i].v4 = 0;
433                 //test_index_face(&mface2[i], &result->faceData, i, 3);
434
435                 if (mface[i].v4) {
436                         DM_copy_tessface_data(dm, result, i, j, 1);
437
438                         mface2[j].v1 = mface[i].v1;
439                         mface2[j].v2 = mface[i].v3;
440                         mface2[j].v3 = mface[i].v4;
441                         mface2[j].v4 = 0;
442                         //test_index_face(&mface2[j], &result->faceData, j, 3);
443
444                         j++;
445                 }
446         }
447
448         CDDM_calc_edges_tessface(result);
449         CDDM_tessfaces_to_faces(result); /* builds ngon faces from tess (mface) faces */
450
451         return result;
452 }
453 #endif
454
455 /************************************************
456  * clothModifier_do - main simulation function
457  ************************************************/
458 void clothModifier_do(ClothModifierData *clmd, Scene *scene, Object *ob, DerivedMesh *dm, float (*vertexCos)[3])
459 {
460         PointCache *cache;
461         PTCacheID pid;
462         float timescale;
463         int framenr, startframe, endframe;
464         int cache_result;
465
466         clmd->scene= scene;     /* nice to pass on later :) */
467         framenr= (int)scene->r.cfra;
468         cache= clmd->point_cache;
469
470         BKE_ptcache_id_from_cloth(&pid, ob, clmd);
471         BKE_ptcache_id_time(&pid, scene, framenr, &startframe, &endframe, &timescale);
472         clmd->sim_parms->timescale= timescale;
473
474         if (clmd->sim_parms->reset ||
475             (framenr == (startframe - clmd->sim_parms->preroll) && clmd->sim_parms->preroll != 0) ||
476             (clmd->clothObject && dm->getNumVerts(dm) != clmd->clothObject->numverts))
477         {
478                 clmd->sim_parms->reset = 0;
479                 cache->flag |= PTCACHE_OUTDATED;
480                 BKE_ptcache_id_reset(scene, &pid, PTCACHE_RESET_OUTDATED);
481                 BKE_ptcache_validate(cache, 0);
482                 cache->last_exact= 0;
483                 cache->flag &= ~PTCACHE_REDO_NEEDED;
484         }
485         
486         // unused in the moment, calculated separately in implicit.c
487         clmd->sim_parms->dt = clmd->sim_parms->timescale / clmd->sim_parms->stepsPerFrame;
488
489         /* handle continuous simulation with the play button */
490         if ((clmd->sim_parms->preroll > 0) && (framenr > startframe - clmd->sim_parms->preroll) && (framenr < startframe)) {
491                 BKE_ptcache_invalidate(cache);
492
493                 /* do simulation */
494                 if (!do_init_cloth(ob, clmd, dm, framenr))
495                         return;
496
497                 do_step_cloth(ob, clmd, dm, framenr);
498                 cloth_to_object(ob, clmd, vertexCos);
499
500                 clmd->clothObject->last_frame= framenr;
501
502                 return;
503         }
504
505         /* simulation is only active during a specific period */
506         if (framenr < startframe) {
507                 BKE_ptcache_invalidate(cache);
508                 return;
509         }
510         else if (framenr > endframe) {
511                 framenr= endframe;
512         }
513
514         /* initialize simulation data if it didn't exist already */
515         if (!do_init_cloth(ob, clmd, dm, framenr))
516                 return;
517
518         if ((framenr == startframe) && (clmd->sim_parms->preroll == 0)) {
519                 BKE_ptcache_id_reset(scene, &pid, PTCACHE_RESET_OUTDATED);
520                 do_init_cloth(ob, clmd, dm, framenr);
521                 BKE_ptcache_validate(cache, framenr);
522                 cache->flag &= ~PTCACHE_REDO_NEEDED;
523                 clmd->clothObject->last_frame= framenr;
524                 return;
525         }
526
527         /* try to read from cache */
528         cache_result = BKE_ptcache_read(&pid, (float)framenr+scene->r.subframe);
529
530         if (cache_result == PTCACHE_READ_EXACT || cache_result == PTCACHE_READ_INTERPOLATED) {
531                 implicit_set_positions(clmd);
532                 cloth_to_object (ob, clmd, vertexCos);
533
534                 BKE_ptcache_validate(cache, framenr);
535
536                 if (cache_result == PTCACHE_READ_INTERPOLATED && cache->flag & PTCACHE_REDO_NEEDED)
537                         BKE_ptcache_write(&pid, framenr);
538
539                 clmd->clothObject->last_frame= framenr;
540
541                 return;
542         }
543         else if (cache_result==PTCACHE_READ_OLD) {
544                 implicit_set_positions(clmd);
545         }
546         else if ( /*ob->id.lib ||*/ (cache->flag & PTCACHE_BAKED)) { /* 2.4x disabled lib, but this can be used in some cases, testing further - campbell */
547                 /* if baked and nothing in cache, do nothing */
548                 BKE_ptcache_invalidate(cache);
549                 return;
550         }
551
552         if (framenr!=clmd->clothObject->last_frame+1)
553                 return;
554
555         /* if on second frame, write cache for first frame */
556         if (cache->simframe == startframe && (cache->flag & PTCACHE_OUTDATED || cache->last_exact==0))
557                 BKE_ptcache_write(&pid, startframe);
558
559         clmd->sim_parms->timescale *= framenr - cache->simframe;
560
561         /* do simulation */
562         BKE_ptcache_validate(cache, framenr);
563
564         if (!do_step_cloth(ob, clmd, dm, framenr)) {
565                 BKE_ptcache_invalidate(cache);
566         }
567         else
568                 BKE_ptcache_write(&pid, framenr);
569
570         cloth_to_object (ob, clmd, vertexCos);
571         clmd->clothObject->last_frame= framenr;
572 }
573
574 /* frees all */
575 void cloth_free_modifier(ClothModifierData *clmd )
576 {
577         Cloth   *cloth = NULL;
578         
579         if ( !clmd )
580                 return;
581
582         cloth = clmd->clothObject;
583
584         
585         if ( cloth ) {
586                 // If our solver provides a free function, call it
587                 if ( solvers [clmd->sim_parms->solver_type].free ) {
588                         solvers [clmd->sim_parms->solver_type].free ( clmd );
589                 }
590
591                 // Free the verts.
592                 if ( cloth->verts != NULL )
593                         MEM_freeN ( cloth->verts );
594
595                 cloth->verts = NULL;
596                 cloth->numverts = 0;
597
598                 // Free the springs.
599                 if ( cloth->springs != NULL ) {
600                         LinkNode *search = cloth->springs;
601                         while (search) {
602                                 ClothSpring *spring = search->link;
603                                                 
604                                 MEM_freeN ( spring );
605                                 search = search->next;
606                         }
607                         BLI_linklist_free(cloth->springs, NULL);
608                 
609                         cloth->springs = NULL;
610                 }
611
612                 cloth->springs = NULL;
613                 cloth->numsprings = 0;
614
615                 // free BVH collision tree
616                 if ( cloth->bvhtree )
617                         BLI_bvhtree_free ( cloth->bvhtree );
618                 
619                 if ( cloth->bvhselftree )
620                         BLI_bvhtree_free ( cloth->bvhselftree );
621
622                 // we save our faces for collision objects
623                 if ( cloth->mfaces )
624                         MEM_freeN ( cloth->mfaces );
625                 
626                 if (cloth->edgeset)
627                         BLI_edgeset_free(cloth->edgeset);
628                 
629                 
630                 /*
631                 if (clmd->clothObject->facemarks)
632                 MEM_freeN(clmd->clothObject->facemarks);
633                 */
634                 MEM_freeN ( cloth );
635                 clmd->clothObject = NULL;
636         }
637 }
638
639 /* frees all */
640 void cloth_free_modifier_extern(ClothModifierData *clmd )
641 {
642         Cloth   *cloth = NULL;
643         if (G.debug_value > 0)
644                 printf("cloth_free_modifier_extern\n");
645         
646         if ( !clmd )
647                 return;
648
649         cloth = clmd->clothObject;
650         
651         if ( cloth ) {
652                 if (G.debug_value > 0)
653                         printf("cloth_free_modifier_extern in\n");
654
655                 // If our solver provides a free function, call it
656                 if ( solvers [clmd->sim_parms->solver_type].free ) {
657                         solvers [clmd->sim_parms->solver_type].free ( clmd );
658                 }
659
660                 // Free the verts.
661                 if ( cloth->verts != NULL )
662                         MEM_freeN ( cloth->verts );
663
664                 cloth->verts = NULL;
665                 cloth->numverts = 0;
666
667                 // Free the springs.
668                 if ( cloth->springs != NULL ) {
669                         LinkNode *search = cloth->springs;
670                         while (search) {
671                                 ClothSpring *spring = search->link;
672
673                                 MEM_freeN ( spring );
674                                 search = search->next;
675                         }
676                         BLI_linklist_free(cloth->springs, NULL);
677
678                         cloth->springs = NULL;
679                 }
680
681                 cloth->springs = NULL;
682                 cloth->numsprings = 0;
683
684                 // free BVH collision tree
685                 if ( cloth->bvhtree )
686                         BLI_bvhtree_free ( cloth->bvhtree );
687                 
688                 if ( cloth->bvhselftree )
689                         BLI_bvhtree_free ( cloth->bvhselftree );
690
691                 // we save our faces for collision objects
692                 if ( cloth->mfaces )
693                         MEM_freeN ( cloth->mfaces );
694
695                 if (cloth->edgeset)
696                         BLI_edgeset_free(cloth->edgeset);
697
698
699                 /*
700                 if (clmd->clothObject->facemarks)
701                 MEM_freeN(clmd->clothObject->facemarks);
702                 */
703                 MEM_freeN ( cloth );
704                 clmd->clothObject = NULL;
705         }
706 }
707
708 /******************************************************************************
709  *
710  * Internal functions.
711  *
712  ******************************************************************************/
713
714 /**
715  * cloth_to_object - copies the deformed vertices to the object.
716  *
717  **/
718 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, float (*vertexCos)[3])
719 {
720         unsigned int    i = 0;
721         Cloth *cloth = clmd->clothObject;
722
723         if (clmd->clothObject) {
724                 /* inverse matrix is not uptodate... */
725                 invert_m4_m4(ob->imat, ob->obmat);
726
727                 for (i = 0; i < cloth->numverts; i++) {
728                         copy_v3_v3 (vertexCos[i], cloth->verts[i].x);
729                         mul_m4_v3(ob->imat, vertexCos[i]);      /* cloth is in global coords */
730                 }
731         }
732 }
733
734
735 int cloth_uses_vgroup(ClothModifierData *clmd)
736 {
737         return (((clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING ) || 
738                 (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL ) ||
739                 (clmd->coll_parms->flags & CLOTH_COLLSETTINGS_FLAG_SELF)) && 
740                 ((clmd->sim_parms->vgroup_mass>0) || 
741                 (clmd->sim_parms->vgroup_struct>0)||
742                 (clmd->sim_parms->vgroup_bend>0)  ||
743                 (clmd->sim_parms->vgroup_shrink>0) ||
744                 (clmd->coll_parms->vgroup_selfcol>0)));
745 }
746
747 /**
748  * cloth_apply_vgroup - applies a vertex group as specified by type
749  *
750  **/
751 /* can be optimized to do all groups in one loop */
752 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm )
753 {
754         int i = 0;
755         int j = 0;
756         MDeformVert *dvert = NULL;
757         Cloth *clothObj = NULL;
758         int numverts;
759         /* float goalfac = 0; */ /* UNUSED */
760         ClothVertex *verts = NULL;
761
762         if (!clmd || !dm) return;
763
764         clothObj = clmd->clothObject;
765
766         numverts = dm->getNumVerts (dm);
767
768         verts = clothObj->verts;
769         
770         if (cloth_uses_vgroup(clmd)) {
771                 for ( i = 0; i < numverts; i++, verts++ ) {
772
773                         /* Reset Goal values to standard */
774                         if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )
775                                 verts->goal= clmd->sim_parms->defgoal;
776                         else
777                                 verts->goal= 0.0f;
778
779                         /* Reset vertex flags */
780                         verts->flags &= ~CLOTH_VERT_FLAG_PINNED;
781                         verts->flags &= ~CLOTH_VERT_FLAG_NOSELFCOLL;
782
783                         dvert = dm->getVertData ( dm, i, CD_MDEFORMVERT );
784                         if ( dvert ) {
785                                 for ( j = 0; j < dvert->totweight; j++ ) {
786                                         if (( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_mass-1)) && (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )) {
787                                                 verts->goal = dvert->dw [j].weight;
788
789                                                 /* goalfac= 1.0f; */ /* UNUSED */
790                                                 
791                                                 // Kicking goal factor to simplify things...who uses that anyway?
792                                                 // ABS ( clmd->sim_parms->maxgoal - clmd->sim_parms->mingoal );
793                                                 
794                                                 verts->goal  = pow4f(verts->goal);
795                                                 if ( verts->goal >= SOFTGOALSNAP )
796                                                         verts->flags |= CLOTH_VERT_FLAG_PINNED;
797                                         }
798                                         
799                                         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING ) {
800                                                 if ( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_struct-1)) {
801                                                         verts->struct_stiff = dvert->dw [j].weight;
802                                                         verts->shear_stiff = dvert->dw [j].weight;
803                                                 }
804                                                 
805                                                 if ( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_bend-1)) {
806                                                         verts->bend_stiff = dvert->dw [j].weight;
807                                                 }
808                                         }
809
810                                         if (clmd->coll_parms->flags & CLOTH_COLLSETTINGS_FLAG_SELF ) {
811                                                 if ( dvert->dw[j].def_nr == (clmd->coll_parms->vgroup_selfcol-1)) {
812                                                         if (dvert->dw [j].weight > 0.0f) {
813                                                                 verts->flags |= CLOTH_VERT_FLAG_NOSELFCOLL;
814                                                         }
815                                                 }
816
817                                         if (clmd->sim_parms->vgroup_shrink > 0 )
818                                         {
819                                                 if ( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_shrink-1))
820                                                 {
821                                                         verts->shrink_factor = clmd->sim_parms->shrink_min*(1.0f-dvert->dw[j].weight)+clmd->sim_parms->shrink_max*dvert->dw [j].weight; // linear interpolation between min and max shrink factor based on weight
822                                                 }
823                                         }
824                                         else {
825                                                 verts->shrink_factor = clmd->sim_parms->shrink_min;
826                                         }
827
828                                         }
829                                 }
830                         }
831                 }
832         }
833 }
834
835
836 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float UNUSED(framenr), int first)
837 {
838         int i = 0;
839         MVert *mvert = NULL;
840         ClothVertex *verts = NULL;
841         float (*shapekey_rest)[3] = NULL;
842         float tnull[3] = {0, 0, 0};
843         Cloth *cloth = NULL;
844         float maxdist = 0;
845
846         // If we have a clothObject, free it. 
847         if ( clmd->clothObject != NULL ) {
848                 cloth_free_modifier ( clmd );
849                 if (G.debug_value > 0)
850                         printf("cloth_free_modifier cloth_from_object\n");
851         }
852
853         // Allocate a new cloth object.
854         clmd->clothObject = MEM_callocN ( sizeof ( Cloth ), "cloth" );
855         if ( clmd->clothObject ) {
856                 clmd->clothObject->old_solver_type = 255;
857                 // clmd->clothObject->old_collision_type = 255;
858                 cloth = clmd->clothObject;
859                 clmd->clothObject->edgeset = NULL;
860         }
861         else if (!clmd->clothObject) {
862                 modifier_setError(&(clmd->modifier), "Out of memory on allocating clmd->clothObject");
863                 return 0;
864         }
865
866         // mesh input objects need DerivedMesh
867         if ( !dm )
868                 return 0;
869
870         cloth_from_mesh ( clmd, dm );
871
872         // create springs
873         clmd->clothObject->springs = NULL;
874         clmd->clothObject->numsprings = -1;
875
876         if ( clmd->sim_parms->shapekey_rest )
877                 shapekey_rest = dm->getVertDataArray ( dm, CD_CLOTH_ORCO );
878
879         mvert = dm->getVertArray (dm);
880
881         verts = clmd->clothObject->verts;
882
883         // set initial values
884         for ( i = 0; i < dm->getNumVerts(dm); i++, verts++ ) {
885                 if (first) {
886                         copy_v3_v3(verts->x, mvert[i].co);
887
888                         mul_m4_v3(ob->obmat, verts->x);
889
890                         if ( shapekey_rest ) {
891                                 verts->xrest= shapekey_rest[i];
892                                 mul_m4_v3(ob->obmat, verts->xrest);
893                         }
894                         else
895                                 verts->xrest = verts->x;
896                 }
897                 
898                 /* no GUI interface yet */
899                 verts->mass = clmd->sim_parms->mass; 
900                 verts->impulse_count = 0;
901
902                 if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )
903                         verts->goal= clmd->sim_parms->defgoal;
904                 else
905                         verts->goal= 0.0f;
906
907                 verts->flags = 0;
908                 copy_v3_v3 ( verts->xold, verts->x );
909                 copy_v3_v3 ( verts->xconst, verts->x );
910                 copy_v3_v3 ( verts->txold, verts->x );
911                 copy_v3_v3 ( verts->tx, verts->x );
912                 mul_v3_fl(verts->v, 0.0f);
913
914                 verts->impulse_count = 0;
915                 copy_v3_v3 ( verts->impulse, tnull );
916         }
917         
918         // apply / set vertex groups
919         // has to be happen before springs are build!
920         cloth_apply_vgroup (clmd, dm);
921
922         if ( !cloth_build_springs ( clmd, dm ) ) {
923                 cloth_free_modifier ( clmd );
924                 modifier_setError(&(clmd->modifier), "Cannot build springs");
925                 printf("cloth_free_modifier cloth_build_springs\n");
926                 return 0;
927         }
928         
929         for ( i = 0; i < dm->getNumVerts(dm); i++) {
930                 if ((!(cloth->verts[i].flags & CLOTH_VERT_FLAG_PINNED)) && (cloth->verts[i].goal > ALMOST_ZERO)) {
931                         cloth_add_spring (clmd, i, i, 0.0, CLOTH_SPRING_TYPE_GOAL);
932                 }
933         }
934         
935         // init our solver
936         if ( solvers [clmd->sim_parms->solver_type].init ) {
937                 solvers [clmd->sim_parms->solver_type].init ( ob, clmd );
938         }
939         
940         if (!first)
941                 implicit_set_positions(clmd);
942
943         clmd->clothObject->bvhtree = bvhtree_build_from_cloth ( clmd, MAX2(clmd->coll_parms->epsilon, clmd->coll_parms->distance_repel) );
944         
945         for (i = 0; i < dm->getNumVerts(dm); i++) {
946                 maxdist = MAX2(maxdist, clmd->coll_parms->selfepsilon* ( cloth->verts[i].avg_spring_len*2.0f));
947         }
948         
949         clmd->clothObject->bvhselftree = bvhselftree_build_from_cloth ( clmd, maxdist );
950
951         return 1;
952 }
953
954 static void cloth_from_mesh ( ClothModifierData *clmd, DerivedMesh *dm )
955 {
956         unsigned int numverts = dm->getNumVerts (dm);
957         unsigned int numfaces = dm->getNumTessFaces (dm);
958         MFace *mface = dm->getTessFaceArray(dm);
959         unsigned int i = 0;
960
961         /* Allocate our vertices. */
962         clmd->clothObject->numverts = numverts;
963         clmd->clothObject->verts = MEM_callocN ( sizeof ( ClothVertex ) * clmd->clothObject->numverts, "clothVertex" );
964         if ( clmd->clothObject->verts == NULL ) {
965                 cloth_free_modifier ( clmd );
966                 modifier_setError(&(clmd->modifier), "Out of memory on allocating clmd->clothObject->verts");
967                 printf("cloth_free_modifier clmd->clothObject->verts\n");
968                 return;
969         }
970
971         // save face information
972         clmd->clothObject->numfaces = numfaces;
973         clmd->clothObject->mfaces = MEM_callocN ( sizeof ( MFace ) * clmd->clothObject->numfaces, "clothMFaces" );
974         if ( clmd->clothObject->mfaces == NULL ) {
975                 cloth_free_modifier ( clmd );
976                 modifier_setError(&(clmd->modifier), "Out of memory on allocating clmd->clothObject->mfaces");
977                 printf("cloth_free_modifier clmd->clothObject->mfaces\n");
978                 return;
979         }
980         for ( i = 0; i < numfaces; i++ )
981                 memcpy ( &clmd->clothObject->mfaces[i], &mface[i], sizeof ( MFace ) );
982
983         /* Free the springs since they can't be correct if the vertices
984          * changed.
985          */
986         if ( clmd->clothObject->springs != NULL )
987                 MEM_freeN ( clmd->clothObject->springs );
988
989 }
990
991 /***************************************************************************************
992  * SPRING NETWORK BUILDING IMPLEMENTATION BEGIN
993  ***************************************************************************************/
994
995 BLI_INLINE void spring_verts_ordered_set(ClothSpring *spring, int v0, int v1)
996 {
997         if (v0 < v1) {
998                 spring->ij = v0;
999                 spring->kl = v1;
1000         }
1001         else {
1002                 spring->ij = v1;
1003                 spring->kl = v0;
1004         }
1005 }
1006
1007 // be careful: implicit solver has to be resettet when using this one!
1008 // --> only for implicit handling of this spring!
1009 int cloth_add_spring(ClothModifierData *clmd, unsigned int indexA, unsigned int indexB, float restlength, int spring_type)
1010 {
1011         Cloth *cloth = clmd->clothObject;
1012         ClothSpring *spring = NULL;
1013         
1014         if (cloth) {
1015                 // TODO: look if this spring is already there
1016                 
1017                 spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1018                 
1019                 if (!spring)
1020                         return 0;
1021                 
1022                 spring->ij = indexA;
1023                 spring->kl = indexB;
1024                 spring->restlen =  restlength;
1025                 spring->type = spring_type;
1026                 spring->flags = 0;
1027                 spring->stiffness = 0;
1028                 
1029                 cloth->numsprings++;
1030         
1031                 BLI_linklist_prepend ( &cloth->springs, spring );
1032                 
1033                 return 1;
1034         }
1035         return 0;
1036 }
1037
1038 static void cloth_free_edgelist(LinkNode **edgelist, unsigned int numverts)
1039 {
1040         if (edgelist) {
1041                 unsigned int i;
1042                 for (i = 0; i < numverts; i++) {
1043                         BLI_linklist_free(edgelist[i], NULL);
1044                 }
1045
1046                 MEM_freeN(edgelist);
1047         }
1048 }
1049
1050 static void cloth_free_errorsprings(Cloth *cloth,  LinkNode **edgelist)
1051 {
1052         if ( cloth->springs != NULL ) {
1053                 LinkNode *search = cloth->springs;
1054                 while (search) {
1055                         ClothSpring *spring = search->link;
1056                                                 
1057                         MEM_freeN ( spring );
1058                         search = search->next;
1059                 }
1060                 BLI_linklist_free(cloth->springs, NULL);
1061                 
1062                 cloth->springs = NULL;
1063         }
1064
1065         cloth_free_edgelist(edgelist, cloth->numverts);
1066         
1067         if (cloth->edgeset) {
1068                 BLI_edgeset_free(cloth->edgeset);
1069                 cloth->edgeset = NULL;
1070         }
1071 }
1072
1073 /* update stiffness if vertex group values are changing from frame to frame */
1074 static void cloth_update_springs( ClothModifierData *clmd )
1075 {
1076         Cloth *cloth = clmd->clothObject;
1077         LinkNode *search = NULL;
1078
1079         search = cloth->springs;
1080         while (search) {
1081                 ClothSpring *spring = search->link;
1082
1083                 spring->stiffness = 0.0f;
1084
1085                 if (spring->type == CLOTH_SPRING_TYPE_STRUCTURAL) {
1086                         spring->stiffness = (cloth->verts[spring->kl].struct_stiff + cloth->verts[spring->ij].struct_stiff) / 2.0f;
1087                 }
1088                 else if (spring->type == CLOTH_SPRING_TYPE_SHEAR) {
1089                         spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0f;
1090                 }
1091                 else if (spring->type == CLOTH_SPRING_TYPE_BENDING) {
1092                         spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].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
1112 }
1113
1114 static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm )
1115 {
1116         Cloth *cloth = clmd->clothObject;
1117         ClothSpring *spring = NULL, *tspring = NULL, *tspring2 = NULL;
1118         unsigned int struct_springs = 0, shear_springs=0, bend_springs = 0;
1119         unsigned int i = 0;
1120         unsigned int numverts = (unsigned int)dm->getNumVerts (dm);
1121         unsigned int numedges = (unsigned int)dm->getNumEdges (dm);
1122         unsigned int numfaces = (unsigned int)dm->getNumTessFaces (dm);
1123         float shrink_factor;
1124         MEdge *medge = dm->getEdgeArray (dm);
1125         MFace *mface = dm->getTessFaceArray (dm);
1126         int index2 = 0; // our second vertex index
1127         LinkNode **edgelist = NULL;
1128         EdgeSet *edgeset = NULL;
1129         LinkNode *search = NULL, *search2 = NULL;
1130         
1131         // error handling
1132         if ( numedges==0 )
1133                 return 0;
1134
1135         /* NOTE: handling ownership of springs and edgeset is quite sloppy
1136          * currently they are never initialized but assert just to be sure */
1137         BLI_assert(cloth->springs == NULL);
1138         BLI_assert(cloth->edgeset == NULL);
1139
1140         cloth->springs = NULL;
1141         cloth->edgeset = NULL;
1142
1143         edgelist = MEM_callocN ( sizeof (LinkNode *) * numverts, "cloth_edgelist_alloc" );
1144         
1145         if (!edgelist)
1146                 return 0;
1147
1148         // structural springs
1149         for ( i = 0; i < numedges; i++ ) {
1150                 spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1151
1152                 if ( spring ) {
1153                         spring_verts_ordered_set(spring, medge[i].v1, medge[i].v2);
1154                         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW && medge[i].flag & ME_LOOSEEDGE) {
1155                                 // handle sewing (loose edges will be pulled together)
1156                                 spring->restlen = 0.0f;
1157                                 spring->stiffness = 1.0f;
1158                                 spring->type = CLOTH_SPRING_TYPE_SEWING;
1159                         }
1160                         else {
1161                                 if (clmd->sim_parms->vgroup_shrink > 0)
1162                                         shrink_factor = 1.0f - ((cloth->verts[spring->ij].shrink_factor + cloth->verts[spring->kl].shrink_factor) / 2.0f);
1163                                 else
1164                                         shrink_factor = 1.0f - clmd->sim_parms->shrink_min;
1165                                 spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest) * shrink_factor;
1166                                 spring->stiffness = (cloth->verts[spring->kl].struct_stiff + cloth->verts[spring->ij].struct_stiff) / 2.0f;
1167                                 spring->type = CLOTH_SPRING_TYPE_STRUCTURAL;
1168                         }
1169                         clmd->sim_parms->avg_spring_len += spring->restlen;
1170                         cloth->verts[spring->ij].avg_spring_len += spring->restlen;
1171                         cloth->verts[spring->kl].avg_spring_len += spring->restlen;
1172                         cloth->verts[spring->ij].spring_count++;
1173                         cloth->verts[spring->kl].spring_count++;
1174                         spring->flags = 0;
1175                         struct_springs++;
1176                         
1177                         BLI_linklist_prepend ( &cloth->springs, spring );
1178                 }
1179                 else {
1180                         cloth_free_errorsprings(cloth, edgelist);
1181                         return 0;
1182                 }
1183         }
1184
1185         if (struct_springs > 0)
1186                 clmd->sim_parms->avg_spring_len /= struct_springs;
1187         
1188         for (i = 0; i < numverts; i++) {
1189                 cloth->verts[i].avg_spring_len = cloth->verts[i].avg_spring_len * 0.49f / ((float)cloth->verts[i].spring_count);
1190         }
1191
1192         // shear springs
1193         for ( i = 0; i < numfaces; i++ ) {
1194                 // triangle faces already have shear springs due to structural geometry
1195                 if ( !mface[i].v4 )
1196                         continue;
1197
1198                 spring = (ClothSpring *)MEM_callocN(sizeof(ClothSpring), "cloth spring");
1199                 
1200                 if (!spring) {
1201                         cloth_free_errorsprings(cloth, edgelist);
1202                         return 0;
1203                 }
1204
1205                 spring_verts_ordered_set(spring, mface[i].v1, mface[i].v3);
1206                 if (clmd->sim_parms->vgroup_shrink > 0)
1207                         shrink_factor = 1.0f - ((cloth->verts[spring->ij].shrink_factor + cloth->verts[spring->kl].shrink_factor) / 2.0f);
1208                 else
1209                         shrink_factor = 1.0f - clmd->sim_parms->shrink_min;
1210                 spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest) * shrink_factor;
1211                 spring->type = CLOTH_SPRING_TYPE_SHEAR;
1212                 spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0f;
1213
1214                 BLI_linklist_append ( &edgelist[spring->ij], spring );
1215                 BLI_linklist_append ( &edgelist[spring->kl], spring );
1216                 shear_springs++;
1217
1218                 BLI_linklist_prepend ( &cloth->springs, spring );
1219
1220                 
1221                 // if ( mface[i].v4 ) --> Quad face
1222                 spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1223                 
1224                 if (!spring) {
1225                         cloth_free_errorsprings(cloth, edgelist);
1226                         return 0;
1227                 }
1228
1229                 spring_verts_ordered_set(spring, mface[i].v2, mface[i].v4);
1230                 if (clmd->sim_parms->vgroup_shrink > 0)
1231                         shrink_factor = 1.0f - ((cloth->verts[spring->ij].shrink_factor + cloth->verts[spring->kl].shrink_factor) / 2.0f);
1232                 else
1233                         shrink_factor = 1.0f - clmd->sim_parms->shrink_min;
1234                 spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest) * shrink_factor;
1235                 spring->type = CLOTH_SPRING_TYPE_SHEAR;
1236                 spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0f;
1237
1238                 BLI_linklist_append ( &edgelist[spring->ij], spring );
1239                 BLI_linklist_append ( &edgelist[spring->kl], spring );
1240                 shear_springs++;
1241
1242                 BLI_linklist_prepend ( &cloth->springs, spring );
1243         }
1244
1245         edgeset = BLI_edgeset_new_ex(__func__, numedges);
1246         cloth->edgeset = edgeset;
1247
1248         if (numfaces) {
1249                 // bending springs
1250                 search2 = cloth->springs;
1251                 for ( i = struct_springs; i < struct_springs+shear_springs; i++ ) {
1252                         if ( !search2 )
1253                                 break;
1254
1255                         tspring2 = search2->link;
1256                         search = edgelist[tspring2->kl];
1257                         while ( search ) {
1258                                 tspring = search->link;
1259                                 index2 = ( ( tspring->ij==tspring2->kl ) ? ( tspring->kl ) : ( tspring->ij ) );
1260
1261                                 // check for existing spring
1262                                 // check also if startpoint is equal to endpoint
1263                                 if ((index2 != tspring2->ij) &&
1264                                     !BLI_edgeset_haskey(edgeset, tspring2->ij, index2))
1265                                 {
1266                                         spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1267
1268                                         if (!spring) {
1269                                                 cloth_free_errorsprings(cloth, edgelist);
1270                                                 return 0;
1271                                         }
1272
1273                                         spring_verts_ordered_set(spring, tspring2->ij, index2);
1274                                         spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1275                                         spring->type = CLOTH_SPRING_TYPE_BENDING;
1276                                         spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0f;
1277                                         BLI_edgeset_insert(edgeset, spring->ij, spring->kl);
1278                                         bend_springs++;
1279
1280                                         BLI_linklist_prepend ( &cloth->springs, spring );
1281                                 }
1282                                 search = search->next;
1283                         }
1284                         search2 = search2->next;
1285                 }
1286         }
1287         else if (struct_springs > 2) {
1288                 /* bending springs for hair strands */
1289                 /* The current algorightm only goes through the edges in order of the mesh edges list   */
1290                 /* and makes springs between the outer vert of edges sharing a vertice. This works just */
1291                 /* fine for hair, but not for user generated string meshes. This could/should be later  */
1292                 /* extended to work with non-ordered edges so that it can be used for general "rope             */
1293                 /* dynamics" without the need for the vertices or edges to be ordered through the length*/
1294                 /* of the strands. -jahka */
1295                 search = cloth->springs;
1296                 search2 = search->next;
1297                 while (search && search2) {
1298                         tspring = search->link;
1299                         tspring2 = search2->link;
1300
1301                         if (tspring->ij == tspring2->kl) {
1302                                 spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1303                                 
1304                                 if (!spring) {
1305                                         cloth_free_errorsprings(cloth, edgelist);
1306                                         return 0;
1307                                 }
1308
1309                                 spring->ij = tspring2->ij;
1310                                 spring->kl = tspring->kl;
1311                                 spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1312                                 spring->type = CLOTH_SPRING_TYPE_BENDING;
1313                                 spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0f;
1314                                 bend_springs++;
1315
1316                                 BLI_linklist_prepend ( &cloth->springs, spring );
1317                         }
1318                         
1319                         search = search->next;
1320                         search2 = search2->next;
1321                 }
1322         }
1323         
1324         /* note: the edges may already exist so run reinsert */
1325
1326         /* insert other near springs in edgeset AFTER bending springs are calculated (for selfcolls) */
1327         for (i = 0; i < numedges; i++) { /* struct springs */
1328                 BLI_edgeset_add(edgeset, medge[i].v1, medge[i].v2);
1329         }
1330
1331         for (i = 0; i < numfaces; i++) { /* edge springs */
1332                 if (mface[i].v4) {
1333                         BLI_edgeset_add(edgeset, mface[i].v1, mface[i].v3);
1334                         
1335                         BLI_edgeset_add(edgeset, mface[i].v2, mface[i].v4);
1336                 }
1337         }
1338         
1339         
1340         cloth->numsprings = struct_springs + shear_springs + bend_springs;
1341         
1342         cloth_free_edgelist(edgelist, numverts);
1343
1344 #if 0
1345         if (G.debug_value > 0)
1346                 printf("avg_len: %f\n", clmd->sim_parms->avg_spring_len);
1347 #endif
1348
1349         return 1;
1350
1351 } /* cloth_build_springs */
1352 /***************************************************************************************
1353  * SPRING NETWORK BUILDING IMPLEMENTATION END
1354  ***************************************************************************************/
1355