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