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