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