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