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