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