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