Cloth: 1. Speedup of collisions (up to 50%, see new dancing ballerina stats here...
[blender.git] / source / blender / blenkernel / intern / cloth.c
1 /*  cloth.c
2 *
3 *
4 * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version. The Blender
10 * Foundation also sells licenses for use in proprietary software under
11 * the Blender License.  See http://www.blender.org/BL/ for information
12 * about this.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software Foundation,
21 * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22 *
23 * The Original Code is Copyright (C) Blender Foundation
24 * All rights reserved.
25 *
26 * The Original Code is: all of this file.
27 *
28 * Contributor(s): none yet.
29 *
30 * ***** END GPL/BL DUAL LICENSE BLOCK *****
31 */
32
33
34 #include <math.h>
35 #include <stdlib.h>
36 #include <string.h>
37
38 #include "MEM_guardedalloc.h"
39
40 /* types */
41 #include "DNA_curve_types.h"
42 #include "DNA_object_types.h"
43 #include "DNA_object_force.h"
44 #include "DNA_cloth_types.h"
45 #include "DNA_key_types.h"
46 #include "DNA_mesh_types.h"
47 #include "DNA_meshdata_types.h"
48 #include "DNA_lattice_types.h"
49 #include "DNA_scene_types.h"
50 #include "DNA_modifier_types.h"
51
52 #include "BLI_blenlib.h"
53 #include "BLI_arithb.h"
54 #include "BLI_editVert.h"
55 #include "BLI_edgehash.h"
56 #include "BLI_linklist.h"
57
58 #include "BKE_curve.h"
59 #include "BKE_deform.h"
60 #include "BKE_DerivedMesh.h"
61 #include "BKE_cdderivedmesh.h"
62 #include "BKE_displist.h"
63 #include "BKE_effect.h"
64 #include "BKE_global.h"
65 #include "BKE_key.h"
66 #include "BKE_mesh.h"
67 #include "BKE_object.h"
68 #include "BKE_cloth.h"
69 #include "BKE_modifier.h"
70 #include "BKE_utildefines.h"
71 #include "BKE_DerivedMesh.h"
72 #include "BIF_editdeform.h"
73 #include "BIF_editkey.h"
74 #include "DNA_screen_types.h"
75 #include "BSE_headerbuttons.h"
76 #include "BIF_screen.h"
77 #include "BIF_space.h"
78 #include "mydevice.h"
79
80 #include "BKE_pointcache.h"
81
82 #ifdef _WIN32
83 void tstart ( void )
84 {}
85 void tend ( void )
86 {
87 }
88 double tval()
89 {
90         return 0;
91 }
92 #else
93 #include <sys/time.h>
94                          static struct timeval _tstart, _tend;
95          static struct timezone tz;
96          void tstart ( void )
97 {
98         gettimeofday ( &_tstart, &tz );
99 }
100 void tend ( void )
101 {
102         gettimeofday ( &_tend,&tz );
103 }
104 double tval()
105 {
106         double t1, t2;
107         t1 = ( double ) _tstart.tv_sec + ( double ) _tstart.tv_usec/ ( 1000*1000 );
108         t2 = ( double ) _tend.tv_sec + ( double ) _tend.tv_usec/ ( 1000*1000 );
109         return t2-t1;
110 }
111 #endif
112
113 /* Our available solvers. */
114 // 255 is the magic reserved number, so NEVER try to put 255 solvers in here!
115 // 254 = MAX!
116 static CM_SOLVER_DEF    solvers [] =
117 {
118         { "Implicit", CM_IMPLICIT, implicit_init, implicit_solver, implicit_free },
119         // { "Implicit C++", CM_IMPLICITCPP, implicitcpp_init, implicitcpp_solver, implicitcpp_free },
120 };
121
122 /* ********** cloth engine ******* */
123 /* Prototypes for internal functions.
124 */
125 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, DerivedMesh *dm);
126 static void cloth_from_mesh ( Object *ob, ClothModifierData *clmd, DerivedMesh *dm );
127 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float framenr);
128 int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm );
129 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm );
130
131
132 /******************************************************************************
133 *
134 * External interface called by modifier.c clothModifier functions.
135 *
136 ******************************************************************************/
137 /**
138  * cloth_init -  creates a new cloth simulation.
139  *
140  * 1. create object
141  * 2. fill object with standard values or with the GUI settings if given
142  */
143 void cloth_init ( ClothModifierData *clmd )
144 {       
145         /* Initialize our new data structure to reasonable values. */
146         clmd->sim_parms->gravity [0] = 0.0;
147         clmd->sim_parms->gravity [1] = 0.0;
148         clmd->sim_parms->gravity [2] = -9.81;
149         clmd->sim_parms->structural = 30.0;
150         clmd->sim_parms->shear = 30.0;
151         clmd->sim_parms->bending = 1.0;
152         clmd->sim_parms->Cdis = 5.0;
153         clmd->sim_parms->Cvi = 1.0;
154         clmd->sim_parms->mass = 1.0f;
155         clmd->sim_parms->stepsPerFrame = 5;
156         clmd->sim_parms->sim_time = 1.0;
157         clmd->sim_parms->flags = 0;
158         clmd->sim_parms->solver_type = 0;
159         clmd->sim_parms->preroll = 0;
160         clmd->sim_parms->maxspringlen = 10;
161         clmd->sim_parms->firstframe = 1;
162         clmd->sim_parms->lastframe = 250;
163         clmd->sim_parms->vgroup_mass = 0;
164         clmd->sim_parms->lastcachedframe = 0;
165         clmd->sim_parms->editedframe = 0;
166         clmd->sim_parms->autoprotect = 25;
167         clmd->sim_parms->firstcachedframe = -1.0;
168         
169         clmd->coll_parms->self_friction = 5.0;
170         clmd->coll_parms->friction = 5.0;
171         clmd->coll_parms->loop_count = 3;
172         clmd->coll_parms->epsilon = 0.015f;
173         clmd->coll_parms->flags = CLOTH_COLLSETTINGS_FLAG_ENABLED;
174         clmd->coll_parms->collision_list = NULL;
175
176         /* These defaults are copied from softbody.c's
177         * softbody_calc_forces() function.
178         */
179         clmd->sim_parms->eff_force_scale = 1000.0;
180         clmd->sim_parms->eff_wind_scale = 250.0;
181
182         // also from softbodies
183         clmd->sim_parms->maxgoal = 1.0f;
184         clmd->sim_parms->mingoal = 0.0f;
185         clmd->sim_parms->defgoal = 0.0f;
186         clmd->sim_parms->goalspring = 10.0f;
187         clmd->sim_parms->goalfrict = 5.0f;
188 }
189
190
191 BVH *bvh_build_from_cloth (ClothModifierData *clmd, float epsilon)
192 {
193         unsigned int i = 0;
194         BVH     *bvh=NULL;
195         Cloth *cloth = clmd->clothObject;
196         ClothVertex *verts = NULL;
197
198         if(!clmd)
199                 return NULL;
200
201         cloth = clmd->clothObject;
202
203         if(!cloth)
204                 return NULL;
205         
206         verts = cloth->verts;
207         
208         // in the moment, return zero if no faces there
209         if(!cloth->numfaces)
210                 return NULL;
211         
212         bvh = MEM_callocN(sizeof(BVH), "BVH");
213         if (bvh == NULL) 
214         {
215                 printf("bvh: Out of memory.\n");
216                 return NULL;
217         }
218         
219         // springs = cloth->springs;
220         // numsprings = cloth->numsprings;
221         
222         bvh->flags = 0;
223         bvh->leaf_tree = NULL;
224         bvh->leaf_root = NULL;
225         bvh->tree = NULL;
226
227         bvh->epsilon = epsilon;
228         bvh->numfaces = cloth->numfaces;
229         bvh->mfaces = cloth->mfaces;
230
231         bvh->numverts = cloth->numverts;
232         
233         bvh->current_x = MEM_callocN ( sizeof ( MVert ) * bvh->numverts, "bvh->current_x" );
234         bvh->current_xold = MEM_callocN ( sizeof ( MVert ) * bvh->numverts, "bvh->current_xold" );
235         
236         for(i = 0; i < bvh->numverts; i++)
237         {
238                 VECCOPY(bvh->current_x[i].co, verts[i].tx);
239                 VECCOPY(bvh->current_xold[i].co, verts[i].txold);
240         }
241         
242         bvh_build (bvh);
243         
244         return bvh;
245 }
246
247 void bvh_update_from_cloth(ClothModifierData *clmd, int moving)
248 {
249         unsigned int i = 0;
250         Cloth *cloth = clmd->clothObject;
251         BVH *bvh = cloth->tree;
252         ClothVertex *verts = cloth->verts;
253         
254         if(!bvh)
255                 return;
256         
257         if(cloth->numverts!=bvh->numverts)
258                 return;
259         
260         if(cloth->verts)
261         {
262                 for(i = 0; i < bvh->numverts; i++)
263                 {
264                         VECCOPY(bvh->current_x[i].co, verts[i].tx);
265                         VECCOPY(bvh->current_xold[i].co, verts[i].txold);
266                 }
267         }
268         
269         bvh_update(bvh, moving);
270 }
271
272 // unused in the moment, cloth needs quads from mesh
273 DerivedMesh *CDDM_convert_to_triangle ( DerivedMesh *dm )
274 {
275         DerivedMesh *result = NULL;
276         int i;
277         int numverts = dm->getNumVerts ( dm );
278         int numedges = dm->getNumEdges ( dm );
279         int numfaces = dm->getNumFaces ( dm );
280
281         MVert *mvert = CDDM_get_verts ( dm );
282         MEdge *medge = CDDM_get_edges ( dm );
283         MFace *mface = CDDM_get_faces ( dm );
284
285         MVert *mvert2;
286         MFace *mface2;
287         unsigned int numtris=0;
288         unsigned int numquads=0;
289         int a = 0;
290         int random = 0;
291         int firsttime = 0;
292         float vec1[3], vec2[3], vec3[3], vec4[3], vec5[3];
293         float mag1=0, mag2=0;
294
295         for ( i = 0; i < numfaces; i++ )
296         {
297                 if ( mface[i].v4 )
298                         numquads++;
299                 else
300                         numtris++;
301         }
302
303         result = CDDM_from_template ( dm, numverts, 0, numtris + 2*numquads );
304
305         if ( !result )
306                 return NULL;
307
308         // do verts
309         mvert2 = CDDM_get_verts ( result );
310         for ( a=0; a<numverts; a++ )
311         {
312                 MVert *inMV;
313                 MVert *mv = &mvert2[a];
314
315                 inMV = &mvert[a];
316
317                 DM_copy_vert_data ( dm, result, a, a, 1 );
318                 *mv = *inMV;
319         }
320
321
322         // do faces
323         mface2 = CDDM_get_faces ( result );
324         for ( a=0, i=0; a<numfaces; a++ )
325         {
326                 MFace *mf = &mface2[i];
327                 MFace *inMF;
328                 inMF = &mface[a];
329
330                 /*
331                 DM_copy_face_data(dm, result, a, i, 1);
332
333                 *mf = *inMF;
334                 */
335
336                 if ( mface[a].v4 && random==1 )
337                 {
338                         mf->v1 = mface[a].v2;
339                         mf->v2 = mface[a].v3;
340                         mf->v3 = mface[a].v4;
341                 }
342                 else
343                 {
344                         mf->v1 = mface[a].v1;
345                         mf->v2 = mface[a].v2;
346                         mf->v3 = mface[a].v3;
347                 }
348
349                 mf->v4 = 0;
350                 mf->flag |= ME_SMOOTH;
351
352                 test_index_face ( mf, NULL, 0, 3 );
353
354                 if ( mface[a].v4 )
355                 {
356                         MFace *mf2;
357
358                         i++;
359
360                         mf2 = &mface2[i];
361                         /*
362                         DM_copy_face_data(dm, result, a, i, 1);
363
364                         *mf2 = *inMF;
365                         */
366
367                         if ( random==1 )
368                         {
369                                 mf2->v1 = mface[a].v1;
370                                 mf2->v2 = mface[a].v2;
371                                 mf2->v3 = mface[a].v4;
372                         }
373                         else
374                         {
375                                 mf2->v1 = mface[a].v4;
376                                 mf2->v2 = mface[a].v1;
377                                 mf2->v3 = mface[a].v3;
378                         }
379                         mf2->v4 = 0;
380                         mf2->flag |= ME_SMOOTH;
381
382                         test_index_face ( mf2, NULL, 0, 3 );
383                 }
384
385                 i++;
386         }
387
388         CDDM_calc_edges ( result );
389         CDDM_calc_normals ( result );
390
391         return result;
392
393 }
394
395
396 DerivedMesh *CDDM_create_tearing ( ClothModifierData *clmd, DerivedMesh *dm )
397 {
398         DerivedMesh *result = NULL;
399         unsigned int i = 0, a = 0, j=0;
400         int numverts = dm->getNumVerts ( dm );
401         int numedges = dm->getNumEdges ( dm );
402         int numfaces = dm->getNumFaces ( dm );
403
404         MVert *mvert = CDDM_get_verts ( dm );
405         MEdge *medge = CDDM_get_edges ( dm );
406         MFace *mface = CDDM_get_faces ( dm );
407
408         MVert *mvert2;
409         MFace *mface2;
410         unsigned int numtris=0;
411         unsigned int numquads=0;
412         EdgeHash *edgehash = NULL;
413         Cloth *cloth = clmd->clothObject;
414         ClothSpring *springs = cloth->springs;
415         unsigned int numsprings = cloth->numsprings;
416
417         // create spring tearing hash
418         edgehash = BLI_edgehash_new();
419
420         for ( i = 0; i < numsprings; i++ )
421         {
422                 if ( ( springs[i].flags & CLOTH_SPRING_FLAG_DEACTIVATE )
423                                      && ( !BLI_edgehash_haskey ( edgehash, springs[i].ij, springs[i].kl ) ) )
424                 {
425                         BLI_edgehash_insert ( edgehash, springs[i].ij, springs[i].kl, NULL );
426                         BLI_edgehash_insert ( edgehash, springs[i].kl, springs[i].ij, NULL );
427                         j++;
428                 }
429         }
430
431         // printf("found %d tears\n", j);
432
433         result = CDDM_from_template ( dm, numverts, 0, numfaces );
434
435         if ( !result )
436                 return NULL;
437
438         // do verts
439         mvert2 = CDDM_get_verts ( result );
440         for ( a=0; a<numverts; a++ )
441         {
442                 MVert *inMV;
443                 MVert *mv = &mvert2[a];
444
445                 inMV = &mvert[a];
446
447                 DM_copy_vert_data ( dm, result, a, a, 1 );
448                 *mv = *inMV;
449         }
450
451
452         // do faces
453         mface2 = CDDM_get_faces ( result );
454         for ( a=0, i=0; a<numfaces; a++ )
455         {
456                 MFace *mf = &mface2[i];
457                 MFace *inMF;
458                 inMF = &mface[a];
459
460                 /*
461                 DM_copy_face_data(dm, result, a, i, 1);
462
463                 *mf = *inMF;
464                 */
465
466                 if ( ( !BLI_edgehash_haskey ( edgehash, mface[a].v1, mface[a].v2 ) )
467                                       && ( !BLI_edgehash_haskey ( edgehash, mface[a].v2, mface[a].v3 ) )
468                                       && ( !BLI_edgehash_haskey ( edgehash, mface[a].v3, mface[a].v4 ) )
469                                       && ( !BLI_edgehash_haskey ( edgehash, mface[a].v4, mface[a].v1 ) ) )
470                 {
471                         mf->v1 = mface[a].v1;
472                         mf->v2 = mface[a].v2;
473                         mf->v3 = mface[a].v3;
474                         mf->v4 = mface[a].v4;
475
476                         test_index_face ( mf, NULL, 0, 4 );
477
478                         i++;
479                 }
480         }
481
482         CDDM_lower_num_faces ( result, i );
483         CDDM_calc_edges ( result );
484         CDDM_calc_normals ( result );
485
486         BLI_edgehash_free ( edgehash, NULL );
487
488         return result;
489 }
490
491 int modifiers_indexInObject(Object *ob, ModifierData *md_seek);
492
493 int cloth_read_cache(Object *ob, ClothModifierData *clmd, float framenr)
494 {
495         FILE *fp = NULL;
496         int stack_index = -1;
497         unsigned int a, ret = 1;
498         Cloth *cloth = clmd->clothObject;
499         
500         if(!cloth)
501                 return 0;
502         
503         stack_index = modifiers_indexInObject(ob, (ModifierData *)clmd);
504         
505         fp = BKE_ptcache_id_fopen((ID *)ob, 'r', framenr, stack_index);
506         if(!fp)
507                 ret = 0;
508         else {
509                 for(a = 0; a < cloth->numverts; a++)
510                 {
511                         if(fread(&cloth->verts[a].x, sizeof(float), 3, fp) != 3) 
512                         {
513                                 ret = 0;
514                                 break;
515                         }
516                         if(fread(&cloth->verts[a].xconst, sizeof(float), 3, fp) != 3) 
517                         {
518                                 ret = 0;
519                                 break;
520                         }
521                         if(fread(&cloth->verts[a].v, sizeof(float), 3, fp) != 3) 
522                         {
523                                 ret = 0;
524                                 break;
525                         }
526                 }
527                 
528                 fclose(fp);
529                 
530                 if(clmd->sim_parms->lastcachedframe < framenr)
531                 {
532                         if(G.rt > 0)
533                                 printf("cloth_read_cache problem: lnex - f#: %f, lastCF: %d\n", framenr, clmd->sim_parms->lastcachedframe);
534                 }
535                 
536                 if(G.rt > 0)
537                         printf("cloth_read_cache: %f successfully \n", framenr);
538         }
539         
540         if(G.rt > 0)
541                 printf("cloth_read_cache: %f\n", framenr);
542         
543         return ret;
544 }
545
546 void cloth_clear_cache(Object *ob, ClothModifierData *clmd, float framenr)
547 {
548         int stack_index = -1;
549         
550         // don't do anything as long as we're in editmode!
551         if(clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_EDITMODE)
552         {
553                 /* delete cache free request */
554                 clmd->sim_parms->flags &= ~CLOTH_SIMSETTINGS_FLAG_CCACHE_FFREE;
555                 
556                 return;
557         }
558         
559         /* clear cache if specific frame cleaning requested or cache is not protected */
560         if((!(clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_CCACHE_PROTECT)) || (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_CCACHE_FFREE))
561         {
562                 stack_index = modifiers_indexInObject(ob, (ModifierData *)clmd);
563                 
564                 BKE_ptcache_id_clear((ID *)ob, PTCACHE_CLEAR_AFTER, framenr, stack_index);
565                 
566                 /* update last cached frame # */
567                 clmd->sim_parms->lastcachedframe = framenr;
568                 
569                 /* update first cached frame # */
570                 if((framenr < clmd->sim_parms->firstcachedframe) && (clmd->sim_parms->firstcachedframe >=0.0))
571                         clmd->sim_parms->firstcachedframe = -1.0;
572                 
573                 if(G.rt > 0)
574                         printf("cloth_clear_cache: %f\n", framenr);
575         }
576         
577         /* delete cache free request */
578         clmd->sim_parms->flags &= ~CLOTH_SIMSETTINGS_FLAG_CCACHE_FFREE;
579         
580         
581 }
582 void cloth_write_cache(Object *ob, ClothModifierData *clmd, float framenr)
583 {
584         FILE *fp = NULL;
585         int stack_index = -1;
586         unsigned int a;
587         Cloth *cloth = clmd->clothObject;
588         
589         if(G.rt > 0)
590                 printf("cloth_write_cache: %f\n", framenr);
591         
592         if(!cloth)
593         {
594                 if(G.rt > 0)
595                         printf("cloth_write_cache: no cloth\n");
596                 return;
597         }
598         
599         stack_index = modifiers_indexInObject(ob, (ModifierData *)clmd);
600         
601         fp = BKE_ptcache_id_fopen((ID *)ob, 'w', framenr, stack_index);
602         if(!fp)
603         {
604                 if(G.rt > 0)
605                         printf("cloth_write_cache: no fp\n");
606                 return;
607         }
608         
609         for(a = 0; a < cloth->numverts; a++)
610         {
611                 fwrite(&cloth->verts[a].x, sizeof(float),3,fp);
612                 fwrite(&cloth->verts[a].xconst, sizeof(float),3,fp);
613                 fwrite(&cloth->verts[a].v, sizeof(float),3,fp);
614         }
615         
616         /* update last cached frame # */
617         clmd->sim_parms->lastcachedframe = MAX2(clmd->sim_parms->lastcachedframe, framenr);
618         
619         /* update first cached frame # */
620         if((clmd->sim_parms->firstcachedframe < 0.0) || ((framenr < clmd->sim_parms->firstcachedframe) && (clmd->sim_parms->firstcachedframe > 0.0)))
621                 clmd->sim_parms->firstcachedframe = framenr;
622         
623         if(G.rt > 0)
624                 printf("lcf: %d, framenr: %f\n", clmd->sim_parms->lastcachedframe, framenr);
625
626         fclose(fp);
627 }
628
629
630
631 /************************************************
632  * clothModifier_do - main simulation function
633 ************************************************/
634 DerivedMesh *clothModifier_do(ClothModifierData *clmd,Object *ob, DerivedMesh *dm, int useRenderParams, int isFinalCalc)
635
636 {
637         unsigned int i;
638         Cloth *cloth = clmd->clothObject;
639         float framenr = G.scene->r.cfra;
640         float current_time = bsystem_time ( ob, ( float ) G.scene->r.cfra, 0.0 );
641         ListBase *effectors = NULL;
642         ClothVertex *verts = NULL;
643         float deltaTime = current_time - clmd->sim_parms->sim_time;
644         unsigned int numverts = -1;
645         unsigned int numedges = -1;
646         unsigned int numfaces = -1;
647         MVert *mvert = NULL;
648         MEdge *medge = NULL;
649         MFace *mface = NULL;
650         DerivedMesh *result = NULL;
651         int ret = 0;
652         
653         if(G.rt > 0)
654                 printf("clothModifier_do start\n");
655         
656         /* we're getting called two times during file load,
657         resulting in a not valid G.relbase on the first time (cache makes problems)
658         --> just return back */
659         if((clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_LOADED) && (!G.relbase_valid)) 
660         {
661                 clmd->sim_parms->flags &= ~CLOTH_SIMSETTINGS_FLAG_LOADED;
662                 return dm;
663         }
664         
665         result = CDDM_copy(dm);
666         
667         if(!result)
668         {
669                 return dm;
670         }
671         
672         numverts = result->getNumVerts(result);
673         numedges = result->getNumEdges(result);
674         numfaces = result->getNumFaces(result);
675         mvert = dm->getVertArray(result);
676         medge = dm->getEdgeArray(result);
677         mface = dm->getFaceArray(result);
678         
679         /* check if cache is active / if file is already saved */
680         /*
681         if ((!G.relbase_valid) && ( deltaTime != 1.0f ))
682         {
683         clmd->sim_parms->flags |= CLOTH_SIMSETTINGS_FLAG_RESET;
684 }
685         */
686         
687         if(clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_RESET)
688         {       
689                 cloth_free_modifier (ob, clmd);
690                 if(G.rt > 0)
691                         printf("clothModifier_do CLOTH_SIMSETTINGS_FLAG_RESET\n");
692         }
693         
694         // unused in the moment, calculated seperately in implicit.c
695         clmd->sim_parms->dt = 1.0f / clmd->sim_parms->stepsPerFrame;
696         
697         if ( ( clmd->clothObject == NULL ) || (clmd->clothObject && (numverts != clmd->clothObject->numverts )) )
698         {       
699                 /* only force free the cache if we have a different number of verts */
700                 if(clmd->clothObject && (numverts != clmd->clothObject->numverts ))
701                 {
702                         if(G.rt > 0)
703                                 printf("Force Freeing: numverts != clmd->clothObject->numverts\n");
704                         
705                         clmd->sim_parms->flags |= CLOTH_SIMSETTINGS_FLAG_CCACHE_FFREE;
706                         cloth_free_modifier ( ob, clmd );
707                 }
708                 
709                 cloth_clear_cache(ob, clmd, 0);
710                                 
711                 if ( !cloth_from_object ( ob, clmd, result, framenr ) )
712                         return result;
713         
714                 if ( clmd->clothObject == NULL )
715                         return result;
716         
717                 cloth = clmd->clothObject;
718                 
719                 if(!cloth_read_cache(ob, clmd, framenr))
720                 {
721                         /* save first frame in case we have a reseted object 
722                         and we move one frame forward.
723                         In that case we would only start with the SECOND frame
724                         if we don't save the current state before 
725                         TODO PROBLEM: IMHO we can't track external movement from the
726                         first frame in this case! */
727                         /*
728                         if ( deltaTime == 1.0f )
729                         cloth_write_cache(ob, clmd, framenr-1.0);
730                         */
731                         if(G.rt > 0)
732                                 printf("cloth_from_object NO cloth_read_cache cloth_write_cache\n");
733                 }
734                 else
735                 {
736                         if(G.rt > 0)
737                                 printf("cloth_from_object cloth_read_cache\n");
738                         
739                         implicit_set_positions(clmd);
740                 }
741                 
742                 clmd->sim_parms->sim_time = current_time;
743         }
744         
745         // only be active during a specific period:
746         // that's "first frame" and "last frame" on GUI
747         if ( current_time < clmd->sim_parms->firstframe )
748         {
749                 if(G.rt > 0)
750                         printf("current_time < clmd->sim_parms->firstframe\n");
751                 return result;
752         }
753         else if ( current_time > clmd->sim_parms->lastframe )
754         {
755                 int stack_index = modifiers_indexInObject(ob, (ModifierData *)clmd);
756                         
757                 if(G.rt > 0)
758                         printf("current_time > clmd->sim_parms->lastframe\n");
759                 
760                 if(BKE_ptcache_id_exist((ID *)ob, clmd->sim_parms->lastcachedframe, stack_index))
761                 {
762                         if(cloth_read_cache(ob, clmd, clmd->sim_parms->lastcachedframe))
763                         {
764                                 implicit_set_positions(clmd);
765                                 
766                                 // Copy the result back to the object.
767                                 cloth_to_object (ob, clmd, result);
768                         }
769                 }
770                 return result;
771         }
772         
773         // check for autoprotection, but only if cache active
774         if((framenr >= clmd->sim_parms->autoprotect) && (G.relbase_valid))
775         {
776                 if(G.rt > 0)
777                         printf("fr#: %f, auto: %d\n", framenr, clmd->sim_parms->autoprotect);
778                 clmd->sim_parms->flags |= CLOTH_SIMSETTINGS_FLAG_CCACHE_PROTECT;
779         }
780         if(G.rt > 0)
781                 printf("clothModifier_do deltaTime=1 cachewrite\n");
782         
783         /* nice moving one frame forward */
784         if ( deltaTime == 1.0f )
785         {
786                 clmd->sim_parms->sim_time = current_time;
787                 
788                 if(G.rt > 0)
789                         printf("clothModifier_do deltaTime=1\n");
790                 
791                 if(!cloth_read_cache(ob, clmd, framenr))
792                 {
793                         verts = cloth->verts;
794
795                         // Force any pinned verts to their constrained location.
796                         for ( i = 0; i < clmd->clothObject->numverts; i++, verts++ )
797                         {
798                                 // Save the previous position.
799                                 VECCOPY ( verts->xold, verts->xconst );
800                                 VECCOPY ( verts->txold, verts->x );
801
802                                 // Get the current position.
803                                 VECCOPY ( verts->xconst, mvert[i].co );
804                                 Mat4MulVecfl ( ob->obmat, verts->xconst );
805                         }
806                         
807                         tstart();
808
809                         // Call the solver.
810                         if ( solvers [clmd->sim_parms->solver_type].solver )
811                         {
812                                 ret = solvers [clmd->sim_parms->solver_type].solver ( ob, framenr, clmd, effectors );
813                         }
814
815                         tend();
816                         // printf ( "Cloth simulation time: %f\n", ( float ) tval() );
817                         
818                         if(ret)
819                                 cloth_write_cache(ob, clmd, framenr);
820                         else
821                                 clmd->sim_parms->sim_time--;
822                 }
823                 else
824                 {
825                         if(G.rt > 0)
826                                 printf("clothModifier_do deltaTime=1 cacheread\n");
827                         implicit_set_positions(clmd);
828                 }
829                 
830                 // Copy the result back to the object.
831                 cloth_to_object (ob, clmd, result);
832         }
833         else if(deltaTime == 0.0f) 
834         {       
835                 if(G.rt > 0)
836                         printf("clothModifier_do deltaTime!=1 clmd->clothObject != NULL\n");
837                 if(cloth_read_cache(ob, clmd, framenr))
838                 {
839                         cloth_to_object (ob, clmd, result);
840                         implicit_set_positions(clmd);
841                 }
842                 else /* same cache parts are missing */
843                 {
844                         /*
845                         clmd->sim_parms->flags |= CLOTH_SIMSETTINGS_FLAG_RESET;
846                         */
847                         clmd->sim_parms->flags |= CLOTH_SIMSETTINGS_FLAG_CCACHE_FFREE;
848                         cloth_clear_cache(ob, clmd, 0);
849                         
850                         cloth_write_cache(ob, clmd, framenr);
851                 }
852         }
853         else
854         {       
855                 if(G.rt > 0)
856                         printf("clothModifier_do deltaTime!=1 clmd->clothObject != NULL\n");
857                 if(cloth_read_cache(ob, clmd, framenr))
858                 {
859                         cloth_to_object (ob, clmd, result);
860                         implicit_set_positions(clmd);
861                         clmd->sim_parms->sim_time = current_time;
862                 }
863                 else
864                 {
865                         /* jump to a non-existing frame makes sim reset */
866                         clmd->sim_parms->flags |= CLOTH_SIMSETTINGS_FLAG_RESET;
867                 }
868         }
869         
870         return result;
871 }
872
873 /* frees all */
874 void cloth_free_modifier ( Object *ob, ClothModifierData *clmd )
875 {
876         Cloth   *cloth = NULL;
877         
878         if ( !clmd )
879                 return;
880
881         cloth = clmd->clothObject;
882
883         
884         if ( cloth )
885         {       
886                 // If our solver provides a free function, call it
887                 if ( solvers [clmd->sim_parms->solver_type].free )
888                 {
889                         solvers [clmd->sim_parms->solver_type].free ( clmd );
890                 }
891
892                 // Free the verts.
893                 if ( cloth->verts != NULL )
894                         MEM_freeN ( cloth->verts );
895
896                 cloth->verts = NULL;
897                 cloth->numverts = 0;
898
899                 // Free the springs.
900                 if ( cloth->springs != NULL )
901                 {
902                         LinkNode *search = cloth->springs;
903                         while(search)
904                         {
905                                 ClothSpring *spring = search->link;
906                                                 
907                                 MEM_freeN ( spring );
908                                 search = search->next;
909                         }
910                         BLI_linklist_free(cloth->springs, NULL);
911                 
912                         cloth->springs = NULL;
913                 }
914
915                 cloth->springs = NULL;
916                 cloth->numsprings = 0;
917
918                 // free BVH collision tree
919                 if ( cloth->tree )
920                         bvh_free ( ( BVH * ) cloth->tree );
921
922                 // we save our faces for collision objects
923                 if ( cloth->mfaces )
924                         MEM_freeN ( cloth->mfaces );
925                 /*
926                 if(clmd->clothObject->facemarks)
927                 MEM_freeN(clmd->clothObject->facemarks);
928                 */
929                 MEM_freeN ( cloth );
930                 clmd->clothObject = NULL;
931         }
932         clmd->sim_parms->flags &= ~CLOTH_SIMSETTINGS_FLAG_RESET;
933 }
934
935 /* frees all */
936 void cloth_free_modifier_extern ( ClothModifierData *clmd )
937 {
938         Cloth   *cloth = NULL;
939         if(G.rt > 0)
940                 printf("cloth_free_modifier_extern\n");
941         
942         if ( !clmd )
943                 return;
944
945         cloth = clmd->clothObject;
946         
947         if ( cloth )
948         {       
949                 if(G.rt > 0)
950                         printf("cloth_free_modifier_extern in\n");
951                 
952                 // If our solver provides a free function, call it
953                 if ( solvers [clmd->sim_parms->solver_type].free )
954                 {
955                         solvers [clmd->sim_parms->solver_type].free ( clmd );
956                 }
957
958                 // Free the verts.
959                 if ( cloth->verts != NULL )
960                         MEM_freeN ( cloth->verts );
961
962                 cloth->verts = NULL;
963                 cloth->numverts = 0;
964
965                 // Free the springs.
966                 if ( cloth->springs != NULL )
967                 {
968                         LinkNode *search = cloth->springs;
969                         while(search)
970                         {
971                                 ClothSpring *spring = search->link;
972                                                 
973                                 MEM_freeN ( spring );
974                                 search = search->next;
975                         }
976                         BLI_linklist_free(cloth->springs, NULL);
977                 
978                         cloth->springs = NULL;
979                 }
980
981                 cloth->springs = NULL;
982                 cloth->numsprings = 0;
983
984                 // free BVH collision tree
985                 if ( cloth->tree )
986                         bvh_free ( ( BVH * ) cloth->tree );
987
988                 // we save our faces for collision objects
989                 if ( cloth->mfaces )
990                         MEM_freeN ( cloth->mfaces );
991                 /*
992                 if(clmd->clothObject->facemarks)
993                 MEM_freeN(clmd->clothObject->facemarks);
994                 */
995                 MEM_freeN ( cloth );
996                 clmd->clothObject = NULL;
997         }
998 }
999
1000 /******************************************************************************
1001 *
1002 * Internal functions.
1003 *
1004 ******************************************************************************/
1005
1006 /**
1007  * cloth_to_object - copies the deformed vertices to the object.
1008  *
1009  **/
1010 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, DerivedMesh *dm)
1011 {
1012         unsigned int    i = 0;
1013         MVert *mvert = NULL;
1014         unsigned int numverts;
1015         Cloth *cloth = clmd->clothObject;
1016
1017         if (clmd->clothObject) {
1018                 /* inverse matrix is not uptodate... */
1019                 Mat4Invert (ob->imat, ob->obmat);
1020
1021                 mvert = CDDM_get_verts(dm);
1022                 numverts = dm->getNumVerts(dm);
1023
1024                 for (i = 0; i < numverts; i++)
1025                 {
1026                         VECCOPY (mvert[i].co, cloth->verts[i].x);
1027                         Mat4MulVecfl (ob->imat, mvert[i].co);   /* cloth is in global coords */
1028                 }
1029         }
1030 }
1031
1032
1033 /**
1034  * cloth_apply_vgroup - applies a vertex group as specified by type
1035  *
1036  **/
1037 /* can be optimized to do all groups in one loop */
1038 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm )
1039 {
1040         unsigned int i = 0;
1041         unsigned int j = 0;
1042         MDeformVert *dvert = NULL;
1043         Cloth *clothObj = NULL;
1044         unsigned int numverts = dm->getNumVerts ( dm );
1045         float goalfac = 0;
1046         ClothVertex *verts = NULL;
1047
1048         clothObj = clmd->clothObject;
1049
1050         if ( !dm )
1051                 return;
1052         
1053         numverts = dm->getNumVerts ( dm );
1054
1055         verts = clothObj->verts;
1056         
1057         if (((clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING ) || 
1058                      (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )) && 
1059                      ((clmd->sim_parms->vgroup_mass>0) || 
1060                      (clmd->sim_parms->vgroup_struct>0)||
1061                      (clmd->sim_parms->vgroup_bend>0)))
1062         {
1063                 for ( i = 0; i < numverts; i++, verts++ )
1064                 {
1065                         verts->mass = 1.0; // standard mass
1066                         
1067                         dvert = dm->getVertData ( dm, i, CD_MDEFORMVERT );
1068                         if ( dvert )
1069                         {
1070                                 for ( j = 0; j < dvert->totweight; j++ )
1071                                 {
1072                                         if (( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_mass-1)) && (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL ))
1073                                         {
1074                                                 verts->goal = dvert->dw [j].weight;
1075                                                 goalfac= 1.0f;
1076                                                 
1077                                                 /*
1078                                                 // Kicking goal factor to simplify things...who uses that anyway?
1079                                                 // ABS ( clmd->sim_parms->maxgoal - clmd->sim_parms->mingoal );
1080                                                 */
1081                                                 
1082                                                 verts->goal  = ( float ) pow ( verts->goal , 4.0f );
1083                                                 if ( verts->goal >=SOFTGOALSNAP )
1084                                                 {
1085                                                         verts->flags |= CLOTH_VERT_FLAG_PINNED;
1086                                                 }
1087                                         }
1088                                         
1089                                         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING )
1090                                         {
1091                                                 if( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_struct-1))
1092                                                 {
1093                                                         verts->struct_stiff = dvert->dw [j].weight;
1094                                                         verts->shear_stiff = dvert->dw [j].weight;
1095                                                 }
1096                                                 
1097                                                 if( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_bend-1))
1098                                                 {
1099                                                         verts->bend_stiff = dvert->dw [j].weight;
1100                                                 }
1101                                         }
1102                                         /*
1103                                         // for later
1104                                         if( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_weight-1))
1105                                         {
1106                                                 verts->mass = dvert->dw [j].weight;
1107                                         }
1108                                         */
1109                                 }
1110                         }
1111                 }
1112         }
1113 }
1114
1115 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float framenr)
1116 {
1117         unsigned int i = 0;
1118         MVert *mvert = NULL;
1119         ClothVertex *verts = NULL;
1120         float tnull[3] = {0,0,0};
1121         int cache_there = 0;
1122         Cloth *cloth = NULL;
1123
1124         // If we have a clothObject, free it. 
1125         if ( clmd->clothObject != NULL )
1126         {
1127                 cloth_free_modifier ( ob, clmd );
1128                 if(G.rt > 0)
1129                         printf("cloth_free_modifier cloth_from_object\n");
1130         }
1131
1132         // Allocate a new cloth object.
1133         clmd->clothObject = MEM_callocN ( sizeof ( Cloth ), "cloth" );
1134         if ( clmd->clothObject )
1135         {
1136                 clmd->clothObject->old_solver_type = 255;
1137                 // clmd->clothObject->old_collision_type = 255;
1138                 cloth = clmd->clothObject;
1139         }
1140         else if ( !clmd->clothObject )
1141         {
1142                 modifier_setError ( & ( clmd->modifier ), "Out of memory on allocating clmd->clothObject." );
1143                 return 0;
1144         }
1145
1146         // mesh input objects need DerivedMesh
1147         if ( !dm )
1148                 return 0;
1149
1150         cloth_from_mesh ( ob, clmd, dm );
1151
1152         if((clmd->sim_parms->firstcachedframe < 0.0) || ((clmd->sim_parms->firstcachedframe >= 0.0) && (!cloth_read_cache(ob, clmd, clmd->sim_parms->firstcachedframe))))
1153         {
1154                 // no cache there
1155                 cache_there = 0;
1156                 if(G.rt > 0)
1157                         printf("cache_there = 0\n");
1158         }
1159         else
1160         {
1161                 // we have a cache
1162                 cache_there = 1;
1163                 if(G.rt > 0)
1164                         printf("cache_there = 1, fcf: %d\n", clmd->sim_parms->firstcachedframe);
1165         }
1166         
1167         // create springs 
1168         clmd->clothObject->springs = NULL;
1169         clmd->clothObject->numsprings = -1;
1170         
1171         mvert = dm->getVertArray ( dm );
1172         verts = clmd->clothObject->verts;
1173
1174         // set initial values
1175         for ( i = 0; i < dm->getNumVerts(dm); i++, verts++ )
1176         {
1177                 if(!cache_there)
1178                 {
1179                         VECCOPY ( verts->x, mvert[i].co );
1180                         Mat4MulVecfl ( ob->obmat, verts->x );
1181                 }
1182                 
1183                 /* no GUI interface yet */
1184                 verts->mass = clmd->sim_parms->mass = 1.0f;
1185
1186                 if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )
1187                         verts->goal= clmd->sim_parms->defgoal;
1188                 else
1189                         verts->goal= 0.0f;
1190
1191                 verts->flags = 0;
1192                 VECCOPY ( verts->xold, verts->x );
1193                 VECCOPY ( verts->xconst, verts->x );
1194                 VECCOPY ( verts->txold, verts->x );
1195                 VecMulf ( verts->v, 0.0f );
1196
1197                 verts->impulse_count = 0;
1198                 VECCOPY ( verts->impulse, tnull );
1199         }
1200         
1201         // apply / set vertex groups
1202         // has to be happen before springs are build!
1203         cloth_apply_vgroup (clmd, dm);
1204         
1205         
1206         if ( !cloth_build_springs ( clmd, dm ) )
1207         {
1208                 cloth_free_modifier ( ob, clmd );
1209                 modifier_setError ( & ( clmd->modifier ), "Can't build springs." );
1210                 printf("cloth_free_modifier cloth_build_springs\n");
1211                 return 0;
1212         }
1213         
1214         for ( i = 0; i < dm->getNumVerts(dm); i++)
1215         {
1216                 if((!(cloth->verts[i].flags & CLOTH_VERT_FLAG_PINNED)) && (cloth->verts[i].goal > ALMOST_ZERO))
1217                 {
1218                         cloth_add_spring (clmd, i, i, 0.0, CLOTH_SPRING_TYPE_GOAL);
1219                 }
1220         }
1221         
1222         // init our solver
1223         if ( solvers [clmd->sim_parms->solver_type].init )
1224                 solvers [clmd->sim_parms->solver_type].init ( ob, clmd );
1225
1226         clmd->clothObject->tree = bvh_build_from_cloth ( clmd, clmd->coll_parms->epsilon );
1227
1228         return 1;
1229 }
1230
1231
1232 static void cloth_from_mesh ( Object *ob, ClothModifierData *clmd, DerivedMesh *dm )
1233 {
1234         unsigned int numverts = dm->getNumVerts ( dm );
1235         unsigned int numfaces = dm->getNumFaces ( dm );
1236         MFace *mface = CDDM_get_faces(dm);
1237         unsigned int i = 0;
1238
1239         /* Allocate our vertices.
1240         */
1241         clmd->clothObject->numverts = numverts;
1242         clmd->clothObject->verts = MEM_callocN ( sizeof ( ClothVertex ) * clmd->clothObject->numverts, "clothVertex" );
1243         if ( clmd->clothObject->verts == NULL )
1244         {
1245                 cloth_free_modifier ( ob, clmd );
1246                 modifier_setError ( & ( clmd->modifier ), "Out of memory on allocating clmd->clothObject->verts." );
1247                 printf("cloth_free_modifier clmd->clothObject->verts\n");
1248                 return;
1249         }
1250
1251         // save face information
1252         clmd->clothObject->numfaces = numfaces;
1253         clmd->clothObject->mfaces = MEM_callocN ( sizeof ( MFace ) * clmd->clothObject->numfaces, "clothMFaces" );
1254         if ( clmd->clothObject->mfaces == NULL )
1255         {
1256                 cloth_free_modifier ( ob, clmd );
1257                 modifier_setError ( & ( clmd->modifier ), "Out of memory on allocating clmd->clothObject->mfaces." );
1258                 printf("cloth_free_modifier clmd->clothObject->mfaces\n");
1259                 return;
1260         }
1261         for ( i = 0; i < numfaces; i++ )
1262                 memcpy ( &clmd->clothObject->mfaces[i], &mface[i], sizeof ( MFace ) );
1263
1264         /* Free the springs since they can't be correct if the vertices
1265         * changed.
1266         */
1267         if ( clmd->clothObject->springs != NULL )
1268                 MEM_freeN ( clmd->clothObject->springs );
1269
1270 }
1271
1272 /***************************************************************************************
1273 * SPRING NETWORK BUILDING IMPLEMENTATION BEGIN
1274 ***************************************************************************************/
1275
1276 // be carefull: implicit solver has to be resettet when using this one!
1277 // --> only for implicit handling of this spring!
1278 int cloth_add_spring ( ClothModifierData *clmd, unsigned int indexA, unsigned int indexB, float restlength, int spring_type)
1279 {
1280         Cloth *cloth = clmd->clothObject;
1281         ClothSpring *spring = NULL;
1282         
1283         if(cloth)
1284         {
1285                 // TODO: look if this spring is already there
1286                 
1287                 spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1288                 
1289                 spring->ij = indexA;
1290                 spring->kl = indexB;
1291                 spring->restlen =  restlength;
1292                 spring->type = spring_type;
1293                 spring->flags = 0;
1294                 spring->stiffness = 0;
1295                 
1296                 cloth->numsprings++;
1297         
1298                 BLI_linklist_prepend ( &cloth->springs, spring );
1299                 
1300                 return 1;
1301         }
1302         return 0;
1303 }
1304
1305 int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm )
1306 {
1307         Cloth *cloth = clmd->clothObject;
1308         ClothSpring *spring = NULL, *tspring = NULL, *tspring2 = NULL;
1309         unsigned int struct_springs = 0, shear_springs=0, bend_springs = 0;
1310         unsigned int i = 0;
1311         unsigned int numverts = dm->getNumVerts ( dm );
1312         unsigned int numedges = dm->getNumEdges ( dm );
1313         unsigned int numfaces = dm->getNumFaces ( dm );
1314         MEdge *medge = CDDM_get_edges ( dm );
1315         MFace *mface = CDDM_get_faces ( dm );
1316         unsigned int index2 = 0; // our second vertex index
1317         LinkNode **edgelist = NULL;
1318         EdgeHash *edgehash = NULL;
1319         LinkNode *search = NULL, *search2 = NULL;
1320         float temp[3];
1321         LinkNode *node = NULL, *node2 = NULL;
1322         
1323         // error handling
1324         if ( numedges==0 )
1325                 return 0;
1326
1327         cloth->springs = NULL;
1328
1329         edgelist = MEM_callocN ( sizeof ( LinkNode * ) * numverts, "cloth_edgelist_alloc" );
1330         for ( i = 0; i < numverts; i++ )
1331         {
1332                 edgelist[i] = NULL;
1333         }
1334
1335         if ( cloth->springs )
1336                 MEM_freeN ( cloth->springs );
1337
1338         // create spring network hash
1339         edgehash = BLI_edgehash_new();
1340
1341         // structural springs
1342         for ( i = 0; i < numedges; i++ )
1343         {
1344                 spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1345
1346                 if ( spring )
1347                 {
1348                         spring->ij = medge[i].v1;
1349                         spring->kl = medge[i].v2;
1350                         VECSUB ( temp, cloth->verts[spring->kl].x, cloth->verts[spring->ij].x );
1351                         spring->restlen =  sqrt ( INPR ( temp, temp ) );
1352                         clmd->coll_parms->avg_spring_len += spring->restlen;
1353                         spring->type = CLOTH_SPRING_TYPE_STRUCTURAL;
1354                         spring->flags = 0;
1355                         spring->stiffness = (cloth->verts[spring->kl].struct_stiff + cloth->verts[spring->ij].struct_stiff) / 2.0;
1356                         struct_springs++;
1357                         
1358                         if(!i)
1359                                 node2 = BLI_linklist_append_fast ( &cloth->springs, spring );
1360                         else
1361                                 node2 = BLI_linklist_append_fast ( &node->next, spring );
1362                         node = node2;
1363                 }
1364         }
1365         
1366         clmd->coll_parms->avg_spring_len /= struct_springs;
1367         
1368         // shear springs
1369         for ( i = 0; i < numfaces; i++ )
1370         {
1371                 spring = ( ClothSpring *) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1372
1373                 spring->ij = mface[i].v1;
1374                 spring->kl = mface[i].v3;
1375                 VECSUB ( temp, cloth->verts[spring->kl].x, cloth->verts[spring->ij].x );
1376                 spring->restlen =  sqrt ( INPR ( temp, temp ) );
1377                 spring->type = CLOTH_SPRING_TYPE_SHEAR;
1378                 spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0;
1379
1380                 BLI_linklist_append ( &edgelist[spring->ij], spring );
1381                 BLI_linklist_append ( &edgelist[spring->kl], spring );
1382                 shear_springs++;
1383
1384                 node2 = BLI_linklist_append_fast ( &node->next, spring );
1385                 node = node2;
1386
1387                 if ( mface[i].v4 )
1388                 {
1389                         spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1390
1391                         spring->ij = mface[i].v2;
1392                         spring->kl = mface[i].v4;
1393                         VECSUB ( temp, cloth->verts[spring->kl].x, cloth->verts[spring->ij].x );
1394                         spring->restlen =  sqrt ( INPR ( temp, temp ) );
1395                         spring->type = CLOTH_SPRING_TYPE_SHEAR;
1396                         spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0;
1397
1398                         BLI_linklist_append ( &edgelist[spring->ij], spring );
1399                         BLI_linklist_append ( &edgelist[spring->kl], spring );
1400                         shear_springs++;
1401
1402                         node2 = BLI_linklist_append_fast ( &node->next, spring );
1403                         node = node2;
1404                 }
1405         }
1406         
1407         // bending springs
1408         search2 = cloth->springs;
1409         for ( i = struct_springs; i < struct_springs+shear_springs; i++ )
1410         {
1411                 if ( !search2 )
1412                         break;
1413
1414                 tspring2 = search2->link;
1415                 search = edgelist[tspring2->kl];
1416                 while ( search )
1417                 {
1418                         tspring = search->link;
1419                         index2 = ( ( tspring->ij==tspring2->kl ) ? ( tspring->kl ) : ( tspring->ij ) );
1420                         
1421                         // check for existing spring
1422                         // check also if startpoint is equal to endpoint
1423                         if ( !BLI_edgehash_haskey ( edgehash, index2, tspring2->ij )
1424                                                    && !BLI_edgehash_haskey ( edgehash, tspring2->ij, index2 )
1425                                                    && ( index2!=tspring2->ij ) )
1426                         {
1427                                 spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1428
1429                                 spring->ij = tspring2->ij;
1430                                 spring->kl = index2;
1431                                 VECSUB ( temp, cloth->verts[index2].x, cloth->verts[tspring2->ij].x );
1432                                 spring->restlen =  sqrt ( INPR ( temp, temp ) );
1433                                 spring->type = CLOTH_SPRING_TYPE_BENDING;
1434                                 spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0;
1435                                 BLI_edgehash_insert ( edgehash, spring->ij, index2, NULL );
1436                                 bend_springs++;
1437
1438                                 node2 = BLI_linklist_append_fast ( &node->next, spring );
1439                                 node = node2;
1440                         }
1441                         search = search->next;
1442                 }
1443                 search2 = search2->next;
1444         }
1445         
1446         cloth->numsprings = struct_springs + shear_springs + bend_springs;
1447         
1448         for ( i = 0; i < numverts; i++ )
1449         {
1450                 BLI_linklist_free ( edgelist[i],NULL );
1451         }
1452         if ( edgelist )
1453                 MEM_freeN ( edgelist );
1454         
1455         BLI_edgehash_free ( edgehash, NULL );
1456         
1457         if(G.rt>0)
1458                 printf("avg_len: %f\n",clmd->coll_parms->avg_spring_len);
1459
1460         return 1;
1461
1462 } /* cloth_build_springs */
1463 /***************************************************************************************
1464 * SPRING NETWORK BUILDING IMPLEMENTATION END
1465 ***************************************************************************************/
1466