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