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