Springs are in a dynamic list now, New function cloth_add_spring() for easier access...
[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 void tend ( void )
83 {
84 }
85 double tval()
86 {
87         return 0;
88 }
89 #else
90 #include <sys/time.h>
91 static struct timeval _tstart, _tend;
92 static struct timezone tz;
93 void tstart ( void )
94 {
95         gettimeofday ( &_tstart, &tz );
96 }
97 void tend ( void )
98 {
99         gettimeofday ( &_tend,&tz );
100 }
101 double tval()
102 {
103         double t1, t2;
104         t1 = ( double ) _tstart.tv_sec + ( double ) _tstart.tv_usec/ ( 1000*1000 );
105         t2 = ( double ) _tend.tv_sec + ( double ) _tend.tv_usec/ ( 1000*1000 );
106         return t2-t1;
107 }
108 #endif
109
110 /* Our available solvers. */
111 // 255 is the magic reserved number, so NEVER try to put 255 solvers in here!
112 // 254 = MAX!
113 static CM_SOLVER_DEF    solvers [] =
114     {
115         { "Implicit", CM_IMPLICIT, implicit_init, implicit_solver, implicit_free },
116         // { "Implicit C++", CM_IMPLICITCPP, implicitcpp_init, implicitcpp_solver, implicitcpp_free },
117     };
118
119 /* ********** cloth engine ******* */
120 /* Prototypes for internal functions.
121 */
122 static void cloth_to_object ( Object *ob, ClothModifierData *clmd, float ( *vertexCos ) [3], unsigned int numverts );
123 static void cloth_from_mesh ( Object *ob, ClothModifierData *clmd, DerivedMesh *dm );
124 static int cloth_from_object ( Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float ( *vertexCos ) [3], unsigned int numverts );
125 static int collobj_from_object ( Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float ( *vertexCos ) [3], unsigned int numverts );
126 int cloth_build_springs ( Cloth *cloth, DerivedMesh *dm );
127 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm, short vgroup );
128
129
130 /******************************************************************************
131 *
132 * External interface called by modifier.c clothModifier functions.
133 *
134 ******************************************************************************/
135 /**
136 * cloth_init -  creates a new cloth simulation.
137 *
138 * 1. create object
139 * 2. fill object with standard values or with the GUI settings if given
140 */
141 void cloth_init ( ClothModifierData *clmd )
142 {
143         /* Initialize our new data structure to reasonable values. */
144         clmd->sim_parms.gravity [0] = 0.0;
145         clmd->sim_parms.gravity [1] = 0.0;
146         clmd->sim_parms.gravity [2] = -9.81;
147         clmd->sim_parms.structural = 100.0;
148         clmd->sim_parms.shear = 100.0;
149         clmd->sim_parms.bending = 1.0;
150         clmd->sim_parms.Cdis = 5.0;
151         clmd->sim_parms.Cvi = 1.0;
152         clmd->sim_parms.mass = 1.0f;
153         clmd->sim_parms.stepsPerFrame = 5;
154         clmd->sim_parms.sim_time = 1.0;
155         clmd->sim_parms.flags = CLOTH_SIMSETTINGS_FLAG_RESET;
156         clmd->sim_parms.solver_type = 0;
157         clmd->sim_parms.preroll = 0;
158         clmd->sim_parms.maxspringlen = 10;
159         clmd->sim_parms.firstframe = 1;
160         clmd->sim_parms.lastframe = 250;
161         clmd->coll_parms.self_friction = 5.0;
162         clmd->coll_parms.friction = 10.0;
163         clmd->coll_parms.loop_count = 1;
164         clmd->coll_parms.epsilon = 0.01f;
165         clmd->coll_parms.flags = 0;
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 & CLOTH_SPRING_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
408         if ( clmd->clothObject )
409         {
410                 search = clmd->sim_parms.cache;
411
412                 while ( search )
413                 {
414                         frame = ( Frame * ) search->link;
415
416                         if ( frame )
417                         {
418                                 if ( frame->time == time )
419                                         return 1;
420                         }
421
422                         search = search->next;
423                 }
424         }
425
426         return 0;
427
428 }
429
430 float cloth_cache_last_frame ( ClothModifierData *clmd )
431 {
432         Frame *frame = NULL;
433         LinkNode *search = NULL;
434         float time = 0;
435
436         if ( clmd->clothObject )
437         {
438                 search = clmd->sim_parms.cache;
439
440                 while ( search )
441                 {
442                         frame = ( Frame * ) search->link;
443
444                         if ( frame )
445                         {
446                                 if ( frame->time > time )
447                                         time = frame->time;
448                         }
449                 }
450         }
451         return time;
452 }
453
454 float cloth_cache_first_frame ( ClothModifierData *clmd )
455 {
456         Frame *frame = NULL;
457         LinkNode *search = NULL;
458         float time = -1.0;
459
460         if ( clmd->clothObject )
461         {
462                 search = clmd->sim_parms.cache;
463
464                 while ( search )
465                 {
466                         frame = ( Frame * ) search->link;
467
468                         if ( frame )
469                         {
470                                 if ( time < 0.0 )
471                                         time = frame->time;
472                                 else
473                                 {
474                                         if ( frame->time < time )
475                                                 time = frame->time;
476                                 }
477                         }
478                 }
479         }
480         return time;
481 }
482
483 void cloth_cache_get_frame ( ClothModifierData *clmd, float time )
484 {
485         Frame *frame = NULL;
486         LinkNode *search = NULL;
487         float newtime = time + clmd->sim_parms.preroll;
488
489         if ( clmd->clothObject )
490         {
491                 search = clmd->sim_parms.cache;
492
493                 while ( search )
494                 {
495                         frame = ( Frame * ) search->link;
496
497                         if ( frame )
498                         {
499                                 if ( frame->time == newtime )
500                                 {
501                                         // something changed, free cache!
502                                         if ( clmd->clothObject->numverts != frame->numverts )
503                                         {
504                                                 cloth_cache_free ( clmd, 0 );
505                                                 printf ( "clmd->clothObject->numverts != frame->numverts\n" );
506                                                 return;
507                                         }
508
509                                         memcpy ( clmd->clothObject->verts, frame->verts, sizeof ( ClothVertex ) *frame->numverts );
510                                         implicit_set_positions ( clmd );
511
512                                         return;
513                                 }
514                         }
515
516                         search = search->next;
517                 }
518         }
519 }
520
521 void cloth_cache_set_frame ( ClothModifierData *clmd, float time )
522 {
523         Frame *frame = NULL;
524         LinkNode *search = NULL;
525
526         if ( clmd->clothObject )
527         {
528                 frame = ( Frame * ) MEM_callocN ( sizeof ( Frame ), "cloth_cache_frame" );
529
530                 if ( frame )
531                 {
532                         frame->time = time;
533                         frame->numverts = clmd->clothObject->numverts;
534                         frame->verts = MEM_dupallocN ( clmd->clothObject->verts );
535
536                         if ( !frame->verts )
537                         {
538                                 MEM_freeN ( frame );
539                                 return;
540                         }
541
542                         BLI_linklist_append ( &clmd->sim_parms.cache, frame );
543
544                 }
545         }
546
547 }
548
549 // free cloth cache
550 void cloth_cache_free ( ClothModifierData *clmd, float time )
551 {
552         Frame *frame = NULL;
553         LinkNode *search = NULL, *lastsearch = NULL;
554         float newtime = time + clmd->sim_parms.preroll;
555
556         if ( time <= 2.0 )
557                 newtime = time;
558
559         if ( clmd->clothObject )
560         {
561                 if ( clmd->sim_parms.cache )
562                 {
563                         lastsearch = search = clmd->sim_parms.cache;
564
565                         while ( search )
566                         {
567                                 frame = ( Frame * ) search->link;
568
569                                 if ( frame->time >= newtime )
570                                 {
571                                         if ( frame->verts )
572                                         {
573                                                 MEM_freeN ( frame->verts );
574                                         }
575                                         MEM_freeN ( frame );
576
577                                         lastsearch->next = search->next;
578                                         MEM_freeN ( search );
579                                         search = lastsearch->next;
580                                         lastsearch->next = NULL;
581                                 }
582                                 else
583                                 {
584                                         lastsearch = search;
585                                         search = search->next;
586                                 }
587                         }
588
589                         if ( time <= 1.0 )
590                         {
591                                 clmd->sim_parms.cache = NULL;
592                         }
593
594                         if ( time <= 2.0 )
595                                 clmd->sim_parms.preroll = 0;
596                 }
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
625         // only be active during a specific period:
626         // that's "first frame" and "last frame" on GUI
627         if ( ! ( clmd->sim_parms.flags & CLOTH_SIMSETTINGS_FLAG_COLLOBJ ) )
628         {
629                 if ( clmd->clothObject )
630                 {
631                         if ( clmd->sim_parms.cache )
632                         {
633                                 if ( current_time < clmd->sim_parms.firstframe )
634                                 {
635                                         int frametime = cloth_cache_first_frame ( clmd );
636                                         if ( cloth_cache_search_frame ( clmd, frametime ) )
637                                         {
638                                                 cloth_cache_get_frame ( clmd, frametime );
639                                                 cloth_to_object ( ob, clmd, vertexCos, numverts );
640                                         }
641                                         return;
642                                 }
643                                 else if ( current_time > clmd->sim_parms.lastframe )
644                                 {
645                                         int frametime = cloth_cache_last_frame ( clmd );
646                                         if ( cloth_cache_search_frame ( clmd, frametime ) )
647                                         {
648                                                 cloth_cache_get_frame ( clmd, frametime );
649                                                 cloth_to_object ( ob, clmd, vertexCos, numverts );
650                                         }
651                                         return;
652                                 }
653                                 else if ( ABS ( deltaTime ) >= 2.0f ) // no timewarps allowed
654                                 {
655                                         if ( cloth_cache_search_frame ( clmd, framenr ) )
656                                         {
657                                                 cloth_cache_get_frame ( clmd, framenr );
658                                                 cloth_to_object ( ob, clmd, vertexCos, numverts );
659                                         }
660                                         clmd->sim_parms.sim_time = current_time;
661                                         return;
662                                 }
663                         }
664
665                 }
666         }
667
668
669         // unused in the moment, calculated seperately in implicit.c
670         clmd->sim_parms.dt = 1.0f / clmd->sim_parms.stepsPerFrame;
671
672         clmd->sim_parms.sim_time = current_time;
673
674         // check if cloth object was some collision object before and needs freeing now
675         if ( ! ( clmd->sim_parms.flags & CLOTH_SIMSETTINGS_FLAG_COLLOBJ ) && ( clmd->clothObject != NULL ) && ( clmd->clothObject->old_solver_type == 255 ) )
676         {
677                 // temporary set CSIMSETT_FLAG_COLLOBJ flag for proper freeing
678                 clmd->sim_parms.flags |= CLOTH_SIMSETTINGS_FLAG_COLLOBJ;
679                 cloth_free_modifier ( clmd );
680                 clmd->sim_parms.flags &= ~CLOTH_SIMSETTINGS_FLAG_COLLOBJ;
681         }
682
683         // This is for collisions objects: check special case CSIMSETT_FLAG_COLLOBJ
684         if ( clmd->sim_parms.flags & CLOTH_SIMSETTINGS_FLAG_COLLOBJ )
685         {
686                 // save next position + time
687                 if ( ( clmd->clothObject == NULL ) || ( numverts != clmd->clothObject->numverts ) )
688                 {
689                         if ( !collobj_from_object ( ob, clmd, dm, vertexCos, framenr ) )
690                         {
691                                 clmd->sim_parms.flags |= CLOTH_SIMSETTINGS_FLAG_COLLOBJ;
692                                 cloth_free_modifier ( clmd );
693                                 return;
694                         }
695
696                         if ( clmd->clothObject == NULL )
697                                 return;
698
699                         cloth = clmd->clothObject;
700                 }
701
702                 // Save old position
703                 clmd->sim_parms.sim_time_old = clmd->sim_parms.sim_time;
704                 clmd->sim_parms.sim_time = current_time;
705
706                 verts = cloth->verts;
707
708                 for ( i = 0; i < clmd->clothObject->numverts; i++, verts++ )
709                 {
710                         // Save the previous position.
711                         VECCOPY ( verts->xold, verts->x );
712                         VECCOPY ( verts->txold, verts->x );
713
714                         // Get the current position.
715                         VECCOPY ( verts->x, vertexCos[i] );
716                         Mat4MulVecfl ( ob->obmat, verts->x );
717
718                         // Compute the vertices "velocity".
719                         // (no dt correction here because of float error)
720                         VECSUB ( verts->v, verts->x, verts->xold );
721                 }
722
723                 return;
724         }
725
726         if ( deltaTime == 1.0f )
727         {
728                 if ( ( clmd->clothObject == NULL ) || ( numverts != clmd->clothObject->numverts ) )
729                 {
730                         if ( !cloth_from_object ( ob, clmd, dm, vertexCos, numverts ) )
731                                 return;
732
733                         if ( clmd->clothObject == NULL )
734                                 return;
735
736                         cloth = clmd->clothObject;
737                 }
738
739                 clmd->clothObject->old_solver_type = clmd->sim_parms.solver_type;
740
741                 // Insure we have a clmd->clothObject, in case allocation failed.
742                 if ( clmd->clothObject != NULL )
743                 {
744                         if ( !cloth_cache_search_frame ( clmd, framenr ) )
745                         {
746                                 verts = cloth->verts;
747
748                                 // Force any pinned verts to their constrained location.
749                                 for ( i = 0; i < clmd->clothObject->numverts; i++, verts++ )
750                                 {
751                                         // Save the previous position.
752                                         VECCOPY ( verts->xold, verts->xconst );
753                                         VECCOPY ( verts->txold, verts->x );
754
755                                         // Get the current position.
756                                         VECCOPY ( verts->xconst, vertexCos[i] );
757                                         Mat4MulVecfl ( ob->obmat, verts->xconst );
758                                 }
759
760                                 tstart();
761
762                                 // Call the solver.
763                                 if ( solvers [clmd->sim_parms.solver_type].solver )
764                                         solvers [clmd->sim_parms.solver_type].solver ( ob, framenr, clmd, effectors );
765
766                                 tend();
767                                 printf ( "Cloth simulation time: %f\n", ( float ) tval() );
768
769                                 cloth_cache_set_frame ( clmd, framenr );
770
771                         }
772                         else // just retrieve the cached frame
773                         {
774                                 cloth_cache_get_frame ( clmd, framenr );
775                         }
776
777                         // Copy the result back to the object.
778                         cloth_to_object ( ob, clmd, vertexCos, numverts );
779
780                         // bvh_free(clmd->clothObject->tree);
781                         // clmd->clothObject->tree = bvh_build(clmd, clmd->coll_parms.epsilon);
782                 }
783
784         }
785         else if ( ( deltaTime <= 0.0f ) || ( deltaTime > 1.0f ) )
786         {
787                 if ( ( clmd->clothObject != NULL ) && ( clmd->sim_parms.cache ) )
788                 {
789                         if ( cloth_cache_search_frame ( clmd, framenr ) )
790                         {
791                                 cloth_cache_get_frame ( clmd, framenr );
792                                 cloth_to_object ( ob, clmd, vertexCos, numverts );
793                         }
794                 }
795         }
796
797 }
798
799 /* frees all */
800 void cloth_free_modifier ( ClothModifierData *clmd )
801 {
802         Cloth   *cloth = NULL;
803
804         if ( !clmd )
805                 return;
806
807         cloth = clmd->clothObject;
808
809         if ( ! ( clmd->sim_parms.flags & CLOTH_SIMSETTINGS_FLAG_CCACHE_PROTECT ) )
810         {
811                 // free our frame cache, TODO: but get to first position before
812                 cloth_cache_free ( clmd, 0 );
813
814                 if ( cloth )
815                 {
816
817                         // If our solver provides a free function, call it
818                         if ( cloth->old_solver_type < 255 && solvers [cloth->old_solver_type].free )
819                         {
820                                 solvers [cloth->old_solver_type].free ( clmd );
821                         }
822
823                         // Free the verts.
824                         if ( cloth->verts != NULL )
825                                 MEM_freeN ( cloth->verts );
826
827                         cloth->verts = NULL;
828                         cloth->numverts = 0;
829
830                         // Free the springs.
831                         if ( cloth->springs != NULL )
832                         {
833                                 LinkNode *search = cloth->springs;
834                                 while(search)
835                                 {
836                                         ClothSpring *spring = search->link;
837                                                         
838                                         MEM_freeN ( spring );
839                                         search = search->next;
840                                 }
841                                 BLI_linklist_free(cloth->springs, NULL);
842                         
843                                 cloth->springs = NULL;
844                         }
845
846                         cloth->springs = NULL;
847                         cloth->numsprings = 0;
848
849                         // free BVH collision tree
850                         if ( cloth->tree )
851                                 bvh_free ( ( BVH * ) cloth->tree );
852
853                         // we save our faces for collision objects
854                         if ( cloth->mfaces )
855                                 MEM_freeN ( cloth->mfaces );
856                         /*
857                         if(clmd->clothObject->facemarks)
858                                 MEM_freeN(clmd->clothObject->facemarks);
859                         */
860                         MEM_freeN ( cloth );
861                         clmd->clothObject = NULL;
862                 }
863         }
864 }
865
866
867 /******************************************************************************
868 *
869 * Internal functions.
870 *
871 ******************************************************************************/
872
873 /**
874 * cloth_to_object - copies the deformed vertices to the object.
875 *
876 * This function is a modified version of the softbody.c:softbody_to_object() function.
877 **/
878 static void cloth_to_object ( Object *ob, ClothModifierData *clmd, float ( *vertexCos ) [3], unsigned int numverts )
879 {
880         ClothVertex     *verts = NULL;
881         unsigned int    i = 0;
882
883         if ( clmd->clothObject )
884         {
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 & CLOTH_SIMSETTINGS_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 // only meshes supported at the moment
1038 static int cloth_from_object ( Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float ( *vertexCos ) [3], unsigned int numverts )
1039 {
1040         unsigned int i = 0;
1041         // dm->getNumVerts(dm);
1042         MVert *mvert = NULL; // CDDM_get_verts(dm);
1043         ClothVertex *verts = NULL;
1044         float tnull[3] = {0,0,0};
1045
1046         /* If we have a clothObject, free it. */
1047         if ( clmd->clothObject != NULL )
1048                 cloth_free_modifier ( clmd );
1049
1050         /* Allocate a new cloth object. */
1051         clmd->clothObject = MEM_callocN ( sizeof ( Cloth ), "cloth" );
1052         if ( clmd->clothObject )
1053         {
1054                 clmd->clothObject->old_solver_type = 255;
1055                 // clmd->clothObject->old_collision_type = 255;
1056         }
1057         else if ( !clmd->clothObject )
1058         {
1059                 modifier_setError ( & ( clmd->modifier ), "Out of memory on allocating clmd->clothObject." );
1060                 return 0;
1061         }
1062
1063         switch ( ob->type )
1064         {
1065                 case OB_MESH:
1066
1067                         // mesh input objects need DerivedMesh
1068                         if ( !dm )
1069                                 return 0;
1070
1071                         cloth_from_mesh ( ob, clmd, dm );
1072
1073                         if ( clmd->clothObject != NULL )
1074                         {
1075                                 /* create springs */
1076                                 clmd->clothObject->springs = NULL;
1077                                 clmd->clothObject->numsprings = -1;
1078
1079                                 if ( !cloth_build_springs ( clmd->clothObject, dm ) )
1080                                 {
1081                                         modifier_setError ( & ( clmd->modifier ), "Can't build springs." );
1082                                         return 0;
1083                                 }
1084
1085                                 mvert = CDDM_get_verts ( dm );
1086                                 verts = clmd->clothObject->verts;
1087
1088                                 /* set initial values */
1089                                 for ( i = 0; i < numverts; i++, verts++ )
1090                                 {
1091                                         VECCOPY ( verts->x, mvert[i].co );
1092                                         Mat4MulVecfl ( ob->obmat, verts->x );
1093
1094                                         verts->mass = clmd->sim_parms.mass;
1095
1096                                         if ( clmd->sim_parms.flags & CLOTH_SIMSETTINGS_FLAG_GOAL )
1097                                                 verts->goal= clmd->sim_parms.defgoal;
1098                                         else
1099                                                 verts->goal= 0.0f;
1100
1101                                         verts->flags = 0;
1102                                         VECCOPY ( verts->xold, verts->x );
1103                                         VECCOPY ( verts->xconst, verts->x );
1104                                         VECCOPY ( verts->txold, verts->x );
1105                                         VecMulf ( verts->v, 0.0f );
1106
1107                                         verts->impulse_count = 0;
1108                                         VECCOPY ( verts->impulse, tnull );
1109                                 }
1110
1111                                 // apply / set vertex groups
1112                                 if ( clmd->sim_parms.vgroup_mass > 0 )
1113                                         cloth_apply_vgroup ( clmd, dm, clmd->sim_parms.vgroup_mass );
1114
1115                                 // init our solver
1116                                 if ( solvers [clmd->sim_parms.solver_type].init )
1117                                         solvers [clmd->sim_parms.solver_type].init ( ob, clmd );
1118
1119                                 clmd->clothObject->tree = bvh_build ( clmd, clmd->coll_parms.epsilon );
1120
1121                                 cloth_cache_set_frame ( clmd, 1 );
1122                         }
1123
1124                         return 1;
1125                 case OB_LATTICE:
1126                         printf ( "Not supported: OB_LATTICE\n" );
1127                         // lattice_to_softbody(ob);
1128                         return 1;
1129                 case OB_CURVE:
1130                 case OB_SURF:
1131                         printf ( "Not supported: OB_SURF| OB_CURVE\n" );
1132                         return 1;
1133                 default: return 0; // TODO - we do not support changing meshes
1134         }
1135
1136         return 0;
1137 }
1138
1139 static void cloth_from_mesh ( Object *ob, ClothModifierData *clmd, DerivedMesh *dm )
1140 {
1141         unsigned int numverts = dm->getNumVerts ( dm );
1142         unsigned int numfaces = dm->getNumFaces ( dm );
1143         MFace *mface = dm->getFaceArray ( dm );
1144         unsigned int i = 0;
1145
1146         /* Allocate our vertices.
1147         */
1148         clmd->clothObject->numverts = numverts;
1149         clmd->clothObject->verts = MEM_callocN ( sizeof ( ClothVertex ) * clmd->clothObject->numverts, "clothVertex" );
1150         if ( clmd->clothObject->verts == NULL )
1151         {
1152                 cloth_free_modifier ( clmd );
1153                 modifier_setError ( & ( clmd->modifier ), "Out of memory on allocating clmd->clothObject->verts." );
1154                 return;
1155         }
1156
1157         // save face information
1158         clmd->clothObject->numfaces = numfaces;
1159         clmd->clothObject->mfaces = MEM_callocN ( sizeof ( MFace ) * clmd->clothObject->numfaces, "clothMFaces" );
1160         if ( clmd->clothObject->mfaces == NULL )
1161         {
1162                 cloth_free_modifier ( clmd );
1163                 modifier_setError ( & ( clmd->modifier ), "Out of memory on allocating clmd->clothObject->mfaces." );
1164                 return;
1165         }
1166         for ( i = 0; i < numfaces; i++ )
1167                 memcpy ( &clmd->clothObject->mfaces[i], &mface[i], sizeof ( MFace ) );
1168
1169         /* Free the springs since they can't be correct if the vertices
1170         * changed.
1171         */
1172         if ( clmd->clothObject->springs != NULL )
1173                 MEM_freeN ( clmd->clothObject->springs );
1174
1175 }
1176
1177 /***************************************************************************************
1178 * SPRING NETWORK BUILDING IMPLEMENTATION BEGIN
1179 ***************************************************************************************/
1180
1181 // be carefull: implicit solver has to be resettet when using this one!
1182 int cloth_add_spring ( ClothModifierData *clmd, unsigned int indexA, unsigned int indexB, float restlength, int spring_type)
1183 {
1184         Cloth *cloth = clmd->clothObject;
1185         ClothSpring *spring = NULL;
1186         
1187         if(cloth)
1188         {
1189                 // TODO: look if this spring is already there
1190                 
1191                 spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1192                 
1193                 spring->ij = indexA;
1194                 spring->kl = indexB;
1195                 spring->restlen =  restlength;
1196                 spring->type = spring_type;
1197                 spring->flags = 0;
1198                 
1199                 cloth->numsprings++;
1200         
1201                 BLI_linklist_append ( &cloth->springs, spring );
1202         }
1203 }
1204
1205 int cloth_build_springs ( Cloth *cloth, DerivedMesh *dm )
1206 {
1207         ClothSpring *spring = NULL, *tspring = NULL, *tspring2 = NULL;
1208         unsigned int struct_springs = 0, shear_springs=0, bend_springs = 0;
1209         unsigned int i = 0;
1210         unsigned int numverts = dm->getNumVerts ( dm );
1211         unsigned int numedges = dm->getNumEdges ( dm );
1212         unsigned int numfaces = dm->getNumFaces ( dm );
1213         MVert *mvert = CDDM_get_verts ( dm );
1214         MEdge *medge = CDDM_get_edges ( dm );
1215         MFace *mface = CDDM_get_faces ( dm );
1216         unsigned int index2 = 0; // our second vertex index
1217         LinkNode **edgelist = NULL;
1218         EdgeHash *edgehash = NULL;
1219         LinkNode *search = NULL, *search2 = NULL;
1220         float temp[3];
1221
1222         // error handling
1223         if ( numedges==0 )
1224                 return 0;
1225
1226         cloth->springs = NULL;
1227
1228         edgelist = MEM_callocN ( sizeof ( LinkNode * ) * numverts, "cloth_edgelist_alloc" );
1229         for ( i = 0; i < numverts; i++ )
1230         {
1231                 edgelist[i] = NULL;
1232         }
1233
1234         if ( cloth->springs )
1235                 MEM_freeN ( cloth->springs );
1236
1237         // create spring network hash
1238         edgehash = BLI_edgehash_new();
1239
1240         // structural springs
1241         for ( i = 0; i < numedges; i++ )
1242         {
1243                 spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1244
1245                 if ( spring )
1246                 {
1247                         spring->ij = medge[i].v1;
1248                         spring->kl = medge[i].v2;
1249                         VECSUB ( temp, mvert[spring->kl].co, mvert[spring->ij].co );
1250                         spring->restlen =  sqrt ( INPR ( temp, temp ) );
1251                         spring->type = CLOTH_SPRING_TYPE_STRUCTURAL;
1252                         spring->flags = 0;
1253                         struct_springs++;
1254
1255                         BLI_linklist_append ( &cloth->springs, spring );
1256                 }
1257         }
1258
1259         // shear springs
1260         for ( i = 0; i < numfaces; i++ )
1261         {
1262                 spring = ( ClothSpring *) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1263
1264                 spring->ij = mface[i].v1;
1265                 spring->kl = mface[i].v3;
1266                 VECSUB ( temp, mvert[spring->kl].co, mvert[spring->ij].co );
1267                 spring->restlen =  sqrt ( INPR ( temp, temp ) );
1268                 spring->type = CLOTH_SPRING_TYPE_SHEAR;
1269
1270                 BLI_linklist_append ( &edgelist[spring->ij], spring );
1271                 BLI_linklist_append ( &edgelist[spring->kl], spring );
1272                 shear_springs++;
1273
1274                 BLI_linklist_append ( &cloth->springs, spring );
1275
1276                 if ( mface[i].v4 )
1277                 {
1278                         spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1279
1280                         spring->ij = mface[i].v1;
1281                         spring->kl = mface[i].v3;
1282                         VECSUB ( temp, mvert[spring->kl].co, mvert[spring->ij].co );
1283                                 spring->restlen =  sqrt ( INPR ( temp, temp ) );
1284                                 spring->type = CLOTH_SPRING_TYPE_SHEAR;
1285
1286                                 BLI_linklist_append ( &edgelist[spring->ij], spring );
1287                                 BLI_linklist_append ( &edgelist[spring->kl], spring );
1288                                 shear_springs++;
1289
1290                                 BLI_linklist_append ( &cloth->springs, spring );
1291                 }
1292         }
1293
1294         // bending springs
1295         search2 = cloth->springs;
1296         for ( i = struct_springs; i < struct_springs+shear_springs; i++ )
1297         {
1298                 if ( !search2 )
1299                         break;
1300
1301                 tspring2 = search2->link;
1302                 search = edgelist[tspring2->kl];
1303                 while ( search )
1304                 {
1305                         tspring = search->link;
1306                         index2 = ( ( tspring->ij==tspring2->kl ) ? ( tspring->kl ) : ( tspring->ij ) );
1307                         
1308                         // check for existing spring
1309                         // check also if startpoint is equal to endpoint
1310                         if ( !BLI_edgehash_haskey ( edgehash, index2, tspring2->ij )
1311                                 && !BLI_edgehash_haskey ( edgehash, tspring2->ij, index2 )
1312                                 && ( index2!=tspring2->ij ) )
1313                         {
1314                                 spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1315
1316                                 spring->ij = tspring2->ij;
1317                                 spring->kl = index2;
1318                                 VECSUB ( temp, mvert[index2].co, mvert[tspring2->ij].co );
1319                                 spring->restlen =  sqrt ( INPR ( temp, temp ) );
1320                                 spring->type = CLOTH_SPRING_TYPE_BENDING;
1321                                 BLI_edgehash_insert ( edgehash, spring->ij, index2, NULL );
1322                                 bend_springs++;
1323
1324                                 BLI_linklist_append ( &cloth->springs, spring );
1325                         }
1326                         search = search->next;
1327                 }
1328                 search2 = search2->next;
1329         }
1330
1331         cloth->numsprings = struct_springs + shear_springs + bend_springs;
1332
1333         for ( i = 0; i < numverts; i++ )
1334         {
1335                 BLI_linklist_free ( edgelist[i],NULL );
1336         }
1337         if ( edgelist )
1338                 MEM_freeN ( edgelist );
1339
1340         BLI_edgehash_free ( edgehash, NULL );
1341
1342         return 1;
1343
1344 } /* cloth_build_springs */
1345 /***************************************************************************************
1346 * SPRING NETWORK BUILDING IMPLEMENTATION END
1347 ***************************************************************************************/
1348