f1b167b38c7c927b2cda6a155f81394abcad477c
[blender.git] / source / blender / blenkernel / intern / cloth.c
1 /*  cloth.c
2 *
3 *
4 * ***** BEGIN GPL 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.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 *
20 * The Original Code is Copyright (C) Blender Foundation
21 * All rights reserved.
22 *
23 * Contributor(s): Daniel Genrich
24 *
25 * ***** END GPL LICENSE BLOCK *****
26 */
27
28 #include "MEM_guardedalloc.h"
29
30 #include "DNA_cloth_types.h"
31 #include "DNA_scene_types.h"
32 #include "DNA_object_types.h"
33 #include "DNA_meshdata_types.h"
34
35 #include "BLI_math.h"
36 #include "BLI_edgehash.h"
37
38 #include "BKE_cdderivedmesh.h"
39 #include "BKE_cloth.h"
40 #include "BKE_effect.h"
41 #include "BKE_global.h"
42 #include "BKE_modifier.h"
43 #include "BKE_pointcache.h"
44 #include "BKE_utildefines.h"
45
46 #ifdef _WIN32
47 void tstart ( void )
48 {}
49 void tend ( void )
50 {
51 }
52 double tval()
53 {
54         return 0;
55 }
56 #else
57 #include <sys/time.h>
58                          static struct timeval _tstart, _tend;
59          static struct timezone tz;
60          void tstart ( void )
61 {
62         gettimeofday ( &_tstart, &tz );
63 }
64 void tend ( void )
65 {
66         gettimeofday ( &_tend,&tz );
67 }
68 double tval()
69 {
70         double t1, t2;
71         t1 = ( double ) _tstart.tv_sec + ( double ) _tstart.tv_usec/ ( 1000*1000 );
72         t2 = ( double ) _tend.tv_sec + ( double ) _tend.tv_usec/ ( 1000*1000 );
73         return t2-t1;
74 }
75 #endif
76
77 /* Our available solvers. */
78 // 255 is the magic reserved number, so NEVER try to put 255 solvers in here!
79 // 254 = MAX!
80 static CM_SOLVER_DEF    solvers [] =
81 {
82         { "Implicit", CM_IMPLICIT, implicit_init, implicit_solver, implicit_free },
83                 // { "Implicit C++", CM_IMPLICITCPP, implicitcpp_init, implicitcpp_solver, implicitcpp_free },
84 };
85
86 /* ********** cloth engine ******* */
87 /* Prototypes for internal functions.
88 */
89 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, DerivedMesh *dm);
90 static void cloth_from_mesh ( ClothModifierData *clmd, DerivedMesh *dm );
91 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float framenr, int first);
92 static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm );
93 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm );
94
95
96 /******************************************************************************
97 *
98 * External interface called by modifier.c clothModifier functions.
99 *
100 ******************************************************************************/
101 /**
102  * cloth_init -  creates a new cloth simulation.
103  *
104  * 1. create object
105  * 2. fill object with standard values or with the GUI settings if given
106  */
107 void cloth_init ( ClothModifierData *clmd )
108 {       
109         /* Initialize our new data structure to reasonable values. */
110         clmd->sim_parms->gravity [0] = 0.0;
111         clmd->sim_parms->gravity [1] = 0.0;
112         clmd->sim_parms->gravity [2] = -9.81;
113         clmd->sim_parms->structural = 15.0;
114         clmd->sim_parms->shear = 15.0;
115         clmd->sim_parms->bending = 0.5;
116         clmd->sim_parms->Cdis = 5.0; 
117         clmd->sim_parms->Cvi = 1.0;
118         clmd->sim_parms->mass = 0.3f;
119         clmd->sim_parms->stepsPerFrame = 5;
120         clmd->sim_parms->flags = 0;
121         clmd->sim_parms->solver_type = 0;
122         clmd->sim_parms->preroll = 0;
123         clmd->sim_parms->maxspringlen = 10;
124         clmd->sim_parms->vgroup_mass = 0;
125         clmd->sim_parms->avg_spring_len = 0.0;
126         clmd->sim_parms->presets = 2; /* cotton as start setting */
127         clmd->sim_parms->timescale = 1.0f; /* speed factor, describes how fast cloth moves */
128         clmd->sim_parms->reset = 0;
129         
130         clmd->coll_parms->self_friction = 5.0;
131         clmd->coll_parms->friction = 5.0;
132         clmd->coll_parms->loop_count = 2;
133         clmd->coll_parms->epsilon = 0.015f;
134         clmd->coll_parms->flags = CLOTH_COLLSETTINGS_FLAG_ENABLED;
135         clmd->coll_parms->collision_list = NULL;
136         clmd->coll_parms->self_loop_count = 1.0;
137         clmd->coll_parms->selfepsilon = 0.75;
138
139         /* These defaults are copied from softbody.c's
140         * softbody_calc_forces() function.
141         */
142         clmd->sim_parms->eff_force_scale = 1000.0;
143         clmd->sim_parms->eff_wind_scale = 250.0;
144
145         // also from softbodies
146         clmd->sim_parms->maxgoal = 1.0f;
147         clmd->sim_parms->mingoal = 0.0f;
148         clmd->sim_parms->defgoal = 0.0f;
149         clmd->sim_parms->goalspring = 1.0f;
150         clmd->sim_parms->goalfrict = 0.0f;
151         clmd->sim_parms->velocity_smooth = 0.0f;
152
153         if(!clmd->sim_parms->effector_weights)
154                 clmd->sim_parms->effector_weights = BKE_add_effector_weights(NULL);
155
156         if(clmd->point_cache)
157                 clmd->point_cache->step = 1;
158 }
159
160 static BVHTree *bvhselftree_build_from_cloth (ClothModifierData *clmd, float epsilon)
161 {
162         unsigned int i;
163         BVHTree *bvhtree;
164         Cloth *cloth;
165         ClothVertex *verts;
166         MFace *mfaces;
167         float co[12];
168
169         if(!clmd)
170                 return NULL;
171
172         cloth = clmd->clothObject;
173
174         if(!cloth)
175                 return NULL;
176         
177         verts = cloth->verts;
178         mfaces = cloth->mfaces;
179         
180         // in the moment, return zero if no faces there
181         if(!cloth->numverts)
182                 return NULL;
183         
184         // create quadtree with k=26
185         bvhtree = BLI_bvhtree_new(cloth->numverts, epsilon, 4, 6);
186         
187         // fill tree
188         for(i = 0; i < cloth->numverts; i++, verts++)
189         {
190                 VECCOPY(&co[0*3], verts->xold);
191                 
192                 BLI_bvhtree_insert(bvhtree, i, co, 1);
193         }
194         
195         // balance tree
196         BLI_bvhtree_balance(bvhtree);
197         
198         return bvhtree;
199 }
200
201 static BVHTree *bvhtree_build_from_cloth (ClothModifierData *clmd, float epsilon)
202 {
203         unsigned int i;
204         BVHTree *bvhtree;
205         Cloth *cloth;
206         ClothVertex *verts;
207         MFace *mfaces;
208         float co[12];
209
210         if(!clmd)
211                 return NULL;
212
213         cloth = clmd->clothObject;
214
215         if(!cloth)
216                 return NULL;
217         
218         verts = cloth->verts;
219         mfaces = cloth->mfaces;
220         
221         // in the moment, return zero if no faces there
222         if(!cloth->numfaces)
223                 return NULL;
224         
225         // create quadtree with k=26
226         bvhtree = BLI_bvhtree_new(cloth->numfaces, epsilon, 4, 26);
227         
228         // fill tree
229         for(i = 0; i < cloth->numfaces; i++, mfaces++)
230         {
231                 VECCOPY(&co[0*3], verts[mfaces->v1].xold);
232                 VECCOPY(&co[1*3], verts[mfaces->v2].xold);
233                 VECCOPY(&co[2*3], verts[mfaces->v3].xold);
234                 
235                 if(mfaces->v4)
236                         VECCOPY(&co[3*3], verts[mfaces->v4].xold);
237                 
238                 BLI_bvhtree_insert(bvhtree, i, co, (mfaces->v4 ? 4 : 3));
239         }
240         
241         // balance tree
242         BLI_bvhtree_balance(bvhtree);
243         
244         return bvhtree;
245 }
246
247 void bvhtree_update_from_cloth(ClothModifierData *clmd, int moving)
248 {       
249         unsigned int i = 0;
250         Cloth *cloth = clmd->clothObject;
251         BVHTree *bvhtree = cloth->bvhtree;
252         ClothVertex *verts = cloth->verts;
253         MFace *mfaces;
254         float co[12], co_moving[12];
255         int ret = 0;
256         
257         if(!bvhtree)
258                 return;
259         
260         mfaces = cloth->mfaces;
261         
262         // update vertex position in bvh tree
263         if(verts && mfaces)
264         {
265                 for(i = 0; i < cloth->numfaces; i++, mfaces++)
266                 {
267                         VECCOPY(&co[0*3], verts[mfaces->v1].txold);
268                         VECCOPY(&co[1*3], verts[mfaces->v2].txold);
269                         VECCOPY(&co[2*3], verts[mfaces->v3].txold);
270                         
271                         if(mfaces->v4)
272                                 VECCOPY(&co[3*3], verts[mfaces->v4].txold);
273                 
274                         // copy new locations into array
275                         if(moving)
276                         {
277                                 // update moving positions
278                                 VECCOPY(&co_moving[0*3], verts[mfaces->v1].tx);
279                                 VECCOPY(&co_moving[1*3], verts[mfaces->v2].tx);
280                                 VECCOPY(&co_moving[2*3], verts[mfaces->v3].tx);
281                                 
282                                 if(mfaces->v4)
283                                         VECCOPY(&co_moving[3*3], verts[mfaces->v4].tx);
284                                 
285                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, co_moving, (mfaces->v4 ? 4 : 3));
286                         }
287                         else
288                         {
289                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, NULL, (mfaces->v4 ? 4 : 3));
290                         }
291                         
292                         // check if tree is already full
293                         if(!ret)
294                                 break;
295                 }
296                 
297                 BLI_bvhtree_update_tree(bvhtree);
298         }
299 }
300
301 void bvhselftree_update_from_cloth(ClothModifierData *clmd, int moving)
302 {       
303         unsigned int i = 0;
304         Cloth *cloth = clmd->clothObject;
305         BVHTree *bvhtree = cloth->bvhselftree;
306         ClothVertex *verts = cloth->verts;
307         MFace *mfaces;
308         float co[12], co_moving[12];
309         int ret = 0;
310         
311         if(!bvhtree)
312                 return;
313         
314         mfaces = cloth->mfaces;
315         
316         // update vertex position in bvh tree
317         if(verts && mfaces)
318         {
319                 for(i = 0; i < cloth->numverts; i++, verts++)
320                 {
321                         VECCOPY(&co[0*3], verts->txold);
322                         
323                         // copy new locations into array
324                         if(moving)
325                         {
326                                 // update moving positions
327                                 VECCOPY(&co_moving[0*3], verts->tx);
328                                 
329                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, co_moving, 1);
330                         }
331                         else
332                         {
333                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, NULL, 1);
334                         }
335                         
336                         // check if tree is already full
337                         if(!ret)
338                                 break;
339                 }
340                 
341                 BLI_bvhtree_update_tree(bvhtree);
342         }
343 }
344
345 void cloth_clear_cache(Object *ob, ClothModifierData *clmd, float framenr)
346 {
347         PTCacheID pid;
348         
349         BKE_ptcache_id_from_cloth(&pid, ob, clmd);
350
351         // don't do anything as long as we're in editmode!
352         if(pid.cache->edit && ob->mode & OB_MODE_PARTICLE_EDIT)
353                 return;
354         
355         BKE_ptcache_id_clear(&pid, PTCACHE_CLEAR_AFTER, framenr);
356 }
357
358 static int do_init_cloth(Object *ob, ClothModifierData *clmd, DerivedMesh *result, int framenr)
359 {
360         PointCache *cache;
361
362         cache= clmd->point_cache;
363
364         /* initialize simulation data if it didn't exist already */
365         if(clmd->clothObject == NULL) { 
366                 if(!cloth_from_object(ob, clmd, result, framenr, 1)) {
367                         BKE_ptcache_invalidate(cache);
368                         return 0;
369                 }
370         
371                 if(clmd->clothObject == NULL) {
372                         BKE_ptcache_invalidate(cache);
373                         return 0;
374                 }
375         
376                 implicit_set_positions(clmd);
377         }
378
379         return 1;
380 }
381
382 static int do_step_cloth(Object *ob, ClothModifierData *clmd, DerivedMesh *result, int framenr)
383 {
384         ClothVertex *verts = NULL;
385         Cloth *cloth;
386         ListBase *effectors = NULL;
387         MVert *mvert;
388         int i, ret = 0;
389
390         /* simulate 1 frame forward */
391         cloth = clmd->clothObject;
392         verts = cloth->verts;
393         mvert = result->getVertArray(result);
394
395         /* force any pinned verts to their constrained location. */
396         for(i = 0; i < clmd->clothObject->numverts; i++, verts++) {
397                 /* save the previous position. */
398                 VECCOPY(verts->xold, verts->xconst);
399                 VECCOPY(verts->txold, verts->x);
400
401                 /* Get the current position. */
402                 VECCOPY(verts->xconst, mvert[i].co);
403                 mul_m4_v3(ob->obmat, verts->xconst);
404         }
405
406         effectors = pdInitEffectors(clmd->scene, ob, NULL, clmd->sim_parms->effector_weights);
407         
408         tstart();
409
410         /* call the solver. */
411         if(solvers [clmd->sim_parms->solver_type].solver)
412                 ret = solvers[clmd->sim_parms->solver_type].solver(ob, framenr, clmd, effectors);
413
414         tend();
415
416         pdEndEffectors(&effectors);
417
418         // printf ( "%f\n", ( float ) tval() );
419         
420         return ret;
421 }
422
423 /************************************************
424  * clothModifier_do - main simulation function
425 ************************************************/
426 DerivedMesh *clothModifier_do(ClothModifierData *clmd, Scene *scene, Object *ob, DerivedMesh *dm)
427 {
428         DerivedMesh *result;
429         PointCache *cache;
430         PTCacheID pid;
431         float timescale;
432         int framedelta, framenr, startframe, endframe;
433         int cache_result;
434
435         clmd->scene= scene;     /* nice to pass on later :) */
436         framenr= (int)scene->r.cfra;
437         cache= clmd->point_cache;
438         result = CDDM_copy(dm);
439
440         BKE_ptcache_id_from_cloth(&pid, ob, clmd);
441         BKE_ptcache_id_time(&pid, scene, framenr, &startframe, &endframe, &timescale);
442         clmd->sim_parms->timescale= timescale;
443
444         if(!result) {
445                 BKE_ptcache_invalidate(cache);
446                 return dm;
447         }
448
449         if(clmd->sim_parms->reset
450                 || (framenr == (startframe - clmd->sim_parms->preroll) && clmd->sim_parms->preroll != 0)
451                 || (clmd->clothObject && result->getNumVerts(result) != clmd->clothObject->numverts))
452         {
453                 clmd->sim_parms->reset = 0;
454                 cache->flag |= PTCACHE_OUTDATED;
455                 BKE_ptcache_id_reset(scene, &pid, PTCACHE_RESET_OUTDATED);
456                 BKE_ptcache_validate(cache, 0);
457                 cache->last_exact= 0;
458                 cache->flag &= ~PTCACHE_REDO_NEEDED;
459                 return result;
460         }
461         
462         // unused in the moment, calculated separately in implicit.c
463         clmd->sim_parms->dt = clmd->sim_parms->timescale / clmd->sim_parms->stepsPerFrame;
464
465         /* handle continuous simulation with the play button */
466         if(BKE_ptcache_get_continue_physics() || ((clmd->sim_parms->preroll > 0) && (framenr > startframe - clmd->sim_parms->preroll) && (framenr < startframe))) {
467                 BKE_ptcache_invalidate(cache);
468
469                 /* do simulation */
470                 if(!do_init_cloth(ob, clmd, result, framenr))
471                         return result;
472
473                 do_step_cloth(ob, clmd, result, framenr);
474                 cloth_to_object(ob, clmd, result);
475
476                 return result;
477         }
478
479         /* simulation is only active during a specific period */
480         if(framenr < startframe) {
481                 BKE_ptcache_invalidate(cache);
482                 return result;
483         }
484         else if(framenr > endframe) {
485                 framenr= endframe;
486         }
487
488         if(cache->flag & PTCACHE_SIMULATION_VALID)
489                 framedelta= framenr - cache->simframe;
490         else
491                 framedelta= -1;
492
493         /* initialize simulation data if it didn't exist already */
494         if(!do_init_cloth(ob, clmd, result, framenr))
495                 return result;
496
497         if((framenr == startframe) && (clmd->sim_parms->preroll == 0)) {
498                 BKE_ptcache_id_reset(scene, &pid, PTCACHE_RESET_OUTDATED);
499                 do_init_cloth(ob, clmd, result, framenr);
500                 BKE_ptcache_validate(cache, framenr);
501                 cache->flag &= ~PTCACHE_REDO_NEEDED;
502                 return result;
503         }
504
505         /* try to read from cache */
506         cache_result = BKE_ptcache_read_cache(&pid, (float)framenr+scene->r.subframe, scene->r.frs_sec);
507
508         if(cache_result == PTCACHE_READ_EXACT || cache_result == PTCACHE_READ_INTERPOLATED) {
509                 implicit_set_positions(clmd);
510                 cloth_to_object (ob, clmd, result);
511
512                 BKE_ptcache_validate(cache, framenr);
513
514                 if(cache_result == PTCACHE_READ_INTERPOLATED && cache->flag & PTCACHE_REDO_NEEDED)
515                         BKE_ptcache_write_cache(&pid, framenr);
516
517                 return result;
518         }
519         else if(cache_result==PTCACHE_READ_OLD) {
520                 implicit_set_positions(clmd);
521         }
522         else if( /*ob->id.lib ||*/ (cache->flag & PTCACHE_BAKED)) { /* 2.4x disabled lib, but this can be used in some cases, testing further - campbell */
523                 /* if baked and nothing in cache, do nothing */
524                 BKE_ptcache_invalidate(cache);
525                 return result;
526         }
527
528         /* if on second frame, write cache for first frame */
529         if(cache->simframe == startframe && (cache->flag & PTCACHE_OUTDATED || cache->last_exact==0))
530                 BKE_ptcache_write_cache(&pid, startframe);
531
532         clmd->sim_parms->timescale *= framenr - cache->simframe;
533
534         /* do simulation */
535         BKE_ptcache_validate(cache, framenr);
536
537         if(!do_step_cloth(ob, clmd, result, framenr)) {
538                 BKE_ptcache_invalidate(cache);
539         }
540         else
541                 BKE_ptcache_write_cache(&pid, framenr);
542
543         cloth_to_object (ob, clmd, result);
544
545         return result;
546 }
547
548 /* frees all */
549 void cloth_free_modifier(ClothModifierData *clmd )
550 {
551         Cloth   *cloth = NULL;
552         
553         if ( !clmd )
554                 return;
555
556         cloth = clmd->clothObject;
557
558         
559         if ( cloth )
560         {       
561                 // If our solver provides a free function, call it
562                 if ( solvers [clmd->sim_parms->solver_type].free )
563                 {
564                         solvers [clmd->sim_parms->solver_type].free ( clmd );
565                 }
566
567                 // Free the verts.
568                 if ( cloth->verts != NULL )
569                         MEM_freeN ( cloth->verts );
570
571                 cloth->verts = NULL;
572                 cloth->numverts = 0;
573
574                 // Free the springs.
575                 if ( cloth->springs != NULL )
576                 {
577                         LinkNode *search = cloth->springs;
578                         while(search)
579                         {
580                                 ClothSpring *spring = search->link;
581                                                 
582                                 MEM_freeN ( spring );
583                                 search = search->next;
584                         }
585                         BLI_linklist_free(cloth->springs, NULL);
586                 
587                         cloth->springs = NULL;
588                 }
589
590                 cloth->springs = NULL;
591                 cloth->numsprings = 0;
592
593                 // free BVH collision tree
594                 if ( cloth->bvhtree )
595                         BLI_bvhtree_free ( cloth->bvhtree );
596                 
597                 if ( cloth->bvhselftree )
598                         BLI_bvhtree_free ( cloth->bvhselftree );
599
600                 // we save our faces for collision objects
601                 if ( cloth->mfaces )
602                         MEM_freeN ( cloth->mfaces );
603                 
604                 if(cloth->edgehash)
605                         BLI_edgehash_free ( cloth->edgehash, NULL );
606                 
607                 
608                 /*
609                 if(clmd->clothObject->facemarks)
610                 MEM_freeN(clmd->clothObject->facemarks);
611                 */
612                 MEM_freeN ( cloth );
613                 clmd->clothObject = NULL;
614         }
615 }
616
617 /* frees all */
618 void cloth_free_modifier_extern ( ClothModifierData *clmd )
619 {
620         Cloth   *cloth = NULL;
621         if(G.rt > 0)
622                 printf("cloth_free_modifier_extern\n");
623         
624         if ( !clmd )
625                 return;
626
627         cloth = clmd->clothObject;
628         
629         if ( cloth )
630         {       
631                 if(G.rt > 0)
632                         printf("cloth_free_modifier_extern in\n");
633                 
634                 // If our solver provides a free function, call it
635                 if ( solvers [clmd->sim_parms->solver_type].free )
636                 {
637                         solvers [clmd->sim_parms->solver_type].free ( clmd );
638                 }
639
640                 // Free the verts.
641                 if ( cloth->verts != NULL )
642                         MEM_freeN ( cloth->verts );
643
644                 cloth->verts = NULL;
645                 cloth->numverts = 0;
646
647                 // Free the springs.
648                 if ( cloth->springs != NULL )
649                 {
650                         LinkNode *search = cloth->springs;
651                         while(search)
652                         {
653                                 ClothSpring *spring = search->link;
654                                                 
655                                 MEM_freeN ( spring );
656                                 search = search->next;
657                         }
658                         BLI_linklist_free(cloth->springs, NULL);
659                 
660                         cloth->springs = NULL;
661                 }
662
663                 cloth->springs = NULL;
664                 cloth->numsprings = 0;
665
666                 // free BVH collision tree
667                 if ( cloth->bvhtree )
668                         BLI_bvhtree_free ( cloth->bvhtree );
669                 
670                 if ( cloth->bvhselftree )
671                         BLI_bvhtree_free ( cloth->bvhselftree );
672
673                 // we save our faces for collision objects
674                 if ( cloth->mfaces )
675                         MEM_freeN ( cloth->mfaces );
676                 
677                 if(cloth->edgehash)
678                         BLI_edgehash_free ( cloth->edgehash, NULL );
679                 
680                 
681                 /*
682                 if(clmd->clothObject->facemarks)
683                 MEM_freeN(clmd->clothObject->facemarks);
684                 */
685                 MEM_freeN ( cloth );
686                 clmd->clothObject = NULL;
687         }
688 }
689
690 /******************************************************************************
691 *
692 * Internal functions.
693 *
694 ******************************************************************************/
695
696 /**
697  * cloth_to_object - copies the deformed vertices to the object.
698  *
699  **/
700 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, DerivedMesh *dm)
701 {
702         unsigned int    i = 0;
703         MVert *mvert = NULL;
704         unsigned int numverts;
705         Cloth *cloth = clmd->clothObject;
706
707         if (clmd->clothObject) {
708                 /* inverse matrix is not uptodate... */
709                 invert_m4_m4(ob->imat, ob->obmat);
710
711                 mvert = CDDM_get_verts(dm);
712                 numverts = dm->getNumVerts(dm);
713
714                 for (i = 0; i < numverts; i++)
715                 {
716                         VECCOPY (mvert[i].co, cloth->verts[i].x);
717                         mul_m4_v3(ob->imat, mvert[i].co);       /* cloth is in global coords */
718                 }
719         }
720 }
721
722
723 int cloth_uses_vgroup(ClothModifierData *clmd)
724 {
725         return (((clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING ) || 
726                 (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )) && 
727                 ((clmd->sim_parms->vgroup_mass>0) || 
728                 (clmd->sim_parms->vgroup_struct>0)||
729                 (clmd->sim_parms->vgroup_bend>0)));
730 }
731
732 /**
733  * cloth_apply_vgroup - applies a vertex group as specified by type
734  *
735  **/
736 /* can be optimized to do all groups in one loop */
737 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm )
738 {
739         int i = 0;
740         int j = 0;
741         MDeformVert *dvert = NULL;
742         Cloth *clothObj = NULL;
743         int numverts;
744         float goalfac = 0;
745         ClothVertex *verts = NULL;
746
747         if (!clmd || !dm) return;
748
749         clothObj = clmd->clothObject;
750
751         numverts = dm->getNumVerts ( dm );
752
753         verts = clothObj->verts;
754         
755         if (cloth_uses_vgroup(clmd))
756         {
757                 for ( i = 0; i < numverts; i++, verts++ )
758                 {       
759                         dvert = dm->getVertData ( dm, i, CD_MDEFORMVERT );
760                         if ( dvert )
761                         {
762                                 for ( j = 0; j < dvert->totweight; j++ )
763                                 {
764                                         if (( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_mass-1)) && (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL ))
765                                         {
766                                                 verts->goal = dvert->dw [j].weight;
767                                                 goalfac= 1.0f;
768                                                 
769                                                 /*
770                                                 // Kicking goal factor to simplify things...who uses that anyway?
771                                                 // ABS ( clmd->sim_parms->maxgoal - clmd->sim_parms->mingoal );
772                                                 */
773                                                 
774                                                 verts->goal  = ( float ) pow ( verts->goal , 4.0f );
775                                                 if ( verts->goal >=SOFTGOALSNAP )
776                                                 {
777                                                          verts->flags |= CLOTH_VERT_FLAG_PINNED;
778                                                 }
779                                         }
780                                         
781                                         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING )
782                                         {
783                                                 if( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_struct-1))
784                                                 {
785                                                         verts->struct_stiff = dvert->dw [j].weight;
786                                                         verts->shear_stiff = dvert->dw [j].weight;
787                                                 }
788                                                 
789                                                 if( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_bend-1))
790                                                 {
791                                                         verts->bend_stiff = dvert->dw [j].weight;
792                                                 }
793                                         }
794                                         /*
795                                         // for later
796                                         if( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_weight-1))
797                                         {
798                                                 verts->mass = dvert->dw [j].weight;
799                                         }
800                                         */
801                                 }
802                         }
803                 }
804         }
805 }
806
807 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float UNUSED(framenr), int first)
808 {
809         int i = 0;
810         MVert *mvert = NULL;
811         ClothVertex *verts = NULL;
812         float (*shapekey_rest)[3]= NULL;
813         float tnull[3] = {0,0,0};
814         Cloth *cloth = NULL;
815         float maxdist = 0;
816
817         // If we have a clothObject, free it. 
818         if ( clmd->clothObject != NULL )
819         {
820                 cloth_free_modifier ( clmd );
821                 if(G.rt > 0)
822                         printf("cloth_free_modifier cloth_from_object\n");
823         }
824
825         // Allocate a new cloth object.
826         clmd->clothObject = MEM_callocN ( sizeof ( Cloth ), "cloth" );
827         if ( clmd->clothObject )
828         {
829                 clmd->clothObject->old_solver_type = 255;
830                 // clmd->clothObject->old_collision_type = 255;
831                 cloth = clmd->clothObject;
832                 clmd->clothObject->edgehash = NULL;
833         }
834         else if ( !clmd->clothObject )
835         {
836                 modifier_setError ( & ( clmd->modifier ), "Out of memory on allocating clmd->clothObject." );
837                 return 0;
838         }
839
840         // mesh input objects need DerivedMesh
841         if ( !dm )
842                 return 0;
843
844         cloth_from_mesh ( clmd, dm );
845
846         // create springs 
847         clmd->clothObject->springs = NULL;
848         clmd->clothObject->numsprings = -1;
849         
850         if( clmd->sim_parms->shapekey_rest )
851                 shapekey_rest = dm->getVertDataArray ( dm, CD_CLOTH_ORCO );
852
853         mvert = dm->getVertArray ( dm );
854
855         verts = clmd->clothObject->verts;
856
857         // set initial values
858         for ( i = 0; i < dm->getNumVerts(dm); i++, verts++ )
859         {
860                 if(first)
861                 {
862                         copy_v3_v3( verts->x, mvert[i].co );
863
864                         mul_m4_v3( ob->obmat, verts->x );
865
866                         if( shapekey_rest ) {
867                                 verts->xrest= shapekey_rest[i];
868                                 mul_m4_v3( ob->obmat, verts->xrest );
869                         }
870                         else
871                                 verts->xrest = verts->x;
872                 }
873                 
874                 /* no GUI interface yet */
875                 verts->mass = clmd->sim_parms->mass; 
876                 verts->impulse_count = 0;
877
878                 if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )
879                         verts->goal= clmd->sim_parms->defgoal;
880                 else
881                         verts->goal= 0.0f;
882
883                 verts->flags = 0;
884                 VECCOPY ( verts->xold, verts->x );
885                 VECCOPY ( verts->xconst, verts->x );
886                 VECCOPY ( verts->txold, verts->x );
887                 VECCOPY ( verts->tx, verts->x );
888                 mul_v3_fl( verts->v, 0.0f );
889
890                 verts->impulse_count = 0;
891                 VECCOPY ( verts->impulse, tnull );
892         }
893         
894         // apply / set vertex groups
895         // has to be happen before springs are build!
896         cloth_apply_vgroup (clmd, dm);
897
898         if ( !cloth_build_springs ( clmd, dm ) )
899         {
900                 cloth_free_modifier ( clmd );
901                 modifier_setError ( & ( clmd->modifier ), "Can't build springs." );
902                 printf("cloth_free_modifier cloth_build_springs\n");
903                 return 0;
904         }
905         
906         for ( i = 0; i < dm->getNumVerts(dm); i++)
907         {
908                 if((!(cloth->verts[i].flags & CLOTH_VERT_FLAG_PINNED)) && (cloth->verts[i].goal > ALMOST_ZERO))
909                 {
910                         cloth_add_spring (clmd, i, i, 0.0, CLOTH_SPRING_TYPE_GOAL);
911                 }
912         }
913         
914         // init our solver
915         if ( solvers [clmd->sim_parms->solver_type].init ) {
916                 solvers [clmd->sim_parms->solver_type].init ( ob, clmd );
917         }
918         
919         if(!first)
920                 implicit_set_positions(clmd);
921
922         clmd->clothObject->bvhtree = bvhtree_build_from_cloth ( clmd, clmd->coll_parms->epsilon );
923         
924         for(i = 0; i < dm->getNumVerts(dm); i++)
925         {
926                 maxdist = MAX2(maxdist, clmd->coll_parms->selfepsilon* ( cloth->verts[i].avg_spring_len*2.0));
927         }
928         
929         clmd->clothObject->bvhselftree = bvhselftree_build_from_cloth ( clmd, maxdist );
930
931         return 1;
932 }
933
934 static void cloth_from_mesh ( ClothModifierData *clmd, DerivedMesh *dm )
935 {
936         unsigned int numverts = dm->getNumVerts ( dm );
937         unsigned int numfaces = dm->getNumFaces ( dm );
938         MFace *mface = CDDM_get_faces(dm);
939         unsigned int i = 0;
940
941         /* Allocate our vertices. */
942         clmd->clothObject->numverts = numverts;
943         clmd->clothObject->verts = MEM_callocN ( sizeof ( ClothVertex ) * clmd->clothObject->numverts, "clothVertex" );
944         if ( clmd->clothObject->verts == NULL )
945         {
946                 cloth_free_modifier ( clmd );
947                 modifier_setError ( & ( clmd->modifier ), "Out of memory on allocating clmd->clothObject->verts." );
948                 printf("cloth_free_modifier clmd->clothObject->verts\n");
949                 return;
950         }
951
952         // save face information
953         clmd->clothObject->numfaces = numfaces;
954         clmd->clothObject->mfaces = MEM_callocN ( sizeof ( MFace ) * clmd->clothObject->numfaces, "clothMFaces" );
955         if ( clmd->clothObject->mfaces == NULL )
956         {
957                 cloth_free_modifier ( clmd );
958                 modifier_setError ( & ( clmd->modifier ), "Out of memory on allocating clmd->clothObject->mfaces." );
959                 printf("cloth_free_modifier clmd->clothObject->mfaces\n");
960                 return;
961         }
962         for ( i = 0; i < numfaces; i++ )
963                 memcpy ( &clmd->clothObject->mfaces[i], &mface[i], sizeof ( MFace ) );
964
965         /* Free the springs since they can't be correct if the vertices
966         * changed.
967         */
968         if ( clmd->clothObject->springs != NULL )
969                 MEM_freeN ( clmd->clothObject->springs );
970
971 }
972
973 /***************************************************************************************
974 * SPRING NETWORK BUILDING IMPLEMENTATION BEGIN
975 ***************************************************************************************/
976
977 // be carefull: implicit solver has to be resettet when using this one!
978 // --> only for implicit handling of this spring!
979 int cloth_add_spring ( ClothModifierData *clmd, unsigned int indexA, unsigned int indexB, float restlength, int spring_type)
980 {
981         Cloth *cloth = clmd->clothObject;
982         ClothSpring *spring = NULL;
983         
984         if(cloth)
985         {
986                 // TODO: look if this spring is already there
987                 
988                 spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
989                 
990                 if(!spring)
991                         return 0;
992                 
993                 spring->ij = indexA;
994                 spring->kl = indexB;
995                 spring->restlen =  restlength;
996                 spring->type = spring_type;
997                 spring->flags = 0;
998                 spring->stiffness = 0;
999                 
1000                 cloth->numsprings++;
1001         
1002                 BLI_linklist_prepend ( &cloth->springs, spring );
1003                 
1004                 return 1;
1005         }
1006         return 0;
1007 }
1008
1009 static void cloth_free_errorsprings(Cloth *cloth, EdgeHash *UNUSED(edgehash), LinkNode **edgelist)
1010 {
1011         unsigned int i = 0;
1012         
1013         if ( cloth->springs != NULL )
1014         {
1015                 LinkNode *search = cloth->springs;
1016                 while(search)
1017                 {
1018                         ClothSpring *spring = search->link;
1019                                                 
1020                         MEM_freeN ( spring );
1021                         search = search->next;
1022                 }
1023                 BLI_linklist_free(cloth->springs, NULL);
1024                 
1025                 cloth->springs = NULL;
1026         }
1027         
1028         if(edgelist)
1029         {
1030                 for ( i = 0; i < cloth->numverts; i++ )
1031                 {
1032                         BLI_linklist_free ( edgelist[i],NULL );
1033                 }
1034
1035                 MEM_freeN ( edgelist );
1036         }
1037         
1038         if(cloth->edgehash)
1039                 BLI_edgehash_free ( cloth->edgehash, NULL );
1040 }
1041
1042 static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm )
1043 {
1044         Cloth *cloth = clmd->clothObject;
1045         ClothSpring *spring = NULL, *tspring = NULL, *tspring2 = NULL;
1046         unsigned int struct_springs = 0, shear_springs=0, bend_springs = 0;
1047         int i = 0;
1048         int numverts = dm->getNumVerts ( dm );
1049         int numedges = dm->getNumEdges ( dm );
1050         int numfaces = dm->getNumFaces ( dm );
1051         MEdge *medge = CDDM_get_edges ( dm );
1052         MFace *mface = CDDM_get_faces ( dm );
1053         int index2 = 0; // our second vertex index
1054         LinkNode **edgelist = NULL;
1055         EdgeHash *edgehash = NULL;
1056         LinkNode *search = NULL, *search2 = NULL;
1057         float temp[3];
1058         
1059         // error handling
1060         if ( numedges==0 )
1061                 return 0;
1062
1063         cloth->springs = NULL;
1064
1065         edgelist = MEM_callocN ( sizeof ( LinkNode * ) * numverts, "cloth_edgelist_alloc" );
1066         
1067         if(!edgelist)
1068                 return 0;
1069         
1070         for ( i = 0; i < numverts; i++ )
1071         {
1072                 edgelist[i] = NULL;
1073         }
1074
1075         if ( cloth->springs )
1076                 MEM_freeN ( cloth->springs );
1077
1078         // create spring network hash
1079         edgehash = BLI_edgehash_new();
1080
1081         // structural springs
1082         for ( i = 0; i < numedges; i++ )
1083         {
1084                 spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1085
1086                 if ( spring )
1087                 {
1088                         spring->ij = MIN2(medge[i].v1, medge[i].v2);
1089                         spring->kl = MAX2(medge[i].v2, medge[i].v1);
1090                         VECSUB ( temp, cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest );
1091                         spring->restlen =  sqrt ( INPR ( temp, temp ) );
1092                         clmd->sim_parms->avg_spring_len += spring->restlen;
1093                         cloth->verts[spring->ij].avg_spring_len += spring->restlen;
1094                         cloth->verts[spring->kl].avg_spring_len += spring->restlen;
1095                         cloth->verts[spring->ij].spring_count++;
1096                         cloth->verts[spring->kl].spring_count++;
1097                         spring->type = CLOTH_SPRING_TYPE_STRUCTURAL;
1098                         spring->flags = 0;
1099                         spring->stiffness = (cloth->verts[spring->kl].struct_stiff + cloth->verts[spring->ij].struct_stiff) / 2.0;
1100                         struct_springs++;
1101                         
1102                         BLI_linklist_prepend ( &cloth->springs, spring );
1103                 }
1104                 else
1105                 {
1106                         cloth_free_errorsprings(cloth, edgehash, edgelist);
1107                         return 0;
1108                 }
1109         }
1110         
1111         if(struct_springs > 0)
1112                 clmd->sim_parms->avg_spring_len /= struct_springs;
1113         
1114         for(i = 0; i < numverts; i++)
1115         {
1116                 cloth->verts[i].avg_spring_len = cloth->verts[i].avg_spring_len * 0.49 / ((float)cloth->verts[i].spring_count);
1117         }
1118         
1119         // shear springs
1120         for ( i = 0; i < numfaces; i++ )
1121         {
1122                 // triangle faces already have shear springs due to structural geometry
1123                 if ( !mface[i].v4 )
1124                         continue; 
1125                 
1126                 spring = ( ClothSpring *) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1127                 
1128                 if(!spring)
1129                 {
1130                         cloth_free_errorsprings(cloth, edgehash, edgelist);
1131                         return 0;
1132                 }
1133
1134                 spring->ij = MIN2(mface[i].v1, mface[i].v3);
1135                 spring->kl = MAX2(mface[i].v3, mface[i].v1);
1136                 VECSUB ( temp, cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest );
1137                 spring->restlen =  sqrt ( INPR ( temp, temp ) );
1138                 spring->type = CLOTH_SPRING_TYPE_SHEAR;
1139                 spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0;
1140
1141                 BLI_linklist_append ( &edgelist[spring->ij], spring );
1142                 BLI_linklist_append ( &edgelist[spring->kl], spring );
1143                 shear_springs++;
1144
1145                 BLI_linklist_prepend ( &cloth->springs, spring );
1146
1147                 
1148                 // if ( mface[i].v4 ) --> Quad face
1149                 spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1150                 
1151                 if(!spring)
1152                 {
1153                         cloth_free_errorsprings(cloth, edgehash, edgelist);
1154                         return 0;
1155                 }
1156
1157                 spring->ij = MIN2(mface[i].v2, mface[i].v4);
1158                 spring->kl = MAX2(mface[i].v4, mface[i].v2);
1159                 VECSUB ( temp, cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest );
1160                 spring->restlen =  sqrt ( INPR ( temp, temp ) );
1161                 spring->type = CLOTH_SPRING_TYPE_SHEAR;
1162                 spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0;
1163
1164                 BLI_linklist_append ( &edgelist[spring->ij], spring );
1165                 BLI_linklist_append ( &edgelist[spring->kl], spring );
1166                 shear_springs++;
1167
1168                 BLI_linklist_prepend ( &cloth->springs, spring );
1169         }
1170         
1171         if(numfaces) {
1172                 // bending springs
1173                 search2 = cloth->springs;
1174                 for ( i = struct_springs; i < struct_springs+shear_springs; i++ )
1175                 {
1176                         if ( !search2 )
1177                                 break;
1178
1179                         tspring2 = search2->link;
1180                         search = edgelist[tspring2->kl];
1181                         while ( search )
1182                         {
1183                                 tspring = search->link;
1184                                 index2 = ( ( tspring->ij==tspring2->kl ) ? ( tspring->kl ) : ( tspring->ij ) );
1185                                 
1186                                 // check for existing spring
1187                                 // check also if startpoint is equal to endpoint
1188                                 if ( !BLI_edgehash_haskey ( edgehash, MIN2(tspring2->ij, index2), MAX2(tspring2->ij, index2) )
1189                                 && ( index2!=tspring2->ij ) )
1190                                 {
1191                                         spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1192                                         
1193                                         if(!spring)
1194                                         {
1195                                                 cloth_free_errorsprings(cloth, edgehash, edgelist);
1196                                                 return 0;
1197                                         }
1198
1199                                         spring->ij = MIN2(tspring2->ij, index2);
1200                                         spring->kl = MAX2(tspring2->ij, index2);
1201                                         VECSUB ( temp, cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest );
1202                                         spring->restlen =  sqrt ( INPR ( temp, temp ) );
1203                                         spring->type = CLOTH_SPRING_TYPE_BENDING;
1204                                         spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0;
1205                                         BLI_edgehash_insert ( edgehash, spring->ij, spring->kl, NULL );
1206                                         bend_springs++;
1207
1208                                         BLI_linklist_prepend ( &cloth->springs, spring );
1209                                 }
1210                                 search = search->next;
1211                         }
1212                         search2 = search2->next;
1213                 }
1214         }
1215         else if(struct_springs > 2) {
1216                 /* bending springs for hair strands */
1217                 /* The current algorightm only goes through the edges in order of the mesh edges list   */
1218                 /* and makes springs between the outer vert of edges sharing a vertice. This works just */
1219                 /* fine for hair, but not for user generated string meshes. This could/should be later  */
1220                 /* extended to work with non-ordered edges so that it can be used for general "rope             */
1221                 /* dynamics" without the need for the vertices or edges to be ordered through the length*/
1222                 /* of the strands. -jahka */
1223                 search = cloth->springs;
1224                 search2 = search->next;
1225                 while(search && search2)
1226                 {
1227                         tspring = search->link;
1228                         tspring2 = search2->link;
1229
1230                         if(tspring->ij == tspring2->kl) {
1231                                 spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1232                                 
1233                                 if(!spring)
1234                                 {
1235                                         cloth_free_errorsprings(cloth, edgehash, edgelist);
1236                                         return 0;
1237                                 }
1238
1239                                 spring->ij = tspring2->ij;
1240                                 spring->kl = tspring->kl;
1241                                 VECSUB ( temp, cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest );
1242                                 spring->restlen =  sqrt ( INPR ( temp, temp ) );
1243                                 spring->type = CLOTH_SPRING_TYPE_BENDING;
1244                                 spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0;
1245                                 bend_springs++;
1246
1247                                 BLI_linklist_prepend ( &cloth->springs, spring );
1248                         }
1249                         
1250                         search = search->next;
1251                         search2 = search2->next;
1252                 }
1253         }
1254         
1255         /* insert other near springs in edgehash AFTER bending springs are calculated (for selfcolls) */
1256         for ( i = 0; i < numedges; i++ ) // struct springs
1257                 BLI_edgehash_insert ( edgehash, MIN2(medge[i].v1, medge[i].v2), MAX2(medge[i].v2, medge[i].v1), NULL );
1258         
1259         for ( i = 0; i < numfaces; i++ ) // edge springs
1260         {
1261                 if(mface[i].v4)
1262                 {
1263                         BLI_edgehash_insert ( edgehash, MIN2(mface[i].v1, mface[i].v3), MAX2(mface[i].v3, mface[i].v1), NULL );
1264                         
1265                         BLI_edgehash_insert ( edgehash, MIN2(mface[i].v2, mface[i].v4), MAX2(mface[i].v2, mface[i].v4), NULL );
1266                 }
1267         }
1268         
1269         
1270         cloth->numsprings = struct_springs + shear_springs + bend_springs;
1271         
1272         if ( edgelist )
1273         {
1274                 for ( i = 0; i < numverts; i++ )
1275                 {
1276                         BLI_linklist_free ( edgelist[i],NULL );
1277                 }
1278         
1279                 MEM_freeN ( edgelist );
1280         }
1281         
1282         cloth->edgehash = edgehash;
1283         
1284         if(G.rt>0)
1285                 printf("avg_len: %f\n",clmd->sim_parms->avg_spring_len);
1286
1287         return 1;
1288
1289 } /* cloth_build_springs */
1290 /***************************************************************************************
1291 * SPRING NETWORK BUILDING IMPLEMENTATION END
1292 ***************************************************************************************/
1293