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