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