Fixed crash with ipo'ed collision object
[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         return temptime;
477 }
478
479 void cloth_cache_get_frame(ClothModifierData *clmd, float time)
480 {
481         Frame *frame = NULL;
482         LinkNode *search = NULL;
483         unsigned int i = 0;
484         Cloth *cloth = NULL;
485         int newtime = time + clmd->sim_parms.preroll;
486
487         if(clmd)
488         {
489                 cloth = clmd->clothObject;
490
491                 if(!cloth)
492                         return;
493
494                 // get cache
495                 if(clmd->sim_parms.cache)
496                 {
497                         search = clmd->sim_parms.cache;
498                         frame = NULL;
499                         // check if frame exists
500                         while(search)
501                         {
502                                 frame = search->link;
503                                 if(frame->time == newtime)
504                                         break;
505
506                                 frame = NULL;
507
508                                 search = search->next;   
509                         }
510
511                         if(frame)
512                         {
513                                 if(frame->verts)
514                                 {
515
516                                         // copy ClothVertex struct
517                                         memcpy(cloth->verts, frame->verts, cloth->numverts*sizeof(ClothVertex));
518                                         implicit_set_positions(clmd);
519                                 }
520                                 /*
521                                 if(frame->springs)
522                                 {
523                                         // copy ClothSpring struct
524                                         memcpy(cloth->springs, frame->springs, cloth->numsprings*sizeof(ClothSpring));
525                                 }
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 = NULL;
550                         /*
551                         frame->springs = (ClothSpring *)MEM_callocN(sizeof(ClothSpring)*cloth->numsprings, "cloth frame spring cache");
552                         */
553                         frame->time = newtime;
554
555                         // copy ClothVertex struct
556                         for(i = 0; i < cloth->numverts; i++)
557                         {
558                                 memcpy(&frame->verts[i], &cloth->verts[i], sizeof(ClothVertex));
559                         }
560                         /*
561                         // copy ClothSpring struct
562                         for(i = 0; i < cloth->numsprings; i++)
563                         {
564                                 memcpy(&frame->springs[i], &cloth->springs[i], sizeof(ClothSpring));
565                         }
566                         */
567                 }
568                 if(frame)
569                         BLI_linklist_append(&clmd->sim_parms.cache, frame);
570         }
571 }
572
573 // free cloth cache
574 void cloth_cache_free(ClothModifierData *clmd, float time)
575 {
576         Frame *frame = NULL;
577         LinkNode *search, *last_search;
578         int newtime = time + clmd->sim_parms.preroll;
579
580         // do never free first cached frame
581         if((newtime<1.0f) && !(clmd->sim_parms.flags & CSIMSETT_FLAG_CCACHE_FREE_ALL))
582                 return;
583
584         /* Calls the solver and collision frees first as they
585         * might depend on data in clmd->clothObject. */
586
587         if (clmd) 
588         {
589                 if(clmd->sim_parms.cache)
590                 {                       
591                         last_search = search = clmd->sim_parms.cache;
592                         while(search)
593                         {
594                                 LinkNode *next= search->next;
595                                 frame = search->link;
596
597                                 // free part of cache, but not preroll cache and first framer
598                                 if((clmd->sim_parms.flags & CSIMSETT_FLAG_CCACHE_FREE_PART)  
599                                         && (frame->time > newtime)) // do not delete the first frame
600                                 {
601                                         MEM_freeN(frame->verts);
602                                         // MEM_freeN(frame->springs);
603                                         MEM_freeN(frame);       
604                                         MEM_freeN(search);
605                                         last_search->next = next;
606                                 }
607                                 else if(clmd->sim_parms.flags & CSIMSETT_FLAG_CCACHE_FREE_ALL) // free COMPLETE cache
608                                 {
609                                         MEM_freeN(frame->verts);
610                                         // MEM_freeN(frame->springs);
611                                         MEM_freeN(frame);       
612                                 }
613                                 else
614                                         last_search = search;
615                                 search = next;
616                         }
617
618                         if(clmd->sim_parms.flags & CSIMSETT_FLAG_CCACHE_FREE_ALL)
619                         {
620                                 BLI_linklist_free(clmd->sim_parms.cache,NULL); 
621                                 clmd->sim_parms.cache = NULL;
622                         }
623                 }
624         }
625
626         /* clear flags */
627         clmd->sim_parms.flags &= ~CSIMSETT_FLAG_CCACHE_FREE_ALL;
628         clmd->sim_parms.flags &= ~CSIMSETT_FLAG_CCACHE_FREE_PART;
629
630 }
631
632
633 /**
634 * cloth_deform_verts - simulates one step, framenr is in frames.
635
636 **/
637 void clothModifier_do(ClothModifierData *clmd, Object *ob, DerivedMesh *dm,
638                 float (*vertexCos)[3], int numverts)
639 {
640         unsigned int i;
641         unsigned int numedges = -1;
642         unsigned int numfaces = -1;
643         MVert *mvert = NULL;
644         MEdge *medge = NULL;
645         MFace *mface = NULL;
646         DerivedMesh *result = NULL, *result2 = NULL;
647         Cloth *cloth = clmd->clothObject;
648         unsigned int framenr = (float)G.scene->r.cfra;
649         float current_time = bsystem_time(ob, (float)G.scene->r.cfra, 0.0);
650         ListBase        *effectors = NULL;
651         ClothVertex *newframe= NULL, *verts;
652         Frame *frame = NULL;
653         LinkNode *search = NULL;
654         float deltaTime = current_time - clmd->sim_parms.sim_time;      
655                 
656         
657         // only be active during a specific period:
658         // that's "first frame" and "last frame" on GUI
659         
660         if (!(clmd->sim_parms.flags & CSIMSETT_FLAG_COLLOBJ))
661         {
662                 if(current_time < clmd->sim_parms.firstframe)
663                         return;
664                 else if(current_time > clmd->sim_parms.lastframe)
665                 {
666                         int frametime = cloth_cache_last_frame(clmd);
667                         if(cloth_cache_search_frame(clmd, frametime))
668                         {
669                                 cloth_cache_get_frame(clmd, frametime);
670                                 cloth_to_object (ob, clmd, vertexCos, numverts);
671                         }
672                         return;
673                 }
674                 else if(ABS(deltaTime) >= 2.0f ) // no timewarps allowed
675                 {
676                         if(!cloth_cache_search_frame(clmd, framenr))
677                                 return;
678                 }
679         }
680         
681         
682         // unused in the moment, calculated seperately in implicit.c
683         clmd->sim_parms.dt = 1.0f / clmd->sim_parms.stepsPerFrame;
684         
685         clmd->sim_parms.sim_time = current_time;
686         
687         // check if cloth object was some collision object before and needs freeing now
688         if (!(clmd->sim_parms.flags & CSIMSETT_FLAG_COLLOBJ) && (clmd->clothObject != NULL) && (clmd->clothObject->old_solver_type == 255))
689         {
690                 // temporary set CSIMSETT_FLAG_COLLOBJ flag for proper freeing 
691                 clmd->sim_parms.flags |= CSIMSETT_FLAG_COLLOBJ;
692                 cloth_free_modifier(clmd);
693                 clmd->sim_parms.flags &= ~CSIMSETT_FLAG_COLLOBJ;
694         }
695
696         // This is for collisions objects: check special case CSIMSETT_FLAG_COLLOBJ
697         if (clmd->sim_parms.flags & CSIMSETT_FLAG_COLLOBJ)
698         {
699                 // save next position + time            
700                 if ((clmd->clothObject == NULL) || (numverts != clmd->clothObject->numverts) )
701                 {
702                         if(!collobj_from_object (ob, clmd, dm, vertexCos, framenr))
703                         {
704                                 clmd->sim_parms.flags |= CSIMSETT_FLAG_COLLOBJ;
705                                 cloth_free_modifier(clmd);
706                                 return;
707                         }
708
709                         if(clmd->clothObject == NULL)
710                                 return;
711
712                         cloth = clmd->clothObject;
713                 }
714
715                 // Save old position 
716                 clmd->sim_parms.sim_time_old = clmd->sim_parms.sim_time;
717                 clmd->sim_parms.sim_time = current_time; 
718                 
719                 verts = cloth->verts;
720                 
721                 for (i = 0; i < clmd->clothObject->numverts; i++, verts++)
722                 {
723                         // Save the previous position. 
724                         VECCOPY (verts->xold, verts->x);
725                         VECCOPY (verts->txold, verts->x);
726
727                         // Get the current position. 
728                         VECCOPY (verts->x, vertexCos[i]);
729                         Mat4MulVecfl(ob->obmat, verts->x);
730
731                         // Compute the vertices "velocity".
732                         // (no dt correction here because of float error)
733                         VECSUB (verts->v, verts->x, verts->xold);
734                 }
735                 
736                 return;
737         }       
738
739         if(deltaTime == 1.0f)
740         {
741                 if ((clmd->clothObject == NULL) || (numverts != clmd->clothObject->numverts) ) 
742                 {
743                         if(!cloth_from_object (ob, clmd, dm, vertexCos, numverts))
744                                 return;
745
746                         if(clmd->clothObject == NULL)
747                                 return;
748
749                         cloth = clmd->clothObject;
750                 }
751
752                 clmd->clothObject->old_solver_type = clmd->sim_parms.solver_type;
753
754                 // Insure we have a clmd->clothObject, in case allocation failed.
755                 if (clmd->clothObject != NULL) 
756                 {            
757                         if(!cloth_cache_search_frame(clmd, framenr))
758                         {
759                                 verts = cloth->verts;
760                                 
761                                 // Force any pinned verts to their constrained location. 
762                                 for (i = 0; i < clmd->clothObject->numverts; i++, verts++)
763                                 {
764                                         // Save the previous position. 
765                                         VECCOPY (verts->xold, verts->xconst);
766                                         VECCOPY (verts->txold, verts->x);
767
768                                         // Get the current position. 
769                                         VECCOPY (verts->xconst, vertexCos[i]);
770                                         Mat4MulVecfl(ob->obmat, verts->xconst);
771                                 }
772
773                                 tstart();
774
775                                 // Call the solver.
776                                 if (solvers [clmd->sim_parms.solver_type].solver)
777                                         solvers [clmd->sim_parms.solver_type].solver (ob, framenr, clmd, effectors);
778                                 
779                                 tend();
780                                 printf("Cloth simulation time: %f\n", (float)tval());
781
782                                 cloth_cache_set_frame(clmd, framenr);
783
784                         }
785                         else // just retrieve the cached frame
786                         {
787                                 cloth_cache_get_frame(clmd, framenr);
788                         }
789
790                         // Copy the result back to the object.
791                         cloth_to_object (ob, clmd, vertexCos, numverts);
792                         
793                         // bvh_free(clmd->clothObject->tree);
794                         // clmd->clothObject->tree = bvh_build(clmd, clmd->coll_parms.epsilon);
795                 } 
796
797         }
798         else if((deltaTime <= 0.0f)||(deltaTime > 1.0f))
799         {
800                 if((clmd->clothObject != NULL) && (clmd->sim_parms.cache)) 
801                 {
802                         if(cloth_cache_search_frame(clmd, framenr))
803                         {
804                                 cloth_cache_get_frame(clmd, framenr);
805                                 cloth_to_object (ob, clmd, vertexCos, numverts);
806                         }
807                 }
808         }
809         
810 }
811
812 /* frees all */
813 void cloth_free_modifier (ClothModifierData *clmd)
814 {
815         Cloth   *cloth = NULL;
816
817         if(!clmd)
818                 return;
819
820         cloth = clmd->clothObject;
821         
822         if(!(clmd->sim_parms.flags & CSIMSETT_FLAG_CCACHE_PROTECT))
823         {
824                 // free our frame cache, TODO: but get to first position before
825                 clmd->sim_parms.flags |= CSIMSETT_FLAG_CCACHE_FREE_ALL;
826                 cloth_cache_free(clmd, 0);
827         
828                 if (cloth) 
829                 {       
830                         // If our solver provides a free function, call it
831                         if (cloth->old_solver_type < 255 && solvers [cloth->old_solver_type].free) 
832                         {       
833                                 solvers [cloth->old_solver_type].free (clmd);
834                         }
835                         
836                         // Free the verts.
837                         if (cloth->verts != NULL)
838                                 MEM_freeN (cloth->verts);
839         
840                         cloth->verts = NULL;
841                         cloth->numverts = -1;
842                         
843                         // Free the springs.
844                         if (cloth->springs != NULL)
845                                 MEM_freeN (cloth->springs);
846         
847                         cloth->springs = NULL;
848                         cloth->numsprings = -1;         
849                         
850                         // free BVH collision tree
851                         if(cloth->tree)
852                                 bvh_free((BVH *)cloth->tree);
853                         
854                         // we save our faces for collision objects
855                         if(cloth->mfaces)
856                                 MEM_freeN(cloth->mfaces);
857                         /*
858                         if(clmd->clothObject->facemarks)
859                                 MEM_freeN(clmd->clothObject->facemarks);
860                         */
861                         MEM_freeN (cloth);
862                         clmd->clothObject = NULL;
863                 }
864         }
865 }
866
867
868 /******************************************************************************
869 *
870 * Internal functions.
871 *
872 ******************************************************************************/
873
874 /**
875 * cloth_to_object - copies the deformed vertices to the object.
876 *
877 * This function is a modified version of the softbody.c:softbody_to_object() function.
878 **/
879 static void cloth_to_object (Object *ob, ClothModifierData *clmd, float (*vertexCos)[3], unsigned int numverts)
880 {
881         ClothVertex     *verts = NULL;
882         unsigned int    i = 0;
883
884         if (clmd->clothObject) {
885                 verts = clmd->clothObject->verts;
886
887                 /* inverse matrix is not uptodate... */
888                 Mat4Invert (ob->imat, ob->obmat);
889
890                 for (i = 0; i < numverts; i++, verts++)
891                 {
892                         VECCOPY (vertexCos[i], verts->x);
893                         Mat4MulVecfl (ob->imat, vertexCos[i]);  /* softbody is in global coords */
894                 }
895         }
896 }
897
898
899 /**
900 * cloth_apply_vgroup - applies a vertex group as specified by type
901 *
902 **/
903 static void cloth_apply_vgroup(ClothModifierData *clmd, DerivedMesh *dm, short vgroup)
904 {
905         unsigned int i = 0;
906         unsigned int j = 0;
907         MDeformVert *dvert = NULL;
908         Cloth *clothObj = NULL;
909         unsigned int numverts = dm->getNumVerts(dm);
910         float goalfac = 0;
911         ClothVertex *verts = NULL;
912
913         clothObj = clmd->clothObject;
914         
915         if(!dm)
916                 return;
917         
918         numverts = dm->getNumVerts(dm);
919
920         /* vgroup is 1 based, decrement so we can match the right group. */
921         --vgroup;
922         
923         verts = clothObj->verts;
924
925         for (i = 0; i < numverts; i++, verts++)
926         {                                       
927                 // LATER ON, support also mass painting here
928                 if(clmd->sim_parms.flags & CSIMSETT_FLAG_GOAL) 
929                 {                                               
930                         dvert = dm->getVertData(dm, i, CD_MDEFORMVERT);
931                         if(dvert)       
932                         {               
933                                 for(j = 0; j < dvert->totweight; j++) 
934                                 {
935                                         if(dvert->dw[j].def_nr == vgroup) 
936                                         {
937                                                 verts->goal = dvert->dw [j].weight;
938
939                                                 goalfac= ABS(clmd->sim_parms.maxgoal - clmd->sim_parms.mingoal);
940                                                 verts->goal  = (float)pow(verts->goal , 4.0f);
941
942                                                 if(dvert->dw [j].weight >=SOFTGOALSNAP)
943                                                 {
944                                                         verts->flags |= CVERT_FLAG_PINNED;
945                                                 }
946
947                                                 // TODO enable mass painting here, for the moment i let "goals" go first
948
949                                                 break;
950                                         }
951                                 }
952                         }
953                 }
954         }
955 }
956
957 // only meshes supported at the moment
958 /* collision objects */
959 static int collobj_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float (*vertexCos)[3], unsigned int numverts)
960 {
961         unsigned int i;
962         MVert *mvert = NULL; 
963         ClothVertex *verts = NULL;
964         float tnull[3] = {0,0,0}; 
965         
966         /* If we have a clothObject, free it. */
967         if (clmd->clothObject != NULL)
968                 cloth_free_modifier (clmd);
969
970         /* Allocate a new cloth object. */
971         clmd->clothObject = MEM_callocN (sizeof(Cloth), "cloth");
972         if (clmd->clothObject) 
973         {
974                 clmd->clothObject->old_solver_type = 255;
975                 clmd->clothObject->old_collision_type = 255;
976         }
977         else if (clmd->clothObject == NULL) 
978         {
979                 modifier_setError (&(clmd->modifier), "Out of memory on allocating clmd->clothObject.");
980                 return 0;
981         }
982
983         switch (ob->type)
984         {
985         case OB_MESH:
986                 
987                 // mesh input objects need DerivedMesh
988                 if(!dm)
989                         return 0;
990                 
991                 cloth_from_mesh (ob, clmd, dm);
992                 
993                 if (clmd->clothObject != NULL) 
994                 {
995                         if (!dm) return 0;
996                         if (!dm->getNumVerts(dm) || !dm->getNumFaces(dm)) return 0;
997                         
998                         mvert = dm->getVertArray(dm);
999                         verts = clmd->clothObject->verts;
1000                         numverts = clmd->clothObject->numverts = dm->getNumVerts(dm);
1001                         
1002                         for (i = 0; i < numverts; i++, verts++)
1003                         {
1004                                 VECCOPY (verts->x, mvert[i].co);
1005                                 Mat4MulVecfl(ob->obmat, verts->x);
1006                                 verts->flags = 0;
1007                                 VECCOPY(verts->xold, verts->x);
1008                                 VECCOPY(verts->txold, verts->x);
1009                                 VECCOPY(verts->tx, verts->x);
1010                                 VecMulf(verts->v, 0.0f);
1011                                 verts->impulse_count = 0;
1012                                 VECCOPY(verts->impulse, tnull);
1013                         }
1014                         clmd->clothObject->tree =  bvh_build(clmd,clmd->coll_parms.epsilon);
1015                         
1016                 }
1017                 
1018                 return 1;
1019         default: return 0; // TODO - we do not support changing meshes
1020         }
1021 }
1022
1023 /*
1024 helper function to get proper spring length 
1025 when object is rescaled
1026 */
1027 float cloth_globallen(float *v1,float *v2,Object *ob)
1028 {
1029         float p1[3],p2[3];
1030         VECCOPY(p1,v1);
1031         Mat4MulVecfl(ob->obmat, p1);    
1032         VECCOPY(p2,v2);
1033         Mat4MulVecfl(ob->obmat, p2);
1034         return VecLenf(p1,p2);
1035 }
1036
1037 static void curve_surf_to_cloth(Object *ob, ClothModifierData *clmd, float (*vertexCos)[3])
1038 {
1039         Curve *cu= ob->data;
1040         Nurb *nu;
1041         BezTriple *bezt;
1042         float goalfac;
1043         unsigned int a, curindex=0, i=0;
1044         unsigned int numverts, numsprings = 0, setgoal=0;
1045         Cloth   *clothObj;
1046         ClothVertex *verts = NULL;
1047         
1048         clmd->clothObject->numverts = numverts= count_curveverts(&cu->nurb);
1049         clothObj = clmd->clothObject;
1050         
1051         if(ob->type==OB_CURVE) 
1052         {
1053                 numsprings = numverts - BLI_countlist(&cu->nurb);
1054         }
1055         
1056         /* Allocate our vertices.
1057         */
1058         clmd->clothObject->numverts = numverts;
1059         clmd->clothObject->verts = MEM_callocN (sizeof (ClothVertex) * clmd->clothObject->numverts, "clothVertex");
1060         if (clmd->clothObject->verts == NULL) 
1061         {
1062                 cloth_free_modifier (clmd);
1063                 modifier_setError (&(clmd->modifier), "Out of memory on allocating clmd->clothObject->verts.");
1064                 return;
1065         }
1066         
1067         verts = clmd->clothObject->verts;
1068         
1069         // copy vertex positions
1070         for (i = 0; i < numverts; i++)
1071         {
1072                 VECCOPY (verts->x, vertexCos[i]);
1073                 Mat4MulVecfl(ob->obmat, verts->x);
1074
1075                 verts->mass = clmd->sim_parms.mass;
1076                 // verts->goal= clmd->sim_parms.defgoal;
1077                 verts->flags = 0;
1078                 VECCOPY(verts->xold, verts->x);
1079                 VECCOPY(verts->xconst, verts->x);
1080                 VECCOPY(verts->txold, verts->x);
1081                 VecMulf(verts->v, 0.0f);
1082         }
1083         
1084         clmd->clothObject->mfaces = NULL; // update face pointer
1085         clmd->clothObject->numfaces = 0;
1086         
1087         clmd->clothObject->springs = MEM_callocN (sizeof (ClothSpring) * (numsprings), "cloth_springs_alloc");
1088                 
1089         // set vars now 
1090         goalfac= ABS(clmd->sim_parms.maxgoal - clmd->sim_parms.mingoal);
1091         // clothObj->verts [i].goal = clmd->sim_parms.mingoal + bezt->weight*goalfac;
1092         
1093         /* apply / set vertex groups */
1094         if(clmd->sim_parms.flags & CSIMSETT_FLAG_GOAL) 
1095         {
1096                 if (clmd->sim_parms.vgroup_mass > 0)
1097                 {
1098                         setgoal = 1;
1099                 }
1100         }
1101                 
1102 /*      
1103         for(nu= cu->nurb.first; nu; nu= nu->next) 
1104         {
1105                 if(nu->bezt) 
1106                 {
1107                         for(bezt=nu->bezt, a=0; a<nu->pntsu; a++, bezt++, bp+=3, curindex+=3) 
1108                         {
1109                                 if(setgoal) 
1110                                 {
1111                                         bp->goal= sb->mingoal + bezt->weight*goalfac;
1112                                         // a little ad hoc changing the goal control to be less *sharp*
1113                                         bp->goal = (float)pow(bp->goal, 4.0f);
1114                                         
1115                                         // all three triples
1116                                         (bp+1)->goal= bp->goal;
1117                                         (bp+2)->goal= bp->goal;
1118                                 }
1119                                 
1120                                 if(totspring) 
1121                                 {
1122                                         if(a>0) 
1123                                         {
1124                                                 bs->v1= curindex-1;
1125                                                 bs->v2= curindex;
1126                                                 bs->strength= 1.0;
1127                                                 bs->order=1;
1128                                                 bs->len= globallen( (bezt-1)->vec[2], bezt->vec[0], ob );
1129                                                 bs++;
1130                                         }
1131                                         bs->v1= curindex;
1132                                         bs->v2= curindex+1;
1133                                         bs->strength= 1.0;
1134                                         bs->order=1;
1135                                         bs->len= globallen( bezt->vec[0], bezt->vec[1], ob );
1136                                         bs++;
1137                                         
1138                                         bs->v1= curindex+1;
1139                                         bs->v2= curindex+2;
1140                                         bs->strength= 1.0;
1141                                         bs->order=1;
1142                                         bs->len= globallen( bezt->vec[1], bezt->vec[2], ob );
1143                                         bs++;
1144                                 }
1145                         }
1146                 }
1147                 else {
1148                         for(bpnt=nu->bp, a=0; a<nu->pntsu*nu->pntsv; a++, bpnt++, bp++, curindex++) 
1149                         {
1150                                 if(setgoal) 
1151                                 {
1152                                         bp->goal= sb->mingoal + bpnt->weight*goalfac;
1153                                         // a little ad hoc changing the goal control to be less *sharp*
1154                                         bp->goal = (float)pow(bp->goal, 4.0f);
1155                                 }
1156                                 if(totspring && a>0) 
1157                                 {
1158                                         bs->v1= curindex-1;
1159                                         bs->v2= curindex;
1160                                         bs->strength= 1.0;
1161                                         bs->order=1;
1162                                         bs->len= globallen( (bpnt-1)->vec, bpnt->vec , ob );
1163                                         bs++;
1164                                 }
1165                         }
1166                 }
1167         }
1168         */
1169 }
1170                 
1171 // only meshes supported at the moment
1172 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float (*vertexCos)[3], unsigned int numverts)
1173 {
1174         unsigned int i = 0;
1175         // dm->getNumVerts(dm);
1176         MVert *mvert = NULL; // CDDM_get_verts(dm);
1177         ClothVertex *verts = NULL;
1178         float tnull[3] = {0,0,0};
1179         
1180         /* If we have a clothObject, free it. */
1181         if (clmd->clothObject != NULL)
1182                 cloth_free_modifier (clmd);
1183
1184         /* Allocate a new cloth object. */
1185         clmd->clothObject = MEM_callocN (sizeof(Cloth), "cloth");
1186         if (clmd->clothObject) 
1187         {
1188                 clmd->clothObject->old_solver_type = 255;
1189                 clmd->clothObject->old_collision_type = 255;
1190         }
1191         else if (clmd->clothObject == NULL) 
1192         {
1193                 modifier_setError (&(clmd->modifier), "Out of memory on allocating clmd->clothObject.");
1194                 return 0;
1195         }
1196
1197         switch (ob->type)
1198         {
1199                 case OB_MESH:
1200                 
1201                 // mesh input objects need DerivedMesh
1202                 if(!dm)
1203                         return 0;
1204                 
1205                 cloth_from_mesh (ob, clmd, dm);
1206
1207                 if (clmd->clothObject != NULL) 
1208                 {                       
1209                         /* create springs */
1210                         clmd->clothObject->springs = NULL;
1211                         clmd->clothObject->numsprings = -1;
1212
1213                         if (!cloth_build_springs (clmd->clothObject, dm) )
1214                         {
1215                                 modifier_setError (&(clmd->modifier), "Can't build springs.");
1216                                 return 0;
1217                         }  
1218                         
1219                         mvert = CDDM_get_verts(dm);
1220                         verts = clmd->clothObject->verts;
1221
1222                         /* set initial values */
1223                         for (i = 0; i < numverts; i++, verts++)
1224                         {
1225                                 VECCOPY (verts->x, mvert[i].co);
1226                                 Mat4MulVecfl(ob->obmat, verts->x);
1227
1228                                 verts->mass = clmd->sim_parms.mass;
1229                                 
1230                                 if(clmd->sim_parms.flags & CSIMSETT_FLAG_GOAL) 
1231                                         verts->goal= clmd->sim_parms.defgoal;
1232                                 else
1233                                         verts->goal= 0.0f;
1234                                 
1235                                 verts->flags = 0;
1236                                 VECCOPY(verts->xold, verts->x);
1237                                 VECCOPY(verts->xconst, verts->x);
1238                                 VECCOPY(verts->txold, verts->x);
1239                                 VecMulf(verts->v, 0.0f);
1240                                 
1241                                 verts->impulse_count = 0;
1242                                 VECCOPY(verts->impulse, tnull);
1243                         }
1244
1245                         /* apply / set vertex groups */
1246                         if (clmd->sim_parms.vgroup_mass > 0)
1247                                 cloth_apply_vgroup (clmd, dm, clmd->sim_parms.vgroup_mass);
1248
1249                         /* init our solver */
1250                         if (solvers [clmd->sim_parms.solver_type].init)
1251                                 solvers [clmd->sim_parms.solver_type].init (ob, clmd);
1252
1253                         clmd->clothObject->tree = bvh_build(clmd, clmd->coll_parms.epsilon);
1254
1255                         // cloth_cache_set_frame(clmd, 1);
1256                 }
1257
1258                 return 1;
1259                 case OB_LATTICE:
1260                         printf("OB_LATTICE\n");
1261                 // lattice_to_softbody(ob);
1262                 return 1;
1263                 case OB_CURVE:
1264                 case OB_SURF:
1265                         printf("OB_SURF| OB_CURVE\n");
1266                 curve_surf_to_cloth(ob, clmd, vertexCos);
1267                 return 1;
1268                 default: return 0; // TODO - we do not support changing meshes
1269         }
1270         
1271         return 0;
1272 }
1273
1274 static void cloth_from_mesh (Object *ob, ClothModifierData *clmd, DerivedMesh *dm)
1275 {
1276         unsigned int numverts = dm->getNumVerts(dm);
1277         unsigned int numfaces = dm->getNumFaces(dm);
1278         MFace *mface = dm->getFaceArray(dm);
1279         unsigned int i = 0;
1280
1281         /* Allocate our vertices.
1282         */
1283         clmd->clothObject->numverts = numverts;
1284         clmd->clothObject->verts = MEM_callocN (sizeof (ClothVertex) * clmd->clothObject->numverts, "clothVertex");
1285         if (clmd->clothObject->verts == NULL) 
1286         {
1287                 cloth_free_modifier (clmd);
1288                 modifier_setError (&(clmd->modifier), "Out of memory on allocating clmd->clothObject->verts.");
1289                 return;
1290         }
1291         
1292         // save face information
1293         clmd->clothObject->numfaces = numfaces;
1294         clmd->clothObject->mfaces = MEM_callocN (sizeof (MFace) * clmd->clothObject->numfaces, "clothMFaces");
1295         if (clmd->clothObject->mfaces == NULL) 
1296         {
1297                 cloth_free_modifier (clmd);
1298                 modifier_setError (&(clmd->modifier), "Out of memory on allocating clmd->clothObject->mfaces.");
1299                 return;
1300         }
1301         for(i = 0; i < numfaces; i++)
1302                 memcpy(&clmd->clothObject->mfaces[i], &mface[i], sizeof(MFace));
1303
1304         
1305         // for SIP code
1306         // clmd->clothObject->facemarks = MEM_callocN (sizeof (unsigned char) * clmd->clothObject->numfaces, "clothFaceMarks");
1307
1308         /* Free the springs since they can't be correct if the vertices
1309         * changed.
1310         */
1311         if (clmd->clothObject->springs != NULL)
1312                 MEM_freeN (clmd->clothObject->springs);
1313
1314 }
1315
1316 /***************************************************************************************
1317 * SPRING NETWORK BUILDING IMPLEMENTATION BEGIN
1318 ***************************************************************************************/
1319
1320 int cloth_build_springs(Cloth *cloth, DerivedMesh *dm)
1321 {
1322         ClothSpring *springs = NULL;    
1323         unsigned int struct_springs = 0, shear_springs=0, bend_springs = 0;
1324         unsigned int i = 0;
1325         unsigned int numverts = dm->getNumVerts(dm);
1326         unsigned int numedges = dm->getNumEdges(dm);
1327         unsigned int numfaces = dm->getNumFaces(dm);
1328         MVert *mvert = CDDM_get_verts(dm);
1329         MEdge *medge = CDDM_get_edges(dm);
1330         MFace *mface = CDDM_get_faces(dm);
1331         unsigned int index2 = 0; // our second vertex index
1332         LinkNode **edgelist = NULL;
1333         EdgeHash *edgehash = NULL;
1334         LinkNode *search = NULL;
1335         float temp[3];
1336         unsigned int temp_index = 0;
1337         ClothSpring *tspring = NULL;
1338
1339         // error handling
1340         if(numedges==0)
1341                 return 0;
1342
1343         edgelist = MEM_callocN (sizeof (LinkNode *) * numverts, "cloth_edgelist_alloc");
1344         for(i = 0; i < numverts; i++)
1345         {
1346                 edgelist[i] = NULL;
1347         }
1348
1349         if(cloth->springs)
1350                 MEM_freeN(cloth->springs);
1351
1352         // create spring network hash
1353         edgehash = BLI_edgehash_new();
1354
1355         // should be 4 for maximal bending springs, using 5 to be sure ;)
1356         springs = cloth->springs = MEM_callocN (sizeof (ClothSpring) * (numedges + numfaces * 2 +  6 * numverts), "cloth_springs_alloc");
1357
1358         // structural springs
1359         for(i = 0; i < numedges; i++)
1360         {
1361                 springs[i].ij = medge[i].v1;
1362                 springs[i].kl = medge[i].v2;
1363                 VECSUB(temp, mvert[springs[i].kl].co, mvert[springs[i].ij].co);
1364                 springs[i].restlen =  sqrt(INPR(temp, temp));
1365                 springs[i].type = STRUCTURAL;
1366                 springs[i].flags = 0;
1367                 struct_springs++;
1368         }
1369
1370         // shear springs
1371         for(i = 0; i < numfaces; i++)
1372         {
1373                 temp_index = struct_springs + shear_springs;
1374
1375                 springs[temp_index].ij = mface[i].v1;
1376                 springs[temp_index].kl = mface[i].v3;
1377                 VECSUB(temp, mvert[springs[temp_index].kl].co, mvert[springs[temp_index].ij].co);
1378                 springs[temp_index].restlen =  sqrt(INPR(temp, temp));
1379                 springs[temp_index].type = SHEAR;
1380
1381                 BLI_linklist_append(&edgelist[springs[temp_index].ij], &(springs[temp_index]));         
1382                 BLI_linklist_append(&edgelist[springs[temp_index].kl], &(springs[temp_index]));
1383
1384                 shear_springs++;
1385                 temp_index++;
1386                 
1387                 if(mface[i].v4)
1388                 {
1389                         springs[temp_index].ij = mface[i].v2;
1390                         springs[temp_index].kl = mface[i].v4;
1391                         VECSUB(temp, mvert[springs[temp_index].kl].co, mvert[springs[temp_index].ij].co);
1392                         springs[temp_index].restlen =  sqrt(INPR(temp, temp));
1393                         springs[temp_index].type = SHEAR;
1394         
1395                         BLI_linklist_append(&edgelist[springs[temp_index].ij], &(springs[temp_index]));         
1396                         BLI_linklist_append(&edgelist[springs[temp_index].kl], &(springs[temp_index]));
1397         
1398                         shear_springs++;
1399                 }
1400         }
1401
1402         // bending springs
1403         for(i = struct_springs; i < struct_springs+shear_springs; i++)
1404         {       
1405                 search = edgelist[springs[i].kl];
1406                 while(search)
1407                 {
1408                         tspring = search->link;
1409                         index2 = ((tspring->ij==springs[i].kl) ? (tspring->kl) : (tspring->ij));
1410
1411                         if(!BLI_edgehash_haskey(edgehash, index2, springs[i].ij) // check for existing spring 
1412                                 && !BLI_edgehash_haskey(edgehash, springs[i].ij, index2)  // same
1413                                 && (index2!=springs[i].ij)) // check if startpoint is equal to endpoint
1414                         {
1415                                 temp_index = struct_springs + shear_springs + bend_springs;
1416
1417                                 springs[temp_index].ij = springs[i].ij;
1418                                 springs[temp_index].kl = index2;
1419                                 VECSUB(temp, mvert[index2].co, mvert[springs[i].ij].co);
1420                                 springs[temp_index].restlen =  sqrt(INPR(temp, temp));
1421                                 springs[temp_index].type = BENDING;
1422                                 BLI_edgehash_insert(edgehash, springs[temp_index].ij, index2, NULL);
1423                                 bend_springs++;
1424
1425                         }
1426                         search = search->next;   
1427                 }
1428         }
1429
1430         cloth->numsprings = struct_springs + shear_springs + bend_springs;
1431
1432         for(i = 0; i < numverts; i++)
1433         {
1434                 BLI_linklist_free(edgelist[i],NULL); 
1435         }
1436         if(edgelist)
1437                 MEM_freeN(edgelist);    
1438
1439         BLI_edgehash_free(edgehash, NULL);
1440
1441         return 1;
1442
1443 } /* cloth_build_springs */
1444 /***************************************************************************************
1445 * SPRING NETWORK BUILDING IMPLEMENTATION END
1446 ***************************************************************************************/
1447