Fix infinite recursion when using adjustment strip placed to channel 1
[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                 if ((clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL) && 
404                         ((!(cloth->verts[i].flags & CLOTH_VERT_FLAG_PINNED)) 
405                         && (cloth->verts[i].goal > ALMOST_ZERO)))
406                 {
407                         copy_v3_v3(verts->xconst, mvert[i].co);
408                         mul_m4_v3(ob->obmat, verts->xconst);
409                 }
410                 else
411                 {
412                         /* This fixed animated goals not to jump back to "first frame position" */
413                         copy_v3_v3(verts->xconst, verts->txold);
414                 }
415         }
416
417         effectors = pdInitEffectors(clmd->scene, ob, NULL, clmd->sim_parms->effector_weights);
418
419         /* Support for dynamic vertex groups, changing from frame to frame */
420         cloth_apply_vgroup ( clmd, result );
421         cloth_update_springs( clmd );
422         
423         tstart();
424
425         /* call the solver. */
426         if (solvers [clmd->sim_parms->solver_type].solver)
427                 ret = solvers[clmd->sim_parms->solver_type].solver(ob, framenr, clmd, effectors);
428
429         tend();
430
431         pdEndEffectors(&effectors);
432
433         // printf ( "%f\n", ( float ) tval() );
434         
435         return ret;
436 }
437
438 #if 0
439 static DerivedMesh *cloth_to_triangles(DerivedMesh *dm)
440 {
441         DerivedMesh *result = NULL;
442         unsigned int i = 0, j = 0;
443         unsigned int quads = 0, numfaces = dm->getNumTessFaces(dm);
444         MFace *mface = dm->getTessFaceArray(dm);
445         MFace *mface2 = NULL;
446
447         /* calc faces */
448         for (i = 0; i < numfaces; i++) {
449                 if (mface[i].v4) {
450                         quads++;
451                 }
452         }
453                 
454         result = CDDM_from_template(dm, dm->getNumVerts(dm), 0, numfaces + quads, 0, 0);
455
456         DM_copy_vert_data(dm, result, 0, 0, dm->getNumVerts(dm));
457         DM_copy_tessface_data(dm, result, 0, 0, numfaces);
458
459         DM_ensure_tessface(result);
460         mface2 = result->getTessFaceArray(result);
461
462         for (i = 0, j = numfaces; i < numfaces; i++) {
463                 // DG TODO: is this necessary?
464                 mface2[i].v1 = mface[i].v1;
465                 mface2[i].v2 = mface[i].v2;
466                 mface2[i].v3 = mface[i].v3;
467
468                 mface2[i].v4 = 0;
469                 //test_index_face(&mface2[i], &result->faceData, i, 3);
470
471                 if (mface[i].v4) {
472                         DM_copy_tessface_data(dm, result, i, j, 1);
473
474                         mface2[j].v1 = mface[i].v1;
475                         mface2[j].v2 = mface[i].v3;
476                         mface2[j].v3 = mface[i].v4;
477                         mface2[j].v4 = 0;
478                         //test_index_face(&mface2[j], &result->faceData, j, 3);
479
480                         j++;
481                 }
482         }
483
484         CDDM_calc_edges_tessface(result);
485         CDDM_tessfaces_to_faces(result); /* builds ngon faces from tess (mface) faces */
486
487         return result;
488 }
489 #endif
490
491 /************************************************
492  * clothModifier_do - main simulation function
493  ************************************************/
494 void clothModifier_do(ClothModifierData *clmd, Scene *scene, Object *ob, DerivedMesh *dm, float (*vertexCos)[3])
495 {
496         PointCache *cache;
497         PTCacheID pid;
498         float timescale;
499         int framenr, startframe, endframe;
500         int cache_result;
501
502         clmd->scene= scene;     /* nice to pass on later :) */
503         framenr= (int)scene->r.cfra;
504         cache= clmd->point_cache;
505
506         BKE_ptcache_id_from_cloth(&pid, ob, clmd);
507         BKE_ptcache_id_time(&pid, scene, framenr, &startframe, &endframe, &timescale);
508         clmd->sim_parms->timescale= timescale;
509
510         if (clmd->sim_parms->reset ||
511             (framenr == (startframe - clmd->sim_parms->preroll) && clmd->sim_parms->preroll != 0) ||
512             (clmd->clothObject && dm->getNumVerts(dm) != clmd->clothObject->numverts))
513         {
514                 clmd->sim_parms->reset = 0;
515                 cache->flag |= PTCACHE_OUTDATED;
516                 BKE_ptcache_id_reset(scene, &pid, PTCACHE_RESET_OUTDATED);
517                 BKE_ptcache_validate(cache, 0);
518                 cache->last_exact= 0;
519                 cache->flag &= ~PTCACHE_REDO_NEEDED;
520                 return;
521         }
522         
523         // unused in the moment, calculated separately in implicit.c
524         clmd->sim_parms->dt = clmd->sim_parms->timescale / clmd->sim_parms->stepsPerFrame;
525
526         /* handle continuous simulation with the play button */
527         if (BKE_ptcache_get_continue_physics() || ((clmd->sim_parms->preroll > 0) && (framenr > startframe - clmd->sim_parms->preroll) && (framenr < startframe))) {
528                 BKE_ptcache_invalidate(cache);
529
530                 /* do simulation */
531                 if (!do_init_cloth(ob, clmd, dm, framenr))
532                         return;
533
534                 do_step_cloth(ob, clmd, dm, framenr);
535                 cloth_to_object(ob, clmd, vertexCos);
536
537                 clmd->clothObject->last_frame= framenr;
538
539                 return;
540         }
541
542         /* simulation is only active during a specific period */
543         if (framenr < startframe) {
544                 BKE_ptcache_invalidate(cache);
545                 return;
546         }
547         else if (framenr > endframe) {
548                 framenr= endframe;
549         }
550
551         /* initialize simulation data if it didn't exist already */
552         if (!do_init_cloth(ob, clmd, dm, framenr))
553                 return;
554
555         if ((framenr == startframe) && (clmd->sim_parms->preroll == 0)) {
556                 BKE_ptcache_id_reset(scene, &pid, PTCACHE_RESET_OUTDATED);
557                 do_init_cloth(ob, clmd, dm, framenr);
558                 BKE_ptcache_validate(cache, framenr);
559                 cache->flag &= ~PTCACHE_REDO_NEEDED;
560                 clmd->clothObject->last_frame= framenr;
561                 return;
562         }
563
564         /* try to read from cache */
565         cache_result = BKE_ptcache_read(&pid, (float)framenr+scene->r.subframe);
566
567         if (cache_result == PTCACHE_READ_EXACT || cache_result == PTCACHE_READ_INTERPOLATED) {
568                 implicit_set_positions(clmd);
569                 cloth_to_object (ob, clmd, vertexCos);
570
571                 BKE_ptcache_validate(cache, framenr);
572
573                 if (cache_result == PTCACHE_READ_INTERPOLATED && cache->flag & PTCACHE_REDO_NEEDED)
574                         BKE_ptcache_write(&pid, framenr);
575
576                 clmd->clothObject->last_frame= framenr;
577
578                 return;
579         }
580         else if (cache_result==PTCACHE_READ_OLD) {
581                 implicit_set_positions(clmd);
582         }
583         else if ( /*ob->id.lib ||*/ (cache->flag & PTCACHE_BAKED)) { /* 2.4x disabled lib, but this can be used in some cases, testing further - campbell */
584                 /* if baked and nothing in cache, do nothing */
585                 BKE_ptcache_invalidate(cache);
586                 return;
587         }
588
589         if (framenr!=clmd->clothObject->last_frame+1)
590                 return;
591
592         /* if on second frame, write cache for first frame */
593         if (cache->simframe == startframe && (cache->flag & PTCACHE_OUTDATED || cache->last_exact==0))
594                 BKE_ptcache_write(&pid, startframe);
595
596         clmd->sim_parms->timescale *= framenr - cache->simframe;
597
598         /* do simulation */
599         BKE_ptcache_validate(cache, framenr);
600
601         if (!do_step_cloth(ob, clmd, dm, framenr)) {
602                 BKE_ptcache_invalidate(cache);
603         }
604         else
605                 BKE_ptcache_write(&pid, framenr);
606
607         cloth_to_object (ob, clmd, vertexCos);
608         clmd->clothObject->last_frame= framenr;
609 }
610
611 /* frees all */
612 void cloth_free_modifier(ClothModifierData *clmd )
613 {
614         Cloth   *cloth = NULL;
615         
616         if ( !clmd )
617                 return;
618
619         cloth = clmd->clothObject;
620
621         
622         if ( cloth ) {
623                 // If our solver provides a free function, call it
624                 if ( solvers [clmd->sim_parms->solver_type].free ) {
625                         solvers [clmd->sim_parms->solver_type].free ( clmd );
626                 }
627
628                 // Free the verts.
629                 if ( cloth->verts != NULL )
630                         MEM_freeN ( cloth->verts );
631
632                 cloth->verts = NULL;
633                 cloth->numverts = 0;
634
635                 // Free the springs.
636                 if ( cloth->springs != NULL ) {
637                         LinkNode *search = cloth->springs;
638                         while (search) {
639                                 ClothSpring *spring = search->link;
640                                                 
641                                 MEM_freeN ( spring );
642                                 search = search->next;
643                         }
644                         BLI_linklist_free(cloth->springs, NULL);
645                 
646                         cloth->springs = NULL;
647                 }
648
649                 cloth->springs = NULL;
650                 cloth->numsprings = 0;
651
652                 // free BVH collision tree
653                 if ( cloth->bvhtree )
654                         BLI_bvhtree_free ( cloth->bvhtree );
655                 
656                 if ( cloth->bvhselftree )
657                         BLI_bvhtree_free ( cloth->bvhselftree );
658
659                 // we save our faces for collision objects
660                 if ( cloth->mfaces )
661                         MEM_freeN ( cloth->mfaces );
662                 
663                 if (cloth->edgehash)
664                         BLI_edgehash_free ( cloth->edgehash, NULL );
665                 
666                 
667                 /*
668                 if (clmd->clothObject->facemarks)
669                 MEM_freeN(clmd->clothObject->facemarks);
670                 */
671                 MEM_freeN ( cloth );
672                 clmd->clothObject = NULL;
673         }
674 }
675
676 /* frees all */
677 void cloth_free_modifier_extern(ClothModifierData *clmd )
678 {
679         Cloth   *cloth = NULL;
680         if (G.debug_value > 0)
681                 printf("cloth_free_modifier_extern\n");
682         
683         if ( !clmd )
684                 return;
685
686         cloth = clmd->clothObject;
687         
688         if ( cloth ) {
689                 if (G.debug_value > 0)
690                         printf("cloth_free_modifier_extern in\n");
691
692                 // If our solver provides a free function, call it
693                 if ( solvers [clmd->sim_parms->solver_type].free ) {
694                         solvers [clmd->sim_parms->solver_type].free ( clmd );
695                 }
696
697                 // Free the verts.
698                 if ( cloth->verts != NULL )
699                         MEM_freeN ( cloth->verts );
700
701                 cloth->verts = NULL;
702                 cloth->numverts = 0;
703
704                 // Free the springs.
705                 if ( cloth->springs != NULL ) {
706                         LinkNode *search = cloth->springs;
707                         while (search) {
708                                 ClothSpring *spring = search->link;
709
710                                 MEM_freeN ( spring );
711                                 search = search->next;
712                         }
713                         BLI_linklist_free(cloth->springs, NULL);
714
715                         cloth->springs = NULL;
716                 }
717
718                 cloth->springs = NULL;
719                 cloth->numsprings = 0;
720
721                 // free BVH collision tree
722                 if ( cloth->bvhtree )
723                         BLI_bvhtree_free ( cloth->bvhtree );
724                 
725                 if ( cloth->bvhselftree )
726                         BLI_bvhtree_free ( cloth->bvhselftree );
727
728                 // we save our faces for collision objects
729                 if ( cloth->mfaces )
730                         MEM_freeN ( cloth->mfaces );
731
732                 if (cloth->edgehash)
733                         BLI_edgehash_free ( cloth->edgehash, NULL );
734
735
736                 /*
737                 if (clmd->clothObject->facemarks)
738                 MEM_freeN(clmd->clothObject->facemarks);
739                 */
740                 MEM_freeN ( cloth );
741                 clmd->clothObject = NULL;
742         }
743 }
744
745 /******************************************************************************
746  *
747  * Internal functions.
748  *
749  ******************************************************************************/
750
751 /**
752  * cloth_to_object - copies the deformed vertices to the object.
753  *
754  **/
755 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, float (*vertexCos)[3])
756 {
757         unsigned int    i = 0;
758         Cloth *cloth = clmd->clothObject;
759
760         if (clmd->clothObject) {
761                 /* inverse matrix is not uptodate... */
762                 invert_m4_m4(ob->imat, ob->obmat);
763
764                 for (i = 0; i < cloth->numverts; i++) {
765                         copy_v3_v3 (vertexCos[i], cloth->verts[i].x);
766                         mul_m4_v3(ob->imat, vertexCos[i]);      /* cloth is in global coords */
767                 }
768         }
769 }
770
771
772 int cloth_uses_vgroup(ClothModifierData *clmd)
773 {
774         return (((clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING ) || 
775                 (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL ) ||
776                 (clmd->coll_parms->flags & CLOTH_COLLSETTINGS_FLAG_SELF)) && 
777                 ((clmd->sim_parms->vgroup_mass>0) || 
778                 (clmd->sim_parms->vgroup_struct>0)||
779                 (clmd->sim_parms->vgroup_bend>0)  ||
780                 (clmd->coll_parms->vgroup_selfcol>0)));
781 }
782
783 /**
784  * cloth_apply_vgroup - applies a vertex group as specified by type
785  *
786  **/
787 /* can be optimized to do all groups in one loop */
788 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm )
789 {
790         int i = 0;
791         int j = 0;
792         MDeformVert *dvert = NULL;
793         Cloth *clothObj = NULL;
794         int numverts;
795         /* float goalfac = 0; */ /* UNUSED */
796         ClothVertex *verts = NULL;
797
798         if (!clmd || !dm) return;
799
800         clothObj = clmd->clothObject;
801
802         numverts = dm->getNumVerts (dm);
803
804         verts = clothObj->verts;
805         
806         if (cloth_uses_vgroup(clmd)) {
807                 for ( i = 0; i < numverts; i++, verts++ ) {
808
809                         /* Reset Goal values to standard */
810                         if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )
811                                 verts->goal= clmd->sim_parms->defgoal;
812                         else
813                                 verts->goal= 0.0f;
814
815                         dvert = dm->getVertData ( dm, i, CD_MDEFORMVERT );
816                         if ( dvert ) {
817
818                                 for ( j = 0; j < dvert->totweight; j++ ) {
819                                         verts->flags &= ~CLOTH_VERT_FLAG_PINNED;
820                                         if (( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_mass-1)) && (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )) {
821                                                 verts->goal = dvert->dw [j].weight;
822
823                                                 /* goalfac= 1.0f; */ /* UNUSED */
824                                                 
825                                                 /*
826                                                 // Kicking goal factor to simplify things...who uses that anyway?
827                                                 // ABS ( clmd->sim_parms->maxgoal - clmd->sim_parms->mingoal );
828                                                 */
829                                                 
830                                                 verts->goal  = powf(verts->goal, 4.0f);
831                                                 if ( verts->goal >=SOFTGOALSNAP )
832                                                          verts->flags |= CLOTH_VERT_FLAG_PINNED;
833                                         }
834                                         
835                                         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING ) {
836                                                 if ( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_struct-1)) {
837                                                         verts->struct_stiff = dvert->dw [j].weight;
838                                                         verts->shear_stiff = dvert->dw [j].weight;
839                                                 }
840                                                 
841                                                 if ( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_bend-1)) {
842                                                         verts->bend_stiff = dvert->dw [j].weight;
843                                                 }
844                                         }
845
846                                         verts->flags &= ~CLOTH_VERT_FLAG_NOSELFCOLL;
847                                         if (clmd->coll_parms->flags & CLOTH_COLLSETTINGS_FLAG_SELF ) {
848                                                 if ( dvert->dw[j].def_nr == (clmd->coll_parms->vgroup_selfcol-1)) {
849                                                         if (dvert->dw [j].weight > 0.0f) {
850                                                                 verts->flags |= CLOTH_VERT_FLAG_NOSELFCOLL;
851                                                         }
852                                                 }
853                                         }
854                                 }
855                         }
856                 }
857         }
858 }
859
860 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float UNUSED(framenr), int first)
861 {
862         int i = 0;
863         MVert *mvert = NULL;
864         ClothVertex *verts = NULL;
865         float (*shapekey_rest)[3]= NULL;
866         float tnull[3] = {0, 0, 0};
867         Cloth *cloth = NULL;
868         float maxdist = 0;
869
870         // If we have a clothObject, free it. 
871         if ( clmd->clothObject != NULL ) {
872                 cloth_free_modifier ( clmd );
873                 if (G.debug_value > 0)
874                         printf("cloth_free_modifier cloth_from_object\n");
875         }
876
877         // Allocate a new cloth object.
878         clmd->clothObject = MEM_callocN ( sizeof ( Cloth ), "cloth" );
879         if ( clmd->clothObject ) {
880                 clmd->clothObject->old_solver_type = 255;
881                 // clmd->clothObject->old_collision_type = 255;
882                 cloth = clmd->clothObject;
883                 clmd->clothObject->edgehash = NULL;
884         }
885         else if (!clmd->clothObject) {
886                 modifier_setError(&(clmd->modifier), "%s", TIP_("Out of memory on allocating clmd->clothObject."));
887                 return 0;
888         }
889
890         // mesh input objects need DerivedMesh
891         if ( !dm )
892                 return 0;
893
894         cloth_from_mesh ( clmd, dm );
895
896         // create springs
897         clmd->clothObject->springs = NULL;
898         clmd->clothObject->numsprings = -1;
899
900         if ( clmd->sim_parms->shapekey_rest )
901                 shapekey_rest = dm->getVertDataArray ( dm, CD_CLOTH_ORCO );
902
903         mvert = dm->getVertArray (dm);
904
905         verts = clmd->clothObject->verts;
906
907         // set initial values
908         for ( i = 0; i < dm->getNumVerts(dm); i++, verts++ ) {
909                 if (first) {
910                         copy_v3_v3(verts->x, mvert[i].co);
911
912                         mul_m4_v3(ob->obmat, verts->x);
913
914                         if ( shapekey_rest ) {
915                                 verts->xrest= shapekey_rest[i];
916                                 mul_m4_v3(ob->obmat, verts->xrest);
917                         }
918                         else
919                                 verts->xrest = verts->x;
920                 }
921                 
922                 /* no GUI interface yet */
923                 verts->mass = clmd->sim_parms->mass; 
924                 verts->impulse_count = 0;
925
926                 if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )
927                         verts->goal= clmd->sim_parms->defgoal;
928                 else
929                         verts->goal= 0.0f;
930
931                 verts->flags = 0;
932                 copy_v3_v3 ( verts->xold, verts->x );
933                 copy_v3_v3 ( verts->xconst, verts->x );
934                 copy_v3_v3 ( verts->txold, verts->x );
935                 copy_v3_v3 ( verts->tx, verts->x );
936                 mul_v3_fl(verts->v, 0.0f);
937
938                 verts->impulse_count = 0;
939                 copy_v3_v3 ( verts->impulse, tnull );
940         }
941         
942         // apply / set vertex groups
943         // has to be happen before springs are build!
944         cloth_apply_vgroup (clmd, dm);
945
946         if ( !cloth_build_springs ( clmd, dm ) ) {
947                 cloth_free_modifier ( clmd );
948                 modifier_setError(&(clmd->modifier), "%s", TIP_("Can't build springs."));
949                 printf("cloth_free_modifier cloth_build_springs\n");
950                 return 0;
951         }
952         
953         for ( i = 0; i < dm->getNumVerts(dm); i++) {
954                 if ((!(cloth->verts[i].flags & CLOTH_VERT_FLAG_PINNED)) && (cloth->verts[i].goal > ALMOST_ZERO)) {
955                         cloth_add_spring (clmd, i, i, 0.0, CLOTH_SPRING_TYPE_GOAL);
956                 }
957         }
958         
959         // init our solver
960         if ( solvers [clmd->sim_parms->solver_type].init ) {
961                 solvers [clmd->sim_parms->solver_type].init ( ob, clmd );
962         }
963         
964         if (!first)
965                 implicit_set_positions(clmd);
966
967         clmd->clothObject->bvhtree = bvhtree_build_from_cloth ( clmd, MAX2(clmd->coll_parms->epsilon, clmd->coll_parms->distance_repel) );
968         
969         for (i = 0; i < dm->getNumVerts(dm); i++) {
970                 maxdist = MAX2(maxdist, clmd->coll_parms->selfepsilon* ( cloth->verts[i].avg_spring_len*2.0f));
971         }
972         
973         clmd->clothObject->bvhselftree = bvhselftree_build_from_cloth ( clmd, maxdist );
974
975         return 1;
976 }
977
978 static void cloth_from_mesh ( ClothModifierData *clmd, DerivedMesh *dm )
979 {
980         unsigned int numverts = dm->getNumVerts (dm);
981         unsigned int numfaces = dm->getNumTessFaces (dm);
982         MFace *mface = dm->getTessFaceArray(dm);
983         unsigned int i = 0;
984
985         /* Allocate our vertices. */
986         clmd->clothObject->numverts = numverts;
987         clmd->clothObject->verts = MEM_callocN ( sizeof ( ClothVertex ) * clmd->clothObject->numverts, "clothVertex" );
988         if ( clmd->clothObject->verts == NULL ) {
989                 cloth_free_modifier ( clmd );
990                 modifier_setError(&(clmd->modifier), "%s", TIP_("Out of memory on allocating clmd->clothObject->verts."));
991                 printf("cloth_free_modifier clmd->clothObject->verts\n");
992                 return;
993         }
994
995         // save face information
996         clmd->clothObject->numfaces = numfaces;
997         clmd->clothObject->mfaces = MEM_callocN ( sizeof ( MFace ) * clmd->clothObject->numfaces, "clothMFaces" );
998         if ( clmd->clothObject->mfaces == NULL ) {
999                 cloth_free_modifier ( clmd );
1000                 modifier_setError(&(clmd->modifier), "%s", TIP_("Out of memory on allocating clmd->clothObject->mfaces."));
1001                 printf("cloth_free_modifier clmd->clothObject->mfaces\n");
1002                 return;
1003         }
1004         for ( i = 0; i < numfaces; i++ )
1005                 memcpy ( &clmd->clothObject->mfaces[i], &mface[i], sizeof ( MFace ) );
1006
1007         /* Free the springs since they can't be correct if the vertices
1008          * changed.
1009          */
1010         if ( clmd->clothObject->springs != NULL )
1011                 MEM_freeN ( clmd->clothObject->springs );
1012
1013 }
1014
1015 /***************************************************************************************
1016  * SPRING NETWORK BUILDING IMPLEMENTATION BEGIN
1017  ***************************************************************************************/
1018
1019 // be careful: implicit solver has to be resettet when using this one!
1020 // --> only for implicit handling of this spring!
1021 int cloth_add_spring(ClothModifierData *clmd, unsigned int indexA, unsigned int indexB, float restlength, int spring_type)
1022 {
1023         Cloth *cloth = clmd->clothObject;
1024         ClothSpring *spring = NULL;
1025         
1026         if (cloth) {
1027                 // TODO: look if this spring is already there
1028                 
1029                 spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1030                 
1031                 if (!spring)
1032                         return 0;
1033                 
1034                 spring->ij = indexA;
1035                 spring->kl = indexB;
1036                 spring->restlen =  restlength;
1037                 spring->type = spring_type;
1038                 spring->flags = 0;
1039                 spring->stiffness = 0;
1040                 
1041                 cloth->numsprings++;
1042         
1043                 BLI_linklist_prepend ( &cloth->springs, spring );
1044                 
1045                 return 1;
1046         }
1047         return 0;
1048 }
1049
1050 static void cloth_free_errorsprings(Cloth *cloth, EdgeHash *UNUSED(edgehash), LinkNode **edgelist)
1051 {
1052         unsigned int i = 0;
1053         
1054         if ( cloth->springs != NULL ) {
1055                 LinkNode *search = cloth->springs;
1056                 while (search) {
1057                         ClothSpring *spring = search->link;
1058                                                 
1059                         MEM_freeN ( spring );
1060                         search = search->next;
1061                 }
1062                 BLI_linklist_free(cloth->springs, NULL);
1063                 
1064                 cloth->springs = NULL;
1065         }
1066         
1067         if (edgelist) {
1068                 for ( i = 0; i < cloth->numverts; i++ ) {
1069                         BLI_linklist_free ( edgelist[i], NULL );
1070                 }
1071
1072                 MEM_freeN ( edgelist );
1073         }
1074         
1075         if (cloth->edgehash)
1076                 BLI_edgehash_free ( cloth->edgehash, NULL );
1077 }
1078
1079 /* update stiffness if vertex group values are changing from frame to frame */
1080 static void cloth_update_springs( ClothModifierData *clmd )
1081 {
1082         Cloth *cloth = clmd->clothObject;
1083         LinkNode *search = NULL;
1084
1085         search = cloth->springs;
1086         while (search) {
1087                 ClothSpring *spring = search->link;
1088
1089                 spring->stiffness = 0.0f;
1090
1091                 if(spring->type == CLOTH_SPRING_TYPE_STRUCTURAL)
1092                 {
1093                         spring->stiffness = (cloth->verts[spring->kl].struct_stiff + cloth->verts[spring->ij].struct_stiff) / 2.0f;
1094                 }
1095                 else if(spring->type == CLOTH_SPRING_TYPE_SHEAR)
1096                 {
1097                         spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0f;
1098                 }
1099                 else if(spring->type == CLOTH_SPRING_TYPE_BENDING)
1100                 {
1101                         spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0f;
1102                 }
1103                 else if(spring->type == CLOTH_SPRING_TYPE_GOAL)
1104                 {
1105                         /* Warning: Appending NEW goal springs does not work because implicit solver would need reset! */
1106
1107                         /* Activate / Deactivate existing springs */
1108                         if ((!(cloth->verts[spring->ij].flags & CLOTH_VERT_FLAG_PINNED)) && (cloth->verts[spring->ij].goal > ALMOST_ZERO))
1109                         {
1110                                 spring->flags &= ~CLOTH_SPRING_FLAG_DEACTIVATE;
1111                         }
1112                         else
1113                         {
1114                                 spring->flags |= CLOTH_SPRING_FLAG_DEACTIVATE;
1115                         }
1116                 }
1117                 
1118                 search = search->next;
1119         }
1120
1121
1122 }
1123
1124 static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm )
1125 {
1126         Cloth *cloth = clmd->clothObject;
1127         ClothSpring *spring = NULL, *tspring = NULL, *tspring2 = NULL;
1128         unsigned int struct_springs = 0, shear_springs=0, bend_springs = 0;
1129         unsigned int i = 0;
1130         unsigned int numverts = (unsigned int)dm->getNumVerts (dm);
1131         unsigned int numedges = (unsigned int)dm->getNumEdges (dm);
1132         unsigned int numfaces = (unsigned int)dm->getNumTessFaces (dm);
1133         MEdge *medge = dm->getEdgeArray (dm);
1134         MFace *mface = dm->getTessFaceArray (dm);
1135         int index2 = 0; // our second vertex index
1136         LinkNode **edgelist = NULL;
1137         EdgeHash *edgehash = NULL;
1138         LinkNode *search = NULL, *search2 = NULL;
1139         
1140         // error handling
1141         if ( numedges==0 )
1142                 return 0;
1143
1144         cloth->springs = NULL;
1145
1146         edgelist = MEM_callocN ( sizeof (LinkNode *) * numverts, "cloth_edgelist_alloc" );
1147         
1148         if (!edgelist)
1149                 return 0;
1150         
1151         for ( i = 0; i < numverts; i++ ) {
1152                 edgelist[i] = NULL;
1153         }
1154
1155         if ( cloth->springs )
1156                 MEM_freeN ( cloth->springs );
1157
1158         // create spring network hash
1159         edgehash = BLI_edgehash_new();
1160
1161         // structural springs
1162         for ( i = 0; i < numedges; i++ ) {
1163                 spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1164
1165                 if ( spring ) {
1166                         spring->ij = MIN2(medge[i].v1, medge[i].v2);
1167                         spring->kl = MAX2(medge[i].v2, medge[i].v1);
1168                         spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1169                         clmd->sim_parms->avg_spring_len += spring->restlen;
1170                         cloth->verts[spring->ij].avg_spring_len += spring->restlen;
1171                         cloth->verts[spring->kl].avg_spring_len += spring->restlen;
1172                         cloth->verts[spring->ij].spring_count++;
1173                         cloth->verts[spring->kl].spring_count++;
1174                         spring->type = CLOTH_SPRING_TYPE_STRUCTURAL;
1175                         spring->flags = 0;
1176                         spring->stiffness = (cloth->verts[spring->kl].struct_stiff + cloth->verts[spring->ij].struct_stiff) / 2.0f;
1177                         struct_springs++;
1178                         
1179                         BLI_linklist_prepend ( &cloth->springs, spring );
1180                 }
1181                 else {
1182                         cloth_free_errorsprings(cloth, edgehash, edgelist);
1183                         return 0;
1184                 }
1185         }
1186         
1187         if (struct_springs > 0)
1188                 clmd->sim_parms->avg_spring_len /= struct_springs;
1189         
1190         for (i = 0; i < numverts; i++) {
1191                 cloth->verts[i].avg_spring_len = cloth->verts[i].avg_spring_len * 0.49f / ((float)cloth->verts[i].spring_count);
1192         }
1193
1194         // shear springs
1195         for ( i = 0; i < numfaces; i++ ) {
1196                 // triangle faces already have shear springs due to structural geometry
1197                 if ( !mface[i].v4 )
1198                         continue;
1199
1200                 spring = ( ClothSpring *) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1201                 
1202                 if (!spring) {
1203                         cloth_free_errorsprings(cloth, edgehash, edgelist);
1204                         return 0;
1205                 }
1206
1207                 spring->ij = MIN2(mface[i].v1, mface[i].v3);
1208                 spring->kl = MAX2(mface[i].v3, mface[i].v1);
1209                 spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1210                 spring->type = CLOTH_SPRING_TYPE_SHEAR;
1211                 spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0f;
1212
1213                 BLI_linklist_append ( &edgelist[spring->ij], spring );
1214                 BLI_linklist_append ( &edgelist[spring->kl], spring );
1215                 shear_springs++;
1216
1217                 BLI_linklist_prepend ( &cloth->springs, spring );
1218
1219                 
1220                 // if ( mface[i].v4 ) --> Quad face
1221                 spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1222                 
1223                 if (!spring) {
1224                         cloth_free_errorsprings(cloth, edgehash, edgelist);
1225                         return 0;
1226                 }
1227
1228                 spring->ij = MIN2(mface[i].v2, mface[i].v4);
1229                 spring->kl = MAX2(mface[i].v4, mface[i].v2);
1230                 spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1231                 spring->type = CLOTH_SPRING_TYPE_SHEAR;
1232                 spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0f;
1233
1234                 BLI_linklist_append ( &edgelist[spring->ij], spring );
1235                 BLI_linklist_append ( &edgelist[spring->kl], spring );
1236                 shear_springs++;
1237
1238                 BLI_linklist_prepend ( &cloth->springs, spring );
1239         }
1240
1241         if (numfaces) {
1242                 // bending springs
1243                 search2 = cloth->springs;
1244                 for ( i = struct_springs; i < struct_springs+shear_springs; i++ ) {
1245                         if ( !search2 )
1246                                 break;
1247
1248                         tspring2 = search2->link;
1249                         search = edgelist[tspring2->kl];
1250                         while ( search ) {
1251                                 tspring = search->link;
1252                                 index2 = ( ( tspring->ij==tspring2->kl ) ? ( tspring->kl ) : ( tspring->ij ) );
1253
1254                                 // check for existing spring
1255                                 // check also if startpoint is equal to endpoint
1256                                 if (!BLI_edgehash_haskey(edgehash, MIN2(tspring2->ij, index2), MAX2(tspring2->ij, index2)) &&
1257                                     (index2 != tspring2->ij))
1258                                 {
1259                                         spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1260
1261                                         if (!spring) {
1262                                                 cloth_free_errorsprings(cloth, edgehash, edgelist);
1263                                                 return 0;
1264                                         }
1265
1266                                         spring->ij = MIN2(tspring2->ij, index2);
1267                                         spring->kl = MAX2(tspring2->ij, index2);
1268                                         spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1269                                         spring->type = CLOTH_SPRING_TYPE_BENDING;
1270                                         spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0f;
1271                                         BLI_edgehash_insert(edgehash, spring->ij, spring->kl, NULL);
1272                                         bend_springs++;
1273
1274                                         BLI_linklist_prepend ( &cloth->springs, spring );
1275                                 }
1276                                 search = search->next;
1277                         }
1278                         search2 = search2->next;
1279                 }
1280         }
1281         else if (struct_springs > 2) {
1282                 /* bending springs for hair strands */
1283                 /* The current algorightm only goes through the edges in order of the mesh edges list   */
1284                 /* and makes springs between the outer vert of edges sharing a vertice. This works just */
1285                 /* fine for hair, but not for user generated string meshes. This could/should be later  */
1286                 /* extended to work with non-ordered edges so that it can be used for general "rope             */
1287                 /* dynamics" without the need for the vertices or edges to be ordered through the length*/
1288                 /* of the strands. -jahka */
1289                 search = cloth->springs;
1290                 search2 = search->next;
1291                 while (search && search2) {
1292                         tspring = search->link;
1293                         tspring2 = search2->link;
1294
1295                         if (tspring->ij == tspring2->kl) {
1296                                 spring = (ClothSpring *)MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1297                                 
1298                                 if (!spring) {
1299                                         cloth_free_errorsprings(cloth, edgehash, edgelist);
1300                                         return 0;
1301                                 }
1302
1303                                 spring->ij = tspring2->ij;
1304                                 spring->kl = tspring->kl;
1305                                 spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1306                                 spring->type = CLOTH_SPRING_TYPE_BENDING;
1307                                 spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0f;
1308                                 bend_springs++;
1309
1310                                 BLI_linklist_prepend ( &cloth->springs, spring );
1311                         }
1312                         
1313                         search = search->next;
1314                         search2 = search2->next;
1315                 }
1316         }
1317         
1318         /* insert other near springs in edgehash AFTER bending springs are calculated (for selfcolls) */
1319         for (i = 0; i < numedges; i++) { /* struct springs */
1320                 BLI_edgehash_insert(edgehash, MIN2(medge[i].v1, medge[i].v2), MAX2(medge[i].v2, medge[i].v1), NULL);
1321         }
1322
1323         for (i = 0; i < numfaces; i++) { /* edge springs */
1324                 if (mface[i].v4) {
1325                         BLI_edgehash_insert(edgehash, MIN2(mface[i].v1, mface[i].v3), MAX2(mface[i].v3, mface[i].v1), NULL);
1326                         
1327                         BLI_edgehash_insert(edgehash, MIN2(mface[i].v2, mface[i].v4), MAX2(mface[i].v2, mface[i].v4), NULL);
1328                 }
1329         }
1330         
1331         
1332         cloth->numsprings = struct_springs + shear_springs + bend_springs;
1333         
1334         if ( edgelist ) {
1335                 for ( i = 0; i < numverts; i++ ) {
1336                         BLI_linklist_free ( edgelist[i], NULL );
1337                 }
1338         
1339                 MEM_freeN ( edgelist );
1340         }
1341         
1342         cloth->edgehash = edgehash;
1343         
1344         if (G.debug_value > 0)
1345                 printf("avg_len: %f\n", clmd->sim_parms->avg_spring_len);
1346
1347         return 1;
1348
1349 } /* cloth_build_springs */
1350 /***************************************************************************************
1351  * SPRING NETWORK BUILDING IMPLEMENTATION END
1352  ***************************************************************************************/
1353